The High Precision Bottleneck of First Order Optimization

128 concepts115 papers1 proposal

First-order optimization methods—such as gradient descent, the Alternating Direction Method of Multipliers (ADMM), and primal-dual gradient schemes—are the workhorses of modern large-scale computation. They are computationally lightweight, require only basic matrix-vector multiplications, and scale gracefully to millions of variables.

However, these algorithms suffer from a severe structural limitation known as the high-precision convergence bottleneck. While first-order methods excel at rapidly finding a coarse, "good enough" solution, their progress slows to a crawl as they approach the exact optimum. This makes them highly inefficient when machine-level precision or strict feasibility is required.

The Geometry of the Tail

To understand why first-order methods stall, imagine navigating a deep, foggy valley using only the slope of the ground directly beneath your feet. When you are high up on the ridges, the slope is steep, and stepping downhill quickly brings you closer to the valley floor. But as you near the bottom, the terrain flattens out. Without knowing how the valley curves ahead, you are forced to take agonizingly small steps or risk oscillating back and forth across the floor indefinitely.

This is the "tailing-off" effect. Because first-order methods rely exclusively on local gradient information, they are blind to the underlying curvature (the Hessian matrix) of the optimization landscape. As observed by Alnur Ali et al. in A Semismooth Newton Method for Fast, Generic Convex Programming, these algorithms frequently exhibit sub-linear or slow linear convergence near the optimum. Instead of cleanly terminating, they enter a regime of diminishing returns. Alberto De Marchi et al. describe this in An interior proximal gradient method for nonconvex optimization as slow tail convergence: the algorithm rapidly reaches the neighborhood of a solution but requires a disproportionate number of iterations to achieve high-precision accuracy.

The Scaling Wall: Polynomial vs. Logarithmic

The bottleneck can be precisely framed by looking at how an algorithm's workload scales with the desired error tolerance ($\varepsilon$).

For a typical first-order method, the iteration complexity scales polynomially with the inverse of the error, often denoted as $O(1/\varepsilon)$ or $O(1/\varepsilon^2)$. As Arun Jambulapati et al. note in Revisiting Area Convexity: Faster Box-Simplex Games and Spectrahedral Generalizations, this inverse scaling means that demanding just one additional decimal point of precision can multiply the required computational iterations tenfold. For highly sensitive problems like Semidefinite Programs (SDPs), Yin Tat Lee et al. demonstrate in An $\widetilde\mathcalO(m/\varepsilon^3.5)$-Cost Algorithm for Semidefinite Programs with Diagonal Constraints that this polynomial dependence makes pure first-order approaches highly impractical when tolerances are very tight. Furthermore, Moise Blanchard et al. show in Memory-Constrained Algorithms for Convex Optimization that gradient-based methods suffer from poor query complexity under strict error tolerances compared to memory-intensive cutting-plane alternatives.

Conversely, second-order methods (such as Newton's method or interior-point methods) compute or approximate the Hessian to map the landscape's curvature. This gives them quadratic convergence near the optimum, meaning the number of correct digits doubles with every iteration. Their workload scales logarithmically as $O(\log(1/\varepsilon))$.

Iteration Complexity vs. Precision (1/ε)

Iterations 
    ▲
    │       / First-Order: O(1/ε) [Stalls at high precision]
    │      /
    │     /
    │    /
    │   /
    │  /   
    │ /_________________ Second-Order: O(log(1/ε)) [Smooth scaling]
    └────────────────────────► High Precision (Small ε)

For applications requiring extreme numerical accuracy (such as a $10^{-10}$ relative gap), Tianxiao Sun et al. show in Composite convex optimization with global and local inexact oracles that second-order methods reach high-precision thresholds significantly faster than first-order algorithms, despite having a higher computational cost per individual iteration.

Where the Bottleneck Matters

In many machine learning applications, coarse precision is acceptable because generalization error bounds dominate numerical errors. However, the high-precision bottleneck remains a critical failure point in several engineering and scientific domains:

Strategies for Breaking the Bottleneck

To bypass this limitation, recent research focuses on hybrid architectures that combine the scalability of first-order steps with the rapid local convergence of second-order methods.

1. Semismooth Newton Fixed-Point Accelerators

Instead of optimizing the original objective function directly with a second-order method, researchers treat the updates of a first-order method as a fixed-point problem and apply a Semismooth Newton (SSN) method to the residuals.

In A Semismooth Newton Method for Fast, Generic Convex Programming, the authors apply an SSN method to the residuals of ADMM, successfully capturing quadratic convergence and eliminating the slow linear tail. Similarly, Xudong Li et al. demonstrate in An Asymptotically Superlinearly Convergent Semismooth Newton Augmented Lagrangian Method for Linear Programming that combining an augmented Lagrangian framework with a semismooth Newton method yields fast, superlinear convergence for large-scale linear programming.

2. Adaptive Restarts and Sharpness

Another approach attempts to force first-order methods into a linear convergence regime by exploiting the underlying geometry of the problem.

By utilizing adaptive restart mechanisms, algorithms can wipe out accumulated error history once they detect they are approaching the optimum. David Applegate et al. show in Practical Large-Scale Linear Programming using Primal-Dual Hybrid Gradient that integrating adaptive restarts allows first-order methods to achieve high-precision solutions (down to $10^{-8}$ relative error) on industrial linear programming problems. In Faster first-order primal-dual methods for linear programming using restarts and sharpness, the authors prove that exploiting a structural "sharpness" condition via restarts allows first-order methods to achieve optimal linear convergence rates, dramatically mitigating the tailing-off effect.

3. Primal-Dual Proximal Hybrids

Modern solvers increasingly embed proximal regularizers directly inside interior-point or augmented Lagrangian frameworks. By doing so, solvers like ProxQP and PIQP maintain the low per-iteration cost and warm-starting capabilities of first-order methods while leveraging second-order updates to cleanly snap to the global optimum without numerical stagnation.

Key Foundational Work

Smooth Optimization with Approximate Gradient (2005) — contributed 3 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 115 papers
  2. Version 1 · 2026-10-04 · 211 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_high_precision_convergence_bottleneck_326e1373,
  title = {high-precision convergence bottleneck},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/high-precision-convergence-bottleneck/rdr_326e1373b7a449bd9b5c103a70684aeb},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_high_precision_convergence_bottleneck_326e1373_v2,
  title = {high-precision convergence bottleneck},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/high-precision-convergence-bottleneck/rdr_326e1373b7a449bd9b5c103a70684aeb/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake