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

arXiv:2608.29074v1 Announce Type: new Abstract: 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, mu-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(sqrt{dlog(1+d)}), we obtain nonpositive regret at every prefix and movement O(sqrt{dlog(1+d),GDlog(eT)/mu}). 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^eta), eta<1, suffers Omega(sqrt{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(G_fDsqrt{dlog(1+d)T}) and cumulative constraint violation O(G_gDsqrt{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(d^{d/2}) projection-path factor in prior analyses by the polynomial dimension dependence of Euclidean nested convex-body chasing.

Source: arXiv cs.AI | 2026-09-01

Related