Metraipolis › archive › dc_e348c987dae8
Nested Convex-Body Chasing for Online Optimization with Evolving Feasible Sets — arXiv:2608.29074
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.29074
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-17T07:44:02.577Z
- SHA-256 of the archived text
a02c3897848bac8f2c4b11c3a8e85ef8d3de150863ed73bb1f459b4374fb0f5c- Stable URL of this page
https://metraipolis.com/documento/dc_e348c987dae8
How to cite
Nested Convex-Body Chasing for Online Optimization with Evolving Feasible Sets — arXiv:2608.29074 — arXiv (en), https://arxiv.org/abs/2608.29074 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e348c987dae8 (Metraipolis archive dc_e348c987dae8, sha256 a02c3897848bac8f2c4b11c3a8e85ef8d3de150863ed73bb1f459b4374fb0f5c)
BibTeX
@misc{dce348c987dae8,
title = {Nested Convex-Body Chasing for Online Optimization with Evolving Feasible Sets — arXiv:2608.29074},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.29074},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e348c987dae8; sha256 a02c3897848bac8f2c4b11c3a8e85ef8d3de150863ed73bb1f459b4374fb0f5c},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.29074. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study online optimization with nested shrinking feasible regions in two settings: convex optimization with nested evolving feasible sets (CONES) and adversarial constrained online convex optimization (COCO). Our algorithms separate loss control from geometric movement: constrained minimizers and cumulative-loss tests preserve regret guarantees, while a deterministic resettable nested convex-body chaser limits movement. For CONES with a $G$-Lipschitz, $\mu$-strongly convex objective on a diameter-$D$ domain, we chase intersections of the current feasible set with adaptive objective sublevel sets. Using the Euclidean chasing ratio $O(\sqrt{d\log(1+d)})$, we obtain nonpositive regret at every prefix and movement $O(\sqrt{d\log(1+d)\,GD\log(eT)/\mu})$. The bound adapts to the increase in the constrained optimum value. In dimension two, with all other parameters fixed, every randomized algorithm with terminal expected regret $O(T^\beta)$, $\beta<1$, suffers $\Omega(\sqrt{\log T})$ expected movement on some deterministic nested sequence, proving optimal horizon dependence. Under linear growth away from the constrained minimizer set, Steiner-point tracking yields movement independent of $T$. For general convex COCO, one-step-delayed chasing with regularized-leader resets gives regret $O(G_fD\sqrt{d\log(1+d)T})$ and cumulative constraint violation $O(G_gD\sqrt{d\log(1+d)T})$. For strongly convex losses, both are $O(d\log(1+d)\log(eT))$ when other parameters are fixed. These reductions replace the $O(d^{d/2})$ projection-path factor in prior analyses by the polynomial dimension dependence of Euclidean nested convex-body chasing.
Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-01 in cs.AI).
Categorie arXiv: Artificial Intelligence (cs.AI).
Pagina del lavoro: https://arxiv.org/abs/2608.29074 — 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-17T07:28:26.509Z dalla pagina https://arxiv.org/catchup/cs.AI/2026-09-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).