Research map / Learning theory and algorithms / Kernels and regression theory
Divide-and-Conquer Learning with Nyström: Optimal Rate and Algorithm
Rong Yin, Yong Liu, Lijing Lu, Weiping Wang, Dan Meng
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 |
|---|---|---|---|
| add divide-and-conquer (p=2) to Nystrom-iterative | NY · covtype, m=2000 | training time (s): 5.62 -> 2.63 | Improved |
| add divide-and-conquer (p=2) to Nystrom-iterative | NY · SUSY, m=2000 | training time (s): 12.9 -> 6.40 | Improved |
| add divide-and-conquer (p=2) to Nystrom-iterative | NY · SUSY, m=2000 | test error: 0.195 -> 0.195 | No clear effect |
| add divide-and-conquer (p=2) to Nystrom-iterative | NY · HIGGS, m=2000 | test error: 0.321 -> 0.322 | No clear effect |
| use Nystrom instead of random features in divide-and-conquer (ablation) | DC-RF · covtype, m=2000 | test error: 0.234 -> 0.185 | Improved |
| use Nystrom instead of random features in divide-and-conquer (ablation) | DC-RF · SUSY, m=2000 | training time (s): 13.67 -> 6.40 | Improved |
| increase number of partitions p | DC-NY · four datasets | test error | Hurt |
| increase number of partitions p | DC-RF and DC-NY · four datasets | training time | Improved |
| increase conjugate gradient iterations t beyond 4 (ablation) | DC-NY · four datasets | test error | No clear effect |
| increase sampling scale m up to sqrt(N) (ablation) | DC-NY · four datasets | test error | Improved |
| increase sampling scale m (ablation) | DC-NY · four datasets | training time | Hurt |
Closest papers by meaning
- Distributed Nyström Kernel Learning with Communications (ICML 2021 · similarity 0.89)
- Preconditioning Kernel Matrices (ICML 2016 · similarity 0.87)
- Optimal Convergence Rates for Agnostic Nyström Kernel Learning (ICML 2023 · similarity 0.87)
- Fast and Accurate Refined Nyström-Based Kernel SVM (AAAI 2016 · similarity 0.87)
- Supervised Kernel Thinning (NeurIPS 2024 · similarity 0.86)
- Nyström-Accelerated Primal LS-SVMs: Breaking the $O(an^3)$ Complexity Bottleneck for Scalable ODEs Learning (NeurIPS 2025 · 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.
