Research map / Learning theory and algorithms / Matrix and tensor methods

The Geometry of Linear Program Compression: An Exact Characterization and Learning Algorithm

NeurIPS 2026 · Learning theory and algorithms › Matrix and tensor methods · approach: Randomized sketching for matrices · 0 citations (OpenAlex)

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.

Gives an exact geometric characterization of LP compression via the decision-relevant subspace, and a sample-based stable-compression learner with a 1/n fast-rate guarantee for recovering optimal solutions of unseen LPs.

Problem

Compressing repeatedly solved LPs with varying objective costs into lower-dimensional equivalent LPs while exactly preserving optimality, given a prior cost set or historical cost samples; existing projection methods give only approximate guarantees.

Approach

Uses the decision-relevant subspace dir(X*(C)) to build an affine (anchored) exact reduction, learns a basis incrementally by appending vertex-difference directions only on samples whose optimal face leaves the current slice, and certifies generalization via stable sample compression (1/n rate); adds a calibrated convex estimated prior to trade compression for coverage.

Key results

• Exact-compression certificate: with probability at least 1-delta, P[Exact] >= 1 - (4/n)(6 d* + log(e/delta)), i.e. a 1/n rate versus 1/sqrt(n) for uniform-convergence projection methods.
• Learned dimension stabilizes quickly on MinCostFlow and RandomLP families, while Packing and GROW7 need larger subspaces (reported qualitatively).
• Empirically, the calibrated exact method is reported to outperform the FCNN-c and DataDrivenProj baselines at matched dimension, but no numeric values appear in the main text excerpt.

Surprising findings

• Any one-dimensional homogeneous (through-origin) projection incurs expected objective gap at least 1/2 on a simple example where an affine one-variable reduction is exact.

Limitations

• Theory restricted to linear programs; extension to MIP and convex QP left open.
• Empirical evaluation limited to synthetic and Netlib instances, not real-world repeated-LP deployments.
• Exact-sketching guarantee for the full prior can require d* dimensions, which may be large; the sample bound depends on d* and is only a probability bound.

Experimental setup

Datasets: synthetic repeated-LP families Netlib LP instances

Benchmarks: synthetic repeated-LP families (MinCostFlow, RandomLP, Packing, GROW7) Netlib instances

Metrics: average test objective ratio learned compression dimension

Baselines: DataDrivenProj FCNN-c random projections

Builds on: sufficient decision dataset characterization stable compression schemes data-driven LP projection learning

Closest papers by meaning

• Generalization Bound and Learning Methods for Data-Driven Projections in Linear Programming (NeurIPS 2024 · similarity 0.87)
• Solver-Aware Decompositions for Programming-by-Example: When Dividing Requires Knowing how to Conquer (NeurIPS 2026 · similarity 0.83)
• CompilerKV: Risk-Adaptive KV Cache Compression via Offline Experience Compilation (NeurIPS 2026 · similarity 0.83)
• Accelerated Methods with Compressed Communications for Distributed Optimization Problems Under Data Similarity (AAAI 2025 · similarity 0.83)
• Agnostic Sample Compression Schemes for Regression (ICML 2024 · similarity 0.83)
• Scalable Distributed Stochastic Optimization via Bidirectional Compression: Beyond Pessimistic Limits (NeurIPS 2026 · similarity 0.83)