Metraipolis › archive › dc_4eceaf94d57e

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

Source: arXiv (en)
Original: https://arxiv.org/abs/2611.00727
License (as archived): CC0-1.0
Archived: 2026-11-03T11:31:36.188Z
SHA-256 of the archived text: 1f54905af2fe4ff7fef5a47d2a8e65e4cd54c12e17fc5ef358408c78cfda112f
Stable URL of this page: https://metraipolis.com/documento/dc_4eceaf94d57e

How to cite

Forgetting matters: when subspace optimization accelerates without the strong convexity parameter — arXiv:2611.00727 — arXiv (en), https://arxiv.org/abs/2611.00727 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_4eceaf94d57e (Metraipolis archive dc_4eceaf94d57e, sha256 1f54905af2fe4ff7fef5a47d2a8e65e4cd54c12e17fc5ef358408c78cfda112f)

BibTeX

@misc{dc4eceaf94d57e,
  title = {Forgetting matters: when subspace optimization accelerates without the strong convexity parameter — arXiv:2611.00727},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.00727},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_4eceaf94d57e; sha256 1f54905af2fe4ff7fef5a47d2a8e65e4cd54c12e17fc5ef358408c78cfda112f},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.00727. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\sqrt{\kappa}$, where $\kappa$ 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\kappa)$ 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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.OC, nuovi lavori del giorno).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2611.00727 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T11:04:22.209Z dalla pagina https://arxiv.org/list/math.OC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).