Answers.Body: <blockquote>
  <p>why neural networks aren't considered contractions, as Geoffrey J. Gordon says in his paper.</p>
  </blockquote>
  <p><a href="https://i.sstatic.net/7jbbO.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/7jbbO.png" alt="enter image description here" /></a></p>
  <p>I am not sure how strongly you mean <em>aren't considered</em>, if you mean it in a strong sense or weak sense.</p>
  <p>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.</p>
  <p><a href="http://motion.me.ucsb.edu/talks/2022-02-10-FBullo-ContractionNeuralNets-NYU.pdf" rel="nofollow noreferrer">Perspectives on Contraction Theory and Neural Networks, Bullo 2022</a><br>
  <a href="https://arxiv.org/pdf/2103.02987.pdf" rel="nofollow noreferrer">Learning-based Adaptive Control using Contraction Theory, Tsukamoto, 2021</a></p>
  <blockquote>
  <p>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 <em>contraction theory</em> 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.</p>
  </blockquote>
  <p>In the weak sense specific NNs can be considered contractions, but in <em>general</em> contractions must be <a href="https://en.wikipedia.org/wiki/Contraction_mapping" rel="nofollow noreferrer">uniformly continuous</a> and it's not clear that in the strong <em>universally true sense</em> for all cases of NNs. There may be some Networks, that for some set of inputs may reveal some discontinuity.</p>
  <p>Also function f must be a mapping of S to itself.
  In image classification we are not mapping S -&gt; S but instead are mapping R^MxNxC -&gt; R^n  where n is the number of classes (or 1 when using integer encoding)</p>
  <p>Its also not clear that all networks would satisfy the condition:</p>
  <blockquote>
  <p>|| f(a) - f(b) ||<br>
  ---------------   &lt;= k &lt; 1 <br>
  || a - b ||</p>
  </blockquote>
  <p>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</p>
  <blockquote>
  <p>a -&gt; a'= [u,u,u,...] <br>
  b -&gt; b'= [v,v,v,...] such that:<br>
  || a'-b' ||/sqrt(n) = sqrt(n*(u-v)) = sqrt(n)*sqrt(u-v) &lt; 1 for all n</p>
  </blockquote>
  <p>So to summarize I would say:</p>
  <ol>
  <li>It depends on how strongly you mean <em>aren't considered</em></li>
  <li>The AI community at large is not familiar with what a contraction mapping is so the connection isn't well developed yet.</li>
  <li>It may be true on case by case basis, but not universally true.</li>
  </ol>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-06-04T07:46:03.787Z
Answers.Text: Please, don't provide screenshots. Copy and paste the actual relevant text (and provide a reference to the original).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-06-04T03:42:25.187Z
Answers.LastActivityDate: 2022-06-04T05:23:00.833Z
Answers.LastEditDate: 2022-06-04T05:23:00.833Z
Answers.UserDisplayName: J.Kent
Body: <p>I'm not sure I understand why neural networks aren't considered contractions, as Geoffrey J. Gordon says in his paper: <a href="http://www.cs.cmu.edu/%7Eggordon/ml95-stable-dp.pdf" rel="nofollow noreferrer">Stable Function Approximation in Dynamic Programming</a>:</p>
  <blockquote>
  <p>&quot;Our theorems in the following sections will be based on two views of function approximators.</p>
  <p>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.</p>
  <p>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.
  ...</p>
  <p>Definition: A function <span class="math-container">$f$</span> from a vector space <span class="math-container">$S$</span> to itself is a <strong>contraction mapping</strong> if, for all points <span class="math-container">$a$</span> and <span class="math-container">$b$</span> in <span class="math-container">$S$</span>, <span class="math-container">$|| f (a) - f(b) || \le \gamma || a-b ||.$</span> Here <span class="math-container">$\gamma$</span>, the contraction factor or modulus, is any real number in <span class="math-container">$[0,1]$</span>. If we merely have <span class="math-container">$|| f (a) - f(b) || \le || a-b ||$</span>, we call <span class="math-container">$f$</span> a nonexpansion.</p>
  <p><span class="math-container">$\qquad$</span> For example, the function <span class="math-container">$f(x) = 5 + \frac{x}{2}$</span> is a contraction with contraction factor <span class="math-container">$\frac{1}{2}$</span>. The identity function is a nonexpansion. All contractions are nonexpansions.</p>
  </blockquote>
  <p>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?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-06-03T17:34:52.307Z
Comments.Text: Can you please define what you mean by "contraction" in this case?
Comments.UserDisplayName: nbro
Tags: <neural-networks><reinforcement-learning><deep-rl>
Title: Why aren't neural networks contractions?
UserDisplayName: Dragoș Constantin
ThreadText: # Why aren't neural networks contractions?
  
  (Asked by: username_0 on 2022-06-03)
  
  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](http://www.cs.cmu.edu/%7Eggordon/ml95-stable-dp.pdf):
  
  > "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?
  
  **Tags:** neural-networks, reinforcement-learning, deep-rl
  
  > **Comments:**
  > **username_1**: Can you please define what you mean by "contraction" in this case?  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2022-06-04. Score: 1 | Accepted answer
  
  > why neural networks aren't considered contractions, as Geoffrey J. Gordon says in his paper.
  
  [![enter image description here](https://i.sstatic.net/7jbbO.png)](https://i.sstatic.net/7jbbO.png)
  
  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](http://motion.me.ucsb.edu/talks/2022-02-10-FBullo-ContractionNeuralNets-NYU.pdf)  
  [Learning-based Adaptive Control using Contraction Theory, Tsukamoto, 2021](https://arxiv.org/pdf/2103.02987.pdf)
  
  > 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](https://en.wikipedia.org/wiki/Contraction_mapping) 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.
  
  > **Comments:**
  > **username_1**: Please, don't provide screenshots. Copy and paste the actual relevant text (and provide a reference to the original).  
  
  ---
  
  