Cutting plane methods can be extended into nonconvex optimization

05/22/2018

∙

by   Oliver Hinder, et al.

∙

0

∙

share

We show that it is possible to obtain an O(ϵ^-4/3) runtime --- including computational cost --- for finding ϵ-stationary points of 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)nesterov2006cubic. Our techniques utilize the convex until proven guilty principle proposed by Carmon, Duchi, Hinder, and Sidford (2017)carmon2017convex.