Analysis of Nonlinear Decision-Making and Optimization Problems: Theory of Global Optimally and Linear-Time Algorithms
Abstract
Even under the ideal condition of no noise and zero approximation error, many highly efficient 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 principals. 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 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. In this work, we studied the optimization landscape of the nonconvex 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 developed the notion of kernel structure property to obtain necessary and sufficient conditions for the inexistence of spurious local solution of 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 simplified the conditions for a certain class of problems to show their satisfaction and applied them to data analytics for power systems.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 16, 2021
- Accession Number
- AD1140359
Entities
People
- Somayeh Sojoudi
Organizations
- University of California Regents