The Sample Complexity of Algorithmic Replicability

28 concepts17 papers2 proposals

When two independent research teams train the same machine learning model on different datasets drawn from the exact same population, they expect to reach the same scientific conclusions. In practice, however, data randomness, non-convex optimization landscapes, and stochastic training dynamics often cause their final models to diverge. This variance underpins the modern reproducibility crisis in empirical computer science.

To address this, recent theoretical work introduces a formal, stringent standard known as algorithmic replicability. First formalized in the context of learning by Russell Impagliazzo et al. in Reproducibility in Learning, an algorithm is defined as replicable if, when given access to a shared random seed, it outputs the exact same result with high probability when run on two completely independent datasets drawn from the same distribution.

While conceptually powerful, achieving this level of absolute consistency introduces a fundamental trade-off: a significant increase in sample complexity, often referred to as the "price of replicability."

Why Replicability Costs Data: The Boundary Problem

To understand why replicability requires more data, consider a simple estimation task. Suppose an algorithm calculates an empirical average $\hat{\mu}$ from a dataset to decide between two models. If the true mean $\mu$ sits exactly on a decision boundary (e.g., $\mu = 0.5$), two independent datasets will yield slightly different empirical estimates—say, $\hat{\mu}_1 = 0.501$ and $\hat{\mu}_2 = 0.499$. Even if the difference between these estimates is minuscule, any deterministic decision rule will split them, causing the two runs to output entirely different models.

To force these independent runs to output the exact same result, replicable algorithms leverage shared randomness to discretize the output space. Imagine a grid of rounding intervals superimposed over the continuous space of estimates. If the position of this grid is shifted by a shared random offset $r$, the grid lines act as consensus boundaries.

Standard Rounding (Fixed Boundary):
              Boundary
                 │
   ───[Run 1]────┼────[Run 2]───   --> Run 1 and Run 2 disagree!
               0.5

Shared Random Rounding (Randomized Grid):
        Boundary
           │
   ───[Run 1]──[Run 2]──────────   --> Both runs fall into the same bucket!
          0.42

If two empirical estimates $\hat{\mu}_1$ and $\hat{\mu}_2$ are close enough together, the probability that a randomly shifted grid line falls between them is small. If no boundary falls between them, they snap to the exact same grid cell, guaranteeing identical outputs.

However, ensuring that the independent estimates are close enough to rarely be split by a random boundary requires their variance to be exceptionally small. As shown by Mark Bun et al. in Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization, this demand typically incurs a quadratic blowup ($O(1/\rho^2)$) in sample complexity relative to the desired replicability error $\rho$. To buy absolute consistency in a noisy environment, you must pay with a larger dataset.

The Limits of Replicability across Domains

The tension between statistical efficiency and output stability manifests uniquely across different algorithmic domains, revealing where replicability is cheap and where it is fundamentally expensive.

Optimization and Classification

In optimization, the choice of algorithm dictates its inherent replicability. Kwangjun Ahn et al. demonstrate in Reproducibility in Optimization: Theoretical Framework and Limits that standard gradient descent is fundamentally more stable than accelerated gradient methods. Acceleration amplifies early sampling errors, whereas slower, smoother trajectories naturally reject noise, showing that computational iterations can be traded for output consistency.

For geometric problems like large-margin classification, the data overhead can sometimes be bypassed. Alkis Kalavasis et al. proved in Replicable Learning of Large-Margin Halfspaces that by pairing dimensionality reduction with specialized rounding schemes, one can achieve dimension-independent replicable learners that match the optimal sample complexity of their non-replicable counterparts.

Reinforcement Learning and Bandits

Sequential decision-making compounds the difficulty of replicability because early variations in a policy alter the distribution of states an agent observes later. In Replicability in Reinforcement Learning, Amin Karbasi et al. highlight a severe tension: while coupling techniques can force identical policy outputs across independent environments, doing so within practical sample limits currently demands exponential computation time.

To mitigate this "replicability tax," Eric Eaton et al. developed the first provably replicable variants of Value Iteration and R-max in Replicable Reinforcement Learning, later expanding these primitives to high-dimensional spaces via linear function approximation in Replicable Reinforcement Learning with Linear Function Approximation.

Interestingly, interactive learning does not always suffer an asymptotic penalty. In Replicable Bandits, Hossein Esfandiari et al. proved that a multi-armed bandit algorithm can pull the exact same sequence of arms across independent executions while maintaining near-optimal regret bounds, showing that the cost of replicability in some interactive settings is merely a constant-factor overhead.

Statistical Testing

Replicability also redefines classical hypothesis testing. In Replicable Uniformity Testing, Sihan Liu et al. designed testers guaranteed to return the same verdict on edge-case data distributions. As explored by Ilias Diakonikolas et al. in Replicable Distribution Testing, a replicable tester's acceptance probability must concentrate tightly around its mean to avoid divergent results. This requirement causes the sample complexity of replicable property testing to scale similarly to high-confidence statistical testing.

Topological and Mathematical Boundaries

Is it always possible to make a learning process replicable? Theoretical limits suggest otherwise. Bogdan Chornomaz et al. established a bridge between algebraic topology and algorithmic stability in Local Borsuk-Ulam, Stability, and Replicability. They proved that in agnostic learning settings—where data contains arbitrary noise—replicable learning is mathematically impossible unless the underlying hypothesis class is strictly finite.

This uncovers a fundamental stability gap: while standard machine learning merely requires a finite Vapnik-Chervonenkis (VC) dimension to guarantee generalization, ensuring that two scientists arrive at the exact same model requires drastically more restrictive constraints on the model space itself.

Key Foundational Work

Reproducibility in Learning (2022) — contributed 2 concept elements to this direction.
Representations for Stable Off-Policy Reinforcement Learning (2020) — contributed 1 concept elements to this direction.
Reproducibility in Optimization: Theoretical Framework and Limits (2022) — contributed 1 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 18 papers
  2. Version 1 · 2026-10-04 · 28 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_replicability_efficiency_tradeoff_302e8c9d,
  title = {replicability-efficiency tradeoff},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/replicability-efficiency-tradeoff/rdr_302e8c9d86924e4788e6329b55c49c4d},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_replicability_efficiency_tradeoff_302e8c9d_v2,
  title = {replicability-efficiency tradeoff},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/replicability-efficiency-tradeoff/rdr_302e8c9d86924e4788e6329b55c49c4d/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake