OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Direct-Search for a Class of Stochastic Min-Max Problems

Anagnostidis, Sotirios-Konstantinos and Lucchi, Aurelien and Diouane, Youssef Direct-Search for a Class of Stochastic Min-Max Problems. (2021) In: The 24th International Conference on Artificial Intelligence and Statistics, 13 April 2021 - 15 April 2021 (A Virtual Conference, United States).

(Document in English)

PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: http://proceedings.mlr.press/v130/anagnostidis21a/anagnostidis21a.pdf


Recent applications in machine learning have renewed the interest of the community in min-max optimization problems. While gradient-based optimization methods are widely used to solve such problems, there are however many scenarios where these techniques are not well-suited, or even not applicable when the gradient is not accessible. We investigate the use of direct-search methods that belong to a class of derivative-free techniques that only access the objective function through an oracle. In this work, we design a novel algorithm in the context of min-max saddle point games where one sequentially updates the min and the max player. We prove convergence of this algorithm under mild assumptions, where the objective of the max-player satisfies the Polyak-Ł{}ojasiewicz (PL) condition, while the min-player is characterized by a nonconvex objective. Our method only assumes dynamically adjusted accurate estimates of the oracle with a fixed probability. To the best of our knowledge, our analysis is the first one to address the convergence of a direct-search method for min-max objectives in a stochastic setting.

Item Type:Conference or Workshop Item (Paper)
Additional Information:http://proceedings.mlr.press/v130/
Audience (conference):International conference proceedings
Uncontrolled Keywords:
Institution:Université de Toulouse > Institut Supérieur de l'Aéronautique et de l'Espace - ISAE-SUPAERO (FRANCE)
Other partners > Eidgenössische Technische Hochschule Zürich - ETHZ (SWITZERLAND)
Laboratory name:
Deposited On:19 Apr 2021 11:46

Repository Staff Only: item control page