Convex Optimization with Nested Evolving Feasible Sets

arXiv:2605.07386v1 Announce Type: new Abstract: 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 S_1 supseteq S_2 supseteq dots supseteq S_T. The goal of an online algorithm is to simultaneously minimize the regret with respect to hindsight static optimal benchmark and the total movement cost while ensuring feasibility at all times. CONES is an optimization-oriented generalization of the well-known nested convex body chasing problem. When the loss function is convex, we propose a lazy-algorithm and show that it achieves O(T^{1-eta}), O(T^eta) simultaneous regret and movement cost for any eta in (0,1], over a time horizon of T. When the loss function is strongly convex or alpha-sharp, we propose an algorithm Frugal 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 Omega(log{T}) for both cases, proving optimality of Frugal.

Source: arXiv cs.LG | 2026-05-11