# Convex Optimization with Nested Evolving Feasible Sets

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 46 references that are in the map.
- First posted on arXiv 8 May 2026.

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

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Overcoming catastrophic forgetting in neural networks](https://mlsanity.com/paper/1612.00796/) (2016)
- [Constitutional AI: Harmlessness from AI Feedback](https://mlsanity.com/paper/2212.08073/) (2022)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Fine-Tuning Language Models from Human Preferences](https://mlsanity.com/paper/1909.08593/) (2019)
- [Safe RLHF: Safe Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2310.12773/) (2023)
- [Online Convex Optimization with Stochastic Constraints](https://mlsanity.com/paper/1708.03741/) (2017)
- [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)
- [Smoothed Online Convex Optimization in High Dimensions via Online Balanced Descent](https://mlsanity.com/paper/1803.10366/) (2018)
- [Beyond Online Balanced Descent: An Optimal Algorithm for Smoothed Online Optimization](https://mlsanity.com/paper/1905.12776/) (2019)
- [Time-Varying Convex Optimization: Time-Structured Algorithms and Applications](https://mlsanity.com/paper/2006.08500/) (2020)
- [Revisiting Smoothed Online Learning](https://mlsanity.com/paper/2102.06933/) (2021)
- [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)
- [Dimension-Free Bounds on Chasing Convex Functions](https://mlsanity.com/paper/2005.14058/) (2020)
- [Beyond tildeO(√T) Constraint Violation for Online Convex Optimization with Adversarial Constraints](https://mlsanity.com/paper/2505.06709/) (2025)
- [O(√T) Static Regret and Instance Dependent Constraint Violation for Constrained Online Convex Optimization](https://mlsanity.com/paper/2502.05019/) (2025)

## Built on by (most cited first, 4 of 4)

- [A Geometric Approach to Constrained Online Learning](https://mlsanity.com/paper/2605.21107/) (2026)
- [Nested Convex-Body Chasing for Online Optimization with Evolving Feasible Sets](https://mlsanity.com/paper/2608.29074/) (2026)
- [Convex Optimization with Nested Evolving Feasible Sets (CONES) under Time-Varying Loss Functions](https://mlsanity.com/paper/2609.11207/) (2026)
- [tildeO(√T) Regret and Polylogarithmic Constraint Violation for COCO](https://mlsanity.com/paper/2610.03983/) (2026)

## Abstract (arXiv)

Convex Optimization with Nested Evolving Feasible Sets (CONES) is considered 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). When the loss function is convex, we propose a lazy-algorithm and show that it achieves O(T1-β), O(Tβ) simultaneous regret and movement cost for any β ∈ (0,1], over a time horizon of T. When the loss function is strongly convex, we propose a textscFrugal algorithm that simultaneously achieves zero regret and a movement cost of O(log T). To complement this, we show that any online algorithm with o(T) regret has a movement cost of Omegaleft(√fraclogTlog log Tright).