Bounds on $L_p$ Errors in Density Ratio Estimation via $f$-Divergence Loss Functions
Authors: Yoshiaki Kitazawa
Venue: ICLR 2025 Poster (2025)
Keywords: density ratio estimation
variational divergence optimization
Kullback–Leibler divergence
$f$-divergence
$L_p$ error
the curse of dimensionality
GAN
Primary area: learning theory
TL;DR: We provide both lower  and upper  bounds on $L_p$ errors in DRE, which hold for any member of a group of Lipschitz continuous estimators regardless of the specific $f$-divergence loss functions used.

Abstract: Density ratio estimation (DRE) is a core technique in machine learning used to capture relationships between two probability distributions. 
$f$-divergence loss functions, which are derived from variational representations of $f$-divergence, have become a standard choice in DRE for achieving cutting-edge performance. 
This study provides novel theoretical insights into DRE by deriving upper and lower bounds on the $L_p$ errors through $f$-divergence loss functions. 
These bounds apply to any estimator belonging to a class of Lipschitz continuous estimators, irrespective of the specific $f$-divergence loss function employed.
The derived bounds are expressed as a product involving the data dimensionality and the expected value of the density ratio raised to the $p$-th power.
Notably, the lower bound includes an exponential term that depends on the Kullback--Leibler (KL) divergence, revealing that the $L_p$ error increases significantly as the KL divergence grows when $p > 1$. 
This increase becomes even more pronounced as the value of $p$ grows. 
The theoretical insights are validated through numerical experiments.

Published as a conference paper at ICLR 2025
BOUNDS ON Ln ERRORS IN DENSITY RATIO ESTIMA- TION VIA f- 1-DIVERGENCE Loss FUNCTIONS
Yoshiaki Kitazawa
NTT DATA Mathematical Systems Inc.
Data Mining Division
IF Shinanomachi Rengakan, 35, Shinanomachi
Shinjuku-ku, Tokyo, 160-0016, Japan
kitazawa kitazawašms co...mmii....................... jp
ABSTRACT
Density ratio estimation (DRE) capture relationships between two probability distributions. f-divergence loss functions, which are derived from variational representations of o f-divergence, have become a standard choice in DRE for achieving cutting-edge performance. This study provides novel theoretical insights into DRE by deriving upper and lower bounds on the Lp еттоrs through f f-divergence loss functions. These bounds apply any estimator belonging irrespective of the specific f-divergence loss function employed. The derived bounds are expressed as a product involving the data dimensionality and the expected value of the density ratio raised to the p-th power. Notably, the lower bound includes an exponential term that depends on the Kullback -Libller (KL) divergence, revealing that the Tpp error increases significantly the KI. divergence grows when p > 1. This increase becomes even more pronounced as the value of p grows. The theoretical insights validated through numerical experiments.
technique in machine learning used
class of Lipschitz continuous estimators,
INTRODUCTION
Density ratio estimation (DRE) key machine learning technique for computing the density ratio r*(x) xx))// /x())) between two probability distributions, based on samples independently drawn from p and g. DRE plays a central role in various machine learning methods, including generative
modeling (Goodfellow et al.) 2014 Nowozin et al. [0166] Uehara al., 2016 mutual information
estimation and representation learning (Belghazi et al., 2018 Hjelm et al. 2018). energy- based modeling (Gutmann & Hyvärinen 2010), and covariate shift and domain adaptation (Shimodaira) 2000
Huang et al. 2006).
Recent advancements in DRE have been fueled by approaches employing neural networks density ratio estimators. These methods use loss functions derived from variational representations of f- divergence (Nguyen al. 2010 Sugiyama et 2012), where the optimal function corresponds to the density ratio via the Legendre transform, leading to state-of-the-ar performance.
Despite their empirical success, recent research has started unravel the theoretical connections between optimizing f-divergence loss functions and the accuracy of DRE. For integral probability metric (IPM) loss functions, the upper and lower bounds of the Lp error in DRE have been established as the minimax bounds of their optimization (Liang 2017 Wiles-Weed & Berthet 2022). More recent studies have concentrated on f-divergence loss functions, deriving upper bounds (Belomestny et 202I) and the minimax upper and lower bounds for optimizing Shannon divergence loss (Belomestny
ct all 2021 Puchkin et al. 2024)..
Although substantial progress has been made, several aspects of the relationship between the choice of f-divergence loss functions and the accuracy of DRE remain unresolved. First, minimax lower bounds do not reflect the true lower bound on the estimation error for the actual density ratio. Second, the relationship between the true magnitudes of the f-divergences and the sample size requirements for DRE using divergence loss functions is not fully understood. Specifically, the role of the true

---

Published as a conference paper at ICLR 2025
Kullback- -eilbac (KL) divergence in determining the sample size needed for DRE with the KL-loss function remains unclear, even though it is known that sample size requirements for KL--ivergencc estimation increase exponentially as the true value of the divergence grows (Poole et al. 2019: Song & Ermon, 2019, McAllester & Stratos 2020). Finally, it remains an open question whether different f-divergence loss functions, such total variation loss and KI.-divergence loss, yield statistically equivalent Lp errors (c.g., root mean square errors).
This study aims to address uncertainties in DRE using f-divergence loss functions by deriving the upper and lower bounds that are independent of the choice of f-divergence. However, the theoretical optimization of f-divergence loss functions presents challenges due to their dependence on sample sets drawn from two distributions. The lack of overlap between these sample sets often leads to unstable optimization points, resulting in losses that do not reach their theoretical optima. In practice, this issue is commonly mitigated by applying early stopping while monitoring validation losses.
We incorporate this practical approach into our theoretical framework by reformulating the loss functions conceptually, thereby bridging the gap between the practical and theoretical behaviors of these functions. Subsequently, we derive upper and lower bounds for the Lp error DRE by optimizing f-divergence loss functions. These bounds are obtained based on the expectation of the distance between nearest neighbors in observations under the assumptions of L L-Lipschitz continuity of the energy function of the distributions and the compactness of the support.
The derived bounds are expressed as a product of terms involving the data dimensionality and the expected value of the density ratio raised to the p-th power. Notably, the lower bound includes exponential term dependent on the KL--dvvrgence,, showing that the Lp error increases significantly as the KL-divergence grows for p > 1, with the rate of increase accelerating for higher values of p. These bounds apply to a class of Lipschitz continuous estimators, irrespective of the specific f-divergence loss functions used. The theoretical findings are validated through numerical experiments.
In summary, the key contributions of this study are as follows: (1) We derive universal upper and lower bounds for the Lp error in DRE through optimizations of variational representations of f-divergences, providing a novel perspective on DRE with f-divergence loss functions. (2) We empirically explore the relationship between KL-divergence, data dimensionality, and estimation accuracy in DRE through optimizations of variational representations of f-divergences. Specifically, we find that the Ly error increases significantly with larger KL-divergence values for p > 1, and this effect is amplified by the magnitude of p.
Related Work. This study establishes upper and lower bounds convergence rates for nonpara- metric density ratio estimation using f-divergence optimization. Relevant prior research includes studies the minimax convergence rates for density estimation in the context of GAN optimization, particularly for Wasserstein GANs (Arjovsky & Bottou/ 2017) and vanilla GANs (Goodfellow et al.) 2014). In Wasserstein GAN optimization, Liang (2017) and Singh & Póczos (2018) derived the minimax convergence rates for the IPM loss, which encompasses total variation among f -diverggencss. Furthermore, SillesWWee & Berthet (2022) extended these findings to the Wasserstein-P p distance for > 1. In the context of vanilla GAN optimization, Belomestny et al. (202T) and Puchkin et all (024) provided minimax upper and lower convergence rates for the Shannon divergence loss, specifically deriving an upper bound for the T.2 error. Beyond GAN- based research, Nguyen et al. (2010) proposed an upper bound for the Hellinger distance in DRE using the KL-divergence loss, thereby establishing minimax upper bound for the L1 error in DRE. Additionally, foundational work by Stone (1980) introduced a minimax convergence rate for nonparametric regression, which is also applicable upper bound for the L2 error in nonparametric density estimation. For detailed comparisons between our derived bounds and existing DRE bounds, see Section i. Appendix.
PRELIMINARIES: NOTATION, SETUP, AND JDIIVERGENCE Loss FUNCTIONS
In this section, define the notation, outline the problem setup, and present the variational repre- sentation of f-divergence along with the associated loss functions that form the foundation of the analysis in the subsequent sections.
2

---

Published as a conference paper at ICLR 2025
2.1 NOTATION, PRELIMINARY CONCEPTS, AND SETUP
Notation: Random variables are represented by uppercase letters, such as X. Lowercase letters denote specific values of these random variables: for example, a represents a value of the random variable X. Boldface letters, X and x, are used to denote sets of random variables and their corresponding values, respectively. lly x||> denotes the maximum norm in Rd. i.e., lly - x||>0 = maxisisa [V; x4 for y = (11, 02.......... ..... Ma) and x (2,, .22). diam((?) denotes the diameter of ft. Specifically, let (1) = inf(r > 0 3a E s.t. S A ((a,r) where (a,, denotes the d-dimensional interval centered at a with each side of length r: A(a, r) {x E IRd| |x - alloo < rr/2). Op (ax) denotes stochastic boundedness with rate aN in μ. i..., X = Op (ax) (as + 00) + for all E > 0, there exist (()) > 0 and (e) 0 such that μ ([X /aN 2 8(e)) < for all N 2 N()).
Preliminary Concepts: Let P and Q represent probability measures on (), where I denotes the a-algebra on Ω. P is called absolutely continuous with respect Q, P(A) 0 whenever QAA) = 0 for any A F This relationship is denoted P < Q. dP refers to the Radon-Nikody derivative of P with respect Q for P and Q with P & Q. f denotes probability measure Ω with < and Q < p.. An example of j is (P + Q)/2. Ep[:] denotes the expectation under the distribution i... Eplo(x)] Ja, (x))d((x), where ((x) measurable function over $2.
dQ
Setup and Assumptions: P and Q represent probability distributions on Q C HR with unknown probability densities p and q. respectively. We assume p(x) > + (xx) > 0 almost everywhere S..
2.2 DRE WITH f-DIVERGENCE VARIATIONAL REPRESENTATION
Here, we introduce the f-divergence variational representation and the corresponding loss functions used for DRE.
Definition 2.1 (f-divergence). The f-divergence D, between two probability measures P and Q is defined using convex function f satisfying f(1) It is expressed as: Dy(Q[IP) Eplf(dQ)/dP(x)))
Various divergences can be obtained as special cases by selecting an appropriate generator function f. For instance, choosing the function fu) u log u yields the Bullback-Leibbe divergence.
We derive the variational representations of f-divergences using the Legendre transform of the convex conjugate of twice differentiable convex function f. f*) supuER (v u - [(()) Nguyen
et al] 2007
-sup { $20
- Ep -Ep
where the supremum is required over all measurable functions Ø 9 + R with Efll < co 0o. The maximum value achieved when d(x) dQ/ dx)).. Pairs of the terms (0) and f" (f in Equation ( for major f f-divergences, along with their corresponding convex functions f. are provided in Table 2 in the Appendix.
and (f(((()))))
By substituting ó with a neural network model Oe and replacing the expectation E with sample means E, the optimal function for Equation (1) is trained through back- poo-propagation using an f-divergence loss function.
(0))) = [o (aan)]-rr[[[cc [r([)(((00)]]]]
Formally, we define the f-divergence loss function within probabilistic theoretical framework as follows:
Definition 2.2 (f-Divergence Loss). Let X PlRj {X] X2
XB3. X lid
P denote R i.i.d.
random variables from P. and Xq1s = (X] x3..... S. variables from Q. Thereafter, for a twice differentiable convex function f. f-divergeecce loss c(
X Q denote i.i.d. random
Sid
In this study, q(x) p(x) is used as notation for 4Q for improved readability.
(x) based on the Nidon-Nikodým density representation dP

---

Published as a conference paper at ICLR 2025
is defined as follows:
R 2 = -1 (x(x)) + R 5 (f (o(x)))),
1 S
(R
(3)
where o denotes measurable function over Q such that Ø + Ryo.
MAIN RESULTS
This study presents two key contributions. First, derive common upper and lower bounds for the Lp error in DRE by employing variational f-divergence optimization. Second, we empirically explore the relationship between KL-divergence, data dimensionality, and estimation accuracy in DRE through variational f-divergence optimization. Specifically, we find that the Lp error increases significantly the KL-divergence rises for p > and this increase becomes more pronounced with larger values of p.
3.1 THEORETICAL RESULTS.
In this study, we outline the assumptions required to derive the upper and lower bounds for DRE. These assumptions are straightforward and primarily pertain to Lipschitz continuity of estimators. Specifically, we assume the L-Lipschitz continuity of the energy function of the distributions, (x) = - log dQ/d (x)...
Assumption 3.1 (Assumption for the Upper Bound). The following assumption is imposed on the probability distributions and Q.
U1. (x) log dQ/dP(x) is L-Lipschitz continuous with L > 0 on Ω.
Assumption 3.2 (Assumptions for the Lower Bound). The following assumptions are imposed on the probability distributions P and Q.
LI. (x) log dQ/dP(x) is L-bi-Lipschitz continuous with L > 1 on Ω.
L2. Ep [dQQ/P))) < oo where p S d.
For the probability distributions P and Q, Assumption LI plays crucial role in deriving the lower bound of the Lp error in DRE. Further details regarding this assumption are provided in Remark 4.6
in Section 4.2
Additionally, Assumptions 3.3 and 3.4 are essential for deriving both the upper and lower bounds of the DRE. A discussion comparing Assumption 3.3 with related assumptions in prior work is provided in Section E.2 in Appendix.
Assumption 3.3 (Assumptions for the Convex Function f). The convex function f is assumed to satisfy the following conditions: (F1) f is three-times differentiable; (F2) f"((x) for all u 0; and (F3) Ep ["(QQ/dP) < cc.
Assumption 3.4 (Assumption for the Support). The support Ω is assumed to satisfy the following conditions: (O1) diam(S?) oc.
Under these conditions, derive the upper and lower bounds for the Lp error in DRE using variational f-divergence optimization.
Theorem 3.5 (Informal. See Theorem 4.5 and 4.8). Assume Ωi is compact set in Rd where > Let P and Q denote the probability measures on Q. and let ø represent a K funntiot that minimizes the f f-divergence loss functions defined Equation (3) using early stopping. Additionally, let N min S).
and satisfies Assumption
3.3
(Upper Bound) Assume Assumption
3.1 Thereafter, Equation 4 holds for S.P S d/2 such that
1/(2.p)
g(x)
diam
dQ
2
(xx)
x
L. F.
K
(4)
p(x)
Nl/d
dP
4

---

Published as a conference paper at ICLR 2025
(Lower Bound) Assume Assumption 3.2
Equations
5 and (6)
hold for 1 1 p I d such that
((x)
dQ
}7} 1/p
Ex3-xx
6(xx)
2
Ep
x
K d1)
p(x)
N1/d
dP
LP(()P))
(5)
(p=i)
KL(P 1Q) 1..diam (2)
N1/d
6
(6)
where 1- (2.P)) denotes the Lpp norm on Q with respect to measure P, and K KI(PIIQ) denotes the Kl.-divergence between P and Q.
These bounds apply all K K-Lippscitz continuous estimators optimized with early stopping using the f-divergence loss functions, as discussed Section 4.3 and supported by Theorem 4.8
Theorem 3.5 indicates that the curse of dimensionality arises when p 1. For p 1, both the curse of dimensionality and the large sample requirements for high KL-divergence data occur simultaneously. In particular, Equation ( shows that the Lp error increases exponentially with growing KL-divergence for > 1, and this growth accelerates as increases. These theoretical insights validated by numerical experiments, which are presented in the following section.
3.2 EXPERIMENTAL RESULTS.
We empirically verified the relationship between KL-divergence and data dimensionality, and their effects on the estimation accuracy of DRE through variational f f-divergence optimization. The results, which corroborate the implications of Theorem 3.5 are presented in detail in Section D of the Appendix.
Lp Errors vs. the KL-Divergence in Data We conducted experiments to investigate the relation- ship between L1, L2, and Ly errors in DRE and the KL-divergence of the data. In these experiments, generated 100 sets of 5-dimensional datasets with KL-divergence values of 1, 2, 4, 6, 8, 10, 12, and 14. For each dataset, DRE was performed using the a--iiergence and KL-divergence loss functions, and the resulting T,, T22, and Lg errors recorded. The results are presented in Figure Details the experimental settings and neural network training procedures are provided in Section
As shown in Figure 1 the estimation errors for p > 1 increased significantly, with this growth accelerating as p becomes larger. In contrast, when p the increase in estimation error was relatively mild. Consistent with Theorem 3.5) these results demonstrate the significant impact of di-divereence on Lp errors for p in DRE with f-divergence loss functions.
Lp Errors vs. the Dimensions of Data We conducted experiments to investigate the relationship between L1. L2, and L3 errors DRE and the dimensionality of the data. In the experiments, we generated 100 datasets with dimensions of 50, 100, and 200, each having KL-divergence value of 3. For each dataset, DRE was performed using a-divergence and KL-divergence loss functions, and the resulting L1, L2. and Lg emrrr experimental settings and neural network training procedures are provided in Section D
observed. The results are presented in Figure 2 Details of the
As depicted in Figure 2 the estimation errors L1, Iz2, and Lzg increased the dimensionality of the data increased for both the a-divergence and KL-divergence loss functions. These results indicate that the curse of dimensionality affects all L, errors equally, suggested by Theorem 3.5
4 OVERVIEW OF UPPER AND LOWER BOUND DERIVATIONS
In this section, we outline the derivation of the upper and lower bounds. We begin by introducing conceptual reformulation of the f-divergence loss function, which serves as the foundation of our theoretical framework. Next, derive the upper and lower bounds for DRE in terms of the Lp error, based on this reformulation. Finally, we extend these results to the practical optimization scenario using the f-divergence loss function, incorporating early stopping by monitoring validation losses.
5

---

Published as a conference paper at ICLR 2025
Ly Error
Lg Error
Lg Error
ordivergence Ki KL-diveryonce
DRE Errors
DRE Errors
DRE Errors
130
0.41
10
50
KL--divergence
KL-divergence
KL-divergence
The experimental results of Lp errors versus the magnitude of KL-divergence in the data presented in Section 3.2 The z-axis represents the magnitude of KL-divergence in synthetic datasets of fixed dimensionality. The y-axes of the left, center, and right graphs correspond to the L1, L2, and Ly errors in DRE, respectively. The plots depict the median values of the y-axis, while the error bars indicate the interquartile range (25th to 75th percentiles). The blue line represents errors computed using the a-divergence loss function, whereas the orange line corresponds errors computed using the Ki-divereence loss function.
Figure 1:
a-divergence L Error
a-divergence- Lg Error
a-divergence Ly Error
-42
log(DRE Errors)
-0.
Dim-100
DRRE Erront)
Dog Erros)
Dim-200
-10
-22
28
log( Number of Samples)
logmNum of Samples)
(Number Samples)
KL-divergence Error
KL KL-divergence Ly Error
KL KL-divergence Ly Error
log/DRE Erross)
DRE Errors
log DRR Errors
1.00
-022
8.27
-04
2.0
5.
A1
80
2.0
6.5
6.5
65
(Nuumer of Samples)
log(Number of Samples)
[og(Number Samples)
Figure 2: The experimental results on Lp errors versus the dimensionality of the data are presented in Section 3.2 The top displays results using the a-divergence loss function, whereas the bottom row presents results using the KL-divergence loss function. The æ-axis represents the logarithm of the number of samples utilized in the optimizations DRE. The y-axes of the left, center, and right graphs correspond to the L1, L2, and L3 errors in DRE, respectively. The plots show the median y-axis values, while the error bars represent the interquartile range (25th 75th percentiles). The blue, orange, and green lines correspond to data dimensions of 50, 100, and 200, respectively.
This extension represents the core theoretical contribution of this study, Detailed statements and proofs for the theorems discussed in this section are provided Section the Appendix.
4.1 CONCEPTUAL REFORMULATION OF THE f-DIVERGENCE LOSS FUNCTIONS
The optimization of f-divergence loss functions, denoted as C.(..)) (o) in Equation 3 poses both practical and theoretical challenges due to its propensity to overfit the training data.
To better understand this issue, consider deterministic setting described in Definition 2.2 where (xt, x xff) = (1, 2..,.... R) and (x²= x²...., ..) R + R 2, ....., R S). Notably, {xt R n (x) = 0. In this setup, we observe that L/ (R.))) (Φ) - 00 as l (J for all < < R and < j < S. practice, this issue is mitigated by implementing early stopping, where validation losses monitored during optimization. The
and -s' ('((())

---

Published as a conference paper at ICLR 2025
present theoretical framework incorporates this practical strategy, allowing for deeper analysis of both the optimization process and its implications for downstream tasks such as DRE.
To bridge the gap between the practical and thcoretical behaviors of f-divergence loss functions within our framework, we propose a conceptual reformulation the loss function.
Definition 4.1 (u-Representation f-Divergence Loss). Let μ be probability measure with < μ and Q < j. Let min RR $) and let X = {X] ........ X denote N i..dd random variables
from μ. For twice differentiable convex function f. let
dQ du
dP
(u: ff (u)
(x) fz (f'
(x). du
where 1 denotes the Legendre transform of f: (v) suPneR ( (u)). The y-representation of the f-divergence loss c( (.) in Equation 3 at the points X is defined as
(0)
N
where ø is measurable function over Ω such that Φ Ω - R30-
This representation introduces error of 1/v/N between the practical f-divergence loss function C(R.)) (ő) and the u-representation f-divergence loss 2 (6)) However, this error is negligible
when d 2 3, which will be discussed in Section 4.3
The optimization properties of this conceptual loss function are encapsulated in Proposition 4.2
Proposition 4.2. Assume that f satisfies Assumption 3.3 Let Φ. arg min E(N) Then,
(X*)) d3 (X)), for 1,2...., N.
This reformulation ensures that the conceptual loss function remains bounded. Furthermore, all optimal points of the conceptual loss function are aligned with the ideal density ratios.
4.2 DERIVATION OF UPPER AND LOWER BOUNDS FOR OPTIMAL FUNCTIONS OF THE U-REPRESENTATION f f-DIVEGGENCE Loss FUNCTIONS
In this section, we derive the upper and lower bounds for the T.p error in DRE for the optimal function of () (.) defined in the previous section. These bounds are based on the expected distance between the nearest neighbors each X; for < N.
(x) denotes the nearest neighbor x in X = [X] p X Specifically, define X (1) H[N] (x) as X in XM(NM) such that |X| - x|100 > X - x|| for all < i, and |X]
Hereafter, x N[N]
X||00 X x| for all i. As in the previous section, let Φb arg min mina:n-nnnaa... R5o C (
As presented in Proposition 4.2 the optimal points of the jrrepressenattion f-iieeggence loss functions Z(8) (x) coincide with the ideal density ratios. This fact provides the following equation, serving as the key bridge between the density ratio and its estimation.
dQ dp
dQ dp = x
d (x.)
(x))
(1) H
(x))
(9)
Based on this equation, we can obtain
P Using the triangle inequality in the Lp norm for the density ratios and its nearest neighbor, obtain
dQ
Φ. (x (1) (x)) (x())
=
dp
x
M[N]
(x)) - -b (x))
(10)
F.p
dP (x)
dQ
dQ (1)
1/p
Ep
dQ
(1)
(x))
- -xx(x))
1P 1/p
dP
dP
7

---

Published as a conference paper at ICLR 2025
m 1/P
dQ
Ep
dp (x) -xx(x)
Ep
dQ
(x)
dQ
(x
(x)((()))
1/8
+
Ep
dQ dP
(x (x)(())) - &z (x2) (//0 /
1/2
(11)
dP
dP
Assuming the L-bi-Lipschitzz continuity of the energy function of the density ratio, (x) - -logg(x)/p(f we yield
1
dQ
(x)
x (x) -
x x +0p (NT//e2)
x
LP
dp
dQ
dQ
(x (x)(
dP (x)
dP
L"
dQ ap
(x)
( (x) - x
+ Op N1/(2d)
(12)
Additionally, from the K -ipsschit continuity of (+) and Equation (
dP (x) (x)
dQ
P = Φb [ [[N] (x)] &. (x) S K"
(1) || A(N/ (x)
(x) (x)-x
(13)
Equations
(12) and (13 provide the upper and lower bounds of the difference in density ratios between x and its nearest neighbor x M[N] (x) using their distance.
To evaluate the expectation of the distance between and its nearest neighbor X (()
p[N] (x), we present
the following theorems: Theorem 4.3 provides upper bound for the expectation the right-hand
side of Equation (12;; and Theorem 4.4 establishes a lower bound for the expectation on the left-hand side.
Theorem 4.3. Under the assumption that QL is compact, for 1 < S d/2,
lim N1/d
Ep
dQ
(x)
}
||XPNn(x) - x 1
1/p
N
dP
dQ d.P
2xp
1/(2.p)
S diam(S))-
Ep
(x)
(14)
Theorem 4.4. Let P and Q be probability measures compact set Q in Rdd with d 2 1. Assume that P & and Q < X, where denotes the Lebesgue measure on IRd Let p be a positive constant such that p 1. Assume El(dQ/dPY) sc. Then,
lim N//d { EXPIN)
dQ
(x
(x))
||x - 1
1/4
Ep
dP
N-100
1/P
dQ
Ep
(15)
where ExpIn] []] denotes the expectation over each variable in X P[N] =X X
X
pp)
Notably, using Jensen's 's inequality on the right-hand side Equation KL-divergence between P and Q appears in the lower bound such that
15 in Theorem 4.4 the
dQ dP (x)
17]
1
1/v
dQ dP
1/P
c-
Ep
=
Eq
(x)
1/p
-1_
Ei
(11-1)-00 de (x)
1/9
2 -1
Fgg
(0-1
22 (x0)
p -=1K)(Q[P))-1 (16)
8

---

Published as a conference paper at ICLR 2025
We derive the upper and lower bounds for the Lp error in DRE for the optimally estimated functions 2 Z())(. (.), as stated in Theorem 4.5
Theorem 4.5, Assume Ω is a compact set in R with d 2 3, and that f satisfies Assumption
3.3 Let P and Q be probability measures on Q, assuming that P & X and Q & X. where
denotes the Lebesgue measure on R.. Let Tet be the energy function of dQ dQ/dPPt /d defined as
(x) = - log dQ/ (x))).. Let F(N) K-Lip denote the set of all K K-Lipschitz continuous functions on Ω2
that minimize y (.). Specifically, define
F(N) 0 52 Rs0
(d.) min Z (0)
(17)
and
FK.1sp { Rso
[k(y) o(x) s K. ||y x for all y
(18)
Subsequently, let FolN) Kii
F(N) FK-Lip
(Upper Bound) Assume that T satisfies Assumption 3.1
Thereafter, for 1 s S d/2, Equation
190 holds for any & E Lsp such that
F(N)
dQ
12)
1/P
lim N1/d N N
Ep
(x)
-(x)
dP
1/(2-p)
dQ dp
< L diam (S2)
Ep
(x)
+ K diamm()).
(19)
(Lower Bound) Assume that T (x) satisfies Assumption 3.2 [(N) such that any @ K-Lip
Then, Equations
20 and
21 hold for
dQ d.
1 1/2
lim N1/d ExPIN) N
Er
(x)
o(x)
dQ dp (x)
1/8 }7]
Ep
KK diamm(1)
(20)
L
1 KLQQIPP)
2 L
diam(S2)
(21)
Remark 4.6. In the case L = Equation 12 with p= implies that [dQ//d(x)-
dQ/dP(x) ||y xI|gg for x,y Q. A typical case when 22 dQ/dP(mi, ;., vay' with d' d. Thus, this typically occurs when dQ/dP(x /x)((x) is replication of its lower-dimensional distribution. In such cases, the upper and lower bounds for the Lp error in DRE are determined by the nower-dimensiones distribution.
4.3 DERIVATION OF UPPER AND LOWER BOUNDS FOR OPTIMAL FUNCTIONS OF THE [-DIVERGENCE LOss FUNCTIONS
To establish upper and lower bounds for practical DRE using f-divergence loss function optimization, we first statistically evaluate the discrepancy between the outputs of the practically optimized functions
c) (ft.5) (.), which employ early stopping based on validation losses, and the theoretically optimized functions (.)) Next, we demonstrate that this discrepancy becomes negligible when 2 3. Finally, the upper and lower bounds for DRE are expressed in terms of the Lp сπтоr for f-divergence loss function optimization with early stopping. This result constitutes the final theoretical contribution of this study.
First, according to the central limit theorem, an error of order 1/vN in probability arises when measuring validation losses.
C (n.5) (0)
[c [c) O, VN
E,p
(22)

---

Published as a conference paper at ICLR 2025
Equation 22 implics that there an error margin of Op when monitoring validation losses
for early stopping in the optimization of 2j clT..s
Subsequently,
the following theorem demonstrate that the optimization of Equation (22 employing early stopping based on validation losses, is governed by the optimization of the u-representation f-divergence loss functions (.).
Theorem 4.7. Assume the same assumptions in Proposition
4.2
Let Φ~
arg mig y E(N)
(Φ). Therefore. for any measurable function Φ : - R Ryo.
)
x(x)) o. (xx)) =0p
(VV)
((..5)(0)) (Φ)
C (R... (0) =0p VN
min E
(23)
(6:2- 2
where {X], X2 p..... X } is defined in Definition 4.1
In Equation the first term on the right-hand side represents the empirical risk of c (R. validation data, while the second term denotes the minimum value of its true error. This equation illustrates that when _ c(R.S)(()) (() is within the actual early stopping margin, specifically Op than Op )v²)
(Ø) using
the function & deviates from the optimal function of L (x) by
Based on Equation 233 we define the optimal function of c/ ((R..)) (Φ) for use with early stopping while monitoring valıdation losses as follows:
(R.5) (d) using early stopping
@val is optimal in the optimization of LJ
- Φx + +Op
where Φ = arg min d:
Ep
[2 [
(24)
The difference Op appearing in Equation (24 is negligible for DRE when d 2 3. Indeed,
using the triangle inequality in the Lp norm for o arg min 7, (d) and Equation 20) we observe
dQ (x) (ra(())
1/8 2
dQ dP (x) - (x()
1/P
IP 1/p
Ep
Ep
Ex (xal(x)) -x((x)
dP
xi7a
=0 +p)
&xtra
(25)
Therefore, finally obtain the following Theorem 4.8
Theorem 4.8. Assume the same assumptions and notations as in Theorem 4.5
Additionally, define
((N) K-p - - 3Φ. E Fi K-Lop such that 6 = 6. + +O
F(N)
}
1
(26)
vN
(N) That is, K-Lip denotes the set of all functions that differ by at most Op (+x) from some functions
that minimize (.). Therefore, the same results as in Theorem 4.5 hold for all 6 E FF(N)
K-Lip
5 CONCLUSIONS
We have established upper and lower bounds on the Lp errors in DRE through the optimization of f-divergence loss functions. These bounds are applicable any member of group of Lipschitz continuous estimators, irrespective of the specific f-divergence loss function employed. These bounds provide new insights into how data dimensionality and the KI. divergence between distributions
10

---

Published as a conference paper at ICLR 2025
influence the accuracy of DRE. Furthermore, numerical experiments validate these theoretical findings, demonstrating that the relationship between Lp errors, KL divergence, and data dimensionality aligns with the theoretical implications derived from the bounds. However, challenges remain, especially in high-dimensional settings, due to the curse of dimensionality and large sample requirements. Future studies could refine the theoretical framework explore loss functions that enhance DRE performance in complex, high-dimensional tasks.
REFERENCES
Martin Arjovsky and Léon Bottou. Towards principled methods for training generative adversarial networks. arXiv preprint (et1:1770.04555 2017.
Francis Bach. Self-concordant analysis for logistic regression. 2010.
Mohamed Ishmael Belghazi, Aristide Baratin, Sai Rajeshwar, Sherjil Ozair, Yoshua Bengio, Aaron Courville, and Devon Hjelm. Mutual information neural estimation. In International conference on machine learning, pp. 531-540. PMLR, 2018
Denis Belomestny, Eric Moulines, Alexey Naumov, Nikita Puchkin, and Sergey Samsonov. Rates of convergence for density estimation with gans, arXiv preprint arXiv:2102.00199, 2021.
Gérard Biau and Luc Devroye. Lectures on the nearest neighbor method, volume 246. Springer, 2015.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. Advances in neural information processing systems, 27, 2014.
Michael Gutmann and Aapo Hyvärinen. Noise-contrastive estimation: A new estimation principle for unnormalized statistical models. Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp. 297-304. JMLR Workshop and Conference Proceedings, 2010.
R Devon Hjelm, Alex Fedorov, Samuel Lavoie-Marchildon, Karan Grewal, Phil Bachman, Adam Trischler, and Yoshua Bengio. Learning deep representations by mutual information estimation and maximization. arXiv preprint
86680000067, 2018.
Jiayuan Huang, Arthur Gretton, Karsten Borgwardt, Bernhard Schölkopf, and Alex Smola. Correcting sample selection bias by unlabeled data. Advances in neural information processing systems, 19, 2006.
Takafumi Kanamori, Taiji Suzuki, and Masashi Sugiyama. Statistical analysis of kernel-based least-squares density-ratio estimation. Machine Learning, 86:335-367, 2012.
Masahiro Kato and Takeshi Teshima. Non-negative bregman divergence minimization for deep direct density ratio estimation. In International Conference Machine Learning, pp. 5320-5333. PMLR, 2021.
Masanari Kimura and Howard Bondell. Density ratio estimation via sampling along generalized geodesics on statistical manifolds. arXiv preprint arXiv:2406. 18806, 2024.
Diederik P Kingma. Adam: A method for stochastic optimization. arXiv preprint arXiv: 1412.6980, 2014.
Yoshiaki Kitazawa. Alpha-divergence loss function for neural density ratio estimation. arXiv preprint arXiv:2402.02044 02041, 2024.
Samory Kpotufe Lipschitz density-ratios, structured data, and data-driven tuning. In Artificial Intelligence and Statistics, pp. 1320-1328. PMLR, 2017.
Tengyuan Liang. How well can generative adversarial networks learn densities: nonparametric view. arXiv preprint arXiv: /7 72.. 08244, 2017.
11

---

Published as a conference paper at ICLR 2025
Zhexiao Lin, Peng Ding, and Fang Han. Estimation based nearest neighbor matching: from density ratio to average treatment effect. Econometrica, 91(6):2187-22) 2217, 2023.
David McAllester and Karl Stratos. Formal limitations on the measurement of mutual information. In International Conference on Artificial Intelligence and Statistics, pp. 875-884, PMLR, 2020.
XuanLong Nguyen, Martin Wainwright, and Michael Jordan. Estimating divergence functionals and the likelihood ratio by penalized convex risk minimization. Advances in neural information processing systems, 20, 2007.
XuanLong Nguyen, Martin J Wainwright, and Michael Jordan, Estimating divergence functionals and the likelihood ratio by convex risk minimization. IEEE Transactions Information Theory, 56(11):5847-586) 2010.
Jonathan Niles-Weed and Quentin Berthet. Minimax estimation of smooth densities in wasserstein distance. The Annals of Statistics, 50(3):1519-1540 2022.
Sebastian Nowozin, Botond Cseke, and Ryota Tomioka. f-gan: Training generative neural samplers using variational divergence minimization. Advances in neural information processing systems, 29, 2016.
George Papamakarios, Eric Nalisnick, Danilo Jimenez Rezende, Shakir Mohamed, and Balaji Lakshminarayanan. Normalizing flows for probabilistic modeling and inference. Journal of Machine Learning Research, 22(57):1-64, 2021.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
Ben Poole, Sherjil Ozair, Aaron Van Den Oord, Alex Alemi, and George Tucker. On variational bounds of mutual information. In International Conference on Machine Learning, pp. 5171-5180. PMLR, 2019.
Nikita Puchkin, Sergey Samsonov, Denis Belomestny, Eric Moulines, and Alexey Naumov. Rates of convergence for density estimation with generative adversarial networks. Journal of Machine Learning Research, 25(29): 1-47, 2024.
Igal Sason and Sergio Verdú. f-divergence inequalities. IEEE Transactions on Information Theory, 62(11):5973-600) 2016.
Hidctoshi Shimodaira. Improving predictive inference under covariate shift by weighting the log- likelihood function. Journal of statistical planning and inference, 90(2):227-244, 2000.
Shashank Singh and Barnabás Póezos. Minimax distribution estimation in wasserstein distance. arXiv preprint arXiv: arXiv: 1802.0885, 2018
Jiaming Song and Stefano Ermon. Understanding the limitations of variational mutual information estimators. arXiv preprint arXiv:1910.06222, 2019.
Charles Stone. Optimal rates of convergence for nonparametric estimators. The annals of Statistics, pp. 1348-1360, 1980.
Masashi Sugiyama, Taiji Suzuki, and Takafumi Kanamori. Density-ratio matching under the bregman divergence: unified framework of density-ratio estimation. Annals of the Institute Statistical Mathematics, 64: 64:1009-1 2012.
Masatoshi Uchara, Issci Sato, Masahiro Suzuki, Kotaro Nakayama, and Yutaka Matsuo. Generative adversarial nets from density ratio estimation perspective. arXiv preprint arXiv: /00i::160.00 1610.029200 2016.
12

---

Published as a conference paper at ICLR 2025
A ORGANIZATION OF THE SUPPLEMENTARY DOCUMENT
This supplementary document is organized as follows:
Section provides a list notations used in this study. Section C presents the proofs referenced in Sections and 4 Section D provides details of the experiments conducted. Section E explores further discussions related to this study.
Additionally, the code used for the numerical experiment is included supplementary material.
B NOTATIONS
We outline all the notations used in the Appendix of this study in Table
C
PROOFS
In this section, we present the theorems and proofs referenced in this study. We begin by summarizing the definitions and assumptions introduced in previous sections, followed by the detailed theorems and proofs utilized throughout this study.
C.I DEFINITIONS AND ASSUMPTIONS IN SECTIONS
AND
C.1.1 DEFINITIONS
Definition C.1 (f-Divergence (Definition (.1sraatedd))) The f-divergence D, between two prob- ability measures P and Q, induced by convex function f satisfying f(1) 0, is defined as (2( (P) =
Definition C.2 (f-Divergence Loss (Definition 2.2 restated)). Let X P|R] = (X X X
X ~ P denote R i..d. random variables from P. and let XQis (X) Xg..... x Q
denote S ii.dd random variables from Q. Then, for twice differentiable convex function f. f-divergence loss C c(..3) (-) is defined follows:
s Σ 1=1
R - + (F(())))
c ((. (0)
= S
(27)
1=1
where á is measurable function over Ω such that ø Ω Rso.
Definition C.3 (j-Representaatin f-Divergence Loss (Definition restated)). Let f twice differentiable convex function f. Then, p-representation function of for u > 0 at point f which is written for (u) in an abbreviated form, is defined
(w; = ff dQ
dP
(x) + f (f'
(w))
(x).
(28)
du
du
where f denotes the Legendre transform of f: (*) = suP WER (v-u-f(ul) Let N = R,, S}. and let [NN [ ...... X.N denote N i..dd random variables from μ. Then, p-representation of the f-divergence loss C(...)))
(.) in Equation 27 at the points X AINN is defined as
Σirlu x
(29)
N
where e is measurable function over such that Φ : + Eyo.
C.1.2 ASSUMPTIONS
Assumption C.4 (Assumption for the Upper Bound (Assumption 3.1 restated)). The following assumption is imposed on the probability distributions P and Q.
U1. (x) log dQ/ (d(()) (y) (x)) & L.
(x) is L-Lipschitz continuous with L on Ω. ie., 3L > s.t. for any y, x E Ω
13

---

Published as a conference paper at ICLR 2025
Table 1: Notations and definitions used in the proofs
Notations
Definitions, Meanings
(Capital, small, and bold let- ters)
Random variables are denoted by capital letters, such A. Corre- sponding values of the random variables are represented by small letters. Bold letters A and a denote sets of random variables and their corresponding values, respectively.
R, Rdd
The of all real numbers and the d-dimensional vector space over the real numbers, respectively.
R>0
The set of all positive real numbers: R50 = fxr E R | x > 0}. A subset of IR4: Q C Rdd
Ω
f(x) = O(g())), as x + a
Asymptotic boundedness with rate g(x) as x - a: f(x)
((g(z)) + lim lim fx))//(x) S. C. where C > 0.
f()) = olg(z)), as x +a
Asymptotic domination with rate g(z) as I 7 a: f(x)
o(g(z)) < limy- f(x)//(x) =
X = Op(aN), as N + 00
Stochastic boundedness with rate ON in μ:: X Op(aN) +
for all & > 0, there exist d(s) > 0 and N(e) > such that
( /aN 2 =(()) < E for all N 2 N(s).
X op(ay), as N 00
Convergence in probability with rate aN in μt: X (ax))) + for all 0, for all 5 O, there exists ((E,)) > 0 such that
u([X / an 2 8) < E for all N 2 (()).
P&Q
P is absolutely continuous with respect Q.
P.Q
A pair of probability measures with P < Q and Q < P. A probability measure with P < μ and Q < p.
p dP
The
derivative of P with respect to Q.
IQ
XP:M
R i.d.d random variables from P: XpIM (Xp, X
X().
where X P ~ P. S ii.dd random variables from Q: Xqis (X2 x X
XQ19]
where X lid Q. N min(R,
N
XuIM
N i.idd. random variables from μ:: XptM] = (x),, jo
x2 _ X.
sid ~ μ.
where X
x (x)
The nearest neighbor variable of x in X kIN:: (1)
[LN] (x) is the X
such that | f-divergence: (Q1 = F)p
x < XX - x|| for all j + i.
Dy(Q11P)
See Definition
C.1
((R(S)()
f-divergence loss function. See Definition y-representation of the f-divergence (w; - (u) de dp
C.2
Tf(u;))
loss function at (x) f" (f)
dp (x).
j--eppresentatinn of the f-divergence loss function C (....)()).
(.). See
Definition 4.1
()(
The expectation of the j-representation of the f-divergence loss on μ. See Lemma C.IT
H::le
The Euclidean norm.
The maximum norm in Rd: |ly x||.c = max lys z//. The d-dimensional interval centered at with each side of length
A(a,r)
r: A(a, = (x E Rd] - all~> < <r/2].
diam(B)
The diameter of Ω: diam(!)) = inf(r > Ea E Ω s.t. Ω S A(a,r))
14

---

Published as a conference paper at ICLR 2025
Assumption C.5 (Assumptions for the Lower Bound (Assumption 3.2 restated)). The following
assumptions are imposed on the probability distributions and Q.
L1. (x) = log dQ/ /PP(x (x) is L-bi-Lipschitz continuous on Ω. ie., 7L > s.t. (1/L) v xI1xc for any y, x E f.
(y) - - _ L
L2. Ep [(QQ/dP)] < do where p S d.
Assumption C.6 (Assumptions for the Convex Function / (Assmption 3.3 restated)), The following assumptions are assumed for the convex function f.
F1. f is three-time differentiable.
F2. (m) > 0 for all u > O.
F3. Ep [f
oc.
Assumption C.7 (Assumption for the Support (Assmption 3.4 restated)). The following assumption assumed for Q.
O1. diam( < 00.
C.2 THEBOREM AND PROOFS IN SECTIONS 2 AND 4
Lemma C.8. Let be twice differentiable function. Consider Ty x) defined as in Equation 28) Then, the first derivative of y x) with respect to u is given by:
d =
{u ={ dp (x)) (m(
dQ
dP
(u:
dp (x).
(30)
du
Additionally, (u; x) is thrice differentiable, its second derivative with respect to u is given by:
d² du
d2 JP (u;xx = { - (x)) (n"(u) + {"'(u)
dP du (x).
(31)
Proof of Lemma C.8 First, note that
dQ
dP
Ty(u;x) -- ('))
xx) + (f))
(x)
dy
du
dQ
=-(((u)
xx) (f(
- f(u)}
dp (x).
(32)
dp
Differentiating Equation as follows:
32 with respect to obtain the first and second derivatives of 7 (u;
d du
[,((;x) = -f" dQ
dP
(x)
+ u
(u)
(x)
du
du
= { u
dQ
dP
dp (x) (f"()
dp (x).
(33)
and
d
dQ
dP
(1) dP
du² T((xx) -w)
(x) + f"(u)
(x) u.
(x)
du
dy
du
= [m( -- (1-x((x)) ff'
dP
(x).
(34)
du
This completes the proof.
15

---

Published as a conference paper at ICLR 2025
Theorem C.9. Assume that satisfies Assumption C.6
Then, xy)x; defined in Equation 28
minimized and only if u² (x) dg (x). Additionally, for u >> O, the the following holds:
dQ
74 (u;x) - 24 dP
(x):x
2 dP (x))
1 fr dQ
dP
dQ
dQ dP (x)
12)
(x)
(x)
(35)
du
dP
where f(a) aa)) (as + 0) denotes asymptotic domination such that lim0- [(w] + 0.
Proof of Theorem C.9 Let sign(z) denote the sign the value x: specifically, sign(x) = x > 0,
sign(x) 1 x < and (1g)(x) 0 if
From Equation 30 in Lemma
C.8. we have
sign
d du
(u;
= sign
u dP
dQ
(x)
dP (u)
du (x)
dQ
(x) 1)
dP
sign
u
sign
(f"(u)) ) sign
dp (x)
dP
dQ
sign
(x)
(36)
dP
Thus, (u; x) is minimized only when u² Next, from Equation (30).
dQ
(x).
dP
dQ
1
(x):x} = -,
(37)
du
dP
and from Equation 31
d²
dQ dp
(10
dQ dp
dP
(x)::x
f"
(x))
(x).
(38)
duz
dy
Thus, using the second-order Taylor expansion of T around
ap (x), we have
d2
(20
dQ dP (x):x
i, (u:x) - -T,
1 l"
dQ
dP
dQ
2
aQ dP (x)
2
dP (x)
du
(x)
11
dP
(x)
+
(39)
This completes the proof.
Proposition C.10 (Proposition 4.2 restated). Assume that f satisfies Assumption C.6 Let E (Ø) denote the p-representation f f-divergence loss as defined Definition C.3 Then, the minimum value of c ((N) (Ø) over all measurable functions ó Ω + Rzo is achieved if and only if & satisfies
dQ for 112,11,..... 1.,
((
dP (x)),
(40)
proof of Proposition C.10 From Theorem C.9
observe that, for i = 1, 1, N,
dQ dP
min f (w; x:) #>0
= =T,
):
(41)
where the minimum value is achieved only
dQ (
7P
16

---

Published as a conference paper at ICLR 2025
Thus,
N
min dd B
Z(N)
(6)
=
min
1
Σ
N
==1
1 N
min (X,)>0
i= N2 1=1
1 N
min u,20,
(i; x
i= 1N N
x
(42)
N
dp
Suppose that o(x) is function on l that satisfies Equation 44
From Equation 42
we have
2 ((
min
((N)
(Φ)
d:12 R.00
((x))) x
1
dQ
N
dP
N
dQ dP
(X
X
N
dP
0.
(43)
Here, we show that the minimum value of [(M) (Ø) over all measurable functions ø : Ω - Ryo is
achieved if Φ: Ω + Rzo satisfies Equation (40
Next, we show that the minimum value of C (Ø) over all measurable functions Φ -+ R is
achieved only if Φ : Ω - R>o satisfies Equation (40)
We have, for any function Φ Ω + (0, 00),
((N) (Ø) min
2 (Ø)
d: 2200
1
di
((x)) ):
X
min
N
1.2..... N
N
Σ
6 ((xx):
xxxx)xx,)
min
, (u; x
(44)
N
u>0
Suppose that o(x))
*
dQ
ap
(X.)) Then, from Equation 41 we have
T (o(X))
min (u;
(45)
u>0
From Equations
44 and
45p we observe that
(N) (0)
min
d:
1
i
((x;);:: x²,
min 7 (w; X,,) u>0
1
[ūr
(xxx):xx
x -
min Ty (u; min
N
(46)
17

---

Published as a conference paper at ICLR 2025
Thus, that the minimum value of ((N) (Φ) over all measurable functions & : Ω - R2 is
achieved only if Φ Ω2 -> Ig satisfies Equation (40) This completes the proof.
Lemma C.11. Assume that f satisfies Assumption C.6
Let ((N) (Ø) denote the prreppreennaation
f-divergence loss as defined in Definition C.3
Define
[1) (0)
Eu
N
dQ - f (o(xi))
(x.)
E
N
du
N
dP du [xx1
+
Ey
(f'f((((x))
(47)
N
Then,
Ep
min 6
Z(N)
(6)
min C)(0) = min
Ep c ((..5) (6)
(48)
4:12 -B
where the infinum is taken over all measurable funcioonn o : 12 + Rxo such that Er(f(((X))) <0.
Additionally, the equality in Equation (48) hold when Φ(x)
dQ
uP (x).
proof of Lemma C.I1
Let, (x) = min (x) From Theorem C.9
we see 1z(x) =
((dQ/dP(xx)xx Then, we have
dQ dP (x):x
7x(x) = 7,
dQ
dQ
dQ
dQ
(dp (x) -1(0(1))
dQ
dP dp
8'
(x)
(x)
(x)
(x) -
(x)
dP
dp
dP
dP
dQ
dP
f
(x)
(x).
(49)
dp
du
Now, we have
min
Z(N) (0) =
min
Σ ((x
4:f
N
i=1
N
Σ [((X)))
min
((,)) 1,.,...N
N
1=1
min I2,....N
Σ X(
N
1=1
1
(x,)
(50)
N
Additionally, we have
dQ
Ep
(0)
E,
-
f
(xi)
N
du
N
Σ
(f'
(x))
N
du
T=1
18

---

Published as a conference paper at ICLR 2025
N
dQ du
f (0(x))
(xx)
N
/1
f=1
1 N
dP
+
ΣEE t=1
Eu
f (f (o(xi))) du
(xi)
1
Eglf [6)] =
1
(f
N
Ee
[f Ep 1 (f)
(51)
and
E
C
(0)
E
1
()(x))
R
i=1
+
1
Σ
f (f'
S
Σ
Fq |f' (o(x:))
S
E=1
+
Σ
Ep
R
Σ Eq If (0) + 1 (E
Liq 1f (0) + Ep 1f (f' (o))).
(52)
Now, note that, from Equation
Nguyen et al.
2007 ) we see
min 4:02 000--Ra0 30
Eq 18' Ep (0))
(53)
where (Q)()PP) denotes f-divergence defined in Definition C.I and the equality in Equation holds for o(x) dQ/ddl (x)).
53
From Equations (1)
52) and
we have
min 6
En
((N) (0) =
min E
[
(C( = (Q)(1)))),
(54)
o:f--R50
and the equality in Equation
54h holds for ((x) dQ aQ/dP(x).
Substituting Equation
49 into Equation
50 we have
N (0)
1
Σ
(
min 2
f
N
1=1
1
Σ
ff
dQ
(x,]
dP
(x.)
(55)
N
dp
dp
i=1
Thus,
min
Z(N) f
(0)
Ey
Σ -f
N
dQ
(xx))
dP
(xi)
pift-
N
dP
Σ Ey
N
f
(00 (xx))
dQ
dP
(x4)
N
dp
19

---

Published as a conference paper at ICLR 2025
N Σ P((P)PP)
N
= (Q))))
(56)
From Equations 54 and (56), we have
min 2
((N) (6)
min Ly(Ø)
min
Ep (((()(((0)
(57)
and the equality in each Equation This completes the proof.
57 holds for o(x) ddQ/d((x).
The following theorem presents the convergence rate of the expected value of the distance between two neighboring samples. Similar theorems have been discussed in studies on the order statistics of multidimensional continuous random variables (e.g.. Biau & Devroye (0055), p. 17, Theorem 2.1).
Theorem C.12 (Theorem 4.3 restated). Assume that Q is a compact set, as stated in Assumption C.7
Let X (1)
u[N] (x) denote the nearest neighbor of x in NIN Specifically, ler (1) u[N] ([N[(x) (x) be X in X p[M]
such that
[ x|100 < |X x (Vj<(), and [X - |X - x|100 (V > i). (58)
Additionally, let dStm denote the diameter o2 where A(a. r) denotes the d-dimensional interval centered with each side of length A(a,r) {x E Rd ||x alloo < r/22).
Qt i.e. diam(B) = inf (B C A(a, r) 3a E B).
Then, for s S
1 x/d
En x
( (L)
-x 1 < diam
(x)
for all N 2 1.
(59)
N +
proof of Theorem C.12 Let we rewrite x in Equation
59 as X N Subsequently, let X [u[N+1] =
X [NN[N] U Let A, = Q [X (1)
plM (X)
X I (c). where A(a,) r) = fx E Rd ||x
a/l < r/23. Note that, A; n = e if + j. Thus, 1 A C
Now, let À denote the Lebesgue measure on Rd Then, we have
N+1 Σ
A(A)=
( A.) < I d
(60)
Subsequently, since A (A.,)
Nlay (xx) (x)) X we have
N+1
N+1
Σ A( = Σ
(1)
H(N) (X:) X
(61)
i=1
==1
Thus, from Equations 60 and 611. we have
Σ
x
X
dia
(62)
A[N
Note that it follows from Jensen's 's inequality that
N+1 N
N+1
x/d
Σ
( - XX
<
(1) HIN
(X)
(63)
N
+
1=1
20

---

Published as a conference paper at ICLR 2025
From Equations (62 and 63
have
k/d
(1) A[N]
(X
-
1
x
HIN (x²)
(2)
x
+
N
00
k/d
N dia
n/d
di)
(N+1 +
(64)
Thus,
N+1
a/d
(
x x!" S diam(12)*
Ex;
(65)
N + 1
N +
where Ex:
(1) xx)
denotes the expectation of | u(N)
(x+)
X
with respect to X
Note that,
x Eu
uli (INN(()) (x)
(2) x
Ex;
x
x MIN) (xx
-x
(66)
Therefore,
N+1
Epy x
[ (x)
(1)
1
Ex
x -x
(67)
N
Finally, from Equations
65 and (67
we have
N+1
s/d
Ey ( AIN (x)
x
Σ
Exp
x1 xx)
(x) - x
S diam(
1
(68)
N
N N+1
This completes the proof.
Corollary C.13. Assume the same assumption as in Theorem
C.12
Then, for 1 15 S d
lim NJ/d N
{ {Ea, || x - x
1/r
< diam([]).
(69)
proof of Corollary
C.13 First, from Theorem C.12 when K =
p/d
M[N] (x) x x|(0 S (lamm(22)
1
E
for all N 2 1.
(70)
N
+
Thus, for all N 11
p/d
1/p
{ Fl (1)
(x) -x12 1/p
diam(St)²
N+1
1/d
diam(
(71)
N
+1
Taking lim both sides of the above inequality, we have
x 1/p
lim N2/d
{E, x (1))
x
000
Wl/d diam(s)). (
1/d
< lim
N +00
N N+11
diam(12).
(72)
This completes the proof.
n
21

---

Published as a conference paper at ICLR 2025
Corollary C.14. Assume the same assumption as in Theorem
C.12 Then, for 15 PS d/2.
1/8
{
dQ dP
}r
lim N1/d
Ep
(x)
x
(()
+000
[dQ dP
2D
))
1/(2.p)
< diam(St)
Ep
(x)
(73)
proof of Corollary
C.14 First from Theorem C.12
when K. p and μ P.
2pp/d
Ep x
(1)
P(N
(x)
x 1
x
ppp
diam
N +
1
for all N 2 1.
(74)
Thus, for all 1,
(x)) -x 2-p 1/(2-)
2p/d 1/(2-))
Ep X (1)
1
N
1/d
1
diam(S))
(75)
N N+11
Now, using Hölder's 's inequality, we have
Ep
dQ
x
xx" 1
dP
Ep
dQ
(x)
2
1/(2p)
EP
(1)
P(Ny
- -x
-x1
2-
1/(2.p)
dP
dQ
2'p
1/(2.)
1
1/a
Ep
(x)
diam(S?)
(76)
dP
N +1
Taking 1 on both sides of the above inequality, we have
Jim N//d
Ep
dQ
(x)
)"
P
(11) (x)
- x
1/p
N
dP
1/(2-p)
1/d
dQ
< lim
N2/dd
Exp
(x)
diam(())
N-+00
dP
N +1
{
dQ (x))
2
1)
1/(2m)
diam(())
Ep
(77)
This completes the proof.
Lemma C.15. Let I be a probability measure on Ted with d 2 Assume that μ & A, where denotes the Lebesgue measure on RRd Let || bloe denote the maximum norm in Rd: Ily xlloc = max maxisisa ly x²), where y = (y",,?....,, A(x, r) denote the d-dimensional interval centered at with each side of length r: A(x,T) fx e
and x (x x² ,...,,") ). Additionally, let
Rd xx' x||x0 S r/23.
Then, for any interior point in ?
dp (x) r +o("), as r + 0.
# (A(x,)))
(78)
dA
where f(r) o(g(r)), as 0, denotes asymptotic domination such that lim f(r)/g(r) 0.
22

---

Published as a conference paper at ICLR 2025
proof of Lemma C.15
Note that, if is interior point in 92, it holds that
lim (()(x,r)) du (x). 2-0 {()(x,r)) dA
(79)
From Equation 79
we have
m()(x,)))
(x(x)r))
lim
lim
pd
pd
1s (x(,))))
lim
(80)
-
A (()(x,T)
dp
(x).
(81)
Here, we use an equation where ((4(x, r)) = rd in Equation 80).
From Equation 81 we observe that
du
dd n(A(x,r)) (x) nd + to (19),
0.
(82)
This completes the proof.
Corollary C.16. Assume the same assumptions as in Lemma C.15 drawn from p., and let Ex denote the expectation with respect to X. Then, for any interior point Xg in Q2
Let be random variable
dp (xo) pptdt1 + o (rotdt1),
Ex [xx 1x I(A(xo I(A(xx,))) (x)
as r r-0, 0.
(83)
dA
where I (-) is the indicator function for A: I(A)(x) 1fxx A, and otherwise.
proof of Corollary
C.16
Consider the integration variable from x to r such that
|x x1I>- =r.
(84)
Then, from Lemma C.15 we have,
O.
dp dx
du (xo) rd + (rd)).
((A(xx,r))xx))
(x)
(85)
dd
dd
0, From the definition of expectation with the density du/ dA and Equation 885 we have,
Ex
[x00 x I(A(xo. r)) (x))
/ [x x1i<- I(A(xo, r) (x) dA
du (x) dx
/ nb. (4)) (xo) (xo)) pd + 0 (1ett dr d)
du d)
(Xo) pttdt] + o (rotdtl).
(86)
This completes the proof.
Theorem C.17 (Theorem 4.4 restated). Let P and Q be probability measures on a compact set Q in Rdd with d > Assume that P & and Q & X, where denotes the Lebesgue measure Rd Let p be positive constant such that p 2 1. Assume Bldd//dP /PP) xc.
Then,
lim N1/d, N-x00
FxMM
Ep
{
dQ dp
(x(1
(x)
-x00 1/P
23

---

Published as a conference paper at ICLR 2025
dQ dP
|]]
1/P
2
Ep
(x)
(87)
where Exx rin]
[] denotes the expectation on each variable in X XPNN]
Xp.........
proof of Theorem C.17
Let
x1100 S 1 1/d
B X
X3 -x|1
-
(88)
Since x x(1) (x))(x)) (x) is the nearest neighbor in {X7,, Xpp..... ...,.. X
for x,
1/d
1 1 N s.t. |X
1
x 00
N
-
1/d
x((1)
XX (x)
- -
I
(89)
N
Thus,
1/d
x (x) (x)
x
1
Ω
N
N
1/d
N U
X
| -
x
B
(90)
N
Next, define
N (B))
Zx(x)
(91)
i=1
Let Xp be random variable drawn from P with Xp 11 X for 1 SiSM N.
From Lemma C.15
P(I (xp) P(B.)
dP
1
d
1
d
(Xp)
di
Ni/d
Ni/a
dP
(Xr)
+
dd
N
N
1
1
(92)
N
N
and I (B:) (Xp) E (0, 1} and / (B.) binomial distribution with N trials and a success probability for each trial of 1/N o(1/N).
(Xp) IL / (BB) (Xp) for i j. j. Namely, ZN (Xp) follows a
Then, we obtain
F P[N] (((ZxxX>>= = 0})]
(
1 N
)
11 N
N
(93)
Since N 1 1 N (+) 1, we have
1
(N
1 N
N
= -
1
( 1
N-1
1
N
N
N
N 0C.
24

---

Published as a conference paper at ICLR 2025
Thus,
Exp:N] [((Zx(Xp)=01) x
-11-3 1
-011)
(as N - 20).
(94)
N
In addition, note that
NV U
2x(x) 21 I
B3 (x):
1=1
and
Zx(x) 21 = UUN Bi
(x) =1
In particular,
N
Ex(x) = +
Σ
1 (Bi) (x) =.
i=1
Therefore,
Zx(x)= -1 - Σ (B.) =
-
(95)
Now, we obtain
dQ {dp dP
(xx) (x))((s)) } [x (x) x
Np/d. Ep
dQ
(x (x)
}
2 Nn/d. Ep
(x) x
dP
x ((XED
1/d
XXE
||x0|x(()) (x) x|| 5
x ((XEn [Zx(x)=11 = =1})]
=Np/d, Ep
{
ddQ
(x (x)N)(x)) ) "
| [x((x(x0) (000-x(] xI""
-x
dP
x (UB)) -1 (fXED [N(x) = 1})
(by Equation 90)
-No/d, Ep
dQ
[ (x)))(x)) } "
/IxPM)(x0) - x1(00
dp
x Σ I (Bi) I (fXE2 Zx(x)=11))
= =11)
(by Equation (95
N
IQ
(x (x))())) " [xx(x((x) (x) -xxx 11/
NP/d
Ep
x
dP
1=1
x ((:)). 1 ((XE2 Zx(x)= = =1}]]
dQ } "² -|XF6 x x1(
-NP/d
Ep
dP
i=1
I(B)): . I 1(xE2
= [[(k)=]]]]]]
(96)
25

---

Published as a conference paper at ICLR 2025
Now, let
xx = Σ T (B:)
Then.
(B.) I ((xE Zx(x) = 1x) 1 IB(.) I (fxED =0}).
(97)
Additionally, let X ppii denote the subset of XPIN excluding X i... XPiNi = XPINI (Xp).
Let E- denote the expectation over the variables in X which is equivalent to Exx p|N]
From Equation 94
N ((B)) 1 (xXES) (x - = (1- N -I-N-1
1
1 (N-1)
(98)
From Equations
997
and 988.
we have
dQ
x (B,) I {(xE5 ZN(x) = =1}) ]]
E
Ep
X x
N
dP
E
Ep
dQ
(xp)
| - x x (BB) 1 ((xEn
(x(x))² = o))
dP
Ep
dQ
( P)
P
x
((.)) FNn' 1 1(xx(8)) ES
(x(x)=²= o))
dP
Ep
dQ
(x*)
/
X
x
x T(B)) x (1-
1 -
1 (N-1))
N-
dP
1
(w-1)
1
N-2
dQ
(xp) )
| - xx"" x I (B,)
x Ep
N -
N
dP
(99)
From Corollary C.16 we have
Ep
dQ (xx)
| -x x||0 x
I
(B.))
dP
dQ
P
dP
1
p+p+1
ptdt1
(x%)
(x,)
+o
dP
du
N1/d
dP
dQ
(xp) }
Itp/d
1tp/d
(x))
+
dy
dP
N
N
dQ
}
1tp/d
1tp/d
(xp)
+o
(100)
dP
N
From Equations
(99 and 100). we obtain
E
Ep
dQ
xp)
}
|XA - x
10/
x (lB)). -1 ((xE0
Zx(x)= =1}] ]]
N
dp
N-2
1
1
N 1
N
26

---

Published as a conference paper at ICLR 2025
dQ dP
1 N
1tp/d
1+p/d)
x
X p)
o
(101)
From Equations
(96 and 101
we obtain, as N - 00,
Nold. ExPNN
Ep
dQ
x
() (inn(())
}
( (()) (x) x
dP
2 No/d EXPINI
Σ Ep
dQ
(xx) } 1
||x6 -6/2" xI("
dP
(B:) 1 {x ED Q
Zx(x) = 11)11
N
dQ
}"
p |X--Xx - 1
Ne/d Exi
EN Ep
dp (Xx)
x I(,)) I ((xES) [N((x== =1}) ]I]
(by Equation (96)
N
(1-N' N o (N-1))
N-2
No/d Exi
dQ
}
p
Itp/d
1
Htp/d
(xp)
+o
dP
N
N-2
1
N
N
N
N
dQ
1
}
x
Ep
(x)
+ N
(by Equation (TOT)
dP
1 N -
1
1
N-2
Ep
{
dP (xx)
dQ
tO(D].
N
N
(102)
As N - 00, observe
N-2 _
1
(103)
-
N
N
Then, from Equation (022.
we obtain
lim NP/d EXPIM
Ep
dQ dP
x (I) (x }
|
-x 1
200
Kap dp (x)
(70
pr
2 ce 1, Ep
(104)
This completes the proof.
Theorem C.18. Assume that f satisfies Assumption C.6 (N) arg -R,0 (g))
(Φ) For ((N) (()) defined in Definition
C.3 let
Then, for any measurable function + + Ryo. the following equivalence holds:
((x)) (2x(())) Op
1
for 1 SiSN
VN
(O) min
E5(0) O VN
(105)
dcf2
where (X) X2 X2...., X. is defined in Definition
C.3 and L5(()) is defined in Lemma C.11
27

---

Published as a conference paper at ICLR 2025
proof of Theorem C.18 First, enumerate several facts used in this proof.
From the Central Limit Theorem, we have:
2 (d! - Er | (5! = =0p
1
(106)
VN
II. From Proposition C.10 we have, for all x E
X W[N]
dQ
0 (x)
dP (x),
(107)
where [p(N] is defined in Definition C.3
III. From Equation (107). follows that:
1 (0!M)) E
( dQ
(108)
dP
and
F ((N) (ob = F.yo
[(M)
dQ
(109)
dP}
IV. From Lemma C.I1
we have:
min Ey(0) = Ls 0
dQ dP
E.g
(N)
[
dQ dP
(110)
V. From Lemma
C.8 for (1; defined in Equation 28
we obtain:
i, dQ
du dp (x);
0,
(111)
and
du 1
d²
dP (x);x)
dQ
= -
dP(xx (x)
dQ
dP dp
(x).
(112)
dP
VI. From Theorem
C.9 we have:
dQ
dQ
dP
dQ
(u;x) T,
dP
(x):x
=
2
1"
dp
(x)
dp
(x)
dP
(x)
dQ
2
+
dp
x
(113)
where f(a) = o(a) (as a + 0) denotes asymptotic domination such that lim f(a)/a=
0.
VII. From the assumption that Eplf" (dQQ < 0o,
dQ dp (x
dP
f"
( = Op (1), as N + oc. du
(114)
Now, we show the direction
52 in Equation 1005..
Assume that of ((x)) 0
+ Op (I/VN) for 1 M
From Equations
35 in Theorem C.9 and (14), we have
T, (x(x)); x - -T, (0! (X x
28

---

Published as a conference paper at ICLR 2025
dQ dP
(o(x,))) -1
(x
= 2 M"
ap (xi)
dQ
dp
(x+)
6 6(x²)
dQ
x
2
+ ( [(xx))
dQ (x
{ )
dj
dp
1"
TP
dQ
)x:)
dp
djp
(xx)
((xx)
~ (x
+o
( (x))) )
Op (1) O, ({ VN
2
Op
(115)
N
Thus, we have:
(0) (1) - -1/²² (d!
1
T (x(x))x
T, ap
(1p
(x xxxxx
N
N
Σ
Op
N
N
==1
1
Op
(116)
N
From Equations (106),
108). 110
and (16).
we obtain:
Z (0)
min
(Ø)
{ (b) - k710 (x! }
min
(x(0)
$00-220
(o) M (
E(N)
dQ
min
(の)
(by Equation (108)
dP
(2)) (0) - / (o!)) }
dQ
dQ
E
(by Equation (100)
dP
dP
{ ( (0) - M (o! }
(
(DS*)
(0. (((N)
(by Equation 108
O, + +Op
(by Equations 106 and 116
VN
Op
(117)
VN
Thus, we have proved "_>
Next, we prove the direction "<" in Equation 105)
Suppose
()) min
Z)(0) = 0,
(118)
VNV
From Equations (06).
110). 109 and (18), we obtain
((N) (0) - - (o!N))
= = -7
(0) (2))
[5(0)
Σ,(d) Z (o!^7)
min
min
29

---

Published as a conference paper at ICLR 2025
(0)
min oill+kg
(x(
+ E (
dQ (P))
] - kggo) (o!M7)
(by Equation (10
(7 (6)
min Rao
[)(0)
+ {E (o!*)) |(N) )
)
(by Equation 109
1
O,
+ +Op
(by Equations (006) and (18)
Og
(119)
From Equation 107 we have
N
2 (0) - 2 (D!"))
Σ
(o(x))) x,,
1 Ei (x)):
N
N i=1
Σ
1 xx xx, - T, (x,)) }
N
(120)
From Equations (19) and (20), we have
1
i (o(x))xx)
T, (20 dP (x)x)) }} -Op
(121)
N
Let n = Ep |1
2 (xx) Since x is identically distributed for S í S N, we have aly- = a for any isiS N. Thus, define AN = sup ai = =upp2 a.
(x(x))
Using Chebyshev's inequality, we have for any >>> O.
(Oxx))) - 0. 1 (x+))
/AN >
8. E.Ep
(x(x)) - 15hh (xx+
An
E .'a's
An
Se.
(122)
Thus, xx)))
(4)
(X)) = Op(AN):
Now, we calculate
N
1
( (O(X):xx: - T, (x,):x))
N
Σ
N
7 (Oxx)): xx)) - 7, (10
dp (x,):
N
N
1
x(xx)))). or (10xx)) dP
dQ
(xx,)) 1) + +.0 (lxxx:)
dQ
(x:) }}
Σ
N
2-
dP
1 N
(1xX)))- - (m) (xx)) (
up (locx)) - 13 (x;))))))
x(x))
10,
N
2
1=1
1
Op (VN) Op (Ax) + N N 2 op (At)
N
N
2
30

---

Published as a conference paper at ICLR 2025
= Or (VN) O2 (AR) + op (At).
(123)
Here, X = Op(aN) denotes the convergence in probability with rate in f N + xc: X =
0p(an) (as N + 00) VE, Ag > (E, 8) such that //X 6) < f A. 2 N(,, 8).
From Equations 121 and (23) we have
20p (VN) Op (A2) top (Atr)
Op
(124)
From the definition of AN, observe that AN decreases as N increases. Thus, lim AN exists
and 0 < 1im An < 00.
Suppose that lim AN > O. Then, we have
Op (VN) Op (A2x + op (AN) = Op (VN) + 0p (1). (1).
(125)
This contradicts Equation 124). Therefore, 1im AN = 0.
From Equation (14). we have
1 N Op
A
2 Op (A3v) + +0p
VN
Op (A%)
(126)
Thus, AN - (1/VN).
Finally, we have
o(x)) 25 (N) (x,)) O2 (AN) = O,
1
(127)
Here, have proved the direction "("
This completes the proof.
Corollary C.19 (Theorem restated). Assume the same assumption as in Theorem
C.18 let
(C0) = arg ming:f-BR. 4 (0).
Then, for any measurable functioonn @ : Ω Ry0.
((x)) - (N))
=p
for Sirs
(((..))())
inf 0:52 o
En
c () (6) = =0p
RR,))
(128)
where (X) X2 po.... X is defined in Definition C.3 and LJ
(R)))(()) is defined in Definition C.2
proof of Corollary
C.19 From Lemma C.11
we have c
C(R.S) Lz(
Thus, Equation
128 follows directly from Equation (105)
This completes the proof.
Theorem C.20 (Theorem 4.5 restated), Assume that Ω2 is a compact set in Rd with 2 and
that satisfies Assumption C.6 Let P and Q be probability measures on Q. Assume that P < and Q & X. where X denotes the Lebesgue measure on Rd Let (x)) be the energy function of dQ (x)) defined as (*(x) log dQ/ dx(().
31

---

Published as a conference paper at ICLR 2025
Let F(N) Specifically, define
Lip denote the of all K-Lipschitz continuous functions Q2 that minimize Lg (.).
F(N) oo Rso (d.) min 2g (0) }
(129)
and
FK-Lip ( R2
(d(y) x(xx) S K. by x11 for all y, x E
(130)
Subsequently, lel
F(N) R-Lap
F(N) n FK-Lip-
(131)
C.4 there exists I, > O such that x||0o for any y, x E 9 i.e, (x) is L- Lipschitz continuous on Q2
(Upper Bound) Assume Assumption
s T. lly
Then, Equation 1320 holds for S p S d/2, such that for any & E F(N) K-Lápp
dQ dP
1/v
Tim N
Ep
(x)
((x)
N-00
1/(2-p)
dQ dP
2p
S L. (S))
Ep
(x)
+ K diam
(132)
(Lower Bound) Assume Assumption C.5
there exists such that (1/L) lly x||
(y) (x) S L- Ily x1loo for any y, E Q, i.e. (x) L-bi-Lipschitz continuous on Z.
and Ep [dQ/dP] < with p d.
F(N) Then, Equation 1331 holds for any K-t such that
dQ
{}
1/8
lim
N1/d
ExpIN)
Ep
(x)
o(xx)
dP
1
dQ
1/v }7}
Ep
(x)
K diam((2)
(133)
dp
1
ا- KLQQIP))) K diamm()))
(134)
L
proof of Theorem C.20
First, list the equations used in this proof.
Using the second-order Taylor expansion of e-t, we have
e- - 1+ <(0) C, where 0 < [c(() < 11..
(135)
II. From Equation 135 it follows that
dQ dP (y)
dQ (x)
= (T)
(T))))
-T"())
(y))
(T (T' (y) Tx'(x)) + +²² clxx.)) (y) T" (x))²
dp (x) (T) (x)))) + + (.lx.x.")..(.) (T* (x)))
dQ
1
where 0 |C x, T") < T (y) (x))
(136)
32

---

Published as a conference paper at ICLR 2025
III. From Corollary C.13 for 0 S p S d/2.
PP 1/p
lim Ni/d. Ep x
xx))(x)
diam(1).
(137)
IV. From Corollary C.14 for 0 S p S d/2.
lim N
N2/d
Ep
P dP (x) }
dQ
1 P(N](x) - x
x1
1/8
[QQ dP (xx]
2.
1/(2-))
$ diam(
Ep
(138)
V. From Equation 138),
for 0 S S.S. d/2.
( P[N] P(N7 - -x 12P 1/r
dQ
}
lim
N/dd
Ep
(x)
N-xc
dP
dQ
2 1/(2.)
1p
1/(2-))
$ Jim
Nl/d.
Ep
(x)
Fp
-
1 (x) -x -x1
N
dP
dQ
2
1/(2.))
N//a
Ep
(x)
diam
lim
dP
N
N2/d
0.
(139)
VI. From Theorem C.17 for S S d,
{dPp
{
dQ
(xPmn(ss) }
1/P
lim Ni/d
ExPIM
Ep
x
dP
+00
{
dQ dP
} P
""}""
1/p
2
Ep
(x)
(140)
where Fxx MiN!
denotes the expectation each variable in X P|NN
(X ps X²
X
VII. Let X A[N] denote the set of random variables defined in Proposition C.10 From Proposition
C.10
dQ for 1
Φ E K-L
F(M)
x(x))
dP (
s W < N.
(141)
Let ((x) be member of F(N) Lap
Now, we prove Equation 132
By applying the triangle inequality in the Lp norm, we have
dQ
1/P
Er
(x)
o(x))
}
dP
<
Ep
dP (x)
dQ
dp
dQ (x)N((()))
(x(1)
() 1/p
+ Ep
dP
dQ
(1()
(x))))) -6(x)) 12) 1/8
(142)
From the K- L-Liischhiz.continuitt
continuity of & and Equation (11).
dQ
(x)) - <6(x) 10 1/p
1 1/p
Ep
Fr x MIN] ( o(x)
(by Equation 141
dP
S K. { Fr (1)
11
1/P
(x)
(143)
33

---

Published as a conference paper at ICLR 2025
From Equations (37 and (13).
dQ
" 1/8
lim N +00
Ep
a(7 (x)x - 0(x))
K - (
(144)
dp
dl' Next, by substituting y x(1) (x) and multiplying by du
(x) in Equation (136). and using the
L- L-Lipschitz continuity of T we have
Ep
dQ
(x(1)
[xN](x))
dP (x)
dQ
1/p
dP H[N]
dQ
(x) x {T ((N)(x))) (x (x))))
-Ep
Ep
dP
(|Nx H(N) (x)) (/A/( -xT) }} 187 1/p
+ 2 ci(x) (TM
where 0 < Ci(x) s (T (1) (x) - 7 (x)
dQ
{ u(1/ ((N)(x)) (x)) - -rxi)
x) x
dQ
(1
cL(() (T- (17 (x)) ((x)) 1/p
+ dP
(x) x
{2
Ep
dP (x)
dQ
P
T (x (1)
M(N) H(N) (x)) -r<xs)"]]
+
Ep
{ dQ
(x)
}
1 - ||- (x (1 mix((x)) - -x/) 22
}}
1/2
dP
20
aQ
P
T TT (x)) -T Tx00
1/8
Ep
(x)
dp
dQ
(x)) }
+ Ep
dP
1
o
(x))
(x (x)) -Tx()) [2p]
[ 1/p
20
:: (x)( s T (x (/N (x)) 7T' (x))
dQ
(x)) } P IPP
-|xx//xX()) -x1""
1/p
Ep
dP
dQ
+
Ep
dp (x))
((1) (x)
(x) 11<0 L..
|x x() - -x
2.p
1/p
20
Ep
dQ
xx)
L" 1| (x) - x
1/p
dP
dQ
xx) }
p
+
Ep
dP
L-diam((1))
I.P. (x() (x) x
12-0]
1/p
x 20
Eop
dQ
(x) /"
||
x
11"0
1/0
dp
34

---

Published as a conference paper at ICLR 2025
1 + eL-diam(()) 2
{
{
dQ dP
}"
||x
- x |2
1/8
Ep
-
(145)
From Equations (38).
139 and 145). we have
dQ
1/p
lim N//a
Ep
(x)
- (x (x)(
N 40000
dP
dQ
1
X (x) - - 11 1/8
< lim
N2/d L.
Ep
(x)
N
dP
+ lim
N//d
1
(l))
Ep
dQ
(x) } -| - xx
22
1/p
N
2
dP
dQ dP
2
1/(2.p)
= L. (S)
Epp
(x)
(146)
Finally, from Equations
144
(142) and (16).. we have
dQ
pP)
1/p
lim 11/d__
Er
(x) - x(x)
N
dP
1/(2p)
dQ dP (x)
2.p
S L L- diimm(a)) (12)
Ep
+ diam( K.
(147)
Thus, it is shown that Equation 132) holds. Next, we prove Equation
133) By applying the triangle inequality in the Lp norm, we have
dQ
p 1/p
Ep
xx) - x(x)
dP
dQ
dQ
} 1/v
{{
dQ
(x)) o(x0) / 1/2
2 Ep
(x)
(x
(x))
NNNT
Ep
X
H|M
(1)
dP
dP
dP
(148)
x(N) (x) and multiplying by Lipschitz continuity of T we have
By substituting = x (1)
dP
(x) in Equation 4p
136 along with the L-bi-
dQ
dQ 1P
1/p
EP
[iN)
(x))
dP (x)
dP
dQ
Ep
X (1)
(x))
dP
{
[ x (1)
(IN (x)) (x))
H|N)
+ 1 c1(x) (T((X(1)) (x)())()))) - (x)) }}] 1p) 1/p
2
where 0 s (x)) S T (x ///2 (x)) - (x)
(1) HIN (x)) }
(X (xx
1/P
Ep
dP
dQ (1) dP
? (x)(( }
Epp
35

---

Published as a conference paper at ICLR 2025
| (xxxx) - -xx) 201) 1/8
2"
In ||x (x)) - -x1[]] 1} 1/00
2
E.
(11
HIND (x)) p
1
dPP
(1) (1)
n[Nv] (x)) }
?
Ep
dp
1
c - (1)) xx10)==1=__0 x11,. I" ||x (xx - -x 2.
1/r
x 2D
dQ
(11)
HIN (x)) }
DP /xx - =x11]] 2/2
1
2
EP
dP
dQ
Ep
(1)
u(N] (xx)
dp
ex L.)iia(( IP. [xx -x [22]] 1/p
1
x 2D
ml/v (1NN7 (2x) }r -1xx)//((0) - -x1" } 1/1
1
Ep
dQ
(x
(1)
L
dP
Ep { da (X (ho) || (x) - x 2/
dQ
x1(30]
1/v
e
(1))
T.
(149)
2
From Equations (38),
139p and 149) we have
dQ
ol ((x(0) (1) MLyy (x)) 1/1
lim
N2/d.
EXPIMI
EP
(x)
dP
N-00
lim N2/d.
EXPMN Mi
Ex
1
Ep
dQ
(x (1) (x)) }², - (xx))
-x)x))x(((
-x([0]
1/p
N-000
LP
dp
1 diam
dQ
(x
piNi (x1)(())) }r
- x1100]
-.
Ep
2
dP
dQ
(x (2) (x)) } - =1=3) 1/p7
> lim Nl/d. N
ExPIMI
Ep
dP
1
lim Nl/d
ExPM MM
(1)
N
2
{ dQ
(x wly)(x))) }"
/xxx)((x) (x) - =x1²0]] 1/v
xL
EP
(x (1)
d.P
1
{dQ
nQ dP
(x(1) (1) (x)) )"
| (x) -x xl(3]) 1/27
2 lim Nl/d. ExPIN]
Ep
N-00
L
ExPiN
lim 1/dd
1 diam(())
N-000
{ dQ
(x (x)) )" | - =1(²0) 1/8
}
XL
Ep
dP
dQ
}
}"]}
P7
1/8
Ep
dp (x)
(150)
L
36

---

Published as a conference paper at ICLR 2025
Finally, from Equations 144]
148
and
(55
we have
1/97
dQ dp
lim NP/d Ex Ex
Ep
(x)
6(x)
dQ dp
}
1/P
L (x)
Ep
diam(s)) K.
(151)
Thus, it is shown that Equation 133) holds.
Next, we prove Equation 134 First, we have
dQ dp (x) }
}"}
1/8
dQ
dQ dP
P-1
1/P
EP
Ep
(x)
(x)
dP
1/p
dQ
EQ
(x)
dP
}}
1/D
EQ
e(o-1))log 3 (x)
(152)
From Jensen's 's inequality,
{ Fo clo-t)iloa 12)x)) (x)
}
1/p
c Eu
(p- 1).log (p-1).1og 48 (x))
1/8
2
1/8
1)-E0
log (8
Eq
log (x)
F .LL.L(QQ P).
(153)
From Equations 151). 152) and (53).
dQ dP
1n 1/m
}
lim Np/d EXPIM
Ep
(x) - -(x)
N +00
dQ dp
P 'T1}
1/8
Ep
(x)
diam K
L
m=1 KL(Q[IP)-1 diam(St) K.
e
(154)
This completes the proof.
Theorem C.21 (Theorem 4.8 restated). Assume the same assumptions and notations as in Theorem Additionally, define
C.20
F(N) F. { FK 7o. E K-Lp such that & = +. + Op
VN {}}}
FkiLip
(155)
That is. FK-Lsp denotes the set of all functions that differ by at most O, (N) from some functions that minimize E.
(.). (.).
Then, the same results as in Theorem C.20 hold for all &o E K K-p Specifically:
I(N)
37

---

Published as a conference paper at ICLR 2025
(Upper Bound) Under Assumption
C.4
Equation
132
holds for S d/2 such that for any
F ④
K-Tpp'
dQ dP
1/v
im N N//d
Ep
(x)
x(xx)
dQ dp
2.p
1/(2-p)
S L.
diam(S))
Ep
(x)
+ K - didmmm)))..
(156)
(Lower Bound) Under Assumption
C.5
Equation
133
holds for any & F(N) K-T such that
1/p
dQ
lim
1/dd
ExPNN
Ep
(p(x)
(x) - 6(x)
dP
N
1
dQ
1/p }7}
Ep
(x)
K d.amm(2)
(157)
dP
p=1
-KT -K. diam(())
L e
(158)
Proof of Theorem C.21
First, we prove Equation (56].
Let e be a member of K-Lip' Then, there exists o E K-Lip such that = 6 6
((N)
Using the triangle inequality in the Lp norm, we obtain
dQ dP (x)
19 1/p
dQ
1/P
Ep
-
=
Ep
dP (x) - x(x)
+ +Op
dQ
P
1/p
1
|0)
1/8
Ep
dP (x) - x(x)
+
Ep
Op
VN
dQ
1/p
1
Ep
dp (x) - Φ(x)
+0
(159)
VN
From Equations (132 and (59), we have
dQ
19) 1/8
Jim
N2/d
Ep
(x) x(x)
dP
Ep dQ
1p) 1/p
lim Ni/d
(x) -x(x)
+0
400
dP
VN
Ep dQ
}
1/D
lim
1/dd
(x) o(x)
+
lim
Nl/d
400
dP
N
N
Ep dQ
}}}
1/P
Jim
1//d
(x) 6(x)
No000
dp
Ep dQ ((pp(x) (x)
2.p
1/(2.r)
L. diadiaa))) ?)
+ K K-diaamaL diam(a).
(160)
Therefore, Equation (156) is proven.
Next, we prove Equation [17
By applying the triangle inequality in the Lp norm, we obtain
"} 1/9
p 1/p
Ep
dQ
dP (x)
T(x)
Ep
dQ
x -
x(x)
+
Op
dP
VN
38

---

Published as a conference paper at ICLR 2025
dQ dP
1/p
1
1/8
Ep
x) - Φ(x)
-
Ep
Op
VN
dQ dp
12)
1/P
Ep
x - x(x)
(161)
VN
In similar manner the derivation of Equation (160)
we have
{
dQ dp
p 1/m
lim N2/d EXPM
Ep
(x)
xxxx
Ep dQ
1P 1/p
1
lim
N/da ExPIMi
dP (x) ((x)
VN
N-+00 lim
N2/d ExPINI
Ep dQ dP (x) ((x)
1/p7
lim
N
0
1
N-100
N
VN
dQ
dP (x) ((xx }}
1/p7
lim N2/d, EXPNNI N-+00
Ep
1/p
{
dQ dp x
- Ep
diam
(162)
Therefore, Equation (157 is proven.
Equation 158) is obtained in the same manner as in the proof of Theorem C.20
This completes the proof.
D DETAILS OF THE EXPERIMENTS SECTION 3
In this section, we provide detailed descriptions of the experiments reported in Section 3 Each dataset, experimental method, experimental result, and the neural network settings used in the experiments presented in separate subsections.
D.1 DATASETS.
We conducted two experiments: one for investigating the relationship between Lp errors and KL- divergence in the data; the other for investigating the relationship between Lp errors and the di- mensionality of the data. In both, the datasets were generated from the following distributions: the numerator distribution was multidimensional multimodal normal distribution, while the denominator distribution was multidimensional standard normal distribution.
Denominator Distribution: The denominator datasets X = (X,,, X X were gener- ated from the following d-dimensional standard normal distribution:
X La)
(163)
where la denotes the d-dimensional identity matrix.
Numerator Distribution: The numerator datasets X = ) from the following d-dimensional, M --multimodal normal distribution:
X3
X were generated
x
üid
N(u Tmy Ia) 2m.
(164)
where for each mode mc
Zm ~ (1/M) and ΣM Zm = 1.
Fm Uniform (8d-1).
39

---

Published as a conference paper at ICLR 2025
Here, Bernoulli(I/M) denotes the Bemoulli distribution with parameter 1/M, and Uniform(S denotes the uniform distribution on the d-dimensional unit surface sd-1 {x E Rd |||| = 1].
In the aforementioned setting when M 1, the Kl.-divergence of the datasets is calculated as:
dp
(L(PIIQ) = Ep
log
dQ)
(0, Id)
= Ex)(O.Ta)
log
N N( Tmm Id)
Epl
+ Tr(xpt 1. Egg + (pp my) -pp (up - Ha)
log
2
Dig
Lal
+ Tr(Ia Ia) + (1r r..mm rm)² Ia (n rmm)
=
2
log
[Ia
(0- d + x² rm rmm
(165)
From Equation (165). the KL-divergence of the datasets for M is calculated
dP doe)
KL(PIIQ) Ep
log
dQ
N(0, Ta)
Ex Ez Remoull Romoollll
log
II
M
N( Frm; 1m
2m
NO Ta)
log II
N( Imy
m==1
M
NO.
1x)(o. Ez,,, m Bernoull((1/M)
log
N( (M-mmm La)
m==1
log NiO, N(u Im. La)
Ex((o.))
1
2 n.2.
(166)
Thus, we set == KT (P(l)) in Equation 1164 for M 1,2,3, and 4, where KT(PI
denotes the KL-divergence of the datasets.
D.2 EXPERIMENTAL PROCEDURE.
We trained neural networks using the training datasets by optimizing the KL-divergence divergence loss functions. Details of these two functions used in the experiments are provided below.
KL-divergence loss function. We used the following KL-diiergence loss function, LKI(.), in experiments:
CKL(T) Ep -EQ
[e")
[2]
s T(xb)
R
1 R
3 T(x)).
(167)
5
a-divergence loss function.
We utilize an a-divergence loss function originally proposed in our previous work (Kitazawa, 2024). The a-divergence loss function is defined as:
40

---

Published as a conference paper at ICLR 2025
The a-divergence loss function is defined as:
C
(R.S) a-divergence (T; a) Eqis] co
1
Erin e(a-1))To)
1 1-a
1
1 R
(a-1))
(168)
1
For further details and theoretical derivations of this loss function, we refer the reader to Kitazawal (2024).
I Errors KI.-Divergence in Data. We initially created 100 training, validation, and test datasets, each consisting of 10000 samples, with a data dimensionality of 5 and KL-divergence values 8, 10, 12, and 14. The numerator datasets were generated with modalities of 1, 2. and 4 using the aforementioned distributions. Neural networks were trained using the training datasets by optimizing both the a-divergence and KL-divergence loss functions. Training was halted if the validation loss did not improve for entire epoch. After training, the Lp errors of the estimated density ratios for p = 1, 2, and were measured using the test datasets. total of 100 trials were conducted, and we reported the median Lp errors along with the interquartile range (25th to 75th percentiles) for each KL-divergence and a-divergence function.
of 1,
Lp Errors vs. the Dimensions of Data. We initially created 100 training datasets, each consisting of 20000 samples, and 100 validation and test datasets, each consisting of 5000 samples, with data dimensionalities of 50, 100, and 200, and KL-divergence value of 3. Neural networks were trained using training datasets of sizes 1000, 2000, 4000, 8000, and 16000, by optimizing both the a-divergence and KL-divergence loss functions. The numerator datasets were generated from the aforementioned distributions, with modalities M = 1, 2, 3, and 4. Training was halted if the validation loss did not improve for an entire epoch. After training, the L,p errors of the estimated density ratios for conducted, and we reported the median Lp errors along with the interquartile range (25th to 75th percentiles) for each KL-divergence and a-divergence function.
L, 2, and were measured using the test datasets. A total of 100 trials were
D.3 RESULTS.
Lp Errors vs. the KL-Divergence in Data. The results for each multimodal case M = 1, 3, and 4 of the numerator datasets are shown in Figure 3 The results for M were reported in Section
As shown in Figure 3 the estimation errors for p > 1 increased significantly, with the rate of increase accelerating as p becomes larger. In contrast, for p = relatively mild increase was observed. As indicated by Theorem 3.5 these results emphasize the impact of the KL-divergence in the data on Lp errors for p > in DRE with f-divergence loss functions. Additionally, only small differences were observed in the results among the modalities of the numerator datasets.
Lp Errors vs. the Dimensions of Data. The results for each multimodal case M = 1, 2,2,3, 3, and of the numerator datasets are shown in Figure 4 andd 5
The results of M 1 (the first and second
rows in Figure were reported in Section
As shown in Figure 2 the I,, L2 and La errors in DRE worsened the data dimensionality increased for both the a-divergencce and KL-divergence loss functions. These results indicate that the curse of dimensionality affects all L, errors equally, as suggested by Theorem 3.5 Additionally, little difference was observed in the results across the modalities of the numerator datasets.
D.4 NEURAL NETWORK ARCHITECTURE, OPTIMIZATION ALGORITHM, AND HYPERPARAMETERS.
Lp Errors vs. the KL-Divergence in Data. The same neural network architecture, optimization al- gorithm, and hyperparameters were used for both the KL-divergence and a-divergence loss functions. A 6-layer perceptron with ReLU activation was employed, with each hidden layer consisting of 1024 nodes. For optimization with both the KL-divergence and a-divergence loss functions, the learning rate set 0.0001, and the batch size was 128. Early stopping was applied with patience of
41

---

Published as a conference paper at ICLR 2025
Lj Error (M=1)
Lg Error (M=1)
Lg Error (M=1)
ordivergence
K Kl-diveryence
DRE Errors
DRE Errors
DRE Errors
130
0.41
10
00
KL--diveggence
KL-divergence
KL-divergence
Ly Error (M=2)
Lg Error (M=2)
Lg Error (M=2)
20
o-divergence
KL divergence
DRE Errors
DRE Errors
200
10C
DRE
0:2
divergeren
Kiveiiergeene
KL Kl-diiergence
Ly Error (M-3)
1, Error (M-3)
Lg Error (M-3)
1.0
ordivergence
Errors
DRE Errors
DRE Errors
divergence
1.4
003
KL divergence
KL divergence
KL divergence
Ly Error (M 4)
L, Error (M 4)
Lg Error (M-4) 4)
230
ordivergence
DRE Erross
1.8-
DRE Errons
DRE Errons
100
KL divergence
100
uc
KL-divergence
KL-divergence
KL-divergence
The experimental results of Lp errors versus the KL-divergence in the data for each multimodal case M = 1, 2,3, 3, and 4 of the numerator datasets are presented, as discussed in Sections and D The results for M 1 were reported in Section 3 The r-axis represents the KL-divergence of synthetic datasets with fixed dimensions. The y-axes of the left, center, and right graphs represent the L1, L2, and La errors in DRE, respectively. The blue line represents errors using the a-divergence loss function, and the orange line represents errors using the KL-divergence loss function. The error bars denote the interquartile range (25th 75th percentiles) of the y-axis values. The plots show the median y-axis values corresponding to the KL-divergence levels in the synthetic datasets.
Figure 3:
epochs, and the maximum number of epochs was set to 5000. The value of a for the a-divergence loss function set to 0.5, PyTorch (Paszke et al. 2017) library in Python used implement all models for DRE, with the Adam optimizer [Kingma] 2014) in PyTorch and an NVIDIA T4 GPU used for training the neural networks.
42

---

Published as conference paper at ICLR 2025
a-divergence- Error (M=1)
n-divergence Ly Error (M=1)
c-divergence Ly Error (M=1)
Uim-50
Iog[DRE Eirors)
-0.4
Dim-1000
Inre Errons)
log Erros))
Dim-200
--20
(Nmmbrr Samples)
(og(Numeer Samples)
log(Number Samples)
KL-divergence Error (M-1)
KL-divergence La Error (M=1)
KL-divergence Lg Error (M=1)
101
log,DRE Erros)
Ieg Errors)
DRRE Errors)
100
-0.2
0.4
0.6
7.0
7.3
2.0
25
50
7.0
1.5
5.5
90
93
170
80
5.5
50
kog (Number of Samples)
log( (Nuumer of Samples)
(og(Number Samples)
a-divergence L, Error (M-2)
a-divergence Lo Error (M-2)
2-divergence Lg Error (M-2)
Dim-50
(DRE Erros))
-0.4
Dim-100
log(DRt Emars)
be((DE Errors)
-96
20
-10
65
65
log (Number of Samples)
(Nmmeee of Samples)
log Number of Samples)
KL-divergence Ly Error (M=2)
KL--divergecc L Error (M=2)
KL-divergence L, Error (M=2)
(Dg(RRE Erros)
-22
[og( Erros)
log (DRE Errons]
36
100
-0.4
kug (Namber Samples)
lug (Nmmber of Samples)
log (Nmmbrr Samples)
The experimental results of Lp errors versus the dimensionality of the data for the multimodal cases M = and 2 in the numerator datasets are presented, as discussed in Sections 3 DDd The results for M were reported in Section 3 The top row shows the results using the a-divergence loss function, while the bottom row shows the results using the KL-divergence loss function. The a-axis represents the logarithm of the number of samples used for the optimizations for DRE. The y-axes of the left, center, and right graphs represent the L1, I.2, and T.3 errors in DRE, respectively. The blue, orange, and green lines represent the results for data dimensionalities of 50, 100, and 200, respectively. The plots show the median y-axis values, and the error bars indicate the interquartile range (25th to 75th percentiles) the y-axis values for the logarithm of the number of samples used in the optimizations for DRE.
Figure 4:
Lp Errors vs. the Dimensions of Data. The same neural network architecture, optimization algo- rithm, and hyperparameters were used for both the KI -ll-dieegeence and a-divergence loss functions. 6-layer perceptron with ReL.U activation was employed, with each hidden layer consisting of 1024 nodes. For optimization with both the KL-divergence and a-divergence loss functions, the learning rate was set to 0.0001, and the batch size was 128. Early stopping was applied with a patience of epoch, and the maximum number of epochs loss function was set to 0.5, PyTorch (Paszke et al. (017) library in Python was used to implement all models for DRE, with the Adam optimizer [Kingma 2014) in PyTorch and an NVIDIA T4 GPU used for training the neural networks.
set 5000. The value of for the a-divergence
43

---

Published as a conference paper at ICLR 2025
c-divergence- Error (M-3)
a--divergence Error (M-3)
a-divergence Lg Error (M-3)
(og(DRE Errass)
Dim-100
(DRE Erross)
40
log( DRE Errans)
-00
Dim-200
%
-10
%6
-10
26
20
75
6/
70
25
65
25
60
65
(Ngumee Samples)
Nugmbee of Samples)
Nog(Numerr Samples)
KL-divergence Error (M=3)
KL-divergence Ly Error (M=3)
KL-divergence
Error (M=3)
4.0
DRE Erars)
log/LOWE Emross
log( DRE Erass)
0.4
-04
30
2.0
25
300
60
65
25
80
90
90 85
60 65
log (Number of Samples)
log(Number of Samples)
log(Number of Samples)
c--divergence- L Error (M=4)
aediivereence Lo Error (M 4)
a-divverennee Lg Error (M-
Dim-50
DoR Errors]
-44
Dim-100
log (RR Errars]
DRE Errons)
Dim=200
7.5
2.0
40
los( Number of Samples)
log(Number of Samples)
log(Number Samples)
KL-divergence L, Error (M=4)
KL-divergence La Error (M=4)
KL-divergence Lg Error (M=4)
2.50
kog DRE Eirors)
log DRE Errons)
lag DRE Errons]
-0.4
1.7
2m0
1.25
200
log( (uguumber of Samples)
log(Number of Samples)
log(Number Samples)
Figure 5: The experimental results of Tpp errors versus the dimensionality of the data for the multi- modal case M = 3 and the numerator datasets are presented, as discussed in Sections [ The top row shows the results using the a-divergence loss function, while the bottom row shows the results using the KL-divergence loss function. The z-axis represents the logarithm of the number of samples used for the optimizations for DRE. The y-axes the left, center, and right graphs represent the L1, L2, and Ly errors in DRE, respectively. Blue, orange, and green lines represent the results for data dimensionalities of 50, 100, and 200, respectively. The plots show the median y-axis values, and the error bars indicate the interquartile range (25th to 75th percentiles) of the y-axis values for the logarithm of the number of samples used in the optimizations for DRE.
44

---

Published as a conference paper at ICLR 2025
E FURTHER DISCUSSIONS RELATED TO THIS STUDY
In this section, delve into further discussions related this study. First, compare the upper DRE bounds derived in this study with those reported in previous research. Next, we provide remarks on Assumption 3.3 highlighting its differences and similarities with related assumptions in prior work. Finally, we discuss the potential applications suggested by the findings of this study.
E. COMPARISON WITH EXISTING DRE BOUNDS
We now compare our Lp upper bound, as presented Equation (4) of Theorem 3.5 to known DRE bounds from other methods.
The terms related to data dimensionality in our upper bound are tighter than the existing non- parametric minimax upper bounds in DRE. Furthermore, prior work has included term compara- ble to ours that involves the exponential of the KL-divergence, as shown Equation (6) of Theorem 3.5
Nguyen et al. 2010 presented a minimax upper bound rate of O(1/N * for the Hellinger distance between the true and estimated density ratio, obtained by optimizing KL-divergence loss function. Since the Hellinger distance serves as an upper bound for the total variation distance (Sason Verdū 2016), the result from Nguyen et al. (2010) provides upper bound the Lı error in DRE using the KL-divergence loss function. Kanamori et al. (2012) proposed an upper bound of O a+d for DRE using kernel unconstrained least-squares importance fitting (KuLSIF), their proposed DRE method. Under an assumption on the 3-Hölder continuity of the probability ratio function, Kpotufe
(017 presented upper bound of (log N/N ) for DRE using empirical distribution-based estimator, where our case corresponds to 3 = 1. A recent study (Lin et al. 2023) provided L and
L2 error upper bounds of O(1/N अंअ) in DRE for estimator using the M-th nearest neighbor, as M increases along with the sample size.
In terms of comparison with our Lp lower bound, minimax L1 lower bound of O(1/Nzta) for example, was provided by Lin et al. (2023). This lower bound is larger than our lower bound in Equation (5) in Theorem 3.5 and appears tighter than ours. However, minimax lower bounds may not represent the true lower bounds and cannot directly compared to our lower bound, as discussed in Section
E.2 REMARKS ON ASSUMPTION 3.3 AND RELATED ASSUMPTIONS IN PRIOR WORK
In the following, we provide remarks on Assumption 3.3 by comparing it with related assumptions in prior work.
An assumption closely related to Assumption
3.3 can be found in the pseuudoself-cconcrrdancc
assumption guarantees that the original loss function smooth and strongly convex proportional to its second derivative, Assumption 3.3 ensures these properties only for the expectation of the loss function.
property of losses introduced by Baahh (2010) While the geeudo-seff-conorddae
First, we briefly review the that follows from it. Bach (2010) introduced the following pseudo-sell senddo--elf-ooe concoraaee assumption.
assumption and a key property of loss functions
Assumption E.1 (Pseudo self-concordance). For any u and for any r e IR, the loss g(u) satisfies (g" + r) < R r² .g"(), for some R 0.
According to Proposition in Bach 2010), under Assumption E.1 have, for sufficiently small To > 0,
+r) g((u+r) ("(
("
Rr
e.r -rr² for 0 < < To.
(169)
"In our discussion, we consider the pseudo-self wwwpseeeee-oooddnneeeeo assumption only for loss functions defined on one-dimensional variable, whereas Bach (2010) introduced it for loss functions in multidimensional domain. For precise formulation, please refer Propositions and in Bach (000).
45

---

Published as a conference paper at ICLR 2025
Now, let Gu(r) (g(u+r) g(u))//"(uu) From Equation 169
1 (r(r) - for <<r<
(170)
L
where I. R.
Therefore, the woaudd--ee--oonorrdade property implies that Gu(r) is both L-smooth and 1/L- strongly convex on any interval of fixed length ro- with independent u. This property is considered a key characteristic of loss functions under the seauddo-elf-cooccrdanncc assumption.
Next, we discuss the properties of the loss function derived from our assumptions. Theorem C.9 the appendix characterizes the local convexity of the loss function follows:
dQ dp (x)
dQ dP
1 -" 8" (dp(x))
(de dP
dP du
1/
+
r:x
(x):x
x
(x)
x² (
(171)
Additionally, from Lemma C.8
dP (x):x) =s" (dQ (x) (
dQ
dP
du (x),
(172)
where
d²
7y (u;x) = dr2 I (u r;x)
From Equations 1171 and (72).
as r 0.
dQ dP (x)
+ rr '
-7, 2
AP (x):x
x²
+ 0x (1),
(173)
(x);x)
2
where ox (1) denotes quantity that converges to 0 as r + 0, though not uniformly in x; that is, f(r) (1) and only if, for every O, there exists 8x > (depending on x) such that [f(r) < = for all 0 < &x.
Now, let Gu(x) (r) [Tx(u(x)+ (Txx))((((((())) (x(x)) x)3 (x(x); where u(x)= ddQ/dP(xx) From Equation (73). we have, for some ox > 0 and Lx 2
("(x)())
Lxx for 0 < 8x,
(174)
Tix
where &x > 0 and Lx 2 are determined at each point E Ω. Because 6x and Lx depend on x. Equation [14 does not imply that Gu(x)) is L-smooth or 1/ L-stronngl convex on any interval of fixed length.
However, taking the expectation with respect to μr on both sides of Equation
171 yields
7,
+r
Ep
i,
dQ dP
(x);x))
)
=
2
1
Ep
s"
dQ
dP
x2 + (175)
From Equation 175).
we have
d²
dQ dP
11 r-
dQ
Ep
(x) (x) + r;xx
Epp
8r
(176)
2
dP)
Thus,
22
o (r²)
G(r)
(177)
2
Ep
f"
dQ dP
where
Ep I
dQ
dP
x
r:x
Emp
dQ
dp (x):
G(r)
d² dr
E
dQ (x) + r;x)
r=
46

---

Published as a conference paper at ICLR 2025
From Equation 177
deduce that, for some L and ro 0.
1 Σ - (r) for <<<<ro
(178)
Equation (178) implies that the expectation the loss function is locally both smooth and strongly convex, with magnitudes proportional to its second derivative. In contrast, under the pseudo-self- concordance assumption, the original loss function is guaranteed to possess these properties (see Equation (170)..
In summary, under Assumption 3.3 the expectation of the loss function exhibits the same local smoothness and strong convexity properties (proportional to its second derivative) as those guaranteed by the pseudo-self-comee comooooodeeeeoooooccccceeeeceeee assumption.
Furthermore, note that the expression
(dQ/ in Assumption 3.3 resembles the Fisher
information when f'u) = log u, as shown Equations (175) and (176). Thus, as an alternative perspective, we propose that Assumption 3.3 establiisss information--heoreiii bound for estimation using f-divergence optimization.
E.3 APPLICATIONS OF THIS STUDY
In this section, we provide a brief discussion of potential applications highlighted by our findings. The following two key applications can be derived from our results.
Selecting a benchmark index for evaluating DRE methods. When evaluating the accuracy of DRE methods using synthetic datasets, the root mean squared error (RMSE) mean squared error (MSE) is recommended over the mean absolute error (MAE). Prior works did not carefully consider the differences in their behavior with respect the KL divergence of the datasets. For example, Kimura & Bondell (2024) used MAE, whereas Kato & Teshima (2021 used MSE.
Fitting the distribution of base noise for f-GAN and Normalizing Flow. The optimization of f- GANs (Nowozin et al. 2016) could benefit from adjusting the base noise distribution to better match data. Since the optimization (Uehara et al.) 2016), the accuracy of generative models could be improved by fitting the base parametric models to the data terms of KL divergence minimization (i.c., likelihood maximization).
f-GANs is equivalent to DRE by optimizing the f-divergence
similar approach could also be applied the base models in Normalizing Flow (Papamakarios
et all 2021)
47

---

Published as a conference paper at ICLR 2025
Table 2: List of (o) and (f) in Equation (1 together with convex functions, discussed
in Section 2.2 Part of the list of divergences and their convex functions is based on Nowozin et al. (2016).
Name
convex function f
f(())
(*(((())
KL
log (u 1) 2
log (d) + 1
Pearson x²
2 2.6-1
8²
Squared Hellinger
(Vū 1)²
1- 1-/2
61/2 1
GAN
log
(u + 1) log (u + 1)
llog (1 + +--1)
log (1 + ②))
48


Reviews:
[{"review_id": "WQORncryUm", "reviewer": "Reviewer_HPRf", "summary": "This paper establishes L_p​ error bounds of the density ratio in Density Ratio Estimation under f-divergence loss. The bounds scale with $N^{-1/d}$ and certain p-Renyi divergence, but is independent from the specific choice of fff-divergence.", "questions": "How do these bounds compare to other known bounds in DRE or related density estimation methods?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The problem of uncertainty quantification in density ratio estimation is an important fundamental question. This work contributes a new understanding of its theoretical limits by deriving L_p​ error bounds of the density ratio. The nearly matching upper and lower bounds are a strong point, and the independence on the specific f-divergence within the loss function is also intriguing.", "weaknesses": "The bound’s dependence on $N^{−1/d}$ means that in high-dimensional spaces (where d is large), the error bound becomes practically useless. There is also a lack of downstream application or implication of the theoretical results. As a whole, this raises questions on the meaningfulness of the bounds. \n\nThe experiments presented exhibit high variance, which limits the interpretability and robustness of the empirical validation.", "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": "QUwR3oXFzg", "reviewer": "Reviewer_mVFa", "summary": "* The paper provides new upper and lower bounds on the Lp errors of a specific density ratio estimator. (Equations 4,5, and 6).\nThis estimator is constructed by minimizing an f-divergence based loss function. \n\nThese bounds provide new insights about how the dimensionality of the data, and the KL divergence between the distributions affect the error of the estimator.", "questions": "* Equation 5 (the upper bound) contains the expectation operator on the left-hand side. This expectation is missing from the lower side (Eq 4). Is it a typo?\n* In Equations 4 and 5, is it possible to create bounds for dimensions 1, and 2 as well?\n* The upper and lower bounds are only derived for a specific density ratio estimator. Is it known how the convergence rate of this estimator compares to other density ratio estimators?\n* How can we use these theoretical results in applications?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* As far as I know, the derived lower and upper bounds on the density ratio estimator are new.\n* The paper is well-written, and easy to follow.\n* The presentation is clear.", "weaknesses": "The theoretical results are interesting. \nIn my opinion, what is missing from the paper is to show that these theoretical results can make a difference in some important applications. The paper contains a nice list of motivations for density ratio estimation, but the experimental section only contains some simple toy problems, and therefore the impact of the theory in real applications is not perfectly clear.", "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": "p7gU64HAp1", "reviewer": "Reviewer_tzbe", "summary": "The paper proposes an approach to density ratio estimation based on $f$-divergences. This idea originated in a paper by Nguyen, Wainwright, and Jordan, who introduced this methodology, which also forms the foundation of generative adversarial networks (GANs). The dual representation of the $f$-divergence involves optimization over a function space, where the optimizer—obtained, for instance, using a neural network—provides an estimator for the likelihood ratio when evaluated on samples. The consistency of this estimator was established in Nguyen et al., and various convergence results have been proved over recent years. The main contribution of this paper is to provide upper and lower bounds on the $L^p$-error, assuming both measures have compact support and that the log-likelihood function is bi-Lipschitz. These bounds are the first of their kind.", "questions": "+ Can you explain why the choice of $f$ in the divergence does not matter?  Does it only change the constant? \n\n+ What are the implications of your results on the analysis of GANs?\n\n+ What are the implications of your results neural estimation of $f$-divergence (see e.g. the recent https://jmlr.org/beta/papers/v23/21-1212.html)?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper is a novel and original contribution to the field of density estimation and highly relevant to recent advances in generative modeling (for example through generative adversarial networks). To my knowledge this are the first $L^p$-error bounds in this context. \nThe proof of the result is very clever and relies on a representation of the $f$-divergence (called the conceptual loss function) which provides access the density ratio.  The estimates are then obtained using a \"nearest neighbor\" approach and by showing that the conceptual loss function and the real loss function are close to each other.  I believe that the techniques of proofs will find other applications where $f$-divergences are used (e.g. in generative modeling).  I found the presentation of the results to be excellent  both, conceptually, in the main text and, technically in the supplementary material.  Also notable is that this result is practical as the implementation of the estimator is totally straightforward using a neural network architecture.", "weaknesses": "+ There is a very unfortunate typo in the informal theorem 3.5 where in the lower bound  $(1-p)$ should be $(p-1)$.   \n\n+ An explanation of why the result does not depend on the $f$-divergence should be provided.  I believe this is because of the Lipschitz assumption on the log-likelihood and the compactness of the support. In that way the behavior of $f$ at $0$ and at $\\infty$ are irrelevant. \n\n+ Some head-to-head experimental comparison with other density ratio estimators would have been helpful.", "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": "Ed4rtpnK0Z", "reviewer": "Reviewer_eBZV", "summary": "This article presents an analysis of error rates for density ratio estimation (DRE) in the context of $L^p$-losses applied to $f$-divergence minimization. The study derives upper and lower error bounds, noting that these rates increase with \\(p\\) and exhibit the curse of dimensionality. Theoretical findings are supported by numerical illustrations, which help validate the proposed rates.", "questions": "+ Are conceptual reformulation presented in Section 4.1 and the nearest-neighbor-based approach in Section 4.2 widely used or newly adapted in the paper?\n+ How does Assumption 3.3 relate to the pseudo-self-concordance of losses as discussed in [1]?\n+ Could the proof techniques introduced here be compared to those used in [1, 2]? Is the presented approach more general than these prior works?\n + Can the derived rates with respect to sample size be directly compared to those established in the literature?\n\n[1] Zellinger, W., Kindermann, S., and Pereverzyev, S. V. \"Adaptive Learning of Density Ratios in RKHS.\" Journal of Machine Learning Research, 24:1–28, 2023.\n\n[2] Menon, A. and Ong, C. S. \"Linking Losses for Density Ratio and Class-Probability Estimation.\" International Conference on Machine Learning, pp. 304–313, PMLR, 2016.\n\n----------------------------------------------------------------------------------------------------------\n**after the rebuttal, I raised my score to 5**", "limitations": "", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "Problem is interesting. The proofs seem to be correct. Numerical illustrations support the theoretical findings.", "weaknesses": "While the work appears mathematically sound and introduces some interesting proof techniques, I am not inclined to recommend acceptance at this stage, primarily due to the following points:\n\n- **Lack of Comparison with Recent DRE Literature**\n    The paper would benefit from a more thorough comparison with recent work in DRE estimation, particularly research involving divergence-based losses. It is, at the current stage, not possible for me to set the results into the context of the large field of DRE (see questions).\n- **Context for Techniques in Sections 4.1 and 4.2**\n    The conceptual reformulation presented in Section 4.1 and the nearest-neighbor-based approach in Section 4.2 would benefit from contextualization. Comparing these methods with existing approaches would clarify their originality and contribution to the field.\n- **Practical Applicability of Assumptions**\n    The main results rely heavily on the Lipschitz continuity of both the function class used and the energy function of the distributions. However, ensuring these assumptions in practical settings may be challenging. This reliance makes the interpretability of the bounds somewhat limited and may constrain practical applicability.\n- **Interpretability of Practical Implications**\n    It remains unclear what practical conclusions can be drawn from the theoretical results. For example, are there implications for algorithmic design that might mitigate the curse of dimensionality or handle large sample sizes effectively? The implications of error rate growth with respect to $p$ should also be discussed.\n- **Minor Issues and Clarifications**\n    The parameter $N$ in Theorem 3.5 is undefined. It should be clarified in what sense equation (4) holds---is this with high probability?", "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)