{"ID":2836745,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.19937","arxiv_id":"2511.19937","title":"Adaptivity and Universality: Problem-dependent Universal Regret for Online Convex Optimization","abstract":"Universal online learning aims to achieve optimal regret guarantees without requiring prior knowledge of the curvature of online functions. Existing methods have established minimax-optimal regret bounds for universal online learning, where a single algorithm can simultaneously attain $\\mathcal{O}(\\sqrt{T})$ regret for convex functions, $\\mathcal{O}(d \\log T)$ for exp-concave functions, and $\\mathcal{O}(\\log T)$ for strongly convex functions, where $T$ is the number of rounds and $d$ is the dimension of the feasible domain. However, these methods still lack problem-dependent adaptivity. In particular, no universal method provides regret bounds that scale with the gradient variation $V_T$, a key quantity that plays a crucial role in applications such as stochastic optimization and fast-rate convergence in games. In this work, we introduce UniGrad, a novel approach that achieves both universality and adaptivity, with two distinct realizations: UniGrad.Correct and UniGrad.Bregman. Both methods achieve universal regret guarantees that adapt to gradient variation, simultaneously attaining $\\mathcal{O}(\\log V_T)$ regret for strongly convex functions and $\\mathcal{O}(d \\log V_T)$ regret for exp-concave functions. For convex functions, the regret bounds differ: UniGrad.Correct achieves an $\\mathcal{O}(\\sqrt{V_T \\log V_T})$ bound while preserving the RVU property that is crucial for fast convergence in online games, whereas UniGrad.Bregman achieves the optimal $\\mathcal{O}(\\sqrt{V_T})$ regret bound through a novel design. Both methods employ a meta algorithm with $\\mathcal{O}(\\log T)$ base learners, which naturally requires $\\mathcal{O}(\\log T)$ gradient queries per round. To enhance computational efficiency, we introduce UniGrad++, which retains the regret while reducing the gradient query to just $1$ per round via surrogate optimization. We further provide various implications.","short_abstract":"Universal online learning aims to achieve optimal regret guarantees without requiring prior knowledge of the curvature of online functions. Existing methods have established minimax-optimal regret bounds for universal online learning, where a single algorithm can simultaneously attain $\\mathcal{O}(\\sqrt{T})$ regret for...","url_abs":"https://arxiv.org/abs/2511.19937","url_pdf":"https://arxiv.org/pdf/2511.19937v1","authors":"[\"Peng Zhao\",\"Yu-Hu Yan\",\"Hang Yu\",\"Zhi-Hua Zhou\"]","published":"2025-11-25T05:23:10Z","proceeding":"cs.LG","tasks":"[\"cs.LG\",\"math.OC\",\"stat.ML\"]","methods":"[]","has_code":false}