Convex Optimization with Nested Evolving Feasible Sets (CONES) under Time-Varying Loss Functions
Summary
This paper extends CONES to time-varying loss functions, showing bounds for regret and movement cost using projected proximal algorithms in convex optimization.
View Cached Full Text
Cached at: 09/11/26, 08:32 AM
# Convex Optimization with Nested Evolving Feasible Sets (CONES) under Time-Varying Loss Functions
Source: [https://arxiv.org/abs/2609.11207](https://arxiv.org/abs/2609.11207)
[View PDF](https://arxiv.org/pdf/2609.11207)[HTML \(experimental\)](https://arxiv.org/html/2609.11207v1)
> 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\-\\beta\}\), O\(T^\\beta\)$ simultaneous regret and movement cost, respectively, for any $\\beta \\in \[0,1\)$, over a time horizon of $T$\. We also show that any \{\\it weakly adaptive\} online algorithm with $O\(T^\\beta\)$ regret has a movement cost of $\\Omega\\left\(T^\{\\frac\{1\-\\beta\}\{2\}\}\\right\)$ for any $\\beta \\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 $\\Omega\\left\(\\log T\\right\)$\.
## Submission history
From: Rahul Vaze \[[view email](https://arxiv.org/show-email/db8087f8/2609.11207)\] **\[v1\]**Thu, 10 Sep 2026 08:13:27 UTC \(22 KB\)Similar Articles
From Non-Convex to Strongly Convex: Curvature-Adaptive FTPL for Online Optimization
This paper introduces a curvature-adaptive Follow-the-Perturbed-Leader (FTPL) algorithm for online optimization that achieves optimal regret bounds for both non-convex Lipschitz losses and strongly convex losses, using a time-varying perturbation scale.
Online Learning on Hidden-Convex Losses via Algorithmic Equivalence: Optimal Regret, Geometric Barrier, and Bandit Feedback
This paper proves that online gradient descent achieves optimal √T regret for hidden-convex losses under a Hessian compatibility condition, resolving open questions in adversarial online learning. It also extends results to one-point bandit feedback with a T^{3/4} expected regret bound.
WeCon: An Efficient Weight-Conditioned Neural Solver for Multi-Objective Combinatorial Optimization Problems
Presents WeCon, a weight-conditioned neural solver for multi-objective combinatorial optimization problems that achieves comparable hypervolume to the state-of-the-art while reducing inference time by 40%.
Online Localized Conformal Prediction
This paper proposes Online Localized Conformal Prediction (OLCP) to address covariate heterogeneity in online learning and time-series settings. It introduces OLCP-Hedge for bandwidth selection and demonstrates valid long-run coverage with narrower prediction sets compared to existing baselines.
Curvature-Independent Regret Bounds for Distributed Online Optimization on Hadamard Manifolds
This paper presents distributed Riemannian online gradient descent on Hadamard manifolds with curvature-independent regret bounds for horospherical convex functions, achieving rates matching Euclidean optimization.