- Rating
- 3
- Confidence
- 3(+1)
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The submission studies sequential prediction under squared loss when responses are adversial and covariate distributions' densities have bounded derivatives. One of the contributions is a novel algorithm, HEDGE-COVER, which corrects and improves predictions in a subset of periods while applying its own predictions in other periods. The authors establish a performance upper bound for the algorithm and complement it with a matching lower bound for the class of linear predictors. It further considers a special case where responses are subGaussian and improves lower bounds over existing results by extending them to account for such randomness. Overall, this submission is a good paper with deep and solid theoretical contributions to the online learning literature.
Critical strengths
- The paper addresses an important problem with a rate-optimal algorithm. Agnostic online learning under adversial responses is important yet hard to solve. The proposed HEDGE-COVER algorithm is shown to be rate-optimal for the class of smoothed distributions of adversarial responses.
- The lower bounds provide explicit mechanisms for difficulty. The orthogonal-plane construction indentifies a difficult sequential path, establishing the fundamental limits. The repeated-node construction similarly explains the additional cost of response noise.
- The paper includes useful qualifications to its own complexity perspective. Remark 1 acknowledges the restriction to finite pseudo-dimension, and Proposition 3.4 distinguishes worst-case minimax sharpness from sharpness for individual classes. These qualifications improve the conceptual value of the results.
Critical weaknesses
-
The upper and lower bounds do not genuinely match. The upper bound (Them 2.1) involves the smoothness parameter , whereas the lower bound (Thm 3.1) involves . Their ration is not uniformly bounded and becomes infinite when . Given the central role of smoothness to this paper, I believe this gap should be clearly stated. Ideally, the authors may consider providing some intuitions into why such a gap exists, and point out potential refinement for future study.
-
The linear comparator class changes between results. Theorem 3.1’s discussion uses clipped linear predictors, whereas Proposition 3.2 compares against without clipping. Clipping can reduce comparator loss, so an upper bound against unrestricted linear predictors does not automatically give an upper bound against clipped predictors. This may affect the claim of a logarithm-free matching result.
-
The ERM optimality claim contains an unresolved assumption transfer. Footnote 1 acknowledges that the cited ERM theorem assumes smoothness conditional on the full interaction history, while this paper assumes smoothness only conditional on covariate history. Appendix D.4 corrects noise scaling but does not explicitly bridge this change in filtration. A cumulative estimation-error bound also requires an additional argument before it yields regret against the empirical best comparator.
Questions for authors
- I am curious about how to practically check out the smoothness assumption ? As you assume the base measure is unknown, it seems it also implies the constant is impossible to find in practice. I understand this assumption is standard and borrowed from the literature, but a quick discussion would be helpful.
- How did you choose the number of discretization ? Theorem B.5 says , which seems incorrect as should be at least greater than 1?
4 comments
Q1: We agree with the reviewer that can be difficult to estimate in the agnostic setting, where the base measure is unknown. As the reviewer notes, the smoothness assumption is standard in smoothed online learning. In our work, both the base measure and the smoothness parameter enter only the analysis of Hedge-Cover, whereas, for implementation, the horizon-based choice suffices to achieve the regret order in Theorem 2.1 and does not require . Knowing may only help refine the multiplicative constant through tuning.
We interpret the smooth condition in the same spirit of rejection sampling while permitting possible dependency on the history. The following two examples justify this intuition and show how specific data generation models for the covariate process can yield an explicit smoothness constant.
1. Uniformly bounded conditional densities. Suppose that the conditional law of given has a Lebesgue density supported on a common set of finite, positive volume. Suppose these densities are bounded above by uniformly over rounds and almost all histories. Taking bounds the conditional density relative to by . Thus we may take .
2. Finite-state hidden Markov model. Let be the hidden state at time , and let be the distribution corresponding to state . Given , the law of is a mixture of the with weights . Since each weight is at most , this conditional law is dominated by . Hence, with , we may take .
Q2: There was a typo in the discretization size: the intended choice is and the subsequent analysis remains the same. In the regret upper bound, enters through the logarithmic factor . We have corrected the statement of Theorem B.5 in the revised submission.
Thank you for your time and feedback. If you feel that our revisions address the points you raised, we would be grateful if you would consider raising your score or confidence rating.
Block, Adam, Alexander Rakhlin, and Abhishek Shetty. "On the performance of empirical risk minimization with smoothed data." The Thirty Seventh Annual Conference on Learning Theory. PMLR, 2024.
I thank the authors for the detailed responses. The gap in the smoothness parameter between the upper and lower bounds seems remain unresolved. Therefore I keep my original score.
I thank the authors for the detailed responses. I am updating my comment as I just noticed the responses at the top of this page.
The new sharper regret bound ito looks good to me; thus, I am rasing my confidence rating from 2 to 3.
We thank the reviewer for their positive feedback and for taking the time to reconsider our theoretical results. We appreciate their acknowledgment of the sharper regret bound.
We thank the reviewer for their careful reading of our manuscript and for their insightful questions. We address each question in turn below.
W1: "The upper and lower bounds do not genuinely match." We thank the reviewer for their careful reading. We agree that the smoothness assumption is central to both the design and analysis of our algorithm. We sharpen our upper bound result in Theorem 2.1 and discuss its role in more detail in our official comment above.
W2: Thank you for identifying the ambiguity in the comparator class for VAW. We agree that an upper bound against unrestricted linear predictors does not imply the same upper bound against clipped linear predictors. We have explicitly distinguished the two classes and clarified that the VAW optimality comparison concerns the unrestricted linear class. We have also provided counterexamples showing that the VAW estimator and its clipped variants can incur linear regret against the clipped linear class. We refer the reviewer to the detailed discussion in our official comment above.
W3.1: Thank you for pointing out the lack of clarity regarding the smoothness assumption required for the ERM guarantee. We agree that the ERM upper bound requires the stronger full-history smoothness assumption. We have explicitly restricted the ERM optimality claim to this setting and added a counterexample showing that partial-history smoothness alone permits linear expected regret even when the ERM is unique. We refer the reviewer to the detailed discussion in our official comment above.
W3.2: Thank you for pointing out that an additional argument is needed to pass from cumulative estimation error to regret against the empirical best comparator. In Appendix E.4 of the revised manuscript, we show that the same rate also bounds the expected regret of ERM. Specifically, using a bound established in the proof of Lemma 13 of Block et al. (2024), we control the additional reduction in empirical loss achieved by the empirical best comparator relative to the true regression function. This additional term can be absorbed into the rate in equation (3.4), yielding the same upper bound for expected regret.