betaFeedback

WorksComputer Science

AHEAD: Adaptive Neural Acceleration for Large-Scale Linear Programming

Abstract

Large-scale linear programs with millions of variables and constraints strain time and memory budgets. First-order methods such as the primal-dual hybrid gradient scale to this regime because they avoid matrix factorizations, but they require many iterations. Learned accelerators can reduce these iterations, yet fewer iterations do not guarantee a shorter solve. Learning inference also takes time, and running the accelerator longer trades solver time for inference time. Existing unrolled accelerators handle this trade-off poorly: each layer processes every variable and constraint, the predicted iterates still need solver refinement, and every instance runs the same layers. We therefore ask: What neural accelerator design achieves end-to-end speedups on large-scale linear programs across sizes and target accuracies? We introduce AHEAD, an accelerator that predicts step sizes for first-order linear programming solvers while keeping their update rules. Its weight-shared predictor reads compact solver statistics and rescales the primal and dual step sizes, so each warm-start iteration stays inexpensive and a short warm-start phase hands the solver a warm start. A learned handoff policy sets the number of warm-start iterations for each instance and target accuracy, after which the solver finishes under its own termination criterion. On packing linear programs with up to 10710^7 variables, AHEAD achieves 6.56.5–11.6×11.6\times end-to-end speedups over Gurobi's first-order solver from a cold start, including on instances of unseen sizes and distributions. The gains extend to PageRank linear programs and hold across difficulty levels and target accuracies.

Introduction

Linear programming (LP) underpins large-scale decision-making, but instances with millions of variables and constraints strain time and memory budgets [9, 31]. First-order methods (FOMs) are attractive at this scale because they rely on sparse matrix-vector multiplications rather than costly factorizations [25, 3, 29]. However, they often need many iterations, particularly at high accuracy [3]. Their progress depends strongly on primal and dual step sizes: conservative choices slow convergence, while aggressive ones can destabilize it [13, 30].

Learning-to-optimize (L2O) offers a promising way to reduce the computational cost of iterative optimization. Early learned optimizers replace hand-designed update rules with learned dynamics [23, 1, 37]. More recent solver-integrated methods predict one-shot warm starts [34, 11], unroll first-order or interior-point trajectories [22, 33, 15, 17], or learn feedback policies that tune algorithmic parameters online [32]. Across these approaches, learning exploits recurring structure among related instances to reduce the cost subsequently performed by an optimization solver.

Fewer solver iterations, however, do not guarantee a shorter solve. In learned acceleration of LP solvers, a solve typically has two stages: a neural accelerator first produces a warm start, and the classical solver then continues from it until the solution reaches the target accuracy. We call the two stages together, the neural warm start followed by the classical solve, end-to-end neural acceleration. Existing unrolled accelerators typically rely on a fixed number of computational layers. Each learned layer processes every variable and constraint and predicts new primal–dual iterates in place of the solver’s native update, causing inference cost to grow with both instance size and rollout depth [33, 22]. These approximate outputs may still require additional solver running time to recover feasibility or attain high accuracy [34, 12]. Moreover, fixed-depth models use the same compute budget for every instance. This prevents them from adapting computational efforts to instance-specific needs and limits generalization across problem distributions and difficulty levels [7, 36]. Consequently, neural inference and subsequent refinement can offset or even outweigh the time saved by reducing solver iterations. These limitations lead to our central question: What neural accelerator design achieves end-to-end speedups on large-scale LPs across sizes and target accuracies?

To address this question, we introduce AHEAD (Adaptive Horizon for End-to-end Acceleration of Primal–Dual Solvers), a lightweight neural accelerator for first-order LP solvers. In the first stage, which we call the warm-start phase, AHEAD applies a weight-shared step-size predictor at every iteration and accelerates the solver only by adjusting its step sizes. To keep each warm-start iteration cheap, the predictor reads only ten statistics built from the solver’s own intermediate results and outputs one multiplier for each of the primal and dual step sizes. AHEAD’s solution quickly approaches the target accuracy on its own. Because only the step sizes change, AHEAD is also fully aligned with the solver: when high accuracy is required, its solution can be handed directly to the solver as a warm start. A learned handoff policy picks this moment by predicting whether stopping now or continuing gives a shorter end-to-end time. Together, these designs address three core challenges: they let the solver reach the target accuracy in fewer iterations, keep the time spent on each iteration low, and adapt the number of warm-start iterations to each instance and accuracy.

Our main contributions are summarized as follows:

  • End-to-end speedups from fast convergence. AHEAD’s solution quickly approaches the target accuracy within a short warm-start phase, leaving little remaining solver time, which yields many-fold end-to-end speedups across unseen scales, LP families, and accuracy levels.

  • Low time per iteration. We keep the inference time of each warm-start iteration small at any problem size: the predictor reads a 10-dimensional solver-native state and outputs two step-size multipliers, which suffice to steer PDHG through its oscillatory early phase.

  • Adaptive number of warm-start iterations. We apply a weight-shared predictor at each iteration recurrently, so the warm-start phase can run for any number of iterations, and a learned handoff policy selects this number for each instance and accuracy, further reducing the end-to-end time.

Related Work

First-order methods for large-scale linear programming. Chambolle & Pock [6] introduced PDHG, whose matrix–vector updates suit large-scale saddle-point problems. Applegate et al. [2] developed PDLP, preconditioning, adaptive step sizes, and primal–dual balancing; subsequent work used adaptive restarting to improve high-accuracy convergence [3]. These solvers adapt through hand-designed rules, but do not learn from related LP solves.

Learning components of LP solvers. Li et al. [24] learn variable reorderings, while Kuang et al. [21] learn presolve routines, including when to stop presolving. Iwata & Sakaue [20] generate instance-specific projections to reduce LP dimension. Other works learns simplex bases or pivot decisions (Fan et al., 2023; Liu et al., 2024; Lu & Yan, 2025). These methods can accelerate stages such as presolve or simplex search, but their neural inference overhead may outweigh the solver time saved.

Learned optimizers and warm starts. Learned update rules can transfer across optimization tasks [1, 37], although generalization outside the training distribution remains challenging [26]. Sambharya et al. [34] learn warm starts for quadratic optimization. For LPs, Li et al. (2024) use a fixed-depth PDHG-Net to predict primal–dual states, then refine them with PDLP; they also demonstrate transfer to larger instances of related problem families. Oshin et al. [32] learn dimension-agnostic parameter feedback for QP and SQP solvers.

Adaptive computation. Graves [14]; Banino et al. [5]; Hou et al. [18] study input-dependent neural computation, while Chen et al. [8] learn when to stop the neural network. For LPs, however, stopping decisions should exploit LP-specific feasibility and gap signals and account for the remaining solver work after learned computation ends. Taken together, prior work leaves open how to combine inexpensive control of LP iterations with instance-dependent computation to obtain consistent end-to-end gains across problem sizes and families.

AHEAD: Lightweight Warm Starts with Adaptive Depth

For an LP instance ii, consider a learned accelerator parameterized by θ\theta that controls the solver during a warm-start phase of KK iterations, and then hands the solver a primal–dual warm start zi,K=(x^iK,y^iK)\mathbf{z}_{i,K} = (\hat{\mathbf{x}}_{i}^{K}, \hat{\mathbf{y}}_{i}^{K}); we call this step the handoff. The solver continues from zi,K\mathbf{z}_{i,K} until it reaches the target accuracy ϵ\epsilon. We define the end-to-end time of instance ii is

Ti(θ,K;ϵ)=Twarm(K)+Tsolver(zi,K;ϵ),(1)\mathcal{T}_{i}(\theta, K; \epsilon) = T_{\mathrm{warm}}(K) + T_{\mathrm{solver}}(\mathbf{z}_{i,K}; \epsilon), \tag*{(1)}

where the warm-start time Twarm(K)T_{\mathrm{warm}}(K) covers the KK warm-start iterations, including the inference of the predictor and the handoff policy, and the remaining solver time Tsolver(zi,K;ϵ)T_{\mathrm{solver}}(\mathbf{z}_{i,K}; \epsilon) covers the solver’s run from the warm start until it reaches ϵ\epsilon. The cold-start time Ti,cold=Ti(0,0;ϵ)T_{i,\mathrm{cold}} = \mathcal{T}_{i}(0, 0; \epsilon) covers the same run from the solver’s default initial point.

AHEAD yields an end-to-end speedup on instance ii if Ti(θ,Ki;ϵ<Ti,cold\mathcal{T}_{i}(\theta, K_{i}; \epsilon< T_{i,\mathrm{cold}}, where KiK_{i} is the number of warm-start iterations selected for instance ii. Our goal is to achieve this on all or most instances, so we design AHEAD to keep both terms of (1) small. Section 3.1 derives what each term requires of the accelerator. Based on this analysis, AHEAD consists of two learned components: a weight-shared step-size predictor fθf_{\theta} (Section 3.2) that adjusts the primal and dual step sizes during the warm-start phase, and a learned handoff policy gφg_{\varphi} (Section 3.3) that selects the number of warm-start iterations KiK_{i} for each instance and accuracy. Section 3.4 describes how we train the predictor over varying numbers of warm-start iterations, and Figure 1 summarizes the framework.

Figure 1. Framework of AHEAD.

Design Requirements

Reducing Ti\mathcal{T}_{i} requires keeping both terms of (1) small. To make warm-starting worthwhile, its runtime must stay small: the accelerator runs each warm-start iteration, so its input must be cheap to compute and fixed-dimensional regardless of problem size. We consider LPs in bounded form

min⁡xcTxs.t.Gx≥h,Ax=b,ℓ≤x≤u,(2)\begin{aligned} \min_{x}\quad& c^{\mathsf{T}}x \quad\text{s.t.}\quad Gx \ge h,\quad Ax = b,\quad\ell\le x \le u, \tag*{(2)} \end{aligned}

where the bounds ℓ\ell and uu may contain infinite entries. PDHG ([6]) is a classical first-order method for Equation (2). Let K=[G;A]∈Rm×nK = [G; A] \in\mathbb{R}^{m \times n}, q=[h;b]q = [h; b], and Y=R+m1×Rm2\mathcal{Y} = \mathbb{R}_{+}^{m_1} \times\mathbb{R}^{m_2} for the m1m_1 inequality and m2m_2 equality rows, with m=m1+m2m = m_1 + m_2. PDHG alternates

xk+1=proj⁡[ℓ,u](xk−τk(c−KTyk)),yk+1=proj⁡Y(yk+σk(q−K(2xk+1−xk))),(3)x_{k+1} = \operatorname{proj}_{[\ell,u]}\left(x_k - \tau_k(c - K^{\mathsf{T}}y_k)\right), \qquad y_{k+1} = \operatorname{proj}_{\mathcal{Y}}\left(y_k + \sigma_k(q - K(2x_{k+1} - x_k))\right), \tag*{(3)}

where proj⁡C(v):=arg⁡min⁡w∈C12∥w−v∥2\operatorname{proj}_{\mathcal{C}}(v) := \arg\min_{w \in\mathcal{C}} \frac{1}{2}\lVert w-v\rVert^2. PDHG-based solvers such as PDLP first go through an oscillatory exploration phase and only then converge toward a solution (Applegate et al. [3]). This observation motivates a lightweight step-size predictor that adjusts τk\tau_k and σk\sigma_k at every iteration to shorten this early phase. After KK warm-start iterations, the accelerator hands the warm start to the solver, which continues until it reaches ϵ\epsilon. The best number of warm-start iterations Ki⋆=arg⁡min⁡KTi(θ,K;ϵ)K_i^{\star} = \arg\min_K T_i(\theta, K; \epsilon) balances the two terms and depends on both the instance and ϵ\epsilon. However, Ki⋆K_i^{\star} is known only in hindsight, since evaluating it requires running solver to termination from the warm start at every candidate KK. A practical accelerator therefore needs an online rule that selects KiK_i.

Formally, AHEAD keeps Equation (3) and only rescales its step sizes:

(τ~k,σ~k)={(ukpτk,ukdσk),k<Ki,(τk,σk),k≥Ki,(4)(\widetilde{\tau}_k, \widetilde{\sigma}_k) = \begin{cases} (u_k^{\mathrm{p}}\tau_k, u_k^{\mathrm{d}}\sigma_k), & k < K_i,\\ (\tau_k, \sigma_k), & k \ge K_i, \end{cases} \tag*{(4)}

where τk,σk\tau_k, \sigma_k are the solver’s own step sizes and ukp,ukd>0u_k^{\mathrm{p}}, u_k^{\mathrm{d}} > 0 are learned step-size multipliers. AHEAD thus makes two online decisions: it predicts (ukp,ukd)(u_k^{\mathrm{p}}, u_k^{\mathrm{d}}) at every warm-start iteration and selects KiK_i for each instance and ϵ\epsilon. The predictor outputs only two scalars per iteration, and the iterate at every warm-start iteration remains a valid PDHG iterate.

Weight-Shared Step-Size Predictor

To predict (ukp,ukd)(u_k^{\mathrm{p}}, u_k^{\mathrm{d}}) at each warm-start iteration, we design a weight-shared step-size predictor (Figure 1, left). It maps the current solver state to the two multipliers and shares its weights across iterations. We first describe the state and then the predictor.

Solver state. At each warm-start iteration kk, the predictor reads a state sks_k that describes the current progress of PDHG. To choose the step sizes for the next iteration, the state must answer four questions: how much the current iterate violates the primal and dual constraints, whether a larger step would remain stable, how to split the step between primal and dual, and whether recent steps make progress or oscillate. PDLP (Applegate et al. [4]) already answers each question with its own mechanism: its termination residuals, its step-acceptance check, its primal weight, and its restart rule (Appendix § 6). We therefore build one group of features from each mechanism, reusing only the solver’s own intermediate results, so that sks_k is cheap to compute and has the same dimension for every LP, as required in § 3.1:

sk=[rkp,rkd⏟feasibility,Mk,Nk,Uk,Sk⏟local stability,ω‾k⏟primal–dual scaling,Ckx,Cky,ρk⏟local trajectory]∈R10.(5)s_k = \left[ \underbrace{r_k^{\mathrm{p}}, r_k^{\mathrm{d}}}_{\text{feasibility}}, \underbrace{\mathcal{M}_k,\mathcal{N}_k,\mathcal{U}_k,\mathcal{S}_k}_{\text{local stability}}, \underbrace{\overline{\omega}_k}_{\text{primal--dual scaling}}, \underbrace{C_k^x,C_k^y,\rho_k}_{\text{local trajectory}} \right] \in\mathbb{R}^{10}. \tag*{(5)}

Feasibility. A primal--dual pair (x,y)(x,y) of an LP is optimal if and only if xx is primal feasible, yy is dual feasible, and the duality gap is zero. The first group tracks the two feasibility conditions: the primal residual rkp=log⁡(1+∥Axk−b∥2/m)r_k^{\mathrm{p}} = \log\left(1 + \lVert Ax_k-b\rVert_2/\sqrt{m}\right) measures how much xkx_k violates the primal constraints, and the dual residual rkd=log⁡(1+∥c−ATyk∥2/n)r_k^{\mathrm{d}} = \log\left(1 + \lVert c-A^{\mathsf{T}}y_k\rVert_2/\sqrt{n}\right) measures how much yky_k violates the dual constraints. Large residuals indicate an early phase of the solve, where larger steps pay off, and small residuals call for finer steps.

Local stability. The second group tells the predictor whether a larger step would remain stable. With constant step size, PDHG converges when τσ∥K∥22<1\tau\sigma\lVert K\rVert_2^2 < 1 (Chambolle & Pock [6]). This bound is often too conservative in practice. PDLP (Applegate et al. [2]) instead adapts the step size with a local stability condition on the actual movement: it computes the update in Equation (3) with a trial step size, keeps the update if the condition holds, and otherwise shrinks the step size and recomputes the update (Appendix § 6). Let Δxk=xk−xk−1\Delta x_k = x_k - x_{k-1} and Δyk=yk−yk−1\Delta y_k = y_k - y_{k-1} denote the change between the last two iterations, and write τk=ηk/ωk\tau_k = \eta_k/\omega_k and σk=ηkωk\sigma_k = \eta_k\omega_k, where ηk>0\eta_k > 0 sets the overall step size and ωk>0\omega_k > 0 is the solver’s primal weight. With the weighted movement Mk=ωk2∥Δxk∥22+12ωk∥Δyk∥22\mathcal{M}_k = \frac{\omega_k}{2}\|\Delta x_k\|_2^2 + \frac{1}{2\omega_k}\|\Delta y_k\|_2^2 and the primal–dual interaction Nk=⟨AΔxk,Δyk⟩\mathcal{N}_k = \langle A\Delta x_k, \Delta y_k\rangle, PDLP’s condition can be written as

Mk/ηk−Nk≥0.(6)\mathcal{M}_k/\eta_k - \mathcal{N}_k \ge0. \tag*{(6)}

This condition always holds when Nk≤0\mathcal{N}_k \le0. When Nk>0\mathcal{N}_k > 0, it limits the step size to ηk≤Mk/Nk\eta_k \le\mathcal{M}_k/\mathcal{N}_k. We define the utilization as the ratio of the current step size to this upper limit, Uk=ηk/(Mk/Nk)=ηkNk/Mk\mathcal{U}_k = \eta_k/(\mathcal{M}_k/\mathcal{N}_k) = \eta_k\mathcal{N}_k/\mathcal{M}_k, so the condition holds exactly when Uk≤1\mathcal{U}_k \le1. We therefore include Mk\mathcal{M}_k, Nk\mathcal{N}_k, Uk\mathcal{U}_k, and the bounded ratio Sk=tanh⁡(Nk/Mk)\mathcal{S}_k = \tanh(\mathcal{N}_k/\mathcal{M}_k) in the state: Uk\mathcal{U}_k tells the predictor how close the current step size is to this limit, and the sign of Sk\mathcal{S}_k tells it whether the condition can be violated at all. The predictor thus observes the same condition that the classical solver imposes on each update, and can set the next multipliers.

Primal–dual scaling. The third group tells the predictor how to split the step between primal and dual. The solver sets this split through its primal weight: τk=ηk/ωk\tau_k = \eta_k/\omega_k and σk=ηkωk\sigma_k = \eta_k\omega_k. The best pair of multipliers thus depend on ωk\omega_k, so we include the detrended log-weight ωˉk=log⁡ωk−0.8log⁡(n/m)\bar{\omega}_k = \log\omega_k - 0.8\log(n/m), which treats reciprocal primal and dual scalings symmetrically.

Local trajectory. The last group tells the predictor whether recent steps make progress or oscillate. PDHG iterates often spiral around saddle points before settling, which slows early progress [6, 3]. PDLP counters this with restarts triggered by the normalized duality gap, which measures how far an iterate is from the saddle point but needs an extra optimization problem to compute, so PDLP evaluates it only periodically [2]. However, our predictor needs this information at every iteration, and computing the gap that often would be too expensive. We therefore measure the directional consistency of consecutive updates with cosine similarities, which are inexpensive to compute at every iteration:

Ckx=⟨Δxk,Δxk−1⟩∥Δxk∥2∥Δxk−1∥2+δ,Cky=⟨Δyk,Δyk−1⟩∥Δyk∥2∥Δyk−1∥2+δ,(7)C_k^x = \frac{\langle\Delta x_k,\Delta x_{k-1}\rangle}{\|\Delta x_k\|_2\|\Delta x_{k-1}\|_2+\delta}, \qquad C_k^y = \frac{\langle\Delta y_k,\Delta y_{k-1}\rangle}{\|\Delta y_k\|_2\|\Delta y_{k-1}\|_2+\delta}, \tag*{(7)}

where the small constant δ>0\delta> 0 prevents division by zero. Up to δ\delta, each cosine equals +1+1 when consecutive updates point in the same direction and −1-1 when they reverse, and it does not change when either update is rescaled, for example by a new step size. Values near +1+1 thus indicate steady progress and suggest that a larger step is safe, whereas values near −1-1 indicate oscillation and need to adapt the step smaller. We also include the movement ratio ρk=log⁡(∥Δzk∥2/∥Δzk−1∥2)\rho_k = \log(\|\Delta z_k\|_2/\|\Delta z_{k-1}\|_2) with Δzk=(Δxk,Δyk)\Delta z_k = (\Delta x_k, \Delta y_k), which shows whether the updates are growing (ρk>0\rho_k > 0) or shrinking (ρk<0\rho_k < 0). These features give the predictor the progress information that PDLP’s restart rule relies on. Thus, AHEAD itself never restarts during the warm-start phase.

Weight-shared step-size predictor. Given sks_k, the predictor outputs the logarithms of the two step-size multipliers,

\begin{bmatrix}\ell_k^p \\ \ell_k^d\end{bmatrix} = f_\theta(s_k), \qquad u_k^p = e^{\ell_k^p}, \qquad u_k^d = e^{\ell_k^d}, \tag*{(8)}\end{bmatrix}

where fθf_\theta is a small MLP with tanh activations. Predicting logarithms keeps both multipliers positive, and (4) applies them to the solver’s native step sizes.

The primal–dual update directions of the solver are faithfully kept in AHEAD, as we find them to be efficient and reliable directions towards optimality. The primal and dual step sizes are much harder to tune, since first-order methods like PDLP lack the higher-order information as interior-point methods to find the optimal step size for each update. Hand-designed rules either overestimate or underestimate the optimal step size. Learning the optimal step sizes only can thus reap the most benefit of learning without introducing more model complexity that lowers per-iteration efficiency.

Another core design principle is a looped architecture for recursive solution refinement: we apply the same predictor fθf_\theta at every warm-start iteration. This is a paradigm shift from existing neural solvers with a fixed model depth and independent model parameters per-layer: they require more parameters and cannot adapt to the varying number of iterations. AHEAD runs like a classical solver: it recursively refines primal–dual solutions, without a pre-determined number of iterations, until the handoff policy ends the warm-start phase. This adaptive recursion is key to generalizability across instances with different sizes and difficulties, as reported in other literature such as Chen et al., [8] and recurrent networks Schwarzschild et al., [35].

Learned Handoff Policy

With the weight-shared predictor, AHEAD can run for any number of warm-start iterations. For moderate accuracy requirements, such as ϵ=10−4\epsilon= 10^{-4}, the warm-start iterations alone already bring the solution close to the accuracy. Because AHEAD is fully aligned with the solver, it enables a second capability: when higher accuracy is required, AHEAD hands its solution directly to the solver as warm start. This warm start substantially reduces the number of iterations the solver needs to converge at high accuracy, while still achieving a large end-to-end speedup over a cold start.

A key question in this handoff is when to stop the warm-start phase and switch to the solver’s own iterations. Switching too late wastes warm-start iterations that no longer reduce the remaining solver time, whereas switching too early gives the solver a weaker warm start than AHEAD could provide. We address this with a learned handoff policy gφg_{\varphi} (Figure 1, right). It selects the number of warm start iterations KiK_i for any given target accuracy ϵ\epsilon. Since the best choice Ki⋆K_i^\star is known only in hindsight (§ 3.1), the policy makes this decision online. At every warm-start iteration kk, it reads a handoff state hk\mathbf{h}_k, predicts the end-to-end time of stopping now and of continuing, and ends the warm-start phase once stopping is predicted to be faster. Unlike halting in adaptive neural computation ([14, 5]), this decision depends on the remaining solver time after handoff, not on the quality of a network output.

Handoff state. Whether to handoff depends on how close the solver is to convergence and how fast it is approaching it. The solver monitors the primal residual, dual residual, and duality gap,

ekp=∥Axk−b∥21+∥b∥2,ekd=∥c−ATyk∥21+∥c∥2,ekg=∣cTxk−bTyk∣1+∣cTxk∣+∣bTyk∣,(9)e_k^{\mathrm{p}} = \frac{\lVert A\mathbf{x}_k-\mathbf{b}\rVert_2}{1+\lVert\mathbf{b}\rVert_2}, \qquad e_k^{\mathrm{d}} = \frac{\lVert\mathbf{c}-A^{\mathsf{T}}\mathbf{y}_k\rVert_2}{1+\lVert\mathbf{c}\rVert_2}, \qquad e_k^{\mathrm{g}} = \frac{\lvert\mathbf{c}^{\mathsf{T}}\mathbf{x}_k-\mathbf{b}^{\mathsf{T}}\mathbf{y}_k\rvert}{1+\lvert\mathbf{c}^{\mathsf{T}}\mathbf{x}_k\rvert+\lvert\mathbf{b}^{\mathsf{T}}\mathbf{y}_k\rvert}, \tag*{(9)}

and reaches target accuracy ϵ\epsilon when max⁡{ekp,ekd,ekg}≤ϵ\max\{e_k^{\mathrm{p}},e_k^{\mathrm{d}},e_k^{\mathrm{g}}\}\leq\epsilon ([2]). Convergence is decided by the slowest criterion, and the same residual may be close enough for a loose ϵ\epsilon but far from a tight one. We therefore measure, for each criterion, the log-gap to the target accuracy

Δkj(ϵ)=log⁡ekj+δϵ+δ,j∈{p,d,g},(10)\Delta_k^j(\epsilon)=\log\frac{e_k^j+\delta}{\epsilon+\delta}, \qquad j\in\{\mathrm{p},\mathrm{d},\mathrm{g}\}, \tag*{(10)}

where δ>0\delta>0 avoids log⁡0\log0. Because ϵ\epsilon is considered in the handoff state, the same learned handoff policy can adapt the number of warm-start iterations across target accuracies.

Handoff rule. At warm-start iteration kk, AHEAD can either hand off now or continue. An MLP gφg_{\varphi} maps the handoff state hk\mathbf{h}_k to

[Q^handoff(hk),Q^continue(hk)]=gφ(hk),(11)\left[\widehat{Q}_{\mathrm{handoff}}(\mathbf{h}_k),\widehat{Q}_{\mathrm{continue}}(\mathbf{h}_k)\right]=g_{\varphi}(\mathbf{h}_k), \tag*{(11)}

where Q^handoff\widehat{Q}_{\mathrm{handoff}} and Q^continue\widehat{Q}_{\mathrm{continue}} estimate the end-to-end time of handing off now and of handing off at the best later iteration, respectively. Both are divided by the cold-start time, so they are comparable across instances of different sizes and difficulty. AHEAD hands off at the first warm-start iteration kk with Q^handoff(hk)≤Q^continue(hk)\widehat{Q}_{\mathrm{handoff}}(\mathbf{h}_k)\leq\widehat{Q}_{\mathrm{continue}}(\mathbf{h}_k), or after Kmax⁡K_{\max} iterations if this condition never holds. estimate the same quantity, so the rule needs no extra threshold. After the handoff, the solver continues from the warm start with its own step-size rule and termination criterion, so every returned solution meets the target accuracy ϵ\epsilon, exactly as a cold-start solve does.

Multi-Horizon Training

To serve different accuracy requirements, we train the predictor over varying horizons KK rather than a fixed one. The handoff policy may end learned acceleration at any checkpoint, so the predictor must leave a useful iterate at every candidate horizon. Formally, let H\mathcal{H} be the set of candidate horizons and (xi⋆,yi⋆)(\mathbf{x}_i^\star,\mathbf{y}_i^\star) an optimal primal–dual solution of instance ii. We train the predictor by

min⁡θ Ei∼DEK∼U(H)[∥x^iK−xi⋆∥22∥xi⋆∥22+δ+∥y^iK−yi⋆∥22∥yi⋆∥22+δ],(12)\min_{\theta}\ \mathbb{E}_{i\sim\mathcal{D}}\mathbb{E}_{K\sim\mathcal{U}(\mathcal{H})}\left[\frac{\lVert\widehat{\mathbf{x}}_i^K-\mathbf{x}_i^\star\rVert_2^2}{\lVert\mathbf{x}_i^\star\rVert_2^2+\delta}+\frac{\lVert\widehat{\mathbf{y}}_i^K-\mathbf{y}_i^\star\rVert_2^2}{\lVert\mathbf{y}_i^\star\rVert_2^2+\delta}\right], \tag*{(12)}

where (x^iK,y^iK)(\widehat{\mathbf{x}}_i^K,\widehat{\mathbf{y}}_i^K) is the handoff iterate after KK learned iterations. The normalized distance to the optimum serves as a differentiable proxy for the remaining solver work TsolverT_{\mathrm{solver}}. This objective can be viewed as training over a distribution of horizons rather than a single fixed depth. By sampling KK, the predictor learns a state-dependent rule that remains useful for any horizon the handoff policy may pick, and the shared weights let it run for horizons outside H\mathcal{H}. We initialize the output layer of fθf_{\theta} at zero, so that (ukp,ukd)=(1,1)(u_k^p,u_k^d)=(1,1) and training starts from the solver’s native step-size rule.

Training the handoff policy. Unlike the distance used to train the predictor, the end-to-end time is measured in wall-clock and is not differentiable. We therefore freeze the trained predictor, roll it out on each training instance, and measure at every warm-start iteration kk the end-to-end time of handing off at kk, divided by the cold-start time, Ci(k)=Ti(θ,k;ϵ)/Ti,coldC_i(k)=T_i(\theta,k;\epsilon)/T_{i,\mathrm{cold}}, using actual solver runs from the warm start rather than a surrogate. The regression targets for the two predictions of the handoff policy are

Qi,handoff(k)=Ci(k),Qi,continue(k)=min⁡k<j≤Kmax⁡Ci(j),(13)Q_{i,\mathrm{handoff}}(k)=C_i(k), \qquad Q_{i,\mathrm{continue}}(k)=\min_{k<j\leq K_{\max}} C_i(j), \tag*{(13)}

the normalized end-to-end time of handing off now and the best one attainable by handing off later. We fit gϕg_{\phi} by

min⁡ϕ1∣Dhandoff∣∑i∈Dhandoff1∣Ji∣∑k∈Ji∑a∈{handoff,continue}(Q^a(hi,k)−Qi,a(k))2,(14)\min_{\phi}\frac{1}{|\mathcal{D}_{\mathrm{handoff}}|}\sum_{i\in\mathcal{D}_{\mathrm{handoff}}}\frac{1}{|\mathcal{J}_i|}\sum_{k\in\mathcal{J}_i}\sum_{a\in\{\mathrm{handoff},\mathrm{continue}\}}\left(\widehat{Q}_a(h_{i,k})-Q_{i,a}(k)\right)^2, \tag*{(14)}

where Dhandoff\mathcal{D}_{\mathrm{handoff}} is the set of training instances for the handoff policy and Ji\mathcal{J}_i is the set of warm-start iterations evaluated on instance ii. Because both outputs are regressed onto the same normalized end-to-end time, the handoff rule compares them directly, without a hand-tuned threshold.

Experiments

In this section, we first examine the proposed adaptive accelerator against common baselines, and further examine the generalization capabilities, adaptive stopping and difficulty. Finally, we conduct ablation analysis to analyze the underlying structure of AHEAD.

Experimental Settings

Datasets and metrics. We evaluate on two LP families: synthetic packing LPs with n∈[105,106]n\in[10^5,10^6] nonnegative variables, one equality constraint, and about 0.1n0.1n sparse inequalities, and PageRank LPs on Barabási–Albert graphs [2, 19]. Both follow the LP form in § 3.1. We report the end-to-end speedup, whose wall-clock time includes AHEAD’s inference, presolve, and solver execution, and the reduction in iterations, both at the same target accuracy (ϵ=10−4\epsilon=10^{-4} by default). Test instances are disjoint from the training instances. Appendices § 8.§ 1, § 8.§ 2, and § 8.§ 3 give the generation details and the measurement protocol.

Baselines and Evaluation. We compare against three groups of baselines. Cold-start solvers form the first group: Gurobi GPU PDHG (PDHGGPU=1) and OR-Tools PDLP. The second group is the learned baseline PDHG-Net [22], the closest learned method to ours. The third group contains two variants of AHEAD: a fixed horizon selected on validation, and a per-instance optimal Ki∗K_i^* that marks the best achievable handoff.

Training Details. The candidate horizons are H={8,16,32,64,128}\mathcal{H}=\{8,16,32,64,128\}. We train the predictor for 200 epochs with Adam, a learning rate of 10−310^{-3}, cosine annealing, and a batch size of 8. Each mini-batch shares one sampled horizon KK, which enables batched rollouts and still gives an unbiased estimate of (12). We clip gradients so that pathological primal or dual errors do not dominate an update. The handoff policy is then trained on the frozen predictor’s trajectories.

Acceleration

Table 1 compares AHEAD with PDHG-Net and with a fixed number of warm-start iterations selected on validation, all on the Gurobi GPU-PDHG backbone at ϵ=10−4\epsilon=10^{-4}.

The test sets contain 50 held-out packing LPs, 20 larger packing LPs with n∈[106,107]n \in[10^{6}, 10^{7}], and 20 packing LPs from an unseen distribution. (1) AHEAD generalizes across scale and distribution. Its predictor only rescales step sizes from a fixed-dimensional solver state and never predicts the solution, unlike PDHG-Net, whose predictions are tied to the training distribution. (2) Adaptive handoff nearly matches the best handoff. The best number of warm-start iterations varies across instances, so a fixed number wastes iterations or stops too early, whereas the handoff policy stops once further iterations no longer save time. (3) The advantage grows with problem size. Larger PageRank LPs require more iterations, and the weight-shared predictor adapts to each instance, whereas PDHG-Net has fixed depth (Figure 2).

Figure 2. Speedup on PageRank LPs.

MethodIID (n=50n=50)Size shift (n=20n=20)Unseen distribution (n=20n=20)
SpeedupTime (s)SpeedupTime (s)SpeedupTime (s)
Cold PDHG (Gurobi)1.00×18.21.00×5.31.00×3.2
Best validation KK (K=32K=32)5.63×3.25.09×1.13.25×0.99
PDHG-Net ([22])1.23×14.81.18×4.51.06×3.1
AHEAD11.07×1.611.59×0.466.48×0.50
Per-instance optimal K⋆K^{\star}12.36×1.512.75×0.427.06×0.46

Table 1. Acceleration with the Gurobi PDHG backbone on packing-type LPs.

Generalization

Fixed vs. adaptive handoff

Figure 3a. Fixed vs. adaptive handoff.

Robustness across target accuracies

Figure 3b. Robustness across target acc.

Speedup across difficulty tiers

Figure 3c. Speedup across difficulty tiers.

Does AHEAD rely on solver continuation? We disable handoff on a representative LP instance and compare AHEAD’s residual trajectory with adaptive AHEAD, cold-start PDHG, and PDHG-Net. Figure 4 supports two observations. (1) AHEAD can reach the target tolerance without native continuation. When AHEAD runs without handoff, it reduces the primal residual and reaches the target, whereas PDHG-Net remains above it. (2) Learned acceleration and solver refinement are complementary. Adaptive handoff reaches the target earlier than AHEAD without handoff or the cold-start solver, indicating that AHEAD accelerates early trajectory while the native solver completes the refinement. Handoff improves efficiency rather than providing progress that AHEAD cannot achieve on its own.

Figure 4. Primal-residual trajectories without early solver handoff.

Adaptive Stopping. To evaluate whether AHEAD can select an effective number of warm-start iterations, we compare adaptive handoff with a fixed K=32K=32 and the per-instance optimal K⋆K^{\star}, the K∈{1,…,128}K \in\{1,\ldots,128\} with the shortest end-to-end time on each instance; we also evaluate robustness across target accuracies. The figures support two observations. (1) Adaptive handoff comes close to the per-instance optimal K⋆K^\star. In Figure 3(a), the adaptive speedup distribution shifts markedly beyond the fixed-horizon baseline and toward the oracle, showing that the current solver state provides useful information for selecting an instance-specific handoff point. (2) Acceleration persists across target accuracies. Figure 3(b) shows consistently large runtime reductions across all evaluated tolerances. Because every run must satisfy the same PDLP termination criterion, these gains demonstrate consistent speedups for convergence without relaxing final solution accuracy.

Robustness across acceleration horizons, target accuracies, and problem difficulty levels

Figure 3. Robustness across acceleration horizons, target accuracies, and problem difficulty levels.

Difficulty. To test whether acceleration persists as instances become harder, we generate 60 packing-LP test instances unseen during training and divide them into three equal-sized groups, Easy, Medium, and Hard, based on their cold-start Gurobi PDHG runtimes. We then split them into three equal-sized groups: the shortest third as Easy, the middle third as Medium, and the longest third as Hard. Figure 3(c) reports AHEAD achieves approximately 9×9 \times, 11×11 \times, and 12×12 \times speedup on easy, medium, and hard instances, respectively. The corresponding fixed K=32K = 32 results are roughly 3×3 \times, 5×5 \times, and 8×8 \times. Adaptive handoff improves speedup in every tier, while OR-Tools PDLP and PDHG-Net remain below the cold Gurobi baseline in this comparison.

Ablation

Which solver-state features matter? Table 2 incrementally introduces the four groups of solver-state features. Adding the primal and dual residuals reduces the total number of steps from 104.4 to 92.5. Movement and nonlinearity provide the largest incremental improvement, further reducing the total to 80.4 steps. Incorporating the primal weight and cosine features subsequently reduces the total to 79.3 and 76.8, respectively. Overall, the complete representation achieves a 26.4% reduction relative to the fixed step-size baseline. These results indicate that feasibility, local stability, primal-dual scaling, and trajectory geometry provide complementary information for step-size prediction.

Input stateTotal steps ↓\downarrowΔ\Delta (%) ↑\uparrow
Fixed stepsize104.4–
+ Residuals92.511.4
+ Movement/nonlinearity80.413.1
+ Primal weight ωk\omega_k79.31.4
+ Cosine geometry (AHEAD)76.83.2

Table 2. Incremental ablation of solver-state features. Features are added cumulatively.

Does the improvement come from model capacity? Table 3 compares controller architectures while fixing the solver-state representation and training objective. Increasing the controller from five layers with width 64 to seven layers with width 128 increases the total number of steps from 68.5 to 72.9. The improvement therefore cannot be explained simply by increased network capacity. In contrast, sharing controller parameters across iterations produces the best result, requiring 67.8 total steps and 35.8 continuation steps. This supports matching the controller parameterization to the iteration-invariant update structure of the underlying optimizer.

ControllerTotal steps ↓\downarrowContinuation steps ↓\downarrow
5 layers, width 6468.536.5
7 layers, width 12872.940.9
Weight-shared (AHEAD)67.835.8

Table 3. Predictor-architecture ablation.

Conclusion

We asked what neural accelerator design achieves end-to-end speedups on large-scale LPs across sizes and target accuracies. AHEAD answers with three design choices. First, it learns only the step sizes and keeps the solver’s update directions, so each warm-start iteration stays inexpensive and every iterate remains a valid warm start. Second, its weight-shared predictor runs recurrently, so the warm-start phase can last any number of iterations. Third, a learned handoff policy selects this number for each instance and accuracy. Together, these choices let the solver reach the target accuracy in fewer iterations with little time per iteration, yielding many-fold end-to-end speedups on packing and PageRank LPs across unseen scales, difficulty levels, and target accuracies. Future work will extend AHEAD to real-world LPs and other first-order solvers.

Engineering Accelerations in PDLP

Classical PDHG uses fixed primal and dual step sizes chosen according to a global stability condition, making its convergence highly sensitive to conservative step-size selection and mismatched primal–dual scaling. Beyond presolving and diagonal preconditioning, PDLP accelerates conventional PDHG through three coupled mechanisms: adaptive step-size selection, adaptive restarting, and dynamic primal weighting.

First, PDHG parameterizes its primal and dual step sizes as

τk=ηkωk,σk=ηkωk\tau_k = \frac{\eta_k}{\omega_k}, \qquad\sigma_k = \eta_k\omega_k

where ηk\eta_k controls the overall step magnitude and ωk\omega_k controls the relative primal-dual scaling. Conventional PDHG selects ηk\eta_k according to the global condition ηk≤1/∥A∥2\eta_k \le1/\lVert A\rVert_2, which guarantees convergence but is often overly conservative. PDLP instead evaluates each candidate step using the local condition ηk≤ηˉk:=∥zk+1−zk∥ωk22(yk+1−yk)⊤A(xk+1−xk)\eta_k \le\bar{\eta}_k := \frac{\lVert z_{k+1}-z_k\rVert_{\omega_k}^2}{2(y_{k+1}-y_k)^\top A(x_{k+1}-x_k)}, where zk=(xk,yk)z_k=(x_k,y_k) and ∥z∥ω2=ω∥x∥22+1ω∥y∥22\lVert z\rVert_{\omega}^2 = \omega\lVert x\rVert_2^2 + \frac{1}{\omega}\lVert y\rVert_2^2. The next candidate step size is updated as ηk+1=min⁡{(1−(k+1)−0.3)ηˉk,(1+(k+1)−0.6)ηk}\eta_{k+1} = \min\left\{\left(1-(k+1)^{-0.3}\right)\bar{\eta}_k,\left(1+(k+1)^{-0.6}\right)\eta_k\right\}. A candidate violating the local condition is rejected and recomputed using a smaller step. Because ηˉk\bar{\eta}_k depends on the realized primal-dual movement rather than only on the global operator norm, PDLP can take substantially larger steps along locally stable portions of the trajectory.

The second mechanism controls trajectory history through adaptive restarting. Within outer iteration nn, PDLP maintains a step-size-weighted average of the inner iterates, zˉn,t+1=∑i=1t+1ηn,izn,i∑i=1t+1ηn,i\bar{z}^{n,t+1}=\frac{\sum_{i=1}^{t+1}\eta^{n,i}z^{n,i}}{\sum_{i=1}^{t+1}\eta^{n,i}}. Progress is evaluated using the normalized duality gap

ρrn(z)=1rmax⁡z^=(x^,y^)∈Z∥z^−z∥ωn≤r{L(x,y^)−L(x^,y)},\rho_r^n(z) = \frac{1}{r}\max_{\substack{\hat{z}=(\hat{x},\hat{y})\in Z\\ \lVert\hat{z}-z\rVert_{\omega_n}\le r}}\left\{\mathcal{L}(x,\hat{y})-\mathcal{L}(\hat{x},y)\right\},

and μn(z,zref)=ρ∥z−zref∥ωn(z)\mu_n(z,z_{\mathrm{ref}})=\rho\lVert z-z_{\mathrm{ref}}\rVert_{\omega_n(z)}.

At each restart check, PDLP selects between the current iterate and its weighted average:

zcn,t+1={zn,t+1,μn(zn,t+1,zn,0)<μn(zˉn,t+1,zn,0)zˉn,t+1,otherwisez_c^{n,t+1} = \begin{cases} z^{n,t+1}, & \mu_n\left(z^{n,t+1},z^{n,0}\right)<\mu_n\left(\bar{z}^{n,t+1},z^{n,0}\right)\\ \bar{z}^{n,t+1}, & \text{otherwise} \end{cases}

The outer loop is restarted when the normalized duality gap exhibits sufficient decay, when local progress stalls after necessary decay has been achieved, or when the inner loop becomes excessively long. This mechanism retains averaging when it is beneficial but discards accumulated trajectory history once it ceases to improve the normalized gap.

Finally, PDLP updates the primal weight only at restart points. Let Δxn=∥xn,0−xn−1,0∥2\Delta_x^n=\lVert x^{n,0}-x^{n-1,0}\rVert_2, Δyn=∥yn,0−yn−1,0∥2\Delta_y^n=\lVert y^{n,0}-y^{n-1,0}\rVert_2. The new primal weight is obtained through log-space smoothing: ωn=exp⁡(θlog⁡ΔynΔxn+(1−θ)log⁡ωn−1)\omega^n=\exp\left(\theta\log\frac{\Delta_y^n}{\Delta_x^n}+(1-\theta)\log\omega^{n-1}\right), where PDLP uses θ=0.5\theta=0.5. This update approximately balances the weighted primal and dual distances while avoiding abrupt changes that may destabilize PDHG. Consequently, the three mechanisms address distinct limitations of conventional PDHG: adaptive step sizes control the step magnitude using local stability, restarts manage accumulated trajectory history, and the primal weight balances progress between the primal and dual spaces.

Training

Algorithm 1 Random-Horizon Training

Require: Dataset D\mathcal{D} with targets (x∗,y∗)(x^{\ast}, y^{\ast}); K={8,16,32,64,128}\mathcal{K} = \{8, 16, 32, 64, 128\}; batch size BB

  1. Initialization

  2. repeat

  3. Sample a mini-batch B⊂D\mathcal{B} \subset\mathcal{D} and a shared K∼Uniform⁡(K)K \sim\operatorname{Uniform}(\mathcal{K})

  4. for all i∈Bi \in\mathcal{B} do

  5. (x^iK,y^iK)←Rollout⁡K(fθ,i)(\hat{x}_{i}^{K}, \hat{y}_{i}^{K}) \leftarrow\operatorname{Rollout}_{K}(f_{\theta}, i)

  6. di←∥x^iK−xi∗∥22∥xi∗∥22+δ+∥y^iK−yi∗∥22∥yi∗∥22+δd_i \leftarrow\frac{\lVert\hat{x}_{i}^{K} - x_i^{\ast} \rVert_{2}^{2}}{\lVert x_i^{\ast} \rVert_{2}^{2} + \delta} + \frac{\lVert\hat{y}_{i}^{K} - y_i^{\ast} \rVert_{2}^{2}}{\lVert y_i^{\ast} \rVert_{2}^{2} + \delta}

  7. end for

  8. L10−8←1B∑i∈Bdi\mathcal{L}_{10^{-8}} \leftarrow\frac{1}{B}\sum_{i \in\mathcal{B}} d_i

  9. Update θ\theta using ∇θL10−8\nabla_{\theta}\mathcal{L}_{10^{-8}}

  10. until convergence

Dataset

PageRank

Following Applegate et al. [2], we generate PageRank LPs with the formulation of Iouditski & Nesterov [19], using a damping factor λ=0.85\lambda= 0.85. The resulting LP has one equality row 1Tx=1\mathbf{1}^{\mathsf{T}}x = 1 and nn inequality rows, and matches the LP form in § 3.1 with S=1S = 1 and the transition constraints written as sparse linear inequalities.

For each instance, we first sample a Barabási–Albert preferential-attachment graph with attachment degree 3. Let S′∈Rn×nS^{\prime} \in\mathbb{R}^{n \times n} denote its column-normalized adjacency matrix, such that S′S^{\prime} is column stochastic. Given a damping factor λ∈(0,1)\lambda\in(0, 1), the PageRank transition matrix is

S=λS′+1−λn11T.(15)S = \lambda S^{\prime} + \frac{1-\lambda}{n}\mathbf{1}\mathbf{1}^{\mathsf{T}}. \tag*{(15)}

The corresponding PageRank vector can be obtained as a feasible solution to

find⁡x,subject to⁡Sx≤x,1Tx=1,x≥0.(16)\begin{aligned} \operatorname{find}\quad&x,\\ \operatorname{subject\ to}\quad&Sx \le x,\\ &\mathbf{1}^{\mathsf{T}}x = 1,\\ &x \ge0. \tag*{(16)} \end{aligned}

Directly constructing SS would introduce a dense teleportation matrix. Using the normalization constraint 1Tx=1\mathbf{1}^{\mathsf{T}}x = 1, we instead retain the equivalent sparse constraints

λ(S′x)i+1−λn≤xi,i=1,…,n.(17)\lambda(S^{\prime}x)_i + \frac{1-\lambda}{n} \le x_i,\qquad i = 1,\ldots,n. \tag*{(17)}

Synthetic Packing LPs

We construct a family of synthetic packing LPs of the form

min⁡x∈RncTxs.t.⁡1Tx=S,Ax≤b,x≥0.(18)\begin{aligned} \min_{x \in\mathbb{R}^{n}}\quad&c^{\mathsf{T}}x\\ \operatorname{s.t.}\quad&\mathbf{1}^{\mathsf{T}}x = S,\\ &Ax \le b,\\ &x \ge0. \tag*{(18)} \end{aligned}

Each instance has n∈[105,106]n \in[10^{5}, 10^{6}] variables and m=0.1nm = 0.1n inequality constraints. The constraint matrix is generated as

Aij=MijA~ij,Mij∼Bernoulli⁡(ρ),A~ij∼Unif⁡(0.5,1.0),(19)A_{ij} = M_{ij}\widetilde{A}_{ij},\qquad M_{ij} \sim\operatorname{Bernoulli}(\rho),\qquad\widetilde{A}_{ij} \sim\operatorname{Unif}(0.5, 1.0), \tag*{(19)}

with density ρ=100/n\rho= 100/n, so each inequality involves about 100 variables on average. The variables have no explicit upper bounds, and the instances match the LP form in § 3.1 directly. The objective coefficients are sampled as cj∼Unif⁡(−1,2)c_j \sim\operatorname{Unif}(-1, 2).

For each instance, we first sample the equality right-hand side as S∼Unif⁡(0.3,0.7)S \sim\operatorname{Unif}(0.3, 0.7). We then draw

u∼Dirichlet⁡(1n),x0=Su,(20)u \sim\operatorname{Dirichlet}(\mathbf{1}_n), \qquad x_0 = Su, \tag*{(20)}

such that x0≥0x_0 \ge0 and 1Tx0=S\mathbf{1}^{\mathsf{T}}x_0 = S. The inequality right-hand side is constructed as

b=Ax0+s,(21)b = Ax_0 + s, \tag*{(21)}

where the entries of ss are sampled independently. This construction makes x0x_0 feasible and controls instance difficulty through the magnitude of the available slack: larger slack values produce mostly inactive inequalities, whereas smaller values yield a larger fraction of binding constraints at the optimum.

Data splits. The training instances and the in-distribution test set are drawn from the generator above with n∈[105,106]n \in[10^{5}, 10^{6}]. The size-shift test set contains 20 instances with n∈[106,107]n \in[10^{6}, 10^{7}] from the same generator. The distribution-shift test set contains 20 instances whose generation parameters differ from those used for training. The difficulty tiers in Figure 3(c) group 60 held-out instances by their cold-start time. Training, validation, and test instances are generated using disjoint random seeds and checked for duplicate content. For the difficulty study (Figure 3(c)), we sort all test instances by their cold-start time on Gurobi PDHG and split them into three equal-sized groups: the shortest third as Easy, the middle third as Medium, and the longest third as Hard.

Experimental Environment and Measurement Protocol

All experiments were conducted on the same machine. Table 4 summarizes the hardware and software environment.

ComponentConfiguration
GPUNVIDIA A100 PCIe 40GB; driver 580.173.02
CPU2× Intel Xeon Gold 5317; 24 cores, 48 threads
Memory251 GiB
OSUbuntu 24.04.3 LTS; Linux 6.8.0-139
Python3.12.9
PyTorch2.9.0
CUDA toolkit12.0 (V12.0.140)
OR-Tools9.15.6755
Gurobi13.0.3, GPU-enabled build

Table 4. Experimental environment.

Timing metric. Unless stated otherwise, the aggregate end-to-end speedup is

Speedup⁡=∑iTi,cold∑iTi(θ,Ki;ϵ),(22)\operatorname{Speedup} = \frac{\sum_i T_{i,\mathrm{cold}}}{\sum_i T_i(\theta, K_i; \epsilon)}, \tag*{(22)}

where Ti=Twarm+TsolverT_i = T_{\mathrm{warm}} + T_{\mathrm{solver}} is the end-to-end time defined in § 3.

Warm-start iterations and handoff. The number of warm-start iterations KK counts complete PDHG updates whose step-size multipliers are predicted by AHEAD. After KK iterations, AHEAD passes the current primal iterate x^K\hat{x}_K and dual iterate y^K\hat{y}_K to the solver as its initial primal and dual solution; for Gurobi, these are assigned through PStart and DStart. No predictor state or step size is transferred, and the solver continues with its own update rule. The warm-start iterations are included in the end-to-end time. The fixed number of warm-start iterations used as a baseline is selected on validation data.

References

  1. [1]Marcin Andrychowicz, Misha Denil, Sergio Gomez, Matthew W. Hoffman, David Pfau, Tom Schaul, Brendan Shillingford, and Nando de Freitas. Learning to learn by gradient descent by gradient descent. In Advances in Neural Information Processing Systems, volume 29, pp. 3981–3989, 2016. URL https://arxiv.org/abs/1606.04474.
  2. [2]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. In Advances in Neural Information Processing Systems, volume 34, pp. 20243–20257, 2021.arxiv.org/abs/2106.04756
  3. [3]David Applegate, Oliver Hinder, Haihao Lu, and Miles Lubin. Faster first-order primal-dual methods for linear programming using restarts and sharpness. Mathematical Programming, 201(1–2): 133–184, 2023. doi: 10.1007/s10107-022-01901-9. URL https://doi.org/10.1007/s10107-022-01901-9.
  4. [4]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. Mathematical Programming Computation, 2026. doi: 10.1007/s12532-026-00309-2. URL https://doi.org/10.1007/s12532-026-00309-2.
  5. [5]Andrea Banino, Jan Balaguer, and Charles Blundell. PonderNet: Learning to ponder. arXiv preprint arXiv:2107.05407, 2021. doi: 10.48550/arXiv.2107.05407. URL https://arxiv.org/abs/2107.05407. Presented at the 8th ICML Workshop on Automated Machine Learning.
  6. [6]Antonin Chambolle and Thomas Pock. A first-order primal-dual algorithm for convex problems with applications to imaging. Journal of mathematical imaging and vision, 40(1):120–145, 2011.DOI
  7. [7]Tianlong Chen, Xiaohan Chen, Wuyang Chen, Howard Heaton, Jialin Liu, Zhangyang Wang, and Wotao Yin. Learning to optimize: A primer and a benchmark. Journal of Machine Learning Research, 23(189):1–59, 2022. URL https://jmlr.org/papers/v23/21-0308.html.arxiv.org/abs/2103.12828
  8. [8]Xinshi Chen, Hanjun Dai, Yu Li, Xin Gao, and Le Song. Learning to stop while learning to predict. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 1520–1530. PMLR, 2020. URL https://proceedings.mlr.press/v119/chen20c.html.arxiv.org/abs/2006.05082
  9. [9]George B. Dantzig. Linear Programming and Extensions. Princeton University Press, 1963.
  10. [11]Weizhi Gao, Zichao Hou, Han Xu, and Xiaorui Liu. Certified robustness for deep equilibrium models via serialized random smoothing. Advances in Neural Information Processing Systems, 37:1370–1401, 2024a.arxiv.org/abs/2411.00899
  11. [12]Xi Gao, Jinxin Xiong, Akang Wang, Qihong Duan, Jiang Xue, and Qingjiang Shi. IPM-LSTM: A learning-based interior point method for solving nonlinear programs. In Advances in Neural Information Processing Systems, volume 37, pp. 122891–122916, 2024b. URL https://proceedings.neurips.cc/paper_files/paper/2024/hash/de0da9c42ee713f2cea eed7bc40c522d-Abstract-Conference.html.arxiv.org/abs/2410.15731
  12. [13]Tom Goldstein, Min Li, Xiaoming Yuan, Ernie Esser, and Richard Baraniuk. Adaptive primal-dual hybrid gradient methods for saddle-point problems. arXiv preprint arXiv:1305.0546, 2013.arxiv.org/abs/1305.0546
  13. [14]Alex Graves. Adaptive computation time for recurrent neural networks. arXiv preprint arXiv:1603.08983, 2016. doi: 10.48550/arXiv.1603.08983. URL https://arxiv.org/abs/1603.08983.
  14. [15]Zichao Hou, Ruiqi Feng, Tyler Derr, and Xiaorui Liu. Robust graph neural networks via unbiased aggregation. Advances in Neural Information Processing Systems, 37:110097–110130, 2024a.arxiv.org/abs/2311.14934
  15. [17]Zhichao Hou, MohamadAli Torkamani, Hamid Krim, and Xiaorui Liu. Robustness reprogramming for representation learning. In International Conference on Learning Representations, volume 2025, pp. 53682–53704, 2025.arxiv.org/abs/2410.04577
  16. [18]Zhichao Hou, Weizhi Gao, and Xiaorui Liu. Fine-grained iterative adversarial attacks with limited computation budget. In International Conference on Learning Representations, volume 2026, pp. 75235–75250, 2026.arxiv.org/abs/2510.26981
  17. [19]Anatoli Iouditski and Yuri Nesterov. Primal-dual subgradient methods for minimizing uniformly convex functions, 2014. URL https://arxiv.org/abs/1401.1792.
  18. [20]Tomoharu Iwata and Shinsaku Sakaue. Learning to generate projections for reducing dimensionality of heterogeneous linear programming problems. In Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pp. 26627–26641. PMLR, 2025.
  19. [21]Yufei Kuang, Xijun Li, Jie Wang, Fangzhou Zhu, Meng Lu, Zhihai Wang, Jia Zeng, Houqiang Li, Yongdong Zhang, and Feng Wu. Accelerate presolve in large-scale linear programming via reinforcement learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 47 (8):6660–6672, 2025. doi: 10.1109/TPAMI.2025.3562286. URL https://doi.org/10.1109/TPAMI.2025.3562286.
  20. [22]Bingheng Li, Linxin Yang, Yupeng Chen, Semmiao Wang, Haitao Mao, Qian Chen, Yao Ma, Akang Wang, Tian Dong, Jiliang Tang, and Ruoyu Sun. PDHG-unrolled learning-to-optimize method for large-scale linear programming. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 29164–29180. PMLR, 2024. URL https://proceedings.mlr.press/v235/li24ce.html.arxiv.org/abs/2406.01908
  21. [23]Ke Li and Jitendra Malik. Learning to optimize. arXiv preprint arXiv:1606.01885, 2016. doi: 10.48550/arXiv.1606.01885. URL https://arxiv.org/abs/1606.01885.
  22. [24]Xijun Li, Qingyu Qu, Fangzhou Zhu, Jia Zeng, Mingxuan Yuan, Kun Mao, and Jie Wang. Learning to reformulate for linear programming. arXiv preprint arXiv:2201.06216, 2022. doi: 10.48550/arXiv.2201.06216. URL https://arxiv.org/abs/2201.06216.
  23. [25]Tianyi Lin, Shiqian Ma, Yinyu Ye, and Shuzhong Zhang. An ADMM-based interior-point method for large-scale linear programming. Optimization Methods and Software, 36(2–3):389–424, 2021. doi: 10.1080/10556788.2020.1821200.DOI
  24. [26]Jialin Liu, Xiaohan Chen, Zhangyang Wang, Wotao Yin, and Hanqin Cai. Towards constituting mathematical structures for learning to optimize. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 21426–21449. PMLR, 2023. URL https://proceedings.mlr.press/v202/liu23e.html.arxiv.org/abs/2305.18577
  25. [29]Haihao Lu and Jinwen Yang. cuPDLP.jl: A GPU implementation of restarted primal-dual hybrid gradient for linear programming in Julia. Operations Research, 73(6):3440–3452, 2025. doi: 10.1287/opre.2024.1069. URL https://doi.org/10.1287/opre.2024.1069.
  26. [30]Yura Malitsky and Thomas Pock. A first-order primal-dual algorithm with linesearch. SIAM Journal on Optimization, 28(1):411–432, 2018. doi: 10.1137/16M1092015. URL https://doi.org/10.1137/16M1092015.
  27. [31]Yurii Nesterov. Subgradient methods for huge-scale optimization problems. Mathematical Programming, 146(1–2):275–297, 2014. doi: 10.1007/s10107-013-0686-4.DOI
  28. [32]Alex Oshin, Rahul Ghosh, Augustinos Saravanos, and Evangelos Theodorou. Deep FlexQP: Accelerated nonlinear programming via deep unfolding. In International Conference on Learning Representations, 2026. URL https://proceedings.iclr.cc/paper_files/paper/2026/hash/84cd19dedba8b8b7461d86c246f2c372-Abstract-Conference.html.arxiv.org/abs/2512.01565
  29. [33]Chendi Qian, Didier Chételat, and Christopher Morris. Exploring the power of graph neural networks in solving linear optimization problems. In Proceedings of the 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pp. 1432–1440. PMLR, 2024. URL https://proceedings.mlr.press/v238/qian24a.html.arxiv.org/abs/2310.10603
  30. [34]Rajiv Sambharya, Georgina Hall, Brandon Amos, and Bartolomeo Stellato. Learning to warm-start fixed-point optimization algorithms. Journal of Machine Learning Research, 25(166):1–46, 2024. URL https://jmlr.org/papers/v25/23-1174.html.arxiv.org/abs/2309.07835
  31. [35]Avi Schwarzschild, Eitan Borgnia, Arjun Gupta, Furong Huang, Uzi Vishkin, Micah Goldblum, and Tom Goldstein. Can you learn an algorithm? generalizing from easy to hard problems with recurrent networks, 2021. URL https://arxiv.org/abs/2106.04537.
  32. [36]Michael Sucker and Peter Ochs. A generalization result for convergence in learning-to-optimize. In Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pp. 57212–57230. PMLR, 2025.arxiv.org/abs/2410.07704
  33. [37]Olga Wichrowska, Niru Maheswaranathan, Matthew W. Hoffman, Sergio Gómez Colmenarejo, Misha Denil, Nando de Freitas, and Jascha Sohl-Dickstein. Learned optimizers that scale and generalize. In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 3751–3760. PMLR, 2017. URL https://proceedings.mlr.press/v70/wichrowska17a.html.arxiv.org/abs/1703.04813

Paper details

vlnc:W_392n8rut
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents