acceptodds
Under review as a conference paper at ICLR 2027

How Much Coordinate Coupling Can Cautious Momentum Tolerate?

Abstract

Cautious momentum suppresses coordinate updates unless the new momentum and current gradient have the same nonzero sign, while retaining the updated momentum buffer. We study the raw, unnormalized rule on time-varying quadratic objectives with a common minimizer, diagonal curvature ratio , and relative off-diagonal coupling strength . For a fixed tuning and zero initial momentum, we prove that the method reaches relative Euclidean error within gradient evaluations under coupling . This bound is independent of dimension and counts evaluations with suppressed updates. It improves on the optimal worst-case bound of gradient evaluations for linear methods with predetermined coefficients. Conversely, for sufficiently large and , we construct a predetermined Hessian sequence for which the same method diverges from a suitable initial point with zero momentum. The convergence and divergence bounds use explicit universal constants that differ by only a factor of about . Thus we characterize, up to constant factors, the robustness threshold for accelerated convergence of cautious momentum as . The proofs use a piecewise quadratic Lyapunov argument for convergence and an explicit construction for divergence.

Primary area:
optimization
Keywords:
cautious momentum, momentum methods, accelerated optimization, optimization stability, coordinate coupling, time-varying quadratics, Lyapunov analysis

Reviews

Among:
Shape:
1234this paper, Top 17%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.75 over 4 reviews, above 83% of the others.
Reviewer_2AQKOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The paper studies a simple cautious momentum rule, where a coordinate only updates when momentum and gradient agree in sign. It analyzes quadratic problems whose Hessian can change over time. The paper shows that the method converges at an accelerated rate when the off-diagonal coupling between coordinates is small, gives an example where slightly larger coupling makes it diverge, and shows that standard momentum methods with fixed schedules cannot achieve the same acceleration in this setting.

A caveat for my review: My expertise in optimization theory is limited. I read the main text and skimmed the appendices, but have not verified the proofs and am likely missing relevant prior work. My comments are mostly about scope, presentation, and what evidence would make the claims more convincing. I defer to other reviewers on technical novelty and correctness.

Critical strengths

(1). The central question is clearly posed and the answer is clear, with matching upper and lower bounds up to a constant of about 2.

(2). The divergence example is concrete and fixed in advance, which makes it convincing.

(3). The paper clearly states its limits: one fixed tuning, gap between the bounds, and that practical cautious optimizers differ from the one analyzed here.

(4). I found it to be clearly written for a theory paper, with some useful intuition in Section 3.

Critical weaknesses

(1). No experiments. A small simulation could help show that the result makes a difference in a realistic setting.

(2). The setting is narrow, with unnormalized rule, exact gradients, quadratics, and a single fixed tuning. The connection to cautious optimizers that are actually used is not clear.

(3). The comparison focuses on momentum methods with pre-set schedules, but it would be interesting to compare to methods that adapt.

Questions for authors

(1). The divergence construction uses a specially designed Hessian sequence. Have you examined whether a single fixed quadratic with coupling of similar order can also cause divergence? You say that this is open in Section 6: have you tried it numerically?

(2). The acceleration claim is relative to momentum methods with pre-set schedules. How does cautious momentum compare to methods that are adaptive, on the same diagonal problems?

1 comment
AuthorsOpenReview ↗

Response to Reviewer 2AQK

Thank you for the helpful questions and comments on the scope and presentation. We have added numerical experiments to examine fixed quadratics, illustrate the divergence construction, and compare cautious momentum with an adaptive method.

We have also expanded the explanations to make the arguments easier to follow. Section 4.2 and Appendix A.2 now describe how successive phases reduce the error, how both position and momentum become small, and how this leads to contraction over a block of iterations. Section 5 and Appendix B.1 now explain what each stage of the growing scalar cycle does and how we construct Hessians that produce the required gradients. We hope these explanations, together with the new numerical illustrations, make the connection between the intermediate steps and the main results clearer.

Q1: Can a single fixed quadratic cause divergence?

We do not know yet. We tested randomly generated fixed positive-definite Hessians, used differential evolution to search over Hessians and initial points for growing trajectories, and tested each Hessian from our periodic divergence construction while holding it fixed throughout the run. None of these tests showed continued growth over the simulated horizons. Appendix D.1 now describes the search methods and results.

So we would say these results suggest the fixed-Hessian question is still open.

Q2: How does cautious momentum compare with adaptive methods on diagonal problems?

We added a comparison with gradient-restarted Nesterov acceleration, which decides when to reset momentum using the observed gradients. This method falls outside the predetermined linear class covered by Theorem C.3.

On the diagonal problems, the comparison is mixed. Appendix D.2 tests two families of time-varying curvature: log-uniform, where curvatures vary across a broad logarithmic range, and sparse-spike, where they are usually small with occasional larger spikes. The median gradient-call counts from Table 2 are:

\text{Diagonal curvature family} & \text{Cautious momentum} & \text{Restarted NAG} \\\\ \hline \text{Log-uniform} & 15{,}431.5 & 7{,}945.5 \\\\ \text{Sparse-spike} & 15{,}431.5 & 35{,}457.5 \end{array}$$ Here, the equal numbers for CM in the diagonal-family column are not wrong (we actually checked the code and ran twice). We think it has a simple explanation. For each seed, the coordinate with curvature $\mu$ has the same initial value and follows the same CM trajectory in both families. Our coordinatewise checks show that this coordinate determines the final error-threshold crossing in all 20 seeds of each family. The interior curvatures and early trajectories differ, but the other coordinates contribute negligibly. We can see that restarted NAG is faster on all 20 log-uniform instances, while cautious momentum is faster on all 20 sparse-spike instances. These experiments use $d=32$ and $\kappa=10^5$. We select baseline parameters on separate validation seeds, and all methods use the same Hessian sequence and initial point on each test seed. We count every gradient call, including rejected cautious-momentum updates. The reported count is the first call after which relative error remains at most $10^{-6}$ through the rest of the observed run, with a budget of 600,000 calls. Appendix D.2 also reports comparisons with GD, heavy-ball, and ordinary NAG. We then added weak coupling to the same two families, with $\rho=373/(2000\sqrt\kappa)$, within the convergence regime of Theorem 2.1(i). Here cautious momentum is faster than restarted NAG on 19 of 20 seeds in each family (see Table 3). These experiments show that the advantage can be visible on concrete examples, including against an adaptive baseline. But the diagonal results also show that cautious momentum does not always win. And our theoretical separation remains specific to methods with predetermined coefficients. Regarding your concern about the narrow setting, we study the raw rule to understand how the sign gate interacts with retained momentum and coordinate coupling. We have also added two direct extensions based on suggestions from other reviewers: Corollary A.10 establishes accelerated convergence for a one-parameter family of step-size and momentum choices, with corresponding coupling bounds, and Corollary A.11 covers $C^2$ objectives with a common minimizer and the same uniform Hessian bounds. These extensions still use exact gradients and the raw update. Remark 4.3 explains which estimates need additional work for stochastic gradients and time-varying normalization.
Reviewer_QgkuOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies raw cautious momentum on time-varying strongly convex quadratics sharing a minimizer. For a prescribed tuning, it proves a dimension-independent accelerated rate when relative coordinate coupling is below 0.1865/κ0.1865/\sqrt{\kappa}, counting all gradient calls, including rejected updates. For sufficiently large κ\kappa, a predetermined Hessian sequence causes divergence at coupling below 0.4/κ0.4/\sqrt{\kappa}. Together, these results determine the coupling tolerance up to constant factors. The paper also establishes the exact worst-case rate of linear methods with predetermined coefficients under time-varying diagonal curvature. No numerical experiments are provided.

Critical strengths
  1. Theorem 2.1 identifies the coupling tolerance up to constant factors. Under the same tuning, the convergence guarantee and divergence construction have the same dependence on κ\kappa. This clarifies how the gate tolerates sign errors, yet can fail through their repeated interaction with retained momentum.

  2. The analysis addresses several important details. The convergence proof counts gradient calls during rejected updates, and Equation (4.9) allows coordinatewise disturbances to peak at different times (lines 326–344). Appendix B.3 reaches an unstable trajectory from zero momentum using admissible diagonal updates, followed by a predetermined, eventually periodic Hessian sequence. I found no substantial mathematical errors in the arguments checked.

Critical weaknesses
  1. The model has limited scope as an explanation of practical cautious optimizers. The analysis assumes strongly convex quadratics with a common minimizer and uniformly bounded diagonal curvature, and guarantees acceleration only for coupling of order 1/κ1/\sqrt{\kappa}. It does not cover nonconvex training or stochastic gradients with persistent noise at the optimum. Removing mask normalization and second-moment adaptation further limits applicability: normalization can substantially increase the effective step size when few coordinates are accepted. Moreover, divergence under a varying Hessian does not establish instability on a fixed objective.

    A numerical illustration would also help. The construction requires sufficiently large κ\kappa but gives no explicit cutoff. Please provide an admissible instance, its coupling norm, and the resulting trajectory.

  2. The linear-method separation is informative but restricted. It concerns methods with predetermined coefficients. Even at ρ=0\rho=0, nonlinear methods such as coordinatewise bisection can converge rapidly. I therefore view this as a separation between specific algorithm classes and give it less weight than the coupling-threshold theorem.

Questions for authors
  1. How essential is the unnormalized mask to Theorem 2.1? Please identify where the convergence proof relies on this assumption and clarify the relevance of the result to the normalized variants mentioned in lines 479–482.

  2. Could the authors give one explicit parameter choice for which the full divergence construction works from zero momentum, including the 100-call preparation? Please report the condition number, the actual relative coupling norm, and a plot of the resulting trajectory.

  3. How essential is the quadratic assumption to the convergence result? Since the analysis allows arbitrary changes in the Hessian, can the guarantee also cover nonquadratic strongly convex functions under analogous Hessian bounds? Please clarify the scope of the result.

  4. How sensitive is the divergence construction to the initialization and the prescribed Hessian sequence? I would like to see a concrete numerical instance and whether the divergent behavior persists under small perturbations.

4 comments
AuthorsOpenReview ↗

Response to Reviewer Qgku (Part 1: Normalization and Divergence)

Thank you for the careful reading and helpful suggestions. We have added a nonquadratic extension and numerical experiments, including the explicit divergence example and perturbation tests you requested.

We also agree with your point about the theoretical linear-method comparison. Theorem C.3 establishes a separation between specific algorithm classes instead of optimality over arbitrary adaptive or nonlinear methods. Appendix D.2 now includes numerical comparisons with gradient-restarted NAG. The results are mixed on the diagonal families, but CM is faster on 19 of 20 seeds in each coupled family.

Q1: How essential is the unnormalized mask?

At a given state, positive normalization keeps the gate decision unchanged but changes how far the accepted coordinates move. In the scaled variables of Eq. (4.2), an accepted raw update gives (x+,y+)=(x−p,p)(x^+,y^+)=(x-p,p), but normalization gives (x+,y+)=(x−ctp,p)(x^+,y^+)=(x-c_tp,p).

If ct=c>0c_t=c>0 is constant, we can absorb it into the step size. The method is then equivalent to raw cautious momentum with step size cηc\eta, and our guarantee applies whenever this effective step size and the momentum parameter satisfy the required tuning. For time-varying normalization, however, two parts of the proof need further work:

  1. The Lyapunov estimate. Eq. (A.3) expands the change in the Lyapunov function using the accepted displacement pp. Replacing x−px-p by x−ctpx-c_tp changes both the coefficients and the conditions determining which branch of the Lyapunov function applies. The perturbation estimate in Eq. (4.4) thus needs to be re-established.

  2. The overshoot estimate. Lemma A.5, particularly Eq. (A.20), uses the accepted displacement pp to relate momentum accumulation to distance traveled. This controls the overshoot and gives the contraction between phases in Eq. (A.19). Changing the displacement to ctpc_tp changes this argument as well.

As you point out, normalization can substantially enlarge a step when few coordinates are accepted. So preserving the gate decision at one state does not preserve the later trajectory. Extending the guarantee would require control of the normalization factors and corresponding changes to the tuning and estimates above.

We added this discussion in Remark 4.3, which also explains the additional terms introduced by stochastic gradient noise. Our current result isolates the interaction between the gate, retained momentum, and coupling.

Q2: An explicit divergence example from zero momentum.

Yes. Appendix D.1 now gives a numerical realization with d=14d=14, μ=10−9\mu=10^{-9}, L=1L=1, and hence κ=109\kappa=10^9. We use the prescribed tuning in Eq. (2.3) and start from zero momentum.

The initial point and first 100 diagonal Hessians are chosen as in Appendix B.3. These calls bring the method to the required starting state, after which we apply the predetermined 14-periodic Hessian sequence from Appendix B.2. All Hessians satisfy the diagonal bounds, and their actual relative coupling is

=\max_{t\ge0}\left\\|D_t^{-1/2}F_tD_t^{-1/2}\right\\|_{\mathrm{op}} \approx1.2632\times10^{-5} <\frac{2}{5\sqrt\kappa}.$$ Figure 4 shows the preparation and the following 1,000 periods. The trajectory agrees with the predicted growth factor of approximately $1.0064311$ per period. After 1,000 periods, the error norm is approximately $608.2$ times its value immediately after preparation. Regarding your concern about fixed objectives, Appendix D.1 also reports numerical searches for divergence on fixed quadratics. None showed continued growth. So we think whether a fixed Hessian can cause divergence at the same coupling scale remains open.
AuthorsOpenReview ↗

Response to Reviewer Qgku (Part 2: Extensions and Robustness)

Q3: Can the convergence guarantee extend beyond quadratics?

Yes. As you suggest, the argument only needs the gradient at each iterate to have the form Ht(xt−x⋆)H_t(x_t-x^\star) with an admissible HtH_t. We added Corollary A.11 to state this simple extension for C2C^2 objectives with a common minimizer and Hessians satisfying Eq. (2.1) uniformly.

The proof follows directly from

\qquad \overline H_t =\int_0^1\nabla^2f_t\bigl(x^\star+s(x_t-x^\star)\bigr)\\,ds.$$ This average preserves the diagonal curvature bounds. It also preserves the relative coupling bound, since that condition can be written as $-\rho D\preceq F\preceq\rho D$ and then integrated along the segment. The same convergence proof therefore applies. The coupling assumption is still necessary for this argument: strong convexity alone does not provide the bound used in Eq. (4.6). **Q4: How sensitive is the construction to initialization and the Hessian sequence?** We tested both types of perturbation on the example in Q2. Each run includes the 100 preparation calls followed by 1,000 periods. **Initialization.** We perturb the original initial point as $$\widetilde x_0=x_0+\epsilon\\|x_0\\|_2u,$$ where $u$ is a normalized Gaussian vector. We use the same 32 directions at each of five perturbation sizes, while keeping zero initial momentum and the entire Hessian sequence unchanged. Figure 5 shows the results. **Hessian sequence.** We keep the initial point and preparation unchanged, and perturb each periodic Hessian by $$\widetilde H_j =H_j+\epsilon\rho_{\mathrm{actual}}D_j^{1/2}E_jD_j^{1/2},$$ where $E_j$ is symmetric, has zero diagonal, and has unit operator norm. We use eight seeds per perturbation size and repeat the same perturbed matrices every period. All tested Hessians remain admissible. Figure 6 shows these results. The outcomes are: $$\begin{array}{lll} \text{Perturbation} & \text{Sizes }\epsilon & \text{Observed behavior} \\\\ \hline \text{Initial point} & 10^{-12},10^{-10},10^{-8} & \begin{array}{l} \text{All 32 runs at each size preserve the gate} \\\\ \text{decisions and grow at rates close to the} \\\\ \text{original trajectory.} \end{array} \\\\ \text{Initial point} & 10^{-6},10^{-4} & \begin{array}{l} \text{All runs change at least one gate decision} \\\\ \text{and none has a positive log-norm slope} \\\\ \text{over the final 500 periods.} \end{array} \\\\ \text{Periodic Hessians} & 10^{-12},10^{-10},10^{-8},10^{-6} & \begin{array}{l} \text{All eight runs at each size preserve the} \\\\ \text{gate decisions and retain the observed} \\\\ \text{growth.} \end{array} \\\\ \text{Periodic Hessians} & 10^{-4} & \begin{array}{l} \text{All eight runs change a gate decision on} \\\\ \text{the first call after preparation; seven have} \\\\ \text{negative slopes and one is nearly flat.} \end{array} \end{array}$$ So the observed growth survives the smaller perturbations we tested, but is sensitive to larger ones. This is consistent with the strict gate inequalities in the scalar construction of Lemma B.1: sufficiently small perturbations can preserve the gate pattern over a fixed finite horizon. Larger perturbations can change the cancellations in Eq. (5.5) and the resulting gate decisions. Appendix D.1 now discusses this distinction.

The response addresses some of my concerns. The numerical example and perturbation tests make the divergence construction easier to assess, and Corollary A.11 shows that the convergence guarantee extends beyond quadratics under the stated Hessian bounds.

My concern about scope remains: the guarantee only covers the unnormalized update, and it is still unclear whether similar divergence can occur on a fixed objective. Addressing these limitations would require further work, and I have no further questions for this round.

On balance, the new results and experiments are enough for me to raise my rating from 2 to 3 (weak acceptance).

Thank you for the careful reading and constructive discussion! Your suggestions helped us clarify the scope of the results and strengthen the numerical evidence. We agree that normalized updates and divergence on fixed objectives remain important questions for future work.

Reviewer_HuuQOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies how coordinate coupling affects the convergence rate and optimization dynamics of cautious momentum, a method proposed by [1] which updates coordinates only when the current gradient and updated momentum have the same nonzero sign. The authors study this optimization procedure on time-varying quadratic objectives sharing a common minimizer. For a fixed choice of step size and momentum, the authors establish a dimension-independent convergence bound of O(κlog⁡(2+κ)log⁡(1/ϵ))\mathcal{O} \left( \sqrt{\kappa} \log(2 + \kappa) \log(1/\epsilon) \right) gradient evaluations when the relative off-diagonal coupling ρ\rho is order O(κ−1/2)\mathcal{O}(\kappa^{-1/2}) where κ\kappa is the “diagonal curvature ratio” (diagonal condition number). Additionally, the authors construct a setting with time-varying positive-definite Hessians for which cautious momentum diverges when the coordinate coupling is sufficiently large, illustrating that coordinate coupling strength plays a large role in the improved convergence rate and dynamics of cautious momentum methods. The authors also show that cautious momentum achieves an improved dependence in κ\kappa compared with standard accelerated linear gradient methods (e.g., Polyak heavy-ball and Nesterov acceleration), or more generally any linear optimization method with coefficients fixed in advance and independent of the observed gradients, under time-varying diagonal Hessians.

[1] Liang, K., Chen, L., Liu, B., & Liu, Q. (2026, April). Cautious optimizers: Improving training with one line of code. In International Conference on Learning Representations (Vol. 2026, pp. 106538-106563).

Critical strengths
  1. Generally, I find the question of how coordinate coupling affects the convergence of cautious momentum to be interesting. Given that cautious optimizers were introduced relatively recently, their implementation simplicity, and the promising theoretical guarantees and practical speedups demonstrated in LLM pretraining and post-training tasks, I find studying the behavior and limitations of this optimizer to be well motivated.

  2. The authors establish a dimension-independent convergence bound of O(κlog⁡(2+κ)log⁡(1/ϵ))\mathcal{O} \left( \sqrt{\kappa} \log(2 + \kappa) \log(1/\epsilon) \right) gradient evaluations when the relative off-diagonal coupling ρ\rho is sufficiently small, of order O(κ−1/2)\mathcal{O}(\kappa^{-1/2}). They further establish that this represents an improvement in the dependence on κ\kappa compared with standard accelerated linear gradient methods. Additionally, the authors construct an example showing that cautious momentum can diverge when ρ\rho is sufficiently large, of order Ω(κ−1/2)\Omega(\kappa^{-1/2}). This illustrates that coordinate coupling strength plays a large role in the improved convergence rate and stability of cautious momentum methods.

Critical weaknesses

W1. The accelerated convergence and divergence guarantees are only established for a specific choice of step size and momentum i.e. η=1/(16L)\eta = 1/(16L) and β=1−1/(4κ)\beta = 1 - 1/(4\sqrt{\kappa}). Therefore, one can only expect provable acceleration and divergence with ρ=Θ(κ−1/2)\rho = \Theta(\kappa^{-1/2}) provided this specific tuning, and it is unclear whether a different choice of parameters could tolerate substantially stronger coupling while retaining acceleration. Additionally, the analysis is restricted to a particular setting with time-varying positive-definite quadratic objectives with access to exact gradients. Although I understand that these assumptions make the theoretical analysis more tractable, they limit the generality of the results, particularly in stochastic optimization settings or more practical implementations of cautious optimizers involving normalization and adaptive preconditioning.

W2. Although the main results are understandable and the proofs generally appear correct, I do not believe the current technical writing is sufficiently clear for a paper whose main contribution is theoretical. For example, the scalar contraction argument in Appendix A.2 involves a sequence of phase definitions and region arguments and similarly the divergence construction in Appendix B involves a highly specific scalar trajectory and several subsequent construction steps. Although the authors try to provide a roadmap and I generally understand that the accelerated convergence rate follows from a specific Lyapunov potential construction that results in a one step decrease alongside a construction which allows one to obtain the required contraction, I found it difficult to extract the main ideas from the detailed calculations and understand which choices are essential to the arguments. I would have expected the authors to spend more time explaining the proof mechanisms, motivating the intermediate results, and illustrating how these results fit together.

Questions for authors

Q1. How sensitive is the coupling threshold ρ=Θ(κ−1/2)\rho = \Theta(\kappa^{-1/2}) to the specific choices of step size and momentum? Could different parameter choices tolerate stronger coupling while retaining acceleration?

Q2. Can the authors provide a more intuitive explanation of the scalar contraction argument in Appendix A.2 and the divergence construction in Appendix B, particularly how the intermediate constructions lead to the main theoretical results?

Q3. How do the results relate to the existing literature on momentum methods in nonstationary optimization [1, 2, 3]? Could the proposed techniques be extended to more general nonstationary or stochastic optimization settings?

The first two questions will materially affect my assessment whereas the last question is just to understand from the authors' perspective if one can easily extend these results to more general settings.

[1] Cutler, J., Drusvyatskiy, D., & Harchaoui, Z. (2021). Stochastic optimization under distributional drift. arXiv preprint arXiv:2108.07356.

[2] Sahu, S., Hogan, C. J., & Wells, M. T. (2026). On the provable suboptimality of momentum sgd in nonstationary stochastic optimization. arXiv preprint arXiv:2601.12238.

[3] Sahu, S., Sarkar, A., Hogan, C. J., & Wells, M. T. (2026). Adapt or forget: Provable tradeoffs between adam and sgd in nonstationary optimization. arXiv preprint arXiv:2605.04269.

5 comments
AuthorsOpenReview ↗

Response to Reviewer HuuQ (Part 1: Tuning and Coupling)

Thank you for the careful reading and for highlighting tuning sensitivity and proof intuition as the main concerns. We agree that the original version needed to explain more clearly why the intermediate steps are needed and how they lead to the main results.

We have expanded the explanations in Section 4.2 and Appendix A.2 to describe the scalar trajectory geometrically: how successive phases reduce the position error, how both position and momentum become small, and why they remain controlled until the end of the block. Appendix A.2 now also includes a proof guide that connects these steps. We also summarize the main results of each subsubsection in Appendix A.2 as lemmas to make the proof easier to follow. In Section 5 and Appendix B.1, we explain what each stage of the growing scalar cycle does, how its initial state is chosen, and how coupling allows us to construct Hessians that produce the desired trajectory.

We give a more detailed explanation of these ideas in our response to Q2 below. We have also added a theoretical extension and numerical experiments on alternative tunings, which we discuss in Q1.

Q1: Sensitivity to tuning and stronger coupling.

We think a better constant in the coupling tolerance may be possible. The current constant comes from the Lyapunov coefficients in Eqs. (A.1)–(A.2) and the sufficient condition for positive decrease in Eq. (A.12). There are several places where we could try to sharpen the argument. For example, choosing different Lyapunov coefficients, or balancing these estimates for another step size and momentum could improve the guaranteed constant.

There is also room to consider changes in η\eta and β\beta independently. They play different roles in the scaled dynamics in Eq. (4.1): η\eta determines the curvature interval [ημ,ηL][\eta\mu,\eta L], and r=1−βr=1-\beta controls momentum decay. The upper curvature bound controls momentum accumulation and overshoot in Lemma A.5. The lower curvature bound and damping help control how long a phase lasts in Lemma A.7. Our prescribed tuning makes ημ=r2\eta\mu=r^2, which simplifies these estimates. We leave a more general characterization of this range for future work.

A simple family of alternative tunings already follows from our main theorem. We added Corollary A.10, which shows that, for any fixed c∈(0,1]c\in(0,1] independent of κ\kappa, the choices

\qquad \beta=1-\frac{\sqrt c}{4\sqrt\kappa}$$ retain the accelerated order whenever $$\rho\le\frac{373\sqrt c}{2000\sqrt\kappa}.$$ This follows by applying Theorem 2.1(i) directly with the relaxed curvature upper bound $L/c$. It shows that the guarantee is not restricted to one exact tuning, although this particular family does not enlarge the guaranteed coupling range. Improving the order of the tolerance is a harder question. For the current tuning, the $\kappa^{-1/2}$ scale arises naturally in the Lyapunov decrease. Combining Eqs. (4.5) and (4.6), the proof of Lemma 4.1 gives $$V_{t+1}-V_t \le-[c_0-Q(r)\rho^2]B_t,$$ where $Q(r)=J/r^2+1$ is the perturbation coefficient from Lemma A.3. Thus, $$Q(r)\rho^2=(J+r^2)\left(\frac{\rho}{r}\right)^2.$$ To keep a uniform positive decrease, Eq. (A.12) requires $\rho/r$ to be sufficiently small. Since $r=1/(4\sqrt\kappa)$ under Eq. (4.1), this gives the scale $\rho=O(\kappa^{-1/2})$. The divergence construction in Theorem 2.1(ii) shows that this order is sharp for the prescribed tuning. Frankly speaking, whether another tuning can tolerate coupling of a larger order while still guaranteeing uniform acceleration is something we do not know at the moment. As a first step toward understanding the independent parameter choices discussed above, we tested whether the observed acceleration persists when we change the step size, the momentum, or both. Appendix D.3 compares the prescribed tuning with a doubled step size, stronger momentum damping, and both changes together. We fix $\rho=1/\sqrt\kappa$ and vary $\kappa$ from $10^2$ to $10^5$. All 200 runs reached relative error $10^{-6}$ and stayed below it through the remainder of the observed run. Doubling the step size generally reduced the median gradient-call count, while increasing damping alone increased it. Changing both generally gave the lowest median counts. Overall, the counts showed roughly $\sqrt{\kappa}$ order. So, on these examples, changing the parameters independently preserves the observed accelerated behavior and can improve convergence speed. This gives some numerical support for exploring a broader tuning region. Remark 2.2 now summarizes the theoretical extension and the numerical investigation.
AuthorsOpenReview ↗

Response to Reviewer HuuQ (Part 2: Convergence Proof)

Q2: Intuition behind the convergence proof and divergence construction.

Why we have convergence under small coupling. The diagonal case in Section 3 gives the starting intuition: the gradient has the same sign as the coordinate error, so the gate accepts movement toward the minimizer but blocks further outward movement after an overshoot. The momentum continues to update while the position is held fixed, and movement resumes once the momentum points back toward the minimizer.

Coupling disrupts this mechanism because a gradient coordinate can now have the opposite sign to its error. To understand the resulting trajectory, we first study a scalar gradient of the form ht=at(xt+et)h_t=a_t(x_t+e_t) with ∣et∣≤E|e_t|\le E. We can think of this as allowing the zero of the gradient to move within [−E,E][-E,E]. If xtx_t is outside this interval, the gradient still has the same sign as the position, so the gate still blocks continued outward movement after an overshoot beyond the interval.

We follow the trajectory through "momentum phases", during which the updated momentum keeps the same sign, so the position moves monotonically. At the start of a full phase, the gradient has just flipped the sign of the momentum, so the new momentum cannot be larger than the gradient. As the position moves toward zero, momentum accumulates, but the curvature bound and the distance traveled limit how much can accumulate. This limits the overshoot and makes the next full phase start closer to zero: Xnext≤12X+32E,X_{\mathrm{next}}\le \frac12X+\frac32E, where XX is the position magnitude at the start of the current full phase (see Eq. (4.9)). Thus, successive full phases make the position closer to zero, up to a residual error proportional to EE.

The next task is to turn this contraction between phases into a bound on gradient calls. We seek a small box in the position–momentum space where both quantities are small. Within a phase, the position is monotone: for positive momentum, it moves from right to left and can visit each position region only once. We bound the time spent in these regions, including calls with rejected updates. Within a bounded number of calls, the trajectory thus either enters the box or starts another full phase. If it has not entered the box, the next phase gives another reduction in position magnitude. Eventually the phase-entry position is small enough, and the momentum is also small because it is bounded by the gradient at the start of that phase.

Entering the box is not quite enough since different coordinates may enter at different times, but we need a contraction estimate at one common block endpoint. We thus also prove the following bound max⁡∣xt∣,∣yt∣≤∣x0∣+∣y0∣+3E,\max\\{|x_t|,|y_t|\\}\le |x_0|+|y_0|+3E, which allows arbitrary incoming momentum (see Eq. (4.10)). Applying this bound again from the first small-box entry time keeps both quantities small for the rest of the block, even if the trajectory leaves the original box. This gives Lemma 4.2: after N(r)=O(r−1log⁡(2/r))N(r)=O(r^{-1}\log(2/r)) calls, the scalar Lyapunov function contracts by a factor of 1/41/4, up to a residual CEE2C_EE^2.

Finally, the coordinate perturbations come from coupling, so we must control these residuals together. This is where small coupling matters. In Lemma 4.1, the total Lyapunov function satisfies

\le -[c_0-Q(r)\rho^2]B_t \le -\delta B_t,$$ where $B_t$ is the weighted squared error. Since $Q(r)=O(r^{-2})$, keeping $\rho/r$ sufficiently small gives a uniform positive margin $\delta$ above. Eq. (4.11) then bounds the accumulated coordinate perturbations by the Lyapunov decrease over the block. Combining this with scalar contraction gives $$V_{\tau+N} \le \frac14V_\tau +A_\rho(V_\tau-V_{\tau+N}), \qquad A_\rho=\frac{C_E\rho^2}{\delta r^2}.$$ The coupling condition keeps $A_\rho$ bounded independently of $\kappa$ and dimension. Rearranging therefore gives a uniform contraction factor $$\frac{A_\rho+1/4}{A_\rho+1}<1.$$ Repeating these blocks gives the accelerated rate. We have expanded the explanation in Section 4.2 and added the geometric description and a clear five-step proof guide in Appendix A.2.
AuthorsOpenReview ↗

Response to Reviewer HuuQ (Part 3: Divergence and Extensions)

Why we might have divergence under strong coupling. With sufficiently strong coupling, we can keep the gradient aligned with the momentum after a coordinate crosses zero, so the gate accepts further steps away from the minimizer. We first prescribe a fourteen-call scalar cycle. 3 rejected calls hold the position fixed while correcting the initial negative momentum. The next 5 calls build positive momentum while moving toward zero, and 2 calls with small curvature carry the position across zero. During the final 4 calls, x<0<yx<0<y, and we let

\qquad p=(\beta+r^3)y>0.$$ The positive gradient keeps the gate open, and the retained momentum provides most of the movement away from zero. We choose the initial state so that the cycle ends at $$z_{14}=-g(r)z_0,\qquad g(r)>1.$$ Both position and momentum reverse sign and grow by the same factor, so the same motion can repeat on the opposite side with increasing amplitude. The remaining question is how to produce these prescribed gradients using actual Hessians. The gradients $a_\circ x$ and $r^2x$ already have the form generated by positive diagonal curvature (since they are linear). The final gradients $r^3y$ do not: they have the opposite sign to $x$. These are the steps where we need coupling. We place fourteen scaled copies of the scalar trajectory, each at a different stage of the cycle, into one vector. At every call, some coordinates thus need the ordinary diagonal gradients, while others need the sign-reversed gradients. We initially assign the corresponding diagonal coefficients. For the coordinates requiring $r^3y$, the diagonal contribution is $r^2x$, so coupling must provide exactly $$r^3y-r^2x.$$ We can get this correction by coupling the coordinates that need gradients $r^3y$ to those whose prescribed gradients are $a_\circ x$, using the off-diagonal Hessian entries in Eq. (5.3). The coupling also changes the gradients of the coordinates we used to provide the correction, since the Hessian has to be symmetric. Here, the extra term is just $cx_i$, with the same $c$ for all of these coordinates. So we subtract $c$ from their diagonal entries to cancel it (Eq. (5.4)). We then get exactly the gradients we wanted in every coordinate. So once we have the scalar cycle, we can build Hessians that produce the desired trajectory. We then check the diagonal and coupling bounds in Appendix B.2. To start from zero momentum, we first use 100 calls with diagonal Hessians to reach the state needed for the cycle (Appendix B.3). We have also added more explanation in Section 5 and Appendix B.1 about what each stage of the scalar cycle does and how we choose the initial state so that the error grows each time the cycle repeats. **Q3: Relation to nonstationary optimization and possible extensions.** Thank you for pointing us to these papers. Cutler et al. (2023) and Sahu et al. (2026a,b) study how objective drift and gradient noise affect optimization, including the difficulty of tracking a moving minimizer. Our setting keeps the minimizer fixed and uses exact gradients, but allows the Hessian to change arbitrarily. This lets us ask what changing curvature alone does to cautious momentum, and how coordinate coupling affects its convergence. We have added this comparison in Section 1.2. Some immediate extensions already follow from our argument based on suggestions from other reviewers. Random Hessians are covered as long as every realization satisfies our assumptions. We also added Corollary A.11 for $C^2$ objectives with a common minimizer and the same uniform Hessian bounds. The reason is simple: the gradient can be written as an averaged Hessian times the error, and this averaged Hessian satisfies the same bounds. The convergence proof then applies directly. With additive gradient noise, the perturbation in our proof becomes $u_t=J_tx_t+\eta\xi_t$. The scalar estimates in Eqs. (4.4) and (4.8) still apply. However, Eq. (4.6) now contains extra terms involving the noise, and we need to control their accumulation over each block to obtain a convergence guarantee. If the minimizer also moves, its movement adds another term to the error recursion. These extensions can build on the same perturbation-based argument, but obtaining convergence would require assumptions controlling the accumulated noise and drift. For the practical variants mentioned in your weakness discussion, time-varying mask normalization changes the accepted displacement, so the Lyapunov and overshoot estimates would need to be re-established. Adaptive preconditioning would also require further analysis. Remark 4.3 now explains what carries over to random Hessians and where additional work is needed for additive noise and normalization.
Reviewer_e1tBOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies cautious momentum on time-varying quadratic objectives with a shared minimizer. It establishes accelerated convergence under sufficiently weak coordinate coupling and a matching-order divergence construction showing the limits of this guarantee. It also proves a worst-case separation from predetermined linear methods in this setting.

Critical strengths
  • Substantial mathematical treatment of cautious momentum, including a dimension-independent convergence guarantee that accounts for rejected updates.
  • The matching-order divergence construction gives a complementary understanding of the limits of the method. Together with the convergence result, it identifies the scale of coordinate coupling at which the guarantee breaks down, rather than providing only a sufficient condition.
  • The paper establishes a genuine worst-case acceleration over predetermined linear methods in its time-varying setting, going beyond one-step comparisons. This provides a theoretical setting in which the cautious momentum update offers a provable advantage.
Critical weaknesses
  • The divergence construction relies on a carefully designed time-varying Hessian sequence, with all quadratics sharing the same minimizer. It is unclear whether similar behavior occurs under more realistic curvature evolution, for example when optimizing a fixed objective. This limits how much the construction tells us about failures of cautious momentum in practice.
  • The constants in the general coupled convergence bound are very large: Appendix A.3 gives a constant of roughly 101110^{11}. While the asymptotic result is meaningful, this makes the bound too conservative to establish a useful speedup at realistic parameter values. The separate diagonal bound is substantially sharper.
  • Another potential weakness is the focus of the work on a very specific optimizer (cautious momentum), in a very particular setting (unnormalized, and under GD) - and combined with the aforementioned non-practicality of the constants in the asymptotic rate, the practical applicability of these results remains extremely limited.
Questions for authors
  • Which parts of the analysis would break when moving toward practical cautious optimizers, in particular with normalization of accepted updates or stochastic gradients (I understand that the second-moment adaptation is beyond the scope)? Do you expect the same acceleration and coupling threshold to persist?
  • Considering the theoretical constants for the asymptotic effects are essentially not very useful from the point of view of practice, do you think there exists empirical evidence for the speedup in realistic settings (maybe on some "reasonable" time-varying quadratics)?
2 comments
AuthorsOpenReview ↗

Response to Reviewer e1tB (Part 1: Practical Variants)

Thank you for the helpful comments. We agree that the connection to practical variants and the meaning of the large theoretical constant need more discussion. We have added clarifications and numerical experiments to address both points.

Q1: What changes with stochastic gradients or normalization?

If the randomness is only in the Hessian, our argument already covers it as long as every realization satisfies our Hessian assumptions. In more realistic cases, where the gradient takes the form g^t=Ht(xt−x⋆)+ξt\widehat g_t=H_t(x_t-x^\star)+\xi_t with additive noise ξt\xi_t, the analysis becomes more complicated but we think it is possible under suitable assumptions on ξt\xi_t. The estimates in Eqs. (4.4) and (4.8) already allow arbitrary gradient perturbations. The only difference is that, in our current analysis, these perturbations come only from coordinate coupling, and in the additive gradient noise case, stochastic gradient noise also contributes here. However, Eq. (4.6) needs to change because utu_t now includes both coupling and gradient noise. In Eqs. (4.5) and (4.6), utu_t becomes Jtxt+ηξtJ_tx_t+\eta\xi_t, so Eq. (4.6) has additional terms involving ξt\xi_t.

To get convergence, we need assumptions on ξt\xi_t. For example, we can assume conditionally unbiased noise with finite moments, where we condition on the history and HtH_t. Unbiasedness removes the cross term between coupling and noise in expectation. Plugging the modified Eq. (4.6) into the argument of Eq. (4.13) then gives a bound of the form EVτ+N≤q∗EVτ+cτ\mathbb{E} V_{\tau+N}\le q_*\mathbb{E} V_\tau+c_\tau, where cτc_\tau depends on the noise over the block. Additional assumptions, such as decay of the noise variance, can then ensure that this extra contribution is small. We think this gives a useful starting point for an extension under suitable noise assumptions.

At a given state, a positive normalization factor preserves the gate decision but changes the accepted displacement from pp to ctpc_tp. If the factor is constant, we can absorb it into the step size, and our guarantee applies whenever the effective step size and momentum satisfy the required tuning. With mask normalization, however, the factor varies with the accepted coordinates and can become large when few coordinates are accepted. Both the one-step Lyapunov estimate and the scalar overshoot bounds use the raw displacement, so these estimates would need to be re-established. Similar acceleration seems plausible with controlled normalization factors and appropriate tuning, but we have to leave it to future analysis as this might require non-trivial analysis and assumptions.

We added this discussion in Remark 4.3. Following suggestions from other reviewers, we also extended the convergence guarantee in two directions: Corollary A.10 shows that accelerated convergence also holds for a one-parameter family of step-size and momentum choices, with a corresponding bound on the allowed coupling, and Corollary A.11 covers C2C^2 objectives with a common minimizer satisfying the same uniform Hessian bounds. Both are direct extensions of our main convergence result and can be proved in a few lines. We keep the raw rule in the main results because it is the simplest setting in which the effect of the gate under coupling can be analyzed.

AuthorsOpenReview ↗

Response to Reviewer e1tB (Part 2: Numerical Results)

Q2: Is there empirical evidence for speedup at concrete parameter values?

Yes, we tested on synthetic time-varying quadratics. We agree that the constant in Appendix A.3 is too conservative to predict practical convergence times, so we added numerical comparisons in Appendix D.2.

We use two curvature families: log-uniform, where curvatures vary across a broad logarithmic range, and sparse-spike, where they are usually small with occasional larger spikes. Both use d=32d=32 and κ=105\kappa=10^5, and we test diagonal and weakly coupled versions. CM uses the prescribed tuning, and parameters of other methods are selected on separate validation seeds. All methods share the same Hessian sequence and initial point on each of the 20 test seeds, and every gradient call is counted, including rejected CM updates.

For the coupled instances, with ρ=373/(2000κ)\rho=373/(2000\sqrt{\kappa}), the median numbers of calls needed to reach and remain below relative error 10−610^{-6} through the rest of the observed run are:

\text{Curvature family} & \text{CM} & \text{Heavy-ball} & \text{NAG} & \text{Restarted NAG} \\\\ \hline \text{Log-uniform} & 15{,}445 & 158{,}220 & 75{,}125.5 & 21{,}180 \\\\ \text{Sparse-spike} & 15{,}354.5 & 228{,}985.5 & 156{,}521 & 57{,}057.5 \end{array}$$ CM is faster than heavy-ball and NAG on every test seed, and faster than restarted NAG on 19 of 20 seeds in each coupled family. On diagonal cases, the comparison with restarting NAG is mixed: restarted NAG is faster on all 20 log-uniform seeds, but CM is faster on all 20 sparse-spike seeds. These results show speedups on simple synthetic time-varying quadratics. Regarding your concern about fixed objectives, we also added numerical searches for divergence on fixed quadratics in Appendix D.1. None showed continued growth. So we would frankly say our divergence construction remains a worst-case result for time-varying Hessians, and whether a fixed Hessian can cause divergence at the same coupling scale is still unknown to us.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.