Replicable Online Learners Must Gamble: The Typical-Case Price of ReplicabilityResearch Paper
A randomized algorithm is replicable if, run twice with the same internal randomness on two independent samples from the same distribution, it returns the same output with high probability. Impagliazzo, Lei, Pitassi and Sorrell introduced the notion for batch learning (ILPS22), where it is now known to be equivalent to approximate differential privacy up to…