Research map / Bandits and online learning / Online convex optimization and games
When Lower-Order Terms Dominate: Adaptive Expert Algorithms for Heavy-Tailed Losses
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that loss-range-adaptive expert algorithms have lower-order terms (max loss) that can dominate regret under heavy-tailed losses, and proposes OMD/FTRL algorithms with multi-scale entropic regularizers and coordinate-wise clipping that achieve sqrt(theta T log K) worst-case and theta log(KT)/Delta_min self-bounded regret.
Problem
Prediction with expert advice when losses are heavy-tailed (only second moments bounded by theta, unknown), where existing loss-range-adaptive algorithms have regret dominated by a max-loss lower-order term that can scale as sqrt(KT).
Approach
Coordinate-wise clipping of instantaneous regrets combined with a multi-scale entropic regularizer and per-expert adaptive learning rates (OMD and FTRL variants, with rescaling in FTRL) removes the dependence on the maximum loss, yielding regret that depends only on second-moment (variance) quantities.
Key results
- Proves the max-loss lower-order term can scale as Omega(sqrt(KT)) even with theta=O(1), so existing loss-range-adaptive bounds can be dominated by it.
- LoOT-Free OMD/FTRL achieve O(sqrt(theta T log(KT))) worst-case regret and O(theta log(KT)/Delta_min) in self-bounded / i.i.d. settings, without knowing theta or loss range.
- For squared loss, the algorithm achieves O((Y^2+sigma) log(KT)) regret, avoiding an O(T) term for heavy-tailed outcomes.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace prior range-dependent guarantees with LoOT-Free OMD | Hedge algorithms · Hedge, finite second moments | worst-case regret: \mathcal{O}\bigl(\sqrt{\theta T \log(K)} + \sqrt{KT}\bigr) -> \mathcal{O}\bigl(\sqrt{\theta T \log(K)}\bigr) | Helped |
| Replace the maximum-loss term with the LoOT-Free FTRL guarantee | Hedge algorithms · Hedge, self-bounded environment with C = 0 | regret: \theta \log(K)\Delta_{\min}^{-1} + M_T -> \theta \log(KT)\Delta_{\min}^{-1} | Helped |
| Use LoOT-Free for squared loss instead of a range-dependent exponential-weights bound | Squared-loss prediction · Squared loss | regret: \mathcal{O}(T) -> \mathcal{O}\sprt{(Y^2 + \sigma) \log(KT)} | Helped |
| Include a maximum-loss term in the regret guarantee | Prior loss-range adaptive algorithms · Hedge, finite second moments | regret bound: L_T \ge \frac12 \sqrt{KT} | Hurt |
| Include a maximum-instantaneous-regret term in the regret guarantee | Prior loss-range adaptive algorithms · Hedge, finite second moments | regret bound: B_T^\star + M_T \ge B_T^\star + \frac1{16} \sqrt{KT} - 1 | Hurt |
Surprising findings
- Lower-order max-loss terms in existing loss-range-adaptive regret bounds can be as large as sqrt(KT) even when the second moment is constant.
- Existing EW-based adaptive algorithms are argued to have an unavoidable L_T-proportional regret term, not just an analysis artifact.
Limitations
- Log(T) factor in the FTRL/OMD bounds may not be necessary but is not removed.
- FTRL variant's extra (1/K) sum sqrt(V_T(i)) term is prohibitive for the improved self-bounded bound and only controlled in expectation.
- Extension to strongly convex and exp-concave losses left for future work.
Experimental setup
Metrics: pseudo-regret worst-case regret bound self-bounded regret bound
Baselines: exponential weights with doubling trick Squint loss-range adaptive version Hedge-based adaptive algorithms with clipping (Cesa-Bianchi-style) regret matching regret matching+
Builds on: multi-scale entropic regularizer Squint exponential weights with doubling trick self-bounded learning
Closest papers by meaning
- Online Learning with Primary and Secondary Losses (NeurIPS 2020 · similarity 0.89)
- Prediction with expert advice under additive noise (NeurIPS 2025 · similarity 0.88)
- A second order regret bound for NormalHedge (NeurIPS 2026 · similarity 0.88)
- From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model (NeurIPS 2026 · similarity 0.87)
- Small-loss Adaptive Regret for Online Convex Optimization (ICML 2024 · similarity 0.86)
- Tracking The Best Expert Privately (ICML 2025 · similarity 0.86)
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.