  In the convex optimization approach to online regret minimization, many
methods have been developed to guarantee a $O(\sqrt{T})$ bound on regret for
subdifferentiable convex loss functions with bounded subgradients, by using a
reduction to linear loss functions. This suggests that linear loss functions
tend to be the hardest ones to learn against, regardless of the underlying
decision spaces. We investigate this question in a systematic fashion looking
at the interplay between the set of possible moves for both the decision maker
and the adversarial environment. This allows us to highlight sharp distinctive
behaviors about the learnability of piecewise linear loss functions. On the one
hand, when the decision set of the decision maker is a polyhedron, we establish
$\Omega(\sqrt{T})$ lower bounds on regret for a large class of piecewise linear
loss functions with important applications in online linear optimization,
repeated zero-sum Stackelberg games, online prediction with side information,
and online two-stage optimization. On the other hand, we exhibit $o(\sqrt{T})$
learning rates, achieved by the Follow-The-Leader algorithm, in online linear
optimization when the boundary of the decision maker's decision set is curved
and when $0$ does not lie in the convex hull of the environment's decision set.
Hence, the curvature of the decision maker's decision set is a determining
factor for the optimal learning rate. These results hold in a completely
adversarial setting.

Machine Learning