mlsanityData to 7 Oct 2026

List and Certificate Complexities in Replicable Learning

arXiv 2304.02240 ↗First posted 5 Apr 2023cs.LG cs.DMcited by 13

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 13 papers in the map (data through 7 Oct 2026). Builds on 12 of its 41 references that are in the map. First posted on arXiv 5 Apr 2023.

Builds on

12 of 41 references.

References · 12

  1. 2020Improving Reproducibility in Machine Learning Research (A Report from the NeurIPS 2019 Reproducibility Program)cited by 318
  2. 2015Algorithmic Stability for Adaptive Data Analysiscited by 88
  3. 2018Private PAC learning implies finite Littlestone dimensioncited by 73
  4. 2020An Equivalence Between Private Classification and Online Predictioncited by 63
  5. 2022Reproducibility in Learningcited by 44
  6. 2019List Decodable Learning via Sum of Squarescited by 37
  7. 2022A Characterization of List Learnabilitycited by 22
  8. 2022Reproducibility in Optimization: Theoretical Framework and Limitscited by 21
  9. 2019ICLR Reproducibility Challenge Report (Padam : Closing The Generalization Gap Of Adaptive Gradient Methods in Training Deep Neural Networks)cited by 2
  10. 2019Pseudo-deterministic Streamingcited by 2
  11. 2016Pseudodeterministic Constructions in Subexponential Timecited by 1
  12. 2019Matching is as Easy as the Decision Problem, in the NC Modelcited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 2; 2024: 6; 2025: 1; 2026: 4.

13 papers.

Sort:

  1. 2023Replicability in Reinforcement Learningcited by 21
  2. 2023Local Borsuk-Ulam, Stability, and Replicabilitycited by 14
  3. 2024Replicable Learning of Large-Margin Halfspacescited by 12
  4. 2024On the Computational Landscape of Replicable Learningcited by 7
  5. 2024Replicability in High Dimensional Statisticscited by 7
  6. 2024Replicable Uniformity Testingcited by 4
  7. 2024Replicability is Asymptotically Free in Multi-armed Banditscited by 2
  8. 2025Simplicial covering dimension of extremal concept classescited by 2
  9. 2026The Sample Complexity of Replicable Realizable PAC Learningcited by 1
  10. 2026Tight list replicability bounds via a novel sphere covering theoremcited by 1
  11. 2026Sign-Rank, Index, and List Replicability: Connections and Separationscited by 1
  12. 2024Generalizability of experimental studiescited by 0
1 more
  1. 2026Replicable Conformal Predictioncited by 0