Unit Tests for Stochastic Optimization
Authors: Tom Schaul, Ioannis Antonoglou, David Silver
ICLR 2014

Abstract: Optimization by stochastic gradient descent is an important component of many large-scale machine learning algorithms. A wide variety of such optimization algorithms have been devised; however, it is unclear whether these algorithms are robust and widely applicable across many different optimization landscapes. In this paper we develop a collection of unit tests for stochastic optimization. Each unit test rapidly evaluates an optimization algorithm on a small-scale, isolated, and well-understood difficulty, rather than in real-world scenarios where many such issues are entangled. Passing these unit tests is not sufficient, but absolutely necessary for any algorithms with claims to generality or robustness. We give initial quantitative and qualitative results on a dozen established algorithms. The testing framework is open-source, extensible, and easy to apply to new algorithms.


Peer review:
[Review]:
This paper looks at developing 'unit tests' for stochastic optimization algorithms, which consist of toy objective functions and corresponding gradient noise that are assembled randomly from a suite of various components.  The hope is that these tests would allow one to analyse the specific failure cases for various methods, perhaps in order to inform improvements to them.

This paper is mostly just engineering, but the authors seem to have created a fairly versatile tool for generating toy problems with many different characteristics which may well be quite useful in the future.  The paper itself doesn't contain much in the way of useful conclusions about the optimization algorithms (mostly different versions of SGD) that are tried.   I also have several issues with various aspects of the unit tests themselves, and am not fully convinced that they are testing the 'right' kind of thing or if these tests can tell us much of use about the optimization problems we really care about. 

It would have been nice if the paper had demonstrated how these tests could actually inform algorithm design.

Nonetheless I would recommend that it be accepted.  I hope the authors can address some of the issues I've brought up.


Detailed comments:

Are these optimization surfaces unimodal?  If not, couldn't it be the case that some optimization methods simply will get 'lucky' and bounce their way into a better local basin, whereas other that might be more careful about remaining stable in the face of noise will miss these?  This seems to me like it might not be a realistic analogy of the kinds of optimizations we care about, where multimodal landscapes with multiple modes of highly variable quality don't seem to exist.  I'm thinking about neural network optimization in particular here, and going on my experience that typically the lowest achievable error from run to run doesn't vary all that much (if at all).

Another major issue I have is that by testing local convergence of methods you are really only testing one them in a single and likely not too important phase of optimization: fine convergence to a local min.  Often in these cases the method that can deal with the noise the best wins.  I'm not sure if this is the best analogy to what happens in deep net optimization, where fine convergence to a local min seems to be only a small and not particularly important phase of optimization (which is often just associated with overfitting).

I would wager that the most significant aspect of optimization is the journey towards a local min from very far away along a very curvy path that can possibly lead to other local mins of roughly equivalent quality.  It is not clear to me that your unit tests properly capture this aspect of optimization by focusing either on fine convergence to local optima, or the tendency for an optimizer to jump out of one local min into a closely situated and much higher quality one.


Page 1:  In what sense do you mean that these weaknesses are separate from 'raw performance'.  If an algorithm is performing well on some task, why would I care if it has some invisible issues on that task, as long as it appears to be working?  I think I'm misinterpreting what you meant here.

Page 1: I don't really understand what you are saying in the 'locally' paragraph.  Are you saying that you want to assume local optimization because your units tests, if they are to be run quickly, can only consider toy examples with a simple local structure (unlike a neural network which has a 'global structure')?   And what does this have to do with non-stationary algorithms (or do you mean non-stationary objective functions?) or 'initialization bias'?   Don't you still need to initialize the algorithms in the unit tests and won't this choice affect the relative performance of different methods?

Page 3: With these noise prototypes, is it obvious why their mean must recover the gradient (i.e. so they are unbiased)?   For the additive case this is clear, since the noise has mean 0, but it is less clear for multiplicative noise.   I suppose if the average scale is alpha the multiplicative noise would on average estimate alpha*gradient.  

This is an important point, since the stochastic gradients need to be unbiased for many stochastic optimization algorithms to work, at least in theory. 

Cauchy noise, for example, doesn't even have a mean, so this seems a bit problematic.  Although I suppose for certain choices of its parameters, the distribution is at least centred around 0.  Perhaps this might be good enough in practice.  Is this what you did?

The mask-out noise is unbiased as far as I can tell.

You really should discuss the issue of unbiasedness of your noise in general, as this is very important to the theory of these methods.

Page 4:  How are you generating these random rotations?  Are these just like random orthonormal matrices?  Generated how?

Page 4:  It is not clear to me why gradient descent should work at all when it is given vectors from a vector field that is not actually a gradient field.  And assuming it does work for certain such fields, the reasons are probably subtle and highly situation dependent.  I don't imagine that this can be easily simulated by applying a fixed rotation to the gradient.  In fact, I can't even imagine how gradient descent could ever converge if it were given gradient with a fixed rotation.  For example, you could just permute the coordinates.  That is a valid rotation, but surely this would cause most reasonable algorithms to fail catastrophically. 

Also, you should explain concept of curl etc for this audience.

Page 5:  What do you mean in the sentence: 'However, non-stationary optimization can even be important in large stationary tasks, when the algorithm itself chooses to track a particular aspect of the problem, rather than solve the problem globally.'  What do you mean by 'aspect', 'track' and 'globally' here?  This goes back to my previous question.

Page 5:  I think a better way of simulating non-stationarity of the objective function would be to perhaps randomly jiggle or move the various shape and scale parameters that define your objective.  Mere translation doesn't seem particularly hard to deal with, or realistic. 

Page 6:  Why didn't you test the method(s) from [9]??

Page 6:  Double the progress of vanilla SGD doesn't seem particularly 'excellent' to me.  Perhaps merely 'good'.

Page 7:  What are these 'groups'?  Where do you describe what they are?  

Page 7:  So if I understand correctly, the vertical axis gives the different methods with different hyper parameter choices for each method?  

Many of these methods, such as Nesterov's accelerated gradient, have automatically adapted hyperparameters, which is sometimes done according to a fixed schedule.  The momentum parameter in particular usually isn't supposed to be constant, at least in theory. 

And in general, for stochastic optimization methods, there usually are no guarantees for a fixed learning rate.  Some methods like ADAGRAD implicitly anneal the learning rate, while with others, like plain SGD, or accelerated gradient SGD, you need to reduce the learning rate adaptively or at least with a schedule if you plan to have fine convergence to a local min.

Are you keeping these fixed, are you are instead varying the hyper-hyperparameters of the methods that adjust the hyperparameters?   

Are methods with 'thicker' regions ones with more adjustable hyperparameters?

It seems to me that it doesn't really make sense to plot the values for all hyper-parameters, when some are clearly crazy.  If a method has lots of hyperparameters, it shouldn't be judged to be 'less robust' if for certain crazy choices of these it diverges.  And it isn't always true that we have no way of determining good hyperparameters for methods that have them.  Binary search, or perhaps Bayesian optimization are certainly better than exhaustive sweeps.  More simply than that, one can just adjust these things on the fly, with a heuristic or manually if needed, as partial progress with sub-optimal hyperparameter choices doesn't need to be thrown out (unless very bad divergence has taken place, and then you can always backtrack to a previous snap-shot of the parameters).