Research map / Bandits and online learning / Online convex optimization and games
Incremental Randomized Sketching for Online 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 |
|---|---|---|---|
| incremental randomized sketching (IRS) instead of incremental Nystrom for kernel approximation | kernel matrix approximation · german and svmguide3, B=100/200 | relative error: e.g. 0.078 -> 0.059 (german B=100) | Helped |
| SkeGD vs. NOGD (Nystrom-based online kernel learning) with budget B=100/200 | online kernel learning · 8 LIBSVM benchmarks | mistake rate (%): e.g. 29.881 -> 27.932 (german); 34.332 -> 31.301 (spambase) | Helped |
| incremental randomized sketching with update cycle rho = 0.005T in adversarial environments | online kernel learning · german adversarial datasets | mistake rate (%): german-1: 30.918 (NOGD) -> 16.578; german-2: 26.737 (NOGD) -> 7.266 | Helped |
| smaller tau = sm/sp (sketch ratio 0.2 vs up to 0.8) (ablation) | SkeGD · cod-rna, B=200/300/400 | average mistake rate and running time: smaller tau yields lower mistake rate and running time | Helped |
| larger number of hash blocks d in the sparse transform sketch (ablation) | SkeGD · spambase, B=200/300/400 | average mistake rate: large d significantly improves accuracy with little sacrifice of time efficiency | Helped |
| larger budget B (ablation) | SkeGD · cod-rna | mistake rate and running time: higher budget lowers mistake rate but raises running time | Mixed |
| update cycle rho too large or too small in adversarial setting (ablation) | SkeGD · german adversarial | mistake rate (%): theta=0.005 best on german-1 (16.578) and german-2 (7.266); theta=0.001 costs more time (1.183/1.856 s) | Mixed |
Closest papers by meaning
- Distributed Randomized Sketching Kernel Learning (AAAI 2022 · similarity 0.89)
- Randomized Sketches for Clustering: Fast and Optimal Kernel $k$-Means (NeurIPS 2022 · similarity 0.86)
- Efficient Second Order Online Learning by Sketching (NeurIPS 2016 · similarity 0.86)
- Sketched Adaptive Distributed Deep Learning: A Sharp Convergence Analysis (NeurIPS 2025 · similarity 0.83)
- Sketching for Distributed Deep Learning: A Sharper Analysis (NeurIPS 2024 · similarity 0.83)
- SketchINR: A First Look into Sketches as Implicit Neural Representations (CVPR 2024 · similarity 0.83)
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.