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 behaves like an accelerated method in experiments. This led to the conjecture that it is accelerated in the strongly convex case without knowing the strong convexity parameter. We show that the conjecture fails in the worst case. For every subspace method whose memory forgets slowly, namely a window of recent gradients and steps together with cumulative sums with subexponential weights, we construct a counterexample: acceleration requires a window of length of order √κ, where κ is the condition number. SESOP and the plane form of conjugate gradients are therefore not accelerated. Memories that forget fast avoid this obstruction. Pairs of geometric filters give accelerated methods with logarithmic memory or only two stored vectors. They need neither the strong convexity parameter nor the smoothness constant, never restart the iterate and restart their memory at most O(logκ) times. Finally, the method with fixed activation times remains asymptotically accelerated on functions with Lipschitz Hessian even when each subproblem is solved by a single Newton step.
Related
- Effect of Spherical Parameter Space on Number of Non-Forgetting Tasks and Capacity of Continual Learning
- Behavioral Mapping of Hierarchical Dynamical Models Accelerates Bayesian Parameter Inference
- Parameter-Robust Subspace Correction with Multiple Semidefinite Penalties
- An Iterative Active Subspace Approach for Model Order Reduction of Parametric Systems with High-Dimensional Parameter Spaces
- An Optimal Second-Order Algorithm for Finite-Sum Optimization under Average Smoothness and Convexity
BibTeX
@misc{kuruzov2026forgetting,
title = {{Forgetting matters: when subspace optimization accelerates without the strong convexity parameter}},
author = {Ilya Kuruzov and Alexander Vyguzov and Ivan Dorofeev and Alexander Gasnikov},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.00727},
eprint = {2611.00727},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.00727},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Forgetting matters: when subspace optimization accelerates without the strong convexity parameter
AU - Ilya Kuruzov
AU - Alexander Vyguzov
AU - Ivan Dorofeev
AU - Alexander Gasnikov
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.00727
UR - https://arxiv.org/abs/2611.00727
AB - 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 behaves like an accelerated method in experiments. This led to the conjecture that it is accelerated in the strongly convex case without knowing the strong convexity parameter. We show that the conjecture fails in the worst case. For every subspace method whose memory forgets slowly, namely a window of recent gradients and steps together with cumulative sums with subexponential weights, we construct a counterexample: acceleration requires a window of length of order √κ, where κ is the condition number. SESOP and the plane form of conjugate gradients are therefore not accelerated. Memories that forget fast avoid this obstruction. Pairs of geometric filters give accelerated methods with logarithmic memory or only two stored vectors. They need neither the strong convexity parameter nor the smoothness constant, never restart the iterate and restart their memory at most O(logκ) times. Finally, the method with fixed activation times remains asymptotically accelerated on functions with Lipschitz Hessian even when each subproblem is solved by a single Newton step.
ER -