A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach.
Aryan Mokhtari, Asuman Ozdaglar, Sarath Pattathil
2020International Conference on Artificial Intelligence and Statistics83 citations
Abstract
In this paper we consider solving saddle point problems using two variants of Gradient Descent-Ascent algorithms, Extra-gradient (EG) and Optimistic Gradient Descent Ascent (OGDA) methods. We show that both of these algorithms admit a unified analysis as approximations of the classical proximal point method for solving saddle point problems. This viewpoint enables us to develop a new framework for analyzing EG and OGDA for bilinear and strongly convex-strongly concave settings. Moreover, we use the proximal point approximation interpretation to generalize the results for OGDA for a wide range of parameters.
Topics & Concepts
Saddle pointGradient descentPoint (geometry)Proximal Gradient MethodsSaddleGradient methodMathematical optimizationMathematicsApplied mathematicsBilinear interpolationRange (aeronautics)Regular polygonComputer scienceAlgorithmConvex optimizationGeometryArtificial intelligenceArtificial neural networkStatisticsComposite materialMaterials scienceAdvanced Optimization Algorithms ResearchSparse and Compressive Sensing TechniquesStochastic Gradient Optimization Techniques