Modified Frank Wolfe in Probability Space
Authors: Carson Kent
Jiajin Li
Jose Blanchet
Peter Glynn
Venue: NeurIPS 2021 Poster (2021)
Keywords: Frank-Wolfe
Variational Methods
Wasserstein Gradient Flows
Distributionally Robust Optimization

Abstract: We propose a novel Frank-Wolfe (FW) procedure for the optimization of infinite-dimensional functionals of probability measures - a task which arises naturally in a wide range of areas including statistical learning (e.g. variational inference) and artificial intelligence (e.g. generative adversarial networks). Our FW procedure takes advantage of Wasserstein gradient flows and strong duality results recently developed in Distributionally Robust Optimization so that gradient steps (in the Wasserstein space) can be efficiently computed using finite-dimensional, convex optimization methods. We show how to choose the step sizes in order to guarantee exponentially fast iteration convergence, under mild assumptions on the functional to optimize. We apply our algorithm to a range of functionals arising from applications in nonparametric estimation.  

Modified Frank Wolfe in Probability Space
Carson Kent Stanford University
Jiajin Li The Chinese University of Hong Kong gerrili19960gaill. com
crkent@stanford. edu
José Blanchet Stanford University jose. bl blanchtttttanforrd edu
Peter Glynn
Stanford University
glynn@stanford.c edu
Abstract
We propose novel Frank-Wolfs (FW) procedure for the optimization of infinite- dimensional functionals of probability measures a task which arises naturally in a wide range of areas including statistical learning (e.g. variational inference) and artificial intelligence (e.g. generative adversarial networks). Our FW pro- cedure takes advantage of Wasserstein gradient flows and strong duality results recently developed in Distributionally Robust Optimization so that gradient steps (in the Wasserstein space) can be efficiently computed using finite-ding mineeedimensional. convex optimization methods. We show how to choose the step sizes in order to guarantee exponentially fast iteration convergence, under mild assumptions on the functional to optimize. We apply our algorithm to range of functionals arising from applications in nonparametric estimation.
Introduction
Problems in artificial intelligence, statistics, and optimization often find a common root as an infinite dimensional optimization problem in the form
inf (J()): (EP):)))
for the space P (R!)) of Borel probability measures over Rd. In recent years, quantitative statistical and algorithmic treatments of these formulations have produced insights into modern computa- tional methods- resulting in novel approaches to difficult, open problems. Recent works in robust
optimization [6] [44 [54] (55, probabilistic faimess [57 (33, reinforcement learning 663 64,, and
generative adversarial networks [42 18 19] highlight these gains and linked by the following
theme: problems in the form of (1) provide access to rich infinite dimensional structure that sidesteps brittle artifacts finite dimensional formulations.
This paper provides the construction and analysis of modified Frank- Wolfe algorithm for I that operates from this infinite dimensional perspective and yields concrete convergence and complexity guarantees for a sub-family of problems I which are well-behaved with respect to the Wasserstein distance of order 2 (see Algorithm and Theorem []]. Under canonical conditions of smoothness and convexity we recover linear rates of convergence while, even for functionals which exhibit low degrees of smoothness and for conditions that go beyond convexity, we recover sublinear rates that are to be expected from finite dimensional analogues (36] (see Section 2.2
The vanilla Frank-Wolff method cannot work in probability space, in general, since the planar derivative (i.e. the first variation also known as the influence function) can be unbounded when distributions do not have compact support. To overcome this issue, conduct natural modification
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

to introduce a tractable. local, linear constraint- inspired by efforts in DRO 44 6 25 54
Specifically,
the modified Frank-Wole step admits the prototypical DRO formulation as below,
sup { fdy= Delu, S so
(2)
where De,,, (o) is the optimal transport cost between μ and poo (a reference measure) under some cost function c. The form of (2) itself, immediately suggests the basis of an infinite dimensional Frank- Wolfe procedure since it provides a "linear" objective subject to local, "trust-region" constraint- centered at No- The relevance of (2) in distributionally robust optimization (DRO) and mathematical finance has resulted in a multitude of computational schemes 44 34 37
54 61] for solving (2) However, hitherto, such works have failed to consider (2) within the context of a general variational
method for ( What makes these efforts notable, within the scope of this work, is that they emphasize that the solution of (2) can be highly non-trivial. Indeed, without particular assumptions, disguise an computationally hard problem- despite being convex in a Banach sense on P(RR)) Even in the case where the cost is the squared Euclidean norm c(x, y) = || y/ (the case of primary concern for this work), computational trouble can lie dormant- an artifact of inherently difficult problems in unconstrained optimization [4.. This should not be surprising, however, given specters of computational hardness dating back to early formulations of DRO [22]. To resolve these issues, we also provide a novel analysis of techniques from distributionally robust optimization (DRO) which illustrate how such formulations can be used, in computationally tractable way, construct first-order, variational methods. By localizing the problem to Wasserstein ball, the new Local Linear Minimization Oracle (LLMO) that we make in this paper not only makes the vanilla Frank- problem sensible, but it also renders the problem computationally tractable via finite dimensional convex optimization.
can
1.1 Previous work
Distributionally robust optimization To navigate such pitfalls, one can consider particular in- stances of (2) where the objective and constraints are sufficiently structured to preclude computational
intractability and permit solution via methods adapted to the provided structure, Early work with this
line (27 22 60), has recently been supplemented by approaches [13 26
7
46
37
67
35] which
focus directly on DRO formulations from particular contexts in machine learning and operations research. Unfortunately, the techniques offered by these efforts require assumptions which too restrictive for this work. These assumptions typically relate to a specific form for the objective function or constraints in (2) (e.g. linear/convex peectiion/pecewise-cooeee
objectives constraints with support or density requirements, see [31 66) 44 34 65] 4 (58) for additional examples). In this instance, such limitations preclude their applicability since, in general, a "gradient object" for functional J (see Section 2 need not satisfy these conditions.
A second, more relevant, approach to compute DRO problems (2 is to restrict the level of robustness 5 for which the problem is solved. This technique has been used in works such as 16 (54 and we apply this principle in similar spirit to [54]. In that work, smoothness of the objective in is used to, qualitatively, argue that a sufficiently small å provides a computationalll-traaae tractable optimization problem. In contrast, we provide quantification of the level of robustness required to achieve this tractability and we demonstrate that this level robustness is sufficiently large to achieve canonical convergence rates for an infinit-dimmnsionn Frank- Wolfe algorithm.
Variational methods Although formulation of a Frank- method for (T) (with quantitative bounds on complexity and convergence) has not appeared in previous literature, certain, tangentially- related variational methods offer conceptual similarity. The first of these methods is [41], which draws similar inspiration from finite-dimensional Frank-Wolfe procedures. However, the notion of first-order variation in [41] appears to be induced by the total variation distance- requiring compact support assumptions for the problem. Alternatively, we exploit Wasserstein geometry to provide a weaker notion of first-order variation, namely, Wasserstein differentiability- allowing us to eliminate restrictions to compact support. Hence, by balancing tractability of the analysis and fidelity of the procedure, the proposed algorithm scheme can be applied broad class of computational examples. Indeed, [1 only discussed the Sinkhorn barycenter problem and is still unclear how it can be applied to our setting. The second, more closely related effort, is (39 where similar, infinite- dimensional conditions (Section[2.) 2.2) are used to study particle-based methods for computing Nash cquilibria of zero-sum games. While the setting and procedures developed in this work are completely
2

---

different, we note that, as special case, our Frank- Wolfe method can also produce particle- based optimization procedure. This hints at possible insightful connections with other particle methods which are left for future consideration.
40
24
10
2
Wasserstein geometry
This work considers the problem
min (EP2(R
[()
(3)
for functionals J (RR) + R over the subset Borel measures P(RR) defined by
{ | P(R"): ||=|| du(x) oa
(2 =
(4)
In particular, we consider functionals J that are differentiable (Definition I stein distance of order 2
with respect Wasser-
(H, inf 7Ell(p.)) R
| y11 dy(22, v)
(5)
where [1, v/) is the of all joint couplings with marginals μ. E P2(IR"). Common examples of functionals that can be cast within this framework are as follows.
Example 1 (Divergences). For any convex, lower-semicontinuous function f RR, -> IR. such that f(1) = 0, one can consider a a "f-divergence" of the form
J(m) = Dy(nllu) = f f
dp dv.
(6)
dv
For instance, if ft) = t tlgg 66) reduces to Kullback-Leibie divergence DKL-
Example (Integral Probability Metrics). For set of real valued functions on Rd one can define the discrepancy
J(m) IPM (1, v) sup { f fdu
JeF Jgd [d
[ Sdv
for n. u P (R.)), where v is fixed, reference measure. Such discrepancies are termed Integral Probability Metrics (IPMs), although they may not strictly satisfy the requirements of metric- say. by failing to distinguish all pairs measures. Instead, for pair measures μl, v E P (R*), IPMs can be interpreted as measuring the extent to which μ and differ functions in F- or, rather, measuring the extent to which and y can distinguished by F. Concretely, consider F == (f || I 1) where H is reproducing kernel hilbert space (RKHS). In this case, one obtains the dual formulation of Maximum Mean Discrepancy (MMD).
2.1 Properties and differentiability for Wasserstein space
Under the Wasserstein distance, P2(Rd) is a Polish space (59] and, more importantly, it is geodesic space. That is, for every μ, V E P2 (R), there exists a constant-spert geodesic curve [0, 1) (2RR)) where p. = 1/ and
W(e: us) = |t - SosissWWil s|W(uo: p1)
(8)
Moreover, there is bijection between constant-speed geodesics and optimal transport plans Theorem 7.2.2]. Every geodesic corresponds to unique, optimal transport plan 7 E 11 (H, v) such that
[
where W²(u, v)) ff J
Ae ((1 t)x ty) 7
||x - vll dr v),
and de is the distribution of the random variable (1 - t)X tY with the pair (X, Y) following distribution Conversely, every optimal transport plan gives rise to unique geodesic via (
method minimizes a sequence of linear approximations, one must define the notion of a gradient (of functional J) to be compatible with respect to the geometry of these geodesics. In particular, as Pa (Rd) is curved under W (see Appendix A), gradients must defined in terms of selection in appropriate cotangent bundle. For Wasserstein space, this cotangent bundle (denoted CoTanp, (R2)) essentially the set of vector fields on Rdd that can approximated by gradients of smooth functions (see Appendix foro details). This results in the following definition.
Since our

---

Definition 1 (Wasserstein differentiabilitty). Let S be a geodesically convex set; that is, Ae E S for any geodesic fr between v.v/ E S. A functional J P2(RR) + E is Wasserstein differentiable on S if there is a map F : P2( + CoTanp, such that for all μ.v E S and a geodesic p4 : [0. 1] + P2 (R2) between μ and v, one has
J (Ma) - J(m)
lim
F(u:)) 20)-x) v),
(10)
Rd
where is the unique optimal transport plan (9) corresponding to f4. Note that F(u:z) = (F(μ)) (1) provides an aesthetic way of representing the evaluation at I E R of the output of F at p. The map F is called the Wasserstein derivative of J.
Remark 1. The deseription of differentiability provided by Definition ffals within the general frame- work of metric derivatives and Wasserstein gradient flows, largely codified in M. This framework is
now a well-established component of the theory of Wasserstein spaces, while the relation (T0 itself,
presents only a narrow structuring of ideas from this framework. Definition [T however, is often how
works in statistical and algorithmic fields interact with this broader area [36] 16
38 39]. Moreover,
this literature demonstrates the most motivating feature of (10): large nunber of functionals of
interest for machine learning and statistical inference exhibit Wasserstein gradients in the sense of
(TO). The curious reader is referred to
for precise statements of conditions under which (IO)
is guaranteed. However, F is intimately relative to the Gateaux differential for J [52 [6). Recall, the
Gateaux differential for a functional J exists when there an appropriate, dual space D on a closed
subspace D S P(RR)) such that
J [ + aiv p)) - (()
(
lim a-0t
(11)
for some (n) D* and all y some set S such that S S C D. In instances where the Gauteaux differential (f) exists, the Wasserstein derivative F will usually exist [39 and be given by VdJ(p). Here, we use the finite dimensional gradient operator (-) formally, and omit a rigorous exposition
on this operation in the context of Co Ta.),
It should be noted that computation of the Wasserstein derivative might be difficult. Indeed, for J in variational form such as 7. computation of the Wasserstein derivative is equivalent to finding witness function that achieves the supremum (52). In the case of a pathological sets (in 77), such a task might be intractable. To resolve this issue, and to simplify our treatment, this work utilizes the existence of an oracle for the computation of a Wasserstein gradient. This oracle permits a unified description of our Frank-Wolfe algorithm and abstracts away variation in sunctional-specinn computational cost. Recall that function in the Hölder space C* (RR) is called L-smooth if has L-Lipschitz gradients.
Definition 2 (Wasserstein Derivative Oracle). Let J P2( + R be a Wasserstein differentiable functional on a set S with Wasserstein derivative F (R - CoTamp, A L-smooth Wasserstein derivative oracle over S is an oracle which, given sample access distribution μ e $ and an error parameter e, returns an L-smooth function 6, E (Rdd satisfying
V
F(N)
S
(12)
(2()))
where I1-1l1a(0) is the canonical norm on the space (1²( of square integrable functions with respect to f. E ((Rd)). In this work, the output of this oracle is represented as O e).
Remark The qualification that the Wasserstein derivative oracle return an L-smooth function is necessary to exclude the, aforementioned, possibility of a pathological Wasserstein derivative- that would be intractable for use in a computational procedure. the fact that the cotangent space CoTan at a point y is too large. Such condition is common in other variational methods 3 19 64 20 and is relatively superficial- when coupled with the degree of approximation afforded by Via smoothing techniques [5]] [] (38), functionals can often be assumed to have Wasserstein derivatives which are C²(Rd) or are well-approximable by C'l (IR)) functions.
some ways, this representative of
2.2 Smoothness and Lojasiewicz inequalities
In finite dimensions, iterative, gradient- based methods typically require the specification of two conditions in order to achieve convergence.

---

The accuracy of local, linear approximations that are provided by the gradient.
The extent to which local descent makes global progress on the objective.
Here, we state these conditions in the context of functionals over Wasserstein space.
Definition (a-Hööler smoothness). Let S be a geodesically convex set and let P2 (RR) + I be a functional which is continuously Wasserstein differentiable on the set S. J is said to be locally Holder smooth on S with parameters T and A if for all μ E S and all v E S such that W(n, v) S A, there exists an optimal transport plan y E P2 (TR. IR.) such that
J J2xxd F(u:)) d7(2,))
T Wi+a (v. I+a -amatt
J(V) S J(H)+
(13)
Definition 4 (Lojasiewicz (nnjeuiievizzieequulttt, A Wasserstein differentiable functional J/ on set S C (12)) said to satisfy a Lojasiewicz inequality with parameter т and exponent if for all μ E and J. == inf wss (()
(J(()) - J.)" < [[F()))1)))))
(14)
where F is the Wasserstein derivative (T0) of
Remark 3. More restrictive versions of both 13 and commonly appear in previous literature to 32 39
establish the explicit converence rate 3
19 15 In most cases, the a-Hölder smoothness condition (13) is stated for a and required to hold globally (A oo). This smoothness criterion is considerably weaker since it requires that the Wasserstein gradient only provide a local approximation that is slightly more than first-order accurate. Moreover, such a condition can be necessary when the Wasserstein derivative (T)) is not Lipschitz with respect to W in the cotangent space norm on (R see [43] for such an example. Additionally, statement of the Lojasiewicz inequality (14) is broader than canonical treatments due to the presence of the auxiliary power 0. Most often, the specific instances either = 1/2 or = are considered. The case 0 1 is implied for (geodesically) convex functionals J with a W-bounded level set, while 0 1/2 is implied for strongly convex J/ 1 32). Although the notions of Holder smoothness condition (14) and Lojasiewicz inequalities (I3) have been well-studied in the literature [33] (5), the of both of these conditions with explicitly determined exponents a and f to provide concrete convergence rates for pnpputatoooally-mllemmeeee
infinite-dimensoon descent method does not appear in related literature as far as the authors are aware.
3 Modified Frank-Wolft algorithm
Algorithm D provides our modified Frank Wolfe procedure along with its associated convergence guarantees and sample complexities in Theorem [ and Proposition [ It is worth mentioning that the algorithm itself only requires a much weaker notion of differentiability to be applicable, namely, Gateaux differentiability (i.e., (p) in (IT) exists). In Section 4 we will provide several com- putational examples which may not satisfy the following assumptions but work well in practice. We have to admit there is a theoretical and computational gap. We will leave it as an open ques- tion for our future work. However, to conduct the convergence analysis, we require the following cesumptions-phrassee in the language from Section
Assumption (Smoothness assumption). The functional J (2( R is Wasserstein differen- tiable (Definition 1 and locally a-Holder smooth (Definition set 5 P2 (R( with parameters and A > 0 (Definition B) Further, an L-smooth Wasserstein derivative oracle (Definition 2 for J exists.
Assumption 2 (Local richness). The set S is rich enough to contain the solution to for μa E S,
L-smooth f. and < Ag.
Remark 4. When
not the whole set, is necessary to invoke Assumption 2 to guarantee that the
iterates produced by our algorithm remain in S. This is result of the fact that the solution of (15) is
optimal for some Wasserstein ball of size 8 < 8. Hence, each of these iterates is guaranteed to lie in so long as 8 < Ag.
innnuieall Assumption (t.ojasiewicz assumption). The functional J satisfies Eojasiewicz inequality 14) on S C P2( with parameters 7 > 0 and 0.
5

---

Algorithm Modified Frank Wolfe for
Input:
Wasserstein derivative oracle θ initial distribution flo, smoothness parameter gradient
error é, estimation error E, iterate error ?, stopping threshold r, step sizes (31, 82, Ba), number of iterations k
for - do
Let p..- + (14--1,
(b Definition
Compute p (1(()-)) - -ES s Vōy.. (P(M-11)
if s S then break
else 5 f min (51, 828, 338 (/)) 5 t de
Compute μ4 satisfying W (Mis (i-1) S å and
(>) Proposition
I
J @mm. du -
inf Mis
mm du SS
(15)
return μl
Theorem 1. Under Assumptions 7 and an appropriate choice of input parameters, Algorithm
7
computes a distribution μ² satisfying
r(p"): = J(x') - inf J(,) S
(16)
in at most
k O6-P6
(17)
iterations, where p- denotes the negative part of = a* for the dual exponent a = a1 The notation O-) omits logarithmic factors in it's arguments.
Remark 5. In the case of (geodescially) strongly-convex and 1-Hölder smooth functional J, the Eojasiewicz inequality (14) holds with 0 1/2 and obtains standard Õ(1) complexity (in terms of c). This is to be expected from finite dimensional analogues [6). Similarly, for J which is only convex (with a W-bounded level set), (14) holds with = and (17 yields Ö(c-') complexity that mimics canonical results. The step size required to achieve these complexities illustrated by the choice of 8 in Algorithm
For functionals which are a-Hölder smooth for < 1, the dependence on the dual exponent a* in (17) can be rather punishing for small a. It is natural to ask if this exponent could be improved within the scope Assumptions [ and Moreover, in finite dimensions, it is well known that first-order methods for convex and a-Hölder smooth functions (also known as weakly smooth functions) can
obtain e-optimal solutions in -(e-2((+3a)) iterations [47] Hence, could even be considered whether, given geodesic-convexity assumptions J, better iteration complexity for Algorithm would be obtainable.
We conjecture that such improvements unlikely particularly those that would draw analogy from finite dimensional techniques. The motivation for this is as follows. common approach to establishing improved iteration complexities for convex, a-Hölder smooth functions, in finite dimensions to consider their gradient oracles as inexact oracles for convex, 1-Hölder smooth Using either averaging arguments accelerated methods, more rapid progress an underlying objective can then be made with these inexact oracles. Our Frank- Wolfe method already utilizes an inexact step (15) so, conceptually, such an approach could be applied Algorithm
functions 23
I Unfortunately, however, such finite dimensional analogies fail due to the difficulty of averaging distributions in Wasserstein space. Indeed, in finite dimensions, averaging is crucial prevent emoor accumulation from outpacing objective progress. Since Wasserstein space is positively curved (Appendix A) computing analogous convex combinations of the μ4 in Algorithm variational problem that might be as expensive to compute as the original problem
[ is, itself,
3.1 Computation of the Frank- Wolfe step
algorithm for computation of the Frank Wolfe step 15 given in Appendix and the net result of this procedure is follows.

---

Proposition 1. Under the assumptions of Theorem 1 there exists stochastic algorithm which (with high probability) provides sample access distribution satisfying (15). Moreover, in the setting of (7), this algorithm requires O (e (E-2a" 0) samples and gradient evaluations.
Crucially, the property enabling Proposition iss duality. The Trank-Wolfee problem dual of the form
15
exhibits a
V gd
( inf AVERR
|10 v1l') du(())
8
sup X
((v)
(18)
and (18) is amenable to computation using techniques from finite dimensional optimization. This approach derives from distributionally robust optimization [6] [54] 25 34 where such techniques have
been used produce methods in optimization and machine learning that are robust to adversarial perturbations.
In general, solution of (15) for any level of 8 could be computationally hard 6 54]. However, since Frank- Wolfe procedure need only solve local problems, not global ones, we show: there is a 6 which is, simultancously, small enough to enable the efficient computation of (88), yet large enough to
produce (7).. The techniques used to achieve these results most closely resemble ideas from [54].
However, provide precise quantification of the 5 in (15) that is required to achieve computation
tractability and develop a procedure which yields guarantees on the primal-dual gap of (15) and (18). In turn, the theoretical insights that we obtain suggest an empirical procedure in which À in (8 can
be updated relatively infrequently within our Frank-Waon algorithm, provided that it is chosen on proper scale. Such an implementation is investigated Section and yields significant computational savings.
It is also worth noting that the implementation in Appendix C requires only sample access do in order to provide sample access to a distribution satisfying (16). Thus, all operations in Algorithm ! be implemented using only sample access Mao Practically, however, it is often more efficient to maintain approximations to the iterates μ4 via a non-parametrie estimator. When this is done, results in additional, additive error in the residual (T6) each step of Algorithm [ on the order of the error produced by the Wasserstein derivative oracle O the iteration complexity (17) remains unaffected. Moreover, analysis of the error induced by a particular non-parametric approximation of the μi is highly problem dependent- so we do not consider it in the context of Theorem
If this error is
Computational examples
In this section, demonstrate the application Frank- Wolfe algorithm to several non- non-parametric estimation problems in statistics and machine learning. All simulations are implemented using Python 3.8 high performance computing server running Ubuntu 18.04 with Gen Quad Intel(R) Xeon(R) Platinum 8268 CPU 2. 2.90GHzz processor. As we mentioned in Section 3 the proposed algorithm just needs very weak of differentiability be applied (i.e., Gateaux differentiability). The computational examples we conduct in this section aim to show attractive performance in applications where the assumptions required for theoretical convergence are unknown, instead of corroborating our theoretical results.
4.1 Gaussian deconvolution
A classical task in nonparametric statistics 12 8 is to infer latent, data-generating distribution c E P2 (IRd) from a set of observations that are corrupted by independent, additive Gaussian noise. For observations Yi.... Y, such that Y; = X; + Z, where X; n,, Z, ~ N (0, o2). One seeks to compute a normmerait estimate of μ μ the variance of the noise o² is considered known. Since Z; independent of X,, this task amounts to "deconvolving" μ from the distribution of Z:. A natural candidate for y is the maximun-likellhood estimator (MLE),
Σ log / go (Y: x) dp(x)
j == arg max
(19)
P (R4)
1=1
7

---

where 9o is the density of Z, We refer the reader to [50] Section 3] for further details but note that it was shown [50] that @ has an equivalent characterization
arg min Do=(H, Pr) MEP2(3d)
(20)
where
Daa (21, =
inf xellipn.sa) ) 2 ||- u/12
dr (2, -1l
o D'L & p2)
(21)
is the entropic optimal transportation distance and By is the empirical distribution of the Y, The problem (20) readily lies within the framework of (3) for J(p) = Do= (H, Py). Moreover, it is known 41 that the Wasserstein derivative (T0) of D (M, Py) with respect is given by
Vén(x) = o² log
exp ((07 - | v:11 121l/22 /09)
(22)
==1
where nx E Rn is dual variable (corresponding Py-) which is optimal for Dy=(pu Py). This provides a Wasserstein derivative oracle for (20) as the vector v" can be readily approximated using
sinkhorn or stochastic gradient algorithms 49
Toy example On 2D Gaussian mixture A simple, two dimensional instance of (19) shown in Figure dataset Y, of 50 samples with mixture of 4 Gaussians illustrated by the kernel density estimator of the Y, shown red. The behavior of our Frank-Wolft A Algorithm is depicted over the course of several iterations, where the foreground contours provide the density of the iterate, 14, that is maintained by the algorithm. It can be easily observed that despite the small overlap between our initial distribution and target one, our method reaches the global optima very quickly.
Iteration
Iteration
Iteration 5
Iteration 8
10
10
10
10
5
5
0
0
-5
-5
-5
-5
10
10
10
10
98.682
61.367
40.837
18.594
Iteration
lteration 14
Iteration 16
Iteration 25
10
10
10
10
5
5
0
0
-5
-5
-5
-5
10
10
10
10
5.904
3.909
3.333
2.811
Figure Toy Example on a 2D Gaussian Mixture. Note that the initial distribution set as N([10, 10), I') for 2 = 0.4 and the number of particles is 200. The bisection method of Appendix Cis used with tolerance set to 1e The objective value D, (p, P,)) is below to each sub-figure.
Uniform strategy for À and sensitivity analysis on high-dimensional examples Since the num- ber of bisection ascent step for À in (18) that arises during the search can be large, the original algorithm may be computationally rather demanding for high-dimensional cases. Thus,

---

Prank-Wolre Convergence
Sensitivity Anelysis Scaling
Sensitivity Analysis
Risuction
Constant
lop (o,n Pv))
lopo Qu. Pg))
D,4u. P-)
$01
201
20
26
40
26
Itoration
Iteration
Iteration
(a) Objective Value
(b) Scaling Factor E
(c) Step size
Figure 2: High-dimensional Gaussian deconvolution for = 64. For 50 data points, Y, sampled from mixture of 7-Gaussians, 200 particles used in non-parametric estimate the μ4, In Figure 2(a) the tolerance for the ascent method is 1e 33 and the shaded bands show the standard derivation over 10 independent runs with random initializations. In Figure 2(b) the step size 5 is 0.5.
motivated develop an approach that makes constant which only depends on the step size inner solver, where is
= =//11/2 //2 without other mie-iimeniional optimization methods the scaling factor. Figure ([ provides a convergence behavior comparison between the vanilla Agoorthm|[aand the modification leveraging this new uniform strategy. Not surprisingly, the modified Frank-Wolfe algorithm can get to the local region around the global optima faster but with a larger variance, the uniform strategy is indeed a more aggressive strategy at the early stage. To further support the uniform strategy and our Frank- Wolfe framework, we conduct extensive sensitivity experiments on the hyperparameter (e.g., step size ó and scaling factor =). Both Figure 2(b) and [(c) demonstrate that our algorithm is robust to these crucial hyperparamter. We can also observe that it is better not choose relatively large step size although we can converge faster at the beginning but suffer from the risk of divergence, as the maximum step size is controlled by the smooth parameter in theory. Hence, our experiment results here also corroborate the theoretical findings.
is worth mentioning that this new uniform strategy can make our Frank-Wolfs framework be extended asynchronous decentralized parallel setting easily and thus further meet the requirements of large-scale applications. Based on the superior performance, we left its rigorous convergence analysis open question.
4.2
Nonparametric learning with student-teacher networks
The rise of generative adversarial networks (GANs) 28 and efforts connecting neural networks and
kernel regression [17.. have generated interest in maximum mean discrepancy (MMD). particularly
with respect to it's role in constructing nigh-dimensional, distributional embeddings (20) (5]. This
development is predicated on the observation that any neural network (x.,) + (xx θ), which
produces output (zx 0) E _ from input data E X C Rd and parameters 0 θ C Rm yields a kernel on the parameter set O:
k(01,02) == Ez [v(x, (0(x,,0))' (b),
(23)
where the expectation over æ is taken with respect to data generating distribution. Via MMD, k(.--) induces a natural discrepancy measure between distributions over network parameters O. Thus, learning of a generative image model can be expressed as minimizing MMD with respect to latent, generative distribution for v. We refer
45 for further deseriptions of these applications.
Being an integral probability metric 7 squared MMD lies well within the framework of this paper
J(z) == MMD? (μ, v)).
(24)
and the Gateaux derivative (i.e.. influence function) of J admits natural expression as the difference between the mean embeddings of μ and 1
(x) Ez-, [k(2, +)] E.-D [k(2,x)]
(25)
Indeed, f can be readily computed via sampling methods- even when l or v are continuous or large, discrete distributions [29]. Note that, as discussed in Remark 1, the Wasserstein

---

Frank-Wolte (Uniform)
MMD Flow (with noise injection)
Ker el Sobolev Descent
Rean (wer 20 tume) Sondard Dacittio
Viant l9ca 10 ngrul Standart Dayy ador
Maur (we 10 srrs
Sauttard Devidtinn
Validaton Eror
0.22
ValitaGon Eror
0.22
0.22
Validation
0.15-
0.55
0:35
0.13-
0.16-
6.33
0.07
0.05
5.65
50603
100030 150000
102000
220002
300020
4003C0
10000
20200
50:00
40002
Gradient Evaluations
Gradlent Evalustions
Gradient Evaluations
Figure 3: Teacher Network; The detailed implementation set up is as 3 Appendix G]. The left one is the result for our Frank-Wolfe method with the uniform strategy X size d is 0.5. The number of particle is 200.
0.05 and the step
derivative is, under sufficient regularity. the gradient of the Gateaux differential (.). Perhaps the most advantageous consequence of (25), however, that the Wasserstein gradient directly inherits regularity present in k: Indeed, should V, (xr, y be L--Lipschitz in a (uniformly for all y), J (24)
naturally T-smooth [3 This has led the development of several variational or particle-based
methods for minimizing (24)
13 45 20).
Remark 6. For general MMD functionals, the smoothness and Lojasiewicz inequalities (i.e., Assump- tions D and 3 are shown in [3. Nevertheless, the MMD experiments in our paper, following the setup 3 fail to satisfy the differentiability assumptions in 3 due the ReLUU terms present in
the network defining the kernel.
However, despite a possible violation of the assumptions, Figure 3 demonstrates the competitive performance of our method with two of baselines showcased in Student-Teacher network problem. Our method is shown on the left, the center plot shows the "MMD gradient flow" algorithm from B and the right plot provides the "Sobolev Descent" algorithm of (45) Performance is evaluated in terms of MMD eπrоr on a validation dataset and is shown as a function of the total gradient evaluations performed by each method. This provides better proxy for relative performance and convergence since an iteration of Algorithm Pprforms multiple solves that are, each, similar in terms of gradient complexity to a single iteration of MMD gradient flow or Sobolev descent. Further, the total number of gradient evaluations should not be viewed as proxy for wall-time as, for each gradient evaluation, the number of operations performed by each method can vary widely. Indeed, for each gradient evaluation in Sobolev descent an entire linear system solve is performed, which computational demanding in practice, Also, note that, as both MMD gradient flow and Sobolev descent are particle-based Algorithm | was, for the purposes of comparison, instantiated with particle distribution of equal size.
Conclusion
This paper introduces and studies Frank- Wolfe procedure for the minimization of functionals of probability measures. While these methods have been widely studied in the finite-dimensional setting: current environment presents both significant benefits and opportunities. First, many problems of interest can be posed in terms of the types of formulations that we study [18] 19
6 54
20
39 64]
55 57 [ Second, our algorithm can naturally be asynchronously parallelized. This a research
avenue of significant promise that we plan to explore in future work, especially in connection with the wide range of applications mentioned earlier.
Acknowledgements Material in this paper is based upon work supported by the Air Force Office of Scientific Research under award number FA9550-20-1 1-0997. Additional support is gratefully acknowledged from NSF grants 191 1915967, 1820942 and 1838576.
10

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No] The
contributions of this work are mainly theoretical. We do not foresee any negative societal impact as a consequence.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] See the supplemental material
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results? [Yes] See the supplemental material
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes]
4. If you using existing assets (e.g., code, data, models) or curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]

---

References
[1] L. Ambrosio, N. Gigli, and G. Savare. Gradient Flows: In Metric Spaces and in the Space of Probability Measures. Lectures in Mathematics. ETH Zürich. Birkhäuser Basel, 2005.
[2] Luigi Ambrosio and Nicola Gigli. Construction of the parallel transport in the wasserstein space. Methods Appl. Anal., 15(1):1-30, 03 2008.
[3] Michael Arbel, Anna Korba, Adil SALIM, and Arthur Gretton. Maximum mean discrepancy gradient flow. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[4] Daniel Bartl, Samuel Drapeau, and Ludovic Tangpi. Computational aspects of robust optimized certainty equivalents and option pricing. Mathematical Finance, 30(1):287-309, 2020.
[5] Adrien Blanchet and Jérôme Bolte. A family of functional inequalities: łojasiewicz inequalities and displacement convex functions. Journal of Functional Analysis, 275( 1650--666, 2018.
[6] Jose Blanchet and Karthyek Murthy. Quantifying distributional model risk via optimal transport. SSRN Electronic Journal, 04 2016.
[7] Jose Blanchet, Karthyek Murthy, and Fan Zhang. Optimal transport based distributionally robust optimization: Structural properties and iterative schemes. 2018.
[8] Claire Caillerie, Frédéric Chazal, Jérôme Dedecker, and Bertrand Michel. Deconvolution for the Wasserstein metric and geometric inference. Electronic Journal of Statistics, 5(none):139p 1423, 2011.
[9] R. Carmona and F. Delarue. Probabilistic Theory of Mean Field Games with Applications II: Mean Field Games with Common Noise and Master Equations. Probability Theory and Stochastic Modelling. Springer International Publishing. 2018
[10] J. A. Carrillo, K. Craig, L. Wang, and Chaozhen Wei. Primal dual methods for wasserstein gradient flows. arXiv: Numerical Analysis, 2019.
[11] José Antonio Carrillo, Katy Craig, and Francesco S. Patacchini. A blob method for diffusion. Calculus of Variations and Partial Differential Equations, 58(2):53, Feb 2019.
[12] Raymond J. Carroll and Peter Hall. Optimal rates of convergence for deconvolving density. Journal of the American Statistical Association, 83(404): 10::::18881111 18--1886 1988.
[13] Z. Chen, D. Kuhn, and W. Wiesemann. Data-driven chance constrained programs over wasser- stein balls. arXiv: Optimization and Control, 2018.
[14] T.C.E. Cheng and Mikhail Y. Kovalyov. An unconstrained optimization problem is np-hard given an oracle representation of its objective function: a technical note. Computers & Operations Research, 29 29044)20077-09 2002.
[15] Sinho Chewi, Tyler Maunu, Philippe Rigollet, and Austin J. Stromme. Gradient descent algorithms for Bures- Sass--assseennn barycenters. In Jacob Abernethy and Shivani Agarwal, editors, Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 1276-1304. PMLR, 09-12 Jul 2020.
[16] Lénaïc Chizat and Francis Bach. On the global convergence of gradient descent for over- parameterized models using optimal transport. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Casa-eeaBiiia Bianchi, and R. Garnett, editors, Advances in Neural Information Pro- cessing Systems, volume 31. Curran Associates, Inc., 2018.
[17] Lénaïc Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable program- ming. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d Alché-Bue, E. Fox, and R. Garnett, editors, Advances Neural Information Processing Systems, volume 32, Curran Associates, Inc., 2019.
12

---

[18] Casey Chu, Jose Blanchet, and Peter Glynn. Probability functional descent: A unifying perspec- tive on GANs, variational inference, and reinforcement learning. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 1213-1222. PMIR,, 09-15 Jun 2019.
[19] Casey Chu, Kentaro Minami, and Kenji Fukumizu. Smoothness and stability in gans. In International Conference on Learning Representations, 2020.
[20] Samuel Cohen, Michael Arbel, and Mare P. Deisenroth. Estimating barycenters of measures in high dimensions. arXiv:2007.077 07000, 2020.
[21] Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. In C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013.
[22] Erick Delage and Yinyu Ye. Distributionally robust optimization under moment uncertainty with application to data-driven problems. Operations Research, 58(3):995-612, 2010.
[23] Olivier Devolder, François Glineur, and Yurii Nesterov. First-order methods of smooth convex optimization with inexact oracle. Mathematical Programming, 146(1):37755, Aug 2014.
[24] Futoshi Futami, Zhenghang Cui, Issei Sato, and Masashi Sugiyama. Bayesian posterior approx- imation via greedy particle optimization. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01):3606-33) 3613, Jul. 2019.
[25] Rui Gao and A. Kleywegt. Distributionally robust stochastic optimization with wasserstein distance. arXiv: Optimization and Control, 2016.
[26] Soumyadip Ghosh, Mark Squillante, and Ebisa Wollega. Efficient stochastic gradient descent for learning with distributionally robust optimization. 2018.
[27] Joel Goh and Melvyn Sim. Distributionally robust optimization and its tractable approximations. Operations Research, 58(4-part- 11:02-9-17 2010.
[28] Ian J. Goodfellow, Jean Pouget- Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. Proceedings of the 27th International Conference on Neural Information Processing Systems Volume 2, NIPS 14, page 2672-2680 2680, Cambridge, MA, USA, 2014. MIT Press.
[29] Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel two-sample test. J. Mach. Learn. Res., 13(null):723-773 March 2012.
[30] O. Güller. Foundations of Optimization. Graduate Texts in Mathematics. Springer New York, 2010.
[31] Grani A. Hanasusanto and Daniel Kuhn. Conic programming reformulations of two-stage distributionally robust linear programs over wasserstein balls. Operations Research, 66(3):849 869, 2018
[32] Daniel Hauer and José Mazón. Kurbixa--opssieviczzsimoo inequality for gradient flows in metric spaces. Transactions of the American Mathematical Society, 372(7)4917-4977, 2019.
[33] Daniel Hauer and José Mazón. Kurdyyk--ojasievicc--smoo inequality for gradient flows in metric spaces. Transactions of the American Mathematical Society, 372(7)4917-4976, 2019.
[34] Daniel Kuhn, Peyman Mohajerin Esfahani, V. Nguyen, and Soroosh Shafiezzadeh-Abadeh Wasserstein distributionally robust optimization: Theory and applications in machine learning. ArXiv, abs/1908. 908.08729. 2019.
[35] Daniel Levy, Yair Carmon, John Duchi, and Aaron Sidford. Large-scale methods for distributionally robust optimization. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 8847-8860. Curran Associates, Inc., 2020.
13

---

[36] Guoyin Li and Ting Kei Pong. Calculus of the exponent of pardyka--ojasiewiiee inequality and its applications linear convergence of first-order methods. Foundations of Computational Mathemalics, 18(5): 199-1232, Oct 2018
[37] Jiajin Li, Sen Huang, and Anthony Man-Cho So. A first-order algorithmic framework for distributionally robust logistic regression. In H. Wallach, H. Larochelle, A. Beygelzimer, F. Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[38] Chang Liu, Jingwei Zhuo, Pengyu Cheng, Ruiyi Zhang, and Jun Zhu. Understanding and accel- erating particle-basee variational inference. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 0092. PMLR, 09-15 Jun 2019.
[39] L. Liu, Y. Zhang, Z. Yang, R. Babanezhad, and Z. Wang. infiite-dimmnsionn game optimization via variational transport. OPT 2020, 2020.
[40] Qiang Liu and Dilin Wang. Stein variational gradient descent: A general purpose bayesian inference algorithm. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016.
[41] Giulia Luise, Saverio Salzo, Massimiliano Pontil, and Carlo Ciliberto. Sinkhorn barycenters with free support via frank-wolft algorithm. In H. Wallach, H. Larochelle, A. Beygelzimer, d' Alché-Bue, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[42] S. Mahdian, J. Blanchet, and P. Glynn. Optimal transport relaxations with application to wasserstein gans. ArXiv, abs/1906.03317, 2019.
[43] Quentin Mérigot, Alex Delalande, and Frederic Chazal. Quantitative stability of optimal transport maps and linearization of the 2-wasserstein space. In Silvia Chiappa and Roberto Calandra, editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 3186-3196 PMLR, 26-28 Aug 2020.
[44] Peyman Mohajerin Esfahani and Daniel Kuhn. Data-driven distributionally robust optimization using the wasserstein metric: Performance guarantees and tractable reformulations. Math. Program., 171(1-2): 15-166, September 2018.
[45] Youssef Mroueh, Tom Sercu, and Anant Raj. Sobolev descent. In Kamalika Chaudhuri and Masashi Sugiyama, editors, Proceedings of the Twentt-Second International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pages 2976-2985. PMLR, 16-18 Apr 2019.
[46] Hongseok Namkoong and John C. Duchi. Stochastic gradient methods for distributionally robust optimization with f-divergences. In Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS' 16. page 2216-2224 Red Hook, NY, USA, 2016. Curran Associates Inc.
[47] A. Nemirovskiī and Yu. E. Nesterov. Optimal methods for smooth convex minimization. Zh. Vychisl. Mat. i Mat. Fiz,, 25(3):356-38) 369, 477, 1985.
[48] Y. Nesterov. Introductory Lectures on Convex Optimization: A Basic Course. Applied Opti- mization. Springer US, 2003.
[49] Gabriel Peyré, Marco Cuturi, et al. Computational optimal transport: With applications to data science. Foundations and Trends@ in Machine Learning. 11(5-6)3556667, 2019.
[50] Philippe Rigollet and Jonathan Weed. Entropic optimal transport is maximum-likellhen deconvolution. Comptes Rendus Mathematique, 356(11): (202111))::22))11 220112222222 2018.
[51] Maziar Sanjabi, Jimmy Ba, Meisam Razaviyayn, and Jason D. Lee. On the convergence and robustness of training gans with regularized optimal transport. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS' 18, page 7091-7101, Red Hook, NY, USA, 2018 Curran Associates Inc
14

---

[52] F. Santambrogio. Optimal Transport Applied Mathematicianss: Calcudus of Variations, PDEs, and Modeling. Progress in Nonlinear Differential Equations and Their Applications. Springer International Publishing, 2015.
[53] M. Scetbon, Laurent Meunier, J. Atif, and Marco Cuturi. Equitable and optimal transport with multiple agents. arXiv: Machine Learning. 2020.
[54] Aman Sinha, Hongseok Namkoong, and John Duchi. Certifiable distributional robustness with principled adversarial training. In International Conference on Learning Representations, 2018.
[55] Matthew Staib and Stefanie Jegelka. Distributionally robust optimization and generalization in kernel methods. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[56] Amirhossein Taghvaei and Prashant Mehta. Accelerated flow for probability distributions. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 6076-6085, PMLR, 09-15 Jun 2019.
[57] Bahar Taskesen, V. Nguyen, Daniel Kuhn, and J. Blanchet. distributionally robust approach to fair classification. ArXiv, abs/2007 009500, 2020.
[58] Bart P. G. Van Parys, Peyman Mohajerin Esfahani, and Daniel Kuhn. From data decisions: Distributionally robust optimization is optimal. Management Science, 0(0):null, O.
[59] C. Villani. Optimal Transport: Old and New. Grundlehren der mathematischen Wissenschaften. Springer Berlin Heidelberg. 2008
[60] Wolfram Wiesemann, Daniel Kuhn, and Melvyn Sim. Distributionally robust convex optimiza- tion. Operations Research, 22(6):135-1337) 2014.
[61] Weijun Xie. On distributionally robust chance constrained programs with wasserstein distance. Mathematical Programming, 186(1):115-155 Mar 2021.
[62] K. Yoshida, Functional Analysis. Classics in mathematics / Springer. World Publishing Company, 1980.
[63] Junyu Zhang, Alec Koppel, Amrit Singh Bedi, Csaba Szepesvari, and Mengdi Wang. Variational policy gradient method for reinforcement learning with general utilities. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances Neural Information Processing Systems, volume 33, pages 4572-4583 Curran Associates, Inc., 2020.
[64] Junyu Zhang, Alec Koppel, Amrit Singh Bedi, Csaba Szepesvari, and Mengdi Wang. Variational policy gradient method for reinforcement learning with general utilities. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 4572-4583. Curran Associates, Inc., 2020.
[65] Chaoyue Zhao and Yongpei Guan. Data-driven risk-averse stochastic optimization with wasser- stein metric. Operations Research Letters, 46(2):262-261 267, 2018.
[66] X. Zheng and Chen. Data-driven distributionally robust unit commitment with wasserstein metric: Tractable formulation and efficient solution method. IEEE Transactions on Power Systems, 35(6):4940 4943, 2020.
[67] A. Zhou, M. Yang, M. Wang, and Y. Zhang. linear programming approximation of distribu- tionally robust chance-constrained dispatch with wasserstein distance. IEEE Transactions Power Systems, 3565):3366-3377, 2020.
15


Reviews:
[{"review_id": "js7mp-FEie", "reviewer": "Reviewer_cwwb", "summary": "This paper proposes an algorithm for the minimization of functionals of probability distributions. The authors derive a convergence rate in the case of a smooth and PL function (under the geometry given by the Wasserstein distance of order 2). They also run some synthetic experiments of non-parametric estimation", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_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": "## Main Points\n### Originality and significance: \nI am not an expert in the area of Distributionally Robust Optimization (DRO) and Variational method which are the areas addressed in the related work of this paper. However, I can comment on the originality of this paper with respect to the optimization literature.\nIt seems to me that the connection between the main algorithm (alg. 1) and the Frank-Wolfe algorithm is not clear. Algorithm 1 seems to be a steepest descent method [Boyd, 2004] with the Wasserstein distance: at each timestep an estimation of the gradient is computed and then a minimizer of the inner product with the gradient within a delta ball is computed in (15). \n\nMoreover, the Frank-Wolfe algorithm is a constrained convex optimization method. The problem considered in (1) is unconstrained. It is not clear how the set S is handled and if S is actually a constraint or not. All this to say that I do not see any clear connection with the Frank-Wolfe algorithm. Can the authors comment on the following question: to what extent your algorithm is related to Frank-Wolfe and steepest descent method? What is the novelty of your analysis with regards to a standard analysis of steepest descent method under PL and smoothness assumptions?\n\n### Clarity: \nThe topic of this paper is quite technical and I think this paper does an OK job at introducing the notions. However, one missing key point in this paper is the algorithm to compute the approximate gradient oracle (called ‘Frank Wolfe step’ in the paper.. Though it is more a steepest descent step in my opinion). I looked at the appendix quite extensively and it seems that one should run algorithm 3 to get a $\\lambda$, sample $x \\sim \\mu$  and then return $m_\\lambda(x)$ see (99). It would be useful to have a pseudo algorithm summarizing this in the main paper.\n \n### Soundness of the experiments: \nAre the experiments within the assumptions? It is not mentioned or justified that the functions considered are smooth and PL. \nA significant part of the related work is dedicated to DRO? Since this work cannot handle constrained optimization (J has to be smooth) how is this work related to DRO?\nAbout the Set S: All your assumptions mention a set $S$: If the set $S$ is not the whole space, how do you make sure that the iterates stay in $S$? What are non-trivial examples of sets $S$?\n\n\n\n## Minor details:\n- L29: DRO in mentioned before being defined\n- L129 Gauteaux\n- L135 What is ‘the supremum”\n- L660 a ‘\\hat’ is missing \n- Eq (54), (65) and (58) it seems that a square is missing on $g_{i-1}$ (thankfully since you need it for the second line of (58))\n\n## References:\nBoyd, Stephen, Stephen P. Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.\n\n### I have read the authors' responses and the other reviews. I stand with the points of reviewer pe3w so I will maintain my score. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "VQsP_7Or83j", "reviewer": "Reviewer_8BEc", "summary": "This work investigates optimization in infinite dimensional functionals of probability measures. The authors first define a notion of gradient of functional using Wasserstein gradient flows. Then, the authors propose a Frank-Wolfe procedure in which gradient steps can be computed using finite dimensional and convex optimization methods. The authors show that their algorithm is guaranteed to converge under some assumptions by choosing proper step sizes. Finally, the authors apply their method to two non-parametric estimation problems.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_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": "The paper aims to optimize a functional of probability measures. This problem is very important and has a lot of applications in machine learning. The paper is well written and has a nice logical flow. The claims in the paper are also well supported. The notion of Wasserstein differentiability introduced to define the gradient of functional is novel, and the proposed Frank-Wolfe procedure is promising. In particular, I like their “primal-dual” algorithm for solving the Frank-Wolfe step which can implicitly maintain a primal-feasible iterate and also make progress on the primal-dual gap.\n\nSome questions:\n\n(1) The notion of Wasserstein differentiability is defined with respect to Wasserstein distance of order 2. I am curious whether this definition can be easily extended to $p$-order Wasserstein distance (e.g., p=1). Similarly, if considering 1-Wasserstein distance, does the algorithm (also the convergence guarantees) still apply?\n\n(2) In Definition 1, the authors define the gradient of a functional in terms of cotangent bundle. If I understand correctly, the element in cotangent bundle should be a mapping from $\\mathbb{R}^d\\rightarrow \\mathbb{R}^d$. Then in Section 4.2, the authors claim that the Wasserstein derivative of squared MMD is the difference between the mean embedding of $\\mu$ and $\\nu$, i.e., $f_{\\mu}^*(\\cdot)$. However $f_{\\mu}^*(\\cdot)$ is a mapping from $\\mathbb{R}^m\\rightarrow \\mathbb{R}$. Isn't this contradictory? Can the authors clarify this?\n\n(3) All assumptions and also Theorem 1 assume a geodesically convex set S. I am interested in what S would be like in practice. Is there any functional of probability measures such that S would be the whole space $\\mathcal{P}_2(\\mathbb{R}^d)$? Moreover, the authors claim that the Frank-Wolfe problem (15) exhibits a dual form given by (18). Can the authors please provide some references for this dual result?\n\nMinor comments:\n\n(1) The authors should comply with the NeurIPS 2021 style where there is no \"Broader impact\" Section and the checklist should be after the References Section.\n\n(2) There are some typos, e.g.,\n- In Line 108, \"a selections\"-> \"a selection\"\n- In Line 116, \"a aesthetic\"-> \"an aesthetic\"\n- In Line 260, $\\nu$ should be $\\mu$\n- In line 163 and (15), $W$ should be $\\mathcal{W}$.\n- What is $\\bar{\\mathbb{R}}$?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The original Frank-Wolfe algorithm proposed by the authors might be computationally expensive for high-dimensional cases as it need a large number of ascent step for $\\lambda$ in computation of gradient steps. To address this issue, the authors provide a uniform strategy for $\\lambda$  which can reduce computational costs. The authors claim that they do not foresee any negative societal impact as the contributions of their work are theoretical.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "20"}, "extra_text": {}}, {"review_id": "97J6meb4XA3", "reviewer": "Reviewer_pe3w", "summary": "This paper provides a first-order iterative method based on Local Linear Minimization Oracle (LLMO) to solve smooth optimization problems in probability spaces. It also analyses its convergence rate under a variety of localized relaxation of classical structural assumptions (local Holder smoothness or Lojasiewicz type of inequality) and approximate oracles (gradient and LLMO).\n\n** The answer to the author's answers is in the comment. I raise my score to 5.", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_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": "The paper originally proposes an algorithm based on LLMO in the context of Probability space. However, I find the paper hard to read with many inaccurate/incomplete statements, missing references, and non-explicit facts preventing the reader from fully appreciating the authors' contribution. A striking example of inaccuracy is that the algorithm is not the \"Frank-Wolfe\" method adapted to Probability Space. Therefore, I believe that this paper requires a major revision. Hence, although the contribution is appreciable, I strongly recommend rejecting this paper. I now provide a detailed review which will hopefully be helpful for the major revision.\n\nMajor comments.\n\n\n- Algorithm description. Algorithm 3 is a non-standard first order method that iteratively solve linear minimization oracle on a shrinking Wasserstein neighborhood of the current iterates.\nThe size of the neighborhood is a trade-off between the progression made at each iteration and the computational tractability of the linear minimization subproblems.\nThe algorithm is itself very interesting but is almost not explained nor compared/related to existing Frank-Wolfe methods.\nThe explanations are confusing and too much space is attributed to speculative discussion about futur work rather that explaning the algorithm (see, e.g., Line 202-220).\\\nAlso, a first obvious remark is that it should not be called \"Frank-Wolfe for (3)\" (or the paper be called \"Frank-Wolfe on Probability Space\"), it is absolutely not the classical form of the original Frank-Wolfe algorithm, for which every subproblems is a linear minimization oracle over the initial constraint domain.\\\nThe algorithm uses  Local Linear Minimization Oracle (LLMO) very reminiscent to the LLMO use in the conditional gradient methods of [Garber2013] and following works. Unfortunately, the authors do not mention any of these previous papers using such LLMO.\\\nFinally, there are also some notational problems that make it hard to read, e.g. $s$ as the stopping criterion with the norm of the gradient, in (15) $\\nu$ should belong to $B_{\\mathcal{W}}(\\mu_{i-1}, \\delta)\\cap \\mathcal{P}_2(\\mathbb{R}^d)$ or the choice of $\\delta$ that can be confused with that of (2).\n\n- Theorem 1 is not properly stated. What does an \"appropriate choice of input parameters\" mean? In Assumption 1, $S$ is not specified to be geodesically convex; is it in Theorem 1? What is the nature of $S$? In the Holder definition, the interplay between $S$ and $\\Delta$ could gain from being clarified. Do the authors assume $J$ to be geodesically convex?\\\nIs $\\mu_0$ belonging to $S$? Are there guarantees that (15) maintains the iterates in $S$? The questions are rhetoric here to outline the riddle the reader has to go through to understand the significance of the results.\\\nAlso, Assumption 2 is not discussed in conjunction with $S$. To draw a parallel with the normed space setting, if $S$ is an open neighborhood in the compact constraint set $\\mathcal{C}$, vanilla Frank-Wolfe converge linearly when the function is smooth and strongly convex (and the convergence results of FW with Holder-smoothness and Lojasiewicz inequality are discussed in [Ker18]).\\\nAs currently written, it is impossible to understand the significance of Theorem 1. (not to mention that numerical results do not illustrate the theorem).\n\n- Unfair or unclear devaluating of related work.\nIn \"However, [39] narrowly considers the Sinkhorn barycenter problem [...]\" the wording \"narrowly\" is inappropriate and inaccurate. There are seemingly no significant difficulty at extending the results of [Liuse2019] to functional $J$ that satisfy the smoothness assumption proposed in [Liuse2019], i.e., outside the Sinkhorn barycenter problem. Also, example 4.1. relies on [Liuse2019] to establish the Wasserstein smoothness of the objective function. Yet, the authors only mention it in Section 4.\nHowever, it is important to relate it in the introduction since it outlines that a main challenge of optimization in probability spaces is to establish the structural properties satisfied by the problems and not only prove the convergence behavior under these structural properties (the current focus of the authors). This fact appears very clearly in the paper of [Liuse2019], where the main technical challenge seems to establish these structural assumptions rather than extending the FW convergence results to probability spaces.\\\nAlso, it would be better to clarify the distinction between the algorithm in [Liuse2019] and Algorithm 1: indeed, the algorithm of [Liuse2019] is much closer to the \"Frank-Wolfe in Probability Spaces\". For instance, in [Liuse2019], they solve a similar type of problem with smooth objective function only that they solve the constraint problem on $\\mathcal{M}_+(\\mathbb{R}^d)$ rather than on $\\mathcal{P}_2(\\mathbb{R}^d)$. Is that difference important?\\\nSo, the term \"narrowly\" is confusing and a  bit impolite. Finally, see the list of minor comments for more examples of inadequate treatments of the related works.\n\n- Importance of Assumption 2. From the previous point, if both methods are a Frank-Wolfe on probability space, then how do the $\\mathcal{O}(1/T)$ of [Liuse2019] is to be compared with the linear convergence rates of Theorem 1 (when the function is smooth and the Lojasiewicz inequality is global with parameter $\\theta=1/2$)? Is the Frank-Wolfe of [Liuse2019] simply less efficient?\\\nActually, I tend to believe that Assumption $2$ plays a central role in the distinction. To draw a comparison with known convergence rates of the Frank-Wolfe methods in normed spaces, the type of rates obtained in Theorem 1 corresponds to the settings when the optimum is in the interior of the constraint set. If the comparison holds, then the $1/T$ convergence rate in [Liuse2019] may stem from the fact that \"the domain $\\mathcal{M}_+^1(\\mathcal{X})$ has empty interior in the space of finite signed measure.\" [Liuse2019] such that the comparison cannot be drawn. In this paper, we do not know to what the rate should be compared: Is the choice of \"S\" such that the solution is in the interior of $\\mathcal{P}_2(\\mathcal{X})$? Does it even make sense? What is the cost of an LLMO iteration? Is it comparable to a proximal step or that of an LMO? Overall, it seems very tangential to see Algorithm 1 as a Frank-Wolfe method.\n\n- Comparison of Theorem 1 with known results in \"similar\" settings. How does the convergence rates compares with known convergence regimes of Frank-Wolfe methods? The authors seems to compare their convergence result with that of proximal methods. Is it because the authors consider the LLMO as kind of proximal steps? This might be the case, since it is not really comparable with a LMO on the initial constraint domain.\n\n- Lojasiewicz conditions. The current presentation of the convergence results with objective functions satisfying Lojasiewicz inequality seems shallow since the class of functions satisfying Loja in that setting is not discussed, no examples are given, and references are missing. I tend to believe that the paper would be clearer without extension to Lojasiewicz inequalities in the main paper but discussion about the meaning of Assumption 2. 1) Lojasiewicz inequalities seem not particularly interesting if they do not come with the theory that explains for which problems' structures they hold generically; 2) missing references about the uses of Lojasiewicz type condition with Frank-Wolfe algorithms, i.e., [Ker2019,Rinaldi2020]; 3) the author present it as a contribution (remark 4) to provide these Lojasiewicz type of inequality, while it is very straightforward or already explored in the context of probability spaces [Bolte2016,Hauer2017]; 4) no examples are given in the numerical experiment part with $\\theta\\neq 1/2$; 6) no discussion about the nature of the subset $S$ on which it is satisfied.\\\nFor point 1), the crux of the power of Lojasiewicz inequalities is that they are known to hold generically for some classes of functions, e.g., subanalytical functions, see [Bolte2007] for references and extension of the classes of function on which it holds generically. However, the authors do not discuss how this applies in their setting, which I believe can be challenging. Important references exploring these directions are missing, e.g. (but probably others), [Bolte2016,Hauer2017].\\\nLine 40 \"Even in the case where the cost in the squared Euclidean norm $c(x,y)=\\|x-y\\|^2$ (the case of primary interest [...]\". Also, in the numerical experiment, the authors only consider (but do not prove it) strongly convex objective functions. So, the Lojasiewicz extension seems relatively shallow. It is not motivated by practical examples, nor is guaranteed by the theory to hold generically.\\\n\n- Numerical Experiments. There are no log plots, and it appears that the convergence is sublinear and not even linear in the asymptotic. So experiments do not support the theory?\nThe authors do not discuss how the given examples satisfy the Lojasiewicz assumption, and I believe they are only strongly convex.  In line 278, the authors write, \"our method reaches the global optima very quickly\". This is not very professional; we expect a link with the theoretical results.\n\n- Important references are missing.\\\nThe Kernel Herding methods with Frank-Wolfe [Bach2012]. This is an important reference as it deals with the difficulty of obtaining a faster rate of convergence on Frank-Wolfe in the infinite-dimensional setting. These papers [Bach2012,Lacoste2015] could be discussed in a related work paragraph on Frank-Wolfe methods.\\\nMissing ref about Lojasiewic in metric spaces, e.g. [Bolte2016,Hauer2017] and others.\\\nThere are specific papers that provide a complete description on the convergence of Frank-Wolfe methods under Holder-smoothness and Lojasiewicz type of inequalities [Ker18,Ker19,Rinaldi2020,Bomze2021].\\\nOther papers about infinite dimensional FW in probability spaces like [Denoyelle2019,Mensch2019] and others.\\\n[Garber2013] for Local Linear Minimization Oracle.\\\n[Guelat1986] for linear convergence of Frank-Wolfe with only smoothness and strong convexity when the optimum is in the interior of the constraint set.\\\n\n\n\nOthers semi-major comments:\n\n- The narrative about the origin of the FW scheme is unclear. Line 29 \"development of our FW method is inspired by efforts in DRO [42,5,24,52]\". This is confusing because the authors ultimately solve another problem (3). And the confusion is reinforced by the $\\delta$ parameter in Algorithm 1 that does not correspond to (2).\nIt rather seems that [42,5,24,52] arguably inspired the paper to focus on problems such as (2), but where is the link with Frank-Wolfe? How did these works inspire the authors' algorithmic development with the Frank-Wolfe algorithms? It is rather the paper from [Liuse2019] (and [Mensch2019] for which the authors missed the reference although they are indicated in the Liuse paper) that inspired the Frank-Wolfe scheme for that type of problem.\\\nIn Line 32-33, \"The form (2), itself, immediately suggests the basis of an infinite-dimensional Frank-Wolfe procedure since it provides a \"linear\" objective [...]\". This explanation is not convincing and looks like an attempt to write another narrative about the origin of using Frank-Wolfe (maybe the reader becomes overly suspicious); in page 4 of [Liuse2019], the comment \"[...] in this work we adopt the Frank-Wolfe we adopt the Frank-Wolfe (FW) algorithm. Indeed, one key advantage of this method is that it is formulated in terms of directional derivatives along with feasible directions [...]\" is a more convincing reason for using FW algorithms specifically for these types of problems.\\\nThere are also issues with the paragraph \"Variational methods\" in Line 66. \"[...] which draws similar inspiration from finite-dimensional Frank-Wolfe procedures\", it is unclear and might lead the reader to believe that the authors deal with the infinite-dimensional setting while other works did not; which is false since e.g. [Liuse2019] already did. The authors do not mention (in the related work paragraph, although they do it in the numerical experiment) also that an important contribution of [Liuse2019] is to prove smoothness of their functional w.r.t. the total variation norm, and the authors use these results in section 4.1.\n\n-  Unclear claims: in Line 53-56, \"Unfortunately, the techniques offered by these efforts require assumptions which are too restrictive for this work.\" For the reader, this statement becomes unclear given the lack of details in Theorem 1, or the authors not discussing when their Lojasiewicz types of inequality are available nor discussing either how restrictive the local richness assumption is.\\\nIn Line 136-138, \"To resolve this issue, and to simplify our treatment, this work utilizes the existence of an oracle for the computation of a Wasserstein gradient.\" The wording \"to simplify our treatment\" is doubtful: isn't it a necessity (which is perfectly fine but triggers doubt during reading)?\nBesides, it is unclear how such an assumption does not limit the result of this work to the scope of the previous works, which were deemed not to be general enough. The authors could expand on that. It is always uncomfortable to read claims about generality with respect to previous works and then see the results with restrictive assumptions that are not discussed.\n\n- First-order methods and Frank-Wolfe. It is relatively well-known that Frank-Wolfe methods have different rates of convergence than other first-order methods. However, in several places, the authors keep on referring to non-projection-free first-order methods, e.g., \"we recover sublinear rates that are to be expected from finite-dimensional analogs [34]\" (Line 27-28) or \"A common approach to establishing improved iteration complexities for convex [...]\" (Line 210-211). \\\nThe reference to [34] is strange; they do not deal with Frank-Wolfe algorithms. The linear convergence rates of Frank-Wolfe are sometimes compared with that of other first-order methods, e.g., when the unconstrained optimum is in the interior of the constraint set. An in-depth discussion of this assumption in the context of (2) would be interesting. Several papers seem to suggest that the assumptions that lead to accelerated convergence results on Frank-Wolfe are relatively similar in finite-dimensional or infinite-dimensional settings or in normed spaces versus metric spaces. Here, the authors do not connect with these types of results.\n\n- The title is too generic with respect to the content of the paper. It is also improper; it is far from being a canonical Frank-Wolfe algorithm. The current title is detrimental to previous and future works on the topic.\n\n- The introduction brings some confusion as to what problem is being solved. It is only via the caption of Algorithm 1 that the reader understands that (3) that is being solved.\n\nMinor comments.\n- Line 9: \"reasonable assumptions\"? \"mild\"?\n\n- Line 20-21: \"problems in the form of (1) provide access to rich infinite dimensional structure that sidesteps brittle artifacts of finite dimensional formulations\". Could you add references and details of specific examples of \"brittle artifacts\"?\n\n- Line 36-37 \"such works have failed to consider (2) within the context of a general variational method for (1).\" the wording \"have failed\" is violent and unfair.\n\n- Line 62-65, \"In that work, smoothness of the objective in (2) is used to, qualitatively, argue that [..]. In contrast, we provide quantification of the level of robustness required to achieve this tractability and demonstrate [...]\": here, there is no reference as to where the authors deal with that in the paper; also, the wording \"quantitatively\" and \"demonstrate\" are ambiguous: do the authors provide a theoretical result? Or rather provide numerical schemes to better chose the level of smoothness? In the absence of forward reference, it is hard to understand.\n\n- Line 69: \"(with quantitative bounds on complexity and convergence)\": I would drop \"quantitative\".\n\n- Line 97 \"is a Polish spaces [57]\": not defined.\n\n- Line 107-108 \"gradients must be defined in terms of a selections in an appropriation cotangent bundle space\". Typo on selections. But most importantly, these important technical details are not sufficiently explained. The authors allow space for speculative discussions as in Line 209-220 or long sentences to explain common sense (e.g., Line 48-50).\n\n- Line 107-108 \"In particular, as $P_2(R)$ is curved under W (see Appendix A), gradients must be defined in terms of selections in an appropriate cotangent bundle\". In Appendix A, the proof of the statement states in Line 602 \"The final bullet [the space curvature results] is a direct restatement of the results in Section 8.4. in [1]\". So, that would be nice in the main to add (along with the forward reference to the appendix) directly the reference to [1]. Otherwise, it provides the wrong impression that it is the authors' contribution (no one read the appendices).\n\n- Line 109 \"is essentially\": I don't know what \"essentially\" refers to in that setting.\n\n- Line 125 \"the curious reader\": a bit annoying when the reader is already annoyed by the lack of clarity.\n\n- Line 156: \"In finite dimensions, iterative, gradient-based ...\" There exists infinite-dimensional work already, so why suggesting that this work provide a novel view on infinite dimensional settings?\nAlso, at first sight, the paper does not describe all gradient based methods but Frank-Wolfe methods, so why keeping it general to first order methods?\n\n- Line 168-178: No mention of the analogous results in normed spaces and no mention of what structure to assume on $J$ to ensure the existence of Lojasiewicz inequality with a non-trivial parameter. This is however the main appeal of Lojasiewicz inequalities.\n\n- Line 180: In algorithm, the second line in the for loop: I found it strange to ask to compute s (and actually, the instruction is even less clear since it asks to compute an inequality which makes no sense), why not just directly taking the norm of your approximate gradient as the stopping criterion?\n\n- Line 180: The choice of $\\delta$ in Algorithm 3 is confusing since it could refers to Equation (2) while the algorithm seek to solving Equation (3).\n\n- Line 191-195: Please provide the reference as to where the proof is in the appendix.\n\n- Line 209-220: I find it too speculative; this is the type of discussion that should be in the conclusion. Also, it is at odd to elaborate on a futur results when the algorithm itself has not been properly introduced. Besides, the elaboration concern techniques of acceleration for proximal methods, not conditional gradient methods (that are different, see e.g. corrective version of FW or [Comb2020]), so hardly understandable in that context.\n\nAdditional references.\n\n[Bach2012] Francis Bach, Simon Lacoste-Julien, Guillaume Obozinski. On the Equivalence between Herding and Conditional Gradient Algorithms. ICML 2012.\n\t\n[Bolte2007] Bolte, J.; Daniilidis, A. and Lewis, A. The {\\L}ojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems. 2007.\n\n[Bolte2016] J. Bolte, A. Blanchet. A family of functional inequalities: Lojasiewicz inequalities and displacement convex functions. 2016\n\n[Bomze2020] I Bomze, F Rinaldi, D Zeffiro. Frank-Wolfe and friends: a journey into projection-free first-order optimization methods. 2020\n\n[Comb2020] Combettes, C. and Pokutta, S. (2020). Boosting Frank-Wolfe\nby chasing gradients. ICML.\n\n[Denoyelle2019] Denoyelle, Q.; Duval, V.; Peyré, G. and Soubies, E. The sliding Frank-Wolfe algorithm and its application to super-resolution microscopy. 2019.\n\n[Garber2013] Dan Garber, Elad Hazan. A linearly convergent conditional gradient algorithm with applications to online and stochastic optimization.\n\n[Guelat1986] J. GuéLat; P. Marcotte. Some comments on Wolfe's away step.\n\n[Hauer2017] D. Hauer, J. Mazon. Kurdyka-Lojasiewicz-Simon inequality for gradient flows in metric spaces. 2017.\n\n[Ker18] T. Kerdreux, A. d'Aspremont, S. Pokutta. Restarting Frank-Wolfe: Faster Rates Under Hölderian Error Bounds. \n\n[Ker19] T. Kerdreux, A. d'Aspremont, S. Pokutta. Restarting Frank-Wolfe. AISTATS 2019.\n\n[Lacoste2015] S. Lacoste-Julien, F. Lindsten, F. Bach. Sequential Kernel Herding: Frank-Wolfe Optimization for Particle Filtering. ICML 2015.\n\n[Liuse2019] G. Luise, S. Salzo, M. Pontil and C. Ciliberto. Sinkhorn barycenters with free support via frank-wolfe methods. NeurIPS 2019.\n\n[Mensch2019] Arthur Mensch, Mathieu Blondel, Gabriel Peyré. Geometric Losses for Distributional Learning. ICML 2020.\n\n[Rinaldi2020] F. Rinaldi, D. Zeffiro. A unifying framework for the analysis of projection-free first-order methods under a sufficient slope condition.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "20"}, "extra_text": {}}, {"review_id": "8xeek7Ld_6C", "reviewer": "Reviewer_yMtu", "summary": "The paper introduces Frank-Wolfe algorithms for minimizing differentiable functionals over probability measures. It can be applied to a wide range of applications from several fields and shed light on distributionally robust optimization problems over ambiguity sets defined through the Wasserstein metric.", "questions": "", "limitations": "", "rating": 9, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_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": "The methods and perspectives are novel. Potential applications of the proposed algorithms are wide are and remain open. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "More discussions on how to handle other types of Wasserstein metrics are necessary. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: I carefully read the interactions between the reviewers and the authors as initially there was some strong split between the reviewers. Some of the things have been clarified in the meantime, so that the overall assessment seems to be that this paper is a good paper. Certain issues regarding notions and review of related methods etc have been raised however. I would like the authors to give the reviews appropriate considerations when preparing their revision. The authors answers have been taking into consideration.
Decision: Accept (Poster)