Projection-Free Methods for Solving Nonconvex-Concave Saddle Point Problems

arXiv2306.11944MaRDI QIDQ6440931FDOQ6440931

Authors: Morteza Boroun, Erfan Yazdandoost Hamedani, Afrooz Jalilzadeh 

Publication date: 20 June 2023

Abstract: In this paper, we investigate a class of constrained saddle point (SP) problems where the objective function is nonconvex-concave and smooth. This class of problems has wide applicability in machine learning, including robust multi-class classification and dictionary learning. Several projection-based primal-dual methods have been developed for tackling this problem, however, the availability of methods with projection-free oracles remains limited. To address this gap, we propose efficient single-loop projection-free methods reliant on first-order information. In particular, using regularization and nested approximation techniques we propose a primal-dual conditional gradient method that solely employs linear minimization oracles to handle constraints. Assuming that the constraint set in the maximization is strongly convex our method achieves an $epsilon$-stationary solution within $mathcalO(epsilo{n}^{-6})$ iterations. When the projection onto the constraint set of maximization is easy to compute, we propose a one-sided projection-free method that achieves an $epsilon$-stationary solution within $mathcalO(epsilo{n}^{-4})$ iterations. Moreover, we present improved iteration complexities of our methods under a strong concavity assumption. To the best of our knowledge, our proposed algorithms are among the first projection-free methods with convergence guarantees for solving nonconvex-concave SP problems.

This page was built for publication: Projection-Free Methods for Solving Nonconvex-Concave Saddle Point Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6440931)