Implicit Regularization of Gradient Descent in Realistic Settings

Abstract

Gradient descent (GD) is the backbone of modern machine learning optimization, and its success is often attributed not just to efficiency but also to an intriguing phenomenon known as implicit regularization—the tendency of GD to favor solutions that generalize well, even without explicit constraints. While existing theoretical studies have shed light on this behavior, they frequently rely on idealized assumptions, such as isotropic data distributions or benign optimization landscapes, which rarely hold in practice. This gap highlights the need to understand implicit regularization in more realistic and challenging settings that better reflect practical machine learning problems.

This dissertation explores implicit regularization in gradient-based learning under three key challenges: (1) robustness to heavy-tailed outlier noise, (2) learning with non-isotropic input distributions, and (3) developing a general theoretical framework for characterizing optimization trajectories. First, we study robust learning with $ell_1$-loss, including robust matrix sensing and robust deep linear networks, and show that GD implicitly preserves low-rank structures throughout training, achieving near-linear convergence under near-optimal sample complexity. Interestingly, we prove that the ground truth corresponds to a strict saddle point, countering the conventional wisdom that saddle points inherently impede optimization. Second, we analyze learning with non-isotropic input distributions—a broad category that includes unregularized matrix completion as a special case. We introduce a novel statistical decoupling technique that establishes near-optimal sample complexity guarantees for GD without relying on standard isotropic assumptions. Lastly, we develop a unified framework based on structured basis function decomposition, revealing that GD trajectories, when projected onto a suitable function basis, exhibit an almost monotonic progression despite their apparent complexity.

Altogether, this work advances the theoretical understanding of implicit regularization under realistic conditions, offering rigorous insights into how gradient descent selects generalizable solutions. These results have broad implications for designing robust and efficient learning algorithms across diverse machine learning tasks.