Augmented Lagrangian Methods for Time-Varying Constrained Online Convex Optimization

doi:10.1007/s40305-023-00496-y

Abstract

Abstract: In this paper, we consider online convex optimization (OCO) with time-varying loss and constraint functions. Specifically, the decision-maker chooses sequential decisions based only on past information; meantime, the loss and constraint functions are revealed over time. We first develop a class of model-based augmented Lagrangian methods (MALM) for time-varying functional constrained OCO (without feedback delay). Under standard assumptions, we establish sublinear regret and sublinear constraint violation of MALM. Furthermore, we extend MALM to deal with time-varying functional constrained OCO with delayed feedback, in which the feedback information of loss and constraint functions is revealed to decision-maker with delays. Without additional assumptions, we also establish sublinear regret and sublinear constraint violation for the delayed version of MALM. Finally, numerical results for several examples of constrained OCO including online network resource allocation, online logistic regression and online quadratically constrained quadratical program are presented to demonstrate the efficiency of the proposed algorithms.

Key words: Online convex optimization, Time-varying constraints, Augmented Lagrangian, Regret, Constraint violation

CLC Number:

Hao-Yang Liu, Xian-Tao Xiao, Li-Wei Zhang. Augmented Lagrangian Methods for Time-Varying Constrained Online Convex Optimization[J]. Journal of the Operations Research Society of China, 2025, 13(2): 364-392.

TrendMD

References

[1] Shalev-Shwartz, S.: Online learning and online convex optimization. Found. Trends^® Mach. Learn. 4(2), 107-194 (2011)
[2] Hazan, E.: Introduction to online convex optimization. Found. Trends^® Optim. 2(3-4), 157-325 (2015)
[3] Hoi, S.C.H., Sahoo, D., Lu, J., Zhao, P.: Online learning: a comprehensive survey. Neurocomputing 459, 249-289 (2021)
[4] Zinkevich, M.: Online convex programming and generalized infinitesimal gradient ascent. In: Proceedings of the 20th International Conference on Machine Learning, pp. 928-935 (2003)
[5] Hazan, E., Agarwal, A., Kale, S.: Logarithmic regret algorithms for online convex optimization. Mach. Learn. 69, 169-192 (2007)
[6] Dixit, R., Bedi, A.S., Tripathi, R., Rajawat, K.: Online learning with inexact proximal online gradient descent algorithms. IEEE Trans. Signal Process. 67(5), 1338-1352 (2019)
[7] Mahdavi, M., Jin, R., Yang, T.: Trading regret for efficiency: online convex optimization with long term constraints. J. Mach. Learn. Res. 13, 2503-2528 (2012)
[8] 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. 21, 1-24 (2020)
[9] Mannor, S., Tsitsiklis, J.N., Yu, J.Y.: Online learning with sample path constraints. J. Mach. Learn. Res. 10, 569-590 (2009)
[10] Paternain, S., Ribeiro, A.: Online learning of feasible strategies in unknown environments. IEEE Trans. Automat. Control 62(6), 2807-2822 (2017)
[11] Chen, T., Ling, Q., Giannakis, G.B.: An online convex optimization approach to proactive network resource allocation. IEEE Trans. Signal Process. 65(24), 6350-6364 (2017)
[12] Neely, M.J., Yu, H.: Online convex optimization with time-varying constraints. arXiv:1702.04783 (2017)
[13] Cao, X., Liu, K.J.R.: Online convex optimization with time-varying constraints and bandit feedback. IEEE Trans. Automat. Control 64(7), 2665-2680 (2019)
[14] Zhang, Y., Dall’Anese, E., Hong, M.: Online proximal-ADMM for time-varying constrained convex optimization. IEEE Trans. Signal Inform. Process. Netw. 7, 144-155 (2021)
[15] Fazlyab, M., Paternain, S., Preciado, V.M., Ribeiro, A.: Prediction-correction interior-point method for time-varying convex optimization. IEEE Trans. Automat. Control 63(7), 1973-1986 (2018)
[16] Cao, X., Başar, T.: Decentralized online convex optimization based on signs of relative states. Automatica J. IFAC 129, 109676-13 (2021)
[17] Yi, X., Li, X., Yang, T., Xie, L., Chai, T., Johansson, K.H.: Distributed bandit online convex optimization with time-varying coupled inequality constraints. IEEE Trans. Automat. Control 66(10), 4620-4635 (2021)
[18] Rockafellar, R.T.: Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Math. Oper. Res. 1(2), 97-116 (1976)
[19] Zhao, X.-Y., Sun, D., Toh, K.-C.: A Newton-CG augmented Lagrangian method for semidefinite programming. SIAM J. Optim. 20(4), 1737-1765 (2010)
[20] Chatzipanagiotis, N., Dentcheva, D., Zavlanos, M.M.: An augmented Lagrangian method for distributed optimization. Math. Program. 152(1-2, Ser. A), 405-434 (2015)
[21] Chatzipanagiotis, N., Zavlanos, M.M.: A distributed algorithm for convex constrained optimization under noise. IEEE Trans. Automat. Control 61(9), 2496-2511 (2016)
[22] Moradian, H., Kia, S.S.: Cluster-based distributed augmented Lagrangian algorithm for a class of constrained convex optimization problems. Automatica J. IFAC 129, 109608 (2021)
[23] Zhang, L., Zhang, Y., Wu, J., Xiao, X.: Solving stochastic optimization with expectation constraints efficiently by a stochastic augmented Lagrangian-type algorithm. INFORMS J. Comput. 34(6), 2989-3006 (2022)
[24] Zinkevich, M., Langford, J., Smola, A.: Slow learners are fast. In: Advances in Neural Information Processing Systems, vol. 22, pp. 2331-2339 (2009)
[25] Joulani, P., Gyorgy, A., Szepesvari, C.: Online learning under delayed feedback. In: Proceedings of Machine Learning Research, vol. 28, pp. 1453-1461. PMLR, Atlanta (2013)
[26] Pan, W., Shi, G., Lin, Y., Wierman, A.: Online optimization with feedback delay and nonlinear switching cost. Proc. ACM Meas. Anal. Comput. Syst. 6(1), 1-34 (2022)
[27] Cao, X., Zhang, J., Poor, H.V.: Constrained online convex optimization with feedback delays. IEEE Trans. Automat. Control 66(11), 5049-5064 (2021)
[28] Asi, H., Duchi, J.C.: Stochastic (approximate) proximal point methods: convergence, optimality, and adaptivity. SIAM J. Optim. 29(3), 2257-2290 (2019)
[29] Liakopoulos, N., Destounis, A., Paschos, G., Spyropoulos, T., Mertikopoulos, P.: Cautious regret minimization: online optimization with long-term budget constraints. In: Proceedings of the 36th International Conference on Machine Learning, vol. 97, pp. 3944-3952 (2019)
[30] Bernstein, A., Dall’Anese, E., Simonetto, A.: Online primal-dual methods with measurement feedback for time-varying convex optimization. IEEE Trans. Signal Process. 67(8), 1978-1991 (2019)
[31] Zhang, L., Liu, H., Xiao, X.: Regrets of proximal method of multipliers for online non-convex optimization with long term constraints. J. Glob. Optim. 85(1), 61-80 (2023)
[32] Grant, M., Boyd, S.: CVX: Matlab Software for Disciplined Convex Programming, version 2.1. http://cvxr.com/cvx (2014)
[33] Yi, X., Li, X., Xie, L., Johansson, K.H.: Distributed online convex optimization with time-varying coupled inequality constraints. IEEE Trans. Signal Process. 68, 731-746 (2020)
[34] Cao, X., Başar, T.: Decentralized online convex optimization with event-triggered communications. IEEE Trans. Signal Process. 69, 284-299 (2021)
[35] Wang, C., Xu, S.: Distributed online constrained optimization with feedback delays. IEEE Trans. Neural Netw. Learn Syst. (2023). Online first
[36] Liu, P., Lu, K., Xiao, F., Wei, B., Zheng, Y.: Online distributed learning for aggregative games with feedback delays. IEEE Trans. Automat. Control (2023). https://doi.org/10.1109/TAC.2023.3237781