论文标题
非凸组成优化的动量降低方差
Momentum with Variance Reduction for Nonconvex Composition Optimization
论文作者
论文摘要
组成优化被广泛应用于非convex机器学习。已经开发了采用动量和差异技术的各种先进的随机算法，以优化组成。但是，这些算法并未完全利用这两种技术来加速收敛性，并且缺乏非convex优化的收敛保证。本文通过开发各种动量方案来补充现有文献，并以基于蜘蛛的方差降低非凸组成优化。特别是，与现有的Katyusha势头所要求的相比，我们的动量设计所需的近端映射评估次数所需的近端映射评估。此外，我们的算法达到了近乎最佳的样本复杂性，可导致非凸有限和在线组成优化，并在梯度显性条件下达到线性收敛速率。数值实验表明，我们的算法在非convex组成优化中的收敛速度明显快于现有算法。
Composition optimization is widely-applied in nonconvex machine learning. Various advanced stochastic algorithms that adopt momentum and variance reduction techniques have been developed for composition optimization. However, these algorithms do not fully exploit both techniques to accelerate the convergence and are lack of convergence guarantee in nonconvex optimization. This paper complements the existing literature by developing various momentum schemes with SPIDER-based variance reduction for non-convex composition optimization. In particular, our momentum design requires less number of proximal mapping evaluations per-iteration than that required by the existing Katyusha momentum. Furthermore, our algorithm achieves near-optimal sample complexity results in both non-convex finite-sum and online composition optimization and achieves a linear convergence rate under the gradient dominant condition. Numerical experiments demonstrate that our algorithm converges significantly faster than existing algorithms in nonconvex composition optimization.
