Transductive Active Learning: Theory and Applications
Authors: Jonas Hübotter
Bhavya Sukhija
Lenart Treven
Yarden As
Andreas Krause
Venue: NeurIPS 2024 poster (2024)
Keywords: active learning
experimental design
bandits
Bayesian optimization
neural networks
deep learning
fine-tuning
transfer learning
transductive learning
generalization
extrapolation
Primary area: active_learning
TL;DR: We develop a theory for automatic data selection when you know what you want to learn. We show that knowing what you want a model to learn can be leveraged to learn much more efficiently than just trying to learn "everything".

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.

Transductive Active Learning: Theory and Applications
Jonas Hübotter"
Bhavya Sukhija
Department of Computer Science ETH Zürich, Switzerland
Department of Computer Science ETH Zürich, Switzerland
Lenart Treven
Yarden As
Department of Computer Science ETH Zürich, Switzerland
Department of Computer Science ETH Zürich, Switzerland
Andreas Krause
Department of Computer Science ETH Zürich, Switzerland
Abstract
We study generalization of classical active learning real-world settings with concrete prediction targets where sampling 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 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 large neural networks and safe Bayesian optimization, where they achieve tfate-of-the-ant performance.
Introduction
Machine learning, 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 over domain X:: How can we learn sample-eficiienty from (noisy) observations? This problem widely studied in active learning and experimental design (Chaloner & Verdinelli, 1995; Settles, 2009).
Active learning methods commonly aim learn 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
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 comprehensive overview of related work Section
"Directed" transductive active learning We consider the generalized problem of transductive active learning, where given two arbitrary subsets of the domain X: target space A X, and sample space C X, we study the question:
How learn within A by actively sampling observations within S?
Coorreppondence jonas huebotterdinf. ethz.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

This problem is ubiquitous in real-world applications such as safe Bayesian optimization, where S 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 model to A. Figure visualizes some instances of transductive active learning.
A
B
C
D
S
Figure Instances of transductive active learning with target space A shown in blue and sample space S shown in gray. The points denote plausible observations within S "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 to- wards learning about a particular target. Prior work on inductive active learning has focused on the instance S.
Whereas most prior work has focused on the "global" in- ductive instance = = S, MacKay (1992) was the first to consider specific target spaces A and proposed the principle of selecting points in S to minimize the "poste- rior 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., model f as a Gaussian process
2023). In this work, (cquivalently) as a function 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 (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- in the batch-wise active fine-tuning of neural networks for image classification (Section 4) and in safe Bayesian optimization (Section 5).
2 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() by fa. and joint random vectors ] for some X C X, XX] < do by fx. Let yx denote the noisy observations of fx. {ye = fx + Exe JæE,, where Eæ is independent noise.² We study the "adaptive" setting, where in round the agent selects point æ,, E S and observes Un ya, The agent's 's choice of T,, may depend on the outcome of prior observations Dn21 del [(x) y: Fien.
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[] is one possible measure of uncertainty about f and the conditional entropy Hif 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 y. We denote the information gain about A from observing X by I(fai Ux). The maximum information gain about A from n observations within S is
(n) def max 1(ffa XCS I
This "information capacity" measures the information about f, 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 Yn 7x (n) (n))(n) S 7ss holds uniformly for all A, S, and n due to the data processing inequality. Generally, (A,ss(n) can be substantially smaller if the target space is sparse subset of the sample space.
del xxxx We remark that
X may be multiset in which repeated occurrence of æ corresponds to independent observations of ye-

---

3
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 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 largets, H[fa], and (2) their total variance, Ex' E.A Var[far] The corresponding decision rules are
En arg min H[fA D 1n Vum] arg max Un (Dn-1); #ES
(ITL.)
#ES
En arg min Var [fa (n
(VTL)
#ES
with an implicit expectation over the feedback Y/-- That is, ITL. (short for Information--ased Transductive Learning) and VTL (Variance-based TL) select F, so as to minimize the uncertainty about the prediction targets fA (in expectation) after having received the feedback Yn- Unlike VTL, ITL takes into account the mutual dependence between points in A. These decision rules were suggested previously (MacKay, 1992; Seo 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 C A, ITL reduces to In arg es I[fei Dn-1),, i.e., is "undirected" and reduces to standard uncertainty based active learning strategies (cf. Appendix C.I). 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 (X) = I(fAi yx) is submodular. In the case of VTL, the variance reduction (X) tr Varlfal - tr Varifa Vx is submodular.
Under this assumption, ( is constant factor approximation of ma (X) due to the seminal result on submodular function maximization by Nemhauser al. (1978). Similar assumptions have been made, e.g., by Bogunovic et al. (2016) and Kothawade et al. (2021), Assump- tion 3.1 is satisfied exactly for ITL when S A and is a Gaussian process (cf. Lemma C.9), and we provide extensive discussion of our results in Appendix C.4 for instances where Assumption 3.1 satisfied approximately, relying on the notion of weak submodularity (Das & Kempe, 2018).
3.1 Gaussian Process Setting
When f ~ (P,,, k) is a Gaussian process (GP, Williams & Rasmussen, 2006) with known mean function μ and kernel k, and the noise a mutually independent and zero-mean Gaussian with known variance, the ITL and VTL objectives have closed form expression (cf. Appendix F) and can be optimized efficiently. Further, the information capacity "n is sublinear in n for 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 a E A''s S. To this end, we derive bounds on the marginal posterior variance o² (x) = Varif(x) 'D,]] 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 rich class of GPs. To the best of our knowledge, this work is the first to present such bounds.
def
We define the irreducible uncertainty as the variance of f(x) provided complete knowledge of f in S:
I (x) del Varifa fsl.
As the name suggests, (x) represents the smallest uncertainty one can hope to achieve from observing only within S. For all S, it is easy to see that nz(x)) O. 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
3

---

and kernel k the noise Eæ is mutually independent and zero-mean Gaussian with known variance, and "/n sublinear n. Then there exists constant C such that for any 2 and æ E A.
(x) S TT)( + +C PAA.(n))
(1)
Vn
irreducible
reducible
Moreover, i E AnS, there exists a constant C' such that
(x) C' TA..(n) n
(2)
Intuitively, 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 all prediction targets æ E 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 faster convergence due smaller information capacity (n. < 7n. Equation (2) matches prior results for the setting S = A. We provide formal proof of Theorem 3.2 in Appendix C.6.
3.2 Agnostic Setting
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, as a (misspecified) model of ʃ", with some kernel lt and zero mean function pa.) = O. We denote by (x))))) = [x) 'D.]] the posterior mean of f. W.l.o.g. assume in the following result that the prior variance is bounded, i.e., Var[f(x:) S 1.
the model f from Section 3.1
Theorem 3.3 (Bound on approximation error for ITI. and VTI., following Abbasi-Yadkorf (2013): Chowdhury& & Gopalan (2017)). Let Assumption 3.1 hold and the data be selected by either ITL or VTL. Pick any å E (0, 1). Assume that f lies the reproducing kernel Hilbert space (x) of the kernel k with norm [[f ll 0o, the noise is conditionally p-sub- Gatb-aaasnnn and "in is sublinear in n. Let (5) = |[ ll + PV/((mn +1 1og(1/6)). Then for any n 2 1 and x E A, jointly with
probability at least
8.
(fx))) - pn(2))] S (0)
ns(x)) - (A
irvdducible
reducible
where (n) denotes the reducible part of Equation (1).
We provide formal proof of Theorem 3.3 in Appendix C.7. Theorem 3.3 generalizes approximation error bounds prior works to the extrapolation setting, where some prediction targets æ A lie outside the sample space S. For prediction targets æ E 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.
3.3 Experiments in the Gaussian Process Setting
Before demonstrating ITL and VTL on GPs develop more intuition, we introduce natural correlation based baseline, which will later uncover connections to existing approaches:
Bn arg max
Σ A.EAAA
Corlfai Sa Dn-i)-
(CTL)
How does the smoothness of affect ITL? We contrast two "extreme" kernels: the Gaussian kernel k(ær, æ²) exp(- æ 2/1 / /2) and the Laplace kernel k(æ, xx) exp( || x In the -quane sense, the Gaussian kernel yields a smooth process f whereas the Laplace kernel yields continuous but non-differentiable f (Williams & Rasmussen, 2006). Figure 2 shows
Here f (æ) denotes the mean observation ya (x) ca

---

Gaussian Kernel
Laplace Kernel
Figure 2: Initial 25 samples ITL under a Gaussian kernel with lengthscale (left) and Laplace kernel with lengthscale 10 (right). Shown in gray is the sample space S and shown in blue is the target space A. In three of the four examples, points outside the target space provide useful information.
ITL
CTL
LOCAL UNSA
RANDOM
UNSA
TRUVAR
Entropy of fA
Ska Dev m A
Number of Iterations
500
0
Number of Iterations 500
Figure 3: Entropy of fA ranging from -3850 to 3325 and the mean marginal standard deviations of fA ranging from 0 to 0.15. Experiment using the Gaussian kernel of the left instance (A C S) from Figure 2. It can be seen that ITL and VTL outperform UNSA and RANDOM. Uncertainty bands correspond to one standard error over 10 random seeds.
how ITL adapts to the smoothness of f: Under the "smooth" Gaussian kemel,, points outside A provide higher-order information. In contrast, under the "rough" Laplace kernel and if AA C S, points outside A do not provide any additional information, and therefore are not sampled by ITL. If, however, A g S, information "leaks" A even under 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 with high prior uncer- tainty: Hn, = arg max (x)) This in stark contrast to ITL and VTL which select points æ that minimize posterior (epistemic) uncertainty about A. It can be seen that UNSA is the special "undirected" case of ITL when S C AA and observation noise is homoscedastic (cf. Appendix C.I).
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, ITI. and VTI. outperform "local" UNSA (i.e., UNSA constrained to AnS) which neglects all information provided by points outside A.* one would expect, VTL. has an advantage with respect to reducing the total variance of fA, whereas ITL reduces the entropy of fA faster. We include ablations in Appendix H where we, in particular, observe that the advantage ITL and VTL over UNSA increases as the volume of prediction targets shrinks in comparison to the size of domain.
4 Active Fine- Fine-Tuning of Neural Networks
Fine-tuning large pre-trained model is cost- and computation-effectiee approach to improve performance on 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 supervised setting, where the function f maps inputs æ X' to outputs E V. We have access
'If' A g S then "local" UNSA does converge the irreducible uncertainty.
5

---

to noisy samples from 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 Pa on X. The goal is to actively and efficiently sample from S to minimize risk with respect to Pa. We show in this section that ITTI and VTI. 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(; 0) as linear function in a latent embedding space, f(æ;; 0) x 3 Φo (2), with weights 3 E IP and embeddings Φo X + RP, 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 wldra-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 comprehensive overview of embeddings in Appendix J.2. Now, supposing the prior B ~~ (O, E), 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')/ / /kxx, 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 3 (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 33 for prediction. This extends recent work which has studied estimators of this generalization error (Wei et al., 2022).
Diversity via conditional embeddings Efficient labeling and training necessitates a batch-wise selection of inputs. The selection of batch of size 6 >> 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 al., 2024). An information-based batch-wise selection strategy is formalized by the following non- adaptive transductive active learning problem (Chen & Krause, 2013) and the greedy approximation of B, by ITL which selects elements Tn of the n-th batch iteratively based on In,1::-1:
Batch selection:
B arg max I(fAi Vp B
Da-1);
Tn. = arg max I[fAi Vv
DD Ven.aa .)
(3)
#ES
The batch B, is diverse and informative by design. We show that under Assumption 3.1, B/ Dn,1:b yields a constant- factor approximation of B, (ef. Appendix C.3).
4.1 Experiments on Active Fine-Tuning
Our empirical evaluation is motivated by the following practical example: We deploy pre-trained image classifier to user's phones who use it within their local environment. We would like to locally fine-tune 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., = (), and discuss alternative instances such as active domain adaptation in Appendix I.
Testheds & 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. 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 EfficientNei-B00 (Tan & Le, 2019) traitedd on ImageNet (Deng et al., 2009), augmented by final fully-connected layer. We train the NNs using the cross-entropy loss and the ADAM optimizer (Kingma & Ba, 2014).
Results 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 PA (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 PA (e.g., maximizing cosine similarity to target embeddings as is common in vector databases;
'The setting with target distributions Pa can be reduced to considering target sets (cf. Appendix E). 'That is, we restrict Pa to the support of points with labels [3, 6, 9) (MNIST) or labels (0, (CIFAR- 100) and train neural network using few examples drawn from the training set S.

---

ITL
CTL
ID
RANDOM
VTL
COSINESIMILARITY
BADGE
MNIST
CIFAR 100
100
100
80
Accuracy
80
60
40
60
20
# Samples from P4
100
400
50
200
0-
20
40
60
80
100
0
20
40
80
100
Number of Samples
Number of Batches of Size 10
Figure 4: Active fine-tuning MNIST (left) and CIFAR-100 (right). RANDOM selects each observation uniformly at random from S. The batch size is for MNIST and for CIFAR-100 Uncertainty bands correspond active learning with ITL. and VTL significantly outperforms competing methods, and particular, retrieves substantially more samples from the support of PA.. See Appendix for details and ablations.
standard error over 10 random seeds. We that transductive
Settles & Craven, 2008; Johnson et al., 2019). INFORMATIONDENSITY (ID, Settles & Craven, 2008) heuristic approach aiming combine (i) diversity and (ii) relevance. In Appendix J.5, also compare against wide range of additional baselines (c.g., CORESET (Sener & Savarese, 2017). TYPICLUST (Hacohen al., 2022), PROBCOVER (Yehuda al., 2022), etc.) that fall into one 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 as well as all baselines. We see that relevance- methods such as COSINESIMILARTY have an initial advantage over RANDOM but for batch sizes larger than they quickly fall behind due to diminishing informativeness of the selected data. In contrast, diversity-based methods such as BA AGE are more competitive with RANDOM but do not explicitly aim retrieve relevant samples.
Remarkably, transductive active lcarning outperforms random data selection even in the MNIST experiment where the model is randomly initialized. This suggests that the learned embeddings 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 a given query AA) which leads the significant improvement upon the state-of-the-arr in Figure 4. Notably, for a batch size and query size of and if correlations are non-negative, ITL, VTL, CTL, and the canonical cosine similarity are equivalent. CTL can be seen as direct generalization of cosine similarity- retrieval to batch and query sizes larger than one. contrast to CTL, ITL and VTL may also sample points which exhibit strong negative correlation (which is also informative).
We observe empirically that ITL obtains samples from PA 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 This phenomenon manifests for both MNIST and CIFAR- 100, as well as imbalanced datasets S or imbalanced reference samples from PA (cf. Appendix J.6). The improvement in accuracy appears to increase in the large-data regime, where learning tasks become more difficult. Akin to a previously identified scaling trend with size of the pre- training dataset (Tamkin al., 2022), this suggests a potential scaling trend where the improvement of ITL over random batch selection grows models fine-tuned larger pool of data.
7

---

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.
5 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 problem
max (ax) where = E X (x) 2 0} #ES'
which 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., In E S*, Vn 1
Safe Bayesian optimization as Transductive Active Learning In the agnostic setting from Section 3.2, GPs f and 9 can be used well-calibrated models of the ground truths I' and g*, and we denote lower- and upper-confidence bounds by 1 ) 18 (x) and ur, (x),, ug (æ)), respectively. These confidence bounds induce a pessimistic safe set Sn def {ar 1g. (ax) 2 () and optimistic safe set S., = {æ (x) 2 }} which satisfy Sn S C S, with high probability at all times. Similarly, the set of potential maximizers
An def fx E S. un (2x) 2 max (x()) x e'ES,
contains the solution to Equation (4) at all times with high probability.
The (simple) regret (S) def max (xxx) (((z))(((00)) (*,,, with T, def arg max wES, (xx) measures the worst-case performance of decision rule. To achieve small regret, one faces an exploration- expansion dilemma wherein one needs to explore points that are known-to-be-safe, i.e. lie in the estimated safe set Sn, and might be optimal, while at the same time discovering new safe points by "ex- panding" S,- Accordingly, a natural choice for the target space of Safe BO is An, since it captures both exploration and expansion simultaneously." 7 To prevent constraint violation, the sample space is re- stricted to the pessimistic safe set Sn, In Safe BO, both the target space and sample space change with each round n., and we generalize our theoretical results from Section
Appendix C to this setting. Theorem 5.1 (Convergence to safe optimum). Pick any c > O, 5 E (0. 1). Assume that f*, g" lie in the reproducing kernel Hilbert space Hx(()) of the kernel k. and that the noise en is conditionally Sub-Gaussian. Then, we have with probability at least - 5,
Safety: for all 2 1,
E S*
Moreover, assume So & 0 and denote with R. the largest reachable safe set starting from So- Then, the convergence of reducible uncertainty implies that there exists n >> 0 such that with probability least 8. 6.
Optimality: for all n n", (R) S.
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, can be inferred efficiently. In Section 3, we outline settings where the reducible uncertainty converges which 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 similar to those of other Safe BO algorithms (Berkenkamp et al., 2021) but require fewer assumptions and generalize 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.
7 An alternative possibility is to weigh each point in A., according to how likely it is to be the safe optimum. Which approach performs better desk-dependent, and we include detailed discussion in Appendix K.I.
8

---

ITL.
ISE
ORACLE SAFEOPT
VIL
SAFEOPT
HEURISTIC SAFEOPT
1d Task
2d Task
Quadcopter Controller Tuning
10.0
0.4
7.5
1.0
Regret
5.0
0.2
0.5
2.5
0.0
0
Number of Iterations 1000
Number of Iterations 100
Number of Iterations 50
Figure 5: 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.
5.1 Experiments Safe Bayesian Optimization
We evaluate two synthetic experiments for a 1d and 2d parameter space, respectively (cf. Ap- pendix 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 quadcopter We consider quadcopter with unknown dynamics; 81+1 = (s; Uz) where u, E Rd. is the control signal and 8; E Rd. is the state at time t. The inputs u, are calculated through a deterministic function of the state π S + U which we call the policy. The policy is parameterized via parameters x E X, e.g., PID controller gains, such that u, (s,). The goal is to find the optimal parameters with respect an unknown objective f* while satisfying some unknown constraint(s) g (xx 2 0, e.g., the quadcopter does not fall on the ground. This typical Safe BO problem which widely applied for safe controller learning in robotics (Berkenkamp et al., 2021; Baumann et al., 2021; Widmer et al., 2023).
Results We compare ITL. and VTL to SAFEOPT (Berkenkamp et al., 2021), which is undirected, ie., 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 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 on par with the state-of-the-an We attribute this to its directed exploration and less conservative expansion over S SAFEOPT (cf. Id 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 entropy), which 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 EIC (Gardner et al., 2014) lead constraint violation (cf. Appendix K.4.2).
We provide
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 overparameterizzed models. Substantial work on active learning has studied entropy-based criteria in parameter-space most notably BALD (MacKay, 1992; Houlshy et al., 2011; Gal et al., 2017; Kirsch et al., 2019), which selects Zin arg x T(0; V/ 1D-1)), where 0 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] 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,
nn aar max #ES
V(aaaVi Dn--1),
(MM-ITI)
Z'EAA
for which we derive analogous versions of Theorems 3.2 and 3.3 in Appendix D.3. We note that similarly to VTL, MM-ITL disregards the mutual dependence of points in the target space A and differs from VTL only in a different weighting of the posterior marginal variances of the prediction targets (ef. Appendix D.3). Recently. Bickford Smith et al. (2023) generalized MM-ITL by treating the prediction target as a random variable, and Kothawade et al. (2021) and Bickford Smith et al. (2024) demonstrated the use of output-space decision rules for image classification tasks in a pre-training context.
Influence functions measure the change in a model's '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- gess-gradient embedding space. We show in our ex- periments that transductive active learning can substantially outperform COSINESIMILARIS tribute 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).
We at-
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 al., 2009). Entropy search methods (Hennig & Schuler, 2012; Hernández-Lobat et al., 2014) are widely used and select 2n, = arg = I(x"; : y 1n in input-space where x. arg max fa. Similarly to ITL. output-space entropy search methods (Hoffman & Ghahramani, 2015; Wang & Jegelka, 2017), which select 2x, = arg = Iff"; y/ 1D= with f max, fn are more computationally tractable. In fact, output-space entropy search is a special case of ITL with a stochastic target space (cf. Equa- tion (47) in Appendix K. Bogunovic et al. (2016) analyze TRUVAR in the context of Bayesian optimization and level set estimation. TRUVAR is akin to VTI. with similar notion of "target space", but their algorithm and analysis rely on a threshold scheme which requires that A C S. Fiez et al. (2019) introduce the transductive linear bandit problem, which is special case of transductive active learning limited to linear function class and with the objective of determining the maximum within an initial candidate set. We mention additional more loosely related works in Appendix A.
7 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 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 tfate-of-the-ar
'The transductive bandit problem can be solved analogously to Safe BO. by maintaining the set An.
10

---

Acknowledgements
Many thanks Armin Lederer, Johannes Kirschner, Jonas Rothfuss, Lars Lorch, Manish Prajapat, Nicolas Emmenegger, Parnian Kassraie, and Scott Sussex for their insightful feedback on different versions of this manuseript, as well as Anton Baumann for helpful discussions. We further thank Freddie Bickford Smith for constructive discussion regarding the relationship between our work and prior work.
This project was supported in part by the European Research Council (ERC) under the European Union's 's Horizon 2020 research and Innovation Program Grant agreement no. 815943, the Swiss National Science Foundation under NCCR Automation, grant agreement 5INF40 180545, and by grant of the Hasler foundation (grant no. 21039).
References
Abbasi-Yadkori, Y. Online learning for linearty parametrized control problems. PhD thesis, Univer- sity of Alberta, 2013.
Antorán, J., Janz, D., Allingham, J. U., Daxberger, E., Barbano, R. R., Nalisnick, E., and Hernández- Lobato, J. M. Adapting the linearised laplace model evidence for modern deep learning. In ICMI,, 2022.
Arora, S., Du, S., Hu, W., Li, Z., Salakhutdinov, R. R., and Wang, R. exact computation with an infinitely wide neural net. NeurIPS, 32, 2019.
Arthur, D., Vassilvitskii, S., et al. k-means++: The advantages of careful seeding. In SODA, volume 2007.
Ash, J., Goel, S., Krishnamurthy, A., and Kakade, S. Gone fishing: Neural active learning with fisher embeddings. NeurlPS, 34, 2021.
Ash, J. T., Zhang, C., Krishnamurthy, A., Langford, J., and Agarwal, A. Deep batch active learning by diverse, uncertain gradient lower bounds. ICLR, 2020.
Audibert, J.-Y., Bubeck, S., and Munos, R. Best arm identification in multi-armed bandits. In COLT, 2010.
Balestriero, R., Ibrahim, M., Sobal, V., Morcos, A., Shekhar, S., Goldstein, T., Bordes, F., Bardes, A. Mialon, G., Tian, Y., et al. A cookbook of self-supervised learning. arXiv preprint arXiv:2304.122100 2023.
Barrett, A. B. Exploration synergistic and redundant information sharing in static and dynamical gaussian systems. Physical Review E, (1),), 2015.
Baumann, D., Marco, A., Turchetta, M., and Trimpe, S. Gosafe: Globally optimal safe robot learning. In ICRA, 2021.
Bengio, Y., Louradour, J., Collobert, R., and Weston, J. Curriculum learning. In ICML, volume 26, 2009.
Beraha, M., Metelli, A. M., Papini, M., Tirinzoni, A., and Restelli, M. Feature selection via mutual information: New theoretical insights. In IJCNN, 2019.
Berkenkamp. F., Schoellig, A. P., and Krause, A. Safe controller optimization for quadrotors with gaussian processes. In ICRA, 2016.
Berkenkamp, F., Krause, A., and Schoellig, A. Bayesian optimization with safety constraints: safe and automatic parameter tuning in robotics. Machine Learning, 2021.
Berlind, C. and Umner, R. Active nearest neighbors in changing environments. In /CML, 2015.
Bickford Smith, F., Kirsch, A., Farquhar, S., Gal, Y., Foster, A., and Rainforth, Prediction-oriented bayesian active learning. In AISTATS, 2023.

---

Bickford Smith, F., Foster, A., and Rainforth, T. Making better use of unlabelled data in bayesian active learning. In AISTATS, 2024.
Blundell, C., Cornebise, J., Kavukeuoglu, K., and Wierstra, D. Weight uncertainty in neural network. In ICML, 2015.
Bogunovic, I. Scarlett, J., Krause, A., and Cevher, V. Truncated variance reduction: A unified approach to bayesian optimization and level-set estimation. NeurIPS, 29, 2016.
Bottero, A., Luis, C., Vinogradska, J., Berkenkamp, F., and Peters, J. R. Information -hheorettcc safe exploration with gaussian processes. NeurIPS, 35, 2022.
Bottero, A. G., Luis, C. E., Vinogradska, J., Berkenkamp. F., and Peters, J. cntemaatioo-thhorette safe bayesian optimization. arXiv preprint arXiv:2402.15347, 2024.
Bubeck, S.. Munos, R., and Stoltz, G. Pure exploration in multi-armed bandits problems. In ALT, volume 20, 2009.
Chaloner, K. and Verdinelli, I. Bayesian experimental design: A review. Statistical Science, 1995.
Chandra, B. Quadrotor simulation, 2023. URL Quadrotor Simulation.
Chen, Y. and Krause, A. Near-optimal batch mode active learning and adaptive submodular optimiza- tion. In ICML, 2013.
Chowdhury, S. R. and Gopalan, A. On kernelized multi-armed bandits. ICML, 2017.
Cohn, D. Neural network exploration using optimal experiment design. NeurIPS, 6, 1993.
Coleman, C., Chou, E., Samuel, J., Culatana, S., Bailis, P., Berg, A. C., Nowak, R., Sumbaly, R., Zaharia, M., and Yalniz, I. Z. Similarity search for efficient active learning and search of rare concepts. In AAAI, volume 36, 2022.
Cook, R. D. Detection of influential observation in linear regression. Technometrics, 19(1), 1977.
Cooper, S. E. and Netoff, T. I. Multidimensional bayesian estimation for deep brain stimulation using the safcopt algorithm. medRxiv, 2022.
Cover, T. M. Elements of information theory. John Wiley Sons, 1999.
Das, A. and Kempe, D. Algorithms for subset selection in linear regression. In STOC, volume 40, 2008.
Das, A. and Kempe, D. Approximate submodularity and its applications: Subset selection, sparse approximation and dictionary selection. JMLR, 19(1), 2018
Daxberger, E., Kristiadi, A., Immer, A., Eschenhagen, R., Bauer, M., and Hennig, Laplace redux-effortless bayesian deep learning. NeurIPS, 34, 2021.
Deng, J., Dong, W., Socher, R., Li. L.-J., Li, K., and Fei-Fei, L. Imagenet: A large-scale hierarchical image database. In CVPR, 2009.
Devlin, J., Chang, M.-W., Lee, K., and Toutanova, K. BERT: Pre-training of deep bidirectional transformers for language understanding. In NAACL, 2019.
Emmenegger, N.. Mutný, M., and Krause, A. Likelihood ratio confidence sets for sequential decision making. NeurlPS, 37, 2023.
Esfandiari, H., Karbasi, A., and Mirrokni, V. Adaptivity in adaptive submodularity. In COLT, 2021.
Eustratiadis, P., Dudziak, E.,, Li, D., and Hospedales, T. Neural fine-tuning search for few-shot learning. ICLR, 2024.
Fiez, T., Jain, I.,, Jamieson, K. G., and Ratliff, I.. Sequential experimental design for transductive linear bandits. NeurIPS, 32, 2019.
12

---

Fu, B.. Cao, Z., Wang, J., and Long, M. Transferable query selection for active domain adaptation. In CVPR, 2021.
Gal, Y., Islam, R., and Ghahramani, Z. Deep bayesian active learning with image data. In ICML, 2017.
Gao, M., Zhang, Z., Yu, G., Arık, S. Ô., Davis, L. S., and Pfister, Consistency-based semi- supervised active learning: Towards minimizing labeling cost. In ECCV, 2020.
Gardner, J. R., Kusner, M. J., Xu, Z. E., Weinberger, Q. and Cunningham, P. Bayesian optimization with inequality constraints. In ICML, volume 2014, 2014.
Geifman, Y. and El-Yaniv, R. Deep active learning over the long tail. arXiv preprint 11X 2017.
Grandvalet, Y. and Bengio, Y. Semi-supervised learning by entropy minimization. NeurIPS, 17, 2004.
Graves, A., Bellemare, M. G., Menick, J., Munos, R., and Kavukcuoglu, K. Automated curriculum learning for neural networks. ICML, 2017.
Graybill, F. A. An introduction to linear statistical models. Literary Licensing, LLC, 1961.
Guo, Y. and Greiner, R. Optimistic active-learning using mutual information. In IJCAI, volume 7, 2007.
Hacohen, G., Dekel, A., and Weinshall, D. Active learning on budget: Opposite strategies suit high and low budgets. ICML, 2022.
Hardt, M. and Sun, Y. Test-time training on nearest neighbors for large language models. ICLR, 2024.
He, B., Lakshminarayanan, B., and Teh, Y. W. Bayesian deep ensembles via the neural tangent kernel. NeurlPS, 33, 2020.
Hendrycks, D. and Gimpel, K. A baseline for detecting misclassified and out-of-distribution examples in neural networks. ICLR, 2017.
Hennig, P. and Schuler, C. Entropy search for information-effccient global optimization. JMLR, 13 (6), 2012.
Hernández-Lobato, J. M., Hoffman, M. W., and Ghahramani, Z. Predictive entropy search for efficient global optimization of black-box functions. NeurIPS, 27, 2014.
Hoffman, M. W. and Ghahramani, Z. Output-space predictive entropy search for flexible global optimization. In NeurIPS workshop Bayesian Optimization, 2015.
Holzmüller, D., Zaverkin, V., Kästner, J., and Steinwart, I. framework and benchmark for deep batch active learning for regression. JMLR, 24(164), 2023.
Hopfield, J. Neural networks and physical systems with emergent collective computational abilities. Proceedings of the national academy of sciences, 79(8), 1982.
Houlsby, N., Huszár, F., Ghahramani, Z., and Lengyel, M. Bayesian active learning for classification and preference learning. CoRR, 2011.
Hübotter. J., Sukhija, B., Treven, L., As, Y., and Krause, A. Active few-shot fine-tuning. ICLR workshop on Bridging the Gap Between Practice and Theory Deep Learning. 2024.
Ilyas, A., Park, S. M., Engstrom, L.,, Leclerc, G., and Madry, A. Datamodels: Predicting predictions from training data. arXiv preprint arXiv:2202.0062. 2022.
Jacot, A., Gabriel, F., and Hongler, C. Neural tangent kernel: Convergence and generalization in neural networks. NewrIPS, 31, 2018
13

---

Johnson, J., Douze, M., and Jégou, H. sclle similarity search with gpus. IEEE Transactions on Big Data, 7(3), 2019.
Kaddour, J., Sæmundsson, S., et al. Probabilistic active meta-learning. NeurlPS, 33, 2020.
Kassraie, P. and Krause, A. Neural contextual bandits without regret. In AISTATS, 2022.
Khan, M. E. E., Immer, A., Abedi, E.,, and Korzepa, M. Approximate inference turns deep networks into gaussian processes, NeurIPS, 32, 2019.
Khanna, R., Elenberg, E., Dimakis, A., Negahban, S., and Ghosh, J. Scalable greedy feature selection via weak submodularity. In AISTATS, 2017.
Kingma, D. and Ba, J. Adam: A method for stochastic optimization. In ICLR, 2014.
Kirsch, A. Blxck-box batch active learning for regression. arXiv preprint arXiv:2302.0898/ 2023. 2023.
Kirsch, A., Van Amersfoort, J., and Gal, Y. Batchbald: Efficient and diverse batch acquisition for deep bayesian active learning. NeurIPS, 32, 2019.
Kirschner, J., Mutny, M., Hiller, N., Ischebeck, R., and Krause, A. Adaptive and safe bayesian optimization in high dimensions via mnediimesiionll subspaces. In ICML, 2019.
Koh, P. W. and Liang, Understanding black-box predictions via influence functions. In JCML, 2017.
Kothawade, S., Beck, N., Killamsetty, K., and Iyer, R. Similar: Submodular information measures based active learning in realistic scenarios. NeurlPS, 34, 2021.
Krause, A. and Golovin, D. Submodular function maximization. Tractability, 3, 2014.
Krause, A. and Guestrin, C. Nonmyopic active learning of gaussian processes: an exploration- exploitation approach. In JCML, volume 24, 2007.
Krause, A., Singh, A., and Guestrin, C. Near-optimal sensor placements in gaussian processes:
Theory, efficient algorithms and empirical studies. JMLR, 9(2), 2008
Krizhevsky, A., Hinton, G., et Learning multiple layers features from tiny images. Technical report, University of Toronto, 2009.
Kumari, L., Wang, S., Das, A., Zhou, T., and Bilmes, J. An end-to-end submodular framework for data-efficient in-context learning. In NAACL, 2024.
Lakshminarayanan, B., Pritzel, A., and Blundell, C. Simple and scalable predictive uncertainty estimation using deep ensembles. NeurlPS, 30, 2017.
LeCun, Y., Cortes, C., and Burges, C. J. The mnist database of handwritten digits. http://yann.lecum wtt..e/ww...oo//////iis..tt 1998.
Lee, J.. Bahri, Y., Novak, R., Schoenholz, S., Pennington, and Sohl-Dickstein, Deep neural networks as gaussian processes. ICIR, 2018.
Lee, J., Xiao, L., Schoenholz, S., Bahri, Y., Novak, R., Sohl-Dickstein J., and Pennington, J. Wide neural networks of any depth evolve as linear models under gradient descent. NeurIPS, 32, 2019.
Lee, Y., Chen, A. S., Tajwar, F., Kumar, A., Yao, H., Liang, P., and Finn, C. Surgical fine-tuning improves adaptation distribution shifts. NeurlPS workshop on Distribution Shifts, 2022.
Lewis, D. and Gale, W. A sequential algorithm for training text classifiers. In SIGIR, 1994.
Lewis, D. D. and Catlett, J. Heterogeneous uncertainty sampling for supervised learning. In Machine learning proceedings. 1994.
MacKay, Information-batt objective functions for active data selection. Neural computation, 4(4). 1992.
14

---

Maddox, W. J., Izmailov, P., Garipov, T., Vetrov, D. P., and Wilson, A. G. A simple baseline for bayesian uncertainty in deep learning. NeurIPS, 32, 2019.
Malladi, S., Wettig, A., Yu, D., Chen, D., and Arora, A kernel-based view of language model fine-tuning, In ICML, 2023.
Martens, J. and Grosse, R. Optimizing neural networks with kronecker-factored approximate curvature. In ICML, 2015.
Mehta, R., Shui, C., Nichyporuk, B., and Arbel, T. Information gain sampling for active learning in medical image classification. In UNSURE, 2022.
Murphy, K. Probabilistic machine learning: Advanced topics. MIT Press, 2023.
Mutny, M. and Krause, A. Experimental design for linear functionals reproducing kernel hilbert spaces. NeurlPS, 35, 2022.
Nemhauser, G. L., Wolsey, L. A., and Fisher, M. L. An analysis of approximations for maximizing submodular set functions-i. Mathematical programming, 14, 1978.
Ostrovsky, R., Rabani, Y., Schulman, I. and Swamy, C. The effectiveness of lloyd-type methods for the k-means problem. JACM, 2013.
Pacchiano, A., Lee, J. N., and Brunskill, Experiment planning with function approximation. NeurIPS, 37, 2024.
Peng, H., Long, F., and Ding, C. Feature selection based on mutual information criteria of max- dependency, max-relevance, and min-redundancy. IEEE Transactions on pattern analysis and machine intelligence, 27(8), 2005.
Prabhu, V., Chandrasekaran, A., Saenko, K., and Hoffman, J. Active domain adaptation via clustering uncertainty-weightedd embeddings. In ICCV, 2021.
Pruthi, G., Liu, F., Kale, S., and Sundararajan, M. Estimating training data influence by tracing gradient descent. In NeurlPS, 2019.
Rahimi, A. and Recht, B. Random features for large-scale kernel machines. NeurlPS, 20, 2007.
Rai, P., Saha, A., Daumé III, H., and Venkatasubramanian, S. Domain adaptation meets active learning. NAACL HLT workshop on Active Learning for Natural Language Processing, 2010.
Rothfuss, J., Koenig, C., Rupenyan, A., and Krause, Meta-learning priors for safe bayesian optimization. In COLT, 2023.
Russo, J. Van Roy, B., Kazerouni, A., Osband, I., Wen, Z., al. A tutorial on thompson sampling. Foundations and Trends@ in Machine Learning, 11(1), 2018.
Saha, A., Rai, P., Daumé, H., Nenkatasubrammanian S., and DuVall, S. I.. Active supervised domain adaptation. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD, 2011.
Scheffer, T., Decomain, C., and Wrobel, S. Active hidden markov models for information extraction. In IDA, 2001.
Schreiter, J., Nguyen-Tuone D., Eberts, M., Bischoff, B., Markert, H., and Toussaint, M. Safe exploration for active learning with gaussian processes. In ECML PKDD, 2015.
Sener, O. and Savarese, S. Active learning for convolutional neural networks: A core-set approach. ICLR, 2017.
Sco, S., Wallat, M., Graepel, T., and Obermayer, K. Gaussian process regression: Active data selection and test point rejection. Mustererkemnung 2000. Springer, 2000.
Settles, Active learning literature survey. Technical report, University of Misconsin-Madisee Department of Computer Sciences, 2009.
15

---

Settles, B. and Craven, M. An analysis of active learning strategies for sequence labeling tasks. In EMNLP, 2008.
Shoham, N. and Avron, H. Experimental design for overparameterized learning with application to single shot deep active learning. IEEE Transactions Pullern Analysis and Machine Intelligence, 2023.
Shwartz-Ziv, R. and LeCun, Y. To compress or not to compress compress-self--uuerviid learning and information theory: A review. arXiv preprint arXiv:2304.09333 09355, 2023.
Soviany, P., lonescu, R. T., Rota, P., and Sebe, N. Curriculum learning: A survey. ICV, 2022.
Srinivas, N., Krause, A., Kakade, S. M., and Seeger, M. Gaussian process optimization in the bandit setting: No regret and experimental design. In ICML, volume 27, 2009.
Strang, G. Introduction to linear algebra. SIAM, 5 edition, 2016.
Su, J.-C., Tsai, Y.-H., Sohn, K., Liu, B., Maji, S., and Chandraker, M. Active adversarial domain adaptation. In
Sui, Y., Gotovos, A., Burdick, J., and Krause, A. Safe exploration for optimization with gaussian processes. In ICML, 2015.
Sukhija, B., Turchetta, M., Lindner, D., Krause, A., Trimpe, S., and Baumann, D. Gosafeopt: Scalable safe exploration for global optimization of dynamical systems. Artificial Intelligence, 2023.
Tamkin, A., Nguyen, D., Deshpande, S., Mu, J., and Goodman, N. Active learning helps pretrained models learn the intended task. NeurIPS, 35, 2022.
Tan, M. and Le, Q. Efficientnet: Rethinking model scaling for convolutional neural networks. In ICML, 2019.
Thompson, W. R. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 1933.
Tu, S., Frostig, R., Singh, S., and Sindhwani, V. JAX: A python library for differentiable optimal control on accelerators, 2023. URL http:// thubb....t.t...
thub. "goooollerraa
Turchetta, M., Berkenkamp, F., and Krause, A. Safe exploration for interactive machine learning. NeurlPS, 32, 2019.
Vakili, S., Khezeli, K., and Picheny, V. On information gain and regret bounds in gaussian process bandits. In AISTATS, 2021.
Vapnik, V. Estimation of dependences based on empirical data. Springer Science & Business Media, 1982.
Vergara, R. and Estévez, A. review of feature selection methods based on mutual information. Neural computing and upplicutions, 24, 2014.
Vinyals, O., Blundell, C., Lillicrap. T., Wierstra, D., al. Matching networks for one shot learning. NeurtPS, 29, 2016.
Wainwright, M. J. High- statistics: A non-asymptotic viewpoint, volume 48. Cambridge university press, 2019.
Wang, C., Sun, S., and Grosse, R. Beyond marginal uncertainty: How accurately can bayesian regression models estimate posterior predictive correlations? In AISTATS, 2021.
Wang, Z. and Jegelka, S. Max-value entropy search for efficient bayesian optimization. In ICML,, 2017.
Wei, A., Hu, W., and Steinhardt, More than a toy: Random matrix models predict how real-world neural representations generalize. In ICML, 2022.
16

---

Widmer, D., Kang, D., Sukhija, B.. Hübotter, J., Krause, A., and Coros, S. Tuning legged locomotion controllers via safe bayesian optimization. CORL. 2023.
Wilks, S. S. Certain generalizations the analysis of variance. Biometrika, 1932.
Williams, K. and Rasmussen, C. E. Gaussian processes for machine learning, volume 2. MIT press Cambridge, MA, 2006.
Wischnewski, A., Betz, J., and Lohmann, B. A model-free algorithm safely approach the handling limit of an autonomous racecar. In ICCVE, 2019.
Xia, M., Malladi, S., Gururangan, S., Arora, S., and Chen, D. Less: Selecting influential data for targeted instruction tuning. In ICML, 2024.
Xu, M. and Kazantsev, G. Understanding goal-oriented active learning via influence functions. In NeurIPS Workshop Machine Learning with Guarantees, 2019.
Ye, J., Wu, Z., Feng, J., Yu, T., and Kong, L. Compositional exemplars for in-context learning. In ICML. 2023.
Yehuda, O., Dekel, A., Hacohen, G., and Weinshall, D. Active learning through a covering lens. NeurlPS, 35, 2022.
Yu, H. and Kim, Passive sampling for regression. In ICDM, 2010.
Yu, K., Bi, J., and Tresp, V. Active learning via transductive experimental design. In ICML, volume 23, 2006.
Zanette, A., Dong, K., Lee, J. N., and Brunskill, E. Design of experiments for stochastic contextual linear bandits. NeurIPS, 34, 2021.
Zheng, H., Liu, R., Lai, F,, and Prakash, A. Coverage-centric coreset selection for high pruning rates. ICLR, 2023.
17

---

Appendices
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 complex world":
When solving problem of interest, do not solve more general problem as an intermediate step. Try get the answer that you really need but not more general one.
Vapnik (1982)
These appendices provide additional background, proofs, experiment details, and ablation studies.
Contents
A Additional Related Work
20
B Background
20
B.1 Information Theory
20
B.2 Gaussian Processes
20
C Proofs
C.1 Undirected Case of ITL.
21
C.2 Non-adaptive Data Selection & Submodularity
C33 Batch Diversity: Batch Selection as Non-adaptive Data Selection
22
C.4 Measures of Synergies & Approximate Submodularity
23
C.5 Convergence of Marginal Gain
25
C.6 Proof of Theorem 3.2
26
C.7 Proof of Theorem
C.8 Proof of Theorem 5.1
32
C.9 Useful Facts and Inequalities
36
D Interpretations & Approximations of Principle (f)
37
D.I Interpretations of ITL.
37
D.2 Interpretations of VTI.
37
D.3 Mean Marginal ITL
38
D.4 Correlation-base Transductive Learning.
40
D.5 Summary
40
E Stochastic Target Spaces
41
F Closed-form Decision Rules
41
G Computational Complexity
42
H Additional GP Experiments & Details
42
18

---

I Alternative Settings for Active Line-Tuning
43
1.1 Prediction Targets Contained in Sample Space: A 1
43
1.2 Active Domain Adaptation
44
J Additional NN Experiments & Details
44
J.1
Experiment Details
45
J.2
Embeddings and Kernels
46
J.3
Towards Uncertainty Quantification in Latent Space
47
J.4
Batch Selection via Conditional Embeddings
47
J.5
Baselines
J.6
Additional experiments
52
J.7
Ablation study of noise standard deviation
52
Additional Safe BO Experiments Details
54
K.1 A More Exploitative Stochastic Target Space
54
K.2 Detailed Comparison with Prior Works
55
K.3
Jumping Past Local Barriers
60
K.4 Experiment Details
19

---

A Additional Related Work
The general principle of non-active "transductive learning" was introduced by Vapnik (1982). The no- tion of "target" from transductive active learning is akin to the notion of "task" in curriculum learning (Bengio et al., 2009; Graves al., 2017; Soviany et al., 2022). The study of settings where the irre- ducible 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 co-beepredicted label is standard approach (Peng et al., 2005; Vergara & Estévez, 2014; Beraha et al., 2019) which is akin ITL (ef. Appendix D). The themes 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 method- ologies, 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).
B
Background
B.1 Information Theory
Throughout this work, log denotes the natural logarithm. Given random vectors x: and y, we denote by
H[æ]] def
Ep(m)] log p(x)),
H[ >
y) def
En(m.y) - log p(æ 1y),
and
[(:; y) def H[æ]] H| y)
the (differential) entropy, conditional entropy, and information gain, respectively (Cover, 1999).
The multivariate information gain (Murphy, 2023) between random vectors æ, y, is given by
def I(x: y) 1(x; y x) I(x; y)
(6)
I(x; + I(x; - I(
(7)
When 1(x; z) * O it is said that y and z interact regarding their information about æ. If the interaction is positive, is said that the information of about æ is redundant given y. Conversely, if the interaction is negative, it is said that the information of z about æ is synergistic with y. The notion of synergy is akin to the frequentist notion of "suppressor variables" in linear regression (Das & Kempe, 2008).
B.2 Gaussian Processes
The stochastic process f is Gaussian process (GP, Williams & Rasmussen (2006)), denoted f ~ (P( k). with mean function and kernel l if for any finite subset X = (.I...., 2n C X, fx NNxx (xxxXxx))
jointly Gaussian with mean vector Mx (i) p(x,) and covariance matrix Kxx(i.)) k();
In the following, formalize the assumptions from the GP setting (cf. Section 3.1).
Assumption B.1 (Gaussian prior). We assume that f ~ (P k) with known mean function μ and kernel
Assumption B.2 (Gaussian noise). We assume that the noise eæ is mutually independent and zero-mean Gaussian with known variance p²(x) > 0. We write Px = diag (xia)?" ((21))...,,p((a. (xx.).
Under Assumptions B.1 and B.2, the posterior distribution of f after observing points X is G'P(nn, ky)) with
Mn,(x) p(x) + Knx (Kxx Px) -ux), ki (xc x²) k( x.) - Knx(Xxx + Px)
'xx'' -x)--Kxxx
o (x) (x x).
'One has to be careful to ensure that 1(x; y) exists, ie.. [I y))l < cc. We will assume that this is the case throughout this work. When and y are jointly Gaussian, this is satisfied when the noise variance p² is positive.
20

---

For Gaussian random vectors f and y, the entropy is H log(2rt) + 1/2 log |Var the
information gain is y(f:y) / (log |aarly] - log Var fl],, and
1
7n
max log I Px Kxxl XCX 2
XX
C Proofs
We will write
o² der
max oz) and
x2 def
max (x) + (x))
The following is a brief overview of the structure of this section:
Appendix C.1 relates ITL. the inductive learning setting (S S A) to prior work.
2. Appendix C.2 relates the designs selected by ITL and VTL to the optimal designs for corresponding non-adaptive objectives.
3. Appendix C.3 shows that batch selection via ITL or VTL leads to informative and diverse batches, utilizing the results from Appendix C.2.
4. Appendix C.4 introduces measures of synergies that generalize the submodularity assump- tion (cf. Assumption 3.1).
5. Appendix C.5 proves key results on the convergence of the ITL and VTL objectives.
6. Appendix C.6 proves Theorem 3.2 (convergence GP setting).
7. Appendix C.7 proves Theorem 3.3 (convergence in agnostic setting).
8. Appendix C.8 proves Theorem 5.1 (convergence in safe BO application).
9. Appendix C.9 includes useful facts.
C.1 Undirected Case of ITL
We briefly examine the important special case of ITL where S C A. In this setting, for all x E S, the decision rule of ITL simplifies to
(4) I(fAl Va (a,
IffAil= Vm D.)
I(fai Uu D..)
((6)
I(fei (D.))
H( ]D,]-H(s. H(ca)
where (z) follows from the chain rule of information gain and æ E S C A; and (ii) follows from the conditional independence fA I V/ fa-
additionally is a GP then
Varifa Dnl
H[ya
Dx] - H(exl
log 1
2
Varlsæ]
This decision rule has also been termed total information gain (MacKay, 1992). When S Ç and observation noise is homoscedastic, this decision rule is equivalent to uncertainty sampling.
C.2 Non-adaptive Data Selection Submodularity
Recall the non-myopic information gain ( 1(fa: (ITL) and variance reduction (x((X== Var[fa]
Var yxl (VTL) objective functions from Assumption 3.1. In this section, we will relate the designs selected by ITL. and VTL to the optimal designs for these objectives. To this end, consider the non-adaptive optimization problem
X arg max &/ (XX..
XCS
21

---

Lemma C.1. For both ITL and VTL, A is non-negarie non-negative and monotone.
Proof. For ITL, (Xx) 2 follows from the non-negativity of mutual information. To conclude monotonicity, note that for any X' S X S.
Ux) = H[fal - HIfA yx & H[fal - H[fa yxl = Mx)
due to monotonicity of conditional entropy (which is also called the "information never hurts" principle).
For VTL, recall that tr Var[fA yx] S ir Var[fa yx, for any X' " S (with an implicit ex-
pectation over Vx Ux.). Non-negativity and monotonicity of th then follow analogously to ITL. O
Lemma C.2. The marginal gain (x X) def U (X) x E S given X C S is
the ITL and VTL objective, respectively.
Proof. For ITL.
A X) = 1(fai 3x V2) - 1(fai 8x)
H[ff yx] H[ff 3lx Mae
= I(fai Vnn yx)
which is precisely the ITL objective.
For VTL,
A X) = ir Var[fa yx] - tr Var 3/x Vmr]
tr Varlfa Fxx Vz) + const
which is precisely the VTI objective.
Definition C.3 (Submodularity). A is submodular if and only if for all æ E S and X' C X C S,
A X') 2 A X).
Theorem C.4 (Nemhauser et (1978)). Let Assumption 3.1 hold. For any n 2 if ITL VTL selected Vi respectively, then
( 2 (1 - 1/ee) max (X().
XCS |
Proof. This is a special case of canonical result from non-negative monotone submodular function maximization (Nemhauser al., 1978; Krause Golovin, 2014).
C.3
Batch Diversity: Batch Selection as Non-adaptive Data Selection
Recall the non-adaptive optimization problem
Bn,k = arg max I(fai
V/ U/
Dnn-1)
BCS =
from Equation (3) with batch size l: >> O, and denote by B = 2r, 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
(x
B) = I[fA Mrs Dn-1) - I(fa: (Dn-1)
H ff D
Dn Mnl
H[ff Dn Vn. Var
= 1(ff: Va
D DD
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', is also competitive with fully sequential "batchless" decision rule (Chen & Krause, 2013; Esfandiari et al., 2021).
22

---

C.4 Measures of Synergies & Approximate Submodularity
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 Tis-
Example C.5. Consider the example where is stochastic process of three random variables X, Y. where X and Y are Bernoulli (p = 2),, and is the XOR of and Y. Suppose that observations exact (i.e., En 0), that the target space A comprises the output variable Z while the sample space & comprises the input variables X and Y. Observing any single X or Y yields however, observing both inputs jointly perfectly
no information about Z: 1(2; X) 1(2; Y) determines Z: (2;X,Y) = 1. Thus, ()) = if ni 2 2 and 7n (): = 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 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 7n (.A; S) since measures only the joint information gain of samples within S. Instead, the prevalence of synergies is captured by the sequence r, max A Ø1mn), which measures the maximum information gain of yn+1. If r > - at any round n, this indicates synergy. The following key object measures the additional complexity due to synergies.
Definition C.6 (Task complexity). For 1, assuming r; > 0 for all S i S define the task complexity as
(n)((n) def
r Tn-1 T
max iE(0....n-11
Note that a,,s (n1 is large only if the information gain of yn larger than that of previous observation 3/s Intuitively, if A, (n) is large, the agent had to discover the implicit intermediate observations V1..... Un-1 that lead downstream synergies. We will subsequently formalize the intimate connections of the task complexity to synergies and submodularity. Note that in the GP setting, (n) can be computed online by keeping track of the smallest r, during previous rounds i. Further, note that (n) < if v/.4 is submodular.
C.4.1 The Information Ratio
Another object will prove useful in our analysis of synergies.
Consider an alternative multiplicative interpretation of the multivariate information gain (cf. Equa- tion (7)), which we call the information ratio of X S given D S, | |D| oo:
D) def ExEx A D) Ax(X D)
R(X
[0,
(8)
Observe that R(X D) measures the synergy properties of yx with respect fA given yp multiplicative sense. That is, if R(X D) > then information in yx is redundant, whereas if #(X D) < then information yx synergistic, and if x(X D) = then yx not mutually interact with respect to fA (all given Уp). In the degenerate case where (x D) 0 (which implies Emex ( D) = 0) we therefore let R(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 S, < cc. If fA and yXuD are jointly Gaussian then R(X D) > 0.
Proof. W.L.o.g. assume D 0. We let X (.i...... mg and prove lower and upper bound sep- arately. We assume w.l.o.g. that T(f4: 3x) > 0 which implies [ar[ff yx ]1 < [Var[fall- Thus, there exists some such that fa and Va, dependent, so |aarffa Va. Varr [fall which implies 1(fAi Vv.) > 0. We therefore conclude that R(X) > 0.
The following example shows that this lower bound is tight.
23

---

Example C.8 (Synergies of Gaussian random variables, inspired by Section 3 of Barrett (2015)).
Consider the three random variables X, Y. and (think A {X] and {Y, Z}) which are jointly Gaussian with mean vector 0 and covariance matrix
[
a
E = a 1 0
for 2a <
0 1
where the constraint on a to ensure that Σ is positive definite. Computing the mutual information, we have
1 I(X;Y) ZX log(1 a²)
and 2( = - log(1 - 2a²). Therefore,
I(X; Y) + I(X;
log(1 - 2n1² + a²))
1. log(1 2a²)
I(X;Y,2)
Note that
log(1 1 2a² + +a 2a²)
lim
0,
log(1
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 ITI.
In the inductive active learning problem considered in most prior works, where C A and f is Gaussian process, it holds for ITL that (n) since all learning targets appear explicitly in S: Lemma C.9. Let S S A. Then A. of ITL. is submodular.
Proof. Fix any E S and X' S X S S. Let X del X information gain, we have
X'.
By the definition of conditional
(a X) 1(yx: fA yx 1(yw: fA Fx 1xx) - 1(yar Mxx (xx).
Since for any æ E and X C S, y/ 1 Vx SA. this simplifies to
T(yn: fA yx ) = T(yan fa yx) - T(yn: Ux yx))
It then follows from [[ yx yx) 2 0 that
A X) Ty fA yx) T(ywi fA yxx) A x').
This implies that (n) < 1 for any and R(X D) 2 1 for any X, C S when S C A.
C.4.3 The Submodularity Ratio
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 (Submocularity ratio). The submodularity ratio of thA up cardinality n 2 is def min
(A(n)
R(X (XXD) D),
DC
XCS1XXSn
DnX=0
where they define 0 1. thA is said to be k-weakly submodular for some k > 0 if K kA(n) 2 k.
As special case of Theorem from Das & Kempe (2018), applying that via is non-negative and monotone, we obtain the following result.
Theorem C.11 (Das & Kempe (2018)). For any n. 2 if ITL VTI. selected $1.. respectively, then
(z im 2 - (1-e (m())))
max (X)).
XCS |
vbL4 submodular, is implied that (n) for all in which case Theorem C.11 recovers Theorem C.4.
24

---

C,5 Convergence of Marginal Gain
Our following analysis allows for changing target spaces A,, and sample spaces Sn (cf. Section 5), and to this end, we redefine r, maX AA,, (z Ø1m]. 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 (n) by On-
Theorem C.12 (Convergence of Marginal Gain for ITL). Assume that Assumptions B.I and B.2 are satisfied. Fix any integers 11 > My 2 0, A = 7g + such that for all i E (no...., n2 - 1}, A+t1 S AA and S del Si+1 Sp. Further, assume A co. Then, if the sequence {0++11 184+1/mn.
was generated by ITL.
7 A
F S a.
(10)
Moreover, nn =
TA) A
F S Onn
(11)
Proof. We have
Tm.
T
L=
max iff B1a))
EES
C'u
I[fA, Marc (i.)
A
I(fAmo ; :oo++ Di)
f=RO
I(fAmo ye4
Yonotie Dra))
(JAm.
ya 11m1 Droo)
A
max T(fAmo ; y0 Dins) XCS
X =
(ni)
O'n
max T(fxi 3x (Dna) XCS
=
(uit)
max I(fx:8x)
A
XCS
I
YA
ani A
where (i) follows from the definition of the task complexity On, (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 C A, 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 yx fAm, fx and the data processing inequality. The conditional independence follows from the assumption that the observation noise is independent. Similarly, yx .. Dno fx which implies (wii).
If no 0, then the bound before line (vi) simplifies any A AA)Aa.
25

---

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. and B.2 are satisfied. Then any n 2 if the sequence (Bi)== is generated by VTL,
20-an
Tn-1 S
Ma)),s())
(12)
æ'EA
We remark that Ex'Es (a'),s()) $ (Ahass(n).
Proof. We have
l
t=0
O
tr Varlfa ynol min tr Varlfa
Vi Uo]
Var ffa Djj Var(fa Dj-1]]
n
(184)
o an
n-1
Varifa' Dnx]
log
Varlfn' Da+1l
#' EA 1=0
20 202an an
n-1
Ifaa Van+i
Dr))
n
YEA
(in) 20
(fa' Vantt ylm...)
n1
æ'EA ==
(v) 20 On
Isfar Merro)
z'EA
20 2 an
max I(far: yx) XCS x
Σ
n
e'EA|xi=n
e'EAIXI
20 On
(n)
n
s'EA
where (i) follows from the definition of the task complexity an, (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; (iit) 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 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. (cf. Appendix C.5).
Keeping track of the task complexity online In general, the task complexity o,, may be larger than one the "directed" setting (i.e., when S g A). However, note that a, can easily be evaluated online by keeping track of the smallest I, during previous rounds
C.6 Proof of Theorem 3.2
We will now prove Theorem 3.2. We first prove the convergence of marginal variance within S for ITL, before proving the convergence outside $ in Appendix C.6.I.
26

---

Lemma C.14 (Uniform convergence of marginal variance within S for ITL). Assume that Assump- tions B.1 and B.2 are satisfied. For any 2 and æ E Ans.
(x) 20 Tn-
(13)
Proof. We have
(2) = Var[f
[r,] Var[Ja 1 Sax Drl
Var Uy
[n] (x)) (Varlyla
Sa, Dnl - (xx)
Varlye
Dn] Var fax Dnl
(10)
Var Dn1
S 0² log
Var 1/ee
fee Dnn)
25²
1(JaiVn (n,)
(10)
S 25 1(fai y Dn))
(10)
S 26t
max x'ES
I(fA: Va" (n,)
(0) 28 max TexxIffa [[fi Ua! Vim)
e'ES
= 25 In
where (i) follows from the noise assumption (cf. Assumption B.2); (ii) follows from Lemma C.38 and using monotonicity variance; (tii) follows from æ E AA and monotonicity information gain; (iv) follows from S; and (v) uses that the posterior variance of Gaussians is independent of the realization and only depends on the location of observations.
C.6.1 Convergence outside S for ITL
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 æ in S, and show (1) that the size of this Markov boundary independent of n, and (2) that small uncertainty reduction within the Markov boundary implies that the marginal variances at the Markov boundary and(!) x are small.
> 0, n 2 O, and æ E X, we denote by Definition C.15 (Approximate Markov boundary). For any (x)) the smallest (multi-)subsee of such that
Varifa Das (m)) S 1 (z) +
(14)
We call (a)) an 6-approximate Markov boundary of x in S.
Equation (14) is akin to the notion of the smallest Markov blanket in S of some æ E X (called a Markov boundary) which is the smallest set B C S such that fa 1. fs fg-
Lemma C.16 (Existence of an approximate Markov boundary). For any > 0, let k be the smallest integer satisfying
7he
Edmin (Kss)
(15)
k
2,5
Then, for any n and X, there exists an e-approximate Markov boundary (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) such that
[n)e S b
Vn 2 0, x X.
(16)
We defer the proof of Lemma C.16 to Appendix C.6.3 where we also provide an algorithm to compute B (x).
27

---

Lemma C.17. For any e > 0, n 2 0, and x E X.
(x) S 20² T(J:: (B) D.)) + (2) +
(17)
where (a) an e-approximate Markov boundary of x in
Proof. We have
(x)) = Var[Sa Dn] - 1/5(2)) + (2))
Varlfa Pnl - Var[fæ (w)) Dnl + n2((x) +
(0) a² log
Varlʃ [nn]
()()))))) +e
Var[f (()) Dn,
20² I(Jx: (z)) D..) + 1/ (z) te
where (i) follows from the defining property of an e-approximate Markov boundary (cf. Equa- tion (14)); and (ii) follows from Lemma C.38 and using monotonicity of variance.
Lemma C.18. For any 0, 2 0, and x E A.
[(ai yn.... (m)) Dn) S Rn (Bn,,(((z)) Tn
(18)
where Br.e( (x) an c-approximate Markov boundary of x S, [x),(x)) S be and where (-) R(. Dimn) denotes the information ratio from Equation (8).
We remark that (-) as shown in Lemma C.7, and hence, the right-hand side of the inequality is well-defined.
Proof. We use the abbreviated notation B Bn.e(a). We have
(6)
T( UB
Dn)
T(SA: UB (Dx)
1
Σ
I(fAiva (2x)
Knn BEB
(Hi)
b.
max
Iffai Va (D.) #EB
Kn,b,
(tv) be
max 1(ffi Va (n,)
Kn,b.
be
max I(fA: Vim))
Rnn
aeS
b T'
Rn.b.
where (i) follows from monotonicity of mutual information; (di) follows from the definition of the information ratio Fn,b, (cf. Equation (8)); (iti) 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 æ E AAS is shown by Lemma C.14 with C = 28
To prove the more general result, fix any E A and > 0. By Lemma C.16, there exists an e-approximate Markov boundary Ba, (w) x in such that [Bn,( S b. We have
(6)
(2) < 202.
I(fa: (B)
Dn) + n (2) +e
(it) 20
In (2())) +
Ri,
(Bn, (x))
28

---

where (i) follows from Lemma C.17; and (ii) follows from Lemma C.18.
Let c L with 2|S|o202 /Amin [Kss). Then, by Equation (15), be be bounded for instance by vn. Together with Theorem C.12 this implies for ITL that
(x)) - 1/ (z) + 20² Vnrn + oyalvn
n (z) c ///p// \//V
for a constant d', e.g., 20
C.6.2 Convergence outside S for VTL
Proof of Theorem 3.2 for VTL. Analogously Lemma C.17, we have
o (x) Varifa Dn. n (a) + (²)
Var[S= [r.] Var[S= (x): Dn) + n)((2)) +
where (i) follows from the defining property of an e-approximate Markov boundary (cf. Equation (14)). Further, we have
Var(fz Dr) Varlfa (w): Dn,]
Σ
(Var[fa (D)] Var(Sa y/ Dr.))
(x)
(10)
(tr Var[fa Fiml
Var(fa yas Bimh))
(E
(hi)
b.In
where (i) follows from the submodularity clus (ti) uses that the posterior variance Gaussians independent of the realization and only depends on the location of observations; and (iii follows from the definition of In and Lemma C.16.
The remainder of the proof is analogous to the result for ITL, using Theorem C.13 to bound F,,-
C.6.3 Existence of an Approximate Markov Boundary
We now derive Lemma C.16 which shows the existence of an upproximate Markov boundary of in S.
Lemma C.19. For any S and ls 2 0, there exists B S with [B] l such that for all x E S,
VariSa' Val S 2; 7k
(19)
Proof. We choose B C S greedily using the acquisition function def
Ty arg max 1(fsi Va YBB-.)
#Es
where Bg T1.e. Note that this is the "undirected" special case of ITL, and hence, we have
Var fa ys..
2
25
where (i) due to Lemma C.14; and (fi) due Theorem C.12 and as,s(k) S 1. Lemma C.20. Given any > 0 and B C S S with [S| < co, such that for any x' E S,
exmin (ss)
Varlf,r ynl <
(20)
S
Then for any X,
Varifa ypl 5 Var far fsl +
(21)
29

---

Proof. We will denote the right-hand side of Equation (20) by e'. We have
Var fe Ys!
fz [ar Lf fs. yBl
yBl
Var [B as
Js+ Ysl
Ugl
(6))
Var [5
Ss yBl + Var [B If
fs. ysl
yp!
(axs) Var 1
fs]
Var [e a0 ss! yB
irreducible uncertainty
reducible (epistemic) uncertainty
where (i) follows from the of total variance; (di) uses that the conditional variance Gaussian depends only on the location of observations and not on their value; and (131) follows from fn 1. YB fs since B C S. It remains to bound the reducible uncertainty.
Let ha RRd + R, fs + B[fa fsl where write d
|S]. Using the formula for the GP posterior
mean, we have
h*()s) Blfa] (fs E[fss)
where z def Kgg Ksn- Because is a linear function in Js we have for the reducible uncertainty that Var fo [ (fs)
Vel "Varlss yol=
(3)
S d diag Varlfs yBl=
(4i)
S éd xT=
c'd Kos Kgg 1 Kgg KS
édd
< Amin (Kss) Amin (Kss)
K Kas Kgg KSx
(si1)
e'do2
where (i) follows from Lemma C.37; (ii) follows from the assumption that Var(Ja' yyl S e' for all x S: and (iii) follows from
K K KSn S K = o²
since Ke Kesk
58 Ksa 20. 0.
Proof of Lemma C.16. Let B C be the set size generated by Lemma C.19 to satisfy Var [yB] I 2022g/////// / for all x' S. We have for any æs E X,
(4)
Var[sa Day Yal Var fm ys
(80
Var[Sa fs] +
where (i) follows from monotonicity of variance; and (ii) follows from Lemma C.20; using [S] < oo and the condition on A.
We remark that Lemma C.19 provides an algorithm (just "undirected" ITL!) to compute an approx- imate Markov boundary, and the set B returned by this algorithm is valid approximate Markov boundary for all æ E X. One can simply swap-in ITL with target space (ær for "undirected" ITL to obtain tighter (but instance-dependent) bounds on the size of the approximate Markov boundary.
C.6.4 Generalization Continuous for Finite Dimensional RKHSs
In this subsection we generalize Theorem 3.2 to continuous sample spaces S. We will make the following assumption:
30

---

Assumption C.21. The RKHS of the kernel l is finite dimensional. In other words, the kernel & can be expressed as k(x, x') Φ(x) Φ(x') for some feature map X R2 with d < co.
the following, we will denote the design matrix of the sample space by def ((z): E SS E R (l and we denote by HI orthogonal projection the orthogonal complement of the span of ④b In particular, it holds that
1. H 0 for all span Φ, and 2. L = for all v E (span Ø)-
Especially, v E ker H if and only if E span 4. This projection can be computed as follows: Lemma C.22. It holds that
I
(22)
Proof. & ( > is the orthogonal projection onto the span of d (see, e.g., Strang, 2016, page 211). Lemma C.23. Under Assumption C.21, the irreducible uncertainty (z)()) of X
ns(()) =1
(23)
where ||u||A Vo Av denotes the Mahalanobis distance.
Proof. This 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 (xe 0 for all æ!l E X' with c(x!!) E span +. That is, the irreducible uncertainty zero for points the span of the sample space. In contrast, for points x with o(x E (span x) the irreducible uncertainty equals the initial uncertainty: (x+)) = (x+ ). The irreducible uncertainty of any other point x can be computed by simple decomposition of (xx) into parallel and orthogonal components.
Assuming that Assumption C.21 holds and given any (non-finite) S C X, there exists a basis Us C X' in the space of embeddings <6-) such that span span SZ 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 continuous domain). Let be any (continuous) subset of X and let Assumption C.21 hold with d < cc. Further, for any c <>> 0, let the smallest integer satisfying
Odmial (Kngts)
(24)
2do272
Then, for any 2 0 and X, there exists e-approximate Markov boundary (x)e of x in S with size at most k.
Proof sketch. opposed to S.
The proof follows analogously to Lemma C.16 by conditioning on the finite set Ωg as
C.7 Proof of Theorem 3.3
We first formalize the assumptions of Theorem 3.3:
Assumption C.25 (Regularity of (*). We assume that 1* is in reproducing kernel Hilbert space H2(X)) associated with a kernel l: and has bounded norm, that is, || B for some finite B E IR. Assumption C.26 Sub-Gausssia noise). We further assume that each en from the noise sequence {En 1 is conditionally zero-mean p(zx) -uu---ausssaaa with known constants p(z) for all X. Concretely.
(x=p((xm)) 2
Vn I,İE:: E[eArn
[Da-1] < exp
where Dn-1 corresponds to the o-algebra generated by the random variables (x,, e )2-1 and æn.
31

---

We make use of the following foundational result, showing that under the above two assumptions the (misspecified) Gaussian process model from Section 3.1 an all-timm time well-calibrated model of f*: Lemma C.27 (Well-calibrated confidence intervals; Abbasi- Yadkori (2013); Chowdhury & Gopalan (2017)), Pick E (0, 1) and let Assumptions C.25 and C.26 hold. Let
(a) - 11 + 2/n + +1+ log(1/6))
where p m p(x)." Then, for all a E X and n 2 0 jointly with probability at least 1 5, (f* (n( S 3,( (x())
where Po (x) and a (x)) are mean and variance (as defined in Appendix B.2) of the GP posterior of f()) conditional on the observations 'D,, pretending that is Gaussian with variance p² (x:)).
The proof of Theorem 3.3 is straightforward application of Lemma C.27 and Theorem 3.2:
Proof of Theorem 3.3. By Theorem 3.2, we have that for all E A,
(x) S V (2(()) + + S ns(x) + vn)s(n).
The result then follows by application Lemma C.27.
C.8 Proof of Theorem 5.1
In this section, we derive our main result on Safe BO. In Appendix C.8.1, 1, we give the definition of the reachable safe set R and derive the conditions under which convergence to the reachable safe set guaranteed. Then, in Appendix C.8.2, we prove Theorem 5.1.
Notation 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 - -)-cofiieee intervals (CIs)
(a)) def Cn-1(ar) n [xn + (x) o,
(25)
where def C-1(x)= R.
We write Un (x) def wn(x) Un (x) (x) for its upper bound, lower bound, and width, respectively.
= max (z)) (xxx der min (x), and
We learn separate statistical models f and fgi.-- agggg) for the ground truth objective f and ground truth constraints .ot.....99). We write I - 1......... ... and collect the constraints in Without loss of generality, we assume that the confidence intervals include the ground truths with probability least In,i, Wn.i 17, fn, the respective quantities. In the following, we do not explicitly denote the dependence of In on
I, def (1....,4] 9).
jointly for all I." Il For
denote by
To improve clarity, we will refer to the set of potential maximizers defined in Equation (5) as Mn. and denote by A, an arbitrary target space.
We point out the following corollary:
Corollary C.28 (Safety). With high probability, jointly for any and any Ia
Vx E Sn ott (x: 2 0.
(26)
C.8.1 Convergence to Reachable Safe Set
Definition C.29 (Reachable safe set). Given any pessimistic safe set S C X' and any 2 0 and 3 2 0, we define the reachable safe set up to (c, Slackk and its closure as
(S) def SU {x X' \
9f (a) 3(m (æ; S) +e) 2 0 for all i E I.}
(S) def
lim (S)
where (Re,g)" denotes the n-th composition of Re,s with itself.
10 8,, (6) can tightened adaptively (Emmenegger et al., 2023).
"his can be achieved by taking union bound and rescaling 6.
32

---

Remark C.30. Convergence of the safe set to the closure of the reachability operator can only be guaranteed for finite safe sets ([S* < oc). The following proofs readily generalize to continuous domains by considering convergence within the k-th composition of the reachability operator with itself for some & <. co. this case the sample complexity grows with A: 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.+1 = S; for a). This assumption is straightforward to lift since for any 0 and T 2 I.
T
T Σ
max A ( Fln+T) S Σ max A F1:++1) $ zES,
max Aa(a F1a++)) & TT wESntt
wESn
T
using submodularity for the first inequality and the monotonicity the safe set for the second inequality. In particular, this shows that one continues learning about points in the original safe set even as the safe set grows.
We denote by Sq the initial pessimistic safe set induced by the (prior) statistical model g (cf. Section 5)
and write Re,8 = (So).
Lemma C.31 (Properties of the reachable safe set), For all S, _ X, e 2 0, and z 0:
(i) S' CCS- = (S)) C (S,, (ii) (S)) CS = (S) S S, and
(iii) Ro, Ro,0- = S'.
Proof (adapted from lemma 7.1 of Berkenkamp et al. (2021)).
1. Let æ E Re Re.)(S"). If x E S then a E Re (S,, so let x & S. Then, by defi- nition, for all i Ig. fi()) (x; - E 2 0. By the monotonicity of variance, 17: (²; 2 (a for all i E I, and hence f; (x) - (=; - 2 0 for all i I, It follows that æ E (S.)
2. By the monotonicity of variance, (2;; (S)) 2 (x: by definition of the safe region, we have that Re (R,, S S. The result follows by taking the limit.
for all X and E I. Thus,
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 Ro The following is our main intermediate result, showing that either we expand the safe set at some point the uncertainty converges to the irreducible uncertainty.
Lemma C.32. Given any no 2 O, O. let n' be the smallest integer such that Un S ē where ē == c/2. Let Brotn' = -maxieI, Bnotn'. Assume that the sequence of target spaces is monotonically decreasing, i.e., Ant1 An, Then, we have with high probability (at least) one of
(o Amotn's ViEI:
Wnotw-a(1) S Bugtt [nd(;;; Sngtn() +
and Anoto' 1 Re. (Snotn') C Snotn))
or |mngtn't1
Stal
Proof. Suppose that |Snotx' +1| = |Sno Then, by Theorem 3.3 (using that the sequence of target spaces is monotonically decreasing), for any E Anotw and E I,
Wno (xx) S Snotn(M((z (no + c]. As Sno+n'44 Snotn we have for all E Anotn' \ Sno+w and E Ig, with high probability that
> Inoon' (x) 2 g (x) - Wnotn', (x))
2 g. (æ:) Brotn (n (x:; Snotar) + e).
It follows that Anotw n Re.togga (Snotw) C Snotn'.
33

---

To gather more intuition about the above lemma, consider the target space
Ep def S, \ Sn.
(27)
We call e,, 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 0 and e, 3 0, E, An then with high probability,
Sn U (An m
(S.)) (e,)(Sn).
Proof. With high probability, (S,) C S, = Sn U En The lemma is direct consequence.
The above lemmas can be combined to yield our main result of this subsection, establishing the convergence of ITL the reachable safe set.
Theorem C.34 (Convergence reachable safe set). For.any any > let n' be the smallest integer
satisfying the condition of Lemma C.32, and define n' = =IS*| + 1)n'. Let Bn. 2 Sa, for all S n E I.- Assume that the sequence of target spaces monotonically decreasing, i.e.. Ant1 S An. Then, the following inequalities hold jointly with probability at least 1 - 8:
(i) Vn 2 0, E Is 9. (Tn) 2
safety
(ii) A R.,.,r S Spr S Ro,0 = S
convergence to safe region
(ii)) Va E Ant, V I: uny (x)) S Bn.,% R R,, +6
convergence of width
(iv) Vo E ReB,,r. Vi I (;; R R,, =0
convergence of width within safe region
Proof. (i) is a direct consequence of Corollary C.28. S., C S* follows directly from the pessimistic safe set S,,- from (di) being a subset of the true safe set S*. (év) follows directly from the definition of irreducible uncertainty. Thus, it remains to establish A, O RR,,,.- C S and (iát).
Recall that with high probability [S,] E [0, |] for all n 2 0. Thus, the size of the pessimistic safe 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:
Vo E Anotw', Vi E I Wno-n' ((() < Bnotw' [Tr Snotw + and Anotn' O Re, (Snotwe Snotn'
(28)
Because the safe set expand most S many times, Equation (28) occurs eventually for some no < |S*|n'. this case, since Br 2 Anotn' and An S. Anotn (as no + n' S n²) we have that
An n R (Snotar) S. Anotw n Re, (Sngtar)
C Smotn'-
By Lemma C.31 (ii), this implies
An n Re,B,r C Snottn C Snr.
emphasize that Theorem C.34 holds for arbitrary target spaces A., additionally, En C A., for all > 0 then by Lemma C.33, Theorem C.34 (ii) strengthens to R. C S,r, Intuitively, E, An ensures that one aims to expand the safe set in all directions. Conversely, En g A, then one aims only expand the safe set in the direction of A,, (or not at all if A,, S.).
34

---

"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,, Straightfor- ward application of Theorem C.34 (informally) requires that the sequence of target spaces is mono- tonically decreasing (i.e., An+1 S A,,, and that each target space A, 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,, Theorem C.34 bounds the convergence of the safe set to the reachable safe set. 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,, satisfies the (informal) requirements laid out previously, since it is monotonically decreasing by definition, and with high probability, any point x E S* that is not in S, is contained within En.
2. Level set estimation: Given any T E I, we denote the (safe) r-level set of f by c def (xc E (x) = J. We define the potential level sel as
C _ fx E S, (x(x)= S S (x)).
def
(29)
That L the subset of the optimistic safe S., where the 7-level of f* may be located. Analogously to the potential expanders, it is straightforward to show that 2% over-approximater the true r-level set and is monotonically decreasing.
We remark that our guarantees from this section also apply to the standard ("unsafe") setting where S Sy X.
C.8.2 Convergence to Safe Optimum
In this section, we specialize Theorem C.34 for the case that the target space contains the potential maximizers Mn (cf. Equation (5)). It is straightffrward
that the sequence M, is monotonically decreasing (i.e.. Mx41 S M,). The following lemma shows that the potential maximizers over- approximate the set of safe maxima X det arg max (x)
Lemma C.35 (Potential maximizers over-approximate safe maxima). For all n 2 0 and with probability at least 1 8.
(i) x E X implies a E Mn and
(ii) x & M, implies x & X".
Proof. If & Mn then
U (x) < max (n,((x)) max (x,)(x))
E'.
z'eS'
where we used Sn C S* with high probability, which directly implies with high probability that E X
For the other direction, if X then
(x) 2 max (xx) 2 max f
es
e'E,,
with high probability.
We denote the set of optimal actions which are safe up to (c, Sl-ck by
X def
arg max (x)),
2ER..
and by fü, the maximum value attained by ft at any of the points in X The regret can be expressed as
Tn =( f
The following theorem formalizes Theorem 5.1 and establishes convergence to the safe optimum.
35

---

Theorem C.36 (Convergence to safe optimum), For any > 0, n' be the smallest integer satisfying the condition of Lemma C.32, and define n* - - 1)n'. Let B., 2 for all n S n", E I. Then, the following inequalities hold jointly with probability at least 6:
(i) Vn 2 0, Vi E Is 91 (F.)) 2
safety
(ii) vn 2 n² : rn (R e.
convergence to safe optimum
Proof. Fix any x' E X S R.. Assume w.l.o.g. that x" M, Then, with high probability,
f2 = (x") S Un un")(("))
lu f(=") + Wx ,(x")
In (ūbn) Whi f(x0)
I f (In.) + Wn ,(x"))
3 (
where (i) follows from the definition of ; and (ii) follows from Theorem C.34 and noting that x² E MM n R.B....
We have shown that (*((x..) f",... e, which implies rn- (Re,p..) S e. Since the upper- and lower-confidence bounds are monotonically decreasing increasing, respectively, we have that for all n", In (R,,R. (B.. S c.
C.9 Useful Facts and Inequalities
We denote by 3 the Loewner partial ordering of symmetric matrices. Lemma C.37. Let A gaax be a positive definite matrix with diagonal D. Then, A < nDD
Proof. Equivalently, one can show nD 2 O. We write A def D 3 @/ 42 and thus, Q D 1/2 -/2 is a positive definite symmetric matrix with all diagonal elements equal to 1. remains to show that
n = D D - Q) 0.
Note that Dn (((Q) = tr Q and hence, all eigenvalues of Q belong to (0, n).
Lemma C.38. af E (0, Mf some M > 0 and 2 then
S M log
(30)
If additionally, a 2 M for some M' > 0 then
b
b- 2 M' log
(31)
Proof. Let f(x) def = log r. By the mean value theorem, there exists E (a, b) such that
(c) = f(b) - -((a) log b log
log( 4
b-a
b-a b
Thus,
b
log :))
- a = c. log
<
1ROtherwise, with high probability, fr (r Si.
36

---

Under the additional condition that a 2 M', we obtain
b - a==aca c. log - > M' log
D Interpretations & Approximations of Principle (f)
We give a brief overview of interpretations and approximations of ITI., as well as alternative decision rules adhering to the fundamental principle (1).
The discussed interpretations of (t) differ mainly in how they quantify the "uncertainty" about A. In the GP setting, this "uncertainty" is captured by the covariance matrix Σ of fA. and we consider two main ways of "scalarizing" E:
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 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 the points in A, and they coincide when |A| =
D.1 Interpretations of ITL
We briefly discuss three interpretations of ITL.
Minimizing generalized variance In the GP setting, ITL can be equivalently characterized as minimizing generalized posterior variance:
Fn = arg max TffAi D..)
#ES
|Var ff Dnn-1ll
arg max #ES 2
log
Var[fa Dn-1, Vwll
arg min Var
(32)
#ES
Maximizing relevance and minimizing redundancy An alternative interpretation of ITT. is
I(fAi Vee (D)) 1(fAi
I(fAi Um: Dr))
(33)
relevance
reclumancc
where 1(fai Mzi D.)) 1(faiwm) 1(faiVe Vee (n)) denotes the multivariate information gain (cf. Appendix B). this way, ITL can be seen as maximizing observation relevance while minimizing observation redundancy. This interpretation is common in the literature feature selection (Peng et al., 2005; Vergara & Estévez, 2014; Beraha et al., 2019).
Steepest descent in measure spaces ITL can be seen performing steepest descent in the space of probability measures over fA. with the KI. divergence as metric:
i(fAi D,)) = E,, [KL(p(fA Dn. Va Ilp( [.,))]
That is, ITL. finds the observation yielding the "largest update" to the current density.
D.2 Interpretations VTL
Quantifying the uncertainty about f.A by the marginal variance of points in A rather than entropy (or generalized variance), the principle (f) leads to VTL. Note that [A] = 1, then VTL is equivalent to ITI. Unlike the similar, but more technical, TRUVAR algorithm proposed by Bogunovic et al. (2016), VTI does not require truncated variances, and hence, VTL. can be applied to constrained settings (where A & S) as well.
37

---

Relationship to ITL
Note that the ITL criterion in the GP setting can be expressed as
En arg min log Var [fa Dn
(34)
#
where for positive semi-definite matrix A with spectral decomposition A = VAV we write log A V log A AVT for the logarithmic matrix function. To derive Equation (34) we use that log A - E, log ); (A) = ir log A. Hence, ITL and VTL are identical up to different weighting
of the eigenvalues of the posterior covariance matrix.
Minimizing bound to the approximation error the approximation error (x) Mn (2)) by
Chowdhury & Gopalan (2017) (page 19) bound
ky (x: K + Pt) ELal Eral+ (f) - kx( (K: P.) P
variance
bins
where kx(x)) def K Kw Kg def 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.c.,
K a and P: def Pa... Similar to standard bias-variance
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 to
F. = arg max #ES
VarlSa/ [Da-1] CorlJa' Ua Dn--1)²
(35)
EA
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 prediction target with higher variance. This is precisely what leads to the "diverse" sample selection, and 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
Cov Yar [D,)]
arg min #ES
Σ
Varifa Da, yol
arg min #E8
Varlfa [x,]
VarlMte [D,]]
se EA
æ'EA
Varlfa. [y) Covlfa' Vx D
arg max #ES
const
Var[Jar [Da] Varlyz [Dn]]
mt EE
arg max
Σ
Varifa' [Dn] Corlfa', ym Dz1 const.
#ES
x' EA
D.3 Mean Marginal ITL
MacKay (1992) previously proposed imman-marginal" ITL (MM-ITL) in the setting where S X, which selects
Fr arg max #ES
Σ
I(fa'iva Dnn11)
(36)
w'EA
and which simplifies in the GP setting
Varlfa [Dn-1]
Dn arg max #ES
log
VarlSa' DD 1. Vne
E.A.A
arg min #ES
Σ
log Var [fa (Dn-1, yml
EEA
= arg min tr log diag Varlfa D Dn-1, #ES
(37)
38

---

Analogously to the derivation of Equation (34), this can also be expressed
arg min diag Var[fA Mmll
(38)
#5$
Effectively, MM-ITI. 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 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 (1), this can be seen minimizing the average marginal entropy of predictions within the target space:
= arg min #ES
Σ
H[ (Dn-1,
We remark that MM-ITL 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 fig are highly correlated while fio is mostly independent of the other points. Visually, imagine smooth function (i.e., under Gaussian kernel) with points through 9 close to each other and point 10 far away. Further, suppose that point 10 has 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-)varianee (i.c., small posterior "uncertainty"),
In contrast, ITL selects the point with the largest prior marginal variance (cf. Appendix C.I), point 10, since this leads to the largest reduction in entropy." 14
Similarity to VTL Observe that the following decision rule is equivalent VTL:
Tn arg maxtr Var(fa Da-1] tr Var ff Dn Vml.
#E8
By Lemma C.38, for any æ E this objective value can be tightly lower- and upper-bounded (up to constant-factors) by
Var[Ja' 1Dn-1l
Σ log
VarlSu
D Mee
''EA
Σ T(Ja' yan (D-1))
(see MM-ITI.
x'EA
(
Σ log 1og(1-
Cor([o' (o Mem D Dn--1²²)
(39)
m E'EA
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 and 6, we observe that MM-ITL performs similarly to VTL and CTL.
Convergence of uncertainty We derive a convergence guarantee for MM-ITL which analogous to the guarantees for ITL from Theorem C.12 and for VTL from Theorem C.13. We will assume for simplicity that F, is monotonically decreasing in n (i.c., an < 1).
Theorem D.1 (Convergence of uncertainty reduction of MM-ITL), Assume that Assumptions B. and B.2 are satisfied. Then for any n 2 1, if 2 ... Tn-1 and the sequence (x, se,) 1 is generated by MM-ITT then
1 Σ {)( T p
(40)
Y'EA
Proof. We have
P P
T
11
1=
17hss because the observation reduces uncertainty not just about the observed point itself.
1 Because points fi highly correlated, H[f.s] already "small".
39

---

max
Σ
T( (Da)
#ES
x'EA
T(Sa:: Umn++ (Dn)
d'EA
(150)
T(Jai Mun+t Yar
Σ x'EAA
1(fa' M.r...)
Σ
max 1(fa'i8x)
XCS
t'EA X
Σ EA
7m (1(43))
n
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 mutual information. The remainder of the proof is analogous to the proof of Theorem C.12 (cf. Appendix C.5).
Noting that
II (Dn-1)
x'EA
for any 2 1, E X, and x' A, Theorem 3.2 can be readily rederived for MM-ITL (ef. Lemmas C.14 and C.18). Hence, the posterior marginal variances of MM-ITL can be bounded uniformly in terms of T, analogously to ITL.
D.4 Correlation-basel Transductive Learning
We will briefly look at the CTL (Correlation-basee TL) decision rule
Z arg max
Σ
Corlfas Dn-11
(41)
E'EA
which permits no interpretation under principle (t). 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| then all decision rules coincide.
If, the other hand, correlations may be negative then there crucial difference between CTL and the decision rules motivated from principle (f). Namely, decision rules following (f) exhibit prefer- ence for points with high absolute correlation prediction targets as opposed CTL which prefers points with high positive correlation. This stems from the intuitive fact that points with strong negative correlation are equally informative as points with strong positive correlation. Nevertheless, we observe in our experiments that (even for a linear kernel which does not ensure non-negative cor- relations) points selected by ITL. and VTL are typically positively correlated with prediction targets.
D.5 Summary
We have seen that ITL, VTL, and MM-ITL can be seen as different interpretations of the same fundamental principle (t), with the approximations CTL. If [A| = and correlations are non-negative, then all four decision rules are equivalent. CTL prefers points with high positive
40

---

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-ITI. differ only in their weighting of the posterior marginal variances of points in A.
E Stochastic Target Spaces
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 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
(2009)). That is, if the target space can be covered approximately using finite (possibly large) set of points, the guarantees of Theorem 3.2 extend directly. This, however, can be impractical when the required size discretization for sufficiently small approximation error is large. In the following, we briefly discuss natural alternative approach based on sampling points from A.
Target distributions Let S X be a (possibly continuous) target space, and let Pa be a probability distribution supported A. In iteration n, subset A, of K points is sampled independently from A according to the distribution Pa and the objective is computed on this subset. Formally, this amounts single-sample Monte Carlo approximation of
En E arg max E, t pa [[( (Dn-1)]-
(42)
#ES
The convergence guarantees from Appendix can be generalized to the setting of stochastic target spaces by estimating how often points "near" specified prediction target E A are sampled. Definition E.1 (y--alll at æ)). Given æ E A and any 7 2 0, we call the set
Bx def (a' E X' || x'll S 7}
the y-ball at æ. Further, call (B (z)) the weight of that ball.
Proposition E.2 (sketch). Given any n 2 1, K 2 1, > O, and x E A. suppose that (., has weight p 0. Assume that the ITL objective is L Li-Lschhhitz continuous. Then, with probability at least 1 - exp( -(1 ()K)/8K)).
( 1
CCL
Tk(m)
/k(n)
where k(n) def Kmm/2.
Proof sketch. Let Y; Binom(K, K, p) denote the random variable counting the number of occurrences del of point from B, (x) in A. Moreover, we write X; 1(B, (z) A, * 0}. Note that
EX; ((B,(x))
= P(Y: = = (1 p) Kp
where the approximation stems from a first-order truncation of the Bernoulli series. Let X Σ X, with EX = nv Kpn.
Using the assumed Lipschitz-continuity of the objective, I(far: Ma DD--)) & LLTI(ffi Var Da-1) where de (A (x, U far) and By is the point from the 7-ball at The bound then follows analogously to Theorem 3.2.
know that
Finally, by Chernoff's bound, at least K pp/22 iterations contain a point from B, (w) with probability at least 1 exp(-Kpn/f
This strategy can also be used to generalize the VTL, CTL, and MM-ITL objectives to stochastic target spaces.
F Closed-form Decision Rules
Below, we list the closed-form expressions for the ITL and VTL objectives. the following, k. denotes the kernel conditional on D,,.
41

---

ITL
Varlya y/ D
I(fAi (D--1)
log
(43)
2
Var 1/x
fA D n-
hn x x) + p²
log
2
kn (x, x)) + p2
where (x) (x) (al2,,))K A)
(A,,
VTL
kn (2), x²)² kin ( 2.) + p2
Var[fa Dn-1:
Σ
(in=1(x',22))
x ELA
G Computational Complexity
Evaluating the acquisition function of ITL in round requires computing for each S
I I(fAx yan
Da)
[Var[Aa [r]]
log
(forward)
2
[aarffa
Va: Dall
Var Dnn]]
log
(backward).
2
Varlye
f.. Dn)
Let [ m and |A|] = k. Then, the forward method has complexity O(m . k-)). For the backward
method, observe that the variances are scalar and the covariance matrix Var [fx Dnn] only has to be inverted once for points æ. Thus, the backward method has complexity O + m))
When the size m of S is relatively small (and hence, all points in S can be considered during each iteration of the algorithm), GP inference corresponds simply computing conditional distributions of multivariate Gaussian. The performance can therefore be improved by keeping track of the full posterior distribution over fs of size 0 (mm²) and conditioning on the latest observation during each iteration of the algorithm. In this case, after each observation the posterior can be updated at cost of ((m) which does not grow with the time n, unlike classical GP inference.
Overall, when m small, the computational complexity of ITL is O + m²). When is large (or possibly infinite) and a subset of m points is considered in a given iteration, the computational complexity of ITL is ( + m n²). neglecting the complexity of selecting the mn candidate points. In the latter case, the computational cost of ITTL is dominated by the cost of GP inference.
Khanna et al. (2017) discuss distributed and stochastic approximations of greedy algorithms (weakly) submodular problems that are also applicable to ITL.
H Additional GP Experiments & Details
We use homoscedastic Gaussian noise with standard deviation 0.1 and discretization of
X' = [-3,3] 3)2 of size 2 500. Uncertainty bands correspond to one standard error over 10 random seeds.
Additional experiments
Figure 6 includes the following additional experiments:
Extrapolation Setting (Ans S = 0): Right experiment from Figure under the Gaussian kernel. ITL has similar advantage in the setting shown in Figure 3.
2. Heteroscedastic Noise: Left experiment from Figure under the Gaussian kernel with heteroscedastic Gaussian noise
[1
i 0.1 otherwise
p(x)
If observation noise is heteroscedastic, considering posterior rather than prior uncertainty, ITL avoids points with high alcatorie uncertainty, which accelerates learning.
42

---

ITL
VTL
CTL
UNSA
UNSA
TRUVAR
RANDOM
Extrapolation Setting (AnS = 0)
Heteroscedastic Noise
Entropy of fx
Entropy of fA
100
200
300
100
200
300
400
Number of Iterations
Number of Iterations
Effect of Smoothness: Laplace Kernel
Sparser Target
Entropy of fx
Entropy of f
0
100
200
300
100
200
300
400
Number of Iterations
Number of Iterations
Figure 6: Additional GP experiments
3. Effect of Smoothness: Experiment from Figure 3 under the Laplace kernel. All algorithms except for US and RANDOM perform equally well. This validates our claims from Sec- tion 3.3: in the extreme non-sme non-smooth case of Laplace kernel and C S, points outside A do not provide any additional information, and ITL and "local" UNSA coincide.
4. Sparser Target: Experiment from Figure 3 under the Gaussian kernel, but with domain extended X' [-10, 10)².
Hyperparameters of VRUVAR As suggested by Bogunovic et al. (2016), we use Ti 1, 0.1, and 0 (even though the theory only holds for > 0). The TRUVAR baseline only applies when A C S (cf. Section 6).
Smoothing reduce numerical noise Applied running average with window 5 entropy curves of Figures? 2 and 6 to smoothen out numerical noise.
I Alternative Settings for Active Fine-Tunie Tune-Tuning
our main experiments, we consider the setting Ans = 0, i.e., the prediction targets cannot be used for fine-tuning since their labels not known. This setting is particularly relevant for practical ap- plications where the model fine-tuned dynamically at test time to each prediction target (or a small set of prediction target). Put differently, in this "transductive" setting, extrapolation 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 train-time without knowledge of the concrete prediction targets, but under the assumption of samples from (or knowledge of) the target dis- tribution. In the following, we briefly survey two settings motivated from an "inductive" perspective.
I.1 Prediction Targets are Contained in Sample Space: C S
If labels can be obtained cheaply, one can also fine-tune on the prediction targets directly, i.e., A C S. Note, however, that the set A is still assumed to small (e.g., |A] = 100 in the CIFAR-100 exper- iment). We perform experiment in this setting and report the results in Figure 7. The experiment shows that similarly to the GP experiment from Figure - there can additional value in fine-tuning the model relevant data selected from S beyond simply fine-tuning the model on A.
43

---

BIG
TYPICLUST
PROBCOVER
MAXDIST
RANDOM
100
600
# Samples from Support Pa
500
80
400
Accuracy
70
60
300
200
40
100
30
20
20
Number Batches Size
Number of Batches Size 10
Figure 7: Evaluation of CIFAR- -EFFR-1000A experiment in the setting A i.e. one also sample from the 100 prediction targets A. The solid black line denotes the performance of the model fine-tuned on all of A. This experiment shows that there is additional value in fine-tuning the model relevant data from S beyond simply fine-tuning the model on A. The baselines are summarized in Appendix J.5
1.2 Active Domain Adaptation
Active DA (Rai et al., 2010; Saha et al., 201 Berlind & Umner, 2015) studies the problem of selecting the most informative samples from (large) target domain A, given a model trained on a source domain S. This problem can be cast as instance of transductive active learning with target space A and sample space S S A where the model is already conditioned on all of This is slightly dif- ferent from the setting considered in Section 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 dissimilar to S. Evaluating ITL and VTL empirically in this setting is a promising direction for future work.
J Additional NN Experiments & Details
We outline the active fine-tuning of NNs in Algorithm 1.
Algorithm Active Fine- Mane-Tunngggg of NNs
Given: initialized or pre-trained model f. small sample A ~ Pa
initialize dataset D = 0 repeat
sample $ ~ Ps subsample target space A' u.a.r. A initialize batch B = /
compute kernel matrix K over domain [S, A']
repeat 6 times
compute acquisition function w.r.t. A'. based on K add maximizer æ E S of acquisition function to B update conditional kernel matrix K
obtain labels for B and add to dataset D update f using data D
In Appendix J.1, detail metrics and hyperparameters. We deseribe 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 ITI. and CTL significantly outperform a wide selection of commonly used heuristies. In Appendices J.6 and J.7, we conduct additional experiments and ablations.
44

---

Table 1: Hyperparameter summary of NN experiments. (*) we train until convergence on oracle validation accuracy.
MNIST
CIFAR-100
0.01
M
100
3
10
1000
1000
batch size b of epochs
1
10
(*)
learning rate
0.001
0.001
Hübotter et al. (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.
J.1 Experiment Details
We evaluate the accuracy with respect to PA using a Monte Carlo approximation with out-of-sample data:
accuracy(0) (2 arg max (2; 0))-
We provide an overview of the hyperparameters used in our NN experiments in Table 1. The effect of noise standard deviation p is small for all tested p [1, 100] (cf. ablation study in Table 2). 15 M denotes the size of the sample A ~ PA. In each iteration, we select the target space A < A' as random subset of m points from A. We provide ablation over in Appendix J.6.
During each iteration, we select the batch B according to the decision rule from random sample from Ps of size k." !?
Since train the MNIST model from scratch, 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 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 100 experiments, use pre-trained EfficientNet-BD (Tan & Le, 2019), and fine-tune the final and penultimate layers. We freeze earlier layers to prevent overfitting the "few-shot" training data.
To prevent numerical inaccuracies when computing ITL objective, we optimize
1
Varlyz Da
T(yAi Vm Dn-1)) log
(44)
Varlyz
M D Dn-1)
instead of Equation (43), which amounts to adding p² the diagonal of the covariance matrix before inversion. This appears to improve numerical stability, especially when using gradient embeddings. 19
We use larger noise standard deviation in CIFAR-100 to stabilize the numerics of batch selection via conditional emheddings (cf. Table 2).
'TTis appears to improve training, likely because it prevents overfitting to peculiarities finite sample (cf. Figure 16).
"In large-scale problems, the work of Coleman et al. (2022) suggests an (approximate) nearest neighbor search select (large) candidate set rather than sampling u.a.r. from Ps. This can viable alternative to simply increasing and suggests future work.
accuracy validation from Pa decreases in an epoch. IIn our experiments, we observe that the effect of various choices of p on this slight adaptation of the ITL decision rule has negligible impact performance. The more prominent effect of p appears to arise from the batch selection via conditional embeddings (cf. Table 2).
Thaaa is. to stop training
45

---

In our experiments, we use last-layer neural tangent embeddings 20 and Σ = I to evaluate ITL and VTL, and select inputs for labeling and training f. Notably, we use this linear Gaussian approximation of only to guide the active data selection and not for inference.
J.2 Embeddings and Kernels
Using neural network to parameterize f, evaluate the canonical approximations of by stochastic process in the following.
An embedding Φ(x) is latent representation of an imput æ. Collecting the embeddings as rows in the design matrix + of set of inputs X, one can approximate the network by the linear function fx= 3 with weights f. Approximating the weights by B ~ (p,, Σ) implies that fx 1 +EΦ ). The covariance matrix Kxx- o can be succinctly represented in terms of its associated kernel k(æ,æ") +())) EΦ((''). Here,
( is the latent representation of æ, 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 (xx) 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-dimensions feature map akin to random feature methods (Rahimi Recht, 2007).
2. Outpul Gradients (eNTK): Another common choice is ((xx) Vo fa:; 0) where
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 al., 2023). Kassraie & Krause (2022) derive bounds of Tn under this kernel. If 0 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) Vo (xf(:; 0), ((x))(()= o=0
where loss function, ((x) is the predicted label, and Ô are the current parameter estimates (Ash et al., 2020).
4. Outputs (eNNGP): Another possible choice is (xx) = fx)), i.e. the output of the network. Its associated kernel is known the empirical neural network Gaussian process (eNNGP) kernel (Lee et al., 2018).
5. Predictive (Kirsch, 2023): Given Bayesian neural network (Blundell al., 2015) or probabilistic (deep) ensemble (Lakshminarayanal et al., 2017), which induce samples O....., 0k ~ p(0) from the distribution over network parameters, one can approximate the predictive covariance k( x²) = Cove [f 0), (='; 0)]. This kernel measures proximity the prediction space rather than parameter space and such does not require gradient information. The, corresponding feature map is (xx) V (1;
Ox)]
where f(;; 0x) def f(:; 0x) * > fxx 0t).
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 embedding
(xx)) Vg. (f 0). (((=))))==
(45)
where 0' are the parameters of the final output layer, Ø are the current parameter estimates, ((x) = arg max, fa fa(:;; 0) are the associated predicted labels, and fcE 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 the norm assumed by taking any other proxy label (xx) In Figure 8, we observe only negligible differences in performance between this and the last- embedding.
we observe essentially the same performance with loss gradient embeddings, cf. Appendix J.2.
46

---

MNIST
0U
70-
60
50
20
50
1000
20
00
30
100
0.00
SSmples Support
80
600
-0
2.0
20
100
100
100
Number of Samples
Number Batches of Size
Figure Comparison of loss gradient ("G-") and last-layer embeddings ("L--").
100
Samples from Support
00
20
50
Number of Samples
Number of Samples
Figure Uncertainty quantification (i.e., estimation of Σ) via Laplace approximation (LA, Daxberger et al. (2021)) over last-layer weights using 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 performance improvement beyond the trivial approximation
J.3 Towards Uncertainty Quantification in Latent Space
A straightforward and common approximation of the uncertainty about NN weights is given by 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 ITI., VTL, and CTL 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 al., 2021; Antorán al., 2022), variational inference (Blundell al., 2015), Markov chain Monte Carlo (Maddox et al., 2019) have been studied. We also evaluate Laplace approximation (LA, Daxberger al. (2021)) for estimating Σ but see no improvement (cf. Figure 9). Nevertheless, we believe that uncertainty quantification is promising direction for future work, with the potential improve performance of ITL and its variations substantially.
J.4 Batch Selection via Conditional Embeddings
will refer 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 fx from Appendix J.2 by iteratively conditioning on the previously selected points 1 and updating the kernel matrix Kxx using the closed-form formula for the variance of conditional
47

---

ITL
ITL top
CTL
CTL Bop
RANDOM
100
600
Samples from Support of P2
400
70-
900
60
60-
1000
80
20
60
80
100
20
40
80
100
Number of Size
Number Batches of
Figure 10: Advantage of batch selection via conditional embeddings over top-b selection in the CIFAR-100 100 experiment.
Gaussians:
Kxx t Kxx- Ka,a, + p²
Kxa, K2,X
(46)
where j denotes the index of the selected æn,s within X and p² is the noise variance. Note that K æ,, a scalar and Kxæ, is row vector, and hence, this iterative update can be implemented efficiently.
We remark that Equation (3) a natural extension of previous non- oon-adtttvve 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 al., 2024). BACE simultaneously maximizes "distance" between points in a batch and minimizes "distance" to points A.
The sample efficiency of BACE B, and therefore also the greedily constructed B; (which gives 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 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, single batch selection step of BACE has complexity 0 (b(k2 2 + m²)) where is the size the batch, = |A] 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 is described in Appendix G.
J.5 Baselines
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 ITL, but approximates the conditional entropy based on the networks' softmax output rather than using GP approximation. We approximate the conditional entropy using single gradient step of the hallucinated updates on the parameters of the final layer, mentioned by Mehta et al. (2022). We observe that EIG is not competitive for batch-wise selection (CIFAR- 100) since does not encourage batch diversity. Moreover, we observe that EIG is orders of magnitude slower than ITL. (since it has to compute |S] individual gradient steps where C is the number classes). We note that since our datasets are balanced, the AEIG algorithm from Mehta et al. (2022) coincides with EIG.
48

---

ITL
MNIST
CIFAR-100
100
90
80
Accuracy
80
60
40
20
Samples from Pa
100
600
400
50
200
20
40
60
80
100
20
40
60
80
100
Number of Samples
Number of Batches of Size 10
Figure 11: Comparison to baselines for the experiment of Figure 4.
Since, EIG does have an open-source implementation, we implemented it ourselves following Mehta et al. (2022). For TYPICLUST & PROBCOVER, we use the author's 's implementation. In the figure, we show that ITL. & VTL substantially outperform all baselines.
In the following, we briefly deseribe other commonly used "undirected" decision rules.
Denote the softmax distribution over labels at inputs by
pi (x; 0) x exp(fi(x;;)
The following heuristics computed based on the softmax distribution aim to quantify the "uncertainty" about a particular input a::
MAXXENTRPP (Settles & Craven, 2008):
arg max Hlp(a On-)) wES
MAXMARGIN (Scheffer et al., 2001; Settles & Craven, 2008):
En arg min P1 (1::; θn- -P2(2: 2n-1)
#ES
where P1 and Pa the two largest class probabilities.
LeASTCONFIDENCE (Lewis & Gale, 1994; Settles & Craven, 2008; Hendrycks & Gimpel, 2017; Tamkin et al., 2022):
arg min pa (z;; θn-1)
#ES
where P1 is the largest class probability.
An alternative class of decision rules aims to select diverse batches by maximizing the distances between points. Embeddings &f (x) induce the (Euclidean) embedding distance
(x, x') [((()) <baa')l2
Similarly, kernel & induces the kernel distance
k(zz, x) + M(x' x') 2k( x'). du (1x x') def
straightforward to see that if k( x() (fx:) (((x'))(()) then embedding and kernel distances coincide, i.c., dø (x, x') dx(xx
49

---

MAXDIST (Holzmüller et al., 2023; Yu & Kim, 2010; Sener & Savarese, 2017; Geifman & EI- Vaniv, 2017) constructs the batch by choosing the point with the maximum distance to the nearest previously selected point:
arg max min d( mx))
#
Similarly, K-MEANS++ (Holzmüller et al., 2023) selects the batch via K-MEANS+ seeding (Arthur al., 2007; Ostrovsky al., 2013). That is, the first centroid æ; 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 z) x min d x;,
zkn
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- decision rules.
UnDIRECTED ITL chooses
Zn arg max [[ss: ya (Dn-1) #ES
arg max I( Uee (Dn-1).
#ES
This can be shown to equivalent to MAXDET (Holzmülllrr et al., 2023) which selects
In arg max K₂ + +
#ES
where K, denotes the kernel matrix over 11.- U(x). conditioned on the prior observations Da-1-
UNSA (Lewis & Catlett, 1994) which with embeddings Φ,-- after round 1 corresponds to:
Cn arg max o (x)) = arg max aES
|| (x))
#ES
With batch size 6 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 VTL. without specified prediction targets (i.e., A 8). In the literature, this decision rule 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 Ps which not in the support of PA since the points are "adversarial examples" that the model 0 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:
COSINESIMILARIH (Settles & Craven, 2008) selects an = arg mAx / L0,-, (1r,
where
<s A)
def
Φ(x) ((x')
A
[<b()))
1l (0(x"))
''EA
INFORMATIONDENSITY (Settles & Craven, 2008) is defined as the multiplicative combina- tion of MAXENTROPY and COSINESIMILARITY:
CG arg max H[p(2:; 1) (L.,, #ES
where 3 > 0 controls the relative importance of both terms. We set B 1 in our experiments.
50

---

LEASTCONIUDECCE MAXDEST
MINMARGEN
UNDIRECTI İTL
UNSA
MNISTT
CIFAR 100
100
80
80-
60-
40-
20
60
40
76
Samplex from
10
25
40
Number of Samples
Number Butches Size 10
Figure 12: Comparison of "undirected" baselines for the experiment of Figure 4. In the MNIST experiment, UNSA and UNDIRECTED ITL coincide, and we therefore only plot the latter.
COSINESINILARTYY
INPONMATOONEENSTY
BADGE
MNIST
CIFAR-100
100
100
80
60
60-
60-
# Samples Support of
1100
1.50
60-
100
0-
Number of Samples
Number of Batches Size 10
Figure 13: Imbalanced Ps experiment.
17L.
CTL
CosmAASONmLARITY
INTORAATIINDENSSIT
BADGE
RANDOM
MNIST
CIFAR-100
100
100
Samplee Support
100
50
100
Number Samples
Number
Figure 14: Imbalanced ~ PA experiment.
51

---

112 500000
VIL (1
50000)
CTL (A 500000
RANDON
100
700
000
80
Sumples from Support
70
200
60-
40-
200
30
20
40
Number of Batches Size 10
Number of Batches of Size 10
Figure 15: Performance of VTL & choice of le in the CIFAR-100 experiment.
J.6
Additional experiments
We conduct the following additional experiments:
1. Imbalanced Ps (Figure 13): We artificially remove 80% of the support of PA from Ps. For example, in case of MNIST, we remove 80% of the images with labels 3, 6, and 9 from Ps. This makes the learning task more difficult, Pa is less represented in Ps. 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 PA (Figure 14): We artificially remove 50% of part of the support of PA while generating ~ 'PA 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 from A. case of CIFAR-100, we remove 50% of the images with labels (O...., 4} from A. We still observe the same trends 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 points which the decision rule is evaluated. Not surprisingly, 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 ~ Pa. We write p m/M. We generally observe that a larger p leads to better performance (with p = 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 ~ PA- Not surprisingly, we observe that the performance ITI. improves with larger M.
J.7 Ablation study of noise standard deviation
In Table 2, we evaluate the CIFAR-10W 100 experiment with different noise standard deviations p. 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 p is negligible.
52

---

ITC G DCG)
ITC (LL---0 0.1
ITC 1T
ITLi
MNIST
CIFAR-100
Accuracy
80
60
40
Samplls Suppoct F3
80
60-
40-
200
20-
40
00
Number of Samples
Number Butches of Size 10
Figure 16: Evaluation of the choice of m relative to the size M of A Pa. Here, m M
ITL (3 100
CTL 300
172. (M 100%
ITE (M 500)
100
700
90
000
70
600
Sumples From
000
10
200
30
20
00
40
Number of Butches Size 10
Number of Batches of Size 10
Figure 17: Evaluation of the choice of M, i.e., the size of A ~ PA. in the CIFAR-100 experiment.
Table 2: Ablation study of noise standard deviation in the CIFAR-100 experiment. We list the accuracy after 100 rounds per decision rule, with its standard error over random seeds. "(top-b)" denotes variants where batches are selected by taking the top-b points according to the decision rule rather than using batch selection via conditional embeddings. Shown in bold are best performing decision rules, and shown in italics results due to numerical instability.
P
0.0001
0.01
100
G-ITL
78.26 1.40
79.12
1.19
87.16 + 0.29
87.18
0.28
L-ITL
87.52 + 0.48
87.52 + 0.41
87.53 + 0.35
86.47 + 0.22
G-CTL
58.68 2.11
81.44 1.04
86.52 0.44
86.92 0.56
L-CTL
86.40 + 0.71
+6.38+0.75
86.00 + 0.69
84.78 + 0.39
G-ITL (top-6)
0.54
85.92 1.02
85.84 0.54
85.55 0.46
L-ITL (top-6)
85.44 0.58
$5.46
85.29 0.36
G-CTL (top-6)
$2.27+0.67
82.27 0.67
82.27 0.67
82.27 0.67
L-CTL (top-b)
50.73
4.673
80.73
80.73 0.68
BADGE
83.24 0.60
83.24 0.60
83.24=0.60
83.24 0.60
INFONIATIONDENSIITY
79.24 0.51
79.24
19.24
RANDOM
82.49 0.66
82.49 + 0.66
82.49 + 0.66
82.49 + 0.66
53

---

ITLA4
PAL-P
VIL-Aa 2d Task
VIL
ISE-BO
1d Task
Controller Tuning Quadcopter
1.0
Regnet
6
0.2
0.5
0.1
2
0.0
0-
0.0
Number of Iterations
1000
0
Number of Iterations
100
0
Number of Iterations
50
Figure 18: We perform the tasks of Figure 5 using Thompson sampling to evaluate the stochastic target space Pan- We additionally compare to GOOSE (cf. Appendix K.2.3) and ISE-BO (cf. Appendix K.2.4).
K Additional Safe BO Experiments & Details
In Appendix K.I, we discuss the use of stochastic target spaces in the safe BO setting. We provide 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.
K.1 More Exploitative Stochastic Target Space
Alternativeyy to the target space An. which comprises all potentially optimal points, evaluate the stochastic target space
PAn (.) IP( arg max f(x) = ID,)
(47)
=EX:g(=)20
which effectively weights points in An according how likely they are be the safe optimum, and is therefore more exploitative than the uniformly-weighte target space discussed so far. Samples from PAn can be obtained efficiently via Thompson sampling (Thompson, 1933; Russo et al., 2018). Observe that PAn is supported precisely on the set of potential maximizers An. We provide formal analysis of stochastic target spaces in Appendix E. Whether transductive active learning with A., or PAn 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 PAn can be obtained via Thompson sampling (Thompson, 1933; Russo et al., 2018). That is, in iteration + 1, we sample K N independent functions f(5 ~ D,, from the posterior distribution and select K points (1)) x(K) which are safe maximum of f()), f(),..., f(k), respectively.
Experiments In Figure 18, we contrast the performance of ITL with PAn to the performance of ITL with the exact target space A.. We observe that their relative performance is instance dependent: tasks that require more difficult expansion, ITL with A., converges faster, whereas simpler tasks (such as the 2d experiment), ITI. with PAn converges faster. We compare against the GOOSE algorithm (Turchetta et al., 2019) which 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 ITL with An and PAn: respectively, as well as SAFEOPT and GOOSE are illustrated in Figure 19. We observe that ITL with A, and SAFEOPT expand the safe set more "uniformly" since the set of potential maximizers encircles the true safe set.21 21 Intuitively, this is because the set of potential maximizers conservatively captures migh points might be safe and
2'This is because typically. there will always remain points in S. \ S. 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.
54

---

optimal. In contrast, ITL with PAn and GOOSE focus exploration and expansion in those regions where the objective is likely be high.
A
B
C
D
E
F
Figure 19: The first 100 samples of (A) ITL with A., (B) SAFEOPT, (C) ORACLE SAFEOPT, (D)
ITL with PAn (E) GOOSE, (F) ORACLE GOOSE. The white region denotes the pessimistic safe S100. 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")).
K.2 Detailed Comparison with Prior Works
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 real-world settings, this constant unknown and has to be estimated using the GP. This estimate is generally conservative and results in suboptimal performance. To this end, Berkenkamp al. (2016) proposed HEURISTIC SAFEOPT which relies solely on the confidence intervals the safe set, but lacks convergence guarantees. More recently, Bottero al. (2022) proposed ISE which queries parameters from S, that yield the most "information" about the safety of another parameter in X. Hence, ISE focuses solely the expansion of the safe S,, 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). 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.3 Similar SAFEOPT, their method aims expand the safe in all directions including those that known to be suboptimal. In contrast, ITL directs expansion only towards potentially optimal regions.
Lipschitz constant of g*. which is assumed to be known. In most
to expand
In the 1d task and quadcopter experiment (cf. Figure 5), observe that SAFEOPT and ORACLE SAFEOPT converge significantly slower than I'T'. to the safe optima. We believe this is due to their conservative Lipschitz-contiiuttygghe smoothness-basee expansion, as opposed ITL LL's expansion,
We provide empirical evaluation in Appendix K.2.4.
55

---

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 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 does not take into account the objective, and purely aims to expand the safe set. ITL, on the other hand, balances expansion and exploration.
K.2.1 SAFEOPT
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 be safe points by assuming knowledge of an upper bound L; to the Lipschitz constant of the unknown constraints g. 23 In each iteration, the (pessimistic) safe set Sn, is updated to include all points which can be reached safely (with respect to the Lipschitz continuity) from known-to-be-saf point æ E Sn. Formally.
SAFROPT def
U {Ør EX IESS
(48)
(x,(()) - Li - 222 2 0 for all i I.).
The expansion of the safe set illustrated 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 (ef. 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 maximizers
M SAFUOPT {x SSAFOOPT
Un (n)
max
(x))
o' ESSnNO
which contains all known-to-be-safe points which are potentially optimal. Note that if Sh SSAFFOFT S, then SAFEOOP C An, since A, contains points which are potentially optimal and potentially safe but possibly unsafe.
To facilitate expansion, for each point x E Sn, the algorithm considers a set of expanding points
TSAFROPT (ar) def (ar' X SSFRROPT
Un,;(x)) (x) L - æ'122 for all i I.}
A point is expanding if it is unsafe initially and can be (optimistically) deduced safe by observing x. The set of expanders corresponds to all known-lo-be-sue points which optimistically lead to expansion of the safe set:
G SArRORT def fxr Sn [F)) 0}.
That is, an expander a safe point which is "close" to at least one expanding point w'. Observe that here, we start with safe x and then find a close and potentially safe x' using the Lipschitz-propent propeety 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 &,, (cf. Equation (27)):
AAAFOPPT Lemma K.1. For any n 2 0. if S
S,, then
U
J SAFEOPT (x) E
DES.
Recall that due to the assumption that ||g| ll co. of is indeed Lipschitz continuous.
56

---

S¹ *
Figure 20: Illustration of the expansion of the safe set à la SAFEOPT. 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 æ and then extrapolating using the Lipschitz constant (cf. Equation (48)). The dashed orange line denotes the expanding points of SAFEOPT which appr-xappr the optimistic safe of ITL (cf. Lemma K.1). Thus, ITL may even learn about points S which are "out reach" for SAFEOPT.
Proof. Without loss of generality, consider the case where I. = {i]. We have
En S, S, = fx E X' \ Sn, un (x) 2 0}. The result follows directly by observing that T. || a'112 0.
SAFEOPT then selects In+1 according to uncertainty sampling within the maximizers and expanders: MS U GAARROPT We remark that due to the separate handling of expansion and exploration, SAFEOPT expands the safe set in all directions 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..
even those that are known to be suboptimal.
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, which minimizes the posterior uncertainty within An Note that the two approaches not identical typically MSAFEÜPT J G.AFFOPTT S SSAFEOPT and An, 2 Sn.
We show empirically in Section 3.3 that depending on the kernel choice (i.e., the smoothness assumptions), uncertainty sampling within 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 be equally informative as points inside.
Finally, note that the set of expanders is constructed "greedily", i.e., only considering single-step expansion. This 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 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 reducing epistemic uncertainty at points with small aleatoric uncertainty. In contrast, maximizing mutual information naturally takes
2'e use of uncertainty sampling for safe sequential decision decision-making goes back to Schreiter et al. (2015) and Sui et al. (2015).
57

---

into account the two sources of uncertainty, preferring those points where epistemic uncertainty is large and aleatoric uncertainty is small (cf. Appendix C.1).
Suboptimal reachable safe set Sui et al. (2015) and Berkenkamp et al. (2021) show that SAFFOPT converges the optimum within the closure R. R.AEEOTTSSS of
RS SAFFOOTT (S) def = S fo E X' Ex' E S such that
fa'a - (L, 2'122 e) 2 0 for all I.}.
Note that analogously to the expansion of the safe set, the "expansion" of the reachable safe set is based on "inferring safety" through a reference point in 8 and using Lipschitz continuity. This is opposed to the reachable safe set of ITL (cf. Definition C.29).
We remark that under the additional assumption that Lipschitz constant is known, ITL can easily be extended to expand its safe set based on the kernel and the Lipschitz constant, resulting in a strictly larger reachable safe set than SAFEOPT. We leave the concrete formalization of this extension to future work. Moreover, we do not evaluate this extension our experiments, as we observe that even without the additional assumption of a Lipschitz constant, ITL outperforms SAFEOPT in practice.
K.2.2 HEURISTIC SAFEOPT
Berkenkamp et al. (2016) also implement heuristic variant of SAFEOPT which does not assume known Lipschitz constant. This heuristic variant uses the same (pessimisticc) safe sets S, as ITL. The set of maximizers is identical to SAFFOPT. As expanders, the heuristic variant considers all safe points S, that if x were be observed next with value u. (x) lead to |S,+1l > |s,]. We refer to this set as C--AARROPT The next point is then selected by uncertainty sampling within M. U-
The heuristic variant shares some properties with SAFEOPT, such that it is based on uncertainty sampling, not adapting to heteroscedastic noise, and separate notions of maximizers and expanders (leading to an "undirected" expansion of the safe set). Note that there are no known convergence guarantees for heuristic SAFEOPT. Importantly, note that similar to SAFEOPT the set of expanders constructed "greedily", and in particular, does only take into account single-step expansion. In contrast, objective such as ITL which quantifies the "information gained towards expansion" also actively seeks out multi-step expansion.
K.2.3 GOOSE
To address the "undirected" expansion of SAFEOPT discussed in the previous section, Turchetta et al. (2019) proposed goal-oriented safe exploration (GoOSE). GoOSE extends any unsafe BO algorithm (which we subsequently call an oracle) to the safe setting. In our experiments, we evaluate GOOSE-UCB which uses UCB oracle and which is also the variant studied by Turchetta et al. (2019). In the following, we assume for ease of notation that I. = [c).
Given the oracle proposal x², GoOSE first determines whether x is safe. If x is safe, x" is queried next. Otherwise, GOOSE first learns about the safety of x* by querying "expansionist" points until the oracle's proposal is determined to be either safe or unsafe.
GoOSE expands the safe set identically SAFEOPT according Equation (48). In the context of GoOSE, SSAFBOPT called the pessimistic safe set. To determine that a point cannot be deduced as safe, GoOSE also keeps track of Lipschitz-based based optimistic safe set:
GUOOSE def
U fo' E E SESSARIO
u - Lelloc - 222122 - - 0}.
We summarize the algorithm in Algorithm 2 where we denote by O(x)) the oracle proposal over the domain X.
remains to discuss the heuristic used to select the "expansionist" points. GOOSE considers all points æ S SAFFOOFT with confidence bands of size larger than the accuracy e, i.e.
GooSE def
nLe = {x E Sy,
SAFEOPT
Un,o(x) (n,e(0) > e).
58

---

Algorithm 2 GOOSE
Given: Lipschitz constant Le. prior model {ff got. oracle O, and precision
Set initial safe set Si SSAFEOFT based on prior
SGoOSE < X
-n.c
n 1--0
for l from 1 to do zx + O(SROOSE)
while o & SSAAEOPT do
Observe "expansionist" point 11+1, set n. <- n + and update model and safe sets end while
Observe Fig, set t- n + 1, and update model and safe sets
end for
Which of the points in this set is evaluated depends on set of learning targets A def SCoOSE nn, S SSAFROFt akin to the "potential expanders" En (cf. Equation (27)), to each of which we assign priority h(z). When h(x) is large, this indicates that the algorithm is prioritizing to determine whether æ is safe. We use as heuristic the negative f didittnec between æ and x". GoOSE then considers the set of potential immediate expanders
gooos del {a: E WGGoos Ra' E AAooSE with
priority a such that "n,.((r) Lellar x' ll2 2 0}-
The "expansionist" point selected by GoOSE is then any point in gGooSE (a²) where a* denotes the largest priority such that Gu (a*)) > O.
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 single oracle proposal x" is safe may take significant time. Consider the (realistic) example where the prior is uniform, and UCB proposes point which is far away from the safe set and suboptimal. GOOSE will typically attempt derive the safety of the proposed point until the uncertainty at all points within S5 SSAFEOPT is reduced to c. 25 Thus, GOOSE can "waste" a significant number of samples, aiming expand the safe set towards 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 suboptimal point for significant number of rounds.
K.2.4 ISE and ISE-BO
Recently, Bottero et al. (2022) proposed an information-theerrtie approach to efficiently expand the safe set which they call informationn-hhorettee safe exploration (ISE). Specifically, they choose the next action In by approximating
arg max [(1
O): Dnn
(ISE)
#ES.-1 x'eX
(w)
In a parallel independent work, Bottero et al. (2024) extended ISE to the Safe BO problem where they propose to choose &n according
arg max max ISE (xE) a MES (x))
(ISE-BO)
wES.
where a MES denotes the acquisition function of max-value entropy search (Wang & Jegelka, 2017). Similarly to SAFROPT, 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 known to suboptimal. In contrast, ITL balances expansion and exploration through the single set of potential maximizers An, With stochastic target space, ITL generalizes max-value entropy search (cf. Appendix K.1).
We evaluate ISE-BO 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.
Thiss is because the proposed point typically remains in the optimistic safe set when it is sufficiently far away from the pessimistic safe set.
59

---

Figure 21: The ground truth /* is shown as the dashed black line. The solid black line denotes the constraint boundary. The GP prior is given by a linear kernel with sin-transform and mean 0.1æ. The light gray region denotes the initial optimistic safe set So and the dark gray region denotes the initial pessimistic safe set Su-
15-
14-
05
0.0
-15.0
-75
-3.0
-2.
7.5
13.0
-10.
-7.9
-3.0
10.0
Figure 22: First 100 samples of ITL using the potential expanders E, (cf. Equation (27)) as target space (left) and SAFEOPT sampling only from the set of expanders GSAPROPT (right).
K.3 Jumping Past Local Barriers
In this additional experiment demonstrate that ITL is able to extrapolate safety beyond local unsafe "barriers", which is 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-ben based methods that they never "jump past local barriers", even if the oracle Lipschitz constant were to be known and tight (i.c., locally accurate) around the barrier. This is be- cause Lipschitz-basee based methods expand to the point based on reference point x', and by definition, x is added to the safe set so are all points on the line segment between æ and x'. Hence, there is a single point this line segment which is unsafe (i.e., "barrier"), the algorithm will never expand past it. This limitation does not exist for kernel based algorithms as expansion occurs function space.
Moreover, note that for non-stationary kernel such as in this example, ITL samples the "closest points" in function space rather than Fuclidean space. We observe that SAFEOPT still samples "locally at the boundary" whereas ITL samples the most informative point which in this case is
60

---

Mean
Ground Truth uncertainty
Safety Boundary
Figure 23: Ground truth and prior well-calibrated model in 1d synthetic experiment. The function serves simultancously as objective and as constraint. The light gray region denotes the initial safe set So.
ORACLE SAPBOPT
SAFEOPT
1d Task
Size of S.
200
100
200
400
600
800
1000
Number of Iterations
Figure 24: Size of S,, in 1d synthetic experiment. The dashed black line denotes the size of S*. In this task, "discovering" the optimum is closely linked to expansion of the safe set, and HEURISTIC SAFEOPT fails since it does not expand the safe set sufficiently.
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 more capable to exploit nonnstationary) 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,, for the compared algorithms, which in this experiment matches the achieved regret closely.
2d task We model our constraint in the form of spherical "island" where the goal is to get 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. We discretize using 2 500 points.
61

---

Orjertie
Condra ot
15
76
35
Figure 25: Ground truth in 2d synthetic experiment.
K.4.2 Safe Controller Tuning for Quadcopter
Modeling the real-world dynamics We learn feedback policy (i.e., "control gains") to compen- sate 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),
(x())) def - (x* - ==(((=* 81) (8* -,)],
(49)
where xx the unknown ground truth disturbance parameters, and s* and 8* are the desired state and state derivative, respectively. This yields the following ground truth dynamics:
$1+1(x) T(s ut 5x())).
(50)
The feedback parameters [ap Id] can be split into Tp tuning the state difference which are called proportional parameters and Dg tuning the state derivative difference which are called derivative parameters. We use the "critical damping" heuristic derivative parameters: æg = Ep. We thus consider the restricted domain each dimension corresponds to the proportional feedback to of the four rotors.
relate the proportional and
[0, 20 where
Ground truth disturbance parameters are sampled from a chi- thuusq distribution with one degree of freedom (i.e., the square of a standard normal distribution), s x². and æt is determined according to the critical damping heuristic.
The learning problem The goal of our learning problem to move the quadcopter from its
initial position s(0) [1 1] (in Euclidean space with meter unit) position [0 Morcover, 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:
T
(x)) def
Σ
||s 81 (x)) + 1| - u. (x))
(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 a linear-quadratee regulator (LQR) which we solve exactly for the undisturbed system using ILQR (Tu et al., 2023). Finally, want ensure at all times that the quadcopter is least 0.5 meter above the ground, that is,
g (ar)
def min 8 (ar) 0.5
(52)
T
where we denote by of the z-coordinate of state
We time horizon of T seconds which discretize using 100 steps. The objective is modeled by a zero-mean GP with a Matérn(z = 5/2) kernel with lengthscale 0.1, and the constraint is modeled by GP with mean -0.5 and Matérn(I 5/2) kernel with lengthscale 0.1. The prior obtained by single observation of the "safe seed" [0 0 10]
62

---

Adaptive discretization We discretize the domain X' adaptively using coordinate LINEBO (Kirschner 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, 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 p 0.1. We let 10. The control target u² [1.766 0 O]T
The state space is 12-dimensional where the first three states correspond to the velocity of the quadcopter, the next three states correspond 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 LQQ parameters are given by
diag 1,,,,,, 0111111111010100000100111111111, and
R = 0.01 diag (5, 0.,,0,,.00 0.8, 0.3}.
The quadcopter simulation was adapted from Chandra (2023).
Each onc-dimensional subspace discretized using 2000 points.
Random seeds We repeat the experiment for 25 different seeds where the randomness is over the ground truth disturbance, observation noise, and the randomness the algorithm.
On average, 1.6 iterations of the first 50 violate the constraints.
63

---

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 of Vakili et al. (2021). The notation O(-) subsumes log-factors. For 1/2, the Matérn kernel is equivalent the Laplace kernel. For oc, the Matérn kernel is equivalent to the Gaussian kernel. The functions sampled from Matérn kernel are [v] mean square differentiable. The kerncl-agnostic bound follows by simple reduction linear kernel in X dimensions.
Kernel
k(ar,ar"
In
Linear
x T xx'
((dlog()
x Ce--a xe'l 11
Gaussian
exp
21
δ log u+ (ni)
Laplace
exp
x x' h
δ r log tro log (n)
Matérn
21-2 [(p)
22r x=xx' x
By
V2r
δ
n natta log ait (n)
h
any
0 log(n))
64

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
65

---

Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
The code is publicly available.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
66

---

Answer: [Yes]
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm cc/
Seerides/CooSSubmiise www.miissssopolioioooooooooeoiee icy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: /CodeSubmic / //iips.co.. //nip..c wttpccccpppccccceeececccccccccct / ssissssilllll onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
See the extensive discussions in the appendices.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
67

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
All individual experiments require only small compute resources.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: h/w/eeeurpp...e httpp///c.p.......ccccciiieeeee.
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
This paper presents work whose goal is to advance the field of Machine Learning. There many potential societal consequences of work, none which we feel must be specifically highlighted here.
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
68

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is 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 being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have 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 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 best faith effort.
12. Lieenses 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 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 URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.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, paperswi thcode. com com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of 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.
69

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
70


Reviews:
[{"review_id": "zu2lNPYUdp", "reviewer": "Reviewer_WV1c", "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. \nThe 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.", "questions": "Q1: What’s the difference between $\\gamma_n$ and  $\\gamma_{\\mathcal{A},\\mathcal{S}}(n).$ These notations can be improved.  \nQ2: If only the target space is (uncountable) separable space, can the theorem have any change?", "limitations": "Not well-discussed", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Among many advantages, the theoretical aspect is better because it can provide the criteria for the use of kernels that are strongly connected to the tuning of the algorithms. Also, the applications are impressive and enlarging the area of active learning. The use of GP is solid because it can provide a solid mathematical background and reliable uncertainty in many cases, compared to variational Bayes approaches.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and detailed comments! You can find below our response to some of your questions. Please let us know if you have any further concerns or suggestions.\n\n> Among many advantages, the theoretical aspect is better because it can provide the criteria for the use of kernels that are strongly connected to the tuning of the algorithms. Also, the applications are impressive and enlarging the area of active learning.\n\nThank you!\n\n## Concerns\n\n> 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.\n\nThank you for pointing this out!\nOur paper introduces *transductive* active learning (TAL), where instances are specified by a target space $\\mathcal{A}$ and a sample space $\\mathcal{S}$.\nThe \"classical\" (*inductive*) active learning (we will call it IAL in the following) that is studied in most prior works on active learning is the special case of TAL where $\\mathcal{A} = \\mathcal{S}$.\nThat is, intuitively, in IAL one tries to learn \"everything\" which amounts to extracting as much information as possible.\nIn contrast, in TAL, learning *can* be directed to a particular region of the domain.\nThis is also why the special case of IAL seems most useful for pre-training (and it has been studied extensively in this setting), while TAL unlocks various applications of active learning for fine-tuning.\n\nWe allude to this in lines 84-86 where we show that in the classical IAL setting, ITL is equivalent to CoreSet which is a standard baseline.\nSo if one were to apply the methods proposed here in the IAL setting, one would recover the existing results.\nThis goes to show that our proposed algorithm is in fact *more general* than prior approaches since it does not only address IAL but also the more general TAL.\nTo argue for the advantages of TAL over the limited view of IAL, we therefore focus our experiments on novel applications of TAL.\nAs you rightly point out, IAL has already been extensively studied, and TAL unlocks many new applications of active learning.\n\n> $\\gamma_n$’s sub-linearity can be clarified as the mathematical formula.\n\nThank you for this suggestion. We updated the paper to more prominently pointing out that in most cases (including all instances where the domain is finite), $\\gamma_n$ is always sub-linear.\n\n> In GP, the kernel is essential, and the experiments can reveal what kernel is best or robust. The discussion about kernels is too short.\n\nThank you also for this suggestion.\nKernels are discussed extensively in other resources (e.g., the kernel cookbook [1]).\nGiven the limited space in the submission, we opted to not include an extensive discussion on kernels, beyond the extensive discussion in section 4, lines 182-194.\nWith the additional page of the camera-ready version, we are able to extend this discussion slightly and reference background resources.\n\n> Limitations: Not well-discussed\n\nThe main limitation of this work is that we focus solely on sequential decision-making *given* some model, rather than asking how one should construct such a model so that it is representative of the ground truth.\nWe implicitly address this scope in lines 12-13.\nKindly let us know of any other potential limitations, and we would be more than happy to address them.\n\n## Questions\n\n> Q1: What’s the difference between $\\gamma_n$ and $\\gamma_{\\mathcal{A}, \\mathcal{S}}(n)$?\n\n$\\gamma_n = \\max_{\\substack{X \\subseteq \\mathcal{X}}, |X| \\leq n} \\mathrm{I}(f_{\\mathcal{X}} ; y_{X})$, whereas $\\gamma_{\\mathcal{A},\\mathcal{S}}(n) = \\max_{\\substack{X \\subseteq \\textcolor{red}{\\mathcal{S}}}, |X| \\leq n} \\mathrm{I}(f_{\\textcolor{red}{\\mathcal{A}}} ; y_{X})$.\n$\\gamma_n$ is used extensively in prior literature that studies inductive active learning. The definition of $\\gamma_{\\mathcal{A},\\mathcal{S}}(n)$ is motivated by the fact that transductive active learning is *generalizing* inductive active learning where $\\mathcal{X} = \\mathcal{A} = \\mathcal{S}$.\nIn the inductive case, $\\gamma_n = \\gamma_{\\mathcal{A},\\mathcal{S}}(n)$.\nIn other transductive cases, it can be that $\\gamma_{\\mathcal{A},\\mathcal{S}}(n) \\ll \\gamma_n$.\n\n> Q2: If only the target space is (uncountable) separable space, can the theorem have any change?\n\nInfinite (but 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 [2]).\nThat is, if the target space can be covered approximately using a finite set of points, Theorems 3.2 and 3.3 extend directly.\n\n---\n\nWe believe that our work is highly relevant since (1) it generalizes widely studied approaches to IAL while (2) unlocking entirely new promising applications of active learning where the use of prior approaches was limited.\n\nHaving addressed all of the questions provided by the reviewer, and given the contributions of this paper, we hope that our answers prompt the reviewer to reconsider their evaluation and potentially increase their score. We would be happy to answer any remaining questions or concerns.\n\n---\n\nReferences:\n1. Kernel cookbook. https://www.cs.toronto.edu/~duvenaud/cookbook/.\n2. Srinivas, Niranjan, et al. ”Gaussian process optimization in the bandit setting: No regret and experimental design.” ICML (2010).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wWYDEuanol", "reviewer": "Reviewer_4uNa", "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.", "questions": "1. How does the computational cost of the methods fare in practice to other methods?", "limitations": "Yes", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well-written and organized, with ample thorough discussions.\n- The problem of transductive active learning is novel to the best of my knowledge and may be of interest to the broader ML community.\n- Compelling empirical results are provided that support the theoretical results of the paper.", "weaknesses": "- The paper is quite dense and long, with a total of 68 pages when appendices are considered.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our paper! Please find our response to your question.\nPlease let us know if you have any further\nconcerns or suggestions.\n\n> - The paper is well-written and organized, with ample thorough discussions.\n> - The problem of transductive active learning is novel to the best of my knowledge and may be of interest to the broader ML community.\n> - Compelling empirical results are provided that support the theoretical results of the paper.\n\nThank you!\n\n> How does the computational cost of the methods fare in practice to other methods?\n\nITL scales cubically in the size of the target space $\\mathcal{A}$ since it takes into account mutual interaction between prediction targets.\nIn contrast, VTL scales in linearly in size of $\\mathcal{A}$.\nWe included a more detailed analysis of the computational complexity in Appendix G.\nIn all our experiments, the computational cost of ITL \\& VTL is around the cost of the fastest baselines, since for these computationally light methods cost tends to be dominated by computing the kernel / the embeddings.\n\n---\n\nWe are glad to see the recognition that transductive active learning can be of interest to the broader ML community, given that it unlocks new applications of active learning.\nHaving addressed the remaining question provided by the reviewer, and given the contributions of this paper, we hope that the reviewer considers to increase their score for our paper. We would be happy to answer any remaining questions or concerns.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Waxd4gmt34", "reviewer": "Reviewer_aHJz", "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.", "questions": "N/A", "limitations": "N/A", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is well written and clearly structured with novel contributions in generalization bounds. It provides sufficient theoretical analysis for specific acquisition functions in active learning with experimental results on some datasets.", "weaknesses": "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. \nSecond, 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our paper! We also very much appreciate the quick response to our follow-up question. You can find below our response to some of your questions. Please let us know if you have any further concerns or suggestions.\n\n> The paper is well written and clearly structured with novel contributions in generalization bounds. It provides sufficient theoretical analysis for specific acquisition functions in active learning with experimental results on some datasets.\n\nThank you!\n\n## Concerns\n\n> 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.\n\nWe chose image classification as a testbed *precisely because* it is widely studied.\nTo the best of our knowledge, MNIST and CIFAR are common tasks for evaluation of active learning [1-3] as well as other works on fine-tuning [e.g., 4].\nGiven that baselines and benchmarks on active learning have been using image classification as testbeds, we intend with this choice to compete against the strongest possible baselines.\n\nThis being said, we strongly agree that applying VTL to other domains (for example, fine-tuning of LLMs) is a very exciting research direction, which we intend to pursue in future work.\n\n> 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.\n\nWe agree that the results might not extend directly to LLMs, and that this is an exciting direction for further research.\nCan you point us to the claim that \"our results improve prompt optimization\"?\nWe did not intend to make this claim.\nIn lines 251-256, we address *model optimization* (i.e., \"fine-tuning\" model weights, like we do here with vision experiments) and suggest that our work opens up this direction of future work.\n\n### Related work on Inductive Active Learning\n\nWe would like to emphasize that Section 4 specifically addresses the (transductive) transfer setting, where we fine-tune to a specific set of (out-of-distribution) examples. This is different from the canonical application of (inductive) active learning to pre-training or fine-tuning without distribution mismatch.\nWe compare against around 10 of the most widely used inductive active learning strategies.\nYou can find the comparison to all baselines in Section J.5.\nOur experiments show that we outperform *all inductive baselines significantly*.\nWe believe that this constitutes a comprehensive evaluation of approaches to inductive active learning, and shows the advantage of transductive active learning.\nWe do not expect any alternative inductive methods to perform dramatically better since they do not take the distribution shift into account.\n\n### Related Work on Influence Functions\n\nThank you for pointing out this line of work!\nIn particular, [5] which was published at ICML 2024, is relevant to the transfer setting we also consider in Section 4.\n\nThe following is a brief comparison between our work and the influence functions line of work:\n- We remark that the selection strategy of [5] is the same as the \"CosineSimilarity\" baseline considered in our experiments, when loss gradient embeddings (cf. Section J.2) are used (and SGD is the used optimizer). We show in our experiments that VTL substantially outperforms CosineSimilarity when the batch size is larger than one.\n- A major limitation of the line of work on influence functions, including [5], is that interactions between samples are not taken into account. That is, the selected samples are not diverse and may contain redundant information. We suspect that this is the main reason why VTL substantially outperforms these methods. [5] discuss this in their limitations.\n    VTL offers an efficient and effective approach to take interactions between samples and account: synthesizing approaches to retrieve *relevant* examples (e.g., CosineSimilarity) and approaches to retrieve *diverse* examples (e.g., inductive active learning).\n- A drawback that [5] points out in Appendix I is that a smaller loss does not always lead to a higher accuracy. Perhaps the loss is therefore not the right proxy goal. In contrast, VTL directly minimizes the bound on the approximation error from Theorem 3.3.\n- VTL also takes into account points with a high negative cosine similarity; something that [5] suggests in Appendix K.2.\n\nWe will include this comparison to the influence functions line of work in our section \"Related Work\".\n\n---\n\nWe hope to have addressed the concerns raised by the reviewer.\nGiven the recognized contributions that unlock new applications of active learning, and that the application in Section 4 offers a natural and effective way to select both *relevant and diverse* points, we would appreciate it if the reviewer would increase their score for our paper. We would be happy to answer any remaining questions or concerns.\n\n---\n\nReferences:\n1. Gal, Y., Islam, R., and Ghahramani, Z. Deep bayesian active learning\nwith image data. In ICML, 2017.\n2. Zhang, Jifan, et al. Labelbench: A comprehensive framework for benchmarking adaptive\nlabel-efficient learning. 2023.\n3. Lüth, Carsten, et al. Navigating the pitfalls of active learning evaluation: A systematic framework\nfor meaningful performance assessment. In NeurIPS, 2023.\n4. Wei, A., Hu, W., and Steinhardt, J. More than a toy: Random matrix models predict how real-world neural representations generalize. In ICML, 2022.\n5. Xia, Mengzhou, et al. ”Less: Selecting influential data for targeted instruction tuning.” In ICML, 2024.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gknJCBdCjJ", "reviewer": "Reviewer_yyUG", "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.", "questions": "In addition to issues in the Weaknesses section, a few questions:\n\n- For Section 4, \n  - is there any existing Bayesian active learning algorithms that can be used as baselines in this setup?\n  - 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?\n  - How do you choose hyperparameters for the baselines?\n\n- For section 5, I'm not familiar with this task, but in my opinion, it does not provide enough details and explanations. For example\n  - 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.\n  - In line 317-318, \"VTL minimizes marginal variances, .. which are decisive for expanding the safe set\". Why?", "limitations": "N/A", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- This paper considers a practically relevant setup of active learning. \n\n- The paper is mostly written clearly.\n\n- The proposed methods are sound. It gives both theoretical guarantees and empirical evaluation.", "weaknesses": "- My major concern is novelty and significance:\n  - 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. \n  - 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.\n\n--------\nI'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.\n\nApart 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our paper! Please find our detailed responses to the concerns raised.\nPlease let us know if you have any further concerns or suggestions.\n\n## Concerns\n\n> 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.\n\nThank you for pointing this out.\nWe do not claim to be the first to propose ITL or VTL (line 82 and lines 333-342).\nHowever, we are the first to show convergence guarantees.\nAs we show in Section 3.3, on transductive instances (where $\\mathcal{A} \\not\\subseteq \\mathcal{S}$), our proposed methods differ substantially from the widely recognized inductive methods (e.g., uncertainty sampling) that have been derived based on the same idea of \"minimizing posterior uncertainty\".\nIn our view, the fact that the proposed sample strategy is a natural choice can be seen as an advantage over baselines.\n\n> 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.\n\nNone of the prior works studying ITL and VTL derive convergence guarantees related to Theorems 3.2 and 3.3.\nSimilar convergence guarantees were only known for the special case where $\\mathcal{A} = \\mathcal{S}$.\n\nCore to our analysis are Theorems C.12 and C.13, where we use the approximate monotonicity of the marginal gains and the chain rule of information gain to derive a convergence rate of the marginal gains.\nThe main technical challenge and novelty of our generalization bounds lies in the definition and proof of existence of \"approximate Markov boundaries\" (see Definition C.15 and Section C.6.1).\n\nAn interesting insight from our bounds is that they shrink with $\\gamma_{\\mathcal{A}, \\mathcal{S}}(n)$ (as opposed to $\\gamma_n$ of inductive approaches).\nThe information capacity $\\gamma_{\\mathcal{A}, \\mathcal{S}}(n)$ of the target space can be *significantly* smaller than the total information capacity across a large domain $\\mathcal{X}$.\nWe observe this empirically in our experiments, where we show that inductive active learning methods are vastly less efficient than ITL/VTL when prediction targets are known.\n\nWe will expand the discussion of the contributions and implications of our new theoretical results, given the additional available page in the camera-ready version.\n\n## Questions\n\n1. The most common (inductive) active learning baseline is \"uncertainty sampling\".\nWe compare against this baseline in Section J.5 (Figure 11) alongside many additional baselines.\n\n2. $\\mathcal{P}\\_{\\mathcal{A}}$ is the data-distribution limited to the target labels (see footnote 5 on page 6).\nWe say that a sample is in the support of $\\mathcal{P}\\_{\\mathcal{A}}$ if its label is one of the target labels (e.g., in $\\\\\\{0, \\dots, 9\\\\\\}$ in case of CIFAR-100).\nThe sample space $\\mathcal{S}$ includes images with such labels.\nHowever, the set of images in $\\mathcal{A}$ is not in $\\mathcal{S}$ (i.e., their labels are not known).\nMethods that sample many points from the support of $\\mathcal{P}\\_{\\mathcal{A}}$ are able to retrieve the relevant data from $\\mathcal{S}$.\nWe discuss the relevance of this particular setting and also evaluate the alternative setting $\\mathcal{A} \\subseteq \\mathcal{S}$ in Appendix I.\n\n3. We discuss all baselines in detail and specify their hyperparameters where applicable in Appendix J.5.\nWe use the author's implementations where applicable (e.g., for TypiClust and ProbCover).\nWe have included all of our code required to reproduce the results in the supplementary material and intend to make it public upon publication.\n\n4. We use the proposed methods for transductive active learning (ITL and VTL) with the specified target space $\\mathcal{A}_n$ and sample space (i.e., pessimistic safe set) $\\mathcal{S}_n$ (lines 277-278).\nYou are absolutely right in pointing out that $\\mathcal{A}_n$ can be unsafe.\nHowever, by definition, all of the sample space is safe with high probability.\nExtrapolating *outside* of $\\mathcal{S}_n$ to those targets in $\\mathcal{A}_n$ that are unsafe is precisely what we employ in our proof of Theorem 5.1.\nIn this way, and unlike prior work, ITL \\& VTL can address the expansion and exploration simultaneously.\n\n5. VTL quantifies \"uncertainty\" by the marginal variances of predictions. As such, VTL greedily minimizes the marginal variances.\nThe pessimistic safe set is defined as $\\mathcal{S}_n = \\\\\\{x \\mid l_n(x) \\geq 0\\\\\\}$ where the lower confidence bound is roughly the mean minus the standard deviation (see eq. (25) in Section C.8).\nThat is, minimizing the variance at $x$ is the most effective way of determining whether $x$ can be added to $\\mathcal{S}_n$ or not.\n\n>I'm not familiar with this task, but in my opinion, it does not provide enough details and explanations.\n\nGiven the limited space in the main body of the paper, we had to extract some of the background and details to the appendix.\nWe include an extensive discussion of the relevant background in Appendix K.2.\n\n---\n\nWe hope to have addressed the reviewer's concern regarding the novelty of our paper, which \n1. introduces a new problem setting generalizing classical inductive active learning,\n2. derives novel convergence guarantees for a natural family of algorithms, and\n3. shows the superior performance of these algorithms on two new applications of active learning (unlocked by the generalized problem setting) as compared to the state-of-the-art.\n\nWe would appreciate it if the reviewer would increase their score for \"contribution\" and their overall score for our paper. We would be happy to answer any remaining questions or concerns.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all reviewers for their feedback, and would like to emphasize the novel contributions of our work.

1. We introduce a new problem setting generalizing classical inductive active learning. All reviewers appear to agree that this new problem setting is relevant and unlocks several new applications of active learning.
2. We derive convergence guarantees for a natural family of algorithms (which recover widely recognized approaches such as "uncertainty sampling" for the inductive special case).
3. We show that these algorithms achieve a significant improvement upon the state-of-the-art in two new applications of active learning (unlocked by the generalized problem setting).
In both applications, the use of active learning leads to a unique advantage over prior work: Synthesizing *relevance & diversity* when sampling in Section 4; Synthesizing *expansion & exploration* when sampling in Section 5.

We believe that transductive active learning is a powerful paradigm for learning under resource constraints.
As noted by the reviewers, this work opens up the possibility to study many other applications of transductive active learning, such as efficient data selection for fine-tuning LLMs (reviewer aHJz).

Meta-review: 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.
Decision: Accept (poster)