Research map / Learning theory and algorithms / Matrix and tensor methods
Generalization Bound and Learning Methods for Data-Driven Projections in Linear Programming
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes data-driven projections that learn an n×k projection matrix from LP training instances to reduce LP dimensionality, proving an Õ(nk²) pseudo-dimension upper bound and Ω(nk) lower bound, with PCA- and gradient-based learning methods.
Problem
Solving high-dimensional linear programs efficiently; random projections reduce LP size but ignore data, and it is unknown how many training LP instances are needed to guarantee the quality of solutions recovered via learned projections.
Approach
Learn the projection matrix from training LP instances (rather than sampling it randomly) within the data-driven algorithm design framework; bound its generalization via pseudo-dimension, using a piecewise-polynomial sign-pattern analysis of LP optimal values with Warren's theorem.
Key results
- On most datasets, PCA and/or SGA with largest k achieved about 95% to 99% objective ratios while being about 4 to 70 times faster than the full LP.
- On STAIR, PCA and SGA attained 13.1% and 51.2% objective ratios, while ColRand achieved near-zero ratios in most cases except Packing and ISRAEL.
- Theory: pseudo-dimension is O(nk^2 log mk) upper bound and Omega(nk) lower bound.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use data-driven projection (PCA and/or SGA) instead of column-randomized projection | LP dimensionality reduction · Most tested datasets | objective ratio | Helped |
| Use data-driven projection (PCA and/or SGA) instead of solving the full LP | LP dimensionality reduction · Datasets except STAIR | solving speed: about 4 to 70 times faster | Helped |
| Replace PCA with SGA | PCA projection method · Packing, MaxFlow, MinCostFlow, STAIR; GROW7 and SC205 similarly | objective value | Helped |
| Replace PCA with SGA | PCA projection method · ISRAEL and SCAGR25 | objective value | Hurt |
| Initialize SGA with ColRand instead of PCA (ablation) | SGA · MinCostFlow, GROW7, SC205, and SCAGR25 | objective ratio | Hurt |
Surprising findings
- SGA was worse than PCA on ISRAEL and SCAGR25, attributed to non-convexity of the objective optimization.
Limitations
- Applies only to LPs with fixed equality constraints and a common feasible point; cannot handle varying equality constraints.
- Learning methods are computationally costly, especially SGA, and experiments limited to moderate-size LPs.
- Projection does not improve theoretical time complexity and ignores solver-specific sparsity and numerical aspects.
Experimental setup
Datasets: Packing (synthetic) MaxFlow (synthetic) MinCostFlow (synthetic) GROW7 (Netlib) ISRAEL (Netlib) SC205 (Netlib) SCAGR25 (Netlib) STAIR (Netlib)
Benchmarks: Packing MaxFlow MinCostFlow GROW7 ISRAEL SC205 SCAGR25 STAIR
Metrics: objective ratio relative to full LP optimum Gurobi running time
Baselines: Full ColRand
Builds on: random projections for LPs data-driven algorithm design Warren's theorem column-randomized LP reduction
Closest papers by meaning
- Provably Data-Driven Projection Method for Quadratic Programming (AAAI 2026 · similarity 0.91)
- Learning to Generate Projections for Reducing Dimensionality of Heterogeneous Linear Programming Problems (ICML 2025 · similarity 0.90)
- The Geometry of Linear Program Compression: An Exact Characterization and Learning Algorithm (NeurIPS 2026 · similarity 0.87)
- Tighter CMI-Based Generalization Bounds via Stochastic Projection and Quantization (NeurIPS 2025 · similarity 0.85)
- Learning Generalized Linear Programming Value Functions (NeurIPS 2024 · similarity 0.84)
- Generalization Bound of Gradient Flow through Training Trajectory and Data-dependent Kernel (NeurIPS 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.