论文标题
随机互补复合最小化的最佳算法
Optimal Algorithms for Stochastic Complementary Composite Minimization
论文作者
论文摘要
受统计和机器学习中的正则化技术的启发，我们研究了随机环境中的互补综合最小化。这个问题对应于具有随机一阶甲骨文的（弱）平滑函数的最小化，以及结构化均匀凸（可能是非平滑和非lipschitz）正则化项的结构化。尽管在密切相关的环境方面进行了大量工作，但在我们的工作之前，对于此问题，尚无复杂性界限。我们通过在预期和高可能性方面提供新颖的过量风险范围来缩小这一差距。我们的算法几乎是最佳的，我们通过针对此类问题的新型较低的复杂性界限证明了这一点。我们通过提供数值结果将我们的方法与艺术的状态进行比较来结束。
Inspired by regularization techniques in statistics and machine learning, we study complementary composite minimization in the stochastic setting. This problem corresponds to the minimization of the sum of a (weakly) smooth function endowed with a stochastic first-order oracle, and a structured uniformly convex (possibly nonsmooth and non-Lipschitz) regularization term. Despite intensive work on closely related settings, prior to our work no complexity bounds for this problem were known. We close this gap by providing novel excess risk bounds, both in expectation and with high probability. Our algorithms are nearly optimal, which we prove via novel lower complexity bounds for this class of problems. We conclude by providing numerical results comparing our methods to the state of the art.
