betaFeedback

WorksMathematics

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.

Introduction

We consider min⁡x∈Rnf(x)\min_{x\in\mathbb{R}^n} f(x) for a μ\mu-strongly convex ff with LL-Lipschitz gradient and condition number κ=L/μ\kappa= L/\mu. Optimal methods need of order κlog⁡(1/ε)\sqrt{\kappa}\log(1/\varepsilon) gradient evaluations to reduce the gap by the factor ε\varepsilon, and gradient descent needs κlog⁡(1/ε)\kappa\log(1/\varepsilon) [1, 2]. For κ=106\kappa= 10^6 this is a factor of a thousand. Nesterov’s method [2, 3] attains the optimal order, but its momentum depends on μ\mu. Unlike LL, the constant μ\mu cannot be found by backtracking: finitely many values and gradients never certify a positive lower bound on the curvature. The usual remedy is restarting [4, 5, 6].

Conjugate gradients avoid μ\mu on quadratics. They minimize ff exactly over the plane of the gradient and the previous step, and the minimization picks the very coefficients that Nesterov’s method computes from μ\mu and LL [7], so no constant has to be known. Exact subspace methods xk+1=arg⁡min⁡{f(x):x∈xk+Sk}x_{k+1}=\arg\min\{f(x):x\in x_k+S_k\} extend this idea. Nemirovski’s orth-method [8], known as SESOP [9], uses

Sk=span⁡{∇f(xk), xk−xk−1, xk−x0, ∑i=0kwi∇f(xi)}S_k=\operatorname{span}\left\{\nabla f(x_k),\ x_k-x_{k-1},\ x_k-x_0,\ \sum_{i=0}^{k}w_i\nabla f(x_i)\right\}

and attains the rate O(LR2/k2)O(LR^2/k^2) on smooth convex functions without any parameter. It performs well on strongly convex problems [10], in our experiments far better than Nesterov’s method with true constants. To the best of our knowledge, it is open whether unrestarted SESOP is accelerated uniformly over Fμ,L\mathcal{F}_{\mu,L}, in the sense of (2). In this paper we continue the study of subspace methods started in [11]. Oracle lower bounds do not separate SESOP from accelerated methods, and on quadratics it coincides with conjugate gradients, so a hard instance must carry an infinite trajectory consistent with SESOP’s anchor and aggregate. For nonlinear conjugate gradients worst-case limitations are known [1, 12, 13].

Our approach starts from the fact that exact minimization over xk+Skx_k+S_k inherits the rate of an accelerated method as soon as SkS_k contains its momentum. This momentum is a geometric average of past gradients and steps with a horizon of order κ\sqrt{\kappa}, so, roughly speaking, acceleration without μ\mu comes down to memory: which subspaces built from the history contain such an average when κ\kappa is unknown? SESOP keeps everything, stale directions included, while a memory that forgets too fast cannot look far enough back. We show that forgetting on the right time scale is both necessary and sufficient, and that this scale can be found without κ\kappa.

Contributions

  1. Remembering too much (§ 4.2). We measure a memory fixed in advance by its window mm and the forgetting index δ\delta of its cumulative sums. For κ≥100(m+2)2\kappa\ge100(m+2)^2 and slowly forgetting sums we construct functions in Fμ,L\mathcal{F}_{\mu,L} on which every exact subspace method with this memory needs Ω((κ/m)log⁡(1/ε))\Omega((\kappa/m)\log(1/\varepsilon)) iterations as ε→0\varepsilon\to0 (Theorem 4.2). SESOP and the plane form of conjugate gradients are such methods and need Ω(κlog⁡(1/ε))\Omega(\kappa\log(1/\varepsilon)) iterations (Corollary 4.3).

  1. Forgetting too fast and the right time scale (Sections 4.3 to 4.5). A filter pair that forgets much faster than at rate κ−1/2\kappa^{-1/2} leaves a method with a bounded window as

slow as a short window (Theorem 4.9). So uniform acceleration needs a window of length Ω(κ)\Omega(\sqrt{\kappa}) or δ=Ω(κ−1/2)\delta= \Omega(\kappa^{-1/2}), and with a bounded window and one pair exactly 1−ρ=Θ(κ−1/2)1-\rho= \Theta(\kappa^{-1/2}) (Corollary 4.10). SESOP misses this time scale. Like the plane form, it stays slow with one aggregate on C∞\mathcal{C}^{\infty} functions that are quadratic near the minimizer (Propositions 4.13, 4.14).

  1. Windows (§ 5.1). A window of length 1.39κ1.39\sqrt{\kappa} is accelerated, so the bound Ω(κ)\Omega(\sqrt{\kappa}) is sharp (Proposition 5.1). A short window converges quadratically over blocks near a minimizer where the Lipschitz Hessian is a multiple of the identity plus a low-rank term (Theorem 5.2). Near such a minimizer this is faster than any linear rate.

  1. Reaching the time scale without κ\kappa (§ 5.2 and § 5.3). Pairs of geometric filters store a horizon of order κ\sqrt{\kappa} in two vectors (Lemma 5.3). Created at times 2j2^j, they give a uniformly accelerated method with memory O(log⁡k)O(\log k) (Theorem 5.4). One pair with a smoothly adapted horizon and no resets is accelerated up to a polynomial prefactor, and with the SESOP directions it keeps the convex rate and is conjugate gradients on quadratics (Theorem 5.5). The schedule also allows inexact subproblems (Proposition 5.7).

All upper bounds follow from one estimate-sequence certificate. Restart schemes are nearly optimal [6, 14], and our rates are no better, but our methods need neither μ\mu nor LL, are monotone and never reset their memory (Table 1).

methodstoragememory, horizonweightsaccelerated
SESOP3slow, ∞\inftyfixedno (Cor. 4.3), O(1/k2)O(1/k^2) if μ=0\mu= 0
window mm2m−12m - 1window, mmfixediff m≳κm \gtrsim\sqrt{\kappa} (Cor. 4.10, Prop. 5.1)
activation schedule2⌈log⁡2k⌉2\lceil\log_2 k\rceilfast, ≤k\leq kfixed timesuniform (Thm. 5.4)
smooth pair2fast, ≤2.5κ\leq2.5\sqrt{\kappa}adaptiveup to poly(κ)(\kappa) (Thm. 5.5)
smooth pair + SESOP5fast and slowadaptivesame, O(1/k2)O(1/k^2) if μ=0\mu= 0 (Thm. 5.5)

Table 1. Methods of this paper, none of which uses μ\mu, LL or a bound on κ\kappa. Storage counts vectors besides xkx_k and ∇f(xk)\nabla f(x_k), and a filter with factor ρ\rho has horizon 1/(1−ρ)1/(1-\rho). “Up to poly(κ)(\kappa)”: an accelerated rate with a prefactor polynomial in κ\kappa. The horizon bound needs κ≥4\kappa\geq4.

The rest of the paper is organized as follows. Sections 2 and 3 cover related work and the setting, Sections 4 and 5 the lower and upper bounds, and Section 6 experiments.

Related work

Exact minimization over low-dimensional subspaces is as old as conjugate gradients [7] and their nonlinear extensions [15]. A subspace containing the momentum of an accelerated method [2] gives an exact step at least as good as the accelerated one, which underlies the orth-method [8], methods with a small-dimensional relaxation oracle [16, 17] and the span search of Drori and Taylor [18]. Narkiss and Zibulevsky [9] named the approach SESOP and solved the subproblems by Newton’s method, so that for φ(Ax)\varphi(Ax) a step costs as many products with AA as a gradient step [19]. SESOP has been extended to weakly quasi-convex functions [10], inexact gradients and restarted conjugate gradients under quadratic growth [11, 20]. CGSO [12] attains O(κlog⁡(1/ε))O(\sqrt{\kappa}\log(1/\varepsilon)) without constants of the function with a subspace of dimension O(log⁡k)O(\log k), using a progress test, the anchor and gradient sums restarted at every dyadic block. Other methods alternate conjugate gradient and accelerated steps [21] or minimize a model built from past gradients [22]. The limited-memory common-directions method [23] is accelerated when the subspace contains Nesterov’s momentum, which requires μ\mu and LL, whereas our filter pairs contain such a momentum without the constants. Tupitsa [24] replaces the exact subproblem of SESOP by a cubic model and attains a local accelerated rate with adaptive restarts.

Restarting a convex accelerated method with period of order κ\sqrt{\kappa} gives an accelerated linear rate [25]. Adaptive schemes decrease an estimate of μ\mu when progress is insufficient [26, 27], test the progress directly [4] or search over a grid of constants [5, 6]. Each restart throws the momentum away. The online estimate of μ\mu in [28] has no guarantee. The survey [29] listed the estimation of μ\mu without restarts as an open problem, which NAG-free [30] later addressed with a global rate of gradient descent type and acceleration near the minimizer. Our smooth pair estimates no constant: it adapts the forgetting horizon of the memory and is globally accelerated, up to a prefactor polynomial in κ\kappa. Lan, Ouyang and Zhang [31] reach ∥∇f∥≤ε\lVert\nabla f\rVert\le\varepsilon with O(κ(log⁡(μ0/μ)+log⁡(∥∇f(x0)∥/ε)))O(\sqrt{\kappa}(\log(\mu_0/\mu)+\log(\lVert\nabla f(x_0)\rVert/\varepsilon))) gradient evaluations from a guess μ0≥μ\mu_0 \ge\mu. These methods count gradient evaluations, whereas we count subspace steps and bound the memory from below.

Oracle lower bounds [1, 2] hold for all first-order methods and are attained when μ\mu is known. Nemirovski [32] extended them to methods that query the oracle on an affine manifold of fixed dimension at every step, covering exact subspace steps. In large dimension they still need of order κlog⁡(1/ε)\sqrt{\kappa}\log(1/\varepsilon) steps on Fμ,L\mathcal{F}_{\mu,L}, so no subspace method beats acceleration. The bounds of § 4 hold in a fixed dimension as ε→0\varepsilon\to0 and decide which memories reach it. Oblivious methods, whose coefficients do not depend on the data, cannot be accelerated without μ\mu [33]. Exact minimization is not oblivious, and our bounds cover it for memories fixed in advance. They rest on the interpolation theorem of Taylor, Hendrickx and Glineur [34], which underlies performance estimation [35] and the exact rate of GD-ELS [36], applied to infinite trajectories whose residuals keep a uniform margin (Lemma 4.7).

Setting and two tools

Inner products and norms are Euclidean. The class Fμ,L(Rn)\mathcal{F}_{\mu,L}(\mathbb{R}^{n}) consists of differentiable μ\mu-strongly convex functions with LL-Lipschitz gradients, 0<μ≤L0 < \mu\le L, and κ=L/μ\kappa= L/\mu, where the constants are valid bounds rather than the best ones. For a method generating points xkx_k we write sk=xk−xk−1s_k = x_k - x_{k-1} for k≥1k \ge1 and s0=0s_0 = 0, and f⋆f^\star and x⋆x^\star are the minimum value and the minimizer. For 0<ε≤10 < \varepsilon\le1 the complexity N(ε)N(\varepsilon) is the first kk with f(xk)−f⋆≤ε(f(x0)−f⋆)f(x_k) - f^\star\le\varepsilon(f(x_0) - f^\star).

Unless stated otherwise, the methods perform the exact subspace step

xk+1=arg min⁡x∈xk+Sk f(x),∇f(xk)∈Sk(1)x_{k+1} = \underset{x \in x_k+S_k}{\operatorname{arg\,min}}\ f(x), \qquad\nabla f(x_k) \in S_k \tag*{(1)}

where the linear subspace SkS_k is built from the history by some rule. One iteration means one exact solution of (1), whatever the inner solver. The window method of length mm searches over the last mm gradients and steps, $S_k = \operatorname{span}{\nabla f(x_i), s_i : k-m < i≤ki \le k. GD-ELS, gradient descent with exact line search, uses Sk=span⁡{∇f(xk)}S_k = \operatorname{span}\{\nabla f(x_k)\}, and the plane form of conjugate gradients uses Sk=span⁡{∇f(xk),sk}S_k = \operatorname{span}\{\nabla f(x_k),s_k\}. SESOP with weights w1,…,wdw_1,\ldots,w_d uses Sk=span⁡{∇f(xk),sk,xk−x0,σk1,…,σkd}S_k = \operatorname{span}\{\nabla f(x_k),s_k,x_k-x_0,\sigma^1_k,\ldots,\sigma^d_k\} with the aggregates σka=∑i=0kwa(i)∇f(xi)\sigma^a_k = \sum_{i=0}^{k} w_a(i)\nabla f(x_i). Common choices are Nemirovski’s weights, w(k)=12+14+w(k−1)2w(k) = \frac{1}{2} + \sqrt{\frac{1}{4} + w(k-1)^2} with w(0)∈{0,1}w(0) \in\{0,1\}, and the linear weights w(i)=iw(i)=i.

Our upper bounds use only the following properties of (1).

References

  1. [1]Nemirovsky, A.S., Yudin, D.B.: Problem Complexity and Method Efficiency in Optimization. Wiley, New York (1983)
  2. [2]Nesterov, Y.: Lectures on Convex Optimization, 2nd edn. Springer Optimization and Its Applications, vol. 137. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-91578-4
  3. [3]Nesterov, Y.E.: A method of solving a convex programming problem with convergence rate O(1/k²). Doklady Akademii Nauk SSSR 269(3), 543–547 (1983). In Russian
  4. [4]O’Donoghue, B., Candès, E.: Adaptive restart for accelerated gradient schemes. Foundations of Computational Mathematics 15(3), 715–732 (2015) https://doi.org/10.1007/s10208-013-9150-3
  5. [5]Roulet, V., d’Aspremont, A.: Sharpness, restart, and acceleration. SIAM Journal on Optimization 30(1), 262–289 (2020) https://doi.org/10.1137/18M1224568
  6. [6]Renegar, J., Grimmer, B.: A simple nearly optimal restart scheme for speeding up first-order methods. Foundations of Computational Mathematics 22(1), 211–256 (2022) https://doi.org/10.1007/s10208-021-09502-2
  7. [7]Hestenes, M.R., Stiefel, E.: Methods of conjugate gradients for solving linear systems. Journal of Research of the National Bureau of Standards 49(6), 409–436 (1952) https://doi.org/10.6028/jres.049.044
  8. [8]Nemirovski, A.S.: Orth-method for smooth convex optimization. Izvestia AN SSSR, Tekhnicheskaya Kibernetika (2) (1982). In Russian
  9. [9]Narkiss, G., Zibulevsky, M.: Sequential subspace optimization method for large-scale unconstrained problems. CCIT Report 559, Technion – Israel Institute of Technology, Department of Electrical Engineering (2005)
  10. [10]Guminov, S., Gasnikov, A., Kuruzov, I.: Accelerated methods for weakly-quasi-convex optimization problems. Computational Management Science 20(1), 36 (2023) https://doi.org/10.1007/s10287-023-00468-w
  11. [11]Kuruzov, I., Stonyakin, F.: On some versions of subspace optimization methods with inexact gradient information. arXiv:2407.01051 (2024)arxiv.org/abs/2407.01051
  12. [12]Karimi, S., Vavasis, S.A.: Conjugate gradient with subspace optimization. Optimization Online preprint, https://optimization-online.org/2012/02/3346/ (2012)
  13. [13]Das Gupta, S., Freund, R.M., Sun, X.A., Taylor, A.: Nonlinear conjugate gradient methods: worst-case convergence rates via computer-assisted analyses. Mathematical Programming 213(1-2), 1–49 (2025) https://doi.org/10.1007/s10107-024-02127-7
  14. [14]Wu, Y., Grimmer, B.: A parameter-free restart scheme with only a parallelizable log log(1/ε) overhead. arXiv:2605.30502 (2026)arxiv.org/abs/2605.30502
  15. [15]Hager, W.W., Zhang, H.: A survey of nonlinear conjugate gradient methods. Pacific Journal of Optimization 2(1), 35–58 (2006)
  16. [16]Nesterov, Y., Gasnikov, A., Guminov, S., Dvurechensky, P.: Primal–dual accelerated gradient methods with small-dimensional relaxation oracle. Optimization Methods and Software 36(4), 773–810 (2021) https://doi.org/10.1080/10556788.2020.1731747
  17. [17]Guminov, S.V., Nesterov, Y.E., Dvurechensky, P.E., Gasnikov, A.V.: Accelerated primal-dual gradient descent with linesearch for convex, nonconvex, and nonsmooth optimization problems. Doklady Mathematics 99(2), 125–128 (2019) https://doi.org/10.1134/S1064562419020042
  18. [18]Drori, Y., Taylor, A.B.: Efficient first-order methods for convex minimization: a constructive approach. Mathematical Programming 184(1-2), 183–220 (2020) https://doi.org/10.1007/s10107-019-01410-2
  19. [19]Zibulevsky, M., Elad, M.: L1-L2 optimization in signal and image processing. IEEE Signal Processing Magazine 27(3), 76–88 (2010) https://doi.org/10.1109/MSP.2010.936023
  20. [20]Kuruzov, I.A., Stonyakin, F.S.: Sequential subspace optimization for quasiconvex optimization problems with inexact gradient. In: Olenev, N.N., Evtushenko, Y.G., Jácimović, M., Khachay, M., Malkova, V. (eds.) Advances in Optimization and Applications (OPTIMA 2021). Communications in Computer and Information Science, pp. 19–33. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-92711-0_2
  21. [21]Karimi, S., Vavasis, S.A.: Nonlinear conjugate gradient for smooth convex functions. Mathematical Programming Computation 16(2), 229–254 (2024) https://doi.org/10.1007/s12532-024-00254-y
  22. [22]Nesterov, Y., Florea, M.I.: Gradient methods with memory. Optimization Methods and Software 37(3), 936–953 (2022) https://doi.org/10.1080/10556788.2020.1858831
  23. [23]Lee, C.-p., Wang, P.-W., Lin, C.-J.: Limited-memory common-directions method for large-scale optimization: convergence, parallelization, and distributed optimization. Mathematical Programming Computation 14, 543–591 (2022) https://doi.org/10.1007/s12532-022-00219-z
  24. [24]Tupitsa, N.: CaCuTe meets SESOP: better theory and practice with Lipschitz Hessians. arXiv preprint arXiv:2610.06557 (2026)arxiv.org/abs/2610.06557
  25. [25]Nemirovskii, A.S., Nesterov, Y.E.: Optimal methods of smooth convex minimization. USSR Computational Mathematics and Mathematical Physics 25(2), 21–30 (1985) https://doi.org/10.1016/0041-5553(85)90100-4
  26. [26]Nesterov, Y.: Gradient methods for minimizing composite functions. Mathematical Programming 140(1), 125–161 (2013) https://doi.org/10.1007/s10107-012-0629-5
  27. [27]Lin, Q., Xiao, L.: An adaptive accelerated proximal gradient method and its homotopy continuation for sparse optimization. Computational Optimization and Applications 60(3), 633–674 (2015) https://doi.org/10.1007/s10589-014-9694-4
  28. [28]Malitsky, Y., Mishchenko, K.: Adaptive gradient descent without descent. In: Proceedings of the 37th International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 119, pp. 6702–6712 (2020)arxiv.org/abs/1910.09529
  29. [29]d’Aspremont, A., Scieur, D., Taylor, A.: Acceleration methods. Foundations and Trends in Optimization 5(1-2), 1–245 (2021) https://doi.org/10.1561/2400000036
  30. [30]Cavalcanti, J.V., Lessard, L., Wilson, A.C.: Adaptive acceleration without strong convexity priors or restarts. arXiv:2506.13033 (2025)arxiv.org/abs/2506.13033
  31. [31]Lan, G., Ouyang, Y., Zhang, Z.: Optimal and parameter-free gradient minimization methods for convex and nonconvex optimization. Mathematical Programming (2026) https://doi.org/10.1007/s10107-026-02352-2
  32. [32]Nemirovski, A.S.: Some results of the theory of optimization problems complexity. Appendix in: Nesterov, Y.E.: Effective Methods in Nonlinear Programming, pp. 272–287. Radio i Svyaz, Moscow (1989). In Russian
  33. [33]Arjevani, Y., Shamir, O.: On the iteration complexity of oblivious first-order optimization algorithms. In: Proceedings of the 33rd International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 48, pp. 908–916 (2016)
  34. [34]Taylor, A.B., Hendrickx, J.M., Glineur, F.: Smooth strongly convex interpolation and exact worst-case performance of first-order methods. Mathematical Programming 161(1-2), 307–345 (2017) https://doi.org/10.1007/s10107-016-1009-3
  35. [35]Drori, Y., Teboulle, M.: Performance of first-order methods for smooth convex minimization: a novel approach. Mathematical Programming 145(1-2), 451–482 (2014) https://doi.org/10.1007/s10107-013-0653-0
  36. [36]de Klerk, E., Glineur, F., Taylor, A.B.: On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions. Optimization Letters 11(7), 1185–1199 (2017) https://doi.org/10.1007/s11590-016-1087-4
  37. [37]Nocedal, J., Wright, S.J.: Numerical Optimization, 2nd edn. Springer Series in Operations Research and Financial Engineering. Springer, New York (2006). https://doi.org/10.1007/978-0-387-40065-5
  38. [38]Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis. Grundlehren der mathematischen Wissenschaften, vol. 317. Springer, Berlin (1998)DOI
  39. [39]Finn, R.: Equilibrium Capillary Surfaces. Grundlehren der mathematischen Wissenschaften, vol. 284. Springer, New York (1986)DOI
  40. [40]Liu, D.C., Nocedal, J.: On the limited memory BFGS method for large scale optimization. Mathematical Programming 45(1-3), 503–528 (1989) https://doi.org/10.1007/BF01589116

Paper details

vlnc:W_pvpc44h4
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 3

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Claude

View statement
Looking for related papers…
Contents