Research map / Learning theory and algorithms / Kernels and regression theory
Fast, Provably convergent IRLS Algorithm for p-norm Linear Regression
Deeksha Adil, Richard Peng, Sushant Sachdeva
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 |
|---|---|---|---|
| Use p-IRLS instead of CVX | ℓp-regression on random matrices · Random matrix ℓp-regression | runtime: 30--50 times | Improved |
| Use p-IRLS instead of CVX | p-Laplacian minimization · Graph p-Laplacian minimization | runtime: 10--30 times | Improved |
| Use p-IRLS instead of CVX | ℓp-regression and graph p-Laplacian minimization · Random matrices and graphs | objective value | Improved |
| Use p-IRLS instead of IRLS/Homotopy | p-Laplacian semi-supervised learning · Hardest benchmark problem, equal iteration count | error: orders of magnitudes smaller | Improved |
| Increase target accuracy by reducing ε | p-IRLS · Random matrices and graphs | iterations: linearly with log(1/ε) | Hurt |
| Increase problem size | p-IRLS · Random matrices and graphs | iterations: nearly constant | No clear effect |
| Increase p | p-IRLS · Random matrices and graphs | iterations: at most linear | Hurt |
| Add systematic padding to the IRLS weights and perform a line search | Standard IRLS for ℓp-regression · ℓp-regression, p ∈ [2,∞) | convergence | Improved |
Closest papers by meaning
- Improved $\ell_{p}$ Regression via Iteratively Reweighted Least Squares (ICLR 2026 · similarity 0.87)
- Global Linear and Local Superlinear Convergence of IRLS for Non-Smooth Robust Regression (NeurIPS 2022 · similarity 0.86)
- Improved Convergence for $\ell_1$ and $\ell_∞$ Regression via Iteratively Reweighted Least Squares (ICML 2019 · similarity 0.86)
- An Analysis of Sketched IRLS for Accelerated Sparse Residual Regression (ECCV 2020 · similarity 0.84)
- Efficient Symmetric Norm Regression via Linear Sketching (NeurIPS 2019 · similarity 0.84)
- Towards Optimal Sobolev Norm Rates for the Vector-Valued Regularized Least-Squares Algorithm (JMLR 2024 · 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.
