Algorithmic Regularization in Model-Free Overparametrized Asymmetric Matrix Factorization

DOI10.1137/22M1519833MaRDI QIDQ6136234zbMATH OpenOpenAlexFDO

Authors Liwei Jiang, Yudong Chen, Lijun Ding

Publication date 29 August 2023

Published in SIAM Journal on Mathematics of Data Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2203.02839

zbMATH Keywords

asymmetric matrix factorizationgradient descentmodel-freeoverparametrizationsmall initialization

Mathematics Subject Classification ID

General topics in artificial intelligence (68T01) Applications of mathematical programming (90C90)

Abstract: We study the asymmetric matrix factorization problem under a natural nonconvex formulation with arbitrary overparametrization. The model-free setting is considered, with minimal assumption on the rank or singular values of the observed matrix, where the global optima provably overfit. We show that vanilla gradient descent with small random initialization sequentially recovers the principal components of the observed matrix. Consequently, when equipped with proper early stopping, gradient descent produces the best low-rank approximation of the observed matrix without explicit regularization. We provide a sharp characterization of the relationship between the approximation error, iteration complexity, initialization size and stepsize. Our complexity bound is almost dimension-free and depends logarithmically on the approximation error, with significantly more lenient requirements on the stepsize and initialization compared to prior work. Our theoretical results provide accurate prediction for the behavior gradient descent, showing good agreement with numerical experiments.

Recommendations

• Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution
• Gradient descent for deep matrix factorization: dynamics and implicit bias towards low rank
• Finding low-rank solutions via nonconvex matrix factorization, efficiently and provably
• Provable accelerated gradient method for nonconvex low rank optimization
• Nonconvex Low-Rank Tensor Completion from Noisy Data

Cites work

• Algorithmic Regularization in Model-Free Overparametrized Asymmetric Matrix Factorization
• Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensing
• Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
• Matrix estimation by universal singular value thresholding
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• When do neural networks outperform kernel methods?*

Cited in

(7)

• Algorithmic Regularization in Model-Free Overparametrized Asymmetric Matrix Factorization
• Understanding Implicit Regularization in Over-Parameterized Single Index Model
• Gradient descent for deep matrix factorization: dynamics and implicit bias towards low rank
• Theoretical guarantees for low-rank compression of deep neural networks
• Sharp global guarantees for nonconvex low-rank recovery in the noisy overparameterized regime
• Tensor-on-tensor regression: Riemannian optimization, over-parameterization, statistical-computational gap and their interplay
• The power of preconditioning in overparameterized low-rank matrix sensing

This page was built for publication: Algorithmic Regularization in Model-Free Overparametrized Asymmetric Matrix Factorization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6136234)