Constrained Online Convex Optimization without Slater's Condition

• URL: http://arxiv.org/abs/2606.31480v1
• Date: Tue, 30 Jun 2026 10:54:41 GMT
• Title: Constrained Online Convex Optimization without Slater's Condition
• Abstract summary: For constraints, existing algorithms that achieve nearly optimal regret and constraint violation bounds typically rely on regularity assumptions such as Slater's condition.<n>We bridge this gap with an anytime primal-dual framework that incorporates an adaptive regularizer into the dual update.<n>Our algorithm achieves $O(sqrtT)$ expected regret and $O(sqrtTlog T)$ expected cumulative constraint violation.
• Score: 0.7646713951724009
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study constrained online convex optimization with adversarial losses and stochastic or adversarial constraints. For stochastic constraints, existing algorithms that achieve nearly optimal regret and constraint violation bounds typically rely on regularity assumptions such as Slater's condition, while adversarial-constraint algorithms avoid these assumptions by using a rather restrictive round-wise feasible comparator. We bridge this gap with an anytime primal-dual framework that incorporates an adaptive regularizer into the dual update. The regularizer stabilizes the dual process without relying on the negative drift induced by Slater's condition. For stochastic constraints and convex losses, our algorithm achieves $O(\sqrt{T})$ expected regret and $O(\sqrt{T}\log T)$ expected cumulative constraint violation. Furthermore, we show that our algorithm also admits high-probability bounds of the same order on regret and constraint violation. For strongly convex losses, the regret bound improves to $O(\log T)$ with a violation bound of the same order. With a minor modification, the framework also applies to adversarial constraints and provides guarantees for hard constraint violation.

Related papers

• Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
  Under common feasibility, our LEDGER algorithm attains $O(sqrt T)$ expected regret and $O(sqrtTlog(eT))$ expected budget violation.<n>Neither a Slater condition, independence between feedback channels, nor an absolute constraint-value bound is needed.
  arXiv  Detail & Related papers  (2026-09-07T01:38:41Z)
• Beyond Slater's Condition in Online CMDPs with Stochastic and Adversarial Constraints [33.41566575424402]
  We study emphonline episodic Constrained Markov Decision Processes (CMDPs) under both and adversarial constraints.<n>We provide a novel algorithm whose guarantees greatly improve those of the state-of-the-art best-of-both-worlds algorithm introduced by Stradi et al.<n>In the adversarial regime, emphi.e., our algorithm ensures sublinear constraint violation without Slater's condition, and sublinear $alpha$-regret with respect to the emphunconstrained optimum.
  arXiv  Detail & Related papers  (2025-09-24T13:38:32Z)
• An Optimistic Algorithm for Online Convex Optimization with Adversarial Constraints [55.2480439325792]
  We study Online Convex Optimization (OCO) with adversarial constraints.<n>We focus on a setting where the algorithm has access to predictions of the loss and constraint functions.<n>Our results show that we can improve the current best bounds of $ O(sqrtT) $ regret and $ tildeO(sqrtT) $ cumulative constraint violations.
  arXiv  Detail & Related papers  (2024-12-11T03:06:42Z)
• Fixed-Budget Differentially Private Best Arm Identification [62.36929749450298]
  We study best arm identification (BAI) in linear bandits in the fixed-budget regime under differential privacy constraints. We derive a minimax lower bound on the error probability, and demonstrate that the lower and the upper bounds decay exponentially in $T$.
  arXiv  Detail & Related papers  (2024-01-17T09:23:25Z)
• Multi-point Feedback of Bandit Convex Optimization with Hard Constraints [1.8130068086063336]
  We study bandit convex optimization with constraints, where the learner aims to generate a sequence of decisions under partial information of loss functions. We adopt the cumulative textithard constraint violation as the metric of constraint violation. Our algorithm attains $O(d2Tmaxc,1-c)$ regret bounds and $O(d2T1-fracc2)$ cumulative hard constraint violation bounds for convex loss functions and time-varying constraints.
  arXiv  Detail & Related papers  (2023-10-17T02:43:22Z)
• On Regularization and Inference with Label Constraints [62.60903248392479]
  We compare two strategies for encoding label constraints in a machine learning pipeline, regularization with constraints and constrained inference. For regularization, we show that it narrows the generalization gap by precluding models that are inconsistent with the constraints. For constrained inference, we show that it reduces the population risk by correcting a model's violation, and hence turns the violation into an advantage.
  arXiv  Detail & Related papers  (2023-07-08T03:39:22Z)
• Projection-Free Online Convex Optimization with Stochastic Constraints [0.0]
  We develop projection-free algorithms for online convex optimization with constraints. We deduce sublinear regret and constraint violation bounds for various settings. We prove that the constraint violation can be reduced to have the same growth as the regret.
  arXiv  Detail & Related papers  (2023-05-02T11:27:34Z)
• Online Convex Optimization with Stochastic Constraints: Zero Constraint Violation and Bandit Feedback [0.0]
  We propose a variant of the drift-plus-penalty algorithm that guarantees $O(sqrtT)$ expected regret and zero constraint violation. Our algorithm is oblivious to the length of the time horizon $T$, in contrast to the vanilla drift-plus-penalty method.
  arXiv  Detail & Related papers  (2023-01-26T18:04:26Z)
• A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
  We study online learning problems in which a decision maker has to take a sequence of decisions subject to $m$ long-term constraints. The goal is to maximize their total reward, while at the same time achieving small cumulative violation across the $T$ rounds. We present the first best-of-both-world type algorithm for this general class problems, with no-regret guarantees both in the case in which rewards and constraints are selected according to an unknown model, and in the case in which they are selected at each round by an adversary.
  arXiv  Detail & Related papers  (2022-09-15T16:59:19Z)
• Regret and Cumulative Constraint Violation Analysis for Online Convex Optimization with Long Term Constraints [24.97580261894342]
  This paper considers online convex optimization with long term constraints, where constraints can be violated in intermediate rounds, but need to be satisfied in the long run. A novel algorithm is first proposed and it achieves an $mathcalO(Tmaxc,1-c)$ bound for static regret and an $mathcalO(T(1-c)/2)$ bound for cumulative constraint violation.
  arXiv  Detail & Related papers  (2021-06-09T15:18:06Z)
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization [55.937424268654645]
  We consider algorithm-independent lower bounds for the problem of black-box optimization of functions having a bounded norm. We provide a novel proof technique for deriving lower bounds on the regret, with benefits including simplicity, versatility, and an improved dependence on the error probability.
  arXiv  Detail & Related papers  (2020-08-20T03:48:14Z)

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.