Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods

We design accelerated algorithms with improved rates for several fundamental classes of optimization problems. Our algorithms all build upon techniques related to the analysis of primal-dual extragradient methods via relative Lipschitzness proposed recently by [CST21]. (1) Separable minimax optimization. We study separable minimax optimization problems minx maxy f(x) - g(y) + h(x, y), where f and g have smoothness and strong convexity parameters (Lx, μx), (Ly, μy), and h is convex-concave with a (Lambdaxx, Lambdaxy, Lambdayy)-blockwise operator norm bounded Hessian. We provide an algorithm with gradient query complexity tildeOleft(√fracLxμx + √fracLyμy + fracLambdaxxμx + fracLambdaxy√μxμy + fracLambdayyμyright). Notably, for convex-concave minimax problems with bilinear coupling (e.g. quadratics), where Lambdaxx = Lambdayy = 0, our rate matches a lower bound of [ZHZ19]. (2) Finite sum optimization. We study finite sum optimization problems minx frac1nsumi∈[n] fi(x), where each fi is Li-smooth and the overall problem is μ-strongly convex. We provide an algorithm with gradient query complexity tildeOleft(n + sumi∈[n] √fracLinμ right). Notably, when the smoothness bounds Lii∈[n] are non-uniform, our rate improves upon accelerated SVRG [LMH15, FGKS15] and Katyusha [All17] by up to a √n factor. (3) Minimax finite sums. We generalize our algorithms for minimax and finite sum optimization to solve a natural family of minimax finite sum optimization problems at an accelerated rate, encapsulating both above results up to a logarithmic factor.