Research map / Learning theory and algorithms / Kernels and regression theory
Optimal Convergence Rates for Agnostic Nyström Kernel Learning
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 |
|---|---|---|---|
| Nyström uniform sampling with landmark count M ≳ n^{1/(2r+γ)} under condition 2r+γ ≥ 1 | KRR-Nyström (uniform sampling) · agnostic setting (r in (0,1]) | excess risk rate O(n^{-2r/(2r+γ)}) | Helped |
| Nyström leverage-score (data-dependent) sampling with landmark count M ≳ n^{γ/(2r+γ)} | KRR-Nyström (leverage scores sampling) · whole agnostic range r in (0,1] | excess risk rate O(n^{-2r/(2r+γ)}) | Helped |
| Sample variance estimate using Bennett's inequality (N∞(λ) based bound instead of 1/(n√λ) bound) | KRR-Nyström analysis · theoretical analysis | sample variance bound | Helped |
| Data-dependent leverage-score sampling adds computation cost of O(N(λ)^2/λ) for sampling | KRR-Nyström with leverage scores · agnostic setting r in (0,1) | time complexity | Hurt |
Closest papers by meaning
- Recursive Sampling for the Nystrom Method (NeurIPS 2017 · similarity 0.90)
- Sampling-based Nyström Approximation and Kernel Quadrature (ICML 2023 · similarity 0.90)
- Improved Convergence Rates for Sparse Approximation Methods in Kernel-Based Learning (ICML 2022 · similarity 0.89)
- Generalization Bound of Gradient Flow through Training Trajectory and Data-dependent Kernel (NeurIPS 2025 · similarity 0.85)
- Generalization in Kernel Regression Under Realistic Assumptions (ICML 2024 · similarity 0.85)
- Kernel-based guarantees for nonlinear parametric models in Bayesian optimization (NeurIPS 2026 · 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.