Mixed Optimization for Smooth Functions
It is well known that the optimal convergence rate for stochastic optimization of smooth functions is O(1/ √ T ), which is same as stochastic optimization of Lipschitz continuous convex functions. This is in contrast to optimizing smooth functions using full gradients, which yields a convergence rate of O(1/T 2 ). In this work, we consider a new setup for optimizing smooth functions, termed as Mixed Optimization, which allows to access both a stochastic oracle and a full gradient oracle. Our goal is to significantly improve the convergence rate of stochastic optimization of smooth functions by having an additional small number of accesses to the full gradient oracle. We show that, with an O(ln T ) calls to the full gradient oracle and an O(T ) calls to the stochastic oracle, the proposed mixed optimization algorithm is able to achieve an optimization error of O(1/T ).
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))". (This is 
      also repeated elsewhere, with a reference to Nemirovski and Yudin's book.) 
      As far as I am aware, this bound has never been shown. The lower 
      bound has been shown for Lipschitz-continuous functions, but I'm not aware 
      of such a lower bound on smooth functions so please provide a citation. 
      Indeed, the recent work of Bach and Moulines ["Non-strongly-convex smooth 
      stochastic approximation with convergence rate O(1/n)"] gives an algorithm 
      for special cases that achieves an O(1/T) rate, indicating that this lower 
      bound may not be true. Note that an O(1/T) rate can also be 
      achieved in some special cases, such as the one given above or cases where 
      the noise goes to zero as the minimizer is approached (as with methods 
      that use a growing sample-size). "A small L2 regularizer does NOT 
      improve the convergence rate of stochastic optimization." Since 
      this paper focuses on the case of smooth optimization, wouldn't adding a 
      small L2 regularizer allow one to use the methods of [18,20] to achieve a 
      faster (linear) convergence rate? The first bullet point in in the 
      introduction should indicate that the gradient is available too. 
      Please add to the paper that Definition 1 is equivalent to f' 
      being beta-Lipschitz continuous. It is worth adding a sentence to 
      the paper pointing out that reducing the amount of regularization over 
      time is closely-related to the classic proximal-point algorithm. 
      In the conclusion, please comment on whether O(1/T^2) rates could 
      be achieved by an accelerated method in the mixed optimization scenario, 
      and whether linear convergence rates could be achieved in the 
      strongly-convex case. It is worthwhile to add a sentence to the 
      paper contrasting the mixed optimization approach with the very 
      closely-related approaches that use growing sample-sizes of Friedlander 
      and Schmidt ["Hybrid Deterministic-Stochastic Methods for Data Fitting"] 
      and Byrd et al. ["Sample size selection in optimization methods for 
      machine learning"].