acceptodds
Under review as a conference paper at ICLR 2027

Tight Transition Time Bounds for Separable Logistic Regression at the Edge of Stability

Abstract

We study logistic regression on linearly separable data under gradient descent with a large constant stepsize . Such dynamics may exhibit a characteristic Edge of Stability phenomenon, in which the loss initially oscillates before transitioning to a stable phase of monotone decrease. Existing work provides a tight bound in dimension as and conjectures a bound independent of in arbitrary dimensions . In this paper, we disprove this conjecture by showing that, for every fixed sample size and sufficiently small margin , the worst-case transition time is uniformly over . The key challenge in establishing a tight bound is that the sample contributing most strongly to the gradient can change repeatedly across iterations. To address this issue, we control such changes by induction on dimension and sample size, and construct matching hard instances.

Primary area:
learning theory
Keywords:
Logistic Regression, Large Stepsize, Edge of Stability

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_NuaJOpenReview ↗
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 (η\eta) 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 O(η)O(\eta) 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 Θ((log⁡η)min⁡(n−2,d−2))\Theta((\log \eta)^{\min ( n-2, d-2 )}) in the limit where η→∞\eta \rightarrow \infty, where nn and dd 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 d=2d = 2, 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 min⁡(n−2,d−2)\min( n-2, d - 2)). 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 (TT), 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 γn\gamma_n? How the constants hidden in the Big-Θ\Theta notation depend on nn and γ\gamma?

3 comments
AuthorsOpenReview ↗

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.

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. (Weakness 1)

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,4n=d=3,4. The 18 benchmark instances show late strict loss increases and transition-time curves consistent with log⁡η\log\eta and (log⁡η)2(\log\eta)^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=4n=32,d=4 and 10 seeds per setting, median log⁡10\log_{10} losses at T=200T=200 were:

Marginη=T\eta=Tη=max⁡{T,exp⁡(0.5T)}\eta=\max\{T,\exp(0.5\sqrt{T})\}
0.020.020.4520.4521.1401.140
0.050.05−4.229-4.229−8.545-8.545
0.100.10−4.427-4.427−13.379-13.379

The larger stepsize can hurt at small margin and short horizon. At margin 0.02 and T=1000T=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<γ≤10<\gamma\le1, k=min⁡n−2,d−2≥1k=\min\\{n-2,d-2\\}\ge1, and the explicit choices a,b>0a,b>0 in Appendix H.6, choosing η(T)=max⁡bT,exp⁡(aT1/k)\eta(T)=\max\\{bT,\exp(aT^{1/k})\\} gives

F(wT)≤C(n,γ)min⁡{T−2,T−1exp⁡(−aT1/k)}F(w_T)\le C(n,\gamma)\min\{T^{-2},T^{-1}\exp(-aT^{1/k})\}

for sufficiently large TT. 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.

In Theorem 1, what is the specific form of γn\gamma_n? How the constants hidden in the Big-Θ\Theta notation depend on nn and γ\gamma? (Question 1)

Theorem 1 now displays the margin threshold, lower coefficient, and both sufficient stepsize thresholds; Appendix H.2 gives CupC_{\mathrm{up}}, 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)]\gamma_n=1/[64\sqrt{2}(n-1)]. For k≥1k\ge1, set m=k+1m=k+1 and ρ=1/(82m)\rho=1/(8\sqrt{2m}) in Appendix E.5. The spectral bounds on KK give auxiliary margin at least 1/(642m)1/(64\sqrt{2}m), and the setup margin exceeds 1/41/4 for sufficiently large η\eta. Since m≤n−1m\le n-1, the claim follows; k=0k=0 is also covered. Direct calculations sharpen the small-nn choices to γ3=1/(410)\gamma_3=1/(4\sqrt{10}) and γ4=1/20\gamma_4=1/20 for sufficiently large η\eta. The explicit ηlow(n)\eta_{\mathrm{low}}(n) below is stated for the general margin range, not these enlarged small-nn ranges.

For every 0<γ≤10<\gamma\le1 and η≥22n+12n3/γ4\eta\ge2^{2n+12}n^3/\gamma^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.

Thank you for your response. I will maintain my score.

AuthorsOpenReview ↗

Thank you!

We sincerely thank you for your supportive feedback! Thanks again for your insightful comments which helps us improve our paper.

Reviewer_nVuROpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper continues a line of work from Wu et al (2024) and Crawshaw and Liu (2026): together those papers show that with a separable dataset, logistic regression with step-size eta has loss O(1/eta) after O(eta) steps in arbitrary dimensions and O(1) steps in dimension 2, and then decreases monotonically (as O(1/(eta t))) after that. This implies faster than classical rates for convex GD. The current paper shows that, if the data has rank r, the small loss condition is satisfied after O((log eta)^r) steps and constructs rank r data for which the monotone decrease cannot happen any earlier.

I knew of these results before seeing this paper - a collaborator and chatGPT obtained exactly these upper and lower bounds in one weekend about two months ago. A few months ago, I would have been very excited to see this advance. But now it seems to be an example of what AI can do with a clearly-stated conjecture and lots of relevant background tools.

I am somewhat ambivalent. On the one hand, it tidies up an earlier line of work that I find very interesting. On the other, a weekend's work isn't what I'd like to see as a conference-level contribution now that we have such capable tools. And with the presentation quirks that AI provides and this paper's authors have not removed, I'm disappointed in the level of effort that's gone into the exposition. So I'd like to see the results published. But I'd also like to see authors put more effort into understanding and shaping the proofs that AI provides.

Critical strengths

The paper resolves the question of the large-step-size asymptotics of logistic regression.

Critical weaknesses

First, it would be worth acknowledging that these are very asymptotic results. Wu et al showed that tau_eta(D) = O(\eta). The new upper bound (c+log eta)^r is better only once eta is exponential in r, the rank of the data. And Corollary 3 improves on the O(1/T^2) asymptotics, but it shows that F(w_T) can be smaller than constant/T only when T is exponential in r. In that vein, it would also be worth improving Corollary 3 by setting eta = \Theta(max(T, exp(aT^{1/r}))) so that F(w_T) = O(min(1/T^2,exp(-aT^{1/r})/T)).

Presentation issues:

Stating the counterexample to the conjecture of Crawshaw and Liu as a corollary of Theorem 1 is very strange. The main thm in (Wu et al, 2024) showed that the upper bound on F(w_t) in the definition of tau_eta(D) implies that F decreases monotonically after that, that is, sigma_eta(D)\le tau_eta(D). So it's immediate from Thm 1 that tau_\eta cannot be independent of eta. On the other hand, Corollary 2 provides something additional (the upper bound on tau_eta), that is in no way a corollary of Theorem 1. The explanation in the introduction (after 'First, it disproves...') is the kind of triviality that should be filtered out of the AI's output.

The same strangely oblivious viewpoint appears in the proof sketch of Corollary 2 on p5: "The stability estimate in Appendix B guarantees permanent monotonicity once F(w_t) \le 2/eta, so sigma_eta(D) \le tau_eta(D)." It's common to see AI output that is strangely focused on trivialities, and this seems to be an example that the authors didn't filter out. "The stability estimate in Appendix B" is part of Thm 1 in (Wu et al, 2024) (and later quoted as Lemma 4). And in Appendix B.1: why include a proof of Lemma 4, without any explanation, after the statement of Lemma 4 acknowledges that the lemma is quoted from Wu et al?

At a high level, the results of the paper are proved in two parts: an upper bound on tau_eta(D) and a matching lower bound on sigma_eta(D). It should be written that way in the main paper. (Writing it as a theorem with upper and lower bounds on sigma_eta and a corollary with upper and lower bounds on tau_eta is weird and misleading.)

The proof of the upper bound is written in a messy style (again, consistent with AI generation). C.1 gives an inductive argument that sequences satisfying a set of conditions cannot be too long in terms of parameters of those conditions. And C.2 applies it to the logistic regression updates. The interface between these two parts of the proof is huge (most of page 16). So confirming that C.2 actually appeals to the implicit lemma that's proved in C.1 is a lot of work. I'm surprised that the authors went to that trouble and didn't bother to write the conclusions of C.1 as an explicit, precise lemma.

Questions for authors

n/a

4 comments
AuthorsOpenReview ↗

Clarifications (1)

We sincerely appreciate your helpful and supportive advice. We also appreciate your recognition that our results resolve the question of large-stepsize asymptotics for logistic regression. We understand that your main concerns are around whether the asymptotic bounds offer improvements at finite stepsizes and whether the contribution and proof structure are clearly presented. In the current manuscript, we have acknowledged the potentially large crossover, strengthened Corollary 3 to retain the O(T−2)O(T^{-2}) guarantee, separated the upper- and lower-bound statements, and clarified the proof structure.

First, it would be worth acknowledging that these are very asymptotic results. Wu et al showed that τη(D)=O(η)\tau_\eta(D)=O(\eta). The new upper bound (c+log⁡η)r(c+\log\eta)^r is better only once η\eta is exponential in rr, the rank of the data. (Weakness 1)

We agree that the crossover can be large. The rank-dependent exponent is max⁡r−2,0\max\\{r-2,0\\}, with worst-case value k=min⁡n−2,d−2k=\min\\{n-2,d-2\\}. The threshold ηup=22n+12n3/γ4\eta_{\mathrm{up}}=2^{2n+12}n^3/\gamma^4 guarantees validity of the upper bound with coefficient Cup(n,γ)C_{\mathrm{up}}(n,\gamma); it does not by itself locate the crossover with the linear bound. Although the sufficient thresholds can be very large, they do not affect the matching asymptotic order for fixed nn and 0<γ≤γn0<\gamma\le\gamma_n as η\eta tends to infinity. We have clarified these points in Sections 3.2-3.3 and Appendix H.6 of the current manuscript; no improvement at moderate stepsizes or horizons is guaranteed.

In that vein, it would also be worth improving Corollary 3 by setting η=Θ(max⁡{T,exp⁡(aT1/r)})\eta=\Theta(\max\{T,\exp(aT^{1/r})\}) so that ... (Weakness 1)

Under our assumptions, we here additionally prove that your proposed modification yields the combined guarantee below. For every 0<γ≤10<\gamma\le1 and k≥1k\ge1, choose η(T)=max⁡bT,exp⁡(aT1/k)\eta(T)=\max\\{bT,\exp(aT^{1/k})\\}, b=3γ2256b=\frac{3\gamma^2}{256}, a=min⁡{1,12n−1Cup(n,γ)}.a=\min\{1,\frac{1}{2^{n-1}C_{\mathrm{up}}(n,\gamma)}\}. For sufficiently large TT,

F(wT)≤C(n,γ)min⁡T−2,T−1exp⁡(−aT1/k).F(w_T)\le C(n,\gamma)\min\\{T^{-2},T^{-1}\exp(-aT^{1/k})\\}.

On the linear branch, the coefficient-mass bounds give τη≤64η/(3γ2)≤T/4\tau_\eta\le64\eta/(3\gamma^2)\le T/4. On the exponential branch, the polylogarithmic bound gives τη≤T/2\tau_\eta\le T/2. The stable-phase decay estimate then yields F(wT)≤128/(15γ2ηT)F(w_T)\le128/(15\gamma^2\eta T). Thus the log-free T−2T^{-2} term follows from our coefficient-mass and stable-phase estimates. We have incorporated this guarantee into Corollary 3 of the current manuscript, with explicit constants and the transition-time argument in Appendix H.6 and the loss bound in Appendix G.2. No monotonicity of τη\tau_\eta in η\eta is assumed. We appreciate this suggestion, which helped us enhance the manuscript.

Corollary 2 provides something additional (the upper bound on τη\tau_\eta), that is in no way a corollary of Theorem 1. [...] At a high level, the results of the paper are proved in two parts: an upper bound on τη(D)\tau_\eta(D) and a matching lower bound on ση(D)\sigma_\eta(D). It should be written that way in the main paper. (Presentation issues 1 and 3)

We originally stated the result for τη\tau_\eta separately to make it easier to compare with prior threshold-time bounds. Following your suggestion, we have reorganized Theorem 1 in the current manuscript to state the upper bound on τη(D)\tau_\eta(D) and the matching lower bound on ση(D)\sigma_\eta(D) directly:

Upper:

τη(D)≤Cup(n,γ)(1+log⁡η)max⁡{r−2,0}\tau_\eta(D)\le C_{\mathrm{up}}(n,\gamma)(1+\log\eta)^{\max\{r-2,0\}}

for every admissible DD, every 0<γ≤10<\gamma\le1, and η≥ηup\eta\ge\eta_{\mathrm{up}};

Lower: for 0<γ≤γn0<\gamma\le\gamma_n and η≥ηlow(n)\eta\ge\eta_{\mathrm{low}}(n), some DηD_\eta satisfies

ση(Dη)≥clow(n)(1+log⁡η)k.\sigma_\eta(D_\eta)\ge c_{\mathrm{low}}(n)(1+\log\eta)^k.

Here γn=1/[642(n−1)]\gamma_n=1/[64\sqrt{2}(n-1)] and clow(n)=2−4n2c_{\mathrm{low}}(n)=2^{-4n^2}. Theorem 1 now displays both sufficient stepsize thresholds explicitly, with the lower-threshold proof in Appendix H.7. For 0<γ≤γn0<\gamma\le\gamma_n, the known inequality ση≤τη\sigma_\eta\le\tau_\eta then gives matching worst-case orders. The upper bound on τη\tau_\eta is proved independently in Appendix D and is now included in Theorem 1, making Corollary 2 a direct consequence. We have also removed the repeated statement about the uniform conjecture.

AuthorsOpenReview ↗

Clarifications (2)

"The stability estimate in Appendix B" is part of Thm 1 in (Wu et al, 2024) (and later quoted as Lemma 4). And in Appendix B.1: why include a proof of Lemma 4, without any explanation, after the statement of Lemma 4 acknowledges that the lemma is quoted from Wu et al? (Presentation issue 2)

We agree that this result should be explicitly attributed to prior work: our Lemma 4 is Lemma 10 of Wu et al. (2024). In the current manuscript, we have cited this result directly in Section 4.1, removed the redundant stability proof sketch, and explained in Appendix C.1 that the recalled proof is included for completeness. We present neither this stability result nor ση≤τη\sigma_\eta\le\tau_\eta as new.

The interface between these two parts of the proof is huge (most of page 16). So confirming that C.2 actually appeals to the implicit lemma that's proved in C.1 is a lot of work. I'm surprised that the authors went to that trouble and didn't bother to write the conclusions of C.1 as an explicit, precise lemma. (Presentation issue 4)

In the current manuscript, we have added a full statement of Lemma 6 in Appendix D.1 specifying the initialization, offset, coefficient, norm, error, and endpoint assumptions, together with the conclusion and constants. We have also added a seven-item check in Appendix D.2 using

\qquad K=\frac{4n}{\gamma},\qquad E=1,$$ and projected rank $r'\le r-1$. The check distinguishes assumptions needed only before the endpoint from those needed through it, ensuring that the last update is covered. > On the other, a weekend's work isn't what I'd like to see as a conference-level contribution now that we have such capable tools. [...] But I'd also like to see authors put more effort into understanding and shaping the proofs that AI provides. (Paper Summary) We sincerely thank you for pointing it out, and we deeply apologize for any confusion it might cause. In this paper, we first identified the research question and established the basic proof ideas. We then used AI tools to refine the technical details, especifically setting constants in the upper- and lower-bound arguments. The main text was carefully written and polished. We recognize that the appendix needs further polishment, and we promise to polish the proof details in the next version to make the arguments clearer and more human-friendly. 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.

Thanks for the response

AuthorsOpenReview ↗

Thank you!

We sincerely thank you for your supportive feedback! Thanks again for your valuable comments to help us improve our paper.

Reviewer_wiWgOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the transition from oscillatory to stable behavior in gd with large constant stepsizes for logistic regression on linearly separable data. Previous work established that the transition time is bounded independently of the stepsize in two dimensions, leading to the conjecture that this property might hold in arbitrary dimensions.

The authors disprove this conjecture by establishing tight worst-case bounds on the transition time. Specifically, for fixed sample size nn, sufficiently small positive margin γ\gamma and stepsize η→∞\eta\to\infty they prove a rate that the worst-case transition time scales.

The proof combines an upper bound based on recursive projections and rank reduction with a matching lower-bound construction involving interacting samples that produce increasingly long oscillatory trajectories.The lower-bound construction establishes a strict loss increase at a sufficiently late iteration demonstrating delayed entry into the genuinely monotone regime.

The authors also establish that the threshold-based transition time has the same worst-case asymptotic order and derive improved finite horizon optimization guarantees.

Critical strengths
  • The paper establishes matching upper and lower bounds for the worst-case transition time in arbitrary dimensions, disproving the conjecture that the transition is uniformly bounded independently of the stepsize. The precise exponent min⁡(n−2,d−2)\min(n-2,d-2) reveals how the interaction between sample size and dimension determines the worst-case behavior. It is a theoretical advance over previous analyses that either provided loose general-dimensional bounds or were restricted to 2 dimensions.

  • The upper-bound analysis uses recursive projections to reduce the effective rank of the dynamics, while the lower-bound construction develops hierarchical interactions that realize each log factor. Of interest is the demonstration of a strict loss increase late in the constructed trajectory, which establishes tightness for the exact transition time rather than only for a sufficient stability threshold. The resulting analysis also yields improved finite-horizon optimization guarantees, strengthening the results.

Critical weaknesses
  • Although the paper establishes a tight worst-case dependence on η\eta, the constructed hard instances may vary with the step size. Consequently, the results do not establish that any single fixed dataset exhibits a transition time growing as (log⁡η)min⁡n−2,d−2)(\log\eta)^{\min{n-2,d-2}}). This limits what can be concluded about the asymptotic behavior of gd on a fixed learning problem and leaves open whether the hierarchical instability is property of individual datasets or if this is mainly subject of worst-case constructions.

  • The matching lower bound holds only for sufficiently small margins with an implicit margin threshold depending on the sample size and the results are asymptotic in the step size. The paper does not provide experiments/simulations illustrating the constructed trajectories or examining their transition times at finite step sizes. Its unclear how small the margins and how large the step sizes must be before the predicted scaling becomes observable or whether similar behavior occurs outside the constructed worst-case instances which would be valuable results for practitioners.

Questions for authors
  • The matching lower-bound construction permits the dataset to depend on η\eta. Is it possible to establish a diverging transition time for a single fixed linearly separable dataset with sample size and dim ≥\geq 3, or is the dependence on the step size in the construction essential?

  • Can the authors characterize the dependence of the admissible margin threshold γn\gamma_n and the required stepsize threshold on nn? In particular, are the constructed instances realizable with moderately sized margins and stepsizes, or do the asymptotic lower bounds require extremely small margins or large step sizes?

  • Could the authors provide numerical trajectories for the lower-bound constructions in small dimensions, such as n=d=3n=d=3 and n=d=4n=d=4 comparing observed transition times against the predicted log⁡η\log\eta and (log⁡η)2(\log\eta)^2 scaling? this would help assess whether the construction produces the predicted behavior at accessible step sizes.

4 comments
AuthorsOpenReview ↗

Clarifications (1)

We sincerely appreciate your helpful and constructive advice. We also appreciate your recognition of our tight worst-case transition-time bounds and the resulting finite-horizon optimization guarantees. We understand that your main concerns are around whether the worst-case growth can occur on a fixed dataset and whether it is observable at finite stepsizes. The worst-case lower-bound formulation permits the dataset to depend on the stepsize, as in Crawshaw and Liu (2026). Our additional result shows that every fixed dataset has eventually bounded transition time; divergence requires datasets that vary with the stepsize. We have added the proof and numerical experiments in three and four dimensions to the current manuscript (Appendices H.1 and I).

Below, k=min⁡n−2,d−2k=\min\\{n-2,d-2\\}; σ\sigma and τ\tau denote the monotonicity and small-loss threshold times, respectively.

Is it possible to establish a diverging transition time for a single fixed linearly separable dataset with sample size and dimension at least 3, or is the dependence on the step size in the construction essential? (Weakness 1; Question 1)

(1) Consistency with prior lower-bound constructions.

Allowing the hard dataset to depend on the stepsize is consistent with prior work. In Crawshaw and Liu (2026, Appendix B, proof of Lemma 3.12), the hard-instance parameter δ\delta is also chosen as a function of η\eta. Our lower bound follows the standard worst-case formulation: nn, dd, and the margin requirement remain fixed, while the worst case is taken separately for each η\eta.

(2) Stepsize dependence is essential for a diverging lower bound.

We agree that allowing the dataset to depend on the stepsize is essential for a diverging lower bound. Under our assumptions, we here additionally prove that every fixed DD admits η∗(D)<∞\eta_*(D)<\infty such that

\qquad \eta\ge\eta_*(D).$$ The proof uses the limiting process $$z_0=0,\qquad z_{t+1}=z_t+\frac{1}{n}\sum_i a(\langle z_t,x_i\rangle)x_i,$$ where $a(s)=1$ for $s<0$, $a(0)=1/2$, and $a(s)=0$ for $s>0$. Separator progress and a norm bound imply that this process reaches a strict separator within $1+\lceil 2n/\gamma^2\rceil$ steps. Over these finitely many steps, $w_t=\eta z_t+o(1)$, including at zero ideal margins, so its final positive margins ensure $F(w_t)\le 1/(8\eta)$ for sufficiently large $\eta$. We have added the full proof and an explicit $\eta_*(D)$ in Appendix H.1 of the current manuscript. The sufficient stepsize threshold $\eta_*(D)$ is dataset-dependent, so this result is consistent with a diverging uniform worst case. We thank you for this question, which motivated the additional result and helped us enhance the manuscript. **(3) Technical contribution of this paper.** Our contribution is the sharp uniform rate $\Theta((\log\eta)^k)$, where $k=\min\{n-2,d-2\}$. Recursive rank reduction establishes the upper bound, while a hierarchical construction realizes all $k$ logarithmic factors. To prove the lower bound for the exact transition time, we construct a strict loss increase at time $\Theta((\log\eta)^k)$ along GD from zero initialization. > In particular, are the constructed instances realizable with moderately sized margins and stepsizes, or do the asymptotic lower bounds require extremely small margins or large step sizes? (Weakness 2; Question 2) Yes, the constructions are realizable with fixed positive margins at finite stepsizes. In 3D and 4D, we obtain margins of $1/(4\sqrt{10})\approx0.07906$ and $1/20=0.05$, respectively. These margins do not shrink as $\eta$ increases, although the stepsizes in our certified examples remain large. To realize these datasets, we choose the scale $\rho=1/2$ in Appendix E.5. The interacting samples have Gram matrix $\rho^2K$, using the pair matrix $K_1$ in 3D and the first-gate matrix $K_2$ in 4D. An additional setup sample places the first GD iterate, starting from zero, at the required auxiliary margins. Our unit separator has margin \$ \frac{\rho}{2\sqrt{\mathbf{1}^{\top}K^{-1}\mathbf{1}}} \$ on the interacting samples. Since $\mathbf{1}^{\top}K_1^{-1}\mathbf{1}=10$ and $\mathbf{1}^{\top}K_2^{-1}\mathbf{1}=25$, this gives the two margins above. For sufficiently large $\eta$, direct checks show that all sample norms are below one and the setup-sample margin exceeds $0.18$, so the full datasets satisfy the claimed margin bounds. We have added these calculations in Appendix H.3 of the current manuscript. We also verify concrete finite instances: at $\eta=10^6$ in 3D, $(\sigma_\eta,\tau_\eta)=(4,6)$; at $\eta=10^8$ in 4D, $(\sigma_\eta,\tau_\eta)=(9,204)$, with the respective margins above. These GD trajectories from zero have interval certificates, establishing finite-step realizability directly. They are included in Appendix I.2 of the current manuscript.
AuthorsOpenReview ↗

Clarifications (2)

Can the authors characterize the dependence of the admissible margin threshold γn\gamma_n and the required stepsize threshold on nn? (Weakness 2; Question 2)

A sufficient margin threshold for every n≥2n\ge2 is

γn=1642(n−1).\gamma_n=\frac{1}{64\sqrt{2}(n-1)}.

To obtain it, set m=k+1m=k+1 and ρ=1/(82m)\rho=1/(8\sqrt{2m}) in Appendix E.5. The bounds 116I⪯K⪯2I\frac{1}{16}I\preceq K\preceq2I give auxiliary margin at least ρ/(8m)=1/(642m)≥γn\rho/(8\sqrt{m})=1/(64\sqrt{2}m)\ge\gamma_n, while the setup margin exceeds 1/41/4 for sufficiently large η\eta. This covers k≥1k\ge1; the separate k=0k=0 construction satisfies the same threshold. The derivation is in Appendix H.3 of the current manuscript.

Tracking Appendices D.1-D.2 gives the sufficient upper-bound threshold $ \eta_{\mathrm{up}}(n,\gamma)=\frac{2^{2n+12}n^3}{\gamma^4}. $

For η≥ηup\eta\ge\eta_{\mathrm{up}}, a sufficient upper coefficient is

x=\frac{3\gamma^2}{2^{n+6}},\qquad Q=1+\frac{256}{\gamma^2},\qquad 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, \end{aligned}$$ where $\log_+(u)=\max\\{0,\log u\\}$. Both quantities are uniform over datasets and ambient dimension. For $\gamma\le\gamma_n$, the lower coefficient can be chosen as $c_{\mathrm{low}}(n)=2^{-4n^2}$, by separating episode-mass and episode-length constants. We have added the derivations of these conservative constants and sharper small-dimensional coefficients in Appendices H.2-H.4 of the current manuscript. Under our assumptions, we here additionally prove that a sufficient lower-bound threshold is $$\eta_{\mathrm{low}}(n)=128n(n-1)\exp\!\left(2^{3200n^2 16^{n-2}}\right).$$ For every $\eta\ge\eta_{\mathrm{low}}(n)$ and $0<\gamma\le 1/[64\sqrt{2}(n-1)]$, the lower bound holds uniformly over dimension. Appendix H.7 of the current manuscript gives the explicit stopping depths, target-set bounds, and finite-stepsize error estimates, including the transfer to GD from zero. This is a conservative sufficient threshold; the finite examples below work at much smaller stepsizes. We appreciate this question, which helped us make the parameter dependence explicit and enhance the manuscript. > Could the authors provide numerical trajectories for the lower-bound constructions in small dimensions, such as $n=d=3$ and $n=d=4$ comparing observed transition times against the predicted $\log\eta$ and $(\log\eta)^2$ scaling? (Weakness 2; Question 3) We have added full-GD trajectories from zero and transition-time comparisons in Appendices I.1-I.2 of the current manuscript, using the inverse construction. The 18 benchmark instances use separator margins approximately 0.009882 in 3D and 0.005103 in 4D, with $\eta$ ranging from $10^{12}$ to $10^{56}$ and from $10^{16}$ to $10^{40}$, respectively. The fitted leading coefficients in natural-log units are 1.1194 and 0.14309, compared with theoretical late-increase lower coefficients 1.12036 and 0.14278. These fits include lower-order terms; their finite-range agreement does not establish equality of the asymptotic coefficients. In separate larger-margin constructions, with separator margins at least $1/(4\sqrt{10})$ in 3D and $1/20$ in 4D, we obtain: | Dimension | $\eta=10^8$ | $\eta=10^{10}$ | $\eta=10^{12}$ | |---|---:|---:|---:| | 3D | $(9,11)$ | $(14,16)$ | $(19,21)$ | | 4D | $(9,204)$ | $(19,214)$ | $(36,231)$ | Each entry is $(\sigma,\tau)$, distinguishing late loss increases from delayed threshold crossing. All 27 saved rational witnesses, including the 18 benchmark instances, have replayable interval certificates for their loss comparisons and transition times. These stepsizes remain large. For comparison, the fixed limiting datasets have $\tau=2$ and $3$ in 3D and 4D, respectively, at $\eta=10^6,10^7,10^8$. These values were checked at 100-digit precision, separately from the interval certificates. This agrees with the fixed-dataset result above; worst-case growth should not be interpreted as typical fixed-data behavior. 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.
Reviewer_wiWgOpenReview ↗

My review points are mostly resolved.

The simulations I was interested in seeing are now present. The authors also demonstrate no single fixed dataset has transition time diverging as the stepsize goes to infinity. The authors also provide explicit sufficient margin and stepsize thresholds but larger margin examples still use large step sizes which still leaves questions about practical relevance. I have raised my score as most of my concerns are resolved.

AuthorsOpenReview ↗

Thank you!

We sincerely thank you for your detailed and insightful feedback, and we are happy to see that our response address your concerns. Thanks again for your valuable comments to help us improve our paper.

Comments on the paper

1 comment

Dear Reviewers,

The rebuttal period ends in less than two days. If you have not already done so, I kindly ask you to acknowledge the authors’ responses, and indicate whether your main concerns have been adequately addressed or further clarification is needed.

Thank you.

AC

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.