Metraipolis › archive › dc_a045e7c3632b

Dimension-Optimal Dynamic Regret in Exp-Concave Online Learning — arXiv:2610.20187

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.20187
License (as archived)
CC0-1.0
Archived
2026-10-15T14:19:45.383Z
SHA-256 of the archived text
1087ce7fd5dbcbef53d9d36004a23e605862b594720bb59135890318b3a7e584
Stable URL of this page
https://metraipolis.com/documento/dc_a045e7c3632b

How to cite

Dimension-Optimal Dynamic Regret in Exp-Concave Online Learning — arXiv:2610.20187 — arXiv (en), https://arxiv.org/abs/2610.20187 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_a045e7c3632b (Metraipolis archive dc_a045e7c3632b, sha256 1087ce7fd5dbcbef53d9d36004a23e605862b594720bb59135890318b3a7e584)
BibTeX
@misc{dca045e7c3632b,
  title = {Dimension-Optimal Dynamic Regret in Exp-Concave Online Learning — arXiv:2610.20187},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.20187},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_a045e7c3632b; sha256 1087ce7fd5dbcbef53d9d36004a23e605862b594720bb59135890318b3a7e584},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.20187. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (cs.LG) ; Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2610.20187 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T13:53:35.709Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).