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

arXiv: https://arxiv.org/abs/1508.04874 · HTML: https://mlsanity.com/paper/1508.04874/

## Key facts

- Cited by 50 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Aug 2015.

## Built on by (most cited first, 30 of 50)

- [Training Quantum Embedding Kernels on Near-Term Quantum Computers](https://mlsanity.com/paper/2105.02276/) (2021)
- [Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time](https://mlsanity.com/paper/2112.07628/) (2021)
- [Submodularity In Machine Learning and Artificial Intelligence](https://mlsanity.com/paper/2202.00132/) (2022)
- [Efficient Projection-Free Online Convex Optimization with Membership Oracle](https://mlsanity.com/paper/2111.05818/) (2021)
- [A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Time](https://mlsanity.com/paper/2309.07418/) (2023)
- [Discrete-Convex-Analysis-Based Framework for Warm-Starting Algorithms with Predictions](https://mlsanity.com/paper/2205.09961/) (2022)
- [A General Algorithm for Solving Rank-one Matrix Sensing](https://mlsanity.com/paper/2303.12298/) (2023)
- [Efficient Convex Optimization Requires Superlinear Memory](https://mlsanity.com/paper/2203.15260/) (2022)
- [An Introduction to Johnson-Lindenstrauss Transforms](https://mlsanity.com/paper/2103.00564/) (2021)
- [Exploiting the Curvature of Feasible Sets for Faster Projection-Free Online Learning](https://mlsanity.com/paper/2205.11470/) (2022)
- [Minimax Optimization with Smooth Algorithmic Adversaries](https://mlsanity.com/paper/2106.01488/) (2021)
- [A Survey on the Densest Subgraph Problem and Its Variants](https://mlsanity.com/paper/2303.14467/) (2023)
- [Submodular Minimax Optimization: Finding Effective Sets](https://mlsanity.com/paper/2305.16903/) (2023)
- [Feature Adaptation for Sparse Linear Regression](https://mlsanity.com/paper/2305.16892/) (2023)
- [Quadratic Memory is Necessary for Optimal Query Complexity in Convex Optimization: Center-of-Mass is Pareto-Optimal](https://mlsanity.com/paper/2302.04963/) (2023)
- [An invitation to the sample complexity of quantum hypothesis testing](https://mlsanity.com/paper/2403.17868/) (2024)
- [Agnostic proper learning of monotone functions: beyond the black-box correction barrier](https://mlsanity.com/paper/2304.02700/) (2023)
- [Accelerated Quasi-Newton Proximal Extragradient: Faster Rate for Smooth Convex Optimization](https://mlsanity.com/paper/2306.02212/) (2023)
- [Memory-Query Tradeoffs for Randomized Convex Optimization](https://mlsanity.com/paper/2306.12534/) (2023)
- [Computing Optimal Regularizers for Online Linear Optimization](https://mlsanity.com/paper/2410.17336/) (2024)
- [The Structural Complexity of Matrix-Vector Multiplication](https://mlsanity.com/paper/2502.21240/) (2025)
- [Decomposable Submodular Function Minimization via Maximum Flow](https://mlsanity.com/paper/2103.03868/) (2021)
- [Rethinking Warm-Starts with Predictions: Learning Predictions Close to Sets of Optimal Solutions for Faster L-/L^natural-Convex Function Minimization](https://mlsanity.com/paper/2302.00928/) (2023)
- [Faster Discrete Convex Function Minimization with Predictions: The M-Convex Case](https://mlsanity.com/paper/2306.05865/) (2023)
- [Memory-Constrained Algorithms for Convex Optimization via Recursive Cutting-Planes](https://mlsanity.com/paper/2306.10096/) (2023)
- [Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimization](https://mlsanity.com/paper/2406.07373/) (2024)
- [Private Geometric Median](https://mlsanity.com/paper/2406.07407/) (2024)
- [A Simple, Optimal and Efficient Algorithm for Online Exp-Concave Optimization](https://mlsanity.com/paper/2512.23190/) (2025)
- [Efficient Online Inverse Optimization with O(d) Regret](https://mlsanity.com/paper/2609.13440/) (2026)
- [Quantum Algorithms for Bandits with Knapsacks with Improved Regret and Time Complexities](https://mlsanity.com/paper/2507.04438/) (2025)

## Abstract (arXiv)

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 Ksubset ℝn 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(n2log nM·EO+n3logO(1)nM) and O(n3log2 n·EO+n4logO(1)n), improving upon the previous best of O((n4EO+n5)log M) and O(n5EO+n6). Matroid Intersection: Our runtimes are O(nrTranklog nlog (nM) +n3logO(1)(nM)) and O(n2log (nM) Tind+n3 logO(1) (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. Submodular Flow: Our runtime is O(n2log nCU·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 tildeO(n(n2+mω+S)), improving upon the previous best of tildeO(n(nω+mω+S)) for the regime where the number of nonzeros S is small.