Research map / Learning theory and algorithms / Matrix and tensor methods
Efficient Symmetric Norm Regression via Linear Sketching
Zhao Song, Ruosong Wang, Lin Yang, Hongyang Zhang, Peilin Zhong
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (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 prior Orlicz regression approach with the proposed algorithm | Orlicz norm regression · Orlicz norm regression | approximation ratio: d \cdot \polylog n -> 1+\varepsilon | Improved |
| Use the proposed symmetric norm sketching algorithm | Linear regression with a general symmetric norm · Symmetric norm regression | approximation ratio: \sqrt{d} \cdot \polylog n \cdot \mathrm{mmc}(\ell) | Improved |
| Use row sampling with Orlicz norm leverage scores instead of the prior random-projection approach | Orlicz norm regression · Orlicz norm regression | approximation ratio: d \cdot \polylog n -> 1+\varepsilon | Improved |
Closest papers by meaning
- Subspace Embedding and Linear Regression with Orlicz Norm (ICML 2018 · similarity 0.89)
- Sketching Algorithms and Lower Bounds for Ridge Regression (ICML 2022 · similarity 0.87)
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms (ICLR 2024 · similarity 0.87)
- A Nearly-Optimal Bound for Fast Regression with $\ell_\infty$ Guarantee (ICML 2023 · similarity 0.86)
- Towards Optimal Sobolev Norm Rates for the Vector-Valued Regularized Least-Squares Algorithm (JMLR 2024 · similarity 0.86)
- Robust Sparse Regression with Non-Isotropic Designs (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.
