skip to main content
Language:
Search Limited to: Search Limited to: Resource type Show Results with: Show Results with: Search type Index

Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution

Foundations of computational mathematics, 2020-06, Vol.20 (3), p.451-632 [Peer Reviewed Journal]

The Author(s) 2019 ;ISSN: 1615-3375 ;EISSN: 1615-3383 ;DOI: 10.1007/s10208-019-09429-9

Digital Resources/Online E-Resources

Citations Cited by
  • Title:
    Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
  • Author: Ma, Cong ; Wang, Kaizheng ; Chi, Yuejie ; Chen, Yuxin
  • Subjects: Applications of Mathematics ; Computer Science ; Economics ; Linear and Multilinear Algebras ; Math Applications in Computer Science ; Mathematics ; Mathematics and Statistics ; Matrix Theory ; Numerical Analysis
  • Is Part Of: Foundations of computational mathematics, 2020-06, Vol.20 (3), p.451-632
  • Description: Recent years have seen a flurry of activities in designing provably efficient nonconvex procedures for solving statistical estimation problems. Due to the highly nonconvex nature of the empirical loss, state-of-the-art procedures often require proper regularization (e.g., trimming, regularized cost, projection) in order to guarantee fast convergence. For vanilla procedures such as gradient descent, however, prior theory either recommends highly conservative learning rates to avoid overshooting, or completely lacks performance guarantees. This paper uncovers a striking phenomenon in nonconvex optimization: even in the absence of explicit regularization, gradient descent enforces proper regularization implicitly under various statistical models. In fact, gradient descent follows a trajectory staying within a basin that enjoys nice geometry, consisting of points incoherent with the sampling mechanism. This “implicit regularization” feature allows gradient descent to proceed in a far more aggressive fashion without overshooting, which in turn results in substantial computational savings. Focusing on three fundamental statistical estimation problems, i.e., phase retrieval, low-rank matrix completion, and blind deconvolution, we establish that gradient descent achieves near-optimal statistical and computational guarantees without explicit regularization. In particular, by marrying statistical modeling with generic optimization theory, we develop a general recipe for analyzing the trajectories of iterative algorithms via a leave-one-out perturbation argument. As a by-product, for noisy matrix completion, we demonstrate that gradient descent achieves near-optimal error control—measured entrywise and by the spectral norm—which might be of independent interest.
  • Publisher: New York: Springer US
  • Language: English
  • Identifier: ISSN: 1615-3375
    EISSN: 1615-3383
    DOI: 10.1007/s10208-019-09429-9
  • Source: SpringerOpen
Back to results list
INSPIRE LIBRARY - TON DUC THANG UNIVERSITY (84-028) 37 755 057 Feedback
19 Nguyen Huu Tho St. Dist.7, HCM thuvien@tdtu.edu.vn

Copyright © 2017 INSPIRE LIBRARY - TON DUC THANG UNIVERSITY

Searching Remote Databases, Please Wait