Research map / Federated learning and privacy / Differential privacy

Computationally Efficient Replicable Learning of Parities and Applications

NeurIPS 2026 · Federated learning and privacy › Differential privacy · approach: Private online and user-level learning · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Gives the first polynomial-time replicable PAC learner for realizable parity learning over arbitrary distributions, built on a new replicable linear-span subroutine, and uses it to argue that generic replicable-to-pure-DP conversion must lose in failure-probability dependence under RP≠NP.

Problem

Efficient (polynomial-time) replicable PAC learning of parities over arbitrary distributions was open; prior replicable parity learners worked only for uniform distributions or ran in time exponential in decision-tree complexity. Also unclear how replicability relates computationally to pure differe

Approach

Compute a replicable subspace of the linear span of the (d+1)-dimensional labeled points by thresholding multiplicities of subspaces from the stable partition with a shared random threshold; then output a consistent parity inside the filtered subspace, or bottom if the label direction e_{d+1} lies in it.

Key results

• Replicable linear span achieves sample complexity poly(d,1/rho,1/eps) with running time O(m^2 d^3) and coverage 1-eps fraction, per the theorems.
• Empirically (d=20, rho=0.05), the replicable learner reaches about 90% replicability at large m, versus 20-30% for Gaussian elimination under the biased distribution.
• Replicable learner test accuracy is about 88% at m=1000 versus nearly 100% for Gaussian elimination.

Surprising findings

• Gaussian elimination, though optimal on uniform distributions, is highly non-replicable under biased distributions (20-30% replicability in experiments).

Limitations

• Realizable setting only; agnostic parity learning is NP-hard and noisy parity is conjectured hard.
• Pure DP impossibility holds only for generic transformations under RP≠NP and for classes with representation dimension polynomial in Littlestone dimension.
• Empirical accuracy trade-off: replicable learner reaches about 88% versus near 100% for Gaussian elimination.

Experimental setup

Datasets: synthetic parity samples over F_2^d with biased distribution D(e_i)=2^{-i}

Benchmarks: synthetic parity learning with d=20

Metrics: replicability (empirical match rate) holdout test accuracy sample complexity bound

Baselines: Gaussian elimination (ERM)

Builds on: stable partition (Bun et al.) replicability (Impagliazzo et al.) replicable statistical query private linear span

Closest papers by meaning

• On the Computational Landscape of Replicable Learning (NeurIPS 2024 · similarity 0.92)
• Oracle-Efficient Differentially Private Learning with Public Data (NeurIPS 2024 · similarity 0.88)
• Privacy Guarantees in Posterior Sampling under Contamination (NeurIPS 2026 · similarity 0.87)
• Minimax Optimal Two-Sample Testing under Local Differential Privacy (NeurIPS 2026 · similarity 0.87)
• The Role of Randomness in Stability (ICML 2025 · similarity 0.87)
• Exactly Minimax-Optimal Locally Differentially Private Sampling (NeurIPS 2024 · similarity 0.86)