For decades, optimization theory relied on a convenient safety rail: the assumption of globally bounded gradients. In mathematical proofs, assuming that the norm of a gradient never exceeds a fixed constant ($\|\nabla f(x)\| \le G$) makes it straightforward to guarantee that an algorithm won't diverge. If the steps are bounded, the trajectory is manageable.
However, this theoretical convenience creates a severe mismatch with reality. Consider a simple quadratic function like $f(x) = x^2$. As $x$ moves toward infinity, the gradient grows indefinitely. In fact, as noted by Ahmed Khaled et al. in Tighter Theory for Local SGD on Identical and Heterogeneous Data and Nhuong V. Nguyen et al. in Hogwild! over Distributed Local Data Sets with Linearly Increasing Mini-Batch Sizes, the bounded gradient assumption is fundamentally incompatible with strong convexity over unconstrained domains. For modern deep learning architectures, the loss landscapes are highly non-convex and prone to exploding gradients, rendering global bounds useless (Bohan Wang et al., Convergence of AdaGrad for Non-convex Objectives: Simple Proofs and Relaxed Assumptions).
To bridge this gap, a major wave of optimization research has focused on proving convergence under relaxed assumptions where gradients can grow arbitrarily large. The core intuition behind these breakthroughs lies in three main mechanisms: adaptive step sizes, self-bounding properties, and explicit decoupling.
How Adaptive Steps Tame Gradient Explosions
If a gradient becomes massive, a standard gradient descent step will catapult the model parameters into instability. Adaptive optimizers solve this by dynamically shrinking the step size when gradients surge.
Take AdaGrad as an example. It scales updates inversely with the square root of the historical sum of squared gradients. Amit Attia et al. show in SGD with AdaGrad Stepsizes: Full Adaptivity with High Probability to Unknown Parameters, Unbounded Gradients and Affine Variance that this mechanism provides automatic robustness. When the algorithm encounters a steep, unbounded region, the denominator grows instantly, dampening the update and keeping the iterates stable without needing prior knowledge of the landscape's smoothness.
A similar principle applies to Adam, the workhorse of deep learning. For years, proving Adam's optimal convergence rate required artificial gradient bounds. Recently, Bohan Wang et al. (Closing the gap between the upper bound and lower bound of Adam's iteration complexity) and Ruinan Jin et al. (A Comprehensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD) dismantled this requirement. The authors demonstrated that Adam's coordinate-wise scaling naturally handles arbitrary gradient growth, achieving optimal iteration complexity under standard smoothness and variance bounds alone.
Decoupling and Self-Bounding Mechanisms
When we move away from adaptive methods, how do simpler algorithms survive unbounded landscapes?
One approach is explicit decoupling. In the classic subgradient method, the step length is directly tied to the subgradient's magnitude. If the subgradient explodes, the step explodes. Xiao Li et al. demonstrate in Revisiting Subgradient Method: Complexity and Convergence Beyond Lipschitz Continuity that by using a normalized step-size rule ($\nabla f(x) / \|\nabla f(x)\|$), the direction of the update is preserved while its disruptive magnitude is entirely neutralized. This allows the algorithm to navigate non-Lipschitz, infinitely steep convex functions efficiently.
Another approach relies on the self-bounding nature of smooth functions. For many realistic objectives, the magnitude of the gradient is bounded by the function value itself (meaning gradients only get large when the loss is large). As proven by Yunwen Lei et al. in Stochastic Gradient Descent for Nonconvex Learning without Bounded Gradient Assumptions, standard SGD naturally converges in these environments because the algorithm makes enough early progress to prevent the iterates from drifting into regions with catastrophic gradient growth. Similarly, Kun Yuan et al. (On the Convergence of Decentralized Gradient Descent) show that a properly bounded step size is mathematically sufficient to keep local function values bounded, rendering global gradient constraints unnecessary.
Stability in Unconstrained Spaces
Beyond standard minimization, optimization often occurs in unconstrained spaces where even the algorithm's iterates might grow indefinitely. Traditional proofs frequently rely on projecting iterates back onto a compact, bounded set to maintain stability.
To bypass this, Xiao Li et al. developed a unified framework in A Unified Convergence Theorem for Stochastic Optimization Methods, proving that stochastic methods can reach stationary points with probability 1 without assuming bounded regions, provided the algorithm makes consistent relative progress.
In saddle-point or min-max optimization (common in GANs and reinforcement learning), unbounded domains can cause gradients to explode due to the coupling between competing variables. Gergely Neu et al. solved this in Dealing With Unbounded Gradients in Stochastic Saddle-point Optimization by introducing a stabilization term that anchors iterates to their starting point, ensuring convergence based on initialization quality rather than an artificial bounding radius.
Scaling to Distributed and Bilevel Systems
The removal of the bounded gradient assumption has unlocked rigorous theoretical foundations for highly complex, modern distributed architectures.
- Decentralized Networks: In peer-to-peer optimization, agents must reach a consensus over time-varying networks. Early theories required bounded gradients to ensure agents didn't drift apart during communication gaps. Ying Sun et al. (Distributed Nonconvex Constrained Optimization over Time-Varying Digraphs) and Ying Sun et al. (Distributed Nonconvex Optimization for Sparse Representation) overcame this by designing Lyapunov-like functions that track and stabilize gradient trajectories across directed graphs. For communication-efficient deep learning, Xiaorui Liu et al. (A Double Residual Compression Algorithm for Efficient Distributed Learning) demonstrated that error-compensated compression algorithms maintain linear convergence speedups even when gradient magnitudes fluctuate wildly.
- Bilevel Optimization: In nested optimization (such as meta-learning), the outer objective depends implicitly on the inner problem's solution, making gradients highly volatile. Kaiyi Ji et al. (Lower Bounds and Accelerated Algorithms for Bilevel Optimization) established accelerated algorithms that eliminate outer-level gradient bounds entirely. To handle the extreme "unbounded smoothness" typical of recurrent networks, Jie Hao et al. (Bilevel Optimization under Unbounded Smoothness: A New Algorithm and Convergence Analysis) introduced a framework combining normalized momentum with periodic lower-level updates, proving that robustness to exploding gradients does not require sacrificing optimal convergence rates.
By shifting the analytical focus from rigid global bounds to dynamic properties—like adaptive scaling, normalization, and self-bounding structures—modern optimization theory now rigorously explains why algorithms succeed on the steep, unpredictable landscapes of real-world machine learning.
Key Foundational Work
Distributed Nonconvex Constrained Optimization over Time-Varying Digraphs (2018) — contributed 2 concept elements to this direction.
On the Convergence of Decentralized Gradient Descent (2016) — contributed 1 concept elements to this direction.
Fast incremental method for smooth nonconvex optimization (2016) — contributed 1 concept elements to this direction.