Dimension-Optimal Dynamic Regret in Exp-Concave Online Learning

Tracking changing comparators is a central problem in online learning. For exp-concave losses, previous work established the T1/3PT2/3 dependence on the horizon T and Euclidean path length PT for fixed dimension, while the optimal cost of dimension remained unresolved. We resolve this question by establishing a sharp d1/3 curved dimension factor, improving the d2/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 ℝd that adapts to the unknown path length and, under fixed dimension-independent diameter, gradient, and curvature parameters, guarantees operatornameRegT(u1:T) ≤ widetildeOleft(d+minleftd1/3T1/3PT2/3,√TPT,Trightright). A matching lower bound on a diameter-one Euclidean ball establishes the minimax frontier up to logarithmic factors when Tgtrsim d2, 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(log2 T) Gaussian states, uses one gradient per round, and runs in time near-linear in T under a Mahalanobis-projection oracle.