- 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
- 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.
- 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.
- 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
- 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.
- 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.
- 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.
- 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
-
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.
-
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. 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 only when the score changes sign between two consecutive evaluations, ; 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 with , 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 . 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 , so it does not restart before this warm start (App. E, F). The Netlib score is initialized exactly at the PDLP rule , 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 is kept away from zero by a small floor (of order ; 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.
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 (θ 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 and momentum βj=(j−1)/(j+2+c), with j the steps since the last restart; (α,c)=(1,0) is Algorithm 1. All arms use the Sec. 4.1 training distribution (d=20, κ∈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).
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 (1.32 to 1.38 over seeds); the momentum offset stays near Algorithm 1 (c=−0.06, −1.25 to 0.31). The gain comes from a longer step, which a restart rule adapted to it makes usable:
3. The surrogate gradient points the right way for the schedule too. Derivative of the training objective with respect to α at Algorithm 1's schedule, against central finite differences (h=0.03):
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):
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):
Joint learning improves on the PDLP default on every tier and is on par with restart-only learning.