Nested Convex-Body Chasing for Online Optimization with Evolving Feasible Sets
Dhruv Sarkar, Aprameyo Chakrabartty
原文摘要
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(\sqrt{d\log(1+d)})$, we obtain nonpositive regret at every prefix and movement $O(\sqrt{d\log(1+d)\,GD\log(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 $Ω(\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_fD\sqrt{d\log(1+d)T})$ and cumulative constraint violation $O(G_gD\sqrt{d\log(1+d)T})$. For strongly convex losses, both are $O(d\log(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.
cs.AI