which implies that the output $\mathbf{\hat{y}}$ will be replaced by its
approximate mean $\mathbf{\hat{y}^{\prime}}$ per manifold which by Lemma 38
reduces the weighted square loss. $A$ remains unchanged and $B$’s Frobenius
norm has not increased. So the value of the minimization objective overall has
reduced which is a contradiction to Lemma 35 which states that all minima are
global in our setting. ∎

Lemma 42 implies that property (A) holds on the train examples from the train
manifolds.

####  D.1.2 Property (B) of GSH for Linear Manifolds

Next we prove a bunch of Lemmas for showing property (B) of GSH for linear
manifolds. In this section, without loss of generality we will assume that $m$
is even. If it is not, we drop the samples from the $m^{th}$ manifold and set
the new value of $m$ to be $m-1$. We will use the fact that our train loss is
small. The following Lemmas will argue that when the train loss is small, the
average of the inter-manifold representation distance over all pairs of our
train manifolds is small.

######  Lemma 43.

Let $\mathbf{a}\in\mathbb{R}^{T}$ such that $\|\mathbf{a}\|_{2}\leq\delta$.
Let $\mathbf{b_{1}},\mathbf{b_{2}}\in\mathbb{R}^{T}$ be such that

$\frac{1}{2}\left(\mathbf{a}^{\top}\mathbf{b_{1}}\right)^{2}+\frac{1}{2}\left(1-\mathbf{a}^{\top}\mathbf{b_{2}}\right)^{2}\leq\varepsilon.$

Then

$\|\mathbf{b_{1}}-\mathbf{b_{2}}\|_{2}^{2}\geq\frac{1-4\sqrt{\varepsilon}}{\delta^{2}}.$

###### Proof.

Let $(\mathbf{a}^{\top}\mathbf{b_{1}})^{2}=2\varepsilon_{1}$ and let
$\varepsilon_{2}=\varepsilon-\varepsilon_{1}$. Then,

$\displaystyle\left\lvert\mathbf{a}^{\top}\mathbf{b_{1}}\right\rvert\leq\sqrt{2\varepsilon_{1}}\;\;\text{and}\;\;\left\lvert
1-\mathbf{a}^{\top}\mathbf{b_{2}}\right\rvert\leq\sqrt{2\varepsilon_{2}}$ (29)
$\displaystyle\implies$
$\displaystyle\lvert\mathbf{a}^{\top}(\mathbf{b_{2}}-\mathbf{b_{1}})\rvert\geq
1-\sqrt{2\varepsilon_{1}}-\sqrt{2\varepsilon_{2}}\geq 1-2\sqrt{\varepsilon}$
(30) $\displaystyle\implies$
$\displaystyle\|\mathbf{a}\|_{2}\|\mathbf{b_{2}}-\mathbf{b_{1}}\|_{2}\geq
1-\sqrt{2\varepsilon}\implies\|\mathbf{b_{2}}-\mathbf{b_{1}}\|_{2}\geq\frac{1-2\sqrt{\varepsilon}}{\delta}$
(31) $\displaystyle\implies$
$\displaystyle\|\mathbf{b_{2}}-\mathbf{b_{1}}\|_{2}^{2}\geq\frac{1+4\varepsilon-4\sqrt{\varepsilon}}{\delta^{2}}\geq\frac{1-4\sqrt{\varepsilon}}{\delta^{2}}.$
(32)

where we used that $\sqrt{2(a+b)}\geq\sqrt{a}+\sqrt{b}$. ∎

######  Lemma 44.

For $l\in[m]$, let

$\displaystyle H(l)=\frac{1}{n(m-1)}\sum_{j\neq
l}\sum_{i=1}^{n}\|B\sigma(C\mathbf{x_{il}})-B\sigma(C\mathbf{x_{ij}})\|_{2}^{2},$
(33)
$\displaystyle\varepsilon_{l}=\frac{1}{n(m-1)}\sum_{i=1}^{n}\left[\sum_{j\neq
l}\varepsilon_{ijl}\right],$ (34) $\displaystyle\text{where
}\varepsilon_{ijl}=\frac{1}{2}\left(A_{l}B\sigma(C\mathbf{x_{ij}})\right)^{2}+\frac{1}{2}\left(1-A_{l}B\sigma(C\mathbf{x_{il}}\right)^{2}.$
(35)

We have,

$H(l)\geq\frac{1-4\sqrt{\varepsilon_{l}}}{\|A_{l}\|_{2}^{2}}.$

###### Proof.

From Lemma 43 we have

$\displaystyle\|B\sigma(C\mathbf{x_{il}})-B\sigma(C\mathbf{x_{ij}})\|_{2}^{2}\geq\frac{1-4\sqrt{\varepsilon_{ijl}}}{\|A_{l}\|_{2}^{2}}$
(36) $\displaystyle\implies$
$\displaystyle\frac{1}{n(m-1)}\sum_{i=1}^{n}\sum_{j\neq
l}\|B\sigma(C\mathbf{x_{il}})-B\sigma(C\mathbf{x_{ij}})\|_{2}^{2}\geq\frac{1}{n(m-1)}\frac{n(m-1)-4n(m-1)\sqrt{\varepsilon_{l}}}{\|A_{l}\|_{2}^{2}}$
(37)
$\displaystyle~{}~{}=\frac{1-4\sqrt{\varepsilon_{l}}}{\|A_{l}\|_{2}^{2}},$
(38)

where we have used that
$\sum_{k=1}^{c}\sqrt{a_{k}}\leq\sqrt{c}\cdot\sqrt{\sum_{k=1}^{n}a_{k}}$. ∎

######  Lemma 45 (Small Weighted Square Loss Implies Distant Representations).

For $l\in[m]$, let

$\displaystyle H(l)=\frac{1}{n(m-1)}\sum_{j\neq
l}\sum_{i=1}^{n}\|B\sigma(C\mathbf{x_{il}})-B\sigma(C\mathbf{x_{ij}})\|_{2}^{2}$
(39) $\displaystyle\varepsilon=\mathcal{L}_{A,B}(Y,\hat{Y}),$ (40)

Then,

$\frac{1}{m}\sum_{l=1}^{m}H(l)\geq\frac{m(1-O(\sqrt{\varepsilon}))}{O(\|A\|_{F}^{2})}.$

###### Proof.

First note that $\varepsilon=\sum_{l=1}^{m}\varepsilon_{l}/m$ and let
$\delta=\sum_{l=1}^{m}\|A_{l}\|_{2}^{2}/m$. From Markov’s inequality we have
that there exists $S_{1}\subseteq[m]$ such that $|S_{1}|=\lceil 9m/10\rceil$
and $\forall l\in S_{1},\varepsilon_{l}\leq 10\varepsilon$. Similarly there
exists $S_{2}\subseteq[m]$, $|S_{2}|=\lceil 9m/10\rceil$ such that $\forall
l\in S_{2},\|A_{l}\|_{2}^{2}\leq 10\delta$. Note that $|S_{1}\cap
S_{2}|\geq\lceil 8m/10\rceil$. We have,

$\displaystyle\frac{1}{m}\sum_{l=1}^{m}H(l)\geq\frac{1}{m}\sum_{l\in|S_{1}\cap
S_{2}|}H(l)\geq\frac{8}{10}\cdot\frac{1-4\sqrt{10\varepsilon}}{10\delta}=\frac{m(1-O(\sqrt{\varepsilon}))}{O(\|A\|_{F}^{2})},$
(41)

where we used Lemma 44. ∎

Now since at any local minimum
$\mathcal{L}_{\hat{A},\hat{B}}(Y,\hat{Y})\leq\varepsilon$ and
$\|\hat{A}\|_{F}^{2}\leq 3m$, Lemma 45 gives property (B) on the train data.

###  D.2 GSH on Train Data for Non-Linear Manifolds With Intra-Class Variance
Regularization

For non-linear manifolds, the argument we had in Section D.1 does not go
through as is. This is because we no longer have as nice a mapping from
monomials of $\mathbf{x}$ to associated monomials of similar degree in
$\bm{\gamma},\bm{\theta}$ as we had before. In particular, our argument for
Lemma 41 breaks down. Instead, we show a more general result over non-linear
manifolds in this section via the means of a different form of regularizer
than before.

Recall that we add to our objective the following variance regularization term

$V_{\text{reg}}(B\sigma(C\cdot))=\frac{n}{n-1}\hat{V}_{mn}(B\sigma(C\cdot))$

The final objective we minimize is,

$\displaystyle\mathcal{L}_{A,B}(Y,\hat{Y})+\lambda_{1}\|A\|_{F}^{2}+\lambda_{2}\left(\|B\|_{F}^{2}+V_{\text{reg}}(B\sigma(C))\right)$
(42)

We prove Theorem 4 via a series of Lemmas which follow. We begin by showing
that for this new minimization objective, the ground truth matrices
$A^{*},B^{*}$ from Lemma 31 still give good properties.

######  Lemma 46 (Good Ground Truth for Non-Linear Manifolds).

Given the ground truth weight matrices $A^{*},B^{*}$ of Lemma 31, we have that

$V_{\text{reg}}(B^{*}\sigma(C.))\leq 2\varepsilon_{2}.$

###### Proof.

This follows immediately from Lemma 31, point 4 since
$V_{\text{reg}}(B^{*}\sigma(C.))=\frac{n}{n-1}\hat{V}_{mn}(B^{*}\sigma(C.))$.
∎

Next, we show that, remarkably, even for our new objective the property that
all local minima are global still holds.

######  Lemma 47.

Consider (42). Every local minimum is a global minimum.

###### Proof.

We will map our minimization to an appropriate form whereafter we can apply
Lemma 35 to argue that it is equivalent to a weighted nuclear norm
minimization in $AB$ which is convex in $AB$. Let
$Z^{\prime\prime}=(I,Z^{\prime})$ where we stacked the identity’s columns at
the front of $Z^{\prime}$. Note that $Z^{\prime\prime}$ is full row rank.
Consider the SVD of $Z^{\prime\prime}=USV^{\top}$ and consider the truncated
form $Z^{\prime\prime}_{trunc}=US_{trunc}$. $Z^{\prime\prime}_{trunc}$ is a
square matrix which is invertible and

$\displaystyle\|B\|_{F}^{2}+\|BZ^{\prime}\|_{F}^{2}=\|BZ^{\prime\prime}\|_{F}^{2}=\|BZ^{\prime\prime}_{trunc}\|_{F}^{2}.$
(43)

By letting $B^{\prime\prime}=BZ^{\prime\prime}_{trunc}$, we can re-write (42)
in the following form now.

$\displaystyle\min_{A,B^{\prime\prime}}\sum_{l=1}^{m}\frac{1}{m}\|W_{l}\odot(Y_{l}-AB^{\prime\prime}M_{l})\|_{F}^{2}+\lambda_{1}\|A\|_{F}^{2}+\lambda_{2}\|B^{\prime\prime}\|_{F}^{2},$
(44)

where $M_{l}=S_{trunc}^{-1}U^{\top}Z_{l}$ which is a minimization of a convex
function of $AB^{\prime\prime}$ with Frobenius norm regularization which by
the application of Lemma 35 gives us the desired mapping to a convex function
minimization with nuclear norm regularization which is a convex objective and
gradient descent on this objective will achieve the global minimum which we
can argue is also what is achieved by gradient descent on our objective. ∎

######  Lemma 48.

We get that at any local minimum $\hat{A},\hat{B}$ of (42) for
$\lambda_{1}=\varepsilon_{1}/m$,
$\lambda_{2}=\varepsilon_{1}/s^{O(\log(1/\varepsilon_{1}))}$, we have

$\displaystyle\mathcal{L}_{\hat{A},\hat{B}}(Y,\hat{Y})\leq 4\varepsilon_{1},$
(45) $\displaystyle\|\hat{A}\|_{F}\leq 4m,\|\hat{B}\|_{F}\leq
4s^{O(\log(1/\varepsilon_{1}))},$ (46) $\displaystyle
V_{\text{reg}}(B^{*}\sigma(C.))\leq 8\varepsilon_{2}.$ (47)

###### Proof.

Following a line of argument similar to the proof of Lemma 34 we get that at
global minimum the bounds stated in the Lemma are satisfies (by using Lemma
33). Lemma 47 gives us that all local minima are global and hence the
statement of the current lemma follows. ∎

Next we show that that each part of GSH holds on the train data.

####  D.2.1 Property (A) of GSH

Since at any local minimum, we have that
$V_{\text{reg}}(\hat{B}\sigma(C.))=\frac{n}{n-1}\hat{V}_{mn}(\hat{B}\sigma(C.))$
and $V_{\text{reg}}(\hat{B}\sigma(C.))\leq 8\varepsilon_{2}$ from Lemma 46 we
get that $\hat{V}_{mn}(\hat{B}\sigma(C.))\leq 8\varepsilon_{2}$ as well
immediately giving property (A) of the GSH.

####  D.2.2 Property (B) of GSH

Recall the argument for showing property B for linear manifolds from Section
D.1. Lemmas 43-45 imply that the average inter-manifold representation
distance is larger than a constant as long as
$\mathcal{L}_{\hat{A},\hat{B}}(Y,\hat{Y})$ is small and $\|\hat{A}\|_{F}$ is
small. These two properties still hold in the current setting for non-linear
manifolds. Hence we immediately get that property (B) holds on the train data
for non-linear manifolds as well.

##  Appendix E Generalization Bounds: Proofs for Section 6

In this section, we present population variants for bounds on empirical
quantities that we saw in Section D. Since the architectures for linear and
non-linear manifolds are the same, the results in this section will apply to
both. We rely on the technique of uniform convergence bounds which are shown
via Rademacher complexity.

A recurring general function class whose Rademacher complexity we will
repeatedly use is the following

$\mathcal{F}=\left\\{f(\mathbf{x})=\|P\mathbf{x}+\mathbf{b}\|_{2}^{2}\middle|\|\mathbf{x}\|_{2}\leq\alpha,\|P\|_{F}\leq\beta,\|\mathbf{b}\|_{2}\leq
b\right\\}.$

We present a Rademacher complexity bound for this class.

######  Lemma 49.

Given the above function class $\mathcal{F}$, we have

$\mathcal{R}_{n}(\mathcal{F})\leq\frac{2b\beta\alpha+\beta^{2}\alpha^{2}}{\sqrt{n}}.$

###### Proof.

First,
$\|P\mathbf{x}+\mathbf{b}\|_{2}^{2}=\|P\mathbf{x}\|_{2}^{2}+\|\mathbf{b}\|_{2}^{2}+2\mathbf{b}^{\top}P\mathbf{x}$.
Since
$\sup_{\theta}(f_{\theta}(\mathbf{x})+g_{\theta}(\mathbf{x}))\leq\sup_{\theta}f_{\theta}(\mathbf{x})+\sup_{\theta}g_{\theta}(\mathbf{x})$
we have

$\displaystyle\mathcal{R}_{n}(\mathcal{F})$
$\displaystyle=\frac{1}{n}\operatorname*{\mathbb{E}}_{\bm{\xi}}\left[\sup_{f\in\mathcal{F}}\sum_{i=1}^{n}\xi_{i}f(\mathbf{x_{i}})\right]$
(48)
$\displaystyle\leq\underbrace{\frac{1}{n}\operatorname*{\mathbb{E}}_{\bm{\xi}}\left[\sup_{P:\|P\|_{F}\leq\beta}\sum_{i=1}^{n}\xi_{i}\|P\mathbf{x_{i}}\|_{2}^{2}\right]}_{(A)}+\underbrace{\frac{1}{n}\operatorname*{\mathbb{E}}_{\bm{\xi}}\left[\sup_{\mathbf{b}:\|\mathbf{b}\|_{2}\leq
b}\sum_{i=1}^{n}\xi_{i}\|\mathbf{b}\|_{2}^{2}\right]}_{(B)}+\underbrace{\frac{1}{n}\operatorname*{\mathbb{E}}_{\bm{\xi}}\left[\sup_{\begin{subarray}{c}P,\mathbf{b}:\|P\|_{F}\leq\beta,\\\
\|\mathbf{b}\|_{2}\leq
b\end{subarray}}\sum_{i=1}^{n}\xi_{i}2\mathbf{b}^{\top}P\mathbf{x_{i}}\right]}_{(C)}.$
(49)

We bound each term separately. $(B)$ is clearly $0$. $(C)$ is the Rademacher
complexity of a class of linear functions of $\mathbf{x}$ which is known to be
bounded by $\|\mathbf{b}^{\top}P\|_{2}\alpha/\sqrt{n}$ (Lemma 26.10 of
[SSBD14]) which can be bounded by $2b\beta\alpha/\sqrt{n}$. It remains to
bound $(A)$. Here we use that,

$\displaystyle\|P\mathbf{x}\|_{2}^{2}=P^{\top}P\odot\mathbf{x}\mathbf{x}^{\top}.$
(50)

Moreover, we have $\|P^{\top}P\|_{*}=\|P\|_{F}^{2}$. Now,

$\displaystyle(A)$
$\displaystyle=\frac{1}{n}\operatorname*{\mathbb{E}}_{\bm{\xi}}\left[\sup_{\|P\|_{F}\leq\beta}\sum_{i=1}^{n}\xi_{i}\|P\mathbf{x_{i}}\|_{2}^{2}\right]$
$\displaystyle=\frac{1}{n}\operatorname*{\mathbb{E}}_{\bm{\xi}}\left[\sup_{\|P\|_{F}\leq\beta}\sum_{i=1}^{n}\xi_{i}\left(P^{\top}P\odot\mathbf{x_{i}}\mathbf{x_{i}}^{\top}\right)\right]$
(51)
$\displaystyle\leq\frac{1}{n}\operatorname*{\mathbb{E}}_{\bm{\xi}}\left[\sup_{\|W\|_{*}\leq\beta^{2}}\sum_{i=1}^{n}\xi_{i}\left(W\odot\mathbf{x_{i}}\mathbf{x_{i}}^{\top}\right)\right]$
(52)
$\displaystyle=\frac{1}{n}\operatorname*{\mathbb{E}}_{\bm{\xi}}\left[\sup_{\|W\|_{*}\leq\beta^{2}}\left(W\odot\sum_{i=1}^{n}\xi_{i}\mathbf{x_{i}}\mathbf{x_{i}}^{\top}\right)\right]$
$\displaystyle=\frac{\beta^{2}}{n}\operatorname*{\mathbb{E}}_{\bm{\xi}}\left[\left\|\sum_{i=1}^{n}\xi_{i}\mathbf{x_{i}}\mathbf{x_{i}}^{\top}\right\|_{2}\right]$
(53)
$\displaystyle\leq\frac{\beta^{2}}{n}\operatorname*{\mathbb{E}}_{\bm{\xi}}\left[\left\|\sum_{i=1}^{n}\xi_{i}\mathbf{x_{i}}\mathbf{x_{i}}^{\top}\right\|_{F}\right]$
(54)
$\displaystyle\leq\frac{\beta^{2}}{n}\sqrt{\operatorname*{\mathbb{E}}_{\bm{\xi}}\left[\left\|\sum_{i=1}^{n}\xi_{i}\mathbf{x_{i}}\mathbf{x_{i}}^{\top}\right\|_{F}^{2}\right]}$
(55)
$\displaystyle=\frac{\beta^{2}}{n}\sqrt{\sum_{i=1}^{n}\|\mathbf{x_{i}}\mathbf{x_{i}}^{\top}\|_{F}^{2}}$
(56)
$\displaystyle=\frac{\beta^{2}}{n}\sqrt{\sum_{i=1}^{n}\|\mathbf{x_{i}}\|_{2}^{4}}\leq\frac{\beta^{2}\alpha^{2}}{\sqrt{n}},$

where (51) uses (50) and (52) is obtained by replacing $P^{\top}P$ with a
matrix $W$ and using that
$\|P\|_{F}\leq\beta\implies\|P^{\top}P\|_{*}=\|P\|_{F}^{2}\leq\beta^{2}$. (53)
uses Claim 20, (54) follows because for any matrix $A,\|A\|_{2}\leq\|A\|_{F}$,
and (55) follows from Jensen’s inequality. Finally (56) follows by expanding
the Frobenius norm and noting that the $\xi_{i}$ are independent and
$\operatorname*{\mathbb{E}}[\xi_{i}\xi_{j}]=0$ for $i\neq j$. Combining the
bounds for $(A),(B)$ and $(C)$ we get the statement of the lemma. ∎

###  E.1 Small Weighted Square Loss on Test Samples from Train Manifolds

The first generalization bound is to show that on the $m$ train manifolds, our
learnt network achieves a small test error as measured by the weighted square
loss. That is, the network has actually learnt to classify inputs from the $m$
train manifolds. A simple uniform convergence argument coupled with Lemma 5
gives us that the expected weighted square loss over unseen samples from our
train manifolds is small as well for large enough $n$.

######  Lemma 50.

At a local minimum $\hat{A},\hat{B}$ we have, with probability $\geq
1-\delta$,

$\frac{1}{m}\sum_{l=1}^{m}\operatorname*{\mathbb{E}}_{\mathbf{x}_{l}\sim\mathcal{D}(M_{l})}\left[\|\mathbf{w_{l}}\odot(\mathbf{y_{l}}-\mathbf{\hat{y}_{l}})\|_{2}^{2}\right]\leq
2\varepsilon,$

for
$n\geq\Theta\left(\frac{s^{O(\log(1/\varepsilon))}\log(m/\delta)}{\varepsilon^{2}}\right)$.

###### Proof.

Let $\beta=s^{O(\log(1/\varepsilon)}$ be the bound we have on
$\|\hat{B}\|_{F}$. Fix a train manifold with index $l$. Let $\hat{A}_{l}$
denote the $l^{th}$ row of $\hat{A}$ and let $\|\hat{A}_{l}\|_{2}\leq a_{l}$.
We know that $\sum_{l}a_{l}^{2}\leq O(m)$. Let
$\operatorname*{\mathbb{E}}_{n}[\|\mathbf{w_{l}}\odot(\mathbf{y_{l}}-\mathbf{\hat{y}_{l}})\|_{2}^{2}\leq\varepsilon_{l}$.
From Lemma 26.5 of [SSBD14] we have that with probability $\geq 1-\delta/m$,

$\displaystyle\operatorname*{\mathbb{E}}_{\mathbf{x}_{l}\sim\mathcal{D}(M_{l})}\left[\|\mathbf{w_{l}}\odot(\mathbf{y_{l}}-\mathbf{\hat{y}_{l}})\|_{2}^{2}\right]\leq\operatorname*{\mathbb{E}}_{n}\left[\|\mathbf{w_{l}}\odot(\mathbf{y_{l}}-\mathbf{\hat{y}_{l}})\|_{2}^{2}\right]+2\operatorname*{\mathbb{E}}[\mathcal{R}_{n}(\mathcal{F})]+c\sqrt{\frac{2\log(m/\delta)}{n}},$
(57)

In our case, $c=O(a_{l}^{2}\beta^{2}\|C\|_{2}^{2})$ as
$\|\mathbf{w_{l}}\odot(\mathbf{y_{l}}-\mathbf{\hat{y}_{l}})\|_{2}^{2}\leq
O(a_{l}^{2}\beta^{2}\|C\|_{2}^{2})$ and $\mathcal{R}_{n}(\mathcal{F}_{l})$ is
the Rademacher complexity of the function class

$\mathcal{F}_{l}=\left\\{f(\mathbf{x_{l}})=\left\|\mathbf{w_{l}}\odot(\mathbf{y_{l}}-AB\sigma(C\mathbf{x_{l}}))\right\|_{2}^{2}\;\;\middle|\;\;\|A\|_{F}^{2}\leq
O(m),\|B\|_{F}\leq\beta\right\\}$

Now
$\|\mathbf{w_{l}}\odot(\mathbf{y_{l}}-AB\sigma(C\mathbf{x_{l}}))\|_{2}^{2}$ is
of the form $\|P\mathbf{z}+\mathbf{b}\|_{2}^{2}$ for $P=\mathbf{w_{l}}\odot
AB$, $\mathbf{b}=-\mathbf{w_{l}}\odot\mathbf{y_{l}}$ and
$\mathbf{z}=\sigma(C\mathbf{x_{l}})$. Since, $\|P\|_{F}^{2}\leq
O(a_{l}^{2}\beta^{2}),\|\mathbf{b}\|_{2}=1/2$ and
$\|\sigma(C\mathbf{x_{l}})\|_{2}\leq\|C\|_{2}$, from Lemma 49 we have that

$\displaystyle\mathcal{R}_{n}(\mathcal{F}_{l})$ $\displaystyle\leq
O\left(\frac{a_{l}^{2}\beta^{2}\|C\|_{2}^{2}}{\sqrt{n}}\right).$

Therefore, we have that, with probability $\geq 1-\delta/m$,

$\displaystyle\operatorname*{\mathbb{E}}_{\mathbf{x}_{l}\sim\mathcal{D}(M_{l})}\left[\|\mathbf{w_{l}}\odot(\mathbf{y_{l}}-\mathbf{\hat{y}_{l}})\|_{2}^{2}\right]$
$\displaystyle\leq\operatorname*{\mathbb{E}}_{n}\left[\|\mathbf{w_{l}}\odot(\mathbf{y_{l}}-\mathbf{\hat{y}_{l}})\|_{2}^{2}\right]+O\left(\frac{a_{l}^{2}\beta^{2}\|C\|_{2}^{2}}{\sqrt{n}}\right)+O(a_{l}^{2}\beta^{2}\|C\|_{2}^{2})\sqrt{\frac{2\log(m/\delta)}{n}}.$
(58)

Averaging over all $m$ train manifolds and taking a union bound, we have with
probability $\geq 1-\delta$,

$\displaystyle\frac{1}{m}\sum_{l=1}^{m}\operatorname*{\mathbb{E}}_{\mathbf{x}_{l}\sim\mathcal{D}(M_{l})}\left[\|\mathbf{w_{l}}\odot(\mathbf{y_{l}}-\mathbf{\hat{y}_{l}})\|_{2}^{2}\right]\leq\varepsilon+O\left(\frac{\beta^{2}\|C\|_{2}^{2}}{\sqrt{n}}\right)+O(\beta^{2}\|C\|_{2}^{2})\sqrt{\frac{2\log(m/\delta)}{n}}.$
(59)

Note that we have used that $\sum_{l=1}^{m}a_{l}^{2}=O(m)$ here. (59) will
imply the statement of the lemma for

$n=\Theta\left(\frac{\beta^{4}\|C\|_{2}^{4}\log(m/\delta)}{\varepsilon^{2}}\right)=\Theta\left(\frac{s^{O(\log(1/\varepsilon))}\log(m/\delta)}{\varepsilon^{2}}\right),$

with probability $\geq 1-\delta/2$. Here we used that for the $D$ we have
chosen $\|C\|_{2}$ is bounded by a constant with very high probability (Lemma
14). ∎

###  E.2 Generalization for Property (A)

We first show that the variance regularization term $V_{\text{reg}}$ is an
unbiased estimator for the intra-manifold variance of our representation.

######  Lemma 51 (Unbiased Variance Estimation).

Consider the variance regularization term (5). For the set of train manifolds
$M_{1},\ldots,M_{m}$, we have,

$\operatorname*{\mathbb{E}}[{({\ref{eq:var-reg-
term}})}]=\frac{1}{m}\sum_{l=1}^{m}V_{M_{l}}(B\sigma(C.)).$

###### Proof.

Let us focus on a single manifold $l$. Let
$\operatorname*{\mathbb{E}}[\|B\mathbf{z}_{l}\|_{2}^{2}]=\mu_{l}$ and let
$\|B\operatorname*{\mathbb{E}}[\mathbf{z}_{l}]\|_{2}^{2}=\kappa_{l}$.

$\displaystyle\frac{1}{(n-1)}\operatorname*{\mathbb{E}}\left[\sum_{i=1}^{n}\|B\hat{\mathbf{z}}_{il}\|_{2}^{2}\right]$
$\displaystyle=\frac{1}{n-1}\sum_{i=1}^{n}\left(\overbrace{\operatorname*{\mathbb{E}}\left[\|B\mathbf{z}_{il}\|_{2}^{2}\right]}^{(A)}+\overbrace{\operatorname*{\mathbb{E}}\left[\|B\operatorname*{\mathbb{E}}_{n}[\mathbf{z}_{l}]\|_{2}^{2}\right]}^{(B)}-\overbrace{2\operatorname*{\mathbb{E}}\left[\mathbf{z}_{il}^{\top}B^{\top}B\operatorname*{\mathbb{E}}_{n}[\mathbf{z}_{l}]\right]}^{(C)}\right).$
(60)

Now $(A)=\mu_{l}$. We obtain the expressions for $(B)$ and $(C)$.

$\displaystyle(B)$
$\displaystyle=\frac{1}{n^{2}}\operatorname*{\mathbb{E}}\left[\left\|\sum_{j=1}^{n}B\mathbf{z}_{jl}\right\|_{2}^{2}\right]$
(61)
$\displaystyle=\frac{1}{n^{2}}\sum_{j=1}^{n}\operatorname*{\mathbb{E}}[\|B\mathbf{z}_{jl}\|_{2}^{2}]+\frac{1}{n^{2}}\sum_{j_{1}\neq
j_{2}}\operatorname*{\mathbb{E}}\left[\mathbf{z}_{j_{1}l}^{\top}B^{\top}B\mathbf{z}_{j_{2}l}\right]$
(62)
$\displaystyle=\frac{\mu_{l}}{n}+\frac{n-1}{n}\operatorname*{\mathbb{E}}[\mathbf{z}_{l}]^{\top}B^{\top}B\operatorname*{\mathbb{E}}[\mathbf{z}_{l}]$
(63)
$\displaystyle=\frac{\mu_{l}}{n}+\frac{n-1}{n}\|B\operatorname*{\mathbb{E}}[\mathbf{z}_{l}]\|_{2}^{2}=\frac{\mu_{l}}{n}+\frac{\kappa_{l}(n-1)}{n}.$
(64)

Finally,

$\displaystyle(C)$
$\displaystyle=\frac{2}{n}\operatorname*{\mathbb{E}}\left[\sum_{j=1}^{n}\mathbf{z}_{il}^{\top}B^{\top}B\mathbf{z}_{jl}\right]$
(65)
$\displaystyle=\frac{2}{n}\operatorname*{\mathbb{E}}[\mathbf{z}_{il}^{\top}B^{\top}B\mathbf{z}_{il}]+\frac{2}{n}\sum_{j,j\neq
i}\operatorname*{\mathbb{E}}[\mathbf{z}_{il}^{\top}B^{\top}B\mathbf{z}_{jl}]$
(66) $\displaystyle=\frac{2\mu_{l}}{n}+\frac{2(n-1)\kappa_{l}}{n}.$ (67)

Adding all together we get,

$\displaystyle\frac{1}{(n-1)}\operatorname*{\mathbb{E}}\left[\sum_{i=1}^{n}\|B\hat{\mathbf{z}}_{il}\|_{2}^{2}\right]=\mu_{l}-\kappa_{l}.$
(68)

It is easy to see via a similar calculation that,

$\displaystyle V_{M_{l}}(B\sigma(C.))=\mu_{l}-\kappa_{l}$ (69)
$\displaystyle\implies$
$\displaystyle\frac{1}{(n-1)m}\operatorname*{\mathbb{E}}\left[\sum_{l=1}^{m}\sum_{i=1}^{n}\|B\hat{\mathbf{z}}_{il}\|_{2}^{2}\right]=\frac{1}{m}\sum_{l=1}^{m}V_{M_{l}}(B\sigma(C.)).$
(70)

∎

We next show that having a small variance regularization term over the train
data implies that Property (A) of GSH holds with high probability.

######  Lemma 52 (Generalization of Property (A) to Unseen Points from Train
Manifolds).

Recall that at local minimum, we have found a $\hat{B}$ so that for
$r(\mathbf{x})=\hat{B}\sigma(C\mathbf{x})$,

$\frac{1}{m}\sum_{l=1}^{m}\frac{1}{n-1}\sum_{i=1}^{n}\|r(\mathbf{x_{il}})-\operatorname*{\mathbb{E}}_{n}[r(\mathbf{x_{l}})]\|_{2}^{2}=0.$

Then we have,

$\displaystyle\operatorname*{\mathbb{P}}\left[\sum_{l=1}^{m}\frac{1}{m}V_{M_{l}}(r(.))\leq
2\varepsilon\right]\geq 1-\delta,$ (71)

where the probability is taken over the sampling of the $n$ input examples
from each of the $m$ train manifolds.

###### Proof.

From Lemma 51 we have that

$\operatorname*{\mathbb{E}}\left[\frac{1}{n-1}\sum_{i=1}^{n}\|r(\mathbf{x_{il}})-\operatorname*{\mathbb{E}}_{n}[r(\mathbf{x_{l}})]\|_{2}^{2}\right]=V_{M_{l}}(r(.)).$

Given a vector $\mathbf{h}\in\mathbb{R}^{D}$, consider the family of functions
defined as follows.

$\displaystyle\mathcal{F}_{\mathbf{h}}=\left\\{f_{B,\mathbf{h}}:\mathbb{R}^{d}\to\mathbb{R}\;\big{|}\
f_{B,\mathbf{h}}(x)=\|B\left(\sigma(C\mathbf{x})-\mathbf{h}\right)\|_{2}^{2},\|\mathbf{x}\|_{2}\leq\alpha,\|B\|_{F}\leq\beta,\|\mathbf{h}\|_{2}\leq\|C\|_{2}\alpha\right\\}.$
(72)

By Theorem 26.5 from [SSBD14], we have that for each manifold $M_{l}$, for
every $f_{B,\mathbf{h}}\in\mathcal{F}_{\mathbf{h}}$,

$\displaystyle\operatorname*{\mathbb{E}}_{M_{l}}\left[f_{B,\mathbf{h}}(\mathbf{x})\right]\leq\tilde{\operatorname*{\mathbb{E}}_{M_{l}}}\left[f_{B,\mathbf{h}}(\mathbf{x})\right]+2\mathcal{R}_{n}(\mathcal{F}_{\mathbf{h}})+c\sqrt{\frac{2\log\left(m/\delta\right)}{n}},$
(73)

with probability $1-\delta/m$. Here $|f_{B,\mathbf{h}}|\leq c$. For the
function family we have considered taking
$c=4\beta^{2}\|C\|_{2}^{2}\alpha^{2}$ suffices. Note that for
$\mathbf{h}(l)=\tilde{\operatorname*{\mathbb{E}}}_{M_{l}}[\sigma(C\mathbf{x})]$,
$\operatorname*{\mathbb{E}}_{M_{l}}\left[f_{\tilde{B},\mathbf{h}(l)}(x)\right]=V_{M_{l}}(\tilde{B}\sigma(C.))]$
and
$\sum_{l=1}^{m}\tilde{\operatorname*{\mathbb{E}}}_{M_{l}}\left[f_{B,\mathbf{h}(l)}(\mathbf{x})\right]=m{({\ref{eq:var-
reg-term}})}\leq m\varepsilon$. An upper bound on
$\mathcal{R}_{n}(\mathcal{F}_{\mathbf{h}(l)})$ will lead us to an upper bound
on $\sum_{l=1}^{m}V_{M_{l}}(\tilde{B}\sigma(C.))]$ as we shall see later. We
proceed to bound $\mathcal{R}_{n}(\mathcal{F}_{\mathbf{h}(l)})$. For
$\mathbf{x}\sim\mathcal{D}(M_{l})$, let
$\sigma(C\mathbf{x})-\mathbf{h}(l)=\mathbf{z}$. From Lemma 49, we have

$\displaystyle\mathcal{R}_{n}(\mathcal{F}_{\mathbf{h}(l)})\leq\frac{3\beta^{2}\|C\|_{2}^{2}\alpha^{2}}{\sqrt{n}}.$

Therefore, we get that

$\displaystyle\sum_{l=1}^{m}V_{M_{l}}(\hat{B}\sigma(C.))$
$\displaystyle\leq\sum_{l=1}^{m}\hat{\operatorname*{\mathbb{E}}_{M_{l}}}\left[f_{B,h(l)}(x)\right]+6m\beta^{2}\|C\|_{2}^{2}\alpha^{2}\sqrt{\frac{1}{n}}+4m\beta^{2}\|C\|_{2}^{2}\alpha^{2}\sqrt{\frac{\log\left(m/\delta\right)}{n}}$
$\displaystyle\leq
m\varepsilon+6m\beta^{2}\|C\|_{2}^{2}\alpha^{2}\sqrt{\frac{1}{n}}+4m\beta^{2}\|C\|_{2}^{2}\alpha^{2}\sqrt{\frac{\log\left(m/\delta\right)}{n}}$
$\displaystyle\leq
m\varepsilon+10m\beta^{2}\|C\|_{2}^{2}\alpha^{2}\sqrt{\frac{\log\left(m/\delta\right)}{n}}.$
(74)

with probability $1-\delta$. Note that we applied a union bound over the
statement for each manifold bounding the probability of large deviation in any
one of the manifolds by $m\cdot\delta/m=\delta$. By choosing
$n\geq\Theta\left(\frac{\beta^{4}\alpha^{4}\|C\|_{2}^{4}\log(m/\delta)}{\varepsilon^{2}}\right)$
in (74), we get that with probability $1-\delta$,

$\displaystyle\frac{1}{m}\sum_{l=1}^{m}V_{M_{l}}(\hat{B}\sigma(C.))\leq
2\varepsilon.$

Since $\|\mathbf{x_{l}}\|_{2}\leq 1$, we can choose $\alpha=1$. Moreover from
Lemma 14 we can assume $\|C\|_{2}$ is bounded by a constant with very high
probability. In addition we have that at local minima $\|\hat{B}\|_{F}\leq
s^{O(\log(1/\varepsilon))}$. Hence, we get the statement of the lemma for

$n\geq\Theta\left(\frac{s^{O(\log(1/\varepsilon))}\log(m/\delta)}{\varepsilon^{2}}\right).$

∎

######  Lemma 53 (Generalization of the Property (A) to new Manifolds).

Given $\hat{A},\hat{B}$ which are at a local minima of either objective (23)
or (42), for a fresh sample $M_{m+1}\sim\mathcal{M}$, we have

$\displaystyle\operatorname*{\mathbb{E}}_{\mathbf{x}\sim\mathcal{D}(M_{m+1})}\left[\left\|\hat{B}\mathbf{z^{\prime}}\right\|_{2}^{2}\right]\leq
O(\varepsilon),$ (75)

with probability $\geq 9/10$ over the draw of $M_{m+1}$ from $\mathcal{M}$
when

$m\geq\Theta\left(\frac{s^{O(\log(1/\varepsilon))}\log(2/\delta)}{\varepsilon^{2}}\right).$

Here
$\mathbf{z^{\prime}}=\sigma(C\mathbf{x})-\operatorname*{\mathbb{E}}_{\mathbf{x}\sim\mathcal{D}(M_{m+1})}[\sigma(C\mathbf{x})]$.

###### Proof.

Consider the following function class which maps a manifold to a non-negative
real value:

$\mathcal{F}=\left\\{f_{B}:M\to\mathbb{R},f_{B}(M)=\operatorname*{\mathbb{E}}_{\mathbf{x}\sim\mathcal{D}(M)}\left[\|B\mathbf{z^{\prime}}\|_{2}^{2}\right]\;\;|\;\;\|B\|_{F}\leq\beta,\|\mathbf{x}\|_{2}\leq\alpha\right\\}.$

By the property of Rademacher complexity (Theorem 26.2 from [SSBD14]), we have
with probability $\geq 1-\delta$, for any $f\in\mathcal{F}$,

$\displaystyle\operatorname*{\mathbb{E}}_{M_{m+1}\sim\mathcal{M}}\left[f(M_{m+1})\right]\leq\operatorname*{\mathbb{E}}_{m}[f(M_{l})]+2\operatorname*{\mathbb{E}}[\mathcal{R}_{m}(\mathcal{F})]+c\sqrt{\frac{\log(2/\delta)}{m}},$
(76)

with probability $1-\delta$. Here $c$ is such that $|f(M)|\leq c$ for all $M$.
Choosing $c=4\beta^{2}\|C\|_{2}^{2}\alpha^{2}$ suffices. We need to bound
$\mathcal{R}_{m}(\mathcal{F})$. We could appeal to Lemma 49 again but since
now the function class $\mathcal{F}$ has functions of manifolds instead of
vectors $\mathbf{x}$ we present the full argument here for clarity. The
argument follows in a very similar vein to that of Lemma 49. Now we let
$\bm{\xi}=(\xi_{1},\ldots,\xi_{m})$ denote a vector of $m$ i.i.d. Rademacher
random variables.

$\displaystyle\mathcal{R}_{m}(\mathcal{F})$
$\displaystyle=\frac{1}{m}\operatorname*{\mathbb{E}}_{\bm{\xi}}\left[\sup_{f_{B}\in\mathcal{F}}\sum_{l=1}^{m}\xi_{l}f_{B}(M_{l})\right]$
$\displaystyle=\frac{1}{m}\operatorname*{\mathbb{E}}_{\bm{\xi}}\left[\sup_{f_{B}\in\mathcal{F}}\sum_{l=1}^{m}\xi_{l}\operatorname*{\mathbb{E}}_{\mathbf{x}\sim\mathcal{D}(M_{l})}\left[\|B\mathbf{z^{\prime}}\|_{2}^{2}\right]\right]$
$\displaystyle=\frac{1}{m}\operatorname*{\mathbb{E}}_{\bm{\xi}}\left[\sup_{\|B\|_{F}\leq\beta}\sum_{l=1}^{m}\xi_{l}\operatorname*{\mathbb{E}}_{\mathbf{x}\sim\mathcal{D}(M_{l})}\left[\left\langle
B^{\top}B,\mathbf{z^{\prime}}\mathbf{z^{\prime}}^{\top}\right\rangle\right]\right]$
$\displaystyle=\frac{1}{m}\operatorname*{\mathbb{E}}_{\bm{\xi}}\left[\sup_{\|B\|_{F}\leq\beta}\left\langle
B^{\top}B,\sum_{l=1}^{m}\xi_{l}\operatorname*{\mathbb{E}}_{\mathbf{x}\sim\mathcal{D}(M_{l})}\left[\mathbf{z^{\prime}}\mathbf{z^{\prime}}^{\top}\right]\right\rangle\right]$
$\displaystyle\leq\frac{1}{m}\operatorname*{\mathbb{E}}_{\bm{\xi}}\left[\sup_{\|W\|_{*}\leq\beta^{2}}\left\langle
W,\sum_{l=1}^{m}\xi_{l}\operatorname*{\mathbb{E}}_{\mathbf{x}\sim\mathcal{D}(M_{l})}\left[\mathbf{z^{\prime}}\mathbf{z^{\prime}}^{\top}\right]\right\rangle\right]$
$\displaystyle=\frac{\beta^{2}}{m}\operatorname*{\mathbb{E}}_{\bm{\xi}}\left[\left\|\sum_{l=1}^{m}\xi_{l}\operatorname*{\mathbb{E}}_{\mathbf{x}\sim\mathcal{D}(M_{l})}\left[\mathbf{z^{\prime}}\mathbf{z^{\prime}}^{\top}\right]\right\|_{2}\right]$
$\displaystyle\leq\frac{\beta^{2}}{m}\sqrt{\operatorname*{\mathbb{E}}_{\bm{\xi}}\left[\left\|\sum_{l=1}^{m}\xi_{l}\operatorname*{\mathbb{E}}_{\mathbf{x}\sim\mathcal{D}(M_{l})}\left[\mathbf{z^{\prime}}\mathbf{z^{\prime}}^{\top}\right]\right\|_{F}^{2}\right]}$
$\displaystyle=\frac{\beta^{2}}{m}\sqrt{\sum_{l=1}^{m}\left\|\operatorname*{\mathbb{E}}_{\mathbf{x}\sim\mathcal{D}(M_{l})}\left[\mathbf{z^{\prime}}\mathbf{z^{\prime}}^{\top}\right]\right\|_{F}^{2}}$
$\displaystyle\leq\frac{\beta^{2}}{m}\sqrt{m\cdot\max\left\|\mathbf{z^{\prime}}\right\|_{2}^{4}}$
$\displaystyle\leq\frac{4\beta^{2}\alpha^{2}\|C\|_{2}^{2}}{\sqrt{m}}.$

Therefore,

$\displaystyle\operatorname*{\mathbb{E}}_{M_{m+1}\sim\mathcal{M}}\left[\operatorname*{\mathbb{E}}_{x\sim\mathcal{D}(M_{m+1})}\left[\|\hat{B}z^{\prime}\|_{2}^{2}\right]\right]$
$\displaystyle\leq\varepsilon+\frac{8\beta^{2}\alpha^{2}\|C\|_{2}^{2}}{\sqrt{m}}+\frac{4\beta^{2}\alpha^{2}\|C\|_{2}^{2}\sqrt{\log(2/\delta)}}{\sqrt{m}}$
$\displaystyle\leq\varepsilon+\frac{12\beta^{2}\alpha^{2}\|C\|_{2}^{2}\sqrt{\log(2/\delta)}}{\sqrt{m}}$
$\displaystyle\leq 2\varepsilon,$

for

$m\geq\frac{144\beta^{4}\alpha^{4}\|C\|_{2}^{4}\log(2/\delta)}{\varepsilon^{2}}=\Theta\left(\frac{s^{O(\log(1/\varepsilon))}\log(2/\delta)}{\varepsilon^{2}}\right)$

Finally, by Markov’s inequality, we have that with probability $\geq 9/10$,

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim\mathcal{D}(M_{m+1})}\left[\|\hat{B}\mathbf{z^{\prime}}\|_{2}^{2}\right]\leq
20\varepsilon.$

∎

###  E.3 Generalization for Property (B)

We first show that a population variant of Lemma 45 over $n$ holds with high
probability.

######  Lemma 54.

With probability $\geq 1-\delta$,

$\frac{1}{m(m-1)}\sum_{l=1}^{m}\sum_{j\neq
l}\operatorname*{\mathbb{E}}_{\begin{subarray}{c}\mathbf{x_{l}}\sim\mathcal{D}(M_{l}),\\\
\mathbf{x_{j}}\sim\mathcal{D}(M_{j})\end{subarray}}\|\hat{B}\sigma(C\mathbf{x_{l}})-\hat{B}\sigma(C\mathbf{x_{j}})\|_{2}^{2}\geq\frac{m(1-O(\sqrt{\varepsilon}))}{O(\|A\|_{F}^{2})}-f(\log(m)/\delta)/\sqrt{n}.$

###### Proof.

Recall the definition of $H(l)$ from Lemma 45. Consider the sum
$S=\frac{1}{m}\sum_{l=1}^{m}H(l)$. From this summation, consider the $n$ terms
corresponding to a pair of manifolds $l\neq j$. Denote the sum over these $n$
terms by $S_{l,j}$. We can argue generalization for $S_{l,j}$ using uniform
convergence theory. In particular, we have that with probability
$1-\delta/(m(m-1))$,

$\displaystyle
S_{l,j}-\frac{1}{m(m-1)}\operatorname*{\mathbb{E}}_{\begin{subarray}{c}\mathbf{x_{l}}\sim\mathcal{D}(M_{l}),\\\
\mathbf{x_{j}}\sim\mathcal{D}(M_{j})\end{subarray}}\|\hat{B}\sigma(C\mathbf{x_{l}})-\hat{B}\sigma(C\mathbf{x_{j}})\|_{2}^{2}\leq
2\frac{\operatorname*{\mathbb{E}}[\mathcal{R}_{n}(\mathcal{F})]}{m(m-1)}+4\beta^{2}\alpha^{2}\|C\|_{2}^{2}\frac{\sqrt{\log(2m(m-1)/\delta)}}{\sqrt{n}m(m-1)},$
(77)

where

$\mathcal{F}=\\{f_{B}:f_{B}(\mathbf{x_{l}},\mathbf{x_{j}})=\|B\sigma(C\mathbf{x_{l}})-B\sigma(C\mathbf{x_{j}})\|_{2}^{2},\|B\|_{F}\leq\beta\\}$

We repeat the above for all pairs $l\neq j$. The probability that for all
pairs the expected loss will be close to the train loss is at least $1-\delta$
by the union bound. From (77) we have that with probability $\geq 1-\delta$,

$\displaystyle S-\frac{1}{m(m-1)}\sum_{l=1}^{m}\sum_{j\neq
l}\operatorname*{\mathbb{E}}_{\begin{subarray}{c}\mathbf{x_{l}}\sim\mathcal{D}(M_{l}),\\\
\mathbf{x_{j}}\sim\mathcal{D}(M_{j})\end{subarray}}\|\hat{B}\sigma(C\mathbf{x_{l}})-\hat{B}\sigma(C\mathbf{x_{j}})\|_{2}^{2}\leq
2\operatorname*{\mathbb{E}}[\mathcal{R}_{n}(\mathcal{F})]+4\beta^{2}\alpha^{2}\|C\|_{2}^{2}\frac{\sqrt{\log(m(m-1)/\delta)}}{\sqrt{n}}$
$\displaystyle\implies$
$\displaystyle\frac{1}{m(m-1)}\sum_{l=1}^{m}\sum_{j\neq
l}\operatorname*{\mathbb{E}}_{\begin{subarray}{c}\mathbf{x_{l}}\sim\mathcal{D}(M_{l}),\\\
\mathbf{x_{j}}\sim\mathcal{D}(M_{j})\end{subarray}}\|\hat{B}\sigma(C\mathbf{x_{l}})-\hat{B}\sigma(C\mathbf{x_{j}})\|_{2}^{2}\geq\frac{m(1-O(\sqrt{\varepsilon}))}{O(\|A\|_{F}^{2})}-2\mathcal{R}_{n}(\mathcal{F})-4\beta^{2}\alpha^{2}\|C\|_{2}^{2}\frac{\sqrt{\log(m(m-1)\delta)}}{\sqrt{n}}.$

Now we bound $\mathcal{R}_{n}(\mathcal{F})$. Using Lemma 49, we get that

$\displaystyle\mathcal{R}_{n}(\mathcal{F})$
$\displaystyle\leq\frac{4\beta^{2}\alpha^{2}\|C\|_{2}^{2}}{\sqrt{n}}.$ (78)

Note that to employ Lemma 49 we think of
$\sigma(C\mathbf{x_{il}})-\sigma(C\mathbf{x_{ij}})=\mathbf{x}$ as the input to
the functions in $\mathcal{F}$. Therefore,

$\displaystyle\frac{1}{m(m-1)}\sum_{l=1}^{m}\sum_{j\neq
l}\operatorname*{\mathbb{E}}_{\begin{subarray}{c}\mathbf{x_{l}}\sim\mathcal{D}(M_{l}),\\\
\mathbf{x_{j}}\sim\mathcal{D}(M_{j})\end{subarray}}\|\hat{B}\sigma(C\mathbf{x_{l}})-\hat{B}\sigma(C\mathbf{x_{j}})\|_{2}^{2}$
$\displaystyle\geq\frac{m(1-O(\sqrt{\varepsilon}))}{O(\|A\|_{F}^{2})}-\frac{8\beta^{2}\alpha^{2}\|C\|_{2}^{2}}{\sqrt{n}}$
(79)
$\displaystyle~{}~{}~{}-4\beta^{2}\alpha^{2}\|C\|_{2}^{2}\frac{\sqrt{\log(m(m-1)\delta)}}{\sqrt{n}}$
(80) $\displaystyle\geq\frac{m(1-O(\sqrt{\varepsilon}))}{O(\|A\|_{F}^{2})},$
(81)

for

$n\geq\Theta\left(\frac{\beta^{4}\alpha^{4}\|C\|_{2}^{4}\log(m\delta)\|A\|_{F}^{4}}{m^{2}}\right)=\Theta\left(s^{O(\log(1/\varepsilon))}\log(m\delta)\right).$

∎

Next we show that for a randomly chosen permutation, with high probability, we
have that the inter-manifold representation distance averaged over consecutive
pairs according to the permutation is also large.

######  Lemma 55.

Suppose $m$ is even and
$m\geq\Theta(\log(2/\delta)s^{O(\log(1/\varepsilon))}/K^{2})$. Let
$d(l,j)=E_{\begin{subarray}{c}\mathbf{x_{l}}\sim\mathcal{D}(M_{l}),\\\
\mathbf{x_{j}}\sim\mathcal{D}(M_{j})\end{subarray}}\|\hat{B}\sigma(C\mathbf{x_{l}})-\hat{B}\sigma(C\mathbf{x_{j}})\|_{2}^{2}$.
Suppose we have that $\frac{1}{m(m-1)}\sum_{l=1}^{m}\sum_{j\neq l}d(l,j)\geq
K$. Then for a randomly chosen permutation $\rho:[m]\to[m]$, we have that with
probability $\geq 1-\delta$,

$\frac{2}{m}\sum_{l=1}^{m/2}d(\rho(2l-1),\rho(2l))\geq K/2.$

###### Proof.

First we have that

$\displaystyle\operatorname*{\mathbb{E}}_{\rho}\left[\frac{2}{m}\sum_{l=1}^{m/2}d(\rho(2l-1),\rho(2l))\right]=\frac{1}{m(m-1)}\sum_{l=1}^{m}\sum_{j\neq
l}d(l,j)\geq K.$ (82)

This is because in expectation over random permutations, we see every pair
$l,j$ the same number of times. The normalization ensures that the overall
sums match. Next, we show that concentration of the sum on the left hand side
around its expected value. Using a trick from [Tal95], we view the process of
choosing a random permutation on $[m]$ as follows. We start with the identity
permutation. Then we perform a sequence of $m-1$ transpositions as follows. We
transpose $(m,a_{m})$, then $(m-1,a_{m-1})$ and so on till $(2,a_{2})$ where
each $a_{j}$ is uniformly samples from $[j]$. This will give us a uniformly
random permutation at the end and it is defined by $\\{a_{l}\\}_{l=2}^{m}$
which are independent. From here, our strategy will be to bound the amount by
which our sum $S_{m}=\frac{2}{m}\sum_{l=1}^{m/2}d(\rho(2l-1),\rho(2l))$
changes when the value of some $a_{j}$ is changed. Changing $a_{j}$ changes at
most 3 locations in the final permutation (wherever $j$, the old $a_{j}$, the
new $a_{j}$ end up). Therefore, at most $3$ terms in $S_{m}$ change. Noting
that $\|B\sigma(C\mathbf{x_{l}})-B\sigma(C\mathbf{x_{j}})\|_{2}\leq
2\alpha\beta\|C\|_{2}$ we can deduce that by changing a single $a_{j}$,
$S_{m}$ changes by at most $\frac{6\alpha\beta\|C\|_{2}}{m}$. Now applying
McDiarmid’s inequality gives us

$\displaystyle\operatorname*{\mathbb{P}}_{\rho}\left[\left\lvert\frac{2}{m}\sum_{l=1}^{m/2}d(\rho(2l-1),\rho(2l))-\operatorname*{\mathbb{E}}_{\rho}\left[\frac{2}{m}\sum_{l=1}^{m/2}d(\rho(2l-1),\rho(2l))\right]\right\rvert\geq
t\right]\leq
2\exp\left(-\frac{t^{2}m}{36\alpha^{2}\beta^{2}\|C\|_{2}^{2}}\right).$ (83)

Taking $t=\sqrt{\frac{\log(2/\delta)}{m}}6\alpha\beta\|C\|_{2}$, we get that
with probability $1-\delta$,

$\displaystyle\frac{2}{m}\sum_{l=1}^{m/2}d(\rho(2l-1),\rho(2l))\geq K-t\geq
K/2,$ (84)

for
$m=144\log(2/\delta)\alpha^{2}\beta^{2}\|C\|_{2}^{2}/K^{2}=\Theta(\log(2/\delta)s^{O(\log(1/\varepsilon))}/K^{2})$.
∎

Finally we show property (B) of GSH for most new manifolds sampled from
$\mathcal{M}$.

######  Lemma 56.

For $M_{m+1},M_{m+2}\sim\mathcal{M}^{2}$, with probability $\geq 1-\delta$,

$E_{\begin{subarray}{c}\mathbf{x_{m+1}}\sim\mathcal{D}(M_{m+1}),\\\
\mathbf{x_{m+2}}\sim\mathcal{D}(M_{m+2})\end{subarray}}\|\hat{B}\sigma(C\mathbf{x_{m+1}})-\hat{B}\sigma(C\mathbf{x_{m+2}})\|_{2}^{2}\geq
K/4,$

for

$m\geq\Theta\left(\frac{s^{O(\log(1/\varepsilon))}\log(2/\delta)}{K^{2}}\right).$

###### Proof.

Consider the following process. We sample $m/2$ pairs from $\mathcal{M}^{2}$,
$\\{M_{l}=(M_{l1},M_{l2})\\}_{l=1}^{m/2}$. Define
$d(M_{l})=\operatorname*{\mathbb{E}}_{\begin{subarray}{c}\mathbf{x_{1}}\sim\mathcal{D}(M_{l1}),\\\
\mathbf{x_{2}}\sim\mathcal{D}(M_{l2})\end{subarray}}\|\hat{B}\sigma(C\mathbf{x_{1}})-\hat{B}\sigma(C\mathbf{x_{2}})\|_{2}^{2}$.
It is easy to see that our original sampling process of getting
$M_{1},\ldots,M_{m}$ and choosing a random permutation to order these $m$
manifolds in and pair consecutive ones is identical in distribution to the
above described process. Hence, any probability statements for the former
process hold also for the latter and vice versa. Let

$\mathcal{F}=\\{d_{B}:M\to\mathbb{R}\;|\;d_{B}(M)=\operatorname*{\mathbb{E}}_{\begin{subarray}{c}\mathbf{x_{1}}\sim\mathcal{D}(M_{1}),\\\
\mathbf{x_{2}}\sim\mathcal{D}(M_{2})\end{subarray}}\|\hat{B}\sigma(C\mathbf{x_{1}})-\hat{B}\sigma(C\mathbf{x_{2}})\|_{2}^{2},\text{
where }M\in\mathcal{M}^{2},\|B\|_{F}\leq\beta\\}$

We have that with probability $1-\delta$,

$\displaystyle\sup_{d_{B}\in\mathcal{F}}\sum_{l=1}^{m/2}d_{B}(M_{l})-\operatorname*{\mathbb{E}}_{M\sim\mathcal{M}^{2}}[d_{B}(M)]\leq
2\operatorname*{\mathbb{E}}[\mathcal{R}_{m/2}(\mathcal{F})]+4\beta^{2}\alpha^{2}\|C\|_{2}^{2}\sqrt{\frac{2\log(2/\delta)}{m}}$
$\displaystyle\implies$
$\displaystyle\operatorname*{\mathbb{E}}_{M\sim\mathcal{M}^{2}}[d_{\hat{B}}(M)]\geq
K/2-2\operatorname*{\mathbb{E}}[\mathcal{R}_{m/2}(\mathcal{F})]-4\beta^{2}\alpha^{2}\|C\|_{2}^{2}\sqrt{\frac{2\log(2/\delta)}{m}}.$

Now it remains to bound $\mathcal{R}_{m/2}(\mathcal{F})$. Given
$M\in\operatorname{supp}(\mathcal{M})$ and
$\mathbf{x_{1}},\mathbf{x_{2}}\sim\mathcal{D}(M_{1}),\mathcal{D}(M_{2})$
respectively, let
$\mathbf{z}=\sigma(C\mathbf{x_{1}})-\sigma(C\mathbf{x_{2}})$. Then we have
$\operatorname*{\mathbb{E}}_{\mathbf{x_{1}},\mathbf{x_{2}}\sim\mathcal{D}(M_{1}),\mathcal{D}(M_{2})}[\|\mathbf{z}\|_{2}^{2}]\leq
4\alpha^{2}\|C\|_{2}^{2}$.

$\displaystyle\mathcal{R}_{m/2}(\mathcal{F})$
$\displaystyle=\frac{2}{m}\operatorname*{\mathbb{E}}_{\bm{\xi},\\{M_{l}=(M_{l1},M_{l2})\\}_{l=1}^{m/2}}\left[\sup_{B,\|B\|_{F}\leq\beta}\sum_{l=1}^{n}\xi_{l}\operatorname*{\mathbb{E}}_{\begin{subarray}{c}\mathbf{x_{1}}\sim\mathcal{D}(M_{l1}),\\\
\mathbf{x_{2}}\sim\mathcal{D}(M_{l2})\end{subarray}}\|B\mathbf{z}\|_{2}^{2}\right]\leq\frac{4\sqrt{2}\beta^{2}\alpha^{2}\|C\|_{2}^{2}}{\sqrt{m}}$

using a line of calculations similar to those done in the proof of Lemma 53.
Therefore, we have

$\displaystyle\operatorname*{\mathbb{E}}_{M\sim\mathcal{M}^{2}}[d_{\hat{B}}(M)]$
$\displaystyle\geq
K/2-\frac{8\sqrt{2}\beta^{2}\alpha^{2}\|C\|_{2}^{2}}{\sqrt{m}}-4\beta^{2}\alpha^{2}\|C\|_{2}^{2}\sqrt{\frac{2\log(2/\delta)}{m}}$
$\displaystyle\geq
K/2-\frac{12\sqrt{2}\beta^{2}\alpha^{2}\|C\|_{2}^{2}\sqrt{\log(2/\delta)}}{\sqrt{m}}\geq
K/4$

for

$m\geq\frac{4608\beta^{2}\alpha^{2}\|C\|_{2}^{2}\log(2/\delta)}{K^{2}}=\Theta\left(\frac{s^{O(\log(1/\varepsilon))}\log(2/\delta)}{K^{2}}\right).$

∎

##  Appendix F Intra-Class Hashing Property Without Variance Regularization

######  Theorem 8 (Property (A) without Variance Regularization).

Given our 3-layer neural network, and given $n$ train samples each from $m$
train manifolds, training the following objective results in a network that
satisfies that $\hat{V}_{mn}(B\sigma(C\mathbf{x}))\rightarrow 0$ as
$\lambda_{1},\lambda_{2}\rightarrow 0$

$\displaystyle\min_{A,B}\mathcal{L}_{A,B}(Y,\hat{Y})+\lambda_{1}\|A\|_{F}^{2}+\lambda_{2}\|B\|_{F}^{2}.$
(85)

###### Proof.

The main point to note is if $\lambda_{1},\lambda_{2}\rightarrow 0$ (that is
very small) then the objective is dominated by $\mathcal{L}_{A,B}(Y,\hat{Y})$
which is minimized only if the prediction $\hat{Y}$ does not depend on
$\bm{\theta}$ – because if it did then by replacing $\hat{Y}$ by
$E_{n}[\hat{Y}]$ for each of the $m$ manifolds, decreases the objective as
shown in Lemma 38.

Now, we know that there is a ground truth model where
$\hat{V}_{mn}(\mathbf{\hat{y}})\leq\varepsilon$. Then it follows from Lemma 39
that $\hat{V}_{mn}(\mathbf{r})\leq 2\sqrt{\varepsilon}$. To get close to this
ground truth we select $\lambda_{1}=\varepsilon/m$ and
$\lambda_{2}=\varepsilon/s^{O(\log(1/\varepsilon))}$. Hence by letting
$\varepsilon\to 0$ we get the desired result.

∎

##  Appendix G Recovering $\bm{\gamma}$ from the Representation

We have argued in Section 1 that in many cases where $\bm{\gamma}$ represents
a set of semantic concepts such as the shape or texture of an image, it is of
interest to recover exactly the latent vector $\bm{\gamma}$ and not just an
isomorphism $f(\bm{\gamma})$. The next lemma shows that there is a linear
transform that maps our learnt representation $r(\mathbf{x})$ to approximately
$\bm{\gamma}$ associated with $\mathbf{x}$; however we can only show this with
the unweighted square loss when the regularization weights
$\lambda_{1},\lambda_{2}$ is tiny and only for the train manifolds. Our
experiments show that this reversibility holds even with our variant of the
weighted square loss $\mathcal{L}_{A,B}(Y,\hat{Y})$.

######  Lemma 57 (Reversibility of the Learnt Representation).

Consider the minimization
$\min_{A,B}\operatorname*{\mathbb{E}}\left[\|Y-AB\sigma(Cx))\|_{F}^{2}\right]+\lambda_{1}(\|A\|_{F}^{2})+\lambda_{2}(\|B\|_{F}^{2})$
subject to $v_{\theta}(r)=0$. As $\lambda_{1},\lambda_{2}\rightarrow 0$ and
for infinite width $C$ layer, there is a linear transform $R$ so that
$R\hat{B}\sigma(C\mathbf{x_{l}})=\mathbf{\bm{\gamma}_{l}}$ for any
$\mathbf{x_{l}}$ from any of the $m$ training manifolds.

###### Proof.

We will show that if $\bm{\gamma}$ is not expressible as a linear transform of
$r(\mathbf{x})$ then creating additional outputs of the $B$ layer that emit
$\bm{\gamma}$ only improves the loss objective. First note that the width of
the hidden layer never needs to be more than $m$ (as otherwise we can replace
$A,B$ by their appropriate truncated-$\mathrm{svd}$ versions that are of at
most width $m$ since the rank of $AB$ is at most $m$). So even if we add
additional co-ordinates to $r(\mathbf{x})$ the width remains bounded. We have
also assume that the variance at the representation layer is $0$ for each
manifold so the representation layer is a function only of the manifold for
the train data.

Note that we have assumed $\lambda=0$ and the width of the random ReLU layer
goes to $\infty$. In this scenario, we know by Lemma 28 that for every
manifold $M_{l}\in\mathcal{M}$, the representation computed by
$\sigma(C\mathbf{x_{l}})$ when $\mathbf{x_{l}}\sim\mathcal{D}(M_{l})$ is
powerful enough to express $\mathbf{\bm{\gamma}_{l}}$ exactly. We will show
that if $\mathbf{\bm{\gamma}_{l}}$ cannot be expressed as a linear combination
of coordinates of $\mathbf{r}=\hat{B}\sigma(C\mathbf{x_{l}})$ over the
training samples $\mathbf{x_{l}}\sim\mathcal{D}(M_{l})$ then the loss
$\operatorname*{\mathbb{E}}_{x_{l}\sim M_{l}}[\|Y-A\mathbf{r}\|_{F}^{2}]$ is
not at a minimum and can be further reduced. Let $A_{l}$ denote the $l^{th}$
row of $A$. Let $\hat{A_{l}}$ be the regression minimization for the term
$\min_{A_{l}}\|Y_{l}-A_{l}\mathbf{r}\|_{2}$ which will be the optimal trained
value of $A_{l}$. Let us find the improvement to this term by appending
$\mathbf{\bm{\gamma}}^{j}$ the the $j^{th}$ coordinate of
$\mathbf{\bm{\gamma}}$ which is the vector of $\gamma_{lj}$ over the different
manifolds $l$ Let $\mathbf{\bm{\gamma}}^{j}$ denote the vector of
$\gamma_{lj}$ over the different manifolds $l$. Note that in any linear
regression problem the improvement obtained from a new coordinate of the input
features can be quantified as follows: orthonormalize it with respect to the
other coordinates and measure the square of the projection of the output
vector along this new orthonormalized input coordinate. So when a new
coordinate $\bm{\gamma}^{j}$ has been added to the input, the decrease in the
square loss is $(\left\langle
Y_{l},\bm{\gamma}^{j^{\prime}}/|\bm{\gamma}^{j^{\prime}}|_{2}\right\rangle)^{2}=(Y_{l}^{\top}\bm{\gamma}^{j^{\prime}})^{2}/|\bm{\gamma}^{j^{\prime}}|_{2}^{2}$
where $\bm{\gamma}^{j^{\prime}}$ is the component of $\bm{\gamma}^{j}$ that is
orthogonal to $\mathbf{r}$; that is,
$\bm{\gamma}^{j^{\prime}}=\bm{\gamma}^{j}-d^{\top}\mathbf{r}$ so that
$\langle\bm{\gamma}^{j^{\prime}},\mathbf{r}\rangle=0$. Note that since
$\bm{\gamma}^{j}$ have been normalized, the improvement is at least
$(Y_{l}^{\top}\bm{\gamma}^{j^{\prime}})^{2}=\sum_{l=1}^{m}(\bm{\gamma}^{j^{\prime}}_{l})^{2}$
(as $Y_{l}$ is the indicator of the $l^{th}$ coordinate). So the total
improvement over all the manifolds from $\bm{\gamma}^{j}$ is at least
$\sum_{l}(\bm{\gamma}^{j^{\prime}}_{l})^{2}=\|\bm{\gamma}^{j^{\prime}}\|_{2}^{2}$.
Now since the loss is at a local minimum it must be that there is no
improvement possible which means $\|\bm{\gamma}^{j^{\prime}}\|_{2}=0$ which
means $\bm{\gamma}^{j}=\mathbf{a}^{\top}\mathbf{h}$ for some $\mathbf{a}$ and
the same argument must be true for each coordinate of $\bm{\gamma}$ and so
$\bm{\gamma}=R\mathbf{h}$ for some $R$.
∎

######  Remark 3.

Although we assumed $\lambda\rightarrow 0$ and width of ReLU layer tends to
$\infty$, note that if the width of $C$ is bounded and large, then
$\bm{\gamma}$ can only be approximately expressed in terms of
$\sigma(C\mathbf{x})$. In that case that approximate version of $\bm{\gamma}$
must be linearly expressible in terms of $\mathbf{h}$.
Also even if $\lambda$ is not $0$, note that as long as
$\sum_{j}\|\bm{\gamma}^{j^{\prime}}\|_{2}^{2}>\lambda$ the increase in
regularization loss is more than offset by the decrease in square loss – to
realize the improvement by $\sum_{j}\|\bm{\gamma}^{j^{\prime}}\|_{2}^{2}$ the
$A$ matrix will add an edge of weight $\langle
Y_{i},\bm{\gamma}^{j^{\prime}}\rangle$ between each $\bm{\gamma}^{j}$ and
$Y_{i}$ and the $B$ matrix needs to add new nodes corresponding to $b$ which
has a bounded norm in terms of $\sigma(C\mathbf{x})$ which bounds the increase
in Frobenius norm of $B$.

##  Appendix H First or Second Order Methods Converge Provably to a Local
Optimum

Here we point the reader to two results about some popular first-order
optimization methods which have the property that they converge quickly to a
local optimum for smooth optimization objectives. The first is the work of
[GHJY15] which shows that for strictly-saddle objectives, a form of stochastic
gradient descent provably converges to a local optimum. The second is the work
of [AAZB+17] who show that a second-order algorithm FastCubic converges to
local optimum faster than gradient descent converges to any critical point for
a set of smooth objectives which includes neural net training. There are more
references within the above works studying similar properties of other
variants as well.

##  Appendix I Additional Experimental Details

In this section, we support our theoretical results with an empirical study of
the GSH property of DNNs on real and synthetic data. First, we detail our
experimental setup and then discuss the experimental results.

###  I.1 Experimental Setup

We separate our experiments to two groups, based on the data generating
process.

##### Natural Images.

We train Myrtle-CNN [Pag18]—a five layer convolutional neural network—on MNIST
and CIFAR-10 with $\ell_{2}$ regularization without regularizing the bias
terms. For CIFAR-10 the width parameter is $c=128$ while for MNIST it is
$c=32$ and we remove the last two pooling layers. For both cases, we train via
the SGD optimizer for $50$ epochs with learning rate of $0.1$ then drop the
learning rate to $0.01$ for another $100$ epochs with batch size of $128$. We
use $\lambda=0.1$ The resulting test accuracies are $99.4\%$ for MNIST and
$88.9\%$ for CIFAR-10 while they also perfectly fit the train.

##### Synthetic Data.

For the synthetic data we do the following data generating process, as to
satisfy Assumption 1: first we randomly sample $\bm{\gamma}$ and $\bm{\theta}$
from the standard and $1/\sqrt{k}$ scaled Gaussians on $\mathbb{R}^{k}$
respectively for $k=11$. Then, we sample two random matrices $V,W$ from a
scaled Gaussian $\mathcal{N}\left(0,\frac{1}{d}I\right)$ on
$\mathbb{R}^{d\times k}$ and use an analytical function $\mathbf{p}$ such as
the $\sin(\cdot)$ to generate
$\mathbf{x}=\mathbf{p}(W\bm{\gamma}+U\bm{\theta})$. The analytic functions we
tried are $e^{x/2},\sin(x),\cos(x)$ and $\log((1+x^{2})/2)$. Note that the
last two are even functions, so precise recovery of $\bm{\gamma}$ is
impossible as $f(x)=f(-x)$. To increase the complexity of the manifold we sum
$4$ functions of each type, so for example, the final sine data generating
function is $\sum_{i=1^{4}}\sin(V_{i}\bm{\gamma}+W_{i}\bm{\theta})$. We also
call a sum of all 4 functions the _Mixture distribution_. Now, in order to
generate examples from the same manifold, we repeat the above process with
$V,W,\bm{\gamma}$ fixed and vary (generate) $\bm{\theta}$. We then train a
three layer Multi-Layer-Perceptron (MLP) with width $1000$ for $200$ epochs
via SGD with learning rate $0.1$, batch size of $32$ with
$\lambda=0.01$-$\ell_{2}$ regularization parameter and $\ell_{2}$ loss for
classification. The train/test accuracies after this procedure are $100\%$.

Meta learning and $\bm{\gamma}$ recovery. The main advantage of the synthetic
data is that we are able to generate as many manifold (and samples) as we
want. Therefore, we can check what is the $\rho$ not only on manifolds we saw
before, but also the behavior on the distribution. Moreover, we can generate
enough manifolds to hope to fit a linear classifier on top of the
representation. If the linear loss is small the representation is
approximately linearly isomorphic to $\bm{\gamma}$. This means that our
representation successfully recovered the manifold geometry.

In a similar fashion described in the Synthetic Data data generation process,
we generate $4$ datasets: train, test, few-shot and few-shot-test. In the
train (and test) there are $50$ classes (manifolds) with $8k$ train examples
and $2k$ test examples per class. As for the few-shot (and few-shot-test) we
generate $10000$ manifolds so their representations will serve as train set
for the linear classifier that will try to recover $\bm{\gamma}$. In order to
estimate the $\rho$ on the distribution of unseen manifold, we sample $5$
samples from each manifold to a total of $50000$ few-shot (train) samples. We
then use SGD with learning rate of $0.1$ and batch size of $32$ fit a linear
model with loss $\|r(\mathbf{x})-\bm{\gamma}\|_{2}^{2}$. Finally, we sample
another $100$ manifolds with one sample per manifold to estimate how well the
linear function recovered $\bm{\gamma}$. In order to measure how close the
representation is to an isomorphism, we use normalized distance as a metric
(see table 1), normalizing $\|Wr(\mathbf{x})-\bm{\gamma}\|_{2}^{2}$, where $W$
is the learnt linear model, by the average distance between two
$\bm{\gamma}$s: $\|\bm{\gamma}_{i}-\bm{\gamma}_{j}\|_{2}^{2}$. So a random
Gaussian will produce normalized distance of $1$ while perfect linear recovery
will be normalized distance of $0$.

###  I.2 Experimental Results

Our results for real data are in shown in Figure 4 and our results for
synthetic data are summarized in Table 1. We observe high $\rho$ values for
both real ($1.46$ for CIFAR-10 and $3.36$ for MNIST) and synthetic
distributions ($\rho\geq 10.7$) both on train and on test. Furthermore, for
synthetic data, we see that even out-of-distribution $\rho$ is high. This
implies that the classifier learnt is a GSH function on the population of
manifolds, effectively inverting the data generating process. Further, we see
that when the function is not even (and thus $\bm{\gamma}$ is not recoverable)
as is the case for the Sine, Log, Exp and Mixture distributions, we are able
to recover $\bm{\gamma}$ from the representation using a linear function.
Specifically the normalized $\bm{\gamma}$ recovery distance is at $\approx
0.1$ where a random $\gamma$ would yield a distance of $1$.

Table 1: Our results on synthetic data. We provide the $\rho$ value for 5 different synthetic distributions, on train, test and transfer (i.e., unseen $\bm{\gamma}$s). We also note the normalized distance of $\|\bm{\gamma}-\hat{\bm{\gamma}}\|$ where $\hat{\bm{\gamma}}$ is a linear classifier on top of the representation layer attempting to recover $\bm{\gamma}$. We are able to nicely recover the Mixture, Sine and Exp distributions, while recovering the $cos(x)$ and $\log((1+x^{2})/2)$ proves more difficult. The reason is that we fail to recover $\bm{\gamma}$ for these functions is that they are even, so there is an ambiguity of whether the sign is positive or negative. $\begin{subarray}{c}\text{Data Generating}\\\ \text{Function}\end{subarray}$ | $\begin{subarray}{c}\text{Test}\\\ \text{Accuracy}\end{subarray}$ |  $\rho$-Train |  $\rho$-Test |  $\rho$-Transfer | $\begin{subarray}{c}\text{Normalized $\bm{\gamma}$}\\\ \text{Recovery Distance}\end{subarray}$
---|---|---|---|---|---
Mixture | 100% | 19.13 | 19.09 | 20.46 | 0.11
Sine | 100% | 26.8 | 26.8 | 28.4 | 0.09
Cosine | 100% | 10.7 | 10.79 | 11.09 | 0.71
Log | 100% | 12.38 | 12.38 | 11.23 | 0.71
Exp | 100% | 25.2 | 25.2 | 28.77 | 0.08
Figure 5: A comparison of intra vs inter class distances for _Unseen Manifold_
for an MLP trained on Mixed synthetic data. Remarkably, even on unseen
manifolds the GSH property holds, that is the representation is invariant to
the “noisy feature” $\bm{\theta}$ while being sensitive to the semantically
meaningful feature $\bm{\gamma}$. Figure 6: We show the ability to recover
$\bm{\gamma}$ with linear regression over the representation with varying the
norm of $\bm{\theta}/\bm{\gamma}$. We see that when the norm of $\bm{\gamma}$
is dominating, the learnt representation is almost a linear function of
$\bm{\gamma}$. In contrast, when $\bm{\theta}$ has larger norm, the learnt
representation becomes a non-linear function of $\bm{\gamma}$. (We know that
$\bm{\gamma}$ and the representation are isomorphic as long as $\rho$ is large
enough.).


11institutetext: Faculty of Engineering, University of Porto, Porto, Portugal
11email<EMAIL_ADDRESS>22institutetext: PORTIC – Porto Research,
Technology & Innovation Center, Polytechnic of Porto (IPP), 4200-374 Porto,
Portugal
22email<EMAIL_ADDRESS>33institutetext: Faculty of Engineering,
University of Porto, Porto, Portugal & HASLab/INESC TEC
33email<EMAIL_ADDRESS>
# Patient-centric health data sovereignty: an approach using Proxy re-
encryption††thanks: This work was partially supported by the Norte Portugal
Regional Operational Programme (NORTE 2020), under the PORTUGAL 2020
Partnership Agreement, through the European Regional Development Fund (ERDF),
within project “Cybers SeC IP” (NORTE-01-0145-FEDER-000044).

Bruno Rodrigues 11 0009-0001-2929-0836 Ivone Amorim 22 0000-0001-6102-6165
Ivan Silva 22 0009-0009-8480-9352 Alexandra Mendes 33 0000-0001-8060-5920

###### Abstract

The exponential growth in the digitisation of services implies the handling
and storage of large volumes of data. Businesses and services see data sharing
and crossing as an opportunity to improve and produce new business
opportunities. The health sector is one area where this proves to be true,
enabling better and more innovative treatments. Notwithstanding, this raises
concerns regarding personal data being treated and processed. In this paper,
we present a patient-centric platform for the secure sharing of health records
by shifting the control over the data to the patient, therefore, providing a
step further towards data sovereignty. Data sharing is performed only with the
consent of the patient, allowing it to revoke access at any given time.
Furthermore, we also provide a _break-glass_ approach, resorting to Proxy Re-
encryption (PRE) and the concept of a centralised trusted entity that
possesses instant access to patients’ medical records. Lastly, an analysis is
made to assess the performance of the platform’s key operations, and the
impact that a PRE scheme has on those operations.

###### Keywords:

data-sovereigntycryptography PREaccess delegatione-health PHR

##  1 Introduction

The ever growing digitisation of services that we use daily, as well as the
increasing interest in data crossing and sharing to improve processes,
services, and achieve new business opportunities, raises concerns regarding
how data is handled and processed. In the healthcare sector, data sharing is
not only beneficial, but also needed to provide the best care possible to the
patients. However, this data is also highly sensitive, which requires special
care. Several governmental measures have already been taken to improve and
standardise the way in which data is shared, such as the European Data
Governance Act [1], GDPR111https://data.europa.eu/eli/reg/2016/679/oj, and,
more specifically in personal health information,
HIPAA222https://www.cdc.gov/phlp/publications/topic/hipaa.html and
HITECH333https://www.hipaajournal.com/what-is-the-hitech-act/. These
directives instigate a user-centric paradigm, granting individuals sovereignty
over their data.

Several approaches have been proposed for ensuring security and privacy in
e-health systems. Conventional encryption techniques like AES and ECC are
commonly used [5]. However, these techniques become problematic when data
needs to be shared among multiple entities due to redundancy and computational
burden [6]. Attribute-Based Encryption (ABE) is another solution [6], but it
has its own complexities and limitations, such as managing attribute-based
keys and overriding policies in emergencies [7]. ABE also lacks the fine-
grained access control necessary for a patient-centric sovereign approach.

Proxy Re-encryption (PRE) is a cryptographic solution for secure data sharing
without prior knowledge of the recipient. Unlike ABE, it does not rely on
policies or attributes. PRE converts a ciphertext to a recipient’s key without
revealing the plaintext to the intermediary entity. It is particularly useful
in semi-trusted cloud environments [17]. In e-health, PRE has already been
used to securely share medical records [20, 23, 19, 26], including in
emergency scenarios [19]. However, challenges remain in terms of revocability,
computational effort, and safeguarding emergencies [26]. Existing solutions
for emergency scenarios are limited and rely on assumptions that may impact
efficiency and reliability.

In this context, it is necessary to develop a platform that addresses the
aforementioned concerns. This includes enabling more control over the data by
the patient while ensuring the safety of that data, even in semi-trusted
environments. This contributes to the collaborative aspect of e-health and
thus enables better treatments and advancements in the health sector.

In this paper, we present a platform that leverages PRE to enhance health data
sharing. Umbral’s PRE [16] is used as the foundation for re-encryption
processes, through which we achieve unidirectionality and non-interactivity,
ensuring secure re-encryption from the patient to the data user (e.g.,
practitioners or health centres) without requiring the data user’s private
key. This approach centres on the expressed opinion of the patient to
authorise data sharing, eliminating the need for prior identification of
authorised parties — a drawback identified in previous solutions.
Additionally, our platform offers revocability options, such as time-based
access limits and patient-initiated access revocation. Importantly, the
revocation of accesses does not require changes to the encrypted healthcare
database, distinguishing our platform from the ones that rely on identity and
attribute-based PRE schemes.

Furthermore, in the context of healthcare, it is crucial to ensure data
sharing in emergency situations when explicit patient consent may not be
possible. Our platform addresses this challenge by incorporating a trusted
entity for data access when patient authorisation is infeasible.

In summary, our main contributions are:

  * •

A patient-centric platform, that empowers patients with sovereign control over
their health data, enabling granular access control and facilitating the
sharing of health records only with explicit consent.

  * •

Robust data protection using Umbral’s PRE, ensuring secure and encrypted
health data sharing without compromising the data user’s private key.

  * •

A robust access revocation mechanism that enables time-based access limits and
supports manual revocation by the patient at any time and with immediate
effect.

  * •

A break-glass mechanism to ensure seamless emergency data access.

The remainder of this paper is organised as follows. Section 2 introduces
basic concepts and definitions, as well as the classification and properties
of PRE schemes. Furthermore, an analysis is made concerning the framework on
which the access delegation mechanism is based. Section 3 presents the current
picture of the PRE and the advancements regarding break-glass scenarios.
Section 4 details the proposed solution and its implementation. Section 5 is
concerned with the performance test, respective results and discussion.
Lastly, Section 6 presents the conclusions and future work.

##  2 Proxy Re-encryption

PRE is a cryptographic technique that enables a third-party entity, named
proxy, to delegate access to encrypted data, without being able to infer the
plaintext content of that data. This is achieved by transforming a ciphertext
encrypted under one key into a ciphertext encrypted under a different key.

###  2.1 Syntax and basic definitions

Since PRE can be seen as a way to delegate decryption rights to a party, it is
possible to categorise the different entities according to the delegation
relation they possess with each other. The _delegator_ is the entity that owns
the data and delegates decryption rights. The _proxy_ is the intermediary
entity in the delegation process, which uses a re-encryption key (PRK) to
transform the ciphertext encrypted under the delegator’s public key into a
ciphertext that can be decrypted only by using the delegatee’s private key.
Finally, the _delegatee_ is the entity that accesses the information through
delegation of decryption rights by the delegator.

######  Definition 1 (PRE)

A PRE scheme can be defined based on five different algorithms:

  * •

KeyGen — On input of a security parameter $n$, the key generation algorithm
KeyGen outputs a public/private key pair ($pk_{A}$, $sk_{A}$) for a given user
A.

  * •

ReKey — On input of a public/private key pair ($pk_{A}$, $sk_{A}$) for user A
and a public/private key pair ($pk_{B}$, $sk_{B}$) for user B, a PRK
$rk_{\;A\rightarrow B}$ is computed.

  * •

Encrypt — Given the input of a public key $pk_{A}$ and a message $m\in{M}$,
the encryption algorithm outputs a ciphertext $c_{A}\in C_{1}$.

  * •

ReEncrypt — On input of a ciphertext $c_{A}\in C_{1}$ and a PRK
$rk_{\;A\rightarrow B}$, the re-encryption algorithm ReEncrypt transforms a
ciphertext $c_{A}\in C_{1}$ into a ciphertext $c_{B}\in C_{2}$.

  * •

Decrypt — Given a private key $sk_{A}$ from user A and a ciphertext
$c_{A}\,\in\,C_{S}\;(S\in\\{1,2\\})$ from user A, the same executes the
decryption algorithm and outputs the original message $m\in{M}$.

According to Qin et al.[18], a PRE scheme can be classified based on its
abilities. For example, regarding its directionality, we say that the scheme
is _unidirectional_ if it enables the delegator’s ciphertext to be re-
encrypted into the delegatee’s ciphertext but not vice versa. Otherwise, we
call it _bidirectional_. The multi-use/single-use classification focuses on
the number of times the PRK can be used to re-encrypt data. In _multi-use_
schemes, the PRK can be utilised to perform several re-encryptions. In the
case of a _single-use_ scheme, the PRK can only be used to perform a single
transformation. Interactivity dictates whether the re-encryption is computed
using just the public key from the delegatee (_non-interactive_ scheme) or
both the public and private keys (_interactive_ scheme). Depending on the
scenario of utilisation, some properties may be more desirable than others.

Other authors classify PRE schemes according to their way of functioning [9,
10]. For example, an Identity-Based PRE (IB-PRE) scheme derives public keys
from identity attributes (e.g. email). The messages are encrypted using an
identity string from the delegatee. Attribute-Based PRE (AB-PRE) schemes allow
transforming a ciphertext defined by a set of attributes or access policies
into another ciphertext with a different set of attributes.

###  2.2 Umbral’s PRE scheme

The Umbral PRE scheme is, in its essence, a threshold PRE scheme. This scheme
features an Elliptic Curve Integrated Encryption Scheme (EICS-KEM) inspired in
[2] and proposes several improvements over the original PRE scheme proposed by
[4], namely unidirectionality, non-interactivity, and verifiability. It relies
on the concept of semi-trusted proxies, also known as ursulas. Being a
threshold PRE scheme, it splits the PRK according to shares. The _threshold_
portion of the scheme dictates the minimum number of those shares required to
decrypt the information.

Splitting the PRK across multiple proxies brings some benefits namely
eliminating a single point of failure, in case of a malfunction or compromise
of one of the proxies the PRK is still safeguarded.

The re-encryption processes in our platform are supported by pyUmbral [15], a
Python-based implementation of Umbral.

Fig. 1 presents an overview of the key processes and data flows involved in
the Umbral PRE scheme. This system beholds seven main processes:
_Encapsulation_ , _Encryption_ , _Generate PRK fragments_ , _Re-encapsulation_
, _Decapsulation_ , and _Decryption_. These processes are supported by three
major cryptographic methods: Key Encapsulation Mechanism (KEM), Data
Encapsulation Mechanism (DEM), and Shamir Secret Sharing (SSS) [21].

Figure 1: Procedural overview of pyUmbral PRE scheme

The first step in this process is _Encapsulation_. This is achieved through
the use of a Key Encapsulation Mechanism (KEM), in this case, a loosely
inspired implementation of ECIES-KEM introduced by [22]. The KEM is fed with
Alice’s public key $pk_{A}$ and outputs a symmetric key $K$, and a _capsule_.

With the capsule and the symmetric key $K$, the _Encryption_ process is
performed using a Data encapsulation mechanism (DEM) which uses Authenticated
Encryption with Additional Data (AEAD). This outputs a ciphertext encrypted
with the symmetric key.

When the data is encrypted and stored in the cloud, in order for the access
delegation to occur, there is a need to generate a PRK. This is performed by
the _Generate PRK fragments_ process resorting to the notions present in
Shamir Secret Sharing (SSS), Alice’s private key and signing key $signk_{A}$,
and Bob’s public key $pk_{B}$. This enables the generation of the PRK
fragments or _kFrags_. The number of fragments is defined by the number of
shares.

The _kFrags_ are stored by the proxy for further use in the _Re-encapsulation_
process. This process is responsible for generating the _cFrags_ which enables
Bob to gain access to the file at a later stage. To generate the _cFrags_ just
the capsule and the _kFrags_ are needed. This is due to the fact that this PRE
scheme performs the re-encryption over the capsule.

Lastly, once Bob wants to retrieve a file, the _Decapsulation_ process needs
to happen. This process resorts to SSS in order to reconstruct the symmetric
key $k$. To do so, Alice’s public key, Alice’s verifying key $vk_{A}$ for
signature verification of the _cFrags_ , Bob’s private key $sk_{B}$, and the
_capsule_ are needed. Through the use of a Key Derivation Function within the
KEM, it is possible to derive the symmetric key $K$ which together with the
ciphertext is passed to the DEM. The DEM performs the _Decryption_ process and
outputs the plaintext content of the file that Bob can now use.

##  3 Related work

The notion of PRE made its first appearance in 1998 when Blaze et al. [4]
introduced the concept of bidirectional and multi-use PRE. Several works have
been published since then with new PRE schemes providing new functionalities
and relying on different mathematical assumptions. For example, both [8] and
[11] proposed a unidirectional, single-use PRE scheme, but the first relies on
threshold PKE, while the second is based on lattice-hardness problems. In
2015, [14] also proposed a unidirectional and single-use PRE scheme, which can
be classified as attribute-based. Later, in 2017, [16] presented a
unidirectional, non-interactive, and verifiable PRE scheme which is threshold-
based.

In the context of healthcare data sharing, PRE has also been widely explored.
In fact, several works address security, privacy, and confidentiality when it
comes to the design and implementation of e-health systems. However, there is
still a lack of development concerning safeguarding emergency scenarios in the
context of e-health systems [26]. Works that address this kind of scenario in
its design, refer to this as break-glass approaches. In 2017, [3] proposed a
framework for the secure sharing of Personal Health Records (PHRs) that relies
on attribute-based PRE and which addresses emergency scenarios. The break-
glass capabilities are provided with ABE. In this scheme, the emergency
department attribute is always appended to the policy that encrypts the
patient PHR, thus providing instant access to the entity from the moment the
same is uploaded. The problem with this approach, and in general with ABE
approaches, is that they present some caveats, namely key management and
resorting to other mechanisms in break-glass approaches. This is due to the
fact that emergency normally means an exception to a policy and, thus,
overriding that same policy might be a hefty task in some implementations. In
2019, [25] also proposed an approach that is based on an attribute-based PRE,
and provided self-adaptive access control, meaning that the system can
automatically adapt to normal or emergency situations. However, their break-
glass mechanism resorts to a _password-based_ paradigm. This approach raises
some concerns, namely in the assumption that the individual that stores the
password, has the necessary means to ensure its secrecy. More recently, in
2022, [13] proposed a system for IoT sensors combining PRE and PKE with
equality test, permitting searches under different public keys and secure data
sharing. However, it does not discuss emergency situations. In the same year,
[20], proposed a non-interactive, multi-use, certificateless PRE for sharing
health data in a cloud environment. Even though their approach gives full
control to the data owner, it has two important drawbacks, namely it is
interactive and does not propose a break-glass mechanism. Also in 2022, [24]
published a secure data sharing and authorised Searchable framework for
e-healthcare systems. This framework lies on a conditional and unidirectional
PRE scheme with keyword search. It is also idealised for managing sensible
data from medical wearable devices. This platform has some disadvantages
namely regarding the PRK generation performance. Also, this work does not
address emergency situations. Finally, in 2022, [12] propose a framework which
is also based on attribute-based PRE that features break-glass capabilities.
However, it leaves open the possible solution for revocability. That being
said, there is a need to develop a solution that can cope with all the
aforementioned concerns and that contributes to a more reliable and robust
break-glass approach.

##  4 Patient-centric health data sovereignty

In this section, we introduce the envisioned solution for a patient-centric
platform that enables health data sovereignty through PRE. The subsequent
section presents the architecture of the solution, followed by a description
of the processes involved in the key operations for access delegation.

###  4.1 Proposed Solution

The proposed solution consists of four main nodes: the client, the resource
server, the proxy server, and the authorization server, as depicted in Figure
2.

Figure 2: Deployment diagram of the idealised architecture

The client node hosts the client-side application developed with
Next.js444https://nextjs.org/. This client node communicates with the server
nodes via Representation State Transfer (REST) and the Hypertext Transfer
Protocol (HTTP). The business logic is divided between the resource and proxy
server nodes. The resource server is based on the FastAPI
framework555https://fastapi.tiangolo.com/ running in a Python environment.
This server is trusted by the data delegator and it is responsible for
assisting the client-side operations, namely feeding the data the client node
needs to display the information to the user. The resource server node also
performs some core operations such as the initial encryption and final
decryption of the Electronic Health Record (EHR) stored in the database server
node hosted in a cloud environment (MongoDB666https://www.mongodb.com/) as
well as the management of delegation requests (accept or decline). Some other
complementary operations are also performed such as the generation of the PRK
which is stored afterwards by the proxy server node, and the signature
verification of the PRK fragments and capsule fragments.

The proxy server is solely responsible for the process of EHR delegation,
being used for the re-encryption of the capsules and the storage of the PRK.

The authorisation server is responsible for performing the authentication of
the different users of the platform as well as the issuing and claims
verification of the authorisation tokens. These tokens are subsequently used
to consume the APIs provided by the resource and proxy server nodes. This node
is also associated with two persistence nodes. An in-memory database
(REDIS777https://redis.com/ instance) for persisting and performing the lookup
of the refresh tokens and a MongoDB instance for storing general purpose user
information such as name, email, password, public and verifying keys and
roles.

###  4.2 Authentication/Authorisation

The authorisation is performed by resorting to JSON Web Tokens (JWT) which are
signed using HMAC SHA256. This ensures the tokens can not be tampered with or
changed, thus enabling secure transmissions between parties.

The authentication flow comprises a traditional email/password authentication,
where each user needs to provide a valid email and password. In case of
successful authentication, a pair of tokens are issued (access/refresh token)
containing some claims needed to support the client-side application. These
claims follow the standards and restrictions defined in Request for Comments
7519888https://datatracker.ietf.org/doc/html/rfc7519#section-4. Besides the
pair of tokens, a Cross-site Request Forgery token is also sent for further
protection in requests that require cookies. The refresh token is also sent in
a cookie configured with the _secure_ and _httpOnly_ flags to ensure it is
only transmitted through HTTPS and not available to JavaScript in case of a
Cross-site Scripting vulnerability in the client-side application.

Since JWT tokens are self-contained, there is no natural way of revoking them.
In order to tackle this problem anti-theft mitigation techniques were
implemented: _refresh token rotation_ and _token reuse detection_.

###  4.3 Access delegation scenario

Access delegation is the core problem tackled in this work. The next sections
dissect the access delegation flow from the moment the file is uploaded by the
patient to the moment the plaintext content is retrieved by the healthcare
provider. For demonstration purposes, the step-by-step process between two
entities, Alice (delegator) and Bob (delegatee), is presented.

Upload of an EHR The access delegation starts with the upload of an EHR by
Alice. When Alice uploads a new EHR, which can be a Portable Document Format
(PDF) or an image, the resource server encrypts the file using a symmetric key
resulting from the encapsulation process and stores it together with the
capsule, resulting from the _encapsulation_ process, and an associated
_userId_.

Another process that is also performed in this step and further detailed in
Section 4.4 is the safeguarding of emergency situations. Besides the
persistence of the file in the database, a PRK is also generated in order to
provide access to the predefined trusted entity. This ensures that the trusted
party possesses the means to access the file from the moment it is uploaded
and that no extra input from the user is needed in this regard. This PRK is
sent to the proxy for subsequent use.

Bob requests access to an EHR When Bob wants to access Alice’s uploaded EHR,
he needs to formalise his intentions by issuing a share request to the
resource server containing the EHR’s _resourceId_. In this step, the system
checks if Bob is the owner of the EHR. This prevents a user from performing a
share request to itself, something that violates the business rules of the
platform.

Once this validation is performed, and provided with the _resourceId_ , the
resource server generates a share request that includes the _resourceId_ , the
_delegatorId_ and the _delegateeId_ , as well as a _status_ that is set to
pending by default.

Alice answers the share request Now that Bob asked Alice for access to the
EHR, Alice is now capable of answering the share request. Depending on Alice’s
answer, the execution flow might have two outcomes:

Accept scenario — In case of an acceptance, Alice needs to generate the PRK
required to re-encrypt the capsule and further enable Bob to have access to
the plaintext content of the EHR. To achieve such a feat, Alice requires his
secret key along with his signing key pair, needed to verify the signature of
the _kFrags_ and _cFrags_ at a later stage, as well as Bob’s public key.
Notice that just the public key is needed, due to the non-interactivity
property of this PRE scheme. Lastly, since the underlying scheme of the access
delegation mechanism is a threshold PRE scheme, there is also the need to
provide a _threshold_ which defines the minimum number of shares needed to
decrypt the capsule and the number of _shares_ which dictates the number of
outputted PRK fragments. This last aforementioned operation outputs the
_kFrags_ , which are sent to the proxy along with a _shareId_ binding the PRK
to a specific share request. Both attributes are persisted by the proxy for
further use once Bob retrieves the EHR.

The share request operation ends with the status update of the share request,
which is defined as accepted, together with an arbitrary expiration date
defined by Alice. This expiration date is optional, being possible to share an
EHR indefinitely or temporarily, in which case the share request is
automatically revoked through a cron job once that date is transposed. This
ensures the time-based access delegation aspect that this work contributes to.

Decline scenario — In case Alice declines the share request the status is
updated accordingly and no other action is performed.

Bob retrieves the EHR Now that Alice explicitly delegated access to the EHR,
Bob is now capable of retrieving it. To do so, Bob performs a request to the
resource server, which requires Bob’s secret key and the _resourceId_ , which
uniquely identifies the EHR. A file ownership verification is also performed
since the decryption steps are different for a delegator and a delegatee,
where the former does not have the need to re-encrypt the _capsule_.

As stated previously, ownership trails different paths regarding execution
flow. With that said, the following can happen whether the user is or not a
data owner.

Data owner — In case the user that requests the file is a data owner, a hybrid
encryption approach is used, thus no re-encryption takes place.

Not a data owner — If the user is not the data owner, meaning they are a
delegatee, a collaborative operation between the resource and proxy servers is
required to take place. For this specific scenario, Bob needs to ask the proxy
to re-encrypt the capsule using the previously generated PRK. To that purpose,
the resource server retrieves the EHR details and sends the capsule to the
proxy server. The proxy, equipped with the capsule and the PRK fragments
_kFrags_ , performs the _re-encapsulation_ process outputting the _cFrags_.
These _cFrags_ are sent back to the resource server, which validates their
signature through Alice’s verifying key. Once the capsule fragments are
validated, Bob decrypts the file by opening the capsule. This last step
encompasses Bob’s private key, Alice’s verifying key and the verified
_cFrags_. With the plaintext content of the EHR, Bob is now capable of
accessing the information.

Some important remarks to highlight are that the secret key used in the
sharing process is never shared with the intermediary entity or proxy, making
it semi-trusted. Additionally, the proxy only stores the PRK, which alone does
not grant it the capability to decrypt the file. Furthermore, even if the
stored information such as the capsule, PRK, and ciphertext were to be leaked
from the database, the safety and integrity of the EHRs would still be
preserved, as they are not sufficient for decrypting the EHRs.

###  4.4 Break-glass approach

Safeguarding emergency scenarios is of paramount importance in a health-
related platform. Therefore, we adopted amd approach that features a central
trustworthy entity responsible for managing the authorisation in emergency
scenarios. This trustworthy entity is seen as a government entity that is
responsible for managing such issues and has full access to the files
submitted in the platform.

The implementation is similar to what is described in Section 4.3 regarding
Alice accepting the share request. However, in this case, there is no explicit
acceptance of the share request. When an EHR is uploaded, the trusted entity
user is retrieved from the database and a PRK is generated. An accepted share
request is automatically created for the trusted entity, which links the PRK
to the share request between the patient and the trusted entity.

Regarding the process of retrieving the EHR, it follows a similar procedure as
depicted in Section 4.3. Just like in a regular file retrieval, since the
share request is automatically accepted and the proxy possesses the PRK, the
trusted entity requests the proxy to re-encrypt the capsules, enabling the
final decryption to take place.

This approach vastly reduces the dependency on external actors, increasing the
reliability and availability of the idealised break-glass approach. Having a
dedicated entity for this purpose enables instant and swift access to the
information if needed.

##  5 Performance analysis

In this section, we present the performance tests conducted to evaluate our
platform. Given the common concerns of limited hardware infrastructures and
sub-optimal conditions in governmental adoption cases, it is important to
assess the responsiveness of the key operations offered by the platform. Our
main goal is to quantitatively analyze the performance of the most
computationally intensive operations and assess the impact of the PRE scheme.
As there are no specific regulations, indications, or suggestions regarding
performance for this type of platform, our tests are purely quantitative and
based on known factors and conditions.

The performance tests were carried out on a deployed version of the platform,
hosted in Microsoft Azure using a Free F1 tier running Linux and Python 3.10.
While these specifications may be basic, they are sufficient to simulate a
sub-optimal environment. In real-world scenarios, it is common for governments
to have financial restrictions, making it likely that the platform would be
deployed on infrastructure with modest specifications. The tests were
conducted using Apache JMeter as the tool of choice.

In the rest of this section, we present the results related to the three most
crucial operations of the platform and which involve the use of PRE: file
upload, accepting a share request, and file retrieval. Additionally, a brief
analysis of the results is also presented.

File upload The performance tests depicted in this section aim to evaluate how
the different file sizes impact the upload performance of files.

Since the size of EHRs depends on various factors, such as the patient’s
medical history, the image resolution of the machines used for exams, and the
content of the file itself, determining an average file size becomes
challenging. Therefore, we conducted our experiments using two different file
sizes: 1MB and 10MB.

Figure 3 illustrates the results obtained from a series of twenty runs
performed for each file size.

Figure 3: Performance Tests - File Size Uploads Bar Chart

It can be observed that a tenfold increase in file size reflected an average
increase of 2715  _milliseconds_(ms) when comparing file sizes of 1MB and 10MB
respectively. The former took an average of 1154  _ms_ and the latter an
average of 3870  _ms_.

Despite a time of almost four _seconds_ , and considering this is not an ideal
response time for a REST API, it should be taken into account the complexity
of the operations performed. Since this is not a critical operation when it
comes to performance, these values are acceptable.

Accepting a share request The acceptance of a share request is a key operation
in the platform described in this paper. Although its performance does not
possess a high impact on the efficiency of the platform, it does provide
valuable information regarding the PRE process. In this operation, the PRK is
generated and sent to the proxy for persistence purposes. Notice that, in this
case, there was no need to perform the tests for both file sizes since the PRK
generation only depends on cryptographic keys.

Regarding the results of these tests, the average time obtained in 20 runs was
869  _ms_. This quick response was expected since the generation of the PRK
fragments is a relatively simple operation that depends on the cryptographic
key from both ends, the signature, and the number of shares. Additionally,
there was not a significant variation among the twenty runs that were
performed. This is supported by the low standard deviation of just 188  _ms_.

File retrieval This set of tests aims to assess the impact of file sizes and
the use of PRE on a file retrieval scenario. The tests were conducted for both
regular decryption and PRE decryption. To evaluate the impact of file sizes,
the tests were performed for both 1MB and 10MB file sizes.

Moving on to the obtained results (Fig.5), a 1MB file took an average of 903
_ms_ to be retrieved while the 10MB one took an average of 2529  _ms_.
Regarding file retrieval with PRE, the 1MB file took an average of 1245  _ms_
and 2877  _ms_ for the 10MB file.

We have also evaluated the impact of re-encryption on file retrieval
operations (Fig.5) by directly measuring the difference between regular
decryption and PRE for each file size. This resulted in an average difference
of 342  _ms_ for the 1MB file and 348  _ms_ for the other one.

Figure 4: Performance Tests - Average Time Taken for File Retrieval

Figure 5: Performance Tests - Average Impact of PRE in Same Sized Files

The results of our tests indicate that there is a similar average difference
between regular and PRE decryption for both file sizes. This similarity can be
attributed to the fact that the re-encryption process only affects the
capsule, not the actual file. Since the sizes of the capsule and cryptographic
keys are similar in both scenarios, it is expected that the results would be
similar as well. The file size does not significantly impact the re-encryption
of the capsule, but rather affects the overhead associated with fetching the
file from the database and delivering it in the response.

Regarding the obtained results, they were deemed satisfactory since most
operations do not possess restrictive requirements when it comes to
performance.

Regarding more critical operations such as file retrieval, considering the
computational effort and infrastructure complexity required to ensure full
correctness with the underlying threshold PRE scheme, the results were deemed
satisfactory. It is important to note that these tests were conducted in a
shared infrastructure with modest specifications. Thus, it was not possible to
control the current workload of the servers during the tests, which may have
impacted negatively the aforementioned results

##  6 Conclusion

In this paper, we present a PRE-based platform for the secure sharing of
e-health, considering a sovereign approach focused on the patient. This
approach is achieved by ensuring that the patient’s data is only shared with
their explicit consent. Furthermore, it also enables robust revocability by
the patient, without requiring updates on the encrypted EHR database, further
contributing to a user-centric approach. Non-interactivity is also a key
characteristic of our platform, which does not require sharing user’s private
key for the re-encryption process to occur. Another key achievement of our
work is the proposed break-glass mechanism. Since some implementations fall
short in terms of revocability, and only a few contemplate PRE in emergency
scenarios, our solution uses a central trusted entity to which the proxy
delegates access from the moment the EHR is uploaded to the platform. This
eliminates the need to trust external actors in the system, increasing
reliability and allowing swift access to the information in critical
situations. There are other key characteristics of our platform worth
highlighting. Firstly, it uses symmetric encryption to encrypt the EHR, which
is faster than PKE. Secondly, the re-encryption process is performed over the
capsule, which tends to have a much smaller size compared to a PHR. The tests
that were conducted and our results show that the most demanding task is the
upload of the EHR, as expected, because it requires the encapsulation process
to occur and the encryption of the EHR. However, the re-encryption process
does not show a significant increase when the size of the uploaded files
increases. This is because the re-encryption does not involve the EHR. Our
platform provides a solution to the sharing of medical data that incorporates
key functionalities not covered together in previous literature, such as
unidirectionality, non-interactivity, revocability, and a mechanism to deal
with emergency situations. This solution contributes to the collaborative
aspect of e-health and enables better, and more informed treatments supported
by the increased exchange of information between providers.

Regarding future work, it would be beneficial to extend the architecture to
accommodate multiple proxies instead of using just one. This could be achieved
by utilising a blockchain network where the proxies work together to re-
encrypt the capsules, thus enabling all the benefits that a threshold-based
scheme has to offer. Furthermore, additional tests could be performed using
different environments and network conditions to cover more use case
scenarios.

## References

  * [1] Regulation (EU) 2022/868 of the European Parliament and of the Council of 30 May 2022 on European data governance and amending Regulation (EU) 2018/1724 (Data Governance Act) (Text with EEA relevance) (May 2022), http://data.europa.eu/eli/reg/2022/868/oj/eng, legislative Body: CONSIL, EP
  * [2] American National Standards Institute (ANSI) X9.F1 subcommittee. ANSI X9.63 Public key cryptography for the Financial Services Industry: Elliptic curve key agreement and key transport schemes (Jul 5, 1998), working draft version 2.0
  * [3] Au, M.H., Yuen, T.H., Liu, J.K., Susilo, W., Huang, X., Xiang, Y., Jiang, Z.L.: A general framework for secure sharing of personal health records in cloud system. Journal of Computer and System Sciences 90, 46–62 (2017). https://doi.org/https://doi.org/10.1016/j.jcss.2017.03.002
  * [4] Blaze, M., Bleumer, G., Strauss, M.: Divertible protocols and atomic proxy cryptography. Advances in Cryptology—EUROCRYPT’98 pp. 127–144 (1998)
  * [5] Edemacu, K., Park, H.K., Jang, B., Kim, J.W.: Privacy provision in collaborative ehealth with attribute-based encryption: Survey, challenges and future directions. IEEE Access 7, 89614–89636 (2019). https://doi.org/10.1109/ACCESS.2019.2925390
  * [6] ENISA: Engineering personal data sharing - emerging use cases and technologies (January 2023), https://www.enisa.europa.eu/publications/engineering-personal-data-sharing
  * [7] Fernández-Alemán, J.L., Señor, I.C., Ángel Oliver Lozoya, P., Toval, A.: Security and privacy in electronic health records: A systematic literature review. Journal of Biomedical Informatics 46(3), 541–562 (2013). https://doi.org/https://doi.org/10.1016/j.jbi.2012.12.003
  * [8] Hanaoka, G., Kawai, Y., Kunihiro, N., Matsuda, T., Weng, J., Zhang, R., Zhao, Y.: Generic construction of chosen ciphertext secure proxy re-encryption. In: Dunkelman, O. (ed.) Topics in Cryptology – CT-RSA 2012. pp. 349–364. Springer Berlin Heidelberg, Berlin, Heidelberg (2012)
  * [9] Inbarani, W.S., Shenbagamoorthy, G., Kumar Charlie, C.: Proxy re-encryption schemes for data storage security in cloud- a survey. International Journal Of Engineering Research & Technology (IJERT) 02(01) (2013)
  * [10] Khan, F.: A comparison of proxy re-encryption schemes – a survey. International Journal of Computer Science and Information Security (IJCSIS) 14, 392–397 (07 2016)
  * [11] Kirshanova, E.: Proxy re-encryption from lattices. In: PKC. pp. 77–94. Springer (2014). https://doi.org/10.1007/978-3-642-54631-0_5
  * [12] Li, M., Yu, S., Ren, K., Lou, W.: Securing personal health records in cloud computing: Patient-centric and fine-grained data access control in multi-owner settings. In: Jajodia, S., Zhou, J. (eds.) Security and Privacy in Communication Networks. pp. 89–106. Springer Berlin Heidelberg, Berlin, Heidelberg (2010)
  * [13] Li, W., Jin, C., Kumari, S., Xiong, H., Kumar, S.: Proxy re-encryption with equality test for secure data sharing in internet of things-based healthcare systems: Na. Transactions on Emerging Telecommunications Technologies 33, e3986 (06 2020). https://doi.org/10.1002/ett.3986
  * [14] Liang, K., Fang, L., Wong, D., Susilo, W.: A ciphertext-policy attribute-based proxy re-encryption scheme for data sharing in public clouds: A cp-abpre for data sharing in public clouds. Concurrency and Computation: Practice and Experience 27 (10 2014). https://doi.org/10.1002/cpe.3397
  * [15] NuCypher: pyumbral. https://github.com/nucypher/pyumbral (2018)
  * [16] Nuñez, D.: Umbral: A threshold proxy re-encryption scheme (2017), https://raw.githubusercontent.com/nucypher/umbral-doc/master/umbral-doc.pdf
  * [17] Nuñez, D., Agudo, I., Lopez, J.: Proxy re-encryption: Analysis of constructions and its application to secure access delegation. Journal of Network and Computer Applications 87, 193–209 (2017). https://doi.org/https://doi.org/10.1016/j.jnca.2017.03.005
  * [18] Qin, Z., Xiong, H., Wu, S., Batamuliza, J.: A survey of proxy re-encryption for secure data sharing in cloud computing. IEEE Transactions on Services Computing pp. 1–1 (2016). https://doi.org/10.1109/TSC.2016.2551238
  * [19] Rabieh, K., Akkaya, K., Karabiyik, U., Qamruddin, J.: A secure and cloud-based medical records access scheme for on-road emergencies. In: 2018 15th IEEE Annual Consumer Communications & Networking Conference (CCNC). pp. 1–8 (2018). https://doi.org/10.1109/CCNC.2018.8319175
  * [20] Ren, C., Dong, X., Shen, J., Cao, Z., Zhou, Y.: Clap-pre: Certificateless autonomous path proxy re-encryption for data sharing in the cloud. Applied Sciences 12(9) (2022). https://doi.org/10.3390/app12094353
  * [21] Shamir, A.: How to share a secret. Commun. ACM 22(11), 612–613 (nov 1979). https://doi.org/10.1145/359168.359176
  * [22] Shoup, V.: A proposal for an iso standard for public key encryption. Cryptology ePrint Archive, Paper 2001/112 (2001), https://eprint.iacr.org/2001/112
  * [23] Thilakanathan, D., Chen, S., Nepal, S., Calvo, R., Alem, L.: A platform for secure monitoring and sharing of generic health data in the cloud. Future Generation Computer Systems 35, 102–113 (2014), special Section: Integration of Cloud Computing and Body Sensor Networks; Guest Editors: Giancarlo Fortino and Mukaddim Pathan
  * [24] Xue, L.: Dsas: A secure data sharing and authorized searchable framework for e-healthcare system. IEEE Access 10, 30779–30791 (2022). https://doi.org/10.1109/ACCESS.2022.3153120
  * [25] Yang, Y., Zheng, X., Guo, W., Liu, X., Chang, V.: Privacy-preserving smart iot-based healthcare big data storage and self-adaptive access control system. Information Sciences 479, 567–592 (2019). https://doi.org/https://doi.org/10.1016/j.ins.2018.02.005
  * [26] Yüksel, B., Küpçü, A., Öznur Özkasap: Research issues for privacy and security of electronic health services. Future Generation Computer Systems 68, 1–13 (2017). https://doi.org/https://doi.org/10.1016/j.future.2016.08.011