Zeroth-order single-loop algorithms for nonconvex-linear minimax problems

Jingjing Shen, Ziqi Wang and Zi Xu ()
Additional contact information
Jingjing Shen: Shanghai University
Ziqi Wang: Shanghai University
Zi Xu: Shanghai University

Journal of Global Optimization, 2023, vol. 87, issue 2, No 11, 580 pages

Abstract: Abstract Nonconvex minimax problems have attracted significant interest in machine learning and many other fields in recent years. In this paper, we propose a new zeroth-order alternating randomized gradient projection algorithm to solve smooth nonconvex-linear problems and its iteration complexity to find an $$\varepsilon $$ ε -first-order Nash equilibrium is $${\mathcal {O}}\left( \varepsilon ^{-3} \right) $$ O ε - 3 and the number of function value estimation per iteration is bounded by $${\mathcal {O}}\left( d_{x}\varepsilon ^{-2} \right) $$ O d x ε - 2 . Furthermore, we propose a zeroth-order alternating randomized proximal gradient algorithm for block-wise nonsmooth nonconvex-linear minimax problems and its corresponding iteration complexity is $${\mathcal {O}}\left( K^{\frac{3}{2}} \varepsilon ^{-3} \right) $$ O K 3 2 ε - 3 and the number of function value estimation is bounded by $${\mathcal {O}}\left( d_{x}\varepsilon ^{-2} \right) $$ O d x ε - 2 per iteration. The numerical results indicate the efficiency of the proposed algorithms.

Keywords: Nonconvex-linear minimax problem; Zeroth-order algorithm; Alternating randomized gradient projection algorithm; Alternating randomized proximal gradient algorithm; Complexity analysis; Machine learning; 90C47; 90C26; 90C30 (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-022-01169-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:87:y:2023:i:2:d:10.1007_s10898-022-01169-5

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-022-01169-5

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().