- Rating
- 3(+1)
- Confidence
- 1
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper studies the convergence of normalized gradient descent for nonconvex and possibly nonsmooth definable functions. The main result shows that, for bounded trajectories, harmonic stepsizes guarantee convergence to a single critical point under polynomially bounded o-minimal definability. The paper also studies more general diminishing stepsizes. In two dimensions, square-summable but nonsummable steps are sufficient for convergence, while in dimension three the authors construct an analytic semialgebraic example with a bounded nonconvergent NGD trajectory for with . The paper also gives boundedness results for coercive objectives and applies them to matrix factorization and regularized finite neural networks. I found the theoretical results interesting, especially the dimension-dependent behavior. My main concern is that the paper is quite far from the practical optimization setting used to motivate NGD.
Critical strengths
-
The dimension-dependent result is interesting. The paper shows that the loss and gradient norm may converge while the iterates themselves do not converge, even for an analytic semialgebraic function.
-
The analysis is fairly general on the deterministic side. It covers nonconvex and nonsmooth definable functions and has to deal with the singular behavior caused by normalizing a subgradient whose norm may approach zero.
Critical weaknesses
-
The connection to practical ML training is weak. The paper studies deterministic NGD with the exact gradient, or an arbitrary Clarke subgradient. In actual neural-network training, normalized methods would normally use minibatch stochastic gradients. I am not sure how much of the analysis survives in the stochastic setting, especially close to critical points where normalization may amplify noise.
-
The results are asymptotic. The paper proves that trajectories eventually converge, but does not give a finite-time rate for reaching stationarity or approaching the limiting point. This makes it difficult to judge the algorithmic relevance of the results at realistic training horizons.
-
The main convergence theorem uses a very specific stepsize schedule. The general-dimensional result is for . This is mathematically natural, but it is not a typical learning-rate schedule in modern deep learning. I am not sure whether the distinction between and reflects a phenomenon that would actually matter in practice.
-
Boundedness is still a strong requirement. The main point-convergence theorem assumes that the trajectory is bounded. For the neural-network application, boundedness is obtained by adding quadratic regularization with and choosing sufficiently small. This is quite different from many practical training setups.
-
There are no experiments. Since the paper motivates NGD using learning applications, I think even a small experimental section would help. For example, it would be useful to see whether the difference between and can be observed on a simple learning problem, or whether the nonconvergent behavior around a critical manifold appears outside the constructed example.
-
The final guarantee is only convergence to a Clarke critical point. The result does not say whether the limit is a local minimum, a saddle point, or a point with any useful generalization or sharpness property. This makes the connection to the motivation about implicit regularization and flatter solutions somewhat indirect.
-
The novelty relative to Lai and Song should be clearer. The harmonic convergence proof uses their recent stratification and diameter framework quite heavily. I understand that normalized directions create an additional difficulty, but I would like the paper to explain more clearly which parts of the argument are genuinely new.
-
There are a couple of technical points that should be fixed or clarified. Theorem 3.1 is stated for a bounded set , but the proof seems to use compactness and maxima over . Also, the conclusion says that the harmonic schedule is sharp among nonsummable power-law schedules, while the counterexample is only proved for .
Questions for authors
-
Do the authors expect the main convergence results to extend to stochastic or minibatch NGD? What would be the main technical obstacle?
-
Is it possible to obtain any finite-time result, for example a rate for the distance to the critical set or for the minimum subgradient norm?
-
How should the harmonic schedule be interpreted in practical neural-network training? Do the authors expect the same behavior for commonly used learning-rate schedules?
-
Is quadratic regularization essential for the neural-network boundedness result? Can boundedness be established for any useful class of unregularized networks?
-
Could the authors clarify the difference with Lai and Song (2026a,b)? Which parts of the proof are specific to normalization and cannot be obtained directly from their existing framework?
-
Theorem 3.1 assumes that is bounded, while the proof appears to use compactness of . Should the theorem assume that is compact?
-
The counterexample covers . What is known for ? If this regime is open, should the sharpness claim in the conclusion be stated more narrowly?
-
Have the authors considered adding a small numerical experiment illustrating the different behavior of and ?
7 comments
5. Difference from Lai and Song. We use the stratification and projection tools of Lai and Song (2026a, Propositions 3.2 and 3.5) and their 2026b abstract diameter theorem (Theorem 2.4). Our normalization-specific work is to establish the required projected block estimates for . The divisor can approach zero, so the effective unnormalized stepsizes can become large and have irregular ratios.
The key idea is to retain the -regular geometry of Lai and Song (2026a) while refining the stratification to have constant rank and satisfy strict Thom's condition. Our Lemma B.3 constructs this simultaneous refinement using the strict-Thom genericity result. Each restriction has rank one or zero, so is respectively everywhere nonzero or everywhere zero on . Lê Loi (1998, Definition 2.1 and Proposition 2.7)
The projection formula, stated in our Eq. (12), gives
Our construction preserves this identity under the refinement in Lemma B.3. Bolte et al. (2007, Proposition 4)
On a rank-one stratum, the continuous positive function attains a positive minimum on every nonempty compact subset . Appendix B.1 proves that, for every sufficiently near and every ,
where is the working ball and is the uniform bound in Eq. (30). Consequently, for updates starting in this neighborhood,
On each such fixed neighborhood, NGD behaves like a subgradient method with comparable stepsizes, and we can adapt the analysis of Lai and Song (2026a, Section 4.1).
On a rank-zero stratum, . For on an incident stratum and , the projection formula on makes perpendicular to . For every incident pair and every , strict Thom's condition supplies constants such that
whenever and , as shown in Eq. (34). At , the projection formula gives zero tangential component. On the scale-dependent neighborhoods, with , Lemma B.5 and Eq. (14) give
\\|y_{k+1}-y_k\\|\le2C\alpha_k^{1+\delta_M},\qquad\delta_M>0,$$ for every nonconstant step. For harmonic stepsizes, the projected-displacement bound is summable because $\sum_k(k+1)^{-1-\delta_M}<\infty$, giving the rank-zero block estimate in Lemma B.7. These two cases supply the projected block estimates used in Appendix B.4. We will clarify this point in the revised manuscript. **6. Bounded versus compact initialization.** Boundedness of a nonempty $X_0$ is sufficient. Appendix A.2 takes maxima over $\overline{X_0}$, which is compact because $X_0$ is bounded in $\mathbb R^n$. Continuity of $f$ and $I$ gives finite maxima $$m_f=\max_{x\in\overline{X_0}}f(x),\qquad m_I=\max_{x\in\overline{X_0}}\|I(x)\|.$$ Every $x_0\in X_0$ satisfies $f(x_0)\le m_f$ and $\|I(x_0)\|\le m_I$. These common bounds enter the definitions of $M$ and $J$ in Appendix A.2 and produce the compact trapping set and step cap uniformly over $X_0$. Thus Theorem 3.1 applies to every nonempty bounded initialization set as stated. **7. The range $p\le1/2$ and sharpness.** Thanks for pointing out this. The proofs in Appendix D essentially works for every $0<p\le1/2$. We will expand the stated range in Theorem 2.5 and Appendix D to $(0,1)$.8. Experiments. The analytic counterexample in Theorem 2.5 (Appendix D) is impractical for numerical experiments because its angular drift is extremely slow. For and , the leading angular increment over eight iterations scales as with a small prefactor (Eq. (128)), so completing a single full turn (i.e., go around the circle once) requires an enormous number of iterations. Instead, we constructed a globally semialgebraic objective on to compare NGD with , and , using the same function and initial point. For updates, the table reports the four-dimensional finite-tail diameter
k & p=0.6 & p=1 \\\\ \hline 10000 & 0.22 & 2.0\times10^{-4} \\\\ 100000 & 0.18 & 2.0\times10^{-5} \\\\ 300000 & 0.16 & 6.7\times10^{-6} \\\\ 500000 & 0.16 & 4.0\times10^{-6} \\\\ 1000000 & 0.15 & 2.0\times10^{-6} \end{array}$$ The full function definition, parameters, initial point, and reproduction instructions are in the README of the [anonymous repository](https://anonymous.4open.science/r/ngd-experiment-7d31c6/). We will add this experiment to the revised manuscript. **Appendix: Proof of the minibatch counterexample.** Fix $x_0\in\mathbb{R}$ and $c>0$. Let $\mathcal{F}_k$ denote the history before sampling at iteration $k$. The sampled gradient equals $G_k=x_k+3$ with probability $1/3$ and $G_k=x_k$ with probability $2/3$. The normalized update is $$x_{k+1}=x_k-\alpha_k\operatorname{sign}(G_k), \qquad \alpha_k=\frac{c}{k+1},$$ where $\operatorname{sign}(0)=0$. First, the iterates are bounded. Put $M=\max\\{|x_0|,3+c\\}$. If $x_k\in[-3,0]$, then $x_{k+1}\in[-3-c,c]$. Outside $[-3,0]$, every update points toward this interval and has length at most $c$. Hence $|x_k|\le M$ for all $k$. Moreover, $$\mathbb{E}[G_k\mid\mathcal{F}_k]=x_k+1=f'(x_k), \qquad \mathbb{E}[(G_k-f'(x_k))^2\mid\mathcal{F}_k]=2.$$ Thus the oracle is unbiased with bounded variance. Its conditional second moment is also bounded along the iterates: $$\mathbb{E}[G_k^2\mid\mathcal{F}_k] =(x_k+1)^2+2\le(M+1)^2+2.$$ Define the mean normalized direction $$h(x)=\frac13\operatorname{sign}(x+3) +\frac23\operatorname{sign}(x).$$ For $x>0$, $h(x)=1$; for $x<0$, $h(x)\le-1/3$. Therefore $xh(x)\ge|x|/3$ for every $x$. Expanding the squared update and using $\operatorname{sign}(G_k)^2\le1$ gives $$\mathbb{E}[x_{k+1}^2\mid\mathcal{F}_k] \le x_k^2-2\alpha_k x_k h(x_k)+\alpha_k^2 \le x_k^2-\frac23\alpha_k|x_k|+\alpha_k^2.$$ Since $\sum_k\alpha_k^2<\infty$, the [Robbins–Siegmund theorem](https://doi.org/10.1016/B978-0-12-604550-5.50015-8) implies that $x_k^2$ converges and $\sum_k\alpha_k|x_k|<\infty$ almost surely. Because $\sum_k\alpha_k=\infty$, the limit of $x_k^2$ must be zero. Hence $x_k\to0$ almost surely, although $f'(0)=1$.
Thank you for the detailed questions. We address each point below.
1. Minibatch NGD. Our convergence guarantee does not extend to minibatch NGD under current assumptions. The main obstacle is that normalization can turn an unbiased gradient estimate into a biased one.
For example, consider the three losses (x+3)2/2, x2/2, and x2/2, sampled uniformly and independently with batch size one. The sampled gradient is unbiased with variance 2, and the mean loss f has its unique minimizer at −1. Nevertheless, stochastic NGD with stepsizes αk=c/(k+1), c>0, has bounded iterates converging almost surely to 0, and f′(0)=1. A short proof is provided in the appendix below.
However, our deterministic results show that parameters can keep moving despite a converging loss and vanishing gradients, even without sampling noise. This highlights why the learning-rate schedule matters in the noiseless case. Section 6 gives conditions ensuring parameter convergence for full-batch training of regularized neural networks.
We will clarify this practical interpretation, the scope of our guarantees, and their limitations for minibatch training in the revised manuscript.
2. Finite-time rates. It is impossible to obtain a uniform finite-time stationarity guarantee for NGD based only on the objective's Lipschitz constant and initial objective gap. As discussed in our response to Reviewer bt7d, for fixed sufficiently small ϵ,δ>0 and any finite iteration budget T, there is a piecewise-linear semialgebraic objective (which is definable in every o-minimal structure) in dimension two, with uniformly bounded Lipschitz constant and initial gap, for which every queried iterate xk, 0≤k<T, satisfies dist(0,Gδ(xk))>ϵ. This lower bound applies to general zero-respecting deterministic methods, a class containing NGD. Tian and So (2024, Theorem 2 and Remarks 3-4)
Here Gδ(x):=conv!(⋃∣y−x∣≤δ∂f(y)), where ∂f is the Clarke subdifferential.
This lower bound applies to both quantities in your question. Put Critf:=y:0∈∂f(y). If dist(x,Critf)<δ, there exists y∈Critf with ∣x−y∣<δ, so 0∈∂f(y)⊆Gδ(x). Moreover, ∂f(xk)⊆Gδ(xk) gives, for every positive integer T,
\le\min_{0\le k<T}\operatorname{dist}(0,\partial f(x_k)).$$ Thus, a uniform finite-time bound forcing the distance to the critical set below $\delta$ or the minimum subgradient norm below $\epsilon$ would yield the Goldstein-stationarity guarantee excluded by this lower bound. We will clarify this in the revised manuscript. **3. Practical meaning of the schedule.** To our knowledge, modern machine learning tasks usually use a constant stepsize schedule or cosine decaying stepsize schedule. In both cases the stepsizes has a uniform lower positive bound. Hence, for these stepsize schedules, $\\|x_{k+1}-x_k\\|$ are uniformly bounded away from 0. Therefore, it is impossible to get convergence toward a single critical point for NGD with these stepsizes schedules, because the iterate is by no way a Cauchy sequence, and hence it does not converge to any point. The practical implication of this paper is that, to ensure the convergence of the parameters using normalization techniques in the tranining, a sufficient condition will be choosing harmonic stepsize schedule. **4. Regularization and unregularized networks.** Quadratic regularization is sufficient for our general neural-network result, but is not required in every application. Corollary 3.3 already proves boundedness and convergence for unregularized least-squares matrix factorization.