# Fast rates for prediction with limited expert advice

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 28 references that are in the map.
- First posted on arXiv 27 Oct 2021.

## Builds on (most cited first, 5 of 5)

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback](https://mlsanity.com/paper/1507.08752/) (2015)
- [Refined Lower Bounds for Adversarial Bandits](https://mlsanity.com/paper/1605.07416/) (2016)
- [Budget-Constrained Multi-Armed Bandits with Multiple Plays](https://mlsanity.com/paper/1711.05928/) (2017)
- [Adaptation to Easy Data in Prediction with Limited Advice](https://mlsanity.com/paper/1807.00636/) (2018)

## Built on by (most cited first, 4 of 4)

- [A Regret-Variance Trade-Off in Online Learning](https://mlsanity.com/paper/2206.02656/) (2022)
- [Constant regret for sequence prediction with limited advice](https://mlsanity.com/paper/2210.02256/) (2022)
- [Group Distributionally Robust Optimization with Flexible Sample Queries](https://mlsanity.com/paper/2505.15212/) (2025)
- [Covariance Adaptive Best Arm Identification](https://mlsanity.com/paper/2306.02630/) (2023)

## Abstract (arXiv)

We investigate the problem of minimizing the excess generalization error with respect to the best expert prediction in a finite family in the stochastic setting, under limited access to information. We assume that the learner only has access to a limited number of expert advices per training round, as well as for prediction. Assuming that the loss function is Lipschitz and strongly convex, we show that if we are allowed to see the advice of only one expert per round for T rounds in the training phase, or to use the advice of only one expert for prediction in the test phase, the worst-case excess risk is Omega(1/ √ T) with probability lower bounded by a constant. However, if we are allowed to see at least two actively chosen expert advices per training round and use at least two experts for prediction, the fast rate O(1/T) can be achieved. We design novel algorithms achieving this rate in this setting, and in the setting where the learner has a budget constraint on the total number of observed expert advices, and give precise instance-dependent bounds on the number of training rounds and queries needed to achieve a given generalization error precision.