2020/07/27 by Radu Ioan Boţ, Boţ, Radu Ioan, Axel Böhm +1 · 4 citations
Computer Science · Engineering · Mathematics · #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2007.13605
openalex publication_date 2020/07/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Minimax problems of the form minx maxy Ψ(x,y) have attracted increased interest largely due to advances in machine learning, in particular generative adversarial networks. These are typically trained using variants of stochastic gradient descent for the two players. Although convex-concave problems are well understood with many efficient solution methods to choose from, theoretical guarantees outside of this setting are sometimes lacking even for the simplest algorithms. In particular, this is the case for alternating gradient descent ascent, where the two agents take turns updating their strategies. To partially close this gap in the literature we prove a novel global convergence rate for the stochastic version of this method for finding a critical point of g(⋅) := maxy Ψ(⋅,y) in a setting which is not convex-concave.