← All problems

Parameter-free acceleration conjecture for SESOP and related subspace methods

Let ff be an LL-smooth, bcbc-strongly convex function with condition number ba=L/bcba=L/bc. Does sequential subspace optimization (SESOP), using only past iterates and gradients and without knowing the strong-convexity parameter bcbc, achieve an accelerated convergence rate whose iteration complexity has dependence O(0˘003balog⁡(1/0˘003b5))O(\sqrt{\u0003ba}\log(1/\u0003b5)) for obtaining an iterate xx satisfying f(x)−f(x∗)≤0˘003b5f(x)-f(x^*)\leq\u0003b5?

References

Source: arXiv

Progress summary

Refreshed
Open · progress reported

A new unrefereed preprint says some memory schemes cannot achieve parameter-free speedups, while others may do so, so the broad conjecture is not settled.

The conjecture concerns whether SESOP and related subspace methods can accelerate without knowing the strong-convexity parameter. The latest work separates memory mechanisms that obstruct acceleration from proposed memories that may achieve it.

October 31, 2026 development

Ilya Kuruzov, Alexander Vyguzov, Ivan Dorofeev, and Alexander Gasnikov report obstructions for specified slowly forgetting memory windows and propose geometric-filter memories with logarithmic or constant storage. This is progress on the classified memory regimes, not a resolution for all subspace methods; the preprint is unrefereed.

Current status (as of November 2026): The broad conjecture remains open; a preprint claims partial negative and positive results for specified memory mechanisms, but these results are unverified.

Sources

Solutions 0

No solutions have been posted yet.