Cutting plane methods can be extended into nonconvex optimization


Oliver Hinder ;
Proceedings of the 31st Conference On Learning Theory, PMLR 75:1451-1454, 2018.


We show that it is possible to obtain an $O(\epsilon^{-4/3})$ runtime — including computational cost — for finding $\epsilon$-stationary points of nonconvex functions using cutting plane methods. This improves on the best known epsilon dependence achieved by cubic regularized Newton of $O(\epsilon^{-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).

Related Material