Learning with Gradient Descent and Weakly Convex Losses

Dominic Richards, Mike Rabbat

Abstract

We study the learning performance of gradient descent when the empirical risk is weakly convex, namely, the smallest negative eigenvalue of the empirical risk's Hessian is bounded in magnitude. By showing that this eigenvalue can control the stability of gradient descent, generalisation error bounds are proven that hold under a wider range of step sizes compared to previous work. Out of sample guarantees are then achieved by decomposing the test error into generalisation, optimisation and approximation errors, each of which can be bounded and traded off with respect to algorithmic parameters, sample size and magnitude of this eigenvalue. In the case of a two layer neural network, we demonstrate that the empirical risk can satisfy a notion of local weak convexity, specifically, the Hessian's smallest eigenvalue during training can be controlled by the normalisation of the layers, i.e., network scaling. This allows test error guarantees to then be achieved when the population risk minimiser satisfies a complexity assumption. By trading off the network complexity and scaling, insights are gained into the implicit bias of neural network scaling, which are further supported by experimental findings.

Introduction

In modern machine learning, models are typically trained by minimizing empirical risk using Gradient Descent (GD). While the theoretical foundations for convex loss functions are robust, modern architectures like deep neural networks present highly non-convex landscapes. Standard theory for non-convex GD often suggests that the algorithm should be highly unstable unless trained with impractically small step sizes (typically $O(1/t)$). This creates a significant disconnect between theoretical guarantees and the practical success of GD in deep learning.

This paper bridges this gap by introducing a framework based on weak convexity. By assuming the loss function's curvature isn't too sharply negative—specifically, that the smallest negative eigenvalue of the Hessian is bounded—the authors prove that GD remains stable and generalizes well even with larger, more realistic step sizes.

Theoretical Framework: Pointwise Weak Convexity

The core of the paper's approach is the concept of Pointwise Weak Convexity. Rather than requiring global convexity, the authors focus on the curvature specifically along the path taken by the gradient descent algorithm. They demonstrate that the stability of GD is governed by the magnitude of the most negative eigenvalue of the Hessian matrix.

If the landscape does not curve downward too sharply, the algorithm maintains algorithmic stability, meaning the model's output does not change drastically if a single data point in the training set is modified. This stability is the key to proving generalization: a stable algorithm is less likely to overfit the specific noise of a training set.

Error Decomposition and Generalization

To provide a comprehensive guarantee of out-of-sample performance (Test Error), the authors decompose the total error into three distinct components:

  1. Generalization Error: The gap between training loss and population loss, bounded using the stability of the weakly convex landscape.
  2. Optimization Error: The degree to which GD successfully minimizes the training loss.
  3. Approximation Error: The statistical bias introduced by the specific structural constraints of the model and the non-convexity of the objective.

By leveraging weak convexity, the authors prove a generalization error bound of $O(t^{1-\alpha}/N)$, where $t$ is the number of iterations and $N$ is the sample size. This matches the optimal rates found in purely convex settings but holds under much milder step-size constraints ($O(1/t^\alpha)$ instead of $O(1/t)$).

Neural Network Scaling and Implicit Bias

The authors apply this framework to two-layer neural networks, exploring how network width and a scaling parameter ($c$) influence the Hessian's eigenvalues. Their analysis reveals two critical insights:

  • Width as a Stabilizer: The weak convexity parameter is found to be inversely proportional to the network's width. This suggests that wider networks are inherently more stable, providing a theoretical justification for why overparameterized models can be trained longer without immediate overfitting.
  • Implicit Bias of Scaling: The scaling parameter $c$ acts as a dial for the network's implicit bias. While increasing $c$ allows the network to learn more complex models (weights with larger norms), it simultaneously makes the approximation of simpler models more difficult. This highlights a fundamental trade-off between model complexity and the ease of optimization.

Empirical Validation

The theoretical claims were tested using subsets of the HIGGS, SUSY, and COVTYPE datasets from the UCI Machine Learning Repository. The experiments confirmed that:

  1. As the scaling parameter ($c$) increases, the Frobenius norm of the learned weights increases, supporting the complexity trade-off theory.
  2. The estimated population risk (test error) consistently decreases as the network width increases, aligning with the prediction that width improves stability and learning performance.

Conclusion

By shifting the focus from global non-convexity to bounded negative curvature (weak convexity), this work provides a more realistic theoretical foundation for gradient descent. It explains why larger step sizes and wider architectures contribute to the success of neural network training. Future work remains to extend these stability bounds to Stochastic Gradient Descent (SGD) and deeper architectures, where the interaction between noise and curvature becomes more complex.

Summary updated

Abstract

We study the learning performance of gradient descent when the empirical risk is weakly convex, namely, the smallest negative eigenvalue of the empirical risk's Hessian is bounded in magnitude. By showing that this eigenvalue can control the stability of gradient descent, generalisation error bounds are proven that hold under a wider range of step sizes compared to previous work. Out of sample guarantees are then achieved by decomposing the test error into generalisation, optimisation and approximation errors, each of which can be bounded and traded off with respect to algorithmic parameters, sample size and magnitude of this eigenvalue. In the case of a two layer neural network, we demonstrate that the empirical risk can satisfy a notion of local weak convexity, specifically, the Hessian's smallest eigenvalue during training can be controlled by the normalisation of the layers, i.e., network scaling. This allows test error guarantees to then be achieved when the population risk minimiser satisfies a complexity assumption. By trading off the network complexity and scaling, insights are gained into the implicit bias of neural network scaling, which are further supported by experimental findings.
BibTeX
@inproceedings{richards2021learning,
  author = {Dominic Richards and Mike Rabbat},
  title = {{Learning with Gradient Descent and Weakly Convex Losses}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2021},
}
Figure