In classical learning theory, there is a troubling disconnect between how we analyze algorithms and how they actually behave. If you look at standard theoretical bounds for iterative optimization, the predicted generalization error often scales with the square root of the number of training steps, $O(\sqrt{T})$. This suggests that if you train a model for too long, its performance on unseen data should eventually collapse into chaos.
Yet, in modern deep learning, we routinely train models for thousands or even millions of iterations—long after the training loss has hit a plateau—and they continue to generalize well. This "time-complexity paradox" suggests that our theoretical tools are missing a fundamental property of stochastic optimization.
A growing body of research is resolving this by establishing time-uniform (or time-independent) generalization bounds. These proofs show that for noisy versions of Stochastic Gradient Descent (SGD), the gap between training and test performance does not explode, but rather saturates at a stable, manageable level.
The Stability Decay Problem
To understand why time-independent bounds are difficult to achieve, we have to look at algorithmic stability. An algorithm is stable if changing a single data point in the training set doesn't drastically change the final model. If an algorithm is stable, it is guaranteed to generalize.
The problem is that in non-convex landscapes, small differences in the training data can lead the optimization trajectory down entirely different valleys. As Tao Sun and Dongsheng Li note in their work on decentralized SGD, stability bounds often grow polynomially or even exponentially with time. This makes the resulting generalization guarantees "vacuous"—they provide no meaningful information for long-running processes.
Noise as a Stabilizing Force
The key to stopping this "error explosion" is the introduction of noise. While practitioners often view noise as something to be minimized, researchers like Jung Eun Huh have shown that specific types of noise, such as label noise, can actually lead to faster generalization rates ($O(n^{-2/3})$) than standard methods (Generalization Bounds for Label Noise Stochastic Gradient Descent).
The intuition is that noise prevents the model from "memorizing" the specific quirks of the training set. In Stochastic Gradient Langevin Dynamics (SGLD), where Gaussian noise is added to the gradients, the optimization process behaves like a physical system reaching thermal equilibrium.
Patrick Rebeschini and Tyler Farghly demonstrated that SGLD exhibits a property called Wasserstein contraction (Time-independent Generalization Bounds for SGLD in Non-convex Settings). Essentially, the noise causes the optimization trajectories to "forget" their initial conditions and converge toward a stable stationary distribution. Once the algorithm reaches this steady state, the generalization error stops growing, regardless of how much longer you train.
Bridging Discrete Steps and Continuous Flow
Proving these bounds for discrete-time algorithms is mathematically grueling. To simplify the analysis, researchers often use Poissonization—a technique that treats discrete optimization steps as a continuous-time Markov process.
Benjamin Dupuis, Umut Şimşekli, and their colleagues have used this approach to derive "entropy flow" formulas (Understanding the Generalization Error of Markov algorithms through Poissonization). By viewing the algorithm as a flow of information, they can link the speed at which an algorithm converges to its ability to generalize.
This framework has even been extended to heavy-tailed noise, which is common in large-batch SGD. In Generalization Bounds for Heavy-Tailed SDEs, Dupuis and Simsekli discovered a "phase transition": depending on the relationship between the noise scale and the model's dimensions, heavy-tailed noise can either drastically improve generalization or cause it to fail entirely.
Why It Works: The Terminal State
The shift in perspective offered by this research direction is profound. Instead of viewing generalization as a fragile state that is lost over time, researchers like Ziqiao Wang and Yongyi Mao suggest we should view it through the lens of terminal states (Two Facets of SDE Under an Information-Theoretic Lens).
When an optimization algorithm is sufficiently noisy and dissipative, it doesn't just wander aimlessly; it settles into a distribution that is inherently tied to the data. Lingjiong Zhu and Mert Gurbuzbalaban established that this stability is "uniform-in-time," meaning the gap between training and test performance remains bounded even as $T \to \infty$ (Uniform-in-Time Wasserstein Stability Bounds).
By proving that generalization error saturates rather than diverges, these researchers have provided the theoretical justification for the "long training" regimes that define modern machine learning. We now know that as long as there is sufficient noise to regularize the trajectory, the clock is not our enemy.