Online mirror descent and dual averaging: keeping pace in the dynamic case
This work addresses a theoretical bottleneck in online convex optimization for researchers and practitioners, providing incremental improvements to algorithm design.
The paper tackled the problem of online mirror descent (OMD) performing poorly with dynamic learning rates compared to dual averaging (DA), by introducing a stabilization technique to OMD. The result showed that stabilized-OMD achieves essentially the same regret bounds as DA, enabling identical performance guarantees in many applications under dynamic learning rates.
Online mirror descent (OMD) and dual averaging (DA) -- two fundamental algorithms for online convex optimization -- are known to have very similar (and sometimes identical) performance guarantees when used with a fixed learning rate. Under dynamic learning rates, however, OMD is provably inferior to DA and suffers a linear regret, even in common settings such as prediction with expert advice. We modify the OMD algorithm through a simple technique that we call stabilization. We give essentially the same abstract regret bound for OMD with stabilization and for DA by modifying the classical OMD convergence analysis in a careful and modular way that allows for straightforward and flexible proofs. Simple corollaries of these bounds show that OMD with stabilization and DA enjoy the same performance guarantees in many applications -- even under dynamic learning rates. We also shed light on the similarities between OMD and DA and show simple conditions under which stabilized-OMD and DA generate the same iterates.