Convex Optimization with Nested Evolving Feasible Sets

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 \cdots \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 M_\cA(T) while ensuring feasibility at all times. CONES is an optimization-oriented generalization of the well-known nested convex body chasing (NCBC). When the loss function is convex, we propose a lazy-algorithm and show that it achieves O(T^{1-β}), O(T^β) simultaneous regret and movement cost for any β\in (0,1], over a time horizon of T. When the loss function is strongly convex, we propose a Frugal algorithm 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 Ω\left(\sqrt{\frac{\log{T}}{\log \log T}}\right).