[!t]
[1]
OnlineMirrorDescent\(\mathbf {x}_1 = \underset{\mathbf {x} \in \mathcal {X} \cap \mathcal {D}}{\arg \min } \,\Phi (\mathbf {x}) , \eta \) 
\(t = 1,2,\dots ,T\) 5cm// Incur a cost \(f_{\mathbf {r}_t}(\mathbf {x}_t)\) , and receive a gradient \( \nabla f_{\mathbf {r}_t}(\mathbf {x})\)
\(\hat{\mathbf {x}}_t= \nabla \Phi (\mathbf {x}_t)\) 5cm// Map primal point to dual point
\(\hat{\mathbf {y}}_{t+1} = \hat{\mathbf {x}}_t - \eta \nabla f_{\mathbf {r}_t}(\mathbf {x}_t)\) 5cm// Take gradient step in the dual
\(\mathbf {y}_{t+1} = \left(\nabla \Phi \right)^{-1}(\hat{\mathbf {y}}_{t+1})\) 5cm// Map dual point to a primal point
\(\mathbf {x}_{t+1}= \prod _{\mathcal {X} \cap \mathcal {D}}^\Phi (\mathbf {y}_{t+1})\) 5cm// Project new point onto feasible region

Online mirror descent (\(\text{OMD}_\Phi \) )


OMD [1]} is the online version of the mirror descent (MD) algorithm [2]} for convex optimization of a fixed, known function. The main premise behind mirror descent is that variables and gradients live into two distinct spaces: the primal space, for variables, and the dual space, for gradients. The two are linked via a function known as a mirror map. Contrary to standard gradient descent, updates using the gradient occur on the dual space; the mirror map is used to invert this update to a change on the primal variables. For several constrained optimization problems of interest, mirror descent leads to faster convergence compared to gradient descent [3]}. OMD arises by observing that MD is agnostic to whether the gradients are obtained from a fixed function, or a sequence revealed adversarially.
