Global Guarantees for Robust Matrix Factorization: Promises of Nonconvex Formulations
Abstract
Optimization problems in the real world are characterized by being large-scale, noisy, and nonconvex. It is a well-known fact that n,on-convex optimization problems are difficult to solve in their worst case. To solve these problems, practitioners typically rely on, simple local-search algorithms, such as different variants of gradient descent, possibly followed by a heuristic method. However, d,ue to their underlying nonconvexity, these algorithms may get trapped at spurious local minima, i.e., those solutions that are not t,he best overall, or globally optimal. An important class of such problems in modern machine learning applications is low-rank matrix, factorization, where the goal is to recover a low-rank matrix, given a limited number of linear and possibly noisy measurements. De,spite the nonconvexity of low-rank matrix factorization, it has been recently shown that its smooth variants enjoy benign landscape,, i.e., they are either devoid of spurious local minima, or their spurious local minima can be efficiently escaped using local-search, algorithms. While these results are theoretically significant, they face major breakdowns in real applications, where the measureme,nts are grossly corrupted with noise, or when the true rank of the solution is unknown.This project will precisely pinpoint and reme,dy this fundamental drawback, by resorting to nonconvex and nonsmooth, but more tractable formulations of low-rank matrix factorizat,ion with unknown rank, specifically tailored to identify and reject random/adversarial noise in a systematic manner. A recurring the,me in our proposed research is a class of nonsmooth and nonconvex L1 minimization problems for low-rank matrix factorization that ar,e provably robust against large-and-sparse outliers. The overarching goals of this proposal are to develop a theoretical framework f,or studying the optimization landscape of robust and nonconvex formulations of low-rank matrix factorization, and to design provably,-optimal algorithmsthat, at the same time, are implementable in meaningful scales.Keywords: Nonconvex optimization, nonsmooth optimi,zation, low-rank matrix factorization.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Mar 05, 2022
- Source ID
- N000142212127
Entities
People
- Salar Fattahi
Organizations
- Board of Regents of the University of Michigan
- Office of Naval Research
- United States Navy