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

Oct 18, 2026

The Optimal Sample Complexity of Pointwise Replicable Agnostic Learning

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.

Guangjian Zhang

Agnostic Learning Sample Complexity Statistical Learning Theory

Ask PDF

Feb 12, 2024

Replicability is Asymptotically Free in Multi-armed Bandits

We consider a replicable stochastic multi-armed bandit algorithm that ensures, with high probability, that the algorithm's sequence of actions is not affected by the randomness inherent in the dataset. Replicability allows third parties to reproduce published findings and assists the original researcher in applying standard statistical tests. We observe that existing algorithms require

O(K^2/ρ^2)

times more regret than nonreplicable algorithms, where

K

is the number of arms and

ρ

is the level of nonreplication. However, we demonstrate that this additional cost is unnecessary when the time horizon

T

is sufficiently large for a given

K, ρ

, provided that the magnitude of the confidence bounds is chosen carefully. Therefore, for a large

T

, our algorithm only requires

K^2/ρ^2

times smaller amount of exploration than existing algorithms. To ensure the replicability of the proposed algorithms, we incorporate randomness into their decision-making processes. We propose a principled approach to limiting the probability of nonreplication. This approach elucidates the steps that existing research has implicitly followed. Furthermore, we derive the first lower bound for the two-armed replicable bandit problem, which implies the optimality of the proposed algorithms up to a

\log\log T

factor for the two-armed case.

Junpei Komiyama, Shinji Ito, Yuichi Yoshida +1

New York University · Mohamed bin Zayed University of Artificial Intelligence (MBZUAI) · RIKEN AIP +2

Multi-Armed Bandits ML Reproducibility

Ask PDF

Feb 16, 2026

Replicable Constrained Bandits

Algorithmic replicability has recently been introduced to address the need for reproducible experiments in machine learning. A replicable online learning algorithm is one that takes the same sequence of decisions across different executions in the same environment, with high probability. We initiate the study of algorithmic replicability in constrained MAB problems, where a learner interacts with an unknown stochastic environment for

T

rounds, seeking not only to maximize reward but also to satisfy multiple constraints. Our main result is that replicability can be achieved in constrained MABs. Specifically, we design replicable algorithms whose regret and constraint violation match those of non-replicable ones in terms of

T

. As a key step toward these guarantees, we develop the first replicable UCB-like algorithm for unconstrained MABs, showing that algorithms that employ the optimism in-the-face-of-uncertainty principle can be replicable, a result that we believe is of independent interest.

Matteo Bollini, Gianmarco Genalti, Francesco Emanuele Stradi +2

Politecnico di Milano

Multi-Armed Bandits ML Reproducibility UCB Algorithms

Ask PDF

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