Optimization and Generalizability: Fair Benchmarking for Stochastic Algorithms

R: "The paper is very well-written and easy to follow. This topic is of high interest to the community: given the ubiquity of SGD in daily machine learning practice, better understanding the intrinsic stochasticity of SGD in various loss landscapes is crucial."

A: We thank the reviewer for this perspective and summary of our work and for the kind words.

R: "On the content itself, I have nothing much to say. I think the research methodology is sound."

A: We thank the reviewer for these encouraging words.

R: "A minor details is the algorithm formatting in LaTex which could be enhanced. The instructions are colliding with the frame borders with almost no padding. This should be fixed for a nicer presentation."

A: We thank the reviewer for prompting us to this issue. It was a side-effect of attempting to pack a lot of content in the nine allowed pages. We have now increased the vertical and horizontal margins between the frame borders and the algorithms’ pseudocodes. We also tightened some of the variable names to allow for such margins, such as replacing “cand” with “c” in the superscript of “w” to indicate candidate weights, and replacing tls with “\Delta t” to indicate amount of time spent by the LocalSearch. Tightening up the language in several paragraphs also allowed us to better fit content in the allowed number of pages and accommodate larger font in the tables.

R: "The experiments on the synthetic dataset are interesting and reveal some useful information such as the distribution of SAM is skewed towards flatter minima."

A: We thank the reviewer for noting this.

R: "The proposed method may not be practical. First, if several models are sampled from one trajectory, they could be correlated, and the resulting statistical test may not be so useful. For example, with a bad initialization, the models sampled from the trajectory may not represent the population, which can lead to misinterprete the actual performance of the algorithm. Second, if multiple trajectories are required, this could increase the computation cost. Moreover, depending on the goal, one best model can be sufficient and a group of models is certainly not required."

A: The reviewer is correct that a trajectory gives you a biased view of the landscape. That is an important point we make in the manuscript. We argue for a population of models, hence the need to sample from multiple trajectories, which is what the paper does. The point on multiple trajectories coming at higher computational cost than one trajectory is correct, but we think it misses the point. We are not changing the behavior of any of the optimizers. We are not arguing for more expensive optimization algorithms. What we are trying to do in this paper is change the way we “do business.” The reviewer will note (and we make this point more formally in the paper) that the way much research that debuts a new optimization algorithms is the following: Here is our algorithm. Here is the converged model. Here is how the model performs on the held-out dataset on a variety of selected real-word problems. Some improvement in accuracy or macro-F1 is touted as the algorithm conferring better generalization. What we are arguing in this paper is that this won’t do in the presence of multi-dimensional nonconvex loss landscapes. Looking at one model ought to give us no confidence for why one would take this model and “deploy” it out there. Looking at one model also ought to give one no confidence for statements to the effect of “my algorithm is better than yours.” What is worse, many of these algorithms (including SGD) are stochastic, so again one cannot rely on one model. We argue that better clarity is provided when you switch the “benchmarking setup” from one model to a population of models. That is what we are attempting to do in this paper. The point on “depending on goal, one best model can be sufficient and a group of models is certainly not required” is somewhat chicken and egg. How would one know? Again, if you show that the population is homogeneous, that is great, but one would only know that if one introduces a nonlocal view in the first place, which is what we are arguing in this paper.

R: "The experiments are not comprehensive. No large-scale datasets such as Imagenet are considered, and the neural network architecture is also limited."

A: We had intended to add experiments on more real-world problems but ran out of time. We have now added ImageNet. Additionally, we had intended to add an important point on model architecture (e.g. ResNetX vs. ResNetY), which the reviewer astutely notes and which allows us to control in some manner for expected loss landscape complexity. We have added several model architectures both for the computer vision and the natural language processing tasks. Due to the limitation of space in the 9 pages in the main paper, we have added this analysis that additionally considers model architectures in the Supplementary Material, summarizing the main findings in the main paper.

R: "Considers generalisation performance rather than simply rate of convergence of the optimiser (there are too many papers that don't do this)."

A: We thank the reviewer and now single it out as Contribution 4.

R: "A neat collection of synthetic examples are considered."

A: We thank the reviewer for noting this.

R: " "Rigorous" comparison is far too limited in scope; unambitious. [..] You need many more real-world examples [..]."

A: We have added ImageNet, as well as different model architectures.

R: "Generally poorly written, with numerous grammatical issues, inconsistent capitalization (e.g. CIFAR vs Cifar)."

A: We have carried out a thorough editing and fixed elemental mistakes and typos. We take issue with the blanket statement that the paper is “generally poorly written.”

R: "Odd structure; why is Section 4 after Section 3, when Section 3 and Section 5 link with each other?"

A: Section 3 needs to come first as it introduces the benchmarking setup. Section 4 introduces the algorithms compared under this setup. Section 5 then relates the performance of these algorithms under the benchmarking setup.

R: "Unpleasant presentation: algorithm environments with clashing borders, [..], incorrect citing (citet vs citep)."

A: These were a side-effect of attempting to pack a lot of content. We have now addressed all.

R: "Algorithms in the comparison are oddly chosen [..]. Where is Adam for example?"

A: We have followed the convention. ADAM has several components that affect behavior, such as the separate learning rate over each weight parameter. This makes it difficult to isolate a “baseline” behavior for deeper understanding that is not confounded by potentially inter-related effects of hyperparameters.

R: "[..] Multiple hypothesis tests are performed without p-value correction [..]."

A: Please note that with our hypothesis testing we are not testing different components and so are not taking the “totality” of tests to reject the null hypothesis. We investigate two distinct approaches to account for potential reviewer concerns re parametric vs. non-parametric.

R: "Does GD use the normalised gradient vector, or just the gradient vector?"

A: We utilize GD on the synthetic functions. Normalizing is computationally more expensive. It also opens up questions. For instance, what step size to use? We determine to proceed with the less expensive (and more popular) version of not normalizing the gradient, and letting the gradient norm provide the speed towards minima.

R: "Do any of the synthetic examples in Figure 1 correspond to parts of a real loss landscape?"

A: Our choices of synthetic functions that have many local minima and so span the range (including “degenerate” examples such as Beale and Rastrigin in the Supplementary Material) in capturing different characteristics of real landscapes.

R: "What is the purpose of the p-values in Section 6.2? [..] There is naturally a lot of variance [..] but one optimiser may still perform consistently better than another [..]"

A: Comparing SetA by Algorithm X to SetA by Algorithm Y addresses the variance when looking at one model, which most optimization-centric papers do. Casting our comparison between populations of models via hypothesis testing ought to reveal if one algorithm does “consistently better.”

R: "Can you present the stationary distributions in terms of bar charts rather than as a table? It's really difficult to read as is."

A: We were trying not to delegate too many important points to the Supplementary Material. Bar charts did not "pack in" better. We amplified with graphical visualizations in the Supplementary Material (distribution of end-points over contour plots).

R: "How long is each optimisation algorithm run for?"

A: Section 6 - “[..] 300 epochs.”

R: "[..] It is obvious that there should be no significant differences here."

A: Expecting no significant differences is akin to believing that you can control for better generalization with better optimization. Researchers are skeptical of this. Correlation analysis is fraught with issues. Even if one were to go down that route, reviewers undoubtedly would insist on a more rigorous comparison under statistical significance testing, which we do in this paper.

R: "The differentiation between SetA and SetB seems odd to me. Why not just report all the metrics?"

A: We are reporting all. We believe this question is due to insufficient differentiation between SetA and SetB, which Contribution #4 now makes.

R: "[..] leads to computational cost. The authors should compare this approach to the standard procedure (repeating the experiments multiple times) and take into account the cost into your comparisons."

A: Copying from Section 6: “We set Tr = 5 and L = 10.” The Tr = 5 trajectories address the reviewer’s suggestion of “repeating the experiments multiple times.” The point on multiple trajectories and computational cost is correct but misses the point. We are not changing the behavior of an algorithm. We are not unfairly making one more expensive than the other.

R: "The approach is naive in the meaning that they do not consider other factors that may affect the performance of each method: step sizes and other hyper parameters, starting point, whether the methods converge and with what network architecture (for the complex learning problems). Without these considerations, it is difficult to say that the proposed benchmark procedure is more fair than the others."

A: The starting point is addressed by varying over trajectories. The point on step sizes and other hyperparameters were explicitly acknowledged in Section 7 (Limitations and Future Work). When researchers debut an optimizer, they “freeze” hyperparameters not introduced in the optimizer. Take SAM; it states several times “see appendix for all hyperparameters.” In the appendix it states: “all other model hyperparameter values are identical to those used in prior work.” Typically, you want to isolate performance in response to a particular effect to start to obtain some understanding. We would love for the community to expand into other factors. Here we focus on better understanding performance by expanding the context first to a population of models, which ought to remove some biases, such as initial conditions.

Our analysis now includes model architectures (summary findings in the main paper and detailed tables in the Supplementary Material). All our findings on the inability to reject the null hypothesis still stand.

We relinquish the point on “fair” and replace it with “new” or “proper” in the title and the rest of the paper.

R: "Contrary to the contribution sections, there is no 'novel' stochastic optimization algorithm introduced in the paper. The authors only apply previous method to Basin Hopping frameworks."

A: We debut novel optimizers that leverage the BH framework. To the best of our knowledge, we cannot find optimizers that do so in published literature on optimization for deep learning.

R: "The presentation of this paper is poor and very confusing. For examples: "populations of models" actually meant a collection of end-models of each trajectory created by an optimizer. "stationary distribution of an optimizer" makes no sense."

A: With this summary term we were trying to incapsulate two distinct analyses, one that compares SetA to SetB for each optimizer for each task, and another that compares SetA of one optimizer to SetA of another optimizer. Hence our "populations of models." We agree that this may have been confusing and have revised the list of Contributions. In particular, Contribution 4 now explicitly brings to the surface the comparison of what we later refer to as SetA and SetB.

On the point on stationary distributions: You can look at a trajectory as a Markov chain. When converged and over multiple trajectories, you have reached the “stationary distribution.” If the reviewer does not have much appreciation for it, we can remove mention of it. It does not affect any of the analysis or the findings.

R: The authors said they "expand their understanding of the relationship between (loss) optimization, generalization (testing error)". However this point is not clearly explained in the submission. Could you elaborate?

A: With Contribution 4 we aim to address the point raised by the reviewer. Also prompted by another reviewer’s note that the focus on generalization over rate of convergence is good, we now have added the following: “4. Generalization performance over rate of convergence: Unlike most literature on optimization for deep learning, we consider generalization performance rather than simply rate of convergence. We do so over a population of models obtained by an optimizer over several optimization trajectories rather than a single model often obtained as representative of the performance of an optimizer. We compare such a population for its generalization performance (to what we refer as SetA later on in the paper) to a population of models that are sampled by the optimizer and that an oracle has determined have the best generalization performance (to what we refer as SetB later on in the paper). Through this setup we test whether optimization performance is a good proxy of generalization performance utilizing hypothesis testing over populations of models.”