Prediction against a limited adversary
This work addresses robust online learning for scenarios with bounded adversarial influence, though it appears incremental as it builds on existing prediction with expert advice frameworks.
The paper tackles the problem of prediction with expert advice under adversarial corruption limited to one expert, characterizing the long-time behavior of the game's value function using viscosity theory and providing lower and upper bounds for regret growth without comparison results.
We study the problem of prediction with expert advice with adversarial corruption where the adversary can at most corrupt one expert. Using tools from viscosity theory, we characterize the long-time behavior of the value function of the game between the forecaster and the adversary. We provide lower and upper bounds for the growth rate of regret without relying on a comparison result. We show that depending on the description of regret, the limiting behavior of the game can significantly differ.