This paper investigates the problem of distributed online optimization with long-term constraints (LTC), where constraints are not required to be satisfied at each time step but only over a longer horizon. We first propose a baseline algorithm based on online regularized Lagrangian functions, achieving a regret bound of O(T3/4). By refining the Lagrangian functions and optimization strategies, we further improve the regret bound to O(T2/3). Notably, our results enforce strict satisfaction of LTC over time, in contrast to most existing works that focus solely on achieving sublinear cumulative constraint violations. Moreover, the obtained performance matches the optimal guarantees achievable in the centralized setting. Finally, we demonstrate the effectiveness of our approach through a distributed online regularized linear regression problem.
- Open Access
- Article
Distributed Online Convex Optimization with Long-Term Constraints: No Cumulative Constraint Violation
- Difeng Zhang 1,
- Shaofu Yang 2,*
Author Information
Received: 13 Sep 2025 | Revised: 03 Nov 2025 | Accepted: 22 Dec 2025 | Published: 11 Mar 2026
Abstract
References
- 1.
Avi, G.; Catherine, T. Online Display Advertising: Targeting and Obtrusiveness. Mark. Sci. 2011, 30, 389–404.
- 2.
Balseiro, S.R.; Lu, H.; Mirrokni, V. The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems. Oper. Res. 2023, 71, 101–119.
- 3.
Chen, T.; Ling, Q.; Giannakis, G.B. An Online Convex Optimization Approach to Proactive Network Resource Allocation. IEEE Trans. Signal Process. 2017, 65, 6350–6364.
- 4.
Mairal, J.; Bach, F.; Ponce, J.; et al. Online Dictionary Learning for Sparse Coding. In Proceedings of the 26th International Conference on Machine Learning (ICML), Montreal, QC, Canada, 14–18 June 2009; pp. 689–696.
- 5.
Zinkevich, M. Online Convex Programming and Generalized Infinitesimal Gradient Ascent. In Proceedings of the 20th International Conference on Machine Learning (ICML), Washington, DC, USA, 21–24 August 2003; pp. 928–936.
- 6.
Flaxman, A.D.; Kalai, A.T.; McMahan, H.B. Online Convex Optimization in the Bandit Setting: Gradient Descent without a Gradient. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Vancouver, BC, Canada, 23–25 January 2005; pp. 385–394.
- 7.
Agarwal, A.; Dekel, O.; Xiao, L. Optimal Algorithms for Online Convex Optimization with Multi-Point Bandit Feedback. In Proceedings of the 23rd Annual Conference on Learning Theory (COLT), Haifa, Israel, 27–29 June 2010; pp. 28–40.
- 8.
Koppel, A.; Jakubiec, F.Y.; Ribeiro, A. A Saddle Point Algorithm for Networked Online Convex Optimization. IEEE Trans. Signal Process. 2015, 63, 5149–5164.
- 9.
Yuan, J.; Lamperski, A. Online Convex Optimization for Cumulative Constraints. In Proceedings of the 32nd Neural Information Processing Systems (NeurIPS), Montreal, QC, Canada, 3–8 December 2018; pp. 6140–6149.
- 10.
Zhang, W.; Zhao, P.; Zhu, W.; et al. Projection-Free Distributed Online Learning in Networks. In Proceedings of the 34th International Conference onMachine Learning (ICML), Sydney, NSW, Australia, 6–11 August 2017; Volume 70, pp. 4054–4062.
- 11.
Mahdavi, M.; Jin, R.; Yang, T. Trading Regret for Efficiency: Online Convex Optimization with Long Term Constraints. J. Mach. Learn. Res. 2012, 13, 2503–2528.
- 12.
Yi, X.; Li, X.; Yang, T.; et al. Regret and Cumulative Constraint Violation Analysis for Online Convex Optimization with Long Term Constraints. In Proceedings of the 38th International Conference on Machine Learning (ICML), online, 18–24 July 2021; Volume 139, pp. 11998–12008.
- 13.
Jenatton, R.; Huang, J.C.; Archambeau, C. Adaptive Algorithms for Online Convex Optimization with Long-Term Constraints. In Proceedings of the 33rd International Conference on Machine Learning (ICML), New York, NY, USA, 19–24 June 2016; Volume 48, pp. 402–411.
- 14.
Yu, H.; Neely, M.J. A Low Complexity Algorithm with O(√T) Regret and O(1) Constraint Violations for Online Convex Optimization with Long Term Constraints. J. Mach. Learn. Res. 2020, 21, 1–24.
- 15.
Guo, H.; Liu, X.; Wei, H.; et al. Online Convex Optimization with Hard Constraints: Towards the Best of Two Worlds and Beyond. In Proceedings of the 36th International Conference on Neural Information Processing Systems, New Orleans, LA, USA, 28 November–9 December 2022; Volume 35, pp. 36426–36439.
- 16.
Yuan, D.; Proutiere, A.; Shi, G. Distributed Online Optimization with Long-Term Constraints. IEEE Trans. Autom. Control 2022, 67, 1089–1104.
- 17.
Yi, X.; Li, X.; Yang, T.; et al. Distributed Bandit Online Convex Optimization with Time-Varying Coupled Inequality Constraints. IEEE Trans. Autom. Control 2021, 66, 4620–4635.
- 18.
Li, X.; Yi, X.; Xie, L. Distributed Online Optimization for Multi-Agent Networks with Coupled Inequality Constraints. IEEE Trans. Autom. Control 2021, 66, 3575–3591.
- 19.
Yuan, D.; Ho, D.W.C.; Jiang, G.P. An Adaptive Primal-Dual Subgradient Algorithm for Online Distributed Constrained Optimization. IEEE Trans. Cybern. 2018, 48, 3045–3055.
- 20.
Abernethy, J.D.; Bartlett, P.L.; Rakhlin, A.; et al. Optimal Strategies and Minimax Lower Bounds for Online Convex Games. In Proceedings of the 21st Annual Conference on Learning Theory (COLT), Helsinki, Finland, 9–12 July 2008.
- 21.
Islam, M.A.; Ren, S.; Quan, G.; et al. An Adaptive Primal-Dual Subgradient Algorithm for Online Distributed Constrained Optimization. IEEE Trans. Cybern. 2018, 48, 3045–3055.
- 22.
Xiong, M.; Zhang, B.; Ho, D.W.C.; et al. Event-Triggered Distributed Stochastic Mirror Descent for Convex Optimization. IEEE Trans. Neural Netw. Learn. Syst. 2023, 34, 6480–6491.
This work is licensed under a Creative Commons Attribution 4.0 International License.
Suite 4002 Level 4, 447 Collins Street, Melbourne, Victoria 3000, Australia
General Inquiries: info@sciltp.com