Combining Online Learning Guarantees
This provides a simple yet effective method for improving adaptivity and efficiency in online learning, though it appears incremental as it builds on existing parameter-free algorithms.
The paper tackles the problem of combining different online learning algorithms by showing that simply adding their iterates produces a single algorithm whose regret equals the minimum of the two base algorithms, enabling efficient adaptation to multiple norms and dimension-free guarantees. It also extends this approach to create optimistic online learning algorithms that achieve the first optimistic regret guarantees in unconstrained settings while ensuring they never perform worse than non-optimistic versions.
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.