  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.
