List and Certificate Complexities in Replicable Learning
This work addresses the challenge of ensuring reproducibility in machine learning for researchers and practitioners, though it appears incremental as it builds on existing replicability concepts.
The paper tackles the problem of designing replicable learning algorithms that output consistent models across runs with different data samples, by introducing and analyzing two feasible notions of replicability (list and certificate replicability) and providing optimal algorithms with matching impossibility results.
We investigate replicable learning algorithms. Ideally, we would like to design algorithms that output the same canonical model over multiple runs, even when different runs observe a different set of samples from the unknown data distribution. In general, such a strong notion of replicability is not achievable. Thus we consider two feasible notions of replicability called list replicability and certificate replicability. Intuitively, these notions capture the degree of (non) replicability. We design algorithms for certain learning problems that are optimal in list and certificate complexity. We establish matching impossibility results.