Abstract
Alternating Regret for Online Convex Optimization
Proceedings of 38th Conference on Learning Theory, COLT 2025, Vol.291, pp.2632-2633
2025
Abstract
Motivated by alternating learning dynamics in two-player games, a recent work by Cevher et al. (2024) shows that o(T−−√) alternating regret is possible for any T-round adversarial Online Linear Optimization (OLO) problem, and left as an open question whether the same is true for general Online Convex Optimization (OCO). We answer this question in the affirmative by showing that the continuous Hedge algorithm achieves O~(d23T13) alternating regret for any adversarial d-dimensional OCO problems. We show that this implies an alternating learning dynamic that finds a Nash equilibrium for any convex-concave zero-sum games or a coarse correlated equilibrium for any convex two-player general-sum games at a rate of O~(d23/T23). To further improve the time complexity and/or the dimension dependence, we propose another simple algorithm, Follow-the-Regularized-Leader with a regularizer whose convex conjugate is 3rd-order smooth, for OCO with smooth and self-concordant loss functions (such as linear or quadratic losses). We instantiate our algorithm with different regularizers and show that, for example, when the decision set is the ℓ2 ball, our algorithm achieves O~(T25) alternating regret with no dimension dependence (and a better O~(T13) bound for quadratic losses). We complement our results by showing some algorithm-specific alternating regret lower bounds, including a somewhat surprising Ω(T−−√) lower bound for a Regret Matching variant that is widely used in alternating learning dynamics.
Details
- Title: Subtitle
- Alternating Regret for Online Convex Optimization
- Creators
- Soumita Hait - University of Southern CaliforniaPing Li - Shanghai University of Finance and EconomicsHaipeng Luo - University of Southern CaliforniaMengxiao Zhang - University of Iowa, United States
- Resource Type
- Abstract
- Publication Details
- Proceedings of 38th Conference on Learning Theory, COLT 2025, Vol.291, pp.2632-2633
- ISSN
- 2640-3498
- eISSN
- 2640-3498
- Grant note
- IIS-1943607 / National Science Foundation (100000001) National Science Foundation (http://data.elsevier.com/vocabulary/SciValFunders/100000001) IIS-1943607 / National Science Foundation (http://data.elsevier.com/vocabulary/SciValFunders/100000001)
- Language
- English
- Date published
- 2025
- Academic Unit
- Business Analytics
- Record Identifier
- 9984962546802771
Metrics
23 Record Views