mlsanityData to 14 Oct 2026

Statistical Indistinguishability of Learning Algorithms

arXiv 2305.14311 ↗First posted 23 May 2023cs.LG cs.DS stat.MLcited by 17

Not on the map. Why?

Abstract (arXiv)

When two different parties use the same learning rule on their own data, how can we test whether the distributions of the two outcomes are similar? In this paper, we study the similarity of outcomes of learning rules through the lens of the Total Variation (TV) distance of distributions. We say that a learning rule is TV indistinguishable if the expected TV distance between the posterior distributions of its outputs, executed on two training data sets drawn independently from the same distribution, is small. We first investigate the learnability of hypothesis classes using TV indistinguishable learners. Our main results are information-theoretic equivalences between TV indistinguishability and existing algorithmic stability notions such as replicability and approximate differential privacy. Then, we provide statistical amplification and boosting algorithms for TV indistinguishable learners.

Key facts. Cited by 17 papers in the map (data through 14 Oct 2026). Builds on 25 of its 78 references that are in the map. First posted on arXiv 23 May 2023.

Builds on

25 of 78 references.

References · 25

  1. 2020Improving Reproducibility in Machine Learning Research (A Report from the NeurIPS 2019 Reproducibility Program)cited by 322
  2. 2021Machine Unlearning via Algorithmic Stabilitycited by 130
  3. 2014Preserving Statistical Validity in Adaptive Data Analysiscited by 103
  4. 2015Algorithmic Stability for Adaptive Data Analysiscited by 88
  5. 2018Private PAC learning implies finite Littlestone dimensioncited by 74
  6. 2020An Equivalence Between Private Classification and Online Predictioncited by 64
  7. 2020A Theory of Universal Learningcited by 60
  8. 2020Statistical-Query Lower Bounds via Functional Gradientscited by 50
  9. 2022Reproducibility in Learningcited by 44
  10. 2023Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalizationcited by 42
  11. 2015Simultaneous Private Learning of Multiple Conceptscited by 34
  12. 2020Sample-efficient proper PAC learning with approximate differential privacycited by 29
13 more
  1. 2020A Limitation of the PAC-Bayes Frameworkcited by 25
  2. 2021Efficient Algorithms for Learning from Coarse Labelscited by 21
  3. 2022Reproducibility in Optimization: Theoretical Framework and Limitscited by 21
  4. 2022Integral Probability Metrics PAC-Bayes Boundscited by 19
  5. 2023Replicable Clusteringcited by 19
  6. 2016Adaptive Learning with Robust Generalization Guaranteescited by 15
  7. 2022Multiclass Learnability Beyond the PAC Framework: Universal Rates and Partial Concept Classescited by 14
  8. 20152 Notes on Classes with Vapnik-Chervonenkis Dimension 1cited by 12
  9. 2020On the Equivalence between Online and Private Learnability beyond Binary Classificationcited by 12
  10. 2021User-Level Private Learning via Correlated Samplingcited by 9
  11. 2022Fine-Grained Distribution-Dependent Learning Curvescited by 7
  12. 2016Typical Stabilitycited by 6
  13. 2021Multiclass versus Binary Differentially Private PAC Learningcited by 4

Built on by

Cited by year (2026 to 14 Oct)

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

17 papers.

Sort:

By area:

  1. 2023Optimal Learners for Realizable Regression: PAC Learning and Online Learningcited by 23
  2. 2023Replicable Reinforcement Learningcited by 21
  3. 2023Replicability in Reinforcement Learningcited by 21
  4. 2023The Bayesian Stability Zoocited by 13
  5. 2024Replicable Learning of Large-Margin Halfspacescited by 12
  6. 2024What Do Machine Learning Researchers Mean by "Reproducible"?cited by 9
  7. 2024Replicability in High Dimensional Statisticscited by 8
  8. 2024On the Computational Landscape of Replicable Learningcited by 7
  9. 2024Replicable Online Learningcited by 7
  10. 2023Simple online learning with consistent oraclecited by 5
  11. 2026The Unseen Threat: Residual Knowledge in Machine Unlearning under Perturbed Samplescited by 4
  12. 2023Optimal Guarantees for Algorithmic Reproducibility and Gradient Complexity in Convex Optimizationcited by 3
5 more
  1. 2024Privacy of SGD under Gaussian or Heavy-Tailed Noise: Guarantees without Gradient Clippingcited by 3
  2. 2024Replicability is Asymptotically Free in Multi-armed Banditscited by 2
  3. 2024Agnostic Private Density Estimation for GMMs via List Global Stabilitycited by 2
  4. 2025Replicable Distribution Testingcited by 2
  5. 2024Generalizability of experimental studiescited by 0