$\bm{e}_{1}(t)=-\eta{\bm{M}}^{*}{\bm{v}}_{1}{\bm{v}}_{1}^{\top}{\bm{R}}(t)+\eta\left({\bm{v}}_{1}{\bm{v}}_{1}^{\top}\bm{\Gamma}(t)-\bm{\Gamma}(t){\bm{v}}_{1}{\bm{v}}_{1}^{\top}\right){\bm{D}}(t)=\eta\left({\bm{v}}_{1}{\bm{v}}_{1}^{\top}\bm{\Gamma}(t)-\bm{\Gamma}(t){\bm{v}}_{1}{\bm{v}}_{1}^{\top}\right){\bm{D}}(t).$

Using the upper bound of $\|{\bm{D}}(t)\|$ in Lemma C.9, and Assumption C.3 we
have

$\|\bm{e}_{1}(t)\|\leq 2\eta\|\Gamma(t)\|\|{\bm{D}}(t)\|\leq
2\eta\frac{c_{2}}{m}c_{3}\sqrt{nm}=2c_{2}c_{3}\eta\sqrt{\frac{n}{m}}$

.

Now we consider the sequence ${\bm{R}}^{\prime}(t)$.

First by Corollary C.3, we can see that the eigenvalues of
$({\bm{M}}^{*}(t)-\bm{\Gamma}^{*}(t))(\bm{I}-{\bm{v}}_{1}{\bm{v}}_{1}^{\top})$
are all the eigenvalues of ${\bm{M}}^{*}(t)-\bm{\Gamma}^{*}(t)$ except the
largest one, hence are in $(\tau,2/\eta-\tau)$. Hence because
$m=\Omega(n^{2})$, if we let $\frac{\lambda_{r}}{nd}<\frac{c_{2}+c_{6}}{m}$,
then by Corollary C.3 we have all eigenvalues of
${\bm{M}}^{*}(t)(\bm{I}-{\bm{v}}_{1}{\bm{v}}_{1}^{\top})$ are in
$(\tau^{\prime},2/\eta-\tau^{\prime})$ where
$\tau^{\prime}=\frac{\lambda_{r}}{nd}$ . Hence
$\|\bm{I}-\eta{\bm{M}}(t)(\bm{I}-{\bm{v}}_{1}(t){\bm{v}}_{1}(t)^{\top})\|\leq
1-\eta\tau^{\prime}$.

By the calculations above we can get

$\displaystyle\|\bm{R}(t+1)-\bm{R}^{\prime}(t+1)\|$
$\displaystyle=\|(\bm{I}-\eta{\bm{M}}^{*}(t)(\bm{I}-{\bm{v}}_{1}{\bm{v}}_{1}^{\top}))(\bm{R}(t)-\bm{R}^{\prime}(t))+\bm{e}_{1}(t)\|$
$\displaystyle\leq\|(\bm{I}-\eta{\bm{M}}(t)(\bm{I}-{\bm{v}}_{1}{\bm{v}}_{1}^{\top}))(\bm{R}(t)-\bm{R}^{\prime}(t))\|+\|\bm{e}_{1}(t)\|$
$\displaystyle\leq\|\bm{I}-\eta{\bm{M}}(t)(\bm{I}-{\bm{v}}_{1}{\bm{v}}_{1}^{\top})\|\|\bm{R}(t)-\bm{R}^{\prime}(t)\|+\|\bm{e}_{1}(t)\|$
$\displaystyle\leq\|\bm{R}(t)-\bm{R}^{\prime}(t)\|(1-\eta\tau^{\prime})+2c_{2}c_{3}\eta\sqrt{\frac{n}{m}}.$

Thus if we denote
$\|\bm{R}(t)-\bm{R}^{\prime}(t)\|-\frac{2c_{2}c_{3}\eta\sqrt{\frac{n}{m}}}{\eta\tau^{\prime}}$
by $p(t)$, and replace $\|\bm{R}(t)-\bm{R}^{\prime}(t)\|$ in the inequality
above by $p(t)+\frac{2c_{2}c_{3}\eta\sqrt{\frac{n}{m}}}{\eta\tau^{\prime}}$,
we can get $|p(t+1)|\leq|p(t)|(1-\eta\tau^{\prime})$. Hence, we can have
$|p(t)|<|p(0)|=\frac{2c_{2}c_{3}\eta\sqrt{\frac{n}{m}}}{\eta\tau^{\prime}}$
for any time $t$. Therefore, we can obtain
$\|\bm{R}(t)-\bm{R}^{\prime}(t)\|<\frac{2c_{2}c_{3}\eta\sqrt{\frac{n}{m}}}{{\eta\tau^{\prime}}}+|p(0)|=\frac{4c_{2}c_{3}\sqrt{\frac{n}{m}}}{\tau^{\prime}}=O(d\sqrt{\frac{n^{3}}{m}}/\lambda_{r})$.

∎

Now based on Theorem C.10, we can give an upper bound of $\|{\bm{R}}(t)\|$.
Because $\|{\bm{R}}^{\prime}(t)\|$ is always decreasing and
$\|{\bm{R}}^{\prime}(0)\|=\sqrt{n}$, hence if
$m=\Omega(n^{2}d^{2}/\lambda_{r}^{2})$, we can have
$O(d\sqrt{\frac{n^{3}}{m}}/\lambda_{r})=O(\sqrt{n})$. Hence

$\|{\bm{R}}(t)\|\leq\|{\bm{R}}^{\prime}(t)\|+O(\sqrt{n})=O(\sqrt{n}).$ (19)

Let $\|{\bm{R}}(t)\|\leq c_{7}\sqrt{n}$.

Next we can use Assumption C.4 to prove that ${\bm{D}}(t)^{\top}{\bm{v}}_{1}$
increases geometrically when $\Lambda>2/\eta$, which then causes the drop of
the sharpness.

######  Lemma C.11.

Let $\rho^{*}=\frac{(c_{2}+c_{6})c_{7}}{2c_{3}}$,
$\rho=\rho^{*}+\frac{\eta}{2}\frac{5c_{2}+c_{6}}{m}$,
$\epsilon_{1}=2\eta(\rho^{*}-\frac{(c_{2}+c_{6})c_{7}}{2c_{3}})$. If
$\Lambda(t),\Lambda(t+1)>\frac{2}{\eta}(1+\rho)$, we have
$|{\bm{D}}(t+1)^{\top}{\bm{v}}_{1}|>(1+\epsilon_{1}){\bm{D}}(t)^{\top}{\bm{v}}_{1}$.

###### Proof.

$\displaystyle{\bm{D}}(t+1)^{\top}{\bm{v}}_{1}$
$\displaystyle={\bm{D}}(t)^{\top}\left(\bm{I}-\eta{\bm{M}}^{*}(t)\right){\bm{v}}_{1}$
$\displaystyle={\bm{D}}(t)^{\top}\left(\bm{I}-\eta\gamma^{*}(t)\mathbf{X}^{\top}\mathbf{X}\right){\bm{v}}_{1}-\eta{\bm{D}}(t)^{\top}\bm{\Gamma}^{*}(t){\bm{v}}_{1}$
$\displaystyle=\left(1-\eta\gamma^{*}(t)\lambda_{1}\right){\bm{D}}(t)^{\top}{\bm{v}}_{1}-\eta{\bm{D}}(t)^{\top}\bm{\Gamma}^{*}(t){\bm{v}}_{1}$

First by Lemma C.8 and Corollary C.2:

$\displaystyle\gamma^{*}(t)\lambda_{1}$
$\displaystyle={\bm{v}}_{1}^{\top}(k_{s}({\bm{M}}(t+1)-\bm{\Gamma}(t+1))+(1-k_{s})({\bm{M}}(t)-\bm{\Gamma}(t))){\bm{v}}_{1}$
$\displaystyle\geq
k_{s}\Lambda^{*}(t+1)+(1-k_{s})\Lambda^{*}(t)-\frac{2c_{2}}{m}$
$\displaystyle\geq\frac{2(1+\rho)}{\eta}-\frac{4c_{2}}{m}$

Also we have
$\left|{\bm{D}}(t)^{\top}\bm{\Gamma}^{*}(t){\bm{v}}_{1}\right|\leq\frac{c_{2}+c_{6}}{m}\|{\bm{D}}(t)\|\leq\frac{c_{2}+c_{6}}{m}|({\bm{D}}(t)^{\top}{\bm{v}}_{1}|+\|{\bm{R}}(t)\|)$.

Hence

$\displaystyle|{\bm{D}}(t+1)^{\top}{\bm{v}}_{1}|$
$\displaystyle\geq|1-\eta\gamma^{*}(t)\lambda_{1}||{\bm{D}}(t)^{\top}{\bm{v}}_{1}|-\eta|{\bm{D}}(t)^{\top}\bm{\Gamma}^{*}(t){\bm{v}}_{1}|$
$\displaystyle\geq|-1-2\rho+\frac{4c_{2}\eta}{m}+\frac{(c_{2}+c_{6})\eta}{m}|$
$\displaystyle\geq(1+2\eta\rho^{*})|{\bm{D}}(t)^{\top}{\bm{v}}_{1}|-\eta\frac{c_{2}+c_{6}}{m}c_{7}\sqrt{n}$
$\displaystyle\geq(1+\epsilon_{1})|{\bm{D}}(t)^{\top}{\bm{v}}_{1}|$

Here the third inequality holds by the definition of $\rho^{*}$. ∎

Now we state a lemma which proves that if ${\bm{D}}(t)^{\top}{\bm{v}}_{1}$ is
large enough, then the sharpness will decrease in the next iteration.

######  Lemma C.12.

Assume $m=\Omega(\eta)$. There exists constant $c_{8},c_{9}>0$ such that if
${\bm{D}}(t)^{\top}{\bm{v}}_{1}>c_{8}\sqrt{n}$, then
${\bm{v}}_{1}^{\top}{\bm{M}}(t+1){\bm{v}}_{1}-{\bm{v}}_{1}^{\top}{\bm{M}}(t){\bm{v}}_{1}<-c_{9}/m$.

###### Proof.

Recall Equation (17). Also we have $\|{\bm{R}}(t)\|\leq c_{7}\sqrt{n}$ by
(19). Hence

$\displaystyle\Lambda^{*}(t+1)-\Lambda^{*}(t)$ $\displaystyle=$
$\displaystyle-\frac{8\eta\lambda_{1}}{mn^{2}}\left({\bm{F}}(t)^{\top}{\bm{D}}(t)+({\bm{F}}(t)^{\top}{\bm{v}}_{1})({\bm{D}}(t)^{\top}{\bm{v}}_{1})-\frac{\eta}{2}({\bm{D}}(t)^{\top}{\bm{v}}_{1})^{2}\Lambda^{*}(t)\right.$
$\displaystyle\left.-\frac{\eta}{2}{\bm{R}}(t)^{\top}\bm{\Gamma}(t){\bm{R}}(t)-\eta{\bm{R}}(t)^{\top}\bm{\Gamma}(t)\left({\bm{v}}_{1}{\bm{v}}_{1}^{\top}{\bm{D}}(t)\right)-{\bm{R}}(t)^{\top}\left(\frac{m}{d}\mathbf{X}^{\top}\mathbf{X}\right){\bm{R}}(t)\frac{\eta}{mn}\right)$
$\displaystyle\leq$
$\displaystyle-\frac{8\eta\lambda{1}}{mn^{2}}\left(2\beta({\bm{D}}(t)^{\top}{\bm{v}}_{1})^{2}+\|{\bm{R}}(t)\|^{2}-\frac{\eta
c_{2}}{2m}\|{\bm{R}}(t)\|^{2}\right.$
$\displaystyle\left.-\frac{c_{2}\eta}{m}\|{\bm{R}}(t)\|\cdot\|{\bm{D}}(t)\|-\frac{\eta\lambda_{1}}{dn}\|{\bm{R}}(t)\|^{2}-2\|\bm{Y}\|\cdot\|{\bm{D}}(t)\|\right)$
$\displaystyle\leq$
$\displaystyle-\frac{8\eta\lambda_{1}}{mn^{2}}\left(2\beta({\bm{D}}(t)^{\top}{\bm{v}}_{1})^{2}+\|{\bm{R}}(t)\|^{2}(1-\frac{c_{2}\eta}{2m})\right.$
$\displaystyle\left.-\frac{c_{2}\eta}{m}\|{\bm{R}}(t)\|\cdot(\|{\bm{R}}(t)\|+|{\bm{D}}(t)^{\top}{\bm{v}}_{1}|)-\frac{\eta\lambda_{1}}{dn}\|{\bm{R}}(t)\|^{2}-2\|\bm{Y}\|\cdot(\|{\bm{R}}(t)\|+|{\bm{D}}(t)^{\top}{\bm{v}}_{1}|)\right)$
$\displaystyle\leq$
$\displaystyle-\frac{8\eta\lambda_{1}}{mn^{2}}\left(2\beta\left({\bm{D}}(t)^{\top}{{\bm{v}}_{1}}\right)^{2}-(\frac{\eta
c_{7}c_{2}\sqrt{n}}{m}+2\sqrt{n})\cdot|{\bm{D}}(t)^{\top}{\bm{v}}_{1}|\right.$
$\displaystyle\left.+c_{7}^{2}n(1-\frac{c_{2}\eta}{2m}-\frac{c_{2}\eta}{m}-\frac{\eta\lambda_{1}}{dn})-2c_{7}n\right)$
$\displaystyle=$
$\displaystyle-\frac{8\eta\lambda_{1}}{mn^{2}}\left(2\beta({\bm{D}}(t)^{\top}{\bm{v}}_{1})^{2}-c_{10}\left({\bm{D}}(t)^{\top}{{\bm{v}}_{1}}\right)+c_{11}\right)$

Here $c_{10}:=\eta
c_{7}\sqrt{n}\cdot\frac{c_{2}}{m}+2\sqrt{n}=\Theta(\sqrt{n})$,
$c_{11}:=c_{7}^{2}n\left(1-\frac{c_{2}\eta}{2m}-\frac{c_{2}\eta}{m}-\frac{\eta\lambda_{1}}{dn}\right)-2c_{7}n=Nn)$,
and the first inequality holds because of Assumption C.5, Assumption C.3 and
$\|{\bm{D}}(t)\|^{2}=({\bm{D}}(t)^{\top}{\bm{v}}_{1})^{2}+\|{\bm{R}}(t)\|^{2}$,
the second inequality holds because of
$\|{\bm{D}}(t)\|\leq|{\bm{D}}(t)^{\top}{\bm{v}}_{1}|+\|{\bm{R}}(t)\|$, and the
third inequality follows from the upper bound (19) of $\|{\bm{R}}(t)\|$.

Note that it is a quadratic function of ${\bm{D}}(t)^{\top}{\bm{v}}_{1}$.
Hence if
${\bm{D}}(t)^{\top}{\bm{v}}_{1}>\frac{|c_{10}|}{2\beta}+\sqrt{\frac{|c_{11}|}{2\beta}}$,
we have

$\Lambda^{*}(t+1)-\Lambda^{*}(t)<-\frac{8\eta\lambda_{1}}{n^{2}m}\cdot\frac{|c_{10}|\sqrt{|c_{11}|}}{2\beta}=\Theta(\frac{\eta}{m})$

Hence we finish the proof. ∎

Now we can prove the final part (the first conclusion) of Theorem 4.

######  Lemma C.13.

Let $\rho$ be the one defined in Theorem C.11. If
$\Lambda(t_{0})>\frac{2}{\eta}(1+\rho)$ for some $t_{0}$, there exists some
$t_{1}>t_{0}$ such that $\Lambda(t_{1})<\frac{2}{\eta}(1+\rho)$.

###### Proof.

Otherwise, for any $t>t_{0}$, $\Lambda(t)>\frac{2}{\eta}(1+\rho)$. Then by
Theorem C.11, ${\bm{D}}(t)^{\top}{\bm{v}}_{1}$ increases geometrically, hence
there exists $t_{2}>t_{0}$, such that
${\bm{D}}(t)^{\top}{\bm{v}}_{1}>c_{8}\sqrt{n}$. Now by Lemma C.12, each
iteration $\Lambda^{*}(t)$ will decrease by at least a fixed amount. Hence
there must exist a time $t_{3}>t_{0}$ such that
$\Lambda^{*}(t_{3})<\frac{2}{\eta}-2c_{2}/m$. Then by Corollary C.2, we get a
contradiction. ∎

###  C.4 Our Results and the NTK Regime

In this subsection, we explain why our results (Theorem 3, Theorem 4) are
sufficiently different from the quadratic setting (e.g., linear regression) or
the recent convergence analysis in NTK setting.

A key requirement in the convergence analysis in the NTK regime is that the
learning rate is very small and the GD trajectory almost tracks the gradient
flow, hence converges to the global minimum. However, we consider typical
learning rate used in practice, which can be much larger. In particular,
$\eta>2/\Lambda$ can happen in our setting, which causes instability (i.e.,
such as the growth of loss in Lemma C.11) along the training trajectory. Such
instability cannot be captured by any existing convergence analysis in NTK
regime at all. Hence, all existing NTK convergence results do not directly
apply here.

Equally importantly, we find that even when ${\bm{W}}(t)$ changes slightly
(several orders of magnitude smaller than its initialization), PS and EOS
still happen with a not so small learning rate $\eta$. To support our claim,
we include the experimental results in Appendix D.2.3. In Figure 22, we can
see that the initialization ${\bm{W}}(0)$ is much larger than the change of
${\bm{W}}(t)$ and the norm of ${\bm{W}}(t)$ grows larger when $m$ becomes
larger. However, we still observe that PS and EOS occur in this setting.
Hence, the setting we study in this paper and our results are intrinsically
different from the quadratic setting (in which case EOS cannot happen).

Last, in our proofs in Section C.2 and C.3, our current bound requires that
$m=\Omega(n^{2})$ and we also assume $\lambda_{r}=\Omega(1)$. This may create
an impression that we need a very wide network which operates in the NTK
regime. However, we remark that if our analysis can be tightened to $m=O(n)$,
one can formally prove that $\|{\bm{A}}(t)\|$ can actually change
significantly ($\|{\bm{A}}(t)\|^{2}-\|{\bm{A}}(0)\|^{2}$) has the same scale
as the initialization $\|{\bm{A}}(0)\|^{2}$), resulting a significant change
of sharpness as well, hence beyond the NTK regime. For example, in the proof
of EOS (Section C.3), we prove a loose $O(\sqrt{mn})$ upper bound of
$\|{\bm{D}}(t)\|$ (Lemma C.9). However by Lemma C.12, when $\|{\bm{D}}(t)\|$
reaches $O(\sqrt{n})$, the sharpness starts dropping quickly. So if a better
upper bound of $\|{\bm{D}}(t)\|=O(\sqrt{n})$ can be proven (this is true
empirically for all of our experiments), the width $m$ can be set to
$\Theta(n)$, and this suffices to implies a significant change of
$\|{\bm{A}}(t)\|^{2}$. We leave these improvements as future directions.

##  Appendix D Verification for Assumptions

In this section, we first justify the assumptions we made in Section 3 and
Section 4 empirically. Then we present the experiment described in Section 5.

###  D.1 Assumptions in Section 3

In this subsection, we conduct experiments to verify the assumptions in
Section 3. The detailed experiment settings can be found in Appendix A.

####  D.1.1 $\mathbf{M}_{A}$ has small eigenvalues

In Section 3.2, we mentioned that the largest eigenvalue of $\bm{M_{A}}\
:=(\frac{\partial\bm{F}}{\partial\bm{A}})(\frac{\partial\bm{F}}{\partial\bm{A}})^{\top}$
is much smaller than the sharpness. We verify this assumption under different
settings in Figure 13, including a fully-connected linear network, a fully-
connected network with tanh activation and a convolutional one. Observe that
$\|\bm{M_{A}}\|$ (the blue curve) is very close to 0 and hardly increases
during the training process along the whole trajectory.

(a) Fully-connected Linear Network (b) Fully-connected tanh Network (c)
Convolutional tanh Network

Figure 13: In this figure, we show that $\|\bm{M_{A}}\|$ is much smaller than
the sharpness. Note that $\|\bm{M_{A}}\|$ (the blue curve) is very close to 0
and hardly increases during the training process along the whole trajectory.
The sharpness (the steel-blue curve) strictly dominates $\|\bm{M_{A}}\|$ for
all time. The detailed experiment settings can be found in Appendix A.

####  D.1.2 Assumption 3.7

In this assumption, we assume that there is a large gap between the largest
and the second largest eigenvalue, and thus the second largest eigenvalue is
always below $1/\eta$. We verify the outlier assumption by calculating the
largest and the second largest eigenvalue of $\bm{M}(t)$. In Sagun et al. [28,
29], the sharpness is much larger than the largest eigenvalue in the bulk (the
$(K+1)$-th largest eigenvalue of ${\bm{M}}$ where $K$ is the number of
classes). In our binary setting $K=1$. In Figure 16, we show that the largest
eigenvalue indeed dominates the second one, and the second one never reaches
$1/\eta$, which verifies Assumption 3.7.

(a) Fully-connected linear network (b) Fully-connected tanh network (c)
Convolutional network with ELU activation

Figure 14: The second largest eigenvalue (the orange curve) of $\bm{M}$ is
much smaller than the sharpness (the steel-blue curve). Also, the second
largest eigenvalue never reaches $2/\eta$.

####  D.1.3 Assumption 3.2 (First Order Approximation of GD)

In Assumption 3.2, we assume the gradient descent trajectory is close to the
first order approximation. To verify that the first order term is indeed
dominant along the trajectory, for both the residual ${\bm{D}}(t)$ and the
output layer norm $\|{\bm{A}}(t)\|^{2}$, we plot the norms of the actual GD
update, the first order approximation order approximation and the higher order
terms of the update rule in Figure 15. Observe that in the progressive
sharpening phase, the first order approximation is almost the same as the
actual gradient update; while in the EOS phase, the first order approximation
is still close to the actual gradient most of the time. We can see that the
norm of the higher order terms spikes occasionally, but when this happens the
first order term spikes much higher.

(a) Linear network (b) Fully connected tanh network

Figure 15: This figure shows the norm of the full gradient
$\|{\bm{D}}(t+1)-{\bm{D}}(t)\|$, the first order approximation
$\|\eta{\bm{M}}(t){\bm{D}}(t)\|$ and the higher order terms
$\|{\bm{D}}(t+1)-{\bm{D}}(t)+\eta{\bm{M}}(t){\bm{D}}(t)\|$ in the training
process. Observe that in both the $\|{\bm{A}}(t)\|^{2}$ and ${\bm{D}}(t)$
dynamics, the first order approximation (the blue curve) almost overlaps with
the actual update (the green curve) in the PS phase. While in the EOS phase,
though the norm of the higher order terms (the orange curve) spikes, the first
order approximation is still close to the actual update.

####  D.1.4 Assumption 3.3 (Gradient flow for the PS phase)

In Assumption 3.3, we assume that in the progressive sharpening phase, the
gradient descent trajectory is close to the gradient flow trajectory. We refer
to Appendix J in Cohen et al. [6] for more experiments about this claim. Here
for readers’ convenience, we duplicate their Figure 29 in Appendix J as Figure
16.

Figure 16: Left: the picture shows the $\ell_{2}$ distance between the
gradient flow trajectory at $t$ iteration and the gradient descent trajectory
at $t/\eta$ iteration. The vertical dotted line is the time when the sharpness
reaches $2/\eta$. Right: the plot of sharpness where (iteration $\times$
learning rate) is on the x-axis.

####  D.1.5 Assumption 3.5 (iii) (principal directions moves slowly)

In Figure 17 we verify Assumption 3.5 (iii) and as well as the discussion
after Assumption 3.5 (i). In general models, we find that the eigenvectors
corresponding to small eigenvalues may change drastically. But for the largest
eigenvector, it indeed changes slowly from the initialized direction. In
Figure 17, we can see that over a long training time the similarity of
${\bm{v}}_{1}(t)$ with its initialization is still larger than at least 0.98.
Mulayoff et al. [24] also proved that near the minima, the top eigenvectors of
the Hessian matrices tend to align. That is, the directions of these top
eigenvectors are approximately parallel. This fact also corroborates our
assumption near the minima.

(a) Fully-connected linear network (b) Fully-connected tanh network (c)
Convolutional network with ELU activation

Figure 17: In this figure, we show that under various architectures, the first
eigenvector of $\bm{M}$ changes slowly throughout the training process, even
when Edge of Stability phenomenon occurs.

###  D.2 Assumptions in Section 4

In this subsection, we present the assumptions in Section 4, and conduct
experiments to verify them. We add a scale coefficient $\frac{1}{\sqrt{m}}$ in
the linear network to be consistent with the settings of theoretical analysis.

####  D.2.1 Assumption 4.1

In Assumption 4.1, we assume the ratio $\lambda_{i}/\lambda_{i+1}$ between the
two adjacent eigenvalues of $\mathbf{X}^{\top}\mathbf{X}$ is bounded by a
small constant. In the 1000-example subset of CIFAR-10, we verify this
assumption by experiments. We plot the eigenvalues and their ratio in Figure
18. It shows that Assumption 4.1 holds and the constant $\chi\approx 38$,
since almost all the ratios are close to 1, and the largest ratio is
$\lambda_{1}/\lambda_{2}\approx 38$.

(a) The eigenvalue spectrum (log scale) (b) The ratio between $\lambda_{i}$
and $\lambda_{i+1}$

Figure 18: (a): The full eigenvalue spectrum of of
$\mathbf{X}^{\top}\mathbf{X}$. Observe that the maximal ratio
$\max\\{\lambda_{i}/\lambda_{i+1}\\}=\lambda_{1}/\lambda_{2}$. (b): The ratio
between two adjacent eigenvalues $\lambda_{i}/\lambda_{i+1}$, $i\geq 2$. We
exclude the largest eigenvalue to make the figure clearer.

If we further consider a mean-subtracted version of this subset of CIFAR-10
(See Figure 19), we can reduce the ratio to $\chi\approx 3$.

(a) The eigenvalue spectrum (log scale) (b) The ratio between $\lambda_{i}$
and $\lambda_{i+1}$

Figure 19: (a): The full eigenvalue spectrum of of
$\mathbf{X}^{\top}\mathbf{X}$ when samples’ mean is subtracted. (b): the ratio
between two adjacent eigenvalues $\lambda_{i}/\lambda_{i+1}$. In Figure (b),
observe that the maximal ratio
$\max\\{\lambda_{i}/\lambda_{i+1}\\}=\lambda_{1}/\lambda_{2}\approx 3$.
Remark. Note we should exclude the minimal eigenvalue if the mean of examples
is subtracted, because when we subtract the mean from the dataset, it cannot
be full rank. The minimal eigenvalue of $\mathbf{X}^{\top}\mathbf{X}$ is 0,
thus it is unnecessary to check it for our assumption.

####  D.2.2 Assumption 4.3

In Appendix C.2, by Theorem 3 we prove that $\|\bm{\Gamma}(t)\|$ is bounded by
$R_{w}=O(1/m)$ in the progressive sharpening phase. When gradient descent
enters EOS, the proof does not hold and we make this bound into an assumption
(Assumption 4.3). We empirically verify that the bound can only increase by a
constant factor (despite some spikes in EOS). See Figure 20. In this figure
$\|\bm{\Gamma}(t)\|\leq\frac{24}{m}$ with $m=40,80,160,200$.

(a) The sharpness, $m=40,80,160,200$

(b) $\|\bm{\Gamma}(t)\|$, $m=40,80,160,200$

Figure 20: In this figure, we show that even when GD enters EOS, the bound of
$\|\bm{\Gamma}(t)\|$ is still $\Theta(1/m)$ along the whole trajectory. The
corresponding constant $c_{2}\approx 24$.

Actually there are two interesting empirical facts related to
$\|\bm{\Gamma}(t)\|$. One is the noticeable fact that $\|\bm{\Gamma}(t)\|$
spikes, the other is that the values of $\|\bm{\Gamma}(t)\|$ are overall quite
small (despite the fact that $\bm{W}$ changes non-trivially in our
experiments) and decreases as $m$ becomes larger. Our assumption tries to
model the second fact (see Figure 20, $\|\bm{\Gamma}(t)\|$ (despite the
spikes) decreases as the width $m$ grows, and the largest $\|\bm{\Gamma}(t)\|$
is almost $24/m$ in all these experiments). However, we admit that our results
do not reflect the first fact (the spikes of $\|\bm{\Gamma}(t)\|$ ), and it is
an interesting fact that is worth investigating. We have strong intuition that
$\|\bm{\Gamma}(t)\|$ only grows by at most a constant factor, but currently do
not have a formal proof yet. Nevertheless, the spiking behavior does not
directly contradict our assumption.

Remark: Note that Assumption 4.3 is not equivalent to a small movement of
${\bm{W}}(t)$. Actually, in the experiments above ($m=40,80,160,200$) the
movement of ${\bm{W}}(t)$ is quite significant compared to the norm of
${\bm{W}}(0)$ at initialization. See Figure 21.

(a) ${\bm{W}}(t)\&\|\Delta{\bm{W}}(t)\|$, $m=40$ (b)
${\bm{W}}(t)\&\|\Delta{\bm{W}}(t)\|$, $m=80$ (c)
${\bm{W}}(t)\&\|\Delta{\bm{W}}(t)\|$, $m=160$ (d)
${\bm{W}}(t)\&\|\Delta{\bm{W}}(t)\|$, $m=200$

Figure 21: In this figure, we show that even the $\bm{\Gamma}(t)$ is small and
bounded, the movement $\|\Delta{\bm{W}}(t)\|:=\|{\bm{W}}(t)-{\bm{W}}(0)\|$
(the dark orange curve) is close to $\|{\bm{W}}(t)\|$ (the blue curve),
implying that ${\bm{W}}(t)$ moves considerably.

####  D.2.3 Comparison with the NTK regime: the non-quadratic property

Here we illustrate why our setting and results are sufficiently different from
the quadratic setting (e.g., linear regression) or the recent convergence
analysis in NTK setting. In particular, we show that even when the movement of
${\bm{W}}(t)$ is comparably negligible compared to the initialization
${\bm{W}}(0)$, EOS can still happen. Here we take a larger initialization of
${\bm{W}}(0)$, which is ten times of the standard initialization in order to
dwarf the movement of ${\bm{W}}(t)$. The widths are $m=1000,2000,4000,8000$.
We can see that the initialization ${\bm{W}}(0)$ is much larger than the
change of ${\bm{W}}(t)$ and the norm of ${\bm{W}}(t)$ grows larger when $m$
becomes larger. See Figure 22. Detailed comparison is in Appendix C.4.

(a) The sharpness,
$m=1000(\eta=2/54),2000(\eta=2/52),4000(\eta=2/53),8000(\eta=2/52)$

(b) The loss, $m=1000,2000,4000,8000$

(c) ${\bm{W}}(t)\&\|\Delta{\bm{W}}(t)\|$, $m=1000,2000,4000,8000$

Figure 22: In this figure, we show that even when ${\bm{W}}(t)$ stays close to
its initialization, EOS can still happen. In particular, Figure (c) shows the
$\|{\bm{W}}(t)\|$ (the blue curve) and $\|{\bm{W}}(t)-{\bm{W}}(0)\|$ (the
orange curve). Here for $m=1000,2000,4000,8000$, observe that the EOS still
happens when $\|{\bm{W}}(t)\|/\|{\bm{W}}(t)-{\bm{W}}(0)\|$ > 10\. That
indicates the intrinsic non-quadratic property of neural networks in the EOS
regime.

###  D.3 Experiments in Section 5

In this subsection we show some empirical results that may reveal some
interesting relation between the inner layers and the sharpness, which is not
yet reflected in our theory. Our experimental results show that all layers
seem to work together to influence the sharpness, and contribute to the
progressive sharpening and edge of stability phenomena. In our experiment,
while the sharpness is still calculated by the gradient of all parameters, we
freeze some of the layers in the training process. The experimental results
show that the more layers we freeze, the slower progressive sharpening happens
and the weaker the oscillation of the sharpness is (See Figure 23, Figure 24).
This indicates that layers other than the output layer has nontrivial
influence on the sharpness, but since different layers seem to work in the
same direction, further justifying our assumption that $\|{\bm{A}}\|$ is
positively related with the sharpness.

Fully-connected tanh Network:

Figure 23: We conduct the experiment on a 5-layer tanh fully-connected
network. Four lines in the plot show the sharpness for four independent
training processes but with 0,1,2,3 outer layers locked. All other hyper-
parameters are the same. The result shows that all layers have cooperative
effect on the sharpness.

Fully-connected Linear Network:

(a) Fully-connected linear network 0 layer frozen (b) Fully-connected linear
network 1 layer frozen (c) Fully-connected linear network 2 layers frozen (d)
Fully-connected linear network 3 layers frozen

Figure 24: The sharpness after 0,1,2,3 outer layers are locked. Details refer
to Figure 23.

##  Appendix E Missing proofs

###  E.1 Proofs in Section 3

In this section, we provide the missing proofs in Section 3.

######  Lemma E.1.

(Lemma 3.1) For all $t$ in Phase I, under Assumption 3.5 (i) and 3.3, it holds
that ${\bm{D}}(t)^{\top}{\bm{F}}(t)<0$.

###### Proof.

Consider the inner product ${\bm{D}}(t)^{\top}\bm{v}_{i}$. Recall $\bm{v}_{i}$
is the $i$-th eigenvector of ${\bm{M}}$. By Assumption 3.5(i), $\bm{v}_{i}$
does not change with $t$. By Assumption 3.3, we have

$\frac{\mathrm{d}{\bm{D}}(t)^{\top}\bm{v}_{i}}{\mathrm{d}t}=-{\bm{D}}(t)^{\top}{\bm{M}}(t)\bm{v}_{i}=-\lambda_{i}(t){\bm{D}}(t)^{\top}\bm{v}_{i}$

where $\lambda_{i}(t)\geq 0$ is the corresponding eigenvalue of $\bm{v}_{i}$.

Since ${\bm{F}}(0)=0$, ${\bm{D}}(0)={\bm{F}}(0)-{\bm{Y}}=-{\bm{Y}}.$ Then the
differential equation has the solution

${\bm{D}}(t)^{\top}{\bm{v}}_{i}=e^{-\int_{0}^{t}\lambda_{i}(t)\mathrm{d}t}\cdot{\bm{D}}(0)^{\top}{\bm{v}}_{i}=-e^{-\int_{0}^{t}\lambda_{i}(t)\mathrm{d}t}\cdot{\bm{Y}}^{\top}{\bm{v}}_{i}$

Plug it into the expression
${\bm{D}}(t)^{\top}{\bm{F}}(t)={\bm{D}}(t)^{\top}({\bm{D}}(t)+{\bm{Y}})$ and
we have:

${\bm{D}}(t)^{\top}{\bm{F}}(t)=\sum_{i=1}^{n}{\bm{D}}(t)^{\top}{\bm{v}}_{i}({\bm{D}}(t)^{\top}{\bm{v}}_{i}+{\bm{Y}}^{\top}{\bm{v}}_{i})=-\sum_{i=1}^{n}({\bm{Y}}^{\top}{\bm{v}}_{i})^{2}e^{-\int_{0}^{t}\lambda_{i}(t)\mathrm{d}t}(1-e^{-\int_{0}^{t}\lambda_{i}(t)\mathrm{d}t})$

since
$({\bm{Y}}^{\top}{\bm{v}}_{i})^{2}e^{-\int_{0}^{t}\lambda_{i}(t)\mathrm{d}t}(1-e^{-\int_{0}^{t}\lambda_{i}(t)\mathrm{d}t})>0$
for all $i\in[n]$, ${\bm{D}}(t)^{\top}{\bm{F}}(t)<0$. ∎

######  Lemma E.2.

(Lemma 3.2) Suppose Assumption 3.5 (iii) and 3.6 hold during this phase (with
constants $\epsilon_{2}>0$ and $c>1$). If $\Lambda(t)=(2+\tau)/\eta$ and
$\tau>\frac{1}{1-\epsilon_{2}-1/c}-1$, then $\bm{D}(t)^{\top}\bm{v}_{1}(t)$
increases geometrically with factor $(1+\tau)(1-\epsilon_{2}-1/c)>1$ for
$t\geq t_{0}$ in this phase.

###### Proof.

First by (3), we have
$\bm{D}(t+1)^{\top}\bm{v}_{1}(t)=\bm{D}(t)^{\top}(\bm{I}-\eta\bm{M}(t))\bm{v}_{1}(t)=(1-\eta\Lambda(t))\bm{D}(t)^{\top}\bm{v}_{1}(t)$.

Then we have

$\displaystyle|\bm{D}(t+1)^{\top}\bm{v}_{1}(t+1)|$
$\displaystyle\geq|\bm{D}(t+1)^{\top}\bm{v}_{1}(t)(1-\epsilon_{2})|-\epsilon_{2}\|\bm{D}(t+1)\|$
$\displaystyle\geq|\bm{D}(t)^{\top}\bm{v}_{1}(t)|(1-\epsilon_{2})(\eta\Lambda(t)-1)-(\eta\Lambda(t)-1)\epsilon_{2}\|\bm{D}(t)\|$
$\displaystyle\geq|\bm{D}(t)^{\top}\bm{v}_{1}(t)|(1-\epsilon_{2})(\eta\Lambda(t)-1)-(\eta\Lambda(t)-1)|\bm{D}(t)^{\top}\bm{v}_{1}(t)|/c$
$\displaystyle=|\bm{D}(t)^{\top}\bm{v}_{1}(t)|(\eta\Lambda(t)-1)(1-\epsilon_{2}-1/c)$
$\displaystyle=|\bm{D}(t)^{\top}\bm{v}_{1}(t)|(1+\tau)(1-\epsilon_{2}-1/c)$

where first inequality holds due to Assumption 3.5 (iii) and the third follows
from Assumption 3.6. ∎

######  Proposition E.1.

(Proposition 3.1) If $\|\bm{D}(t)\|>\|\bm{Y}\|$, then
$\bm{D}(t)^{\top}\bm{F}(t)>0$.

###### Proof.

This proposition can be proved by simply noticing that
$\bm{D}(t)^{\top}\bm{F}(t)=\bm{D}(t)^{\top}(\bm{D}(t)-\bm{Y}(t))\geq\|\bm{D}\|^{2}-\|\bm{D}\|\|\bm{Y}\|>0$
when $\|\bm{D}(t)\|\geq\|\bm{Y}\|$. ∎

######  Proposition E.2.

(Proposition 3.2) Under Assumption 3.2, if $\|{\bm{D}}(t)\|>\|{\bm{Y}}\|$,
then
$\|\bm{A}(t+1)\|^{2}-\|\bm{A}(t)\|^{2}<-\frac{4\eta}{n}(\|{\bm{D}}(t)\|-\|{\bm{Y}}\|)^{2}$.

###### Proof.

Use Assumption 3.2 and notice that
${\bm{D}}(t)^{\top}{\bm{F}}(t)\geq\|{\bm{D}}(t)\|^{2}-\|{\bm{D}}(t)\|\|{\bm{Y}}\|>(\|{\bm{D}}(t)\|-\|{\bm{Y}}\|)^{2}$.
∎

######  Lemma E.3.

(Lemma 3.3) If $\Lambda(t)<2/\eta$, then for any vector
$\bm{u}\in\mathbb{R}^{n}$,
$\|\bm{u}^{\top}(\bm{I}-\eta{\bm{M}}(t))\|\leq(1-\eta\alpha)\|\bm{u}\|$, where
$\alpha=\min\\{2/\eta-\Lambda(t),\lambda_{\min}({\bm{M}}(t))\\}$. In
particular, replacing $\bm{u}$ with ${\bm{D}}(t)$, we can see
$\|{\bm{D}}(t+1)\|\leq(1-\eta\alpha)^{2}\|{\bm{D}}(t)\|$.

###### Proof.

For any vector $\bm{u}\in\mathbb{R}^{n}$,

$\displaystyle\|\bm{u}^{\top}(\bm{I}-\eta{\bm{M}}(t))\|^{2}$
$\displaystyle=\sum_{i=1}^{n}\|(\bm{u}^{\top}{\bm{v}}_{i}(t)){\bm{v}}_{i}(t)^{\top}(\bm{I}-\eta{\bm{M}}(t))\|^{2}$
$\displaystyle=\sum_{i=1}^{n}(1-\eta\lambda_{i})^{2}(\bm{u}^{\top}{\bm{v}}_{i}(t))^{2}\leq(1-\eta\alpha)^{2}\sum_{i=1}^{n}(\bm{u}^{\top}{\bm{v}}_{i}(t))^{2}=(1-\eta\alpha)^{2}\|\bm{u}\|^{2}.$

Then the second statement is due to Assumption 3.2. ∎

######  Lemma E.4.

(Lemma 3.4) Suppose Assumption 3.5 (iii) holds. $\bm{R}(t)$ satisfies the
following:

$\bm{R}(t+1)=(I-\eta\bm{M}(t))\bm{R}(t)+\bm{e}_{1}(t),\quad\text{where}\quad\|\bm{e}_{1}(t)\|\leq
6\sqrt{\epsilon_{2}}\|\bm{D}(t)\|(B_{\Lambda}-1)$

###### Proof.

We consider the update rule for $\bm{R}(t)$:

$\displaystyle\bm{R}(t+1)={}$
$\displaystyle(\bm{I}-\bm{v}_{1}(t+1)\bm{v}_{1}(t+1)^{\top})(\bm{I}-\eta\bm{M}(t))\bm{D}(t)$
$\displaystyle={}$
$\displaystyle(\bm{I}-\eta\bm{M}(t))\bm{R}(t)-(\bm{v}_{1}(t+1)\bm{v}_{1}(t+1)^{\top})(\bm{I}-\eta\bm{M}(t))(\bm{I}-\bm{v}_{1}(t)\bm{v}_{1}(t)^{\top})\bm{D}(t)$
$\displaystyle+(\bm{I}-\bm{v}_{1}(t+1)\bm{v}_{1}(t+1)^{\top})(\bm{I}-\eta\bm{M}(t))(\bm{v}_{1}(t)\bm{v}_{1}(t)^{\top})\bm{D}(t)$
$\displaystyle={}$
$\displaystyle(\bm{I}-\eta\bm{M}(t))\bm{R}(t)-(1-\eta\Lambda(t))(\bm{v}_{1}(t+1)\bm{v}_{1}(t+1)^{\top})(\bm{I}-\bm{v}_{1}(t)\bm{v}_{1}(t)^{\top})\bm{D}(t)$
$\displaystyle+(1-\eta\Lambda(t))(\bm{I}-\bm{v}_{1}(t+1)\bm{v}_{1}(t+1)^{\top})(\bm{v}_{1}(t)\bm{v}_{1}(t)^{\top})\bm{D}(t)$

Now if we decompose
$\bm{v}_{1}(t+1)=(1-\delta(t))\bm{v}_{1}(t)+\sqrt{1-(1-\delta)^{2}}\bm{v}_{\perp}(t)$,
where $\langle{\bm{v}}_{1}(t),{\bm{v}}_{\perp}\rangle=0$. Then we have

$\displaystyle\|(\bm{I}-\bm{v}_{1}(t+1)\bm{v}_{1}(t+1)^{\top})\bm{v}_{1}(t)\bm{v}_{1}(t)^{\top}\|$
$\displaystyle={}$
$\displaystyle\|\bm{v}_{1}(t)-(\bm{v}_{1}(t)^{\top}\bm{v}_{1}(t+1))\bm{v}_{1}(t+1)\|$
$\displaystyle={}$
$\displaystyle\|(1-(1-\delta(t))^{2})\bm{v}_{1}(t)+\sqrt{1-(1-\delta(t)^{2})}\bm{v}_{\perp}(t)\|$
$\displaystyle\leq{}$
$\displaystyle\sqrt{(2\delta(t)-\delta(t)^{2})(1-\delta(t))+(2\delta(t)-\delta(t)^{2})^{2}}$
$\displaystyle\leq{}$ $\displaystyle\sqrt{2\delta(t)+4\delta(t)^{2}}$
$\displaystyle\leq{}$ $\displaystyle 3\sqrt{\delta(t)}$ $\displaystyle\leq{}$
$\displaystyle 3\sqrt{\epsilon_{2}}.$

Similar result can be obtained for the term
$(\bm{v}_{1}(t+1)\bm{v}_{1}(t+1)^{\top})(\bm{I}-\bm{v}_{1}(t)\bm{v}_{1}(t)^{\top})$.

Therefore,
$\|(\eta\Lambda(t)-1)(I-\bm{v}_{1}(t+1)\bm{v}_{1}(t+1)^{\top})(\bm{v}_{1}(t)\bm{v}_{1}(t)^{\top})\bm{D}(t)\|\leq
6\sqrt{\epsilon_{2}}(B_{\Lambda}-1)B_{D}.$ ∎

######  Lemma E.5.

(Lemma 3.5) Define an auxiliary sequence $\bm{R}^{\prime}(t)$ by
$\bm{R}^{\prime}(0)=\bm{R}(0)$, and
$\bm{R}^{\prime}(t+1)=(\bm{I}-\eta\bm{M}(t)(\bm{I}-{\bm{v}}_{1}(t){\bm{v}}_{1}(t)^{\top}))\bm{R}^{\prime}(t)$.
If Assumption 3.4, Assumption 3.5 (iii), Assumption 3.7 hold, and for any time
$t$ there exists a quantity $\lambda_{r}>0$, such that the smallest eigenvalue
of ${\bm{M}}(t)$, i.e. $\lambda_{\min}({\bm{M}}(t))>\lambda_{r}$, then there
exists a constant $c_{r}>0$ such that $\|\bm{R}(t)-\bm{R}^{\prime}(t)\|\leq
c_{r}\frac{B_{D}(B_{\Lambda}-1)\sqrt{\epsilon_{2}}}{\eta\lambda_{r}}$.

###### Proof.

First we can see that the eigenvalues of
${\bm{M}}(t)(\bm{I}-{\bm{v}}_{1}(t){\bm{v}}_{1}(t)^{\top})$ are all the
eigenvalues of ${\bm{M}}$ except the largest one. Hence with Assumption 3.7,
all eigenvalues of ${\bm{M}}(t)(\bm{I}-{\bm{v}}_{1}(t){\bm{v}}_{1}(t)^{\top})$
are in $(\lambda_{r},1/\eta)$. Thus
$\|\bm{I}-\eta{\bm{M}}(t)(\bm{I}-{\bm{v}}_{1}(t){\bm{v}}_{1}(t)^{\top})\|\leq
1-\eta\lambda_{r}$.

Hence by Assumption 3.4 we can get

$\displaystyle\|\bm{R}(t+1)-\bm{R}^{\prime}(t+1)\|$ $\displaystyle={}$
$\displaystyle\|(\bm{I}-\eta{\bm{M}}(t))\bm{R}(t)-(\bm{I}-\eta\bm{M}(t)(\bm{I}-{\bm{v}}_{1}(t){\bm{v}}_{1}(t)^{\top}))\bm{R}^{\prime}(t)+\bm{e}_{1}(t)\|$
$\displaystyle={}$
$\displaystyle\|(\bm{I}-\eta{\bm{M}}(t)(\bm{I}-{\bm{v}}_{1}(t){\bm{v}}_{1}(t)^{\top}))(\bm{R}(t)-\bm{R}^{\prime}(t))+\bm{e}_{1}(t)\|$
$\displaystyle\leq{}$
$\displaystyle\|(\bm{I}-\eta{\bm{M}}(t)(\bm{I}-{\bm{v}}_{1}(t){\bm{v}}_{1}(t)^{\top}))(\bm{R}(t)-\bm{R}^{\prime}(t))\|+\|\bm{e}_{1}(t)\|$
$\displaystyle\leq{}$
$\displaystyle\|\bm{I}-\eta{\bm{M}}(t)(\bm{I}-{\bm{v}}_{1}(t){\bm{v}}_{1}(t)^{\top})\|\|\bm{R}(t)-\bm{R}^{\prime}(t)\|+\|\bm{e}_{1}(t)\|$
$\displaystyle\leq{}$
$\displaystyle\|\bm{R}(t)-\bm{R}^{\prime}(t)\|(1-\eta\lambda_{r})+3B_{D}(B_{\Lambda}-1)\sqrt{\epsilon_{2}}.$

Thus if we denote
$\|\bm{R}(t)-\bm{R}^{\prime}(t)\|-\frac{3B_{D}(B_{\Lambda}-1)\sqrt{\epsilon_{2}}}{\eta\lambda_{r}}$
by $p(t)$, and replace $\|\bm{R}(t)-\bm{R}^{\prime}(t)\|$ in the inequality
above by
$p(t)+\frac{3B_{D}(B_{\Lambda}-1)\sqrt{\epsilon_{2}}}{\eta\lambda_{r}}$, we
can get $|p(t+1)|\leq|p(t)|(1-\eta\lambda_{r})$. Hence, we can see that
$|p(t)|<|p(0)|=\frac{3B_{D}(B_{\Lambda}-1)\sqrt{\epsilon_{2}}}{\eta\lambda_{r}}$
for any time $t$. Therefore, we obtain that

$\|\bm{R}(t)-\bm{R}^{\prime}(t)\|<\frac{3B_{D}(B_{\Lambda}-1)\sqrt{\epsilon_{2}}}{{\eta\lambda_{r}}}+|p(0)|<\frac{6B_{D}(B_{\Lambda}-1)\sqrt{\epsilon_{2}}}{\eta\lambda_{r}}.$

Taking $c_{r}=6$, we finish the proof. ∎

######  Lemma E.6.

For all $t$ in Phase I, under Assumption 3.5 (i) and Assumption 3.7, it holds
that ${\bm{R}}^{\prime}(t)^{\top}({\bm{R}}^{\prime}(t)+\bm{Y})<0$ where
${\bm{R}}^{\prime}(t)$ is defined in Lemma 3.5.

###### Proof.

Consider the inner product ${\bm{R}}^{\prime}(t)^{\top}\bm{v}_{i}$. Recall
$\bm{v}_{i}$ is the $i$-th eigenvector of ${\bm{M}}$. By Assumption 3.5 (i),
$\bm{v}_{i}$ does not change with $t$.

By Assumption 3.7, $\lambda_{i}(t)<1/\eta$ for $i>1$, where
$\lambda_{i}(t)\geq 0$ is the corresponding eigenvalue of $\bm{v}_{i}$.

By definition of ${\bm{R}}^{\prime}(t)$ and Assumption 3.5 (i),
${\bm{R}}^{\prime}(t+1)=(\bm{I}-\eta{\bm{M}}(t)(\bm{I}-{\bm{v}}_{1}{\bm{v}}_{1}^{\top})){\bm{R}}^{\prime}(t)$,
hence
${\bm{R}}^{\prime}(t+1)^{\top}\bm{v}_{i}=(1-\eta\lambda_{i}(t)){\bm{R}}^{\prime}(t)^{\top}\bm{v}_{i}$
for $i>1$ and ${\bm{R}}^{\prime}(t)^{\top}{\bm{v}}_{1}=0$. Hence for any
$i>1,t>0$,
$\frac{{\bm{R}}^{\prime}(t)^{\top}\bm{v}_{i}}{{\bm{R}}^{\prime}(0)^{\top}\bm{v}_{i}}=\prod_{j=0}^{t-1}(1-\eta\lambda_{i}(j))\in(0,1)$.

Since
${\bm{R}}^{\prime}(0)={\bm{R}}(0)=(\bm{I}-{\bm{v}}_{1}{\bm{v}}_{1}^{\top})\bm{Y}$,
hence ${\bm{R}}^{\prime}(0)^{\top}\bm{v}_{i}=-{\bm{Y}}^{\top}{\bm{v}}_{i}$ for
any $i>1$.

Plug it into the expression
${\bm{R}}^{\prime}(t)^{\top}({\bm{R}}^{\prime}(t)+{\bm{Y}})$ and we have:

${\bm{D}}(t)^{\top}{\bm{F}}(t)=\sum_{i=2}^{n}{\bm{R}}^{\prime}(t)^{\top}{\bm{v}}_{i}({\bm{R}}^{\prime}(t)^{\top}{\bm{v}}_{i}+{\bm{Y}}^{\top}{\bm{v}}_{i})=\sum_{i=2}^{n}({\bm{R}}^{\prime}(t)^{\top}{\bm{v}}_{i})^{2}(1-\frac{{\bm{R}}^{\prime}(0)^{\top}{\bm{v}}_{i}}{{\bm{R}}^{\prime}(t)^{\top}\bm{v}_{i}})<0$

∎

###  E.2 Progressive Sharpening under Weaker Assumptions

We prove Lemma 3.1 in Section 3, i.e. progressive sharpening happens under
Assumption 3.5 (i) that the set of eigenvectors of the Gram matrix
${\bm{M}}(t)$ is fixed throughout. However, empirically, the eigenvectors of
${\bm{M}}(t)$ change non-negligibly (see Figure 26). In this section, we show
that it is possible to relax Assumption 3.5 (i) to more realistic assumption
on the eigenspace of ${\bm{M}}(t)$. To this end, we first present a dynamical
system view of the dynamics of ${\bm{D}}(t)$, then prove Lemma E.7 which is
analogue of Lemma 3.1 but under weaker assumptions.

####  E.2.1 A dynamical system view

Recall that we assume that ${\bm{D}}(t)$ follows the gradient flow trajectory:
$\frac{\mathrm{d}{\bm{D}}(t)}{\mathrm{d}t}=-{\bm{M}}(t){\bm{D}}(t)$. This is a
linear dynamical system with changing coefficients $-{\bm{M}}(t)$. In order to
understand this dynamics, we first consider the linear dynamical system with
constant coefficients $-{\bm{M}}$,
$\frac{\mathrm{d}{\bm{D}}(t)}{\mathrm{d}t}=-{\bm{M}}{\bm{D}}(t)$, which is
much better understood. The corresponding phase portrait is shown in Figure
25(a). Here, $O$ is only fixed point. In this figure, we consider the ball
$\mathbb{B}\subset\mathbb{R}^{n}$ such that the south pole of $\mathbb{B}$ is
the origin $O$ and the north pole $N$ of $\mathbb{B}$ is fixed to be
$-{\bm{Y}}$, which is the initial point $-{\bm{D}}(t)$. Recall that
${\bm{F}}(t)={\bm{D}}(t)+{\bm{Y}}$ and ${\bm{D}}(0)=-{\bm{Y}}$. We denote the
tip of the vector ${\bm{D}}(t)$ as $D$. Hence,
$\overrightarrow{DO}={\bm{D}}(t)$ and $\overrightarrow{ND}={\bm{F}}(t)$. A
useful geometric observation is the following:

######  Observation E.1.

${\bm{D}}(t)\in\mathbb{B}$ if and only if
${\bm{D}}(t)^{\top}{\bm{F}}(t)={\bm{D}}(t)^{\top}({\bm{D}}(t)-(-{\bm{Y}}))<0$
(equivalently, the angle $\measuredangle(NDO)\geq\pi/2$).

Let $\\{{\bm{v}}_{i}(t)\\}_{i}$ be the set of eigenvectors of ${\bm{M}}(t)$.
By symmetry, we can assume the direction of all $\\{{\bm{v}}_{i}(t)\\}_{i}$
are pointing inside $\mathbb{B}$ (or equivalently,
$-{\bm{v}}_{i}(t)^{\top}{\bm{Y}}\geq 0$). We also define the hypercube
$\mathbb{H}(t)$, which is defined by $\\{{\bm{v}}_{i}(t)\\}_{i}$ as the edges
and $ON$ as the diagonal (see the dashed rectangle in Figure 25(a). All
vertices of $\mathbb{H}(t)$ are on the sphere $\partial\mathbb{B}$. In our
proof of Lemma 3.1 (in which we assume the eigenvectors do not change), we
have shown the entire trajectory of ${\bm{D}}(t)$ is contained in
$\mathbb{H}(t)$ which is always contained in $\mathbb{B}$. In particular, we
prove that the projection of ${\bm{D}}(t)$ onto each ${\bm{v}}_{i}$ decreases
monotonically).

Now, we consider the more general case when the eigenvectors
$\\{{\bm{v}}_{i}(t)\\}_{i}$ may change. In Lemma E.7 presented below, we show
that if the eigenvectors change directions relatively slowly (precisely the
change rate satisfies (20)), ${\bm{D}}(t)$ is still contained in
$\mathbb{H}(t)$, hence also in $\mathbb{B}$. Then by Observation E.1 and (3),
the norm $\|A\|$ increases (hence the sharpness increases).

We also note that it is impossible to prove ${\bm{D}}(t)\in\mathbb{B}$ for all
$t>0$ without any assumption on the change of eigenvector directions. In
particular, if the eigenvector changes fast enough so that ${\bm{D}}(t)$ is
out of the hypercube $\mathbb{H}(t)$, the trajectory may eventually go out of
the ball $\mathbb{B}$ (e.g., the region inside the dashed red box in Figure
25(b)). However, it seems that this region is fairly close to the origin $O$,
and the trajectory does not go very far away from $\mathbb{B}$ (implying
${\bm{D}}(t)^{\top}{\bm{F}}(t)$ is not a large positive number). Hence, the
above geometric intuition suggests that it is possible to further relax the
assumption (inequality (20)) made in E.7 and prove that A-norm increases
(hence sharpness increases) until the sharpness reaches close to $2/\eta$,
after which gradient flow is not a good approximation of gradient descent
anymore. We leave it as an interesting future direction.

(a) The dynamics of ${\bm{D}}(t)$ with constant coefficients. (b) The
eigenvectors of ${\bm{M}}(t)$ change

Figure 25: The phase portraits of the dynamics of ${\bm{D}}(t)$ (projected to
the first two principle directions). We rotate the coordinate system so that
south pole of $\mathbb{B}$ is the origin $O$ and the north pole is $-{\bm{Y}}$
which is the initial point ${\bm{D}}(t)$. ${\bm{v}}_{1}$ and ${\bm{v}}_{2}$
are the first two eigenvectors of ${\bm{M}}$. In (b), ${\bm{v}}_{1}$ and
${\bm{v}}_{2}$ change directions to ${\bm{v}}_{1}^{\prime}$ and
${\bm{v}}_{2}^{\prime}$. The trajectory may go out of $\mathbb{B}$ from
certain regions (the dashed red box).

####  E.2.2 Progressive sharpening when eigendirections change slowly

Suppose at initialization ${\bm{F}}(0)=0$. By ${\bm{D}}(t)={\bm{F}}(t)-Y$, we
know ${\bm{D}}(0)=-Y$. With loss of generality, we assume
${\bm{D}}(0)^{\top}{\bm{v}}_{i}(0)>0$ at initialization for all $i$
(Otherwise, we define ${\bm{v}}_{i}(0)=-{\bm{v}}_{i}(0)$ and this condition
holds).

######  Lemma E.7.

Suppose Assumption 3.3 holds, and the set of (unit) eigenvectors of
${\bm{M}}(t)$ is $\\{{\bm{v}}_{i}(t)\\}$. Assume at all time $t$ and direction
${\bm{v}}_{i}(t)$, the following condition holds:

${\bm{F}}(t)^{\top}\frac{\mathrm{d}{\bm{v}}_{i}(t)}{\mathrm{d}t}<\lambda_{i}(t){\bm{D}}(t)^{\top}{\bm{v}}_{i}(t).$
(20)

Then we have ${\bm{D}}(t)^{\top}{\bm{F}}(t)<0$ for all $t<t_{1}$, where
$t_{1}$ is the first time when there exists some $i$,
${\bm{D}}(t)^{\top}{\bm{v}}_{i}(t)\leq 0$.

In the above lemma, we can see that inequality (20) holds if ${\bm{v}}_{i}(t)$
changes relatively slowly. In particular, if
$\frac{\mathrm{d}{\bm{v}}_{i}(t)}{\mathrm{d}t}=0$ for all $i$, the lemma
reduces to Lemma 3.1. Note that in contrast to the fixed eigenvector
assumption, we cannot show that ${\bm{D}}(t)^{\top}{\bm{v}}_{i}(t)$ decreases
in all directions all the time (since ${\bm{M}}(t)$ may change). Instead, we
show that ${\bm{D}}(t)$ is always in the hypercube $\mathbb{H}(t)$ under the
condition of the lemma.

###### Proof.

We first notice the decomposition

${\bm{D}}(t)^{\top}{\bm{F}}(t)=\sum_{i=1}^{r}{\bm{D}}(t)^{\top}{\bm{v}}_{i}(t){\bm{F}}(t)^{\top}{\bm{v}}_{i}(t).$

We show for each ${\bm{v}}_{i}(t)$,
${\bm{D}}(t)^{\top}{\bm{v}}_{i}(t){\bm{F}}(t)^{\top}{\bm{v}}_{i}(t)<0$ under
the conditions of the lemma.

We first consider the dynamics of inner product
${\bm{D}}(t)^{\top}{\bm{v}}_{i}(t)$. According to Assumption 3.3, when
$t<t_{1}$, ${\bm{D}}(t)^{\top}{\bm{v}}_{i}(t)>0$ due to the continuity.
Moreover, by the dynamics of ${\bm{D}}(t)$ in Assumption 3.3, we can see

$\displaystyle\frac{\mathrm{d}{\bm{D}}(t)^{\top}\bm{v}_{i}(t)}{\mathrm{d}t}$
$\displaystyle=-{\bm{D}}(t)^{\top}{\bm{M}}(t)\bm{v}_{i}(t)+{\bm{D}}(t)^{\top}\frac{\mathrm{d}{\bm{v}}_{i}(t)}{\mathrm{d}t}$
$\displaystyle=-\lambda_{i}(t){\bm{D}}(t)^{\top}\bm{v}_{i}(t)+{\bm{D}}(t)^{\top}\frac{\mathrm{d}{\bm{v}}_{i}(t)}{\mathrm{d}t}$

With this dynamics above and ${\bm{F}}(t)={\bm{D}}(t)+{\bm{Y}}$, we can get
${\bm{F}}$’s dynamics:

$\displaystyle\frac{\mathrm{d}{\bm{F}}(t)^{\top}\bm{v}_{i}(t)}{\mathrm{d}t}$
$\displaystyle=-{\bm{D}}(t)^{\top}{\bm{M}}(t)\bm{v}_{i}(t)+{\bm{F}}(t)^{\top}\frac{\mathrm{d}{\bm{v}}_{i}(t)}{\mathrm{d}t}$
$\displaystyle=-\lambda_{i}(t){\bm{D}}(t)^{\top}\bm{v}_{i}(t)+{\bm{F}}(t)^{\top}\frac{\mathrm{d}{\bm{v}}_{i}(t)}{\mathrm{d}t}$
(D1)

With (D1) and
${\bm{F}}(t)^{\top}\frac{\mathrm{d}{\bm{v}}_{i}(t)}{\mathrm{d}t}\leq\lambda_{i}(t){\bm{D}}(t)^{\top}\bm{v}_{i}(t)$,
we know

$\displaystyle\frac{\mathrm{d}{\bm{F}}(t)^{\top}\bm{v}_{i}(t)}{\mathrm{d}t}$
$\displaystyle=-\lambda_{i}(t){\bm{D}}(t)^{\top}\bm{v}_{i}(t)+{\bm{F}}(t)^{\top}\frac{\mathrm{d}{\bm{v}}_{i}(t)}{\mathrm{d}t}<0.$

In this way, we know ${\bm{F}}(t)^{\top}\bm{v}_{i}(t)$ always decreases for
$t<t_{1}$. Recall that ${\bm{F}}(0)={\bm{D}}(0)+Y=0$, which makes
${\bm{F}}(0)^{\top}{\bm{v}}_{i}(0)=0$. So
${\bm{F}}(t)^{\top}{\bm{v}}_{i}(t)<0$ according to the dynamics.
Geometrically, this implies ${\bm{D}}(t)$ does not cross the facets of
$\mathbb{H}(t)$ incident on the north pole $N$ 444 The hypercube
$\mathbb{H}(t)$ has $2n$ facets, $n$ of them incident on the south pole $O$
and the others the north pole $N$.  (otherwise
${\bm{F}}(t)^{\top}{\bm{v}}_{i}(t)$ needs to change sign). See Figure 25). On
the other hand, ${\bm{D}}(t)^{\top}{\bm{v}}_{i}(t)>0$ for $t<t_{1}$, by the
definition of $t_{1}$, which is equivalent to say that
${\bm{D}}(t)^{\top}{\bm{v}}_{i}(t)$ does not change sign or ${\bm{D}}(t)$ does
not cross the facets of $\mathbb{H}(t)$ incident on the south pole $O$.

Therefore we have
${\bm{D}}(t)^{\top}{\bm{v}}_{i}(t){\bm{F}}(t)^{\top}{\bm{v}}_{i}(t)<0$ and
${\bm{D}}(t)\in\mathbb{H}(t)\subset\mathbb{B}$ for all $t<t_{1}$, where
$t_{1}$ is the first time when ${\bm{D}}(t_{1})^{\top}{\bm{v}}_{i}(t_{1})\leq
0.$ Summing over all the components
${\bm{D}}(t)^{\top}{\bm{v}}_{i}(t){\bm{F}}(t)^{\top}{\bm{v}}_{i}(t)$ for all
$i$, we prove the lemma. ∎

####  E.2.3 Empirical verification of inequality (20)

Figure 26: Verification for inequality (20) when $i=1,5,50$.

We verify the condition (20) in Lemma E.7 via experiments. See Figure 26. We
can see that (20) holds for $i=1,5,50$ during the first hundred iterations of
the training process. However, for very large $i$, the eigenvectors
corresponding to very small eigenvalues may change quickly and (20) does not
hold. The contributions (i.e.,
${\bm{D}}(t)^{\top}{\bm{v}}_{i}(t){\bm{F}}(t)^{\top}{\bm{v}}_{i}(t)$) from
those corresponding to very small eigenvalues tend to cancel each other
empirically, hence does not affect the sign of the total sum
$\sum_{i=1}^{r}{\bm{D}}(t)^{\top}{\bm{v}}_{i}(t){\bm{F}}(t)^{\top}{\bm{v}}_{i}(t)$.
Hence, it is possible to further relax the condition (20) and we leave it as a
future direction.

###  E.3 Proofs of equations in Appendix C

The proof of some equations in Appendix C is omitted, and we list them in this
subsection.

######  Lemma E.8.

(Lemma C.1) The update rule of the residual vector of ${\bm{D}}(t)$:

${\bm{D}}(t+1)^{\top}-{\bm{D}}(t)^{\top}=-\eta{\bm{D}}(t)^{\top}{\bm{M}}(t)+\frac{4\eta^{2}}{n^{2}m}{\bm{D}}(t)^{\top}({\bm{F}}(t)^{\top}{\bm{D}}(t))\mathbf{X}^{\top}\mathbf{X}$
(21)

###### Proof.

$\displaystyle{\bm{D}}(t+1)^{\top}-{\bm{D}}(t)^{\top}={}$
$\displaystyle\frac{1}{\sqrt{m}}({\bm{A}}(t+1)^{\top}{\bm{W}}(t+1)-{\bm{A}}(t)^{\top}{\bm{W}}(t))\mathbf{X}$
$\displaystyle={}$
$\displaystyle\frac{1}{\sqrt{m}}\left(({\bm{A}}(t+1)^{\top}-{\bm{A}}(t)^{\top}){\bm{W}}(t+1)+{\bm{A}}(t)^{\top}({\bm{W}}(t+1)-{\bm{W}}(t))\right)\mathbf{X}$
$\displaystyle={}$
$\displaystyle\frac{1}{\sqrt{m}}\left(({\bm{A}}(t+1)^{\top}-{\bm{A}}(t)^{\top}){\bm{W}}(t)+{\bm{A}}(t)^{\top}({\bm{W}}(t+1)-{\bm{W}}(t))\right)\mathbf{X}$
$\displaystyle+\frac{1}{\sqrt{m}}({\bm{A}}(t+1)^{\top}-{\bm{A}}(t)^{\top})({\bm{W}}(t+1)-{\bm{W}}(t))\mathbf{X}$
$\displaystyle={}$
$\displaystyle\frac{2\eta}{nm}\left((-\bm{W}(t)\mathbf{X}{\bm{D}}(t))^{\top}{\bm{W}}(t)-{\bm{A}}(t)^{\top}{\bm{A}}(t){\bm{D}}(t)^{\top}\mathbf{X}^{\top}\right)\mathbf{X}$
$\displaystyle+\frac{1}{\sqrt{m}}(\frac{2\eta}{n\sqrt{m}}\bm{W}(t)\mathbf{X}{\bm{D}}(t))^{\top}\frac{2\eta}{n\sqrt{m}}{\bm{A}}(t){\bm{D}}(t)^{\top}\mathbf{X}^{\top}\mathbf{X}$
$\displaystyle={}$
$\displaystyle-{\bm{D}}(t)^{\top}\frac{2\eta}{nm}(\mathbf{X}^{\top}{\bm{W}}(t)^{\top}{\bm{W}}(t)\mathbf{X}+\|{\bm{A}}(t)\|^{2}\mathbf{X}^{\top}\mathbf{X})$
$\displaystyle+\frac{4\eta^{2}}{n^{2}m}{\bm{D}}(t)^{\top}({\bm{F}}(t)^{\top}{\bm{D}}(t))\mathbf{X}^{\top}\mathbf{X}$
$\displaystyle={}$
$\displaystyle-\eta{\bm{D}}(t)^{\top}{\bm{M}}(t)+\frac{4\eta^{2}}{n^{2}m}{\bm{D}}(t)^{\top}({\bm{F}}(t)^{\top}{\bm{D}}(t))\mathbf{X}^{\top}\mathbf{X}$

∎

######  Lemma E.9.

(Lemma C.2) The update rule of the Gram matrix ${\bm{M}}(t)$ is,

$\displaystyle{\bm{M}}(t+1)-{\bm{M}}(t)=$
$\displaystyle-\frac{4\eta}{n^{2}m}\left(2({\bm{F}}(t)^{\top}{\bm{D}}(t))\mathbf{X}^{\top}\mathbf{X}+{\bm{F}}(t){\bm{D}}(t)^{\top}\mathbf{X}^{\top}\mathbf{X}+\mathbf{X}^{\top}\mathbf{X}{\bm{D}}(t){\bm{F}}(t)^{\top}\right)$
$\displaystyle+\frac{8\eta^{2}}{n^{3}m^{2}}({\bm{D}}(t)^{\top}\mathbf{X}^{\top}\bm{W}(t)^{\top}\bm{W}(t)\mathbf{X}{\bm{D}}(t))\mathbf{X}^{\top}\mathbf{X}$
$\displaystyle+\frac{8\eta^{2}}{n^{3}m^{2}}\|{\bm{A}}(t)\|^{2}\
\mathbf{X}^{\top}\mathbf{X}{\bm{D}}(t){\bm{D}}(t)^{\top}\mathbf{X}^{\top}\mathbf{X}$

###### Proof.

By the update rule of ${\bm{A}}(t)$ and ${\bm{W}}(t)$ in equation (6) and (7),
we have

$\displaystyle{\bm{M}}(t+1)-{\bm{M}}(t)$ $\displaystyle={}$
$\displaystyle\frac{2}{nm}\left((\|{\bm{A}}(t+1)\|^{2}-\|{\bm{A}}(t)\|^{2})\mathbf{X}^{\top}\mathbf{X}+\
\mathbf{X}^{\top}(\bm{W}(t+1)^{\top}\bm{W}(t+1)-\bm{W}(t)^{\top}\bm{W}(t))\mathbf{X}\right)$
(Use equation (7)) $\displaystyle={}$
$\displaystyle\frac{2}{nm}(-\frac{4\eta}{n}{\bm{D}}(t)^{\top}{\bm{F}}(t)+\eta^{2}\|\frac{\partial\mathcal{L}}{\partial{\bm{A}}}\|^{2})\mathbf{X}^{\top}\mathbf{X}$
$\displaystyle{}+\frac{2}{nm}\left(\mathbf{X}^{\top}((\bm{W}(t+1)^{\top}-\bm{W}(t)^{\top})\bm{W}(t)+{\bm{W}}(t)^{\top}(\bm{W}(t+1)-\bm{W}(t)))\mathbf{X}\right.$
$\displaystyle\left.+\
\mathbf{X}^{\top}(\bm{W}(t+1)^{\top}-\bm{W}(t)^{\top})(\bm{W}(t+1)-\bm{W}(t))\mathbf{X}\right)$
(Use equation (6)) $\displaystyle={}$
$\displaystyle-\frac{8\eta}{n^{2}m}{\bm{D}}(t)^{\top}{\bm{F}}(t)\mathbf{X}^{\top}\mathbf{X}+\frac{8}{n^{3}m^{2}}\eta^{2}({\bm{D}}(t)^{\top}\mathbf{X}^{\top}\bm{W}(t)^{\top}\bm{W}(t)\mathbf{X}{\bm{D}}(t))\mathbf{X}^{\top}\mathbf{X}$
$\displaystyle-\frac{4\eta}{n^{2}m}\left({\bm{F}}(t){\bm{D}}(t)^{\top}\mathbf{X}^{\top}\mathbf{X}+\mathbf{X}^{\top}\mathbf{X}{\bm{D}}(t){\bm{F}}(t)^{\top}\right)$
$\displaystyle+\frac{8\eta^{2}}{n^{3}m^{2}}\|{\bm{A}}(t)\|^{2}\mathbf{X}^{\top}\mathbf{X}{\bm{D}}(t){\bm{D}}(t)^{\top}\mathbf{X}^{\top}\mathbf{X}$

Rearrange the terms and we complete the proof. ∎

######  Lemma E.10.

For all iteration $t$, if any vector $\bm{u}\in\mathbb{R}^{n}$ satisfies
$\mathbf{X}^{\top}\mathbf{X}\bm{u}=0$, then

${\bm{Y}}^{\top}\bm{u}={\bm{D}}(t)^{\top}\bm{u}=0$

###### Proof.

If $\mathbf{X}^{\top}\mathbf{X}\bm{u}=0$, then

$\bm{u}^{\top}\mathbf{X}^{\top}\mathbf{X}\bm{u}=0\Rightarrow\mathbf{X}\bm{u}=0.$

So we have

${\bm{Y}}^{\top}\bm{u}=-{\bm{D}}(0)^{\top}\bm{u}={\bm{A}}^{*\top}{\bm{W}}^{*}\mathbf{X}\bm{u}=0$

With the dynamics of ${\bm{D}}(t)$, we have

${\bm{D}}(t+1)^{\top}\bm{u}={\bm{D}}(t)^{\top}(\bm{I}_{n}-\eta{\bm{M}}^{*}(t))\bm{u}$

While

$\displaystyle{\bm{M}}^{*}(t)\bm{u}$
$\displaystyle={\bm{M}}(t)\bm{u}-\frac{4\eta}{n^{2}m}({\bm{D}}(t)^{\top}{\bm{F}}(t))\mathbf{X}^{\top}\mathbf{X}\bm{u}={\bm{M}}(t)\bm{u}$
$\displaystyle=\frac{2}{mn}(\|{\bm{A}}(t)\|^{2}\mathbf{X}^{\top}\mathbf{X}+\mathbf{X}^{\top}{\bm{W}}^{\top}(t){\bm{W}}(t)\mathbf{X})\bm{u}=0$

Thus we have

${\bm{D}}(t+1)^{\top}\bm{u}={\bm{D}}(t)^{\top}(\bm{I}_{n}-\eta{\bm{M}}^{*}(t))\bm{u}={\bm{D}}(t)^{\top}\bm{u}=...={\bm{D}}(0)^{\top}\bm{u}=0$

∎

######  Lemma E.11.

(Lemma C.7) Here we give the proof of the equation (17):

$\displaystyle\Lambda^{*}(t+1)-$
$\displaystyle\Lambda^{*}(t)=-\frac{8\eta\lambda_{1}}{mn^{2}}\left({\bm{F}}(t)^{\top}{\bm{D}}(t)+({\bm{F}}(t)^{\top}{\bm{v}}_{1})({\bm{D}}(t)^{\top}{\bm{v}}_{1})-\frac{\eta}{2}({\bm{D}}(t)^{\top}{\bm{v}}_{1})^{2}\Lambda^{*}(t)\right.$
$\displaystyle\left.-{}\frac{\eta}{2}{\bm{R}}(t)^{\top}\bm{\Gamma}(t){\bm{R}}(t)-\
\eta{\bm{R}}(t)^{\top}\bm{\Gamma}(t)\left({\bm{v}}_{1}{\bm{v}}_{1}^{\top}{\bm{D}}(t)\right)-\frac{\eta}{mn}{\bm{R}}(t)^{\top}\left(\frac{m}{d}\mathbf{X}^{\top}\mathbf{X}\right){\bm{R}}(t)\right).$

###### Proof.

First, since $\bm{W}^{\top}\bm{W}$ is initialized as
$\frac{m}{d}\mathbf{X}^{\top}\mathbf{X}$, by definition, we have

$\mathbf{X}^{\top}\bm{W}^{\top}\bm{W}\mathbf{X}=\frac{mn}{2}\bm{\Gamma}(t)+\frac{m}{d}\mathbf{X}^{\top}\mathbf{X}$.

Then

$\displaystyle\Lambda^{*}(t+1)-\Lambda^{*}(t)$ $\displaystyle=$
$\displaystyle{\bm{v}}_{1}^{\top}{\bm{M}}(t+1){\bm{v}}_{1}-{\bm{v}}_{1}^{\top}{\bm{M}}(t){\bm{v}}_{1}$
$\displaystyle=$
$\displaystyle{\bm{v}}_{1}^{\top}({\bm{M}}(t+1)-{\bm{M}}(t)){\bm{v}}_{1}$
$\displaystyle=$
$\displaystyle-\frac{8\eta}{n^{2}m}\left(\lambda_{1}{\bm{F}}(t)^{\top}{\bm{D}}(t)+\lambda_{1}({\bm{F}}(t)^{\top}{\bm{v}}_{1})({\bm{D}}(t)^{\top}{\bm{v}}_{1})\right)$
$\displaystyle+\frac{8\eta^{2}}{n^{3}m^{2}}\left(\lambda_{1}{\bm{D}}(t)^{\top}\mathbf{X}^{\top}\bm{W}^{\top}\bm{W}\mathbf{X}{\bm{D}}(t)+\|{\bm{A}}\|^{2}\lambda_{1}^{2}({\bm{D}}(t)^{\top}{\bm{v}}_{1})^{2}\right)$

Because

$\displaystyle{\bm{D}}(t)^{\top}\mathbf{X}^{\top}\bm{W}^{\top}\bm{W}\mathbf{X}{\bm{D}}(t)$
$\displaystyle={}$
$\displaystyle{\bm{D}}(t)^{\top}\left(\frac{m}{d}\mathbf{X}^{\top}\mathbf{X}+\frac{mn}{2}\bm{\Gamma}(t)\right){\bm{D}}(t)$
$\displaystyle={}$
$\displaystyle\frac{m}{d}{\bm{D}}(t)^{\top}\left({\bm{v}}_{1}{\bm{v}}_{1}^{\top}+\bm{I}-{\bm{v}}_{1}{\bm{v}}_{1}^{\top}\right)\mathbf{X}^{\top}\mathbf{X}\left({\bm{D}}(t)^{\top}\left({\bm{v}}_{1}{\bm{v}}_{1}^{\top}+\bm{I}-{\bm{v}}_{1}{\bm{v}}_{1}^{\top}\right)\right)^{\top}$
$\displaystyle+\frac{mn}{2}{\bm{D}}(t)^{\top}\bm{\Gamma}(t){\bm{D}}(t)$
$\displaystyle={}$
$\displaystyle\frac{m}{d}\lambda_{1}({\bm{D}}(t)^{\top}{\bm{v}}_{1})^{2}+\frac{m}{d}{\bm{R}}(t)^{\top}\mathbf{X}^{\top}\mathbf{X}{\bm{R}}(t)+\frac{mn}{2}{\bm{D}}(t)^{\top}\bm{\Gamma}(t){\bm{D}}(t)$

and

$\lambda_{1}\left(\frac{m}{d}+\|{\bm{A}}\|^{2}\right)=\frac{mn}{2}{\bm{v}}_{1}^{\top}({\bm{M}}(t)-\bm{\Gamma}(t)){\bm{v}}_{1}=\frac{mn}{2}\Lambda^{*}(t)-\frac{mn}{2}{\bm{v}}_{1}^{\top}\bm{\Gamma}(t){\bm{v}}_{1}$

we can see that

$\displaystyle\Lambda^{*}(t+1)-\Lambda^{*}(t)$ $\displaystyle=$
$\displaystyle-\frac{8\eta\lambda_{1}}{n^{2}m}\left({\bm{F}}(t)^{\top}{\bm{D}}(t)+({\bm{F}}(t)^{\top}{\bm{v}}_{1})({\bm{D}}(t)^{\top}{\bm{v}}_{1})-\frac{\eta}{mn}({\bm{D}}(t)^{\top}{\bm{v}}_{1})^{2}\left(\frac{m}{d}+\|{\bm{A}}\|^{2}\right)\lambda_{1}\cdot\right.$
$\displaystyle\left.-\frac{\eta}{mn}\cdot\frac{m}{d}{\bm{R}}(t)^{\top}\mathbf{X}^{\top}\mathbf{X}{\bm{R}}(t)-\frac{\eta}{2}{\bm{D}}(t)^{\top}\bm{\Gamma}(t){\bm{D}}(t)\right)$
$\displaystyle=$
$\displaystyle-\frac{8\eta\lambda_{1}}{mn^{2}}\left({\bm{F}}(t)^{\top}{\bm{D}}(t)+({\bm{F}}(t)^{\top}{\bm{v}}_{1})({\bm{D}}(t)^{\top}{\bm{v}}_{1})-\frac{\eta}{2}({\bm{D}}(t)^{\top}{\bm{v}}_{1})^{2}\Lambda^{*}(t)\right.$
$\displaystyle+\frac{\eta}{2}\left({\bm{v}}_{1}^{\top}\bm{\Gamma}(t){\bm{v}}_{1}\cdot({\bm{D}}(t)^{\top}{\bm{v}}_{1})^{2}-{\bm{D}}(t)^{\top}\bm{\Gamma}(t){\bm{D}}(t)\right)-\left.{\bm{R}}(t)^{\top}\left(\frac{m}{d}\mathbf{X}^{\top}\mathbf{X}\right){\bm{R}}(t)\right)$

Note that

$\displaystyle{\bm{v}}_{1}\bm{\Gamma}(t){\bm{v}}_{1}^{\top}({\bm{D}}(t)^{\top}{\bm{v}}_{1})^{2}-{\bm{D}}(t)^{\top}\bm{\Gamma}(t){\bm{D}}(t)$
$\displaystyle=$
$\displaystyle{\bm{D}}(t)^{\top}{\bm{v}}_{1}{\bm{v}}_{1}^{\top}\bm{\Gamma}(t){\bm{v}}_{1}{\bm{v}}_{1}^{\top}{\bm{D}}(t)-\left({\bm{R}}(t)^{\top}+{\bm{D}}(t)^{\top}{\bm{v}}_{1}{\bm{v}}_{1}^{\top}\right)\bm{\Gamma}(t)\left({\bm{R}}(t)+{\bm{v}}_{1}{\bm{v}}_{1}^{\top}{\bm{D}}(t)\right)$
$\displaystyle=$
$\displaystyle-{\bm{R}}(t)^{\top}\bm{\Gamma}(t){\bm{R}}(t)-2{\bm{R}}(t)^{\top}\bm{\Gamma}(t)\left({\bm{D}}(t)^{\top}{\bm{v}}_{1}{\bm{v}}_{1}^{\top}\right)^{\top}$

Now we finish the proof. ∎

######  Lemma E.12.

(Equation 18)
${\bm{R}}(t+1)=\left(I-\eta{\bm{M}}^{*}(t)\right){\bm{R}}(t)+\eta\left({\bm{v}}_{1}{\bm{v}}_{1}^{\top}\bm{\Gamma}(t)-\bm{\Gamma}(t){\bm{v}}_{1}{\bm{v}}_{1}^{\top}\right){\bm{D}}(t)$

###### Proof.

$\displaystyle{\bm{R}}(t+1)$
$\displaystyle=\left(\bm{I}-{\bm{v}}_{1}{\bm{v}}_{1}^{\top}\right){\bm{D}}(t+1)$
$\displaystyle=$
$\displaystyle\left(\bm{I}-{\bm{v}}_{1}{\bm{v}}_{1}^{\top}\right)\left(\bm{I}-\eta{\bm{M}}^{*}(t)\right){\bm{D}}(t)$
$\displaystyle=$
$\displaystyle\left(\bm{I}-{\bm{v}}_{1}{\bm{v}}_{1}^{\top}\right)\left(\bm{I}-\eta{\bm{M}}^{*}(t)\right){\bm{v}}_{1}{\bm{v}}_{1}^{\top}{\bm{D}}(t)$
$\displaystyle+\left(\bm{I}-{\bm{v}}_{1}{\bm{v}}_{1}^{\top}\right)\left(\bm{I}-\eta{\bm{M}}^{*}(t)\right)\left(\bm{I}-{\bm{v}}_{1}{\bm{v}}_{1}^{\top}\right){\bm{D}}(t)$
$\displaystyle=$
$\displaystyle\left(\bm{I}-\eta{\bm{M}}^{*}(t)\right){\bm{R}}(t)-{\bm{v}}_{1}{\bm{v}}_{1}^{\top}\left(\bm{I}-\eta{\bm{M}}^{*}(t)\right)\left(\bm{I}-{\bm{v}}_{1}{\bm{v}}_{1}^{\top}\right){\bm{D}}(t)$
$\displaystyle+\left(\bm{I}-{\bm{v}}_{1}{\bm{v}}_{1}^{\top}\right)\left(\bm{I}-\eta{\bm{M}}^{*}(t)\right){\bm{v}}_{1}{\bm{v}}_{1}^{\top}{\bm{D}}(t)$
$\displaystyle=$
$\displaystyle\left(\bm{I}-\eta{\bm{M}}^{*}(t)\right){\bm{R}}(t)-{\bm{v}}_{1}{\bm{v}}_{1}^{\top}(-\eta\bm{\Gamma}(t))\left(\bm{I}-{\bm{v}}_{1}{\bm{v}}_{1}^{\top}\right){\bm{D}}(t)$
$\displaystyle+\left(\bm{I}-{\bm{v}}_{1}{\bm{v}}_{1}^{\top}\right)(-\eta\bm{\Gamma}(t)){\bm{v}}_{1}{\bm{v}}_{1}^{\top}{\bm{D}}(t)$
$\displaystyle=$
$\displaystyle\left(I-\eta{\bm{M}}^{*}(t)\right){\bm{R}}(t)+\eta\left({\bm{v}}_{1}{\bm{v}}_{1}^{\top}\bm{\Gamma}(t)-\bm{\Gamma}(t){\bm{v}}_{1}{\bm{v}}_{1}^{\top}\right){\bm{D}}(t)$

∎

##  Appendix F Missing Preliminaries

Hessian, Fisher information matrix and NTK: The Hessian of the objective
$\mathcal{L}(f(\bm{\theta}))$ is:

$\nabla_{\bm{\theta}}^{2}\mathcal{L}(f(\bm{\theta}))=\frac{1}{n}\sum_{i=1}^{n}\nabla_{\bm{\theta}}^{2}\ell(f(\bm{\theta},\mathbf{x}_{i}))$

We need the relationship between the Hessian matrix, the Fisher information
matrix (FIM) and the neural tangent kernel (NTK). As shown in Papyan [26],
Martens [23], Bottou et al. [4], the Hessian can be decomposed into two
components:

$\nabla_{\bm{\theta}}^{2}\mathcal{L}(f(\bm{\theta}))=\frac{1}{n}\sum_{i=1}^{n}\left(\frac{\partial
f(\mathbf{x}_{i},\bm{\theta})}{\partial\bm{\theta}}^{\top}\left.\frac{\partial^{2}\ell(z,y_{i})}{\partial
z^{2}}\right|_{f(\mathbf{x}_{i})}\frac{\partial
f(\mathbf{x}_{i},\bm{\theta})}{\partial\bm{\theta}}+\left.\frac{\partial\ell(z,y_{i})}{\partial
z}\right|_{f(\mathbf{x}_{i})}\nabla_{\bm{\theta}}^{2}f(\mathbf{x}_{i},\bm{\theta})\right)$

Here $\frac{\partial
f(\mathbf{\mathbf{x}_{i},{\bm{\theta}}})}{\partial{\bm{\theta}}}\in\mathbb{R}^{1\times
p}$ is the gradient of $f$. Papyan [26] also demonstrate empirically that the
first term, known as “Gauss-Newton matrix”, G-term or Fisher information
matrix (FIM), dominates the second term in terms of the largest eigenvalue.
Thus when considering the sharpness, we can analyze the largest eigenvalue of
FIM which is a close proxy of the largest eigenvalue of Hessian. In the binary
MSE loss case, $\left.\frac{\partial^{2}\ell(z,y_{i})}{\partial
z^{2}}\right|_{f(\mathbf{x}_{i})}=2$, which implies that

$\left\|\nabla_{\bm{\theta}}^{2}\mathcal{L}(f(\bm{\theta}))\right\|_{2}\approx\bm{\left
missing}\|G\right\|_{2}:=\frac{2}{n}\left\|\sum_{i=1}^{n}\frac{\partial
f(\mathbf{x}_{i},\bm{\theta})}{\partial{\bm{\theta}}}^{\top}\frac{\partial
f(\mathbf{x}_{i},\bm{\theta})}{\partial{\bm{\theta}}}\right\|_{2}=\frac{2}{n}\left\|\frac{\partial{\bm{F}}(\bm{\theta})}{\partial{\bm{\theta}}}^{\top}\frac{\partial{\bm{F}}(\bm{\theta})}{\partial{\bm{\theta}}}\right\|_{2}$

where
$\frac{\partial{\bm{F}}(\bm{\theta})}{\partial{\bm{\theta}}}:=\left(\frac{\partial
f(\mathbf{\mathbf{x}_{1},{\bm{\theta}}})}{\partial{\bm{\theta}}}^{\top},...,\frac{\partial
f(\mathbf{\mathbf{x}_{n},{\bm{\theta}}})}{\partial{\bm{\theta}}}^{\top}\right)^{\top}\in\mathbb{R}^{n\times
p}$. Meanwhile, Karakida et al. [16] pointed out the duality between the FIM
and a Gram matrix ${\bm{M}}$, defined as

$\bm{M}=\frac{2}{n}\frac{\partial{\bm{F}}(\bm{\theta})}{\partial{\bm{\theta}}}\frac{\partial{\bm{F}}(\bm{\theta})}{\partial{\bm{\theta}}}^{\top}$
(22)

It also known as the neural tangent kernel NTK (Karakida et al. [16, 15]),
which has been studied extensively in recent years (see e.g.,
[13],[8],[2],[5]). Note that in this paper, we do not assume the training is
in NTK regime, in which the Hessian does not change much during training. It
is not hard to see that ${\bm{M}}$ and FIM share the same non-zero
eigenvalues: if $\bm{G}\bm{u}=\lambda\bm{u}$ for some eigenvector
$\bm{u}\in\mathbb{R}^{p}$,

${\bm{M}}\frac{\partial{\bm{F}}(\bm{\theta})}{\partial{\bm{\theta}}}\bm{u}=\frac{\partial{\bm{F}}(\bm{\theta})}{\partial{\bm{\theta}}}\bm{G}\bm{u}=\lambda\frac{\partial{\bm{F}}(\bm{\theta})}{\partial{\bm{\theta}}}\bm{u},$

in other words, $\lambda$ is also an eigenvalue of ${\bm{M}}$.

Sharpness: There are various definitions of sharpness in the literature ([20,
30, 9]). In particular, a popular definition of the sharpness is the largest
eigenvalue of the Hessian ([30]). Based on the above discussion, in this
paper, we adopt the largest eigenvalue of ${\bm{M}}$,
$\Lambda(\bm{\theta})=\lambda_{\max}({\bm{M}})$ as the definition of the
sharpness, which is a close approximation of the largest eigenvalue of the
Hessian empirically.

Gradient Descent: In this paper, we study the trajectory of gradient descent
and gradient flow 555 Gradient flow is a good approximation of gradient
descent in the beginning of the training. See Cohen et al. [6] for more
experiments and Ahn et al. [1] for theoretical justification. We assume this
fact during the progressive sharpening phase. See Assumption 3.3. . We use
$\bm{\theta}(t)$ to denote the parameter at iteration $t$ (or time $t$) and
the sharpness at time $t$ as $\Lambda(t)=\Lambda(\bm{\theta}(t))$. We
similarly define ${\bm{M}}(t),{\bm{F}}(t),{\bm{D}}(t),\mathcal{L}(t)$.

Along GD trajectory, the weight vector $\bm{\theta}(t)$ is updated in the
following way:

$\bm{\theta}(t+1)=\bm{\theta}(t)-\eta\frac{\partial\mathcal{L}(\bm{\theta}(t))}{\partial\bm{\theta}(t)}$

When the learning rate $\eta$ is infinitesimal, the GD trajectory above is
equivalent to gradient flow trajectory. Here we show the gradient flow
dynamics of the residual vector $\bm{D}(t)$:

$\frac{\mathrm{d}\bm{D}(t)}{\mathrm{d}t}=\frac{\partial{\bm{D}}(t)}{\partial{\bm{\theta}}}\frac{\mathrm{d}\bm{\theta}(t)}{\mathrm{d}t}=-\frac{\partial{\bm{F}}(t)}{\partial{\bm{\theta}}}\frac{\partial\mathcal{L}(t)}{\partial{{\bm{\theta}}}}=-\frac{2}{n}\frac{\partial{\bm{F}}(t)}{\partial{\bm{\theta}}}\frac{\partial{\bm{F}}(t)}{\partial{\bm{\theta}}}^{\top}\bm{D}(t)=-\bm{M}(t)\bm{D}(t)$
(23)

In light of (23), we have the following approximate update rule of
${\bm{D}}(t)$ under gradient descent:

${\bm{D}}(t+1)-{\bm{D}}(t)\approx-\eta{\bm{M}}(t){\bm{D}}(t)$


# Normal Reconstruction from Specularity in the Endoscopic Setting

###### Abstract

We show that for a plane imaged by an endoscope the specular isophotes are
concentric circles on the scene plane, which appear as nested ellipses in the
image. We show that these ellipses can be detected and used to estimate the
plane’s normal direction, forming a normal reconstruction method, which we
validate on simulated data. In practice, the anatomical surfaces visible in
endoscopic images are locally planar. We use our method to show that the
surface normal can thus be reconstructed for each of the numerous
specularities typically visible on moist tissues. We show results on
laparoscopic and colonoscopic images.

Index Terms—  Specular, reconstruction, endoscopy.

##  1 Introduction

Specularities typically appear as moving white spots on the tissues in
endoscopy; they are usually considered as nuisance [1]. In contrast, we
propose to use them as 3D reconstruction cues arising from a single image.
They may then be used as valuable assets to integrate in existing multi-image
endoscopic 3D reconstruction systems [2, 3, 4]. Although shape-from-
specularity has been researched in computer vision, our proposal of using the
specular isophotes for 3D reconstruction is new. Existing work is generally
based on tracking specularities or reflections over multiple images. The
analysis in [5] shows that local surface convexity or concavity can be
determined from the image motion of specularities with a known camera
trajectory. The method in [6] reconstructs the shape mesostructure from a
dense specularity field from hundreds of images. The method in [7] uses the
specular flow for estimating scene structure from 2D image motion. The method
in [8] uses a quadric surface model, an orthographic camera, and requires the
object to rotate around the optical axis to the shape of a mirror surface from
sparse correspondences. The method in [9] reconstructs the pose of a moving
plane from three images of its reflection on a specular surface. These methods
rely on assumptions which cannot be fulfilled in interventional medical
images.

In contrast, we provide theoretical and practical insights into the 3D
reconstruction of the observed tissue’s normal from an isolated specularity.
We show that once a specularity is detected, the shape normal at the
specularity’s Brightest Point (BP) can be estimated in closed-form. We derive
these results under the so-called endoscopic setup, which is that the light is
a point-light source collocated with the camera centre. Our main assumption is
then that the observed surface is locally flat and that the reflectance is
modelled by Phong’s specular model. We study the isophotes, which are the
curves of equal incoming intensities on the camera’s retinal plane. We show
that under the above assumptions the isophotes are concentric circles on the
scene plane and ellipses in the image. From this key result, we re-use well-
known 3D vision results on conics, of which the ellipse is a special case.
Specifically, we show that using a single ellipse isophote detected in an
image, the scene plane’s normal can be reconstructed up to a two-fold
ambiguity. This leads to a reliable method of local normal reconstruction for
mildly curved surface patches. We show results on synthetic and real images of
the liver and the colon.

##  2 Theory and methods

###  2.1 General Specular Isocurve Model

A model of specular isophotes on planes was introduced [10] with Phong’s
reflection [11], where it was shown that the specular isophotes are subset of
quartic isocurves on the scene plane. We briefly recall and adapt the
derivation of this model and specialise it to the endoscopic setup. The scene
plane is chosen as the $XY$-plane with 2D points $p^{\top}=(x,y)$
corresponding to 3D points $P^{\top}=(x,y,0)$. Defining $V,L\in\mathbb{R}^{3}$
as the viewpoint and light source position, the cosine formula [11] gives
specular reflection as:

$\hat{I}_{s}(p)\overset{\text{def}}{=}c\max(0,\cos(\beta(p)))^{n},$ (1)

where $n>0$ characterises the surface roughness and $c>0$ is an unknown
constant factor modelling the surface albedo, light intensity and linear
camera response coefficient, and $\beta(p)$ is the angle between the viewing
direction $\mu(V-P)$ and the direction of perfect reflection $-\mu(R-P)$ such
that $\mu(U)\overset{\text{def}}{=}\frac{U}{\|U\|}$ for $U\in\mathbb{R}^{3}$
and $R^{\top}=(L_{X},L_{Y},-L_{Z})$. By substituting these components in
equation (1), simplifying and introducing $\tau=\sqrt[n]{\frac{t}{c}}$, it was
shown [10] that, on an infinite scene plane, the specular isophote
$\hat{I}_{s}(p)=t$, $0<t\leq c$ is a subset of the quartic isocurve (that is,
given by nullifying a bivariate polynomial of degree four) $Q(p)=0$, called
the general specular isocurve, with:

$Q(p)=((R-P)^{\top}(V-P))^{2}-\tau^{2}\|R-P\|^{2}\|V-P\|^{2}.$ (2)

We point out the distinction that exists between an isophote
$\hat{I}_{s}(p)=t$, which is a curve on the scene plane of constant intensity
as observed in the image, and its model as a quartic isocurve $Q(p)=0$. The
quartic isocurve is a pair of curves; parts of which form the isophote [10],
in a non-trivial and non-systematic way. We show that simplifications exist in
the endoscopic setup.

###  2.2 Endoscopic Specular Isophote Model

In the endoscopic setup, the light source and the camera are co-located and we
thus set $L=V$. We substitute $\kappa=1-\tau^{2}$ and
$R^{\top}=(V_{X},V_{Y},-V_{Z})$ in equation (2), which after simplification
yields the endoscopic specular isocurve $E(p)=0$, with:

$\displaystyle E(p)=\kappa((x-V_{X})^{2}+(y-V_{Y})^{2})^{2}+$ (3)
$\displaystyle 2V_{Z}^{2}(\kappa-2)((x-V_{X})^{2}+(y-V_{Y})^{2})+\kappa
V_{Z}^{4}.$

This is still a quartic equation, albeit of a simpler form than the general
quartic isocurve (2). Our main results are next given as two propositions,
which characterise the geometric curve represented by this quartic.

######  Proposition 1.

The endoscopic specular isocurve $E(p)=0$ represents a pair of concentric
circles with centre $(V_{X},V_{Y})^{\top}$ and radii
$r_{\pm}=|V_{Z}|\sqrt{\frac{2-\kappa}{\kappa}\pm\sqrt{(\frac{2-\kappa}{\kappa})^{2}-1}}$.

###### Proof.

The quartic (3) factorises into the product of two quadratics as:

$E(p)=q_{+}(p)\,q_{-}(p),$ (4)

where $q_{\pm}(p)=(x-V_{X})^{2}+(y-V_{Y})^{2}-r_{\pm}^{2}$ and $q_{+},q_{-}$
represent the sought circles. ∎

######  Proposition 2.

The endoscopic specular isophote is the circle of smallest radius $r_{-}$ from
the endoscopic specular isocurve.

###### Proof.

For $0<t<c$ we have $0<\kappa<1$ and $r_{+}>|V_{Z}|>r_{-}>0$. It was shown
[10, lemma 27] that, in the general case, the isophote lies in a so-called
‘outer ring’, a circle of radius $|V_{Z}|$ and with centre
$(V_{X},V_{Y})^{\top}$. Therefore, in the endoscopic case, the isophote must
be the smallest of the two circles of the isocurve. ∎

Figure 1(a) illustrates the isocurves obtained for simulated data, as
described in section 3. We clearly see that the specularity is radial on the
scene plane and that the isophote is given by the circle of radius $r_{-}$ (in
green), lying inside the outer ring (in orange), whilst the circle of radius
$r_{+}$ lies outside it (in red). This is verified for all isophotes in figure
1(b).

(a) Isocurves for $\kappa=0.55$

(b) Radii against $\kappa$

Fig. 1: Endoscopic specular isocurves on the scene plane.

###  2.3 Reconstruction Method

Proposition 2 shows that the specular isophotes are concentric circles on the
scene plane. By property of perspective projection, these circles form
ellipses on the image plane. We use this property to reconstruct the plane
normal from the specularity observed in the image in closed-form. We denote as
$C\in\mathbb{R}^{3\times 3}$ the symmetric matrix representation of the
isophote ellipse as a so-called point-conic in the image. Background on
ellipses and conics is given in [12, Chapter 8]. We proceed with a given
isovalue $0<t<m$, where $m$ is the maximum image intensity (typically $m=255$
for 8-bit images), a given region of interest $\Omega$ containing the
specularity and a given intrinsic camera parameter matrix
$K\in\mathbb{R}^{3\times 3}$ obtained by classical calibration [12, Chapter
6]. Our method follows four steps. First, we find the image pixels pertaining
to the isophote in $\Omega$ using the Marching Squares algorithm, the 2D
version of the popular Marching Cubes algorithm. Second, we fit the isophote
ellipse using the closed-form solution [13]. This gives us matrix $C$. Third,
we transfer the ellipse to the normalised camera plane as
$C^{\prime}=K^{\top}CK$. Fourth, we use the circle pose estimation method [14,
Appendix A], or so-called backprojection problem for one conic correspondence,
which provides us with two possible normals $N_{\pm}$ for the scene plane.
These two normals are due to a concave/convex surface ambiguity, under the
assumption that the isophote lies on the tangent plane to the observed surface
at the BP. This ambiguity cannot generally be resolved from a single viewpoint
[5]. If the circle radius were known, the camera to plane distance could be
reconstructed. However, as opposed to observing physical circles, the circle
radius related to a specularity is never known, and the camera to plane
distance is thus unrecoverable.

##  3 Experimental Results

Fig. 2:  Pipeline for the validation of normal reconstruction from specular
isophotes on simulated data.

###  3.1 Synthetic Data

Figure 2 illustrates the three-stage evaluation pipeline with synthetic data.
In stage 1, we simulate the imaging process with the following three steps. 1)
We compute the scene plane texture map as an $M\times M$ image using equation
(1) with material roughness $n$. Without loss of generality, we set
$V_{X}=V_{Y}=0$ so that the BP lies at the image center. We thus have that
$V_{Z}>0$ is the camera to scene plane distance. We simulate a non-perfect
endoscopic setup by choosing $\epsilon>0$ and setting
$L=V+\epsilon(\cos(\alpha),\sin(\alpha),\beta)^{\top}$, where $\alpha$ and
$\beta$ are uniformly distributed in $[0,2\pi[$ and $[-0.5,0.5]$,
respectively. 2) We apply a projective transformation to the scene plane by
means of a homography $H$, to form its sought perspective image $I_{s}$. We
use a slanted view, as typical of colonoscopy, with a plane normal to camera
axis angle $\theta=58^{\circ}$. We set the camera intrinsics as $f=M$ for the
focal length and $c_{x}=c_{y}=M/2$ for the principal point. 3) We add white
Gaussian noise to the simulated image with variance $\sigma^{2}$. In stage 2,
we proceed with the reconstruction process with the following two steps. 4) We
use Gaussian smoothing to reduce the effect of noise. We then normalise the
image intensities so that the intensity at the BP is 1. 5) Given the isovalue
$0<t<1$, we run the proposed reconstruction method. In stage 3, we compute the
angular error on each of the estimated normals. The default parameters are
$\epsilon=0$, $M=406$, $V_{Z}=1000$, $n=50$, $\sigma=5\%$, and $t=0.1$; they
lead to the illustration from figure 2.

The error plots for 1000 independent realisations are shown in figure 3. We
vary five important parameters within their range of interest while freezing
the others to their default values. First, the noise $\sigma$ is varied from
0% to 10% of the intensity range. We observe that the normal error increases
with noise, in average and in standard deviation. It is on average kept below
1.25°, including the case of very noisy images. Second, the plane to camera
angle $\theta$ is varied from 0 (fronto-parallel view) towards $\frac{\pi}{2}$
(extreme grazing view). We observe a strong growth of the error, with
nonetheless a maximum value kept under 7°. Third, the material roughness $n$
is varied from 30 to 120. The higher this parameter, the steeper the intensity
profile of the specularity, making isophote detection more sensitive to noise.
We indeed observe that the normal error increases linearly with roughness,
with a very small slope of approximately $10^{-2}$, without exceeding 1.75°.
Fourth, the isovalue $t$ is varied from 0.02 and 0.8. Recall that for a low
value the isophote is wide and close to the outer ring whilst for a high value
it shrinks closely to the BP. Therefore the stable configurations should be
between these two extremes. We observe that this indeed happens, with a
globally U-shaped normal error curve, reaching a minimum at about 0.5 to 0.6.
Fifth, the imperfect co-location of the light source and camera centre
$\epsilon$ is varied between 0 and 800, which, as for $V_{Z}$, can be
understood as mm. Specifically, we first centre the scene plane’s window at
the BP and choose $n=100$ to explore larger space of model imperfections while
ensuring that the model errors are not mixed with errors related to partial
view. Recall that for a large value of $\epsilon$ the isophote is no longer a
circle in the scene plane. We observe that the normal error remains stable for
a light source and camera located inside a cylinder of radius 200 mm and
height 200 mm (i.e., for $\epsilon\leq 200$). This is much larger than the
distance which may exist in the design of most endoscopes.

Fig. 3: Evaluation results on synthetic data, giving the average normal error
$\bar{E}$ in degrees. The black bars represent the error standard deviation
and the cyan bars represent the interval $[\bar{E}-\min(E),\max(E)-\bar{E}]$.

###  3.2 Real Data

We used our method in two concrete cases, laparoscopic liver resection and
colonoscopy. In both cases, the practical problem is to obtain an
interventional 3D model from images. This is difficult because the observed
structures are very deformable, precluding the use of many vision techniques
such as Structure-from-Motion. It is thus tremendously important to be able to
exploit single-image 3D reconstruction, for which our method is well-adapted.
First, the camera can be easily calibrated when the procedure starts. Second,
because the observed structures are moist, the images contain many
specularities. Third, the specularities are typically small in size, and thus
supported by a locally planar surface region.

####  3.2.1 Laparoscopic Liver Resection

We ran our method on five images with a total of 26 specularities extracted
from five procedures collected in our hospital under ethical approval
IRB00008526-2019-CE58 issued by CPP Sud-Est VI in Clermont-Ferrand, France. A
representative example is shown in figure 4. We disambiguated the normal-pairs
manually and performed a comparison with [15], a method which registers a
preoperative 3D model to the image, obtaining an angular difference of
$7.11^{\circ}\pm 4.86^{\circ}$. This shows a very good quantitative agreement
between our method and [15].

(a) Laparoscopic image

(b) Results for P1

(c) Reconstructed VS mesh normals

(d) Reference 3D model

Fig. 4: Example of normal reconstruction for a 2D laparoscopic image. (a) The
four specularities used. (b) Close-up and reconstructed normals for P1. (c)
Reconstructed normals for our method compared to preoperative model
registration [15]. (d) Location of the four specularities on the registered
preoperative model.

####  3.2.2 Colonoscopy

We ran our method on $1248\times 1080$ images extracted from colonoscopy
procedures within the IRB approved protocol of the Endomapper project. We show
representative examples in figure 5 with 11 reconstructed normals. We did not
find a method which would provide a satisfying 3D reconstruction for
comparison. Nonetheless, the reconstructed normals we obtained are
qualitatively sound, showing the potential applicability of our method to
colonoscopy. We considered using the simulated data from EndoSLAM [3], for
which however the surface is made of fronto-parallel planes whose normal is
thus always $(0,0,1)^{\top}$. In contrast, [16] provides smoother depth maps
but the surface triangulation is not dense enough to create realistic local
specularities, as shown in figure 6.

Fig. 5:  Sparse normal reconstruction for the colon surface. We show the two
possible orientations of each local tangent plane containing an isolated
specular highlight. Fig. 6:  Excerpts of publicly available datasets, left:
EndoSLAM [3] and right: [16].

##  4 Conclusion

We have introduced a geometric model of the specular isophotes in endoscopy,
from which we have derived a normal reconstruction method. This is based on
the general specular model [10], which we have specialised to endoscopy and
extended to 3D reconstruction. We have obtained convincing results in two
clinical applications. Our future work will focus on two main points. First,
we will design automatic specularity detection by means of combining deep
learning and the elliptic shape prior we have derived. This will increase the
applicability of our method and cope with the mixed specularities of non-
elliptical shape owing the inter-reflections. Second, we will incorporate our
method into the tubular-NRSfM method applied to the colon [4].

Declarations Informed consent was obtained from all individual participants
included in the study. This article does not contain any studies with animals
performed by any of the authors.

## References

  * [1] R. Daher, F. Vasconcelos, and D. Stoyanov,  “A temporal learning approach to inpainting endoscopic specularities and its effect on image correspondence,”  arXiv preprint arXiv:2203.17013, 2022.
  * [2] CS. Bell, KL. Obstein, and P. Valdastri,  “Image partitioning and illumination in image-based pose detection for teleoperated flexible endoscopes,”  Artificial intelligence in medicine, vol. 59, no. 3, pp. 185–196, 2013.
  * [3] KB Ozyoruk et al.,  “EndoSLAM dataset and an unsupervised monocular visual odometry and depth estimation approach for endoscopic videos,”  Medical image analysis, vol. 71, pp. 102058, 2021.
  * [4] A. Sengupta and A. Bartoli,  “Colonoscopic 3D reconstruction by tubular non-rigid structure-from-motion,”  International Journal of Computer Assisted Radiology and Surgery, vol. 16, no. 7, pp. 1237–1241, 2021.
  * [5] A. Zisserman, P. Giblin, and A. Blake,  “The information available to a moving observer from specularities,”  Image and vision computing, vol. 7, no. 1, pp. 38–42, 1989.
  * [6] T. Chen, M. Goesele, and H-P. Seidel,  “Mesostructure from specularity,”  in CVPR’06. IEEE, 2006, vol. 2, pp. 1825–1832.
  * [7] S. Roth and M-J. Black,  “Specular flow and the recovery of surface structure,”  in CVPR’06. IEEE, 2006, vol. 2, pp. 1869–1876.
  * [8] A-C. Sankaranarayanan, A. Veeraraghavan, O. Tuzel, and A. Agrawal,  “Specular surface reconstruction from sparse reflection correspondences,”  in CVPR. IEEE, 2010, pp. 1245–1252.
  * [9] M. Liu, Kwan-Yee K. Wong, Z. Dai, and Z. Chen,  “Pose estimation from reflections for specular surface recovery,”  in CVPR. IEEE, 2011, pp. 579–586.
  * [10] A. Bartoli,  “The highlight ovals,”  Journal of Mathematical Imaging and Vision, vol. 61, no. 7, pp. 919–943, 2019.
  * [11] Bui Tuong Phong,  “Illumination for computer generated pictures,”  Communications of the ACM, vol. 18, no. 6, pp. 311–317, 1975.
  * [12] R. Hartley and A. Zisserman,  Multiple view geometry in computer vision,  Cambridge university press, 2003.
  * [13] A. Fitzgibbon, M. Pilu, and R-B. Fisher,  “Direct least square fitting of ellipses,”  IEEE PAMI, vol. 21, no. 5, pp. 476–480, 1999.
  * [14] D. Forsyth, J-L. Mundy, A. Zisserman, C. Coelho, A. Heller, and C. Rothwell,  “Invariant descriptors for 3D object recognition and pose,”  IEEE PAMI, vol. 13, no. 10, pp. 971–991, 1991.
  * [15] B. Koo, E. Özgür, B. Le Roy, E. Buc, and A. Bartoli,  “Deformable registration of a preoperative 3D liver volume to a laparoscopy image using contour and shading cues,”  in MICCAI. Springer, 2017, pp. 326–334.
  * [16] A Rau et al.,  “Implicit domain adaptation with conditional generative adversarial networks for depth prediction in endoscopy,”  International journal of computer assisted radiology and surgery, vol. 14, no. 7, pp. 1167–1176, 2019.