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

Constrained Online Convex Optimization with Memory and Predictions
Mar 22, 2026Mohammed Abdullah, George Iosifidis, Salah Eddine Elayoubi +1Online Convex Optimization Online Learning
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
Constrained Online Convex Optimization without Slater's Condition
Jun 30, 2026Kihyun Yu, Junehee Lee, Dabeen LeePrimal-Dual Optimization Online Convex Optimization
1KAIST · 2Seoul National University
Breaking the $O(\sqrt{T})$ Cumulative Constraint Violation Barrier while Achieving $O(\sqrt{T})$ Static Regret in Constrained Online Convex Optimization
Mar 21, 2026Haricharan Balasundaram, Karthick Krishna Mahendran, Rahul VazeOnline Convex Optimization Constrained Optimization

Mar 22, 2026J/K move · Enter open · S save

Constrained Online Convex Optimization with Memory and Predictions

Mohammed Abdullah, George Iosifidis, Salah Eddine Elayoubi, Tijani Chahed

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

Open paper AskPDF arXiv

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.

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