We study online classification under smoothed adversaries. In this setting,
at each time point, the adversary draws an example from a distribution that has
a bounded density with respect to a fixed base measure, which is known apriori
to the learner. For binary classification and scalar-valued regression,
previous works \citep{haghtalab2020smoothed, block2022smoothed} have shown that
smoothed online learning is as easy as learning in the iid batch setting under
PAC model. However, we show that smoothed online classification can be harder
than the iid batch classification when the label space is unbounded. In
particular, we construct a hypothesis class that is learnable in the iid batch
setting under the PAC model but is not learnable under the smoothed online
model. Finally, we identify a condition that ensures that the PAC learnability
of a hypothesis class is sufficient for its smoothed online learnability.

在线分类在平滑对手条件下的学习与 PAC 模型下的批处理学习相对应，当标签空间无界时，平滑在线分类可能比批处理分类更困难，但我们找到了一个条件，确保假设类的 PAC 可学习性足以保证其平滑在线可学习性。