Convex optimization handles changing goals and shrinking options efficiently
Convex Optimization with Nested Evolving Feasible Sets (CONES) under Time-Varying Loss Functions
Machine LearningData Structures and Algorithms
Summary
This paper studies how to solve optimization problems when both the rules and goals change over time. The authors extend previous work that only handled shrinking constraints to also cope with changing objectives. They show that certain algorithms can balance making good choices and not changing those choices too much over time. Their results show trade-offs between how well the algorithm performs and how much it moves, depending on the problem’s difficulty.
What this means in practice
- •For robotic control teams: Manage robot movement paths when obstacles you face keep shrinking and your goals shift over time.
- •For network schedulers: Optimize dynamic resource allocations in networks where constraints tighten and objectives change frequently.
A theory result. No direct application yet.
Authors
Rahul Vaze
Abstract
Convex Optimization with Nested Evolving Feasible Sets (CONES)} was introduced in \cite{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 \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 \emph{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-β}), O(T^β)$ simultaneous regret and movement cost, respectively, for any $β\in [0,1)$, over a time horizon of $T$. We also show that any {\it weakly adaptive} online algorithm with $O(T^β)$ regret has a movement cost of $Ω\left(T^{\frac{1-β}{2}}\right)$ for any $β\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 $Ω\left(\log T\right)$.