Online Learning with Local Permutations and Delayed Feedback
  We propose an Online Learning with Local Permutations (OLLP) setting, in
which the learner is allowed to slightly permute the \emph{order} of the loss
functions generated by an adversary. On one hand, this models natural
situations where the exact order of the learner's responses is not crucial, and
on the other hand, might allow better learning and regret performance, by
mitigating highly adversarial loss sequences. Also, with random permutations,
this can be seen as a setting interpolating between adversarial and stochastic
losses. In this paper, we consider the applicability of this setting to convex
online learning with delayed feedback, in which the feedback on the prediction
made in round $t$ arrives with some delay $\tau$. With such delayed feedback,
the best possible regret bound is well-known to be $O(\sqrt{\tau T})$. We prove
that by being able to permute losses by a distance of at most $M$ (for $M\geq
\tau$), the regret can be improved to $O(\sqrt{T}(1+\sqrt{\tau^2/M}))$, using a
Mirror-Descent based algorithm which can be applied for both Euclidean and
non-Euclidean geometries. We also prove a lower bound, showing that for
$M<\tau/3$, it is impossible to improve the standard $O(\sqrt{\tau T})$ regret
bound by more than constant factors. Finally, we provide some experiments
validating the performance of our algorithm.
