acceptodds
Under review as a conference paper at ICLR 2027

When Predictions Become Supervision: Sharp Minimax Laws for Stochastic Replay

Abstract

When past predictors are reused to generate new training labels, each prediction shapes both current accuracy and future supervision. We study this feedback in online learning over thresholds with a fixed but unknown target. After an initial truthful round, an independent audit reveals the true label with probability , and otherwise an adversary-selected past predictor generates the feedback label. For horizons with fixed , we establish sharp minimax rates for every . At , the minimax cumulative loss is . Achieving this rate requires sacrificing some current accuracy to preserve future information, and this tradeoff is unavoidable even for improper learners. Restricting replay to sufficiently recent predictors on average reduces the loss to . For proper learners, revealing audit status or the selected replay source achieves the same rate. We further derive sharp rates for partial or noisy information about label generation and show that equally frequent disclosures can yield different minimax rates. Finally, with the replay source revealed but audit status hidden, fixing the reusable first predictor to raises the long-horizon loss from to .

Primary area:
learning theory
Keywords:
learning theory, online learning, model-generated supervision, stochastic replay, recursive learning

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_yCueOpenReview ↗
Rating
4(+1)
Confidence
3
Informativeness
2
Presentation
3(+1)
Soundness
3
Read review
Paper summary

The paper studies online threshold learning in which, with probability 1−ρ1-\rho, labels are generated by an adversary-chosen past predictor of the learner, and it derives sharp minimax rates for all ρ\rho when T≤K1/2−εT\le K^{1/2-\varepsilon}, with Θ(min⁡{T,T2/3(log⁡K)1/3})\Theta(\min\{T,T^{2/3}(\log K)^{1/3}\}) at ρ=1/2\rho=1/2. The upper bound comes from clipped exponential weights, and the matching lower bound from a "two-clock" construction that forces the learner either to pay while misleading predictors are built or to be misled when they are replayed.

Critical strengths
  1. The two-clock lower bound is new and tight, settles an open question from Dmitriev et al. (SODA 2026), and its technique looks reusable for other self-generated-feedback settings.
  2. Section 4 clearly quantifies how replay age, audit flags and source disclosure reduce the loss, which is useful for thinking about provenance signals in synthetic-data pipelines.
Critical weaknesses
  1. The headline rate relies on a strong adversary that knows the target, chooses replays based on the true label and reaches back Θ(T)\Theta(T) rounds, and it holds only for T≤K1/2−εT\le K^{1/2-\varepsilon}, which limits what it says about model collapse.
  2. The real contribution sits in the appendix, with no simulations and no link to practices such as soft pseudo-labels or sampling temperature, which limits the paper's impact at ICLR.
Questions for authors
  1. What is the rate at ρ=1/2\rho=1/2 when the replay distribution does not depend on the target? A super-log⁡K/ρ\log K/\rho lower bound would strengthen the motivation and could raise my rating.
  2. Is the K\sqrt K horizon limit intrinsic, or an artifact of the construction?
  3. Can the claim that the rate "requires sacrificing current accuracy" be stated as a theorem, or should the abstract be reworded?
  4. For ρ>1/2\rho>1/2, what is new relative to existing results on online learning with noisy labels?
7 comments
AuthorsOpenReview ↗

Thank You for Your Feedback (Part 1/4)

Thank you for your careful reading and constructive feedback. We apologize for the delay. We took additional time to establish a new super-logarithmic lower bound for target-independent replay distributions, directly addressing your first question. We are encouraged by your assessment that the two-clock lower bound is "new and tight” and that its technique "looks reusable for other self-generated-feedback settings.” We address your comments below.


Q1. What is the rate at ρ=1/2\rho=1/2 when the replay distribution does not depend on the target? A super-log⁡K/ρ\log K/\rho lower bound would strengthen the motivation and could raise my rating.

A: Thank you for this suggestion. We prove a new super-logarithmic lower bound even when the replay distribution is fixed in advance and depends only on time. At ρ=1/2\rho=1/2, we establish

R_T^{\mathrm{time}}(K,1/2) \ge c\min\left\\{ T,\\,[\min\\{T,K\\}\log K]^{1/4} \right\\}.

For (log⁡K)3≪T≤K(\log K)^3\ll T\le K, this gives Ω((Tlog⁡K)1/4)=ω(log⁡K)\Omega((T\log K)^{1/4})=\omega(\log K). The lower bound holds even for improper learners. The replay policy does not access the target or depend on the inputs and feedback. The input adversary retains the original model's target-aware freedom. We further prove that the original sharp critical rate remains unchanged when the fixed target-independent replay distribution may depend on the input:

RTinput(K,1/2)=Θε(min⁡T,T2/3(log⁡K)1/3),T≤K1/2−ε.R_T^{\mathrm{input}}(K,1/2) = \Theta_\varepsilon\left( \min\\{T,T^{2/3}(\log K)^{1/3}\\} \right), \qquad T\le K^{1/2-\varepsilon}.

Our proof extends the two-clock construction. The learner must first create two historical predictors through its own actions. Hidden source assignments then make the feedback distributions nearly indistinguishable with constant probability. For the time-only result, we schedule all potential source-pair tests in advance. Both lower bounds account for the cost of creating the replay sources. We have added both new results as Theorems 3.8 and 3.9, with complete proofs in Appendix S. They show that target-aware source selection is not necessary for super-logarithmic replay loss. As in our original model, the replay distribution remains hidden. Theorem S.1 shows that knowing its actual conditional probabilities instead permits logarithmic loss.


Q2: Is the K\sqrt K horizon limit intrinsic, or an artifact of the construction?

A: Thank you for this question. The horizon restriction comes from our current lower-bound construction, while the upper bound holds for every horizon. The two-clock construction requires

(m+1)22d≤K,(m+1)^2 2^d\le K,

where mm controls the construction of two replay sources and dd counts the unresolved target bits. To keep m=Θ(T)m=\Theta(T) and d=Θε(log⁡K)d=\Theta_\varepsilon(\log K) feasible, we impose T≤K1/2−εT\le K^{1/2-\varepsilon}. Our results also provide a lower bound beyond this range. Corollary N.1 establishes, for every K,TK,T in the proper model,

R_T(K,1/2)\gtrsim \min\left\\{ T,\left[T^2\log\left(1+\frac{K}{T^2}\right)\right]^{1/3} \right\\}.

In particular, the lower bound is Ω(K1/3)\Omega(K^{1/3}) for all T≥KT\ge\sqrt K. At T≍KT\asymp\sqrt K, the current upper bound is O(K1/3(log⁡K)1/3)O(K^{1/3}(\log K)^{1/3}). Thus, the square-root restriction is not a proven phase transition, and determining the sharp rate beyond it remains open. We have brought this all-horizon proper comparison from Appendix N into Eq. (5) to clarify the scope of Theorem 3.1.

AuthorsOpenReview ↗

Thank You for Your Feedback (Part 2/4)

Q3. Can the claim that the rate “requires sacrificing current accuracy” be stated as a theorem, or should the abstract be reworded?

A: Thank you for this suggestion. Yes. We now state a theorem proving that this tradeoff is necessary on our hard instances. Let BB be the expected loss during source construction. At ρ=1/2\rho=1/2, our two-clock lower bound gives

\mathbb{E}L_T \ge B+c\min\left\\{ m,\frac{dm^2}{B^2} \right\\}.

In the enhanced probe experiment of Appendix P, we further construct a proper learner with zero construction loss. Its two stored predictors output zero and one on the subsequent test inputs. The adversary can then make both possible target labels produce identical Bern⁡(1/2)\operatorname{Bern}(1/2) feedback. This forces Ω(m)\Omega(m) expected testing loss. Conversely, let r=(dm2)1/3r=(dm^2)^{1/3}. For any fixed CC and m/dm/d sufficiently large depending on CC, any learner achieving at most CrCr total loss must incur B=ΩC(r)B=\Omega_C(r) during source construction. This holds even for improper learners. Thus, the tradeoff is not specific to our clipped algorithm. We have added Theorem 3.6 and its proof in Appendix P.5, including the zero-construction-loss example. The fraction above is interpreted as +∞+\infty when B=0B=0. We have also replaced the abstract claim with:

On hard instances, achieving the optimal rate requires accepting prediction errors while creating replay sources to avoid larger future losses. This necessity holds even for improper learners.


Q4: For ρ>1/2\rho>1/2, what is new relative to existing results on online learning with noisy labels?

A: Thank you for this question. The upper bound O(log⁡K/(2ρ−1)2)O(\log K/(2\rho-1)^2) follows from classical bounded-noise online learning [1]. Our contribution is a matching lower bound under self-generated replay and a sharp characterization of the transition near ρ=1/2\rho=1/2.

Theoretical aspectPrior noisy-label learningOur result
Feedback mechanismNoise distributions are chosen from an allowed channel family [1, 2].Starting with an empty archive, replay must use predictors already deployed by the learner.
Minimax lower boundHard noise channels need not be constructed through the learner's actions.Our matching lower bound accounts for the cost of creating replay sources and applies even to improper learners.
Near-critical behaviorThe classical gap-dependent bound becomes uninformative as ρ→1/2\rho\to1/2.At criticality, the loss has order T2/3(log⁡K)1/3T^{2/3}(\log K)^{1/3}. Our bounds also locate the sharp transition to this sublinear regime.

Specifically, Theorem 3.1 establishes, for T≤K1/2−εT\le K^{1/2-\varepsilon} and ρ>1/2\rho>1/2,

R_T(K,\rho)\asymp_\varepsilon R_T^{\mathrm{imp}}(K,\rho) \asymp_\varepsilon \min\left\\{ T,\\, T^{2/3}(\log K)^{1/3},\\, \frac{\log K}{(2\rho-1)^2} \right\\}.

For T≫log⁡KT\gg\log K, the transition occurs at 2ρ−1≍(log⁡K/T)1/32\rho-1\asymp(\log K/T)^{1/3}. Unlike general bounded-noise models, where feedback can become entirely uninformative at ρ=1/2\rho=1/2, self-generated replay still permits a sublinear minimax rate. We have made this distinction explicit in the discussion of Theorem 3.1 and in Section 7.

References

[1] S. Ben-David, D. Pál, and S. Shalev-Shwartz. Agnostic Online Learning. COLT, 2009.

[2] C. Wu, A. Grama, and W. Szpankowski. Information-theoretic Limits of Online Classification with Noisy Labels. NeurIPS, 2024.

AuthorsOpenReview ↗

Thank You for Your Feedback (Part 3/4)

Q5: The headline rate relies on a strong adversary that knows the target, chooses replays based on the true label and reaches back Θ(T)\Theta(T) rounds, and it holds only for T≤K1/2−εT\le K^{1/2-\varepsilon}, which limits what it says about model collapse.

A: Thank you for raising this concern. We establish a new super-logarithmic lower bound without target-dependent replay selection. At ρ=1/2\rho=1/2, even a replay distribution fixed in advance and depending only on time satisfies

R_T^{\mathrm{time,imp}}(K,1/2) \ge c\min\left\\{ T,\\,[\min\\{T,K\\}\log K]^{1/4} \right\\}.

For (log⁡K)3≪T≤K(\log K)^3\ll T\le K, this yields Ω((Tlog⁡K)1/4)=ω(log⁡K)\Omega((T\log K)^{1/4})=\omega(\log K). The result holds against improper learners. Source selection depends neither on the target nor on the current input. The input adversary retains the original model's target-aware freedom. We further recover the original sharp critical rate under fixed target-independent replay kernels that may depend on the input:

RTinput(K,1/2)=Θε(min⁡T,T2/3(log⁡K)1/3),T≤K1/2−ε.R_T^{\mathrm{input}}(K,1/2) = \Theta_\varepsilon\left( \min\\{T,T^{2/3}(\log K)^{1/3}\\} \right), \qquad T\le K^{1/2-\varepsilon}.

Replay age remains an important distinction. Theorem 4.2 shows that bounded expected replay age reduces the minimax loss to Θ(min⁡T,log⁡K/ρ)\Theta(\min\\{T,\log K/\rho\\}) for fixed DD. Corollary G.5 further shows that the original polynomial lower bound requires D+1=Ω((T/log⁡K)2/3)D+1=\Omega((T/\log K)^{2/3}). This establishes the need for growing replay age without claiming that Θ(T)\Theta(T) is necessary. The horizon restriction applies to our sharp characterization rather than to all lower bounds. Appendix N already proves Ω(K1/3)\Omega(K^{1/3}) loss for T≥KT\ge\sqrt K. Our new time-only lower bound also holds for every horizon. We have added both new results as Theorems 3.8 and 3.9, with complete proofs in Appendix S. We have also clarified the scope of our conclusions. They concern worst-case learning under hidden replay rather than inevitable model collapse in practical training.


Q6: The real contribution sits in the appendix, with no simulations and no link to practices such as soft pseudo-labels or sampling temperature, which limits the paper's impact at ICLR.

A: Thank you for this helpful suggestion. We have expanded the main-text explanation of the matching bounds and conducted three controlled simulation studies. The experiments connect the theory to soft pseudo-labels and sampling temperature. They show how clipping can reduce cumulative loss and how fresh sampling can remain costly even when the replay source is known.

(1) Main-text explanation of the matching bounds. Sections 3.2 and 3.3 present the clipped upper bound in Proposition 3.2 and the two-predictor lower bound in Proposition 3.5, respectively. At ρ=1/2\rho=1/2, the upper bound balances the prediction cost αT\alpha T against the learning cost (log⁡K)/α2(\log K)/\alpha^2. The lower-bound construction starts from an empty history and induces two replay sources through the learner's own predictions. It balances the loss incurred in producing these sources against the difficulty of learning from their reuse. Remark 3.2 and Theorem 3.6 explain how these tradeoffs yield matching rates.

Section 5 isolates the cost of fresh sampling when the replay source is known. The variance term c(1−c)c(1-c) in Theorem 5.1 motivates the soft-label and temperature comparisons below.

All tables report mean cumulative deployment loss ±\pm the half-width of a 95% Monte Carlo confidence interval. Comparisons across conditions use paired random streams.

(2) Clipping and future information. We simulate the enhanced lower-bound construction from Appendix K at ρ=1/2\rho=1/2, including its disclosed construction branches and completed test bits. The learner uses clipped predictions and Bayesian updates. A separate pilot selects the clipping level, which is then evaluated on 4,096 fresh runs.

Horizon TTSelected α\alphaNo clippingSelected clippingLoss reduction
12,28812{,}28800842.1±31.8842.1 \pm 31.8842.1±31.8842.1 \pm 31.80.00.0\\%
49,15249{,}1520.030.033,270.3±126.53{,}270.3 \pm 126.53,030.9±62.93{,}030.9 \pm 62.97.37.3\\%
196,608196{,}6080.030.0313,286.4±505.913{,}286.4 \pm 505.98,978.6±127.38{,}978.6 \pm 127.332.432.4\\%
786,432786{,}4320.020.0251,936.9±2,012.051{,}936.9 \pm 2{,}012.024,036.8±350.724{,}036.8 \pm 350.753.753.7\\%

At the largest tested horizon, clipping reduces cumulative loss by 53.7%, with a paired bootstrap 95% interval of 52.6% to 54.9%. At the smallest horizon, the pilot selects no clipping. The comparison illustrates how preserving future information can offset the immediate prediction cost of clipping.

Reviewer_CkMJOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

This paper studies the following online learning setting with stochastic replays, which is a follow-up to Dmitriev et. al. 2026 (which focused on replays that are not fresh random samples). The problem is this: let the domain be a finite set of KK point on the line, and a binary hypothesis class corresponding to threshold functions. At each point in time t=1,2,…t = 1, 2, \ldots

  • the learner chooses a predictor pt:X→[0,1]p_t : \mathcal{X} \to [0,1]
  • an adversary selects an instance xtx_t
  • the learner incurs loss ℓt=∣pt(xt)−f(xt)∣\ell_t = |p_t(x_t) - f(x_t)|, where ff is the underlying threshold function
  • with probability ρ\rho, the learner observes the label f(xt)f(x_t)
  • with probability 1−ρ1 - \rho, the adversary can (randomly) select a past predictor pSp_S and reveal a label drawn from Ber(pS(xt))\mathrm{Ber}(p_S(x_t)).

This paper determines the minimax risk RT=∑ℓtR_T = \sum \ell_t for certain regimes of KK, TT, and ρ\rho.

Critical strengths

This paper studies a fairly interesting setting. The rates given by Theorem 3.1 are somewhat surprising (I’m not sure what I would’ve expected, but it wouldn’t really have been these rates). The paper also makes an intriguing claim: for example, they summarize in the conclusions that “the analysis identifies a fundamental tradeoff between prediction accuracy and the informativeness of future supervision”.

Critical weaknesses

The main issue for me is that the paper does not help a reader understand the problem/results. The structure and exposition also read unnaturally technical, in a way that seems to give too much emphasis about secondary details, without giving any intuition for how the algorithms or analysis works/what is hard. The authors note that they used LLMs to help with language revisions; to be honest, it feels like there is too much LLM writing, which is unfortunately making a pretty interesting problem rather impenetrable.

  1. A claim that is made repeatedly is that there is a “tradeoff between current accuracy and preserving future information” (e.g. line 170). But this is not obvious, nor is it ever justified in the paper. I can imagine at least two extreme settings: ρ=0\rho = 0 meaning that the learner essentially receives no data, and so the best thing to do is play the minimax optimal strategy pt≡1/2p_t \equiv 1/2. On the other hand, if ρ=1\rho = 1, then the learner should run the Halving algorithm, guaranteeing a mistake bound of log⁡K\log K. So, I can see that the fraction of replay, controlled by ρ\rho, affects what sort of strategy the learner should use. But in this case, the issue does not seem to be about current accuracy versus preserving future information (I also don’t understand what it means to preserve future information). Is it possible to use these two extremes to illustrate this tradeoff you mention?
  2. Can you explain what this means: the “difficulty depends on both the feedback generated by past predictions and the loss incurred while producing those predictions” (line 150).
  3. It seems that the main result is Theorem 3.1. However, there isn’t any satisfying interpretation (Remark 3.1 is not particularly clarifying). Why are there phase changes? Why is ρ=1/2\rho = 1/2 the critical rate? What does it mean to not be able to “eliminate the excess truthful signal”? Why is TT bounded by K1/2−εK^{1/2 - \varepsilon} in this theorem?
  4. Line 182 states that the upper bound is constructed by modifying a strategy by Dmitriev et. al. (2026). But I don’t understand why the described algorithm should work. In particular, if I were the adversary, I would just set h∗≡1h^* \equiv 1, and let xt=K−tx_t = K - t. And since the learning algorithm always predicts zero, it makes a mistake at every single point in time, getting a Ω(T)\Omega(T) mistake bound instead of a O(log⁡K)O(\log K) bound.
  5. I think the algorithms achieving the upper bounds of Theorem 3.1 should be in the main paper. Also it seems that a minimax algorithm would need to know KK, TT, and ρ\rho. There was a mention of anytime valid algorithm somewhere in the appendix (which I assume means you don’t know TT in advance). That sounds quite interesting, and perhaps should replace some of the later sections of the paper.
  6. In line 212, the authors write “This argument extends to any finite binary class admitting a proper predictor that outputs 1/2 everywheere”. Are you saying that the results for the threshold generalizes to all finite hypothesis classes? If so, that would be worth formalizing in the main paper, instead of as a side comment.
  7. From Section 4.2 on, I don’t really see how these results are contributing to the central question of how replay makes learning hard or how it affects how a learner should strategize. The setting where the audit information is revealed just seems to basically be the non-replay setting (indeed, Theorem 4.2 shows this). Can you say more about what these sections (4.2 on) are telling us about the problem? As far as I can tell from, at least the main body, they seem to be fairly unsurprising corollaries of Theorem 3.1.
  8. Heavy editing is needed. A lot of the sentences are not very comprehensible. For example, just selecting at random, consider: “The adversary induces two actual predictors and reuses them to test dd unresolved branch bits along a balanced search-tree path, with mm setting the time scale of construction and reuse” (line 216). I have no idea what this means, “search-trees” were never introduced before; what are “actual predictors”?
Questions for authors

Please see previous sections for question. I recommend a weak reject: the problem and model are interesting, but I don’t think the paper has managed to convey what the results mean. The writing needs major revision.

5 comments
AuthorsOpenReview ↗

Thank You for Your Feedback (Part 1/4)

Thank you for your careful reading and constructive feedback. We apologize for the delay. We took extra time to substantially rewrite the manuscript in response to your concerns, with particular attention to improving the intuition and accessibility of our results. All revisions are marked in blue. We appreciate your assessment that the paper studies a "fairly interesting setting” and that the rates in Theorem 3.1 are "somewhat surprising.” Your comments have helped us rethink how to communicate the central ideas and contributions of this work. We address your specific comments below.


Q1: A claim that is made repeatedly is that there is a “tradeoff between current accuracy and preserving future information”. But this is not obvious, nor is it ever justified in the paper. What does it mean to preserve future information? Is it possible to use the two extremes, ρ=0\rho=0 and ρ=1\rho=1, to illustrate this tradeoff?

A: Thank you for pointing out that this central idea needs a clearer explanation. We agree that the two extremes illustrate different learning strategies rather than the tradeoff itself. The tradeoff arises because current predictions become sources of future feedback. Restricting these predictions can preserve information about the true target but may increase current prediction loss. At ρ=0\rho=0, no further truthful audits occur after the first round, and predicting 1/21/2 throughout guarantees loss T/2T/2. At ρ=1\rho=1, all feedback is truthful and Halving achieves O(log⁡K)O(\log K) loss.

The tradeoff becomes clear at the fixed rate ρ=1/2\rho=1/2. Suppose two earlier predictors output 00 and 11 at the same input. Replaying the zero predictor when the true label is 11 produces Bern⁡(1/2)\operatorname{Bern}(1/2) feedback. Replaying the one predictor when the true label is 00 produces exactly the same distribution. The learner cannot distinguish these cases from such feedback. To prevent this cancellation, the learner can restrict all deployed prediction probabilities to [α,1−α][\alpha,1-\alpha]. This preserves a feedback-mean separation of at least α\alpha, but may increase current loss by up to α\alpha per round. More generally, the guaranteed signed separation is

γ=2ρ−1+2(1−ρ)α.\gamma=2\rho-1+2(1-\rho)\alpha.

At ρ=0\rho=0, no positive separation can be guaranteed. At ρ=1\rho=1, the separation is one without clipping. At ρ=1/2\rho=1/2, it equals α\alpha, making the tradeoff explicit. Proposition 3.2 quantifies this tradeoff at ρ=1/2\rho=1/2:

E[LT]≤12+α(T−1)+4log⁡Kα2.\mathbb{E}[L_T] \le \frac12+\alpha(T-1)+\frac{4\log K}{\alpha^2}.

Balancing the prediction cost against the cost of learning from weaker feedback yields T2/3(log⁡K)1/3T^{2/3}(\log K)^{1/3}. Importantly, the matching lower bound in Theorem 3.1 shows that this minimax cost is unavoidable even for improper learners. The adversary can replay only predictors previously deployed by the learner. Our lower bound accounts for both the loss incurred while producing these predictors and the difficulty of learning when they are reused. We have incorporated this explanation into the Introduction and Section 3 to clarify the meaning and theoretical basis of the tradeoff.


Q2: Can you explain what this means: the “difficulty depends on both the feedback generated by past predictions and the loss incurred while producing those predictions” (line 150)?

A: Thank you for pointing out this unclear statement. The key difficulty is that the adversary cannot introduce arbitrary replay sources. It must use predictors previously deployed by the learner, and the loss incurred while producing them also counts. Our lower bound captures this through two phases. The first phase uses two unpredictable stopping times to select earlier predictors. Most labels favor zero in the first selection process and one in the second. If the learner keeps its construction loss small, the selected predictors must therefore have scores close to zero and one at the relevant test queries, with constant probability. For proper thresholds, monotonicity extends this control to the later test points.

In the second phase, the adversary reuses these predictors to obscure unresolved target labels. At ρ=1/2\rho=1/2, the feedback distributions under labels zero and one then have a separation of at most O(Lbuild/m)O(L_{\mathrm{build}}/m) on the event above, where LbuildL_{\mathrm{build}} is the expected construction loss. Repeating the tests across dd unresolved target bits yields

\mathbb{E}[L_T] \ge L_{\mathrm{build}} + c\min\left\\{ m,\frac{d}{(L_{\mathrm{build}}/m)^2} \right\\}.

AuthorsOpenReview ↗

Thank You for Your Feedback (Part 2/4)

Thus, reducing the loss of producing replay sources makes their later feedback harder to distinguish. Avoiding this difficulty instead incurs loss during source construction. We have replaced the original sentence with:

The adversary can replay only predictors previously deployed by the learner. Our lower bound shows that the learner must incur substantial loss either while producing these predictors or when their later reuse makes feedback difficult to distinguish.


Q3: It seems that the main result is Theorem 3.1. However, there isn't any satisfying interpretation (Remark 3.1 is not particularly clarifying). Why are there phase changes? Why is ρ=1/2\rho=1/2 the critical rate? What does it mean to not be able to “eliminate the excess truthful signal”? Why is TT bounded by K1/2−εK^{1/2-\varepsilon} in this theorem?

A: Thank you for this comment. We agree that Remark 3.1 needs a clearer explanation of the rates. The critical value ρ=1/2\rho=1/2 determines whether adversarial replay can eliminate the guaranteed distinction between the two true labels. For a past predictor's score z∈[0,1]z\in[0,1], the feedback mean is ρy⋆+(1−ρ)z\rho y^\star+(1-\rho)z. Its possible values lie in [0,1−ρ][0,1-\rho] under label zero and [ρ,1][\rho,1] under label one. When ρ>1/2\rho>1/2, these intervals remain separated by 2ρ−12\rho-1 regardless of the replay source. This unavoidable gap is what we call the “excess truthful signal.” At ρ=1/2\rho=1/2, the intervals touch. Below 1/21/2, they overlap, allowing replay to cancel the label information once suitable historical predictors are available.

This also explains the three minimax regimes. Clipping all deployed scores to [α,1−α][\alpha,1-\alpha] guarantees a signed feedback separation

γ=2ρ−1+2(1−ρ)α.\gamma=2\rho-1+2(1-\rho)\alpha.

For γ>0\gamma>0, Proposition 3.2 gives expected loss O(αT+(log⁡K)/γ2)O(\alpha T+(\log K)/\gamma^2). At ρ=1/2\rho=1/2, balancing the two terms yields T2/3(log⁡K)1/3T^{2/3}(\log K)^{1/3}. Above 1/21/2, setting α=0\alpha=0 gives the additional cap O(log⁡K/(2ρ−1)2)O(\log K/(2\rho-1)^2). Below 1/21/2, clipping must first overcome the negative offset 2ρ−12\rho-1, producing the additional linear term (1−2ρ)T(1-2\rho)T. The transition occurs around ∥2ρ−1∥≍(log⁡K/T)1/3\|2\rho-1\|\asymp(\log K/T)^{1/3}. Our matching lower bounds establish these minimax rates.

The restriction T≤K1/2−εT\le K^{1/2-\varepsilon} comes from the matching lower-bound construction, not the upper-bound algorithm. The construction requires (m+1)22d≤K(m+1)^2 2^d\le K. For T≳εlog⁡KT\gtrsim_\varepsilon\log K, the restriction allows m=Θ(T)m=\Theta(T) while preserving d=Θε(log⁡K)d=\Theta_\varepsilon(\log K) unresolved target bits. Shorter horizons are handled by a separate balanced-tree lower bound. We have revised Remark 3.1 and the all-horizon discussion immediately after it to explain these phase changes and the role of the horizon condition more clearly.


Q4: Line 182 states that the upper bound is constructed by modifying a strategy by Dmitriev et al. (2026). But I don't understand why the described algorithm should work. In particular, if h⋆≡1h^\star\equiv 1 and xt=K−tx_t=K-t, wouldn't the algorithm always predict zero and incur Ω(T)\Omega(T) mistakes instead of an O(log⁡K)O(\log K) bound?

A: Thank you for this concrete example. Your calculation is correct for the zero-initialized conservative strategy. However, this strategy proves the O(K/ρ)O(K/\rho) upper bound in Theorem Q.1, not an O(log⁡K)O(\log K) bound. In your example, every new query lies to the left of the updated cutoff. The zero-initialized strategy therefore incurs loss TT for T≤K−1T\le K-1. Its symmetric version, initialized at the constant-one predictor, incurs zero loss. Randomizing between the two gives expected loss T/2T/2 in your example, consistent with the rate Θδ(min⁡T,K/ρ)\Theta_\delta(\min\\{T,K/\rho\\}) in Theorem Q.1.

The bound follows by counting certified updates. Whenever the zero-initialized strategy predicts zero, all earlier predictors also output zero at that input. Thus, feedback one certifies a true positive and moves the cutoff left. Each mistake after the first round triggers such an update with probability ρ\rho. Since the cutoff decreases at most K−a⋆K-a^\star times, the expected cumulative loss is at most (K−a⋆)/ρ(K-a^\star)/\rho. The symmetric strategy gives (a⋆−1)/ρ(a^\star-1)/\rho. A fair initial randomization therefore yields

E[LT]≤K−12ρ,\mathbb{E}[L_T]\le\frac{K-1}{2\rho},

as proved in Appendix O. We have clarified this argument there and in the discussion of Theorem Q.1 in Appendix Q. Section 3 distinguishes this all-horizon guarantee from the clipped exponential-weights algorithm used for Theorem 3.1.

AuthorsOpenReview ↗

Thank You for Your Feedback (Part 3/4)

Q5: I think the algorithms achieving the upper bounds of Theorem 3.1 should be in the main paper. Also it seems that a minimax algorithm would need to know K,T,ρK,T,\rho. There was a mention of an anytime valid algorithm in the appendix. That sounds quite interesting, and perhaps should replace some of the later sections of the paper.

A: Thank you for this suggestion. We now present the upper-bound algorithm and its parameter choices more clearly in Section 3.2. The model assumes that K,T,ρK,T,\rho are known. The finite-horizon algorithm uses TT to select its clipping level, but advance knowledge of TT is not always necessary. Starting from p1≡1/2p_1\equiv 1/2 and uniform weights over the KK thresholds, the learner deploys

pt(x)=αt+(1−2αt)∑a≤xwt(a)p_t(x)=\alpha_t+(1-2\alpha_t)\sum_{a\le x}w_t(a)

and updates its weights using the observed feedback with learning rate γt/2\gamma_t/2, where γt=2ρ−1+2(1−ρ)αt>0\gamma_t=2\rho-1+2(1-\rho)\alpha_t>0. Nonincreasing clipping levels ensure that all earlier predictors satisfy the current score bounds. For ρ>1/2\rho>1/2, the upper bound compares the unclipped algorithm with a clipping level of order (log⁡K/T)1/3(\log K/T)^{1/3}. For ρ<1/2\rho<1/2, clipping starts above (1−2ρ)/(2(1−ρ))(1-2\rho)/(2(1-\rho)) and adds a horizon-dependent margin. The constant-half predictor handles cases where the required clipping level is infeasible. The anytime algorithm in Appendix J achieves the critical rate without knowing TT in advance. At ρ=1/2\rho=1/2, choosing

\alpha_t=\min\left\\{ \frac14, \left(\frac{\log K}{t}\right)^{1/3} \right\\}

guarantees O(min⁡T,T2/3(log⁡K)1/3)O(\min\\{T,T^{2/3}(\log K)^{1/3}\\}) loss for every horizon. We have brought this result into the main text as Corollary 3.3, alongside the algorithm, and condensed the later technical exposition to make room.


Q6: In line 212, the authors write “This argument extends to any finite binary class admitting a proper predictor that outputs 1/2 everywhere”. Are you saying that the results for thresholds generalize to all finite hypothesis classes? If so, that would be worth formalizing in the main paper, instead of as a side comment.

A: Thank you for this suggestion. The upper bound extends to every finite binary class admitting a proper constant-1/21/2 predictor, but the matching minimax rate need not hold for every class. Specifically, suppose there exists a distribution ν\nu over H\mathcal H satisfying Eh∼νh(x)=1/2\mathbb{E}_{h\sim\nu}h(x)=1/2 for every input xx. Mixing the current hypothesis weights with ν\nu preserves properness under clipping. The potential argument does not require the ordering of thresholds. Corollary I.3 establishes that for all T≥1T\ge1 and ρ∈[0,1]\rho\in[0,1],

RT(H,ρ)≤C,rρ(T,∥H∥),R_T(\mathcal H,\rho)\le C\\,r_\rho(T,\|\mathcal H\|),

where rρr_\rho is defined in Theorem 3.1. This upper bound is tight in the worst case over such finite classes. Corollary I.4 shows that thresholds attain the worst-case rate for T≤∥H∥1/2−εT\le\|\mathcal H\|^{1/2-\varepsilon}, although individual classes can be easier. We now state both results formally in Corollary 3.3 and keep their proofs in Appendix I.


Q7: From Section 4.2 on, I don't really see how these results contribute to the central question of how replay makes learning hard or affects the learner's strategy. The audit-information setting seems essentially equivalent to non-replay learning. Are these results simply corollaries of Theorem 3.1?

A: Thank you for highlighting this gap in the exposition. Sections 4–5 examine which information can overcome the difficulty of replay and how the learner's past predictions affect its value. We agree that revealing audit flags provides a natural benchmark. However, this is not equivalent to receiving truthful feedback every round. Audits still occur only with probability ρ\rho, while deployment loss is incurred on every round. The resulting rate is Θ(min⁡T,(log⁡K)/ρ)\Theta(\min\\{T,(\log K)/\rho\\}), rather than Θ(min⁡T,log⁡K)\Theta(\min\\{T,\log K\\}) under fully truthful feedback.

A more important distinction is that source information can replace audit flags without identifying truthful rounds. Theorem 4.1 achieves the same rate by deploying binary predictors from the first round. Knowing the selected source allows the learner to subtract the replay contribution from feedback. The resulting learning signal has mean proportional to ρ\rho and second moment O(ρ)O(\rho). This explains why the learner's choice of earlier predictions matters, even when source information is available.

Reviewer_chNtOpenReview ↗
Rating
2
Confidence
3
Informativeness
3
Presentation
1
Soundness
3
Read review
Paper summary

In recent work, to model learners in a situation wherein labels may be synthetically generated from past versions of it, Dmitriev et al. proposed a certain model of online learning with a replay adversary, wherein the learner commits to a predictor hth_t in each round, and the adversary controls not only the context xtx_t, but may also the feedback via the option to reveal hs(xt)h_s(x_t) for some s<ts < t instead of the true label yty_t. This prior paper penalised only mistakes made when the ground truth was not revealed, and established that thresholds form a certain natural hard case for the problem (therein, by characterising optimal numbers of mistakes in terms of certain variations of the threshold dimension).

The submission studies a probabilistic version of this problem, with audits. The main presentation focuses on the domain X=[1:K−1]\mathcal{X} = [1:K-1], with the class of interest being the thresholds ha(x)=1x≥ah_a(x) = 1\\{x \ge a\\}. In each round, the learner picks a score function pt:X→[0,1]p_t : \mathcal{X} \to [0,1], where ptp_t is monotone for proper learners, and arbitrary for improper. The adversary selects a single true threshold h\*h_\* obliviously, and in each round selects a prior round StS_t---this StS_t is itself modeled to be drawn from a distribution over [1:t−1][1:t-1] which can depend on everything except the randomness used by the learner. Independently, a ρ\rho-audit coin is tossed. If this is coin is heads, the learner observes the true label y∗_t=h\*(xt)y^*\_t = h_\*(x_t), while if tails, the learner observes a draw from Bern(pSt(xt)\mathrm{Bern}(p_{S_t}(x_t). Either way, the observation is called YtY_t. In each round, the learner suffers a cost of ℓt(p,y∗)=∣pt(xt)−y∗_t∣\ell_t(p, y^*) = |p_t(x_t) - y^*\_t|.

In the first part of the paper, a characterisation of minimax costs is given when T≤K1/2−ϵT \le K^{1/2 -\epsilon} for some ϵ>0\epsilon > 0.

The upper bound arises thus:

  • The learner maintains weights on the thresholds, and sets rt(x)r_t(x) as the expected prediction according to the weights.
  • Then, the prediction pt=α+(1−2α)rtp_t = \alpha + (1-2\alpha) r_t is given. This linearly clips rtr_t to lie in the interval [α,1−α][\alpha, 1-\alpha].
  • Finally, weights are updated according to hedge on the basis of the observation YtY_t. The key insight is that, because of the clipping, the bias of the adversary's choice of pStp_{S_t} remains far from 00 and 11, which in turn means that the expectation of the feedback when y∗y^* is 00 or 11 are separated from one another by at least γ:=(2ρ−1)+2(1−ρ)α\gamma := (2\rho -1) + 2(1-\rho)\alpha. So long as γ>0\gamma> 0 (since we need to know the bias to upweight the right predictors), this gives enough signal to drive the hedge routine to low-regret. The overall bound is of the form Tα+log⁡(K)/γ2T\alpha + \log(K)/\gamma^2, as long as γ>0\gamma > 0. Then, if 2ρ−1>0,2\rho - 1 > 0, one can set α=0\alpha = 0 to get log⁡(K)/(1−ρ)2\log(K)/(1-\rho)^2 regret. If 2ρ=1,2\rho = 1, one balances αT\alpha T with log⁡(K)/α2\log(K)/\alpha^2 to get T2/3T^{2/3} regret. Finally, if (2ρ−1)<0,(2\rho - 1) < 0, then α\alpha must be set nontrivially high, and one gets a bound of (1−2ρ)T+T2/3,(1 - 2\rho ) T + T^{2/3}, the latter term from optimising α,\alpha, the former due to it's large floor. Naturally, this analysis extends to arbitrary finite classes of predictors.

This is complemented by a matching lower bound when T≤K1/2−ϵT \le K^{1/2 - \epsilon}. The lower bound construction is poorly explained in the main text. A high level the picture is thus (the details are intricate): each threshold is attached to a number k.k. Say K0=(m+1)22d≤KK_0 = (m+1)^2 2^d \le K. Divide [1:K0][1:K_0] into (m+1) contiguous blocks, and then each block into (m+1) blocks. Put a geometric prior on which block has the ground truth, so that the learner cannot commit easily. Then, go through the top level blocks in order, giving a pivot corresponding to one of the end-points, and simply reveal whether the truth lies in that block or not. Then do the lower level blocks, but in reverse order. The point of all this is thus: in predicting at each block, the learner can either try to "commit", or not. If it does commit, then there is a nontrivial chance that it eats a big cost. If it does not commit, then it must produce a prediction that is far from both 0 and 1. As long as we are thinking about proper learners, this is a resource, because a the learner must reveal a monotone prediction function each time. So, if the learner was committing throughout, we get a rich set of prediction functions to obfuscate the feedback later, whereas if it was not committing, we get a big cost directly. The two-level nesting is so that the outer blocks can induce a gap from 00, and the inner ones from 11, which is ensured by reversing the order. In order to use this obfuscation resource, turn to the 2d2^d functions in this block. Here, give a uniform prior within this block (conditionally), and pick xtx_t in the middle of the current run (a la binary search). Then the loss imposed through this depends on the obfuscation strength, and the cost (in terms of ρ\rho and this strength) to reveal dd bits, where the feedback for each bit is obfuscated as above through ρ\rho. The condition T≤K1/2−ϵT \le K^{1/2 - \epsilon} is needed to let m22dm^2 2^d fit into [1:T][1:T] (mm is set to cTcT, dd to O(ϵ)log⁡(K)O(\epsilon) \log(K).)

In addition, the authors offer a characterisation of the regret when ρ\rho is bounded below 1/31/3. Herein, the chief observation is that one can always learn with O(K/ρ)O(K/\rho) regret by running the conservative scheme of Dmitriev et al., and that for general TT this is tight. Again, the condition on ρ\rho arises because of the lower bound.

The bulk of the remainder of the paper studies variations on the feedback and obfuscation that make it easier to learn in the presence of such replay adversaries. A number of settings are considered (with some intuition for the upper bound given below):

  • When the audit flag is revealed: here, a versioning based idea is proposed, and the bound drops to O(log⁡(K)/ρ)O(\log(K)/\rho).
  • If instead of being revealed directly, some noisy channel output depending on the status of the audit coin is given, then a cost log⁡(K)/(ρ2J),\log(K)/(\rho^2 J), where JJ is the Le Cam divergence between the two feedback laws. This is instead based on a version of hedge, the key resource being that one can reduce the variance of the hedge loss by exploiting this weaker information.
  • If the learner instead is simply told if pSt≥1/2p_{S_t} \ge 1/2 or <1/2<1/2, then a bound of O(log⁡(K)/ρ)O(\log(K)/\rho) arises. The idea is to use the median predictor according to the hedge law instead of the smooth prediction. Since the resulting ptp_t values all lie in $\{0,1\}, knowing the bias of the adversary reveals the adversarie's choice of label, which can be used to center the feedback better, and thus reduce the variance of the hedge loss significantly.
    • In the final section of the paper, the paper revisits this case, but under the extra restriction that the very first prediction must be flat with bias c∈[0,1]c \in [0,1]. Here, it is found that the minimax costs are (1/ρ+(1−ρ)c(1−c)/ρ2)log⁡(K),(1/\rho + (1-\rho) c(1-c)/\rho^2) \log(K), so for cc bounded away from the end points, scales as log⁡(K)/ρ2\log(K)/\rho^2. This arises because the adversary can use this cc to obfuscate always, inflating feedback variance.
  • A case wherein the adversary's bias is revealed, but only in non-audit rounds is considered. When this is revealed on all non-audit rounds, the costs are similar. However, if information is revealed only on a qq-fraction of such rounds, the regret grows to log⁡(K)/qρ2\log(K)/q \rho^2 (when q<3/4,q < 3/4, say). This is in contrast to if any of the above results are similarly slowed down with such a qq, wherein the costs only get multiplied by 1/q1/q (notice the ρ\rho v/s ρ2\rho^2).
  • If the adversary is constrained to picking a recent StS_t, in the sense of a certain expected delay being ≤D\le D, then a bound of O(Dlog⁡(K)/ρO( D \log(K)/\rho arises. Here the idea is to operate in phases of length CD/ρ,C D/\rho, where in a long period in each phase one plays a known predictor, so that in the remaining rounds one roughly knows the bias of the adversary feedback, which can again be used to center the feedback.

All of these results are accompanied by lower bounds. These also include terms from the previous result, and so are stated in terms of the same constraint on small TT. However, the new terms arise mostly from just the binary search phase at the end. The details of how information is revealed in this bit, of course, vary depending on the feedback.

Critical strengths

This is an interesting paper. The replay adversary model is an elegant, if stylised, way to study synthetically generated feedback found in the wild, and the probabilistic extension is bound to be of interest to the learning theory and online learning communities at ICLR. The authors do a comprehensive job of studying the problem in various feedback scenarios, and derive certain interesting insights about the role of various types of feedback. The upper bounds are mostly based on a simple idea of using hedge, but well executed. The nested first-phase construction in the lower bound for Thm 3.1 is both clever and insightful, even though it loses pertinence for large TT. The generic construction underlying Thm 3.2 also operationalises the extrinsic threshold dimension well.

Critical weaknesses

Let me get the concern about T≤K1/2−ϵT \le K^{1/2 - \epsilon} out of the way first: for sure, this is a restriction, but I think for the concerns of the paper, this is not terribly important. In part this is because a tight characterisation is anyway offered for the hard case of ρ<1/3.\rho < 1/3. Given that the easy case of ρ>1/2\rho > 1/2 has log⁡(K)\log(K) regret, the only question potentially left open is if the (1−2ρ)−2(1-2\rho)^{-2} dependence here is tight for large TT. This is, on the whole, fine.

The main problem of the paper is its exposition and length. Note that the appendix of this paper occupies 70 pages. This is, obviously, extremely long, even when taking into account that theory papers often include 20-30 page appendices. Given conference reviewing timelines, the expectation, at least in ML venues, is that the main paper supplies the key steps and intuitions underlying their results, and further supplies enough context to reduce the remaining technical results to be reduced to standard approaches in the literature. In more plain language, the main ideas must be presented and be clear, and it is okay to have dependence on standard technical tools. These issues are doubly important when the appendix is very very large.

However, this paper chooses a very different tack. The main ideas are stated in a highly compressed way, using technical language developed in the paper, which perhaps renders the explanations the authors offer short, but equally makes them opaque. As a result, I think the paper does not supply enough intuition. There are two substantial grouses

  • First, the lower bound construction and intuition is extremely compressed to the point of incomprehensibility. In fact, even the appendix leaves this somewhat hard to understand.
  • Second, a key background intuition underlying the upper bounds of Section 4 is missing from the main text, which makes the explanations given in the text appear very terse and hard to understand. Additionally, I find the order in which the results are given somewhat strange.

Overall: I will justify the above opinions below, but let me discuss the overall view I have. I think the paper is clearly interesting and insightful. However, it hits itself in the foot significantly by doing a poor job of explaining its ideas. This immediately means that at best I can only recommend acceptance weakly. Now, if I simply think about what is best for the work (in my opinion, of course), I think that it should just be rewritten: this would substantially improve its readership, if nothing else. But such a rewrite will be significant (in journal terms it'd be a 'major revision'), so cannot be accommodated within the conference system. As a result I weakly recommend a rejection: the results are certainly good enough for any premier ML venue, but the exposition needs significant work.


  • Lower bounds: Consider, for example, line 216-246, which deal with the main lower bound. This is the key result underlying the headline result of Thm 3.1(the upper bound here being much more standard). One would thus hope that this exposition gives me a clear understanding of the construction underlying this lower bound, including how the adversary might exploit past choices made by the learner. Instead, this proceeds thus:

    • 216-218: we first get a line saying that "two actual predictors are induced". I don't understand what it means to induce a predictor, or what makes them actual. Then we're told there's a tree involved, and "time scale of construction and reuse", which, without the protocol defining the adversary, is meaningless.
    • 219-226: Then we get an intermediate statement, from which the form of Thm. 3.1 is to be derived.
    • 226-239: Then we get an explanation with unknown terms: what is the lower-bound experiment that induces this loss? Why do the scores approach extremes (and what are extremes, you can just say {0,1})? What is a test interval, and what does it mean to extend control from source-selection points to it? I could go on.
    • 240-246: Then we get statements involving enhancements of an experiment we haven't been told about. Finally, the authors tell us how to set the parameters in Prop. 3.4 to arrive at the lower bound of Thm. 3.1.

    At no point does this actually tell us what on earth is going on under the hood. We are invited to consider appendices O and V, and that's cool and all, but it is your job as an author to tell the reader the fundamental idea in terms that they can understand without going and reading the 9 odd pages of these appendices.

    In fact, let me mention that even these appendices don't do a good job of explaining the construction and the underlying tools. For instance, large parts of the terminology arise from auxiliary lemmas (MUCH!) earlier in the appendix. For example, section O repeatedly talks about testing, but imagine that your reader saw the pointer to section O in the main text, and went to it directly (as I indeed did). They have no clue what that means (since it wasn't used in the main text), and no pointer to what section to go read about this. Further, important details of the construction are needlessly compressed --- it took me like 5 minutes to simply parse section O.1, for instance, while it is obvious (once parsed) that one can draw a simple 3-panel figure which explains what is going on in like 30 seconds.

  • Upper bounds: In terms of upper bound in section 4, I understand that the key resource being used is that you can use the feedback to drive hedge with losses depending on (Yt−μ^t)(Y_t - \hat\mu_t) instead of (Yt−1/2)(Y_t - 1/2) for some notion of μ^\hat\mu depending on the feedback, the point being that this maintains separation under the two ground truth scenarios, and that the better centering of the observations reduces the variance of the loss, which in turn speeds up the hedge learning. This is the key way in which 1/ρ1/\rho instead of 1/ρ21/\rho^2 dependence arises, and how one can avoid having to clip the hedge output. This bias and variance motif is used at least a couple of times as explanation, but observe that this background understanding of how, say, the ratio of these terms lead to the hedge regret is never explained, and as a result a reader cannot connect this to the bound directly. This is strange because it is very easy to state something like this as a lemma in the main text: it can even go in section 3. I think introducing something like this, and then repeatedly pointing to it in the rest of the exposition can make section 4 a lot lot less mysterious---once the penny drops, a lot of this is straightforward. A couple of other things: the results mix the versioning based scheme and the better centred hedge into the same results, which is strange, and that it is strange to discuss the bounded delay case first, because the idea underlying the scheme is better illustrated by talking about what happens if you know the adversary bias first (because essentially that's what is being engineered for Thm 4.1).

Questions for authors
6 comments
AuthorsOpenReview ↗

Thank You for Your Feedback (Part 1/5)

Thank you for your careful reading and constructive feedback. We apologize for the delay. We took extra time to substantially rewrite the relevant sections of the original manuscript in response to your suggestions. All revisions are marked in blue. We are greatly encouraged by your assessment that the paper is “clearly interesting and insightful” and that “the results are certainly good enough for any premier ML venue.” We address your specific comments below.


Q1: On lines 216–218, the paper states that “two actual predictors are induced” without explaining what it means to induce them or why they are called actual. The text then introduces a tree and a “time scale of construction and reuse” without first describing the adversary's construction, making these terms difficult to understand.

A: Thank you for pointing out this lack of clarity. We agree that the original passage introduces several concepts before explaining the underlying construction. The two predictors are functions previously deployed by the learner, not functions supplied by the adversary. The adversary selects them through two geometric stopping rules and later replays them to make the remaining target labels difficult to distinguish.

We have replaced the original passage in Lines 216–218. The revised explanation in Section 3.3 and Appendix K is summarized below:

The lower bound begins by partitioning the candidate thresholds into two nested levels of blocks. The adversary then performs two scans, one through the outer blocks and another through the inner blocks in reverse order. Each scan uses a truncated geometric stopping rule with stopping probability 1/m1/m. The prediction functions deployed by the learner at the two stopping rounds become the replay sources. The first scan usually presents label zero, while the second usually presents label one. The stopping-time argument shows that, unless the learner incurs substantial loss during these scans, the selected predictors have low and high scores, respectively, at the later test queries in the sense required by the lower-bound analysis. If both scans stop, the adversary replays these predictors while repeatedly querying midpoints of the remaining block, which contains 2d2^d candidate thresholds. These queries test the dd unresolved binary decisions needed to identify the target. The two scans use at most 2m2m rounds, and the subsequent tests use at most another mm rounds. The target threshold is fixed before interaction.

This revision explains how the two replay sources arise from the learner's actual actions, why the nested tree is needed, and what the time parameter mm controls. We have also distinguished the proper and improper lower-bound arguments in the subsequent explanation. The former uses monotonicity to control the selected predictors throughout the remaining block, while the latter uses randomized query probes to obtain the required control across the testing levels.


Q2: Lines 219–239 present an intermediate proposition before explaining the underlying lower-bound construction. What is the lower-bound experiment that produces this loss? Why do the prediction scores approach the extremes 00 and 11? What is the test interval, and how does monotonicity extend score control from the source-selection points to the later test points?

A: Thank you for these detailed comments. We agree that the original passage states the lower bound before adequately explaining how the construction works. The two extreme scores arise from the opposite prediction-loss incentives in two geometric scans. Avoiding substantial loss during these scans produces historical predictors whose replay makes the remaining target labels difficult to distinguish.

We have reorganized the discussion around Lines 219–239, moving the construction and its intuition before Proposition 3.5. The revised discussion in Section 3.3 and Appendix K makes the following points:

Consider first the construction for proper threshold learners. In the first geometric scan, the true label is usually zero and becomes one when the scan stops. In the reversed second scan, the true label is usually one and becomes zero at the stopping round. With stopping probability α=1/m\alpha=1/m, the conditional expected losses for prediction scores qq and rr are α+(1−2α)q\alpha+(1-2\alpha)q and α+(1−2α)(1−r)\alpha+(1-2\alpha)(1-r), respectively. Thus, unless the learner incurs substantial loss during these scans, the stopping-time argument yields a low-score predictor plop^{\mathrm{lo}} and a high-score predictor phip^{\mathrm{hi}} on an event of constant probability.

AuthorsOpenReview ↗

Thank You for Your Feedback (Part 2/5)

The remaining candidate thresholds form a contiguous block containing 2d2^d cutoffs. Its internal midpoints are the subsequent test queries. The first stopping query lies to the right of this block, while the second lies to its left. Since proper threshold predictions are nondecreasing, plo(x)≤qIp^{\mathrm{lo}}(x)\le q_I and phi(x)≥rJp^{\mathrm{hi}}(x)\ge r_J at every internal midpoint xx, where qIq_I and rJr_J are the scores at the two stopping queries. Writing LbuildL_{\mathrm{build}} for the expected loss during the scans, the stopping-time analysis gives plo(x)+1−phi(x)=O(Lbuild/m)p^{\mathrm{lo}}(x)+1-p^{\mathrm{hi}}(x)=O(L_{\mathrm{build}}/m) simultaneously at these midpoints on the same constant-probability event.

At ρ=1/2\rho=1/2, the adversary replays plop^{\mathrm{lo}} under true label one and phip^{\mathrm{hi}} under true label zero. The resulting feedback distributions are Bern⁡((1+plo(x))/2)\operatorname{Bern}((1+p^{\mathrm{lo}}(x))/2) and Bern⁡(phi(x)/2)\operatorname{Bern}(p^{\mathrm{hi}}(x)/2). Both approach Bern⁡(1/2)\operatorname{Bern}(1/2) when the construction loss is small. Sequential testing across the dd unresolved binary decisions then incurs additional expected loss of order min⁡m,dm2/Lbuild2\min\\{m,dm^2/L_{\mathrm{build}}^2\\}. Balancing this with the construction loss yields the critical lower bound (dm2)1/3(dm^2)^{1/3}. For improper learners, the proof replaces monotonicity with independent query probes that control the historical scores on a constant fraction of testing levels in expectation. For other audit rates, the feedback gap also depends on 2ρ−12\rho-1, and source mixing can eliminate the gap when ρ<1/2\rho<1/2 and the historical scores are sufficiently separated.

This revision explains the source of the extreme scores, identifies the previously undefined test interval, and shows how the construction produces the matching lower bound. It also clarifies the distinction between the proper construction in Appendix K and the improper lower bound in Appendix P, which underlies Proposition 3.5.


Q3: Lines 219–226 present an intermediate proposition before explaining the lower-bound construction. Lines 240–246 then introduce “enhancements of an experiment we haven't been told about” and proceed directly to the parameter choices in Proposition 3.4 that yield the lower bound of Theorem 3.1.

A: Thank you for pointing out this gap in the exposition. The enhanced experiment gives the learner additional information while preserving the underlying lower-bound construction. We agree that the original text introduces this experiment and the parameter choices before explaining their roles.

We have reorganized the discussion around Lines 219–246. After introducing the two-scan construction, we have moved the explanation of the enhanced experiment before Proposition 3.5. The explanation is summarized below:

To prove the lower bound, we consider a stronger learner that receives additional information from a genie. During the two scans, the genie reveals the current tree node before prediction and identifies the child containing the target only after the current loss. During subsequent testing, each unresolved branch is revealed only after all predictions and feedback at that level. Thus, the learner receives additional information without knowing the current hidden decision before incurring its losses. The stopping times and branch bits are sampled at the outset and determine one fixed target threshold. The replay sources remain predictors previously deployed by the learner, and the independent audit mechanism is unchanged. Since the lower bound holds even for this stronger learner, it also holds under the original protocol.

We now explain the parameter choices after the lower-bound statements, with the full calculation in Lemma L.2. The derivation is as follows:

The two scans use at most 2m2m rounds, and the dd testing levels require at most d⌊m/d⌋≤md\lfloor m/d\rfloor\le m additional rounds. Thus, the construction fits within 3m≤T3m\le T rounds. The two nested levels of blocks, each with m+1m+1 possibilities, leave 2d2^d candidate thresholds in the selected block, requiring (m+1)22d≤K(m+1)^2 2^d\le K. For Cεlog⁡K≤T≤K1/2−εC_\varepsilon\log K\le T\le K^{1/2-\varepsilon}, choosing m=⌊T/6⌋m=\lfloor T/6\rfloor and d=min⁡⌊m/2⌋,⌊log⁡2(K/(m+1)2)⌋d=\min\\{\lfloor m/2\rfloor,\lfloor\log_2(K/(m+1)^2)\rfloor\\} gives m=Θ(T)m=\Theta(T) and d=Θε(log⁡K)d=\Theta_\varepsilon(\log K). Hence, the critical lower bound (dm2)1/3(dm^2)^{1/3} becomes Θε(T2/3(log⁡K)1/3)\Theta_\varepsilon(T^{2/3}(\log K)^{1/3}). The remaining audit regimes follow from the corresponding bounds in Proposition 3.5, while shorter horizons use the balanced-tree lower bound.

We have also clarified that Appendix K uses monotonicity for proper learners, whereas Appendix P uses independent query probes for improper learners. Both arguments preserve the same timing of the additional genie disclosures.

AuthorsOpenReview ↗

Thank You for Your Feedback (Part 3/5)

These revisions make the enhanced experiment and its role explicit before the formal lower-bound statement, while keeping the parameter derivation immediately after it. They also explain how the construction yields Theorem 3.1 without requiring readers to reconstruct the argument from the appendices.


Q4: Even Appendices O and V do not adequately explain the lower-bound construction and its underlying tools. Important terminology, particularly “testing,” is introduced in earlier auxiliary lemmas without sufficient explanation or cross-references. Section O.1 is also unnecessarily compressed. A simple three-panel figure could make the construction much easier to understand.

A: Thank you for this helpful suggestion. We agree that readers should be able to follow the construction directly from Appendix K without first navigating earlier technical lemmas. We have added the suggested three-panel figure, defined testing before using it, and reorganized the opening of Appendices K and P.

First, we have placed a short roadmap and the new figure at the beginning of Appendix K, before Proposition K.1. The roadmap reads:

The lower bound proceeds in three steps. First, two truncated geometric clocks select predictors from the learner's own earlier actions. The first scans the outer blocks from left to right, while the second scans the inner blocks in reverse order. If both clocks stop, the selected predictors are plo=pIp^{\mathrm{lo}}=p_I and phi=pI+Jp^{\mathrm{hi}}=p_{I+J}. Second, the remaining block contains 2d2^d candidate thresholds. By testing a branch bit, we mean querying the corresponding midpoint for h=⌊m/d⌋h=\lfloor m/d\rfloor rounds before revealing that bit and proceeding to the next level. The same two historical predictors are reused throughout these tests. Third, the proof relates the loss incurred during the scans to the selected predictors' scores, creating a tradeoff between the cost of producing the replay sources and the cost of distinguishing the remaining target bits. The latter is quantified by the sequential Bernoulli testing bounds in Lemmas B.2 and B.3 of Appendix B, in the sequential testing subsection.

The new Figure 2 illustrates these three steps, with the following caption:

Three stages of the lower-bound construction. (a) The first geometric scan selects pIp_I from the outer blocks. (b) The reversed second scan selects pI+Jp_{I+J} from the inner blocks. (c) The adversary reuses these historical predictors while repeatedly testing the dd unresolved branch bits of the remaining threshold block. Each bit is revealed only after its hh testing rounds. The target and both stopping times are sampled before interaction.

We have also revised the introduction to Appendix P, before the target-prior construction, to clarify the difference between the proper and improper constructions:

For proper learners, monotonicity transfers score control from the two source-selection points to every later test point. Arbitrary probability-valued predictors need not be monotone. We therefore use independent query probes during the non-stopping rounds of the two scans, drawn after the learner has submitted its complete prediction function. The stopping-round boundary queries and the subsequent midpoint tests remain unchanged. These probes allow the construction-phase loss to control the historical scores on average across testing levels, rather than simultaneously at every level. This average control is sufficient to apply the same sequential testing bounds.

Finally, we have added explicit references to Lemmas B.2 and B.3 wherever the testing argument is first invoked, and to Proposition B.1 for the source-mixing argument. The main text also points directly to the new figure and roadmap.

These changes are intended to make Appendix K understandable on its own, clarify the different score-control arguments in Appendices K and P, and make the construction accessible before the technical proof begins.


Q5: Section 4 repeatedly uses the bias–variance tradeoff to explain the Hedge upper bounds, but does not show how the ratio between the effective signal and its second moment determines the resulting regret. Could this relationship be stated as a general lemma in the main text and used to explain the subsequent bounds?

A: Thank you for this suggestion. We agree that the connection between the feedback moments and the Hedge bound should be made explicit. The signed mean drives the Hedge potential downward, while the second moment controls the quadratic cost of each update. Together, they determine the learning rate and the cumulative prediction error. We have added the following lemma in Section 3.2, after the upper-bound discussion, and referred to it throughout Section 4.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Contributions and Review Discussion

Dear Area Chair,

Thank you for coordinating the discussion. Reviewer yCue (confidence 3) raised their overall rating to 4 (Clear acceptance) after the discussion. Reviewer CkMJ (confidence 4) and Reviewer chNt (confidence 3) both rated the paper 2 (Weak rejection) and assigned a Soundness score of 3. Neither CkMJ nor chNt has replied to our rebuttal or posted a follow-up comment in the public discussion.

We study online learning over KK thresholds starting from an empty history. Feedback comes from either the true label or a previously deployed predictor. For horizons T≤K1/2−εT \le K^{1/2-\varepsilon}, we establish sharp minimax rates for all audit rates ρ\rho. At ρ=1/2\rho=1/2, the minimax cumulative loss is Θε(min⁡T,T2/3(log⁡K)1/3)\Theta_\varepsilon\bigl(\min\\{T, T^{2/3}(\log K)^{1/3}\\}\bigr). The lower bound holds even for improper learners. It accounts for the loss incurred while the learner produces the predictors that are later replayed.

1. Main concerns from Reviewer CkMJ and Reviewer chNt

Reviewer chNt described the paper as “clearly interesting and insightful” and wrote that “the results are certainly good enough for any premier ML venue.” Reviewer CkMJ described the problem as a “fairly interesting setting” and found the rates in Theorem 3.1 “somewhat surprising.”

Both reviewers selected the Soundness assessment 3 “I have no substantive concerns about the paper’s soundness.” For Informativeness, CkMJ gave 2 (“I learned something interesting or useful”) and chNt gave 3 (“I gained a substantially deeper understanding of the problem or question”). Both reviews identified the exposition of the core theory as a main concern.

Concern in the original reviewsRevision
The main lower-bound construction was difficult to follow.We rewrote Section 3.3 to explain, before stating the lower bound, how the two historical predictors are selected and how replay makes feedback under different true labels hard to distinguish. The new three-panel Figure 2 illustrates the construction.
The upper-bound algorithm and analysis were hard to follow.Section 3.2 now presents the clipped exponential-weights algorithm and its anytime guarantee at the critical audit rate. The new Lemma 3.4 shows how the feedback signal and its second moment determine the cumulative loss bound for Hedge.
The appendix was long and key arguments were dispersed.We removed secondary results and replaced repeated proofs with cross-references. The main text now explains the key steps of the construction and algorithm.

2. Feedback on the revised presentation

Reviewer yCue specifically noted that the construction figure, the comparison for longer horizons moved into the main text, and the new Section 6 improved the presentation. They wrote, “Given these additions, I am raising my rating and my presentation score.” The updated review gives Presentation 3 (Clear and easy to follow). Their assessment of the construction figure speaks directly to the difficulty that both reviewers identified in following the main lower bound.

All three reviewers saw merit in the main theoretical results. Both reviewers who recommended weak rejection found the work interesting and reported no substantive concerns about its soundness. They identified presentation as the main weakness. After reading the revised manuscript, yCue, the only reviewer who participated in the public discussion, raised the presentation score to 3 (Clear and easy to follow). We believe the revisions address the main presentation concerns raised in both reviews. We would be grateful if you could consider the positive assessments of the core theory from each of the three reviewers and yCue’s assessment of the revised presentation in your final recommendation.

Best regards,
The authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.