Research map / Optimization / Optimizers
Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update
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 |
|---|---|---|---|
| Replace the dense Gaussian embedding with a LESS embedding | Newton Sketch · General convex optimization, local convergence | local convergence rate: Gaussian Newton Sketch: \frac dm; Newton-LESS: \frac dm | No clear effect |
| Replace the dense Gaussian embedding with a LESS embedding | Newton Sketch · Least squares regression, global convergence | excess function value convergence rate: Prior guarantee: (C\log d\cdot\frac dm)^T; Newton-LESS: (\frac dm)^T | Helped |
| Use regularization and sketch only the unregularized Hessian component | Newton-LESS · Regularized minimization | local convergence rate: \frac{f}{m} | Helped |
| Reduce the row density to about d non-zeros per row (ablation) | LESS-uniform Newton Sketch · Least squares regression | convergence rate | No clear effect |
| Drastically decrease row density from the dense sketch (ablation) | LESS-uniform Newton Sketch · Least squares regression, datasets other than CIFAR-10 | convergence rate | No clear effect |
| Use random row sampling instead of a denser embedding (ablation) | Newton Sketch · Least squares regression, CIFAR-10 | convergence rate | No clear effect |
| Use LESS-uniform sketching rather than Gaussian, SRHT, or random row sampling | Newton Sketch · Regularized logistic regression, CIFAR-10, Musk, and WESAD | wall-clock time | Helped |
Closest papers by meaning
- Adaptive Newton Sketch: Linear-time Optimization with Quadratic Convergence and Effective Hessian Dimensionality (ICML 2021 · similarity 0.92)
- Newton Meets Marchenko-Pastur: Massively Parallel Second-Order Optimization with Hessian Sketching and Debiasing (ICLR 2025 · similarity 0.89)
- Sketching for Convex and Nonconvex Regularized Least Squares with Sharp Guarantees (ICLR 2025 · similarity 0.88)
- Distributed Least Squares in Small Space via Sketching and Bias Reduction (NeurIPS 2024 · similarity 0.88)
- Fundamental Bias in Inverting Random Sampling Matrices with Application to Sub-sampled Newton (ICML 2025 · similarity 0.88)
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms (ICLR 2024 · similarity 0.87)
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.