Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Gradient flows defined on the Wasserstein space have received particular attention from the statistical and machine learning community, since they allow to fit a target distribution starting from another source distribution. They consist in minimizing a certain functional, and the choice of this functional strongly affects its theoretical properties and empirical performance. Recent work have studied gradient flows based on specific functionals, including the maximum mean discrepancy (MMD) and the Kullback-Leibler divergence (KL). This paper focuses on these two cases and proposes a novel gradient flow method based on an approximation of KL, in order to alleviate the limitations induced by MMD and KL. 

First, the authors introduce a novel divergence on the space of probability measures, which corresponds to a relaxed version of the KL and is called the "KL approximate lower-bound estimator" (KALE, Definition 1). They study some of its topological properties (Theorem 1), show that KALE interpolates between KL and a specific instance of MMD if the associated kernel is bounded (Proposition 1). Besides, KALE admits a dual formulation (equation (6)), which can be approximated using samples from the two distributions of interest (eq. (7)). 

Then, the authors develop the gradient flow in the Wasserstein space based on KALE, by solving a specific instance of the continuity equation in eq. (8): see Proposition 2. The resulting gradient flow is shown to ensure global convergence under certain assumptions (Proposition 3). A practical algorithm is developed to approximate the solution of the KALE gradient flow, and imply discretizing the time of the continuity equation and performing gradient descent on finitely many samples (Algorithm 1). This "particle descent" scheme induce an approximation error (due to the use of samples instead of their underlying densities), which is upper bounded in Proposition 4. The authors also present a variant of this algorithm, largely inspired by prior work on MMD flows, which incorporate Gaussian noise (Section 4.2). The goal of this approach is to relax the convergence guarantees associated to time discretization, which are too strict (Proposition 5). Experiments on different synthetic settings are finally conducted to illustrate the advantages yielded by the KALE gradient flow over the MMD and KL counterparts (Section 5).

main_review: This work is relevant for the NeurIPS community, since prior work have demonstrated that gradient flows can be employed in modern machine learning approaches, including generative modeling. Moreover, the newly introduced probability divergence KALE is clearly motivated: according to the empirical analysis in Section 5, KALE can return useful information when comparing two distributions, even when their support do not overlap (unlike KL), and might offer a higher discriminative power than MMD. These advantages, combined with the topological properties in Theorem 1 and the fact that it can be estimated when the two distributions are accessible through samples only, suggest that KALE has great potential for other applications than gradient flows.  

The paper is very dense as it provides numerous theoretical contribution on novel tools, and due to lack of time, I was not able to thoroughly check all the proofs in the appendix. The empirical analysis in Section 5 illustrates well the flexibility of KALE gradient flow over the MMD and KL ones, likely due to its interpolation property (Proposition 2). The rest of the claims were not empirically verified, and in my opinion, some of them should be discussed more: 

(A1) "As shown in [5], the KALE's sample complexity scales with $\frac1{\sqrt{N}}$" (l.157-158), where [5] refers to "Generalized energy based models" (Arbel et al., 2021). However, the authors also emphasized that the KALE they consider "differs from the one in [5]" (l.111). In that sense, it is not clear why the sample complexity in [5] still applies here. On the other hand, that sample complexity is said to be "similar to the sample complexity of Sinkhorn divergences". The sample complexity of Sinkhorn divergences also strongly depends on the value of its regularization coefficient; is it the case for KALE?

(A2) The convergence rate of KALE flow derived in Proposition 3 is said to be slower than the one yielded by KL flow (l.192), but it is not clear how it compares with MMD flow (in particular, with Proposition 7 in "Maximum Mean Discrepancy Gradient Flow", Arbel et al., 2019). Therefore, I have trouble understanding why "trajectories of the KALE flow exhibit better convergence properies when compared to the MMD flow" (l.326-327): it this claim solely supported by the empirical results in Section 5 for now?

(A3) Proposition 4 establishes an approximation error bound, which guarantees that "given sufficiently many samples of $\mathbb{P}_0$ and $\mathbb{Q}$, one can approximate an exact discrete KALE flow ... with arbitrary precision" (l.240-242). However, the derived bound depends on other constants than the number of samples, whose impact is not discussed at all. In particular, the smaller $\lambda$, the larger $A$ (l.239), so the larger $N$ needs to be to compensate. This might be a limitation of KALE in practice and it should be addressed in the paper to give a more sensible interpretation. 

The aforementioned points explain why I can't give a higher overall score for now. 

This paper is very well written, but some parts in the main document are not self-contained, which makes them hard to understand. I encourage the authors to address the following points to improve readability.

(B1) Assumptions 1 to 3, which play an important role in most theoretical results in this work, are only presented in the appendix (Section B). The main document should at least provide a small description of them. Besides, it is not clear to which extent these assumptions are met in the experiments.

(B2) The notation $\dot{H}^{-1}(\mathbb{P}_t)$ in the negative Sobolev norm is not clear. The definition of this norm (given in Section F) could be recalled in Proposition 3.

(B3) The set $\mathcal{H}_n$ in equation (13) is not defined.

(B4) The constants in Proposition 4 ($L$, $K$, $\mu$) are not explained. This point is actually connected to (B1), since these constants come from the assumptions.

Some other minor inaccuracies and typos are given below.

l.97: "an superscript" -> "a superscript"

Equation (7): Given equation (6), why is it -1 instead of +1?

Equation (11): $\partial \mathbb{P}_t$ -> $\partial_t \mathbb{P}_t$

Equation (13): What is the norm used here? (Precise the set)

l.214 "Approxation" -> "Approximation"

Equation (15): the set of $h$ should be precised. 

Algorithm 1: 
- Extra "max_iter",
- The variable $\texttt{v}$ should depend on $\texttt{h}$_$\texttt{star}$,
- Precise what operation $\texttt{log}$_$\texttt{ratio}$ does.

l.257: Given the rest of the statement, $\mathcal{D}_{\beta_n}$ should be defined as a function of $\mathbb{P}_n$.

l.272: "appearing in the the"

l.284: "and thus the the" 

Figure 3: in the legend, "and and"

l.624: "ahd" -> "and"

l.646: "metrices" -> "metrizes"

Equation below l.651: $\mathcal{K}(0, \mathbb{P})$ -> $\mathcal{K}(0_{\mathcal{H}}, \mathbb{P})$

Equation (27): $\mathbb{P}$ should be $\mathbb{P}_t$


limitations_and_societal_impact: The authors addressed two limitations: (i) the condition on the noise schedule in Proposition 5 might be too strict, given Figures 3 to 5; (ii) KALE flow (Figure 2) does not recover outliers well (Figure 2, l.303-305). 

The societal impact is not discussed.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors propose KALE Flow to transport mass from one distribution to another. They also study the properties and convergence of the proposed algorithm.
main_review: 
This paper provides a good theoretical analysis of KALE, and introduces a particle descent algorithm.
However,  as the authors stated, Arbel M, Zhou L, Gretton A.  2021 studied KALE previously.  The main contribution in this paper  compared with Arbel M, Zhou L, Gretton A.  2021, is   the optimization guarantees. However, the main idear of this  part is similar to the MMD flow paper. For the numerics,  I am not really convinced by the toy experiments.

 It is better to present several concrete examples, in which the kernelized KL divergence has a closed-form solution. Or the authors may provide several toy examples to compare the advantage of the proposed generalized KL divergences.
Some  related works are missing, for example,  Li et.al, Natural gradient via optimal transport, Information geometry, 2018; Li, Hessian metric via transport information geometry, 2020.

Another issue is  the exponential dependence on the iteration number $n$ seems unavoidable in the current context. If my understanding is right, KALE flow converges at an extremely slow rate $O(poly(1/\log n))$ by choosing $n = O(\log N)$.
Therefore,  the KALE flow becomes less appealing. 




limitations_and_societal_impact: No.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the Wasserstein gradient flow of the KALE, a lower bound estimator of the KL divergence. By time discretization, this flow leads to an algorithm to sample from a target distribution for which samples are known (in contrast to the setting where the log density is known). Moreover, this KALE flow performs well in the case when the initial and the target distribution have disjoint supports, a setting in which the KL flow is not defined. 
main_review: Originality: The paper is in two parts. 

The first part is about defining the KALE, a relaxation of the KL which is not equal to infinity if the two distributions are singular. The KALE depends on a relaxation parameter and on the choice of a RKHS, and is shown to interpolate between the MMD and the KL (by setting the parameter accordingly). The main mathematical remark here is that the derivative at zero of the objective defining the KALE is the witness function whose norm is the MMD. This is hidden is the appendix, I would suggest to state it in the main paper as a Lemma. 
Except the weak continuity of KALE, this part seems to be mainly an adaptation of [5], for the purpose of defining the KALE flow, which is the topic of the second (and main) part of the paper. 

The second part is about the KALE flow. The authors first establish the existence and uniqueness of the KALE flow, a task which is non trivial due to the fact the KALE doesn't have the form of a free energy.  Then, under a boundedness assumption of the flow, they show a O(1/t) convergence rate of KALE to zero along the flow. This results seems to be mainly an extension of a result of [3]. 
I don't think that the convergence of the KL would be faster (as suggested after Prop 3) because KL does not satisfy log Sobolev inequality.

Additionally, the authors propose their main algorithm, obtained as a time discretization of the KALE flow. This algorithm is a provable approximation of the Euler discretization of the KALE flow (which is intractable). 

Finally, they propose a modified algorithm by introducing a Gaussian noise at each iteration of the algorithm. This seems similar to a technique used in [3]. This is the least convincing part of the paper because Prop 5 relies on an assumption that cannot be checked (and I cannot find a case where this assumption holds, it can be the case that this assumption is super strong), and empirically this noise injection does not lead to large improvements. Therefore, the introduction of noise is not really justified. 

The simulations of the KALE flow are nice and show what the KALE flow brings compare to other flows such as MMD flow of KL flow. The KALE flow improves the convergence in the case where the initial and the target distribution have disjoint supports. 

Refs: Various papers have investigated the task of sampling in the case where source and target have disjoint supports, **in the case where the log density is known** in particular Arxiv 1507.02564, 1802.10174, 2006.09270, 2010.16212









Quality and clarity: The paper is rather clear but would deserve more polishing. There are many typos in the appendix, and also some typos in the main paper (l.13, l. 116, l.214, l.284, Eq (13) etc.). 
It would be better to move the assumptions in the main paper (and correct the typos in the statement of the assumptions). 
The bibliography has not been cleaned before submission. Refs [1] and [2] are almost the same and the authors refers to [2] as [1] sometimes in the appendix. Venues, names etc. have to be harmonized. 
Finally, the implementation of Algo 1 should be discussed a bit more (2 more lines would be sufficient).

Significance: Overall, the content is novel and relevant to the community, but the main results seem close to those in [3] and [5].


MINOR:

l. 57: "generalization properties"? I don't understand
l.92: It seems better to write that we work on an open set X endowed with its Borelian sigma-algebra
l.124: Strong convexity is used to prove that KALE is a probability divergence
l.151: Why not using directly the primal formulation of KALE?
l.295: Why are the heart and the spiral supported on disjoint subsets? This is not seen on the figure.
l.306 "the target admits a positive density"



limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a new probability divergence called KALE (KL approximate lower-bound estimator) that interpolates between the KL divergence and MMD through a scaling parameter. The motivation comes from regularizing the dual formulation of KL, and KALE has been shown to exhibit desirable topological properties. In addition, the Wasserstein gradient flow of KALE is derived and a particle-based descent algorithm is introduced to compute the KALE flow in practice. Consistency and global convergence under noise injection of the proposed algorithm have been shown. Experiments on toy examples have been conducted to demonstrate empirically that the KALE flow indeed interpolates between those of KL and MMD, while having a "non-flat" geometry (compared to MMD) and requiring only sample access to compute (compared to KL).
main_review: The theoretical aspect of the paper is quite solid. While the established properties of KALE as a probability divergence are not surprising - after all it interpolates MMD and KL and hence ought to enjoy the properties of both - the exposition is clear and rigorous. It is perhaps a bit lacking in motivation: what motivates the regularization in (2), and what does the term do intuitively? The choice seems rather arbitrary to me. It would also be nice to have some comparison with Sinkhorn divergence, which also interpolates between MMD and KL: what theoretical advantage does KALE have compared to it? why do we need another interpolating divergence?

Using KALE as a gradient flow is interesting as it circumvents a lot of the problems that KL flow has and it is curious that it converges slower than KL. The particle descent algorithm is natural and not very novel, but the consistency of the descent algorithm is well justified. I'm wondering if it is possible to avoid space discretization (particle-based methods)? For instance, you can parameterize $\mathbb{P}_n$'s using normalizing flow, and then using techniques similar to "Stochastic Optimization for Large-scale Optimal Transport" by Genevay et al. for solving for finding $h_n^\star$ in an RKHS. To me, there is this disconnection where a large part of the theory is based on the RKHS theory but the algorithm has no use of it.

For the experiments, it is nice that the properties of KALE flow are checked empirically, but the setups are simple 2D examples. I will be interested in seeing how KALE would fare in higher dimensional tasks, such as when the density is defined on a submanifold. In general, I found the experiments section a bit weak and lacks applications: for what practical problems would people use KALE gradient flow for, compared to alternatives? Some comparison with other gradient flow algorithms (such as the SVGD algorithm by Chewi et al.) on a larger scale setting would be nice.

Some minor comments:
- Line 147: what is $h^*$?
- Line 608: "litterature"
- Figure 2: where is MMD result?
- Algorithm 1 could use some captions to point back what "backprop", "log_ratio" refer to in the main text.
limitations_and_societal_impact: The authors have not addressed the limitations or potential negative societal impact.
review_title: null

Meta-review: This paper develops KALE particle flow, although the paper is incremental and the noise injection scheme is an adaption from MMD flow, reviewers and the AC agreed that the  theoretical contribution of the paper is reasonable  but the experimental side of the paper is rather weak. Weak accept  
Decision: Accept (Poster)