{"id":"80ad280b-2157-490c-8ac4-e75f6a42be6c","arxiv_id":"2411.13730","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":3,"one_line_summary":"Introduces adversarially replicable online learning, with sublinear-regret algorithms for linear optimization and experts, plus regret lower bounds.","lead":"This paper defines a stronger form of reproducibility for online learning: a program run twice on independent random data should take the exact same sequence of decisions. It gives algorithms for online linear optimization and for learning from expert advice that meet this standard while keeping regret small, and it proves limits on how well any such algorithm can do.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma B.1's McDiarmid application uses bounded-difference constant 2 instead of 4, making the trajectory-concentration bound too strong; the displayed parameter settings in Theorems 3.1 and 5.2 are not justified as written.","rationale":"I read the paper in good faith. The central construction--blocking plus random rounding or geometric noise--is plausible, and the coin-problem reductions for the lower bounds are sound at a high level. The reader's conditional verdict is appropriate. My strongest additional concern is sharper than the reader's: it is not merely that Lemma B.1 requires bounded l1 costs and independence, but that the lemma as proved is quantitatively false because of the bounded-difference constant. This is a concrete internal inconsistency in a lemma that underpins Theorems 3.1, 5.2, and Corollaries 5.3 and 5.6. The gap appears fixable by increasing p by a constant factor, and the qualitative sublinear-regret claims likely survive, so I do not recommend rejection or a downgrade. I also noticed the off-by-one/causality issue in Lemma 5.1's reduction, but I did not select it as the single concern because Lemma B.1 is used more broadly and is already the reader's identified weak point.","tokens_in":32632,"tokens_out":35000,"duration_ms":261668,"concrete_test":"Recompute the bounded-difference constant for f(u)=||Sigma_i u_i||_1 in Lemma B.1: max over ||u_i||_1, ||u_i'||_1 <= 2 of |f(u)-f(u')| equals 4, not 2, yielding exponent n/8 instead of n/2. Then simulate n=1, t=10^6, Rademacher differences, T=t, rho=0.01, c=sqrt(2 log(2T/rho))+2, and estimate P(|Sigma_i(v_i-w_i)| > c sqrt(t)); if the estimate exceeds exp(-(c-2)^2/2), the lemma as stated is false. Finally, re-derive Theorem 3.1 with the n/8 exponent and verify that p=sqrt(8 log(2T/rho)/n)+2 restores rho-replicability with the same asymptotic regret bound.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing weakness is in Lemma B.1, which every grid-rounding replicability proof relies on. The lemma claims Pr[||Sigma_i(v_i-w_i)||_1 > c sqrt(tn)] <= exp(-(c-2)^2 n/2). Its proof sets u_i = v_i - w_i, f = ||Sigma_i u_i||_1, and applies McDiarmid with bounded-difference constant 2. But each u_i lies in the l1 ball of radius 2, so replacing u_i by u_i' changes f by at most ||u_i - u_i'||_1, which can be as large as 4. With c_i = 4, McDiarmid gives exp(-epsilon^2/(8t)), and after using E f <= 2 sqrt(tn) with epsilon=(c-2)sqrt(tn), the correct bound is exp(-(c-2)^2 n/8), a factor 4 weaker in the exponent. For n=1 with c = sqrt(2 log(2T/rho)) + 2, the true Rademacher large-deviation tail is roughly (rho/(2T))^{1/2}, not (rho/(2T)); Equation (4) in the proof of Theorem 3.1 and Equations (23)/(24) in Corollaries 5.3 and 5.6 therefore understate the non-replicability probability. The asymptotic ~O claims survive if p is enlarged to sqrt(8 log(2T/rho)/n)+2, but the theorem statements with the displayed B and epsilon, and the specific inequality (rho/(2T))^n <= rho/(2T), are not justified as written. This is an internal inconsistency in a central supporting lemma, not merely a disagreement with the surrounding literature.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":32968,"tokens_out":29440,"duration_ms":324168,"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":[{"comment":"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.","section":"Appendix B, Lemma B.1; used in Theorem 3.1, Eq. (3)-(4), and Corollaries 5.3 and 5.6"},{"comment":"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.","section":"Section 5.1, Lemma 5.1, Equations (12)-(15)"}],"minor_comments":[{"comment":"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.","section":"Appendix B, Lemma B.1 statement"},{"comment":"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.","section":"Theorems 5.2 and 5.5 and Corollaries 5.3 and 5.6"},{"comment":"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.","section":"Section 7.3, proof of Theorem 7.3"}],"recommendation":"major_revision","confidential_remarks":"The main technical problem is localized to Lemma B.1 and its downstream parameter displays. The high-level framework and the asymptotic claims are likely recoverable after a constant-factor correction, so I do not see a reason to reject. The manuscript fits the journal's scope, and I found no issues with citation practice or novelty disclosure. I recommend major revision so that the concentration lemma and the displayed parameter settings in Theorems 3.1, 5.2, 5.5, and their corollaries are repaired."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing you should know: this paper is the first to define adversarial replicability for online learning against time-varying product distributions, and it gives real algorithms with sublinear regret plus lower bounds. The main theorems—3.1, 4.6, 5.2, 7.2, 7.3—form a coherent picture: FLLB with blocking and random rounding, the geometric-noise experts variant, a general conversion framework, and an iid experts algorithm whose regret is near-optimal. The lower bounds via the coin problem are clean and correctly cited.\n\nThat said, there is a genuine technical bug in the concentration lemma everything rests on. Lemma B.1 claims a McDiarmid bounded-difference constant of 2, but each u_i = v_i - w_i has l1 norm up to 2, so changing one u_i can change ||sum u_i||_1 by up to 4. The correct exponent is (c-2)^2 n/8, a factor 4 weaker than stated. This invalidates the displayed choices of B and epsilon in Theorems 3.1 and 5.2 as written, and the specific inequality (rho/(2T))^n <= rho/(2T) only works for n >= 4 with the stated p. The asymptotic regret bounds survive if p is enlarged to sqrt(8 log(2T/rho)/n)+2, so this is a fixable flaw rather than a collapsed framework. I want it fixed before using the paper as a reference.\n\nOther issues are smaller: Theorem 5.2 says Omega(B Reg...) where it should be O; Algorithms 5, 6, and 7 have pseudocode defects, most notably an unbounded loop in Algorithm 7; and there are scattered typos. None of these affect the core existence arguments.\n\nVerdict: the central claims hold up modulo the Lemma B.1 fix. This is a serious thinker and the paper deserves a serious referee. I would advise the editor to send it out, but with a clear request that the authors correct the concentration bound and the pseudocode before acceptance.","headline":"New and useful formalization of adversarial replicability for online learning, with a fixable but real concentration-bug in the key lemma.","tokens_in":33543,"tokens_out":4220,"would_cite":true,"duration_ms":807852,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W27","68Q32","68W20"],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["algorithmic replicability","online learning","experts problem","online linear optimization","regret minimization","randomized rounding","geometric noise","lower bounds"],"falsifier":"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)$.","tokens_in":32399,"feed_emoji":"🔁","tokens_out":7299,"duration_ms":77499,"temperature":0.7,"pith_summary":"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.","feed_headline":"Two runs of an online learner can take identical actions","feed_subtitle":"New algorithms keep sublinear regret under time-varying input distributions, with matching lower bounds.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the Follow-the-Perturbed-Leader and Follow-the-Lazy-Leader algorithms that the new block-update variants modify and compare against.","marker":"[Kalai and Vempala, 2005]"},{"why":"Provides the coin-problem replicability lower bound used in Theorems 7.2 and 7.3.","marker":"[Impagliazzo et al., 2022]"},{"why":"Defines the earlier iid-replicable bandit setting that this paper generalizes and contrasts with adversarial replicability.","marker":"[Esfandiari et al., 2022]"},{"why":"Gives the concentration inequality that powers the trajectory lemma and the experts replicability proof.","marker":"[McDiarmid, 1989]"},{"why":"Introduces the notion of algorithmic replicability in parallel, providing part of the conceptual foundation for the paper's definitions.","marker":"[Ghazi et al., 2021]"},{"why":"Introduces reproducibility in optimization, another background notion of replicability that the online setting builds on.","marker":"[Ahn et al., 2024]"}],"fun_headline_variants":["Replicable online learning: identical actions, sublinear regret","Online algorithms that mirror their actions across runs","Adversarially replicable learners achieve low regret","Same actions twice: replicable online learning with bounds","Replicable experts: optimal regret under varying distributions"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Replicable online learning: identical actions, sublinear regret","Online algorithms that mirror their actions across runs","Adversarially replicable learners achieve low regret","Same actions twice: replicable online learning with bounds","Replicable experts: optimal regret under varying distributions"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000757,"raw_usage":{"total_tokens":3444,"prompt_tokens":1103,"completion_tokens":2341,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":719,"completion_tokens_details":{"reasoning_tokens":2265}},"tokens_in":719,"tokens_out":2341,"duration_ms":18150,"temperature":1.0,"reasoning_tokens":2265,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T15:58:35.851249+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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)$.","supporting_citations":[{"cited_title":"Reproducibility in learning","cited_arxiv_id":null,"evidence_quote":"Provides the coin-problem replicability lower bound used in Theorems 7.2 and 7.3."},{"cited_title":"On the method of bounded differences","cited_arxiv_id":null,"evidence_quote":"Gives the concentration inequality that powers the trajectory lemma and the experts replicability proof."},{"cited_title":"User-level differentially private learning via correlated sampling","cited_arxiv_id":null,"evidence_quote":"Introduces the notion of algorithmic replicability in parallel, providing part of the conceptual foundation for the paper's definitions."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces reproducibility in optimization, another background notion of replicability that the online setting builds on."}],"review_version":1}