Transductive Active Learning: Theory and Applications

Authors: jonas  hübotter
bhavya  sukhija
lenart  treven
yarden  as
andreas  krause
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-06 10:01:27

Abstract: We study a generalization of classical active learning to real-world settings with concrete prediction targets where sampling is restricted to an accessible region of the domain, while prediction targets may lie outside this region.
We analyze a family of decision rules that sample adaptively to minimize uncertainty about prediction targets.
We are the first to show, under general regularity assumptions, that such decision rules converge uniformly to the smallest possible uncertainty obtainable from the accessible data.
We demonstrate their strong sample efficiency in two key applications: active fine-tuning of large neural networks and safe Bayesian optimization, where they achieve state-of-the-art performance.

Main paper: 
 introduction: 
 Machine learning, at its core, is about designing systems that can extract knowledge or patterns from data. One part of this challenge is determining not just how to learn given observed data but deciding what data to obtain next, given the information already available. More formally, given an unknown and sufficiently regular function f over a domain X : How can we learn f sample-efficiently from (noisy) observations? This problem is widely studied in active learning and experimental design (Chaloner & Verdinelli, 1995; Settles, 2009) .Active learning methods commonly aim to learn f globally, i.e., across the entire domain X . However, in many real-world problems, (i) the domain is so large that learning f globally is hopeless or (ii) agents have limited information and cannot access the entire domain (e.g., due to restricted access or to act safely). Thus, global learning is often not desirable or even possible. Instead, intelligent systems are typically required to act in a more directed manner and extrapolate beyond their limited information. This work formalizes the above two aspects of active learning, which have remained largely unaddressed by prior work. We provide a comprehensive overview of related work in Section 6."Directed" transductive active learning We consider the generalized problem of transductive active learning, where given two arbitrary subsets of the domain X ; a target space A ⊆ X , and a sample space S ⊆ X , we study the question:How can we learn f within A by actively sampling observations within S? The points denote plausible observations within S to "learn" A. In (A), the target space contains "everything" within S as well as points outside S. In (B, C, D), one makes observations directed towards learning about a particular target.Prior work on inductive active learning has focused on the instance A = S.This problem is ubiquitous in real-world applications such as safe Bayesian optimization, where S is a set of safe parameters and A might represent parameters outside S whose safety we want to infer. Active fine-tuning of neural networks is another example, where the target space A represents the test set over which we want to minimize risk, and the sample space S represents the dataset from which we can retrieve data points to fine-tune our model to A. Figure 1 visualizes some instances of transductive active learning.Whereas most prior work has focused on the "global" inductive instance X = A = S, MacKay (1992) was the first to consider specific target spaces A and proposed the principle of selecting points in S to minimize the "posterior uncertainty" about points in A. Since then, several works have studied this principle empirically (e.g., Seo et al., 2000; Yu et al., 2006; Bogunovic et al., 2016; Wang et al., 2021; Kothawade et al., 2021; Bickford Smith et al., 2023) . In this work, we model f as a Gaussian process or (equivalently) as a function in a reproducing kernel Hilbert space, for which the above principle is analytically and computationally tractable. Our contributions are:• Theory (Section 3): We are the first to give rates for the uniform convergence of uncertainty over the target space A to the smallest attainable value, given samples from the sample space S (Theorems 3.2 and 3.3), Our results provide a theoretical justification for the principle of minimizing posterior uncertainty in transductive active learning, and indicate that transductive active learning can be more sample efficient than inductive active learning.• Applications: We show that transductive active learning improves upon the state-of-the-art in the batch-wise active fine-tuning of neural networks for image classification (Section 4) and in safe Bayesian optimization (Section 5). 
problem setting: 
 We assume for now that the target space A and sample space S are finite, and relax these assumptions in the appendices. We model f as a stochastic process and denote the marginal random variables f (x) by f x , and joint random vectors {f x } x∈X for some X ⊆ X , |X| < ∞ by f X . Let y X denote the noisy observations of f X , {y x = f x + ε x } x∈X , where ε x is independent noise. 2 We study the "adaptive" setting, where in round n the agent selects a point x n ∈ S and observes y n = y xn . The agent's choice of x n may depend on the outcome of prior observations D n-1 def = {(x i , y i )} i<n .Background on information theory We briefly recap several important concepts from information theory of which we provide formal definitions in Appendix B. The (differential) entropy H[f ] is one possible measure of uncertainty about f and the conditional entropy H[f | y] is the (expected) posterior uncertainty about f after observing y. The information gain I(f ;y) = H[f ] -H[f | y]measures the (expected) reduction in uncertainty about f due to y. We denote the information gain about A from observing X by I(f A ; y X ). The maximum information gain about A from n observations within S is γ A,S (n) def = max X⊆S |X|≤n I(f A ; y X ).This "information capacity" measures the information about f A that is accessible from within S, and has been used previously (e.g., by Srinivas et al., 2009; Chowdhury & Gopalan, 2017; Vakili et al., 2021) in the setting where X = A = S, taking the form of γ n def = γ X (n) def = γ X ,X (n). We remark that γ A,S (n) ≤ γ S (n) holds uniformly for all A, S, and n due to the data processing inequality. Generally, γ A,S (n) can be substantially smaller if the target space is a sparse subset of the sample space. 
main results: 
 We analyze the following principle for transductive active learning:Select samples to minimize the posterior "uncertainty" about f within A.( †)This principle yields a family of simple and natural decision rules which depend on the chosen measure of "uncertainty". Two natural measures of uncertainty are (1) the entropy of prediction targets, H[f A ], and (2) their total variance, x ′ ∈A Var[f x ′ ]. The corresponding decision rules are(1)EQUATION(2)x n = arg minx∈S tr Var[f A | D n-1 , y x ] (VTL)with an implicit expectation over the feedback y x . That is, ITL (short for Information-based Transductive Learning) and VTL (Variance-based TL) select x n so as to minimize the uncertainty about the prediction targets f A (in expectation) after having received the feedback y n . Unlike VTL, ITL takes into account the mutual dependence between points in A. These decision rules were suggested previously (MacKay, 1992; Seo et al., 2000; Yu et al., 2006) without deriving theoretical guarantees; and they generalize several widely used algorithms which we discuss in more detail in Section 6. Most prominently, in the inductive setting where S ⊆ A, ITL reduces to x n = arg max x∈S I(f x ; y x | D n-1 ), i.e., is "undirected" and reduces to standard uncertainty-based active learning strategies (cf. Appendix C.1). The convergence properties for the special instance of ITL with S = A have been studied extensively. To the best of our knowledge, we are the first to extend these guarantees to the more general setting of transductive active learning.In our presented results, we make the following assumption. Assumption 3.1. In the case of ITL, the information gain ψ A (X) = I(f A ; y X ) is submodular. In the case of VTL, the variance reduction ψ A (X) = tr Var[f A ] -tr Var[f A | y X ] is submodular. Under this assumption, ψ A (x 1:n ) is a constant factor approximation of max X⊆S,|X|≤n ψ A (X) due to the seminal result on submodular function maximization by Nemhauser et al. (1978) . Similar assumptions have been made, e.g., by Bogunovic et al. (2016) and Kothawade et al. (2021) . Assumption 3.1 is satisfied exactly for ITL when S ⊆ A and f is a Gaussian process (cf. Lemma C.9), and we provide an extensive discussion of our results in Appendix C.4 for instances where Assumption 3.1 is satisfied approximately, relying on the notion of weak submodularity (Das & Kempe, 2018) .When f ∼ GP(µ, k) is a Gaussian process (GP, Williams & Rasmussen, 2006) with known mean function µ and kernel k, and the noise ε x is mutually independent and zero-mean Gaussian with known variance, the ITL and VTL objectives have a closed form expression (cf. Appendix F) and can be optimized efficiently. Further, the information capacity γ n is sublinear in n for a rich class of GPs (Srinivas et al., 2009; Vakili et al., 2021) , with rates summarized in Table 3 of the appendix.Convergence to irreducible uncertainty So far, our discussion was centered around the role of the target space A in facilitating directed learning. An orthogonal contribution of this work is to study extrapolation from the sample space S to points x ∈ A \ S. To this end, we derive bounds on the marginal posterior variance σ 2 n (x)def = Var[f (x) | D n ]for points in A. These bounds depend on the instance of transductive active learning (i.e., A and S) and might be of independent interest for active learning. For ITL and VTL, they imply uniform convergence of the variance for a rich class of GPs. To the best of our knowledge, this work is the first to present such bounds.We define the irreducible uncertainty as the variance of f (x) provided complete knowledge of f in S:η 2 S (x) def = Var[f x | f S ].As the name suggests, η 2 S (x) represents the smallest uncertainty one can hope to achieve from observing only within S. For all x ∈ S, it is easy to see that η 2 S (x) = 0. However, the irreducible uncertainty of x ̸ ∈ S may be (and typically is!) strictly positive. Theorem 3.2 (Bound on marginal variance for ITL and VTL). Let Assumption 3.1 hold and the data be selected by either ITL or VTL.. Assume that f ∼ GP(µ, k) with known mean function µ and kernel k, the noise ε x is mutually independent and zero-mean Gaussian with known variance, and γ n is sublinear in n. Then there exists a constant C such that for any n ≥ 1 and x ∈ A,σ 2 n (x) ≤ η 2 S (x) irreducible + C γ A,S (n) √ n reducible .(1)Moreover, if x ∈ A ∩ S, there exists a constant C ′ such thatEQUATIONIntuitively, Equation (1) of Theorem 3.2 can be understood as bounding an epistemic "generalization gap" (Wainwright, 2019) of the learner. The reducible uncertainty converges to zero at all prediction targets x ∈ A, e.g., for linear, Gaussian, and smooth Matérn kernels. As to be expected, a smaller target space (i.e., more targeted sampling) leads to faster convergence due to a smaller information capacity γ A,S (n) ≪ γ n . Equation (2) matches prior results for the setting S = A. We provide a formal proof of Theorem 3.2 in Appendix C.6.The result from the GP setting translates also to the agnostic setting, where the "ground truth" f ⋆ may be any sufficiently regular fixed function on X . 3 In this case, we use the model f from Section 3.1 as a (misspecified) model of f ⋆ , with some kernel k and zero mean function µ(•) = 0. We denote by µ n (x) = E[f (x) | D n ] the posterior mean of f . W.l.o.g. we assume in the following result that the prior variance is bounded, i.e., Var[f (x) ] ≤ 1. Theorem 3.3 (Bound on approximation error for ITL and VTL, following Abbasi-Yadkori (2013); Chowdhury & Gopalan (2017) ). Let Assumption 3.1 hold and the data be selected by either ITL or VTL. Pick any δ ∈ (0, 1). Assume that f ⋆ lies in the reproducing kernel Hilbert space H k (X ) of the kernel k with norm ∥f ⋆ ∥ k < ∞, the noise ε n is conditionally ρ-sub-Gaussian, and γ n is sublinear in n. Let β n (δ) = ∥f ⋆ ∥ k + ρ 2(γ n + 1 + log(1/δ)). Then for any n ≥ 1 and x ∈ A, jointly with probability at least 1 -δ,EQUATIONreducible where ν 2 A,S (n) denotes the reducible part of Equation (1).We provide a formal proof of Theorem 3.3 in Appendix C.7. Theorem 3.3 generalizes approximation error bounds of prior works to the extrapolation setting, where some prediction targets x ∈ A lie outside the sample space S. For prediction targets x ∈ A ∩ S, the irreducible uncertainty vanishes, and we recover previous results from the setting S = A.Theorems 3.2 and 3.3 show that ITL and VTL efficiently learn f at the prediction targets A for large classes of "sufficiently regular" functions f . In the following, we validate these results experimentally by showing that ITL and VTL exhibit strong empirical performance in a broad range of applications.Before demonstrating ITL and VTL on GPs to develop more intuition, we introduce a natural correlation-based baseline, which will later uncover connections to existing approaches:x n = arg max x∈S x ′ ∈A Cor[f x , f x ′ | D n-1 ]. (CTL)How does the smoothness of f affect ITL? We contrast two "extreme" kernels: the Gaussian kernel k(x, x ′ ) = exp(-∥x -x ′ ∥ 2 2 /2) and the Laplace kernel k(x, x ′ ) = exp(-∥x -x ′ ∥ 1 ). In the mean-squared sense, the Gaussian kernel yields a smooth process f whereas the Laplace kernel yields a continuous but non-differentiable f (Williams & Rasmussen, 2006) . Figure 2 how ITL adapts to the smoothness of f : Under the "smooth" Gaussian kernel, points outside A provide higher-order information. In contrast, under the "rough" Laplace kernel and if A ⊆ S, points outside A do not provide any additional information, and therefore are not sampled by ITL. If, however, A ̸ ⊆ S, information "leaks" A even under a Laplace kernel prior. That is, even for non-smooth functions, the point with most information need not be in A.Does ITL outperform uncertainty sampling? Uncertainty sampling (UNSA, Lewis & Catlett, 1994) is one of the most popular active learning methods. UNSA selects points x with high prior uncertainty:x n = arg max x∈S σ 2 n-1 (x). This is in stark contrast to ITL and VTL which select points x that minimize posterior (epistemic) uncertainty about A. It can be seen that UNSA is the special "undirected" case of ITL when S ⊆ A and observation noise is homoscedastic (cf. Appendix C.1).We compare UNSA to ITL, VTL, and CTL in Figure 3 . We observe that ITL and VTL outperform UNSA which also samples points that are not informative about A. Further, ITL and VTL outperform "local" UNSA (i.e., UNSA constrained to A ∩ S) which neglects all information provided by points outside A. 4 As one would expect, VTL has an advantage with respect to reducing the total variance of f A , whereas ITL reduces the entropy of f A faster. We include ablations in Appendix H where we, in particular, observe that the advantage of ITL and VTL over UNSA increases as the volume of prediction targets shrinks in comparison to the size of domain. 
active fine-tuning of neural networks: 
 Fine-tuning a large pre-trained model is a cost-and computation-effective approach to improve performance on a given target domain (Lee et al., 2022) . While previous work has studied the effectiveness of various training procedures for fine-tuning (e.g., Eustratiadis et al., 2024) , we ask: How can we select the right data for fine-tuning to a specific task? This active fine-tuning problem is an instance of the introduced "directed" transductive learning problem: Concretely, consider a supervised setting, where the function f maps inputs x ∈ X to outputs y ∈ Y. We have access to noisy samples from a training set S on X , and we would like to learn f such that our estimate minimizes a given risk measure, such as classification error, with respect to a test distribution P A on X . The goal is to actively and efficiently sample from S to minimize risk with respect to P A . 5We show in this section that ITL and VTL can learn f from only few examples from S.How can we leverage the latent structure learned by the pre-trained model? As common in related work, we approximate the (pre-trained) neural network (NN) f (•; θ) as a linear function in a latent embedding space, f (x; θ) ≈ β ⊤ ϕ θ (x), with weights β ∈ R p and embeddings ϕ θ : X → R p . Common choices of embeddings include last-layer embeddings (Devlin et al., 2019; Holzmüller et al., 2023) , neural tangent embeddings arising from neural tangent kernels (Jacot et al., 2018) which are motivated by their relationship to the training and fine-tuning of ultra-wide NNs (Arora et al., 2019; Lee et al., 2019; Khan et al., 2019; He et al., 2020; Malladi et al., 2023) , and loss gradient embeddings (Ash et al., 2020) . We provide a comprehensive overview of embeddings in Appendix J.2. Now, supposing the prior β ∼ N (0, Σ), often with Σ = I (Khan et al., 2019; He et al., 2020; Antorán et al., 2022; Wei et al., 2022) , this approximation of f is a Gaussian process with kernel k(x, x ′ ) = ϕ θ (x) ⊤ Σϕ θ (x ′ ) which quantifies the similarity between points in terms of their alignment in the learned latent space. Note that the correlation k(x, x ′ )/ k(x, x)k(x ′ , x ′ ) between two points x, x ′ is equal to the cosine similarity of their embeddings.In this context, Theorem 3.2 bounds the epistemic posterior uncertainty about a prediction using the approximation β ⊤ ϕ θ (x), given that the model is trained using data selected by ITL or VTL. Theorem 3.3 bounds the generalization error when using the posterior mean of β for prediction. This extends recent work which has studied estimators of this generalization error (Wei et al., 2022) .Batch selection: Diversity via conditional embeddings Efficient labeling and training necessitates a batch-wise selection of inputs. The selection of a batch of size b > 1 can be seen as an individual non-adaptive active learning problem, and significant recent work has shown that batch diversity is crucial in this setting (Ash et al., 2020; Zanette et al., 2021; Holzmüller et al., 2023; Pacchiano et al., 2024 ). An information-based batch-wise selection strategy is formalized by the following nonadaptive transductive active learning problem (Chen & Krause, 2013) and the greedy approximation of B n by ITL which selects elements x n,i of the n-th batch iteratively based on x n,1:i-1 :EQUATIONThe batch B n is diverse and informative by design. We show that under Assumption 3.1, B ′ n = x n,1:b yields a constant-factor approximation of B n (cf. Appendix C.3).Our empirical evaluation is motivated by the following practical example: We deploy a pre-trained image classifier to user's phones who use it within their local environment. We would like to locally fine-tune a user's model to their environment. Since the users' images A are unlabeled, this requires selecting a small number of relevant and diverse images from the set of labeled images S. As such, we will focus here on the setting where the points in our test set do not lie in our training set (i.e., A ∩ S = ∅), and discuss alternative instances such as active domain adaptation in Appendix I.Testbeds & architectures We use the MNIST (LeCun et al., 1998) and CIFAR-100 (Krizhevsky et al., 2009) datasets as testbeds. In both cases, we take S to be the training set, and we consider the task of learning the digits 3, 6, and 9 (MNIST) or the first 10 categories of CIFAR-100. 6 For MNIST, we train a simple convolutional neural network with ReLU activations, three convolutional layers with max-pooling, and two fully-connected layers. For CIFAR-100, we fine-tune an EfficientNet-B0 (Tan & Le, 2019) pre-trained on ImageNet (Deng et al., 2009) , augmented by a final fully-connected layer. We train the NNs using the cross-entropy loss and the ADAM optimizer (Kingma & Ba, 2014) .In Figure 4 , We compare against (i) active learning methods which largely aim for sample diversity but which are not directed towards the target distribution P A (e.g., BADGE; Ash et al., 2020) , and (ii) search methods that aim to retrieve the most relevant samples from S with respect to the targets P A (e.g., maximizing cosine similarity to target embeddings as is common in vector databases; Uncertainty bands correspond to one standard error over 10 random seeds. We see that transductive active learning with ITL and VTL significantly outperforms competing methods, and in particular, retrieves substantially more samples from the support of P A . See Appendix J for details and ablations. Settles & Craven, 2008; Johnson et al., 2019) . INFORMATIONDENSITY (ID, Settles & Craven, 2008) is a heuristic approach aiming to combine (i) diversity and (ii) relevance. In Appendix J.5, we also compare against a wide range of additional baselines (e.g., CORESET (Sener & Savarese, 2017) , TYPICLUST (Hacohen et al., 2022) , PROBCOVER (Yehuda et al., 2022) , etc.) that fall into one of the categories (i) and (ii), and which perform similar to the baselines listed here.We observe that ITL, VTL, and CTL consistently and significantly outperform random sampling from S as well as all baselines. We see that relevance-based methods such as COSINESIMILARITY have an initial advantage over RANDOM but for batch sizes larger than 1 they quickly fall behind due to diminishing informativeness of the selected data. In contrast, diversity-based methods such as BADGE are more competitive with RANDOM but do not explicitly aim to retrieve relevant samples.Remarkably, transductive active learning outperforms random data selection even in the MNIST experiment where the model is randomly initialized. This suggests that the learned embeddings can be informative for data selection even in the early stages of training, bootstrapping the learning progress.Balancing sample relevance and diversity Our proposed methods unify approaches to coverage (promoting diverse samples) and search (aiming for relevant samples with respect to a given query A) which leads to the significant improvement upon the state-of-the-art in Figure 4 . Notably, for a batch size and query size of 1 and if correlations are non-negative, ITL, VTL, CTL, and the canonical cosine similarity are equivalent. CTL can be seen as a direct generalization of cosine similarity-based retrieval to batch and query sizes larger than one. In contrast to CTL, ITL and VTL may also sample points which exhibit a strong negative correlation (which is also informative).We observe empirically that ITL obtains samples from P A at more than twice the rate of COSINES-IMILARITY, which translates to a significant improvement in accuracy in more difficult learning tasks, while requiring fewer (labeled) samples from S. This phenomenon manifests for both MNIST and CIFAR-100, as well as imbalanced datasets S or imbalanced reference samples from P A (cf. Appendix J.6). The improvement in accuracy appears to increase in the large-data regime, where the learning tasks become more difficult. Akin to a previously identified scaling trend with size of the pretraining dataset (Tamkin et al., 2022) , this suggests a potential scaling trend where the improvement of ITL over random batch selection grows as models are fine-tuned on a larger pool of data.Towards task-driven few-shot learning Being able to efficiently and automatically select data may allow dynamic few-shot fine-tuning to individual tasks (Vinyals et al., 2016; Hardt & Sun, 2024) , e.g., fine-tuning the model to each test point / query / prompt. Such task-driven few-shot learning can be seen as a form of "memory recall" akin to associative memory (Hopfield, 1982) .Our results are a first indication that task-driven learning can lead to substantial performance gains, and we believe that this is a promising direction for future studies. 
safe bayesian optimization: 
 Another practical problem that can be cast as "directed" learning is safe Bayesian optimization (Safe BO, Sui et al., 2015; Berkenkamp et al., 2021) which has applications in natural science (Cooper & Netoff, 2022) and robotics (Wischnewski et al., 2019; Sukhija et al., 2023; Widmer et al., 2023) . Safe BO solves the following optimization problemEQUATIONwhich can be generalized to multiple constraints. The functions f ⋆ and g ⋆ , and hence also the "safe set" S ⋆ , are unknown and have to be actively learned from data. However, it is crucial that the data collection does not violate the constraint, i.e., x n ∈ S ⋆ , ∀n ≥ 1.Safe Bayesian optimization as Transductive Active Learning In the agnostic setting from Section 3.2, GPs f and g can be used as well-calibrated models of the ground truths f ⋆ and g ⋆ , and we denote lower-and upper-confidence bounds by l f n (x), l g n (x) and u f n (x), u g n (x), respectively. These confidence bounds induce a pessimistic safe set S n def = {x | l g n (x) ≥ 0} and an optimistic safe set S n def = {x | u g n (x) ≥ 0} which satisfy S n ⊆ S ⋆ ⊆ S n with high probability at all times. Similarly, the set of potential maximizersEQUATIONcontains the solution to Equation ( 4) at all times with high probability.The (simple) regret r n (S)def = max x∈S f ⋆ (x) -f ⋆ ( x n ) with x n def = arg max x∈Sn l f n (x)measures the worst-case performance of a decision rule. To achieve small regret, one faces an explorationexpansion dilemma wherein one needs to explore points that are known-to-be-safe, i.e., lie in the estimated safe set S n , and might be optimal, while at the same time discovering new safe points by "expanding" S n . Accordingly, a natural choice for the target space of Safe BO is A n since it captures both exploration and expansion simultaneously. 7 To prevent constraint violation, the sample space is restricted to the pessimistic safe set S n . In Safe BO, both the target space and sample space change with each round n, and we generalize our theoretical results from Section 3 in Appendix C to this setting. Theorem 5.1 (Convergence to safe optimum). Pick any ϵ > 0, δ ∈ (0, 1). Assume that f ⋆ , g ⋆ lie in the reproducing kernel Hilbert space H k (X ) of the kernel k, and that the noise ε n is conditionally ρ-sub-Gaussian. Then, we have with probability at least 1 -δ, Safety: for all n ≥ 1, x n ∈ S ⋆ . Moreover, assume S 0 ̸ = ∅ and denote with R the largest reachable safe set starting from S 0 . Then, the convergence of reducible uncertainty implies that there exists n ⋆ > 0 such that with probability at least 1 -δ,Optimality: for all n ≥ n ⋆ , r n (R) ≤ ϵ.We provide a formal proof in Appendix C.8. Central to the proof is the application of Theorem 3.3 to show that the safety of parameters outside the safe set S n can be inferred efficiently. In Section 3, we outline settings where the reducible uncertainty converges which is the case for a very general class of functions, and for such instances Theorem 5.1 guarantees optimality in the largest reachable safe set R. R represents the largest set any safe learning algorithm can explore without violating the safety constraints (with high probability) during learning (cf. Definition C.29). Our guarantees are similar to those of other Safe BO algorithms (Berkenkamp et al., 2021) but require fewer assumptions and generalize to continuous domains. We obtain Theorem 5.1 from a more general result (Theorem C.34) which can be specialized to yield "free" novel convergence guarantees for problems other than Bayesian optimization, such as level set estimation, by choosing an appropriate target space. We compare ITL and VTL to ORACLE SAFEOPT, which has oracle knowledge of the Lipschitz constants, SAFEOPT, where the Lipschitz constants are estimated from the GP, as well as HEURISTIC SAFEOPT and ISE, and observe that ITL and VTL systematically perform well. We compare against additional baselines in Appendix K.1. The regret is evaluated with respect to the ground truth objective f ⋆ and constraint g ⋆ , and averaged over 10 (in synthetic experiments) and 25 (in the quadcopter experiment) random seeds. Additional details can be found in Appendix K.4.We evaluate two synthetic experiments for a 1d and 2d parameter space, respectively (cf. Appendix K.4 for details), which demonstrate the various shortcomings of existing Safe BO baselines. Additionally, as third experiment, we safely tune the controller of a quadcopter.Safe controller tuning for a quadcopter We consider a quadcopter with unknown dynamics; s t+1 = T (s t , u t ) where u t ∈ R du is the control signal and s t ∈ R ds is the state at time t. The inputs u t are calculated through a deterministic function of the state π : S → U which we call the policy. The policy is parameterized via parameters x ∈ X , e.g., PID controller gains, such that u t = π x (s t ). The goal is to find the optimal parameters with respect to an unknown objective f ⋆ while satisfying some unknown constraint(s) g ⋆ (x) ≥ 0, e.g., the quadcopter does not fall on the ground. This is a typical Safe BO problem which is widely applied for safe controller learning in robotics (Berkenkamp et al., 2021; Baumann et al., 2021; Widmer et al., 2023) .We compare ITL and VTL to SAFEOPT (Berkenkamp et al., 2021) , which is undirected, i.e., expands in all directions including ones that are known-to-be suboptimal, and ISE (Bottero et al., 2022) , which is solely expansionist -does not trade-off expansion-exploration. We provide a detailed discussion of baselines in Appendix K.2. In all our experiments, summarized in Figure 5 , we observe that ITL and VTL systematically perform well, i.e., better or on par with the state-of-the-art.We attribute this to its directed exploration and less conservative expansion over SAFEOPT (cf. 1d task and quadcopter experiment), and natural trade-off between expansion and exploration as opposed to ISE (see 2d task). Generally, VTL has a slight advantage over ITL, which is because VTL minimizes marginal variances (as opposed to entropy), which are decisive for expanding the safe set.While ITL and VTL do not violate constraints, we observe that other methods that do not explicitly enforce safety such as EIC (Gardner et al., 2014) lead to constraint violation (cf. Appendix K.4.2). 
related work: 
 (Inductive) active learning The special case of transductive active learning where A = S = X has been widely studied. We refer to this special instance as inductive active learning, since the goal is to extract as much information as possible as opposed to making predictions on a specific target set.Several works have previously found entropy-based decision rules to be useful for inductive active learning (Krause & Guestrin, 2007; Guo & Greiner, 2007; Krause et al., 2008) and semi-supervised learning (Grandvalet & Bengio, 2004) . The variance-based VTL has previously been proposed by Cohn (1993) in the special case of inductive active learning without proving theoretical guarantees. VTL was then recently re-derived by Shoham & Avron (2023) along other experimental design criteria under the lens of minimizing risk for inductive one-shot learning in overparameterized models. Substantial work on active learning has studied entropy-based criteria in parameter-space, most notably BALD (MacKay, 1992; Houlsby et al., 2011; Gal et al., 2017; Kirsch et al., 2019) , which selects x n = arg max x∈X I(θ; y x | D n-1 ), where θ is the random parameter vector of a parametric model (e.g., obtained via Bayesian deep learning). Such methods are inherently inductive in the sense that they do not facilitate learning on specific prediction targets.Transductive active learning In contrast, ITL operates in output-space where it is straightforward to specify prediction targets, and which is computationally easier. Special cases of ITL when S = X and |A| = 1 have been proposed in the foundational work of MacKay (1992) on "directed" output-space active learning. As generalization to larger target spaces, MacKay (1992) proposed mean-marginal ITL, Influence functions measure the change in a model's prediction when a single data point is removed from the training data (Cook, 1977; Koh & Liang, 2017; Pruthi et al., 2019) . Influence functions have been used for data selection in settings closely related to the transductive active fine-tuning of neural networks proposed in this work (Xia et al., 2024) . They select data that reduces a first-order Taylor approximation to the test loss after fine-tuning a neural network, which corresponds to maximizing cosine similarity to the prediction targets in a loss-gradient embedding space. We show in our experiments that transductive active learning can substantially outperform COSINESIMILARITY. We attribute this primarily to influence functions implicitly assuming that the influence of selected data adds linearly (i.e., two equally scored data points are expected to doubly improve the model performance, Xu & Kazantsev, 2019, Section 3.2 ). This assumption does not hold in practice as seen, e.g., by simply duplicating data. The same limitation applies to the related approach of datamodels (Ilyas et al., 2022) .x n = arg max x∈S x ′ ∈A I(f x ′ ; y x | D n-Other work on directed active learning Directed active learning methods have been proposed for the problem of determining the optimum of an unknown function, also known as best-arm identification (Audibert et al., 2010) or pure exploration bandits (Bubeck et al., 2009) . Entropy search methods (Hennig & Schuler, 2012; Hernández-Lobato et al., 2014) are widely used and select x n = arg max x∈X I(x * ; y x | D n-1 ) in input-space where x * = arg max x f x . Similarly to ITL, output-space entropy search methods (Hoffman & Ghahramani, 2015; Wang & Jegelka, 2017) , which select x n = arg max x∈X I(f * ; y x | D n-1 ) with f * = max x f x , are more computationally tractable.In fact, output-space entropy search is a special case of ITL with a stochastic target space (cf. Equation (47) in Appendix K.1). Bogunovic et al. (2016) analyze TRUVAR in the context of Bayesian optimization and level set estimation. TRUVAR is akin to VTL with a similar notion of "target space", but their algorithm and analysis rely on a threshold scheme which requires that A ⊆ S. Fiez et al. (2019) introduce the transductive linear bandit problem, which is a special case of transductive active learning limited to a linear function class and with the objective of determining the maximum within an initial candidate set. 8 We mention additional more loosely related works in Appendix A. 
conclusion: 
 We investigated the generalization of active learning to settings with concrete prediction targets and/or with limited information due to constrained sample spaces. This provides a flexible framework, applicable also to other domains than were discussed (such as recommender systems, molecular design, robotics, etc.) by varying the choice of target space and sample space. Further, we proved novel generalization bounds which may be of independent interest for active learning. Finally, we demonstrated across broad applications that sampling relevant and diverse points (as opposed to only one of the two) leads to a substantial improvement upon the state-of-the-art. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification:Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification:Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. 
 
 Appendix: A general principle of "transductive learning" was already formulated by the famous computer scientist Vladimir Vapnik in the 20th century. Vapnik proposes the following "imperative for a complex world":When solving a problem of interest, do not solve a more general problem as an intermediate step. Try to get the answer that you really need but not a more general one.- Vapnik (1982) These appendices provide additional background, proofs, experiment details, and ablation studies. A Additional Related WorkThe general principle of non-active "transductive learning" was introduced by Vapnik (1982) . The notion of "target" from transductive active learning is akin to the notion of "task" in curriculum learning (Bengio et al., 2009; Graves et al., 2017; Soviany et al., 2022) . The study of settings where the irreducible uncertainty is zero is related to the study of estimability in experimental design (Graybill, 1961; Mutny & Krause, 2022) . In feature selection, selecting features that maximize information gain with respect to a to-be-predicted label is a standard approach (Peng et al., 2005; Vergara & Estévez, 2014; Beraha et al., 2019) which is akin to ITL (cf. Appendix D). The themes of relevance and diversity are also important for efficient in-context learning (e.g., Ye et al., 2023; Kumari et al., 2024) and data pruning (Zheng et al., 2023) . Transductive active learning is complimentary to other learning methodologies, such as semi-supervised learning (Gao et al., 2020) , self-supervised learning (Shwartz-Ziv & LeCun, 2023; Balestriero et al., 2023) , and meta-learning (Kaddour et al., 2020; Rothfuss et al., 2023) .Throughout this work, log denotes the natural logarithm. Given random vectors x and y, we denote byEQUATIONI(x; y) def = H[x] -H[x | y]the (differential) entropy, conditional entropy, and information gain, respectively (Cover, 1999 ).9 The multivariate information gain (Murphy, 2023) between random vectors x, y, z is given byEQUATIONWhen I(x; y; z) ̸ = 0 it is said that y and z interact regarding their information about x. If the interaction is positive, it is said that the information of z about x is redundant given y. Conversely, if the interaction is negative, it is said that the information of z about x is synergistic with y. The notion of synergy is akin to the frequentist notion of "suppressor variables" in linear regression (Das & Kempe, 2008) .The stochastic process f is a Gaussian process (GP, Williams & Rasmussen (2006) ), denoted f ∼ GP(µ, k), with mean function µ and kernel k if for any finite subsetX = {x 1 , . . . , x n } ⊆ X , f X ∼ N (µ X , K XX ) is jointly Gaussian with mean vector µ X (i) = µ(x i ) and covariance matrix K XX (i, j) = k(x i , x j ).In the following, we formalize the assumptions from the GP setting (cf. Section 3.1). Assumption B.1 (Gaussian prior). We assume that f ∼ GP(µ, k) with known mean function µ and kernel k. Assumption B.2 (Gaussian noise). We assume that the noise ε x is mutually independent and zero-mean Gaussian with known variance ρ 2 (x) > 0. We write P X = diag ρ 2 (x 1 ), . . . , ρ 2 (x n ).Under Assumptions B.1 and B.2, the posterior distribution of f after observing points X isGP(µ n , k n ) with µ n (x) = µ(x) + K xX (K XX + P X ) -1 (y X -µ X ), k n (x, x ′ ) = k(x, x ′ ) -K xX (K XX + P X ) -1 K Xx ′ , σ 2 n (x) = k n (x, x).Lemma C.1. For both ITL and VTL, ψ A is non-negative and monotone.Proof. For ITL, ψ A (X) ≥ 0 follows from the non-negativity of mutual information. To conclude monotonicity, note that for any X ′ ⊆ X ⊆ S,I(f A ; y X ′ ) = H[f A ] -H[f A | y X ′ ] ≤ H[f A ] -H[f A | y X ] = I(f A ; y X )due to monotonicity of conditional entropy (which is also called the "information never hurts" principle).For VTL, recall that tr Var[f A | y X ] ≤ tr Var[f A | y X ′ ]for any X ′ ⊆ X ⊆ S (with an implicit expectation over y X , y X ′ ). Non-negativity and monotonicity of ψ A then follow analogously to ITL.Lemma C.2. The marginal gain ∆ A (x | X) def = ψ A (X ∪ {x}) -ψ A (X) of x ∈ S given X ⊆ S is the ITL and VTL objective, respectively. Proof. For ITL, ∆ A (x | X) = I(f A ; y X , y x ) -I(f A ; y X ) = H[f A | y X ] -H[f A | y X , y x ] = I(f A ; y x | y X )which is precisely the ITL objective.For VTL,∆ A (x | X) = tr Var[f A | y X ] -tr Var[f A | y X , y x ] = -tr Var[f A | y X , y x ] + constwhich is precisely the VTL objective.Definition C.3 (Submodularity). ψ A is submodular if and only if for all x ∈ S and X ′ ⊆ X ⊆ S, ∆ A (x | X ′ ) ≥ ∆ A (x | X).Theorem C.4 (Nemhauser et al. (1978) ). Let Assumption 3.1 hold. For any n ≥ 1, if ITL or VTL selected x 1:n , respectively, thenψ A (x 1:n ) ≥ (1 -1/e) max X⊆S |X|≤n ψ A (X).Proof. This is a special case of a canonical result from non-negative monotone submodular function maximization (Nemhauser et al., 1978; Krause & Golovin, 2014) .Recall the non-adaptive optimization problemB n,k = arg max B⊆S |B|=k I(f A ; y B | D n-1 )from Equation (3) with batch size k > 0, and denote by B ′ n,k = x n,1:k the greedy approximation from Equation (3). The selection of an individual batch can be seen as a single non-adaptive optimization problem with marginal gain∆ n (x | B) = I(f A ; y B , y x | D n-1 ) -I(f A ; y B | D n-1 ) = H[f A | D n-1 , y B ] -H[f A | D n-1 , y B , y x ] = I(f A ; y x | D n-1 , y B )and which is precisely the objective function of ITL from Equation (3). Hence, the approximation guarantees from Theorems C.4 and C.11 apply. The derivation is analogous for VTL.Prior work has shown that the greedy solution B ′ n is also competitive with a fully sequential "batchless" decision rule (Chen & Krause, 2013; Esfandiari et al., 2021) .We will now show that "downstream synergies", if present, can be seen as a source of learning complexity, which is orthogonal to the information capacity γ n .Example C.5. Consider the example where f is a stochastic process of three random variables X, Y, Z where X and Y are Bernoulli (p = 1 2 ), and Z is the XOR of X and Y . Suppose that observations are exact (i.e., ε n = 0), that the target space A comprises the output variable Z while the sample space S comprises the input variables X and Y . Observing any single X or Y yields no information about Z: I(Z; X) = I(Z; Y ) = 0, however, observing both inputs jointly perfectly determines Z: I(Z; X, Y ) = 1. Thus, γ n (A; S) = 1 if n ≥ 2 and γ n (A; S) = 0 else.Learning about Z in examples of this kind is difficult for agents that make decisions greedily, since the next action (observing X or Y ) yields no signal about its long-term usefulness. We call a sequence of observations, such as {X, Y }, synergistic since its combined information value is larger than the individual values. The prevalence of synergies is not captured by the information capacity γ n (A; S) since it measures only the joint information gain of n samples within S. Instead, the prevalence of synergies is captured by the sequenceΓ n def = max x∈S ∆ A (x | x 1:n ), which measures the maximum information gain of y n+1 . If Γ n > Γ n-1 at any round n, this indicates a synergy. The following key object measures the additional complexity due to synergies.Definition C.6 (Task complexity). For n ≥ 1, assuming Γ i > 0 for all 1 ≤ i ≤ n, we define the task complexity asα A,S (n) def = max i∈{0,...,n-1} Γ n-1 Γ i .Note that α A,S (n) is large only if the information gain of y n is larger than that of a previous observation y i . Intuitively, if α A,S (n) is large, the agent had to discover the implicit intermediate observations y 1 , . . . , y n-1 that lead to downstream synergies. We will subsequently formalize the intimate connections of the task complexity to synergies and submodularity. Note that in the GP setting, α A,S (n) can be computed online by keeping track of the smallest Γ i during previous rounds i. Further, note that α A,S (n) ≤ 1 if ψ A is submodular.Another object will prove useful in our analysis of synergies.Consider an alternative multiplicative interpretation of the multivariate information gain (cf. Equation ( 7)), which we call the information ratio of X ⊆ S given D ⊆ S, |X|, |D| < ∞:EQUATIONObserve that κ(X | D) measures the synergy properties of y X with respect tof A given y D in a multiplicative sense. That is, if κ(X | D) > 1 then information in y X is redundant, whereas if κ(X | D) < 1 then information in y X is synergistic, and if κ(X | D) = 1 then y X do not mutually interact with respect to f A (all given y D ). In the degenerate case where ∆ A (X | D) = 0 (which implies x∈X ∆ A (x | D) = 0) we therefore let κ(X | D) = 1.The information ratio of ITL is strictly positive in the Gaussian case We prove the following straightforward lower bound to the information ratio of ITL.Lemma C.7. Let X, D ⊆ S, |X|, |D| < ∞. If f A and y X∪D are jointly Gaussian then κ(X | D) > 0.Proof. W.l.o.g. assume D = ∅. We let X = {x 1 , . . . , x k } and prove lower and upper bound separately. We assume w.l.o.g. thatI(f A ; y X ) > 0 which implies |Var[f A | y X ]| < |Var[f A ]|.Thus, there exists some i such that f A and y xi are dependent, so|Var[f A | y xi ]| < |Var[f A ]| which implies I(f A ; y xi ) > 0.We therefore conclude that κ(X) > 0.The following example shows that this lower bound is tight.Example C.8 (Synergies of Gaussian random variables, inspired by Section 3 of Barrett (2015) ). Consider the three random variables X, Y , and Z (think A = {X} and S = {Y, Z}) which are jointly Gaussian with mean vector 0 and covariance matrixΣ = 1 a a a 1 0 a 0 1 , for 2a 2 < 1where the constraint on a is to ensure that Σ is positive definite. Computing the mutual information, we haveI(X; Y ) = I(X; Z) = - 1 2 log(1 -a 2 ) and I(X; Y, Z) = -1 2 log(1 -2a 2 ). Therefore, I(X; Y ) + I(X; Z) I(X; Y, Z) = log(1 -2a 2 + a 4 ) log(1 -2a 2 ) < 1.Note thatlim a→ 1 √ 2 log(1 -2a 2 + a 4 ) log(1 -2a 2 ) = 0,and hence -perhaps unintuitively -even if Y and Z are uncorrelated, their information about X may be arbitrarily synergistic.C.4.2 The Submodularity of the Special "Undirected" Case of ITLIn the inductive active learning problem considered in most prior works, where S ⊆ A and f is a Gaussian process, it holds for ITL that α A,S (n) = 1 since all learning targets appear explicitly in S:Lemma C.9. Let S ⊆ A. Then ψ A of ITL is submodular. Proof. Fix any x ∈ S and X ′ ⊆ X ⊆ S. Let X def = X \ X ′ .By the definition of conditional information gain, we have∆ A (x | X) = I(y x ; f A | y X ) = I(y x ; f A , y X ′ | y X ) -I(y x ; y X ′ | y X ). Since for any x ∈ S and X ⊆ S, y x ⊥ y X | f A , this simplifies to I(y x ; f A | y X ) = I(y x ; f A | y X ) -I(y x ; y X ′ | y X ). It then follows from I(y x ; y X ′ | y X ) ≥ 0 that ∆ A (x | X) = I(y x ; f A | y X ) ≤ I(y x ; f A | y X ) = ∆ A (x | X ′ ).This implies that α A,S (n) ≤ 1 for any n and κ(X | D) ≥ 1 for any X, D ⊆ S when S ⊆ A.Building upon the theory of maximizing non-negative monotone submodular functions (Nemhauser et al., 1978; Krause & Golovin, 2014) , Das & Kempe (2018) define the following notion of "approximate" submodularity: Definition C.10 (Submodularity ratio). The submodularity ratio ofEQUATIONwhere they define 0 0 ≡ 1. ψ A is said to be κ-weakly submodular for some κ > 0 if inf n∈N κ A (n) ≥ κ. As a special case of Theorem 6 from Das & Kempe (2018) , applying that ψ A is non-negative and monotone, we obtain the following result. Theorem C.11 (Das & Kempe (2018) ). For any n ≥ 1, if ITL or VTL selected x 1:n , respectively, thenψ A (x 1:n ) ≥ (1 -e -κ A (n) ) max X⊆S |X|≤n ψ A (X). If ψ A is submodular, it is implied that κ A (n) ≥ 1 for all n ≥ 1 in which case Theorem C.11 recovers Theorem C.4.Our following analysis allows for changing target spaces A n and sample spaces S n (cf. Section 5), and to this end, we redefineΓ n def = max x∈Sn ∆ An (x | x 1:n ).The following theorems show that the marginal gains of ITL and VTL converge to zero, and will serve as the main tool for establishing Theorems 3.2 and 3.3. We will abbreviate α A,S (n) by α n . Theorem C.12 (Convergence of Marginal Gain for ITL). Assume that Assumptions B.1 and B.2 are satisfied. Fix any integers n 1 > n 0 ≥ 0, ∆ = n 1 -n 0 + 1 such that for all i ∈ {n 0 , . . . , n 1 -1},A i+1 ⊆ A i and S def = S i+1 = S i . Further, assume |A n0 | < ∞. Then, if the sequence {x i+1 } n1 i=n0was generated by ITL,EQUATION)Proof. We haveΓ n1 = 1 ∆ n1 i=n0 Γ n1 (i) ≤ α n1 ∆ n1 i=n0 Γ i = α n1 ∆ n1 i=n0 max x∈S I(f Ai ; y x | y 1:i ) (ii) = α n1 ∆ n1 i=n0 I(f Ai ; y xi+1 | D i ) (iii) ≤ α n1 ∆ n1 i=n0 I(f An 0 ; y xi+1 | D i ) (iv) = α n1 ∆ n1 i=n0 I(f An 0 ; y xi+1 | y xn 0 +1:i , D n0 ) (v) = α n1 ∆ I(f An 0 ; y xn 0 +1:n 1 +1 | D n0 ) ≤ α n1 ∆ max X⊆S |X|=∆ I(f An 0 ; y X | D n0 ) (vi) ≤ α n1 ∆ max X⊆S |X|=∆ I(f X ; y X | D n0 ) (vii) ≤ α n1 ∆ max X⊆S |X|=∆ I(f X ; y X ) = α n1 γ ∆∆ where (i) follows from the definition of the task complexity α n1 (cf. Definition C.6); (ii) uses the objective of ITL and that the posterior variance of Gaussians is independent of the realization and only depends on the location of observations; (iii) uses A i+1 ⊆ A i and monotonicity of information gain; (iv) uses that the posterior variance of Gaussians is independent of the realization and only depends on the location of observations; (v) uses the chain rule of information gain; (vi) uses y X ⊥ f An 0 | f X and the data processing inequality. The conditional independence follows from the assumption that the observation noise is independent. Similarly, y X ⊥ D n0 | f X which implies (vii).If n 0 = 0, then the bound before line (vi) simplifies to α n1 γ A0,S (∆)/∆.The result for VTL is stated, for simplicity, only for the case where the target space and sample space are fixed. Theorem C.13 (Convergence of Marginal Gain for VTL). Assume that Assumptions B.1 and B.2 are satisfied. Then for any n ≥ 1, if the sequence {x i } n i=1 is generated by VTL,EQUATIONWe remark thatx ′ ∈A γ {x ′ },S (n) ≤ |A|γ A,S (n).Proof. We haveΓ n-1 = 1 n n-1 i=0 Γ n-1 (i) ≤ α n n n-1 i=0 Γ i = α n n n-1 i=0 tr Var[f A | y 1:i ] -min x∈S tr Var[f A | y 1:i , y x ] (ii) = α n n n-1 i=0 tr Var[f A | D i ] -tr Var[f A | D i+1 ] (iii) ≤ σ 2 α n n x ′ ∈A n-1 i=0 log Var[f x ′ | D n ] Var[f x ′ | D n+1 ] = 2σ 2 α n n x ′ ∈A n-1 i=0 I f x ′ ; y xn+1 D n (iv) = 2σ 2 α n n x ′ ∈A n-1 i=0 I f x ′ ; y xn+1 y x1:n (v) = 2σ 2 α n n x ′ ∈A I f x ′ ; y x1:n ≤ 2σ 2 α n n x ′ ∈A max X⊆S |X|=n I(f x ′ ; y X ) = 2σ 2 α n n x ′ ∈A γ {x ′ },S (n)where (i) follows from the definition of the task complexity α n1 (cf. Definition C.6); (ii) follows from the VTL decision rule and that the posterior variance of Gaussians is independent of the realization and only depends on the location of observations; (iii) follows from Lemma C.38 and monotonicity of variance; (iv) uses that the posterior variance of Gaussians is independent of the realization and only depends on the location of observations; and (v) uses the chain rule of mutual information. The remainder of the proof is analogous to the proof of Theorem C.12 (cf. Appendix C.5).Keeping track of the task complexity online In general, the task complexity α n may be larger than one in the "directed" setting (i.e., when S ̸ ⊆ A). However, note that α n can easily be evaluated online by keeping track of the smallest Γ i during previous rounds i.C.6 Proof of Theorem 3.2We will now prove Theorem 3.2. We first prove the convergence of marginal variance within S for ITL, before proving the convergence outside S in Appendix C.6.1.Lemma C.14 (Uniform convergence of marginal variance within S for ITL). Assume that Assumptions B.1 and B.2 are satisfied. For any n ≥ 0 and x ∈ A ∩ S,EQUATIONProof. We haveσ 2 n (x) = Var[f x | D n ] -Var[f x | f x , D n ] 0 (i) = Var[y x | D n ] -ρ 2 (x) -(Var[y x | f x , D n ] -ρ 2 (x)) = Var[y x | D n ] -Var[y x | f x , D n ] (ii) ≤ σ2 log Var[y x | D n ] Var[y x | f x , D n ] = 2σ 2 • I(f x ; y x | D n ) (iii) ≤ 2σ 2 • I(f A ; y x | D n ) (iv) ≤ 2σ 2 • max x ′ ∈S I(f A ; y x ′ | D n ) (v) = 2σ 2 • max x ′ ∈S I(f A ; y x ′ | y 1:n ) = 2σ 2 • Γ nwhere (i) follows from the noise assumption (cf. Assumption B.2); (ii) follows from Lemma C.38 and using monotonicity of variance; (iii) follows from x ∈ A and monotonicity of information gain; (iv) follows from x ∈ S; and (v) uses that the posterior variance of Gaussians is independent of the realization and only depends on the location of observations.We will now show convergence of marginal variance to the irreducible uncertainty for points outside the sample space.Our proof roughly proceeds as follows: We construct an "approximate Markov boundary" of x in S, and show (1) that the size of this Markov boundary is independent of n, and (2) that a small uncertainty reduction within the Markov boundary implies that the marginal variances at the Markov boundary and(!) x are small. Definition C.15 (Approximate Markov boundary). For any ϵ > 0, n ≥ 0, and x ∈ X , we denote by B n,ϵ (x) the smallest (multi-)subset of S such thatEQUATIONWe call B n,ϵ (x) an ϵ-approximate Markov boundary of x in S.Equation ( 14) is akin to the notion of the smallest Markov blanket in S of some x ∈ X (called a Markov boundary) which is the smallest set B ⊆ S such thatf x ⊥ f S | f B .Lemma C.16 (Existence of an approximate Markov boundary). For any ϵ > 0, let k be the smallest integer satisfyingEQUATION)Then, for any n ≥ 0 and x ∈ X , there exists an ϵ-approximate Markov boundary B n,ϵ (x) of x in S with size at most k.Lemma C.16 shows that for any ϵ > 0 there exists a universal constant b ϵ (with respect to n and x)EQUATION)We defer the proof of Lemma C.16 to Appendix C.6.3 where we also provide an algorithm to compute B n,ϵ (x).Lemma C.17. For any ϵ > 0, n ≥ 0, and x ∈ X ,σ 2 n (x) ≤ 2σ 2 • I(f x ; y Bn,ϵ(x) | D n ) + η 2 S (x) + ϵ (17)where B n,ϵ (x) is an ϵ-approximate Markov boundary of x in S.Proof. We haveσ 2 n (x) = Var[f x | D n ] -η 2 S (x) + η 2 S (x) (i) ≤ Var[f x | D n ] -Var[f x | y Bn,ϵ(x) , D n ] + η 2 S (x) + ϵ (ii) ≤ σ 2 log Var[f x | D n ] Var[f x | y Bn,ϵ(x) , D n ] + η 2 S (x) + ϵ = 2σ 2 • I(f x ; y Bn,ϵ(x) | D n ) + η 2 S (x) + ϵwhere (i) follows from the defining property of an ϵ-approximate Markov boundary (cf. Equation ( 14)); and (ii) follows from Lemma C.38 and using monotonicity of variance.Lemma C.18. For any ϵ > 0, n ≥ 0, and x ∈ A,EQUATION)where B n,ϵ (x) is an ϵ-approximate Markov boundary of x in S, |B n,ϵ (x)| ≤ b ϵ , and where κn (•)def = κ(• | x 1:n ) denotes the information ratio from Equation (8).We remark that κn (•) > 0 as is shown in Lemma C.7, and hence, the right-hand side of the inequality is well-defined.Proof. We use the abbreviated notation B = B n,ϵ (x). We haveI(f x ; y B | D n ) (i) ≤ I(f A ; y B | D n ) (ii) ≤ 1 κn,bϵ x∈B I(f A ; y x | D n ) (iii) ≤ b ϵ κn,bϵ max x∈B I(f A ; y x | D n ) (iv) ≤ b ϵ κn,bϵ max x∈S I(f A ; y x | D n ) (v) = b ϵ κn,bϵ max x∈S I(f A ; y x | y 1:n ) = b ϵ κn,bϵ Γ nwhere (i) follows from monotonicity of mutual information; (ii) follows from the definition of the information ratio κn,bϵ (cf. Equation ( 8)); (iii) follows from b ≤ b ϵ ; (iv) follows from B ⊆ S; and (v) uses that the posterior variance of Gaussians is independent of the realization and only depends on the location of observations.Proof of Theorem 3.2 for ITL . The case where x ∈ A ∩ S is shown by Lemma C.14 with C = 2σ 2 .To prove the more general result, fix any x ∈ A and ϵ > 0. By Lemma C.16, there exists an ϵ-approximate Markov boundaryB n,ϵ (x) of x in S such that |B n,ϵ (x)| ≤ b ϵ . We have σ 2 n (x) (i) ≤ 2σ 2 • I(f x ; y Bn,ϵ(x) | D n ) + η 2 S (x) + ϵ (ii) ≤ 2σ 2 b ϵ κn (B n,ϵ (x)) Γ n + η 2 S (x) + ϵwhere (i) follows from Lemma C.17; and (ii) follows from Lemma C.18.Let ϵ = c γ √ n √ n with c = 2|S|σ 2 σ2 /λ min (K SS ).Then, by Equation ( 15), b ϵ can be bounded for instance by √ n. Together with Theorem C.12 this implies for ITL thatσ 2 n (x) ≤ η 2 S (x) + 2σ 2 √ n Γ n + cγ √ n / √ n ≤ η 2 S (x) + c ′ γ n / √ n for a constant c ′ , e.g., c ′ = 2σ 2 + c.C.6.2 Convergence outside S for VTL Proof of Theorem 3.2 for VTL . Analogously to Lemma C.17, we haveσ 2 n (x) = Var[f x | D n ] -η 2 S (x) + η 2 S (x) (i) ≤ Var[f x | D n ] -Var[f x | y Bn,ϵ(x) , D n ] + η 2 S (x)+ ϵ where (i) follows from the defining property of an ϵ-approximate Markov boundary (cf. Equation ( 14)). Further, we haveVar[f x | D n ] -Var[f x | y Bn,ϵ(x) , D n ] (i) ≤ x∈Bn,ϵ(x) (Var[f x | D n ] -Var[f x | y x, D n ]) (ii) ≤ x∈Bn,ϵ(x) (tr Var[f A | y 1:n ] -tr Var[f A | y x, y 1:n ]) (iii) ≤ b ϵ Γ nwhere (i) follows from the submodularity of ψ A ; (ii) uses that the posterior variance of Gaussians is independent of the realization and only depends on the location of observations; and (iii) follows from the definition of Γ n and Lemma C.16.The remainder of the proof is analogous to the result for ITL, using Theorem C.13 to bound Γ n .We now derive Lemma C.16 which shows the existence of an approximate Markov boundary of x in S. Lemma C.19. For any S ⊆ S and k ≥ 0, there exists B ⊆ S with |B| = k such that for all x ′ ∈ S,EQUATION)Proof. We choose B ⊆ S greedily using the acquisition functionxk def = arg max x∈S I(f S ; y x | y B k-1 )where B k = x1:k . Note that this is the "undirected" special case of ITL, and hence, we haveVar f x ′ | y B k (i) ≤ 2σ 2 Γ k (ii)≤ 2σ 2 γ k k where (i) is due to Lemma C.14; and (ii) is due to Theorem C.12 and α S,S (k) ≤ 1.Lemma C.20. Given any ϵ > 0 and B ⊆ S ⊆ S with |S| < ∞, such that for any x ′ ∈ S,EQUATION)Then for any x ∈ X ,EQUATIONProof. We will denote the right-hand side of Equation ( 20) by ϵ ′ . We haveVar[f x | y B ] (i) = E f S [Var fx [f x | f S , y B ] | y B ] + Var f S [E fx [f x | f S , y B ] | y B ] (ii) = Var fx [f x | f S , y B ] + Var f S [E fx [f x | f S , y B ] | y B ] (iii) = Var fx [f x | f S ] irreducible uncertainty + Var f S [E fx [f x | f S ] | y B ] reducible (epistemic) uncertaintywhere (i) follows from the law of total variance; (ii) uses that the conditional variance of a Gaussian depends only on the location of observations and not on their value; and (iii)follows from f x ⊥ y B | f S since B ⊆ S.It remains to bound the reducible uncertainty.Leth x : R d → R, f S → E[f x | f S ]where we write d def = |S|. Using the formula for the GP posterior mean, we haveh x (f S ) = E[f x ] + z ⊤ (f S -E[f S ])wherez def = K -1 SS K Sx .Because h is a linear function in f S we have for the reducible uncertainty thatVar f S [h x (f S ) | y B ] = z ⊤ Var[f S | y B ]z (i) ≤ d • z ⊤ diag Var[f S | y B ]z (ii) ≤ ϵ ′ d z ⊤ z = ϵ ′ d K xS K -1 SS K -1 SS K Sx ≤ ϵ ′ d λ min (K SS ) K xS K -1 SS K Sx (iii) ≤ ϵ ′ dσ 2 λ min (K SS )where (i) follows from Lemma C.37; (ii) follows from the assumption that Var[f x ′ | y B ] ≤ ϵ ′ for all x ′ ∈ S; and (iii) follows fromK xS K -1 SS K Sx ≤ K xx = σ 2 since K xx -K xS K -1 SS K Sx ≥ 0.Proof of Lemma C.16. Let B ⊆ S be the set of size k generated by Lemma C.19 to satisfyVar[f x ′ | y B ] ≤ 2σ 2 γ k /k for all x ′ ∈ S.We have for any x ∈ X ,Var[f x | D n , y B ] (i) ≤ Var[f x | y B ] (ii) ≤ Var[f x | f S ] + ϵwhere (i) follows from monotonicity of variance; and (ii) follows from Lemma C.20; using |S| < ∞ and the condition on k.We remark that Lemma C.19 provides an algorithm (just "undirected" ITL!) to compute an approximate Markov boundary, and the set B returned by this algorithm is a valid approximate Markov boundary for all x ∈ X . One can simply swap-in ITL with target space {x} for "undirected" ITL to obtain tighter (but instance-dependent) bounds on the size of the approximate Markov boundary.In this subsection we generalize Theorem 3.2 to continuous sample spaces S. We will make the following assumption:Assumption C.21. The RKHS of the kernel k is finite dimensional. In other words, the kernel k can be expressed as k(x, x ′ ) = ϕ(x) ⊤ ϕ(x ′ ) for some feature map ϕ : X → R d with d < ∞.In the following, we will denote the design matrix of the sample space S by Φ def = [ϕ(x) : x ∈ S] ⊤ ∈ R |S|×d , and we denote by Π Φ its orthogonal projection onto the orthogonal complement of the span of Φ. In particular, it holds that 1. Π Φ v = 0 for all v ∈ span Φ, and 2.Π Φ v = v for all v ∈ (span Φ) ⊥ .Especially, v ∈ ker Π Φ if and only if v ∈ span Φ. This projection can be computed as follows: Lemma C.22. It holds thatEQUATION)Proof. Φ ⊤ (ΦΦ ⊤ ) -1 Φ is the orthogonal projection onto the span of Φ (see, e.g., Strang, 2016, page 211) .Lemma C.23. Under Assumption C.21, the irreducible uncertaintyEQUATION)where∥v∥ A = √ v ⊤ Av denotes the Mahalanobis distance.Proof. This is an immediate consequence of the formula for the conditional variance of multivariate Gaussians (cf. Appendix B.2), applied to the linear kernel.Lemmas C.22 and C.23 imply that η 2 S (x ∥ ) = 0 for all x ∥ ∈ X with ϕ(x ∥ ) ∈ span Φ. That is, the irreducible uncertainty is zero for points in the span of the sample space. In contrast, for points x ⊥ with ϕ(x ⊥ ) ∈ (span Φ) ⊥ , the irreducible uncertainty equals the initial uncertainty:η 2 S (x ⊥ ) = σ 2 0 (x ⊥ ).The irreducible uncertainty of any other point x can be computed by simple decomposition of ϕ(x) into parallel and orthogonal components.Assuming that Assumption C.21 holds and given any (non-finite) S ⊆ X , there exists a basis Ω S ⊆ X in the space of embeddings ϕ(•) such that span S = span Ω S and |Ω S | ≤ d. The generalized existence of an approximate Markov boundary for continuous domains can then be shown analogously to Lemma C.16: Lemma C.24 (Existence of an approximate Markov boundary for a continuous domain). Let S be any (continuous) subset of X and let Assumption C.21 hold with d < ∞. Further, for any ϵ > 0, let k be the smallest integer satisfyingEQUATION)Then, for any n ≥ 0 and x ∈ X , there exists an ϵ-approximate Markov boundary B n,ϵ (x) of x in S with size at most k.Proof sketch. The proof follows analogously to Lemma C.16 by conditioning on the finite set Ω S as opposed to S.We first formalize the assumptions of Theorem 3.3: Assumption C.25 (Regularity of f ⋆ ). We assume that f ⋆ is in a reproducing kernel Hilbert space H k (X ) associated with a kernel k and has bounded norm, that is, ∥f ⋆ ∥ k ≤ B for some finite B ∈ R. Assumption C.26 (Sub-Gaussian noise). We further assume that each ε n from the noise sequence {ε n } ∞ n=1 is conditionally zero-mean ρ(x n )-sub-Gaussian with known constants ρ(x) > 0 for all x ∈ X . Concretely,∀n ≥ 1, λ ∈ R : E e λϵn D n-1 ≤ exp λ 2 ρ 2 (x n ) 2where D n-1 corresponds to the σ-algebra generated by the random variables {x i , ϵ i } n-1 i=1 and x n .We make use of the following foundational result, showing that under the above two assumptions the (misspecified) Gaussian process model from Section 3.1 is an all-time well-calibrated model of f ⋆ : Lemma C.27 (Well-calibrated confidence intervals; Abbasi-Yadkori (2013); Chowdhury & Gopalan (2017) ). Pick δ ∈ (0, 1) and let Assumptions C.25 and C.26 hold. Letβ n (δ) = ∥f ⋆ ∥ k + ρ 2(γ n + 1 + log(1/δ))where ρ = max x∈X ρ(x).10 Then, for all x ∈ X and n ≥ 0 jointly with probability at least 1 -δ,|f ⋆ (x) -µ n (x)| ≤ β n (δ) • σ n (x)where µ n (x) and σ 2 n (x) are mean and variance (as defined in Appendix B.2) of the GP posterior of f (x) conditional on the observations D n , pretending that ε i is Gaussian with variance ρ 2 (x i ).The proof of Theorem 3.3 is a straightforward application of Lemma C.27 and Theorem 3.2:Proof of Theorem 3.3. By Theorem 3.2, we have that for all x ∈ A,σ n (x) ≤ η 2 S (x) + ν 2 A,S (n) ≤ η S (x) + ν A,S (n).The result then follows by application of Lemma C.27.C.8 Proof of Theorem 5.1In this section, we derive our main result on Safe BO. In Appendix C.8.1, we give the definition of the reachable safe set R and derive the conditions under which convergence to the reachable safe set is guaranteed. Then, in Appendix C.8.2, we prove Theorem 5.1.In the agnostic setting from Section 3.2 (i.e., under Assumptions C.25 and C.26), Lemma C.27 provides us with the following (1 -δ)-confidence intervals (CIs)EQUATIONwhereC -1 (x) = R. We write u n (x) def = max C n (x), l n (x) def = min C n (x), and w n (x) def = u n (x) -l n (x) for its upper bound, lower bound, and width, respectively.We learn separate statistical models f and {g 1 , . . . , g q } for the ground truth objective f ⋆ and ground truth constraints {g ⋆ 1 , . . . , g ⋆ q }. We write I def = {f, 1, . . . , q} and collect the constraints in I s def = {1, . . . , q}. Without loss of generality, we assume that the confidence intervals include the ground truths with probability at least 1 -δ jointly for all i ∈ I.11 For i ∈ I, denote by u n,i , l n,i , w n,i , η i , β n,i the respective quantities. In the following, we do not explicitly denote the dependence of β n on δ.To improve clarity, we will refer to the set of potential maximizers defined in Equation ( 5) as M n and denote by A n an arbitrary target space.We point out the following corollary: Corollary C.28 (Safety). With high probability, jointly for any n ≥ 0 and any i ∈ I s ,EQUATIONC.8.1 Convergence to Reachable Safe Set Definition C.29 (Reachable safe set). Given any pessimistic safe set S ⊆ X and any ϵ ≥ 0 and β ≥ 0, we define the reachable safe set up to (ϵ, β)-slack and its closure asR ϵ,β (S) def = S ∪ {x ∈ X \ S | g ⋆ i (x) -β(η i (x; S) + ϵ) ≥ 0 for all i ∈ I s } Rϵ,β (S) def = lim n→∞ (R ϵ,β ) n (S)where (R ϵ,β ) n denotes the n-th composition of R ϵ,β with itself.Remark C.30. Convergence of the safe set to the closure of the reachability operator can only be guaranteed for finite safe sets (|S ⋆ | < ∞). The following proofs readily generalize to continuous domains by considering convergence within the k-th composition of the reachability operator with itself for some k < ∞. In this case the sample complexity grows with k rather than |S ⋆ |. The only required modification is to lift the assumption of Theorem C.12 that information is gained only while safe sets remain constant (i.e., S i+1 = S i for all i). This assumption is straightforward to lift since for any n ≥ 0 and T ≥ 1,max x∈Sn ∆ A (x | x 1:n+T ) ≤ 1 T T t=1 max x∈Sn ∆ A (x | x 1:n+t ) ≤ 1 T T t=1 max x∈Sn+t ∆ A (x | x 1:n+t ) ≤ γ T T ,using submodularity for the first inequality and the monotonicity of the safe set for the second inequality. In particular, this shows that one continues learning about points in the original safe seteven as the safe set grows.We denote by S 0 the initial pessimistic safe set induced by the (prior) statistical model g (cf. Section 5) and write Rϵ,β def = Rϵ,β (S 0 ). Lemma C.31 (Properties of the reachable safe set). For all S, S ′ ⊆ X , ϵ ≥ 0, and β ≥ 0:(i) S ′ ⊆ S =⇒ R ϵ,β (S ′ ) ⊆ R ϵ,β (S), (ii) R ϵ,β (S) ⊆ S =⇒ Rϵ,β (S) ⊆ S, and (iii) R 0,0 (∅) = R0,0 = S ⋆ .Proof (adapted from lemma 7.1 of Berkenkamp et al. (2021) ).1. Let x ∈ R ϵ,β (S ′ ). If x ∈ S then x ∈ R ϵ,β (S), so let x ̸ ∈ S. Then, by defi- nition, for all i ∈ I s , f ⋆ i (x) -βη i (x; S ′ ) -ϵ ≥ 0.By the monotonicity of variance, η i (x; S ′ ) ≥ η i (x; S) for all i ∈ I, and hencef ⋆ i (x) -βη i (x; S) -ϵ ≥ 0 for all i ∈ I s . It follows that x ∈ R ϵ,β (S).2. By the monotonicity of variance, η i (x; R ϵ,β (S)) ≥ η i (x; S) for all x ∈ X and i ∈ I. Thus, by definition of the safe region, we have that R ϵ,β (R ϵ,β (S)) ⊆ S. The result follows by taking the limit.3. The result follows directly from the definition of the true safe set S ⋆ (cf. Equation ( 4)).Clearly, we cannot expand the safe set beyond R0,0 . The following is our main intermediate result,showing that either we expand the safe set at some point or the uncertainty converges to the irreducible uncertainty.Lemma C.32. Given any n 0 ≥ 0, ϵ > 0, let n ′ be the smallest integer such that ν n ′ ,ε 2 ≤ ε where ε = ϵ/2. Let β n0+n ′ = max i∈Is β n0+n ′ ,i . Assume that the sequence of target spaces is monotonically decreasing, i.e., A n+1 ⊆ A n . Then, we have with high probability (at least) one of ∀x ∈ A n0+n ′ , ∀i ∈ I :w n0+n ′ ,i (x) ≤ β n0+n ′ [η i (x; S n0+n ′ ) + ϵ] and A n0+n ′ ∩ R ϵ,β n 0 +n ′ (S n0+n ′ ) ⊆ S n0+n ′ or |S n0+n ′ +1 | > |S n0 |. Proof. Suppose that |S n0+n ′ +1 | = |S n0 |.Then, by Theorem 3.3 (using that the sequence of target spaces is monotonically decreasing), for any x ∈ A n0+n ′ and i ∈ I,w n0+n ′ ,i (x) ≤ β n0+n ′ [η i (x; S n0+n ′ ) + ϵ].As S n0+n ′ +1 = S n0+n ′ we have for all x ∈ A n0+n ′ \ S n0+n ′ and i ∈ I s , with high probability that0 > l n0+n ′ ,i (x) ≥ g ⋆ i (x) -w n0+n ′ ,i (x) ≥ g ⋆ i (x) -β n0+n ′ [η i (x; S n0+n ′ ) + ϵ]. It follows that A n0+n ′ ∩ R ϵ,β n 0 +n ′ (S n0+n ′ ) ⊆ S n0+n ′ .To gather more intuition about the above lemma, consider the target spaceEQUATIONWe call E n the potential expanders since it contains all points which might be safe, but are not yet known to be safe. Under this target space, the above lemma simplifies slightly: Lemma C.33. For any n ≥ 0 and ϵ, β ≥ 0, if E n ⊆ A n then with high probability,S n ∪ (A n ∩ R ϵ,β (S n )) = R ϵ,β (S n ). Proof. With high probability, R ϵ,β (S n ) ⊆ S n = S n ∪ E n .The lemma is a direct consequence.The above lemmas can be combined to yield our main result of this subsection, establishing the convergence of ITL to the reachable safe set.Theorem C.34 (Convergence to reachable safe set). For any ϵ > 0, let n ′ be the smallest integer satisfying the condition of Lemma C.32, and definen ⋆ def = (|S ⋆ | + 1)n ′ . Let βn ⋆ ≥ β n,i for all n ≤ n ⋆ , i ∈ I s .Assume that the sequence of target spaces is monotonically decreasing, i.e., A n+1 ⊆ A n . Then, the following inequalities hold jointly with probability at least 1 -δ:(i) ∀n ≥ 0, ∀i ∈ I s : g ⋆ i (x n ) ≥ 0, safety (ii) A n ⋆ ∩ Rϵ, βn ⋆ ⊆ S n ⋆ ⊆ R0,0 = S ⋆ , convergence to safe region (iii) ∀x ∈ A n ⋆ , ∀i ∈ I : w n ⋆ ,i (x) ≤ βn ⋆ η i (x; Rϵ, βn ⋆ ) + ϵ, convergence of width (iv) ∀x ∈ Rϵ, βn ⋆ , ∀i ∈ I : η i (x; Rϵ, βn ⋆ ) = 0.convergence of width within safe region Proof. (i) is a direct consequence of Corollary C.28. S n ⋆ ⊆ S ⋆ follows directly from the pessimistic safe set S n ⋆ from (ii) being a subset of the true safe set S ⋆ . (iv) follows directly from the definition of irreducible uncertainty. Thus, it remains to establish A n ⋆ ∩ Rϵ, βn ⋆ ⊆ S n ⋆ and (iii).Recall that with high probability |S n | ∈ [0, |S ⋆ |] for all n ≥ 0. Thus, the size of the pessimistic safe set can increase at most |S ⋆ | many times. By Lemma C.32, using the assumption on n ′ , the size of the pessimistic safe set increases at least once every n ′ iterations, or else:EQUATION)Because the safe set can expand at most |S ⋆ | many times, Equation ( 28) occurs eventually for somen 0 ≤ |S ⋆ |n ′ . In this case, since βn ⋆ ≥ β n0+n ′ and A n ⋆ ⊆ A n0+n ′ (as n 0 + n ′ ≤ n ⋆ ) we have that A n ⋆ ∩ R ϵ, βn ⋆ (S n0+n ′ ) ⊆ A n0+n ′ ∩ R ϵ,β n 0 +n ′ (S n0+n ′ ) ⊆ S n0+n ′ .By Lemma C.31 (ii), this impliesA n ⋆ ∩ Rϵ, βn ⋆ ⊆ S n0+n ′ ⊆ S n ⋆ .We emphasize that Theorem C.34 holds for arbitrary target spaces A n . If additionally, E n ⊆ A n for all n ≥ 0 then by Lemma C.33, Theorem C.34 (ii) strengthens to Rϵ, βn ⋆ ⊆ S n ⋆ . Intuitively, E n ⊆ A n ensures that one aims to expand the safe set in all directions. Conversely, if E n ̸ ⊆ A n then one aims only to expand the safe set in the direction of A n (or not at all if A n ⊆ S n )."Free" convergence guarantees in many applications Theorem C.34 can be specialized to yield convergence guarantees in various settings by choosing an appropriate target space A n . Straightforward application of Theorem C.34 (informally) requires that the sequence of target spaces is monotonically decreasing (i.e., A n+1 ⊆ A n ), and that each target space A n is an "over-approximation" of the actual set of targeted points (such as the set of optimas in the Bayesian optimization setting). We discuss two such applications in the following.1. Pure expansion: For example, for the target space E n , Theorem C.34 bounds the convergence of the safe set to the reachable safe set. In this case, the transductive active learning problem corresponds to the "pure expansion" setting, also addressed by the ISE baseline discussed in Section 5. The ISE baseline, however, does not establish convergence guarantees of the kind of Theorem C.34. Note that E n satisfies the (informal) requirements laid out previously, since it is monotonically decreasing by definition, and with high probability, any point x ∈ S ⋆ that is not in S n is contained within E n .2. Level set estimation: Given any τ ∈ R, we denote the (safe) τ -level set of f ⋆ byL τ def = {x ∈ S ⋆ | f ⋆ (x) = τ }.We define the potential level set asEQUATION)That is, L τ n is the subset of the optimistic safe set S n where the τ -level set of f ⋆ may be located. Analogously to the potential expanders, it is straightforward to show that L τ n over-approximates the true τ -level set and is monotonically decreasing.We remark that our guarantees from this section also apply to the standard ("unsafe") setting where S ⋆ = S 0 = X .In this section, we specialize Theorem C.34 for the case that the target space contains the potential maximizers M n (cf. Equation ( 5)). It is straightforward to see that the sequence M n is monotonically decreasing (i.e., M n+1 ⊆ M n ). The following lemma shows that the potential maximizers overapproximate the set of safe maxima X * def = arg max x∈S ⋆ f ⋆ (x). Lemma C.35 (Potential maximizers over-approximate safe maxima). For all n ≥ 0 and with probability at least 1 -δ,(i) x ∈ X * implies x ∈ M n and (ii) x ̸ ∈ M n implies x ̸ ∈ X * . Proof. If x ̸ ∈ M n then u n,f (x) < max x ′ ∈Sn l n,f (x ′ ) ≤ max x ′ ∈S ⋆ l n,f (x ′ )where we used S n ⊆ S ⋆ with high probability, which directly implies with high probability that x ̸ ∈ X * .For the other direction, if x ∈ X * thenu n,f (x) ≥ max x ′ ∈S ⋆ l n,f (x ′ ) ≥ max x ′ ∈Sn l n,f (x ′ )with high probability.We denote the set of optimal actions which are safe up to (ϵ, β)-slack byX * ϵ,β def = arg max x∈ Rϵ,β f ⋆ (x),and by f * ϵ,β the maximum value attained by f ⋆ at any of the points in X * ϵ,β . The regret can be expressed asr n ( Rϵ,β ) = f * ϵ,β -f ⋆ ( x n )The following theorem formalizes Theorem 5.1 and establishes convergence to the safe optimum.Theorem C.36 (Convergence to safe optimum). For any ϵ > 0, let n ′ be the smallest integer satisfying the condition of Lemma C.32, and define n ⋆ def = (|S ⋆ | + 1)n ′ . Let βn ⋆ ≥ β n,i for all n ≤ n ⋆ , i ∈ I s . Then, the following inequalities hold jointly with probability at least 1 -δ:(i) ∀n ≥ 0, ∀i ∈ I s : g ⋆ i (x n ) ≥ 0, safety (ii) ∀n ≥ n ⋆ : r n ( Rϵ, βn ⋆ ) ≤ ϵ.convergence to safe optimum Proof. Fix any x * ∈ X * ϵ, βn ⋆ ⊆ Rϵ, βn ⋆ . Assume w.l.o.g. that x * ∈ M n ⋆ .12 Then, with high probability,f * ϵ, βn ⋆ = f ⋆ (x * ) ≤ u n ⋆ ,f (x * ) = l n ⋆ ,f (x * ) + w n ⋆ ,f (x * ) (i) ≤ l n ⋆ ,f ( x n ⋆ ) + w n ⋆ ,f (x * ) ≤ f ⋆ ( x n ⋆ ) + w n ⋆ ,f (x * ) (ii) ≤ f ⋆ ( x n ⋆ ) + ϵwhere (i) follows from the definition of x n ; and (ii) follows from Theorem C.34 and noting thatx * ∈ M n ⋆ ∩ Rϵ, βn ⋆ .We have shown thatf ⋆ ( x n ⋆ ) ≥ f * ϵ, βn ⋆ -ϵ, which implies r n ⋆ ( Rϵ, βn ⋆ ) ≤ ϵ.Since the upper-and lower-confidence bounds are monotonically decreasing / increasing, respectively, we have that for all n ≥ n ⋆ , r n ( Rϵ, βn ⋆ ) ≤ ϵ.We denote by ⪯ the Loewner partial ordering of symmetric matrices. Lemma C.37. Let A ∈ R n×n be a positive definite matrix with diagonal D. Then, A ⪯ nD.Proof. Equivalently, one can show nD -A ⪰ 0. We write A def = D1 /2 QD 1 /2 , and thus, Q = D -1 /2 AD -1 /2 is a positive definite symmetric matrix with all diagonal elements equal to 1. It remains to show thatEQUATION)If additionally, a ≥ M ′ for someEQUATION)Proof. Let f (x) def = log x. By the mean value theorem, there exists c ∈ (a, b) such that1 c = f ′ (c) = f (b) -f (a) b -a = log b -log a b -a = log( b a ) b -a . Thus, b -a = c • log b a < M • log b a .Under the additional condition that a ≥ M ′ , we obtainb -a = c • log b a > M ′ • log b a .We give a brief overview of interpretations and approximations of ITL, as well as alternative decision rules adhering to the fundamental principle ( †).The discussed interpretations of ( †) differ mainly in how they quantify the "uncertainty" about A. In the GP setting, this "uncertainty" is captured by the covariance matrix Σ of f A , and we consider two main ways of "scalarizing" Σ:1. the total (marginal) variance tr Σ, and 2. the "generalized variance" |Σ|.The generalized variance -which was originally suggested by Wilks (1932) as a generalization of variance to multiple dimensions -takes into account correlations. In contrast, the total variance discards all correlations between points in A.All discussed decision rules following principle ( †) (i.e., ITL, VTL, MM-ITL) differ only in their weighting of the points in A, and they coincide when |A| = 1.We briefly discuss three interpretations of ITL.Minimizing generalized variance In the GP setting, ITL can be equivalently characterized as minimizing generalized posterior variance:EQUATION)Maximizing relevance and minimizing redundancy An alternative interpretation of ITL isEQUATION)whereI(f A ; y x ; D n ) = I(f A ; y x ) -I(f A ; y x | D n ) denotes the multivariate information gain (cf. Appendix B).In this way, ITL can be seen as maximizing observation relevance while minimizing observation redundancy. This interpretation is common in the literature on feature selection (Peng et al., 2005; Vergara & Estévez, 2014; Beraha et al., 2019) .Steepest descent in measure spaces ITL can be seen as performing steepest descent in the space of probability measures over f A , with the KL divergence as metric:I(f A ; y x | D n ) = E yx [KL(p(f A | D n , y x )∥p(f A | D n ))].That is, ITL finds the observation yielding the "largest update" to the current density.Quantifying the uncertainty about f A by the marginal variance of points in A rather than entropy (or generalized variance), the principle ( †) leads to VTL. Note that if |A| = 1, then VTL is equivalent to ITL. Unlike the similar, but more technical, TRUVAR algorithm proposed by Bogunovic et al. (2016) , VTL does not require truncated variances, and hence, VTL can be applied to constrained settings (where A ̸ ⊆ S) as well.Relationship to ITL Note that the ITL criterion in the GP setting can be expressed asEQUATIONwhere for a positive semi-definite matrix A with spectral decomposition A = V ΛV ⊤ we write log A = V log ΛV ⊤ for the logarithmic matrix function. To derive Equation (34) we use that log |A| = i log λ i (A) = tr log A. Hence, ITL and VTL are identical up to a different weighting of the eigenvalues of the posterior covariance matrix.Minimizing a bound to the approximation error Chowdhury & Gopalan (2017) (page 19) bound the approximation error |f ⋆ (x) -µ n (x)| by|k t (x) ⊤ (K t + P t ) -1 ε 1:t | variance + |f ⋆ (x) -k t (x) ⊤ (K t + P t ) -1 f 1:t | bias where k t (x) def = K xx1:t , K t def= K x1:tx1:t , and P t def = P x1:t . Similar to a standard bias-variance decomposition, the first term measures variance and the second term measures bias. Following Lemma C.27, VTL can be seen as greedily minimizing this bound to the approximation error (i.e., both bias and variance).Maximizing correlation to prediction targets weighted by their variance It can be shown (see the proof below) that the VTL decision rule is equivalent toEQUATION)That is, VTL maximizes the squared correlation between the next observation and the prediction targets, weighted by their variance. Intuitively, prediction targets are weighted by their variance since more can be learned about a prediction target with higher variance. This is precisely what leads to the "diverse" sample selection, and is akin to "uncertainty sampling" among the prediction targets and then selecting the observation which is most correlated with the selected prediction target.Proof. Starting with the VTL objective, we have arg minx∈S x ′ ∈A Var[f x ′ | D n , y x ] = arg min x∈S x ′ ∈A Var[f x ′ | D n ] - Cov[f x ′ , y x | D n ] 2 Var[y x | D n ] = arg max x∈S x ′ ∈A Var[f x ′ | D n ] • Cov[f x ′ , y x | D n ] 2 Var[f x ′ | D n ] • Var[y x | D n ] + const = arg max x∈S x ′ ∈A Var[f x ′ | D n ] • Cor[f x ′ , y x | D n ] 2 + const.MacKay (1992) previously proposed "mean-marginal" ITL (MM-ITL) in the setting where S = X , which selectsEQUATIONand which simplifies in the GP setting toEQUATIONAnalogously to the derivation of Equation ( 34), this can also be expressed asEQUATIONEffectively, MM-ITL ignores the mutual interaction between points in A. As can be seen from Equation (37) and as is also mentioned by MacKay (1992), MM-ITL is equivalent to VTL up to a different weighting of the points in A: instead of minimizing the average posterior variance (as in VTL), MM-ITL minimizes the average posterior log-variance. Under the lens of principle ( †), this can be seen as minimizing the average marginal entropy of predictions within the target space:x n = arg minx∈S x ′ ∈A H[f x ′ | D n-1 , y x ] .We remark that MM-ITL is a special case of EPIG (Bickford Smith et al., 2023, Appendix E.2).Not a generalization of uncertainty sampling Unlike ITL, MM-ITL is not a generalization of uncertainty sampling. The reason is precisely that MM-ITL ignores the mutual interaction between points in A. Consider the example where X = S = A = {1, . . . , 10} where f 1:9 are highly correlated while f 10 is mostly independent of the other points. Visually, imagine a smooth function (i.e., under a Gaussian kernel) with points 1 through 9 close to each other and point 10 far away. Further, suppose that point 10 has a slightly larger marginal variance than the others. Then, MM-ITL would select one of the points 1 : 9 since this leads to the largest reduction in the marginal (log-)variances (i.e., to a small posterior "uncertainty"). 13 In contrast, ITL selects the point with the largest prior marginal variance (cf. Appendix C.1), point 10, since this leads to the largest reduction in entropy. 14Similarity to VTL Observe that the following decision rule is equivalent to VTL:x n = arg max x∈S tr Var[f A | D n-1 ] -tr Var[f A | D n-1 , y x ].By Lemma C.38, for any x ∈ S, this objective value can be tightly lower-and upper-bounded (up to constant-factors) byx ′ ∈A log Var[f x ′ | D n-1 ] Var[f x ′ | D n-1 , y x ] = 2 x ′ ∈A I(f x ′ ; y x | D n-1 ) (see MM-ITL) (i) = - x ′ ∈A log 1 -Cor[f x ′ , y x | D n-1 ] 2 (39)where (i) is detailed in example 8.5.1 of Cover (1999) . Thus, VTL and MM-ITL are closely related.Experiments In our experiments with Gaussian processes from Figures 2 and 6 , we observe that MM-ITL performs similarly to VTL and CTL.We derive a convergence guarantee for MM-ITL which is analogous to the guarantees for ITL from Theorem C.12 and for VTL from Theorem C.13. We will assume for simplicity that Γ n is monotonically decreasing in n (i.e., α n ≤ 1). EQUATION)Proof. We haveΓ n-1 = 1 n n-1 i=0 Γ n-1 (i) ≤ 1 n n-1 i=0 Γ i = 1 n n-1 i=0 max x∈S x ′ ∈A I(f x ′ ; y x | D n ) (ii) = 1 n n-1 i=0 x ′ ∈A I(f x ′ ; y xn+1 | D n ) (iii) = 1 n x ′ ∈A n-1 i=0 I(f x ′ ; y xn+1 | y x1:n ) (iv) = 1 n x ′ ∈A I f x ′ ; y x1:n ≤ 1 n x ′ ∈A max X⊆S |X|=n I(f x ′ ; y X ) = 1 n x ′ ∈A γ n ({x ′ }; S)where (i) follows by assumption; (ii) follows from the MM-ITL decision rule; (iii) uses that the posterior variance of Gaussians is independent of the realization and only depends on the location of observations; and (iv) uses the chain rule of mutual information. The remainder of the proof is analogous to the proof of Theorem C.12 (cf. Appendix C.5).Noting thatI(f x ′ ; y x | D n-1 ) ≤ x ′ ∈A I(f x ′ ; y x | D n-1 )for any n ≥ 1, x ∈ X , and x ′ ∈ A, Theorem 3.2 can be readily rederived for MM-ITL (cf. Lemmas C.14 and C.18). Hence, the posterior marginal variances of MM-ITL can be bounded uniformly in terms of Γ n analogously to ITL.We will briefly look at the CTL (Correlation-based TL) decision ruleEQUATIONwhich permits no interpretation under principle ( †). However, if all correlations are non-negative (such as for the standard Gaussian and Matérn kernels), CTL is closely related to ITL, VTL, and MM-ITL (cf. Equations ( 35) and ( 39)). In this case, if |A| = 1, then all decision rules coincide.If, on the other hand, correlations may be negative then there is a crucial difference between CTL and the decision rules motivated from principle ( †). Namely, decision rules following ( †) exhibit a preference for points with high absolute correlation to prediction targets as opposed to CTL which prefers points with high positive correlation. This stems from the intuitive fact that points with a strong negative correlation are equally informative as points with a strong positive correlation. Nevertheless, we observe in our experiments that (even for a linear kernel which does not ensure non-negative correlations) points selected by ITL and VTL are typically positively correlated with prediction targets.We have seen that ITL, VTL, and MM-ITL can be seen as different interpretations of the same fundamental principle ( †), with the approximations CTL. If |A| = 1 and correlations are non-negative, then all four decision rules are equivalent. CTL prefers points with high positive correlation whereas the other decision rules prefer points with high absolute correlation. ITL is the only decision rule that takes into account the mutual dependence between points in A, and VTL and MM-ITL differ only in their weighting of the posterior marginal variances of points in A.When the target space A is large, it may be computationally infeasible to compute the exact objective.A natural approach to address this issue is to approximate the target space by a smaller set of size K.Discretizing the target space One possibility is to discretize the target space A. Compact target spaces can be addressed, e.g., via discretization arguments which are common in the Bayesian optimization literature (see, e.g., appendix C.1 of Srinivas et al. (2009) ). That is, if the target space can be covered approximately using a finite (possibly large) set of points, the guarantees of Theorem 3.2 extend directly. This, however, can be impractical when the required size of discretization for sufficiently small approximation error is large. In the following, we briefly discuss a natural alternative approach based on sampling points from A.Target distributions Let A ⊆ X be a (possibly continuous) target space, and let P A be a probability distribution supported on A. In iteration n, a subset A n of K points is sampled independently from A according to the distribution P A and the objective is computed on this subset. Formally, this amounts to a single-sample Monte Carlo approximation ofEQUATION)The convergence guarantees from Appendix C can be generalized to the setting of stochastic target spaces by estimating how often points "near" a specified prediction target x ∈ A are sampled. Definition E.1 (γ-ball at x). Given x ∈ A and any γ ≥ 0, we call the setB γ (x) def = {x ′ ∈ X | ∥x -x ′ ∥ ≤ γ}the γ-ball at x. Further, we call P A (B γ (x)) the weight of that ball. Proposition E.2 (sketch). Given any n ≥ 1, K ≥ 1, γ > 0, and x ∈ A, suppose that B γ (x) has weight p > 0. Assume that the ITL objective is L I -Lipschitz continuous. Then, with probability at least 1 -exp(-(1 -p)n/(8K)),σ 2 n (x) ≲ η 2 S (x) + CL I γ γ k(n) k(n)where k(n)def = Kpn/2.Proof sketch. Let Y i ∼ Binom(K, p) denote the random variable counting the number of occurrences of a point from B γ (x) in A i . Moreover, we writeX i def = 1{B γ (x) ∩ A i ̸ = ∅}. Note that ν def = EX i = P(B γ (x) ∩ A i ̸ = ∅) = 1 -P(Y i = 0) = 1 -(1 -p) K ≈ Kpwhere the approximation stems from a first-order truncation of the Bernoulli series. Let X def = n i=1 X i with EX = nν ≈ Kpn. Using the assumed Lipschitz-continuity of the objective, we know thatI(f A ′ ; y x | D n-1 ) ≤ L I γI(f A ; y x | D n-1 ) where A ′ def = (A \ {x γ }) ∪{x} and x γ is the point from the γ-ball at x. The bound then follows analogously to Theorem 3.2.Finally, by Chernoff's bound, at least Kpn/2 iterations contain a point from B γ (x) with probability at least 1 -exp(-Kpn/8).This strategy can also be used to generalize the VTL, CTL, and MM-ITL objectives to stochastic target spaces.Below, we list the closed-form expressions for the ITL and VTL objectives. In the following, k n denotes the kernel conditional on D n . Hyperparameters of TRUVAR As suggested by Bogunovic et al. (2016) , we use η2(1) = 1, r = 0.1, and δ = 0 (even though the theory only holds for δ > 0). The TRUVAR baseline only applies when A ⊆ S (cf. Section 6).Smoothing to reduce numerical noise Applied running average with window 5 to entropy curves of Figures 2 and 6 to smoothen out numerical noise.In our main experiments, we consider the setting A ∩ S = ∅, i.e., the prediction targets cannot be used for fine-tuning since their labels are not known. This setting is particularly relevant for practical applications where the model is fine-tuned dynamically at test time to each prediction target (or a small set of prediction target). Put differently, in this "transductive" setting, extrapolation to new prediction targets happens at test-time with knowledge of the prediction target(s). This is in contrast to a more traditional "inductive" setting, where extrapolation happens at train-time without knowledge of the concrete prediction targets, but under the assumption of samples from (or knowledge of) the target distribution. In the following, we briefly survey two settings motivated from an "inductive" perspective.If labels can be obtained cheaply, one can also fine-tune on the prediction targets directly, i.e., A ⊆ S. Note, however, that the set A is still assumed to be small (e.g., |A| = 100 in the CIFAR-100 experiment). We perform an experiment in this setting and report the results in Figure 7 . The experiment shows that -similarly to the GP experiment from Figure 2 -there can be additional value in fine-tuning the model on relevant data selected from S beyond simply fine-tuning the model on A. Active DA (Rai et al., 2010; Saha et al., 2011; Berlind & Urner, 2015) studies the problem of selecting the most informative samples from a (large) target domain A, given a model trained on a source domain S. This problem can be cast as an instance of transductive active learning with target space A and sample space S ′ = S ∪ A where the model is already conditioned on all of S. This is slightly different from the setting considered in Section 4 where A is small and not necessarily part of the sample space. We hypothesize that ITL behaves similarly to recent work on active DA (Su et al., 2020; Prabhu et al., 2021; Fu et al., 2021) : querying informative and diverse samples from A that are dissimilar to S. Evaluating ITL and VTL empirically in this setting is a promising direction for future work.We outline the active fine-tuning of NNs in Algorithm 1. In Appendix J.1, we detail metrics and hyperparameters. We describe in Appendices J.2 and J.3 how to compute the (initial) conditional kernel matrix K, and in Appendix J.4 how to update this matrix K to obtain conditional embeddings for batch selection. In Appendix J.5, we show that ITL and CTL significantly outperform a wide selection of commonly used heuristics. In Appendices J.6 and J.7, we conduct additional experiments and ablations. 2024) discusses additional motivation and related work that has previously studied active fine-tuning, but which has largely focused on the training algorithm rather than data selection.We evaluate the accuracy with respect to P A using a Monte Carlo approximation with out-of-sample data:accuracy( θ) ≈ E (x,y)∼P A 1{y = arg max i f i (x; θ)}.We provide an overview of the hyperparameters used in our NN experiments in Table 1 . The effect of noise standard deviation ρ is small for all tested ρ ∈ [1, 100] (cf. ablation study in Table 2 ).15 M denotes the size of the sample A ∼ P A . In each iteration, we select the target space A ← A ′ as a random subset of m points from A. 16 We provide an ablation over m in Appendix J.6.During each iteration, we select the batch B according to the decision rule from a random sample from P S of size k.17 Since we train the MNIST model from scratch, we train from random initialization until convergence on oracle validation accuracy. 18 We do this to stabilize the learning curves, and provide the least biased (due to the training algorithm) results. For CIFAR-100, we train for 5 epochs (starting from the previous iterations' model) which we found to be sufficient to obtain good performance.We use the ADAM optimizer (Kingma & Ba, 2014) . In our CIFAR-100 experiments, we use a pre-trained EfficientNet-B0 (Tan & Le, 2019) , and fine-tune the final and penultimate layers. We freeze earlier layers to prevent overfitting to the "few-shot" training data.To prevent numerical inaccuracies when computing the ITL objective, we optimizeEQUATIONinstead of Equation ( 43), which amounts to adding ρ 2 to the diagonal of the covariance matrix before inversion. This appears to improve numerical stability, especially when using gradient embeddings. 19In our experiments, we use last-layer neural tangent embeddings20 and Σ = I to evaluate ITL and VTL, and select inputs for labeling and training f . Notably, we use this linear Gaussian approximation of f only to guide the active data selection and not for inference.Using a neural network to parameterize f , we evaluate the canonical approximations of f by a stochastic process in the following.An embedding ϕ(x) is a latent representation of an input x. Collecting the embeddings as rows in the design matrix Φ of a set of inputs X, one can approximate the network by the linear function f X = Φβ with weights β. Approximating the weights by β ∼ N (µ, Σ) implies that f X ∼ N (Φµ, ΦΣΦ ⊤ ). The covariance matrix K XX = ΦΣΦ ⊤ can be succinctly represented in terms of its associated kernel k(x, x ′ ) = ϕ(x) ⊤ Σϕ(x ′ ). Here,• ϕ(x) is the latent representation of x, and • Σ captures the dependencies in the latent space.While any choice of embedding ϕ is possible, the following are common choices:1. Last-Layer: A common choice for ϕ(x) is the representation of x from the penultimate layer of the neural network (Holzmüller et al., 2023) . Interpreting the early layers as a feature encoder, this uses the low-dimensional feature map akin to random feature methods (Rahimi & Recht, 2007) . 2. Output Gradients (eNTK): Another common choice is ϕ(x) = ∇ θ f (x; θ) where θ are the network parameters (Holzmüller et al., 2023) . Its associated kernel is known as the empirical neural tangent kernel (eNTK) and the posterior mean of this GP approximates ultra-wide NNs trained with gradient descent (Jacot et al., 2018; Arora et al., 2019; Lee et al., 2019; Khan et al., 2019; He et al., 2020; Malladi et al., 2023) . Kassraie & Krause (2022) derive bounds of γ n under this kernel. If θ is restricted to the weights of the final linear layer, then this embedding is simply the last-layer embedding. 3. Loss Gradients: Another possible choice isϕ(x) = ∇ θ ℓ(f (x; θ), ŷ(x))| θ= θwhere ℓ is a loss function, ŷ(x) is the predicted label, and θ are the current parameter estimates (Ash et al., 2020) . 4. Outputs (eNNGP): Another possible choice is ϕ(x) = f (x), i.e., the output of the network.Its associated kernel is known as the empirical neural network Gaussian process (eNNGP) kernel (Lee et al., 2018) . 5. Predictive (Kirsch, 2023) : Given a Bayesian neural network (Blundell et al., 2015) or probabilistic (deep) ensemble (Lakshminarayanan et al., 2017) , which induce samples θ 1 , . . . , θ K ∼ p(θ) from the distribution over network parameters, one can approximate the predictive covariance k(x,x ′ ) = Cov θ [f (x; θ), f (x ′ ; θ)].This kernel measures proximity in the prediction space rather than parameter space and as such does not require gradient information. The corresponding feature map is ϕ(x) = 1 √ K [ f (x; θ 1 ) • • • f (x; θ K )] ⊤ where f (x; θ k ) def = f (x; θ k ) -1 K K l=1 f (x; θ l ).In the additional experiments from this appendix we use last-layer embeddings unless noted otherwise. We compare the performance of last-layer and the loss gradient embeddingEQUATIONwhere θ ′ are the parameters of the final output layer, θ are the current parameter estimates, ŷ(x) = arg max i f i (x; θ) are the associated predicted labels, and ℓ CE denotes the cross-entropy loss. This gradient embedding captures the potential update direction upon observing a new point (Ash et al., 2020) . Moreover, Ash et al. (2020) show that for most neural networks, the norm of these gradient embeddings are a conservative lower bound to the norm assumed by taking any other proxy label ŷ(x). In Figure 8 , we observe only negligible differences in performance between this and the last-layer embedding. 2021)) over last-layer weights using a Kronecker factored log-likelihood Hessian approximation (Martens & Grosse, 2015) and the loss gradient embeddings from Equation (45). The results are shown for the MNIST experiment. We do not observe a performance improvement beyond the trivial approximation Σ = I.A straightforward and common approximation of the uncertainty about NN weights is given by Σ = I, and we use this approximation throughout our experiments.The poor performance of UNSA (cf. Appendix J.5) with this approximation suggests that with more sophisticated approximations, the performance of ITL, VTL, and CTL can be further improved.Further research is needed to study the effect of more sophisticated approximations of "uncertainty" in the latent space. For example, with parameter gradient embeddings, the latent space is the network parameter space where various approximations of Σ based on Laplace approximation (Daxberger et al., 2021; Antorán et al., 2022) , variational inference (Blundell et al., 2015) , or Markov chain Monte Carlo (Maddox et al., 2019) have been studied. We also evaluate Laplace approximation (LA, Daxberger et al. (2021) ) for estimating Σ but see no improvement (cf. Figure 9 ). Nevertheless, we believe that uncertainty quantification is a promising direction for future work, with the potential to improve performance of ITL and its variations substantially.We will refer to the greedy decision rule from Equation (3) as BACE, short for Batch selection via Conditional Embeddings. BACE can be implemented efficiently using the Gaussian approximation of f X from Appendix J.2 by iteratively conditioning on the previously selected points x n,1:i-1 , and updating the kernel matrix K XX using the closed-form formula for the variance of conditional Gaussians:EQUATION)where j denotes the index of the selected x n,i within X and ρ 2 is the noise variance. Note that K xj xj is a scalar and K Xxj is a row vector, and hence, this iterative update can be implemented efficiently.We remark that Equation ( 3) is a natural extension of previous non-adaptive active learning methods, which typically maximize some notion of "distance" between points in the batch, to the "directed" setting (Ash et al., 2020; Zanette et al., 2021; Holzmüller et al., 2023; Pacchiano et al., 2024) . BACE simultaneously maximizes "distance" between points in a batch and minimizes "distance" to points in A.The sample efficiency of BACE B n , and therefore also the greedily constructed B ′ n (which gives a constant-factor approximation with respect to the objective), yields diverse batches by design. In Figure 10 , we compare BACE to selecting the top-b points according to the decision rule (which does not yield diverse batches). We observe a significant improvement in accuracy and data retrieval when using BACE. We expect the gap between both approaches to widen further with larger batch sizes.Computational complexity of BACE As derived in Appendix G, a single batch selection step of BACE has complexity O b(k 3 + m 2 ) where b is the size of the batch, k = |A| is the size of the target space, and m = |S| is the size of the candidate set. In the case of large m, an alternative implementation whose runtime does not depend on m is described in Appendix G.In Figure 11 , we compare against additional baselines:• Both TYPICLUST (Hacohen et al., 2022) and PROBCOVER (Yehuda et al., 2022) are recent methods to select points that "cover" the data distribution well. To maintain comparability between algorithms, we use the same embeddings as for ITL which are re-computed before every new batch selection. ITL significantly outperforms TYPICLUST & PROBCOVER, which only attempt to cover S well without taking A into account (i.e., are "undirected").• Mehta et al. (2022) introduced EIG for training neural classification models, which uses the same decision rule as ITL, but approximates the conditional entropy based on the networks' softmax output rather than using a GP approximation. We approximate the conditional entropy using a single gradient step of the hallucinated updates on the parameters of the final layer, as mentioned by Mehta et al. (2022) . We observe that EIG is not competitive for batch-wise selection (CIFAR-100) since it does not encourage batch diversity. Moreover, we observe that EIG is orders of magnitude slower than ITL (since it has to compute |S| • C individual gradient steps where C is the number of classes). We note that since our datasets are balanced, the AEIG algorithm from Mehta et al. (2022) coincides with EIG. In the following, we briefly describe other commonly used "undirected" decision rules.Denote the softmax distribution over labels i at inputs x byp i (x; θ) ∝ exp(f i (x; θ)).The following heuristics computed based on the softmax distribution aim to quantify the "uncertainty" about a particular input x:• MAXENTROPY (Settles & Craven, 2008) :x n = arg max x∈S H[p(x; θ n-1 )].• MAXMARGIN (Scheffer et al., 2001; Settles & Craven, 2008) :x n = arg min x∈S p 1 (x; θ n-1 ) -p 2 (x; θ n-1 )where p 1 and p 2 are the two largest class probabilities.• LEASTCONFIDENCE (Lewis & Gale, 1994; Settles & Craven, 2008; Hendrycks & Gimpel, 2017; Tamkin et al., 2022) :x n = arg min x∈S p 1 (x; θ n-1 )where p 1 is the largest class probability.An alternative class of decision rules aims to select diverse batches by maximizing the distances between points. Embeddings ϕ(x) induce the (Euclidean) embedding distanced ϕ (x, x ′ ) def = ∥ϕ(x) -ϕ(x ′ )∥ 2 .Similarly, a kernel k induces the kernel distanced k (x, x ′ ) def = k(x, x) + k(x ′ , x ′ ) -2k(x, x ′ ).It is straightforward to see that if k(x, x ′ ) = ϕ(x) ⊤ ϕ(x ′ ), then embedding and kernel distances coincide, i.e., d ϕ (x, x ′ ) = d k (x, x ′ ).• MAXDIST (Holzmüller et al., 2023; Yu & Kim, 2010; Sener & Savarese, 2017; Geifman & El-Yaniv, 2017) constructs the batch by choosing the point with the maximum distance to the nearest previously selected point:x n = arg max x∈S min i<n d(x, x i )• Similarly, K-MEANS++ (Holzmüller et al., 2023) selects the batch via K-MEANS++ seeding (Arthur et al., 2007; Ostrovsky et al., 2013) . That is, the first centroid x 1 is chosen uniformly at random and the subsequent centroids are chosen with a probability proportional to the square of the distance to the nearest previously selected centroid:P(x n = x) ∝ min i<n d(x, x i ) 2 .When using the loss gradient embeddings from Equation ( 45), this decision rule is known as BADGE (Ash et al., 2020) .Finally, we summarize common kernel-based decision rules.• UNDIRECTED ITL choosesx n = arg max x∈S I(f S ; y x | D n-1 ) = arg max x∈S I(f x ; y x | D n-1 ) .This can be shown to be equivalent to MAXDET (Holzmüller et al., 2023) which selectsx n = arg max x∈S K x + σ 2 Iwhere K x denotes the kernel matrix over x 1:n-1 ∪{x}, conditioned on the prior observations D n-1 . • UNSA (Lewis & Catlett, 1994) which with embeddings ϕ n-1 after round n -1 corresponds to:x n = arg max x∈S σ 2 n-1 (x) = arg max x∈S ϕ n-1 (x) 2 2 .With batch size b = 1, UNSA coincides with UNDIRECTED ITL. When evaluated with gradient embeddings, this acquisition function is similar to previously used "embedding length" or "gradient length" heuristics (Settles & Craven, 2008 ). • UNDIRECTED VTL (Cohn, 1993) is the special case of VTL without specified prediction targets (i.e., A = S). In the literature, this decision rule is also known as BAIT (Holzmüller et al., 2023; Ash et al., 2021) .We compare to the abovementioned decision rules and summarize the results in Figure 12 . We observe that most "undirected" decision rules perform worse (and often significantly so) than RANDOM. This is likely due to frequently selecting points from the support of P S which are not in the support of P A since the points are "adversarial examples" that the model θ is not trained to perform well on. In the case of MNIST, the poor performance can also partially be attributed to the well-known "cold-start problem" (Gao et al., 2020) .In Figure 4 , we also compare to the following "directed" decision rules:• COSINESIMILARITY (Settles & Craven, 2008) selects x n = arg max x∈S ∠ ϕ n-1 (x, A) where∠ ϕ (x, A) def = 1 |A| x ′ ∈A ϕ(x) ⊤ ϕ(x ′ ) ∥ϕ(x)∥ 2 ∥ϕ(x ′ )∥ 2 .• INFORMATIONDENSITY (Settles & Craven, 2008) is defined as the multiplicative combination of MAXENTROPY and COSINESIMILARITY:x n = arg max x∈S H[p(x; θ n-1 )] • ∠ ϕ n-1 (x, A) βwhere β > 0 controls the relative importance of both terms. We set β = 1 in our experiments. We conduct the following additional experiments:1. Imbalanced P S (Figure 13 ): We artificially remove 80% of the support of P A from P S . For example, in case of MNIST, we remove 80% of the images with labels 3, 6, and 9 from P S . This makes the learning task more difficult, as P A is less represented in P S , meaning that the "targets" are more sparse. The trend of ITL outperforming CTL which outperforms RANDOM is even more pronounced in this setting. 2. Imbalanced A ∼ P A (Figure 14 ): We artificially remove 50% of part of the support of P A while generating A ∼ P A to evaluate the robustness of ITL and CTL in presence of an imbalanced target space A. Concretely, in case of MNIST, we remove 50% of the images with labels 3 and 6 from A. In case of CIFAR-100, we remove 50% of the images with labels {0, . . . , 4} from A. We still observe the same trends as in the other experiments. 3. VTL & choice of k (Figure 15 ): We observe that VTL performs almost as well as ITL.Additionally, we evaluate the effect of the number of points k at which the decision rule is evaluated. Not surprisingly, we observe that the performance of ITL, VTL, and CTL improves with larger k. 4. Choice of m (Figure 16 ): Next, we evaluate the choice of m, i.e., the size of the target space A relative to the number M of candidate points A ∼ P A . We write p = m/M . We generally observe that a larger p leads to better performance (with p = 1 being the best choice). However, it appears that a smaller p can be beneficial with respect to accuracy when a large number of batches are selected. We believe that this may be because a smaller p improves the diversity between selected batches.5. Choice of M (Figure 17 ): Finally, we evaluate the choice of M , i.e., the size of A ∼ P A .Not surprisingly, we observe that the performance of ITL improves with larger M .In Table 2 , we evaluate the CIFAR-100 experiment with different noise standard deviations ρ. We observe that the performance of batch selection via conditional embeddings drops (mostly for the less numerically stable gradient embeddings) if ρ is too small, since this leads to numerical inaccuracies when computing the conditional embeddings. Apart from this, the effect of ρ is negligible. In Appendix K.1, we discuss the use of stochastic target spaces in the safe BO setting. We provide a comprehensive overview of prior works in Appendix K.2 and an additional experiment highlighting that ITL, unlike SAFEOPT, is able to "jump past local barriers" in Appendix K.3. In Appendix K.4, we provide details on the experiments from Figure 5 .Alternatively to the target space A n which comprises all potentially optimal points, we evaluate the stochastic target spaceEQUATIONwhich effectively weights points in A n according to how likely they are to be the safe optimum, and is therefore more exploitative than the uniformly-weighted target space discussed so far. Samples from P An can be obtained efficiently via Thompson sampling (Thompson, 1933; Russo et al., 2018) . Observe that P An is supported precisely on the set of potential maximizers A n . We provide a formal analysis of stochastic target spaces in Appendix E. Whether transductive active learning with A n or P An performs better is task-dependent, as we will see in the following.Note that performing ITL with this target space is analogous to output-space entropy search (Wang & Jegelka, 2017) . Samples from P An can be obtained via Thompson sampling (Thompson, 1933; Russo et al., 2018) . That is, in iteration n + 1, we sample K ∈ N independent functions f (j) ∼ f | D n from the posterior distribution and select K points x (1) , . . . , x (K) which are a safe maximum of f (1) , . . . , f (K) , respectively.Experiments In Figure 18 , we contrast the performance of ITL with P An to the performance of ITL with the exact target space A n . We observe that their relative performance is instance dependent: in tasks that require more difficult expansion, ITL with A n converges faster, whereas in simpler tasks (such as the 2d experiment), ITL with P An converges faster. We compare against the GOOSE algorithm (Turchetta et al., 2019) which is a heuristic extension of SAFEOPT that explores more greedily in directions of (assumed) high reward (cf. Appendix K.2.3). GOOSE suffers from the same limitations as SAFEOPT, which were highlighted in Section 5, and additionally is limited by its heuristic approach to expansion which fails in the 1d task and safe controller tuning task. Analogously to our experiments with SAFEOPT, we also compare against ORACLE GOOSE which has oracle knowledge of the true Lipschitz constants.The different behaviors of ITL with A n and P An , respectively, as well as SAFEOPT and GOOSE are illustrated in Figure 19 . We observe that ITL with A n and SAFEOPT expand the safe set more "uniformly" since the set of potential maximizers encircles the true safe set. 21 Intuitively, this is because the set of potential maximizers conservatively captures migh points might be safe and optimal. In contrast, ITL with P An and GOOSE focus exploration and expansion in those regions where the objective is likely to be high.Figure 19 : The first 100 samples of (A) ITL with A n , (B) SAFEOPT, (C) ORACLE SAFEOPT, (D) ITL with P An , (E) GOOSE, (F) ORACLE GOOSE. The white region denotes the pessimistic safe set S 100 , the light gray region denotes the true safe set S ⋆ (i.e., the "island"), and the darker gray regions denotes unsafe points (i.e., the "ocean").The most widely used method for Safe BO is SAFEOPT (Sui et al., 2015; Berkenkamp et al., 2021) which keeps track of separate candidate sets for expansion and exploration and uses UNSA to pick one of the candidates in each round. Treating expansion and exploration separately, sampling is directed towards expansion in all directions -even those that are known to be suboptimal. The safe set is expanded based on a Lipschitz constant of g ⋆ , which is assumed to be known. In most real-world settings, this constant is unknown and has to be estimated using the GP. This estimate is generally conservative and results in suboptimal performance. To this end, Berkenkamp et al. (2016) proposed HEURISTIC SAFEOPT which relies solely on the confidence intervals of g to expand the safe set, but lacks convergence guarantees. More recently, Bottero et al. (2022) proposed ISE which queries parameters from S n that yield the most "information" about the safety of another parameter in X . Hence, ISE focuses solely on the expansion of the safe set S n and does not take into account the objective f . In practice, this can lead to significantly worse performance on the simplest of problems (cf. Figure 5 ). In contrast, ITL balances expansion of and exploration within the safe set. Furthermore, ISE does not have known convergence guarantees of the kind of Theorem 5.1.In parallel independent work, Bottero et al. (2024) proposed a combination of ISE and max-value entropy search (Wang & Jegelka, 2017) for which they derive a similar guarantee to Theorem 5.1. 22Similar to SAFEOPT, their method aims to expand the safe set in all directions including those that are known to be suboptimal. In contrast, ITL directs expansion only towards potentially optimal regions.In the 1d task and quadcopter experiment (cf. Figure 5 ), we observe that SAFEOPT and even ORACLE SAFEOPT converge significantly slower than ITL to the safe optima. We believe this is due to their conservative Lipschitz-continuity/global smoothness-based expansion, as opposed to ITL's expansion, which adapts to the local smoothness of the constraints. HEURISTIC SAFEOPT, which does not rely on the Lipschitz constant for expansion, does not efficiently expand the safe set due to its heuristic that only considers single-step expansion. This is especially the case for the 1d task. Furthermore, in the 2d task, we notice the suboptimality of ISE since it does not take into account the objective, and purely aims to expand the safe set. ITL, on the other hand, balances expansion and exploration.SAFEOPT (Sui et al., 2015; Berkenkamp et al., 2021 ) is a well-known algorithm for Safe BO.Lipschitz-based expansion SAFEOPT expands the set of known-to-be safe points by assuming knowledge of an upper bound L i to the Lipschitz constant of the unknown constraints g ⋆ i . 23 In each iteration, the (pessimistic) safe set S n is updated to include all points which can be reached safely (with respect to the Lipschitz continuity) from a known-to-be-safe point x ∈ S n . Formally,S SAFEOPT n def = x∈S SAFEOPT n-1 {x ′ ∈ X | l n,i (x) -L i ∥x -x ′ ∥ 2 ≥ 0 for all i ∈ I s }. (48)The expansion of the safe set is illustrated in Figure 20 .We remark two main limitations of this approach. First, the Lipschitz constant is an additional safety critical hyperparameter of the algorithm, which is typically not known. The RKHS assumption (cf. Assumption C.25) induces an assumption on the Lipschitz continuity, however, the worst-case a-priori Lipschitz constant is typically very large, and prohibitive for expansion. Second, the Lipschitz constant is global property of the unknown function, meaning that it does not adapt to the local smoothness. For example, a constraint may be "flat" in one direction (permitting straightforward expansion) and "steep" in another direction (requiring slow expansion). Furthermore, the Lipschitz constant is constant over time, whereas ITL is able to adapt to the local smoothness and reduce the (induced) Lipschitz constant over time.Undirected expansion SAFEOPT addresses the trade-off between expansion and exploration by focusing learning on two different sets. First, the set of maximizersM SAFEOPT n def = {x ∈ S SAFEOPT n | u n,f (x) ≥ max x ′ ∈S SAFEOPT n l n,f (x)}which contains all known-to-be-safe points which are potentially optimal. Note that if S SAFEOPT n = S n then M SAFEOPT n ⊆ A n since A n contains points which are potentially optimal and potentially safe but possibly unsafe.To facilitate expansion, for each point x ∈ S n , the algorithm considers a set of expanding pointsF SAFEOPT n (x) def = {x ′ ∈ X \ S SAFEOPT n | u n,i (x) -L i ∥x -x ′ ∥ 2 ≥ 0 for all i ∈ I s }A point is expanding if it is unsafe initially and can be (optimistically) deduced as safe by observing x. The set of expanders corresponds to all known-to-be-safe points which optimistically lead to expansion of the safe set:G SAFEOPT n def = {x ∈ S n | |F n (x)| > 0}.That is, an expander is a safe point x which is "close" to at least one expanding point x ′ . Observe that here, we start with a safe x and then find a close and potentially safe x ′ using the Lipschitz-property of the constraint function. Thus, the set of expanding points is inherently limited by the assumed Lipschitzness (cf. Figure 20 ), and generally a subset of the potential expanders E n (cf. Equation ( 27 Here, the blue region denotes the pessimistic safe set S, the red region denotes the true safe set S ⋆ , and the orange region denotes the optimistic safe set S. Whereas ITL learns about the point x ′ directly, SAFEOPT expands the safe set using the reduction of uncertainty at x, and then extrapolating using the Lipschitz constant (cf. Equation ( 48)). The dashed orange line denotes the expanding points of SAFEOPT which under-approximate the optimistic safe set of ITL (cf. Lemma K.1). Thus, ITL may even learn about points in S which are "out of reach" for SAFEOPT.Proof. Without loss of generality, we consider the case where I s = {i}. We haveE n = S n \ S n = {x ∈ X \ S n | u n,i (x) ≥ 0}.The result follows directly by observing that L i ∥x -x ′ ∥ 2 ≥ 0.SAFEOPT then selects x n+1 according to uncertainty sampling within the maximizers and expanders:M SAFEOPT n ∪ G SAFEOPT n. We remark that due to the separate handling of expansion and exploration, SAFEOPT expands the safe set in all directions -even those that are known to be suboptimal. In contrast, ITL only expands the safe set in directions that are potentially optimal by balancing expansion and exploration through the single set of potential maximizers A n .Based on uncertainty sampling As mentioned in the previous paragraph, SAFEOPT selects as next point the maximizer/expander with the largest prior uncertainty. 24 In contrast, ITL selects the point within S n which minimizes the posterior uncertainty within A n . Note that the two approaches are not identical as typicallyM SAFEOPT n ∪ G SAFEOPT n ⊂ S SAFEOPT n and A n ̸ ⊇ S n .We show empirically in Section 3.3 that depending on the kernel choice (i.e., the smoothness assumptions), uncertainty sampling within a given target space neglects higher-order information that can be attained by sampling outside the set. This can be seen even more clearly when considering linear functions, in which case points outside the maximizers and expanders can be equally informative as points inside.Finally, note that the set of expanders is constructed "greedily", i.e., only considering single-step expansion. This is necessitated as the inference of safety is based on single reference points. Instead, ITL directly quantifies the information gained towards the points of interest without considering intermediate reference points.Requires homoscedastic noise SAFEOPT imposes a homoscedasticity assumption on the noise which is an artifact of the analysis of uncertainty sampling. It is well known that in the presence of heteroscedastic noise, one has to distinguish epistemic and aleatoric uncertainty. Uncertainty sampling fails because it may continuously sample a high variance point where the variance is dominated by aleatoric uncertainty, potentially missing out on reducing epistemic uncertainty at points with small aleatoric uncertainty. In contrast, maximizing mutual information naturally takes = S GOOSE n,ϵ \ S SAFEOPTn akin to the "potential expanders" E n (cf. Equation ( 27)), to each of which we assign a priority h(x). When h(x) is large, this indicates that the algorithm is prioritizing to determine whether x is safe. We use as heuristic the negative ℓ 1 -distance between x and x ⋆ . GOOSE then considers the set of potential immediate expandersEQUATIONdef = {x ∈ W GOOSE n,ϵ | ∃x ′ ∈ A GOOSE n,ϵ with priority α such that u n,c (x) -L c ∥x -x ′ ∥ 2 ≥ 0}.The "expansionist" point selected by GOOSE is then any point inG GOOSE n,ϵ (α ⋆ ) where α ⋆ denotes the largest priority such that |G GOOSE n,ϵ (α ⋆ )| > 0.We observe empirically that the sample complexity of GOOSE is not always better than that of SAFEOPT. Notably, the expansion of the safe set is based on a "greedy" heuristic. Moreover, determining whether a single oracle proposal x ⋆ is safe may take significant time. Consider the (realistic) example where the prior is uniform, and UCB proposes a point which is far away from the safe set and suboptimal. GOOSE will typically attempt to derive the safety of the proposed point until the uncertainty at all points within S SAFEOPT 0 is reduced to ϵ.25 Thus, GOOSE can "waste" a significant number of samples, aiming to expand the safe set towards a known-to-be suboptimal point. In larger state spaces, due to the greedy nature of the expansion strategy, this can lead to GOOSE being effectively stuck at a suboptimal point for a significant number of rounds.Recently, Bottero et al. (2022) proposed an information-theoretic approach to efficiently expand the safe set which they call information-theoretic safe exploration (ISE). Specifically, they choose the next action x n by approximating arg maxx∈Sn-1 max x ′ ∈X I(1{g x ′ ≥ 0}; y x | D n-1 ) α ISE (x).(ISE)In a parallel independent work, Bottero et al. (2024) extended ISE to the Safe BO problem where they propose to choose x n according to arg maxx∈Sn-1 max{α ISE (x), α MES (x)} (ISE-BO)where α MES denotes the acquisition function of max-value entropy search (Wang & Jegelka, 2017) . Similarly to SAFEOPT, ISE-BO treats expansion and exploration separately, which leads to "undirected" expansion of the safe set. That is, the safe set is expanded in all directions, even those that are known to be suboptimal. In contrast, ITL balances expansion and exploration through the single set of potential maximizers A n . With a stochastic target space, ITL generalizes max-value entropy search (cf. Appendix K.1).We evaluate ISE-BO in Figure 18 and observe that it does not outperform ITL and VTL in any of the tasks, while performing poorly in the 1d task and suboptimally in the 2d task. In this additional experiment we demonstrate that ITL is able to extrapolate safety beyond local unsafe "barriers", which is a fundamental limitation of Lipschitz-based methods such as SAFEOPT. We consider the ground truth function and prior statistical model shown in Figure 21 . Note that initially, there are three disjoint safe "regions" known to the algorithm corresponding to two of the three safe "bumps" of the ground truth function. In this experiment, the main challenge is to "jump past" the local barrier separating the leftmost and initially unknown safe "bump".Figure 22 shows the sampled points during the first 100 iterations of SAFEOPT and ITL. Clearly, SAFEOPT does not discover the third safe "bump" while ITL does. Indeed, it is a fundamental limitation of Lipschitz-based methods that they can never "jump past local barriers", even if the oracle Lipschitz constant were to be known and tight (i.e., locally accurate) around the barrier. This is because Lipschitz-based methods expand to the point x based on a reference point x ′ , and by definition, if x is added to the safe set so are all points on the line segment between x and x ′ . Hence, if there is a single point on this line segment which is unsafe (i.e., a "barrier"), the algorithm will never expand past it. This limitation does not exist for kernel-based algorithms as expansion occurs in function space.Moreover, note that for a non-stationary kernel such as in this example, ITL samples the "closest points" in function space rather than Euclidean space. We observe that SAFEOPT still samples "locally at the boundary" whereas ITL samples the most informative point which in this case is the local maximum of the sinusoidal function. In other words, ITL adapts to the geometry of the function. This generally leads us to believe that ITL is more capable to exploit (non-stationary) prior knowledge than distance-based methods such as SAFEOPT.K.4 Experiment Details K.4.1 Synthetic Experiments 1d task Figure 23 shows the objective and constraint function, as well as the prior. We discretize using 500 points. The main difficulty in this experiment lies in sufficiently expanding the safe set to discover the global maximum. Figure 24 plots the size of the safe set S n for the compared algorithms, which in this experiment matches the achieved regret closely.2d task We model our constraint in the form of a spherical "island" where the goal is to get a good view of the coral reef located to the north-east of the island while staying in the interior of the island during exploration (cf. Figure 25 ). The precise objective and constraint functions are unknown to the agent. Hence, the agent has to gradually and safely update its belief about boundaries of the "island" and the location of the coral reef. The prior is obtained by a single observation within the center of the island [-0.5, 0.5] 2 . We discretize using 2 500 points. Modeling the real-world dynamics We learn a feedback policy (i.e., "control gains") to compensate for inaccuracies in the initial controller. In our experiment, we model the real world dynamics and the adjusted model using the PD control feedback (Widmer et al., 2023) ,EQUATIONwhere x ⋆ are the unknown ground truth disturbance parameters, and s ⋆ and ṡ⋆ are the desired state and state derivative, respectively. This yields the following ground truth dynamics:EQUATIONThe feedback parameters x = [x p x d ] ⊤ can be split into x p tuning the state difference which are called proportional parameters and x d tuning the state derivative difference which are called derivative parameters. We use the "critical damping" heuristic to relate the proportional and derivative parameters: x d = 2 √ x p . We thus consider the restricted domain X = [0, 20] 4 where each dimension corresponds to the proportional feedback to one of the four rotors.Ground truth disturbance parameters are sampled from a chi-squared distribution with one degree of freedom (i.e., the square of a standard normal distribution), x ⋆ p ∼ χ 2 1 , and x ⋆ d is determined according to the critical damping heuristic.The learning problem The goal of our learning problem is to move the quadcopter from its initial position s(0) = [1 1 1] ⊤ (in Euclidean space with meter as unit) to position s ⋆ = [0 0 2] ⊤ . Moreover, we aim to stabilize the quadcopter at the goal position, and therefore regularize the control signal towards an action u ⋆ which results in hovering (approximately) without any disturbances. We formalize these goals with the following objective function:f ⋆ (x) def = -σ T t=0 ∥s ⋆ -s t (x)∥ 2 Q + ∥u ⋆ -u t (x)∥ 2 R (51)where σ(v) def = tanh((v -100)/100) is used to smoothen the objective function and ensure that its range is [-1, 1]. The non-smoothed control objective in Equation ( 51) is known as a linear-quadratic regulator (LQR) which we solve exactly for the undisturbed system using ILQR (Tu et al., 2023) . Finally, we want to ensure at all times that the quadcopter is at least 0.5 meter above the ground, that is,EQUATIONwhere we denote by s z t the z-coordinate of state s t . We use a time horizon of T = 3 seconds which we discretize using 100 steps. The objective is modeled by a zero-mean GP with a Matérn(ν = 5/2) kernel with lengthscale 0.1, and the constraint is modeled by a GP with mean -0.5 and a Matérn(ν = 5/2) kernel with lengthscale 0.1. The prior is obtained by a single observation of the "safe seed" [0 0 0 10] ⊤ .Adaptive discretization We discretize the domain X adaptively using coordinate LINEBO (Kirschner et al., 2019) . That is, in each iteration, one of the four control dimensions is selected uniformly at random, and the active learning oracle is executed on the corresponding one-dimensional subspace.Safety Using the (unsafe) constrained BO algorithm EIC (Gardner et al., 2014) leads constraint violation,26 while ITL and VTL do not violate the constraints during learning for any of the random seeds.Hyperparameters The observation noise is Gaussian with standard deviation ρ = 0.1. We let β = 10. The control target is u ⋆ = [1.766 0 0 0] ⊤ .The state space is 12-dimensional where the first three states correspond to the velocity of the quadcopter, the next three states correspond to its acceleration, the following three states correspond to its angular velocity, and the last three states correspond to its angular velocity in local frame. The LQR parameters are given by Q = diag {1, 1, 1, 1, 1, 1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1} and R = 0.01 • diag {5, 0.8, 0.8, 0.3}.The quadcopter simulation was adapted from Chandra (2023) .Each one-dimensional subspace is discretized using 2 000 points.We repeat the experiment for 25 different seeds where the randomness is over the ground truth disturbance, observation noise, and the randomness in the algorithm.Table 3 : Magnitudes of γ n for common kernels. The magnitudes hold under the assumption that X is compact. Here, B ν is the modified Bessel function. We take the magnitudes from Theorem 5 of Srinivas et al. (2009) and Remark 2 of Vakili et al. (2021) . The notation O(•) subsumes log-factors. For ν = 1/2, the Matérn kernel is equivalent to the Laplace kernel. For ν → ∞, the Matérn kernel is equivalent to the Gaussian kernel. The functions sampled from a Matérn kernel are ⌈ν⌉ -1 mean square differentiable. The kernel-agnostic bound follows by simple reduction to a linear kernel in |X | dimensions. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).X may be a multiset in which case repeated occurrence of x corresponds to independent observations of yx.Here f ⋆ (x) denotes the mean observation yx = f ⋆ (x) + ϵxIf A ̸ ⊆ S then "local" UNSA does not even converge to the irreducible uncertainty.The setting with target distributions PA can be reduced to considering target sets A (cf. Appendix E).That is, we restrict PA to the support of points with labels {3, 6, 9} (MNIST) or labels {0, . . . , 9} (CIFAR-100) and train a neural network using few examples drawn from the training set S.An alternative possibility is to weigh each point in An according to how likely it is to be the safe optimum. Which approach performs better is task-dependent, and we include a detailed discussion in Appendix K.1.The transductive bandit problem can be solved analogously to Safe BO, by maintaining the set An.One has to be careful to ensure that I(x; y) exists, i.e., |I(x; y)| < ∞. We will assume that this is the case throughout this work. When x and y are jointly Gaussian, this is satisfied when the noise variance ρ 2 is positive.βn(δ) can be tightened adaptively(Emmenegger et al., 2023).This can be achieved by taking a union bound and rescaling δ.Otherwise, with high probability, f ⋆ ( xn⋆ ) > f * ϵ, βn ⋆ .This is because the observation reduces uncertainty not just about the observed point itself.Because points f 1:9 are highly correlated, H[f 1:9 ] is already "small".We use a larger noise standard deviation ρ in CIFAR-100 to stabilize the numerics of batch selection via conditional embeddings (cf. Table2).This appears to improve the training, likely because it prevents overfitting to peculiarities in the finite sample A (cf. Figure16).In large-scale problems, the work ofColeman et al. (2022) suggests to use an (approximate) nearest neighbor search to select the (large) candidate set rather than sampling u.a.r. from PS . This can be a viable alternative to simply increasing k and suggests future work.That is, to stop training as soon as accuracy on a validation set from PA decreases in an epoch.In our experiments, we observe that the effect of various choices of ρ on this slight adaptation of the ITL decision rule has negligible impact on performance. The more prominent effect of ρ appears to arise from the batch selection via conditional embeddings (cf. Table2).We observe essentially the same performance with loss gradient embeddings, cf. Appendix J.2.This is because typically, there will always remain points in Sn \ Sn of which the safety cannot be fully determined, and since, they cannot be observed, it can also not be ruled out that they have high objective value.We provide an empirical evaluation in Appendix K.2.4.Recall that due to the assumption that ∥g ⋆ i ∥ k < ∞, g ⋆ i is indeed Lipschitz continuous.The use of uncertainty sampling for safe sequential decision-making goes back toSchreiter et al. (2015) andSui et al. (2015).This is because the proposed point typically remains in the optimistic safe set when it is sufficiently far away from the pessimistic safe set.On average, 1.6 iterations of the first 50 violate the constraints. 


Decision: The reviewers agree that the proposed framework is a novel and interesting generalization of active learning that can potentially be used in a variety of applications. They also appreciate the resulting theoretical guarantees. The main weaknesses mentioned were regarding situating the proposed method with regard to previous active learning methods (addressed in the rebuttals) and the strength of the generalization bounds. Due to the generality of the framework, I feel that this paper would be impactful as a foundation on which future work can be done. Therefore, I  would recommend to accept the paper.

Reviews: review: paper_summary: paper_summary: This paper introduces transductive active learning based on the uncertainty of GP when the labeling space and target space can be different. They have assumptions such as submodularity of information gain and information capacity’s sub-linearity in GP, resulting in a bound for variance of GP’s posterior with the proposed labeling algorithm. Under a specific setup, this can go to 0, and it cannot avoid the irreducible error when the deviation between labeling space and target space is larger. The various properties of the proposed algorithm(ITL and VTL) are examined by simple examples showing labeling in the target space as much as possible. 
The proposed algorithm's applications are interesting, including few-shot learning and safe BO (rarely considered in conventional active learning). These parts show the algorithm’s flexibility and applicability well. The results are promising.
strength_weakness: strength_weakness: This paper gives too little attention to conventional active learning. Although the novelty of the new area is essential in this paper, traditional active learning tasks are still popular. In this view, this paper does not provide strong evidence for the superiority compared to conventional active learning. At first glance, the proposed active learning algorithm seems too specific. In theoretical aspects, it is unsatisfactory to consider only the spaces. More clarification of theoretical aspects in the paper can be helpful to strengthen the paper. $gamma_n$’s sub-linearity can be clarified as the mathematical formula. In GP, the kernel is essential, and the experiments can reveal what kernel is best or robust. The discussion about kernels is too short.
questions: questions: Q1: What’s the difference between $\gamma_n$ and  $\gamma_{\mathcal{A},\mathcal{S}}(n).$ These notations can be improved.  
Q2: If only the target space is (uncountable) separable space, can the theorem have any change?
limitations: limitations: Not well-discussed
paper_summary: paper_summary: This paper introduces and considers approaches for the generalized (transductive) active learning problem, where the space of prediction targets and samples are not necessarily the same. The authors propose methods ITL and VTL to select samples in order to minimize the posterior uncertainty about the target function with the target space $A$. They prove favorable properties of these methods and compare their performance to other active learning techniques on empirical settings, including batch active learning and safe Bayesian optimization.
strength_weakness: strength_weakness: - The paper is quite dense and long, with a total of 68 pages when appendices are considered.
questions: questions: 1. How does the computational cost of the methods fare in practice to other methods?
limitations: limitations: Yes
paper_summary: paper_summary: The paper investigates the generalization of active learning to scenarios with specific prediction targets and limited information due to constrained sample spaces, offering a flexible framework adaptable to various domains such as recommender systems, molecular design, and robotics. It introduces novel generalization bounds of independent interest for active learning. The practical performance of the model relies on its ability to capture correlations between points (learning the latent structure) and accurately estimate uncertainty. The study demonstrates that sampling relevant and diverse points significantly improves performance across various applications, surpassing the state-of-the-art methods.
strength_weakness: strength_weakness: The authors use MNIST and CIFAR100 as experiments on active few-shot tuning. First, image classification is a well-studied topic and lack of novelty. Image classification uses convolutional networks for classifier while current LLMs uses auto-regressive models therefore most of theoretical assumptions and results might not be able to extend. Even though the paper is well-written, the claims that the results shall be able to extend to prompt optimization is groundless. It would be more interesting to study the prompt tuning/efficient data selection for fine-tuning LLMs. 
Second, the baselines for active learning is not state-of-the-art. For instance, there are more state-of-the-art baselines than badge, typicluster and probcover, for AL domains in image classification. Moreover, there has been work in using influence function to select data to fine tune LLMs or image classifications that worth comparing.
questions: questions: N/A
limitations: limitations: N/A
paper_summary: paper_summary: This paper considers active learning with Gaussian Process in a transductive setting where the learner wants to optimize the model performance on a target space A while it can only sample from a sample space S. It proposes a few algorithms that sequentially choose the example that minimizes a few variations of "posterior uncertainty" of the model on A. Assuming the measure for such uncertainty is submodular, it provides bounds on the convergence rate of the proposed algorithm. Empirically, it evaluates the proposed methods on two scenarios: fine-tuning and safe Bayesian optimization.
strength_weakness: strength_weakness: - My major concern is novelty and significance:
  - The main idea of the proposed query strategy is to minimize posterior uncertainty. This is a well-known method in active learning, and it is an especially straightforward choice in a Bayesian setting. 
  - For the theoretical results, I'm not very familiar with Gaussian Process literature, but I'm not convinced that the theoretical guarantees in Section 3.1 and 3.2 are nontrivial. It would help readers appreciate the results if the authors could clarify the challenges of obtaining such results, tightness of the bounds, how strong it is compared to other baseline sample strategies, or any new insights from such bounds.

--------
I've read author feedback. Now I agree that the theoretical part offers interesting techniques and results (which roughly matches known results in similar problems), but I personally think the results are still a bit unsatisfactory (specifically, the dependency on |S|, the RHS of the bound in Thm 3.3 can grow with n increases). In addition, since this paper claims the theory part is one of the major contributions, it would be better if there are more explanations, discussions, and comparisons for the results.

Apart from that, I still tend to think the proposed AL approach is a well-known idea in active learning and applying it to transductive learning is a bit natural, so the contribution of this part is not significant enough for a top conference. And I agree with reviewer aHJz that "few-shot fine-tuning of large neural networks" is a bit oversold.
questions: questions: In addition to issues in the Weaknesses section, a few questions:

- For Section 4, 
  - is there any existing Bayesian active learning algorithms that can be used as baselines in this setup?
  - it is mentioned in line 213-214 that "we will focus here on .. $A \cap S = \emptyset$", but in Figure 3 and line 243 it is comparing samples from $P_A$. How can the algorithm sample from $P_A$ if the sample space S does not intersect with A? What is the exact setup of the experiments?
  - How do you choose hyperparameters for the baselines?

- For section 5, I'm not familiar with this task, but in my opinion, it does not provide enough details and explanations. For example
  - What exactly is your sample strategy? In particular, how do you ensure the chosen samples are safe? In line 276 it says "a natural choice for the target space of safe BO is A_n", but it looks like A_n can be unsafe.
  - In line 317-318, "VTL minimizes marginal variances, .. which are decisive for expanding the safe set". Why?
limitations: limitations: N/A

Comments: title: Response to reviewer’s comment
Reply to the Rebuttal
Brief List of Notation
Discussion Period
Discussion Period
Ask for Clarification
comment: Dear reviewer, we would like to thank you for your efforts in reviewing our submission and pointing us to the related work on influence functions. We will include the above comparison to this line of work in our updated version.

Regarding our citation of [1], our intention was to mention that in future work, the methods of this submission could potentially be extended to the setting described in [1].
We did *not* intend to suggest that this submission is an extension to [1].
We agree with the reviewer that our methods cannot be applied trivially (due to the different learning paradigms), however, selecting relevant and diverse data seems also to be important for the fine-tuning of LLMs (as argued in the limitations of [2]).
We will clarify this in the updated version, and thank the reviewer for highlighting this.

With only one day left, we would appreciate it if the reviewer can express their thoughts about our latest comment and potentially raise their score.

[1] Hardt, M. and Sun, Y. Test-time training on nearest neighbors for large language models. ICLR, 2024.

[2] Xia, Mengzhou, et al. ”Less: Selecting influential data for targeted instruction tuning.” In ICML, 2024.
We sincerely appreciate you for reviewing and giving insightful comments on our manuscript. Thank you.
We would like to thank you for your efforts in reviewing our work and for recognizing its relevance to the broader ML community.
We sincerely thank you for reviewing and giving insightful comments on our manuscript.
Thanks again for the detailed explanation. I will adjust my review.
We thank the reviewer for their continued look into our new theoretical results.
We will add a version of this table of notation to the camera-ready version as well as a brief discussion on related results from other problem settings. Thank you for this suggestion and improving our work in this regard.

> Is this notion of "constant" $C$ also standard in literature? I'm a bit concerned about it since it involves many factors which do not look negligible to me. In particular, it looks not very strong to me since it scales linearly in $|\mathcal{S}|$, and it involves maximum initial variance for every example in A. And perhaps it can be clearer if you can explain exactly what it is (up to universal constants) in some specific examples.

The dependence on the initial variance is standard in kernelized analysis of bandits. Usually it is assumed that the kernel is such that $k(\boldsymbol{x},\boldsymbol{x}) \leq 1$ which alleviates this.
In our analysis, the dependence on $|\mathcal{S}|$ is required to achieve convergence to the irreducible variance (kindly see the discussion below).
We would be happy to make this dependence evident in the main theorem statement if the reviewer thinks this is important.
A linear dependence on the size of $|\mathcal{S}|$ is standard in works on safe exploration (i.e., where "extrapolation" is required due to restrictions on the domain) [see, e.g., 1].

We further thank the reviewer for the suggestion, and will update the appendix to clarify whenever we mention "universal constant" what this term is a constant with respect to.

> I would expect there to be a smoother transition between (1) and (2) as x moves into . Is there any explanation why it goes from  to  directly?

The difference in rates is indeed interesting.
In our analysis this stems from using a "nested" learning problem that learns the function over all of $\mathcal{S}$.
This appears to be required in our view to achieve the *very strong* convergence to the *irreducible* variance $\eta_{\mathcal{S}}^2(\boldsymbol{x})$, since there is a slight mismatch between the original learning problem wrt. $\mathcal{A}$ and a different learning problem wrt. $\mathcal{S}$.
It might be possible to obtain tighter results in the special case $\mathcal{S} \subseteq \mathcal{A}$ (i.e., when the two learning problems are not misaligned).
We are inclined to leave this study as an interesting direction for future work.

> Tightness of Thm 3.3: For results that you cited (e.g. [3, Theorem 4]), the regret diminishes as $n\to\infty$, but for your bound, the irreducible part gets even larger. Can you comment on this?

We would like to point out that in the referenced works on bandits no "extrapolation" is required since *all* points can be observed directly. These works therefore do not have a notion of "irreducible error".
However, we agree while the slight increase of this error in the agnostic setting is likely an artifact of us performing the analysis in a Bayesian setting, in this Bayesian setting this error is tight.

> Proof: For the inequality following line 1225, how is the $\bar{\kappa}_n$ term bounded?

It follows from Assumption 3.1 (submodularity) that $\bar{\kappa}_n \geq 1$. We have updated the proof to make this more explicit.

---

We would further like to highlight that due to the large set of instances of *transductive* active learning, our results constitute new results in multiple settings:
1. The *extrapolation* to points outside $\mathcal{S}$ which unlocks the application to Safe BO, leading to a new sota algorithm.
2. *Directed* learning where $\mathcal{A} \subseteq \mathcal{S}$. Here the analysis simplifies and we prove the rate $\gamma_{\mathcal{A},\mathcal{S}}(n)/n$.

Finally, we would like to mention that beyond our theoretical contributions, the application of transductive active learning to two new applications, Safe BO and the discussed fine-tuning setting, are also key contributions of our work.
In both of these settings our findings show that our proposed approaches to transductive active learning substantially improve upon the current state of the art.

We hope that upon reevaluation these substantial contributions are acknowledged by the reviewer by increasing their score.

---

1. Sui, Yanan, et al. "Safe exploration for optimization with Gaussian processes." International conference on machine learning. PMLR, 2015.
Dear reviewer,

Thanks for your active engagement in the rebuttal period. We have a follow up question on your comment:

“However, I think fine-tuning model weights for image classification task would not serve as a novel contribution.”

First, while we might be of a different opinion, we respect your opinion regarding the contribution of our fine tuning experiments. However, we would like to mention that there are some very important other contributions of our paper that should also be considered in the evaluation (below is a non exhaustive list):

1. We formulate the problem of TAL which results in natural decision rules/acquisition functions of ITL, VTL.

2. We are the first to give uniform convergence rates for the posterior uncertainty in regions beyond the sample space. This implies a new generalisation bound for RKHS functions. Note that our assumptions are very general and common in active learning literature. 

3. We evaluate our method on two distinct domains, (i) fine-tuning of large neural networks and (ii) safe BO. In both cases, our method outperforms the baselines.

We hope this clarifies our contributions further. Moreover, even though the reviewer thinks our contribution for the fine tuning case are not novel, our work has other significant contributions. Given these contributions, we kindly ask the reviewer to reconsider their evaluation of our work. Looking forward to the reviewer’s response.
Thanks for the explanation and the added list of notation! I think it would make the paper clearer if some of them are added to the future version (e.g. list of notation, how the results or parameters compared to existing literature, and what they would be in some examples like Table 3).

I still have a few questions:

- Tightness of Thm 3.2: 
  - Is this notion of "constant" C also standard in literature? I'm a bit concerned about it since it involves many factors ($\sigma^2$, $|S|$, $1/\lambda_\min(K)$) which do not look negligible to me. In particular, it looks not very strong to me since it scales linearly in  $|S|$, and it involves maximum initial variance for every example in A (if $\sigma_0^2(x)$ is mostly small but extremely big for some points, the bound of $\sigma_n^2(x)$ would be quite big, even for x such that $\sigma_0^2(x)$ is small). And perhaps it can be clearer if you can explain exactly what it is (up to universal constants) in some specific examples.
  - I would expect there to be a smoother transition between (1) and (2) as x moves into $A\cap S$. Is there any explanation why it goes from $1/\sqrt{n}$ to $1/n$ directly?

- Tightness of Thm 3.3: For results that you cited (e.g. [3, Theorem 4]), the regret diminishes as $n \to \infty$, but for your bound, the irreducible part gets even larger. Can you comment on this?

- Proof: For the inequality following line 1225, how is the $\bar{\kappa}_n$ term bounded?
Thanks for your reply. Almost all my concerns are resolved.  I only want the results applied in the conventional AL learning setups, which can be expected shown in other chances. 
I'll keep my score.
Hi I have read all the rebuttals. I do appreciate the authors efforts in literature review and agree that the references the authors list are more comprehensive. However, I think fine-tuning model weights for image classification task would not serve as a novel contribution and the learning paradigm for fine tuning deep neural networks is different from fine tuning LLMs as LLMs are generative models (the authors cite [1] and argue this paper could be an extension for the future work for fine-tuning the model for each prompt.) I think the contribution below is not novel and a bit vague.

"We apply the transductive active learning framework to batch-wise active few-shot fine tuning of large neural networks and to safe Bayesian optimization. We empirically show, in both cases, that ITL and VTL outperform the state-of-the-art.

[1] Hardt, M. and Sun, Y. Test-time training on nearest neighbors for large language models. ICLR, 2024.

I would lean towards keeping my score.
Thank you for your response. I read the reviews and the responses. I lean towards keeping my score.
As requested, the following includes a brief list of notations that are defined in the appendix. Kindly let us know if you have a question about any other symbol.

| Symbol | Reference |
|-|-|
| $\sigma^2$ | maximum initial variance (line 1015) |
| $\tilde{\sigma}^2$ | maximum [initial variance + noise variance] (line 1016) |
| $\Delta_{\mathcal{A}}(\boldsymbol{x} \mid X)$ | marginal gain (Lemma C.2) |
| $\Gamma_n$ | maximal marginal gain in iteration $n+1$ (line 1084) |
| $\alpha_{\mathcal{A}, \mathcal{S}}(n)$ and $\alpha_n$ | task complexity (definition C.6) |
| $\bar{\kappa}(X \mid D)$ | information ratio (eq. (8)) |
| $\kappa_{\mathcal{A}}(n)$ | submodularity ratio (definition C.10) |
| $b_{\epsilon}$ | bound on size of approx. Markov boundary (eq. (16)) |

The definitions of $\alpha, \bar{\kappa}, \kappa$ are all to generalize to instances where Assumption 3.1 is satisfied approximately. Under Assumption 3.1, all can be bounded trivially: $\alpha \leq 1$ and $\bar{\kappa}, \kappa \geq 1$.
We thank the reviewer for taking a close look at our novel convergence guarantees.

> It is still unclear to me how strong/tight your results are. It would be easier if you could refer to some similar upper or lower bounds.

One can show that $\sigma_n^2(\boldsymbol{x}) \geq \frac{1}{n+1} \sigma_0^2(\boldsymbol{x}) \in \Omega(1/n)$ which is achieved if the point $\boldsymbol{x}$ is sampled repeatedly (and no other points have to be generalized to). Please see eq. (7.26) of [1]. The derivation is along the lines of [2, Section 2].
In particular, our eq. (2) is tight up to $\gamma_n$.

Our results in the agnostic kernelized setting (Theorem 3.3) match regret bounds of kernelized bandit algorithms in the same setting.
For example, [3, Theorem 4] prove for the celebrated and widely used GP-UCB algorithm that $R_n / n \leq \widetilde{O}(\frac{\gamma_n + \|\|{f^*}\|\|_k \sqrt{\gamma_n}}{\sqrt{n}})$ where $R_n$ is the cumulative regret up to round $n$ and $\widetilde{O}(\cdot)$ subsumes log-factors.
A similar result can be found in [4, Theorem 3] (ICML 2020 Test of Time Award winner).
Our results match the rates of results in this widely cited and often applied line of work on kernelized bandits.

> For Thm 3.2, is $C$ a universal constant, or it depends on other things? Specifically, how does it scale with the size of $\mathcal{A}$, $\mathcal{S}$, or $\mathcal{X}$, and what happens if they're infinite (I saw your comment to Reviewer WV1c13, but could you give some quantitative characterization)?

You can find the constant $C$ defined precisely in the proof of Theorem 3.2 (cf. lines 1227 and 1229). $C$ is independent of $n$.
For a finite discretization of a continuous domain, our results hold as stated in the main body of the paper.
We generalize our analysis to continuous domains when the RKHS is finite-dimensional in Section C.6.4.
With this generalization, intuitively, the dimensionality of the RKHS assumes the role of the size of $\mathcal{S}$ from the finite setting.

> For thm 3.3, how realistic are the assumptions (bounded norm for f*, sublinear \gamma_n)?

$f^*$ has bounded norm iff it is element in the corresponding RKHS. We remark that for standard kernels (such as RBF/squared exponential or Matérn kernels), the space of functions is extremely large; containing, e.g., the smooth or the continuous functions defined over $\mathcal{X}$.
Our dependence on $\|\|f^*\|\|$ and $\gamma_n$ are standard compared to the large literature on kernelized bandits [e.g., 3] as discussed above.

We provide the magnitudes of $\gamma_n$ for common kernels in Table 3 (last page of Appendix). $\gamma_n$ is logarithmic in $n$ for many common kernels. We further remark that $\gamma_n$ is a very standard measure of "information capacity" / "function class complexity" in the literature on kernelized bandits. [3] is merely one of the many works that fundamentally rely on this notion.

> It looks \beta_n is increasing as n increases, won't this make the bound very weak?

Yes, $\beta_n(\delta)$ is increasing with $n$, however, only very slowly at the rate $\sqrt{\gamma_n}$.
This dependence on $\beta_n$ is standard in the literature on kernelized bandits [e.g., 3, Theorem 2].

> Why isn't there a term that characterizes how close f* can be approximated by the model class (Gaussian process)?

The term $\|\| f^* \|\|$ measures "how easy" it is to find $f^*$ within the model class (the RKHS) with $\|\| f^* \|\| = \infty$ if $f^*$ is not at all in the model class.
The term $\gamma_n$ measures the "size" / "capacity" of the model class.

> For Lemma C.16 and the comments thereafter, how can you conclude b_\epsilon is universal constant? doesn't it depends on all other terms in inequality (15)?

We mean "universal" with respect to $n$ and $\boldsymbol{x}$. We are very sorry for the confusion and have updated this line to point this out explicitly. Thank you for highlighting this!

---

In summary, we would like to mention:

1. Our results match rates of prior work from the widely recognized and large literature on kernelized bandits. We use the same measures of size and complexity of model class as most works from kernelized bandits.

2. Our dependence on $\gamma_{\mathcal{A}, \mathcal{S}}(n)$ can be dramatically better than $\gamma_n$, since this only measures the information capacity of prediction targets $\mathcal{A}$ as opposed to of the entire domain $\mathcal{X}$.

We hope to have addressed the reviewer's questions adeptly.
We are happy to answer any other questions that may help with the interpretation of our results!

---

1. Williams and Rasmussen. Gaussian processes for machine learning, volume 2. MIT press Cambridge, MA, 2006.
2. Opper and Vivarelli. General bounds on bayes errors for regression with gaussian processes. NeurIPS, 11, 1998.
3. Chowdhury and Gopalan. On kernelized multi-armed bandits. ICML, 2017.
4. Srinivas et al. Gaussian process optimization in the bandit setting: No regret and experimental design. ICML, 2010.
Since one of the main claimed contributions is the theory part, I would like to take a deeper look. I'm not very familiar with theory in gaussian process or bayesian learning, so it would take some time.

Questions and comments so far:

- Given there are a lot of notations involved, it would be clearer if you could provide a list of notations for reference.

- It is still unclear to me how strong/tight your results are. It would be easier if you could refer to some similar upper or lower bounds.
  
  - For Thm 3.2, is C a universal constant, or it depends on other things? Specifically, how does it scale with the size of A, S, or X, and what happens if they're infinite (I saw your comment to Reviewer WV1c13, but could you give some quantitative characterization)?  
  
   - For thm 3.3
      - how realistic are the assumptions (bounded norm for f*, sublinear \gamma_n)? 
      - It looks \beta_n is increasing as n increases, won't this make the bound very weak?
      - Why isn't there a term that characterizes how close f* can be approximated by the model class (Gaussian process)?

- For Lemma C.16 and the comments thereafter, how can you conclude b_\epsilon is universal constant? doesn't it depends on all other terms in inequality (15)?
Dear Reviewer,

We hope this message finds you well. We have noticed that our detailed rebuttal, addressing each of the concerns raised in your review, has not yet received any feedback. We understand the demanding nature of the review process and appreciate the time and effort invested in evaluating our work.

We kindly urge you to consider our responses to your questions, as we believe they adeptly address your concerns. With some days left, we hope we can still have a fruitful rebuttal period.

Thank you, Authors
Dear Reviewer,

We hope this message finds you well. We have noticed that our detailed rebuttal, addressing each of the concerns raised in your review, has not yet received any feedback. We understand the demanding nature of the review process and appreciate the time and effort invested in evaluating our work.

We kindly urge you to consider our responses to your questions, as we believe they adeptly address your concerns. With some days left, we hope we can still have a fruitful rebuttal period.

Thank you, Authors
1. There are some active learning papers published in vision venues. 
[1] Li, Jingyao, et al. "Bal: Balancing diversity and novelty for active learning." IEEE Transactions on Pattern Analysis and Machine Intelligence (2023).
[2] Parvaneh, Amin, et al. "Active learning by feature mixing." Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. 2022.

2. Below are references for influence function to finetune language models or image classification tasks. 
[1] Kwon, Yongchan, et al. "Datainf: Efficiently estimating data influence in lora-tuned llms and diffusion models." arXiv preprint arXiv:2310.00902 (2023).
[2] Liu, Zhuoming, et al. "Influence selection for active learning." Proceedings of the IEEE/CVF international conference on computer vision. 2021.
[3] Zhao, Zhuokai, Yibo Jiang, and Yuxin Chen. "Direct Acquisition Optimization for Low-Budget Active Learning." arXiv preprint arXiv:2402.06045 (2024).
[4] Xia, Mengzhou, et al. "Less: Selecting influential data for targeted instruction tuning." arXiv preprint arXiv:2402.04333 (2024).
We thank the reviewer for their review. To address the points raised in our rebuttal effectively, we kindly ask for some clarification and additional references.

> For instance, there are more state-of-the-art baselines than badge, typicluster and probcover, for AL domains in image classification.

We would greatly appreciate it if the reviewer could point us to those state-of-the-art baselines. We would be more than happy to compare against additional approaches. To the best of our knowledge, BADGE, TypiClust, and ProbCover are some of the most widely recognized and best-performing AL methods for neural network training to date.

> Moreover, there has been work in using influence function to select data to fine tune LLMs or image classifications that worth comparing.

As we are not fully familiar with this specific line of work, we would be grateful if the reviewer could provide references that they believe are relevant for comparison.

Thank you in advance for your assistance in providing these clarifications. We believe that this will facilitate a more productive rebuttal process.