Stochastic algorithms with geometric step decay converge linearly on sharp functions
Stochastic algorithms with geometric step decay converge linearly on sharp functions
复制标题
DOI：
10.1007/s10107-023-02003-w
复制
发表时间：
2019-07
期刊：
影响因子：
--
通讯作者：
Damek Davis;D. Drusvyatskiy;Vasileios Charisopoulos
中科院分区：
文献类型：
--
作者：
Damek Davis;D. Drusvyatskiy;Vasileios Charisopoulos
随机（次）梯度方法需要步长调度调整才能在实践中表现良好。经典的调整策略会衰减步长多项式，并导致（强）凸问题的最佳次线性率。另一种方案在非凸优化中很流行，称为几何步长衰减，每隔几个时期后将步长减半。在最近的工作中，几何步长衰减被证明可以在锐凸函数类的经典次线性速率的基础上呈指数级提高。在这项工作中，我们询问几何步长衰减是否同样改进了尖锐弱凸问题类的随机算法。这种损失是现代统计恢复问题的特征，并导致凸设置中不存在的新挑战：收敛区域是局部的，因此必须限制逃逸概率。我们的主要结果表明，对于一大类随机、尖锐、非光滑和非凸问题，几何步长衰减时间表赋予众所周知的算法局部线性（或接近线性）的全局最小化收敛速度。此保证适用于随机投影次梯度、近端点和 prox 线性算法。作为我们主要结果的应用，我们分析了两个统计恢复任务——相位检索和盲反卷积——并匹配高斯测量模型下最著名的保证，并在重尾分布下建立新的保证。
Stochastic (sub)gradient methods require step size schedule tuning to perform well in practice. Classical tuning strategies decay the step size polynomially and lead to optimal sublinear rates on (strongly) convex problems. An alternative schedule, popular in nonconvex optimization, is calledgeometric step decayand proceeds by halving the step size after every few epochs. In recent work, geometric step decay was shown to improve exponentially upon classical sublinear rates for the class ofsharpconvex functions. In this work, we ask whether geometric step decay similarly improves stochastic algorithms for the class of sharp weakly convex problems. Such losses feature in modern statistical recovery problems and lead to a new challenge not present in the convex setting: the region of convergence is local, so one must bound the probability of escape. Our main result shows that for a large class of stochastic, sharp, nonsmooth, and nonconvex problems a geometric step decay schedule endows well-known algorithms with a local linear (or nearly linear) rate of convergence to global minimizers. This guarantee applies to the stochastic projected subgradient, proximal point, and prox-linear algorithms. As an application of our main result, we analyze two statistical recovery tasks—phase retrieval and blind deconvolution—and match the best known guarantees under Gaussian measurement models and establish new guarantees under heavy-tailed distributions.