Revisiting Area Convexity: Faster Box-Simplex Games and Spectrahedral Generalizations

arXiv2303.15627MaRDI QIDQ6431053FDOQ6431053

Kevin T. Tian, Arun Jambulapati

Publication date: 27 March 2023

Abstract: We investigate different aspects of area convexity [Sherman '17], a mysterious tool introduced to tackle optimization problems under the challenging $el{l}_{i}nfty$ geometry. We develop a deeper understanding of its relationship with more conventional analyses of extragradient methods [Nemirovski '04, Nesterov '07]. We also give improved solvers for the subproblems required by variants of the [Sherman '17] algorithm, designed through the lens of relative smoothness [Bauschke-Bolte-Teboulle '17, Lu-Freund-Nesterov '18]. Leveraging these new tools, we give a state-of-the-art first-order algorithm for solving box-simplex games (a primal-dual formulation of $el{l}_{i}nfty$ regression) in a $dimesn$ matrix with bounded rows, using $O(logdcdotepsilo{n}^{-1})$ matrix-vector queries. As a consequence, we obtain improved complexities for approximate maximum flow, optimal transport, min-mean-cycle, and other basic combinatorial optimization problems. We also develop a near-linear time algorithm for a matrix generalization of box-simplex games, capturing a family of problems closely related to semidefinite programs recently used as subroutines in robust statistics and numerical linear algebra.

This page was built for publication: Revisiting Area Convexity: Faster Box-Simplex Games and Spectrahedral Generalizations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6431053)