{"ID":2824200,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.23190","arxiv_id":"2512.23190","title":"A Simple, Optimal and Efficient Algorithm for Online Exp-Concave Optimization","abstract":"Online eXp-concave Optimization (OXO) is a fundamental problem in online learning, where the goal is to minimize regret when loss functions are exponentially concave. The standard algorithm, Online Newton Step (ONS), guarantees an optimal $O(d \\log T)$ regret, where $d$ is the dimension and $T$ is the time horizon. Despite its simplicity, ONS may face a computational bottleneck due to the Mahalanobis projection at each round. This step costs $Ω(d^ω)$ arithmetic operations for bounded domains, even for simple domains such as the unit ball, where $ω\\in (2,3]$ is the matrix-multiplication exponent. As a result, the total runtime can reach $\\tilde{O}(d^ωT)$, particularly when iterates frequently oscillate near the domain boundary. This paper proposes a simple variant of ONS, called LightONS, which reduces the total runtime to $O(d^2 T + d^ω\\sqrt{T \\log T})$ while preserving the optimal regret. Deploying LightONS with the online-to-batch conversion implies a method for stochastic exp-concave optimization with runtime $\\tilde{O}(d^3/ε)$, thereby answering an open problem posed by Koren [2013]. The design leverages domain-conversion techniques from parameter-free online learning and defers expensive Mahalanobis projections until necessary, thereby preserving the elegant structure of ONS and enabling LightONS to act as an efficient plug-in replacement in broader scenarios, including gradient-norm adaptivity, parametric stochastic bandits, and memory-efficient OXO.","short_abstract":"Online eXp-concave Optimization (OXO) is a fundamental problem in online learning, where the goal is to minimize regret when loss functions are exponentially concave. The standard algorithm, Online Newton Step (ONS), guarantees an optimal $O(d \\log T)$ regret, where $d$ is the dimension and $T$ is the time horizon. Des...","url_abs":"https://arxiv.org/abs/2512.23190","url_pdf":"https://arxiv.org/pdf/2512.23190v2","authors":"[\"Yi-Han Wang\",\"Peng Zhao\",\"Zhi-Hua Zhou\"]","published":"2025-12-29T03:59:51Z","proceeding":"cs.LG","tasks":"[\"cs.LG\",\"math.OC\",\"stat.ML\"]","methods":"[\"Generative Adversarial Network\"]","has_code":false}