{"id":"1162179e-f95c-4c8c-91ce-4e32bf37adc4","arxiv_id":"2501.18388","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A two-layer majority-voting boosting algorithm achieves the best-known sample complexity for replicable learning.","lead":"Researchers from Aarhus University present a new boosting algorithm that combines many weak predictors into one strong predictor while guaranteeing the same output when rerun on fresh data. It needs significantly fewer samples than the previous best replicable boosting method.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 2.6 absorbs T=O(ln(1/epsilon)) into the argument of m_W; for arbitrary m_W the first term of Theorem 1.2 is not justified.","rationale":"I approached the paper as a black-box boosting result for an arbitrary replicable weak learner, with all claims expressed through m_W. The main construction is coherent: Lemma 2.3's potential argument yields error epsilon under the stated subroutine successes, Lemma 2.4 supplies the density needed for rejection sampling, and Lemma 2.5's replicability budget is consistent. The threshold check is a genuine improvement. The load-bearing weakness is not the algorithm but the final sample-complexity identity in Lemma 2.6. Because the theorem's headline is a quantitative improvement over the prior bound, an unjustified absorption of T into m_W's argument is serious. This is exactly the reader's weakest_assumption, so I agree with that diagnosis. With either a polynomial-growth assumption on m_W or a corrected theorem statement, the conditional verdict stands; nothing in my read pushes toward rejection.","tokens_in":14793,"tokens_out":19061,"duration_ms":183145,"concrete_test":"Re-derive Lemma 2.6 without the step that replaces m_W(Theta(rho gamma^2/T)) by m_W(tilde-Theta(rho gamma^2)). Then plug in a weak learner with m_W(rho)=2^(1/rho) and compare the exact first term of the total sample complexity with the first term claimed in Theorem 1.2. If the ratio is 2^(Theta(ln(1/epsilon)/(rho gamma^2))) (it is), the theorem is false as stated for general weak learners and must be amended with a polynomial-growth condition or a bound that keeps T inside m_W.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The advertised sample complexity is the central improvement, and Theorem 1.2 states it as tilde-O( m_W(tilde-Theta(rho gamma^2))/(epsilon gamma^2) + 1/(rho^2 epsilon gamma^3) ). In the proof, Lemma 2.6 first obtains a per-iteration Boost* complexity of O( ln(T/(rho gamma^2)) m_W(Theta(rho gamma^2/T))/gamma^2 + ... ) with T=O(ln(1/epsilon)), and then collapses the total to the statement above. The collapse moves T into the argument of m_W. Tilde-O may suppress polylog factors multiplying an expression, but it cannot change the evaluation point of an arbitrary function m_W. Concretely, if m_W(rho)=2^(1/rho), the proven first term is 2^(Theta(T/(rho gamma^2)))/(epsilon gamma^2), while the stated first term is 2^(Theta(1/(rho gamma^2)))/(epsilon gamma^2). These differ by 2^(Theta(ln(1/epsilon)/(rho gamma^2))), a super-polynomial gap in 1/epsilon. So Theorem 1.2 needs an explicit growth assumption on m_W (e.g., m_W(rho)=rho^{-O(1)}) or must retain T inside m_W. The algorithm's correctness and replicability proofs are otherwise coherent; the issue is in the final sample-complexity accounting.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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)).","tokens_in":15125,"tokens_out":26079,"duration_ms":208293,"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":[{"comment":"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.","section":"Section 2.1, Lemma 2.6 and Theorem 1.2"},{"comment":"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).","section":"Theorem 1.2 and Section 2.1"}],"minor_comments":[{"comment":"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.","section":"Algorithm 2, line 5"},{"comment":"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.","section":"Theorem 1.4, proof"},{"comment":"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.","section":"Notation"},{"comment":"There is a typo in the first sentence: 'sign ificantly' should be 'significantly'.","section":"Abstract"}],"recommendation":"major_revision","confidential_remarks":"The main theorem's sample complexity is the key selling point, so the gap in the m_W argument is important. The authors should also be asked to address the discrepancy between the stated and used weak-learner replicability parameter. I would not reject the paper, as the algorithmic framework is promising and the gap appears fixable by a more careful statement. The citation to an unpublished erratum about the prior work's sample complexity should be documented more fully."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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*.\n\nThe 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.\n\nA 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.\n\nThe 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.\n\nBottom 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.","headline":"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.","tokens_in":15586,"tokens_out":3068,"would_cite":true,"duration_ms":30401,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","68W20"],"pacs":[],"model":"deepseek-v4-flash","headline":"MetaBoost, a two-layer majority-vote booster, is proven to achieve the best-known sample complexity for replicable boosting.","keywords":["replicable boosting","sample complexity","majority-of-majorities","weak-to-strong learning","replicable threshold check","smooth boosting","AdaBoost","replicability"],"falsifier":"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.","tokens_in":14594,"feed_emoji":"🗳️","tokens_out":12663,"duration_ms":106463,"temperature":0.7,"pith_summary":"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.","feed_headline":"Majority-of-majorities boosting cuts replicable sample costs","feed_subtitle":"The two-layer scheme reaches the best-known sample cost for reproducible weak-to-strong learning.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines replicability and supplies the original replicable boosting algorithm, the rejection-sampling subroutine, and the statistical-query threshold check that this paper improves.","marker":"[Impagliazzo et al., 2022]"},{"why":"Provides the smooth-boosting framework and the iteration/correctness argument used by Booster* and by the density argument for MetaBoost.","marker":"[Servedio, 2001]"},{"why":"Supplies AdaBoost's exponential reweighting and the $O(\\ln(1/\\epsilon)/\\gamma^2)$ round complexity that the outer loop of MetaBoost mimics.","marker":"[Freund and Schapire, 1995]"},{"why":"Shows a smooth boosting algorithm with AdaBoost-level round complexity via Bregman projections; the paper argues making its projections replicable would cost more samples, motivating the chosen design.","marker":"[Barak et al., 2009]"},{"why":"Connects differential privacy and replicability, situating the result and explaining why a cheaper replicable booster would also cheapen replicable versions of private boosting.","marker":"[Bun et al., 2023]"}],"fun_headline_variants":["Two-layer majority vote reduces replicable boosting cost","Replicable boosting improved with majority-of-majorities","Majority-of-majorities cuts replicable sample complexity","Double majority voting lowers replicable boosting sample cost","New replicable boosting scheme uses majority-of-majorities"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Two-layer majority vote reduces replicable boosting cost","Replicable boosting improved with majority-of-majorities","Majority-of-majorities cuts replicable sample complexity","Double majority voting lowers replicable boosting sample cost","New replicable boosting scheme uses majority-of-majorities"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000512,"raw_usage":{"total_tokens":2417,"prompt_tokens":798,"completion_tokens":1619,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":414,"completion_tokens_details":{"reasoning_tokens":1542}},"tokens_in":414,"tokens_out":1619,"duration_ms":10902,"temperature":1.0,"reasoning_tokens":1542,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T23:41:10.903789+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}