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

Abstract

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)$.

Authors 1

Rahul Vaze

Specification

Official page

arxiv.org/abs/2609.11207

Source:arXiv (Atom API + RSS)·T1·observed 1 h ago·high

Arxiv announce type

new

Source:arXiv (Atom API + RSS)·T1·observed 1 h ago·high

arXiv id

2609.11207

Source:arXiv (Atom API + RSS)·T1·observed 1 h ago·high

Categories

cs.LG, cs.DS, math.OC

Source:arXiv (Atom API + RSS)·T1·observed 1 h ago·high

PDF

arxiv.org/pdf/2609.11207

Source:arXiv (Atom API + RSS)·T1·observed 1 h ago·high

Primary category

cs.LG

Source:arXiv (Atom API + RSS)·T1·observed 1 h ago·high

Published

11 Sept 2026

Source:arXiv (Atom API + RSS)·T1·observed 1 h ago·high

Each value shows its source, tier and observation time. Conflicting claims are kept side by side and flagged — never averaged. How AI Atlas records facts →

Provenance