{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:20:44Z","timestamp":1750220444940,"version":"3.41.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2020,12,10]],"date-time":"2020-12-10T00:00:00Z","timestamp":1607558400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61906212 and 61773392"],"award-info":[{"award-number":["61906212 and 61773392"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"National Key R 8 D Program of China","award":["2018YFB1003203"],"award-info":[{"award-number":["2018YFB1003203"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Intell. Syst. Technol."],"published-print":{"date-parts":[[2021,2,28]]},"abstract":"<jats:p>\n            Recently, convex-concave bilinear Saddle Point Problems (SPP) is widely used in lasso problems, Support Vector Machines, game theory, and so on. Previous researches have proposed many methods to solve SPP, and present their convergence rate theoretically. To achieve linear convergence, analysis in those previouse studies requires strong convexity of \u03c6(\n            <jats:bold>z<\/jats:bold>\n            ). But, we find the linear convergence can also be achieved even for a general convex but not strongly convex \u03c6(\n            <jats:bold>z<\/jats:bold>\n            ). In the article, by exploiting the strong duality of SPP, we propose a new method to solve SPP, and achieve the linear convergence. We present a new general sufficient condition to achieve linear convergence, but do not require the strong convexity of \u03c6(\n            <jats:bold>z<\/jats:bold>\n            ). Furthermore, a more efficient method is also proposed, and its convergence rate is analyzed in theoretical. Our analysis shows that the well conditioned \u03c6(\n            <jats:bold>z<\/jats:bold>\n            ) is necessary to improve the efficiency of our method. Finally, we conduct extensive empirical studies to evaluate the convergence performance of our methods.\n          <\/jats:p>","DOI":"10.1145\/3420035","type":"journal-article","created":{"date-parts":[[2020,12,10]],"date-time":"2020-12-10T18:46:41Z","timestamp":1607626001000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["A Theoretical Revisit to Linear Convergence for Saddle Point Problems"],"prefix":"10.1145","volume":"12","author":[{"given":"Wendi","family":"Wu","sequence":"first","affiliation":[{"name":"State Key Laboratory of High Performance Computing, National University of Defense Technology, Changsha, Hunan, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yawei","family":"Zhao","sequence":"additional","affiliation":[{"name":"China Electronic Equipment System Engineering Company, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"En","family":"Zhu","sequence":"additional","affiliation":[{"name":"School of Computer, National University of Defense Technology, Changsha, Hunan, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xinwang","family":"Liu","sequence":"additional","affiliation":[{"name":"School of Computer, National University of Defense Technology, Changsha, Hunan, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xingxing","family":"Zhang","sequence":"additional","affiliation":[{"name":"Institute of Information Science, and Beijing Key Laboratory of Advanced Information Science and Network Technology, Beijing Jiaotong University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lailong","family":"Luo","sequence":"additional","affiliation":[{"name":"Science and Technology on Information Systems Engineering Laboratory, National University of Defense Technology, Changsha, Hunan, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shixiong","family":"Wang","sequence":"additional","affiliation":[{"name":"Artificial Intelligence Research Center, National Innovation Institute of Defense Technology, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianping","family":"Yin","sequence":"additional","affiliation":[{"name":"Department of Software Engineering, Dongguan University of Technology, Dongguan, Guangdong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,12,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1561\/2200000015"},{"volume-title":"Proceedings of the Conference on Learning Theory (COLT\u201919)","author":"Bach Francis","key":"e_1_2_1_2_1","unstructured":"Francis Bach and Kfir Y. Levy . 2019. A universal algorithm for variational inequalities adaptive to smoothness and noise . In Proceedings of the Conference on Learning Theory (COLT\u201919) . 164--194. Francis Bach and Kfir Y. Levy. 2019. A universal algorithm for variational inequalities adaptive to smoothness and noise. In Proceedings of the Conference on Learning Theory (COLT\u201919). 164--194."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the International Conference on Neural Information Processing Systems (NeurIPS\u201916)","author":"Balamurugan P.","year":"2016","unstructured":"P. Balamurugan and Francis Bach . 2016 . Stochastic variance reduction methods for saddle-point problems . In Proceedings of the International Conference on Neural Information Processing Systems (NeurIPS\u201916) . 1416--1424. P. Balamurugan and Francis Bach. 2016. Stochastic variance reduction methods for saddle-point problems. In Proceedings of the International Conference on Neural Information Processing Systems (NeurIPS\u201916). 1416--1424."},{"volume-title":"Convex Optimization","author":"Boyd Stephen","key":"e_1_2_1_4_1","unstructured":"Stephen Boyd and Lieven Vandenberghe . 2004. Convex Optimization . Cambridge University Press , New York, NY . Stephen Boyd and Lieven Vandenberghe. 2004. Convex Optimization. Cambridge University Press, New York, NY."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10851-010-0251-1"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0957-3"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/130919362"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1080\/10618600.2014.948181"},{"key":"e_1_2_1_9_1","unstructured":"Cong Dang and Guanghui Lan. 2014. Randomized first-order methods for saddle point optimization. Retrieved from https:\/\/arxiv:math.OC\/1409.8625v4.  Cong Dang and Guanghui Lan. 2014. Randomized first-order methods for saddle point optimization. Retrieved from https:\/\/arxiv:math.OC\/1409.8625v4."},{"volume-title":"Proceedings of the Conference on Machine Learning Research. 196--205","author":"Simon","key":"e_1_2_1_10_1","unstructured":"Simon S. Du and Wei Hu. 2019. Linear convergence of the primal-dual gradient method for convex-concave saddle point problems without strong convexity . In Proceedings of the Conference on Machine Learning Research. 196--205 . Simon S. Du and Wei Hu. 2019. Linear convergence of the primal-dual gradient method for convex-concave saddle point problems without strong convexity. In Proceedings of the Conference on Machine Learning Research. 196--205."},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the Advances in Neural Information Processing Systems (NeurIPS\u201914)","author":"Goodfellow Ian","year":"2014","unstructured":"Ian Goodfellow , Jean Pouget-Abadie , Mehdi Mirza , Bing Xu , David Warde-Farley , Sherjil Ozair , Aaron Courville , and Yoshua Bengio . 2014 . Generative adversarial nets . In Proceedings of the Advances in Neural Information Processing Systems (NeurIPS\u201914) . 2672--2680. Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. 2014. Generative adversarial nets. In Proceedings of the Advances in Neural Information Processing Systems (NeurIPS\u201914). 2672--2680."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783313"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1561\/2400000013"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/14096757X"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0308738101"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-46128-1_50"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1080\/10556788.2016.1266355"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 36th International Conference on Machine Learning. 3642--3651","author":"Lange Kenneth","year":"2019","unstructured":"Kenneth Lange , Joong-Ho Won , and Jason Xu . 2019 . Projection onto Minkowski sums with application to constrained learning . In Proceedings of the 36th International Conference on Machine Learning. 3642--3651 . Kenneth Lange, Joong-Ho Won, and Jason Xu. 2019. Projection onto Minkowski sums with application to constrained learning. In Proceedings of the 36th International Conference on Machine Learning. 3642--3651."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623403425629"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623403425629"},{"key":"e_1_2_1_21_1","first-page":"543","article-title":"A method for solving the convex programming problem with convergence rate O(1\/k2)","volume":"269","author":"Nesterov Yurii","year":"1983","unstructured":"Yurii Nesterov . 1983 . A method for solving the convex programming problem with convergence rate O(1\/k2) . Soviet Math. Doklady 269 (1983), 543 -- 547 . Yurii Nesterov. 1983. A method for solving the convex programming problem with convergence rate O(1\/k2). Soviet Math. Doklady 269 (1983), 543--547.","journal-title":"Soviet Math. Doklady"},{"key":"e_1_2_1_22_1","unstructured":"Yuyuan Ouyang and Yangyang Xu. 2019. Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems. Math. Program. https:\/\/link.springer.com\/article\/10.1007\/s10107-019-01420-0.  Yuyuan Ouyang and Yangyang Xu. 2019. Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems. Math. Program. https:\/\/link.springer.com\/article\/10.1007\/s10107-019-01420-0."},{"volume-title":"Understanding Machine Learning: From Theory to Algorithms","author":"Shalev-Shwartz Shai","key":"e_1_2_1_23_1","unstructured":"Shai Shalev-Shwartz and Shai Ben-David . 2014. Understanding Machine Learning: From Theory to Algorithms . Cambridge University Press , New York, NY . Shai Shalev-Shwartz and Shai Ben-David. 2014. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, New York, NY."},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 34th International Conference on Machine Learning (ICML\u201917)","author":"Wang Jialei","year":"2017","unstructured":"Jialei Wang and Lin Xiao . 2017 . Exploiting strong convexity from data with primal-dual first-order algorithms . In Proceedings of the 34th International Conference on Machine Learning (ICML\u201917) . 3694--3702. Jialei Wang and Lin Xiao. 2017. Exploiting strong convexity from data with primal-dual first-order algorithms. In Proceedings of the 34th International Conference on Machine Learning (ICML\u201917). 3694--3702."},{"key":"e_1_2_1_25_1","unstructured":"E. Yazdandoost Hamedani and N. Serhat Aybat. 2018. A primal-dual algorithm for general convex-concave saddle point problems. Retrieved from https:\/\/arxiv:math.OC\/1803.01401.  E. Yazdandoost Hamedani and N. Serhat Aybat. 2018. A primal-dual algorithm for general convex-concave saddle point problems. Retrieved from https:\/\/arxiv:math.OC\/1803.01401."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2865342"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2019.2923239"}],"container-title":["ACM Transactions on Intelligent Systems and Technology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3420035","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3420035","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:47:39Z","timestamp":1750193259000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3420035"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,10]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,2,28]]}},"alternative-id":["10.1145\/3420035"],"URL":"https:\/\/doi.org\/10.1145\/3420035","relation":{},"ISSN":["2157-6904","2157-6912"],"issn-type":[{"type":"print","value":"2157-6904"},{"type":"electronic","value":"2157-6912"}],"subject":[],"published":{"date-parts":[[2020,12,10]]},"assertion":[{"value":"2020-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-12-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}