Stochastic Variance Reduction Methods for Saddle-Point Problems

By Balamurugan Palaniappan, Francis R. Bach. 2016

225 citations recorded by the source corpus.

We consider convex-concave saddle-point problems where the objective functions may be split in many components, and extend recent stochastic variance reduction methods (such as SVRG or SAGA) to provide the first large-scale linearly convergent algorithms for this class of problems which is common in machine learning. While the algorithmic extension is straightforward, it comes with challenges and opportunities: (a) the convex minimization analysis does not apply and we use the notion of monotone operators to prove convergence, showing in particular that the same algorithm applies to a larger class of problems, such as variational inequalities, (b) there are two notions of splits, in terms of functions, or in terms of partial derivatives, (c) the split does need to be done with convex-concave terms, (d) non-uniform sampling is key to an efficient algorithm, both in theory and practice, and (e) these incremental algorithms can be easily accelerated using a simple extension of the "catalyst" framework, leading to an algorithm which is always superior to accelerated batch algorithms.

Subfields: Artificial Intelligence, Statistics and Probability, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

In Optimization & Training

Citations in the corpus

Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity (2021, methodology): “, 2009] or its variance reduced version [Balamurugan and Bach, 2016], that we call stochastic gradient descent-ascent (SGDA) in this paper.”
Stochastic Hamiltonian Gradient Methods for Smooth Games (2020, background): “It is only very recently that last-iterate convergence guarantees over a non-compact domain appeared in literature for the stochastic problem (Palaniappan & Bach, 2016; Chavdarova et al., 2019; Hsieh et al., 2019; Mishchenko et al., 2020) under the assumption of strong monotonicity.”
Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates (2019, methodology): “For strongly-monotone operators, the convergence can be improved to obtain a linear rate by using variance-reduction methods [63, 16] exploiting the ﬁnite-sum structure in F .”
Reducing Noise in GAN Training with Variance Reduced Extragradient (2019, methodology): “This strategy has been first introduced for variance reduced methods by Xiao and Zhang (2014) for SVRG and has been discussed for saddle point optimization by Palaniappan and Bach (2016). The “noise dataset” in a GAN is not finite though; see § D.”
A Variational Inequality Perspective on Generative Adversarial Networks (2018, methodology): “We study a variant of extragradient that we call extrapolation from the past originally introduced by Popov (1980). It only requires one gradient computation per update compared to extrapolation, which needs to compute the gradient twice.”
On the Ineffectiveness of Variance Reduced Optimization for Deep Learning (2018, background): “, 2016] as well as saddle point problems [Balamurugan and Bach, 2016].”
Stochastic Variance Reduction Methods for Policy Evaluation (2017, methodology): “…in the policy evaluation problem, the strong concavity with respect to the dual variable w comes from a weighted quadratic norm (1 / 2) (cid:107) w (cid:98) C , which does not admit an efﬁcient proximal mapping as required by the proximal versions of SVRG and SAGA in Balamurugan & Bach (2016).”
A Variational Inequality Perspective on Generative Adversarial Nets (2018, methodology): “A linearly convergent variance reduced version of the stochastic gradient method has been proposed by Palaniappan and Bach (2016) for strongly monotone variational inequalities.”
AUC Maximization in the Era of Big Data and AI: A Survey (2022, methodology): “It is notable that a similar min-max formulation for AUC maximization was also independently examined in [134] for the oline setting.”
Accelerating Smooth Games by Manipulating Spectral Shapes (2020, methodology): “ing a richer, more complex set of dynamics (Mescheder et al., 2017; Balduzzi et al., 2018). Some old papers (Korpelevich, 1976; Tseng, 1995) and many recent ones (Nemirovski, 2004; Chen et al., 2014; Palaniappan and Bach, 2016; Mescheder et al., 2017; Gidel et al., 2019a,b; Daskalakis et al., 2018; ”
Linear Lower Bounds and Conditioning of Differentiable Games (2019, methodology): “Some commonly used deﬁni-tions, like the one used in Chambolle and Pock (2011); Palaniappan and Bach (2016), are undeﬁned for bilinear problems, which lack strong convexity and strong concavity in the variables.”
Stabilizing Adversarial Nets With Prediction Methods (2017, unknown): “For general saddle point problems, “doubly” stochastic gradient descent methods are discussed in Nemirovski et al. (2009),Palaniappan & Bach (2016), in Figure 2: A schematic depiction of the prediction method.”
Convergent Tree-Backup and Retrace with Function Approximation (2017, methodology): “In particular, the stochastic extra-gradient method or proximal methods (Balamurugan and Bach, 2016) seem to be promising future directions.”
Variance Reduction for Matrix Games (2019, methodology): “We note that while it naturally arises from our variance requirements, our gradient estimator appears to be fundamentally different from those used in known variance-reduced algorithms [32, 38, 4, 25].”
Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems (2020, methodology): “However, when it comes to the minimax problems, there are limited results, except under convex-concave setting [Palaniappan and Bach, 2016, Du and Hu, 2019].”
Solving Weakly-Convex-Weakly-Concave Saddle-Point Problems as Successive Strongly Monotone Variational Inequalities (2018, methodology): “Such a complexity can be also improved to O (( nρ 2 + Lρ ) /ǫ 2 ) by using the acceleration technique [57].”
Dualize, Split, Randomize: Fast Nonsmooth Optimization Algorithms (2020, background): “For instance, [27, 28] obtain fast convergence results by leveraging variance reduction, when the saddle-point problem is strongly convex-concave.”