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

arXiv: https://arxiv.org/abs/2609.11207 · HTML: https://mlsanity.com/paper/2609.11207/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 21 references that are in the map.
- First posted on arXiv 10 Sep 2026.

## Builds on (most cited first, 13 of 13)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Online Convex Optimization with Time-Varying Constraints](https://mlsanity.com/paper/1702.04783/) (2017)
- [Optimal Algorithms for Online Convex Optimization with Adversarial Constraints](https://mlsanity.com/paper/2310.18955/) (2023)
- [Time-Varying Convex Optimization: Time-Structured Algorithms and Applications](https://mlsanity.com/paper/2006.08500/) (2020)
- [Chasing Nested Convex Bodies Nearly Optimally](https://mlsanity.com/paper/1811.00999/) (2018)
- [Chasing Convex Bodies with Linear Competitive Ratio](https://mlsanity.com/paper/1905.11877/) (2019)
- [Distributed Online Convex Optimization with Adversarial Constraints: Reduced Cumulative Constraint Violation Bounds under Slater's Condition](https://mlsanity.com/paper/2306.00149/) (2023)
- [A Nearly-Linear Bound for Chasing Nested Convex Bodies](https://mlsanity.com/paper/1806.08865/) (2018)
- [Nested Convex Bodies are Chaseable](https://mlsanity.com/paper/1707.05527/) (2017)
- [No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization](https://mlsanity.com/paper/2405.06575/) (2024)
- [Convex Optimization with Nested Evolving Feasible Sets](https://mlsanity.com/paper/2605.07386/) (2026)
- [Beyond tildeO(√T) Constraint Violation for Online Convex Optimization with Adversarial Constraints](https://mlsanity.com/paper/2505.06709/) (2025)
- [Nested Convex-Body Chasing for Online Optimization with Evolving Feasible Sets](https://mlsanity.com/paper/2608.29074/) (2026)

## Abstract (arXiv)

Convex Optimization with Nested Evolving Feasible Sets (CONES) was introduced in citeCONESVaze where the objective function (f) remains fixed but the feasible region evolves over time as a nested sequence (S1 supseteq S2 supseteq cdots supseteq 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 M_cA(T) while ensuring feasibility at all times. CONES is an optimization-oriented generalization of the well-known 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 Omegaleft(T^frac1-β2right) 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 Omegaleft(log Tright).