acceptodds
Under review as a conference paper at ICLR 2027

Agnostic smoothed online regression with adversarial responses

Abstract

We study smoothed online prediction with bounded adversarial responses. This widely studied framework bridges i.i.d. sampling and adversarial covariate selection through a smoothness parameter , which bounds conditional covariate densities relative to a fixed, unknown base measure. We propose Hedge-Cover, an information-theoretic algorithm that achieves sublinear regret for function classes with bounded pseudo-dimension. The algorithm aggregates a carefully constructed family of experts using Hedge, with a prior that links regret to the number of disagreements between a consistent selector and a target function. We bound this number by exploiting covariate smoothness. This answers an open problem posed in blanchard2025agnostic on the minimax optimal adaptive regret of the smoothed online regression problem. We establish a matching lower bound for the class of linear predictors. The main intricacy of the lower bound lies in explicitly constructing a challenging sequential covariate distribution supported on mutually orthogonal hyperplanes. This construction may be of independent technical interest. Finally, we revisit the well-specified setting and quantify the effect of response noise. For conditionally -subGaussian responses, we extend the existing lower bound under realizable responses by showing that the minimax expected regret is for a function class of VC dimension . A corresponding upper bound for ERM matches this dependence on .

Primary area:
learning theory
Keywords:
learning theory, online learning, smoothed analysis, ERM

Reviews

Among:
Shape:
1234this paper, Top 17%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.75 over 4 reviews, above 83% of the others.
Reviewer_c4p3OpenReview ↗
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
  1. 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.
  2. 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.
  3. 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
  1. The upper and lower bounds do not genuinely match. The upper bound (Them 2.1) involves the smoothness parameter CcovC_{cov}, whereas the lower bound (Thm 3.1) involves Ccov−1C_{cov}-1. Their ration is not uniformly bounded and becomes infinite when Ccov→1C_{cov}\rightarrow 1. 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.

  2. The linear comparator class changes between results. Theorem 3.1’s discussion uses clipped linear predictors, whereas Proposition 3.2 compares against θ⊤x\theta^\top x 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.

  3. 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
  1. I am curious about how to practically check out the smoothness assumption dp/dμ≤Ccovdp/d\mu\leq C_{cov}? As you assume the base measure μ\mu is unknown, it seems it also implies the constant CcovC_{cov} is impossible to find in practice. I understand this assumption is standard and borrowed from the literature, but a quick discussion would be helpful.
  2. How did you choose the number of discretization mm? Theorem B.5 says m≍T−1m\asymp T^{-1}, which seems incorrect as mm should be at least greater than 1?
4 comments

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.

Q1: We agree with the reviewer that CcovC_{cov} can be difficult to estimate in the agnostic setting, where the base measure μ\mu 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 m≍Tm\asymp T suffices to achieve the regret order in Theorem 2.1 and does not require CcovC_{cov}. Knowing CcovC_{cov} 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 (Xt)t≥1(X_t)_{t\geq 1} can yield an explicit smoothness constant.

1. Uniformly bounded conditional densities. Suppose that the conditional law of XtX_t given X1,…,Xt−1X_1,\ldots,X_{t-1} has a Lebesgue density supported on a common set S\textsf{S} of finite, positive volume. Suppose these densities are bounded above by LL uniformly over rounds and almost all histories. Taking μ=unif(S)\mu=\textsf{unif}(\textsf{S}) bounds the conditional density relative to μ\mu by LVol(S)L\textsf{Vol}(\textsf{S}). Thus we may take Ccov=LVol(S)\textsf{C}_{\textsf{cov}}=L\textsf{Vol}(\textsf{S}).

2. Finite-state hidden Markov model. Let st∈{1,⋯ ,K}s_t\in\{1,\cdots,K\} be the hidden state at time tt, and let qkq_k be the distribution corresponding to state kk. Given X1,⋯ ,Xt−1X_1,\cdots,X_{t-1}, the law of XtX_t is a mixture of the qkq_k with weights P(st=k∣X1,…,Xt−1)\mathbb{P}(s_t=k\mid X_1,\ldots,X_{t-1}). Since each weight is at most 11, this conditional law is dominated by ∑k=1Kqk\sum_{k=1}^{K}q_k. Hence, with μ=K−1∑k=1Kqk\mu=K^{-1}\sum_{k=1}^{K}q_k, we may take Ccov=K\textsf{C}_{\textsf{cov}}=K.

Q2: There was a typo in the discretization size: the intended choice is m≍Tm\asymp T and the subsequent analysis remains the same. In the regret upper bound, mm enters through the logarithmic factor log⁡(mε−1)≍log⁡(Tε−1)\log(m\varepsilon^{-1})\asymp\log(T\varepsilon^{-1}). 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 CcovC_{cov} 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 CcovC_{cov} 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.

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

The paper shows that the optimal sublinear adaptive regret for the agnostic smoothed online regression problem is of order dCcovT\sqrt{dC_{\text{cov}}T}. The problem refers to the case where (1) a smoothness condition bounds the conditional covariate densities with respect to a fixed, unknown measure and (2) an adversary can arbitrarily choose the response at each time step. To derive the upper bound, they propose an information-theoretic (but computationally infeasible) algorithm called HEDGE-COVER. In addition, a class of linear predictors is considered to derive the lower bound. Finally, the authors additionally show that the optimal regret is of similar order even under well-specified problems, where they further refine existing theoretical derivations from Block et al. (2024) and Blanchard (2025) by explicitly characterizing the effect of the noise level on the regret.

Critical strengths
  • Unlike the work of Blanchard (2025), they derive the order of the optimal adaptive regret.

  • They explicitly characterize the effect of the noise level on the optimal regret under well-specified problems.

Critical weaknesses

In order to derive the order of the optimal adaptive regret, they impose a stronger assumption on the pseudo-dimension in comparison to that of Blanchard (2025) on the fat-shattering dimension. I am wondering whether such a restriction hinders the general applicability of the theoretical findings for future research.

Questions for authors

See Critical Weaknesses.

2 comments

We thank the reviewer for their clear summary of our contributions and for raising important questions concerning the pseudo-dimension of the function class F\mathcal{F}. The reviewer asked about the finite pseudo-dimension assumption in Theorem 2.1. We agree that only requiring a more general condition such as finite generalized fat-shattering dimension fatF(γ)\textsf{fat}_{\mathcal{F}}(\gamma) will broaden the scope of the work. The finite pseudo-dimension assumption covers standard classes such as finite-dimensional clipped linear predictors, linear predictors with a fixed sigmoid link, and clipped ReLU networks of fixed architecture (see Bartlett et al., 2019).

In the literature on smoothed online prediction, Haghtalab et al. (2022) use pseudo-dimension to analyze smoothed online learning with real-valued function class and a known base measure μ\mu. Wu et al. (2023) impose the same function class complexity and bound sequential covering numbers for real-valued classes under i.i.d. covariates. In our setting, Remark 1 explains how pseudo-dimension controls the number of discretized prediction patterns in the covers used by Hedge-Cover. We leave the extension to fat-shattering conditions for future work. We refer the reviewer to our official comments for our other changes. If our revisions satisfactorily address your concerns, we would be grateful if you would consider updating your score or confidence assessment.

Bartlett, Peter L., et al. "Nearly-tight VC-dimension and pseudo-dimension bounds for piecewise linear neural networks." Journal of Machine Learning Research 20.63 (2019): 1-17.

Haghtalab, Nika, et al. "Oracle-efficient online learning for smoothed adversaries." Advances in Neural Information Processing Systems 35 (2022): 4072-4084.

Wu, Changlong, et al. "Expected worst case regret via stochastic sequential covering." arXiv preprint arXiv:2209.04417 (2022).

Thank you for the detailed response. I have read the rebuttal as well as the other reviews. As reflected in my confidence score, this paper is outside my primary area of expertise, so I am not in a position to fully judge whether the remaining concerns have been resolved. I will therefore keep my original score and defer to the other reviewers and the AC for the final assessment.

Reviewer_eryeOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This manuscript studies smoothed online regression with bounded adversarial responses when the base measure governing the covariates is unknown to the learner. The authors proposed HEDGE-COVER, an information-theoretic algorithm with a sublinear adaptive regret guarantee for function classes of finite pseudo-dimension. The manuscript also develops lower bounds, analyzes VAW for linear regression, and studies sub-Gaussian response noise in the well-specified setting. However, the ERM extension requires additional assumptions or restrictions, the comparison between the linear upper and lower bounds needs clarification, and the stated optimality claims are too broad near the i.i.d. boundary.

Critical strengths

The manuscript addresses a meaningful question in smoothed online learning by allowing adversarial responses without giving the learner access to the base measure. HEDGE-COVER connects the aggregation penalty to the number of corrections made by a consistent selector, providing an interesting route to an adaptive regret guarantee. The lower-bound construction and the noise-dependent analysis also help distinguish the difficulty caused by covariate adaptivity from that caused by response noise.

Critical weaknesses
  1. The ERM guarantee in Remark 1, or a restriction on how the empirical minimizer is selected. Definition 1 conditions smoothness only on the covariate history, whereas the ERM predictor can depend on past responses. This difference can lead to linear error even with i.i.d. covariates. For example, let X1,…,XT+1X_1,\ldots,X_{T+1} be i.i.d. uniform on [N][N], where N≥T2N\geq T^2, and let StS_t be independent Rademacher signs, independent of these covariates. Set
Yt=StXt+14N,F={0}∪{x↦1{x=j}:j∈[N]}.Y_t=\frac{S_tX_{t+1}}{4N}, \qquad \mathcal F=\{0\}\cup\{x\mapsto\mathbf 1\{x=j\}:j\in[N]\}.

This class has VC dimension one, f∗=0f^*=0, and the noise is conditionally mean-zero and bounded by 1/41/4. Although Ccov=1C_{\mathrm{cov}}=1 under Definition 1, Yt−1Y_{t-1} reveals XtX_t. Every unseen singleton is an empirical minimizer, while each observed singleton has greater empirical loss than the zero function. Starting with f^1=0\widehat f_1=0, a valid ERM rule can select the singleton at the revealed XtX_t whenever that point is unseen, and select zero otherwise. Its expected cumulative estimation error is ∑t=2T(1−1/N)t−1=Ω(T),\sum_{t=2}^{T}(1-1/N)^{t-1}=\Omega(T), contradicting the claimed sublinear specialization of equation~(3.4) for unrestricted ERM. The authors should retain smoothness conditional on the full interaction history, or specify an ERM selection rule and justify the bound for that rule. This issue concerns the ERM extension; it does not by itself invalidate the HEDGE-COVER guarantee. 2. The claimed optimality of VAW needs to use the same comparator class in the upper and lower bounds. The proof discussion for Theorem 3.1 defines the clipped linear class Flin={x↦(θ⊤x∨−1)∧1:θ∈Rd}\mathcal F_{\mathrm{lin}}=\{x\mapsto(\theta^\top x\vee-1)\wedge1: \theta\in\mathbb R^d\}, whereas Proposition 3.2 compares the learner with untruncated linear predictions θ⊤x\theta^\top x. For responses in [−1,1][-1,1], clipping can reduce the comparator's loss. Consequently, a regret upper bound against untruncated predictors does not imply the same bound against the clipped class. The authors should show that the lower-bound construction also applies to the untruncated comparator, or establish the upper bound for the clipped class, before concluding that these results match. 3. HEDGE-COVER is an information-theoretic algorithm whose hypothesis class has size (m+1)T(m+1)^T, with m=2Tm=2T. Maintaining and aggregating predictions over this exponentially large class appears computationally intractable. The manuscript acknowledges this limitation, but the practical applicability of the proposed approach remains unclear. 4. The claimed minimax optimality is not established uniformly across all parameter regimes. The upper bound in Theorem 2.1 is O~(dCcovT)\widetilde{O}(\sqrt{d C_{\mathrm{cov}}T}), whereas Theorem 3.1 gives a lower bound of order d(Ccov−1)T\sqrt{d(C_{\mathrm{cov}}-1)T} for d≥2d\geq 2 and Ccov>1C_{\mathrm{cov}}>1, but only a logarithmic lower bound when Ccov=1C_{\mathrm{cov}}=1 or d=1d=1. The relationship between these bounds, particularly near Ccov=1C_{\mathrm{cov}}=1, remains insufficiently characterized. 5. The main agnostic regret guarantee assumes bounded responses, yt∈[−1,1]y_t\in[-1,1], while sub-Gaussian responses are considered only in the well-specified setting.

Questions for authors

Please see strengths and weaknesses.

1 comment

We thank the reviewer for their reading, thoughtful questions, and insightful counterexample, which have helped us clarify several important aspects of the manuscript.

W1: Thank you for pointing out the lack of clarity regarding the smoothness assumption required for the ERM guarantee and providing the illustrative counterexample. 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.

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: We agree that the explicit implementation of Algorithm 1 is computationally inefficient for large horizons, since it enumerates all (2T+1)T(2T+1)^T hypothesis. The computation can be reduced by aggregating hypotheses with the same trajectory Dt,hD_{t, h} and the same number ∣Th∩[t]∣|\mathcal T_h\cap[t]|. Within each group, predictions determined by the selector coincide, and the prior mass associated with the remaining choices depends only on tt and ∣Th∩[t]|\mathcal T_h\cap[t]. We can therefore maintain the sum of the corresponding Hedge weights and update these groups recursively.

When Pdim(F)≤d\mathrm{Pdim}(\mathcal F)\leq d, Sauer’s lemma bounds the number of realizable trajectories, yielding an implementation with TO(d)T^{O(d)} operations. We will add this implementation discussion in the final version and its oracle requirements to clarify the computational scope of Hedge-Cover.

W4: 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. In short, we sharpen our upper bound result in Theorem 2.1 by proving a stronger version of Corollary 2.5. This improvement replaces CcovC_{cov} with Ccov−1C_{cov}-1. We refer the reviewer to the detailed discussions in our official comment above.

W5: "The main agnostic regret guarantee assumes bounded responses, yt∈[−1,1]y_t\in [-1,1], while sub-Gaussian responses are considered only in the well-specified setting". Theorems 2.1 and 3.1 address the setting in which nature may choose responses adversarially in [−1,1][-1,1]. Our ERM discussion considers an easier prediction problem: well-specified responses of the form yt=f⋆(xt)+ηty_t=f^\star(x_t)+\eta_t, where f⋆∈Ff^\star\in\mathcal F and ηt\eta_t is conditionally mean-zero and sub-Gaussian (see Definition 4).

We interpret the reviewer’s question as asking whether our agnostic guarantee extends to responses with an arbitrary history-dependent conditional mean gt=E[Yt∣Ht−1,Xt]g_t=\mathbb E[Y_t\mid\mathcal H_{t-1},X_t] satisfying ∣gt∣≤1|g_t|\leq1, with Yt−gtY_t-g_t conditionally ν2\nu^2-sub-Gaussian. Given an upper bound on the noise scale ν\nu, we can truncate the responses at B=1+ν2log⁡(2T)\textsf{B}=1+\nu\sqrt{2\log(2T)}, apply Hedge-Cover to the normalized responses and the class F/B\mathcal F/\textsf{B}, and rescale its predictions. The squared-loss difference between the learner and each comparator is linear in the response, so the sub-Gaussian tails control the expected truncation error. For fixed ν\nu, this yields an expected regret guarantee with the same dependence on TT, dd, and Ccov\mathsf{C}_{\mathsf{cov}} up to logarithmic factors.

We would be happy to address further questions you may have. If our revisions satisfactorily address your concerns, we would be grateful if you would consider increasing your score or confidence assessment.

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

This paper investigates agnostic smoothed online regression under the squared loss with bounded adversarial responses yt∈[−1,1]y_t \in [-1, 1] and an unknown base measure μ\mu, where the conditional law of each covariate xtx_t given past covariates has density ratio at most Ccov≥1C_{\text{cov}} \geq 1 with respect to μ\mu. The main contribution of this paper is to achieve Pdim(F)CcovT\sqrt{Pdim(\mathcal F)C_{cov}T} adaptive regret using the proposed Hedge-Cover algorithm, as well as providing a matching regret lower bound and analyzing the dependence of regret on level of the (subGaussian) noise in the well-specified setting.

Critical strengths
  1. The paper provides a guarantee on the adaptive regret of agnostic smoothed online regression under covariate-history smoothness, which is more general than the full-history smoothness.
  2. The Hedge-Cover algorithm takes a conceptually simpler form than R-Cover from the previous work Blanchard (2025), whose published regression guarantee concerns oblivious regret.
  3. In the well-specified setting where the responses satisfy E[yt∣xt]=f∗(xt)E[y_t|x_t]=f^* (x_t) for some f∗∈Ff^*\in \mathcal F, they provide a sharp characterization of dependence on the response noise level.
Critical weaknesses
  1. While their main result provides guarantee on adaptive regret, it requires a stronger assumption on the pseudo-dimension of the hypothesis class. This is crucial for their proof. Under the same pseudo-dimensional assumption, and when restricted to Blanchard’s original full-history smoothness model, the R-Cover’s existing high-probability guarantee appears extendable to adaptive regret through discretization and uniform covering. The authors should clarify the additional contribution of their algorithm and analysis, particularly in handling the broader covariate-history smoothness model.
  2. Their second point of contribution overstates how much novelty is conveyed by the lower-bound rate itself. Theorem 3 of Blanchard (2025) already establishes the same lower bound for realizable binary classes, which yields the corresponding worst-case regression lower bound over finite-Pdim classes through a short reduction. The plausible additional contribution is a targeted extension to unrestricted linear regression, built from earlier constructions. Those should be made clear in the paper.
Questions for authors

Question: The footnote to Eq. (3.4) acknowledges that the cited ERM upper bound in n Block et al. (2024) assumes smoothness conditional on the full history. Are Eq. (3.4) and the associated ERM minimax-optimality claim in Remark 5 intended only for this stronger assumption? If so, please state that restriction explicitly in Remark 5. Otherwise, if the claim holds for the covariate-history smoothness in Definition 1, please provide the argument extending the upper bound to covariate-history smoothness.

4 comments

We thank the reviewer for reading our manuscript carefully, raising several important questions, and identifying ambiguous points that would benefit from clarification.

W1: We agree that, under Blanchard’s original full-history smoothness condition dPt( ⋅∣x1,y1,⋯ ,xt−1,yt−1)/dμ(x)≤Ccov\mathrm{d}P_t(\,\cdot\mid x_1,y_1,\cdots,x_{t-1},y_{t-1})/\mathrm{d}\mu(x)\leq C_{cov}, the fixed-comparator high-probability bound for R-Cover (Blanchard [2025] Theorem 12) can be proved over a regression class of finite pseudo-dimension. Applying the bound over a finite cover and controlling the approximation error uniformly along the realized covariates leads to the same O~(dCcovT)\widetilde O(\sqrt{dC_{cov}T}) adaptive regret rate.

Our Theorem 2.1 requires smoothness only conditional on the past covariates dPt( ⋅∣x1,⋯ ,xt−1)/dμ(x)≤Ccov\mathrm{d}P_t(\,\cdot\mid x_1,\cdots,x_{t-1})/\mathrm{d}\mu(x) \leq C_{cov}. This difference matters when past responses carry information about future covariates. We thank the reviewer for this perceptive observation, which helped us clarify and position our algorithm. We revised the discussion following Table 1 to clarify this subtlety. Our comment to Reviewer eoBG discusses the pseudo-dimension assumption in more detail.

W2: Thank you for pointing out the need to clarify our contribution compared with Blanchard (2025). We agree that Theorem 3 therein establishes the lower bound for realizable binary classes, which implies the corresponding worst-case regression lower bound through a short reduction. We have revised Remark 3 to explicitly acknowledge this relationship and distinguish our contribution from the lower-bound rate itself.

Our contribution is to establish the lower bound specifically for the linear function class, building on the earlier construction of Chen et al. (2026). We adapt this construction to smooth environments by constructing a hard sequential covariate process supported on mutually orthogonal two-dimensional subspaces. The resulting lower bound shows that linear classes in dimension at least two already capture the worst-case difficulty among classes of the corresponding pseudo-dimension.

Moreover, together with the upper bounds in Chen et al. (2026, Theorem 5) and Proposition 3.2, our results identify a sharp dimension-dependent transition for linear predictors: logarithmic regret in one dimension versus square-root dependence on the horizon in higher dimensions. Since general classes of pseudo-dimension one can already exhibit the latter rate, this transition reflects the structural properties of the linear function class.

Q1: 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.

Blanchard, Moïse. "Agnostic smoothed online learning." Proceedings of the 57th Annual ACM Symposium on Theory of Computing. 2025.

Chen, Fan, et al. “Self-Normalized Martingales and Uniform Regret Bounds for Linear Regression.” Proceedings of Thirty Ninth Conference on Learning Theory, 2026

We are following up on our response to your review and would appreciate any further feedback. Following your suggestions, we clarified the distinction from R-Cover under covariate-only-history smoothness and revised the positioning of our linear-class lower bound in the general responses.

Could you please let us know whether these revisions address your concerns, or whether any points need further clarification?

Thank you again for your careful review and helpful suggestions!

We thank the author for reaching out. The real contribution of this paper is actually in the covariate-history smoothness, which we personally believe should be emphasized more -- we appreciate the author's effort by adding after their contribution section, a discussion that acknowledges what this paper has really achieved beyond the prior work, but it still seem to the readers that, at the first glance, this paper has achieved more than what it really obtains. Also, using the Pdim assumption rather than fat shattering dimensions would potentially hinder the contribution of a potential future work that attempts to extend to adaptive regret in this problem.

Nevertheless, there's still novelty in this paper. Therefore, we will not change our current assessment of this paper.

Thank you for your follow-up and for recognizing the novelty of our work. Your feedback is valuable for improving the presentation and clarifying the scope of our results.

Comments on the paper

8 comments
AuthorsOpenReview ↗

General Responses

We thank all the reviewers for their time and feedback. Their questions and suggestions helped strengthen the manuscript. We have uploaded a revised version with four main changes.

  1. A sharper regret bound for Hedge-Cover. We sharpen the upper bound in Theorem 2.1, which now only depends on Ccov−1C_{cov}-1 not CcovC_{cov}, matching the smoothness dependence in the lower bound of Theorem 3.1.

  2. Clarifying the comparator class for VAW. We clarify that the VAW optimality comparison concerns the unrestricted linear class and add counterexamples showing that VAW and its clipped variants can incur linear regret against the clipped linear class.

  3. Clarifying the smoothness assumption for ERM. We explicitly restrict the ERM optimality claim to full-history smoothness and add a counterexample showing that partial-history smoothness alone permits linear expected regret even when the ERM is unique.

  4. A discussion of two concurrent papers that study variants of our problem, highlighting an algorithmic insight in one and an approach to computational efficiency in the other.

AuthorsOpenReview ↗

Improved upper bound dependency on

We thank reviewers erye and c4p3 for their careful reading and for asking how the regret bound in Theorem 2.1 depends on CcovC_{cov}.

From reviewer erye, "the claimed minimax optimality is not established uniformly across all parameter regimes. ... The relationship between these bounds, particularly near CcovC_{cov} near 1, remains insufficiently characterized."

From reviewer c4p3, "The upper and lower bounds do not genuinely match. The upper bound (Thm 2.1) involves the smoothness parameter CcovC_{cov}, whereas the lower bound (Thm 3.1) involves Ccov−1C_{cov}-1. Their ratio is not uniformly bounded and becomes infinite when Ccov→1C_{cov} \to 1."

Let d=Pdim(F)d=\text{Pdim}(\mathcal{F}), the original theorem gave a regret bound of O~(Ccov dT)\widetilde{O}(\sqrt{C_{cov}\,dT}). We further close the ``non-uniform" gap (w.r.t. CcovC_{cov}) mentioned by the two reviewers. The revised theorem 2.1 sharpens this bound to O~([d+(Ccov−1)dT]∧T).\widetilde{O}([d+\sqrt{(C_{cov}-1)dT}]\wedge T). The revised rate matches the lower bound in Theorem 3.1 in its dependence on TT, dd, and CcovC_{cov}, up to logarithmic factors. The bound also makes the transition to the i.i.d. covariate regime explicit. As Ccov↓1C_{cov}\downarrow 1, the square-root term decreases continuously and no further phase transition hidden.

Regarding the technical details, the improvement follows from a sharper version of Corollary 2.5. In the low-density term analysis in the proof of Corollary 2.5 Appendix A, we use a truncated telescoping argument to obtain a tighter bound on ∑1≤t≤TPt(At)\sum_{1\leq t \leq T}P_t(A_t). Plugging this estimate at the corresponding step in the proof of Theorem 2.1 brings the improved regret bound with respect to CcovC_{cov}. We have highlighted the revised statement and proof of Corollary 2.5 in cyan. We thank the reviewers for drawing attention to the dependence on the smoothness parameter. To the best of our knowledge, this is the first regret upper bound for agnostic smoothed online prediction with a smoothness-dependent term that scales as Ccov−1\sqrt{C_{cov}-1} and reveals the behavior of regret when CcovC_{cov} is near 11. We allude to this refinement in the first two bullet points of the contributions list and in Remark 1. In the revised version of submitted manuscript, we highlight the corresponding statement and proof changes in cyan.

AuthorsOpenReview ↗

Filtration

We thank reviewers RZd6, erye, and c4p3 for pointing out the lack of clarity regarding the smoothness assumption required for the ERM guarantee.

We agree that the ERM upper bound of Block et al. (2024) requires full-history smoothness, which is stronger than the partial-history smoothness in Definition 1, and that our previous Remark 5 did not adequately distinguish these assumptions. We have revised its title to Optimality of ERM under full-history smoothness and explicitly restricted both equation (3.4) and the associated optimality claim to this setting.

Although Theorem 3.3 is stated under partial-history smoothness, its lower-bound construction also satisfies full-history smoothness. This allows comparison with the ERM upper bound under the same assumption. Appendix E.3 explains this verification and where full-history smoothness enters the analysis of Block et al. (2024).

As illustrated by reviewer erye's example, the full-history assumption cannot generally be relaxed to partial-history smoothness for the ERM upper bound. To address whether restricting the ERM selection rule could resolve this issue, Appendix E.3 provides a counterexample satisfying partial-history smoothness but past responses reveal future covariates. The ERM in this example is almost surely unique, yet incurs linear expected cumulative estimation error and hence linear expected regret. Thus changing the tie-breaking rule cannot generally recover the guarantee.

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.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.