Role of sparsity and structure in the optimization landscape of non-convex matrix sensing
- PDF / 1,597,396 Bytes
- 37 Pages / 439.37 x 666.142 pts Page_size
- 30 Downloads / 156 Views
Series A
Role of sparsity and structure in the optimization landscape of non-convex matrix sensing Igor Molybog1 · Somayeh Sojoudi1 · Javad Lavaei1 Received: 4 November 2019 / Accepted: 3 November 2020 © Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2020
Abstract In this work, we study the optimization landscape of the non-convex matrix sensing problem that is known to have many local minima in the worst case. Since the existing results are related to the notion of restricted isometry property (RIP) that cannot directly capture the underlying structure of a given problem, they can hardly be applied to real-world problems where the amount of data is not exorbitantly high. To address this issue, we develop the notion of kernel structure property to obtain necessary and sufficient conditions for the inexistence of spurious local solutions for any class of matrix sensing problems over a given search space. This notion precisely captures the underlying sparsity and structure of the problem, based on tools in conic optimization. We simplify the conditions for a certain class of problems to show their satisfaction and apply them to data analytics for power systems. Keywords Non-convex optimization · Spurious local minima · Matrix sensing
1 Introduction Even under the ideal condition of no noise and zero approximation error, many highlyefficient machine learning techniques involve solving potentially hard or intractable computational problems while learning from data. In practice, they are tackled by heuristic optimization algorithms, based on relaxations or greedy principles. The lack of guarantees on their performance limits their use in applications with significant cost of an error, impacting our ability to implement progressive data analysis techniques
B
Javad Lavaei [email protected] Igor Molybog [email protected] Somayeh Sojoudi [email protected]
1
University of California, Berkeley, CA, USA
123
I. Molybog et al.
in crucial social and economic systems, such as healthcare, transportation, and energy production and distribution. Commonly, non-convexity is the main obstacle for a guaranteed learning of continuous parameters. It is well known that many fundamental problems with a natural non-convex formulation are N P-hard [27]. Sophisticated techniques for addressing this issue, like generic convex relaxations, may require working in an unrealistically highdimensional space to guarantee the exactness of the solution. As a consequence of complicated geometrical structures, a non-convex function may contain an exponential number of saddle points and spurious local minima, and therefore local search algorithms may become trapped in any of those points. Nevertheless, empirical observations show positive results regarding the application of these approaches to several practically important instances. This provokes a major branch of research that aims to explain the success of experimental results in order to understand the boundaries of the applicability o
Data Loading...
