Non-Negative Bregman Divergence Minimization for Deep Direct Density Ratio Estimation
Authors: Masahiro Kato
Takeshi Teshima
Venue:  (2021)
Keywords: density ratio estimation
bregman divergence

Abstract: The estimation of the ratio of two probability densities has garnered attention as the density ratio is useful in various machine learning tasks, such as anomaly detection and domain adaptation. To estimate the density ratio, methods collectively known as direct density ratio estimation (DRE) have been explored. These methods are based on the minimization of the Bregman (BR) divergence between a density ratio model and the true density ratio. However, existing direct DRE suffers from serious overfitting when using flexible models such as neural networks. In this paper, we introduce a non-negative correction for empirical risk using only the prior knowledge of the upper bound of the density ratio. This correction makes a DRE method more robust against overfitting and enables the use of flexible models. In the theoretical analysis, we discuss the consistency of the empirical risk. In our experiments, the proposed estimators show favorable performance in inlier-based outlier detection and covariate shift adaptation.

Under review as a conference paper at ICLR 2021
NON-NEGATIN BREGMAN DIVERGENCE MINIMIZA- TION FOR DEEP DIRECT DENSITY RATIO ESTIMATION
Anonymous authors Paper under double-blind review
ABSTRACT
This paper aims to estimate the ratio of probability densities using flexible mod- els, such as sfate-of-the-arr deep neural networks. The density ratio estimation (DRE) has garnered attention as the density ratio is useful in various machine learning tasks, such as anomaly detection and domain adaptation. For estimating the density ratio, methods collectively known as direct DRE have been explored. These methods are based on the minimization of the Bregman (BR) divergence between density ratio model and the true density ratio. However, when using flexible models, such as deep neural networks, existing direct DRE suffers from serious train-loss hacking, which is kind of over-fitting caused by the form of an empirical risk function. In this paper, we introduce a non-negative correction for empirical risk using only the prior knowledge of the upper bound of the density ratio. This correction makes a DRE method robust against train-loss hacking. It enables the use of flexible models, such as state-of-the offte----thh-rrtt deep neural networks. In the theoretical analysis, we show the generalization error bound of the BR di- vergence minimization. our experiments, the proposed methods show favorable performance in inlier-based outlier detection and covariate shift adaptation.
INTRODUCTION
The density ratio estimation (DRE) problem has attracted a great deal of attention as an essential task in data science for its various industrial applications, such as domain adaptation (Shimodaira, 2000; Plank et al., 2014; Reddi et al., 2015), learning with noisy labels (Liu & Tao, 2014; Fang et al., 2020), anomaly detection (Smola al., 2009; Hido et al., 2011; Abe Sugiyama, 2019), two- sample testing (Keziou & Leoni-Aubin, 2005; Kanamori et al., 2010; Sugiyama et al., 201 1a), causal inference (Kato et al., 2020), change point detection in time series (Kawahara & Sugiyama, 2009), and binary classification only from positive and unlabeled data (PU learning; Kato al., 2019). For example, anomaly detection is not easy to perform based on standard machine learning methods such binary classification since anomalous data is often scarce, but it can be solved by estimating the density ratio when training data without anomaly as well as unlabeled test data are available (Hido et al., 2008).
Among various approaches for DRE, we focus on the Bregman (BR) divergence minimization framework (Bregman, 1967: Sugiyama et al., 201 that a generalization of various DRE meth- ods, e.g., the moment matching (Huang et al., 2007: Gretton et al., 2009), the probabilistic classifi- cation (Qin, 1998: Cheng & Chu, 2004), the density matching (Nguyen et al., 2010; Yamada al., 2010), and the density-ratee ratto fitting (Kanamori et al., 2009). Recently, Kato et al. (2019) also pro- posed using the risk of PU learning for DRE, which also can be generalized from the BR divergence minimization viewpoint, as we show below.
However, existing DRE methods mainly adopt a linear-in innar-in-parameter model for nonparametric DRE (Kanamori et al., 2012) and rarely discussed the use of more flexible models, such as deep neural networks, while recent developments in machine learning suggest that deep neural networks can significantly improve the performances for various tasks, such as computer vision (Krizhevsky et al., 2012) and natural language processing (Bengio et al., 2001). This motivates us to use deep neural networks for DRE. However, existing DRE studies have not fully discussed using such state-of-the- art deep neural networks. For instance, although Nam & Sugiyama (2015) and Abe Sugiyama (2019) proposed using neural networks for DRE, their neural networks are simple and shallow.

---

Under review as a conference paper at ICLR 2021
When using deep neural networks in combination with empirical minimization of BR divergence, we often observe a serious over-fitting problem as demonstrated through experiments in Figure 2 of Section 5. We hypothesize that this is mainly because there is no lower bound in the empirically BR divergence approximating by finite samples, i.e., we can achieve an infinitely negative value in Kiryo al. (2017), which reports similar problem in
minimization. This hypothesis is based PU learning. While Kiryo et al. (2017) call this phenomena over-fitting, we refer to it as train-loss hacking because the nuance is bit different from the standard meaning of overfitting.
Here, we briefly introduce the train-loss hacking discussed in the PU learning literature Kiryo et al. (2017). In a standard binary classification problem, we train classifier & by minimizing the fol- lowing empirical risk using {1v, Pi)
Σ +1==+1Je(00 7
n2 1 -
where yi E {+1} is a binary label, X, feature, and is a loss function. On the other hand, in PU learning formulated by du Plessis et al. (2015), because we only have positive data {(v] minimize the following alternative empirical risk:
+1, x and unlabeled data {(ag))=>>
(x(X)))
n Σ E
E (x)())))
n
Cause of train-lass hacking.
where IT is a hhper--ppaaaeee pyper--aramettr representing pyy = +1). Note that the empirical risk (2) is unbiased to the population binary classification risk (1) (du Plessis et al., 2015). While the the empirical risk (1) of the standard binary classification lower bounded under an appropiate choise of f, the empirical risk (2) of PU learning proposed by du Plessis et al. (2015) is not lower bounded owing to the existence of the second term. Therefore, if model is sufficiently flexible, we can significantly
minimize the empirical risk only by minimizing the second term - Σ ((-))x)) without increasing the other terms. Kiryo et al. (2017) proposed non-negative risk correction for avoiding this problem when using neural networks. We discuss this problem again in Section 2 and Figure 1.
In cxisting DRE literature, this train-loss hacking has rarely been discussed, although we often face this problem when using neural networks, mentioned in Section 5. One reason for this is that the existing method assumes a linear-in- linear-nn-parametrr model for a density ratio model (Kanamori et al., 2012), which is not flexible neural networks and do not cause the phenomenon.
To mitigate the train-loss hacking, we propose a general procedure to modify the empirical BR divergence using the prior knowledge of the upper bound of the density ratio. Our idea of the correction is inspired by Kiryo et al. (2017). However, their idea of non-negative correction is only immediately applicable to the binary classification; thus we require non-trivial rewriting of the BR divergence to generalize the approach to our problem. We call the proposed empirical risk the non-negative BR (nnBR) divergence, and it is generalization of the method of Kiryo et al. (2017). In addition, for special case of DRE, we can still use lower bounded loss for DRE (See bounded uLSIF and BKL introduced in the following section). However, such loss also suffers from the train-loss hacking (bounded uLSIF of Figure and BKL-NN of Figure 4). In the case, the train-loss hacking caused because the loss sticks to the lower bound. This type of train-loss hacking also avoided by using the proposed nnBR divergence.
Our main contributions are: (1) the proposal of a general procedure to modify a BR divergence to enable DRE with flexible models, (2) theoretical justification of the proposed estimator, and (3) the experimental validation of the proposed method using benchmark data.
PROBLEM SETTING
Let puu C Rd and de C RRd be the spaces of the d-dimensional covariates {X!")] Timi
1 and Jiz1
[yde] Ride [Xde) Ji=1, respectielly, which are independent and identically distributed (i.i.d.) as {x!") Pon iidd
Jizi
Pau (X) and {X,ee) Rae tidd
Jizl (X), where Pau (X) and (X) probability densities over nu
2

---

Under review as a conference paper at ICLR 2021
Table 1: Summary of methods for DRE(Sugiyama et al., 201 For POLogLoss, we use C
(())
Reference
LSIF
1272
Kanamon et (2009)
Kernel Mean Matching
(1 1/2/2
Greiton et al. (2009)
UKL KLIEP
flogit) -t
Nguyen (2010)
Hlgi())
Sugiyamu el (2008)
Logistic Regression (BKL)
loggt)) (1 log(1 +0
Hastie al, (2001)
PULogLoss
Clog 6) + Ct (log (1) log f) for <
Kato et al. (2019)
and d respectively. Here, "nu" and "de" indicate the numerator and the denominator, Our goal is to estimate the density ratio r" (XX) Puu Pu)(X) To identify the density ratio, we assume the following:
(x)
Assumption 1. The density Pau (x) is strictly positive over the space X the density Pae(X) is strictly positive over the space Mr and n Ç xe In addition, the density ratio r" is bounded from above on pde; R s r" (X) <0.
Note that the assumption x C Xe is typical in the context of DRE. For instance, in anomaly detection with unlabeled test data, de corresponds to sample space including clean and anomaly data and xd corresponds to a sample space only with clean data. Here, we introduce the notation of this paper. Let EEnu and Eddo denote the expectations over Pnu Pmn(X) (X) and (X), respectively. Let Rdw
Enu and Ee denote the sample average over { {xP") } J=m and { (x Jim1" respectively. Let H C fr: Rdd (br, ] be the hypothesis class of the density ratio, where 0 S b, < R < B
2.1 DENSITY RATIO MATCHING UNDER THE BREGMAN DIVERGENCE
naive way to implement DRE would be to estimate the numerator and the denominator densities separately and take the ratio. However, according to Vapnik's principle, should avoid solving a more difficult intermediate problem than the target problem (Vapnik, 1998). Therefore, various methods for directly estimating the density ratio model have been proposed (Gretton et al., 2009; Sugiyama et al., 2008; Kanamori et al., 2009; Nguyen er al., 2010; Yamada et al., 2010; Kato et al., 2019). Sugiyama et al. (2011b) showed that these methods can be generalized as the density ratio matching under the BR divergence.
The BR divergence is an extension of the Euclidean distance class of divergences that share similar properties (Bregman, 1967). Formally, let f (b,., B,) + R be twice continuously differ- entiable convex function with a bounded derivative. Then, the point-wise BR divergence associated with f from t" derivative of f. Now, the discrepancy from the true density ratio function r" to density ratio model r is measured by integrating the point-wiss wise BR divergence as follows (Sugiyama al., 2011b):
defined (t*
f(tt) f(t) - O (t) t), where Of is the
f(r(x)) BRy(r"Ilr) /
Pao (x)(
(3)
We estimate the density ratio by finding function that minimizes the BR divergence defined in (3). Here, we subtract the constant BR Ede (XX)) from (3) to obtain
(r+(r")/r) == (X)(( ((0eXxX)))(((()))))) ((r(x))) -f - (xx((X)0(((XxxX
(4)
Here, Sugiyama et al. (2012) used r" (X))et Pnu for removing rXX),, which is a common tech- nique in the DRE literature. Since BR is constant with respect we have arg min, BR' (r*)lr))) min, BR, (r" [|r). Then, let us define the sample analogue of (4) as
fr((x.) ()(()))))=)((((((()))))))))))))) Enn [
BRy = Eas (o5(F(x)))<(x))
(5)
For hypothesis class H. we estimate the density ratio by solving min,ew Br (r*)l)).
2.2 EXAMPLES OF DRE
Sugiyama al. (2011b) showed that various DRE methods can be unified from the viewpoint of BR divergence minimization. Furthermore, Menon & Ong (2016) showed an equivalence be- tween conditional probability estimation and DRE by BR divergence minimization. In addition,
3

---

Under review as a conference paper at ICLR 2021
derive novel method for DRE from the proposed method of du Plessis et al. (2015) and Kato et al. (2019). We summarize the DRE methods in Table 1. Here, the empirical risks of least- square importance fitting (LSIF), the Selbback-eeible importance estimation procedure (KLIEP),
logistic regression (LR), and PU learning with log Loss (PULogLoss) is given as BR (r) =
- -Bmn Pmm[r((x)]] + 2 (rtc((((X,))))) (RUKL(r) == Edde [r(X.)] Emm [log (r(X)))]. BRBKL(r) = n(X,) ){ and BRpu(r) = -Ede [log (1-r( (x())) + -Ede log T4T(X.) - Enu log [+r(X,)
CE log (r(X,) + log (1 (1-rid r(x,))] where 0 <<< f/. Here, (RISIF(F) and (Rpu(r) correspond to LSIF and PULoggosss, respectively. We can derive the KLIEP and LR from (R and BRRKLL which are called unnormalized Kullback-Leibler (UKL) divergence and binary Kullback-Leibler (BKL) divergence, respectively (Sugiyama et al., 2011b). In BRpu(r), restrict the model as r E (0, 1) and we obtain an estimator Cr" as a result of the minimization of the risk. Details of the existing methods shown in Appendix A.
3 DEEP DIRECT DRE BASED ON NON-NEGATIVE RISK ESTIMATOR
In this section, we develop methods for DRE with flexible models such as neural networks.
3.1 DIFFICULTIES OF DRE USING NEURAL NETWORKS
Training neural networks for DRE by minimizing the empirical BR divergence tends to suffer from an overfitting phenomenon. For example, we show in Section 5 that the LSIF with neural networks (Nam & Sugiyama, 2015) suffers from serious overfitting issue. One possible cause of overfitting of flexible models has been identified to the train-loss hacking as shown by Kiryo et al. (2017) in the context of PU learning (Fig- ure 1). In DRE, the train-loss hacking is also sensible: the term Em,,, [r(x)) can easily diverge to -oo if we try to minimize empirical BR divergence (5) over a highly flexible hypothesis class H. This is because the term is not lower bounded, unlike the loss functions for other machine learning tasks such as classification.
r(x)
reprecents a sample x!" generated from Par(t).
represents sample x/" gensented from Pru(r).
Figure Illustration of the train-loss hacking phenomenon. Given finite data points, sufficienlly flexible model r can easily make the training loss, e.g., BRESIE (r), diverge to -cc.
Here, note that the other term Eet (xX)
(r((.))) does not introduce a sufficient trade-off prevent the divergence
when the hypothesis class is highly flexible (Figure 1).
3.2 NON-NEGATIVE BR DIVERGENCE
Although DRE using flexible models suffers from serious train-loss hacking, we still have strong motivation to use those models for analyzing data such as computer vision and text data. For ex- ample, Nam & Sugiyama (2015) and Abe & Sugiyama (2019) approximated the density ratio with neural networks, and Uehara et al. (2016) applied direct DRE for generative adversarial nets (GANs; Goodfellow et al., 2014), both by minimizing the empirical BR divergence (5). To alleviate the train- loss hacking problem, we propose the non-negative BR divergence estimator. The proposed method inspired by Kiryo et al. (2017), which suggested non-negative correction to the empirical risk of PU learning based on the knowledge that a part of the population risk is non-negative. On the not obvious how to correct the empirical risk because we do not know
other hand, in DRE, which part of the population risk (4) is non-negative. However, this can be alleviated by determining the upper bound R the density ratio r*. With the prior knowledge of Rt we can determine part of the risk of DRE (4) is non-negative and conduct non-negative correction to the empirical risk (5) based on the non-ncgativity of the population risk. Let define f to be function such that @f(t) = (t) f()) + ftt,, where C मे and put the following assumption.
Assumption 2. Assume that f(t)) is bounded from above, and that there exists a constant such that (f(()( (() + A 2 0 for E (b,, B,)-
4

---

Under review as a conference paper at ICLR 2021
Assumption is satisfied by most of the loss functions which appear in the previously proposed DRE methods (see Appendix B for examples). Under Assumption 2, because f(t) is bounded above, the train-loss backing Eun [ -o in the minimization of the empirical risk (5) is caused
by -E EEnu ((0(((())))(X [(r(X)))) -x because
Em (f((((x)))
Emu [f((()))
Emu [ (010f((()))
Bounded
Thus, we succeeded in identifying the part of the empirical risk causing the train-loss hacking- Therefore, by preventing the term from going to infinite negative, we can avoid the train-loss hack- ing. For achieving this purpose, we impose a non-negative correction to the empirical risk (5); that is, under Assumption 2, we restrict the behavior of the problematic term. To incorporate the assumption, we first rewrite the population risk (4) as (r
/ (Pac(X)-Cpmm())) Cpmu (X))
- f(((())))))))))))))))))))))))( A]ax - f f F((x)))axx
Note that we introduce constant A, which is irrelevant to the original optimization problem. Thus, the problematic term is incorporated into (+). Therefore, we next consider a constraint condition on the term (+). Here, let us define (1) 0f((), f(() + A, and (2(() == - -f()) In the above equation, since Assumption 2 implies (t) 2 O, and < C
and (xn
(X) S R imply
Pao (X) Cpmu (X) > 0 for all X E X, we have ʃ {pao(X) Cpma (X) Hei)((((())) dx > 0.
Motivated by this inequality, we propose an empirical risk with the non non-negative correction as niBR, (r) = Enu [(2(r(X))]] + (Bao (Bae (f(((())) [ (e (+(()()))))
where (+) == ma Note that the constraint on (*) not broken in population (infinite samples) but broken in finite samples with causing the train-loss hacking. Our deep direct DRE (D3RE) based on minimizing (r).
Remark (Choice of C). In practice, selecting the hyper- parameter C does not require accurate knowledge of R because any C < 1/R sufficient justify the non-negative correction. How- ever, selecting C' that is relatively much smaller than 1/ R may damage the empirical performance. See Section G.1.1. This remark does not mean that 1/R should not be small; that is, R. is note be small. If 1/R is small, C also can be small. Therefore, we recommend use larger C' more than smaller C.
mBBR Divergence with Existing Methods: The above strategy can be instantiated in various methods previously proposed for DRE. Here, we introduce the non-negative BR divergence estima- tors that correspond to LSIF, UKL, BKL, and PULogLoss follows:
in BRR.ii (r) = -Bmm (X,)) (.²(X,)) + ( Ban [F(()]]
C Eia [-((x,)]
2
BnBRuKI. (r) -Bam [log (r(X,)) - Cr(Xx)] + (Bao [r(X,)) ClEmu (r(X;)1)
r(X,) ) + Cloog (I+r(X)) nnBR = Emuu log [+r(X,))
+ EEde log
1 (T+T(()) ]
+ C'Emm log
(T+((x))
nnBRpu(r) -CiEm [log (r(X,))]+ (CÉm [log (1 (1-r(X3 r(X,)) Edo [log (1 - r(xi)))
More detailed derivation of f is in Appendix B. In Appendix C, we provide the pseudo code of D3RE. For improving the performance heuristically, we use gradient ascending in our main exper- iments. Note that the gradient ascent only slightly improves the performance and the use is not essential. In the experiments in Appendix E and G.1.3, we also show the experimental results without the gradient ascent for readers concerning the effect of the gradient ascent.
5

---

Under review as a conference paper at ICLR 2021
4 THEORETICAL JUSTIFICATION OF D3RE
In this section, we confirm the validity of the proposed method by providing generalization error bound, Given n N and a distribution p. we define the Rademacher complexity R2 of a function class H. R2, (7t) == EyBo (supren Σx= 0er oxr(X,)]], where {a,)i=) are independent uniform sign variables and {X:]=1 Lidd. p. We omit from the notation of BRy when there is ambiguity.
4.1 GENERALIZATION ERROR BOUND ON BR DIVERGENCE
Theorem in Appendix provides generalization error bound under the following assumption. Assumption 3. Let I, == (b,, B.). Assume that there exists an empirical risk minimizer i E argmin,ge 1 and a population risk minimizer F E arg min BRy Assume B, := SuPιer, {max (le, (1), [(()] < xo. Also assume & (resp. (2) is Le, -Lipschitz (resp. Le-- Lipschitz) on Jr. Assume also that ( C. (1 (r(X)) 0 holds.
In order for the boundedness and Lipschitz continuity in Assumption 3 to hold for the loss functions involving a logarithm (UKL, BKL, PU), a technical assumption 6,- > O is sufficient. We obtain theoretical guarantee for D3RE from Theorem in Appendix I by additionally imposing Assump- tion 4 to bound the Rademacher complexities using a previously known result (Golowich et al., 2019, Theorem 1).
Assumption (Neural networks with bounded complexity). Assume that Pou and Pao have bounded supports: su || cc. Also assume that H consists of real-valued neural networks of depth L over the domain X, where each parameter matrix W, has the Frobenius norm at most Bw, 2 0 and with 1- 1-Lipschitz activation functions (oj that are positive-homogenenn (i.c., (o) is applied element-wise and y (at) axpy (t) for all a 2 0).
Under Assumption 4, Lemma 3 in Appendix J reveals Remn (H) = O (OL/VTmu) VTnu) and Re (H) = O1/ /Tae). By combining these with Theorem in Appendix we obtain the following theorem: Theorem (Generalization error bound for D3RE). Under Assumptions 3 and 4, for any 5 (0, 1). we have with probability at least 1 6,
(f) (R)
K1
R2
+ 24 / Nado) + Be
1
(1+
log 8'
Ade
VTnn
7lde
7mm
where K1, K2 are constants that depend on J, Bpacy Brad L, and Bw;:
See Remark in Appendix for the explicit form of this bound, By transforming the BR divergence, Theorem tells us generalization error bounds for various problems. For instance, by defining ((t) as log (1 t) + Ct (log (t) - log (1 t)) for 0 < < 1, the BR divergence (r) becomes the same risk functional of PU learning (see Appendix A for the derivation). Then, the generalization bound is similar to the one shown by Kiryo et al. (2017), i.e., the generalization bounds matches the classification error bound of classification only from positive and unlabeled data. Note that the dependency of the bound is standard for classification risk bound with Lipschitz function (See Corollary 15 of Bartlett& & Mendelson (2003)). Thus, this result implies that the BR divergence minimization with D3RE also minimize the generalization error bound of binary classification.
4.2 ESTIMATION ERROR BOUND ON L NORM
Next, we derive the estimation error bound of f on the 1,2 norm. We aim to derive the standard convergence rate of parameetet regression; that is, under appropriate conditions, the order of || - 1r-rr"lu>>pp. is nearly Op (1/ [/(nae A Rmu) (Kanamori et al., 2012). Note that unlike the gen- eralization emor bound of the BR divergence, which is related to classification problems, to restrict the neural network model to achieve such a convergence rate in general. To the best of knowledge, it is difficult for showing the convergence rate for any neural network models such as ResNet (Schmidt-Hane Hieber, 2020) in a general way. In the following Theorem 1, for multi-layer perception with ReLU activation function (Definition 3), we derive converge rate of 1,2 distance,
need

---

Under review as a conference paper at ICLR 2021
which is the same rate with the nonparametric regression using radial basis function with the Gaus- sian kernel and LSIF loss (Kanamori et al., 2012). This result also corresponds to a tighter gener- alization error bound than Theorem under the model restriction. Note that without such model restriction in Theorem 2, the convergence rate will slower based on the rate of Theorem 1. The proof is shown in Appendix K. To support this result, we empirically investigate the estimator error using an artificially generated dataset with the known true density ratio in Appendix E.
Theorem 2 (L2 Convergence rate), Assume is u-strongly convex. Let H. be defined as in Defini- tion 3, and assume r*
E H. Also assume the same conditions as Theorem 3. Then, for any 7 we have ||i r" (I.p( S Op ((min (Nder Renu)) 1112))))))))) (Nder Anu - 00).
Puu
Pde
EXPERIMENT WITH IMAGE DATA
In this section, we experimentally show how the existing estimators fail to estimate the density ratio when using neural networks and that our proposed estimators succeed. To investigate the perfor- mances, we consider PU learning. For binary classification problem with labels y {-1, +1}, we consider training a classifier only from p(X point in test data sampled from p(X). The goal is maximize the area under the receiver op- erating characteristic (AUROC) curve, which is a criterion used for anomaly detection, by esti- mating the density ratio r" (X) p(X
= +1) and p(X) to find a positive data
+1)/p(X). We construct the positive and neg- ative dataset from CIFAR- 10 (Krizheeesk,, 2009) dataset with 10 classes. The positive dataset comprises 'airplane', 'automobile', 'ship', and 'truck'; the negative dataset comprises 'bird', 'cat', 'deer', 'dog'. 'frog', and 'horse'. We use 1, 000 positive data sampled from p(X | = +1) and 1, 000 unlabeled data sampled from p(X) to train the models. Then, we calculate the AUROCs using 10, 000 test data sampled from p(X). In this case, it is desirable to set C' < 2 because x) x5p(([p==)))005ppiXX x===-)
For demonstrative purposes, we use the CNN 0.5++0.5 BCX +
architecture from the PyTorch tutorial (Paszke et al., 2019). Details of the network structure shown in Appendix D.2. The model is trained using Adam without weight decay and the parameters (31, $2, e) in Kingma & Ba (2015) are fixed at the default of PyTorch, namely (0.9, 0.999, 10 10-5).
First, we compare two of the proposed estimators, unBRpu (nnBR-PU PU) and unBR (nnBR- LSIF), with the existing estimators, BR (PU-NN) and BRESIF (uLSIF-NN). We use the logis- tic loss for PULogLoss. Additionally, we conduct an experiment with uLSIF-NN using naively capped model F(X) = min(r(X), 1/C) (Bounded uLSIF). We fix the hyperparameter C at 1/3. We report the results for two learning rates, 10-4 and x 10-5 We conducted 10 trials, and calculated the average AUROCS. We also compute [Ea[f((), which should close to 1. The
if we successfully estimate the density ratio, because [p(xly = +1)//(X)))(()dd results are Figure 2. all cases, the proposed estimators outperform the other methods. In contract, the unstable behaviors of PU-NN and LISF-NN are caused by the train-loss hacking (also see (Kiryo et al., 2017) Appendix G.I). The experiment also demonstrates that naive cap- ping (Bounded SIF) fails to prevent train-loss hacking and leads suboptimal behavior. A naive capping is insufficient because an unreasonable model such that r r(X,le) = and r(X.") = 1/C still can be a minimizer by making one part of the empirical BR divergence largely negative, e.g., as EEde [x)( E [x)(X)
20
Additional experimental results for sensitivity analysis on the upper bound of the density ratio and comparison with various estimators using nnBR divergence are shown in Appendix G.I.
WNLIER-BASER OUTLIER DETECTION
As an applications of D3RE, we introduce inlier-based outlier detection with experiments using benchmark datasets. Moreover, we introduce other applications such as covariate shift adap- tation in Appendix H. In addition to CIFAR-10, we use MNIST2 (LeCun et al., 1998) and fashion MNIST (FMNIST)² (Xiao et al., 2017). Hido et al. (2008; 2011) applied the direct DRE
'See https: wwwwww/ww...o/./o/////////o toronto. wwt.:o/dddooe/eeeeeeeeeee ST has 10 classes from 0 to 9. See http: //yann..////..../ www.en.cooeeeeeeeeeeeeeee www.exdb/mmi..ttttcee PMN LS has 10 classes. See https: / thub. com/za waacoresearcc//aaaee on-mni
html.
7

---

Under review as a conference paper at ICLR 2021
600
0.00
000
615
0.55
1638-AM
ULSE NM
645
PU-W0 (dherged)
Bounced
245
HUAN
mibi
25
26.
35
1.0
3.0
65-
250
Figure 2: Experimental results of Section 5. The horizontal axis is epoch. and the vertical axis is AUROC. The learning rates of the left and right graphs are 1 x 10 and 1 x 10-5, respectively. The upper graphs show the AUROCs and the lower graphs show Eac[f(X)) which will approach when we successfully estimate the density ratio.
Table 2: Average AUROC curve (Mean) with the standard deviation (SD) over 5 trials of anomaly detection methods. For all datasets, each model was trained on a single class and tested against all other classes. The best figure is in bold.
CTEAR-10
SERIRN LeNet
roRR-I SIP
SORR--PL LeNet
mifi-- SIF
miR--PU WRN
Doep SAD Lohee
CTT WRN
Network
LoNee
WRN
Tnlle: Class
Mean
30
Meat
5.5
51D
Klea0
503
Mesn
3D
Moaa
SScaa
SD"
planz
07745
00066
0:354
10002
8.943
01001
01925
03004
00000
0.827
01055
car
0.957
0.002
8.968
0.001
0.965
0.003
0.887
0.530
0.003
0.856
0.002
0.810
0.014
01066
0.386
0.004
0.909
0.000
0.864
0.008
0.832
0.014
Deep SAD
Network
LeNet
LeNet
LeNet
WRN
LeNet
WRN
3D
T T.hiVVup
0.900
10025
0.981
0031
03665
U354
10000
0.558
UX3T
0350
05007
Truae
0.061
0.000
0.993
0.000
L000
0.000
0.958
0.000
0.998
0.000
0.758
0.032
0.974
0.004
Pullower
0.944
0.012
0.97
0.001
0390
0.001
0.933
010012
0,922
01091
0.617
0.866
0102
0.0015
Drzss
0.973
0.006
0.985
0.001
0.992
0.000
0.991
0.001
0.986
0.000
0.525
0.038
0.643
0.014
Cool
0.558
01006
0.975
0.001
0.965
0.000
0.881
0.003
0.954
0.000
0.027
0.799
0885
0.003
for inlier-based outlier detection: finding outliers in a test set based on a training set consisting only of inliers by using the ratio of training and test data densities as an outlier score. Nam & Sugiyama (2015) and Abe & Sugiyama (2019) proposed using neural networks with DRE for this problem. In relation to the experimental setting of Section 5, the problem setting can be seen as a transductive variant of PU learning (Kato et al., 2019).
We follow the setting proposed by Golan & El- Yaniv (2018) using MNIST, CIFAR-10, and FMNIST. There are ten classes in each dataset; we use one class as the inlier class and all other classes the outliers. For example, in the case of CIFAR 10, there are 5, 000 train data per class. On the other hand, there are 1, 000 test data for each class, which consists of 1, 000 inlier samples and 9, 000 outlier samples. The AUROC is used be detected in the test data. We compare the proposed methods with benchmark methods of deep semi-supervised anomaly detection (DeepSAD) (Ruff et al., 2020) and geometric transformations (GT) (Golan & EI- Yaniv, 2018). The details of each method are shown in Appendix F. To compare the methods fairly, we use the same architectures of neural networks from Golan & EI- El-Yaniv (2018) and Ruff et al. (2020), LeNet and Wide Resnet, for D3RE. The details of the structures are shown in Appendix D. A part of the experimental results with CIFAR-10 and FMNIST are shown in Table due to the limitation of the space. The full results are shown in Table 4 in Appendix G.2. The pro- posed methods result in better AUROCs than the existing methods. The largest performance gain seen in the CIFAR- 10: the mean AUROC is improved by 0.157 on average between the uLSIF-NN and LSBR- Although GT and DeepS are designed for different problem, to the best of our knowledge, these are the state-of-the-an a algorithms, which are not based on DRE.
metric to evaluate whether outlier class can
7 CONCLUSION
We proposed non-negative correction to the empirical BR divergence for DRE. Using the prior knowledge of the upper bound of the density ratio, we can prevent train-loss hacking when using flexible models. In our theoretical analysis, we showed the generalization bound of the algorithm.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Masahiro Abe and Masashi Sugiyama. Anomaly detection by deep direct density ratio estimation. openreview, 2019.
Ryan Prescott Adams. Bayesian online changepoint detection. Technical report, 2007.
S. M. Ali and S. D. Silvey, A general class of coefficients of divergence of one distribution from another. Journal of the Royal Statistical Society, Series B(28):131-142, 1966.
Susan Athey and Stefan Wager. Efficient policy learning. arXiv preprint Xx2:::702.00289900 2017.
Peter L.. Bartlett and Shahar Mendelson. Rademacher and Gaussian complexities: Risk bounds and structural results. In Computational Learning Theory, volume 2111, pp. 224-240. Springer Berlin Heidelberg, 2001.
Peter L Bartlett and Shahar Mendelson. Rademacher and Gaussian complexities Risk bounds and structural results. The Journal of Machine Learning Research, 3:463-482, 2003.
Michèle Basseville and Igor V. Nikiforov. Detection of abrupt changes: theory and application. Prentice Hall information and system sciences. Prentice Hall, 1993.
Yoshua Bengio, Réjean Ducharme, and Pascal Vincent. A neural probabilistic language model. In NeurlPS, pp. 932-938. MIT Press, 2001.
Alina Beygelzimer and John Langford. The offset tree for learning with partial labels. In KDD, pp- 129-138, 2009.
Aurelien Bibaut, Ivana Malenica, Nikos Vlassis, and Mark Van Der Laan. More efficient off off-policy evaluation through regularized targeted learning. In ICML. PMLR, 2019.
Bickel, C. A. J. Klaassen, Y. Ritov, and J. Wellner. Efficient and Adaptive Estimation for Semiparametric Models. Springer, 1998.
Steffen Bickel, Michael Brückner, and Tobias Scheffer. Diseriminative learning under covariate shift. J. Mach. Learn. Res., 10:2137-2152) December 2009. ISSN 1532-4435.
John Blitzer, Mark Dredze, and Fernando Pereira. Biographies, Bollywood, boom-boxes and blenders: Domain adaptation for sentiment classification. Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, June 2007.
L.M. Bregman. The relaxation method of finding the common point of convex sets and its applica- tion to the solution of problems in convex programming. USSR Computational Mathematics and Mathematical Physics, 7(3):200- 217, 1967. ISSN 0041-5553.
E. Brodsky and B.S. Darkhovsky. Nonparametric Methods in Change Point Problems. Mathematics and Its Applications. Springer Netherlands, 1993.
Minmin Chen, Zhixiang Xu, Kilian Q. Weinherger, and Fei Sha. Marginalized denoising autoen- coders for domain adaptation. In ICML, ICML. 12, pp. 1627-1634, Madison, WI, USA, 2012. Omnipress.
kuang-Fu Cheng and C.K. Chu. Semiparametric density estimation under a two-sample density ratio model. Bernoulli, 10, 08 2004.
Victor Chernozhukov, Juan Carlos Escanciano, Hidehiko Ichimura, Whitney K. Newey, and James M. Robins. Locally robust semiparametric estimation, 2016.
Victor Chernozhukov, Denis Chetverikov, Mert Demirer, Esther Duflo, Christian Hansen, Whitney Newey, and James Robins. Double/debiased machine learning for treatment and structural pa- rameters. Econometrics Journal, 21:C1-C68. -668 2018.
Stephen R. Cole and Elizabeth A. Stuart. Generalizing evidence from randomized clinical trials to target populations, American Journal of Epidemiology, 177(1):107-115, 2010.

---

Under review as a conference paper at ICLR 2021
Corinna Cortes and Mehryar Mohri. Domain adaptation in regression. In Algorithmic Learning Theory, pp. 308-,23, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg.
I. Csiszár. Information-type measures of difference of probability distributions and indirect obser- vation. Studia Scientiarum Mathematicarum Hungarica, (2):229-318, 1967.
Marthinus Christoffel du Plessis, Gang. Niu, and Masashi Sugiyama. Convex formulation for learn- ing from positive and unlabeled data. In ICML, pp. 1386-1394, 2015.
Miroslav Dudík, John Langford, and Lihong Li. Doubly Robust Policy Evaluation and Learning. In ICMI, pp. 1097-1104, 2011.
Charles Elkan and Keith Noto. Learning classifiers from only positive and unlabeled data. In ICDM, pp. 213-220, 2008.
Tongtong Fang, Nan Lu, Gang Niu, and Masashi Sugiyama. Rethinking importance weighting for deep learning under distribution shift. In NeurIPS, 2020.
Roman Garnett, Michael A. Osborne, and Stephen J. Roberts. Sequential bayesian prediction the presence of changepoints. In ICML, pp. 345-352, New York, NY, USA, 2009. Association for Computing Machinery.
Izhak Golan and Ran ElnYa.iv. Deep anomaly detection using geometric transformations. In NeurlPS, pp. 9758-9769. Curran Associates, Inc., 2018.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Indeeennnnn Sample Complexity of Neural Networks. 17X1v:1712.0654 [cs, stat], November 2019.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In NeurlPS, pp. 2672-2680.
Curran Associates, Inc., 2014.
A. Gretton, A.J. Smola, J. Huang, Marcel Schmittfull, K.M. Borgwardt, and B. Schölkopf. Covariate shift by kernel mean matching. Dataset Shift in Machine Learning, 131-160 (2009), 01 2009.
M. G. L. Gustafsson. Surpassing the lateral resolution limit by a factor of two using structured illumination microscopy. Journal of Microscopy, 198(2):82-87, 2000.
Jens Hainmueller. Entropy balancing for causal effects: multivariate reweighting method to pro- duce balanced samples in observational studies. Political Analysis, 2012.
Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The elements of statistical learning: data mining, inference and prediction. Springer, 2001.
Kaiming He, Shaoqing Ren Xiangyu Zhang, and Jian Sun. Deep residual learning for image recog- nition. In CoRR, 2015.
E. Hellinger. Neue begründung der theorie quadratischer formen unendlichvielen veränder- lichen. Journal für die reine und angewandte Mathematik, 136:210-271, 1909.
Masayuki Henmi and Shinto Eguchi. A paradox concerning nuisance parameters and projected estimating functions. Biometrika, 2004.
Masayuki Henmi, Ryo Yoshida, and Shinto Eguchi. Importance Sampling Via the Estimated Sam- pler. Biometrika, 2007.
Shohei Hido, Yuta Tsuboi, Hisashi Kashima, Masashi Sugiyama, and Takafumi Kanamori. Inlier- based outlier detection via direct density ratio estimation. pp. 223-232. 12 2008
Shohei Hido, Yuta Tsuboi, Hisashi Kashima, Masashi Sugiyama, and Takafumi Kanamori. Statis- tical outlier detection using direct density ratio estimation. Knowledge and Information Systems, 26(2):309-336, Feb 2011.
Keisuke Hirano, Guido W. Imbens, and Geert Ridder. Efficient estimation of average treatment effects using the estimated propensity score. Econometrica, 7164):1161-1189 2003.
10

---

Under review as a conference paper at ICLR 2021
D. G. Horvitz and D. J. Thompson. A generalization of sampling without replacement from finite universe. Journal of the American Statistical Association, 47((60))663- 685, 1952.
Jiayuan Huang, Arthur Gretton, Karsten Borgwardt, Berharrd Schölkopf, and Alex J. Smola. Cor- recting sample selection bias by unlabeled data. In NewrIPS, pp. 601-608. MIT Press, 2007.
Kosuke Imai and Mare Ratkovic. Covariate balancing propensity score. J. R. Statist. Soc. B, 76(1): 243-263, 2014.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In ICMI, pp. 448-456, 2015.
Nathan Kallus and Masatoshi Uehara. Intrinsically efficient, stable, and bounded off-policy evalua- tion for reinforcement learning. In NeurIPS, pp. 3320-3329. 2019.
Takafumi, Kanamori, Shohei Hido, and Masashi Sugiyama. A least-squares approach to direct importance estimation. Journal of Machine Learning Research, 10(hul):1391-14455 2009.
Takafumi Kanamori, Taiji Suzuki, and Masashi Sugiyama. f 1-divergence estimation and two-sample homogeneity test under semiparametric density-ratee -ratio models. IEEE Transactions on Information Theory, 58, 10 2010.
Takafumi Kanamori, Taiji Suzuki, and Masashi Sugiyama. Statistical analysis of kernel-based least- squares density-ratio estimation. Mach. Learn., 86(3):335- 367,, March 2012. ISSN 0885-6125.
Masahiro Kato. Identifying different definitions of future in the assessment of future economic conditions: Application of pu learning and text mining. arXiv, 2019.
Masahiro Kato, Takeshi Teshima, and Junya Honda. Learning from positive and unlabeled data with selection bias. In ICLR, 2019.
Masahiro Kato, Masatoshi Uehara, and Shota Yasui. Off-policy evaluation and learning for external validity under a covariate shift, 2020.
Yoshinobu Kawahara and Masashi Sugiyama. Change-point detection time-series data by direct density-ratio estimation. In ICDM, 2009.
A. Keziou. Utilisation des divergences entre mesures en statistique inferentielle. Pht) thesis, 2003.
Amor Keziou and Samuela Leoni-Aubin. Test of homogeneity in semiparametric two-sample den- sity ratio models. Comptes Rendus Mathematique C CR MATH, 340:905-910, 06 2005.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR, 2015.
Ryuichi Kiryo, Gang Niu, Marthinus du Plessis, and Masashi Sugiyama. Positive-unlaheled learning with non-negative risk estimator. 1703. 00593 [cs, stat], 2017.
Chris J. Klaassen. Consistent estimation of the influence function of locally asymptotically linear estimators. Ann. Statist., 1987.
Alex Krizhevsky, Learning multiple layers of features from tiny images. 2009.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey Hinton. Imagenet classification with deep convo- lutional neural networks. In NeurIPS, pp. 1097-1105. Curran Associates, Inc., 2012.
S. Kullback and R. A. Leibler. On information and sufficiency. Ann. Math. Statist., 22(1):79-88 1951.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. In Proceedings of the IEEE, 1998.
Michel Ledoux and Michel Talagrand. Probability in Banach Spaces: Isoperimetry and Processes. Springer, Berlin, 1991.
Lihong Li, Wei Chu, John Langford, and Robert Schapire. A contextual-bandde approach to personalized news article recommendation. In WWW, pp. 661-670, 2010.
11

---

Under review as a conference paper at ICLR 2021
Song Liu, Makoto Yamada, Nigel Collier, and Masashi Sugiyama. Change-point detection in time- series data by relative censity-ratio estimation. In Structural, Syntactic, and Statistical Pattern Recognition, pp. 363-372, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg.
Tongliang Liu and Dacheng Tao. Classification with noisy labels by importance reweighting, 2014.
Jane Loevinger. The technic of homogeneous tests compared with some aspects of "scale analysis"
and factor analysis. Psychological Bullerin, 45(6):507-522 1948. ISSN 0033-2909.
Nan Lu, Tianyi Zhang, Gang Niu, and Masashi Sugiyama. Mitigating overfitting in supervised classification from two unlabeled datasets: consistent risk correction approach. 2020.
Colin McDiarmid. On the method of bounded differences. Surveys in Combinatorics, 1989; Invited Papers at the Twelfth British Combinatorial Conference, London Mathematical Society Lecture Note Series, pp. 148-188. Cambridge University Press, 1989.
Aditya Menon and Cheng Soon Ong. Linking losses for density ratio and class-probability estima- tion. In JCML, volume 48, pp. 304-313, New York, New York, USA, 2016
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning- The MIT Press, 2018
Hyunha Nam and Masashi Sugiyama. Direct density ratio estimation with convolutional neural networks with application in outlier detection. IEICE Transactions on Information and Systems, E98.D(5);0033-077) 2015.
Yusuke Narita, Shota Yasui, and Kohei Yata. Efficient counterfactual learning from bandit feedback. AAAI 2019.
Minh Nhut Nguyen, Xiaoli-Li Li, and See- See-Kiong Ng. Positive unlabeled leaning for time series classification. In IJCAI, pp. 1421-1426, 2011.
Xuanl.ong Nguyen, Martin Wainwright, and Michael Jordan. Estimating divergence functionals and the likelihood ratio by convex risk minimization. IEFE, 2010.
Gang Niu, Marthinus Christoffel du Plessis, Tomoya. Sakai, Y. Ma, and Masashi Sugiyama. Theo- retical comparisons of uusabile-unlaaeled learning against positive-negative learning. In NeurIPS, pp. 1199-1207, 2016.
Sebastian Nowozin, Botond Cseke, and Ryota Tomioka. f-gan: Training generative neural samplers using variational divergence minimization. In NeurIPS, pp. 271-279. Curran Associates, Inc., 2016.
Michael Oberst and David Sontag. Counterfactual off-policy evaluation with gumbel- max structural 2019.
causal models. In ICMI., volume 97, pp.
Ulrich Paquet. Empirical bayesian change point detection. Graphical Models, 1995, 01 2007.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, gegh-performance deep learning library. In NeurlPS, pp. 8024-8035 Curran Associates, Inc., 2019.
Judea Pearl and Elias Bareinboim. External validity: From do-calculus to transportability across populations. Statistical Science, 29, 2014.
K. Pearson. On the criterion that a given system of deviations from the probable in the case of correlated system of variables is such that it can reasonably be supposed to have arisen from random sampling. Philosophical Magazine, 5750):157-175, 1900.
Barbara Plank, Anders Johannsen, and Anders Søgaard. Importance weighting and unsupervised domain adaptation of POS taggers: negative result. 2014.
12

---

Under review as a conference paper at ICLR 2021
Jing Qin. Inferences for case-control and semiparametric two-sample density ratio models.
Biometrika, 85(3):619-633 630, 1998.
Jing Qin and Biao Zhang. Empirical-likelin likelihoodd-ased inference missing response problems and
its application in observational studies. Journal of the Royal Statistical Society, 2007.
Sashank Jakkam Reddi, Barnabás Póczos, and Alex J. Smola. Doubly robust covariate shift correc- tion. In AAAI, pp. 2949-2955. AAAI Press, 2015.
P. R. Rosenbaum. The central role of the propensity score in observational studies for causal effects. 70:41-55, 1983.
R. Rosenbaum. Model-based direct adjustment. Journal of the American Statistical Association, 82:387-394, 1987.
Donald B. Rubin. Estimating causal effects of treatments in randomized and nonrandomized studies. Journal of Educational Psychology, 66(5)688,, 1974.
Lukas Ruff, Robert A. Vandermeulen, Nico Gömitz,, Alexander Binder, Emmanuel Müller, Klaus- Robert Müller, and Marius Kloft. Deep semi-supervised anomaly detection. In ICLR, 2020.
Gerard Salton and Michael McGill. Introduction modern information retrieval. 1986.
Johannes Schmidt-Hieber. Nonparametrie regression using deep neural networks with ReLU acti- vation function. 2020.
Hidetoshi Shimodaira. Improving predictive inference under covariate shift by weighting the log- likelihood function. Journal of statistical planning and inference, 90(2):227-244, 2000.
Alex Smola, Le Song, and Choon Hui Teo. Relative novelty detection. In AISTATS, volume of Proceedings of Machine Learning Research, pp. 536-543, Hilton Clearwater Beach Resort, Clearwater Beach, Florida USA, 2009. PMLR.
J.T. Springenberg, A. Dosovitskiy, Brox, and M. Riedmiller. Striving for simplicity: The all convolutional net. In ICLR (workshop track), 2015.
Masashi Sugiyama, Taiji Suzuki, Shinichi Nakajima, Hisashi Kashima, Paul Bünau, and Mo- toaki Kawanabe. Direct importance estimation for covariate shift adaptation. Annals of the Insti- tute of Statistical Mathematics, 60:699-744 02 2008.
Masashi Sugiyama, Taiji Suzuki, Yuta Itoh, Takafumi Kanamori, and Manabu Kimura. Least- squares two-sample test. Neural networks the official journal of the International Neural Net- work Suciety, 24:735-51, 04 201 la.
Masashi Sugiyama, Taiji Suzuki, and Takafumi Kanamori. Density ratio matching under the breg- man divergence: A unified framework of density ratio estimation. Annals of the Institute of Statistical Mathematics, 64, 10 201
Masashi Sugiyama, Taiji Suzuki, and Takafumi Kanamori. Density Ratio Estimation in Machine Learning. Cambridge University Press, New York, NY, USA, 1st edition, 2012.
Zhiqiang Tan. Bounded, efficient and doubly robust estimation with inverse weighting. Biometrika, 2010.
Yuta Tsuboi, Hisashi Kashima, Shohei Hido, Steffen Bickel, and Masashi Sugiyama. Direct density ratio estimation for large-scale scale covariate shift adaptation. Journal of Information Processing, 17: 138-155, 2009. doi: 10.2197/ipsjjp.17..5.
M. Uehara, I. Sato, M. Suzuki, K Nakayama, and Y. Matsuo. Generative adversarial tets from density ratio estimation perspective. 2016. URL https: pittpp:://axxiie //taxiiivv.////////////////aaavl watps/.orr//a////1//// 02920.
Sara van de Geer. Empirical Processes in E-Esimmation, volume Cambridge university press, 2000.
Vladimir Naumovich Vapnik, Statisfical Learning Theory. Wiley, September 1998.
13

---

Under review as a conference paper at ICLR 2021
J. Wainwright. High-Dimenniionll Statistics: A Non-Asymptotic Viewpoint. 1st edition, 2019.
Yu-Xiang Wang, Alekh Agarwal, and Miroslav Dudik. Optimal and adaptive off-policy evaluation in contextual bandits. In ICML, pp. 3589-3597, 2017.
Richard Wyss, Alan R. Ellis, M. Alan Brookhart, Cynthia J. Girman, Michele Jonsson Funk, Robert LoCasale, and Til Stürmer. 'he Role of Prediction Modeling in Propensity Score Estimation: An Evaluation of Logistic Regression, bCART, and the Covariate- Bartiiin- Propensity Score.
American Journal of Epidemiology. 2014.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnis a novel image dataset for benchmark- ing machine learning algorithms. ArXiv,
2017.
Makoto Yamada and Masashi Sugiyama. Direct importance estimation with gaussian mixture models. IEICE Transactions on Information and Systems, E92.D((0)2219922162 2009, doi: 1111587/transin..222.2222
Makoto Yamada, Masashi Sugiyama, Gordon Wichern, and Jaak Simm. Direct importance estima- tion with a mixture of probabilistic principal component analyzers. IEICE Transactions, 93-D: 2846-2849, 2010.
Kenji Yamanishi and Junnichi Takeuchi. A unifying framework for detecting outliers and change points from non-stationary time series data. pp. 676-681, 12 2002.
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. In Proceedings of the British Machine Vision Conference (BMVC), pp. 87.1-87.12. BMVA Press, September 2016.
Wenjing Zheng and Mark J van der Laan. Cross-validated targeted minimum-loss-ben based estima- tion. In Targeted Learning: Causal Inference for Observational and Experimental Data, Springer Series in Statistics. 2011.
14

---

Under review as a conference paper at ICLR 2021
A DETAILS OF EXISTING METHODS FOR DRE
In this section, we overview examples of DRE methods in the framework of the density ratio match- ing under BR divergence.
Least Squares Importance Fitting (LSIF)): LSIF minimizes the squared error between density ratio model r and the true density ratio defined as follows (Kanamori et al., 2009):
(T) Ea.((r(X) - (X))² Eao((r" (X))² 2 [x()] + Ed ((r()))
In the unconstrained LSIF (uI.SIF) (Kanamori et al., 2009), we ignore the first term in the above equation and estimate the density ratio by the following minimization problem:
(x)(((( - Ê... (r(X) R
= arg min rEH
(6)
where R regularization term. This empirical risk minimization is equal to minimizing the empirical BR divergence defined in (5) with f(() (1 101--117 1)
Unnormalized Kullback-Leinn (UKL) Divergence and KL Importance Estimation Pro- cedure (KLIEP): The KL importance estimation procedure (KLIEP) is derived from the un- normalized Kullback-Leiblee (UKL) divergence objective (Sugiyama et al., 2008; Nguyen et al., 2010; Tsuboi et al., 2009; Yamada & Sugiyama, 2009; Yamada et al., 2010), which uses [(t) l (lg(() L. Ignoring the terms which are irrelevant for the optimization, we obtain the unnor- malized Kullback-Leide (UKL) divergence objective (Nguyen al., 2010; Sugiyama al., 2012) as
BRUKL = Ede [r(x)] Ena [log (r(X))
Directly minimizing UKL proposed by Nguyen et (2010). The KLIEP also solves the same problem with further imposing constraint that the ratio model r r(X) is non-negative for all X and normalized as
Eao [r(X]]
Then, following is the optimization criterion of KLIEP (Sugiyama et al., 2008):
max Eau [log (r(x))]
s.l. EdG [r(X)] = and r(X) 2 0 for all X.
Logistic Regression: By using f(t) = log(t) - (1 + t) log(1 + t), we obtain the following BR divergence called the binary Kullback-Leibler (BKL) divergence:
BR (r) = Eage log
(1+ (1+7(x))
Ena
log
1 (++(x)) )
r(X)
This BR divergence is derived from a formulation based on the logistic regression (Hastie et al., 2001; Sugiyama al., 201 1b).
PU Learning with the Log Loss: Consider binary classification problem and let X and y
(+1} be the feature and the label of a sample, respectively. In PU learning, the goal is to train a classifier only using positive data sampled from y( = +1), and unlabeled data sampled from p(X) in binary classification (Elkan & Noto, 2008). More precisely, this problem setting of PU learning is called the case-control scenario (Elkan & Noto. 2008; Niu al., 2016). Let be the set of measurable functions from X' to [e, ee]. where e (0, 1/2) is a small positive value. For a loss function & x (=1} + R+ du Plessis al. (2015) showed that the classification risk of g E in the PU problem setting can be expressed as
(g) = TT (ll)(X), +1) l(g(X), -1) -1)pp( p(X y = +1)dX + -1)(())
15

---

Under review as a conference paper at ICLR 2021
According to Kato et al. (2019), we can derive the following risk for DRE from the risk for PU learning (7) as follows:
BR (g) = Eu |- log (o(X)) + log (1 +(x))) Ede [log (1 s(Xi)),
R
and Kato et al. (2019) showed that g" = arg min mingee
geg BR satisfies the following:
Proposition It holds almost everywhere that
(X D2),
9" (x)
C
(X E D1 n D2),
(X D1),
S (1 - c))) where C R D1 = {X Pmm (X) 2 ePde (X)),, and D2 = (1-)))x()
Using this result, we define the empirical version of (g) follows:
(r [[r) C. [- log (r(X))) + log (1 --x((( Ede [log (1_()1 r(Xi)]
Note that for f() in the BR divergence, we use
f(t) C'log (1 - + Ct (log (t) log (1-1))
Then, we have
C 0f(() 1-1
+ C(log(() - -o)(1-t)) Ct 1-1)
Therefore, we have
(r = Ede - Em ( [of(((3))]
E.n r-x( + +Cr(())(og(((())) - 1og(1-r(Xi)) r(xi)) + cr?(3)) (M(x)) + 1 - -
Cr(Xi)
Edee
Ede
log (1 r(X.)) + Cr(X,) (log (r(X.) log (1-x11
C
)
Emn
--x(X,) + C(log(r(()))) log(1 ((x))))))))))))))))))))))))(())) Cr(X,) r(x,)
+
1 - r(x,) 1_x(x.)
Cr(X,)
Cr(X,)
Ede
r-r(X;) + +C+(X))(og((((x)) - -oog://og((())))oooooooo----ea
-og(1 r(xi))) + 1 1- r(X,)
Ede
log (1 r(X.)) + Cr(X;) (log (r(X.)) log (1 -((xx)))
Emn
1- r(X,) + C(log(r(x:)) - log(1 - r((x))) + 1- r(x))
EEde
log (1 - r(x,)) CEnu log(r(X.)) - log(1 r( r(xi))
Remark (DRE and PU learning). Menon & Ong (2016) showed that minimizing proper CPE loss is equivalent to minimizing BR divergence to the true density ratio, and demonstrated the viability of using existing losses from one problem for the other for CPE and DRE. Kato al. (2019) pointed out the relation between the PU learning and density ratio estimation and leveraged solve sample selection bias problem in PU learning. In this paper, we introduced the BR divergence with f(t) = log (1 - Ct) + C't (log (Ct) log (1 - -Ct),, inspired by the objective function of PU learning with the log loss. the terminology of Menon Ong (2016), this f results in DRE objective without a link function. In other words, it yields direct DRE method.
B EXAMPLES OF f
Here, we show the examples of if such that Of = C(Of()tt-f()) fft), where f(t) bounded from above, and (f()) f(() is non-negative.
16

---

Under review as a conference paper at ICLR 2021
First, we consider f(t) (t - 1)2/2, which results in the LSIF objective. Because 0f(t) 1, we have
1-1= - 1)l (1- (())
C - 1
C
+ -1)=-C((-1))((111)7 +
The function a concave quadratic function, therefore is upper bounded. Note that uLSIF satisfies the Assumption 2 with A & since θf((), f(() + - 312² and Assumption 3 automatically holds. Also note that the term A is irrelevant to the optimization.
Second, we consider f(t) t log(t) which results in the UKL or KLIEP objective. Because (t) = ltg(t), we have
log(t) = ((og(()) - log(() +1) F(1)
+ f(t)= -tC + log(t).
We can easily confirm that the function is upper bounded by taking the derivative and finding that 1 1/C gives the maximum. Note that UKL. satisfies the Assumption with since (f))
f(t = t (tg(()) llg((t) + = and Assumption 3 automatically holds.
Third, we consider ftt) = log(() - (1 + log(1 + t). which is used for DRE based on LR or BKL.
Because Ot(() log(t) log(1 t), we have
log(t) - log(1 + 1) = C((log(()) - log(1 + 1)) - t (lg(() + (1 + log(1
+ +1)) + f(1)
C
t
+ f(t) = -C C' [log(1 + +)) + ltg(t) - log(1 + t) log
+ log 1+t
1+1
We can easily confirm that the function is upper bounded as the terms involving f always add up be negative. Note that BKL satisfies the Assumption with A since 0f(t)t f(t) (Iog(t) log(1 + t))t t (tg + (1 +) log(1 + = log(1 + t), and Assumption 3 automatically holds.
Fourth, we consider DRE based on PUL.g.
By setting ((t) log (1 1) +
Ct (log (4)-lop log (1) we can obtain the same risk functional introduced Kiryo et (2017). Note that PÚLog satisfies the Assumption 2 with A = 0 since 0f(t)t f(t) log(1 t) with
t < 1, and Assumption automatically holds.
C IMPLEMENTATION
The algorithm for D3RE described in Algorithm 1. For training with large amount of data, we adopt the stochastic optimization by splitting the dataset into mini-batches. In stochastic optimiza- tion, we separate the samples into N mini-batches as (fx Ji=1 where Rnu,f and ride,j are the sample sizes each mini-batch. Then, we consider taking sam- ple average each mini-batch. Let E and Eye be sample averages over {xT") ) and Rdeaj {x("e) Jim1 In addition,
Rau.s {X_e) Ji=1 ) (j 1,..., N,
regularization such LI and L2 penalties, denoted by R(r). For improving the performance, we heuristically employ gradient ascent from Kiryo et al. (2017) when Eee (r(X)) CLEE [ex (r())) becomes less than 0, i.e., update the model in the direc- tion that increases the term. Let us that our proposed method is agnostic to the optimization procedure, and other methods such as plain gradient descent can be combined with our method. We consider that further theoretical investigation of the optimization procedure is out of scope.
D NETWORK STRUCTURE USED IN SECTIONS AND 6
We explain the structures of neural networks used in the experiments.
D.1 NETWORK STRUCTURE USED IN SECTIONS 5
In Section 5, we used CIFAR-10 datasets. The model was a convolutional net (Springenberg et al.,
2015): (32 x 32 x C)- x 6,3)-C(3 x 16, 1288-841,, where the input a 32 32 RGB image,
17

---

Under review as a conference paper at ICLR 2021
Algorithm D3RE
Input:
Training data {X!mm ji= and {x:ee [
i==1 the algorithm for stochastic optimization such
as Adam (Kingma & Ba, 2015), the learning rate 7, the regularization coefficient A.
Output: A density ratio estimator A. while No stopping criterion has been met: do
Create N mini-batches {(XTT))
Pnu.j Timl
{x Jiml [
for = 1 to N do
if Ede [f((((X)) Cênu [<)(( 2 0: then
Gradient decent: set gradient V, E (=(((())) + (e (())(()))))) -CE, (1((())))) XR(r))
else
Gradient ascent: set gradient v - (E, XR(r))
end if
Update r with the gradient and the learning rate end for end while
C(3 6, 3) indicates that 3 channels of 3 6 convolutions followed by ReLU is used. This structure has been adopted from the tutorial of Paszke et al. (2019).
D.2 NETWORK STRUCTURE USED IN SECTIONS 6
Inlier-based Outlier Detection: We used the same LeNet-type CNNs proposed in Ruff et al. (2020). In the CNNs, each convolutional module consists of convolutional layer followed by leaky ReLU activations with leakiness a = 0.1 and (2 x ma-mxx--ol For MNIST, we em- ploy CNN with two modules: (32 32 3)-C(3 x 32, (3- 64, 5)-C(64 128, 5)-1. For CIFAR-10 we employ the following architecture: (32 x 32 x 1)-C(1 x 8, 5)-C(( x 4, 5)-1 with batch normalization (loffe & Szegedy, 2015) after each convolutional layer.
The WRN architecture was proposed in Zagoruyko & Komodakis (2016) and it is also used in Golan Yaniv (2018). This structure improved the performance of image recognition by de- creasing the depth and increasing the width of the residual networks (He et al., 2015). We omit the detailed description of the structure here.
Covariate Shift Adaptation: We used the 5-layer perceptron with ReLU activations. The struc- ture is 10000-100--10001000001100
E EXPERIMENTS FOR REGRESSION ERROR USING SYNTHETIC DATASET
In this experiment, investigate the regression error of the proposed D3RE. We compare our method with the ul.SIF (Kanamori et al., 2009) with reproducing ker- nel Hilbert space (Kanamori et al., 2012). For uLSIF, we use /stps://githute
open code of For D3RE, we use unBR-LSIF and 3-layer perceptron with ReLU activation function, where the number of the nodes of the middle layer is 100. We conducted anBR-LSIF for all C' E {0.8, 1, 2, 3, 4, 5, 10, 15, 203. We also compare these method with naively implemented LSIF with the 3-layer perceptron.
Let the dimension of the domain be d and
(8) (9) where ((, Σ) denotes the multivariate normal distribution with mean j and E, nz and de are d d-dimensional vector such that nT (1,0...., and t (0, 0, ........o .0 and Ia d- dimensional identity matrix. We fix the sample sizes at nun = nae = 1, 0.0 and estimate the density ratio using SIF, LSI,, and D3RE (nnBR-LSIF))
Pnu (X) = (X; Ia):
(X) (X; Ia).
18

---

Under review as a conference paper at ICLR 2021
IIBBRLLIF
nnBR-LSiF
EnBR.PU
AnBR.PU
NN
uLSIF -NN
PU-NN (diverged)
Bounded uLSIF
Bounded uLSIF
100
200
300
400
500
-10
300
500
0.95
0.95
0.90
0.90
MNBR-LSIF
AnBR-LSIF
0.75
MnBR.PU
0.75
AnBR-PU
0.70
ULSIF
0.70
PU-NN (diverged)
PU-NN
0.65
Bounded uLSIF
0.65
Bounded uLSIF
0.60
0.60
100
200
300
400
500
0
100
200
300
400
500
Figure 3: The learning curves of the experiments Section 5. The horizontal axis epoch. The ver- tical axes of the top figures indicate the training losses. The vertical axes of the bottom figures show AURPC for the test data. The bottom figures are identical ones displayed Section 5.
DnBR-LSIF (1.2)
AnBR-PU (1.2)
DABR-LSIF (1.5)
AnBR-PU
AABR-LSIF (3.0)
nnBR-PU (3.0)
AnBR-LSIF (5:0)
nnBR-PU (5.0)
500
100
400
500
0.96
MIBR-LSIF
0.94
NABR-PU
0.92
DKL-NN
AnDR UKL
NOBR-BKL
0.88
0.86
Figure 4: Top figures: the detailed experimental results for Section G.I.I. Bottom figure: the detailed experimental results for Section G.1.2. The horizontal axis is epoch, and the vertical axis is AUROC.
For performance metric, we use the mean squared error (MSE) and the standard deviation (SD) calculated over 50 trials. Note that in this setting, we can calculate the true density ratio r". The results are shown Table 3. The lowest MSE methods are highlighted in bold. As shown in Table 3, the proposed 1nBR-LSIF methods estimate the density rate better than the other methods; that is, achieve lower MSEs. Note that this setting, the upper bound of r" is infinite because we do not restrict the support of X for simplicity. In the many cases of the results, nnBR-LSIF achieve the best performance around C' = 2. This result implies that we do not need to know the exact for better estimation; that is,
ignore some "out-lier" samples, which cause train-loss hacking.
19

---

Under review as a conference paper at ICLR 2021
Table 3: Experimental results (MSEs and SDs) of DRE using synthetic datasets.
D3RE (anBR-I.a)
uL.IIF
LSIF-NN
C
C=1 1111
C
C=
C=
C
C 10
C 15
C 20
MSE
2.378
1.272
1,750
1.695
1.191
0.964
0,873
0.833
0.948
1.079
1.170
dim 10
1.143
0.413
0.523
0.487
0.459
0.387
MSE
1.844
2.694
1,704
1.446
1,307
1,272
1,337
1.444
2,066
2.697
3,098
SD
0.372
0.409
0,380
0.368
0.328
0.297
0.283
0.288
0.285
0.346
0.374
dim
30
MSE
SD
0.456
1,786
0.460
3.724
0.459
0.449
1.747
1.488
0.411
0.400
1.377
0.401
1.798
0.379
2,019
0.370
3.238
0.464
4.306
0.543
5.432
dim
50
MSE
1,791
8.717
1817
1.753
1.609
1,118
2.194
2.614
4.848
6.955
8,798
SD
0.562
1.518
0.555
0.513
0.503
0.484
0.465
0.597
0.672
MSE
1.723
4.849
1.748
1.693
1.626
1,360
2.226
2,709
5.528
8.605
11,557
dim
100
0,574
4.182
0.575
0.571
0.540
0.532
0.495
0.563
0.672
0.790
1.140
F EXISTING METHODS FOR ANOMALY DETECTION
This section introduces the existing methods for anomaly detection. DeepSAD is method for semi- supervised anomaly detection, which tries to take advantage of labeled anomalies (Ruff et al., 2020). GT proposed by Golan & El- Yania (2018) trains neural networks based on a self-labeled dataset by performing 72 geometric transformations. The anomaly score based on GT is calculated based on the Dirichlet distribution obtained by maximum likelihood estimation using the softmax output from the trained network.
In the problem setting of the DeepSAD, have access small pool of labeled samples, e.g. subset verified by some domain expert as being normal or anomalous. In the experimental results shown in Ruff et al. (2020) indicate that, when the other methods. However, in our experimental results, such samples are not assumed to be avail- able, hence the method does not perform well. The problem setting of Ruff al. (2020) and ours are both termed semi- semi-supervised learning in anomaly detection, but the two settings are different.
such samples, the DeepSAD outperforms
G DETAILS OF EXPERIMENTS
The details of experiments are shown in this section. The description of the data is as follows:
MNIST:
The MNIST database is one of the most popular benchmark datasets for image classifi- cation, which consists of 28 x 28 pixel handwritten digits from 0 to 9 with 60, 000 train samples and 10, 000 test samples (LoCun et al., 1998).
CIFAR-10: The CIFAR-10 dataset consists of 60, 000 color images of size 32 x 32 from 10 classes, each having 6000. There are 50, 000 training images and 10, 000 test images (Krizhevsky et al., 2012).
fashion-MNI The fashi ON-MNTST dataset consists of 70, 000 grayscale images of size 28 x 28 from 10 classes. There are 60, 000 training images and 10, 000 test images (Xiao al., 2017).
Amazon Review Dataset: Blitzer al. (2007) published the text data of Amazon review. The data originally consists of a rating (0-5 stars) for four different genres of products in the electronic commerce site Amazon.com: books, DVDs, electronics, and kitchen appliances. Blitzer et al. (2007) also released the pre- pre-processed and balanced data of the original data. The pre-processed data consists of text data with four labels 4, and We map the text data into 10, 000 dimensional data by the TF-IDF mapping with that vocabulary size. In the experiment, for the pre-proue pre-processed data, we solve the regression problem where the text data are the inputs and the ratings 1, 2, 4, and 5 are the outputs. When evaluating the per- formance, following Menon Ong (2016), we calculate PD (=I-AUROUC) by regarding 4 and 5 ratings as positive labels and 1 and 2 ratings as negative labels.
G.1 EXPERIMENTS WITH IMAGE DATA
We show the additional results of Section 5. Figure 3, we show the training loss of LSIF-based methods to demonstrate the train-loss hacking phenomenon caused by the objective function without
20

---

Under review as a conference paper at ICLR 2021
0.8
0.55
0.90
0.90
0.83
0.85
0.03
MnBRILSI
0.00
InDRILSIF
0.73
0.75
0.79
0.70
FUNN veleeredd
PU-NN
0.6
Sounded u6.51
0.65
Bounded ULSP
0.99
100
A02
300
0.60
120
200
5.0
4.-
IIBR PU
3.-
35-
PU-NW (diverged)
ULSIF NN
Boundeed ULSIP
UUSIT NN
PU-11N
2.5
24
1.5
18
0.5
0.5
1000
2003 3000 400 300
Figure 5: Experimental results of Section 5 without gradient ascent/descent heuristic. The horizontal axis is epoch, and the vertical axis is AUROC. The learning rates of the left and right graphs are 1 10-4 and x 10-5, respectively. The upper graphs show the AUROCs and the lower graphs show Eac [FX)], which will approach 1 when successfully estimate the density ratio.
lower bound. In Figure 3, even though the training loss of uLSIF-NN and that of bounded uLSIF decrease more rapidly than that nnBR-LSIF, the test AUROC score (the higher the better) either drops or fails to increase. These graphs are the manifestations of the severe train-loss hacking in DRE without our proposed device.
G.1.1 EMPIRICAL SENSITIVITY ANALYSIS ON THE UPPER BOUNDS OF THE DENSITY RATIO
Next, we investigate the sensitivity of D3RE to the hyperparameter C. We use mnBR-LSIF and nnBR-PU as Section 5, but vary the hyperparameter in (1/1.2, 1/1.5, 1/2.0.1 1/.00.1//500) The other settings remain unchanged from the previous section. These results shown in Figure 4. For R = 2.0, the estimator show a better performance when 1/C is close to 2.0.
G.1.2 COMPARISON WITH VARIOUS ESTIMATORS USING NNBR DIVERGENCE
Let UKL-NN and BKL-NN be DRE method with the UKL and BKL losses with neural networks without non-negative correction. Finally, we examine the performances of unBR-LSIF, nnBR-PU UKL-NN, BKL-NN, nnBR-UKL, and LmBR-BKL. The learning rate 1 10 4, and the other settings were identical to those in the previous experiments. These results are shown in Figure 4. UKL-NN and BKL-NN also suffer train-loss hacking although BKI. loss seems be more robust against the train-loss hacking than the other loss functions Although anBR-UKL. and nnBR-BKI. show better performance in carlier epochs, nnBR-LSIF and nnBR-PU appear more stable.
G.1.3 RESULTS WITHOUT GRADIENT ASCENT
We also show the experimental results without the gradient ascent heuristic. Figure 5 corresponds to the Figure 2 without the gradient ascent heuristic. Figure 6 corresponds the Figure 3 without the gradient ascent heuristic. Figure 7 corresponds to the Figure 4 without the gradient ascent heuristic. As shown these experiments, although the gradient ascent/descent heuristic improve the performance, there is no significant difference between empirical performance with and without the heuristic. Therefore. readers concern the theoretical guarantee, they can use the plain gradient descent algorithm; that is, naively minimize the proposed original empirical nnBR risk.
recommend practitioners use the gradient ascent/descent heuristic, but
G.2 EXPERIMENTS OF WLLIERBASSE OUTLIER DETECTION
In Table 4, we show the full results malier-based outlier detection. In almost the cases, D3RE for inlier-based outlier detection outperforms the other methods. As explained in Section F, consider that DeepSAD does not work well because the method assumes the availability of the labeled anomaly data, which is not available in problem setting.
21

---

Under review as a conference paper at ICLR 2021
MOBR-LSIF
nnBR-LSIF
-6
MNBR-PU
-6
nnBR-PU
ULSIF-NI MIN-NN
ULSIF-MN -NII-NNN
PU-NN (diverged)
PU-NN
Bounded ULSIF
Bounded
-10
200
400
500
-10
200
300
500
0.90
0.90
0.85
0.85
0.80
0.80
AnBR-LSIF
MMBR-LSIF
0.75
0.75
0.70
U.SIF NN
0.70
ULSIF -NN
PU-NN (diverged)
PU-NN
Bounded uLSiF
Bounded uLSIF
100
200
300
400
500
100
200
300
400
500
Figure 6: The learning curves of the experiments in Section 5 without gradient ascent/descent heuris- tic. The horizontal axis epoch. The vertical axes of the top figures indicate the training losses. The vertical axes of the bottom figures show the AURPC for the test data. The bottom figures are identical the ones displayed in Section 5.
0.96
AnBR-LSIF (1.2)
AUBR (1.2)
0.94
11.5)
AnBR-LSIF (2.0)
AnBR-PU (2.0)
AnBR-LSIF (3.0)
AnBR-PU (3.0)
(5.0)
AnBR.PU (5:0)
0.90
0.88
0.86
0.86
0
100
200
300
400
500
100
200
300
400
500
0.96
nnBR-LSIF
0.94
AnBR-PU
UKL-NN
BKL-NN
NnBR UKL
0.90
nnBR-BKL
Nyh Virpaa
0.86
(841
100
200
300
400
500
Figure 7: Top figures: the detailed experimental results for Section G.1.1 without gradient as- cent/descent heuristic. Bottom figure: the detailed experimental results for Section G.1.2. The horizontal axis is epoch, and the vertical axis is AUROC.
Remark 3 (Benchmark Methods), Although GT is outperformed by our proposed method, the problem setting for the comparison not in favor of GT as does not assume the access to the test data. Recently proposed methods for semi-supervised anomaly detection by Ruff et al. (2020) did not perform well without using other side information used Ruff et al. (2020). On the other hand, there is other competitive methods in this problem setting, the best of our knowledge.
22

---

Under review as a conference paper at ICLR 2021
Table 4: Average area under the ROC curve (Mean) of anomaly detection methods averaged over trials with the standard deviation (SD). For all datasets, each model was trained on the single class, and tested against all other classes. The best performing method in each experiment is in bold. SD: Standard deviation.
MNIST
ULSIF-NN
anBR-LSIF
nnBR-PU
naBR-LSIF
naBR-PU
Deep SAD
GT
Network
LeNet
LeNet
LeNet
WRN
WRN
LeNet
WRN
Inlier Class
Mean
SD
Mcan
SD
Mcan
Mean
SD
Mcan
SD
Mcan
SD
Mcan
SD
0
0.999
0.000
0.997
0.000
0.999
0,000
1,000)
0.000
1,000
0.000
0.592
0.051
0,963
0.002
1
1,000
0.000
0.999
0.000
1.000
0.000
1.000
0.000
1,000
0.000
0.942
0.016
0.517
0.039
2
0.997
0.001
0.994
0.000
0.997
0.001
1.000
0.000
1.000
0.001
0.447
0.027
0.992
0.001
3
0.997
0.000
0.995
0.001
0.998
0.000
1.000
0.000
1,000
0.000
0.562
0.035
0.974
0.001
4
0.998
0.000
0.997
0.001
0.999
0.000
1.000
0.000
1.000
0.000
0.646
0.015
0.989
0.001
5
0.997
0.000
0.996
0.001
0.998
0.000
1.000
0.000
1,000
0.000
0.502
0.046
0.990
0.001
0.997
0.001
0.997
0.001
0.999
0.000
1.000)
0.000
1,000
0.000
0.671
0.027
0.998
0.000
7
0.996
0.001
0.993
0.001
0.998
0.001
1.000)
0.000
1.000
0:001
0.685
0.032
0.927
0.004
8
0.997
0.000
0.994
0.001
0.997
0.000
0.999
0.000
0.999
0.000
0.654
0.026
0.949
0.002
9
0.993
0.002
0.990
0.002
0.994
0.001
0.998
0.001
0.998
0.001
0.786
0.021
0.989
0.001
CIFAR 10
uLSIF-NN
noBR-LSIF
nnBR-PU
nnBR-LSIP
nnBR-PU
Deep SAD
GT
Network
LeNet
LeNet
LeNet
WRN
WRN
LeNet
WRN
Intier Class
Mccan
SD
Mcan
SD
Mcan
SD
Mcan
SD
Mcan
SD
Mean
SD
Mcan
SD
plane
0.745
0.056
0.934
0.943
0.001
0.925
0.004
0.923
0.001
0.627
0.066
0.697
0.009
0.758
0.078
0.957
0.002
0.968
0.001
0.965
0.002
0,960
0.001
0.606
0.018
0.962
0.003
hird
0.768
0.012
0.850
0.007
0.878
0.004
0.844
0.004
0.858
0.004
0.404
0.006
0.752
0.002
0.745
0.037
0.820
0.003
0.856
0.002
0.810
0.009
0.841
0.002
0.517
0.018
0.727
0.014
deer
0.758
0.036
0.886
0.004
0.909
0.002
0.864
0.008
0.872
0.002
0.704
0.052
0.863
0.014
dog
0.728
0.103
0.875
0.004
0.906
0.002
0.867
0.005
0.896
0.002
0.490
0.025
0.873
0.002
frog
0,750
0,060
0,944
0.003
0.958
0.001
0:948
0.004
0.948
0.001
0.744
0.014
0.879
0.008
horse
0.782
0.048
0.928
0.003
0.948
0.002
0.921
0.007
0.927
0.002
0.519
0.015
0.953
0.001
ship
0.780
0.048
0,958
0.003
0.965
0.001
0.964
0.002
0.957
0.001
0.430
0.062
0.921
0.009
truck
0.708
0.081
0.939
0.003
0.955
0.001
0.952
0.003
0.949
0.001
0.393
0.008
0.911
0.003
FNNIST
uf UIFIF-NN
mnBR-LSIF
InBR-PU
naBR-LSIF
nnBR-PU
Deep SAD
GT
Network
LeNet
LeNet
LeNet
WRN
WRN
LeNet
WRN
Inlier Class
Mean
SD
Mean
SD
Mean
SD>
Mean
STS
Mcan
SD
Mean
SD
Mean
SD
T-shirthop
0.960
0.005
0.981
0.001
0.985
0.000
0,984
0.001
0.982
0.000
0.558
0.033
0.890
0.007
Trouser
0.961
0.010
0.998
0,000
1.000
0.000
0.998
0.000
0.998
0.000
0.758
0.022
0.974
0.004
Pullover
0.945
0.012
0.976
0.001
0.980
0.001
0,983
0.002
0,972
0.001
0.617
0.046
0.902
0.005
Dress
0.973
0.006
0.986
0.001
0.992
0.000
0.991
0.001
0.986
0.000
0.525
0.038
0.843
0.014
Cout
0.958
0.006
0.978
0.001
0.983
0.000
0
0.002
0,974
0.000
0.627
0.029
0.885
0.003
Sandal
0.968
0.011
0.997
0.001
0.999
0.000
0.999
0.000
0.999
0.000
0.681
0.023
0.949
0.005
Shirt
0.919
0.005
0.952
0.001
0.958
0.001
0.944
0.005
0.932
0.001
0.618
0.015
0.842
0.004
Sneaker
0.991
0.001
0.994
0.002
0.998
0.000
0.998
0.000
0.998
0.000
0.802
0.054
0.954
0.006
Bag
0.980
0.005
0.994
0.001
0,999
0.000
0.998
0.000
0.999
0.000
0,447
0.034
0.973
0.006
Ankle boot
0.992
0.001
0.985
0.015
0.999
0.000
0.997
0.000
0.996
0.000
0.583
0.023
0.996
0.000
G.3 EXPERIMENTS OF COVARIATE SHIFT ADAPTATION
In Table 5, we show the detailed results of experiments of covariate shift adaptation. Even when the training data and the test data follow the same distribution, the covariate shift adaptation based on D3RE improves the mean PD. We consider that this is because the importance weighting emphasizes the loss in the empirical higher-density regions of the test examples.
H OTHER APPLICATIONS
In this section, we explain other potential applications of the proposed method,
H.1 COVARIATE SHIFT ADAPTATION BY IMPORTANCE WEIGHTING
We consider training model using input distribution different from the test input distribution, which is called covariate shift, (Bickel et al., 2009). To solve this problem, the density ratio has been used via importance weighting (IW) (Shimodaira, 2000; Yamada et al., 2010; Reddi et al., 2015).
23

---

Under review as a conference paper at ICLR 2021
Table 5: Average PD (Mean) with standard deviation (SD) over 10 trials with different seeds per
method. The best performing method in terms of the mean PD is specified by bold face.
Domains (Train - Test)
books - books
dvd - books
dvd - dvd
elec - books
elec - dvd
DRE method
Mcan
SD
Mean
SD
Mcan
5D
Mean
SD
Mcan
SD
w/o IW
0.093
0.003
0.128
0.008
0.100
0.005
0.212
0.012
0.187
0.008
Kernel SIF
0.089
0.002
0.114
0.006
0.094
0.004
0.200
0.009
0.179
0.006
Kernel KLIEP
0.089
0.002
0.116
0.006
0.094
0.004
0.205
0.011
0.184
0.008
uLSIF-NN
0.093
0,005
0.128
0,008
0.100
0.005
0.212
0.012
0.187
0.008
PU-NN
0.093
0.003
0.128
0.008
0.100
0.005
0.212
0.012
0.187
0.008
mBBR. LSIF
0.086
0.002
0.113
0.005
0.091
0.004
0.199
0.009
0.176
0.005
mnBR-PU
0.090
0.003
0.113
0.006
0.096
0.004
0.199
0.009
0.176
0.006
Domains (Train - Test)
cloc
clcc
kitchen
books
kitchen
dvd
kitchen
cloc
kitchen
kitchen
DRE method
Mean
5D
Mean
SD
Mean
SD>
Mean
SD
Mean
SD
w/o IW
0.079
0.013
0.185
0.006
0.002
Kernel uf SIF
0.072
0.003
0.192
0.007
0.178
0.008
0.071
0.003
0.060
0.003
Kernel KLIEP
0.072
0.003
0.195
0.005
0.182
0.007
0.072
0.004
0.060
0.002
ULSIF-NN
0,079
0,005
0.202
0.013
0.185
0.006
0.073
0,004
0.062
0.002
PU-NN RnBR-LSIF
0.079
0.005
0.202
0.013
0.185
0.006
0.073
0.004
0.062
0.002
0.071
0,003
0.189
0.008
0.174
0.008
0.068
0,003
0.058
0.003
mnBR-PU
0.074
0.004
0.190
0.008
0.174
0.008
0.068
0.003
0.062
0.005
Table 6: Average PD (Mean) with standard deviation (SD) over 10 trials with different seeds per method. The best performing method in terms of the mean PD is specified by bold face.
Domains (Train + Test)
book -> dvd
book - elec
book -+ kitchen
dvd -+ clec
dyd -+ kitchen
elec - kitchen
method
Mean
Mean
Mean
Mean
Mean
SD>
wio IW
0,126
0.008
0.174
0.010
0.166
0.009
0.162
0.006
0.145
0.010
0.074
0.005
Kernel uLSIF
0.122
0.009
0.162
0.159
0.007
0.153
0.006
0.142
0.007
0.005
Kernel KLIEP
0.130
0.010
0.164
0.009
0.161
0.007
0.154
0.006
0.143
0,006
0.070
0.005
uLSIF-NN
0.126
0.008
0.174
0,010
0.166
0.009
0.162
0.006
0.146
0.010
0.074
0.005
PU-NN nnRR-LSTP
0.126
0.008
0.174
0.010
0.166
0.009
0.162
0.006
0.146
0.010
0.074
0.005
0.120
0.008
0.160
0.008
0.7
0.008
0.148
0.006
0,138
0.007
0.066
0.005
naBR-PU
0.119
0.008
0.160
0.156
0.007
0.148
0.138
0.007
0.005
We use a document dataset of Amazon (Blitzer et al., 2007) for multi-domaii sentiment analy- sis (Blitzer et al., 2007). This data consists of text reviews from four different product domains: book, electronics (elec), dvd, and kitchen. Following Chen et al. (2012) and Menon & Ong (2016), we transform the text data using TF-IDF to map them into the instance space X = 1000000 (Salton & McGill, 1986). Each review is endowed with four labels indicating the positivity of the review, and our goal is to conduct regression for these labels. To achieve this goal, we perform kernel ridge regression with the polynomial kernel. We compare regression without IW (w/o IW) with regression using the density ratio estimated by PU-NN, uLSIF-NN, nnBR-LSIF, nnBR-PU, uLSIF with Gaussian kernels (Kernel uLSIF), and KLIEP with Gaussian kemels (Kernel KLIEP). We conduct experiments on 2, 000 samples from one domain, and test 2, 000 samples. Following Menon & Ong (2016), we reduce the dimension into 100 dimensions by principal component anal- ysis when using Kernel uLSIF. Kernel KLEIP, and regressions. Following Menon & Ong (2016) and Cortes & Mohri (2011), the mean and standard deviation of the pairwise disagreement (PD), 1 - AUROC, is reported. A part of results is in Table 6. The full results are in Appendix G.3. The methods with D3RE show preferable performance, but the improvement is not significant compared with the image data. We consider this is owing to the difficulty of the covariate shift problem in this dataset.
f --divergence Estimation: f f-divergences (Ali & Silvey, 1966; Csiszár, 1967) are the discrepancy measures of probability densities based on the density ratio, hence the proposed method can be used for their estimation. They include the KL divergence (Kullback & Leibler, 1951), the Hellinger distance (Hellinger, 1909), and the Pearson divergence (Pearson, 1900), as examples.
The purpose of a homogeneity test to determine if two or more datasets come from the same distribution (Loevinger, 1948). For two-sample testing, using a semiparametric f-divergence estimator with nonparametric density ratio models has been studied
Two-sample Homogeneity Test:
hhtp:://jchn b6l mizer.cco. s0 fofftwaree.. 1
24

---

Under review as a conference paper at ICLR 2021
(Keziou., 2003; Keziou & Leoni-Aubin, 2005). Kanamori et al. (2010) and Sugiyama et al. (2011a) employed direct DRE for the nonparametric DRE.
Generative Adversarial Networks: Generative adversarial networks (GANs) are successful deep generative models, which learns to generate new data with the same distribution as the train- ing data Goodfellow et al. (2014). Various GAN methods have been proposed, amongst which Nowozin et al. (2016) proposed f-GAN, which minimizes the variational estimate of f-divergence. Uehara et al. (2016) extended the idea of Nowozin et al. (2016) to use BR divergence minimiza- tion for DRE, The estimator proposed in this paper also has a potential to improve the method of Uehara et al. (2016).
Average Treatment Effect Estimation and Off-poolicy Evaluation: One of the goals in causal inference is to estimate the expected treatment effect, which is counterfactual value. There- fore, following the causality formulated by Rubin (1974), we consider estimating the average treatment effect (ATE). Recently, from machine learning community, off-policy evaluation (OPE) is also proposed, which is a generalization of ATE (Dudík et al., 2011; Imai & Ratkovic. 2014; Wang et al., 2017: Narita et al., 2019; Bibaut et al., 2019; Kallus & Uehara, 2019; Oberst & Sontag, 2019). OPE has garnered attention in applications such as advertisement design selection, per- sonalized medicine, search engines, and recommendation systems (Beygelzimer Langford, 2009; Li ct al., 2010; Athey & Wager, 2017).
The problem in ATE estimation and OPE is sample selection bias. For removing the bias, the density ratio has a critical role. An idea of using the density ratio dates back to (Rosenbaum, 1987), which proposed an inverse probability weighting (IPW) method (Horvitz & Thompson, 1952) for ATE esti- mation. In the IPW method, we approximate the parameter of interest with the sample average with inverse assignment probability of treatment (action), which is also called propensity score. Here, it is known that using the true assignment probability yields higher variance than the case where we use an estimated assignment probability even if we know the true value (Hirano et al., 2003; Henmi & Eguchi, 2004; Henmi et al., 2007). This property can be explained from the viewpoint of semiparametric efficiency (Bickel et al., 1998). While the asymptotic variance of the IPW estimator with an estimated propensity score can achieve the efficiency bound, that of the IPW estimator with the true propensity score does not.
By extending the IPW estimator, more robust ATE estimators are proposed by Rosenbaum (1983), which is known as doubly robust (DR) estimator. The doubly robust estimator is not only robust to model misspecification but also useful in showing asymptotic normality. In particular, when using the density ratio and the other nuisance parameters estimated from the machine learning method, the conventional IPW and DR estimators do not have asymptotic normality (Chernozhukov et al., 2018). This is because the nuisance estimators do not satisfy Donsker's condition, which is required for showing the asymptotic normality of semiparametric models. However, by using the sample split- ting method proposed by Klaassen (1987), Zheng& & van der Laan (2011), and Chernozhukov et al. (2018), we can show the asymptotic normality when using the DR estimator. Note that for the IPW estimator, we cannot show the asymptotic normality even if using sample-splitting
When using the IPW and DR estimator, we often consider a two-stage approach: in the first stage, we estimate the nuisance parameters, including the density ratio; in the second stage, we construct a semiparametric ATE estimator including the first-stage nuisance estimators. This is also called two-step generalized method of moments (GMM). On the other hand, from the causal inference community, there are also weighting- based covariate balancing methods (Qin & Zhang, 2007; Tan, 2010: Hainmueller, 2012: Imai& & Ratkovic, 2014). In particular, Imai & Ratkovic (2014) proposed a covariate balancing propensity score (CBPS), which simultaneously estimates the density ratio and ATE. The idea of CBPS is to construct moment conditions, including the density ratios, and estimate the ATE and density ratio via GMM simultancously. Although the asymptotic property of the CBPS is the same as other conventional estimators, existing empirical studies report that the CBPS outperforms them (Wyss et al., 2014).
Readers may feel that the CBPS has a close relationship with the direct DRE. However, Imai & Ratkovic (2014) is less relevant to the context of the direct DRE. From the DRE perspective, the method of Imai& & Ratkovic (2014) boils down to the method of Gretton et al. (2009), which pro- posed direct DRE through moment matching. The research motivation of Imai & Ratkovic (2014)
25

---

Under review as a conference paper at ICLR 2021
to estimate the ATE with estimating a nuisance density ratio estimator simultaneously. Therefore, the density ratio itself is nuisance parameter, that is, they are not interested the estimation perfor- mance of the density ratio. Under their motivation, they are interested in density ratio estimator satisfying the moment condition for estimating the ATE, not in a density ratio estimator predicting the true density ratio well. In addition, while the direct DRE method adopts models and neural networks (our work), it is not appropriate to use those methods with the CBPS (Chernozhukov al., 2018). This because the density ratio estimator does not satisfy Donsker's condition. Even naive Ridge and Lasso regression estimators do not satisfy the Donsker's 's condition. Therefore, when using machine learning methods for estimating the density ratio, we cannot show asymptotic normality of an ATE estimator obtained by the CBPS; therefore, we need to use the sample-spliting method by (Chernozhukov et al., 2018). This means that when using the CBPS, we can only use a naive parametric linear model without regularization or classic nonparametric kernel regression. Recently, for GMM with such non- non-Donsker nuisance estimators, Chernozhukov et al. (2016) also proposed reasons, the CBPS is less relevant to the direct DRE context.
GMM method based on the conventional two-step approach. For these
Off-policy Evaluation with External Validity: By the problem setting of combining causal in- ference and domain adaptation, Kato et al. (2020) recently proposed using covariate shift adaptation to solve the external validity problem in OPE, i.e., the case that the distribution of covariates is the same between the historical and evaluation data (Cole & Stuart, 2010; Pearl & Barcinboim, 2014).
Change Point Detection: The methods for change-point detection try to detect abrupt changes in time-series data (Basseville Nikiforov, 1993; Brodsky Darkhovsky, 1993; Gustafsson, 2000; Nguyen et al., 2011). There are two types of problem settings in change-poin detection, namely the real-time detection (Adams, 2007; Garnett al., 2009; Paquet, 2007) and the retrospective detection (Basseville & Nikiforov, 1993; Yamanishi & Takeuchi, 2002). In retrospective detection, which re- quires longer reaction periods, Liu et al. (2012) proposed using techniques of direct DRE, Whereas the existing methods rely on linear-in satut-i--auuu in-parameter models, our proposed method enables to employ more complex models for change point detection.
Similarity- Sentiment Analysis: Kato (2019) used the density ratio estimated from PU learning for sentiment analysis of text data based on similarity.
I GENERALIZATION ERROR BOUND
The generalization error bound can be proved by building upon the proof techniques in Kiryo et al. (2017); Lu al. (2020).
Notations for the Theoretical Analysis: We denote the set of real values by R and that of positive integers by N. Let X' C Rdd Let Pmu (2) and pao (x:) be probability density functions
X, and
assume that the density ratio (xx) = P=n(#) is existent and bounded: I = || < co. Assume C F Since R (because
Pac
pac(x)r" (x)dr S lo)r, we have E (0, and
hence Pmood = Pde Cpau >
Problem Setup: Let the hypothesis class of density ratio be H C (r (R:RD. - (br, B:) T,).
where 0 < b, < R < B,. Let f I, + R be a twice aantinooullydiiffreetti where Of is the derivative
convex function
with a bounded derivative. Define f by ( = f(t) of f continuously extended 0 and B, Recall the definitions (1()) == af(()) f(t)) + A, (2(1)= ==
26

---

Under review as a conference paper at ICLR 2021
ft(,,, and
== Ede ((A))) Eau [f(((()))
EEmod (1())(X)))xxx)((((()) -
+ +AI - Enu [(x(
Ei + (xx))((XX)))
(= (Ede ClE + (m)22((()))),,
nnBR, = (Emodli(r(x))) + Enul2(r(X))
(= pl (Ede CTE 34 (((()))((()))))))) Bm)l)(((X))
where we denoted Byoo Bete- ClEn and p is a consistent correction function with Lipschitz constant hp (Definition 1).
Remark 4. The true density ratio r* minimizes BRy.
Definition 1 (Consistent correction function Lu et al. (2020)). A function f RR R is called consistent correction function if it is Lipschitz continuous, non-negative and f(x) = for all x 2 0.
Definition 2 (Rademacher complexity). Given N and distribution p. define the Rademacher complexity (Z)) of function class H as
1 Σ o
(HL) = E, B
sup rEH
where } are Rademacher variables (i.e., independent variables following the uniform distri- iid
bution over (-1,-1) and {X ~ p.
The theorem in the paper is a special case of Theorem 3 with p(-) = max (0,)) (in which case T, 1) and Theorem 4.
Theorem 3 (Generalization error bound). Assume that Br == supter (+) ((2(t))))
Assume & is Le, -Lipschitz and Eg is Ltg- Lipschitz. Assume that there exists an empirical risk minimizer f E argmin,ee nnBR, (r) and population risk minimizer argmin,es, (R) Also assume infreH 1 (r) > and that (p (p-1e Id) is (Lp-ra)-Lipschinn Then for any 8 E (0, 1), with probability at least 1 8, have
(f) (F) I 8L, Te, Rp4 (H) + 8(I,, + Tee RRRa (H)
L2
(1 L,)2
+ 24 (. naa) + +Be
++++
log g
7hd
where Te (C nao)) is defined in Lemma 2.
Proof. Since i minimizes nnBR,, we have
(F) (F) (R) - nnBR, BR (F)
(f) , nnBR, BF)
< 2 sup rEH
InBRR (r) - (r)
< 2 sup (inBR, Bl + 2 sup reW
[EnBBRy - (R)
rewl
Maximal deviation
Blas
We apply McDiarmid's ss inequality McDiarmid (1989); Mohri et (2018) to the maximal deviation term. The absolute value of the difference caused by altering one data point in the maximal deviation term is bounded from above by 2B, Le if the altered point is sample from Pae and 2 2 1+ if
nás
Pam
27

---

Under review as a conference paper at ICLR 2021
it is from Pau- Therefore, McDiarmid's inequality implies, with probability at least 5, that have
sup rEH
nnBR, (r) EnnBRR (r)
L2 nn nnBRy (nnnn)r))nnnnnnlll +Be/2
(1 (1+ 1,2 log 8"
E
sup LEH
+
Ade
1mm
Expected maximal deviation
Applying Lemma the expected maximal deviation term and Lemma the bias term, we obtain the assertion.
The following lemma generalizes the symmetrization lemmas proved in Kiryo al. (2017) and Lu et al. (2020).
Lemma (Symmetrization under Lipschitz-comtinuous modification). Let 0 < b, J E N, and (Kj}f=1 C N. Given i..dd samples ((, == {X,),=1
k.. each from distribution P(j.) over X,
consider a stochastic process S indexed by F c (a, b)*
of the form
K2 Σ (asleess(( A=1
S()) Σ Pj
where each Pj is a L functionn on R. ((j,k) is -Lipschitzz function on (a, b), and B(aa) denotes the expectation with respect to the empirical measure of Dij,y- Denote S(f)
ES(() where E is the expectation with respect to the product measure of (D(.,)) Here, the index j denotes the grouping of terms due Py, and denotes each sample average term. Then we have
K2
E Sup 1$(1) S(N) <
Σ
Lap Leg Ruggayaaee (F).
fe3
Proof. First, we consider a continuous extension of ((,,) defined on (a, [0, Since the functions in F take values only in (a, this extension be performed without affecting the values of S(f) S(f). We extend the function by defining the values for E [0, a] as (.,)(z)
lim ((j,)) (x'), where the right-hand side is guaranteed to exist since {.R; is Lipschitz continuous hence uniformly continuous. Then, l(j,)) remains Lp, -Lipschitz continuous function
[0.
Now we perform symmetrization (Vapnik, 1998), deal with p5 ss and then bound the symmetrized process Rademacher complexity. Denoting independent copies of (X by (X (gh)
(.. and
28

---

Under review as a conference paper at ICLR 2021
the corresponding expectations well the sample averages with (gh)
sup SEF
($( - -())
J
K
E sup fEF
lp,
& - -EEsh))
Blah) (i.k) (EA) (f(x(ee)))))
==1
1=1
1=1
K2
K;
(xb)
sup FEF
lpj
(is - Ps
b(at)
(i. Cin ((
1=11
EE gh)
((s) - E(gh)
(AA) & (1.)) (f
sup FEF
Lips
EE(R))
sup SEF
I8 ( - (o)) - Elsh)
- (AAN - (G.,) (0))
k=1
Lp
(2R (2 (((G)))) -G(,A)(0:
k=1
K2
L ps
2. 2. Rog
1=11
where we applied Talagrand's contraction lemma for two-sided Rademacher complexity (Ledoux & Talagrand, 1991; Bartlett & Mendelson, 2001) with respect to (t + (t,))()) (), (0)
the last inequality.
Lemma (Bias due to risk correction). Assume infrew Elomo (r(())) 0 and that (p Id) is (Lp- Liipschitz on I.. There exists a >> 0 such that
2a²
sup EnnBRR,r) BRy S (1 C)B exp (TB,²² (BB2/nde)) + (C2 B r
(c (Naus nde).
Remark 5. Note that already have Pmod 2 0 and & > 0 and hence infren EEmod (r(()) 0. Therefore, the assumption of Lemma 2 is essentially referring to the strict positivity the in- fimum. Here, EEmod and P (.) denote the expectation and the probability with respect to the joint distribution of the samples included in B
Proof. Fix arbitrary H. We have
EnnBR, - (r) = E(nnBR (r) - BR, (r)]
(r(X))) Emod & (r(X))] < E [ (1 (r(X))) Emod (r(
E I [p(Bmood E1 (r(X)) + Emodé (r(X))) [p( (r(()))) - -Emod ei (r(X))
S E I
# Bmoah e (r(x)))
lp(s) -s1
sup
*1
where 1 denotes the indicator function, and we used [mmod & (r(X)) < (1+ By Further, we have sup *))5((++))
(p(s) - $/$ sup
(d)ss) - (p- (0) + (p - ld)(
sup -p + * (
(1+
29

---

Under review as a conference paper at ICLR 2021
where Id denotes the identity function. On the other hand, since inf EEmod (r(())) > is assumed, there exists a such that for any r E H. ElEmodd (r(()) > a. Therefore, denoting the support of a function by supp(-),
Le & (r(())) * Emaa Em = ( E supp(e Id)
$ IP ((moal((((X) < 0) s P (Emoali(((X)) < ElEmod (r(()) aa)
holds. Now we apply McDiarmid's inequality to the right-most quantity. The absolute difference caused by altering one data point Emoali (r(X)) is bounded by B. if the change in a sample from Pdee and CB2 otherwise. Therefore, McDiarmid's inequality implies
Vhan
PP (B (r(()) < E (r(()) - a) s exp (- ((Bi²) (nd) (C² (
20
Theorem (Generalization error bound). Under Assumption 3, for any E (0. 1), with probability at least 5, we have BRy(F) - BR2(F) I Le, RRan (H) + 8(CLe, +
Ren Rm (H) + 2 (n (dee + Bey/s (((L) + (4002) ) log }. where & (T mae) (1 +
nide
Aun
By exp in Appendix I.
2a² /mm)) and a O a constant determined in the proof of Lemma
(ne"/maa)+(Ca ((am//)mm))
Remark 6 (Explicit form of the bound in Theorem 1). Here, we show the explicit form of the bound in Theorem I as follows:
(f) - (F)
K1
R2
+ 200 (Nmu: ndde) + Beg
(1 1
(1
C)2 log
1 8
+
Vdde
Vnnu
Idde
Auu
(V2log(2)L +1) 11 Bw,
Bpan
Vdde
Byn
(V2log(2)L + 1) 1 Bw,
+ 8CCL,, + Lig))
Vnnu
(-18, (Bee/Tnde + (C2 //mu))
2a²
+ (1 C))Beep
1
(1+ C)²
+ B
8
+
log 8"
Rdde
Dmu
J RADEMACHER COMPLEXITY BOUND
The following lemma provides an upper-bound on the Rademacher complexity for multi-layer per- ceptron models in terms of the Frobenius norms of the parameter matrices. Alternatively, other approaches to bound the Rademacher complexity can be employed. The assertion of the lemma fol- lows immediately from the proof of Theorem of Golowich et al. (2019) after slight modification to incorporate the absolute value function in the definition of Rademacher complexity.
Lemma (Rademacher complexity bound (Golowich et al., 2019, Theorem 1)). Assume the distri- bution p has a bounded support: Bp := sup suPresupp(p) || < co. Let H be the class of real-valued networks of depth L over the domain X, where each parameter matrix W, has Frobenius norm at most Bw, 2 0, and with 1-Lipschitz activation functions vj which are positive-homogeneous (i.e.,
PP is applied element-wic and (att) = aip, (t) for all a 2 0). Then
Bp 22log ( +
11; Bw,
(?) <
Vn
30

---

Under review as a conference paper at ICLR 2021
Proof. The assertion immediately follows once modify the beginning of the proof of Theorem by introducing the absolute value function inside the supremum the Rademacher complexity as
sup rER
Σ
a.r().)
S x
log E. sup exp reH
> Σ
for À > 0. The rest of the proof is identical to that of Theorem of Golowich et al. (2019).
K PROOF OF THEOREM
We consider relating the I error bound to the BR divergence generalization error bound in the following lemma.
Lemma 4 (L2 distance bound). Let H. == fr X (b,, L |x oo} and assume r" E H. Ifinfre,, (t) > 0, then there exists μ > 0 such that for all E H.
2 ||r r" (122((p))) I (BR,(r) (r)(r"))
"
holds.
Proof. Since μ == infres, (1)) > 0, the function p-strongly convex. By the definition of strong convexity,
BRG(r) (R)(r") = (rR,(r) - (r=ff((((())) - (BRy(r") + Edef (X)))
Edd [X(r((X) ((x(X) -0(((())) rxx))
2 Edte
(((()))-(xx)) -(()))(] --
- r
Lemma 5 (&2 distance bound). Fix E H. Given n samples {z beili=1 from Pac- with probability at
least 1 8, we have
log
n Σ (r(aa))
[rr (x)] +(2R)²
2n
Proof. The assertion follows from McDiarmid's inequality after noting that altering one sample results in an absolute change bounded by (2R))
Thus, generalization error bound in terms of BR, can be converted to that of an I distance when the true density ratio and the density ratio model are square-integrable and f strongly convex. However, when using the result of Theorem I, the convergence rate shown here is On the other hand, Kanamori et al. (2012) derived Op ((min fnae: Nuu -)11((++)) convergence rate. To derive this bound when using neural network, we need to restrict the neural network models. In the following part, we prove Theorem 2 for the following hypothesis class H.
slower than Op ((min (Raes (nn3)-1/(4))
(po....,PI+)) E Definition (ReLU neural networks; Schmidt-Hieber 2020). For E N and p (po..... PL+1)
N4-2
F(L,)) = + WLO W Wio. Wox
W, RP--IKP Us E R O....., L)).
where o. (v) oly v). and a(.) max 0} is applied in an element-wise manner. Then, for s E F O, N, andpp NL+2 define
= (f F p)
W flo + 1lylloo & &, F).
31

---

Under review as a conference paper at ICLR 2021
where || llo denotes the number of non-zero entries of the matrix the vector, and oo denotes
the supremum norm. Now, fixing L, & E N as well as F > O, we define
Ind = {[L. p) L LEN,L L S L. p
and we consider the hypothesis class
H = U
M,L,
(L.d)
H = fre H: Im(r) C (br, B,)}.
Moreover, we define /1 : Indi.p + IR and 1: H + o0) by
[1,,,) = 2|Ind x (L+ 1)V?
I(r) == max ||rloos
min
I(L,))
(L.d) rEH(L....))
where V ;= 11 (pr + 1), and we define
HM = fr :: I(r) S M).
Note that the requirement for the hypothesis class of Theorem is not as tight as that of Theorem 2. Then, we prove Theorem follows:
Proof. Thanks to the strong convexity, by Lemma 4, we have
11 || r" (p::)) S (F) (BR((r))
2
(F) - BR, (r*)
(F) (f) -nnBR) + nnBRR((F) (Ry(r") (r)
=0
=0
< (f) BR, (f) + (BR - (F)) (nnBR, (r)
< (F) - BR, (r') BRy - (R) 2 sup (r) nnBR, (r)).
rEwl
where we used nnBR, S nnBRRyrr)). To bound A, for ease of notation, let Eq e, (r(X)) and fs (x(r( Then, since
(r) (r(e)(((X)) C + (r())
(r) = Bde(((((X)) ei + (r())),
we have
A = BR, - BR2(r") + Bry (F)
(Ede Eed)) 0 E7') C(Emu B (e9 E" + (E (nn) 23) -
< [Bao - Edo) - l )1 + C1(EEm - Emd (eh f7') 3 + [(E, Ens - Eg
By applying Lemma 10, for any 0 < < 2, we have
||
1-7/2 (Ps.) min (Neess Run)
(min {nde nuu J 1221(2+ 1)
A < Op max
32

---

Under review as a conference paper at ICLR 2021
On the other hand, by Lemma 12 and Lemma 7, and the assumption inf EEmod ( 0,
there exists a > O such that we have B I Oş exp (B=//an)+(CCBpp //omm)))
2a
Combining the
above bounds on A and B, for any < y < 2, we get
7/2 |
|| r'(1(2(ppa))) S 50p max
1.2 (pa())))
min ( nnul
(min (ndee Amu 1)2/(2+7)
2a²
+ O3
exp
(Be² (Bee/ + (C /nmm))
|| r"
1-7/2 (.(Ppc)
S OOp max
min (ndes Amuj
(min (Ades Amu }) (2/(24)))
As result, we have
|| r" (1pp(pp))) S Op (Imin {Tder mma)) z
Each lemma used in the proof is provided follows.
K.1
COMPLEXITY OF THE HYPOTHESIS CLASS
For the function classes in Definition 3, we have the following evaluations of their complexities.
Lemma (Lemma 5 in Schmidt-Hieber (2020)). For E and E NL-2 2, let = I (p: (1). Then, for any 5 > 0.
log (8, H(.. oc), (l - (s + 1) 12g 2 1)1?).
Lemma' 7. There exists > 0 such that
RPen (H) S cD 1/2
R.de (H) < CT
-1/2
By Dudley's entropy integral bound (Wainwright, 2019, Theorem 5.22) and Lemma 6, we have
Proof.
2F
log.N(8, H(L, p, 1l00) d8
RPmm (H(L,p, < 32
7m
2F
32
((s+ 1) (6 (1+12001(+)111) 1/2 d8
n 112
Ja
Therefore, there exists c such that
R Run (H) I
Σ
REem (H(,,,ps, S en 1/2
(L.p)EIndL.
The same argument applies to R (H), and we obtain the assertion.
Lemma 8. There exists co > such that for any 7 > 0, any > 0, and any M 1, we have
log.N (8, HM, |1,0) 5 $ s
and
sup ||r -r-ri Ir-rolllo S co rEHM
33

---

Under review as a conference paper at ICLR 2021
Proof. The first assertion is result of the following calculation:
log.V (6, Har.
|| (leo) S log
Σ (6, &, llee)
Uorletdd h(T.)))M
(
6+1
I log
Σ
Logietod 4(LP)SM
s+1
I log pldd,pl
8 M
+t1
M
(s + 1)
(s+ 11
(L.P)s where the first inequality follows from HM C (ld,) (L.()))) H(L, p, 8, F), and the last inequality from y log x² log x that holds for all 2, 7 > 0.
The second assertion can be confirmed by noting that for any E HMs with M 2 1,
||r 10 S |||||xx + 1ox S M ||o0
||r 10x0
M (1 || |
M
holds.
Definition 4 (Derived function class and bracketing entropy). Given a real-valued function class F, define lo F = {Eo f E FJ. By extension, we define 1 E H + [1, by I(l and & a Har = El ffor:r E HM Note that, as a result, & o Har coincides with {e ffor r E lo H r) S M}.
1(r)
Lemma 9. Let : (br, - IR be a v-Lipschitz continuous function. Let HB (5, F, l(((()) denote the bracketing entropy of F with respect to a distribution P. Then, for any distribution P. any 7 > 0, any M 1, and any ō > O, we have
HB (5, l a HM, (1)2()) 1 (s (s+
(M)
(
8
Moreover, there exists co 0 such that for any M 2 I and any distribution P.
sup toretoHar
|tor E (>1(( S couM,
sup Nor
-
S CoMM, for all 8 >
[Bor- $8
Proof. By combining Lemma 2.1 in van de Geer (2000) with Lemma 6, we have
6
o HM. || 11xz) lba))
HB (ō. f HM, (I((())) I log.
2
8
1
(2vM
< log
Hm, 11l (l1.111120) < 7
2v
8
For M 2 1, we have
sup torefoHar
lleor- ( [((P))
sup torêtoHN
- lo 1100
sup EorgtoHa |ioor-orr 1ZA
1loor Wor-loorlles S sup toretoHss
llor-los
and Lemma 6 implies
sup tor
| - for 1000 < sup u||r - r 1011 S V.g reH
34

---

Under review as a conference paper at ICLR 2021
K.2 BOUNDING THE EMPIRICAL DEVIATIONS
Lemma 10. Under the conditions of Theorem for any 0 < < < 2, we have
f r" 1/7/22
i(Bde [ete - e =0p
max
v Mite
2/+2))
de
|| r
1-y/22
(Enu - [n - O2
La (pac)
max
2/(2
Buu
Ahri
2-7/2 | r
(mmn - (22 -
Oz
max
1.2 (pac)
2/(2+7)
Yua
as Tmuy Thde - DO.
Proof. Since <>< < 2, we can apply Lemma 11 in combination with Lemma 9 obtain
Eec) eT" Or),,
sup rEM
D1(r)
(E Bnn)(ef eT")l or.
(1),
sup rEW
D2(r)
EE
Ens - 155) -z)
sup rEW
Dz(r)
where
119 e7 1-x/2 T(E))2/2
(3(P)))
((f)
(r(r) = max
Vide
2/(2+))
|1e ET (.
1-2/2 I(e9)1/2
[(T)
D2(r) = max
Vina
Thu
2/(2+n)
1/2 11 - Eg (2(m))) 1(eg//2
I ((())
Da(r) = max
2/(247)
Vlau
Noting that sup,ew I(r) < oc, that l2, & are Lipschitz continuous, and that ||A r (1)(())))) S (2)(
suPaex
||A (1. holds, we have the assertion.
Pac(x)
Following is a proposition originally presented in van de Geer (2000), which was rephrased in Kanamori al. (2012) in form that is convenient for our purpose.
Lemma 11 (Lemma 5.14 in van de Geer (2000), Proposition I in Kanamori et al. (2012)). Let F c LPPP) be function class and the map I(ʃ') be complexity measure of F, where is non- negative function on F and I(fo) < oc for a a.fixed fo E F. We now define FM = {f E F I(f) M) satisfying F UM21 FM. Suppose that there exist co > 0 and 0 < 7 < 2 such that
|f foll c.M, feFF
sup
sup IEFM |lf folll 56
Ilf foll S SoM, for all 8 > 0,
and that H8(6, FM O (M/66)" Then, we have
[f -fodd(P Pw)l
sup FEF
Op (1), (n + oo),
D(f)
35

---

Under review as a conference paper at ICLR 2021
where Dff) is defined by
Ilf - foll 1-2/2 foll 1(5)112
I() (2/(24))
D(J = max
vn
K.3 BOUNDING THE DIFFERENCE OF THE BR DIVERGENCE ESTIMATORS
Lemma 12. Assume R (H) (() + 00) and Rug (H) (m) + 00). Also assume
the same conditions as Theorem 3. Then,
202
sup nnBRy(r) BR, (3R((1) Op
(exp exp (Be² /nee) + BC*
Be /Tmua)
as Tauus Tide - OC.
Proof. First, by combining Lemma 13, the assumption the Rademacher complexities, and Markov's ' inequality, there exist a > and v n E N such that for any Ride 2 y and any å E (0, 1), have with probability least 1 5,
de and Timn 2 n
(nBR, - (R)(r)) (1 C) exp (T(B? 2 /nae) + CC² /nuu)
2xx
sup NEW
6
Therefore, we have the assertion.
Lemma 13. Assume R (H) = ( + oo) and Renn (H) = o(1) + o0). Also assume
the same conditions as Theorem 3. Then, there exist a O and U n E N such that for any nde 2 de and Anu n
2a²
E sup mnBR, BRy(r)) (1 (1+ (-1B,² (/d2//ne)=>> + (C²BB²/nnmn)
reH
nnm))
holds.
Proof. First, we have
(nBR, BR)(())
sup LEW
E
sup Lre
( Emod&
E
sup ( ( ( ( Emod & (r(x))) Lre
( sup (1))|5(1-C)
< E
sup 1 rew
# Bmod E
(p(s) s1
where 11-) denotes the indicator function, and we used Emnod (r(x)))) S (1 C) Further, have
sup *(1
Ip(s) 1p(s) - s| S sup =|
- (p- (d)ss) (p - Id)(o))
< sup Lp-tals (L+CC)
+ 0 C)
where Id denotes the identity function. On the other hand, since inf EBmoaa (r(X)) > is assumed, there exists B > such that for any
H. RB (r(X)) > B. Therefore, denoting
36

---

Under review as a conference paper at ICLR 2021
the support of function by supp(-),
E
sup I (i Emod (r(X)))
Lre
E
sup (1 supp(p rew
sup (( < 00] Ireh
[3r H E (r(()) < <0]]
Br E H Emod (r(X)) <0)
$ Ar E H Emod E (r(X)) < En & (r(X)) (3)
- P B < sup & (r(X)) Rmod li (r( (r())))
rEH
Take an arbitrary a E (0, 3). Since Rea (H) - O(Ndo + 20) and R (H) - 0(Tem + 00), we
can apply Lemma 14 and obtain the assertion.
O
Lemma 14. Let B > >> O. Assume that there exist n n E N such that for any Thdo 2 nde and Thn 2 Tuu
4he, Rea (H) Le, Renn (H) 3 a.
Then, for any Nae 2 na and Pmm nnw we have
B sup sup(E (r(X)) Emoddl ((nnnl((r(())) (r(x)))
rEA
2a²
I exp
(BB² (B/2/nae> (C² Br /
Proof. First, we will apply McDiammid's inequality. The absolute difference caused by altering one data point in SuprEæ (El - Emod (r(X))) is bounded by Br if the change is in
sample from Pae and CB otherwise. This can confirmed by letting By B'nod denote the sample Tha averaging operator obtained by altering one data point in Emod and observing
sup [E (r(()))))))))))))))))))))))())) - Emoah (r())) rEit
sup mo ( E' 41 (r(x))
rEH
I sup (E moo 6 (r(X)) Emadd e1 (1 (r(X)) (1 By & (r())))) rEW
< sup (i'mn & (r(X)) Emonth & (r(X)))- rEW
The right-most expression be bounded by Br. if the change is in sample from Pde and C.B Tum
vin Eim ( (r(X)) suprez (IE &1 (r(X)) otherwise. Likewise, suprew (ID2mod& (r(X))
Emoali (r()))) can be bounded by one of these quantities. Therefore, we have
sup sup ( reW
( sup & E' (r(X)))
rek
B; CB
Thde
and McDiarmid's inequality implics, for any > 0,
E sup e, (r(x)) Emod e (r(X))
sup (EE 1 (r(()) Emoo Emodd Lr
TER.
2c2
< exp <exp
(-(Be") /nde) BC2 /nma))
(10)
37

---

Under review as a conference paper at ICLR 2021
Now, applying Lemma 1, we have
E
sup LEH
EEÉ mod e (r(X)) Emodki (r(()))))
< E
sup Ed E1 (r(X)) (rce(((())) + CE
sup L
[B l (r(()) - Emu &i (
LEE
< 4L2, Rid (H) + LC, Rum (H) =: R.
By the assumption, if nae 2 de and Mmm 2 nuu we have R < a. Therefore,
sup Eoo (r(()) Emodl((((X))) < - a< rE
hence B - E suprew EEEEa (r(X)) ( 0. Therefore, we can take B
rHP (Elmmod E1 (r(X)) Emadd (r(()))) in Equation (10) to obtain
PP
3 < sup rEH
(Elmod & (r(X)) Emoa (r(()))
2(3 E sup (BlEmod (r(()) - Emod (I )²
< exp
(Be² /nde) + (C2 /nnu)
2(3 - RR)2
(-(B((/()/))
2a²
< exp
Sexp
(Be²/nao) ndoe + (C²B,² /nmu)
(Bee/nde) + (C² /nm))
where used 0 B R.
38


Reviews:
[{"review_id": "mYz0sYiGePz", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "SUMMARY:\nThis work introduces a new family of Bregman divergences for density ratio estimation with flexible models that aims at solving the train-loss hacking problem. The contribution is foremost theoretical, but includes an experimental validation on benchmark problems.\n\nSTRENGTHS:\n- This work introduces a new family of non-negative Bregman divergences.\n- The proposed estimator is theoretical justified.\n- Experiments show convincing results over the original Bregman divergences (at least for LSIF and PU).\n- The paper is well written, although quite difficult to follow without some theoretical background.\n\nWEAKNESSES:\n- In Section 3.1, it said the loss functions for other machine learning tasks such as classification are lower-bounded, hence (as far I understand) they do not suffer from the train-loss hacking problem. Shall I therefore understand that estimating the density ratio through classification, using the cross-entropy (BR_BKL), does not suffer from this the train-loss hacking issue? In this case, what is the advantage of using nnBR_BKL over BR_BKL?\n- The experiments do not include BR_BKL nor nnBR_BKL, which I would have found quite interesting for the reason mentioned above.\n- While appreciate the estimation error bound for D3RE, can you comment on the error bound for the original Bregman divergences? How much does nnBR improve over it? \n- How tight is the error bound for D3RE?\n- Some recent applications of density ratio estimation that could have been worth mentioning as well as likelihood-free inference approaches based on likelihood ratios.\n\nDISCLAIMER:\nDue to the critical conditions in my country due to the pandemic, I must admit that I did not verify the mathematical developments. I am sorry for the limited quality of my review. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "fTcvK-jL8Cx", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "The paper addresses an issue that arises in a particular formulation of the density ratio estimation problem. Namely, when one tries to directly fit a density estimation ratio, while minimizing Bergman divergence, it may be that overfitting causes the minimization problem to diverge to minus-infinity.\nThe paper suggests some form of regularization that uses a bound on the ell_infy norm of the ratio function. The paper justifies the change by proving a bound on Bergman divergence between minimizer computed and the best minimizer within the class.\nThe authors support their suggestion by experimenting: computing anomalies and learning from positive or unlabeled data.\n\nThe main drawback of the paper is that it is very hard to read, overloaded with cumbersome notation and lacks sensible discussion about the meaning of the results. Frankly, I couldn't decipher exactly why the over-fitting problem arises, what the 'theoretical justification' exactly says. While the experiments seems good, I didn't fully understand what was done, why are these the right experiments and what was learned from them.\nMore serious is that I can't understand how it compares to prior work. The paper claims it extends a work by Kiryo et al. which I'm not familiar with. There are other lines of research that attack the general problem of density estimation, some of them very related. \nIn particular, one can use arbitrarily strong learning models via the approach of the following paper:\n\"Estimating Divergence Functionals and the Likelihood Ratio by Convex Risk Minimization\" by Ngoyan, Wainright, Jordan.\nA comparison with this paper (and the rich literature that cites it) is lacking. \nAnother line of research for direct estimation comes from the econometric community. A starting point is\n\"Covariate balancing propensity score\" by Imai and Ratkovic. \nThe latter is less directly related but represents a huge body of work on direct density ratio estimation that should be cited and discussed.\n\nTo conclude, the paper's suggestion might be a good one, it is just too hard to asses. It seems to insist on a particular formulation of the problem and then find ways to make it work, but the writing is not clear and important related work is missing. \n\nSpecific comments, mostly related to style and presentation:\n1. In the introduction you have to discuss better what is the problem you solve exactly. How is direct density estimation different from calibrated classification? What is train-loss hacking and why is it unique to this formulation of the problem? etc.\n2. Don't assume that readers are familiar with Kiryo et al.\n3. Equation (3) needs to be discussed. That's the heart of the optimization to solve. I think it is somewhat similar to the one in NWJ I mention above, but I'm not sure. In any case, it is a bit 'weird' that r^* could be dropped from the formulation. What does that mean? \n4. Figure 1 suggests the issue is over fitting, I didn't understand the claim it is of a different flavor.\n5. I thing the assumption that the ratio is bounded is a reasonable one. One can try to justify it better.\n6. The last paragraph of Section 3 has to be explained better.\n7. I found Section 4 frustrating to read. The lack of numbered equations, the wording and the notation just confused me too much. At the end of the day I didn't fully understand what is the meaning of the theorem. For instance, Lemma 2 assumes the true ratio function is part of the class H. That's a very strong assumption no? How do these bounds compare to previous bounds?\n8. In the experiments, besides applications and such, don't you want simply to check the quality of the estimation of the ratio when the ground truth is known? I don't understand how the first experiment in Section 5 achieves that (I think I do, but I'm not sure).\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "atkzQAWwHRX", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "***\n\nSummary:\n\nThe paper addresses learning the ratio between two densities from their samples, with applications to outlier detection and covariate shift adaption. An existing approach is to minimize the Bregman (BR) divergence's empirical approximation while modeling the density ratio function $r^*$ by a flexible hypothesis family, such as neural networks (NNs). A particular issue of such an approach (that the present work aims to resolve) is \"train-loss hacking,\" meaning that the empirical loss can become arbitrarily large and negative. A new loss/objective based on BR divergence has been proposed, appearing on page 4, and is referred to as $\\widehat{\\text{nnBR}}_f(r)$. The major theoretical result, Theorem 1, states that minimizing the proposed objective effectively minimizes the BR divergence for sufficiently large sample sizes. Following this theorem and its corollary, the paper presents empirical evaluations, showing the new algorithm outperforms prior ones on standard datasets.\n\n***\n\nReasons for score:\n\nI think the paper is marginally below the acceptance threshold of ICLR. Learning the density ratio is a well-motivated problem with an objective different from density or functional estimation. But it is unclear to me how strong the theoretical claims are, and the writing needs significantly more work. I am also concerned about the reasoning behind several claims and the potential gap between the derived theory and experiments. Please refer to the \"Cons\" for details. \n\n***\n\nPros:\n\n \n1. The paper attempts to resolve a particular issue for employing flexible hypothesis families in density ratio estimation with BR-divergence loss. I think the problem is interesting and practically relevant. In particular, as the BR divergence encompasses several well-known loss functions, the proposed method naturally induces a class of new methods (page 4).\n\n2. The contribution is also meaningful as the algorithm incorporates the hypothesis class of neural networks, known to have strong expressive power, while some prior works don't. Under a sequence of Assumptions (1 to 4), Corollary 1 presents finite-sample guarantees for a specific NN class with bounded complexity. Experimental results further confirm the algorithm's effectiveness on tasks involving labeled images and text contents. \n\n3. I also like how the paper imposes assumptions and identifies/handles the portion of the vanilla BR-type risk contributing to \"train-loss hacking,\" as the rationale seems natural and might apply to other relevant tasks.\n\n***\n\nCons:\n \n1. It is unclear to me how strong those theoretical claims are.\n\n- First, the main theorem, Theorem 1, holds under a sequence of assumptions. I can see that the first part of Assumption 1 is natural, but assuming an upper bound $\\bar R$ on the density ratio might be a problem when combined with other assumptions/settings. Before continuing, I would like to point out a hidden assumption, $\\ 0 < C < \\frac1R\\ $, right before Assumption 2, where $C$ appears in $\\partial f(t) = \\boldsymbol{C}(\\partial f(t) t - f(t)) + \\tilde f(t)$, as a key parameter in the definition of $\\tilde f$. Note that this assumption translates to $0<R<1/C$. Additionally, observe that $1/5\\le C$ in all the experiments and a very small $C$ can \"damage the empirical performance\" (Remark 1). Given all these constraints, one essentially requires the density ratio to be bounded by a small absolute constant, which seems restrictive.\n\n- Second, I wonder if there is any quantitative assessment of the tightness of Theorem 1 or Corollary 1 (page 5). Let me use the latter as an example. In terms of sample size dependency, the discrepancy upper bound is $\\mathcal O(\\max \\\\{ 1/\\sqrt n_{\\text{de}}, 1/\\sqrt{n_{\\text{nu}}} \\\\} )$. For the BR divergence, is such dependency optimal (up to absolute constant factors)? As for $\\delta$, the $\\sqrt{\\log \\frac1\\delta}$ factor seems tight, but how about the other parameters? In particular, does any constant in the theorem, e.g., $\\kappa_1$ or $\\kappa_2$, has non-polynomial dependency on $C, B_p, L$, or $B_{W_j}$? I think additional details and explanations should be provided to illustrate the meaning and significance of these results. \n\n- Third, \"Computation\" would be an important aspect of the proposed heuristic. I don't see how to derive an efficient optimization procedure for finding the actual empirical risk minimizer or an accurate approximation. From a theoretical point of view, such a procedure is crucial for the sample-dependent error bounds in Theorem/Corollary 1 to take effect. For the experimental results' completeness, it also seems reasonable to add relevant details about implementing the proposed algorithm.\n \n2. I also believe the writing of the paper needs improvement. \n\n- As stated above, the assumptions, theorems, and definitions require more explanation. In particular, I suggest adding comments addressing how natural or restrictive the assumptions are, the significance of the theorem/corollary, and their optimality, and the intuitions behind the technical reasoning. For example, page 4 presents the new objective function's construction right after Assumption 2, which currently is a sequence of formulas/definitions together with light comments. In my opinion, this part is crucial for the paper and should show technical insights and novelty of the proposed method, along with relevant intuitions. Besides, the instantiation of the \"nnBR divergence\" with existing methods shown at the base of the page doesn't seem important to me and somehow introduces redundancy, given Table 1. \n\n- On page 6, the paper claims that \"the above theoretical guarantee already suffices for the basic justification of D3RE.\" I don't fully understand where this sufficiency comes from. Furthermore, I wonder if any prior or related method(s) satisfy a bound similar to that in Theorem 1, namely, if the sample sizes are large, the minimizer is essentially optimal. A concern relevant to this point is that the paper lacks references in a few places. For example, the second last paragraph on page 2 says, \"Therefore, various methods for directly estimating the density ratio model have been proposed (Sugiyama et al., 2012), and (Sugiyama et al. 2011b) ...\". My thought is that if this is a popular problem, then it should've studied by at least a few research groups instead of one.\n\n3. Other comments, suggestions, and questions.\n\n- On page 2, the original pointwise BR divergence is defined as $BR'_f(t^*\\vert\\\\!\\vert t)$. It might be better to avoid using the $(\\cdot)'$ notation as it usually serves as an indicator for derivatives.\n\n- In Equation (3) and some other definitions, I found $\\boldsymbol x_i$ is used instead of $\\boldsymbol x$, while the left-hand side quantities do not involve $i$. \n\n- On page 5, it is said that \"for the boundedness and Lipschitz continuity in Assumption 3 to hold ..., a technical assumption $b_r>0$ is sufficient.\" I wonder how the relevant quantities in Assumption 3 appear as functions of $b_r$. \n\n- On page 4, $\\ell_2(t)$ is introduced to represent $-\\tilde f(t)$. What is the purpose of this new notation?\n\nIt would be nice if the author(s) can address some of my concerns in the rebuttal. Thanks.\n\n*** ", "extra_scores": {}, "extra_text": {}}, {"review_id": "01MMxCvFeKn", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "##########################################################################\n\nSummary:\n\nThe paper studies density ratio estimation (DRE), addressing the 'train-loss hacking' problems which often arise and hamper estimation when models are too flexible. The authors propose a new risk estimator for DRE, providing a non-negative Bregman divergence estimator, with the non-negative correction. Theoretical analyses are shown with the estimation error and empirical analyses are examined in multiple machine learning problem settings.  \n\n##########################################################################\n\nPros: \n\n- A simple yet practical and principled algorithm for DRE is proposed.\n- Although the non-negative correction idea itself is not new, as the authors mentioned in Section 1, using the prior knowledge for the non-negative correction appears novel in DRE. \n- All numerical experiments considered in the paper are reasonable and interesting.\n\n##########################################################################\n\nCons (or questions): \n\n- Although the results in section 4 justify the proposed estimator has vanishing estimation error in some sense, the core idea for the results are basically a simple application of the Mcdiarmid’s inequality. I acknowledge these are highly technical results, but I believe more theoretical analyses of the approximation error would improve the paper. What conditions are needed for r^* (or model space) to have zero approximation error? How can this be explained in terms of a usual reproducing kernel Hilbert space?\n\n- Based on the theories in Section 4, the current algorithm provides an estimator that has a vanishing estimation error. As far as I understand, it might not guarantee the maximization of AUROC (or minimization of pairwise disagreement). Are there any explicit relationships between the 'consistent' density ratio estimation and the AUROC maximization?\n\n- Following the previous question, Figure 3 in the appendix shows the proposed algorithm does not diverge to the negative infinity, but it is not clear if the Bregman divergence evaluated at the proposed estimator is converging to the 'optimal' Bregman divergence value. How can we empirically justify Corollary 1 (even in a very simple simulation setting?)\n\n##########################################################################\n\nOverall, I recommend the weak acceptance. I may well have missed some points in my reading, so clarification is welcome.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper discusses the likelihood ratio estimation using the Bregman divergence.  The authors consider the 'train-loss hacking', which is an overfitting issue causing minus infinity for the divergence.   They introduce non-negative correction for the divergence under the assumption that we have knowledge on the upper bound of the density ratio.  Some theoretical results on the convergence rate are given.  The proposed method shows favorable performance on outlier detection and covariate shift adaptation.

The proposed non-negative modification of Bregman divergence is a reasonalbe solution to the important problem of density ratio estimation.  The experimental results as well as theoretical justfication make this work solid.  However, there are some concerns also.  The paper assumes knowledge on the upper bound of density ratio and uses a related parameter essentially in the method.  Assuming the upper bound  is a long standing problem in estimating density ratio, and it is in practice not necesssarily easy to obtain.  Also, there is a room on improvements on readability. 

Although this paper has some signicance on the topic, it does not reach the acceptance threshold unfortunately because of the high competition in this years' ICLR.  
Decision: Reject