Id: arxiv/2602.13177 Url: https://arxiv.org/abs/2602.13177 Tags: math.OC, cs.DS, cs.LG Score: 0 Title: Block-Norm Geometries for Online Mirror Descent with Sparse Losses Domain: math.OC Source: arxiv Authors: Swati Gupta, Jai Moondra, Mohit Singh Reviews: 0 Subject: math.OC Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-02-13 Page: https://delphi.science/r/arxiv/2602.13177 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…