Proxy Convexity: A Unified Framework for the Analysis of Neural Networks Trained by Gradient Descent

Spencer Frei, Quanquan Gu

Abstract

Although the optimization objectives for learning neural networks are highly non-convex, gradient-based methods have been wildly successful at learning neural networks in practice. This juxtaposition has led to a number of recent studies on provable guarantees for neural networks trained by gradient descent. Unfortunately, the techniques in these works are often highly specific to the particular setup in each problem, making it difficult to generalize across different settings. To address this drawback in the literature, we propose a unified non-convex optimization framework for the analysis of neural network training. We introduce the notions of proxy convexity and proxy Polyak-Lojasiewicz (PL) inequalities, which are satisfied if the original objective function induces a proxy objective function that is implicitly minimized when using gradient methods. We show that gradient descent on objectives satisfying proxy convexity or the proxy PL inequality leads to efficient guarantees for proxy objective functions. We further show that many existing guarantees for neural networks trained by gradient descent can be unified through proxy convexity and proxy PL inequalities.

Introduction

In classical optimization theory, convexity is the "gold standard." A convex function ensures that any local minimum is globally optimal, providing a clear path for gradient-based algorithms to succeed. However, the loss landscapes of modern neural networks are notoriously non-convex, characterized by complex topologies, plateaus, and potentially sub-optimal stationary points. Despite this theoretical hurdle, Gradient Descent (GD) and its variants are remarkably effective in practice.

To bridge this gap between theory and practice, the research community has produced numerous "provable guarantees" for specific architectures and regimes. For instance, proofs exist for very wide networks (the Neural Tangent Kernel or NTK regime) and for single-neuron models. However, these proofs are often "bespoke"—the mathematical machinery used to analyze a ReLU neuron does not easily extend to a deep residual network. This paper introduces a unified framework to identify the underlying structure that makes these disparate non-convex problems solvable.

The Proxy Framework

The authors propose two primary mathematical definitions to bridge the gap between non-convexity and convergence: Proxy Convexity and Proxy Polyak-Łojasiewicz (PL) inequalities.

The general optimization problem addressed by the proxy framework.

Proxy Convexity

Instead of requiring the objective function $f$ to be convex, the framework assumes the existence of "proxy" functions $g$ and $h$. A function $f$ is proxy-convex if its gradient $\nabla f(w)$ always points in a direction that reduces the discrepancy between $g(w)$ and $h(v)$. Essentially, while $f$ itself may be non-convex, the trajectory of gradient descent acts as if it is minimizing a better-behaved, implicit objective.

Proxy PL Inequality

The standard PL inequality suggests that the gradient's magnitude grows with the distance to the minimum. The "Proxy" version generalizes this by allowing for a slack term ($\xi$): $$\|\nabla f(w)\|^2 \ge \mu (f(w) - f^*) - \xi$$ This slack term is crucial for neural networks, as it accounts for the fact that a stationary point (where the gradient vanishes) might not be the absolute global minimum, but may still be "good enough" or approximately optimal in a practical sense.

Convergence and Unification

By establishing these proxy conditions, the authors derive general convergence theorems. They prove that if a loss function satisfies proxy convexity or the proxy PL inequality, standard Gradient Descent will efficiently converge to a point that is nearly optimal relative to the proxy objective. For proxy PL objectives, the number of iterations $T$ required to reach an $\epsilon$-approximate solution scales polynomially with $1/\epsilon$.

A significant contribution of this work is the unification of existing literature. The authors demonstrate that several landmark results in deep learning theory are actually specific instances of this framework:

  • Deep Linear Networks and Leaky ReLU Neurons: These satisfy the standard PL inequality.
  • Wide ReLU Networks (NTK Regime): These can be analyzed through the lens of Proxy PL.
  • Single ReLU Neurons under Squared Loss: These exhibit Proxy Convexity.

Furthermore, the framework allowed the authors to provide a new, simplified proof for the convergence of one-hidden-layer networks outside the NTK regime, demonstrating its utility beyond mere unification.

Conclusion

The Proxy Convexity framework provides a powerful language for understanding why non-convex neural networks are trainable. By shifting the focus from the literal loss function to an implicit proxy, it explains the success of gradient descent across diverse settings.

However, challenges remain. The "crux of the problem" for any new architecture is the discovery of the appropriate proxy functions $g$ and $h$. Additionally, while the framework handles sub-optimality via slack terms, these bounds can sometimes be loose for complex, non-overparameterized architectures. Future research may focus on tightening these proxies and extending the framework to stochastic optimization methods like SGD.

Summary updated

Abstract

Although the optimization objectives for learning neural networks are highly non-convex, gradient-based methods have been wildly successful at learning neural networks in practice. This juxtaposition has led to a number of recent studies on provable guarantees for neural networks trained by gradient descent. Unfortunately, the techniques in these works are often highly specific to the particular setup in each problem, making it difficult to generalize across different settings. To address this drawback in the literature, we propose a unified non-convex optimization framework for the analysis of neural network training. We introduce the notions of proxy convexity and proxy Polyak-Lojasiewicz (PL) inequalities, which are satisfied if the original objective function induces a proxy objective function that is implicitly minimized when using gradient methods. We show that gradient descent on objectives satisfying proxy convexity or the proxy PL inequality leads to efficient guarantees for proxy objective functions. We further show that many existing guarantees for neural networks trained by gradient descent can be unified through proxy convexity and proxy PL inequalities.
BibTeX
@inproceedings{frei2021proxy,
  author = {Spencer Frei and Quanquan Gu},
  title = {{Proxy Convexity: A Unified Framework for the Analysis of Neural Networks Trained by Gradient Descent}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=NVpGLJUuPx5},
}
Figure