Recent works have shown that line search methods can speed up Stochastic Gradient Descent (SGD) and Adam in modern over-parameterized settings. However, existing line searches may take steps that are smaller than necessary since they require a monotone decrease of the (mini-)batch objective function. We explore nonmonotone line search methods to relax this condition and possibly accept larger step sizes. Despite the lack of a monotonic decrease, we prove the same fast rates of convergence as in the monotone case. Our experiments show that nonmonotone methods improve the speed of convergence and generalization properties of SGD/Adam even beyond the previous monotone line searches. We propose a POlyak NOnmonotone Stochastic (PoNoS) method, obtained by combining a nonmonotone line search with a Polyak initial step size. Furthermore, we develop a new resetting technique that in the majority of the iterations reduces the amount of backtracks to zero while still maintaining a large initial step size. To the best of our knowledge, a first runtime comparison shows that the epoch-wise advantage of line-search-based methods gets reflected in the overall computational time.
Paper
Similar papers
Peer review
Summary
This paper proposes the use of nonmonotone line search methods to speed up the optimization process of modern deep learning models, specifically Stochastic Gradient Descent (SGD) and Adam, in over-parameterized settings. The proposed method relaxes the condition of a monotonic decrease in the objective function and allows for larger step sizes. The authors introduce a new resetting technique that reduces the number of backtracks to zero while still maintaining a large initial step size. The proposed POlyak NOnmonotone Stochastic (PoNoS) method combines a nonmonotone line search with a Polyak initial step size. The paper proves the same rates of convergence as in the monotone case. The experiments show that nonmonotone methods outperform the rate of convergence and also generalization properties of SGD/Adam.
Strengths
- **Originality:** The use of nonmonotone line search methods to relax the condition of a monotonic decrease in the objective function is a stochastic generalization of [Zhang and Hager 2004] which was proposed initially for deterministic optimization. The initial step size is chosen on the basis of previous work [Vaswani et al 2019]. The paper also introduces originally a new resetting technique that reduces the amount of backtracks to zero while still maintaining a large initial step size. Overall, the paper's originality is a significant strength. - **Quality:** The paper provides rigorous proof that the proposed nonmonotone line search method has the same rate of convergence as in the monotone case despite the lack of a monotonic decrease. The experiments show that nonmonotone method has a larger speed of convergence and better generalization properties of SGD and Adam. Computational time comparison experiments also show the outperformance of the proposed method. The theory is solid and the experimental results are strong. - **Clarity:** The paper is well-written and easy to understand, with clear explanations of technical terms and concepts. Qualitative explanations of the theorems are provided to help the readers understand the main messages. The authors provide detailed descriptions of the proposed method and the experiments conducted to evaluate its performance. Comparisons with other methods are presented clearly. - **Significance:** The proposed method shows the outperformance of existing state-of-the-art algorithms in both computational time and generalization properties.
Weaknesses
- The proposed method includes many parameters to be chosen artificially, such as $\eta_{\rm max}$, $c$, $c_p$, $\delta$, and $\xi$. Although the ranges of them are provided in the theorems, influences on the performance of the proposed method due to different choices of these parameters are not clear. Are the specific values used in a real experiment not so important? If so, to what extent?
Questions
Same as stated in the **Weakness** part.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
The limitations of the proposed method are stated not sufficiently. Only future perspectives are stated. For example, considering the local PL assumption. The claims that the proposed method outperforms many other the-state-of-the-art methods from several perspectives are quite strong. Are there any drawbacks, or points to be improved, of the proposed method?
Summary
This paper proposes a non-monotonic line search method for choosing step sizes in stochastic optimization. Convergence rates are proved for strongly convex, convex, and PL functions, and the rates match those of previous work. Experimental results show that (1) for MLPs and CNNs, the proposed algorithm outperforms SGD, Adam, and previous line search methods, and (2) for kernel models and transformers, the proposed algorithm outperforms SGD and previous line search methods, and is competitive with Adam.
Strengths
1. The question is significant. Given the observations of the "edge of stability" and non-monotonic decreases in loss when training deep networks, it seems natural that incorporating non-monotonicity into line search methods may yield significant performance improvements. 2. The presentation is clear and easy to follow. 3. The theoretical results (Theorems 1, 2, 3) can recover convergence rates from previous work. 4. The experimental evaluation is very broad, covering many datasets and neural network architectures.
Weaknesses
1. The proposed algorithm appears to be a direct combination of existing techniques (non-monotonic line search with Polyak initial step size). While this isn't necessarily a problem in itself, as a result the technical novelty of the paper is not very high. 2. The theoretical results recover the previous convergence rate, but they do not exhibit any improvement over baselines. Recovering the previous convergence rates is natural and the proofs don't appear to contain any new techniques. Therefore, the theoretical contribution is not significant. 3. The main text contains no information about the tuning procedure for baselines or for the proposed algorithm, and the appendix contains very little information about hyperparameters. It's uncertain whether the experimental comparison is fair, and since the theoretical results do not exhibit improvement over baselines, the experimental performance is the only substantial contribution. Some previous baselines require additional hyperparameters (e.g. SPS with $\gamma$), but there is no assurance that this parameter was properly tuned. It is also difficult to see whether PoNoS was tuned more extensively than baselines, which would of course not be a fair comparison. 4. Evaluation for RBF kernel models and transformers does not compare by wall-clock time, and does not include results for test loss. Since PoNoS is competitive with Adam when measured by epochs, it is natural to assume that PoNoS lags behind Adam in terms of wall-clock time, which begs the question whether existing line search methods are useful for training Transformers. Line 344 says that only the training procedure is considered (following previous work), but this is not completely satisfying to me. If we compared test performance for MLPs, and CNNs, why not also for RBFs and Transformers?
Questions
1. Why is interpolation important to achieve the theoretical results? The introduction discusses interpolation in detail, but Section 4 only mentions interpolation as a condition for the theorems, and does not discuss why interpolation is necessary. Do previous line search methods also require interpolation to recover the same convergence rates? 2. How were the hyperparameters chosen? In particular, were all algorithms fairly tuned? 2. Why does PoNoS outperform other line search methods empirically when the theoretical guarantees of PoNoS do not improve over baselines? 3. How much do the two individual components of PoNoS (non-monotonicity and choice of initial step size) affect the performance? In particular, how would PoNoS perform if we used non-monotonicity with a classical initial step size? As a miscellaneous suggestion, please use lower resolution images for Figures 1-3, or if you're using a vector format please remove some data points. The provided PDF is unusually large and viewing the figures in Chrome's PDF viewer is quite slow.
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
3 good
Presentation
4 excellent
Contribution
2 fair
Limitations
The authors include some discussion of limitations and future work in the conclusion, though it would be nice to see some more discussion of the weaknesses of the proposed method instead of just directions for future work. Discussion of potential negative societal impact is, in my opinion, not necessary for this paper.
Summary
This paper presents a non-monotone line search method for optimizing over-parameterized models. The method is equipped with some theoretical support for strongly convex, convex and the PL condition. Furthermore, experimentally, the method is shown to have favorable performance when optimizing various deep learning models of practical interest. ==> post rebuttal: increased score from 4 to 5.
Strengths
Obtaining convergence results with non-monotone line search strategies appears to be a novel contribution - though, I don't know if some variant of this result has appeared in existing literature dealing with non-monotone line search.
Weaknesses
- The proposed approach seems incremental compared to existing approaches. - The theory doesn't adequately capture why the proposed method outperforms existing approaches. The bounds suggest identical convergence rates as ones that use monotone line search methods. This suggests all these bounds are fairly worst case (loose upper bounds) that do not help quantify why these methods work well in practice in the first place.
Questions
- In the theorem, particularly for the PL case, the degree of (non-) monotonicity that can be tolerated seems to be rather small (the permitted \zeta appears to be super small)? Can the authors clarify this? - The theorem for the strongly convex case doesn't appear to be particularly applicable in the over-parameterized case unless a regularized objective is being solved for, which doesn't reflect on how the behavior manifests on the loss function we truly care for. - Can the authors clarify why the proposed stepsizes tend to increase as a function of iterations? Is this related to using normalization layers (e.g. batch norm/layer norm) within the architectures? How do these stepsizes look like for convex case in the experiments conducted in the paper?
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
3 good
Presentation
3 good
Contribution
2 fair
Limitations
Yes.
Summary
This submission proposed a new linear search method to ensure convergence without the monotone decrease condition of the (mini-)batch objective function. The method is quite suitable for the modem DNN training, which prefers the larger training learning rate.
Strengths
- The explanation of motivation is very clear. - The related work has been extensively discussed.
Weaknesses
- Discussing the difference between the proposed and the previous methods is inadequate, especially since the existing methods inspire some steps. - The theoretical benefits of the proposed method are not shown/discussed in the convergence rate results. The proposed method seems to share a similar rate with the previous results. However, since PoNoS prefers a larger learning rate, its rate at least can demonstrate the advantage of a constant level. - There is no numerical comparison in the main part, and just having the curve figures cannot fully display the results.
Questions
- The experimental results are not entirely convincing. With the development of neural network training technology in recent years, the Adam optimizer can achieve better training losses than SGD in most cases. It is strange that SGD beat Adam constantly, especially on the transformer model for the NLP task.
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
2 fair
Presentation
2 fair
Contribution
3 good
Limitations
See weakness.
Summary
This paper proposes a new line search method for determining the step size in SGD within the interpolation regime. In contrast to the previous approach called SLS, which relies on the monotonically decreasing Amijo condition, the proposed method adopts the non-monotone Zhang & Hager line search. The authors establish the convergence guarantees for the proposed Stochastic Zhang & Hager line search when an upper bound is placed on the initial step size, considering strongly convex, convex, and PL problems. Additionally, they introduce several enhancements to improve empirical performance: (1) utilizing the Stochastic Polyak Step (SPS) to set the initial step size of the line search and (2) introducing a new resetting technique to reduce the number of backtracking steps.
Strengths
- Numerical experiments are extensive and the performance of PoNoS looks quite promising. It is great to see a provably convergent optimization algorithm (with other heuristics) working well in large-scale experiments while incurring only a minor computation overhead. - The proof techniques look new and interesting.
Weaknesses
- There are certain expressions within theorems that may lead to confusion. I have elaborated on these concerns in the "Questions" section of my review. - The Polyak step and the resetting technique are only heuristics. It would be valuable to provide further analysis regarding how these heuristics influence the convergence properties of the algorithm.
Questions
- While reading the main text, I was initially skeptical about Theorem 1 and 2 due to their requirement of Lipschitz continuity for function $f$. It has been shown that the bounded gradient assumption contradicts the strong convexity [1]. Upon reviewing the proof in the appendix, it seems that the Lipschitz continuity of $f$ may not be necessary for Theorem 1 and 2. Additionally, in Theorem 3, it is unclear why the smoothness of $f$ needs to be separately assumed given that $f_i$ is $L_i$-smooth. It would be helpful if the authors could provide clarification. - Furthermore, the notation "LC" used in Theorem 2 and 3 lacks a definition in the main text. The corresponding definition can be found in Appendix B. - In theory, how can you ensure that backtracking (Lines 10 - 12) halts in finite steps? [1] Nguyen, Lam, et al. "SGD and Hogwild! convergence without the bounded gradients assumption." International Conference on Machine Learning. ICML, 2018.
Rating
8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
N/A
Summary
The paper presents a proposed Polyak nonmonotone stochastic (PoNoS) method which combines a nonmonotone line search with a Polyak initial step size. It builds on the work of Vaswani et al. [2019] by modifying the monotone line search to incorporate a nonmonotone approach.
Strengths
Originality: The introduction of nonmonotone line search applied to Deep Learning is noteworthy. Clarity: The paper is generally well-written. However, the authors should emphasize their specific methodological innovation and contribution to the conclusion section to highlight the significance. Quality: The overall quality is good. The paper demonstrates the outperformance of the proposed methods over other methods in regard to runtime. Significance: The experiments show the advantages of the methods in terms of convergence speed and runtime when applied to Deep Learning.
Weaknesses
The authors admitted the adverse impact on convergence speed of the proposed method. This matter should be further investigated to have a more comprehensive intuition of the robustness of the method. Additionally, the authors should conduct a further comparison with the state-of-the-art line search approaches and the based model of Vaswani et al. [2019] ?a Figurethis
Questions
1. Lines 12-23 are about a reduction of the number of backtracks to zero. Can you specify which parts of the experiments to support the argument. 2. Did you have comparison with he based model of Vaswani et al. [2019]? 3. Can you explain further or provide intuition about the observation in lines 317-319? 4. In figure 4, data for SLS-prec, SPS-pre and PoNoS-pres seems to be missing. Do you have any reason for not to put the data?
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
2 fair
Limitations
The authors do address some of the limitations of their work.
Thank you for the response. I am keeping my current rating to champion this paper.
Thank you for your response, which cleared a few things up. There is slightly more theoretical contribution than I originally thought, and the discussion of the condition (*) clarified this contribution. However, I still believe that recovering the previous rate (as opposed to improving it) is a little unsatisfying. It is true that some papers, like Adam, only recover the previous rate in theory while improving the performance in practice. However, I don't think that the empirical results in this paper are enough to make up for the lack of theoretical improvement in the same way as e.g. Adam. The authors claim that the proposed algorithm is "the first stochastic nonmonotone line search method able to train neural networks efficiently while simultaneously achieving state-of-the-art generalization performance". I do not agree that PoNoS exhibits SOTA generalization performance, at least not for all tasks. The results in Figures 1-3 are good, but the main body contains no results on the test set for kernel models or transformers. The appendix does contain some test results for kernel models, but PoNoS does not outperform other methods. My biggest concern is that there are no test results for transformers anywhere, and without these results I don't believe the claim that PoNoS has SOTA generalization. With all of this in mind, the empirical improvement does not feel substantial enough to make up for the lack of theoretical improvement. I will keep my rating.
"However, I still believe that recovering the previous rate (as opposed to improving it) is a little unsatisfying. It is true that some papers, like Adam, only recover the previous rate in theory while improving the performance in practice." It is true that in an ideal world we would be able to prove a faster rate. However, the (almost 4 decades of) impressive practical performance of non-monotone methods have thus far resisted analysis. On the other hand, it is reassuring that we can still match the rate of SOTA methods like SLS and SPS. Note that Adam did *not* recover the previous rates in theory (the proof in the original Adam paper is obviously wrong). The same is true for other important practical methods like AdamW and cosine annealing which have become the most popular optimization algorithms in the field. These practical contributions inspired later theoretical works exploring how to justify their empirical performance. "However, I don't think that the empirical results in this paper are enough to make up for the lack of theoretical improvement in the same way" We are confused by this comment. Our experiments indicate that PoNoS is the same or better than a variety of existing methods, across a range of tasks and datasets (the reviewer also acknowledged the breadth of our experiments within the Strengths of our paper). All our evidence points to PoNoS being a method that is useful in practice. And they indicate that PoNoS is particularly effective for CNNs, one of the most important model classes in computer vision. Our experiments are more extensive than most empirical works presenting new optimization algorithms, with most empirically-motivated methods only first showing success on a small-but-important class of problems (the AdamW paper with >10,000 citations only presented results on CIFAR-10 and downscaled ImageNet datasets). "The appendix does contain some test results for kernel models, but PoNoS does not outperform other methods" In these settings PoNoS outperformed the other methods on one dataset while matching SOTA performance on the other 3. This is in contrast to Adam, for example, which can perform poorly on convex problems [Reddi et al., 2018]. We should not expect any method to strictly outperform all other methods in every scenario. "My biggest concern is that there are no test results for transformers anywhere, and without these results I don't believe the claim that PoNoS has SOTA generalization." In the transformer experiments, all methods achieve the same test error while methods that decreased the training error faster achieve this error faster. We will update the paper to include these results.
Re. author response
Thanks to the authors for their clarifications. I will increase my score to a 5. My comment about the loss function was that even if we solve the regularized loss, the eventual loss that we care about is the one without regularization, so the rates of convergence to the regularized loss don't really matter all that much. Nevertheless, thanks your response.
Thank you for answering the questions.
Decision
Accept (poster)