- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
The paper studies when randomised restarting reduces the expected iteration count of a first-order method for linear programming and how the restart probability should depend on the state of the iteration. The authors propose a renewal model of restarted first-order methods and provide the expected iteration count. A global analysis is also provided and an optimal state dependent policy is established. Experiments showcase that a state dependent update rule is similar in iteration count to restarted PDLP in 66 setups, while being faster on the instance that PDLP is slowest.
Critical strengths
- The paper establishes regimes at which randomised restarting reduces the iteration count of a first-order method for LP.
- A global analysis is provided giving a dichotomy for when restarting is be
- Under additional assumptions, the optimal policy is established and shown not to require restarts.
Critical weaknesses
- The paper was difficult to follow and some parts might not be fully understood. I would recommend revising the writing with keeping more of a high level idea behind the results and presenting the technical details in Appendix.
- I would expect the experiments to show significant gains for the proposed state-dependent policy. However, my understanding is that the performance of the method is similar to restarted PDLP and only in one instance it is better than that.
Questions for authors
- In line 64, are not defined. Could you please elaborate on the definition of each one?
- Why the proposed method performs similarly to restarted PDLP in the provided experiments? Are there particular regimes where the method is expected to perform better than it? Could you provide corresponding examples of that?
Response to Reviewer vUQx: Clarifications and Revisions
We thank the reviewer for a constructive review and a fair summary.
We have done this. Section 1.1 now presents the plateau-and-wall example in words alongside the theorem; its numerical illustration and the many-walls extension are in Appendix A, the connection with neural networks in Appendix E, and all proofs in Appendices D, F and G. The contributions state each result without technical vocabulary.
Tp is the expected number of iterations needed to meet the stopping criterion when, at every iteration, the method is restarted with probability p, independently of the past, from a fixed restart law; T0 is the same quantity without restarting, the expected restart-free count E[N]. Both are now defined where they first appear, in the contributions, and formally in Section 4.2, where Theorem 2 gives Tp in closed form.
Why similar. Restarting is most promising when the iteration count from a restart point varies substantially, so that a long run may indicate a slow mode worth abandoning. When the count obeys a two-sided linear-rate bound (the upper half is what the sharpness analysis of Applegate et al. (2022) gives for restarted PDHG), it varies by an additive constant while growing like log(1/ε), and Corollary 4 shows that the best speed-up from geometric restarting tends to one. When the restart-free count is NBUE, Corollary 3 shows that, under the independent-restart model, no constant restart rate can improve its expected value.
We observed an empirical NBUE profile on
danoint(Appendix I.2.2): restart-free counts between 165 and 184 checks, with a slowdown under restarting. The near-neutral benchmark result (geometric-mean iteration ratio 1.074; sign test p≈0.18) is consistent with this theoretical interpretation, although we have directly examined restart-free count concentration only ondanoint. The plug-in estimate of Section 4.4 can help assess from pilot runs whether constant-rate restarting is promising for a given instance.Where it does better. Restarting can help when the restart-free count has a favorable fast mode that a restart can reach. Snapping additionally allows the algorithm to leave the convex hull of past iterates, potentially overcoming the limitation illustrated by Theorem 1. Three examples:
The plateau-and-wall family (Theorem 1). A restart that places mass on the wall reaches the target in at most 2ef iterations in expectation, whereas any method that restarts to averages of past iterates, PDLP included, needs at least n/δ. Numerically, sPDLP with snapping needs between 117 and 169 iterations at every n, against thousands, growing with n, for restarts to the average (Figure 3, Appendix A).
PageRank LPs with coupled walls (new; Appendix B, Figures 1 and 2, Table 2). Here the walls appear in the constraints, rather than as unconstrained variables that presolve can trivially eliminate. With fixed step sizes and no diagonal preconditioning, sPDLP with snapping needs up to 13.5 times fewer iterations than PDLP, and at N=3⋅105 it terminates where both variants without snapping reach the time limit. We do not claim an advantage over PDLP in its default, preconditioned configuration.
The benchmark itself. On
app1-2, the instance on which PDLP is slowest, sPDLP needs 4.5 per cent of PDLP's iterations.