Combining Online Learning Guarantees
  We show how to take any two parameter-free online learning algorithms with
different regret guarantees and obtain a single algorithm whose regret is the
minimum of the two base algorithms. Our method is embarrassingly simple: just
add the iterates. This trick can generate efficient algorithms that adapt to
many norms simultaneously, as well as providing diagonal-style algorithms that
still maintain dimension-free guarantees. We then proceed to show how a variant
on this idea yields a black-box procedure for generating optimistic online
learning algorithms. This yields the first optimistic regret guarantees in the
unconstrained setting and generically increases adaptivity. Further, our
optimistic algorithms are guaranteed to do no worse than their non-optimistic
counterparts regardless of the quality of the optimistic estimates provided to
the algorithm.
