Answers.Body: <p>After working on it for a while this is what I got.</p>
  <p>Concerning proposition 1 in the paper, a rigorous statement could be the following version of the Gradient Theorem for line integrals:</p>
  <p><strong>Proposition 1.</strong> (Gradient Theorem for Lipschitz Continuous Functions).
  Let <span class="math-container">$U$</span> be an open subset of <span class="math-container">$\mathbb{R}^n$</span>.  If
  <span class="math-container">$F : U \to \mathbb{R}$</span> is Lipschitz continuous, and
  <span class="math-container">$\gamma : [0,1] \to U$</span> is a smooth path such that <span class="math-container">$F$</span> is
  differentiable at <span class="math-container">$\gamma(t)$</span> for almost every <span class="math-container">$t\in [0,1]$</span>, then
  <span class="math-container">$$
      \int_{\gamma} \nabla F(\mathbf{x}) \cdot d\mathbf{x} = F(\gamma(1)) - F(\gamma(0))
      \,.
    $$</span></p>
  <p>I found theorem 1 about symmetry-preserving harder to state rigurously while still fully capturing its intended meaning - this is the best I got:</p>
  <p><strong>Theorem 1.</strong>
  Given <span class="math-container">$i,j\in \{1,\dots,n\}$</span>, <span class="math-container">$i\neq j$</span>, real numbers <span class="math-container">$a&lt;b$</span>, and a
  strictly monotonic smooth path <span class="math-container">$\gamma : [0,1] \to (a,b)^n$</span>
  such that <span class="math-container">$\gamma_i(0)=\gamma_j(0)$</span> and <span class="math-container">$\gamma_i(1)=\gamma_j(1)$</span>,
  then the following statements are equivalent:</p>
  <p>(1) For every <span class="math-container">$t\in [0,1]$</span>, <span class="math-container">$\gamma_i(t) = \gamma_j(t)$</span>.</p>
  <p>(2) For every function <span class="math-container">$F : [a,b]^n \to \mathbb{R}$</span> symmetric
  in <span class="math-container">$x_i$</span> and <span class="math-container">$x_j$</span> and verifying the premises of
  proposition 1 with <span class="math-container">$U=(a,b)^n$</span> we have
  <span class="math-container">$\int_{\gamma} \frac{\partial F(\mathbf{x})}{\partial x_i} \, dx_i
  = \int_{\gamma} \frac{\partial F(\mathbf{x})}{\partial x_j} \,
  dx_j$</span>.</p>
  <p>Further details and proofs: <a href="https://sites.math.northwestern.edu/%7Emlerma/papers-and-preprints/ig-symmetry-preserving.pdf" rel="nofollow noreferrer">Symmetry-Preserving Paths in Integrated Gradients</a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-18T20:30:48.400Z
Answers.LastActivityDate: 2021-03-18T20:30:48.400Z
Answers.UserDisplayName: mlerma54
Body: <p>Theorem 1 (<a href="https://arxiv.org/pdf/1703.01365.pdf#page=5" rel="nofollow noreferrer">page 5</a>)  in the paper about <a href="https://arxiv.org/pdf/1703.01365.pdf" rel="nofollow noreferrer">Integrated Gradients</a> states that</p>
  <blockquote>
  <p>Integrated gradients is the unique path method that is symmetry-preserving.</p>
  </blockquote>
  <p>What I miss is</p>
  <ol>
  <li><p>A precise formulation of the theorem: in particular, the exact properties that must be satisfied by the function <span class="math-container">$f$</span> used in the proof (continuity, differentiability, etc.). Also, should the paths be assumed to be monotonic?</p>
  </li>
  <li><p>A consistent definition of function <span class="math-container">$f$</span> in the proof - note that <span class="math-container">$f$</span> is defined inconsistently, e.g. in the region where <span class="math-container">$x_i&lt;a$</span> and <span class="math-container">$x_j&gt;b$</span>, where it is not clear whether its value should be <span class="math-container">$0$</span> or <span class="math-container">$(b-a)^2$</span>.</p>
  </li>
  </ol>
  <p>Point 2 is easy to fix with an appropriate redefinition (e.g. replacing &quot;if <span class="math-container">$\text{max}(x_i,x_j)\geq 0$</span>&quot; with &quot;else if <span class="math-container">$\text{max}(x_i,x_j)\geq 0$</span>&quot;). What it is not clear if whether there is a redefinition that:</p>
  <ol>
  <li><p>preserves the properties that have been assumed in the rest of the paper, in particular in Proposition 1 (proving completeness), where the function is assumed to be continuous everywhere, and the set of discontinuous points of each of its partial derivatives along each input dimension has measure zero, and</p>
  </li>
  <li><p>the function is a constant for <span class="math-container">$t \notin [t_1,t_2]$</span>.</p>
  </li>
  </ol>
  <p>Does anybody have a precise formulation and full proof of the theorem?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-10T16:51:58.340Z
Comments.Text: Well, I just realized that Proposition 1 in the paper cannot be correct as stated either. In one dimension that proposition is just the (second) Fundamental Theorem of Calculus stated for functions that verify Lebesgue’s integrability criterion, but Cantor's staircase function is a well known counter-example showing that such condition is not enough to ensure the conclusion of the FTC. The premises of the proposition would need to be relaxed somehow, but still keeping them strong enough to be applied to deep networks with functions such as ReLu and max pooling.
Comments.UserDisplayName: mlerma54
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-11T01:52:41.437Z
Comments.Text: Back to Proposition 1, for univariate functions the condition should be "absolutely continuous" (rather than differentiable almost everywhere) - this leads to a suitable generalization of the Fundamental Theorem of Calculus that can be applied to functions occurring in deep networks, but I am still wondering how to generalize the gradient theorem in a similar way so it can be applied to functions implemented by deep networks. That generalization would contain premises to be used in the formulation of Theorem 1.
Comments.UserDisplayName: mlerma54
Tags: <deep-learning><image-recognition><papers><math>
Title: Is there a full and precise formulation of Theorem 1 in the Integrated Gradients paper?
UserDisplayName: mlerma54
ThreadText: # Is there a full and precise formulation of Theorem 1 in the Integrated Gradients paper?
  
  (Asked by: username_0 on 2021-03-07)
  
  Theorem 1 ([page 5](https://arxiv.org/pdf/1703.01365.pdf#page=5)) in the paper about [Integrated Gradients](https://arxiv.org/pdf/1703.01365.pdf) states that
  
  > Integrated gradients is the unique path method that is symmetry-preserving.
  
  What I miss is
  
  1. A precise formulation of the theorem: in particular, the exact properties that must be satisfied by the function $f$ used in the proof (continuity, differentiability, etc.). Also, should the paths be assumed to be monotonic?
  2. A consistent definition of function $f$ in the proof - note that $f$ is defined inconsistently, e.g. in the region where $x\_i and $x\_j>b$, where it is not clear whether its value should be $0$ or $(b-a)^2$.
  
  Point 2 is easy to fix with an appropriate redefinition (e.g. replacing "if $\text{max}(x\_i,x\_j)\geq 0$" with "else if $\text{max}(x\_i,x\_j)\geq 0$"). What it is not clear if whether there is a redefinition that:
  
  1. preserves the properties that have been assumed in the rest of the paper, in particular in Proposition 1 (proving completeness), where the function is assumed to be continuous everywhere, and the set of discontinuous points of each of its partial derivatives along each input dimension has measure zero, and
  2. the function is a constant for $t \notin [t\_1,t\_2]$.
  
  Does anybody have a precise formulation and full proof of the theorem?
  
  **Tags:** deep-learning, image-recognition, papers, math
  > **Comments:**
  > **username_0**: Well, I just realized that Proposition 1 in the paper cannot be correct as stated either. In one dimension that proposition is just the (second) Fundamental Theorem of Calculus stated for functions that verify Lebesgue’s integrability criterion, but Cantor's staircase function is a well known counter-example showing that such condition is not enough to ensure the conclusion of the FTC. The premises of the proposition would need to be relaxed somehow, but still keeping them strong enough to be applied to deep networks with functions such as ReLu and max pooling.  
  > **username_0**: Back to Proposition 1, for univariate functions the condition should be "absolutely continuous" (rather than differentiable almost everywhere) - this leads to a suitable generalization of the Fundamental Theorem of Calculus that can be applied to functions occurring in deep networks, but I am still wondering how to generalize the gradient theorem in a similar way so it can be applied to functions implemented by deep networks. That generalization would contain premises to be used in the formulation of Theorem 1.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_0 on 2021-03-18. Score: 1
  
  After working on it for a while this is what I got.
  
  Concerning proposition 1 in the paper, a rigorous statement could be the following version of the Gradient Theorem for line integrals:
  
  **Proposition 1.** (Gradient Theorem for Lipschitz Continuous Functions).
  Let $U$ be an open subset of $\mathbb{R}^n$. If
  $F : U \to \mathbb{R}$ is Lipschitz continuous, and
  $\gamma : [0,1] \to U$ is a smooth path such that $F$ is
  differentiable at $\gamma(t)$ for almost every $t\in [0,1]$, then
  $$
  \int\_{\gamma} \nabla F(\mathbf{x}) \cdot d\mathbf{x} = F(\gamma(1)) - F(\gamma(0))
  \,.
  $$
  
  I found theorem 1 about symmetry-preserving harder to state rigurously while still fully capturing its intended meaning - this is the best I got:
  
  **Theorem 1.**
  Given $i,j\in \{1,\dots,n\}$, $i\neq j$, real numbers $a, and a
  strictly monotonic smooth path $\gamma : [0,1] \to (a,b)^n$
  such that $\gamma\_i(0)=\gamma\_j(0)$ and $\gamma\_i(1)=\gamma\_j(1)$,
  then the following statements are equivalent:
  
  (1) For every $t\in [0,1]$, $\gamma\_i(t) = \gamma\_j(t)$.
  
  (2) For every function $F : [a,b]^n \to \mathbb{R}$ symmetric
  in $x\_i$ and $x\_j$ and verifying the premises of
  proposition 1 with $U=(a,b)^n$ we have
  $\int\_{\gamma} \frac{\partial F(\mathbf{x})}{\partial x\_i} \, dx\_i
  = \int\_{\gamma} \frac{\partial F(\mathbf{x})}{\partial x\_j} \,
  dx\_j$.
  
  Further details and proofs: [Symmetry-Preserving Paths in Integrated Gradients](https://sites.math.northwestern.edu/%7Emlerma/papers-and-preprints/ig-symmetry-preserving.pdf)
  
  
  ---
  
  