一种求解凸-PL极小极大优化问题的随机交替梯度投影算法
A Stochastic Alternating Gradient Projection Algorithm for Convex-PL Minimax Optimization Problems
DOI: 10.12677/ORF.2023.131031, PDF,    科研立项经费支持
作者: 覃媛媛, 王福胜, 王 静：太原师范学院数学与统计学院，山西 晋中
关键词: 机器学习；凸-PL；GDA算法；随机梯度；Machine Learning； Convex-PL； GDA Algorithm； Stochastic Gradient
摘要: 针对机器学习中常见的一类非凸极小极大优化问题，本文提出了一种新的随机交替梯度投影算法，该算法基于交替梯度投影算法，在随机环境中用随机梯度进行更新，和随机交替梯度下降–上升算法相比，运算效率大大提高。在高斯分布数据集上的数值实验结果表明新算法是可行有效的。
Abstract: To solve a class of nonconvex minimax optimization problems in machine learning, we propose a new stochastic alternating gradient projection algorithm (SAGP). This algorithm is based on the alternating gradient projection algorithm (AGP), which is updated with stochastic gradients in a stochastic environment. Compared with the stochastic alternating gradient descent ascent algorithm (SAGDA), the operation efficiency is greatly improved. Numerical experiments on Gaussian distributed data sets show that the new algorithm is feasible and effective.
文章引用：覃媛媛, 王福胜, 王静. 一种求解凸-PL极小极大优化问题的随机交替梯度投影算法[J]. 运筹与模糊学, 2023, 13(1): 292-297. https://doi.org/10.12677/ORF.2023.131031

参考文献

[1] Nemirovski, A. (2004) Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems. SIAM Journal on Optimization, 15, 229-251. [Google Scholar] [CrossRef] 
[2] Nesterov, Y. (2007) Dual Extrapolation and Its Applications to Solving Variational Inequalities and Related Problems. Mathematical Programming, 109, 319-344. [Google Scholar] [CrossRef] 
[3] Monteiro, R.D.C. and Svaiter, B.F. (2010) On the Complexity of the Hybrid Proximal Extragradient Method for the Iterates and the Ergodic Mean. SIAM Journal on Optimization, 20, 2755-2787. [Google Scholar] [CrossRef] 
[4] Monteiro, R.D.C. and Svaiter, B.F (2011) Complexity of Variants of Tseng’s Modified F-B Splitting and Korpelevich’s Methods for Hemivariational Inequalities with Applications to Saddle-Point and Convex Optimization Problems. SIAM Journal on Optimization, 21, 1688-1720. [Google Scholar] [CrossRef] 
[5] Abernethy, J., Lai, K.A. and Wibisono, A. (2019) Last-Iterate Convergence Rates for Min-Max Optimization. ArXiv Preprint arxiv: 1906.02027.
[6] Rafique, H., Liu, M., Lin, Q. and Yang, T. (2018) Non-Convex Min-Max Optimization: Provable Algorithms and Applications in Machine Learning. ArXiv Preprint arXiv: 1810.02060.
[7] Nouiehed, M., Sanjabi, M., Huang, T., Lee, J.D. and Razaviyayn, M. (2019) Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods. 33rd Con-ference on Neural Information Processing Systems (NeurIPS 2019), Vancouver, 8-14 December 2019, 14934-14942.
[8] Thekumparampil, K.K., Jain, P., Netrapalli, P. and Oh, S. (2019) Efficient Algorithms for Smooth Minimax Optimization. 33rd Conference on Neural Information Processing Systems (NeurIPS 2019), Vancouver, 8-14 December 2019, 12659-12670.
[9] Kong, W. and Monteiro, R.D.C. (2021) An Accelerated Inexact Proximal Point Method for Solving Non-convex Concave Min-Max Problems. SIAM Journal on Optimization, 31, 2558-2585. [Google Scholar] [CrossRef] 
[10] Lin, T., Jin, C. and Jordan, M.I. (2020) Near-Optimal Algorithms for Minimax Optimization. In: Abernethy, J. and Agarwal, S., Eds., Proceedings of Thirty Third Conference on Learning Theory, PMLR 125, ML Research Press, Maastricht, 2738-2779.
[11] Lin, T., Jin, C. and Jordan, M.I. (2020) On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems. In: Daumé III, H. and Singh, S., Eds., Proceedings of the 37th International Con-ference on Machine Learning, PMLR 119, ML Research Press, Maastricht, 6083-6093.
[12] Jin, C., Netrapalli, P. and Jordan, M.I. (2019) Minmax Optimization: Stable Limit Points of Gradient Descent Ascent Are Locally Optimal. ArXiv Preprint arXiv: 1902.00618.
[13] Lu, S., Tsaknakis, I., Hong, M. and Chen, Y. (2020) Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications. IEEE Transactions on Signal Processing, 68, 3676-3691. [Google Scholar] [CrossRef] 
[14] Xu, Z., Zhang, H., Xu, Y. and Lan, G. (2020) A Unified Single-loop Alternating Gradient Projection Algorithm for Nonconvex-Concave and Convex-Nonconcave Minimax Problems. ArXiv Preprint arXiv: 2006.02032.
[15] Boţ, R.I. and Böhm, A. (2020) Alternating Proximal-Gradient Steps for (Stochastic) Noncon-vex-Concave Minimax Problems. ArXiv Preprint arXiv: 2007.13605.
[16] Zhang, J., Xiao, P., Sun, R. and Luo, Z.-Q. (2020) A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problems. 34th Conference on Neural Information Processing Systems (NeurIPS 2020), Vancouver, 6-12 December 2020.
[17] Yang, J., Orvieto, A., Lucchi, A. and He, N. (2022) Faster Single-Loop Algorithms for Minimax Optimization without Strong Concavity. In: Camps-Valls, G., Ruiz, F.J.R. and Valera, I., Eds., Proceedings of the 25th International Conference on Artificial Intelligence and Statistics, PMLR 151, ML Research Press, Maastricht, 5485-5517.
[18] Chambolle, A. and Pock, T. (2016) On the Ergodic Convergence Rates of a First-Order Primaldual Algorithm. Mathematical Programming, 159, 253-287. [Google Scholar] [CrossRef] 
[19] Daskalakis, C. and Panageas, I. (2018) The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization. 32nd Conference on Neural Information Processing Systems (NeurIPS 2018), Montréal, 2-8 December 2018, 9236-9246.
[20] Polyak, B.T. (1963) Gradient Methods for Minimizing Functionals. Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki, 3, 643-653.
[21] Fazel, M., Ge, R., Kakade, S. and Mesbahi, M. (2018) Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator. In: Dy, J. and Krause, A., Eds., Proceedings of the 35th International Conference on Machine Learning, PMLR 80, ML Research Press, Maastricht, 1467-1476.
[22] Liu, C., Zhu, L. and Belkin, M. (2020) Loss Landscapes and Optimization in Over-Parameterized Non-Linearsystems and Neural Net-works. ArXiv Preprint arXiv: 2003.00307.
[23] Yang, J., Kiyavash, N. and He, N. (2020) Global Convergence and Variance Reduction for a Class of Nonconvex-Nonconcave Minimax Problems. 34th Conference on Neural Information Processing Sys-tems (NeurIPS 2020), Vancouver, 6-12 December 2020, 1153-1165.
[24] Guo, Z., Liu, M., Yuan, Z., Shen, L., Liu, W. and Yang, T. (2020) Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks. In: Daumé III, H. and Singh, A., Eds., Proceedings of the 37th International Conference on Machine Learning, PMLR 119, ML Research Press, Maas-tricht, 3864-3874.
[25] Cai, Q., Hong, M., Chen, Y. and Wang, Z. (2019) On the Global Convergence of Imitation Learning: A Case for Linear Quadratic Regulator. ArXiv Preprint arXiv: 1901.03674.
[26] Du, S., Lee, J., Li, H., Wang, L. and Zhai, X. (2019) Gradient Descent Finds Global Minima of Deep Neural Networks. In: Chaudhuri, K. and Salakhutdinov, R., Eds., Proceedings of the 36th International Conference on Machine Learning, PMLR 97, ML Research Press, Maastricht, 1675-1685.
[27] Rafique, H., Liu, M., Lin, Q. and Yang, T. (2022) Weakly-Convex-Concave Min-Max Optimization Provable Algo-rithms and Applications in Machine Learning. Optimization Methods and Software, 37, 1087-1121. [Google Scholar] [CrossRef] 

为你推荐