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

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

Let 𝑿 = { 𝒙 1 , … , 𝒙 n } \bm{X}=\{\bm{x}_{1},...,\bm{x}_{n}\} and 𝒀 = { y 1 , … , y n } \bm{Y}=\{y_{1},...,y_{n}\} denote the training set input features and their labels. Let 𝜷 g ∈ ℝ d \bm{\beta}_{g}\in\mathbb{R}^{d} denote the true parameters/weights for the underlying linear function g g , i.e., g ⁡ ( 𝒙 ) = 𝜷 g ⊤ ​ 𝒙 for all ​ 𝒙 ∈ ℝ d g(\bm{x})=\bm{\beta}_{g}^{\top}\bm{x}\;\;\;\;\;\text{for all }\bm{x}\in\mathbb{R}^{d}

Recall from Section A that in the NTK regime, where networks are infinitely wide, randomly initialized, and trained by gradient descent with infinitesimally small learning rate, the learning dynamics of a neural network is equivalent to that of a kernel regression with respect to its neural tangent kernel. Moreover, Lemma 2 tells us that this kernel regression solution can be expressed in the functional form in the neural tangent kernel’s feature space. That is, the function learned by the neural network (in the ntk regime) can be precisely characterized as f ⁡ ( 𝒙 ) = ϕ ​ ( 𝒙 ) ⊤ ​ 𝜷 NTK , \displaystyle f(\bm{x})=\phi(\bm{x})^{\top}\bm{\beta}_{\text{NTK}}, where the representation coefficient 𝜷 NTK \bm{\beta}_{\text{NTK}} is min 𝜷 ⁡ ‖ 𝜷 ‖ 2 \displaystyle\min_{\bm{\beta}}\|\bm{\beta}\|_{2} (45) s.t. ϕ ( 𝒙 i ) ⊤ 𝜷 = y i , for i = 1 , … , n . \displaystyle\phi(\bm{x}_{i})^{\top}\bm{\beta}=y_{i},\;\;\;\text{for }i=1,...,n. (46) An infinite-dimensional feature map ϕ ⁡ ( 𝒙 ) \phi(\bm{x}) for a two-layer ReLU network is described in 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), 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. That is, there are infinitely many directions 𝒘 \bm{w} with Gaussian density, and each direction comes with two features. Without loss of generality, we can assume the scaling constant to be 1 1 .

##### Constrained optimization in NTK feature space.

The representation or weight of the neural network’s learned function in the neural tangent kernel feature space, 𝜷 NTK \bm{\beta}_{\text{NTK}} , consists of weight vectors for each 𝒙 ⋅ 𝕀 ⁡ ( 𝒘 ( k ) ⊤ ​ 𝒙 ≥ 0 ) ∈ ℝ d \bm{x}\cdot\mathbb{I}\left(\bm{w}^{(k)^{\top}}\bm{x}\geq 0\right)\in\mathbb{R}^{d} and 𝒘 ( k ) ⊤ ​ 𝒙 ⋅ 𝕀 ⁡ ( 𝒘 ( k ) ⊤ ​ 𝒙 ≥ 0 ) ∈ ℝ \bm{w}^{(k)^{\top}}\bm{x}\cdot\mathbb{I}\left(\bm{w}^{(k)^{\top}}\bm{x}\geq 0\right)\in\mathbb{R} . For simplicity of notation, we will use 𝒘 \bm{w} to refer to a particular 𝒘 \bm{w} , without considering the index ( k ) (k) , which does not matter for our purposes. For any 𝒘 ∈ ℝ d \bm{w}\in\mathbb{R}^{d} , we denote by 𝜷 ^ 𝒘 = ( 𝜷 ^ 𝒘 ( 1 ) , … , 𝜷 ^ 𝒘 ( d ) ) ∈ ℝ d \hat{\bm{\beta}}_{\bm{w}}=(\hat{\bm{\beta}}^{(1)}_{\bm{w}},...,\hat{\bm{\beta}}^{(d)}_{\bm{w}})\in\mathbb{R}^{d} the weight vectors corresponding to 𝒙 ⋅ 𝕀 ⁡ ( 𝒘 ⊤ ​ 𝒙 ≥ 0 ) \bm{x}\cdot\mathbb{I}\left(\bm{w}^{\top}\bm{x}\geq 0\right) , and denote by 𝜷 ^ 𝒘 ′ ∈ ℝ d \hat{\bm{\beta}}^{\prime}_{\bm{w}}\in\mathbb{R}^{d} the weight for 𝒘 ⊤ ​ 𝒙 ⋅ 𝕀 ⁡ ( 𝒘 ⊤ ​ 𝒙 ≥ 0 ) \bm{w}^{\top}\bm{x}\cdot\mathbb{I}\left(\bm{w}^{\top}\bm{x}\geq 0\right) .

Observe that for any 𝒘 ∼ 𝒩 ⁡ ( 𝟎 , 𝑰 ) ∈ ℝ d \bm{w}\sim\mathcal{N}(\bm{0},\bm{I})\in\mathbb{R}^{d} , any other vectors in the same direction will activate the same set of 𝒙 i ∈ ℝ d \bm{x}_{i}\in\mathbb{R}^{d} . That is, if 𝒘 ⊤ ​ 𝒙 i ≥ 0 \bm{w}^{\top}\bm{x}_{i}\geq 0 for any 𝒘 ∈ ℝ d \bm{w}\in\mathbb{R}^{d} , then ( k ⋅ 𝒘 ) ⊤ ​ 𝒙 i ≥ 0 (k\cdot\bm{w})^{\top}\bm{x}_{i}\geq 0 for any k > 0 k>0 . Hence, we can reload our notation to combine the effect of weights for 𝒘 \bm{w} ’s in the same direction. This enables simpler notations and allows us to change the distribution of 𝒘 \bm{w} in NTK features from Gaussian distribution to uniform distribution on the unit sphere.

More precisely, we reload our notation by using 𝜷 𝒘 \bm{\beta}_{\bm{w}} and 𝜷 𝒘 ′ \bm{\beta}_{\bm{w}}^{\prime} to denote the combined effect of all weights ( 𝜷 ^ k ​ 𝒘 ( 1 ) , … , 𝜷 ^ k ​ 𝒘 ( d ) ) ∈ ℝ d (\hat{\bm{\beta}}^{(1)}_{k\bm{w}},...,\hat{\bm{\beta}}^{(d)}_{k\bm{w}})\in\mathbb{R}^{d} and 𝜷 ^ k ​ 𝒘 ′ ∈ ℝ \hat{\bm{\beta}}^{\prime}_{k\bm{w}}\in\mathbb{R} for all k ​ 𝒘 k\bm{w} with k > 0 k>0 in the same direction of 𝒘 \bm{w} . That is, for each 𝒘 ∼ Uni(unit sphere) ∈ ℝ d \bm{w}\sim\text{Uni(unit sphere)}\in\mathbb{R}^{d} , we define 𝜷 𝒘 ( j ) \bm{\beta}_{\bm{w}}^{(j)} as the total effect of weights in the same direction 𝜷 𝒘 ( j ) = ∫ 𝜷 ^ 𝒖 ( j ) ​ 𝕀 ​ ( 𝒘 ⊤ ​ 𝒖 ‖ 𝒘 ‖ ⋅ ‖ 𝒖 ‖ = 1 ) ​ 𝑑 ℙ ​ ( 𝒖 ) , for ​ j = [ d ] \displaystyle\bm{\beta}_{\bm{w}}^{(j)}=\int\hat{\bm{\beta}}_{\bm{u}}^{(j)}\mathbb{I}\left(\frac{\bm{w}^{\top}\bm{u}}{\|\bm{w}\|\cdot\|\bm{u}\|}=1\right)\mathrm{d}\mathbb{P}(\bm{u}),\;\;\;\text{for }j=[d] (47) where 𝒖 ∼ 𝒩 ⁡ ( 𝟎 , 𝑰 ) \bm{u}\sim\mathcal{N}(\bm{0},\bm{I}) . Note that to ensure the 𝜷 𝒘 \bm{\beta}_{\bm{w}} is a well-defined number, here we can work with the polar representation and integrate with respect to an angle. Then 𝜷 𝒘 \bm{\beta}_{\bm{w}} is well-defined. But for simplicity of exposition, we use the plain notation of integral. Similarly, we define 𝜷 𝒘 ′ \bm{\beta}_{\bm{w}}^{\prime} as reloading the notation of 𝜷 𝒘 ′ = ∫ 𝜷 ^ 𝒖 ​ 𝕀 ​ ( 𝒘 ⊤ ​ 𝒖 ‖ 𝒘 ‖ ⋅ ‖ 𝒖 ‖ = 1 ) ⋅ ‖ 𝒖 ‖ ‖ 𝒘 ‖ ​ 𝑑 ℙ ​ ( 𝒖 ) \displaystyle\bm{\beta}_{\bm{w}}^{\prime}=\int\hat{\bm{\beta}}_{\bm{u}}\mathbb{I}\left(\frac{\bm{w}^{\top}\bm{u}}{\|\bm{w}\|\cdot\|\bm{u}\|}=1\right)\cdot\frac{\|\bm{u}\|}{\|\bm{w}\|}\mathrm{d}\mathbb{P}(\bm{u}) (48) Here, in Eqn. 48 we have an extra term of ‖ 𝒖 ‖ ‖ 𝒘 ‖ \frac{\|\bm{u}\|}{\|\bm{w}\|} compared to Eqn. 47 because the NTK features that Eqn. 48 corresponds to, 𝒘 ⊤ ​ 𝒙 ⋅ 𝕀 ⁡ ( 𝒘 ⊤ ​ 𝒙 ≥ 0 ) \bm{w}^{\top}\bm{x}\cdot\mathbb{I}\left(\bm{w}^{\top}\bm{x}\geq 0\right) , has an extra 𝒘 ⊤ \bm{w}^{\top} term. So we need to take into account the scaling. This abstraction enables us to make claims on the high-level parameters 𝜷 𝒘 \bm{\beta}_{\bm{w}} and 𝜷 𝒘 ′ \bm{\beta}_{\bm{w}}^{\prime} only, which we will show to be sufficient to determine the learned function.

Then we can formulate the constrained optimization problem whose solution gives a functional form of the neural network’s learned function. We rewrite the min-norm solution in Eqn. 45 as min ⁡ ∫ 𝜷 ⁡ ( 𝜷 𝒘 ( 1 ) ) 2 + ( 𝜷 𝒘 ( 2 ) ) 2 + … + ( 𝜷 𝒘 ( d ) ) 2 + ( 𝜷 𝒘 ′ ) 2 ​ 𝑑 ℙ ​ ( 𝒘 ) \displaystyle\min_{\bm{\beta}}\int\left(\bm{\beta}_{\bm{w}}^{(1)}\right)^{2}+\left(\bm{\beta}_{\bm{w}}^{(2)}\right)^{2}+...+\left(\bm{\beta}_{\bm{w}}^{(d)}\right)^{2}+\left(\bm{\beta}_{\bm{w}}^{\prime}\right)^{2}\mathrm{d}\mathbb{P}(\bm{w}) (49) s.t. ∫ 𝒘 ⊤ ​ 𝒙 i ≥ 0 𝜷 𝒘 ⊤ ​ 𝒙 i + 𝜷 𝒘 ′ ⋅ 𝒘 ⊤ ​ 𝒙 i ​ 𝑑 ℙ ​ ( 𝒘 ) = 𝜷 g ⊤ ​ 𝒙 i ​ ∀ i ∈ [ n ] , \displaystyle\int\limits_{\bm{w}^{\top}\bm{x}_{i}\geq 0}\bm{\beta}_{\bm{w}}^{\top}\bm{x}_{i}+\bm{\beta}_{\bm{w}}^{\prime}\cdot\bm{w}^{\top}\bm{x}_{i}\;\;\mathrm{d}\mathbb{P}(\bm{w})=\bm{\beta}_{g}^{\top}\bm{x}_{i}\;\;\;\forall i\in[n], (50) where the density of 𝒘 \bm{w} is now uniform on the unit sphere of ℝ d \mathbb{R}^{d} . Observe that since 𝒘 \bm{w} is from a uniform distribution, the probability density function ℙ ⁡ ( 𝒘 ) \mathbb{P}(\bm{w}) is a constant. This means every 𝒙 i \bm{x}_{i} is activated by half of the 𝒘 \bm{w} on the unit sphere, which implies we can now write the right hand side of Eqn. 50 in the form of left hand side, i.e., integral form. This allows us to further simplify Eqn. 50 as ∫ 𝒘 ⊤ ​ 𝒙 i ≥ 0 ( 𝜷 𝒘 ⊤ + 𝜷 𝒘 ′ ⋅ 𝒘 ⊤ − 2 ⋅ 𝜷 g ⊤ ) ​ 𝒙 i ​ 𝑑 ℙ ​ ( 𝒘 ) = 0 ​ ∀ i ∈ [ n ] , \displaystyle\int\limits_{\bm{w}^{\top}\bm{x}_{i}\geq 0}\left(\bm{\beta}_{\bm{w}}^{\top}+\bm{\beta}_{\bm{w}}^{\prime}\cdot\bm{w}^{\top}-2\cdot\bm{\beta}_{g}^{\top}\right)\bm{x}_{i}\;\;\mathrm{d}\mathbb{P}(\bm{w})=0\;\;\;\forall i\in[n], (51) where Eqn. 51 follows from the following steps of simplification ∫ 𝒘 ⊤ ​ 𝒙 i ≥ 0 𝜷 𝒘 ( 1 ) ​ 𝒙 i ( 1 ) + . . 𝜷 𝒘 ( d ) ​ 𝒙 i ( d ) + 𝜷 𝒘 ′ ⋅ 𝒘 ⊤ ​ 𝒙 i ​ 𝑑 ℙ ​ ( 𝒘 ) = 𝜷 g ( 1 ) ​ 𝒙 i ( 1 ) + … ​ 𝜷 g ( d ) ​ 𝒙 i ( d ) ​ ∀ i ∈ [ n ] , \displaystyle\int\limits_{\bm{w}^{\top}\bm{x}_{i}\geq 0}\bm{\beta}_{\bm{w}}^{(1)}\bm{x}_{i}^{(1)}+..\bm{\beta}_{\bm{w}}^{(d)}\bm{x}_{i}^{(d)}+\bm{\beta}_{\bm{w}}^{\prime}\cdot\bm{w}^{\top}\bm{x}_{i}\mathrm{d}\mathbb{P}(\bm{w})=\bm{\beta}_{g}^{(1)}\bm{x}_{i}^{(1)}+...\bm{\beta}_{g}^{(d)}\bm{x}_{i}^{(d)}\;\;\forall i\in[n], ⟺ \displaystyle\Longleftrightarrow ∫ 𝒘 ⊤ ​ 𝒙 i ≥ 0 𝜷 𝒘 ( 1 ) ​ 𝒙 i ( 1 ) + … + 𝜷 𝒘 ( d ) ​ 𝒙 i ( d ) + 𝜷 𝒘 ′ ⋅ 𝒘 ⊤ ​ 𝒙 i ​ 𝑑 ℙ ​ ( 𝒘 ) \displaystyle\int\limits_{\bm{w}^{\top}\bm{x}_{i}\geq 0}\bm{\beta}_{\bm{w}}^{(1)}\bm{x}_{i}^{(1)}+...+\bm{\beta}_{\bm{w}}^{(d)}\bm{x}_{i}^{(d)}+\bm{\beta}_{\bm{w}}^{\prime}\cdot\bm{w}^{\top}\bm{x}_{i}\;\mathrm{d}\mathbb{P}(\bm{w}) = 1 ∫ 𝒘 ⊤ ​ 𝒙 i ≥ 0 d ​ ℙ ​ ( 𝒘 ) ⋅ ∫ 𝒘 ⊤ ​ 𝒙 i ≥ 0 d ℙ ( 𝒘 ) ⋅ ( 𝜷 g ( 1 ) 𝒙 i ( 1 ) + … + 𝜷 g ( d ) 𝒙 i ( d ) ) ∀ i ∈ [ n ] , \displaystyle=\frac{1}{\int\limits_{\bm{w}^{\top}\bm{x}_{i}\geq 0}\mathrm{d}\mathbb{P}(\bm{w})}\cdot\int\limits_{\bm{w}^{\top}\bm{x}_{i}\geq 0}\mathrm{d}\mathbb{P}(\bm{w})\cdot\left(\bm{\beta}_{g}^{(1)}\bm{x}_{i}^{(1)}+...+\bm{\beta}_{g}^{(d)}\bm{x}_{i}^{(d)}\right)\;\;\;\forall i\in[n], ⟺ \displaystyle\Longleftrightarrow ∫ 𝒘 ⊤ ​ 𝒙 i ≥ 0 𝜷 𝒘 ( 1 ) ​ 𝒙 i ( 1 ) + … + 𝜷 𝒘 ( d ) ​ 𝒙 i ( d ) + 𝜷 𝒘 ′ ⋅ 𝒘 ⊤ ​ 𝒙 i ​ 𝑑 ℙ ​ ( 𝒘 ) \displaystyle\int\limits_{\bm{w}^{\top}\bm{x}_{i}\geq 0}\bm{\beta}_{\bm{w}}^{(1)}\bm{x}_{i}^{(1)}+...+\bm{\beta}_{\bm{w}}^{(d)}\bm{x}_{i}^{(d)}+\bm{\beta}_{\bm{w}}^{\prime}\cdot\bm{w}^{\top}\bm{x}_{i}\mathrm{d}\mathbb{P}(\bm{w}) = 2 ⋅ ∫ 𝒘 ⊤ ​ 𝒙 i ≥ 0 𝜷 g ( 1 ) ​ 𝒙 i ( 1 ) + … + 𝜷 g ( d ) ​ 𝒙 i ( d ) ​ 𝑑 ℙ ​ ( 𝒘 ) ​ ∀ i ∈ [ n ] , \displaystyle=2\cdot\int\limits_{\bm{w}^{\top}\bm{x}_{i}\geq 0}\bm{\beta}_{g}^{(1)}\bm{x}_{i}^{(1)}+...+\bm{\beta}_{g}^{(d)}\bm{x}_{i}^{(d)}\mathrm{d}\mathbb{P}(\bm{w})\;\;\;\forall i\in[n], ⟺ \displaystyle\Longleftrightarrow ∫ 𝒘 ⊤ ​ 𝒙 i ≥ 0 ( 𝜷 𝒘 ⊤ + 𝜷 𝒘 ′ ⋅ 𝒘 ⊤ − 2 ⋅ 𝜷 g ⊤ ) ​ 𝒙 i ​ 𝑑 ℙ ​ ( 𝒘 ) = 0 ​ ∀ i ∈ [ n ] . \displaystyle\int\limits_{\bm{w}^{\top}\bm{x}_{i}\geq 0}\left(\bm{\beta}_{\bm{w}}^{\top}+\bm{\beta}_{\bm{w}}^{\prime}\cdot\bm{w}^{\top}-2\cdot\bm{\beta}_{g}^{\top}\right)\bm{x}_{i}\;\;\mathrm{d}\mathbb{P}(\bm{w})=0\;\;\;\forall i\in[n].

###### Claim 1 .

Without loss of generality, assume the scaling factor c c in NTK feature map ϕ ⁡ ( 𝐱 ) \phi(\bm{x}) is 1 1 . Then the global optimum to the constraint optimization problem Eqn. 49 subject to Eqn. 51 , i.e., min ⁡ ∫ 𝜷 ⁡ ( 𝜷 𝒘 ( 1 ) ) 2 + ( 𝜷 𝒘 ( 2 ) ) 2 + … + ( 𝜷 𝒘 ( d ) ) 2 + ( 𝜷 𝒘 ′ ) 2 ​ 𝑑 ℙ ​ ( 𝒘 ) \displaystyle\min_{\bm{\beta}}\int\left(\bm{\beta}_{\bm{w}}^{(1)}\right)^{2}+\left(\bm{\beta}_{\bm{w}}^{(2)}\right)^{2}+...+\left(\bm{\beta}_{\bm{w}}^{(d)}\right)^{2}+\left(\bm{\beta}_{\bm{w}}^{\prime}\right)^{2}\mathrm{d}\mathbb{P}(\bm{w}) (52) s.t. ∫ 𝒘 ⊤ ​ 𝒙 i ≥ 0 ( 𝜷 𝒘 ⊤ + 𝜷 𝒘 ′ ⋅ 𝒘 ⊤ − 2 ⋅ 𝜷 g ⊤ ) ​ 𝒙 i ​ 𝑑 ℙ ​ ( 𝒘 ) = 0 ​ ∀ i ∈ [ n ] . \displaystyle\int\limits_{\bm{w}^{\top}\bm{x}_{i}\geq 0}\left(\bm{\beta}_{\bm{w}}^{\top}+\bm{\beta}_{\bm{w}}^{\prime}\cdot\bm{w}^{\top}-2\cdot\bm{\beta}_{g}^{\top}\right)\bm{x}_{i}\;\;\mathrm{d}\mathbb{P}(\bm{w})=0\;\;\;\forall i\in[n]. (53) satisfies 𝛃 𝐰 + 𝛃 𝐰 ′ ⋅ 𝐰 = 2 ​ 𝛃 g \bm{\beta}_{\bm{w}}+\bm{\beta}_{\bm{w}}^{\prime}\cdot\bm{w}=2\bm{\beta}_{g} for all 𝐰 \bm{w} .

This claim implies the exact extrapolation we want to prove, i.e., f NTK ​ ( 𝒙 ) = g ​ ( 𝒙 ) f_{\text{NTK}}(\bm{x})=g(\bm{x}) . This is because, if our claim holds, then for any 𝒙 ∈ ℝ d \bm{x}\in\mathbb{R}^{d} f NTK ​ ( 𝒙 ) \displaystyle f_{\text{NTK}}(\bm{x}) = ∫ 𝒘 ⊤ ​ 𝒙 ≥ 0 𝜷 w ⊤ ​ 𝒙 + 𝜷 𝒘 ′ ⋅ 𝒘 ⊤ ​ 𝒙 ​ 𝑑 ℙ ​ ( 𝒘 ) \displaystyle=\int_{\bm{w}^{\top}\bm{x}\geq 0}\bm{\beta}_{w}^{\top}\bm{x}+\bm{\beta}_{\bm{w}}^{\prime}\cdot\bm{w}^{\top}\bm{x}\;\;\mathrm{d}\mathbb{P}(\bm{w}) = ∫ 𝒘 ⊤ ​ 𝒙 ≥ 0 2 ⋅ 𝜷 g ⊤ ​ 𝒙 ​ 𝑑 ℙ ​ ( 𝒘 ) \displaystyle=\int_{\bm{w}^{\top}\bm{x}\geq 0}2\cdot\bm{\beta}_{g}^{\top}\bm{x}\;\;\mathrm{d}\mathbb{P}(\bm{w}) = ∫ 𝒘 ⊤ ​ 𝒙 ≥ 0 d ​ ℙ ​ ( 𝒘 ) ⋅ 2 ​ 𝜷 g ⊤ ​ 𝒙 \displaystyle=\int_{\bm{w}^{\top}\bm{x}\geq 0}\mathrm{d}\mathbb{P}(\bm{w})\cdot 2\bm{\beta}_{g}^{\top}\bm{x} = 1 2 ⋅ 2 ​ 𝜷 g ⊤ ​ 𝒙 = g ⁡ ( 𝒙 ) \displaystyle=\frac{1}{2}\cdot 2\bm{\beta}_{g}^{\top}\bm{x}=g(\bm{x})

Thus, it remains to prove Claim 1 . To compute the optimum to the constrained optimization problem Eqn. 52 , we consider the Lagrange multipliers. It is clear that the objective Eqn. 52 is convex. Moreover, the constraint Eqn. 53 is affine. Hence, by KKT, solution that satisfies the Lagrange condition will be the global optimum. We compute the Lagrange multiplier as ℒ ⁡ ( 𝜷 , λ ) = \displaystyle\mathcal{L}(\bm{\beta},\lambda)= ∫ ( 𝜷 𝒘 ( 1 ) ) 2 + ( 𝜷 𝒘 ( 2 ) ) 2 + … + ( 𝜷 𝒘 ( d ) ) 2 + ( 𝜷 𝒘 ′ ) 2 ​ 𝑑 ℙ ​ ( 𝒘 ) \displaystyle\int\left(\bm{\beta}_{\bm{w}}^{(1)}\right)^{2}+\left(\bm{\beta}_{\bm{w}}^{(2)}\right)^{2}+...+\left(\bm{\beta}_{\bm{w}}^{(d)}\right)^{2}+\left(\bm{\beta}_{\bm{w}}^{\prime}\right)^{2}\mathrm{d}\mathbb{P}(\bm{w}) (54) − ∑ i = 1 n λ i ⋅ ( ∫ 𝒘 ⊤ ​ 𝒙 i ≥ 0 ( 𝜷 𝒘 ⊤ + 𝜷 𝒘 ′ ⋅ 𝒘 ⊤ − 2 ⋅ 𝜷 g ⊤ ) 𝒙 i d ℙ ( 𝒘 ) ) \displaystyle-\sum\limits_{i=1}^{n}\lambda_{i}\cdot\left(\int\limits_{\bm{w}^{\top}\bm{x}_{i}\geq 0}\left(\bm{\beta}_{\bm{w}}^{\top}+\bm{\beta}_{\bm{w}}^{\prime}\cdot\bm{w}^{\top}-2\cdot\bm{\beta}_{g}^{\top}\right)\bm{x}_{i}\;\;\mathrm{d}\mathbb{P}(\bm{w})\right) (55)

Setting the partial derivative of ℒ ⁡ ( 𝜷 , λ ) \mathcal{L}(\bm{\beta},\lambda) with respect to each variable to zero gives ∂ ℒ ∂ 𝜷 𝒘 ( k ) = 2 ​ 𝜷 𝒘 ( k ) ​ ℙ ​ ( 𝒘 ) + ∑ i = 1 n λ i ⋅ 𝒙 i ( k ) ⋅ 𝕀 ⁡ ( 𝒘 ⊤ ​ 𝒙 i ≥ 0 ) = 0 \displaystyle\frac{\partial\mathcal{L}}{\partial\bm{\beta}_{\bm{w}}^{(k)}}=2\bm{\beta}_{\bm{w}}^{(k)}\mathbb{P}(\bm{w})+\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)=0 (56) ∂ ℒ 𝜷 𝒘 ′ = 2 ​ 𝜷 𝒘 ′ ​ ℙ ​ ( 𝒘 ) + ∑ i = 1 n λ i ⋅ 𝒘 ⊤ ​ 𝒙 i ⋅ 𝕀 ⁡ ( 𝒘 ⊤ ​ 𝒙 i ≥ 0 ) = 0 \displaystyle\frac{\partial\mathcal{L}}{\bm{\beta}_{\bm{w}}^{\prime}}=2\bm{\beta}_{\bm{w}}^{\prime}\mathbb{P}(\bm{w})+\sum\limits_{i=1}^{n}\lambda_{i}\cdot\bm{w}^{\top}\bm{x}_{i}\cdot\mathbb{I}\left(\bm{w}^{\top}\bm{x}_{i}\geq 0\right)=0 (57) ∂ ℒ ∂ λ i = ∫ 𝒘 ⊤ ​ 𝒙 i ≥ 0 ( 𝜷 𝒘 ⊤ + 𝜷 𝒘 ′ ⋅ 𝒘 ⊤ − 2 ⋅ 𝜷 g ⊤ ) ​ 𝒙 i ​ 𝑑 ℙ ​ ( 𝒘 ) = 0 \displaystyle\frac{\partial\mathcal{L}}{\partial\lambda_{i}}=\int\limits_{\bm{w}^{\top}\bm{x}_{i}\geq 0}\left(\bm{\beta}_{\bm{w}}^{\top}+\bm{\beta}_{\bm{w}}^{\prime}\cdot\bm{w}^{\top}-2\cdot\bm{\beta}_{g}^{\top}\right)\bm{x}_{i}\;\;\mathrm{d}\mathbb{P}(\bm{w})=0 (58) It is clear that the solution in Claim 1 immediately satisfies Eqn. 58 . Hence, it remains to show there exist a set of λ i \lambda_{i} for i ∈ [ n ] i\in[n] that satisfies Eqn. 56 and Eqn. 57 . We can simplify Eqn. 56 as 𝜷 𝒘 ( 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), (59) where c c is a constant. Similarly, we can simplify Eqn. 57 as 𝜷 𝒘 ′ = c ⋅ ∑ i = 1 n λ i ⋅ 𝒘 ⊤ ​ 𝒙 i ⋅ 𝕀 ⁡ ( 𝒘 ⊤ ​ 𝒙 i ≥ 0 ) \displaystyle\bm{\beta}_{\bm{w}}^{\prime}=c\cdot\sum\limits_{i=1}^{n}\lambda_{i}\cdot\bm{w}^{\top}\bm{x}_{i}\cdot\mathbb{I}\left(\bm{w}^{\top}\bm{x}_{i}\geq 0\right) (60) Observe that combining Eqn. 59 and Eqn. 60 implies that the constraint Eqn. 60 can be further simplified as 𝜷 𝒘 ′ = 𝒘 ⊤ ​ 𝜷 𝒘 \displaystyle\bm{\beta}_{\bm{w}}^{\prime}=\bm{w}^{\top}\bm{\beta}_{\bm{w}} (61)

It remains to show that given the condition on training data, there exists a set of λ i \lambda_{i} so that Eqn. 59 and Eqn. 61 are satisfied.

##### Global optimum via the geometry of training data.