Cutting plane methods can be extended into nonconvex optimization

We show that it is possible to obtain an $O({ϵ}^{-4\mathrm{/}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\mathrm{/}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).