aiqbench analysis
This research advances online convex optimization by introducing randomized block-norm geometries that significantly outperform standard Euclidean and entropic approaches when loss gradients are sparse. The study provides rigorous regret bounds for various convex sets and proposes a meta-algorithm to handle scenarios where sparsity patterns are unknown. These theoretical improvements offer more efficient convergence guarantees for high-dimensional machine learning problems involving sparse data structures.
Block-Norm Geometries for Online Mirror Descent with Sparse Losses
arXiv:2602.13177v2 Announce Type: replace-cross 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.
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.
Optimization and Control (math.OC); Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG)
arXiv:2602.13177 [math.OC]
(or arXiv:2602.13177v2 [math.OC] for this version)
https://doi.org/10.48550/arXiv.2602.13177 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 321 words
Related coverage
AF-Muon: An AdamW-Free Muon Optimizer for Tied-Embedding Models
arXiv · Oct 2, 2026
Subspace-Aware Sparse Autoencoders for Effective Mechanistic Interpretability
arXiv · Jun 6, 2026
Exact-Form Regret for Gradient Descent, Mirror Descent and Follow-the-Regularized-Leader
arXiv · Sep 10, 2026
[AINews] High Taste Testers Ep. 1
Latent Space · Oct 17, 2026