Replicability in Learning
summary
Defines rho‑replicable randomized algorithms that, with probability 1−rho, produce exactly the same output on two independent samples from the same distribution when the random string is fixed. Implements replicability for statistical queries, approximate heavy hitters, medians, and halfspaces via a randomized discretization (rounding empirical estimates to a random grid) and correlated sampling, giving sample complexity with an inverse‑quadratic dependence on rho and requiring the publish the randomness protocol. Shows formal links to differential privacy and max‑information, and proves a computational barrier: efficient correlated sampler needs finite output range or else one‑way cryptography yields exponential hardness.
AI-written summary · about
chapters (7)
- 0:00Introduction to replicability
- 3:44Defining replicable algorithms
- 10:45Statistical query simulation
- 21:57Connections between stability
- 32:22Algorithmic transformations
- 39:50Computational complexity
- 47:56Q&A and final remarks
related talks
30mReproducible Machine Learning
35mPrivacy amplification by random allocation
48mLearning by Local Entropy Maximization
01h 57mResearch Reproducibility in Embedded Learning
54mPrivacy Amplification from Structured Algorithmic Randomness
17mData privacy and reliable learning
41mReducibility and Statistical-Computational Gaps from Secret Leakage
43mDifferential Privacy Meets Robust Statistics