# Parameter Tuning with Generalization Guarantees for GPU-Accelerated Linear Programming

arXiv: https://arxiv.org/abs/2606.08638 · HTML: https://mlsanity.com/paper/2606.08638/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 41 references that are in the map.
- First posted on arXiv 7 Jun 2026.

## Builds on (most cited first, 21 of 21)

- [Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond](https://mlsanity.com/paper/2106.04033/) (2021)
- [Practical Large-Scale Linear Programming using Primal-Dual Hybrid Gradient](https://mlsanity.com/paper/2106.04756/) (2021)
- [How much data is sufficient to learn high-performing algorithms? Generalization guarantees for data-driven algorithm design](https://mlsanity.com/paper/1908.02894/) (2019)
- [Generalization Bounds for Data-Driven Numerical Linear Algebra](https://mlsanity.com/paper/2206.07886/) (2022)
- [Structural Analysis of Branch-and-Cut and the Learnability of Gomory Mixed Integer Cuts](https://mlsanity.com/paper/2204.07312/) (2022)
- [Improved Sample Complexity Bounds for Branch-and-Cut](https://mlsanity.com/paper/2111.11207/) (2021)
- [Generalization Guarantees for Multi-item Profit Maximization: Pricing, Auctions, and Randomized Mechanisms](https://mlsanity.com/paper/1705.00243/) (2017)
- [Algorithm Configuration for Structured Pfaffian Settings](https://mlsanity.com/paper/2409.04367/) (2024)
- [Generalization Bound and Learning Methods for Data-Driven Projections in Linear Programming](https://mlsanity.com/paper/2309.00203/) (2023)
- [A Practical and Optimal First-Order Method for Large-Scale Convex Quadratic Programming](https://mlsanity.com/paper/2311.07710/) (2023)
- [cuPDLP.jl: A GPU Implementation of Restarted Primal-Dual Hybrid Gradient for Linear Programming in Julia](https://mlsanity.com/paper/2311.12180/) (2023)
- [Sample complexity of data-driven tuning of model hyperparameters in neural networks with structured parameter-dependent dual function](https://mlsanity.com/paper/2501.13734/) (2025)
- [Sample Complexity of Algorithm Selection Using Neural Networks and Its Applications to Branch-and-Cut](https://mlsanity.com/paper/2402.02328/) (2024)
- [MPAX: Mathematical Programming in JAX](https://mlsanity.com/paper/2412.09734/) (2024)
- [Restarted Halpern PDHG for Linear Programming](https://mlsanity.com/paper/2407.16144/) (2024)
- [cuPDLPx: A Further Enhanced GPU-Based First-Order Solver for Linear Programming](https://mlsanity.com/paper/2507.14051/) (2025)
- [Provably data-driven projection method for quadratic programming](https://mlsanity.com/paper/2509.04524/) (2025)
- [Restarted Primal-Dual Hybrid Conjugate Gradient Method for Large-Scale Quadratic Programming](https://mlsanity.com/paper/2405.16160/) (2024)
- [Provably Data-driven Lagrangian Relaxation for Mixed Integer Linear Programming](https://mlsanity.com/paper/2605.19052/) (2026)
- [An Overview of GPU-based First-Order Methods for Linear Programming and Extensions](https://mlsanity.com/paper/2506.02174/) (2025)
- [Gradient Descent with Provably Tuned Learning-rate Schedules](https://mlsanity.com/paper/2512.05084/) (2025)

## Abstract (arXiv)

Recent research has developed practical, parallelizable first-order methods for large scale linear programming, but performance is highly dependent on hyperparameter selection. We derive generalization guarantees for hyperparameter tuning within (cu)PDLP, a state-of-the-art first-order LP solver designed for modern hardware. First, we pin down the behavior of PDHG, the primal-dual hybrid gradient algorithm that underlies PDLP, as a function of its step size and primal weight, leading to linear sample complexity guarantees for learning those parameters. We then conduct a structural analysis of PDLP, which augments PDHG with several specialized techniques like preconditioning, adaptive step sizes, averaging, adaptive restarts, and smoothed primal weight updates. Our analysis captures the behavior of the solution trajectory as a function of the hyperparameters and leverages recent advances in data-driven algorithm design to obtain polynomial sample complexity guarantees for learning those hyperparameters. Finally, we conduct proof-of-concept experiments that demonstrate the need for data-driven PDLP parameter tuning. Our results showcase the versatility of the data-driven algorithm design toolkit for principled hyperparameter tuning within solver-grade implementations of complex modern optimization algorithms.