- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper studies gradient descent (GD) with a large constant step size () in the edge of stability (EOS) regime, where the loss can oscillate before it becomes monotonically non-increasing. The first time at which this happens was shown to be in the previous work. This work aims to address the question whether the step-size dependence is necessary. Specifically, it shows that the transition time grows with the step size as in the limit where , where and are the number of data points and the feature dimension, respectively. Thus, it provides an upper bound on the transition time together with a matching lower bound. When , the transition time is independent of the step size, agreeing with the previous analysis. However, for high dimensions, this generally does not hold, and this work provides a precise quantification.
Critical strengths
The results of this work are novel. It disproves the conjecture from Crawshaw & Liu, 2026 for high dimensional data, by showing that the transition time depends polylogerithmic on the step size (with the exponent being ). The analysis techniques are new and different from the previous approach in Wu et al., 2024. Building upon the transition time characterization, the paper further introduces a step size that is exponential in the total number of iterations (), and show the loss decreases exponentially fast with such step size. Overall, it is a nice addition to the line of works on the dynamics of GD on the logistic loss with separable data.
Crawshaw $ Liu, Tight Bounds for Logistic Regression with Large Stepsize Gradient Descent in Low Dimension
Wu et al., Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiency
Critical weaknesses
This paper does not have any numerical validations on its theoretical claims. This is my main concern. It is unclear to me how well the proposed step size performs in practice.
Questions for authors
In Theorem 1, what is the specific form of ? How the constants hidden in the Big- notation depend on and ?
3 comments
Thank you for your response. I will maintain my score.
Thank you!
We sincerely thank you for your supportive feedback! Thanks again for your insightful comments which helps us improve our paper.
Clarifications
We sincerely appreciate your helpful and constructive advice. We also appreciate your recognition of the novelty of our results and analysis techniques, as well as the improved optimization guarantees. We understand that your main concerns are around whether the theoretical predictions are supported by numerical evidence and whether the proposed stepsize helps at finite horizons. Appendix I of the current manuscript now includes certified construction trajectories and comparisons on fixed synthetic data, where the larger stepsize helps in some settings and hurts in others. We have also made the margins, bound coefficients, and both stepsize thresholds explicit in Appendices H.2-H.4 and H.7.
We have added numerical validation in Appendix I of the current manuscript, including full GD from zero on the lower constructions for n=d=3,4. The 18 benchmark instances show late strict loss increases and transition-time curves consistent with logη and (logη)2 over the tested ranges. Their explicit rational realizations have interval certificates for the loss comparisons and transition times. These construction experiments use large stepsizes; they validate finite instances of the worst-case behavior, rather than practical tuning performance.
Appendix I.3 reports comparisons on fixed datasets across three margins, two exponential prefactors, and multiple horizons: 210 trajectories, each checked at 100 and 200 digits. With n=32,d=4 and 10 seeds per setting, median log10 losses at T=200 were:
The larger stepsize can hurt at small margin and short horizon. At margin 0.02 and T=1000, it improves loss on all 10 datasets. The prefactors are empirical, so these synthetic-data comparisons do not establish a universal tuning rule.
During the rebuttal, we have also strengthened Corollary 3 in the current manuscript. For every 0<γ≤1, k=minn−2,d−2≥1, and the explicit choices a,b>0 in Appendix H.6, choosing η(T)=maxbT,exp(aT1/k) gives
F(wT)≤C(n,γ)min{T−2,T−1exp(−aT1/k)}
for sufficiently large T. Each selected branch leaves at least half the horizon for stable descent. Appendix H.6 gives explicit constants and a sufficient horizon, which can be large.
Theorem 1 now displays the margin threshold, lower coefficient, and both sufficient stepsize thresholds; Appendix H.2 gives Cup, and Appendices H.3-H.4 give the margin and lower-coefficient derivations in the current manuscript. A sufficient choice is γn=1/[642(n−1)]. For k≥1, set m=k+1 and ρ=1/(82m) in Appendix E.5. The spectral bounds on K give auxiliary margin at least 1/(642m), and the setup margin exceeds 1/4 for sufficiently large η. Since m≤n−1, the claim follows; k=0 is also covered. Direct calculations sharpen the small-n choices to γ3=1/(410) and γ4=1/20 for sufficiently large η. The explicit ηlow(n) below is stated for the general margin range, not these enlarged small-n ranges.
For every 0<γ≤1 and η≥22n+12n3/γ4, a sufficient upper coefficient is
H=3+\frac{32}{x}+\frac{2}{x}\log_+\!\left(\frac{32}{9ex}\right),\qquad C_{\mathrm{up}}=\frac{8n}{\gamma^2} +\left(\frac{8n}{\gamma^2}+1+\frac{16}{\gamma^4}\right) H\sum_{j=0}^{n-2}Q^j,$$ where $\log_+(u)=\max\{0,\log u\}$. Appendix H.2 derives this from the recursion in D.1 and the block counts in D.2. For $\gamma\le\gamma_n$, a sufficient lower coefficient is $c_{\mathrm{low}}(n)=2^{-4n^2}$, independent of $\gamma$ and ambient dimension. Under our assumptions, we here additionally prove the sufficient lower-bound threshold, valid for $0<\gamma\le 1/[64\sqrt{2}(n-1)]$, $$\eta_{\mathrm{low}}(n)=128n(n-1)\exp\!\left(2^{3200n^2 16^{n-2}}\right).$$ We have added its quantitative proof in Appendix H.7 of the current manuscript. Both thresholds are conservative sufficient bounds, rather than minimal requirements or practical tuning rules. We appreciate this suggestion, which helped us make the parameter dependence explicit and enhance the manuscript. We thank you again for your thoughtful and constructive comments, which have helped us strengthen this work. We would be happy to provide any further clarification to assist your evaluation.