How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks — part 6/11

Cleaned-text code points [77792, 91985). Bibliography omitted here; source.md includes it.

Recall that we assume our training data { ( 𝒙 i , y i ) } i = 1 n \{(\bm{x}_{i},y_{i})\}_{i=1}^{n} satisfies for any 𝒘 ∈ ℝ d \bm{w}\in\mathbb{R}^{d} , there exist d d linearly independent { 𝒙 i 𝒘 } i = 1 d ⊂ 𝑿 \{\bm{x}_{i}^{\bm{w}}\}_{i=1}^{d}\subset\bm{X} , where 𝑿 = { 𝒙 i } i = 1 n \bm{X}=\{\bm{x}_{i}\}_{i=1}^{n} , so that 𝒘 ⊤ ​ 𝒙 i 𝒘 ≥ 0 \bm{w}^{\top}\bm{x}_{i}^{\bm{w}}\geq 0 and − 𝒙 i 𝒘 ∈ 𝑿 -\bm{x}_{i}^{\bm{w}}\in\bm{X} for i = 1 . . d i=1..d , e.g., an orthogonal basis of ℝ d \mathbb{R}^{d} and their opposite vectors. We will show that under this data regime, we have

(a) for any particular 𝒘 \bm{w} , there indeed exist a set of λ i \lambda_{i} that can satisfy the constraints Eqn. 59 and Eqn. 61 for this particular 𝒘 \bm{w} .

(b) For any 𝒘 1 \bm{w}_{1} and 𝒘 2 \bm{w}_{2} that activate the exact same set of { 𝒙 i } \{\bm{x}_{i}\} , the same set of λ i \lambda_{i} can satisfy the constraints Eqn. 59 and Eqn. 61 of both 𝒘 1 \bm{w}_{1} and 𝒘 2 \bm{w}_{2} .

(c) Whenever we rotate a 𝒘 1 \bm{w}_{1} to a 𝒘 2 \bm{w}_{2} so that the set of 𝒙 i \bm{x}_{i} being activated changed, we can still find λ i \lambda_{i} that satisfy constraint of both 𝒘 1 \bm{w}_{1} and 𝒘 2 \bm{w}_{2} .

Combining (a), (b) and (c) implies there exists a set of λ \lambda that satisfy the constraints for all w w . Hence, it remains to show these three claims.

We first prove Claim (a). For each 𝒘 \bm{w} , we must find a set of λ i \lambda_{i} so that the following hold. 𝜷 𝒘 ( k ) = c ⋅ ∑ i = 1 n λ i ⋅ 𝒙 i ( k ) ⋅ 𝕀 ⁡ ( 𝒘 ⊤ ​ 𝒙 i ≥ 0 ) , \displaystyle\bm{\beta}_{\bm{w}}^{(k)}=c\cdot\sum\limits_{i=1}^{n}\lambda_{i}\cdot\bm{x}_{i}^{(k)}\cdot\mathbb{I}\left(\bm{w}^{\top}\bm{x}_{i}\geq 0\right), 𝜷 𝒘 ′ = 𝒘 ⊤ ​ 𝜷 𝒘 \displaystyle\bm{\beta}_{\bm{w}}^{\prime}=\bm{w}^{\top}\bm{\beta}_{\bm{w}} 𝜷 𝒘 + 𝜷 𝒘 ′ ⋅ 𝒘 = 2 ​ 𝜷 g \displaystyle\bm{\beta}_{\bm{w}}+\bm{\beta}_{\bm{w}}^{\prime}\cdot\bm{w}=2\bm{\beta}_{g} Here, 𝜷 g \bm{\beta}_{g} and 𝒘 \bm{w} are fixed, and 𝒘 \bm{w} is a vector on the unit sphere. It is easy to see that 𝜷 𝒘 \bm{\beta}_{\bm{w}} is then determined by 𝜷 g \bm{\beta}_{g} and 𝒘 \bm{w} , and there indeed exists a solution (solving a consistent linear system). Hence we are left with a linear system with d d linear equations 𝜷 𝒘 ( k ) = c ⋅ ∑ i = 1 n λ i ⋅ 𝒙 i ( k ) ⋅ 𝕀 ( 𝒘 ⊤ 𝒙 i ≥ 0 ) ∀ k ∈ [ d ] \bm{\beta}_{\bm{w}}^{(k)}=c\cdot\sum\limits_{i=1}^{n}\lambda_{i}\cdot\bm{x}_{i}^{(k)}\cdot\mathbb{I}\left(\bm{w}^{\top}\bm{x}_{i}\geq 0\right)\;\;\;\forall k\in[d] to solve with free variables being λ i \lambda_{i} so that 𝒘 \bm{w} activates 𝒙 i \bm{x}_{i} , i.e., 𝒘 ⊤ ​ 𝒙 i ≥ 0 \bm{w}^{\top}\bm{x}_{i}\geq 0 . Because the training data { ( 𝒙 i , y i ) } i = 1 n \{(\bm{x}_{i},y_{i})\}_{i=1}^{n} satisfies for any 𝒘 \bm{w} , there exist at least d d linearly independent 𝒙 i \bm{x}_{i} that activate 𝒘 \bm{w} . This guarantees for any 𝒘 \bm{w} we must have at least d d free variables. It follows that there must exist solutions λ i \lambda_{i} to the linear system. This proves Claim (a).

Next, we show that (b) for any 𝒘 1 \bm{w}_{1} and 𝒘 2 \bm{w}_{2} that activate the exact same set of { 𝒙 i } \{\bm{x}_{i}\} , the same set of λ i \lambda_{i} can satisfy the constraints Eqn. 59 and Eqn. 61 of both 𝒘 1 \bm{w}_{1} and 𝒘 2 \bm{w}_{2} . Because 𝒘 1 \bm{w}_{1} and 𝒘 2 \bm{w}_{2} are activated by the same set of 𝒙 i \bm{x}_{i} , this implies 𝜷 𝒘 1 = c ⋅ ∑ i = 1 n λ i ⋅ 𝒙 i ⋅ 𝕀 ⁡ ( 𝒘 1 ⊤ ​ 𝒙 i ≥ 0 ) = c ⋅ ∑ i = 1 n λ i ⋅ 𝒙 i ⋅ 𝕀 ⁡ ( 𝒘 2 ⊤ ​ 𝒙 i ≥ 0 ) = 𝜷 𝒘 2 \displaystyle\bm{\beta}_{\bm{w}_{1}}=c\cdot\sum\limits_{i=1}^{n}\lambda_{i}\cdot\bm{x}_{i}\cdot\mathbb{I}\left(\bm{w}_{1}^{\top}\bm{x}_{i}\geq 0\right)=c\cdot\sum\limits_{i=1}^{n}\lambda_{i}\cdot\bm{x}_{i}\cdot\mathbb{I}\left(\bm{w}_{2}^{\top}\bm{x}_{i}\geq 0\right)=\bm{\beta}_{\bm{w}_{2}} Since λ i \lambda_{i} already satisfy constraint Eqn. 59 for 𝒘 1 \bm{w}_{1} , they also satisfy that for 𝒘 2 \bm{w}_{2} . Thus, it remains to show that 𝜷 𝒘 1 + 𝜷 𝒘 1 ′ ⋅ 𝒘 1 = 𝜷 𝒘 2 + 𝜷 𝒘 2 ′ ⋅ 𝒘 1 \bm{\beta}_{\bm{w}_{1}}+\bm{\beta}_{\bm{w}_{1}}^{\prime}\cdot\bm{w}_{1}=\bm{\beta}_{\bm{w}_{2}}+\bm{\beta}_{\bm{w}_{2}}^{\prime}\cdot\bm{w}_{1} assuming 𝜷 𝒘 1 = 𝜷 𝒘 2 \bm{\beta}_{\bm{w}_{1}}=\bm{\beta}_{\bm{w}_{2}} , 𝜷 𝒘 1 ′ = 𝒘 1 ⊤ ​ 𝜷 𝒘 1 \bm{\beta}_{\bm{w}_{1}}^{\prime}=\bm{w}_{1}^{\top}\bm{\beta}_{\bm{w}_{1}} , and 𝜷 𝒘 2 ′ = 𝒘 2 ⊤ ​ 𝜷 𝒘 2 \bm{\beta}_{\bm{w}_{2}}^{\prime}=\bm{w}_{2}^{\top}\bm{\beta}_{\bm{w}_{2}} . This indeed holds because 𝜷 𝒘 1 + 𝜷 𝒘 1 ′ ⋅ 𝒘 1 = 𝜷 𝒘 2 + 𝜷 𝒘 2 ′ ⋅ 𝒘 2 \displaystyle\bm{\beta}_{\bm{w}_{1}}+\bm{\beta}_{\bm{w}_{1}}^{\prime}\cdot\bm{w}_{1}=\bm{\beta}_{\bm{w}_{2}}+\bm{\beta}_{\bm{w}_{2}}^{\prime}\cdot\bm{w}_{2} ⟺ \displaystyle\Longleftrightarrow\;\;\; 𝜷 𝒘 1 ′ ⋅ 𝒘 1 ⊤ = 𝜷 𝒘 2 ′ ⋅ 𝒘 2 ⊤ \displaystyle\bm{\beta}_{\bm{w}_{1}}^{\prime}\cdot\bm{w}_{1}^{\top}=\bm{\beta}_{\bm{w}_{2}}^{\prime}\cdot\bm{w}_{2}^{\top} ⟺ \displaystyle\Longleftrightarrow\;\;\; 𝒘 1 ⊤ ​ 𝜷 𝒘 1 ​ 𝒘 1 ⊤ = 𝒘 2 ⊤ ​ 𝜷 𝒘 2 ​ 𝒘 2 ⊤ \displaystyle\bm{w}_{1}^{\top}\bm{\beta}_{\bm{w}_{1}}\bm{w}_{1}^{\top}=\bm{w}_{2}^{\top}\bm{\beta}_{\bm{w}_{2}}\bm{w}_{2}^{\top} ⟺ \displaystyle\Longleftrightarrow\;\;\; 𝒘 1 ⊤ ​ 𝒘 1 ​ 𝜷 𝒘 1 ⊤ = 𝒘 2 ⊤ ​ 𝒘 2 ​ 𝜷 𝒘 2 ⊤ \displaystyle\bm{w}_{1}^{\top}\bm{w}_{1}\bm{\beta}_{\bm{w}_{1}}^{\top}=\bm{w}_{2}^{\top}\bm{w}_{2}\bm{\beta}_{\bm{w}_{2}}^{\top} ⟺ \displaystyle\Longleftrightarrow\;\;\; 1 ⋅ 𝜷 𝒘 1 ⊤ = 1 ⋅ 𝜷 𝒘 2 ⊤ \displaystyle 1\cdot\bm{\beta}_{\bm{w}_{1}}^{\top}=1\cdot\bm{\beta}_{\bm{w}_{2}}^{\top} ⟺ \displaystyle\Longleftrightarrow\;\;\; 𝜷 𝒘 1 = 𝜷 𝒘 1 \displaystyle\bm{\beta}_{\bm{w}_{1}}=\bm{\beta}_{\bm{w}_{1}} Here, we used the fact that 𝒘 1 \bm{w}_{1} and 𝒘 2 \bm{w}_{2} are vectors on the unit sphere. This proves Claim (b).

Finally, we show (c) that Whenever we rotate a 𝒘 1 \bm{w}_{1} to a 𝒘 2 \bm{w}_{2} so that the set of 𝒙 i \bm{x}_{i} being activated changed, we can still find λ i \lambda_{i} that satisfy constraint of both 𝒘 1 \bm{w}_{1} and 𝒘 2 \bm{w}_{2} . Suppose we rotate 𝒘 1 \bm{w}_{1} to 𝒘 2 \bm{w}_{2} so that 𝒘 2 \bm{w}_{2} lost activation with 𝒙 1 , 𝒙 2 , … , 𝒙 p \bm{x}_{1},\bm{x}_{2},...,\bm{x}_{p} which in the set of linearly independent 𝒙 i \bm{x}_{i} ’s being activated by 𝒘 1 \bm{w}_{1} and their opposite vectors − 𝒙 i -\bm{x}_{i} are also in the training set (without loss of generality). Then 𝒘 2 \bm{w}_{2} must now also get activated by − 𝒙 1 , − 𝒙 2 , … , − 𝒙 p -\bm{x}_{1},-\bm{x}_{2},...,-\bm{x}_{p} . This is because if 𝒘 2 ⊤ ​ 𝒙 i < 0 \bm{w}_{2}^{\top}\bm{x}_{i}<0 , we must have 𝒘 2 ⊤ ​ ( − 𝒙 i ) > 0 \bm{w}_{2}^{\top}(-\bm{x}_{i})>0 .

Recall that in the proof of Claim (a), we only needed the λ i \lambda_{i} from linearly independent 𝒙 i \bm{x}_{i} that we used to solve the linear systems, and their opposite as the free variables to solve the linear system of d d equations. Hence, we can set λ \lambda to 0 0 for the other 𝒙 i \bm{x}_{i} while still satisfying the linear system. Then, suppose there exists λ i \lambda_{i} that satisfy 𝜷 𝒘 1 ( k ) = c ⋅ ∑ i = 1 d λ i ⋅ 𝒙 i ( k ) \displaystyle\bm{\beta}_{\bm{w}_{1}}^{(k)}=c\cdot\sum\limits_{i=1}^{d}\lambda_{i}\cdot\bm{x}_{i}^{(k)} where the 𝒙 i \bm{x}_{i} are the linearly independent vectors that activate 𝒘 1 \bm{w}_{1} with opposite vectors in the training set, which we have proved in (a). Then we can satisfy the constraint for 𝜷 𝒘 2 \bm{\beta}_{\bm{w}_{2}} below 𝜷 𝒘 2 ( k ) = c ⋅ ∑ i = 1 p λ ^ i ⋅ ( − 𝒙 i ) ( k ) + ∑ i = p + 1 d λ i ⋅ 𝒙 i ( k ) \displaystyle\bm{\beta}_{\bm{w}_{2}}^{(k)}=c\cdot\sum\limits_{i=1}^{p}\hat{\lambda}_{i}\cdot(-\bm{x}_{i})^{(k)}+\sum\limits_{i=p+1}^{d}\lambda_{i}\cdot\bm{x}_{i}^{(k)} by setting λ ^ i = − λ i \hat{\lambda}_{i}=-\lambda_{i} for i = 1 ​ … ​ p i=1...p . Indeed, this gives 𝜷 𝒘 2 ( k ) \displaystyle\bm{\beta}_{\bm{w}_{2}}^{(k)} = c ⋅ ∑ i = 1 p ( − λ i ) ⋅ ( − 𝒙 i ) ( k ) + ∑ i = p + 1 d λ i ⋅ 𝒙 i ( k ) \displaystyle=c\cdot\sum\limits_{i=1}^{p}(-\lambda_{i})\cdot(-\bm{x}_{i})^{(k)}+\sum\limits_{i=p+1}^{d}\lambda_{i}\cdot\bm{x}_{i}^{(k)} = c ⋅ ∑ i = 1 d λ i ⋅ 𝒙 i ( k ) \displaystyle=c\cdot\sum\limits_{i=1}^{d}\lambda_{i}\cdot\bm{x}_{i}^{(k)} Thus, we can also find λ i \lambda_{i} that satisfy the constraint for 𝜷 𝒘 2 \bm{\beta}_{\bm{w}_{2}} . Here, we do not consider the case where 𝒘 2 \bm{w}_{2} is parallel with an 𝒙 i \bm{x}_{i} because such 𝒘 2 \bm{w}_{2} has measure zero. Note that we can apply this argument iteratively because the flipping the sign always works and will not create any inconsistency.

Moreover, we can show that the constraint for 𝜷 𝒘 ​ 2 ′ \bm{\beta}_{\bm{w}2}^{\prime} is satisfied by a similar argument as in proof of Claim (b). This follows from the fact that our construction makes 𝜷 𝒘 1 = 𝜷 𝒘 2 \bm{\beta}_{\bm{w}_{1}}=\bm{\beta}_{\bm{w}_{2}} . Then we can follow the same argument as in (b) to show that 𝜷 𝒘 1 + 𝜷 𝒘 1 ′ ⋅ 𝒘 1 = 𝜷 𝒘 2 + 𝜷 𝒘 2 ′ ⋅ 𝒘 1 \bm{\beta}_{\bm{w}_{1}}+\bm{\beta}_{\bm{w}_{1}}^{\prime}\cdot\bm{w}_{1}=\bm{\beta}_{\bm{w}_{2}}+\bm{\beta}_{\bm{w}_{2}}^{\prime}\cdot\bm{w}_{1} . This completes the proof of Claim (c).

In summary, combining Claim (a), (b) and (c) gives that Claim 1 holds. That is, given our training data, the global optimum to the constrained optimization problem of finding the min-norm solution among functions that fit the training data satisfies 𝜷 𝒘 + 𝜷 𝒘 ′ ⋅ 𝒘 = 2 ​ 𝜷 g \bm{\beta}_{\bm{w}}+\bm{\beta}_{\bm{w}}^{\prime}\cdot\bm{w}=2\bm{\beta}_{g} . We also showed that this claim implies exact extrapolation, i.e., the network’s learned function f ⁡ ( 𝒙 ) f(\bm{x}) is equal to the true underlying function g ⁡ ( 𝒙 ) g(\bm{x}) for all 𝒙 ∈ ℝ d \bm{x}\in\mathbb{R}^{d} . This completes the proof.

### B.3 Proof of Theorem 2

Proof of the asymptotic convergence to extrapolation builds upon our proof of exact extrapolation, i.e., Lemma 1 . The proof idea is that if the training data distribution has support at all directions, when the number of samples n → ∞ n\rightarrow\infty , asymptotically the training set will converge to some imaginary training set that satisfies the condition for exact extrapolation. Since if training data are close the neural tangent kernels are also close, the predictions or learned function will converge to a function that achieves perfect extrapolation, that is, the true underlying function.

##### Asymptotic convergence of data sets.

We first show the training data converge to a data set that satisfies the exact extrapolation condition in Lemma 1 . Suppose training data { 𝒙 i } i = 1 n \{\bm{x}_{i}\}_{i=1}^{n} are sampled from a distribution whose support contains a connected set 𝒮 \mathcal{S} that intersects all directions, i.e., for any non-zero 𝒘 ∈ ℝ d \bm{w}\in\mathbb{R}^{d} , there exists k > 0 k>0 so that k ​ 𝒘 ∈ 𝒮 k\bm{w}\in\mathcal{S} .

Let us denote by 𝒮 \mathcal{S} the set of datasets that satisfy the condition in Lemma 1 . In fact, we will use a relaxed condition in the proof of Lemma 1 (Lemma 1 in the main text uses a stricter condition for simplicity of exposition). Given a general dataset 𝑿 \bm{X} and a dataset 𝑺 ∈ 𝒮 \bm{S}\in\mathcal{S} of the same size n n , let σ ⁡ ( 𝑿 , 𝑺 ) \sigma(\bm{X},\bm{S}) denote a matching of their data points, i.e., σ \sigma outputs a sequence of pairs σ ​ ( 𝑿 , 𝑺 ) i = ( 𝒙 i , 𝒔 i ) ​ for ​ i ∈ [ n ] \displaystyle\sigma(\bm{X},\bm{S})_{i}=\left(\bm{x}_{i},\bm{s}_{i}\right)\;\;\;\text{for }i\in[n] s . t . 𝑿 = { 𝒙 i } i = 1 n \displaystyle s.t.\;\;\;\bm{X}=\{\bm{x}_{i}\}_{i=1}^{n} 𝑺 = { 𝒔 i } i = 1 n \displaystyle\;\;\;\;\;\;\;\;\;\bm{S}=\{\bm{s}_{i}\}_{i=1}^{n}

Let ℓ : ℝ d × ℝ d → ℝ \ell:\mathbb{R}^{d}\times\mathbb{R}^{d}\rightarrow\mathbb{R} be the l ​ 2 l2 distance that takes in a pair of points. We then define the distance between the datasets d ⁡ ( 𝑿 , 𝑺 ) d(\bm{X},\bm{S}) as the minimum sum of l ​ 2 l2 distances of their data points over all possible matching. d ⁡ ( 𝑿 , 𝑺 ) = { min ⁡ ∑ i = 1 n σ ⁡ ℓ ⁡ ( σ ​ ( 𝑿 , 𝑺 ) i ) | 𝑿 | = | 𝑺 | = n ∞ | 𝑿 | ≠ | 𝑺 | \displaystyle d(\bm{X},\bm{S})=\begin{cases}\quad\min\limits_{\sigma}\sum\limits_{i=1}^{n}\ell\left(\sigma\left(\bm{X},\bm{S}\right)_{i}\right)\quad\quad\quad&|\bm{X}|=|\bm{S}|=n\\ \quad\infty\quad\quad\quad&|\bm{X}|\neq|\bm{S}|\end{cases}

We can then define a “closest distance to perfect dataset” function 𝒟 ∗ : 𝒳 → ℝ \mathcal{D}^{\ast}:\mathcal{X}\rightarrow\mathbb{R} which maps a dataset 𝑿 \bm{X} to the minimum distance of 𝑿 \bm{X} to any dataset in 𝒮 \mathcal{S} 𝒟 ∗ ​ ( 𝑿 ) = min 𝑺 ∈ 𝒮 ⁡ d ⁡ ( 𝑿 , 𝑺 ) \displaystyle\mathcal{D}^{\ast}\left(\bm{X}\right)=\min\limits_{\bm{S}\in\mathcal{S}}d\left(\bm{X},\bm{S}\right)

It is easy to see that for any dataset 𝑿 = { 𝒙 i } i = 1 n \bm{X}=\{\bm{x}_{i}\}_{i=1}^{n} , 𝒟 ∗ ​ ( 𝑿 ) \mathcal{D}^{\ast}\left(\bm{X}\right) can be bounded by the minimum of the closest distance to perfect dataset 𝒟 ∗ \mathcal{D}^{\ast} of sub-datasets of 𝑿 \bm{X} of size 2 ​ d 2d . 𝒟 ∗ ​ ( { 𝒙 i } i = 1 n ) ≤ min k = 1 ⌊ n / 2 ​ d ⌋ ​ 𝒟 ∗ ​ ( { 𝒙 j } j = ( k − 1 ) ∗ 2 ​ d + 1 k ∗ 2 ​ d ) \displaystyle\mathcal{D}^{\ast}\left(\{\bm{x}_{i}\}_{i=1}^{n}\right)\leq\min\limits_{k=1}^{\lfloor n/2d\rfloor}\mathcal{D}^{\ast}\left(\{\bm{x}_{j}\}_{j=(k-1)*2d+1}^{k*2d}\right) (62) This is because for any 𝑺 ∈ 𝒮 \bm{S}\in\mathcal{S} , and any 𝑺 ⊆ 𝑺 ′ \bm{S}\subseteq\bm{S}^{\prime} , we must have 𝑺 ′ ∈ 𝒮 \bm{S}^{\prime}\in\mathcal{S} because a dataset satisfies exact extrapolation condition as long as it contains some key points. Thus, adding more data will not hurt, i.e., for any 𝑿 1 ⊆ 𝑿 2 \bm{X}_{1}\subseteq\bm{X}_{2} , we always have 𝒟 ∗ ​ ( 𝑿 𝟏 ) ≤ 𝒟 ∗ ​ ( 𝑿 2 ) \displaystyle\mathcal{D}^{\ast}\left(\bm{X_{1}}\right)\leq\mathcal{D}^{\ast}\left(\bm{X}_{2}\right)

Now let us denote by 𝑿 n \bm{X}_{n} a random dataset of size n n where each 𝒙 i ∈ 𝑿 n \bm{x}_{i}\in\bm{X}_{n} is sampled from the training distribution. Recall that our training data { 𝒙 i } i = 1 n \{\bm{x}_{i}\}_{i=1}^{n} are sampled from a distribution whose support contains a connected set 𝒮 ∗ \mathcal{S}^{\ast} that intersects all directions, i.e., for any non-zero 𝒘 ∈ ℝ d \bm{w}\in\mathbb{R}^{d} , there exists k > 0 k>0 so that k ​ 𝒘 ∈ 𝒮 ∗ k\bm{w}\in\mathcal{S}^{\ast} . It follows that for a random dataset 𝑿 2 ​ d \bm{X}_{2d} of size 2 ​ d 2d , the probability that 𝒟 ∗ ​ ( 𝑿 2 ​ d ) > ϵ \mathcal{D}^{\ast}(\bm{X}_{2d})>\epsilon happens is less than 1 1 for any ϵ > 0 \epsilon>0 .