- 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
-
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.
-
The experiments provide substantive evidence of solver acceleration. The main comparisons use a common relative KKT tolerance of 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.
-
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.
-
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
-
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.
-
The theoretical conclusion of Proposition 3.1 relies on strong convergence assumptions. The proposition assumes that both the output iterates and the accelerated inputs 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.
-
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
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.
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 and separately clips each group likelihood ratio to reflect GA-PDHG's distinct control roles.
Specifically, expanding ρ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.