# Generalization Bound and Learning Methods for Data-Driven Projections in Linear Programming

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 48 references that are in the map.
- First posted on arXiv 1 Sep 2023.

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

- [OptNet: Differentiable Optimization as a Layer in Neural Networks](https://mlsanity.com/paper/1703.00443/) (2017)
- [Differentiable Convex Optimization Layers](https://mlsanity.com/paper/1910.12430/) (2019)
- [Smart "Predict, then Optimize"](https://mlsanity.com/paper/1710.08005/) (2017)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Melding the Data-Decisions Pipeline: Decision-Focused Learning for Combinatorial Optimization](https://mlsanity.com/paper/1809.05504/) (2018)
- [Solving Linear Programs in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1810.07896/) (2018)
- [Parallelizing the dual revised simplex method](https://mlsanity.com/paper/1503.01889/) (2015)
- [Tutorial on amortized optimization](https://mlsanity.com/paper/2202.00665/) (2022)
- [On the Global Linear Convergence of Frank-Wolfe Optimization Variants](https://mlsanity.com/paper/1511.05932/) (2015)
- [A PAC Approach to Application-Specific Algorithm Selection](https://mlsanity.com/paper/1511.07147/) (2015)
- [Generalization Bounds in the Predict-then-Optimize Framework](https://mlsanity.com/paper/1905.11488/) (2019)
- [Learning-Based Low-Rank Approximations](https://mlsanity.com/paper/1910.13984/) (2019)
- [Practical Large-Scale Linear Programming using Primal-Dual Hybrid Gradient](https://mlsanity.com/paper/2106.04756/) (2021)
- [Generalization Bounds for Data-Driven Numerical Linear Algebra](https://mlsanity.com/paper/2206.07886/) (2022)
- [Automatically Learning Compact Quality-aware Surrogates for Optimization Problems](https://mlsanity.com/paper/2006.10815/) (2020)
- [Learning the Positions in CountSketch](https://mlsanity.com/paper/2007.09890/) (2020)
- [Structural Analysis of Branch-and-Cut and the Learnability of Gomory Mixed Integer Cuts](https://mlsanity.com/paper/2204.07312/) (2022)
- [Learning Linear Programs from Optimal Decisions](https://mlsanity.com/paper/2006.08923/) (2020)
- [Improved Sample Complexity Bounds for Branch-and-Cut](https://mlsanity.com/paper/2111.11207/) (2021)
- [Frank-Wolfe with a Nearest Extreme Point Oracle](https://mlsanity.com/paper/2102.02029/) (2021)
- [Random projections for linear programming](https://mlsanity.com/paper/1706.02768/) (2017)
- [Sample Complexity of Learning Heuristic Functions for Greedy-Best-First and A* Search](https://mlsanity.com/paper/2205.09963/) (2022)
- [AI4OPT: AI Institute for Advances in Optimization](https://mlsanity.com/paper/2307.02671/) (2023)
- [Improved Generalization Bound and Learning of Sparsity Patterns for Data-Driven Low-Rank Approximation](https://mlsanity.com/paper/2209.08281/) (2022)
- [Random projection of Linear and Semidefinite problem with linear inequalities](https://mlsanity.com/paper/2007.00242/) (2020)
- [Column-Randomized Linear Programs: Performance Guarantees and Applications](https://mlsanity.com/paper/2007.10461/) (2020)
- [Faster Randomized Interior Point Methods for Tall/Wide Linear Programs](https://mlsanity.com/paper/2209.08722/) (2022)

## Built on by (most cited first, 10 of 10)

- [Provably data-driven projection method for quadratic programming](https://mlsanity.com/paper/2509.04524/) (2025)
- [Distribution-dependent Generalization Bounds for Tuning Linear Regression Across Tasks](https://mlsanity.com/paper/2507.05084/) (2025)
- [Algorithm Design and Stronger Guarantees for the Improving Multi-Armed Bandits Problem](https://mlsanity.com/paper/2511.10619/) (2025)
- [Provably Data-driven Multiple Hyper-parameter Tuning with Structured Loss Function](https://mlsanity.com/paper/2602.02406/) (2026)
- [Gradient Descent with Provably Tuned Learning-rate Schedules](https://mlsanity.com/paper/2512.05084/) (2025)
- [Learning Decision-Sufficient Representations for Linear Optimization](https://mlsanity.com/paper/2603.18551/) (2026)
- [Generalization Guarantees for Learning Branch-and-Cut Policies in Integer Programming](https://mlsanity.com/paper/2505.11636/) (2025)
- [Data-driven Projection Generation for Efficiently Solving Heterogeneous Quadratic Programming Problems](https://mlsanity.com/paper/2510.26061/) (2025)
- [Parameter Tuning with Generalization Guarantees for GPU-Accelerated Linear Programming](https://mlsanity.com/paper/2606.08638/) (2026)
- [Tight Bounds for Data-driven Multiple Hyper-parameter Tuning with Structured Loss Function](https://mlsanity.com/paper/2608.17343/) (2026)

## Abstract (arXiv)

How to solve high-dimensional linear programs (LPs) efficiently is a fundamental question. Recently, there has been a surge of interest in reducing LP sizes using random projections, which can accelerate solving LPs independently of improving LP solvers. This paper explores a new direction of data-driven projections, which use projection matrices learned from data instead of random projection matrices. Given training data of n-dimensional LPs, we learn an n× k projection matrix with n > k. When addressing a future LP instance, we reduce its dimensionality from n to k via the learned projection matrix, solve the resulting LP to obtain a k-dimensional solution, and apply the learned matrix to it to recover an n-dimensional solution. On the theoretical side, a natural question is: how much data is sufficient to ensure the quality of recovered solutions? We address this question based on the framework of data-driven algorithm design, which connects the amount of data sufficient for establishing generalization bounds to the pseudo-dimension of performance metrics. We obtain an tildeO(nk2) upper bound on the pseudo-dimension, where tildeO compresses logarithmic factors. We also provide an Omega(nk) lower bound, implying our result is tight up to an tildeO(k) factor. On the practical side, we explore two simple methods for learning projection matrices: PCA- and gradient-based methods. While the former is relatively efficient, the latter can sometimes achieve better solution quality. Experiments demonstrate that learning projection matrices from data is indeed beneficial: it leads to significantly higher solution quality than the existing random projection while greatly reducing the time for solving LPs.