Replicable Composition

Kiarash Banihashem; MohammadHossein Bateni; Hossein Esfandiari; Samira Goudarzi; MohammadTaghi Hajiaghayi

cs.LGApr 12, 2026

Replicable Composition

Authors: Kiarash Banihashem, MohammadHossein Bateni, Hossein Esfandiari, Samira Goudarzi, MohammadTaghi Hajiaghayi

Organizations: University of Maryland, College Park, MD, USA · Google Research, New York City, NY, USA · Google Research, London, UK

Abstract

Replicability requires that algorithmic conclusions remain consistent when rerun on independently drawn data. A central structural question is composition: given $k$ problems each admitting a $ρ$ -replicable algorithm with sample complexity $n$ , how many samples are needed to solve all jointly while preserving replicability? The naive analysis yields $\widetilde{O}(nk^2)$ samples, and Bun et al. (STOC'23) observed that reductions through differential privacy give an alternative $\widetilde{O}(n^2k)$ bound, leaving open whether the optimal $\widetilde{O}(nk)$ scaling is achievable. We resolve this open problem and, more generally, show that problems with sample complexities $n_1,\ldots,n_k$ can be jointly solved with $\widetilde{O}(\sum_i n_i)$ samples while preserving constant replicability. Our approach converts each replicable algorithm into a perfectly generalizing one, composes them via a privacy-style analysis, and maps back via correlated sampling. This yields the first advanced composition theorem for replicability. En route, we obtain new bounds for the composition of perfectly generalizing algorithms with heterogeneous parameters. As part of our results, we provide a boosting theorem for the success probability of replicable algorithms. For a broad class of problems, the failure probability appears as a separate additive term independent of $ρ$ , immediately yielding improved sample complexity bounds for several problems. Finally, we prove an $Ω(nk^2)$ lower bound for adaptive composition, establishing a quadratic separation from the non-adaptive setting. The key technique, which we call the phantom run, yields structural results of independent interest.

Figures & tables

Problem	Previous Bound	New Bound (This work)
Statistical Query	$O\left(\frac{\log(1/\beta)}{\alpha^{2}\rho^{2}}\right)$ for $\beta\geq\rho$ [ 27 ]	$O\left(\frac{\log(1/\rho)}{\alpha^{2}\rho^{2}}+\frac{\log(1/\beta)}{\alpha^{2}}\right)$
PAC, Littlestone	$\widetilde{O}\left(\frac{d^{12}\log^{3}(1/\beta)}{\alpha^{2}\rho^{2}}\right)$ [ 8 ]	$\widetilde{O}\left(\frac{d^{12}}{\alpha^{2}\rho^{2}}+\frac{\log(1/\beta)}{\alpha}\right)$
PAC, finite classes	$O\left(\frac{(\log^{2}\|\mathcal{H}\|+\log(1/(\rho\beta)))\log^{3}(1/\rho)}{\alpha\rho^{2}}\right)$ [ 8 ]	$O\left(\frac{(\log^{2}\|\mathcal{H}\|+\log(1/\rho))\log^{3}(1/\rho)}{\alpha\rho^{2}}+\frac{\log(1/\beta)}{\alpha}\right)$
PAC, thresholds	$\widetilde{O}\left(\frac{(\log^{*}d)^{3}\log^{2}(1/\beta)}{\alpha^{2}\rho^{2}}\right)$ [ 8 ]	$\widetilde{O}\left(\frac{(\log^{*}d)^{3}}{\alpha^{2}\rho^{2}}+\frac{\log(1/\beta)}{\alpha}\right)$
Heavy-hitters	$\widetilde{O}\left(\frac{\log(1/\beta)}{\nu\epsilon^{2}\rho^{2}}\right)$ [ 21 ]	$\widetilde{O}\left(\frac{1}{\nu\epsilon^{2}\rho^{2}}+\frac{\log(1/\beta)}{\epsilon^{2}}\right)$
Best arm	$O(\frac{\log^{3}(\|A\|/\beta)}{\rho^{2}\alpha^{2}})$ [ 26 ]	$O\left(\frac{\log^{3}(\|A\|/\rho)}{\rho^{2}\alpha^{2}}+\frac{\log(\|A\|/\beta)}{\alpha^{2}}\right)$

Table 1: Examples of improved upper bounds obtained via Theorem 5 . The list includes Statistical Query estimation, PAC learning with bounded Littlestone dimension

d

, PAC learning for a finite class

\mathcal{H}

, PAC learning of thresholds over

\{0,1,\dots,d\}

, the

(\nu,\epsilon)

-approximate heavy-hitters problem, and the best arm problem with additive error

\alpha

over a finite set

A

. We emphasize that the list is by no means exhaustive. For most existing work the dependence on

\beta

appears as a multiplicative

\operatorname{polylog}(1/\beta)

factor. Theorem 5 (see Theorem 12 for a formal statement) shows that in many cases

\beta

appears in a separate additive term independent of

\rho

Sample Complexity

Sample complexity studies how many data points, queries, or observations are needed to learn, estimate, test, or sample to a target accuracy.

See all 96 papers

The Optimal Sample Complexity of Pointwise Replicable Agnostic Learning
Oct 18, 2026Guangjian ZhangAgnostic Learning Sample Complexity
Replicability is Asymptotically Free in Multi-armed Bandits
Feb 12, 2024Junpei Komiyama, Shinji Ito, Yuichi Yoshida +1Multi-Armed Bandits ML Reproducibility
New York University · Mohamed bin Zayed University of Artificial Intelligence (MBZUAI) · RIKEN AIP +2
Replicable Constrained Bandits
Feb 16, 2026Matteo Bollini, Gianmarco Genalti, Francesco Emanuele Stradi +2Multi-Armed Bandits ML Reproducibility
Politecnico di Milano

Oct 18, 2026J/K move · Enter open · S save

The Optimal Sample Complexity of Pointwise Replicable Agnostic Learning

Guangjian Zhang

Agnostic Learning Sample Complexity Statistical Learning Theory

Open paper AskPDF arXiv

Pointwise replicability asks that two independently trained predictors, using the same random seed, agree at each fixed query with high probability. We determine its optimal agnostic sample complexity on finite and countable domains. For every nonempty binary class of finite VC dimension

d\ge1

, the required number of independent examples is

Θ\!\left(\frac{d}{ρ^2α^2}+\frac{\log(1/β)}{α^2}\right)

, uniformly over independent accuracy, failure, and disagreement parameters

α,β,ρ\in(0,1/10)

. The learner returns one binary function, may be improper, and uses unrestricted shared randomness. Its sample budget is fixed before observing data, and the replicability guarantee includes queries of zero marginal mass. The main construction combines an ensemble of empirical-risk minimizers with a smooth, signal-dependent risk decomposition. A single shared phase selects the final binary predictor. Record times certify its weak-signal risk, while a uniform bound protects the strong-signal risk at that same selected time. A phase-comparison theorem controls the actual shared-seed execution under simultaneous changes in the marginals and risk coefficients. A rare repair step then makes the confidence cost additive. Together with matching lower bounds, this removes the remaining logarithmic overhead and parameter restrictions in the general countable-domain sample-complexity problem. This extended version also retains the earlier explicit constructions and their proofs, including proper learning for VC-one classes, the full finite-atom class, a faster realizable bound, and counterexamples that separate restrictions of particular algorithms from restrictions of the learning problem.

Abstract

Sample Complexity

Explore similar work

The Optimal Sample Complexity of Pointwise Replicable Agnostic Learning

Replicability is Asymptotically Free in Multi-armed Bandits

Replicable Constrained Bandits