Cutting plane methods can be extended into nonconvex optimization

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

Abstract

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).

Cite this Paper

BibTeX
@InProceedings{pmlr-v75-hinder18a, title = {Cutting plane methods can be extended into nonconvex optimization}, author = {Hinder, Oliver}, booktitle = {Proceedings of the 31st Conference On Learning Theory}, pages = {1451--1454}, year = {2018}, editor = {Bubeck, Sébastien and Perchet, Vianney and Rigollet, Philippe}, volume = {75}, series = {Proceedings of Machine Learning Research}, month = {06--09 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v75/hinder18a/hinder18a.pdf}, url = {https://proceedings.mlr.press/v75/hinder18a.html}, abstract = {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). } }
Endnote
%0 Conference Paper %T Cutting plane methods can be extended into nonconvex optimization %A Oliver Hinder %B Proceedings of the 31st Conference On Learning Theory %C Proceedings of Machine Learning Research %D 2018 %E Sébastien Bubeck %E Vianney Perchet %E Philippe Rigollet %F pmlr-v75-hinder18a %I PMLR %P 1451--1454 %U https://proceedings.mlr.press/v75/hinder18a.html %V 75 %X 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).
APA
Hinder, O.. (2018). Cutting plane methods can be extended into nonconvex optimization. Proceedings of the 31st Conference On Learning Theory, in Proceedings of Machine Learning Research 75:1451-1454 Available from https://proceedings.mlr.press/v75/hinder18a.html.

Related Material