Imagine walking down a steep hill in the dark. To ensure you do not step off a hidden cliff, you must assume the slope changes gradually. In mathematical optimization, this "safety rail" is known as global Lipschitz smoothness. It guarantees that the gradient of a function changes at a bounded rate. Geometrically, it means your objective function can always be sandwiched under a fixed quadratic parabola. If a function is globally Lipschitz smooth, you can safely take a step proportional to the inverse of this bound and guarantee that the function value decreases.
However, real-world optimization landscapes rarely conform to this idealized picture. Consider a simple polynomial like $f(x) = x^4$, or the log-barrier functions used in imaging and portfolio management. As you move further from the origin or approach the boundaries of the parameter space, the gradient explodes or changes arbitrarily fast. The fixed parabola no longer fits; the safety rail collapses.
Historically, optimization algorithms were forced to assume global Lipschitz continuity to prove convergence. But a growing body of research is breaking free from this constraint, developing new theoretical frameworks and algorithmic mechanisms that allow vanilla and accelerated methods to navigate landscapes with unbounded curvature.
Why the Classical Framework Fails
To understand why the lack of Lipschitz continuity is catastrophic for standard algorithms, we must look at how step sizes are chosen. In classical gradient descent, the step size $\eta$ is a fixed constant inversely proportional to a global Lipschitz constant $L$. This ensures that the algorithm never overshoots the minimum.
When a function lacks a global Lipschitz constant, its curvature can grow infinitely. If you use a fixed step size, an update might land in a region where the gradient is vastly steeper than expected. Instead of descending, the algorithm overshoots violently, leading to oscillation or outright divergence. As noted by Jalilzadeh et al., this restriction severely limits the applicability of traditional frameworks to complex nonconvex engineering problems.
Similarly, in latent variable models, Kunstner et al. point out that the loss function can become infinitely steep near parameter boundaries, violating the global smoothness assumptions required by standard Expectation-Maximization (EM) analyses. When gradients change too rapidly to satisfy standard Lipschitz continuity, traditional gradient-based methods cannot rely on a fixed quadratic upper bound to ensure stable convergence.
Relative Smoothness and Bregman Divergences
How do we optimize a function whose curvature is unbounded? One elegant solution is to change how we measure distance. Instead of bounding our objective function with a standard quadratic parabola (which relies on standard Euclidean distance), we can bound it relative to a custom reference function $h(x)$ that mirrors the wild geometry of our objective.
This concept is known as relative smoothness. Instead of requiring the gradient to change slowly relative to the Euclidean metric, we require it to change slowly relative to the Bregman divergence of $h(x)$. The Bregman divergence acts as a localized, non-symmetric distance measure that stretches and bends along with the function itself.
Standard Smoothness: Objective(x) <= Linear_Approximation(x) + (L / 2) * ||x - y||²
Relative Smoothness: Objective(x) <= Linear_Approximation(x) + L * Bregman_Divergence(x, y)
Latafat et al. leverage this idea to develop the Bregman Finito/MISO framework, allowing finite-sum minimization without Lipschitz gradient continuity. By matching the reference function to the objective's growth, the authors construct a generalized upper bound that remains valid even when slopes change abruptly. In the dual space, Maddison et al. use dual space preconditioning to exploit relative smoothness for challenging problems like $p$-norm regression, where gradients flatten at infinity or explode near boundaries.
Self-Concordance
For a specific but highly important class of functions—such as log-barriers and logistic regression—the curvature doesn't just grow arbitrarily; it grows in a way that is intrinsically tied to the function's value or its lower-order derivatives. This is the domain of self-concordance.
A function is self-concordant if its third derivative is bounded by its second derivative (the Hessian). This means that while the Hessian can change rapidly, its rate of change is controlled by the Hessian itself.
Dvurechensky et al. adapted the Frank-Wolfe algorithm to self-concordant functions by introducing adaptive step-size rules that scale with the local Hessian geometry, providing convergence guarantees for functions with unbounded curvature like those in Poisson imaging. Furthermore, Jin et al. demonstrated that shifting the theoretical framework of the BFGS quasi-Newton method to self-concordance yields an affine-invariant global convergence analysis, freeing the algorithm from reliance on global strong convexity and Lipschitz smoothness.
Local Smoothness and Adaptive Stepsizes
When a function does not possess a global geometric structure like self-concordance, researchers often turn to local smoothness or generalized smoothness. Here, the smoothness parameter is not a single global constant $L$, but a function that depends on the magnitude or location of the current iterate.
To prevent divergence in these environments, algorithms must dynamically adjust their step sizes or modify the gradients themselves. For instance, Xian et al. showed that minimax optimization algorithms can converge under generalized smoothness if they employ adaptive step size strategies. In stochastic weakly convex optimization, where gradients can explode polynomially or exponentially as iterates move away from the origin, Gao et al. introduced robust adaptive stepsizes that prevent divergence without requiring expensive projections.
When gradients cannot be trusted or computed, gradient clipping and normalization serve as vital tools. Gorbunov et al. proved that gradient clipping provides high-probability convergence in non-smooth stochastic optimization by relying only on local smoothness around the solution rather than global smoothness. For deterministic settings, Mei developed accelerated first-order methods tailored for convex optimization with locally Lipschitz continuous gradients, utilizing verifiable termination criteria to handle functions like high-degree polynomials where the gradient grows faster as variables move further from the origin.
Broader Implications and Practical Realities
The push beyond global Lipschitz continuity is not merely a theoretical exercise; it explains why many modern empirical successes work in practice. For example, deep learning practitioners heavily rely on the Adam optimizer with its default hyperparameters, yet classical theory struggled to explain its stability without assuming well-behaved loss functions. Iiduka bridged this gap by providing a theoretical analysis of Adam without assuming Lipschitz smoothness, validating empirical configurations.
Similarly, in Differential Privacy (DP), standard privacy loss analyses for DP-SGD traditionally required global Lipschitz continuity to ensure bounded gradients. Chien et al. broke this bottleneck by proving that privacy loss converges even on the "jagged" or irregular landscapes of non-smooth functions. By relaxing these restrictive regularity conditions across machine learning, optimization theory is catching up to the complex, non-linear realities of modern data science.