Convex Optimization with Nested Evolving Feasible Sets

Abstract:\emph{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 \emph{nested convex body chasing} (NCBC). When the loss function is convex, we propose a lazy-algorithm and show that it achieves $O(T^{1-\beta}), O(T^\beta)$ simultaneous regret and movement cost for any $\beta \in (0,1]$, over a time horizon of $T$. When the loss function is strongly convex, we propose a \textsc{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 $\Omega\left(\sqrt{\frac{\log{T}}{\log \log T}}\right)$.

Machine Learning (cs.LG); Data Structures and Algorithms (cs.DS); Optimization and Control (math.OC)

arXiv:2605.07386 [cs.LG]

(or arXiv:2605.07386v2 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2605.07386 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.