Error Bounds for Fast Convergence without Strong Convexity

31 concepts20 papers1 proposal

In textbook optimization theory, ensuring that a first-order algorithm (like gradient descent) converges at a fast, geometric (linear) rate typically requires a heavy mathematical hammer: strong convexity. Geometrically, a strongly convex function is shaped like a steep bowl. The steepness guarantees that if you are far from the minimum, the gradient is large, pulling you rapidly toward the solution.

However, many foundational problems in modern machine learning and statistics—such as least squares, logistic regression, $\ell_{1,p}$-regularized models, and neural network training objectives—are not strongly convex. Their objective functions often feature flat valleys or low-slope plateaus where the gradient can become vanishingly small, even when the current iterate is far from an optimal solution. Yet, in practice, first-order methods applied to these problems still converge remarkably fast.

This gap between pessimistic classical theory and optimistic practical performance is bridged by the concept of error bounds. As established by Haibin Zhang et al. (2013) in On the Linear Convergence of a Proximal Gradient Method for a Class of Nonsmooth Convex Minimization Problems, error bounds act as a functional substitute for strong convexity. They provide a geometric guarantee that allows optimization algorithms to maintain a fast convergence rate as they approach a solution, even in the presence of nonsmooth regularizers or nonconvex landscapes.

The Geometry of an Error Bound

To understand why an error bound works, imagine you are navigating a foggy landscape trying to reach the lowest point. Let $X^*$ be the set of all optimal solutions. At your current position $x$, you want to know your distance to this optimal set, denoted as $\text{dist}(x, X^*)$.

Because you do not know where $X^*$ is, you cannot measure $\text{dist}(x, X^*)$ directly. Instead, you can only measure a local, computable residual—such as the norm of the gradient, $\|\nabla f(x)\|$.

An error bound condition asserts a direct, proportional relationship between this unobservable distance and the observable residual:

$$\text{dist}(x, X^*) \le \kappa \cdot \text{residual}(x)$$

where $\kappa > 0$ is a constant.

This simple inequality is incredibly powerful. If an algorithm takes a step proportional to the residual, and the residual bounds the remaining distance to the solution, then each iteration is guaranteed to shrink the remaining distance by a constant factor. This is the exact mechanism that triggers linear convergence.

This property is vividly illustrated in the study of deep learning dynamics. For instance, in Linear Convergence Analysis of Neural Collapse with Unconstrained Features, Peng Wang et al. (2022) prove an error bound property for over-parameterized neural networks. They demonstrate that for points near the optimal solution set, the distance to that set is bounded by the gradient norm, explaining why standard gradient descent converges linearly to highly structured "neural collapse" states.

Generalizing Residuals for Nonsmooth and Constrained Problems

When an optimization problem involves constraints or nonsmooth terms (like lasso or sparse penalties), the standard gradient norm $\|\nabla f(x)\|$ is no longer a reliable residual. If an iterate hits a constraint boundary or a sharp kink in the function, the gradient may be undefined or fail to reflect actual progress.

To handle this, researchers alter the definition of the "residual" to match the geometry of the algorithm:

The presence or absence of these error bounds explains sudden "phase transitions" in algorithm behavior. In $\ell_{1, p}$-Norm Regularization: Error Bounds and Convergence Rate Analysis of First-Order Methods, Zirui Zhou et al. (2015) analyzed first-order methods under $\ell_{1,p}$ regularization. They proved that the error bound condition holds perfectly when $p \in [1, 2]$ or $p = \infty$, yielding fast linear convergence. However, for $p \in (2, \infty)$, the error bound breaks down, explaining why algorithms suddenly slow down in that parameter regime.

From Local Growth to Global Guarantees

Error bounds can be categorized by where they hold across the optimization landscape:

Local Growth Conditions

Often, an error bound only holds within a specific neighborhood around the optimal set. Yi Xu et al. (2017) explore this in Stochastic Convex Optimization: Faster Local Growth Implies Faster Global Convergence. They show that by understanding how fast an objective function grows locally around the optimal solution, one can design accelerated stochastic subgradient methods that drastically cut down iteration complexity for non-smooth machine learning problems.

Global Error Bounds

When an error bound holds universally across the entire domain, it provides an even stronger analytical foundation. In Non-asymptotic convergence analysis of inexact gradient methods for machine learning without strong convexity, Anthony Man-Cho So et al. (2017) utilize a Hoffman-like global error bound. This structural property allows for a non-asymptotic analysis, meaning researchers can precisely track an algorithm's progress at every single iteration rather than just predicting its behavior in the limit.

Similarly, Zhi-Quan Luo et al. (2022) introduce a global dual error bound in A Global Dual Error Bound and Its Application to the Analysis of Linearly Constrained Nonconvex Optimization, leveraging it to achieve an optimal $O(1/\epsilon^2)$ iteration complexity for a challenging class of nonconvex problems.

Advanced Frontiers: Duals, Values, and Persistent Errors

The utility of error bounds extends beyond standard primal optimization space into dual formulations, value-based metrics, and non-ideal environments:

Robustness to Noise and Regularization

Error bounds also provide a mathematical safety net when algorithms operate under non-ideal conditions. In Analysis of Gradient Descent Methods With Nondiminishing Bounded Errors, Arunselvan Ramaswamy (2017) analyzes gradient descent where errors are persistent and never disappear. Instead of diverging, the algorithm is proven to remain stable and converge to a bounded neighborhood proportional to the error size, a guarantee deeply rooted in the geometric control provided by error bounds.

Furthermore, this perspective sheds light on regularized solution paths and adaptive optimizers. Alberto González-Sanz et al. (2024) utilize suboptimality slope bounding in Quantitative Convergence of Quadratically Regularized Linear Programs to establish a linear bound on the rate of improvement toward an optimal solution as a regularization penalty vanishes. In a similar vein, Diego Klabjan et al. (2024) use approximate Karush-Kuhn-Tucker conditions in A Mirror Descent Perspective of Smoothed Sign Descent to provide explicit mathematical bounds on how much final weights deviate from a perfect solution when using adaptive, sign-based descent methods.

Ultimately, error bounds reveal that global strong convexity is a sufficient condition for fast convergence, but far from a necessary one. By ensuring a strict geometric relationship between local algorithmic movement and global distance to the solution, error bounds explain why simple first-order methods remain incredibly efficient at solving complex, nonsmooth, and nonconvex real-world problems.

Key Foundational Work

On the Linear Convergence of a Proximal Gradient Method for a Class of Nonsmooth Convex Minimization Problems (2013) — contributed 2 concept elements to this direction.
\(\ell_{1, p}\)-Norm Regularization: Error Bounds and Convergence Rate Analysis of First-Order Methods (2015) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_local_error_bound_8620c03f,
  title = {local error bound},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/local-error-bound/rdr_8620c03fb6334c87970570d919ff832a},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_local_error_bound_8620c03f_v1,
  title = {local error bound},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/local-error-bound/rdr_8620c03fb6334c87970570d919ff832a/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake