Venue: NeurIPS 2022 Conference

Reviews:

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: The submission presents an infinite dimensional extension of relative measures of smoothness and strong-convexity to handle non-Euclidean notions of regularity. The theoretical guarantees cover the finite dimensional results recently obtained for Sinkhorn's algorithm in optimal transport and the Expectation Maximization algorithm for probabilistic models with latent variables.

strengths_and_weaknesses: The submission is well presented and well contextualized within the line of work on relative smoothness and its application to probabilistic models. My only major concern is the approachability of the submission to an audience familiar with the optimization literature, including the recent developments in relative smoothness and its application to probabilistic models, but unfamiliar with measure spaces. An exhaustive introduction to the mathematical background is of course out of scope, and I appreciated the references the submission already provides. But the motivation and significance of the presented work could be made clearer by a concrete example, not covered by prior work, where the presented framework applies. The links with Optimal Transport and EM are beneficial, but abstract. An instantiation of an infinite dimensional transport problem or a probabilistic model with infinite dimensional latent variables, to serve as equivalents of the toy problems of transporting an histogram or a mixture model of 2 Gaussians.

questions: (Minor points)

> 36: When using the KL divergence as Bregman divergence, mirror descent yields multiplicative updates, such as Sinkhorn’s algorithm

This statement might benefit from a qualification to the KL divergence "on discrete distributions" or measures. This is to avoid the confusion that "mirror descent + KL divergence = MWU", as is can also model divergences between parametrized measures (as the KL divergences between Gaussians with fixed identity covariance leads to Euclidean gradient descent on the parameters).

limitations: No concerns
review_title: null

final_score: rating: 9: Very Strong Accept: Technically flawless paper with groundbreaking impact on at least one area of AI/ML and excellent impact on multiple areas of AI/ML, with flawless evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper studies mirror descent on measure spaces under relative smoothness and relative convexity assumptions. This setting is a significant generalisation of the classical $\mathbb{R}^d$ setting and basic definitions such as the definition of Bregman divergence needs to be reworked (using directional derivatives). The main results are similar convergence results as in the classical setting (such as Lu et al. 2018). As application, explicit convergence rates are obtained for the Sinkhorn and the latent EM algorithms.
strengths_and_weaknesses: The paper introduces a beautiful new theory of relative smoothness and convexity of functionals acting on measure spaces. The study of mirror descent on measure spaces has been gaining interest in recent years, and this paper offers a significant contribution to the understanding of this method. It is quite remarkable that two widely used algorithm, the Sinkhorn and latent EM algorithm are actually special cases of the mirror descent algorithm, showing the generality of the results.

Extending the theory of relative smoothness and convexity to the measure space setting was not at all straightforward, and required a significant amount of work, including the change of some basic definitions.

Since both the theory and the applications of the paper are very convincing, we do not feel that there are any notable weaknesses.
questions: In Proposition 6, you define the quantity $D_c$ and explain how is it related to the relative strong convexity property of F_S.
In practice, this is only finite if the cost function c is bounded.
In Proposition 7 equation (22), it is not entirely clear whether the second bound also holds for unbounded cost functions (i.e. this was not an assumption), would you be able to state this explicitly?

It is not clear whether the sub-linear bound of O(1/n) dependence is the best we can hope for unbounded cost functions. Could the authors include an example or a reference to illustrate what happens in this case?
limitations: The authors have adequality addressed the limitations of their work.
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 is a mathematical paper on calculus of variation. The main contribution is an extension of the paper by Lu et al where in finite dimensional setting authors introduced notion of relative smoothness and relative convexity using notion of Bergman divergence and proposed corresponding Mirror Descent algorithm for which linear convergence holds. The extension to infinite dimensional space of measures is not trivial and there are a few different notions of differentiability that one may consider. Authors work with generic  Gâteaux and Fréchet derivatives which are then used to define Bergman divergence.  As an application of the theory they recover linear convergence rate for Sinkhorn algorithm in the case when the cost function c is bounded and a special setting for abstract EM algorithm. 
strengths_and_weaknesses: Strengths:
- The paper is carefully written with the theoretical parts well flesh out. 
- Adaptation of finite dimensional optimisation techniques to infinite spaces of measures allow for elegant analysis of many of the machine learning algorithms and so is of value.  
-  Connection between Sinkhorn algorithm and Mirror descent while not entirely new is interesting 

Weaknesses:
- The paper is purely mathetmical and I’m not convinced that NeurIPS is the best venue for this type of work. I believe mathematical journal on (variational) analysis would be more appropriate. 
-  There is a large body work on differential and sub differential calculus on the spaces of measures (e.g book by Ambrosio, Luigi and Gigli, Nicola and Savaré, Giuseppe) and differentiation along the gradient flow as first proposed by Otto and Otto In Villani in their seminar paper about HWI inequality e.g W_2 or/and Fisher-Rao gradient flows . I would appreciate more through discussion  and comparisons to these works. Though I suspect that the main results would remain true for these other notions (modulo technical assumptions)
questions: - In Lu et al. (Which I was not aware until now) Authors did a descent job presenting in which situations one cannot except to prove convergence of classical mirror descent but the modification using notions of relative smoothness and convexity fixed the problem.  In the current submissions a thorough discussion is missing. 
 - One popular example of optimising functions of a measure is the story of one-hidden layer neural network in mean filed regime (works of Montanari et al. Chizat and Bach, Hu et al.). Most of the works use W_2 gradient flows perspective. It would be interesting to shed some light how ideas developed by authors could help with establishing exponential convergence in that setting. 
limitations: The work is purely theoretical and hence will not have negative social 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: When working optimizing over measures, authors analyze the infinite-dimensional mirror descent algorithm and provide O(L/t) convergence rates, when the functional is $l$ strongly convex and L-smooth, relative to another functional $\phi$, where t is the iteration count and the big O contains an initial measure of dissimilarity between the optimal measure and the initial guess. This framework is applied to optimal transport, by which using it with the KL divergence (and resulting in Sinkhorn's algorithm) and convergence results are recovered. Expectation maximization is also shown to be equivalent to the mirror descent in their framework and it is shown that one particular case is convex and thus their framework applies and guarantees sublinear convergence. Part of the contribution lies in technical generalizations of the operations and analysis to the infinite-dimensional case via the use of directional derivatives as opposed to assuming a setting in which derivatives of some kind (Gateaux, Frechet...) exist.
strengths_and_weaknesses: I am not an expert in the topic of measure spaces and infinite dimensional analysis of mirror descent algorithms or other algorithms. For this reason, my evaluation of this work is somewhat limited.

Strengths: 

+ Good discussion of related work, when justifying where some ideas come from in the analysis or when some theorems' proofs are inspired by others. Still, I would have liked to see a couple of comments regarding related work, see the questions section.

+ The convergence rates for Richardson-Lucy deconvolution.

+ General framework of mirror descent with its convergence rates (Theorem 3)

Weaknesses:

+ See the questions section.


Minor:

L119 As a direct consequence of Lemma 11 in *the* Appendix
L184 "which proof" -> "whose proof"

questions: I would have liked to see more discussion on the motivation of the problem, in comparison to what has been studied. The results applying to Sinkhorn for optimal transport were already known, am I right? It is nice that the framework allows to recover this, but I want to understand whether there was some generalization made with respect to assumptions or any other thing in this problem.

Also, was there any previous analysis for Richardson-Lucy deconvolution yielding convergence rates?

Regarding the motivating problem mentioned in the introduction, in which the functional is identified to an MMD, and regarding the implications of the results of this work to this setting, the relative smoothness 4 c_k in line 587 seems to be a very large quantity. Can you quantify / are there quantifications of this value for the application mentioned regading the infinite-width one hidden layer neural network?


limitations: yes
review_title: null

Meta-review: metareview: All reviewers recommend the paper. The authors should think about ways to make the paper more accessible to a machine learning audience, but I recommend accepting. When preparing the camera-ready version, please take into account the reviewers comments and please also specifically address these two points raised in the discussion:

"I'm of the opinion that authors should try put more effort in making current submission more accessible to general audience helping the reader to understand why certain notions of differentiability have been chosen over others etc."

"Providing a concrete example where relative smoothness fails but the proposed approach applies would increase the potential audience among non-experts."
confidence: Certain
Decision: Accept