# Remarks on manifolds with two sided curvature bounds

Vitali Kapovitch  University of Toronto<EMAIL_ADDRESS>and  Alexander
Lytchak  Mathematisches Institut
Universität Köln
Weyertal 86 – 90
50931 Köln, Germany<EMAIL_ADDRESS>
###### Abstract.

We discuss folklore statements about distance functions in manifolds with two
sided bounded curvature. The topics include regularity, subsets of positive
reach and the cut locus.

###### Key words and phrases:

Distance functions, cut locus, subsets of positive reach, harmonic
coordinates, Alexandrov spaces

###### 2010 Mathematics Subject Classification:

53C20, 53C21, 53C23

V.K. is partially supported by a Discovery grant from NSERC; A. L. was
partially supported by the DFG grants SFB TRR 191 and SPP 2026.

##  1\. Introduction

###  1.1. Distance functions in smooth Riemannian manifolds

We discuss slightly generalized versions of some folklore results about
distance functions $d_{A}$ to subsets $A$ of smooth Riemannian manifolds $M$.
The results turn out to be local and are proved without any completeness
assumptions. Our proofs do not involve Jacobi fields, but only basic facts
about semi-concavity and semi-convexity of distance functions. Therefore, the
statements generalize to the synthetic setting of manifolds with two sided
curvature bounds, as will be explained below.

The first statement is well-known in the complete situation, see, for
instance, [MM03], [CS04], [GS19, Section 2].

######  Proposition 1.1.

Let $M$ be a smooth Riemannian manifold. Let $A\subset M$ be a closed subset
and let $f$ denote the distance function to the set $A$. Then $f$ is
semiconcave in $M\setminus A$. The following conditions are equivalent for an
open subset $O\subset M\setminus A$:

  1. (1)

$f$ is semiconvex in $O$.

  2. (2)

$f$ is $\mathcal{C}^{1,1}$ in $O$.

  3. (3)

$f$ is $\mathcal{C}^{1}$ in $O$.

  4. (4)

For any $y\in O$, there exists at most one geodesic
$\gamma_{y}:[0,\epsilon)\to M$ starting at $y$ and parametrized by arclength,
with the property $f\circ\gamma_{y}(t)=f(y)-t$, for all $t$ in $[0,\epsilon)$.

We assume some familiarity with the notions of semiconcave (semiconvex)
functions and their gradient flows, [Pet07], [AKP19], [AGS05]. Here and below,
the notions of semi-concavity (convexity) and $\mathcal{C}^{1,1}$ are local.
For instance, we say that a function $f$ is $\mathcal{C}^{1,1}$ if it is
$\mathcal{C}^{1}$ and the gradient $\nabla f$ is _locally_ Lipschitz
continuous.

For a closed subset $A$ of $M$, denote by $Reg^{d_{A}}$ the set of points
$x\in M\setminus A$, such that $d_{A}$ is $\mathcal{C}^{1}$ in a neighborhood
of $x$. Thus, $Reg^{d_{A}}$ is the maximal open set $O\subset M\setminus A$
which satisfies the equivalent conditions of Proposition 1.1. The closed
subset $CL(A)=(M\setminus A)\setminus Reg^{d_{A}}$ of $M\setminus A$ is called
the _cut locus_ of $A$ in $M$.

If $M$ is complete, then the geodesic $\gamma_{y}$ in (4) can be extended to a
unique minimizing geodesic $\gamma_{y}:[0,d_{A}(y)]\to M$ from $y$ to $A$. The
endpoint of this geodesic is the unique projection point $\Pi^{A}(y)$ of $y$
on $A$. Moreover, the whole geodesic $\gamma_{y}([0,d_{A}(y)))$ is contained
in $Reg^{d_{A}}$.

If $M$ is complete and $A$ is a $\mathcal{C}^{k}$ submanifold, for $k\geq 2$,
then $d_{A}:Reg^{d_{A}}\to\mathbb{R}$ can be expressed in terms of the normal
exponential map of $A$ and turns out to be $\mathcal{C}^{k}$, see, for
instance, [MM03, Prop. 4.3].

In the non-complete situation, none of the above statements need to hold, see
Example 4.3.

The next result is known to specialists for some subsets in complete
manifolds, [ACNS13], [Alb15]. We inlcude a short proof based on a general fact
about gradient flows. Note, that the function $d_{A}$ is semi-concave on
$M\setminus A$ and has a uniquely defined (local) gradient flow.

######  Proposition 1.2.

Let $A$ be a closed subset of a Riemannian manifold $M$. Then the cut locus
$CL(A)\subset M\setminus A$ of $A$ is invariant under the gradient flow $\Phi$
of the distance function $d_{A}$.

A natural generalization of the above result and its proof is valid in
Alexandrov spaces, [AKP19, Prop. 14.1.5]. As an application of Proposition 1.2
one can derive a very short proof of the nice geometric observation [GS19,
Theorem 6.1], see Corollary 4.2 below.

Finally, we address (again essentially well-known to specialists) properties
of subsets of positive reach, defined and investigated by Federer in Euclidean
spaces, [Fed69], and by Bangert and Kleinjohann in Riemannian manifolds,
[Ban82], [Kle81]; see also [Lyt05b], [Lyt04], [RZ17].

Recall that a closed subset $A$ in a Riemannian manifold is said to have
positive reach, if $A$ has a neighborhood $O$ such that the foot point
projection $\Pi^{A}$ is uniquely defined on $O$. As has been shown by Federer
and Bangert, the notion only depends on the underlying smooth structure and
not on the Riemannian metric. The following result is essentially contained in
[Kle81], [Ban82], [Lyt05b].

######  Proposition 1.3.

Let $A$ be a closed subset of a smooth Riemannian manifold $M$. Then the
following are equivalent:

  1. (1)

The subset $A$ is of positive reach.

  2. (2)

There is an open neighborhood $O$ of $A$ such that the distance function
$d_{A}$ is $\mathcal{C}^{1,1}$ in $O\setminus A$.

  3. (3)

The function $d_{A}$ is semiconvex on a neighborhood $O$ of $A$.

See [Ban82] and [Lyt05b] for other characterizations.

Any subset of positive reach $A\subset M$ has a well-defined _tangent cone_
$T_{x}A$ at every point $x\in A$. This tangent cone is a convex cone in
$T_{x}M$, [Fed69, Theorem 4.8]. The _normal cone_ $T^{\perp}_{x}A$ is the
convex cone of all vectors in $T_{x}M$ enclosing angles at least
$\frac{\pi}{2}$ with all vectors in $T_{x}A$.

For the following folklore statement about subsets of positive reach we could
not find appropriate references. In the Euclidean case the result is contained
in [Fed69].

######  Proposition 1.4.

Let $A\subset M$ be a subset of positive reach. Then for any $x\in A$ and unit
$h\in T^{\perp}_{x}A$ the geodesic $\gamma^{h}$ starting at $x$ in the
direction of $h$ satisfies $d_{A}(\gamma^{h}(s))=s$, for all $s>0$ such that
$\gamma^{h}([0,s])$ is contained in the open subset $O$ from Proposition 1.3.

###  1.2. Manifolds with two sided curvature bounds

Here we discuss some basic observations about non-smooth Riemannian manifolds
which have two sided curvature bounds in the sense of Alexandrov and the
extensions of the above results to this setting. These results have been
applied in [KL20]. Readers only interested in the smooth situation can skip
this part of the introduction together with Section 6.

Manifolds with two sided curvature bounds in the sense of Alexandrov appear in
one of the most prominent examples of Gromov–Hausdorff convergence. Namely,
the class of such compact manifolds with uniform bounds on injectivity radius,
diameter and curvature is compact with respect to the Gromov–Haudorff
convergence, [BN93], [Gro07], [Pet87]. It provides a natural compactification
of the corresponding class of smooth Riemannian manifolds. Moreover, all
manifolds with two sided curvature bounds in the sense of Alexandrov turn out
to have a rather regular analytic structure and to admit a smoothing, as has
been proved by Nikolaev in a series of papers. A good readable summary of
these results of Nikolaev and related statements on the structure of such
manifolds has appeared in [BN93]. Results and ideas of Nikolaev motivated many
theorems in the theory of Alexandrov spaces with one-sided curvature bounds,
[BGP92], [KKK19], [Per94], [OS94], [Pet98], [LN18].

We will assume some familiarity with the theory of Alexandrov spaces, and
refer the non-familiar reader to [AKP19]. The most appropriate setting for our
local results is the following one.

######  Definition 1.5.

A locally compact length metric space $X$ has two sided bounded curvature if
for any point $x\in X$ there exists a compact convex neighborhood $U$ and some
$K>0$ such that $U$ is an Alexandrov space of curvature $\geq-K$ and a
$CAT(K)$ space.

A space $X$ with two sided bounded curvature is topologically a manifold $M$
with boundary $\partial M$. Moreover, $M\setminus\partial M$ is convex in $M$,
[BN93], cf. [KKK19]. We restrict the attention to the case $\partial
M=\emptyset$.

By a _manifold with two sided curvature bounds_ we will denote a space as in
the above Definition 1.5 which, in addition, is homeomorphic to a manifold
without boundary.

Any manifold $M$ with two sided curvature bounds admits a natural atlas of
distance coordinates, see [BN93] and Section 3 below. The distance in $M$ is
defined by a $\mathcal{C}^{0,1}$ Riemannian metric $g$ in this atlas.
Moreover, the $\mathcal{C}^{1,1}$-smoothness of the atlas and the
$\mathcal{C}^{0,1}$-smoothness of the Riemannian metric is optimal, as can be
observed in the manifold $M$ arising from the gluing of a flat cylinder and a
hemisphere. Results of this type with weaker conclusions have been obtained
for distance coordinates under one-sided curvature bounds, [Per94], [OS94],
[LN18].

On any $\mathcal{C}^{1,1}$ manifold $M$ with a Lipschitz continuous Riemannian
metric, any harmonic function is $\mathcal{C}^{1,\alpha}$, for all $\alpha<1$,
[Tay00, III, Chapter 9] and there exist harmonic coordinates around any point,
[Tay00, III, Chapter 9]. The atlas of harmonic coordinates is of class
$\mathcal{C}^{2,\alpha}$, [Sv76, p. 689] and the distance is defined by a
metric of class $\mathcal{C}^{\alpha}$ in these coordinates. One of the
central results of Nikolaev’s theory, see [BN93], is that for any manifold $M$
with two sided curvature bounds, the harmonic atlas is of class
$\mathcal{C}^{3,\alpha}$, for any $\alpha<1$, and the Riemannian metric in
this atlas is of class $\mathcal{C}^{1,\alpha}$, for any $\alpha<1$.

In a general $\mathcal{C}^{1,1}$-manifold with a $\mathcal{C}^{0,1}$
Riemannian metric a harmonic function does not need to be of class
$\mathcal{C}^{1,1}$, cf. [Sv76, p. 693] and Problem 1.9 below. Our first
observation is that such a loss of smoothness cannot happen on a manifold with
two sided bounded curvature.

######  Proposition 1.6.

Let $M$ be a manifold with two sided bounded curvature. Then any harmonic
function on an open subset $U$ in $M$ is of class $\mathcal{C}^{1,1}$ in
distance coordinates. Thus, any transformation from distance to harmonic
coordinates is of class $\mathcal{C}^{1,1}$.

Thus, the $\mathcal{C}^{1,1}$ atlas of distance coordinates can be assumed to
include all harmonic coordinates as well. From now on all statements will
refer to this $\mathcal{C}^{1,1}$ atlas. The following result might be
folklore knowledge:

######  Proposition 1.7.

Let $M$ be a manifold with two sided curvature bounds and let $N\subset M$ be
a $\mathcal{C}^{1,1}$ submanifold. Then $N$ with its intrinsic metric is a
manifold with two sided curvature bounds.

This result follows from the Gauß equation and another central result of
Nikolaev’s theory, stating that manifolds with two sided curvature bounds are
exactly the limit spaces (in a precise local sense) of smooth Riemannian
manifolds with uniform bounds on sectional curvature.

The final statement discussed in the introduction is that all results about
distance functions in smooth Riemannian manifolds are valid in this more
general setting:

######  Theorem 1.8.

The statements of Proposition 1.1, Proposition 1.2 and Proposition 1.3 are
valid for any closed subset $A$ of any manifold $M$ with two sided bounded
curvature. The differentiability in Propositions 1.1, 1.3 is considered with
respect to distance coordinates.

###  1.3. A few questions

We would like to finish the introduction with a few open questions about
manifolds with two sided curvature bounds.

######  Problem 1.9.

Does there exist a Riemannian metric of class $\mathcal{C}^{0,1}$ and a
harmonic function with respect to this metric, which is not
$\mathcal{C}^{1,1}$?

It is possible that a positive answer to this problem might be obtained
following the ideas in the examples discussed in [Sv76, p. 693].

The second part of the next problem is motivated by Proposition 1.7. It should
be compared with Nash’s embedding theorem for Riemannian manifolds of higher
regularity, see [And02].

######  Problem 1.10.

Let $M$ be a (compact, complete, local) manifold with two sided curvature
bounds in the sense of Alexandrov. Do there exist coordinates on $M$ in which
the distance is defined by a Riemannian metric of class $\mathcal{C}^{1,1}$?
Can $M$ be length-preserving embedded as a $\mathcal{C}^{1,1}$ submanifold in
a Euclidean space?

We would like to mention that the folklore argument providing a negative
answer to the first question above, for instance, [Pet87], is not correct.
Indeed, [Pet87] provides a surface with two sided curvature bounds such that
in harmonic coordinates the Riemannian metric is not of class
$\mathcal{C}^{1,1}$. Then the proof invokes the statement of [DK81], [Sv76]
that the smoothness of the metric is optimal in harmonic coordinates. However,
this elliptic regularity statement is not covered by [DK81] (since elliptic
regularity does not work well for Lipschitz functions). Indeed, the following
result has appeared in [Sv76, Example 2] and provides a counter-example to the
folklore proof. There exists a Riemannian metric of class $\mathcal{C}^{2}$ on
$\mathbb{R}^{2}$ such that in any harmonic coordinates the metric is not
$\mathcal{C}^{1,1}$.

The second question concerns the existence of a canonical smoothing of
manifolds with two sided curvature bounds. While the existence part in the
next question is a direct consequence of the approximation results of Nikolaev
and [Shi89], the uniqueness is more subtle:

######  Problem 1.11.

Let $M$ be a complete manifold with two sided bounded curvature. If the
curvature bounds can be chosen uniformly on $M$ then there exists a unique
Ricci flow coming out of the manifold $M$.

The final problem we would like to mention is due to the following fact. The
theory of Nikolaev is scattered through several works and some of them are not
easy to read (and to find). Thus, we formulate:

######  Problem 1.12.

Find a streamlined proof of Nikolaev’s result on smoothings of manifolds with
two sided curvature bounds, [Nik91], [Nik88].

###  1.4. Structure of the paper

In Section 2, we recall basics on semiconcave functions and their gradient
flows and verify a local version of Proposition 1.2. In Section 3, we recall
basic facts about distance coordinates. In Section 4, we prove Proposition 1.1
and 1.2. In Section 5, we prove the stated results about subsets of positive
reach, Propositions 1.3, 1.4. Finally, in Section 6, we prove Proposition 1.6
and Proposition 1.7.

##  2\. Semiconcavity and gradient flows

###  2.1. Notation

Distance will be denote by $d$. The distance function from a subset $A$ of a
space $X$ will be denote by $d_{A}$. By definition, this is a $1$-Lipschitz
function. A geodesic will denote an isometric embedding $\gamma:I\to X$ of an
interval. Thus, our geodesics are always parametrized by arclength and
globally minimizing.

###  2.2. Special neighborhood

Let $M$ be a manifold with two sided curvature bounds. For any point $x\in M$,
we find a compact neighborhood $U$ of $x$ as in Definition 1.5. Restricting
the neighborhood and using convexity of small balls in $CAT(K)$ spaces we may
assume that the neighborhood $U=U_{x}$ has the following form.

The set $U_{x}$ is the closed ball of radius $r_{x}$ around $x$ and it is
homeomorphic to a Euclidean ball, [BN93, Theorem 12.1]. Any pair of points in
$U_{x}$ is connected by a unique geodesic in $U_{x}$. For some $K_{x}>0$, the
space $U_{x}$ is $CAT(K_{x})$ and an Alexandrov space of curvature $\geq-
K_{x}$, moreover, $\epsilon_{x}:=r_{x}\cdot K_{x}<<1$. Any geodesic in $U_{x}$
extends to a geodesic starting and ending on the distance sphere $\partial
U_{x}$, [BN93, Prop. 8.3].

###  2.3. Semiconvexity, semiconcavity and gradient flows

A locally Lipschitz function $f$ on an open subset $O$ of $M$ is _$C$
-concave_, respectively _$C$ -convex_, if for any geodesic $\gamma:I\to O$ the
function $f\circ\gamma(t)-\frac{C}{2}t^{2}$ is concave, respectively convex,
on $I$.

A function $f$ is $C$-concave if and only if for all pairs of points
$p_{1},p_{2}\in M$ which are sufficiently close to each other and any midpoint
$m$ between $p_{1}$ and $p_{2}$, we have

(2.1) $f(m)\geq\frac{1}{2}(f(p_{1})+f(p_{2}))-\frac{C}{8}\cdot
d^{2}(p_{1},p_{2})\;.$

The function $f:O\to\mathbb{R}$ is _semiconcave_ (semiconvex) if for any $x\in
O$ there is some $C\in\mathbb{R}$, such that the restriction of $f$ to some
neighborhood of $x$ in $O$ is $C$-concave ($C$-convex).

If $f:O\to\mathbb{R}$ is semiconcave and $h:O\to\mathbb{R}$ is continuous, we
say that the function $f$ is $h$-concave, if for any $x\in O$ and any
$\epsilon>0$, there exists a neighborhood $O_{\epsilon}$ of $x$ such that $f$
is $(h(x)+\epsilon)$-concave in $O_{\epsilon}$.

This is equivalent to the requirement that, for any geodesic $\gamma:I\to O$,
we have $(f\circ\gamma)^{\prime\prime}\leq h\circ\gamma$ on $I$ in the sense
of distributions.

Since the notion of semiconcavity and of gradient curves and flows of
semiconcave functions is local, the whole theory of gradient flows in
Alexandrov spaces, [AKP19], [Pet07], applies to the present situation.

For any semiconcave function $f:O\to\mathbb{R}$ and every $x\in O$ there
exists a unique vector $\nabla_{x}f\in T_{x}O$, the _gradient_ of $f$ at $x$.
Moreover, there exists a unique maximal curve $\eta_{x}:[0,a)\to O$ with some
$a\in(0,\infty)$, the gradient curve of $f$, which starts in $x$ and satisfies

$\eta_{x}^{\prime}(t)=\nabla_{\eta_{x}(t)}f\;\text{and}\;(f\circ\eta_{x})^{\prime}(t)=|\nabla_{\eta_{x}(t)}f|^{2}\;,$

for all $t\in[0,a)$. Furthermore, if $a<\infty$ then $\eta_{x}([0,a))$ is not
contained in a compactum in $O$. Finally, the map
$(x,t)\to\Phi(t,x):=\eta_{x}(t)$ is a local flow defined on a neighborhood of
$O\times\\{0\\}\subset O\times[0,\infty)$ is locally Lipschitz continuous,
[Pet07].

A point $x\in O$ is _critical_ for $f$ if $\nabla_{x}f=0$. In this case
$\eta_{x}$ is the stationary curve $\eta_{x}(t)=x$. On the other hand, if the
curve $\eta_{x}$ does not contain critical points of $f$, it has a unique
parametrization $\tilde{\eta}_{x}:[0,\tilde{a})\to O$ by arclength.

The following is a not very well-known but fundamental observation. The first
statement is exactly [AKP19, Theorem 14.1.3]; the second one follows from the
first by localization:

######  Lemma 2.1.

Let $f:O\to\mathbb{R}$ be $C$-concave. Then for the arclength
reparametrization $\tilde{\eta}_{x}$ of any gradient curve $\eta_{x}$ of $f$
in $O$, the composition $f\circ\tilde{\eta}_{x}:[0,a)\to\mathbb{R}$ is
$C$-concave.

If $f$ is $h$-concave for a continuous function $h:O\to\mathbb{R}$ then
$f\circ\tilde{\eta}_{x}$ is $h\circ\tilde{\eta}_{x}$-concave on $[0,a)$.

###  2.4. Distance functions in special neighborhoods

Let $U\subset M$ be a special neighborhood of some point as in Subsection 2.2.
Thus, $U$ is convex, compact, $CAT(K)$ and it is an Alexandrov space of
curvature $\geq-K$, for some $K>0$.

Then, for any point $x\in U$ the distance function $f=d_{x}$ is convex in $U$.
Moreover, $f$ is also semiconcave on $U\setminus\\{x\\}$. More precisely, on
the set $O$ of points $y\in U$ with $d(x,y)>\delta$, the function $f$ is
$C$-concave, for some $C=C(K,\delta)$.

Since an infimum of $C$-concave functions is $C$-concave, for any subset
$B\subset U$ the distance function $d_{B}$ is $C(K,\delta)$ concave on the set
of all points $y\in U$ with $d_{B}(y)>\delta$.

The function $f=d_{B}$ is $1$-Lipschitz, thus $|\nabla_{y}f|\leq 1$ for all
$y\in U\setminus B$. By the first variation formula, $|\nabla_{y}f|=1$ if and
only if $y$ is connected with $B$ by a unique shortest geodesic.

The conclusion of Proposition 1.2 will easily follow from the next Lemma, cf.
[AKP19, Prop. 14.1.5], [ACNS13, Theorem 4.5]:

######  Lemma 2.2.

Let $B\subset U$ be any closed subset in a special neighborhood $U$ as above.
Let $y\in U\setminus B$ be arbitrary and let $\eta_{y}:[0,a)\to U$ be the
gradient curve in $U$ of the distance function $f=d_{B}$ starting at $y$. If
$|\nabla_{y}f|<1$ then $|\nabla_{z}f|<1$, for all $z$ on the gradient curve
$\eta_{y}$.

###### Proof.

Rescaling the space, we may assume that the lower curvature bound on $U$
equals $-1$. Then, for the distance function $F=d_{p}$ to any $p\in U$ the
composition $\hat{F}=\cosh\circ F$ is $\hat{F}$-concave on $U$, [AKP19,
Theorem 7.4.1]. Hence, also for the infimum $f=d_{B}$ of distance functions to
points, the composition $\hat{f}:=\cosh\circ f$ is $\hat{f}$-concave on $U$.

The gradient curves of $f$ and $\hat{f}$ on $U\setminus B$ coincide up to
parametrizations, [AKP19, Theorem 11.4.4]. Thus, the arclength
reparametrization $\tilde{\eta}_{y}$ of $\eta_{y}$ is also the arclength
parametrization of the gradient curve of $\hat{f}$. From Lemma 2.1, we deduce
that $\hat{f}\circ\tilde{\eta}_{y}$ is $\hat{f}\circ\tilde{\eta}_{y}$-concave
on the interval of definition $[0,b]$ of $\tilde{\eta}_{y}$ from $y$ to $z$.

Define $h:[0,b]\to\mathbb{R}$ as $h(t)=f\circ\tilde{\eta}_{y}(t)$. Then $h$ is
an increasing, $1$-Lipschitz, semiconcave function; we have $h^{\prime}(0)<1$
and the composition $\hat{h}:=\cosh\circ h$ is $\hat{h}$-concave. We only need
to verify $h^{\prime}(b)<1$.

Assume, by contrary that $h^{\prime}(b)=1$. Consider the linear function
$h_{0}(t)=t+(h(b)-b)$. Then

$h_{0}(b)=h(b)\;;\;h_{0}^{\prime}(b)=h^{\prime}(b)\;;\;(\cosh\circ
h_{0})^{\prime\prime}=\cosh\circ h_{0}\;.$

By comparison, cf. [AKP19, Theorem 4.5.3], we deduce

$\cosh\circ h(t)\leq\cosh\circ h_{0}(t)\,,$

for all $t\in[0,b]$. Hence $h(t)\leq h_{0}(t)$ for all $t$. However, $h$ is
$1$-Lipschitz. Thus, $h(t)=h_{0}(t)$ for all $t\in[0,b]$. This implis
$h^{\prime}(0)=1$ in contradiction to our assumption. This finishes the proof.
∎

###  2.5. Distance functions to remote subsets

Let $M$ be a manifold with two sided curvature bounds (possibly non-complete
and without uniform bounds on curvature), as in Subsection 1.2. Let $A$ be a
closed subset of $M$ and consider the distance function $f=d_{A}$ to $A$.

Consider an arbitrary point $x\in M\setminus A$ and a special neighborhood
$U=U_{x}=\bar{B}_{r_{x}}(x)$ as in Subsection 2.2. Making $r_{x}$ smaller, we
may assume that $U$ is disjoint from $A$.

Let $\tilde{U}$ be a smaller ball of radius $r<\frac{1}{3}\cdot r_{x}$ around
$x$. Set $s=f(x)$ and denote by $B$ the compact subset $B=f^{-1}(s-2r)\cap U$.
By compactness and convexity of $U$, for any $y\in\tilde{U}$, we find at least
one footpoint $\hat{y}$ of $y$ on $B$, thus $d(y,\hat{y})=d_{B}(y)$. By the
triangle inequality,

$f(y)\leq f(\hat{y})+d(y,\hat{y})=(s-2r)+d_{B}(y)\;.$

On the other hand, any curve $\eta$ from $A$ to $y$ must contain points $z$
with $f(z)=s-2r$. If $z$ is not in $U$ then the length of $\eta$ is at least
$s+r$. Thus, any such $\eta$ with length less than $s+r$, contains points on
$B$. Thus by the triangle inequality we deduce the equality

$d_{A}=f=(s-2r)+d_{B}$

on $\tilde{U}$. Since $d_{B}$ is semiconcave on $\tilde{U}$, so is $f$,
moreover, the gradient curves of $f$ and $d_{B}$ coincide in $\tilde{U}$.

Now we arrive at the following results (also valid in all Alexandrov spaces
and their localized version, Alexandrov regions, [LN20]).

######  Corollary 2.3.

Let $A$ be a closed subset in a manifold $M$ with two sided curvature bounds.
Then, the distance function $f=d_{A}$ is semiconcave on $M\setminus A$. For
any point $x\in M\setminus A$ with $|\nabla_{x}f|<1$ we have $|\nabla_{y}f|<1$
for all $y$ on the gradient curve $\eta_{x}$.

###### Proof.

The semiconcavity condition is local and has been verified above in the
neighborhood of any $x\in M\setminus A$.

In order to see the second statement, we consider the compact part
$\eta_{x}:[0,b]\to M$ of the gradient curve $\eta_{x}$ between $x$ and $y$.
Assuming the contrary, and using that $f\circ\tilde{\eta}_{x}$ is semiconcave,
we find a smallest $t\in(0,b]$ such that $|\nabla_{\eta_{x}(t)}f|=1$.

Now we find a small special neighborhood $U$ of $z=\eta_{x}(t)$, identify on a
smaller neighborhood $\tilde{U}$ (up to an additive constant) $f$ with $d_{B}$
for a closed subset $B\subset U$ and derive a contradiction to Lemma 2.2. ∎

##  3\. Coordinates

###  3.1. Distance coordinates

Let $U\subset M$ be a special neighborhood of a point $x$ in a manifold $M$
with two sided curvature bounds.

For any $x\in U$ the function $d_{x}$ is convex in $U$. Moreover, $d_{x}$ is
$C(K,\delta)$ concave on the set of points $y$ in $U$ with $d(x,y)>\delta$.

For any $p$ in the interior of $U$, consider any points $p_{1},...,p_{n}$ in
$U$ such that the starting directions of the geodesics $pp_{i}$ are almost
orthogonal at $p$, (see [BN93, Theorem 13.2]). Then the map
$F:U\to\mathbb{R}^{n}$ with coordinates $f_{i}:=d_{p_{i}}$ is a biLipschitz
map $F:O\to\tilde{O}$ from an open ball $O$ around $p$ onto an open subset of
$\mathbb{R}^{n}$. (This is even true for any Alexandrov space, [BGP92]).

Any such restriction $F:O\to\tilde{O}$ is called a _distance chart_ on $M$.
The distance charts define a $\mathcal{C}^{1,1}$ atlas on $M$ and the distance
on $M$ is given by a Riemannian metric of class $\mathcal{C}^{0,1}$ with
respect to this atlas, [BN93, Theorem 13.2].

###  3.2. Distance charts and semiconcavity

The following observation can also be used to obtain a shorter alternative
proof of [BN93, Theorem 13.2], using the observation that a homeomorphism
between open subsets of $\mathbb{R}^{n}$ is $\mathcal{C}^{1,1}$ if and only if
it preserves the class of semiconcave functions.

######  Lemma 3.1.

Let $F:O\to\tilde{O}\subset\mathbb{R}^{n}$ be a distance chart in a manifold
with two sided curvature bounds. Then a function $f:\tilde{O}\to\mathbb{R}$ is
semiconcave if and only if $f\circ F$ is semiconcave on $O$.

###### Proof.

From the biLipschitz porperty of $F$, and semiconcavity and semiconvexity of
the coordinates $f_{i}$, we deduce the following. For any geodesic $\gamma$ in
$O$ connecting $q_{1}$ and $q_{2}$ and having $m$ as its midpoint the distance
between $F(m)$ and the midpoint $\bar{m}=\frac{1}{2}(F(q_{1})+F(q_{2}))$ in
$\mathbb{R}^{n}$ between $F(q_{i})$, we have

$d(F(m),\bar{m})\leq C\cdot d^{2}(q_{1},q_{2})\;.$

Here the constant $C$ depends only on the biLipschitz constant of $F$ and the
curvature bounds.

Since $F$ is biLipschitz, $F^{-1}$ sends midpoints in $\tilde{O}$ to ”almost
midpoints” in $O$ in the same sense as above. Now the equivalence of
semiconcavity of $f$ and $f\circ F$ follows after applying (2.1). ∎

##  4\. Main results

###  4.1. General distance functions

We are going to prove the following slight generalization of Proposition 1.1

######  Proposition 4.1.

Let $M$ be a manifold with two sided curvature bounds. Let $A\subset M$ be a
closed subset and $f=d_{A}$. Then the following conditions are equivalent for
an open subset $O\subset M\setminus A$:

  1. (1)

$f$ is semiconvex in $O$.

  2. (2)

$f$ is $\mathcal{C}^{1,1}$ in $O$.

  3. (3)

$f$ is $\mathcal{C}^{1}$ in $O$.

  4. (4)

For all $x\in O$ we have $|\nabla_{x}f|=1$

  5. (5)

For any $x\in O$, there exists at most one geodesic
$\gamma_{x}:[0,\epsilon)\to M$ starting at $x$, with
$f\circ\gamma_{x}(t)=f(x)-t$, for all $t$ in $[0,\epsilon)$.

###### Proof.

All statements are local on $O$. We may fix $p\in O$ and consider a special
neighborhood $U$ of $p$ in $M$. Furthermore, in Subsection 2.5, we have found
a closed subset $B$ in $U$ and a smaller neighborhood $O_{0}$ of $p$ in $O$,
such that on $O_{0}$ the function $f$ coincides with $d_{B}$ up to an additive
constant. Thus, we may assume without loss of generality, that $A=B\subset U$
and $O=O_{0}$. Making $O$ smaller, if needed, we may assume that $O$ is a
coordinate chart. Thus, on $O$ the notion of semiconcavity are the same with
respect to the metric structure and to the coordinate chart.

The semiconcavity of $f$ has been verified in Corollary 2.3. Since on open
subsets of $\mathbb{R}^{n}$ a function is $\mathcal{C}^{1,1}$ if and only if
it is semiconcave and semiconvex, the properties (1) and (2) are equivalent.

Clearly, (2) implies (3).

For any $x\in O$, we find, by compactness, at least one shortest geodesic
$\gamma_{x}:[0,f(x)]\to U$ from $x$ to $A=B$. Then
$(f\circ\gamma_{x})^{\prime}=-1$ on $[0,f(x))$. This shows, that for all
$t\in(0,f(x))$, we have $|\nabla_{\gamma_{x}(t)}f|=1$. If $f$ is
$\mathcal{C}^{1}$ it also implies $|\nabla_{x}f|=1$. Hence, (3) implies (4).

By the first formula of variation, $|\nabla_{x}f|=1$ if and only $x$ is
connected with $B$ by exactly one shortest geodesic $\gamma_{x}$. Note that
for any such geodesic $f\circ\gamma_{x}(t)=f(x)-t$ for all $t\in[0,f(x)]$.
Moreover, for any geodesic, $\tilde{\gamma}_{x}:[0,\epsilon)\to U$ satisfying
the above equality for all $t\in[0,\epsilon)$, the unique extension of
$\tilde{\gamma}_{x}$ to length $f(x)$ ends on $B$. This shows the equivalence
of (4) and (5).

It remains to show that (4) implies (1). In this case, gradient lines
$\eta_{x}$ of $f$ in $O$ are parametrized by arclength and $f\circ\eta_{x}$
has everywhere velocity $1$. This implies that any gradient line $\eta_{x}$ in
$O$ is an (as always minimizing) geodesic.

Fix $x\in O$ and consider $\delta$ such that the ball of radius $3\delta$
around $x$ is contained in $O$. Consider $C=C(K,\delta)$, the semiconcavity
constant of distance functions in $O$ at distance $\geq\delta$, as in
Subsection 2.4. We claim that $f$ is $-C$-convex on the ball $W$ of radius
$\delta$ around $x$.

Indeed, consider points $q_{1},q_{2}\in W$ and their midpoint $m$. Set
$z=\eta_{m}(2\delta)$. Then, for $i=1,2$,

$f(z)=f(m)+2\delta=f(m)+d(m,z)\leq f(q_{i})+d(q_{i},z)\;,$

due to the triangle inequality. This implies

$f(m)\leq\frac{1}{2}(f(q_{1})+f(q_{2}))+(\frac{1}{2}(d(q_{1},z)+d(q_{2},z))-d(m,z))\leq$
$\leq\frac{1}{2}(f(q_{1})+f(q_{2}))+\frac{C}{8}\cdot d^{2}(q_{1},q_{2})\;.$

This implies the claimed semiconvexity of $f$. ∎

###  4.2. Cut locus

As a combination of previous results we now obtain

###### Proof of Proposition 1.2.

As before set $f=d_{A}$. Due to Proposition 4.1, the cut locus $CL(A)$ of $A$
is exactly the closure $CL(A)=\bar{X}$ of

$X=\\{x\in M\setminus A\;:\;|\nabla_{x}f|<1\\}\;.$

As we have seen in Corollary 2.3, the set $X$ is invariant under the gradient
flow of $f$. By continuity of the gradient flow, the closure $\bar{C}=CL(A)$
is invariant under the gradient flow as well. ∎

As a consequence we deduce the following observation from [GS19]:

######  Corollary 4.2.

Let $M$ be a complete Riemannian manifold. Let $A$ be a closed subset of $M$
and let $X=CL(A)\subset M\setminus A$ be the cut locus of $A$. Assume that the
distance function $d_{A}$ is concave on $M$.

Let $x\in M\setminus A$ be arbitrary and let $x_{0}\in CL(A)$ be a point with
$d(x,x_{0})=d(x,CL(A))$. Then $d_{A}(x_{0})\geq d_{A}(x)$.

###### Proof.

Assume the contrary, thus $d_{A}(x_{0})<d_{A}(x)$. Consider a geodesic
$\gamma$ from $x_{0}$ to $x$. Since $h:=d_{A}\circ\gamma$ is concave, the
derivative of $h$ at $0$ is positive. In particular, $x_{0}$ is non-critical
for the function $d_{A}$. Thus, the gradient curve $\eta_{x_{0}}$ of $d_{A}$
starting at $x_{0}$ is non-constant. Moreover, the angle between
$\gamma^{\prime}(0)$ and $\nabla_{x_{0}}d_{A}$ is less than $\frac{\pi}{2}$.

By the first variation formula, the derivative of $l(t):=d(x,\eta_{x_{0}}(t))$
at $0$ is negative. Hence, for small $t>0$, we have

$d(x,\eta_{x_{0}}(t))<d(x,x_{0})\;.$

Due to Proposition 1.2, $\eta_{x_{0}}(t)$ is contained $CL(A)$. Thus, $x_{0}$
is not a nearest point to $x$ in $CL(A)$. This contradiction finishes the
proof. ∎

###  4.3. Simple counterexample

The following example shows that without a completeness assumpion no higher
smoothness of the distance function can be expected:

######  Example 4.3.

Let $M$ be the flat non-complete manifold $\mathbb{R}^{2}\setminus C$, where
$C$ is the ray $C=\\{(0,t)\;:\;t\geq 0\\}$. Let $A$ be the singleton $(1,0)\in
M$. It is not difficult to see (for instance, using that the completion of $M$
is CAT(0), [LW18, Proposition 12.1], thus uniquely geodesic) that
$Reg^{d_{A}}$ is the whole complement $M\setminus A$. While $M$ is smooth and
$A$ is a smooth submanifold, the distance function $f$ to $A$ is not smooth:
level sets of $f^{-1}(s)$ of $f$ are concatenations of parts of Euclidean
circles of radii $s$ and $s-1$ and thus not $\mathcal{C}^{2}$.

##  5\. Subsets of positive reach

###  5.1. Characterization

We are going to provide:

###### Proof of Proposition 1.3.

Proposition 1.1 shows the equivalence of (1) and (2). Moreover, by Proposition
1.1, (3) implies (2).

It remains to show that (2) implies (3). Thus, let $O$ be a neighborhood of
$A$ such that $f=d_{A}$ is $\mathcal{C}^{1,1}$ in $O\setminus A$. Then $f$ is
semiconvex on $O\setminus A$ and we need to show that $f$ is semiconvex around
any point $x\in A$. Consider a special ball $U_{x}$ around $x$ of radius $r$.
Let $W$ be the ball of radius $\frac{r}{3}$ around $x$. For any
$q_{1},q_{2}\in W$ with midpoint $m$ we either have $m\in A$ and then

$f(m)=0\leq\frac{1}{2}(f(q_{2})+f(q_{2}))\;.$

Or $m\notin A$. Then the gradient curve $\eta_{m}$ of $f$ starting in $m$ is a
geodesic on $[0,\frac{r}{3}]$. As in the last part of the proof of Proposition
1.1, we deduce

$f(m)\leq\frac{1}{2}(f(q_{1})+f(q_{2}))+\frac{C}{8}\cdot
d^{2}(q_{1},q_{2})\;,$

for some $C$ depending only on $U_{x}$. Hence $f$ is semiconvex in $W$,
finishing the proof. ∎

###  5.2. Geodesics in normal directions

Now we derive:

###### Proof of Proposition 1.4.

The distance function $f=d_{A}$ is semiconvex in a neighborhood $O$ of $A$.
Thus, we have a well-defined (directional) differential
$D_{x}f:T_{x}M\to\mathbb{R}$ and this differential coincides with the distance
to the tangent cone $T_{x}A$, cf. [Lyt05a].

By the definition of normal directions, we have $D_{x}f(h)=1$. In other word,
$(f\circ\gamma^{h})^{\prime})(0)=1$. By semiconvexity of $f\circ\gamma^{h}$,
we have

$\lim_{t\to 0}(f\circ\gamma^{h})^{\prime}(t)=1\,.$

By the first variation formula, this implies that for $t\to 0$, the angle
between $(\gamma^{h})^{\prime}(t)$ and the unique shortest geodesic from
$\gamma^{h}(t)$ to $A$ converges to $\pi$. Thus the angle between the gradient
curve $\eta^{t}$ of $f$ starting at $\gamma^{h}(t)$ and $\gamma^{h}$ at the
point $\gamma^{h}(t)$ converges to $0$. Since, the gradient curves $\eta^{t}$
are geodesics on a fixed interval $[0,s_{0}]$, we deduce that
$\eta^{t}:[0,s_{0}]\to O$ converge to $\gamma^{h}$.

Thus, $d(\gamma^{h}(t),A)=t$ for all $t\in[0,s_{0}]$. This implies the claim.
∎

##  6\. Harmonic coordinates and submanifolds

###  6.1. Harmonic and distance coordinates

We provide:

###### Proof of Proposition 1.6.

. Thus, let $M$ be a manifold with two sided curvature bounds. Let
$G:V\to\mathbb{R}^{n}$ be some distance coordinates on an open subset $V$ of
$M$ and let $f:V\to\mathbb{R}$ be a harmonic function.

We identify $V$ with $G(V)\subset\mathbb{R}^{n}$. The Riemannian metric $g$ of
$M$ restricted to is Lipschitz continuous on $V$, [BN93, Theorem 13.2].

Let $x\in V$ be arbitrary and consider arbitrary harmonic coordinates
$F:O\to\mathbb{R}^{n}$ defined on a neighborhood $O$ of $x$. Thus, the
coordinates of $F$ are harmonic functions in $O$.

Due to Nikolaev’s theorem, the pull-back Riemannian metric
$\tilde{g}:=(F^{-1}){\ast}(g)$ is $\mathcal{C}^{1,\alpha}$ on
$\tilde{O}:=F(O)\subset\mathbb{R}^{n}$, for all $\alpha<1$, [BN93, Theorem
14.2]. In particular, $\tilde{g}$ is locally Lipschitz continuous.

Then $F:(O,g)\to(\tilde{O},\tilde{g})$ is an isometry between Riemannian
manifolds with $\mathcal{C}^{0,1}$ Riemannian metrics. And such an isometry is
always $\mathcal{C}^{1,1}$, [Sab93]. See also [LY06] and [Tay06] for other
proofs of this fact. Hence, $F$ and $F^{-1}$ are of class $\mathcal{C}^{1,1}$.

The function $F^{-1}\circ f$ is harmonic on $\tilde{O}$. By elliptic
regularity, [Tay00] or [Sv76, p. 689], the function $F^{-1}\circ f$ is
$\mathcal{C}^{3,\alpha}$. In particular, it is $\mathcal{C}^{1,1}$. Hence,
$f=F\circ F^{-1}\circ f$ is $\mathcal{C}^{1,1}$ on $O$ as well. This finishes
the proof. ∎

###  6.2. Submanifolds

This subsection is devoted to

###### Proof of Proposition 1.7.

Let $M$ be a manifold with two sided bounded curvature and let $N$ be a
$\mathcal{C}^{1,1}$ submanifold with respect to distance coordinates.

The statement is local. We fix any point $x\in N$ and consider a special
neighborhood $U_{x}$ of $x$ in $M$. Then we find a compact $\mathcal{C}^{1,1}$
submanifold $\hat{N}$ of $M$ which is contained in $U_{x}$ and such that $N$
and $\hat{N}$ coincide in a neighborhood of $x$.

Since the statement is local we may assume that $N=\hat{N}$. We may further
assume that $U_{x}$ is a distance chart and identify it with a ball in
$\mathbb{R}^{n}$. Then the distance in $U$ is given by a Lipschitz continuous
Riemannian metric $g$.

Due to [Lyt05b, Proposition 1.5] and [Lyt04, Theorem 1.2], the space $N$ is
$CAT(\kappa)$ for some $\kappa$. It thus remains to show that $N$ has
curvature bounded from below.

Applying Proposition 1.6 and Nikolaev’s approximation theorem, [BN93, Theorem
15.1], we may further assume on $U$ there exist smooth Riemannian metrics
$g^{\epsilon}$, which are uniformly Lipschitz continuous and converge to the
Riemannian metric $g$. Moreover, the Riemannian manifold $(U,g^{\epsilon})$
have sectional curvature uniformly bounded from above and below.

Smoothing the submanifold $N$ we find a family of smooth submanifolds
$N^{\epsilon}\subset U$ with uniform bounds on their $\mathcal{C}^{1,1}$-norms
(thus any $N^{\epsilon}$ is a union of a uniform number of charts each of them
of bounded $\mathcal{C}^{1,1}$-norm), such that $N^{\epsilon}$ converge to $N$
in $\mathcal{C}^{1}$ sense.

Considering $N^{\epsilon}$ with the the intrinsic metric induced by
$g^{\epsilon}$, we see that $N^{\epsilon}$ converge to $N$ in the
Gromov–Hausdroff metric (in fact, the convergence is much stronger). Thus, it
remains to show that all $N^{\epsilon}$ are Alexandrov space of curvature
$\geq-\kappa$, for some fixed $\kappa$. However, the $\mathcal{C}^{1,1}$
bounds of $N^{\epsilon}$ directly imply, that the second fundamental forms of
$N^{\epsilon}$ are uniformly bounded (as subsets of the flat space
$\mathbb{R}^{n}$ and therefore, of the Riemannian manifold
$(U,g^{\epsilon})$). Applying the Gauß equation, we derive a uniform lower
bound on the sectional curvatures of $N^{\epsilon}$. By Toponogov’s theorem
and compactness of $N^{\epsilon}$, the manifolds $N^{\epsilon}$ are Alexandrov
spaces of curvature $\geq-\kappa$. This finishes the proof. ∎

## References

  * [ACNS13] P. Albano, P. Cannarsa, Khai T. Nguyen, and C. Sinestrari.  Singular gradient flow of the distance function and homotopy equivalence.  Math. Ann., 356(1):23–43, 2013.
  * [AGS05] Luigi Ambrosio, Nicola Gigli, and Giuseppe Savaré.  Gradient flows in metric spaces and in the space of probability measures.  Lectures in Mathematics ETH Zürich. Birkhäuser Verlag, Basel, 2005\.
  * [AKP19] S. Alexander, V. Kapovitch, and A. Petrunin.  Alexandrov geometry.  Preprint, https://arxiv.org/abs/1903.08539, 2019.
  * [Alb15] Paolo Albano.  On the cut locus of closed sets.  Nonlinear Anal., 125:398–405, 2015.
  * [And02] Ben Andrews.  Notes on the isometric embedding problem and the Nash-Moser implicit function theorem.  In Surveys in analysis and operator theory (Canberra, 2001), volume 40 of Proc. Centre Math. Appl. Austral. Nat. Univ., pages 157–208. Austral. Nat. Univ., Canberra, 2002.
  * [Ban82] Victor Bangert.  Sets with positive reach.  Arch. Math. (Basel), 38(1):54–57, 1982.
  * [BBI01] D. Burago, Y. Burago, and S. Ivanov.  A course in metric geometry, volume 33 of Graduate Studies in Mathematics.  American Mathematical Society, Providence, RI, 2001.
  * [BGP92] Yu. Burago, M. Gromov, and G. Perelman.  A. D. Aleksandrov spaces with curvatures bounded below.  Uspekhi Mat. Nauk, 47(2(284)):3–51, 222, 1992.
  * [BN93] V. N. Berestovskij and I. G. Nikolaev.  Multidimensional generalized Riemannian spaces.  In Geometry, IV, volume 70 of Encyclopaedia Math. Sci., pages 165–243, 245–250. Springer, Berlin, 1993.
  * [CS04] Piermarco Cannarsa and Carlo Sinestrari.  Semiconcave functions, Hamilton-Jacobi equations, and optimal control, volume 58 of Progress in Nonlinear Differential Equations and their Applications.  Birkhäuser Boston, Inc., Boston, MA, 2004.
  * [DK81] Dennis M. DeTurck and Jerry L. Kazdan.  Some regularity theorems in Riemannian geometry.  Ann. Sci. École Norm. Sup. (4), 14(3):249–260, 1981.
  * [Fed69] H. Federer.  Geometric measure theory.  Die Grundlehren der mathematischen Wissenschaften, Band 153. Springer-Verlag New York Inc., New York, 1969.
  * [Gro07] Misha Gromov.  Metric structures for Riemannian and non-Riemannian spaces.  Modern Birkhäuser Classics. Birkhäuser Boston, Inc., Boston, MA, english edition, 2007.  Based on the 1981 French original, With appendices by M. Katz, P. Pansu and S. Semmes, Translated from the French by Sean Michael Bates.
  * [GS19] M. Ghomi and J. Sprouck.  Total curvature and the isoperimetric inequality in Cartan–Hadamard manifolds.  Preprint, https://arxiv.org/abs/1908.09814, 2019.
  * [KKK19] Vitali Kapovitch, Martin Kell, and Christian Ketterer.  On the structure of RCD spaces with upper curvature bounds.  arXiv:1908.07036, 2019.
  * [KL20] V. Kapovitch and A. Lytchak.  Structure of submetries.  Preprint, https://arxiv.org/abs/2007.01325, 2020.
  * [Kle81] Norbert Kleinjohann.  Nächste Punkte in der Riemannschen Geometrie.  Math. Z., 176(3):327–344, 1981.
  * [LN18] Alexander Lytchak and Koichi Nagano.  Geodesically complete spaces with an upper curvature bound.  arXiv:1804.05189, 2018.
  * [LN20] N. Lebedeva and A. Nepechiy.  Alexandrov regions.  Preprint, 2020.
  * [LW18] A. Lytchak and S. Wenger.  Isoperimetric characterization of upper curvature bounds.  Acta Math., 221, 2018.
  * [LY06] Alexander Lytchak and Asli Yaman.  On Hölder continuous Riemannian and Finsler metrics.  Trans. Amer. Math. Soc., 358(7):2917–2926, 2006.
  * [Lyt04] Alexander Lytchak.  On the geometry of subsets of positive reach.  Manuscripta Math., 115(2):199–205, 2004.
  * [Lyt05a] A. Lytchak.  Open map theorem for metric spaces.  Algebra i Analiz, 17(3):139–159, 2005.
  * [Lyt05b] Alexander Lytchak.  Almost convex subsets.  Geom. Dedicata, 115:201–218, 2005.
  * [MM03] Carlo Mantegazza and Andrea Carlo Mennucci.  Hamilton-Jacobi equations and distance functions on Riemannian manifolds.  Appl. Math. Optim., 47(1):1–25, 2003.
  * [Nik88] I. G. Nikolaev.  The Synge’s formula for geodesic variations in a space of bounded curvature by A. D. Aleksandrov.  preprint (Russian), 1988.
  * [Nik91] I. G. Nikolaev.  Bounded curvature closure of the set of compact Riemannian manifolds.  Bull. Amer. Math. Soc. (N.S.), 24(1):171–177, 1991.
  * [OS94] Y. Otsu and T. Shioya.  The Riemannian structure of Alexandrov spaces.  J. Differential Geom., 39(3):629–658, 1994.
  * [Per94] G. Perelman.  DC-structures on Alexandrov spaces.  preprint, preliminary version, 1994.
  * [Pet87] Stefan Peters.  Convergence of Riemannian manifolds.  Compositio Math., 62(1):3–16, 1987.
  * [Pet98] A. Petrunin.  Parallel transportation for Alexandrov space with curvature bounded below.  Geom. Funct. Anal., 8(1):123–148, 1998.
  * [Pet07] A. Petrunin.  Semiconcave functions in Alexandrov’s geometry.  In Surveys in differential geometry. Vol. XI, volume 11 of Surv. Differ. Geom., pages 137–201. Int. Press, Somerville, MA, 2007.
  * [RZ17] Jan Rataj and Luděk Zajíček.  On the structure of sets with positive reach.  Math. Nachr., 290(11-12):1806–1829, 2017.
  * [Sab93] I. Kh. Sabitov.  On the smoothness of isometries.  Sibirsk. Mat. Zh., 34(4):169–176, iv, x, 1993.
  * [Shi89] W.-X. Shi.  Deforming the metric on complete Riemannian manifolds.  J. Differential Geom., 30(1):223–301, 1989.
  * [Sv76] I. H. Sabitov and S. Z. Šefel.  Connections between the order of smoothness of a surface and that of its metric.  Sibirsk. Mat. Ž., 17(4):916–925, 1976.
  * [Tay00] Michael E. Taylor.  Tools for PDE, volume 81 of Mathematical Surveys and Monographs.  American Mathematical Society, Providence, RI, 2000.  Pseudodifferential operators, paradifferential operators, and layer potentials.
  * [Tay06] Michael Taylor.  Existence and regularity of isometries.  Trans. Amer. Math. Soc., 358(6):2415–2423, 2006.


11institutetext: Princeton University, Princeton, NJ, USA
11email<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>22institutetext: The University of British Columbia,Vancouver, BC, Canada

#  $\mathsf{EMA}$: Auditing Data Removal from Trained Models

Yangsibo Huang 11 Xiaoxiao Li Corresponding Author: Xiaoxiao Li,
<EMAIL_ADDRESS>Kai Li Corresponding Author: Kai Li,
<EMAIL_ADDRESS>
###### Abstract

Data auditing is a process to verify whether certain data have been removed
from a trained model. A recently proposed method [10] uses Kolmogorov-Smirnov
(KS) distance for such data auditing. However, it fails under certain
practical conditions. In this paper, we propose a new method called Ensembled
Membership Auditing ($\mathsf{EMA}$) for auditing data removal to overcome
these limitations. We compare both methods using benchmark datasets (MNIST and
SVHN) and Chest X-ray datasets with multi-layer perceptrons (MLP) and
convolutional neural networks (CNN). Our experiments show that $\mathsf{EMA}$
is robust under various conditions, including the failure cases of the
previously proposed method. Our code is available at:
https://github.com/Hazelsuko07/EMA.

###### Keywords:

Privacy Machine Learning Auditing

##  1 Introduction

Figure 1: EMA method consists of two steps: 1) the auditor first infers if
each sample in the query set is memorized by the target model; 2) then it
ensembles the results and see if the whole query set is memorized.

An important aspect of protecting privacy for machine learning is to verify if
certain data are used in the training of a machine learning model, i.e., data
auditing. Regulations such as GDPR [18] and HIPPA [1] require institutions to
allow individuals to revoke previous authorizations for the use of their data.
In this case, such data should be removed not only from storage systems, but
also from trained models.

Previous work focuses on data removal instead of data auditing. Some
investigate how training data can be memorized in model parameters or outputs
[20, 3] so as to show the importance of data removal. Others study data
removal methods from trained models, especially those that does not require
retraining the model [4, 2]. However, independent of how data is removed, in
order to meet the compliance of data privacy regulations, it is important,
especially for healthcare applications such as medical imaging analysis, to
have a robust data auditing process to verify if certain data are used in a
trained model.

The data auditing problem is an under-studied area. The closely related work
is by Liu et al. [10] who proposed an auditing method to verify if a query
dataset is removed, based on Kolmogorov-Smirnov (KS) distance and a
calibration dataset. However, the method may fail under certain practical
conditions, such as when the query dataset is similar to the training dataset
or when the calibration dataset is not of high quality.

To overcome these limitations, we propose an Ensembled Membership Auditing
($\mathsf{EMA}$) method, inspired by membership inference attacks [16], to
audit data removal from a trained model (see Fig. 1). It is a 2-step procedure
which ensembles multiple metrics and statistical tools to audit data removal.
To verify if a trained model memorizes a query dataset, first, $\mathsf{EMA}$
auditor infers whether the model memorizes each sample of the query dataset
based on various metrics. Second, $\mathsf{EMA}$ ensembles multiple membership
metrics and utilizes statistical tools to aggregate the sample-wise results
and obtain a final auditing score.

Our contributions are summarized as follows:

  1. 1.

We propose Ensembled Membership Auditing ($\mathsf{EMA}$), an effective method
to measure if certain data are memorized by the trained model.

  2. 2.

$\mathsf{EMA}$ method improves the cost-efficiency of the previous approach
[10], as it does not need to train a model on the query dataset.

  3. 3.

Our experiments on benchmark datasets and Chest X-ray datasets demonstrate
that our approach is robust under various practical settings, including the
conditions that the previous method fails.

##  2 Preliminary

###  2.1 Problem formulation

Our formulation of the data auditing problem is similar to that proposed by
Liu et al. [10]. Suppose the dataset $D$ is sampled from a given distribution
$\mathbb{D}\subset\mathbb{R}^{d}$, where $d$ denotes the input dimension. A
machine learning model $f_{D}:\mathbb{R}^{d}\rightarrow\mathcal{C}$ is trained
on $D$ to learn the mapping from an input to a label in the output space
$\mathcal{C}$. We denote the inference with a data point $x\in\mathbb{R}^{d}$
as $f_{D}(x)$. The auditory institution (or the auditor) aims to tell if a
query dataset $D_{\rm q}$ is memorized by the trained model $f_{D}$.

In real applications, most machine learning models for healthcare are provided
as Application Programming Interface (APIs). Users only have access to the
model outputs rather than model parameters, referred to as a black-box access.
Hence, similar to [10], we assume a black-box setting for data auditing: the
auditor has access to 1) the algorithm to train $f_{D}$, and 2)$f_{D}(D_{\rm
q})$, probability outputs of the query data $D_{\rm q}$ on $f_{D}$. The
auditor does not have access to the training dataset, nor the network
parameters of $f_{D}$.

###  2.2 Previous Method

Let us use $D$ to denote the training dataset and $D_{\rm cal}$ to denote the
calibration dataset. Liu et al. proposes an auditing method [10] that uses
Kolmogorov-Smirnov (KS) distance to compare the distance between
$f_{D}(D_{q})$ and $f_{D_{q}}(D_{q})$ and that between $f_{D_{cal}}(D_{q})$
and $f_{D_{q}}(D_{q})$, where $D$ and $D_{cal}$ are drawn from the same
domain. The criteria is defined as:

$\rho_{\rm KS}={KS(f_{D}(D_{\rm q}),f_{D_{\rm q}}(D_{\rm q}))}/{KS(f_{D_{\rm
cal}}(D_{\rm q}),f_{D_{\rm q}}(D_{\rm q}))},$ (1)

where $\rho_{\rm KS}\geq 1$ indicates the query dataset $D_{\rm q}$ has been
forgotten by $f_{D}$. However, the $\rho_{\rm KS}$ formula may fail in the
following scenarios:

  * •

when the query dataset is very similar to the original training dataset, the
numerator is small, which will lead to a false negative result;

  * •

when the calibration set is of low quality, the denominator is small, which
will lead to a false positive result.

Section 4 provides experimental results of the above limitations of using
$\rho_{\rm KS}$.

##  3 The Proposed Method

This section presents Ensembled Membership Auditing ($\mathsf{EMA}$), a 2-step
procedure to audit data removal from a trained model.

###  3.1 Membership Inference Attack

The key idea of our approach is inspired by the Membership Inference Attack
(MIA) [16], which shares a same black-box setting as that of auditing data
removal. A black-box MIA attacker aims to identify if a single datapoint is a
member of a machine learning model’s training dataset. Formally, given an
example $x$ and a target trained model $f_{D}$, MIA formulates a decision rule
$h$ and computse $h(x;f_{D})\in[0,1]$, the probability of $x$ being a member
of $f_{D}$’s training dataset. The final results are binarized by a threshold,
and $1$ indicates the membership. To formulate the decision rule $h$, in
addition to knowing trained model outputs, MIA requires knowing another set of
data (we refer to as calibration data), which is assumed to be similar to the
training dataset. Previous work suggests that the decision rule $h$ can either
be a machine learning model that is trained on the calibration data [16, 11,
15], or be thresholds of certain metrics that are computed using the
calibration data [17]. Motivated by recent successes of MIA on single data
points, we propose a framework that adapts MIA to audit whether a set of data
points is removed.

###  3.2 Ensembled Membership Auditing ($\mathsf{EMA}$)

We propose Ensembled Membership Auditing ($\mathsf{EMA}$), a 2-step auditing
scheme for data removal (see Algorithm 1): to verify if a query dataset is
memorized by a trained model, the auditor first infers if each sample is
memorized based on certain metrics, and then utilizes some statistical tools
to aggregate the sample-wise results and to infer the probability that the
query dataset is memorized. We name this probability as the $\mathsf{EMA}$
score and denote it by $\rho_{\rm EMA}$.

Algorithm 1 Ensembled Membership Auditing ($\mathsf{EMA}$)

Input: $A$, the training algorithm; $f_{D}$, the target model; $D_{\rm q}$,
the query dataset; $D_{\rm cal}$, the calibration dataset;
$g_{1},\cdots,g_{m}$, $m$ different metrics for membership testing.
Output: $\rho_{\rm EMA}\in[0,1]$, the possibility that $D_{\rm q}$ is
memorized by $f_{D}$

1:procedure EnsembledMembershipAuditing

2:
$\tau_{1},\cdots,\tau_{m}\leftarrow\textsc{InferMembershipThresholds}(A,D_{\rm
cal},g_{1},\cdots,g_{m})$

3: $\mathbf{M}\leftarrow\mathbf{0}$ $\triangleright$
$\mathbf{M}\in\\{0,1\\}^{|D_{\rm q}|}$, the inferred membership of each sample
in $D_{\rm q}$

4: for $(x_{i},y_{i})\in D_{\rm q}$ do

5:
$\mathbf{M}_{i}\leftarrow\mathbf{1}\\{g_{1}(f_{D},(x_{i},y_{i}))\geq\tau_{1}\\}\cup\mathbf{1}\\{g_{2}(f_{D},(x_{i},y_{i}))\geq\tau_{2}\\}\cup\cdots\cup\mathbf{1}\\{g_{m}(f_{D},(x_{i},y_{i}))\geq\tau_{m}\\}$

6: end for

7: $\rho_{\rm EMA}\leftarrow\textsc{2Samp-pvalue}(\mathbf{M},\mathbf{1})$
$\triangleright$ $\textsc{2Samp-pvalue}()$ returns the p-value of a two-sample
statistical test, which determines if two populations are from the same
distribution

8: return $\rho_{\rm EMA}$

9:end procedure

Algorithm 2 Infer Membership Thresholds [17]

Input: $A$, the training algorithm; $D_{\rm cal}$, the calibration dataset;
$g_{1},\cdots,g_{m}$, $m$ different metrics for membership testing.
Output: $\tau_{1},\cdots,\tau_{m}$, thresholds for $m$ different metrics for
membership inference.

1:procedure InferMembershipThresholds

2: Split $D_{\rm cal}$ into a training dataset $D_{\rm cal}^{\rm train}$ and a
test set $D_{\rm cal}^{\rm test}$

3: $f_{D_{\rm cal}}\leftarrow A(D_{\rm cal}^{\rm train})$ $\triangleright$
Train the calibration model

4: for $i\in[m]$ do

5: $\mathbf{V}_{\rm train}\leftarrow\\{g_{i}(f_{D_{\rm cal}},s)|s\in D_{\rm
cal}^{\rm train}\\}$ $\triangleright$ Compute metrics for training dataset

6: $\mathbf{V}_{\rm test}\leftarrow\\{g_{i}(f_{D_{\rm cal}},s)|s\in D_{\rm
cal}^{\rm test}\\}$ $\triangleright$ Compute metrics for test dataset

7: $\tau_{i}\leftarrow\arg\max_{\tau\in[\mathbf{V}_{\rm train},\mathbf{V}_{\rm
test}]}(BA(\tau))$ $\triangleright$ Infer the threshold based on Eq 2

8: end for

9: return $\tau_{1},\cdots,\tau_{m}$

10:end procedure

Table 1: Comparing $\mathsf{EMA}$ with the method by Liu et al. [10]. |  Calibration model |  Query model |  High quality calibration set |  Query data similar to training data
---|---|---|---|---
$\mathsf{EMA}$ |  Need to train |  No need to train |  No Need |  Robust
Liu et al. |  Need to train |  Need to train |  Need |  Not robust

Step 1: Infer if each sample is memorized. Given the target model $f_{D}$,
which is trained with training dataset $D$, and query dataset $D_{\rm q}$, the
first step infers if each sample in $D_{\rm q}$ is memorized by $f_{D}$ (see
Algorithm 1, line 2 to line 6). The auditor first computes
$\tau_{1},\cdots,\tau_{m}$, thresholds for $m$ different metrics by running a
standard membership inference pipeline [17] on the calibration set. To select
thresholds to identify training data, we define balanced accuracy on
calibration data based on the balanced accuracy regarding True Positive Rate
(TPR) and True Negative Rate (TNR):

$BA(\tau)=\frac{TPR(\tau)+TNR(\tau)}{2}$ (2)

where given a threshold $\tau$, $TPR(\tau)=\sum_{s\in D_{\rm cal}^{\rm
train}}\mathbf{1}\\{g_{i}(s)\geq\tau\\}/|D_{\rm cal}^{\rm train}|$, and
$TNR(\tau)=\sum_{s\in D_{\rm cal}^{\rm
test}}\mathbf{1}\\{g_{i}(s)\geq\tau\\}/|D_{\rm cal}^{\rm test}|$. The best
threshold is selected to maximize the balanced accuracy (see Algorithm 2). For
each sample in $D_{\rm q}$, it will be inferred as a member or memorized by
the target model, if it gets a membership score higher than the threshold for
at least one metric (Algorithm 1, line 3 to 6). The auditor stores the
membership results in ${\bf M}\in\\{0,1\\}^{|D_{\rm q}|}$: $\mathbf{M}_{i}=1$
indicates that the $i$-th sample in $D_{\rm q}$ is inferred as memorized by
$f_{D}$, and $\mathbf{M}_{i}=0$ indicates otherwise.

Our scheme uses the following 3 metrics for membership inference [17]:
\- Correctness: $g_{\rm
corr}(f,(x,y))=\mathbf{1}\\{\arg\max_{i}~{}f(x)_{i}=y\\}$
\- Confidence: $g_{\rm conf}(f,(x,y))=f(x)_{y}$
\- Negative entropy: $g_{\rm entr}(f,(x,y))=\sum_{i}f(x)_{i}\log(f(x)_{i})$

Step 2: Aggregate sample-wise auditing results. Given $\mathbf{M}$, the
sample-wise auditing results from step 1, the auditor infers if the whole
query dataset is memorized. A simple approach is to perform majority voting on
$\mathbf{M}$, however, the state-of-the-art MIA approaches[17] achieve only
$\sim$70% accuracy with benchmark datasets. Majority voting may not achieve
reliable results.

The unreliability of a single entry in $\mathbf{M}$ motivates us to consider
using the distribution of $\mathbf{M}$: ideally, if a query dataset
$D_{q}^{*}$ is memorized, it should give $\mathbf{M}_{D_{q}^{*}}=\mathbf{1}$.
Thus, we run a two-sample statistical test: we fix one sample to be
$\mathbf{1}$ (an all-one vector), and use $\mathbf{M}$ as the second sample.
We set the null hypothesis to be that 2 samples are drawn from the same
distribution (i.e., $\mathbf{M}$ is the sample-wise auditing results for a
memorized query dataset). The test will return a p-value, which is the final
output of our $\mathsf{EMA}$ scheme, and we denote it as $\rho_{\rm EMA}$. We
interpret $\rho_{\rm EMA}$ as follow: if $\rho_{\rm EMA}\leq\alpha$, the
auditor can reject the null hypothesis, and conclude that the query dataset is
not memorized. Here, $\alpha$ is the threshold for statistical significance,
and is set to 0.1 by default.

Comparison with the previous method. Table 1 lists the differences between our
method and Liu et al.’s [10]. As shown, our approach is more cost-efficient
since it does not require training a model on the query dataset. It also
addresses limitations of the previous method by avoiding possible false-
positive (due to low quality calibration data) and false-negative cases (due
to similar query data to training data), which we are going to show in the
next section.

##  4 Experiments

We conduct two experiments to validate $\mathsf{EMA}$ and compare it with the
method by Liu et al. [10]. The first (see Section 4.1) uses benchmark datasets
(MNIST and SVHN) and the second (see Section 4.2) uses Chest X-ray datasets.
Both methods are implemented in Pytorch framework [13]. We present the main
results by using t-test as the statistical aggregation step of $\mathsf{EMA}$.
Appendix 0.B provides the results of $\mathsf{EMA}$ using different
statistical tests, and more results under various constraints of the query
dataset.

###  4.1 Benchmark Datasets (MNIST and SVHN)

We start with verifying the feasibility of $\mathsf{EMA}$ and explaining the
experiment setting on benchmark datasets for the ease of understanding. 111The
real medical data experiment follows the similar setting. MNIST dataset [9]
contains 60,000 images with image size $28\times 28$. SVHN dataset [12]
contains 73,257 images in natural scenes with image size $32\times 32$. We
generate the training dataset, the calibration set, and the query dataset as
follow.

#### Training dataset.

We randomly sample 10,000 images from MNIST as the training dataset and split
it equally to 5 non-overlapping folds. Each fold contains 2,000 images.

#### Calibration set.

We sample 1,000 images from MNIST (disjoint with the training dataset) as the
calibration set . To simulate a low-quality calibration set in practice, we
keep $k\%$ of the original images, add random Gaussian noise to
$(100-k)/{2}\%$ of the images, and randomly rotate the other $(100-k)/{2}\%$
of the images. We vary $k$ in our evaluation.

$\mathbf{k}$ | M1 | M2 | M3 | M4 | M5 | M6 | S
---|---|---|---|---|---|---|---
100 | 0.91 | 0.90 | 0.90 | 0.89 | 0.90 | 0.82 | 2.34
90 | 0.96 | 0.95 | 0.96 | 0.95 | 0.95 | 0.86 | 2.59
80 | 0.98 | 0.95 | 0.97 | 0.95 | 0.96 | 0.87 | 3.75
70 | 0.98 | 0.96 | 0.97 | 0.96 | 0.96 | 0.88 | 1.08
60 | 1.02 | 0.99 | 1.01 | 1.00 | 0.99 | 0.90 | 4.74
50 | 1.07 | 1.04 | 1.06 | 1.05 | 1.05 | 0.94 | 2.62
(a) $\rho_{\rm KS}$ scores of method by Liu et al.

$\mathbf{k}$ | M1 | M2 | M3 | M4 | M5 | M6 | S
---|---|---|---|---|---|---|---
100 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
90 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
80 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
70 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
60 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
50 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
(b) $\rho_{\rm EMA}$ scores of $\mathsf{EMA}$ (t-test)

Table 2: Auditing scores of both methods on benchmark datasets. Each column
corresponds to a query dataset, and each row corresponds to a calibration set
with quality controlled by $k$. False positive results are in red, while false
negative results are in blue.

(a) The benchmark dataset

(b) The chest X-ray dataset

Figure 2: Distribution of correctness, confidence, and negative entropy scores
of query datasets M1 (memorized), M6 and S (not memorized) for benchmark
dataset; of query datasets C1 (memorized), C6 and R (not memorized) for chest
X-ray dataset.

#### Query dataset.

We design the following three kinds of query dataset:
\- $\\{\rm\bf M1,M2,M3,M4,M5\\}$: 5 folds of MNIST images used in training,
each with 2,000 images;
\- $\rm\bf M6$: 2,000 images randomly selected from the MNIST dataset
(disjoint with the training and the calibration set);
\- $\rm\bf S$: 2,000 images randomly selected from the SVHN dataset.

#### Target model.

The target model is a three-layer multi-layer perceptron of hidden size (256,
256). Its training uses SGD optimizer [14] with learning rate 0.05 run for 50
epochs. The learning rate decay is set to $10^{-4}$.

Results and discussion. Fig.2(a) shows that the distribution of metrics on M1
(memorized) is clearly distinguishable from those of M6 and S (not memorized).
This validate that $\mathsf{EMA}$ can be used to infer whether a query dataset
is memorized by the target model.

EMA gives correct auditing results even when the calibration set is of low
quality, while the method by Liu et al. [10] may fail. Note that for method by
Liu et al., $\rho_{\rm KS}\leq 1$ indicates that the dataset is removed. For
$\mathsf{EMA}$, $\rho_{\rm EMA}\leq\alpha$ ($\alpha=0.1$) indicates that the
dataset is removed. Table 2(a) shows when a query dataset is included in the
training dataset of the target model (columns ‘M1’ to ‘M5’) and the
calibration set’s quality the calibration set’s quality drops to $k=60$, Liu
et al. [10] returns false positive results on M1, M3, and M4 (i.e. $\rho_{\rm
KS}\geq 1$) On the contrary, $\mathsf{EMA}$ returns correct $\mathsf{EMA}$
scores despite variations in the quality of the calibration set.

Liu et al.’s method fails when the query dataset is similar to but not
included in the training dataset (shown in column ‘M6’ in Table 2(a)). By
contrast, $\mathsf{EMA}$ is robust for such a scenario. Both methods give
correct answers for query dataset ‘S’ from SVHN whose appearance is
significantly different from that of MNIST.

(a) $k=100$

(b) $k=80$

(c) $k=60$

Figure 3: Visualization of $f_{D_{\rm tr}}(D_{\rm q})$, $f_{D_{\rm
cal}}(D_{\rm q})$, and $f_{D_{\rm q}}(D_{\rm q})$ of the Chest X-ray datasets,
with the query dataset is included in the training dataset. $f_{D_{\rm
tr}}(D_{\rm q})$ highly overlaps with $f_{D_{\rm q}}(D_{\rm q})$, but the KS
distance between them is larger than the KS distance between $f_{D_{\rm
cal}}(D_{\rm q})$ and $f_{D_{\rm q}}(D_{\rm q})$. This suggests KS distance
may not be a good measure of distributions of prediction outputs.

###  4.2 Chest X-ray Datasets

We further evaluate $\mathsf{EMA}$ on medical image analysis. We use two Chest
X-ray datasets, including COVIDx [19], a recent public medical image dataset
which contains 15,173 Chest X-ray images, and the Childx dataset [7], which
contains 5,232 Chest X-ray images from children. We perform pneumonia/normal
classification on both datasets. Appendix 0.A.1 provides details and sample
images of both datasets. We describe the training dataset, the calibration
set, and the query dataset as follow.

#### Training dataset.

We randomly sample 4,000 images from COVIDx as the training dataset and split
it equally to 5 non-overlapping folds. Each fold contains 800 images.

#### Calibration set.

We generate the calibration set using a subset of the COVIDx dataset, which is
disjoint with the training dataset and contains 4,000 images as well. To
simulate a potentially low-quality calibration set, we keep $k\%$ of the
original images, and add random Gaussian noise to $(100-k)\%$ of the images.

#### Query dataset.

We evaluate with different query datasets, including
\- $\\{\rm\bf C1,C2,C3,C4,C5\\}$, 5 folds of COVIDx images used in training,
each with 800 images;
\- $\rm\bf C6$, 800 images randomly selected from the COVIDx dataset (disjoint
with the training and the calibration set);
\- $\rm\bf R$, 800 images randomly selected from the Childx dataset.

#### Target model.

The target model is ResNet-18 [5]. We use the Adam optimizer [8] with learning
rate $2\times 10^{-5}$ and run for 30 epochs (weight decay is set to
$10^{-7}$).

$\mathbf{k}$ | C1 | C2 | C3 | C4 | C5 | C6 | R
---|---|---|---|---|---|---|---
100 | 1.19 | 1.20 | 1.23 | 1.20 | 1.21 | 0.99 | 0.53
90 | 1.25 | 1.28 | 1.23 | 1.24 | 1.25 | 1.01 | 0.71
80 | 1.26 | 1.27 | 1.2 | 1.22 | 1.21 | 1.00 | 0.96
70 | 1.28 | 1.26 | 1.24 | 1.21 | 1.24 | 1.02 | 0.73
60 | 1.32 | 1.32 | 1.31 | 1.26 | 1.31 | 1.09 | 1.06
(a) $\rho_{\rm KS}$ scores of method by Liu et al.

$\mathbf{k}$ | C1 | C2 | C3 | C4 | C5 | C6 | R
---|---|---|---|---|---|---|---
100 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
90 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
80 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
70 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
60 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
(b) $\rho_{\rm EMA}$ scores of $\mathsf{EMA}$ (t-test)

Table 3: Auditing scores of both methods on Chest X-ray datasets. Each column
corresponds to a query dataset, and each row corresponds to a calibration set
with quality controlled by $k$. False positive results are in red while false
negative results are in blue.

Results and Discussion. The results further validate $\mathsf{EMA}$ can be
used to infer whether a query dataset is memorized by the target model. As
shown in Fig. 2(b), the distribution of membership metrics on C1 (memorized)
is clearly distinguishable from those of C6 and R (not memorized); however,
the difference between distributions of metrics for memorized and not-
memorized query datasets is smaller when compared to that on benchmark
datasets. One potential rationale for this difference is that we perform a
10-way classification on benchmark datasets, but only do a binary
classification for Chest X-ray datasets. Thus, the auditor may get less
information from the final prediction of the target model on Chest X-ray
datasets, as the the final prediction has fewer classes.

When the query dataset is a subset of the training dataset (columns ‘C1’ to
‘C5’ in Table 3), $\mathsf{EMA}$ correctly indicates that the query dataset is
memorized ($\rho_{\rm EMA}=1$), whereas the results of the method by Liu et
al. [10] are all false positive.

For the case where the query dataset is not included in the training dataset
(columns C6 and R in Table 3), $\mathsf{EMA}$ always gives correct answers
when the quality level of the calibration set is equal to or higher than
$k=60$, namely with less than $40\%$ noisy data. However, the method by Liu et
al. gives a false positive result for C6 when $k=100$ and all false positive
results for R when $k>60$.

A possible explanation why the method by Liu et al. fails is that KS distance
may not be a good measure when the number of classes is small (see Fig. 3).

##  5 Conclusion

This paper presents $\mathsf{EMA}$, a 2-step robust data auditing procedure to
verify if certain data are used in a trained model or if certain data has been
removed from a trained model. By examining if each data point of a query set
is memorized by a target model and then aggregating sample-wise auditing
results, this method not only overcomes two main limitations of the state-of-
the-art, but also improves efficiency. Our experimental results show that
$\mathsf{EMA}$ is robust for medical images, comparing with the state-of-the-
art, under practical settings, such as lower-quality calibration dataset and
statistically overlapping data sources.

Future work includes testing $\mathsf{EMA}$ with more medical imaging tasks,
and more factors that may affect the algorithm’s robustness, such as the
requirements of the calibration data, different training strategies and
models, and other aggregation methods.

## Acknowledgement

This project is supported in part by Princeton University fellowship and
Amazon Web Services (AWS) Machine Learning Research Awards. The authors would
like to thank Liwei Song and Dr. Quanzheng Li for helpful discussions.

## References

  * [1] Act, A.: Health insurance portability and accountability act of 1996. Public law 104, 191 (1996)
  * [2] Bourtoule, L., Chandrasekaran, V., Choquette-Choo, C.A., Jia, H., Travers, A., Zhang, B., Lie, D., Papernot, N.: Machine unlearning. arXiv preprint arXiv:1912.03817 (2019)
  * [3] Carlini, N., Liu, C., Erlingsson, Ú., Kos, J., Song, D.: The secret sharer: Evaluating and testing unintended memorization in neural networks. In: 28th USENIX Security Symposium (USENIX Security 19). pp. 267–284. USENIX Association, Santa Clara, CA (Aug 2019), https://www.usenix.org/conference/usenixsecurity19/presentation/carlini
  * [4] Guo, C., Goldstein, T., Hannun, A., Maaten, L.v.d.: Certified data removal from machine learning models. arXiv preprint arXiv:1911.03030 (2019)
  * [5] He, K., Zhang, X., Ren, S., Sun, J.: Deep residual learning for image recognition. In: Proceedings of the IEEE conference on computer vision and pattern recognition. pp. 770–778 (2016)
  * [6] Kermany, D., Zhang, K., Goldbaum, M., et al.: Labeled optical coherence tomography (oct) and chest x-ray images for classification. Mendeley data 2(2) (2018)
  * [7] Kermany, D.S., Goldbaum, M., Cai, W., Valentim, C.C., Liang, H., Baxter, S.L., McKeown, A., Yang, G., Wu, X., Yan, F., et al.: Identifying medical diagnoses and treatable diseases by image-based deep learning. Cell 172(5), 1122–1131 (2018)
  * [8] Kingma, D.P., Ba, J.: Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 (2014)
  * [9] LeCun, Y., Cortes, C.: MNIST handwritten digit database (2010), http://yann.lecun.com/exdb/mnist/
  * [10] Liu, X., Tsaftaris, S.A.: Have you forgotten? a method to assess if machine learning models have forgotten data. In: International Conference on Medical Image Computing and Computer-Assisted Intervention. pp. 95–105. Springer (2020)
  * [11] Nasr, M., Shokri, R., Houmansadr, A.: Machine learning with membership privacy using adversarial regularization. In: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. pp. 634–646 (2018)
  * [12] Netzer, Y., Wang, T., Coates, A., Bissacco, A., Wu, B., Ng, A.Y.: Reading digits in natural images with unsupervised feature learning (2011)
  * [13] Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., et al.: Pytorch: An imperative style, high-performance deep learning library. arXiv preprint arXiv:1912.01703 (2019)
  * [14] Ruder, S.: An overview of gradient descent optimization algorithms. arXiv preprint arXiv:1609.04747 (2016)
  * [15] Salem, A., Zhang, Y., Humbert, M., Berrang, P., Fritz, M., Backes, M.: Ml-leaks: Model and data independent membership inference attacks and defenses on machine learning models. arXiv preprint arXiv:1806.01246 (2018)
  * [16] Shokri, R., Stronati, M., Song, C., Shmatikov, V.: Membership inference attacks against machine learning models. In: 2017 IEEE Symposium on Security and Privacy (SP). pp. 3–18. IEEE (2017)
  * [17] Song, L., Mittal, P.: Systematic evaluation of privacy risks of machine learning models. arXiv preprint arXiv:2003.10595 (2020)
  * [18] Voigt, P., Von dem Bussche, A.: The EU general data protection regulation (GDPR). Intersoft consulting (2018)
  * [19] Wang, L., Lin, Z.Q., Wong, A.: Covid-net: A tailored deep convolutional neural network design for detection of covid-19 cases from chest x-ray images. Scientific Reports 10(1), 1–12 (2020)
  * [20] Zhang, Y., Jia, R., Pei, H., Wang, W., Li, B., Song, D.: The secret revealer: Generative model-inversion attacks against deep neural networks. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 253–261 (2020)

##  Appendix 0.A Experiment details

###  0.A.1 Details of Chest X-ray datasets

The Covid19 X-ray dataset. COVIDx [19] is a recent public medical image
dataset which contains near 16,000 chest x-ray (CXR) images. Some participants
are associated with more than one CXR. To simplify membership evaluation, we
only keep the patients with one CXR, ending up with 15,173 cases and CXR
images. We show some examples in Figure 4.

(a) Normal people

(b) Pneumonia patients

Figure 4: Examples of Chest X-ray images of normal people (a) and pneumonia
patients (b) in the Covid19 X-ray dataset.

The Childx dataset. The Childx dataset is a Chest X-ray dataset selected from
retrospective cohorts of pediatric patients of one to five years old from
Guangzhou Women and Children’s Medical Center, Guangzhou [6]. This dataset
contains a total of 5,232 chest X-ray images from children, including 3,883
characterized as depicting pneumonia and 1,349 normal. We show some examples
in Figure 5.

(a) Normal people

(b) Pneumonia patients

Figure 5: Examples of Chest X-ray images of normal people (a) and pneumonia
patients (b) in the Childx dataset. We crop original images to square format
for better visualization.

##  Appendix 0.B Ablation study

###  0.B.1 Kolmogorov–Smirnov-test v.s t-test

We first evaluate the performance of $\mathsf{EMA}$ using two different
statistical tests, including the two-sample Kolmogorov–Smirnov test and the
two-sample t-test between the sample-wise auditing result $\mathbf{M}$ and
$\mathbf{1}$: 1) the Kolmogorov–Smirnov statistic quantifies the distance
between the empirical distribution function of both samples; 2) the t-test
statistic is defined as $\frac{\mu_{M}-1}{(\sigma_{M}+10^{8})/\sqrt{|M|}}$,
where $\mu_{M}$ and $\sigma_{M}$ are the element-wise mean and the standard
deviation of the vector $\mathbf{M}$.

As shown in Table 4, the t-test always outperforms the Kolmogorov–Smirnov
test, under different tasks and with calibration datasets of different
qualities. A possible explanation is that both $\mathbf{M}$ and $\mathbf{1}$
are binary vectors, thus are not suitable for the Kolmogorov–Smirnov statistic
which is designed to measure the distance between continuous distributions.

$\mathbf{k}$ | M1 | M2 | M3 | M4 | M5 | M6 | S
---|---|---|---|---|---|---|---
100 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.10 | 0.00
90 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.08 | 0.00
80 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.11 | 0.00
70 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.08 | 0.00
60 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.12 | 0.00
50 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.27 | 0.00
(a) $\rho_{\rm EMA}$, using K-S test, benchmark dataset

$\mathbf{k}$ | M1 | M2 | M3 | M4 | M5 | M6 | S
---|---|---|---|---|---|---|---
100 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
90 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
80 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
70 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
60 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
50 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
(b) $\rho_{\rm EMA}$, using t-test, benchmark dataset

$\mathbf{k}$ | C1 | C2 | C3 | C4 | C5 | C6 | R
---|---|---|---|---|---|---|---
100 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.02 | 0.05
90 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
80 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
70 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
60 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
50 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
(c) $\rho_{\rm EMA}$, using KS-test, Chest X-ray dataset

$\mathbf{k}$ | C1 | C2 | C3 | C4 | C5 | C6 | R
---|---|---|---|---|---|---|---
100 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
90 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
80 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
70 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
60 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
50 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
(d) $\rho_{\rm EMA}$, using t-test, Chest X-ray dataset

Table 4: Auditing results of $\mathsf{EMA}$ using different statistical tests
on the benchmark (the first row) and Chest X-ray (the second row) datasets.
False positive results are in red, while false negative results are in blue.

###  0.B.2 Varying size of the query dataset

We also evaluate the robustness of the $\mathsf{EMA}$ approach by varying
$D_{q}$, the size of the query dataset. As shown in Table 5, for the benchmark
dataset, $\mathsf{EMA}$ gives correct answers if $D_{q}>200$; when $D_{q}\leq
200$, the performance of $\mathsf{EMA}$ will be affected if the calibration
dataset is not of perfect quality, i.e. $k<100$. For the Chest X-ray dataset,
$\mathsf{EMA}$ gives correct answers if $D_{q}>20$ (see Table 6), which
suggests that $\mathsf{EMA}$ is quite robust even with a very small query
dataset.

$\mathbf{k}$ | M1 | M2 | M3 | M4 | M5 | M6 | S
---|---|---|---|---|---|---|---
100 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
90 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
80 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
70 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
60 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
50 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
(a) $\rho_{\rm EMA}$, $|D_{q}|=2,000$

$\mathbf{k}$ | M1 | M2 | M3 | M4 | M5 | M6 | S
---|---|---|---|---|---|---|---
100 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
90 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
80 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
70 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
60 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
50 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
(b) $\rho_{\rm EMA}$, $|D_{q}|=500$

$\mathbf{k}$ | M1 | M2 | M3 | M4 | M5 | M6 | S
---|---|---|---|---|---|---|---
100 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.01 | 0.00
90 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
80 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.01 | 0.00
70 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.08 | 0.00
60 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.32 | 0.00
50 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.01 | 0.00
(c) $\rho_{\rm EMA}$, $|D_{q}|=200$

$\mathbf{k}$ | M1 | M2 | M3 | M4 | M5 | M6 | S
---|---|---|---|---|---|---|---
100 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.16 | 0.00
90 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.16 | 0.00
80 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.32 | 0.00
70 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00
60 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00
50 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.32 | 0.00
(d) $\rho_{\rm EMA}$, $|D_{q}|=50$

$\mathbf{k}$ | M1 | M2 | M3 | M4 | M5 | M6 | S
---|---|---|---|---|---|---|---
100 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.32 | 0.00
90 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.32 | 0.00
80 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00
70 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00
60 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00
50 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00
(e) $\rho_{\rm EMA}$, $|D_{q}|=20$

$\mathbf{k}$ | M1 | M2 | M3 | M4 | M5 | M6 | S
---|---|---|---|---|---|---|---
100 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.35 | 0.00
90 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00
80 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00
70 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00
60 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00
50 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00
(f) $\rho_{\rm EMA}$, $|D_{q}|=5$

Table 5: Auditing results of $\mathsf{EMA}$ with query datasets of different
sizes on the benchmark dataset. Size of the query datasets are annotated as
$|D_{q}|$ in sub-captions. False positive results are in red, while false
negative results are in blue.

$\mathbf{k}$ | C1 | C2 | C3 | C4 | C5 | C6 | R
---|---|---|---|---|---|---|---
100 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
90 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
80 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
70 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
60 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
50 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
(a) $\rho_{\rm EMA}$, $|D_{q}|=800$

$\mathbf{k}$ | C1 | C2 | C3 | C4 | C5 | C6 | R
---|---|---|---|---|---|---|---
100 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
90 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
80 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
70 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
60 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
50 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
(b) $\rho_{\rm EMA}$, $|D_{q}|=500$

$\mathbf{k}$ | C1 | C2 | C3 | C4 | C5 | C6 | R
---|---|---|---|---|---|---|---
100 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
90 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
80 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
70 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
60 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
50 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
(c) $\rho_{\rm EMA}$, $|D_{q}|=200$

$\mathbf{k}$ | C1 | C2 | C3 | C4 | C5 | C6 | R
---|---|---|---|---|---|---|---
100 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.01 | 0.04
90 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
80 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.01 | 0.00
70 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.01 | 0.00
60 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.01 | 0.00
50 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00 | 0.00
(d) $\rho_{\rm EMA}$, $|D_{q}|=50$

$\mathbf{k}$ | C1 | C2 | C3 | C4 | C5 | C6 | R
---|---|---|---|---|---|---|---
100 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.15 | 0.07
90 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.02 | 0.04
80 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.07 | 0.01
70 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.32 | 0.04
60 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.04 | 0.04
50 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.04 | 0.04
(e) $\rho_{\rm EMA}$, $|D_{q}|=20$

$\mathbf{k}$ | C1 | C2 | C3 | C4 | C5 | C6 | R
---|---|---|---|---|---|---|---
100 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00
90 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.35 | 0.14
80 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.14
70 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.35
60 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.14 | 1.00
50 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.14 | 0.35
(f) $\rho_{\rm EMA}$, $|D_{q}|=5$

Table 6: Auditing results of $\mathsf{EMA}$ with query datasets of different
sizes on the Chest X-ray dataset. Size of the query datasets are annotated as
$|D_{q}|$ in sub-captions. False positive results are in red, while false
negative results are in blue.