Paperlane

no. 16 · Tuesday 17 November 2026

Forgetting matters: when subspace optimization accelerates without the strong convexity parameter

Ilya Kuruzov, Alexander Vyguzov, Ivan Dorofeev and Alexander Gasnikov

math.OC · v2

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
pdf ↗ page arXiv:2611.00727 ↗