# Exponential Weights Algorithms for Selective Learning

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 30 references that are in the map.
- First posted on arXiv 29 Jun 2021.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Agnostic Estimation of Mean and Covariance](https://mlsanity.com/paper/1604.06968/) (2016)
- [Learning from Untrusted Data](https://mlsanity.com/paper/1611.02315/) (2016)
- [Online Learning with Switching Costs and Other Adaptive Adversaries](https://mlsanity.com/paper/1302.4387/) (2013)
- [Distribution-Independent PAC Learning of Halfspaces with Massart Noise](https://mlsanity.com/paper/1906.10075/) (2019)
- [Robustly Learning a Gaussian: Getting Optimal Error, Efficiently](https://mlsanity.com/paper/1704.03866/) (2017)
- [Learning from weakly dependent data under Dobrushin's condition](https://mlsanity.com/paper/1906.09247/) (2019)
- [Composite convex minimization involving self-concordant-like cost functions](https://mlsanity.com/paper/1502.01068/) (2015)
- [A Theory of Selective Prediction](https://mlsanity.com/paper/1902.04256/) (2019)

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

- [Online Learning with Bounded Recall](https://mlsanity.com/paper/2205.14519/) (2022)
- [Online Prediction with Limited Selectivity](https://mlsanity.com/paper/2508.09592/) (2025)

## Abstract (arXiv)

We study the selective learning problem introduced by Qiao and Valiant (2019), in which the learner observes n labeled data points one at a time. At a time of its choosing, the learner selects a window length w and a model hatℓ from the model class L, and then labels the next w data points using hatℓ. The excess risk incurred by the learner is defined as the difference between the average loss of hatℓ over those w data points and the smallest possible average loss among all models in L over those w data points. We give an improved algorithm, termed the hybrid exponential weights algorithm, that achieves an expected excess risk of O((loglog|L| + loglog n)/log n). This result gives a doubly exponential improvement in the dependence on |L| over the best known bound of O(√|L|/log n). We complement the positive result with an almost matching lower bound, which suggests the worst-case optimality of the algorithm. We also study a more restrictive family of learning algorithms that are bounded-recall in the sense that when a prediction window of length w is chosen, the learner's decision only depends on the most recent w data points. We analyze an exponential weights variant of the ERM algorithm in Qiao and Valiant (2019). This new algorithm achieves an expected excess risk of O(√log |L|/log n), which is shown to be nearly optimal among all bounded-recall learners. Our analysis builds on a generalized version of the selective mean prediction problem in Drucker (2013); Qiao and Valiant (2019), which may be of independent interest.