acceptodds
Under review as a conference paper at ICLR 2027

First passage time in geometric resetting of first-order methods in linear programming

Abstract

Restart strategies play a central role in the performance of first order methods for large-scale linear programming, such as primal-dual hybrid gradient (PDHG) methods. We study mean first passage time of geometric restarting in an abstraction of such methods. This yields a dispersion criterion that characterizes whether introducing a sufficiently small restart probability improves or worsens expected first passage time. We corroborate these criterion through controlled experiments on linear programming instances. The experiments closely agree with the analytical formula, while restarted PDHG experiments exhibit a substantial slowdown in a negative-dispersion regime, consistent with the predicted direction. We further evaluate variants of the restart policy on Mittelmann benchmark instances.

Primary area:
optimization
Keywords:
restarting, geometric restarting, linear programming, PDLP, PDHG

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_vUQxOpenReview ↗
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
  1. The paper establishes regimes at which randomised restarting reduces the iteration count of a first-order method for LP.
  2. A global analysis is provided giving a dichotomy for when restarting is be
  3. Under additional assumptions, the optimal policy is established and shown not to require restarts.
Critical weaknesses
  1. 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.
  2. 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
  1. In line 64, Tp−T0T_p - T_0 are not defined. Could you please elaborate on the definition of each one?
  2. 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?
1 comment
AuthorsOpenReview ↗

Response to Reviewer vUQx: Clarifications and Revisions

We thank the reviewer for a constructive review and a fair summary.

The paper was difficult to follow; keep the high-level ideas in the main text and the technical details in the appendix.

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.

In line 64, TpT_p and T0T_0 are not defined.

TpT_p is the expected number of iterations needed to meet the stopping criterion when, at every iteration, the method is restarted with probability pp, independently of the past, from a fixed restart law; T0T_0 is the same quantity without restarting, the expected restart-free count E[N]\mathbb E[N]. Both are now defined where they first appear, in the contributions, and formally in Section 4.2, where Theorem 2 gives TpT_p in closed form.

Why does the proposed method perform similarly to restarted PDLP? Are there regimes where it should do better? Examples?

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/ε)\log(1/\varepsilon), 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.18p\approx0.18) is consistent with this theoretical interpretation, although we have directly examined restart-free count concentration only on danoint. 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:

  1. The plateau-and-wall family (Theorem 1). A restart that places mass on the wall reaches the target in at most 2ef2\mathrm e f iterations in expectation, whereas any method that restarts to averages of past iterates, PDLP included, needs at least n/δ\sqrt n/\delta. Numerically, sPDLP with snapping needs between 117 and 169 iterations at every nn, against thousands, growing with nn, for restarts to the average (Figure 3, Appendix A).

  2. 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⋅105N=3\cdot10^5 it terminates where both variants without snapping reach the time limit. We do not claim an advantage over PDLP in its default, preconditioned configuration.

  3. The benchmark itself. On app1-2, the instance on which PDLP is slowest, sPDLP needs 4.5 per cent of PDLP's iterations.

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

In the paper the authors explore the role of restarts for primal-dual gradient method. Analyzing the dichotomy of the updates (average length of the convergence phase after the restart), under regularity and stochastic monotonicity assumption they derive results for sPDLP with state-dependent restart scheduling. The authors also validate the findings numerically.

Critical strengths

1)Restarts tend to work in several setups. And with standard probability theory the authors get the results, justifying restarts for prial-dual gradient method.

Critical weaknesses

1)Some introduced notation is not well-defined, like rpkr_p^k, rdkr_d^k (only introduced in the appendix, but it's not clear whether it's the same update rule), and this update rule is used in the main algorithm

2)Section 6 is introducing various variables without any theoretical result.

Questions for authors

1)Does assumption 3 hold in numerical experiments?

2)What breaks if there is no regularity?

3)Is the dichotomy effect noticeable in the experiments?

1 comment
AuthorsOpenReview ↗

Response to Reviewer SQar: Clarifications and Revisions

We thank the reviewer for the careful review and for three precise questions.

Weakness 1. Notation introduced only in the appendix and used in the main algorithm.

We agree that the submission left this unclear. The quantities used by Algorithm 1 are now defined in the main text before they are used:

  • The convergence score sks^k (Section 3, eq. (3)), the sum of the relative primal residual, relative dual residual, and relative duality gap of PDLP's termination test, whose formulas are in Appendix C; and sˉk=s(zˉk)\bar s^k=s(\bar z^k), the score of the running average zˉk\bar z^k, by which the solver stops and which defines the no-restart region (18).

  • The progress variable RkR_k (Section 3), defined by Rk=τ−1∥xk+1−xk∥22+σ−1∥yk+1−yk∥22R_k=\tau^{-1}\lVert x^{k+1}-x^k\rVert_2^2+\sigma^{-1}\lVert y^{k+1}-y^k\rVert_2^2. For the diagnostics in Appendix I, it is evaluated using PDLP's per-iteration step sizes τk=ηk/ωk\tau_k=\eta_k/\omega_k and σk=ηkωk\sigma_k=\eta_k\omega_k. The merit Mk=Rk−1M_k=\sqrt{R_{k-1}} is defined in Section 6.

  • The epoch length LkL_k and the restart count νk\nu_k (Section 6).

The step-size and primal-weight updates are those of PDLP; sPDLP leaves them unchanged and replaces only the restart (Section 6, first paragraph).

Weakness 2. Section 6 introduces various variables without any theoretical result.

This is fair, and the revision says so explicitly. Only the no-restart region (18) is motivated by the theory, through Corollary 5, and even that is imposed on the convergence score rather than on the reduced state. The dependence on LkL_k and νk\nu_k lies outside the model of Section 5, and the floor pmin⁡>0p_{\min}>0 departs from Corollary 5. We present the rule as a heuristic informed by the theory, not as an implementation of Theorem 4. The theory's main use is diagnostic: Corollaries 3 and 4, and the plug-in estimate of Section 4.4, can help assess whether constant-rate restarting is promising.

Q1. Does Assumption 3 hold in numerical experiments?

We have not established Assumption 3 for projected PDHG. Appendix I.2.3 examines it empirically on danoint using 50 restart-free trajectories, placing RkR_k in 20 quantile bins and comparing the conditional distributions of Rk+hR_{k+h}.

Over one iteration, the observed departures from stochastic ordering are small: the largest violation is 0.042, and 3 of 190 bin pairs exceed a Kolmogorov–Smirnov reference. Over 40 iterations, the interval between restart decisions, the departures are substantially larger (0.424, and 118 of 190 pairs). The Kolmogorov–Smirnov reference is descriptive, not a formal significance test, since the observed transition pairs overlap.

A monotone one-step kernel of a time-homogeneous Markov process would give a monotone 40-step kernel, so these findings point to limitations of the reduced-state approximation. Assumption 3 holds for the diffusion surrogate (Lemma 3, Appendix H); for projected PDHG it remains unproven, and Theorem 4 is exact for the surrogate and only suggestive for the algorithm. Section 5 now makes this distinction explicit.

Q2. What breaks if there is no regularity?

Each part of Assumption 2 serves a different step. Compactness of A\mathcal A ensures that the minimum in the Bellman equation (Lemma 1) is attained, at max⁡A\max\mathcal A or min⁡A\min\mathcal A; with, say, A=[0,1)\mathcal A=[0,1) it need not be, and Theorem 4(iii), which asserts that a particular stationary policy is optimal, can fail.

If max⁡A=0\max\mathcal A=0, no restart is possible and the question is empty. Borel kernels make Q⋆Q^\star, C⋆C^\star, and the policies measurable, so that the integrals are defined.

Finally, without some policy of bounded expected count, T⋆T^\star may be infinite on part of the state space, and the comparison of Q⋆Q^\star with C⋆C^\star, on which the threshold rests, carries no information. Under Assumption 1, if A\mathcal A contains a probability aˉ∈(0,1)\bar a\in(0,1), the boundedness condition follows from (13).

Q3. Is the dichotomy effect noticeable in the experiments?

Yes, on one side of it. On danoint we ran the method without restarts from 200 independent restart points (Appendix I.2.2). The counts lie between 165 and 184 termination checks, with squared coefficient of variation about 4⋅10−44\cdot10^{-4}, and the empirical mean residual life lies below the mean at every jj with surviving observations (Figure 5): the empirical distribution is NBUE.

Under the independent-restart model, the empirical NBUE property predicts no benefit from geometric restarting (Corollary 3(i)). Consistently, restarting with probability 0.01 per check raises the observed mean from 174.2 to 361.2 checks (Table 6).

We have not encountered an instance whose counts are NWUE, and do not claim to have verified part (ii) experimentally.

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

This paper likens first order solution methods in linear programming which employ resets, to the problem of stochastic resetting in statistical physics, and uses the results in this domain about a condition based on first passage time, to explore conditions under which resetting helps the convergence of primal dual linear programming. Studies of where and how to do these resets are presented. Unfortunately, the problem is not defined clearly, notation is used that is not defined until later in the paper, and the results are not presented clearly. As such, I found it impossible to evaluate the technical correctness of this paper.

Critical strengths

The problem studied does seem well motivated – in that examining the convergence of the primal dual algorithm with resets could be inspired by the statistical physics results.

If the results in the paper are correct, they do indicate that there is an increase in convergence rate for resetting schemes which satisfy the conditions outlined in the paper.

Critical weaknesses

The critical weakness of this paper is the writing and presentation: the paper is very difficult to impossible to understand. Terms are used without definition, or they are defined later but the reader is not told they are defined later, or the writing just doesn’t make sense. I’ll give some examples below with my corresponding questions.

Questions for authors

Abstract (and appears also in Introduction): “restarting can never help when that count is new better than used in expectation, and can never hurt when it is new worse than used.” What does this mean?

Section 1.1 (Motivating example):
“The following idealised family” – family of what?

“Take a variable w ∈ [0, 1] that enters no constraint and has cost −δ, so that the optimum has w = 1, together with a block min{…} whose constraint matrix has …” – What does it mean to “enter no constraint”? What is a block?

“Take the target to be w = 1 together with a target for the block.” – what is the target for the block?

In the statement of Theorem 1: “Any method whose iterates are PDHG steps or convex combinations of earlier iterates needs at least L iterations from w = 0. This covers PDHG with the restarts of PDLP, which go to averages of past iterates, run with this step size from the origin, and the rule of Section 6, whose restarts go to the segment between the current iterate and the average.” -- First, clearly define iterates, and explain what complex combinations of earlier iterates are. What is the rule of Section 6? It would be better to explain it intuitively in this section rather than requiring a forward reference to a very technical section to find this elusive rule. This section is meant to present an intuitive description of the problem with a simple model, yet it is frustratingly difficult to understand.

2 comments
AuthorsOpenReview ↗

Response to Reviewer DWrj: Clarifications and Revisions

We thank the reviewer for the detailed feedback and for identifying passages that were difficult to follow. We agree that the original submission was too compressed and introduced several concepts without sufficient explanation. We have revised these passages, with changes highlighted in dark blue. We address the questions in order.

"restarting can never help when that count is new better than used in expectation, and can never hurt when it is new worse than used." What does this mean?

Let NN be the number of iterations the method needs from a restart point if it is not restarted again, and let m(j)=E[N−j∣N>j]m(j)=\mathbb E[N-j\mid N>j] be the expected number of further iterations needed by a run that has already spent jj iterations without success. Restarting after jj iterations exchanges m(j)m(j) for m(0)=E[N]m(0)=\mathbb E[N]. If m(j)≤E[N]m(j)\le\mathbb E[N] for every jj, so that an unfinished run never expects to need more than a fresh start would, NN is called new better than used in expectation (NBUE), and restarting at any constant rate cannot reduce the expected count (Corollary 3(i)). If m(j)≥E[N]m(j)\ge\mathbb E[N] for every jj (NWUE), restarting cannot increase it (Corollary 3(ii)). The revised abstract and contributions say this in words, and Corollary 3 defines both terms.

"The following idealised family" – family of what?

Of linear programmes, indexed by the dimension nn and the cost δ\delta. The text now reads "idealised family of LP instances".

What does it mean to "enter no constraint"? What is a block?

The variable ww has a zero column in the constraint matrix: it appears only in the objective, with cost −δ-\delta, and in its bounds 0≤w≤10\le w\le 1, so its optimal value is w=1w=1. The block is an independent LP in the remaining variables, min⁡{c^⊤x^:K^x^≥h^, l^≤x^≤u^}\min\{\hat c^\top\hat x:\hat K\hat x\ge\hat h,\ \hat l\le\hat x\le\hat u\}; the whole instance is the block together with ww. The text now says "an independent LP subproblem, the block" and "ww does not appear in the block's constraints".

What is the target for the block?

A prescribed set B\mathcal B of primal-dual points of the block, for example the points at which PDLP's termination test holds. Theorem 1 needs only that the block reaches B\mathcal B within ff iterations from any starting point, whatever ww does. The target of the whole problem is then the set of points with w=1w=1 and block part in B\mathcal B. This is now stated before the theorem.

Define iterates, explain convex combinations of earlier iterates, and the rule of Section 6.

The iterate zk=(wk,x^k,y^k)z^k=(w^k,\hat x^k,\hat y^k) is the primal-dual point after kk iterations. A convex combination of earlier iterates is a weighted average ∑iλizi\sum_i\lambda_i z^i with λi≥0\lambda_i\ge0 and ∑iλi=1\sum_i\lambda_i=1; the restarts of PDLP, which go to the running average of the iterates since the last restart, are of this kind. When the rule of Section 6 restarts, it chooses among the current iterate, the running average and a random point on the segment between them, so it too stays in the convex hull of the trajectory. Since ww rises by at most τδ\tau\delta per PDHG step, and no average can exceed the largest value already reached, every such method needs at least 1/(τδ)≥n/δ1/(\tau\delta)\ge\sqrt n/\delta iterations from w=0w=0; that is part (i). Snapping, which moves a coordinate directly to the bound its reduced cost points to, leaves the convex hull and so escapes this bound. The revised Theorem 1(i) gives the definition and describes the rule in words.

We hope that Section 1.1 can now be read on its own, and that the reviewer will be able to assess the results. The proofs are in Appendices D, F and G; if any step there remains unclear, we should be grateful to be told which, and will expand it.

Reviewer_DWrjOpenReview ↗

Thank you for your revision, I have reviewed the new version, but didn't have time to check the correctness.

Thank you for revising the paper and improving the clarify. I did not have time in this phase to check the all correctness of the results, but the sections that I called out as not understandable have been revised and are clearer.

Comments on the paper

2 comments
AuthorsOpenReview ↗

Summary of revisions and responses to reviewers

We thank the three reviewers for their careful reading and constructive feedback. We agree that the original submission was too compressed and did not explain several important concepts clearly. We have uploaded a revised manuscript, with changes highlighted in dark blue.

The revision addresses four main areas:

Presentation. Section 1.1 has been rewritten for a reader new to the subject. It now says what the family consists of, what the block and the target are, what an iterate and a convex combination of iterates are, and, in words, what the rule of Section 6 does. The abstract and the list of contributions state the main results without technical vocabulary, and define TpT_p and T0T_0 where they first appear. The numerical illustration of the plateau-and-wall family and its extension to many walls have moved to Appendix A, and the discussion of neural networks to Appendix E.

Theory and heuristic. Section 6 now says plainly which part of the practical rule is motivated by the theory (the no-restart region (18), after Corollary 5) and which is heuristic (the dependence on the epoch length and the restart count, and the floor pmin⁡p_{\min}). Theorem 4 does not cover the practical rule, and the revision says so.

Tests of the assumptions and of the dichotomy. Appendix I.2 reports three controlled experiments on danoint: the renewal formula against independent restarted runs (I.2.1); an empirical test of the dichotomy of Corollary 3 from 200 restart-free runs (I.2.2); and a test of the stochastic monotonicity of Assumption 3 (I.2.3).

A regime in which restarting helps. Appendix B and Figures 1 and 2 add PageRank LPs in which the walls of Theorem 1 appear in the constraints, so that presolve cannot remove them. With fixed step sizes and no diagonal preconditioning, sPDLP with snapping needs up to 13.5 times fewer iterations than PDLP. Appendix I.1 runs the same variant on the MIPLIB relaxations, where it costs little: over the 67 instances with a ratio, its geometric-mean ratios to PDLP are 1.133 in iterations and 1.006 in time.

The main benchmark result is unchanged: on the MIPLIB relaxations the stochastic rule is close to neutral. Corollaries 3 and 4 explain why this is to be expected when restart-free iteration counts are concentrated, as we measured on danoint (Appendix I.2.2), and Section 1.1 and Appendix B show where restarting can help.

AuthorsOpenReview ↗

Further questions?

Dear reviewers,

if you have any further questions, please do ask! We would be delighted to answer any further questions prior to the rebuttal window closing.

Thanks! The authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.