Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: This paper proposes a heuristic method for selecting learning rate schedules for momentum-type methods and evaluates the proposed method on two image classification benchmarks including CIFAR10 and ImageNet. Statistical tests are presented to check the stationarity of the gradient updates. And stochastic line-search methods are proposed to warm up the optimization process during early phases.

Pros:

The main idea is to check the non-stationarity of the iterates and decrease the learning rate if stationarity is detected. To check stationarity, a quadratic approximation for the objective is used. Another procedure for how to decrease the learning rate is proposed using a stochastic line search. The idea makes sense to me.

Cons:

-- The quadratic approximation simply assumes that the Hessian matrix of the objective is identity (Equation 10 in Section 2). I appreciate the simplicity of this formulation. Indeed quadratic forms are good local approximations for any general function. On the other hand, it is quite possible that the Hessian matrix has a low-rank structure or has a sharply decaying spectrum. This kind of scenario naturally arise in high-dimensional settings where the model has lots of parameters. Therefore, it seems to me that further justification (either empirical or theoretical) could help clarify the intuition better.

-- The experimental results compare the proposed method to other well-known methods such as SGD and ADAM. From Figure 1 and Figure 5, it seems that the proposed method performs comparatively to both SGD and ADAM. In particular, it is not obvious from the experimental results that there is a huge benefit obtained from the proposed methods. Hence the experimental results seem a bit incremental to me, as far as I can tell.

More comments:
-- Notation: using $\xi$ to denote the data points seems a bit unconventional.
-- Typos: "Pflug also a devised" -> "Pflug also devised".
-- The current version is significantly over length (by more than 1 page).
review_title: Official Blind Review #1

final_score: rating: 6: Weak Accept
review_content: The authors explore how stationarity tests can be leveraged to automatically tune the learning rate during training. Their algorithm also add a robust line search algorithm, to reduce the need to tune the initial learning rate. The paper is clear and the literature review is honest and thorough. However, it is unclear to me if the contribution of the authors is enough, as the method used and its presentation are very close to Lang and al. In particular:

- First bullet point on page 2: Because of its conceptual and analytical simplicity, it greatly simplifies implementation and deployment in software packages. It is unclear why the approach proposed by Lang is more complicated to use
- It is a recurrent theme in the paper that the proposed method is a simple interval test compared to a more complicated equivalence test in Lang et al. It is unclear to me what the authors mean by that, as pages 5 and 6 of Lang clearly details a confidence interval test too.
- If SASA+ is indeed just a new presentation of the algorithm detailed by Lang, the line search contribution does not justify a paper in my opinion
- In page 5, "Another major difference is that they set non-stationarity as the null hypothesis and stationarity as the alternative hypothesis (opposite to ours)." I am not sure how the authors arrived to the conclusion that non-stationarity was the null hypothesis in Lang and would appreciate some clarifications on this point. The test used in SASA is a simple t test with a variance corrected to account for the auto-correlation of the gradients.

About the empirical work:

- The experiments seems plausible. Hyper parameters were search for fairly for the competing methods. Adam could have benefited from a finer learning rate schedule, as it is only decreased once compared to several time for the SGD. I would indeed expect a performance gap between Adam and SGD, but I think most of it in this case comes from the one step schedule.
- Line search is performed but no metrics were shown to discuss the computational overhead of evaluating the model and its gradients for different parameters during the search.

SALSA appears to be an already existing algorithm on which a line search was plugged in. The line search part, which appears to be the only contribution, is not discussed enough in my opinion (in terms of computation cost for instance)

To conclude, I think the presented work is too close to the existing literature and that the progress made is very incremental.

EDIT after rebuttal: My concerns have been addressed, I revise my rating from weak reject to weak accept.
review_title: Official Blind Review #3

final_score: rating: 8: Accept
review_content: This paper proposes a new way of automatically scheduling the learning rate in stochastic optimization algorithms: Stochastic Approximation with Line-search and Statistical Adaptation (SALSA).
By first introducing a necessary condition for stationarity, the authors use this condition to make a simple statistical test for non-stationarity. Using this test, the authors propose the following strategy for the learning rate schedule in stochastic optimization problems:
(1) They first apply a new Line-Search algorithm (Smoothed Stochastic Line-Search - SSLS) to increase a small initial learning rate until the process becomes stationary according to their statistical test. At this stage, the learning rate is assumed to be optimally initialized for the objective function considered.
(2) The second step is to decrease the learning rate gradually every time the process is stationary again. For this, the authors derived their own version of a Statistical Adaptive Stochastic Approximation algorithm called SASA+ based on their statistical test.
The resulting strategy benefits from being simpler than previous statistical tests while being equally effective empirically.
The authors empirically demonstrated that their new learning rate scheduling mechanism achieves comparable, if not better, accuracy on two image classification tasks with ResNet-18 neural networks. It is important to note that the compared baselines got their parameters slightly fine-tuned, while (according to the authors) the proposed approach was not fine-tuned, and only the default parameters were used. This shows the robustness of the proposed approach against its various parameter settings.

I would accept this submission because the authors propose a new learning rate scheduling mechanism that seems to perform well empirically while being robust against its different initial parameter settings (including the choice of the initial learning rate).

This paper has several novelties: first, it proposes a simpler, yet as effective as previous approaches, Statistical Adaptive Stochastic Approximation (SASA) algorithm based on a new statistical test for non-stationarity. Second, it manages to relax the dependence of SASA algorithms on their optimal initial learning rate by introducing a Smoothed Stochastic Line Search (SSLS) algorithm that is responsible for finding such an optimal initial learning rate. Combined together, these two sub-routine provide a robust mechanism to schedule the learning rate in stochastic optimization problems.

One improvement I could suggest to better motivate the proposed approach is to experiment it not only on Convolutional-based networks with image classification tasks but also on Recurrent-based networks with text datasets. For instance, keeping the ImageNet experiments, the CIFAR-10 experiments could be replaced by an NLP task. This would show that the proposed approach is robust to different types of deep learning problems.

Overall I found the paper well written, and relatively easy to follow, even for non-theoretical practitioners. A few details listed below could improve even more the quality of this paper:
- At the top of page 2, the last sentence of the top paragraph ("However, these learning rate schedules are insufficient ...") requires a citation.
- In Figure 5: it is a little confusing to have the SASA+(NAG) algorithm in both rows: once in the top row, twice in the bottom row. The difference between the two SASA+(NAG) in the bottom row is well explained, but is there any difference between SASA+(NAG) in the top row and the ones in the bottom row?
- In Figure 5 - bottom row, left graph: if all lines are SASA+ algorithm, the legend should be consistent: either add "sasa+" to all lines or remove it from all lines.
- On page 9, ImageNet paragraph: a small typo: "On the other hand, both both SASA+ and SALSA...".
review_title: Official Blind Review #2

Meta-review: The paper proposes an approach to automatically tune the learning rate by using a statistical test that detects the stationarity of the learning dynamics. It also proposes a robust line search algorithm to reduce the need to tune the initial learning rate. The statistical test uses a test function which is taken to be a quadratic function in the paper for simplicity, although any choice of test function is valid. Although the method itself is interesting, the empirical benefits over SGD/ADAM seem to be minor. 

Decision: Reject