Smoothed Online Classification can be Harder than Batch Classification

We thank the reviewer for their comments.

We are unsure what the reviewer meant by "They didn’t show a necessary and sufficient condition that a hypothesis class learnable under the PAC learning is also learnable under the smoothed online learning." We would like to point out that the main result of our work shows that PAC learnability is provably not sufficient for smoothed online classification for unbounded label spaces. However, PAC learnability is certainly necessary for smoothed online classification for unbounded label spaces.

We thank the reviewer for noting that our results "enhance our understanding of the smoothed online learning problem." We address their concerns below.

• Our sufficiency condition strictly improves the sufficiency condition presented in Haghtalab's thesis, as noted in lines 312-316. Specifically, there are classes where the VC dimension is infinite and the upper bounds in Haghtalab's thesis are therefore vacuous, but our sufficiency condition still provides a meaningful upper bound. We believe that the significance of our sufficiency condition is more conceptual than technical. Our upper bound highlights that distribution-dependent complexity measures quantify the rates more precisely than distribution-independent complexity measures. This is an important point worth highlighting because any complexity measure that characterizes smoothed online learnability has to be a joint property of both $\mathcal{H}$ and $\mu$ (as noted in the Discussion section). Lastly, we only considered non-adaptive adversaries because the primary focus of our work is the hardness result. However, our upper bounds can be extended to adaptive adversaries using the coupling argument from [1].

• We note that Theorem 3.3 shows that, in terms of regret bound, the separation between PAC learnability and smoothed online learnability holds even for finite label spaces as long as the size of the label space is $\geq 2^{T \log(T)}$. More precisely, for any time horizon $T$, there exists a class $\mathcal{H}_T \subseteq \mathcal{Y}^{\mathcal{X}}$ with $|\mathcal{Y}|\geq 2^{T \log{T}}$ for which its PAC error bound is $O\left(\sqrt{\frac{\log{n}}{n}} \right)$, but its regret is $\Omega(T)$ (or average regret is $\Omega(1)$). That is, $\mathcal{H}_T$ has a vanishing PAC upper bound (independent of $T$) but a constant non-vanishing average regret lower bound. The infinite label space is required only to show a separation of learnability. In particular, showing that the class is non-learnable according to Definition 1 requires establishing $\Omega(1)$ average regret for every $T$ even as $T \to \infty$.

• Finally, we disagree with the reviewer that multiclass classification with infinite label sets is not ``a not very extensively studied learning model." This setting has been studied in several seminal works in learning theory in the last 40 years beginning with [2,3] and more recently in [4,5,6] to name a few. Studying infinite label spaces is important for understanding when one can establish learning guarantees independent of the label size. This is quite a practical question as many modern machine learning paradigms have massive label space, such as in face recognition and protein structure prediction, where the dependence of label size in learning bounds would be undesirable.

[1] Haghtalab, Nika, Tim Roughgarden, and Abhishek Shetty. ``Smoothed analysis with adaptive adversaries." Journal of the ACM 71.3 (2024): 1-34.

[2] Balas K. Natarajan. Some results on learning. 1988.

[3] B. K. Natarajan. On learning sets and functions. Machine Learning, 4:67–97, 1989.

[4] A. Daniely, S. Sabato, S. Ben-David, and S. Shalev-Shwartz. Multiclass learnability and the ERM principle. In Proceedings of the 24th Conference on Learning Theory, 2011.

[5] A. Daniely and S. Shalev-Shwartz. Optimal learners for multiclass problems. In Proceedings of the 27th Conference on Learning Theory, 2014.

[6] N. Brukhim, D. Carmon, I. Dinur, S. Moran, and A. Yehudayoff. A characterization of multiclass learnability. In Proceedings of the 63rd Annual IEEE Symposium on Foundations of Computer Science, 2022.

We thank the reviewers for their comments and address their concerns below.

Weaknesses

1. In online classification, smoothness is only an assumption on the instances $x_1, ..., x_T$, and the labels can still be adversarial. This is the standard smooth model considered in [1,2,3,4]. If by 'adversarial labels' the reviewer means noisy labels, then we would like to clarify that our hardness result is actually derived in the realizable setting. This is established in the math display between lines 280 and 281, where we show the existence of a hypothesis that perfectly labels the data and achieves $0$ cumulative loss.

2. The reviewer is correct in that the sufficient condition is not necessary. We mention this fact in lines 97-99 and formalize it in Theorem 4.3. As noted in the Discussion section, the smoothed model allows some pathological edge cases that make characterizing learnability difficult.

Questions

1. We would like to clarify that our hardness result is in the realizable setting. This is established in the math display between lines 280 and 281, where we show the existence of a hypothesis that perfectly labels the data and achieves $0$ cumulative loss.

2. The notion of stochastic sequential cover provided in Definition 1 of (Wu et al. 2023) does not characterize smoothed learnability. In fact, this can be established using the same examples used in the proof of Theorem 4.3. To see why it is not sufficient, consider $\mathcal{X}=[0,1]$ and $\mathcal{H}= \lbrace{ x \mapsto 1[x \in S]\, : S \subset \mathcal{X} \text{ and } |S|<\infty\rbrace}$. Let $\mathcal{P}$ denote set of all distributions on $\mathcal{X}^{T}$ such that for any $\nu \in \mathcal{P}$, its marginal at each $t$ is $\sigma$-smooth with respect to $\mu=\text{Uniform}(\mathcal{X})$ for some fixed $\sigma>0$. It is easy to see that the size of the stochastic sequential cover of $\mathcal{H}$ with respect to $\mathcal{P}$ under $0$-$1$ metric is $1$ (see proof of Theorem 4.3 (i) for details). However, as shown in Theorem 4.3 (i), this class is not learnable under the smoothed model. On the other hand, the class $\mathcal{H} = \lbrace{x \mapsto a: a \in \mathbb{N}\rbrace}$ shows that the stochastic sequential cover is not necessary, as its size of sequential cover for any distribution family $\mathcal{P}$ is $\infty$.

3. Realizable and agnostic learnability are equivalent for smoothed online classification even when the label space is unbounded. We have some ongoing work that establishes this result using an adaptation of Theorem 11 in [6] for infinite label spaces.

[1] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning: Stochastic, constrained, and smoothed adversaries. Advances in neural information processing systems, 24, 2011.

[2] Nika Haghtalab. Foundation of Machine Learning, by the People, for the People. PhD thesis, Carnegie Mellon University, 2018.

[3] Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. Smoothed analysis of online and differentially private learning. Advances in Neural Information Processing Systems, 33:9203–9215,379 2020.

[4] Adam Block, Yuval Dagan, Noah Golowich, and Alexander Rakhlin. Smoothed online learning is as easy as statistical learning. In Conference on Learning Theory, pages 1716–1786. PMLR, 2022.

[5] Wu C, Heidari M, Grama A, Szpankowski W. Expected Worst Case Regret via Stochastic Sequential Covering. Transactions on Machine Learning Research, 2023.

[6] Raman, Vinod, Unique Subedi, and Ambuj Tewari. "A Characterization of Multioutput Learnability." arXiv preprint arXiv:2301.02729 (2023).

We thank the reviewer for finding our paper well-written. We will make sure to define $\Sigma$ in the camera-ready version.