Research map / Learning theory and algorithms / Sample complexity
On the Computational Landscape of Replicable Learning
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.
Studies computational aspects of replicable PAC learning, giving a separation from online learning under OWFs, a replicable lifting framework from uniform to decision-tree-structured marginals (with parity application), and a pure-DP-to-replicable transformation with exponential dependence on representation dimension.
Problem
How replicable PAC learning computationally relates to online learning, statistical query learning, and private (pure and approximate DP) learning, and whether parities can be learned replicably under non-uniform marginals.
Approach
Shows a computational separation between replicable and online learning via One-Way Sequences with a replicable quantile estimator; lifts replicable uniform learners to arbitrary marginals of bounded decision-tree complexity by decomposing into subcube-uniform mixtures; and transforms pure DP learners into replicable ones with exp(representation dimension) runtime.
Key results
- Replicable PAC learner for One-Way Sequences with poly(d, 1/alpha, 1/rho) sample and time complexity, separating replicable PAC learning from efficient online learning under OWFs.
- Replicable lifting framework yields replicable PAC learners under monotone distributions with decision tree complexity l at sample/runtime blowup (m*l)^l.
- Pure DP learners transform to replicable learners with poly(1/alpha, 1/rho, log(1/beta), dim) samples and poly * exp(dim) running time.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use replicable quantile estimation to select an approximate minimum index | OWS PAC learning · One-Way Sequences (OWS_d) | efficient replicable PAC learnability | Helped |
| Use a uniform-marginal replicable learner as a black-box component in the lifting framework | Replicable PAC learning under monotone marginals · Boolean hypercube with monotone marginal of decision tree complexity ℓ | replicable PAC learnability | Helped |
| Add conditional sampling to the replicable lifting framework | Replicable PAC learning under arbitrary marginals · Boolean hypercube with arbitrary marginal of decision tree complexity ℓ | replicable PAC learnability | Helped |
| Adapt the uniform-marginal Gaussian-elimination learner to affine parities | Affine parity learning · Affine parities under uniform marginal | replicable PAC learnability | Helped |
| Apply replicable lifting to the uniform affine-parity learner | Affine parity learning · Affine parities under unknown monotone marginals | replicable PAC learnability | Helped |
| Transform a pure DP learner into a replicable learner | Realizable PAC learning · Concept classes with pure DP learners | replicable learnability | Helped |
| Require efficient online no-regret learning rather than replicable PAC learning | OWS · One-Way Sequences (OWS_d) | efficient learnability | Hurt |
| Use standard Gaussian elimination under the constructed non-uniform marginal | Parity learning · Monotone marginals with decision tree complexity ℓ = Θ(1) | replicable PAC learnability | Hurt |
| Transform a pure DP learner into a replicable learner | Realizable PAC learning · Concept classes with representation dimension | running time | Hurt |
Surprising findings
- Gaussian elimination can fail to be replicable with constant probability under some monotone low-decision-tree-complexity distributions, even though it is replicable under uniform marginals.
Limitations
- Pure DP to replicable transformation runs in exp(representation dimension) time.
- Lifting runtime scales as (m*l)^l, quasi-polynomial when l=O(log d).
- Open whether efficient replicable learners exist for parities under every distribution.
Experimental setup
Metrics: sample complexity time complexity replicability parameter
Baselines: Gaussian elimination
Builds on: replicable learning (Impagliazzo et al.) One-Way Sequences online hardness (Blum) Gaussian elimination for parities pure DP to online transformation
Closest papers by meaning
- Computationally Efficient Replicable Learning of Parities and Applications (NeurIPS 2026 · similarity 0.92)
- List and Certificate Complexities in Replicable Learning (NeurIPS 2023 · similarity 0.90)
- Replicable Online Learning (NeurIPS 2025 · similarity 0.88)
- The Role of Randomness in Stability (ICML 2025 · similarity 0.88)
- Replicable Constrained Bandits (NeurIPS 2026 · similarity 0.86)
- Replicability in Learning: Geometric Partitions and KKM-Sperner Lemma (NeurIPS 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.