本文提出一种单循环分块交替近端梯度算法求解分块凸-非凹的极小极大优化问题。在该算法的每次迭代中, 采用近端梯度法交替更新目标函数中的各个变量。从理论上证明了算法达到ε-稳定点需要的迭代复杂度是O(ε-4), 这是求解分块凸-非凹的极小极大优化问题的首个带复杂度的单循环算法。
This paper proposes a single-loop block-alternating proximal gradient algorithm to solve block convex-nonconcave minimax optimization problems. In each iteration of the algorithm, the proximal gradient method is used to alternately update each variable in the objective function. We have theoretically proved that the algorithm achieves an ε-stationary point in O(ε-4) iterations. To the best of our knowledge, this is the first time that a single loop algorithm has been proposed to solve a block convexnonconcave minimax optimization problem.
[1] Goodfellow I, Pouget-Abadie J, Mirza M. Generative adversarial nets[C]//Advances in Neural Information Processing Systems, 2014: 2672-2680.
[2] Sinha A, Namkoong H, Duchi J. Certifiable distributional robustness with principled adversarial training[J]. 2017, arXiv: 1710.10571.
[3] Jordan M I. Artificial intelligence-the revolution hasn’t happened yet[J]. Harvard Data Science Review, 2019, 1(1): 1-9.
[4] Shamma J. Cooperative Control of Distributed Multi-Agent Systems[M]. New Jersey: John Wiley & Sons, 2008.
[5] Mateos G, Bazerque J A, Giannakis G B. Distributed sparse linear regression[J]. IEEE Transactions on Signal Processing, 2010, 58(10): 5262-5276.
[6] Nemirovski A. Prox-method with rate of convergence O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems [J]. SIAM Journal on Optimization, 2004, 15(1): 229-251.
[7] Nesterov Y. Dual extrapolation and its applications to solving variational inequalities and related problems[J]. Mathematical Programming, 2007, 109(2-3): 319-344.
[8] Tseng P. On accelerated proximal gradient methods for convex-concave optimization[EB/OL]. (2008-05-21)[2020-10-20]. https://www.csie.ntu.edu.tw/b97058/tseng/papers/apgm.pdf.
[9] Ouyang Y, Xu Y. Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems[J]. Mathematical Programming, 2019, 185: 1-35.
[10] Nouiehed M, Sanjabi M, Huang T, et al. Solving a class of non-convex min-max games using iterative first order methods[C]//Advances in Neural Information Processing Systems, 2019: 14934-14942.
[11] Thekumparampil K K, Jain P, Netrapalli P. Efficient algorithms for smooth minimax optimization[C]//Advances in Neural Information Processing Systems, 2019: 12680-12691.
[12] Lin T, Jin C, Jordan M. Near-optimal algorithms for minimax optimization[J]. 2020, arXiv: 2002.02417.
[13] Lin T, Jin C, Jordan M. On gradient descent ascent for nonconvex-concave minimax problems [C]//International Conference on Machine Learning, 2020: 6083-6093.
[14] Lu S, Tsaknakis I, Hong M, et al. Hybrid block successive approximation for one-sided nonconvex min-max problems: algorithms and applications[J]. IEEE Transactions on Signal Processing, 2020, 68: 3676-3691.
[15] Xu Z, Zhang H, Xu Y, et al. A unified single-loop alternating gradient projection algorithm for nonconvex-concave and convex-nonconcave minimax problems[J]. 2020, arXiv: 2006.02032.
[16] Nesterov Y. Introductory Lectures on Convex Optimization[M]. Berlin: Springer Science & Business Media, 2013.
