acceptodds
Under review as a conference paper at ICLR 2027

Convergence Guarantees of Gradient Descent for Neural Networks via Generalized Lipschitz Smoothness

Abstract

We establish the first convergence guarantees of gradient descent for general feedforward neural networks of any width or depth, with any initialization or dataset. We only assume that the activation functions are linearly bounded, Lipschitz continuous, and Lipschitz smooth—properties that hold for linear, tanh, softplus, sigmoid, and smoothed ReLU functions—and that the loss function is Lipschitz smooth in the model outputs, a mild condition satisfied by mean squared error and binary cross-entropy loss. By relating the Lipschitz properties of one layer to the next, we obtain a novel generalized Lipschitz smoothness condition for an -layer neural network where the change in gradient is upper bounded by the change in the parameter space, multiplied by a polynomial of the parameter norms at both endpoints of degree . This yields a descent lemma where the loss decreases as long as the learning rate is small enough with respect to the parameter norms. By ensuring that the leading term of the polynomial grows at a controlled rate, we prove that the minimum squared gradient norm converges to zero in iterations at rate .

Primary area:
optimization
Keywords:
gradient descent, neural networks, optimization, nonconvex, Lipschitz smoothness

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_znx7OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

In this paper, the author show a bound for the convergence of ∥∇L(Wt)∥\|\nabla L(W_t)\| under two weaker assumptions that

1/. the activation is continuously differentiable and

2/. the loss is samplewise, non-negative and lipschitz smooth.

Importantly this work does not make particular assumption about the initialization, width, or depth of the network. They evaluate their framework by training dense neural net on the Cifar10 vision task.

Critical strengths

I appreciated the effort done to make this paper accessible to the general deep learning community. Importantly, this works show a decent focus on applicability: this paper derive a bound that works under pragmatic assumptions, which can be applied to realistic training settings.

Also the experiments illustrate the flexibility of the framework which setting involving dynamic learning rates, or weight sharing for instance. Among others, experiment in fig1 shows that this framework can be used to derive practical applications such as a dynamic lr scheduler.

Critical weaknesses

I couldn't review this paper's proof with enough attention, so my observations will mainly be about the experimental section part. Although I see why these experiments can be interesting, this part of the text is very descriptive and miss its important objective: to validate that the bound holds in practice. An easy way to show this could be to plot ∥∇L(Wt)∥\|\nabla L(W_t)\| and do a fit test with a function in α1T1/L+β\alpha\frac{1}{T^{1/L}}+\beta In general the experiments are framed as "what works best?" instead of "what are the nominal and limit cases of this framework?". Experiment in fig 1 is a good example of this, as it tells that "adaptive learning rate works better than constant learning rate" where it could illustrate a tightness of condition 9.

Similarly, the experiment in fig2 uses weight repetition, while this setting is correctly motivated, it can also induce confusing factor. Again, tackling the question "would the framework predict this correctly?" would be more valuable than an insight such as "deeper networks train slower if we repeat the weights".

Questions for authors

How does the batch size affect the results ? Given that the proof is for full batch setting, evaluating how the batch size empirically degrades the hypotheses would strengthen the empirical results. Gradient accumulation allows to artificially increase the batch size when the hardware becomes insufficient.

How were the learning rate tuned in the experiments of fig 2 ? An extensive literature shows that optimal lr is width and depth dependent, choosing the same lr for all models can bias results. The same phenomenon can occur with the tuning of alpha in the adaptive setting.

4 comments

Thank you for your review. In the following, we respond to your comments.

Although I see why these experiments can be interesting, this part of the text is very descriptive and miss its important objective: to validate that the bound holds in practice.

We respectfully disagree that the purpose of the experiments is to validate that the bound holds, because the mathematical proof (which is the main contribution of this work) is sufficient to establish the result. Moreover, since the bound is a worst-case analysis over all possible functions, the actual convergence rate in any particular instance may not be precisely 1/T1/L1/T^{1/L}. To illustrate, if in practice the model was initialized at a stationary point, then the algorithm would converge in zero iterations. Instead, our experiments serve to provide additional context for how scaling the learning rate with the parameter norm, as suggested by theory, affects the convergence of gradient descent for a real-world feedforward neural network and dataset. We note that we perform experiments on both standard neural networks and the shared-weights architecture, the latter being a good test case for isolating the impact of depth in this real-world setting.

In addition, we added experiments to the paper illustrating the stated 1/T1/L1/T^{1/L} convergence rate on the hard example used to establish the lower bound. This shows the "limit case" of our theoretical setting where the rate cannot be improved among all deterministic learning rate rules. The plots for these experiments are located in Appendix D.2.

How does the batch size affect the results ? Given that the proof is for full batch setting, evaluating how the batch size empirically degrades the hypotheses would strengthen the empirical results.

Proving theoretical guarantees for the stochastic setting would require significant development of new analytical techniques, so we leave this for future work. However, we ran additional experiments varying the batch size to see how they affect our hypotheses. The plots for these experiments have been added to Appendix D.3. We observe that smaller batch size/increased noise do slow down the convergence, which aligns with theoretical expectations from analyses of SGD/GD on Lipschitz smooth functions. Moreover, for small networks (L=2) and small batch size (32), the advantage of the adaptive learning rate is diminished for earlier iterates. This suggests that the relationship between LL and convergence rate may be more complicated in the stochastic regime, and may depend also all the scale of the noise. However, after extended training, we observe that even when the noise causes the constant learning rate iterates to diverge over time, the adaptive learning rates do eventually converge. This suggests that the learning rate should still be scaled with the parameter norm in order to adapt to the non-uniform smoothness of the loss landscape.

**How were the learning rate tuned in the experiments of fig 2 ? **

The appropriate range of learning rates was chosen using a cyclical learning rate finder algorithm on the two-layer neural network, as detailed in Appendix D. Since deeper neural networks tend to require smaller learning rates, this establishes a general upper bound on the constant learning rate, and we tested a range of values designed to converge stably yet quickly for the range of models considered. As expected, larger constant learning rates lead to faster convergence, but as the learning rate is increased, training becomes more unstable. In contrast, the adaptive learning rates show faster and/or more stable convergence than all these constant learning rates, so it is likely that learning rates outside of this range will also underperform in one way or the other.

Thank you again for your review. As the discussion period is coming to an end, we would like to check if our rebuttal sufficiently addressed your concerns. If so, we would appreciate it if you kindly considered updating your score.

Thank you for the detailed response and additional experiments, which provide valuable insights into the tightness of your bound in a worst-case setting, and also the influence of batch size.

We are glad to hear that our response has addressed your concerns. We kindly ask if you would consider updating your score or review to reflect your current opinion of the work.

Reviewer_eN7wOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary
  • Derives a double polynomial smoothness condition controlling gradient variation through the parameter norms at both endpoints.
  • Uses a parameter-norm- and loss-dependent learning rate to establish min⁡t<T∥∇L(Wt)∥2=O(T−1/L)\min_{t<T} \Vert \nabla \mathcal{L} (W_t)\Vert^2 = O(T^{-1/L}).
  • Avoids specific overparameterization, initialization, and bounded-iterate assumptions, and experimentally investigates a modified adaptive learning rate on CIFAR-10.
Critical strengths
  • Deriving the required smoothness estimates from layerwise activation properties is more informative than assuming global smoothness of the overall loss.
  • Explicitly tracking parameter growth allows the analysis to cover trajectories that move arbitrarily far from initialization.
  • The analysis yields a computable learning-rate rule and distinguishes the general result from the O(1/T)O(1/T) bounded-iterate case.
Critical weaknesses
  • The slow depth-dependent rate and exponentially growing constants leave the practical strength of the guarantee unclear. No matching lower bound establishes that the depth dependence is unavoidable.
  • The experiments fall outside the precise theoretical setting: minibatch optimization and multiclass outputs replace full-batch scalar-output optimization, and theoretical learning-rate constants are replaced by tuned values.
Questions for authors
  • Even for a small network, how large is the learning rate obtained using the actual theoretical constants in Eq. (9), and does it produce meaningful optimization progress?
  • Can the authors provide a lower bound or an example exhibiting the T(−1/L)T^(-1/L) rate? How much can the shared-weight experiment establish about general depth dependence?
  • When the learning rate depends on minibatch loss, it is correlated with the stochastic gradient. Can the analysis accommodate this dependence?
  • Do the gains persist against cosine decay, backtracking, and gradient clipping under comparable tuning budgets?
  • For PDE-residual or Sobolev objectives involving input derivatives, how do the activation regularity requirements and polynomial degree change?
2 comments

Thank you for your review. In the following, we respond to your comments.

The slow depth-dependent rate and exponentially growing constants leave the practical strength of the guarantee unclear. No matching lower bound establishes that the depth dependence is unavoidable/ Can the authors provide a lower bound or an example exhibiting the T^{-1/L} case?

In Appendix C.11 of the updated draft, we have added the proof for the matching lower bound of the 1/T1/L1/T^{1/L} convergence rate, therefore establishing rigorously that the dependence is in fact unavoidable. We show that for any deterministic step-size rule that may depend on the full history of iterates, losses, and gradients, and any TT, there is an LL-layer neural network and loss satisfying Assumptions 3.1-3.2 such that min⁡t=0...T−1∣∇L(Wt)∣2≥T−1/L/(9L)\min_{t=0...T-1}|\nabla\mathcal L(W_t)|^2 \ge T^{-1/L}/(9L). Combined with Theorem 4.8, the 1/T1/L1/T^{1/L} rate is optimal over this class. The bound holds for any deterministic step-size rule, so the slowdown with depth is not caused by the conservative step size in (9). This provably demonstrates that increasing the number of layers makes the loss landscape more ill-conditioned and slows the theoretical convergence rate of gradient descent, strengthening the contribution of our work.

The experiments fall outside the precise theoretical setting: minibatch optimization and multiclass outputs replace full-batch scalar-output optimization, and theoretical learning-rate constants are replaced by tuned values.

We emphasize that the experiments on CIFAR-10 are not for testing or validating the theorem (whose proof is provided in the paper), but to provide additional context for how scaling the learning rate with the parameter norm, as suggested by theory, affects the convergence of gradient descent for a real-world network and dataset. We therefore design our experiments to reflect practice: minibatch gradient descent and finetuning a scaling factor both more closely reflects how neural networks are actually trained. In addition, in Appendix D.2, we added experiments implementing gradient descent on the hard function from the lower bound, illustrating the 1/T1/L1/T^{1/L} convergence rate for varying stationarity tolerances and depths.

When the learning rate depends on minibatch loss, it is correlated with the stochastic gradient. Can the analysis accommodate this dependence?

Our analysis is restricted to the deterministic setting, as extending it to stochastic gradient descent would require significantly new theoretical tools. One key challenge of stochasticity is handling the higher-order moments of noise that arise from the descent lemma, which are not typically bounded by standard variance assumptions. This would require new analytical techniques for identifying suitable bounds that reflect minibatch stochastic sampling. We therefore leave this for future work.

Do the gains persist against cosine decay, backtracking, and gradient clipping under comparable tuning budgets?

Theoretically, the lower bound in Theorem C.14 holds for any history-dependent deterministic step-size rule, including cosine decay and gradient clipping, so none of them can improve on the T−1/LT^{-1/L} worst-case rate that our step size rule attains. While backtracking may achieve an advantage, it requires extra loss evaluations at every step and is not computationally feasible for neural networks.

For PDE-residual or Sobolev objectives involving input derivatives, how do the activation regularity requirements and polynomial degree change?

We expect the analysis to extend by applying the same layer-wise recursion to the input derivatives of each layer. For a loss involving derivatives up to order k, this would require σ′,…,σ(k+1)\sigma', …, \sigma^{(k+1)} to be bounded and σ(k+1)\sigma^{(k+1)} to be Lipschitz. The polynomial degree would also grow with kk, which may lead to a slower convergence rate. This is an interesting future direction of our work.

Thank you again for your review. As the discussion period is coming to an end, we would like to check if our rebuttal sufficiently addressed your concerns. If so, we would appreciate it if you kindly considered updating your score.

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

The paper studies the convergence of gradient descent for general feedforward neural networks without assumptions on initialization, width, dataset, or boundedness of the iterates. The authors derive a generalized Lipschitz smoothness condition in which the gradient variation is controlled by a polynomial of degree 2L-2 in the parameter norms, where L is the network depth. Using this characterization, they propose an adaptive learning rate depending on the parameter norms and loss value, and establish an O(T−1/L)O(T^{-1/L}) best-iterate convergence rate for the squared gradient norm.

Critical strengths

The paper derives an explicit generalized smoothness characterization for multilayer neural networks and leverages it to establish a nonasymptotic stationarity guarantee without assumptions on initialization, width, dataset, or boundedness of the iterates.

Critical weaknesses
  1. The main result only establishes best-iterate first-order stationarity, without guaranteeing convergence to a local or global minimum, convergence of the iterates, or any bound on the limiting loss value. This substantially limits what the result tells us about successful neural network optimization.

  2. The O(T−1/L)O(T^{-1/L}) rate deteriorates significantly with network depth, making the guarantee increasingly weak for deeper networks. It is however unclear whether this dependence on depth is fundamental or an artifact of the analysis. Moreover, the step size that the guarantee requires is far too small to describe any practical training run. The experiments rescale by α‖W0‖2L−2α‖W₀‖^{2L−2}, and tune α\alpha. Therefore, the experiments do not actually test or validate the theorem.

Questions for authors
  1. Can you report ηtη_t from eq. (9), with the actual constants, for the architectures in Section 5? Does gradient descent with that step size make measurable progress in any reasonable number of steps?
6 comments

Thank you for your review. In the following, we respond to your comments.

The main result only establishes best-iterate first-order stationarity...This substantially limits what the result tells us about successful neural network optimization.

We respectfully disagree with this characterization. As discussed thoroughly in our introduction, existing works that guarantee stronger outcomes, such as global convergence of the loss, require strong and often unrealistic assumptions on the initialization, dataset, and model architecture, such as extremely wide networks. However, these works do not explain what happens when such conditions do not hold. For general nonconvex loss functions, it is well-known that gradient descent may converge to suboptimal stationary points such as saddle points, a phenomenon that is well-documented for training neural networks. Therefore, we require a general analysis for this realistic setting under minimal assumptions, which has not been previously established. We also emphasize that best-iterate first-order stationarity is a classic criterion for establishing a convergence rate of gradient descent on nonconvex functions (see "Optimization Methods for Large-Scale Machine Learning," Bouttou, Curtis, and Nocedal 2018), as opposed to other analyses which may show asymptotic convergence as t→∞t \to \infty yet reveal little about how fast the iterates converge.

In addition, because of the generality of our setting, our work yields rigorous insights into neural network optimization. First, our analysis captures the feature learning regime of neural networks by allowing for the iterates to progress to infinity, instead of requiring that they remain in a bounded set as in many prior analyses. Second, we also establish how the conditioning of the neural network loss function affects the convergence rate of gradient descent. As reinforced by the matching lower-bound we added to the paper (see below), our analysis demonstrates that increasing the number of layers makes the loss landscape more ill-conditioned, provably slowing down the convergence rate of gradient descent as 1/T1/L1/T^{1/L}.

The rate deteriorates significantly with network depth, making the guarantee increasingly weak for deeper networks. It is however unclear whether this dependence on depth is fundamental or an artifact of the analysis.

In Appendix C.11 of the updated draft, we have added the proof for the matching lower bound of the 1/T1/L1/T^{1/L} convergence rate, therefore establishing rigorously that the dependence is in fact fundamental and not an artifact of the analysis. We show that for any deterministic step-size rule that may depend on the full history of iterates, losses, and gradients, and any TT, there is an LL-layer neural network and loss satisfying Assumptions 3.1-3.2 such that min⁡t=0...T−1∣∇L(Wt)∣2≥T−1/L/(9L)\min_{t=0...T-1}|\nabla\mathcal L(W_t)|^2 \ge T^{-1/L}/(9L). Combined with Theorem 4.8, the 1/T1/L1/T^{1/L} rate is optimal over this class. The bound holds for any deterministic step-size rule, so the slowdown with depth is not caused by the conservative step size in (9). This provably demonstrates that increasing the number of layers makes the loss landscape more ill-conditioned and slows the theoretical convergence rate of gradient descent, strengthening the contribution of our work.

Moreover, the step size that the guarantee requires is far too small to describe any practical training run... Therefore, the experiments do not actually test or validate the theorem.

We emphasize that the experiments on CIFAR-10 are not for directly testing or validating the theorem (whose proof is provided in the paper), but to provide additional context for how scaling the learning rate with the parameter norm, as suggested by theory, affects the convergence of gradient descent for a real-world network and dataset. Because our theorem is a worst-case analysis (analogous to the standard convergence proof of gradient descent on Lipschitz smooth functions), some real-world instance may not necessarily require the same theoretical guarantees to yield convergence. The theoretically prescribed learning rate is small because it must hold for all possible functions, whereas in practice finetuning a scaling factor more closely reflects how neural networks are actually trained. In addition, in Appendix D.2, we added experiments implementing gradient descent on the hard function from the lower bound, illustrating the 1/T1/L1/T^{1/L} convergence rate for varying stationarity tolerances and depths.

Thank you again for your review. As the discussion period is coming to an end, we would like to check if our rebuttal sufficiently addressed your concerns. If so, we would appreciate it if you kindly considered updating your score.

Thank you to the authors for their detailed rebuttal and additional results. I appreciate the effort to address my concerns, particularly the new lower bound, which is an interesting theoretical addition.

I agree that first-order stationarity is a reasonable convergence criterion in nonconvex optimization, and I recognize the value of establishing a convergence rate without assuming bounded iterates, under such general and relatively mild assumptions. My main reservation concerns the significance of the resulting rate. The upper bound relies on a very conservative learning-rate schedule whose constants deteriorate rapidly with depth, raising questions about how informative the depth dependence is for neural network optimization. I appreciate that the new lower bound establishes the optimality of this dependence in the worst case, independently of the choice of step size. However, the construction uses a specially designed smooth loss for a scalar deep linear network, so it remains unclear whether this slowdown is representative of neural networks trained with standard losses.

I recognize that the generality of the analysis necessarily limits the strength of the guarantees, and I appreciate both the novelty and the mathematical rigor of the results. I also understand that theoretical advances do not always have immediate practical implications. Nevertheless, I remain uncertain about the significance of these results for understanding neural network optimization more broadly.

If the paper is accepted, I would be interested in seeing the authors explore extensions of this framework that address questions of broader interest to the deep learning community, whether through stronger theoretical guarantees under additional assumptions or closer connections to practical optimization dynamics.

Overall, while the rebuttal has strengthened my appreciation of the theoretical contribution, my concerns about its significance remain, and I am inclined to maintain my original assessment.

Comments on the paper

1 comment

We thank the reviewers for their comments, and we have provided detailed responses to each review. We have also made several additions to the appendix of the paper with new theoretical analyses and experiments. For convenience during the rebuttal period, we restrict the new edits (in red) to Appendix C.11, D.2, and D.3. In the camera-ready version, we will update the main body to reference these results as well.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.