A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization

This is wonderful news. One of the things I wonder is if this new approach will do better than some  greedy algorithms: A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization by Yin Tat Lee, Aaron Sidford, Sam Chiu-wai Wong

We improve upon the running time for finding a point in a convex set given a separation oracle. In particular, given a separation oracle for a convex set K⊂Rn contained in a box of radius R, we show how to either find a point in K or prove that K does not contain a ball of radius ϵ using an expected O(nlog(nR/ϵ)) oracle evaluations and additional time O(n3logO(1)(nR/ϵ)). This matches the oracle complexity and improves upon the O(nω+1log(nR/ϵ)) additional time of the previous fastest algorithm achieved over 25 years ago by Vaidya for the current matrix multiplication constant ω<2.373 when R/ϵ=nO(1).
Using a mix of standard reductions and new techniques, our algorithm yields improved runtimes for solving classic problems in continuous and combinatorial optimization:

• Submodular Minimization: Our weakly and strongly polynomial time algorithms have runtimes of O(n2lognM⋅EO+n3logO(1)nM) and O(n3log2n⋅EO+n4logO(1)n), improving upon the previous best of O((n4EO+n5)logM) and O(n5EO+n6).
• Matroid Intersection: Our runtimes are O((nrlog2nTrank+n3logO(1)n)lognM) and O((n2lognTind+n3logO(1)n)lognM), achieving the first quadratic bound on the query complexity for the independence and rank oracles. In the unweighted case, this is the first improvement since 1986 for independence oracle.
• Submodular Flow: Our runtime is O(n2lognCU⋅EO+n3logO(1)nCU), improving upon the previous bests from 15 years ago roughly by a factor of O(n4).
• Semidefinite Programming: Our runtime is O~(n(n2+mω+S)), improving upon the previous best of O~(n(nω+mω+S)) for the regime where the number of nonzeros S is small.

    Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.