Solving Non-Convex Non-Differentiable Min-Max Games Using Proximal Gradient Method

Babak Barazandeh; Meisam Razaviyayn

ICASSP 2020accepted0 citations

Solving Non-Convex Non-Differentiable Min-Max Games Using Proximal Gradient Method

Abstract

Min-max saddle point games appear in a wide range of applications in machine leaning and signal processing. Despite their wide applicability, theoretical studies are mostly limited to the special convex-concave structure. While some recent works generalized these results to special smooth non-convex cases, our understanding of nonsmooth scenarios is still limited. In this work, we study special form of non-smooth min-max games when the objective function is (strongly) convex with respect to one of the player's decision variable. We show that a simple multi-step proximal gradient descent-ascent algorithm converges to -first-order Nash equilibrium of the min-max game with the number of gradient evaluations being polynomial in 1/. Finally, we evaluate the performance of the proposed algorithm through adversarial attack on a LASSO estimator.

BibTeX

@inproceedings{icassp2020_solvingnonconvex,
  title = {Solving Non-Convex Non-Differentiable Min-Max Games Using Proximal Gradient Method},
  author = {Babak Barazandeh and Meisam Razaviyayn},
  booktitle = {ICASSP 2020},
  year = {2020}
}