We develop stochastic first-order primal-dual algorithms to solve stochastic three-composite convex-concave saddle point problems. When the saddle function is non-strongly convex in the primal variable, we design an algorithm based on the PDHG framework, that achieves the state-of-the-art oracle complexity. Using this algorithm as subroutine, when the saddle function is strongly convex in the primal variable, we develop a novel stochastic restart scheme, whose oracle complexity is strictly better than any of the existing ones, even in the deterministic case.
Novel theoretical inroads on saddle-point problems involve moving beyond the convex-concave framework. Here we analyze the behavior of mirror descent (MD) in a class of non-monotone problems whose solutions coincide with those of a naturally associated variational inequality - a property which we call "coherence." We show that "vanilla" MD converges under a strict version of coherence (but not otherwise) and that this deficiency is mitigated by taking an "extra-gradient" step which leads to convergence in all coherent problems. We validate our analysis by numerical experiments in GANs.
joint work with Yuyuan Ouyang
There have been many works studying the upper complexity bounds of first-order methods for solving the convex-concave bilinear saddle-point problem (SPP). In this talk I will show the opposite direction by deriving lower complexity bounds for first-order methods for SPPs. For convex-concave SPP, I show that the lower complexity bound is $O(1/\epsilon)$ to obtain an $\epsilon$-solution, and is $O(1/\sqrt{\epsilon})$ under primal strong convexity. These established bounds are tight in terms of the dependence on $\epsilon$, and they imply the optimality of several existing first-order methods.