Research map / Learning theory and algorithms / Matrix and tensor methods
A Nearly-Optimal Bound for Fast Regression with $\ell_\infty$ Guarantee
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 dense sketches (SRHT) with m=eps^-2 d log^3(n/delta) rows rather than prior d^{1+gamma} rows | sketch-and-solve regression with l_inf guarantee · theoretical row count | row count | Helped |
| Require pairwise column inner products of the sketch to be small (OCE property) as the mechanism for l_inf guarantee | dense sketching matrices · theoretical analysis | l_inf guarantee preserved | No clear effect |
Closest papers by meaning
- Fast Regression for Structured Inputs (ICLR 2022 · similarity 0.89)
- Optimal bounds for $\ell_p$ sensitivity sampling via $\ell_2$ augmentation (ICML 2024 · similarity 0.87)
- Robust Sparse Regression with Non-Isotropic Designs (NeurIPS 2024 · similarity 0.87)
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms (ICLR 2024 · similarity 0.86)
- Agnostic Sample Compression Schemes for Regression (ICML 2024 · similarity 0.86)
- Coresets for Multiple $\ell_p$ Regression (ICML 2024 · 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.