Cutting Plane Methods Can Be Extended into Nonconvex Optimization
Abstract
We show that it is possible to obtain an $O(\epsilon^{-4/3})$ expected runtime --- including computational cost --- for finding $\epsilon$-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(\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).
Cite
Text
Hinder. "Cutting Plane Methods Can Be Extended into Nonconvex Optimization." Annual Conference on Computational Learning Theory, 2018.Markdown
[Hinder. "Cutting Plane Methods Can Be Extended into Nonconvex Optimization." Annual Conference on Computational Learning Theory, 2018.](https://mlanthology.org/colt/2018/hinder2018colt-cutting/)BibTeX
@inproceedings{hinder2018colt-cutting,
title = {{Cutting Plane Methods Can Be Extended into Nonconvex Optimization}},
author = {Hinder, Oliver},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2018},
pages = {1451-1454},
url = {https://mlanthology.org/colt/2018/hinder2018colt-cutting/}
}