mlsanityData to 7 Oct 2026

A Second-order Bound with Excess Losses

arXiv 1402.2044 ↗First posted 10 Feb 2014stat.ML cs.LG math.STcited by 91

Not on the map. Why?

Abstract (arXiv)

We study online aggregation of the predictions of experts, and first show new second-order regret bounds in the standard setting, which are obtained via a version of the Prod algorithm (and also a version of the polynomially weighted average algorithm) with multiple learning rates. These bounds are in terms of excess losses, the differences between the instantaneous losses suffered by the algorithm and the ones of a given expert. We then demonstrate the interest of these bounds in the context of experts that report their confidences as a number in the interval [0,1] using a generic reduction to the standard setting. We conclude by two other applications in the standard setting, which improve the known bounds in case of small excess losses and show a bounded regret against i.i.d. sequences of losses.

Key facts. Cited by 91 papers in the map (data through 7 Oct 2026). First posted on arXiv 10 Feb 2014.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2019: 1; 2020: 0; 2021: 19; 2022: 14; 2023: 14; 2024: 16; 2025: 11; 2026: 16.

91 papers.

Sort:

By area:

  1. 2022Adaptive Conformal Predictions for Time Seriescited by 155
  2. 2021Impossible Tuning Made Possible: A New Expert Algorithm and Its Applicationscited by 52
  3. 2023A Blackbox Approach to Best of Both Worlds in Bandits and Beyondcited by 29
  4. 2023A Unifying Perspective on Multi-Calibration: Game Dynamics for Multi-Objective Learningcited by 29
  5. 2021MetaGrad: Adaptation using Multiple Learning Rates in Online Learningcited by 26
  6. 2021Simple and near-optimal algorithms for hidden stratification and multi-group learningcited by 26
  7. 2022Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphscited by 26
  8. 2021CRPS Learningcited by 21
  9. 2021On Optimal Robustness to Adversarial Corruption in Online Decision Problemscited by 20
  10. 2022Best-of-Both-Worlds Algorithms for Partial Monitoringcited by 19
  11. 2022A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphscited by 17
  12. 2023Adapting to Continuous Covariate Shift via Online Density Ratio Estimationcited by 15
38 more
  1. 2023Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worldscited by 15
  2. 2023Efficient Methods for Non-stationary Online Learningcited by 15
  3. 2023Online-to-PAC Conversions: Generalization Bounds via Regret Analysiscited by 14
  4. 2021A closer look at temporal variability in dynamic online learningcited by 13
  5. 2022Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Boundscited by 12
  6. 2022Learning on the Edge: Online Learning with Stochastic Feedback Graphscited by 12
  7. 2021Online Strongly Convex Optimization with Unknown Delayscited by 11
  8. 2023Best-of-three-worlds Analysis for Linear Bandits with Follow-the-regularized-leader Algorithmcited by 11
  9. 2024Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Analysis and Best-of-Both-Worldscited by 11
  10. 2024Gradient-Variation Online Learning under Generalized Smoothnesscited by 11
  11. 2019Soft-Bayes: Prod for Mixtures of Experts with Log-Losscited by 10
  12. 2022Exploiting the Curvature of Feasible Sets for Faster Projection-Free Online Learningcited by 10
  13. 2021On the Last Iterate Convergence of Momentum Methodscited by 9
  14. 2022Damped Online Newton Step for Portfolio Selectioncited by 9
  15. 2023Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approachcited by 9
  16. 2021Minimax Optimal Quantile and Semi-Adversarial Regret via Root-Logarithmic Regularizerscited by 8
  17. 2024Group-wise oracle-efficient algorithms for online multi-group learningcited by 8
  18. 2022A Regret-Variance Trade-Off in Online Learningcited by 7
  19. 2022Adaptive Oracle-Efficient Online Learningcited by 7
  20. 2024uniINF: Best-of-Both-Worlds Algorithm for Parameter-Free Heavy-Tailed MABscited by 7
  21. 2025Revisiting Online Learning Approach to Inverse Linear Optimization: A Fenchel-Young Loss Perspective and Gap-Dependent Regret Analysiscited by 7
  22. 2025Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Boundcited by 7
  23. 2021Online Convex Optimization with Continuous Switching Constraintcited by 6
  24. 2024Universal Online Convex Optimization with 1 Projection per Roundcited by 6
  25. 2026Improved Dimension Dependence for Bandit Convex Optimization with Gradient Variationscited by 5
  26. 2021Universal Online Convex Optimization Meets Second-order Boundscited by 4
  27. 2021Adaptive first-order methods revisited: Convex optimization without Lipschitz requirementscited by 4
  28. 2021Hierarchical transfer learning with applications for electricity load forecastingcited by 4
  29. 2021Isotuning With Applications To Scale-Free Online Learningcited by 4
  30. 2022Online Learning with Off-Policy Feedbackcited by 4
  31. 2023Multivariate Probabilistic CRPS Learning with an Application to Day-Ahead Electricity Pricescited by 4
  32. 2025Generalized Kernelized Bandits: A Novel Self-Normalized Bernstein-Like Dimension-Free Inequality and Regret Boundscited by 4
  33. 2021Low-Regret Active learningcited by 3
  34. 2021Sequential Ski Rental Problemcited by 3
  35. 2021Online Aggregation of Probability Forecasts with Confidencecited by 3
  36. 2021Expert Aggregation for Financial Forecastingcited by 3
  37. 2022One Arrow, Two Kills: An Unified Framework for Achieving Optimal Regret Guarantees in Sleeping Banditscited by 3
  38. 2023Adaptive Selective Sampling for Online Prediction with Expertscited by 3

50 most cited of 91 All 91 (JSON)