Improved Replicable Boosting with Majority-of-Majorities

Clement Svendsen; Kasper Green Larsen; Markus Engelund Mathiasen

REVIEW 2 major objections 4 minor 1 cited by

Improved Replicable Boosting with Majority-of-Majorities

T0 review · 2 major / 4 minor · reviewed 2026-08-09 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read MetaBoost, a two-layer majority-vote booster, is proven to achieve the best-known sample complexity for replicable boosting.

desk verdict A genuine step forward for replicable boosting, but the advertised sample complexity is stronger than what the proof supports unless the paper adds an explicit growth assumption on the weak learner's sample complexity. read the letter →

arxiv 2501.18388 v2 pith:7UMNGXO3 submitted 2025-01-30 cs.LG

Kasper Green Larsen , Markus Engelund Mathiasen , Clement Svendsen This is my paper · ORCID

classification cs.LG MSC 68Q3268W20

keywords replicableboostingsamplecomplexitymajority-of-majoritiesweak-to-stronglearningthresholdchecksmoothAdaBoostreplicability

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Replicable learning asks an algorithm to output the same hypothesis with high probability when run twice on independent samples from the same distribution but with the same internal randomness. This paper claims that boosting in this setting can be made much cheaper: its two-layer majority-vote algorithm MetaBoost turns any replicable weak learner with advantage $\gamma$ into a strong learner with sample complexity $\widetilde{O}(m_W(\widetilde{\Theta}(\rho\gamma^2))/(\epsilon\gamma^2) + 1/(\rho^2\epsilon\gamma^3))$, while making only $O(\ln(1/\epsilon)/\gamma^2)$ calls to the weak learner. The key idea is to run an improved replicable booster only at constant error, then reduce the error with an AdaBoost-style outer loop, avoiding the $1/\epsilon$ blow-up of earlier replicable boosting. The engine behind the savings is a new replicable threshold check that costs $1/z$ samples instead of $1/z^2$. If the analysis is correct, this is the best-known sample complexity for replicable boosting.

What carries the argument

The central object is the two-layer majority structure: MetaBoost calls Booster* with constant target error $\epsilon_0 = 1/16$ and treats its majority vote as a weak hypothesis of constant advantage. The load-bearing mechanism is the reweighting function $\mu_t(x) = \exp(M_t(x) - c_t)$, where $M_t$ is a capped count of how often $x$ has been misclassified and $c_t$ is the current cap; the proof shows the density $d(\mu_t) \ge \epsilon/32$, which guarantees rejection sampling from the reweighted distribution $D_{\mu_t}$ is cheap. The cap decisions are made by the replicable Threshold subroutine, which draws a random cutoff $z_0$ uniformly in $[3z/4, 3z/2]$ and compares the empirical mean of a test function to it; since it outputs only a bit, its sample complexity is $O(\ln(1/\delta)/(\rho^2 z))$. Keeping the density high and capping only when the test function has small mass confines the hard points to sets of total mass at most $\epsilon/8$ per iteration, which is what produces the final error bound.

What would settle it

Take a weak learner with sample complexity $m_W(s) = \exp(1/s)$ and substitute it into Lemma 2.6's first term: the argument becomes $m_W(\Theta(\rho\gamma^2/T)) \approx \exp(T/(\rho\gamma^2))$, which cannot be absorbed into $\widetilde{O}(m_W(\Theta(\rho\gamma^2))/(\epsilon\gamma^2))$. This calculation is the direct check; it shows the stated sample complexity fails for such weak learners.

Watch

Extended reading notes

Core claim

The paper's central claim, Theorem 1.2, is that for any $\rho, \epsilon \in (0,1)$ and any $\Theta(\rho\gamma^2)$-replicable weak learner with advantage $\gamma$, MetaBoost is $\rho$-replicable, makes $O(\ln(1/\epsilon)/\gamma^2)$ calls to the weak learner, and with probability at least $1-\rho$ outputs a hypothesis $H$ with $\mathrm{Er}_D(H) \le \epsilon$. Its sample complexity is the expression given above. The discovery is that a majority-of-majorities arrangement, in which the modified replicable booster Booster* is used as a constant-error subroutine and its output is amplified by exponential reweighting with capped counters, removes most of the $\epsilon$ and $\gamma$ dependence from earlier replicable boosting bounds. The proof bounds the final error through a potential $\mathbb{E}[\exp(M_{T+1}(X))]$, splits the bad set into points with high capped count and points misclassified despite low count, and controls both sets by the replicable threshold checks.

Load-bearing premise

The headline sample-complexity bound assumes the weak learner's sample need does not blow up faster than a polynomial as its replicability parameter is tightened; if it does, the claimed tilde-O bound is not justified.

Editorial extensions

If this is right

If Theorem 1.2 is correct, replicable boosting is within logarithmic factors of non-replicable AdaBoost in its number of weak-learner calls, while retaining polynomial sample complexity in $1/\rho$ and $1/\epsilon$.
The first sample-complexity term no longer has a factor $1/\epsilon$ multiplying the weak learner's sample complexity, and the weak learner only needs replicability $\Theta(\rho\gamma^2)$ instead of $\Theta(\rho\epsilon\gamma^2)$; for weak learners whose sample complexity scales as $1/\rho^2$, that is an extra $1/\epsilon^2$ saving.
The second term drops from $1/(\rho^2\epsilon^5\gamma^6)$ to $1/(\rho^2\epsilon\gamma^3)$, so the algorithm remains usable for small $\epsilon$ and small $\gamma$.
The replicable Threshold check, with $1/z$ instead of $1/z^2$ sample dependence, can replace statistical-query subroutines in other replicable algorithms that only need a yes/no answer about an expectation.
For weak learners with polynomial dependence on their replicability parameter, this is the best-known sample complexity for replicable boosting.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The two-layer recipe suggests a general design pattern for replicable algorithms: pay for an expensive replicable subroutine once at constant accuracy, then delegate error reduction to a non-replicable-style outer loop; this could apply to other replicable learning primitives, not only boosting.
The sample-complexity derivation absorbs a factor $T = O(\ln(1/\epsilon))$ into the weak learner's replicability parameter and then hides it in $\widetilde{O}$; this only works if $m_W$ grows at most polylogarithmically in $1/\rho$, an assumption the paper leaves implicit. A weak learner with exponential growth in $1/\rho$ would escape the stated bound.
Because the Threshold check only needs a multiplicative separation between the threshold and the true expectation, it could serve as a cheap replicable test for property checking, such as verifying whether a model's error exceeds a target, without estimating the error to additive accuracy.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The real news here is the majority-of-majorities construction. The two-layer meta-boosting structure is new, the threshold-check subroutine with 1/z sample complexity is a clean and useful contribution, and the correctness and replicability proofs read as coherent and careful. The algorithm itself looks sound, and the improvement over the prior replicable boosting bound is real once you account for the constant-error invocation of Boost*.

The main problem is the sample-complexity accounting. Theorem 1.2 states the first term as mW(~Θ(ργ^2))/(εγ^2), but Lemma 2.6 actually derives a bound containing mW(Θ(ργ^2/T)) with T=O(ln(1/ε)). You cannot absorb T into the argument of an arbitrary function mW just by writing a tilde over Θ. Tilde-O suppresses polylog factors multiplying an expression; it does not let you change the evaluation point of mW. If mW grows exponentially in 1/ρ, the gap between the proven and stated first terms is super-polynomial in 1/ε. So the theorem either needs an explicit assumption that mW grows at most polynomially or polylogarithmically in 1/ρ, or the final statement must keep T inside mW. This is a fixable but real flaw in the central advertised claim.

A lesser concern: the paper corrects the prior algorithm's sample complexity based on a personal communication with the original authors rather than a public derivation. That is a bit fragile for a comparison baseline, but it does not affect the new algorithm's own correctness.

The threshold subroutine's 1/z dependence is a good observation and seems solid. The bottom-layer Boost* modifications also make sense: replacing the statistical query with a threshold check and inserting the every-1/γ-iteration guard to reduce the number of threshold calls are both reasonable and well motivated.

Bottom line: the construction and most of the analysis are genuinely valuable, and the sample-complexity issue is localized and repairable. I would send this to a serious referee, with the instruction to focus on the mW argument. Once the growth assumption is added or the statement is weakened accordingly, the paper should be in good shape.

Referee Report

2 major / 4 minor

Summary. This paper proposes MetaBoost, a replicable boosting algorithm that combines a modified version of Impagliazzo et al.'s replicable Boost (called Boost*) with a second level of majority voting. The algorithm runs Boost* for T = O(ln(1/ε)) iterations with constant error parameter ε0 = 1/16, and returns the majority vote of the resulting hypotheses. The main claimed result (Theorem 1.2) is that, for a ~Θ(ργ²)-replicable γ-weak learner with sample complexity m_W, MetaBoost is ρ-replicable, makes O(ln(1/ε)/γ²) calls to the weak learner, and has sample complexity ~O(m_W(~Θ(ργ²))/(εγ²) + 1/(ρ²εγ³)). The paper also introduces Threshold, a replicable test for whether E[φ(X)] exceeds a threshold z, with sample complexity O(ln(1/δ)/(ρ²z)).

Significance. The design idea of using a constant-error replicable booster as a subroutine in a meta-boosting scheme with capped multiplicative weights is interesting, and the correctness and replicability analyses are mostly coherent and detailed. If the claimed sample complexity is justified, the improvement over the previous replicable boosting algorithm of Impagliazzo et al. is substantial, particularly in the dependence on ε. The Threshold subroutine is a clean contribution that may be of independent interest. The main weakness is that the final theorem's sample complexity and weak-learner assumption are not fully supported by the proof, as detailed in the major comments.

major comments (2)

[Section 2.1, Lemma 2.6 and Theorem 1.2] The collapse of the sample complexity's first term is not justified for an arbitrary weak learner. Lemma 2.6 derives a first term of O(T ln(T/ρ) ln(T/(ργ²)) m_W(Θ(ργ²/T))/(εγ²)), but Theorem 1.2 states it as ~O(m_W(~Θ(ργ²))/(εγ²)). This requires moving T = Θ(ln(1/ε)) from the argument of m_W into the tilde notation. For an arbitrary function m_W this can change the term super-polynomially, e.g., if m_W(α) = 2^{1/α}, the two expressions differ by a factor 2^{Θ(ln(1/ε)/(ργ²))}. The theorem must either state an explicit growth assumption (e.g., m_W(α) = α^{-O(1)}) or keep T inside the argument of m_W.
[Theorem 1.2 and Section 2.1] The replicability assumption on the weak learner is misstated. The proof of Lemma 2.5 runs Boost* with ρ0 = ρ/(6T) and ε0 = 1/16, so by Theorem 1.4 the weak learner W is called with replicability parameter Θ(ρ0 ε0 γ²) = Θ(ργ²/T). The theorem assumes W is ~Θ(ργ²)-replicable, which is a weaker condition since T ≥ 1. To make the theorem match the proof, the assumption should be Θ(ργ²/ln(1/ε))-replicable (or the proof must be modified to work under the stated assumption).

minor comments (4)

[Algorithm 2, line 5] The pseudocode comments state 'T = O(1/ε)', while Lemma 2.3 and the sample-complexity analysis use T = Θ(ln(1/ε)). This inconsistency should be corrected.
[Theorem 1.4, proof] The bound on the number of iterations T0 = O(1/(εγ²)) is deferred to Servedio [2001] without a precise statement. Please state the exact lemma used and explain why the modification (checking density only every ⌊1/γ⌋ iterations) preserves the bound, preferably with a self-contained argument.
[Notation] The notation ~Θ is used without a formal definition. Please clarify whether it hides polylog factors in all parameters (ε, ρ, γ) or only in some of them, since this affects the interpretation of Theorem 1.2.
[Abstract] There is a typo in the first sentence: 'sign iﬁcantly' should be 'significantly'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: MetaBoost's guarantees are assembled from external replicable-boosting, smooth-boosting, and Chernoff ingredients, with no fitted parameter renamed as a prediction.

full rationale

I walked the derivation chain of Theorem 1.2 through Lemmas 2.1-2.7 and Theorem 1.4. The algorithm does not fit parameters to a subset of data; the predicted error and replicability follow from composition lemmas (Impagliazzo et al.) plus Servedio's smooth-boosting iteration bound and standard Chernoff bounds. None of these are self-citations: the current authors do not overlap with Impagliazzo et al. or Servedio. The only self-citation (Kalavasis et al.) is in related work and is not load-bearing. The definitions of the potential functions N_t, M_t, mu_t are not defined in terms of the final error bound, and the final majority vote is argued from first principles. The one caveat is a sample-complexity accounting step in Lemma 2.6, where T=O(ln(1/epsilon)) is absorbed into the evaluation point of m_W, changing m_W(Theta(rho gamma^2/T)) into m_W(~Theta(rho gamma^2)); for arbitrary m_W this needs an unstated growth assumption. This is a technical gap in the tilde-O notation, not an equivalence-by-construction or a prediction that reduces to an input, so it does not constitute circularity.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The central claim rests on standard concentration bounds and prior boosting and rejection-sampling lemmas. The only load-bearing ad hoc item is the unstated assumption that the weak learner's sample complexity is well-behaved under a logarithmic-factor change in the replicability parameter.

assumptions (6)

standard math Chernoff/Hoeffding concentration inequalities for sums of independent bounded random variables.
Used in Lemma 1.3 to bound the probability that the empirical average deviates from the expectation by a prescribed amount.
domain assumption Weak learner W is Theta(rho gamma^2)-replicable with advantage gamma and sample complexity mW.
This is the input model stated in Theorem 1.2; all replicability and error guarantees for the boosted hypothesis flow from this assumption.
domain assumption Servedio's smooth boosting iteration bound: for every kappa > 0 there is t = O(1/(kappa gamma^2)) with d(mu_t) < kappa.
Invoked in the proof of Theorem 1.4 to bound the number of iterations of Boost*; the paper explicitly does not repeat the proof and refers to Servedio [2001].
domain assumption Rejection sampling lemmas (Lemma 2.1 and Lemma 2.2) from Impagliazzo et al. [2022].
Used as black boxes to generate samples from the reweighted distribution D_mu and to compose replicability guarantees through rejection sampling.
ad hoc to paper The weak learner sample complexity mW grows at most polynomially or polylogarithmically in 1/rho, so replacing Theta(rho gamma^2/T) with Theta(rho gamma^2) is absorbed by ~O.
Needed for the final sample complexity in Theorem 1.2 as written; Lemma 2.6 only proves the first term with mW evaluated at Theta(rho gamma^2/T), with T = O(ln(1/epsilon)).
domain assumption The corrected sample complexity of the original Boost algorithm given in Footnote 1.
The improvement comparison in Section 1.1 depends on this asserted correction, which is attributed to personal communication rather than a public derivation.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Improved Replicable Boosting with Majority-of-Majorities." pith.science (2026). https://pith.science/paper/7UMNGXO3

@misc{pith2026250118388,
  author       = {Pith},
  title        = {Pith review of: Improved Replicable Boosting with Majority-of-Majorities},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7UMNGXO3}},
  note         = {Machine review of arXiv:2501.18388}
}

read the original abstract

We introduce a new replicable boosting algorithm which significantly improves the sample complexity compared to previous algorithms. The algorithm works by doing two layers of majority voting, using an improved version of the replicable boosting algorithm introduced by Impagliazzo et al. [2022] in the bottom layer.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

On the Structure of Replicable Hypothesis Testers
cs.DS 2025-07 conditional novelty 8.0 of 10

Replicable testers can be assumed to threshold a deterministic statistic against a random number, and this canonical structure yields improved sample-complexity bounds for several classic testing problems.

Reference graph

Works this paper leans on

16 extracted references · 14 canonical work pages · cited by 1 Pith paper

[1]

Ahmadi, S

S. Ahmadi, S. Bhandari, and A. Blum. Replicable online learning. arXiv preprint arXiv:2411.13730, 2024

arXiv 2024
[2]

M. Baker. Reproducibility crisis. nature, 533 0 (26): 0 353--66, 2016

work page 2016
[3]

P. Ball. Is ai leading to a reproducibility crisis in science? Nature, 624 0 (7990): 0 22--25, 2023

work page 2023
[4]

Barak, M

B. Barak, M. Hardt, and S. Kale. The uniform hardcore lemma via approximate bregman projections. In Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms, pages 1193--1200. SIAM, 2009

work page 2009
[5]

M. Bun, M. Gaboardi, M. Hopkins, R. Impagliazzo, R. Lei, T. Pitassi, S. Sivakumar, and J. Sorrell. Stability is stable: Connections between replicability, privacy, and adaptive generalization. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, page 520–527, New York, NY, USA, 2023. Association for Computing Machinery. ISBN ...

arXiv 2023
[6]

Dixon, J

P. Dixon, J. Vander Woude, and N. Vinodchandran. List and certificate complexities in replicable learning. Advances in Neural Information Processing Systems, 36, 2024

work page 2024
[7]

Dwork, G

C. Dwork, G. N. Rothblum, and S. Vadhan. Boosting and differential privacy. In 2010 IEEE 51st annual symposium on foundations of computer science, pages 51--60. IEEE, 2010

work page 2010
[8]

Eaton, M

E. Eaton, M. Hussing, M. Kearns, and J. Sorrell. Replicable reinforcement learning. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS '23, Red Hook, NY, USA, 2024. Curran Associates Inc

work page 2024

Show all 16 references

[9]

Esfandiari, A

H. Esfandiari, A. Karbasi, V. Mirrokni, G. Velegkas, and F. Zhou. Replicable clustering. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS '23, Red Hook, NY, USA, 2024. Curran Associates Inc

2024
[10]

Freund and R

Y. Freund and R. E. Schapire. A desicion-theoretic generalization of on-line learning and an application to boosting. In P. Vit \'a nyi, editor, Computational Learning Theory, pages 23--37, Berlin, Heidelberg, 1995. Springer Berlin Heidelberg. ISBN 978-3-540-49195-8

1995
[11]

Impagliazzo, R

R. Impagliazzo, R. Lei, T. Pitassi, and J. Sorrell. Reproducibility in learning. In Proceedings of the 54th annual ACM SIGACT symposium on theory of computing, pages 818--831, 2022

2022
[12]

Kalavasis, A

A. Kalavasis, A. Karbasi, K. G. Larsen, G. Velegkas, and F. Zhou. Replicable learning of large-margin halfspaces. In R. Salakhutdinov, Z. Kolter, K. Heller, A. Weller, N. Oliver, J. Scarlett, and F. Berkenkamp, editors, Proceedings of the 41st International Conference on Machi...

2024
[13]

M. Kearns. Learning boolean formulae or finite automata is as hard as factoring. Technical Report TR-14-88 Harvard University Aikem Computation Laboratory, 1988

1988
[14]

Kearns and L

M. Kearns and L. Valiant. Cryptographic limitations on learning boolean formulae and finite automata. Journal of the ACM (JACM), 41 0 (1): 0 67--95, 1994

1994
[15]

R. E. Schapire. The strength of weak learnability. Machine learning, 5: 0 197--227, 1990

1990
[16]

R. A. Servedio. Smooth boosting and learning with malicious noise. In D. Helmbold and B. Williamson, editors, Computational Learning Theory, pages 473--489, Berlin, Heidelberg, 2001. Springer Berlin Heidelberg. ISBN 978-3-540-44581-4

2001

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.

[1] [1]

Ahmadi, S

S. Ahmadi, S. Bhandari, and A. Blum. Replicable online learning. arXiv preprint arXiv:2411.13730, 2024

arXiv 2024

[2] [2]

M. Baker. Reproducibility crisis. nature, 533 0 (26): 0 353--66, 2016

work page 2016

[3] [3]

P. Ball. Is ai leading to a reproducibility crisis in science? Nature, 624 0 (7990): 0 22--25, 2023

work page 2023

[4] [4]

Barak, M

B. Barak, M. Hardt, and S. Kale. The uniform hardcore lemma via approximate bregman projections. In Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms, pages 1193--1200. SIAM, 2009

work page 2009

[5] [5]

M. Bun, M. Gaboardi, M. Hopkins, R. Impagliazzo, R. Lei, T. Pitassi, S. Sivakumar, and J. Sorrell. Stability is stable: Connections between replicability, privacy, and adaptive generalization. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, page 520–527, New York, NY, USA, 2023. Association for Computing Machinery. ISBN ...

arXiv 2023

[6] [6]

Dixon, J

P. Dixon, J. Vander Woude, and N. Vinodchandran. List and certificate complexities in replicable learning. Advances in Neural Information Processing Systems, 36, 2024

work page 2024

[7] [7]

Dwork, G

C. Dwork, G. N. Rothblum, and S. Vadhan. Boosting and differential privacy. In 2010 IEEE 51st annual symposium on foundations of computer science, pages 51--60. IEEE, 2010

work page 2010

[8] [8]

Eaton, M

E. Eaton, M. Hussing, M. Kearns, and J. Sorrell. Replicable reinforcement learning. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS '23, Red Hook, NY, USA, 2024. Curran Associates Inc

work page 2024