- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
The paper studies heavy-ball momentum on quadratics when the step size and momentum may change every steps. Those changes are chosen by an adversary among all settings that converge at rate at least . At every change, a fixed fraction of the velocity is kept. The question the authors address is, what is the smallest for which the method converges for every sequence of changes. For a full reset (), Theorem 1 gives an exact condition, . Theorem 2 shows that keeping part of the velocity allows a shorter , and that as the best fraction tends to .
Critical strengths
1. The result on how much velocity to keep is interesting.
Erasing the velocity at every switch and keeping all of it fail for opposite reasons. The first makes the method overshoot again in every block, while the second lets alternating rules build up the error. The paper shows that in the limit these are the only two ways the method can fail, and that keeping the fixed fraction balances them for every margin. It is a simple and elegant answer to a problem that looks complicated at first.
2. The results appear correct.
I checked the proofs of the main results and found no errors.
Critical weaknesses
1. The paper is very hard to read
- Title and abstract. They present the work as a study of restarting, but the main result depends on the optimizer's settings changing adversarially at every block boundary. The abstract never says this, and it only becomes clear in the introduction and Section 2.
- Writing. Many sentences are hard to follow, for example "Exact rational exclusions and independently checked interval certificates establish exact results at finite margins." Such repeated disclaimers keep interrupting the argument and make it necessary to read the same sentence over and over again to understand it.
- Unexplained terms and experiments. Terms such as "commit length," "contract," and "handoff" are not explained when first used. Section 7.3 squeezes four studies into a few paragraphs, relies on objects defined only in Appendix C, and includes a "two-scale proposal-control" experiment that is not described anywhere.
- No figure of the mechanism. The idea is easy to picture, so I was expecting some accompanying figures. Erasing the velocity makes the fast oscillating rule overshoot again in every block, while keeping it lets a fast and a slow rule take turns building up the error. A plot of a single mode in these cases would make Sections 3–4 much easier to follow than the stability inequalities alone.
The paper needs a major rewrite. These are only a few examples of writing issues.
2. Limited scope.
As mentioned in the first point, the paper's setting is different than classical restarts in accelerated optimization, so I failed to understand why the shortest stable block length matters or when this setting arises. With a fixed rule, keeping all the velocity is already stable, so the trade-off exists only because the rule changes. The worst case also needs the step size to jump by a factor of (under the paper's Polyak parameters) between blocks. If all rules must converge on the same range of curvatures , this worst case cannot happen, so it is unclear how much of the result carries over to changing the optimizer on a given problem.
Within the model, keeping part of the velocity only improves the constant in the formula. Block lengths shrink by about 10% and that saving gets smaller as grows. While the goal of the paper is to establish stability, I would still have liked some intuition on what happens to the convergence rate. Right now, the scope of the paper is limited.
Finally, the paper should compare more concretely with dwell-time methods for switched systems. They are only mentioned in the third paragraph of the intro. Perhaps, a better positioning against that literature would also allow to effectively show why this setting is significant.
Questions for authors
- Is there a practical setting where the optimizer's settings change as much as the worst case requires?
- How do the results change if the kept fraction can depend on the rules before and after the switch, does that extra information buy any extra gains?
- Does the derived block length and kept fraction lead to faster convergence than a full reset under any switching schedule? Not necessarily a theoretical argument, even an empirical experiment would be interesting.
2 comments
Response to Reviewer XTqh (2/2)
Size of the gain and the rate. We agree that the interval gain is a constant-order term. Retention shortens the interval from 104 to 93 steps at , about 10%, and from 320 to 292 and from 724 to 669 steps at and (Table 1). At a fixed block length, it also reduces the worst-case per-block factor by a constant ratio. As with , this factor tends to (Corollary 5, Appendix I). Hence improves on full reset by the factor , where is the golden ratio. At , the certified per-block factor for is 0.64 times that of full reset at every tested from 104 to 300 (Table 8). Per step, the gain is only . To reduce the worst-case bound by at , needs about 1,459 steps and full reset 2,383, but at they need 438 and 460. Retention therefore matters most near the stability threshold and when is fixed externally.
Dwell-time methods. In the new Appendix K, a dwell-time bound in the Euclidean norm, which needs for every allowed rule , requires at least 126, 373 and 829 steps at the three margins. At our retentions, a numerical search finds no common quadratic Lyapunov function for blocks shorter than 96, 300 and 686 steps. These are 3, 8 and 17 steps more than our exact optima of 93, 292 and 669, although this search is not certified. Our analysis also proves that blocks below these optima fail, and it gives the exact no-reset intervals 105, 320 and 725. Mode-dependent conditions in the style of Geromel & Colaneri (2006) use one Lyapunov function per rule. Our certificate for rule-dependent retention (Appendix J) is of this kind, with one norm per sign of the rule's trace, but we did not compute one for constant retention. Our certified designs also contract every longer block.
Q2: retention that depends on both rules. This information helps, but it can at most halve the leading term of the interval (Proposition 6, Appendix J), because every such policy needs , which means , 185 and 416 at the three margins. On the complete class of rules, we certify the following policy at , 201 and 461: keep the velocity when consecutive rules have traces of the same sign, and reset it otherwise. This is 27 to 31% shorter than the best constant retention and within 12% of the bound. It acts on each mode separately, so it needs the eigenbasis and is an oracle policy.
Q3: is it faster than full reset? Only in the worst case, where it has a better rate and is stable at shorter blocks: the certified converges for every , while full reset can diverge for . Under random switching with five rule distributions, every retention converged, including and at (Section 7.5, Appendix M). Retention barely mattered on three distributions, and full retention was fastest on the two with extreme rules. For example, when and are drawn with equal probability, the per-step rates (lower is faster) at were 0.980 for , 0.986 for and 0.991 for , so the certified retention was the slowest. The static design thus protects against bad sequences but does not improve average speed (Section 7.5).
Response to Reviewer XTqh (1/2)
Thank you for checking the proofs and for the concrete suggestions. We agree with the criticism of the presentation.
Title and abstract. The abstract now opens with the switching model: the rule (step size and momentum) may change every h steps, a fraction r of the velocity is kept at each change, and the guarantee covers every rule sequence with spectral radius at most s<1. Because the retention result needs rules that change between blocks, we propose the title "Restarting Heavy Ball under Changing Hyperparameters: Sharp Intervals for Momentum Retention". The revised PDF keeps the submitted title until the change is approved.
Writing. The sentence you quote is now a plain statement of the exact intervals. We removed the framed scope box and many repeated caveats, gathered the main scope statements in one paragraph of Section 2, and made Sections 3, 4, 5 and 7 open by saying what they show.
Terms. "Commit length" is now "block length", the number h of steps between rule changes. "Contract" (after Theorem 3) is the guaranteed decrease W+≤qhW at each completed checkpoint, where W=∥g∥2+L2∥v∥2 and q<1 is fixed. "Handoff" (contributions) means that an executor keeps moving with the last velocity for K steps until the next gradient arrives.
Section 7.3. It now opens with its question and answer: certifying a joint position-velocity energy did not help the optimizer in any of four controls. Three labelled paragraphs then define the objects in place, including the two-scale proposal control, an evolution strategy whose two mutation scales are frozen or adapted. Appendix O specifies these experiments.
Mechanism figure. Figure 1 now shows one eigenmode at 1−s=0.05 and h=93. In panel (a), the fastest allowed rule A− runs in every block, and each full reset re-excites its transient. In panel (b), A− alternates with the slowest rule A+, and full retention builds up the error. The certified r=0.3727 contracts in both.
Q1: does the worst case arise in practice? For full reset, it needs no rule change at all. With Polyak's parameters, the heavy-ball matrix of the top eigenmode is exactly A−, so a single well-tuned rule restarted every h steps diverges whenever h<hreset, the full-reset threshold. On a 200-dimensional quadratic, the measured growth per block matches Ds(h)=sh[1+h(1+s)] with relative error below 10−10 (Section 7.5). For partial retention, the worst case needs the step in one mode to change by the factor κs=((1+s)/(1−s))2, which is 1521 at s=0.95. With a scalar step and momentum on a quadratic with condition number κ=L/μ, this requires κ=1, whereas steps that differ between eigendirections, such as coordinate-wise steps in an eigenbasis, also allow it (Proposition 4(iii), Appendix H.1). Schedules, warm restarts, population-based search and learned optimizers change rules, but we do not claim that they select the worst case (Appendix H.3).
Weakness 2: rules that converge on the same [μ,L]. You are right for retention when κ>1, because its worst case needs the step ratio κs within one mode, but the full-reset worst case needs only one rule and still occurs. The retention designs of Table 1 therefore stay valid for every κ and optimal for κ near 1, but may be conservative for large κ. In uncertified grid estimates at s=0.95 (Table 6), full reset still needs 104 steps for every κ, while the best of six tested retentions needs about 72 steps at κ=10 (with r=0.8), and 54 at κ=100 and 40 at κ=1000, both with full retention.