Reproducibility in learning
From MaRDI portal
Abstract: We introduce the notion of a reproducible algorithm in the context of learning. A reproducible learning algorithm is resilient to variations in its samples -- with high probability, it returns the exact same output when run on two samples from the same underlying distribution. We begin by unpacking the definition, clarifying how randomness is instrumental in balancing accuracy and reproducibility. We initiate a theory of reproducible algorithms, showing how reproducibility implies desirable properties such as data reuse and efficient testability. Despite the exceedingly strong demand of reproducibility, there are efficient reproducible algorithms for several fundamental problems in statistics and learning. First, we show that any statistical query algorithm can be made reproducible with a modest increase in sample complexity, and we use this to construct reproducible algorithms for finding approximate heavy-hitters and medians. Using these ideas, we give the first reproducible algorithm for learning halfspaces via a reproducible weak learner and a reproducible boosting algorithm. Finally, we initiate the study of lower bounds and inherent tradeoffs for reproducible algorithms, giving nearly tight sample complexity upper and lower bounds for reproducible versus nonreproducible SQ algorithms.
Cited in
(5)- Certifying private probabilistic mechanisms
- Replicable bandits for digital health interventions
- An empirical scrutinization of four crisp clustering methods with four distance metrics and one straightforward interpretation rule
- From tcs to learning theory (invited paper)
- Local computation algorithms for knapsack: impossibility results, and how to avoid them
This page was built for publication: Reproducibility in learning
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6083537)
