# Time-Constrained Learning

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 31 references that are in the map.
- First posted on arXiv 4 Feb 2022.

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

- [An Overview of Machine Teaching](https://mlsanity.com/paper/1801.05927/) (2018)
- [A Benchmark and Comparison of Active Learning for Logistic Regression](https://mlsanity.com/paper/1611.08618/) (2016)
- [Near-Optimally Teaching the Crowd to Classify](https://mlsanity.com/paper/1402.2092/) (2014)
- [Towards Black-box Iterative Machine Teaching](https://mlsanity.com/paper/1710.07742/) (2017)
- [Understanding the Role of Adaptivity in Machine Teaching: The Case of Version Space Learners](https://mlsanity.com/paper/1802.05190/) (2018)
- [Feature Statistics Guided Efficient Filter Pruning](https://mlsanity.com/paper/2005.12193/) (2020)
- [Teacher Improves Learning by Selecting a Training Subset](https://mlsanity.com/paper/1802.08946/) (2018)
- [A novel active learning framework for classification: using weighted rank aggregation to achieve multiple query criteria](https://mlsanity.com/paper/1809.10565/) (2018)
- [Faster SVM Training via Conjugate SMO](https://mlsanity.com/paper/2003.08719/) (2020)
- [Stochastic batch size for adaptive regularization in deep network optimization](https://mlsanity.com/paper/2004.06341/) (2020)

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

- [Accelerating Deep Learning with Fixed Time Budget](https://mlsanity.com/paper/2410.03790/) (2024)

## Abstract (arXiv)

Consider a scenario in which we have a huge labeled dataset cal D and a limited time to train some given learner using cal D. Since we may not be able to use the whole dataset, how should we proceed? Questions of this nature motivate the definition of the Time-Constrained Learning Task (TCL): Given a dataset cal D sampled from an unknown distribution μ, a learner cal L and a time limit T, the goal is to obtain in at most T units of time the classification model with highest possible accuracy w.r.t. to μ, among those that can be built by cal L using the dataset cal D. We propose TCT, an algorithm for the TCL task designed based that on principles from Machine Teaching. We present an experimental study involving 5 different Learners and 20 datasets where we show that TCT consistently outperforms two other algorithms: the first is a Teacher for black-box learners proposed in [Dasgupta et al., ICML 19] and the second is a natural adaptation of random sampling for the TCL setting. We also compare TCT with Stochastic Gradient Descent training -- our method is again consistently better. While our work is primarily practical, we also show that a stripped-down version of TCT has provable guarantees. Under reasonable assumptions, the time our algorithm takes to achieve a certain accuracy is never much bigger than the time it takes the batch teacher (which sends a single batch of examples) to achieve similar accuracy, and in some case it is almost exponentially better.