G_{1}(\mathbf{W}_{t})\in\mathcal{B}\big{(}0,2(\sqrt{2c_{0}\eta
T}+\|\mathbf{W}_{0}\|_{2})\big{)}$ and $\mathbf{W}_{t}^{(i)}-\eta\nabla
G_{2}(\mathbf{W}_{t}^{(i)})\in\mathcal{B}\big{(}0,2(\sqrt{2c_{0}\eta
T}+\|\mathbf{W}_{0}\|_{2})\big{)}$. On the other hand, similar to Lemma B.2,
we can show that $G_{1}(\mathbf{W})$ and $G_{2}(\mathbf{W})$ is
$8\hat{\rho}$-smooth for any
$\mathbf{W}\in\mathcal{B}\big{(}0,2(\sqrt{2c_{0}\eta
T}+\|\mathbf{W}_{0}\|_{2})\big{)}$. Combining the above results, we can get

$G_{1}(\mathbf{W}_{t}-\eta\nabla G_{1}(\mathbf{W}_{t}))\leq
G_{1}(\mathbf{W}_{t})-\eta\big{(}1-{4\eta\hat{\rho}}\big{)}\|\nabla
G_{1}(\mathbf{W}_{t})\|_{2}^{2},$ (B.14)
$G_{2}(\mathbf{W}_{t}^{(i)}-\eta\nabla G_{2}(\mathbf{W}_{t}^{(i)}))\leq
G_{2}(\mathbf{W}_{t}^{(i)})-\eta\big{(}1-{4\eta\hat{\rho}}\big{)}\|\nabla
G_{2}(\mathbf{W}_{t}^{(i)})\|_{2}^{2}.$ (B.15)

If we can further show that

$G_{1}(\mathbf{W}_{t}-\eta\nabla G_{1}(\mathbf{W}_{t}))\geq
G_{1}(\mathbf{W}_{t}^{(i)})-\frac{\tilde{\epsilon}_{t}}{2}\|\mathbf{W}_{t}-\mathbf{W}_{t}^{(i)}-\eta\nabla
G_{1}(\mathbf{W}_{t})\|_{2}^{2},$ (B.16)
$G_{2}(\mathbf{W}_{t}^{(i)}-\eta\nabla G_{2}(\mathbf{W}_{t}^{(i)}))\geq
G_{2}(\mathbf{W}_{t})-\frac{\tilde{\epsilon}_{t}}{2}\|\mathbf{W}_{t}^{(i)}-\mathbf{W}_{t}-\eta\nabla
G_{2}(\mathbf{W}_{t})\|_{2}^{2},$ (B.17)

with $\tilde{\epsilon}_{t}=C_{3,T}\big{(}B_{3}\big{(}\frac{\sqrt{\eta
T}+\|\mathbf{W}_{0}\|_{2}}{m^{2c-\frac{1}{2}}}+m^{1-2c}\big{)}\big{(}(1+\eta\hat{\rho})\|\mathbf{W}_{t}-\mathbf{W}_{t}^{(i)}\|_{2}+2\big{(}\sqrt{2c_{0}\eta
T}+\|\mathbf{W}_{0}\|_{2}\big{)}+\sqrt{2c_{0}}\big{)}$, where
$C_{3,T}=4B_{1}\big{(}2c_{0}\eta
T{m^{-3c}}+\big{(}{m^{\frac{1}{2}-2c}}+{m^{\frac{1}{2}-3c}}\big{)}\sqrt{2c_{0}\eta
T}+{m^{1-3c}}+{m^{\frac{1}{2}-2c}}\big{)}$. Then combining (B.14), (B.15),
(B.16) and (B.17) together yields

$G_{1}(\mathbf{W}_{t})-G_{1}(\mathbf{W}_{t}^{(i)})\geq\eta\big{(}1-{4\eta\hat{\rho}}\big{)}\|\nabla
G_{1}(\mathbf{W}_{t})\|_{2}^{2}-\frac{\tilde{\epsilon}_{t}}{2}\|\mathbf{W}_{t}-\mathbf{W}_{t}^{(i)}-\eta\nabla
G_{1}(\mathbf{W}_{t})\|_{2}^{2},$
$G_{2}(\mathbf{W}_{t}^{(i)})-G_{2}(\mathbf{W}_{t})\geq\eta\big{(}1-{4\eta\hat{\rho}}\big{)}\|\nabla
G_{2}(\mathbf{W}_{t})\|_{2}^{2}-\frac{\tilde{\epsilon}_{t}}{2}\|\mathbf{W}_{t}^{(i)}-\mathbf{W}_{t}-\eta\nabla
G_{2}(\mathbf{W}_{t})\|_{2}^{2}.$

Plugging the above two inequalities back into (B.13) yields

$\displaystyle\langle\mathbf{W}_{t}-\mathbf{W}_{t}^{(i)},\nabla
L_{S^{\setminus i}}(\mathbf{W}_{t})-\nabla L_{S^{\setminus
i}}(\mathbf{W}^{(i)}_{t})\rangle=G_{1}(\mathbf{W}_{t})-G_{1}(\mathbf{W}_{t}^{(i)})+G_{2}(\mathbf{W}_{t}^{(i)})-G_{2}(\mathbf{W}_{t})$
$\displaystyle\\!\geq\\!2\eta\big{(}1\\!-\\!{4\eta\hat{\rho}}\big{)}\big{\|}\nabla
L_{S^{\setminus i}}\\!(\mathbf{W}_{t})\\!-\\!\nabla L_{S^{\setminus
i}}\\!(\mathbf{W}^{(i)}_{t})\\!\big{\|}_{2}^{2}\\!\\!-\\!\tilde{\epsilon}_{t}\big{\|}\mathbf{W}_{t}\\!-\\!\mathbf{W}_{t}^{(i)}\\!\\!-\\!\eta\big{(}\nabla
L_{S^{\setminus i}}\\!(\mathbf{W}_{t})\\!-\\!\nabla L_{S^{\setminus
i}}\\!(\mathbf{W}_{t}^{(i)})\big{)}\\!\big{\|}_{2}^{2}.$

The desired result has been proved.

Now, we give the proof of (B.16) and (B.17). For $\alpha\in[0,1]$, let
$\mathbf{W}(\alpha)=\alpha\mathbf{W}_{t}+(1-\alpha)\mathbf{W}_{t}^{(i)}-\alpha\eta\big{(}\nabla
L_{S^{\setminus i}}(\mathbf{W}_{t})-\nabla L_{S^{\setminus
i}}(\mathbf{W}_{t}^{(i)})\big{)}$. For any $\alpha\in[0,1]$, it’s obvious that
$\|\mathbf{W}(\alpha)\|_{2}\leq 2(\sqrt{2c_{0}\eta t}+\|\mathbf{W}_{0}\|_{2})$
by using Lemma B.2. Combining this observation with (B.8) we can obtain

$\displaystyle\lambda_{\min}\big{(}\nabla^{2}L_{S^{\setminus
i}}(\mathbf{W}(\alpha))\big{)}$
$\displaystyle\geq-\max_{j\in[n]}\|\nabla^{2}f_{\mathbf{W}(\alpha)}(\mathbf{x}_{j})\|_{op}\big{|}f_{\mathbf{W}(\alpha)}(\mathbf{x}_{j})-y_{j}\big{|}$
$\displaystyle\geq-
C_{\mathbf{W}(\alpha)}\max_{j\in[n]}\Big{(}\big{|}f_{\mathbf{W}(\alpha)}(\mathbf{x}_{j})-f_{\mathbf{W}_{t}^{(i)}}(\mathbf{x}_{j})\big{|}+\big{|}f_{\mathbf{W}_{t}^{(i)}}(\mathbf{x}_{j})-f_{\mathbf{0}}(\mathbf{x}_{j})\big{|}+\big{|}f_{\mathbf{0}}(\mathbf{x}_{j})-y_{j}\big{|}\Big{)}$
$\displaystyle\geq-
C_{\mathbf{W}(\alpha)}\Big{(}\Big{(}\frac{B_{\sigma^{\prime}}^{2}c_{\mathbf{x}}}{m^{2c-\frac{1}{2}}}\|\mathbf{W}(\alpha)\|_{2}+\frac{B_{\sigma^{\prime}}B_{\sigma}}{m^{2c-1}}\Big{)}\big{(}\|\mathbf{W}(\alpha)-\mathbf{W}_{t}^{(i)}\|_{2}+\|\mathbf{W}_{t}^{(i)}\|_{2}\big{)}+\sqrt{2c_{0}}\Big{)}$
$\displaystyle\geq-C_{\mathbf{W}(\alpha)}\Big{(}B_{3}\big{(}\frac{\sqrt{\eta
T}+\|\mathbf{W}_{0}\|_{2}}{m^{2c-\frac{1}{2}}}+m^{1-2c}\big{)}\big{(}\|\mathbf{W}_{t}-\mathbf{W}_{t}^{(i)}\|_{2}+\eta\|\nabla\ell(\mathbf{W}_{t})-\ell(\mathbf{W}_{t}^{(i)})\|_{2}$
$\displaystyle\quad+\|\mathbf{W}_{t}^{(i)}\|_{2}\big{)}+\sqrt{2c_{0}}\Big{)}$
$\displaystyle\geq-\tilde{\epsilon}_{t},$ (B.18)

where the second inequality is due to (B.1), the third inequality is according
to (B.1) and in the last inequality we used Lemma B.2. Similarly, let
$\widetilde{\mathbf{W}}(\alpha)=\alpha\mathbf{W}_{t}^{(i)}+(1-\alpha)\mathbf{W}_{t}-\alpha\eta\big{(}\nabla
L_{S^{\setminus i}}(\mathbf{W}_{t}^{(i)})-\nabla L_{S^{\setminus
i}}(\mathbf{W}_{t})\big{)}$, we can also control
$\lambda_{\min}\big{(}\nabla^{2}L_{S^{\setminus
i}}(\widetilde{\mathbf{W}}(\alpha))\big{)}$ by $-\tilde{\epsilon}_{t}$.

Let $\Delta=\big{\|}\mathbf{W}_{t}-\mathbf{W}_{t}^{(i)}-\eta\big{(}\nabla
L_{S^{\setminus i}}(\mathbf{W}_{t})-\nabla L_{S^{\setminus
i}}(\mathbf{W}_{t}^{(i)})\big{)}\big{\|}_{2}^{2}$. We define

$g_{1}(\alpha)=G_{1}(\mathbf{W}(\alpha))+\frac{\tilde{\epsilon}_{t}\alpha^{2}}{2}\Delta,\qquad
g_{2}(\alpha)=G_{2}(\widetilde{\mathbf{W}}(\alpha))+\frac{\tilde{\epsilon}_{t}\alpha^{2}}{2}\Delta.$

From (B.1) we know that $g_{1}^{\prime\prime}(\alpha)\geq 0$ for any
$\alpha\in[0,1]$. Hence, $g_{1}$ is convex on $[0,1]$. Then from the convexity
of $g_{1}$ we can get that

$\displaystyle 0=g_{1}^{\prime}(0)$ $\displaystyle\leq g_{1}(1)-g_{1}(0)\leq
G_{1}(\mathbf{W}_{t}-\eta\nabla
G_{1}(\mathbf{W}_{t}))+\frac{\tilde{\epsilon}_{t}}{2}\Delta-
G_{1}(\mathbf{W}_{t}^{(i)}),$

which completes the proof of (B.16). We can also show $g_{2}(\alpha)$ is
convex on $[0,1]$ and prove (B.17) in a similar way. The proof is completed. ∎

Based on Lemma B.1, Lemma B.2 and Lemma B.3 we can establish the following
uniform stability bounds for three-layer neural networks.

######  Theorem B.4 (Uniform Stability).

Suppose Assumptions 1 and 2 hold. Let $S$ and $S^{(i)}$ be constructed in
Definition 2. Let $\\{\mathbf{W}_{t}\\}$ and $\\{\mathbf{W}_{t}^{(i)}\\}$ be
produced by (2) with $\eta\leq 1/(8\hat{\rho})$ based on $S$ and $S^{(i)}$,
respectively. Assume (6) holds. Then, for any $t\in[T]$, there holds

$\displaystyle\big{\|}\mathbf{W}_{t}-\mathbf{W}_{t}^{(i)}\big{\|}_{2}\leq\frac{2e\eta
T\sqrt{2c_{0}\hat{\rho}(\hat{\rho}\eta T+2)}}{n}.$

###### Proof.

Similar to (A.1), by the update rule
$\mathbf{W}_{t+1}=\mathbf{W}_{t}-\eta\nabla L_{S}(\mathbf{W}_{t})$ we know

$\displaystyle\big{\|}\mathbf{W}_{t+1}-\mathbf{W}_{t+1}^{(i)}\big{\|}_{2}^{2}$
$\displaystyle\leq(1+p)\big{\|}\mathbf{W}_{t}-\mathbf{W}_{t}^{(i)}-\eta\big{(}\nabla
L_{S^{\setminus i}}(\mathbf{W}_{t})-\nabla L_{S^{\setminus
i}}(\mathbf{W}_{t}^{(i)})\big{)}\big{\|}_{2}^{2}$
$\displaystyle\quad+\frac{2\eta^{2}(1+1/p)}{n^{2}}\big{(}\big{\|}\nabla\ell(\mathbf{W}_{t};z_{i})\big{\|}_{2}^{2}+\big{\|}\nabla\ell(\mathbf{W}_{t}^{(i)};z_{i}^{\prime})\big{\|}_{2}^{2}\big{)}.$
(B.19)

From Lemma B.3 we know

$\displaystyle\big{\|}\mathbf{W}_{t}-\mathbf{W}_{t}^{(i)}-\eta\big{(}\nabla
L_{S^{\setminus i}}(\mathbf{W}_{t})-\nabla L_{S^{\setminus
i}}(\mathbf{W}_{t}^{(i)})\big{)}\big{\|}_{2}^{2}$
$\displaystyle=\big{\|}\mathbf{W}_{t}-\mathbf{W}_{t}^{(i)}\big{\|}_{2}^{2}+\eta^{2}\big{\|}\nabla
L_{S^{\setminus i}}(\mathbf{W}_{t})-\nabla L_{S^{\setminus
i}}(\mathbf{W}_{t}^{(i)})\big{\|}_{2}^{2}-2\eta\Big{\langle}\mathbf{W}_{t}-\mathbf{W}_{t}^{(i)},\nabla
L_{S^{\setminus i}}(\mathbf{W}_{t})-\nabla L_{S^{\setminus
i}}(\mathbf{W}_{t}^{(i)})\Big{\rangle}$
$\displaystyle\leq\big{\|}\mathbf{W}_{t}-\mathbf{W}_{t}^{(i)}\big{\|}_{2}^{2}+\eta^{2}\big{\|}\nabla
L_{S^{\setminus i}}(\mathbf{W}_{t})-\nabla L_{S^{\setminus
i}}(\mathbf{W}_{t}^{(i)})\big{\|}_{2}^{2}-4\eta^{2}\big{(}1-{4\eta\hat{\rho}}\big{)}\big{\|}\nabla
L_{S^{\setminus i}}(\mathbf{W}_{t})-\nabla L_{S^{\setminus
i}}(\mathbf{W}^{(i)}_{t})\big{\|}_{2}^{2}$
$\displaystyle\quad+2\eta\tilde{\epsilon}_{t}\big{\|}\mathbf{W}_{t}-\mathbf{W}_{t}^{(i)}-\eta\big{(}\nabla
L_{S^{\setminus i}}(\mathbf{W}_{t})-\nabla L_{S^{\setminus
i}}(\mathbf{W}_{t}^{(i)})\big{)}\big{\|}_{2}^{2}.$

Note $4\eta\hat{\rho}\leq 1/2$ implies $1-4(1-{4\eta\hat{\rho}})<0$ and
condition (6) ensures that $2\eta\tilde{\epsilon}_{t}<1$ for any $t\in[T]$.
Then from the above inequality we can get

$\displaystyle(1-2\eta\tilde{\epsilon}_{t})\big{\|}\mathbf{W}_{t}-\mathbf{W}_{t}^{(i)}-\eta\big{(}\nabla
L_{S^{\setminus i}}(\mathbf{W}_{t})-\nabla L_{S^{\setminus
i}}(\mathbf{W}_{t}^{(i)})\big{)}\big{\|}_{2}^{2}\leq\big{\|}\mathbf{W}_{t}-\mathbf{W}_{t}^{(i)}\big{\|}_{2}^{2}.$
(B.20)

Now, plugging (B.20) back into (B.1) we have

$\displaystyle\big{\|}\mathbf{W}_{t+1}\\!-\\!\mathbf{W}_{t+1}^{(i)}\big{\|}_{2}^{2}\\!\leq\\!\frac{1+p}{1\\!-\\!2\eta\tilde{\epsilon}_{t}}\big{\|}\mathbf{W}_{t}\\!-\\!\mathbf{W}_{t}^{(i)}\big{\|}_{2}^{2}\\!+\\!\frac{2\eta^{2}(1\\!+\\!1/p)}{n^{2}}\Big{(}\big{\|}\nabla\ell(\mathbf{W}_{t};z_{i})\big{\|}_{2}^{2}\\!+\\!\big{\|}\nabla\ell(\mathbf{W}_{t}^{(i)};z_{i}^{\prime})\big{\|}_{2}^{2}\Big{)}.$

Applying the above inequality recursively and note that
$\mathbf{W}_{0}=\mathbf{W}_{0}^{(i)}$ we get

$\displaystyle\big{\|}\mathbf{W}_{t+1}-\mathbf{W}_{t+1}^{(i)}\big{\|}_{2}^{2}$
$\displaystyle\leq\frac{2\eta^{2}(1+1/p)}{n^{2}}\sum_{j=0}^{t}\big{(}\big{\|}\nabla\ell(\mathbf{W}_{j};z_{i})\big{\|}_{2}^{2}+\big{\|}\nabla\ell(\mathbf{W}_{j}^{(i)};z_{i}^{\prime})\big{\|}_{2}^{2}\big{)}\prod_{\tilde{j}=j+1}^{t}\frac{1+p}{1-2\eta\tilde{\epsilon}_{\tilde{j}}}$
$\displaystyle\leq\frac{2\eta^{2}(1+1/p)(1+p)^{t}}{n^{2}(1-2\eta\tilde{\epsilon}_{j})^{t}}\sum_{j=0}^{t}\big{(}\big{\|}\nabla\ell(\mathbf{W}_{j};z_{i})\big{\|}_{2}^{2}+\big{\|}\nabla\ell(\mathbf{W}_{j}^{(i)};z_{i}^{\prime})\big{\|}_{2}^{2}\big{)}.$

Let $p=1/t$ and note that $(1+1/t)^{t}\leq e$, we have

$\displaystyle\big{\|}\mathbf{W}_{t+1}-\mathbf{W}_{t+1}^{(i)}\big{\|}_{2}^{2}\leq\frac{2e\eta^{2}(1+t)}{n^{2}}\sum_{j=0}^{t}\big{(}\big{\|}\nabla\ell(\mathbf{W}_{j};z_{i})\big{\|}_{2}^{2}+\big{\|}\nabla\ell(\mathbf{W}_{j}^{(i)};z_{i}^{\prime})\big{\|}_{2}^{2}\big{)}\prod_{\tilde{j}=j+1}^{t}\frac{1}{1-2\eta\tilde{\epsilon}_{\tilde{j}}}.$
(B.21)

According to Lemma B.1 and Lemma A.1, Assumption 2 and noting that
$\|\mathbf{W}_{j}-\mathbf{W}_{0}\|_{2}\leq\sqrt{2c_{0}\eta j}$ for any $j\leq
t$, we know

$\displaystyle\|\nabla\ell(\mathbf{W}_{j};z)\|_{2}^{2}$ $\displaystyle\leq
2\|\nabla\ell(\mathbf{W}_{j};z)-\nabla\ell(\mathbf{W}_{0};z)\|_{2}^{2}+2\|\nabla\ell(\mathbf{W}_{0};z)\|_{2}^{2}$
$\displaystyle\leq
2\hat{\rho}^{2}\|\mathbf{W}_{j}-\mathbf{W}_{0}\|_{2}^{2}+4\hat{\rho}\ell(\mathbf{W}_{0};z)\leq
4c_{0}\hat{\rho}(\hat{\rho}\eta j+1).$

Similarly, we have

$\displaystyle\|\nabla\ell(\mathbf{W}_{j}^{(i)};z)\|_{2}^{2}\leq
4c_{0}\hat{\rho}(\hat{\rho}\eta j+1).$

Combining the above three inequalities together, we get

$\displaystyle\big{\|}\mathbf{W}_{t+1}-\mathbf{W}_{t+1}^{(i)}\big{\|}_{2}^{2}\leq\frac{8c_{0}e\eta^{2}(1+t)^{2}\hat{\rho}\big{(}\hat{\rho}\eta
t+2)\big{)}}{n^{2}}\prod_{\tilde{j}=j+1}^{t}\frac{1}{1-2\eta\tilde{\epsilon}_{\tilde{j}}}.$

Similar to the proof of Theorem A.5, we can derive the following stability
result by induction

$\displaystyle\big{\|}\mathbf{W}_{t+1}-\mathbf{W}_{t+1}^{(i)}\big{\|}_{2}\leq\frac{2e\eta
T\sqrt{2c_{0}\hat{\rho}(\hat{\rho}\eta T+2)}}{n}.$

Here, the condition
$\frac{1}{(1-2\eta\tilde{\epsilon}_{j})^{t}}\leq\Big{(}\frac{1}{1-1/(t+1)}\Big{)}^{t}\leq
e$ is ensured by condition (6), i.e.,

$\displaystyle m\\!\gtrsim$ $\displaystyle\big{(}(\eta
T\mathcal{B}_{T})^{2}+\frac{(\eta
T)^{\frac{7}{2}}\mathcal{B}_{T}}{n}\big{)}^{\frac{1}{5c-\frac{1}{2}}}+\big{(}(\eta
T)^{\frac{3}{2}}\mathcal{B}_{T}^{2}\\!+\\!\frac{(\eta
T)^{3}\mathcal{B}_{T}}{n}\big{)}^{\frac{1}{4c-1}}\\!\\!+\\!\big{(}(\eta
T)^{2}\mathcal{B}_{T}\\!+\\!\frac{(\eta
T)^{\frac{7}{2}}}{n}\big{)}^{\frac{1}{5c-1}}$
$\displaystyle\\!+\\!\big{(}(\eta
T)^{\frac{3}{2}}\mathcal{B}_{T}\\!+\\!\frac{(\eta
T)^{3}}{n}\big{)}^{\frac{1}{4c-\frac{3}{2}}}$

with $\mathcal{B}_{T}=\sqrt{\eta T}+\|\mathbf{W}_{0}\|_{2}$. The proof is the
same as Theorem A.5, we omit it for simplicity. ∎

We can combine Theorem B.4 and Lemma 1 together to get the upper bound of the
generalization error.

###### Proof of Theorem 6.

The proof is similar to that of Theorem 2. From (B.21) we know that

$\displaystyle\big{\|}\mathbf{W}_{t+1}-\mathbf{W}_{t+1}^{(i)}\big{\|}_{2}^{2}\leq\frac{4e^{2}\eta^{2}\hat{\rho}(1+t)}{n^{2}}\sum_{j=0}^{t}\Big{(}\ell(\mathbf{W}_{j};z_{i})+\ell(\mathbf{W}_{j}^{(i)};z_{i}^{\prime})\Big{)},$

where we used the self-bounding property of the smooth loss (Lemma A.1).

Then, taking an average over $i\in[n]$ and noting that
$\mathbb{E}\big{[}\ell(\mathbf{W}_{j};z_{i})\big{]}=\mathbb{E}\big{[}\ell(\mathbf{W}_{j}^{(i)};z_{i}^{\prime})\big{]}$,
we have

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}\big{\|}\mathbf{W}_{t+1}-\mathbf{W}_{t+1}^{(i)}\big{\|}_{2}^{2}$
$\displaystyle\leq\frac{8e^{2}\eta^{2}\hat{\rho}(1+t)}{n^{2}}\sum_{j=0}^{t}\mathbb{E}\big{[}L_{S}(\mathbf{W}_{j})\big{]},$

Combining the above stability bounds with Lemma 1 together and noting that
$L_{S}(\mathbf{W}_{t})\leq\frac{1}{t}\sum_{j=1}^{t-1}L_{S}(\mathbf{W}_{j})$
[34], the desired result is obtained. ∎

###  B.2 Proofs of Optimization Bounds

To show optimization error bounds, we first introduce the following lemma on
the bound of GD iterates.

######  Lemma B.5.

Suppose Assumptions 1 and 2 hold, and $\eta\leq 1/(8\hat{\rho})$. Assume (6)
and (7) hold. Then for any $t\in[T]$, there holds

$\displaystyle 1\vee\mathbb{E}[\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{t}\|_{2}^{2}]\leq\Big{(}\frac{16e^{2}\eta^{3}t^{2}\hat{\rho}^{2}}{n^{2}}\\!+\\!\frac{16e\eta^{2}t\hat{\rho}}{n}\Big{)}\sum_{s=0}^{t-1}\mathbb{E}\big{[}L_{S}(\mathbf{W}_{s})\big{]}\\!+\\!2\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}\\!\\!-\\!\mathbf{W}_{0}\|_{2}^{2}\\!+\\!2\eta
T\big{[}L(\mathbf{W}_{\frac{1}{\eta T}}^{*})-L(\mathbf{W}^{*})\big{]}.$

###### Proof.

For any $\mathbf{W}\in\mathbb{R}^{md}$ and $\alpha\in[0,1]$, define
$\mathbf{W}(\alpha):=\mathbf{W}_{t}+\alpha(\mathbf{W}-\mathbf{W}_{t})$.
Similar to (B.1), according to Lemma B.1 we can show that

$\displaystyle\lambda_{\min}\big{(}\nabla^{2}L_{S}(\mathbf{W}(\alpha))\big{)}\\!\geq\\!-C_{\mathbf{W}(\alpha)}\Big{(}\big{(}\frac{B_{\sigma^{\prime}}^{2}c_{\mathbf{x}}}{m^{2c-1/2}}\|\mathbf{W}(\alpha)\|_{2}\\!+\\!\frac{B_{\sigma^{\prime}}B_{\sigma}}{m^{2c-1}}\big{)}\big{(}\|\mathbf{W}\\!-\\!{\mathbf{W}}_{t}\|_{2}\\!+\\!\|{\mathbf{W}}_{t}\|_{2}\big{)}\\!+\\!\sqrt{2c_{0}}\Big{)},$

where
$C_{\mathbf{W}(\alpha)}=\frac{B^{2}_{\sigma^{\prime}}B_{\sigma^{\prime\prime}}c_{\mathbf{x}}^{2}}{m^{3c}}\big{\|}\mathbf{W}(\alpha)^{(2)}\big{\|}_{2}^{2}+\Big{(}\frac{B_{\sigma^{\prime}}B_{\sigma^{\prime\prime}}c_{\mathbf{x}}^{2}}{m^{2c-\frac{1}{2}}}+\frac{2B_{\sigma^{\prime\prime}}B_{\sigma^{\prime}}B_{\sigma}c_{\mathbf{x}}}{m^{3c-\frac{1}{2}}}\Big{)}\|\mathbf{W}(\alpha)^{(2)}\|_{2}+\frac{B_{\sigma^{\prime\prime}}B_{\sigma}^{2}}{m^{3c-1}}+\frac{2B_{\sigma^{\prime}}^{2}c_{\mathbf{x}}}{m^{2c-\frac{1}{2}}}$.
Let
$\hat{C}_{\mathbf{W}}=4B_{1}\big{(}m^{-3c}(\|\mathbf{W}\|_{2}^{2}+4c_{0}\eta
T+2\|\mathbf{W}_{0}\|_{2}^{2})+m^{\frac{1}{2}-2c}(\|\mathbf{W}\|_{2}+\sqrt{2c_{0}\eta
T}+\|\mathbf{W}_{0}\|_{2})\big{)}$. According to Lemma B.2, we can verify that
$C_{\mathbf{W}(\alpha)}\leq\hat{C}_{\mathbf{W}}$ for any $\alpha\in[0,1]$.

Now, let

$\displaystyle g(\alpha)\\!:=$ $\displaystyle
L_{S}(\mathbf{W}(\alpha))\\!+\\!\frac{\alpha^{2}\hat{C}_{\mathbf{W}}}{2}\Big{(}\\!\big{(}\frac{B_{\sigma^{\prime}}^{2}c_{\mathbf{x}}}{m^{2c-1/2}}\|\mathbf{W}(\alpha)\|_{2}+\frac{B_{\sigma^{\prime}}B_{\sigma}}{m^{2c-1}}\big{)}\big{(}\|\mathbf{W}\\!-\\!\mathbf{W}_{t}\|_{2}\\!+\\!\|\mathbf{W}_{t}\|_{2}\big{)}\\!+\\!\sqrt{2c_{0}}\Big{)}$
$\displaystyle\quad\times(1\vee\mathbb{E}[\|\mathbf{W}-\mathbf{W}_{t}\|_{2}^{2}]).$

It is obvious that $g(\alpha)$ is convex in $\alpha\in[0,1]$. Similar to the
proof of Lemma A.6, by convexity of $g$ and smoothness of the loss we can show
that

$\displaystyle\frac{1}{t}\sum_{s=0}^{t-1}\mathbb{E}[L_{S}(\mathbf{W}_{s})]+\frac{\mathbb{E}\big{[}\|\mathbf{W}_{t}-\mathbf{W}\|_{2}^{2}\big{]}}{2\eta
t}$
$\displaystyle\leq\mathbb{E}[L_{S}(\mathbf{W})]+\frac{\mathbb{E}\big{[}\|\mathbf{W}\\!-\\!\mathbf{W}_{0}\|_{2}^{2}\big{]}}{2\eta
t}+\frac{\hat{C}_{\mathbf{W}}}{2t}\sum_{s=0}^{t-1}\Big{(}\big{(}\frac{B_{\sigma^{\prime}}^{2}c_{\mathbf{x}}}{m^{2c-1/2}}\|\mathbf{W}(\alpha)\|_{2}+\frac{B_{\sigma^{\prime}}B_{\sigma}}{m^{2c-1}}\big{)}\big{(}\mathbb{E}[\|\mathbf{W}\\!-\\!{\mathbf{W}}_{s}\|_{2}]$
$\displaystyle\quad+\sqrt{2c_{0}\eta
T}+\|\mathbf{W}_{0}\|_{2}\big{)}+\sqrt{2c_{0}}\Big{)}(1\vee\mathbb{E}[\|\mathbf{W}-\mathbf{W}_{s}\|_{2}^{2}]).$
(B.22)

Combining the above inequality with Theorem 6 and let
$\mathbf{W}=\mathbf{W}^{*}_{\frac{1}{\eta T}}$, we have

$\displaystyle\frac{\mathbb{E}\big{[}\|\mathbf{W}_{t}-\mathbf{W}_{\frac{1}{\eta
T}}^{*}\|_{2}^{2}\big{]}}{2\eta t}$
$\displaystyle\\!\\!\leq\frac{1}{t}\sum_{s=1}^{t-1}\big{[}L(\mathbf{W}_{\frac{1}{\eta
T}}^{*})-\mathbb{E}[L(\mathbf{W}_{s})]\big{]}+\frac{\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}\\!-\\!\mathbf{W}_{0}\|_{2}^{2}}{2\eta
t}\\!+\\!\Big{(}\frac{4e^{2}\eta^{2}t\hat{\rho}^{2}}{n^{2}}\\!+\\!\frac{4e\eta\hat{\rho}}{n}\Big{)}\sum_{s=0}^{t-1}\mathbb{E}\big{[}L_{S}(\mathbf{W}_{s})\big{]}$
$\displaystyle\\!\\!+\\!\frac{1}{2t}\\!\sum_{s=0}^{t-1}\\!\hat{C}_{\mathbf{W}_{\frac{1}{\eta
T}}^{*}}\\!\\!\Big{(}\big{(}\frac{B_{\sigma^{\prime}}^{2}c_{\mathbf{x}}}{m^{2c-1/2}}\|\mathbf{W}(\alpha)\|_{2}\\!+\\!\frac{B_{\sigma^{\prime}}B_{\sigma}}{m^{2c\\!-\\!1}}\big{)}\big{(}\mathbb{E}[\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}\\!\\!-\\!{\mathbf{W}}_{s}\|_{2}]\\!+\\!\sqrt{2c_{0}\eta
T}\\!+\\!\|\mathbf{W}_{0}\|_{2}\big{)}\\!+\\!\sqrt{2c_{0}}\Big{)}(1\vee\mathbb{E}[\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{s}\|_{2}^{2}])$ $\displaystyle\\!\leq
L(\mathbf{W}_{\frac{1}{\eta
T}}^{*})-L(\mathbf{W}^{*})+\frac{\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{0}\|_{2}^{2}}{2\eta
t}+\Big{(}\frac{4e^{2}\eta^{2}t\hat{\rho}^{2}}{n^{2}}+\frac{4e\eta\hat{\rho}}{n}\Big{)}\sum_{s=0}^{t-1}\mathbb{E}\big{[}L_{S}(\mathbf{W}_{s})\big{]}$
$\displaystyle+\\!\frac{1}{2t}\\!\sum_{s=0}^{t-1}\\!\hat{C}_{\mathbf{W}_{\frac{1}{\eta
T}}^{*}}\\!\Big{(}\\!\big{(}\frac{B_{\sigma^{\prime}}^{2}c_{\mathbf{x}}}{m^{2c-1/2}}\|\mathbf{W}(\alpha)\|_{2}\\!+\\!\frac{B_{\sigma^{\prime}}B_{\sigma}}{m^{2c-1}}\big{)}\big{(}\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}\\!\\!-\\!{\mathbf{W}}_{s}\|_{2}\\!+\\!\sqrt{2c_{0}\eta
T}\\!+\\!\|\mathbf{W}_{0}\|_{2}\big{)}\\!+\\!\sqrt{2c_{0}}\Big{)}(1\vee\mathbb{E}[\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{s}\|_{2}^{2}]),$ (B.23)

where in the second inequality we used $L(\mathbf{W}_{\frac{1}{\eta
T}}^{*})-L(\mathbf{W}_{s})\leq L(\mathbf{W}_{\frac{1}{\eta
T}}^{*})-L(\mathbf{W}^{*})$ since $L(\mathbf{W}_{s})\geq L(\mathbf{W}^{*})$
for any $s\in[t-1]$.

According to Lemma B.2 we can get

$\displaystyle\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{s}\|_{2}\leq\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{0}\|_{2}+\|\mathbf{W}_{s}-\mathbf{W}_{0}\|_{2}\leq\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{0}\|_{2}+\sqrt{2c_{0}\eta T}.$ (B.24)

Then there holds

$\displaystyle\big{(}\frac{B_{\sigma^{\prime}}^{2}c_{\mathbf{x}}}{m^{2c-1/2}}\|\mathbf{W}(\alpha)\|_{2}\\!+\\!\frac{B_{\sigma^{\prime}}B_{\sigma}}{m^{2c-1}}\big{)}\big{(}\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}\\!-\\!{\mathbf{W}}_{s}\|_{2}+\sqrt{2c_{0}\eta
T}+\|\mathbf{W}_{0}\|_{2}\big{)}+\sqrt{2c_{0}}$
$\displaystyle\leq\Big{(}\frac{B_{\sigma^{\prime}}^{2}c_{\mathbf{x}}}{m^{2c-1/2}}(2\sqrt{2c_{0}\eta
T}+2\|\mathbf{W}_{0}\|_{2}+\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{0}\|_{2})+\frac{B_{\sigma^{\prime}}B_{\sigma}}{m^{2c-1}}\Big{)}(2\sqrt{2c_{0}\eta
T}+\|\mathbf{W}_{0}\|_{2}+\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{0}\|_{2})+\sqrt{2c_{0}}.$ (B.25)

Plugging the above inequality back into (B.2) and multiplying both sides by
$2\eta t$ yields

$\displaystyle\mathbb{E}\big{[}\|\mathbf{W}_{t}-\mathbf{W}_{\frac{1}{\eta
T}}^{*}\|_{2}^{2}\big{]}$ $\displaystyle\leq\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}\\!\\!-\\!\mathbf{W}_{0}\|_{2}^{2}\\!+\\!\eta\hat{C}_{\mathbf{W}_{\frac{1}{\eta
T}}^{*}}\\!\Big{(}\Big{(}\frac{B_{\sigma^{\prime}}^{2}c_{\mathbf{x}}}{m^{2c-1/2}}(2\sqrt{2c_{0}\eta
T}+\|\mathbf{W}_{0}\|_{2}\\!+\\!\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}\\!\\!-\\!\mathbf{W}_{0}\|_{2})\\!+\\!\frac{B_{\sigma^{\prime}}B_{\sigma}}{m^{2c-1}}\Big{)}$
$\displaystyle\quad\times(2\sqrt{2\eta
Tc_{0}}+\|\mathbf{W}_{0}\|_{2}+\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{0}\|_{2})+\sqrt{2c_{0}}\Big{)}\sum_{s=0}^{t-1}(1\vee\mathbb{E}[\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{s}\|_{2}^{2}])$
$\displaystyle\quad+\Big{(}\frac{8e^{2}\eta^{3}t^{2}\hat{\rho}^{2}}{n^{2}}+\frac{8e\eta^{2}t\hat{\rho}}{n}\Big{)}\sum_{s=0}^{t-1}\mathbb{E}\big{[}L_{S}(\mathbf{W}_{s})\big{]}+2\eta
T\big{[}L(\mathbf{W}_{\frac{1}{\eta T}}^{*})\\!-L(\mathbf{W}^{*})\big{]}.$

Let $x=\max_{s\in[T]}\mathbb{E}[\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{s}\|_{2}^{2}]\vee 1$. Then the above inequality implies

$\displaystyle x$ $\displaystyle\leq\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}\\!\\!-\\!\mathbf{W}_{0}\|_{2}^{2}\\!+\\!\eta
T\hat{C}_{\mathbf{W}_{\frac{1}{\eta
T}}^{*}}\\!\\!\Big{(}\Big{(}\frac{B_{\sigma^{\prime}}^{2}c_{\mathbf{x}}}{m^{2c\\!-\\!1/2}}(2\sqrt{2c_{0}\eta
T}+\|\mathbf{W}_{0}\|_{2}\\!+\\!\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}\\!\\!-\mathbf{W}_{0}\|_{2})\\!+\\!\frac{B_{\sigma^{\prime}}B_{\sigma}}{m^{2c-1}}\Big{)}$
$\displaystyle\times(2\sqrt{2\eta
Tc_{0}}\\!+\\!\|\mathbf{W}_{0}\|_{2}\\!+\\!\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}\\!\\!-\mathbf{W}_{0}\|_{2})\\!+\\!\sqrt{2c_{0}}\Big{)}x\\!+\\!\Big{(}\frac{8e^{2}\eta^{3}t^{2}\hat{\rho}^{2}}{n^{2}}\\!+\\!\frac{8e\eta^{2}t\hat{\rho}}{n}\Big{)}\sum_{s=0}^{t-1}\mathbb{E}\big{[}L_{S}(\mathbf{W}_{s})\big{]}$
$\displaystyle+2\eta T\big{[}L(\mathbf{W}_{\frac{1}{\eta
T}}^{*})-L(\mathbf{W}^{*})\big{]}.$

Note that condition (7) implies that $\eta T\hat{C}_{\mathbf{W}_{\frac{1}{\eta
T}}^{*}}\big{(}(\frac{B_{\sigma^{\prime}}^{2}c_{\mathbf{x}}}{m^{2c-1/2}}(2\sqrt{2c_{0}\eta
T}+\|\mathbf{W}_{0}\|_{2}+\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{0}\|_{2})+\frac{B_{\sigma^{\prime}}B_{\sigma}}{m^{2c-1}})(2\sqrt{2\eta
Tc_{0}}+\|\mathbf{W}_{0}\|_{2}+\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{0}\|_{2})+\sqrt{2c_{0}}\big{)}\leq\frac{1}{2}$, then there
holds

$x\leq\Big{(}\frac{16e^{2}\eta^{3}t^{2}\hat{\rho}^{2}}{n^{2}}+\frac{16e\eta^{2}t\hat{\rho}}{n}\Big{)}\sum_{s=0}^{t-1}\mathbb{E}\big{[}L_{S}(\mathbf{W}_{s})\big{]}+2\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}\\!\\!-\\!\mathbf{W}_{0}\|_{2}^{2}+2\eta
T\big{[}L(\mathbf{W}_{\frac{1}{\eta T}}^{*})-L(\mathbf{W}^{*})\big{]}.$

It then follows that

$\displaystyle 1\vee\mathbb{E}[\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}\\!-\\!\mathbf{W}_{t}\|_{2}^{2}]\leq\Big{(}\frac{16e^{2}\eta^{3}t^{2}\hat{\rho}^{2}}{n^{2}}\\!+\\!\frac{16e\eta^{2}t\hat{\rho}}{n}\Big{)}\sum_{s=0}^{t-1}\mathbb{E}\big{[}L_{S}(\mathbf{W}_{s})\big{]}\\!+\\!2\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}\\!\\!-\\!\mathbf{W}_{0}\|_{2}^{2}\\!+\\!2\eta
T\big{[}L(\mathbf{W}_{\frac{1}{\eta T}}^{*})\\!-\\!L(\mathbf{W}^{*})\big{]}.$

This completes the proof. ∎

###### Proof of Theorem 7.

Combining (B.2) and (B.2) with $\mathbf{W}=\mathbf{W}^{*}_{\frac{1}{\eta T}}$
together yields

$\displaystyle\frac{1}{T}\sum_{s=0}^{T-1}\mathbb{E}[L_{S}(\mathbf{W}_{s})]$
$\displaystyle\\!\leq\\!\mathbb{E}[L_{S}(\mathbf{W}^{*}_{\frac{1}{\eta
T}})]\\!+\\!\frac{\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}\\!\\!-\\!\mathbf{W}_{0}\|_{2}^{2}}{2\eta
T}\\!+\\!\frac{\hat{C}_{\mathbf{W}^{*}_{\frac{1}{\eta
T}}}}{2T}\\!\\!\sum_{s=0}^{T-1}\\!\Big{(}\\!\big{(}\frac{B_{\sigma^{\prime}}^{2}c_{\mathbf{x}}}{m^{2c-1/2}}(2\sqrt{2c_{0}\eta
T}\\!+\\!\|\mathbf{W}_{0}\|_{2}\\!+\\!\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}\\!\\!-\\!\mathbf{W}_{0}\|_{2})$
$\displaystyle\quad+\frac{B_{\sigma^{\prime}}B_{\sigma}}{m^{2c-1}}\big{)}\big{(}\mathbb{E}[\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}-{\mathbf{W}}_{s}\|_{2}]+2\sqrt{2c_{0}\eta
T}+\|\mathbf{W}_{0}\|_{2}\big{)}+\sqrt{2c_{0}}\Big{)}(1\vee\mathbb{E}[\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}-\mathbf{W}_{s}\|_{2}^{2}])$
$\displaystyle\leq\mathbb{E}[L_{S}(\mathbf{W}^{*}_{\frac{1}{\eta
T}})]+\frac{1}{2T}\hat{C}_{\mathbf{W}^{*}_{\frac{1}{\eta
T}}}\hat{B}_{\mathbf{W}^{*}_{\frac{1}{\eta
T}}}\sum_{s=0}^{T-1}1\vee\mathbb{E}[\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}-\mathbf{W}_{s}\|_{2}^{2}]+\frac{\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}-\mathbf{W}_{0}\|_{2}^{2}}{2\eta T},$ (B.26)

where $\hat{B}_{\mathbf{W}^{*}_{\frac{1}{\eta
T}}}=\big{(}\frac{B_{\sigma^{\prime}}^{2}c_{\mathbf{x}}}{m^{2c-1/2}}(2\sqrt{2c_{0}\eta
T}+\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{0}\|_{2})+\frac{B_{\sigma^{\prime}}B_{\sigma}}{m^{2c-1}}\big{)}(2\sqrt{2\eta
Tc_{0}}+\|\mathbf{W}_{0}\|_{2}+\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{0}\|_{2})+\sqrt{2c_{0}}$ and in the last inequality we
used (B.24).

By monotonically decreasing of $\\{L_{S}(\mathbf{W}_{t})\\}$ and Lemma B.5, we
further know

$\displaystyle\mathbb{E}[L_{S}(\mathbf{W}_{T})]$
$\displaystyle\leq\mathbb{E}[L_{S}(\mathbf{W}^{*}_{\frac{1}{\eta
T}})]+\frac{\hat{C}_{\mathbf{W}^{*}_{\frac{1}{\eta
T}}}\hat{B}_{\mathbf{W}^{*}_{\frac{1}{\eta
T}}}}{2T}\sum_{s=0}^{T-1}1\vee\mathbb{E}[\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}\\!\\!-\\!\mathbf{W}_{s}\|_{2}^{2}]+\frac{\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}\\!\\!-\\!\mathbf{W}_{0}\|_{2}^{2}}{2\eta T}$
$\displaystyle\leq\mathbb{E}[L_{S}(\mathbf{W}^{*}_{\frac{1}{\eta
T}})]+\hat{C}_{\mathbf{W}^{*}_{\frac{1}{\eta
T}}}\hat{B}_{\mathbf{W}^{*}_{\frac{1}{\eta
T}}}\Big{(}\Big{(}\frac{8e^{2}\eta^{3}T^{2}\hat{\rho}^{2}}{n^{2}}\\!+\\!\frac{8e\eta^{2}T\hat{\rho}}{n}\\!\Big{)}\\!\sum_{s=0}^{T-1}\\!\mathbb{E}\big{[}L_{S}(\mathbf{W}_{s})\big{]}$
$\displaystyle\quad+\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}\\!-\\!\mathbf{W}_{0}\|_{2}^{2}+\eta
T\big{[}L(\mathbf{W}_{\frac{1}{\eta
T}}^{*})-L(\mathbf{W}^{*})\big{]}\Big{)}+\frac{\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}-\mathbf{W}_{0}\|_{2}^{2}}{2\eta T},$

which completes the proof. ∎

######  Lemma B.6.

Suppose Assumptions 1 and 2 hold. Let $\\{\mathbf{W}_{t}\\}$ be produced by
(2) with $\eta\leq 1/(8\hat{\rho})$. Assume (6) and (7) hold. Then

$\displaystyle\sum_{s=0}^{T-1}\mathbb{E}[L_{S}(\mathbf{W}_{s})]\leq
2TL(\mathbf{W}^{*}_{\frac{1}{\eta T}})-\eta
TL(\mathbf{W}^{*})+\big{(}1+\frac{1}{2\eta}\big{)}\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}-\mathbf{W}_{0}\|_{2}^{2}.$

###### Proof.

Multiplying $T$ over both sides of (B.2) and using Lemma B.5 we get

$\displaystyle\sum_{s=0}^{T-1}\mathbb{E}[L_{S}(\mathbf{W}_{s})]$
$\displaystyle\leq TL(\mathbf{W}^{*}_{\frac{1}{\eta
T}})\\!+\\!\hat{C}_{\mathbf{W}^{*}_{\frac{1}{\eta
T}}}\\!\\!\hat{B}_{\mathbf{W}^{*}_{\frac{1}{\eta
T}}}\\!\\!\Big{(}\Big{(}\frac{8e^{2}\eta^{3}T^{2}\hat{\rho}^{2}}{n^{2}}\\!+\\!\frac{8e\eta^{2}T\hat{\rho}}{n}\\!\Big{)}\\!\sum_{s=0}^{T-1}\\!\mathbb{E}\big{[}L_{S}(\mathbf{W}_{s})\big{]}$
$\displaystyle+\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{0}\|_{2}^{2}+\eta T\big{[}L(\mathbf{W}_{\frac{1}{\eta
T}}^{*})-L(\mathbf{W}^{*})\big{]}\Big{)}+\frac{\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}-\mathbf{W}_{0}\|_{2}^{2}}{2\eta}.$ (B.27)

Condition (7) with $\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{0}\|_{2}\leq\|\mathbf{W}^{*}-\mathbf{W}_{0}\|_{2}$ implies
$\hat{C}_{\mathbf{W}^{*}_{\frac{1}{\eta
T}}}\hat{B}_{\mathbf{W}^{*}_{\frac{1}{\eta
T}}}\big{(}\frac{4e^{2}\eta^{3}T^{2}\hat{\rho}^{2}}{n^{2}}\\!+\\!\frac{4e\eta^{2}T\hat{\rho}}{n}\\!\big{)}\\!\leq
1/2$ and $\hat{C}_{\mathbf{W}^{*}_{\frac{1}{\eta
T}}}\hat{B}_{\mathbf{W}^{*}_{\frac{1}{\eta T}}}\leq 1$, then there holds

$\displaystyle\sum_{s=0}^{T-1}\mathbb{E}[L_{S}(\mathbf{W}_{s})]\leq
2TL(\mathbf{W}^{*}_{\frac{1}{\eta T}})-\eta
TL(\mathbf{W}^{*})+\big{(}1+\frac{1}{2\eta}\big{)}\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}-\mathbf{W}_{0}\|_{2}^{2},$

which completes the proof. ∎

###  B.3 Proofs of Excess Population Bounds

###### Proof of Theorem 8.

Note $\hat{\rho}=\mathcal{O}(1)$. According to Theorem 6 and Lemma B.6 we know

$\displaystyle\mathbb{E}[L(\mathbf{W}_{T})-L_{S}(\mathbf{W}_{T})]=\mathcal{O}\Big{(}\big{(}\frac{\eta^{2}T^{2}}{n^{2}}+\frac{\eta
T}{n}\big{)}\big{(}L(\mathbf{W}^{*}_{\frac{1}{\eta T}})+\frac{1}{\eta
T}\|\mathbf{W}^{*}_{\frac{1}{\eta T}}-\mathbf{W}_{0}\|_{2}^{2}\Big{)}.$ (B.28)

The estimation of the optimization error is given by combining Lemma B.6 and
Theorem 7 together

$\displaystyle\mathbb{E}[L_{S}(\mathbf{W}_{T})-L_{S}(\mathbf{W}^{*}_{\frac{1}{\eta
T}})-\frac{1}{2\eta T}\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}-\mathbf{W}_{0}\|_{2}^{2}]$
$\displaystyle=\mathcal{O}\Big{(}\big{(}\frac{\eta^{2}T^{2}}{n^{2}}\\!+\\!\frac{\eta
T}{n}\big{)}\big{(}L(\mathbf{W}^{*}_{\frac{1}{\eta T}})\\!+\\!\frac{1}{2\eta
T}\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}\\!\\!-\\!\mathbf{W}_{0}\|_{2}^{2}\big{)}\\!+\\!\frac{1}{\eta
T}\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}\\!\\!-\\!\mathbf{W}_{0}\|_{2}^{2}+\Lambda_{\frac{1}{\eta
T}}\big{)}\Big{)},$

where we used the fact that $\hat{C}_{\mathbf{W}^{*}_{\frac{1}{\eta
T}}}\hat{B}_{\mathbf{W}^{*}_{\frac{1}{\eta T}}}\leq 1/\eta T$ implied by
condition (7) and $L(\mathbf{W}^{*}_{\frac{1}{\eta
T}})-L(\mathbf{W}^{*})\leq\Lambda_{\frac{1}{\eta T}}.$

Combining the above two inequalities together we get

$\displaystyle\mathbb{E}[L(\mathbf{W}_{T})-L(\mathbf{W}^{*})]$
$\displaystyle=\Big{[}\mathbb{E}[L(\mathbf{W}_{T})-L_{S}(\mathbf{W}_{T})\Big{]}+\mathbb{E}\Big{[}L_{S}(\mathbf{W}_{T})-\big{(}L_{S}(\mathbf{W}^{*}_{\frac{1}{\eta
T}})+\frac{1}{2\eta T}\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}-\mathbf{W}_{0}\|_{2}^{2}\big{)}\Big{]}$
$\displaystyle\quad+\Big{[}L(\mathbf{W}^{*}_{\frac{1}{\eta T}})+\frac{1}{2\eta
T}\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}-\mathbf{W}_{0}\|_{2}^{2}-L(\mathbf{W}^{*})\Big{]}$
$\displaystyle=\mathcal{O}\Big{(}\frac{\eta T}{n}\Big{(}\frac{\eta
T}{n}\\!+\\!1\Big{)}\Big{[}L(\mathbf{W}^{*}_{\frac{1}{\eta
T}})\\!+\\!\frac{1}{2\eta T}\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}\\!\\!-\\!\mathbf{W}_{0}\|_{2}^{2}\Big{]}\\!+\\!\frac{1}{\eta
T}\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}\\!\\!-\\!\mathbf{W}_{0}\|_{2}^{2}+\Lambda_{\frac{1}{\eta T}}\Big{)}.$

Since $n\gtrsim\eta T$, we further have

$\displaystyle\mathbb{E}[L(\mathbf{W}_{T})\\!-\\!L(\mathbf{W}^{*})]=\mathcal{O}\Big{(}\frac{\eta
T}{n}\Big{[}L(\mathbf{W}^{*}_{\frac{1}{\eta T}})\\!+\\!\frac{1}{2\eta
T}\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}\\!\\!-\\!\mathbf{W}_{0}\|_{2}^{2}\Big{]}\\!+\\!\frac{1}{\eta
T}\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}\\!\\!-\\!\mathbf{W}_{0}\|_{2}^{2}+\Lambda_{\frac{1}{\eta T}}\Big{)}.$

Finally, note that $L(\mathbf{W}^{*}_{\frac{1}{\eta T}})+\frac{1}{2\eta
T}\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}-\mathbf{W}_{0}\|_{2}^{2}=L(\mathbf{W}^{*})+\Lambda_{\frac{1}{\eta T}}$ and
$\|\mathbf{W}^{*}_{\frac{1}{\eta T}}-\mathbf{W}_{0}\|_{2}^{2}\leq\eta
T\Lambda_{\frac{1}{\eta T}}$, we have

$\displaystyle\mathbb{E}[L(\mathbf{W}_{T})-L(\mathbf{W}^{*})]=\mathcal{O}\Big{(}\frac{\eta
T}{n}L(\mathbf{W}^{*})+\Lambda_{\frac{1}{\eta T}}\Big{)}.$

The proof is completed. ∎

###### Proof of Corollary 9.

Part (a). From the definition of the approximation error
$\Lambda_{\frac{1}{\eta T}}$ and Theorem 8 we can get

$\displaystyle\mathbb{E}[L(\mathbf{W}_{T})-L(\mathbf{W}^{*})]=\mathcal{O}\Big{(}\frac{\eta
T}{n}L(\mathbf{W}^{*})+\frac{1}{\eta
T}\|\mathbf{W}^{*}-\mathbf{W}_{0}\|_{2}^{2}\Big{)}.$

For the case $c\in[9/16,1]$, to ensure conditions (6) and (7) hold, we choose
$m\asymp(\eta T)^{4}$ for this case. Then according to Theorem 8 and
Assumption 3, there holds

$\displaystyle\mathbb{E}[L(\mathbf{W}_{T})-L(\mathbf{W}^{*})]=\mathcal{O}\Big{(}\frac{\eta
T}{n}+(\eta T)^{3-8\mu}\Big{)}.$

Here, the condition $\mu\geq 1/2$ ensures that $3-8\mu<0$. Hence, the bound
will vanish as $\eta T$ tends to $0$. Further, if
$n^{\frac{1}{2(8\mu-3)}}\lesssim\eta T\lesssim\sqrt{n}$ (the existence of
$\eta T$ is ensured by $\mu\geq 1/2$), then there holds $\eta
T/n=\mathcal{O}(n^{-1/2})$ and $(\eta T)^{3-8\mu}=\mathcal{O}(n^{-1/2})$. That
is

$\displaystyle\mathbb{E}[L(\mathbf{W}_{T})-L(\mathbf{W}^{*})]=\mathcal{O}\big{(}\frac{1}{\sqrt{n}}\big{)}.$

For the case $c\in(1/2,9/16)$, we choose $m\asymp(\eta T)^{\frac{1}{4c-2}}$,
and $n^{\frac{2c-1}{2\mu+4c-3}}\lesssim\eta T\lesssim\sqrt{n}$. From Theorem 8
and Assumption 3 we have

$\displaystyle\mathbb{E}[L(\mathbf{W}_{T})-L(\mathbf{W}^{*})]=\mathcal{O}\big{(}\frac{1}{\sqrt{n}}\big{)}.$

The first part of the theorem is proved.

Part (b). For the case $c\in[9/16,1]$, by choosing $m\asymp(\eta T)^{4}$ and
$\eta T\gtrsim n^{\frac{1}{8\mu-3}}$, from Theorem 8 and Assumption 3 we have

$\displaystyle\mathbb{E}[L(\mathbf{W}_{T})-L(\mathbf{W}^{*})]=\mathcal{O}\big{(}\frac{1}{{n}}\big{)}.$

For the case $c\in(1/2,9/16)$, by choosing $m\asymp(\eta T)^{\frac{1}{4c-2}}$
and $\eta T\gtrsim n^{\frac{4c-2}{4c+2\mu-3}}$, from Theorem 8 and Assumption
3 we have

$\displaystyle\mathbb{E}[L(\mathbf{W}_{T})-L(\mathbf{W}^{*})]=\mathcal{O}\big{(}\frac{1}{{n}}\big{)}.$

The proof is completed. ∎

###  B.4 More Discussion on Related Works

[35] derived a lower bound on the minimum eigenvalue of the Hessian for the
three-layer NN, where the first layer activation is linear, and the second
activation is smooth. They proved the weak convexity of the empirical risk
scales with $m^{\frac{1}{2}-2c}$ when optimizing the first and third layers of
weights with Lipschitz and convex losses. We train the first and the second
layers of the network with general smooth activation functions for both
layers. Our result shows that the weak convexity of the least square loss
scales with $m^{\frac{1}{2}-2c}$.

## References

  * [1] Z. Allen-Zhu, Y. Li, and Y. Liang.  Learning and generalization in overparameterized neural networks, going beyond two layers.  In Advances in neural information processing systems, volume 32, 2019.
  * [2] Z. Allen-Zhu, Y. Li, and Z. Song.  A convergence theory for deep learning via over-parameterization.  In International Conference on Machine Learning, pages 242–252. PMLR, 2019.
  * [3] S. Arora, S. Du, W. Hu, Z. Li, and R. Wang.  Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks.  In International Conference on Machine Learning, pages 322–332. PMLR, 2019.
  * [4] S. Arora, S. S. Du, W. Hu, Z. Li, R. R. Salakhutdinov, and R. Wang.  On exact computation with an infinitely wide neural net.  Advances in Neural Information Processing Systems, 32, 2019.
  * [5] D. Bahdanau, K. Cho, and Y. Bengio.  Neural machine translation by jointly learning to align and translate.  arXiv preprint arXiv:1409.0473, 2014.
  * [6] P. L. Bartlett, D. J. Foster, and M. J. Telgarsky.  Spectrally-normalized margin bounds for neural networks.  Advances in neural information processing systems, 30, 2017.
  * [7] P. L. Bartlett, A. Montanari, and A. Rakhlin.  Deep learning: a statistical viewpoint.  Acta numerica, 30:87–201, 2021.
  * [8] O. Bousquet and A. Elisseeff.  Stability and generalization.  The Journal of Machine Learning Research, 2:499–526, 2002.
  * [9] A. Brutzkus, A. Globerson, E. Malach, and S. Shalev-Shwartz.  Sgd learns over-parameterized networks that provably generalize on linearly separable data.  arXiv preprint arXiv:1710.10174, 2017.
  * [10] Y. Cao and Q. Gu.  Generalization bounds of stochastic gradient descent for wide and deep neural networks.  In Advances in neural information processing systems, volume 32, 2019.
  * [11] Z. Charles and D. Papailiopoulos.  Stability and generalization of learning algorithms that converge to global optima.  In International Conference on Machine Learning, pages 745–754. PMLR, 2018.
  * [12] L. Chizat and F. Bach.  On the global convergence of gradient descent for over-parameterized models using optimal transport.  In Advances in neural information processing systems, volume 31, 2018.
  * [13] L. Chizat, E. Oyallon, and F. Bach.  On lazy training in differentiable programming.  In Advances in Neural Information Processing Systems, volume 32, 2019.
  * [14] S. Du, J. Lee, H. Li, L. Wang, and X. Zhai.  Gradient descent finds global minima of deep neural networks.  In International conference on machine learning, pages 1675–1685. PMLR, 2019.
  * [15] S. S. Du, X. Zhai, B. Poczos, and A. Singh.  Gradient descent provably optimizes over-parameterized neural networks.  In International Conference on Learning Representations, 2018.
  * [16] N. Golowich, A. Rakhlin, and O. Shamir.  Size-independent sample complexity of neural networks.  In Conference On Learning Theory, pages 297–299. PMLR, 2018.
  * [17] M. Hardt, B. Recht, and Y. Singer.  Train faster, generalize better: Stability of stochastic gradient descent.  In International Conference on Machine Learning, pages 1225–1234. PMLR, 2016.
  * [18] G. Hinton, L. Deng, D. Yu, G. E. Dahl, A.-r. Mohamed, N. Jaitly, A. Senior, V. Vanhoucke, P. Nguyen, T. N. Sainath, et al.  Deep neural networks for acoustic modeling in speech recognition: The shared views of four research groups.  IEEE Signal processing magazine, 29(6):82–97, 2012.
  * [19] A. Jacot, F. Gabriel, and C. Hongler.  Neural tangent kernel: Convergence and generalization in neural networks.  Advances in neural information processing systems, 31, 2018.
  * [20] P. Ju, X. Lin, and N. B. Shroff.  On the generalization power of the overfitted three-layer neural tangent kernel model.  arXiv preprint arXiv:2206.02047, 2022.
  * [21] A. Krizhevsky, I. Sutskever, and G. E. Hinton.  Imagenet classification with deep convolutional neural networks.  Communications of the ACM, 60(6):84–90, 2017.
  * [22] I. Kuzborskij and C. Lampert.  Data-dependent stability of stochastic gradient descent.  In International Conference on Machine Learning, pages 2820–2829, 2018.
  * [23] Y. Lei, R. Jin, and Y. Ying.  Stability and generalization analysis of gradient methods for shallow neural networks.  In Advances in Neural Information Processing Systems, volume 35. PMLR, 2022.
  * [24] Y. Lei and Y. Ying.  Fine-grained analysis of stability and generalization for stochastic gradient descent.  In International Conference on Machine Learning, pages 5809–5819, 2020.
  * [25] Y. Lei and Y. Ying.  Sharper generalization bounds for learning with gradient-dominated objective functions.  In International Conference on Learning Representations, 2020.
  * [26] Y. Li and Y. Liang.  Learning overparameterized neural networks via stochastic gradient descent on structured data.  In Advances in neural information processing systems, volume 31, 2018.
  * [27] P. M. Long and H. Sedghi.  Generalization bounds for deep convolutional neural networks.  arXiv preprint arXiv:1905.12600, 2019.
  * [28] S. Mei, T. Misiakiewicz, and A. Montanari.  Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit.  In Conference on Learning Theory, pages 2388–2464. PMLR, 2019.
  * [29] S. Mei, A. Montanari, and P.-M. Nguyen.  A mean field view of the landscape of two-layer neural networks.  Proceedings of the National Academy of Sciences, 115(33):E7665–E7671, 2018.
  * [30] W. Mou, L. Wang, X. Zhai, and K. Zheng.  Generalization bounds of sgld for non-convex learning: Two theoretical viewpoints.  In Conference on Learning Theory, pages 605–638, 2018.
  * [31] B. Neyshabur, S. Bhojanapalli, and N. Srebro.  A pac-bayesian approach to spectrally-normalized margin bounds for neural networks.  In International Conference on Learning Representations, 2018.
  * [32] B. Neyshabur, R. Tomioka, and N. Srebro.  Norm-based capacity control in neural networks.  In Conference on Learning Theory, pages 1376–1401. PMLR, 2015.
  * [33] A. Nitanda, G. Chinot, and T. Suzuki.  Gradient descent can learn less over-parameterized two-layer neural networks on classification problems.  arXiv preprint arXiv:1905.09870, 2019.
  * [34] D. Richards and I. Kuzborskij.  Stability & generalisation of gradient descent for shallow neural networks without the neural tangent kernel.  In Advances in Neural Information Processing Systems, volume 34. PMLR, 2021.
  * [35] D. Richards and M. Rabbat.  Learning with gradient descent and weakly convex losses.  In International Conference on Artificial Intelligence and Statistics, pages 1990–1998. PMLR, 2021.
  * [36] D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. Van Den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot, et al.  Mastering the game of go with deep neural networks and tree search.  nature, 529(7587):484–489, 2016.
  * [37] N. Srebro, K. Sridharan, and A. Tewari.  Smoothness, low noise and fast rates.  In Advances in Neural Information Processing Systems, pages 2199–2207, 2010.
  * [38] H. Taheri and C. Thrampoulidis.  Generalization and stability of interpolating neural networks with minimal width.  arXiv preprint arXiv:2302.09235, 2023.
  * [39] C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals.  Understanding deep learning requires rethinking generalization.  arXiv e-prints, pages arXiv–1611, 2016.
  * [40] Y. Zhou, Y. Liang, and H. Zhang.  Understanding generalization error of sgd in nonconvex optimization.  Machine Learning, 111(1):345–375, 2022.


# Multiple-camera defocus imaging of ultracold atomic gases

A. R. Perry  1,2 S. Sugawa  1,3,4 F. Salces-Carcoba  1,5 Y. Yue  1 and I. B.
Spielman1  1Joint Quantum Institute, National Institute of Standards and
Technology, and University of Maryland, Gaithersburg, Maryland, 20899, USA
2Honeywell Quantum Solutions, 303 S. Technology Ct. 80021 Broomfield,
Colorado, USA
3Institute for Molecular Science, National Institutes of Natural Sciences,
Myodaiji, Okazaki 444-8585, Japan 4SOKENDAI (The Graduate University for
Advanced Studies), Myodaiji, Okazaki 444-8585, Japan 5LIGO Laboratory,
California Institute of Technology, MS 100–36, Pasadena, CA 91125, USA
<EMAIL_ADDRESS>
###### Abstract

In cold atom experiments, each image of light refracted and absorbed by an
atomic ensemble carries a remarkable amount of information. Numerous imaging
techniques including absorption, fluorescence, and phase-contrast are commonly
used. Other techniques such as off-resonance defocused imaging (ORDI, [1, 2,
3, 4]), where an in-focus image is deconvolved from a defocused image, have
been demonstrated but find only niche applications. The ORDI inversion process
introduces systematic artifacts because it relies on regularization to account
for missing information at some spatial frequencies. In the present work, we
extend ORDI to use multiple cameras simultaneously at degrees of defocus,
eliminating the need for regularization and its attendant artifacts. We
demonstrate this technique by imaging Bose-Einstein condensates, and show that
the statistical uncertainties in the measured column density using the
multiple-camera off-resonance defocused (MORD) imaging method are competitive
with absorption imaging near resonance and phase contrast imaging far from
resonance. Experimentally, the MORD method may be incorporated into existing
set-ups with minimal additional equipment.

††journal: oe

http://ultracold.jqi.umd.edu

##  1 Introduction

Ultracold atoms exist in isolation, enshrouded in ultrahigh vacuum, so that
nearly every measurement on them relies on their interaction with
electromagnetic fields. The most common measurements use a probe laser beam
that is attenuated and phase shifted by the atoms to recover two-dimensional
images of the integrated density–the column density–of the atoms. Whether the
technique be absorption imaging (AI), or phase-contrast imaging (PCI), the
spatially resolved column density of the atomic cloud is recovered; from this,
physical information regarding the atomic ensemble can be extracted.

In this paper, we describe and demonstrate an extension to off-resonance
defocused imaging (ORDI) pioneered in Refs. [1, 2, 3, 4]. ORDI uses
information from both the absorbed and phase-shifted probe laser light; by
contrast, absorption or phase-contrast imaging rely only on the absorption or
phase shift signal, respectively. Both the absorption and phase-shift are
proportional to the quantity of interest, the column density. When the laser
detuning from atomic resonance $\delta$ is large, the fractional absorption
$\propto 1/\delta^{2}$, while the phase-shift $\propto 1/\delta$: thus for
sufficiently large detunings the phase-shift is more significant than
absorption. Typically AI [5] is used for clouds of low to medium column
density using a resonant probe beam (no phase-shift), and PCI [6] is used to
image clouds of high column density using a far-detuned probe beam (negligible
absorption). In AI and PCI, intensity images are recorded by a detector at the
focus of the imaging system. In ORDI, a image is taken by a detector
positioned away from the focus: remarkably, Ref. [2] showed that given full
knowledge of the atoms’ complex susceptibility it is possible to digitally
refocus intensity images of atoms by inverting contrast transfer function
[CTF, shown in Fig. 1(a)] without knowing the phase of the underlying optical
field. Still, ORDI was beset with unavoidable imaging artifacts resulting from
lost information at some spatial frequencies in defocused images where the
inverse CTF diverges [Fig. 1(b)]. Here we demonstrate a technique to
reconstruct defocuse images of ultracold atoms with greatly reduced artifacts.
In this technique, multiple-camera off-resonance defocused (MORD) imaging, we
simultaneously use cameras placed at different defocused distances and show
that suitably placed cameras allow for essentially artifact-free
reconstruction of the atomic column density. We compare this technique to
conventional imaging techniques and show that its signal to noise ratio (SNR)
is comparable to AI near atomic resonance and comparable to PCI far from
resonance.

Figure 1: Contrast transfer function (a) and its inverse (b), as discussed in
Sect. 2.3, using eqns. (18) and (22). These are computed as a function of
transverse wave number $k_{\perp}$, for a probe laser beam with wavelength
$\lambda=780\ {\rm nm}$, detuning $\bar{\delta}=1$, and defocus distance
$z=60\ \mu{\rm m}$. The black curves denote $\tilde{h}(k_{\perp})$ and
$\tilde{h}^{-1}(k_{\perp})$ where appearance of repeating zeros in the CTF and
the associated divergences in its inverse indicate spatial frequencies where
all information about the initial density profile is lost. The red curve shows
the regularized inverse $\tilde{h}^{-1}_{\rm R}(k_{\perp})$ with
regularization parameter $\eta=0.2$, which tracks $\tilde{h}^{-1}(k_{\perp})$
until it exceeds a threshold value and then returns to zero.

This paper is organized as follows; in Sec. 1 we discuss the solution to the
vector wave equation under the paraxial approximation after interacting with a
thin, dilute atomic cloud. In Sec. 2, we describe absorption and phase-
contrast imaging; derive expressions for ORDI and MORD imaging; and conclude
with a theoretical comparison of MORD to absorption and phase-contrast
imaging. In Sec. 3, we describe the experimental implementation of the MORD
method with three detectors, and the procedure we used to prepare 87Rb Bose-
Einstein condensates (BECs) of variable column density. In Sec. 4, we present
our experimental MORD results.

###  1.1 Propagation of an electromagnetic wave

First we introduce the theoretical problem, starting with the propagation of
an electromagnetic wave defined at all positions ${\bf
r}=x\mathbf{e}_{x}+y\mathbf{e}_{y}+z\mathbf{e}_{z}$. For our neutral atomic
systems interrogated by a monochromatic probe laser beam with wavelength
$\lambda$ and wave number $k_{0}$ = $2\pi/\lambda$, the evolution of the laser
beam’s electric field in the presence of atoms with complex susceptibility
$\chi$ is described by a pair of scalar wave equations

$\nabla^{2}\mathcal{E}_{i}({\bf r})+k_{0}^{2}[1+\chi({\bf
r})]\mathcal{E}_{i}({\bf r})=0,$ (1)

i.e., Helmholtz equations, one for each polarization component
$\mathcal{E}_{i}$. These equations are valid provided that the susceptibility
$\chi$ changes slowly with respect to $\lambda$ [allowing the term
$\nabla(\nabla\cdot\boldsymbol{\mathcal{E}})$ in the vector wave equation to
be neglected]. For each polarization component, the Helmholtz equation then
has the formal solution

$\mathcal{E}({\bf r}_{\perp},z+\Delta z)=\exp\left\\{\pm i\Delta
z\left[\nabla_{\bot}^{2}+k_{0}^{2}+\chi({\bf
r}_{\perp})k_{0}^{2}\right]^{1/2}\right\\}\mathcal{E}({\bf r}_{\perp},z),$ (2)

provided $\chi({\bf r})$ has no dependence on $z$. Here ${\bf
r}_{\perp}=x\mathbf{e}_{x}+y\mathbf{e}_{y}$ and $\nabla_{\bot}^{2}$ =
$\partial^{2}/\partial^{2}x+\partial^{2}/\partial^{2}y$ are the transverse
position and Laplacian, respectively. $\mathcal{E}({\bf r}_{\perp},z)$ is the
field before propagation, and $\mathcal{E}({\bf r}_{\perp},z+\Delta z)$ is the
field that has propagated an infinitesimal distance $\Delta z$ through the
medium. This solution becomes straightforward to evaluate numerically even for
arbitrary displacements provided that $\chi$ has no spatial dependence – such
as the case for propagation in a homogenous isotropic medium – by working in
the Fourier domain.

In our simulations, we only used eq. (2) to evolve the electric field in free
space where $\chi=0$. For the problem at hand, we need to understand light
traveling though a medium with $\chi({\bf r}_{\perp},z)$ dependent on both
${\bf r}_{\perp}$ and $z$, a situation where eq. (1) is inconvenient to
manipulate analytically. For these cases, we make the paraxial approximation
that renders both numerical and analytical treatments straightforward. We
write the field $\mathcal{E}({\bf r}_{\perp},z)=\exp(izk_{0})E({\bf
r}_{\perp},z)$ making explicit the nominal propagation axis $\mathbf{e}_{z}$.
In addition, we assume that the transverse spatial structure is slowly varying
compared to the optical wavelength, i.e., $\left|\partial
E/\partial(k_{0}z)\right|\gg\left|\partial^{2}E/\partial^{2}(k_{0}z)\right|$.
Together these approximations lead to the paraxial wave equation

$\displaystyle i\frac{\partial}{\partial z}E({\bf r}_{\perp},z)$
$\displaystyle=\left[-\frac{\nabla_{\perp}^{2}}{2k_{0}}+\frac{k_{0}\chi({\bf
r}_{\perp},z)}{2}\right]E({\bf r}_{\perp},z).$ (3)

In this manuscript, the paraxial wave equation offers two primary benefits.
Firstly the free space propagator

$\displaystyle h_{\rm p}({\bf r}_{\perp},\Delta z)$
$\displaystyle=\exp\left(i\Delta z\frac{\nabla_{\perp}^{2}}{2k_{0}}\right),$
that gives $\displaystyle E({\bf r}_{\perp},z+\Delta z)=h_{\rm p}({\bf
r}_{\perp},\Delta z)E({\bf r}_{\perp},z),$

is Gaussian and is therefore straightforward to manipulate analytically.
Secondly, we parametrize propagation through a medium localized at $z=0$ in
terms of an absorption coefficient $\alpha({\bf r}_{\perp})$ and a phase shift
$\phi({\bf r}_{\perp})$. We relate the electric field $E_{-}({\bf
r}_{\perp},z=0)$ just prior to the medium to the field $E_{+}({\bf
r}_{\perp},z=0)$ just after the medium with

$\displaystyle E_{+}({\bf r}_{\perp},z=0)$
$\displaystyle=\exp\left[i\frac{k_{0}}{2}\int\chi({\bf r}_{\perp},\Delta
z)dz\right]E_{-}({\bf r}_{\perp},z=0)$ $\displaystyle=\exp\left[-\alpha({\bf
r}_{\perp})+i\phi({\bf r}_{\perp})\right]E_{-}({\bf r}_{\perp},z=0).$ (4)

This expression is valid provided the medium is thin compared to the depth of
field $2k_{0}/k_{\rm max}^{2}$, where $k_{\rm max}$ is the largest wave-vector
of any significance present in $E({\bf r})$, or more pragmatically $k_{\rm
max}$ might be the largest wave-vector resolvable by the experimental
detector. In effect, eq. (4) neglects diffraction as light propagates through
the atomic layer, and is equivalent to dropping the Laplacian in eq. (3).

For two-level atoms, we characterize the absorption and phase shift via the
complex susceptibility

$\chi({\bf
r})=\frac{\sigma_{0}}{k_{0}}\left[\frac{i-2\bar{\delta}}{1+\bar{I}({\bf
r})+4\bar{\delta}^{2}}\right]\rho({\bf r}),$ (5)

for an ensemble of atoms with density $\rho({\bf r})$ illuminated by a probe
laser of wavelength $\lambda$. Eq. (5) is valid for dilute clouds $\rho({\bf
r})\ll k_{0}^{3}$ such that collective effects can be neglected. Here
$\sigma_{0}=3\lambda^{2}/2\pi$ is the resonant cross-section, $\bar{I}({\bf
r})=I({\bf r})/I_{{\rm sat}}$ is the optical intensity $I({\bf
r})=c\epsilon_{0}\left|E({\bf r})\right|^{2}/2$ in units of the saturation
intensity $I_{{\rm sat}}$, and $\bar{\delta}=\delta/\Gamma$ is the detuning
$\delta$ from atomic resonance in units of the natural line-width $\Gamma$.
Here, $c$ is the speed of light and $\epsilon_{0}$, once known as the
permittivity of free space, is the now ill-named electric constant.

The two-level model for the susceptibility gives coefficients

$\displaystyle\alpha({\bf r}_{\perp})$ $\displaystyle={\rm OD}({\bf
r}_{\perp})/2,$ $\displaystyle{\rm and}$ $\displaystyle\phi({\bf r}_{\perp})$
$\displaystyle=-\bar{\delta}\ {\rm OD}({\bf r}_{\perp}).$ (6)

Where the optical depth

$\displaystyle{\rm OD}({\bf r}_{\perp})$
$\displaystyle\equiv-\ln\left[\frac{I_{+}({\bf r}_{\perp})}{I_{-}({\bf
r}_{\perp})}\right]=2\alpha,$ (7)

expresses exponential attenuation of light by the atoms and is defined in
terms of the intensity just before $I_{-}({\bf r}_{\perp})$ and just after
$I_{+}({\bf r}_{\perp})$ interacting with the atoms. The column density

$\displaystyle\rho_{\rm 2D}({\bf r}_{\perp})$ $\displaystyle=\int\rho({\bf
r}_{\perp},z){\rm d}z$

can be derived from the optical depth given both the detuning and the
intensity using [7]

$\displaystyle\sigma_{0}\rho_{\rm 2D}({\bf r}_{\perp})$
$\displaystyle=(1+4\bar{\delta}^{2}){\rm OD}({\bf r}_{\perp})+\bar{I}_{-}({\bf
r}_{\perp})\left[1-e^{-{\rm OD}({\bf r}_{\perp})}\right].$ (8)

This leads us to two essential messages for this section: (I) according to eq.
(6) the complete impact of the atomic ensemble on the electric field can be
parametrized in terms of ${\rm OD}({\bf r}_{\perp})$ alone; and (II) once
${\rm OD}({\bf r}_{\perp})$ is obtained, the column density can be
reconstructed using eq. (8), independent of what measurement technique was
employed to obtain the optical depth.

As a result, any imaging technique will first find the optical density and
then obtain the column density using eq. (8). Therefore in the following
discussion we will compare imaging techniques in terms of their ability to
reconstruct the optical depth.

##  2 Imaging techniques

In our experiments, the detectors – CCD cameras – are sensitive to the field’s
intensity, not its amplitude. The imaging techniques discussed here use image
pairs, each consisting of a 2D array of pixels giving the optical intensity
with atoms present $\bar{I}^{(i)}_{+}({\bf r}_{\perp})$ resulting from the
field $E_{+}({\bf r}_{\perp},z^{(i)})$, and the intensity with the atoms
absent $\bar{I}^{(i)}_{-}({\bf r}_{\perp})$ resulting from the field
$E_{-}({\bf r}_{\perp},z^{(i)})$. The superscript $(i)$ indicates that for
MORD several cameras simultaneously recordthe intensity at different positions
$z^{(i)}$. We characterize the impact of the atoms in terms of the fractional
drop in intensity

$\displaystyle g^{(i)}({\bf r}_{\perp})$
$\displaystyle=1-\frac{I^{(i)}_{+}({\bf r}_{\perp})}{I^{(i)}_{-}({\bf
r}_{\perp})}.$ (9)

Where it is clear, we will omit the camera index $i$ and pixel coordinate
${\bf r}_{\perp}$. Evidently this detection process has no direct sensitivity
to the fields’ phase, nor the phase shift imprinted by the atoms.

Each acquired image has a noise contribution $\delta I^{(i)}({\bf r}_{\perp})$
that we model as a classical random process from shot noise on the CCD
detector with

$\displaystyle\langle\delta I^{(i)}({\bf r}_{\perp})\rangle$
$\displaystyle=0,$ $\displaystyle{\rm and}$ $\displaystyle\langle\delta
I^{(i)}({\bf r}_{\perp})\delta I^{(i^{\prime})}({\bf
r}_{\perp}^{\prime})\rangle$ $\displaystyle=\delta_{i,i^{\prime}}\delta_{{\bf
r}_{\perp},{\bf r}_{\perp}^{\prime}}I_{0}\langle I^{(i)}({\bf
r}_{\perp})\rangle,$ (10)

where $I_{0}={\hbar\omega}/{\eta A\Delta t}$ is the intensity required to
generate a single photo-electron. Here $\hbar\omega=c\hbar k_{0}$ is the
single-photon energy, $\eta$ is the detector quantum efficiency (shot noise is
really the shot noise of the photo-electrons not of the photons), $A$ is the
area of a single pixel, and $\Delta t$ is the measurement time. This noise
model neglects other physical sources of noise such as CCD readout noise, or
excess noise from dark current.

Since the fractional absorption contains the full information about the atomic
ensemble, we transfer the noise in the images to the noise in the fractional
intensity which has $\langle\delta g^{(i)}({\bf r}_{\perp})\rangle=0$ and the
correlation function

$\displaystyle\langle\delta g^{(i)}({\bf r}_{\perp})\delta
g^{(i^{\prime})}({\bf r}_{\perp}^{\prime})\rangle$
$\displaystyle=\delta_{i,i^{\prime}}\delta_{{\bf r}_{\perp},{\bf
r}_{\perp}^{\prime}}\frac{I_{0}}{I^{(i)}_{-}({\bf r}_{\perp})}\left[1-\langle
g^{(i)}({\bf r}_{\perp})\rangle\right].$ (11)

In what follows, we describe the AI and PCI techniques, and then derive the
ORDI and MORD methods. For each technique, we compute the expected uncertainty
in optical depth resulting from photon shot noise, and conclude with a
comparison of these uncertainties across all cases.

###  2.1 Absorption imaging

AI proceeds directly from the intensities recorded by a single camera placed
in-focus (effectively recording the intensity as it was in the object plane at
$z=0$), to give the optical depth ${\rm OD}({\bf r}_{\perp})=-\ln[1-g({\bf
r}_{\perp})]$ without further approximation. AI is most straightforward for
resonant ($\bar{\delta}=0$) low intensity ($\bar{I}_{-}\ll 1$) imaging, giving
an optical depth ${\rm OD}({\bf r}_{\perp})=\sigma_{0}\rho_{\rm 2D}({\bf
r}_{\perp})$ proportional to the column density. In this limit, the repeated
scattering of resonant photons strongly perturbs the atomic ensemble after a
single instance of imaging. As a result, AI is not generally used to perform
weakly destructive measurements111Reference [8] describes a weakly destructive
absorption technique called partial transfer absorption imaging (PTAI) where
only a small fraction of a large atomic ensemble is transferred to a internal
state sensitive to a probe laser, while the majority of the atoms were kept in
a dark state..

Using the formalism in eqn. (11) along with eqn. (7), we find the noise for AI
to be

$\displaystyle\langle\delta{\rm OD}({\bf r}_{\perp})\rangle$
$\displaystyle=0,$ $\displaystyle{\rm and}$ $\displaystyle\langle\delta{\rm
OD}({\bf r}_{\perp})\delta{\rm OD}({\bf r}_{\perp}^{\prime})\rangle$
$\displaystyle=\delta_{{\bf r}_{\perp},{\bf
r}_{\perp}^{\prime}}\frac{\langle\delta g({\bf
r}_{\perp})^{2}\rangle}{[1-\langle g({\bf r}_{\perp})\rangle]^{2}}.$ (12)

This shows that the noise is still $\delta$-correlated in space and diverges
at large optical depth. This is expected because at large OD the vast majority
of the probe is absorbed, leading to an increased fractional contribution of
photon shot noise.

###  2.2 Phase contrast imaging

PCI is often used for weakly destructive measurements, and readily allows the
same cloud to be imaged repeatedly. Like AI, PCI is performed with a single
in-focus camera, but unlike AI, the recorded intensity of a phase-contrast
image contains phase information from which the column density is extracted.
After traversing the layer of atoms, the electric field $E_{+}=E_{-}+\Delta E$
may be expressed as a sum [5] of its unscattered and scattered parts $E_{-}$
and $\Delta E$. PCI is typically implemented by adding a $\theta=\pi/2$ phase
shift to the unscattered field222In practice this phase shift is created using
a phase plate, with a retarding spot slightly larger than the focused beam
spot-size, in the imaging system (Fig. 4). The $\pi/2$ phase shift maximizes
the phase contrast signal (in contrast, for $\theta$ = $\pi$, the Taylor
expansion is dominated by even functions, so that $I\propto\phi^{2}$). so that
$E_{-}\rightarrow E_{-}\exp(i\theta)$. PCI is typically applied in the far
detuned limit where absorption can be neglected, i.e., $\alpha\ll\phi$, giving
the PCI intensity pattern

$\displaystyle g({\bf r}_{\perp})$ $\displaystyle=2\left[\cos\phi({\bf
r}_{\perp})-\sin\phi({\bf r}_{\perp})-1\right]\approx-2\phi({\bf
r}_{\perp})=2\bar{\delta}{\rm OD}({\bf r}_{\perp})$ (13)

resulting from the interference of the the phase-shifted light with the light
refracted by the atoms. The final approximation in Eq. (13) is valid for small
phase shifts (requiring a combination of large detuning), and in this limit
the PCI signal is linear in $\phi$, therefore proportional to the optical
depth [6].

Next, we find the uncertainty in the recovered optical depth for PCI using
eqn. (13) to be

$\displaystyle\langle\delta{\rm OD}({\bf r}_{\perp})\rangle$
$\displaystyle=0,$ $\displaystyle{\rm and}$ $\displaystyle\langle\delta{\rm
OD}({\bf r}_{\perp})\delta{\rm OD}({\bf r}_{\perp}^{\prime})\rangle$
$\displaystyle=\delta_{{\bf r}_{\perp},{\bf
r}_{\perp}^{\prime}}\frac{1}{4\bar{\delta}^{2}}\langle\delta g({\bf
r}_{\perp})^{2}\rangle.$ (14)

This shows that for large detuning (where the approximations leading to PCI
are valid) and low optical depth ($g\ll 1$), the variance in phase contrast
imaging is reduced by a factor of $\bar{\delta}^{2}$ compared to that of AI.

###  2.3 Off resonant defocus imaging

The AI technique introduced in Sec. 2.1 is best implemented on resonance,
where there are no phase shifts. On the other hand, PCI works best off-
resonance when absorption is minimal. The ORDI technique [1, 2, 3, 4] is a
method that works best in the intermediate regime where both absorption and
phase shift are important. ORDI and MORD build from an invertible relation
between the observed intensity and the optical depth that recovers all but a
small range of spatial frequencies.

ORDI relies on several simplifying assumptions, the first of which is the
paraxial approximation to the electric field that has propagated through an
atomic cloud in Sec. 1.1. We assume that the electric field did not diffract
as it traveled through the cloud (i.e., that it was thin compared to the depth
of field). Both AI and PCI require these same approximations.

Going forward we introduce the Fourier transform (FT) of a two-dimensional
function $f({\bf r}_{\perp})$ as $\tilde{f}({\bf k}_{\perp})$ =
$\int_{-\infty}^{\infty}f({\bf r}_{\perp})\exp(-i{\bf k}_{\perp}\cdot{\bf
r}_{\perp}){\rm d}^{2}{{\bf r}_{\perp}}$.

Using the paraxial propagator and the convolution theorem, we readily obtain
the Fresnel diffraction integral

$\displaystyle E({\bf r}_{\perp},z)$ $\displaystyle=\frac{i}{\lambda
z}\int_{-\infty}^{\infty}E({\bf
r}_{\perp},z=0)\exp\left[\frac{ik_{0}}{2z}\left|{\bf r}_{\perp}-{\bf
r}_{\perp}^{\prime}\right|^{2}\right]{\rm d}^{2}{\bf r}_{\perp}^{\prime}.$
(15)

Using eqn. (15) and the electric field just after it traversed the cloud in
eqn. (4), the normalized intensity at a detector placed an arbitary distance
from the atomic ensemble is

$\displaystyle\tilde{g}({\bf k}_{\perp},z)=$
$\displaystyle\int_{-\infty}^{\infty}\bigg{\\{}1-\exp[-\alpha({\bf
r}_{\perp}+z{\bf k}_{\perp}/2k_{0})-\alpha({\bf r}_{\perp}-z{\bf
k}_{\perp}/2k_{0})$ $\displaystyle+i\phi({\bf r}_{\perp}-z{\bf
k}_{\perp}/2k_{0})-i\phi({\bf r}_{\perp}+z{\bf
k}_{\perp}/2k_{0})]\bigg{\\}}\times\exp(-i{\bf r}_{\perp}\cdot{\bf
k}_{\perp}){\rm d}^{2}{\bf r}_{\perp}.$ (16)

To derive the ORDI technique we further required that the phase is slowly-
varying: $|\phi({\bf r}_{\perp}+{z{\bf k}_{\perp}/2k_{0}})-\phi({\bf
r}_{\perp}-{z{\bf k}_{\perp}/2k_{0}})|\ll 1$, and that absorption is small:
$\alpha({\bf r}_{\perp})\ll 1$. To the lowest order in $\phi$ and $\alpha$,
the resulting normalized intensity

$\displaystyle\tilde{g}({\bf k}_{\perp},z)\approx$
$\displaystyle\int_{-\infty}^{\infty}[\alpha({\bf r}_{\perp}+z{\bf
k}_{\perp}/2k_{0})+\alpha({\bf r}_{\perp}-z{\bf k}_{\perp}/2k_{0})$ (17)
$\displaystyle-i\phi({\bf r}_{\perp}-z{\bf k}_{\perp}/2k_{0})+i\phi({\bf
r}_{\perp}+z{\bf k}_{\perp}/2k_{0})]\times\exp(-i{\bf r}_{\perp}\cdot{\bf
k}_{\perp}){\rm d}^{2}{\bf r}_{\perp}\>,$

is a Fourier integral of $\phi$ and $\alpha$. Defining the FTs of $\phi$ and
$\alpha$ as $\tilde{\phi}$ and $\tilde{\alpha}$, respectively, we find

$\displaystyle\tilde{g}({\bf k}_{\perp},z)$
$\displaystyle=2\tilde{\alpha}({\bf
k}_{\perp})\cos(zk_{\perp}^{2}/2k_{0})-2\tilde{\phi}({\bf
k}_{\perp})\sin(zk_{\perp}^{2}/2k_{0}),$ (18)

where $k_{\perp}^{2}=k_{x}^{2}+k_{y}^{2}$. Using eq. (6) we arrive at the
explicit expression

$\displaystyle\tilde{g}({\bf k}_{\perp},z)$
$\displaystyle=[\cos(zk_{\perp}^{2}/2k_{0})+2\bar{\delta}\sin(zk_{\perp}^{2}/2k_{0})]\tilde{\rm
OD}({\bf k}_{\perp})\equiv\tilde{h}({\bf k}_{\perp},z)\tilde{\rm OD}({\bf
k}_{\perp}),$ (19)

that uses a CTF $\tilde{h}({\bf k}_{\perp},z)$ to provide a linear relation
between the Fourier transformed optical depth $\tilde{\rm OD}({\bf
k}_{\perp})$ and the fractional change in intensity $\tilde{g}({\bf
k}_{\perp},z)$ defined in eq. (9).

We plot a representative CTF and its inverse in Fig. 1 showing singularities
at some spatial frequencies $k_{\perp}$, the locations of which depend upon
the camera position $z$ and the detuning $\bar{\delta}$. When $\tilde{h}({\bf
k}_{\perp},z)^{-1}$ is applied, measurement noise is amplified near the
divergences, so that no useful information can be extracted from these spatial
frequencies. The ratio $\alpha/\phi=-1/2\bar{\delta}$ along with the sign of
$z$ determines the quality of information at low spatial frequencies. When
${\rm sign}(z)\alpha/\phi<0$, the inverse CTF has a divergence at a low
spatial frequency, and information may be lost for the spatial structure of
interest. There are two mathematically equivalent cases to achieve the “good”
condition: $\bar{\delta}<0$ (red detuning) with $z<0$ (negative defocus), and
$\bar{\delta}>0$ (blue detuning) with $z>0$ (positive defocus).

####  2.3.1 ORDI statistical uncertainties and regularization

Here we compute the anticipated diverging uncertainty at the zeros of the CTF
quantitatively and introduce a regularization parameter to resolve these
divergences. In general the spatial structure in eq. (11) would lead to
correlated noise in $\langle\delta\tilde{g}({\bf
k}_{\perp})\delta\tilde{g}({\bf k}_{\perp}^{\prime})\rangle$, however, for
simplicity we assume that the spatial dependence is weak (as would be the case
for an extended system). We are reminded that random variables that are
uniform and $\delta$-correlated spatially are also uniform and
$\delta$-correlated in the Fourier basis, giving $\langle\delta\tilde{g}({\bf
k}_{\perp})\delta\tilde{g}({\bf k}_{\perp}^{\prime})\rangle=\delta_{{\bf
k}_{\perp},{\bf k}_{\perp}^{\prime}}\langle\delta\tilde{g}({\bf
k}_{\perp})^{2}\rangle$.

The anticipated variance of the reconstructed optical depth is therefore

$\displaystyle\langle\delta{\rm OD}({\bf k}_{\perp})\delta{\rm OD}({\bf
k}_{\perp}^{\prime})\rangle$ $\displaystyle=\delta_{{\bf k}_{\perp},{\bf
k}_{\perp}^{\prime}}\tilde{h}({\bf
k}_{\perp},z)^{-2}\langle\delta\tilde{g}({\bf k}_{\perp})^{2}\rangle,$

divergent at the zeros of $\tilde{h}({\bf k}_{\perp},z)$.

Here we describe the process of regularization used to mitigate the
amplification of noise near divergences in the inverse CTF. The basic idea is
to include a “default” (i.e., a Bayesian prior) optical depth ${\rm
OD}_{0}({\bf k}_{\perp})$ with uncertainty quantified by a known
$\delta$-correlated random variable $\delta{\rm OD}_{0}({\bf k}_{\perp})$, and
we use the weighted average of the reconstructed and prior images

$\displaystyle\tilde{\rm OD}({\bf k}_{\perp})$ $\displaystyle=\frac{a({\bf
k}_{\perp})\tilde{h}({\bf k}_{\perp},z)^{-1}\tilde{g}({\bf
k}_{\perp},z)+b({\bf k}_{\perp}){\rm OD}_{0}({\bf k}_{\perp})}{a({\bf
k}_{\perp})+b({\bf k}_{\perp})}$ (20)

as our reconstructed optical depth. We determine the coefficients $a({\bf
k}_{\perp})$ and $b({\bf k}_{\perp})$ by minimizing the variance

$\displaystyle\langle\delta{\rm OD}({\bf k}_{\perp})\delta{\rm OD}({\bf
k}_{\perp}^{\prime})\rangle$ $\displaystyle=\delta_{{\bf k}_{\perp},{\bf
k}_{\perp}^{\prime}}\frac{a({\bf k}_{\perp})^{2}\tilde{h}({\bf
k}_{\perp},z)^{-2}\langle(\delta\tilde{g}_{\perp})^{2}\rangle+b({\bf
k}_{\perp})^{2}\langle\delta{\rm OD}_{0}({\bf k}_{\perp})^{2}\rangle}{[a({\bf
k}_{\perp})+b({\bf k}_{\perp})]^{2}},$

for each wavevector. This gives standard expression for Wiener deconvolution
[9]

$\displaystyle\tilde{\rm OD}({\bf k}_{\perp})$
$\displaystyle=\frac{\tilde{h}({\bf k}_{\perp},z)\tilde{g}({\bf
k}_{\perp},z)+\eta^{2}({\bf k}_{\perp}){\rm OD}_{0}({\bf
k}_{\perp})}{\tilde{h}({\bf k}_{\perp},z)^{2}+\eta({\bf k}_{\perp})^{2}}$ (21)

with regularization constant $\eta({\bf
k}_{\perp})^{2}=\langle\delta\tilde{g}({\bf
k}_{\perp})^{2}\rangle/\langle\delta{\rm OD}_{0}({\bf k}_{\perp})^{2}\rangle$.
In practice we typically select the prior ${\rm OD}_{0}({\bf k}_{\perp})=0$,
essentially assuming no prior information, and take $\eta$ to be ${\bf
k}$-independent. This results in the Tikhonov regularized inverse CTF

$\displaystyle\tilde{h}_{\rm R}({\bf k}_{\perp},z)^{-1}$
$\displaystyle=\frac{\tilde{h}({\bf k}_{\perp},z)}{\tilde{h}({\bf
k}_{\perp},z)^{2}+\eta^{2}}$ (22)

that blocks the divergence of statistical noise, but introduces artifacts.

Since the ORDI technique is implemented in the Fourier basis, we find the
noise-correlation function in coordinate space

$\displaystyle\langle\delta{\rm OD}({\bf r}_{\perp})\delta{\rm OD}({\bf
r}_{\perp}^{\prime})\rangle$ $\displaystyle=\langle\delta g({\bf
r}_{\perp})^{2}\rangle\frac{1}{N}\sum_{{\bf k}_{\perp}}\frac{\tilde{h}({\bf
k}_{\perp},z)^{2}}{\left[\tilde{h}({\bf
k}_{\perp},z)^{2}+\eta^{2}\right]^{2}}e^{i{\bf k}_{\perp}\cdot\left({\bf
r}_{\perp}-{\bf r}_{\perp}^{\prime}\right)}$ (23)

where we explicitly expressed the discrete FT in terms of a sum over a total
of $N$ pixels. Unlike AI or PCI, ORDI reconstruction of the optical depth has
correlated noise.

###  2.4 Multi-camera off resonant defocus imaging

We showed in Sec. 2.3 that with the ORDI method, spatial frequencies exist for
which we retrieve no information (where $\tilde{h}\rightarrow 0$). These
spatial frequencies depend on $z$, the position in the object plane where the
intensities are recorded (Fig. 2). This suggests that by adding cameras to the
system at different $z$, we might recover information at all spatial
frequencies. In the multiple camera method, the images are combined and
processed in a way that minimizes the uncertainty in the recovered optical
depth.

Figure 2: Forward (a) and inverse (b) CTFs computed as a function of
transverse wave number $k_{\perp}$, for detuning $\bar{\delta}=1$ for three
defocus distances $60\ \mu{\rm m}$ (black), $-100\ \mu{\rm m}$ (blue), and
$87\ \mu{\rm m}$ (orange). This shows that for a generic selection of defocus
distances the CTFs do not have coincident zeros

As shown in Sec. 2.3, each CTF taken independently provides a linear relation
between a measurement and the estimated optical depth [eqn. (19)]. Our task is
to find the best estimate of the optical depth for MORD using the measurements
taken in the laboratory [eqn. (9)] and their corresponding CTFs. We model
shot-noise, the only source of noise we consider, as noise that is spatially
uncorrelated and uniform over all spatial frequencies (i.e., additive white
noise). Following the argument in Sec. 2.3.1, we minimize the noise in the
reconstructed optical depth and find

$\tilde{\rm
OD}_{k}=-\frac{\sum_{(i)}\tilde{h}_{k}^{(i)}\tilde{g}_{k}^{(i)}}{\sum_{(i)}|\tilde{h}_{k}^{(i)}|^{2}+\eta^{2}}.$
(24)

For $\eta=0$ and non-overlapping divergences, the above equation is an exact
solution to the intensity predicted by the scalar wave equation, subject to
the approximations discussed above. As with the ORDI case, this transfer
function also transforms uncorrelated measurement noise into correlated noise
in reconstructed images.

###  2.5 Comparison of statistical and systematic uncertainties

We compare the signal to noise ratio (SNR) of three-camera MORD to those of AI
and PCI in Fig. 3(a). The solid symbols are the result of a numerical
simulation of our full imaging process, while the curves for PCI and AI plot
the expected SNR given the expressions in eqns. (12) and (14), thereby
confirming the performance of our numerical model. Except for the resonant
case, the MORD imaging technique gives a larger SNR than AI at the same
detuning. Further, for positive detuning [right panel to Fig. 3(a)] MORD
method shows the same $\delta^{-1}$ scaling in the SNR as PCI, but with about
$2\times$ lower SNR. The performance at negative detuning is slightly reduced
owing to two of the cameras having a near-zero $k$ node in their CTF as
compared to just one for positive detuning.

Figure 3: Simulations. (a) Computed signal to noise ratio for AI (black
markers), PCI (blue markers), and MORD (red markers) for both red and blue
detunings plotted on separate log scales. The numerical simulations and
analytical solutions (see Sects. 2.1 and 2.2) are shown as symbols and solid
curves, respectively. These simulations combined three defocus distances $60\
\mu{\rm m}$, $-100\ \mu{\rm m}$, and $87\ \mu{\rm m}$ and set the
regularization parameter $\eta=0$. (b) Optical depth obtained for AI, PCI, and
MORD compared to the true value (black curve). Both MORD and AI show a
systematic shift at small OD resulting from noise rectification when
converting from measured intensities to OD.

Next Fig. 3(b) quantifies systematic uncertainties in the MORD calculated
optical depth. Here the black curve plots the true optical depth, and the
symbols plot the outcome of our numerical simulation. At very low optical
depth both AI and MORD begin to diverge from the true signal. These systematic
shifts result from the non-linearity in the logarithm used to convert from
fractional absorption to OD, where detector noise is rectified, leading to
excess signal.

##  3 Experimental techniques

Our optical geometry, schematically depicted in Fig. 4, consisted of a
standard two-lens Keplerian microscope. The first lens (focal length $f_{1}$)
was positioned a distance $f_{1}$ from the object (a BEC in our experiments);
and the second lens (focal length $f_{2}$) was placed a distance $f_{1}+f_{2}$
from the first lens. Typically the detector would be placed at the focus of
the second lens, and would have a magnification $M=f_{2}/f_{1}$. This system
forms the conceptual basis of the imaging system described in this manuscript.

Figure 4: A simplified schematic of a two-lens Keplerian imaging system with
magnification $M\approx 3.3$ using lenses $f_{1}=75\ {\rm mm}$ and $f_{2}=250\
{\rm mm}$. In MORD, the three detector planes $z^{(i)}$ are located away from
the focus. This is equivalent to having three detectors next to BEC, as shown.
The imaging resolution is set by the diameter of the apertures placed in the
imaging system. A representative aperture, placed near the Fourier plane, is
shown above.

We implemented the MORD technique using a two-lens imaging system with
magnification $M\approx 3.3$ (as shown in Fig. 4), and placed three detectors
at different distances from the focal plane. The system consisted of a pair of
25.4 mm diameter lenses with focal lengths $f_{1}=75$ mm and $f_{2}=250$ mm
separated by 325(10) mm. In such an imaging system, a point
$(x_{0},y_{0},z_{0})$ in the object space is imaged to the point
$(-Mx_{0},-My_{0},M^{2}z_{0})$ in the image space. We placed a $18(1)$ mm
aperture close to the imaging system’s Fourier plane to minimize spherical
aberrations. This gave a numerical aperture NA $\approx 0.12$. After the final
lens, roughly equal fractions of the light was directed to each of our three
detectors (Fig. 5) using non-polarizing beam splitters (NPBSs) with reflection
to transmission (R:T) ratios 70:30 and 50:50. We detected this light on
charge-coupled device (CCD) cameras with 648$\times$488 square pixels with
width 5.6 $\mu$m. Each camera was on a translation stage, so that the set-up
could be used for both the defocused and standard absorption imaging methods.

Figure 5: Schematic of our MORD setup. The two-lens imaging system described
by Fig. 4 is followed by two non-polarizing beam splitters that nominally
split the probe laser beam into three equal intensities. Each image is then
recorded by its designated camera. Each camera takes a defocused image at
position $M^{2}z^{(i)}$ from focus, where the red circles denote the image
planes.

###  3.1 Experimental procedure

Here we describe the experimental procedure used to acquire the images for the
MORD technique. We collected about $2\times 10^{8}$ 87Rb atoms in a vapor-fed
six-beam magneto-optical trap, performed sub-Doppler cooling, and then trapped
the atoms in the $\left|f=2,m_{F}=2\right\rangle$ state in a spherical
quadrupole trap. We used magnetic transport [10] to move the resulting cloud
about 42 cm vertically in 2.2 s, giving an ensemble at $\approx 120\ \mu$K
with about $1\times 10^{8}$ atoms. We then evaporated to degeneracy in the
combined magnetic/optical technique described in Ref. [11]. During
evaporation, we performed a microwave transfer between the ground hyperfine
states $\left|f=2,m_{F}=2\right\rangle$ to $\left|f=1,m_{F}=-1\right\rangle$,
giving $100\times 10^{3}$ atom BECs in a cross-optical dipole trap every $15$
s. The resulting trap frequencies were $\approx$ 110 Hz, 75 Hz, and 50 Hz
along $\mathbf{e}_{x}$,$\mathbf{e}_{y}$, and $\mathbf{e}_{z}$ respectively. To
achieve the desired optical depth to test our imaging technique, we performed
a partial $\approx 10$ % transfer to the $\left|f=2,m_{F}=1\right\rangle$
state with a short ($\ll\pi/2$) microwave pulse [8]. We then used a probe beam
with $\lambda\approx 780\ {\rm nm}$ detuned a variable $\bar{\delta}$ from the
$f$ = $2$ to $f^{\prime}$ = $3$ cycling transition (without a repumping laser)
to image the transferred $N\approx 1\times 10^{4}$ atoms after a 6 ms time of
flight (TOF) with the three cameras simultaneously. In Sec. 4.1, we present
the results of this experiment for $\bar{\delta}=2.0(1)$. We used a probe beam
with intensity $I\approx 2.5I_{\rm sat}$, where $I_{\rm sat}\approx
1.67~{}{\rm mW/cm^{2}}$ [12] for a circularly polarized probe beam.

##  4 Measurement and analysis

###  4.1 Experimental data

Fig. 6(a) shows the fractional absorption $g^{(i)}$ recorded on each camera as
described by eqn. (9). In practice we obtained a third image with neither the
atoms nor the probe light. This background image was subtracted from
$I^{(i)}_{+}$ and $I^{(i)}_{-}$ to remove dark counts and stray light from the
images. The camera 1 image was defocused a distance $z^{(1)}$ = $1.5$ mm away
from the image plane. Similarly, the diffraction patterns from cameras 2 and 3
resulted from defocus distances of $z^{(2)}$ = $3.3$ mm and $z^{(3)}$ = $7.6$
mm, respectively. These distances were chosen to insure the diffraction
patterns were discernible within the imaging system resolution, and the
interference pattern was contained within the spatial extent of the detector.

To compare the ORDI and MORD imaging techniques, we show the single-camera
ORDI results for each of the three cameras independently in the left three
panels of Fig. 6(b), and the three-camera MORD reconstructed on the right
panel. The background of the MORD method has visibly fewer artifacts than the
ORDI reconstructed images. Lastly, we address the fidelity of the
reconstruction by comparing to the expected “Thomas-Fermi” density
distribution [13]

$\displaystyle n(x)=n_{0}\left[1-(x-x_{0})^{2}/r_{\rm TF}^{2}\right]^{3/2}.$
(25)

Figure 6(c) plots cross-sectional cuts along $\mathbf{e}_{x}$ through the
reconstructions with black symbols along with fits to the Tomas-Fermi model
with red curves. We see that the data is in good agreement with the expected
behavior.

The defocus distances $z^{(i)}$ used in the ORDI and MORD reconstructions
shown in Fig. 6 were first measured in the lab with $\approx 1\ {\rm mm}$
uncertainties, we then used the focusing technique in Ref. [14] to fine tune
the displacements $z^{(i)}$.

Figure 6: Raw and refocused data. (a) Raw data with defocus distances of
$M^{2}z^{(1)}=1.5\ {\rm mm}$, $M^{2}z^{(2)}=3.3\ {\rm mm}$ and
$M^{2}z^{(3)}=7.6\ {\rm mm}$ showing clear defocus patterns. A radial mask
excluded artifacts from the probe beam diffracting off of the edge of the CCD
sensor. (b) Refocused images. The first three images depict individual ORDI
reconstructions and the right-most image shows a MORD reconstruction. The
ring-like artifacts present in the ORDI method are less prevalent in the MORD
data. (c) Cross sections along $\mathbf{e}_{x}$ (black markers) along with
fits (red curves) to the expected “Thomas-Fermi” distribution.

##  5 Conclusion

We experimentally demonstrated an improvement to the single-camera ORDI
technique by using three cameras simultaneously to eliminate the divergences
that arise in any single CTF. We studied the systematic uncertainties of the
MORD method, and theoretically compared multiple techniques using simulated
data to understand the array of imaging techniques on equal footing. We showed
that in the regime of far detuned probe beam and low optical depth, the MORD
method is comparable to PCI. Therefore, in experiment, the easier to implement
MORD set-up may be preferable to PCI.

Because the first low-spatial-frequency divergence of a CTF may occur at
length scales of tens of micrometers, ORDI has been limited to imaging
relatively large objects. By eliminating the spatial CTF divergences, MORD
offers a complementary technique to in-situ AI and PCI imaging of quantum
gases. The SNR of MORD imaging is about 1.5 times below both AI and PCI in
their respective optimal operating conditions: resonant imaging for AI and
far-detuned imaging for PCI. As a result MORD can switch between near optimal
strong (destructive) measurements and weak (minimally destructive)
measurements with no hardware modifications. In addition, MORD eliminates the
need to refocus the imaging systems, for example in TOF experiments where the
object plane shifts depending on the TOF.

A final noteworthy outcome of our noise analysis is that even with spatially
uncorrelated detector noise, the ORDI and MORD methods introduce correlations
into the reconstructed signal, meaning that without added calibration, these
techniques would not be of use in experiments studying noise-correlations
between atoms [16].

Funding This work was partially supported by the AROs Atomtronics MURI, by the
AFOSRs Quantum Matter MURI, NIST, and the NSF through the PFC at the JQI.

Acknowledgments We thank D. Barker and A. Putra for their careful and thorough
reading of this manuscript. We appreciate the efforts of E. Altuntas, R. P.
Anderson, Q.-Y. Liang, D. Trypogeorgos, and A. Valdés-Curiel for employing
defocus imaging in their experiments, and motivating the completion of this
manuscript.

Disclosures The authors declare no conflicts of interest.

Data Availability Statement Data underlying the results presented in this
paper are not publicly available at this time but may be obtained from the
authors upon reasonable request.

## References

  * [1] L. D. Turner, K. F. E. M. Domen, and R. E. Scholten, “Diffraction-contrast imaging of cold atoms,” Phys. Rev. A 72, 031403 (2005).
  * [2] L. D. Turner, K. P. Weber, D. Paganin, and R. E. Scholten, “Off-resonant defocus-contrast imaging of cold atoms,” Opt. Lett. 29, 232–234 (2004).
  * [3] L. D. Turner, “Holographic imaging of cold atoms,” PhD Thesis, University of Melbourne (2004).
  * [4] P. B. Wigley, P. J. Everitt, K. S. Hardman, M. R. Hush, C. H. Wei, M. A. Sooriyabandara, P. Manju, J. D. Close, N. P. Robins, and C. C. N. Kuhn, “Non-destructive shadowgraph imaging of ultra-cold atoms,” Opt. Lett. 41, 4795–4798 (2016).
  * [5] W. Ketterle, D. S. Durfee, and D. Stamper-Kurn, “Making, probing and understanding Bose-Einstein condensates,” In Bose-Einstein condensation in atomic gases, Proceedings of the International School of Physics "Enrico Fermi", Course CXL pp. 67–176 (1999).
  * [6] M. R. Andrews, D. M. Kurn, H.-J. Miesner, D. S. Durfee, C. G. Townsend, S. Inouye, and W. Ketterle, “Propagation of sound in a Bose-Einstein condensate,” Phys. Rev. Lett. 79, 553–556 (1997).
  * [7] G. Reinaudi, T. Lahaye, Z. Wang, and D. Guéry-Odelin, “Strong saturation absorption imaging of dense clouds of ultracold atoms,” Opt. Lett. 32, 3143–3145 (2007).
  * [8] A. Ramanathan, S. R. Muniz, K. C. Wright, R. P. Anderson, W. D. Phillips, K. Helmerson, and G. K. Campbell, “Partial-transfer absorption imaging: A versatile technique for optimal imaging of ultracold gases,” Review of Scientific Instruments 83, 083119 (2012).
  * [9] F. Orieux, J.-F. Giovannelli, and T. Rodet, “Bayesian estimation of regularization and point spread function parameters for wiener–hunt deconvolution,” J. Opt. Soc. Am. A 27, 1593–1607 (2010).
  * [10] M. Greiner, I. Bloch, T. W. Hänsch, and T. Esslinger, “Magnetic transport of trapped cold atoms over a large distance,” Phys. Rev. A 63, 031401 (2001).
  * [11] Y.-J. Lin, A. R. Perry, R. L. Compton, I. B. Spielman, and J. V. Porto, “Rapid production of 87rb bose-einstein condensates in a combined magnetic and optical potential,” Phys. Rev. A 79, 063631 (2009).
  * [12] D. A. Steck, “Rubidium 87 d line data,” (2001).
  * [13] Y. Castin and R. Dum, “Bose-einstein condensates in time dependent traps,” Phys. Rev. Lett. 77, 5315–5319 (1996).
  * [14] A. Putra, D. L. Campbell, R. M. Price, S. De, and I. B. Spielman, “Optimally focused cold atom systems obtained using density-density correlations,” Review of Scientific Instruments 85, 013110 (2014).
  * [15] N. Gemelke, X. Zhang, C.-L. Hung, and C. Chin, “In situ observation of incompressible Mott-insulating domains in ultracold atomic gases.” Nature 460, 995–998 (2009).
  * [16] C.-L. Hung, X. Zhang, L.-C. Ha, S.-K. Tung, N. Gemelke, and C. Chin, “Extracting density–density correlations from in situ images of atomic quantum gases,” New Journal of Physics 13, 075019 (2011).
  * [17] C. Hofrichter, L. Riegger, F. Scazza, M. Höfer, D. R. Fernandes, I. Bloch, and S. Fölling, “Direct probing of the mott crossover in the $\mathrm{SU}(n)$ fermi-hubbard model,” Phys. Rev. X 6, 021030 (2016).