Research map / Bandits and online learning / Online convex optimization and games
Online Learning with Primary and Secondary Losses
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 |
|---|---|---|---|
| Assume each expert's secondary loss stays within δT^α of the threshold on every interval | Adversarial online learning with primary and secondary losses · Good scenario | max(regret to best, regret to cT): O(T^{\frac{1+\alpha}{2}}) | Helped |
| Remove the bounded-variance assumption on secondary losses | Any online learning algorithm · Adversarial online learning | max(regret to best, regret to cT): \Omega(T) | Hurt |
| Limit expert switches by playing one expert per epoch | A_SL(ℒ) · Good scenario | max(regret to best, regret to cT): O(T^{\frac{1+\alpha}{2}}) | Helped |
| Use the relaxed assumption that bounds secondary loss between an algorithm's switches | Switching-limited algorithms · Relaxed good scenario | max(regret to best, regret to cT): O(T^{\frac{1+\alpha}{2}}); \Omega(T^{\frac{1+\alpha}{2}}) | Mixed |
| Deactivate experts when their secondary loss violates the interval constraint, using pseudo losses and active-expert mapping | A1 · Bad scenario with permanent deactivation oracle | sleeping regret for primary loss: O(\sqrt{\log(K)T_{h^*}T^\alpha}) | Helped |
| Combine activation-schedule meta experts with switching-limited expert selection | A2 · Bad scenario with fixed-time reactivation oracle | sleeping regret for primary loss: O(\sqrt{\log(K)T^{1+\alpha}} +T_{h^*}\sqrt{\log(K)T^{\alpha-1}}) | Helped |
| Require sublinear sleeping regret for every expert under permanent deactivation | Any algorithm · Bad scenario | regret to cT: \Omega(KT^\alpha) | Hurt |
| Make decisions depend only on cumulative expert losses | Any algorithm under Assumption 2 · Good scenario | max(regret to best, regret to cT): \Omega(T^\frac{1+\alpha}{2}) | Hurt |
Closest papers by meaning
- When Lower-Order Terms Dominate: Adaptive Expert Algorithms for Heavy-Tailed Losses (NeurIPS 2025 · similarity 0.89)
- A Regret-Variance Trade-Off in Online Learning (NeurIPS 2022 · similarity 0.89)
- Dying Experts: Efficient Algorithms with Optimal Regret Bounds (NeurIPS 2019 · similarity 0.86)
- From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model (NeurIPS 2026 · similarity 0.86)
- Avoiding Catastrophe in Online Learning by Asking for Help (ICML 2025 · similarity 0.86)
- Improved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality (NeurIPS 2025 · 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.