no. 16 · Tuesday 17 November 2026
Forgetting matters: when subspace optimization accelerates without the strong convexity parameter
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.
- fields
- Optimization and Control