- 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 , labels are generated by an adversary-chosen past predictor of the learner, and it derives sharp minimax rates for all when , with at . 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
- 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.
- 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
- The headline rate relies on a strong adversary that knows the target, chooses replays based on the true label and reaches back rounds, and it holds only for , which limits what it says about model collapse.
- 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
- What is the rate at when the replay distribution does not depend on the target? A super- lower bound would strengthen the motivation and could raise my rating.
- Is the horizon limit intrinsic, or an artifact of the construction?
- Can the claim that the rate "requires sacrificing current accuracy" be stated as a theorem, or should the abstract be reworded?
- For , what is new relative to existing results on online learning with noisy labels?
7 comments
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 be the expected loss during source construction. At , 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 feedback. This forces expected testing loss. Conversely, let . For any fixed and sufficiently large depending on , any learner achieving at most total loss must incur 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 when . 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 , what is new relative to existing results on online learning with noisy labels?
A: Thank you for this question. The upper bound 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 .
| Theoretical aspect | Prior noisy-label learning | Our result |
|---|---|---|
| Feedback mechanism | Noise 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 bound | Hard 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 behavior | The classical gap-dependent bound becomes uninformative as . | At criticality, the loss has order . Our bounds also locate the sharp transition to this sublinear regime. |
Specifically, Theorem 3.1 establishes, for and ,
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 , the transition occurs at . Unlike general bounded-noise models, where feedback can become entirely uninformative at , 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.
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 rounds, and it holds only for , 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 , 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 , this yields . 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:
Replay age remains an important distinction. Theorem 4.2 shows that bounded expected replay age reduces the minimax loss to for fixed . Corollary G.5 further shows that the original polynomial lower bound requires . This establishes the need for growing replay age without claiming that is necessary. The horizon restriction applies to our sharp characterization rather than to all lower bounds. Appendix N already proves loss for . 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 , the upper bound balances the prediction cost against the learning cost . 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 in Theorem 5.1 motivates the soft-label and temperature comparisons below.
All tables report mean cumulative deployment loss 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 , 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 | Selected | No clipping | Selected clipping | Loss reduction |
|---|---|---|---|---|
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.
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 when the replay distribution does not depend on the target? A super-logK/ρ 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, we establish
R_T^{\mathrm{time}}(K,1/2) \ge c\min\left\\{ T,\\,[\min\\{T,K\\}\log K]^{1/4} \right\\}.
For (logK)3≪T≤K, this gives Ω((TlogK)1/4)=ω(logK). 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)=Θε(minT,T2/3(logK)1/3),T≤K1/2−ε.
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 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,
where m controls the construction of two replay sources and d counts the unresolved target bits. To keep m=Θ(T) and d=Θε(logK) feasible, we impose T≤K1/2−ε. Our results also provide a lower bound beyond this range. Corollary N.1 establishes, for every K,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) for all T≥K. At T≍K, the current upper bound is O(K1/3(logK)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.