Research map / Bandits and online learning / Online convex optimization and games
Efficient online learning with kernels for adversarial large scale problems
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 |
|---|---|---|---|
| Replace full kernel computation with a fixed Taylor basis for the Gaussian kernel | PKAWV · Gaussian kernel | regret: $(\log n)^{2d+1} -> (\log n)^{d+1}$ | Helped |
| Replace full kernel computation with a fixed Taylor basis for the Gaussian kernel | PKAWV · Gaussian kernel | per-round complexity: $(n/c)^2 -> (\log n)^{2d}$ | Helped |
| Use sequential Nyström projections in place of the full kernel representation | PKAWV · General kernels under the stated capacity condition | regret: $n^{\frac{4\gamma}{(1+\gamma)^2}} \log n -> n^{\frac{\gamma}{\gamma+1}} \log n$ | Helped |
| Use a larger Nyström dictionary | PKAWV with KORS · General kernels under the capacity condition | regret: $nm^{\frac{1}{2}-\frac{1}{2\gamma}} -> n^{\frac{\gamma}{1+\gamma}}$ | Helped |
| Compute the full Nyström dictionary beforehand when inputs are known | PKAWV with Nyström projections · General kernels under the capacity condition | regret: $nm^{\frac{1}{2}-\frac{1}{2\gamma}} -> nm^{-\frac{1}{2\gamma}}$ | Helped |
| Use Taylor features with $M=2$ instead of the full-kernel forecaster | PKAWV · UCI datasets in the experiments | average loss | Mixed |
| Use Taylor features with $M=2$ on the first million SUSY examples | PKAWV · SUSY | average classification error | No clear effect |
Closest papers by meaning
- Kernel Learning with Adversarial Features: Numerical Efficiency and Adaptive Regularization (NeurIPS 2025 · similarity 0.90)
- Near-Optimal Regret in Adversarial Kernel Bandits (NeurIPS 2026 · similarity 0.89)
- High-Dimensional Prediction for Sequential Decision Making (ICML 2025 · similarity 0.88)
- From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model (NeurIPS 2026 · similarity 0.88)
- Discounted Adaptive Online Learning: Towards Better Regularization (ICML 2024 · similarity 0.87)
- A Simple and Optimal Approach for Universal Online Learning with Gradient Variations (NeurIPS 2024 · similarity 0.87)
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.