Research map / Learning theory and algorithms / Combinatorial and search optimization
Faster Randomized Infeasible Interior Point Methods for Tall/Wide Linear Programs
Agniva Chowdhury, Palma London, Haim Avron, Petros Drineas
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| precondition the normal equations with sketching (Algorithm 2) instead of plain CG | standard IPM with CG · ARCENE l1-SVM LP | inner CG iterations: 1,000 -> 15 to 35 | Improved |
| sketching improves conditioning of normal equations matrix | standard IPM with CG · ARCENE | condition number: 10^8 -> lower | Improved |
| decrease sketch dimension w from 1000 to 200 (ablation) | Sketched IPM · ARCENE | inner CG iterations | Hurt |
| vary w and tolCG over grid (ablation) | Sketched IPM · ARCENE | inner iterations: 15 to 35 | No clear effect |
| increase both tolCG and w (ablation) | Sketched IPM · ARCENE | condition number | Improved |
| use sketched preconditioning instead of standard solver | Sketched IPM · ARCENE | outer iterations | No clear effect |
| vary (w,tolCG) settings (ablation) | Sketched IPM · ARCENE | relative error: 0.04% | No clear effect |
Closest papers by meaning
- Faster Randomized Interior Point Methods for Tall/Wide Linear Programs (JMLR 2022 · similarity 0.98)
- On the Convergence of Inexact Predictor-Corrector Methods for Linear Programming (ICML 2022 · similarity 0.94)
- Accelerated Infeasibility Detection of Constrained Optimization and Fixed-Point Iterations (ICML 2023 · similarity 0.87)
- IPM-LSTM: A Learning-Based Interior Point Method for Solving Nonlinear Programs (NeurIPS 2024 · similarity 0.86)
- A Differentiable Interior-Point Method in Single Precision (NeurIPS 2026 · similarity 0.86)
- Provable Acceleration of Nesterov's Accelerated Gradient for Asymmetric Matrix Factorization and Linear Neural Networks (NeurIPS 2024 · similarity 0.85)
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.
