An efficient algorithm for nonconvex-linear minimax optimization problem and its application in solving weighted maximin dispersion problem. (English) Zbl 1468.90141
Summary: In this paper, we study the minimax optimization problem that is nonconvex in one variable and linear in the other variable, which is a special case of nonconvex-concave minimax problem, which has attracted significant attention lately due to their applications in modern machine learning tasks, signal processing and many other fields. We propose a new alternating gradient projection algorithm and prove that it can find an \(\varepsilon\)-first-order stationary solution within \(\mathcal{O}\left(\varepsilon^{-3}\right)\) projected gradient step evaluations. Moreover, we apply it to solve the weighted maximin dispersion problem and the numerical results show that the proposed algorithm outperforms the state-of-the-art algorithms.
MSC:
| 90C47 | Minimax problems in mathematical programming |
| 90C60 | Abstract computational complexity for mathematical programming problems |
Software:
SBEEDReferences:
| [1] | Cesa-Bianchi, N.; Lugosi, G., Prediction, learning, and games (2006), Cambridge: Cambridge University Press, Cambridge · Zbl 1114.91001 · doi:10.1017/CBO9780511546921 |
| [2] | Chen, Y., Ye, X.: Projection onto a simplex. arXiv preprint arXiv:1101.6081, (2011) |
| [3] | Dai, B., Shaw, A., Li, L., Xiao, L., He, N., Liu, Z., Chen, J., Sbeed, L. S.: Convergent reinforcement learning with nonlinear function approximation. arXiv preprint arXiv:1712.10285, (2017) |
| [4] | Daskalakis, C., Ilyas, A., Syrgkanis, V., Zeng, H.: Training gans with optimism. arXiv preprint arXiv:1711.00141, (2017) |
| [5] | Daskalakis, C., Panageas, I.: The limit points of (optimistic) gradient descent in min-max optimization. In Advances in neural information processing systems, pp. 9236-9246, (2018) |
| [6] | Dolan, ED; Moré, JJ, Benchmarking optimization software with performance profiles, Math. Program., 91, 2, 201-213 (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263 |
| [7] | Drezner, Z.; Wesolowsky, GO, A maximin location problem with maximum distance constraints, AIIE Trans., 12, 3, 249-252 (1980) · doi:10.1080/05695558008974513 |
| [8] | Facchinei, F.; Pang, J-S, Finite-dimensional variational inequalities and complementarity problems (2007), Berlin: Springer, Berlin · Zbl 1062.90002 |
| [9] | Goodfellow, I., Pouget-Abadie, J., Mirza, M., Xu, B., Warde-Farley, D., Ozair, S., Courville, A., Bengio, Y.: Generative adversarial nets. In Advances in neural information processing systems, pp. 2672-2680, (2014) |
| [10] | Haines, S.; Loeppky, J.; Tseng, P.; Wang, X., Convex relaxations of the weighted maxmin dispersion problem, SIAM J. Optim., 23, 4, 2264-2294 (2013) · Zbl 1295.90110 · doi:10.1137/120888880 |
| [11] | Hamedani, E. Y., Jalilzadeh, A., Aybat, N.S., Shanbhag, U.V.: Iteration complexity of randomized primal-dual methods for convex-concave saddle point problems. arXiv preprint arXiv:1806.04118, (2018) |
| [12] | Johnson, ME; Moore, LM; Ylvisaker, D., Minimax and maximin distance designs, J. Stat. Plan. Inference, 26, 2, 131-148 (1990) · doi:10.1016/0378-3758(90)90122-B |
| [13] | Lu, S., Tsaknakis, I., Hong, M., Chen, Y.: Hybrid block successive approximation for one-sided non-convex min-max problems: algorithms and applications. arXiv preprint arXiv:1902.08294, (2019) |
| [14] | Madry, A., Makelov, A., Schmidt, L., Tsipras, D., Vladu, A.: Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:1706.06083, (2017) |
| [15] | Monteiro, RDC; Svaiter, BF, On the complexity of the hybrid proximal extragradient method for the iterates and the ergodic mean, SIAM J. Optim., 20, 6, 2755-2787 (2010) · Zbl 1230.90200 · doi:10.1137/090753127 |
| [16] | Nouiehed, M., Sanjabi, M., Huang, T., Lee, J.D., Razaviyayn, M.: Solving a class of non-convex min-max games using iterative first order methods. In Advances in Neural Information Processing Systems, pp. 14905-14916, (2019) |
| [17] | Qian, Qi, Zhu, Shenghuo, Tang, Jiasheng, Jin, Rong, Sun, Baigui, Li, Hao: Robust optimization over multiple domains. Proceedings of the AAAI Conference on Artificial Intelligence Vol 33, pp 4739-4746 (2019) |
| [18] | Rafique, H., Liu, M., Lin, Q., Yang, T.: Non-convex min-max optimization: Provable algorithms and applications in machine learning. arXiv preprint arXiv:1810.02060, (2018) |
| [19] | Sanjabi, M., Ba, J., Razaviyayn, M., Lee, J.D.: On the convergence and robustness of training gans with regularized optimal transport. In Advances in Neural Information Processing Systems, pp. 7091-7101, (2018) |
| [20] | Schaback, R., Multivariate interpolation and approximation by translates of a basis function, Ser. Approx. Decompos., 6, 491-514 (1995) · Zbl 1139.41301 |
| [21] | Sinha, A.; Namkoong, H.; Duchi, J., Certifiable distributional robustness with principled adversarial training, Statistics, 29, 1050 (2017) |
| [22] | Wang, S.; Xia, Y., On the ball-constrained weighted maximin dispersion problem, SIAM J. Optim., 26, 3, 1565-1588 (2016) · Zbl 1346.90659 · doi:10.1137/15M1047167 |
| [23] | White, DJ, A heuristic approach to a weighted maxmin dispersion problem, IMA J. Manag. Math., 7, 3, 219-231 (1996) · Zbl 0851.90076 · doi:10.1093/imaman/7.3.219 |
| [24] | Wu, Z.; Xia, Y.; Wang, S., Approximating the weighted maximin dispersion problem over an \(\ell_p\)-ball: SDP relaxation is misleading, Optim. Lett., 12, 4, 875-883 (2018) · Zbl 1404.90139 · doi:10.1007/s11590-017-1177-y |
| [25] | Xu, H.; Caramanis, C.; Mannor, S., Robustness and regularization of support vector machines, J. Mach. Learn. Res., 10, Jul, 1485-1510 (2009) · Zbl 1235.68209 |
| [26] | Xu, Z.; Wang, S.; Huang, J., An efficient low complexity algorithm for box-constrained weighted maximin disperision problem, J. Ind. Manag. Optim. (2020) · Zbl 1474.90287 · doi:10.3934/jimo.2020007 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
