# Gradient Descent Optimizes Infinite-Depth ReLU Implicit Networks with Linear Widths

arXiv: https://arxiv.org/abs/2205.07463 · HTML: https://mlsanity.com/paper/2205.07463/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 27 references that are in the map.
- First posted on arXiv 16 May 2022.

## Builds on (most cited first, 21 of 21)

- [Neural Ordinary Differential Equations](https://mlsanity.com/paper/1806.07366/) (2018)
- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Deep Equilibrium Models](https://mlsanity.com/paper/1909.01377/) (2019)
- [Gradient Descent Finds Global Minima of Deep Neural Networks](https://mlsanity.com/paper/1811.03804/) (2018)
- [On Exact Computation with an Infinitely Wide Neural Net](https://mlsanity.com/paper/1904.11955/) (2019)
- [Towards moderate overparameterization: global convergence guarantees for training shallow neural networks](https://mlsanity.com/paper/1902.04674/) (2019)
- [Multiscale Deep Equilibrium Models](https://mlsanity.com/paper/2006.08656/) (2020)
- [Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks](https://mlsanity.com/paper/1811.08888/) (2018)
- [Implicit Deep Learning](https://mlsanity.com/paper/1908.06315/) (2019)
- [Monotone operator equilibrium networks](https://mlsanity.com/paper/2006.08591/) (2020)
- [Dynamics of Deep Neural Networks and Neural Tangent Hierarchy](https://mlsanity.com/paper/1909.08156/) (2019)
- [Tight Bounds on the Smallest Eigenvalue of the Neural Tangent Kernel for Deep ReLU Networks](https://mlsanity.com/paper/2012.11654/) (2020)
- [Stabilizing Equilibrium Models by Jacobian Regularization](https://mlsanity.com/paper/2106.14342/) (2021)
- [Global Convergence of Deep Networks with One Wide Layer Followed by Pyramidal Topology](https://mlsanity.com/paper/2002.07867/) (2020)
- [Trellis Networks for Sequence Modeling](https://mlsanity.com/paper/1810.06682/) (2018)
- [On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widths](https://mlsanity.com/paper/2101.09612/) (2021)
- [Recurrent Stacking of Layers for Compact Neural Machine Translation Models](https://mlsanity.com/paper/1807.05353/) (2018)
- [On the Theory of Implicit Deep Learning: Global Convergence with Implicit Layers](https://mlsanity.com/paper/2102.07346/) (2021)
- [A global convergence theory for deep ReLU implicit networks via over-parameterization](https://mlsanity.com/paper/2110.05645/) (2021)

## Built on by (most cited first, 5 of 5)

- [Wide Neural Networks as Gaussian Processes: Lessons from Deep Equilibrium Models](https://mlsanity.com/paper/2310.10767/) (2023)
- [Global Convergence of Over-parameterized Deep Equilibrium Models](https://mlsanity.com/paper/2205.13814/) (2022)
- [Deep Equilibrium Models are Almost Equivalent to Not-so-deep Explicit Models for High-dimensional Gaussian Mixtures](https://mlsanity.com/paper/2402.02697/) (2024)
- [Global Convergence Rate of Deep Equilibrium Models with General Activations](https://mlsanity.com/paper/2302.05797/) (2023)
- [On the optimization and generalization of overparameterized implicit neural networks](https://mlsanity.com/paper/2209.15562/) (2022)

## Abstract (arXiv)

Implicit deep learning has recently become popular in the machine learning community since these implicit models can achieve competitive performance with state-of-the-art deep networks while using significantly less memory and computational resources. However, our theoretical understanding of when and how first-order methods such as gradient descent (GD) converge on textitnonlinear implicit networks is limited. Although this type of problem has been studied in standard feed-forward networks, the case of implicit models is still intriguing because implicit networks have textitinfinitely many layers. The corresponding equilibrium equation probably admits no or multiple solutions during training. This paper studies the convergence of both gradient flow (GF) and gradient descent for nonlinear ReLU activated implicit networks. To deal with the well-posedness problem, we introduce a fixed scalar to scale the weight matrix of the implicit layer and show that there exists a small enough scaling constant, keeping the equilibrium equation well-posed throughout training. As a result, we prove that both GF and GD converge to a global minimum at a linear rate if the width m of the implicit network is textitlinear in the sample size N, i.e., m=Omega(N).