Randomized First-Order Methods for Saddle Point Optimization

Abstract

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 an $\mathcal{O}(1/N)$ and $\mathcal{O}(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.

References in corpus (1)

• Stochastic Dual Coordinate Ascent with Alternating Direction Multiplier Method

Cited by in corpus (9)

• Incremental Aggregated Proximal and Augmented Lagrangian Algorithms
• Optimal Epoch Stochastic Gradient Descent Ascent Methods for Min-Max Optimization
• Randomized Linear Programming Solves the Discounted Markov Decision Problem In Nearly-Linear (Sometimes Sublinear) Running Time
• Randomized Primal-Dual Proximal Block Coordinate Updates
• Fast and Simple Optimization for Poisson Likelihood Models
• Accelerated first-order primal-dual proximal methods for linearly constrained composite convex programming
• Hybrid Jacobian and Gauss-Seidel proximal block coordinate update methods for linearly constrained convex programming
• Variance Reduction via Primal-Dual Accelerated Dual Averaging for Nonsmooth Convex Finite-Sums
• Accelerated Primal-Dual Proximal Block Coordinate Updating Methods for Constrained Convex Optimization