Skip to main content
Back

Researchers Prove Replicable AI Pipelines Can Run on Linear Data Samples

A team of five researchers closes a decade-defining gap in replicable algorithm theory, proving optimal sample scaling when composing k stable procedures.

Pro

Paper, Full Access
  • New paper resolves an open STOC 2023 question on replicable algorithm composition.
  • Non-adaptive composition of k replicable algorithms achieves optimal Õ(sum n_i) sample complexity.
  • Method: convert to perfectly generalizing, compose via privacy analysis, map back with correlated sampling.
  • First advanced composition theorem for replicability, closing gap between prior Õ(nk²) and Õ(n²k) bounds.
  • Adaptive setting is fundamentally harder: proves Ω(nk²) lower bound via a phantom run technique.
  • Bonus boosting theorem yields improved sample bounds for several downstream replicable learning problems.

Replicability is the guarantee that if you rerun the same algorithm on a freshly drawn dataset, you get the same output. It sounds mundane, but in a field where reruns produce different models, different rankings, and different scientific conclusions, it turns out to be a hard mathematical property to preserve, especially when you start chaining algorithms together. A new arXiv preprint on replicable composition, by Kiarash Banihashem, MohammadHossein Bateni, Hossein Esfandiari, Samira Goudarzi, and Mohammad Hajiaghayi, resolves an open question left dangling since STOC 2023 about how much data that chaining actually costs.

The composition gap that would not close

The formal notion of replicability was introduced at STOC 2022. A replicable algorithm gives the same output with high probability when its randomness is fixed and it is run on a new i.i.d. sample drawn from the same distribution. The motivation is scientific: replicable algorithms let independent researchers verify published results by ensuring that an analysis returns the same answer with high probability, even on a fresh dataset.

Trouble starts when you want to run several such routines on the same data, say a clustering step, a classifier, and a statistical test. Each is individually stable, but the joint pipeline may not be. The central question is how many samples you need to keep the whole chain replicable.

Before this work, the picture had two unsatisfying answers. The naive analysis yields Õ(nk²) samples, and Bun et al. (STOC'23) observed that reductions through differential privacy give an alternative Õ(n²k) bound, leaving open whether the optimal Õ(nk) scaling is achievable. One bound is quadratic in the number of tasks, the other quadratic in the per-task sample size. Neither is tight, and both blow up quickly.