An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications

Given a separation oracle for a convex set K subset ℝ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 (kappa)) evaluations of the oracle and an additional O(n2) time per evaluation, where kappa = nR/ε. bullet This improves upon Vaidya's O( SO · n log (kappa) + nω+1 log (kappa)) 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. bullet This improves upon Lee-Sidford-Wong's O( SO · n log (kappa) + n3 logO(1) (kappa)) time algorithm [Lee, Sidford and Wong, FOCS 2015] in terms of dependence on kappa. For many important applications in economics, kappa = Omega(exp(n)) and this leads to a significant difference between log(kappa) and poly(log (kappa)). We also provide evidence that the n2 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.