An Error Analysis of Deep Density-Ratio Estimation with Bregman Divergence
Authors: Siming Zheng
GUOHAO SHEN
Yuling Jiao
Yuanyuan Lin
Jian Huang
Venue: NeurIPS 2022 Submitted (2022)
Keywords: Curse of dimensionality
error analysis
KL divergence
telescoping density ratio estimator

Abstract: We establish non-asymptotic error bounds for a nonparametric density-ratio estimator using deep neural networks with the Bregman divergence. We also show that the deep density-ratio estimator can mitigate the curse of dimensionality when the data is supported on an approximate low-dimensional manifold. Our error bounds are optimal in the minimax sense and the pre-factors in our error bounds depend on the dimensionality of the data polynomially. We apply our results to investigate the convergence properties of the telescoping density-ratio estimator (Rhodes et al., 2020) and provide sufficient conditions under which it has a smaller upper error bound than a single-ratio estimator.

An Error Analysis of Deep Density-Ratio Estimation with Bregman Divergence
Anonymous Author(s)
Affiliation Address email
Abstract
We establish non-asymptotic error bounds for nonparametric density-ratio estima- tor using deep neural networks with the Bregman divergence. We also show that the deep density-ratio estimator can mitigate the curse of dimensionality when the data is supported on an approximate low-dimensional manifold. Our error bounds optimal in the minimax on the dimensionality of the data polynomially. We apply our results to investigate the convergence properties of the telescoping density-ratis estimator (Rhodes al., (220)) and provide sufficient conditions under which it has a smaller upper error bound than a single-ratio estimator.
2
and the pre-factors in our error bounds depend
Introduction
10
11
Density-ratio estimation is key importance various statistical and machine learning problems
(Sugiyama et al. 2011bb Kato & Teshima 202T). There is vast literature on density-ratio estimation due to its wide range of applications. such as discriminative analysis (Silverman, 1978, Cox & Ferry
13
1991), covariate shift adaptation (Sugiyama et al.) 2008 Tsuboi et al.) 2009). two-sample testing
15
Qin 1998 Sugiyama et al. 201T), energy-based modelling (Gutmann & Hyvärinen 2012 Ceylan & al. (0166), and mutual information estimation (Moustakides & Basioti 2019 Rhodes et al. 2020). among others.
Gutmann 2018), 8), generative learning (Goodfellow al. |
17
Let Zy and Zp 2 [] be two random vectors with probability density functions g and p', respectively. Given independent and identically distributed (i.i.d) samples {7g.i from qº and
20
(2 1 from p", basic problem is to estimate the density ratio
Rd (z) = (2))
21
naive estimator of R' is q/D. where q and و are the density estimators of q" and p", respectively. However, such estimator be highly unstable. Moreover, density estimation itself is diffi- cult problem, especially in the high-dimensional settings. For example, kernel density estimators 1962) works well when < but deteriorate dramatically as d increases. To avoid density estimation, various methods have been proposed to estimate the density ratio Rt directly, including the density matching approach (Sugiyama al. 2008 Tsuboi et al. 2009) Yamada
29
24
(Rosenblatt 1956 Parzen
25
26
& Sugiyama, 2009 No00/eNuuyer Nguyen et al.) 2010, Yamada et al. 2010), the moment matching approach (Qin al. 2012b), the density-rain fitting approach (Kanamori et al. 2009 2012a), and the unified density- density-ratio matching approach under Bregman divergence
27
28
1998 Gretton et al. 2009 Kanamori
29
30
framework (Sugiyama et al.) 2012a). Impressive empirical successes of using deep neural networks
31
in density-ratio estimation have been reported in some recent works (Moustakides & Basioti] 2019) Rhodes et al. 2020). Moreover, Kato TTeshima (202T) studied the convergence properties of deep density-ratio estimation under modified Bregman divergence criterion.
32
33
Submitted to 36th Conference on Neural Information Processing Systems (NeurIPS 2022). Do not distribute.

---

34 In this paper, we study deep density-ratis estimators with the Bregman divergence as the criterion. We apply our results construct an estimator for statistical inference for the Kullback-Lieble divergence. We also study the theoretical properties of the telescoping density-ratio estimator (Rhodes et al.
35
37
2020) based on our results.
38
Our contributions are as follows:
39
1. We establish non- non-asymptotic error bounds for the density-ratio estimator using deep neural networks under the Bregman divergence (BD,Brremmai (967). and provide neural network architecture for the estimator to achieve minimax optimal rate Op (n (2))()))))) where n = min (2g. np and [3 is smoothness parameter of the logarithmic density-ratio function; see Subsection 3.2 for details;
41
42
43
2. We show that deep density-ratin estimator with the Bregman divergence criterion is able to mitigate the curse of dimensionality when the data is supported on an approximate low-dimensional manifold: see Subsection 3.3
45
48
3. We apply results to study the convergence properties of the telescoping density estimator (Rhodes et al. 2020) and demonstrate its advantages over single-ratio estimators under certain conditions.
48
Notation. Let min m mp be the smaller sample size between the two samples {Z i=1 and { 1 1=1 In addition, || ol denotes the sup-norm some specific domain, and C, Co are 52 generic constants that may vary from place to place. For any measurable function f. we denote (115 IIflll...) where |l = f2) and [| E,, E,, (Z() (1/n,) E (Z( p.g. 54
51
Ilf mnxx = max Ipp Il [1g) and Ilffl
53
Density-ratio estimation
55
In this section, we first present the density-ratio estimation problem using the Bregman divergence 57 (BD, Bregman 1967) and then describe the structure of the deep neural networks to be used in density-ratie estimation.
59 Let vp + IR be first-order continuously differentiable and strictly convex function. Define
(x v) xxx) (b)) - + (x)((xx y),
80 where v/ is the derivative of tb. Then, the convexity of 1 implies that (a, 2 and the equality holds if and only if = y. follows that Ep. Ay (R' (Z), R R(()) 2 0 and the equality holds if and only if R = R Therefore, the target density-ratin ratio R 9" //p can be characterized minimizer:
81
R E
arg min nonnegative and measurable
Ep A (R' (Z),
83 We verify in the appendix that
Av (Z), = Epr (T-((R(())) - (((())) Eg (v) E
Since the last term the right side in ①1 Eg. [v) [R" (Z)) is independent of R, we have
Rs E
arg min I nonnegative and meusurable
Ep- ( (RZ)) - (R(Z)) - Eg (V' (R(Z)).
(2)
Hence, for any measurable function R: Z + R. the BD score induced by for estimating the target 66 density-ratio Re = =q" 00"p"" is B& E.p (R a (R())) Feg (R()))
(3)
where ef is the derivative of v/ (Sugiyama et al. 2012a bj. Then, R² is the minimizer of (R) over 68 all nonnegative measurable functions.
Because density ratio is always nonnegative, a nonnegative constraint needs to be considered when 70
defining the density ratio as minimizer, as in (2). This makes the minimization problem more difficult to solve. To avoid the non-negative constraint of the density ratio, we first consider the

---

72 density ratio D := log R". Then the nonnegativity constraint is no longer needed and by (2. we
73 have
D E arg min (x(exp(D)).
D measurable
74 In practice, the estimation of R" can be based on empirical version of By when random samples
75 from p" and q" are available. Suppose we have samples (Zq i..d. qº and {Zps وب=1 i..d. p'.
78 We estimate D* by
D arg min (e DEF
(4)
77 where Fn class of neural network functions and (e is an empirical version of B (e
defined in 3 which can be written
B)(ee)=
Σ
(D((2))))
Σ (2n.))
Thp j=1
ng 1=1
79 where
(t ('' (eee)) and C2(t) -b'
(5)
The density-ratio estimator is R R= cxp
81 We take the function class Fr to be M.D.W.WU.s. class of ReLU activated feedforward neural
networks (FNNs) So : Ied + R with parameter 0, depth D. width W, size S, number of neurons
82
U. We require that [o < M for some 0 < M < co. There are D hidden layers and (D + 1)
84 layers in total. The width W the maximum width of the hidden layers; the number of neurons LA defined as the number of neurons of fe: the size S is the total number of parameters in the network.
86 Note that D, W.u, S may depend on n, but we suppress the dependence for notational simplicity. We write FM,D.W M4 JFNN for brevity.
86 3 Theoretical results
89 In this section, we first study the error bounds for the deep logarithmic density-ratio estimator. The bounds for the density-ratio estimator follows directly based on the properties of the exponential function. We also show that deep density-ratio estimator can mitigate the curse of dimensionality when data supported on an approximate low-dimensional manifold.
90
91
92
93
3.1
General error bounds
94
To state assumptions and results, we need the definitions of p-smoothness, o-strong convexity and pseudo dimension.
95
96 A function f IR + R is said to be p-smooth over set A C IR if differentiable over A and its first-order derivative f' satisfies
97
('(z) - f')] S p/æ y/. x. y A,
(6)
98
where 0 S μ < co. The constant 1 is called the smoothness parameter.
function f: R. R is called -troongyy convex if the domain dom()) of f is convex and for any dfm(f) and x E [0. 1], satisfies
39
100
f(Ar + (1 A)y) s
- = X(1 211- 1) -
where 05 < co. The constant is called the strong convexity (SC) parameter.
102
For a function class F, its pseudo dimension denoted by Pdim (J), is the largest integer B satisfying
that there exists (x1, .22,... ... ..,
,B, y1, (0. 1) there exists an / E J satisfying for any E {1,2, B} f(x)) > B $ r (Anthoy Bartlett et al. 2019).
3/,.... yy) , E 2 R such that for any (r1.72, rn)
104
& Bartlett 1999
3

---

Table 1: Commonly-usee Loss Functions
Name
(c)) (c- 1)2
Domain R
Smooth Parameter μ
SC Parameter
LS
2
LR
clog + log(e+1)
[a. (-1 b (0<55
1
caa+1) 1
5(++1 1]
KL
cloge-4
h
Remark 1. For any measurable function class F, by the definition of VC dimension, (F)im(FF & Pdim(F), F is the class of functions generated by ReLU FNNs, it follows from Theorem 14.1 of Anthony & Bartletl (1999) that PFim(F) S VCdim(F), Hence, for the function class F generated by ReLU FNNs, Pdim(F)) = VCdim F.).
107
109
110
We make the following assumptions.
Assumption 1. The function vo is y-smooth & a-strongly convex, that is. it satisfies (6) and (
111
Some uuse vé's satisfy Assumption 1 see Table for some examples.
Assumption 2. There exists a constant 0 < . < oc such that |D S M, D1loo S M for
113
114
every D E FNNN.
115
Assumption 2 assumes that the target density ratio is bounded. Such an assumption is often made in nonparametrie statistics for avoiding technical diffieulties associated with dealing with unbounded functions. We will partially relax this assumption below. The finite M in Assumption 2 can be relaxed to M = Olog log n) a small price of additional logarithm term in the error bounds. The boundedness of network can be achieved by clipping operation. For example, let
117
118
119
120
(t) MI(t < M1 + f < M) MI M) be the truncation function taking M)} can be computed by ReLU network with depth and width 4. Hence, through network concatenation, we can construct some bounded ReLUU FNNs and such boundedness assumption can be satisfied.
values in [-M, M]. then (tt)= = ((t))o(a(t)) - M) (o(-t)-o(a(tt)
122
Define the best in class approximation of D' in JINN DNN arg mig Denote
|
D D max-
125
Pdim (FeNn) logn
S.
(8)
n
126
Theorem 1. Suppose Assumptions 7 are satisfied, When n > Pdim(FPNN), there exists constant C' depending on (p, o, M) such that for any y > 0, with probability at least 1 - exp(-7))
127
D D' SC E.. + 1|NNN
D' D'Ilmax 1
2
and
| D' lmpiing
En D| - DmIlmax v2 $ 20
m2
We have the following corollary for the expected error.
130
Corollary 1. Under the conditions of Theorem (p, o. M), such that
? there exists a constant Co depending only on
131
Epr .r- 110-11122 S Co (5h + || D*112ax))
132 and
Ep. xr D012 mg... 2C ( DNNN 11
133
The above results are obtained under the boundedness Assumption 2 While such an assumption is
134
often made in the error analysis of nonparametric procedures, somewhat restrictive in density- ratio estimation problems. For example, this assumption may not be satisfied in the presence of
196 the density-chasm problem, i.e., the gap between two densities is large (Rhodes al. 2020). We
establish an error bound result with the following partially relaxed assumption.

---

138
Assumption 3. There exists a constant 0 < M < oo such that (2) 2 - M for every 2 E Z and | I M for every D E FFNN.
139
140
This assumption does not require the target log-density ratio D to be bounded above. Denote truncated versions of D' and R by
(²) = D*
M) M1(" 2 M), 1 e (z) 2 e
Ri (z) (2) =
142
where 0 < M < and 1 is the indicator function. We establish non-asymptotic error bound involving the truncation error.
143
144 Theorem 2. Suppose Assumptions ! and 3 hold. When > PdimmFFFNN) there exists two
145
constants C depending only on (μ, o, M) and Co depending only on (Jr, O), such that
Ex- 11D1I D" - Coe2M || RRM + C
En
inf |D - DEFRN
JD-Dirlly Dirlle)
148
where& En is defined in 8
147
The term || - RM 1| is the truncation error for an unbounded He and the unboundedness also leads to the term S., = [Pdim(FrNN) (log (llog)/mm) n)/n]1/2 in the error bound, which is greater than 5% in the bounded case. However, because no boundedness assumption needed in this theorem, we can
148
149
150
apply it to study the convergence properties of the telescoping density-ratio estimator of Rhodes et al. 2020) in Section below.
151
3.2
Non-asymptotic error bounds
By Corollary [ it suffices to bound the estimation error Pdim(Frux) log n/n and the approxi- mation error [TNN D* ma It follows from Theorem 6 in Bartlett et al. (2019) that, for
153
155
FINN = F.,DDWW..S there exists a universal constant C2 such that Pdim S C2SD log S.
156
To control the approximation error |NN D' 1 we assume that D belongs to the Hölder class H. ( 1]d, M) with 3 = k + where & E N+ and a E (0, 1]. where N+ the set of positive integers.
157
Definition (Hölder class). Hölder class H 1] , M) with B k a where N+ and E (0, 1] consists of function [] R satisfying
159
160
10 fzz - 8 f(v)
max 0 flloo: max max ||ai]]s = zz
M,
|alliSA Sk
x 111
where ||]|| -' a4 and 0 8m y for a (a1, 02.......... ad) E
We use Theorem 3.3 of Jiao et al. (2021) to control the approximation error || DNN D' For convenience, we include this result the following lemma.
162
163
184
We specify the width W and depth D as follows. For any K, E N+
W = 38(L3] +
21([3) + [1o,
(9)
165
where [a] is the smallest integer no less than a.
186
Lemma 1 (Approximation error). Assume f E H. ([0, 1]dh M) with = k and a E (0, 1]. Then there exists a function do implemented by ReLU network with width W and depth specified in (9) such that
where N
187
188
1f- S 18MCg(KL)- -8
sup tE(0.1]HHHa
where C3 = (13) + 1)2 H uf = [x] ......,aal : x; E
189
-P (b/B 8, b/B) for = (KL) (0, 1/(3B) and a b = max (a, b).
170
Furthermore, W = 38([3] + 1)2 + log, [,L) = 21( + 1)2 [log, + 2d,
171
then
// f S 19MC (KL)
sup
xE|o,1]
In this uniform approximation result, the width W is required depend on d exponentially.
5

---

The following theorem gives an error bound for D.
174
Theorem 3 (Non-asymptotic error bound for D). Suppose that Assumptions / are satisfied, 176 D E H ([O, 1] M)) with 3 = k + a where & N* and a E (0, 1]. and FENN is the function class of ReLU DNNs with width W and depth D specified in (9. Then, for M and 2 Pdim(FFNN)
178 we have
Egy a- | D
sc + +((K))
where C1 = (18) + 1) 2)3)213))( and the constant C depends only on (H, a, M).
179
Furthermore,
W 11=114(13]+ 1)) =21[13]1]] 1)2 n Nा
loga S(azze )
181 then
Ey',' D D' I Co[[[]] + 1) 100 where the constant Co depends only on (,,o,
4428
(10)
182
The convergence rate in (T)) is optimal. This can be seen by considering a density estimation problem {Z J from an underlying unknown density qı on [0, 1jd. To estimate U1 we sample referencing observations 1 with m, Z map from a uniform distribution 185
184
with i.idd observations
Uni 1]9) whose density 21 = 1. Thus, estimating the density ratio / is equivalent to
186
estimating Q1- According to (4). we obtain the estimator @ of qı. log 9 E H ( 1]", .M) where
187
k with is E N and a (0, 1]. neural estimator based on the network structure specified
189
in Theorem 3 satisfies
Ep ف|
91 ll I C
+ 11)08
(1I)
190
Tsybakov 20088) showed that for a density belonging to the Hölder function class, the optimal minimax rate of the density estimation is Op mm -2) Hence, our estimator achieves the
191
optimal minimax rate.
193
In addition, the existing error bounds usually contain a prefactor depending on the dimension d exponentially, e.g. 2 (Devroye & Lugosi| 1996). Such prefactor can be very large even for moderately large d, which severely degrades the quality of an error bound. The prefactors in our results depend on d only polynomially and are much smaller than those in the existing bounds.
194
195
196
Under Assumption 2 to derive a nonasymptotic error bound for the don-density ratio estimator R, we note that
197
196
Flr .-- ||
R 12 S Se2 a 11 D*1 1
Thus bound for R follows directly from bound for π.
200
Remark 2. Appendix A.2 contains some examples of p" and q" such that D = =log(9') /p*) e
H ((0, 1]d, .M).
201
202
The hypercube [0, 1]dd assumption for the density ratio made for technical convenience. With an unbounded support, we can bound D| - D' using truncation technique under some suitable additional assumptions, at small price of an additional loga- rithm term in the error bound. Specifically, suppose the pdfs are supported on Rdd In addition to Assumptions 1-2 and the Höilerr class assumption in Theorem 3, we need to further assume 20 (n) S n. 4442, For I p q. and any D E FFNN, where FFNN is the function class of ReLU FNNs with width W and depth D specified by
Remark 3.
203
204
205
206
that max [(] Zlloo log Eyg E(I
208
W 111(11 + 112110111 D = == + +1²
mra log,
(8n (Snzatza )
209
we have
| DI S
1) (2log 2133)
T120
28
210
Compared with the upper bound of the approximation error Theorem 3, when the pdfs are supported on Red (unbounded case), we can derive similar approximation error upper bound with an additional logrithmic factor (2 log n) 2131, The details are given in Appendix A.3
211

---

213
3.3
Circumventing the curse of dimensionality
214
In many modern statistical and machine learning tasks, such as image processing and text analysis, the dimensionality d of the data can be high, which results in very slow convergence rate even with a large sample size. This is known as the curse of dimensionality. Nonetheless, the data in various applications has been demonstrated to be supported or approximately supported in some subspaces or subsets with low intrinsic dimensionality (Nakada & Imaizumi 2020). For regression problems, Nakada & Imaizumi (2020) have shown that DNNs can adaptively estimate the regression function through the low-dimensional structure of the data, and the resulting convergence rates no longer depend on the nominal high dimensionality d of the data, but on its low intrinsic dimension.
216
217
218
220
222
Motivated by these advancements, we assume that the data is concentrated on an approximate compact Riemannian submanifold M with the Riemannian dimension dM < d.
Assumption 4. The target log-density ratio D E (H,, 11", M) with 5 = k + where E N and a E (0, 1), and the data from the densities p" .4" are concentrated on a set Mp S [0, 1j
224
225
226
defined as
Mp = for E [0, there exists y E M, | | S p):
227
where M is a compact dm ddy-diimensooal Riemannian submanifold and p E (0.
228
Theorem 4. Suppose Assumptions 1
2 and 4 hold. Suppose that D E (H0, 17 M) with
229
3= k + N+ and a E (0, 1f FFNN is the function class of Rel.U FNNs with width and depth
W = 38([3] d) [8] +1 L. (.
21([3] 1)8 K [1K2)88))1
where K, E N+ and do 0 (dm log( (og(d/))88)) < d, then when M 2 1, n > Pdim(FFNN) and
230
(KL) 2.
p s (18] +
231 we have
Fip . 11 D7 11 SC(1 - 50-22
23 [
C2( 42
232 where the constant C only depends on (1, M), C2 (18) 1) 2 (00+0v and En is
233 defined in (8.
By Theorem if we set W = 114(11]1+++00111111 1) 181+1 D 21([8] + 1)² [nss logz (8nSi)], with
SB ds/ (2/()( + 23)), then
28 FØr 11 D' SCoC3(1 -28 dg+
(12)
236 where the constant Co only depends on (H, o, M) and C3
(1$)
237 1) m 233+3 ( do (0+(0V1) The convergence rate n -228/(de+28) in 12) only de-
238 pends on ds < d, instead of the ambient dimension d. Therefore, Theorem shows that a low-dimensional Riemannian manifold support assumption can alleviate the curse of dimensionality.
4 Error analysis of the telescoping density-ratio estimator
240
When the difference or the 'gap" between two densities is large, single-ratio estimation method may perform poorly. This is referred to as the the density-chasm problem (Rhodes et al. 2020). To alleviate this problem, Rhodes et al. (2020) proposed an approach called Telescoping density-Ratio Estimation (TRE). This approach first gradually transports samples from q" to samples from p'. creating a chain of intermediate datasets, then estimates the density ratio between consecutive datasets along this chain. The chained ratios are combined via a telescoping product which yields an estimate of the original density ratio. The experiments conducted by Rhodes et al. (2020) demonstrate that TRE can yield substantial improvements over existing single-ratio methods for mutual information estimation, representation learning and energy-based modelling.
242
2M4
246
248
249
250
We now provide a theoretical analysis of TRE, which partially explains why TRE performs well. For notational simplicity, suppose np ng = below.
7

---

252
For h = 0, .......y. K, Rhodes et al. 2020) constructed chain of intermediate samples connecting
q" and p" by setting ZE. = (1 ax ))) Zg. + a4 Z.d. i = L,...,,,, n, where 0 = ao < a1 < ....
253
254
a--1 ak- 1, and used these samples to build a TRE.
255
To simplity the analysis, we use a slightly different chain of intermediate samples as follows. For
k- 0, 1....... K, let
k (1 (1- -1,,,,)) + òz, Zp.. i i.......
(13)
where 6R,5, i 1, .....,,.............. n, are i.idd Bernoulli random variables with success probability auk-
258
Let gR be the density of the synthetic data Zz.; constructed this way. We have (x(2) (1- ay )4 (2)
o&p' (z), k = 1, ,...., K - 1. Therefore, the distribution of the samples from q): in the chain is simple mixture of q" and p" with the mixing proportions
260
ag and Ogg, instead of more complex convolution of two densities using the construction of [Rhodes et al. (2020). As Og changes from
262
ag to ag = 1 over a grid {ao, Ci,...,, aak C [0, 1]. the distributions of the samples in the chain move gradually from 9" to p². Let 40 q" and qK p². Then,
(=)
K-1
(=)
II (3), = 2,
(14)
(2)
254
where (=) - q;(=)/ (z). For k = 0, I, - 1, applying the neural density-ratio estimator with ) and (Z++1.] D yields estimator R, of Rt Then the telescoping density ratio estimator of R is K-1 II R
286
We consider the log-density ratio. Let D be the neural estimator of D = log(ax/uk->) Based on 14) the telescoping estimator of the log-density ratio D = log R is
288
K
DTRE
Σ
DR.
(15)
k==
289
In what follows, we show that under certain conditions, the telescoping estimator has an improved asymptotic error bound. The intuition as follows: when qu /q++1 is bounded or g (2) (2)/ 1//++11 (z) < (=()/pp (z) for E 2, where @ and 7s+1 are the densities of the synthetic data { (Zk,) 1 f==1 and 1Z respectively, the truncation error for uk/ge. //t++1 vanishes is far less than that for q" /p".
270
273
This can help the telescoping density- estimator perform better than a single-ratio estimator.
274
Assume that q² 2 C1 and c S pp < C22 where 0 < C1, C2 < 0O are two constants. Thus, D' log(a*/p") 2 log(c1/02). Therefore, Assumption 3 is satisfied. For any finite set A C R.
275
278
max A denotes the maximal value in A. Let M = log(ce/ C1) and Mo be a constant satisfying
Mo 2 max ( (2
M,
(16)
where
A
(2K) M.a = [M.1] u log
1 ak-1
1 k < K 1 log
(e 1)al + (c 1)ax + , 1
ak
278 Based on Theorem 2. we can establish an asymptotic error bound for the telescoping estimator DTRE defined in (5).. with
Dr E arg min ( (c
DEFN
where
( = 1 T
Σ L LD( + n
280 where L, and L2 are defined in ( and J consists of DNNs D with ||] < Mo To 281 demonstrate the advantages of the telescoping estimator, we also consider the single-ratio estimator
(SRE), DSRE E arg min (e))
8

---

Proposition 1. Assume that q' 2 C1. p I oz where the constants 0 < c2 < oo, and the samples {= from qº and 1- p" are independent. Then, there exists constans Co (1, a, 01) depending only on (ju, 0, 01) such that for
BsRE = e Mo Colos, 0,
RMo lpp
283
we have
lim sup Pep DSRE 17112 S BSRE,
lim sup Ep at [DrRE - D2 222 s (1 OK BSRE,
22+00
where ||ʃl|2 [2)d=] for any square functribleuunction
285
aK-1 < <K = and truncation level Mo. the upper bound for the asymptotic L2-error of DIRE is reduced by a factor (1 (xK-1) with 0 < 1 ak-1 < 1. This upper bound can be far less than that of DSRE when OKK - is close to 1. Therefore, TRE can improve the asymptotic error bound over the bound for the single-ratio method.
Proposition shows that for a given sequence 0 = ag < a1
286
288
290
important note that there tradeoff between the value of ak- and the truncation level Mo dictated by (16). For instance, with α < ... I 0K-2 fixed, the closer ak- is to 1, in view of 16.. the larger Mo is. Larger ak-1 sharpens the pre-factor (1 --K-) and larger Mo also improves R Rās, Ilp. but deteriorates the fre-factor e Mo.
281
292
Proposition is generally not applicable to the original chain of TRE. The difficulty is due to the possibly intensive oscillation of density ratios caused by the convolution form for the density of the of two random variables. We illustrate this by toy example: suppose Zup 7pp ii.d uniform random variables on [0, 1]. For any 1. E (0, 1/2). (1 1) + 1.7pp has density 1-2
295
297
298
of u [(0 I S It < ((1 - In this case, 9"' /9/ unbounded and oscillates sharply when is close to 0 or 1. This makes it hard to estimate q" /4t- However, the chain we used does not have this problem, which may be a good choice in practice.
300
Additionally, we conduct simulation studies to evaluate the performance of our proposed mixing chain and the original convolution chain; see Table 2 for the results. The simulation settings are given in Appendix A.4] Table shows that, for the models considered in the simulation studies, the proposed mixing chain performs comparably or better compared with the original convolution chain.
302
303
304
Table 2: The MSEs averaged over 10 replications and the corresponding standard errors in parentheses between the telescoping ratio estimate (TRE) of log density-ratio and its true value for the proposed mixing chain (mTRE) and the original convolution chain (cTRE) under different settings, where n is the training data sample size and K is the length of the chain. The bold one is the best in specific setting among the two estimates.
(n.
Setting
Method
(5000,5)
(5000,10)
(10000,5)
(10000,
0.9850(0.0269)
0.8840(0.0180)
(.0109(0.017I)
0.9199(0.0194)
Beta
cTRE
1.4670(0.0606)
1.2935(0.0274)
1.3674(0.0625))
1.2850(0.0293)
TRE(ours)
2.7426(0.0370)
2.8330(0.045))
2.7483(0.0367)
2.7813(0.0265)
Normal
cTRE
2.7987(0.0586)
2.7076(0.0293)
2.8184(0.0347)
2.7503(0.0297)
30s
5
Related work: comparison with the NN-BD estimator
306
There has been much work on the error analysis nonparametric density-ratio estimation (Nguyen
et al. 2010) Sugiyama et al. 2008 Kanamori et al. 2012a Yamada et al. 2013). These results show that when the targeted density-ratio belongs to certain function space H. such as RKHS, and thus
308
no approximation error is incurred, their estimators achieve certain nonparametric convergence rate

---

310
decided by the complexity of H. Compared to these works, our results consider the approximation eтror using neural network functions and still achieves the minimax optimality under some mild conditions.
311
Our work is most related to the paper by Kato & Teshima 2021), who proposed non-negative Bregman divergence (NN-BD) method to tackle the possible over-fitting problem due to the unbound- edness of certain Bregman divergences. We compare our theoretical results with those for the NN-BD estimator of Kato & Teshima (202T). Using the notation in this paper, we restate two conditions
314
315
318
317
required in Kato & Teshima (2021):
318 (a) Let FFNN be a class of FNNs with output taking values in [e M ,e,M for some finite M > 0. The target density-ratio R' E FFN Moreover, for any function in FFN. its Frobenius norm of the parameter matrix W in the jth layer is bounded by Bj 0 and the activation functions are I-Lipschitz haaitivehhomogeecuus.
319
321
(b) The function (-)- is o-strongly convex. Let (t) 8 (t) (t)) + (,((() -t()). 322
le M eM), where (t) = Crn (t)) (t). Here (t) is function bounded above, Can
323
and A are user-selected constants. Suppose (-) and (-) are Lipschitz functions on [e-M, cdl).
324
325
Under these two conditions, Kato & Teshima (202I) rewrote the BD in (3)
(R) ()))(((())) C.n (P)((()
+ (R()) + (1 C.n)
(17)
and proposed the density-ratio estimator RKT defined as
1ig (2(R(Z
up np (R((p)))
CRn
ng
RKT E arg min REFiN
(((R(Zn))){
fly i=1
nl
327 where [a]+ = max(00 a) for any E R. They showed that
RKT R'Ipp =Op
( (n- -1((22)))
(18)
for any 0 S 5 2.
According to Theorem we have the following corollary for our density-ratio estimator u = exp(D).
330 Corollary 2. Under Assumption when n 2 Pdi there exists a constant C depending
331
only on (p, a, M) such that, for any 7 2 O. with probability least 1 exp(-7))
j - R² 1 cc(
Pdim (FNN
logn
2
Corollary 2 implies that 1 (Vlogg/)) when the true density-ratio R FINN- This
332
convergence rate is slightly faster than the rate for Rxt given in (18). Moreover, the boundedness assumption for the weights of the neural network functions, as imposed by Kato & Teshima (202T),
333
334
335
is not needed. Corollary 2 also shows that, if the target ratio is assumed to belong to the optmization space (or hypothesis space). i.e.. R* FFNN without approximation error, then the convergence rate does not depend on the dimension of the data. In other words, the estimation of R does not suffer from the curse of dimensionality. However, this is probably not realistic. Therefore, it is important to consider the approximation error due to the fact that R E FR in applications.
336
337
338
339
340
6
Conclusions
341
In this paper, we have established the non-asymptotic error bounds for the deep density-ratio estimator using the Bregman divergence criterion. Under reasonable conditions, we have shown that the deep density-ratio estimator achieves the optimal minimax convergence rate. When the data is supported
342
343
344
on an approximate low-dimensional manifold, we have shown that the neural estimator can mitigate the curse of dimensionality. We have also analyzed the convergence properties of the telescoping density ratio estimator (Rhodes et al.] (020)) and provided sufficient conditions under which it has lower error bound than single-ratio estimator.
346
10

---

348
A limitation of this work is that certain boundedness assumptions on the target density ratio such as Assumption or iis needed. Also, when the boundedness assumption is partially relaxed in Assumption 3 the error bound in Theorem 2 is not as sharp as that with the boundedness assumption in Theorem would be interesting to further relax or remove such assumptions. It would also be useful to improve the error bound in Theorem if possible. These are interesting and challenging problems that deserve further study in the future.
349
351
353

---

References
354
355
Anthony, M. and Bartlett, L. Neural Network Learning: Theoretical Foundations. Cambridge University Press, Cambridge, 1999.
357
Baraniuk, R. G. and Wakin, M. B. Random projections of smooth manifolds. Found. Comput. Math., 91):51177,
Bartlett, P. L.. Bousquet, O., and Mendelson, S. Local rademacher complexities. The Annals of
360
Statistics, 33(4):1497-1537, 2005.
361
Bartlett, P. L., Harvey, N., Liaw, C., and Mehrabian, A. Nearly-tight VC-dimension and pseudodi-
362
mension bounds for piecewise linear neural networks. Journal of Machine Learning Research, 20
(63):1 - 17, 2019.
Beck, A. First-Order Methods in Optimization. Society for Industrial and Applied Mathematics, 2017.
385
Bregman, L. The relaxation method of finding the common point of convex sets and its application to the solution problems convex programming. USSR Computational Mathematics and Mathematical Physics, 7(3):200 217, 1967.
367
369
Ceylan, C. and Gutmann, M. U. Conditional Montr-Contrastive Estimation of Unnormalised Models. In Proceedings of the 35th International Conference on Machine Learning, pp. 725-733. PMLR, 2018.
370
372
Cox, T. F. and Ferry, G. Robust logistic discrimination. Biometrika, 78(4):841 - 849, 1991.
373
Devroye, L. and Lugosi, G. A universally acceptable smoothing factor for kernel density estimates. The Annals of Statistics, 24(6):2499- 2512, 1996.
374
375
Fefferman, C. Whitney's extension problem for c" Annals of Mathematics.. 164(1):31333) 1111333339930 2006.
376
Goodfellow, I., Pouget-Abadie, J., Mirza, M., Xu, B., Warde-Farley, D., Ozair, S., Courville, A., and
377
Bengio, Y. Generative adversarial nets, In Advances in neural information processing systems, pp. 2672-2680, 2014.
378
Gretton, A., Smola, A., Huang, J., Schmittfull, M., Borgwardr, K., and Schölkopf, B. Covariate shift by kernel mean matching. In Candela, J., Sugiyama, M., Schwaighofer, A., and Lawrence, N. (eds.), Dataset Shift in Machine Learning, chapter 8, pp. 131 160. MIT Press, Cambridge, 2009.
380
382
Gutmann, M. and Hyvärinen, Noise-contrastive estimation of unnormalized statistical models, with applications to natural image statistics. Journal of Machine Learning Research, 13:307-361, 2012.
383
384
385
Huang, G., Liu, Z., Van Der Maaten, L.,, and Weinberger, K. Q. Densely connected convolutional networks. In 2017 IEEE Conference Computer Vision and Pattern Recognition (CVPR), pp.
387
2261-2269, 2017.
388
Jiao, Y., Shen, G., Lin, Y., and Huang, J. Deep nonparametric regression on approximately low- dimensional manifolds. arXiv:2104.06708 2021.
309
390
Kanamori, T., Hido, S., and Sugiyama, M. A least-squares approach to direct importance estimation.
Journal of Machine Learning Research, 10(48):1391 1445, 2009.
Kanamori, T., Suzuki, T., and Sugiyama, M. Statistical analysis of kernel-based least-squares
382
383
rensity-ratio estimation. Machine Learning, 86(3):335- - 367, 2012a.
Kanamori, T., Suzuki, T., and Sugiyama, M. f-divergence estimation and two-sample homogeneity
385
test under semiparametric density-ratio models. IEEE Transactions on Information Theory, 58:708 720, 2012b.
396
397
Kato, M. and Teshima, Non-negative bregman divergence minimization for deep direct density ratio estimation. In International Conference on Machine Learning, pp. 5320 5333, 2021.
12

---

Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. arXiv:1412.6980) 2014.
LeCun, Y., Cortes, C., and Burges, C. Mnist handwritten digit database. AT&T Labs [Online].
401
Available: http://yamm. lecun. com/exab/mmist, 2, 2010.
Moustakides, G. V. and Basioti, K. Training neural networks for likelihood/density ratio estimation.
403
arXiv:1911.00405, 2019.
404
Nakada, R. and Imaizumi, M. Adaptive approximation and estimation of deep neural network with
405
intrinsic dimensionality. Journal of Machine Learning Research, 21(174):1 38, 2020.
406
Nguyen, X., Wainwright, M., and Jordan, M. Estimating divergence functionals and the likelihood
ratio by convex risk minimization. IEEE Transactions Information Theory, 56(1 1):5847 5861, 2010.
408
Nowozin, S., Cscke, B., and Tomioka, R. f-gan: Training generative neural samplers using variational
410
divergence minimization. In Advances in neural information processing systems, pp. 201 271,279,
2016.
412
Parzen, E. Estimation of a Probability Density Function and Mode. The Annals of Mathematical Statistics, 33(3):1065 1076, 1962.
Qin, J. Inferences for case-control and semiparametric two-sample density ratio models. Biometrika, 85(3):619- - 630, 1998.
415
Rhodes, B., Xu, K., and Gutmann, M. U. Telescoping density-ratio estimation. In Advances in Neural Information Processing Systems, 2020.
417
418
Rosenblatt, M. Remarks on some nonparametric estimates of a density function. The Annals of
419
Mathematical Statistics, 27(3):332 837, 1956.
420
Silverman, B. W. Density ratios, empirical likelihood and cot death. Journal of the Royal Statistical
Society. Series C (Applied Statistics), 27(1):26 33, 1978.
422
Sugiyama, M., Nakajima, S., Kashima, H., Bunau, V., and Kawanabe, M. Direct importance
estimation for covariate shift adaptation. Annals of the Institute of Statistical Mathematies, 60(4):
424
699 - 796, 2008
425
Sugiyama, M., Suzuki, T., Itoh, Y., Kanamori, T., and Kimura, M. Least-squares two-sample test.
426
Neural Networks, 24(7):735 751, 2011.
427
Sugiyama, M., Suzuki, T., and Kanamori, T. Density-ratio matching under the bregman divergence:
428
unified framework of density-ratio estimation. Annals of the Institute of Statistical Mathematics, 64(5):1009- - 1044, 2012a.
429
Sugiyama, M., Suzuki, T., and Kanamori, T. Density Ratio Estimation in Machine Learning. Cambridge University Press, Cambridge, 2012b.
431
432
Tsuboi, Y., Kashima, H., Hido, S., Bickel, S., and Sugiyama, M. Direct density ratio estimation for
433
large-scale covariate shift adaptation. Journal of Information Processing, 17(2):138 - 155, 2009.
434
Tsybakov. A. B. Introduction to Nonparametric Estimation. Springer Series in Statistics. Springer
435
New York, 2008
436
Yamada, M. and Sugiyama, M. Direct importance estimation with gaussian mixture models. IEICE Transactions Information and Systems, E92.D(10):2199) 2162,, -2662, 2009.
438
Yamada, M., Sugiyama, M., Wichern, G., and Simm, Direct importance estimation with a mixture of probabilistic principal component analyzers. IFICE Transactions Information and Systems, F93.D(10::8466 2849, 2010.
440
441
Yamada, M., Suzuki, T., Kanamori, T.. Hachiya. H., and Sugiyama, M. Relative density-rati estimation for robust distribution comparison. Neural computation, 1344:1134 2013.
442
13

---

Checklist
443
444
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
446
contributions and scope? [Yes]
447
(b) Did you descrihe the limitations of your work? [Yes] See Section 6
448
(c) Did you discuss any potential negative societal impacts of your work? [No] There is no such a potential negative societal impact in our work.
449
450
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
452
2. If you are including theoretical results...
453
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Assump- tions]
and 4
455
(b) Did you include complete proofs of all theoretical results? [Yes] See the subsection
456
A.1 in Appendix A
457
3. If you ran experiments..
458
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes].
480
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes].
461
462
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes].
465
464
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes].
485
466
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
467
(a) If your work uses existing assets, did you cite the creators? [N/A]
468
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
470
471
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
472
473
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
474
475
5. If you used crowdsourcing or conducted research with human subjects...
476
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
478
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
479
480
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
481
482
A
Appendix
A.1
Theoretical Proofs
484 In the appendix, we provide all the technical details and proofs of the theorems stated in the paper.
485 Verification of I Equation I
holds because
Ep- (H))
- -((0) = Ep - - - -EvrL'((((2)) + (x
- -
-E. (((Z))) Ex-L
= -
14

---

where (p-()((((2) = Eg- (V(() by the definition of R This verifies (
486
487
We now prove the following lemmas.
Lemma A.I. 1. If the convex fanction f RR - R is p-smooth over I. then for any
489
3; y E R. the following inequality holds
(w)) S +())+ x))
2 x)?
1
490
2. Les f: IR + R be first-order differentiable and convex function. If f is a-strongly convex, then for any x. y E TR, the following inequality holds
491
f(y) 2 + x)
2 x)?
482
Proof of Lemma A.7 The proof of Lemma A.1 is standard and can be found in Beck (011)).
493
Lemma A.2. Under Assumptions we have
(a). There exist two constants Co 2
0e-3M
Co = I such that
co col| - D 1lax S SBo (e²) -Ba (e
495
and
By (cP) Bi (d0t) S &ColID- D llaas
(b). For 4, 12 E [-M, M. there exist two constants C1 C2 such that
(t)(t)) - (1222 - C1/t1 tzl.
497
and
(62(1)) f22(22) S C2/l1 12)-
Actually, we can take Ci = 2c2M 11 C2 ea μ..
489
Proof of Lemma A.2 (a) Let (x, ==
(xx)
(x(x)(x y). Since
500
Ep. A
((Z)
e (2)) = B (e - (e and vi is smoohh and o-strongly convex, by Lemma
A.
σ
2 Ep
-0 < Epp A D12) ,e12))))))))) s
" E _ 22(21)3
502
and then by Assumption 2
oe 2M
1e
2 Ep (D(2) < E, ( (0(2)) <
2 (D(2) (A.1)
As E (D(Z) - (2)) E - Dr (2))² and 1| S M, we have
503
- e Eg -D()) -D' Ep (D(Z) - 22) v M Eg- (D(Z) - (2 (A.2)
AM
aMr
504
Let Co
2 Co = 2 then
A.I and (A.2) imply that
bolD-D'' 1l S B (eP) B& (e0*) S Coll D 11
505
(b) Obviouslyy for t1, t2 E [-M,M],
-
I ) (((ttr)) - - -b((E))) [(())
en "bl''(""') (6*1) s (e(2)) 11(("1) - -b(e²) (e e'2)]
M nle² - - + 11 let - 22222
2
2c w/eet - e (As let1 e'3l s M)
2e 2M ult1 t2/.
15

---

506 and
[62(1)) (2((12]
(1'(e (e
s Ale c
I eM ult1 - tzl
507
The proof of the lemma is completed.
508
Proof Theorem / For notational convenience, denote Gn DNN Im and use E₁ to denote E₁-, I = p. q- Recall that En, denotes the expectation with respect to (w.r.t) the empirical
509
distribution of 11 for 1 p.q- As D arg minpeTes fagin (D), where S.g.m, (D) 1/0p Σ (D((2))) + 1/mg Ein Lz(D(Zg,)), have
coll 1 D 1
$ B (e0
B (cli)
S B (cD)
By (c0+) - fupimng (D) + fo (DNN)
Be (eb)
Lm, (D) ( [BBs (eD*) mmm)(())
{fo my (DNN) f. (D")}
(Eep En, (Cn (D") (Bg En, -
En, (DNN) - (D())
En, (22(NN) C2
(A.3)
512
By Theorem 2.1 in Bartlett et al. 20055), with probability at least - exp(
1/2 +
16C1MM
En, (,00::/(("00000a//o/ooo)00---11-
S
Im
3n
(A.4)
513
Also, with probability at least 1 -
711 1602M
En,
E -,0 - V
3n
(A.5)
514
The inequalities (A.4) and (A.5) together imply that with probability least 1 2exp(->1)
En, (DiN) - Li (D")) + En, (D2(DN)) - L2(D")}
< Cp (DNN) - (D(D") + (D -
+ V2(Ci + C2) - D mmx
71 +
16(C) + C2)M71
3n
By (ND)) - By (cD*) +
2
(C1 C2) D Imax 16(C) + C2)
3n
2
16(C, + C2) (A.6)
s CollDNN 121 max + V
(C1 + C2) D Imax
n
3n
515
Step 1. Let g (D- -- then g < 4M2 by Assumption If If D*
Iaax r, then
var < Ep(g²)
Ex(D-D*) D7y1
< Ep D71²
4M2,2
Regarding g function of D D*. we have
Dg(D1 - D*) g(D2 D*)l = |o - 2D,D* - (DŹ - 2D2D")l
1(D, + D2 (D) D2)l
1(D, + D2 - 22D) - D -D2 D*)H
S (M) - D*) (D2 -D').
16

---

Thus can be viewed as the function of D - D with a Lipschitz constant 4M. Denote JENN" {D E FiNN,
518
D mmx S r), and
R1 m f(Zr.), I=p.9.
Ba, F = sup fEF
TI
where n/,, .., By are i.i.d Rademacher variables. For the rest of the proof of Theorem
519
1 Rn, denote the conditional expectation of R w.r.t w/ 2,,,... v,,, given 71,i, 1,2....y ,,, and R F to denote the expectation of R jointly w.r.t 57. Z,, 8 ,, nr. Again, by Theorem 2.1 in Bartlett et al. (2055), with probability at least 1 - exp( -71)
520
522
- D'-
pm - 1
I Bppn (D-)"); DE FINN" 5 + 2
2n1 M +
16M
7/1
3
271
16M
< 24MEp. Ra, (D- D*): D DE F
+2/
Mr +
(A.7)
n
3
where the last inequality follows from Talagland's contraction theorem. Similarly, with probability at least 1 - exp(-<> --)))
624
D- 12
13 q.
-1 11 < 24M 2n Bn, {DD- D E FIPi""
+2
12n Mr+
16M n
n
3
(A.8)
525
Let
(r)
FE Res ( D³) DD) D E FINN" 1
max re(p.))
24M
526
When
16M22
2 Rn (r), r2 2
(A.9)
3n
A.7 and A.8
indicate that with probability at least 1 2exp( -m),
1D D 12 my
max
D' I ||D D"I
2 Mr
16M 21
max - D'
11 1|-m || 1011 + (r)r)) + 2/
n
3
n
2n1 Mr +
16M 71
| D max + (r) 2
n
3
< (2r)².
528 Thus, when A.9 holds, with probability at least - 2exp (711)
|| D' Dulax Sr | D" 11np.ng 2r. 2r.
(A.10)
Step 2. Suppose | D" max I ro and let
529
g, = [C((D) C.(D)) FD" j: 1,2.
530
For each (I, E {pp, 1), (q. with probability at least 1 1-2eepp 1-eeeppxpp -1x)
- (n)
11 + - C,("))) &,, + v2C
46C,M
(A.11)
3n
531 Denote A. = (D E JINN: | Im Sr.. By A. Step 1, when r8 2 (r, and
532 rō 2 (6M2)/((3)) with probability at least 2exp( 7. for each (I, E {p, (q,22)
E, Rn, Gi S 2C, ( (D- D*) DE DD FAN
s 2C,E, Rug { - D*): : D FD 270
17

---

Denote J.prr = (D FFNN, IID - DM S r). When n 2 Pdim(FrNN); ro 2 1/n and
534 n 2 (2eM)? we have
Pdim( logn
Bn ((D (1D : F S 6
(A.12)
535 and thus
Pdim (FrNN) logn
E Bng 91 S 1280
(A.13)
536
Combining
A.3
A.6
A.11
and AA113) with probability at least 1 - 8exp(- we have
Pdim(FFNN) log
Co
|
768(C1 + C2)rro S
2n (CI + +22 + 46(C) + C2)M + CDe
+V
n
3n
2m
16(C) + 02)
(CI + C2) +
3n
Pdim (FFNN logn +
2
(C1 C2)ro
V68V
n
2n1 (C1 + C2)c +
62(C) + C2)
+Coch + V
3n
Therefore, when max { (Pdim(FFNx))ogg 6n) < ro. there exists ri < ro such that ||
537
538
D'llmax < T1-
539
Step& 3. Let T. in 2
0
Rx (s)
S
2², for s
2 r} and
=
540
{ | - D* D* In S 4r. for all D D FNN
2r.
f. We intend to prove
Pdim(FrNs log
r. S KM
== 24 130.
(A.14)
n
When r. S 2/3M log n//33, the inequality is trivial. When r. 2 2/3M /logn/n/2 by the result in Step 1, P(E) 2 1 - 2/n. As a result,
542
r v R (r-)
Rn (2r.)
24M max (nr DE FD' }. rE(ma)
543
For each E {p.9).
Bn { D²): : D JD' }
Ey (D- D*): D E JDD 2r.
Ey Rmi {D- D*) : D E JDD FD,,2r. 2r.
(Ig Ig-)
E, Ey Ray { D') D E PNN
Ar.
4M
+
n
It follows from A.12) that
Pdim JFNN log 4M
22 <
24M
128r
Pdim JFNN log logn)
4M 1
24M
128r
n T+
Pdim (F FFNN log
3
24Mr.
128
7
n log 72
Pdim FFNN) log Mr
7
18

---

545 where K. = 24 x 130. Thus, T, I xM Pdim FFNN log n/n and (A.14) is proved.
Step 4. Let B rr) = {D FFNN || D max I r), 2 max (Vlogn/n.7) and
548
1 - 10g BAAAMM/Vo//// (/gg/n) Then, the neural network function space JFNN can be divided into
547
Bunxx D F), Biax ,D", Buax (D", (D",F),... Biax (D*, (2,2 ( ( 1r)
2F)
548
As F 2 Pa. it then follows from the definition of r. that 72 2 (T) Further, if f2 2 16M //M/n/(3n) according A.10 in Step 1, with probability at least 21 exppp-111 for any
549
550
j = 1.2.....
| - D' S 2/r = ||D D'Ilay.n 2
Suppose that for some j 11. Bmax (D' (2 (2 (D*, 2 7),
then by the results in Step
552
with probability at least 1 - --xxe-xp-1)
Rdim(FFFNM) log
2
coll D 1 max
$
(CI + F2)2'
7681
+
121 (C1 + C2)En +
62(C1 C2)
+Coe + +V
n
3n
553
1 (11 + C2)
768
Pdim(FFNNI) log + v2
71
S
2/7
(A.15)
c0
N
N
and
Coe +
n
+
62(C1 + C2)
< 22
(A.16)
N
3N
555 then
[1 DD < 22-2222 +> 11 D max S 10
556 In short, to obtain this inequality, we need F satisfying A.15).
(A.16) and F
2
557 max (/ogg//n,4/311 //33////3/333.. As I xM AMMdiim(Frsa log n/ m, there exists con-
558 stant C. C. Co. C1, C2, M) (",,, o, M) such that Pddim(FeNx) log n
71
C=
n
satisfies all the requirements. As result, with probability at least 1 101 exp(-xxp)
| D Imax S F and 1 1'lmmim S 2F.
Let 11 log 101 + 7.1 1ogg(2M/ Vlog n,/]], there exists C C(co, Co, C1, C2,M) C(u, o, M) such that with probability at least exp(-7),
561
11 - D*llmxx SPSC (V
|ddim(FraN) logn
7 + en
n
n
and
| D' Im 20
Pdim(FrNN log
2 n
en
n
The proof of Theorem is completed.
584
Lemma A.3. The following excess risk decomposition always holds:
By (e0) -By (60*) ={8, B (eD)
{
B& (c0)
By (eP) - By (e.)
inf
inf
DEJION
DEJINN
19

---

585 Under Assumptions 1 and 3 when 2 (FNN), there exist three constants C, Co, C.. with
586
C, Co depending only on (p. o. M) and C. depending only on (1, σ), such that
Exr ar { BB (eD)
By (e21) SCV
Pdim (FNN log
inf DES
(A.18)
n
and 567
Pdim Pdim(FFNN) log
-a 17-173 1D-111 s Coy
+ C.e2M
2M
inf
|ee - 1
DEFIsN
Proof of Lemmna A.3
To show (A.18) is the key step in the proof of this theorem, thus we focus on
569
the proof of A. 18)
Let
Do arg min B (cP) DEFis
570
Then,
Fgy of
BB (6))
inf By (c0)
DEJION
Bg (0)) Bi (ePu)} }
Fagis a
BB (e0) - B (c0)
+ +Br (60) - By (c
Exg a
BB (c) - B& (cPu}} }
+ Ep'.9 .4-
18p (cD) - B& (cP)
< 2Fp'. .4'
sup
(A.19)
DEFINN
By the symmetrization technique, Talagrand's lemma, A2.12 and the fact that D S M for any
572
D E FFNN, we can easily get the inequality (A.18) through (9.19)
Proof of Theorem Theorem 2 is direct corollary of Lemma A.3 We omit the details here.
574 Proof of Theorem
Since D' E ([0, 1J M) with 8 = + where k N+ and a E (0. 11. by Lemma 1 for the FENN, function class consists of ReLU FNN with width W 38 and depth D 21([$] + 2)2 (8K)) where K, L E N+ there exists 577 a function dn FFNN such that
L [[og, dd
sup 1 - dol s (13 + +)2 2
(A.20)
where HB.8 f= , rd]] Di - (b/B 5, B) }, B [(KT))2/1 5
(0, 1/3B)] As DNN arg me D - D* mmmx then
| D' < 11:0 D'
580
By the result in A.20 for I = g, we have
11 - 1'113
1 D - (00-0121(())dd +
D - 10-
H8.
+ I) (1101000))))))
+M12 /
(x(d)dr.
HBg
As p" (-),g(() are the density functions of some measures on [0, 1]d which are absolutely continuous 582 with respect to the Lebesgue measure and 8 can be arbitrarily small, JHa. To (o(r)a is also arbitrarily
small. Thus we have
|100 - 1" < 324M²( + (K)))))))))
20

---

584
and
|| DNN - D*Ilmax
v 1100 D
s 324M²(18] () (1 (KL)
+
=
585
By Corollary
! there exists a constant C₁ only depending on (1, o, M) such that
Pdim(FrxN] logn
Epr .6 |5 D
C2
n + DINNN - D max
Pdim(FFNN logn
1 C1
n + (2, (KL) 4
324M² (dim(FFNN)) log n
+ (i3,
(A.21)
n
586
This completes the proof of the first part Theorem
587
As for the second part of this theorem, based on Theorem 6 in Bartlett et al. (019)) for a specific
586
ReLU network før where & contains the parameters in the network, there exists universal constant
589 C2 such that
Pdim(FFNN) S C2SD log
where S is the total number of parameters in the network fa. For ReLU FNN with width W and depth D, it can be easily checked that S O(W2D) Now for W 114([3)
1) D 21(13] + 1)² n स.त log2 8nn Saazzr)) ] and W,D satisfy O(W²D) =
592
O (13) 1)9 n.azzz log" *n] which means I, 1, K = n s and there exist
594
three universal constants C3. Ca. Cs such that
SD log S log n
s Cs (13) + 21012 n m log "n]
(log Co [13) + +1)8 111111 n ग log 3 1}1)
f211118) + 1)² n ा loga (8n Strzee)) ) log n/n
C. {(L8) + 1)88 2 -2 पमा 2ht log 1 n
(log(155 + +1)++ 2(1 1) log d
log
2(d + 23)
C4 [(18) +) 2113 2n (( log-'n
'p--nn 'n (6(18) + 2(13) + 1)d + logn]
Co(18] + 1180018)++3 2427
(A.22)
It follows from A.21 that
Ex |
D 121 max
PdimmFFNN) logn (KL)) -2
324M2c
n
C2SD log S log
324M'c
(3,
20 < 3 [CCC3(18] + d2 81+3
+ 11 (1914(((8
324M (C2Css 1) ا|ا - -..9
This completes the proof of the second part of Theorem
21

---

597
Proof of Theorem 4 Based on Theorem 3.1 in Baraniuk & Wakin (2009), there exists a linear
596 projection Roaxd such that AA" dlaz/db. da where Laz E Xxx is an identity matrix, and for
any F 1 E M,
(1- u112 S AAr - Ayll2 - (1 + +)]l= ylle.
(A.23)
Then we have
A(M,) S (10, S [-
d d
de
vda vds
601 Note that for any & E A(M). there exits a unique x E M such that 2 = Az. Otherwise, suppose we find x x' E M, F x' such that = Ar Ar', then by (A.23) we know | 2/I12 0 and 603 thus x = x', which contradicts the assumption that x # x'. This uniqueness allows us to define a
602
linear operator SL: A(M) M such that A[S2(=)] 2. By A.23 we have
(1 - ())(((((())) SL(z))ll2 ||=1 22/12 (1 8) SC(a)) Sf(z2)ll2-
605
This implies that the norm of SC belongs to [1/(1 5), function D* [0, 1] - R whose support is Mp. it has approximate low-dimensional representation
1/(1 - -)]- For the high-dimensional
607
D' as follows:
D²(=)= D(())))()((3)) E
As D E (10, M) with B = k + a where k E N+ and a E (0, we have 609 D E H M/MM)M/((1))) 8)%) By the extended version of Whitney's extension theorem
608
in Fefferman (2006), since A(M) _ A (10, = [-d//Vds d/ d// da there exists D e 5)0) such that Di D on A(M). If W = 38(
610
7 ([ d/ [-d/vds, Vdz, d/ [ds]" M/(1-5)²)
612 d) 191+2 L (8L)) and D = 21([3] + [loK[lo,,SKKT (8K)), by the first result of Lemma there exists function oo implemented by a ReLU network with width W and depth D such that
sup x
D
2dz dldss <bo())
5 (1 8)5
18M
(18) + (2)) -101 (KL) 25.
Vdz
where Hee
1z
[21, T2..,,,., Idh] : x2 E up b/bBB) and B
[(KI)2/4 E (0, 1/(3))] Thus
615
Di((2) -do (Vdsz + dlds
sup
2d
v'g v4g
(1 8)3 (1B) + 1)² (())+(8V1+))/2(((X)1 (KL))
18M
(KL)
2/
B,c 616 where Hde = (2dt - -d1d,)/ Vds: it t H
617 Let 60(x)
= do ((Vd5Ar + (/2d)) and H
{x [0, 1] (VdgAr+ (1d, B.e) ). It can be easily checked that do is also function
619 implemented by ReLU network with the same structure as Φu. except that the input layer of Oo has d units, instead of de units. For any x E MpHHi Ar E [-d/Vds, d/ /ds do Hrg and there
621 exists x' E M satisfying || r2112 S p. Since Dj E H2 (I-d/ d/ Vabl do M/ - 518)
22

---

622 and D E (10, M),
00(2)) (x)=
(x)
(z) -
- (x)x
18M
5)3 ([8) (
28
+
(1 5)3 1|Ax' - -Arll2 + PM
M
18M
(18) 1f
# + (1 - 5). /dd'
M Mvd
P + pM
(1 - 5).
18M
2M
(13) + 1) (2d)
(KT))
28 + (1 - 8)8 Vd8 0
5)3
x
20M
5)3 (1š) + (2d) (KL) 46
(A.24)
823 where the last inequality holds when p S (18) + 1)22 d DNN arg min Fro De
(KL) 24 As
D D* mmax-
DNN D'Imax S 11000 DJ
By the result in A.24 for I por q. it holds
11 - 1
D - (x) +
DD" - 10
Io.jaa.H..
18.0
(1 8)28 (18) 1) gg 38 (KL)
400M
4#
"5
+ (1 - 6)-8
4M2
(x))d..
JHS...
626 As As (),g()) are the density functions of some measures on [0, 1j which are absolutely continuous
627 w.r. the Lebesgue measure and 6 can be arbitrarily small for the given 8, SH Io(x))e is also
628 arbitrarily small for the given 5. Thus have
400M
11000 17
S
(LB) + (2 (KI.) 35
(1 - 5-23
629
and
|NNN D lemax
1000 D max
400M
(KT)) (13) + 1)4 (2 23 (KL) #
s (1-6)a0
(1 (1-8)28 C2(B, d, (e(B,,,d)(KKI) #.
4
630 By Corollary I
there exists a constant C₁ only depending on (M, o, M). such that
Epr,0 x | D* D' I|
Pdim FFNN) log n
G
1IDAN
11 1laxx
C
Pdimm log n
(1- C2 d. (.3,ddd)((K)) (KL.)
400M
#
200M
Pdim log + C2( d, (KL) 46
<
(A.25)
(1 8)28
n
For
W = 114(13) + d) 181+1
632
2e n न log,
de 8n ..6
D = 21((111)) + 1)2
23

---

633 and W, D satisfy
2101+2 -0 2
n b
log 3 n2 n/
there exists universal constants C* such that along the derivation of A.22
( log n
C (18)
1) 25+23
Based on the result of A.25
Ep a 11
D Fdim(FFNN) log
400M
+ (3, do) 44
(1 - 5)23
"
40
[03( + 1) 128143, n ug + (B, d, d&)m 12
(1 - 5)28
800M2C1
(1 5)23 (18) + 1) max (d2 (2d)28 d 1011+33
29
n
46
S00 C* (3, d, da)
26428
(1- (1-8)a8
636
This completes the proof of the theorem and
637
Proof of Proposition
L For k = O, K 2, the densities Q=(), 4-10) of the synthetic data { 1 and 1 17 satisfy
638
(x(() (1 ax (2) axp"
(1-e M--e-Maa + e- - akk
(1) - (1-0 10 (2) + ox 12)
- e e--e-Mope M Max+1 M1 ax+1
As lf = (z)d then for any density g satisfying 2 lllll = (J2 {((r)d))* S 629
(J2 (()))(()//dd)) & /1/lla/ Vo. Using an appropriate JPNN whose element D satisfies || S
640
Mo. for the direct estimate DSRE. as log(g"/ /p") is only bounded from below by Mo. by Theorem
641
642
we have
lim sup P- |SRE - D2112 s Mo (1, c1)] - Ri lpp
For = 1,...... K 2, as log 9k (t)/ (+) is bounded by Mo. by Corollary I we have 643
lim limsup Ex ar 1| Dilla
6M Let R (1- (1-ak- ak-iaaa R855, + tak 1. As the logarithm of Ri- (1 aa--1) /p" + tak-1 is also only bounded from below by - Mo. again, by Theorem 2
645
lim sup F...g. [ D2-1l12 s (, Ri RM-11, n-400
(1- Rig, 1pp
646 Thus
lim sup Fp DTRE D2112 <
lim sup Fpr 15 - Dill2
n-000
2-000
lim sup Ep .4- 11 [D - D*-1ll:
n
< (1 o Mo. -Rar l1
647
This completes the proof of Proposition
24

---

648
A.2 Examples of Hölder function class
649
Let p" be the density function of truncated d-dimensional multivariate Gaussian with mean zero and covariance matrix Ep Idxd in [0, 1]". That means
650
p²(=) exp(-2222 2 x/2)/c(Ep), c(Ep) Sa.n exp(-t'E, t/2)dt t/2)dt,
[0,
651
Similarly, let
==(=) cxp==xxp->''y 2/2) (((gg)
for some positive definite matrix Eg. For any matrix A Rdxd Ai, is the ith row of A for
652
653 i = 1,2,..., and
|, sup |
11
654
Then,
(2) log gx(x)
1
2 2x1p'' 2 )2 1og((((())))) c(>ig)), 2 E [0,
p (=(=)
655
Let M = max
(11
2
1/2 12,
+ |
1/2
12, + [log[c(E))) - cl (E 11 Ey E7 12,, = 1,2, 1..
656
is straightforward to check that
D (10, .)).
657
It implies the Hölder smoothness parameter 3 is 2 for this example.
Moreover, the truncated multivariate Gaussian distributions considered above are special cases of the exponential distribution class defined below. Define the density function class
659
Exp(3, B) = { p(z) = exp(s(=))/<) : E [0, [0, Cq / exp(o(t))dt, E H 11 B)
J1o.1a
Suppose that E Rdxd is positive definite and let g(z) 2'Ez/2. Then, g E H[ M2). where My = max { (1 12 ||,,, 1.2, 1,2,.... .... If p" E Exp(3, B), we have
660
681
D' (z) = logla" (z)/p" [=)] E 7t (fo, 1]4,4)). 4B).
662
663
A.3
Extension to unbounded support case
684
In fact, our Theorem M Corollary D and Theorem 2 do not rely on the hypercube assumption. To relax the hypercube assumption to allow unbounded support, we need to study the upper bound for the approximation error ||DN 1 carefully. With unbounded support, we may bound DNN - D || by the truncation technique under some additional assumptions, at a small price of an additional logarithm term in the error bound.
665
666
667
Specifically, when the pdfs are supported on Rdd bound the approximation error as in Theorem
669
670
aside from Assumptions 2 and the Hölder class assumption, we need to further assume that
671
max ( E.. /[] [1 2 n). E.g |l 2 1)gn)} S शーक For or q, and any D E FENN.
672
where FFNN is the function class of ReLU FNNs with width W and depth D specified by
W 114(1 1)2a111+1
D D=21(13 + 11² 2(4+20)) loga
(8n (Snaaata)) )
873
we have
(1ID(ZZ)DD*22 Ei (D-) D' ( 2 logn))
(22))) ( 1 sogn)] AM 2 l) + E,- - ( S n)],
where the second inequality follows from the facts that | M, ||||0 < M under Assumption
2 Since D* E (Rd, M), (2t log log nl,) E ( 1]4, (2 log log
function of
676 T, where 1a is the d-dimensional all-one vector. By Lemma]] there exists a function do E FINN such
677
that
(21 log nl)) Φol 5 18(2 log (81 M + 2 (8111(() n 2ं..
sup
25

---

where HA.5 -U [l,,..,,dd] E up (b/B - 6.b/B) anaass 1,8
579
(3B)] Thus
(²(2) - on ( = log nl 2 log n
18 M((3] 1)) 10)101+003) 18(2 1)
sup =E[- Iog m
680
where H { 2t log log n : BB8 J. Let )o()) do
log mly
2 log
E FINN. As 8 can be
arbitrarily small, it then follows from similar lines as in the proof of Theorem
that
E1- (()(()) D D' (2))
& logn)] (18) (2 (2lo 2) 2t2s.
Since DNN arg argmin DEFFFN |D D* D'||maxx Imax have
pe
DNN - D 1
11ō0 - -1
W
max [4M Fg 1( 2 logn) + Fg- - -2) I log n)]
1=p.4
328 2 ( 1)) (2 log n) 21
at20
Compared with the upper bound of the approximation error in Theorem 3, when the pdfs are supported 684 on IRd (unbounded case), similar approximation error upper bound can derived with an additional
logrithmic factor (2 log 2
685
686
A.4
Simulation setting and implementation details
687
Our simulation settings are as follows.
Beta setting: Let Z = (Z1, Z2...., 7p) Rd be random vector of interest, where Z1, 7,,,...,, Zp are i.i.d. random variables following Beta distribution, denoted by Beta(a, B). Set p" the p.d.f of Beta(2.2, 1.5) and q² the p.d.f of Beta(2, In 5.
........
689
881
this setting, we set
Normal setting: Let 2 (Z1, Zz..... Zd, Za+1, Z8+2.... Z2a) E Rdd be some random vector of interest. Let p" be the p.d.f of N (0, 12a) and q² be the p.d.f of (0, (p))) where E(p) = (of.)) E IR 2dx2d and
692
694
= ji P,
1,
of
=
i- =
1,
1,2,..,,24
0, otherwise.
885
In this setting, we set d = 5 and p 0.9.
696
We apply the Adam algorithm (Kingma & Ba, 2014) in Pytorch with learning rate Ir 0.0001 and weight decay parameter wd = 0.0001. A neural network with 2 hidden layers with widths (64, 64) and ReLU activation function, used in the experiment. The maximum number of epoches is 20000. In this experiment, the training data size n is 5000 (10000). A validation data is used. The batch size 500 (1000), and an early-stopping technique is applied with patience = 100 for Beta setting and patience 1000 for Normal setting, where patience is the number of epochs until termination if no improvement is made on the validation dataset. The experiment conducted on a laptop with an Intel(R) Core(TM) i7-875011 @ 2.20GH CPU having 6 cores. We use the LR- -R-Bregman divergence in this example. For the sequence 0 = ag < a1 < ... OKK- < ak = 1, we use the lincarly spaced ag 's, that ag k/K, K. & 0, 1, 2..,,..,,KK K.
887
696
689
700
702
704
706
A.5
The MNIST dataset
707
We now apply the proposed mixing chain 13 for density ratio estimation to the MNIST dataset
708
LeCCun et al. 2010). In the implementation, to accelerate the computation, we use the subsampling
709
method with a training subsample size of 20,000 and a relatively small DenseNet network structure
Huang et al. 2017); see Table A. for the specification of the network architectures. Similarly
711
to the results Table of Rhodes et al. (2020), we calculate the average negative log-likelihood
(ANLL) in bits per dimension (bpd, smaller is better). We denote the estimate based on the proposed
26

---

713
mixing chain 13) with the chain length B by InTRE-B". The batch size is 512, /r = 0.001 and wd 0.0001. The maximum number of epoches 1000. The reference distribution for our mTRE is taken to be the standard Gaussian distribution. Here, the reference distribution is the same as the noise distribution in the MNIST experiments of (Rhodes et al. 2020). We obtaín the averaged ANLLs and their empirical standard errors for mTRE-5 and m TIE-10 10 over 5 random training subsamples.
714
715
716
717
718
As comparison, we use the results with the Gaussian noise for the direct single ratio estimate and the direct estimate based on the original convolution chain (cTRE) obtained from Table I in (Rhodes) ct al. 2020) as the benchmarks. Note that cTRE and the direct single ratio estimate are based on the full training sample, where the sample size is 60,000. The result for the cTRE presented in Table A.2
720
722
is the best one among the cTTR'ss s with the chain length E (5. 10, 15,20, 25. 30) in Table in the online supplemental Rhodes et al. 20200. Our results presented in Table A.2
724
From Table A.2 we see that mTREE is significantly better than the single ratio estimate and comparable with cTRE. The difference between the results from m and cTRE is not statistically significant.
725
726
We note that the training sample size for mTRE we used restricted 20,000, due to the memory limitation of the laptop used in the computation. In comparison, the sample size for cTRE is 60,000.
Table A.I: Architecture for mTRE
Layers
Details
Output size
Convolution
3 x Conv
12 x 28 x 28
Transition Layer
BN, ReLU, 2 x 2 Average Pool, 1 Conv
12 X 14 x 14
Dense Block
BN, 1 x Conv, BN, x 3 Conv
24 x 14 x
14
Transition Layer
BN, ReLU, 2 x 2 Average Pool,1 1 Conv
12
7
x
7
Dense Block
BN, 1 X Conv, BN, x 3 Conv
24 x
7
x 7
Pooling Fully connected
BN, ReLU, 7 x 7 Average Pool, Reshape
24
Linear
Table A.2: Average negative log-likelihood (ANLL) in bits per dimension (bpd, smaller is better). For the proposed mixing chain estimate with the chain length B (mTRE-B)), the ANLLS averaged over 5 random training subsamples, where the subsample size is 20,000, and the corresponding standard errors are in parentheses. The cTRR is the direct estimate based on the original convolution chain (cTRE). The results for the direct single ratio estimate and the direct cTRE are obtained from Table 1 in the seminal paper (Rhodes et al.) (020) and we use them the benchmarks. The cTRE and the direct single ratio estimate are based on the full training sample, where the sample size is 60,000.
Estimator
mTRE-5
mTRE-10
Direct Single ratio
Direct cTRE
ANLL
1.40 (0.0045) 1.39 (0.0077)
1.96
1.39
27


Reviews:
[{"review_id": "wLlaW9Jr3AI", "reviewer": "Reviewer_1fM2", "summary": "The paper introduces a density ratio estimator (DRE) based on the Bregman divergence which is different from Kato & Teshima (2021).\nThe author(s) derive(s) non-asymptotic error bounds for the proposed DRE, which turns out to be slightly better than that of Kato & Teshima (2021).\nBased on the established bounds, the paper then studies why the telescoping density-ratio estimator (TRE) has a good empirical performance compared to single-ratio DRE.\nOn a specific bridging methods proposed by the author(s), it was argued that TRE has a better asymptotic error bound than that of the single-ratio method.\nIt also indicates that the originally proposed bridging method in TRE could have some insatiability issue.", "questions": "- $\\exp$ is used to make the density ratio estimator positive but it is known that $\\exp$ is numerically unstable and in deep learning usually $\\mathrm{softplus}$ is preferred. Can you justify your choice here?\n\nTypos\n- L134: \"Section ??\" -> Section 4\n- L260: \"TDR\" -> TRE", "limitations": "Limitations are discussed but not potential negative societal impact.\nThe work is theoretical and I don't see direct societal impact.\n", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros\n- The paper studies an important problem that wasn't paid enough attention.\n- The method and analysis presented in the paper is novel.\n\nCons\n- Conclusions derived from the analysis are not verified empirically. For example the choice of bridging method (mixing v.s. convolution).\n- The analysis of TRE is based on an alternative bridging method for analysis convenience, which may not be enough to explain why TRE performs well.\n- The paper is dense and not easy to follow for readers who are not familiar with the proof techniques.", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "rYwrvNnvTAN", "reviewer": "Reviewer_T57B", "summary": "In this paper, the authors aim to establish non-asymptotic error bounds for a nonparametric density-ratio estimator which minimizes the empirical Bregman Divergence (BD) score over a class of neural network functions. More specifically, let $D^*=\\log R^*$ where $R^*=p^*/q^*$ is the density-ratio that we would like to estimate. In addition, assume that we have $n_p$ i.i.d. samples from $p^*$ and $n_q$ i.i.d. samples from $q^*$.  The empirical nonparametric density-ratio estimator of $D^*$ over a class of feed-forward neural network function $\\mathcal{F_{\\mathrm{FNN}}}$ is defined as $\\hat{D}:= argmin_{D \\in \\mathcal{F_{\\mathrm{FNN}}}} \\hat{\\mathcal{B_{\\psi}}}(e^D)$ where $\\hat{\\mathcal{B_{\\psi}}}(\\cdot)$ is the empirical Bregman Divergence (BD) score. \n\nThe authors first show that under some mild conditions, with high probability, $||\\hat{D}-D^*||$ is bounded above by $||D_{\\mathrm{NN}}-D^*||$ plus some $O(\\sqrt{(\\log n) \\mathrm{Pdim}(\\mathcal{F_{\\mathrm{FNN}})}/n)}$ terms where $D_{\\mathrm{NN}}= argmin_{D\\in \\in \\mathcal{F_{\\mathrm{FNN}}}} ||D-D^*||$, $\\mathrm{Pdim}(\\mathcal{F_{\\rm{FNN}}})$ is the pseudo-dimension of $\\mathcal{F_{\\mathrm{FNN}}}$, and  $n:=\\min (n_p,n_q)$ (a PAC-bound). Then, in the next parts, the authors show how to bound $||D_{\\mathrm{NN}}-D^*||$ for a special case where $D^*$ belongs to a Holder class of functions, $\\mathcal{H^{\\beta}}([0,1]^d,M)$. The authors proved that this term is bounded by a term of order $(KL)^{-2\\beta/d}$ if the neural network has with $\\mathcal{W}=38(\\lfloor \\beta \\rfloor+1)^2 d^{\\lfloor \\beta \\rfloor +1} L\\lceil \\log_2(8L)\\rceil$ and $\\mathcal{D}=21(\\lfloor \\beta \\rfloor+1)^2 K \\lceil \\log_2(8K)\\rceil$. By additional assumption that the data from $p^*$ and $q^*$ are concentrated on some $\\rho$-cover of a compact finite-dimensional Riemannian submanifold in $[0,1]^d$, the authors can obtain an improved bound on  $||D_{\\mathrm{NN}}-D^*||$ which reduces the curse of dimensionality. Finally, the authors perform error analysis for a telescoping density-ratio estimator and affirm that the telescoping strategy (TRE) can improve the expected error $||\\hat{D}-D^*||$ as $n\\to \\infty$, which affirms a conclusion by Rhodes et al. (2020) by experiments. \n\nThe key contribution of this paper is Theorem 1 which provides a PAC-bound for $||\\hat{D}-D^*||$ via $||D_{\\mathrm{NN}}-D^*||$.  The proof of this theorem is based on a good observation that the Bregman divergence score function $\\hat{\\mathcal{B_{\\psi}}}(t)$ is sum of two Lipschitz functions and an interesting fact that $\\hat{\\mathcal{B_{\\psi}}}(e^D)- \\hat{\\mathcal{B_{\\psi}}}(e^{D^*})\\sim ||D-D^*||^2$ under some bounded conditions. Hence, the authors can apply some classical results in learning theory such as symmetrization inequalities and Talagrand's contraction theorems to bounds $||\\hat{D}-D^*||$. The other results are mainly based on existing results related to an approximation of a Holder function by a neural network function (Jiao et al. (2021)) and/or another dimension reduction result by (Nakada and Imaizumi, 2020) to bound $||D_{\\mathrm{NN}}-D^*||$.", "questions": "Here is a list of typos and questions:\n\n1. In line 586, please explain how to bound $||\\tilde{D_E^*}(Ax')-D^*(x)||$ by $M\\rho$. It looks not clear how to obtain this. \n2.  Please explain why the convergence rate in (8) is optimal (a conclusion in line 166). See my comments in the previous part. \n3.  Some typos: in line 134; Proposition 1 ($2 M_0$ should be replaced for $M_0$); a definition of $\\Delta_{\\psi}(x,y):=\\psi(x)-\\psi(y)-\\psi'(x) (y-x)$ should be mentioned in the proof of Lemma A.2; a citation for (A.12) should be provided; and the norm of $\\rm{SL}$ (not of its derivative) in line 569, etc. Please correct them.\n", "limitations": "This is a theoretical work. The authors already finished the checklist as well as stated the limitations of theorems and results. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This work can be considered a novel combination of well-known techniques. The error bounds in this paper are new (to my knowledge). By setting a distribution is fixed, the error bound results in this paper can recover the minimax rate of the density estimation in Tsybakov (2008) with an improvement on the effects of $d$ (cf. Section 3.2). \n\nIn general, all the results in this paper are well proved and look correct. There are some typos but it does not hinder readers from understanding the results and their proofs. There is a problem related to the minimax optimal conclusion in line 168. More specifically, the authors mentioned that the convergence rate is optimal. This looks not make sense if the authors only based on the fact that this bound is minimax optimal when fixing a distribution. Optimality by fixing one does not imply optimality for the fraction of the two distributions.\n\nFrom the technical viewpoint, there are some interesting ideas in the proofs such as converting the estimation problem for $R^*$ to the estimation problem for $D^*=\\log R^*$, partitioning the range of $\\hat{D}$ to make use the fact of that if $||D-D^*||\\leq r$ then $||D-D^*||_{n_p,n_q}\\leq 2r$ to bound $||\\hat{D}-D^*||$ in the proof of Theorem 1, or using i.i.d. Bernoulli random variables to telescope density-ratio estimator in Section 4. \n\nHowever, this paper contains some weak points as follows.\n   1. To obtain an upper bound on $||D_{\\mathrm{NN}}-D^*||$, the authors need to make an assumption that $D^*$ belongs to some special class of functions. More specifically, the authors assumed that $D^* \\in \\mathcal{H^{\\beta}}([0,1]^d,M)$. However, this looks unavoidable with deep-learning-based methods. An example of $p^*$ and $q^*$ (common distributions, exponential class for example) such that $R^*$ belongs to this class will make your paper more interesting.  \n  2.  If $D^*$ is unbounded above, the result in Theorem 2 looks not tight enough.\n  3. The optimality of the bounds in Theorem 3  needs to justify (see the comment below). ", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "rVUMavJK-3Q", "reviewer": "Reviewer_hTC4", "summary": "This paper studies density ratio estimation based on deep ReLU networks. Based on a loss criterion by the Bregman divergence (eq.1), and under weak conditions (stated in assumptions 1-3), the authors showed that this family of density ratio estimators can achieve optimal convergence rate (Thm 1 & 2, and 3).\n\nThe authors also extended their bound into the cases where the data is on a low-dimensional submanifold (Thm 4), showing the curse of dimensionality can be alleviated.\n\nAs an application, the authors further applied their bounds to the Telescoping density-Ratio estimation (TRE) (Rhodes et al., 2020). The author's bounds can help demonstrate the advantages of TRE over single-ratio estimators.", "questions": "The current paper studied density estimation of p and q, which are pdfs supported on a hypercube [0,1]^d. It is not clear how the results can be generalized.\n\nAssumption 2. As a ReLU network output values in the range (0, \\infty). It is not clear how this assumption can be satisfied. It should be explained in more detail in the text.\n\nIn equation (3),  $\\hat{D}$ is the global optimum by definition. In practice, one only gets a local optimum solution through neural network training. Can the stated bounds guarantee the density-ratio estimation quality of these local optimums?\n\nThe main weaknesses mentioned in \"Strengths And Weaknesses\" can be regarded as my questions.", "limitations": "This work is of theoretical nature. I could not see any negative societal impact. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pro:\n- Solid theoretical results.\n\nCon:\n-The paper contains a list of formal results and lacks intuitions, numerical examples, and detailed explanations. As a result, it is hard to read.\n- The theoretical results are for general Bregman divergences satisfying certain smoothness and convexity constraints. Although some examples are given in table 1, it is not clear how certain choices of the Bregman divergence can further enhance the results.\n\nPlease see below for some minor comments (these are not questions to be addressed in the rebuttal).\n\neq.(1), write some intermediate step, as the reader may be familiar with Bregman divergences but not eq.(1) and wonder where it comes from.\n\nthe unnumbered equations between eq.(1) and eq.(2): $R\\in\\cdots$ (use set notations)\n\nL134: Section ?? below (missing reference).\n\nPdim: mention the relation with VC dimension (that is widely known).", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "BVs1RVbBoe1", "reviewer": "Reviewer_Eu9B", "summary": "This paper establishes non-asymptotic error bounds for a density-ratio estimator based on the Bregman divergence. These bounds depend on the approximation error and pseudo-dimension of the underlying function classes. If one assumes the optimal estimator belongs to the Hölder class, combing with existing results on the approximation error of neural networks to Hölder functions, and the pseudo-dimension of neural networks, the authors establish error bounds of neural-network based density-ratio estimators. If the data is concentrated on a low-dimensional manifold, the curse of dimensionality can be alleviated. The authors also apply the error bounds to analyze a telescoping density-ratio estimator.", "questions": "1. Do you have any evidence that the chain defined in the paper has a better or similar performance to the one in [2]?\n2. Can the convergence result in [1] induce similar result on the chain problem defined in the paper or the one in [2], i.e., the chains are better than a single-ratio estimator?", "limitations": "No other major concerns than the ones listed in weaknesses.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThis paper provides a general non-asymptotic bound for the density-ratio estimator, which does not depend on any specific function class. With known neural-network theoretical properties, this general bound can be applied to the deep density-ratio estimator, which is in some sense optimal. The convergence rate is also slightly faster than known result in [1].\n\nWeaknesses:\n1. The paper is not carefully written. Line 134 contains a missing reference. Line 260 uses an abbreviation TDR (I believe it is a typo of TRE?), which is not defined anywhere.\n2. The authors analyze a different telescoping density-ratio estimator, rather than the one in [2], and acknowledge that the techniques used for the chain defined in the paper do not apply to the estimator of interest in [2]. This means that the analysis is only for the problem defined in this paper. The authors should provide some evidence that the chain defined in this paper has a superior or comparable performance to the estimator of interest in [2].\n\n[1]Kato, M. and Teshima, T. Non-negative bregman divergence minimization for deep direct density ratio estimation. In International Conference on Machine Learning, pp. 5320 – 5333, 2021.\n\n[2] Rhodes, B., Xu, K., and Gutmann, M. U. Telescoping density-ratio estimation. In Advances in Neural Information Processing Systems, 2020.", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Reject