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

By Yin Tat Lee, Aaron Sidford, Sam Chiu-wai Wong. IEEE Annual Symposium on Foundations of Computer Science, 2015

327 citations recorded by the source corpus.

In this paper 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 ⊂ Rⁿ that is contained in a box of radius R we show how to either compute a point in K or prove that K does not contain a ball of radius ϵ using an expected O(n log(nR/ϵ)) evaluations of the oracle and additional time O(n³ log^O(1)(nR/ϵ)). This matches the oracle complexity and improves upon the O(n^ω+1 log(nR/ϵ)) additional time of the previous fastest algorithm achieved over 25 years ago by Vaidya [91] for the current value of the matrix multiplication constant w <; 2.373 [98], [36] when R/ϵ = O(poly(n)). Using a mix of standard reductions and new techniques we show how our algorithm can be used to improve the running time for solving classic problems in continuous and combinatorial optimization. In particular we provide the following running time improvements: · Submodular Function Minimization: n is the size of the ground set, M is the maximum absolute value of function values and EO is the time for function evaluation. Our weakly and strongly polynomial time algorithms have a running time of O(n² log nM · EO + n³ log^O(1) nM) and O(n³ log² n · EO + n⁴ log^O(1) n), improving upon the previous best of O((n⁴ · EO + n⁵)logM) and O(n⁵ · EO + n⁶) respectively. · Submodular Flow: n = |V|, m = |E|, C is the maximum edge cost in absolute value and U is maximum edge capacity in absolute value. We obtain a faster weakly polynomial running time of O(n² log nCU · EO + n³ logO(1) nCU), improving upon the previous best of O(mn⁵ log nU · EO) and O (n⁴h min {log C, log U}) from 15 years ago by a factor of Õ(n⁴). We also achieve faster strongly polynomial time algorithms as a consequence of our result on submodular minimization. · Matroid Intersection: n is the size of the ground set, r is the maximum size of independent sets, M is the maximum absolute value of element weight, T_rank and T_ind are the time for each rank and independence oracle query. We obtain a running time of O((nr log² nT_rank+n³ log^O(1) n) log nM) and O((n² log nT_ind+n³ log^O(1) n) log nM), 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. · Semidefinite Programming: n is the number of constraints, m is the number of dimensions and S is the total number of non-zeros in the constraint matrices. We obtain a running time of O(n(n² + m^ω + S)), improving upon the previous best of Õ(n(n^ω + m^ω + S)) for the regime S is small.

Subfields: Computational Theory and Mathematics, Computer Graphics and Computer-Aided Design, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/0d32773b665284d1eb22eeea462a5cefaa146ea1

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

1. Dorsa Sadigh
2. Elad Hazan
3. Ashish Kapoor
4. Jinwoo Shin
5. David P. Woodruff
6. Massimiliano Pontil
7. Sébastien Bubeck
8. Haim Avron

In Computer Graphics and Computer-Aided Design

1. Jinwoo Shin
2. David P. Woodruff
3. Sébastien Bubeck
4. Haim Avron
5. Elad Hazan

In Computer Networks and Communications

1. Carlo Ciliberto
2. Massimiliano Pontil
3. Sébastien Bubeck
4. Elad Hazan
5. Naman Agarwal
6. Jinwoo Shin
7. David P. Woodruff
8. Dorsa Sadigh

Citations in the corpus

• Challenges and opportunities in quantum optimization (2023, unknown): “, in which ω ∈[2,2.373) is the unknown optimal matrix exponent for multiplication 97 .”
• Lower Bounds for Higher-Order Convex Optimization (2017, background): “, 2012), cutting plane (Vaidya, 1989; Lee et al., 2015) and random-walk (Bertsimas and Vempala, 2004; Kalai and Vempala, 2006; Lovász and Vempala, 2006) based methods.”
• Stochastic Chebyshev Gradient Descent for Spectral Optimization (2018, background): “We remark that similar ideas of sampling unbiased polynomials have been studied in the literature, but for different setups [5, 17, 31, 26], and none of which are suitable for use in our setup.”
• Convex Optimization: Algorithms and Complexity (2014, background): “In fact the computational complexity can even be improved further, and the recent breakthrough Lee et al. [2015] shows that it can essentially (up to logarithmic factors) be brought down to O(n3).”
• Learning Two Layer Rectified Neural Networks in Polynomial Time (2018, background): “ to the above problem is unique and equal to U∗f(V∗X). It remains to show that the above optimization problem can be solved in polynomial time. Note, the objective function is convex. As mentioned in [LSW15], we can then run an interior point algorithm and it is well known that in order to achieve a”
• Safe Control under Uncertainty with Probabilistic Signal Temporal Logic (2016, background): “as an SDP, which is cubic in the number of constraints [27].”
• Quantum machine learning: a classical perspective (2017, background): “The best known classical SDP solvers [107] run in time O(m(m2 + n + mns)logO(1)(mnR/ )), where is an approximation parameter, ω ∈ [2, 2.”