Review for NeurIPS paper: Acceleration with a Ball Optimization Oracle

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