acceptodds
Under review as a conference paper at ICLR 2027

Oracle-Efficient and Parameter-Free Agnostic Smoothed Online Learning

Abstract

Classical online learning deals with scenarios where data arrive sequentially and decisions must be made in an online fashion, often under adversarial conditions, and is attractive due to its robustness relative to more classical learning that relies on assuming independence. Unfortunately, due to the minimal assumptions it makes about the data-generating process, it often suffers from poor statistical and computational efficiency. Recently, smoothed online learning has emerged as a promising framework that interpolates between the fully adversarial and fully stochastic settings, making the assumption that the conditional law of each covariate has a density at most with respect to some fixed base measure . Prior work has investigated this setting either under the assumption that is known to the learner or under the assumption that the labels are perfectly predicted by a fixed hypothesis; in both cases, smoothed online learning admits statistically and computationally efficient algorithms. Recent work has demonstrated that even absent these conditions, smoothed online learning with unknown can be statistically efficient, but the algorithm studied was computationally intractable, leaving open the key question of whether it is possible to achieve both statistical and computational efficiency simultaneously when is unknown. In this work we resolve this question by giving the first oracle-efficient algorithm that achieves sublinear regret in the agnostic setting without knowledge of . We introduce a new, parameter-free algorithm based on Gaussian Follow-The-Perturbed-Leader that does not require prior knowledge of the smoothing parameter and is capable of achieving regret for binary classes of VC dimension with a single call to an optimization oracle per round. En route to establishing the regret bound, we introduce several new techniques that may be of independent interest.

Primary area:
learning theory
Keywords:
Online learning, smoothed analysis, beyond-worst-case analysis, oracle-efficient learning, follow-the-perturbed-leader, parameter-free learning

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_kuqEOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies agnostic smoothed online learning when the base measure is unknown to the learner. Previous works established oracle-efficient algorithms when the base measure is known, or under realizability assumptions when it is unknown. More recently, sublinear regret was obtained in the agnostic setting with an unknown base measure, but without oracle efficiency.

The paper resolves this computational question by proposing a parameter-free Gaussian Follow-The-Perturbed-Leader (FTPL) algorithm. For binary hypothesis classes with VC dimension (d), the algorithm achieves expected regret O~(dT/σ)\widetilde O(d\sqrt{T/\sigma}) using a single weighted ERM oracle call per round, without knowledge of the base measure, smoothing parameter, or horizon. The results are also extended to real-valued function classes and convex Lipschitz losses, with guarantees in terms of fat-shattering dimension.

The technical analysis combines an improved surprise lemma controlling second moments, a comparison between Gaussian FTPL and an auxiliary exponential-weights algorithm using Gaussian integration by parts, and a stability analysis showing that Gaussian perturbations control cumulative prediction variance.

Critical strengths

The paper addresses a natural and important open problem in smoothed online learning: achieving oracle-efficient agnostic learning without knowledge of the base distribution. Removing both the realizability and known-base-measure assumptions is a meaningful advancement over the existing literature. Furthermore, despite the technical complexity of the setting, the proposed algorithm is remarkably simple. In the binary case, it requires only one weighted ERM oracle call per round and does not require tuning based on σ,μ\sigma, \mu, or TT. The proof contains several potentially reusable techniques. In particular, the comparison between FTPL and exponential weights through their associated potentials and Stein's lemma is elegant. The second-moment surprise lemma provides a useful way to transfer guarantees on historical covariates to predictions on future adaptively generated covariates. The analysis of Gaussian-perturbed exponential weights with a constant learning rate is also interesting. The writing of the paper is also clear.

Critical weaknesses

My only concern is about the requirement of ERM oracle. The analysis assumes access to a weighted agnostic ERM oracle that can handle linear perturbations and general convex losses. The implications of this oracle requirement for practical implementations could be discussed more carefully. In particular, the guarantees appear to rely on exact optimization, and it is unclear how they degrade when only approximate ERM solutions are available.

Questions for authors

While I do not have much experience with agnostic smooth online learning, my experience is that in the offline setting, ERM oracle is usually not efficiently implementable, even if the function class is very simple, such as linear separators, and the data is sampled from a nice distribution such as Gaussian. As a result, even in these very simple offline settings, efficient learning algorithms can only achieve sth like Copt+ϵC opt + \epsilon error guarantee instead of opt+ϵopt + \epsilon guarantee and sometimes the output hypothesis is even improper. I would like to understand whether the assumption on the ERM oracle can be relaxed so that it matches the performance of known agnostic learning algorithms in the offline setting.

2 comments
AuthorsOpenReview ↗

Response to Reviewer kuqE

We thank reviewer kuqE for their time and attention to the paper. We have submitted a minor revision of the paper to clarify some of the points raised by the reviewers. Throughout our response, line, equation, and lemma numbers refer to the revised version.

On using an ERM oracle in our setting

Reviewers pMZz and kuqE ask about the computational implications of our weighted ERM oracle assumption. We would like to point out that relying on an ERM oracle is a standard computational primitive in the line of work on efficient online learning in general (see Kalai & Vempala, 2005; Hazan & Koren, 2016) and the literature on smoothed online learning essentially uses the same form of the weighted ERM we do (see Block et al., 2022; Haghtalab et al., 2022). It is used to establish a conceptual equivalence between statistical learning and online learning. As such, we present a reduction paradigm that is valid for any class of bounded VC dimension. We view obtaining computationally efficient guarantees of the form O(OPT)+εO(\mathrm{OPT}) + \varepsilon without access to an ERM oracle as an interesting open question.

On using an exact ERM oracle

Reviewer kuqE questions whether our methods can accommodate approximate ERM oracles. We can achieve similar guarantees as long as we can optimize the ERM objective up to additive error α\alpha in poly⁡(1/α)\operatorname{poly}(1/\alpha) time, and we have included the corresponding argument in the revision. In a nutshell, the only place that uses exactness of the minimizer is Lemma 4.4 (comparison with exponential weights; Lemma C.3 in the real-valued case) and, in particular, using Danskin’s theorem to express f^t(Xs)\hat f_t(X_s) as a negative gradient of the potential Φt(G)\Phi_t(G). By leveraging the smoothness of the map δ↦EΦt(G+δ)\delta \mapsto \mathbb E \Phi_t(G + \delta), we are able to show that a similar comparison holds for the approximate minimizer of the objective. See lines 441 to 453 for the remark we make in the main body, and see Lemma C.4 in the appendix for the formal statement.

References

Block, A., Dagan, Y., Golowich, N., & Rakhlin, A. (2022, June). Smoothed online learning is as easy as statistical learning. In Conference on Learning Theory (pp. 1716-1786). PMLR.

Haghtalab, N., Han, Y., Shetty, A., & Yang, K. (2022). Oracle-efficient online learning for smoothed adversaries. Advances in Neural Information Processing Systems, 35, 4072-4084.

Hazan, E., & Koren, T. (2016, June). The computational power of optimization in online learning. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (pp. 128-141).

Kalai, A., & Vempala, S. (2005). Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71(3), 291-307.

Dear Reviewer kuqE,

Thank you again for your review. As the discussion period ends in a few hours, we wanted to check whether our response addressed your questions, and we are happy to clarify anything further before the deadline.

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

This paper studies agnostic smoothed online learning when the base measure is unknown. For binary classes of VC dimension dd, it proposes a parameter-free Gaussian FTPL algorithm that achieves expected regret O~(dT/σ)\widetilde O(d\sqrt{T/\sigma}) with one weighted ERM oracle call per round. The paper also extends its analysis to real-valued function classes and convex 1-Lipschitz losses. Its main techniques are second-moment surprise bounds and a comparison between Gaussian FTPL and an exponential-weights reference algorithm.

Critical strengths
  • The paper addresses an important computational question in agnostic smoothed online learning with an unknown base measure.
  • The binary algorithm is simple and requires no knowledge of the base measure, smoothing parameter, or time horizon.
  • The analysis introduces potentially useful tools for handling adaptively chosen covariates.
Critical weaknesses
  • The proof of the general-loss extension appears incomplete. In Lemma C.2, Eq. (39) applies a norm-comparison theorem for a fixed function class to a class constructed from coupled data. The resulting selection dependence is not addressed.
  • The one-call-per-round guarantee applies to the binary algorithm. The general-loss extension uses tt oracle calls in round tt and averages their predictions; these costs and the potentially improper output should be more prominent in the statement of the contribution.
Questions for authors

In Lemma C.2, Fλ\mathcal F_\lambda is constructed from data coupled with X1:TX_{1:T} and Xˉ1:T\bar X_{1:T}, whereas the norm-comparison theorem used in Eq. (39) assumes a class fixed in advance. What justifies applying the theorem to this data-dependent class? If an additional argument is needed, can the authors provide it and clarify whether the regret bound in Theorem 3.2 remains unchanged?

2 comments
AuthorsOpenReview ↗

Response to Reviewer n5wY

We thank reviewer n5wY for their time and attention to the paper. We submitted a minor revision addressing the reviewers’ points, with changes in red. Throughout our response, line, equation, and lemma numbers refer to the revised version.

On multiple ERM calls per round

Reviewers pMZz and n5wY point out that our real-valued algorithm is improper in general and uses up to O(t)O(t) oracle calls per round, which leads to O(T2)O(T^2) oracle calls overall. We clarified this point in the revision: see lines 144-145, 306-308, and 502-503. The first states the oracle complexity right after the real-valued result is mentioned in the paper, the second states it after the formal description of the algorithm, and the third is in the conclusion paragraph.

While we agree that fewer oracle calls would be better, we emphasize that all prior approaches to this setting (beyond the i.i.d. case σ=1\sigma = 1) have runtime exponential in the dimension for sublinear regret. Thus, our paper resolves the question of polynomial learning in the agnostic unknown base measure smoothed online learning setting. It is an interesting open question to further improve the quadratic number of oracle calls of our algorithm, which we now state as an open question in the revision.

On Lemma C.2 and equation (41) (equation (39) in the submission)

We thank the reviewers pMZz and n5wY for catching this point. Indeed, to apply Theorem 10 from Block et al. (2024), we require a fixed class. This issue can be repaired by using Proposition A.1(ii) instead of (i) to construct the class Gλ\mathcal G_\lambda. This has a similar covering guarantee, except at a few exceptional points as in equation (22). We can repeat Maurey’s empirical method argument, and such replacement incurs additional error on the order K⋅(1+fatcλ(F))log⁡2CTσλK \cdot (1+\mathsf{fat}_{c\lambda}(\mathcal{F}))\log^2\frac{CT}{\sigma\lambda} in (41) due to the exceptional points in equation (22). This repairs the argument since Proposition A.1(ii) supplies a fixed class. This is a good catch, and we have included a revised proof of the statement in lines 1481–1544 in the revision. The resulting statement of the lemma is unchanged, since the additional error term that exceptional points contribute is of the same order as the previous bound. Thus, Theorem 3.2 holds as stated.

References

Block, A., Rakhlin, A., & Shetty, A. (2024). On the performance of empirical risk minimization with smoothed data. In The Thirty Seventh Annual Conference on Learning Theory. PMLR.

Thank you to the authors for the detailed response and revision. The updated proof and clarifications have addressed my concerns, and I will maintain my positive recommendation.

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

The paper studies online binary prediction when input distributions can change in response to the past, but remain dominated by one fixed, unknown reference distribution with density ratio at most 1/σ1/\sigma. Labels need not be perfectly predictable by the classifier class. For a class of VC dimension dd over TT rounds, the proposed Gaussian perturbation method achieves expected regret O~(dT/σ)\widetilde O(d\sqrt{T/\sigma}) using one exact weighted offline optimization call per round. It needs no reference samples or knowledge of σ\sigma, dd, or TT. Blanchard (2025) already gives the better bound of O~(dT/σ)\widetilde O(\sqrt{dT/\sigma}), but without this oracle reduction. The paper also extends the method to real-valued predictions and convex Lipschitz losses, using tt oracle calls on round tt.

Critical strengths

The binary theorem gives a generic one-call reduction to exact weighted offline optimization for agnostic prediction with adaptively changing smooth inputs and an unknown reference distribution. It removes the need for reference samples and parameter tuning while retaining square-root dependence on the horizon. This establishes a computational guarantee absent from the earlier statistically stronger result and is the main reason I support weak acceptance.

The proof addresses the difficulty of using perturbations attached only to dependent historical inputs. Gaussian identities control prediction differences and variances on past inputs; a strengthened second-moment argument transfers this control to current inputs. These comparisons provide useful technical content beyond the short algorithm itself, since ordinary i.i.d. VC generalization does not directly justify this transfer.

Critical weaknesses

My main concern is the significance of the computational improvement. Exact weighted optimization is tractable for classes such as thresholds, interval unions, and decision stumps, but the paper does not establish an advantage over specialized methods for these classes. For richer models, the oracle itself may be intractable, and the theorem does not justify replacing it with approximate training. The real-valued extension's tt calls per round further limit its computational appeal. These limitations leave the practical value of the reduction unclear and prevent me from giving a stronger recommendation.

The regret guarantee is worse by a factor of d\sqrt d than the earlier unknown-reference result, without evidence that this loss is necessary for oracle efficiency. Statistical learnability was already established. The contribution therefore rests on a computational trade-off rather than a better statistical guarantee. I regard this as useful but moderately significant theoretical progress.

Questions for authors

Clarification of computational significance: Can you identify a classifier class with an implementable exact weighted oracle for which the reduction offers a useful advantage over existing specialized methods? Please explain the resulting total computation, including processing the growing history. A concrete comparison would help me assess the significance of the oracle guarantee; I am not requesting a new application or experimental study during rebuttal.

Clarification of the proof: In equation (39) of Lemma C.2, the class appears to be chosen using the coupled sample, whereas the cited comparison theorem requires a fixed class. How is this application justified? A possible repair is to use the fixed cover from Proposition A.1(ii) and account for exceptional positions when approximating each mixture.

2 comments
AuthorsOpenReview ↗

Response to Reviewer pMZz

We thank reviewer pMZz for their time and attention to the paper. We submitted a minor revision addressing the reviewers’ points, with changes in red. Throughout our response, line, equation, and lemma numbers refer to the revised version.

On multiple ERM calls per round

Reviewers pMZz and n5wY point out that our real-valued algorithm is improper in general and uses up to O(t)O(t) oracle calls per round, which leads to O(T2)O(T^2) oracle calls overall. We clarified this point in the revision: see lines 144-145, 306-308, and 502-503. The first states the oracle complexity right after the real-valued result is mentioned in the paper, the second states it after the formal description of the algorithm, and the third is in the conclusion paragraph.

While we agree that fewer oracle calls would be better, we emphasize that all prior approaches to this setting (beyond the i.i.d. case σ=1\sigma = 1) have runtime exponential in the dimension for sublinear regret. Thus, our paper resolves the question of polynomial learning in the agnostic unknown base measure smoothed online learning setting. It is an interesting open question to further improve the quadratic number of oracle calls of our algorithm, which we now state as an open question in the revision.

On using an ERM oracle in our setting

Reviewers pMZz and kuqE ask about the computational implications of our weighted ERM oracle assumption. We would like to point out that relying on an ERM oracle is a standard computational primitive in the line of work on efficient online learning in general (see Kalai & Vempala, 2005; Hazan & Koren, 2016) and the literature on smoothed online learning essentially uses the same form of the weighted ERM we do (see Block et al., 2022; Haghtalab et al., 2022). It is used to establish a conceptual equivalence between statistical learning and online learning. We do not claim an advantage over specialized methods for simple classes such as thresholds or stumps. Rather, we present a reduction paradigm that is valid for any class of bounded VC dimension, which is a new and general result.

On Lemma C.2 and equation (41) (equation (39) in the submission)

We thank the reviewers pMZz and n5wY for catching this point. Indeed, to apply Theorem 10 from Block et al. (2024), we require a fixed class. This issue can be repaired by using Proposition A.1(ii) instead of (i) to construct the class Gλ\mathcal G_\lambda. This has a similar covering guarantee, except at a few exceptional points as in equation (22). We can repeat Maurey’s empirical method argument, and such replacement incurs additional error on the order K⋅(1+fatcλ(F))log⁡2CTσλK \cdot (1+\mathsf{fat}_{c\lambda}(\mathcal{F}))\log^2\frac{CT}{\sigma\lambda} in (41) due to the exceptional points in equation (22). This repairs the argument since Proposition A.1(ii) supplies a fixed class. This is a good catch, and we have included a revised proof of the statement in lines 1481–1544 in the revision. The resulting statement of the lemma is unchanged, since the additional error term that exceptional points contribute is of the same order as the previous bound. Thus, Theorem 3.2 holds as stated.

On d\sqrt{d} factor

Indeed, the regret guarantee in the binary case is off the statistical one by a factor of d\sqrt{d}, and the question we address is computational. We emphasize that the computational landscape of this problem has remained challenging, and the only prior work achieving an oracle-efficient guarantee in the agnostic setting with an unknown base measure is that of Wu et al. (2024), who (a) only give guarantees for σ=1\sigma = 1 in our setting and (b) achieve a substantially worse regret bound of T3/4T^{3/4}. This paper resolves the open problem and brings the rate down to T\sqrt{T}, modulo suboptimal dimension dependence.

References

Block, A., Dagan, Y., Golowich, N., & Rakhlin, A. (2022, June). Smoothed online learning is as easy as statistical learning. In Conference on Learning Theory (pp. 1716-1786). PMLR.

Block, A., Rakhlin, A., & Shetty, A. (2024). On the performance of empirical risk minimization with smoothed data. In The Thirty Seventh Annual Conference on Learning Theory. PMLR.

Haghtalab, N., Han, Y., Shetty, A., & Yang, K. (2022). Oracle-efficient online learning for smoothed adversaries. Advances in Neural Information Processing Systems, 35, 4072-4084.

Hazan, E., & Koren, T. (2016, June). The computational power of optimization in online learning. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (pp. 128-141).

Kalai, A., & Vempala, S. (2005). Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71(3), 291-307.

Wu, C., Sima, J., & Szpankowski, W. (2024, June). Oracle-efficient hybrid online learning with unknown distribution. In The Thirty Seventh Annual Conference on Learning Theory (pp. 4992-5018). PMLR.

Dear Reviewer pMZz,

Thank you again for your review. As the discussion period ends in a few hours, we wanted to check whether our response addressed your questions, and we are happy to clarify anything further before the deadline.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.