Bounds on $L_p$ Errors in Density Ratio Estimation via $f$-Divergence Loss Functions

Authors: Yoshiaki Kitazawa
Primary area: learning theory
Keywords: density ratio estimation, variational divergence optimization, Kullback–Leibler divergence, $f$-divergence, $L_p$ error, the curse of dimensionality, GAN

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

Decision: accept (poster)
Reviewer scores: 6, 5, 8, 5

Reviews and discussion:
<thread>
creation date:
1730535039539

thread_type:
official_review

<thread_object>
creator: reviewer_ebzv

<content>
summary:
This article presents an analysis of error rates for density ratio estimation (DRE) in the context of $L^p$-losses applied to $f$-divergence minimization. The study derives upper and lower error bounds, noting that these rates increase with \(p\) and exhibit the curse of dimensionality. Theoretical findings are supported by numerical illustrations, which help validate the proposed rates.

strengths:
Problem is interesting. The proofs seem to be correct. Numerical illustrations support the theoretical findings.

weaknesses:
While the work appears mathematically sound and introduces some interesting proof techniques, I am not inclined to recommend acceptance at this stage, primarily due to the following points:

- **Lack of Comparison with Recent DRE Literature**
    The paper would benefit from a more thorough comparison with recent work in DRE estimation, particularly research involving divergence-based losses. It is, at the current stage, not possible for me to set the results into the context of the large field of DRE (see questions).
- **Context for Techniques in Sections 4.1 and 4.2**
    The conceptual reformulation presented in Section 4.1 and the nearest-neighbor-based approach in Section 4.2 would benefit from contextualization. Comparing these methods with existing approaches would clarify their originality and contribution to the field.
- **Practical Applicability of Assumptions**
    The main results rely heavily on the Lipschitz continuity of both the function class used and the energy function of the distributions. However, ensuring these assumptions in practical settings may be challenging. This reliance makes the interpretability of the bounds somewhat limited and may constrain practical applicability.
- **Interpretability of Practical Implications**
    It remains unclear what practical conclusions can be drawn from the theoretical results. For example, are there implications for algorithmic design that might mitigate the curse of dimensionality or handle large sample sizes effectively? The implications of error rate growth with respect to $p$ should also be discussed.
- **Minor Issues and Clarifications**
    The parameter $N$ in Theorem 3.5 is undefined. It should be clarified in what sense equation (4) holds---is this with high probability?

questions:
+ Are conceptual reformulation presented in Section 4.1 and the nearest-neighbor-based approach in Section 4.2 widely used or newly adapted in the paper?
+ How does Assumption 3.3 relate to the pseudo-self-concordance of losses as discussed in [1]?
+ Could the proof techniques introduced here be compared to those used in [1, 2]? Is the presented approach more general than these prior works?
 + Can the derived rates with respect to sample size be directly compared to those established in the literature?

[1] Zellinger, W., Kindermann, S., and Pereverzyev, S. V. "Adaptive Learning of Density Ratios in RKHS." Journal of Machine Learning Research, 24:1–28, 2023.

[2] Menon, A. and Ong, C. S. "Linking Losses for Density Ratio and Class-Probability Estimation." International Conference on Machine Learning, pp. 304–313, PMLR, 2016.

----------------------------------------------------------------------------------------------------------
**after the rebuttal, I raised my score to 5**
</content>
</thread_object>

</thread>
<thread>
creation date:
1730671681782

thread_type:
official_review

<thread_object>
creator: reviewer_tzbe

<content>
summary:
The paper proposes an approach to density ratio estimation based on $f$-divergences. This idea originated in a paper by Nguyen, Wainwright, and Jordan, who introduced this methodology, which also forms the foundation of generative adversarial networks (GANs). The dual representation of the $f$-divergence involves optimization over a function space, where the optimizer—obtained, for instance, using a neural network—provides an estimator for the likelihood ratio when evaluated on samples. The consistency of this estimator was established in Nguyen et al., and various convergence results have been proved over recent years. The main contribution of this paper is to provide upper and lower bounds on the $L^p$-error, assuming both measures have compact support and that the log-likelihood function is bi-Lipschitz. These bounds are the first of their kind.

strengths:
The paper is a novel and original contribution to the field of density estimation and highly relevant to recent advances in generative modeling (for example through generative adversarial networks). To my knowledge this are the first $L^p$-error bounds in this context. 
The proof of the result is very clever and relies on a representation of the $f$-divergence (called the conceptual loss function) which provides access the density ratio.  The estimates are then obtained using a "nearest neighbor" approach and by showing that the conceptual loss function and the real loss function are close to each other.  I believe that the techniques of proofs will find other applications where $f$-divergences are used (e.g. in generative modeling).  I found the presentation of the results to be excellent  both, conceptually, in the main text and, technically in the supplementary material.  Also notable is that this result is practical as the implementation of the estimator is totally straightforward using a neural network architecture.

weaknesses:
+ There is a very unfortunate typo in the informal theorem 3.5 where in the lower bound  $(1-p)$ should be $(p-1)$.   

+ An explanation of why the result does not depend on the $f$-divergence should be provided.  I believe this is because of the Lipschitz assumption on the log-likelihood and the compactness of the support. In that way the behavior of $f$ at $0$ and at $\infty$ are irrelevant. 

+ Some head-to-head experimental comparison with other density ratio estimators would have been helpful.

questions:
+ Can you explain why the choice of $f$ in the divergence does not matter?  Does it only change the constant? 

+ What are the implications of your results on the analysis of GANs?

+ What are the implications of your results neural estimation of $f$-divergence (see e.g. the recent https://jmlr.org/beta/papers/v23/21-1212.html)?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730691346202

thread_type:
official_review

<thread_object>
creator: reviewer_mvfa

<content>
summary:
* The paper provides new upper and lower bounds on the Lp errors of a specific density ratio estimator. (Equations 4,5, and 6).
This estimator is constructed by minimizing an f-divergence based loss function. 

These bounds provide new insights about how the dimensionality of the data, and the KL divergence between the distributions affect the error of the estimator.

strengths:
* As far as I know, the derived lower and upper bounds on the density ratio estimator are new.
* The paper is well-written, and easy to follow.
* The presentation is clear.

weaknesses:
The theoretical results are interesting. 
In my opinion, what is missing from the paper is to show that these theoretical results can make a difference in some important applications. The paper contains a nice list of motivations for density ratio estimation, but the experimental section only contains some simple toy problems, and therefore the impact of the theory in real applications is not perfectly clear.

questions:
* Equation 5 (the upper bound) contains the expectation operator on the left-hand side. This expectation is missing from the lower side (Eq 4). Is it a typo?
* In Equations 4 and 5, is it possible to create bounds for dimensions 1, and 2 as well?
* The upper and lower bounds are only derived for a specific density ratio estimator. Is it known how the convergence rate of this estimator compares to other density ratio estimators?
* How can we use these theoretical results in applications?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731095560087

thread_type:
official_review

<thread_object>
creator: reviewer_hprf

<content>
summary:
This paper establishes L_p​ error bounds of the density ratio in Density Ratio Estimation under f-divergence loss. The bounds scale with $N^{-1/d}$ and certain p-Renyi divergence, but is independent from the specific choice of fff-divergence.

strengths:
The problem of uncertainty quantification in density ratio estimation is an important fundamental question. This work contributes a new understanding of its theoretical limits by deriving L_p​ error bounds of the density ratio. The nearly matching upper and lower bounds are a strong point, and the independence on the specific f-divergence within the loss function is also intriguing.

weaknesses:
The bound’s dependence on $N^{−1/d}$ means that in high-dimensional spaces (where d is large), the error bound becomes practically useless. There is also a lack of downstream application or implication of the theoretical results. As a whole, this raises questions on the meaningfulness of the bounds. 

The experiments presented exhibit high variance, which limits the interpretability and robustness of the empirical validation.

questions:
How do these bounds compare to other known bounds in DRE or related density estimation methods?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732807845242

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
We sincerely thank the reviewers for their valuable comments and suggestions during the review process, which have greatly contributed to improving our work. We have carefully revised our paper based on the discussions and feedback provided.

We deeply apologize for the delay in submitting the revised version.

Below, we outline the key revisions made to the manuscript in response to your comments:

1. Comparison with existing DRE bounds (Section E.1 in the appendix)  
   - We have added a detailed comparison between the results of this study and existing DRE bounds in Section E.1 in the appendix. We have carefully revised our comparison with prior work and found that our upper bounds are tighter than the existing minimax bounds in both $L_1$ and $L_2$ errors.  
   - Additionally, we identified additional prior works which are particularly relevant to this study and have included them as references.

2. Remarks on Assumption 3.3 and related assumptions in prior work (Section E.2 in the appendix)  
   - In Section E.2 in the appendix, we have included a detailed discussion on the relationship between Assumption 3.3 and the pseudo-self-concordance of losses to address the concern raised by Reviewer eBZV.  
   - The discussion has been refined, and we believe that it provides a more rigorous and clearer explanation regarding this issue.

3. Applications of this study (Section E.3 in the appendix)  
   - We have added a discussion on potential applications suggested by this research in Section E.3 in the appendix based on the discussion during the review process. This new section elaborates on how the findings could contribute to related fields.

4. Formatting and Minor Revisions:  
   - We have updated the Related Work in Section 1 by adding important relevant citations.  
   - We have corrected grammatical errors and typos for improved clarity. While the main content of the paper remains unchanged, we have also made adjustments to the formatting due to space constraints, such as relocating figures in the manuscript.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper provides (nearly matching) upper and lower bounds on $L_p$ error in density ration estimation (DRE) for a natural class of $f$-divergence-based estimators. The bounds are independent of the specific $f$-divergence used, which is intriguing. They are instead dominated by the dimensional dependence, scaling with $1/N^{1/d}$. The proof techniques appear novel and interesting. The main reservations about the paper stemmed from the limitations of the $1/N^{1/d}$ scaling in high dimensions, lack of proper comparison with prior work, and lack of applications. The latter two points were mostly addressed during the rebuttal period, though the authors are advised to further expand on those discussions in the next revision. For the first point, I believe there is value to the results, despite such scaling, for the following reasons. First, given that the considered estimators are natural and commonly used, it is helpful to understand their limitations through the provided lower bounds. Second, as was revealed during the discussion, there are no alternative upper bounds that provide a better scaling with the dimension.