Randomized First-Order Methods for Saddle Point Optimization

By Cong D. Dang, Guanghui Lan. 2014

45 citations recorded by the source corpus.

In this paper, we present novel randomized algorithms for solving saddle point problems whose dual feasible region is given by the direct product of many convex sets. Our algorithms can achieve anO(1=N) andO(1=N 2 ) rate of convergence, respectively, for general bilinear saddle point and smooth bilinear saddle point problems based on a new prima-dual termination criterion, and each iteration of these algorithms needs to solve only one randomly selected dual subproblem. Moreover, these algorithms do not require strongly convex assumptions on the objective function and/or the incorporation of a strongly convex perturbation term. They do not necessarily require the primal or dual feasible regions to be bounded or the estimation of the distance from the initial point to the set of optimal solutions to be available either. We show that when applied to linearly constrained problems, RPDs are equivalent to certain randomized variants of the alternating direction method of multipliers (ADMM), while a direct extension of ADMM does not necessarily converge when the number of blocks exceeds two.

Citations in the corpus

• Stochastic Primal-Dual Methods and Sample Complexity of Reinforcement Learning (2016, neutral): “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.”
• Communication-efficient algorithms for decentralized and stochastic optimization (2017, neutral): “Recently, Chen, Lan and Ouyang [12] incorporated Bregman distance into the primal-dual method together with an acceleration step.”
• Katyusha: the first direct acceleration of stochastic gradient methods (2016, neutral): “However, we refrain from doing so in our experiments in order to have a strong comparison: by fixing τ 2 = 1 / 2 and thus without increasing parameter tuning difficulties, Katyusha can already beat most of the state-of-the-arts.”
• Randomized Linear Programming Solves the Discounted Markov Decision Problem In Nearly-Linear Running Time (2017, unknown): “Two later works [11] [9] studied optimal rate of convergence for strongly convex-concave saddle point problems under a stochastic first-order oracle.”
• Stabilizing Adversarial Nets With Prediction Methods (2017, unknown): “Stochastic methods for convex 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…”
• An online primal-dual method for discounted Markov decision processes (2016, unknown): “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.”