An Efficient Stochastic Approximation Algorithm for Stochastic Saddle Point Problems

By Arkadi Nemirovski, Reuven Y. Rubinstein. 2005

21 citations recorded by the source corpus.

Subfields: Computational Mechanics, Management Science and Operations Research, Statistics and Probability

How researchers see this paper

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

In Computational Mechanics

1. Amrit Singh Bedi
2. Mengdi Wang
3. Zeeshan Akhtar
4. Ketan Rajawat
5. Yichen Chen

In Management Science and Operations Research

1. Mengdi Wang
2. Yichen Chen
3. Zeeshan Akhtar
4. Ketan Rajawat
5. Amrit Singh Bedi
6. Donghwan Lee
7. Lihong Li
8. Niao He

In Statistics and Probability

1. Mengdi Wang
2. Zeeshan Akhtar
3. Ketan Rajawat
4. Amrit Singh Bedi
5. Yichen Chen

Citations in the corpus

• Stochastic Primal-Dual Methods and Sample Complexity of Reinforcement Learning (2016, methodology): “In particular, our algorithm can be viewed as a stochastic approximation method for stochastic saddle point problems, which was first studied by Nemirovski and Rubinstein (2005) without rate of convergence analysis.”
• Primal-Dual π Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problems (2017, methodology): “Our proposed algorithm and analysis was partly motivated by the stochastic mirror-prox methods for solving convex-concave saddle point problems [20] and variational inequalities [13].”
• Randomized Linear Programming Solves the Discounted Markov Decision Problem In Nearly-Linear (Sometimes Sublinear) Running Time (2017, methodology): “The general primal-dual convergence analysis given by [25, 17] requires E [ ‖∂μL(v, μ) + ω‖(2)∗ | Ft ] < σ(2) for some appropriate norm ‖ · ‖∗ and a finite constant σ, where Ft denotes the collection of random variables up to the t-th iteration.”
• 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.”
• Conservative Stochastic Optimization With Expectation Constraints (2020, background): “The compactness assumption on the domain of λ is a key requirement in classical stochastic saddle point algorithms [33].”