0
$\begingroup$

I'm not sure I understand why neural networks aren't considered contractions, as Geoffrey J. Gordon says in his paper: Stable Function Approximation in Dynamic Programming:

"Our theorems in the following sections will be based on two views of function approximators.

First, we will cast function approximators as expansion or contraction mappings; this distinction captures the essential difference between approximators that can exaggerate changes in their training values, like linear regression and neural nets, and those like k-nearest-neighbor that respond conservatively to changes in their inputs.

Second, we will show that approximate temporal difference learning with some function approximators is equivalent to exact temporal difference learning for a slightly different problem. ...

Definition: A function $f$ from a vector space $S$ to itself is a contraction mapping if, for all points $a$ and $b$ in $S$, $|| f (a) - f(b) || \le \gamma || a-b ||.$ Here $\gamma$, the contraction factor or modulus, is any real number in $[0,1]$. If we merely have $|| f (a) - f(b) || \le || a-b ||$, we call $f$ a nonexpansion.

$\qquad$ For example, the function $f(x) = 5 + \frac{x}{2}$ is a contraction with contraction factor $\frac{1}{2}$. The identity function is a nonexpansion. All contractions are nonexpansions.

I understand that at least in practice they've been shown to greatly exaggerate differences between similar target functions, but I suppose there's a theoretical explanation for this?

$\endgroup$
1
  • $\begingroup$ Can you please define what you mean by "contraction" in this case? $\endgroup$
    – nbro
    Jun 3, 2022 at 17:34

1 Answer 1

1
$\begingroup$

why neural networks aren't considered contractions, as Geoffrey J. Gordon says in his paper.

enter image description here

I am not sure how strongly you mean aren't considered, if you mean it in a strong sense or weak sense.

Contraction theory is probably not very well known in the AI community, but I did find some material to suggest contraction theory is being applied to NNs.

Perspectives on Contraction Theory and Neural Networks, Bullo 2022
Learning-based Adaptive Control using Contraction Theory, Tsukamoto, 2021

The use of DNNs permits real-time implementation of the control law and broad applicability to a variety of nonlinear systems with parametric and nonparametric uncertainties. We show using contraction theory that the aNCM ensures exponential boundedness of the distance between the target and controlled trajectories in the presence of parametric uncertainties of the model, learning errors caused by aNCM approximation, and external disturbances.

In the weak sense specific NNs can be considered contractions, but in general contractions must be uniformly continuous and it's not clear that in the strong universally true sense for all cases of NNs. There may be some Networks, that for some set of inputs may reveal some discontinuity.

Also function f must be a mapping of S to itself. In image classification we are not mapping S -> S but instead are mapping R^MxNxC -> R^n where n is the number of classes (or 1 when using integer encoding)

Its also not clear that all networks would satisfy the condition:

|| f(a) - f(b) ||
--------------- <= k < 1
|| a - b ||

Suppose we had a vector a of size n of all 1's [1,1,1,...] and a vector b of all zeros of size n [0,0,0,...] then their norm || a - b || = sqrt(n) a neural network would need to map

a -> a'= [u,u,u,...]
b -> b'= [v,v,v,...] such that:
|| a'-b' ||/sqrt(n) = sqrt(n*(u-v)) = sqrt(n)*sqrt(u-v) < 1 for all n

So to summarize I would say:

  1. It depends on how strongly you mean aren't considered
  2. The AI community at large is not familiar with what a contraction mapping is so the connection isn't well developed yet.
  3. It may be true on case by case basis, but not universally true.
$\endgroup$
1
  • $\begingroup$ Please, don't provide screenshots. Copy and paste the actual relevant text (and provide a reference to the original). $\endgroup$
    – nbro
    Jun 4, 2022 at 7:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .