Structured Prediction in Online Learning
This work addresses structured prediction for online learning scenarios, including non-stationary and adversarial data, but is incremental as it builds on existing supervised learning frameworks.
The paper tackles structured prediction in online learning by proposing algorithms that generalize optimal supervised methods and achieve the same excess risk bound even with non-i.i.d. data, with a second algorithm bounding stochastic regret based on data distribution variation.
We study a theoretical and algorithmic framework for structured prediction in the online learning setting. The problem of structured prediction, i.e. estimating function where the output space lacks a vectorial structure, is well studied in the literature of supervised statistical learning. We show that our algorithm is a generalisation of optimal algorithms from the supervised learning setting, and achieves the same excess risk upper bound also when data are not i.i.d. Moreover, we consider a second algorithm designed especially for non-stationary data distributions, including adversarial data. We bound its stochastic regret in function of the variation of the data distributions.