# Cutting plane methods can be extended into nonconvex optimization

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 May 2018.

## Built on by (most cited first, 2 of 2)

- [Multi-objective Optimization by Learning Space Partitions](https://mlsanity.com/paper/2110.03173/) (2021)
- [Improved Complexity for Smooth Nonconvex Optimization: A Two-Level Online Learning Approach with Quasi-Newton Methods](https://mlsanity.com/paper/2412.02175/) (2024)

## Abstract (arXiv)

We show that it is possible to obtain an O(ε-4/3) expected runtime --- including computational cost --- for finding ε-stationary points of smooth nonconvex functions using cutting plane methods. This improves on the best-known epsilon dependence achieved by cubic regularized Newton of O(ε-3/2) as proved by Nesterov and Polyak (2006). Our techniques utilize the convex until proven guilty principle proposed by Carmon, Duchi, Hinder, and Sidford (2017).