A primal-dual smoothing gap reduction framework for strongly convex-generally concave saddle point problems
Le Thi Khanh Hien, Renbo Zhao, William B. Haskell · arXiv (Cornell University) · 2017
In this paper, we propose a new approach for finding a saddle point of a function $\mathcal{L}(x,\lambda)$ which is strongly convex in $x$ and generally concave in $\lambda$. We prove that, in the deterministic setting, to obtain an $\varepsilon$-optimal solution, this class of algorithms achieves the convergence rate $O\left(1/{\sqrt{\varepsilon}}\right)$. In the stochastic setting, where we utilize fast first order randomized algorithms to solve the sub-problems of our framework, we prove that this class of algorithms preserves the convergence rate $O\left(1/{\sqrt{\varepsilon}}\right)$ with high probability. We then apply our general algorithm to a large-scale convex constrained optimization problem, where the objective function is strongly convex and it consists of a large number of component functions or the number of convex constraints is prodigious. We establish the overall iteration complexity $O\left(1/{\sqrt{\varepsilon}}\right)$ for the optimality gap and constraint violation.