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

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.