Capping the Overshoot of Long-Step Gradient Descent with a Progress-Relative Projection

Gradient descent can be made faster without momentum. The trick is a carefully chosen schedule of step sizes in which most steps are short and a few are very long, far longer than the classical stability limit. The price is that the objective temporarily gets worse after each long step, sometimes much worse, before later steps recover the loss. This is harmless when only the final iterate matters. It is a real problem when an intermediate iterate is actually used. Examples include a controller that stops its optimizer early to meet a sampling deadline and applies whatever it has, or an online learner whose current parameters are being deployed. We propose to tame these spikes with the oldest stabilizer in adaptive control: a projection. After every step, the iterate is projected back into the problem's feasible set and also into a ball around the current point. The radius of that ball grows with the total distance the algorithm has already traveled.

The key observation comes from the known lower bound on long-step methods. The size of a spike is governed by how long the step is relative to the progress already made. A cap tied to that ratio should therefore bound the worst intermediate error by a constant factor. It should still leave room for the step sizes themselves to grow without limit, because gradients shrink as the algorithm converges. If this holds, it gives constrained, anytime-usable acceleration with a certified bound on transient overshoot. As a side effect, the method should also be robust to underestimating the smoothness constant, which is the failure mode that makes long-step schedules explode in practice.

Core Claim

We study projected gradient descent on problems of the form $\min_{x\in\mathcal{X}} f(x)$. Here $f$ is convex with $M$-Lipschitz gradient, and $\mathcal{X}$ is a closed convex set. We run a long-step schedule $\alpha_t$ (the silver schedule or its anytime variant) but modify the update as

$$x_{t+1} = \Pi_{\mathcal{X}}\big(x_t + \mathrm{clip}_{r_t}(-\tfrac{\alpha_t}{M}\nabla f(x_t))\big), \qquad r_t = c\sum_{s<t}\|x_{s+1}-x_s\| + r_0,$$

In this update, $\mathrm{clip}_{r}$ rescales a vector to have norm at most $r$, $\Pi_{\mathcal{X}}$ is Euclidean projection onto $\mathcal{X}$, $c>0$ is a cap ratio, and $r_0$ is a small initial radius. Clipping is itself the projection onto a ball of radius $r_t$. The whole update is therefore a composition of non-expansive maps, the property that makes projected methods analyzable.

We make two claims. First, for suitable $c$, the capped schedule keeps a better-than-$O(1/T)$ rate at every iteration $T$ on constrained smooth convex problems. It also guarantees $f(x_{T}) - f^* \le (1+c)^2 \min_{s\le T}\big(f(x_s)-f^*\big)$ up to constants. The squared form mirrors the overshoot penalty discussed below. Second, when $M$ is underestimated by a factor of $k$, the capped method degrades gracefully, with error growth bounded in terms of $c$ and independent of $k$. The uncapped schedule diverges in the same situation.

What prior work establishes and leaves open

Three papers supply the acceleration machinery. Altschuler and Parrilo showed that plain gradient descent with a fractal "silver" schedule, whose occasional spikes exceed $2/L$, reaches $O(n^{-1.2716})$. Bok and Altschuler extended this to proximal and projected steps using a Laplacian sum-of-squares certificate. They showed that the non-expansiveness of projection does not destroy the accelerated rate. Their guarantee holds only at milestone horizons $n=2^k-1$, however, and they acknowledge that transient surges can cause practical instability. Zhang, Lee, Du and Chen obtained an anytime rate of $O(T^{-1.119})$ by concatenating silver blocks with "join" steps that control gradient norms. Their result is unconstrained and still non-monotone. We reuse their schedules unchanged. Our contribution is the progress-relative cap and its analysis in the constrained setting.

Two results constrain the design. Kornowski and Shamir proved that any momentum-free schedule achieving $o(1/T)$ on a one-dimensional quadratic must have $\limsup_t \eta_t=\infty$. A cap on the step size itself is therefore ruled out. This is why we cap displacement instead, which still permits $\eta_t\to\infty$ because $\|\nabla f\|\to 0$. The same paper shows that on a scaled Huber loss, the error after a long step grows with the square of the ratio between that step and the cumulative prior progress. That ratio is exactly what $r_t$ bounds. We read their negative result as a prescription for where to place the projection.

The projection side motivates the regime. In adaptive control and reinforcement learning, projection onto a compact set is the standard way to stop drift and bound oscillation. Dayan et al. used it for temporal-difference learning, projected SARSA bounds "chattering" to a ball whose radius is independent of the projection radius (Zhang et al.), and the deadly-triad analysis uses a ball centered on the moving primary weights (Zhang, Yao and Whiteson). That last construction, a projection set centered on a moving iterate, is the closest structural precedent to our ball around $x_t$. In their work the projection enforces slow timescales. We instead use it to permit fast, aggressive steps. The field's known weakness also applies here: a ball chosen too small biases the answer, and one chosen too large does nothing. Tying the radius to progress rather than to a fixed prior is our response to that problem.

Finally, the application motivation is real-time projected-gradient NMPC for anesthesia. That controller runs a truncated number of projected gradient steps per sample under hard infusion limits, with a Lyapunov stopping rule. Any iterate may be the one applied, so a long-step method is only usable there if its intermediate iterates are certified.

Research Program

The theoretical work has three parts. We first bound the spike by adapting the Kornowski–Shamir Huber argument, showing that with the cap, the post-step error ratio is at most $(1+c)^2$. We then prove that acceleration survives. The strategy is to show that along the silver schedule on smooth convex problems, the uncapped long-step displacement is itself at most a constant multiple of prior cumulative displacement except in a controlled set of cases. In those cases, clipping costs at most a constant factor per block, which a recursive-gluing argument in the style of Bok and Altschuler can absorb. We expect a rate exponent strictly between $1$ and $1.119$ that depends on $c$, and we will characterize this trade-off curve. Where proofs stall, we will compute worst-case performance numerically by solving small semidefinite "performance estimation" programs over the capped update for horizons up to about 127. This tells us, for each $c$, the true worst-case rate and spike. The third part is the robustness claim under misestimated $M$, which follows from the spike bound because clipping does not depend on $M$.

Empirically, we will implement the capped method in two forms. One is a standalone solver for constrained smooth problems. The other is a drop-in inner solver for truncated-iteration model predictive control, which optimizes a plan over a short horizon at each sampling instant.

Baselines

The naive reference point is projected gradient descent with constant step $1/M$. It is monotone and safe, it has the $O(1/T)$ rate, and it is what practitioners would ship. Beating it means reaching a target accuracy in fewer iterations while never exceeding its worst intermediate error by more than the certified factor.

The strongest existing long-step competitor is proximal silver gradient descent of Bok and Altschuler, together with the anytime concatenated schedule of Zhang et al. run with projection. The only reported figures on Lacuna are theoretical rates, $O(n^{-1.2716})$ at milestones and $O(T^{-1.119})$ anytime (unconstrained). No reported empirical result was found on Lacuna for either schedule on constrained benchmarks, so we will measure both ourselves. We will run all methods on identical problem instances with the same $M$ estimate, the same iteration budgets, and no per-instance tuning beyond a single sweep of $c$ on held-out instances. Beating these baselines means lowering the worst intermediate error (over all stopping times) by a large factor while losing no more than a small constant factor in error at milestone horizons.

The strongest momentum competitor is accelerated projected gradient (Nesterov/FISTA-type), whose rate is better than any momentum-free schedule. The file's transfer-function analysis of SGD with momentum and Nesterov's method (Yao et al.) shows that momentum trades rate for underdamped overshoot. We will include it both plain and with gradient-based restart, under the same budgets.

The key ablations are a cap with a fixed radius $r_t\equiv r_0$, which should destroy acceleration as Theorem 1 predicts, and a cap relative to $\|x_t-x_0\|$ instead of cumulative path length. Together they isolate whether progress-relative scaling is the essential ingredient.

Why not just…?

Why not just use Nesterov acceleration, which is faster anyway? In pure offline optimization it is faster, and we do not claim otherwise. The case for momentum-free long steps is where iterates are applied mid-run and a hidden velocity state is undesirable. That includes warm-started truncated MPC, where momentum carried across sampling instants is ill-defined, and settings where overshoot means a physical constraint approach. This is a genuine threat. The truncated-MPC experiment settles it: if restarted FISTA matches our method on worst intermediate cost and closed-loop tracking at equal iteration budgets, then our contribution reduces to the theory of the capped schedule, and we will say so.

Why not just add a line search or reject steps that increase the objective? A monotone safeguard rejects exactly the steps that produce acceleration. Silver steps work because individual long steps temporarily raise the objective (Altschuler and Parrilo). We will run an Armijo-safeguarded silver schedule and expect it to collapse to roughly constant-step behavior. Our cap permits bounded increases rather than forbidding them.

Why not just use the anytime schedule of Zhang et al. with projection added? Anytime rates bound the error envelope asymptotically, but they do not bound spikes relative to the best iterate seen so far. They also offer no protection when $M$ is underestimated. The uncapped-with-projection run is a direct baseline. If its measured spikes are already within $(1+c)^2$ and it survives misestimated $M$, the cap is unnecessary and the project narrows to the constrained anytime proof.

Proposed Experiments

The first experiment uses the adversarial instance: the scaled Huber function from Kornowski and Shamir, embedded in a box constraint. We will plot the error at every $T$ for all methods and measure the maximum ratio of current error to best-so-far error. The capped method must hold this ratio near $(1+c)^2$ while the silver schedule spikes.

The second experiment uses constrained smooth convex problems: box-constrained least squares, simplex-constrained quadratics, and $\ell_2$-ball-constrained logistic regression, at condition numbers from $10^2$ to $10^5$. The metrics are iterations to reach a target accuracy, worst intermediate error, and fitted rate exponent. We will repeat the runs with $M$ underestimated by factors of 2, 4, and 10. The decisive check is that the uncapped schedule diverges while the capped one degrades by a bounded factor.

The third experiment is truncated projected-gradient MPC on the Schnider/Minto pharmacokinetic models used in the anesthesia NMPC study, with fixed per-sample iteration budgets of 3, 5, and 10. The metrics are setpoint tracking error, constraint violation (which must be zero because of $\Pi_{\mathcal{X}}$), and the number of samples at which the applied iterate is worse than the warm start.

The project succeeds if the capped schedule beats constant-step projected gradient on iteration count in the second experiment, shows bounded spikes where silver does not in the first and third, and does not lose to restarted FISTA on worst-case transient cost in the third. The performance-estimation computations should agree with measured worst cases to within numerical tolerance.