mlsanityData to 7 Oct 2026

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

arXiv 1508.04874 ↗First posted 20 Aug 2015cs.DS cs.DM cs.NAcited by 50

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 8; 2022: 7; 2023: 12; 2024: 11; 2025: 7; 2026: 5.

50 papers.

Sort:

  1. 2021Training Quantum Embedding Kernels on Near-Term Quantum Computerscited by 69
  2. 2021Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Timecited by 62
  3. 2022Submodularity In Machine Learning and Artificial Intelligencecited by 37
  4. 2023A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Timecited by 30
  5. 2021Efficient Projection-Free Online Convex Optimization with Membership Oraclecited by 29
  6. 2022Discrete-Convex-Analysis-Based Framework for Warm-Starting Algorithms with Predictionscited by 16
  7. 2023A General Algorithm for Solving Rank-one Matrix Sensingcited by 15
  8. 2022Efficient Convex Optimization Requires Superlinear Memorycited by 14
  9. 2021An Introduction to Johnson-Lindenstrauss Transformscited by 10
  10. 2022Exploiting the Curvature of Feasible Sets for Faster Projection-Free Online Learningcited by 10
  11. 2021Minimax Optimization with Smooth Algorithmic Adversariescited by 8
  12. 2023A Survey on the Densest Subgraph Problem and Its Variantscited by 8
38 more
  1. 2023Submodular Minimax Optimization: Finding Effective Setscited by 7
  2. 2023Feature Adaptation for Sparse Linear Regressioncited by 6
  3. 2023Quadratic Memory is Necessary for Optimal Query Complexity in Convex Optimization: Center-of-Mass is Pareto-Optimalcited by 5
  4. 2024An invitation to the sample complexity of quantum hypothesis testingcited by 5
  5. 2023Agnostic proper learning of monotone functions: beyond the black-box correction barriercited by 4
  6. 2023Accelerated Quasi-Newton Proximal Extragradient: Faster Rate for Smooth Convex Optimizationcited by 4
  7. 2023Memory-Query Tradeoffs for Randomized Convex Optimizationcited by 4
  8. 2024Computing Optimal Regularizers for Online Linear Optimizationcited by 4
  9. 2025The Structural Complexity of Matrix-Vector Multiplicationcited by 4
  10. 2021Decomposable Submodular Function Minimization via Maximum Flowcited by 3
  11. 2023Rethinking Warm-Starts with Predictions: Learning Predictions Close to Sets of Optimal Solutions for Faster L-/L^natural-Convex Function Minimizationcited by 3
  12. 2023Faster Discrete Convex Function Minimization with Predictions: The M-Convex Casecited by 3
  13. 2023Memory-Constrained Algorithms for Convex Optimization via Recursive Cutting-Planescited by 3
  14. 2024Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimizationcited by 3
  15. 2024Private Geometric Mediancited by 3
  16. 2025Quantum Algorithms for Bandits with Knapsacks with Improved Regret and Time Complexitiescited by 2
  17. 2025A Simple, Optimal and Efficient Algorithm for Online Exp-Concave Optimizationcited by 2
  18. 2026Efficient Online Inverse Optimization with O(d) Regretcited by 2
  19. 2021A Hybrid Quantum-Classical Hamiltonian Learning Algorithmcited by 1
  20. 2022Polynomial-time Sparse Measure Recovery: From Mean Field Theory to Algorithm Designcited by 1
  21. 2022Online Nonsubmodular Minimization with Delayed Costs: From Full Information to Bandit Feedbackcited by 1
  22. 2024Quantum Speedup for Spectral Approximation of Kronecker Productscited by 1
  23. 2024Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problemscited by 1
  24. 2024Binary Hypothesis Testing for Softmax Models and Leverage Score Modelscited by 1
  25. 2024Solving 0-1 Integer Programs with Unknown Knapsack Constraints Using Membership Oraclescited by 1
  26. 2024Active Learning of Deep Neural Networks via Gradient-Free Cutting Planescited by 1
  27. 2025Characterizing the Accuracy-Communication-Privacy Trade-off in Distributed Stochastic Convex Optimizationcited by 1
  28. 2025Differentially Private Bilevel Optimization: Efficient Algorithms with Near-Optimal Ratescited by 1
  29. 2025Differentially Private Synthetic Graphs Preserving Triangle-Motif Cutscited by 1
  30. 2021Identifiability of AMP chain graph modelscited by 0
  31. 2022Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient Oracle Complexitycited by 0
  32. 2024Logarithmic Regret for Unconstrained Submodular Maximization Stochastic Banditcited by 0
  33. 2024Reconstructing Deep Neural Networks: Unleashing the Optimization Potential of Natural Gradient Descentcited by 0
  34. 2025On Quantum Perceptron Learning via Quantum Searchcited by 0
  35. 2026Matroid Algorithms Under Size-Sensitive Independence Oraclescited by 0
  36. 2026Beyond Averaging in John Ellipsoid Approximation: High-Accuracy Algorithms in the Leverage-Score Modelcited by 0
  37. 2026Fast, Parallel, Query-Efficient Binary Classificationcited by 0
  38. 2026Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memorycited by 0