Asynchronous stochastic convex optimization: the noise is in the noise and SGD don't care
We show that asymptotically, completely asynchronous stochastic gradient procedures achieve optimal (even to constant factors) convergence rates for the solution of convex optimization problems under nearly the same conditions required for asymptotic optimality of standard stochastic gradient procedures. Roughly, the noise inherent to the stochastic approximation scheme dominates any noise from asynchrony. We also give empirical evidence demonstrating the strong performance of asynchronous, parallel stochastic optimization schemes, demonstrating that the robustness inherent to stochastic approximation problems allows substantially faster parallel and asynchronous solution methods. In short, we show that for many stochastic approximation problems, as Freddie Mercury sings in Queen's Bohemian Rhapsody, "Nothing really matters."
Summary of paper:The paper studies a class of asynchronous methods to solving optimization problems in which the objective function is an integral functional of a random process or variable integrated against a probability measure. The class of problem assumed is that the argument of the functional for each non-zero measure set or outcome in the sample space upon which the measure is defined will produce a convex function. In this case the authors demonstrate that asymptotically, completely asynchronous stochastic gradient procedures achieve optimal convergence rates for the solution of convex optimization problems under nearly the same conditions required for asymptotic optimality of standard stochastic gradient procedures. The authors are able to then propose based on these results specialised asynchronous procedures based on multi-core parallelization schemes for stochastic gradient based optimization algorithms which behave analogously to synchronous procedures.Quality:The problem statement and all assumptions are very carefully set out and clearly written and explained with regard to the meaning and significance of such assumptions. The exposition and explanation of Theorem 1 is very well presented as is the technical details for Theorem 2 and the required Lemmas in the appendix.The examples selected to illustrate the method were also very interesting having selected the regression examples based on linear regression as a toy illustration and then non-linear logistic regressions were proposed. These were relatively simple and demonstrated that the required conditions were not overly restrictive for real problems in applications settings.However, it would be perhaps informative to explain a little more background on the context of the extended problems based on stochastic monotone operator problems, this is left very brief and a citation given, it would be useful to see a little more context here.In assumption C and D for the distribution of the noise process it would be good to get more explanation of these assumptions and their significance and interpretation.The experiment performed is very carefully detailed and well designed.Clarity:The paper is highly technical for a NIPS audience but it is very well written and explained carefully so it is still in my opinion in the scope of the conference. I believe the authors have done an excellent job to explain such detailed results in a short paper so clearly and concisely.Originality:The paper is based on several existing works but provides a useful set of results for practical problems which generalise and relax assumptions of existing works.Significance:The authors show that their results significantly generalize existing works that have considered similar results, though as they state previous works of a related nature often impose strong conditions on gradient sparsity or conditioning of the Hessian or allowable types of asynchrony. In particular they only require minimal conditions which are that at the argument that minimizes the objective function one has a positive definite evaluation of the function and that the gradient are smooth.