View PDF HTML (experimental)

Abstract:The performance of online mirror descent depends critically on the geometry induced by its mirror map, yet standard algorithms largely rely on two canonical choices: Euclidean and entropic geometry. We show that these two geometries can both be substantially suboptimal when loss gradients are sparse. We introduce a family of randomized block-norm mirror maps that interpolates between Euclidean and entropic geometries and adapts to intermediate sparsity structure. For several standard convex sets, including $\ell_p$ balls, ellipsoids, boxes, and Minkowski sums of norm balls, we prove polynomial-in-dimension improvements in regret bounds over the better of online projected gradient descent and exponentiated gradient. We further construct explicit online convex optimization instances for which these improvements are realized: on a simple polytope, an intermediate block geometry achieves a $\text{poly}(d)$ separation in regret from both Euclidean and entropic geometries in dimension $d$, while on the probability simplex we obtain a separation of order $\Omega(\sqrt{\log d}/\log\log d)$. Finally, we study geometry selection when sparsity is unknown. We show that naively alternating between mirror maps can incur linear regret, even though either mirror map alone has sublinear regret, and give a Hedge meta-algorithm that competes with the best mirror map in a finite portfolio. For random block geometries, this yields regret within an $O(\sqrt{\log\log d})$ factor of the best random uniform block norm chosen in hindsight.

Submission history

From: Jai Moondra [view email]
[v1] Fri, 13 Feb 2026 18:37:26 UTC (560 KB)
[v2] Fri, 11 Sep 2026 14:48:40 UTC (186 KB)