Structure-Dependent Regret and Constraint Violation Bounds for Online Convex Optimization with Time-Varying Constraints

Xiufeng Liu; Qian Chen; Zhijin Wang; Ruyu Liu

cs.LGMar 15, 2026

Structure-Dependent Regret and Constraint Violation Bounds for Online Convex Optimization with Time-Varying Constraints

Authors: Xiufeng Liu, Qian Chen, Zhijin Wang, Ruyu Liu

Organizations: Department of Technology, Management and Economics, Technical University of Denmark, 2800 Kongens Lyngby, Denmark · Department of Management and Engineering, Department of Management and Engineering, Linköping University, SE-581 83 Linköping, Sweden · College of Computer Engineering, Jimei University, Xiamen 361021, China

Abstract

Online convex optimization (OCO) with time-varying constraints is a critical framework for sequential decision-making in dynamic networked systems, where learners must minimize cumulative loss while satisfying regions of feasibility that shift across rounds. Existing theoretical analyses typically treat constraint variation as a monolithic adversarial process, resulting in joint regret and violation bounds that are overly conservative for real-world network dynamics. In this paper, we introduce a structured characterization of constraint variation - smooth drift, periodic cycles, and sparse switching - mapping these classes to common network phenomena such as slow channel fading, diurnal traffic patterns, and discrete maintenance windows. We derive structure-dependent joint bounds that strictly improve upon adversarial rates when the constraint process exhibits regularity. To realize these gains, we propose the Structure-Adaptive Primal-Dual (SA-PD) algorithm, which utilizes observable constraint signals to detect environmental structure online and adapt dual update strategies accordingly. Extensive experiments on synthetic benchmarks and real-world datasets - including online electricity scheduling and transformer load management - demonstrate that SA-PD reduces cumulative constraint violation by up to 53% relative to structure-agnostic baselines while maintaining competitive utility. This work serves as a comprehensive guide for exploiting temporal regularity in constrained online learning for robust network engineering.

Figures & tables

Algorithm	Feedback	Constraint Type	Structure Awareness	Violation Bound	Regret Bound
Mahdavi et al. [ 3 ]	Full-Info	Fixed	No	$O(T^{3/4})$	$O(\sqrt{T})$
Yu & Neely [ 8 ]	Stochastic	Fixed	No	$O(1)$	$O(\sqrt{T})$
Cao & Liu [ 5 ]	Bandit	Time-varying	No	$O(\sqrt{T})$	$O(\sqrt{T})$
Li et al. [ 14 ]	Bandit	Time-varying	No	$O(T^{3/4})$	$O(\sqrt{T})$
Qin et al. [ 15 ]	Full-Info	Nonconvex	No	$O(T^{3/4})$	$O(\sqrt{T})$
Hamoud et al. [ 16 ]	Full-Info	Smooth	Yes ( $\delta_{c}$ )	0	N/A

TABLE I: Comparison of online convex optimization algorithms with constraints.

T

denotes the time horizon, and structure parameters

\delta_{c},P,K

are defined in Section IV .

Class	Regret $\mathcal{R}_{T}$	Violation $\mathcal{V}_{T}$
Adversarial	$O(\sqrt{T})$	$O(T^{3/4})$
Smooth $\mathcal{S}(\delta_{c})$	$O(\sqrt{T}+T\delta_{c})$	$O(\sqrt{T\delta_{c}}+T\delta_{c})$
Periodic $\mathcal{P}(P)$	$O(\sqrt{T}+T\bar{\delta}_{P})$	$O(\frac{T}{P}(\sqrt{P\bar{\delta}_{P}}+P\bar{\delta}_{P}+\log(T/P)))$
Sparse $\mathcal{K}(K)$	$O(\sqrt{KT}+K\log T)$	$O(\sqrt{KT})$

TABLE II: Summary of regret and violation bounds under each constraint variation class. Here

\delta_{c}

P

\bar{\delta}_{P}

, and

K

are structure parameters defined in Section IV . The adversarial row corresponds to no structural assumption.

Fig. 1: Cumulative constraint violation on synthetic OCO (

T=10{,}000

d=10

) across nine constraint variation configurations. Percentage labels indicate SA-PD’s reduction relative to PD-Fixed. SA-PD achieves 53–69% lower violation across all classes. Note the log scale.

Smooth ( $\delta_{c}=10^{-3}$ )
	PD-Fixed	VQ-OCO	SA-PD
Loss	7903 $\pm$ 12	7278 $\pm$ 11	7867 $\pm$ 12
Violation	312.9 $\pm$ 0.4	1379 $\pm$ 1.1	141.5 $\pm$ 0.2
Periodic ( $P=200$ )
Loss	4395 $\pm$ 8	4108 $\pm$ 8	4583 $\pm$ 9
Violation	343.1 $\pm$ 0.5	937.0 $\pm$ 0.8	105.3 $\pm$ 0.2

TABLE III: Cumulative violation and loss on synthetic OCO (

T=10{,}000

d=10

, 10 seeds). Best violation per row in bold .

Fig. 2: Violation scaling with horizon

T

under (a) smooth, (b) periodic, and (c) sparse-switching constraints. Dashed lines show

O(T^{3/4})

and

O(T^{1/2})

reference rates. SA-PD empirically tracks a rate closer to

O(T^{1/2})

on these instances, reflecting the small

\delta_{c}

and

\bar{\delta}_{P}

values in our experimental configurations (see Remark 2 for the theoretical regime analysis). This plot illustrates instance-dependent scaling and does not contradict the worst-case linear growth permitted by ( 8 ) for fixed

P

Dataset	Method	Violation	Loss
Electricity	PD-Fixed	163.4	7564
	VQ-OCO	338.0	7449
	SA-PD	77.2	7779
Traffic	PD-Fixed	6.3	3870
	VQ-OCO	6.4	3870
	SA-PD	6.1	3871

TABLE IV: Results on real-world datasets (10 seeds). Best violation in bold .

Fig. 3: Cumulative violation over time on real datasets. (a) Electricity scheduling with periodic capacity: SA-PD grows 53% slower than PD-Fixed. (b) ETT load management with 8 maintenance windows (dashed vertical lines): SA-PD’s staircase has smaller step heights at each change point.

Fig. 4: Ablation study. Each panel removes one SA-PD mechanism. Under smooth constraints, the adaptive

\beta

accounts for the majority of improvement. Under sparse-switching, the change-point reset is the dominant factor.

Online Convex Optimization

Online Convex Optimization studies sequential decisions under changing convex losses, seeking low regret with limited feedback and constraints.

See all 62 papers

Mar 22, 2026

Constrained Online Convex Optimization with Memory and Predictions

We study Constrained Online Convex Optimization with Memory (COCO-M), where both the loss and the constraints depend on a finite window of past decisions made by the learner. This setting extends the previously studied unconstrained online optimization with memory framework and captures practical problems such as the control of constrained dynamical systems and scheduling with reconfiguration budgets. For this problem, we propose the first algorithms that achieve sublinear regret and sublinear cumulative constraint violation under time-varying constraints, both with and without predictions of future loss and constraint functions. Without predictions, we introduce an adaptive penalty approach that guarantees sublinear regret and constraint violation. When short-horizon and potentially unreliable predictions are available, we reinterpret the problem as online learning with delayed feedback and design an optimistic algorithm whose performance improves as prediction accuracy improves, while remaining robust when predictions are inaccurate. Our results bridge the gap between classical constrained online convex optimization and memory-dependent settings, and provide a versatile learning toolbox with diverse applications.

Mohammed Abdullah, George Iosifidis, Salah Eddine Elayoubi +1

Université Paris-Saclay, CentraleSupélec, CNRS, L2S, Gif-sur-Yvette, France · Institut Polytechnique de Paris, Télécom SudParis, Palaiseau, France · Delft University of Technology, The Netherlands

Online Convex Optimization Online Learning

Ask PDF

Jun 30, 2026

Constrained Online Convex Optimization without Slater's Condition

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.

Kihyun Yu, Junehee Lee, Dabeen Lee

1KAIST · 2Seoul National University

Primal-Dual Optimization Online Convex Optimization Constrained Optimization

Ask PDF

Mar 21, 2026

Breaking the $O(\sqrt{T})$ Cumulative Constraint Violation Barrier while Achieving $O(\sqrt{T})$ Static Regret in Constrained Online Convex Optimization

The problem of constrained online convex optimization is considered, where at each round, once a learner commits to an action

x_t \in \mathcal{X} \subset \mathbb{R}^d

, a convex loss function

f_t

and a convex constraint function

g_t

that drives the constraint

g_t(x)\le 0

are revealed. The objective is to simultaneously minimize the static regret and cumulative constraint violation (CCV) compared to the benchmark that knows the loss functions and constraint functions

f_t

and

g_t

for all

t

ahead of time, and chooses a static optimal action that is feasible with respect to all

g_t(x)\le 0

. In recent prior work Sinha and Vaze [2024], algorithms with simultaneous regret of

O(\sqrt{T})

and CCV of

O(\sqrt{T})

or (CCV of

O(1)

in specific cases Vaze and Sinha [2025], e.g. when

d=1

) have been proposed. It is widely believed that CCV is

Ω(\sqrt{T})

for all algorithms that ensure that regret is

O(\sqrt{T})

with the worst case input for any

d\ge 2

. In this paper, we refute this and show that the algorithm of Vaze and Sinha [2025] simultaneously achieves regret of

O(\sqrt{T})

regret and CCV of

O(T^{1/3})

when

d=2

Haricharan Balasundaram, Karthick Krishna Mahendran, Rahul Vaze

Online Convex Optimization Constrained Optimization Regret Minimization

Ask PDF

Abstract

Online Convex Optimization

Explore similar work

Constrained Online Convex Optimization with Memory and Predictions

Constrained Online Convex Optimization without Slater's Condition

Breaking the O(T)O(\sqrt{T})O(T​) Cumulative Constraint Violation Barrier while Achieving O(T)O(\sqrt{T})O(T​) Static Regret in Constrained Online Convex Optimization

Breaking the $O(\sqrt{T})$ Cumulative Constraint Violation Barrier while Achieving $O(\sqrt{T})$ Static Regret in Constrained Online Convex Optimization