Nested Convex-Body Chasing for Online Optimization with Evolving Feasible Sets

• URL: http://arxiv.org/abs/2608.29074v1
• Date: Sat, 29 Aug 2026 06:01:56 GMT
• Title: Nested Convex-Body Chasing for Online Optimization with Evolving Feasible Sets
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study online optimization with nested shrinking feasible regions in two settings: convex optimization with nested evolving feasible sets (CONES) and adversarial constrained online convex optimization (COCO). Our algorithms separate loss control from geometric movement: constrained minimizers and cumulative-loss tests preserve regret guarantees, while a deterministic resettable nested convex-body chaser limits movement. For CONES with a $G$-Lipschitz, $μ$-strongly convex objective on a diameter-$D$ domain, we chase intersections of the current feasible set with adaptive objective sublevel sets. Using the Euclidean chasing ratio $O(\sqrt{d\log(1+d)})$, we obtain nonpositive regret at every prefix and movement $O(\sqrt{d\log(1+d)\,GD\log(eT)/μ})$. The bound adapts to the increase in the constrained optimum value. In dimension two, with all other parameters fixed, every randomized algorithm with terminal expected regret $O(T^β)$, $β<1$, suffers $Ω(\sqrt{\log T})$ expected movement on some deterministic nested sequence, proving optimal horizon dependence. Under linear growth away from the constrained minimizer set, Steiner-point tracking yields movement independent of $T$. For general convex COCO, one-step-delayed chasing with regularized-leader resets gives regret $O(G_fD\sqrt{d\log(1+d)T})$ and cumulative constraint violation $O(G_gD\sqrt{d\log(1+d)T})$. For strongly convex losses, both are $O(d\log(1+d)\log(eT))$ when other parameters are fixed. These reductions replace the $O(d^{d/2})$ projection-path factor in prior analyses by the polynomial dimension dependence of Euclidean nested convex-body chasing.

Related papers

• Convex Optimization with Nested Evolving Feasible Sets (CONES) under Time-Varying Loss Functions [5.533296779866529]
  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)$.
  arXiv  Detail & Related papers  (2026-09-10T08:13:27Z)
• Online Convex Optimization with Sublinear Noisy Probes [6.998574163422056]
  We study Online Convex Optimization (OCO) over a convex set $Ksubseteq mathbb Rd$.<n>We introduce a unified probing model that generalizes two recent lines of work: sublinear best-expert queries in the experts setting, and pairwise feedback available every round in OCO.<n>Our main result shows that even a sublinear and noisy probe budget can provably improve worst-case regret in the full feedback OCO regime.
  arXiv  Detail & Related papers  (2026-06-12T17:05:08Z)
• 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)
• A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees [58.59385794080679]
  We introduce a continuous-time model under which regret decomposes into a delay-independent learning term and a delay-induced drift term.<n>For bandit convex optimization, we significantly improve existing regret bounds, with delay-dependent terms matching state-of-the-art first-order rates.
  arXiv  Detail & Related papers  (2026-02-02T18:17:34Z)
• 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)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  We study the Shortest Path (SSP) problem with a linear mixture transition kernel. An agent repeatedly interacts with a environment and seeks to reach certain goal state while minimizing the cumulative cost. Existing works often assume a strictly positive lower bound of the iteration cost function or an upper bound of the expected length for the optimal policy.
  arXiv  Detail & Related papers  (2024-02-14T07:52:00Z)
• 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)
• ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
  We introduce a new tool for BFG convex optimization (SCO): a Reweighted Query (ReSQue) estimator for the gradient of a function convolved with a (Gaussian) probability density. We develop algorithms achieving state-of-the-art complexities for SCO in parallel and private settings.
  arXiv  Detail & Related papers  (2023-01-01T18:51:29Z)
• Towards Painless Policy Optimization for Constrained MDPs [46.12526917024248]
  We study policy optimization in an infinite horizon, $gamma$-discounted constrained Markov decision process (CMDP) Our objective is to return a policy that achieves large expected reward with a small constraint violation. We propose a generic primal-dual framework that allows us to bound the reward sub-optimality and constraint violation for arbitrary algorithms.
  arXiv  Detail & Related papers  (2022-04-11T15:08:09Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  Up to logarithmic factors the optimal excess population loss of any $(varepsilon,delta)$-differently private is $sqrtlog(d)/n + sqrtd/varepsilon n.$ We show that when the loss functions satisfy additional smoothness assumptions, the excess loss is upper bounded (up to logarithmic factors) by $sqrtlog(d)/n + (log(d)/varepsilon n)2/3.
  arXiv  Detail & Related papers  (2021-03-02T06:53:44Z)
• 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.