Lipschitz constant for four layers in Neural Networks

Consider any two input samples $a$ and $b$ and pass them one by one to a layer $f$ like relu or Linear (fully connected layer). Let's say the distance between the two inputs before being passed to the layer is $||a - b||$.

After, passing through the layer, the distance between the two respective outputs is $||f(a) - f(b)||$. Thus the stretch for that pair is: $$ stretch(a, b) = ||f(a) − f(b)|| / ||a − b|| $$

The Lipschitz constant $L$ is defined as the largest stretch across every possible pair of input samples. There are 3 cases to interpret based on the value of $L$.

• $L < 1$: The layer always pulls data points(samples) closer.
• $L = 1$: The layer never pushes the point apart. Although it could pull them sometime. Remember L is the largest stretch that we get across all data points.
• $L > 1$, e.g. $L = 5$: Some pair of points can end up being 5 times further apart than they started.

ReLU: $L \le 1$

Let $a$ and $b$ be scalar values for now. $relu(x)$ is defined as: $$ relu(x) = max(0, x) $$ There are there cases to consider while comparing the output of relu for two inputs:

• Both inputs are positive — In this case, $relu(a) − relu(b) = a − b$. Thus the difference between the inputs and the outputs remain the same. Thus the input is neither stretched nor shrinked. The gap between them stays the same.
• Both inputs are negatives — When passed through relu, both inputs become zero. Thus the difference between their outputs shrinks to zero. i.e. relu(a) − relu(b) = 0.
• One input is positive and other is negative — In this case as well, the output difference shrinks because the negative input's relu goes to zero. e.g. - the a=3, b=-2. Input gap here is 5. After ReLU, the gap shrinks to 3 because the negative input got pulled up to 0.

Thus across all cases, we can generalize that: $$ |relu(a) − relu(b)| ≤ |a − b| $$

Now instead of scalar inputs, consider vector inputs $a$ and $b$. Now to calculate the distance between two vectors, we take their norm. Thus we get the following relation: $$ ||relu(a) − relu(b)||^2 = \sum (relu(a_i) − relu(b_i))^2 \ \le \sum (a_i - b_i) \ = ||a − b||^2 $$

Therefore we can say: $$ ||relu(a) − relu(b)|| \le ||a-b|| $$ And hence, $L \le 1$ for relu.

Max pooling: $L \le 1$

Max pooling takes a list of inputs and outputs the largest (Here, we assume just one window. For a more generic case, with strided max pooling and overlapping values within windows, $L \le \lceil w / s \rceil$). Take one such list for two vector-inputs with values $(a_1, a_2, ...)$ and $(b_1, b_2, ...)$ respectively. We want to compare max(a) with max(b).

Claim: the output gap is at most the largest gap between corresponding matching inputs: $$ |max(a) − max(b)| \le max_i |a_i − b_i| $$ Make sure you understand the right hand side before we move forward.

Proof: Let $\delta$ be the right hand side we want to prove. Thus let $\delta = max_i|a_i - b_i|$. In words, $\delta$ is the largest gap between matching entries. We want to show that: $$ |max(a) − max(b)| \le \delta $$

Before moving to the proof, we will use two facts that we help us prove the above statement.

Fact 1 — The maximum of a list is at least as big as every entry in it. So $max(b) \ge b_i$ for every $i$.

Fact 2 — Any number is at most its absolute value, and any single gap is at most the largest gap. So: $$ a_i - b_i \le |a_i - b_i| \le \delta $$

Now we will proceed to prove the statement by breaking it down in two cases.

Case 1: $max(a) \ge max(b)$. In this case, the absolute value of the difference, is the same value without as the normal difference. Thus, $$ |max(a) − max(b)| = max(a) − max(b) $$ Now let's call the position where $a$ reaches its maximum by $i$. Thus $max(a) = a_i$. Substitute that in the above equation, we get: $$ |max(a) − max(b)| = a_i − max(b) $$ Now, by Fact 1, we know $max(b) \ge b_i$. ($b_i$ be the corresponding element in $b$ where $a$ is achieving its maximum). Subtracting a bigger number leaves a smaller result so: $$ a_i − max(b) \le a_i − b_i $$ Now, using Fact 2, we get: $$ a_i − b_i \le |a_i − b_i| \le \delta $$ Combining these propositions together, we get: $$ |max(a) − max(b)| \le a_i − max(b) \le a_i − b_i \le \delta $$ This proves the case 1.

Case 2: $max(b) \gt max(a)$. The same argument gets applied with the roles swapped. Now the absolute value equals $max(b) - max(a)$. Let's call the position of the element where $b$ reaches its maximum by $j$. So $max(b) = b_j$.

By Fact 1, we know $max(a) \ge a_j$. Thus: $$ |max(a) − max(b)| \le b_j − max(a) \le b_j − a_j \le \delta $$ This proves the case 2. And the both collectively prove $|max(a) − max(b)| \le \delta. \blacksquare$

Fully connected layer: $L =$ largest singular value of the weight matrix $W$

We know a fully connected layer is: $y = Wx + b$. We claim that the Lipchitz constant for the linear layer is its largest singular value. Let's compute it.

$$ f(p) - f(q) = (Wp + b) - (Wq + b) = W(p - q) $$ Note the bias term disappeared. Let's call $d = p - q$. The stretch is then defined as: $||Wd||/||d||$. So the question changes to figuring out which direction does $W$ stretches the most. Once we figure out the direction of the biggest stretch, then we can apply the same stretch to all other directions. That's the whole purpose of the Lipschitz constant — to figure out the biggest stretch.

Now we know that a matrix can be decomposed into three matrices by SVD. Thus $W = U\Sigma V^T$. If we read right to left, we get:

1. $V^T$: Rotate — rotation doesn't change lengths.
2. $\Sigma$: Stretch — the stretch denotes the stretch along each axes. These are the singular values, and usually we write these as largest first.
3. $U$: Rotate again. — again there will be no change in length.

So this proves that the largest stretch in a linear layer is the largest singular value of the weight matrix $W$. This is important because the direction $v_1$ is most susceptible to attacks. Any small perturbation will amplify the output the largest by the linear layer.

Convolution Layer:

The convolution kernel behaves like a fully connected Layer and hence: $L =$ largest singular value of the weight matrix $W$ when convolution is represented as a linear layer.

A convolution is just doing the computation of the linear layer, while the weights are being shared within inputs. Once we can show that convolution is just linear layer, then the same result as above for the the calculation of the Lipschitz constant gets applied. And thus we will claim that the Lipschitz constant for convolution is the largest singular value, when the convolution kernel is represented as a linear layer.

Look at the case for the linear layer. Each output element is a weighted sum of the inputs. The weights here are values in a particular row of the weight matrix. Particularly the $row_i$ holds the weights to make output $y_i$.

Now look at the convolution with kernel $[1, 2, 3]$ on a 1D input with 6 elements: $[x_0, ..., x_5]$ $$ \begin{aligned} \text{out}_0 &= 1 \cdot x_0 + 2 \cdot x_1 + 3 \cdot x_2 \ \text{out}_1 &= 1 \cdot x_1 + 2 \cdot x_2 + 3 \cdot x_3 \ \text{out}_2 &= 1 \cdot x_2 + 2 \cdot x_3 + 3 \cdot x_4 \ \text{out}_3 &= 1 \cdot x_3 + 2 \cdot x_4 + 3 \cdot x_5 \end{aligned} $$ We see that every output is just a weighted sum of inputs. We can rewrite this a liner layer: $$ \begin{bmatrix} 1 & 2 & 3 & 0 & 0 & 0 \ 0 & 1 & 2 & 3 & 0 & 0 \ 0 & 0 & 1 & 2 & 3 & 0 \ 0 & 0 & 0 & 1 & 2 & 3 \end{bmatrix} $$ Let's call that matrix $W$. Thus $conv(x) = Wx$ exactly. So a convolution layer is a fully connected layer, just with a special shaped weight matrix (weights are shared with inputs). There are certain properties of this weight matrix:

• Sparse — mostly zeros. each output only looks at a small neighborhood.
• Repeated weights — weight sharing. every row is the same kernel, shifted one step right. Note, we can generalize this to 2D and 3D convolution and beyond as well.

Thus, now that we agree that convolution is just a linear layer, the same properties of the linear gets applied. And thus, the Lipschitz constant of the convolution layer, is the largest singular value of the matrix $W$ we created above.

The only problem is the matrix $W$ in this case in practice is enormous. So generally researchers use the Fourier trick to figure out the largest singular value cheaply. The answer still remains the same, only the method of computing the singular value changes.