Research map / Learning theory and algorithms / Matrix and tensor methods
Large Scale Constrained Linear Regression Revisited: Faster Algorithms via Preconditioning
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 |
|---|---|---|---|
| Increase HDpwBatchSGD batch size by a factor of 2 (ablation) | HDpwBatchSGD · Syn1 and Syn2, unconstrained | iteration complexity: factor of b=2 | Helped |
| Increase batch size in the low-precision ℓ2-constrained setting (ablation) | HDpwBatchSGD · Buzz, ℓ2 constrained, low precision | relative error convergence | No clear effect |
| Use two-step preconditioning and mini-batch SGD with uniform sampling | HDpwBatchSGD · Low-precision linear regression experiments | running time | Helped |
| Use accelerated mini-batch SGD instead of ordinary mini-batch SGD | HDpwAccBatchSGD · Low-precision constrained linear regression | time complexity: O\left(nd\log{n} + \frac{d^2\log{n}}{\epsilon^2}) + \frac{\text{poly}(d)\log{n}}{r\epsilon^2}\right) -> O\left(nd\log{n} | Helped |
| Use one fixed sketch instead of a sequence of sketches | pwGradient compared with IHS · High-precision linear regression | time complexity: O\left((nd\log d+\text{poly}(d))\log{\frac{1}{\epsilon}}\right) -> O(nd\log d+(nd+\text{poly}(d))\log\frac{1}{\epsilon}) | Helped |
| Use pwGradient instead of stochastic methods | High-precision solvers · Synthetic and real datasets | running time | Helped |
| Use HDpwBatchSGD with a large batch instead of pwSGD | Low-precision solvers · Low-precision experiments | running time | Helped |
Closest papers by meaning
- Large Stepsizes Accelerate Gradient Descent for Regularized Logistic Regression (NeurIPS 2025 · similarity 0.88)
- Gradient Descent Converges Arbitrarily Fast for Logistic Regression via Large and Adaptive Stepsizes (ICML 2025 · similarity 0.87)
- Accelerated Sparse Linear Regression via Random Projection (AAAI 2016 · similarity 0.87)
- (S)GD over Diagonal Linear Networks: Implicit bias, Large Stepsizes and Edge of Stability (NeurIPS 2023 · similarity 0.87)
- Scalable First-order Method for Certifying Optimal k-Sparse GLMs (ICML 2025 · similarity 0.87)
- Optimal Rates in Continual Linear Regression via Increasing Regularization (NeurIPS 2025 · similarity 0.86)
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.