Research map / Learning theory and algorithms / Sample complexity
Improved Convergence for $\ell_1$ and $\ell_∞$ Regression via Iteratively Reweighted Least Squares
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (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 |
|---|---|---|---|
| Use long-step updates instead of short-step updates (ablation) | IRLS for ℓ∞ regression · Random 150 × 200 matrices with orthogonal rows; ε = 1/2^k, k ∈ {1, …, 12} | iterations | Helped |
| Use long-step updates instead of short-step updates (ablation) | IRLS for ℓ1 and ℓ∞ regression · Random regression instances | iterations and running time | Helped |
| Vary the number of columns m | IRLS for ℓ1 and ℓ∞ regression · Random 150 × (200·k) matrices; ε = .01 | iterations and running time | Helped |
| Vary ε using short-step updates | IRLS for ℓ1 and ℓ∞ regression · Random 150 × 200 matrices with orthogonal rows | iterations | Mixed |
Closest papers by meaning
- Precise asymptotics of reweighted least-squares algorithms for linear diagonal networks (NeurIPS 2024 · similarity 0.87)
- Quasi-Self-Concordant Optimization with $\ell_{\infty}$ Lewis Weights (NeurIPS 2025 · similarity 0.86)
- Unveiling the Cycloid Trajectory of EM Iterations in Mixed Linear Regression (ICML 2024 · similarity 0.85)
- Transformers Learn to Achieve Second-Order Convergence Rates for In-Context Linear Regression (NeurIPS 2024 · similarity 0.85)
- Coresets for Multiple $\ell_p$ Regression (ICML 2024 · similarity 0.84)
- Robust Sparse Regression with Non-Isotropic Designs (NeurIPS 2024 · similarity 0.84)
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.