Implicit Regularization in Nonconvex Statistical Estimation by Leave-One-Out Trajectory Analysis

A general nonconvex optimization and statistical estimation analysis framework (introduced by Cong Ma, Kaizheng Wang, Yuejie Chi, and Yuxin Chen in 2020) proving that vanilla unregularized gradient descent $\boldsymbol{x}^{t+1} = \boldsymbol{x}^t - \eta_t\nabla f(\boldsymbol{x}^t)$ following spectral initialization automatically stays within a *Region of Incoherence and Contraction* (RIC) without requiring explicit projection, gradient clipping/trimming, or incoherence-enforcing regularization penalties. Theorem 5 formulates the general leave-one-out trajectory perturbation recipe: for each sample or row/column index $l$, an auxiliary leave-one-out loss $f^{(l)}(\boldsymbol{x})$ drops the randomness associated with $l$, producing a leave-one-out gradient trajectory $\boldsymbol{x}^{t,(l)}$ that is statistically independent of the $l$-th measurement while remaining $\|\boldsymbol{x}^t - \boldsymbol{x}^{t,(l)}\|_2$-close to the full trajectory $\boldsymbol{x}^t$. By inductively coupling $\ell_2$ restricted strong convexity contraction with leave-one-out proximity, the framework proves linear convergence and entrywise/incoherence control for (1) nonconvex phase retrieval $f(\boldsymbol{x}) = \frac{1}{4m}\sum_{j=1}^m (|\boldsymbol{a}_j^*\boldsymbol{x}|^2 - y_j)^2$ under $m \gtrsim n\log n$ maintaining $\max_l |\boldsymbol{a}_l^*(\boldsymbol{x}^t - \boldsymbol{x}^\star)| \lesssim \sqrt{\log m}\|\boldsymbol{x}^\star\|_2$ (Theorem 1); (2) noisy and noiseless low-rank matrix completion $f(\boldsymbol{X}) = \frac{1}{4p}\|\mathcal{P}_\Omega(\boldsymbol{X}\boldsymbol{X}^T - \boldsymbol{M}^\star)\|_F^2$ maintaining row-wise incoherence $\|\boldsymbol{X}^t\widehat{\boldsymbol{H}}^t - \boldsymbol{X}^\star\|_{2,\infty}$ (Theorem 2); and (3) blind deconvolution $f(\boldsymbol{h},\boldsymbol{x}) = \sum_{j=1}^m |\boldsymbol{b}_j^*\boldsymbol{h}\boldsymbol{x}^*\boldsymbol{a}_j - y_j|^2$ under $m \gtrsim \mu^2 n\text{poly}\log m$ (Theorems 3–4).