Computationally Efficient Replicable Learning of Parities
This work addresses a foundational problem in machine learning theory by bridging gaps between replicability, differential privacy, and SQ-learning, with implications for algorithm design in privacy-preserving and stable learning.
The paper tackles the computational relationship between replicable learning and other stability notions, specifically showing that efficient replicable learning can extend beyond the statistical query (SQ) model by providing the first computationally efficient replicable algorithm for learning parities over arbitrary distributions, which was previously hard in the SQ model but possible under differential privacy.
We study the computational relationship between replicability (Impagliazzo et al. [STOC `22], Ghazi et al. [NeurIPS `21]) and other stability notions. Specifically, we focus on replicable PAC learning and its connections to differential privacy (Dwork et al. [TCC 2006]) and to the statistical query (SQ) model (Kearns [JACM `98]). Statistically, it was known that differentially private learning and replicable learning are equivalent and strictly more powerful than SQ-learning. Yet, computationally, all previously known efficient (i.e., polynomial-time) replicable learning algorithms were confined to SQ-learnable tasks or restricted distributions, in contrast to differentially private learning. Our main contribution is the first computationally efficient replicable algorithm for realizable learning of parities over arbitrary distributions, a task that is known to be hard in the SQ-model, but possible under differential privacy. This result provides the first evidence that efficient replicable learning over general distributions strictly extends efficient SQ-learning, and is closer in power to efficient differentially private learning, despite computational separations between replicability and privacy. Our main building block is a new, efficient, and replicable algorithm that, given a set of vectors, outputs a subspace of their linear span that covers most of them.