Research map / Learning theory and algorithms / Matrix and tensor methods
Adaptive Sketching for Fast and Convergent Canonical Polyadic Decomposition
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 |
|---|---|---|---|
| adaptive sketching rate selection via multiplicative weights (CPD-MWU) instead of static sketching rate | proximally/Tikhonov regularized sketched CPD-ALS · Noisy synthetic tensor | runtime (s): 214.51 -> 185.67 s | Helped |
| adaptive sketching rate selection (CPD-MWU) vs static sketching | sketched CPD-ALS · Noisy synthetic tensor | residual error ε: 0.3808 vs 0.3808 | No clear effect |
| adaptive sketching rate selection (CPD-MWU) vs static sketching | sketched CPD-ALS with proximal regularization · Ill-conditioned synthetic tensor, 10-minute budget | residual error ε: 0.0149 -> 0.0030 | Helped |
| adaptive sketching rate selection (CPD-MWU) vs static sketching | sketched CPD-ALS · Park bench video, rank 250 | runtime (s): 527.98 -> 465.83 s | Helped |
| adaptive sketching rate selection (CPD-MWU) vs static sketching | sketched CPD-ALS · NELL knowledge base, 30-minute limit | residual error ε: CPRAND-MIX 0.072 and SPALS 0.104 vs CPD-MWU+MIX 0.058 | Helped |
| static sketching rates (CPRAND-MIX, SPALS) run for two hours instead of 30 minutes (ablation) | static sketched CPD-ALS baselines · NELL knowledge base | residual error ε: CPRAND-MIX 0.072 -> 0.066; SPALS 0.104 -> 0.098; neither reaches target 0.060 | No clear effect |
| adaptive sketching rate selection (CPD-MWU + MIX) vs CPD-ALS + MIX | CPD-ALS with pre-mixed tensor · NELL knowledge base, target error 0.060 | runtime (s): 1044.75 -> 354.55 s | Helped |
| number of candidate sketching rates N increased from 5/10 to 50-1000 (ablation) | CPD-MWU · Ill-conditioned synthetic tensor | residual error ε over time: N=5 and 10 perform similarly and significantly outperform larger N | Hurt |
| proximal regularization (λ) vs Tikhonov in sketched CPD-ALS | sketched CPD-ALS · Synthetic tensors | convergence | No clear effect |
Closest papers by meaning
- Fast and accurate randomized algorithms for low-rank tensor decompositions (NeurIPS 2021 · similarity 0.88)
- Near Optimal Sketching of Low-Rank Tensor Regression (NeurIPS 2017 · similarity 0.88)
- Tensor-Based Sketching Method for the Low-Rank Approximation of Data Streams. (ICLR 2023 · similarity 0.87)
- More Efficient Sampling for Tensor Decomposition With Worst-Case Guarantees (ICML 2022 · similarity 0.87)
- Fast Sampling-Based Sketches for Tensors (ICML 2024 · similarity 0.87)
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms (ICLR 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.