Research map / Learning theory and algorithms / Matrix and tensor methods
Exploiting Numerical Sparsity for Efficient Learning : Faster Eigenvector Computation and Regression
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 numerical-sparsity-aware coordinate sampling with SVRG and shift-and-invert | Top eigenvector computation · Top eigenvector computation | running time: \tilde{O}\left(\mathrm{nnz}(\mat{A}) + \frac{1}{\mathrm{gap}^2\lambda_1}\sum_i \norm{a_i}_2^2\left(\sqrt{s_i} + \sqrt{\m | Helped |
| Apply approximate proximal point acceleration to the numerical-sparsity-aware method | Top eigenvector computation · Top eigenvector computation | running time: \tilde{O}\left(\mathrm{nnz}(\mat{A}) + \frac{\mathrm{nnz}(\mat{A})^{\frac{3}{4}}}{\sqrt{\mathrm{gap}}}\left({\sum_i \fra | Helped |
| Use numerical-sparsity-aware coordinate sampling with SVRG | Linear regression · Linear regression | running time: \tilde{O}\left(\mathrm{nnz}(\mat{A}) + \sqrt{\kappa}\sum_i \frac{\norm{a_i}^2_2}{\mu}\sqrt{s_i}\right) versus \tilde{O}\ | Helped |
| Apply approximate proximal point acceleration to the numerical-sparsity-aware method | Linear regression · Linear regression | running time: O\left(\left(\mathrm{nnz}(\mat{A}) + \mathrm{nnz}(\mat{A})^{\frac{2}{3}}{\kappa}^{\frac{1}{6}}{\left(\sum_{i \in [n]} \f | Helped |
| Rely on numerical sparsity rather than only row nonzero-count sparsity | Regression and top eigenvector computation · Numerically sparse matrices | running time: For top eigenvector computation, \tilde{O}(\mathrm{nnz}(\mat{A}) + (\mathrm{sr}(\mat{A})/\mathrm{gap}^2)\sqrt{\mathrm{sr | Helped |
Closest papers by meaning
- Principal Component Hierarchy for Sparse Quadratic Programs (ICML 2021 · similarity 0.89)
- Faster Eigenvector Computation via Shift-and-Invert Preconditioning (ICML 2016 · similarity 0.89)
- Efficient Algorithms for Large-scale Generalized Eigenvector Computation and Canonical Correlation Analysis (ICML 2016 · similarity 0.88)
- Provable Acceleration of Nesterov's Accelerated Gradient for Asymmetric Matrix Factorization and Linear Neural Networks (NeurIPS 2024 · similarity 0.88)
- Block Acceleration Without Momentum: On Optimal Stepsizes of Block Gradient Descent for Least-Squares (ICML 2024 · similarity 0.86)
- Learning to Discover Iterative Spectral Algorithms (NeurIPS 2026 · 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.