# Selecting Near-Optimal Learners via Incremental Data Allocation

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Dec 2015.

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

- [Learning Curves for Decision Making in Supervised Machine Learning: A Survey](https://mlsanity.com/paper/2201.12150/) (2022)
- [AutoPDL: Automatic Prompt Optimization for LLM Agents](https://mlsanity.com/paper/2504.04365/) (2025)
- [How Much Automation Does a Data Scientist Want?](https://mlsanity.com/paper/2101.03970/) (2021)
- [AutoAI-TS: AutoAI for Time Series Forecasting](https://mlsanity.com/paper/2102.12347/) (2021)
- [Fast and Informative Model Selection using Learning Curve Cross-Validation](https://mlsanity.com/paper/2111.13914/) (2021)
- [FLoRA: Single-shot Hyper-parameter Optimization for Federated Learning](https://mlsanity.com/paper/2112.08524/) (2021)
- [Scalable One-Pass Optimisation of High-Dimensional Weight-Update Hyperparameters by Implicit Differentiation](https://mlsanity.com/paper/2110.10461/) (2021)
- [ChaCha for Online AutoML](https://mlsanity.com/paper/2106.04815/) (2021)
- [EvoOtter: Evolutionary Reproduction Test Generator](https://mlsanity.com/paper/2607.02854/) (2026)
- [A Survey on Semantics in Automated Data Science](https://mlsanity.com/paper/2205.08018/) (2022)
- [Toward Theoretical Guidance for Two Common Questions in Practical Cross-Validation based Hyperparameter Selection](https://mlsanity.com/paper/2301.05131/) (2023)
- [The Challenger: When Do New Data Sources Justify Switching Machine Learning Models?](https://mlsanity.com/paper/2512.18390/) (2025)

## Abstract (arXiv)

We study a novel machine learning (ML) problem setting of sequentially allocating small subsets of training data amongst a large set of classifiers. The goal is to select a classifier that will give near-optimal accuracy when trained on all data, while also minimizing the cost of misallocated samples. This is motivated by large modern datasets and ML toolkits with many combinations of learning algorithms and hyper-parameters. Inspired by the principle of "optimism under uncertainty," we propose an innovative strategy, Data Allocation using Upper Bounds (DAUB), which robustly achieves these objectives across a variety of real-world datasets. We further develop substantial theoretical support for DAUB in an idealized setting where the expected accuracy of a classifier trained on n samples can be known exactly. Under these conditions we establish a rigorous sub-linear bound on the regret of the approach (in terms of misallocated data), as well as a rigorous bound on suboptimality of the selected classifier. Our accuracy estimates using real-world datasets only entail mild violations of the theoretical scenario, suggesting that the practical behavior of DAUB is likely to approach the idealized behavior.