Cutting plane methods can be extended into nonconvex optimization

2018/05/22 by Hinder, Oliver
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1805.08370

Abstract

We show that it is possible to obtain an O(ε^-4/3) expected runtime --- including computational cost --- for finding ε-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(ε^-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

• Progressive Bound Strengthening via Doubly Nonnegative Cutting Planes for Nonconvex Quadratic Programs
• Cutting plane methods with gradient-based heuristics
• An Inexact Regularized Newton Framework with a Worst-Case Iteration Complexity of O(ε^-3/2) for Nonconvex Optimization
• The Cutting Plane Method is Polynomial for Perfect Matchings
• An optimal variant of Kelley's cutting-plane method