acceptodds
Under review as a conference paper at ICLR 2027

Convergence Analysis of Normalized Gradient Descent for Definable Functions

Abstract

Normalized gradient descent (NGD) updates model parameters in the negative gradient direction with a prescribed step length. Its invariance to positive rescaling and its ability to move through regions with small gradients make it an attractive alternative to gradient descent. We study when diminishing stepsizes make NGD iterates bounded and convergent. For locally Lipschitz definable objectives and every positive vanishing nonsummable schedule, a bounded NGD trajectory has convergent objective values and only Clarke critical accumulation points. For a coercive definable loss, all trajectories of NGD from a bounded initial set are bounded when all the stepsizes are below a uniform threshold. We also prove that stepsizes , with , guarantee convergence of every bounded trajectory to a Clarke critical point for locally Lipschitz losses definable in a polynomially bounded o-minimal structure. This class includes squared-loss objectives for finite ReLU networks on finite datasets. We also show a sharp dependence on the stepsize schedule and dimension: for every and , a real-analytic semialgebraic objective in three dimensions admits a bounded nonconvergent NGD trajectory with . In two dimensions, every bounded NGD trajectory converges throughout for locally Lipschitz definable losses. Thus, even when the loss converges to a critical value and the distance to the set of critical points tends to zero, parameter convergence can depend on dimension and stepsize decay.

Primary area:
optimization
Keywords:
Normalized gradient descent, nonsmooth optimization, o-minimal structure

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_bd8UOpenReview ↗
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 αk=c/(k+1)\alpha_k=c/(k+1) 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 αk=c(k+1)−p\alpha_k=c(k+1)^{-p} with 1/2<p<11/2<p<1. 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 αk=c/(k+1)\alpha_k=c/(k+1). 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 p=1p=1 and 1/2<p<11/2<p<1 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 λ∣w∣2\lambda|w|^2 with λ>0\lambda>0 and choosing cc 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 p=1p=1 and 1/2<p<11/2<p<1 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 X0X_0, but the proof seems to use compactness and maxima over X0X_0. Also, the conclusion says that the harmonic schedule is sharp among nonsummable power-law schedules, while the counterexample is only proved for 1/2<p<11/2<p<1.

Questions for authors
  1. Do the authors expect the main convergence results to extend to stochastic or minibatch NGD? What would be the main technical obstacle?

  2. 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?

  3. How should the harmonic schedule αk=c/(k+1)\alpha_k=c/(k+1) be interpreted in practical neural-network training? Do the authors expect the same behavior for commonly used learning-rate schedules?

  4. Is quadratic regularization essential for the neural-network boundedness result? Can boundedness be established for any useful class of unregularized networks?

  5. 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?

  6. Theorem 3.1 assumes that X0X_0 is bounded, while the proof appears to use compactness of X0X_0. Should the theorem assume that X0X_0 is compact?

  7. The counterexample covers 1/2<p<11/2<p<1. What is known for p≤1/2p\leq 1/2? If this regime is open, should the sharpness claim in the conclusion be stated more narrowly?

  8. Have the authors considered adding a small numerical experiment illustrating the different behavior of p=1p=1 and 1/2<p<11/2<p<1?

7 comments

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(x+3)^2/2, x2/2x^2/2, and x2/2x^2/2, sampled uniformly and independently with batch size one. The sampled gradient is unbiased with variance 22, and the mean loss ff has its unique minimizer at −1-1. Nevertheless, stochastic NGD with stepsizes αk=c/(k+1)\alpha_k=c/(k+1), c>0c>0, has bounded iterates converging almost surely to 00, and f′(0)=1f'(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\epsilon,\delta>0 and any finite iteration budget TT, 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 xkx_k, 0≤k<T0\le k<T, satisfies dist⁡(0,Gδ(xk))>ϵ\operatorname{dist}(0,G_\delta(x_k))>\epsilon. 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)),G_\delta(x):=\operatorname{conv}\\!\left(\bigcup_{\\|y-x\\|\le\delta}\partial f(y)\right), where ∂f\partial f is the Clarke subdifferential.

This lower bound applies to both quantities in your question. Put Crit⁡f:=y:0∈∂f(y)\operatorname{Crit}f:=\\{y:0\in\partial f(y)\\}. If dist⁡(x,Crit⁡f)<δ\operatorname{dist}(x,\operatorname{Crit}f)<\delta, there exists y∈Crit⁡fy\in\operatorname{Crit}f with ∣x−y∣<δ\\|x-y\\|<\delta, so 0∈∂f(y)⊆Gδ(x)0\in\partial f(y)\subseteq G_\delta(x). Moreover, ∂f(xk)⊆Gδ(xk)\partial f(x_k)\subseteq G_\delta(x_k) gives, for every positive integer TT,

\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.

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 vk/∣vk∣v_k/\\|v_k\\|. The divisor ∣vk∣\\|v_k\\| can approach zero, so the effective unnormalized stepsizes αk/∣vk∣\alpha_k/\\|v_k\\| can become large and have irregular ratios.

The key idea is to retain the L′L'-regular geometry of Lai and Song (2026a) while refining the stratification to have constant rank and satisfy strict Thom's (wf)(w_f) condition. Our Lemma B.3 constructs this simultaneous refinement using the strict-Thom genericity result. Each restriction f∣Mf|_M has rank one or zero, so ∇Mf\nabla_M f is respectively everywhere nonzero or everywhere zero on MM. Lê Loi (1998, Definition 2.1 and Proposition 2.7)

The projection formula, stated in our Eq. (12), gives

PTyMv=∇Mf(y),y∈M,v∈∂f(y).P_{T_yM}v=\nabla_M f(y),\qquad y\in M,\quad v\in\partial f(y).

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 ∣∇Mf∣\\|\nabla_M f\\| attains a positive minimum μC\mu_C on every nonempty compact subset C⊂MC\subset M. Appendix B.1 proves that, for every x∈K+x\in K^+ sufficiently near CC and every v∈∂f(x)v\in\partial f(x),

μC/2≤∣v∣≤Q,\mu_C/2\le\\|v\\|\le Q,

where K+K^+ is the working ball and QQ is the uniform bound in Eq. (30). Consequently, for updates starting in this neighborhood,

αkQ≤αk∣vk∣≤2αkμC.\frac{\alpha_k}{Q}\le\frac{\alpha_k}{\\|v_k\\|}\le\frac{2\alpha_k}{\mu_C}.

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, TyM=ker⁡D(f∣M)(y)T_yM=\ker D(f|_M)(y). For xx on an incident stratum RR and 0≠v∈∂f(x)0\ne v\in\partial f(x), the projection formula on RR makes u=v/∣v∣u=v/\\|v\\| perpendicular to ker⁡D(f∣R)(x)\ker D(f|_R)(x). For every incident pair M⊆R‾∖RM\subseteq\overline R\setminus R and every y0∈My_0\in M, strict Thom's condition supplies constants C,r>0C,r>0 such that

∣PTyMu∣≤C∣x−y∣\\|P_{T_yM}u\\|\le C\\|x-y\\|

whenever y∈M∩B(y0,r)y\in M\cap B(y_0,r) and x∈R∩B(y0,r)x\in R\cap B(y_0,r), as shown in Eq. (34). At x∈Mx\in M, the projection formula gives zero tangential component. On the scale-dependent neighborhoods, with yk=PMxky_k=P_Mx_k, 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 p=0.6p=0.6 and m=3m=3, the leading angular increment over eight iterations scales as (k+1)−4/5(k+1)^{-4/5} 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 C2C^2 semialgebraic objective on R4\mathbb R^4 to compare NGD with αk=(k+1)−p\alpha_k=(k+1)^{-p}, p=0.6p=0.6 and p=1p=1, using the same function and initial point. For T=2,000,000T=2{,}000{,}000 updates, the table reports the four-dimensional finite-tail diameter

Dk,T:=max⁡k≤i,j≤T∣yi−yj∣.D_{k,T}:=\max_{k\le i,j\le T}\\|y_i-y_j\\|.

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$.
Reviewer_bt7dOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper analyzes the convergence behavior of normalized gradient descent (NGD). For locally Lipschitz and definable functions, this paper shows that NGD can converge to the optimal solution.

Critical strengths
  • This paper comprehensively studied the convergence behavior of NGD.
  • Specifically, for locally Lipschitz and definable functions, this paper shows that NGD converges to the stationary point when the stepsize decreases as O(1/k)O(1 / k).
  • The paper demonstrates that, in Theorem 2.5, NGD may not converge to any single point, even when the stepsize is decreasing.
Critical weaknesses
  • The paper analyzes NGD under assumptions such as definability, but it does not adequately motivate why these assumptions are important in practice. In particular, it is unclear which classes of optimization problems benefit from these results and how the assumptions relate to neural networks.
  • The convergence behavior of NGD has been widely studied in the existing literature, e.g., [1,2], especially for smooth and non-smooth functions. However, this paper did not discuss it. It makes it difficult to understand why it is important to analyze NGD in these assumptions, i.e., definable functions.
  • Although the paper establishes convergence of NGD, it does not characterize the convergence rate. In particular, it remains unclear how quickly the iterates approach a critical point and how the rate depends on the objective function and stepsize schedule.

Reference

[1] Vankov et. al., Optimizing (L0,L1)-Smooth Functions by Gradient Methods, ICLR 2025
[2] Nesterov. Lectures on convex optimization. In Springer, 2018.

Questions for authors

See the weakness section.

1 comment

Thank you for the references and for asking us to explain the function class and the convergence results.

Practical relevance and neural networks. Definability covers many familiar functions, including polynomials, exponential and logarithmic functions, and their finite sums, products, compositions, and pointwise maxima. It accommodates nonconvexity and sharp corners while providing a decomposition into smooth pieces whose geometry supports our convergence analysis (Davis et al., Section 5.2).

Widely used activations such as ReLU, sigmoid, tanh, and GELU are definable. Network layers and squared loss preserve this property, so the resulting training objectives are also definable. Section 6 verifies that their restrictions to bounded parameter regions are definable in a common polynomially bounded o-minimal structure.

Our results apply to least-squares matrix factorization (Corollary 3.3) and squared-loss training of feedforward neural networks with positive quadratic regularization of all parameters (Corollary 6.2). For these problems, harmonic stepsizes αk=c/(k+1)\alpha_k=c/(k+1) with sufficiently small c>0c>0 guarantee boundedness and convergence of the entire parameter sequence to a single critical point. This establishes that the parameters themselves converge as training continues, which does not follow from convergence of the loss alone. We will make these connections more explicit in the revised manuscript.


Prior analyses. Nesterov (2018, Section 3.2.3) gives rates for the best objective value of normalized subgradient descent on convex objectives, including nonsmooth ones. Vankov et al. (2025) study gradient methods under generalized smoothness, giving rates for objective gaps in convex problems and gradient norms in nonconvex problems.

These analyses do not cover objectives that are both nonconvex and nonsmooth, such as ReLU-network training losses. Definability provides geometric structure shared by many such objectives, allowing us to analyze NGD in this setting. For locally Lipschitz objectives definable in a polynomially bounded o-minimal structure, Theorem 2.3 establishes convergence of every bounded NGD sequence with harmonic stepsizes to a single critical point. Section 6 shows that this result applies to the neural-network objectives discussed in our response to your first concern. We will add these references and clarify this motivation in the revised manuscript.


Convergence rates. Obtaining a uniform finite-time complexity for convergence to the limit in such a general nonconvex, nonsmooth setting is difficult. A rate of convergence to a critical point also gives a Goldstein-stationarity guarantee. Indeed, whenever ∣xk−x∗∣<δ\\|x_k-x^\ast\\| < \delta, 0∈∂f(x∗)⊆Gδ(xk),0\in\partial f(x^\ast)\subseteq G_\delta(x_k), so dist⁡(0,Gδ(xk))=0\operatorname{dist}(0,G_\delta(x_k))=0. Thus, a bound on ∣xk−x∗∣\\|x_k-x^\ast\\| gives the number of iterations needed to reach (δ,0)(\delta,0)-Goldstein stationarity. However, subgradient methods that choose subgradients deterministically, including NGD, admit no finite-time stationarity guarantee based only on the objective's Lipschitz constant and initial objective gap (Tian and So, 2024, Theorem 2 and Remarks 3–4). This holds even for piecewise-linear semialgebraic objectives, which is definable in every o-minimal structure.

While a uniform finite-time complexity bound based only on the Lipschitz constant and initial objective gap is impossible, our current results yield asymptotic rates for harmonic stepsizes. Choose the exponent θ∈(1/2,1)\theta\in(1/2,1) in Eq. (39). The KL inequality and local separation of Clarke subgradients, combined with the diameter estimate (72), show that crossing a function-value band of scale ε\varepsilon takes cumulative stepsize O(ε1−2θ)O(\varepsilon^{1-2\theta}). Using ∑j<kαj≍log⁡k\sum_{j < k}\alpha_j\asymp\log k gives the objective rate below, and Eq. (72) then transfers it to the rate on the parameter sequence xkk\\{x_k\\}_k:

=O\left((\log k)^{-1/(2\theta-1)}\right),\qquad \\|x_k-x^\ast\\| =O\left((\log k)^{-(1-\theta)/(2\theta-1)}\right).$$ We will add this asymptotic convergence rate result in the revised manuscript.
Reviewer_tpftOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

This paper discusses convergence properties of normalized gradient descent under localized smoothness + definable functions. The convergence guarantee depends on the step size scheduling, hence they look at different learning rate schedules; namely (k+1)^{-p} scaled learning rates. When p = 1 every trajectory converges, but when 1/2 < p < 1 they have an explicit counterexample where the algorithm has a limit cycle.

Critical strengths

The motivation for studying normalized gradient descent is understandable, and I think they aimed to do a thorough analysis on the convergence of normalized gradient descent. Also the nonconvergence results are interesting.

Critical weaknesses

The major weakness is it is very hard to understand why the authors are interested in definable functions, and what the definable functions even mean. The authors refer the definition of definability to existing references, but I think they should explain what it means and motivate sufficiently why we want to understand when the objective is definable. Also, whether the definability condition is needed for the proofs were also a bit hard to follow; I think a better emphasis on the technical importance of definability is needed.

Also a related reference is missing and I think there should be discussion on the difference between their proof and the proof here. I believe normalized gradient descent is an instance of the Lion-K optimizer with l_2 norm, and in the Lion-K paper there are convergence guarantees already made for Lipschitz functions. Is this paper proving something stronger? If true, is the theorem substantially stronger, or does it reflect reality better, or is it technically harder? These should be discussed.

[1] Chen, Lizhang, et al. "Lion secretly solves a constrained optimization: As lyapunov predicts." International Conference on Learning Representations. Vol. 2024. 2024.

Questions for authors

See critical weaknesses

2 comments

Thank you for highlighting the need to explain definability and to situate the results relative to Lion-K.

Motivations. Definability covers a broad range of familiar functions. For example, all polynomials, exponential and logarithmic functions are definable in a suitable o-minimal structure. Finite sums, products, compositions, and pointwise maxima of these functions are also definable. This covers many standard learning objectives, including those in linear and logistic regression, hinge-loss support vector machines, least-squares matrix factorization, and neural network training with widely used activation functions and losses (Davis et al., Section 5.2). We study this class because it allows nonconvexity and sharp corners while providing favorable geometric structure for convergence analysis. It excludes functions such as f(x)=x2sin⁡(1/x)f(x)=x^2\sin(1/x) for x≠0x\neq0, with f(0)=0f(0)=0, which oscillates infinitely often near zero. A formal definition is included at the end of this response.

Technical Importance. For Theorem 2.1, definability supplies a chain rule for nonsmooth descent dynamics and ensures that objective values at critical points cannot fill an interval. Remark 2.2 identifies these as the two structural properties used in the proof (Appendix A.1).

For Theorem 2.3, definability provides finitely many smooth pieces with controlled geometry at their boundaries. We analyze projected updates near these pieces and combine the estimates across repeated visits. The additional "polynomially bounded" assumption provides quantitative bounds that make the relevant errors summable under harmonic stepsizes. Together, these estimates show that all sufficiently late iterates are close to one another, establishing convergence of every bounded trajectory to a single critical point (Section 4 and Appendix B).

We will add this intuition, definition, and motivation to the introduction and Section 2, and explain these proof dependencies explicitly in Section 4.


Relation to Lion-K. Indeed, NGD is obtained from Lion-K by taking K(v)=∥v∥2K(v)=\|v\|_2 and β1=λ=0\beta_1=\lambda=0. The main difference is the convergence guarantee. Lion-K paper (Chen et al., 2024) assumes Lipschitz continuous gradients and bounds a stationarity measure averaged over iterations. Our result allows nonsmooth losses. With definability assumption, it proves that every bounded NGD sequence with harmonic stepsizes converges to a single critical point. Notice that even vanishing gradient norms don't ensure that the parameters converge (Theorem 2.5).

Lion-K's proof use a Lyapunov approach to bound the averaged stationarity. However, proving convergence to a single point requires ruling out infinite oscillation near critical points. This can't be excluded by using stationarity estimates alone. Our proof uses definable geometry to control projected updates on smooth pieces of definable functions and show that all sufficiently late iterates are close to each another.

We will add this reference and clarify these differences in the revised manuscript.


Appendix: Formal definition (for completeness).

Following Bolte et al., 2007, Definitions 6–7, an o-minimal structure on the real field is a sequence R=(Rn)n≥1\mathcal{R}=(\mathcal{R}_n)_{n\geq 1} of Boolean algebras of subsets of Rn\mathbb{R}^n. Thus, each Rn\mathcal{R}_n contains ∅\varnothing and is closed under finite unions, finite intersections, and complements relative to Rn\mathbb{R}^n. The following four axioms hold:

  1. If A∈RnA\in\mathcal{R}_n, then A×RA\times\mathbb{R} and R×A\mathbb{R}\times A belong to Rn+1\mathcal{R}_{n+1}.

  2. If A∈Rn+1A\in\mathcal{R}_{n+1}, then π(A)∈Rn\pi(A)\in\mathcal{R}_n, where π:Rn+1→Rn\pi:\mathbb{R}^{n+1}\to\mathbb{R}^n is the coordinate projection π(x1,…,xn+1)=(x1,…,xn)\pi(x_1,\ldots,x_{n+1})=(x_1,\ldots,x_n).

  3. For every polynomial function p:Rn→Rp:\mathbb{R}^n\to\mathbb{R} with real coefficients, the set x∈Rn:p(x)=0\\{x\in\mathbb{R}^n:p(x)=0\\} belongs to Rn\mathcal{R}_n.

  4. The members of R1\mathcal{R}_1 are exactly the finite unions of points and open intervals, including unbounded intervals.

A function f:Rd→Rf:\mathbb{R}^d\to\mathbb{R} is definable in R\mathcal{R} if its graph gph⁡f=(x,f(x)):x∈Rd\operatorname{gph}f=\\{(x,f(x)):x\in\mathbb{R}^d\\} belongs to Rd+1\mathcal{R}_{d+1}.

I appreciate the authors for their response. I believe the paper has some values by proposing definable functions as a way to deal with nonsmoothness, but I believe the manuscript is not ready for publication and needs much more work on the presentation.

Therefore I remain my score.

Comments on the paper

1 comment

We sincerely thank the Program Chairs, Senior Area Chairs, Area Chairs, and reviewers for their time and constructive feedback. The discussion helped us sharpen the stepsize result, derive convergence rates, and add a numerical illustration. We summarize the main contributions and the results added during the rebuttal below.

Main contributions

  • Loss convergence and stationarity. For locally Lipschitz definable objectives, every bounded normalized gradient descent (NGD) trajectory has convergent loss values and only Clarke-critical accumulation points under positive, vanishing, nonsummable stepsizes.
  • Whole-sequence convergence. For locally Lipschitz objectives definable in a polynomially bounded o-minimal structure, harmonic stepsizes guarantee convergence of every bounded trajectory to a single Clarke-critical point in any dimension. In two dimensions, the guarantee extends to every positive, nonsummable, square-summable schedule.
  • Dimension-dependent nonconvergence. The original submission constructs a three-dimensional real-analytic semialgebraic objective for each power-law exponent 1/2<p<11/2 < p < 1 and each c>0c > 0. The resulting bounded trajectory accumulates on a circle of critical points, with convergent loss values and vanishing gradient norms.
  • Boundedness and learning applications. A coercive auxiliary function yields boundedness guarantees. With sufficiently small harmonic stepsizes, the results give whole-sequence convergence for unregularized least-squares matrix factorization and quadratically regularized feedforward neural networks training with squared loss.

New theoretical results

  • Logarithmic rates for harmonic NGD. Theorem 2.3 and Appendix B.5 give trajectory-dependent rates of O((log⁡k)−1/(2θ−1))O((\log k)^{-1/(2\theta-1)}) for the absolute loss gap and O((log⁡k)−(1−θ)/(2θ−1))O((\log k)^{-(1-\theta)/(2\theta-1)}) for the distance to the limit, for some θ∈(1/2,1)\theta\in(1/2,1).
  • Sharpness over the full power-law range. Theorem 2.5 now covers every 0<p<10 < p < 1 and every c>0c > 0. Together with Theorem 2.3, this makes harmonic decay the unique vanishing, nonsummable power-law schedule that guarantees point convergence uniformly over bounded trajectories in dimensions three and higher.

New numerical result

  • Numerical illustration. Section 7 compares p=0.6p=0.6 and p=1p=1 on the same four-dimensional C2C^2 semialgebraic objective from the same initial point. Over iterations 10610^6 through 2×1062\times10^6, the iterate diameters were approximately 0.150.15 for p=0.6p=0.6 and 2.0×10−62.0\times10^{-6} for p=1p=1. Figure 2 reports the tail diameters, and Appendix E provides the details.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.