Research map / Learning theory and algorithms / Matrix and tensor methods
Optimal Randomized First-Order Methods for Least-Squares Problems
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 the optimal first-order update with a fixed SRHT embedding instead of the best fixed-Gaussian first-order method | First-order methods for least-squares · Overdetermined least-squares (asymptotic) | convergence rate: \rho -> \frac{1-\xi}{1-\gamma} \rho | Helped |
| Use the optimal fixed-SRHT first-order method instead of Heavy-ball with a refreshed SRHT embedding | First-order methods for least-squares · Overdetermined least-squares (asymptotic) | convergence rate: \rho_h < \rho_h^\text{ref} | Helped |
| Use an optimal first-order update with a fixed Gaussian embedding instead of fixed SRHT | First-order methods for least-squares · Overdetermined least-squares (asymptotic) | convergence rate: \frac{1-\xi}{1-\gamma} \rho < \rho | Hurt |
| Use SRHT sketch size m \asymp d with the proposed method instead of the prescribed sketch size m \asymp d \log d with pre-conditioned conjugate gradient | Dense least-squares solver · Dense least-squares (fixed error \varepsilon) | complexity: \frac{C_{\text{fhs}}}{C_{\text{cg}}} \asymp \frac{1}{\log d} | Helped |
| Use the fixed-SRHT optimal first-order method instead of Heavy-ball with refreshed SRHT | Dense least-squares solver · Dense least-squares (arbitrary sketch size m) | complexity: \mathcal{C}_{\text{fhs}} \leqslant \mathcal{C}_{\text{ihs}} | Helped |
| Use the optimal SRHT first-order method instead of a Heavy-ball update with fixed parameters based on edge eigenvalues | First-order methods for least-squares · SRHT empirical convergence curves | error | Helped |
| Set the sketch size to m=n for the optimal SRHT first-order method | Optimal first-order method · Overdetermined least-squares (asymptotic) | iterations to converge: one iteration | Helped |
Closest papers by meaning
- Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization (NeurIPS 2020 · similarity 0.92)
- Optimization Can Learn Johnson Lindenstrauss Embeddings (NeurIPS 2024 · similarity 0.88)
- Improving Convergence Guarantees of Random Subspace Second-order Algorithm for Nonconvex Optimization (ICLR 2025 · similarity 0.86)
- Fundamental Bias in Inverting Random Sampling Matrices with Application to Sub-sampled Newton (ICML 2025 · similarity 0.86)
- Debiasing Random Oblique Projections for Subsampled OLS and Fast CUR in High Dimensions (NeurIPS 2026 · similarity 0.85)
- Distributed Least Squares in Small Space via Sketching and Bias Reduction (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.