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

• URL: http://arxiv.org/abs/2609.11207v1
• Date: Thu, 10 Sep 2026 08:13:27 GMT
• Title: Convex Optimization with Nested Evolving Feasible Sets (CONES) under Time-Varying Loss Functions
• Abstract summary: We extend CONES to allow for loss functions $f_t'$s to also change over time.<n>We show that any online algorithm with sublinear it anytime regret has a movement cost of $left(log Tright)$.
• Score: 5.533296779866529
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• 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)$.

Related papers

• Nested Convex-Body Chasing for Online Optimization with Evolving Feasible Sets [0.0]
  We study online optimization with nested shrinking feasible regions in two settings.<n>Concerned minimizers and cumulative-loss tests preserve regret guarantees.<n>A deterministic resettable nested convex-body chaser limits movement.
  arXiv  Detail & Related papers  (2026-08-29T06:01:56Z)
• Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence [54.59847568544922]
  We study horizon-free regret for finite-horizon time-homogeneous Markov decision processes with $A$ states, $A$ actions, horizon $H$, and per-trajectory total reward bounded by $1$.<n>We prove a regret upper bound [tilde O(sqrtSAK+S8A3)] with failure probability $$, where $K$ is the number of episodes and $tilde O(sqrtSAK+S3K)$ hides $mathsfpoly
  arXiv  Detail & Related papers  (2026-07-22T07:42:19Z)
• Lower Bound on the Cumulative Constrained Violation for the OGD+Projection algorithm for Constrained Online Convex Optimization (COCO) [4.167459103689586]
  The objective is to simultaneously minimize the static regret and cumulative constraint violation.<n>This paper shows that the CCV of the OGD+Projection algorithm is $(Tfracd-12d)$.
  arXiv  Detail & Related papers  (2026-07-12T15:36:04Z)
• Convex Optimization with Nested Evolving Feasible Sets [4.67724003380452]
  We show that an online algorithm with $o(T)$ regret has a movement cost of $(logT)$ for both cases, proving optimality of Frugal.<n>We also show that any online algorithm with $o(T)$ regret has a movement cost of $(logT)$ for both cases, proving optimality of Frugal.
  arXiv  Detail & Related papers  (2026-05-08T07:42:15Z)
• Adaptivity and Universality: Problem-dependent Universal Regret for Online Convex Optimization [64.88607416000376]
  We introduce UniGrad, a novel approach that achieves both universality and adaptivity, with two distinct realizations: UniGrad.Correct and UniGrad.Bregman.<n>Both methods achieve universal regret guarantees that adapt to gradient variation, simultaneously attaining $mathcalO(log V_T)$ regret for strongly convex functions and $mathcalO(d log V_T)$ regret for exp-concave functions.
  arXiv  Detail & Related papers  (2025-11-25T05:23:10Z)
• Fast Rates in Stochastic Online Convex Optimization by Exploiting the Curvature of Feasible Sets [35.8717656676532]
  In online linear optimization, it is known that if the average gradient of loss functions exceeds a certain threshold, the curvature of feasible sets can be exploited.<n>This study reveals that algorithms adaptive to the curvature of loss functions can also leverage the curvature of feasible sets.
  arXiv  Detail & Related papers  (2024-02-20T09:59:33Z)
• Optimal and Efficient Algorithms for Decentralized Online Convex Optimization [51.00357162913229]
  Decentralized online convex optimization (D-OCO) is designed to minimize a sequence of global loss functions using only local computations and communications.<n>We develop a novel D-OCO algorithm that can reduce the regret bounds for convex and strongly convex functions to $tildeO(nrho-1/4sqrtT)$ and $tildeO(nrho-1/2log T)$.<n>Our analysis reveals that the projection-free variant can achieve $O(nT3/4)$ and $O(n
  arXiv  Detail & Related papers  (2024-02-14T13:44:16Z)
• Improved Dynamic Regret for Online Frank-Wolfe [54.690867216880356]
  We investigate the dynamic regret of online Frank-Wolfe (OFW), which is an efficient projection-free algorithm for online convex optimization. In this paper, we derive improved dynamic regret bounds for OFW by extending the fast convergence rates of FW from offline optimization to online optimization.
  arXiv  Detail & Related papers  (2023-02-11T07:19:51Z)
• Online Convex Optimization with Continuous Switching Constraint [78.25064451417082]
  We introduce the problem of online convex optimization with continuous switching constraint. We show that, for strongly convex functions, the regret bound can be improved to $O(log T)$ for $S=Omega(log T)$, and $O(minT/exp(S)+S,T)$ for $S=O(log T)$.
  arXiv  Detail & Related papers  (2021-03-21T11:43:35Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  We study online learning with bandit feedback (i.e. learner has access to only zeroth-order oracle) where cost/reward functions admit a "pseudo-1d" structure. We show a lower bound of $min(sqrtdT, T3/4)$ for the regret of any algorithm, where $T$ is the number of rounds. We propose a new algorithm sbcalg that combines randomized online gradient descent with a kernelized exponential weights method to exploit the pseudo-1d structure effectively.
  arXiv  Detail & Related papers  (2021-02-15T08:16:51Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.