# Budget Learning via Bracketing

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

## Key facts

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

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

- [Who Should Predict? Exact Algorithms For Learning to Defer to Humans](https://mlsanity.com/paper/2301.06197/) (2023)
- [Sample Efficient Learning of Predictors that Complement Humans](https://mlsanity.com/paper/2207.09584/) (2022)
- [Realizable H-Consistent and Bayes-Consistent Loss Functions for Learning to Defer](https://mlsanity.com/paper/2407.13732/) (2024)
- [Mastering Multiple-Expert Routing: Realizable H-Consistency and Strong Guarantees for Learning to Defer](https://mlsanity.com/paper/2506.20650/) (2025)
- [Budgeted Multiple-Expert Deferral](https://mlsanity.com/paper/2510.26706/) (2025)
- [Learning to Abstain From Uninformative Data](https://mlsanity.com/paper/2309.14240/) (2023)

## Abstract (arXiv)

Conventional machine learning applications in the mobile/IoT setting transmit data to a cloud-server for predictions. Due to cost considerations (power, latency, monetary), it is desirable to minimise device-to-server transmissions. The budget learning (BL) problem poses the learner's goal as minimising use of the cloud while suffering no discernible loss in accuracy, under the constraint that the methods employed be edge-implementable. We propose a new formulation for the BL problem via the concept of bracketings. Concretely, we propose to sandwich the cloud's prediction, g, via functions h^-, h^+ from a `simple' class so that h^- ≤ g ≤ h^+ nearly always. On an instance x, if h^+(x)=h^-(x), we leverage local processing, and bypass the cloud. We explore theoretical aspects of this formulation, providing PAC-style learnability definitions; associating the notion of budget learnability to approximability via brackets; and giving VC-theoretic analyses of their properties. We empirically validate our theory on real-world datasets, demonstrating improved performance over prior gating based methods.