Convex Optimization with Nested Evolving Feasible Sets (CONES) under Time-Varying Loss Functions

arXiv:2609.11207v1 Announce Type: new Abstract: Convex Optimization with Nested Evolving Feasible Sets (CONES)} was introduced in ite{CONESVaze} 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 M_A(T) while ensuring feasibility at all times. CONES is an optimization-oriented generalization of the well-known nested convex body chasing (NCBC). In this paper, we extend CONES to allow for loss functions f_t's to also change over time. When all loss functions are convex, we show that the projected proximal algorithm achieves O(T^{1-eta}), O(T^eta) simultaneous regret and movement cost, respectively, for any eta in [0,1), over a time horizon of T. We also show that any {it weakly adaptive} online algorithm with O(T^eta) regret has a movement cost of Omegaleft(T^{frac{1-eta}{2}}right) for any eta in [0,1). When all loss functions are strongly convex, we show that the projected proximal algorithm simultaneously achieves O(1) regret and a movement cost of O(log T). To complement this, we show that any online algorithm with sublinear {it anytime} regret has a movement cost of Omegaleft(log Tright).

Related

• Convex Optimization with Nested Evolving Feasible Sets
• Parameter-free Dynamic Regret: Time-varying Movement Costs, Delayed Feedback, and Memory
• Parameter-Free Dynamic Regret for Online Convex Optimization under Heavy-Tailed Noise

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