论文标题
更快的随机交替方向方法，用于非convex优化
Faster Stochastic Alternating Direction Method of Multipliers for Nonconvex Optimization
论文作者
论文摘要
在本文中，我们通过使用新的随机路径综合差估计器（蜘蛛）（称为蜘蛛ADMM）提出了更快的随机交替方向方法（ADMM）进行非convex优化。此外，我们证明了蜘蛛ADMM达到了$ \ Mathcal {O}（n+N^{1/2}ε^{ - 1}）$的$ \ Mathcal {o}的复杂性的创纪录的增量一阶（IFO）$ $ \ Mathcal {o}（n^{1/2}）$，其中$ n $表示样本尺寸。作为本文的主要贡献之一，我们为非convex随机ADMM方法提供了一个新的理论分析框架，可提供最佳的IFO复杂性。基于这个新的分析框架，我们研究了现有的非Convex SVRG-ADMM和SAGA-ADMM方法的未解决的最佳IFO复杂性，并证明它们具有$ \ MATHCAL {O}的最佳IFO复杂性（N+N+N^{2/3}ε^{ - 1}）$。因此，蜘蛛ADMM将现有的随机ADMM方法提高了$ \ MATHCAL {O}（n^{1/6}）$。此外，我们将Spider-Admm扩展到在线设置，并提出更快的在线蜘蛛ADMM。我们的理论分析表明，在线蜘蛛admm具有$ \ Mathcal {O}（ε^{ - \ frac {3} {2}}）$的IFO复杂性，该$ \ \ nathcal {o}（O}（O}（ε^{ε^{ - \ frac { - \ frac {1}}}）提高了现有最佳结果。最后，基准数据集上的实验结果验证了所提出的算法的收敛速率比现有的非convex优化的ADMM算法更快。
In this paper, we propose a faster stochastic alternating direction method of multipliers (ADMM) for nonconvex optimization by using a new stochastic path-integrated differential estimator (SPIDER), called as SPIDER-ADMM. Moreover, we prove that the SPIDER-ADMM achieves a record-breaking incremental first-order oracle (IFO) complexity of $\mathcal{O}(n+n^{1/2}ε^{-1})$ for finding an $ε$-approximate stationary point, which improves the deterministic ADMM by a factor $\mathcal{O}(n^{1/2})$, where $n$ denotes the sample size. As one of major contribution of this paper, we provide a new theoretical analysis framework for nonconvex stochastic ADMM methods with providing the optimal IFO complexity. Based on this new analysis framework, we study the unsolved optimal IFO complexity of the existing non-convex SVRG-ADMM and SAGA-ADMM methods, and prove they have the optimal IFO complexity of $\mathcal{O}(n+n^{2/3}ε^{-1})$. Thus, the SPIDER-ADMM improves the existing stochastic ADMM methods by a factor of $\mathcal{O}(n^{1/6})$. Moreover, we extend SPIDER-ADMM to the online setting, and propose a faster online SPIDER-ADMM. Our theoretical analysis shows that the online SPIDER-ADMM has the IFO complexity of $\mathcal{O}(ε^{-\frac{3}{2}})$, which improves the existing best results by a factor of $\mathcal{O}(ε^{-\frac{1}{2}})$. Finally, the experimental results on benchmark datasets validate that the proposed algorithms have faster convergence rate than the existing ADMM algorithms for nonconvex optimization.
