An improved cutting plane method for convex optimization, convex-concave games, and its applications

Given a separation oracle for a convex set K ⊂ R n that is contained in a box of radius R, the goal is to either compute a point in K or prove that K does not contain a ball of radius . We propose a new cutting plane algorithm that uses an optimal O(n log(κ)) evaluations of the oracle and an additional O(n 2 ) time per evaluation, where κ = nR/ . • This improves upon Vaidya's O(SO • n log(κ) + n ω+1 log(κ)) time algorithm [Vaidya, FOCS 1989a] in terms of polynomial dependence on n, where ω < 2.373 is the exponent of matrix multiplication and SO is the time for oracle evaluation. and Wong, FOCS 2015] in terms of dependence on κ. For many important applications in economics, κ = Ω(exp(n)) and this leads to a significant difference between log(κ) and poly(log(κ)). We also provide evidence that the n 2 time per evaluation cannot be improved and thus our running time is optimal. A bottleneck of previous cutting plane methods is to compute leverage scores, a measure of the relative importance of past constraints. Our result is achieved by a novel multi-layered data structure for leverage score maintenance, which is a sophisticated combination of diverse techniques such as random projection, batched low-rank update, inverse maintenance, polynomial interpolation, and fast rectangular matrix multiplication. Interestingly, our method requires a combination of different fast rectangular matrix multiplication algorithms. Our algorithm not only works for the classical convex optimization setting, but also generalizes to convex-concave games. We apply our algorithm to improve the runtimes of many interesting problems, e.g., Linear Arrow-Debreu Markets, Fisher Markets, and Walrasian equilibrium. * A preliminary version of this paper appears in Proceedings of the 52nd ACM Symposium on Theory of Computing (STOC 2020). The authors would like to express their sincere gratitude to matrix multiplicationer Josh Alman and Jeroen Zuiddam for their patient and answers of our exponential number of questions about fast matrix multiplication.