Metraipolis › archive › dc_3c4fffec1ef8

Convex Optimization with Nested Evolving Feasible Sets (CONES) under Time-Varying Loss Functions — arXiv:2609.11207

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.11207
License (as archived)
CC0-1.0
Archived
2026-10-16T05:54:55.666Z
SHA-256 of the archived text
de16acbfcf75b8b4aff5b59fe3bb2e1e11510bbf79c1d6e657ed196c85d251bc
Stable URL of this page
https://metraipolis.com/documento/dc_3c4fffec1ef8

How to cite

Convex Optimization with Nested Evolving Feasible Sets (CONES) under Time-Varying Loss Functions — arXiv:2609.11207 — arXiv (en), https://arxiv.org/abs/2609.11207 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_3c4fffec1ef8 (Metraipolis archive dc_3c4fffec1ef8, sha256 de16acbfcf75b8b4aff5b59fe3bb2e1e11510bbf79c1d6e657ed196c85d251bc)
BibTeX
@misc{dc3c4fffec1ef8,
  title = {Convex Optimization with Nested Evolving Feasible Sets (CONES) under Time-Varying Loss Functions — arXiv:2609.11207},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.11207},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_3c4fffec1ef8; sha256 de16acbfcf75b8b4aff5b59fe3bb2e1e11510bbf79c1d6e657ed196c85d251bc},
  year = {2026}
}

Archived text

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

Convex Optimization with Nested Evolving Feasible Sets (CONES)} was introduced in \cite{CONESVaze} where the objective function \(f\) remains fixed but the feasible region evolves over time as a nested sequence \(S_1 \supseteq S_2 \supseteq \cdots \supseteq S_T\). The goal of an online algorithm is to simultaneously minimize the regret with respect to hindsight static optimal benchmark and the total movement cost $M_\cA(T)$ while ensuring feasibility at all times. CONES is an optimization-oriented generalization of the well-known \emph{nested convex body chasing} (NCBC). In this paper, we extend CONES to allow for loss functions $f_t'$s to also change over time. When all loss functions are convex, we show that the projected proximal algorithm achieves $O(T^{1-\beta}), O(T^\beta)$ simultaneous regret and movement cost, respectively, for any $\beta \in [0,1)$, over a time horizon of $T$. We also show that any {\it weakly adaptive} online algorithm with $O(T^\beta)$ regret has a movement cost of $\Omega\left(T^{\frac{1-\beta}{2}}\right)$ for any $\beta \in [0,1)$. When all loss functions are strongly convex, we show that the projected proximal algorithm simultaneously achieves $O(1)$ regret and a movement cost of $O(\log T)$. To complement this, we show that any online algorithm with sublinear {\it anytime} regret has a movement cost of $\Omega\left(\log T\right)$.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-11 in cs.LG).
Categorie arXiv: Machine Learning (cs.LG) ; Data Structures and Algorithms (cs.DS); Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2609.11207 — 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-16T05:44:24.987Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-11?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).