Mirror Descent with Relative Smoothness in Measure Spaces, with application to Sinkhorn and EM
Authors: Pierre-Cyril Aubin-Frankowski
Anna Korba
Flavien Léger
Venue: NeurIPS 2022 Accept (2022)
Keywords: optimization
mirror descent
measure spaces
sinkhorn's algorithm
expectation-maximization

Abstract: Many problems in machine learning can be formulated as optimizing a convex functional over a vector space of measures. This paper studies the convergence of the mirror descent algorithm in this infinite-dimensional setting. Defining Bregman divergences through directional derivatives, we derive the convergence of the scheme for relatively smooth and convex pairs of functionals. Such assumptions allow to handle non-smooth functionals such as the Kullback--Leibler (KL) divergence. Applying our result to joint distributions and KL, we show that Sinkhorn's primal iterations for entropic optimal transport in the continuous setting correspond to a mirror descent, and we obtain a new proof of its (sub)linear convergence. We also show that Expectation Maximization (EM) can always formally be written as a mirror descent. When optimizing only on the latent distribution while fixing the mixtures parameters -- which corresponds to the Richardson--Lucy deconvolution scheme in signal processing -- we derive sublinear rates of convergence.

Mirror Descent with Relative Smoothness in Measure Spaces, with application to Sinkhorn and EM
Pierre-Cyril Aubin-Frankowski DI ENS, Ecole normale supérieure, Université PSL, CNRS, INRIA Paris ceerre-cyril.ubbi. airaa.fr fr
Anna Korba CREST, ENSAB IP Paris anna. ktma.korbaBensae. fr
Flavien Léger INRIA Paris
Flavien.
Abstract
Many problems in machine learning can be formulated optimizing a convex functional over a vector space of measures. This paper studies the convergence of setting. Defining Breg-
the mirror descent algorithm in this man divergences through directional derivatives, we derive the convergence of the scheme for relatively smooth and convex pairs of functionals. Such assumptions allow to handle non-smooth functionals such as the Kullback-Leiller (KI.) diver- gence. Applying result to joint distributions and KL, we show that Sinkhorn's ss primal iterations for entropic optimal transport the continuous setting correspond to a mirror descent, and we obtain new proof of its (sub)linear convergence. We also show that Expectation Maximization (EM) can always formally be written as mirror descent. When optimizing only on the latent distribution while fixing the mixtures parameters which corresponds to the Richardson Lucy deconvolution scheme in signal processing derive sublinear rates of convergence.
Introduction
Many important problems in machine learning and computational statistics can be cast as optimiza- tion problem over the space probability distributions, where the objective functional assesses the dissimilarity target distribution j on Rd. Classical dissimilarities include f-divergences, Integral Probability Metrics (IPMs), or optimal transport distances among others. In Bayesian inference for instance, it is common to optimize the Kullback-Leible (KL) divergence to the target, which corresponds to the posterior distribution of the parameters of interest. In generative modelling, the goal is to generate data whose distribution is similar to the training set distribution defined by samples of the target, where the similarity is often measured by an integral probability metric or an optimal transport distance (Arjovsky et al., 2017) Dziugaite et al. 2015). In supervised learning, optimizing an infinite-widhh one hidden layer neural network, e.g. through the mean squared error, corresponds minimizing functional on the space of probability distributions
the parameters of the network (Chizat and Bach, 2018 Mei et al., 22018) Rotskoff and Vanden- Eijjde- (218)). In particular, the objective functional can be identified a Maximum Mean Diserepancy (MMD) in the well-specified setting AAbel et al.) (2019). Many other problems in machine learning can be formalized in this framework (Chu al. (019)).
Once the objective functional chosen, one has to select an optimization algorithm that is well- suited to the geometry of the problem. In this article, we consider the widely used mirror descent scheme, a first-order optimization method based on Bregman divergences. While the traditional
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

smoothness and strong convexity assumptions, required by standard convergence analysis, do not always hold over measure spaces, their "relative" versions have received increased interest. The relative smoothness assumption was first suggested by [Birbbaum et al. (2011) in the context of algorithmic game theory, but remained unnoticed by the optimization community, until [aascckee et al. (2017) discovered the same concept independently. while [L et al. (2018) coupled it with relative strong convexity. We extend their work to the infinite dimensional setting and target specifically the KL divergence. Indeed, when using the entropy as Bregman divergence, mirror descent is known to yield multiplicative updates for the measures. In this paper we study two such schemes in machine learning, i.e. Sinkhorn's 's algorithm, widely used to solve entropic optimal transport (Peyré and Cuturi 2019), and the EM algorithm, a very common approach to fitting probabilistic models.
Related work. Chizat ) gave convergence rates of mirror descent on measure spaces for integral functionals with Lipschitz gradients, working mostly in the 7.- space and without leveraging relative smoothness. However his assumptions do not cover f f-divergences, such as the ubiquitous KT. nor entropic regularized transport as in Léger (220). His setting also implies Gâteaux differentiability, which is classical for mirror descent in Banach spaces (Bauschke et al. 2003). As the entropy is not differentiable in infinite dimensions, directional derivatives were instead used by Resmerita (2005) for mirror descent, and applied by Chu et al. (2019) to gradient descent. Connections between mirror descent and Sinkhorn iterations for the entropic optimal transport problem were first investigated in Mishchenko (2019); Mensch and Peyré (2020); Léger (020). Our framework is closest to Léger (2020), which we simplify by considering primal rather than dual iterations, and extend by also deriving linear convergence rate. Kunstner et al. (2021) recently showed that EM over parametric exponential mixtures corresponds to a mirror descent scheme with relative smoothness properties. Their setting is complementary to ours since consider instead fixed mixtures and nonparametric latent distribution. A prominent alternative setting to ours when optimizing over measures is based on (grid-free) Wasserstein gradient flows, which we do not cover here (see Appendix E for discussion on the difference of geometries). A remarkable discussion on the optimization over measures with different geometries can be found in Trillos and Sanz-Alonso (2020)
Contributions. We propose a rigourous framework for the analysis of the dimnnie-dimensional version of mirror descent over measure spaces. In this setting, recover the rate of convergence of mirror descent under relative smoothness and convexity, previously shown in finite dimensions. Defining Bregman divergences through directional derivatives, we able to consider objective functionals over measures that are not smooth in the "standard" sense, but satisfy relative smoothness and/or convexity with respect to a Bregman divergence, e.g. KL. Focusing optimization over joint distributions, we show that both Sinkhorn's primal iterations for entropic optimal transport in the continuous setting and EM can be written as a mirror descent. We then obtain new proof of Sinkhorn's 's (sub)linear convergence. For EM, when optimizing on the latent distribution while fixing the mixtures, a choice which coincides with Richardson- Lucy deconvolution, we derive new sublinear rates of convergence.
This paper is organized follows. Section 2 introduces the necessary background on derivatives in measure spaces and relative smoothness and convexity. Section discusses the poll-posessess of the mirror descent scheme and provides our proof of convergence adapted from Lu al. (018)) Section
| recovers the convergence of algorithms such as Sinkhorn's 's iterations and latent EM as special cases of mirror descent with relative smoothness and convexity.
Background and definitions
In this section, we set the mathematical framework in which we will rigourously reformulate relative smoothness and convexity on a space of measures.
Given a topologiaal vector space y with topology т, the domain dom(f) f) of an extended- valued function f y + I U { is the set of points of ) where f takes finite values. The function f is said to be proper if dom(f) is non-empty and if f never takes the value - 0o. It is -llwwer semicontinuous (l.s.c.) if its sublevel sets are 7-closed. We consider dual pair () ) with duality product ((,))==x> which induces a )""-wak topology on y (see Aliprantis and Border 2006). We write Int. C for the interior of set C y. Let X C Rdd, and fix locally convex topological vector space of measures (M(X), 7). which could for instance (dp). T.2(dp) where p is reference measure, or the space of Radon measures M, (2') with the total variation (TV) norm.
Notation.

---

Fix (X') a topologiaal dual of M( For f E M(X) and f (2),,, we use the shorthand (f.p) (f.)) (1)))) formally equal to fx f(z)p(dr). We denote by P(X) the subset of
measures j E M(X) with mass and. for any u.v M(X), we write p & v when μ is absolutely continuous w.r.t v, i.. when it has a RNdoonN derivative du/dv.
Consider convex functional F M(X) R U (+oo} and the following minimization problem
min F(v) rEC
(I)
where C' c M( is a convex set. To solve this convex optimization problem, a classical choice is to resort to mirror descent scheme (see e.g. [Beck and Teboulle, (203). The latter is first-order optimization scheme based on the knowledge of the "derivative" of the objective functional F at each iteration. The difficulty is to choose the appropriate notion of derivative. Indeed. Gâteaux and Fréchet derivatives have to be defined in every direction (see Appendix (A). thus requiring that the points of differentiabilityy belong to the interior of the domain Int (F) of the functional F considered. In infinite dimensions, for functionals defined on positive measures, such as the negative entropy, Int (dom is however empty] Consequently, following Resmerita (2005), we favor weaker notion, that of directional derivatives Saattvees@hiii This comes at the price of manipulating too values but ensures that the considered derivatives are always well-defined for convex functionals. Besides, whenever the directional derivative is a linear function in a restricted set of directions, the notion of first variation that comes next will enable us perform all the computations we need, as if the function was Gâteaux differentiable.
+ Definition (Directional derivative). If it exists, the directional derivative of F M(x)
RU = at a point dom(F) in the direction μ E M(X) is defined
Flu + hp) F(v)
d d+F(()(u) lim 1-00+
(2)
h
Remark 1. In particular, for convex and proper functions, d' (+) exists and belongs to R U { (Aliprantis and Border 2006 Lemma 7.14). This direct consequence of the nondecreasingness of R 3 h + -(otha)-Fww) for any V: fa and convex F. The monotonicity also entails that (u) S ())+ - F(() < oc whenever v and v + l belong to dFm(F) and that dt is linear operation over the cone of convex functions. Note that μ + d d+)(( is not always r-L.s.. although it is always positively homogeneous, and, whenever F is convex, it is convex.
h
Definition 2 (First variation). Let F M(X) + RUR u be a functional and C be a subset of M(X). If it exists, the first variation of FF over C evaluated at μ E dom(FF) n C' is the element (CF(H) E (X)), unique up to orthogonal components to span(dom(F) nc p), such that:
(VcF((n) = d F())(E))
for all =- E M(X), where vs E do.(F)
By Remark 1 we have that (+) E (-0,, oo), since l E dom(F) n C. Naturally, if F has a Fréchet or Gâteaux derivative at jr, which implies that μ E Int (nt(d)((F)) then it coincides with the first variation at μ. Calling first variations the derivatives of functionals stems from the field of calculus of variations; a pragmatic approach when dealing with probability measures can be found in Santambrogio 2015 Definition 7.1 where Vp(x) F(a) is defined measurable function, we instead take it most in often in (XX). We now introduce Bregman divergences over measures through directional derivatives.
Definition (Bregman divergence) Let o : MMX) - dom (6), the Ø-Bregman divergence is defined for all v E dom(@) by
[+oo] be a convex functional. For
Dœ((lm)) = Φ(v) (1)) - d (())(()) n)) E [0, too],
and +o0 elsewhere. The function @ is referred to as the Bregman potential.
'Intiitively if X contains an open set, then any positive measure can be infinitesimally perturbed to have negative values. For finite sets X' this phenomenon does not occur, see also Example
FIn finite dimensions, Maddison et al. (202)) also defined Bregman divergences through directional deriva- tives, but under the stringent assumption of essentially smooth convex functions, an assumption which does not extend well to infinite dimensions.
3

---

In the previous definition, the restriction to dom 6) is necessary to avoid the substraction of infinite values. As a direct consequence of Lemma 12 in Appendix, a stricly convex @ entails that the 0 if and only if v = μ. Note that (1p)) is difference of convex functions, so is not convex in general. Nevertheless the existence of a first variation (3) of Φ over C, resulting in the last term in 4 being linear, is sufficient to ensure the convexity of the restriction D (4) to C. Bregman divergences have useful immediate properties: since dt is linear operation over convex functions, so is the Bregman divergence, i.e. for two convex Ø, v), Da+0 DD + De. Moreover, it is idempotent, as shown the following lemma.
Bregman divergence D& separates measures, i.e. (=(
Lemma 1 (Idempotence of Bregman divergence). Let ó M( + R U {+00} be convex functional. Assume that given & E dom( the first variation VoO(E) exists, then, for all μe, E C dom( DDa(-ee)(/ppp (v(p) = (v(p))
Proof. Since vb f -d (E) 5) = -VVo((() g) convex over do) we can apply the linearity of the Bregman divergence:
(v)( = (v(vl)) + D- (e)(())))))))))))))))))) + (vlp) Do(v)m).
since the Bregman divergence of constant of linear form is null.
We are now ready to introduce the notions of relative smoothness (Bauschke et al. 2017) and convexity (Lu al. 2018) of functional w.r.t a Bregman potential.
Definition 4. (Relative smoothness and convexity) Let F MM()) + U { be convex
proper functional. Given a scalar 2 O, we say that is L-smooth relative to & over if, for any Jr, dom(F) n (Ø) n C, we have
Dy(v))) = F(v) F(u) (')))d(((((( - A) s LD&(vln)
(5)
Conversely, we say that is I-strongly convex relative to & over C, for some scalar / 0, if, for any Jr, dFm(F) n (Ø) n C, we have
Dz(1)p) (D(()))).
(6)
Example (L-smoothness)) Choosing Φ(μ) = || the square norm on M(X) shows that
relative smoothness extends the notion of L-smooth functionals (see for instance Chizat 2021 Lemma 3.1)), i.e. functionals with L-Lipschitz Gâteaux derivative, thus satisfying:
F(v) - F(p) - dt F(n)(v - p)) - 111-211- p1l².
(7)
Notice that by Lemma | provided Vcc(E) is well-defined, Bregman divergence objective ( is always 1-relatively smooth and strongly convex w.r.t. Φ. This we will heavily exploit for mirror descent schemes that involve the KL divergence both as objective and Bregman divergence in Section 4 Interestingly, relative smoothness and convexity can be characterized different, equivalent ways, see Lemma 13 in the Appendix. We now turn to the analysis of the mirror descent scheme using the above framework.
Mirror descent over measures and convergence
In the following, é is assumed to be strictly convex. The relative smoothness assumption (5) of the convex objective functional F w.r.t. a Bregman potential Φ suggests to minimize iteratively over C. the function + F(p) d+ μ4) + LDD(elu), acting as an upper approximation of F(v). Starting from a given E M(2),, the mirror descent iterates are thus defined at each time as
Mn+1 = argminnddd ( (..) + LDD(plPm))
wEC
Let R. C C' be a given subset. As proven later in this section, sufficient conditions for the convergence of the scheme (8) are:
(A1) (Existence) The sequence of iterates (Nn)ner defined by (8) exist, belong to R, and are unique.
(A2) (Relative smoothnes/convvexitt)) For some 1, T. 2 0, the functional F is T-smooth and I-strongly convex relative to é in Definition 4 for elements of R.

---

(Ag) (Existence of first variation of () For each n 2 0, the first variation VoΦ(Hn) exists.
These assumptions have to be verified on a case-by case-by-case basis. In the simplest case, one can take R = C. However the set R does not have to be convex (see Section 4 On the other hand, Assumption ( (A',) below, ensures that the iterates in ( are well-defined, uniqueness resulting from the strict convexity of
1A' (Lower semicontinuity and coercivity) (i) the set C' is r-closed in M(X), the functionals (.(.)) := (())))))F(((((----->>>)))>())))) (n)) and D-(-(1n)) are proper and r-I.s.c. when restricted to C, and the functional 9, Do(-(um)) + ic 3 has least one r-compact sublevel set. (ii) For each n 2 the first variations VcO(pn) exist. (ii) The iterates belong to R.
By Attouch et al. 2014 Theorem 3.2.2), Assumption (A')) implies (A Indeed, (i) r-lower
semicontinuity and 7-compactmess guarantee the existence of minimizers of the objective (8). while (ii) the existence of Vco((u, guarantees that Da(+1 is strictly convex (since ø is assumed strictly convex) hence unicity of the minimizer. Regarding Assumption (A),) notice that Gn is proper and .M" (2"(----weaa--...c as soon as F has a first variation at jun, since this case G, is linear on C. We refer Appendix B for more details on proving that Assumption (A') holds for some F, ó and C.
(A')
Mirror descent can also be defined through a subdifferential constraint if F also has first variations.
Lemma (Mirror descent dual iteration). If VcF())) and Veo(un) exist for n 2 0, then 8 is equivalent to
Voo(um) - 1 VoF(m)) E (o0(unt1) := {pl Vv E C, (p, v- Hn+1) S (ot(()+))))))) 1 1n+1)}
(9)
Thus, if (oo((n-1) (Vod(un+1)) corresponds to VoΦ(Un+1) ( -
- (.(m))
Proof. The minimization B is equivalent to having, for all E C.
d+F((m)(v - mn) (D (tF(())))nntt - (nn) + LD (H(+all)) (VoF(),,) L LV Mn+1) + L(ő(v) ((pu+1)) 0.
Take & E C, set Mat1 + (1 for E [o, 1]. Taking the limit t + 0+ yields the result.
In the general case, as discussed in finite dimensions in Bauschke et al. (2017 Remark 3), one needs extra assumptions to justify that fa++1 exists in (9) akin to the invertibility of V or that ø is essentially smooth of Legendre type. To avoid any restrictive assumption required to use (
stick with the minimal formulation (8) as was also done by Bauschke et al. (2017); Lu et al. (2018).
We now state a preliminary result, known the "three-point inequality" or "Bregman proximal inequality" in the optimization literature (Chen and Teboulle 1993) Lemma 3.2), (Lan et al. 2011 Lemma 1), useful to prove the convergence of the mirror descent scheme, similarly to|Lu et al. (2018).
Lemma 3 (Three-point inequality). Given μ E MMX)) and some proper convex functional G M(X) - R U [+ if (C)(p) exists, as well as argmin (g(v) + (v(un) then for all
E C' n dom()) n dGm
G(v) + (o(P))) ( + D2(() Do(p)D).
(10)
Proof. The existence of Voδ(H) entails that C n dom (Do((11)) = C' n dom(d). Set f(-) G()) + Do(-Iu). Then, by linearity of the Bregman divergence and Lemma we obtain that, for any v E C C'n dom( n dom(g).
=
Dy(plD) = Do(u|p) + (D.((i)(UDD) = Do(u|D) + Do(ulD) 2 Do(vlD).
(11)
By optimality of for all C, dt (f)(z)(v - lim -ot (f((1 h)p + hv) - f()) 0:
which is equivalent to f(v) 2 f(7) (z(z))) We conclude using (TT) and the definition of f. r
c denotes the indicator function of the set C. defined by ic(μ) if E C. +oo otherwise for any E M(X). Notice that ic being 7-L.s.c. is equivalent C being closoedd in M(()).
5

---

The following theorem gives the rate of convergence of mirror descent for relatively smooth and convex pairs of functionals, and extends to infinite dimensions the convergence result of Lu al.) (2018) Theorem 3.1). Its proof can be found in Appendix F.T
Theorem (Convergence rate). Assume that Assumptions (A (A2) and (As)
hold. Consider the
mirror descent scheme (8, then for all 2 0 and all domi dodmml) R. we have
(D (O)
L
F(mm) - F(v)
S Do(vlpo),
(12)
(1 (1+ (
n
where, in the case 1 = 0, the middle expression is defined in the limit as - 0+.
Remark 2 (About the proof of convergence). Our proof resembles the one of Lu et al. (2018), which also relies three-point inequality as stated in Lemma However, the proot of the latter inequality in finite dimensions relies on a sum of subdifferentials formula, which is hard to verify for general functionals and in particular for the KL divergeence defined below (see also Remark 6 in Appendix). On the contrary, by working with directional derivatives and first variations, we circumvent most of the difficulties related (sub)ciiferrentiabilty.
An important example is the one discussed below where Φ is chosen to be the negative entropy de. Example 2 (The KL divergence and negative entropy). The Kullback-Leible (KL) divergence and the negative entropy are defined for μ < f and μ < p, writing pax) dz)dp(z), respectively as
(L(ulp) = J In (du/ap(z)) du(x), sc(u)
1/. (n(p(=)))(()dpp()) = KL(Upp)
(13)
where p some reference finite measure on X. is straightforward to show that KL can be written as a Bregman divergence of the if F < ji & p. i.e. D&_ (u) KT((ul);; hence one can choose = Φe for the mirror descent scheme (8). Assumption (A')) guaranteeing that the iterates (8) are well-posed, is satisfied for instance when M(X) = I, (2)) and if there exists Ko, 11 > 0 such that Ni I dum/4a(()) S K₁ almost everywhere over X' for any n, which is the case for Sinkhorn's 's and EM iterates. This implies that the first variations of the negative entropy or KL belong to - at Na, see also Remark 5 in Appendix for more details. Moreover, by Lemma 2 exponentiating the
dual iteration ( recovers the classical multiplicative scheme: un++1 = ene FFF(),) n 2 0. This observation generalizes the Iterative Proportional Fitting Procedure, also known as Sinkhorn's algorithm.
KT. is a strong Bregman divergence, in the sense that dominates wide range of objective functionals F. Indeed, we already know from Section 2 and the idempotence property that F = KT.(- is l-relatively smooth w.r.t. de, since for any v E dom(F), (v(v(pp) = Do (vln) = (L(p)p). In Section
4 we will extensively use this fact (sometimes applying KL to joint distributions rather than marginals, e.g. for Sinkhorn's 's algorithm). This is of crucial importance because J KL is not smooth objective in the "standard" sense (see Example I hence convergence proofs requiring the latter cannot apply -. but it is relatively smooth w.r.t. itself. Indeed the KL diverges for Dirac masses, so is unbounded over the bounded set P(X'), and thus KL does not have subquadratic growth 77) w.r.t. any norm on measures. Other objective functionals can be dominated by KL, such as the Maximum Mean Discrepancy (MMD) for bounded kernels, see Proposition 14 in Appendix [
4 Applications to Sinkhorn and EM with convergence rates
We now analyze the convergence of two algorithms, Sinkhorn and Expectation Maxitiizaanaiiiiiiiiiinn (EM), by showing that they can be written as mirror descent schemes based on the KL divergence, in order to apply the results of Section Note that the relative smoothness was first introduced by BBrnbbum et al. (201T) for this very purpose, to study the convergence of Proportional Response Dynamics.
In both the Sinkhorn and EM settings we will be given two probability spaces (X' and (), D). We recall that P(X'' x )) denotes the subset of Radon measures M, x 3²) with mass 1. We equip M, with L (X' x ))) as dual space. A joint measure म E P(X x )/) is also called a coupling between its first 7x and second py marginals. We denote by [[ *) the set of couplings having first marginal ji and (*( D) the set of couplings having second marginal V. and IT D) = M(z, *) n IT(,, 2) the couplings with marginals (ū, D). We now recall an instrumental disintegration formula:

---

Let vT, n, 7 E P(X (('XX x )) with π & n, (x dy) x(de.dw)/pxxtdd)) We have ग = px @ K and
KL(*)T) (L(xxTpxx) (L(K,|Ka))) dpx
(14)
This decomposition is at the heart of the two objective functions Fs and FEM considered below.
4.1 Sinkhorn
To describe the entropic optimal transport problem we follow Nutz (021). Consider cost function
E _ (X' xy. ji B) and a regularization parameter > 0. The entropic optimal transport problem the minimization problem
(T, D) min (/ =Ell(a.))
(15)
By adding a constant to we can assume without loss of generality that e- 7. 1 has mass 1. Since e bounded, (13) admits unique solution n, We use characterization (Nutz, 202T, Theorem 4.2, Lemma 4.9, Section 6) of the set of cyclically invariant couplings, and define it follows, as the set of couplings π that solve an entropic optimal transport problem for their own marginals,
II. = { E P(X x )) (T ()
min #ell(p)))
(/ (1,, v) = (xxx,PyT)
(16)
Moreover when E II. there exist f T (x) and g E ()) such that π = e $
The Sinkhorn algorithm in its primal formulation solves (15) by alternating (entropic) projections on 11(p,*) +) and II(*, Ø) (Ruschendorf) 1995). i.c. initializing with To E II iterate
#n 1 argmin (T.(r(=.).
(17)
=ell(a)))
To+11 argmin (L(TTT+3) xEII(+.P)
(18)
Let pn px More explicitly, 177 is "rescaling of the rows". Tn+3 (dr, dy)
Tn (dx, (()x)(d))/pp))) pp while (18) is a "rescaling of the columns", Ta+1 (dr, dy) Tn+z (dx, (dy)(dd)) (ddg)/PPs / (dy). This can be seen
consequence of (14). as in (77) the first
marginal is fixed, the optimum of (I7) is such that the integral term of (14) vanishes. One can also
show recursively that nn E IT, (see Nutz 2021
Section 6, Lemma 6.22).
Define the constraint set C = [T(+, D), R C CT, and the objective function
FS(T) = (L(pxxlp).
(19)
Connections between mirror descent and Sinkhorn iterations for the entropic regularized optimal transport problem were first discovered in Mishhhenko (2019); Mensch and Peyré (2020): Léger
(2020). We propose yet another mirror descent interpretation of Sinkhorn in the spirit of Léger (2020), and use the primal formulation (17)(18) directly instead of introducing dual potentials. This is stated in the following Proposition, whose complete proof can be found in Appendix F2
Proposition 5 (Sinkhorn as mirror descent). The Sinkhorn iterations (17) can be written as a mirror
descent with objective Fs and Bregman divergence KI. over the constraint C = II((<>>) V))
Ta+1 argmin(( REC
(Vanin((eele (V.Ps(TT); - -n) KL(x(Tm) with Vc/F((T.) = In(dpn/ddp E (X x ))-
Sketch of proof. Let pn = Tn where n, is defined in 17 We have the identity:
Fs(TT) + (VCFs(TT)) Tn) + KL(T)T,) (L(p mw/un)) KL(T||T+3)
We conclude by taking the argmin over π E C.
We first show relative smoothness of F' relatively de. consequence of the standard KL data processing inequality, i.c. KL the marginals is smaller than KL of the plans.
'The last equality uses: KL K+) In ( P dpxx Kr Sx KL(K<(Kr) dpxm.
7

---

Lemma 6. The functional Fs is convex and is 1-relatively smooth w.r.t. oe over P(X x )).
Proof. Let ग., ã E P(X' x )) with pa < Px & p. Then with straightforward computations,
(+)) (L(px 2 0, so Fs is convex. Then (4 results Dr, ( I (a O
By considering singular first marginals, it is obvious that there exists no ( such that DF, (+ > I (K((F(T) for all H, т E C; i.c that relative strong convexity of Es relatively to Oe does not hold over all C. However, we show in the next Proposition that this inequality actually holds over R nc
Its complete proof can be found in Appendix F33
Proposition 7. Let De =
suPmaaa' by [c(2, v) + cla',1/ - c(2, - c(x', .1) <0. Fora,
II, n C, we have that
(T((*)) & (1 4e 3D ((xpxT)))))
(20)
in other words Fs is (1 + 3D. - strongly convex w.r.t. KT. over IT. NC..
Sketch of proof. For म E II, n C with their potentials and marginals (f,g. D) and (.D.
respectively, setting |I = (supx f) (infxx f), we can derive the bound
< S II /llvarll/ pl|TV + <TT()))
(21)
We can then bound the potentials by the marginals using Proposition 15 in Appendix:
||
Allvr - var S 2e 3D. @DD./((Il TV + ||0 =|[Tv).
(22)
Then, chaining
21
and
22 conclude using Pinsker's inequality.
We now ready to recover convergence rates for Sinkhorn leveraging relative smoothness and strong convexity.
Proposition (Sinkhorn convergence). For all n 2 0, the Sinkhorn iterates verify, for n, the optimum of (15) and μt, its first marginal,
KL TT (To)
KL(T..TO
KL(umlua)) S
(23)
(1 + 4e 2
(( + 4E
-1)
Proof. Fix n 2 0, we know that Tn, T, E R= C C IIc We conclude by applying Theorem to F = Fs and Ø m...)).). leveraging the results of Lemma and Proposition
The linear convergence of Sinkhorn for bounded costs has been known since at least Franklin and Lorenz (1899 and has then been derived also in the non-discrete case and multimarginal settings (see Carlier 2022 and references therein). To derive this linear rate (the first inequality in (33 ). we require relative strong convexity of the objective hence we also fundamentally rely on the boundedness of the cost, as can from the assumptions of Proposition 7 Indeed the proof of Proposition 7 relies on the classical result that the soft c-transforms are contractions in the Hilbert metric; result also at the heart of other proofs for the linear rate (see Franklin and Lorenz 1989; Chen et al. 2016 for proof). Regarding the sublinear convergence (the second inequality in (23). Léger 2020) first obtained sublinear rates for unbounded costs leveraging relative smoothness, using (9) formally and through dual iterations on the potentials. In this Section we assumed L (X' )), in order manipulate finite quantities in our computations (e.g. first variations in the proof of Proposition 5 hence the latter can be seen as convenient working hypothesis. In this paper we derive the same rate as Léger (2020) rigorously with a more direct proof using primal iterations, and complete the picture by recovering linear rates of convergence.
4.2
Expectation-Maximizatte
In this subsection, we show how the EM algorithm can always formally be written as a mirror descent scheme, and, when optimizing the latent variable distribution, results in convex problem with sublinear convergence rates. Consider the following probabilistic model: we have a latent, hidden random variable X e (X, (z), observed variable Y e y distributed as P, and we posit joint
8

---

distribution Py (dz, dy) parametrized by an element of some given set Q. As presented in Neal and Hinton (1998). the goal infer q by solving
min (T.(Flypp.)
(24)
qEQ
where (dy upperbounding KL(P)pyp,). For any E II(,, D). by the data processing inequality, KI PyPp) - (T(T)))) =: ()
= Py dy). The EM approach starts by minimizing surrogate function of
Again, as a consequence of the disintegration formula 14 there is equality if and only if
π dy) Py dy) (dy)/ (yPy
(25)
EM then proceeds by alternate minimizations of [(T.g) g) (see Neal and Hinton 1998 Theorem 1):
4n argmin (Tn
(26)
vEQ
1n+11 argmin (L
(27)
=EIT(..0)
The above formulation consists in (26). optimizing the parameters 4n at step n (M-step), and then
(27). optimizing the joint distribution +1+ step 1 (E-step). We choose this order to highlight
the analogy of (27) with Sinkhorn's (18). The minimization (27) corresponds to taking an explicit
expectation, according (25) justifying the denomination. On the contrary making explicit the
M-step is often difficult.
Define the constraint set C' II[(,, i) and the, possibly non-convex, objective function
(TM inf (I(p))
(28)
We first show that EM can be formally written as mirror descent scheme in the following Proposition, whose precise statement with additional assumptions can be found in Appendix F.4
Proposition 9 (EM as mirror descent, formal). The EM iterations (26) 27 can be written
mirror descent iteration with objective function FEM, Bregman potential Φe and constraints C,
Tn+1 argmin (V π nx) KL(x|T,) with FEM (T,) inddw,/dpp xEC
(29)
Sketch of proof. Let nn be the current EM iterate. Formally, we use the envelope theorem to differ- entiate FEM and find that Fc ) = In (ndd,,/ /dp..) (see Appendix [.4 a justification based on directional derivatives and Milgrom and Segal (2002) Theorem 3)). Then for any coupling æ, we have the identity
FEM (TT) + (VoFEM(TT)) x -ma) (TT(TT (L(TIPQ..)
Thus 29 matches
Since FEM is in general non-convex, we cannot apply outright the framework developed in Section t There however one direct case of Pg making FEM convex, by optimizing only over its first marginal.
Latent EM. We consider the case where p, dy) = p(dx) (x, dy), i.e. Pa is of the form p & K, with Q P(X') and K kept fixed along iterations. In other words, we choose only optimize over the density of the latent variable, and keep the mixture parameters fixed. Here K can be interpreted as the conditional distribution of Y given X, K(x, dy) P(Y = y X x). We consider in the following Gibbs distributions with K (az, dy) e c(z.))) (dy) with e uniformly bounded. The term c can be interpreted as a cost similarly to the entropic optimal transport (15).
Remark (Various EM). The general goal of EM is fit, through the objective function FEM. parametric distribution, e.g. a mixture of Gaussians, to some observed data Y. One needs to estimate both the latent variable distribution on X (i.e. weights of each Gaussian) and the parameters of conditionals P x²) (e.g. means and covariances of each Gaussian). Latent EM focuses on learning the mixture weights, since consists in optimizing over the nonparametric latent distribution (1. which can be continuous or discrete. In contrast, the parametric setting considered by Kunstner al. (202T), who obtained (1 /n) rates of convergence in KI. for EM, can be seen as complementary to ours since they consider fixed μ and variable exponential mixture Kg. with q 0.

---

Parametrizing by the first marginal, EM iterations
26
27
takes the following form for Latent EM:
argmin KL 1 @ K);
(30)
MEP(X)
An+1 argmin (L @ K).
(31)
=)ll(,,))
First, we necessarily have from (30) that (4n = px Indeed, from the disintegration formula (14). (30) corresponds to minimizing over first marginals. Then, since the E-step (31) corresponds to
computing 25
we can rewrite (30--31
(31)
as:
K(., ddy Mn+1() / Tn+i (,++(,ddy) dy) dy) px()) J Jx K(x (n))
(32)
Define (T) == inf (x)( KL(T @ K). Notice that by disintegration (4). FLEM takes the form FLEM(TT) (T) pxxx & K). To take care of the initialization, we define the operator Tx- E P(2) + Ix ((dr) (x,-) E M)))),, with K K(x, dy) = k(z, () and take = e with fo E - and assume that TRū D (in other words we assume that the mixture applied the latent space is compatible with all the observations).
Proposition 10 (Latent EM as mirror descent). The latent EM iterations 30 mirror descent with objective FIEM. Bregman potential Φe and the constraints [I(+,
can be written as
dnn d(un & K) E Lo.
T.) Th+1 argminn(Ver FieM (T,)) -- ) +KL(T(Tx) with VC(LLE((TT) = In
NEC
Proof. Similarly to Proposition we have the identity
nn) + (L((T),,)) KL(xpxxT K); (T, + (LT))
where VcFiaM In an(T,// T, @ K) (x, see Appendix F.5 for rigorous justifications. Since (An = mx due to 30). we conclude by minimizing over æ E C.
We now ready to state convergence rates of latent EM in the following proposition. The reader may refer to Appendix F.6 for a complete proof.
Proposition 11 (Convergence rate for Latent EM). Set μ. argmin,eP(.r functional FLEM is convex and 1-smooth relative to de Moreover for To D),
The
(L(P(T<pm) s (L(F[TKu.)+ KL(,,}μo) (L(T)T - KL(FTTxPo)
n
Sketch of proof. By the disintegration formula (1]) we can decompose FLEM as
FLEM TT = (L(Plpy(Px @ K)) + KL(T/D|(xxT @ ( K)/ 8 K))do,
(33)
and show then straightforwardly that m. defined by n. (dr, dy) = n. (dx) (()))(( dy) (T... (dy) is a minimizer of Fi.M with FieM("*) (L Then, by the disintegration formula (14) and
linearity of the Bregman divergence, (T π) Drg ( (m/=)+ + Dris (m|²), hence FLAM -rrelatively
smooth w.r.t. oe Consequently, Theorem yields:
FLEM(TT) FLEM(T.) KL(xx (TO) n Finally: KL (LTT))))) bp & K)) (L K) FLEM(TT).
Remark (Richardson-Lucy). Interestingly, the iterations 32 of latent EM correspond precisely to that of Richardson-Lucy deconvolution (Richardson, 1972; Lucy 1974) where is a known convolution and one aims at recovering the original signal μr, based the observations D. Thus our proof yields rates convergence for this other algorithm from signal processing, a novel result to the best of our knowledge.
We have provided a rigorous proof of convergence of mirror descent under relative smoothness and convexity, which holds in the measure spaces. The latter condition can handle objective functionals that are not smooth in standard sense, such as the ubiquitous KI. It enabled us to provide new and simple way to derive rates of convergence for Sinkhorn's 's algorithm. We also derived new convergence rates for EM when restricted to the latent distribution, obtaining complementary rates to Kunstner et al. (202))
Conclusion:
setting of optimization over
10

---

References
Aliprantis, C. and Border, K. C. (2006). Infinite dimensional analysis a hitchhiker's guide. Springer, Berlin New York.
Ambrosio, L., Gigli, N., and Savaré, G. (2008). Grudient flows: in metric spaces and in the space of probability measures. Springer Science Business Media.
Arbel, M., Korba, A., Salim, A., and Gretton, A. (2019). Maximum mean discrepancy gradient flow. In Advances in Neural Information Processing Systems (NeurIPS), pages 6481 6481-6491.
Arjovsky, M., Chintala, S., and Bottou, L. (2017). Wasserstein generative adversarial networks. In International conference on machine learning, pages 214-223. PMLR.
Attouch, and Brezis, H. (1986). Duality for the sum of convex functions general Banach spaces.
In Aspects of Mathematics and its Applications, volume 34, pages 125-133. Elsevier.
Attouch, H., Buttazzo, G., and Michaille, G. (2014). Variational Analysis in Sobolev and BV Spaces. Society for Industrial and Applied Mathematics.
Bauschke, H. H., Bolte, J., and Teboulle, M. (2017). descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications. Mathematics of Operations Research, 42(2):330-348.
Bauschke, H., Borwein, J. M., and Combettes, P. (2003). Bregman monotone optimization algorithms. SIAM Journal on Control and Optimization, 42(2):596-63
Beck, A. and Teboulle, M. (2003). Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Reseurch Letters, 3163)1677-175.
Birnbaum, B., Devanur, N. R., and Xiao, L. (201 Distributed algorithms via gradient descent for fisher markets. In Proceedings of the 12th ACM conference Electronic commerce EC '11.
ACM Press.
Borwein, J. and Goebel, R. (2003). Notions of relative interior in banach spaces. Journal of Mathematical Sciences, 115(4).
Braides, A. (2002). I-convergence for Beginners, volume 22. Oxford University Press.
Butnariu, D. and Resmerita, E. (2006). Bregman distances, totally convex functions, and method for solving operator equations Banach spaces. Abstract and Applied Analysis, 2006:1-39.
Carlier, G. (2022). the linear convergence of the multimarginal sinkhorn algorithm. SIAM Journal Optimization.
Chen, G. and Teboulle, M. (1993). Convergence analysis of proximal-like minimization algorithm using Bregman functions. SIAM Journal on Optimization, 3(3):538-555
Chen, Y., Georgiou, T., and Pavon, M. (2016). Entropic and displacement interpolation: a computa- tional approach using the Hilbert metric. SIAM Journal Applied Mathematics, 76(6):237522366
Chizat, L. (2021). Convergence rates of gradient methods for convex optimization in the space of measures. arXiv:2105.08366 [math]. arXiv: 2105.08363
Chizat, and Bach, F. (2018). On the global convergence of gradient descent over-parameterizee models using optimal transport. Advances in neural information processing systems, 31.
Chu, C., Blanchet, J., and Glynn, P. (2019). Probability functional descent: A unifying perspective on GANs, variational inference, and reinforcement learning. International Conference on Machine Learning (ICML), volume 97, pages 1213-1222.
Csiszar, (1975). I-divergence geometry of probability distributions and minimization problems. The Annals of Probability, 346-116--
Dal Maso, G. (1987). 7econvergencc and y=capacities. Annali della Scuola Normale Superiore di Pisa-Classe di Scienze, 14(3):423-464.
11

---

Dziugaite, G. K., Roy, D. M., and Ghahramani, Z. (2015). Training generative neural networks via maximum mean discrepancy optimization. Uncertainty in Artificial Intelligence.
Eggermont, P. P. B. (1993). Maximum entropy regularization for Fredholm integral equations of the first kind. SIAM Journal Mathematical Analysis, 24(6):155-11576
Franklin, J. and Lorenz, (1989), On the scaling multidimensional matrices, Linear Algebra and its Applications, 114-115:717-735.
Korba, A., Aubin-Frankowski, P.-.., Majewski. S., and Ablin, (2021). Kernel stein discrepancy descent. In International Conference on Machine Learning, pages 1719-57300 PMLR.
Korba, A., Salim, A., Arbel, M., Luise, G., and Gretton, A. (2020). A non-asymptotic analysis for stein variational gradient descent. Advances in Neural Information Processing Systems, 33:4672-466
Kunstner, F., Kumar, R., and Schmidt, M. W. (2021). Homeonorphi---nvariace of EM: Non- asymptotic convergence in KL. divergence for exponential families via mirror descent. AISTATS.
Lan, G., Lu, Z. and Monteiro, R. D. C. (2011). Primal-dual first-order methods with o(1/e) iteration-complexty for cone programming. Mathematical ProieallPPrrrr Programming, 126:1-29.
Léger, F. (2020). A gradient descent perspective on Sinkhorn. Applied Mathematics Optimization, 8442)51843-1855.
Lu. H., Freund, R. M., and Nesterov, Y. (2018). Relatively smooth convex optimization by first-order methods, and applications. SIAM Journal Optimization, 28(1):333 13333333.
Lucy, L. (1974). An iterative technique for the rectification of observed distributions. The Astronomical Journal, 79:745.
Luise, G., Salzo, S., Pontil, M., and Ciliberto, C. (2019). Sinkhorn barycenters with free support via Frank- Wolfe algorithm. Advances in neural information processing systems, 32.
Maddison, C. J., Paulin, D., Teh, Y. W., and Doucet, A. (2021). Dual space preconditioning for gradient descent. SIAM Journal on Optimization, 31(1)9991-1016.
Mei, S., Montanari, A., and Nguyen, P.-M. (2018). A mean field view of the landscape of two-layer neural networks. Proceedings of the National Academy of Sciences, 115(33).E7665-E777
Mensch, and Peyré, G. (2020). Online Sinkhorn: Optimal transport distances from sample streams. Advances in Neural Information Processing Systems, 13:1677-1667.
Milgrom, P. and Segal, I. (2002). Envelope theorems for arbitrary choice sets. Econometrica. 70(2):583-610.
Mishchenko, K. (2019). Sinkhorm algorithm special case of stochastic mirror descent. arXiv preprint arXiv: 190900618, NeurIPS 2019 OTML Workshop.
Neal, R. M. and Hinton, G. E. (1998). A view of the EM algorithm that justifies incremental, sparse, and other variants. In Learning in Gruphical Models, pages 355-368. Springer Netherlands.
Nutz, M. (2021). Introduction to entropic optimal transport. http::/www.matee www.....th.commm cow.aatth.ooo..aoa umbia /dd:/mmutzz docs Bww_oeoetureeooeeeeeeeeeeoeeeeee
Otto, F. (2001). The geometry dissipative evolution equations: the porous medium equation.
Peypouquet, J. (2015). Convex optimization in normed spaces: theory, methods and examples. Springer.
Peyré, G. and Cuturi, M. (2019). Computational optimal transport: With applications to data science. Foundations and Trends in Machine Learning, 11(5-6)355-600 607.
Phelps, R. R. (1989). Convex Functions, Monotone Operators and Differentiability Springer Berlin Heidelberg.
12

---

Resmerita, E. (2005). Regularization of ill-posed problems in Banach spaces: convergence rates. Inverse Problems, 2134):
Resmerita, E. and Anderssen, R. S. (2007). Joint additive Kullback-Leibke residual minimization and regularization for linear inverse problems. Mathematical Methods in the Applied Sciences, 30(13):1527-1544
Richardson, W. H. (1972). Bayesian-based iterative method of image restoration. Journal of the Optical Society of America, 62(1):55.
Rotskoff, G. M. and Vanden-Eijnden, E. (2018). Trainability and accuracy of neural networks: An interacting particle system approach. Technical report. lhttps://arxa http://///.ii..co/aaa/////////// 1805 00915).
Ruschendorf, I.. (1995). Convergence of the iterative proportional fitting procedure. The Annals of Statistics, 23(4).
Salim, A., Korba, A., and Luise, G. (2020). The wasserstein proximal gradient algorithm. Advances in Neural Information Processing Systems, 33:12356-1233 12366.
Santambrogio, F. (2015). Optimal Transport for Applied Mathematicians. Springer International Publishing.
Smola, A., Gretton, A., Song, L., and Schölkopf, B. (2007). A Hilbert space embedding for distributions. In International Conference on Algorithmic Learning Theory, pages 13-31. Springer.
Steinwart, I. and Christmann, A. (2008). Support vector machines. Springer Science & Business Media.
Trillos, G. and Sanz-Alonso, D. (2020). The Bayesian update: variational formulations and gradient flows. Bayesian Analysis, 15(1):29-56.
Villani, C. (2003). Topics in optimal transportation, volume 58. American Mathematical Soc.
Wibisono, A. (2018). Sampling as optimization in the space of measures: The langevin dynamics as composite optimization problem. In Conference on Learning Theory, pages 2093-3027. PMLR.
13


Reviews:
[{"review_id": "r4dSIzj-A5X", "reviewer": "Reviewer_Li1G", "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.", "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.\n\nAlso, was there any previous analysis for Richardson-Lucy deconvolution yielding convergence rates?\n\nRegarding 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?\n\n", "limitations": "yes", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nStrengths: \n\n+ 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.\n\n+ The convergence rates for Richardson-Lucy deconvolution.\n\n+ General framework of mirror descent with its convergence rates (Theorem 3)\n\nWeaknesses:\n\n+ See the questions section.\n\n\nMinor:\n\nL119 As a direct consequence of Lemma 11 in *the* Appendix\nL184 \"which proof\" -> \"whose proof\"\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "WGEwDh0LyR", "reviewer": "Reviewer_w1zg", "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.\n", "questions": "(Minor points)\n\n> 36: When using the KL divergence as Bregman divergence, mirror descent yields multiplicative updates, such as Sinkhorn’s algorithm\n\nThis 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).\n", "limitations": "No concerns", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Hmb8I3LSIE8", "reviewer": "Reviewer_SWHV", "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. ", "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. \n - 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. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper is carefully written with the theoretical parts well flesh out. \n- 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.  \n-  Connection between Sinkhorn algorithm and Mirror descent while not entirely new is interesting \n\nWeaknesses:\n- 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. \n-  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)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "7FWH3qvgih", "reviewer": "Reviewer_rqqG", "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.", "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.\nIn practice, this is only finite if the cost function c is bounded.\nIn 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?\n\nIt 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.", "rating": 9, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nExtending 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.\n\nSince both the theory and the applications of the paper are very convincing, we do not feel that there are any notable weaknesses.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept