acceptodds
Under review as a conference paper at ICLR 2027

Learning to Restart: Differentiable Restart Policies for Optimization Dynamics

Abstract

Adaptive restart mechanisms, which reset the momentum or other auxiliary state of an iterative optimizer, play a central role in the empirical performance of accelerated first-order methods, yet existing restart rules remain almost entirely hand-designed. The obstruction to learning restart policies is that, unlike the typical Learning to Optimize (L2O) setting, the discrete restart events make the resulting trajectory non-differentiable in the algorithm parameters and thus block gradient-based optimization of the restart policy. We resolve this obstruction by developing a differentiable framework for restart policies through their continuous-time limit. We introduce *surrogate gradients* for the restart events and optimization trajectories that are efficient to compute and provably converge to their continuous-time counterparts. We validate the effectiveness of our surrogate gradients in L2O settings, training restart policies that improve upon standard handcrafted adaptive restart criteria on quadratic and linear programs, and that transfer zero-shot from synthetic quadratics to logistic regression on real datasets.

Primary area:
optimization
Keywords:
learning to optimize, optimization

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_6uKZOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes a differentiable framework for learning restart policies in iterative optimization algorithms. The authors derive the sensitivity of restart times in continuous-time optimization dynamics and construct surrogate gradients for discrete restart decisions, with theoretical guarantees on their approximation accuracy. Experiments on quadratic programming and linear programming, including transfer to real-data problems, demonstrate improvements over several handcrafted restart rules.

Critical strengths
  1. Learning when to restart an optimization algorithm is an interesting direction in L2O. Existing restart mechanisms are largely handcrafted, and making restart decisions learnable could improve the performance of iterative optimizers.
  2. The paper develops an elegant connection between discrete restart events and their continuous-time counterparts. The derivation of restart-time sensitivities through the implicit function theorem, together with the proposed discrete surrogate gradients, provides a mathematically motivated solution to the non-differentiability problem.
  3. The authors provide convergence guarantees for the proposed surrogate gradients under suitable assumptions. The experimental results are encouraging, particularly the transfer of learned restart policies from synthetic quadratic problems to logistic regression and CT reconstruction on real datasets.
Critical weaknesses
  1. My primary concern is that the experiments are relatively simple. Although the paper includes experiments on real datasets, all the considered optimization problems are deterministic convex problems, primarily quadratic programming, logistic regression, and linear programming. Furthermore, much of the training is performed on synthetic objectives. It would be much more convincing to evaluate the proposed method on more challenging and practically relevant optimization tasks, such as non-convex optimization, stochastic optimization, or neural network training.
  2. The main motivation of this paper is that discrete restart decisions are non-differentiable, making conventional gradient-based learning inapplicable. However, gradient-based optimization is not the only way to learn restart policies. Reinforcement learning, zeroth-order optimization, and evolutionary strategies can optimize discrete decisions or black-box objectives without requiring gradients through the restart events. In particular, since the learned restart policies contain relatively few parameters, zeroth-order optimization seems to be a natural alternative.
  3. The main theoretical result establishes that the proposed discrete surrogate gradients converge to the corresponding continuous-time gradients as the discretization becomes sufficiently fine. However, this does not directly guarantee that optimizing the actual discrete restart policy with these surrogate gradients improves the optimization objective. The theoretical results also rely on regularity and event-crossing assumptions that may not hold in more general settings.
  4. Although the learned policies outperform handcrafted restart rules in the reported experiments, the paper provides limited insight into what the policies actually learn. For example, do the learned policies primarily adjust the restart frequency, or do they identify restart patterns that are fundamentally different from existing criteria? Furthermore, the practical computational overhead of surrogate-gradient training is not thoroughly evaluated against alternative training approaches.
Questions for authors
  1. In the experiments, are only the parameters of the restart policy learned, while the underlying optimizer's step sizes and momentum schedules remain fixed? The introduction discusses the possibility of jointly learning the within-phase dynamics and the restart criterion, but it is not entirely clear whether this is explored experimentally.

  2. The theoretical formulation assumes that the restart score is positive at the beginning of each phase and crosses zero transversally. How are these conditions handled or enforced when the restart score is parameterized by an MLP? Are any numerical safeguards used to prevent immediate or excessively frequent restarts?

3 comments

Q. In the experiments, are only the parameters of the restart policy learned, while the underlying optimizer's step sizes and momentum schedules remain fixed? The introduction discusses the possibility of jointly learning the within-phase dynamics and the restart criterion, but it is not entirely clear whether this is explored experimentally.

Yes: in the submission only the restart policy is learned. The NAG experiments use the step size and momentum of Algorithm 1, and the LP experiments the PDLP rules of App. G.2. Joint learning appears in the motivating example of Sec. 2 and in Sec. 2.2, and is covered by the theory (θ\theta may enter the flow map), but it was not evaluated. We have now run it on the Sec. 4.1 QP setting; the results below will be added to the paper.

Setup. The schedule has two scalars: step α/L\alpha/L and momentum βj=(j−1)/(j+2+c)\beta_j = (j-1)/(j+2+c), with jj the steps since the last restart; (α,c)=(1,0)(\alpha, c) = (1, 0) is Algorithm 1. All arms use the Sec. 4.1 training distribution (d=20d = 20, κ∈180,240,320\kappa \in \\{180, 240, 320\\}), the 7-32-1 policy with features (75), the two-stage training with an objective of the form (76), and start from Algorithm 1's schedule. They differ only in which parameters receive the surrogate gradient. 20 seeds per arm.

Metric. Final gap (geometric mean over test problems) of the better of function / gradient restart under Algorithm 1, divided by the arm's final gap. Median over seeds; above 1 favours the arm.

1. Joint learning helps (test panels of Fig. 2 and Fig. 5, 30 problems each).

trained parametersd=20d=20d=400d=400d=1000d=1000all 11 panels
restart policy only4.5x47x1.7e3x333x
restart policy + schedule (joint)154x691x5.3e4x5.6e3x
schedule only, policy frozen83x170x8.5e3x1.2e3x
schedule only, function restart40x141x2.8e3x720x
schedule only, gradient restart39x45x637x97x

Joint learning beats restart-only learning on 20/20 seeds and 11/11 panels, by 20x on average (95% bootstrap CI 15x to 28x). At twice the training horizon the factors are 3.1e3x (restart only) and 2.4e6x (joint), so the gain is in the rate.

2. What is learned. The learned step is α=1.34\alpha = 1.34 (1.32 to 1.38 over seeds); the momentum offset stays near Algorithm 1 (c=−0.06c = -0.06, −1.25-1.25 to 0.310.31). The gain comes from a longer step, which a restart rule adapted to it makes usable:

  • Both parts contribute. Joint is 4.0x better than training only the schedule (17/20 seeds) and 20x better than training only the policy.
  • The policy adapts to the schedule. Replacing the learned policy by function restart under the jointly learned schedule is 2.6e3x worse. Even a schedule trained specifically for function or gradient restart is 101x or 62x behind the joint arm (20/20 seeds).

3. The surrogate gradient points the right way for the schedule too. Derivative of the training objective with respect to α\alpha at Algorithm 1's schedule, against central finite differences (h=0.03h = 0.03):

restart rulesurrogatefinite differencebackprop, restart times fixed
function restart−10.0-10.0−9.9-9.9−2.2-2.2
gradient restart−10.5-10.5−11.8-11.8−0.4-0.4
learned policy (3 seeds)−13.9-13.9 to −15.1-15.1−12.8-12.8 to −14.4-14.4+4.0+4.0 to +6.1+6.1

With restart times held fixed, the sign is wrong for a learned policy. Training the schedule under function restart with that naive gradient reaches 0.67x, against 720x with the surrogate.

4. Zero-shot transfer. The same checkpoints, without retraining, on unseen problem classes (final gap, lower is better; "handcrafted" is the better of function and gradient restart):

unseen problemhandcraftedrestart onlyjoint
ℓ2\ell_2 logistic regression, λ=10−2L0\lambda = 10^{-2} L_01.3e-49.1e-51.9e-5
ℓ2\ell_2 logistic regression, λ=10−3L0\lambda = 10^{-3} L_08.6e-59.2e-52.8e-5
matrix factorisation n=20n=20, r=3r=34.1e-171.8e-192.0e-21
matrix factorisation n=60n=60, r=5r=51.7e-144.3e-161.3e-18
non-convex logistic regression, d=30d=305.4e-35.9e-34.8e-3
non-convex logistic regression, d=100d=1002.8e-34.4e-32.0e-3

The joint arm ends below the restart-only arm on all six problems, which include non-quadratic and non-convex objectives.

5. LP. We also ran the joint variant on Netlib under the protocol of Table 1, learning two PDHG scalars together with the restart policy. Median final KKT residual per tier (learned rows: median over 5 seeds; lower is better):

methodsmallmidlarge
PDLP default3.20e-31.52e-31.43e-2
learned restart policy only1.71e-36.46e-42.36e-3
learned restart policy + schedule (joint)1.70e-35.44e-42.22e-3

Joint learning improves on the PDLP default on every tier and is on par with restart-only learning.

Q. Positivity of the score at the phase start, transversal crossing, and safeguards against immediate or overly frequent restarts.

Thank you for raising this point. It is a real issue. The theory of Sections 2–3 assumes that the score is positive at the start of every phase and crosses zero transversally, and an MLP score does not satisfy either condition automatically. We handle it at two levels: the way a restart event is defined in the implementation, and the way the score is initialized before training.

Event rule. We implemented two ways of detecting a restart. The crossing rule triggers a restart at step kk only when the score changes sign between two consecutive evaluations, Vˉ(k−1)>0≥Vˉ(k)\bar V(k-1) \gt 0\ge\bar V(k); at the start of a phase, the previous value is the score at the phase-start state. The sign rule triggers a restart at the first k≥1k\ge 1 with Vˉ(k)≤0\bar V(k)\le 0, as in Definition 3.1. When the score is positive at the phase start, the two rules give the same restarts. They differ only when it is not. The crossing rule then waits until the score has become positive and crosses zero again, so a violated assumption postpones a restart and never causes an immediate one, whereas the sign rule restarts at the first step. In each experiment we used the rule that performed better: the crossing rule for the continuous-time experiment (Sec. 2.4), the synthetic quadratics (Fig. 2) and the synthetic LPs (Fig. 3), and the sign rule for the transfer policy (logistic regression and CT) and for Netlib. Under both rules, the surrogate gradient (17) acts only at genuine crossings, where Δi=Vˉ(Si)−Vˉ(Si−1)<0\Delta_i=\bar V(S_i)-\bar V(S_i-1) \lt 0. The crossing rule produces no other events, and under the sign rule a restart without a sign change contributes no event gradient.

Initialization keeps the outputs well behaved. We never fine-tune a randomly initialized score. Every MLP score is first fitted by supervised learning (behaviour cloning) to the restart decisions of handcrafted rules: function restart for NAG, the FirstOrderLP baselines for LP (App. D, E, G.3). The transfer policy also starts with output bias +0.5+0.5, so it does not restart before this warm start (App. E, F). The Netlib score is initialized exactly at the PDLP rule ρk≤0.85\rho_k\le 0.85, which its affine class contains (App. G.4). Fine-tuning therefore starts from a score with the sign pattern of a known rule.

Numerical safeguards. In every implementation, the backward difference Δi\Delta_i is kept away from zero by a small floor (of order 10−810^{-8}; 10−1210^{-12} for Netlib). The gradient norm is clipped when training the Fig. 2, transfer and Netlib policies (at 1, and at 5 for the transfer policy), and all policies are trained with Adam-type optimizers, whose step does not grow with the gradient norm.

Thanks for the clarification. I think the submission is quite borderline. I would rate it as 2.5.

Reviewer_RXQkOpenReview ↗
Rating
2(−1)
Confidence
3(+1)
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

The paper learns adaptive restart rules for momentum and primal-dual first-order methods such as NAG and PDHG. Restart times are integer-valued in discrete time, so they are not differentiable in the policy parameters and plain backpropagation gives zero gradient. Instead, the authors starts from the continuous-time ODE, where restart times become differentiable, and derive their gradients through the implicit function theorem (Theorem 2.2). They then define a discrete surrogate gradient (Definition 3.2) and prove it converges to the continuous-time gradient as the step size goes to zero, whenever the discrete iteration is consistent with the ODE (Theorem 3.4). Learned restart policies beat the handcrafted restart rules on synthetic QPs, transfer zero-shot to logistic regression, and improve a PDLP-style restart rule on synthetic LPs and Netlib.

Critical strengths
  1. The problem is real and the idea seems practical: existing standard restart rules are not optimal, hence, heuristic, and have been left out of L2O because they are not differentiable.

  2. The theory is careful. Theorem 3.4 is stated with explicit conditions, the consistency of NAG with its high-resolution ODE is actually verified (Appendix C.5), and the surrogate is checked numerically against the continuous gradient (Appendix D.2).

  3. The zero-shot transfer from synthetic quadratics to real CT measurements is interesting, showcasing the potential application.

Critical weaknesses

I would not call the following weaknesses. Rather, given that the idea proposed in the paper is nice, I would like to ensure that what is indeed novel and what is not. Currently, the authors do not seem to make this distinction clear enough for readers who are not active in this topic.

  1. The core idea is not new, and the paper does not say so: The main technical idea is a discrete surrogate gradient for an event time, built by replacing the time derivative with a backward difference, and a theorem that it converges to the continuous-time gradient. Both already appear in Xie et al. (2025), Definition 3 and Theorem 2, for a single stopping time. The continuous-time gradient via the implicit function theorem is also there, and in Chen et al. (2020). What this paper adds is the extension to a sequence of restart events with state resets.

That extension is legitimate, but the paper presents the surrogate gradient as its own contribution ("We develop a surrogate gradient... We prove that... the surrogate gradients converge"), cites Xie et al. only for the continuous-time step, and calls it "closely related" in the appendix. Readers of the main text would think the surrogate idea is new. The contribution list should state clearly that Definition 3.2 and Theorem 3.4 generalize Xie et al.'s Definition 3 and Theorem 2 from one event to a sequence of reset events, and say what is technically hard about that step. My evaluation depends on this: if the multi-event extension is the whole difference, the contribution is a solid but incremental generalization with a new application.

  1. The LP experiments may be too small to show the benefit. The QP side is tested at realistic sizes (CT reconstruction up to d = 16384 on real data). The LP side is not: synthetic LPs have 12 variables and 6 constraints, and the Netlib policy is trained on the 7 smallest instances with the largest evaluation tier keeping only 10 instances (Appendix G.4). PDLP-style restarts exist because they make PDHG work on large LPs, so this is exactly the regime where the learned restart would need to be evaluated, and the paper has no results there. I am not asking for a particular baseline; I just cannot tell from these experiments whether the learned rule helps on LPs where restarts actually matter.
Questions for authors
  1. Definition 3.2 and Theorem 3.4 look like the multi-event version of Definition 3 and Theorem 2 in Xie et al. (2025). Is that correct? If so, what is technically new beyond handling a sequence of reset events?

  2. Is the idea that restart events are differentiable in the continuous-time limit itself new, or is it the application of existing event-differentiation ideas to restarts? Please be explicit in the contribution list.

  3. Do you expect the learned restart rule to still help significantly on large LPs, say with millions of variables, where PDLP-style restarts are actually used? While I think while the results seem to indicate the promising results, I found it a bit strange to use PDLP to solve such a small LP problems.

1 comment

Definition 3.2 and Theorem 3.4 look like the multi-event version of Definition 3 and Theorem 2 in Xie et al. (2025). Is that correct? If so, what is technically new beyond handling a sequence of reset events?

Indeed, our framework is a generalization of Xie et al 2025 to a sequence of restart events. Technically, when the optimization process terminates after the first restart event, the two definitions agree. Our main contribution here is conceptual: By modeling each restart as a continuous stopping time, we can derive its derivative and performance first-order optimization.

Is the idea that restart events are differentiable in the continuous-time limit itself new, or is it the application of existing event-differentiation ideas to restarts? Please be explicit in the contribution list.

Differentiating an event time through the implicit function theorem is standard: it underlies sensitivity analysis of hybrid systems and neural event functions for ODEs (Chen et al., 2020). Xie et al. (2025) applied it, together with a backward-difference surrogate, to a single stopping time. Our contribution is (i) to cast adaptive restart, which L2O has so far left out, as a sequence of stopping times with state resets, and (ii) to extend the derivation and the theory from one event to many.

This extension is not immediate. Moving an earlier restart shifts every later phase, which gives the boundary-shift terms in (12) and (19), and each restart sets the phase clock back to zero. Errors in the restart times and restart states therefore carry over from one phase to the next. Theorem 3.4 bounds these errors, and the errors of their gradients, at the same order O(ϵh+h)O(\epsilon_h+h) in every phase. We will rewrite the contribution list to state these points explicitly.

Do you expect the learned restart rule to still help significantly on large LPs, say with millions of variables, where PDLP-style restarts are actually used? While I think while the results seem to indicate the promising results, I found it a bit strange to use PDLP to solve such a small LP problems.

We expect so, but we agree that our experiments do not show it at the scale of millions of variables, and we will add this as a limitation. The evidence we have points in this direction. The Netlib policy is trained only on the seven smallest instances, and its gain over the PDLP default does not shrink on larger instances: its median KKT residual is 1.5×, 2.2× and 11.4× smaller on the small, mid and large tiers (Table 2). We used small LPs because training repeatedly unrolls long solver trajectories and differentiates through them.

Reviewer_rw7yOpenReview ↗
Rating
2
Confidence
3
Informativeness
3
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies the problem of learning adaptive restart policies for optimization algorithms. To address the non-differentiability of discrete restart events, the authors derive the sensitivities of restart times and optimization trajectories in continuous time using the implicit function theorem. They then construct discrete surrogate gradients via finite differences and establish their consistency with the continuous-time gradients. Experiments based on NAG and PDHG demonstrate the advantages of the learned restart policies on quadratic programming, linear programming, and optimization problems involving real-world datasets.

Critical strengths
  1. Adaptive restart is widely used in accelerated first-order optimization methods, but existing restart policies are largely handcrafted. Learning restart decisions through data-driven approaches is a worthwhile research direction.

  2. The paper applies continuous-time event sensitivities to learning discrete restart policies, accounting for recursive sensitivities across multiple restart events and boundary-shift corrections. Theorem 3.4 establishes a consistency guarantee for the proposed surrogate gradients.

  3. The learned policies outperform several handcrafted restart criteria on QP and LP problems and demonstrate transferability from synthetic QPs to logistic regression and CT reconstruction tasks, suggesting some degree of generalization.

Critical weaknesses
  1. The presentation and organization are insufficiently clear, making the core methodology difficult to follow. The paper introduces the L2O paradigm without providing a concrete mathematical formulation to explain how optimization algorithm design is cast as a parameter-learning problem, or how learning restart policies differs from conventional L2O. Sections 2–3 introduce a large number of symbols with insufficient explanation. For example, although AVA_V, V(t)V(t), FVF_V, Vˉ\bar V, FˉV\bar F_V, and Δi\Delta_i represent distinct mathematical objects, their meanings and relationships are not intuitive from the notation, requiring readers to frequently revisit earlier definitions. Furthermore, many essential derivations are deferred to the appendix. For instance, Definition 3.2 directly presents the three surrogate-gradient formulas in Eqs. (17)–(19), without first systematically explaining how they are obtained by discretizing the continuous-time formulas in Eqs. (10)–(12). In particular, the boundary-shift correction in Eq. (19) lacks an intuitive explanation or example in the main text. Overall, the presentation relies heavily on abstract definitions and statements, with insufficient mathematical derivations, intuitive explanations, and a concrete algorithmic example connecting the different sections. This substantially increases the effort required to understand the paper. I suggest reorganizing Sections 2–3 and using NAG as a running example to progressively establish the connections among the continuous-time model, discrete restart mechanism, and surrogate gradients.
  2. The paper lacks a systematic comparison with existing restart methods, and the experimental baselines are insufficient. The paper does not adequately explain why restarting can improve convergence, why restart decisions should be learned, or what specific limitations of existing handcrafted restart policies motivate the proposed approach. Although the main text provides mathematical expressions for Function Restart and Gradient Restart, it lacks a systematic comparison with Learned Restart in terms of decision mechanisms, expressive power, and applicability. For example, the authors should clarify what additional optimization-state information can be exploited by the learned policy and why this information may lead to better restart decisions. Furthermore, the NAG/QP experiments mainly compare against Function Restart and Gradient Restart introduced by O'Donoghue and Candès (2015), without including more recent theoretically grounded adaptive restart methods, such as [1–3]. In particular, [2] applies to both accelerated gradient methods and PDHG, making it highly relevant to the scope of this paper.
  3. The experiments do not sufficiently establish the contribution and computational efficiency of the proposed surrogate-gradient method. The paper employs a two-stage training procedure: supervised imitation of a handcrafted restart policy, followed by end-to-end fine-tuning using the proposed surrogate gradients. However, it lacks an ablation study that evaluates the policy trained only through supervised imitation, without surrogate-gradient fine-tuning. Consequently, it is unclear whether the performance improvements primarily arise from learning a restart policy or from the proposed surrogate-gradient training method. Regarding computational efficiency, Learned Restart requires additional feature computation and policy inference, so improvements in iteration counts do not necessarily translate into reductions in actual runtime. Nevertheless, the experiments do not report wall-clock time or the computational cost required to reach a prescribed accuracy.
  4. The so-called scale-free features are not strictly scale-invariant. Equation (75) in Appendix E describes the input features used for cross-task transfer as scale-free, but some of these features still depend on the numerical scale of the objective function. For example, the first feature, ϕ1=110log⁡10f(xk+1)\phi_1=\frac{1}{10}\log_{10}f(x_{k+1}), is not invariant under multiplicative scaling of the objective function, while the relative objective decrease feature, rk=f(xk)−f(xk+1)f(xk)+f(xk+1)r_k=\frac{f(x_k)-f(x_{k+1})}{f(x_k)+f(x_{k+1})}, is not invariant under additive shifts. Adding a constant to the objective function does not change the NAG optimization trajectory or the decisions of conventional Function Restart and Gradient Restart, but it may significantly alter the input features and resulting decisions of Learned Restart. This issue is particularly relevant to the claimed cross-task generalization.
Questions for authors
  1. Could the authors provide a running NAG example throughout Sections 2–3 to clarify the relationships among the continuous-time dynamical system, restart score function, and discrete surrogate gradients? Could they also provide a mathematical comparison between Learned Restart and existing handcrafted policies?
  2. Could the authors include the adaptive restart methods in [1–3] as additional experimental baselines, and provide comparisons among supervised pretraining alone, surrogate-gradient fine-tuning, and alternative methods for learning discrete restart decisions?
  3. Could the authors report wall-clock time and time-to-accuracy to verify whether Learned Restart offers practical computational advantages after accounting for feature computation and policy inference overhead?
  4. For Eq. (75), are the restart decisions of the learned policy robust under objective transformations of the form f↦af+Cf\mapsto af+C? Could the authors also clarify whether the policy function class contains the handcrafted restart rules as special cases?
4 comments
AuthorsOpenReview ↗

For question one

Q1.Could the authors provide a running NAG example throughout Sections 2–3 to clarify the relationships among the continuous-time dynamical system, restart score function, and discrete surrogate gradients? Could they also provide a mathematical comparison between Learned Restart and existing handcrafted policies?

Thank you for this helpful suggestion. We agree that a single running example makes it easier to see how the continuous-time dynamics, the restart score, and the discrete surrogate gradients fit together. In the revision, we will carry the following NAG example through Sections 2–3.

Continuous time: NAG with a learnable restart score. Let f:Rd→Rf:\mathbb{R}^d\to\mathbb{R} be smooth and convex, let ss be the stepsize, and set h=sh=\sqrt{s}. Within each restart phase, NAG is modeled by the high-resolution ODE (3):

X¨t+3t+τX˙t+h∇2f(Xt)X˙t+(1+3h2(t+τ))∇f(Xt)=0,τ=3h2,\ddot X_t+\frac{3}{t+\tau}\dot X_t+h\nabla^2 f(X_t)\dot X_t+\left(1+\frac{3h}{2(t+\tau)}\right)\nabla f(X_t)=0,\qquad \tau=\frac{3h}{2},

where tt is the time elapsed since the start of the phase and X0X_0 is the phase-start position. We write Zt=(Xt,X˙t)Z_t=(X_t,\dot X_t) for the full state and attach to it a parameterized restart score Vθ(t)=vθ(t,Zt;X0)V_\theta(t)=v_\theta(t,Z_t;X_0). A restart is triggered at the first time LL with Vθ(L)≤0V_\theta(L)\le 0: the momentum is reset, and a new phase starts from XLX_L with the phase clock set back to zero.

Discrete time: the NAG iteration. The discrete counterpart is the standard NAG iteration with a phase-local index kk:

βk=k−1k+2,yk=xk+βkhuk,xk+1=yk−s∇f(yk),uk+1=xk+1−xkh.\begin{aligned}\beta_k&=\frac{k-1}{k+2}, & y_k&=x_k+\beta_k h u_k,\\\\ x_{k+1}&=y_k-s\nabla f(y_k), & u_{k+1}&=\frac{x_{k+1}-x_k}{h}.\end{aligned}

The phase ends at the first step SS with Vˉθ(S)≤0\bar V_\theta(S)\le 0. In the notation of Sections 2–3, the two within-phase flow maps are F(t;x0,θ)=(Zt,Vθ(t))F(t;x_0,\theta)=(Z_t,V_\theta(t)) and Fˉ(k;x0,θ)=((xk,uk),Vˉθ(k))\bar F(k;x_0,\theta)=((x_k,u_k),\bar V_\theta(k)), compared on the grid tk=kht_k=kh.

From the restart score to the surrogate gradient. In continuous time, the phase length LL is defined implicitly by Vθ(L)=0V_\theta(L)=0, so the implicit function theorem gives its gradient (Section 2):

∂θL=−∂θVθ(L)+∂X0Vθ(L),∂θX0∂tVθ(L).\partial_\theta L=-\frac{\partial_\theta V_\theta(L)+\partial_{X_0}V_\theta(L)\\,\partial_\theta X_0}{\partial_t V_\theta(L)}.

In discrete time, the restart step SS is an integer and has no derivative. The surrogate gradient of Section 3 uses the same formula with the time derivative ∂tVθ(L)\partial_t V_\theta(L) replaced by the backward difference Vˉθ(S)−Vˉθ(S−1)\bar V_\theta(S)-\bar V_\theta(S-1). Appendix C.5 shows that the NAG iteration tracks the ODE, together with its derivatives with respect to the phase-start position, with error O~(h)\widetilde O(h). The closeness theorem of Section 3 then gives h,grad(S)=∂θL+O~(h)h\\,\mathsf{grad}(S)=\partial_\theta L+\widetilde O(h), and the same order of error for the gradients of the restart state and of the trajectory away from restart times.

Comparison with handcrafted restart rules. In discrete time, the function-restart and gradient-restart rules of O'Donoghue and Candès are the scores Vˉfunc(k+1)=f(xk)−f(xk+1)\bar V_{\mathrm{func}}(k+1)=f(x_k)-f(x_{k+1}) and Vˉgrad(k+1)=−⟨∇f(yk),xk+1−xk⟩\bar V_{\mathrm{grad}}(k+1)=-\langle\nabla f(y_k),x_{k+1}-x_k\rangle. Replacing xk+1−xkx_{k+1}-x_k by hX˙th\dot X_t and yky_k by Xt+hX˙tX_t+h\dot X_t, and dividing by hh, gives their continuous-time counterparts

Vfunc(t)=−⟨∇f(Xt),X˙t⟩,Vgrad(t)=−⟨∇f(Xt+hX˙t),X˙t⟩.V_{\mathrm{func}}(t)=-\langle\nabla f(X_t),\dot X_t\rangle,\qquad V_{\mathrm{grad}}(t)=-\langle\nabla f(X_t+h\dot X_t),\dot X_t\rangle.

Periodic restart with period pp is the score V(t)=p−tV(t)=p-t. All three rules are therefore fixed, parameter-free choices of the score v(t,Zt;X0)v(t,Z_t;X_0), and each triggers its restart through the same event V(L)=0V(L)=0 of the same hybrid system. Learned Restart differs only in that vθv_\theta is trainable and is optimized with the gradients above. If vθv_\theta is initialized at a handcrafted rule, the monotone-improvement result (Appendix C.2) guarantees that projected gradient steps with a suitable stepsize do not worsen the training objective.

AuthorsOpenReview ↗

For question three

Q. Could the authors report wall-clock time and time-to-accuracy to verify whether Learned Restart offers practical computational advantages after accounting for feature computation and policy inference overhead?

Thank you for this question. The paper compares methods at equal iteration counts only. We have now measured wall-clock time on the Netlib benchmark, with feature computation and policy evaluation included, and will add the results to Appendix G.

Cost per iteration. Under the Table 2 protocol, both PDLP default and the learned policy evaluate a restart test at every iteration. The test computes the KKT residual and the distance travelled for the current iterate and for the averaged iterate.

Setup. We report the Netlib instance woodw. We follow the Table 2 protocol: 50,000 iterations, restart test at every iteration, four random initial points.

MethodTime per iterationKKT after 50,000 iterationsKKT after 72 sTime to PDLP default's final KKTTime to KKT 3e-2Time to KKT 1e-2
Learned1.47 ms9.7e-31.0e-25.5 s9.4 s69 s (median; reached in 11 of 20 runs)
PDLP default1.44 ms4.1e-24.1e-272.1 snot reached (reached in 1 of 4 runs)not reached
PDLP default, test every 64 iterations0.47 ms2.8e-21.7e-210.8 s11.2 snot reached
Periodic-2001.45 ms3.4e-24.0e-219.5 s20.2 snot reached
No restart0.44 ms2.2e-16.2e-2not reachednot reachednot reached

Time per iteration includes feature computation and policy evaluation. 72 s is the time PDLP default needs for 50,000 iterations. "PDLP default's final KKT" is its KKT residual after 50,000 iterations, taken separately for each initial point (2.3e-2 to 8.9e-2). "Not reached" means not reached within the run: 200,000 iterations (about 90 s) for No restart and for PDLP default with the 64-iteration cadence, so that both can use the full 72 s, and 50,000 iterations for the other methods.

AuthorsOpenReview ↗

For question 2

Q. Could the authors provide comparisons among supervised pretraining alone, surrogate-gradient fine-tuning, and alternative methods for learning discrete restart decisions?

The review cites [1–3], but the reference list is not included in the review we received. Could the reviewer tell us which works these are? We would be glad to add a direct comparison with them. Here we give the comparison before and after fine tuning.

QP (NAG backbone)

Surrogate-gradient fine-tuning. The metric is the final gap of the best handcrafted rule (function or gradient restart, chosen per instance), divided by that of the fine-tuned policy. It is a geometric mean over test problems.

Test problemsAfter surrogate-gradient fine-tuning
Fig. 2, d=20d=204.33x
Fig. 2, d=400d=40047.5x
Fig. 2, d=1000d=10001.7e3x
Fig. 6, 8 panels (d∈{500,2000}d\in\{500,2000\}, four κ\kappa)49–5.0e3x
ℓ2\ell_2 logistic regression, 5 LIBSVM datasets × 2 regularization levels (zero-shot)2.39x (wins 78% of instances)

LP (PDHG backbone of PDLP)

Netlib: initialization vs. trained policy. This experiment has no supervised stage. The 16-parameter affine policy is initialized exactly at the PDLP sufficient-decrease test ρ≤0.85\rho\le 0.85, and training starts there. We trained 5 seeds on the 7 smallest instances and compared each trained policy with its initialization on all 65 held-out instances:

ResidualGeometric-mean improvement over the initialization (range over 5 seeds)
KKT1.00–1.61x
Primal1.36–2.62x
Dual0.65–1.26x

Training also reduces the iterations needed to reach a KKT residual of 10−310^{-3} by 16%.

Netlib: the initialization is already good, but the gradient still carries information. Training starts from PDLP's own sufficient-decrease test, which is already a strong restart rule. The room for fine-tuning is therefore limited and the gains above are moderate. To check that this small update comes from the gradient and not from an arbitrary perturbation, we compared it with random directions of the same size. The comparison is on the small tier, at the training horizon of 3000 iterations:

PolicyKKT residual, PDLP default / policy
Initialization (ρ≤0.85\rho\le 0.85)1.01x
Surrogate-gradient update1.79x
30 random directions of the same sizemedian 1.01x, best 1.61x
Negated update (3 seeds)0.56–0.65x

The trained update beats all 30 random directions, and reversing it makes the policy worse than the initialization. So the direction of the surrogate gradient carries the information. We will add these comparisons to the appendix.

Q. For Eq. (75), are the restart decisions of the learned policy robust under objective transformations of the form f→αf+Cf \to \alpha f + C? Could the authors also clarify whether the policy function class contains the handcrafted restart rules as special cases?

Thank you for this question. Our experiments did not consider this transformation, and the features (75) are not invariant to it. With the stepsize s=1/Ls = 1/L, the iterates of NAG and the decisions of function and gradient restart do not change under f→αf+Cf \to \alpha f + C with α>0\alpha > 0. The learned policy, however, sees ff through the coordinates log⁡10f(xk+1)\log_{10} f(x_{k+1}), rkr_k and pkp_k of (75), and these change.

Invariant features can be designed by hand, using ff only through differences divided by the gradient-step scale s∥∇f(xk+1)∥2s\|\nabla f(x_{k+1})\|^2, for example (f(xk)−f(xk+1))/(∣f(xk)−f(xk+1)∣+s∥∇f(xk+1)∥2)\bigl(f(x_k) - f(x_{k+1})\bigr) / \bigl(|f(x_k) - f(x_{k+1})| + s\|\nabla f(x_{k+1})\|^2\bigr). The restart decisions are then unchanged by any α>0\alpha > 0 and CC. Trained with the same procedure, however, this policy performs worse than the current one on the real-data logistic regression benchmark of Table 4. Against the instance-wise best handcrafted rule, the gap ratio is 1.11× (8 of 10 configurations), compared with 2.39× (10 of 10) for the policy with features (75). We will state the lack of invariance as a limitation.

We will clarify that in the strongly convex case, the restart policy with appropriate parameters can realize the hand-crafted baselines. For LP experiments, affine class contains PDLP’s sufficient-decrease test. However, with MLP policies, the rules can be approximated.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.