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

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

For any 𝒙 ∈ ℝ d \bm{x}\in\mathbb{R}^{d} , the network output is given by f ( 𝒙 ) = ( ⟨ ϕ ( 𝒙 ) , ϕ ( 𝒙 1 ) ⟩ , … , ⟨ ϕ ( 𝒙 ) , ϕ ( 𝒙 n ) ⟩ ) ⋅ NTK train − 1 𝒀 , \displaystyle f(\bm{x})=\left(\bigl<\phi(\bm{x}),\phi(\bm{x}_{1})\bigr>,...,\bigl<\phi(\bm{x}),\phi(\bm{x}_{n})\bigr>\right)\cdot\text{NTK}_{\text{train}}^{-1}\bm{Y}, where NTK train \text{NTK}_{\text{train}} is the n × n n\times n kernel for training data, ⟨ ϕ ( 𝒙 ) , ϕ ( 𝒙 i ) ⟩ \bigl<\phi(\bm{x}),\phi(\bm{x}_{i})\bigr> is the kernel value between test data 𝒙 \bm{x} and training data 𝒙 i \bm{x}_{i} , and 𝒀 \bm{Y} is training labels. By Lemma 2 , the kernel regression solution is also equivalent to the min-norm solution in the NTK RKHS space that fits all training data f ⁡ ( 𝒙 ) = ϕ ​ ( 𝒙 ) ⊤ ​ 𝜷 NTK , \displaystyle f(\bm{x})=\phi(\bm{x})^{\top}\bm{\beta}_{\text{NTK}}, (11) where the representation coefficient 𝜷 NTK \bm{\beta}_{\text{NTK}} is min 𝜷 ⁡ ‖ 𝜷 ‖ 2 \displaystyle\min_{\bm{\beta}}\|\bm{\beta}\|_{2} s.t. ϕ ( 𝒙 i ) ⊤ 𝜷 = y i , for i = 1 , … , n . \displaystyle\phi(\bm{x}_{i})^{\top}\bm{\beta}=y_{i},\;\;\;\text{for }i=1,...,n. The feature map ϕ ⁡ ( 𝒙 ) \phi(\bm{x}) for a two-layer MLP with ReLU activation is given by Lemma 3 ϕ ⁡ ( 𝒙 ) = c ′ ​ ( 𝒙 ⋅ 𝕀 ⁡ ( 𝒘 ( k ) ⊤ ​ 𝒙 ≥ 0 ) , 𝒘 ( k ) ⊤ ​ 𝒙 ⋅ 𝕀 ⁡ ( 𝒘 ( k ) ⊤ ​ 𝒙 ≥ 0 ) , … ) , \displaystyle\phi\left(\bm{x}\right)=c^{\prime}\left(\bm{x}\cdot\mathbb{I}\left(\bm{w}^{(k)^{\top}}\bm{x}\geq 0\right),\bm{w}^{(k)^{\top}}\bm{x}\cdot\mathbb{I}\left(\bm{w}^{(k)^{\top}}\bm{x}\geq 0\right),...\right), (12) where 𝒘 ( k ) ∼ 𝒩 ⁡ ( 𝟎 , 𝑰 ) \bm{w}^{(k)}\sim\mathcal{N}(\bm{0},\bm{I}) , with k k going to infinity. c ′ c^{\prime} is a constant, and 𝕀 \mathbb{I} is the indicator function. Without loss of generality, we assume the bias term to be 1 1 . For simplicity of notations, we denote each data 𝒙 \bm{x} plus bias term by, i.e., 𝒙 ^ = [ 𝒙 | 1 ] \hat{\bm{x}}=[\bm{x}|1] ( Bietti & Mairal, 2019 ) , and assume constant term is 1 1 .

Given any direction 𝒗 {\bm{v}} on the unit sphere, the network outputs for out-of-distribution data 𝒙 0 = t ​ 𝒗 \bm{x}_{0}=t{\bm{v}} and 𝒙 = 𝒙 0 + h ​ 𝒗 = ( 1 + λ ) ​ 𝒙 0 \bm{x}=\bm{x}_{0}+h{\bm{v}}=(1+\lambda)\bm{x}_{0} , where we introduce the notation of 𝒙 \bm{x} and λ \lambda for convenience, are given by Eqn. 11 and Eqn. 12 f ⁡ ( 𝒙 0 ^ ) = \displaystyle f(\hat{\bm{x}_{0}})= 𝜷 NTK ⊤ ​ ( 𝒙 0 ^ ⋅ 𝕀 ⁡ ( 𝒘 ( k ) ⊤ ​ 𝒙 0 ^ ≥ 0 ) , 𝒘 ( k ) ⊤ ​ 𝒙 0 ^ ⋅ 𝕀 ⁡ ( 𝒘 ( k ) ⊤ ​ 𝒙 0 ^ ≥ 0 ) , … ) , \displaystyle\bm{\beta}_{\text{NTK}}^{\top}\left(\hat{\bm{x}_{0}}\cdot\mathbb{I}\left(\bm{w}^{(k)^{\top}}\hat{\bm{x}_{0}}\geq 0\right),\bm{w}^{(k)^{\top}}\hat{\bm{x}_{0}}\cdot\mathbb{I}\left(\bm{w}^{(k)^{\top}}\hat{\bm{x}_{0}}\geq 0\right),...\right), f ⁡ ( 𝒙 ^ ) = \displaystyle f(\hat{\bm{x}})= 𝜷 NTK ⊤ ​ ( 𝒙 ^ ⋅ 𝕀 ⁡ ( 𝒘 ( k ) ⊤ ​ 𝒙 ^ ≥ 0 ) , 𝒘 ( k ) ⊤ ​ 𝒙 ^ ⋅ 𝕀 ⁡ ( 𝒘 ( k ) ⊤ ​ 𝒙 ^ ≥ 0 ) , … ) , \displaystyle\bm{\beta}_{\text{NTK}}^{\top}\Big(\hat{\bm{x}}\cdot\mathbb{I}\left(\bm{w}^{(k)^{\top}}\hat{\bm{x}}\geq 0\right),\bm{w}^{(k)^{\top}}\hat{\bm{x}}\cdot\mathbb{I}\left(\bm{w}^{(k)^{\top}}\hat{\bm{x}}\geq 0\right),...\Big), where we have 𝒙 0 ^ = [ 𝒙 0 | 1 ] \hat{\bm{x}_{0}}=\left[\bm{x}_{0}|1\right] and 𝒙 ^ = [ ( 1 + λ ) ​ 𝒙 0 | 1 ] \hat{\bm{x}}=\left[(1+\lambda)\bm{x}_{0}|1\right] . It follows that f ⁡ ( 𝒙 ^ ) − f ⁡ ( 𝒙 0 ^ ) = 𝜷 NTK ⊤ ​ ( CLOSE \displaystyle f(\hat{\bm{x}})-f(\hat{\bm{x}_{0}})=\bm{\beta}_{\text{NTK}}^{\top}\Big( 𝒙 ^ ⋅ 𝕀 ⁡ ( 𝒘 ( k ) ⊤ ​ 𝒙 ^ ≥ 0 ) − 𝒙 0 ^ ⋅ 𝕀 ⁡ ( 𝒘 ( k ) ⊤ ​ 𝒙 0 ^ ≥ 0 ) , \displaystyle\hat{\bm{x}}\cdot\mathbb{I}\left(\bm{w}^{(k)^{\top}}\hat{\bm{x}}\geq 0\right)-\hat{\bm{x}_{0}}\cdot\mathbb{I}\left(\bm{w}^{(k)^{\top}}\hat{\bm{x}_{0}}\geq 0\right), (13) OPEN 𝒘 ( k ) ⊤ ​ 𝒙 ^ ⋅ 𝕀 ⁡ ( 𝒘 ( k ) ⊤ ​ 𝒙 ^ ≥ 0 ) − 𝒘 ( k ) ⊤ ​ 𝒙 0 ^ ⋅ 𝕀 ⁡ ( 𝒘 ( k ) ⊤ ​ 𝒙 0 ^ ≥ 0 ) , … ) \displaystyle\bm{w}^{(k)^{\top}}\hat{\bm{x}}\cdot\mathbb{I}\left(\bm{w}^{(k)^{\top}}\hat{\bm{x}}\geq 0\right)-\bm{w}^{(k)^{\top}}\hat{\bm{x}_{0}}\cdot\mathbb{I}\left(\bm{w}^{(k)^{\top}}\hat{\bm{x}_{0}}\geq 0\right),...\Big) (14) By re-arranging the terms, we get the following equivalent form of the entries: 𝒙 ^ ⋅ 𝕀 ⁡ ( 𝒘 ⊤ ​ 𝒙 ^ ≥ 0 ) − 𝒙 0 ^ ⋅ 𝕀 ⁡ ( 𝒘 ⊤ ​ 𝒙 0 ^ ≥ 0 ) \displaystyle\hat{\bm{x}}\cdot\mathbb{I}\left(\bm{w}^{\top}\hat{\bm{x}}\geq 0\right)-\hat{\bm{x}_{0}}\cdot\mathbb{I}\left(\bm{w}^{\top}\hat{\bm{x}_{0}}\geq 0\right) (15) = \displaystyle=\;\; 𝒙 ^ ⋅ ( 𝕀 ⁡ ( 𝒘 ⊤ ​ 𝒙 ^ ≥ 0 ) − 𝕀 ⁡ ( 𝒘 ⊤ ​ 𝒙 0 ^ ≥ 0 ) + 𝕀 ⁡ ( 𝒘 ⊤ ​ 𝒙 0 ^ ≥ 0 ) ) − 𝒙 0 ^ ⋅ 𝕀 ⁡ ( 𝒘 ⊤ ​ 𝒙 0 ^ ≥ 0 ) \displaystyle\hat{\bm{x}}\cdot\left(\mathbb{I}\left(\bm{w}^{\top}\hat{\bm{x}}\geq 0\right)-\mathbb{I}\left(\bm{w}^{\top}\hat{\bm{x}_{0}}\geq 0\right)+\mathbb{I}\left(\bm{w}^{\top}\hat{\bm{x}_{0}}\geq 0\right)\right)-\hat{\bm{x}_{0}}\cdot\mathbb{I}\left(\bm{w}^{\top}\hat{\bm{x}_{0}}\geq 0\right) (16) = \displaystyle=\;\; 𝒙 ^ ⋅ ( 𝕀 ⁡ ( 𝒘 ⊤ ​ 𝒙 ^ ≥ 0 ) − 𝕀 ⁡ ( 𝒘 ⊤ ​ 𝒙 0 ^ ≥ 0 ) ) + ( 𝒙 ^ − 𝒙 0 ^ ) ⋅ 𝕀 ⁡ ( 𝒘 ⊤ ​ 𝒙 0 ^ ≥ 0 ) \displaystyle\hat{\bm{x}}\cdot\left(\mathbb{I}\left(\bm{w}^{\top}\hat{\bm{x}}\geq 0\right)-\mathbb{I}\left(\bm{w}^{\top}\hat{\bm{x}_{0}}\geq 0\right)\right)+\left(\hat{\bm{x}}-\hat{\bm{x}_{0}}\right)\cdot\mathbb{I}\left(\bm{w}^{\top}\hat{\bm{x}_{0}}\geq 0\right) (17) = \displaystyle=\;\; [ 𝒙 | 1 ] ⋅ ( 𝕀 ⁡ ( 𝒘 ⊤ ​ 𝒙 ^ ≥ 0 ) − 𝕀 ⁡ ( 𝒘 ⊤ ​ 𝒙 0 ^ ≥ 0 ) ) + [ h ​ 𝒗 | 0 ] ⋅ 𝕀 ⁡ ( 𝒘 ⊤ ​ 𝒙 0 ^ ≥ 0 ) \displaystyle\left[\bm{x}|1\right]\cdot\left(\mathbb{I}\left(\bm{w}^{\top}\hat{\bm{x}}\geq 0\right)-\mathbb{I}\left(\bm{w}^{\top}\hat{\bm{x}_{0}}\geq 0\right)\right)+[h{\bm{v}}|0]\cdot\mathbb{I}\left(\bm{w}^{\top}\hat{\bm{x}_{0}}\geq 0\right) (18) Similarly, we have 𝒘 ⊤ ​ 𝒙 ^ ⋅ 𝕀 ⁡ ( 𝒘 ⊤ ​ 𝒙 ^ ≥ 0 ) − 𝒘 ⊤ ​ 𝒙 0 ^ ⋅ 𝕀 ⁡ ( 𝒘 ⊤ ​ 𝒙 0 ^ ≥ 0 ) \displaystyle\bm{w}^{\top}\hat{\bm{x}}\cdot\mathbb{I}\left(\bm{w}^{\top}\hat{\bm{x}}\geq 0\right)-\bm{w}^{\top}\hat{\bm{x}_{0}}\cdot\mathbb{I}\left(\bm{w}^{\top}\hat{\bm{x}_{0}}\geq 0\right) (19) = \displaystyle=\;\; 𝒘 ⊤ ​ 𝒙 ^ ⋅ ( 𝕀 ⁡ ( 𝒘 ⊤ ​ 𝒙 ^ ≥ 0 ) − 𝕀 ⁡ ( 𝒘 ⊤ ​ 𝒙 0 ^ ≥ 0 ) + 𝕀 ⁡ ( 𝒘 ⊤ ​ 𝒙 0 ^ ≥ 0 ) ) − 𝒘 ⊤ ​ 𝒙 0 ^ ⋅ 𝕀 ⁡ ( 𝒘 ⊤ ​ 𝒙 0 ^ ≥ 0 ) \displaystyle\bm{w}^{\top}\hat{\bm{x}}\cdot\left(\mathbb{I}\left(\bm{w}^{\top}\hat{\bm{x}}\geq 0\right)-\mathbb{I}\left(\bm{w}^{\top}\hat{\bm{x}_{0}}\geq 0\right)+\mathbb{I}\left(\bm{w}^{\top}\hat{\bm{x}_{0}}\geq 0\right)\right)-\bm{w}^{\top}\hat{\bm{x}_{0}}\cdot\mathbb{I}\left(\bm{w}^{\top}\hat{\bm{x}_{0}}\geq 0\right) (20) = \displaystyle=\;\; 𝒘 ⊤ ​ 𝒙 ^ ⋅ ( 𝕀 ⁡ ( 𝒘 ⊤ ​ 𝒙 ^ ≥ 0 ) − 𝕀 ⁡ ( 𝒘 ⊤ ​ 𝒙 0 ^ ≥ 0 ) ) + 𝒘 ⊤ ​ ( 𝒙 ^ − 𝒙 0 ^ ) ⋅ 𝕀 ⁡ ( 𝒘 ⊤ ​ 𝒙 0 ^ ≥ 0 ) \displaystyle\bm{w}^{\top}\hat{\bm{x}}\cdot\left(\mathbb{I}\left(\bm{w}^{\top}\hat{\bm{x}}\geq 0\right)-\mathbb{I}\left(\bm{w}^{\top}\hat{\bm{x}_{0}}\geq 0\right)\right)+\bm{w}^{\top}\left(\hat{\bm{x}}-\hat{\bm{x}_{0}}\right)\cdot\mathbb{I}\left(\bm{w}^{\top}\hat{\bm{x}_{0}}\geq 0\right) (21) = \displaystyle=\;\; 𝒘 ⊤ ​ [ 𝒙 | 1 ] ⋅ ( 𝕀 ⁡ ( 𝒘 ⊤ ​ 𝒙 ^ ≥ 0 ) − 𝕀 ⁡ ( 𝒘 ⊤ ​ 𝒙 0 ^ ≥ 0 ) ) + 𝒘 ⊤ ​ [ h ​ 𝒗 | 0 ] ⋅ 𝕀 ⁡ ( 𝒘 ⊤ ​ 𝒙 0 ^ ≥ 0 ) \displaystyle\bm{w}^{\top}\left[\bm{x}|1\right]\cdot\left(\mathbb{I}\left(\bm{w}^{\top}\hat{\bm{x}}\geq 0\right)-\mathbb{I}\left(\bm{w}^{\top}\hat{\bm{x}_{0}}\geq 0\right)\right)+\bm{w}^{\top}[h{\bm{v}}|0]\cdot\mathbb{I}\left(\bm{w}^{\top}\hat{\bm{x}_{0}}\geq 0\right) (22) Again, let us denote the part of 𝜷 NTK \bm{\beta}_{\text{NTK}} corresponding to each 𝒘 \bm{w} by 𝜷 𝒘 \bm{\beta}_{\bm{w}} . Moreover, let us denote the part corresponding to Eqn. 18 by 𝜷 𝒘 1 \bm{\beta}_{\bm{w}}^{1} and the part corresponding to Eqn. 22 by 𝜷 𝒘 2 \bm{\beta}_{\bm{w}}^{2} . Then we have f ⁡ ( 𝒙 ^ ) − f ⁡ ( 𝒙 0 ^ ) h \displaystyle\frac{f(\hat{\bm{x}})-f(\hat{\bm{x}_{0}})}{h} (23) = \displaystyle=\;\; ∫ 𝜷 𝒘 1 ⊤ ​ [ 𝒙 / h | 1 / h ] ⋅ ( 𝕀 ⁡ ( 𝒘 ⊤ ​ 𝒙 ^ ≥ 0 ) − 𝕀 ⁡ ( 𝒘 ⊤ ​ 𝒙 0 ^ ≥ 0 ) ) ​ 𝑑 ℙ ​ ( 𝒘 ) \displaystyle\int\bm{\beta}_{\bm{w}}^{1^{\top}}\left[\bm{x}/h|1/h\right]\cdot\left(\mathbb{I}\left(\bm{w}^{\top}\hat{\bm{x}}\geq 0\right)-\mathbb{I}\left(\bm{w}^{\top}\hat{\bm{x}_{0}}\geq 0\right)\right)\mathrm{d}\mathbb{P}(\bm{w}) (24) + \displaystyle+\;\; ∫ 𝜷 𝒘 1 ⊤ ​ [ 𝒗 | 0 ] ⋅ 𝕀 ⁡ ( 𝒘 ⊤ ​ 𝒙 0 ^ ≥ 0 ) ​ 𝑑 ℙ ​ ( 𝒘 ) \displaystyle\int\bm{\beta}_{\bm{w}}^{1^{\top}}[{\bm{v}}|0]\cdot\mathbb{I}\left(\bm{w}^{\top}\hat{\bm{x}_{0}}\geq 0\right)\mathrm{d}\mathbb{P}(\bm{w}) (25) + \displaystyle+\;\; ∫ 𝜷 𝒘 2 ⋅ 𝒘 ⊤ ​ [ 𝒙 / h | 1 / h ] ⋅ ( 𝕀 ⁡ ( 𝒘 ⊤ ​ 𝒙 ^ ≥ 0 ) − 𝕀 ⁡ ( 𝒘 ⊤ ​ 𝒙 0 ^ ≥ 0 ) ) ​ 𝑑 ℙ ​ ( 𝒘 ) \displaystyle\int\bm{\beta}_{\bm{w}}^{2}\cdot\bm{w}^{\top}\left[\bm{x}/h|1/h\right]\cdot\left(\mathbb{I}\left(\bm{w}^{\top}\hat{\bm{x}}\geq 0\right)-\mathbb{I}\left(\bm{w}^{\top}\hat{\bm{x}_{0}}\geq 0\right)\right)\mathrm{d}\mathbb{P}(\bm{w}) (26) + \displaystyle+\;\; ∫ 𝜷 𝒘 2 ⋅ 𝒘 ⊤ ​ [ 𝒗 | 0 ] ⋅ 𝕀 ⁡ ( 𝒘 ⊤ ​ 𝒙 0 ^ ≥ 0 ) ​ 𝑑 ℙ ​ ( 𝒘 ) \displaystyle\int\bm{\beta}_{\bm{w}}^{2}\cdot\bm{w}^{\top}[{\bm{v}}|0]\cdot\mathbb{I}\left(\bm{w}^{\top}\hat{\bm{x}_{0}}\geq 0\right)\mathrm{d}\mathbb{P}(\bm{w}) (27) Note that all 𝜷 𝒘 \bm{\beta}_{\bm{w}} are finite constants that depend on the training data. Next, we show that as t → ∞ t\rightarrow\infty , each of the terms above converges in O ⁡ ( 1 / ϵ ) O(1/\epsilon) to some constant coefficient 𝜷 𝒗 \bm{\beta}_{{\bm{v}}} that depend on the training data and the direction 𝒗 {\bm{v}} . Let us first consider Eqn. 25 . We have ∫ 𝕀 ⁡ ( 𝒘 ⊤ ​ 𝒙 0 ^ ≥ 0 ) ​ 𝑑 ℙ ​ ( 𝒘 ) \displaystyle\int\mathbb{I}\left(\bm{w}^{\top}\hat{\bm{x}_{0}}\geq 0\right)d\mathbb{P}(\bm{w}) = ∫ 𝕀 ⁡ ( 𝒘 ⊤ ​ [ 𝒙 0 | 1 ] ≥ 0 ) ​ 𝑑 ℙ ​ ( 𝒘 ) \displaystyle=\int\mathbb{I}\left(\bm{w}^{\top}[\bm{x}_{0}|1]\geq 0\right)\mathrm{d}\mathbb{P}(\bm{w}) (28) = ∫ 𝕀 ⁡ ( 𝒘 ⊤ ​ [ 𝒙 0 / t | 1 / t ] ≥ 0 ) ​ 𝑑 ℙ ​ ( 𝒘 ) \displaystyle=\int\mathbb{I}\left(\bm{w}^{\top}[\bm{x}_{0}/t|1/t]\geq 0\right)\mathrm{d}\mathbb{P}(\bm{w}) (29) → ∫ 𝕀 ⁡ ( 𝒘 ⊤ ​ [ 𝒗 | 0 ] ≥ 0 ) ​ 𝑑 ℙ ​ ( 𝒘 ) as ​ t → ∞ \displaystyle\xrightarrow{}\int\mathbb{I}\left(\bm{w}^{\top}[{\bm{v}}|0]\geq 0\right)\mathrm{d}\mathbb{P}(\bm{w})\quad\quad\text{as }t\rightarrow\infty (30) Because 𝜷 𝒘 1 \bm{\beta}_{\bm{w}}^{1} are finite constants, it follows that ∫ 𝜷 𝒘 1 ⊤ ​ [ 𝒗 | 0 ] ⋅ 𝕀 ⁡ ( 𝒘 ⊤ ​ 𝒙 0 ^ ≥ 0 ) ​ 𝑑 ℙ ​ ( 𝒘 ) → ∫ 𝜷 𝒘 1 ⊤ ​ [ 𝒗 | 0 ] ⋅ 𝕀 ⁡ ( 𝒘 ⊤ ​ [ 𝒗 | 0 ] ≥ 0 ) ​ 𝑑 ℙ ​ ( 𝒘 ) , \displaystyle\int\bm{\beta}_{\bm{w}}^{1^{\top}}[{\bm{v}}|0]\cdot\mathbb{I}\left(\bm{w}^{\top}\hat{\bm{x}_{0}}\geq 0\right)\mathrm{d}\mathbb{P}(\bm{w})\rightarrow\int\bm{\beta}_{\bm{w}}^{1^{\top}}[{\bm{v}}|0]\cdot\mathbb{I}\left(\bm{w}^{\top}[{\bm{v}}|0]\geq 0\right)\mathrm{d}\mathbb{P}(\bm{w}), (31) where the right hand side is a constant that depends on training data and direction 𝒗 {\bm{v}} . Next, we show the convergence rate for Eqn. 31 . Given error ϵ > 0 \epsilon>0 , because 𝜷 𝒘 1 ⊤ ​ [ 𝒗 | 0 ] \bm{\beta}_{\bm{w}}^{1^{\top}}[{\bm{v}}|0] are finite constants, we need to bound the following by C ⋅ ϵ C\cdot\epsilon for some constant C C , | ∫ 𝕀 ⁡ ( 𝒘 ⊤ ​ 𝒙 0 ^ ≥ 0 ) − 𝕀 ⁡ ( 𝒘 ⊤ ​ [ 𝒗 | 0 ] ≥ 0 ) ​ 𝑑 ℙ ​ ( 𝒘 ) | \displaystyle|\int\mathbb{I}\left(\bm{w}^{\top}\hat{\bm{x}_{0}}\geq 0\right)-\mathbb{I}\left(\bm{w}^{\top}[{\bm{v}}|0]\geq 0\right)\mathrm{d}\mathbb{P}(\bm{w})| (32) = | ∫ 𝕀 ⁡ ( 𝒘 ⊤ ​ [ 𝒙 0 | 1 ] ≥ 0 ) − 𝕀 ⁡ ( 𝒘 ⊤ ​ [ 𝒙 0 | 0 ] ≥ 0 ) ​ 𝑑 ℙ ​ ( 𝒘 ) | \displaystyle=|\int\mathbb{I}\left(\bm{w}^{\top}[\bm{x}_{0}|1]\geq 0\right)-\mathbb{I}\left(\bm{w}^{\top}[\bm{x}_{0}|0]\geq 0\right)\mathrm{d}\mathbb{P}(\bm{w})| (33) Observe that the two terms in Eqn. 33 represent the volume of half-(balls) that are orthogonal to vectors [ 𝒙 0 | 1 ] [\bm{x}_{0}|1] and [ 𝒙 0 | 0 ] [\bm{x}_{0}|0] . Hence, Eqn. 33 is the volume of the non-overlapping part of the two (half)balls, which is created by rotating an angle θ \theta along the last coordinate. By symmetry, Eqn. 33 is linear in θ \theta . Moreover, the angle θ = arctan ⁡ ( C / t ) \theta=\arctan(C/t) for some constant C C . Hence, it follows that | ∫ 𝕀 ⁡ ( 𝒘 ⊤ ​ [ 𝒙 0 | 1 ] ≥ 0 ) − 𝕀 ⁡ ( 𝒘 ⊤ ​ [ 𝒙 0 | 0 ] ≥ 0 ) ​ 𝑑 ℙ ​ ( 𝒘 ) | \displaystyle|\int\mathbb{I}\left(\bm{w}^{\top}[\bm{x}_{0}|1]\geq 0\right)-\mathbb{I}\left(\bm{w}^{\top}[\bm{x}_{0}|0]\geq 0\right)\mathrm{d}\mathbb{P}(\bm{w})| = C 1 ⋅ arctan ⁡ ( C 2 / t ) \displaystyle=C_{1}\cdot\arctan(C_{2}/t) (34) ≤ C 1 ⋅ C 2 / t \displaystyle\leq C_{1}\cdot C_{2}/t (35) = O ⁡ ( 1 / t ) \displaystyle=O(1/t) (36) In the last inequality, we used the fact that arctan ⁡ x < x \arctan x<x for x > 0 x>0 . Hence, O ⁡ ( 1 / t ) < ϵ O(1/t)<\epsilon implies t = O ⁡ ( 1 / ϵ ) t=O(1/\epsilon) as desired. Next, we consider Eqn. 24 . ∫ 𝜷 𝒘 1 ⊤ ​ [ 𝒙 / h | 1 / h ] ⋅ ( 𝕀 ⁡ ( 𝒘 ⊤ ​ 𝒙 ^ ≥ 0 ) − 𝕀 ⁡ ( 𝒘 ⊤ ​ 𝒙 0 ^ ≥ 0 ) ) ​ 𝑑 ℙ ​ ( 𝒘 ) \displaystyle\int\bm{\beta}_{\bm{w}}^{1^{\top}}\left[\bm{x}/h|1/h\right]\cdot\left(\mathbb{I}\left(\bm{w}^{\top}\hat{\bm{x}}\geq 0\right)-\mathbb{I}\left(\bm{w}^{\top}\hat{\bm{x}_{0}}\geq 0\right)\right)\mathrm{d}\mathbb{P}(\bm{w}) (37) Let us first analyze the convergence of the following: | ∫ 𝕀 ⁡ ( 𝒘 ⊤ ​ 𝒙 ^ ≥ 0 ) − 𝕀 ⁡ ( 𝒘 ⊤ ​ 𝒙 0 ^ ≥ 0 ) ​ 𝑑 ℙ ​ ( 𝒘 ) | \displaystyle|\int\mathbb{I}\left(\bm{w}^{\top}\hat{\bm{x}}\geq 0\right)-\mathbb{I}\left(\bm{w}^{\top}\hat{\bm{x}_{0}}\geq 0\right)\mathrm{d}\mathbb{P}(\bm{w})| (38) = \displaystyle=\quad | ∫ 𝕀 ⁡ ( 𝒘 ⊤ ​ [ ( 1 + λ ) ​ 𝒙 0 | 1 ] ≥ 0 ) − 𝕀 ⁡ ( 𝒘 ⊤ ​ [ 𝒙 0 | 1 ] ≥ 0 ) ​ 𝑑 ℙ ​ ( 𝒘 ) ​ 𝑑 ℙ ​ ( 𝒘 ) | \displaystyle|\int\mathbb{I}\left(\bm{w}^{\top}[(1+\lambda)\bm{x}_{0}|1]\geq 0\right)-\mathbb{I}\left(\bm{w}^{\top}[\bm{x}_{0}|1]\geq 0\right)\mathrm{d}\mathbb{P}(\bm{w})\mathrm{d}\mathbb{P}(\bm{w})| (39) = \displaystyle=\quad | ∫ 𝕀 ⁡ ( 𝒘 ⊤ ​ [ 𝒙 0 | 1 1 + λ ] ≥ 0 ) − 𝕀 ⁡ ( 𝒘 ⊤ ​ [ 𝒙 0 | 1 ] ≥ 0 ) ​ 𝑑 ℙ ​ ( 𝒘 ) ​ 𝑑 ℙ ​ ( 𝒘 ) | → 0 \displaystyle|\int\mathbb{I}\left(\bm{w}^{\top}[\bm{x}_{0}|\frac{1}{1+\lambda}]\geq 0\right)-\mathbb{I}\left(\bm{w}^{\top}[\bm{x}_{0}|1]\geq 0\right)\mathrm{d}\mathbb{P}(\bm{w})\mathrm{d}\mathbb{P}(\bm{w})|\rightarrow 0 (40) The convergence to 0 0 follows from Eqn. 34 . Now we consider the convergence rate. The angle θ \theta is at most 1 − 1 1 + λ 1-\frac{1}{1+\lambda} times of that in Eqn. 34 . Hence, the rate is as follows ( 1 − 1 1 + λ ) ⋅ O ⁡ ( 1 t ) = λ 1 + λ ⋅ O ⁡ ( 1 t ) = h / t 1 + h / t ⋅ O ⁡ ( 1 t ) = O ⁡ ( h ( h + t ) ​ t ) \displaystyle\left(1-\frac{1}{1+\lambda}\right)\cdot O\left(\frac{1}{t}\right)=\frac{\lambda}{1+\lambda}\cdot O\left(\frac{1}{t}\right)=\frac{h/t}{1+h/t}\cdot O\left(\frac{1}{t}\right)=O\left(\frac{h}{(h+t)t}\right) (41) Now we get back to Eqn. 24 , which simplifies as the following. ∫ 𝜷 𝒘 1 ⊤ ​ [ 𝒗 + t ​ 𝒗 h | 1 h ] ⋅ ( 𝕀 ⁡ ( 𝒘 ⊤ ​ 𝒙 ^ ≥ 0 ) − 𝕀 ⁡ ( 𝒘 ⊤ ​ 𝒙 0 ^ ≥ 0 ) ) ​ 𝑑 ℙ ​ ( 𝒘 ) \displaystyle\int\bm{\beta}_{\bm{w}}^{1^{\top}}\left[{\bm{v}}+\frac{t{\bm{v}}}{h}|\frac{1}{h}\right]\cdot\left(\mathbb{I}\left(\bm{w}^{\top}\hat{\bm{x}}\geq 0\right)-\mathbb{I}\left(\bm{w}^{\top}\hat{\bm{x}_{0}}\geq 0\right)\right)\mathrm{d}\mathbb{P}(\bm{w}) (42) We compare the rate of growth of left hand side and the rate of decrease of right hand side (indicators). t h ⋅ h ( h + t ) ​ t = 1 h + t → 0 as ​ t → ∞ \displaystyle\frac{t}{h}\cdot\frac{h}{(h+t)t}=\frac{1}{h+t}\rightarrow 0\quad\text{as }t\rightarrow\infty (43) 1 h ⋅ h ( h + t ) ​ t = 1 ( h + t ) ​ t → 0 as ​ t → ∞ \displaystyle\frac{1}{h}\cdot\frac{h}{(h+t)t}=\frac{1}{(h+t)t}\rightarrow 0\quad\text{as }t\rightarrow\infty (44) Hence, the indicators decrease faster, and it follows that Eqn. 24 converges to 0 0 with rate O ⁡ ( 1 ϵ ) O(\frac{1}{\epsilon}) . Moreover, we can bound 𝒘 \bm{w} with standard concentration techniques. Then the proofs for Eqn. 26 and Eqn. 27 follow similarly. This completes the proof.

### B.2 Proof of Lemma 1

Overview of proof. To prove exact extrapolation given the conditions on training data, we analyze the function learned by the neural network in a functional form. The network’s learned function can be precisely characterized by a solution in the network’s neural tangent kernel feature space which has a minimum RKHS norm among functions that can fit all training data, i.e., it corresponds to the optimum of a constrained optimization problem. We show that the global optimum of this constrained optimization problem, given the conditions on training data, is precisely the same function as the underlying true function.

##### Setup and preparation.