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

• URL: http://arxiv.org/abs/2603.14319v1
• Date: Sun, 15 Mar 2026 10:30:35 GMT
• Title: Structure-Dependent Regret and Constraint Violation Bounds for Online Convex Optimization with Time-Varying Constraints
• Abstract summary: We introduce a structured characterization of constraint variation to common network phenomena.<n>We derive structure-dependent joint bounds that strictly improve upon adversarial rates when the constraint process exhibits regularity.<n>Experiments on synthetic benchmarks and real-world datasets demonstrate that SA-PD reduces cumulative constraint violation by up to 53%.
• Score: 12.438794398358548
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Guided Streaming Stochastic Interpolant Policy [8.673777984856075]
  Inference-time guidance is essential for steering generative robot policies toward dynamic objectives without retraining.<n>In this work, we derive the optimal guidance term for dynamic, unstructured Interpolants (SI)<n>We apply this framework to real-time control through the Streaming Interpolant Policy (SSIP)
  arXiv  Detail & Related papers  (2026-05-11T06:24:21Z)
• Alternating Gradient Flow Utility: A Unified Metric for Structural Pruning and Dynamic Routing in Deep Networks [52.153950303594684]
  We propose a decoupled kinetic paradigm inspired by Alternating Gradient Flow (AGF)<n>AGF accurately captures the network's structural "kinetic utility"<n>We design a hybrid routing framework that decouples AGF-guided offline structural search from online execution via zero-cost physical priors.
  arXiv  Detail & Related papers  (2026-03-12T18:19:21Z)
• When Learning Hurts: Fixed-Pole RNN for Real-Time Online Training [58.25341036646294]
  We analytically examine why learning recurrent poles does not provide tangible benefits in data and empirically offer real-time learning scenarios.<n>We show that fixed-pole networks achieve superior performance with lower training complexity, making them more suitable for online real-time tasks.
  arXiv  Detail & Related papers  (2026-02-25T00:15:13Z)
• Smooth embeddings in contracting recurrent networks driven by regular dynamics: A synthesis for neural representation [45.88028371034407]
  Recent empirical work has documented topology-preserving latent organization in trained recurrent models.<n>Recent theoretical results in reservoir computing establish conditions under which the synchronization map is an embedding.<n>Our contribution is an integrated framework that assembles generalized synchronization and embedding guarantees for contracting reservoirs.
  arXiv  Detail & Related papers  (2026-01-26T23:10:39Z)
• Unsupervised Online 3D Instance Segmentation with Synthetic Sequences and Dynamic Loss [52.28880405119483]
  Unsupervised online 3D instance segmentation is a fundamental yet challenging task.<n>Existing methods, such as UNIT, have made progress in this direction but remain constrained by limited training diversity.<n>We propose a new framework that enriches the training distribution through synthetic point cloud sequence generation.
  arXiv  Detail & Related papers  (2025-09-27T08:53:27Z)
• PowerGrow: Feasible Co-Growth of Structures and Dynamics for Power Grid Synthesis [75.14189839277928]
  We present PowerGrow, a co-generative framework that significantly reduces computational overhead while maintaining operational validity.<n> Experiments across benchmark settings show that PowerGrow outperforms prior diffusion models in fidelity and diversity.<n>This demonstrates its ability to generate operationally valid and realistic power grid scenarios.
  arXiv  Detail & Related papers  (2025-08-29T01:47:27Z)
• DeCo-SGD: Joint Optimization of Delay Staleness and Gradient Compression Ratio for Distributed SGD [5.618337879898599]
  Distributed machine learning in high-end-to-end latency and low, varying bandwidth networks undergoes severe throughput degradation.<n>Existing approaches typically employ gradient compression and delayed aggregation to alleviate low bandwidth and high latency.<n>We propose DeCoSGD, which dynamically adjusts the compression ratio and staleness based on the real-time network condition.
  arXiv  Detail & Related papers  (2025-07-23T09:22:51Z)
• Topology-Aware Conformal Prediction for Stream Networks [68.02503121089633]
  We propose Spatio-Temporal Adaptive Conformal Inference (textttCISTA), a novel framework that integrates network topology and temporal dynamics into the conformal prediction framework.<n>Our results show that textttCISTA effectively balances prediction efficiency and coverage, outperforming existing conformal prediction methods for stream networks.
  arXiv  Detail & Related papers  (2025-03-06T21:21:15Z)
• Leveraging Low-Rank and Sparse Recurrent Connectivity for Robust Closed-Loop Control [63.310780486820796]
  We show how a parameterization of recurrent connectivity influences robustness in closed-loop settings. We find that closed-form continuous-time neural networks (CfCs) with fewer parameters can outperform their full-rank, fully-connected counterparts.
  arXiv  Detail & Related papers  (2023-10-05T21:44:18Z)

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.