Loading...
Please wait, while we are loading the content...
Similar Documents
Iteration Complexity of Randomized Primal-Dual Methods for Convex-Concave Saddle Point Problems
| Content Provider | Semantic Scholar |
|---|---|
| Author | Hamedani, Erfan Yazdandoost Jalilzadeh, Amin Aybat, Necdet Serhat Shanbhag, U. V. |
| Copyright Year | 2018 |
| Abstract | In this paper we propose a class of randomized primal-dual methods to contend with large-scale saddle point problems defined by a convex-concave function $\mathcal{L}(\mathbf{x},y)\triangleq\sum_{i=1}^m f_i(x_i)+\Phi(\mathbf{x},y)-h(y)$. We analyze the convergence rate of the proposed method under the settings of mere convexity and strong convexity in $\mathbf{x}$-variable. In particular, assuming $\nabla_y\Phi(\cdot,\cdot)$ is Lipschitz and $\nabla_\mathbf{x}\Phi(\cdot,y)$ is coordinate-wise Lipschitz for any fixed $y$, the ergodic sequence generated by the algorithm achieves the convergence rate of $\mathcal{O}(m/k)$ in a suitable error metric where $m$ denotes the number of coordinates for the primal variable. Furthermore, assuming that $\mathcal{L}(\cdot,y)$ is uniformly strongly convex for any $y$, and that $\Phi(\cdot,y)$ is linear in $y$, the scheme displays convergence rate of $\mathcal{O}(m/k^2)$. We implemented the proposed algorithmic framework to solve kernel matrix learning problem, and tested it against other state-of-the-art solvers. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://export.arxiv.org/pdf/1806.04118 |
| Alternate Webpage(s) | https://arxiv.org/pdf/1806.04118v2.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
