Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview

By Yuejie Chi, Yue M. Lu, Yuxin Chen. 2018

491 citations recorded by the source corpus.

Substantial progress has been made recently on developing provably accurate and efficient algorithms for low-rank matrix factorization via nonconvex optimization. While conventional wisdom often takes a dim view of nonconvex optimization algorithms due to their susceptibility to spurious local minima, simple iterative methods such as gradient descent have been remarkably successful in practice. The theoretical footings, however, had been largely lacking until recently. In this tutorial-style overview, we highlight the important role of statistical models in enabling efficient nonconvex optimization with performance guarantees. We review two contrasting approaches: (1) two-stage algorithms, which consist of a tailored initialization step followed by successive refinement; and (2) global landscape analysis and initialization-free algorithms. Several canonical matrix factorization problems are discussed, including but not limited to matrix sensing, phase retrieval, matrix completion, blind deconvolution, and robust principal component analysis. Special care is taken to illustrate the key technical insights underlying their analyses. This article serves as a testament that the integrated consideration of optimization and statistics leads to fruitful research findings.

Subfields: Computational Mechanics, Computational Theory and Mathematics, Numerical Analysis, Representation & Self-Supervised Learning, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computational Theory and Mathematics

In Numerical Analysis

In Representation & Self-Supervised Learning

In Optimization & Training

Citations in the corpus

Initialization and Regularization of Factorized Neural Layers (2021, background): “Outside deep learning, spectral methods have also been shown to yield better initializations for certain matrix and tensor problems (Keshavan et al., 2010; Chi et al., 2019; Cai et al., 2019).”
Continual learning: a feature extraction formalization, an efficient algorithm, and fundamental obstructions (2022, background): “spectral initialization [7]) or adding a regularization term that enforces smoothness [12], none of which are applicable in our setting.”
Exploiting Shared Representations for Personalized Federated Learning (2021, background): “Incoherence of the ground-truth matrices is a key property required for efficient matrix completion and other sensing problems with sparse measurements (Chi et al., 2019).”
A modern maximum-likelihood theory for high-dimensional logistic regression (2018, background): “The leave-one-out techniques introduced in high-dimensional statistics by [42,43] have deep roots in probability, random matrix theory and statistical physics, and have found several applications over the years (see for instance, [25] and the references cited therein).”
Implicit Regularization in Deep Learning May Not Be Explainable by Norms (2020, background): “[13] Yuejie Chi, Yue M Lu, and Yuxin Chen.”
Trained Transformers Learn Linear Models In-Context (2023, background): “We also note that this quadratic optimization problem is an instance of a rank-one matrix factorization problem, a problem well-studied in the deep learning theory literature [Gun+17; Aro+19; LMZ18; CLC19; Bel20; LLL20; Jin+23; SSX23].”
Implicit Regularization in Deep Matrix Factorization (2019, background): “The literature on matrix factorization for low-rank matrix recovery is far too broad to cover here — we refer to [10] for a recent survey, while mentioning that the technique is oftentimes attributed to [8].”
Edge Artificial Intelligence for 6G: Vision, Enabling Technologies, and Applications (2021, background): “, blind demixing [189], phase retrieval [254], and shallow neural networks [255].”
On critical points of quadratic low-rank matrix optimization problems (2020, background): “, 2016), which are much less costly per iteration; see also Chi et al. (2019) for a recent overview.”