{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-02-13","reactions":{}}