2018/03/06 by Damek Davis, Dmitriy Drusvyatskiy, Davis, Damek +5 · 9 citations
Mathematics · #65K05 #65K10 #90C15 #90C30 #FOS: Mathematics #Optimization and Control (math.OC) #math.OC #msc:65K05 #msc:65K10 #msc:90C15 #msc:90C30
paper · pdf · doi:10.48550/arxiv.1803.02461
16 pages, 3 figures
arxiv created 2018/03/06 · arxiv updated 2018/03/08
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.