The performance of Online Mirror Descent (OMD) hinges on the geometry induced by its mirror map. Existing methods mainly rely on two canonical geometries—Euclidean and entropic—but both can be far from optimal when loss gradients are sparse. We introduce a family of randomized block‑norm mirror maps that smoothly interpolate between Euclidean and entropic geometries and adapt to intermediate sparsity patterns.
For several standard convex sets—including $\ell_p$ balls, ellipsoids, boxes, and Minkowski sums of norm balls—we prove that block‑norm OMD achieves regret bounds that improve polynomially in the dimension $d$ over the better of projected gradient descent and exponentiated gradient.
We also construct explicit online convex optimization instances that realize these gains: on a simple polytope, an intermediate block geometry yields a $\text{poly}(d)$ separation in regret from both Euclidean and entropic geometries; on the probability simplex we obtain a separation of order $\Omega(\sqrt{\log d}/\log\log d)$.
When sparsity is unknown, naïvely alternating between mirror maps can incur linear regret even though each map alone guarantees sublinear regret. To address this, we propose a Hedge meta‑algorithm that competes with the best mirror map in a finite portfolio. For random block geometries, this meta‑algorithm achieves regret within an $O(\sqrt{\log\log d})$ factor of the best random uniform block norm chosen in hindsight.
Review