Introduction
Gaussian process (GP) models [60 ] are a popular choice for probabilistic modeling. Given their strong priors they are especially popular in low data regimes and their interpretable uncertainties make them ideally suited for sequential decision tasks such as Bayesian optimization [13 , 21 ] and Reinforcement Learning [16 , 35 ] . For the modeling assumption of GPs, the inference procedure leads to a natural factorization of the uncertainty into an aleatoric and an epistemic part. As we often specify the model before seeing the data, there are scenarios where the model does not correspond to the data generation process, which we refer to as model mismatch . Box [11 ] famously stated “all models are wrong but some are useful” which means that these assumptions very rarely match the data generation process. In active learning scenarios such as Bayesian optimization, modeling and decision making are often seen as two separate tasks. We first model the data, then make decisions on where to model next. In scenarios of model mismatch this can have severely limiting effects, as we might introduce data, which has detrimental effects on the model that is relevant to the task.
More formally, the interaction of the aleatoric and epistemic components of the predictive uncertainty is not intrinsic to the data alone, but is induced by the choice of model and the task [65 ] . First, in most cases, the choice of model is made a priori , and may be misaligned for the considered task, while we retain full control over the subset of data used during training. Secondly, many machine learning tasks only require accurate predictions in a target region of the input domain, whereas available observations may originate from a broader region with a potentially different distribution. This distribution shift may lead to a misattribution between the aleatoric and epistemic uncertainty within the target region. As a result, incorporating additional observations can have adverse effects: (i) the aleatoric noise level in the target region may increase significantly when certain observations are included, and (ii) may cause some samples to counteract variance reduction precisely in the target region. Both effects arise because observations that improve the global model fit may be uninformative or even detrimental to predictions in the target region. This is particularly interesting, since in many machine learning tasks, such as transductive learning [48 ] and experimental design [12 ] , the target region in which predictions are made is known beforehand. This knowledge is used in many sequential learning algorithms for BO and RL to select new samples according to information-theoretic acquisition functions, under the assumption that more observed samples strictly improve performance. However, in scenarios of model mismatch, we obtain the described non-trivial model-data dependency of the aleatoric and epistemic uncertainty, which results in potentially detrimental influences of early observed samples for the entire learning process.
To address these limitations, we propose Forgetting to Improve (F2I), a principled data removal algorithm that “forgets ” data points with detrimental influence on the predictions within the target region in transductive learning tasks. As we cannot rely on having access to labels to measure generalization in the target region, we focus instead on reducing predictive uncertainty. This is achieved by determining the influence of individual samples on the predictive uncertainty, consisting of the model-data dependent and location-specific epistemic and global aleatoric uncertainties. Samples with detrimental influence are removed to improve predictions and confidence in transductive learning, as visualized for a real-world stock market data set in Figure 1 . Especially sequential learning tasks, such as BO and RL, can benefit significantly from this removal paradigm when detrimental samples have been evaluated in the beginning of the optimization process.
Figure 1. Influence of detrimental data structures based on the Dow Jones data set [4 ] . (Left) Homoscedastic GP absorbs detrimental structures in the noise, resulting in uncertain predictions in A \mathcal{A} A A \mathcal{A} A
Our contributions include theoretical grounding and practical evidence of Forgetting to Improve:
We propose a principled measure to quantify the contribution of individual samples to the epistemic and aleatoric components of the predictive uncertainty.
We introduce the greedy data removal algorithm F2I to “forget” detrimental data points in transductive learning tasks. In addition, we derive a near-optimality confidence for F2I and provide a rigorous analysis by establishing approximation bounds on the predictive uncertainty with respect to the optimal data subset.
We extend F2I to Forgetful BO and Forgetful RL, formulating BO and RL as sequential transductive learning tasks with dynamical target regions.
We conduct an extensive empirical evaluation of F2I and Forgetful BO on several different transductive and sequential learning tasks.
Related Literature
Prior works on probabilistic models and their use in uncertainty-aware learning algorithms fall broadly into two categories: (i) principled methods that focus on choosing the best next unseen sample to improve predictions and (ii) algorithms aiming to improve predictions given a fixed set of samples.
Targeted Data Acquisition A canonical line of work focuses on “where to sample next ”. While active learning aims to optimally select informative sampling locations, transductive active learning has additional knowledge about the desired target region, where predictions will be made. Early work [48 ] introduced information-theoretic criteria for selecting samples that are most informative for a fixed target region. This perspective has recently been revisited empirically for different settings [39 , 64 , 72 ] . and information-theoretically extended in [63 , 75 ] . Recently, optimality guarantees were derived in [30 ] for these decision rules in transductive learning and BO. Closely related ideas appear in optimal sensor placement and Bayesian experimental design, for which acquisition functions have been designed to maximize information gain or reduce posterior uncertainty [29 , 42 , 63 ] . However, these approaches require strict assumptions on well-behaved objectives and focus exclusively on selecting new samples and leveraging all collected data. Meaning that once a sample is acquired, it is never revisited, even if it later proves detrimental under model mismatch for the specific task. In contrast, our work addresses the complementary and largely unexplored question “which samples should be removed”.
Robustness via Correction and Reweighting A large body of work addresses robustness in probabilistic modeling with data preprocessing, alternative likelihoods, or noise modeling. Data curation and preprocessing methods [14 ] aim to remove corrupted samples before training. These methods are typically model-agnostic, assume access to the full dataset beforehand, may introduce unintended biases, and have limited applicability in sequential tasks. In contrast, robust GP formulations modify the likelihood or noise model to mitigate the influence of detrimental data structures. This includes heavy-tailed likelihoods, such as Student-t [34 ] , Laplace [59 ] , and Huber losses [1 ] . These have been proven to be effective against global noise misspecification. However, noise can also be locally dependent, which is addressed in a different line of work by introducing noise models to determine input-dependent noise distributions using heteroscedastic [25 , 37 , 45 , 73 ] or twinned GPs [52 ] . Although these approaches allow local noise variations, the underlying noise distribution has to be smooth with respect to the input. Additionally, these methods do not take into account task-specific prediction regions and allow modeling structures of interest with the noise model. More closely related methods remove or down-weight data points. Trimmed likelihood approaches select subsets of data that maximize the marginal likelihood [5 , 7 ] , however require a prespecified fraction of detrimental samples [7 ] , or converge to a locally stationary point without optimality guarantees [5 ] . Therefore, these methods may unnecessarily remove points for well-behaved objectives or in the target region of our predictions. Other strategies rely on residual-based heuristic pruning [47 ] or structured noise models that assume clustered outliers [2 ] . Latent variable and input warping approaches aim to absorb the model mismatch by reshaping the input space [10 , 66 ] . The latent GP model separates inputs with detrimental structure by introducing an additional dimension and performing computationally expensive posterior sampling with MCMC over the separation, while input warping is only capable of transforming the entire input space globally, ignoring local structures. Related work also considers modifications in the output space, by assuming biased observations of the form y ( x ) = f ( x ) + δ ( x ) + ϵ y(x) = f(x) + \delta(x) + \epsilon y ( x ) = f ( x ) + δ ( x ) + ϵ ϵ ∼ N ( 0 , σ 2 ) \epsilon\sim\mathcal{N}(0, \sigma^2) ϵ ∼ N ( 0 , σ 2 ) δ ( x ) \delta(x) δ ( x ) [4 , 56 ] . While both methods introduce learnable data-point-specific biases, [56 ] optimizes the negative marginal log likelihood in a single step, which generally does not lead to sparsity in the biases, in contrast to [4 ] . Consequently, [10 , 4 ] are most closely related to our work, as they induce effects similar to the removal of detrimental samples by distancing them in the input space or adding a large bias in the output space. Unlike latent-space or bias-based methods, which implicitly reduce the influence of detrimental samples through additional modeling assumptions, our approach explicitly selects a task-optimal subset of data with theoretical guarantees. Furthermore, our per-sample influence is related to classical influence-functions and data-valuation approaches [38 , 23 ] , that quantify single sample attributions on a global estimator or loss. Crucially, our measure enables principled task-specific removals rather than global reweighting.
Problem Setting
We consider in this work a standard Gaussian process regression setting. Let X \mathcal{X} X f : X → R f : \mathcal{X} \to\mathbb{R} f : X → R f f f f ∼ GP ( 0 , k ( ⋅ , ⋅ ) ) f \sim\operatorname{GP}(0, k(\cdot,\cdot)) f ∼ GP ( 0 , k ( ⋅ , ⋅ )) k k k S : = { x i , y i } i = 1 n ⊆ X × R \mathcal{S} := \{x_i, y_i\}_{i=1}^{n} \subseteq\mathcal{X} \times\mathbb{R} S := { x i , y i } i = 1 n ⊆ X × R y i = f ( x i ) + ϵ i y_i = f(x_i) + \epsilon_i y i = f ( x i ) + ϵ i ϵ i ∼ N ( 0 , σ w 2 ) \epsilon_i \sim\mathcal{N}(0, \sigma_w^2) ϵ i ∼ N ( 0 , σ w 2 ) σ w 2 \sigma_w^2 σ w 2 p ( σ w 2 ) p(\sigma_w^2) p ( σ w 2 ) [51 ]
σ w 2 ( S ) = arg max σ w 2 L ( σ w 2 , S ) : = log ∏ i = 1 n p ( y i ∣ x i ; σ w 2 ) + log p ( σ w 2 ) . (1) \sigma_w^2(\mathcal{S}) = \arg\max_{\sigma_w^2} \mathcal{L}(\sigma_w^2,\mathcal{S}) := \log\prod_{i=1}^{n} p(y_i|x_i;\sigma_w^2) + \log p(\sigma_w^2). \tag*{(1)} σ w 2 ( S ) = arg σ w 2 max L ( σ w 2 , S ) := log i = 1 ∏ n p ( y i ∣ x i ; σ w 2 ) + log p ( σ w 2 ) . (1) The predictive distribution of a GP trained on the subset S ′ ⊆ S \mathcal{S}' \subseteq\mathcal{S} S ′ ⊆ S x x x
σ S ′ 2 ( x ) = k ( x , x ) − k x , S ′ ( K + σ w 2 ( S ′ ) I ) − 1 k S ′ , x + σ w 2 ( S ′ ) I , (2) \sigma_{\mathcal{S}'}^2(x) = k(x,x) - k_{x,\mathcal{S}'}(K + \sigma_w^2(\mathcal{S}')I)^{-1}k_{\mathcal{S}',x} + \sigma_w^2(\mathcal{S}')I, \tag*{(2)} σ S ′ 2 ( x ) = k ( x , x ) − k x , S ′ ( K + σ w 2 ( S ′ ) I ) − 1 k S ′ , x + σ w 2 ( S ′ ) I , (2) where K = k ( S ′ , S ′ ) K = k(S', S') K = k ( S ′ , S ′ ) S ′ S' S ′ k x , S ′ = [ k ( x , x i ) ] x i ∈ S ′ k_{x,S'} = [k(x, x_i)]_{x_i \in S'} k x , S ′ = [ k ( x , x i ) ] x i ∈ S ′ σ ω 2 ( S ′ ) \sigma^2_{\omega}(S') σ ω 2 ( S ′ )
Our goal is to find a subset S ′ ⊆ S S' \subseteq S S ′ ⊆ S A ⊆ X A \subseteq\mathcal{X} A ⊆ X predictive uncertainty becomes a natural objective, as it characterizes the information content of the posterior distribution in A A A subset S ′ ⊆ S S' \subseteq S S ′ ⊆ S that minimizes the predictive uncertainty in A A A
min S ′ ⊆ S J ( S ′ ) , J ( S ′ ) = ∑ x ∈ A σ S ′ 2 ( x ) . (3) \min_{S' \subseteq S} \mathcal{J}(S'), \qquad\mathcal{J}(S') = \sum_{x \in A} \sigma^2_{S'}(x). \tag*{(3)} S ′ ⊆ S min J ( S ′ ) , J ( S ′ ) = x ∈ A ∑ σ S ′ 2 ( x ) . (3) This closely relates to established principles in Bayesian Optimization and Reinforcement Learning , where uncertainty guides exploration and balances exploitation (see § 5 and § 6 ).
Forgetting to Improve – Principled Data Removal
We propose Forgetting to Improve (F2I), a principled data-removal algorithm to find the subset S ′ S' S ′ (3) by greedily removing data points based on our predictive uncertainty influence measure. The influence measure naturally decomposes into the sum of per-example aleatoric and epistemic terms. In this section, we derive these terms, present the full algorithm, and discuss its optimality.
Tracing Epistemic Uncertainty Back to Data A natural strategy for data selection, deeply rooted in related works of active learning, is to select data with the maximum gain in information for the given task. For transductive learning, this reduces to choosing the sample that minimizes the epistemic uncertainty in the target region A A A (3) is combinatorial and computationally infeasible for large data sets. Leave-one-out (LOO) methods instead greedily remove the sample with the highest influence, which for example i i i σ S ∖ { x i , y i } 2 − σ S 2 \sigma^2_{S \setminus\{x_i,y_i\}} - \sigma^2_S σ S ∖ { x i , y i } 2 − σ S 2
To solve this, we first generalize the discrete LOO case via a continuous removal direction h h h k ( x , S , h ) = k x , S − h ⊙ k x , S k(x,S,h) = k_{x,S} - h \odot k_{x,S} k ( x , S , h ) = k x , S − h ⊙ k x , S σ S 2 ( h ) \sigma^2_S(h) σ S 2 ( h ) h h h h h h e i e_i e i σ S 2 \sigma^2_S σ S 2 σ S ∖ { x i , y i } 2 \sigma^2_{S \setminus\{x_i,y_i\}} σ S ∖ { x i , y i } 2 σ S 2 ( h ) \sigma^2_S(h) σ S 2 ( h ) S S S h = 0 h = 0 h = 0 h = e i h = e_i h = e i σ S ∖ { x i , y i } 2 − σ S 2 ≈ e i ⋅ ∇ h σ S 2 ∣ h = 0 \sigma^2_{S \setminus\{x_i,y_i\}} - \sigma^2_S \approx e_i \cdot\nabla_h \sigma^2_S\big|_{h=0} σ S ∖ { x i , y i } 2 − σ S 2 ≈ e i ⋅ ∇ h σ S 2 h = 0
Proposition 1. Suppose we have a single test point A = { x } A = \{x\} A = { x } μ S ( x ) \mu_S(x) μ S ( x ) σ S 2 ( x ) \sigma^2_S(x) σ S 2 ( x ) S = { x i , y i } i = 1 n S = \{x_i,y_i\}_{i=1}^n S = { x i , y i } i = 1 n u i ( x ) u_i(x) u i ( x ) x i ∈ S x_i \in S x i ∈ S σ S 2 ( x ) \sigma^2_S(x) σ S 2 ( x ) h i h_i h i x i ∈ S x_i \in S x i ∈ S σ ω 2 ( S ) \sigma^2_\omega(S) σ ω 2 ( S ) *
u i ( x ) = 2 k x , x i ( A − 1 k S , x ) i − 2 ( A − 1 k S , x ) i ( k x i , S A − 1 k S , x ) , u_i(x) = 2k_{x,x_i}(A^{-1}k_{S,x})_i - 2(A^{-1}k_{S,x})_i(k_{x_i,S}A^{-1}k_{S,x}), u i ( x ) = 2 k x , x i ( A − 1 k S , x ) i − 2 ( A − 1 k S , x ) i ( k x i , S A − 1 k S , x ) , where k x , S = k ( x , S ) k_{x,S} = k(x,S) k x , S = k ( x , S ) A = K + σ ω 2 ( S ) I A = K + \sigma^2_\omega(S)I A = K + σ ω 2 ( S ) I K = k ( S , S ) K = k(S,S) K = k ( S , S )
Furthermore, in Proposition 2 we can interpret our derived influence measure u i u_i u i x i x_i x i x x x x x x k ( ⋅ ) k(\cdot) k ( ⋅ )
Proposition 2. Suppose the uncertainty difference at A = { x } A = \{x\} A = { x } i i i
Δ i ( x ) = σ S ∖ { x i , y i } 2 ( x ) − σ S 2 ( x ) = ( A − 1 k S , x ) i 2 A i , i . \Delta_i(x) = \sigma^2_{S \setminus\{x_i,y_i\}}(x) - \sigma^2_S(x) = \frac{(A^{-1}k_{S,x})_i^2}{A_{i,i}}. Δ i ( x ) = σ S ∖ { x i , y i } 2 ( x ) − σ S 2 ( x ) = A i , i ( A − 1 k S , x ) i 2 . Then, our uncertainty measure u u u k x , S k_{x,S} k x , S k x , x i k_{x,x_i} k x , x i u u u
k x , x i ∂ Δ i ∂ k x , x i = 2 k x , x i ( A − 1 k S , x ) i − 2 ( A − 1 k S , x ) i ( k x i , S A − 1 k S , x ) = u i ( x ) . k_{x,x_i}\frac{\partial\Delta_i}{\partial k_{x,x_i}} = 2k_{x,x_i}(A^{-1}k_{S,x})_i - 2(A^{-1}k_{S,x})_i(k_{x_i,S}A^{-1}k_{S,x}) = u_i(x). k x , x i ∂ k x , x i ∂ Δ i = 2 k x , x i ( A − 1 k S , x ) i − 2 ( A − 1 k S , x ) i ( k x i , S A − 1 k S , x ) = u i ( x ) . We refer to Section A.2 for the formal proofs of Propositions 1 and 2. Please note that the absolute uncertainty reduction Δ i ( x ) \Delta_i(x) Δ i ( x ) A A A u i ≥ 0 u_i \ge0 u i ≥ 0
How Data drives Aleatoric Uncertainty under Model Mismatch The derived epistemic influence measure u i u_i u i k k k σ w 2 ( S ) \sigma_w^2(S) σ w 2 ( S ) training data on the model-data mismatch absorbed by the noise σ w 2 ( S ) \sigma_w^2(S) σ w 2 ( S ) p ( σ w 2 ∣ a , b ) p(\sigma_w^2 \mid a,b) p ( σ w 2 ∣ a , b ) h i h_i h i
Proposition 3. Let A ( σ w 2 ( S ) ) = K ( S , S ) + σ w 2 ( S ) I A(\sigma_w^2(S)) = K(S,S) + \sigma_w^2(S)I A ( σ w 2 ( S )) = K ( S , S ) + σ w 2 ( S ) I σ w 2 ( S ) \sigma_w^2(S) σ w 2 ( S ) (1) ) L ( σ w 2 , S , a , b ) = D ( σ w 2 , S , a , b ) = 0 \mathcal{L}(\sigma_w^2,S,a,b) = \mathcal{D}(\sigma_w^2,S,a,b) = 0 L ( σ w 2 , S , a , b ) = D ( σ w 2 , S , a , b ) = 0 S S S σ w 2 ( S ) \sigma_w^2(S) σ w 2 ( S ) h i h_i h i ∂ σ w 2 ∂ h i = − ∂ ∂ h i D ( σ w 2 , S , a , b ) / ∂ ∂ σ w 2 D ( σ w 2 , S , a , b ) \frac{\partial\sigma_w^2}{\partial h_i} = -\frac{\partial}{\partial h_i}\mathcal{D}(\sigma_w^2,S,a,b)\big/\frac{\partial}{\partial\sigma_w^2}\mathcal{D}(\sigma_w^2,S,a,b) ∂ h i ∂ σ w 2 = − ∂ h i ∂ D ( σ w 2 , S , a , b ) / ∂ σ w 2 ∂ D ( σ w 2 , S , a , b )
∂ σ w 2 ( S ) ∂ h i = − ( A − 1 y ) i ( k x i , S ( A − 2 y ) ) − ( A − 2 y ) i ( k x i , S ( A − 1 y ) ) + k x i , S ( A − 2 ) ⋅ , i + y i ( A − 2 y ) i − y T A − 3 y + 1 2 tr ( A − 2 ) − a − 1 ( σ w 2 ) 2 \frac{\partial\sigma_w^2(S)}{\partial h_i} =
\frac{-(A^{-1}y)_i(k_{x_i,S}(A^{-2}y))-(A^{-2}y)_i(k_{x_i,S}(A^{-1}y))+k_{x_i,S}(A^{-2})_{\cdot,i}+y_i(A^{-2}y)_i}
{-y^{\mathsf T}A^{-3}y+\frac{1}{2}\operatorname{tr}(A^{-2})-\frac{a-1}{(\sigma_w^2)^2}} ∂ h i ∂ σ w 2 ( S ) = − y T A − 3 y + 2 1 tr ( A − 2 ) − ( σ w 2 ) 2 a − 1 − ( A − 1 y ) i ( k x i , S ( A − 2 y )) − ( A − 2 y ) i ( k x i , S ( A − 1 y )) + k x i , S ( A − 2 ) ⋅ , i + y i ( A − 2 y ) i :::
Given this sensitivity, we now derive the aleatoric influence measure v i ( x ) v_i(x) v i ( x ) h i h_i h i σ w 2 ( S ) \sigma_w^2(S) σ w 2 ( S )
Proposition 4. Suppose we have a single test point A = { x } A=\{x\} A = { x } μ S ( x ) \mu_S(x) μ S ( x ) σ S 2 ( x ) \sigma_S^2(x) σ S 2 ( x ) S = { x i , y i } i = 1 n S=\{x_i,y_i\}_{i=1}^{n} S = { x i , y i } i = 1 n v i ( x ) v_i(x) v i ( x ) x i ∈ S x_i\in S x i ∈ S σ w 2 ( S ) \sigma_w^2(S) σ w 2 ( S ) σ S 2 ( x ) \sigma_S^2(x) σ S 2 ( x ) h i h_i h i x i ∈ S x_i\in S x i ∈ S
v i ( x ) = ( 1 + k x , S A − 2 k S , x ) ∂ σ w 2 ( S ) ∂ h i v_i(x)=\left(1+k_{x,S}A^{-2}k_{S,x}\right)\frac{\partial\sigma_w^2(S)}{\partial h_i} v i ( x ) = ( 1 + k x , S A − 2 k S , x ) ∂ h i ∂ σ w 2 ( S ) where the partial derivative of the noise parameter is taken from Proposition 3.
We provide the mathematical derivations of Propositions 3 and 4 in Section A.3.
Forgetting to Improve Propositions 1 and 4 establish how removing samples from S S S A = { x } \mathcal{A}=\{x\} A = { x } A \mathcal{A} A u ( x ) u(x) u ( x ) v ( x ) v(x) v ( x ) u ( x ) u(x) u ( x ) v ( x ) v(x) v ( x ) u u u v v v x ∈ A x\in\mathcal{A} x ∈ A
Table 1.
greedy algorithm is based on the derivatives of the aleatoric and epistemic uncertainty of Propositions 1 and 4 and can hence be interpreted as a “reverse ” orthogonal matching pursuit algorithm [70 ] for the predictive uncertainty in A \mathcal{A} A J ( T ) = J ( S ) − J ( S ∖ T ) \mathcal{J}(T)=\mathcal{J}(S)-\mathcal{J}(S\setminus T) J ( T ) = J ( S ) − J ( S ∖ T ) [15 , 18 , 41 ] , we bound its optimal value using restricted strong concavity and impose a gradient-dominance condition along the executed removal sequence satisfying the Polyak–Łojasiewicz inequality [36 sec. 3.2] . Let m R , M R > 0 m_R, M_R > 0 m R , M R > 0
Assumption 1. Let T ′ = S ∖ S ′ T^\prime= S \setminus S^\prime T ′ = S ∖ S ′ q = ∣ T ′ ∣ ≥ 1 q = |T^\prime| \ge1 q = ∣ T ′ ∣ ≥ 1 T k = S ∖ S ( k ) T_k = S \setminus S^{(k)} T k = S ∖ S ( k ) g ( 0 ) = − u ( 0 ) ( A ) − v ( 0 ) ( A ) g^{(0)} = -u^{(0)}(\mathcal{A}) - v^{(0)}(\mathcal{A}) g ( 0 ) = − u ( 0 ) ( A ) − v ( 0 ) ( A ) g ( 1 ) ≥ ⋯ ≥ g ( ∣ S ∣ ) g^{(1)} \ge\cdots\ge g^{(|S|)} g ( 1 ) ≥ ⋯ ≥ g ( ∣ S ∣ ) k = 0 , … , q − 1 k = 0, \ldots, q - 1 k = 0 , … , q − 1
∥ u ( k ) ( A ) + v ( k ) ( A ) ∥ ∞ 2 ≥ 2 m R q [ U q − J ˉ ( T k ) ] + , U q = min { J ( S ) , ∑ i = 1 q g ( i ) ( 0 ) − m R q 2 2 } . \left\|u^{(k)}(\mathcal{A}) + v^{(k)}(\mathcal{A})\right\|_{\infty}^{2} \ge\frac{2m_R}{q}\left[U_q - \bar{J}(T_k)\right]_+,\qquad U_q = \min\left\{\mathcal{J}(S), \sum_{i=1}^{q}g_{(i)}^{(0)} - \frac{m_Rq^2}{2}\right\}. u ( k ) ( A ) + v ( k ) ( A ) ∞ 2 ≥ q 2 m R [ U q − J ˉ ( T k ) ] + , U q = min { J ( S ) , i = 1 ∑ q g ( i ) ( 0 ) − 2 m R q 2 } . This gives a conditional near-optimality bound in Theorem 1, under the checkable Assumption 1.
Theorem 1. Let J ˉ ( T ) = J ( S ) − J ( S ∖ T ) \bar{J}(T) = \mathcal{J}(S) - \mathcal{J}(S \setminus T) J ˉ ( T ) = J ( S ) − J ( S ∖ T ) T ′ = S ∖ S ′ T^\prime= S \setminus S^\prime T ′ = S ∖ S ′ q ≥ 1 q \ge1 q ≥ 1 σ w 2 \sigma_w^2 σ w 2 − J -\mathcal{J} − J m R m_R m R L = ∅ L = \varnothing L = ∅ U ⊆ S U \subseteq S U ⊆ S ∣ U ∣ = q |U| = q ∣ U ∣ = q
J ˉ ( T ′ ) ≥ ( 1 − e − γ ) max T ⋆ ⊆ S ∣ T ⋆ ∣ = ∣ T ′ ∣ J ˉ ( T ⋆ ) , γ = ρ m R M R , \bar{J}(T^\prime) \ge\left(1-e^{-\gamma}\right)\max_{\substack{T^\star\subseteq S\\|T^\star|=|T^\prime|}}\bar{J}(T^\star),\qquad\gamma=\rho\frac{m_R}{M_R}, J ˉ ( T ′ ) ≥ ( 1 − e − γ ) T ⋆ ⊆ S ∣ T ⋆ ∣ = ∣ T ′ ∣ max J ˉ ( T ⋆ ) , γ = ρ M R m R , for the restricted smoothness M R > 0 M_R > 0 M R > 0 ρ = min 0 ≤ k < q 2 M R [ J ( S ( k ) ) − J ( S ( k + 1 ) ) ] ∥ u ( k ) ( A ) + v ( k ) ( A ) ∥ ∞ 2 > 0 \rho= \min_{0\le k<q}\frac{2M_R\left[\mathcal{J}(S^{(k)})-\mathcal{J}(S^{(k+1)})\right]}{\left\|u^{(k)}(\mathcal{A})+v^{(k)}(\mathcal{A})\right\|_{\infty}^{2}} > 0 ρ = min 0 ≤ k < q ∥ u ( k ) ( A ) + v ( k ) ( A ) ∥ ∞ 2 2 M R [ J ( S ( k ) ) − J ( S ( k + 1 ) ) ] > 0
Proof Sketch A detailed outline of the proof is given in Section G.1. First, we define J ˉ \bar{J} J ˉ − u i ( A ) − v i ( A ) -u_i(\mathcal{A}) - v_i(\mathcal{A}) − u i ( A ) − v i ( A ) − J ˉ -\bar{J} − J ˉ U q U_q U q q q q ρ \rho ρ U q U_q U q q q q
Forgetful Bayesian Optimization
We extend F2I to Bayesian optimization by viewing BO as a sequence of transductive learning problems, each defined by a dynamically shrinking region of interest. The key idea is to remove samples that distort posterior uncertainty exactly where the acquisition function relies on it. This allows us to improve optimization performance without modifying the acquisition function itself. Therefore, we consider an unknown objective function f ( x ) : X → R f(x):\mathcal{X}\to\mathbb{R} f ( x ) : X → R x ∗ = arg max x ∈ X f ( x ) x^\ast=\arg\max_{x\in\mathcal{X}}f(x) x ∗ = arg max x ∈ X f ( x )
Model Mismatch in Bayesian Optimization The model-mismatch effects studied in Section 4 are particularly problematic in Bayesian optimization. Since BO relies on uncertainty-aware acquisition functions, such as the GP Upper Confidence Bound (GP-UCB) [67 ] , logarithmic Expected Improvement (logEI) [3 ] , Expected Improvement (EI) and Probability of Improvement [33 , 50 ] , misleading posterior uncertainty can directly harm exploration and exploitation decisions. Prior work addresses this issue through alternative likelihoods [49 ] , latent or warped input spaces [10 , 66 ] , tree-based structure [32 ] , or preference-based feedback [26 ] . In contrast to these approaches, which modify the model or acquisition function, we address the model mismatch by explicitly revising the set of observations used to form the posterior uncertainty, in each iteration.
Target Regions in Bayesian Optimization In order to address this problem, we propose to view BO as sequential transductive learning [30 ] . At each iteration, only a subset of the search space can plausibly contain the maximum. Improving predictive uncertainty outside this subset is therefore unnecessary and can even be harmful under model mismatch. We formalize this intuition by defining a region of interest and applying F2I for this region. The GP-UCB algorithm [67 ] provides a natural way to define such regions of interest. At each iteration t t t A t \mathcal{A}_t A t A t \mathcal{A}_t A t A t \mathcal{A}_t A t S t ( k ) S_t^{(k)} S t ( k ) k k k A t ( k ) \mathcal{A}_t^{(k)} A t ( k ) A t ( k ) \mathcal{A}_t^{(k)} A t ( k )
A t ( k ) ← { x i ∈ X : μ S t ( k ) ( x i ) + β t σ S t ( k ) ( x i ) ⏟ U C B ( x i ) > max x m ∈ X μ S t ( k ) ( x m ) − β t σ S t ( k ) ( x m ) ⏟ L C B ( x m ) } ∩ A t ( k − 1 ) . (4) \mathcal{A}_t^{(k)} \leftarrow\left\{x_i\in\mathcal{X}: \underbrace{\mu_{S_t^{(k)}}(x_i)+\beta_t\sigma_{S_t^{(k)}}(x_i)}_{\mathrm{UCB}(x_i)}>\max_{x_m\in\mathcal{X}}\underbrace{\mu_{S_t^{(k)}}(x_m)-\beta_t\sigma_{S_t^{(k)}}(x_m)}_{\mathrm{LCB}(x_m)}\right\}\cap\mathcal{A}_t^{(k-1)}. \tag*{(4)} A t ( k ) ← ⎩ ⎨ ⎧ x i ∈ X : UCB ( x i ) μ S t ( k ) ( x i ) + β t σ S t ( k ) ( x i ) > x m ∈ X max LCB ( x m ) μ S t ( k ) ( x m ) − β t σ S t ( k ) ( x m ) ⎭ ⎬ ⎫ ∩ A t ( k − 1 ) . (4) Accordingly chosen constants β t \beta_t β t [67 ] and therefore A t \mathcal{A}_t A t
Forgetful Reinforcement Learning
Building on F2I, we investigate by introducing Forgetful RL how the data removal paradigm mitigates model-data mismatch in model-based reinforcement learning. We consider a discounted Markov Decision Process (MDP) ( X , A , p , r , γ , ρ 0 ) (\mathcal{X}, \mathcal{A}, p, r, \gamma, \rho_0) ( X , A , p , r , γ , ρ 0 ) X \mathcal{X} X A \mathcal{A} A p ( x ′ ∣ x , a ) p(x' \mid x,a) p ( x ′ ∣ x , a ) r ( x , a ) r(x,a) r ( x , a ) γ ∈ ( 0 , 1 ) \gamma\in(0,1) γ ∈ ( 0 , 1 ) ρ 0 \rho_0 ρ 0 [16 , 31 ] , a world model is learned to simulate trajectories, enabling in each episode n = 1 , … , N n = 1,\ldots,N n = 1 , … , N π n \pi_n π n R ( π n ) = E π n [ ∑ t = 0 ∞ γ t r ( x t , a t ) ] R(\pi_n) = \mathbb{E}_{\pi_n}\left[\sum_{t=0}^{\infty}\gamma^t r(x_t,a_t)\right] R ( π n ) = E π n [ ∑ t = 0 ∞ γ t r ( x t , a t ) ] [69 ]
Q π n ( x , a ) = E π n [ ∑ t = 0 ∞ γ t r ( x t , a t ) ∣ x 0 = x , a 0 = a ] , V π n ( x ) = E a ∼ π n ( x ) [ Q π n ( x , a ) ] . (5) Q^{\pi_n}(x,a) = \mathbb{E}_{\pi_n}\left[\sum_{t=0}^{\infty}\gamma^t r(x_t,a_t) \mid x_0=x,a_0=a\right], \qquad V^{\pi_n}(x) = \mathbb{E}_{a\sim\pi_n(x)}\left[Q^{\pi_n}(x,a)\right]. \tag*{(5)} Q π n ( x , a ) = E π n [ t = 0 ∑ ∞ γ t r ( x t , a t ) ∣ x 0 = x , a 0 = a ] , V π n ( x ) = E a ∼ π n ( x ) [ Q π n ( x , a ) ] . (5) Since we only have limited data at episode n n n ( x , a ) (x,a) ( x , a )
A n = { ( x , a ) ∈ X × A : Q ‾ π n ( x , a ) ≥ min x m ∼ ρ 0 V π n ( x m ) ∧ Q ‾ π n ( x , a ) ≥ V π n ( x ) } , (6) \mathcal{A}_n = \left\{(x,a) \in\mathcal{X} \times\mathcal{A} : \overline{Q}^{\pi_n}(x,a) \ge\min_{x_m\sim\rho_0} V^{\pi_n}(x_m) \wedge\overline{Q}^{\pi_n}(x,a) \ge V^{\pi_n}(x)\right\}, \tag*{(6)} A n = { ( x , a ) ∈ X × A : Q π n ( x , a ) ≥ x m ∼ ρ 0 min V π n ( x m ) ∧ Q π n ( x , a ) ≥ V π n ( x ) } , (6) where Q ‾ π n \overline{Q}^{\pi_n} Q π n V ‾ π n \underline{V}^{\pi_n} V π n [58 ] in detail in Section C.
Experiments
We evaluate the empirical performance of F2I, Forgetful BO and Forgetful RL, using our implementation, based on GPyTorch [20 ] , BoTorch [8 ] , and MBRL-Lib [58 ] . Our results focus on (i) transductive regression tasks, improving predictions in a priori known target regions; (ii) BO, by removing detrimental data structures in the sequential learning tasks; and (iii) MBRL under global kernel misspecification of the GP world model.
Transductive Learning For many real-world applications, the desired prediction location is known a priori, which we refer to as target region A \mathcal{A} A S \mathcal{S} S X \mathcal{X} X transductive learning experiments , our aim is to improve the predictions in A \mathcal{A} A A \mathcal{A} A [17 ] , and sharpness , which is defined as the expected predictive variance in A \mathcal{A} A [44 , 46 , 22 ] , to quantify the coverage of predicted confidence intervals (CE) [44 ] , as well as the local calibration comparing the observed residuals (ECE) [46 ] . Based on these metrics, we compare F2I with a homoscedastic and a heteroscedastic GP [37 ] , domain warping GP [66 ] and relevance pursuit [4 ] on four transductive learning tasks. These include two synthetic test functions, described in Section E.1, and two real-world tasks using the Boston Housing dataset [28 ] and the intra-day data from the Dow Jones Industrial Average index [4 ] . We report in Figure 3 the mean relative performance across 100 different randomly sampled training points using the hyperparameters listed in Section E.1. The relative performance is computed with respect to the best and worst performing method. The numerical results, including standard deviations, are provided in Section E.1. As we minimize predictive uncertainty with our objective in Equation (3) , F2I achieves competitive predictive sharpness in A \mathcal{A} A Figure 2 shows this improvement for the task in Figure 1 . The top row shows the calibration improvement for unseen test samples in the target region A \mathcal{A} A X \mathcal{X} X
Figure 2. Empirical confidence p ^ \hat{p} p ^ p p p A \mathcal{A} A X \mathcal{X} X Figure 1 .
Figure 3. Benchmark comparison (mean over 100 training sample draws). F2I achieves competitive predictive sharpness while providing strong overall accuracy and calibration across the evaluations.
Bayesian Optimization We next investigate how these task-oriented prediction improvements translate to the sequential learning process of Forgetful BO. The BO performance is measured using simple regret , the difference between the best evaluation up to the current iteration t t t r ( t ) = f ( x ∗ ) − max 1 ≤ t ′ ≤ t f ( x t ′ ) r(t) = f(x^*) - \max_{1 \le t' \le t} f(x_{t'}) r ( t ) = f ( x ∗ ) − max 1 ≤ t ′ ≤ t f ( x t ′ ) T T T warped GP model [66 ] and the relevance pursuit model [4 ] , based on the BoTorch implementations [8 ] , as well as additional baselines in Section E.2, using the Matérn 5/2 kernel and a LogNormal(0, 1) for the prior lengthscale. In Figure 4 , we use the GP-UCB acquisition function [67 ] , while we also report results for the log expected improvement acquisition function [3 ] in Section E.2. We provide statistical results for 10 runs, with random initializations and a limited evaluation budget of T = 50 T = 50 T = 50 Figure 4 the mean simple regret and standard deviation for 8 test-functions [68 ] , using the default domains, provided together with the dimensionality in Section E.2. By forgetting detrimental data during the optimization task, Forgetful BO achieves a consistently low simple regret, while the performance of competing baselines strongly varies between test-functions. To demonstrate the advantage of removals, we visualize this behavior for a two dimensional test function in Figure 6 of Section B. In Sections E.2 and F.3, we additionally demonstrate superior performance of Forgetful BO for noisy tasks with sparse outliers, and the computational efficiency of Forgetful BO.
Figure 4. Simple regret across different test functions. Forgetful BO consistently achieves low simple regret, while competing baselines exhibit strong variability across tasks.
Figure 6. Forgetful BO: Visualization of sequential removal mechanism integrated in BO pipeline.
Reinforcement Learning We demonstrate the full potential of data removal under model-data mismatch, by learning the overall non-linear Cartpole Balance task using a linear GP for model-based reinforcement learning. From classical control theory, it is well known that the task relevant part of the dynamics around the upright pole position can be described with a linearized model [6 ] . Since RL learns from trial and error and may fail in early episodes, the system may not remain in this approximately linear domain. We show in Figure 5 (top) that Forgetful RL converges using a linear kernel (left) by constantly removing detrimental nonlinear experiences (middle) for predictions in the stabilizing target region A \mathcal{A} A [31 ] , which retains all samples, does not solve the task. We visualize the behavior of Forgetful RL to delete nonlinear experiences in Figure 5 (bottom). The retained data points lie within the dynamics part relevant to stabilizing at the upward pole position. Forgetful RL automatically removes samples from the attractive regime of the undesired stable poles, compared with the dynamics phase diagram in the right-hand subplot.
Figure 5. (Top) Forgetful RL succeeds to learn Cartpole Balance with a linear GP model, while standard methods suffer from retained nonlinear observations. (Bottom) Visualization of removed and retained samples for Forgetful RL. The method keeps task-relevant data in the linear regime.
Conclusion
This work revisits the fundamental assumption on the irreducibility of aleatoric uncertainty in GP regression, from which the well known paradigm of incorporating all available data to improve the predictive uncertainty originates. For task-specific predictions, we demonstrate that this assumption breaks under model mismatch. To address this, we introduce Forgetting to Improve, a principled data-removal algorithm that explicitly minimizes predictive uncertainty in the task-specific target region by identifying and removing samples that are detrimental to these areas under model mismatch. We further extend this paradigm to sequential decision making, reformulating BO and RL as iterative transductive learning problems. Our improvements on regression, BO and RL tasks highlight data removal as a complementary and largely underexplored direction for improving uncertainty-aware learning.
Acknowledgement
We would like to thank Amanda Prorok, Jasmine Bayrooti, Massimiliano Tamborski and Yarden As for insightful discussions during this project. We thank the anonymous reviewers for their valuable comments and suggestions. This work was supported as a part of NCCR Automation, a National Centre of Competence in Research, funded by the Swiss National Science Foundation (grant number 51NF40_225155). This work was partially supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) founded by the Knut and Alice Wallenberg Foundation.
Epistemic and Aleatoric influence proofs
In this appendix we provide the detailed proofs for (i) the removal direction for leave-one-out in Section A.1, (ii) the derivation of the epistemic and (ii) the aleatoric influence in Sections A.2 and A.3.
LOO – Removal Direction
Proposition 5. Let k k k H k \mathcal{H}_k H k ϕ ( x ) = k ( x , ⋅ ) \phi(x) = k(x,\cdot) ϕ ( x ) = k ( x , ⋅ ) S = { ( x j , y j ) } j = 1 n S = \{(x_j,y_j)\}_{j=1}^{n} S = {( x j , y j ) } j = 1 n k S ( x ) : = [ k ( x , x 1 ) , … , k ( x , x n ) ] T k_S(x) := [k(x,x_1),\ldots,k(x,x_n)]^{\mathsf{T}} k S ( x ) := [ k ( x , x 1 ) , … , k ( x , x n ) ] T y : = [ y 1 , … , y n ] T y := [y_1,\ldots,y_n]^{\mathsf{T}} y := [ y 1 , … , y n ] T i i i h i ∈ [ 0 , 1 ] h_i \in[0,1] h i ∈ [ 0 , 1 ] i i i ϕ ( x i ) \phi(x_i) ϕ ( x i ) 1 − h i 1-h_i 1 − h i
k S ( x ; h i ) : = k S ( x ) − h i k ( x , x i ) e i , y ( h i ) : = y − h i y i e i , k_S(x;h_i) := k_S(x) - h_i k(x,x_i)e_i,\qquad y(h_i) := y - h_i y_i e_i, k S ( x ; h i ) := k S ( x ) − h i k ( x , x i ) e i , y ( h i ) := y − h i y i e i , where e i e_i e i i i i σ w 2 \sigma_w^2 σ w 2 h i = 1 h_i=1 h i = 1
μ S ( x ; 1 ) = μ S ∖ { x i , y i } ( x ) , σ S 2 ( x ; 1 ) = σ S ∖ { x i , y i } 2 ( x ) . \mu_S(x;1)=\mu_{S\setminus\{x_i,y_i\}}(x),\qquad\sigma_S^2(x;1)=\sigma_{S\setminus\{x_i,y_i\}}^2(x). μ S ( x ; 1 ) = μ S ∖ { x i , y i } ( x ) , σ S 2 ( x ; 1 ) = σ S ∖ { x i , y i } 2 ( x ) . Proof. Write the regularized kernel matrix as
A ( h i ) : = K ( h i ) + σ w 2 I , (7) A(h_i):=K(h_i)+\sigma_w^2 I, \tag*{(7)} A ( h i ) := K ( h i ) + σ w 2 I , (7) and the corresponding predictor in kernel form as
μ S ( x ; h i ) = k S ( x ; h i ) T A ( h i ) − 1 y ( h i ) , (8) \mu_S(x;h_i)=k_S(x;h_i)^{\mathsf{T}}A(h_i)^{-1}y(h_i), \tag*{(8)} μ S ( x ; h i ) = k S ( x ; h i ) T A ( h i ) − 1 y ( h i ) , (8) σ S 2 ( x ; h i ) = k ( x , x ) − k S ( x ; h i ) T A ( h i ) − 1 k S ( x ; h i ) + σ w 2 . (9) \sigma_S^2(x;h_i)=k(x,x)-k_S(x;h_i)^{\mathsf{T}}A(h_i)^{-1}k_S(x;h_i)+\sigma_w^2. \tag*{(9)} σ S 2 ( x ; h i ) = k ( x , x ) − k S ( x ; h i ) T A ( h i ) − 1 k S ( x ; h i ) + σ w 2 . (9) At h i = 1 h_i=1 h i = 1 i i i i i i K ( 1 ) K(1) K ( 1 ) i i i A ( 1 ) A(1) A ( 1 )
A ( 1 ) = [ K S ∖ { x i , y i } + σ w 2 I 0 0 T σ w 2 ] , A ( 1 ) − 1 = [ ( K S ∖ { x i , y i } + σ w 2 I ) − 1 0 0 T σ w − 2 ] , (10) A(1)=
\begin{bmatrix}
K_{S\setminus\{x_i,y_i\}}+\sigma_w^2I & 0\\
0^{\mathsf{T}} & \sigma_w^2
\end{bmatrix},
\qquad
A(1)^{-1}=
\begin{bmatrix}
\left(K_{S\setminus\{x_i,y_i\}}+\sigma_w^2I\right)^{-1} & 0\\
0^{\mathsf{T}} & \sigma_w^{-2}
\end{bmatrix}, \tag*{(10)} A ( 1 ) = [ K S ∖ { x i , y i } + σ w 2 I 0 T 0 σ w 2 ] , A ( 1 ) − 1 = [ ( K S ∖ { x i , y i } + σ w 2 I ) − 1 0 T 0 σ w − 2 ] , (10) k S ( x ; 1 ) = [ k S ∖ { x i , y i } ( x ) 0 ] , y ( 1 ) = [ y S ∖ { x i , y i } 0 ] . (11) k_S(x;1)=
\begin{bmatrix}
k_{S\setminus\{x_i,y_i\}}(x)\\
0
\end{bmatrix},
\qquad
y(1)=
\begin{bmatrix}
y_{S\setminus\{x_i,y_i\}}\\
0
\end{bmatrix}. \tag*{(11)} k S ( x ; 1 ) = [ k S ∖ { x i , y i } ( x ) 0 ] , y ( 1 ) = [ y S ∖ { x i , y i } 0 ] . (11) Substituting these expressions into the formulas above gives
μ S ( x ; 1 ) = k S ∖ { x i , y i } ( x ) T ( K S ∖ { x i , y i } + σ w 2 I ) − 1 y S ∖ { x i , y i } = μ S ∖ { x i , y i } ( x ) , (12) \mu_S(x;1)=k_{S\setminus\{x_i,y_i\}}(x)^{\mathsf{T}}\left(K_{S\setminus\{x_i,y_i\}}+\sigma_w^2I\right)^{-1}y_{S\setminus\{x_i,y_i\}}=\mu_{S\setminus\{x_i,y_i\}}(x), \tag*{(12)} μ S ( x ; 1 ) = k S ∖ { x i , y i } ( x ) T ( K S ∖ { x i , y i } + σ w 2 I ) − 1 y S ∖ { x i , y i } = μ S ∖ { x i , y i } ( x ) , (12) σ S 2 ( x ; 1 ) = k ( x , x ) − k S ∖ { x i , y i } ( x ) T ( K S ∖ { x i , y i } + σ w 2 I ) − 1 k S ∖ { x i , y i } ( x ) + σ w 2 = σ S ∖ { x i , y i } 2 ( x ) . (13) \sigma_S^2(x;1)=k(x,x)-k_{S\setminus\{x_i,y_i\}}(x)^{\mathsf{T}}\left(K_{S\setminus\{x_i,y_i\}}+\sigma_w^2I\right)^{-1}k_{S\setminus\{x_i,y_i\}}(x)+\sigma_w^2=\sigma_{S\setminus\{x_i,y_i\}}^2(x). \tag*{(13)} σ S 2 ( x ; 1 ) = k ( x , x ) − k S ∖ { x i , y i } ( x ) T ( K S ∖ { x i , y i } + σ w 2 I ) − 1 k S ∖ { x i , y i } ( x ) + σ w 2 = σ S ∖ { x i , y i } 2 ( x ) . (13) To complete the proof for the output space, we examine the weight vector v ( h i ) = A ( h i ) − 1 y ( h i ) v(h_i)=A(h_i)^{-1}y(h_i) v ( h i ) = A ( h i ) − 1 y ( h i ) h i = 1 h_i=1 h i = 1 y ( 1 ) = [ y 1 , … , 0 , … , y n ] T y(1)=[y_1,\ldots,0,\ldots,y_n]^{\mathsf{T}} y ( 1 ) = [ y 1 , … , 0 , … , y n ] T A ( 1 ) − 1 A(1)^{-1} A ( 1 ) − 1
v ( 1 ) = [ ( K S ∖ { x i , y i } + σ w 2 I ) − 1 0 0 T 1 σ w 2 ] [ y S ∖ { x i , y i } 0 ] = [ ( K S ∖ { x i , y i } + σ w 2 I ) − 1 y S ∖ { x i , y i } 0 ] (14) v(1)=
\begin{bmatrix}
\left(K_{S\setminus\{x_i,y_i\}}+\sigma_w^2I\right)^{-1} & 0\\
0^{\mathsf{T}} & \frac{1}{\sigma_w^2}
\end{bmatrix}
\begin{bmatrix}
y_{S\setminus\{x_i,y_i\}}\\
0
\end{bmatrix}
=
\begin{bmatrix}
\left(K_{S\setminus\{x_i,y_i\}}+\sigma_w^2I\right)^{-1}y_{S\setminus\{x_i,y_i\}}\\
0
\end{bmatrix} \tag*{(14)} v ( 1 ) = [ ( K S ∖ { x i , y i } + σ w 2 I ) − 1 0 T 0 σ w 2 1 ] [ y S ∖ { x i , y i } 0 ] = [ ( K S ∖ { x i , y i } + σ w 2 I ) − 1 y S ∖ { x i , y i } 0 ] (14) Let v S ∖ { x i , y i } v_{S\setminus\{x_i,y_i\}} v S ∖ { x i , y i } S ∖ { x i , y i } S\setminus\{x_i,y_i\} S ∖ { x i , y i }
v ( 1 ) = { ( v S ∖ { x i , y i } ) j j ≠ i 0 j = i (15) v(1)=
\begin{cases}
(v_{S\setminus\{x_i,y_i\}})_j & j\ne i\\
0 & j=i
\end{cases} \tag*{(15)} v ( 1 ) = { ( v S ∖ { x i , y i } ) j 0 j = i j = i (15) The predictive mean at x x x μ S ( x , 1 ) = k ( x , S , 1 ) T v ( 1 ) \mu_S(x,1)=k(x,S,1)^{\mathsf{T}}v(1) μ S ( x , 1 ) = k ( x , S , 1 ) T v ( 1 ) i i i
μ S ( x , 1 ) = ∑ j ≠ i k ( x , x j ) v j ( 1 ) + k ( x , x i ) ⋅ 0 = ∑ j ≠ i k ( x , x j ) ( v S ∖ { x i , y i } ) j (16) \mu_S(x,1)=\sum_{j\ne i}k(x,x_j)v_j(1)+k(x,x_i)\cdot0=\sum_{j\ne i}k(x,x_j)(v_{S\setminus\{x_i,y_i\}})_j \tag*{(16)} μ S ( x , 1 ) = j = i ∑ k ( x , x j ) v j ( 1 ) + k ( x , x i ) ⋅ 0 = j = i ∑ k ( x , x j ) ( v S ∖ { x i , y i } ) j (16) This is identically the LOO predictive mean μ S ∖ { x i , y i } ( x ) \mu_{S\setminus\{x_i,y_i\}}(x) μ S ∖ { x i , y i } ( x ) h i = 1 h_i=1 h i = 1 σ w 2 \sigma_w^2 σ w 2
Epistemic Influence
Proposition 1. Suppose we have a single test point A = { x } A=\{x\} A = { x } μ S ( x ) \mu_{S}(x) μ S ( x ) σ S 2 ( x ) \sigma_{S}^{2}(x) σ S 2 ( x ) S = { x i , y i } i = 1 n S=\{x_{i},y_{i}\}_{i=1}^{n} S = { x i , y i } i = 1 n u i ( x ) u_{i}(x) u i ( x ) x i ∈ S x_{i}\in S x i ∈ S σ S 2 ( x ) \sigma_{S}^{2}(x) σ S 2 ( x ) h i h_{i} h i x i ∈ S x_{i}\in S x i ∈ S σ w 2 ( S ) \sigma_{w}^{2}(S) σ w 2 ( S )
u i ( x ) = 2 k x , x i ( A − 1 k S , x ) i − 2 ( A − 1 k S , x ) i ( k x i , S A − 1 k S , x ) , u_{i}(x)=2k_{x,x_{i}}(A^{-1}k_{S,x})_{i}-2(A^{-1}k_{S,x})_{i}(k_{x_{i},S}A^{-1}k_{S,x}), u i ( x ) = 2 k x , x i ( A − 1 k S , x ) i − 2 ( A − 1 k S , x ) i ( k x i , S A − 1 k S , x ) , where k x , S = k ( x , S ) k_{x,S}=k(x,S) k x , S = k ( x , S ) A = K + σ w 2 ( S ) I A=K+\sigma_{w}^{2}(S)I A = K + σ w 2 ( S ) I K = k ( S , S ) K=k(S,S) K = k ( S , S )
Proof. Let the predictive uncertainty of the GP for a set of samples S S S (2) , and we consider the aleatoric noise estimate σ w 2 ( S ) \sigma_{w}^{2}(S) σ w 2 ( S )
σ S 2 ( x ) = k ( x , x ) − k x , S ( K + σ w 2 ( S ) I ) − 1 k S , x + σ w 2 ( S ) I (17) \sigma_{S}^{2}(x)=k(x,x)-k_{x,S}(K+\sigma_{w}^{2}(S)I)^{-1}k_{S,x}+\sigma_{w}^{2}(S)I \tag*{(17)} σ S 2 ( x ) = k ( x , x ) − k x , S ( K + σ w 2 ( S ) I ) − 1 k S , x + σ w 2 ( S ) I (17) Furthermore, we consider the RKHS and output removal directions in h i h_{i} h i
σ S 2 ( x ) = k ( x , x ) − k ( x , S , h i ) ( K ( h i ) + σ w 2 ( S ) I ) − 1 k ( S , x , h i ) + σ w 2 ( S ) I , (18) \sigma_{S}^{2}(x)=k(x,x)-k(x,S,h_{i})(K(h_{i})+\sigma_{w}^{2}(S)I)^{-1}k(S,x,h_{i})+\sigma_{w}^{2}(S)I, \tag*{(18)} σ S 2 ( x ) = k ( x , x ) − k ( x , S , h i ) ( K ( h i ) + σ w 2 ( S ) I ) − 1 k ( S , x , h i ) + σ w 2 ( S ) I , (18) where we define the Gram matrix under the removal is defined using the as
K ( h i ) = k ( S , S , h i ) = [ ( 1 − h j ) K j , k ( 1 − h k ) ] j , k = { ( 1 − h i ) k ( x j , x k ) if j = i ∨ k = i , ( 1 − h i ) 2 k ( x j , x k ) if i = j = k , k ( x j , x k ) otherwise. (19) K(h_{i})=k(S,S,h_{i})=[(1-h_{j})K_{j,k}(1-h_{k})]_{j,k}=
\begin{cases}
(1-h_{i})k(x_{j},x_{k}) & \text{if } j=i\lor k=i,\\
(1-h_{i})^{2}k(x_{j},x_{k}) & \text{if } i=j=k,\\
k(x_{j},x_{k}) & \text{otherwise.}
\end{cases} \tag*{(19)} K ( h i ) = k ( S , S , h i ) = [( 1 − h j ) K j , k ( 1 − h k ) ] j , k = ⎩ ⎨ ⎧ ( 1 − h i ) k ( x j , x k ) ( 1 − h i ) 2 k ( x j , x k ) k ( x j , x k ) if j = i ∨ k = i , if i = j = k , otherwise. (19) Hence, after deriving the continuous surrogate, we differentiate w.r.t. h i h_{i} h i σ w 2 ( S ) \sigma_{w}^{2}(S) σ w 2 ( S )
∂ σ S 2 ( x ) ∂ h i = ∂ ∂ h i k ( x , x ) − ∂ ∂ h i k ( x , S , h i ) ( K ( h i ) + σ w 2 ( S ) I ) − 1 k ( S , x , h i ) + ∂ ∂ h i σ w 2 ( S ) I (20) \frac{\partial\sigma_{S}^{2}(x)}{\partial h_{i}}=\frac{\partial}{\partial h_{i}}k(x,x)-\frac{\partial}{\partial h_{i}}k(x,S,h_{i})(K(h_{i})+\sigma_{w}^{2}(S)I)^{-1}k(S,x,h_{i})+\frac{\partial}{\partial h_{i}}\sigma_{w}^{2}(S)I \tag*{(20)} ∂ h i ∂ σ S 2 ( x ) = ∂ h i ∂ k ( x , x ) − ∂ h i ∂ k ( x , S , h i ) ( K ( h i ) + σ w 2 ( S ) I ) − 1 k ( S , x , h i ) + ∂ h i ∂ σ w 2 ( S ) I (20) = − ∂ ∂ h i k ( x , S , h i ) ( K ( h i ) + σ w 2 ( S ) I ) − 1 k ( S , x , h i ) (21) =-\frac{\partial}{\partial h_{i}}k(x,S,h_{i})(K(h_{i})+\sigma_{w}^{2}(S)I)^{-1}k(S,x,h_{i}) \tag*{(21)} = − ∂ h i ∂ k ( x , S , h i ) ( K ( h i ) + σ w 2 ( S ) I ) − 1 k ( S , x , h i ) (21) = − ∂ k ( x , S , h i ) ∂ h i ( K ( h i ) + σ w 2 ( S ) I ) − 1 k ( S , x , h i ) (22) =-\frac{\partial k(x,S,h_{i})}{\partial h_{i}}(K(h_{i})+\sigma_{w}^{2}(S)I)^{-1}k(S,x,h_{i}) \tag*{(22)} = − ∂ h i ∂ k ( x , S , h i ) ( K ( h i ) + σ w 2 ( S ) I ) − 1 k ( S , x , h i ) (22) − k ( x , S , h i ) ∂ ( K ( h i ) + σ w 2 ( S ) I ) − 1 ∂ h i k ( S , x , h i ) − k ( x , S , h i ) ( K ( h i ) + σ w 2 ( S ) I ) − 1 ∂ k ( S , x , h i ) ∂ h i = − 2 ∂ k ( x , S , h i ) ∂ h i ( K ( h i ) + σ w 2 ( S ) I ) − 1 k ( S , x , h i ) + k ( x , S , h i ) A ( h i ) − 1 ∂ K ( h i ) ∂ h i A ( h i ) − 1 k ( S , x , h i ) (23) \begin{aligned}
-k(x,S,h_{i})\frac{\partial(K(h_{i})+\sigma_{w}^{2}(S)I)^{-1}}{\partial h_{i}}k(S,x,h_{i})
-k(x,S,h_{i})(K(h_{i})+\sigma_{w}^{2}(S)I)^{-1}\frac{\partial k(S,x,h_{i})}{\partial h_{i}} \\
&=-2\frac{\partial k(x,S,h_{i})}{\partial h_{i}}(K(h_{i})+\sigma_{w}^{2}(S)I)^{-1}k(S,x,h_{i}) \\
&+k(x,S,h_{i})A(h_{i})^{-1}\frac{\partial K(h_{i})}{\partial h_{i}}A(h_{i})^{-1}k(S,x,h_{i}) \tag*{(23)}
\end{aligned} − k ( x , S , h i ) ∂ h i ∂ ( K ( h i ) + σ w 2 ( S ) I ) − 1 k ( S , x , h i ) − k ( x , S , h i ) ( K ( h i ) + σ w 2 ( S ) I ) − 1 ∂ h i ∂ k ( S , x , h i ) = − 2 ∂ h i ∂ k ( x , S , h i ) ( K ( h i ) + σ w 2 ( S ) I ) − 1 k ( S , x , h i ) + k ( x , S , h i ) A ( h i ) − 1 ∂ h i ∂ K ( h i ) A ( h i ) − 1 k ( S , x , h i ) (23) = 2 k ( x , x i ) e i T A ( h i ) − 1 k ( S , x , h i ) + k ( x , S , h i ) A ( h i ) − 1 ( e i k ( x i , S ) + k ( S , x i ) e i T ) A ( h i ) − 1 k ( S , x , h i ) . (24) \begin{aligned}
=2k(x,x_{i})e_{i}^{\mathsf{T}}A(h_{i})^{-1}k(S,x,h_{i}) \\
&+k(x,S,h_{i})A(h_{i})^{-1}(e_{i}k(x_{i},S)+k(S,x_{i})e_{i}^{\mathsf{T}})A(h_{i})^{-1}k(S,x,h_{i}). \tag*{(24)}
\end{aligned} = 2 k ( x , x i ) e i T A ( h i ) − 1 k ( S , x , h i ) + k ( x , S , h i ) A ( h i ) − 1 ( e i k ( x i , S ) + k ( S , x i ) e i T ) A ( h i ) − 1 k ( S , x , h i ) . (24) We can further simplify this expression by differentiating the Gram matrix K ( h i ) K(h_{i}) K ( h i ) (19) and introducing the short notation α = A ( h i ) − 1 k ( S , x , h i ) \alpha=A(h_{i})^{-1}k(S,x,h_{i}) α = A ( h i ) − 1 k ( S , x , h i )
∂ σ S 2 ( x ) ∂ h i = 2 k ( x , x i ) α i + α T [ − e i k ( x i , S , h i ) − k ( S , x i , h i ) e i T ] α (25) \frac{\partial\sigma_{S}^{2}(x)}{\partial h_{i}}=2k(x,x_{i})\alpha_{i}+\alpha^{\mathsf{T}}\left[-e_{i}k(x_{i},S,h_{i})-k(S,x_{i},h_{i})e_{i}^{\mathsf{T}}\right]\alpha \tag*{(25)} ∂ h i ∂ σ S 2 ( x ) = 2 k ( x , x i ) α i + α T [ − e i k ( x i , S , h i ) − k ( S , x i , h i ) e i T ] α (25) = 2 k ( x , x i ) α i − [ ( α T e i ) ( k ( x i , S , h ) α ) + ( α T k ( S , x i , h ) ) ( e i T α ) ] (26) =2k(x,x_{i})\alpha_{i}-\left[(\alpha^{\mathsf{T}}e_{i})(k(x_{i},S,h)\alpha)+(\alpha^{\mathsf{T}}k(S,x_{i},h))(e_{i}^{\mathsf{T}}\alpha)\right] \tag*{(26)} = 2 k ( x , x i ) α i − [ ( α T e i ) ( k ( x i , S , h ) α ) + ( α T k ( S , x i , h )) ( e i T α ) ] (26) = 2 k ( x , x i ) α i − 2 α i ( k ( x i , S , h ) α ) (27) =2k(x,x_{i})\alpha_{i}-2\alpha_{i}(k(x_{i},S,h)\alpha) \tag*{(27)} = 2 k ( x , x i ) α i − 2 α i ( k ( x i , S , h ) α ) (27) Since we evaluate the partial derivative at h i = 0 h_{i}=0 h i = 0
∂ σ S 2 ( x ) ∂ h i ∣ h i = 0 = 2 k ( x , x i ) α i − 2 α i ( k ( x i , S ) α ) (28) \left.\frac{\partial\sigma_{S}^{2}(x)}{\partial h_{i}}\right|_{h_{i}=0}=2k(x,x_{i})\alpha_{i}-2\alpha_{i}(k(x_{i},S)\alpha) \tag*{(28)} ∂ h i ∂ σ S 2 ( x ) h i = 0 = 2 k ( x , x i ) α i − 2 α i ( k ( x i , S ) α ) (28) = 2 k ( x , x i ) ( A − 1 k ( S , x ) ) i − 2 ( A − 1 k ( S , x ) ) i ( k ( x i , S ) A − 1 k ( S , x ) ) , (29) =2k(x,x_{i})(A^{-1}k(S,x))_{i}-2(A^{-1}k(S,x))_{i}(k(x_{i},S)A^{-1}k(S,x)), \tag*{(29)} = 2 k ( x , x i ) ( A − 1 k ( S , x ) ) i − 2 ( A − 1 k ( S , x ) ) i ( k ( x i , S ) A − 1 k ( S , x )) , (29) which completes the proof, when writing the kernel vectors in index notation.
Proposition 2. Suppose the uncertainty difference at A = { x } \mathcal{A}=\{x\} A = { x } i i i
Δ i ( x ) = σ S ∖ { x i , y i } 2 ( x ) − σ S 2 ( x ) = ( A − 1 k S , x ) i 2 A i , i − 1 . \Delta_i(x)=\sigma^2_{S\setminus\{x_i,y_i\}}(x)-\sigma^2_S(x)=\frac{(A^{-1}k_{S,x})_i^2}{A^{-1}_{i,i}}. Δ i ( x ) = σ S ∖ { x i , y i } 2 ( x ) − σ S 2 ( x ) = A i , i − 1 ( A − 1 k S , x ) i 2 . Then, our uncertainty measure u u u k x , S k_{x,S} k x , S k x , x i k_{x,x_i} k x , x i u u u
k x , x i ∂ Δ i ∂ k x , x i = 2 k x , x i ( A − 1 k S , x ) i − 2 ( A − 1 k S , x ) i ( k x i , S A − 1 k S , x ) = u i ( x ) . k_{x,x_i}\frac{\partial\Delta_i}{\partial k_{x,x_i}}=2k_{x,x_i}(A^{-1}k_{S,x})_i-2(A^{-1}k_{S,x})_i(k_{x_i,S}A^{-1}k_{S,x})=u_i(x). k x , x i ∂ k x , x i ∂ Δ i = 2 k x , x i ( A − 1 k S , x ) i − 2 ( A − 1 k S , x ) i ( k x i , S A − 1 k S , x ) = u i ( x ) . Proof. Let S = { x 1 , … , x n } S=\{x_1,\ldots,x_n\} S = { x 1 , … , x n } i i i x t x_t x t
A = K ( S , S ) + σ w 2 ( S ) I , k : = k S , x t = k ( S , x t ) ∈ R n , (30) A=K(S,S)+\sigma^2_w(S)I,\qquad k:=k_{S,x_t}=k(S,x_t)\in\mathbb{R}^n, \tag*{(30)} A = K ( S , S ) + σ w 2 ( S ) I , k := k S , x t = k ( S , x t ) ∈ R n , (30) and partition A A A k k k i i i
A = [ A i , i A i , − i A − i , i A − i , − i ] , k = [ k i k − i ] . (31) A=\begin{bmatrix}A_{i,i}&A_{i,-i}\\A_{-i,i}&A_{-i,-i}\end{bmatrix},\qquad k=\begin{bmatrix}k_i\\k_{-i}\end{bmatrix}. \tag*{(31)} A = [ A i , i A − i , i A i , − i A − i , − i ] , k = [ k i k − i ] . (31) Define the Schur complement [54 ]
S i , i : = A i , i − A i , − i A − i , − i − 1 A − i , i . (32) S_{i,i}:=A_{i,i}-A_{i,-i}A^{-1}_{-i,-i}A_{-i,i}. \tag*{(32)} S i , i := A i , i − A i , − i A − i , − i − 1 A − i , i . (32) Epistemic uncertainty difference for leave one-out: Using the block inverse identities in [24 Prop. 2] , the i i ii ii A − 1 A^{-1} A − 1 A i , i − 1 = S i , i − 1 A^{-1}_{i,i}=S^{-1}_{i,i} A i , i − 1 = S i , i − 1
A i , − i − 1 = − S i , i − 1 A i , − i A − i , − i − 1 , A − i , i − 1 = − A − i , − i − 1 A − i , i S i , i − 1 , (33) A^{-1}_{i,-i}=-S^{-1}_{i,i}A_{i,-i}A^{-1}_{-i,-i},\qquad A^{-1}_{-i,i}=-A^{-1}_{-i,-i}A_{-i,i}S^{-1}_{i,i}, \tag*{(33)} A i , − i − 1 = − S i , i − 1 A i , − i A − i , − i − 1 , A − i , i − 1 = − A − i , − i − 1 A − i , i S i , i − 1 , (33) A − i , − i − 1 = A − i , − i − 1 + A − i , − i − 1 A − i , i S i , i − 1 A i , − i A − i , − i − 1 (34) A^{-1}_{-i,-i}=A^{-1}_{-i,-i}+A^{-1}_{-i,-i}A_{-i,i}S^{-1}_{i,i}A_{i,-i}A^{-1}_{-i,-i} \tag*{(34)} A − i , − i − 1 = A − i , − i − 1 + A − i , − i − 1 A − i , i S i , i − 1 A i , − i A − i , − i − 1 (34) The GP predictive variance with the full set S S S
σ S 2 ( x t ) = k ( x t , x t ) − k ⊤ A − 1 k , (35) \sigma^2_S(x_t)=k(x_t,x_t)-k^\top A^{-1}k, \tag*{(35)} σ S 2 ( x t ) = k ( x t , x t ) − k ⊤ A − 1 k , (35) and the variance when training on S ∖ { x i , y i } S\setminus\{x_i,y_i\} S ∖ { x i , y i } i i i
σ S ∖ { x i , y i } 2 ( x t ) = k ( x t , x t ) − k − i ⊤ A − i , − i − 1 k − i . (36) \sigma^2_{S\setminus\{x_i,y_i\}}(x_t)=k(x_t,x_t)-k^\top_{-i}A^{-1}_{-i,-i}k_{-i}. \tag*{(36)} σ S ∖ { x i , y i } 2 ( x t ) = k ( x t , x t ) − k − i ⊤ A − i , − i − 1 k − i . (36) Therefore the variance drop due to sample i i i
Δ i ( x t ) = σ S ∖ { x i , y i } 2 ( x t ) − σ S 2 ( x t ) = k ⊤ A − 1 k − k − i ⊤ A − i , − i − 1 k − i . (37) \Delta_i(x_t)=\sigma^2_{S\setminus\{x_i,y_i\}}(x_t)-\sigma^2_S(x_t)=k^\top A^{-1}k-k^\top_{-i}A^{-1}_{-i,-i}k_{-i}. \tag*{(37)} Δ i ( x t ) = σ S ∖ { x i , y i } 2 ( x t ) − σ S 2 ( x t ) = k ⊤ A − 1 k − k − i ⊤ A − i , − i − 1 k − i . (37) Expanding k ⊤ A − 1 k k^\top A^{-1}k k ⊤ A − 1 k
k ⊤ A − 1 k = [ k i k − i ⊤ ] [ S i , i − 1 A i , − i − 1 A − i , i − 1 A − i , − i − 1 ] [ k i k − i ] (38) k^\top A^{-1}k=
\begin{bmatrix}k_i&k^\top_{-i}\end{bmatrix}
\begin{bmatrix}S^{-1}_{i,i}&A^{-1}_{i,-i}\\A^{-1}_{-i,i}&A^{-1}_{-i,-i}\end{bmatrix}
\begin{bmatrix}k_i\\k_{-i}\end{bmatrix} \tag*{(38)} k ⊤ A − 1 k = [ k i k − i ⊤ ] [ S i , i − 1 A − i , i − 1 A i , − i − 1 A − i , − i − 1 ] [ k i k − i ] (38) = S i , i − 1 k i 2 + 2 k i A i , − i − 1 k − i + k − i ⊤ A − i , − i − 1 k − i (39) =S^{-1}_{i,i}k_i^2+2k_iA^{-1}_{i,-i}k_{-i}+k^\top_{-i}A^{-1}_{-i,-i}k_{-i} \tag*{(39)} = S i , i − 1 k i 2 + 2 k i A i , − i − 1 k − i + k − i ⊤ A − i , − i − 1 k − i (39) = S i , i − 1 k i 2 + 2 k i ( − S i , i − 1 A i , − i A − i , − i − 1 ) k − i (40) =S^{-1}_{i,i}k_i^2+2k_i(-S^{-1}_{i,i}A_{i,-i}A^{-1}_{-i,-i})k_{-i} \tag*{(40)} = S i , i − 1 k i 2 + 2 k i ( − S i , i − 1 A i , − i A − i , − i − 1 ) k − i (40) + k − i ⊤ ( A − i , − i − 1 + A − i , − i − 1 A − i , i S i , i − 1 A i , − i A − i , − i − 1 ) k − i = S i , i − 1 k i 2 − 2 k i S i , i − 1 A i , − i A − i , − i − 1 k − i (41) \begin{aligned}
\qquad+k^\top_{-i}(A^{-1}_{-i,-i}+A^{-1}_{-i,-i}A_{-i,i}S^{-1}_{i,i}A_{i,-i}A^{-1}_{-i,-i})k_{-i} \\
&=S^{-1}_{i,i}k_i^2-2k_iS^{-1}_{i,i}A_{i,-i}A^{-1}_{-i,-i}k_{-i} \tag*{(41)}
\end{aligned} + k − i ⊤ ( A − i , − i − 1 + A − i , − i − 1 A − i , i S i , i − 1 A i , − i A − i , − i − 1 ) k − i = S i , i − 1 k i 2 − 2 k i S i , i − 1 A i , − i A − i , − i − 1 k − i (41) + k − i ⊤ A − i , − i − 1 k − i + k − i ⊤ A − i , − i − 1 A − i , i S i , i − 1 A i , − i A − i , − i − 1 k − i = k − i ⊤ A − i , − i − 1 k − i + S i , i − 1 ( k i 2 − 2 k i A i , − i A − i , − i − 1 k − i (42) \begin{aligned}
\qquad+k^\top_{-i}A^{-1}_{-i,-i}k_{-i}+k^\top_{-i}A^{-1}_{-i,-i}A_{-i,i}S^{-1}_{i,i}A_{i,-i}A^{-1}_{-i,-i}k_{-i} \\
&=k^\top_{-i}A^{-1}_{-i,-i}k_{-i}+S^{-1}_{i,i}(k_i^2-2k_iA_{i,-i}A^{-1}_{-i,-i}k_{-i} \tag*{(42)}
\end{aligned} + k − i ⊤ A − i , − i − 1 k − i + k − i ⊤ A − i , − i − 1 A − i , i S i , i − 1 A i , − i A − i , − i − 1 k − i = k − i ⊤ A − i , − i − 1 k − i + S i , i − 1 ( k i 2 − 2 k i A i , − i A − i , − i − 1 k − i (42) + ( A i , − i A − i , − i − 1 k − i ) ⊤ ( A i , − i A − i , − i − 1 k − i ) ) = k − i ⊤ A − i , − i − 1 k − i + S i , i − 1 ( k i − A i , − i A − i , − i − 1 k − i ) 2 . (43) \begin{aligned}
\qquad+(A_{i,-i}A^{-1}_{-i,-i}k_{-i})^\top(A_{i,-i}A^{-1}_{-i,-i}k_{-i})) \\
&=k^\top_{-i}A^{-1}_{-i,-i}k_{-i}+S^{-1}_{i,i}(k_i-A_{i,-i}A^{-1}_{-i,-i}k_{-i})^2. \tag*{(43)}
\end{aligned} + ( A i , − i A − i , − i − 1 k − i ) ⊤ ( A i , − i A − i , − i − 1 k − i )) = k − i ⊤ A − i , − i − 1 k − i + S i , i − 1 ( k i − A i , − i A − i , − i − 1 k − i ) 2 . (43) Further, the i i i A − 1 k A^{-1}k A − 1 k
( A − 1 k ) i = A i , i − 1 k i + A i , − i − 1 k − i = S i , i − 1 ( k i − A i , − i A − i , − i − 1 k − i ) . (44) (A^{-1}k)_i=A^{-1}_{i,i}k_i+A^{-1}_{i,-i}k_{-i}=S^{-1}_{i,i}(k_i-A_{i,-i}A^{-1}_{-i,-i}k_{-i}). \tag*{(44)} ( A − 1 k ) i = A i , i − 1 k i + A i , − i − 1 k − i = S i , i − 1 ( k i − A i , − i A − i , − i − 1 k − i ) . (44) Finally, we express the variance drop using Equation (43) :
Δ i ( x t ) = S i , i − 1 ( k i − A i , − i A − i , − i − 1 k − i ) 2 = S i , i − 1 ( S i , i ( A − 1 k ) i ) 2 = ( A − 1 k S , x t ) i 2 A i , i − 1 . (45) \Delta_i(x_t)=S^{-1}_{i,i}(k_i-A_{i,-i}A^{-1}_{-i,-i}k_{-i})^2=S^{-1}_{i,i}(S_{i,i}(A^{-1}k)_i)^2=\frac{(A^{-1}k_{S,x_t})_i^2}{A^{-1}_{i,i}}. \tag*{(45)} Δ i ( x t ) = S i , i − 1 ( k i − A i , − i A − i , − i − 1 k − i ) 2 = S i , i − 1 ( S i , i ( A − 1 k ) i ) 2 = A i , i − 1 ( A − 1 k S , x t ) i 2 . (45) We obtain step (i) by substituting Equation (44) and (ii) from S i , i − 1 = A i , i − 1 S^{-1}_{i,i}=A^{-1}_{i,i} S i , i − 1 = A i , i − 1
Directional-derivative: Let us abbreviate α = A − 1 k \alpha=A^{-1}k α = A − 1 k v = A i i − 1 = e i T A − 1 e i v=A^{-1}_{ii}=e_i^{\mathsf{T}}A^{-1}e_i v = A ii − 1 = e i T A − 1 e i Δ i = α i 2 / v \Delta_i=\alpha_i^2/v Δ i = α i 2 / v i i i
∂ k i Δ i = 2 α i v ∂ k i α i − α i 2 v 2 ∂ k i v . (46) \partial_{k_i}\Delta_i=\frac{2\alpha_i}{v}\partial_{k_i}\alpha_i-\frac{\alpha_i^2}{v^2}\partial_{k_i}v. \tag*{(46)} ∂ k i Δ i = v 2 α i ∂ k i α i − v 2 α i 2 ∂ k i v . (46) Using the identity ∂ k i ( A − 1 ) = − A − 1 ( ∂ k i A ) A − 1 \partial_{k_i}(A^{-1})=-A^{-1}(\partial_{k_i}A)A^{-1} ∂ k i ( A − 1 ) = − A − 1 ( ∂ k i A ) A − 1 α i = e i T A − 1 k \alpha_i=e_i^{\mathsf{T}}A^{-1}k α i = e i T A − 1 k v v v
∂ k i α i = e i T ( − A − 1 ( ∂ k i A ) A − 1 k + A − 1 ∂ k i k ) = − e i T A − 1 ( ∂ k i A ) α + v ∂ k i k . (47) \partial_{k_i}\alpha_i=e_i^{\mathsf{T}}\left(-A^{-1}(\partial_{k_i}A)A^{-1}k+A^{-1}\partial_{k_i}k\right)=-e_i^{\mathsf{T}}A^{-1}(\partial_{k_i}A)\alpha+v\partial_{k_i}k. \tag*{(47)} ∂ k i α i = e i T ( − A − 1 ( ∂ k i A ) A − 1 k + A − 1 ∂ k i k ) = − e i T A − 1 ( ∂ k i A ) α + v ∂ k i k . (47) ∂ k i v = e i T ( − A − 1 ( ∂ k i A ) A − 1 ) e i = − v e i T ( ∂ k i A ) A : , i − 1 − ( A : , i − 1 ∂ k i A ) e i v . (48) \partial_{k_i}v=e_i^{\mathsf{T}}\left(-A^{-1}(\partial_{k_i}A)A^{-1}\right)e_i=-ve_i^{\mathsf{T}}(\partial_{k_i}A)A^{-1}_{:,i}-(A^{-1}_{:,i}\partial_{k_i}A)e_iv. \tag*{(48)} ∂ k i v = e i T ( − A − 1 ( ∂ k i A ) A − 1 ) e i = − v e i T ( ∂ k i A ) A : , i − 1 − ( A : , i − 1 ∂ k i A ) e i v . (48) For a directional change along the i i i k i ∂ k i k = e i k i k_i\partial_{k_i}k=e_ik_i k i ∂ k i k = e i k i k i ∂ k i A = e i K i , S + K S , i e i T k_i\partial_{k_i}A=e_iK_{i,S}+K_{S,i}e_i^{\mathsf{T}} k i ∂ k i A = e i K i , S + K S , i e i T
∂ k i α i = − ( v ( K i , S α ) + ( A i , S − 1 K S , i ) α i ) + v k i , (49) \partial_{k_i}\alpha_i=-\left(v(K_{i,S}\alpha)+(A^{-1}_{i,S}K_{S,i})\alpha_i\right)+vk_i, \tag*{(49)} ∂ k i α i = − ( v ( K i , S α ) + ( A i , S − 1 K S , i ) α i ) + v k i , (49) ∂ k i v = − ( v ( K i , S A : , i − 1 ) + ( A i , S − 1 K S , i ) v ) = − 2 v ( K i , S A : , i − 1 ) . (50) \partial_{k_i}v=-\left(v(K_{i,S}A^{-1}_{:,i})+(A^{-1}_{i,S}K_{S,i})v\right)=-2v(K_{i,S}A^{-1}_{:,i}). \tag*{(50)} ∂ k i v = − ( v ( K i , S A : , i − 1 ) + ( A i , S − 1 K S , i ) v ) = − 2 v ( K i , S A : , i − 1 ) . (50) Now, substitute ∂ k i α i \partial_{k_i}\alpha_i ∂ k i α i ∂ k i v \partial_{k_i}v ∂ k i v d Δ i d\Delta_i d Δ i
∂ k i Δ i = 2 α i v ( − v ( K i , S α ) − α i ( K i , S A : , i − 1 ) + v k i ) − α i 2 v 2 ( − 2 v ( K i , S A : , i − 1 ) ) (51) \partial_{k_i}\Delta_i=\frac{2\alpha_i}{v}\left(-v(K_{i,S}\alpha)-\alpha_i(K_{i,S}A^{-1}_{:,i})+vk_i\right)-\frac{\alpha_i^2}{v^2}\left(-2v(K_{i,S}A^{-1}_{:,i})\right) \tag*{(51)} ∂ k i Δ i = v 2 α i ( − v ( K i , S α ) − α i ( K i , S A : , i − 1 ) + v k i ) − v 2 α i 2 ( − 2 v ( K i , S A : , i − 1 ) ) (51) = − 2 α i ( K i , S α ) − 2 α i 2 v ( K i , S A : , i − 1 ) + 2 α i k i + 2 α i 2 v ( K i , S A : , i − 1 ) (52) =-2\alpha_i(K_{i,S}\alpha)-\frac{2\alpha_i^2}{v}(K_{i,S}A^{-1}_{:,i})+2\alpha_ik_i+\frac{2\alpha_i^2}{v}(K_{i,S}A^{-1}_{:,i}) \tag*{(52)} = − 2 α i ( K i , S α ) − v 2 α i 2 ( K i , S A : , i − 1 ) + 2 α i k i + v 2 α i 2 ( K i , S A : , i − 1 ) (52) = 2 α i k i − 2 α i ( K i , S α ) . (53) =2\alpha_ik_i-2\alpha_i(K_{i,S}\alpha). \tag*{(53)} = 2 α i k i − 2 α i ( K i , S α ) . (53) Hence, we recover the epistemic influence u i ( x ) u_i(x) u i ( x )
u i ( x ) = 2 k x , x i ( A − 1 k ) i − 2 ( A − 1 k ) i ( K i , S A − 1 k ) . (54) u_i(x)=2k_{x,x_i}(A^{-1}k)_i-2(A^{-1}k)_i(K_{i,S}A^{-1}k). \tag*{(54)} u i ( x ) = 2 k x , x i ( A − 1 k ) i − 2 ( A − 1 k ) i ( K i , S A − 1 k ) . (54) Aleatoric Influence
Proposition 3. Let A ( σ w 2 ( S ) ) = K ( S , S ) + σ w 2 ( S ) I A(\sigma_w^2(S))=K(S,S)+\sigma_w^2(S)I A ( σ w 2 ( S )) = K ( S , S ) + σ w 2 ( S ) I σ w 2 ( S ) \sigma_w^2(S) σ w 2 ( S ) (1) ∂ ∂ σ w 2 L ( σ w 2 , S , a , b ) = D ( σ w 2 , S , a , b ) = 0 \frac{\partial}{\partial\sigma_w^2}\mathcal{L}(\sigma_w^2,S,a,b)=D(\sigma_w^2,S,a,b)=0 ∂ σ w 2 ∂ L ( σ w 2 , S , a , b ) = D ( σ w 2 , S , a , b ) = 0 S S S σ w 2 ( S ) \sigma_w^2(S) σ w 2 ( S ) h i h_i h i ∂ σ w 2 ∂ h i = − ∂ ∂ h i D ( σ w 2 , S , a , b ) / ∂ ∂ σ w 2 D ( σ w 2 , S , a , b ) \frac{\partial\sigma_w^2}{\partial h_i}=-\frac{\partial}{\partial h_i}D(\sigma_w^2,S,a,b)\big/\frac{\partial}{\partial\sigma_w^2}D(\sigma_w^2,S,a,b) ∂ h i ∂ σ w 2 = − ∂ h i ∂ D ( σ w 2 , S , a , b ) / ∂ σ w 2 ∂ D ( σ w 2 , S , a , b )
∂ σ w 2 ( S ) ∂ h i = − ( A − 1 y ) i ( k x i , S ( A − 2 y ) ) − ( A − 2 y ) i ( k x i , S ( A − 1 y ) ) + k x i , S ( A − 2 ) : , i + y i ( A − 2 y ) i − y T A − 3 y + 1 2 tr ( A − 2 ) − a − 1 ( σ w 2 ) 2 . \frac{\partial\sigma_w^2(S)}{\partial h_i}=\frac{-(A^{-1}y)_i(k_{x_i,S}(A^{-2}y))-(A^{-2}y)_i(k_{x_i,S}(A^{-1}y))+k_{x_i,S}(A^{-2})_{:,i}+y_i(A^{-2}y)_i}{-y^{\mathsf{T}}A^{-3}y+\frac{1}{2}\operatorname{tr}(A^{-2})-\frac{a-1}{(\sigma_w^2)^2}}. ∂ h i ∂ σ w 2 ( S ) = − y T A − 3 y + 2 1 tr ( A − 2 ) − ( σ w 2 ) 2 a − 1 − ( A − 1 y ) i ( k x i , S ( A − 2 y )) − ( A − 2 y ) i ( k x i , S ( A − 1 y )) + k x i , S ( A − 2 ) : , i + y i ( A − 2 y ) i . Proof. We abbreviate A = A ( σ w 2 ( S ) ) A=A(\sigma_w^2(S)) A = A ( σ w 2 ( S )) σ w 2 = σ w 2 ( S ) \sigma_w^2=\sigma_w^2(S) σ w 2 = σ w 2 ( S ) ( σ w 2 ( S ) , y ) (\sigma_w^2(S),y) ( σ w 2 ( S ) , y )
D ( σ w 2 , S , a , b ) = ∂ ( log p ( y ∣ S , σ w 2 ) + log p ( σ w 2 ( S ) ) ) ∂ σ w 2 = 0 (55) D(\sigma_w^2,S,a,b)=\frac{\partial(\log p(y|S,\sigma_w^2)+\log p(\sigma_w^2(S)))}{\partial\sigma_w^2}=0 \tag*{(55)} D ( σ w 2 , S , a , b ) = ∂ σ w 2 ∂ ( log p ( y ∣ S , σ w 2 ) + log p ( σ w 2 ( S ))) = 0 (55) = 1 2 y T A − 1 ∂ A − 1 ∂ σ w 2 A − 1 y − 1 2 tr ( A − 1 ∂ A ∂ σ w 2 ) + ∂ p ( σ w 2 ) ∂ σ w 2 = 0 (56) =\frac{1}{2}y^{\mathsf{T}}A^{-1}\frac{\partial A^{-1}}{\partial\sigma_w^2}A^{-1}y-\frac{1}{2}\operatorname{tr}\left(A^{-1}\frac{\partial A}{\partial\sigma_w^2}\right)+\frac{\partial p(\sigma_w^2)}{\partial\sigma_w^2}=0 \tag*{(56)} = 2 1 y T A − 1 ∂ σ w 2 ∂ A − 1 A − 1 y − 2 1 tr ( A − 1 ∂ σ w 2 ∂ A ) + ∂ σ w 2 ∂ p ( σ w 2 ) = 0 (56) = 1 2 ( y T A − 2 y − tr ( A − 1 ) ) + a − 1 σ w 2 − b = 0. (57) =\frac{1}{2}\left(y^{\mathsf{T}}A^{-2}y-\operatorname{tr}(A^{-1})\right)+\frac{a-1}{\sigma_w^2}-b=0. \tag*{(57)} = 2 1 ( y T A − 2 y − tr ( A − 1 ) ) + σ w 2 a − 1 − b = 0. (57) We apply the implicit function theorem [40 Theorem 1.3.1] : differentiate D ( σ w 2 , S , a , b ) = 0 D(\sigma_w^2,S,a,b)=0 D ( σ w 2 , S , a , b ) = 0 y i y_i y i σ w 2 = σ w 2 ( y ) \sigma_w^2=\sigma_w^2(y) σ w 2 = σ w 2 ( y ) y y y
∂ D ( σ w 2 , S , a , b ) ∂ σ w 2 ∂ σ w 2 ∂ h i + ∂ D ( σ w 2 , S , a , b ) ∂ h i = 0 ⟹ ∂ σ w 2 ∂ h i = − ∂ D ( σ w 2 , S , a , b ) ∂ h i ∂ D ( σ w 2 , S , a , b ) ∂ σ w 2 . (58) \frac{\partial D(\sigma_w^2,S,a,b)}{\partial\sigma_w^2}\frac{\partial\sigma_w^2}{\partial h_i}+\frac{\partial D(\sigma_w^2,S,a,b)}{\partial h_i}=0\quad\Longrightarrow\quad\frac{\partial\sigma_w^2}{\partial h_i}=-\frac{\frac{\partial D(\sigma_w^2,S,a,b)}{\partial h_i}}{\frac{\partial D(\sigma_w^2,S,a,b)}{\partial\sigma_w^2}}. \tag*{(58)} ∂ σ w 2 ∂ D ( σ w 2 , S , a , b ) ∂ h i ∂ σ w 2 + ∂ h i ∂ D ( σ w 2 , S , a , b ) = 0 ⟹ ∂ h i ∂ σ w 2 = − ∂ σ w 2 ∂ D ( σ w 2 , S , a , b ) ∂ h i ∂ D ( σ w 2 , S , a , b ) . (58) Since D ( σ w 2 , S , a , b ) = y ⊤ ( h i ) A ( h i ) − 2 y ( h i ) − tr ( A ( h i ) − 1 ) + a − 1 σ w 2 − b \mathcal{D}(\sigma_w^2,\mathcal{S},a,b)=y^{\top}(h_i)A(h_i)^{-2}y(h_i)-\operatorname{tr}(A(h_i)^{-1})+\frac{a-1}{\sigma_w^2}-b D ( σ w 2 , S , a , b ) = y ⊤ ( h i ) A ( h i ) − 2 y ( h i ) − tr ( A ( h i ) − 1 ) + σ w 2 a − 1 − b D ( σ w 2 , S , a , b ) \mathcal{D}(\sigma_w^2,\mathcal{S},a,b) D ( σ w 2 , S , a , b ) h i h_i h i
∂ D ( σ w 2 , S , a , b ) ∂ h i = ∂ ∂ h i ( y ⊤ ( h i ) A ( h i ) − 2 y ( h i ) − tr ( A ( h i ) − 1 ) ) (59) \frac{\partial\mathcal{D}(\sigma_w^2,\mathcal{S},a,b)}{\partial h_i}
=\frac{\partial}{\partial h_i}\left(y^{\top}(h_i)A(h_i)^{-2}y(h_i)-\operatorname{tr}(A(h_i)^{-1})\right) \tag*{(59)} ∂ h i ∂ D ( σ w 2 , S , a , b ) = ∂ h i ∂ ( y ⊤ ( h i ) A ( h i ) − 2 y ( h i ) − tr ( A ( h i ) − 1 ) ) (59) = y ⊤ ( h i ) ∂ A ( h i ) − 2 ∂ h i y ( h i ) − ∂ ∂ h i tr ( A ( h i ) − 1 ) + 2 ∂ y ( h i ) ∂ h i A ( h i ) − 2 (60) =y^{\top}(h_i)\frac{\partial A(h_i)^{-2}}{\partial h_i}y(h_i)-\frac{\partial}{\partial h_i}\operatorname{tr}(A(h_i)^{-1})+2\frac{\partial y(h_i)}{\partial h_i}A(h_i)^{-2} \tag*{(60)} = y ⊤ ( h i ) ∂ h i ∂ A ( h i ) − 2 y ( h i ) − ∂ h i ∂ tr ( A ( h i ) − 1 ) + 2 ∂ h i ∂ y ( h i ) A ( h i ) − 2 (60) = 2 ( ( A − 1 y ) i ( k x i , S ( A − 2 y ) ) + ( A − 2 y ) i ( k x i , S ( A − 1 y ) ) ) − 2 k x i , S ( A − 2 ) ⋅ , i − 2 y i ( A − 2 y ) i . (61) =2\left((A^{-1}y)_i(k_{x_i,\mathcal{S}}(A^{-2}y))+(A^{-2}y)_i(k_{x_i,\mathcal{S}}(A^{-1}y))\right)
-2k_{x_i,\mathcal{S}}(A^{-2})_{\cdot,i}-2y_i(A^{-2}y)_i. \tag*{(61)} = 2 ( ( A − 1 y ) i ( k x i , S ( A − 2 y )) + ( A − 2 y ) i ( k x i , S ( A − 1 y )) ) − 2 k x i , S ( A − 2 ) ⋅ , i − 2 y i ( A − 2 y ) i . (61) Hence, we can use the results of to compute the derivative of D ( σ w 2 , S , a , b ) \mathcal{D}(\sigma_w^2,\mathcal{S},a,b) D ( σ w 2 , S , a , b ) σ w 2 \sigma_w^2 σ w 2
∂ D ( σ w 2 , S , a , b ) ∂ σ w 2 = ∂ ∂ σ w 2 ( y ⊤ A ( σ w 2 ) − 2 y − tr ( A ( σ w 2 ) − 1 ) + 2 ( a − 1 ) σ w 2 ) (62) \frac{\partial\mathcal{D}(\sigma_w^2,\mathcal{S},a,b)}{\partial\sigma_w^2}
=\frac{\partial}{\partial\sigma_w^2}\left(y^{\top}A(\sigma_w^2)^{-2}y-\operatorname{tr}(A(\sigma_w^2)^{-1})+\frac{2(a-1)}{\sigma_w^2}\right) \tag*{(62)} ∂ σ w 2 ∂ D ( σ w 2 , S , a , b ) = ∂ σ w 2 ∂ ( y ⊤ A ( σ w 2 ) − 2 y − tr ( A ( σ w 2 ) − 1 ) + σ w 2 2 ( a − 1 ) ) (62) = y ⊤ ( − 2 A − 3 ) y − tr ( − A − 2 ) + − 2 ( a − 1 ) ( σ w 2 ) 2 (63) =y^{\top}(-2A^{-3})y-\operatorname{tr}(-A^{-2})+\frac{-2(a-1)}{(\sigma_w^2)^2} \tag*{(63)} = y ⊤ ( − 2 A − 3 ) y − tr ( − A − 2 ) + ( σ w 2 ) 2 − 2 ( a − 1 ) (63) = − 2 y ⊤ A − 3 y + tr ( A − 2 ) − 2 ( a − 1 ) ( σ w 2 ) 2 (64) =-2y^{\top}A^{-3}y+\operatorname{tr}(A^{-2})-\frac{2(a-1)}{(\sigma_w^2)^2} \tag*{(64)} = − 2 y ⊤ A − 3 y + tr ( A − 2 ) − ( σ w 2 ) 2 2 ( a − 1 ) (64) Finally, we combine the derived terms in the implicit differentiation, evaluated at h i = 0 h_i=0 h i = 0
∂ σ w 2 ∂ h i = − 2 ( ( A − 1 y ) i ( k x i , S ( A − 2 y ) ) + ( A − 2 y ) i ( k x i , S ( A − 1 y ) ) ) − 2 k x i , S ( A − 2 ) ⋅ , i − 2 y i ( A − 2 y ) i − 2 y ⊤ A − 3 y + tr ( A − 2 ) − 2 ( a − 1 ) ( σ w 2 ) 2 (65) \frac{\partial\sigma_w^2}{\partial h_i}
=
\frac{-2\left((A^{-1}y)_i(k_{x_i,\mathcal{S}}(A^{-2}y))+(A^{-2}y)_i(k_{x_i,\mathcal{S}}(A^{-1}y))\right)-2k_{x_i,\mathcal{S}}(A^{-2})_{\cdot,i}-2y_i(A^{-2}y)_i}
{-2y^{\top}A^{-3}y+\operatorname{tr}(A^{-2})-\frac{2(a-1)}{(\sigma_w^2)^2}} \tag*{(65)} ∂ h i ∂ σ w 2 = − 2 y ⊤ A − 3 y + tr ( A − 2 ) − ( σ w 2 ) 2 2 ( a − 1 ) − 2 ( ( A − 1 y ) i ( k x i , S ( A − 2 y )) + ( A − 2 y ) i ( k x i , S ( A − 1 y )) ) − 2 k x i , S ( A − 2 ) ⋅ , i − 2 y i ( A − 2 y ) i (65) = − ( A − 1 y ) i ( k x i , S ( A − 2 y ) ) − ( A − 2 y ) i ( k x i , S ( A − 1 y ) ) + k x i , S ( A − 2 ) ⋅ , i + y i ( A − 2 y ) i − y ⊤ A − 3 y + 1 2 tr ( A − 2 ) − a − 1 ( σ w 2 ) 2 . (66) =
\frac{-(A^{-1}y)_i(k_{x_i,\mathcal{S}}(A^{-2}y))-(A^{-2}y)_i(k_{x_i,\mathcal{S}}(A^{-1}y))+k_{x_i,\mathcal{S}}(A^{-2})_{\cdot,i}+y_i(A^{-2}y)_i}
{-y^{\top}A^{-3}y+\frac{1}{2}\operatorname{tr}(A^{-2})-\frac{a-1}{(\sigma_w^2)^2}}. \tag*{(66)} = − y ⊤ A − 3 y + 2 1 tr ( A − 2 ) − ( σ w 2 ) 2 a − 1 − ( A − 1 y ) i ( k x i , S ( A − 2 y )) − ( A − 2 y ) i ( k x i , S ( A − 1 y )) + k x i , S ( A − 2 ) ⋅ , i + y i ( A − 2 y ) i . (66) This completes the proof for the derivative of the aleatoric MAP w.r.t. the removal direction h i h_i h i
Proposition 4. Suppose we have a single test point Λ = { x } \Lambda=\{x\} Λ = { x } μ S ( x ) \mu_{\mathcal{S}}(x) μ S ( x ) σ S 2 ( x ) \sigma_{\mathcal{S}}^2(x) σ S 2 ( x ) S = { x i , y i } i = 1 n \mathcal{S}=\{x_i,y_i\}_{i=1}^n S = { x i , y i } i = 1 n v i ( x ) v_i(x) v i ( x ) x i ∈ S x_i\in\mathcal{S} x i ∈ S σ w 2 ( S ) \sigma_w^2(\mathcal{S}) σ w 2 ( S ) σ S 2 ( x ) \sigma_{\mathcal{S}}^2(x) σ S 2 ( x ) h i h_i h i x i ∈ S x_i\in\mathcal{S} x i ∈ S
v i ( x ) = ( 1 + k x , S A − 2 k S , x ) ∂ σ w 2 ( S ) ∂ h i , v_i(x)=\left(1+k_{x,\mathcal{S}}A^{-2}k_{\mathcal{S},x}\right)\frac{\partial\sigma_w^2(\mathcal{S})}{\partial h_i}, v i ( x ) = ( 1 + k x , S A − 2 k S , x ) ∂ h i ∂ σ w 2 ( S ) , where the partial derivative of the noise parameter is taken from Proposition 3.
Proof. Let the predictive uncertainty of the GP for a set of samples S \mathcal{S} S (2) , then we compute the derivative with respect to all aleatoric noise terms of σ S 2 \sigma_{\mathcal{S}}^2 σ S 2
σ S 2 ( x ) = k ( x , x ) − k x , S ( K + σ w 2 ( S ) I ) − 1 k S , x + σ w 2 ( S ) I . (67) \sigma_{\mathcal{S}}^2(x)=k(x,x)-k_{x,\mathcal{S}}(K+\sigma_w^2(\mathcal{S})I)^{-1}k_{\mathcal{S},x}+\sigma_w^2(\mathcal{S})I. \tag*{(67)} σ S 2 ( x ) = k ( x , x ) − k x , S ( K + σ w 2 ( S ) I ) − 1 k S , x + σ w 2 ( S ) I . (67) We further consider the RKHS and output space direction h i h_i h i
∂ σ S 2 ( x ) ∂ h i = ∂ ∂ h i k x , S ( K + σ w 2 ( S ) I ) − 1 k S , x + ∂ ∂ h i σ w 2 ( S ) (68) \frac{\partial\sigma_{\mathcal{S}}^2(x)}{\partial h_i}
=\frac{\partial}{\partial h_i}k_{x,\mathcal{S}}(K+\sigma_w^2(\mathcal{S})I)^{-1}k_{\mathcal{S},x}+\frac{\partial}{\partial h_i}\sigma_w^2(\mathcal{S}) \tag*{(68)} ∂ h i ∂ σ S 2 ( x ) = ∂ h i ∂ k x , S ( K + σ w 2 ( S ) I ) − 1 k S , x + ∂ h i ∂ σ w 2 ( S ) (68) = k x , S A − 1 ∂ σ w 2 ( S ) I ∂ h i A − 1 k S , x + ∂ σ w 2 ( S ) ∂ h i (69) =k_{x,\mathcal{S}}A^{-1}\frac{\partial\sigma_w^2(\mathcal{S})I}{\partial h_i}A^{-1}k_{\mathcal{S},x}+\frac{\partial\sigma_w^2(\mathcal{S})}{\partial h_i} \tag*{(69)} = k x , S A − 1 ∂ h i ∂ σ w 2 ( S ) I A − 1 k S , x + ∂ h i ∂ σ w 2 ( S ) (69) = ( 1 + k x , S A − 2 k S , x ) ∂ σ w 2 ( S ) ∂ h i , (70) =\left(1+k_{x,\mathcal{S}}A^{-2}k_{\mathcal{S},x}\right)\frac{\partial\sigma_w^2(\mathcal{S})}{\partial h_i}, \tag*{(70)} = ( 1 + k x , S A − 2 k S , x ) ∂ h i ∂ σ w 2 ( S ) , (70) which completes the proof for the aleatoric influence measure v i ( x ) v_i(x) v i ( x )
Algorithm 2 Forgetful BO
Require: Objective f f f X \mathcal{X} X α \alpha α n 0 n_0 n 0 T T T
Initialize dataset S 0 = { ( x i , y i ) } i = 1 n 0 S_0 = \{(x_i, y_i)\}_{i=1}^{n_0} S 0 = {( x i , y i ) } i = 1 n 0 y i = f ( x i ) y_i = f(x_i) y i = f ( x i )
Fit initial GP model ( μ S 0 ( ⋅ ) , σ S 0 ( ⋅ ) ) (\mu_{S_0}(\cdot), \sigma_{S_0}(\cdot)) ( μ S 0 ( ⋅ ) , σ S 0 ( ⋅ )) S 0 S_0 S 0
Set x ∗ = arg max x i ∈ S 0 y i x^* = \arg\max_{x_i \in S_0} y_i x ∗ = arg max x i ∈ S 0 y i y ∗ = max x i ∈ S 0 y i y^* = \max_{x_i \in S_0} y_i y ∗ = max x i ∈ S 0 y i
for t = 1 , … , T t = 1, \ldots, T t = 1 , … , T do
Optimize acquisition function: x t = arg max x ∈ X α ( x ∣ ( μ S t − 1 ′ ( ⋅ ) , σ S t − 1 ′ ( ⋅ ) ) ) x_t = \arg\max_{x \in\mathcal{X}} \alpha(x|(\mu_{S'_{t-1}}(\cdot), \sigma_{S'_{t-1}}(\cdot))) x t = arg max x ∈ X α ( x ∣ ( μ S t − 1 ′ ( ⋅ ) , σ S t − 1 ′ ( ⋅ )))
Evaluate objective: y t = f ( x t ) y_t = f(x_t) y t = f ( x t ) S t = S t − 1 ∪ { ( x t , y t ) } S_t = S_{t-1} \cup\{(x_t,y_t)\} S t = S t − 1 ∪ {( x t , y t )}
( x ∗ , y ∗ ) ← max ( ( x t , y t ) , ( x ∗ , y ∗ ) ) (x^*, y^*) \leftarrow\max((x_t,y_t),(x^*,y^*)) ( x ∗ , y ∗ ) ← max (( x t , y t ) , ( x ∗ , y ∗ ))
Initialize τ = 0 \tau= 0 τ = 0 S t ( 0 ) = S t S_t^{(0)} = S_t S t ( 0 ) = S t
Determine A t ( 0 ) \mathcal{A}_t^{(0)} A t ( 0 ) u ( 0 ) ( A t ( 0 ) ) , v ( 0 ) ( A t ( 0 ) ) u^{(0)}(\mathcal{A}_t^{(0)}), v^{(0)}(\mathcal{A}_t^{(0)}) u ( 0 ) ( A t ( 0 ) ) , v ( 0 ) ( A t ( 0 ) ) (4) and propositions 1 and 4
while min ( u ( τ ) ( A t ( τ ) ) + v ( τ ) ( A t ( τ ) ) ) < 0 \min(u^{(\tau)}(\mathcal{A}_t^{(\tau)}) + v^{(\tau)}(\mathcal{A}_t^{(\tau)})) < 0 min ( u ( τ ) ( A t ( τ ) ) + v ( τ ) ( A t ( τ ) )) < 0 do
Determine worst sample: i = arg min j ( u j ( τ ) ( A t ( τ ) ) + v j ( τ ) ( A t ( τ ) ) ) i = \arg\min_j (u_j^{(\tau)}(\mathcal{A}_t^{(\tau)}) + v_j^{(\tau)}(\mathcal{A}_t^{(\tau)})) i = arg min j ( u j ( τ ) ( A t ( τ ) ) + v j ( τ ) ( A t ( τ ) ))
Update S t ( τ + 1 ) = S t ( τ ) ∖ x i S_t^{(\tau+1)} = S_t^{(\tau)} \setminus x_i S t ( τ + 1 ) = S t ( τ ) ∖ x i
Update τ ← τ + 1 \tau\leftarrow\tau+ 1 τ ← τ + 1 A t ( τ ) , u ( τ ) ( A t ( τ ) ) , v ( τ ) ( A t ( τ ) ) \mathcal{A}_t^{(\tau)}, u^{(\tau)}(\mathcal{A}_t^{(\tau)}), v^{(\tau)}(\mathcal{A}_t^{(\tau)}) A t ( τ ) , u ( τ ) ( A t ( τ ) ) , v ( τ ) ( A t ( τ ) ) (4) and propositions 1 and 4
Set S t ′ = S t ( τ ) S'_t = S_t^{(\tau)} S t ′ = S t ( τ )
return x ∗ , y ∗ x^*, y^* x ∗ , y ∗
Forgetful Bayesian Optimization
Starting from an initial sample set S 0 S_0 S 0 n 0 n_0 n 0 S 0 S_0 S 0 α \alpha α A \mathcal{A} A (4) and assesses the contribution of each data point in S S S A \mathcal{A} A S ′ S' S ′ (4) . This forgetting step continues until all remaining samples provide a positive contribution to uncertainty reduction in the target region A \mathcal{A} A α \alpha α x t x_t x t S S S S S S T T T
In Figure 6 , we visualize the application of our iterative removal scheme F2I in our Forgetful BO pipeline. In Snapshot 1 , we visualize the default predictive distribution based on all samples and indicate with the black star the next chosen query point according to the GP-UCB acquisition function. The first red cross in Snapshot 1 indicates that Forgetful BO is removing the right-most sample. As we can see from Snapshot 3 , this removal causes the uncertainty bands to inflate at the location of the removal, which are outside of the previous target area A A A (4) , to not include previously excluded regions in the target region. Further, we see in Snapshot 3 that the detrimental data structure, composed of the three data points in the bottom left corner, is removed, resulting in the improved posterior predictive distribution visualized in Snapshot 4 . The recursive target region in Equation (4) has substantially decreased the size of the target region further. Within the target region, we now apply the GP-UCB acquisition function to query the next point at the location indicated with the yellow star, which coincides with the global optimum of our test function. This demonstrates visually how our removal scheme in Forgetful BO improves the predictive distribution of the model, and thereby results in better acquisition.
Forgetful Reinforcement Learning
Algorithm 3 Forgetful RL
Require: Initial real experience S 0 = { ( x i , a i , x i + 1 , r i ) } i = 1 n 0 \mathcal{S}_0 = \{(x_i, a_i, x_{i+1}, r_i)\}_{i=1}^{n_0} S 0 = {( x i , a i , x i + 1 , r i ) } i = 1 n 0 D S A C ← { } \mathcal{D}_{\mathrm{SAC}} \leftarrow\{\} D SAC ← { }
Fit initial GP model ( μ S 0 ( ⋅ ) , σ S 0 ( ⋅ ) ) (\mu_{\mathcal{S}_0}(\cdot), \sigma_{\mathcal{S}_0}(\cdot)) ( μ S 0 ( ⋅ ) , σ S 0 ( ⋅ )) S 0 \mathcal{S}_0 S 0
Initialize policy π 0 \pi_0 π 0 Q π 0 ( x , a ) Q^{\pi_0}(x,a) Q π 0 ( x , a )
for n = 1 , … , N n = 1,\ldots,N n = 1 , … , N do
Fit GP on current dataset S n − 1 \mathcal{S}_{n-1} S n − 1
Compute target region A n \mathcal{A}_n A n u ( A n ) , v ( A n ) u(\mathcal{A}_n), v(\mathcal{A}_n) u ( A n ) , v ( A n ) (4) and propositions 1 and 4
if there exist samples j ∈ A n j \in\mathcal{A}_n j ∈ A n ( u j + v j ) < 0 (u_j+v_j)<0 ( u j + v j ) < 0 then
R ← { j ∈ S n − 1 ∣ ( u j + v j ) < 0 } R \leftarrow\{j \in\mathcal{S}_{n-1}\mid(u_j+v_j)<0\} R ← { j ∈ S n − 1 ∣ ( u j + v j ) < 0 }
Remove samples: S n − 1 ← S n − 1 ∖ { ( x j , a j , x j + 1 , r j ) } j ∈ R \mathcal{S}_{n-1} \leftarrow\mathcal{S}_{n-1}\setminus\{(x_j,a_j,x_{j+1},r_j)\}_{j\in R} S n − 1 ← S n − 1 ∖ {( x j , a j , x j + 1 , r j ) } j ∈ R
Refit GP on the pruned dataset S n − 1 \mathcal{S}_{n-1} S n − 1 ( μ S n − 1 ( ⋅ ) , σ S n − 1 ( ⋅ ) ) (\mu_{\mathcal{S}_{n-1}}(\cdot),\sigma_{\mathcal{S}_{n-1}}(\cdot)) ( μ S n − 1 ( ⋅ ) , σ S n − 1 ( ⋅ ))
for m = 1 , … , M m = 1,\ldots,M m = 1 , … , M do ▷ Generate M M M H H H
Sample start state x ~ 0 ∼ ρ 0 \tilde{x}_0 \sim\rho_0 x ~ 0 ∼ ρ 0
for t = 0 , … , H − 1 t = 0,\ldots,H-1 t = 0 , … , H − 1 do
Sample action a ~ t ∼ π n − 1 ( ⋅ ∣ x ~ t ) \tilde{a}_t \sim\pi_{n-1}(\cdot\mid\tilde{x}_t) a ~ t ∼ π n − 1 ( ⋅ ∣ x ~ t )
Predict via GP: x ~ t + 1 ∼ p G P ( ⋅ ∣ x ~ t , a ~ t ) \tilde{x}_{t+1} \sim p_{\mathrm{GP}}(\cdot\mid\tilde{x}_t,\tilde{a}_t) x ~ t + 1 ∼ p GP ( ⋅ ∣ x ~ t , a ~ t ) r ~ t ← r G P ( x ~ t , a ~ t ) \tilde{r}_t \leftarrow r_{\mathrm{GP}}(\tilde{x}_t,\tilde{a}_t) r ~ t ← r GP ( x ~ t , a ~ t )
Store synthetic transition ( x ~ t , a ~ t , x ~ t + 1 , r ~ t ) (\tilde{x}_t,\tilde{a}_t,\tilde{x}_{t+1},\tilde{r}_t) ( x ~ t , a ~ t , x ~ t + 1 , r ~ t ) D S A C \mathcal{D}_{\mathrm{SAC}} D SAC
Learn π n = arg max π ∈ Π E π , p G P [ ∑ h = 0 H − 1 r ( s t , a t ) ] \pi_n = \arg\max_{\pi\in\Pi}\mathbb{E}_{\pi,p_{\mathrm{GP}}}\left[\sum_{h=0}^{H-1}r(s_t,a_t)\right] π n = arg max π ∈ Π E π , p GP [ ∑ h = 0 H − 1 r ( s t , a t ) ] D S A C \mathcal{D}_{\mathrm{SAC}} D SAC
for t = 0 , … , H − 1 t = 0,\ldots,H-1 t = 0 , … , H − 1 do
Execute action a t ∼ π n ( s t ) a_t \sim\pi_n(s_t) a t ∼ π n ( s t )
Append collected transition to the real buffer: S n ← S n − 1 ∪ { s t , a t , s t + 1 , r t } \mathcal{S}_n \leftarrow\mathcal{S}_{n-1}\cup\{s_t,a_t,s_{t+1},r_t\} S n ← S n − 1 ∪ { s t , a t , s t + 1 , r t }
Our MBRL implementation builds upon Model-Based Policy Optimization (MBPO) [31 ] and employs GPs to model both the dynamics and reward function. In each episode n n n S n \mathcal{S}_n S n π n \pi_n π n [27 ] agent with replay buffer D S A C \mathcal{D}_{\mathrm{SAC}} D SAC Q π n ( x , a ) Q^{\pi_n}(x,a) Q π n ( x , a ) (6) using the respective highest and lowest ensemble member of value functions. For a more principled approach to obtain these optimistic and pessimistic Q-functions, one can implement an uncertainty Bellman equation [55 ] or an approximation by for example using an optimistic and pessimistic uncertainty bonus, based on the model uncertainty [74 ] , or sampling based [71 ] .
To enhance model reliability, we introduce an additional removal step prior to generating the synthetic rollouts. Specifically, we determine the target region for potential improvements in Equation (6) . For this target region, we next determine the influence measures u u u v v v S n \mathcal{S}_n S n
Table 1 (PDF p. 23). Benchmark comparison showing mean and standard deviation across 100 different training sample draws. Best (lowest mean) values per row are highlighted in bold. Sharpness measures the average prediction uncertainty (lower is better, indicating sharper/more confident predictions).
Finally, this model is used to roll out the current policy π n \pi_n π n D S A C \mathcal{D}_{SAC} D S A C Q π n ( x , a ) Q^{\pi_n}(x,a) Q π n ( x , a )
Limitations and Future Work
Although the proposed removal procedure is substantially more efficient than exhaustive search or extensive leave-one-out evaluations, it still incurs computational overhead compared to a standard homoscedastic GP because each greedy step requires updating the model and evaluating the removal influence under the current posterior. Compared to other robust Gaussian process Bayesian Optimization baselines, we have comparable or lower computational costs Figure 20 .
Figure 20. Acquisition time comparisons for the different BO algorithms. Comparing mean and standard deviation across all evaluated non-corrupted benchmarks and baselines.
The accompanying near-optimality guarantee is based on a restricted curvature condition that serves as a theoretical certificate rather than an algorithmic constraint; in practice, these conditions may be conservative, and the method can remain effective even when they are not verified explicitly. Finally, the current formulation is tailored to Gaussian process models, and it would be interesting to investigate analogous removal influences for parametric models.
Experimental Setup
In this section, we provide a detailed description of the experimental setup of the transductive and Bayesian optimization benchmarks in Sections E.1 and E.2. For transductive learning, we additionally provide the numeric results table of Figure 3 .
Transductive Learning
We provide in Table 1, the absolute values with standard deviations for the results in Figure 3 .
We evaluate F2I in the transductive learning setting, in addition to the real world data sets, on two synthetic functions with a detrimental wavelength structure. Therefore, we consider a varying lengthscale across the domain, where our target region-aware algorithm F2I significantly improves in prediction accuracy and calibration. We therefore consider the test-functions Symmetric Lengthscale (LS) f s y m m e t r i c ( x ) f_{symmetric}(x) f sy mm e t r i c ( x ) Asymmetric Lengthscale (LS) f a s y m m e t r i c ( x ) f_{asymmetric}(x) f a sy mm e t r i c ( x )
f s y m m e t r i c ( x ) = sin ( 0.5 + 0.39 ⋅ ∣ x ∣ ) , (71) f_{symmetric}(x) = \sin(0.5 + 0.39 \cdot\lvert x \rvert), \tag*{(71)} f sy mm e t r i c ( x ) = sin ( 0.5 + 0.39 ⋅ ∣ x ∣) , (71) f a s y m m e t r i c ( x ) = { sin ( 0.5 + 0.39 x ) if x ≥ 0 sin ( 0.5 + 0.39 1 x ) otherwise. (72) f_{asymmetric}(x) =
\begin{cases}
\sin(0.5 + 0.39x) & \text{if } x \ge0 \\
\sin(0.5 + 0.39 \frac{1}{x}) & \text{otherwise.}
\end{cases} \tag*{(72)} f a sy mm e t r i c ( x ) = { sin ( 0.5 + 0.39 x ) sin ( 0.5 + 0.39 x 1 ) if x ≥ 0 otherwise. (72) We provide visualizations comparing the homoscedastic GP and F2I for both synthetic test functions in Figure 7 and Figure 8 . Further, we also provide the calibration metrics for the two examples in Figure 9 . The two designed test functions do not have specific outliers, but are rather detrimental in their overall design for the chosen kernel with a single lengthscale. We observe, that relevance pursuit is outperformed by F2I, which is also acknowledged in the limitations section of [4 ] by not considering the location of removed samples in relevance pursuite .
Figure 7. Influence of detrimental data structures based on Symmetric LS test functions. (Left) A standard homoscedastic GP absorbs the detrimental lengthscale structures in the noise. (Right) We visualize the result of applying F2I.
Figure 8. Influence of detrimental data structures based on Asymmetric LS test functions. (Left) A standard homoscedastic GP absorbs the detrimental lengthscale structures in the noise. (Right) We visualize the result of applying F2I.
Figure 9. Calibration comparison of (left) homoscedastic GP and (right) F2I for (a) symmetric and (b) asymmetric lengthscale increases test functions.
In addition, for all benchmarks in the transductive learning setting, we report the domain and task specifications in Table 2 . We evaluated all methods for 100 random seeds for an RBF kernel with a log prior log ( 0 , 1 ) \log(0,1) log ( 0 , 1 ) a = 2 a=2 a = 2 b = 0.15 b=0.15 b = 0.15
Table 2. Hyperparameters and settings for the transductive learning benchmarks.
Bayesian Optimization
For our BO benchmarks, we provide the standard domain limits, the dimensionality and the global optimum in Table 3 . During the optimization process, we rescale all objective functions into the hypercube [ 0 , 1 ] n [0,1]^n [ 0 , 1 ] n n n n
Table 3. Bayesian Optimization Test Functions: Domain Limits and Optimal Values
Additional Experiments
Further, we provide in this section different additional experiments to demonstrate the empirical performance and behavior of F2I, Forgetful BO and Forgetful RL. We first showcase the influence of the epistemic term of F2I in Section F.1, and provide additional Bayesian optimization and reinforcement learning experiments in Sections F.2 and F.4.
Aleatoric Noise Ablation
We ablate the epistemic term u u u v v v u + v u+v u + v u ≥ 0 u \ge0 u ≥ 0 Figure 10 , the joint criterion removes slightly fewer points while achieving substantially lower NLL on both benchmarks, with improved RMSE on Asymmetric and comparable RMSE on Twitter.
Figure 10. Comparing joint (u + v u+v u + v v v v u u u
Bayesian Optimization Ablations
As a challenging real-world benchmark for Bayesian optimization, we consider hyperparameter tuning for the GLMNET training algorithm [19 ] across multiple datasets. Following [62 , 57 , 61 ] , we replace the expensive evaluation step with a table lookup constructed from a large set of precomputed evaluations [43 ] . Using the first seven classification datasets from OpenML [9 ] , we study in Figure 11 whether Forgetful BO can improve transfer learning of hyperparameters across tasks. We evaluate the first seven tasks sequentially, using 25 samples per task. To highlight the effect of forgetting potentially detrimental information from previous datasets, and thus improving transfer across tasks, we compare our method against all baselines in two settings: one that retains all observations from previous tasks, and one that uses only data from the current task. Most importantly, all baselines benefit from retaining data from previous tasks, since this allows them to transfer knowledge about well-performing configurations across datasets. At the same time, we observe that Forgetful BO outperforms all baselines by selectively discarding information that is harmful for subsequent tasks. Both the cumulative regret in the left panel and the simple regret in the right panel confirm the value of forgetting in this setting.
Figure 11. Transfer learning AutoML benchmark for seven sequential GLMNET hyper-parameter training tasks. Comparison of (left) cumulative regret and (right) simple regret
For Figure 4 , we add in Figure 12 the two additional baselines for robust Bayesian Optimization, Student-t likelihood [49 ] and trimmed marginal log likelihood [5 ] , are compared to Forgetful BO. We observe that both trimmed MLL and Student-t likelihood are outperformed by Forgetful BO. We extend our evaluation in Figure 13 to the outlier setting of [4 ] , where the test functions are perturbed using constant outliers with probability p = 0.1 p = 0.1 p = 0.1 relevance search performs better relative to baselines in the perturbed setting, compared to the unperturbed, as mentioned in [4 ] , the algorithm might remove important samples related to the optimum by mistaking them for outliers, due to the dependence on the missing target region.
Figure 12. Simple regret of Forgetful BO and competing baselines for test functions.
Figure 13. Simple regret of Forgetful BO and competing baselines for perturbed test functions.
Additionally, we provide the cumulative regret results for the BO experiments from Figure 4 and Figure 13 . Figure 14 demonstrates that Forgetful BO is not only reaching good simple regret, but also has a fast diminishing regret, so that the accumulated value over all iterations t = 1 … T t = 1 \ldots T t = 1 … T
Figure 14. Cumulative regret of Forgetful BO and competing baselines for different test functions.
of Figure 13 in Figure 15 . In addition, Forgetful BO can seamlessly integrate different acquisition functions than GP-UCB [67 ] . TO demonstrate this, we evaluate Forgetful BO on all benchmarks using the log expected improvement (LEI) acquisition function [3 ] . Therefore, we also use LEI for all competitive baselines and visualize the achieved regret in Figure 16 . We note that, except for the Ackley 6D test-function, Forgetful BO performs better or on par with competing baselines. The cumulative regret for the LEI experiments are also provided in Figure 17 . To complete this evaluation, we provide the performance of Forgetful BO on the noisy benchmarks using the LEI acquisition function in Figure 18 and Figure 19 . We observe, that also in this setting Forgetful BO demonstrates superior or equal performance across all benchmarks and compared to all baselines.
Figure 15. Cumulative regret of Forgetful BO and competing baselines for different test functions with constant corruptions.
Figure 16. Simple regret of Forgetful BO and competing baselines for different test functions using log expected improvement acquisition function.
Figure 17. Cumulative regret of Forgetful BO and competing baselines for different test functions using log expected improvement acquisition function.
Figure 18. Simple regret of Forgetful BO and competing baselines for perturbed test functions using log expected improvement acquisition function.
Figure 19. Cumulative regret of Forgetful BO and competing baselines for perturbed test functions using log expected improvement acquisition function.
Bayesian Optimization Computational Complexity
We demonstrate in Figure 20 , that Forgetful BO, based on the removal algorithm F2I is computationally efficient. We report the mean and standard deviation of the acquisition time per sample. We visualize the mean across all random seeds and the entire optimization process of Figure 4 in Figure 20 . Note that Forgetful BO outperforms relevance pursuit by nearly one order of magnitude in the log-scale, while having small computational overhead compared to the homoscedastic GP and the Warped GP . The large variance of the Forgetful BO runtime is caused due to the potentially higher number of removals in later stages of the optimization process.
Reinforcement Learning
We conduct all reinforcement learning experiments for Forgetful RL using a single NVIDIA RTX 4090 GPU per run, with 5 CPU cores. Besides the linear kernel experiment in Figure 5 , we also consider tasks, which require a nonlinear model and for the pendulum, for example start in a downward pendulum position and require to swing up. This task nature requires a significantly larger target region, where the dynamics should be modeled well, and which can definitely no longer be approximated with a linear model. We first consider the inverted pendulum task in Figure 21 . We observe, that relatively little data removal occurs due to a much larger target region, but these lead to better convergence compared to the vanilla MBPO. We observe in Figure 21 , that we initially remove most points from the replay buffer, that we obtained from the initial random samples prefilling the buffer. We ablate in Figure 22 the removal behavior by not filling the buffer with random experiences before the initial episode. We observe that we converge slower and require to remove more detrimental experiences throughput learning, which have been gathered during suboptimal episodes. Further, we extend the swingup task in Figure 23 to Cartpole Swingup . Analogous to the other swingup , tasks we also remove fewer samples than in the Cartpole Balance task, because large parts of the state space are visited of the optimal policy, and require detailed modeling. We additionally increase the task difficulty of Inverted Pendulum by introducing a sparse reward function. In Figure 24 ,
Figure 21. Comparing the performance and data removal of Forgetful RL and vanilla GP-based MBPO for Inverted Pendulum .
Figure 22. Comparing the performance and data removal of Forgetful RL and vanilla GP-based MBPO for Inverted Pendulum , beginning with an empty buffer.
Figure 23. Comparing the performance and data removal of Forgetful RL and vanilla GP-based MBPO for Cartpole Swingup .
Figure 24. Comparing the performance and data removal of Forgetful RL and vanilla GP-based MBPO for Cartpole Swingup on a sparse reward task.
we observe that the task is significantly harder with a sparse reward and requires longer to converge. Forgetful RL also improves in this problem setting the learning behavior and reaches the optimum.
Near-Optimality
In this section, we both derive the near optimality theory Section G.1, and demonstrate empirically the used curvature and optimality diagnostics in Section G.2 dependent on the chosen noise prior.
Proof of the Near-Optimality Guarantee
In order to establish the near-optimality proof under a curvature condition on the magnitude of the prior parameter a a a p ( σ w 2 ( S ) ) = b a Γ ( a ) ( σ w 2 ( S ) ) a − 1 e − b σ w 2 ( S ) p(\sigma_w^2(S)) = \frac{b^a}{\Gamma(a)}(\sigma_w^2(S))^{a-1}e^{-b\sigma_w^2(S)} p ( σ w 2 ( S )) = Γ ( a ) b a ( σ w 2 ( S ) ) a − 1 e − b σ w 2 ( S )
We introduce the normalized removal-gain set function J ˉ \bar{J} J ˉ
Secondly, we show in Lemma 2 that F2I selects the removed data points greedily according to the first-order influence gradient − u i ( A ) − v i ( A ) -u_i(\mathcal{A})-v_i(\mathcal{A}) − u i ( A ) − v i ( A ) ∂ ∂ h ˉ i J ˉ ( A i ) \frac{\partial}{\partial\bar{h}_i}\bar{J}(\mathcal{A}_i) ∂ h ˉ i ∂ J ˉ ( A i ) − J ˉ -\bar{J} − J ˉ
We characterize the curvature of the continuous removal objective. Specifically, Lemma 3 derives the sensitivity of the estimated noise variance, while Lemma 4 establishes the Hessian contributions of epistemic and aleatoric uncertainty. Furthermore, Lemma 6 provides conditions on the Gamma-prior parameter a a a
Using RSC, we establish an upper bound U q U_q U q q q q
Finally, Lemma 8 combines gradient dominance with the realized-step coefficient ρ \rho ρ
In the following, we list all relevant lemmas and definitions required to establish Theorem 1:
Lemma 1. Consider the set of given samples S S S min S ′ ⊆ S J ( S ′ ) \min_{S'\subseteq S}\mathcal{J}(S') min S ′ ⊆ S J ( S ′ ) (3) . Let the removed set of samples be T = S ∖ S ′ T=S\setminus S' T = S ∖ S ′ J ˉ ( T ) \bar{\mathcal{J}}(T) J ˉ ( T )
max T ⊆ S J ˉ ( T ) : = J ( S ) − J ( S ′ ) = J ( S ) − J ( S ∖ T ) . \max_{T\subseteq S}\bar{\mathcal{J}}(T):=\mathcal{J}(S)-\mathcal{J}(S')=\mathcal{J}(S)-\mathcal{J}(S\setminus T). T ⊆ S max J ˉ ( T ) := J ( S ) − J ( S ′ ) = J ( S ) − J ( S ∖ T ) . This set function has the same form as [18 Equation 4] , with the submodularity ratio γ L , U \gamma_{L,U} γ L , U L ⊆ T L\subseteq T L ⊆ T U ⊆ T ∖ L U\subseteq T\setminus L U ⊆ T ∖ L
γ L , U ( J ˉ ) = ∑ j ∈ U ( J ˉ ( L ∪ { j } ) − J ˉ ( L ) ) J ˉ ( L ∪ U ) − J ˉ ( L ) . \gamma_{L,U}(\bar{\mathcal{J}})=\frac{\sum_{j\in U}\left(\bar{\mathcal{J}}(L\cup\{j\})-\bar{\mathcal{J}}(L)\right)}{\bar{\mathcal{J}}(L\cup U)-\bar{\mathcal{J}}(L)}. γ L , U ( J ˉ ) = J ˉ ( L ∪ U ) − J ˉ ( L ) ∑ j ∈ U ( J ˉ ( L ∪ { j }) − J ˉ ( L ) ) . Proof. Consider a retained set S ′ S' S ′ T = S ∖ S ′ T=S\setminus S' T = S ∖ S ′ L ⊆ T L\subseteq T L ⊆ T U ⊆ T ∖ L U\subseteq T\setminus L U ⊆ T ∖ L j ∈ U j\in U j ∈ U
J ˉ ( L ∪ { j } ) − J ˉ ( L ) = J ( S ) − J ( S ∖ ( L ∪ { j } ) ) − J ( S ) + J ( S ∖ L ) (73) \bar{\mathcal{J}}(L\cup\{j\})-\bar{\mathcal{J}}(L)=\mathcal{J}(S)-\mathcal{J}(S\setminus(L\cup\{j\}))-\mathcal{J}(S)+\mathcal{J}(S\setminus L) \tag*{(73)} J ˉ ( L ∪ { j }) − J ˉ ( L ) = J ( S ) − J ( S ∖ ( L ∪ { j })) − J ( S ) + J ( S ∖ L ) (73) = J ( S ∖ L ) − J ( S ∖ ( L ∪ { j } ) ) (74) =\mathcal{J}(S\setminus L)-\mathcal{J}(S\setminus(L\cup\{j\})) \tag*{(74)} = J ( S ∖ L ) − J ( S ∖ ( L ∪ { j })) (74) Thus, the forward marginal on J ˉ \bar{\mathcal{J}} J ˉ − J -\mathcal{J} − J [18 Def. 2] depends only on the marginal combinations. Hence, the submodularity ratio for the set-function considering the complement removal sets L ⊆ T L\subseteq T L ⊆ T U ⊆ T ∖ L U\subseteq T\setminus L U ⊆ T ∖ L
γ L , U ( J ˉ ) = ∑ j ∈ U ( J ˉ ( L ∪ { j } ) − J ˉ ( L ) ) J ˉ ( L ∪ U ) − J ˉ ( L ) . (75) \gamma_{L,U}(\bar{\mathcal{J}})=\frac{\sum_{j\in U}\left(\bar{\mathcal{J}}(L\cup\{j\})-\bar{\mathcal{J}}(L)\right)}{\bar{\mathcal{J}}(L\cup U)-\bar{\mathcal{J}}(L)}. \tag*{(75)} γ L , U ( J ˉ ) = J ˉ ( L ∪ U ) − J ˉ ( L ) ∑ j ∈ U ( J ˉ ( L ∪ { j }) − J ˉ ( L ) ) . (75) Lemma 2. Let S ⊆ X S\subseteq\mathcal{X} S ⊆ X x i ∈ S x_i\in S x i ∈ S
− J ( S ) = − ∑ x ∈ A σ S 2 ( x ) . -\mathcal{J}(S)=-\sum_{x\in\mathcal{A}}\sigma_S^2(x). − J ( S ) = − x ∈ A ∑ σ S 2 ( x ) . Let the RKHS removal direction associated with a sample i i i
k ( x , S , h i ) = k x , S − h i k ( x , x i ) e i , h i ∈ [ 0 , 1 ] ⊂ R , k(x,S,h_i)=k_{x,S}-h_i k(x,x_i)e_i,\qquad h_i\in[0,1]\subset\mathbb{R}, k ( x , S , h i ) = k x , S − h i k ( x , x i ) e i , h i ∈ [ 0 , 1 ] ⊂ R , i.e. an infinitesimal decrease of the kernel coupling to x i x_i x i − J -\mathcal{J} − J S S S
∂ ∂ h i − J ( A i ) ∣ h i = 0 = − u i ( A ) − v i ( A ) , \left.\frac{\partial}{\partial h_i}-\mathcal{J}(A_i)\right|_{h_i=0}=-u_i(\mathcal{A})-v_i(\mathcal{A}), ∂ h i ∂ − J ( A i ) h i = 0 = − u i ( A ) − v i ( A ) , where u i ( A ) u_i(\mathcal{A}) u i ( A ) v i ( A ) v_i(\mathcal{A}) v i ( A )
Proof. We compute the gradient of − J ( S ) -\mathcal{J}(S) − J ( S ) k ( ⋅ , x i ) k(\cdot,x_i) k ( ⋅ , x i )
− J ( S ) = ∑ x ∈ A ( − k ( x , x ) + k x , S A − 1 k S , x ) − ∣ A ∣ σ w 2 ( S ) , (76) -\mathcal{J}(S)=\sum_{x\in\mathcal{A}}\left(-k(x,x)+k_{x,S}A^{-1}k_{S,x}\right)-|\mathcal{A}|\sigma_w^2(S), \tag*{(76)} − J ( S ) = x ∈ A ∑ ( − k ( x , x ) + k x , S A − 1 k S , x ) − ∣ A ∣ σ w 2 ( S ) , (76) where ∣ A ∣ |\mathcal{A}| ∣ A ∣ A \mathcal{A} A h i h_i h i − J -\mathcal{J} − J x ∈ A x\in\mathcal{A} x ∈ A h i h_i h i A \mathcal{A} A
∂ − J ( S ) ∂ h i = ∑ x ∈ A ( − ∂ ∂ h i k ( x , x ) + ∂ ∂ h i k ( x , S , h i ) A ( h i ) − 1 k ( S , x , h i ) ) − ∣ A ∣ ∂ ∂ h i σ w 2 ( S ) = ∑ x ∈ A ( 2 ∂ k ( x , S , h i ) ∂ h i A − 1 k S , x − k ( x , S , h i ) A ( h i ) − 1 ∂ A ( h i ) ∂ h i A ( h i ) − 1 (77) \begin{aligned}
\frac{\partial-\mathcal{J}(\mathcal{S})}{\partial h_i}
=
\sum_{x\in\mathcal{A}}\left(-\frac{\partial}{\partial h_i}k(x,x)+\frac{\partial}{\partial h_i}k(x,\mathcal{S},h_i)A(h_i)^{-1}k(\mathcal{S},x,h_i)\right)-|\mathcal{A}|\frac{\partial}{\partial h_i}\sigma_w^2(\mathcal{S}) \\
&=
\sum_{x\in\mathcal{A}}\left(2\frac{\partial k(x,\mathcal{S},h_i)}{\partial h_i}A^{-1}k_{\mathcal{S},x}-k(x,\mathcal{S},h_i)A(h_i)^{-1}\frac{\partial A(h_i)}{\partial h_i}A(h_i)^{-1}
\right. \tag*{(77)}
\end{aligned} ∂ h i ∂ − J ( S ) = x ∈ A ∑ ( − ∂ h i ∂ k ( x , x ) + ∂ h i ∂ k ( x , S , h i ) A ( h i ) − 1 k ( S , x , h i ) ) − ∣ A ∣ ∂ h i ∂ σ w 2 ( S ) = x ∈ A ∑ ( 2 ∂ h i ∂ k ( x , S , h i ) A − 1 k S , x − k ( x , S , h i ) A ( h i ) − 1 ∂ h i ∂ A ( h i ) A ( h i ) − 1 (77) × k ( S , x , h i ) ) − ∣ A ∣ ∂ ∂ h i σ w 2 ( S ′ ) = ∑ x ∈ A ( − 2 k ( x , x i ) ( A − 1 k ( S , x ) ) i − k ( x , S , h i ) A ( h i ) − 1 ∂ K ( h i ) ∂ h i A ( h i ) − 1 k ( S , x , h i ) (78) \begin{aligned}
\left.
\times k(\mathcal{S},x,h_i)\right)-|\mathcal{A}|\frac{\partial}{\partial h_i}\sigma_w^2(\mathcal{S}') \\
&=
\sum_{x\in\mathcal{A}}(-2k(x,x_i)(A^{-1}k(\mathcal{S},x))_i-k(x,\mathcal{S},h_i)A(h_i)^{-1}\frac{\partial K(h_i)}{\partial h_i}A(h_i)^{-1}k(\mathcal{S},x,h_i) \tag*{(78)}
\end{aligned} × k ( S , x , h i ) ) − ∣ A ∣ ∂ h i ∂ σ w 2 ( S ′ ) = x ∈ A ∑ ( − 2 k ( x , x i ) ( A − 1 k ( S , x ) ) i − k ( x , S , h i ) A ( h i ) − 1 ∂ h i ∂ K ( h i ) A ( h i ) − 1 k ( S , x , h i ) (78) − k ( x , S , h i ) A ( h i ) − 1 ∂ σ w 2 ( S ) ∂ h i A ( h i ) − 1 k ( S , x , h i ) ) − ∣ A ∣ ∂ ∂ h i σ w 2 ( S ) = ∑ x ∈ A − 2 k ( x , x i ) ( A − 1 k ( S , x ) ) i − k ( x , S , h i ) A ( h i ) − 1 ( − e i k ( x i , S ) − k ( S , x i ) e i ⊤ ) (79) \begin{aligned}
\left.
-k(x,\mathcal{S},h_i)A(h_i)^{-1}\frac{\partial\sigma_w^2(\mathcal{S})}{\partial h_i}A(h_i)^{-1}k(\mathcal{S},x,h_i)\right)-|\mathcal{A}|\frac{\partial}{\partial h_i}\sigma_w^2(\mathcal{S}) \\
&=
\sum_{x\in\mathcal{A}}-2k(x,x_i)\left(A^{-1}k(\mathcal{S},x)\right)_i-k(x,\mathcal{S},h_i)A(h_i)^{-1}\left(-e_i k(x_i,\mathcal{S})-k(\mathcal{S},x_i)e_i^{\top}\right) \tag*{(79)}
\end{aligned} − k ( x , S , h i ) A ( h i ) − 1 ∂ h i ∂ σ w 2 ( S ) A ( h i ) − 1 k ( S , x , h i ) ) − ∣ A ∣ ∂ h i ∂ σ w 2 ( S ) = x ∈ A ∑ − 2 k ( x , x i ) ( A − 1 k ( S , x ) ) i − k ( x , S , h i ) A ( h i ) − 1 ( − e i k ( x i , S ) − k ( S , x i ) e i ⊤ ) (79) × A ( h i ) − 1 k ( S , x i ) − ∂ ∂ h i σ w 2 ( S ) ( 1 + k ( x , S , h i ) A ( h i ) − 2 k ( S , x , h i ) ) = ∑ x ∈ A − 2 k ( x , x i ) ( A − 1 k ( S , x ) ) i + 2 ( A − 1 k ( S , x ) ) i ( k ( x i , S ) A − 1 k ( S , x ) ) ⏟ − u i ( x ) (80) \begin{aligned}
\times A(h_i)^{-1}k(\mathcal{S},x_i)-\frac{\partial}{\partial h_i}\sigma_w^2(\mathcal{S})\left(1+k(x,\mathcal{S},h_i)A(h_i)^{-2}k(\mathcal{S},x,h_i)\right) \\
&=
\sum_{x\in\mathcal{A}}\underbrace{-2k(x,x_i)(A^{-1}k(\mathcal{S},x))_i+2(A^{-1}k(\mathcal{S},x))_i\left(k(x_i,\mathcal{S})A^{-1}k(\mathcal{S},x)\right)}_{-u_i(x)} \tag*{(80)}
\end{aligned} × A ( h i ) − 1 k ( S , x i ) − ∂ h i ∂ σ w 2 ( S ) ( 1 + k ( x , S , h i ) A ( h i ) − 2 k ( S , x , h i ) ) = x ∈ A ∑ − u i ( x ) − 2 k ( x , x i ) ( A − 1 k ( S , x ) ) i + 2 ( A − 1 k ( S , x ) ) i ( k ( x i , S ) A − 1 k ( S , x ) ) (80) − ( 1 + k ( x , S , h i ) A ( h i ) − 2 k ( S , x , h i ) ) ∂ ∂ h i σ w 2 ( S ) ⏟ − v i ( x ) (81) \underbrace{-(1+k(x,\mathcal{S},h_i)A(h_i)^{-2}k(\mathcal{S},x,h_i))\frac{\partial}{\partial h_i}\sigma_w^2(\mathcal{S})}_{-v_i(x)} \tag*{(81)} − v i ( x ) − ( 1 + k ( x , S , h i ) A ( h i ) − 2 k ( S , x , h i )) ∂ h i ∂ σ w 2 ( S ) (81) This completes the proof that − u i ( A ) − v i ( A ) -u_i(\mathcal{A})-v_i(\mathcal{A}) − u i ( A ) − v i ( A ) − J -\mathcal{J} − J x i x_i x i h i = 0 h_i=0 h i = 0
Definition 1 (Restricted Strong Concavity, Restricted Smoothness). A function − J ( ⋅ ) -\mathcal{J}(\cdot) − J ( ⋅ ) m R ∈ R + m_R\in\mathbb{R}_+ m R ∈ R + M R ∈ R + M_R\in\mathbb{R}_+ M R ∈ R + R R R
− m R 2 ∥ h ∥ 2 2 ≥ J ( S ∖ L ) − J ( S ∖ ( L ∪ U ) ) − ⟨ ∇ − J ( S ∖ L ) , h ⟩ ≥ − M R 2 ∥ h ∥ 2 2 , -\frac{m_R}{2}\lVert h\rVert_2^2\geq\mathcal{J}(\mathcal{S}\setminus L)-\mathcal{J}(\mathcal{S}\setminus(L\cup U))-\langle\nabla-\mathcal{J}(\mathcal{S}\setminus L),h\rangle\geq-\frac{M_R}{2}\lVert h\rVert_2^2, − 2 m R ∥ h ∥ 2 2 ≥ J ( S ∖ L ) − J ( S ∖ ( L ∪ U )) − ⟨ ∇ − J ( S ∖ L ) , h ⟩ ≥ − 2 M R ∥ h ∥ 2 2 , where L ∪ U ⊆ R L\cup U\subseteq R L ∪ U ⊆ R h h h L ∪ U L\cup U L ∪ U L L L
Lemma 3. Let S \mathcal{S} S σ w 2 ( S ) \sigma_w^2(\mathcal{S}) σ w 2 ( S ) D ( σ w 2 , S , a , b ) = 0 \mathcal{D}(\sigma_w^2,\mathcal{S},a,b)=0 D ( σ w 2 , S , a , b ) = 0 h h h h = 0 h=0 h = 0 T ≠ 0 T\ne0 T = 0 σ w 2 ( S ) \sigma_w^2(\mathcal{S}) σ w 2 ( S ) h h h h = 0 h=0 h = 0
∇ h 2 σ w 2 = − 1 T ( ∇ σ w 2 2 D ( σ w 2 ; y ) + ∇ σ w 2 , h 2 D ( σ w 2 ; y ) ( ∇ h σ w 2 ) ⊤ + ∇ h σ w 2 ( ∇ σ w 2 , h 2 D ( σ w 2 ; y ) ) ⊤ + ∇ σ w 2 2 T ( ∇ h σ w 2 ) ( ∇ h σ w 2 ) ⊤ ) , \nabla_h^2\sigma_w^2=-\frac{1}{T}\left(\nabla_{\sigma_w^2}^2\mathcal{D}(\sigma_w^2;y)+\nabla_{\sigma_w^2,h}^2\mathcal{D}(\sigma_w^2;y)(\nabla_h\sigma_w^2)^{\top}
+\nabla_h\sigma_w^2(\nabla_{\sigma_w^2,h}^2\mathcal{D}(\sigma_w^2;y))^{\top}
+\nabla_{\sigma_w^2}^2T(\nabla_h\sigma_w^2)(\nabla_h\sigma_w^2)^{\top}\right), ∇ h 2 σ w 2 = − T 1 ( ∇ σ w 2 2 D ( σ w 2 ; y ) + ∇ σ w 2 , h 2 D ( σ w 2 ; y ) ( ∇ h σ w 2 ) ⊤ + ∇ h σ w 2 ( ∇ σ w 2 , h 2 D ( σ w 2 ; y ) ) ⊤ + ∇ σ w 2 2 T ( ∇ h σ w 2 ) ( ∇ h σ w 2 ) ⊤ ) , where we define the following sub-parts of the derivatives as
∇ h σ w 2 = 1 T ( − α ( 1 ) ⊙ s ( 2 ) − α ( 2 ) ⊙ s ( 1 ) + diag ( M ( 2 ) ) + y ⊙ α ( 2 ) ) , \nabla_h\sigma_w^2=\frac{1}{T}\left(-\alpha^{(1)}\odot s^{(2)}-\alpha^{(2)}\odot s^{(1)}+\operatorname{diag}(M^{(2)})+y\odot\alpha^{(2)}\right), ∇ h σ w 2 = T 1 ( − α ( 1 ) ⊙ s ( 2 ) − α ( 2 ) ⊙ s ( 1 ) + diag ( M ( 2 ) ) + y ⊙ α ( 2 ) ) , ∇ σ w 2 , h 2 D ( σ w 2 ; y ) = − ( 2 α ( 2 ) ⊙ s ( 2 ) + 2 α ( 1 ) ⊙ s ( 3 ) + 2 α ( 3 ) ⊙ s ( 1 ) − 2 diag ( M ( 3 ) ) ) + 2 y ⊙ α ( 3 ) , \nabla_{\sigma_w^2,h}^2D(\sigma_w^2;y)=-\left(2\alpha^{(2)}\odot s^{(2)}+2\alpha^{(1)}\odot s^{(3)}+2\alpha^{(3)}\odot s^{(1)}-2\operatorname{diag}(M^{(3)})\right)+2y\odot\alpha^{(3)}, ∇ σ w 2 , h 2 D ( σ w 2 ; y ) = − ( 2 α ( 2 ) ⊙ s ( 2 ) + 2 α ( 1 ) ⊙ s ( 3 ) + 2 α ( 3 ) ⊙ s ( 1 ) − 2 diag ( M ( 3 ) ) ) + 2 y ⊙ α ( 3 ) , ∇ h 2 D ( σ w 2 ; y ) = A − 1 ⊙ ( ( s ( 1 ) s ( 2 ) T + s ( 2 ) s ( 1 ) T − y s ( 2 ) T − s ( 2 ) y T ) + A − 2 ⊙ ( ( s ( 1 ) − y ) ( s ( 1 ) − y ) T \nabla_h^2D(\sigma_w^2;y)=A^{-1}\odot\left((s^{(1)}s^{(2)\mathsf{T}}+s^{(2)}s^{(1)\mathsf{T}}-ys^{(2)\mathsf{T}}-s^{(2)}y^{\mathsf{T}}\right)+A^{-2}\odot\left((s^{(1)}-y)(s^{(1)}-y)^{\mathsf{T}}\right. ∇ h 2 D ( σ w 2 ; y ) = A − 1 ⊙ ( ( s ( 1 ) s ( 2 ) T + s ( 2 ) s ( 1 ) T − y s ( 2 ) T − s ( 2 ) y T ) + A − 2 ⊙ ( ( s ( 1 ) − y ) ( s ( 1 ) − y ) T + M ( 1 ) ⊙ ( α ( 1 ) s ( 2 ) T + s ( 2 ) α ( 1 ) T + α ( 2 ) s ( 1 ) T + s ( 1 ) α ( 2 ) T − y α ( 2 ) T − α ( 2 ) y T ) + M ( 2 ) ⊙ ( α ( 1 ) ( s ( 1 ) − y ) T + ( s ( 1 ) − y ) α ( 1 ) T ) + M ( 1 ) K ⊙ ( α ( 1 ) α ( 2 ) T + α ( 2 ) α ( 1 ) T ) \begin{aligned}
\left.+M^{(1)}\odot\left(\alpha^{(1)}s^{(2)\mathsf{T}}+s^{(2)}\alpha^{(1)\mathsf{T}}+\alpha^{(2)}s^{(1)\mathsf{T}}+s^{(1)}\alpha^{(2)\mathsf{T}}-y\alpha^{(2)\mathsf{T}}-\alpha^{(2)}y^{\mathsf{T}}\right)\right. \\
&+M^{(2)}\odot(\alpha^{(1)}(s^{(1)}-y)^{\mathsf{T}}+(s^{(1)}-y)\alpha^{(1)\mathsf{T}})+M^{(1)}K\odot(\alpha^{(1)}\alpha^{(2)\mathsf{T}}+\alpha^{(2)}\alpha^{(1)\mathsf{T}})
\end{aligned} + M ( 1 ) ⊙ ( α ( 1 ) s ( 2 ) T + s ( 2 ) α ( 1 ) T + α ( 2 ) s ( 1 ) T + s ( 1 ) α ( 2 ) T − y α ( 2 ) T − α ( 2 ) y T ) + M ( 2 ) ⊙ ( α ( 1 ) ( s ( 1 ) − y ) T + ( s ( 1 ) − y ) α ( 1 ) T ) + M ( 1 ) K ⊙ ( α ( 1 ) α ( 2 ) T + α ( 2 ) α ( 1 ) T ) + M ( 2 ) K ⊙ α ( 1 ) α ( 1 ) T − ( 2 M ( 1 ) ⊙ M ( 2 ) + A − 1 ⊙ M ( 2 ) K + A − 2 ⊙ M ( 1 ) K ) \left.+M^{(2)}K\odot\alpha^{(1)}\alpha^{(1)\mathsf{T}}-\left(2M^{(1)}\odot M^{(2)}+A^{-1}\odot M^{(2)}K+A^{-2}\odot M^{(1)}K\right)\right. + M ( 2 ) K ⊙ α ( 1 ) α ( 1 ) T − ( 2 M ( 1 ) ⊙ M ( 2 ) + A − 1 ⊙ M ( 2 ) K + A − 2 ⊙ M ( 1 ) K ) + K ⊙ ( A − 2 − α ( 1 ) α ( 2 ) T − α ( 2 ) α ( 1 ) T ) ) , \left.+K\odot\left(A^{-2}-\alpha^{(1)}\alpha^{(2)\mathsf{T}}-\alpha^{(2)}\alpha^{(1)\mathsf{T}}\right)\right), + K ⊙ ( A − 2 − α ( 1 ) α ( 2 ) T − α ( 2 ) α ( 1 ) T ) ) , ∇ σ w 2 T = 3 α ( 2 ) T α ( 2 ) − tr ( A − 3 ) + 2 ( a − 1 ) ( σ w 2 ) 3 , \nabla_{\sigma_w^2}T=3\alpha^{(2)\mathsf{T}}\alpha^{(2)}-\operatorname{tr}(A^{-3})+\frac{2(a-1)}{(\sigma_w^2)^3}, ∇ σ w 2 T = 3 α ( 2 ) T α ( 2 ) − tr ( A − 3 ) + ( σ w 2 ) 3 2 ( a − 1 ) , using the short hand notations
α ( p ) = A − p y , M ( p ) = K A − p , s ( p ) = K α ( p ) , \alpha^{(p)}=A^{-p}y,\qquad M^{(p)}=KA^{-p},\qquad s^{(p)}=K\alpha^{(p)}, α ( p ) = A − p y , M ( p ) = K A − p , s ( p ) = K α ( p ) , T = − α ( 1 ) T α ( 2 ) + 1 2 tr ( A − 2 ) − a − 1 ( σ w 2 ) 2 . T=-\alpha^{(1)\mathsf{T}}\alpha^{(2)}+\frac{1}{2}\operatorname{tr}(A^{-2})-\frac{a-1}{(\sigma_w^2)^2}. T = − α ( 1 ) T α ( 2 ) + 2 1 tr ( A − 2 ) − ( σ w 2 ) 2 a − 1 . Proof. We obtained the first derivative from the implicit function theorem
∂ D ( σ w 2 ; y ) ∂ σ w 2 ∂ σ w 2 ∂ h i + ∂ D ( σ w 2 ; y ) ∂ h i = 0. (82) \frac{\partial D(\sigma_w^2;y)}{\partial\sigma_w^2}\frac{\partial\sigma_w^2}{\partial h_i}+\frac{\partial D(\sigma_w^2;y)}{\partial h_i}=0. \tag*{(82)} ∂ σ w 2 ∂ D ( σ w 2 ; y ) ∂ h i ∂ σ w 2 + ∂ h i ∂ D ( σ w 2 ; y ) = 0. (82) By differentiating the identity in Equation (82) w.r.t. h j h_j h j
∂ ∂ h j ( ∂ D ( σ w 2 ; y ) ∂ σ w 2 ∂ σ w 2 ∂ h i + ∂ D ( σ w 2 ; y ) ∂ h i ) = ( ∂ 2 D ( σ w 2 ; y ) ∂ σ w 2 ∂ h j + ∂ 2 D ( σ w 2 ; y ) ∂ ( σ w 2 ) 2 ∂ σ w 2 ∂ h j ) ∂ σ w 2 ∂ h i + ∂ 2 D ( σ w 2 ; y ) ∂ h i ∂ h j + ∂ 2 D ( σ w 2 ; y ) ∂ σ w 2 ∂ h i ∂ σ w 2 ∂ h j + ∂ D ( σ w 2 ; y ) ∂ σ w 2 ∂ 2 σ w 2 ∂ h i ∂ h j = 0. (83) \begin{aligned}
\frac{\partial}{\partial h_j}\left(\frac{\partial D(\sigma_w^2;y)}{\partial\sigma_w^2}\frac{\partial\sigma_w^2}{\partial h_i}+\frac{\partial D(\sigma_w^2;y)}{\partial h_i}\right)=\left(\frac{\partial^2D(\sigma_w^2;y)}{\partial\sigma_w^2\partial h_j}+\frac{\partial^2D(\sigma_w^2;y)}{\partial(\sigma_w^2)^2}\frac{\partial\sigma_w^2}{\partial h_j}\right)\frac{\partial\sigma_w^2}{\partial h_i} \\
&+\frac{\partial^2D(\sigma_w^2;y)}{\partial h_i\partial h_j}+\frac{\partial^2D(\sigma_w^2;y)}{\partial\sigma_w^2\partial h_i}\frac{\partial\sigma_w^2}{\partial h_j}+\frac{\partial D(\sigma_w^2;y)}{\partial\sigma_w^2}\frac{\partial^2\sigma_w^2}{\partial h_i\partial h_j}=0. \tag*{(83)}
\end{aligned} ∂ h j ∂ ( ∂ σ w 2 ∂ D ( σ w 2 ; y ) ∂ h i ∂ σ w 2 + ∂ h i ∂ D ( σ w 2 ; y ) ) = ( ∂ σ w 2 ∂ h j ∂ 2 D ( σ w 2 ; y ) + ∂ ( σ w 2 ) 2 ∂ 2 D ( σ w 2 ; y ) ∂ h j ∂ σ w 2 ) ∂ h i ∂ σ w 2 + ∂ h i ∂ h j ∂ 2 D ( σ w 2 ; y ) + ∂ σ w 2 ∂ h i ∂ 2 D ( σ w 2 ; y ) ∂ h j ∂ σ w 2 + ∂ σ w 2 ∂ D ( σ w 2 ; y ) ∂ h i ∂ h j ∂ 2 σ w 2 = 0. (83) Reordering the terms yields the desired second derivative from the implicit function theorem
∂ 2 σ w 2 ∂ h i ∂ h j = − 1 ∂ D ( σ w 2 ; y ) ∂ σ w 2 ( ∂ 2 D ( σ w 2 ; y ) ∂ σ w 2 ∂ h j ∂ σ w 2 ∂ h i + ∂ 2 D ( σ w 2 ; y ) ∂ ( σ w 2 ) 2 ∂ σ w 2 ∂ h j ∂ σ w 2 ∂ h i + ∂ 2 D ( σ w 2 ; y ) ∂ h i ∂ h j + ∂ 2 D ( σ w 2 ; y ) ∂ σ w 2 ∂ h i ∂ σ w 2 ∂ h j ) . (84) \begin{aligned}
\frac{\partial^2\sigma_w^2}{\partial h_i\partial h_j}=-\frac{1}{\frac{\partial D(\sigma_w^2;y)}{\partial\sigma_w^2}}(\frac{\partial^2D(\sigma_w^2;y)}{\partial\sigma_w^2\partial h_j}\frac{\partial\sigma_w^2}{\partial h_i}+\frac{\partial^2D(\sigma_w^2;y)}{\partial(\sigma_w^2)^2}\frac{\partial\sigma_w^2}{\partial h_j}\frac{\partial\sigma_w^2}{\partial h_i} \\
&+\frac{\partial^2D(\sigma_w^2;y)}{\partial h_i\partial h_j}+\frac{\partial^2D(\sigma_w^2;y)}{\partial\sigma_w^2\partial h_i}\frac{\partial\sigma_w^2}{\partial h_j}). \tag*{(84)}
\end{aligned} ∂ h i ∂ h j ∂ 2 σ w 2 = − ∂ σ w 2 ∂ D ( σ w 2 ; y ) 1 ( ∂ σ w 2 ∂ h j ∂ 2 D ( σ w 2 ; y ) ∂ h i ∂ σ w 2 + ∂ ( σ w 2 ) 2 ∂ 2 D ( σ w 2 ; y ) ∂ h j ∂ σ w 2 ∂ h i ∂ σ w 2 + ∂ h i ∂ h j ∂ 2 D ( σ w 2 ; y ) + ∂ σ w 2 ∂ h i ∂ 2 D ( σ w 2 ; y ) ∂ h j ∂ σ w 2 ) . (84) We now differentiate each term to obtain the full Hessian. For convenience, we introduce the abbreviation α ( p ) = A − p y \alpha^{(p)}=A^{-p}y α ( p ) = A − p y ∂ σ w 2 ∂ h i \frac{\partial\sigma_w^2}{\partial h_i} ∂ h i ∂ σ w 2 ∂ σ w 2 ∂ h j \frac{\partial\sigma_w^2}{\partial h_j} ∂ h j ∂ σ w 2
∂ σ w 2 ∂ h i = − ∂ D ( σ w 2 ; y ) ∂ h i ∂ D ( σ w 2 ; y ) ∂ σ w 2 = − α i ( 1 ) ( k x i , S α ( 2 ) ) − α i ( 2 ) ( k x i , S α ( 1 ) ) + k x i , S ( A − 2 ) ⋅ , i + y i ( A − 2 y ) i − α ( 1 ) T α ( 2 ) + 1 2 tr ( A − 2 ) − a − 1 ( σ w 2 ) 2 , (85) \frac{\partial\sigma_w^2}{\partial h_i}=-\frac{\frac{\partial D(\sigma_w^2;y)}{\partial h_i}}{\frac{\partial D(\sigma_w^2;y)}{\partial\sigma_w^2}}=\frac{-\alpha_i^{(1)}(k_{x_i,S}\alpha^{(2)})-\alpha_i^{(2)}(k_{x_i,S}\alpha^{(1)})+k_{x_i,S}(A^{-2})_{\cdot,i}+y_i(A^{-2}y)_i}{-\alpha^{(1)\mathsf{T}}\alpha^{(2)}+\frac{1}{2}\operatorname{tr}(A^{-2})-\frac{a-1}{(\sigma_w^2)^2}}, \tag*{(85)} ∂ h i ∂ σ w 2 = − ∂ σ w 2 ∂ D ( σ w 2 ; y ) ∂ h i ∂ D ( σ w 2 ; y ) = − α ( 1 ) T α ( 2 ) + 2 1 tr ( A − 2 ) − ( σ w 2 ) 2 a − 1 − α i ( 1 ) ( k x i , S α ( 2 ) ) − α i ( 2 ) ( k x i , S α ( 1 ) ) + k x i , S ( A − 2 ) ⋅ , i + y i ( A − 2 y ) i , (85) ∂ σ w 2 ∂ h j = − ∂ D ( σ w 2 ; y ) ∂ h j ∂ D ( σ w 2 ; y ) ∂ σ w 2 = − α j ( 1 ) ( k x j , S α ( 2 ) ) − α j ( 2 ) ( k x j , S α ( 1 ) ) + k x j , S ( A − 2 ) ⋅ , j + y j ( A − 2 y ) j − α ( 1 ) T α ( 2 ) + 1 2 tr ( A − 2 ) − a − 1 ( σ w 2 ) 2 . \frac{\partial\sigma_w^2}{\partial h_j}=-\frac{\frac{\partial D(\sigma_w^2;y)}{\partial h_j}}{\frac{\partial D(\sigma_w^2;y)}{\partial\sigma_w^2}}=\frac{-\alpha_j^{(1)}(k_{x_j,S}\alpha^{(2)})-\alpha_j^{(2)}(k_{x_j,S}\alpha^{(1)})+k_{x_j,S}(A^{-2})_{\cdot,j}+y_j(A^{-2}y)_j}{-\alpha^{(1)\mathsf{T}}\alpha^{(2)}+\frac{1}{2}\operatorname{tr}(A^{-2})-\frac{a-1}{(\sigma_w^2)^2}}. ∂ h j ∂ σ w 2 = − ∂ σ w 2 ∂ D ( σ w 2 ; y ) ∂ h j ∂ D ( σ w 2 ; y ) = − α ( 1 ) T α ( 2 ) + 2 1 tr ( A − 2 ) − ( σ w 2 ) 2 a − 1 − α j ( 1 ) ( k x j , S α ( 2 ) ) − α j ( 2 ) ( k x j , S α ( 1 ) ) + k x j , S ( A − 2 ) ⋅ , j + y j ( A − 2 y ) j . The denominator is given by
∂ D ( σ w 2 ; y ) ∂ σ w 2 = − y T A − 3 y + 1 2 tr ( A − 2 ) − a − 1 ( σ w 2 ) 2 = − α ( 1 ) T α ( 2 ) + 1 2 tr ( A − 2 ) − a − 1 ( σ w 2 ) 2 . (86) \begin{aligned}
\frac{\partial D(\sigma_w^2;y)}{\partial\sigma_w^2}=-y^{\mathsf{T}}A^{-3}y+\frac{1}{2}\operatorname{tr}(A^{-2})-\frac{a-1}{(\sigma_w^2)^2} \\
&=-\alpha^{(1)\mathsf{T}}\alpha^{(2)}+\frac{1}{2}\operatorname{tr}(A^{-2})-\frac{a-1}{(\sigma_w^2)^2}. \tag*{(86)}
\end{aligned} ∂ σ w 2 ∂ D ( σ w 2 ; y ) = − y T A − 3 y + 2 1 tr ( A − 2 ) − ( σ w 2 ) 2 a − 1 = − α ( 1 ) T α ( 2 ) + 2 1 tr ( A − 2 ) − ( σ w 2 ) 2 a − 1 . (86) The second derivative of this term is given by
∂ 2 D ( σ w 2 ; y ) ∂ ( σ w 2 ) 2 = 3 y ⊤ A − 4 y − tr ( A − 3 ) + 2 ( a − 1 ) ( σ w 2 ) 3 = 3 α ( 2 ) ⊤ α ( 2 ) − tr ( A − 3 ) + 2 ( a − 1 ) ( σ w 2 ) 3 . (87) \begin{aligned}
\frac{\partial^2 D(\sigma_w^2;y)}{\partial(\sigma_w^2)^2}=3y^\top A^{-4}y-\operatorname{tr}(A^{-3})+\frac{2(a-1)}{(\sigma_w^2)^3} \\
&=3\alpha^{(2)\top}\alpha^{(2)}-\operatorname{tr}(A^{-3})+\frac{2(a-1)}{(\sigma_w^2)^3}. \tag*{(87)}
\end{aligned} ∂ ( σ w 2 ) 2 ∂ 2 D ( σ w 2 ; y ) = 3 y ⊤ A − 4 y − tr ( A − 3 ) + ( σ w 2 ) 3 2 ( a − 1 ) = 3 α ( 2 ) ⊤ α ( 2 ) − tr ( A − 3 ) + ( σ w 2 ) 3 2 ( a − 1 ) . (87) Further, the cross derivatives ∂ 2 D ( σ w 2 ; y ) ∂ σ w 2 ∂ h i \frac{\partial^2D(\sigma_w^2;y)}{\partial\sigma_w^2\partial h_i} ∂ σ w 2 ∂ h i ∂ 2 D ( σ w 2 ; y ) ∂ 2 D ( σ w 2 ; y ) ∂ σ w 2 ∂ h j \frac{\partial^2D(\sigma_w^2;y)}{\partial\sigma_w^2\partial h_j} ∂ σ w 2 ∂ h j ∂ 2 D ( σ w 2 ; y ) ∂ D ∂ h i = α i ( 1 ) s i ( 2 ) + α i ( 2 ) s i ( 1 ) − diag ( M ( 2 ) ) i − y i α i ( 2 ) \frac{\partial D}{\partial h_i}=\alpha_i^{(1)}s_i^{(2)}+\alpha_i^{(2)}s_i^{(1)}-\operatorname{diag}(M^{(2)})_i-y_i\alpha_i^{(2)} ∂ h i ∂ D = α i ( 1 ) s i ( 2 ) + α i ( 2 ) s i ( 1 ) − diag ( M ( 2 ) ) i − y i α i ( 2 ) σ w 2 \sigma_w^2 σ w 2 ∂ α ( p ) ∂ σ w 2 = − p α ( p + 1 ) \frac{\partial\alpha^{(p)}}{\partial\sigma_w^2}=-p\alpha^{(p+1)} ∂ σ w 2 ∂ α ( p ) = − p α ( p + 1 ) ∂ s ( p ) ∂ σ w 2 = − p s ( p + 1 ) \frac{\partial s^{(p)}}{\partial\sigma_w^2}=-p s^{(p+1)} ∂ σ w 2 ∂ s ( p ) = − p s ( p + 1 )
∂ 2 D ( σ w 2 ; y ) ∂ σ w 2 ∂ h i = − 2 α i ( 2 ) ( k x i , S α ( 2 ) ) − 2 α i ( 1 ) ( k x i , S α ( 3 ) ) − 2 α i ( 3 ) ( k x i , S α ( 1 ) ) + 2 k x i , S ( A − 3 ) ⋅ , i + 2 y i α i ( 3 ) , (88) \frac{\partial^2D(\sigma_w^2;y)}{\partial\sigma_w^2\partial h_i}
=-2\alpha_i^{(2)}(k_{x_i,S}\alpha^{(2)})-2\alpha_i^{(1)}(k_{x_i,S}\alpha^{(3)})-2\alpha_i^{(3)}(k_{x_i,S}\alpha^{(1)})
+2k_{x_i,S}(A^{-3})_{\cdot,i}+2y_i\alpha_i^{(3)}, \tag*{(88)} ∂ σ w 2 ∂ h i ∂ 2 D ( σ w 2 ; y ) = − 2 α i ( 2 ) ( k x i , S α ( 2 ) ) − 2 α i ( 1 ) ( k x i , S α ( 3 ) ) − 2 α i ( 3 ) ( k x i , S α ( 1 ) ) + 2 k x i , S ( A − 3 ) ⋅ , i + 2 y i α i ( 3 ) , (88) ∂ 2 D ( σ w 2 ; y ) ∂ σ w 2 ∂ h j = − 2 α j ( 2 ) ( k x j , S α ( 2 ) ) − 2 α j ( 1 ) ( k x j , S α ( 3 ) ) − 2 α j ( 3 ) ( k x j , S α ( 1 ) ) + 2 k x j , S ( A − 3 ) ⋅ , j + 2 y j α j ( 3 ) . (89) \frac{\partial^2D(\sigma_w^2;y)}{\partial\sigma_w^2\partial h_j}
=-2\alpha_j^{(2)}(k_{x_j,S}\alpha^{(2)})-2\alpha_j^{(1)}(k_{x_j,S}\alpha^{(3)})-2\alpha_j^{(3)}(k_{x_j,S}\alpha^{(1)})
+2k_{x_j,S}(A^{-3})_{\cdot,j}+2y_j\alpha_j^{(3)}. \tag*{(89)} ∂ σ w 2 ∂ h j ∂ 2 D ( σ w 2 ; y ) = − 2 α j ( 2 ) ( k x j , S α ( 2 ) ) − 2 α j ( 1 ) ( k x j , S α ( 3 ) ) − 2 α j ( 3 ) ( k x j , S α ( 1 ) ) + 2 k x j , S ( A − 3 ) ⋅ , j + 2 y j α j ( 3 ) . (89) Finally, we derive ∂ 2 D ( σ w 2 ; y ) ∂ h i ∂ h j \frac{\partial^2D(\sigma_w^2;y)}{\partial h_i\partial h_j} ∂ h i ∂ h j ∂ 2 D ( σ w 2 ; y ) A ( h ) = P ( h ) K P ( h ) + σ w 2 I A(h)=P(h)KP(h)+\sigma_w^2I A ( h ) = P ( h ) K P ( h ) + σ w 2 I y ( h ) = P ( h ) y y(h)=P(h)y y ( h ) = P ( h ) y P ( h ) = diag ( 1 − h ) P(h)=\operatorname{diag}(1-h) P ( h ) = diag ( 1 − h ) y ( h ) y(h) y ( h ) h h h A ( h ) A(h) A ( h ) h = 0 h=0 h = 0
∂ A ∂ h i = − ( e i e i ⊤ K + K e i e i ⊤ ) , ∂ y ∂ h i = − y i e i , \frac{\partial A}{\partial h_i}=-(e_ie_i^\top K+Ke_ie_i^\top),\qquad\frac{\partial y}{\partial h_i}=-y_ie_i, ∂ h i ∂ A = − ( e i e i ⊤ K + K e i e i ⊤ ) , ∂ h i ∂ y = − y i e i , ∂ 2 A ∂ h i ∂ h j = e i e i ⊤ K e j e j ⊤ + e j e j ⊤ K e i e i ⊤ , ∂ 2 y ∂ h i ∂ h j = 0. (90) \frac{\partial^2 A}{\partial h_i\partial h_j}=e_ie_i^\top Ke_je_j^\top+e_je_j^\top Ke_ie_i^\top,\qquad\frac{\partial^2y}{\partial h_i\partial h_j}=0. \tag*{(90)} ∂ h i ∂ h j ∂ 2 A = e i e i ⊤ K e j e j ⊤ + e j e j ⊤ K e i e i ⊤ , ∂ h i ∂ h j ∂ 2 y = 0. (90) The first derivative reads
∂ D ( σ w 2 ; y ) ∂ h i = − y i α i ( 2 ) − α ( 1 ) ⊤ ∂ A ∂ h i α ( 2 ) + 1 2 tr ( A − 2 ∂ A ∂ h i ) , (91) \frac{\partial D(\sigma_w^2;y)}{\partial h_i}=-y_i\alpha_i^{(2)}-\alpha^{(1)\top}\frac{\partial A}{\partial h_i}\alpha^{(2)}+\frac{1}{2}\operatorname{tr}\left(A^{-2}\frac{\partial A}{\partial h_i}\right), \tag*{(91)} ∂ h i ∂ D ( σ w 2 ; y ) = − y i α i ( 2 ) − α ( 1 ) ⊤ ∂ h i ∂ A α ( 2 ) + 2 1 tr ( A − 2 ∂ h i ∂ A ) , (91) and differentiating once more w.r.t. h j h_j h j
∂ 2 D ( σ w 2 ; y ) ∂ h i ∂ h j = − y i ( ∂ α ( 2 ) ∂ h j ) i − ( ∂ α ( 1 ) ∂ h j ) ⊤ ∂ A ∂ h i α ( 2 ) − α ( 1 ) ⊤ ∂ A ∂ h i ∂ α ( 2 ) ∂ h j − α ( 1 ) ⊤ ∂ 2 A ∂ h i ∂ h j α ( 2 ) − 1 2 tr ( ( A − 1 ∂ A ∂ h j A − 2 + A − 2 ∂ A ∂ h j A − 1 ) ∂ A ∂ h i ) + 1 2 tr ( A − 2 ∂ 2 A ∂ h i ∂ h j ) . (92) \begin{aligned}
\frac{\partial^2D(\sigma_w^2;y)}{\partial h_i\partial h_j}
={}&-y_i\left(\frac{\partial\alpha^{(2)}}{\partial h_j}\right)_i
-\left(\frac{\partial\alpha^{(1)}}{\partial h_j}\right)^\top\frac{\partial A}{\partial h_i}\alpha^{(2)}
-\alpha^{(1)\top}\frac{\partial A}{\partial h_i}\frac{\partial\alpha^{(2)}}{\partial h_j}\\
&-\alpha^{(1)\top}\frac{\partial^2A}{\partial h_i\partial h_j}\alpha^{(2)}
-\frac{1}{2}\operatorname{tr}\left(\left(A^{-1}\frac{\partial A}{\partial h_j}A^{-2}+A^{-2}\frac{\partial A}{\partial h_j}A^{-1}\right)\frac{\partial A}{\partial h_i}\right)\\
&+\frac{1}{2}\operatorname{tr}\left(A^{-2}\frac{\partial^2A}{\partial h_i\partial h_j}\right). \tag*{(92)}
\end{aligned} ∂ h i ∂ h j ∂ 2 D ( σ w 2 ; y ) = − y i ( ∂ h j ∂ α ( 2 ) ) i − ( ∂ h j ∂ α ( 1 ) ) ⊤ ∂ h i ∂ A α ( 2 ) − α ( 1 ) ⊤ ∂ h i ∂ A ∂ h j ∂ α ( 2 ) − α ( 1 ) ⊤ ∂ h i ∂ h j ∂ 2 A α ( 2 ) − 2 1 tr ( ( A − 1 ∂ h j ∂ A A − 2 + A − 2 ∂ h j ∂ A A − 1 ) ∂ h i ∂ A ) + 2 1 tr ( A − 2 ∂ h i ∂ h j ∂ 2 A ) . (92) with
∂ α ( 1 ) ∂ h j = A − 1 ( ∂ y ∂ h j − ∂ A ∂ h j α ( 1 ) ) , ∂ α ( 2 ) ∂ h j = A − 1 ( ∂ α ( 1 ) ∂ h j − ∂ A ∂ h j α ( 2 ) ) . (93) \frac{\partial\alpha^{(1)}}{\partial h_j}=A^{-1}\left(\frac{\partial y}{\partial h_j}-\frac{\partial A}{\partial h_j}\alpha^{(1)}\right),\qquad
\frac{\partial\alpha^{(2)}}{\partial h_j}=A^{-1}\left(\frac{\partial\alpha^{(1)}}{\partial h_j}-\frac{\partial A}{\partial h_j}\alpha^{(2)}\right). \tag*{(93)} ∂ h j ∂ α ( 1 ) = A − 1 ( ∂ h j ∂ y − ∂ h j ∂ A α ( 1 ) ) , ∂ h j ∂ α ( 2 ) = A − 1 ( ∂ h j ∂ α ( 1 ) − ∂ h j ∂ A α ( 2 ) ) . (93) At h = 0 h=0 h = 0 A − 1 A^{-1} A − 1 K K K M ( p ) M^{(p)} M ( p ) M ( p ) K M^{(p)}K M ( p ) K A A A y y y
∂ 2 D ( σ w 2 ; y ) ∂ h i ∂ h j = ( A − 1 ) i j ( s i ( 1 ) s j ( 2 ) + s i ( 2 ) s j ( 1 ) − y i s j ( 2 ) − s i ( 2 ) y j ) + ( A − 2 ) i j ( s i ( 1 ) − y i ) ( s j ( 1 ) − y j ) + M i j ( 1 ) ( α i ( 1 ) s j ( 2 ) + s i ( 2 ) α j ( 1 ) + α i ( 2 ) s j ( 1 ) + s i ( 1 ) α j ( 2 ) − y i α j ( 2 ) − α i ( 2 ) y j ) + M i j ( 2 ) ( α i ( 1 ) ( s j ( 1 ) − y j ) + ( s i ( 1 ) − y i ) α j ( 1 ) ) + ( M ( 1 ) K ) i j ( α i ( 1 ) α j ( 2 ) + α i ( 2 ) α j ( 1 ) ) + ( M ( 2 ) K ) i j α i ( 1 ) α j ( 1 ) − ( 2 M i j ( 1 ) M i j ( 2 ) + ( A − 1 ) i j ( M ( 2 ) K ) i j + ( A − 2 ) i j ( M ( 1 ) K ) i j ) + K i j ( ( A − 2 ) i j − α i ( 1 ) α j ( 2 ) − α i ( 2 ) α j ( 1 ) ) . (94) \begin{aligned}
\frac{\partial^2D(\sigma_w^2;y)}{\partial h_i\partial h_j}
={}&(A^{-1})_{ij}\left(s_i^{(1)}s_j^{(2)}+s_i^{(2)}s_j^{(1)}-y_is_j^{(2)}-s_i^{(2)}y_j\right)
+(A^{-2})_{ij}(s_i^{(1)}-y_i)(s_j^{(1)}-y_j)\\
&+M_{ij}^{(1)}\left(\alpha_i^{(1)}s_j^{(2)}+s_i^{(2)}\alpha_j^{(1)}+\alpha_i^{(2)}s_j^{(1)}+s_i^{(1)}\alpha_j^{(2)}-y_i\alpha_j^{(2)}-\alpha_i^{(2)}y_j\right)\\
&+M_{ij}^{(2)}\left(\alpha_i^{(1)}(s_j^{(1)}-y_j)+(s_i^{(1)}-y_i)\alpha_j^{(1)}\right)
+(M^{(1)}K)_{ij}\left(\alpha_i^{(1)}\alpha_j^{(2)}+\alpha_i^{(2)}\alpha_j^{(1)}\right)\\
&+(M^{(2)}K)_{ij}\alpha_i^{(1)}\alpha_j^{(1)}
-\left(2M_{ij}^{(1)}M_{ij}^{(2)}+(A^{-1})_{ij}(M^{(2)}K)_{ij}+(A^{-2})_{ij}(M^{(1)}K)_{ij}\right)\\
&+K_{ij}\left((A^{-2})_{ij}-\alpha_i^{(1)}\alpha_j^{(2)}-\alpha_i^{(2)}\alpha_j^{(1)}\right). \tag*{(94)}
\end{aligned} ∂ h i ∂ h j ∂ 2 D ( σ w 2 ; y ) = ( A − 1 ) ij ( s i ( 1 ) s j ( 2 ) + s i ( 2 ) s j ( 1 ) − y i s j ( 2 ) − s i ( 2 ) y j ) + ( A − 2 ) ij ( s i ( 1 ) − y i ) ( s j ( 1 ) − y j ) + M ij ( 1 ) ( α i ( 1 ) s j ( 2 ) + s i ( 2 ) α j ( 1 ) + α i ( 2 ) s j ( 1 ) + s i ( 1 ) α j ( 2 ) − y i α j ( 2 ) − α i ( 2 ) y j ) + M ij ( 2 ) ( α i ( 1 ) ( s j ( 1 ) − y j ) + ( s i ( 1 ) − y i ) α j ( 1 ) ) + ( M ( 1 ) K ) ij ( α i ( 1 ) α j ( 2 ) + α i ( 2 ) α j ( 1 ) ) + ( M ( 2 ) K ) ij α i ( 1 ) α j ( 1 ) − ( 2 M ij ( 1 ) M ij ( 2 ) + ( A − 1 ) ij ( M ( 2 ) K ) ij + ( A − 2 ) ij ( M ( 1 ) K ) ij ) + K ij ( ( A − 2 ) ij − α i ( 1 ) α j ( 2 ) − α i ( 2 ) α j ( 1 ) ) . (94) Next, we express all terms in matrix vector notation to obtain the full Hessian matrix. Therefore, we used the following additional definitions
M ( p ) = K A − p , s ( p ) = K α ( p ) , T = ∂ D ( σ w 2 ; y ) ∂ σ w 2 . (95) M^{(p)} = KA^{-p},\quad s^{(p)} = K\alpha^{(p)},\quad T = \frac{\partial D(\sigma_w^2;y)}{\partial\sigma_w^2}. \tag*{(95)} M ( p ) = K A − p , s ( p ) = K α ( p ) , T = ∂ σ w 2 ∂ D ( σ w 2 ; y ) . (95) First, the gradient ∇ h σ w 2 \nabla_h\sigma_w^2 ∇ h σ w 2 (85) as
∇ h σ w 2 = 1 T ( − α ( 1 ) ⊙ s ( 2 ) − α ( 2 ) ⊙ s ( 1 ) + diag ( M ( 2 ) ) + y ⊙ α ( 2 ) ) . (96) \nabla_h\sigma_w^2 = \frac{1}{T}\left(-\alpha^{(1)}\mathbin{\odot}s^{(2)}-\alpha^{(2)}\mathbin{\odot}s^{(1)}+\operatorname{diag}(M^{(2)})+y\mathbin{\odot}\alpha^{(2)}\right). \tag*{(96)} ∇ h σ w 2 = T 1 ( − α ( 1 ) ⊙ s ( 2 ) − α ( 2 ) ⊙ s ( 1 ) + diag ( M ( 2 ) ) + y ⊙ α ( 2 ) ) . (96) Further, the mixed terms ∇ σ w 2 , h 2 D ( σ w 2 ; y ) \nabla^2_{\sigma_w^2,h}D(\sigma_w^2;y) ∇ σ w 2 , h 2 D ( σ w 2 ; y ) (88) simplify to
∇ σ w 2 , h 2 D ( σ w 2 ; y ) = − ( 2 α ( 2 ) ⊙ s ( 2 ) + 2 α ( 1 ) ⊙ s ( 3 ) + 2 α ( 3 ) ⊙ s ( 1 ) − 2 diag ( M ( 3 ) ) ) + 2 y ⊙ α ( 3 ) . (97) \nabla^2_{\sigma_w^2,h}D(\sigma_w^2;y)=-\left(2\alpha^{(2)}\mathbin{\odot}s^{(2)}+2\alpha^{(1)}\mathbin{\odot}s^{(3)}+2\alpha^{(3)}\mathbin{\odot}s^{(1)}-2\operatorname{diag}(M^{(3)})\right)+2y\mathbin{\odot}\alpha^{(3)}. \tag*{(97)} ∇ σ w 2 , h 2 D ( σ w 2 ; y ) = − ( 2 α ( 2 ) ⊙ s ( 2 ) + 2 α ( 1 ) ⊙ s ( 3 ) + 2 α ( 3 ) ⊙ s ( 1 ) − 2 diag ( M ( 3 ) ) ) + 2 y ⊙ α ( 3 ) . (97) And the term ∂ 2 D ( σ w 2 ; y ) ∂ h i ∂ h j \frac{\partial^2D(\sigma_w^2;y)}{\partial h_i\partial h_j} ∂ h i ∂ h j ∂ 2 D ( σ w 2 ; y ) (94) is given by
\begin{aligned}
\nabla_h^2D(\sigma_w^2;y)={}&A^{-1}\mathbin{\odot}\left(s^{(1)}s^{(2)\mathsf{T}}+s^{(2)}s^{(1)\mathsf{T}}-ys^{(2)\mathsf{T}}-s^{(2)}y^{\mathsf{T}}\right)\\
&+A^{-2}\mathbin{\odot}(s^{(1)}-y)(s^{(1)}-y)^{\mathsf{T}}+M^{(1)}\mathbin{\odot}\left(\alpha^{(1)}s^{(2)\mathsf{T}}+s^{(2)}\alpha^{(1)\mathsf{T}}\right.\\
&\left.+\alpha^{(2)}s^{(1)\mathsf{T}}+s^{(1)}\alpha^{(2)\mathsf{T}}-y\alpha^{(2)\mathsf{T}}-\alpha^{(2)}y^{\mathsf{T}}\right)+M^{(2)}\mathbin{\odot}\left(\alpha^{(1)}(s^{(1)}-y)^{\mathsf{T}}\\
&+(s^{(1)}-y)\alpha^{(1)\mathsf{T}}\right)+M^{(1)}K\mathbin{\odot}\left(\alpha^{(1)}\alpha^{(2)\mathsf{T}}+\alpha^{(2)}\alpha^{(1)\mathsf{T}}\right)\\
&+M^{(2)}K\mathbin{\odot}\alpha^{(1)}\alpha^{(1)\mathsf{T}}-\left(2M^{(1)}\mathbin{\odot}M^{(2)}+A^{-1}\mathbin{\odot}M^{(2)}K+A^{-2}\mathbin{\odot}M^{(1)}K\right)\\
&+K\mathbin{\odot}\left(A^{-2}-\alpha^{(1)}\alpha^{(2)\mathsf{T}}-\alpha^{(2)}\alpha^{(1)\mathsf{T}}\right). \tag*{(98)}
\end{aligned}
Finally, the last term as the gradient of the denominator ∇ σ w 2 T \nabla_{\sigma_w^2}T ∇ σ w 2 T
∇ σ w 2 T = 3 α ( 2 ) T α ( 2 ) − tr ( A − 3 ) + 2 ( a − 1 ) ( σ w 2 ) 3 . (99) \nabla_{\sigma_w^2}T=3\alpha^{(2)\mathsf{T}}\alpha^{(2)}-\operatorname{tr}(A^{-3})+\frac{2(a-1)}{(\sigma_w^2)^3}. \tag*{(99)} ∇ σ w 2 T = 3 α ( 2 ) T α ( 2 ) − tr ( A − 3 ) + ( σ w 2 ) 3 2 ( a − 1 ) . (99) So that we can write the final Hessian as
∇ h 2 σ w 2 = − 1 T ( ∇ h 2 D ( σ w 2 ; y ) + ∇ σ w 2 , h 2 D ( σ w 2 ; y ) ( ∇ h σ w 2 ) T + ∇ h σ w 2 ( ∇ σ w 2 , h 2 D ( σ w 2 ; y ) ) T + ∇ σ w 2 T ( ∇ h σ w 2 ) ( ∇ h σ w 2 ) T ) . (100) \begin{aligned}
\nabla_h^2\sigma_w^2={}&-\frac{1}{T}\left(\nabla_h^2D(\sigma_w^2;y)+\nabla^2_{\sigma_w^2,h}D(\sigma_w^2;y)(\nabla_h\sigma_w^2)^{\mathsf{T}}\right.\\
&\left.+\nabla_h\sigma_w^2(\nabla^2_{\sigma_w^2,h}D(\sigma_w^2;y))^{\mathsf{T}}+\nabla_{\sigma_w^2}T(\nabla_h\sigma_w^2)(\nabla_h\sigma_w^2)^{\mathsf{T}}\right). \tag*{(100)}
\end{aligned} ∇ h 2 σ w 2 = − T 1 ( ∇ h 2 D ( σ w 2 ; y ) + ∇ σ w 2 , h 2 D ( σ w 2 ; y ) ( ∇ h σ w 2 ) T + ∇ h σ w 2 ( ∇ σ w 2 , h 2 D ( σ w 2 ; y ) ) T + ∇ σ w 2 T ( ∇ h σ w 2 ) ( ∇ h σ w 2 ) T ) . (100) Lemma 4. Let S ⊆ X S\subseteq\mathcal{X} S ⊆ X x i ∈ S x_i\in S x i ∈ S − J ( S ) -J(S) − J ( S ) x i x_i x i k ( x , S , h i ) = k x , S − h i k ( x , x i ) e i k(x,S,h_i)=k_{x,S}-h_i k(x,x_i)e_i k ( x , S , h i ) = k x , S − h i k ( x , x i ) e i h i ∈ [ 0 , 1 ] h_i\in[0,1] h i ∈ [ 0 , 1 ] − J -J − J h = 0 h=0 h = 0
∇ h 2 − J ( S ) ∣ h = 0 = H e p i ( S ) + H a l e ( S ) , \nabla_h^2-J(S)\big|_{h=0}=H^{\mathrm{epi}}(S)+H^{\mathrm{ale}}(S), ∇ h 2 − J ( S ) h = 0 = H epi ( S ) + H ale ( S ) , where the epistemic and aleatoric Hessian contributions are given by
H e p i ( x ) = 8 ( σ w 2 ) 2 diag ( c x ) A − 1 diag ( c x ) − 6 σ w 2 diag ( c x ⊙ c x ) , H^{\mathrm{epi}}(x)=8(\sigma_w^2)^2\operatorname{diag}(c_x)A^{-1}\operatorname{diag}(c_x)-6\sigma_w^2\operatorname{diag}(c_x\mathbin{\odot}c_x), H epi ( x ) = 8 ( σ w 2 ) 2 diag ( c x ) A − 1 diag ( c x ) − 6 σ w 2 diag ( c x ⊙ c x ) , H a l e ( x ) = mix ( ∇ h σ w 2 ) T + ( ∇ h σ w 2 ) mix T + 2 ( c x ⋅ c x ′ ) ( ∇ h σ w 2 ) ( ∇ h σ w 2 ) T − ( ∥ c x ∥ 2 + 1 ) ∇ h 2 σ w 2 , H^{\mathrm{ale}}(x)=\operatorname{mix}(\nabla_h\sigma_w^2)^{\mathsf{T}}+(\nabla_h\sigma_w^2)\operatorname{mix}^{\mathsf{T}}+2(c_x\cdot c'_x)(\nabla_h\sigma_w^2)(\nabla_h\sigma_w^2)^{\mathsf{T}}-(\lVert c_x\rVert^2+1)\nabla_h^2\sigma_w^2, H ale ( x ) = mix ( ∇ h σ w 2 ) T + ( ∇ h σ w 2 ) mix T + 2 ( c x ⋅ c x ′ ) ( ∇ h σ w 2 ) ( ∇ h σ w 2 ) T − (∥ c x ∥ 2 + 1 ) ∇ h 2 σ w 2 , with ∇ h σ w 2 \nabla_h\sigma_w^2 ∇ h σ w 2 ∇ h 2 σ w 2 \nabla_h^2\sigma_w^2 ∇ h 2 σ w 2
mix = − ( 2 c x ′ ⊙ ( s x − k ( S , x ) ) + 2 s x ′ ⊙ c x ) , \operatorname{mix}=-\left(2c'_x\mathbin{\odot}(s_x-k(S,x))+2s'_x\mathbin{\odot}c_x\right), mix = − ( 2 c x ′ ⊙ ( s x − k ( S , x )) + 2 s x ′ ⊙ c x ) , and the following abbreviations
c x = A − 1 k ( S , x ) , c x ′ = A − 2 k ( S , x ) , s x = K c x , s x ′ = K c x ′ . c_x=A^{-1}k(S,x),\quad c'_x=A^{-2}k(S,x),\quad s_x=Kc_x,\quad s'_x=Kc'_x. c x = A − 1 k ( S , x ) , c x ′ = A − 2 k ( S , x ) , s x = K c x , s x ′ = K c x ′ . For a multi-point target region, the Hessians H e p i ( S ) H^{\mathrm{epi}}(S) H epi ( S ) H a l e ( S ) H^{\mathrm{ale}}(S) H ale ( S )
Proof. We begin by revisiting the derivative of the negated objective function in Lemma 2
∂ − J ( S ) ∂ h i = − 2 k ( x , x i ) ( c x ) i + 2 ( c x ) i ( k x i , S c x ) − ( ∥ c x ∥ 2 + 1 ) ∂ σ w 2 ∂ h i . (101) \frac{\partial-\mathcal{J}(\mathcal{S})}{\partial h_i}=-2k(x,x_i)(c_x)_i+2(c_x)_i(k_{x_i,\mathcal{S}}c_x)-(\lVert c_x\rVert^2+1)\frac{\partial\sigma_w^2}{\partial h_i}. \tag*{(101)} ∂ h i ∂ − J ( S ) = − 2 k ( x , x i ) ( c x ) i + 2 ( c x ) i ( k x i , S c x ) − (∥ c x ∥ 2 + 1 ) ∂ h i ∂ σ w 2 . (101) We first derive the epistemic part, corresponding to the negative of the epistemic influence u i ( x ) u_i(x) u i ( x ) s = σ w 2 s=\sigma_w^2 s = σ w 2
∂ F ∂ h i ∣ h = 0 , s = − 2 k ( x , x i ) ( c x ) i + 2 ( c x ) i ( k x i , S c x ) = − 2 σ w 2 ( c x ) i 2 = − u i ( x ) , (102) \left.\frac{\partial F}{\partial h_i}\right|_{h=0,s}=-2k(x,x_i)(c_x)_i+2(c_x)_i(k_{x_i,\mathcal{S}}c_x)=-2\sigma_w^2(c_x)_i^2=-u_i(x), \tag*{(102)} ∂ h i ∂ F h = 0 , s = − 2 k ( x , x i ) ( c x ) i + 2 ( c x ) i ( k x i , S c x ) = − 2 σ w 2 ( c x ) i 2 = − u i ( x ) , (102) where we used K c x − k ( S , x ) = − σ w 2 c x Kc_x-k(\mathcal{S},x)=-\sigma_w^2c_x K c x − k ( S , x ) = − σ w 2 c x P ( h ) = diag ( 1 − h ) P(h)=\operatorname{diag}(1-h) P ( h ) = diag ( 1 − h ) h = 0 h=0 h = 0 P ( h ) P(h) P ( h )
F ( h , s ) = k ( x , S ) P ( h ) ( P ( h ) K P ( h ) + s I ) − 1 P ( h ) k ( S , x ) = k ( x , S ) ( K + s P ( h ) − 2 ) − 1 k ( S , x ) . (103) \begin{aligned}
F(h,s)&=k(x,\mathcal{S})P(h)\left(P(h)KP(h)+sI\right)^{-1}P(h)k(\mathcal{S},x)\\
&=k(x,\mathcal{S})\left(K+sP(h)^{-2}\right)^{-1}k(\mathcal{S},x). \tag*{(103)}
\end{aligned} F ( h , s ) = k ( x , S ) P ( h ) ( P ( h ) K P ( h ) + s I ) − 1 P ( h ) k ( S , x ) = k ( x , S ) ( K + s P ( h ) − 2 ) − 1 k ( S , x ) . (103) Writing Q ( h , s ) = K + s P ( h ) − 2 Q(h,s)=K+sP(h)^{-2} Q ( h , s ) = K + s P ( h ) − 2 h = 0 h=0 h = 0
∂ Q ∂ h i = 2 s e i e i T , ∂ 2 Q ∂ h i ∂ h j = 6 s 1 { i = j } e i e i T . (104) \frac{\partial Q}{\partial h_i}=2s e_i e_i^{\mathsf{T}},\qquad\frac{\partial^2Q}{\partial h_i\partial h_j}=6s\mathbf{1}_{\{i=j\}}e_i e_i^{\mathsf{T}}. \tag*{(104)} ∂ h i ∂ Q = 2 s e i e i T , ∂ h i ∂ h j ∂ 2 Q = 6 s 1 { i = j } e i e i T . (104) By differentiating F ( h , s ) = k ( x , S ) Q ( h , s ) − 1 k ( S , x ) F(h,s)=k(x,\mathcal{S})Q(h,s)^{-1}k(\mathcal{S},x) F ( h , s ) = k ( x , S ) Q ( h , s ) − 1 k ( S , x )
∂ 2 F ∂ h i ∂ h j ∣ h = 0 , s = 8 s 2 ( c x ) i ( A − 1 ) i j ( c x ) j − 6 s 1 { i = j } ( c x ) i 2 . (105) \left.\frac{\partial^2F}{\partial h_i\partial h_j}\right|_{h=0,s}=8s^2(c_x)_i(A^{-1})_{ij}(c_x)_j-6s\mathbf{1}_{\{i=j\}}(c_x)_i^2. \tag*{(105)} ∂ h i ∂ h j ∂ 2 F h = 0 , s = 8 s 2 ( c x ) i ( A − 1 ) ij ( c x ) j − 6 s 1 { i = j } ( c x ) i 2 . (105) Therefore, in matrix form,
H e p i ( x ) = 8 ( σ w 2 ) 2 diag ( c x ) A − 1 diag ( c x ) − 6 σ w 2 diag ( c x ⊙ c x ) . (106) H^{\mathrm{epi}}(x)=8(\sigma_w^2)^2\operatorname{diag}(c_x)A^{-1}\operatorname{diag}(c_x)-6\sigma_w^2\operatorname{diag}(c_x\odot c_x). \tag*{(106)} H epi ( x ) = 8 ( σ w 2 ) 2 diag ( c x ) A − 1 diag ( c x ) − 6 σ w 2 diag ( c x ⊙ c x ) . (106) For the aleatoric term, we write the negated objective as − J = F ( h , σ w 2 ( h ) ) − σ w 2 ( h ) -\mathcal{J}=F(h,\sigma_w^2(h))-\sigma_w^2(h) − J = F ( h , σ w 2 ( h )) − σ w 2 ( h ) F ( h , s ) = k ( h ) T ( K ( h ) + s I ) − 1 k ( h ) F(h,s)=k(h)^{\mathsf{T}}(K(h)+sI)^{-1}k(h) F ( h , s ) = k ( h ) T ( K ( h ) + s I ) − 1 k ( h )
∂ 2 ( − J ) ∂ h i ∂ h j = ∂ 2 F ∂ h i ∂ h j ∣ s + ∂ 2 F ∂ s ∂ h j g i + ∂ 2 F ∂ s ∂ h i g j + ∂ 2 F ∂ s 2 g i g j − ( ∥ c x ∥ 2 + 1 ) H σ [ i , j ] , (107) \frac{\partial^2(-\mathcal{J})}{\partial h_i\partial h_j}=\left.\frac{\partial^2F}{\partial h_i\partial h_j}\right|_s+\frac{\partial^2F}{\partial s\partial h_j}g_i+\frac{\partial^2F}{\partial s\partial h_i}g_j+\frac{\partial^2F}{\partial s^2}g_ig_j-(\lVert c_x\rVert^2+1)H_\sigma[i,j], \tag*{(107)} ∂ h i ∂ h j ∂ 2 ( − J ) = ∂ h i ∂ h j ∂ 2 F s + ∂ s ∂ h j ∂ 2 F g i + ∂ s ∂ h i ∂ 2 F g j + ∂ s 2 ∂ 2 F g i g j − (∥ c x ∥ 2 + 1 ) H σ [ i , j ] , (107) where g = ∇ h σ w 2 g=\nabla_h\sigma_w^2 g = ∇ h σ w 2 H σ = ∇ h 2 σ w 2 H_\sigma=\nabla_h^2\sigma_w^2 H σ = ∇ h 2 σ w 2 ∂ F ∂ s = − ∥ c x ∥ 2 \frac{\partial F}{\partial s}=-\lVert c_x\rVert^2 ∂ s ∂ F = − ∥ c x ∥ 2 H e p i H^{\mathrm{epi}} H epi ∂ F ∂ h j ∣ h = 0 , s = − u j ( x ) \left.\frac{\partial F}{\partial h_j}\right|_{h=0,s}=-u_j(x) ∂ h j ∂ F h = 0 , s = − u j ( x ) s s s ∂ c x ∂ s = − c x ′ \frac{\partial c_x}{\partial s}=-c_x' ∂ s ∂ c x = − c x ′ ∂ s x , j ∂ s = − s x , j ′ \frac{\partial s_{x,j}}{\partial s}=-s_{x,j}' ∂ s ∂ s x , j = − s x , j ′
∂ 2 F ∂ s ∂ h j = − ∂ u j ∂ s = − 2 c x , j ′ ( s x , j − k ( S , x ) j ) − 2 c x , j s x , j ′ = mix j . (108) \frac{\partial^2F}{\partial s\partial h_j}=-\frac{\partial u_j}{\partial s}=-2c_{x,j}'(s_{x,j}-k(\mathcal{S},x)_j)-2c_{x,j}s_{x,j}'=\operatorname{mix}_j. \tag*{(108)} ∂ s ∂ h j ∂ 2 F = − ∂ s ∂ u j = − 2 c x , j ′ ( s x , j − k ( S , x ) j ) − 2 c x , j s x , j ′ = mix j . (108) The pure s s s F F F
∂ 2 F ∂ s 2 = 2 k ( S , x ) T A − 3 k ( S , x ) = 2 c x ⋅ c x ′ . (109) \frac{\partial^2F}{\partial s^2}=2k(\mathcal{S},x)^{\mathsf{T}}A^{-3}k(\mathcal{S},x)=2c_x\cdot c_x'. \tag*{(109)} ∂ s 2 ∂ 2 F = 2 k ( S , x ) T A − 3 k ( S , x ) = 2 c x ⋅ c x ′ . (109) Collecting these contributions yields the aleatoric Hessian term
H a l e = mix ( ∇ h σ w 2 ) T + ( ∇ h σ w 2 ) mix T + 2 ( c x ⋅ c x ′ ) ( ∇ h σ w 2 ) ( ∇ h σ w 2 ) T − ( ∥ c x ∥ 2 + 1 ) ∇ h 2 σ w 2 . (110) H^{\mathrm{ale}}=\operatorname{mix}(\nabla_h\sigma_w^2)^{\mathsf{T}}+(\nabla_h\sigma_w^2)\operatorname{mix}^{\mathsf{T}}+2(c_x\cdot c_x')(\nabla_h\sigma_w^2)(\nabla_h\sigma_w^2)^{\mathsf{T}}-(\lVert c_x\rVert^2+1)\nabla_h^2\sigma_w^2. \tag*{(110)} H ale = mix ( ∇ h σ w 2 ) T + ( ∇ h σ w 2 ) mix T + 2 ( c x ⋅ c x ′ ) ( ∇ h σ w 2 ) ( ∇ h σ w 2 ) T − (∥ c x ∥ 2 + 1 ) ∇ h 2 σ w 2 . (110) Lemma 5. Let H ( S ( k ) ) = H e p i ( S ( k ) ) + H a l e ( S ( k ) ) H(\mathcal{S}^{(k)})=H^{\mathrm{epi}}(\mathcal{S}^{(k)})+H^{\mathrm{ale}}(\mathcal{S}^{(k)}) H ( S ( k ) ) = H epi ( S ( k ) ) + H ale ( S ( k ) ) − J -\mathcal{J} − J S ( k ) \mathcal{S}^{(k)} S ( k ) k k k T ( k ) ⊆ T : = S ∖ S ′ ⊆ R T^{(k)}\subseteq T:=\mathcal{S}\setminus\mathcal{S}'\subseteq R T ( k ) ⊆ T := S ∖ S ′ ⊆ R H R ( S ( k ) ) H_R(\mathcal{S}^{(k)}) H R ( S ( k ) ) H ( S ( k ) ) H(\mathcal{S}^{(k)}) H ( S ( k ) ) R R R
m R : = inf S ( k ) λ min ( − H R ( S ( k ) ) ) , M R : = sup S ( k ) λ max ( − H R ( S ( k ) ) ) , m_R:=\inf_{\mathcal{S}^{(k)}}\lambda_{\min}(-H_R(\mathcal{S}^{(k)})),\qquad M_R:=\sup_{\mathcal{S}^{(k)}}\lambda_{\max}(-H_R(\mathcal{S}^{(k)})), m R := S ( k ) inf λ m i n ( − H R ( S ( k ) )) , M R := S ( k ) sup λ m a x ( − H R ( S ( k ) )) , such that for all S ( k ) \mathcal{S}^{(k)} S ( k ) T ( k ) ⊆ T ⊆ R T^{(k)}\subseteq T\subseteq R T ( k ) ⊆ T ⊆ R H R ( S ( k ) ) H_R(\mathcal{S}^{(k)}) H R ( S ( k ) )
− M R I ≤ H R ( S ( k ) ) ≤ − m R I . -M_RI\leq H_R(\mathcal{S}^{(k)})\leq-m_RI. − M R I ≤ H R ( S ( k ) ) ≤ − m R I . Proof. By definition of m R m_R m R M R M_R M R S ( k ) ⊆ S ′ \mathcal{S}^{(k)} \subseteq\mathcal{S}' S ( k ) ⊆ S ′ H R ( S ( k ) ) H_R(\mathcal{S}^{(k)}) H R ( S ( k ) )
− M R I ≤ H R ( S ( k ) ) ≤ − m R I , (111) -M_R I \leq H_R(\mathcal{S}^{(k)}) \leq-m_R I, \tag*{(111)} − M R I ≤ H R ( S ( k ) ) ≤ − m R I , (111) which is precisely the final criterion in Lemma 5.
It remains to show that this criterion implies restricted strong concavity and smoothness (RSC/RSM). Let L ⊂ L ∪ U ⊆ R L \subset L \cup U \subseteq R L ⊂ L ∪ U ⊆ R h h h U U U L L L h h h U ⊆ R U \subseteq R U ⊆ R h T H ( S ( k ) ) h = h T H R ( S ( k ) ) h h^{\mathsf{T}}H(\mathcal{S}^{(k)})h = h^{\mathsf{T}}H_R(\mathcal{S}^{(k)})h h T H ( S ( k ) ) h = h T H R ( S ( k ) ) h (111) therefore says that − J ˉ -\bar{J} − J ˉ R R R m R m_R m R M R M_R M R [53 Lemma 1.2.3] , this is equal to
− M R 2 ∥ h ∥ 2 2 ≤ J ˉ ( L ∪ U ) − J ˉ ( L ) − ⟨ ∇ J ˉ ( L ) , h ⟩ ≤ − m R 2 ∥ h ∥ 2 2 , (112) -\frac{M_R}{2}\lVert h\rVert_2^2 \leq\bar{J}(L \cup U) - \bar{J}(L) - \langle\nabla\bar{J}(L), h\rangle\leq-\frac{m_R}{2}\lVert h\rVert_2^2, \tag*{(112)} − 2 M R ∥ h ∥ 2 2 ≤ J ˉ ( L ∪ U ) − J ˉ ( L ) − ⟨ ∇ J ˉ ( L ) , h ⟩ ≤ − 2 m R ∥ h ∥ 2 2 , (112) which is the RSC/RSM condition for the outer objective.
Lemma 6. Let K K K λ i ( K ) \lambda_i(K) λ i ( K ) ∥ y ∥ 2 2 \lVert y\rVert_2^2 ∥ y ∥ 2 2 p ( σ w 2 ( S ) ∣ a , b ) = b a Γ ( a ) ( σ w 2 ( S ) ) a − 1 e − b σ w 2 ( S ) p(\sigma_w^2(\mathcal{S})\mid a,b) = \frac{b^a}{\Gamma(a)}(\sigma_w^2(\mathcal{S}))^{a-1}e^{-b\sigma_w^2(\mathcal{S})} p ( σ w 2 ( S ) ∣ a , b ) = Γ ( a ) b a ( σ w 2 ( S ) ) a − 1 e − b σ w 2 ( S ) b > 0 b > 0 b > 0 a a a σ w 2 ∈ [ ξ min , ξ max ] \sigma_w^2 \in[\xi_{\min},\xi_{\max}] σ w 2 ∈ [ ξ m i n , ξ m a x ] 0 < ξ min < ξ max 0 < \xi_{\min} < \xi_{\max} 0 < ξ m i n < ξ m a x
a > 1 + 1 2 ∑ i = 1 ∣ S ∣ ( ξ max λ i ( K ) + ξ max ) 2 − ξ min 2 ∥ y ∥ 2 2 ( λ max ( K ) + ξ max ) 3 . (113) a > 1 + \frac{1}{2}\sum_{i=1}^{|\mathcal{S}|}\left(\frac{\xi_{\max}}{\lambda_i(K)+\xi_{\max}}\right)^2 - \frac{\xi_{\min}^2\lVert y\rVert_2^2}{(\lambda_{\max}(K)+\xi_{\max})^3}. \tag*{(113)} a > 1 + 2 1 i = 1 ∑ ∣ S ∣ ( λ i ( K ) + ξ m a x ξ m a x ) 2 − ( λ m a x ( K ) + ξ m a x ) 3 ξ m i n 2 ∥ y ∥ 2 2 . (113) Then the noise log MAP II objective L ( σ w 2 , S , a , b ) \mathcal{L}(\sigma_w^2,\mathcal{S},a,b) L ( σ w 2 , S , a , b ) [ ξ min , ξ max ] [\xi_{\min},\xi_{\max}] [ ξ m i n , ξ m a x ] D ( σ w 2 , S , a , b ) = 0 \mathcal{D}(\sigma_w^2,\mathcal{S},a,b)=0 D ( σ w 2 , S , a , b ) = 0 T < 0 T<0 T < 0
Proof. We consider the second derivative of the log MAP II objective w.r.t. the noise parameter, which is given by
∂ 2 L ( σ w 2 , S , a , b ) ∂ ( σ w 2 ) 2 = − y T A − 3 y + 1 2 tr ( A − 2 ) − a − 1 ( σ w 2 ) 2 , (114) \frac{\partial^2\mathcal{L}(\sigma_w^2,\mathcal{S},a,b)}{\partial(\sigma_w^2)^2}=-y^{\mathsf{T}}A^{-3}y+\frac{1}{2}\operatorname{tr}(A^{-2})-\frac{a-1}{(\sigma_w^2)^2}, \tag*{(114)} ∂ ( σ w 2 ) 2 ∂ 2 L ( σ w 2 , S , a , b ) = − y T A − 3 y + 2 1 tr ( A − 2 ) − ( σ w 2 ) 2 a − 1 , (114) where A = K + σ w 2 I A=K+\sigma_w^2I A = K + σ w 2 I
a > 1 + ( σ w 2 ) 2 ( 1 2 tr ( A − 2 ) − y T A − 3 y ) . (115) a>1+(\sigma_w^2)^2\left(\frac{1}{2}\operatorname{tr}(A^{-2})-y^{\mathsf{T}}A^{-3}y\right). \tag*{(115)} a > 1 + ( σ w 2 ) 2 ( 2 1 tr ( A − 2 ) − y T A − 3 y ) . (115) We now upper bound the right-hand side uniformly for σ w 2 ∈ [ ξ min , ξ max ] \sigma_w^2\in[\xi_{\min},\xi_{\max}] σ w 2 ∈ [ ξ m i n , ξ m a x ] K K K
( σ w 2 ) 2 tr ( A − 2 ) = ∑ i = 1 ∣ S ∣ ( σ w 2 λ i ( K ) + σ w 2 ) 2 ≤ ∑ i = 1 ∣ S ∣ ( ξ max λ i ( K ) + ξ max ) 2 . (116) (\sigma_w^2)^2\operatorname{tr}(A^{-2})=\sum_{i=1}^{|\mathcal{S}|}\left(\frac{\sigma_w^2}{\lambda_i(K)+\sigma_w^2}\right)^2\leq\sum_{i=1}^{|\mathcal{S}|}\left(\frac{\xi_{\max}}{\lambda_i(K)+\xi_{\max}}\right)^2. \tag*{(116)} ( σ w 2 ) 2 tr ( A − 2 ) = i = 1 ∑ ∣ S ∣ ( λ i ( K ) + σ w 2 σ w 2 ) 2 ≤ i = 1 ∑ ∣ S ∣ ( λ i ( K ) + ξ m a x ξ m a x ) 2 . (116) Moreover, λ max ( A ) ≤ λ max ( K ) + ξ max \lambda_{\max}(A)\leq\lambda_{\max}(K)+\xi_{\max} λ m a x ( A ) ≤ λ m a x ( K ) + ξ m a x
( σ w 2 ) 2 y T A − 3 y ≥ ( σ w 2 ) 2 ∥ y ∥ 2 2 ( λ max ( K ) + ξ max ) 3 ≥ ξ min 2 ∥ y ∥ 2 2 ( λ max ( K ) + ξ max ) 3 . (117) (\sigma_w^2)^2y^{\mathsf{T}}A^{-3}y\geq\frac{(\sigma_w^2)^2\lVert y\rVert_2^2}{(\lambda_{\max}(K)+\xi_{\max})^3}\geq\frac{\xi_{\min}^2\lVert y\rVert_2^2}{(\lambda_{\max}(K)+\xi_{\max})^3}. \tag*{(117)} ( σ w 2 ) 2 y T A − 3 y ≥ ( λ m a x ( K ) + ξ m a x ) 3 ( σ w 2 ) 2 ∥ y ∥ 2 2 ≥ ( λ m a x ( K ) + ξ m a x ) 3 ξ m i n 2 ∥ y ∥ 2 2 . (117) Combining both bounds yields
( σ w 2 ) 2 ( 1 2 tr ( A − 2 ) − y T A − 3 y ) ≤ 1 2 ∑ i = 1 ∣ S ∣ ( ξ max λ i ( K ) + ξ max ) 2 − ξ min 2 ∥ y ∥ 2 2 ( λ max ( K ) + ξ max ) 3 . (118) (\sigma_w^2)^2\left(\frac{1}{2}\operatorname{tr}(A^{-2})-y^{\mathsf{T}}A^{-3}y\right)\leq\frac{1}{2}\sum_{i=1}^{|\mathcal{S}|}\left(\frac{\xi_{\max}}{\lambda_i(K)+\xi_{\max}}\right)^2-\frac{\xi_{\min}^2\lVert y\rVert_2^2}{(\lambda_{\max}(K)+\xi_{\max})^3}. \tag*{(118)} ( σ w 2 ) 2 ( 2 1 tr ( A − 2 ) − y T A − 3 y ) ≤ 2 1 i = 1 ∑ ∣ S ∣ ( λ i ( K ) + ξ m a x ξ m a x ) 2 − ( λ m a x ( K ) + ξ m a x ) 3 ξ m i n 2 ∥ y ∥ 2 2 . (118) Thus, the condition in the lemma implies ∂ 2 L ∂ ( σ w 2 ) 2 < 0 \frac{\partial^2\mathcal{L}}{\partial(\sigma_w^2)^2}<0 ∂ ( σ w 2 ) 2 ∂ 2 L < 0 T = ∂ 2 L ∂ ( σ w 2 ) 2 < 0 T=\frac{\partial^2\mathcal{L}}{\partial(\sigma_w^2)^2}<0 T = ∂ ( σ w 2 ) 2 ∂ 2 L < 0
Lemma 7. Suppose that the negated objective − J ( ⋅ ) -\mathcal{J}(\cdot) − J ( ⋅ ) T T T T T T
J ( S ∖ L ) − J ( S ∖ ( L ∪ U ) ) ≤ 1 2 m R ∥ ∇ − J ( S ∖ L ) U ∥ 2 2 \mathcal{J}(S \setminus L) - \mathcal{J}(S \setminus(L \cup U)) \le\frac{1}{2m_R}\lVert\nabla-\mathcal{J}(S \setminus L)_U \rVert_2^2 J ( S ∖ L ) − J ( S ∖ ( L ∪ U )) ≤ 2 m R 1 ∥ ∇ − J ( S ∖ L ) U ∥ 2 2 where the sets satisfy L ⊂ L ∪ U ⊆ T L \subset L \cup U \subseteq T L ⊂ L ∪ U ⊆ T
Proof. Let us begin with the restricted strong concavity criterion
− m R 2 ∥ h ∥ 2 2 ≥ J ( S ∖ L ) − J ( S ∖ ( L ∪ U ) ) − ⟨ ∇ − J ( S ∖ L ) , h ⟩ . (119) -\frac{m_R}{2}\lVert h\rVert_2^2 \ge\mathcal{J}(S \setminus L) - \mathcal{J}(S \setminus(L \cup U)) - \langle\nabla-\mathcal{J}(S \setminus L), h\rangle. \tag*{(119)} − 2 m R ∥ h ∥ 2 2 ≥ J ( S ∖ L ) − J ( S ∖ ( L ∪ U )) − ⟨ ∇ − J ( S ∖ L ) , h ⟩ . (119) By bringing the inner product of the gradient to the other side, we obtain
⟨ ∇ − J ( S ∖ L ) , h ⟩ − m R 2 ∥ h ∥ 2 2 ≥ J ( S ∖ L ) − J ( S ∖ ( L ∪ U ) ) , (120) \langle\nabla-\mathcal{J}(S \setminus L), h\rangle- \frac{m_R}{2}\lVert h\rVert_2^2 \ge\mathcal{J}(S \setminus L) - \mathcal{J}(S \setminus(L \cup U)), \tag*{(120)} ⟨ ∇ − J ( S ∖ L ) , h ⟩ − 2 m R ∥ h ∥ 2 2 ≥ J ( S ∖ L ) − J ( S ∖ ( L ∪ U )) , (120) which we can further upper bound by the best possible subset
max h ⟨ ∇ − J ( S ∖ L ) , h ⟩ − m R 2 ∥ h ∥ 2 2 ≥ J ( S ∖ L ) − J ( S ∖ ( L ∪ U ) ) . (121) \max_h \langle\nabla-\mathcal{J}(S \setminus L), h\rangle- \frac{m_R}{2}\lVert h\rVert_2^2 \ge\mathcal{J}(S \setminus L) - \mathcal{J}(S \setminus(L \cup U)). \tag*{(121)} h max ⟨ ∇ − J ( S ∖ L ) , h ⟩ − 2 m R ∥ h ∥ 2 2 ≥ J ( S ∖ L ) − J ( S ∖ ( L ∪ U )) . (121) The unrestricted quadratic expression in the variable z z z U U U z = 1 m R ∇ ( − J ) U z = \frac{1}{m_R}\nabla(-\mathcal{J})_U z = m R 1 ∇ ( − J ) U ∥ ∇ ( − J ) U ∥ 2 2 1 2 m R \lVert\nabla(-\mathcal{J})_U\rVert_2^2\frac{1}{2m_R} ∥ ∇ ( − J ) U ∥ 2 2 2 m R 1
J ( S ∖ L ) − J ( S ∖ ( L ∪ U ) ) ≤ 1 2 m R ∥ ∇ − J ( S ∖ L ) U ∥ 2 2 (122) \mathcal{J}(S \setminus L) - \mathcal{J}(S \setminus(L \cup U)) \le\frac{1}{2m_R}\lVert\nabla-\mathcal{J}(S \setminus L)_U\rVert_2^2 \tag*{(122)} J ( S ∖ L ) − J ( S ∖ ( L ∪ U )) ≤ 2 m R 1 ∥ ∇ − J ( S ∖ L ) U ∥ 2 2 (122) Lemma 8. Suppose the conditions of Theorem 1 hold, and let T k = S ∖ S ( k ) T_k = S \setminus S^{(k)} T k = S ∖ S ( k ) k = 0 , … , q k = 0, \ldots, q k = 0 , … , q k < q k < q k < q
J ˉ ( T k + 1 ) − J ˉ ( T k ) ≥ ρ m R q M R [ U q − J ˉ ( T k ) ] + . (123) \bar{\mathcal{J}}(T_{k+1}) - \bar{\mathcal{J}}(T_k) \ge\frac{\rho m_R}{qM_R}[U_q - \bar{\mathcal{J}}(T_k)]_+. \tag*{(123)} J ˉ ( T k + 1 ) − J ˉ ( T k ) ≥ q M R ρ m R [ U q − J ˉ ( T k ) ] + . (123) Proof. By the definition of the realization coefficient in Assumption 1, the actual improvement from the k k k
J ˉ ( T k + 1 ) − J ˉ ( T k ) = J ( S ( k ) ) − J ( S ( k + 1 ) ) (124) \bar{\mathcal{J}}(T_{k+1}) - \bar{\mathcal{J}}(T_k) = \mathcal{J}(S^{(k)}) - \mathcal{J}(S^{(k+1)}) \tag*{(124)} J ˉ ( T k + 1 ) − J ˉ ( T k ) = J ( S ( k ) ) − J ( S ( k + 1 ) ) (124) = ρ k 2 M R ∥ u ( k ) ( A ) + v ( k ) ( A ) ∥ ∞ 2 (125) = \frac{\rho_k}{2M_R}\lVert u^{(k)}(A) + v^{(k)}(A)\rVert_\infty^2 \tag*{(125)} = 2 M R ρ k ∥ u ( k ) ( A ) + v ( k ) ( A ) ∥ ∞ 2 (125) ≥ ρ m R q M R [ U q − J ˉ ( T k ) ] + , (126) \ge\frac{\rho m_R}{qM_R}[U_q - \bar{\mathcal{J}}(T_k)]_+, \tag*{(126)} ≥ q M R ρ m R [ U q − J ˉ ( T k ) ] + , (126) where the last step follows from Assumption 1 and ρ k ≥ ρ \rho_k \ge\rho ρ k ≥ ρ
Theorem 1. Let J ˉ ( T ) = J ( S ) − J ( S ∖ T ) \bar{\mathcal{J}}(T) = \mathcal{J}(S) - \mathcal{J}(S \setminus T) J ˉ ( T ) = J ( S ) − J ( S ∖ T ) T ′ = S ∖ S ′ T' = S \setminus S' T ′ = S ∖ S ′ q ≥ 1 q \ge1 q ≥ 1 σ w 2 \sigma_w^2 σ w 2 − J -\mathcal{J} − J m R m_R m R L = ∅ L = \varnothing L = ∅ U ⊆ S U \subseteq S U ⊆ S ∣ U ∣ = q |U| = q ∣ U ∣ = q
J ˉ ( T ′ ) ≥ ( 1 − e − γ ) max T ∗ ⊆ S ∣ T ∗ ∣ = ∣ T ′ ∣ J ˉ ( T ∗ ) , γ = ρ m R M R , \bar{\mathcal{J}}(T') \ge(1-e^{-\gamma})\max_{\substack{T^* \subseteq S\\ |T^*|=|T'|}}\bar{\mathcal{J}}(T^*), \qquad\gamma= \rho\frac{m_R}{M_R}, J ˉ ( T ′ ) ≥ ( 1 − e − γ ) T ∗ ⊆ S ∣ T ∗ ∣ = ∣ T ′ ∣ max J ˉ ( T ∗ ) , γ = ρ M R m R , for the restricted smoothness M R > 0 M_R > 0 M R > 0 ρ = min 0 ≤ k < q 2 M R [ J ( S ( k ) ) − J ( S ( k + 1 ) ) ] ∥ u ( k ) ( A ) + v ( k ) ( A ) ∥ ∞ 2 > 0 \rho= \min_{0 \le k < q}\frac{2M_R[\mathcal{J}(S^{(k)})-\mathcal{J}(S^{(k+1)})]}{\lVert u^{(k)}(A)+v^{(k)}(A)\rVert_\infty^2} > 0 ρ = min 0 ≤ k < q ∥ u ( k ) ( A ) + v ( k ) ( A ) ∥ ∞ 2 2 M R [ J ( S ( k ) ) − J ( S ( k + 1 ) )] > 0
Proof. Let T ∗ T^* T ∗ ∣ T ∗ ∣ = q |T^*| = q ∣ T ∗ ∣ = q L = ∅ L = \varnothing L = ∅ U = T ∗ U = T^* U = T ∗
J ˉ ( T ∗ ) ≤ ∑ i ∈ T ∗ g i ( 0 ) − m R q 2 (127) \bar{\mathcal{J}}(T^*) \le\sum_{i \in T^*} g_i^{(0)} - \frac{m_R q}{2} \tag*{(127)} J ˉ ( T ∗ ) ≤ i ∈ T ∗ ∑ g i ( 0 ) − 2 m R q (127) ≤ ∑ i = 1 q g ( i ) ( 0 ) − m R q 2 . (128) \le\sum_{i=1}^{q} g_{(i)}^{(0)} - \frac{m_R q}{2}. \tag*{(128)} ≤ i = 1 ∑ q g ( i ) ( 0 ) − 2 m R q . (128) Since J ( S ∖ T ∗ ) ≥ 0 \mathcal{J}(S \setminus T^*) \ge0 J ( S ∖ T ∗ ) ≥ 0 J ˉ ( T ∗ ) ≤ J ( S ) \bar{\mathcal{J}}(T^*) \le\mathcal{J}(S) J ˉ ( T ∗ ) ≤ J ( S )
J ˉ ( T ∗ ) ≤ U q . (129) \bar{\mathcal{J}}(T^*) \le U_q. \tag*{(129)} J ˉ ( T ∗ ) ≤ U q . (129) By ρ > 0 \rho> 0 ρ > 0 J ˉ ( T k ) ≤ J ˉ ( T ′ ) ≤ J ˉ ( T ∗ ) ≤ U q \bar{\mathcal{J}}(T_k) \le\bar{\mathcal{J}}(T') \le\bar{\mathcal{J}}(T^*) \le U_q J ˉ ( T k ) ≤ J ˉ ( T ′ ) ≤ J ˉ ( T ∗ ) ≤ U q k ≤ q k \le q k ≤ q G k = U q − J ˉ ( T k ) ≥ 0 G_k = U_q - \bar{\mathcal{J}}(T_k) \ge0 G k = U q − J ˉ ( T k ) ≥ 0 c = ρ m R / ( q M R ) > 0 c = \rho m_R/(qM_R) > 0 c = ρ m R / ( q M R ) > 0 (123) ,
G k + 1 ≤ ( 1 − c ) G k . (130) G_{k+1} \le(1-c)G_k. \tag*{(130)} G k + 1 ≤ ( 1 − c ) G k . (130) Since ρ > 0 \rho> 0 ρ > 0 q ≥ 1 q \ge1 q ≥ 1 U q ≥ J ˉ ( T ∗ ) ≥ J ˉ ( T ′ ) > 0 U_q \ge\bar{\mathcal{J}}(T^*) \ge\bar{\mathcal{J}}(T') > 0 U q ≥ J ˉ ( T ∗ ) ≥ J ˉ ( T ′ ) > 0 G 0 > 0 G_0 > 0 G 0 > 0 G 1 ≥ 0 G_1 \ge0 G 1 ≥ 0 0 < c ≤ 1 0 < c \le1 0 < c ≤ 1 T 0 = ∅ T_0 = \varnothing T 0 = ∅ J ˉ ( T 0 ) = 0 \bar{\mathcal{J}}(T_0) = 0 J ˉ ( T 0 ) = 0
G q ≤ ( 1 − c ) q U q ≤ e − c q U q = e − γ U q . (131) G_q \le(1-c)^q U_q \le e^{-cq}U_q = e^{-\gamma}U_q. \tag*{(131)} G q ≤ ( 1 − c ) q U q ≤ e − c q U q = e − γ U q . (131) Therefore,
J ˉ ( T ′ ) ≥ ( 1 − e − γ ) U q (132) \bar{\mathcal{J}}(T') \ge(1-e^{-\gamma})U_q \tag*{(132)} J ˉ ( T ′ ) ≥ ( 1 − e − γ ) U q (132) ≥ ( 1 − e − γ ) J ˉ ( T ∗ ) , (133) \ge(1-e^{-\gamma})\bar{\mathcal{J}}(T^*), \tag*{(133)} ≥ ( 1 − e − γ ) J ˉ ( T ∗ ) , (133) which proves the claim.
Empirical Diagnostics of the Near-Optimality Conditions
We empirically investigate the conditions underlying the near-optimality guarantee in Theorem 1: restricted strong concavity (RSC), positive realized improvement under binary deletion, and restricted gradient dominance. We evaluate these conditions for the symmetric and asymmetric synthetic examples and the Twitter experiment, varying the Gamma-prior parameter a a a
Restricted curvature. Following Lemma 4, we evaluate the Hessian of the negated uncertainty objective at each removal step k k k H ( k ) = H e p i ( k ) + H a l e ( k ) H^{(k)} = H_{\mathrm{epi}}^{(k)} + H_{\mathrm{ale}}^{(k)} H ( k ) = H epi ( k ) + H ale ( k ) T T T R k = T ∩ S ( k ) R_k = T \cap S^{(k)} R k = T ∩ S ( k ) k k k H R k ( k ) H_{R_k}^{(k)} H R k ( k )
λ min ( H R k ( k ) ) ≤ λ max ( H R k ( k ) ) . (134) \lambda_{\min}\left(H_{R_k}^{(k)}\right) \le\lambda_{\max}\left(H_{R_k}^{(k)}\right). \tag*{(134)} λ m i n ( H R k ( k ) ) ≤ λ m a x ( H R k ( k ) ) . (134) A negative largest eigenvalue indicates local strong concavity along the considered removal coordinates. These eigenvalues provide empirical curvature diagnostics and show constraint violations, but do not alone establish the full RSC condition of Definition 1.
Gradient dominance. To assess the effect of discrete removals, we compute the removal coefficient
ρ k = 2 M R [ J ( S ( k ) ) − J ( S ( k + 1 ) ) ] ∥ u ( k ) + v ( k ) ∥ ∞ 2 , (135) \rho_k = \frac{2M_R\left[\mathcal{J}\left(S^{(k)}\right)-\mathcal{J}\left(S^{(k+1)}\right)\right]}{\left\|u^{(k)}+v^{(k)}\right\|_\infty^2}, \tag*{(135)} ρ k = u ( k ) + v ( k ) ∞ 2 2 M R [ J ( S ( k ) ) − J ( S ( k + 1 ) ) ] , (135) where ρ k > 0 \rho_k > 0 ρ k > 0
∥ u ( k ) + v ( k ) ∥ ∞ 2 ≥ 2 m R q [ U q − J ˉ ( T k ) ] + , (136) \left\|u^{(k)}+v^{(k)}\right\|_\infty^2 \ge\frac{2m_R}{q}\left[U_q-\bar{\mathcal{J}}(T_k)\right]_+, \tag*{(136)} u ( k ) + v ( k ) ∞ 2 ≥ q 2 m R [ U q − J ˉ ( T k ) ] + , (136) where U q U_q U q Figure 25 compares U q U_q U q
Figure 25. Empirical diagnostics of the near-optimality conditions for the symmetric and asymmetric synthetic examples and the Twitter experiment, for different Gamma-prior parameters a a a Top: Extremal eigenvalues of the Hessian restricted to the remaining removal coordinates; positive largest eigenvalues indicate a violation of local concavity. Middle: Removal coefficients ρ k \rho_k ρ k Bottom: Upper-bound quantity U q U_q U q J ˉ ( T k ) \bar{J}(T_k) J ˉ ( T k ) a a a
Observations. As shown in Figure 25 , the prior parameter a a a a a a a a a a a a ρ k \rho_k ρ k a = 1.1 a = 1.1 a = 1.1 a a a
These observations highlight that restricted curvature, positive realized improvement, and gradient dominance capture distinct properties of the removal process. Importantly, we observe empirical improvements even when not all theoretical conditions are satisfied. Thus, these conditions are sufficient for the near-optimality guarantee, but are not necessary for successful data removal in practice.
