NeurIPS 2020

Acceleration with a Ball Optimization Oracle

Meta Review

This paper is concerned with optimization via a "ball optimization oracle", which returns the minimizer of a function restricted to an L2 ball of radius r around a query point x. The authors demonstrate an oracle complexity of roughly (R/r)^{2/3} when combined with a Monteiro-Svaiter acceleration scheme. The authors show that this oracle can be implemented on a variety of important machine learning problems. (Although, the authors acknowledge in the response that the algorithm is not immediately suitable for use.) The ideas in this paper are elegant and surprising, despite arising from a "deceptively simple" oracle. The reviewers were unanimously positive about this work, and everyone agrees it is an important theoretical contribution to the optimization community. I am delighted to recommend acceptance. Please address all of the reviewer comments. In particular, please revise the Broader Impact section to comport with the instructions in the Call for Papers.