Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper establishes the dimension-optimal dynamic regret bound for exp-concave online learning, achieving a $d^{1/3}$ factor for the dimension's influence on regret, a significant improvement over prior $d^{2/3}$ bounds. The authors introduce a novel full-information learner that adapts to unknown path length and, under standard parameter constraints, achieves a regret bound of $\widetilde{O}(d + \min\{d^{1/3}T^{1/3}P_T^{2/3}, \sqrt{TP_T}, T\})$. A matching lower bound on a diameter-one Euclidean ball confirms this minimax optimality for relevant regimes, demonstrating an unavoidable cost of learning across directions.
The cost of tracking changing comparators in exp-concave online learning is reduced by a factor of $d^{1/3}$, resolving the dimension's optimal dependence.
Tracking changing comparators is a central problem in online learning. For exp-concave losses, previous work established the $T^{1/3}P_T^{2/3}$ dependence on the horizon $T$ and Euclidean path length $P_T$ for fixed dimension, while the optimal cost of dimension remained unresolved. We resolve this question by establishing a sharp $d^{1/3}$ curved dimension factor, improving the $d^{2/3}$ factor of recent switching and interval reductions [1, 2]. To achieve this improvement, we develop a proper, full-information learner on compact convex subsets of $\mathbb{R}^d$ that adapts to the unknown path length and, under fixed dimension-independent diameter, gradient, and curvature parameters, guarantees $$\operatorname{Reg}_T(u_{1:T}) \le \widetilde{O}\left(d+\min\left\{d^{1/3}T^{1/3}P_T^{2/3},\sqrt{TP_T},T\right\}\right).$$ A matching lower bound on a diameter-one Euclidean ball establishes the minimax frontier up to logarithmic factors when $T\gtrsim d^2$, including the transition from the curved rate to larger path budgets. The lower bound already holds for losses that depend on only one coordinate per round, isolating an unavoidable cost of learning across directions. Our upper bound follows from square-root Gaussian KL control of comparator movement and a cancellation argument that pays for history restarts. The curved learner maintains $O(\log^2 T)$ Gaussian states, uses one gradient per round, and runs in time near-linear in $T$ under a Mahalanobis-projection oracle.