Subgradient Methods for Sharp Weakly Convex Functions
Subgradient Methods for Sharp Weakly Convex Functions
复制标题
DOI：
10.1007/s10957-018-1372-8
复制
发表时间：
2018-03
影响因子：
1.9
通讯作者：
Damek Davis;D. Drusvyatskiy;Kellie J. MacPhee;C. Paquette
中科院分区：
文献类型：
--
作者：
Damek Davis;D. Drusvyatskiy;Kellie J. MacPhee;C. Paquette
次梯度法线性收敛于一个凸函数，该凸函数远离其解集急剧增长。在这项工作中，我们表明，同样是真实的尖锐的功能，只有弱凸，提供了次梯度方法的初始化在一个固定的管周围的解决方案集。各种各样的统计和信号处理任务都配备了良好的初始化，并可证明会导致弱凸和尖锐的公式。因此，在这种情况下，次梯度方法可以作为廉价的本地搜索程序。我们说明了相位恢复和协方差估计问题上提出的技术。
Subgradient methods converge linearly on a convex function that grows sharply away from its solution set. In this work, we show that the same is true for sharp functions that are only weakly convex, provided that the subgradient methods are initialized within a fixed tube around the solution set. A variety of statistical and signal processing tasks come equipped with good initialization and provably lead to formulations that are both weakly convex and sharp. Therefore, in such settings, subgradient methods can serve as inexpensive local search procedures. We illustrate the proposed techniques on phase retrieval and covariance estimation problems.