A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization I: The Largest-Coordinate Strategy Keeps the Stochastic Chasing 0 Game within 2(c+R)log(4mk²/p)Research Paper
Cutting plane methods minimize a convex function, or find a point in a convex set, using only a separation oracle: a routine that, given a query point, either certifies it is good or returns a halfspace containing the target. Lee, Sidford and Wong (arXiv:1508.04874, FOCS 2015) gave a cutting plane method for a convex set in inside a box of…