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 S1 ⊇ S2 ⊇ ⋯ ⊇ ST. The goal of an online algorithm is to simultaneously minimize the regret with respect to hindsight static optimal benchmark and the total movement cost McA(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 ft's to also change over time. When all loss functions are convex, we show that the projected proximal algorithm achieves O(T1−β), O(Tβ) simultaneous regret and movement cost, respectively, for any β∈ [0,1), over a time horizon of T. We also show that any {\it weakly adaptive} online algorithm with O(Tβ) regret has a movement cost of Ω(T(1−β)/2) for any β∈ [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 Ω(log T).
Related
- Accelerated Proximal Gradient Method for Non-Strongly Convex Time-Varying Optimization
- Synthesis of the Transient Behaviour of Optimization Algorithms for Strongly Convex Objective Functions
- Sequential Monte Carlo Sampling of Feasible Regions Represented by R-Functions
- A Feasible-Direction-Type Method for Nonconvex Optimization with Infeasible Starts
- A Feasible Direction Method with Active-Set Identification for Derivative-Free Optimization
BibTeX
@misc{vaze2026convex,
title = {{Convex Optimization with Nested Evolving Feasible Sets (CONES) under Time-Varying Loss Functions}},
author = {Rahul Vaze},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.11207},
eprint = {2609.11207},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.11207},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Convex Optimization with Nested Evolving Feasible Sets (CONES) under Time-Varying Loss Functions
AU - Rahul Vaze
PY - 2026
DA - 2026/09/10
PB - arXiv
DO - 10.48550/arxiv.2609.11207
UR - https://arxiv.org/abs/2609.11207
AB - 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 ⊇ S_2 ⊇ ⋯ ⊇ 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−β), O(T^β) simultaneous regret and movement cost, respectively, for any β∈ [0,1), over a time horizon of T. We also show that any {\it weakly adaptive} online algorithm with O(T^β) regret has a movement cost of Ω(T^(1−β)/2) for any β∈ [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 Ω(log T).
ER -