Cutting plane methods can be extended into nonconvex optimization

05/22/2018
by   Oliver Hinder, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset