Optimal Primal-Dual Methods for a Class of Saddle Point Problems

By Yunmei Chen, Guanghui Lan, Yuyuan Ouyang. 2013

280 citations recorded by the source corpus.

We present a novel accelerated primal-dual (APD) method for solving a class of deterministic and stochastic saddle point problems (SPPs). The basic idea of this algorithm is to incorporate a multistep acceleration scheme into the primal-dual method without smoothing the objective function. For deterministic SPP, the APD method achieves the same optimal rate of convergence as Nesterov's smoothing technique. Our stochastic APD method exhibits an optimal rate of convergence for stochastic SPP not only in terms of its dependence on the number of the iteration, but also on a variety of problem parameters. To the best of our knowledge, this is the first time that such an optimal algorithm has been developed for stochastic SPP in the literature. Furthermore, for both deterministic and stochastic SPP, the developed APD algorithms can deal with the situation when the feasible region is unbounded, as long as a saddle point exists. In the unbounded case, we incorporate the modified termination criterion introduced b...

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis

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

1. Lihong Li
2. Sergey Levine
3. Bo Dai
4. Ofir Nachum
5. Niao He
6. Yoshua Bengio
7. Doina Precup
8. Le Song

In Computational Mechanics

1. Wotao Yin
2. Thomas Pock
3. Ji Liu
4. Damek Davis
5. Ming Yan
6. Antonin Chambolle
7. Niao He
8. Aryan Mokhtari

In Numerical Analysis

1. Thomas Pock
2. Antonin Chambolle
3. Wotao Yin
4. Niao He
5. Aryan Mokhtari
6. Ji Liu
7. Sridhar Mahadevan
8. Bo Liu

Citations in the corpus

• Boosting the Actor with Dual Critic (2017, background): “To solve the dual problem in (6), a straightforward idea is to apply stochastic mirror prox (Nemirovski et al., 2009) or stochastic primal-dual algorithm (Chen et al., 2014) to address the saddle point problem in (6).”
• Stochastic Primal-Dual Methods and Sample Complexity of Reinforcement Learning (2016, background): “Recent works (Dang and Lan, 2014; Chen et al., 2014) studied stochastic first-order methods for a class of general stochastic convex-concave saddle point problems and obtained optimal and near-optimal convergence rates.”
• Finite-Sample Analysis of Proximal Gradient TD Algorithms (2015, methodology): “SMP is able to accelerate the convergence rate of our gradient TD method to: and stochastic accelerated primal-dual (SAPD) method [Chen et al. , 2013] which can reach the optimal convergence rate in (36).”
• Scalable Learning of Non-Decomposable Objectives (2016, unknown): “Importantly, the surrogate objectives we derive can be optimized us-ing standard stochastic (mini-batch) gradient methods for saddle-point problems with favorable convergence rates [6].”
• Convergent Tree-Backup and Retrace with Function Approximation (2017, background): “Existing stochastic saddle-point problem results: Chen et al. (2014) provides a comprehensive review of stochastic saddle-point problem.”
• A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach (2019, background): “Papers including Nemirovski et al. (2009); Juditsky et al. (2011); Chen et al. (2014) solve this problem in the case where the objective function is convex in x and concave in y .”
• Convergence Rate Analysis of Several Splitting Schemes (2014, background): “(As an exception, lower complexity results and optimal algorithms are known for the primal-dual case [13].”
• Algorithms for stochastic optimization with expectation constraints (2016, methodology): “However these methods would require either the estimation of the optimal dual variables or iterations performed on the dual space (see [7], [23] and [20]).”
• Randomized First-Order Methods for Saddle Point Optimization (2014, unknown): “.1), i.e., a point ˆz ∈ Z such that E[Q0(ˆz,z)] ≤ ǫ for any z ∈ Z, can be bounded by O(p3/2kAk2ΩXΩY /ǫ). This bound is not improvable in terms of its dependence on ǫ for a given p (see discussions in [9]). It should be noted, however, that the number of dual subprobems to be solved in the RPD algori”
• An introduction to continuous optimization for imaging (2016, methodology): “There have also been many attempts to learn optimal analysis operators from data; see for example Protter, Yavneh and Elad (2010), Peyré, Fadili and Starck (2010), Chen et al. (2014b) and Hawe, Kleinsteuber and Diepold (2013).”
• An online primal-dual method for discounted Markov decision processes (2016, methodology): “In particular, our stochastic primal-dual algorithm can be viewed as SA applied to the stochastic saddle point problems; see recent works [8], [10], [17] for convergence rate benchmarks.”
• Proximal Reinforcement Learning: A New Theory of Sequential Decision Making in Primal-Dual Spaces (2014, methodology): “Using the bounds proved in [145, 109, 108], the optimal convergence rate of stochastic saddle-point problem is O(F N2 + LK N + σ √ N ).”
• Stabilizing Adversarial Nets With Prediction Methods (2017, background): “…saddle-point problems can be roughly divided into two categories: stochastic coordinate descent (Dang & Lan, 2014; Lan & Zhou, 2015; Zhang & Lin, 2015; Zhu & Storkey, 2015; 2016; Wang & Xiao, 2017; Shibagaki & Takeuchi, 2017) and stochastic gradient descent (Chen et al., 2014; Qiao et al., 2016).”
• On the ergodic convergence rates of a first-order primal–dual algorithm (2016, background): “In the Euclidean setting and when g = 0, a better algorithm (in fact, optimal, see [21, 23]) is proposed in [7], which yields a rate of order O(Lf/N 2 + L/N).”