Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution
From MaRDI portal
Publication:2189396
DOI10.1007/s10208-019-09429-9zbMath1445.90089arXiv1711.10467WikidataQ127406705 ScholiaQ127406705MaRDI QIDQ2189396
Yuejie Chi, Yuxin Chen, Cong Ma, Kaizheng Wang
Publication date: 15 June 2020
Published in: Foundations of Computational Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1711.10467
matrix completion; nonconvex optimization; blind deconvolution; gradient descent; phase retrieval; leave-one-out analysis
90C26: Nonconvex programming, global optimization
Related Items
Unnamed Item, Unnamed Item, Unnamed Item, First-Order Methods for Nonconvex Quadratic Minimization, An Equivalence between Critical Points for Rank Constraints Versus Low-Rank Factorizations, Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization, Exact Recovery of Multichannel Sparse Blind Deconvolution via Gradient Descent, Estimation from nonlinear observations via convex programming with application to bilinear regression, Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees, Bridging convex and nonconvex optimization in robust PCA: noise, outliers and missing data, Matrix completion with nonconvex regularization: spectral operators and scalable algorithms, Entrywise eigenvector analysis of random matrices with low expected rank, Smoothed amplitude flow-based phase retrieval algorithm, Normal approximation and confidence region of singular subspaces, Spectral method and regularized MLE are both optimal for top-\(K\) ranking, Gradient descent with random initialization: fast global convergence for nonconvex phase retrieval, Asymmetry helps: eigenvalue and eigenvector analyses of asymmetrically perturbed low-rank matrices, Robust recovery of low-rank matrices with non-orthogonal sparse decomposition from incomplete measurements, Median-Truncated Gradient Descent: A Robust and Scalable Nonconvex Approach for Signal Estimation
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Matrix Completion and Low-Rank SVD via Fast Alternating Least Squares
- Optimal rates of convergence for noisy sparse phase retrieval via thresholded Wirtinger flow
- Solving quadratic equations via phaselift when there are about as many equations as unknowns
- Oracle inequalities in empirical risk minimization and sparse recovery problems. École d'Été de Probabilités de Saint-Flour XXXVIII-2008.
- Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion
- An elementary proof of convex phase retrieval in the natural parameter space via the linear program PhaseMax
- A tail inequality for quadratic forms of subgaussian random vectors
- Hanson-Wright inequality and sub-Gaussian concentration
- Estimating the matrix \(p\)-norm
- Low rank matrix completion by alternating steepest descent methods
- The spectral norm of a nonnegative matrix
- Perturbation bounds for matrix square roots and Pythagorean sums
- Orthogonal Procrustes rotation for two or more matrices
- A note on \(\sin\Theta\) theorems for singular subspace variations
- Phase retrieval with one or two diffraction patterns by alternating projections with the null initialization
- A flexible convex relaxation for phase retrieval
- Debiasing the Lasso: optimal sample size for Gaussian designs
- The landscape of empirical risk for nonconvex losses
- Fast rank-one alternating minimization algorithm for phase retrieval
- The likelihood ratio test in high-dimensional logistic regression is asymptotically a rescaled Chi-square
- Spectral method and regularized MLE are both optimal for top-\(K\) ranking
- Rapid, robust, and reliable blind deconvolution via nonconvex optimization
- ROP: matrix recovery via rank-one projections
- The local convexity of solving systems of quadratic equations
- Fundamental limits of weak recovery with applications to phase retrieval
- Gradient descent with random initialization: fast global convergence for nonconvex phase retrieval
- Exact matrix completion via convex optimization
- Convex Recovery of a Structured Signal from Independent Random Linear Measurements
- Guarantees of Riemannian Optimization for Low Rank Matrix Recovery
- On robust regression with high-dimensional predictors
- Guaranteed Matrix Completion via Non-Convex Factorization
- Exact and Stable Covariance Estimation From Quadratic Sampling via Convex Programming
- Incoherence-Optimal Matrix Completion
- Phase Retrieval via Wirtinger Flow: Theory and Algorithms
- Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems
- Blind Deconvolution Using Convex Programming
- Blind Recovery of Sparse Signals From Subsampled Convolution
- Complete Dictionary Recovery Over the Sphere I: Overview and the Geometric Picture
- Robust principal component analysis?
- Rank-Sparsity Incoherence for Matrix Decomposition
- Self-calibration and biconvex compressive sensing
- Solving systems of phaseless equations via Kaczmarz methods: a proof of concept study
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
- Non-Convex Phase Retrieval From STFT Measurements
- Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow
- PhaseMax: Convex Phase Retrieval via Basis Pursuit
- GESPAR: Efficient Phase Retrieval of Sparse Signals
- Compressive Phase Retrieval via Generalized Approximate Message Passing
- Phase Retrieval Using Alternating Minimization
- The Projected Power Method: An Efficient Algorithm for Joint Alignment from Pairwise Differences
- Theoretical Insights Into the Optimization Landscape of Over-Parameterized Shallow Neural Networks
- Sparse Phase Retrieval via Truncated Amplitude Flow
- A Well-Tempered Landscape for Non-convex Robust Subspace Recovery
- Near-Optimal Bounds for Phase Synchronization
- Fast and Guaranteed Blind Multichannel Deconvolution Under a Bilinear System Model
- 10.1162/153244302760200704
- Inference and uncertainty quantification for noisy matrix completion
- Structured Signal Recovery From Quadratic Measurements: Breaking Sample Complexity Barriers via Nonconvex Optimization
- Symmetry, Saddle Points, and Global Optimization Landscape of Nonconvex Matrix Factorization
- Blind Deconvolution by a Steepest Descent Algorithm on a Quotient Manifold
- Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
- Fast, robust and non-convex subspace recovery
- Regularized gradient descent: a non-convex recipe for fast joint blind deconvolution and demixing
- Phase retrieval via randomized Kaczmarz: theoretical guarantees
- A useful variant of the Davis–Kahan theorem for statisticians
- A Probabilistic and RIPless Theory of Compressed Sensing
- Recovering Low-Rank Matrices From Few Coefficients in Any Basis
- ADMiRA: Atomic Decomposition for Minimum Rank Approximation
- Matrix Completion From a Few Entries
- The Power of Convex Relaxation: Near-Optimal Matrix Completion
- Perturbation Bounds for the Polar Decomposition
- A Simpler Approach to Matrix Completion
- Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
- Low-rank matrix completion using alternating minimization
- An Introduction to Matrix Concentration Inequalities
- The Rotation of Eigenvectors by a Perturbation. III
- Perturbation bounds in connection with singular value decomposition
- Concentration and Moment Inequalities for Polynomials of Independent Random Variables
- Phase Retrieval via Matrix Completion
