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.
We establish a $\widetildeΩ(d^{5/4}\sqrt T)$ lower bound on the minimax expected regret of stochastic bandit convex optimization of $1$-Lipschitz functions on the Euclidean ball. This presents the first nontrivial regret lower bound that grows faster than $d\sqrt{T}$ for this problem, establishing that stochastic bandit convex optimization is fundamentally harder than linear bandits. The hard class of convex functions we construct takes the following form in dimension $2d$: for an action $a = (a^1,a^2) \in \mathbb{B}^{2d}_2$, each function is the scaled soft maximum of a "tube", $r^{-1} \| W^\star a^1 - \frac{r}{8\varepsilon} a^2 \|_2$ (hyperparameterized by $\varepsilon,r$), and a squared distance function, $\frac12 \| a^1 - u^\star \|_2^2 - \frac12 \| u^\star \|_2^2$. Here, $W^\star \in \mathbb{R}^{d \times d}$ is an unknown linear transformation, and $u^\star \in \mathbb{R}^{d}$ is an unknown vector which must be learned to minimize the function. Observations are informative about $u^\star$ only when the learner's action lies near the tube determined by $W^\star$, satisfying $a^2 \approx \frac{8\varepsilon}{r} W^\star a^1$: thus the learner must either find this tube without knowing $W^\star$, or spend observations learning useful directions of $W^\star$. Formally, our regret analysis exploits this tradeoff by bounding the posterior spread of Fisher information matrices obtained under an adaptive sequence of actions. Together, these ingredients give a sample complexity lower bound of $\widetildeΩ(d^{5/2}/\varepsilon^2)$ to find an $\varepsilon$-optimal action, which translates to an $\widetildeΩ (d^{5/4} \sqrt{T})$ regret lower bound. We also extend this lower bound to the unconstrained setting where the action space is $\mathbb{R}^d$.