Pith. sign in

REVIEW 2 major objections 3 minor 2 cited by

Replicable Online Learning

T0 review · 2 major / 3 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read The paper constructs online algorithms that, on two independent samples from time-varying distributions, take the same action at every step with probability $1-\rho$, while keeping regret sublinear; it also proves near-matching lower…

desk verdict New and useful formalization of adversarial replicability for online learning, with a fixable but real concentration-bug in the key lemma. read the letter →

arxiv 2411.13730 v1 pith:XSGL2NGC submitted 2024-11-20 cs.LG

Saba Ahmadi , Siddharth Bhandari , Avrim Blum This is my paper · ORCID
classification cs.LG MSC 68W2768Q3268W20
keywords algorithmicreplicabilityonlinelearningexpertsproblemlinearoptimizationregretminimizationrandomizedroundinggeometricnoiselowerbounds
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

The paper asks whether an online learner can be replicable in a strong sense: run twice with the same internal randomness on two independently drawn input sequences, it must output the identical action at every time step with high probability. The authors propose a model in which an oblivious adversary chooses a distribution for each time step, generalizing both the standard adversarial online setting and the previously studied iid setting. They prove that replicability is achievable at sublinear regret for online linear optimization and the experts problem, give a generic conversion that turns any low-regret online learner into a replicable one, and prove lower bounds showing that the iid-replicable regret bound is nearly optimal. The central mechanism is to update decisions only at block boundaries and round cumulative cost vectors to a random grid (or add geometric noise), so that two close trajectories map to the same rounded decision.

What carries the argument

The load-bearing mechanism is block-deferred decisions plus randomized rounding of cumulative cost vectors. At block endpoints the algorithm rounds the cumulative cost vector to the unique point of a random grid (or, for the experts algorithm, adds geometric noise to each expert's cumulative cost), and then commits to the resulting action for the whole block. Replicability follows from a trajectory concentration lemma: two independent draws from the same product distribution have cumulative cost vectors within $O(\sqrt{tn})$ in $\ell^1$ norm with probability at least $1-\gamma$; if the rounding grid is coarse enough relative to this separation, both trajectories land on the same grid point and therefore select the same action. The memorylessness of geometric noise plays the same role in the experts setting, letting the algorithm reuse one noisy perturbation across many comparisons.

What would settle it

Set up an experts instance with $n=2$ and a distribution $D_t$ whose mean cost difference sits exactly on a grid boundary, run the algorithm from Theorem 4.6 on many independent pairs of samples for the prescribed block size and noise, and count how often the two runs disagree at any time step; a disagreement rate above $\rho$ would refute the replicability guarantee. Alternatively, directly check Lemma B.1 by drawing pairs of independent cost sequences whose per-step vectors have total magnitude 1 and seeing whether the cumulative $\ell^1$ difference ever exceeds the claimed $O(\sqrt{tn})$ envelope with probability greater than $\rho/(2T)$.

Watch

Extended reading notes

Core claim

On its own terms, the paper's central discovery is that adversarial replicability can be achieved together with sublinear regret, and that the cost of replicability can be quantified. Theorem 3.1 gives an adversarially $\rho$-replicable algorithm for online linear optimization with regret $\tilde{O}(D T^{5/6} n^{1/6} \rho^{-1/3})$; Theorem 4.6 gives an experts algorithm with regret $\tilde{O}(T^{5/6} \ln^{5/6}(n) \rho^{-1/3})$. Theorem 5.2 supplies a general conversion: any internal online learner can be wrapped in blocks and random-grid rounding to become adversarially $\rho$-replicable, with regret scaling as a block-dependent factor times the internal regret. Theorem 6.1 shows that in the iid setting the experts problem admits regret $O(\rho^{-1}(\log\log T)^2 \log(n \log\log T / \rho) \sqrt{T})$, which is optimal up to lower-order factors by Theorem 7.2; Theorem 7.3 gives the adversarial lower bound $\Omega(\sqrt{T\log n}/\rho)$. The message is that replicability is attainable in a best-of-both-worlds sense, with the iid and adversarial variants separated by a logarithmic factor in the number of experts.

Load-bearing premise

The load-bearing premise is that two independent draws from the same time-varying distributions have cumulative cost vectors that stay within about $\sqrt{tn}$ of each other with high probability, which requires per-round cost vectors with bounded total magnitude and independent (non-adaptive) draws; if that closeness fails, the grid-rounding and geometric-noise arguments no longer control the probability that the two runs pick different actions.

Editorial extensions

If this is right

  • For online linear optimization, there is a $\rho$-replicable algorithm with regret $\tilde{O}(D T^{5/6} n^{1/6} \rho^{-1/3})$.
  • For the experts problem, adversarial $\rho$-replicability can be achieved with regret $\tilde{O}(T^{5/6} \ln^{5/6}(n) \rho^{-1/3})$.
  • Any low-regret online learner can be converted into an adversarial $\rho$-replicable learner, with regret multiplied by a block factor that depends on $\rho$.
  • In the iid setting, the experts problem admits regret $O(\rho^{-1}(\log\log T)^2 \log(n \log\log T / \rho) \sqrt{T})$, and no algorithm can do better than $\Omega(\sqrt{T}/\rho)$ even with two experts.
  • Adversarial replicability costs an extra $\sqrt{\log n}$ factor in the lower bound, separating it from iid replicability.

Reading between the lines

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

  • The block-and-grid conversion is not tied to linear costs; any internal learner whose regret is defined against a fixed action set can be wrapped, so the same recipe should produce replicable versions of other full-information online problems.
  • If the adversarial lower bound of $\Omega(\sqrt{T\log n}/\rho)$ is tight, then the extra $\sqrt{n}$ factor in the linear-optimization upper bound is likely an artifact of the grid-rounding analysis rather than an intrinsic cost of replicability.
  • The trajectory-concentration step suggests a cleaner statistical view: replicability here is essentially a Lipschitz-stability property of the decision rule under $\ell^1$ perturbations of the cumulative cost vector, so one could try to design online learners that are inherently stable rather than rounding at block boundaries.
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.

Referee Report

2 major / 3 minor

Summary. The paper studies replicability in online learning. In the proposed model, an adversary chooses a sequence of input distributions D_1,...,D_T (obliviously), and an online learner is required to output the same action sequence with probability at least 1-rho when run twice on two independent draws from the product distribution, using the same internal randomness. The paper gives an adversarially rho-replicable algorithm for online linear optimization (FLLB), an adversarially rho-replicable algorithm for the experts problem (FTPLB*), a general framework for converting any online learner into an adversarially rho-replicable learner, an iid-replicable experts algorithm with near-optimal regret, and lower bounds, via the coin problem, for both iid and adversarial replicable regret minimization. The central claimed results are sublinear regret bounds that scale polynomially in rho^{-1}, T, and n, with a gap in the adversarial case that the paper leaves open.

Significance. If the bounds are correct, the paper makes a substantial contribution by extending algorithmic replicability from iid settings to time-varying and adversarial input distributions. The model is natural and the paper cleanly separates iid-replicability from adversarial replicability, a distinction that is missing from earlier online-replicability work. The general conversion framework is a useful abstraction, and the lower-bound reduction from the Impagliazzo et al. coin problem is principled. The proof skeletons for FLLB and FTPLB* are coherent and the main ideas, blocking and rounding or geometric noise, are well motivated. However, the exact parameter choices in several central theorems rely on a concentration lemma whose bounded-difference accounting is not correct as written, so the displayed settings are not justified; the asymptotic rates appear recoverable after a constant-factor correction.

major comments (2)
  1. [Appendix B, Lemma B.1; used in Theorem 3.1, Eq. (3)-(4), and Corollaries 5.3 and 5.6] The McDiarmid step in Lemma B.1 is not valid as written. The proof applies McDiarmid to f(u_1,...,u_t) with u_i = v_i - w_i and implicitly uses a bounded-difference constant of 2 per vector-valued u_i. But u_i always lies in the l1 ball of radius 2, so replacing u_i by u_i' can change f = ||sum_i u_i||_1 by as much as ||u_i - u_i'||_1, which can be 4. Under the proof's own u_i-variable formulation, the McDiarmid denominator should be at least 16t rather than 4t, giving a tail of order exp(-(c-2)^2 n / 8) rather than the displayed exp(-(c-2)^2 n / 2). In particular, the choice p = sqrt(2 log(2T/rho)) + 2 in Eq. (4) does not yield the claimed (2T/rho)^{-n} bound, and the displayed values of B in Theorem 3.1 and of m in Corollaries 5.3 and 5.6 are not justified as written. The asymptotic tilde-O rates survive if p is enlarged to, for example, sqrt(8 log(2T/rho)/n) + 2, so the issue is local in constants but it is load-bearing for the exact theorem statements.
  2. [Section 5.1, Lemma 5.1, Equations (12)-(15)] The alignment between blocks and the internal input sequence is off by one. At t=1, the condition 't-1 is a multiple of B' holds, but g'_{t-1-B} = g'_{-B} is undefined, and the first term of the sequence hat{S} in the proof is g_B, which is the grid point prepared at t=B+1, not at t=1. Equation (15) as written sums <a_u, g_{uB} - g'_{(u-1)B}> starting at u=1, but a_1 is not chosen from this input. The proof should start the internal-input sequence after the first block and add the first block's cost separately, or should redefine transition points as B+1, 2B+1, ... . This is repairable and does not change the claimed regret rate, but the equality between external and internal cost is not established as the lemma is currently written.
minor comments (3)
  1. [Appendix B, Lemma B.1 statement] The statement says 'distributions over the unit l1 ball in R^t', but the vectors v_i and w_i are n-dimensional; the domain should be R^n.
  2. [Theorems 5.2 and 5.5 and Corollaries 5.3 and 5.6] The theorem statements say the algorithms 'achieve cumulative regret Omega(B Reg_{T/B}(ALG_int))', but the proofs conclude an upper bound of 2B Reg_{T/B}(ALG_int). These should be O, not Omega.
  3. [Section 7.3, proof of Theorem 7.3] The first sentence of the proof says 'any iid rho-replicable algorithm', but the theorem is about adversarially rho-replicable algorithms; this typo should be corrected to avoid confusion.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the upper bounds are proved from stated concentration and memorylessness assumptions, and the lower bounds rest on an externally established coin-problem bound.

full rationale

The paper's derivations are self-contained with respect to circularity. The replicability algorithms (FLLB, FTPLB*, and the general framework) are constructed from blocking, random-grid rounding, and geometric noise, and their regret and replicability guarantees are derived, not fitted. The replicability proofs set parameters such as block size B, grid spacing epsilon, and noise level so that a union-bound/probability budget of rho is met; these are design choices with explicit formulas, not parameters fitted to the target claim. The general framework in Theorem 5.2 explicitly states its trajectory-concentration supposition as a hypothesis, rather than assuming the conclusion. Lower bounds in Theorems 7.2 and 7.3 invoke the external coin-problem sample-complexity bound of Impagliazzo et al. (2022), which is independent of the present authors and not a restatement of this paper's results. The McDiarmid constant concern noted in Lemma B.1, if valid, would be an internal correctness or proof-strength issue, not a circularity: the lemma is asserted with a proof rather than assumed from the conclusions. No equation is shown to be equivalent to another by construction, and no fitted input is renamed as a prediction.

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

The central algorithms depend on explicit protocol parameters, block sizes, grid spacings, and noise levels that are set in closed form in the theorems; no hidden fitted constants appear. The proofs rely on standard concentration inequalities, geometric memorylessness, and the cited coin-problem lower bound. No new physical or mathematical entities are postulated.

free parameters (3)
  • Block size B = B = (2( sqrt(2 log(2T/rho)) + 2 ) sqrt(nT) / rho)^{2/3} in Theorem 3.1; analogous formulas in Sections 4 and 5
    Explicit hyperparameter set in the proofs to balance replicability failure probability against regret; not fitted to data.
  • Grid spacing epsilon and noise parameters = epsilon = 1/sqrt(BT) for FLLB; epsilon = sqrt(ln n / (BT)) for FTPLB*; epsilon(i) = gamma / (2 alpha sqrt(P(i-1))) in…
    Closed-form choices in the theorem statements, selected to optimize the regret versus replicability tradeoff.
  • Algorithm 7 regret threshold K = K = 1000 (1/rho) (log log T)^2 log(n log log T / rho) sqrt(T)
    Chosen large enough that on iid inputs the algorithm does not switch to FTPL with high probability, and small enough to deliver the stated worst-case regret bound.
assumptions (6)
  • standard math McDiarmid's inequality and Blackwell's martingale concentration inequality
    Used to control deviations of cumulative costs from expectations in Sections 3, 4, 6, and Lemma B.1.
  • standard math Memorylessness of geometric random variables
    Used in Lemma 4.3, Theorem 4.6, and Theorem 6.1 to show that the best expert is stable across two trajectories after geometric noise.
  • domain assumption Bounded cost vectors and bounded action diameter
    Section 2 assumes unit l1 costs for online linear optimization, [0,1]^n costs for experts, and l1 diameter D for the action set; needed for concentration and regret bounds.
  • domain assumption Oblivious adversary fixing D_1,...,D_T in advance
    This is the definition of adversarial replicability in Section 2; adaptive adversaries that pick distributions based on past actions are outside the model.
  • standard math Coin problem sample-complexity lower bound of Impagliazzo et al.
    Used as a black box in Theorems 7.2 and 7.3 to prove the regret lower bounds; the paper does not reprove it.
  • domain assumption Full-information feedback
    The algorithms observe all expert costs or the full cost vector after each action; bandit or partial-information settings are explicitly left to future work.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Replicable Online Learning." pith.science (2026). https://pith.science/paper/XSGL2NGC

@misc{pith2026241113730,
  author       = {Pith},
  title        = {Pith review of: Replicable Online Learning},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XSGL2NGC}},
  note         = {Machine review of arXiv:2411.13730}
}
read the original abstract

We investigate the concept of algorithmic replicability introduced by Impagliazzo et al. 2022, Ghazi et al. 2021, Ahn et al. 2024 in an online setting. In our model, the input sequence received by the online learner is generated from time-varying distributions chosen by an adversary (obliviously). Our objective is to design low-regret online algorithms that, with high probability, produce the exact same sequence of actions when run on two independently sampled input sequences generated as described above. We refer to such algorithms as adversarially replicable. Previous works (such as Esfandiari et al. 2022) explored replicability in the online setting under inputs generated independently from a fixed distribution; we term this notion as iid-replicability. Our model generalizes to capture both adversarial and iid input sequences, as well as their mixtures, which can be modeled by setting certain distributions as point-masses. We demonstrate adversarially replicable online learning algorithms for online linear optimization and the experts problem that achieve sub-linear regret. Additionally, we propose a general framework for converting an online learner into an adversarially replicable one within our setting, bounding the new regret in terms of the original algorithm's regret. We also present a nearly optimal (in terms of regret) iid-replicable online algorithm for the experts problem, highlighting the distinction between the iid and adversarial notions of replicability. Finally, we establish lower bounds on the regret (in terms of the replicability parameter and time) that any replicable online algorithm must incur.

Figures

Figures reproduced from arXiv: 2411.13730 by the authors.

Figure 1
Figure 1. An illustration of the FLLB(ε, B) algorithm. The perturbed point c1:t−1 + p is uniformly random over a cube of side 1/ε with vertex at c1:t−1 (similarly for c ′ t−1 + p). In Theorem 3.1, we prove that by McDiarmid concentration bound, two different trajectories c1:t−1 and c ′ 1:t−1 are within a distance Ω(√ nT) with high probability, and they get mapped to the same grid point gt−1 with high probability. Algorithm 2 … view at source ↗
Figure 2
Figure 2. An illustration of the FTPLB algorithm. The blue and red boxes are corresponding to FTPLB and BTPL respectively. Theorem 3.4. Assume the maximum ℓ1 length of any cost vector c ∈ C is 1, and the ℓ1 diameter of the action set A is D. If c0 ∼ Unif([0, 1/ε] n ) then the expected regret of FTPLB(ε, B) in T steps satisfies: E[Reg] ≤ D(BεT + 1/ε) setting ε = 1/( √ BT) gives an expected regret at most D √ BT. Proof of Theor… view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

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

  1. 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.

  2. Improved Replicable Boosting with Majority-of-Majorities

    cs.LG 2025-01 conditional novelty 7.0 of 10

    A two-layer majority-voting boosting algorithm achieves the best-known sample complexity for replicable learning.

Reference graph

Works this paper leans on

15 extracted references · 12 canonical work pages · cited by 2 Pith papers

  1. [1]

    Kwangjun Ahn, Prateek Jain, Ziwei Ji, Satyen Kale, Praneeth Netrapalli, and Gil I. Shamir. Reproducibility in optimization: theoretical framework and limits. In Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS '22, Red Hook, NY, USA, 2024. Curran Associates Inc. ISBN 9781713871088

    work page 2024

  2. [2]

    1,500 scientists lift the lid on reproducibility

    Monya Baker. 1,500 scientists lift the lid on reproducibility. Nature, 533 0 (7604), 2016

    work page 2016

  3. [3]

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

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

    work page 2023

  4. [4]

    Large deviations for martingales

    D Blackwell. Large deviations for martingales. Festschrift for Lucien Le Cam: Research Papers in Probability and Statistics, pages 89--91, 1997

    work page 1997

  5. [5]

    Stability is stable: Connections between replicability, privacy, and adaptive generalization

    Mark Bun, Marco Gaboardi, Max Hopkins, Russell Impagliazzo, Rex Lei, Toniann Pitassi, Satchit Sivakumar, and Jessica Sorrell. Stability is stable: Connections between replicability, privacy, and adaptive generalization. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 520--527, 2023

    work page 2023

  6. [6]

    Replicable reinforcement learning

    Eric Eaton, Marcel Hussing, Michael Kearns, and Jessica Sorrell. Replicable reinforcement learning. Advances in Neural Information Processing Systems, 36, 2024

    work page 2024

  7. [7]

    Replicable bandits

    Hossein Esfandiari, Alkis Kalavasis, Amin Karbasi, Andreas Krause, Vahab Mirrokni, and Grigoris Velegkas. Replicable bandits. arXiv preprint arXiv:2210.01898, 2022

    arXiv 2022

  8. [8]

    Replicable clustering

    Hossein Esfandiari, Amin Karbasi, Vahab Mirrokni, Grigoris Velegkas, and Felix Zhou. Replicable clustering. Advances in Neural Information Processing Systems, 36, 2024

    work page 2024

Show all 15 references
  1. [9]

    User-level differentially private learning via correlated sampling

    Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. User-level differentially private learning via correlated sampling. Advances in Neural Information Processing Systems, 34: 0 20172--20184, 2021

    2021

  2. [10]

    Howard, Aaditya Ramdas, Jon McAuliffe, and Jasjeet Sekhon

    Steven R. Howard, Aaditya Ramdas, Jon McAuliffe, and Jasjeet Sekhon. Time-uniform chernoff bounds via nonnegative supermartingales. Probability Surveys, 17 0 (none), January 2020. ISSN 1549-5787. doi:10.1214/18-ps321. URL http://dx.doi.org/10.1214/18-ps321

    2020 doi

  3. [11]

    Reproducibility in learning

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

    2022

  4. [12]

    Efficient algorithms for online decision problems

    Adam Kalai and Santosh Vempala. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71 0 (3): 0 291--307, 2005

    2005

  5. [13]

    Statistical indistinguishability of learning algorithms

    Alkis Kalavasis, Amin Karbasi, Shay Moran, and Grigoris Velegkas. Statistical indistinguishability of learning algorithms. In International Conference on Machine Learning, pages 15586--15622. PMLR, 2023

    2023

  6. [14]

    On the method of bounded differences

    Colin McDiarmid. On the method of bounded differences. In J. Siemons, editor, Surveys in Combinatorics, volume 141 of London Mathematical Society Lecture Note Series, pages 148--188. Cambridge University Press, Cambridge, UK, 1989

    1989

  7. [15]

    Zhang, Nowell Closser, Anna L

    Kelly W. Zhang, Nowell Closser, Anna L. Trella, and Susan A. Murphy. Replicable bandits for digital health interventions, 2024

    2024

Pith tools

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