 |
ML Newsnew | past | best | rss | submit | about |
| When Are Nonconvex Optimization Problems Not Scary? (2015) (arxiv.org) | |
| 1 point by tpudlik on Feb 3, 2018 | hide | past | pdf | 1 comment on HN | |
|
In plain words: Some tricky optimization problems hide a comfort: every local bottom is the true best, and every trap or peak has a downhill direction. A method that checks curvature slides past these traps and reaches the best answer from any starting point. Abstract · When Are Nonconvex Problems Not Scary?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. | |
| add comment on HN |
Many problems arising from scientific and engineering applications can be naturally formulated as optimization problems, most of which are nonconvex. For nonconvex problems, obtaining a local minimizer is computationally hard in theory, never mind the global minimizer. In practice, however, simple numerical methods often work surprisingly well in finding high-quality solutions for specific problems at hand.
In this talk, I will describe our recent effort in bridging the mysterious theory-practice gap for nonconvex optimization. I will highlight a family of nonconvex problems that can be solved to global optimality using simple numerical methods, independent of initialization. This family has the characteristic global structure that (1) all local minimizers are global, and (2) all saddle points have directional negative curvatures. Problems lying in this family cover various applications across machine learning, signal processing, scientific imaging, and more. I will focus on two examples we worked out: learning sparsifying bases for massive data and recovery of complex signals from phaseless measurements. In both examples, the benign global structure allows us to derive geometric insights and computational results that are inaccessible from previous methods. In contrast, alternative approaches to solving nonconvex problems often entail either expensive convex relaxation (e.g., solving large-scale semidefinite programs) or delicate problem-specific initializations.
Completing and enriching this framework is an active research endeavor that is being undertaken by several research communities. At the end of the talk, I will discuss open problems to be tackled to move forward.