Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: SUMMARY:
This 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.

STRENGTHS:
- This work introduces a new family of non-negative Bregman divergences.
- The proposed estimator is theoretical justified.
- Experiments show convincing results over the original Bregman divergences (at least for LSIF and PU).
- The paper is well written, although quite difficult to follow without some theoretical background.

WEAKNESSES:
- 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?
- The experiments do not include BR_BKL nor nnBR_BKL, which I would have found quite interesting for the reason mentioned above.
- 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? 
- How tight is the error bound for D3RE?
- Some recent applications of density ratio estimation that could have been worth mentioning as well as likelihood-free inference approaches based on likelihood ratios.

DISCLAIMER:
Due 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. 
review_title: Delay with my review

final_score: rating: 5: Marginally below acceptance threshold
review_content: ***

Summary:

The 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.

***

Reasons for score:

I 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. 

***

Pros:

 
1. 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).

2. 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. 

3. 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.

***

Cons:
 
1. It is unclear to me how strong those theoretical claims are.

- 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.

- 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. 

- 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.
 
2. I also believe the writing of the paper needs improvement. 

- 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. 

- 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.

3. Other comments, suggestions, and questions.

- 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.

- 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$. 

- 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$. 

- On page 4, $\ell_2(t)$ is introduced to represent $-\tilde f(t)$. What is the purpose of this new notation?

It would be nice if the author(s) can address some of my concerns in the rebuttal. Thanks.

*** 
review_title: Both the problem and contribution are interesting, but the writing and explanation need improvement. 

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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.
The 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.
The authors support their suggestion by experimenting: computing anomalies and learning from positive or unlabeled data.

The 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.
More 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. 
In particular, one can use arbitrarily strong learning models via the approach of the following paper:
"Estimating Divergence Functionals and the Likelihood Ratio by Convex Risk Minimization" by Ngoyan, Wainright, Jordan.
A comparison with this paper (and the rich literature that cites it) is lacking. 
Another line of research for direct estimation comes from the econometric community. A starting point is
"Covariate balancing propensity score" by Imai and Ratkovic. 
The latter is less directly related but represents a huge body of work on direct density ratio estimation that should be cited and discussed.

To 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. 

Specific comments, mostly related to style and presentation:
1. 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.
2. Don't assume that readers are familiar with Kiryo et al.
3. 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? 
4. Figure 1 suggests the issue is over fitting, I didn't understand the claim it is of a different flavor.
5. I thing the assumption that the ratio is bounded is a reasonable one. One can try to justify it better.
6. The last paragraph of Section 3 has to be explained better.
7. 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?
8. 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).


review_title: The paper suggests a way to estimate the density ratio of two distributions. While the contribution seems potentially useful, it is very hard to follow.

final_score: rating: 6: Marginally above acceptance threshold
review_content: ##########################################################################

Summary:

The 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.  

##########################################################################

Pros: 

- A simple yet practical and principled algorithm for DRE is proposed.
- 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. 
- All numerical experiments considered in the paper are reasonable and interesting.

##########################################################################

Cons (or questions): 

- 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?

- 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?

- 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?)

##########################################################################

Overall, I recommend the weak acceptance. I may well have missed some points in my reading, so clarification is welcome.

review_title: Interesting analysis of density ratio estimation

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