Enhanced PDHG for Linear Programming with Online Preconditioning

Haihao Lu; Wanyu Zhang

REVIEW 4 major objections 4 minor 16 references

Enhanced PDHG for Linear Programming with Online Preconditioning

T0 review · 4 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Online preconditioning that adapts the primal and dual scalings of PDHG reduces both iteration counts and overall solving time on standard LP benchmarks.

desk verdict A clean, honest engineering paper with real empirical promise, but the headline acceleration rests on per-instance learning-rate selection and needs a fixed-rate test before I'd trust the numbers as deployable. read the letter →

arxiv 2506.17650 v1 pith:KQVSOXYS submitted 2025-06-21 math.OC

Haihao Lu , Wanyu Zhang This is my paper · ORCID

classification math.OC MSC 90C0590C0690C25

keywords linearprogrammingprimal-dualhybridgradientonlinepreconditioningscaledmethodfirst-ordermethodsGPUcomputingcuPDLP.jlPDLP

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper tries to establish that the preconditioners inside the primal-dual hybrid gradient (PDHG) method for linear programming can be learned online rather than fixed by a static scaling rule. It proposes updating diagonal primal and dual preconditioners with online gradient descent on Lagrangian-difference losses, and adds two practical enhancements: normalized losses and infrequent updates. Implemented on top of vanilla PDHG and on the GPU solver cuPDLP.jl, the method reports about 10% lower shifted-geometric-mean iteration counts on Netlib and MIPLIB 2017 relaxations, roughly 30% lower mean iteration counts on MIPLIB, and about 20% lower geometric-mean solve time on large instances. A sympathetic reader would care because PDHG is a leading first-order LP solver on GPUs, and a preconditioner update that costs only vector-vector operations could make large-scale LP solving faster without changing the algorithm's parallel structure.

What carries the argument

The central mechanism is the online scaled gradient method applied to preconditioner selection inside preconditioned PDHG. The algorithm treats the choice of $T_k$ and $\Sigma_k$ as an online decision problem whose feedback losses measure the one-step change in the Lagrangian from the primal and dual updates, and online gradient descent with AdaGrad then adjusts each diagonal entry. The key identity is the coordinate-wise gradient formula, for example $\nabla\ell^p_k(T_k)=-\frac{\eta_k}{\omega}[(c-A^\top\lambda_k)\circ I\{x_{k+1/2}(T_k)\ge 0\}](c-A^\top\lambda_k)^\top$, which keeps updates cheap. The enhancements of normalizing by $\|c-A^\top\lambda_k\|^2$ and $\|b-Ax_k\|^2$, and updating only every $\phi$ iterations, make the learned preconditioners practical inside a restarted PDHG solver.

What would settle it

Run the best variant (with normalization and infrequent updates) using a single fixed learning rate, say $10^{-6}$, on every Netlib and MIPLIB instance instead of choosing per instance from $\{10^{-5},10^{-6},10^{-7}\}$. If the aggregate iteration counts or solve times are not consistently below the cuPDLP.jl defaults, the claimed practical speedup is an artifact of per-instance tuning.

Watch

Extended reading notes

Core claim

The paper's central claim is that online preconditioning effectively reduces iteration counts and overall solving time for PDHG-based LP solvers. At each PDHG iteration the method maintains diagonal preconditioners $T_k$ and $\Sigma_k$, updates them by online gradient descent on the losses $\ell^p_k(T_k)=L(x_{k+1}(T_k),\lambda_k)-L(x_k,\lambda_k)$ and $\ell^d_k(\Sigma_k)=L(x_k,\lambda_k)-L(x_k,\lambda_{k+1}(\Sigma_k))$, and projects back to nonnegative diagonal matrices. The coordinate-wise updates require only Hadamard products and vector-vector outer products, so the overhead is minimal and GPU-friendly. The authors integrate this scheme with PDLP's adaptive restarts, adaptive stepsize, and primal weight, add normalized loss and infrequent updates (every $\phi=20$ iterations), and report experiments on Netlib and MIPLIB 2017 where the best variant reduces iteration counts by roughly 10% (SGM10) and solve time by about 20% on large instances. They also state that the online learning rate is currently selected per instance and that theoretical convergence guarantees remain open.

Load-bearing premise

The method's practical success depends on choosing a good learning rate for each problem instance: the authors pick it from a small grid per instance, and they give no evidence that one fixed rate works across instances or that the online gradient updates always preserve convergence.

Editorial extensions

If this is right

If the reported gains hold, GPU-based PDHG LP solvers can be made faster on large-scale instances by adding only vector-vector operations, preserving the parallelism that makes first-order LP solvers attractive.
Normalized online losses improve iteration efficiency, so future variants can trade the extra norm-computation overhead against time savings by updating the preconditioners less frequently.
Infrequent updates (every 20 iterations) retain most of the iteration-count benefit while cutting runtime, suggesting the preconditioner can be learned at very low computational cost.
The larger gains on instances needing more than 5000 iterations indicate that online preconditioning matters most where PDHG spends many iterations, such as large or ill-conditioned LPs.
A tuning-free learning-rate schedule would be needed to make the method a drop-in solver component, since the current results select the rate per instance from a small grid.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Beyond the paper: because the preconditioner updates are coordinate-wise and independent of matrix factorization, the same online update could be layered on top of stronger static scalings such as Ruiz or Pock-Chambolle preconditioning instead of starting from the default preprocessing.
Beyond the paper: the observed two-phase convergence suggests the main benefit is shortening the initial flat phase, so combining online preconditioning with restart heuristics that detect phase transitions might compound the gains.
Beyond the paper: a natural testable extension is to apply the same Lagrangian-feedback online gradient descent to the step-size parameters themselves, replacing the per-instance grid search by an adaptive schedule.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Jin, here's the quick take on Lu-Zhang, Enhanced PDHG with Online Preconditioning. It is a solid engineering paper, not a breakthrough. The new thing is genuinely new: they bring online scaled gradient methods into PDHG preconditioner selection for LP, derive the coordinate-wise gradients for the Lagrangian feedback losses, and bolt the scheme onto PDLP/cuPDLP.jl with two sensible tweaks—normalized losses and infrequent updates. The implementation is straightforward and the experimental setup is transparent: vector-vector overhead, benchmark on Netlib and MIPLIB, and the variant tables are there to see. I believe the derivation in Section 3.1 is clean, and the infrequent update idea is practically motivated.

The soft spots are exactly the ones the stress test flags. Section 4.1 says the AdaGrad learning rate is chosen per instance from a three-value grid to minimize iterations. Remark 1 admits it. The conclusion admits it. Figure 1 shows convergence is strongly rate-dependent. So the reported 10% SGM10 iteration reductions and ~20% time reductions on large MIPLIB instances are, as reported, oracle-style numbers. They may not survive a single fixed rate. That does not kill the idea—online preconditioning might still be useful with a default rate or a robust schedule—but the central practical claim ("effectively reduces both iteration counts and overall solving time") is not yet established in a deployable sense. The absence of repeated runs and error bars is a secondary concern; for GPU timing, run-to-run variation is real. Also, the normalization variant Norm-Freq increases Netlib time relative to PDLP (6.47 vs 5.88 s), so the overhead story is mixed.

What holds up: the method is simple, parallelizable, and built on a defensible online-learning analogy. The citation pattern is fine—self-cites are to PDLP, cuPDLP, and the OSGM line they extend, all appropriate. No fitted constants are hidden in a prediction; the tuning is acknowledged. A code release would help full reproducibility, but the paper is transparent about its methods and settings.

Who is this for? People working on first-order LP solvers and anyone who wants to try a cheap preconditioning layer on PDHG. It deserves a serious referee. The right review outcome is major revision with a fixed-rate or tuning-free experiment, repeated runs, and ideally some stability or convergence guarantee for the preconditioner updates. As is, I'd treat the acceleration claims as promising pilot evidence, not validated. Yes, send to review.

Referee Report

4 major / 4 minor

Summary. The paper proposes an online preconditioning method for PDHG for linear programming. Section 3 derives online gradient descent updates for diagonal primal and dual preconditioners from one-step Lagrangian losses, integrates the scheme into the PDLP framework, and introduces normalized losses and infrequent updates. Section 4 reports experiments on Netlib and MIPLIB instances showing roughly 10% reductions in shifted geometric mean iteration counts and, for the best variant Norm-Infreq, reductions in geometric mean solving time. The paper explicitly acknowledges in the conclusion that the results rely on per-instance tuning of the online learning rate and that theoretical convergence guarantees remain open.

Significance. If the empirical claims held under a fixed, deployable configuration, the method would be a valuable low-overhead enhancement to GPU-based PDHG solvers. The Section 3.1 gradient derivation is compact and appears correct, the per-iteration overhead is only vector-vector operations, and the experiments span standard benchmark sets with ablation of the two proposed enhancements. However, the significance is currently limited by the oracle-style per-instance selection of the learning rate, by inconsistent gains across the four variants, and by the absence of any convergence or boundedness guarantee. I do not see evidence of hidden circularity: the preconditioners are learned from the same problem's feedback, which is intrinsic to the method, and the per-instance tuning is openly disclosed.

major comments (4)

[Section 4.1, Remark 1] The online learning rate is selected per instance from {1e-1,1e-2,1e-3} in Section 4.2 and from {1e-5,1e-6,1e-7} in Section 4.3 to minimize iteration counts on the same instances used for evaluation. Figure 1 shows that convergence behavior is strongly rate-dependent, with qualitatively different behavior across the tested rates. Since Remark 1 confirms that a tuning-free version is not yet available, the reported iteration and time reductions in Tables 1-3 are consistent with oracle selection rather than with a method that a user can deploy with fixed hyperparameters. The central claim that online preconditioning effectively reduces iteration counts and overall solving time requires either a single fixed rate that works across all instances, a principled adaptive rate with no per-instance oracle, or a tuning-set evaluation separated from the test instances.
[Tables 1-2 and Abstract] The abstract claims that online preconditioning effectively reduces both iteration counts and overall solving time, but the evidence is not uniform across the four variants. In Table 1, Norm-Freq increases the Netlib geometric mean time from 5.88 to 6.47 seconds relative to the PDLP baseline, despite reducing iteration counts. In Table 2, NoNorm-Freq increases the MIPLIB geometric mean time from 3.63 to 4.82 seconds and reduces the number of OPTIMAL instances from 346 to 341. Only the infrequent-update variants consistently improve time. Furthermore, the #Iter and Time metrics in Section 4.1 are computed only over instances where all compared methods reach OPTIMAL; when a variant solves fewer instances than the baseline, this common-instance restriction can mask failures. The paper should either restrict the central claim to the configurations that support it or explain why the inconsistent variants are still within the claimed behavior.
[Section 3.2 (Normalized online loss) and Algorithm 1] The text says the normalized online loss divides the feedback by the squared norms of c - A^T lambda_k and b - A x_k, but Algorithm 1, line 7 divides the gradients by the norms themselves, not by their squares. If the normalization is by squared norms, the gradient of the normalized loss should be the original gradient divided by the squared norm; if the implementation divides only by the norm, then it implements a different normalization than the one described. This discrepancy is material because the normalized-loss variants are a central part of the experimental comparison, and the mismatch affects the numerical results in Tables 1-3. Please clarify the intended normalization and ensure the description and code agree.
[Section 3.2, Algorithm 1, and Conclusion] The preconditioners are updated by online gradient descent and projected only onto the set of nonnegative diagonal matrices, with no upper bound or explicit safeguard ensuring that the resulting preconditioners keep the PDHG iteration in a convergence regime. The paper acknowledges in the Conclusion that theoretical convergence guarantees remain open. As a result, there is no a priori reason that the per-instance tuned rates transfer to unseen instances, and nothing prevents the learned preconditioners from leaving the stability region on some problem. I am not requiring a full convergence proof for an empirical paper, but at minimum the authors should report whether any instance in the benchmark exhibited divergence or unbounded preconditioner entries, and should discuss a practical safeguard or boundedness condition.

minor comments (4)

[Figure 1] The caption does not specify the learning rate values, the exact instances shown, or the axis definitions; please add these details so the three convergence-behavior classes can be interpreted.
[Section 4.1 (Computing environment)] The reported times appear to come from a single run on a shared GPU cluster; given possible run-to-run variability, a small number of repeated runs or a statement about variance would strengthen the time comparisons.
[General] The paper does not mention availability of the implementation code or a reproducibility package; providing the code used for the experiments would be valuable given the implementation-specific nature of the enhancements.
[Section 4.2] The text says the experiments use normalized online loss and disable infrequent updates, but it does not state which of the four variant names from Section 4.3 corresponds to the Figure 1 implementation; please label it explicitly.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the online preconditioner updates are derived from Lagrangian feedback, and the per-instance learning-rate tuning is an acknowledged evaluation limitation rather than a derivation-level circular step.

full rationale

The central derivation is self-contained. In Section 3.1, the losses are defined directly from the change in the Lagrangian value caused by the primal and dual updates (equation 5), and the preconditioner updates are obtained by online gradient descent on those losses. No fitted constant or excluded quantity is embedded in the update rule; the method is an algorithmic extension of the online scaled gradient method to PDHG. The numerical claims are empirical benchmarks, not first-principles predictions derived from the method's equations. The per-instance selection of the online learning rate (Section 4.1 and Remark 1) is a real methodological weakness: choosing the rate that minimizes iteration counts on the same instances used for evaluation can inflate the reported improvements, and the paper explicitly concedes this in Remark 1 and the Conclusion. However, this is an experimental-design issue, not circularity in the derivation chain; the reported iteration counts are measurements after tuning, not quantities forced by the method's definition. The self-citations to PDLP [1] and cuPDLP.jl [10] are references to the baseline implementations on which the method is built, and they are not used to justify the correctness or novelty of the online preconditioning update. No uniqueness theorem, no ansatz smuggled through citation, and no renaming of a known result were found. The derivation chain from the Lagrangian feedback to the preconditioner update is therefore independent of the paper's empirical conclusions.

Assumptions & free parameters 2 free parameters · 3 assumptions · 0 invented entities

The central empirical claim rests on a per-instance tuned learning rate and a fixed update frequency; no new theoretical entities are introduced.

free parameters (2)

online learning rate alpha = per-instance selected from 10^-1,10^-2,10^-3 (Sec 4.2) or 10^-5,10^-6,10^-7 (Sec 4.3)
The AdaGrad learning rate is tuned per instance to minimize iterations, so reported gains represent best-case over this grid.
update frequency phi = 20
Chosen as a fixed practical value; its effect on runtime vs iteration count is not ablated across different values.

assumptions (3)

standard math The Lagrangian losses and their gradients are well-defined for the projection step (indicator function derivative)
Used in Section 3.1 to derive update rules; assumes differentiability almost everywhere.
domain assumption The PDHG iterates and preconditioner updates remain bounded so online gradient descent is meaningful
No proof is given that the online scheme maintains the assumptions of OSGM convergence; the paper states convergence guarantees are open.
domain assumption The experimental setup of [1] for MIPLIB instances is applicable
They follow the 383 MIP relaxation setup from [1], which is accepted as a standard benchmark, but the chosen instances may affect the results.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Enhanced PDHG for Linear Programming with Online Preconditioning." pith.science (2026). https://pith.science/paper/KQVSOXYS

@misc{pith2026250617650,
  author       = {Pith},
  title        = {Pith review of: Enhanced PDHG for Linear Programming with Online Preconditioning},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KQVSOXYS}},
  note         = {Machine review of arXiv:2506.17650}
}

read the original abstract

We present an online preconditioning technique for the primal-dual hybrid gradient (PDHG) algorithm for linear programming (LP). The method adaptively updates primal and dual preconditioners using an online optimization framework. To improve its practical performance, we introduce several algorithmic enhancements, including using normalized online loss functions and updating preconditioners infrequently. We implement the technique on top of vanilla PDHG and the GPU-based LP solver cuPDLP.jl, and benchmark its performance on standard LP datasets. Our numerical experiments demonstrate that online preconditioning effectively reduces both iteration counts and overall solving time.

Figures

Figures reproduced from arXiv: 2506.17650 by the authors.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

16 extracted references · 6 canonical work pages

[1]

Practical large-scale linear programming using primal-dual hybrid gradient

David Applegate, Mateo D ´ ıaz, Oliver Hinder, Haihao Lu, Miles Lubin, Brendan O’Donoghue, and Warren Schudy. Practical large-scale linear programming using primal-dual hybrid gradient. Advances in Neural Information Processing Systems, 34:20243–20257, 2021

work page 2021
[2]

Pdlp: A practical first-order method for large-scale linear programming

David Applegate, Mateo D ´ ıaz, Oliver Hinder, Haihao Lu, Miles Lubin, Brendan O’Donoghue, and Warren Schudy. Pdlp: A practical first-order method for large-scale linear programming. arXiv preprint arXiv:2501.07018, 2025

arXiv 2025
[3]

Online learning rate adaptation with hypergradient descent

Atılım G¨ une¸ s Baydin, Robert Cornish, David Mart ´ ınez Rubio, Mark Schmidt, and Frank Wood. Online learning rate adaptation with hypergradient descent. In Sixth International Conference on Learning Representations (ICLR), Vancouver, Canada, April 30 – May 3, 2018, 2018

work page 2018
[4]

Provable and Practical Online Learning Rate Adaptation with Hypergradient Descent

Ya-Chi Chu, Wenzhi Gao, Yinyu Ye, and Madeleine Udell. Provable and practical online learning rate adaptation with hypergradient descent. arXiv preprint arXiv:2502.11229, 2025

work page Pith review arXiv 2025
[5]

Adaptive subgradient methods for online learning and stochastic optimization

John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011

2011
[6]

Gradient methods with online scaling

Wenzhi Gao, Ya-Chi Chu, Yinyu Ye, and Madeleine Udell. Gradient methods with online scaling. arXiv preprint arXiv:2411.01803, 2024

arXiv 2024
[7]

Gradient methods with online scaling part i

Wenzhi Gao, Ya-Chi Chu, Yinyu Ye, and Madeleine Udell. Gradient methods with online scaling part i. theoretical foundations, 2025. URL https://arxiv.org/abs/2505.23081

arXiv 2025
[8]

Electronic mail distribution of linear programming test problems

David M Gay. Electronic mail distribution of linear programming test problems. Mathematical Pro- gramming Society COAL Newsletter, 13:10–12, 1985

work page 1985

Show all 16 references

[9]

Miplib 2017: data- driven compilation of the 6th mixed-integer programming library

Ambros Gleixner, Gregor Hendel, Gerald Gamrath, Tobias Achterberg, Michael Bastubbe, Timo Berthold, Philipp Christophel, Kati Jarck, Thorsten Koch, Jeff Linderoth, et al. Miplib 2017: data- driven compilation of the 6th mixed-integer programming library. Mathematical Programmi...

2017
[10]

Haihao Lu and Jinwen Yang. cupdlp. jl: A gpu implementation of restarted primal-dual hybrid gradient for linear programming in julia. arXiv preprint arXiv:2311.12180, 2023. 8

2023 arXiv
[11]

On the geometry and refined rate of primal–dual hybrid gradient for linear programming

Haihao Lu and Jinwen Yang. On the geometry and refined rate of primal–dual hybrid gradient for linear programming. Mathematical Programming, pages 1–39, 2024

2024
[12]

Restarted halpern pdhg for linear programming

Haihao Lu and Jinwen Yang. Restarted halpern pdhg for linear programming. arXiv preprint arXiv:2407.16144, 2024

2024 arXiv
[13]

cupdlp-c: A strengthened implementation of cupdlp for linear programming by c language

Haihao Lu, Jinwen Yang, Haodong Hu, Qi Huangfu, Jinsong Liu, Tianhao Liu, Yinyu Ye, Chuwen Zhang, and Dongdong Ge. cupdlp-c: A strengthened implementation of cupdlp for linear programming by c language. arXiv preprint arXiv:2312.14832, 2023

2023 arXiv
[14]

Diagonal preconditioning for first order primal-dual algorithms in convex optimization

Thomas Pock and Antonin Chambolle. Diagonal preconditioning for first order primal-dual algorithms in convex optimization. In 2011 International Conference on Computer Vision, pages 1762–1769. IEEE, 2011

2011
[15]

A scaling algorithm to equilibrate both rows and columns norms in matrices

Daniel Ruiz. A scaling algorithm to equilibrate both rows and columns norms in matrices. Technical report, CM-P00040415, 2001

2001
[16]

The role of level-set geometry on the performance of pdhg for conic linear optimization

Zikai Xiong and Robert M Freund. The role of level-set geometry on the performance of pdhg for conic linear optimization. arXiv preprint arXiv:2406.01942, 2024. 9

2024 arXiv

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.

[1] [1]

Practical large-scale linear programming using primal-dual hybrid gradient

David Applegate, Mateo D ´ ıaz, Oliver Hinder, Haihao Lu, Miles Lubin, Brendan O’Donoghue, and Warren Schudy. Practical large-scale linear programming using primal-dual hybrid gradient. Advances in Neural Information Processing Systems, 34:20243–20257, 2021

work page 2021

[2] [2]

Pdlp: A practical first-order method for large-scale linear programming

David Applegate, Mateo D ´ ıaz, Oliver Hinder, Haihao Lu, Miles Lubin, Brendan O’Donoghue, and Warren Schudy. Pdlp: A practical first-order method for large-scale linear programming. arXiv preprint arXiv:2501.07018, 2025

arXiv 2025

[3] [3]

Online learning rate adaptation with hypergradient descent

Atılım G¨ une¸ s Baydin, Robert Cornish, David Mart ´ ınez Rubio, Mark Schmidt, and Frank Wood. Online learning rate adaptation with hypergradient descent. In Sixth International Conference on Learning Representations (ICLR), Vancouver, Canada, April 30 – May 3, 2018, 2018

work page 2018

[4] [4]

Provable and Practical Online Learning Rate Adaptation with Hypergradient Descent

Ya-Chi Chu, Wenzhi Gao, Yinyu Ye, and Madeleine Udell. Provable and practical online learning rate adaptation with hypergradient descent. arXiv preprint arXiv:2502.11229, 2025

work page Pith review arXiv 2025

[5] [5]

Adaptive subgradient methods for online learning and stochastic optimization

John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011

2011

[6] [6]

Gradient methods with online scaling

Wenzhi Gao, Ya-Chi Chu, Yinyu Ye, and Madeleine Udell. Gradient methods with online scaling. arXiv preprint arXiv:2411.01803, 2024

arXiv 2024

[7] [7]

Gradient methods with online scaling part i

Wenzhi Gao, Ya-Chi Chu, Yinyu Ye, and Madeleine Udell. Gradient methods with online scaling part i. theoretical foundations, 2025. URL https://arxiv.org/abs/2505.23081

arXiv 2025

[8] [8]

Electronic mail distribution of linear programming test problems

David M Gay. Electronic mail distribution of linear programming test problems. Mathematical Pro- gramming Society COAL Newsletter, 13:10–12, 1985

work page 1985