When Are Nonconvex Problems Not Scary?
It addresses the challenge of efficiently solving nonconvex problems in applications like dictionary learning and phase retrieval, though it is incremental as it builds on known structures.
The paper tackles nonconvex optimization problems with specific benign structures, such as all local minimizers being global, and presents a second-order trust-region algorithm that provably converges efficiently to a global minimizer without special initializations.
In this note, we focus on smooth nonconvex optimization problems that obey: (1) all local minimizers are also global; and (2) around any saddle point or local maximizer, the objective has a negative directional curvature. Concrete applications such as dictionary learning, generalized phase retrieval, and orthogonal tensor decomposition are known to induce such structures. We describe a second-order trust-region algorithm that provably converges to a global minimizer efficiently, without special initializations. Finally we highlight alternatives, and open problems in this direction.