Low-rank Matrix Recovery Problem: Machine Learning and Polynomial Optimization
Abstract
Optimization appears in many key problems in machine learning (ML), such as training of natural networks, matrix sensing, reinforcement leaning, and statistical learning. The staggering advances made in artificial intelligence (AI) in the past 10 years are due, in part, to handling computationally intensive machine learning problems directly as non-convex optimization. Inspired by the recent advances in AI for solving non-convex optimization problems using low-complexity methods, in this project we study a fundamental class of optimization problems, named low-rank matrix recovery. This project is also motivated by our observation that solving an arbitrary polynomial optimization problem to global optimality can be reduced to a low-rank matrix recovery problem. There have been several works on special cases of this problem, leading to the notions of restricted isometry property (RIP) and incoherence. However, these notions are extremely restrictive and are not applicable to many practical problems as well as polynomial optimization.To address the above issues, the objective of this project is to develop a rich mathematical foundation for the low-rank matrix recovery problem. The following tasks will be performed:1) New complexity metric/measure for local search methods: Task 1 aims to develop a new complexity metric that applies to an arbitrary low-rank matrix recovery problem and includes RIP and incoherence as special cases. This metric will have two properties: (i) a small value for the metric guarantees that the problem is easy to solve using local search methods (i.e., it has no spurious solutions), (ii) a large value implies that an instance of the problem is difficult to solve.2) New complexity metric/measure for conic relaxations: Task 2 aims to redo Task~1 but for conic methods rather than local search methods. The focus is on different conic relaxations, such as semidefinite programs (SDPs). Since SDP is more powerful than local search methods and can avoid certain spurious solutions through convex relaxations, it is expected that the metrics for SDP and other conicformulations will be much stronger than the metric for local search methods.3) Role of structural properties: Based on the metrics to be obtained in Tasks 1 and 2, Task 3 aims to investigate how the structural properties of a low-rank matrix recovery problem affects the values of the metrics for local search and conic methods.4) Finding a near-global solution of polynomial optimization: Task 4 aims to investigate how to convert a given polynomial optimization problem into a high-dimensional low-rank matrix recovery problem that is easy to solve based on either local search or conic relaxations using Tasks 1-3. Since our metrics depend on the structural properties of the low-rank matrix recovery problem, the overall complexity of our method for finding a near-global solution is expected to depend on the underlying structure of the given polynomial optimization problem.5) Casestudies: Task 5 conducts several case studies on nonlinear optimization problems and machine learning problems. A particular emphasis will be placed on data-driven DoD applications, such as learning in uncertain environments.This project is expected to significantly advance the areas of nonlinear optimization and machine learning methods, with immediate impacts on DoD applications."Approved for Public Release"
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Nov 09, 2024
- Source ID
- N000142412673
Entities
People
- Javad Lavaei
Organizations
- Office of Naval Research
- United States Navy
- University of California Regents