Skip to main content

🌀 1-Lipschitz and stability

Status:Preliminary
Tags:Needs revisionFormulationStability
Last modified:

Lipschitzness​

Let us start with a definition. A function f:Rn→Rmf:\mathbb{R}^n\to\mathbb{R}^m is 1-Lipschitz if:

∥f(x)−f(y)∥≤∥x−y∥\|f(x)-f(y)\| \leq \|x-y\|

for all x,y∈Rnx,y\in\mathbb{R}^n.

What does this all mean?. I know. It may look like a random math definition, but it has a very intuitive meaning. In plain english, this means that if you change the input a little bit, the output will also change only a little bit. In other words, the function is not "stretching" the input too much.

From a systems point of view, this is the definition of a sort of overall gain. In fact, we can define the Lipschitzness as the maximum gain of the function:

L=sup⁡x≠y∥f(x)−f(y)∥∥x−y∥.L =\sup_{x\neq y} \frac{\|f(x)-f(y)\|}{\|x-y\|}.

In other words, this constant is how much the input gets amplified or attenuated by the function mapping.

Why do we care about this property?. You might be wondering that. In order to answer that we need to change gears from general discrete updates of training neural networks, to dynamical systems.

The gradient feedbackloop and network stability​

Recall the standard training loop using SGD in continuous time:

dθdt=−η∇θL(θ).\frac{d\theta}{dt} = -\eta \nabla_\theta \mathcal{L}(\theta).

Now let's imagine a simple 2-dense layer network like this:

xx
θ1:W1,b1\theta_1: W_1,b_1
y1y_1
θ2:W2,b2\theta_2: W_2,b_2
y^\hat{y}

Let's explicitly write the function and the intermediate activations:

{y1=W1x+b1,y^=W2y1+b2.\begin{cases} y_1 &= W_1x+b_1, \\ \hat{y} &= W_2y_1+b_2. \end{cases}

The loss is:

L(θ1,θ2)=ℓ(y^,ytrue).\mathcal{L}(\theta_1,\theta_2) = \ell(\hat{y},y_{\text{true}}).

The gradient with respect to each parameter is:

θ2:{∇W2L=∂ℓ∂y^∂y^∂W2=∂ℓ∂y^∂(W2y1+b2)∂W2=∂ℓ∂y^y1∇b2L=∂ℓ∂y^∂y^∂b2=∂ℓ∂y^∂(W2y1+b2)∂b2=∂ℓ∂y^θ1:{∇W1L=∂ℓ∂y^∂y^∂y1∂y1∂W1=∂ℓ∂y^∂(W2y1+b2)∂y1∂(W1x+b1)∂W1=∂ℓ∂y^W2x∇b1L=∂ℓ∂y^∂y^∂y1∂y1∂b1=∂ℓ∂y^∂(W2y1+b2)∂y1∂(W1x+b1)∂b1=∂ℓ∂y^W2\theta_2: \begin{cases} \nabla_{W_2}\mathcal{L} &= \frac{\partial \ell}{\partial \hat{y}} \frac{\partial \hat{y}}{\partial W_2} = \frac{\partial \ell}{\partial \hat{y}} \frac{\partial (W_2y_1+b_2)}{\partial W_2} = \frac{\partial \ell}{\partial \hat{y}} y_1 \\[8pt] \nabla_{b_2}\mathcal{L} &= \frac{\partial \ell}{\partial \hat{y}} \frac{\partial \hat{y}}{\partial b_2} = \frac{\partial \ell}{\partial \hat{y}} \frac{\partial (W_2y_1+b_2)}{\partial b_2} = \frac{\partial \ell}{\partial \hat{y}} \\[8pt] \end{cases} \qquad \theta_1: \begin{cases} \nabla_{W_1}\mathcal{L} &= \frac{\partial \ell}{\partial \hat{y}} \frac{\partial \hat{y}}{\partial y_1} \frac{\partial y_1}{\partial W_1} = \frac{\partial \ell}{\partial \hat{y}} \frac{\partial (W_2y_1+b_2)}{\partial y_1} \frac{\partial (W_1x+b_1)}{\partial W_1} = \frac{\partial \ell}{\partial \hat{y}} W_2 x \\[8pt] \nabla_{b_1}\mathcal{L} &= \frac{\partial \ell}{\partial \hat{y}} \frac{\partial \hat{y}}{\partial y_1} \frac{\partial y_1}{\partial b_1} = \frac{\partial \ell}{\partial \hat{y}} \frac{\partial (W_2y_1+b_2)}{\partial y_1} \frac{\partial (W_1x+b_1)}{\partial b_1} = \frac{\partial \ell}{\partial \hat{y}} W_2 \end{cases}

But recall that y1y_1 is:

y1=W1x+b1.y_1=W_1x+b_1.

But now note what happens when we write the update rule for each parameter, in terms of these gradients:

{W2˙=−η∂ℓ∂y^(W1x+b1)b2˙=−η∂ℓ∂y^W1˙=−η∂ℓ∂y^W2xb1˙=−η∂ℓ∂y^W2\begin{cases} \dot{W_2} = -\eta \frac{\partial \ell}{\partial \hat{y}} (W_1x + b_1) \\ \dot{b_2} = -\eta \frac{\partial \ell}{\partial \hat{y}} \\ \dot{W_1} = -\eta \frac{\partial \ell}{\partial \hat{y}} W_2 x \\ \dot{b_1} = -\eta \frac{\partial \ell}{\partial \hat{y}} W_2 \end{cases}

This system has the form:

θ˙=A(θ)θ+b(θ)+c(θ)x,\dot{\theta} = A(\theta)\theta + b(\theta) + c(\theta)x,

where the matrix A(θ)A(\theta) depends on the parameters themselves. This is a nonlinear dynamical system(non-linear because the ∂ℓ∂y^\frac{\partial\ell}{\partial\hat{y}} term will most likely -depending on the specific loss function- depend on y2y_2, which depends on θ\theta), and its stability depends on the eigenvalues of the Jacobian of the update rule. In particular, the gain of the second layer W2W_2 directly affects the stability of the updates of the first layer θ1\theta_1. If W2W_2 has a large norm, then the updates of θ1\theta_1 can become very large, which can lead to instability in the training process.

This makes it clear that the update of θ1\theta_1 depends on the gain of the second layer, which on its turn depends on the gain of the first layer. If the gain of the second layer is too high, then the update of θ1\theta_1 can become unstable, even if the loss landscape is smooth. In other words, the training update itself creates two feedback loops, as captured by the following diagram:

Key insight

The stability of the training process is not only governed by the smoothness of the loss landscape, but also by the gain of the network itself. The gain of the network can amplify the updates in a way that can lead to instability, even if the loss landscape is smooth. This is why controlling the Lipschitzness of the network is important for stable training.

So what would the ideal Lipschitzness be?​

The ideal Lipschitzness for stability is 1. If the network is 1-Lipschitz, then the gain of the network is at most 1, which means that the updates will not be amplified too much, and the training process will be stable. If the network is not 1-Lipschitz, then the gain can be greater than 1, which can lead to instability in the training process. Therefore, controlling the Lipschitzness of the network is crucial for ensuring stable training.