Minimax Optimal Two-Stage Algorithm For Moment Estimation Under Covariate Shift
Authors: Zhen Zhang
Xin Liu
Shaoli Wang
Jiaye Teng
Venue: ICLR 2025 Poster (2025)
Keywords: covariate shift
minimax optimal
two-stage algorithm
double robustness
Primary area: learning theory
TL;DR: This paper investigates the minimax lower bound for moment estimation under covariate shift, and proposes a minimax optimal two-stage algorithm with a truncated version that ensures double robustness.

Abstract: Covariate shift occurs when the distribution of input features differs between the training and testing phases.  In covariate shift, estimating an unknown function's moment is a classical problem that remains under-explored, despite its common occurrence in real-world scenarios. In this paper, we investigate the minimax lower bound of the problem when the source and target distributions are known. To achieve the minimax optimal bound (up to a logarithmic factor), we propose a two-stage algorithm. Specifically, it first trains an optimal estimator for the function under the source distribution, and then uses a likelihood ratio reweighting procedure to calibrate the moment estimator. In practice, the source and target distributions are typically unknown, and estimating the likelihood ratio may be unstable. To solve this problem, we propose a truncated version of the estimator that ensures double robustness and provide the corresponding upper bound. Extensive numerical studies on synthetic examples confirm our theoretical findings and further illustrate the effectiveness of our proposed method.

Published as a conference paper at ICLR 2025
MINIMAX OPTIMAL TWO-STAGE ALGORITHM FOR MOMENT ESTIMATION UNDER COVARIATE SHIFT
Zhen Zhang, Xin Liu, Shaoli Wang, Jiaye Teng* School of Statistics and Data Science
Shanghai University of Finance and Economics Shanghai 200433, P.R. China
chenzhang@stia st.. sufe. edu. en, swangeshufe. edu.
ABSTRACT
Covariate shift occurs when the distribution of input features differs between the training and testing phases. In covariate shift, estimating an unknown function's 's moment is classical problem that remains under-explored, despite its common occurrence in real-world scenarios. In this paper, we investigate the minimax lower bound of the problem when the source and target distributions To achieve the minimax optimal bound (up to logarithmic factor), we propose a two-stage algorithm. Specifically, first trains an optimal estimator for the fune- tion under the source distribution, and then uses likelihood ratio reweighting procedure to calibrate the moment estimator. distributions are typically unknown, and estimating the likelihood ratio may be unstable. To solve this problem, we propose truncated version of the estimator that ensures double robustness and provide the corresponding upper bound. Ex- tensive numerical studies on synthetic examples confirm our theoretical findings and further illustrate the effectiveness of our proposed method.
known.
practice, the source and target
INTRODUCTION
Covariate shift occurs when the marginal distribution of the input covariates differs between the training and test data, but the conditional distribution of the response given the covariates remains consistent. It is prevalent and crucial in rerl-world applications, such as natural language processing (Wang et al.) (017). computer vision (Tzeng et al., (017)) reinforcement learning (Chang et al., 2021), finance (Timper) 2021) and medical care (Guan & Liu| 2021). addition to its practical significance, covariate shift has been extensively studied theoretically, particularly in the context of function estimation. For example, the linear function linear regression (Ryan & Culpl 2015), the classifier in nonparametric classification (Kpotufe & Martinet 2021), and the conditional mean function in nonparametric regression (Feng et al. 2024b).
However, in modern machine learning tasks, we are often more interested in the functionals of these estimated functions, such as the average treatment effect causal inference or accuracy in classifi- cation problems. To address these issues, practitioners commonly they estimate the functions, and then they use these estimators to calculate the desired functional (Oates et al. 2017 Lei & Candès 2021 1 Blanchet al. 2024). Yet, there are few theoretical works that analyze the efficiency of these two stages from unified perspective. Consequently. this paper aims explore the following question:
two-stage approach: first,
Under covariate shift, can we calibrate an optimal function estimator under source distribution to maintain the optimality for the functional under target distribution, and if so, how?
To this end, we consider the problem of estimating the moment of an unknown function under covariate shift. This is common scenario in many fields, such as counterfactual inference in causal inference) Specifically, we aim to estimate the q-th moment 17 == Ex -p- (X)) ] of f under target distribution 1x with p.d.f. p² (æ), based on values f()), ..... f(xn) observed random samples
"Correspond to {1 luu.iin, xin, tengji i ayee 9mai1. 1 whw.e..ee. edu..eeeeuucc edu.
For detailed discussion, please refer Appendix B.1

---

Published as a conference paper at ICLR 2025
Moment estimation
Randomly split s into S₁ and Sg
under covariate shift
#g Ex-F-
(x)
2
Σ
w(x) 6/2
(x))
72
Type
(R.yUes
Target
1.4
1.0
1.
12
0.8
0.6
-1
0.00
0.25
0.50
3.75
1.00
0.00
0.26
0.50
0.75
Stage I: train machine learning model on S1.
Stage II: use the likelihood ratio to calibrate based on S2-
0.5
02:0
1.30
Figure 1: The top figure in the left box shows the source and target distributions along with the corresponding likelihood ratio. The bottom figure in the left box illustrates the underlying function and the sampled data. The middle and right boxes show the first and second stages, respectively. More details can be found in Section
Ei...., In E Ω drawn from source distribution Pe with p.d.f. (x)) Here, the unknown function I belongs to the Sobolev space (S))( with Q C TR4, where s indicates the degree of smoothness and p specifies the integrability condition of these derivatives. To understand the complexity of this nonparametric functional estimation problem under covariate shift, we restrict our problem in certain class defined
{(f,p", ,²) E W*)(S)) S pd b, suP=en w(x) S B3, where [w) represents the likelihood ratio. The constants b, b and B are used to quantitatively compare the quality of different source distribution and the intensity of covariate shift. The problem
w(x) := p (a))
we consider extends the work of Blanchet et al. (024)) to scenarios involving covariate shift.
Our contributions in this paper can be summarized follows:
Contribution The impact of covariate shift on the minimax lower bound when pe and p are known. We establish the minimax lower bound for any given target p.d.f. p² over as follow?
inf sup HICH (V
E A - 17 2 B. maxt -Q(2 -
where ;= {fr: 12" X²" R} denotes the class that contains all estimators of the q-th moment 17. The value B 2 supzen w(x) measures the cost we need when doing estimations under covariate shift. A larger B indicates a greater extent of covariate shift, which leads to more challenging estimation task. When there no covariate shift, B 1. The value i indicates the influence of the sampling strategy the problem, larger b implies a more irregular source distribution. When pe taken as uniform distribution, b 1. The term n max((q(2 - --,,, 1 describes the difficulty caused by the combination of function class (s.(()) and the order of the moment
Contribution II: A two-stage algorithm that achieves the lower bound. We then propose a two- stage algorithm which attains the minimax lower bound up to logarithmic factor. Specifically, we split the data S {(x,, y/: f(x,)));= into two parts with equal size, S, and S.. We use S, to fit an optimal nonparametric estimator fs, ff and then use S₂ to do calibration. Our estimator is formulated as follows, and the framework is illustrated in Figure
Hg)()) Ex-e- 1f3, (X)]+
Σ (RE
w(xx)) (v) - f2,
Since p" (z) is known, we use sampling method estimate the first term. This estimator can be seen as importance sampling using fs, as the control variate. The fs, introduced in the first stage is used to reduce variance, while w wxx) in the second stage is used to debias residual. Furthermore, if fs. is chosen to be optimal (Assumption I then matches the minimax lower bound up
We the notations and hide log factors and define Vv- ((fpp') ) (f. V}.
2

---

Published as a conference paper at ICLR 2025
logarithmic factor, follows:
Es [ r3] s B. b. max -(---))111---
Contribution III: Stabilized algorithm with double robustness when p" and p" are unknown. In practice, the source and target distributions are typically unknown. Therefore, we need to replace w(x) in equation with the estimator vx(x). To estimate w(x), is necessary to have m (> n " unlabelled data points drawn from P denoted as S' {o'..... 22 Although there is extensive literature (Yu & Szepesvári 2012; Bickel et al. 2007 Kpotufe (0177) on methods for estimating wr(r), (x) becomes unstable when we lack prior information about Ip and IP?, To address this, we introduce the truncated version of equation as follows:
m
i
(x))
Σ (.L.))E.
(w(())))) (wf - f3, (a.)),
where (-) = min f- T). To understand how this affects the convergence rate, we assume that
g(2) = PP (1 x (x)
(m) > >T}) T and denote r(n) n max( -33-))1----333 By selecting T' to balance the trade-off between bias and variance, the convergence rate of the truncated version of the estimator is:
Es ( r3] - - (6-r(())= + m
Note that our estimator involves two models: one for estimating ʃ and the other for estimating w(x)). We demonstrate that our estimator possesses the double robust property, meaning it be consistent least one of the two estimates consistent.
The paper is organized as follows. Section 2 provides a review of the relevant literature. Section 3 introduces the notation and problem setup. In Section 4 we establish the minimax rate of con- vergence for the moment estimation problem under covariate shift and demonstrate its attainability where pd and p" are known. In Section55 we introduce stabilized algorithm with double robustness for cases where p" and p" are unknown. In Section[6 we provide the simulation results to illustrate our theoretical findings. Finally, we conclude in Section 7 and leave most of proofs to the appendix.
2 RELATED WORK
Covariate shift. Extensive work has been done on covariate shift (Sugiyama & Kawanabe 20122). The primary tool to address covariate shift is the reweighting method, as discussed by (Shimodaira (200). This method utilizes the likelihood ratio to reweight the loss function or estimator, thereby correcting for bias. Numerous studies have examined the statistical efficiency of this method in var- ious contexts, such nonparametric classification (Kpotufe & Martinet 2021 and nonparametric regression (Ma et al. 2023; Feng et al., 2024a). Among them, Ma et al. (2023) is closely related to ours which studies the covariate shift problem in the context of nonparametrie regression over reproducing kernel Hilbert space and introduces the truncation trick on the reweighted loss for the case of unbounded likelihood ratios. However, while their focus is estimating the unknown func- tion itself, our work is concerned with the moments of the unknown function, thereby advancing one step beyond previous studies. The likelihood ratio is the key component of this method, but is often unknown in practice. Many studies focus on estimating the likelihood ratio in covariate shift using techniques such as histogram based methods (Kpotufe) 2017). kernel mean matching YYu & Szepesvári 2012 Li et al., 2020), and discriminative learning Bickel et al. 2007 2009).
There are also other methods that do not require estimating the likelihood ratio. For example, Pransfrratioonbbasedd methods (Flamary et al.) 2016) Wang et al.] 2024) involve learning a transfor- mation from the source feature domain to the target feature domain and then using the transformed data to train the model. Domain-ing Nomain-invariant methods (Robey et al.) 2021 Blanchard et al., 2021) aim to learn transformations that map data between domains and subsequently enforce invariance to these transformations.
The condition m (* n) is not necessary in this paper but it is a common scenario in practice, as un data is generally more easily available than labeled data.
3

---

Published as a conference paper at ICLR 2025
Two-stage algorithm is a class of method that divides the problem-solving process into two distinct phases, each with a specific purpose. These methods have numerous applications across various fields. For example, in the deep learning community, the training regime typically involves repre- sentation learning followed by downstream task fine-tuning (Devlin et al. 2018: Du et al. 2020 He al. 2022). In computational statistics, regression-adjusted control variates introduced the first stage to reduce the variance for the estimation of the quantity of interest (Oates et al. 2017; Holzmüller & Bach 2023). In uncertainty quantification, conformal inference uses calibration
set in the second stage to construct confidence intervals for any point estimator from the first stage
(Romano al. 2019 Tibshirani et al. 2019 Teng al. 2021 Lei & Candès 202T).
Recently, Blanchet (2024) found that using optimal nonparametric machine learning algorithms to construct control variates is the best way to enhance Monte Carlo methods, but remains under- explored how to adapt such a two-stage algorithm to ensure it remains optimal under covariate shift.
3 NOTATION AND SETUP
Notation. Let || denote the standard Euclidian norm, and let = [0, 1] denote the unit cube in Rdd for any fixed d E N. Define No := NU {0} as the set of all non-negative integers. For any given 8 E No and S p S oc, the Sobolev space W (S2) is defined as follows:
(S) = (f E CP()): D f E (22), Va E Ny satisfying |a| S s}.
Problem Setup. Consider the problem of estimating a function's 's g-th moment under covariate shift. For any fixed q E N and f E WS)((S),, we want to estimate the q-th moment 1 := Ex-P-1 If (X)) under target distribution F where p" is the p.d.f. of IP* However, we only access
observations
S == =((x,, W) C Ω x R", where {0,) are i.i.d. samples from source distribution IP with p.d.f. pd and y/- = f(x)). Our goal is to find estimator 1/2 Ω2" x R" + R to tackle with this nonparametric functional estimation problem under covariate shift.
Notably, under covariate shift, transferring knowledge from the source to the target not straightfor- ward without additional assumptions on IPo and P For example, consider the extreme case where 5e is uniform distribution on [0. 1 and IP is uniform distribution on 1]d. In this scenario, anything learned on [0, 1] is independent of the information on [ 1j Therefore, the difficulty of this problem hinges on the notion of discrepancy between the source and target distributions. By imposing various conditions on this discrepancy, we can define different families of source-target pairs (Definition T). denoted as (Po IP*). In this paper, we focus pairs defined on the likelihood ratio, common choice under covariate shift (Ma et al. 2023 Feng et al. 2024b), as outlined below.
Definition (Uniformly B-bounded). For any source-targel pairs (IP P*) with p.d.f. (p vv)) and constant B 2 1, we say that the pair is uniformly B-bounded if:
px(x)
sup w(x) =
(x)) < B.
is worth noting that B recovers the case without covariate shift, i.e., p P At the same time, the source distribution also affects the difficulty of the problem. A well-shaped source distribution provides comprehensive information about the function f. To exclude extreme cases, we assume that p" is bounded below by b and above by b, an assumption commonly used in transfer learning (Audibert Tsybakov 2007 Cai Wei 202T).
Putting the above together, we consider the following class in the rest of this paper:
V(b, B,s,)) (F.D'
p²) (f''".p"):
WoP(S)), p s b, sup w(x) < B).
z
and investigate how the parameters within this family influence the difficulty of the estimation prob- lem. We use the shorthand V when the context is clear.
4 MINIMAX LOWER BOUND AND ITS ATTAINABILITY
In this section, we establish the minimax rate of convergence for the moment estimation problem under covariate shift in Section 4.1 assuming that pd and p" are known. We then propose two-
4

---

Published as a conference paper at ICLR 2025
Additionally, since a large covariate shift intensity B leads to high variance, we introduce a biased estimator in Section achieve variance-bise trade-off. This allows to obtain bound that is independent of B.
stage algorithm that achieves this bound up logarithmic factor in Section 4.2
4.1 MINIMAX LOWER BOUND
In this subsection, we study the minimax lower bound for the problem above via the method of two fuzzy hypotheses (Tsybakov, 2009). We have the following minimax lower bound on the class W44 that contains all estimators H Q x IR" + IR of the q-th moment f7.
Theorem 1 (Minimax Lower Bound on Estimating the Moment under Covariate Shift). Let Hi denote the class of all the estimators using S { 3/s = f(x,))};= to estimate the q-th moment of I under Ip. For any given larget p.d.f. p² {p" ('''pp") VJ. when p 2, 9 S p 2g and (f.1P) EV = ((J.P)))) (T,P, .P") VV,, holds that
inf sup HREM! (S.P)EV,
Es [1((S)) 171 2 B- maxt - 1
(2)
Theorem indicates that the complexity of this problem determined by three factors: covariate shift, sampling strategy, and the interplay between the function class and the moment order. We will provide a simulation study illustrate these three factors in Section
Covariate Shift: The value B 2 supzen w(x) represents the additional cost associated with mak- ing accurate estimations in the presence of covariate shift. A larger B signifies a more pronounced covariate shift, which inherently complicates the estimation process due to the increased divergence between the source and target distributions. When there no covariate shift, B 1, meaning the distributions are aligned, and estimation is straightforward.
Sampling Strategy:
The parameter b quantifies the impact of the sampling strategy on the problem. A larger b suggests a more irregular source distribution, which introduces complexities in the esti- mation process. For example, when pe a uniform distribution, 1, indicating that the source distribution is regular and well-behaved.
Function Class and Moment Order: plexity arising from the interplay between the function class (*))(S)) and the order of the moment It delineates the function class into two distinet regimes based error decomposition: (f fo) can be broken down into the semi-parametric influence part f2 f)² and the propagated es- timation error (ʃ - --22 (Blanchet et al. 2024). When 8 d(2g-p)
The term n max 11-1,-3 encapsulates the com-
2)2--2j the smoothness parameter is sufficiently large to make the parameareetriic influence part the dominant term. Conversely, d(2g-p) 2]2 the semi-parametric influence longer dominates, and the final convergence rate shifts from 1 11- to n - -11-))-11
4.2 ATTAINABILITY
This subsection focuses constructing minimax optimal estimators for the q-th moment under covariate shift. It addresses the question posed in Section under covariate shift, we can obtain an optimal function estimator fs, that satisfies Assumption then we can calibrate it as follows to derive the moment estimator frg which preserves the optimality in functional estimation:
(S) = Ex 188 [X)
+ n
2
Σ (mL.)))S,
w<x;)) (vl f3 (2:)).
(3)
where S₁ = {xx 1 and S = {Z;; v1 u,)) are two subsets of the sample S.
Assumption (Optimal Function Estimator as an Oracle). Given any function E WPsP( and N. let {x, { be data points sampled independently and identically from the source distri- bution Io, whose p.d.f. f pd is bounded bellow by b and above by b on Q. Assume that for 1- 24' there exists oracle K2 Q R (VS.P(()) that estimates f based the n points )
5

---

Published as a conference paper at ICLR 2025
Algorithm Minimax Optimal Algorithm for Known Source and Target Distributions
1: Input: labeled data: S { 3/ = fx++))
2: Randomly split S into two parts S {(x,, W)) i=l and 82 {(x,,, v
3: Train machine learning model S₁ to obtain fs, (z)).
4: Choose a sampling method based on p² (a:) to compute Ex- 153 (X)]
5: Use S2 to estimate the I based on equation 3
6: Output: q-th moment under target: 17.
along with the n observed function values {f(x)))= and satisfies the following bound for any r satisfying 1 (max{
d=e2
pd 0}, max { T($ $1
[n,({ (faaa:ffaaaaa (f(x)))i=)> file-)))) Sb.n 2+1 +)+
B
(4)
Assumption illustrates that when the function is smooth enough, i.e., 3 1/2 24 it becomes possible to construct optimal function estimator, provided the source distribution is well-shaped. This assumption is also used in Blanchet et al. (2024), and many works (Wendland [2004] Krieg & 2024) focus on constructing such estimators, notably through the
Sonnleitner, 2024 Blanchet
moving least squares method, which achieves the convergence rate in equation 4 A construction of the desired oracle is deferred Appendix [B.3]
Theorem 2 (Upper Bound on Moment Estimation with Smoothness). Assume that p 2 2, p S 2q and
Let (f.p"pp") E V(b, b, s,s) and we have sample S {( V:
f(x:)))== If fs. satisfies the Assumption then the estimator f1, constructed in equation above satisfies
Es [Tg(s)) - 19 B. b. max(- 1- -1),
(5)
Construction Procedure. We construct our moment estimator in two-stage manner. First, divide the sample into two parts S {(x, y)) and S {(z,, ((.. Using a machine learning algorithm, we compute a nonparametric estimation fs. of f based on S₁. In the second stage, we use S2 for calibration based on the following equation:
Ex-p- Ex-r([/((X)) = Ex-F= p- L/3, (X) + Ex-P- (X( - 13, (X)]
Ex [/3 X Ex-r (X) (X)( f3. (X)))
Ex-r- lf3. (X) i.e., the second term in equa- tion 6 using samples from S2. This is given by 2 3 (...))))s w(x)) (v/" f3 (a.)). Since assume that p" is known, the first term in equation can be easily estimated. Finally, by combining these steps, we obtain our moment estimator, as summarized Algorithm
Specifically, we estimate residual Ex f X))
2
(1g(8):= = Ex-r 1f3 (X)
Σ (#..)))S2
w(x:) (2) (x:)).
T
Note that the fs, in equation can be constructed using various method in practice Künzel et al. 2019 Wager & Athey] 2018). Theorem shows that if fs, is optimal, i.e., it satisfies Assumption above, then the estimator HT achieves the minimax lower bound up to logarithmic factor.
4.3
B-INDEPENDENT BOUND
The bound derived in Theorem 2 depends on the intensity of the covariate shift. In some scenarios, the term B 2 supzen w(x), which measures this shift, can become exceedingly large even when the actual difference between y" and pd is relatively minor. This situation leads the issue where large

---

Published as a conference paper at ICLR 2025
values of the weighting function w(x) in the estimator H3. introduce significant variance, despite the estimator maintaining its unbiased nature. High variance is problematic because it overshadows the benefits of unbiasedness, resulting in less reliable estimations. Consequently, it becomes crucial to balance bias and variance to achieve more stable estimators. To address this challenge, we propose using a truncated version of the estimator f1
The truncated estimator is defined as follows:
2
H7(S) Ex (X)
Σ vr(w(x,))
(of f3. (x))),
where (.(()= == min T is the truncation function, which limits the influence of large likelihood ratios by truncating values of w(x)) that exceed predefined threshold T 0.
Theorem 3 (B (B-independent Bound). Denote 2 = {2: w(xx) T} as the area where the like- lihood ratio exceeds the threshold T, and let (P( (T)) denote the probability of this event. Under the conditions in Theorem 2 the upper bound for the variance and bias of the truncated
estimator 7 are given as follows:
Bias [((())) - 17 S P((7))
Variance = E H - B(H+g) | s $B..12 r(n)) ((n))+B) +B P((7))
If we further assume that (T) S T and pick T -(((()) |ो.
then obtain the following
B B-independent bound:
Es (H)(S)) r711 S b..()))
where r(n) n max(- -11-))1--- is the same order in Theorem 2
Compared to the unbiased estimator frg in Theorem 2 introducing the threshold T adds bias term when T < B. The threshold T controls the trade-off between bias and variance: increasing reduces bias, while decreasing 7 reduces variance. By carefully selecting the threshold T, we can mitigate the variance introduced by extreme likelihood ratios, thus achieving an optimal B- independent bound. However, climinating the influence of B comes at the cost of changing r(n) large, as it helps mitigate high variance,
to ="T This result is especially beneficial when improving the stability of the algorithm. Even when B is not large, the estimator vi(x) may still be large, potentially introducing additional variance. To address this, we apply the truncated estimator f14, which we will discuss in Section
Remark. The additional assumption (T) S T-a reduces the size of the class V, potentially making the minimax lower bound in 2 less tight. Consequently, the upper bound in 8 may be better than the minimax lower bound when is large. A more detailed discussion of this assumption is provided in Appendix B.2
STABILIZED ALGORITHM FOR UNKNOWN LIKELIHOOD RATIOS
In Section 4 we discuss the importance of the likelihood ratio w(x) in debiasing estimators. How- ever, the related discussion limited to the ideal scenario where both the source p.d.f. (x)) and the target p.d.f. p" (x) are known, allowing direct computation of wx:). In practice, these distributions are usually unknown, making the calculation of the likelihood ratio challenging.
still gather series of unlabeled data from the target domain when both p¹ (xx) and p" (ax) are unknown. Specifically, we have access to n labeled samples from the source distri- bution, denoted S = {(ar,, y4 f(x))) ) Additionally, we have m (>> n) unlabeled samples from the target distribution, represented by S" = {
Fortunately,
There are various methods available for estimating the likelihood ratio w(x) Yu & Szepesvárij 2012 Bickel et al. 2007 Kpotufe 2017). For example, we employ a classification approach
'The term depends on the parameters defining the class V. which brings insight about the relation between the choice of 7' and the smoothness of function, intensity of covariate shift. Unfortunately, they are unknown in practice, we can only determine the appropriate truncation point through grid search method.

---

Published as a conference paper at ICLR 2025
to obtain the estimator ti), with further details provided in Appendix However, it inevitable that the estimation procedure introduces large values (()), even when the true value w(x) is relatively small. To address this issue, adopt the truncated version of the moment estimator from Section 4.3 Specifically, we replace the unknown weight function w(x:) in the estimator 7 with vi)):). Furthermore, since the target distribution p" (a:) unknown, cannot directly compute the first term E x-- L (x)). To address this, we use unlabeled data to approximate The modified estimator is given by equation 9 and the entire procedure is summarized in Algorithm
HA(SUS))
2
Σ
TT(((x;)) (u? 83 (xxe).
m
5.1 CONVERGENCE RATE AND DOUBLE ROBUSTNESS
In this subsection, we first examine the convergence rate of the estimator 9 under the same assump- tions in Theorem 3 Additionally, we demonstrate the double robustness the estimator 9
The difference between estimators 7 and lies in the need to estimate additional quantities when pd (x) and p" (æ) are unknown. The following theorem shows how these unknown quantities affect the convergence rate of the estimator 9
Theorem (Convergence Rate of Plug-in Truncated Estimator). Under the same assumptions in Theorem the convergence rate of the plug-in truncated estimator HG is:
E [ - r9 H A
+ -
(10)
Theorem 4 indicates that the only additional cost to the convergence rate for the unknown source and target distributions is m- This term represent the Monte Carlo simulation error for estimating Ex~e- 1/, (X)] using unlabeled data points S The additional error from estimating w(x) is
bounded above by the error of the estimator H.y. due to the truncation applied to the estimator (xx).
Proof Sketch. The relationship between the convergence rate of FG. and HG.. is established through the following error decomposition:
E 9
r3]
Esus
2
Σ
(1((())) (uf f3, (a::)
(TT(1i()))) - (r(((,))) (r)((:
+
(#.
additional emror for estimating an (xe)
X
Esus
- 1f3, (x)
1x
Esus
[| A 17
m
ertor of
w(())
Monte Curlo simulaation
The first term represents the additional error due to estimating the likelihood ratio w(x). Due to truncation, this term is bounded above by T and the estimation error of f (x). which is further bounded by the third term. The second term accounts for the Monte Carlo simulation error in estimating Ex-p- 1/3, (X) using m unlabeled data S' form target domain, with a convergence rate O(m +). The third term corresponds the estimation error of fry. as discussed in Theorem
In our approach, two models play crucial role: one for estimating the likelihood ratio w(x) and another for estimating the function f() itself. So far, assumptions have been made about fs, (x) but not about ú( (x). If assumptions are instead made only about 20 (x:). the conclusion as follows.
Corollary (Double Robustness of Plug-in Truncated Estimator). Pf(7) - as n + co, then the estimator Hi exhibits double robustness. Specifically, this means that as long as either w(x) or fs, (xx consistent, the moment estimator H1 is also consistent.
Corollary provides guidance on selecting (xxx) and fs, (x) to maintain consistency when achiev- ing the optimal estimator of f that satisfies Assumption T is not feasible in practice. The assumption
8

---

Published as a conference paper at ICLR 2025
Turing the intensifly covarite shift
Tuning the upper bound of source pdf
Sample reach specified error
0.75
0.20
400
0.50
0:15
265
0.110
200
0.25
0.05
100
0.00
0.00
8- 0.2
x --4
P--
0-8.88
am0
252
2-7
3-10
0 -3.0
8-1
B 8.9.0
B 12.00 23.3.03
b-1.4
5-1.33
5-1.33
6 1.64
-2.5
-2.0
-1.0
Mean
(E
(a) Effect of covariate shift.
(b) Effect of sampling strategy.
(c) Effect of function class.
Figure 2: Impact of covariate shift, sampling strategy, and function class on the error of the estimator,
measured by the L1 norm between the true and estimated values. (a) Boxplot of the error across different levels of covariate shift intensity B, which is adjusted by fixing F as truncated normal distribution with mean of 0.2 and altering [P* be the same truncated normal with a shifted mean to vary B while keeping b constant. As B increases, the error increases and the stability of the algorithm decreases. (b) Boxplot of the error across different levels of the upper bound of the Po, with fixed F as uniform distribution and modifying P with a hyperparameter a that vary b while keeping B constant. As increases, the error increases and the stability of the algorithm decreases. (c) Required sample size to achieve specified error for different smoothness levels, controlled by hyperparameter k. A larger indicates less smoothness, resulting in a slower convergence rate.
P(27) - 0 - indicates that the probability of the truncated region 27- diminishes the sample size increases, thus ensuring that the influence of extreme values becomes negligible in large samples. It can be achieved if we follow the rule in Theorem 3
NUMERICAL EXPERIMENTS
In this section, we generate synthetic data to illustrate three key factors that influence the problem
discussed in Section 4.1, as well as the effect of truncation covered in Section 4.3 We set g 2 and the machine learning algorithm employed to learn fs, is the random forest. Each experiment is repeated 100 times. To highlight the advantages of our proposed two-stage estimator under covariate shift, compare it against the Monte Carlo estimator and the one-stage estimator on both synthetic data (Figure 3) and real-world data (Figure 5) with detailed explanations provided in Appendix C
Covariate Shift. We set P truncated normal distribution on [0. 1] with mean of 0.2 and a standard deviation of 0.3, denoted by tnorm( ([0, 11. 0.2. To vary the intensity of covariate shift, consider the target distributions tnorm (0, 1]. ju, 0.3), adjusting the mean parameter μa. We set (x) = + x² + sin( 16x) and select 0.2, 0.4, 0.6, 0.8, with the corresponding B values being 1.00, 3.98, 12.08, 23.03, respectively.
Sampling Strategy. We set Pa as uniform distribution over [0, 1]. To maintain the covariate shift, we consider source distributions with the following probability density functions:
24
24 Jr 5"
p);a) ax.3 + (-
a))=²
(1
+ a
2
which ensures that B = 5. We set f(z) = + x² + 1 sin sin(16z) and select a = 00,3,7, 10, with the corresponding values 1.40, 1.43, 1.53, 1.64, respectively.
Function Class. We set P tnorm ([0, 0.6, 0.6) and Po uniform distribution over (0, 1]. To examine the impact of the function class, we select functions f from the following class:
f(r;k) = = x2 sin(k: x).
where increasing leads to a less smooth function. our analysis, we use A = 4, 16, 32, 64. To determine the required sample size to achieve specified error levels of 0.1, 0.05, 0.01, 0.001, start with a sample size of 10 and increment by 10 until the error falls below 0.001. For each specified error level, we select the sample size for which the error is closest to the desired value.
The numerical experiments reveal that the error rates increase with the intensity of covariate shift, as illustrated in Figure 2 a). When varying the hyperparameter B, which controls the mean shift in the

---

Published as a conference paper at ICLR 2025
Inentisy of covariate shif
Inentayy of covariste shift
Inentisy covarite shift B=12.08
0.05
0.03
0.04
0:10
g 0.033
Entr
0.00
0.05
0.01
0.01
0.00
Two--saga
One-slaga
Two-stage
Two-slage
Method
Method
Malthod
Figure 3: Comparison of the Monte Carlo estimator, one-stage estimator and two-stage estimator on synthetic data, with performance measured by the L1 norm between true and estimated values. Each subfigure presents boxplots of the errors for different methods across varying levels of covariate shift B. The Monte Carlo estimator performs better than the two-stage methods when there is no covariate shift (B = 1). However, as B increases, the two-stage estimator demonstrates greater accuracy and improved stability, highlighting its necessity under significant covariate shift.
Inantisy covariato shift B-3.38
Inentisy of covar ats shift B=12.08
Inentisy of covartate shitt B-23.03
0.15
0.75
2.100
303
0.50
02
0.05
0.1
0.25
0.00
0.00
Method
Method
Method
Figure 4: Effect of truncation. Each subfigure presents boxplots of errors for both untruncated and truncated estimators across different levels of covariate shift B. Truncation improves stability while preserving accuracy, with its impact becoming more pronounced as B increases.
source distribution, we observe that larger shifts lead to higher error rates. This pattern is consistent across different settings of the function class and sampling strategies, as depicted in Figures 2b) and (c). These findings underscore the importance of both the degree of covariate shift and the smoothness of the function in determining model performance.
Effect of truncation. To illustrate how truncation enhances the stability of the two-stage method, the truncated estimator from equation using T = 1/2 B. The source distribution IPd defined as a truncated normal distribution on [0, 1] with mean 0.2 and standard deviation 0.3, denoted by tnorm [0, 1]. 0.2, 0.3). To vary the intensity of covariate shift, we consider the target distributions no [0, 11, μ., 0.3), adjusting the mean param- eter μs. We set f(x = 1 x² + 1 sin(162) and select μ 0.4, 0.6, 0.8, resulting in corresponding B values of 3.98, 12.08, and 23.03, respectively.
we compare the untruncated estimator from equation
The results are presented in Figure 4 showing that truncation enhances stability while preserving accuracy, with its effect becoming more significant as B increases.
7 CONCLUSION
In this paper, we explore how to calibrate an optimal function estimator to maintain its optimality for moment estimation under covariate shift. Firstly, we establish the minimax lower bound for this problem and develop an optimal two-stage algorithm when both the source and target distributions are known. Our findings indicate that the convergence rate is influenced by three factors: the inten- sity of covariate shift, the sampling strategy, and the properties of the function class. Furthermore, we propose a truncated version of the estimator that ensures double robustness and provide the cor- responding upper bound when the source and target distributions are unknown. This is important in practice because estimating the likelihood ratio can often be unstable.
Nonetheless, several potential extensions warrant exploration. This paper utilizes the uniformly B- bounded class; however, alternative choices, such as the moment-boundar class, are also feasible. Additionally, our assumptions, including the constraints on the parameters p and and the bounded source p.d.f., may be extremely restrictive for some application scenarios. We leave the relaxation of these assumptions for future work. Furthermore, our analysis focuses on moment functionals. A potential direction for future research is to explore more complex functionals to investigate whether the optimality still holds given the optimal function estimator under covariate shift.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This work is supported by Shanghai Science and Technology Development Funds 24YF2711700 and Fundamental Research Funds for the Central Universities 20241 10586. Xin Liu is partially sup- ported by the National Natural Science Foundation of China 12201383, Shanghai Pujiang Program 21 PJCC05 and Innovative Research Team of Shanghai University of Finance and Economics. Shaoli Wang is partially supported by the National Natural Science Foundation of China NSFC72271148.
REFERENCES
Jean-Yve Audibert and Alexandre B Tsybakov. Fast learning rates for plug-in classifiers. The Annals of Statistics, 2007.
Steffen Bickel, Michael Brückner, and Tobias Scheffer. Diseriminative learning for differing training and distributions. In Proceedings of the 24th international conference on Machine learning, pp. 81-88, 2007.
Steffen Bickel, Michael Brückner, and Tobias Scheffer. Discriminative learning under covariate shift. Journal of Machine Learning Research, 10(9), 2009.
Gilles Blanchard, Aniket Anand Deshmukh, Urun Dogan, Gyemin Lee, and Clayton Scott. Domain generalization by marginal transfer learning. Journal of machine learning research, 22(2):1-55,, 2021.
Jose Blanchet, Haoxuan Chen, Yiping Lu, and Lexing Ying. When can regression-adjusted con- trol variate help? rare events, sobolev embedding and minimax optimality. Advances in Neural Information Processing Systems, 36, 2024.
T Tony Cai and Hongji Wei. Transfer learning for nonparametric classification: Minimax rate and adaptive classifier. The Annals of Statistics, 2021.
Jonathan Chang, Masatoshi Uchara, Dhruv Sreenivas. Rahul Kidambi, and Wen Sun. Mitigating covariate shift in imitation learning via offline data with partial coverage. Advances in Neural Information Processing Systems, 34:965-979. 2021.
Jacob Devlin, Ming-Was Wei Chang. Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04800, 2018.
Peng Ding. A first course in causal inference. CRC Press, 2024.
Simon S Du, Wei Hu, Sham M Kakade, Jason D Lee, and Qi Lei. Few-shot learning via learning the representation, provably. arXiv preprint arXiv:2002.00 09434,, 2020.
Xingdong Feng. Xin He, Yuling Jiao, Lican Kang, and Caixing Wang. Deep nonparametric quantile regression under covariate shift. Journal of Machine Learning Research, 25(385):1-500 2024a.
Xingdong Feng, Xin He, Caixing Wang, Chao Wang, and Jingnan Zhang. Towards unified anal- ysis of kernel-based methods under covariate shift. Advances in Neural Information Processing Systems, 36, 2024b.
Rémi Flamary, Nicholas Courty, Davis Tuia, and Alain Rakotomamonjy. Optimal transport for domain adaptation. IEEE Trans. Pattern Anal. Mach. Intell, 1(1-40):2, 2016.
Hao Guan and Mingxia Liu. Domain adaptation for medical image analysis: survey. IEEE Trans- actions on Biomedical Engineering, 69(3):1 2021.
Kaiming He, Xinlei Chen, Saining Xie, Yanghao Li, Piotr Dollár, and Ross Girshick. Masked au- toencoders are scalable vision learners. In Proceedings of the IEFE/CVF conference on computer vision and pattern recognition, pp. 16000-16009, 2022.
David Holzmüller and Francis Bach. Convergence rates for non-log-concate sampling and log- partition estimation. arXiv preprint arXiv:2303.032377 2023.

---

Published as a conference paper at ICLR 2025
Samory Kpotufe. Lipschitz density-ratios, structured data, and data-driven tuning. In Artificial Intelligence and Statistics, pp. 1320-1328. PMLR, 2017.
Samory Kpotufe and Guillaume Martinet. Marginal singularity and the benefits of labels in covariate-shift. The Annals of Statistics, 49(6):3299-3323, 2021.
David Krieg and Mathias Sonnleimer. Random points are optimal for the approximation of sobolev functions, IMA Journal of Numerical Analysis, 44(3): ((1)):344-13711 2024.
Sören R Künzel, Jasjeet S Sekhon, Peter J Bickel, and Bin Yu. Metalcarners for estimating heteroge- neous treatment effects using machine learning. Proceedings of the national academy of sciences, 116(10)4156-4155 2019.
Lihua Lei and Emmanuel J Candès. Conformal inference of counterfactuals and individual treatment the Royal Statistical Society Series B: Statistical Methodology, 83(5):911-99)
effects. Journal the 2021.
Fengpei Li, Henry Lam, and Siddharth Prusty. Robust importance weighting for covariate shift. In International conference on artificial intelligence and statistics, pp. 352-362. PMLR, 2020.
Cong Ma, Reese Pathak, and Martin Wainwright, Optimally tackling covariate shift in rkhs-based nonparametric regression. The Annals of Statistics, 51(2):738-761, 2023.
Chris J Oates, Mark Girolami. and Nicolas Chopin. Control functionals for monte carlo integration. Journal of the Royal Statistical Society Series B: Statistical Methodology, (9(3),695-718, 2017.
Aleksandr Reznikov and Edward B Saff. The covering radius of randomly distributed points on manifold. International Mathematics Research Notices, 2016(19):60655-6099 2016.
Alexander Robey, George Pappas, and Hamed Hassani. Model-based domain generalization. Ad-
vances in Neural Information Processing Systems, 11:20210-202299 2021.
Yaniv Romano, Evan Patterson, and Emmanuel Candes. Conformalized quantile regression. Ad- vances neural information processing systems, 32, 2019.
Kenneth Joseph Ryan and Mark Vere Culp. On semi-supervised linear regression in covariate shift problems. The Journal of Machine Learning Research, 16(1):3183-3217, 2015.
Hidetoshi Shimodaira. Improving predictive inference under covariate shift by weighting the log- likelihood function. Journal of statistical planning and inference, 90(2):227-244, 2000.
Masashi Sugiyama and Motoaki Kawanabe. Machine learning in non-stationary envirouments: Introduction to covariate shift adaptation. MIT press, 2012.
Jiaye Teng, Zeren Tan, and Yang Yuan. T-sci: two-stage conformal inference algorithm with guaranteed coverage for cox-mlp. In International conference machine learning, pp. 10203- 10213. PMLR, 2021.
Ryan Tibshirani, Rina Foygel Barber, Emmanuel Candes, and Aaditya Ramdas. Conformal pre- diction under covariate shift. Advances in neural information processing systems, 32, 2019.
Robert Timper. Improvement the Credit Risk Stress Testing Methodology for Corporate Bonds Using Machine Learning with Covariate Shift Adaptation. PhD thesis, HEC Montréal, 2021.
Alexandre B. Tsybakov. Introduction to Nonparametric Estimation. Springer, 2009.
Eric Tzeng, Judy Hoffman, Kate Saenko, and Trevor Darrell. Adversarial discriminative domain adaptation. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 7167-7176, 2017.
Stefan Wager and Susan Athey. Estimation and inference of heterogencous treatment effects using random forests. Journal of the American Statistical Association, 113662));1228-12222 2018.
Martin Wainwright. digg--iimesionnl statistics: A non-asymptotic viewpoint, volume 48, Cam- bridge university press, 2019.
12

---

Published as a conference paper at ICLR 2025
Hao Wang, Jiajun Fan, Zhichao Chen, Haoxuan Li, Weiming Liu, Tianqiao Liu, Quanyu Dai, Yichao Wang, Zhenhua Dong, and Ruiming Tang. Optimal transport for treatment effect estimation. Advances in Neural Information Processing Systems, 36, 2024.
Rui Wang, Masao Utiyama, Lemao Liu, Kehai Chen, and Eiichiro Sumita. Instance weighting for neural machine translation domain adaptation. In Proceedings of the 2017 Conference on Empirical Methods Natural Language Processing, pp. 1482-1488, 2017.
Holger Wendland. Local polynomial reproduction and moving least squares approximation. IMA
Journal of Numerical Analysis, 21(1):285-300, 2001.
Holger Wendland. Scattered data approximation, volume 17. Cambridge university press, 2004.
Yaoliang Yu and Csaba Szepesvári. Analysis of kernel mean matching under covariate shift. arXiv preprint
2012.
A APPENDIX
A.1 PROOF OF THROREM 1
Theorem 1 (Minimax Lower Bound on Estimating the Moment under Covariate Shift). Let Hig
denote the class of all the estimators using S {(2;;: V/i = ((x;)))>= to estimate the q-th moment of f under T For any given target p.d.f. p" E {p"" (',,,p") V]. when 2 2, q S S 2g and
(f.P)) E Vo = ((.P') (f.p", ,pppppp)))))) V). it holds that
Es [T(S)) r 2 B-b max{ ( - -2)
inf sup iHEH! (E.')
(2)
Proof Sketch. The primary strategy for deriving minimax lower bounds involves creating instances from V that are similar enough be statistically indistinguishable, while ensuring that the cor- responding g-th moments are as distinct as possible. In this problem, we encounter two extreme cases. The first is the rare event case, characterized by a function that has sharp peak confined to specific small region and is otherwise constant. Moreover, the covariate shift accentuates this peak's prominence; specifically, the target distribution assigns greater probability mass to the peak region than the source distribution. The second case involves function that continuously oscillates around a constant. Utilizing the construction method outlined above, we derive the result based on the method of two fuzzy hypotheses.
Lemma 1 (Method of Two Fuzzy Hypotheses (Tsybakov) 2009)). Let F O R be some con- tinuous functional defined on the measurable space (O, and taking values in (R. B(R)), where B(R) denotes the Borel o-algebra IR. Suppose that each parameter 0 E θ is associated with distribution Ps. which together form a collection {Pag E θE of distributions.
For any fixed E O, assume that our observation X is distributed as Pg. Let F be an arbitrary estimator of F(0) based on X. Let po: f4 be two prior measures on O. Assume that there exist constants e E IR, A (0, 20) and Bo, 31 E [0, 1]. such that:
Bo, (1 E θ F(O) 2c+ 2 B1.
Ao E θ F(0) < <
For E {0, P,(-)= Po(
denote the marginal distribution P, associated with the prior distribution μý. Then we have the following lower bound:
inf sup Po(l F(O N A) 1 1 (Pol( 30 3
GEE
2
where TV(:1.) denotes the total variation (TV) distance.
Proof. We derive the minimax lower bounds established in Theorem D using the method of two
fuzzy hypotheses outlined above. Firstly, introduce some notations used in proof. Let C(2)
13

---

Published as a conference paper at ICLR 2025
denote the space of all continuous function Ω - R and [-] be the rounding function. For any s > 0 and f E C(22), we define the Hölder norm (lcx(0)) by:
D*x(() f(yil
[[ = max | (0) + max |== EER.
[
sup
| 111-111
The corresponding Hölder space is defined as (9) = {s E C(2) || < oo). Consider the function Kg defined as follows:
Ko(x) = II exp ( (- 1 x
1(|xy) $ 1), Vx = (01, 22, ,.)) R
then we define function K(x)= == Ko (2x). Ya Rd. From the construction of Ko and above, we have that K (R*) and compactly supported on [- 2 The function K is used to model the small bump. Furthermore,
partition the domain f into ma small cubes 92 .,,,..,, Pmm. each with side length of m where 7 = (yi,-.., Mn) to denote the two n-dimennional vectors formed by the sample S. With the preliminaries established, we now present the main proof below, addressing the two different cases:
(200m) à. Moreover,
use E == (Z1,..., Rn,) and
(Case 1) Construct the lower bound instance: let pº (a)) be any p.d.f. that is bounded bellow by b and above by Since Sn (x)) = Σ==1J (x))d = 1, there exists an 1 such that P(x a 14+)) Sa.- pd (x))xx S 1. Let pe (x) be the p.d.f. of the uniform distribution over [ m m + (1) Consider the following two functions go and 91:
(o(x) =0 (Vx: E EΩ),
91 (x) = b m m+=++ ((m(x - (2-)) (a E 24-), (otherwise).
This construction is commonly used in the proof of nonparametric statistics, Chapter 15 in Wainwright (201)) The choice of models the worst-case scenario of covariate shift. The functions Go and 91 are in the W* as proven in Theorem 2.1 of Blanchet et al. (2024).
Next, we compute the g-th moment under the target distribution Pa, Obviously, 1 = 0, so we only need to compute -
= [ - B (f(dd = B.
/ m ++ 1 -ct)) dx
Jn
91
1,-
= B B. m a(a-5) $) / (K(u))²
dy 2 B b. m $)-
(11)
Or- md
Construct two discrete measures μo, #n supported on {go. }1} C Ws as bellow:
1 +
1-c
(o((go))
mo (o(191))
2
1 1-c
1 +
#1 (1900)
M1 ((
2
Take e = 1, c= A = 11g and Bo = B1
I-s
we obtain that:
2
1+c
Po(s W r s A) 1o 0)
3o:
1 +
m E W 2 A) mi 1 2
1 1 B
14

---

Published as a conference paper at ICLR 2025
We proceed to compute the mixture distribution under Mu and f1:
/ TPO H. ()
Po =
Po(ū x) P(#))
II p (x,))
1 II do(Ui)) + 1 II
Snn (mn, (26)
Il
Il i:
bu(ui)
2 ia
2
Es,y
/ TPT 3. (d0)
Pi 77) = P( Pr क) = P(Ø)
II (I:()
- II
(0(())
1+6 II
II 1
II 1:22, EQ
50(ui)
d:0e; EΩ,-
4:00, E0,
where (.).) denotes the Dirac delta distribution at point ie., I (())) f(a) for any
function f : IR + R.
Then we may compute KL divergence between Po and P1 as bellow:
Po(æ ū Pi (zt, 57
Po Po 87 Pi (at,, 17)
K L(PPoIIP = log
Po (z, 37) = EgLEg
log
IPo (zt, 97)
1+t
II En 6o(y.) 1- Eor 6g (o:s)
Eg
log
Ih En, 80(y:) Lif eir 6g1 (m= (21)
+ E
II
+
1- E 2
II
8 ((x)
II II 1F L00:
50(3a)
II dyi
2
E:;; EQA
8:00 EQ
1+c
En,
E 5o(U:) 1-c
2
Tieeee 50x (os))
E
log
I-c
Eh do(U:) + Itc
Ner. 6 (cx (U:)
00
00
++6 6
60(1)) +
1-c
II
ED ((.))
II dy:
2
2
1:20, ED
=(1og
1 ++
1+E
+ log
1-
E
1 - E
IP (i:
10- 14-3 Ø
1
[+ 2
=coog
P
(i: (i:m: w. E 2x-) # 0))
Since P(x: : 22-)
m. follows that:
P (i: x 24- + Ø) =1 =1 -P((:: (2-) 2)
= =1 (1- - Pp(x E 14-1)) < (1
m )m
1
S (
1
< - (2e)
ma
Then, use the Pinkser's inequality to upper bound the TV distance between IP and P1 as bellow:
TV(P.IPP) < |K((P//PP)
I
1 (2e)
1 +
3
v3
2 e elog
- $
(12)
100
10
Using the property of Dirac measure: 1 f(z)0a (2) f(a).
15

---

Published as a conference paper at ICLR 2025
Finally, combining and 12 obtain:
inf
sup
IEs (S) - -191
HrEH! P'V
2 inf
sup
Ps
(T(( - -1 ス ]
ire (p.pp JEV
1 TV P1)
30 31
1 1
1
1
2
4
10
2 b. 1 which is the first term in the RHS of equation
(13)
(Case II We proceed to construct the second lower bound instance: let pxx) and (* be the p.d.f.
of the uniform distribution over [0, 1] For any 1 S j S m². consider f, defined as follows:
m (K(m( - c2)) (x ex
fy (x) = 10 (otherwise),
we further pick two constants a, M satisfying == (1 and M 30. Now consider
the following finite set of 2m functions:
F = (Bb)) (M + E mff): :n E (=1), si md)
Any function in F belongs to W (12 as proven in Theorem 2.1 of Blanchet al. 2024
Next, construct two discrete measure Po: j4 supported on F whose p.m.f. has the following form:
m P(u, -
p ((((())) (M Σ
k 10,
Where {w,) (0) ) and {w (1) 1m J==1 are independent and identical copies of wiew and wine respec-
tively, we take x = 3V 3m Here wp denote Radmacher random variable satisfying P(wup = -1) p and Pw, = 1)
In order to determine the separation between two priors fi and (41, we need to derive the con-
centration inequality of each prior first. Define A := Jay Bb (M + fy(x)))dxx and
Ja, Bb (M (dn, may derive the lower bound on the quantity A' = A C> 0:
/ Bb (M (x)) Sn
/ Bb. (M fz(
A' =
Bb. ( (S a(M + 1)) dy )y) 2 Bb. Ja, U-sste)
1 M dy dy)do
Ja, -5((m)))
-Bb- 9 M / (2f)(e)) doc Bb. / fx()ddæ
24-1
Bb. m * "K([mmx c;)) Bb m - |K
(14)
2 Moreover, let's set A 1 and apply Hoeffding's Inequality the bounded random variables {w (0) nm
j==1 and (w))) (1) J-=1 to deduce that:
d
> -(1 (-x)mmk) S exp (- 2(Am²11)) exp
w (0)
4md
m
(1)
< (1 - 2)m²n) s sexpl (- 2(2mmx))
1 (-
1 x2)mm
=exp
4md
2
16

---

Published as a conference paper at ICLR 2025
md By picking e c= 3 (A C)2 A = (1
A) and 30 B1 exp(- ==p(-)22²m we may
deduce that:
Ho E ( 1775 sc-
m
(1
1+ (1- A)N
=P
m
d A +
md
(Bb) (M0
(0) fd)
2
2
4
PP
Σ
(0)
1 -(1 -))mm = P
Σ
(0) j
2 -(1 -A)m²k)
1=1
j=1
21 - exp (-2 X2n2m= = =1- 9o.
mi(s E ( : 17 22c+Aa A)
m
1 A)xx
1- 1-(1- A)x ()
2
m A +
(Bb) (M+w)
2
2
2P Σ
" 2 (1- - ))m2k)
(1)
= =1 - P
w (0)
I (1 - 2)m*k)
1=1
21 - exp (- (-2 222=m== m =1 31,
We proceed to compute the mixture distribution under No and P1:
=P( / P(O G. (d0)
Fo 17 P(t)
m
1 2
p (x:))
II
(vi) +
5 (M+))) (vi)): E0,
II
2
(18) (M (x.))
j=1
1:00 EN
/ P(i E. (d))
(T P(T)
Pi (J
P(t)
md II
II p (x.))
1
II im.
(vi) +
1 1+ K
II i,,,
8 (BB) à (Mtt) (v1)
(B6) (M (M-))((x))
2
2
j=1
Denote Jn as the set of all indices j satisfying that 22 contains at least one of the points in {
In = In(a,, xn) [j:15 md and 2 n (.),..... ,,,) # 0)
17

---

Published as a conference paper at ICLR 2025
Since m 200n > have [Ja] $ n. Thus, KL divergence can be upper bounded by:
Po at 7)
Po z)
[P]
TR
log(
o 37)
Ey log(
Po( 57)
P1 (z; y)
P1 P1 y)
m
1 En, (BB) (ar fy(mm))
(1/i)
-
2
Ii en, 8 (B6) (M (M- (,=+)( (16)
Eg
log
1- x Iha (18)) ( (M- (yi) + 1 j=1
Ilim 6 (1b) (MS+ (36)
00
1 +
II ER,
8 (Bb) (M- (z,))) (vi) + 1 II (M+1((0))(1A)
IIdyi dy.
a
2
j=1
EQ,
lim En, (BB) & (as f2 (mm)) (y/t) + 1 Iim,en 6 (B8) (As ((x))) (11))
8
00
Eg
log
1-x 2
Is, 8
(0i) + 1ts
2 Ih (BB) h (ar f3 (1/))
(BB) 2
jEJn
(M f,(m,))
1 + K
1 1 K
8 (Bb) (M ((a))
(Bi) +
6
(Bb) (M+5)( (4:)
II dys im
2
2
km
Ex [
1 *
+ K
1 1 K
Ki
log
+
+log
1
2
1+
2
1 +
< nvi log
1 K
Use the Pinkser's inequality to upper bound TV distance between Po and P1 further:
TV & 2 (LL(Fo)(P1) S
nN log
1 + n
S
2 K
3n
1
(15)
2
1 - k
3
Finally, let A = (1 A)mma A' and 30 31 = exp( - 22222² exp(
-29
Combining
6
14 and 15 we obtain the final lower bound:
inf HEEH!" ""p".""EE""
sup
Ar
(1x:) (w))=1)) -r9
2 A inf sup Pla.a [79 (1)((1)))))) (u)iza) r/ > A
Avent (f.p" DEV
2 (1 - 1--m))mmm' 1 1 (P)) Bu 32
2
2 B.
(16)
Combing the two lower bounds established in 13 and 16 completes the proof of Theorem I
n
A.2 PROOF OF THEOREM 2
Theorem 2 (Upper Bound Moment Estimation with Smoothness). Assume that p > 2, q < P S 2q and? 5 > 2q
I Let (f.p". E V(b b. s,s,)) and we have sample S = { Vi
((x:)) If fs, satisfies the Assumption then the estimator frg constructed in equation
above satisfies
Es [ig(S)) 17] s B. b. n max(ma(aa -
We begin with the key lemma used the proof.
Lemma 2 (Sobolev Embedding Theorem). For some fixed dimension d E N, we have that:
(I) For any s,t E No and p.q E R satisfying s > t.p d and S P < q S 00, we have WSP(R C (W (Rd) when the relation I p
q d holds. In the special case when t = 0. we for any s E N and p, E R satisfying 1 S p < q S xa and - - 4
have (td) C (RR))
(II) For any (0. 1), let 3 - E (d, oo). Then we have e³ (RR)) n ( C C* (Rd)).
18

---

Published as a conference paper at ICLR 2025
Proof. Firstly, decompose the mean square error Es (1 -13 into
bias
part
Es| [s]](]((S)] - 19 and variance part Es [ir](S) - Es [
Estimator (S) is unbias for 17. so the bias part is zero:
Es [fg(()) Exxr-
[ (x)
Σ ((((a:)) : (v --, (a:)))
+
Ex~p-
(1% (X)
p" p²(x)
((x))--3,, (00) p² (x=)do
nn pe (x))
Ex~P- [1% (X)
Ex-P-
[x(X - f33 (x)
Ex-P- [f*(X)] = 17.
Using the law total variance to decompose the variance part further:
Var [1)(()) = Var (1))))) si)] + Var E ((rg(() [s)]
Since (M)(()) si) r7. the second part is zero. So we only need to compute the first part.
E Var (S) 8.)]
E
Var
2
Σ
w((x:) (v² f3, (a:)) |S
2
Var (xX) (X) f3,(( (x)) |s.)]
71
2
Ess ESsis (w(X). (( - 83, (x1)) )
11
< B² Esi Es,is. (F(X) - f2g (x)) 21
2
(17)
n
Following the proof in Blanchet et al. Es, ESIs,, (xx())
(004), we further upper bound the expression Let Is. = Ss, represent the difference between the
estimator fs, and underlying function f.
(((t)-/3,))) Es. ES,s (1(x)) (x)) < b. <.sss Es, (1, ((f(z) + gs. (z))²- (x)))) dx
1/ (Maz) 13, (3((aa)) dx
=6- Es.
195; (m) S
2
-b IEss,
((((x) - dæ
185((m) (w)
198 (w) (w)
<b- Ess,
1dy
(f((x)) 22) dx
(Hölder's Inequality)
<b. EEs,
98, (x))
19s. (x) max { 2 | 2 (x))
dxc
Sb. EEs
24 9s, (x:
da
+ d. Es, 1 |o' (m) 2 2 dxc
(18)
19

---

Published as a conference paper at ICLR 2025
Let's further upper bound the two terms in
18 For the first term, since 3 1 1 we may apply
p 2q"
equation 4 from Assumption by choosing
2q. This leads to the following deduction:
Es,
24 n 95.
(x)
dæ = Es, [Ilfs. -f1l [00)
2 b (())
) s b. n..1a
20 2 # = b..nnnn - -1) 2)-1 (since p S 24)..
(19)
2
Now, we proceed to upper bound the second term in equation 18 Here we define Po := (max
d-sp when 8 p and Pe = oc otherwise. By the Sobolev Embedding Theorem, we have ( S (S2). There are three distinct cases to consider based on the smoothness parameter 8.
2. 03)-- that is, Po = pd
(Case I) When 8 E (g. oo), we have ps = oc which implies that f E (W) C (1)). Similarly, by Assumption [ fs, is also in the Sobolev space (S)((S) S ( Therefore, the difference 9s. = fs. f E ( S _ (2) S (S2). By picking r = 2 in 4 of Assumption | and utilizing the facts that p 2 2
and f E L (It), we can deduce that:
Es, 1/ |3. (a) 20 - 2 (z)) dæ
1/ Ios, (a:) dæ
S Es,
(Hölder's Inequality)
-Es
[1sss, [1 < b - $)1
( )² b. -
(20)
(Case II) When e (d)2g-p) p(2q-2)
d), it follows that
pd
pd
p(2q 2)
Po d sp
d p(24
d(24-p)
p-2 2
which implies f E WP)((S) S CP- C L (1) C CP()). Since -ーz
1, it follows that f2a-2 E L (St). Moreover, since fs, E WS* C (P)),, we obtain gs. = fs, f E CP))).
Given that 2 2, can further deduce that 93, E L (92). We may then apply Hölder's Inequality to obtain:
dx = Es, [ll9.] fx) Es. 1/1 J (x) 2x)))
<Es,
|105 (x) 2 (0)
2 (x)) محf cm.] [las. (x) [(((0)
(Hölder's Inequality)
<llf 20-2
Es,
22
(0)
Note that the function h(tt) _ is concave and _ E (= 1] when 2 2. Thus, by applying Jensen's inequality and choosing = of Assumption we can upper bound the last term as follows:
[1os, (x) (1))12))))) = Es, [1loss (x) ( Es.
<Es,
I1os. (x) (())(()))))
Es. [1lis f(x))
(Jensen's 's inequality)
Sb
n -
+ 1)+
2 S h. n 2.
This gives us the final upper bound under the assumption that s E dd(2g-p)
25) 25 ( as follows:
Esi [ 03, (a:)
2(x) dac $ b. 2
(21)
20

---

Published as a conference paper at ICLR 2025
(Case III) When d(2g-p) d(2g-p)) ). we have d which implies that po d-sp 2pg p((4-2)
pd satisfies
p
2q < Po < p(22-2) Given that Po > 2q > 2q 2 and f (S S C (9), it follows that
p-2
f2a- 2 E [ (9)) Moreover, since Ps 2q, we have 2n
po+2 Po- Additionally, because
Po < 2(29-2) follows that Po+2-24 > p.
2p.
p-2
Given that both fs. and f are in the Sobolev space (SP( C _ (2), it follows that gs.
fs, f WSP(1) S (S2) S - (9t). Since q 2 + 24 2 1, we have 9ă
L C (9)). We can then apply Hölder's Inequality to obtain:
Es
93. (a) )
(z) dx = Es, [lloš, 2 [c))
<ks 11,93 (x)] CrottEa (02)
|1 ( + (1))
(Hölder's Inequality)
<1lf(>) 2g-2 (2) Es, |los. | (2))1
200
L
(9)
Note that the function h(t) = t Pot2 2x
Po
is concave since 2 1. Furthermore, given the assumption
E
d/2g p))
4(2g p)
have d=sp'
pd
2q. This implies:
2pq p(24 2)
Po + 2 - 2q
pd sp
+ 29
2
d sp
2po
pd
pd d=sp
pdl
d-sp
i.e., po+2-29 E ( dp ldld
1]. Hence, we may apply Jensen's 's inequality and in Assumption 1 to upper
pd
bound the last term:
12 2u Pe
(less) (2)]l
Es,
|los, (x=)1
200 L 20 (03)
Es,
200 Loo Loo+2 1--t2-20 ((3))
po 20
S Ess [ (11ss, (2:)
1o Rno
vo.
2
Rss [
(11)s (2z) - f(x) (x)
2no
1o.13 2x Po.
Po
L
2o (52)
L FFo (1)
S b. ( (")
po 22-42-2 )+
2
b.nn"
2 +2( po12-20)
Recalled that we have proved that Po E (2q, p(2g-2) this implies that Po 2) < p(2g 2)
p-2
2po > p(po + 2 - 2q), i.e.
2o 2g
Then we may simplify the last term above as follows:
2ps
28
1 Po 2 2q
2s
2
(1
2
2q
24
1
+
1
24
1.
d
p
2p.
d
p
Po
Po
Po
p
This gives us the final upper bound under the assumption that 8 E
d(2g-p)
d(2g p) 2
as follows:
2pq
S |93, (x)
Es.
dæ S b n 29( -1
(22)
Combining the upper bounds derived in 19 19
21 and
22 we may deduce that:
Ess Es, s.
(f%(
f% (x)
S 62_
[ 2 ;
-1-1 + max(n #, 20 - 23-11]. (23)
Finally, substituting 23 into 17 gives the final upper bound:
Es
(T)(5) 17
1 Es [1gg(5) - 13/² = E Var (f))(S) s.)]
< b. n
maax--o6$ 1---0120 -1,
21

---

Published as a conference paper at ICLR 2025
A.3 PROOF OF THEOREM 3
Theorem 3 (B-independent Bound). Denote 2tp := {x w(x) > T3 as the area where the like- lihood ratio exceeds the threshold T, and let (P( = g()) denote the probability of this event. Under the conditions in Theorem the upper bound for the variance and bias of the truncated
estimator arr are given as follows:
E( E(HG) 19 < P(27).
Bias
Variance = IE [1z B((r7) 2 52. + +B. (P(T))?
If we further assume that (T)) S T and pick T = (r((n) a
then we obtain the following
B d-ineppendent bound:
Es [1 17 191] S
r(n)
(8)
where r(n) maxi -0 11 -11-
is the same order in Theorem 2
Proof. Decompose the mean square error Es (S) r3|" into bias part [s|A ry]
and variance part E.s ( Es (
We first compute E [8) S. may deduce that:
Recall that 27 (x w(x) < 73 and 22 22/2tt then
[1((()) S = ExxF=
f3 (x) + rr(((x)) (f((z) - (3,(5))) (x)) .p (x))d
=E Exxr [r,(1)] + / p²(x)) (f( ff²; (x))dxx
T (x) (f) f33 (x))
24
(x))dx + ( (x()) f3, (x))dx / T T. (x)) (f(())))))))))))))))))())) f3, (x))da. (24)
Jnf (x))
St
We proceed to compute the bias term:
E si]] - ry]
Bias
E
/
/ (²(x) n2
Es.
so p" pixx) (x))dx + 5nz (y'( (f)(z) - f3, (x))
-Es,
a, (p'(x) - TTpp(x)) (f((z) - f3, (x))
(Since w(x) > T in 1
/ (x()) (ww(x) - T) (f) f3. (x))dx
-Es,
nn
/ pd (x()) - w(x) (f) f3, (x)
<Iss,
-Fas,
p² (x()) (f)())) 12, (z:) dax
<Es, [P(27)]
(Since fs, and f are in (P())
<b I.(T))
(25)
Using the law of total variance to decompose the variance part further:
Var [S)()) E Var (H) s:)] Var E (H))()) (ss) s.)]
22

---

Published as a conference paper at ICLR 2025
The first term can be upper bound by:
E Var (S) si)] = 2 Var (T((((() (f(()) - (x) |s)]]
1 Es, Essis (rx(w(X)) (f* f's. (X))
f3, 22 Es. Esyis: (f, (x)
2 T b()]
(26)
Substitute equation 24 in the second term:
/ (p'(x) T p0 (x)) f3, (x)
(S) ss)] = =Var
Var
E
27
<Bs.
(x'(x) - T - (xx) 13 (2))dx
St
Bs
(P(27)
$ bb IP (127))
(27)
The last term follows from the proof of Theorem where r(n) = =n" max! - -
Finally, combining the results 25
26 and
27 above, we obtain the final upper bound:
Es AQ(())
ry|] s / $ Es AT 13 13
Ess (5)
-13
2 + Var (8)
2 V [b P[ + [ (r-]) (B-((2)))
Furthermore, if P(27) < T-a, by taking 7 O(((n)) we obtain the following result:
Es (17((5) - 1911 r(.
A.4 PROOF OF THEOREM
Theorem 4 (Convergence Rate of Plug-in Truncated Estimator). Under the assumptions in Theorem the convergence rate of the plug-in in truncatdd estimator H. is:
E
191 S
(1z(S)
-19] + +m=
(10)
23

---

Published as a conference paper at ICLR 2025
Proof. Decompose the enror of Hi via the intermediate estimator H7:
Esss
H 13
Ess
H H9 + Ft. r9]
Ess.s'
117. f7
+ Esuu
[1 - 19]
< Esus
Σ
(rT((((x:)) nT (w)())))) (y, f3 (2:1)
+
7 (mi:Di)E
additional for estimating w=x)
Esus
[fg. (X)
+
Esus
[1 1
arme the case when un( is known
Monte Carlo simulation error
The first term represents the additional due to estimating the likelihood ratio w(x)). The second term accounts for the Monte Carlo simulation error estimating TE Tx [f'3, (X) using m unla-
beled data S' form target domain, with convergence rate O(m 3). The third term corresponds to the estimation error of fi?. as discussed in Theorem
The convergence rates of the second and third terms have been previously addressed; thus, we only need focus on the first term. Note that the first term can be upper bounded by:
Essu
2 Ti
Σ (Tr(ύ(x;)) (w(x)))) (uf f3 (xx))
(aNN)ES
[[((())) - f3,10 (a:)
<2T
Esus
[ro(a)) 13, (zt) (x)() (a)))
<2T
Esuu
which is upper bound by the variance term in Theorem Thus, the convergence rate of H4. is:
E
(H(SSS))
ry] - (T) 17] + -
A.5 PROOF OF COROLLARY
Corollary (Double Robustness of Plug-in Truncated Estimator). Pf(T) + as n + co, then the estimator 11 exhibits double robustness. Specifically, this means that long either w(x) or fs, (ar) consistent, the moment estimator Hr. is also consistent.
Proof. The case when fs, (x) is consistent has been discussed in Theorem consider the case when (xx)) is consistent. Decompose the error follows:
so we only need to
m
2 n
E Esus'
[ 17
(x))
(w)()); (yi - 83 (z:)) 17
172
(m:
2
<lEsus
(+(())))) f(( - 13 +
n
(E
EEsus
(x))
2
Σ
(w(())))) f3, (2x.)
m
n
24

---

Published as a conference paper at ICLR 2025
Algorithm 2 Stabilized Algorithm for Unknown Likelihood Ratios
1: Input: labeled data: S { y/ = fxx)) J== unlabeled data: {
2: Use S and 8' to construct ancillary sample Sc {(x,, 0) U ( 1
3: Use ancillary sample Se to train a classifier, and then compute the likelihood ratio estimator (x)x) as given in equation 29
4: Randomly split S into two parts S = ((,, a)) and S2 = {( v:) -+
5: Train a machine learning model on S₁ to obtain fs, (z).
6: Use S' and S2 estimate the 1 based on equation
7: Output: q-th moment under target: 17.
If (x) is consistent and P(QT) + 0 as n - oo, then (x)) is a consistent estimator of w(x).
Let > denote convergence probability. holds that:
2
Σ
Tr(#(x;)) (xx; -pp Ex-r- (X))),,
m
(1 - E Ex-F- [83 (X),
m
2
Σ (ύ(())) (z,) +pp Exxe- 153, (X)).
(E..
Therefore,
H4((US) - 17
A.6 STABILIZED ALGORITHM FOR UNKNOWN LIKELIHOOD RATIOS
The stabilized algorithm for unknown likelihood ratios proposed in Section is summarised in Algorithm !
A.7 ESTIMATE THE LIKELIHOOD RATIO
The most straightforward approach is use the unlabeled source and target data to estimate p and f², respectively, and then compute the likelihood ratio p But intermediate step of estimating P and 6 may introduce additional errors and affect the robustness the estimation process. Therefore, it is crucial develop methods that allow us estimate w(x) directly from the data without relying on these intermediate density estimators. To achieve this, we introduce a latent label Z E {0, 1} indicate whether sample is from the target distribution (Z or the source distribution (Z = 0). This formulation allows us to express the likelihood ratio as:
8"
(X) P(X Z 1) w ( P(X = 0) PiZ = X)
P(Z = X)
P(Z 0) P(Z = 1)
(28)
where = P(Z = 1 x)) is known the propensity score. With data {(x,, +)){ and {(0), m- we can estimate P(Z = 1) and P(Z 0) with m4n and m+n respectively. To estimate the propensity score, we can apply classification model that distinguishes between source and target samples. The propensity score estimator, denoted probability that a sample with feature x belongs to the target distribution. Using the estimated propensity score, can derive the plug in estimator of the likelihood ratio follows:
u(x), represents the estimated
ē(x)
n
((x)
(29)
1 ē(xx) m
25

---

Published as a conference paper at ICLR 2025
B APPENDIX
B.1 DISCUSSION ABOUT THE MOTIVATION
Generally speaking, many high-stakes areas are interested in estimating the q-th moment of an un- known function, as higher-order moments are often essential for capturing risk-related characteris- ties in real-works applications beyond the first-order moment. For example,
in finance, investors are interested in the shape of the asset's return (which is an unknown function of the factors) distribution, especially its skewness and kurtosis. These higher- order moments help investors assess the risk characteristics of an asset, particularly extreme risks (tail risks) and asymmetric risks. Moreover, covariate shift is commonly observed among factors across different industries.
in medical fields, we need to monitor the volatility (variance) of certain patient metrics to identify high-risk patients, which requires multiple measurements. However, measuring these indicators for rare diseases (e.g. Alzheimer's ' disease) is very costly. Fortunately, this metric is a function other, more easily accessible indicators, so we can estimate this function by collecting data those indicators. Moreover, covariate shift is commonly observed across different population.
In classical causal inference (Ding 2024 The average treatment effect on the treated (ATT) is defined as (1) (() T= where Y()) and Y (0) represent the potential outcomes under treatment (T' = and control (T' = 0). These potential outcomes are un- known functions of the covariate X. The difficulty is to estimate E (0) = 1] which can be written as:
E (0 T- 1] =R =B =1 E (Y(0) T 1]}
=Ix (X))
But we only have sample
(v. 23
(0)
where a; ~ PX|T=-
Due to the broad applicability of these scenarios, we have unified these questions within the frame- work of estimating the q-th moment of unknown function under covariate shift.
B.2 DISCUSSION ABOUT THE ADDITIONAL ASSUMPTION IN THEOREM 3
Insights into source/target distribution pairs that satisfy g(T) S T-a:
Indeed, sufficient condition for g(T) < T that the likelihood ratio w(x) (c))
exhibits a polynomial order in a. Therefore, any distribution with polynomial order p.d.f. satisfies this condition, such as the Beta and Pareto distributions.
Additionally, we can also consider (x) with any f.d.f. that has faster rate than a polyno- mial, such the truncated Gaussian on Q. provided that wxx) still exhibits a polynomial order (e.g., by taking p" as a Beta distribution).
Moreover, the benefits of truncation were also observed in certain distribution pairs that do not satisfy this condition in experiments, such as when both the source and target dis- tributions are truncated Gaussian. Therefore, this condition used solely for convenience in deriving the upper bound of the truncated estimator and provides insight into changes in the convergence rate.
The estimator År. in Theorem 3 may not be minimax optimal:
The minimax lower bound B- B-b-r(n) established in Theorem I applies to the where the distributions are known. Therefore, we can only assess whether an estimator is minimax optimal under the assumption that the distributions distribution class V. However, the upper bound b- r(n) Tf in Eq. (8) is derived under this known distribution case but within a more restrictive distribution class, as we impose an additional assumption on V, specifically gT) T Consequently, the corresponding
known and belong to the same
26

---

Published as a conference paper at ICLR 2025
minimax lower bound will be less than equal to the bound in Theorem 1. In fact, the upper bound b r(n) 14a in Eq. (8) may outperform the minimax lower bound B b- r(n) when B is large.
When the distributions are unknown, we do not have the minimax lower bound, and there- fore cannot determine whether the estimator is minimax-optimal. However, the minimax lower bound derived in the known case serves as a lower bound, which may be loose, but still provides valuable insight.
The truncation will bring benefits when is large, as it reduces variance by introducing some bias. This is especially useful in practice because, when the likelihood ratio w(x) is unknown, the estimator ((x) often involves some excessively large values. Specifically, the upper bound after truncation is b r(n) I+a compared to B b r(n). which is the upper bound before truncation. Note that, the new bound dose not depend on the B 1, which characterize the intensity of covariate shift, but the rate in r(n) decreases. This is especially beneficial when B is large, as helps mitigate high variance, thereby improving the stability of the algorithm.
When a = oo, the upper bound matches the bound in Theorem 2 for the case of no covariate shift:
when almost surely. However, since both are p.d.f.s on the Ω so p" p'(x) = px() almost surely. Thus there is covariate shift, and the convergence rate reduce to br(n), which matches the bound in Theorem 2 when B (i.e., no covariate shift).
P((x w(x) > T}) 0 for any T > 1, it holds that p" (x) > p'(x)
B.3 CONSTRUCTION OF THE ORACLE IN ASSUMPTION
T
When {x:}__ are independent and uniformly distributed over S2 the optimal function estimator is constructed using the moving least squares method, as demonstrated by Krieg & Sonnleitner (2024) (when s > ) and Blanchet et al. (024)) (when s E (2dg-dy these results hold when the sample drawn from distribution with p.d.f. that is both upper and lower bounded. We need to introduce some notations first.
2pg ()). Thus, we only need to verify that
Definition 2 (Covering radius). For any compact region R C -Rd the diameter R is defined as diamd Rt- == SuP2,ER | 1 yll- Moreover, for any two compact regions Rı, Ra C CRd, the distance dist( R1, R₂) between them is defined as distí Rı, R2) = [i,, - -Cn llo. where 11- denotes the loo norm in Rd and CRi CR2 are the centroids of R1. R2 respectively. For any collection of n data
points P = 1..,,.., EnJ, the covering radius of P in Ω = [0, 1] is defined as follows:
p(P,S) == sup inf |y - æx||- yen ISiSn
(30)
The properties of the moving least squares estimator is summarized the following Lemma.
Lemma 3 (Properties of the moving least squares estimator (Theorem 4.7 in Reznikov Saff
)) For any given collection of points P = [æ1..... Æn with covering radius PP.))). there exist constants a1, 02 independent of and continuous functions uae Ω RR < S n), such that
n (z)) Ei T (x.)),, (y) for any y E Ω and any polynomial n with deg(T) S 8
E Un, (n, (v)1 S a1 for any Ω
u (y) for any y E Ω and x E P with ||x yll azp(1 (P..))
Based on the function un (1 S i S n) given Lemma we define function estimator K, Kn Kn((x,) y {f(x))]?, for f as
K,((n,)i (f()))
Σ (ax))u
This estimator is derived using the moving least squares approximation, originally introduced by Wendland (200T). For further details, see Wendland (2004).
27

---

Published as a conference paper at ICLR 2025
To demonstrate that the function estimator K,, defined above satisfies the upper bound in Assump- tion we need to control the covering radius P(,, when P is drawn from a distribution with a p.d.f. that is both lower and upper bounded.
Lemma 4 (Bound on the covering radius (Theorem 2.1 in Reznikov & Safi (2016))). Given P == ( Inf sampled independently and identically from a distribution with a p.d.f. that is both lower and upper bounded on ! = [0, 11", have that there exist constants eı C2 > 0 and ag 0, which are all independent of n, such that the following inequality holds for any a > Ag:
Jalogn n
P
p ((P,))
2
72 1-2a
12
Building on the Lemma 3 and Lemma we can use the result from Appendix E.3 Blanchet et al. (2024) to demonstrate that the function estimator Kn, satisfies the upper bound specified in Assumption
C APPENDIX
C.I COMPARISON OF DIFFERENT METHODS
In this subsection, conduct experiments on both synthetic and real datasets compare the per- formance of various methods, highlighting the necessity and advantages of the two-stage approach under covariate shift.
Synthetic dataset. In our experiment, the source distribution IPo is defined as truncated normal
distribution on [0, 1] with mean 0.2 and standard deviation 0.3, denoted by tnorm([0, (0, 1). 0.2, 0.3). To vary the intensity of covariate shift, we consider the target distributions tnorm([0. 1], p. 0.3), adjusting the mean parameter μ.. We set f(x)
+ x + sin(162) and select μ 0.2, 0.4, 0.6, resulting in corresponding B values of 1.00, 3.98, and 12.08, respectively.
We set y 2 and train fs. using linear regression. Each experiment is repeated 100 times. The performance of the following three estimators is compared:
Monte Carlo estimator (MC): estimate I using [S] Eies w(x:)yf
One-stage estimator (One- stage):: train fs using the entire dataset S, and then estimate 1 by Ex-F-
(X)
Two-stage estimator (Two-stage). estimate 13 using the truncated estimator from equa- tion 7 with 7 set B.
The results are presented in Figure 3 It indicates that the Monte Carlo estimator outperforms the two-stage methods the absence of covariate shift (B = 1). However, as B increases, the two-stage estimator demonstrates greater accuracy and improved stability, highlighting its necessity under significant covariate shift.
Real dataset. We illustrate the application of the proposed two-stage estimator under covariate shift with an empirical example. Specifically, we use the airfoil dataset S from the UCI Machine Learning Repository, which comprises N 1503 observations of a response variable Y (scaled sound pressure level of NASA airfoils) and a covariate X with d = 5 dimensions: log frequency, angle of attack, chord length, free-stream velocity, and suction side log displacement thickness. We conducted an experiment over 100 trials, where in each trial, we randomly partitioned the dataset into three subsets: Strains Sela, and Steat-
Strain containing 50% of the data, is used to construct estimator of 17.
Stest, containing 30% of the data, is used to create the covariate shift and establish a ground truth for 17. The covariate shift is introduced by sampling points from Stest with replace- ment, using probabilities proportional to ((x) = exp (x T B), where /3 (-1, 0, O, O, I)T. We denote the resulting sample as Sahift, which is used to compute the ground truth by
Sonsyel E(e. 8/
28

---

Published as a conference paper at ICLR 2025
Boxplots errors on real data
30
20
Error
10
MC
pne-stageTwoo-saag Method
Figure 5: Boxplots of errors for the Monte Carlo estimator, one-stage estimator, and two-stage estimator on the airfoil dataset. The proposed two-stage method outperforms both the Monte Carlo estimator and the one-stage estimator under the covariate shift setting.
Satss comprising 20% of the data, is combined with Sahefe to train a classifier for estimating the likelihood ratio and obtaining the estimator (xx).
We compare the three different estimators as follows:
Monte Carlo estimator (MC): estimate 13 using [Strama (.. (r(x))y?
1
One-stage estimator (One-stage); train fSrmaw using the entire dataset Strain, and then estimate 1 by [Baasell (e rai
Two-stage estimator (Iwo-stage): estimate 17 using the truncated estimator from equa- 7
The results Figure 5 demmostrate that the proposed two-stage method outperforms both the Monte Carlo estimator and the one-stage estimator under the covariate shift setting.
29


Reviews:
[{"review_id": "c4oMWBDvFl", "reviewer": "Reviewer_PpwD", "summary": "This paper addresses the problem of estimating moments of responses under covariate shifts. The authors propose a two-stage algorithm, using a doubly robust structure with weight truncation, that achieves a minimax estimation lower bound.", "questions": "1. Do we really need to do two-stage algorithm? For example, can $\\hat f$ obtained from importance-weighted regression satisfy the upper bound? (perhaps truncating the weights in the regression?)\n2. Assumption 1 requires $f$ to be sufficiently smooth. Can the upper bound still be matched if $f$ is less smooth?\n3. There is not much discussion on the difference with recent minimax optimal results, e.g., [Ma et al. 2023], which also addresses estimation under nonparametric space. More detailed comparisons would help highlight the unique contributions of this work.\n\n**Reply to authors' response:** I thank the authors for the clarifications and additional experiments. The explanation on the literature regarding known versus unknown distributions is helpful, and so is the additional experiment that shows the significance of two-stage over one-stage procedures. Regarding the relative novelty, my feeling is that using truncation on likelihood ratio to control bias-variance is, in some sense, obvious as an idea, but working it out rigorously and demonstrating its usage as the authors did requires a lot of careful work, which I appreciate. I raised my score in view of all these.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The investigated problem of estimating moments under covariate shift appears fundamental, and the paper offers an approach that the authors show is minimax optimal, which seems a valuable contribution.\n\n - The technical results are presented and interpreted clearly.", "weaknesses": "**Technical Contributions**: The novelty in attaining and proving the main theorems (Theorems 1 and 2), compared to the existing literature, is unclear. In particular, the proofs appear similar to those in Blanchet et al. (2024), with the main addition being separating and upper bounding the term $w(x)$.\n\n**Limitations of the minimax lower bound results**: If I understand correctly, the minimax lower bound result, as well as the proposed algorithm from the authors that achieve the lower bound, assumes the source and target distributions are known. However, a major difficulty of covariate shifts is to handle the unknown distributions. In this regard, the authors only show an upper rate bound and double robustness of their approach in the latter setting. So, I feel there's a gap between the claimed minimax optimality and the actual efficiency of the proposed approach, and this gap is not just the usual discrepancy between theoretical bounds and practical algorithms (as common in ML theoretical guarantees), but is about whether the claimed theory is conceptually trying to capture the fundamental difficulty of the estimation problem.\n\nThe above are my main concerns. Additionally, the following suggestions might be useful:\n- It would be helpful to provide more justification for the critical Assumption 1, for instance discussing specific estimators that meet the assumption (i.e., to make the paper more self-contained instead of just referring readers to previous papers).\n- Section 4.3 deserves more discussions. For example, \n- It would be beneficial if the authors could draw parallels of their assumed condition on the probability concerning likelihood ratio with existing literature, possibly through examples demonstrating the probability of large shift regions and the functions $g(T)\\leq T^{-\\alpha}$ for classical parametric distribution classes.\n- More guidance can be provided on choosing threshold $T$ in practice. For example, how much do we need to know about $\\alpha$ to choose $T$ properly.\n- More discussions can be provided on the implication of the power decay $\\alpha$. In particular, when $\\alpha = \\infty$, does the convergence rate reduce to $\\bar b r(n)$, matching the dependence on $n$ observed in Theorem 2?\n\nSome typos:\n- In the right-hand side of eq (4) in Assumption 1, the last “+” should be a subscript.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "geFcgWuxiO", "reviewer": "Reviewer_vWi5", "summary": "This paper considers the problem of estimating the moment of an unknown function under covariate shift. Specifically, the paper aims to estimate the $q$-th moment of $f$ under target distribution $\\mathbb{P}^*$ with p.d.f. $p^*(x)$, based on a random sample drawn from source distribution $\\mathbb{P}^{\\circ}$ with p.d.f. $p^{\\circ}(x)$. Here, the unknown function $f$ is assumed to belong to the Sobolev space $\\mathcal{W}^{s, p}(\\Omega)$ with $\\Omega \\subset \\mathbb{R}^d$, where $s$ indicates the degree of smoothness and $p$ specifies the integrability condition of these derivatives. The paper characterizes the impact of covariate shift on the minimax lower bound when $p^{\\circ}$ and $p^*$ are known. It turns out that a constant $B \\geq w(x)$, where $w(x):=\\frac{p^*(x)}{p^{\\circ}(x)}$, plays a central role in the established minimax lower bound. Then, the paper proposes a two-stage algorithm which attains the minimax lower bound up to a logarithmic factor for two cases: (i) $p^{\\circ}$ and $p^*$ are known and (ii) $p^{\\circ}$ and $p^*$ are unknown. For the latter case, the paper truncates an estimator of $w(x)$ to stablize the algorithm. The proposed method requires two models: one for estimating $f(x)$ and the other for estimating $w(x)$. The proposed estimator is doubly robust in that it will be consistent if at least one of the two estimators is consistent.", "questions": "(1) There is a typo in the title: \"Minixax\" should be \"Minimax\".\n\n(2) When the target distribution is unknown, it is assume that m (≫n) unlabeled samples from the target distribution. Is it necessary that m is much larger than n? This seems quite restrictive. Also, what condition is exactly needed between m and n? Is it enough to assume that $m/n \\rightarrow \\infty$?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is clearly laid out. Specifically, it provides the minimax lower bounds and develops an estimator that matches the lower bounds up to the log factor when both target and source distributions are known. Furthermore, a doubly robust estimator is developed when the distributions are unknown.", "weaknesses": "Although the paper considers an interesting problem in theme of an important topic, namely covariate shift, there are two major weaknesses. \n\n(1) The problem of estimating the $q$-th moment of an unknown function $f$ is not well motivated. On page 1, it is stated that \"This is a common scenario in many fields, such as counterfactual inference in causal inference (Ding, 2024).\" However, this is not informative enough; Ding (2024) is a textbook and there is no concrete example by simply citing the textbook.\n\n(2) In addition, the current numerical example is very artificial and has nothing to do with real applications in causal inference or any other substantive field.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qpX1USQ5ih", "reviewer": "Reviewer_gBmp", "summary": "The paper studies the problem of functional estimation, specifically, a moment of some function, with respect to the target distribution under covariate shift. The paper establishes minimax lower bound of this problem under RKHS assumption on the objective f, with additional constraints on source and target distribution. Furthermore, the paper proposes an estimator which attains this lower bound. The paper also introduces a practical version of the proposed estimator, and further establishes convergence rate.", "questions": "On the decaying rate assumption on g(T) in theorem 3, it seems that this imposes further restrictions on the source/target distributions. In addition to the statements on the weight itself, is there any way to gain further insights on what type of source/target distributions pairs would satisfy this condition?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "The paper is beautifully written with a solid theoretical results. Starting from the optimality, it presents an idealized estimator which attains the optimality, and most importantly, it provides a practically usable estimator and establishes theoretical results for the stabilized estimator. The structure and presentation of the theoretical statements hits perfect balance between technical details and insights for readers to follow. The results are stated in a way how each step of the proposed estimator influences the final convergence rate, which really helps to gain insight on the proposed estimator.", "weaknesses": "No major weakness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LzoAxkWfiF", "reviewer": "Reviewer_AoMc", "summary": "This paper proposes a moment estimation method under covariate shift.\nMore specifically, the authors consider the moment estimation problem with the Sobolev class for the labeling function and with a bounded likelihood ratio of the source and target covariate distribution.\n\nUnder this setup, the paper proves a minimax lower bound on the estimation error.\n\nThen, the authors propose a method whose upper bound of the error meets the lower bound, but with the knowledge of the target covariate distribution and the likelihood ratio.\nThe proposed method combines any estimate of the labeling function and the estimate with truncated likelihood-ratio weighting to construct a doubly robust estimator (Eq. (3)).\n\nFurthermore, the paper proposes an estimator that does not use the knowledge of the target covarite distribution or the likelihood ratio but estimate them using additional unlabeled data sampled from the target distribution. Under some tail probability condition on the likelihood ratio, this estimator has an upper bound slightly worse than the minimax lower bound.\n\nFinally, the paper presents some simulation to see the impact of the degree of covariate shift and the smoothness of the labeling function.", "questions": "### Major concerns\n- Is there anything I am missing in the first comment in Weaknesses (about the minimax lower bound)?\n\n- Is there a practical application where there is no noise or uncertainty in the label?\n\n- Does the truncation bring any benefits in theory?\n\n- Do the authors have any result for the ablation study about the effect of truncation? That is, comparison between the proposed estimate and that without truncation.\n\n- Any comparison between the proposed method and the Monte Carlo estimate only using $\\mathbb{E}[\\hat{f}^q(x_i')]$ or $\\mathbb{E}[w(x_i) y_i^q]$?\n\n### Minor issues\n- Perhaps, the paper should mention that Ma et al. (2023) uses the truncation trick but in the case of unbounded likelihood ratios.\n\n- Is the calculation of the KL divergence with the delta function mathematically sound? Because there is the logarithm function inside the integral. In particular, I could not figure out how to obtain the equality in line 718. Could the authors detail this calculation?\n\n- What is $s$ in $f(x; s)$? Is it $k$?\n\n- Is the $+$ at the end of Eq. (4) a typo?\n\n- In line 644, maybe $K_0$ should be $K$ (otherwise, the support should be $[-1, 1]^d$).\n\n\n---\n**Edit:**\nAfter the discussions with the authors, my concerns about the soundness has been addressed. I have adjusted my score from 5 to 6.\nHowever, I still think the assumptions that there is no noise in $y_i$ and the density is known are strong, and the applications are very limited.\n\nMoreover, the former assumption allows one to change the label from $y_i$ to $y_i^q$, to reduce the problem to the expectation of the mean under covariate shift. This type of problem has been already well studied in the treatment effect estimation literature, including the doubly robust estimators. The submitted paper might lack comparison with such work and discussions about its novelty.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The paper is nicely written. The analyses in the appendix are quite involved, but I can see the authors' efforts to make them accessible.\n\n- The paper studies an interesting and useful problem and theory.\n\n- The proposed doubly robust estimator is interesting (although the core idea has been already wide used in the causal inference/econometrics literature).", "weaknesses": "- In the minimax lower bound of Theorem 1, is the estimator $\\hat{H}^q$ is not allowed to access any information about $p^*$ or $w$, unlike the proposed estimator does. This makes the comparison between the lower bound and the upper bound in Theorem 2 irrelevant.\n\n  Indeed, the proof does not construct the two hypotheses in a way that the estimator needs to know about $p^*$ or $w$. For example, in the first part of the proof, it suffices to determine whether $p(y | x)$ is $g_0$ or $g_1$.\n\n  I believe that in the formulation of $\\mathcal{H}_n^{f,q}$, we can construct two hypothesis with a common $p(y | x)$ but different $p(x)$'s, to make any estimator unable to tell the difference.\n\n- There is a strong assumption that there is no noise in the observations of the label: $y_i = f(x_i)$. This limits applications of the proposed method.\n\n- The estimator in the case of an unknown likelihood ratio does not seem minimax-optimal because of the exponent $\\frac{\\alpha}{\\alpha + 1}$ in Eq. (8).\n\n- There is no experiment about the comparison between the proposed method and the Monte Carlo estimate using $\\hat{f}^q(x_i')$ or $w(x_i) y_i^q$.\n\n- Likewise, there is no experiment about the effect of the truncation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)