Abstract
Modern machine learning models often exhibit "implicit regularization," converging to simple, low-dimensional solutions despite being heavily over-parameterized. This paper introduces Infinitesimally Perturbed Gradient Descent (IPGD), proving that microscopic noise—even as small as floating-point round-off errors—is sufficient to escape saddle points while keeping the model's trajectory locked within a low-dimensional "implicit region." We provide a unified theoretical framework and demonstrate near-linear convergence for over-parameterized matrix sensing and completion tasks.
Introduction
In contemporary deep learning, models are frequently designed with far more parameters than necessary to represent the training data. Theoretically, such over-parameterization should lead to complex overfitting; however, in practice, Gradient Descent (GD) often finds "simple" solutions, such as sparse vectors or low-rank matrices. This phenomenon, known as implicit regularization, is critical for generalization but remains poorly understood.
A primary challenge in non-convex optimization is avoiding "saddle points" — flat regions that are not local minima. While adding random noise to gradients is a common strategy to escape these points, large perturbations can push the model out of the "good" low-dimensional region, degrading statistical performance. This paper addresses the fundamental trade-off: how can an algorithm escape bad stationary points without losing the simplicity that ensures generalization?
Methodology: IPGD and IPGD+
The authors propose Infinitesimally Perturbed Gradient Descent (IPGD) and its accelerated variant, IPGD+. The framework is built upon three core pillars:
- Signal-Residual Decomposition: The model parameters ($x$) are decomposed into a "signal" component ($x^\sharp$) on the target low-dimensional manifold and a "residual" component ($x^\perp$) representing the deviation.
- Infinitesimal Perturbations: IPGD utilizes a perturbation radius ($\gamma$) that can be arbitrarily small. The authors prove that the "stuck region" around a saddle point is sufficiently narrow that even microscopic noise (e.g., $10^{-15}$) can push the iterate toward a descent direction.
- Deviation Rate: A new metric, the "deviation rate" ($r(x)$), acts as a mathematical "gravity" that determines if the optimization process naturally pulls the iterate back toward the low-dimensional manifold.
IPGD+ further enhances this by adding a local improvement step: it uses IPGD to navigate the neighborhood of a solution and then switches to vanilla GD to achieve rapid, linear convergence.
Experimental Validation
The theoretical findings were validated using several synthetic benchmarks common in high-dimensional statistics:
- Matrix Sensing: Recovering low-rank matrices from linear measurements.
- Matrix Completion: Filling missing entries in symmetric, asymmetric, and 1-bit matrices.
- Sparse Recovery: Identifying sparse signals from observations.
These experiments demonstrate that IPGD/IPGD+ can recover diverse structures without prior knowledge of the specific rank or sparsity level.
Key Insights and Results
The most striking finding is that the perturbation radius $\gamma$ only affects the convergence rate logarithmically. This implies that the inherent noise from double-precision floating-point arithmetic is often sufficient to act as the infinitesimal perturbation required for convergence.
Key results include:
- Unified Theory: The first unified framework for implicit regularization in over-parameterized matrix sensing under the Restricted Isometry Property (RIP).
- Near-Linear Convergence: IPGD+ reaches an $\epsilon$-accurate solution in $O(\text{polylog}(1/\epsilon))$ iterations, significantly faster than typical non-convex rates.
- Empirical Success: Simulations show IPGD+ consistently converges to ground truth with residual errors as low as $10^{-15}$, matching the perturbation radius and confirming that the model stays near the low-dimensional manifold.
Limitations and Future Directions
While providing a robust framework, the current theory requires the objective function to be smooth (Lipschitz gradients and Hessians). This currently excludes models with non-smooth components like ReLU activations. Additionally, extending these insights to Stochastic Gradient Descent (SGD), where noise is inherent but non-isotropic, remains a significant open question. Future work will also need to address the complexities of escaping saddle points in non-smooth landscapes.
Summary updated