Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 3: Clear rejection
review_content: This paper proposes a line-search for optimizing deep neural networks. The method is rather unprincipled and quite close to the approach proposed in (Vaswani et al, 2019). I do not think that the paper proposes new ideas that haven't been already explored in the deterministic optimization literature. All in all, the paper needs to better connect to the algorithmic ideas in the deterministic optimization literature, compare against the new optimization methods proposed recently and have more representative plots. Detailed review below. 

- The claim "adaptive methods concentrate more on finding good directions than on optimal step sizes, and could benefit from line search approaches" needs justification. At this point, there has been substantial work that shows that adaptive methods like Adam are quite robust to their step size and do in fact, work well across problems. 

- Please cite the literature relevant to SGD, for example, Robins-Munro and Bottou et al, 2016. In the deterministic optimization literature, using Polyak step size is an alternative to line-search approaches. Please also cite the recently proposed methods based on the Polyak step-size, Berrada, et al "Training Neural Networks for and by Interpolation" and Loizou et al "Stochastic polyak step-size for SGD: An adaptive learning rate for fast convergence" that have been used to train deep neural networks. 

- In Figure 1, it is not enough to show that the loss landscapes are similar in the batch gradient direction. they should also be the same in the stochastic gradient direction, which depending on the batch, can be very different from the batch gradient direction. A more convincing approach would be to choose random directions and compute a metric of similarity for all such directions. Moreover, please explain how is "t" chosen for this plot. We know that the loss landscape is different at the start vs the end of the optimization. Consequently, this is not enough evidence to show that line-search can be done on a stochastic batch. In this figure, the batch-size is another confounding factor. What is the effect of the batch-size? 

- "lemp has a simple shape and can be approximated well by lower order polynomials, splines or fourier series." This is indeed the motivation behind line-search techniques for convex problems. Please cite Noecedal-Wright 2006 or the original line-search paper by Armijo. 

- In Section 2.2, backtracking line-search is used to overcome the first challenge, i.e. the algorithm picks the largest step-size that satisfies a sufficient decrease condition. The complexity of this is proportional to the number of backtracking iterations which is small. In the proposed approach, a number of points is sampled, meaning additional function evaluations. Please justify why the backtracking approach is not sufficient in this case, and explain why the proposed method would be better.  

- Similarly, for the second challenge, it is doing exactly the thing you cautioned against earlier "that the batch need not be representative of the full loss function".  Doing a backtracking line-search on a batch is exactly the approach adopted by (Vaswani et al, 2019). Please clarify this and also explain why you do not experimentally compare against them. 

- The idea of building a model of the loss function by using additional points (from the past) is well known in the deterministic optimization literature in the form of line-search with quadratic/cubic interpolation. This approach does not use additional function evaluations. Please explicitly make this connection and again, justify your approach against this less expensive method. Moreover, the paper proposes to build a highly accurate model of a stochastic loss which need not be representative of the full loss in any case. 

- "The test error is determined by a 5-fold cross-validation. The second last polynomial degree is chosen and the polynomial is again
fitted on all loss values to get a more accurate fit. Consequently the closest minimum to the initial location is determined and additional losses are measured in a reasonable interval around it." This is clearly very computationally expensive for determining the step-size for one iteration. Please clearly state what is the computational complexity of determining the step-size in one iteration. 

- "ELF generalizes better if not performing a step to the minimum, but to perform a step that decreased the loss by a decrease factor" This is almost the same as checking the Armijo sufficient decrease condition with a factor of \delta. Why not just do this and say it explicitly?

- Experimentally, since the proposed approach is closest to the work of (Vaswani et al, 2019), please experimentally compare against their method. 

- In Figure 4, please plot the training/test loss vs the number of iterations. One point of information in the form of the test accuracy is not representative, especially since the metric being optimized is the training loss. And there are multiple confounding factors that influence the test error corresponding to any optimization method. Since this is more of an experimental paper, it would make sense to compare against the newer variants of Adam, such as RADAM and AdaBound that have found to work well.
review_title: Unprincipled line-search approach for optimizing deep neural networks. Needs better comparison to past literature. 

final_score: rating: 4: Ok but not good enough - rejection
review_content: Summary:
This work proposes ELF, a newl method to do line search. The key idea is to fit a low order polynomial of the empirical loss (by sampling multiple batches) along the direction of a mini-batch gradient. The method stays computationally efficient by only computing the step size every so often. Experiments on a variety of image classification tasks show that ELF is competitive to GOLS1, PLS, PAL, SGD, and Adam, while taking less time to train.

Strengths:
The fact that ELF can get competitive results compared to SGD with momentum, and Adam, while taking less time to train, is exciting.

Weaknesses:
- I find the contribution of this paper a bit weak. Reading a line search paper with mostly empirical justifications, I would like to see the method outperforming a strong baseline (a commonly used optimizer for that architecture, with default hyperparameters for example) where ELF uses a fixed set of hyperparameters. Such an experiment would justify the practical usefulness of ELF. As far as I can tell, this sort of experiment was not done. 
- The paper doesn’t clearly show the role fitting empirical instead of batch loss (which is written as the main contribution) compared to the introduction of beta and delta on performance. How does PAL perform with these additional settings (since they also seem equally applicable)? Similarly, for Figure 3: How much of this is due to the introduction of beta and delta compared to fitting method, or the fact that empirical loss is used rather than batch loss?
- Using the validation set during training doesn’t really make sense. If the method overfits greatly by using just the training set, then that method is prone to overfitting; using the validation set can’t be the solution.
- Currently, the paper’s presentation is lacking. Paragraphs are too long, the related work section feels unorganized, Figure 1 is taken from an already published paper, and the two huge algorithm boxes break the flow of the paper and is too much detail. 

Decision:
Reject. The idea shows promise but the current state of the paper should be improved before warranting acceptance, for the reasons listed above.

Comments and questions:
- “Due to CLT we can assume p_data to be Gaussian” - not true.
- Was there a reason why SLS (Vaswani et al. 2019) wasn't included in the comparisons? To my knowledge, SLS is the best performing line search method in deep learning.

review_title: Review for ELF

final_score: rating: 4: Ok but not good enough - rejection
review_content: Update: I thank the authors for the detailled response. Due to the number of required changes and the feedback of other reviewers, I believe the paper needs a major revision before publication and still recommend rejection.


---

The submission introduces a heuristic to select the step-size for training deep learning models. Reducing the dependence on hyperparameters and improving the performance of optimization methods with out-of-the-box settings is an important problem and relevant to the ICLR community. The proposed approach is novel and well illustrated.

However, as there are limited theoretical contributions or new insights, the submission has to be evaluated on the effectiveness of the method. The main weakness of the manuscript is a lack of motivation for the details of the proposed heuristics and insufficient experimental evaluation. 

Despite the method being described as simple and straightforward, I fail to see how the proposed approach is simpler than a backtracking line-search on the batch loss. A main argument for the proposed approach in constrast to previous work is that the minibatch loss is not sufficiently representative for a line-search. This contrasts with observations in previous work (e.g. Vaswani et al., 2019). While it makes intuitive sense that taking multiple batches into account is necessary in the presence of noise, there is limited evidence that the proposed method does so appropriately. The experimental evidence in section 3.1 is promising but is not broad enough to be informative. While the results of section 3.2 are nice to have, the improved robustness of the method against SGD and Adam is not surprising; the space would be better used comparing the performance of the method against the other cited works on batch line search.

My recommendation is towards a rejection. There is evidence the proposed method can work. But I doubt the submission will generate enthusiasm from the theory side of the community do to the limited new insights and the empirical evaluation is insufficient to convince me of the benefits of the method over previous work for its applications.


As additional feedback (there to help, not necessarily part of the decision), I advise the authors to pay a greater attention to presentation details when preparing their submissions. The writing and quality of the figures gets in the way of the message they are trying to communicate. For a few example, since the "homoscedasticity" is irrelevant for the current problem, I do not follow why it is mentioned so prominently in section 2. The use of "vertical cross-section" is also confusing; it is still unclear to me what is 
vertical.

review_title: Review

final_score: rating: 4: Ok but not good enough - rejection
review_content: The paper tackles an important issue, namely how to tune the step sizes in SGD during the training, trying to approximate step sizes which would be used in GD (even though the search direction is still noisy). Relevant prior work is cited. The method is simple and easy to understand. Step sizes are kept piecewise constant over updates. New batches are sampled, and the loss values along the search line are fitted with a low-order polynomial. There is some heuristic to choose the interval around 0 for the step. Importantly, these batches are sampled from the validation set. While this sounds very elaborate to find the minimum of the approximation, they later say they are just trying for sufficient descent along the line. Compared to previous work, the method is simple and seems quite robust. As drawbacks, the method seems pretty expensive, and it has a large number of free parameters that need to be chosen.

A major weakness of the paper is the empirical evaluation. The comparison to related work in 3.1 is a bit meaningless, because they look at validation error. Now, their method uses the validation set extensively (to sample batches), while the others do not, so the comparison is flawed. One would have to evaluate on an independent test set. What is also really missing here are figures about the extra amount of time required. My suspicion is that PLS is quite a bit cheaper than what they do here, even though admittedly it needs specific implementations (which, for TensorFlow, are provided by the authors).
Then, in 3.2, they do not compare against this related work anymore. Why not? Again, I am missing a proper quantification of extra cost. It is also unclear how the many free parameters of their heuristic are chosen. For Figure 6 left, it is hard to understand why there is this difference. The reason is buried in the text somewhere: "To determine whether to measure a new step size...". This describes a rule for how often to update step size, and it again has unspecified free parameters. For Figure 6 right: This comparison is meaningless unless the stopping criteria for all methods are clearly stated. If ELF is using *extra* batch evaluations to adjust learning rate, it must be slower than ADAM or SGD if the same number of epochs are done. What takes the extra time for ADAM and SGD? Do they run more epochs? If so, what is the stopping rule? If that rule depends on validation error, the comparison is flawed (see above), because ELF accesses the validation set a lot, while ADAM and SGD do not (except for initial HPO). Or do they all run the same number of epochs? If so, what takes the extra time for ADAM and SGD? If this is some initial HPO, it has to be clearly specified, as it could range from cheap to very expensive depending on what is done.

Given these issues, I feel the work cannot be properly evaluated. My recommendation is to (a) clearly quantify the extra cost for all methods compared, (b) to compare against PLS and GOLS1 everywhere, (c) to be very specific about how training is stopped when comparing training runtime, and (d) to evaluate metrics on a dataset that ELF has no access to.

Since ELF seems quite expensive, it would be useful to try and see what can be done with batch losses evaluated along the training trajectory, instead of having to sample independent ones. They should also test how few batch losses are needed to still get good behaviour. In general, some ablation studies are needed that would drive down extra compute and check how fast this can be made.

review_title: Proposes heuristic to tune step sizes in SGD during the training run, by sampling a number of extra batch losses now and then.

Meta-review: This paper proposes an empirical method to automatically schedule the learning rate in stochastic optimization methods for deep learning, based on line-search over a locally fitted model. The idea looks interesting and promising, but the reviewers have serious concerns in the lack of principled support and insufficient empirical evidences. Therefore I recommend rejection of the paper and encourage the author(s) to strengthen the idea and contribution with further theoretical and empirical study.
Decision: Reject