Research map / Bandits and online learning / Online convex optimization and games
Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach
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 a multi-layer ensemble with universal optimism and cascaded corrections | Online convex optimization · Convex losses with gradient variation | regret bound: from \(\O(\sqrt{T})\) to \(\Oh(\sqrt{V_T})\) | Helped |
| Use the proposed universal ensemble | Online convex optimization · Strongly convex losses | regret bound: \(\O(\log V_T)\) | Helped |
| Use the proposed universal ensemble | Online convex optimization · Exp-concave losses | regret bound: \(\O(d \log V_T)\) | Helped |
| Use the proposed universal ensemble | Online convex optimization · Nonnegative losses | small-loss regret bound: \(\O(\log F_T)\), \(\O(d \log F_T)\), and \(\Oh(\sqrt{F_T})\) | Helped |
| Use the proposed algorithm in place of separate parameter setups | SEA online learning · Strongly convex, exp-concave, and convex losses | expected regret bound: \(\O((\sigma_{\max}^2 + \Sigma_{\max}^2) \log (\sigma_{1:T}^2 + \Sigma_{1:T}^2))\); \(\O(d \log (\sigma_{1: T}^2 + \Sigm | Helped |
| Use the proposed algorithm without knowing the game type | Two-player zero-sum games · Honest players | regret summation bound: \(\O(1)\) | Helped |
| Use the proposed algorithm | Two-player zero-sum games · Dishonest players, strongly convex-concave games | individual regret bound: \(\O(\log T)\) | Helped |
| Replace original-loss updates with carefully designed surrogate-loss updates | Ours · Strongly convex, exp-concave, and convex losses | gradient queries per round: \(\O(\log^2 T)\) -> 1 | Helped |
| Use universal optimism \(m_{t,i}=r_{t-1,i}\) instead of the previous-gradient-at-current-decision optimism | Online ensemble meta-regret · Exp-concave losses | second-order regret term: \(\sum_t (r_{t,\is}-m_{t,\is})^2 \lesssim \sum_t \langle\nabla f_t(\x_t),\x_t-\x_{t,\is}\rangle^2\) | Helped |
| Add negative stability terms to the MsMwC analysis | Multi-layer meta learner · Online ensemble stability | stability contribution to regret: \(-4 \sum_{t=2}^T \|\p_t-\p_{t-1}\|_1^2\) | Helped |
| Add cascaded correction terms to the top and middle layers | Multi-layer online ensemble · Convex losses with gradient variation | stability contribution to regret | Helped |
Closest papers by meaning
- A Simple and Optimal Approach for Universal Online Learning with Gradient Variations (NeurIPS 2024 · similarity 0.96)
- Gradient-Variation Online Learning under Generalized Smoothness (NeurIPS 2024 · similarity 0.92)
- Optimal Algorithms for Online Convex Optimization with Adversarial Constraints (NeurIPS 2024 · similarity 0.91)
- Revisiting Projection-Free Online Learning with Time-Varying Constraints (AAAI 2025 · similarity 0.91)
- Universal Online Convex Optimization with $1$ Projection per Round (NeurIPS 2024 · similarity 0.90)
- Gradient-Variation Online Adaptivity for Accelerated Optimization with Hölder Smoothness (NeurIPS 2025 · similarity 0.90)
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.