acceptodds
Under review as a conference paper at ICLR 2027

Reinforcement Learning to Accelerate Primal-Dual Hybrid Gradient for Linear Programming

Abstract

Primal dual hybrid gradient (PDHG) methods solve large-scale linear programs (LPs) using GPU-friendly matrix vector products and projections, but their practical performance depends on coordinating algorithm parameters, acceleration, and restarts. We introduce GALLOP, which uses reinforcement learning to jointly learn continuous algorithm parameters and discrete restart decisions without differentiating through the solver. Its generalized accelerated PDHG update combines separate primal and dual extrapolation, history corrections, and restart anchoring with independently adjustable coefficients. We train a dimension-agnostic feedback policy using a groupwise proximal policy optimization objective that clips likelihood ratios separately for different control groups and excludes inactive acceleration controls on restart transitions. We evaluate GALLOP on six LP families and a public item-placement benchmark. On the main evaluation settings across the six families, GALLOP reduces iteration counts by factors of - and achieves up to a speedup in algorithm wall-clock time over MPAX. With one policy trained per family, the learned policies generalize without retraining to within-family LPs - larger than the largest training instances, including Transport LPs with million variables.

Primary area:
optimization
Keywords:
Linear programming, Primal-dual hybrid gradient, Learning to optimize, Reinforcement learning

Reviews

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

This paper proposes GALLOP, a reinforcement learning framework for accelerating primal–dual hybrid gradient (PDHG) methods for linear programming. The method introduces a generalized accelerated PDHG update that combines separate primal and dual extrapolation, history corrections, and restart-anchor corrections. A dimension-agnostic policy jointly controls step sizes, primal weights, acceleration coefficients, and restart decisions. Training uses a groupwise PPO objective that separately clips likelihood ratios for different control groups and excludes inactive acceleration controls on restart transitions. Experiments cover six LP families and a public item-placement benchmark, reporting reduced iteration counts, algorithm wall-clock speedups of up to 16× over MPAX, and within-family size generalization to instances with up to 400× more variables than the largest training instances.

Critical strengths
  1. The paper addresses an important practical problem with a well-motivated learning formulation. The performance of PDHG-based solvers depends on coordinating several interacting controls. Learning their joint feedback policy throughout the solve offers a meaningful alternative to independently designed heuristics. The inclusion of discrete restart decisions also provides a concrete motivation for reinforcement learning.

  2. The experiments provide substantive evidence of solver acceleration. The main comparisons use a common relative KKT tolerance of 10−610^{-6} and report iteration counts, matrix–vector products, and algorithm wall-clock time. GALLOP also improves over a hand-tuned baseline sharing its solver implementation, indicating that the gains cannot be explained entirely by implementation differences with MPAX.

  3. The dimension-agnostic policy demonstrates valuable size generalization. The Transport policy scales from training instances with at most 25,600 variables to test instances with 10.24 million variables without retraining, while retaining substantial performance gains. Results on the public item-placement benchmark provide additional evidence beyond the six synthetic families.

  4. The paper provides detailed implementation descriptions. The appendix specifies action transformations, observations, preconditioning, caching, and training procedures, facilitating understanding and reproduction of the method.

Critical weaknesses
  1. Groupwise PPO lacks a theoretical analysis of its joint-policy update properties. Equation (9) separately clips the likelihood ratio of each control group, but when multiple groups are updated simultaneously, their joint likelihood ratio can still exceed the clipping range imposed on individual groups. Consequently, separate clipping does not directly impose an equivalent constraint on the joint update. The paper explains how this design avoids gradient suppression across control groups, but does not establish its mathematical relationship to the joint-policy objective or provide conditions controlling the magnitude of the joint update.

  2. The theoretical conclusion of Proposition 3.1 relies on strong convergence assumptions. The proposition assumes that both the output iterates ztz_t and the accelerated inputs z^t\hat z_t converge before establishing optimality of the limit. Because PDHG involves projections, convergence of the outputs does not directly imply convergence of the inputs. The appendix verifies coefficient bounds and the vanishing anchor correction, but retains input convergence as an additional assumption. The result therefore does not establish an optimality guarantee based solely on output convergence, nor does it provide a counterexample explaining the necessity of the additional assumption. Its theoretical contribution is consequently limited.

  3. Figure 1 and Figure 2 show clear signs of AI generation. The trajectories in Figure 1 serve to illustrate the algorithm’s behavior. If the curves were synthesized by AI but presented as real experimental data, this would be unacceptable. The authors should provide plots generated from real data using Python or other scientific plotting tools. Figure 2 likewise shows clear signs of AI generation. Given ICLR’s requirements for accurate technical communication, the authors should manually redraw the main methodological figure.

Questions for authors

See Weaknesses.

2 comments

We thank the reviewer for the constructive comments.

Q1. Relation to joint policy objective and control of joint update

Relationship to the joint-policy objective(Standard PPO). Groupwise PPO omits higher-order cross-group terms in ρt−1ρ_t-1 and separately clips each group likelihood ratio to reflect GA-PDHG's distinct control roles.

Specifically, expanding ρt−1ρ_t-1 yields

+\sum_{\substack{S⊆\mathcal G \|S|≥2}}\prod_{j∈S}(ρ_t^j-1).$$ Groupwise PPO constructs a surrogate objective by discarding the second sum and clipping each remaining group term separately. This removes higher-order coupling between group ratios from the objective. This design fits GA-PDHG, where each control variables have distinct roles and are typically governed by separate rules (Section 2.2). See Section 3.3 for more details. **Magnitude of the joint update.** Per-group KL bounds suffice to bound the joint KL, but clipping does not enforce the bounds. In practice, empirical joint KL can be controlled by tuning each group clipping ranges. Let $D_j$ denote the old-to-new KL of group $j$ before masking and let $p^e_{\mathrm{old}}$ be the old restart probability. For the policy over executed actions, $π_{θ,\mathrm{act}}$, marginalizing inactive acceleration controls gives $$D_{\mathrm{KL}}(π_{\mathrm{old,act}}\|π_{θ,\mathrm{act}}) =D_e+D_η+D_ω +(1-p^e_{\mathrm{old}})(D_β+D_{αζ}).$$ Their KL contributions are weighted by the old non-restart probability because they are active only without a restart and the KL expectation is taken under the old policy. This decomposition gives a sufficient condition for bounding the joint KL. Suppose that, at the same observation, $D_j≤δ_j$ for every $j∈\{e,η,ω,β,αζ\}$, where $δ_j≥0$ are prescribed finite KL budgets. Then $$D_{\mathrm{KL}}(π_{\mathrm{old,act}}\|π_{θ,\mathrm{act}}) ≤δ_e+δ_η+δ_ω +(1-p^e_{\mathrm{old}})(δ_β+δ_{αζ}).$$ Our groupwise PPO objective, however, does not enforce these per-group KL bounds. As in standard PPO-Clip, clipping modifies the surrogate objective rather than imposing hard constraints on the actual likelihood ratios. We added this discussion in Appendix F.3. In practice, tuning clipping ranges can control empirical joint KL. For the action-grouping experiment in Section 4.5, we monitored per-group clipping fractions and joint KL to select ranges yielding comparable early joint KL. ## Q2. Necessity of input convergence condition in Proposition 3.1 **We provide a counterexample showing that output convergence does not guarantee primal–dual optimality without input convergence, even when all other assumptions of Proposition 3.1 hold.** Consider $\min_{x∈ℝ_+^2}x_1+2x_2$ subject to $x_1+x_2=1$, whose unique primal–dual optimum is \$(x_1^* , x_2^* , y^*)=(1,0,1) \$. Here $X=ℝ_+^2$, $Y=ℝ$, $A=(1,1)$, $b=1$, and $c=(1,2)^\top$. For $ω_t=1$, the PDHG update is $$x_{t+1}=[\hat x_{t+1}-η_t(c-A^\top\hat y_{t+1})]_+,$$ $$y_{t+1}=\hat y_{t+1}+η_t[1-A(2x_{t+1}-\hat x_{t+1})],$$ where $[\cdot]_+$ takes the nonnegative part componentwise. Set $e_t=0$ (no restart), $α_t^x=α_t^y=1$, $\boldsymbol{β}_t=0$, and $ζ_t=0$. The acceleration update reduces to $$\hat z_{t+1}=2z_t-\hat z_t.$$ Choose $η_t=1$ for odd $t$ and $1/2$ for even $t$. Initialize $\hat z_1=(1,2,-2)^\top$ with $η_0=1/2$. The first two PDHG outputs and the intervening accelerated input are $$z_1=([-\frac12]_+, 0, -2+\frac12\cdot4)^\top=0,$$ $$\hat z_2=2z_1-\hat z_1=(-1,-2,2)^\top, z_2=(0, [-2]_+, 2-2)^\top=0.$$ The next acceleration step gives $\hat z_3=\hat z_1$. This pattern repeats, so for every $t≥1$, $$z_t=0, \hat z_t=(-1)^{t+1}(1,2,-2)^\top.$$ The outputs violate $x_1+x_2=1$, while the inputs oscillate. All other assumptions of Proposition 3.1 are satisfied. The step sizes lie in $[1/2,1]$, $ω_t=1$, $1+α_t^x=1+α_t^y=2$, the history coefficients are bounded, and the anchor correction is zero. The example uses the proposition's general coefficient class and unrestricted initialization. We added this counterexample to Remark 3.1. ## Q3. Figures 1 and 2 **Figure 1 uses real solver trajectories plotted with Python/Matplotlib, and Figure 2 is redrawn as a manually editable schematic. AI was used only for visual design, and we produced the experimental data and methodological content.** The trajectories in Figure 1 were obtained by running the solvers on the toy LP $\min_{x∈ℝ^2} - x_1 - 2x_2$ s.t. $x_1≤4, x_2≤1.5, x_1-x_2≤3.5, x≥0$. To make clear that this conceptual figure is based on the real experimental data, we added axis ticks and numerical axis labels and revised the caption to specify the LP's objective and constraints. The caption also states that the policy was trained on the same LP instance. For Figure 2, we developed the overall schematic structure. AI was used only to assist with visual design. During the rebuttal, we have manually redrawn Figure 2 using editable drawing tool for accurate technical communication.

Dear Reviewer HqSj,

Thank you again for your review. As the discussion period is closing, we would like to briefly summarize how the revision addresses each of your three concerns.

1. Groupwise PPO and the joint update. Section 3.3 now relates the groupwise objective to the standard PPO objective (Eqs. 9-10). Appendix F.3 adds the joint-KL decomposition and a sufficient condition for bounding it (Eqs. 115-117), noting that, as in PPO-Clip, clipping does not itself enforce this bound. Section 4.5 adds an empirical comparison with standard and hybrid PPO.

2. Input convergence in Proposition 3.1. Remark 3.1 now gives a counterexample showing that output convergence alone does not imply optimality, which is why the assumption is needed.

3. Figures 1 and 2. Figure 1 plots recorded solver trajectories with Matplotlib on the LP stated in its caption, and Figure 2 has been manually redrawn.

We would be grateful to hear whether these changes resolve your concerns, or whether anything remains that we can clarify. If they do, we would appreciate your taking them into account in your final assessment.

Thank you for your time.

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

This paper proposes GALLOP, a reinforcement learning framework for accelerating PDHG methods for large-scale LP. The authors introduce a generalized accelerated PDHG update and a dimension-agnostic RL policy to learn algorithmic parameters and restart decisions. Experimental results demonstrate substantial improvements in iteration counts and wall-clock time over existing PDHG baselines. The learned policies also exhibit within-family size generalization.

Critical strengths
  1. A flexible and unified framework for learnable PDHG acceleration.
  2. An interesting and practically relevant topic: accelerating GPU-based first-order LP solvers.
  3. Extensive empirical evaluations across six LP families, demonstrating size generalization and the contributions of different control groups.
Critical weaknesses
  1. The contribution of the proposed groupwise PPO algorithm is unclear. Comparisons with standard PPO and existing hybrid actor-critic methods are missing.
  2. The contribution of the RL-based restart mechanism is not fully justified, as the auxiliary heuristic supervision is not separately evaluated.
  3. The theoretical result only establishes optimality assuming convergence, while convergence guarantees under learned policies remain unclear.
  4. High-accuracy evaluations (e.g., (10−810^{-8})) are missing, particularly against competitive solvers such as HPR-LP [1]. Direct comparisons with recent acceleration methods, such as cuPDLPx and AA-PDHG [2], are also missing.

[1] Chen, Kaihuang, et al. "HPR-LP: An implementation of an HPR method for solving linear programming: K. Chen et al." Mathematical Programming Computation 18.1 (2026): 183-210.

[2] Zhou, Yingxin, Stefano Cipolla, and Phan Tu Vuong. "Anderson Accelerated Primal-Dual Hybrid Gradient for solving LP." arXiv preprint arXiv:2508.08062 (2025).

Questions for authors
  1. How much improvement does the proposed groupwise PPO achieve over standard PPO?
  2. How does performance change when the auxiliary heuristic supervision for restart is removed during training?
  3. How does proposed method perform under tighter stopping criteria (e.g., (10−810^{-8})), particularly compared with HPR-LP?
  4. How does proposed method compare with recent acceleration methods such as cuPDLPx and FAA-PDHG?
7 comments

We thank the reviewer for the constructive comments.

Q1. Comparison with standard PPO and hybrid PPO

On Auction, standard (joint-ratio) PPO clips the product of all active groups' likelihood ratios. Hybrid PPO separately clips restart and joint continuous ratios. Groupwise PPO clips restart, history, relaxation/anchor, step size, and primal weight separately. We train each objective with four seeds, using the same experimental settings except for the grouping and clipping ranges. As group clipping allows different joint changes, ranges are selected to obtain similar empirical joint KL over first 100 iterations.

Table 9StandardHybridGroupwise
Final-checkpoint failures2/42/40/4
Iterations194.2±0.4199.5±11.3189.2±2.4

Standard and hybrid PPO each fail in two of four runs following sharp increases in empirical joint KL (Figure 5), whereas all four groupwise PPO runs solve the full validation set.

These results support improved training stability and lower solver iteration counts with groupwise PPO under the evaluated settings. See Section 4.5 and Appendix H.1 for details.

Q2. RL-learned Restart policy and effect of auxiliary restart supervision

RL learns a restart policy that improves on heuristic restart control and can learn to restart without auxiliary heuristic supervision. Replacing only RL-learned restart with the heuristic raises Transport median iterations from 165 to 181 (Table 6). Auction learns effective restart with no auxiliary supervision. (Table 18).

Auxiliary supervision primarily stabilizes training, and its performance benefit depends on the problem family. On Min-cost flow, 4/12 runs collapse to near-1 restart rate within 300 PPO iterations without supervision, whereas no collapsed runs with the supervision (Table 21). We also compare median solver iterations from successful runs trained for Min-cost flow and Transport at tolerance 10⁻⁶. The supervision increases solver iteration counts on Transport but reduces them on Min-cost flow in these runs.

Family(m,n)λprior=0.02λ_{prior}=0.02λprior=0λ_{prior}=0
MCF(4800,28800)152.5165
MCF(24000,144000)202215
MCF(57600,345600)207255
T(320,25600)148142
T(1012,256000)150.5137.5
T(3200,2560000)239.5186

Q3. Convergence guarantee under learned policies

We state that Proposition 3.1 does not claim convergence guarantee for the general choice of acceleration coefficient. See Sec 6.

Stopping criteria (Q4–5)

We retain HPR-LP and cuPDLPx their own stopping conditions even when their returned solutions do not satisfy GALLOP's criterion (Table 15). Consequently, their reported wall-clock times may benefit from this evaluation protocol as they can terminate at lower accuracy under GALLOP's relative metric. We therefore report the runtime results under each solver's own stopping criterion rather than presenting them as matched-accuracy comparisons. See Appendix E.1.

Q4. High accuracy evaluations

At 10⁻⁸ on Transport, both GALLOP implementations solve all 20 reported LPs. GALLOP uses fewer iterations than HPR-LP at every size, but HPR-LP has lower algorithm wall-clock time at 4/5 reported sizes.

Entries: iterations/algorithm wall-clock ms.

(m,n)GALLOP JAXGALLOP CUDAHPR-LPcuPDLPx
(160,6400)458/133404/211500/461700/39
(320,25600)925/193850/511350/451800/44
(506,64000)710/190866/721450/492100/54
(720,128000)484/141638/761600/592100/64
(1012,256000)714/242538/971600/642200/99

Iteration savings in GALLOP do not transfer to wall-clock time savings, due to per-iteration convergence check and policy evaluation. e.g. HPR-LP checks termination every 150 iterations. See Appendix H.3.

High-accuracy training incurs substantially higher computational costs, limiting our exploration to one seed without hyperparameter tuning during rebuttal. We state this as limitation.

Q5. Comparison with baseline Solvers

CUDA GALLOP has lower reported median runtime than cuPDLPx at 42 of 49 evaluated sizes and HPR-LP at 39 of 49 sizes. Our adapted AA-PDHG baseline fails to solve 26 of the 196 test LPs to tolerance 10⁻⁶, whereas GALLOP solves all 196. See Appendix E.1

This table shows selected rows from Tables 16–17.

Family(m,n)GALLOP CUDAHPR-LPcuPDLPxAA-PDHG (adapted)
Random LP(150000,300000)364109012801110
Transport(1920,921600)6881201562
Auction(89600,358400)91174364691
Min-cost flow(12000,72000)162537317
Robust inventory(760,2201)63109824000
L∞ regression(1680,9)174854433

AA-PDHG (Zhou et al.)'s repository was inaccessible, and we could not fully reproduce the solver's implementation details from the paper alone within the rebuttal period. AA-PDHG (adapted) is our Anderson acceleration within GA-PDHG and is not a reproduction of original AA-PDHG.

I thank the authors for their detailed response and additional experiments. The comparison with standard and hybrid PPO adequately addresses my first concern.

However, i remain concerned about the high-accuracy performance. In particular, it remains unclear whether the proposed method offers a competitive advantage over state-of-the-art solvers under comparable termination criteria and matched solution accuracy at tighter tolerances, especially in terms of wall-clock solving time.

Furthermore, the authors report additional training for the high-accuracy setting, which raises another important question regarding generalization across accuracy levels. In practice, retraining the policy for each desired accuracy level would significantly limit the method's applicability. It remains unclear whether a policy trained at a relatively loose tolerance can generalize to tighter tolerances without retraining. The current experiments do not adequately address this issue.

While I appreciate the additional results, these concerns remain unresolved. Therefore, I will maintain my current score.

We thank reviewer 1v3U for the follow up. We run additional experiments to address reviewer 1v3U's residual concern.

We deploy the policy trained at tolerance 10−610^{-6} to the tighter tolerance 10−710^{-7} without retraining, and CUDA GALLOP has lower median algorithm wall-clock time than HPR-LP and cuPDLPx at the same required solution accuracy across all five reported sizes in the Transport family.

Experiment setting with matched solution accuracy

We evaluate the unchanged policy on 80 unseen Transport LPs, 16 at each of five sizes, with no additional training

All returned solutions satisfy the same criterion as the GALLOP, Mrel(z)≤log⁡10−7M^{\mathrm{rel}}\left(z\right)\leq\log 10^{-7}. For each LP, we progressively tighten HPR-LP's and cuPDLPx's nominal tolerances and retain the loosest tested setting that meets this criterion, keeping each solver's internal stopping test. HPR-LP requires 5×10−85\times10^{-8} or 2×10−82\times10^{-8} on 29/80 LPs; cuPDLPx requires 5×10−85\times10^{-8} on 8/80. The remaining LPs meet the criterion at nominal tolerance 10−710^{-7}.

Results

Tables report medians over 16 LPs per size.

Table 1. Solver iterations at the common 10−710^{-7} threshold.

(m,n)(m,n)GALLOP JAXGALLOP CUDAHPR-LPcuPDLPx
(120, 3,200)2642781,4001,800
(160, 6,400)4223561,5002,000
(240, 12,800)2743641,3001,600
(320, 25,600)6564901,3001,600
(352, 30,976)4995871,3001,700

Table 2. Algorithm wall-clock time (ms) at the common 10−710^{-7} threshold.

(m,n)(m,n)GALLOP JAXGALLOP CUDAHPR-LPcuPDLPx
(120, 3,200)65.014.042.839.7
(160, 6,400)121.918.142.944.2
(240, 12,800)64.919.543.337.5
(320, 25,600)139.629.543.339.2
(352, 30,976)106.737.042.740.4

Both GALLOP implementations use fewer median iterations than HPR-LP and cuPDLPx at all five reported sizes.

Conclusion

This experiment demonstrates tolerance generalization without retraining. On Transport, CUDA GALLOP retains a median runtime advantage at the common required accuracy of 10−710^{-7} using the policy trained at 10−610^{-6}. Please refer to Appendix H.3 for more details.

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

This paper proposes GALLOP, a reinforcement learning framework for accelerating primal-dual hybrid gradient (PDHG) methods for large-scale linear programming.

Critical strengths
  1. The paper addresses an important challenge in large-scale optimization: coordinating step sizes, acceleration, and restarts to improve practical convergence.
  2. The method consistently reduces iteration counts compared with the evaluated baselines across six LP families. The results on Transport LPs with 10.24 million variables are particularly interesting, as the same policy is applied to problems substantially larger than those encountered during training.
Critical weaknesses
  1. In table 12, Algorithm wall-clock is 16x, but iterations and Matrix-vector products is around 2.5x.
  2. could the author compare the Standard PPO、Joint-ratio PPO and Hybrid PPO
  3. I am not sure about the novelty of theory. Could you compare with “PDHG-Unrolled Learning-to-Optimize Method for Large-Scale Linear Programming”
Questions for authors

see weakness

2 comments

We thank the reviewer for the constructive feedback.

Q1. Wall-clock speedup

The 16× wall-clock speedup over MPAX reflects fewer iterations as well as differences in sparse matrix–vector product implementation and stopping criteria. GALLOP also achieves up to a 7.0× wall-clock speedup over GA-PDHG(HT) under a shared implementation and common stopping criteria.

MPAX uses JAX BCSR for sparse matrix–vector products with the default configuration of JAX 0.10.2, while GALLOP uses CSR through cuSPARSE. The time required for each product can therefore differ between the two implementations, so fewer products do not translate proportionally into lower runtime. The stopping criteria also differ. The reported iteration counts measure the optimization steps needed to reach a common tolerance, whereas the wall-clock time covers execution until each solver's own stopping test terminates the run.

The largest wall-clock speedup over GA-PDHG(HT) occurs on Robust inventory at 3× the largest training size. GALLOP reduces the wall-clock time from 5,978 ms to 858 ms, a factor of 7.0, and the median iteration count from 25,798 to 2,874, a factor of 9.0 (Table 4). This comparison demonstrates substantial acceleration with the same sparse matrix–vector product implementation and stopping criteria. Appendix E provides the full results and comparison protocol.

Q2. Comparison with standard PPO and hybrid PPo

Our comparison experiment on Auction demonstrates that groupwise PPO trains more reliably than standard and hybrid PPO and requires fewer solver iterations among successfully trained runs.

We compare three PPO objectives that differ in which likelihood ratios are clipped together.

  • Standard PPO (joint-ratio PPO) clips a single joint likelihood ratio, the product of all active action groups' ratios. These names denote the same baseline here.
  • Hybrid PPO clips the discrete restart ratio and the joint continuous ratio separately.
  • Groupwise PPO (ours) clips each of five solver-control groups separately: restart, history, relaxation/anchor, step size, and primal weight.

We train each objective for 800 PPO iterations with four seeds, using the same experimental settings except for the grouping and clipping ranges. Since group-level clipping can permit different joint policy changes, we choose the clipping ranges separately for each objective to obtain similar empirical joint KL over iterations 1–100.

Table 9:

MetricStandard PPOHybrid PPOGroupwise PPO
Final-checkpoint failures (4 seeds)2/42/40/4
Iterations at 1× largest training size194.8±1.1199.8±4.6190.0±3.5
Iterations at 14× largest training size194.2±0.4199.5±11.3189.2±2.4

Standard and hybrid PPO each fail in two of four runs following sharp increases in empirical joint KL (Figure 5). The final checkpoints of these failed runs solve none of the held-out validation LPs, whereas all four final groupwise checkpoints solve the full validation set. Among successful runs, groupwise PPO requires fewer solver iterations at both sizes in Table 9.

These results support improved training stability and lower solver iteration counts with groupwise PPO under the evaluated settings. Please refer to Section 4.5 and Appendix H.1 for details.

Q3. Novelty of theory and comparison with PDHG-Net

PDHG-Net learns layer-specific step sizes and channel-mixing matrices in a PDHG-unrolled network. Its learned updates operate on latent embeddings, and the network output initializes PDLP, which performs the remaining iterations. GALLOP instead learns a feedback policy that directly controls algorithm parameters in the original primal–dual space at each iteration. As discussed in Section 1 (Introduction), our policy runs until the prescribed stopping criterion is met, without handing subsequent iterations to an external solver. We have made the distinction between latent embeddings and direct algorithm control explicit in Section 5 (Related Work).

PDHG-Net unrolls the basic PDHG iteration, whereas GALLOP incorporates generalized acceleration and learns its coefficients. This difference is discussed in Section 1. Section 3.1 defines the generalized acceleration update, which combines separate primal and dual extrapolation, history corrections, and a restart-anchor correction.

The theoretical results address different properties of these methods. PDHG-Net's Theorems 2.2–2.3 establish the existence of network parameters that reproduce standard PDHG and derive an approximation guarantee from this construction. Our Proposition 3.1 in Section 3.1 establishes primal–dual optimality of the GA-PDHG output limit if both the input and output sequences converge and the stated coefficient and vanishing-anchor conditions hold.

Section 4.4 reports experiments on PDHG-Net's public item-placement benchmarks. On IP-S, Table 7 reports an average of 186.7 iterations for GALLOP, compared with 422 for PDHG-Net + PDLP.

Thanks for the reply, I will keep my score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.