f73b76ce8949fe29bf2a537cfa420e8f-Reviews.html

The paper considers optimization with a "mixed" oracle, which provides the algorithm access to the standard stochastic oracle as well as a small number of accesses to an exact oracle. In this setting, the authors give an algorithm that achieves a convergence rate of O(1/T) after O(T) calls to the stochastic oracle and O(log T) class to the exact oracle, improving on the known rates of O(1/sqrt(T)) after O(T) calls to the stochastic oracle and O(1/T) after O(T) calls to the exact oracle. Comments: The paper asks an interesting question, and provides an interesting answer to it. The paper has the potential to change the way many optimization problems are solved, and is certainly of interest to the NIPS community. The first sentence of the abstract: "It is well known that the optimal convergence rate for stochastic optimization of smooth functions is O(1/sqrt(T))".