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 965kB |
Official URL: http://proceedings.mlr.press/v130/anagnostidis21a/anagnostidis21a.pdf
Abstract
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: | |
Statistics: | download |
Deposited On: | 19 Apr 2021 11:46 |
Repository Staff Only: item control page