DISCRETE-TIME GRADIENT FLOWS AND LAW OF LARGENUMBERS IN ALEXANDROV SPACES
SHIN-ICHI OHTA AND MIKLÓS PÁLFIA
Abstract. We develop the theory of discrete-time gradient ﬂows for convex functions on Alexandrov spaces with arbitrary upper or lower curvature bounds. We
employ diﬀerent resolvent maps in the upper and lower curvature bound cases toconstruct such a ﬂow, and show its convergence to a minimizer of the potentialfunction. We also prove a stochastic version, a generalized law of large numbers forconvex function valued random variables, which not only extends Sturm’s law oflarge numbers on nonpositively curved spaces to arbitrary lower or upper curvaturebounds, but this version seems new even in the Euclidean setting. These results
generalize those in nonpositively curved spaces (partly for squared distance functions) due to Bačák, Jost, Sturm and others, and the lower curvature bound caseseems entirely new.

1. Introduction
In this paper, we consider discrete-time gradient ﬂows for convex functions on
Alexandrov spaces (X, d) with arbitrary upper or lower curvature bounds. An Alexandrov space is a metric space whose sectional curvature is bounded above or below bysome constant in the sense of triangle comparison theorem (see Section 2). The
discrete-time gradient ﬂow is introduced with an appropriate notion of resolvent operator Jλf : X → X deﬁned for a ﬁxed geodesically convex function f and a positive
number λ > 0. The operator Jλf provides a gradient descent step towards the set ofminimizers of f . Under upper and lower curvature bounds, we deﬁne our Jλf diﬀerently. In the case of upper curvature bounds, we employ the standard Moreau–Yosida
Key words and phrases. Alexandrov space, convex function, discrete time gradient ﬂow, law oflarge numbers.
AMS Classiﬁcations (2010): 51K05, 53C20, 58C05, 49L20, 49M37
S.O. is supported by the Grant-in-Aid for Young Scientists (B) 23740048; M.P. is supported by the
Research Fellowship of the Canon Foundation.
1

2

SHIN-ICHI OHTA AND MIKLÓS PÁLFIA

resolvent:(1.1){
Jλf (x) := arg miny∈G1
f (y) + d(x, y)22λ}for a closed geodesically convex set G containing a nonempty sublevel set of f . In
the case of lower curvature bounds, we deﬁne(1.2)

Jλf (x) := g-exp(λ∇(−f )(x)),

where g-exp is the gradient exponential map and ∇(−f )(x) denotes the gradientvector of −f (see [37, 38] and Sections 3, 4 for these notions). Before discussing thereason why we use these diﬀerent resolvents, we present our results in this paper.
With these mappings at hand, we deﬁne the sequence
xk+1 := Jλfk (xk )for k ≥ 0 with an arbitrary starting point x0 and for an a priori given positive sequence
λk > 0. We prove the convergence of xk to a minimizer of f under various, plausible
conditions on f and the sequence λk . In particular, we generalize the classical resultsin [12] to arbitrary Alexandrov spaces. Furthermore, our results generalize the ones
recently given in [5] for NPC spaces (Alexandrov spaces with upper curvature boundby 0) to arbitrary Alexandrov spaces. In the upper curvature bound case, we allow X
to be inﬁnite dimensional, while in the lower curvature bound case we formulate ourresults for ﬁnite dimensions for technical reasons, although our techniques would workin inﬁnite dimensions equally well. The most general known results in the literature,according to our knowledge, consider NPC spaces and Riemannian manifolds with
nonpositive sectional curvature, see for example [7, 15, 27] just to mention a few
among the numerous results. Also our results relate to and generalize the ones givenin [17, 18, 19, 20] for NPC spaces, and harmonic maps with NPC target spaces.
∑n
We also consider the case of f (x) =i=1 fi (x), where fi are also geodesically∑2
convex functions. Then, under the assumption of ∞k=0 λk < +∞ and the Lipschitz
continuity of fi , we prove that the sequence generated by(1.3)

xk+1 := Jλfk1 ◦ · · · ◦ Jλfkn (xk )converges to a minimizer of f in any Alexandrov space. On the one hand, this result generalizes the ones given for Euclidean spaces in [9, 8, 32, 33] and for NPC

DISCRETE-TIME GRADIENT FLOWS IN ALEXANDROV SPACES

3

spaces in [6]. On the other hand, this is also a generalization of the “no dice” approximation result given in NPC spaces for the barycenter, which is the minimizer of∑f (x) = ni=1 wi d(x, ai )2 with ﬁxed points ai ∈ X, in [28, 16]. The barycenter (sometimes also called the Karcher mean indebted to [21]), or more generally the p-mean∑
obtained as the unique minimizer of f (x) = ni=1 wi d(x, ai )p for p ∈ [1, +∞), is ofgreat interest, see for example [3, 4, 10, 11, 19, 26, 22, 23]. Our general approximation
results, motivated by and applied for p-means among many others, carry over to positively curved Riemannian setting, for example, compact Lie groups with bi-invariant
Riemannian metrics [3, 4, 31, 22, 23], see Remarks 6.8 and 6.9.
We also prove a stochastic version of the convergence of the discrete-time ﬂow givenin (1.3). In this setting, we assume that∫h(x)dµ(h),f (x) :=FK (G)

where µ is a probability measure supported over the cone of lower semi-continuous,
K-convex functions FK (G) over G, with K > 0. Then we prove a law of large numbers
result for the stochastic sequence
xk+1 := Jλfkk (xk ),where fk is a sequence of independent, identically distributed FK (G)-valued randomvariables with distribution µ. That is to say, we prove that xk → Eµ almost surely,∫
where Eµ is the (unique) minimizer of f (x) = FK (G) h(x)dµ(h). This generalizes aresult of Sturm [43, 44], which states that xk → Eµ almost surely when µ is supported
only on squared distance functions ga (x) := d(a, x)2 on NPC spaces. This result ofSturm already implies the classical law of large numbers on Euclidean spaces, since∫on them Eµ = G adµ̃(a), where µ̃ is the push-forward measure of µ under the map
ga . Hence our result extends the law of large numbers to arbitrary Alexandrov spaces
and arbitrary convex functions, see Remarks 6.8 and 6.9. Sturm [41, 42, 43, 45] used
his result in his stochastic approach to the theory of harmonic maps between metricspaces, and also his result became extremely useful for the barycenter in the case of
the NPC space of positive deﬁnite matrices [26, 28, 16]. Therefore we expect wide
applicability of our results, for example in the case of positive curvature.

4SHIN-ICHI OHTA AND MIKLÓS PÁLFIA

The deﬁnitions and properties of Jλf distinguish two diﬀerent kinds of approaches in
the lower and upper curvature bound cases. In [2, 17, 19, 20] among many others, forsetting up the minimizing movements, the original resolvent (1.1) given in [12] is being
used that we also adopt in the upper curvature bound case. Besides technical reasons,the usefulness of (1.1) in discrete-time gradient ﬂows is due to the fact that Alexandrov
spaces with upper curvature bounds are simply connected and have unique minimal
geodesics in balls with designated radii. We cannot expect these properties in thelower curvature bound case, the injectivity radius can be 0 even locally. Then it isdiﬃcult to control the behavior of discrete-time ﬂows and there are no investigationin this direction as far as the authors know, while continuous-time gradient ﬂows areintensively studied in [37, 38, 29, 35, 19].
To overcome this diﬃculty, we introduce the other (but natural) construction (1.2)
relying on gradient vectors directly. This makes an interesting contrast with (1.1):(1.4)

logxk+1 xk = λ∇f (xk+1 ),(1.5)

logxk xk+1 = λ∇(−f )(xk ),in the upper and lower curvature bounds, respectively, where logx y is the direction
from x to y. In other words, these two ﬂows provided in the opposite curvaturebounds are in reverse relation. In the upper curvature bound case, we take thebackward ﬂow for the convex function f , while we take the forward ﬂow for the
concave function −f in the lower curvature bound case. In Euclidean spaces, bothmethods work equivalently well [9, 8, 32, 33]. In general, it seems that the curvaturebound determines whether a proximal step (1.1) or a gradient step (1.2) is moresuitable from the analytic point of view of discrete ﬂows. For instance, the convexityof squared distance functions, which is the very deﬁnition of upper curvature bounds,
can give a contraction estimate of discrete-time gradient ﬂows together with (1.4)(estimate d(xk+1 , yk+1 ) from above by using d(xk , yk ) and the convexity of f along
a geodesic between xk+1 and yk+1 ). Similarly, the concavity of squared distancefunctions is useful only with (1.5) (via the convexity of f along a geodesic between
xk and yk ).

DISCRETE-TIME GRADIENT FLOWS IN ALEXANDROV SPACES

5

2. Alexandrov spaces
We refer to [13] for the basics of metric geometry and Alexandrov spaces. Let(X, d) be a metric space. A continuous curve γ : [0, 1] → X is called a minimal
geodesic if it satisﬁes d(γ(s), γ(t)) = |s − t|d(γ(0), γ(1)) for all s, t ∈ [0, 1]. We saythat (X, d) is geodesic if any two points x, y ∈ X admit a minimal geodesic between
them. Though minimal geodesics are not necessarily unique, we abuse the notationx#t y, t ∈ [0, 1], for denoting a minimal geodesic from x to y. A subset G ⊂ X is said
to be geodesically convex if, for any x, y ∈ G, all minimal geodesics x#t y between
them are contained in G.
For κ ∈ R, we denote by M2 (κ) a complete, simply connected, 2-dimensional
Riemannian manifold of constant sectional curvature κ. For three points x, y, z ∈ X√with d(x, y) + d(y, z) + d(z, x) < 2π/ κ if κ > 0, we can take corresponding points
x̃, ỹ, z̃ ∈ M2 (κ) uniquely up to rigid motions such thatdM2 (κ) (x̃, ỹ) = d(x, y),dM2 (κ) (ỹ, z̃) = d(y, z),

dM2 (κ) (z̃, x̃) = d(z, x).

We call 4x̃ỹz̃ a comparison triangle of 4xyz in M2 (κ).
Deﬁnition 2.1. [Alexandrov spaces] A geodesic metric space (X, d) is called an
Alexandrov space of curvature bounded above by κ if, for any x, y, z ∈ X with d(x, y)+√d(y, z) + d(z, x) < 2π/ κ if κ > 0, we have
(2.1)

d(y#t z, x) ≤ dM2 (κ) (ỹ#t z̃, x̃)for any minimal geodesic y#t z joining y and z.
Similarly, (X, d) is called an Alexandrov space of curvature bounded below by κ if
we have(2.2)

d(y#t z, x) ≥ dM2 (κ) (ỹ#t z̃, x̃)for any minimal geodesic y#t z.
For instance, if κ = 0, then (2.1) is calculated asd(x, y#t z)2 ≤ (1 − t)d(x, y)2 + td(x, z)2 − t(1 − t)d(y, z)2 ,and (2.2) isd(x, y#t z)2 ≥ (1 − t)d(x, y)2 + td(x, z)2 − t(1 − t)d(y, z)2 .

6SHIN-ICHI OHTA AND MIKLÓS PÁLFIA

By the parallelogram identity, Hilbert spaces have curvature bounded both above andbelow by 0. Here are some further examples.
Example 2.2. (1) A complete, simply connected Riemannian manifold with the
Riemannian distance is an Alexandrov space with curvature bounded above by κ
if and only if its sectional curvature is not greater than κ. Typical examples of
nonpositively curved spaces admitting singularities include trees, Euclidean buildings
and gluing of nonpositively curved spaces. See [13, §9.1] for further examples.
(2) A complete Riemannian manifold is an Alexandrov space of curvature bounded
below by κ if and only if its sectional curvature is not less than κ. Typical examples ofnonnegatively curved spaces admitting singularities include the boundaries of convex
domains in Euclidean spaces, quotients of nonnegatively curved spaces by isometries(e.g., orbifolds), and the L2 -Wasserstein spaces over nonnegatively curved spaces (see[46, 35]). We refer to [13, §10.2] for further examples.
An important feature of Alexandrov spaces is that angles are well deﬁned between
two geodesics γ and η emanating from the same point γ(0) = η(0) = x:g η(s),g∠x (γ, η) := lim ∠γ(t)x̃s,t→0+g η(s)
g is a comparison triangle in M2 (κ). For ﬁxed x ∈ X, we deﬁne Σ0 X
where γ(t)x̃
x
as the set of unit speed minimal geodesics γ : [0, δ] → X, δ > 0, emanating fromx. The angle ∠x (γ, η) deﬁnes a pseudo-distance on the set Σ0x X. The completion of(Σ0x X/{∠x = 0}, ∠x ) with respect to ∠x is denoted by (Σx X, ∠x ), and is called thespace of directions at x ∈ X.
The tangent cone (Cx X, σx ) at x ∈ X is deﬁned as the Euclidean cone over(Σx X, ∠x ):Cx X := (Σx X × [0, ∞))/ ∼,where (γ, 0) ∼ (η, 0) andσx ((γ, s), (η, t)) :=√s2 + t2 − 2st cos ∠x (γ, η)for (γ, s), (η, t) ∈ Cx X. We denote by ox the origin (∗, 0) ∈ Cx X. For any u =(γ, s), v = (η, t) ∈ Cx X, we can deﬁne their inner product as
hu, vi := st cos ∠x (γ, η).

DISCRETE-TIME GRADIENT FLOWS IN ALEXANDROV SPACES

7

If X is complete, ﬁnite Hausdorﬀ dimensional and has curvature bounded abovein the sense of Deﬁnition 2.1, then (Σx X, ∠x ) is an Alexandrov space of curvaturebounded above by 1 and (Cx X, σx ) is an Alexandrov space of curvature bounded
above by 0. In the case of curvature bounded below, we have the same curvaturebounds for (Σx X, ∠x ) and (Cx X, σx ), but from below. In the inﬁnite dimensionalcase, however, this is not the case in general.
By the deﬁnition of the angle, we readily have the following (see [13, Corollary 4.5.7]).
Theorem 2.3 (First variation formula). Let γ : [0, δ] → X be a geodesic in an
Alexandrov space (X, d) with curvature bounded above or below by κ, and assume that
X is locally compact in the lower curvature bound case. Put x := γ(0) and take y ∈ X√with d(x, y) < π/ κ if κ > 0. Then the function d(t) := d(γ(t), y) satisﬁes(2.3)

d(²) − d(0)1=−
max hγ 0 (0), η 0 (0)i ,²→0+²d(x, y) ηlim

where η : [0, 1] → X runs over all minimal geodesics from x to y.
We remark that η is unique under the upper curvature bound. The inequality ‘≤’holds in (2.3) for any η in a more general situation without any compactness assumption ([13, Proposition 4.5.2]), and such an inequality is enough in our discussion in
the lower curvature bound case. Equality in (2.3) is necessary only in the proof of
Lemma 4.6(I).
3. Convex functions on Alexandrov spaces
Let (X, d) be an Alexandrov space with curvature bounded above or below byκ ∈ R. We say that a function f : X → (−∞, ∞] is K-(geodesically) convex forK ∈ R ifKt(1 − t)d(x, y)22
holds for any x, y ∈ X, t ∈ [0, 1] and any minimal geodesic x#t y. The 0-convexity(3.1)

f (x#t y) ≤ (1 − t)f (x) + tf (y) −will be simply called the convexity.
Deﬁnition 3.1. [Absolute gradients] Let f : X → (−∞, ∞] be lower semi-continuous
and K-convex. Then the (descending) absolute gradient of f at x ∈ X with f (x) 6= ∞

8SHIN-ICHI OHTA AND MIKLÓS PÁLFIA

is deﬁned by{}
f (x) − f (y).
|∇− f |(x) := max 0, lim supd(x, y)y→xNote that |∇− f |(x) ∈ [0, ∞] and also |∇− f |(x) = 0 if f (x) = inf y∈X f (y).
Deﬁnition 3.2. [Directional derivatives] For f : X → (−∞, ∞], the directional
derivative of f at x with f (x) 6= ∞ in the direction v ∈ Cx X is deﬁned as{}f (γ(st)) − f (x)Dx f (v) := lim inf lim,t→0+(γ,s)→vt
where (γ, s) ∈ Σ0x X × [0, ∞) ⊂ Cx X.
The above limit along γ indeed exists for lower semi-continuous, K-convex functions. Note that Dx f (v) ≥ −|∇− f |(x)·|v| clearly holds. Typical examples of K-convex(or K-concave) functions are squared distance functions. We set da (x) := d(a, x) fora, x ∈ X, and denote closed metric balls byB̄a (r) := {x ∈ X : d(a, x) ≤ r},a ∈ X, r > 0.

Proposition 3.3 (Proposition 3.1 in [34]). Let (X, d) be an Alexandrov space withcurvature bounded above by κ > 0. Then, for any a ∈ X, the function d2a is K√
convex on the (geodesically convex) metric ball B̄a (r) with 2r = (π/2 − ²)/ κ and
K = (π − 2²) tan ² for arbitrary ² ∈ (0, π/2).
Proposition 3.4 (Lemma 3.3 in [35]). Let (X, d) be an Alexandrov space with curvature bounded below by κ < 0. Then, for any a ∈ X, the function −d2a is K-convex
on the metric ball B̄a (r) with K = −2(1 − κ(2r)2 ) for all r > 0.
Slightly more generally, we can take a geodesically convex set G ⊂ X with diam G ≤2r in Propositions 3.3, 3.4.
In the lower curvature bound case, by comparing the convexity of f and the concavity of the squared distance function, one can ﬁnd the useful notion of gradientvectors as follows (see [37, 38, 29, 35] for details). Let (X, d) be an Alexandrov spaceof curvature bounded below and f : X → (−∞, ∞] be a lower semi-continuous, Kconvex function. Then, at every x ∈ X with 0 < |∇− f |(x) < ∞, we can ﬁnd theunique direction γ ∈ Σx X such that Dx f (γ) = −|∇− f |(x) and(3.2)

Dx f (η) ≥ −|∇− f |(x)hγ, ηi

DISCRETE-TIME GRADIENT FLOWS IN ALEXANDROV SPACES

9

for all η ∈ Σx X. Thus ∇(−f )(x) := (γ, |∇− f |(x)) ∈ Cx X can be regarded as thegradient vector of −f at x. Set also ∇(−f )(x) := ox if |∇− f |(x) = 0. The gradientvector will be used to deﬁne an appropriate resolvent map for f .
4. Resolvent maps
In this section, we introduce our key tool also appeared in [17, 18, 19, 20], theresolvent map Jλf , to construct discrete-time gradient ﬂows for convex functions. We
will adopt diﬀerent deﬁnitions of Jλf in the upper and lower curvature bound cases.
Throughout the section, let f : X → (−∞, ∞] be a convex, lower semi-continuousfunction not identically +∞, and ﬁx the size λ > 0 of the discrete-time step and aclosed, geodesically convex set G ⊂ X containing a nonempty sublevel set of f .
First, let (X, d) be a complete Alexandrov space with curvature bounded above by√κ. If κ > 0, then we assume diam G < π/(2 κ). In this case, we employ the standard
resolvent map used in, e.g., [18, 30, 2].
Deﬁnition 4.1. [Resolvent map, upper curvature bound case] For each x ∈ X, we
deﬁne
(4.1)

{
Jλf (x) := arg min
y∈G

}
1
2
f (y) + d(x, y) .
2λLemma 4.2. Let (X, d), G and f be as above. Then there exists a unique point y ∈ Gattaining the minimum (4.1).
√
1
Proof. By Proposition 3.3 and diam G < π/(2 κ), the function y 7→ f (y)+ 2λd(x, y)2
is K-convex on G for some K > 0. The rest of the argument can be obtained by astraightforward optimization argument, see for example [2, Lemma 2.4.8].

¤

For any minimal geodesic γ : [0, δ] → G with γ(0) = Jλf (x), we deduce from theﬁrst variation formula (Theorem 2.3) that
(4.2)

DJ f (x) f (γ̇(0)) −λ1hη̇(0), γ̇(0)i ≥ 0,
λwhere η : [0, 1] → X is any minimal geodesic from Jλf (x) to x.
Next we consider the lower curvature bound case. In this setting, the deﬁnition
provided by (4.1) for Jλf (x) is not convenient, because the squared distance function
is no longer convex, but is concave instead. This concavity leads to, however, the10SHIN-ICHI OHTA AND MIKLÓS PÁLFIA

advantage of well deﬁned gradient vectors of −f . Then we shall deﬁne the resolvent
map by using an “exponential map” from Cx X to X. Although we can not simply use
geodesics since there may be no geodesic with a given initial direction, the gradientcurves of the convex function −d2x will do the job.
Let (X, d) be a complete, ﬁnite dimensional Alexandrov space of curvature bounded
below by κ with ∂X = ∅. Note that, even for κ < 0, the function −d2x is K-convex
on balls B̄x (r) for some K = K(κ, r) < 0 by Proposition 3.4. Hence we can construct
the gradient ﬂow Φ : [0, ∞) × X → X of −d2x , i.e., each curve ξ(t) = Φ(t, y) satisﬁes
˙ = ∇(d2 )(ξ(t)) at almost all t > 0. The convexity of −d2 ensures the uniqueness
ξ(t)
x

x

and contraction of Φ, see [37, 38]. The gradient exponential map g-expx : Cx X → X
is obtained by a re-parametrized scaling of Φ: Deﬁne g-expx as the limit of the mapΦ(s, ·) ◦ idX : (X, es d) → (X, d)
as s → ∞, where es d is the scaled distance and idX : (X, es d) → (X, d) is the identity
map. The gradient exponential map enjoys many nice properties, for instance, thecurve ξ(t) = g-expx (tv) satisﬁes
(4.3)

˙
ξ(0)
= v,

˙ = d(x, ξ(t)) ∇dx (ξ(t)),ξ(t)
td(x, ξ(t)) ≤ t|v|.

Moreover, the following useful comparison estimate holds.
Lemma 4.3 (Lemma 3.1.2 in [38]). Put ξ(t) = g-expx (tv) with v ∈ Cx X. Then, forany (−K)-convex function h : X → R with K ≥ 0 and all t > 0, we haveh(ξ(t)) ≥ h(x) + tDx h(v) −K(t|v|)2 .
2Remark 4.4. The gradient ﬂow Φ of −d2x can be constructed also in proper, inﬁnite
dimensional Alexandrov spaces (see [37, Appendix] and [29, 35]). However, the proof
of Lemma 4.3 above in [38] essentially requires both dim X < ∞ and ∂X = ∅.
One may consult the argument in [37, Appendix] proving an estimate comparable toLemma 4.3 (called the monotonicity there) along gradient curves parametrized in adiﬀerent way. However, these curves may be deﬁned only on small intervals.
We are ready to deﬁne the resolvent map under lower curvature bound. We abuse
the same notation Jλf (x) as the upper curvature bound case.

DISCRETE-TIME GRADIENT FLOWS IN ALEXANDROV SPACES

11

Deﬁnition 4.5. [Resolvent map, lower curvature bound case] For x ∈ X with|∇− f |(x) < ∞, we deﬁne
Jλf (x) := g-exp(λ∇(−f )(x)),(4.4)

where ∇(−f ) ∈ Cx X is the gradient vector of −f at x given in Section 3.
The following estimates will play crucial roles in the next section.
Lemma 4.6. Let (X, d) be a complete Alexandrov space either with curvature bounded
above or below by κ.
(I) If (X, d) has curvature bounded above by κ > 0, then also assume diam G <√π/(2 κ). Then we haved(y, Jλf (x))2 ≤ d(y, x)2 − 2λ[f (Jλf (x)) − f (y)](4.5)

for all x, y ∈ G.
(II) In the lower curvature bound case, we assume that X is ﬁnite dimensional,∂X = ∅, and that diam G < ∞ if κ < 0. Then we have
(4.6)

d(y, Jλf (x))2 ≤ d(y, x)2 − 2λ[f (x) − f (y)] +K(λ|∇− f |(x))22

for all x, y ∈ G satisfying Jλf (x) ∈ G, where K = K(κ, diam G) ≥ 0.
Proof. (I) By assumption, the squared distance function is convex (Proposition 3.3).
Hence, by Theorem 2.3,d(y, x)2 ≥ d(y, Jλf (x))2 − 2 hγ̇(0), η̇(0)i√for γ(t) = Jλf (x)#t y and η(t) = Jλf (x)#t x (they are unique since diam G < π/(2 κ)).
Combine this with (4.2) to get(4.7)

d(y, Jλf (x))2 ≤ d(y, x)2 + 2λDJ f (x) f (γ̇(0)).
λ

Now the convexity of f along γ yields that DJ f (x) f (γ̇(0)) ≤ f (y) − f (Jλf (x)), so we
λget from (4.7) thatd(y, Jλf (x))2 ≤ d(y, x)2 − 2λ[f (Jλf (x)) − f (y)].

12SHIN-ICHI OHTA AND MIKLÓS PÁLFIA(II) Put ξ(λ) := g-exp(λ∇(−f )(x)). By Proposition 3.4, the function −d2y is (−K)convex on G for some K = K(κ, diam G) ≥ 0. Thus Lemma 4.3 shows thatd(y, ξ(λ))2 ≤ d(y, x)2 + λDx (d2y )(∇(−f )(x)) +K(λ|∇− f |(x))2 .
2Fixing arbitrary minimal geodesic γ(t) = x#t y, we deduce from the ﬁrst variation
formula (Theorem 2.3) and (3.2) thatDx (d2y )(∇(−f )(x)) ≤ −2hγ̇(0), ∇(−f )(x)i ≤ 2Dx f (γ̇(0)).
Finally the convexity of f shows that f (y) ≥ f (x) + Dx f (γ̇(0)). Therefore we obtaind(y, Jλf (x))2 ≤ d(y, x)2 − 2λ[f (x) − f (y)] +K(λ|∇− f |(x))2 .
2¤

5. Proximal and sub-gradient methods
The resolvent map Jλf can be used to consider proximal point algorithms or, inother words, discrete-time gradient ﬂows for general convex functions in the upper
curvature bound case. We start with a basic result that generalizes the one in [5]given in NPC spaces. The algorithm has been used at many places, one of the ﬁrst
occasions was in [12]. The situation is the same as Lemma 4.6(I).
Theorem 5.1. Let (X, d) be a complete Alexandrov space with curvature bounded
above by κ. Let f : X → (−∞, ∞] be a convex, lower semi-continuous function andG ⊂ X be a closed, geodesically convex set containing a sublevel set of f such that∑√diam G < π/(2 κ) if κ > 0. Take a positive sequence {λk }k≥1 with ∞k=1 λk = +∞.
Fix an arbitrary starting point x0 ∈ G and put
xk := Jλfk (xk−1 ),k ≥ 1.

Then we have limk→∞ f (xk ) = inf y∈G f (y).
Proof. By the deﬁnition (4.1) of Jλf , the sequence f (xk ) is monotone non-increasing.
Indeed, we havef (Jλfk+1 (xk )) +1d(xk , Jλfk+1 (xk ))2 ≤ f (xk ).
2λk+1

DISCRETE-TIME GRADIENT FLOWS IN ALEXANDROV SPACES

13

Furthermore, by (4.5) in Lemma 4.6, we have for any y ∈ Gd(y, xk+1 )2 ≤ d(y, xk )2 − 2λk+1 [f (xk+1 ) − f (y)].
This combined with the monotonicity of f (xk ) yields
2[f (xk ) − f (y)]

k
∑
i=1

λi ≤ 2k∑

λi [f (xi ) − f (y)] ≤ d(y, x0 )2 − d(y, xk )2 ,i=1

which givesf (xk ) − f (y) ≤d(y, x0 )2.
∑
2 ki=1 λi

By the choice of λk , this implies that limk→∞ f (xk ) ≤ f (y) for any y ∈ G. Therefore
we obtain limk→∞ f (xk ) = inf y∈G f (y).

¤Remark 5.2. Weak convergence in Alexandrov spaces with upper curvature bounds
has been introduced in [14] which generalized this notion given for NPC spaces by Jostin [17]. The same results for weak convergence as in NPC spaces hold if we restrict√
the analysis to closed metric balls of diameter at most π/(2 κ). Hence actually one
can prove weak convergence to a minimizer (if it exists) in Theorem 5.1 in the same
way as in [5] for NPC spaces. Furthermore, if f is K-convex with K > 0, then we
have (strong) convergence to the unique minimizer y.
In the rest of this section, we set up a discrete-time gradient ﬂow converging to aminimizer of a convex function that is the sum of ﬁnitely many convex functions. We
adjust the setting of Lemma 4.6 to admit such sum of functions.
Deﬁnition 5.3. [Proximal Point Algorithm] Let (X, d) be a complete Alexandrov
space either with curvature bounded above or below by κ, and G ⊂ X be a closed,
geodesically convex set satisfying the following:√(I) In the upper curvature bound case, diam G < π/(2 κ) if κ > 0;(II) In the lower curvature bound case, dim X < ∞, ∂X = ∅, and diam G < ∞ if
κ < 0.
Let fi : G → (−∞, ∞] be a convex, lower semi-continuous function for i = 1, . . . , n.
∑
Set f (x) := ni=1 fi (x) and suppose that it is not identically +∞. Take a positive

14

SHIN-ICHI OHTA AND MIKLÓS PÁLFIA

sequence λk > 0 such that∑∞k=0 λk = +∞ and also∑∞2
k=0 λk < +∞.

Given x0 ∈ G

and for each k ≥ 0 and 1 ≤ i ≤ n, we set
xkn+i := Jλfki (xkn+i−1 ),where the resolvent map is deﬁned by (4.1) or (4.4), assuming that xm ∈ G for allm ≥ 0 in the lower curvature bound case.
Before turning to our result on the convergence of the sequences generated in
Deﬁnition 5.3, we state an elementary lemma from [9, Lemma 3.4] for later use.
Lemma 5.4. Let ak , bk , ck ≥ 0 be sequences such that ak+1 ≤ ak −bk +ck for any k ≥ 1,∑∑∞
and assume ∞k=1 ck < ∞. Then the sequence ak converges and also
k=1 bk < ∞.
∑Theorem 5.5. Let (X, d), G ⊂ X, f = ni=1 fi and {λk }k≥0 be as in Deﬁnition 5.3.
Assume further that X is locally compact, fi is L-Lipschitz for some L ≥ 1 and all i,and that inf G f is attained at some point. Then xm converges to some minimizer off in G as m → ∞.
Proof. Fix a minimizer y ∈ G of f .
Upper curvature bound case (I): By (4.5) in Lemma 4.6, we haved(y, xkn+i )2 ≤ d(y, xkn+i−1 )2 − 2λk [fi (xkn+i ) − fi (y)].
Summing the above for 1 ≤ i ≤ n impliesd(y, xkn+n ) ≤ d(y, xkn ) − 2λk
2

2

n
∑

[fi (xkn+i ) − fi (y)],i=1which is equivalent to(5.1) d(y, xkn+n ) ≤ d(y, xkn ) −2λk22The next step is to estimate

∑n

n
∑
i=1

[fi (xkn )−fi (y)]+2λkn∑[fi (xkn )−fi (xkn+i )].

i=1

i=1 [fi (xkn ) − fi (xkn+i )] from above. By (4.1), for any

1 ≤ j ≤ n, we have1d(xkn+j , xkn+j−1 )2 ≤ fj (xkn+j−1 ),2λkwhich yields by using the L-Lipschitz continuity thatfj (xkn+j ) +d(xkn+j , xkn+j−1 ) ≤ 2λk

fj (xkn+j−1 ) − fj (xkn+j )≤ 2λk L.
d(xkn+j , xkn+j−1 )DISCRETE-TIME GRADIENT FLOWS IN ALEXANDROV SPACES

Since d(xkn , xkn+i ) ≤15∑i

j=1 d(xkn+j−1 , xkn+j ), this gives also thatd(xkn , xkn+i ) ≤ 2λk Li.

(5.2)
Furthermore, we haven∑[fi (xkn ) − fi (xkn+i )] =

i=1

n ∑
i
∑

[fi (xkn+j−1 ) − fi (xkn+j )]i=1 j=1

≤

n ∑
i
∑

Ld(xkn+j , xkn+j−1 )i=1 j=1≤n∑2λk L2 i = λk L2 n(n + 1).

i=1This combined with (5.1) yields(5.3)

d(y, xkn+n ) ≤ d(y, xkn ) − 2λk
2

2

n
∑

[fi (xkn ) − fi (y)] + 2λ2k L2 n(n + 1).

i=1

Since f (xkn ) − f (y) ≥ 0, Lemma 5.4 implies that the sequence ak := d(y, xkn )2
converges andHence, by the∞∑λk [f (xkn ) − f (y)] < +∞.

k=0∑∞
assumption
k=0 λk= +∞, there exists a subsequence xkl n suchthat liml→∞ f (xkl n ) = f (y). Since xkl n is bounded, by local compactness it has asubsequence converging to a point z ∈ G, which by lower semicontinuity of f must bea minimizer of f . Then, by replacing y with z in the above discussion, the sequence
ak = d(z, xkn )2 is convergent and has a subsequence converging to 0. Hence the whole
sequence ak converges to 0, i.e., xkn → z as k → ∞. Moreover, (5.2) givesd(z, xkn+i ) ≤ d(z, xkn ) + d(xkn , xkn+i ) ≤ d(z, xkn ) + 2λk Li∑
2for all 1 ≤ i ≤ n. Since we have λk → 0 by ∞k=0 λk < +∞, we conclude that
xkn+i → z as k → ∞ for all i. Therefore xm → z as m → ∞.
Lower curvature bound case (II): The proof is similar to Case (I). From (4.6) inLemma 4.6, we getd(y, xkn+i )2 ≤ d(y, xkn+i−1 )2 − 2λk [fi (xkn+i−1 ) − fi (y)] +

K 2 2
λ L.
2 k

16

SHIN-ICHI OHTA AND MIKLÓS PÁLFIA

Summing the above for 1 ≤ i ≤ n yields
d(y, xkn+n )2 ≤ d(y, xkn )2 − 2λkn∑[fi (xkn+i−1 ) − fi (y)] +

i=1

K 2 2
λ L n,
2 kwhich is equivalent tod(y, xkn+n )2 ≤d(y, xkn )2 − 2λkn∑[fi (xkn ) − fi (y)]

i=1

(5.4)
+ 2λk

n
∑

[fi (xkn ) − fi (xkn+i−1 )] +

i=1

K 2 2
λ L n.
2 k

We ﬁnd by (4.3) and assumption that d(xkn+i−1 , xkn+i ) ≤ λk L, and hencefi (xkn ) − fi (xkn+i−1 ) ≤ Ld(xkn , xkn+i−1 ) ≤ L

i−1∑

d(xkn+j−1 , xkn+j ) ≤ λk L2 (i − 1).

j=1

Then these bounds combined with (5.4) gived(y, xkn+n ) ≤ d(y, xkn ) − 2λk
2

2

n
∑

(
[fi (xkn ) − fi (y)] + λ2k L2 ni=1

The rest of the argument is identical to Case (I).

)
K
+n−1 .
2¤

Remark 5.6. In the lower curvature bound case (II), the assumption that xm ∈ G
can be met, since d(y, xm ) is bounded as we saw in the proof. Thus, choosing thesequence λk appropriately, we can assure that xm stays inside G.
The above theorem relies on local compactness. In fact, it is known that in theinﬁnite dimensional case we cannot always have convergence under these assumptions[6]. However, if we assume that f is K-convex for positive K, then the assumptionof local compactness can be dropped.
Proposition 5.7. Let (X, d), G ⊂ X, f =∑ni=1 fi be as in Deﬁnition 5.3 and further

assume that fi is L-Lipschitz for some L ≥ 1 and all i, and that f is K-convex for∑some K > 0. Take λk > 0 with λk K < 1, λk → 0 and ∞k=0 λk = +∞, and consider
a sequence {xm }m≥0 generated by Deﬁnition 5.3. Then xm converges to the uniqueminimizer y ∈ G of f as m → ∞.

DISCRETE-TIME GRADIENT FLOWS IN ALEXANDROV SPACES

17

More concretely, in the upper curvature bound case, d(xkn , y)2 ≤ ak holds with
a0 := d(x0 , y)2 and ak+1 := (1 − λk K)ak + 2λ2k L2 n(n + 1) inductively, that is,k∏ak+1 =(1 − λi K)a0 + 2L n(n + 1)
2

i=0

k
∑

(λ2j−1j=1k∏(1 − λi K) + λ2k ).
i=j

In the lower curvature bound case, d(xkn , y)2 ≤ ak similarly holds for a0 := d(x0 , y)20

and ak+1 := (1 − λk K)ak + λ2k L2 n( K2 + n − 1) with K 0 = K 0 (κ, diam G) ≥ 0 given in
Lemma 4.6(II). Also
ak+1 =

k∏((1 − λi K)a0 + L n

i=0

2

)∑
k
k
∏
K0
2
(λj−1 (1 − λi K) + λ2k )
+n−1
2
j=1
i=j

in this case.
Proof. Thanks to the K-convexity with K > 0 and the completeness of (X, d), there
is a unique minimizer y ∈ G of f (see, e.g., [2, Lemma 2.4.8]). For any x ∈ G, bydividing (3.1) with 1 − t and letting t → 1, we haveKd(x, y)2 ≤ f (x) − f (y).
2
Let us consider Case (I), the proof of Case (II) will be similar. By (5.3), we have

(5.5)

d(y, xkn+n )2 ≤ d(y, xkn )2 − 2λk [f (xkn ) − f (y)] + 2λ2k L2 n(n + 1).
Using (5.5), we get(5.6)

d(y, xkn+n )2 ≤ (1 − λk K)d(y, xkn )2 + 2λ2k L2 n(n + 1).

Then by induction it is easy to see that d(xkn , y)2 ≤ ak . The explicit formula for ak+1
is proved also by induction.
Now we prove lim inf k→∞ ak = 0 by contradiction. Assume that there are N ≥ 0
and c > 0 such that, for every k > N , we have ak > c and 2L2 n(n + 1)λk < cK/2.
Then
λk cK
,
ak+1 = ak + λk (2L2 n(n + 1)λk − ak K) ≤ ak −2∑which is a contradiction, since ∞k=0 λk = +∞. We ﬁnally show limk→∞ ak = 0. If
ak > 2L2 n(n + 1)λk /K, then clearly ak+1 < ak . If ak ≤ 2L2 n(n + 1)λk /K, thenak+1 ≤ (1 − λk K)(2L2 n(n + 1)λk /K) + 2λ2k L2 n(n + 1) = 2L2 n(n + 1)λk /K.

18

SHIN-ICHI OHTA AND MIKLÓS PÁLFIA

Thus we haveak+1 ≤ max{ak , 2L2 n(n + 1)λk /K},
from which we get, for any l ≥ k,{}
al+1 ≤ max ak , (2L2 n(n + 1)/K) · max{λk , λk+1 , . . . , λl } .
Take lim supl→∞ and then lim inf k→∞ of the above to see that ak → 0. The convergence of the rest of the sequence d(xm , y)2 to 0 follows from setting up a similar¤inequality of the form (5.2).
For the explicit convergence rate analysis, let us quote a lemma from [32]:Lemma 5.8. Let ak ≥ 0 be a sequence such that()αβ
ak+1 ≤ 1 −
ak +
,
k+1
(k + 1)2where α, β > 0. Then

ak ≤


(
)
2α β(2−α)
1

a
+

0
α
1−α

 (k+2)

β(1+log(k+1))
k+11(α−1)(k+2)(

0 −ββ + (α−1)a(k+2)α−1

if 0 < α < 1;)

if α = 1;
if α > 1.

From this we obtain that the convergence is sublinear in Proposition 5.7.
6. Law of large numbers and Jensen’s inequality
In this section, we give a stochastic discrete-time gradient ﬂow for arbitrary convex(inﬁnite) combinations of convex functions. We will restrict ourselves to K-convex
functions with K > 0, however, our proofs can be adapted to the case K = 0
in the same manner as we have seen in Theorem 5.5, which is a generalized formof Proposition 5.7 in this sense. We will adopt, and generalize the notations of[43, 44] given for measures supported only over the squared distance functions fa (x) :=d(x, a)2 .
Let G ⊂ X be a closed, geodesically convex set. We assume that (G, d) is separable.
Consider the set of all lower semi-continuous, convex functions f : G → (−∞, ∞] not
identically +∞, denoted by F (G). For K > 0, we denote by FK (G) the subsetof all lower semi-continuous, K-convex functions f : G → (−∞, ∞] not identicallyDISCRETE-TIME GRADIENT FLOWS IN ALEXANDROV SPACES

19+∞. In order to consider measures over FK (G), we must equip F (G) with a σalgebra. There are diﬀerent ways to do this, however there is a natural topology
on F (G) that is obtained by associating every function f ∈ F (G) with its epigraphepi(f ) := {(x, α) ∈ G × (−∞, +∞] : α ≥ f (x)}. It is known that f is convex lower
semi-continuous if and only if epi(f ) is a closed convex set of (G × (−∞, +∞]) whichitself is equipped with the product topology. The construction of the topology weadopt is a standard one in stochastic variational analysis, we refer to the book [40],where instead of an arbitrary Polish space X, only ﬁnite dimensional Euclidean spaces
are considered, however the theory carries over without modiﬁcations to the generalcase, as can be seen in [24] for example.
The set of closed convex sets of (G×(−∞, +∞]) is denoted by clc(G×(−∞, +∞]).
The Eﬀrös-ﬁeld on clc(G × (−∞, +∞]) is the σ-ﬁeld E(G × (−∞, +∞]) generated
by all sets of the form
EO = {C ∈ clc(G × (−∞, +∞]) : C ∩ O 6= ∅},O ⊆ G × (−∞, +∞],

open.

The topology on F (G) is then generated by the topology on clc(G×(−∞, +∞]) givenby the σ-ﬁeld E(G × (−∞, +∞]) which is itself generated by the Fell or ChoquetWijsman hyperspace topologies, see [24] and the references therein. The resulting
σ-ﬁeld on F (G) is denoted by E. It is known that E is generated by sets of the form{}
E(O,α) = f ∈ F (G) : inf f < α , O ⊆ G, open, α ∈ R,O

see [24], it corresponds to a topology of one-sided uniform convergence. Now we
can consider measures on (FK (G), E), i.e. random lower semi-continuous K-convex
functions on G. Let (Π, A, µ) be a complete probability space. Then a map L :Π → FK (G) is a random lower semi-continuous (K-)convex function if the bivariatemap (Π, G) → L(a, x) is A ⊗ B(X)-measurable where B(X) denotes the Borel σalgebra of (G, d). Equivalently L : Π → FK (G) is a random lower semi-continuous(K-)convex function if the associated epigraphical mapping SL (a) := epi L(a, ·) ={(x, α) ∈ G × R : α ≥ L(a, x)} is E(G × (−∞, +∞]) measurable as a closed convex
set valued mapping, see Proposition 14.34 in [40].
A very useful consequence of the measurability of L : Π → FK (G) is the following:

20

SHIN-ICHI OHTA AND MIKLÓS PÁLFIA
L(a)Lemma 6.1. The resolvent map Π 7→ Jλ(x) deﬁned by (4.1) for ﬁxed x ∈ G, asa map Π → X, is closed-valued and A-measurable as a set-valued map, moreoverL(a)Π 7→ L(a, Jλ(x)), as a map Π → R is also A-measurable.
¤

Proof. See Theorem 14.37 in [40].

Also by the measurable projection theorem we have that for ﬁxed x ∈ G the map
L(·, x) : Π → (−∞, +∞] is A-measurable, see Proposition 14.28 in [40]. What follows∫
is that the integral f (x) = Π L(a, x)dµ(a) pointwisely deﬁnes an extended real-valued
function f : G → [−∞, +∞].
Lemma 6.2. The function f : G → [−∞, +∞] deﬁned as f (x) :=∫Π

L(a, x)dµ(a)is lower semi-continuous K-convex and f (x) > −∞ for all x ∈ G if there exists
an integrable function α0 : Π → (−∞, +∞) such that L(a, x) ≥ α0 (a) holds almost
surely.
Proof. The lower boundedness of f is clear under the last part of the assumption.
To prove the ﬁrst part, let xk ∈ G be a sequence such that xk → x. We∫∫
have f (x) = Π L(a, x)dµ(a) and f (xk ) = Π L(a, xk )dµ(a). For ﬁxed a ∈ Π bylower semi-continuity we have L0 (a, x) := limxk →x L(a, xk ) ≥ L(a, x). Hence, by∫∫monotonicity of the Lebesgue-integral we get Π L0 (a, x)dµ(a) ≥ Π L(a, x)dµ(a).
∫∫Then by Fatou’s lemma we get Π L0 (a, x)dµ(a) ≤ lim inf k→∞ Π L(a, xk )dµ(a), hence
f (x) ≤ lim inf k→∞ f (xk ) proving the lower semi-continuity. Now the K-convexityof f is obtained by integrating the inequality (3.1) given for x 7→ L(a, x) for ﬁxeda ∈ Π.

¤

With the above setup at hand, instead of always emphasizing the complete probability space (Π, A, µ), we assume directly that Π := FK (G), A := E and µ is a complete
probability measure on (Π, A). By the deﬁnition of a random lower semi-continuous
K-convex function it follows that the map (Π, G) → L(a, x) is A ⊗ B(X)-measurable,
see Exercise 14.9 in [40], hence the above machinery applies. For simplicity we denote by P(FK (G)) the set of all complete probability measures on FK (G) with σ-ﬁeld∫
A = E, such that g(x) := FK (G) f (x)dµ(f ) is lower semi-continuous (−∞, +∞]valued K-convex and there exists x ∈ G so that g(x) < +∞.

DISCRETE-TIME GRADIENT FLOWS IN ALEXANDROV SPACES

21

Deﬁnition 6.3. [Variance] We deﬁne the variance of µ ∈ P(FK (G)) by∫var(µ) := inf
f (x)dµ(f ).
x∈G

FK (G)

This contains as a special case the original deﬁnition of the variance given by∫var(ν) := inf x∈G G d(x, a)2 dν(a) in [43, 44] for a probability measure ν supported
over G.
A ﬁxed µ ∈ P(FK (G)) can be viewed as the distribution of an FK (G)-valued
random variable. In this sense, integration with respect to µ can be viewed as taking
expectations:

∫
Eϕ :=

ϕ(f )dµ(f ),FK (G)

where ϕ : FK (G) → [−∞, +∞] is assumed to be measurable.
Deﬁnition 6.4. [Expectation] Let µ ∈ P(FK (G)). We deﬁne the expectation of µ as∫
f (x)dµ(f ),Eµ := arg minx∈G

FK (G)

which is indeed uniquely determined by the K-convexity of g(x) =∫FK (G)

f (x)dµ(f ).

The above is motivated by the deﬁnition given in [43, 44] of the expectation as∫Eν := arg minx∈G G d(x, a)2 dν(a) of a probability measure ν supported over G.
Note that g(Eµ) = var(µ). Using our new notation, we have a generalization of thevariance inequality in [44, Proposition 4.4] as well (see also [45, 36] for the reverse
variance inequality for squared distance functions under lower curvature bounds). Let
Lx denote the evaluation operator at x ∈ G deﬁned as Lx f := f (x). Clearly Lx is alinear functional on the cone FK (G).
Proposition 6.5 (Variance inequality). Let µ ∈ P(FK (G)). Then, for all x ∈ G, we
have

∫
2
2
(6.1)
d(x, Eµ) ≤ E (Lx − LEµ ) =[f (x) − f (Eµ)]dµ(f ).
K
K FK (G)∫Proof. Put g(x) = FK (G) f (x)dµ(f ) and note that g(Eµ) = inf G g. Then the claim
2

follows from (5.5).

¤

22

SHIN-ICHI OHTA AND MIKLÓS PÁLFIA

Remark 6.6. Lemma 6.1 ensures us that, in the case of upper curvature bound, thenonnegative real-valued map f 7→ d(y, Jλf (x))2 is measurable for any x, y ∈ G, i.e.
∫
(6.2)
d(y, Jλf (x))2 dµ(f )FK (G)

exists. In the case of lower curvature bound, the measurability of f 7→ d(y, Jλf (x))2 is
nontrivial and veriﬁed only in special cases. If µ is ﬁnitely supported, then measurability is clear. Also if X is a Euclidean space and µ is supported over diﬀerentiable
functions, then the measurability follows from the continuity of the gradient vectorsof convex functions, see Theorem 25.7 in [39].
In the following, we prove a stochastic variant of Proposition 5.7, which extends
the law of large numbers proved in [44, Theorem 4.7] to the case of Alexandrov spaces
with arbitrary upper or lower curvature bounds, and arbitrary Lipschitz functions in
FK (G).
Theorem 6.7 (Law of large numbers). Let (X, d) and G ⊂ X be as in Deﬁnition 5.3. Fix µ ∈ P(FK (G)) supported on L-Lipschitz functions and let {fk }k≥0denote a sequence of independent, identically distributed random variables taking values in FK (G) with distribution µ. Take a positive sequence {λk }k≥0 with λk K < 1,∑
λk → 0 and ∞k=0 λk = +∞. Deﬁne the sequence Sk ∈ G recursively as
Sk+1 := Jλfkk (Sk ),k ≥ 0,

with an arbitrary starting point S0 ∈ G, assuming that Sk ∈ G for all k ≥ 0 and
the integral in (6.2) exists in the lower curvature bound case. Then Sk → Eµ almost
surely.
Proof. We prove only the upper curvature bound case, the lower curvature boundcase is similar. By (4.5) in Lemma 4.6, we haved(y, Jλfkk (x))2 ≤ d(y, x)2 − 2λk [fk (Jλfkk (x)) − fk (y)]for all x, y ∈ G. Therefore we have(6.3) d(Eµ, Sk+1 )2 ≤ d(Eµ, Sk )2 − 2λk [fk (Sk ) − fk (Eµ)] + 2λk [fk (Sk ) − fk (Sk+1 )].

DISCRETE-TIME GRADIENT FLOWS IN ALEXANDROV SPACES

23

By (4.1), we havefk (Sk+1 ) +1d(Sk+1 , Sk )2 ≤ fk (Sk ),2λkwhich yields by using the L-Lipschitz continuity thatd(Sk+1 , Sk ) ≤ 2λk

fk (Sk ) − fk (Sk+1 )≤ 2λk L.
d(Sk+1 , Sk )Thus we obtainfk (Sk ) − fk (Sk+1 ) ≤ Ld(Sk+1 , Sk ) ≤ 2λk L2 .
This combined with (6.3) yields
d(Eµ, Sk+1 )2 ≤ d(Eµ, Sk )2 − 2λk [fk (Sk ) − fk (Eµ)] + 4λ2k L2 .
Taking expectations in fk conditioned on Fk−1 := {f1 , . . . , fk−1 } and using the variance inequality (6.1), we get()
E d(Eµ, Sk+1 )2 |Fk−1 ≤ d(Eµ, Sk )2 − 2λk E[fk (Sk ) − fk (Eµ)] + 4λ2k L2≤ d(Eµ, Sk )2 − λk Kd(Eµ, Sk )2 + 4λ2k L2 ,and hence()
E d(Eµ, Sk+1 )2 |Fk−1 ≤ (1 − λk K)d(Eµ, Sk )2 + 4λ2k L2 .
Taking expectations again yields
Ed(Eµ, Sk+1 )2 ≤ (1 − λk K)Ed(Eµ, Sk )2 + 4λ2k L2 .
From here proving the convergence Ed(Eµ, Sk+1 )2 → 0 can be done in the same way
as in the proof of Proposition 5.7 after (5.6). To get a convergence rate estimate, one
can refer to Lemma 5.8.

¤

Remark 6.8. Suppose that (X, d) has curvature bounded above by κ > 0. Fix√
arbitrary o ∈ X and let G := B̄o (r) with 2r = (π/2 − ²)/ κ for ² ∈ (0, π/2).
Then, by Proposition 3.3, the function fa (x) := d(a, x)2 with a ∈ G is K-convex and
Lipschitz continuous on G with K = (π − 2²) tan ² > 0. Take µ ∈ P(FK (G)) suchthat supp µ ⊂ {fa : a ∈ G}. Then Theorem 6.7 generalizes Sturm’s law of large

24SHIN-ICHI OHTA AND MIKLÓS PÁLFIA

1, then we havenumbers in [43, 44]. In particular, if λk := 2k{}d(z, Sk )2
fk
2
Sk+1 = Jλk (Sk ) = arg min d(ak , z) +
2λk
z∈G
{
}
2λk
1
2
2
= arg mind(ak , z) +d(z, Sk )1 + 2λk
1 + 2λkz∈G= Sk # 1 a k ,k+1

where ak is a G-valued random variable with distribution provided by the pushforward measure of µ under the bijective map fa 7→ a. In this case, one can reproduce
the same sublinear order of convergence O(1/k) as in [44]. More generally, one canconsider fa (x) := d(x, a)p for any p ∈ [2, ∞), still fa (x) being K-convex and Lipschitz
continuous on the same G, hence Theorem 6.7 can be applied.
Under these assumptions if µ is also ﬁnitely supported, then our Proposition 5.7
extends the “no dice” approximation given only for the barycenter on NPC spaces in[28, 16].
It seems reasonable to expect that, in the upper curvature bound case in Re√
mark 6.8, one can take any 2r < π/ κ even though the functions fa are then notconvex on whole G. This is motivated by the results in [1] on the existence anduniqueness of the center of mass in Riemannian manifolds.
Remark 6.9. Theorem 6.7 generalizes the law of large numbers from Euclidean
spaces to Alexandrov spaces, moreover, to the case of measures supported over thecone of K-convex Lipschitz functions. We recover the original law of large numbers
in Hilbert spaces by choosing X to be a Hilbert space in Remark 6.8. Also the setting
in Remark 6.8 is of interest if we choose X to be a sphere, or any compact Lie groupwith a bi-invariant Riemannian metric, for instance the matrix Lie group of rotations SO(H) studied in [31] or unitary tranformations U(H) over a ﬁnite dimensional
Hilbert space H.
Using our law of large numbers, we have an alternative proof for Jensen’s inequalityof Kuwae [25], along the line of the second proof of [44, Theorem 6.2] in the NPC
space case.

DISCRETE-TIME GRADIENT FLOWS IN ALEXANDROV SPACES

25

Proposition 6.10 (Jensen’s inequality). Let X be a complete Alexandrov space withcurvature bound above by κ > 0, and G ⊂ X be a closed, geodesically convex set√
with diam G < π/(2 κ). Take a probability measure µ on G and a convex, lower
semi-continuous function f : G → R. Then we havef (Eµ) ≤ Ef,∫∫
where Eµ := arg miny∈G G d(a, y)2 dµ(a) and Ef := G f (a)dµ(a).
Proof. Choose a sequence of independent, identically distributed random variables Yk
with values in G, and with distribution µ. Let Sk ∈ G be deﬁned as in Remark 6.8,
i.e., S1 := Y1 and Sk+1 := Sk # 1 Yk+1 . Similarly, let Zk ∈ R be deﬁned as Z1 := f (Y1 )k+1

and Zk+1 := Zk # 1 f (Yk+1 ). We can explicitly write as
k+1

Zk+1 = Zk # 1 f (Yk+1 ) =
k+1

k
1
Zk +
f (Yk+1 ).
k+1
k+1

By Theorem 6.7, we have Sk → Eµ and Zk → E(f∗ µ) = Ef , where f∗ µ denoted thepush-forward of µ. We proceed by induction showingf (Sk ) ≤ Zk .

(6.4)

For k = 1, this clearly holds. For general k ≥ 1, we have by inductionf (Sk+1 ) = f (Sk # 1 Yk+1 )
k+1

k
1
≤
f (Sk ) +f (Yk+1 )
k+1
k+1
k
1
Zk +
f (Yk+1 ) = Zk+1
≤
k+1
k+1
showing (6.4). Hence, by the lower semi-continuity of f , we obtainf (Eµ) ≤ lim inf f (Sk ) ≤ lim inf Zk = Ef
k→∞

k→∞

¤

and complete the proof.
Acknowledgment

The authors would like to thank the anonymous referee for his valuable comments,
in particular improving the discussion in section 6.

26

SHIN-ICHI OHTA AND MIKLÓS PÁLFIA

The second author would like to thank Prof. John Holbrook for raising his attention
to the approximation problem of the barycenter treated in Remark 6.8 on the sphere.
The second author had doubts in the convergence of such approximation scheme in
the positive curvature case, but then he learned about the favorable outcomes ofProf. Holbrook’s numerical experiments on the sphere in a private communication
with him, which initiated the further study of the problem.

References[1] B. Afsari, Riemannian Lp center of mass: Existence, uniqueness, and convexity, Proc. Amer.
Math. Soc. 139 (2011), 655–673.
[2] L. Ambrosio, N. Gigli and G. Savaré, Gradient ﬂows in metric spaces and in the space of
probability measures. Second edition, Birkhäuser Verlag, Basel, 2008.
[3] M. Arnaudon and X. M. Li, Barycenters of measures transported by stochastic ﬂows, Ann.
Probab. 33 (2005), 1509–1543.
[4] M. Arnaudon, C. Dombry, A. Phan and L. Yang, Stochastic algorithms for computing meansof probability measures, Stochastic Process. Appl. 122 (2012), 1437–1455.
[5] M. Bačák, The proximal point algorithm in metric spaces, Israel J. Math. 194 (2013), 689–701.
[6] M. Bačák, Computing means and medians in Hadamard spaces, to appear in SIAM J. Optim.
(2014). Available at arXiv:1210.2145.
[7] G. C. Bento and J. X. Cruz Neto, Finite termination of the proximal point method for convex
functions on Hadamard manifolds, Optimization (2012), DOI:10.1080/02331934.2012.730050.
[8] D. P. Bertsekas, Incremental proximal methods for large scale convex optimization, Math.
Program., Ser. B 129 (2011), 163–195.
[9] D. P. Bertsekas and J. N. Tsitsiklis, Neuro-Dynamic Programming, Athena Scientiﬁc, 1996.
[10] R. Bhatia, Positive deﬁnite matrices, Princeton Series in Applied Mathematics, Princeton University Press, Princeton, NJ, 2007.
[11] R. Bhatia and J. Holbrook, Riemannian geometry and matrix geometric means, Linear AlgebraAppl. 413 (2006), 594–618.
[12] H. Brézis and P.-L. Lions, Produits inﬁnis de rèsolvantes, Israel J. Math. 29 (1978), 329–345.
[13] D. Burago, Yu. Burago and S. Ivanov, A course in metric geometry, American MathematicalSociety, Providence, RI, 2001.
[14] R. Espı́nola and A. Fernández-León, CAT(k)-spaces, weak convergence and ﬁxed points, J.
Math. Anal. Appl. 353 (2009), 410–427.
[15] O. P. Ferreira and P. R. Oliveira, Proximal Point Algorithm On Riemannian Manifolds, Optimization 51 (2002), 257–270.

DISCRETE-TIME GRADIENT FLOWS IN ALEXANDROV SPACES

27[16] J. Holbrook, No dice: a deterministic approach to the Cartan centroid, J. Ramanujan Math.
Soc. 27 (2012), 509–521.
[17] J. Jost, Equilibrium maps between metric spaces, Calc. Var. Partial Diﬀerential Equations 2(1994), 173–204.
[18] J. Jost, Convex functionals and generalized harmonic maps into spaces of nonpositive curvature,
Comment. Math. Helv. 70 (1995), 659–673.
[19] J. Jost, Nonpositive curvature: geometric and analytic aspects, Birkhäuser Verlag, Basel, 1997.
[20] J. Jost, Nonlinear Dirichlet forms, New directions in Dirichlet forms, 1–47, AMS/IP Stud. Adv.
Math., 8, Amer. Math. Soc., Providence, RI, 1998.
[21] H. Karcher, Riemannian center of mass and molliﬁer smoothing, Comm. Pure Appl. Math. 30(1977), 509–541.
[22] W. S. Kendall, Probability, convexity, and harmonic maps with small image I: uniqueness andﬁne existence, Proc. London Math. Soc. (3) 61 (1990), 371–406.
[23] W. S. Kendall, Convexity and the hemisphere, J. London Math. Soc. (2) 43 (1991), 567–576.
[24] L. A. Korf and R. J.-B. Wets, Random lsc Functions: An Ergodic Theorem, Mathematics ofOperations Research (26) 2 (2001), 421–445.
[25] K. Kuwae, Jensen’s inequality over CAT(κ)-space with small diameter, Potential theory andstochastics in Albac, 173–182, Theta Ser. Adv. Math., 11, Theta, Bucharest, 2009.
[26] J. Lawson and Y. Lim, Monotonic properties of the least squares mean, Math. Ann. 351 (2011),
267–279.
[27] C. Li, G. López, and V. Martı́n-Márquez, Monotone vector ﬁelds and the proximal point algorithm on Hadamard manifolds, J. Lond. Math. Soc. (2) 79 (2009), 663–683.
[28] Y. Lim and M. Pálﬁa, Weighted deterministic walks for the least squares mean on Hadamard
spaces, Bull. London Math. Soc. 46 (2014), 561–570.
[29] A. Lytchak, Open map theorem for metric spaces, St. Petersburg Math. J. 17 (2006), 477–491.
[30] U. F. Mayer, Gradient ﬂows on nonpositively curved metric spaces and harmonic maps, Comm.
Anal. Geom. 6 (1998), 199–253.
[31] M. Moakher, Means and Averaging in the Group of Rotations, SIAM J. Matrix Anal. Appl. 24(2002), 1–16.
[32] A. Nedic and D. P. Bertsekas, Convergence Rate of Incremental Subgradient Algorithms, Stochastic optimization: algorithms and applications (Gainesville, FL, 2000), 223–264, Appl. Optim., 54, Kluwer Acad. Publ., Dordrecht, 2001.
[33] A. Nedic and D. P. Bertsekas, Incremental subgradient methods for nondiﬀerentiable optimization, SIAM J. Optim. 12 (2001), 109–138.
[34] S. Ohta, Convexities of metric spaces, Geom. Dedicata 125 (2007), 225–250.
[35] S. Ohta, Gradient ﬂows on Wasserstein spaces over compact Alexandrov spaces, Amer. J. Math.
131 (2009), 475–516.

28

SHIN-ICHI OHTA AND MIKLÓS PÁLFIA[36] S. Ohta, Barycenters in Alexandrov spaces of curvature bounded below, Adv. Geom. 12 (2012),
571–587.
[37] G. Perel’man and A. Petrunin, Quasigeodesics and gradient curves in Alexandrov spaces, Unpublished preprint (1995). Available at http://www.math.psu.edu/petrunin/[38] A. Petrunin, Semiconcave functions in Alexandrov’s geometry, Surveys in diﬀerential geometry.
Vol. XI, 137–201, Surv. Diﬀer. Geom., 11, Int. Press, Somerville, MA, 2007.
[39] R.T. Rockafellar, Convex Analysis, Princeton University Press, 1997.
[40] R.T. Rockafellar and R. J.-B. Wets, Variational Analysis, Springer-Verlag, Berlin, 1998.
[41] K.-T. Sturm, Nonlinear Markov operators associated with symmetric Markov kernels and energy
minimizing maps between singular spaces, Calc. Var. Partial Diﬀerential Equations 12 (2001),
317–357.
[42] K.-T. Sturm, Nonlinear Markov operators, discrete heat ﬂow, and harmonic maps between
singular spaces, Potential Anal. 16 (2002), 305–340.
[43] K.-T. Sturm, Nonlinear martingale theory for processes with values in metric spaces of nonpositive curvature, Ann. Probab. 30 (2002), 1195–1222.
[44] K.-T. Sturm, Probability measures on metric spaces of nonpositive curvature, Heat kernels andanalysis on manifolds, graphs, and metric spaces (Paris, 2002), 357–390, Contemp. Math., 338,
Amer. Math. Soc., Providence, RI, 2003.
[45] K.-T. Sturm, A semigroup approach to harmonic maps, Potential Anal. 23 (2005), 225–277.
[46] K.-T. Sturm, On the geometry of metric measure spaces, Acta Math. 196 (2006), 65–131.
Department of Mathematics, Kyoto University, Kyoto 606-8502, Japan
E-mail address: sohta@math.kyoto-u.ac.jp
E-mail address: palfia.miklos@aut.bme.hu