# Nested Convex-Body Chasing for Online Optimization with Evolving Feasible Sets

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 12 references that are in the map.
- First posted on arXiv 29 Aug 2026.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Optimal Algorithms for Online Convex Optimization with Adversarial Constraints](https://mlsanity.com/paper/2310.18955/) (2023)
- [Chasing Nested Convex Bodies Nearly Optimally](https://mlsanity.com/paper/1811.00999/) (2018)
- [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)
- [A Geometric Approach to Constrained Online Learning](https://mlsanity.com/paper/2605.21107/) (2026)
- [Convex Optimization with Nested Evolving Feasible Sets](https://mlsanity.com/paper/2605.07386/) (2026)

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

- [Convex Optimization with Nested Evolving Feasible Sets (CONES) under Time-Varying Loss Functions](https://mlsanity.com/paper/2609.11207/) (2026)

## Abstract (arXiv)

We study online optimization with nested shrinking feasible regions in two settings: convex optimization with nested evolving feasible sets (CONES) and adversarial constrained online convex optimization (COCO). Our algorithms separate loss control from geometric movement: constrained minimizers and cumulative-loss tests preserve regret guarantees, while a deterministic resettable nested convex-body chaser limits movement. For CONES with a G-Lipschitz, μ-strongly convex objective on a diameter-D domain, we chase intersections of the current feasible set with adaptive objective sublevel sets. Using the Euclidean chasing ratio O(√dlog(1+d)), we obtain nonpositive regret at every prefix and movement O(√dlog(1+d),GDlog(eT)/μ). The bound adapts to the increase in the constrained optimum value. In dimension two, with all other parameters fixed, every randomized algorithm with terminal expected regret O(Tβ), β<1, suffers Omega(√log T) expected movement on some deterministic nested sequence, proving optimal horizon dependence. Under linear growth away from the constrained minimizer set, Steiner-point tracking yields movement independent of T. For general convex COCO, one-step-delayed chasing with regularized-leader resets gives regret O(GfD√dlog(1+d)T) and cumulative constraint violation O(GgD√dlog(1+d)T). For strongly convex losses, both are O(dlog(1+d)log(eT)) when other parameters are fixed. These reductions replace the O(dd/2) projection-path factor in prior analyses by the polynomial dimension dependence of Euclidean nested convex-body chasing.