Progress-Certified Momentum Restarts

Momentum optimizers overshoot. They build up velocity along a flat stretch of the loss surface, then carry it straight through the bottom of a sharp valley and oscillate. The standard fixes are blind to where the optimizer actually is. One is a momentum coefficient that decays on a fixed clock. Another resets the momentum buffer every fixed number of steps. A third zeroes it coordinate by coordinate whenever one noisy mini-batch gradient disagrees in sign with the stored velocity. We propose a restart rule that fires only when the optimizer has measurably stopped making progress. Progress is estimated from quantities the optimizer already computes, the inner product between each gradient and the step just taken, so no loss evaluations are needed. The rule plugs into a theoretical recipe that turns online-learning algorithms into non-convex optimizers. Inside that recipe, the rule inherits convergence guarantees instead of being a heuristic.

The link between the two research directions is concrete. Parameter-free online learning, meaning algorithms that need no step size, no domain bound and no gradient bound, pays an unavoidable "volatility tax" when gradient magnitudes jump. The main protection against that tax is to remember the largest gradient scale seen so far and to penalize large moves softly. A momentum restart that throws away this scale memory reintroduces the volatility problem. A restart that keeps nothing directional lets oscillation continue. Our design resets the direction and keeps the scale, and we test directly whether that split is what matters.

Core Claim

In online-to-non-convex conversion (O2NC), an online learner chooses each update vector $\Delta_t$ and is scored on the linear loss $\langle g_t, \Delta_t\rangle$, where $g_t$ is the stochastic gradient. The learner's internal state plays the role of the momentum buffer. Random Scaling and Momentum for Non-smooth Non-convex Optimization shows that if each update is multiplied by an independent random factor $s_t \sim \mathrm{Exp}(1)$, then the expected change in the objective $f$ equals the expected inner product of gradient and step. That identity has so far been used only inside proofs. We use it as a live, unbiased progress meter. Over the steps since the last restart $\tau$, define

$$\widehat{P}_{\tau:t} = -\sum_{s=\tau}^{t} \langle g_s, \Delta_s \rangle ,$$

which estimates the loss decrease since the restart. The martingale noise of this sum is controlled by $\sigma\,(\sum_s \|\Delta_s\|^2)^{1/2}$, where $\sigma$ is the gradient-noise scale.

The rule works as follows. Once a minimum epoch length $T_{\min}$ has passed, the momentum direction is restarted when the confidence-adjusted progress over a recent window becomes nonpositive:

$$\widehat{P}_{t-W:t} + c\,\hat\sigma \Big(\sum_{s=t-W}^{t}\|\Delta_s\|^2\Big)^{1/2} \le 0 .$$

Here $W$ is the window length, $\hat\sigma$ is a running noise estimate, and $c$ is a confidence constant. The learner's magnitude hint, its running maximum gradient norm, is carried across restarts. The rule is a stochastic, non-convex version of the function-decay restart that Free-FISTA uses in deterministic convex problems. It needs no function values, and a fluctuation in a single mini-batch cannot trigger it.

Three things are new relative to prior work. The restart signal is a noise-calibrated estimate of actual descent, not a sign test or a clock. Restart times are stopping times inside the O2NC analysis, so the guarantees of periodic restarts can be retained. The reset separates direction from scale, so parameter-free adaptation survives each restart.

What Prior Work Leaves Open

Two papers supply the scaffolding. Derandomized Online-to-Non-convex Conversion for Stochastic Weakly Convex Optimization proves that SGD with momentum, with its buffer zeroed every $T_0$ steps, reaches the optimal $\mathcal{O}(\delta^{-1}\epsilon^{-3})$ complexity for Goldstein stationarity. Goldstein stationarity is a notion of approximate stationarity for non-smooth functions, based on averaging gradients over a small ball. The restarts in that paper are strictly periodic, and its step sizes are tuned by hand within each epoch. Random Scaling and Momentum for Non-smooth Non-convex Optimization supplies the exponential-scaling identity that turns $\langle g_t,\Delta_t\rangle$ into an unbiased descent measurement. That paper does not study oscillation or restarts. Our proposal reuses both techniques and replaces the fixed $T_0$ with a data-driven stopping rule.

Two further lines of work motivate the trigger and also constrain its design. Parameter-Free FISTA by Adaptive Restart and Backtracking shows that restarts driven by function decay can be dramatic in deterministic convex problems, but it requires exact objective values that stochastic training does not provide. SPI-Optimizer: an integral-Separated PI Controller for Stochastic Optimization treats momentum as the integral term of a control loop. Its explanation of overshoot, stale accumulated gradient continuing to push after the true slope has flipped, is exactly what our trigger targets. Its per-coordinate sign test has no guarantees and is exposed to mini-batch noise. HVAdam: A Full-Dimension Adaptive Optimizer uses drops in cosine similarity against a long-term trend, which is a similar direction-based signal. We aggregate over a window and all coordinates into one scalar with a concentration bound, so that a single noisy batch cannot fire the trigger.

The volatility literature constrains how the reset may be done. Online Convex Optimization with Unconstrained Domains and Losses and Online Learning Without Prior Information prove that without prior scale knowledge, sudden gradient-magnitude increases force an exponential penalty. Fully Unconstrained Online Learning avoids the worst of this by carrying the maximum observed gradient norm as a magnitude hint and applying a soft quadratic penalty on large moves. Together these results imply that a restart which reinitializes the scale estimate will repay the volatility tax at every restart. They also imply that the regret bound will pick up a factor growing with the number of restarts, through the range-ratio term between the true scale and the initial guess. This is why we reset direction but not scale. The tension documented in Gradient Descent with Polyak's Momentum Finds Flatter Minima via Large Catapults also shapes the rule. Large momentum-driven loss spikes can reduce sharpness, which helps generalization. A trigger based on "the loss went up" would kill those beneficial catapults. A trigger based on windowed net progress lets a spike that is followed by recovery pass without a restart. Whether it does so in practice is something we measure rather than assume.

Research Program

The algorithm is SGD with momentum written as an O2NC online learner over update vectors. We study two versions of that learner. The first is the discounted online gradient descent used in D-O2NC. The second is a parameter-free one-dimensional learner in the style of Fully Unconstrained Online Learning, applied to the step magnitude, so that the radius $D$ of the update ball is learned rather than set. Each step draws an $\mathrm{Exp}(1)$ scale, accumulates the progress estimate, and checks the confidence-adjusted trigger. When the trigger fires, the direction state is zeroed and the magnitude hint and noise estimate are kept. The per-step overhead is one inner product and one squared norm.

The theory has a narrow target. First, we show that when epochs end at stopping times with length at least $T_{\min}$, the D-O2NC Goldstein-stationarity guarantee holds with $T_0$ replaced by $T_{\min}$, up to constants. The per-epoch regret bound of an anytime online learner does not depend on how the epoch ends. The remaining work is to check that the conversion's averaging argument tolerates random epoch lengths. Second, we construct piecewise-quadratic and plateau-then-valley problems on which adaptive epochs provably need fewer gradient calls than the best fixed $T_0$. The intuition is that the optimal fixed period is forced to compromise between the lengths of plateaus and the widths of valleys. We do not claim to fix the suboptimal $\mathcal{O}(\epsilon^{-5})$ Moreau-envelope rate of D-O2NC. If the analysis gives an improvement there, we will report it as a bonus. Third, for the parameter-free version, we bound how much each restart adds to the regret, with and without scale retention. The goal is to show that retention removes the growth of the range-ratio term with the number of restarts.

Baselines

The naive reference point is SGD with momentum at $\beta=0.9$ with a tuned learning rate and no restarts. On CIFAR-10 with ResNet-18, Random Scaling and Momentum for Non-smooth Non-convex Optimization reports 94.6% top-1 test accuracy for standard SGD with momentum and 94.4% for its randomly scaled variant. The randomly scaled variant is the exact configuration our method builds on. This pair tells us how much random scaling alone costs, and our method must recover that gap.

The most direct competitor is periodically restarted D-O2NC from Derandomized Online-to-Non-convex Conversion for Stochastic Weakly Convex Optimization. It reports test-accuracy gains over SGD with momentum of 0.9 points on CIFAR-10 with ResNet-101 and 1.96 points with a Vision Transformer. Absolute accuracies are not reported. We run it with a full sweep over $T_0$ and give our method the same tuning budget, split over $T_{\min}$ and $c$. Beating it means two things. The first is matching or exceeding its best-$T_0$ accuracy on each workload. The second, which is the real claim, is doing so with a single setting shared across all workloads, where no single $T_0$ does.

We compare against two noise-sensitive adaptive restart schemes. One is SPI-Optimizer's coordinate-wise sign reset, which reports up to 40% faster convergence and a 27.5% error reduction ratio against momentum and Nesterov baselines on CIFAR-100. The other is a cosine-similarity reset in the spirit of HVAdam. Both run on the same ResNet-56 and Wide ResNet CIFAR-100 setups with matched learning-rate sweeps. Our method should reach the same target accuracy in no more steps, and it should restart at least an order of magnitude less often near convergence.

For schedule-based damping we use SHB-DW from Exploring the Inefficiency of Heavy Ball as Momentum Parameter Approaches 1. It reports 93.38% on CIFAR-10 with ResNet-18, compared with 93.26% for heavy ball at $\beta=0.9$ and 92.66% for plain SGD. It gets its horizon for free, whereas our method never sees the horizon.

For the strongest practical optimizer we use Schedule-Free SGD and Schedule-Free AdamW from The Road Less Scheduled. The SGD version matches the 76.9% ImageNet ResNet-50 accuracy of a tuned cosine schedule. The AdamW version won the AlgoPerf self-tuning track with an 8% speedup over the self-tuning baseline, according to Accelerating neural network training: An analysis of the AlgoPerf competition. Our restart rule is orthogonal to schedule-free averaging, so the fair comparison is Schedule-Free with and without our trigger acting on its base sequence, at identical hyperparameters. The trigger is worthwhile if it improves time-to-target on the AlgoPerf workloads without lowering the rate at which trials complete.

Three ablations isolate the key ingredients. The first resets both direction and scale, which tests the volatility argument. The second uses a zero confidence term, which tests noise robustness. The third removes the $\mathrm{Exp}(1)$ scaling, which tests whether the progress estimate needs to be unbiased.

Why not just…?

Why not just tune $T_0$ for periodic restarts? This is the most serious threat. On any single workload, a well-tuned $T_0$ may match our method. The argument for adaptivity is that the best period depends on how long plateaus and valleys last, and that changes across architectures and across phases of training. The experiment that settles this is the full $T_0$ sweep on ResNet-101, ViT and CIFAR-100. If the best $T_0$ varies little across workloads and our single setting does not beat it, the adaptive trigger is not worth its complexity, and we will say so.

Why not just clip gradients? Clipping limits the size of each incoming gradient but leaves the stored velocity untouched. As SPI-Optimizer's analysis of stale accumulated gradient points out, that velocity keeps pushing past the valley floor after a clipped impulse. Clipping also needs a threshold, and the unconstrained-learning results cited above show that a wrongly chosen threshold is expensive when the scale is unknown. We include clipped SGD with momentum at a swept threshold on the phase-retrieval and CIFAR tasks. If clipping removes the oscillation events that our trigger detects, that result counts against us.

Why not just decay $\beta$ on a schedule, as in SHB-DW? The schedule is tied to the clock, not to the loss surface, and it needs the horizon in advance. The Road Less Scheduled documents that horizon-dependent schedules are brittle. Stopping SHB-DW early or extending it past its planned length is the test. We evaluate every method at several stopping points, and our method should dominate SHB-DW at every point other than the one SHB-DW was scheduled for.

Why not just use Adam? Dividing by a running second moment normalizes gradient size per coordinate, but the first moment of Adam still lags and overshoots in the same way. Our trigger acts on that first moment, so the natural test is AdamW or Schedule-Free AdamW with and without the trigger, not a contest between Adam and our method.

Proposed Experiments

We begin with problems where the ground truth is visible. On robust phase retrieval across condition numbers, the benchmark D-O2NC uses, we log every restart and compare its timing with the true loss trajectory. We check whether $\widehat{P}$ tracks actual loss change measured on large held-out batches, and whether the trigger fires near genuine overshoots rather than at random. On the linear diagonal networks and small CIFAR-10 subsets from the catapult study, we measure sharpness before and after each spike. This tells us whether the trigger suppresses the sharpness-reducing catapults at $\beta=0.9$ while still curbing the overshooting at $\beta=0.99$ that produces dead neurons. As a convex sanity check, the 12 LibSVM logistic-regression problems from The Road Less Scheduled test whether the rule behaves like a stochastic Free-FISTA.

The main deep-learning runs cover CIFAR-10 with ResNet-18, ResNet-101 and ViT, and CIFAR-100 with ResNet-56 and Wide ResNet, all with the baselines above over three or more seeds. If these succeed, we run the AlgoPerf self-tuning track with Schedule-Free AdamW plus the trigger.

Four checks decide the outcome. The progress estimate must correlate with measured loss change; if it does not, the method has no basis. With one shared setting, the method must match the best tuned $T_0$ across workloads. Keeping the scale estimate must beat resetting it, with the gap widening as restarts become more frequent, as the volatility-tax argument predicts. Near convergence, the trigger must fire far less often than sign-based resets. If the first check fails, we stop. If only the second fails, the contribution shrinks to a guarantee-preserving restart analysis without a practical advantage, and we will report it that way.