# Optimal learning with Bernstein Online Aggregation

arXiv: https://arxiv.org/abs/1404.1356 · HTML: https://mlsanity.com/paper/1404.1356/

## Key facts

- Cited by 35 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Apr 2014.

## Built on by (most cited first, 30 of 35)

- [Adaptive Conformal Predictions for Time Series](https://mlsanity.com/paper/2202.07282/) (2022)
- [Conformal Inference for Online Prediction with Arbitrary Distribution Shifts](https://mlsanity.com/paper/2208.08401/) (2022)
- [Impossible Tuning Made Possible: A New Expert Algorithm and Its Applications](https://mlsanity.com/paper/2102.01046/) (2021)
- [CRPS Learning](https://mlsanity.com/paper/2102.00968/) (2021)
- [Sequential Domain Adaptation by Synthesizing Distributionally Robust Experts](https://mlsanity.com/paper/2106.00322/) (2021)
- [Scale-free Unconstrained Online Learning for Curved Losses](https://mlsanity.com/paper/2202.05630/) (2022)
- [Split-kl and PAC-Bayes-split-kl Inequalities for Ternary Random Variables](https://mlsanity.com/paper/2206.00706/) (2022)
- [High-Probability Risk Bounds via Sequential Predictors](https://mlsanity.com/paper/2308.07588/) (2023)
- [Exponential Tail Local Rademacher Complexity Risk Bounds Without the Bernstein Condition](https://mlsanity.com/paper/2202.11461/) (2022)
- [Adaptive Probabilistic Forecasting of Electricity (Net-)Load](https://mlsanity.com/paper/2301.10090/) (2023)
- [Stochastic Online Convex Optimization. Application to probabilistic time series forecasting](https://mlsanity.com/paper/2102.00729/) (2021)
- [A Regret-Variance Trade-Off in Online Learning](https://mlsanity.com/paper/2206.02656/) (2022)
- [Smoothed Bernstein Online Aggregation for Day-Ahead Electricity Demand Forecasting](https://mlsanity.com/paper/2107.06268/) (2021)
- [Isotuning With Applications To Scale-Free Online Learning](https://mlsanity.com/paper/2112.14586/) (2021)
- [Multivariate Probabilistic CRPS Learning with an Application to Day-Ahead Electricity Prices](https://mlsanity.com/paper/2303.10019/) (2023)
- [Low-Regret Active learning](https://mlsanity.com/paper/2104.02822/) (2021)
- [Expert Aggregation for Financial Forecasting](https://mlsanity.com/paper/2111.15365/) (2021)
- [Local Risk Bounds for Statistical Aggregation](https://mlsanity.com/paper/2306.17151/) (2023)
- [Sparse Deep Learning for Time Series Data: Theory and Applications](https://mlsanity.com/paper/2310.03243/) (2023)
- [Constant regret for sequence prediction with limited advice](https://mlsanity.com/paper/2210.02256/) (2022)
- [When Lower-Order Terms Dominate: Adaptive Expert Algorithms for Heavy-Tailed Losses](https://mlsanity.com/paper/2506.01722/) (2025)
- [Multivariate Online Linear Regression for Hierarchical Forecasting](https://mlsanity.com/paper/2402.14578/) (2024)
- [Minimax-optimal and Locally-adaptive Online Nonparametric Regression](https://mlsanity.com/paper/2410.03363/) (2024)
- [Random feature-based double Vovk-Azoury-Warmuth algorithm for online multi-kernel learning](https://mlsanity.com/paper/2503.20087/) (2025)
- [Minimax Adaptive Online Nonparametric Regression over Besov Spaces](https://mlsanity.com/paper/2505.19741/) (2025)
- [Online conformal inference with retrospective adjustment for faster adaptation to distribution shift](https://mlsanity.com/paper/2511.04275/) (2025)
- [Electricity Price Forecasting: Bridging Linear Models, Neural Networks and Online Learning](https://mlsanity.com/paper/2601.02856/) (2026)
- [Online (Non-)Convex Learning via Tempered Optimism](https://mlsanity.com/paper/2301.07530/) (2023)
- [An adaptive standardisation methodology for Day-Ahead electricity price forecasting](https://mlsanity.com/paper/2311.02610/) (2023)
- [Enhancing reliability in prediction intervals using point forecasters: Heteroscedastic Quantile Regression and Width-Adaptive Conformal Inference](https://mlsanity.com/paper/2406.14904/) (2024)

## Abstract (arXiv)

We introduce a new recursive aggregation procedure called Bernstein Online Aggregation (BOA). The exponential weights include an accuracy term and a second order term that is a proxy of the quadratic variation as in Hazan and Kale (2010). This second term stabilizes the procedure that is optimal in different senses. We first obtain optimal regret bounds in the deterministic context. Then, an adaptive version is the first exponential weights algorithm that exhibits a second order bound with excess losses that appears first in Gaillard et al. (2014). The second order bounds in the deterministic context are extended to a general stochastic context using the cumulative predictive risk. Such conversion provides the main result of the paper, an inequality of a novel type comparing the procedure with any deterministic aggregation procedure for an integrated criteria. Then we obtain an observable estimate of the excess of risk of the BOA procedure. To assert the optimality, we consider finally the iid case for strongly convex and Lipschitz continuous losses and we prove that the optimal rate of aggregation of Tsybakov (2003) is achieved. The batch version of the BOA procedure is then the first adaptive explicit algorithm that satisfies an optimal oracle inequality with high probability.