Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: # === Update === #

I appreciate the thorough response to my review provided by the authors. I have looked through the newest version of the submission and find it to be much improved. The inclusion of repeats for the train loss / test accuracy comparison is great to see and the updated figures are mostly fixed. The experiments now make a meaningful argument for Eigencurve as a (non)-convex optimization method.

I have increased my score to 6 to reflect the improvements and the author response. 

# ====== #

This submission proposes a new step-size schedule for stochastic gradient descent which leverages the eigenvalue spectrum of Hessian to speed-up convergence. 
The approach, dubbed Eigencurve, is shown to achieve the minimax optimal convergence rate for stochastic gradient descent on quadratic functions under an additional condition that the eigenspectrum of the Hessian decays according to a power law.
When this decay condition is not satisfied, Eigencurve still improves upon the popular step-decay schedule; in this case, it is sub-optimal by a factor of $\\log(\\kappa)$ rather than the $\\log(T)$ factor of step-decay.
A lower bound is also provided verifying that the $\\log(T)$ sub-optimality of step-decay is tight and cannot be improved for quadratics.
The submission concludes with an empirical investigation of Eigencurve for (non-convex) optimization of several popular neural network architectures on the CIFAR-10 and ImageNet datasets.
main_review: ## Writing

The quality of the writing is generally good.
Some sections have grammatical issues (see "Minor Comments" for a few examples), but these could be easily corrected by carefully proof-reading the draft. 

## Theory

**Correctness**: I checked all of the theoretical derivations in the Appendix and believe them to be sound.
Some of the proofs are fairly dense and written with complex notation, so it possible that I missed a mistake. 
With that said, I commend the authors on their attention to detail in the appendices.

**Novelty**: I believe the theoretical contributions to be novel.
While nice, the improvement in convergence rate of step-decay from a $\\log(T)$ to $\\log(\\kappa)$ factor is does not seem like a major contribution.
For instance, depending on $\\kappa$ and $T$, it is still possible for step-decay to have a faster theoretical rate of convergence than Eigencurve.

Eigencurve does attain the idea minimax complexity for SGD on convex quadratics when the "power power law" condition holds.
However, it is not clear that this means Eigencurve is optimal in a rigorous sense.
Is Eigencurve minimax optimal for the restricted class of quadratic problems satisfying the power power law? 
This restricted class may be "easier" than the set of all quadratic functions due to clustering of the eigenvalues.
It seems to me that a lower bound for this class is necessary for the claim that Eigencurve is optimal to be accurate, since it is clearly not minimax optimal for the full class of quadratics.

Eigencurve also requires knowledge of the complete eigenvalue spectrum. 
In general, computing this spectrum is as computationally intensive as minimizing the quadratic objective in the first place.
It isn't clear from the theoretical analysis if Eigencurve is robust to miss-estimation of the eigenvalues.
For tractability, extensions to approximate estimation of the spectrum or perhaps partial (e.g. only the top $n$ eigenvalues) spectra are attractive, but maybe hard to prove.
Given this issue, I think many practitioners will be content with step-decay. 

Finally, it is not at all clear to me how to apply Eigencurve to non-quadratic optimization problems. 
The discussion in the Appendix notes that, for non-convex optimization, an approximation of the Hessian at an approximate first-order critical point is used to compute the eigenvalue spectrum. 
Why does this choice make sense?
Firstly, the FO point may be a saddle and the Hessian will be indefinite. 
In this case, why is using the magnitude of the spectrum justified? 
Secondly, why should the Hessian at a FO point be a good descriptor of the global function curvature? 
The eigenvalues around a stationary point can be arbitrarily scaled for non-convex, non-smooth, non-Lipschitz models like neural networks [1].
I think these choices must be justified more carefully than they are in the submission.


## Experiments

The experimental evaluation in the submission is not ready for publication.

The first issue is that nearly all figures in the paper are illegible
For example, the labels for Figures 3, 4, and 5 are barely visible when reading the paper at a normal zoom-level. 
Moreover, the columns and rows of Figure 4 are not labeled, meaning that the figure is still difficult to interpret when zoomed-in.
Note that the additional experiments in the appendix suffer from these same problems. 
I don't think that figures need to be perfect at submission time, but they must be legible. 

Another major issue of the evaluation is that there do not appear to be any repeats over random seed.
I searched Appendix B.1 where the experimental experimental methodology is given and did not find any mention of repetitions. 
Moreover, distribution is not reported in any figure or table in the submission.
When evaluating stochastic optimization methods, it is absolutely essential that multiple repetitions be performed and distribution information included with the experimental results. 
This is necessary for readers to judge whether or not results are a meaningful trend or a low-probability outcome.
For example, table 2 is just not meaningful without standard deviations or inter-quartile range.

Finally, there is a problem of fairness in the comparison to step-decay. 
The authors report in Appendix B.1 that they use the "common settings" for step-decay on CIFAR-10/100. 
No reference is provided to justify that the given settings are standard.
Moreover, the authors report that estimating the eigenvalue spectrum requires 1-2 days, which is an order of magnitude more time than required to train a single model. 
This gives Eigencurve a huge advantage in computational budget over step-decay.
To be fair, I think a similar (or least substantial) attempt must be made to tune the parameters of step-decay.


## Minor Comments

- Remark 1: "coordinately" -> "coordinate-wise".
- Line after Eq. 1.7: In fact, no real justification or explanation of this assumption is given in Appendix G.5. The only comment made there is that previous work also make the same assumption.
- (Page 3) "Moreover, in practice, $\\kappa$ can be very big for large neural networks": (i) this remark requires some justification, (ii) to be picky, $\\kappa$ is not defined for neural networks because they are non-convex and typically non-smooth.
- Proposition 1: The proof of proposition 1 is not given in Lemma 15 as stated in the text. Instead, it is given in Appendix E on page 22. 
- Page 12: what is $\\beta$? I don't see a description of this parameter in Eq. 3.3. Edit: I see that this is defined in Appendix B.1 *after* it is first used.
- Figure 6: It looks like the Largest eigenvalue is not within the bounds of the left-hand plot (log-scale).
- Appendix A.1: what is the batch size for this experiment? I don't see it reported anywhere.
- Page 20: I don't understand why the GPU memory limit prevents you from using multiple batches to estimate the Hessian spectrum. Isn't that the point of using batching in the first place?
- Page 20: There is no guarantee that the optimizer converges to a local minimum. It may converge to a saddle-point, resulting in the negative eigenvalues.
- Appendix B.4: This is not correct. The README.md of the indicated repository explicitly states "the CIFAR-10 are not my property. If used in a paper, you'll need to cite the reference paper, as indicated in the official website."
- Appendix C: Again, referencing a GitHub repository for code using ImageNet doesn't mean that the ImageNet dataset is distributed under the same license  as that repo.
    Licensing rules for ImageNet are given here: https://www.image-net.org/download.
- Appendix G.1: Use the restatable environment from thmtools (https://ctan.org/pkg/thmtools?lang=en) to avoid creating a new Lemma (i.e. Lemma 15) when proving Lemma 1. 

## References:

[1] Dinh, Laurent, et al. "Sharp minima can generalize for deep nets." International Conference on Machine Learning. PMLR, 2017.
summary_of_the_review: 
This is an interesting submission with a very novel (at least, to my knowledge) approach to choosing the step-size for SGD.
Effective step-size selection for stochastic optimizers is a challenging problem with potential for great impact on current machine learning practice. 
As such, I think this work is a good fit for ICLR.
Theoretically, the submission is sound and I enjoyed reviewing the theoretical arguments (see "Theory" below).
However, empirically, the work is weak and, in my opinion, essentially unfinished. 
I found the decision to focus the experiments on heuristic extensions of Eigencurve to non-convex optimization to be strange, given the theory does not even apply to general convex functions.
The majority of figures are completely unreadable and all results are reported without distribution information; it is to judge the significance of the experiments as a result. 
See "Experiments" for more details.

Although interesting, I recommend that the submission be rejected given the unfinished state of the empirical evaluation.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the convergence of SGD with different learning rate schedules and aims to achieve minimax optimal convergence rates on quadratic objectives. To this end, this work proposes a new learning rate schedule (named Eigencurve) based on the Hessian spectrum and provides an optimal last-iterate convergence rate.
The proposed Eigencurve gives rise to slightly improved performance on image classification tasks with deep neural networks. In addition, the introduced schedule is similar to the popular cosine learning rate schedule on some problems, which, to some extent, justifies the effectiveness of the cosine schedule.
main_review: Overall, the paper is easy to follow and well-motivated. 

Strengths:
- The derived learning rate schedule is theoretically sound and the intuition is well-conveyed. It also provides some justifications for the effectiveness of the cosine decay schedule.

Weaknesses:
- In terms of optimal learning rate schedule for convex-quadratics, it was previously discussed in [1] with a noisy quadratic model. In particular, [1] directly optimized the schedule as they can compute the exact loss using dynamic programming. In principle, one can get an optimal (or near-optimal) learning rate schedule in this model by plugging the Hessian spectrum, then use it to train neural networks. Given that, some discussions or comparisons would be valuable in the main paper.
- The derived theoretical results are all about asymptotic convergence. To be honest, I’m not sure how relevant that would be. Of course, it is an interesting contribution from a theoretical perspective. But in practice, we train neural networks with fixed epochs and I would expect the learning rate schedule to depend on the gradient noise level $\sigma$. It seems that the proposed schedule is independent of $\sigma$. I think the authors might like to add some discussions on that.
- As the authors mentioned in the paper, Polyak averaging is optimal for convex quadratics but is unable to handle nonconvex landscapes in practice. However, I believe the exponential moving averaging method is commonly used for training neural networks, so I encourage the authors to include the comparison with the exponential moving average.
- The 10-epoch results are a bit artificial. With only 10 epochs, it makes little sense to decay the learning rates twice for the step-decay schedule. It seems that the authors used different parameters (e.g. \beta) for the 10-epoch setting. Although the authors argue that \beta is not a hyperparameter, but it is obvious to me that the value of 1.000005 is carefully tuned. Could the authors justify this particular choice?
Overall, the improvement of using the proposed Eigencurve is marginal on image classification tasks, though this is understandable as the step-decay and cosine-decay schedules are very strong baselines.

Minor points:
- The authors could save a lot of space by reorganizing all the figures in Figure 4. And with the saved space, I suggest the authors to include the details of hyperparameter tuning in the main paper.


[1] Which Algorithmic Choices Matter at Which Batch Sizes? Insights From a Noisy Quadratic Model. NeurIPS 2019.
summary_of_the_review: The paper proposed an interesting learning rate schedule that achieves an optimal asymptotic rate on strongly-convex quadratics. However, the schedule relies on first computing the Hessian spectrum and the empirical improvement is not significant. 

Overall, this is a borderline paper and I'm inclined to reject the paper (though I'm willing to increase my score if the authors can address my comments).
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies convergence rates of SGD with different stepsize schemes, in the context of linear regression. For convergence of the last iterate of SGD, the best known result still misses a $\\log T$ factor compared to the minimax rate. This work aims to fill this gap with an improved stepsize scheme that utilizes the eigenvalue distribution of the Hessian. When the true Hessian is known, the proposed method successfully fills the gap, provably and in the sense of the worst problem instances. When the true Hessian is hard to know, practical variants are also proposed, and are shown to be comparable to the state-of-the-art stepsize schemes in standard deep neural network benchmarks.
main_review: # Pros
+ The paper is pretty clear written. 
+ Related literature from the SGD side is well explained.


# Cons
- I am not sure how interesting it is to embed Hessian information into the SGD stepsize design. The stepsize in Prop 1 is nothing but Newton's method in my perspective, which should be counted as a second order method, and it is unfair comparing this to SGD as a first order method. 
- Therefore, the authors should explain the difference between the proposed method with Newton's method, and cite/compare with related works from (stochastic) Newton's method.
- More importantly, the empirical gain of using second order information is, in my perspective, marginal (see e.g., Table 2)...  which can hardly justify the extra cost of obtaining the Hessian information.
- The following comments are from the theory side ---- first of all, I would not say this paper contributes novel techniques or surprising results based on my knowledge of SGD literature; therefore I would not consider the presented theory as a sufficient contribution to justify the value of this work. Please correct me if important points are missing here.
- Prop 2 is only an upper bound for poly-decay stepsize, and this along cannot support the claim that poly-decay is sub-optimal. As least a minimax-lower bound is required. For such lower bounds of poly-decay stepsize, [Ge 2019] already presented a minimax version, and a more recent work [Wu 2021] has an instance-dependent lower bound. The authors should use a lower bound here & clearly cite existing results in their next verison.
- I am not sure how useful it is to compare the minimax rate. The authors want to claim one stepsize scheme is better than another. However the argued gain only happens in the worst case, while in benign instances, it is unknown whether or not the proposed stepsize scheme can have benefits. Perhaps conduct a instance-dependent analysis, and show a (nearly) instance-wise domination of one stepsize scheme over the other is more appealing. 
- Even let us assume there are truly someone cares about minimax rates, I doubt the importance of removing a logarithmic factor... 
- A final comment is that, comparing upper bound to upper bound simply cannot prove the benefit of one method over the other. The gain could be a loose analysis. A lower bound is needed to demonstrate the tightness of the analysis.





[Ge 2019] Ge, Rong, et al. "The step decay schedule: A near optimal, geometrically decaying learning rate procedure for least squares." arXiv preprint arXiv:1904.12838 (2019).

[Wu 2021] Wu, Jingfeng, et al. "Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regression." arXiv preprint arXiv:2110.06198 (2021).
summary_of_the_review: I think the paper is clearly below the bar of acceptance. From the theory side, many points are not well supported (e.g., comparing upper bound to upper bound, comparing the minimax rate, etc.) and little technical novelty can be found. From the practice side, the improvement is too small to justify the cost of computing second order information.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors propose Eigencurve, a new approach to learning rate scheduling that utilizes information form the eigenvalues of the Hessian. They show that this scheduler obtains the minimax optimal rate on the noisy quadratic problem. Empirically, this scheduler demonstrates faster convergence on CIFAR-10 and ImageNet, especially when the number of epochs is small.
main_review: Strengths 
- Eigencurve is proved to achieve the optimal convergence rate when the eigenvalue distribution is skewed. It does no worse than step decay generally.
- In the appendix, eigencurve is verified on ridge regression setting where the exact Hessian is known. This helps validate the correctness of the theory.
- The empirical results are strong on CIFAR-10 and CIFAR-100. The authors verify that the loss surface is well approximated by quadratics. They show lower training loss and improved validation performance.
- Paper is clearly written and easy to follow.


Weaknesses
- There is no theory analyzing the non-asymptotic case.
- One concern I have with this method is the computational cost. This is somewhat mitigated by experiments in the appendix demonstrating that the distribution of eigenvalues of the Hessian can be re-used across different models on CIFAR-10.  Other learning rate scheduler have little to no additional overhead. Perhaps it would be useful to report the wall clock time of compute the eigenvalues + training.
- The results on ImageNet appear to be less strong than those on CIFAR and they are not emphasized in the main text. I am a bit concerned that the learning rate scheduler offers limited improvement in the standard training regime (200 epochs on CIFAR and ~100 on ImageNet).
- The experiments are on image classification datasets. Extending these results to other domains, such as language modelling, would improve the significance of the work.

Minor
- In the appendix, it's unclear what the extra term is. Adding a sentence to two would make things more clear.

----
### Post-rebuttal
I'm increasing my score to an 8. Small note is that I believe step decay applied on ImageNet typically decays at epoch 30, 60, and 80 (e.g. Goyal, Priya, et al. "Accurate, large minibatch sgd: Training imagenet in 1 hour."), so it'd be best to compare to that as a baseline.
summary_of_the_review: Overall this paper offers an interesting perspective and approach to learning rate scheduling on an existing quadratic setting that shows practical implications in image classification. The experiments are thorough (including various ablations in the appendix) and validate the improved performance from the approach, especially when the number of epochs is limited.
review_title: null

Meta-review: The paper proposes a method to learning rate scheduling that uses information form the eigenvalues of the Hessian. It shows that this scheduler obtains the minimax optimal rate on the noisy quadratic problem; and, empirically, this scheduler demonstrates faster convergence on CIFAR-10 and ImageNet, when the number of epochs is small.  Using Hessian information in direct and indirect ways is of interest to the community, and the paper does a nice job illustrating that in a context of interest.
Decision: Accept (Poster)