- 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 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 , or . 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 error guarantee instead of 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
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.
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)+ε 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 α in poly(1/α) 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) as a negative gradient of the potential Φt(G). By leveraging the smoothness of the map δ↦EΦt(G+δ), 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.