First-Order Methods with Increasing Iterate Averaging for Solving Saddle-Point Problems

摘要: First-order methods are known to be among the fastest algorithms for solving large-scale convex-concave saddle-point problems. Algorithms that achieve a theoretical convergence rate on order of $1/T$ known, but these often rely uniformly averaging iterates in get guaranteed rate. In contrast, using last iterate has repeatedly been found perform better practice, with no guarantee this paper we propose schemes increasing weight recent iterates, which leads rate, while capturing practical performance iterate. We show Chambolle and Pock's primal-dual algorithm, mirror prox. present numerical results computing Nash equilibria matrix games, competitive Fisher markets, image denoising via total-variation minimization under $\ell_1$ norm. all cases find our lead much than uniform averaging, sometimes even