In classical optimization theory, there is a sharp divide between "slow" and "fast" algorithms. If a function is merely convex, first-order methods like Gradient Descent typically converge at a sublinear rate ($O(1/t)$). To achieve the "gold standard" of linear convergence—where the error drops exponentially—textbooks usually require the objective to be strongly convex.
However, practitioners have long observed that many important problems, such as LASSO, logistic regression, and even deep linear networks, converge much faster than sublinear theory predicts, despite lacking global strong convexity. A growing body of research shows that these problems satisfy a more general geometric property known as an Error Bound Condition (EBC). This condition acts as a theoretical bridge, allowing algorithms to automatically adapt to the local geometry of the loss landscape and achieve high-speed convergence.
The Geometry of Growth
The intuition behind an error bound is simple: it relates how much the objective function "grows" as you move away from the optimal set to the physical distance from that set.
In a strongly convex function, the surface curves upward like a bowl; if you are far from the bottom, the function value is significantly higher. An error bound generalizes this. As Tianbao Yang and Qihang Lin describe in A Richer Theory of Convex Constrained Optimization with Reduced Projections and Improved Rates, a local error bound ensures that the distance to the optimal set is bounded by a multiple of a "computable residual"—usually the gradient or a proximal step.
Mathematically, this is often expressed as a Hölderian Error Bound (HEB). If the objective $f(x)$ satisfies an HEB with exponent $\theta$, the distance to the optimal set $X^*$ is bounded by $(f(x) - f^* )^\theta$. When $\theta = 1/2$, we recover a property similar to strong convexity (quadratic growth), leading to linear convergence. When $\theta > 1/2$, the convergence is faster than $O(1/t)$ but slower than linear, creating a continuous spectrum of convergence rates Fast Rates of ERM and Stochastic Approximation: Adaptive to Error Bound Conditions.
Automatic Adaptation in First-Order Methods
One of the most powerful aspects of error bounds is that many algorithms are automatically adaptive to them. They don't need to know the specific growth constant to speed up.
Frank-Wolfe and Polytopes
The Frank-Wolfe (FW) algorithm is often limited by a slow $O(1/t)$ rate. However, Tianbao Yang proved in Frank-Wolfe Method is Automatically Adaptive to Error Bound Condition that when minimizing over a strongly convex set, FW naturally accelerates to $O(1/t^2)$ or even linear rates by exploiting the underlying error bound. Similarly, Elias Samuel Wirth and Sebastian Pokutta have shown that FW variants on polytopes follow a continuous spectrum of convergence determined by the degree of the error bound Fast convergence of Frank-Wolfe algorithms on polytopes.
ADMM and Proximal Methods
The Alternating Direction Method of Multipliers (ADMM) is a staple for constrained problems like LASSO. In a seminal work, Zhi-Quan Luo established that ADMM converges linearly on many non-strongly convex problems by satisfying a proximal error bound On the Linear Convergence of the Alternating Direction Method of Multipliers. This explains why ADMM remains efficient for high-dimensional models where the objective function is "flat" in many directions.
Beyond First-Order: Newton and Bilevel Optimization
The utility of error bounds extends to second-order methods and complex hierarchical problems.
- Proximal Newton: Man-Chung Yue, Anthony Man-Cho So, and Zirui Zhou developed the Inexact Regularized Proximal Newton (IRPN) method. By leveraging the Luo-Tseng Error Bound, they proved that second-order methods can achieve superlinear or quadratic convergence even on degenerate problems with singular Hessians Inexact Regularized Proximal Newton Method: Provable Convergence Guarantees for Non-Smooth Convex Minimization without Strong Convexity.
- Bilevel Optimization: In problems where one optimization is nested inside another, Jeongyeol Kwon and Stephen Wright use proximal error bounds as a regularity assumption to handle nonconvex landscapes where standard conditions like Polyak-Łojasiewicz are too restrictive On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximation.
Sharpness in Machine Learning
In the context of learning single neurons or deep networks, error bounds often appear under the guise of sharpness. Puqian Wang and Jelena Diakonikolas demonstrate that "sharpness" (a local error bound) allows simple mini-batch SGD to learn neurons robustly even with adversarial noise Robustly Learning a Single Neuron via Sharpness.
For deep linear networks, Pisin Chen and colleagues have shown that the loss landscape satisfies an error bound condition that guarantees gradient descent will not stall in regions with small gradients, ensuring a linear path to a critical point Error Bound Analysis for the Regularized Loss of Deep Linear Neural Networks.
Summary
The shift from global strong convexity to local error bound conditions represents a move toward a more realistic and granular understanding of optimization. By focusing on the relationship between suboptimality and distance to the solution set, researchers have provided a unified framework that explains the empirical success of first-order methods, justifies the use of second-order methods on degenerate data, and enables the solving of complex bilevel and neural network problems.