Distributionally-Constrained Adversaries in Online Learning
This work addresses the challenge of bridging adversarial and stochastic settings in online learning for researchers, providing a flexible framework that generalizes smoothed analysis and offers insights into learnability conditions.
The paper tackles the problem of online learning with distributionally constrained adversaries, characterizing which distribution classes are learnable against both oblivious and adaptive adversaries, and showing that for function classes like linear classifiers, learning can be achieved without prior knowledge of the distribution class.
There has been much recent interest in understanding the continuum from adversarial to stochastic settings in online learning, with various frameworks including smoothed settings proposed to bridge this gap. We consider the more general and flexible framework of distributionally constrained adversaries in which instances are drawn from distributions chosen by an adversary within some constrained distribution class [RST11]. Compared to smoothed analysis, we consider general distributional classes which allows for a fine-grained understanding of learning settings between fully stochastic and fully adversarial for which a learner can achieve non-trivial regret. We give a characterization for which distribution classes are learnable in this context against both oblivious and adaptive adversaries, providing insights into the types of interplay between the function class and distributional constraints on adversaries that enable learnability. In particular, our results recover and generalize learnability for known smoothed settings. Further, we show that for several natural function classes including linear classifiers, learning can be achieved without any prior knowledge of the distribution class -- in other words, a learner can simultaneously compete against any constrained adversary within learnable distribution classes.