破解专家问题与在线凸优化的极小极大交替后悔率，发现其与时间无关。
Minimax Alternating Regret for the Experts Problem and Online Convex Optimization
- 提出修正版Hedge算法，通过抵消不利曲率实现最优后悔率。
- 证明d个专家的最小最大交替后悔为Θ(log d)，与时间T无关。
- 适用于在线学习、博弈论等场景，适合研究最优策略设计者。
本文研究在线凸优化（OCO）中的交替后悔问题，受双人博弈中交替学习动态成功的启发。尽管已有研究在损失函数和可行域满足特定假设下证明了o(√T)的交替后悔可实现，但专家问题的极小极大后悔率仍悬而未决。本文通过建立匹配的上下界，解决了该问题：对于d个专家问题，极小极大交替后悔为Θ(log d)，与时间跨度T无关，显著优于此前Hait等人[2025]提出的O(T^{1/3}log^{2/3}d)。进一步将结果扩展至d维紧凸集上的通用OCO，证明最坏情况下的极小极大交替后悔为Θ(d log(1 + T/d))，远优于现有O((d log T)^{2/3}T^{1/3})上界，并解答了Cevher等人[2023]及Hait等人[2025]提出的问题。技术上，专家问题的上界通过修正Hedge算法实现，其中精心设计的修正项抵消了交替后悔分析中的不利曲率；该方法被推广至连续动作集，获得最优的OCO交替后悔率。下界方面，专家构造通过反复剔除一半候选专家实现，而OCO下界则采用单位圆盘上的多尺度构造替代离散消除。
原文摘要 · Abstract (English)
In this paper, we study alternating regret in online convex optimization (OCO), motivated by the success of alternating learning dynamics in two-player games. Although previous works have shown that $o(\sqrt{T})$ alternating regret is achievable under various assumptions on the loss functions and feasible domains, the minimax regret rate has remained open even for the expert problem. In this paper, we resolve this question by showing matching lower and upper bounds for both the expert problem and general OCO. Somewhat surprisingly, for the $d$-expert problem, we show that the minimax alternating regret is $Θ(\log d)$, independent of the horizon $T$. This significantly improves upon the best-known $\mathcal{O}(T^{1/3}\log^{2/3} d)$ established by Hait et al. [2025]. We further extend our results to general OCO over a $d$-dimensional compact convex set and prove that the worst-case minimax alternating regret is $Θ\left(d\log \left(1+\frac{T}{d}\right)\right)$, also significantly improving upon the best-known $\mathcal{O}((d\log T)^{2/3}T^{1/3})$ upper bound and resolving the open problem posed by Cevher et al. [2023], Hait et al. [2025]. Technically, our upper bound for the expert problem is achieved by a corrected variant of Hedge, in which carefully designed correction terms cancel the unfavorable curvature arising in the alternating-regret analysis. We extend the same corrected-potential argument to continuous action sets to obtain the optimal alternating-regret rate for OCO. For the lower bounds, the expert construction repeatedly eliminates half of the candidate experts, while the OCO lower bound instance construction replaces this discrete elimination by a more involved multiscale construction on the unit disk.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。