Skip to main content
Back

Imperial College London Explains Why Your Optimizer Runs Faster Than Theory Predicts

A new optimization framework shows convergence speed depends on the local geometry an algorithm actually traverses, not worst-case bounds over the entire space.

Paper, Full Access
  • New framework localizes PL, error bound, and quadratic growth conditions to subsets that optimization trajectories actually traverse.
  • For polyhedral problems, convergence is governed by restricted Hoffman constants on active faces, not global ones.
  • LASSO local condition number improves from d^2 to n^2, dimension-free under normalized loss.
  • Explains empirical two-phase ISTA convergence: slow search phase, then fast active-set phase.
  • Extends naturally to dual SVMs, coordinate descent, and general l_p geometry.
  • Reproducible LASSO experiments released; builds on Karimi et al. 2016.

Watch a proximal gradient method blast through a high-dimensional LASSO problem far faster than its theoretical convergence rate predicts, and you are looking at a well-known gap between optimization theory and practice. A new paper from Imperial College London and the Institute of Statistical Mathematics in Japan, Trajectory-Restricted Optimization Conditions, tries to close that gap by rewriting the classical linear convergence guarantees in terms of the geometry an algorithm actually visits.

The pessimism baked into classical rates

Linear convergence for first-order methods is typically established through conditions like the Polyak-Lojasiewicz (PL) inequality, error bounds, or quadratic growth. These are gradient-dominance conditions that say roughly: whenever you are far from the optimum in function value, the gradient (or a proximal analogue) must be large enough to guarantee real progress. The PL inequality is weaker than most other conditions used to prove linear convergence without strong convexity, and it extends cleanly to proximal-gradient methods for non-smooth objectives.

The catch is that the constants in these inequalities are almost always defined globally, over the entire ambient space. In high dimensions that worst-case view can be absurdly loose. For LASSO, the global condition number scales as roughly d^2 in the ambient dimension d, even though iterates in practice quickly collapse onto a low-dimensional support and converge like a small, well-conditioned problem.

Localizing the classical conditions

The authors introduce restricted versions of the three workhorse conditions, each required to hold only on some subset K of the domain that the algorithm actually explores:

  • A K-restricted proximal PL inequality
  • A K-restricted proximal error bound
  • A K-restricted quadratic growth condition

They show that the classical convergence proof for proximal gradient descent goes through almost unchanged: if the iterate lies in K and the restricted PL constant is