Research map / Bandits and online learning / Online convex optimization and games
Tracking Slowly Moving Clairvoyant: Optimal Dynamic Regret of Online Learning with True and Noisy Gradient
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 |
|---|---|---|---|
| Use path variation to constrain how quickly the clairvoyant minimizers move | Online convex optimization with full information · Lipschitz losses | dynamic regret upper bound: O(V^p_T) | Helped |
| Use constant-step-size OGD under smoothness and vanishing-gradient conditions | Online convex optimization with true gradients · Smooth losses with vanishing gradients | dynamic regret upper bound: O(V^p_T) | Helped |
| Use OGD with bounded stochastic gradient feedback | Online convex optimization · Lipschitz losses | dynamic regret upper bound: O(√(V^p_TT)) | Helped |
| Use two-point rather than one-point bandit feedback | Online convex optimization · Lipschitz losses | dynamic regret upper bound: O(√(V^p_TT)) | Helped |
| Leverage gradient variation in the smooth-loss bandit method | META with two-point bandit feedback · Smooth losses | dynamic regret upper bound: O(max{√(V^p_TV^g_T), V^p_T}) | Helped |
| Allow path variation budget B_T to be at least C_1T | Any online policy · Unconstrained-rate dynamic regret | dynamic regret lower bound: C_2T | Hurt |
| Use noisy gradient feedback rather than noiseless feedback | Online convex optimization · Path variation budget B_T | dynamic regret lower bound: C(κ)B_T^κ T^(1 - κ) | Hurt |
Closest papers by meaning
- Parameter-free Dynamic Regret: Time-varying Movement Costs, Delayed Feedback, and Memory (ICML 2026 · similarity 0.92)
- Capacity-Constrained Online Convex Optimization with Delayed Feedback (NeurIPS 2026 · similarity 0.90)
- Dynamic Regret Reduces to Kernelized Static Regret (NeurIPS 2025 · similarity 0.90)
- A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees (NeurIPS 2026 · similarity 0.89)
- Dynamic Regret in Online Convex Optimization with Indicator Switching Costs (NeurIPS 2026 · similarity 0.89)
- An Equivalence Between Static and Dynamic Regret Minimization (NeurIPS 2024 · similarity 0.89)
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.