Tightening Convergence Bounds for Practical Optimization

This direction is split into other directions: theoretical-empirical performance gap (theoretical-empirical convergence gap). Its last version stays readable and citable here.

Version 1 of 1462 papers489 conceptsfrozen 2026-10-04

In the world of optimization, there is a long-standing "theory-practice gap." If you look at a textbook for Stochastic Gradient Descent (SGD), it might tell you the algorithm converges at a rate of $O(1/\sqrt{T})$. If you actually run the code, however, it often behaves as if it’s converging much faster—closer to $O(1/T)$ or even at a linear rate.

For years, researchers treated this discrepancy as a quirk of "good data." But a growing body of research is moving beyond these pessimistic upper bounds. By identifying hidden structural properties in data and using more sophisticated mathematical tools, researchers are proving that our algorithms are actually as good as they look in practice.

The Problem with Global Pessimism

Standard optimization theory often assumes the worst-case scenario. To prove a convergence rate, theorists traditionally require a property called strong convexity. If a function is strongly convex, it has a clear, bowl-like curvature everywhere, allowing an algorithm to slide down to the minimum quickly.

The problem is that most real-world functions—especially in deep learning—are not globally strongly convex. They are flat in some places and curvy in others. Traditional theory looks at the "flat" parts and concludes the algorithm must be slow.

However, Chao Qu, Huan Xu, and Chong Jin Ong showed in Fast Rate Analysis of Some Stochastic Optimization Algorithms that you don't need global strong convexity. If the function is locally strongly convex around the optimal solution, stochastic algorithms like OPG and RDA can achieve a "fast rate" of $O(\ln T / T)$. This shift in perspective—from global requirements to local behavior—explains why algorithms accelerate as they get closer to the answer.

Finding Hidden Structure in Data

Sometimes the speed doesn't come from the function itself, but from the geometry of the data. In When do support vector machines work fast?, Ingo Steinwart demonstrates that Support Vector Machines (SVMs) learn much faster than standard benchmarks suggest when data clusters away from the decision boundary. By formalizing this geometric condition, the theory finally matches the near-linear learning rates observed in the field.

Similarly, Jialei Wang explores how primal-dual algorithms can exploit "hidden" strong convexity inherent in specific datasets. These algorithms can tune their own parameters on the fly, effectively "sensing" the curvature of the data to achieve linear convergence even when the problem wasn't explicitly regularized to do so.

The Power of Over-Parameterization

One of the biggest mysteries in modern AI is why massive neural networks converge so quickly despite being "over-parameterized." Traditional theory suggests that having more parameters than data points should make the optimization landscape a nightmare of flat plateaus.

In Adaptive Gradient Methods Converge Faster with Over-Parameterization, Sharan Vaswani and colleagues show that this "interpolation regime" actually simplifies the problem. When a model is large enough to fit the training data perfectly, adaptive methods like Adam and AdaGrad naturally hit an $O(1/T)$ rate. The over-parameterization creates a "realizable" setting where the gradient doesn't just get small—it vanishes exactly at the solution, allowing for much more aggressive steps.

Computer-Aided Tightness

Even when we know an algorithm is fast, proving the exact rate is notoriously difficult. It often requires finding a Lyapunov function—a mathematical "energy" that decreases at every step. Finding these functions has historically been a manual "black art."

Researchers like Adrien Taylor and Francis Bach are turning this into a science. In Stochastic first-order methods: non-asymptotic and computer-aided analyses via potential functions, they use computer-aided proofs to search for the tightest possible Lyapunov functions. This approach was used in Tight analyses of first-order methods with error feedback to prove that certain communication-compression methods are exactly as efficient as their uncompressed counterparts, resolving long-standing debates about the "cost" of distributed learning.

Why Shuffling and Blocking Work

Finally, this research direction has tackled the "common sense" heuristics that practitioners use every day. For example, almost everyone shuffles their data before training, but for a long time, theory couldn't prove why this was better than random sampling. Zijian Liu and Zhengyuan Zhou recently provided the first theoretical proof that shuffling gradient methods converge faster than standard descent for nonsmooth problems, matching the lower bounds that had eluded theorists for years.

Similarly, Improved Iteration Complexity Bounds of Cyclic Block Coordinate Descent narrowed the gap for BCD algorithms. While old proofs suggested BCD was $K$ times slower (where $K$ is the number of blocks), new analysis shows that for quadratic problems, BCD is nearly as fast as full Gradient Descent, providing the mathematical "permission" for its widespread use in large-scale machine learning.

By moving away from conservative, one-size-fits-all bounds, this field is creating a new "theory of the average case" that finally explains why our most successful algorithms work as well as they do.

Papers in this version

Showing 60 of 462 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_tightening_convergence_bounds_for_practi_9329c631,
  title = {Tightening Convergence Bounds for Practical Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/tightening-convergence-bounds-for-practical-optimization/rdr_9329c631973840c19a2e7b23b4f090b1},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_tightening_convergence_bounds_for_practi_9329c631_v1,
  title = {Tightening Convergence Bounds for Practical Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/tightening-convergence-bounds-for-practical-optimization/rdr_9329c631973840c19a2e7b23b4f090b1/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}