Source-linked AI summary
Convex Optimization with Nested Evolving Feasible Sets (CONES) under Time-Varying Loss Functions
Rahul Vaze
TL;DR
CONES seeks simultaneous control of regret and movement while feasible sets evolve, and this paper extends it to time-varying loss functions. Using a projected proximal algorithm, it establishes stronger movement lower bounds and characterizes the convex and strongly convex cases.
Problem
CONES studies online decisions that remain feasible under nested evolving sets while simultaneously minimizing regret and movement cost.
Method
The paper extends CONES to evolving loss functions and analyzes a projected proximal algorithm for this setting.
Results
The convex case retains the known upper-bound rate while gaining lower bounds, whereas strongly convex losses yield a tight Θ(log T) movement rate under sublinear anytime regret.
Takeaways & Limitations
The results widen CONES to time-varying objectives and improve the theoretical understanding of movement requirements.
Takeaways & Limitations
The bounds include constants depending on the chosen norm and the dimension d, so their constants are not universal.
Abstract
from arXiv · showhide
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)$.
1 Introduction
CONES studies online optimization with nested feasible sets, requiring simultaneous control of regret and movement while maintaining feasibility. This paper extends the framework to time-varying losses and develops upper and lower bounds for convex and strongly convex settings.
- Problem setting: The online algorithm must choose feasible actions from nested convex sets while simultaneously minimizing regret against a static hindsight optimum and total movement cost.The benchmark chooses a feasible action minimizing cumulative loss, and nestedness preserves its feasibility across rounds.
- Prior work: CONES generalizes nested convex body chasing and was previously studied for a fixed loss function, with algorithms including greedy, FRUGAL, and LSP.Prior work established different regret–movement trade-offs for strongly convex and convex objectives.
- Contributions: The paper extends CONES to arbitrary time-varying loss functions while retaining evolving nested feasible sets and a static hindsight benchmark.The contribution separates changes in optimization geometry from temporal variation in the objective.
- Contributions: For strongly convex losses, Prox achieves O(1) regret and O(log T) movement, while every sublinear-anytime-regret algorithm requires Ω(log T) movement.Prox uses η_t = 1/μ_t and automatically adapts to changing constraints rather than moving only when regret forces it.
- Contributions: For convex losses, Prox achieves the regret–movement pair (T^(1−β), T^β) for any β ∈ [0, 1], while weakly adaptive regret O(T^β) implies movement Ω(T^((1−β)/2)).The latter lower bound applies even in the fixed-objective special case, where prior work had not provided such a result.
2 ft’s are strongly convex
For strongly convex, Lipschitz losses, the projected proximal algorithm achieves constant regret and logarithmic movement, while any anytime-sublinear-regret algorithm requires logarithmic movement.
- 2.1 Upper Bound: O(1) regret and O(log T) movement are achieved by Prox with η_t = 1/(µt) for strongly convex losses.The update uses the entire current loss and adapts to changing feasible sets.
- 2.1 Upper Bound: The proximal update’s fixed-point form places η_t in the numerator, enabling T-independent regret together with O(log T) movement.This form supports a nested-projection movement bound.
- 2.2 Lower Bound: Any online algorithm with anytime sublinear regret can be forced to incur logarithmic movement on a sequence of 1-strongly convex, 1-Lipschitz losses.The lower bound is stated against an adaptive adversary.
- 2.2 Lower Bound: Together, the upper and lower bounds characterize the optimal movement rate for anytime o(T) regret as Θ(log T) with changing losses.This is worse than the fixed-objective setting’s previously known O(√log T) upper bound.
3 ft’s are convex
For convex losses, the paper analyzes simultaneous regret and movement trade-offs, establishes projected-proximal upper bounds, and derives lower bounds for weakly adaptive algorithms.
- 3.2.1 Weakly Adaptive Algorithms: Weak adaptivity requires regret guarantees on every interval, with terminal static regret recovered by choosing the full horizon interval.Nested feasibility ensures a fixed comparator remains feasible throughout each interval.
- 3.3 Examples of weakly adaptive algorithms for CONES: The changing-loss Prox algorithm is R-weakly adaptive under convex losses and constant stepsize η_t = η.Its guarantee follows by summing the proximal optimality inequality over an arbitrary interval.
- 3.3 Examples of weakly adaptive algorithms for CONES: The changing-loss LSP extension is Tε-weakly adaptive, while GREEDY is 0-weakly adaptive.These provide examples of weakly adaptive algorithms beyond Prox.
4 Conclusion
The paper extends CONES from fixed objectives to evolving losses and characterizes regret–movement trade-offs for convex and strongly convex settings.
- 4 Conclusion: CONES is generalized so both loss functions and nested feasible sets may evolve while the benchmark remains a static hindsight optimum.The extension separates evolving optimization geometry from temporal variation in the objective.
- 4 Conclusion: For strongly convex losses, the paper establishes tight Θ(log T) movement under sublinear anytime regret, versus the earlier O(√log T) fixed-objective upper bound.The projected proximal algorithm attains the matching logarithmic upper bound.
- 4 Conclusion: For convex losses, the paper retains the known fixed-objective upper-bound order in the evolving-objective setting and adds lower bounds that also apply to fixed objectives.These results broaden CONES and strengthen its theoretical characterization.
5 Proof of Theorem 1
The proof of Theorem 1 rewrites the proximal update as a projected-gradient trajectory and combines strong-convexity regret control with a nested-projection movement bound.
- 5 Proof of Theorem 1: The proximal update is equivalent to a projected-gradient form involving a subgradient of the current loss.This representation is the bridge to the movement analysis.
- 5 Proof of Theorem 1: The nested-projection lemma applies because the feasible sets satisfy S_t ⊆ S_{t−1}, yielding the logarithmic movement estimate.The dimension- and norm-dependent constant is denoted C_d.
- 5 Proof of Theorem 1: The first-order optimality condition and projection characterization provide the inequalities used to compare each iterate with the static optimum.Feasibility of x_OPT in every S_t is used in the comparison.
6 Proof of Theorem 2
The proof constructs phased instances with strongly convex, Lipschitz losses and shows that sublinear anytime regret forces constant movement in all but finitely many phases. Because the number of phases grows logarithmically with the horizon, movement is logarithmic.
- The constructed losses are 1-Lipschitz and 1-strongly convex, while all feasible sets in the instance are identical and therefore nested.
- Every sufficiently large phase of length 32N incurs at least 1/4 movement for any algorithm with o(t) anytime regret.The contradiction argument uses the phase construction and the assumed anytime-regret guarantee.
- Only finitely many phases can avoid the constant movement lower bound, with the number of exceptions independent of T.
- The number of complete phases is K = floor(log_33 T), yielding an Ω(log T) movement lower bound.Each nonexceptional phase contributes at least 1/4 movement, and the phase count grows logarithmically.
7 Proof of Theorem 3
The proof applies convexity and the projected proximal update's optimality condition to bound the algorithm's regret against a feasible static benchmark. Nested feasibility enables the required comparison and summation across time.
- Convexity gives a first-order loss comparison against x_OPT, which is feasible at every time because the feasible sets are nested.
- The first-order optimality condition for the Prox update supplies the per-round inequality used to sum the regret bound.
- The proximal update's structural form and nested-set lemma complete the telescoping argument for the regret guarantee.
8 Proof of Theorem 4
The proof constructs nested convex feasible sets and alternating linear objectives whose minimizers change across phases. Weak adaptivity forces the algorithm to enter separated trigger sets, so consecutive phases impose movement and produce the lower bound.
- The construction uses Sk = conv{c, zk, ..., zK}, with alternating zk first coordinates and decreasing qk values.The points are defined by qk = 1 − (k − 1)δ and sk = (−1)^k.
- For each phase, the linear loss f(x, y) = −y has unique minimizer zk over Sk.
- Each phase has length at most L because weakly adaptive regret contradicts any L consecutive rounds outside its trigger set.Actions outside the trigger set incur a definite loss relative to the phase minimizer.
- All K phases fit within the horizon, with remaining rounds continuing under the final feasible set; the phase transitions therefore yield the stated movement growth.
- Every phase ends in its trigger set, and consecutive trigger sets are at least distance 1 apart, forcing at least one unit of movement per phase transition.