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

arXiv: https://arxiv.org/abs/2603.14319 · HTML: https://mlsanity.com/paper/2603.14319/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 56 references that are in the map.
- First posted on arXiv 15 Mar 2026.

## Builds on (most cited first, 16 of 16)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Online Convex Optimization with Stochastic Constraints](https://mlsanity.com/paper/1708.03741/) (2017)
- [Online convex optimization for cumulative constraints](https://mlsanity.com/paper/1802.06472/) (2018)
- [An Online Convex Optimization Approach to Dynamic Network Resource Allocation](https://mlsanity.com/paper/1701.03974/) (2017)
- [Optimal Algorithms for Online Convex Optimization with Adversarial Constraints](https://mlsanity.com/paper/2310.18955/) (2023)
- [Simultaneously Achieving Sublinear Regret and Constraint Violations for Online Convex Optimization with Time-varying Constraints](https://mlsanity.com/paper/2111.07707/) (2021)
- [Online Proximal-ADMM For Time-varying Constrained Convex Optimization](https://mlsanity.com/paper/2005.03267/) (2020)
- [Dynamic Regret of Adaptive Gradient Methods for Strongly Convex Problems](https://mlsanity.com/paper/2209.01608/) (2022)
- [Universal Online Convex Optimization with Minimax Optimal Second-Order Dynamic Regret](https://mlsanity.com/paper/1907.00497/) (2019)
- [Distributed Management of Fluctuating Energy Resources in Dynamic Networked Systems](https://mlsanity.com/paper/2405.19015/) (2024)
- [Distributed Event-Triggered Bandit Convex Optimization with Time-Varying Constraints](https://mlsanity.com/paper/2406.14060/) (2024)
- [Slicing for AI: An Online Learning Framework for Network Slicing Supporting AI Services](https://mlsanity.com/paper/2411.02412/) (2024)
- [Safety in the Face of Adversity: Achieving Zero Constraint Violation in Online Learning with Slowly Changing Constraints](https://mlsanity.com/paper/2505.00398/) (2025)
- [Distributed Online Stochastic Convex-Concave Optimization: Dynamic Regret Analyses under Single and Multiple Consensus Steps](https://mlsanity.com/paper/2508.09411/) (2025)

## Abstract (arXiv)

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.