Density-Aware Farthest Point Sampling
Authors: Paolo Climaco
Jochen Garcke
Venue: Accepted by TMLR ()

Abstract: We focus on training machine learning regression models in scenarios where the availability of labeled training data is limited due to computational constraints or high labeling costs. Thus, selecting suitable training sets from unlabeled data is essential for balancing performance and efficiency. For the selection of the training data, we focus on passive and model-agnostic sampling methods that only consider the data feature representations. We derive an upper bound for the expected prediction error of Lipschitz continuous regression models that linearly depends on the weighted fill distance of the training set—a quantity we can estimate simply by considering the data features. We introduce ``Density-Aware Farthest Point Sampling'' (DA-FPS), a novel sampling method. We prove that DA-FPS provides approximate minimizers for a data-driven estimation of the weighted fill distance, thereby aiming at minimizing our derived bound. We conduct experiments using two regression models across three datasets. The results demonstrate that DA-FPS significantly reduces the mean absolute prediction error compared to other sampling strategies.

Published in Transactions on Machine Learning Research (02/2026)
Density-Aware Farthest Point Sampling
Paolo Climaco"
ciimacopuoloo@gmaal.com
Institut für Numerische Simulation, Universität Bonn, Germany Department of Mathematics, University of California, Los Angeles, USA
Jochen Garcke
garcke uni ani-bornn.ce
Institut für Numerische Simelaaiin,, Universität Bonn, Germany Praunhofer SCAI, Sankt Augustin, Germany
Reviewed on OpenReview: Atips: // openreview. net/ pormfo id= uII471gffY
Abstract
We focus on training machine learning regression models in scenarios where the availabil- ity of labeled training data is limited due to computational constraints or high labeling costs. Thus, selecting suitable training sets from unlabeled data essential for balancing performance and efficiency. For the selection of the training data, we focus on passive and agnost sampling methods that only consider the data feature representations. We derive upper bound for the expected prediction error of Lipschitz continuous regression models that linearly depends on the weighted fill distance of the training set quantity we can estimate simply by considering the data features. We introduce "Density- Aware Farthest Point Sampling" (DA-FPS), a novel sampling method. We prove that DA-FPS provides approximate minimiizers for a data-driven estimation of the weighted fill distance, thereby aiming at minimizing our derived bound. We conduct experiments using two re- gression models across three datasets. The results demonstrate that DA-FPS significantly reduces the mcan absolute prediction error compared to other sampling strategies.
1 Introduction
Machine learning regression aims predict continuous numerical values based on input features by learning the underlying prediction patterns from labeled training data. Data quality and data selection crucial for developing and deploying effective regression models. Without sufficient or reliable data, ML regression models cannot perform well: too little data leads to poor learning, and biased or corrupted data results in inaccurate predictions. This work addresses challenges related to the limited availability of labeled training data, often resulting from computational constraints and high labeling costs. These challenges frequently occur in scientific applications, where labeling typically relies on expensive numerical simulations or labora- tory experiments. Our work is motivated by molecular property prediction. The chemical compound space is large. It is estimated to contain over 1050 molecules (Kirkpatrick & Ellis 2004p. Its exhaustive exploration using classical labeling methods based on quantum simulation is impractical. Machine learning regression offers promising solution by leveraging small, selectively labeled datasets to predict molecular properties at scale (von Lilienfeld et al. 2020). This data-efficient approach has the potential to accelerate the discovery of new drugs and materials.
We consider scenarios where we have access to a large pool of unlabeled data, e.g., molecules for which chemical and physical propertics (the labels) are unknown and costly to obtain. We aim to seloct and label small subset of the data pool to train regression model. We show that by selecting suitable training sets we positively impact the prediction performance of ML regression models. The goal is to improve the average prediction performance of the model on the points in the pool not selected for training. We focus on label-agnostic, passive, and model-agnostic sampling, that is, selection approaches that solely rely
Work done while at Universität Bonn. Currently University of California, Los Angeles.

---

Published in Transactions on Machine Learning Research (02/2026)
the data feature representations, do not consider any active learning procedure, and do not assume any specific structure for the regression model. On the one hand, this promotes the reusability of the labeled samples, ensuring labeling efforts are not wasted on subsets useful only for specific models or tasks. On the other hand, developing such approaches is a non-trivial challenge because we can rely only on very little information, that is, the data feature representations and some assumption on the regularity of the learned function, but not on the model used to learn it, e.g., using a neural network or a kernel approach. As an additional constraint, we are interested in sampling approaches that are computationally efficient and potentially can be used data pools consisting of hundreds of thousands of high-dimensional data points, which is a realistic size for molecular property prediction tasks.
Training data selection for model performance optimization has been extensively studied. Relevant literature includes Active Learning (AL) [Settles] 2012 Ren et al. 2021) and experimental design (John & Draper 1975, Yu et al. 2006). However, both focus on methodologies that optimize data selection by leveraging model- specific knowlodge. Here, we focus on passive and aodel-agnostic sampling strategies. Passive sampling was first introduced in Yu & Kim (2010), where the authors highlight its importance in scenarios where labeled data can be difficult, consucins,,nng, passive sampling strategics can be classified as model-dependent and model-agnostic. Model-dependent approaches optimize the data selection process for specific models or classes of models. We see single-shot batch active learners and experimental design approaches as passive and model-dependent methods. Model- agnostic selection approaches have the potential to benefit multiple classes of regression models, thereby enhancing reusability of costly data labelling.
expensive to obtain. Drawing from CCiiaaoo & Garcke) (2024),
The Farthest Point Sampling (FPS) is greedy passive and model-agnostic sampling strategy that provides approximate solutions to the k-center problem by minimizing the fill distance of the selected set, which is the maximal distance between a point in the feature space of interest and its closest selected point. The benefits of minimizing the training set fill distance have been studied independently for classification (Sener & Savarese 2018) and regression (Climaco & Garcke 2024). In Sencr & Savarese (0188) it was shown that minimizing the training set fill distance leads to increased accuracy by reducing the average classification error of Lipschitz continuous models with a softmax output layer. In Climaco & Garcke| (2024) we show that for regression tasks minimizing the training set fill distance with the FPS significantly reduces the maximum error of the label predictions of Lipschitz continnous models. However, it was also shown that employing FPS to minimize the maximum prediction error is mostly beneficial in the low data regime and that in such low data regime it does not provide any significant advantage in terms of the average absolute prediction error compared to other passive sampling approaches that are model-agnostic.
This work addresses the limitations of the FPS for molecular property prediction tasks and aims to extend the work done in Climaco& & Garcke| (2024). In particular, we develop a passive and model-agnostic algorithm, inspired by the FPS greedy procedure and supported by solid theoretical motivation, to select training sets that can improve the average prediction performance of regression models measured in terms of the mean absolute error (MAE).
We derive an upper bound for the expected prediction error of Lipschitz continuous regression models. Our bound is linear in a novel weighted fill distance, that is, the maximum weighted distance between a point in the fcature domain of interest and its closest selected training point. The weights we use to scale the distances provide information on the distributions of the data in the feature space. We introduce a novel passive and model-agnostic data selection strategy called "Density-Aware Farthest Point Sampling" (DA-FPS). This strategy greedily selects sets from pool of available data points with the aim of minimizing a data-driven estimation of the weighted fill distance of the selected set, thereby minimizing our proposed bound. The ultimate goal of DA-FPS is to select training sets that can enhance the average prediction performance of Lipschitz continuous regression models. We prove that DA-FPS provides approximate minimizers for a data-driven estimation of the weighted fill distance. Additionally, we report experimental results showing that selecting training sets using DA-FPS can decrease the average prediction absolute error of Lipschitz continuous regression models. Compared with other model-agnostic sampling techniques, including FPS, DA-FPS demonstrates its superiority for low training set budgets in terms of mean absolute error (MAE) reduction. We are not aware of any other passive sampling model-agnostic strategy supported by rigorous theoretical work that can improve the mean absolute prediction error of a regression model.
2

---

Published in Transactions on Machine Learning Research (02/2026)
The paper is organized follows: In section we review related work. In section regression problem and define the optimization objective. In section I we derive an upper bound for the expected prediction error of Lipschitz continuous regression models that depends linearly on a weighted fill we introduce the DA-FPS algorithm and prove that it provides approximale minimizers for a data-driven estimation of the weighted fill distance. In section g we report experimental results showing that DA-FPS can reduce the mcan absolute prediction error of regression models compared to other passive sampling model-agnostic strategies. In section g we summarize our contributions and outline future research directions. After the conclusion, Table ! provides key notation.
g we formalize the
distance of the training set. In scction 5 i
2 Related work
There has been significant research effort to develop approaches that can be used for training data selec- tion aiming at model performance optimization. There is a large body of literature on active learning (AL). See Settles 2012) and Ren et al.] (2021) for review of such approaches. AL lypically involves training regression models to predict uncertainties or estimate labels for unlabeled data, selecting the most relevant points for labeling, including them in the training set and repeating the process until stopping criteria are met. It optimizes the training set selection for a specific model or model class, and for a given task, by using computed labels to iteratively update model parameters during selection. Single-shot batch active learners select the training set in one step without iterative training or label knowledge. Examples include methods that minimize maximum mean discrepancy, discrepancy, and muclear discrepancy, which are quantities that can be estimated solely relying on the data features (Chatlopadhyay et al. 2012 Wang & Yel 2015 Vier- ing et al. 2019h. However, these approaches require choosing a kernel function, and their effectiveness in reducing the prediction error is theoretically motivated only assuming that the regression function belongs to the reproducing kernel Hilbert space associated with the chosen kernel (Viering et al., 2019). That is, they optimize the selection for specific model classes, such as kernel regularized least squares, similar to active learning. Moreover, such approaches have been mostly studied for classification tasks. Assuming the knowledge of the learning model may even lead to the development of strategies that reflect some principle of optimality for the selection of the training set, in the case of approaches developed in the field of experimental design (John & Draper 1975 Yu ct al. 2006).
In this work we focus on passive and model-agnostic sampling strategies. Coresets (Feldman 2019 pro- vide an effective set of tools for performing model-agnostic passive sampling. Uniform random sampling is considered the natural benchmark for all the other sampling strategics (Feldman] 2019). Importance sampling selects data points that are more important to the problem at. hand based on importance weights determining the relevance of each data point. For instance, Xie et al. (2023) present an importance sam- pling approach for selecting suitable pretraining datasets for large language models. Cluster-based methods, such as + and k-means++ (Schubert & Rousseeuw 2021), group similar points together and select representatives from each cluster. Greedy methods such as submodular function maximization ion algo- rithmns (Krause & Golovin 2014) start with an empty set and iteratively add the most influential point at each step; according to a given priuciple. Data twinning partitions the dataset into statistically similar twin sets by attempting to minimize the energy distance, a quantity that can be estimated solely by computing pairwise distances between data. features. It has been effectively used for training data selection in regres- sion (Vakayil & Joseph 2022). In our earlier work Climaco & Garcke (2024) we show that selecting the training set by fill distance minimization using the Farthest Point Sampling (FPS) can reduce the maximum prediction error of Lipschitz contimuous regression models. However, we also show that FPS does not offer any significant benefit in terms of the average absolute prediction crror when compared to other benchmark passive sampling model-agnostic approaches.
3 Problem definition
In this section we formalize the setting of the regression problem we aim to address and define the optimization objective. Our setting is similar to the one introduced Climaco Garcke (2024). We consider a supervisod regression problem where the feature space X C Rd is bounded and the label space is y C R. The goal is to learn function g X + y from function space M, using set of labeled data. Fach function in M may
3

---

Published in Transactions on Machine Learning Research (02/2026)
be parameterized by weights E R" depending on the learning algorithm. To evaluate prediction quality, we use an error function X x y x M - IR+,, which measures the prediction error of a trained regression model for a given input feature and associated true label.
Let D == Wo)=: be a pool of available data points consisting of iid. realizations of two random variables X and Y taking value on L' and V/ respectively, with joint distribution pr E == {p X y I JE p(æ, y)dwdy = 1}. We consider scenarios where the labels {ui are unknown. We aim to select and label a training set == { (k,)), from D, with in E (I,...,m} Vj. and b < n. The objective of the training data selection is to maximize the average predictive performance of a regression model mc E M, trained on L, on the new data points not selected for training. In the following, without loss of generality, we assume := ((2,,,))} and define Lx == { Following along Wang & Ye (2015), we assume that the training data is selected according to distribution Pe E P with pD F Pc and Po(y)z) = Po(y/æ). In other words, the training data distribution may differ from the data source distribution, but the map connecting data location æ E & and its associated label value is independent on how the data is selected. Furthermore, we study a typical scenario involving molecular prediction tasks in which the data source distribution pp is unknown, and we have only access to the locations Dx == |= of the dataset D. Moreover, we are interested in applications in which the labeling process is computationally expensive, therefore, given a budget. b E N of points to label, the goal is to select a subset. Lx C Dxx and label it to obtain subset C C D that solves the following optimization problem:
min E,, Y,m=]
LCD.
12|=6
In other words, we aim to sample and label a training set L, of cardinality b, so that the expected error on the data distribution pp associated with the function ma is minimized.
The optimization problem addressed in Climaco & Garcke (0244) and the we define in 1 are similar in the sense that both focus minimizing an expected value of the error function by selecting a subset L from set of available data points D. The key distinction lies in their objectives: in Climaco & Garcke (2024). the goal is to minimize the maximum expected error over a finite set of known data locations. Differently, in L the objective is to minimize the average error, defined as the expected value of the error function over the data source distribution pD on X y
4 Bound for the expected prediction error
In this section we develop our main theoretical contribution: upper bound for the optimization objective in ! that depends linearly on a novel weighted fill distance of the training set. We first introduce the concopt of weighted fill distance of a set. We then establish assumptions and present our main theoretical result.
Since the optimization problem in I cannot be solved directly due to the unknown labels of the points in D and the unknown data source distribution PD. we derive upper bound for its optimization objective. This bound identifies the weighted fill distance of the training set as key quantity to minimize for better predic- tion performance, motivating our Awnsity-Aware Farthest Point Sampling (DA-FPS) algorithm introduced in the next section. We define the weighted fill distance, a quantity we can associate with finite subsets of the feature space X' selected from pxe, which is the marginal on X' of a distribution Pe E P, called training data distribution.
Definition 4.1. Consider X' C Rd bounded and Lx = {2,})=1 C X, set of data locations sampled from Pxc: marginal on X' of a distribution Pc E P. Moreover, consider px, marginal on X of distribution PD E P. We define the weighted fill distance of Lx in X' with respect to pxp as
Wex x (pxx llxxx)= == sup min || 2,112veex (z), mex afEx
(2)
where || - 1|2 is the Lorm and the weight function v/ex : X + R is defined as
VCx (x) = (1
pag (x) (x)
if pxx (x) + 0, otherwise,
pxp (x)
(3)
4

---

Published in Transactions on Machine Learning Research (02/2020)
with px, px,(x) == fy Pc(a, y)dy and px (x) == Sy PD (a yddy.
The weighted fill distance is deterministic quantity depending on the densities px, (2) and pxp (x) the weight function (æz), the selected set Lx and the distance metric. Here, we use the Ig-metric as it is commonly used in machine learning applications. The following results can be generalized to other metrics. The weighted fill distance is non-negative, as we show in Appendix A and reduces to the standard fill distance when (x) for all z E X. Our weight function Vc., = 1 pxz(=)
(x)(() assigns higher weights to regions where the marginal of training data distribution on X' underrepresents the marginal of the data source distribution, iee, where Pxe (x) < (a)). Note that the weighted fill distance can be zero under different circumstances. This occurs, for instance, when V2x (ar) = for all æ E X, or when any point in the non-zero support of PXp is in Lx, that is when min || - æ,112 = 0 for all æ such that (x) > 0. In axELx
the first case, the fact that dex (x) 0 for all E X' implies that the marginals of the training and data source distributions are perfectly aligned, that is, Px, pxx(()) pxp (x) for all æ E X. This simply follows by how we defined the weight function. In the second case, the fact that each point in the non-zero support of Pxp is in Cx implics that Cx already contains all points associated with data locations where a point from the data source distribution could arise. That, is, the relevant regions of the data space are already included in the selected set. In other words, the fact that the weighted fill distance is zero can indicate either perfect distributional alignment or full geometric coverage of regions of the data space where points from the data source distribution could arise, but not necessarily both. Thus, the weighted fill distance serves as joint measure of geometric coverage and distributional matching between the training and data source marginals.
For our theoretical analysis, we use assumptions from Climaco & Garcke (2024), which we recapture in Appendix B.I and B.2 In particular, we consider the assumptions to be valid also for pp and pc- The first assumption states that given the data feature location X = 2i the expected associated label value, yv, is close to the conditional expected value of the random variable Y at that location. That is, E ||Y - Exy]=, [x.] S e, with scalar e 0. This assumption models scenarios where the true feature-label relationship is stochastic deterministic but subject to random fluctuations with a magnitude parameterized by fixed scalar e. Further, a Lipschitz continuity assumption relates to the smoothness of the map connecting X' and y. That is, [E - E [||@]| S >p - ã 2|12, A & a E X, where Xp E IR+. It implies that when two data points are closer in X, their corresponding labels tend to be closer in y. The second assumption essentially states that the expected error on the training set is bounded. That is, we assume there exist Eg 2 O, depending on the labeled set L C D and the trained regression model my: such that for any labeled point (z,.8z) E L we have that [[] Y, m²) mzy] S ec.. We also make standard regularity assumptions on the error and learned functions hold in the form of Lipschitz continuity, With that, are able to establish an upper bound for the optimization objective in [
Theorem 4.2. Consider random variables (X,Y) taking value on X x 3 C Rd R, with X bounded, data source distribution pD E P, labeled dalaset L:= { ((m,,,))) u;)})=1 arising from training data distribution PC E P. regression model m. E -M trained on L, and error function 1: X x y x M + IR.. If Assumptions B. and B. are fulfilled, then we have that
Epp [1X,, Y.mc)l CWE.. (pxxllxxx)
+ (
+
EC VRa trainiing set
) < <xxl+
Epe 1(X, Y,Yc),.
(4)
labels uncertainty
expected training distributioon
< (x) da quantifies distribulional mismalch belween Pxo and pxe- The indicator function 1 (P)x(x) < Pxx (x)} equals 1 when the condition Pxo (x) < Pxx (x) is satisfied. C (Axx + >1)) Ap Lipschitz constant and e laaelss' uncertainty from Assumption B.1 Xix
where Pe [pxo < Pxx] := Px 1 (pxx
and Aty are Lipschitz constants of the error function from Assumption B. eg is the mazimum error of m on the training set, from Assumption B.2 Wex. x (pxcllxx, ) is the weighted fill distance defined as 2 Moreover, pxp and pxz are the marginals of pD and pc, respectively, defined on X.
Theorem 4.2 proof in Appendix C provides a qualitative upper bound for the expected value of the error function on the data. source distribution pr depending linearly on the weighted fill distance of the selected
5

---

Published in Transactions on Machine Learning Research (02/2026)
training set. Note that if (x)x()) Pxx (2:) V x in the non-zero support of pxp: the weighted fill distance and Pe [px, < pxx] would be zero and the bound reduces to the trivial but tight inequality Ryx, [x(X, Y, Y,m)) s EpD [[X,, Y, mc)]. This shows that when the training and data source distributions are perfectly aligned, our bound reduces to the best achievable bound in this scenario.
The bound 4 depends on five main quantities: the maximum error on the training set (ec), which we can only compute after training regression model, the label uncertainty (e), the expected error on the training data distribution (Epe [[X,, Y, mc))), which we may not know be able to compute, P2 [px;, Pxxl quantifying the mismatch between pxp and pXc. and the weighted fill distance. The last two quantities do not depend on the data labels, contrary to the first three. The expected error on the training data distribution and the maximum error on the training set indicate that the bound also depends on how well the unknown trained model fits the training data distribution. We do not consider minimizing these quantities because we cannot estimate them without training a regression model. We are considering a passive and model-agnostic sampling scenario where we have no knowlodge about the data labols and the regression model at the time of selection. In what follows, we work under the general assumption that the employed trained model works well on the training data and that these quantities are negligible. A similar assumption has been considered in previous work (Just et al., 2023). Under such assumptions, the smaller the weighted fill distance of the selected training set and Pc Pxx < <xxcl, the smaller the bound for the expected approximation error on data from the source distribution PD-
In this work, we focus on minimizing the weighted fill distance of the selected set. We only consider minimizing the weighted fill distance for the following reasons: First, the weighted fill distance provides quantification of distributional mismatch between the marginals of training and data source distributions by means of the weight function. If there is no distributional mismatch the fill distance is zero. Thus, minimizing the weighted fill distance is related to decreasing Pc IPxx < Pxxl as well. Second, by taking into account point distances, the weighted fill distance provides a more comprehensive measure that captures both geometric coverage and distributional alignment aspects. Third, it is more tractable to minimize one of the two quantities than to minimize both. Our goal is to design a data sampling strategy, inducing a training data distribution marginal pxe, to sample a set Lx with minimal weighted fill distance.
5 Density-Aware Farthest Point Sampling (DA-FPS)
In this section we present our main algorithmic contribution: the DA-FPS method for selecting training sets aiming at minimizing the weighted fill distance. We first cxplain the core algorithmic idca. We then detail how we estimate the weighted fill distance from data. Specifically, we describe the density estimation approach using k-nearest neighbors and discuss the estimated weighted fill distance formulation. After that, we present the complete DA-FPS algorithm. The scction concludes by addressing computational challenges, providing implementation details, and discussing key algorithmic choices.
DA-FPS is data selection procedure aiming at minimizing the weighted fill distance of the selected set: We.. x (Px:llex>>) Unfortunately, given set Lx C X, its associatod weighted fill distance cannot be directly computed
the weights explicitly depend on the marginal of the data source distribution Pxd: which we consider to be unknown. Still, we have access to a set Dx = {2;) of unlabeled data points arising from PXp- Thus, we compute an estimation pxp of pxv from the unlabeled set Dx. In this work we assume we do not know a priori the explicit form of the training data distribution marginal px, that we want to use to sample points. If we knew it we could sample according to and would not have the need to develop data selection strategy. Instcad, we develop a data selection strategy that induces a training data distribution marginal pxz, which we estimate from the selected Lx as pxc- The selection procedure we propose aims at selecting a set Lx that minimizes data-driven estimation of the weighted fill distance based on the dataset Dx. the selected subset Lx and the two estimated marginals px, and pxc-
Before diving into the technicalities of our proposed sampling method, let us briefly describe its core pro- cedure. Our approach involves iteratively sampling data points at a maximal weighted distance from those alrcady selected. Initially the weights are set to one for all available points, thus, in this initial stage, our procedure coincides with FPS. After a portion of the data has been selected, the weights adapt dynami- cally during the selection process according to the chosen training set. The weights reflect the relationship
6

---

Published in Transactions on Machine Learning Research (02/2026)
between Pxs, and Pxg, which we estimate from the data locations. For this reason we call our approach Density-Aware Farthest Point Sampling (DA-FPS). The weights dynamically change because the estimation of the marginal of the training data distribution, Px2, is data-driven and depends on the current training set. As we add new points to the selected set, Pxg must be updated.
5.1 Density estimation
To estimate the multivariate marginal distributions Pxo and Pxc: we follow along Wang et al. (2009) and choose an adaptive A-nearest-neighhor (kNN) density estimation approach. Note that, we opted for kNN density estimators over other strategies for density or density ratio estimation because they are computa- tionally efficient. Using kNNs, we can estimate the density at a specific data point by only considering its distance relationships with its k-nearest neighbors, without having perform additional comparisons with other points in the data set. This reduces the computational costs involved in the iterative process of density estimation. The multivariate kNN density estimations of marginal distributions, Pxc and pXp, are based on a selected set Lx, the dataset Dx and kernel function K Rd + RR. At point a E X' the estimated densities have the form
Σ K mxEDx
E
Σ K and pxx (x) = B,ELx
22 22
2xx (z)
(2)
px: (z) =
(5)
[Dxe (r2 (x:))
1ex
(1 (2z)
where
} and K(x)= =
Va if | S 1,
A 2x (x) = min min [EExx
|| Øl12 +
Ex
pa(co)
(6)
Lxx
0, otherwise,
with (=(x)) == min(r E IR+ such that Hi E Dx || - 2l|2 S r]] 2 k3 the distance between æ and its nearest neighbor in Dx, and Va r(d/2+1) is the volume of the unit ball in R where I(r) (r 1)! is the so-called Gamma function. The quantity r2 (a)) (x)) defines an adaptive neighborhood size, depending on the selected set Cx, aiming at reducing the estimation bias at finite sample sizes (Wang et al. 2009). cx in the definition of r²z (x) is an arbitrarily small positive scalar that prevents the denominator in the kNN density estimations from becoming zero on points in Lx. Note that, we are interested in estimating the densitics only for points in Dx',Cx == {ar E Dx such that Lx), which are not already in Lx, and we may want to select depending
the value they would provide, which quantify with the associated weighted distance. Nonetheless, the kernel estimations in 55) are well-defined for all points in X. In Appendix D we show that, under some assumptions, pix. and Pr:, are asymptotically unbiased estimations of px. and pxo: respectively.
5.2 Estimated weighted fill distance
We compute a data-driven estimate of the weighted fill distance of a set Lx C Dx using the densily estimations in as follows
-1-- max #E Dx Cx
(
phc (x) P.p (x)
min || 25ELx
xz ll
(7)
Unfortunately, the behavior of the estimated weight function 7 is inconsistent with that of the true weight
function in (3). To see such inconsistency, we consider Ni. (xxx)) == { Dx such that ||æ-øll2 S px(x)) C Dx as the set of data points of Dx in the k-neighborhood of æ, and introduce the weights
= |x E Dx s.t. || - ø122 s r (x)}l.
Cxx > 0, if Lx 0
2i (x)
(8)
ki
defining the number of points in Dx contained in the ball centered in x with radius 2 (x). Note that, w²x (x) & k. For completeness, we set the weights associated with the empty set equal to k. Now that
7

---

Published in Transactions on Machine Learning Research (02/2026)
Algorithm Density-Aware Farthest Point Sampling (DA-FPS)
Input: Dataset Dx ( C X, data budget b E N, neighborhood size k E N, with b, h < n. Set Lx C Dxx with x < b, u E with u < b. Output: Subset Cx C Dx with Cxl = b.
if Lx= 0 then
Choose â E Dx randomly and set Lx {
3: end if
4: while [xx < b do
if [x < then
x arg max zEDx
min EJELx
| 2z112
else
8:
Compute w
(x) V x E Dx/ Lx as in (8)
2 arg max rEDx/Lx
min ||a ny 112 (x)) B,ELx
10:
end if
11: Lx c Lx U (x)
12: end while
we have introduced the weights in we can rewrite the estimated weight function point X, follows
evaluated on a
F (w) Pxp (x)
1,
if 3l æ E Lx (x))),
Dx otherwise. Cx]
(9)
To see this consider that the numerator of Pxx (2), as defined in 5 is either Va or zero depending on
whether there exists an 2Ú E Lx (x( or not. Depending, on the ratio 22, (+]]Cx] and the value of k the estimated weight function in (9) may allow for negative values data points in Dx not yet included in the training set, where we would expect p (a)) S Pxxp (æ).. This behavior is not consistent with the bchavior of the true weight function defined in (3). which associates non-negative values with points where px. (x) & Pxp (æ). This artifact is directly linked to the fact that the training and data densities are estimated using sets with different amount of points, ie., if | = [xxl the estimated weight function in would be non-negative.
Dxl
Thus, the approach use to compute the densities' ratio affected by scaling issues related to the sets' imbalance. But, observe that the values of the estimated weight function are directly correlated with
(1 Fxp (2)
2 (z)
those of the weights w²x (ær defined in 18. Given क. x E X' we have
1
Pxp (2)
(1
1
(x) (a)
2., (7) wh (z) and w2x (Ø) > (
The value of wř,, (Φ) is simply
Px (+)
Exp (x)
the number of points in Dx that are close to x. Based on these observations, we avoid the scaling issue of the estimated weight function in g by replacing it with weights defined in
That is, instead of attempting the minimization of the quantity in 7 consider the following minimization problem:
Ox arg min
max xEDx
(w (x: min 2xEcx
|| 23 mzlla)) l1)l
(10)
CxC 1x
For more compact notation, we define the quantity between the squared brackets as follows
W
Cx. Dx == max
(a:) min
|| - 22,12 mex,,,112)
(11)
2EDx
ELx

---

Published in Transactions on Machine Learning Research (02/2026)
and refer to it as estimated weighted fill distance of Lx in Dx. The value k in 11 is the amount of nearest neighbors consider to compute the distance weights as in ( The optimization problem in (10p is a weighted version of the fill distance minimization problem and is therefore at least NP hard.
5.3 DA-FPS algorithm
To address the estimated weighted fill distance minimization problem in 110 we propose the novel DA- FPS, described in Algorithm ! DA-FPS takes in imput a finite dataset Dx C E a data budget b E N, a neighborhood size E N, with b, & < n, a subset Lx C Dx, with |4x] < and an additional hyperparamcter u E N, u < b. The input hyperparameter u N allows for a greedy selection with uniform weights until the size of the selected set reaches the value described by the hyperparameter. Later on, the objective of our algorithm is to greedily augment the input subset Lx by selecting points from the dataset Dx that the maximum weighted distance of any point in Dx to its nearest selected point in Lx is minimized. The weights used to scale the distances are defined in (8 depend on the selected set Lx- Consequently, they must be itoratively updated any time a now point is selected and included in Lx. The algorithm stops when the number of elements in the selected set Lx reaches the data budget b. After that, Lx is the output.
The behavior of the algorithm is primarily controlled by two hyperparameters: the neighborhood size k for the ANN density estimation and the parameter u for initial uniform selection. The parameter k controls how we estimate densily and directly alfects the weight values w (2:). Small values of k make the weights very responsive to local changes in density, which may lead to high variance in the values of the weights, and consequently, to noticeable differences in the values of weights associated with points lying in regions with similar true density. Large values of k produce more stable weights but may over-smooth important density variations. As we select more points, the impact of the parameter & becomes less relevant because the weight value at given location is increasingly determined by how close the nearest selected point is, rather than by the distance from the k-th nearest neighbor. This happens because cach weight value counts points within a neighborhood whose size depends the distance to the closest selected point. The parameter u determines the amount of points selected with uniform weight: setting u = 0 recovers pure density-aware selection from the start, while w- = b reduces to standard FPS. In Section S where we report experimental results, we comment on the influence & and u on DA-FPS performance.
Note that we are considering the Euclidean distance in our formulation of the (estimated) weighted fill distance. However, other distance metrics can be used depending on the data characteristies and the specific application. We follow common practice and use the Euclidean distance for general-purposee applications. We remark that alternative formulations for the estimated weighted fill distance could be considered during the development of DA-FPS. For instance, we chose multiplicative weighting (wž, (x) ming, ECx -a---- | rather than additive weighting (ming,ec.x - + awi, (x)) because multiplicative weighting was motivated by our theoretical result and avoids the need to tune an additional scaling parameter a. Further investigation into alternative formulations and their empirical performance could yield valuable insights and potentially
lead to improved sampling strategies.
6 Simple illustration of DA-FPS
In this section we provide an intuitive understanding of DA-FPS behavior through a visual 2D example. We compare DA-FPS with uniform random sampling and standard FPS on a synthetic dataset with varying density regions. The illustration demonstrates how DA-FPS balances coverage of the fcature space with density awareness, selecting points from high-density regions while still covering sparse areas.
Fig. I (top row) shows dataset of 1000 two-dimensional points in the unit square. The dataset contains high-density cluster (650 points) in the center, smaller cluster (200 points) in the lower left, and 150 points scaltered uniformly at random. The blue background is a 2D kernel density estimation (KDE) plot, where darker blue means higher density. For the KDE plot we use the Seaborn Python library (Waskom 2021) The second row of Fig. | shows 100-point subsets selected by uniform random sampling, FPS, and DA-FPS. For DA-FPS, we set 0 and & 100. From a global perspective, DA-FPS balances two objectives: covering the data space evenly while giving greater importance to higher-density regions. Consequently, the
9

---

Published in Transactions on Machine Learning Research (02/2026)
(a) Dataset with 1000 points
(b) 100 points selected uniformly at random
(c) 100 points selected
(d) 100 points selected with DA-FPS
with FPS
Figure 1: Illustration of DA-FPS, FPS, and uniform random sampling synthetic 2D dataset. Top row: (a) A dataset with 1000 points in the unit square. The dataset consists of high-density central cluster (650 points), smaller lower-left cluster (200 points), and uniformly scaltered points (150 points). The background shows a 2D kernel density estimation, where darker blue indicates higher density. Bottom row: 100 points selected by each method.
(b) Uniform random sampling mostly selects from the dense cluster and may miss sparse regions. (c) FPS selects points evenly across the space, ignoring density. (d) DA-FPS selects more points from dense regions but still covers sparse areas, balancing density and coverage.
sampled data approximates the original distribution but with reduced density differences across the data space. In contrast, FPS consistently selects points to provide a uniform representation of the data space, while uniform random sampling mainly focuses on the high-density clusters, potentially neglecting sparser regions, e.g,, no point selected in the lower right corner when uniform random sampling is used. Locally, both FPS and DA-FPS tend to select points that evenly distributed without clustering. This due to their optimization processes, which lead to maximize pairwise (weighted) distances between the selected points, creating a "repulsion effect.". One of the key advantages of DA-FPS for sampling training sets lies in its ability to balance the representation of both dense and sparse regions in the data. By ensuring that high-density regions are rell-represented while also covering sparser areas, DA-FPS mitigates the risk of over-fitting or fuder-fitting to dominant clusters, which a common issue when using random sampling and FPS, respectively.
7 Analysis of DA-FPS
In this section we provide a theoretical analysis of DA-FPS performance. We establish that DA-FPS achieves a 21-approximation for the estimated weighted fill distance minimization problem in (10 where & is the number of nearest neighbors used DA-FPS. Following a discussion of the relationship between the parameter & and approximation quality, well computational complexity considerations. We also address limitations of our density estimation approach and implementation details. The following theorem establishes that DA-FPS achieves a 22-approxination for the fill distance minimization problem in 10
10

---

Published in Transactions on Machine Learning Research (02/2026)
Theorem 7.1. Given set of data locations Dx= forli= CR, subset Ox Dx, optimal solution to the problem in (10) with |Oxl = b E N+, b < n, and Lxx C Dx, 16x1 = b, subset selected with Algorilhm 7
initialized with Lx = 0 and u = O, we have
W Wx, Dx S 2kW Ox, Dx
(12)
where Wxx D and Wox, Dx are the estimated weighted fill distances of Lx and Ox in Dx, respeclively, defined as in 11).
Proof is in Appendix Theorem 7.1 gives an upper bound on the approximation error of DA-FPS for the estimated weighted fill distance minimization problem defined in (10). The theorem indicates that increasing the number k increases the approxination error. Recall that & is the largest possible value of the weights wh, (z)). The presence of k in the bound quantifies the worst case approximation error of the weights values, which depend on the selected set Cx. In particular, the weights associated with the set selected by DA-FPS can differ siguificantly from those of an optimal set Ox of size b, especially in the early stages of sampling when Cx contains only a few points. Appendix N provides an additional result stating that the approximation error of the DA-FPS estimation depends on the relationship between the weights of an optimal set and those of the set selected by DA-FPS.
It is important to note that the bound in Theorem 7.1 does not account for the quality of the density ratio estimation itself, which also depends on the parameter k. In other words, it does not quantify how well the estimated weighted fill distance in [11 relates to the true weighted fill distance in ( Addressing this issue is an open problem for future work and is closely related to the broader field of density ratio estimation.
The estimated weighted fill distance in [1 may not accurately reflect the true weighted fill distance in 2 particularly when the training set is small or the data are high-dimensional. According to multivariate density estimation theory (Wang et al.) 2009), limited sample sizes lead to biased densily estimates in (5) which in turn cause the behavior of the estimated weights w²xx (x) to deviate from that of the true weights #cx(x)) in (3). Consequently, DA-FPS may appear effective for the estimated problem in (10) but may fail to provide reliable performance for the true problem, especially for small training sets under high-dimensionall settings where density estimation is challenging. To mitigate these limitations, we first sample attempting to ensure broad coverage of the data space by using the hyperparameter u > That is, during the initial consider constant weights, which
steps of the sampling process, when density estimates are unreliable, we then iteratively update according to (8) after selecting the first и points. Thus, in early stages, DA-FPS coincides with FPS and focuses on minimizing the maximum distance between any point in the datasct Dx and its closest selected element. We note that, the theoretical approximation guarantee in Theorem 7.1 applies only to u = O. Nonetheless, using u > offers practical benefits: it ensures coverage across different regions of the data space before density-aware sampling begins, and allows us to accumulate sufficient points to improve the reliability of density estimation needed for effective weight computation. The choice of u is critical to DA-FPS effectiveness. For instance, if set too small, sparse regions may be underrepresented in the training set. This imbalance can result in low model performances in sparse regions of the dataset with a consequential increase in the average crror. We speculate that setting u > O may lead to improved approximation guarantees for DA-FPS with respect to minimizing the true weighted fill distance in (2). This is because the initial uniform sampling phase helps ensure that the selected set Lx has a more balanced representation of the data space, which can lead to more accurate density estimates and weight computations in subsequent iterations. However, formalizing this intuition and deriving precise approximation bounds for DA-FPS with u > 0 remains an open problem for future research.
Note that, Algorithum I can be implemented using ((D)k)) memory and takes O(d[DDkk) time, where d is the data dimension. To give a qualitative understanding, with an implementation in PyTorch (Paszke 2019) it takes approximately 970 seconds to select 26000 points (sx 20% of the total) from the Ruddigkeit et al. 2012 Ramakrishnan et al. 2014 datasct consisting 130202 data points of dimension we provide more experimental results on the efficiency of DA-FPS.
lt al.]
QM9
100
In Appendix
We used 48-cores CPU with 384 GB RAM.
11

---

Published in Transactions on Machine Learning Research (02/2026)
8 Numerical Experiments
In this section we empirically validate DA-FPS on molecular properly prediction tasks. We describe our ex- perimental setup, introduce the baseline sampling strategies and regression models, and analyze performance using mean absolute error as our primary evaluation metric.
Experimental setup We focus on molecular property prodiction, a regression task in quantum chemistry. We use the QM7, QM8, and QM9 datasets, which contain 7,165, 21,766, and 130,202 molecules, respectively. Our setup is based on Climaco & Garcke| (2024), but with important differences. While Climaco & Garcke 2024) studied FPS mainly for small training sets (1% to 10% of the data), we evaluate DA-FPS for larger training set sizes, from 5% up to 20% of the data pool. This allows us to address challenges with high- dimensional density estimation in very small data regimes (which DA-FPS requires), and to test. DA-FPS in scenarios where FPS alone does not significantly outperform standard passive sampling in terms of average prediction crror. Our data preprocessing is similar to Climaco & Garcke (2024), but we reduce the feature vector dimension (up to 276 instead of up to 1300) to further mitigate issues with high-dimenniooall densily estimation. Full details on datasets, preprocessing, and descriptors are in Appendix G Appendix H provides empirical evidence that the datasets satisfy the required data assumption B.2 We use two regression models that have been utilized in previous works for molecular property prediction tasks: kernel ridge regression with a Gaussian kernel (KRR) (Stuke et al. 2019: Deringer et al.] 2021] and leed-forward neural networks (FNNs) (Pinheiro et al. 2020 Both models are Lipschitz continuous, which is required for our theoretical results (see Appendix [ for details on the models and hyperparameter tuning). We evaluate prediction performance using the mean absolute error (MAE), defined as MAE 1
nu E== ly: -4--ii -kl. where yt are true values, 0: are predictions, and ny is the number of unlabeled points in the data pool. The code necessary to reproduce the results presented in this section is available in our GitHub repository the final goal of our experiments is to empirically show the benefits of using DA-FPS compared to other model-agnostic -tate-of-the-art the-art sampling approaches and investigate the benefits of complementing classical passive sampling approaches with the FPS. We do not make any claims on the general prediction quality of the employed models on any of the studied datasels.
F Let us remark that
Baseline sampling strategies We compare our approach with four sampling techniques, among those analyzed in well-established papers related to data selection (Sener & Savarese 2018 Ghorbani & Zou, 2019 Mirzasolciman et al., 2020 Killamsetty et al.j 2021), that fit our application sccnario and problem constraints: passive sampling model-agnostic data selection techniques that do not rely on the knowledge of the labels. Specifically, we consider random sampling (RDM), Farthest Point Sampling (FPS), facility location (Fricze) 1974) and k-medoids++ (Mannor et al., 2011). Both facility location and k-medoids-4 attempt to minimize a sum of pairwise squared distances. However, the fundamental difference is that facility location is greedy technique, while k-medoids++ is based on a segmentation of the data points into clusters.
Molecular property prediction on QM datasets Fig. shows the MAE for the regression tasks on the QM7, QM8 and QM9 datasets using KRR (top row) and FNN (bottom row). For each combination of training set size and sampling strategy, the MAF is computed considering all the data points in the available dataset that have not been selected for training. Our experiments indicate that selecting the training sets using DA-FPS leads to botter prediction performances than the basclincs RDM, facility location, FPS and k-medoids+++ in terms of the MAE, particularly on the larger QM8 and QM9 and for larger training set sizes (> 5% of the available data points). Comparing the MAE obtained with KRR and FNN, reveals that the standard deviation of the MAE, represented by the error bars, tends to be larger for the FNN,, especially on the smaller QM7. This occurs because the FNN training process is sensitive to the limited amount of training data available with the QM7. More specifically, the FNN determines its regression parameters by solving a non-linear optimization problem using stochastic gradient descent, which is inherently prone to variability and instability. As a result, metries like the MAE often exhibit larger standard deviations. In rast, KRR solves a convex optimization problem with a dosed-form solution. This deterministic approach results
http:://gthhu..cm///aCccmaa/aan
12

---

Published in Transactions on Machine Learning Research (02/2020)
1.1
RDM
0.32
FaciityLocation
0.30
krttedidds*
MAE [eV]
0.9
FPS
MAE [eM]
0.28
MAE MAE(eV)
(eV]
DA-FPS
0.8
0.26
0.22
0.7
0.24
0.8
0.22
0.20
15%
15%
Amount of training samples
Amount of training samples
Amount of training samples
0.30
1.2
0.32
1.1
0.30
MAE [eV]
1.0
[e]]
MAE [ev]
0,28
0.26
0.9
0.26
0.7
0.24
0.22
0.8
0.22
5%
10%
20%
5%
10%
15%
20%
10%
16%
20%
Amount training samples
Amount training samples
Amount training samples
(a) QM7
(b) QM8
(c) QM9
Figure 2: MAF for regression tasks on QM datasets using KRR with Gaussian kernel (top row) and FNN (bottom row) trained on sets of varions sizes, expressed as a percentage of the available data points, and selected with different sampling stralegies. Error bars represent the standard deviation over five runs. DA- FPS (red lines) outperforms the baselines. The legend in the top-row leftmost graph applies to all graphs, DA-FPS is initialized with Lx W, k 100, and u 3% of the available data, independently of the datasct.
in lower variability in predictions and lower standard deviation of the MAE. In Appendix J we evaluate DA-FPS considering the root mean squared error (RMSE == / nu Σm= y ū.13) and show that DA-FPS is still the most competitive approach. In Appendix K we provide results with two additional datasets, not related to the quantum chemistry domain, two additional baseline selection strategies and one additional regression model. The results the additional experiments in Appendix K indicate that using DA-FPS leads the most competitive results in terms of MAE and RMSE.
It is important to note that, as explained in Section during the initial phase of the sampling process DA- FPS uses uniform weights. Meaning that, DA-FPS initially coincide with FPS, The amount of points selected with uniform weights is controlled by the hyperparameter u. In Appendix L we empirically investigate the benefits of combining FPS with the baselines used to benchmark DA-FPS. The experiments in Appendix L show that augmenting the baselines approaches with FPS during the initial steps of the sampling process consistently leads to a decrease in the MAE the predictions. Still, DA-FPS remains the most competitive approach. This investigation highlights that the advantages DA-FPS stem not only from initially using FPS but also from its density-aware weighting, taking place after the first u points have been selected.
Regarding the DA-PPS hyperparameter u, determining the amount of points selected with uniform weights, we make observations that can guide a user to a suitable choice. Our ablation study on the ZINC dataset (Appendix M) shows that for larger training set sizes (> 10%), the choice of u has little effect on DA-FPS performance compared to the basclincs. However, for smaller training set sizes, u has a stronger impact. When u is large, DA-FPS behaves more like FPS, which is known to reduce the maximum absolute prediction error (MAXAE == max (y)-) but may not lead to better average error. The work in Climaco & Garcke 15isa.
2024h found that, on the QM datasets, selecting just the first 2% of points with FPS, then switching to random sampling, achieves similar MAXAE as using FPS alone. This suggests that should not be chosen too large (e.g., < 5% of the available data points). Based on these observations we think that an "optimal" choice u depends on what the user wants to achieve. Qualitatively, if the user interested ensuring low MAXAE, at the cost of higher MAE, a larger is recommended. If the user is mainly interested in performing well average in the region of high data density, smaller recommended.
13

---

Published in Transactions on Machine Learning Research (02/2026)
In Appendix M we also analyze how changing the DA-FPS hyperparameter k affects performance. k defines the amount of k-nearest neighbors considered for computing the weights. The results show that DA-FPS works well for a range of & values, but choosing k that is too small can reduce its effectiveness. The rough magnitude of likely depends on the data dimension and distribution and is generally investigated in the context. of density estimation. The problem of choosing is common for ANN-based density estimation methods. We expect further insights from that domain. We think that the choice of should take into account at least two aspects: First, k should not be too small, because it would lead to high variance in the values of the weights, and consequently, to noticeable differences in the values of weights associated with points lying in regions with similar true density. Second, k should not be too large as the computational cost of DAFPS depends linearly on k.
9 Conclusion
We proposed DA-FPS, a passive model-agnostic sampling algorithm to select training sets by weighted fill distance minimization. We provided an upper bound for the approximation error of DA-FPS to the estimated weighted fill distance minimization problem we defined. Our numerical results demonstrated that utilizing DA-FPS select training sets has a positive impact on the average prediction of the regression models, particularly for larger datasets, in line with our theoretical motivation.
A key aspect of DA-FPS is the need to estimate the data densities. Poor density estimation in DA-FPS can lead to ineffective weights that cause oversampling of high-density regions, generating redundant information in the selected sct, and undersampling of low-density regions, leading to underrepresentation of important areas of the data space in the training set. This can lead to degraded model performance, for instance, through increased prediction errors in underrepresented regions. In this paper, we used a k-nearest neighbors (kNN) approach for density estimation. Using the kNN was computationally efficient but led scaling issues when estimating the weight function used in the definition of the weighted fill distance. Alternative methods that overcome this issue while remaining effective and computationally efficient could be developed. Our ablation study on the hyperparameter k: in Appendix M provides empirical evidence that choosing k too small can negatively impact performance, highlighting the importance of appropriate density estimation. Future research directions should investigate alternatives for the data density estimations or approaches for direct density ratio estimation. Concerning the choice of DA-FPS hyperparameter u, we hypothesize that statistical properties, such as density or size of the tails of the dataset, may be exploited by user to take informed decision. Developing adaptive strategies for automatically selecting the hyperparameterss & and based dataset characteristies would enhance the robustness and applicability of DA-FPS.
Notation
Broader Impact Statement
Selecting points aiming to reduce the weighted fill distance of the training set is beneficial when traditional labeling methods, such as numerical simulations laboratory experiments, are expensive or time-consuming. In such applications ML regression models provide fast label predictions for new data points. The quality of these predictions depends on the quality of the training data. Therefore, selecting is crucial to ensure accurate predictions. Our research on minimizing the training set weighted fill distance can potentially identify sets that can enhance average prediction quality for various regression models and tasks, preventing the wastage of expensive labeling resources on training sets that may only benefit a specific learning model or task.
effective training set
Acknowledgments
This work was partly supported by the German Federal Ministry of Education and Research (BMBF) within the projects MaGriDo (Mathematics for Machine Learning Methods for Graph-Based Data with Integrated Domain Knowledge). FKZ 05M20PDB and Rhine-Rull Center for Scientific Data Literacy (DKZ.2R), FKZ 16DK72030C.
14

---

Published in Transactions on Machine Learning Research (02/2026)
Symbol
Description
X'
Feature space, subset of R Label space, subset of R Pool of available data points, {( v.) Mi Cxxx Set of feature vectors of points D, (a:)== C
y
D
Dx
C
Training set { Vi, )1 D, with is E (1, ( n Set of feature vectors of points in L, (ai, 1 C Dx Data source distribution on Training data distribution on A' x y Marginal of po on X Marginal of Pe on X' General density estimator of pxp General density estimator of pxg k-NN density estimator of pxp k--N density estimator of pxz Weight function: 1
Lx
pD
Pc
pxp
pxg
pxo
pxe
Pxx
pxe
Mex (x)
Px,
PWr
Wer.x (px;)1pxx))
Weighted fill distance of Lx in Estimated weighted fill distance using k-NN
W
(x)
Adaptive neighborhood radius for density estimation Number of points in k-neighborhood of within distance r2, (z) Distance to k-th nearest neighbor of x: in Dx Regression model trained
w (c)
pk(a))
me
(x, mc)
Error function measuring prediction error
Table 1: Table of notation used throughout the paper.
References
Jayanta Basak. A least square kernel machine with box constraints. In 2008 19th International Conference Pattern Recognition, pp. 1-4. IEEE, December 2008. doi: 1001009 URL http:
//dx.do...rg/11.11100393 1109//I...1///PR.... 2008 4761717
Gantavya Bhatt, Yifang Chen, Arnav Das, Jifan Zhang, Sang Truong, Stephen Mussmann, Yinglun Zhu, Jeff Bilmes, Simon Du, Kevin Jamicson, Jordan Ash, and Robert Nowak. An experimental design framework for label-efficient supervised finetuning of large language models. In Findings of the Association for Computational Linguistics ACL 2024, pp. 1549-65600 Association for Computational Linguistics, 2024.
doi: 10. 10.18653/vi
L. C. Blum and J.-L. Reymond. 970 million druglike small molecules for virtual screening in the chemical universe database GDB-13. J. Am. Chem. Soc., 131:8732, 2009.
Theophilos Cacoullos. Estimation of multivariate density. Annals of the Institute of Statistical Mathematics, 18(1):179-189, December 1966. ISSN 1572-9052. doi: 10.1007/bf02266952 URL http://dx. doi. org/ 10. 1007/8F02888828
Rita Chattopadhyay, Zheng Wang, Wei Fan, Ian Davidson, Sethuraman Panchanathan, and Jieping Ye. Batch mode active sampling based on marginal probability distribution matching. In Proceedings of the 18th ACM SIGKDD international conference Knowledge discovery and data mining, KDD '12, pp. 741-749. ACM, August 2012.
doi: N0.1145/2339530.233666
Paolo Climaco and Jochen Garcke. On minimizing the training set fill distance in machine learning regression. Journal of Data-centric Machine Learning Research, 1(14):1-36, 2024. URL https://openreviee: .etteeeewwweeeeeeeeeeeee....e Forum?id=8R712uul
L. Dagum and R. Menon. Openmp: an industry standard api for shared- memooyy programming. Compulational Science and Engineering, 5(1):46
JEEE
2-44555,5 55, 1998. doi: 10. 09.1109/99.660 /9////99966......
15

---

Published in Transactions on Machine Learning Research (02/2026)
Volker L. Deringer, Albert P. Bartók, Noam Bernstein, David M. Wilkins, Michele Ceriotti, and Gábor Csányi. Gaussian process regression for materials and molecules. Chemical Reviews, 121(16):10033-11144 aug 2021. doi: 10.102//acs.cheemrr..o00000
Dheeru Dua and Casey Graff. Uci machine learning repository, 2017. URL http:///rchtrr..tes..... edu/ Accessod: November 1, 2024.
Vijay Prakash Dwivedi, Chaitanya K. Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. Journal of Machine Learning Research, 24(43):1-48, 2023.
URL http::/jmlr: http://www...pppppp///////////// 0567422222666..02 05mm.
M.E Dyer and A.M Frieze. simple houristic for the p-centre problem. Operations Research Letters, 3(6):
285 288, February 1985. ISSN 0167-6377. doi: 10.001/0166-333(((500002.
Dan Feldman. Corc-sets: Updated survey. In Sampling Techniques for Supervised or Unsupercised Tasks,
pp. 23-44. Springer International Publishing, oct 2019. doi: 10.1007 00000099978--002994999
M. Frieze. A cost lunction property for plant location problems. Malhemalical Programsming, 7(1): 245 248, dec 1974. doi: 10.1007/bf01588500
Amirata Ghorbani and James Zou. Data shapley: Equitable valuation of data for machine learning. Tn Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 2242 2251. PMLR, 09 Jun 2019. URL
mlr, ppess//9/ /ttps///////hoobbai1..... html
Tan Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, 2016.
Rafael Cómere-om Jennifer N. Wei, David Duvenaud, José Miguel Hernández-Lobato, Benjamín Sánchez- Lengeeiz,nnng,ing,, Dennis Sheberla, Jorge eguilera-lparraguree Timothy D. Hirzel, Ryan P. Adams, and Alán Aspuru-Guzik. Automatic chemical design using a data-driven continuous representation of molecules. ACS Central Science, 4(2):268 276, January 2018. ISSN 2374-7951. doi: 10.1021 /a.102//acccentsci. 7b00572.
Sariel Har-Peled. Geometric approzimation algorithms. American Mathematical Society, 2011.
Dorit S. Hochbaum and David B. Shmoys. A bost possible heuristic for the k-center problem. Mathematics of Operations Research, 10(2):180-184, may 1985. doi: 111288/moor1002.111
R. C. St. John and N. R. Draper. D-optimality for regression designs: A review. Technometrics, 17(1): Learning Representations, 2023. URL /11.://0401001.9.....1.1
15-23, feb 1975. doi:
Hoang Anh Just, Feiyang Kang, Tianhao Wang, Yi Zeng, Myeongseob Ko, Ming Jin, and Ruoxi Jia. LAVA: Data valuation without pre-specified learning algorithms. In The Eleventh International Conference on
Krishnateja Killamsetty, Durga Sivasubramanian, Ganesh Ramakrishnan, and Rishabh Iyer. Glister: Gener- alization based data subset selection for efficient and robust learning. Proceedings of the AAAI Conference on Artificial Intelligence, 35(99)8110-8811) May 2021. ISSN 2159-5399. doi: 10.1609/aaai.
Peter Kirkpatrick and Clare Ellis. Chemical space. Nature, 432(7019)) 823, December 2004. ISSN 1476-4687. doi: 10.1038 10.1038/432825.. /42883a..
Andreas Krause and Daniel Golovin. Submodular function maximization. Tractability, 3:71-104, 2014.
G. Landrum. Rdkit: Open-source cheminformatics, 2012. URL hittp://wwwrrdt org
Shic Mannor, Xin Jin, Jiawei Han, Xin Jin, Jiawei Han, Xin Jin, Jiawei Han, and Xinhua Zhang. K- medoids clustering. In Encyclopedia of Machine Learning, pp. 564-565 Springer US, 2011. doi: 10.1007/ 978-0-387-30164-8 426.
16

---

Published in Transactions on Machine Learning Research (02/2026)
Baharan Mirzasolciman, Kaidi Cao, and Jure Leskovec. Coresets for robust training of neural networks against noisy labels. Advances in Newral Information Processing Systems, 33, 2020.
Hirotomo Moriwaki, Yu-Shi Tian, Norihito Kawashita, and Tatsuya Takagi. Mordred: a molecular descriptor calculator. Journal of Cheminformatics, 10(1), feb 2018. doi: 10.1186/8133211-018022555
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang, Zach DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: an imperative style, high-performance deep learning library. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, Red Hook, NY, USA, 2019. Curran Associates Inc.
Gabriel A. Pinhciro, Johnatan Mucelini, Marinalva D. Soares, Ronaldo C. Prati, Juarez L. F. Da Silva, and Marcos G. Quiles. Machine learning prediction of nine molecular properties based on the SMILES representation of the QM9 quantum-chemistry dataset. The Journal of Physical Chemistry A, 124(47); 9854-9866, nov 2020. doi: 10.1021 /acs. waa..jjca..00590..
Raghunathan Ramakrishnan, Pavlo O Dral, Matthias Rupp, and O Anatole von Lilienfeld. Quantum chem- istry structures and properties of 134 kilo molecules. Scientific Data, 1, 2014.
Raghunathan Ramakrishnan, Mia Hartmann, Enrico Tapavicza, and O. Anatole von Lilienfeld. Electronic spectra from TDDFT and machine learning in chemical space. The Journal of Chemical Physics, 143(8), aug 2015. doi: (4.1063/1.498777
Pengzhen Ren, Yun Xiao, Xiaojun Chang, Po- Yao Huang, Zhihui Li, Brij B. Gupla, Xiaojiang Chen, and Xin Wang- A survey of deep active learning. ACM Computing Surveys, 54(9):1-40, October 2021. ISSN 1557-7341. doi: 10.1145/3472291. URL http://dx..t..////// doi org/10..///. 110...1115/3422299
Lars Ruddigkeit, Ruud van Deursen, Lorenz C. Blum, and Jean-Louis Reymond. Enumeration of 166 billion organic small molecules in the chemical universe database GDB-17. Journal of Chemical Information and Modeling, 28814 2875, nov 2012. doi:
M. Rupp, A. Tkatchenko, K.-R. Müller, and O. A. von Lilienfeld. Fast and accurate modeling of molecular atomization energies with machine learning. Physical Review Letters, 108:058301, 2012.
Erich Schubert and Peter J. Rousseeuw. Fast and eager k-medoids clustering: o(k) runtime improvement of the pam, clara, and clarans algorithms. Information Systems, 101:101804, November 2021. ISSN 0306-4379. doi: 1..1016//..s2222111113
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. In International Conference on Learning Represenlations, 2018. URL http::ts//oppearriiiiv.eoo hotterrrrr
H1aluk-RM RW
B. Settles. Active Learning. Synthesis Lectures Artificial Intelligence and Machine Learning, Morgan & Claypool Publishers, 2012.
Teague Sterling and John J. Irwin. Zinc 15 - ligand discovery for everyone. Journal of Chemical Information and Modeling, 5511):2332 2337, November 2015. ISSN 1549-960X. doi: httpl//aas.ccc...bb..
Annika Stuke, Milica Todorović, Matthias Rupp, Christian Kunkel, Kunal Ghosh, Lauri Himanen, and Patrick Rinke. Chemical diversity in molecular orbital energy predictions with kernel ridge regression. The Journal of Chemical Physics, 250422):, may 2019. doi: 10.1063/1.5086100
Akhil Vakayil and V. Roshan Joseph. Data twinning. Statistical Analysis and Data Mining: The ASA
Data Science Journal, 15(5):598 610, February 2022. ISSN 1932-1872. doi: 10.1002/sami 11574. URL
http://dx... doi. otgg/0..//000000 20m0. 11574
17

---

Published in Transactions on Machine Learning Research (02/2026)
Stéfan der Walt, S Chris Colbert, and Gaäl Varoquaux. The numpy array: A structure for efficient numerical computation. Compuling in Science & amp; Engineering, 13(2):22-30) 30, March 2011. ISSN 1521-9615. doi: 10.1009mmse.20111
Tom J. Viering, Jesse H. Krijthe, and Marco Loog. Nuclear discrepancy for single-shot batch active learning. Machine Learning, 108(8-9)1551--5599) June 2019. ISSN 1573-0565. doi:
Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Ev- geni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan van der Walt, Matthew Breut Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, C Carey, îhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, lan Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, António H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientifie Computing in Python. Nature Methods, 17:261-22 2722, 2020. doi: 10.1033/s44199--015 0666-2..
O. Anatole von Lilienfeld, Klaus-Robers Müller, and Alexandre Tkatchenko. Exploring chemical compound space with quantum- based machine learning. Nature Reviews Chemistry, 4(7):347-358, June 2020. ISSN 2397-3358. doi: 10.1038/ (0000///117000000011000
Endong Wang, Qing Zhang, Bo Shen, Guangyong Zhang, Xiaowei Lu, Qing Wu, and Yajuan Wang. Intel Math Kernel Library, pp. 167-188. Springer International Publishing, 2014. ISBN 9783319064864. doi: 7. URL http://dx. doi 00t/110..00///78--3319----888
10.1007/978-3-3199-666
Qing Wang, Sanjeev R. Kulkarni, and Sergio Verdu. Divergence estimation for multidimensional densities via n-ncarost-neighhor distances. IEEE Transactions Information Theory, 55(5):2332-244) 2405, May 2009. ISSN 0018-9448. doi: 200.://tt.2009200000
Zheng Wang and Jieping Ye. Querying discriminative and representative samples for batch mode active learning. ACM Transactions on Knowledge Discovery from Data, 9(3):1-23, feb 2015. doi: 10.1145/ 2700408.
Michael L. Waskom. seaborn: statistical data visualization. Journal of Open Source Software, 6(60):3021, 2021. doi: 10.21105/joss.0022.. URL
03021
Sang Michael Xie, Shibani Santurkar, Tengyu Ma, and Percy Liang. Data selection for language models via importance resampling. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL
I-Cheng Yeh. Modeling of strength of perfomaaformance concrete using artificial neural networks. Ce- ment and Concrete Research, 28:1797-1808, 1998. https://t/:/ htt./appi.smmaancccchcollllaaa Trrg/orppusD;
135820588
Hwanjo Yu and Sungchul Kim. Passive sampling for regression. In 2010 IEEE International Conference on Data Mining. IEEE, dec 2010. doi: 10.1109/tcdm.20100 2010.9.
Kai Yu, Jinbo Bi, and Volker Tresp. Active learning via transductive experimental design. Proceedings of the 23rd international conference on Machine learning ICML '06. ACM Press, 2006. doi: 10.1145/ 1 1143844. 143980.
18

---

Published in Transactions on Machine Learning Research (02/2020)
A The weighted fill distance is non-negative
Remark A.1. The weighted fill distance defined in
2 is non-negative.
Proof. In the definition of the weighted fill distance in 2 the distances are by definition non-negative. Therefore, it is enough to show that there always exists a point æ E X such that pxp (œ) 2 Px2 (2), that is, there always exists a point where the weight function non-negative. Let us proceed by contradiction. Let us assume that Va E we have that pxp (a) < px. (x)). Next, let us note that fxx Pxe (r))dæ = fx Pxp (æ)) 1, which follows from the fact that both, Pxo and pxe are probability distributions on X. However, by our assumption we have that
/ PNo (x0)dd < S pxc (2))de = 1,
which is a contradiction.
B
Assumptions
We recapture two assumptions from Climaco & Garcke 2024) that underlic our thcoretical results. The first assumption concerns the data being analyzed and the relationship between data features and labels.
Assumption B.1. We assume that for any feature vector Bg E we have that
E [[ = =//, 1ul pul < ox
(13)
and that there exists e 2 such that
[| E 2 [zg] = J, 11 10-EEyaa pcglppyy>x,,dll S c,
(14)
where
p(ylarg) ( v) px
and px((x)) = IsS Pz v)dy.
(15)
We refer to "6" the labels' 2 uncerlainly. Moreover, we assume that
E [ - E [ S Ap1la -+1l1 #112.
(16)
V à t E X, where Ap E R
The assumption in 14 states that given the data feature location X = Fii the associated label value is close to the conditional expected value of the random variable Y that location. This assumption models scenarios where the true feature-label relationship fluctuations with magnitude parametrized by the scalar The Lipschitz contimuity assumption in equation (16] relates to the smoothness of the map connecting X and y. It implies that when two data points are closer in X, their corresponding labels tend to be closer in y.
stochastic or deterministie but subject to random
The second assumption concerns the error function used to evaluate the performance of the model and the prediction quality of the model on the training set. Firstly, to formalize the notion that the prediction error of trained model on the training exhibit certain degree of regularity, which also reflects the regularity of the regression model.
is bounded. Secondly, to limit our analysis to error functions that
Assumption B.2. We assume there exist e 2 0, depending on the labeled set. L C D ((mgq yg) X y and the trained regression model mc, such that for any labeled point (æz Uj) E L we have that
E[, Y, m,) <c.
(17)
We consider <g as the maximum expected prediction error of the trained model mc on the labeled data Moreover, we assume that for any y E y and C the error function I(-y, me) is -ix-schch and that for any E X and L C DD 1(,,,,m, is -ipscctt, convex and E[[[(æ, Y, V,mc)](ar) < co.
19

---

Published in Transactions on Machine Learning Research (02/2026)
With 17 we assume that the expected error the training set is bounded. Morcover, with the Lipschitz continuity assumptions we limit our study to error functions that show certain regularity. However, these regularity assumptions on the error function are not too restrictive and are connected with the regularity of the evaluated trained model as already shown in Climaco & Garcke (2024). For instance, the A Lipschitz regularity and the convexity the second argument are verilied by all Ly-norm error functions, with S p < s.. We also assume that [l Y,,,m,mmi., m=) < oo for any given a E X. This assumption formalizes the intuitive lact that, applications, independently of the trained model and the feature vector considered, we expect the error function to take finite values.
C Proof Theorem 4.2
Proof. First, let us notice that
Ep [(x, Y, mc)]
= Epp (XX, [X,YYma) M,Y,) - Epc. [1(,, Y, mc)] + Epc [[X,, Y, mc)l
= E [1x,, Y, mc) px, (cr) / IE [1(x, Y, mm)) (x) pxx (x)) + Epe ((X, Y, mc)]
(18)
E Bl( (pxx pxe (x)) dx + Epe [IX,Y, mc).
X. PXp SPXC
Note that in the expectation [1x,, Y, m2) ae] is independent of pD and pc- This because, as mentioned in Section x X and its associated label value is independent on how the data is selected, that is, pD * pe and po(yl=) = pc(y(x). In what follows we define p(y x) == PD Pp(ylz) (c(y)x) Next, fixed X = C E X, we want to bound E [( Y, [.). To do that we use a result from Climaco & Garcke (2024): For fixed ă E and 2j Lx we have
consider scenario where Po may differ from Pc but the map connecting data location
E ( Y, mcc]] = / I(ã, y, mc)plyl@ddy
s S [( y. mm) MI m me)lplllaad + I 1 mc)plyladdy
(19)
< | - -0 + / (( y, mc)r(ul@)dd
The second inequality in 19 follows from the dix -ipsschti continuity of the error function. We can bound the remaining term as follows
J (00,, mc)plylaad)
13 p(yp)
/ [1z, E [Y[=) mc) I( EY m.) m2)1 p(y) 2 dy
+ / ((0), IE [Y|05 mc))(vl)))
< AN1 / l1 - E - p dy
+ X1y
[ Y
20

---

Published in Transactions on Machine Learning Research (02/2026)
+ / Blllag Y, mc) a.)
S Naye Aty / (Apllē 2,
+ / Ec ecpluloddy
s Saye AtpApllã 01ll2 ec.
The second inequality follows from the -iy-Lipschitz continuity of the error function and Jensen's inequality, which is used to obtain the conditional expectation in the integrand of the last term. The third inequality follows from the definition of labels' uncertainty, the >p-Lipschitz continuity of the conditional expectation of the random variable Y and the assumption that the expected crror on the training set is bounded by eg. The fourth inequality is obtained by taking out the constants from the integrals the second and third terms and noticing that, from the definition of p(ylæ), we have Syy
1.
By taking the minimum over By Cx get
[( Y, @c) <
min | æz1l2 (Aex + A1) + Aey + EC. myELx
(20)
Next, we define C = (Aex + Aty Ap) and apply 20 to 18h.
Consequently, we have
Epp [XX, Y, mc)]
min || - 2z 12c + A te ) (xx) pxx a,ECx
-exe) (x)) dx + Epc ((X,, Y, mc)]
X. Pxp 2PX2
(x)) - pxx (2:) dx min ||= - (px12((pxxx00
my afEhx
X.
pxp ZPNC
/
(Atye EE) (x) px- (2)) dæ + Epp ((X, mc)]
X.
PXp 2PX2
min Exx
x - 2zl12C (pxx (x) - pxx (x)) dx
X.
PXp 2PXC
(A1ye+ / p.oo (x))
/
pxe (x)
-Epe [1X,Y, Y,K,) mz)]
X.
PXD Zoa2
min || x, 12 (1 Px (x)(()) Ex
pNo (x)dx + (Ayeteec
1 - p.re (x))dx
+ Ep [1X,Y, M())
pxo (x))
X.
X. Pod 20xg
PXp 2PXC
PXp
|| 2,112 (1- Pxe (ax)
Pxx(1T)
)) (1sc+ee)
C sup xEX
min (2yExx
pxo (z)
pxe (x))x
+ Epe. M.))
X.
PXp <PNg
CCCxxx x (pxe (xxx)) (Nese + te) lxx pxxl Epe 1(X,Y,
21

---

Published in Transactions on Machine Learning Research (02/2026)
where Pe [px> pxxl== ==
f Px, (z)dx
Sx Px. (x) (pxx (x) < Pxc (x)) dæ is the probability, under Pxze
EXp <PXe
that randomly drawn sample is assigned higher likelihood by px: than by PXp It quantifies the mismatch
between Pxe. and Pxp. The last inequality follows from taking the supremum over a E X, taking the constant terms out of the integral and noticing that
ʃ Pxx (æ)dæ S Pxx (x))d== =. X.
X
Pxp 2PXC
20
D Asymptotic unbiasedness of the density estimations
In this appendix we show that the ANN data-driven estimates PXD and Px=, defined in (5) and derived from the finite sets xx, Lx C Rd, are asymptotically unbiased estimations of some densitics pxs and pxz respectively, for any 2 S k n. We assume that pxp and px; uniformly continuous and that Dx and Lx consist of random samples drawn from PX₂ and Pxe, respectively. To show this we use results from conCCooullos 1966), which recapture in the following theorem in formulation that is more suitable for purposes.
Theorem D.1. Let us consider d-dimensional Euclidean space X and K X R, Borel function X, such that
sup [K(x] oc, / [K()))de 0o, / K(x)dx= and xEX
lim | 1--00
(21)
Additionally, let us consider sequence of positive scalar numbers {ri C R such that lim T2 = 0. Let us (-200
also consider (m:)m C, m E N+ set of independent realization of random variable X with uriformly continuous distribution densily Then, for any a E X in the non-zero support of we have that
Σ K x 2;
Pm (x) m mm
(22)
I'm
is asymptotically unbiased estimator of p(x), i.e., lim (pm))=))]] p(x).
Proof- The theorem recaptures results from Theorem 3.1 of Cacoullos 1966)) which is proved using results from Thcorem 2.1 and Lemma 2.1 of the same paper. The sketch of the proof is as follows: First, fix X, and let.
x (m=xx)
Em <a) (rm)
K
(33
Tim
Then, under the mentioned assumptions on K and p. given a positive integer it is possible to show that
(x)) lim au - Epie (x)] = p(x)) / K 15' (x)dx.
(24)
Next, the theorem follows from noting that
Ep (x)) = E, (z)).
(25)
Next we provide corollary of the above theorem showing that the data-driven ENN density estimations Pr and phx are asymptotically unbiased estimators Pxp and Pxe, respectively, for any 2 < k < n.
Corollary D.2. Let us consider X' I and the function K d - + defined O.. Let us also consider Dr, X, n, N+ such that D,, = {a and La == {w, 1 are independent realizations of random variables X and X with uniformly continuous densities pxp and pxc, respectively. Next, consider the
22

---

Published in Transactions on Machine Learning Research (02/2026)
points 2, Rd in the non-zero support of pxo and Pxzz respectivcly, and the kNN data-driven density estimations fxxo. (x) and f'xe, (x) defined as follows
Σ B,ED,
K
Ri (x)
Σ K
2; D.n (#)
and Pxc, (x) = 2t ELs
Pxr. (
(26)
(1 (2))((()))
(x))(())
where, for each E E Rd (+) min
min ayEL,
- - 22112 Pk. p with the scalar > 0 arbitrary
small and (t) the distance between and its k-nearest neighbor in Dn Then we have that, for any < n, Pxx. (x) and P'xe, (x) are asymptotically unbiased estimators of (xx((a) and pxc (T), respectively,
i.e.,
lim Exx, Pxo, (x)] Pxp (2c) and lim Exxe I (t) Pxc (.))
(27)
b-000
Proof. First note that the function K I2d + IR+ defined in 6 satisfies all the requirements in 21 In particular, we have that
1 Va
1 and / K(x))da Va (0,1))
/
sup [x()] EER
ldæ 1,
(28)
where Va is the volume of the d-dimensional unit ball, which we write as (O = {ar e
Rdd such that ||œl|| s 1}. Moreover, have that [K(x)] = 0 for ||0||| 2 1, thus, lim || [ K [()){()) 0.
2
The only thing left to show apply Theorem D.1 to pxo, (x) and pxc, (ω) that lim b2 ( and
6000
lim r (x)= 0. n-000
To show that lim rf,n(() 0 it is sufficient to observe that lim min - 2,112 0 because the number 6-000
bo0o E,CLs
of samples in La increases, the distance between E and its nearest neighbor in Lo decreases, tending to zero. Morcover, lim 5x 0. Similarly, we have that lim "f,n()) = from the fact that lim (k.n(z) = 0 h-00
n=000
n=+00
which follows from the observation that as the number of samples in Dn increases, the distance between æ and its k-nearest neighbor decreases, tending to zero. Thus, we can apply Theorem D.1 to pkx (a) and
Pix,, (Ø) showing that they are asymptotically unbiased estimators of (x) and px, (z), respectively, for any 2 k n.
E Proof Theorem 7.1
Proof. Let us fix the budget b E N and define, for each i = I,...,b 1, C, = fI1...., 2z} as the set of cardinality i obtained after i - iterations of the "While" loop in line 3 of Algorithm [ To simplify the notation, for the rest of the proof, for each Lx C Dx we define Wex == W Ex. Dx omitting the k and Dx from the notation of the estimated weighted fill distance. The following proof consists of three main steps.
Step 1 The first step of the proof consists of showing that for each 1 1 < b we have
Wea1 $ Wer
To prove this first step we notice that C, C, U 0:41. Thus, for each æ E Dx we have that
min C
| 21yle S min || - 2zy122
eyec.
This because adding a point to the selected set C, ensures that the distance from any a Dx to its closest selected element either remains the same decreases. Consequently, wh (m) w/2 (m) also holds.
23

---

Published in Transactions on Machine Learning Research (02/2026)
To see this, recall that w/, (a:) is the number of data points in Dx contained within the ball centered at with radius r2, (z) = min min,,ee, || æy122 :2))) where pa(x) the distance between and its k-th nearest neighbor and ex positive scalar value, which consider arbitrary small. Adding a point to the selected set & ensures that the distance between any æ E Dx and its closest selected element does not increase. As a result, the value of r (z) is non-increasing, which in turn implics that the weights w (2) are also non-increasing. Therefore, we have that for each 1 1 <b+1
min | ae-aayl224 2:11222222 2441 (a:) S min 8, ElE44
| 2z 22 (ar):
2, E,EL,
Since the above inequality holds for each a E Dx, by taking the maximum over the points in Dx we prove the first claim.
Step 2
The second step of the proof shows that for each 2 sisb+ and s <<< < S we have that
We, S [m 21ll2w22m (mmm;
(29)
where am and an are the points selected by Algorithm D the m-th and 1-th iterations, respectively. To prove this second step we proceed by induction. For the base step we have i = 2, m 2, = 1. Then we have
Wc, = max =EDx
||
x 11,22, (x) = || 21 1aw2, (202)
which verifies the base step. The second equality follows from how the selection strategy in Algorithm | is defined. Next, let us assune the assumption in 29 is true for i- 1. Then we have for each < < m Si-1
W S WC I |m
(m
Where the first incquality follows from the first step of the proof and the second inequality is our inductive assumption. Now notice that for each 1 S < i we have
We. = min || - x, 22llo (xx) I || - x, 1211222 (x;). m.cli11
which proves the inductive step.
Step 3 Consider now a set C C Dx, with |C|= =. Observe that by the definition of weighted fill distance we have that for each x E Dx there exists e C such that wp(x)]l= - cl|2 < Wc. Next, notice that given C1+1, with [Cozll b+ I, selected with Algorithm I by the pigeonhole principle we have that there b + 1 that have common closest element C. Therefore,
exists Im, xy Lbt1 with 1 < 1 max [|mm @llaw)((mm)) | 2| (x))) We. Thus, have
Wc, < |m0m 21 1aw Em (Im)
< (I| @m E|22 + ||2|| E(l2) w/m (xm)
[mmm c112w//( (Z))) + ||E; (2 wh wm (0m)
(30)
2 Dm (Im)
2kWc.
The first inequality follows from the second step of the proof, the second inequality follows from the triangular incquality of the distance considered, the third and fifth incqualities follow from the fact that, by definition, we have 1 I (x)) < & for all æ E Dx and Dx. Since the above inequality holds for each Dx, it holds for the optimal subset Ox well.
24

---

Published in Transactions on Machine Learning Research (02/2026)
F Computational efficiency DA-FPS
Given the novelty of DA-FPS, it is important to investigate its computational complexity. DA-FPS can be implemented using O(DD)) memory and the greedy selection takes (db[D]k) time. |D] is the amount of available data points, k the amount of nearest neighbors is the amount of points we select and d is the dimension of the data points. The computational cost of DA-FPS is determined by the weights update (line 7 im Algorithm ! taking O(d[D() at each of the b iterations. In the current implementation the weights update involves iterating over all points in 'D and compute the distances between the new selected point and the points' k-nearest neighbors, which costs Odd[Dk)). Note that, initializing DA-FPS requires the computation of the k-nearest neighbors matrix, which can be a potential bottleneck. In our implementation we query the k-nearest neighbors using the cKDtree algorithm from the SciPy python library (Virtanen ct al. 2020 The algorithm takes Odd[D) log (D]) for building the balanced tree in the worst case scenario. After that, it queries the k-nearest neighbors with a worst-case cost of (( and an average cost of (log (D), Additionally, it is important to note that if the nearest neighborhood size to compute the weights as in g is set to k = 1, the optimization problem in (10) coincides with the fill distance minimization problem and Algorithm [ reduces to the well known Farthest Point Sampling algorithm (FPS); thus providing 2-optimal solution (Har-Peled) (001)). which the best approximation factor attainable in polynomial time with theoretical guarantees (Hochbaum & Shmoys 1985).
consider for the density approximation, b
We implemented two versions of DA-FPS: one using NumPy (van der Walt et al. 2011 and the other with PyTorrc (Paszke et al.) 2019). The average computation times (over five runs) to select 20% of data points from QM7, QM8, QM9, and ZINC are respectively as follows: NumPy - 6, 48, 1974, and 70 seconds; PyTorch- - 4, 31, 968, and 33 seconds. This was conducted on a 48-core CPU with 384 GB RAM. DA-FPS was initialized with u and = 100 independently of the dataset. DA-FPS' PyTorch implementation is faster than the NunPy implementation. This is because PyTTrrch can run computations exploiting multiple CPU cores. It uses libraries like OpenMP ODenMP(Dagum
(Dagum & Menon 1998) and Math Kernel Library (Wang et al. 2014 to perform operations on multiple CPU cores, leading to faster computations.
G Datasets
This appendix draws from (Climaco & Garcke| 2024 and provides additional information related to the datasots, preprocessing procedurcs and molccular descriptors used for the experiments reported in Section
QM7 (lum & Reymond 2009 Rupp et al. 2012) contains 7,165 small organic molecules (up to 23 atoms, including C, N, O, S). Each molecule is represented by the upper triangular entries of its Coulomb ma- trix (Rupp et al., 2012), resulting in a feature vector in 2R2 The regression target is the atomization enorgy (in eV), iee. the energy required to separate all atoms in a molecule.
QM8 (Ruddigkeit et al.) 2012 Ramakrishnan et al., 2015p contains 21,766 organic molecules with up to 8 heavy atoms. For each molecule it provides its SMILES representation. We use Mordred (Moriwaki et all, 2018) to compute 1,826 molecular descriptors from SMILES, set missing values to zero, remove 530 features with zero variance, and normalize all features to (0, 1).Thus, each molecule in QM8 is represented by a vector in I21996 We then apply PCA to reduce the feature dimension to 100. The regression target is the lowest singlet transition energy (E1, in eV), computed using the PBEO functional.
QM9 [Ruddigkeit al., 2012 Ramakrishnan al. 2014) consists of 130,202 small organic molecules with up to heavy atoms. For each molecule it provides its SMILES string and 19 computed properties. Following along (Climaco & Garckel 2024) we preprocess QM9 by removing molecules that fail consistency checks, cannot be parsed by RDKit (Landrum) 2012), or have duplicate SMILES. Molecular features are computed using Mordred (Moriwaki et al.] (018),, with missing values set to zero, features with zero variance removed, normalization to (0, 1), and PCA to 100 dimensions. The regression target is the HOMO-LUMO energy gap (in eV), an important indicator of molecular stability.
The ZINC dataset (Gómez- Boannrell et al. 2018) consists of about 250,000 molecules with up to 38 heavy atoms selected from the ZINC database (Sterling& & Irwin 2015), which contains over 120 million purchasable
25

---

Published in Transactions on Machine Learning Research (02/2026)
organic molecules. To reduce the computational effort of our analysis, we follow along Dwivedi et al. (2023) and consider a subset of the ZINC dataset. Specifically, we use subset of ZINC consisting of 24000 molecules selected uniformly at random. The molecular representation we employ is based on the Mordred (Moriwaki ict al. 2018) library, as for the QM8 and QM9 datascts. We normalize the features provided by the Mordred library, to scale them independently in the interval (0, 1). Again, we set to zero all the descriptor values that Mordred could not compute, removed the features for which the values across the dataset have zero variance and applied PCA to reduce the dimension of the feature vectors to 100. The label value to predict is the water-octanal partition coefficient (LogP), describing the molecules' solubility.
G.1 Datasets for additional experiments in Appendix K
In this section we provide a more detailed description of the additional datasets unrelated quantum chemistry used for experiments in Appendix K
including information on the preprocessing procodures.
The Concrete Compressive Strength dataset (Yeh 1998) downloaded from the UCI Machine Learning Repository (Dua& & Graff] 2017) contains 1030 data points and is used for regression tasks. It includes eight features: the amount of cement, blast furnace slag, fly ash, water, superplasticizer, coarse aggregate, and fine aggregate, as well as the age of the concrete in days. We remove 34 data points having identical descriptors as at least one other point in the dataset, obtaining a reduced dataset of 996 data points. Furthermore, we normalize the features to scale them independently in the interval (0, 1). The target variable is the comprossive strength of the concrete, measured in megapascals (MPa). This dataset is used to test machine learning models to predict material properties.
In the additional experiments illustrated in Appendix K we use the Twinning algorithm implementation from Vakayil & Joseph| (2022), which selects subsets based on an integer r, the inverse of the partitioning ratio. Since the algorithm strictly partitions the dataset according to this ratio, we remove 6 points from the Conerete datasot, resulting a reduced dataset with 990 points. The points were selected randomly. This adjustment ensures that the subset size determined by the Twinning algorithm matches the percentages used to select the subsets, eliminating any discrepancies. Similarly, for the experiments in Appendix K we remove 66 points from the QM8 dataset, creating a reduced dataset of 21 20000 points. QM8 is preprocessed with the same procedure used in Scction S
The Electrical Grid Stability Simulated dataset from the UCI Machine Learning Repository Duua & Graff 2017) contains 10000 data points and is designed for both classification and regression tasks. Each data point in this dataset is represented by 12 features that describe characteristies of a simulated power grid. We normalize the features to scale them independently in the interval (0, For regression tasks, the target variable is the stability margin, which quantifies the power grid's stability.
H Data assumptions
We note that, for the experiments to be consistent with the theory the datascts we use should respect the data assumptions required in Theorem 1.2 We focus on Assumption B.2 more specifically Formula (6), indicating that if two data points have close representations in the feature space, then the conditional expectations of the associated labels are also close. This assumption is necessary to attain the theoretical result in Theorem 4.2
For the QM datasots, the data assumptions have been already tested in Climaco & Garcke (2024) where the authors perform experiments related to FPS. However, for the experiments with DA-FPS we use different feature vectors. Thus, it is worth to verify whether the new feature vectors we consider still respect the required assumptions or not. We use the same procedure employed in Climaco & Garcke (2024) and study the correlation between pairwise distances in the feature and labels spaces by computing the Pcarson's 's (pp) and Spearman's (px) correlation coefficients. We recall that these coefficients measure and quantily the correlation between the quantities of interest. We compute the correlation coefficients for the pairwise distances in the feature and label spaces on the QM7, QM8, QM9 and ZINC. We consider the features and labels used for the experiments illustrated in Section g and Appendix M Due to memory issue in storing the distance matrix, for the QM9 we computed the correlation coefficients 50% of randomly selected data
26

---

Published in Transactions on Machine Learning Research (02/2026)
points. We selected random subsets and computed the associated correlation coefficients for five times. The results we report for the QM9 are the average over the five runs. The computed coefficients are 0.15, 0.22, 0.26 and 0.22 for Pp. and 0.27, 0.19, 0.22 and 0.19 forp.: for QM7, QM8, QM9 and ZLNC, respectively. Thus, both the Pearson's 's and Spearman's 's coefficients indicate a positive correlation between the pairwise distances of the data features and labels, suggesting that the data assumption considered Theorem 4.2 is respected for each of the considered datasots.
Regression models: KRR and FNN
In this work, we follow along Climaco Garcke (2024) and use two regression models already used in previous works for molecular property prediction: kernel ridge regression with a Gaussian kernel (KRR) and feed-forward neural networks (FNN). In this appendix we recapture the key aspects of the KRR and FNN regression models. For more in depth analysis of KRR and FNN for molecular property prediction see Deringer et al. (2021 and Pinheiro et al. (020)), respectively.
Kernel ridge regression (KRR) is a machine learning method that combines ridge regression with kernel functions to perform regression in a flexible, non-linear way (Deringer et al. 2021). In this work, we use the Gaussian kernel. Given two data points z dt E X, the Gaussian kernel defined as k( my)) == e e->,,,,- m1 where > 0 is a parameter that controls the width of the kernel. Suppose we have a training set L = {(1,,,)) 1;) and a set of weights a = =[n,, ((1,00....,,.)) E RR, the predicted label value mc.a (x) E R associated with a data location æ E Rd of a new data point is defined as follows (g,((x) == Σin E= ayk(1, æz). The scalar (x) is the label predicted by the KRR method associated with the training data locations {ar (e)))=1 and weights a. The goal of KRR is to find weights 021,02...... that minimize the following
objective:
a arg Σ (mc(z;) - -;)² + da" K a.
(31)
a
where K is the kernel matrix with entries K2(g,r) kaag a,,, and À 0 is regularization parameter that helps prevent overfitting, The solution to this problem is given by: (K + XI)-'y, where y (91, ....... "o]"" To predict the label for a new data point æ E X, we use: y(x) == mc(x) = (+())==' a,k(x, 2,). The hyperparameters y and Ả are selected by cross-validation grid search random training subsets. For each training set size we select the best pairs of parameters. Next, we compute the average of the best pairs across all set sizes and use it for testing. The cross- validation tensor-grid uses 6 values per parameter from 10-6 to 10-1, We use the same set of hyperparameters for all selection strategies and training set sizes so that the only variable affecting the model performances is the selected training set.
Feed-forward neural networks (FNNs) GGoddfelow et al. 2016) are a type of deep neural network used for regression. An FNN predicts the label y(œ) for input E X by passing it through sequence of layers. With / layers, the output is: v(m) 4/2 oz e v/- 0 (b:)
(32)
where each vo is an affine transformation (11(x)) W. + b:) and each o; is nonlinear activation function (here, ReLU). Following (Pinheiro et al. 2020), we use = 3 layers and ReLU activations. The weights W; and biases b, are learned by minimizing the mean absolute error on the training set. To train the FNN and learn the weight matrices W, and biases b,, we use the PyTorch (Paszke et al. 2019) Adam optimizer with learning rate of 0.001, betas (0.9, 0.999), and weight decay 0.001. We use a batch size of 516 and train for 1000 epochs, regardless of the dataset. To ensure that performance differences are only due to the choice of training set, we always initialize the FNN with the same random weights
27

---

Published in Transactions on Machine Learning Research (02/2020)
1.8
RDM
0.42
0.36
FaciltLLocation
0.40
0.34
RMSE [eV]
kimedodds++
0.38
RMSE [eV]
1.4
FPS
0.32
DA-FPS
0.36
0.34
0.32
0.28
0.30
0.8
0.26
5%
10%
16%
20%
5%
10%
15%
20%
5%
10%
15%
20%
Amount training samples
Amount of training samples
Amount training samples
0.44
0.40
2.50
0.42
2.25
0.40
[eV]
RMSE [ev]
0.36
0.38
1.75
0.36
0.34
1.50
0.34
0.32
1.25
0.30
1.00
0.30
0.75
0.28
5%
10% 15%
20%
5%
10%
15%
20%
5%
10%
15%
20%
Amount of training samples
Amount of training samples
Amount training samples
(a) QM7
(b) QM8
(c) QM9
Figure 3: RMSE for regression tasks on QM datasets using KRR with Gaussian kernel (top row) and FNN (bottom row) trained on sets of various sizes, expressed as a percentage of the available data points, and selected with different sampling strategies. Error bars represent the standard deviation over five runs. The performances of FPS (blue lines) may be close to that of DA-FPS (red lines) when we consider the RMSE, particularly for larger training set sizes, e-g,, on QM7 and for larger set sizes on QM8. Nevertheless, DA-FPS still leads to the most competitive performances across datascts. The legend in the leftmost graph in the top row applies to all graphs. DA-FPS is initialized with Lx 0, k 100, and u = 3% of the available data, independently of the dataset.
J Evaluation DA-FPS using the root mean squared error (RMSE)
In this appendix we use the root mean squared error (RMSE) to evaluate the performance of DA-FPS against the baselines used in Section g Given true larget values {y:) and the predicted values ( the RMSE is defined as RMSE data pool. Similarly to the MAE, the RMSE provides information on the average quality of the prediction. The difference is in the fact that RMSE penalizes large errors more than the MAE, thus providing insight on the robustness of the predictions. The graphs in Fig. 3 compare the performances of DA-FPS with the baselines and illustrate the RMSE of the predictions for the KRR (top row) and FNN (bottom row). The illustrated results suggest that the performances of FPS may be closer to that of DA-FPS when we consider the RMSE, This is particularly evident on the smaller QM7 and for larger set sizes on the QM8. Note that the RMSE penalizes large errors more than the MAE, thus giving more relevance to outlier error values. As we know from Climaco & Garcke (2024). FPS leads to a substantial decrease in maximum prediction error and hence reduces the amount and magnitude of large error values. Nevertheless, DA-FPS still leads to competitive performances in terms of the RMSE, highlighting its robustness against large errors.
n. Ei 1B: 32, where ny is the number of unlabeled points in the
K Additional experiments
In this section we present experiments considering two additional datasets unrelated to quantum chemistry, two additional sampling strategics, and one additional kernel method. The new datasets are the Conerete Compressive Strength dataset and the Electrical Grid Stability Simulated Dataset, from the public UCI ML repository (Dua& & Graff 2017). The Electrical Grid Stability dataset contains 10000 data points represented
28

---

Published in Transactions on Machine Learning Research (02/2026)
by 12-dimensional vectors. The target variable for regression is the stability margin (stab), reflecting grid stability. The Concrete dataset consists of 1030 data points described by 8-dimensional vectors. The target variable is the compressive strength in megapascals (MPa). In Section G.1 we provide additional details on the datasets and preprocessing procedures. We also consider the QM8 to evaluate the performance of the additional sampling strategies and regression model in a quanlum chemistry context.
The additional sampling strategies are the Twinning algorithm (Vakayil & Joseph 2022). and the facility location with Gaussian similarity function (FacLocG) defined in Bhhtt et al. (2024 Fine-tuning is required for the Gaussian width of the similarity function in facility location, and we follow the methodology outlined in Bhatt et al. (2024), with complete details and hyperparancters described in Section M. of this appendix. Section [M.] also includes the hyperparameters used for DA-FPS. In these experiments, we compare DA-FPS with the additional sampling strategies alongside the baseline methods used in the previous section, including RDM, k-medoids+++, facility location and FPS. The Twinning algorithm implementation from Vakayil & Joseph (2022) only allows the selection of subsets of the size that can be expressed as an integer "r" representing the inverse of the partitioning ratio, i.e., for obtaining a training subset consisting of 20% of the data points, must set r 100 5. Consequently, to use the Twinning algorithm, we consider training set sizes similar to those considered in the previous section, but that can be expressed as an integer ratio. Specifically, we consider training set sizes of 5%, 10%, 16.67% and 20% associated with a ratio of 20, 10, 6 and 5, respectively.
We use KRR with a Cauchy kernel as an additional regression method. We take the definition of Cauchy kernel used in Basak (2008). We describe the Cauchy kernel, its hyperparameters and the hyperparameters' optimization process in later in Section M.2 For each sampling strategy and set size, the training set selection process is independently run five times considering different initializations, that is, different initial point random seed. Accordingly, we report for each analyzed model the average and the standard deviation of the results for five runs. We consider three distinct evaluation metrics to analyze prediction performance. We use the MAE and RMSE, introduced in Section g and Appendix J respectivoly, which quantify the average quality of the prediction. In addition, we also compute the Maximum Absolute Error (MAXAE) of the predictions. The MAXAE is defined as MAXAE:= maxişisn, ly: - , where yi and i/ are the true and predicted values, respectively. The MAXAE provides information the worst-case sccnario, and thus the robustness of the model's predictions. Fig. presents the regression task results the Concrete dataset, the Electrical Grid dataset, and the QM8 dataset, using KRR with Cauchy kernel trained on datasets of various sizes, selected with different strategies. The top row of the figure shows the MAE of the predictions, the primary metric of interest. These results suggest that, overall, DA-FPS outperforms other methods across all datasets. The only exception occurs with a training set size of 5% on the QM8 dataset, where the Twinning approach performs better. Generally, the MAE plots indicate that Twinning is the second-best method regarding MAE. The middle row of Fig. 4 presents the RMSE results, which indicate that DA-FPS consistently achieves strong performance, ranking as either the best or second-best method across all scenarios. Unlike the MAE results, where Twinning is the second best-performing approach, the RMSE results highlight FPS as the method most closely aligned with DA-FPS in terms of performance. This distinction underscores the reliability of DA-FPS across varying evaluation metries. Since RMSE assigns greater weight to larger prediction errors compared to MAE, these findings emphasize the capability of DA- FPS to manage and mitigate significant prediction crrors effectively. The bottom row of Fig. g illustrates the MAXAE, further indicating DA-FPS as either the best or second-best method in every scenario. FPS emerges the other best performing. It is worth to note that while the Twinning approach is the second best performing approach it terms of the MAE, it performs poorly in terms of MAXAE, especially when compared to DA-FPS and FPS. For example, Twinning is the worst-performing algorithm on the Concrete dataset with a training set size of 5% and the second-worst on the QMS dataset, regardless of training set size. In both cases, Twinning performs even worse than random sampling. The results in Fig. | underscore the effectiveness and adaptability of DA-FPS across different datasets, sampling strategies, and error metrics. These additional experiments further indicate that DA-FPS is robust and versatile approach for various regression tasks not only constrained to the quantum-chemistry domain.
29

---

Published in Transactions on Machine Learning Research (02/2026)
Twinning
FacLoc-G
FacilRyLocation
k-medoids+++
RDM
FP5
DA-FPS
0.009
0.350
9
0.325
MAE [MPa]
MAE (stab)
0.008
MAE [ev]
8
0.300
0.275
0.007
0.250
0.006
0.225
6
5%
10%
16.67%
20%
5%
10%
16.67% 20%
5%
10%
16.67% 20%
Amount of training samples
Amount of training samples
Amount of training samples
12
0.012
0.45
RMSE [MPa]
11
RMSE (stab)
RMSE [eV]
0.011
0.40
10
0.010
0.35
0.009
0.30
0.008
5%
10%
16.67%
20%
5%
10%
16.67% 20%
5%
10%
16.67% 20%
Amount of training samples
Amount of training samples
Amount of training samples
60
0.10
MAXAE [MPa]
MAXAE (stab)
0.09
MAXAE [ev]
8
50
0.08
6
40
0.07
4
0.06
30
0.05
2
5%
10% 16.67% 20%
5%
10%
16.67% 20%
5%
10%
16.67% 20%
Amount of training samples
Amount of training samples
Amount of training samples
(a) Concrete
(b) Electrical Grid
(c) QM8
Figure 4: Results for regression tasks the Concrete Compressive Strength, Electrical Grid Stability, and QM8 datasets. We use KRR with the Cauchy kernel trained on sets of various sizes, expressed as a percentage of the available data points, and selected with different sampling strategies. MAE (top row), RMSE (middle row) and MAXAE (bottom row) are shown for each training set size and sampling approach. Error bars represent the standard deviation of the results over five runs. DA-FPS (red lines) consistently showcases competitive performances across all metrics. For MAE, DA-FPS generally outperforms other methods, except Twinning (black lines) at 5% training set size QM8. Twinning is the second-best method in terms of the MAE. For the RMSE, DA-FPS consistently ranks the best or second-best. MAXAE results confirm DA-FPS as the best second-approach, with FPS (blue lines) as the other most competitive approach. As for Twinning, despite strong MAE performance, it under-performm in MAXAE, sometimes worse than random sampling (green lincs). Overall, DA-FPS delivers competitive performances across all metrics. DA-FPS initialized with Lx and и 3%, 1% and 3% and = 100, 300 and 300 for the QM8, Concrete dataset and electricity dataset, respectively.
30

---

Published in Transactions on Machine Learning Research (02/2026)
0.32
RDM
Facilylocatoon
0.9
k-medoids**
MAE [eV]
TPS RDM
MAE [eV]
FPS-FacLoo
0.28
0.24
0.8
MAE
0.26
0.22
0.8
0.22
0.20
5%
10%
15%
20%
5%
10%
15%
20%
5%
10%
15%
20%
Amount training samples
Amount of training samples
Amount of training samples
0.32
1.1
0.28
0.30
MAE [eV]
1.0
MAE [eV]
MAE [eV]
0.28
0.26
0.8
0.24
0.7
0.24
0.22
6%
10% 15%
20%
5%
10%
20%
10%
15%
20%
Amount of training samples
Amount of training samples
Amount of training samples
(a) QM7
(b) QM8
(c) QM9
Figure 5: MAE for regression tasks QM datasets using KRR with Gaussian kernel (top row) and FNN (bottom row) trained on sets of various sizes, expressed a percentage of the available data points, and selected with different sampling strategies. Error bars represent the standard deviation over five runs. The modified versions of the baselines (dashed lines) lead to better performance than the respective original baselines (solid lines). The legend in the leftmost graph in the top row applies to all graphs. The modified basclines sample the first 3% of the points using FPS.
L Combining FPS with baselines
In this appendix empirically investigate the benefits of combining the baseline sampling approaches used in Section wootion&Siihh with FPS. We consider modified versions of the RDM, Facility location and k-medoids++ These modified versions of the basclines first select a prefixed amount of points with the FPS, the same amount we would consider for the DA-FPS, and then augment. the selected set by sampling from the remaining points in the data pool according to their specific criteria. Consequently, in the early stage of the sampling process, the sets selected with our proposed approach coincide with those selected with FPS and the modified baselines. We refer to the modification of the baselines FPS-RDM, FPS-FacLoc and FPS-k-modoids The experiments in this appendix are performed considering the same experimental set up as in Section S
Fig. 5) shows that FPS-RDM, FPS-FacLoc and UPSs---mdoiids++ consistently outperform the associated baselines RDM, facility location and k-medoids++ in terms of the MAE for both, the KRR (top row) and FNN (bottom row). These results suggest that modifying the baselines by initially sampling with FPS leads reduction of the MAE independently of the datasct and trained model.
Fig. @compares DA-FPS with the modified baselines. Overall, DA-FPS leads to lower MAE of the regression models. Looking at the results in Fig. 6 obtained with FNN (bottom row), where DA-FPS is outperformed by one of the modified baselines: on the smaller QM7 and on the QM9 for the 5% training set size. These results suggest that, the advantages of using DA-FPS with respect to the modified baselines may be less evident on smaller datasets and training set sizes (< 5% of the available points), when using the FNN as learning model. Recall that, FNN predictions are prone to instability for lower training set sizes. Nonetheless, our experiments still indicate that, overall, DA-FPS more competi- tive than the modified baselines in terms of the MAE of the predictions. In particular, modified baseline
highlight two scenarios
31

---

Published in Transactions on Machine Learning Research (02/2026)
FPS-DMM
0.30
FPS-FacLoC
0.25
FPS4kmedadds++
MAE [eV]
DA-FPS
MAE [eV]
0.28
0.8
0.23
0.26
MAE
0.24
0.21
0.8
0.22
5%
10%
15%
20%
5%
10%
15%
20%
5%
10%
15%
20%
Amount training samples
Amount of training samples
Amount of training samples
0.32
1.0
0.30
MAE [eV]
MAE [ev]
MAE [eV]
0.9
0.28
0.26
0.8
0.24
0.24
10% 15%
20%
5%
10%
20%
15%
20%
Amount training samples
Amount of training samples
Amount of training samples
(a) QM7
(b) QM8
(c) QM9
Figure 6: MAE for regression tasks QM datasets using KRR with Gaussian kernel (top row) and FNN (bottom row) trained on sets of various sizes, expressed a percentage of the available data points, and selected with different sampling strategies. Error bars represent the standard deviation over five runs. DA- FPS (red lines) perferrs the modified baselines. The legend in the leftmost graph in the top row applies to all graphs. DA-FPS is initialized with Cx = 0, k = 100, and u = 3% of the available data, independently of the datasct. The modified baselines coincide with DA-FPS until 3% of the data is selected
can consistently outperform DA-FPS any the datasets considered. Moreover, according to our experi- ments, the comparative effectiveness of the modified basclines, in terms of the MAE, depends on the dataset considered, that is, the underlying data distribution. For instance, in Fig. G if consider KRR as the regression model (top row), FPS-RDM outperforms FPS-k-medoids++ QM8. The results with DA-FPS appear to be more robust to changes in the datasets.
QM9. The opposite is true
M Ablation study DA-FPS hyperparameters on ZINC dataset
In this appendix we analyze how the performances of DA-FPS may be affected as we vary the hyperparameter u, defining the amount of samples initially selected with uniform weights and the hyperparameter k, defining the amount of k-ncarest neighbors considered for computing the weights. We perform this analysis the ZINC dataset and use the KRR and FNN as regression models. We consider a version of the ZINC dataset consisting of 24000 molecules represented as vectors 100 We aim to predict the molecules' LogP value, describing the molecules' solubility. In Appendix G we provide the details on the descriptors, label values, and preprocessing procedures we use. ZINC provides one additional application scenario those already considered in Section
Hyperparameter "z"
To study how DA-FPS performs as the hyperparameter u varies, we fix = 300. The graphs in Fig. 7 illustrate how the performance of DA-FPS (dashed lines) changes as the parameter u varies, compared the bascline approaches (solid lines) for both, the KRR (top row) and FNN (bottom row). We consider 0%, 1%, 2%, 3%. For the low data budget of 5%, that random sampling and k-medoids+++ lead to
32

---

Published in Transactions on Machine Learning Research (02/2020)
0.26
RBV
0.26
FPS4OM
0.28
FPS-DM
FacilMaaatoo
MAE [LogP]
0..44
DA-PR.0
MAE [Log]] LogPo
0.24
(ogP)80
MAE [LogP]
0.24
FPB
D4-175
D6-PS
DA-FP8.2
DA-PSS
0.22
0.22
0.22
0.20
0.20
0.20
0.18
5%
10%
15%
20%
5%
10%
15%
20%
5%
10%
15%
20%
Amount of training samples
Amount of training samples
Amount of training samples
Rby
FPS-ROM
FPS-ADM
0.28
0.28
0.28
Focilyyacatoon
medollie
kraadsida
MAE [LogP] (ogP)o.0
FPB
MAE [LogP]
0.26
DA FP3.0
MAE [LogP] Logg))
0:26
34 RPB
0.26
DA FPB
D4-FPS_
DA-FP8
0.24
DA-FPS
0.24
0.24
0.22
0.22
0.22
0.20
0.20
0.20
5%
10%
15%
20%
5%
10%
15%
20%
5%
10%
15%
20%
Amount of training samples
Amount of training samples
Amount of training samples
(a) u- 0%,1 1%, 2%, 3%
(b) u=1%
(c) u=3%
Figure 7: Sensitivity study DA-FPS hyperparameter "u": MAE for regression tasks on ZINC using KRR (top row) and FNN (bottom row) trained on sets of various sizes, expressed a percentage of the available data points, and selected with different sampling strategies. DA-FPS is implemented with k = 300 and considering various values for u. In (a) DA-FPS is implemented with u = 0%, 1%, 2%, 3%. DA-FPS and the modified baselines are implemented with u = 1% in (b) and u = 3% in (c). Error bars represent the standard deviation over five runs. DA-FPS initialized with Lx = and 300.
better results than DA-FPS, particularly if we consider larger values of u for DA-FPS. This is more evident with KRR. On the contrary, for the larger training set sizes of 10,, 15% and 20%, DA-FPS consistently outperforms all the baselines independently of the choice of u. Moreover, for the smallest training set size of 5% we see that the smaller the value of u the more accurate the average predictions obtained considering training set selected with DA-FPS, independently of the regression model. We note that, such a trend may change or even be reverted if we consider larger training set sizes of 10,, 15% and 20%. This particularly evident in the graph of Fig. 7 related to the FNN model (bottom row), where, for training set sizes of 15% and 20%, the larger the value of u the more accurate the average predictions with DA-FPS. Thus, from our experiments, we see that the parameter may affect the performance of DA-FPS differently, depending on the training set size and regression model considered. Nonetheless, for larger training set sizes the increased effectiveness of DA-FPS compared to the baselines is consistent across the different choices of u.
The graphs in Fig. 7 compare DA-FPS and the modified baselines. They show the results obtained by initializing DA-FPS and the modificd basclines with 1% of the available data points. That is, DA-FPS and the modified baselines coincide with FPS until 1% of the available data points has been selected. The results align with those of the experiments performed in Section & In particular, the graphs in Fig. 7 show that, DA-FPS tends to outperform the modified basclines in terms of the MAE of the regression models, particularly for larger training set sizes (> 5%).
Fig. 7p illustrates the performance of DA-FPS and the modified baselines considering u = 3% of the available data. The graphs suggest that, by increasing the parameter form 1% to 3% the gap between the modified basclines and DA-FPS reduces for KRR and increases FNN. This indicates that the choice of u has an impact the relative effectiveness of the modified baselines and DA-FPS and that such impact also depends on
33

---

Published in Transactions on Machine Learning Research (02/2026)
0.26
30
0.28
290
MAE [LogP]
0.24
k 300
MAE (LogP]
0.26
k 310
0.22
k 3000
0.24
0.22
0.20
0.20
0.18
5%
10%
15%
2
5%
10% 15%
20%
Amount of training samples
Amount of training samples
(a) KRR.
(b) FNN
Figure Sensitivily study DA-FPS hyperparameter "\": MAE for regression lasks on ZINC using KRR with Gaussian kernel (a) and FNN (b) trained on of various sizes, and selected with DA-FPS considering
1% and & 30, 290, 300, 310, 3000. Error bars represent the standard deviation over five runs. The per- formance of DA-FPS remains stable when the hyperparameter k is within certain range (A 290, 300, 310). Choosing & too small may lead to notable performance decline. Legend in the left graph applies to both graphs DA-FPS is initialized with Lx = and = 1% of the available data.
the model used for the regression task. Nonetheless, independently the choice DA-FPS is the best or second best performing for the larger training set sizes (> 10%).
Hyperparameter "k"
To study how DA-FPS performs as the hyperparameter k varies, we fix w-1%. We choose u=1% because, according to the results in Fig. 7 it provides the better overall results across the various training set sizes considered. Fig. X reports experiments where we investigate the effects of varying the DA-FPS parameter k for regression tasks with KRR and FNN on the ZINC dataset. We select training sets of various sizes with DA-FPS, considering different values of (k: 30, 290, 300, 310,3000)
These exemplary results suggest that the proposed value k = 300 (used for the experiments in Fig. falls within a range where small changes would not negatively impact the effectiveness of our approach on the ZINC datasets. Using k = 290 and 310 does not lead to substantial differences, independently of the training set size. However, applying changes of an order magnitude to could potentially affect the approach. For instance, changing the value of i 300 by factor of to 30 lcads a significant decrease performance for the training set size of 5%, independently of the regression model. The rough magnitude of likely depends the data dimension and distribution and is generally investigated in the context. of density estimation. We expect further insights from that domain.
M.1 Hyperparameter optimization for additional experiments
In this section we follow along Bhatt et al. 2024 and describe the fine-tuning process for optimizing the hyperparameters of the facility location algorithm with the Gaussian similarity function. In addition, we report the hyperparamoters considered for DA-FPS used for the additional experiments.
For the facility location method using the Gaussian similarity function, the fine-tuning process involves selecting an appropriate kernel width, denoted as 7, prevent the function's gains from saturating when new data points are added to the training set. That is, given finite pool of data points Dx R", subset. Sn. Dx. consisting of l elements, and f(Sx) Σ max e > alla e B value of the facility location function
xEDx #ES,
evaluated on St. we aim to choose y maximize the gains f(Sx+1) f(x).. The optimization procodure consists of computing the gains for various values of y and analyzing their behavior. The optimal value
34

---

Published in Transactions on Machine Learning Research (02/2026)
10a
10a
10a
1000
(5x+1) ((Sx)
4 f(Se))
10a
5
10a
10"
1
10
lel
le2
10-
10a
110-2
Values of
10-1
0%
10%
20%
0%
10%
20%
0%
10%
20%
Amount of training samples
Amount of training samples
Amount of training samples
(a) Concrete
(b) Electrical grid
(c) QM8
Figure 9: Gains from adding new elements to the selected sets for the QM8, Concrete, and Electrical Grid datasets using the facility location method with the Gaussian similarity function. Gains are shown for various values of the kernel width, 7 1000, 10, 5, 1, 0.1 and 0.01.
y is chosen to maximize gains for larger training sets while maintaining the ability to capture interactions between data points.
Figure g illustrates the gains obtained from adding new elements to the selected sets for the Concrete, Electrical grid, and QM8 datasets. We initialize the greedy selection process with the same data point, independently of the value of y. Low values of y result diminishing gains as the training set size grows, while excessively high values, such as = 1000, cause the kernel to approximate a diagonal matrix, failing capture data point interactions. Basod on the experimental results, we set ? to for QM8, 10 for the Concrete dataset, and 10 for the Electrical grid dataset.
For the DA-FPS we follow the same heuristic approach used for experiments in Section S and set 3%, 1% and 3% and k = 100, 300 and 300 for the QM8, Concrete dataset and electricity datasct, respectively.
M.2 Cauchy Kernel
In this section define the Cauchy kernel and describe the optimization process implemented to fine-tune the kernel hyperparameter and the regularization hyperparameter for the kernel ridge regression weights optimization problem. Given data points æ,, 2y E Rd, we follow along Basak (2008) and define the Cauchy kernel as follows:
1 |o0 [o0:-a;l1a k(a;; m.)
(33)
To
The hyperparamotor % of the Canchy kornel and A, the regularization parameter of kernel ridge regression problem, are fine-tuned using the following process: first, we conduct a cross-validation grid search to identify the best hyperparameters for each training set size used in the experiments. The training subsets are obtained through random sampling. Then, we calculate the average of the best hyperparameter pairs across all training set sizes, which is subsequently used to build the final model. The tensor-grid scarch explores 6 points for each hyperparameter, ranging from 10-6 to 10-2 It is important to nole that in our experiments we do not use an optimal set of hyperparameters for each selection strategy and training set size. This choice ensures that we focus on analyzing the qualitative behavior of a fixed model, where the only variable influencing the prediction quality is the selection of the training set.
N Alternative to Theorem 7.1
Theorem 7.1 states that DA-FPS provides a 2k-optimal result to the optimization problem in 410 which considers dynamic-woights, that is, the weights are iteratively updated any time a new point selected. We can consider simplified version of the optimization problem in (10) by considering for each data point E Dx fixed weight w(x)) RR, which is determined a-priori and does not depend the selected set..
35

---

Published in Transactions on Machine Learning Research (02/2026)
Such simplified scenario has been already studied in literature. In particular, the authors of Dyer & Frieze (1955) show that it is possible to find solutions that are a-optimal, with o= min 1 + a), where mAX w(x)
a =
mineeDx w(a) That is, it is possible to find solutions that are at least 3-optimal. With the following
theorem we attempt to extend the result provided in Dyer & Frieze 1985 into our scenario with dynamic weights.
Theorem N.1. Given set Dx = (2,)/=1 C. R. subset Ox C Dx, optimal solution to the problem in with [0x| b E N+, b n, and Lx Dx, [Cxl b, subset selected with Algorithm 1 initiolized with Lx and 0, have
W Lx.Dx Dx I <o
Ox, Dx
(34)
where Ex, Dy and Wox. Dx are the estimated weighted fill distances of Lxx and Ox in Dx respectively, defined in 7 11. Morcover,
w (x0)
7 ==
max
(35)
WOx (2))
and
wk
L--1 (z,)
min a} with == max L.=l.... K
(36)
w (3:;)
,, bz} is the set of cordinality j obtained with Algorithm 7 We set Co = 0. The weights 22,_,(1) and wox (x,) in (5 and (60 are computed according to the same principle
For each = -,....,, b, Lu = {
in
Proof. Lot Ox == ( ,0} be an optimal solution the optimization problem in 10). Morcover, let Ca+1 = ( (b+ } be the set of cardinality b obtained with Algorithm [ First, note that by pigeonhole principle there exist He Ty L641, with 1 < i < j S b - 1 such that there exists a common closest element 0, Ox. Therefore, max ool 0ol12w0, (ax4, ||æ, o.ll2w0,, S Wox. Dx. Dx Next, we define the quantity
-h (Zz)) wh - (xi
B =
and consider two scenarios 3 < 2 and B B>3 2.
First scenario: 2 2. If we assume B < 2 we can prove the Theorem as follows
W Ls, Dx Swz, (x)) min ||x | -yyl2
mEC; 1
su (z,) || - 2zyl2
sw² (x3)) (1|æ, ooll2 + ||,, o
- (az))
wox (xz)) lar, ozll2
wox (az)
+ whi (xx) w/ (x,) wo, (x;))læz, 0cl12
wh. (xx)
w/ (z;)
ST(1 + 3) W)x.... Dxx SayWox.ne Dx
The first inequality follows from the fact that W C.... Dy S W Dx for all = 1,..., b. This is shown in Step I of the proof of Theorem 7.1 The second incquality follows from the fact that x; E 2,-1 since i < j. The last inequality follows from the assumption that < 2, thus, we have that B < minfa, 2} which implics that + a.
36

---

Published in Transactions on Machine Learning Research (02/2026)
Second scenario: 3 2. Consider 1 = < - b++1 Note that by how the weights are defined in (8] we
have that w 2 (at)) = w/o (a11 w ( = k and that for each j 2....,br bb + 1 we have 1 S w (m)) S k.
Thus, if = i < j S b + 1, it follows that
w J5- (2n)
w (x;z 1
B
w c. (2:)
which contradicts the assumption 8 > 2, so it holds i > 1. Next, consider 15 S b+ b+1, 1, and to be the closest point to æ, when x; is chosen, then we have that
W Dx Dx Sw))-,((3)
min xELi-1
| - æ2l12
swβ=_-, (a;;)] am x1y12
5 o E Dx such that ||æ; - øl12 S min[ - æil12 +
Ri-1l Pa (,1))|[[1> - =xyll2
Ex
= (ar))
min || - =,y122
(37)
wEC;
Sw (x;)
min | x;l12 x
Swee (2:;)|
xi 12
Sw² (x:) (1|23 - x 21l12 + ||,,- - x; 21)12).
The second incquality follows from the fact that σ1 E Lý-1, thus the distance between zj and the closest element in L--1 is smaller than ||ær - -2112- This is also relevant for the third inequality: The value of the weight _ (2y)) which is the amount of data points in the ball centered in æ, with radius r r²,_, (x;) == min { minuee, 1 ||æe - -2,ll2 + cx (x;;) is less or equal the amount of data points contained in the ball centered in æ, with the larger radius of min [,, æxll2 + Px The equality follows from the fact that we assume oi to be the closest point to 2; when æ, is chosen, that is, r (ax)) min(llær æylla + <x (ar))) The fourth inequality true because if we assume was false then my would have been selected before Z;-
ex
If we now assume that ||a; - my l222 S ||ar - sall2 by the inequalities 37 we would have
w², (m;))la, - æill2 S 2wh. (2; - x 1|2
which implies that
w (xzz) / (x:)
< 2,
which is contradiction since we are assuming / > 2. Thus, we have that 1|æ;-2;;112 bey-x;ll2 Therefore, from equation 37 we have that.
W Ln. Dx
22w (a:)) 22,12
2w (xx) (1|x3 ooll2 + +1 22ll2)
w 2// (x:;
wox (1::)|(z - oml12
w (xx)
wh (x;)
w W (zt) w/, (0,))læ3 -oll2
2 W/ (xz)
w/t (xx))
<2n + S W Dx
Dxx
SonWor.D.
The last inequality follows from the facts that B =a> +
V 4 3. Thus, since
2(1 + 3-1) < 3, we have that 2 2(1 + 1-11).
37

---

Published in Transactions on Machine Learning Research (02/2026)
provide an alternative result to Theorem 7.1 for the optimality of the solution provided by DA-FPS. Note that in Theorem N.1 we explicitly link the quality of approximation of DA-FPS with the ratio between the computed and optimal weights. In particular, one of the terms in the approximation factor _ (13))
With Theorem N.1
is y = max,y=1....b++ wox (a,) that is, the ratio between the weights related to the set selected with DA-FPS
and those of an optimal set. Note that the simplest upper bound for 7 is 7 S k. This is because, for how we defined them (8), the weights value is at least 1 and the most k, independently of the set considered to define them. Thus, using the simplest upper bound for 7, according to Theorem N..] DA-FPS achieves approximations that are 3k-optimal. This rate represents less favorable worst-case scenario compared to the 2k-optimal rate given by Theorem 7.1 Nonetheless, we think this result is relevant because it highlights how the relationship between the weights an optimal set and those associated with the selected set can be connected to the approximation error of DA-FPS. Moreover, by explicitly linking the quality of DA-FPS's approximation to and 0, we aim to highlight a possible path for improving the optimality constant by identifying a bound for either of these two quantities. Future work should focus on this direction.
38


Reviews:
[{"review_id": "OgQ49NlPTc", "reviewer": "Reviewer_rsAe", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces an approach for training data selection which is model-agnostic (i.e. makes no assumptions about the structure or parametrisation of the model) and is passive - particuarly suited for settings where labeled data is scarce / expensive to generate.\n\nThe presented idea is Density-Aware farthest point sampling which is an extension of Farthest point sampling, which adds a weighting term reflecting the relative concentration of labelled to unlabelled points.   Based on this, they bound the generalisation error that depends linearly on the WFD.   They propose a greedy algorithm, leveraging KDEs to approximate the distributions.  They show that the algorithm provides a 2k-approximation of the estimated WFD, where k is the nhd size of the KDE.\n\nThey demonstrate the efficacy of the approach on molecular property regression datasets, compared to a number of sensible baseline approaches.", "claims_and_evidence_yn": "Yes", "claims_explanation": "Generaliation bound - well supported by proof.\nDA-FPS algorithm - clear discussion how it is implemented, computational complexity & wall-clock run times.\nApproximation guarantee for the estimate Weighted FPS\nEmpirical evidence on a number of challenging molecular regression datasets, and strong comparisons with baseline model-agnostic point selection processes.", "audience_yn": "Yes", "audience_explanation": "The problem is of suitable generality and applicability across a wide range of domains.    The theory and generalisation bound is of indepdnent interest - with connections to coreset construction, and subset selection.", "requested_changes": "There are no major changes required.\n\n1. Making the the relationship between the theoretical bound and the implemented algorithm.  So thm 4.2 applies to the weighted fill distance, but DA-FPS uses a surrogate.    Clarify the gap between the theoretical bound and the implemented algorithm. Theorem 4.2 applies to the true weighted fill distance.   No need for a new theorem, but adding a short subsection or paragraph explicitly stating: (i) what is provably minimised, (ii) what remains conjectural about its relationship to the true weighted fill distance.\n\n2. Can you explain the effect of the hyperparameter u.  Approximation theorem is provd for u=0, but then u>0 in the experiments.  Maybe just explicitly noting this, and adding some remark on what the authors expect to happen theorywise more generally.\n\n3. Provide some heuristic guidance for k and u.", "broader_impact_concerns": "None", "additional_comments": "None", "extra_scores": {}, "extra_text": {}}, {"review_id": "lAEtc0gXAT", "reviewer": "Reviewer_pVQd", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors proposed density aware farthest point sampling, which extends farthest point sampling to be density aware so that higher density regions in the feature space are sampled more often, which helped reducing covariate shift in down stream training. \n\n- Key strength: density aware is principled and model agnostic, can also be extend to other distance based sampling schemes, e.g., coresets \n- Weaknesses: the method requires density estimate, which is itself nontrivial and can be hard in higher dimensions. Assumption B1 is interesting in the sense that requires the conditional expectation of Y given X to be very predictive and Y has very little noise. This should not be hidden in the appendix.", "claims_and_evidence_yn": "Yes", "claims_explanation": "Fig.2 showed numerical results in one type of regression tasks that the proposed method is never worse than existing methods and sometimes better, which support the claim on the effectiveness of the proposal. In appendix the authors showed theoretical results.", "audience_yn": "Yes", "audience_explanation": "Model agnostic method for data selection is useful where data labeling is costly.", "requested_changes": "I think the assumptions should be made clear, at least qualitatively in the main text. The authors should also make comments on that one needs to estimate the density and consequence when it is not estimated well.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "7dPHmvQqX1", "reviewer": "Reviewer_2mgk", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the problem of data selection for efficient training in the scenario where a large pool of unlabeled data is available and the learner wants to select a subset in order to obtain labels for it.\n\nThe proposed algorithm is based on designing a probability distribution to sample from to form the training set. The algorithm relies on a theorem that relates the excess error to a discrepancy measure referred to as weighted fill distance. Then, the algorithm constructs a distribution that (approximately) minimizes this weighted fill distance.\n\nThe authors provide experiments showing improvements compared to the baselines.", "claims_and_evidence_yn": "No", "claims_explanation": "**Notation and presentation**\nThe notation is hard to follow. Please add a table of notation (for example: D_X, L_X, p_D, p_L, p_X^D, p_X^L, ψ_{L_X}, W(·), and the empirical/k-NN counterparts) and expand the discussion of your algorithmic choices (choice of metric, role of k, etc.). The current presentation is quite dense and would benefit from a short “roadmap” paragraph at the start of each section.\n\n**Definition of the weighted fill distance**\nPlease clarify whether the weighted fill distance is a random variable or not. Let Q denote the training-source distribution induced by the selection policy and P the data-source distribution. If Q = P pointwise, then p_X^L = p_X^D and the weight ψ_{L_X}(x) = 1 − p_X^L(x)/p_X^D(x) vanishes everywhere, making the population weighted fill distance zero. Does this imply that sampling according to P is optimal? If not, please explain what fails in finite samples. In general, I think this confusion is another example of bad notation.\n\n**Theorem 4.2 (tightness)**\nWhen Q = P, the density term in the bound disappears and the remainder is driven by training-error and noise terms. In particular, it seems we are upper bounding a quantity by that quantity and some additional terms. It shows in trivial cases, the theorem is not tight. Please provide conditions under which this theorem is tight.\n\n**Sampling distribution vs. active selection**\nThe introduction frames the method as designing a sampling distribution, but Algorithm 1 greedily selects individual points. Please reconcile these perspectives and define p_X^L precisely in your notation: is it the empirical measure on L_X or a k-NN–smoothed estimate? \n\n**Numerical results**\nThe improvements over baselines appear marginal. To provide a baseline, please add a full-data (or 90%) ceiling: train the same model on all labels (or 90% train / 10% test) and report test performance. Please ensure validation handling is fair: use a fixed held-out validation set shared by all methods (not touched by the selector)", "audience_yn": "Yes", "audience_explanation": "the topic is interesting.", "requested_changes": "please see above.", "broader_impact_concerns": "not applicable.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)