Implicit Regularization of Infinitesimally-perturbed Gradient Descent Toward Low-dimensional Solutions

Jianhao Ma, Geyu Liang, Salar FattahiarXiv 2025 · DOI · arXiv

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:

  1. 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.
  2. 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.
  3. 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.
Figure 2: Geometric intuition of escaping a saddle point. The negative Hessian direction (a) provides the escape route, while the deviation direction (b) represents the risk of leaving 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.

Figure 1: Convergence behavior of standard Projected Gradient Descent (PGD). In over-parameterized settings (red), standard PGD often plateaus at a high error level, whereas exact-parameterization (blue) reaches high precision.

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

Abstract

Implicit regularization refers to the tendency of local search algorithms to converge to low-dimensional solutions, even when such structures are not explicitly enforced. Despite its ubiquity, the mechanism underlying this behavior remains poorly understood, particularly in over-parameterized settings. We analyze gradient descent dynamics and identify three conditions under which it converges to second-order stationary points within an implicit low-dimensional region: (i) suitable initialization, (ii) efficient escape from saddle points, and (iii) sustained proximity to the region. We show that these can be achieved through infinitesimal perturbations and a small deviation rate. Building on this, we introduce Infinitesimally Perturbed Gradient Descent (IPGD), which satisfies these conditions under mild assumptions. We provide theoretical guarantees for IPGD in over-parameterized matrix sensing and empirical evidence of its broader applicability.
BibTeX
@misc{ma2025implicit,
  author = {Jianhao Ma and Geyu Liang and Salar Fattahi},
  title = {{Implicit Regularization of Infinitesimally-perturbed Gradient Descent Toward Low-dimensional Solutions}},
  year = {2025},
  eprint = {2505.17304},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2505.17304},
}
Figure