Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper introduces a density ratio estimator (DRE) based on the Bregman divergence which is different from Kato & Teshima (2021).
The author(s) derive(s) non-asymptotic error bounds for the proposed DRE, which turns out to be slightly better than that of Kato & Teshima (2021).
Based on the established bounds, the paper then studies why the telescoping density-ratio estimator (TRE) has a good empirical performance compared to single-ratio DRE.
On a specific bridging methods proposed by the author(s), it was argued that TRE has a better asymptotic error bound than that of the single-ratio method.
It also indicates that the originally proposed bridging method in TRE could have some insatiability issue.
strengths_and_weaknesses: Pros
- The paper studies an important problem that wasn't paid enough attention.
- The method and analysis presented in the paper is novel.

Cons
- Conclusions derived from the analysis are not verified empirically. For example the choice of bridging method (mixing v.s. convolution).
- The analysis of TRE is based on an alternative bridging method for analysis convenience, which may not be enough to explain why TRE performs well.
- The paper is dense and not easy to follow for readers who are not familiar with the proof techniques.
questions: - $\exp$ is used to make the density ratio estimator positive but it is known that $\exp$ is numerically unstable and in deep learning usually $\mathrm{softplus}$ is preferred. Can you justify your choice here?

Typos
- L134: "Section ??" -> Section 4
- L260: "TDR" -> TRE
limitations: Limitations are discussed but not potential negative societal impact.
The work is theoretical and I don't see direct societal impact.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies density ratio estimation based on deep ReLU networks. Based on a loss criterion by the Bregman divergence (eq.1), and under weak conditions (stated in assumptions 1-3), the authors showed that this family of density ratio estimators can achieve optimal convergence rate (Thm 1 & 2, and 3).

The authors also extended their bound into the cases where the data is on a low-dimensional submanifold (Thm 4), showing the curse of dimensionality can be alleviated.

As an application, the authors further applied their bounds to the Telescoping density-Ratio estimation (TRE) (Rhodes et al., 2020). The author's bounds can help demonstrate the advantages of TRE over single-ratio estimators.
strengths_and_weaknesses: Pro:
- Solid theoretical results.

Con:
-The paper contains a list of formal results and lacks intuitions, numerical examples, and detailed explanations. As a result, it is hard to read.
- The theoretical results are for general Bregman divergences satisfying certain smoothness and convexity constraints. Although some examples are given in table 1, it is not clear how certain choices of the Bregman divergence can further enhance the results.

Please see below for some minor comments (these are not questions to be addressed in the rebuttal).

eq.(1), write some intermediate step, as the reader may be familiar with Bregman divergences but not eq.(1) and wonder where it comes from.

the unnumbered equations between eq.(1) and eq.(2): $R\in\cdots$ (use set notations)

L134: Section ?? below (missing reference).

Pdim: mention the relation with VC dimension (that is widely known).
questions: The current paper studied density estimation of p and q, which are pdfs supported on a hypercube [0,1]^d. It is not clear how the results can be generalized.

Assumption 2. As a ReLU network output values in the range (0, \infty). It is not clear how this assumption can be satisfied. It should be explained in more detail in the text.

In equation (3),  $\hat{D}$ is the global optimum by definition. In practice, one only gets a local optimum solution through neural network training. Can the stated bounds guarantee the density-ratio estimation quality of these local optimums?

The main weaknesses mentioned in "Strengths And Weaknesses" can be regarded as my questions.
limitations: This work is of theoretical nature. I could not see any negative societal impact.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper establishes non-asymptotic error bounds for a density-ratio estimator based on the Bregman divergence. These bounds depend on the approximation error and pseudo-dimension of the underlying function classes. If one assumes the optimal estimator belongs to the Hölder class, combing with existing results on the approximation error of neural networks to Hölder functions, and the pseudo-dimension of neural networks, the authors establish error bounds of neural-network based density-ratio estimators. If the data is concentrated on a low-dimensional manifold, the curse of dimensionality can be alleviated. The authors also apply the error bounds to analyze a telescoping density-ratio estimator.
strengths_and_weaknesses: Strengths:
This paper provides a general non-asymptotic bound for the density-ratio estimator, which does not depend on any specific function class. With known neural-network theoretical properties, this general bound can be applied to the deep density-ratio estimator, which is in some sense optimal. The convergence rate is also slightly faster than known result in [1].

Weaknesses:
1. The paper is not carefully written. Line 134 contains a missing reference. Line 260 uses an abbreviation TDR (I believe it is a typo of TRE?), which is not defined anywhere.
2. The authors analyze a different telescoping density-ratio estimator, rather than the one in [2], and acknowledge that the techniques used for the chain defined in the paper do not apply to the estimator of interest in [2]. This means that the analysis is only for the problem defined in this paper. The authors should provide some evidence that the chain defined in this paper has a superior or comparable performance to the estimator of interest in [2].

[1]Kato, M. and Teshima, T. Non-negative bregman divergence minimization for deep direct density ratio estimation. In International Conference on Machine Learning, pp. 5320 – 5333, 2021.

[2] Rhodes, B., Xu, K., and Gutmann, M. U. Telescoping density-ratio estimation. In Advances in Neural Information Processing Systems, 2020.
questions: 1. Do you have any evidence that the chain defined in the paper has a better or similar performance to the one in [2]?
2. Can the convergence result in [1] induce similar result on the chain problem defined in the paper or the one in [2], i.e., the chains are better than a single-ratio estimator?
limitations: No other major concerns than the ones listed in weaknesses.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: In this paper, the authors aim to establish non-asymptotic error bounds for a nonparametric density-ratio estimator which minimizes the empirical Bregman Divergence (BD) score over a class of neural network functions. More specifically, let $D^*=\log R^*$ where $R^*=p^*/q^*$ is the density-ratio that we would like to estimate. In addition, assume that we have $n_p$ i.i.d. samples from $p^*$ and $n_q$ i.i.d. samples from $q^*$.  The empirical nonparametric density-ratio estimator of $D^*$ over a class of feed-forward neural network function $\mathcal{F_{\mathrm{FNN}}}$ is defined as $\hat{D}:= argmin_{D \in \mathcal{F_{\mathrm{FNN}}}} \hat{\mathcal{B_{\psi}}}(e^D)$ where $\hat{\mathcal{B_{\psi}}}(\cdot)$ is the empirical Bregman Divergence (BD) score. 

The authors first show that under some mild conditions, with high probability, $||\hat{D}-D^*||$ is bounded above by $||D_{\mathrm{NN}}-D^*||$ plus some $O(\sqrt{(\log n) \mathrm{Pdim}(\mathcal{F_{\mathrm{FNN}})}/n)}$ terms where $D_{\mathrm{NN}}= argmin_{D\in \in \mathcal{F_{\mathrm{FNN}}}} ||D-D^*||$, $\mathrm{Pdim}(\mathcal{F_{\rm{FNN}}})$ is the pseudo-dimension of $\mathcal{F_{\mathrm{FNN}}}$, and  $n:=\min (n_p,n_q)$ (a PAC-bound). Then, in the next parts, the authors show how to bound $||D_{\mathrm{NN}}-D^*||$ for a special case where $D^*$ belongs to a Holder class of functions, $\mathcal{H^{\beta}}([0,1]^d,M)$. The authors proved that this term is bounded by a term of order $(KL)^{-2\beta/d}$ if the neural network has with $\mathcal{W}=38(\lfloor \beta \rfloor+1)^2 d^{\lfloor \beta \rfloor +1} L\lceil \log_2(8L)\rceil$ and $\mathcal{D}=21(\lfloor \beta \rfloor+1)^2 K \lceil \log_2(8K)\rceil$. By additional assumption that the data from $p^*$ and $q^*$ are concentrated on some $\rho$-cover of a compact finite-dimensional Riemannian submanifold in $[0,1]^d$, the authors can obtain an improved bound on  $||D_{\mathrm{NN}}-D^*||$ which reduces the curse of dimensionality. Finally, the authors perform error analysis for a telescoping density-ratio estimator and affirm that the telescoping strategy (TRE) can improve the expected error $||\hat{D}-D^*||$ as $n\to \infty$, which affirms a conclusion by Rhodes et al. (2020) by experiments. 

The key contribution of this paper is Theorem 1 which provides a PAC-bound for $||\hat{D}-D^*||$ via $||D_{\mathrm{NN}}-D^*||$.  The proof of this theorem is based on a good observation that the Bregman divergence score function $\hat{\mathcal{B_{\psi}}}(t)$ is sum of two Lipschitz functions and an interesting fact that $\hat{\mathcal{B_{\psi}}}(e^D)- \hat{\mathcal{B_{\psi}}}(e^{D^*})\sim ||D-D^*||^2$ under some bounded conditions. Hence, the authors can apply some classical results in learning theory such as symmetrization inequalities and Talagrand's contraction theorems to bounds $||\hat{D}-D^*||$. The other results are mainly based on existing results related to an approximation of a Holder function by a neural network function (Jiao et al. (2021)) and/or another dimension reduction result by (Nakada and Imaizumi, 2020) to bound $||D_{\mathrm{NN}}-D^*||$.
strengths_and_weaknesses: This work can be considered a novel combination of well-known techniques. The error bounds in this paper are new (to my knowledge). By setting a distribution is fixed, the error bound results in this paper can recover the minimax rate of the density estimation in Tsybakov (2008) with an improvement on the effects of $d$ (cf. Section 3.2). 

In general, all the results in this paper are well proved and look correct. There are some typos but it does not hinder readers from understanding the results and their proofs. There is a problem related to the minimax optimal conclusion in line 168. More specifically, the authors mentioned that the convergence rate is optimal. This looks not make sense if the authors only based on the fact that this bound is minimax optimal when fixing a distribution. Optimality by fixing one does not imply optimality for the fraction of the two distributions.

From the technical viewpoint, there are some interesting ideas in the proofs such as converting the estimation problem for $R^*$ to the estimation problem for $D^*=\log R^*$, partitioning the range of $\hat{D}$ to make use the fact of that if $||D-D^*||\leq r$ then $||D-D^*||_{n_p,n_q}\leq 2r$ to bound $||\hat{D}-D^*||$ in the proof of Theorem 1, or using i.i.d. Bernoulli random variables to telescope density-ratio estimator in Section 4. 

However, this paper contains some weak points as follows.
   1. To obtain an upper bound on $||D_{\mathrm{NN}}-D^*||$, the authors need to make an assumption that $D^*$ belongs to some special class of functions. More specifically, the authors assumed that $D^* \in \mathcal{H^{\beta}}([0,1]^d,M)$. However, this looks unavoidable with deep-learning-based methods. An example of $p^*$ and $q^*$ (common distributions, exponential class for example) such that $R^*$ belongs to this class will make your paper more interesting.  
  2.  If $D^*$ is unbounded above, the result in Theorem 2 looks not tight enough.
  3. The optimality of the bounds in Theorem 3  needs to justify (see the comment below). 
questions: Here is a list of typos and questions:

1. In line 586, please explain how to bound $||\tilde{D_E^*}(Ax')-D^*(x)||$ by $M\rho$. It looks not clear how to obtain this. 
2.  Please explain why the convergence rate in (8) is optimal (a conclusion in line 166). See my comments in the previous part. 
3.  Some typos: in line 134; Proposition 1 ($2 M_0$ should be replaced for $M_0$); a definition of $\Delta_{\psi}(x,y):=\psi(x)-\psi(y)-\psi'(x) (y-x)$ should be mentioned in the proof of Lemma A.2; a citation for (A.12) should be provided; and the norm of $\rm{SL}$ (not of its derivative) in line 569, etc. Please correct them.

limitations: This is a theoretical work. The authors already finished the checklist as well as stated the limitations of theorems and results.
review_title: null

Meta-review: metareview: This paper establishes non-asymptotic error bounds for nonparametric density-ratio estimators using deep neural networks.
According to the reviews this is a borderline paper and some changes will be needed before publication. In particular, some reviewers found the paper to be too dense and not easy to follow. The paper lacks intuitions, detailed explanations, and numerical illustrations. 

confidence: Less certain
Decision: Reject