Fast Algorithms for Regression Problems
summary
Presents a concrete algorithmic claim: p‑norm regression for p>2 gets high‑accuracy solutions by reducing to a sequence of L2 solves and converges in m^{1/3} iterations rather than m^{1/2. It combines iterative refinement (global envelopes built from gradient, Hessian and a p‑term) with a width‑reduced multiplicative‑weights solver that penalizes large coordinates. Generalizes to quasi self‑concordant losses, uses inverse‑maintenance to approach m^{2.33+o(1)} time on dense instances, and an IRLS variant reaches ~1e-12 accuracy* in practice, often 10–50× faster on benchmarks.
AI-written summary · about
chapters (11)
- 0:00Introduction
- 7:20p-norm regression for p>2
- 10:41Faster algorithm with m to the one third iterations
- 18:15Residual problem with multiplicative weights
- 23:13Fast solver properties
- 28:57Iterative refinement for accuracy
- 35:37Sparse graph rates
- 39:43Fast IRLS algorithms
- 41:33Ball Oracle methods
- 46:56Open problems
- 47:40Summary
related talks
29mImplicit Regularization in Nonconvex Statistical Estimation
01h 23mImplicit Regularization II
01h 01mRobustness, Stochastics, Uncertainty 2
01h 30mHigh-Dimensional Statistics II
01h 06mAnalytic Methods for Supervised Learning III
41mTransfer learning via local convergence rates of the nonparametric least squares estimator
01h 18mOptimization I
01h 05mOptimization for Machine Learning I