Forgetting matters: when subspace optimization accelerates without the strong convexity parameter
math.OC
Submitted: 2026-10-31
Updated: 2026-11-16
License: http://creativecommons.org/licenses/by/4.0/
The gist: Sequential subspace optimization (SESOP) minimizes the objective exactly over a few directions built from past iterates.
Terminology
Abstract
Sequential subspace optimization (SESOP) minimizes the objective exactly over a few directions built from past iterates. It needs no problem constants, is accelerated on smooth convex functions and in practice behaves like an accelerated method. This led to the conjecture that it is uniformly accelerated on strongly convex functions as well. The conjecture is false. Consider exact subspace methods whose memory is a window of recent gradients and steps plus finitely many fixed cumulative sums. Uniform acceleration then requires either a window whose length grows as the square root of the condition number or a sum that forgets at a rate of at least the order of the inverse square root. For one filter pair with a fixed factor and a bounded window this scale of forgetting is necessary and sufficient up to constants. SESOP remembers too much and the plane form of conjugate gradients too little: neither is uniformly accelerated, even on infinitely differentiable functions that are quadratic near the minimizer. A short window, in contrast, converges locally quadratically over blocks of steps when the Hessian is Lipschitz near the minimizer and equals a multiple of the identity plus a low-rank term there. Pairs of geometric filters created at fixed times give a uniformly accelerated method with logarithmic memory and no problem constants, also with inexact subproblems. A single pair with a smoothly adapted factor needs two vectors and is accelerated up to a prefactor polynomial in the condition number.
Sources
- On Some Versions of Subspace Optimization Methods with Inexact Gradient Information
- Detecting and correcting the loss of independence in nonlinear conjugate gradient
- A Parameter-Free Restart Scheme with Only a Parallelizable $\log\log(1/\epsilon)$ Overhead
- Gradient Methods with Memory for Minimizing Composite Functions
- Adaptive Acceleration Without Strong Convexity Priors Or Restarts
Related papers
- An Accelerated Proximal Gradient Method for Bures-Wasserstein Space
- FOMTools: Development and AI-Assisted Code Generation for First-Order Methods
- Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
- Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms
- Integrating Learning and Optimization for Open Transport Capacity Pooling under Disruption
- Zeroth-Order Gradient Estimators under Decision-Dependent Noise