# The Directional Bias Helps Stochastic Gradient Descent to Generalize in
Kernel Regression Models

Yiling Luo, Xiaoming Huo, Yajun Mei

(April 2022)

###### Abstract

We study the Stochastic Gradient Descent (SGD) algorithm in nonparametric
statistics: kernel regression in particular. The directional bias property of
SGD, which is known in the linear regression setting, is generalized to the
kernel regression. More specifically, we prove that SGD with moderate and
annealing step-size converges along the direction of the eigenvector that
corresponds to the largest eigenvalue of the Gram matrix. In addition, the
Gradient Descent (GD) with a moderate or small step-size converges along the
direction that corresponds to the smallest eigenvalue. These facts are
referred to as the directional bias properties; they may interpret how an SGD-
computed estimator has a potentially smaller generalization error than a GD-
computed estimator. The application of our theory is demonstrated by
simulation studies and a case study that is based on the FashionMNIST dataset.

##  1 Introduction

The Stochastic Gradient Descent (SGD) is a popular optimization algorithm that
has a wide range of applications, including generalized linear model in
statistics and deep Neural Network in machine learning. One main advantage of
the SGD is the computational scalability due to low cost per iteration. Recent
work also indicates that the SGD might also lead to outcomes that possess nice
statistical properties under the linear regression framework, see [19].

In this paper, we study the statistical properties of the SGD under
nonparametric regression models. We focus on the Reproducing Kernel Hilbert
Space (RKHS) model, which is popular in both statistics and machine learning
communities and is often simply referred to as the “kernel trick,” see [2,
27]. The kernel method can be applied in various domains such as image
processing [24] and text mining [11].

Our main approach is to analyze the directional bias of the SGD algorithm
under the RKHS model, which can help us to explain why the outcome of SGD has
good generalization properties. Directional bias, also referred to as implicit
bias, means that an algorithm generates a solution path that is biased towards
a certain direction, and it is also closely related to implicit regularization
in deep learning [10]. Directional bias also means that the algorithm prefers
some directions over the others even though they may have the same objective
function value. For example, paper [29] shows the directional bias of SGD and
GD in the linear regression model, and analyzes the relationship between the
directional bias and the generalization error in such a setting. There is no
directional bias result in kernel regression, but one may expect it to exist
and to explain the generalization performance of the outcome of SGD in the
kernel regression model.

The state-of-the-art result on the directional bias of SGD can be divided into
two categories, based on their underlying techniques, mostly under the linear
regression model. The first category is the stochastic gradient flow method
where one assumes an infinitesimal step-size in SGD and thus the parameter
dynamic follows a stochastic differential equation, see [18, 1, 4]. The second
category is to analyze the discrete SGD sequence, which in general requires a
moderate step-size such that the algorithm converges, see [29] for a example
in linear regression. Our approach belongs to the second category.

We want to point out that there are more research to study the directional
bias of the Gradient Descent (GD) than for the SGD. For instance, for Neural
Networks in the ‘lazy training’ regime, paper [6] shows that GD converges in
the direction of the smallest eigenvalue of the Neural Tangent Kernel; for
high-dimension regression, papers [26, 31] show that GD finds a sparse
estimation.

Our contributions are two folded. First, we study the directional bias of
(S)GD in a nonparametric regression model. Though the nonparametric regression
is well studied in statistics, the directional bias is a relatively new
concept [29]. Second, we unify the conditions to guarantee the directional
bias of GD and SGD sequences. The main condition is the diagonally dominant
Gram matrix, which covers a large class of kernel functions.

Our result can shed new light on deep learning [3]. By the state-of-the-art
mathematical theory of Neural Networks (NN), kernel and/or nonparametric
methods can approximate the functional space of neural networks, see for
example the NTK theory [15], and the Radon bounded variance space description
for ReLU NN [20]. These phenomena can lead to interesting future research.

Organization. The rest of this paper is organized as follows. In Section 2, we
give problem formulation, revisit the algorithms and state our assumption. In
Section 3, we state our main theorems, including the directional bias result
and its implication for generalization. In Section 4, we perform numerical
experiments. In Section 5, we discuss our findings and propose some future
research topics. The detailed proof and experiments are included in the
appendix.

##  2 Problem Formulation

In Subsection 2.1 we define the kernel regression; in Subsection 2.2, we
present the SGD and GD algorithms; in Subsection 2.3, we state our assumption
for later analysis. We also provide a simple example to justify the
assumption.

###  2.1 Kernel Regression

Suppose that we have $n$ data pairs $\\{\bm{x}_{i},y_{i}\\}_{i=1}^{n}$, where
$y_{i}\in\mathcal{R}$ is associated with
$\bm{x}_{i}\in\mathcal{X}\subset\mathcal{R}^{p}$ through an unknown model
$f(\bm{x}_{i})$. The goal is to estimate the unknown model $f$ from the data.
One solution is to minimize the empirical risk function

$\displaystyle\min_{f}\frac{1}{n}\sum_{i=1}^{n}\ell(y_{i},f(\bm{x}_{i})),$ (1)

where $\ell$ is the loss function. A popular choice for regression task is the
squared loss $\ell(y,\bm{x})=\frac{1}{2}(y-f(\bm{x}))^{2}$.

One can see that problem (1) is not well-defined, as there are infinitely many
solutions to $\forall i:f(\bm{x}_{i})=y_{i}$, and some of them do not
generalize for a new test data. One way to fix it is to restrict
$f\in\mathcal{H}$ and penalize $\|f\|_{\mathcal{H}}$ for smoothness, where
$\mathcal{H}$ is a RKHS with reproducing kernel $K(\cdot,\cdot)$ and
$\|\cdot\|_{\mathcal{H}}$ is the Hilbert norm. Adding these restrictions and
applying Representer Theorem, problem (1) with the squared loss becomes

$\displaystyle\begin{split}\min_{\bm{\alpha}\in\mathcal{R}^{n}}&\frac{1}{2n}\sum_{i=1}^{n}(y_{i}-\bm{K}_{i}^{T}\bm{\alpha})^{2}=\frac{1}{2n}\|\bm{y}-K\bm{\alpha}\|_{2}^{2},\end{split}$
(2)

where $\bm{K}_{i}^{T}$ is the $i$th row of
$K:=K(X,X)=(K(\bm{x}_{i},\bm{x}_{j}))_{i,j}$. For a parameter $\bm{\alpha}$,
the corresponding estimator in $\mathcal{H}$ is
$f(\cdot)=\sum_{i=1}^{n}\alpha_{i}K(\bm{x}_{i},\cdot):=\bm{\alpha}^{T}K(\cdot,X)$.

Now when $K$ is invertible, it is trivial that any algorithm on objective
function (2) converges at the unique minimizer
$\bm{\hat{\alpha}}=K(X,X)^{-1}\bm{y}$, so the RKHS functional estimator is

$\displaystyle\hat{f}(\bm{x})=K(\bm{x},X)^{T}K(X,X)^{-1}\bm{y},$ (3)

where $K(\bm{x},X)^{T}=(K(\bm{x},\bm{x}_{1}),\ldots,K(\bm{x},\bm{x}_{n}))$.
Estimator (3) is the minimum norm interpolant, i.e.:

$\displaystyle\arg\min_{f\in\mathcal{H}}\\{\|f\|_{\mathcal{H}}:f(\bm{x}_{i})=y_{i},i=1,\ldots,n\\},$

whose properties are studied in [17].

In this work, we compare the convergence direction of SGD and GD to
$\hat{\alpha}$. Specifically, we consider a two-stage SGD with a phase
transition from a larger step-size to a decreased step-size. Note that this
matches the training scheme people always use in practice for SGD algorithms:
decreasing the step-size after training for a few epochs. For that purpose, in
the following sections, we define the one-step SGD/GD update and state our
assumptions and notations for analysis.

###  2.2 One step SGD/GD update

For objective function (2), denote the parameter estimation at $t$th step as
$\alpha_{t}$, then SGD update $\bm{\alpha}_{t+1}$ as

$\displaystyle\begin{split}\bm{\alpha}_{t+1}=\bm{\alpha}_{t}-\eta_{t}(\bm{K}_{i_{t}}^{T}\bm{\alpha}_{t}-y_{i_{t}})\cdot\bm{K}_{i_{t}},\end{split}$
(4)

where $i_{t}$ is uniformly random sampled from $\\{1,\ldots,n\\}$.

The GD update $\bm{\alpha}_{t+1}$ as

$\displaystyle\begin{split}\bm{\alpha}_{t+1}=\bm{\alpha}_{t}-\frac{\eta_{t}}{n}K^{T}(K\bm{\alpha}_{t}-\bm{y}).\end{split}$
(5)

###  2.3 Assumptions and Notations

We state our assumption on the Gram matrix as following:

######  Assumption 1 (Diagonally dominant Gram matrix).

Denote by $K=K(X,X)$ the Gram matrix, we assume that $K$ is diagonally
dominant. Specifically, suppose w.l.o.g. that $K_{1,1}\geq
K_{2,2}\geq\ldots\geq K_{n,n}>0$, then we have for a small value $\tau$ that

$|K_{i,j}|\leq\tau\ll K_{n,n},\forall i\neq j.$

######  Remark 1.

Diagonally dominant Gram matrix is common in kernel learning. Mathematically,
one can justify that a Gram matrix is diagonally dominant by imposing proper
assumptions on the kernel function $K(\cdot,\cdot)$ and the data distribution.
One can see Appendix B for some examples.

######  Remark 2.

Thinking of the kernel function as the inner product of high-dimensional
features, the resulting Gram matrix is diagonally dominant when the high-
dimension features are sparse. This happens in a lot of practical problems
[23, 28], for example, linear or string kernels being applied to text data
[11], domain-specific kernels being applied to image retrieval [25] and
bioinformatics [22], and the Global Alignment kernel being applied to most
datasets [9, 8].

######  Proposition 1 (Lemma 1 in [29]).

Consider the bilinear kernel
$K(\bm{x},\bm{x}^{\prime}):=\langle\bm{x},\bm{x}^{\prime}\rangle$. Assume the
data $\bm{x}_{i},i=1,\ldots,n$, are i.i.d. uniformly distributed on the unit
sphere $S^{d-1}$, where $d\gg n$. When $d\geq 4\log(2n^{2}/\delta)$ for some
$\delta\in(0,1)$. Then with probability at least $1-\delta$, we have

$|K_{i,j}|=|\langle\bm{x}_{i},\bm{x}_{j}\rangle|<\tilde{\tau}:=\tilde{\mathcal{O}}(1/\sqrt{d})\ll
K_{n,n}=1,\forall i\neq j.$

Though commonly exists, the diagonal dominance is undesired in classification
and clustering tasks. It indicates that the data points are dissimilar to each
other, which means not enough information for classification/clustering. There
are some efforts for solving the issue of diagonal dominance in these cases,
see for example [11, 16]. But for the regression task, the diagonal dominance,
in other words, the dissimilarity of data points, may have benefits. One can
find similar conditions such as Restricted Isometry Property and $s$-goodness
that describes linearly dissimilar features in a regression literature [5, 7].
Such conditions are required for proving minimax optimality or exact recovery
of a sparse signal in many settings. In our case, we adopt the dissimilarity
concept and apply it to data points in high-dimensional nonlinear feature
space. Later we will see that in our case, the directional bias drives SGD to
select a good solution that generalizes well among all solutions of the same
level of empirical loss. In this way, our SGD estimator benefits from the
diagonal dominance.

Notations. We use the following notations throughout this paper. For the Gram
matrix $K$, let $K_{i,j}$ denote its $(i,j)$th element. Denote
$\lambda_{i}=K_{i,i}=K(\bm{x}_{i},\bm{x}_{i})$, and assume w.l.o.g. that
$\lambda_{1}\geq\lambda_{2}\geq\ldots\geq\lambda_{n}$. Denote the $i$th column
of $K$ as $\bm{K}_{i}$, let $K_{-1}=[K_{2},\ldots,K_{n}]$. Denote $P_{-1}$ the
projection onto column space of $K_{-1}$, and $P_{1}=I-P_{-1}$. And denote
$\gamma_{1}\geq\ldots\geq\gamma_{n}>0$ the eigenvalues of $K$ in non-
increasing order.

##  3 Main result

The main results are presented in two subsections: Subsection 3.1 states the
directional bias results of SGD and GD estimators, respectively; Subsection
3.2 shows that certain directional bias leads to good generalization
performance, and applies this result to show that an outcome from SGD
potentially generalizes better than an outcome from GD.

###  3.1 Directional bias

By our assumption, $K$ will be full rank, (S)GD on (2) converges at
$\hat{\bm{\alpha}}=K^{-1}\bm{y}$. We are interested in the direction at which
$\bm{\alpha}_{t}$ converges to $\hat{\bm{\alpha}}$, i.e., the quantity

$\bm{b}_{t}:=\bm{\alpha}_{t}-\hat{\bm{\alpha}}.$

With Assumption 1 that the Gram matrix is diagonally dominant, we prove that a
two-stage SGD has $\bm{b}_{t}$ converge in the direction that is aligned with
the eigenvector associated with the largest eigenvalue of the Gram matrix $K$.

######  Theorem 1 (Directional bias of an SGD-based estimator).

Assume Assumption 1 holds, run a two-stage SGD with a fixed step-size for each
stage: stage 1 with step-size $\eta_{1}$ for steps $1,\ldots,k_{1}$, stage $2$
with step-size $\eta_{2}$ for steps $k_{1}+1,\ldots,k_{2}$, such that

$\displaystyle\frac{2}{\lambda_{1}^{2}-C_{1}\sqrt{n}\tau}<\eta_{1}<\frac{2}{\lambda_{2}^{2}+C_{2}\sqrt{n}\tau},$
$\displaystyle\eta_{2}<\frac{1}{\lambda_{1}^{2}+C_{3}\sqrt{n}\tau},$

where $C_{1},C_{2},C_{3}$ are constants. For a small $\epsilon>0$ such that
$n\tau<poly(\epsilon)$ there exists
$k_{1}=\mathcal{O}(\log\frac{1}{\epsilon})$ and $k_{2}$ such that

$(1-2\epsilon)\gamma_{1}\leq
E[\|K\bm{b}_{k_{2}}^{SGD}\|_{2}]/E[\|\bm{b}_{k_{2}}^{SGD}\|_{2}]\leq\gamma_{1}.$

That is, $\bm{b}_{k_{2}}^{SGD}$ is close to the direction of eigenvector
corresponding to the largest eigenvalue of $K$.

######  Remark 3.

One should assume $\tau$ in Assumption 1 to be small enough for $\epsilon$ to
be very small if one would like the resulting estimator $\bm{b}_{k_{2}}^{SGD}$
to have the direction that corresponds to the largest eigenvalue of $K$. Later
we will see that if one only wants different directional bias of SGD and GD
estimators, a moderate $\epsilon$ is allowed, the assumption on $\tau$ is not
that strong.

The proof for Theorem 1 is in Appendix E. Next, we see the different
convergence direction of GD.

######  Theorem 2 (Directional bias of a GD-based estimator).

Assume Assumption 1 holds, run GD with a fixed step-size $\eta$ such that

$\displaystyle\eta<n/(\lambda_{1}+n\tau)^{2}.$

For a $\epsilon^{\prime}>0$, let
$k=\mathcal{O}(\log\frac{1}{\epsilon^{\prime}})$, we have the GD estimator
after $k$ steps satisfying:

$\displaystyle\gamma_{n}\leq\|K\bm{b}_{k}^{GD}\|_{2}/\|\bm{b}_{k}^{GD}\|_{2}\leq\sqrt{1+\epsilon^{\prime}}\gamma_{n}.$

That is, $\bm{b}_{k}^{GD}$ is close to the direction that corresponds to the
smallest eigenvalue of $K$.

######  Remark 4.

The assumption (on $\tau$) is mild for differentiating the directional bias of
SGD and GD. Comparing Theorem 1 and 2,when
$\gamma_{n}<(1-2\epsilon)\gamma_{1}$, taking $k$ large enough we have

$\frac{\|K\bm{b}_{k}^{GD}\|_{2}}{\|\bm{b}_{k}^{GD}\|_{2}}<\frac{E\|K\bm{b}_{k_{2}}^{SGD}\|_{2}}{E\|\bm{b}_{k_{2}}^{SGD}\|_{2}}.$

That is, one may expect $\bm{b}_{k_{2}}^{SGD}$ to be in the direction of
larger eigenvalue compared with $\bm{b}_{k}^{GD}$. In the following
subsection, we will see that the directional bias towards a larger eigenvalue
of the kernel is good for generalization. That is, directional bias helps an
SGD-based estimator to generalize.

One can see the detailed proof of Theorem 2 in Appendix F. Though assumption 1
appears in Theorem 2, it is just used to bound the step-size so that GD
converges; the diagonally dominant structure of $K$ is not required. Moreover,
the choice of $\epsilon^{\prime}$ is independent of $\tau$, then for an
arbitrarily small $\epsilon^{\prime}>0$, run GD long enough then the theorem
will apply. The estimator $\bm{b}_{k}^{GD}$ can be arbitrarily close to the
eigenvector that correspond to the smallest eigenvalue.

Figure 1: Kernel regression on synthetic data. The first plot shows
directional bias by Rayleigh Quotient(RQ):=
$\|K\bm{b}\|_{2}^{2}/\|\bm{b}\|_{2}^{2}$. The SGD indeed converges in the
direction of a larger RQ, which matches our Theorems 1 and 2. In the third
plot we show the prediction error of the solution paths, and the SGD does have
lower prediction error than GD, even GD has smaller training loss than SGD.
This supports Theorem 4.

###  3.2 Effect of directional bias

In this subsection, the estimator that is biased towards the largest
eigenvalue of the Hessian is shown to be the best for parameter estimation,
see Theorem 3. Later we define a realizable problem setting of kernel
regression where the generalization error depends on the parameter estimation
error, and in this way, the directional bias helps an SGD-based estimator to
generalize.

######  Theorem 3.

Consider minimizing the quadratic loss function

$L(\bm{w})=\|A\bm{w}-\bm{y}\|_{2}^{2}.$

Assume there is a ground truth $\bm{w}^{*}$ such that $\bm{y}=A\bm{w}^{*}$.
For a fixed level of the quadratic loss, the parameter estimation error
$\|\bm{w}-\bm{w}^{*}\|_{2}^{2}$ has a lower bound:

$\forall\bm{w}\in\\{\bm{w}:L(\bm{w})=a\\}:\|\bm{w}-\bm{w}^{*}\|_{2}^{2}\geq
a/\|A^{T}A\|_{2}.$

Moreover, the equality is obtained when $\bm{w}-\bm{w}^{*}$ is in the
direction of the eigenvector that corresponds to the largest eigenvalue of
matrix $A^{T}A$.

######  Remark 5.

Theorem 3 implies that the directional bias towards the largest eigenvalue is
good for parameter estimation. As discussed in Remark 4, the SGD-based
estimator is biased towards a larger eigenvalue compared to the GD-based
estimator, by Theorem 3 the SGD estimator potentialy better estimates the true
parameter and thus generalizes better, which we will formalize later.

Suppose $\exists f^{*}\in\mathcal{H}$ such that $y=f^{*}(\bm{x})$. Consider
the generalization error $L_{D}(f):=\|f-f^{*}\|_{\mathcal{H}}^{2}$. For an
algorithm output $f^{\mbox{alg}}$, we decompose its generalization error as:

$\displaystyle L_{D}(f^{\mbox{alg}})-\inf_{f\in\mathcal{H}}L_{D}(f)$
$\displaystyle=$
$\displaystyle\underbrace{L_{D}(f^{\mbox{alg}})-\inf_{f\in\mathcal{H}_{s}}L_{D}(f)}_{:=\Delta(f^{\mbox{alg}}),\text{
estimation
error}}+\underbrace{\inf_{f\in\mathcal{H}_{s}}L_{D}(f)-\inf_{f\in\mathcal{H}}L_{D}(f)}_{\text{approximation
error}},$

where $\mathcal{H}_{s}$ is the hypothesis class that the output of the
algorithm is restricted to. By formulation (2), we have $\mathcal{H}_{s}$:

$\mathcal{H}_{s}=\\{f\in\mathcal{H}:f=\bm{\alpha}^{T}K(\cdot,X),\bm{\alpha}\in\mathcal{R}^{n}\\}.$

We define the $a$-level set of training loss:

$\nu_{a}=\\{f\in\mathcal{H}_{s}:f=\bm{\alpha}^{T}K(\cdot,X),\frac{1}{2n}\|K\bm{\alpha}-\bm{y}\|_{2}^{2}=a\\},$

and denote $\Delta_{a}^{*}:=\inf_{f\in\nu_{a}}\Delta(f)$.

Note that the approximation error can not be improved unless we change the
hypothesis class, which is, changing the problem formulation in our case. So
we just minimize the estimation error for estimators that are in the $a$-level
set. One can check the estimation error is given by

$f\in\mathcal{H}_{s}:\Delta(f)=\bm{b}^{T}K\bm{b},$

where $\bm{b}=\bm{\alpha}-\hat{\bm{\alpha}}$, seeing details in Appendix G.2.
Similar to Theorem 3, the estimation error is minimized when $\bm{b}$ is in
the direction of the largest eigenvalue of $K$, so the directional bias
towards a larger eigenvalue helps to generalize in kernel regression. We
compare the estimation error of SGD and GD in following theorem.

######  Theorem 4 (Generalization performance).

Follow Theorems 1 and 2, we have the following:

  * •

The output of SGD has
$E[\Delta^{1/2}(f^{SGD})]\leq(1+4\epsilon)(\Delta_{a}^{*})^{1/2}$, where $a$
is such that $E[\|K\bm{\alpha}^{SGD}-y\|_{2}]^{2}=2na$ and $\epsilon$ could be
any positive small constant;

  * •

The output of GD has $\Delta(f^{GD})\geq M\Delta_{a}^{*}$, where $a$ is the
training loss of GD estimator, and
$M=\frac{\gamma_{1}}{\gamma_{n}}(1-\epsilon^{\prime})>1$ is a large constant.

######  Remark 6.

This theorem indicates that $E[\Delta^{1/2}(f^{SGD})]\leq\Delta^{1/2}(f^{GD})$
when $1+4\epsilon\leq M^{1/2}$. Taking
$\epsilon<(\sqrt{\gamma_{1}/\gamma_{n}}-1)/4$ in Theorem 1 and combining with
Theorem 2 which states that $\epsilon^{\prime}\stackrel{{\scriptstyle
k\to\infty}}{{\longrightarrow}}0$, we will have $1+4\epsilon\leq M^{1/2}$
holds. In this way, $\Delta(f^{SGD})<\Delta(f^{GD})$ with high probability.
This finishes our claim that SGD generalizes better than GD.

(a) Relative Rayleigh Quotient.

(b) Test accuracy

Figure 2: The experiment of a small ResNet on FashionMNIST. In (a), we follow
[29] to use the Relative Rayleigh Quotient(RRQ) as the measurement of the
convergence direction. The SGD with moderate step-size has higher RRQ than the
GD with either moderate step-size or small step-size, which supports the
theory in Theorems 1 and 2. It is interesting to observe that SGD with a small
step-size has a different directional bias compared with SGD with a moderate
step-size, indicating that the directional bias studied in this work does not
hold for a general SGD. In (b), we plot the testing accuracy from $20$
repetitions of experiments, the test accuracy (inside bracket) of SGD with
moderate step-size is higher than the other cases, and we have Wilcoxon
signed-rank test to confirm that the difference is significant at $0.01$
level. The test accuracy validates Theorem 4. For more details of the
experiments, the rank test, and more experiments, see Appendix H.2.

##  4 Numeric Study

Simulation. We simulate data from a nonlinear regression model with Gaussian
additive noise as $y_{i}=\sum_{j=1}^{100}\sin(x_{i,j})+\epsilon_{i}$, where
$x_{i,j}\sim N(0,1)$ and $\epsilon_{i}\sim N(0,0.01)$. We fit kernel
regression using the polynomial kernel
$K(\bm{x}_{1},\bm{x}_{2})=(\langle\bm{x}_{1},\bm{x}_{2}\rangle+.01)^{2}$ on
$10$ training data and test the estimator on $5$ testing data. We run both SGD
and GD for two step-size schemes: small step-size, and moderate annealing
step-size. The results are in Fig. 1.

Real data experiment. We run a 6-layer ResNet [13] on FashionMNIST. The
network structure is

Input $\displaystyle\Rightarrow 7\times 7\text{ Conv
}\Rightarrow\text{BatchNorm}\Rightarrow\text{ReLU}$ $\displaystyle\Rightarrow
3\times 3\text{ MaxPool
}\Rightarrow\text{ResBlock1}\Rightarrow\text{ResBlock2}$
$\displaystyle\Rightarrow\text{Global
AvePool}\Rightarrow\text{FC}\Rightarrow\text{output}.$

We run SGD and GD for two step-size schemes, similar to our simulation. There
are $1,500$ training data and $10,000$ testing data in our experiment. The
result is in Fig. 2.

######  Remark 7.

The purposes of experiment using a Neural Network (Fig. 2) are: first, the
Neural Network results support our finding on kernel regression, since Neural
Network is related to kernel regression through NTK theory [15]; second, our
experiment indicates that our result may be empirically true for the more
general deep learning framework [3].

##  5 Discussion and Further Work

We advance one more step towards understanding the directional bias of SGD in
kernel learning. We discuss some implications of our results.

Implication to the SGD scheme: Our result shows the directional bias holds to
SGD with annealing step-size. Specifically, the first stage of SGD with
moderate step-size should run long enough, then in the second stage by
decreasing step-size we have the directional bias towards the largest
eigenvalue of the Hessian, which helps in obtaining a better generalization
error bound. This explains a technique for tuning the learning rate that
people adopt in practice: starting with a large step-size, running long enough
until the error plateaus, then decreasing the step-size [13]. Although this
technique is always used for speed convergence, we show that it also helps in
predictive power, which becomes even better.

Implication to deep learning: Our assumption in the analysis implies certain
structures for the deep learning models. Per our discussion in Remark 2, our
assumption holds when the feature space is high dimensional and/or when
features are possibly sparse. This matches the deep learning scenario where we
have a highly overparameterized model and when the trained parameter estimator
becomes sparse. In addition, considering that some deep learning tasks can be
approximated by kernel learning [15], our results help to explain why the SGD-
based estimator can perform better in an overparameterized deep learning
setting.

Just as stated in [3], to understand deep learning one needs to understand
kernel learning. This work improves our understanding in kernel learning, and
can possibly lead to deep understanding of practices in deep learning.

## References

  * [1] Alnur Ali, Edgar Dobriban and Ryan Tibshirani  “The implicit regularization of stochastic gradient flow for least squares”  In _International Conference on Machine Learning_ , 2020, pp. 233–244  PMLR
  * [2] Peter L. Bartlett, Andrea Montanari and Alexander Rakhlin  “Deep learning: a statistical viewpoint”  In _arXiv:2103.09177_ , 2021
  * [3] Mikhail Belkin, Siyuan Ma and Soumik Mandal  “To understand deep learning we need to understand kernel learning”  In _International Conference on Machine Learning_ , 2018, pp. 541–549  PMLR
  * [4] Guy Blanc, Neha Gupta, Gregory Valiant and Paul Valiant  “Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like process”  In _Proceedings of Thirty Third Conference on Learning Theory_ , 2020, pp. 483–513
  * [5] Emmanuel Candes and Terence Tao  “The Dantzig selector: Statistical estimation when p is much larger than n”  In _The annals of Statistics_ 35.6 Institute of Mathematical Statistics, 2007, pp. 2313–2351
  * [6] Yuan Cao et al.  “Towards Understanding the Spectral Bias of Deep Learning”  In _arXiv:1912.01198_ , 2020
  * [7] Shaobing Chen and David Donoho  “Basis pursuit”  In _Asilomar Conference on Signals, Systems and Computers_ 1, 1994, pp. 41–44  IEEE
  * [8] Marco Cuturi  “Fast global alignment kernels”  In _International Conference on Machine Learning_ , 2011, pp. 929–936
  * [9] Marco Cuturi, Jean-Philippe Vert, Oystein Birkenes and Tomoko Matsui  “A kernel for time series based on global alignments”  In _ICASSP’07_ , 2007  IEEE
  * [10] Michal Derezinski, Feynman T Liang and Michael W Mahoney  “Exact expressions for double descent and implicit regularization via surrogate random design”  In _Advances in Neural Information Processing Systems_ , 2020, pp. 5152–5164
  * [11] Derek Greene and Pádraig Cunningham  “Practical solutions to the problem of diagonal dominance in kernel document clustering”  In _International Conference on Machine Learning_ , 2006, pp. 377–384
  * [12] Hussein Hazimeh, Rahul Mazumder and Peter Radchenko  “Grouped Variable Selection with Discrete Optimization: Computational and Statistical Perspectives”  In _arXiv:2104.07084_ , 2021
  * [13] Kaiming He, Xiangyu Zhang, Shaoqing Ren and Jian Sun  “Deep Residual Learning for Image Recognition”  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2016
  * [14] Roger A Horn and Charles R Johnson  “Matrix analysis”  Cambridge university press, 2012
  * [15] Arthur Jacot, Franck Gabriel and Clement Hongler  “Neural Tangent Kernel: Convergence and Generalization in Neural Networks”, 2018
  * [16] Jaz Kandola, Thore Graepel and John Shawe-Taylor  “Reducing kernel matrix diagonal dominance using semi-definite programming”  In _Learning Theory and Kernel Machines_ Springer, 2003, pp. 288–302
  * [17] Tengyuan Liang and Alexander Rakhlin  “Just Interpolate: Kernel ‘Ridgeless’ Regression Can Generalize”  In _The Annals of Statistics_ 48.3, 2020, pp. 1329–1347
  * [18] Tianyi Liu, Zhehui Chen, Enlu Zhou and Tuo Zhao  “A Diffusion Approximation Theory of Momentum SGD in Nonconvex Optimization”  In _arXiv:1802.05155_ , 2018
  * [19] Siyuan Ma, Raef Bassily and Mikhail Belkin  “The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning”  In _arXiv:1712.06559_ , 2018
  * [20] Rahul Parhi and Robert D. Nowak  “What Kinds of Functions do Deep Neural Networks Learn? Insights from Variational Spline Theory”  In _arXiv:2105.03361_ , 2021
  * [21] Garvesh Raskutti, Martin J Wainwright and Bin Yu  “Minimax-Optimal Rates For Sparse Additive Models Over Kernel Classes Via Convex Programming.”  In _Journal of Machine Learning Research_ 13.2, 2012
  * [22] Hiroto Saigo, Jean-Philippe Vert, Nobuhisa Ueda and Tatsuya Akutsu  “Protein homology detection using string alignment kernels”  In _Bioinformatics_ 20.11 Oxford University Press, 2004, pp. 1682–1689
  * [23] Bernhard Schölkopf et al.  “A kernel approach for learning from almost orthogonal patterns”  In _European Conference on Machine Learning_ , 2002, pp. 511–528  Springer
  * [24] Hiroyuki Takeda, Sina Farsiu and Peyman Milanfar  “Kernel regression for image processing and reconstruction”  In _IEEE Transactions on image processing_ 16.2 IEEE, 2007, pp. 349–366
  * [25] Qingping Tao et al.  “An extended kernel for generalized multiple-instance learning”  In _16th IEEE International Conference on Tools with Artificial Intelligence_ , 2004, pp. 272–277  IEEE
  * [26] Tomas Vaskevicius, Varun Kanade and Patrick Rebeschini  “Implicit Regularization for Optimal Sparse Recovery”  In _Advances in Neural Information Processing Systems_ , 2019
  * [27] Grace Wahba  “Spline models for observational data”  SIAM, 1990
  * [28] Jason Weston et al.  “Dealing with large diagonals in kernel matrices”  In _Annals of the institute of statistical mathematics_ 55.2 Springer, 2003, pp. 391–408
  * [29] Jingfeng Wu, Difan Zou, Vladimir Braverman and Quanquan Gu  “Direction Matters: On the Implicit Bias of Stochastic Gradient Descent with Moderate Learning Rate”  In _International Conference on Learning Representations_ , 2021
  * [30] Aston Zhang, Zachary C. Lipton, Mu Li and Alexander J. Smola  “Dive into Deep Learning”  In _arXiv:2106.11342_ , 2021
  * [31] Peng Zhao, Yun Yang and Qiao-Chu He  “Implicit regularization via Hadamard product over-parametrization in high-dimensional linear regression”  In _arXiv:1903.09367_ , 2019

##  Appendix A Background on RKHS

This section details the background on RKHS in two subsections. The first
subsection includes notations, theorems, and an example of RKHS, the second
section reduces the kernel regression in RKHS from infinite dimension to
finite dimension, which gives our objective function (2) .

###  A.1 Nonparametric model in RKHS

In this subsection, we give the definition and notations for our model in
RKHS, and its associated norms, basis, etc. The definitions are similar to
those in [21].

Given $n$ data pairs $\\{\bm{x}_{i},y_{i}\\}_{i=1}^{n}$, where
$\bm{x}_{i}\in\mathcal{X}\subset\mathcal{R}^{p}$ and $y_{i}\in\mathcal{R}$,
assume that $y_{i}$s are associated with $\bm{x}_{i}$s through
$f(\bm{x}_{i})$, where $f(\cdot)$ is some unknown function in the reproducing
kernel Hilbert space (RKHS) of functions $\mathcal{X}\to\mathcal{R}$, our goal
is to estimate the function $f(\cdot)$ from the data.

Denote the RKHS where $f$ lives as $\mathcal{H}$, with reproducing kernel
$K:\mathcal{X}\times\mathcal{X}\to\mathcal{R}_{+}$ (which is known to us). And
we associate the functions in $\mathcal{H}$ with probability measure
$\mathbbm{Q}$, assume w.l.o.g. that
$\int_{\mathcal{R}^{p}}f(\bm{a})d\mathbbm{Q}(\bm{a})=0$. By Mercer’s theorem,
$K$ has eigen-expansion:

$K(\bm{a},\bm{b})=\sum_{j=1}^{\infty}\gamma_{j}\phi_{j}(\bm{a})\phi_{j}(\bm{b})$

Where $\\{\phi_{j}\\}_{j=1}^{\infty}$ are orthonormal basis in
$\mathbbm{L}^{2}(\mathbbm{Q})$, w.r.t. the usual inner product in
$\mathbbm{L}^{2}(\mathbbm{Q})$ as

$\langle
g(\cdot),h(\cdot)\rangle_{\mathbbm{L}^{2}(\mathbbm{Q})}=\int_{\mathcal{X}}g(\bm{a})h(\bm{a})d\mathbbm{Q}(\bm{a})$

Now for any $f\in\mathcal{H}$, we can expand
$f(\cdot)=\sum_{j=1}^{\infty}c_{j}\phi_{j}(\cdot)$, where $c_{j}=\langle
f(\cdot),\phi_{j}(\cdot)\rangle_{\mathbbm{L}^{2}(\mathbbm{Q})}$. And for
$f(\cdot)=\sum_{j=1}^{\infty}c_{j}\phi_{j}(\cdot)$,
$g(\cdot)=\sum_{j=1}^{\infty}c^{\prime}_{j}\phi_{j}(\cdot)$, by Parseval’s
theorem

$\langle
f(\cdot),g(\cdot)\rangle_{\mathbbm{L}^{2}(\mathbbm{Q})}=\sum_{j=1}^{\infty}c_{j}c^{\prime}_{j}$

And we have another inner product that is defined for RKHS $\mathcal{H}$ as

$\langle
f(\cdot),g(\cdot)\rangle_{\mathcal{H}}=\sum_{j=1}^{\infty}\frac{c_{j}c^{\prime}_{j}}{\gamma_{j}}$

The reproducing property of RKHS says that $\forall f\in\mathcal{H}$, we have

$\displaystyle\langle f(\cdot),K(\cdot,\bm{x})\rangle_{\mathcal{H}}=f(\bm{x})$

Cubic Splines Formulate a RKHS. We go over an example of RKHS for better
understanding. Consider the cubic spline of one dimension, we can show that
the space of cubic splines is a RKHS. One can also find the cubic spline
example in [12]. For more details on the relationship between polynomial
smoothing splines and RKHS, one can check Section 1.2 of [27] .

Assume w.l.o.g. that $x_{i}\in\mathcal{X}=[0,1]\subset\mathcal{R}$. The cubic
spline $f$ on $\mathcal{X}$ is continuous, has a continuous first-order
derivative and square integrable second order derivative. By Taylor’s theorem
with remainder, we have

$\displaystyle f(t)$
$\displaystyle=f(0)+tf^{\prime}(0)+\int_{0}^{t}(t-u)f^{\prime\prime}(u)du$
$\displaystyle=f(0)+tf^{\prime}(0)+\int_{0}^{1}(t-u)_{+}f^{\prime\prime}(u)du$

where $(t-u)_{+}=\max\\{0,t-u\\}$. Let $\mathcal{B}$ be the set of cubic
splines $f$ on $[0,1]$ that satisfies the boundary condition
$f(0)=f^{\prime}(0)=0$, then for $f\in\mathcal{B}$

$\displaystyle f(t)=\int_{0}^{1}(t-u)_{+}f^{\prime\prime}(u)du$

Let $G(t,u)=(t-u)_{+}$, then we claim that $\mathcal{B}$ is RKHS with
reproducing kernel

$\displaystyle K(s,t)=\int_{0}^{1}G(s,u)G(t,u)du$

and inner product

$\displaystyle\langle
f,g\rangle_{\mathcal{B}}=\int_{0}^{1}f^{\prime\prime}(u)g^{\prime\prime}(u)du$

as one can check the reproducing property

$\displaystyle\langle f(\cdot),K(\cdot,t)\rangle_{\mathcal{B}}$
$\displaystyle=\int_{0}^{1}\frac{\partial^{2}K(u,t)}{\partial
u^{2}}f^{\prime\prime}(u)du$
$\displaystyle=\int_{0}^{1}(t-u)_{+}f^{\prime\prime}(u)du=f(t)$

###  A.2 Optimization problem considered

This subsection gives problem formulation of kernel regression. Given data
pairs $\\{\bm{x}_{i},y_{i}\\}_{i=1}^{n}$ and RKHS $\mathcal{H}$, consider a
loss function $\ell$ which is selected according to how $y$ is connected with
$f(\bm{x})$, we may estimate the model by

$\displaystyle\min_{f\in\mathcal{H}}\frac{1}{n}\sum_{i=1}^{n}\ell(y_{i},f(\bm{x}_{i}))$
(6) $\displaystyle=$
$\displaystyle\min_{c_{j}}\frac{1}{n}\sum_{i=1}^{n}\ell(y_{i},\sum_{j=1}^{\infty}c_{j}\phi_{j}(\bm{x}_{i}))$

Example for $\ell$ includes

  * •

Squared error loss $\ell(y,f)=(y-f)^{2}$, which is usually used in regression;

  * •

0-1 loss $\ell(y,f)=\mathbf{1}(y*f>0)$, for binary classification;

  * •

Logistic loss $\ell_{(}y,f)=\log(1+\exp(-y*f))$, also a loss function for
classification, can be considered as a surrogate function of 0-1 loss, and is
the same as negative log likelihood function in logistic regression.

Let us come back to the nonparametric model part, to control the model
smoothness, the usual practice is to add a penalty to objective (6), result in

$\displaystyle\begin{split}&\min_{f\in\mathcal{H}}\sum_{i=1}^{n}\ell(y_{i},f(\bm{x}_{i}))+\lambda\text{pen}(f)\end{split}$

A popular choice of $\text{pen}(f)$ is $\|f\|_{\mathcal{H}}^{2}$, or any
strictly increasing function of $\|f\|_{\mathcal{H}}^{2}$. Such method is
explicitly controlling the model smoothness, and by Representer Theorem, it
has solution of the form

$\displaystyle{f}(\cdot)=\sum_{i=1}^{n}\alpha_{i}K(\cdot,\bm{x}_{i})$ (7)

Plug equation (7) into objective (6), we have the problem becomes

$\min_{\alpha_{i^{\prime}}}\frac{1}{n}\sum_{i=1}^{n}\ell(y_{i},\sum_{i^{\prime}=1}^{n}\alpha_{i^{\prime}}K(\bm{x}_{i},\bm{x}_{i^{\prime}}))$

Which gives the formulation (2) under loss function
$\ell(y,f(\bm{x}))=(y-f(\bm{x}))^{2}/2$.

##  Appendix B Diagonal Dominance of Some Popular Kernels

In this section, we justify Assumption 1 by figuring out a problem setting
where some popular kernels give a diagonal dominant Gram matrix. For
simplicity, we assume the following data distribution throughout this section:

$\displaystyle\text{$\mathbf{x}_{i}\in R^{d},i=1,\ldots,n$, are normalized
such that $\|\bm{x}_{i}\|_{2}^{2}=1$};$ (8a) $\displaystyle\text{The direction
of $\bm{x}_{i}$s are i.i.d. uniformly distributed on the unit sphere
$S^{d-1}$};$ (8b) $d\gg n$ (overparameterized setting). (8c)

Given assumption set (8), we can bound the inner product of data
$\langle\bm{x}_{i},\bm{x}_{j}\rangle$ with high probability as follows:

######  Lemma 1 (Lemma 1 in [29]).

Under assumption set (8), let $d\geq 4\log(2n^{2}/\delta)$ for some
$\delta\in(0,1)$. Then with probability at least $1-\delta$, we have

$|\langle\bm{x}_{i},\bm{x}_{j}\rangle|<\tilde{\tau}:=\tilde{\mathcal{O}}(\frac{1}{\sqrt{d}}),\forall
i\neq j$

###### Proof.

See proof of Lemma 1 in [29]. ∎

The bound on the inner product $\langle\bm{x}_{i},\bm{x}_{j}\rangle$ induces
bound on $K(\bm{x}_{i},\bm{x}_{j})$ for some popular kernels. We show the
diagonal dominance for two groups of kernels in the following propositions,
and list some examples for kernels in each group.

######  Proposition 2 (Inner product kernel).

The inner product kernel is defined as a smooth transformation of inner
product. We can write it as:

$K(\bm{x}_{i},\bm{x}_{j})=g(\langle\bm{x}_{i},\bm{x}_{j}\rangle)$

Assume assumptions (8) hold, and assume the function $g:[-1,1]\to R$
satisfies:

$\displaystyle g\text{ is convex};$ (9a) $\displaystyle\text{$g$ is
$L-$smooth, that is, $\nabla g$ is $L-$Lipschitz continuous};$ (9b)
$\displaystyle|g(0)|\leq c\tilde{\tau}\text{ for a constant
$c$},g^{\prime}(0)\geq 0.$ (9c)

we will have with probability $1-\delta$

$\displaystyle|K_{i,j}|\leq(c+g^{\prime}(0))\tilde{\tau}+\frac{L}{2}\tilde{\tau}^{2}\text{
for }i\neq j$ (10)

where $\delta$ and $\tilde{\tau}$ the same as in Lemma 1.When
$g^{\prime}(0)\tilde{\tau}+\frac{L}{2}\tilde{\tau}^{2}\ll g(1)$ for a small
enough $\tilde{\tau}$, the Gram matrix is diagonal dominant.

###### Proof.

We have the following with probability at least $1-\delta$ by Lemma 1. For any
off-diagonal elements of $K$:

$\displaystyle\begin{split}K_{i,j}&=g(\langle\bm{x}_{i},\bm{x}_{j}\rangle)\\\
&\geq g(0)+g^{\prime}(0)\langle\bm{x}_{i},\bm{x}_{j}\rangle\\\
&\geq-(g^{\prime}(0)+c)\tilde{\tau}\end{split}$

and

$\displaystyle\begin{split}K_{i,j}&=g(\langle\bm{x}_{i},\bm{x}_{j}\rangle)\\\
&\leq
g(0)+g^{\prime}(0)\langle\bm{x}_{i},\bm{x}_{j}\rangle+\frac{L}{2}\langle\bm{x}_{i},\bm{x}_{j}\rangle^{2}\\\
&\leq(c+g^{\prime}(0))\tilde{\tau}+\frac{L}{2}\tilde{\tau}^{2}\end{split}$

Thus $|K_{i,j}|\leq(c+g^{\prime}(0))\tilde{\tau}+\frac{L}{2}\tilde{\tau}^{2}$.
∎

######  Remark 8.

We list some examples of inner product kernels that give diagonal dominant
kernel matrices:

  * •

Bilinear Kernel:
$K(\bm{x},\bm{x}^{\prime})=\langle\bm{x},\bm{x}^{\prime}\rangle$, then

$|K(\bm{x}_{i},\bm{x}_{j})|\leq\tilde{\tau}\ll K(\bm{x}_{n},\bm{x}_{n})=1.$

  * •

Polynomial Kernel:
$K(\bm{x},\bm{x}^{\prime})=(\langle\bm{x},\bm{x}^{\prime}\rangle+c)^{m}$ for
$m\in\mathbbm{N}$ and $c\sim\mathcal{O}(\tilde{\tau})$, then by Proposition 2

$|K(\bm{x}_{i},\bm{x}_{j})|\leq(1+m)\tilde{\tau}+\frac{m*\exp((m-1)\tilde{\tau})}{2}\tilde{\tau}^{2}$

when
$(1+m)\tilde{\tau}+\frac{m*\exp((m-1)\tilde{\tau})}{2}\tilde{\tau}^{2}\ll(1+c)^{m}$,
we have diagonal dominant Gram matrix.

  * •

Hyperbolic Tangent Kernel (Sigmoid Kernel):
$K(\bm{x},\bm{x}^{\prime})=\tanh(\alpha\langle\bm{x},\bm{x}^{\prime}\rangle+c)$,
where $\alpha>0,c\geq 0$. Note that Hyperbolic Tangent Kernel does not satisfy
all the assumptions in Proposition 2, one can still calculate

$|K(\bm{x}_{i},\bm{x}_{j})|\leq\tanh(\alpha\tilde{\tau}+c)$

and

$K(\bm{x}_{k},\bm{x}_{k})=\tanh(\alpha+c)$

When $\tanh(\alpha\tilde{\tau}+c)\ll\tanh(\alpha+c)$ (which is the case when
$\alpha$ is large, and $c,\tilde{\tau}$ are small enough), we have
$|K(\bm{x}_{i},\bm{x}_{j})|\ll K(\bm{x}_{n},\bm{x}_{n})$ and the Gram matrix
is diagonal dominant.

######  Proposition 3 (Radial Basis Function (RBF) kernel).

Radial Basis Function kernel depends on two data points through their
distance, which is of following form

$K(\bm{x}_{i},\bm{x}_{j})=\exp(-\gamma\|\bm{x}_{i}-\bm{x}_{j}\|_{2}^{2}),\gamma>0$

Assume assumptions (8) hold, when $\gamma=-c_{0}\log(\tilde{\tau})$ for a
constant $c_{0}$, we have with probability $1-\delta$

$\displaystyle|K_{i,j}|\leq\tilde{\tau}^{2c_{0}(1-\tilde{\tau})}\ll
K_{n,n}=1,\text{ for }i\neq j$

where $\delta$ and $\tilde{\tau}$ the same as in Lemma 1. That is, the Gram
matrix is diagonal dominant.

###### Proof.

Bound off-diagonal terms of $K$ by Lemma 1:

$\displaystyle\begin{split}K_{i,j}&=\exp(-\gamma\|\bm{x}_{i}-\bm{x}_{j}\|_{2}^{2})\\\
&\leq\exp(2\gamma\tilde{\tau}-2\gamma)\\\ &\
=\tilde{\tau}^{2c_{0}(1-\tilde{\tau})}\end{split}$

∎

######  Remark 9.

We note some popular kernels that are related to Radial Basis Function kernel,
and show that they lead to diagonal dominance:

  * •

Gaussian Kernel:
$K(\bm{x},\bm{x}^{\prime})=\exp(-\frac{\|\bm{x}-\bm{x}^{\prime}\|_{2}^{2}}{2\sigma^{2}})$.
One can see that Gaussian Kernel is reparameterizing RBF Kernel by
$\gamma=1/(2\sigma^{2})$. Thus Gaussian Gram matrix is diagonal dominant when
$\sigma^{2}\sim\mathcal{O}(-\frac{1}{\log(\tilde{\tau})})$.

  * •

Laplace Kernel:
$K(\bm{x},\bm{x}^{\prime})=\exp(-\frac{\|\bm{x}-\bm{x}^{\prime}\|_{2}}{\sigma})$
for $\sigma>0$. The Laplace Kernel is very similar to Gaussian Kernel, and one
can check by similar steps that when
$\sigma\sim\mathcal{O}(-\frac{1}{\log(\tilde{\tau})})$, Laplace Gram matrix is
diagonal dominant.

##  Appendix C Lemmas

This section includes two useful lemmas for characterizing the eigenvalues of
a symmetric matrix.

######  Lemma 2 (Gershgorin circle theorem, restated for symmetric matrix).

Let $A\in\mathcal{R}^{n\times n}$ be a symmetric matrix. Let $A_{ij}$ be the
entry in the $i-$th row and the $j-$th column. Let

$R_{i}(A):=\sum_{j\neq i}|A_{ij}|,i=1,\ldots,n$

Consider n Gershgorin discs

$D_{i}(A):=\\{z\in\mathcal{R},|z-A_{ii}|\leq R_{i}(A)\\},i=1,\ldots,n$

The eigenvalues of A are in the union of Gershgorin discs

$G(A):=\cup_{i=1}^{n}D_{i}(A)$

Furthermore, if the union of $k$ of the $n$ discs that comprise $G(A)$ forms a
set $G_{k}(A)$ that is disjoint from the remaining $n-k$ discs, then
$G_{k}(A)$ contains exactly $k$ eigenvalues of $A$, counted according to their
algebraic multiplicities.

###### Proof.

See [14], Chap 6.1, Theorem 6.1.1. ∎

######  Lemma 3 (Cauchy interlacing theorem, restated for symmetric matrix).

Let $B\in\mathcal{R}^{m\times m}$ be a symmetric matrix, let
$\bm{y}\in\mathcal{R}^{n}$ and $a\in\mathcal{R}$, and let
$A=\begin{bmatrix}B&\bm{y}\\\ \bm{y}^{T}&a\end{bmatrix}$. Then

$\displaystyle\lambda_{1}(A)\geq\lambda_{1}(B)\geq\lambda_{2}(A)\geq\ldots\geq\lambda_{m}(A)\geq\lambda_{m}(B)\geq\lambda_{m+1}(A).$

###### Proof.

See [14], Chap 4.3, Theorem 4.3.17. ∎

##  Appendix D Spectrum of Gram matrix

This section analyzes the eigen structure of the Gram matrix.

######  Lemma 4 (Characterizing $K^{2}$).

Under Assumption 1, we have

$\displaystyle\langle\bm{K}_{i},\bm{K}_{i}\rangle\in[\lambda_{i}^{2},\lambda_{i}^{2}+(n-1)\tau^{2}]$
(11)
$\displaystyle|\langle\bm{K}_{i},\bm{K}_{j}\rangle|\leq[2\lambda_{1}+(n-2)\tau]\tau,i\neq
j$ (12)

###### Proof.

For $\langle\bm{K}_{i},\bm{K}_{i}\rangle$

$\displaystyle\langle\bm{K}_{i},\bm{K}_{i}\rangle$
$\displaystyle=K_{i,i}^{2}+\sum_{l\neq i}K_{l,i}^{2}$
$\displaystyle\in[\lambda_{i}^{2},\lambda_{i}^{2}+(n-1)\tau^{2}]$

And for $\langle\bm{K}_{i},\bm{K}_{j}\rangle,i\neq j$

$\displaystyle\begin{split}|\langle\bm{K}_{i},\bm{K}_{j}\rangle|&=|\sum_{l=1}^{n}K_{l,i}K_{l,j}|\\\
&=|K_{i,i}K_{i,j}+K_{j,i}K_{j,j}+\sum_{l\neq i,j}K_{l,i}K_{l,j}|\\\
&\leq|K_{i,i}K_{i,j}|+|K_{j,i}K_{j,j}|+\sum_{l\neq i,j}|K_{l,i}K_{l,j}|\\\
&\leq[\lambda_{i}+\lambda_{j}]\tau+(n-2)\tau^{2}\\\
&\leq[2\lambda_{1}+(n-2)\tau]\tau\end{split}$

∎

######  Lemma 5 (Eigenvalue of $K$).

Under Assumption 1, we have

$\displaystyle\gamma_{1}\leq\lambda_{1}+n\tau$ (13)
$\displaystyle\gamma_{n}\geq\lambda_{n}-n\tau$ (14)

If we further assume $\lambda_{j}+n\tau<\lambda_{j-1}-n\tau$, we will have

$\displaystyle\gamma_{j-1}\geq\lambda_{j-1}-n\tau>\lambda_{j}+n\tau\geq\gamma_{j}.$

###### Proof.

Use Gershgorin circle theorem, calculate

$\displaystyle R_{i}(K)=\sum_{j\neq i}|K_{i,j}|\leq n\tau$

then

$\displaystyle D_{i}(K)\subset[\lambda_{i}-n\tau,\lambda_{i}+n\tau].$

By Gershgorin circle theorem, the lemma claim holds. ∎

######  Lemma 6 (Characterize $P_{1}K$ and $P_{-1}K$).

Recall our definition: $P_{-1}$ is the projection on column space of
$K_{-1}=[\bm{K}_{2},\bm{K}_{3},\ldots,\bm{K}_{n}]$, and $P_{1}=I-P_{-1}$. We
claim the following hold

$\displaystyle P_{1}K$ $\displaystyle=[P_{1}\bm{K}_{1},\bm{0},\ldots,\bm{0}]$
(15) $\displaystyle P_{-1}K$
$\displaystyle=[P_{-1}\bm{K}_{1},\bm{K}_{2},\ldots,\bm{K}_{n}]$ (16)

Assume $\tau$ is small enough that $n\tau\leq\mathcal{O}(1)$,
$\lambda_{n}-n\tau\geq c_{1}>0$ and $\lambda_{1}+n\tau\leq c_{2}$, let
$c_{3}:=\frac{c_{2}}{c_{1}^{2}}$, then we have the following:

$\displaystyle\|P_{-1}\bm{K}_{1}\|_{2}\in\left[0,c_{3}(2\lambda_{1}+(n-2)\tau)\sqrt{n}\tau\right]$
(17)
$\displaystyle\|P_{1}\bm{K}_{1}\|_{2}\in\left[\sqrt{\lambda_{1}^{2}-c_{3}^{2}[2\lambda_{1}+(n-2)\tau]^{2}n\tau^{2}},\lambda_{1}+\sqrt{n}\tau\right].$
(18)

###### Proof.

For $i\neq 1$, we calculate

$\displaystyle P_{-1}\bm{K}_{i}$ $\displaystyle=\bm{K}_{i}$ $\displaystyle
P_{1}\bm{K}_{i}$ $\displaystyle=\bm{K}_{i}-P_{-1}\bm{K}_{i}=\bm{0}$

thus we have equations (15) and (16).

For $\|P_{-1}\bm{K}_{1}\|_{2}$:

$\displaystyle\begin{split}&\|P_{-1}\bm{K}_{1}\|_{2}\\\
=&\|K_{-1}(K_{-1}^{T}K_{-1})^{-1}K_{-1}^{T}\bm{K}_{1}\|_{2}\\\
\leq&\|K_{-1}(K_{-1}^{T}K_{-1})^{-1}\|_{2}\|K_{-1}^{T}\bm{K}_{1}\|_{2}\end{split}$

where

$\displaystyle\begin{split}&\|K_{-1}^{T}\bm{K}_{1}\|_{2}^{2}\\\
=&\sum_{i=2}^{n}(\bm{K}_{i}^{T}\bm{K}_{1})^{2}\\\
\stackrel{{\scriptstyle\eqref{ch2:eq:lemC1eq2}}}{{\leq}}&(n-1)[2\lambda_{1}+(n-2)\tau]^{2}\tau^{2}\\\
\leq&[2\lambda_{1}+(n-2)\tau]^{2}n\tau^{2}\end{split}$

and $K_{-1}^{T}K_{-1}$ has all eigenvalues in
$[\gamma_{n}^{2},\gamma_{1}^{2}]$ by Cauchy interlacing theorem (Lemma 3),
that is, all singular values of $K_{-1}$ are in $[c_{1},c_{2}]$ by our
assumption. Then

$\displaystyle\|K_{-1}(K_{-1}^{T}K_{-1})^{-1}\|_{2}\leq\frac{c_{2}}{c_{1}^{2}}:=c_{3}$

So we have

$\displaystyle\|P_{-1}\bm{K}_{1}\|_{2}$
$\displaystyle\leq\|K_{-1}(K_{-1}^{T}K_{-1})^{-1}\|_{2}\|K_{-1}^{T}\bm{K}_{1}\|_{2}$
$\displaystyle\leq c_{3}[2\lambda_{1}+(n-2)\tau]\sqrt{n}\tau.$

For $\|P_{1}\bm{K}_{1}\|_{2}$:

$\displaystyle\|P_{1}\bm{K}_{1}\|_{2}\leq\|\bm{K}_{1}\|_{2}$
$\displaystyle\leq$ $\displaystyle(\lambda_{1}^{2}+(n-1)\tau^{2})^{.5}$
$\displaystyle\leq$ $\displaystyle\lambda_{1}+\sqrt{n}\tau$

and

$\displaystyle\|P_{1}\bm{K}_{1}\|_{2}^{2}$ $\displaystyle=$
$\displaystyle\|\bm{K}_{1}\|_{2}^{2}-\|P_{-1}\bm{K}_{1}\|_{2}^{2}$
$\displaystyle\geq$
$\displaystyle\lambda_{1}^{2}-c_{3}^{2}[2\lambda_{1}+(n-2)\tau]^{2}n\tau^{2}.$

∎

######  Lemma 7 (Spectrum of $H_{-1}:=P_{-1}KK^{T}P_{-1}$).

Assume

$c_{3}^{2}[2\lambda_{1}+(n-2)\tau]^{2}n\tau^{2}+2[2\lambda_{1}+(n-2)\tau]n\tau\leq\lambda_{n}^{2}$

We have the following:

  * •

$0$ is an eigenvalue of $H_{-1}$, corresponding eigenspace is the column space
of $P_{1}$;

  * •

Restricted to the column space of $P_{-1}$, the eigenvalues of $H_{-1}$ are
all in the interval:

$\left(\lambda_{n}^{2}-[2\lambda_{1}+(n-2)\tau]n\tau,\lambda_{2}^{2}+[2\lambda_{1}+(n-1)\tau]n\tau\right).$

###### Proof.

The first claim is by construction of $P_{1}$ and $P_{-1}$.

For the second claim, note that $H_{-1}$ has the same eigenvalues as

$H_{-1}^{\prime}=(P_{-1}K)^{T}P_{-1}K$

Now the diagonal entries of $H_{-1}^{\prime}$ are:

$\displaystyle(H_{-1}^{\prime})_{ii}=\|P_{-1}\bm{K}_{i}\|_{2}^{2}=\left\\{\begin{array}[]{ll}\|P_{-1}\bm{K}_{1}\|_{2}^{2}\leq
c_{3}^{2}[2\lambda_{1}+(n-2)\tau]^{2}n\tau^{2}&,i=1\\\
\|\bm{K}_{i}\|_{2}^{2}\in[\lambda_{i}^{2},\lambda_{i}^{2}+(n-1)\tau^{2}]&,i\neq
1\end{array}\right.$

And the off-diagonal entries of $H_{-1}^{\prime}$ are:

$\displaystyle|(H_{-1}^{\prime})_{ij}|=|\langle
P_{-1}\bm{K}_{i},P_{-1}\bm{K}_{j}\rangle|=|\langle\bm{K}_{i},\bm{K}_{j}\rangle|\leq[2\lambda_{1}+(n-2)\tau]\tau$

To use Gershgorin circle theorem, calculate

$\displaystyle R_{i}(H_{-1}^{\prime})=\sum_{j\neq
i}|(H_{-1}^{\prime})_{ij}|<[2\lambda_{1}+(n-2)\tau]n\tau$

Thus the Gershgorin discs:

$\displaystyle
D_{1}(H_{-1}^{\prime})\in(\|P_{-1}\bm{K}_{1}\|_{2}^{2}-[2\lambda_{1}+(n-2)\tau]n\tau,\|P_{-1}\bm{K}_{1}\|_{2}^{2}+[2\lambda_{1}+(n-2)\tau]n\tau)$
$\displaystyle
D_{i}(H_{-1}^{\prime})\in(\|\bm{K}_{i}\|_{2}^{2}-[2\lambda_{1}+(n-2)\tau]n\tau,\|\bm{K}_{i}\|_{2}^{2}+[2\lambda_{1}+(n-2)\tau]n\tau)$

when
$c_{3}^{2}[2\lambda_{1}+(n-2)\tau]^{2}n\tau^{2}+[2\lambda_{1}+(n-2)\tau]n\tau\leq\lambda_{n}^{2}-[2\lambda_{1}+(n-2)\tau]n\tau$,
the first Gershgorin discs does not intersect with the others, so we have
$n-1$ nonzero eigenvalues in

$\cup_{i=2}^{n}D_{i}(H_{-1}^{\prime})\subset\left(\lambda_{n}^{2}-[2\lambda_{1}+(n-2)\tau]n\tau,\lambda_{2}^{2}+[2\lambda_{1}+(n-1)\tau]n\tau\right).$

∎

##  Appendix E Directional bias of SGD with moderate step size

This section gives formal proof of Theorem 1 and specifies the constants. The
proof is done in four steps: Lemma 8 analyzes one update of SGD; Lemma 9 uses
Lemma 8 to bound the first stage updates of SGD with moderate step size; Lemma
10 again uses Lemma 8, and bounds the second stage updates of SGD with small
step size; finally, Theorem 5 combines Lemma 9 and Lemma 10 to formalize the
directional bias of SGD, it is the same as Theorem 1, but restated using the
constants defined therein.

######  Lemma 8 (One step update of SGD).

Under Assumption 1, denote $A_{t}:=E[\|P_{1}\bm{b}_{t}\|_{2}]$,
$B_{t}:=E[\|P_{-1}\bm{b}_{t}\|_{2}]$, fix a constant
$c_{4}\geq(\lambda_{1}+\sqrt{n}\tau)(2\lambda_{1}+(n-2)\tau)c_{3}$, then we
have:

$\displaystyle A_{t+1}\leq q_{1}(\eta)A_{t}+\xi(\eta)B_{t}$ (19)
$\displaystyle A_{t+1}\geq q_{1}(\eta)A_{t}-\xi(\eta)B_{t}$ (20)
$\displaystyle B_{t+1}\leq q_{-1}(\eta)B_{t}+\xi(\eta)A_{t}$ (21)

where

$\displaystyle
q_{1}(\eta)=\frac{n-1}{n}+\frac{1}{n}|1-\eta\|P_{1}\bm{K}_{1}\|_{2}^{2}|$
$\displaystyle
q_{-1}(\eta)=\sqrt{1+\frac{\|KP_{-1}\bm{b}_{t}\|_{2}^{2}}{n\|P_{-1}\bm{b}_{t}\|_{2}^{2}}\left[\eta^{2}(\lambda_{2}^{2}+(n-1)\tau^{2})-2\eta\right]}$
$\displaystyle\xi(\eta)=c_{4}\eta n^{-1/2}\tau.$

###### Proof.

One step of SGD update is:

$\bm{b}_{t+1}=\bm{b}_{t}-\eta\bm{K}_{i}\bm{K}_{i}^{T}\bm{b}_{t}=[I-\eta\bm{K}_{i}\bm{K}_{i}^{T}]\bm{b}_{t}$

where $i$ is uniformly random sample from $[1,\ldots,n]$.

For inequalities (19) and (20), check

$\displaystyle P_{1}\bm{b}_{t+1}$
$\displaystyle=P_{1}[I-\eta\bm{K}_{i}\bm{K}_{i}^{T}]\bm{b}_{t}$
$\displaystyle=P_{1}\bm{b}_{t}-\eta
P_{1}\bm{K}_{i}\bm{K}_{i}^{T}(P_{1}+P_{-1})\bm{b}_{t}$ $\displaystyle=[I-\eta
P_{1}\bm{K}_{i}\bm{K}_{i}^{T}P_{1}]P_{1}\bm{b}_{t}-\eta[P_{1}\bm{K}_{i}\bm{K}_{i}^{T}P_{-1}]P_{-1}\bm{b}_{t}$

where $P_{1}\bm{K}_{i}$ and $P_{1}\bm{b}_{t}$ are in the same $1$ dimensional
linear space, thus

$\displaystyle P_{1}\bm{K}_{i}\bm{K}_{i}^{T}P_{1}P_{1}\bm{b}_{t}$
$\displaystyle=$
$\displaystyle\|P_{1}\bm{K}_{i}\|_{2}\|P_{1}\bm{b}_{t}\|_{2}sign(\langle
P_{1}\bm{K}_{i},P_{1}\bm{b}_{t}\rangle)P_{1}\bm{K}_{i}$ $\displaystyle=$
$\displaystyle\|P_{1}\bm{K}_{i}\|_{2}^{2}P_{1}\bm{b}_{t}$
$\displaystyle\Rightarrow\quad[I$ $\displaystyle-\eta
P_{1}\bm{K}_{i}\bm{K}_{i}^{T}P_{1}]P_{1}\bm{b}_{t}=[1-\eta\|P_{1}\bm{K}_{i}\|_{2}^{2}]P_{1}\bm{b}_{t}$

and

$\displaystyle\|[P_{1}\bm{K}_{i}\bm{K}_{i}^{T}P_{-1}]P_{-1}\bm{b}_{t}\|_{2}$
$\displaystyle\leq$
$\displaystyle\|P_{1}\bm{K}_{i}\|_{2}\|P_{-1}\bm{K}_{i}\|_{2}\|P_{-1}\bm{b}_{t}\|_{2}.$

Then

$\displaystyle E[\|P_{1}\bm{b}_{t+1}\|_{2}|\bm{b}_{t}]\leq
E[|1-\eta\|P_{1}\bm{K}_{i}\|_{2}^{2}|]\|P_{1}\bm{b}_{t}\|_{2}+\eta
E[\|P_{1}\bm{K}_{i}\|_{2}\|P_{-1}\bm{K}_{i}\|_{2}]\|P_{-1}\bm{b}_{t}\|_{2}$
(22) $\displaystyle E[\|P_{1}\bm{b}_{t+1}\|_{2}|\bm{b}_{t}]\geq
E[|1-\eta\|P_{1}\bm{K}_{i}\|_{2}^{2}|]\|P_{1}\bm{b}_{t}\|_{2}-\eta
E[\|P_{1}\bm{K}_{i}\|_{2}\|P_{-1}\bm{K}_{i}\|_{2}]\|P_{-1}\bm{b}_{t}\|_{2}$
(23)

where

$\displaystyle E[|1-\eta\|P_{1}\bm{K}_{i}\|_{2}^{2}|]$ $\displaystyle=$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}|1-\eta\|P_{1}\bm{K}_{i}\|_{2}^{2}|$
$\displaystyle=$
$\displaystyle\frac{n-1}{n}+\frac{1}{n}|1-\eta\|P_{1}\bm{K}_{1}\|_{2}^{2}|$
$\displaystyle:=$ $\displaystyle q_{1}(\eta)$

and

$\displaystyle\eta E[\|P_{1}\bm{K}_{i}\|_{2}\|P_{-1}\bm{K}_{i}\|_{2}]$
$\displaystyle=$
$\displaystyle\eta\frac{1}{n}\sum_{i=1}^{n}\|P_{1}\bm{K}_{i}\|_{2}\|P_{-1}\bm{K}_{i}\|_{2}$
$\displaystyle=$
$\displaystyle\frac{\eta}{n}\|P_{1}\bm{K}_{1}\|_{2}\|P_{-1}\bm{K}_{1}\|_{2}$
$\displaystyle\stackrel{{\scriptstyle}}{{\leq}}$
$\displaystyle\frac{\eta}{n}(\lambda_{1}+\sqrt{n}\tau)c_{3}(2\lambda_{1}+(n-2)\tau)\sqrt{n}\tau$
$\displaystyle\leq$ $\displaystyle\frac{\eta}{n}c_{4}\sqrt{n}\tau:=\xi(\eta)$
(24)

where the first inequality by upper bounds (17) and (18), second inequality by
$n\tau\leq\mathcal{O}(1)$. Plug the term (24) into inequalities (22) and (23),
take expectation on both sides, we get claims (19) and (20).

For inequality (21), check

$\displaystyle P_{-1}\bm{b}_{t+1}$
$\displaystyle=P_{-1}[I-\eta\bm{K}_{i}\bm{K}_{i}^{T}]\bm{b}_{t}$
$\displaystyle=[I-\eta
P_{-1}\bm{K}_{i}\bm{K}_{i}^{T}P_{-1}]P_{-1}\bm{b}_{t}-\eta[P_{-1}\bm{K}_{i}\bm{K}_{i}^{T}P_{1}]P_{1}\bm{b}_{t}$

Then we have

$\displaystyle\quad E[\|P_{-1}\bm{b}_{t+1}\|_{2}|\bm{b}_{t}]$
$\displaystyle\leq\frac{1}{n}\sum_{i=1}^{n}\|[I-\eta
P_{-1}\bm{K}_{i}\bm{K}_{i}^{T}P_{-1}]P_{-1}\bm{b}_{t}\|_{2}+\eta
E[\|P_{-1}\bm{K}_{i}\|_{2}\|P_{1}\bm{K}_{i}\|_{2}]\|P_{1}\bm{b}_{t}\|_{2}$
$\displaystyle\stackrel{{\scriptstyle\eqref{ch2:eq:lemc1_9}}}{{\leq}}\frac{1}{n}\sum_{i=1}^{n}\|[I-\eta
P_{-1}\bm{K}_{i}\bm{K}_{i}^{T}P_{-1}]P_{-1}\bm{b}_{t}\|_{2}+\xi(\eta)\|P_{1}\bm{b}_{t}\|_{2}$

where

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\|[I-\eta
P_{-1}\bm{K}_{i}\bm{K}_{i}^{T}P_{-1}]P_{-1}\bm{b}_{t}\|_{2}$ $\displaystyle=$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\sqrt{\|[I-\eta
P_{-1}\bm{K}_{i}\bm{K}_{i}^{T}P_{-1}]P_{-1}\bm{b}_{t}\|_{2}^{2}}$
$\displaystyle=$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\sqrt{\|P_{-1}\bm{b}_{t}\|_{2}^{2}+\eta^{2}\|P_{-1}\bm{K}_{i}\bm{K}_{i}^{T}P_{-1}P_{-1}\bm{b}_{t}\|_{2}^{2}-2\eta\langle
P_{-1}\bm{b}_{t},P_{-1}\bm{K}_{i}\bm{K}_{i}^{T}P_{-1}P_{-1}\bm{b}_{t}\rangle}$
$\displaystyle=$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\sqrt{\|P_{-1}\bm{b}_{t}\|_{2}^{2}+\eta^{2}(\bm{K}_{i}^{T}P_{-1}P_{-1}\bm{b}_{t})^{2}\|P_{-1}\bm{K}_{i}\|_{2}^{2}-2\eta(\bm{K}_{i}^{T}P_{-1}P_{-1}\bm{b}_{t})^{2}}$
$\displaystyle=$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\sqrt{1+\frac{(\bm{K}_{i}^{T}P_{-1}P_{-1}\bm{b}_{t})^{2}}{\|P_{-1}\bm{b}_{t}\|_{2}^{2}}(\eta^{2}\|P_{-1}\bm{K}_{i}\|_{2}^{2}-2\eta)}\|P_{-1}\bm{b}_{t}\|_{2}$
$\displaystyle\leq$
$\displaystyle\sqrt{1+\frac{1}{n}\sum_{i=1}^{n}\frac{(\bm{K}_{i}^{T}P_{-1}P_{-1}\bm{b}_{t})^{2}}{\|P_{-1}\bm{b}_{t}\|_{2}^{2}}(\eta^{2}\|P_{-1}\bm{K}_{i}\|_{2}^{2}-2\eta)}\|P_{-1}\bm{b}_{t}\|_{2}$

where the last inequality from Jensen’s inequality. Now the term

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\frac{(\bm{K}_{i}^{T}P_{-1}P_{-1}\bm{b}_{t})^{2}}{\|P_{-1}\bm{b}_{t}\|_{2}^{2}}(\eta^{2}\|P_{-1}\bm{K}_{i}\|_{2}^{2}-2\eta)$
$\displaystyle\stackrel{{\scriptstyle\eqref{ch2:eq:lemC1eq1}}}{{\leq}}$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\frac{(\bm{K}_{i}^{T}P_{-1}P_{-1}\bm{b}_{t})^{2}}{\|P_{-1}\bm{b}_{t}\|_{2}^{2}}\left[\eta^{2}(\lambda_{2}^{2}+(n-1)\tau^{2})-2\eta\right]$
$\displaystyle=$
$\displaystyle\frac{\|KP_{-1}\bm{b}_{t}\|_{2}^{2}}{n\|P_{-1}\bm{b}_{t}\|_{2}^{2}}\left[\eta^{2}(\lambda_{2}^{2}+(n-1)\tau^{2})-2\eta\right]$

Let

$q_{-1}(\eta):=\sqrt{1+\frac{\|KP_{-1}\bm{b}_{t}\|_{2}^{2}}{n\|P_{-1}\bm{b}_{t}\|_{2}^{2}}\left[\eta^{2}(\lambda_{2}^{2}+(n-1)\tau^{2})-2\eta\right]}$

combine all three inequalities above, take the expectation w.r.t.
$\bm{b}_{t}$, we have claim (21).

∎

######  Lemma 9 (Long run behavior of SGD with moderate step size).

Assume $\bm{b}_{0}$ is away from $0$,
$\lambda_{n}^{2}>(2\lambda_{1}+(n-2)\tau)n\tau+c_{4}\sqrt{n}\tau$,
$\lambda_{2}^{2}+c_{6}\sqrt{n}\tau<\lambda_{1}^{2}-c_{5}\sqrt{n}\tau$ where
$c_{5},c_{6}$ are constants such that

$c_{5}\geq c_{3}^{2}[2\lambda_{1}+(n-2)\tau]^{2}\sqrt{n}\tau+c_{4}$
$c_{6}\geq\frac{\sqrt{n}\tau-
c_{4}^{2}n^{-.5}\tau/[\lambda_{n}^{2}-(2\lambda_{1}+(n-2)\tau)n\tau]+\lambda_{2}^{2}c_{4}/[\lambda_{n}^{2}-[2\lambda_{1}+(n-2)\tau]n\tau]}{1-c_{4}\sqrt{n}\tau/[\lambda_{n}^{2}-(2\lambda_{1}+(n-2)\tau)n\tau]}$

Consider first $k_{1}$ steps of SGD updates with step size $\eta$:

$\frac{2}{\lambda_{1}^{2}-c_{5}\sqrt{n}\tau}<\eta<\frac{2}{\lambda_{2}^{2}+c_{6}\sqrt{n}\tau}$

Fix a $\beta_{0}\leq A_{0}$, then for $0<\epsilon<1$ and $0<\beta<\beta_{0}$
such that $\sqrt{n}\tau\leq poly(\epsilon\beta)$, there exists
$k_{1}=\mathcal{O}(\log\frac{1}{\epsilon\beta})$ satisfying:

  * •

$B_{k_{1}}\leq\epsilon\beta$

  * •

$A_{k_{1}}\leq\|\bm{b}_{0}\|_{2}*\rho_{1}^{k_{1}}+\epsilon\beta/2$ for some
$\rho_{1}>1$

  * •

$A_{k}>\beta_{0}$ for $k=0,\ldots,k_{1}$.

###### Proof.

For this choice of $\eta$, denote
$q_{1}=q_{1}(\eta),q_{-1}=q_{-1}(\eta),\xi=\xi(\eta)$. By Lemma 4, we have

$\displaystyle A_{k}$ $\displaystyle\geq q_{1}A_{k-1}-\xi B_{k-1}$
$\displaystyle\begin{bmatrix}A_{k}\\\ B_{k}\end{bmatrix}$
$\displaystyle\leq\begin{bmatrix}q_{1}&\xi\\\
\xi&q_{-1}\end{bmatrix}\begin{bmatrix}A_{k-1}\\\ B_{k-1}\end{bmatrix}$

Decompose the coefficient matrix as

$\displaystyle\begin{bmatrix}q_{1}&\xi\\\
\xi&q_{-1}\end{bmatrix}=\begin{bmatrix}\cos\theta&-\sin\theta\\\
\sin\theta&\cos\theta\end{bmatrix}\begin{bmatrix}\rho_{1}&0\\\
0&\rho_{-1}\end{bmatrix}\begin{bmatrix}\cos\theta&\sin\theta\\\
-\sin\theta&\cos\theta\end{bmatrix}$

Assume w.l.o.g. that $\sin\theta\geq 0$ ( since otherwise we can take
$\theta\to\theta+\pi$), then we have

$\displaystyle\begin{bmatrix}A_{k}\\\ B_{k}\end{bmatrix}$
$\displaystyle\leq\begin{bmatrix}q_{1}&\xi\\\
\xi&q_{-1}\end{bmatrix}^{k}\begin{bmatrix}A_{0}\\\ B_{0}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\cos\theta&-\sin\theta\\\
\sin\theta&\cos\theta\end{bmatrix}\begin{bmatrix}\rho_{1}^{k}&0\\\
0&\rho_{-1}^{k}\end{bmatrix}\begin{bmatrix}\cos\theta&\sin\theta\\\
-\sin\theta&\cos\theta\end{bmatrix}\begin{bmatrix}A_{0}\\\ B_{0}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}A_{0}(\rho_{1}^{k}\cos^{2}\theta+\rho_{-1}^{k}\sin^{2}\theta)+B_{0}(\rho_{1}^{k}\cos\theta\sin\theta-\rho_{-1}^{k}\cos\theta\sin\theta)\\\
B_{0}(\rho_{-1}^{k}\cos^{2}\theta+\rho_{1}^{k}\sin^{2}\theta)+A_{0}(\rho_{1}^{k}\cos\theta\sin\theta-\rho_{-1}^{k}\cos\theta\sin\theta)\end{bmatrix}$
$\displaystyle=\begin{bmatrix}A_{0}\rho_{1}^{k}+(\rho_{1}^{k}-\rho_{-1}^{k})\sin\theta(B_{0}\cos\theta-
A_{0}\sin\theta)\\\
B_{0}\rho_{-1}^{k}+(\rho_{1}^{k}-\rho_{-1}^{k})\sin\theta(B_{0}\sin\theta+A_{0}\cos\theta)\end{bmatrix}$
$\displaystyle\leq\begin{bmatrix}A_{0}\rho_{1}^{k}+|\rho_{1}^{k}-\rho_{-1}^{k}|\sin\theta\sqrt{B_{0}^{2}+A_{0}^{2}}\\\
B_{0}\rho_{-1}^{k}+|\rho_{1}^{k}-\rho_{-1}^{k}|\sin\theta\sqrt{B_{0}^{2}+A_{0}^{2}}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}A_{0}\rho_{1}^{k}+|\rho_{1}^{k}-\rho_{-1}^{k}|\sin\theta\|\bm{b}_{0}\|_{2}\\\
B_{0}\rho_{-1}^{k}+|\rho_{1}^{k}-\rho_{-1}^{k}|\sin\theta\|\bm{b}_{0}\|_{2}\end{bmatrix}$

We claim the following holds:

$\displaystyle 0<\rho_{-1}<1<\rho_{1}\leq q_{1}+\xi$ (25a)
$\displaystyle\rho_{-1}^{k_{1}}\|\bm{b}_{0}\|_{2}\leq\epsilon\beta/2$ (25b)
$\displaystyle\rho_{1}^{k_{1}}\|\bm{b}_{0}\|_{2}\sin\theta\leq\epsilon\beta/2$
(25c) $\displaystyle(B_{0}+\epsilon\beta_{0}/2)\xi<(q_{1}-1)\beta_{0}$ (25d)

which we check later. Using inequalities (25), we can upper bound $B_{k_{1}}$
as

$\displaystyle B_{k_{1}}$ $\displaystyle\leq
B_{0}\rho_{-1}^{k_{1}}+(\rho_{1}^{k1}-\rho_{-1}^{k_{1}})\sin\theta\|\bm{b}_{0}\|_{2}$
$\displaystyle\leq\|\bm{b}_{0}\|_{2}\rho_{-1}^{k_{1}}+\rho_{1}^{k1}\sin\theta\|\bm{b}_{0}\|_{2}$
$\displaystyle\stackrel{{\scriptstyle\eqref{ch2:eq:lemc2_eq5_b},\eqref{ch2:eq:lemc2_eq5_c}}}{{\leq}}\epsilon\beta$

In addition, for $k=0,\ldots,k_{1}$

$\displaystyle B_{k}$ $\displaystyle\leq
B_{0}\rho_{-1}^{k}+(\rho_{1}^{k}-\rho_{-1}^{k})\sin\theta\|\bm{b}_{0}\|_{2}$
$\displaystyle\leq B_{0}+\rho_{1}^{k1}\sin\theta\|\bm{b}_{0}\|_{2}$
$\displaystyle\stackrel{{\scriptstyle\eqref{ch2:eq:lemc2_eq5_c}}}{{\leq}}B_{0}+\epsilon\beta/2$

We now lower bound $A_{k}$ by mathematical induction. We have
$A_{0}\geq\beta_{0}$, assume $A_{k-1}>\beta_{0}$, then

$\displaystyle A_{k}$ $\displaystyle\geq q_{1}A_{k-1}-\xi B_{k-1}$
$\displaystyle\geq q_{1}\beta_{0}-\xi(B_{0}+\epsilon\beta/2)$
$\displaystyle\stackrel{{\scriptstyle\eqref{ch2:eq:lemc2_eq5_d}}}{{>}}q_{1}\beta_{0}-(q_{1}-1)\beta_{0}=\beta_{0}$

For upper bound $A_{k_{1}}$, check

$\displaystyle A_{k_{1}}$ $\displaystyle\leq
A_{0}\rho_{1}^{k_{1}}+(\rho_{1}^{k_{1}}-\rho_{-1}^{k_{1}})\sin\theta\|\bm{b}_{0}\|_{2}$
$\displaystyle\leq\|\bm{b}_{0}\|_{2}\rho_{1}^{k_{1}}+\rho_{1}^{k_{1}}\sin\theta\|\bm{b}_{0}\|_{2}$
$\displaystyle\stackrel{{\scriptstyle\eqref{ch2:eq:lemc2_eq5_c}}}{{\leq}}\|\bm{b}_{0}\|_{2}\rho_{1}^{k_{1}}+\epsilon\beta/2$

We have all lemma claims proved. Now it remains to check inequalities (25).
First note that our choice of the upper bound on $\eta$ guarantees that
$q_{-1}<1$.

For inequality (25a): By Gershgorin circle theorem, it suffices to show
$q_{-1}+\xi<1,q_{1}-\xi>1$, then we have $\rho_{1}\geq q_{1}-\xi>1$ and
$\rho_{-1}\leq q_{-1}+\xi<1$. In addition, we need the matrix to be positive
definite so that $\rho_{-1}>0$, we just need $q_{1}q_{-1}>\xi^{2}$ to make the
matrix p.d..

$\displaystyle q_{-1}+\xi<1$ $\displaystyle\Longleftrightarrow$
$\displaystyle\sqrt{1+\frac{\|KP_{-1}\bm{b}_{t}\|_{2}^{2}}{n\|P_{-1}\bm{b}_{t}\|_{2}^{2}}\left[\eta^{2}(\lambda_{2}^{2}+(n-1)\tau^{2})-2\eta\right]}<1-c_{4}\eta
n^{-1/2}\tau$ $\displaystyle\Longleftarrow$
$\displaystyle\frac{\|KP_{-1}\bm{b}_{t}\|_{2}^{2}}{n\|P_{-1}\bm{b}_{t}\|_{2}^{2}}\left[\eta^{2}(\lambda_{2}^{2}+(n-1)\tau^{2})-2\eta\right]<c_{4}^{2}\eta^{2}n^{-1}\tau^{2}-2c_{4}\eta
n^{-1/2}\tau$ $\displaystyle\stackrel{{\scriptstyle\text{Lemma
}\ref{ch2:lem:C4}}}{{\Longleftarrow}}$ $\displaystyle 2c_{4}\eta
n^{-1/2}\tau\leq
c_{4}^{2}\eta^{2}n^{-1}\tau^{2}+\frac{\lambda_{n}^{2}-[2\lambda_{1}+(n-2)\tau]n\tau}{n}\left[2\eta-\eta^{2}(\lambda_{2}^{2}+(n-1)\tau^{2})\right]$
$\displaystyle\Longleftrightarrow$
$\displaystyle\frac{\lambda_{n}^{2}-[2\lambda_{1}+(n-2)\tau]n\tau}{n}\left[\lambda_{2}^{2}+(n-1)\tau^{2}\right]\eta-
c_{4}^{2}n^{-1}\tau^{2}\eta$ $\displaystyle\quad\leq
2\frac{\lambda_{n}^{2}-[2\lambda_{1}+(n-2)\tau]n\tau}{n}-2c_{4}n^{-1/2}\tau$
$\displaystyle\Longleftarrow$ $\displaystyle\eta\leq
2\frac{1-c_{4}\sqrt{n}\tau/[\lambda_{n}^{2}-[2\lambda_{1}+(n-2)\tau]n\tau]}{\lambda_{2}^{2}+(n-1)\tau^{2}-c_{4}^{2}\tau^{2}/[\lambda_{n}^{2}-[2\lambda_{1}+(n-2)\tau]n\tau]}$
$\displaystyle\Longleftrightarrow$
$\displaystyle\eta\leq\frac{2}{\lambda_{2}^{2}+\frac{(n-1)\tau^{2}-c_{4}^{2}\tau^{2}/[\lambda_{n}^{2}-[2\lambda_{1}+(n-2)\tau]n\tau]+\lambda_{2}^{2}[c_{4}\sqrt{n}\tau/[\lambda_{n}^{2}-[2\lambda_{1}+(n-2)\tau]n\tau]]}{1-c_{4}\sqrt{n}\tau/[\lambda_{n}^{2}-[2\lambda_{1}+(n-2)\tau]n\tau]}}$

which is true by our choice of $\eta$.

$\displaystyle q_{1}-\xi>1$ $\displaystyle\Longleftrightarrow$
$\displaystyle\frac{n-1}{n}+\frac{1}{n}|1-\eta\|P_{1}\bm{K}_{1}\|_{2}^{2}|-c_{4}\eta
n^{-1/2}\tau>1$ $\displaystyle\Longleftrightarrow$ $\displaystyle
1+c_{4}\eta\sqrt{n}\tau<|1-\eta\|P_{1}\bm{K}_{1}\|_{2}^{2}|$
$\displaystyle\Longleftarrow$
$\displaystyle\eta\|P_{1}\bm{K}_{1}\|_{2}^{2}-1>1+c_{4}\eta\sqrt{n}\tau$
$\displaystyle\Longleftarrow$
$\displaystyle\eta>\frac{2}{\|P_{1}\bm{K}_{1}\|_{2}^{2}-c_{4}\sqrt{n}\tau}$
$\displaystyle\stackrel{{\scriptstyle\eqref{ch2:eq:lemB3_eq4}}}{{\Longleftarrow}}$
$\displaystyle\eta>\frac{2}{\lambda_{1}^{2}-c_{3}^{2}[2\lambda_{1}+(n-2)\tau]^{2}n\tau^{2}-c_{4}\sqrt{n}\tau}$

which is true by our lower bound on $\eta$.

$\displaystyle q_{1}q_{-1}>\xi^{2}$ $\displaystyle\Longleftarrow$
$\displaystyle q_{-1}^{2}\geq\xi$ $\displaystyle\Longleftrightarrow$
$\displaystyle
1+\frac{\|KP_{-1}\bm{b}_{t}\|_{2}^{2}}{n\|P_{-1}\bm{b}_{t}\|_{2}^{2}}\left[\eta^{2}(\lambda_{2}^{2}+(n-1)\tau^{2})-2\eta\right]>c_{4}\eta
n^{-1/2}\tau$ $\displaystyle\Longleftarrow$ $\displaystyle
1-2\eta\frac{\lambda_{2}^{2}+(2\lambda_{1}+(n-1)\tau)n\tau}{n}>c_{4}\eta
n^{-1/2}\tau$ $\displaystyle\Longleftrightarrow$
$\displaystyle\eta<\frac{n}{2\lambda_{2}^{2}+2(2\lambda_{1}+(n-1)\tau)n\tau+c_{4}\sqrt{n}\tau}$

which is true.

For inequality (25b): It suffices to take

$\displaystyle
k_{1}=\frac{\log(\epsilon\beta/(2\|\bm{b}_{0}\|_{2}))}{\log(\rho_{-1})}=\mathcal{O}(\log\frac{1}{\epsilon\beta})$

For inequality (25c): We just need to show
$\sin\theta<(\rho_{-1}/\rho_{1})^{k_{1}}$. Calculate that
$\xi/(q_{1}-q_{-1})=\frac{\cos\theta\sin\theta}{\cos^{2}\theta-\sin^{2}\theta}$,
then

$\displaystyle\sin\theta<(\rho_{-1}/\rho_{1})^{k_{1}}$
$\displaystyle\Longleftarrow$
$\displaystyle\xi/(q_{1}-q_{-1})<0.9(\rho_{-1}/\rho_{1})^{k_{1}}$
$\displaystyle\Longleftarrow$
$\displaystyle\xi<0.9(q_{1}-q_{-1})(\frac{q_{-1}-\xi}{q_{1}+\xi})^{k_{1}}$
$\displaystyle\Longleftarrow$
$\displaystyle\xi<0.9(q_{1}-q_{-1})(\epsilon\beta/(2\|\bm{b}_{0}\|_{2}))^{1-\frac{\log(q_{1}+\xi)}{\log(q_{-1}-\xi)}}$
$\displaystyle\Longleftarrow$ $\displaystyle\xi<(q_{1}-1)poly(\epsilon\beta)$
$\displaystyle\Longleftarrow$ $\displaystyle\sqrt{n}\tau\leq
poly(\epsilon\beta)$

For inequality (25d): Suffice to show

$\displaystyle\xi<\frac{(q_{1}-1)\beta_{0}}{B_{0}+\epsilon\beta_{0}/2}$
$\displaystyle\Longleftarrow$ $\displaystyle\sqrt{n}\tau\leq\mathcal{O}(1)$

∎

######  Lemma 10 (Long run behavior of SGD with small step size).

Under the same notations and assumptions as Lemma 9 unless otherwise
specified. Consider another $k_{2}-k_{1}$ steps of SGD update with step size

$\eta^{\prime}<\frac{1}{\lambda_{1}^{2}+c_{7}\sqrt{n}\tau}$

where the constant $c_{7}\geq\sqrt{n}\tau+c_{4}$. Then we have for $k>k_{1}$:

  * •

$B_{k}\leq\epsilon\beta$

  * •

$A_{k}\leq\left\\{\begin{array}[]{ll}qA_{k-1}&,A_{k-1}>\beta\\\
\beta&,A_{k-1}<\beta\end{array}\right.$

where $q:=q_{1}(\eta^{\prime})+\xi(\eta^{\prime})\epsilon<1$.

###### Proof.

Denote
$q_{1}^{\prime}=q_{1}(\eta^{\prime}),q_{-1}^{\prime}=q_{-1}(\eta^{\prime}),\xi^{\prime}=\xi(\eta^{\prime})$,
then $q=q_{1}^{\prime}+\xi^{\prime}\epsilon$, denote
$B=\|\bm{b}_{0}\|_{2}*\rho_{1}^{k_{1}}+\epsilon\beta/2$. We have by proof of
Lemma 9 that $q_{-1}^{\prime}+\xi<1$. We claim the following holds:

$\displaystyle q<1$ (26a)
$\displaystyle\xi^{\prime}B\leq(1-q_{1}^{\prime})\epsilon\beta$ (26b)

Check inequality (26a):

$\displaystyle q_{1}^{\prime}+\xi^{\prime}\epsilon<1$
$\displaystyle\Longleftarrow$
$\displaystyle\frac{n-1}{n}+\frac{1}{n}|1-\eta^{\prime}\|P_{1}\bm{K}_{1}\|_{2}^{2}|+c_{4}\eta^{\prime}n^{-1/2}\tau<1$
$\displaystyle\Longleftrightarrow$
$\displaystyle|1-\eta^{\prime}\|P_{1}\bm{K}_{1}\|_{2}^{2}|<1-c_{4}\eta^{\prime}\sqrt{n}\tau$
$\displaystyle\Longleftrightarrow$ $\displaystyle
c_{4}\eta^{\prime}\sqrt{n}\tau<\eta^{\prime}\|P_{1}\bm{K}_{1}\|_{2}^{2}<2-c_{4}\eta^{\prime}\sqrt{n}\tau$
$\displaystyle\Longleftrightarrow$
$\displaystyle\left\\{\begin{array}[]{l}c_{4}\sqrt{n}\tau<\|P_{1}\bm{K}_{1}\|_{2}^{2}\\\
\eta^{\prime}<\frac{2}{\|P_{1}\bm{K}_{1}\|_{2}^{2}+c_{4}\sqrt{n}\tau}\end{array}\right.$
$\displaystyle\Longleftarrow$
$\displaystyle\left\\{\begin{array}[]{l}\sqrt{n}\tau<\mathcal{O}(1)\\\
\eta^{\prime}<\frac{2}{\lambda_{1}^{2}+n\tau^{2}+c_{4}\sqrt{n}\tau}\end{array}\right.$

which are true by assumption.

Check inequality (26b):

$\displaystyle\xi^{\prime}B\leq(1-q_{1}^{\prime})\epsilon\beta$
$\displaystyle\Longleftrightarrow$ $\displaystyle
c_{4}\eta^{\prime}n^{-1/2}\tau(\|\bm{b}_{0}\|_{2}*\rho_{1}^{k_{1}}+\epsilon\beta/2)\leq(1-\frac{n-1}{n}-\frac{1}{n}(1-\eta^{\prime}\|P_{1}\bm{K}_{1}\|_{2}^{2}))\epsilon\beta$
$\displaystyle\Longleftrightarrow$ $\displaystyle
c_{4}\eta^{\prime}\sqrt{n}\tau(\|\bm{b}_{0}\|_{2}*\exp(k_{1})^{\log\rho_{1}}+\epsilon\beta/2)\leq\eta^{\prime}\|P_{1}\bm{K}_{1}\|_{2}^{2}\epsilon\beta$
$\displaystyle\Longleftarrow$ $\displaystyle\sqrt{n}\tau\leq
poly(\epsilon\beta).$

With (26) we can prove the lemma by mathematical induction. Suppose
$B_{k-1}\leq\epsilon\beta$ and $A_{k-1}\leq A_{k_{1}}\leq B$, then check

$\displaystyle B_{k}$
$\displaystyle\leq\xi^{\prime}A_{k-1}+q_{-1}^{\prime}B_{k-1}$
$\displaystyle\leq\xi^{\prime}B+q_{-1}^{\prime}\epsilon\beta$
$\displaystyle\stackrel{{\scriptstyle\eqref{ch2:eq:lemc3_eq1_b}}}{{\leq}}\epsilon\beta$

and

$\displaystyle A_{k}$ $\displaystyle\leq
q_{1}^{\prime}A_{k-1}+\xi^{\prime}B_{k-1}$ $\displaystyle\leq
q_{1}^{\prime}A_{k-1}+\xi^{\prime}\epsilon\beta$
$\displaystyle\leq(q_{1}^{\prime}+\xi^{\prime}\epsilon)\max\\{A_{k-1},\beta\\}$
$\displaystyle\leq\left\\{\begin{array}[]{ll}qA_{k-1}&,A_{k-1}>\beta\\\
q\beta<\beta&,A_{k-1}<\beta\end{array}\right..$

∎

We recap Theorem 1 using our notations in previous lemmas as follows:

######  Theorem 5 (Directional bias of the two-stage SGD).

Use the two stage SGD scheme as defined in Lemma 9 and 10. Assume
$n\tau<poly(\epsilon)$, then there exists
$k_{1}=\mathcal{O}(\log\frac{1}{\epsilon})$ and $k_{2}$ such that

$(1-2\epsilon)\gamma_{1}\leq\frac{E[\|K\bm{b}_{k_{2}}\|_{2}]}{E[\|\bm{b}_{k_{2}}\|_{2}]}\leq\gamma_{1}$

where $\gamma_{1}$ is the largest eigenvalue of $K$.

###### Proof.

In Lemma 9 let $\beta=\beta_{0}$, then for
$k_{1}=\mathcal{O}(\log\frac{1}{\epsilon})$ we have
$B_{k_{1}}\leq\epsilon\beta_{0}$. For the 2nd stage, by Lemma 10 we can early
stop at $k_{2}$ such that $A_{k_{2}}\geq\beta_{0}$ and
$A_{k_{2}+1}<\beta_{0}$. We then have

$\displaystyle B_{k_{2}}\leq\epsilon\beta_{0}\leq\epsilon A_{k_{2}}$

Then we check

$\displaystyle\frac{E\|K\bm{b}_{k_{2}}\|_{2}}{E\|\bm{b}_{k_{2}}\|_{2}}$
$\displaystyle=$
$\displaystyle\frac{E\sqrt{\|KP_{-1}\bm{b}_{k_{2}}\|_{2}^{2}+\|KP_{1}\bm{b}_{k_{2}}\|_{2}^{2}+2\langle\bm{K}_{1}^{T}P_{-1}\bm{b}_{k_{2}},\bm{K}_{1}^{T}P_{1}\bm{b}_{k_{2}}\rangle}}{E\|\bm{b}_{k_{2}}\|_{2}}$
$\displaystyle\geq$
$\displaystyle\frac{E\sqrt{\|KP_{1}\bm{b}_{k_{2}}\|_{2}^{2}-2\|P_{-1}\bm{K}_{1}\|_{2}\|P_{1}\bm{K}_{1}\|_{2}\|\bm{b}_{k_{2}}\|_{2}^{2}}}{E\|\bm{b}_{k_{2}}\|_{2}}$
$\displaystyle\geq$
$\displaystyle\frac{E\sqrt{\|KP_{1}\bm{b}_{k_{2}}\|_{2}^{2}}-E\sqrt{2\|P_{-1}\bm{K}_{1}\|_{2}\|P_{1}\bm{K}_{1}\|_{2}\|\bm{b}_{k_{2}}\|_{2}^{2}}}{E\|\bm{b}_{k_{2}}\|_{2}}$
$\displaystyle=$
$\displaystyle\frac{E\|\bm{K}_{1}^{T}P_{1}\bm{b}_{k_{2}}\|_{2}-\sqrt{2\|P_{-1}\bm{K}_{1}\|_{2}\|P_{1}\bm{K}_{1}\|_{2}}E\|\bm{b}_{k_{2}}\|_{2}}{E\|\bm{b}_{k_{2}}\|_{2}}$
$\displaystyle\stackrel{{\scriptstyle\eqref{ch2:eq:lemB3_eq3},\eqref{ch2:eq:lemB3_eq4}}}{{\geq}}$
$\displaystyle\sqrt{\lambda_{1}^{2}-c_{3}^{2}[2\lambda_{1}+(n-2)\tau]^{2}n\tau^{2}}\frac{E\|P_{1}\bm{b}_{k_{2}}\|_{2}}{E\|P_{1}\bm{b}_{k_{2}}\|_{2}+E\|P_{-1}\bm{b}_{k_{2}}\|_{2}}$
$\displaystyle\quad-\sqrt{2(\lambda_{1}+\sqrt{n}\tau)(c_{3}(2\lambda_{1}+(n-2)\tau)\sqrt{n}\tau)}$
$\displaystyle\geq$
$\displaystyle\sqrt{\lambda_{1}^{2}-c_{3}^{2}[2\lambda_{1}+(n-2)\tau]^{2}n\tau^{2}}\frac{\beta_{0}}{\epsilon\beta_{0}+\beta_{0}}-\sqrt{2(\lambda_{1}+\sqrt{n}\tau)(c_{3}(2\lambda_{1}+(n-2)\tau)\sqrt{n}\tau)}$
$\displaystyle\stackrel{{\scriptstyle\eqref{ch2:eq:lemB2_eq1}}}{{\geq}}$
$\displaystyle(\gamma_{1}-n\tau-
c_{3}(2\lambda_{1}+(n-2)\tau)\sqrt{n}\tau)(1-\epsilon)-\sqrt{2(\lambda_{1}+\sqrt{n}\tau)(c_{3}(2\lambda_{1}+(n-2)\tau)\sqrt{n}\tau)}$
$\displaystyle\geq$
$\displaystyle\gamma_{1}(1-\epsilon)-\gamma_{1}\epsilon\quad(\text{By
}n\tau<poly(\epsilon))$ $\displaystyle=$
$\displaystyle\gamma_{1}(1-2\epsilon)$

And the upper bound in the theorem is by definition of $\gamma_{1}$. ∎

##  Appendix F Directional bias of GD with moderate or small step size

This section includes the proof of Theorem 2. We first rewrite the GD updates
as linear combination of eigenvectors. Then the theorem is proved using the
transformed variables and finally transformed back to original parameters.

The directional bias of GD does not require diagonal dominant Gram matrix.

Reloading notations Denote the eigen decomposition of $K$:

$\displaystyle K=G\Gamma
G^{T},\Gamma=diag(\gamma_{1},\ldots,\gamma_{n}),G=[\bm{g}_{1},\ldots,\bm{g}_{n}]$

where the eigenvectors $\bm{g}_{i}$’s are orthogonal. The GD update as

$\displaystyle\bm{\alpha}_{t+1}=\bm{\alpha}_{t}-\frac{\eta}{n}K(K\bm{\alpha}_{t}-\bm{y})$

Denote $\bm{w}_{t}:=G^{T}(\bm{\alpha}_{t}-\hat{\bm{\alpha}})$, we can rewrite
GD update in $\bm{w}_{t}$:

$\displaystyle\bm{w}_{t+1}=\bm{w}_{t}-\frac{\eta}{n}\Gamma^{2}\bm{w}_{t}=(I-\frac{\eta}{n}\Gamma^{2})\bm{w}_{t}$

We recap Theorem 2 to make reading easier as follows:

######  Theorem 6 (Direction bias of GD).

Assume $\bm{\alpha}_{0}$ is away from $0$, $\lambda_{n}+2n\tau<\lambda_{n-1}$,
GD with step size:

$\displaystyle\eta<\frac{n}{(\lambda_{1}+n\tau)^{2}}$

For a small $\epsilon>0$, take $k=\mathcal{O}(\log\frac{1}{\epsilon})$, we
have

$\displaystyle\gamma_{n}\leq\frac{\|K(\bm{\alpha}_{k}-\hat{\bm{\alpha}})\|_{2}}{\|\bm{\alpha}_{k}-\hat{\bm{\alpha}}\|_{2}}\leq\sqrt{1+\epsilon}\gamma_{n}$

###### Proof.

For $i=1,\ldots,n$, we have

$\displaystyle\begin{split}w_{k}^{(i)}=(1-\eta\gamma_{i}^{2}/n)^{k}w_{0}^{(i)}\end{split}$

Denote $q_{i}=1-\eta\gamma_{i}^{2}/n$, then $0<q_{1}\leq\ldots\leq q_{n}<1$
since

$\displaystyle
0<\eta<\frac{n}{(\lambda_{1}+n\tau)^{2}}\stackrel{{\scriptstyle\eqref{ch2:eq:lemB2_eq1}}}{{\leq}}\frac{n}{\gamma_{1}^{2}}\leq\frac{n}{\gamma_{i}^{2}}$

Since $\lambda_{n}+n\tau<\lambda_{n-1}-n\tau$, we have
$\gamma_{n}<\gamma_{n-1}$ by lemma 3, it follows that $q_{n}>q_{n-1}$. Denote
$q=q_{n-1}/q_{n}<1$, then

$\displaystyle\frac{\sum_{i=1}^{n-1}(w_{k}^{(i)})^{2}}{(w_{k}^{(n)})^{2}}$
$\displaystyle=$
$\displaystyle\frac{\sum_{i=1}^{n-1}q_{i}^{2k}(w_{0}^{(i)})^{2}}{q_{n}^{2k}(w_{0}^{(n)})^{2}}$
$\displaystyle\leq$
$\displaystyle\frac{\sum_{i=1}^{n-1}q_{n-1}^{2k}(w_{0}^{(i)})^{2}}{q_{n}^{2k}(w_{0}^{(n)})^{2}}$
$\displaystyle=$ $\displaystyle
q^{2k}\frac{\sum_{i=1}^{n-1}(w_{0}^{(i)})^{2}}{(w_{0}^{(n)})^{2}}$

Let
$q^{2k}\leq\frac{\gamma_{n}^{2}\epsilon(w_{0}^{(n)})^{2}}{\gamma_{1}^{2}\sum_{i=1}^{n-1}(w_{0}^{(i)})^{2}}\Longleftrightarrow
k\geq\frac{1}{2}\frac{\log\frac{\gamma_{n}^{2}\epsilon(w_{0}^{(n)})^{2}}{\gamma_{1}^{2}\sum_{i=1}^{n-1}(w_{0}^{(i)})^{2}}}{\log
q}=\mathcal{O}(\log\frac{1}{\epsilon})$, we have

$\displaystyle\frac{\sum_{i=1}^{n-1}(w_{k}^{(i)})^{2}}{(w_{k}^{(n)})^{2}}\leq\frac{\gamma_{n}^{2}\epsilon}{\gamma_{1}^{2}}$

Thus

$\displaystyle\frac{\|K(\bm{\alpha}_{k}-\hat{\bm{\alpha}})\|_{2}^{2}}{\|\bm{\alpha}_{k}-\hat{\bm{\alpha}}\|_{2}^{2}}$
$\displaystyle=\frac{\|\Gamma\bm{w}_{k}\|_{2}^{2}}{\|\bm{w}_{k}\|_{2}^{2}}$
$\displaystyle=\frac{\sum_{i=1}^{n}(w_{k}^{(i)})^{2}\gamma_{i}^{2}}{\sum_{i=1}^{n}(w_{k}^{(i)})^{2}}$
$\displaystyle=\frac{(w_{k}^{(n)})^{2}\gamma_{n}^{2}}{\sum_{i=1}^{n}(w_{k}^{(i)})^{2}}+\frac{\sum_{i=1}^{n-1}(w_{k}^{(i)})^{2}\gamma_{i}^{2}}{\sum_{i=1}^{n}(w_{k}^{(i)})^{2}}$
$\displaystyle\leq\gamma_{n}^{2}+\frac{\sum_{i=1}^{n-1}(w_{k}^{(i)})^{2}}{\sum_{i=1}^{n}(w_{k}^{(i)})^{2}}\gamma_{1}^{2}$
$\displaystyle\leq\gamma_{n}^{2}+\gamma_{1}^{2}\frac{\gamma_{n}^{2}}{\gamma_{1}^{2}}\epsilon=\gamma_{n}^{2}(1+\epsilon)$

thus

$\frac{\|K(\bm{\alpha}_{k}-\hat{\bm{\alpha}})\|_{2}}{\|\bm{\alpha}_{k}-\hat{\bm{\alpha}}\|_{2}}\leq\sqrt{\gamma_{n}^{2}(1+\epsilon)}$

The lower bound of the theorem holds by definition of $\gamma_{n}$. ∎

##  Appendix G Effect of directional bias

In this section, we provide the proof for theorems in Section 3.2. There are
two theorems there, so we split this section into two subsections. Subsection
G.1 proves Theorem 3. For a general problem setting of squared error
minimization, the Theorem gives a straightforward understanding for why
directional bias towards the largest eigenvalue of the Hessian is good for
generalization. Section G.2 proves Theorem 4 by giving concrete generalization
bounds of SGD and GD estimators in kernel regression.

###  G.1 Proof of Theorem 3

Denote $\bm{v}=\bm{w}-\bm{w}^{*}$, rewrite the objective function as

$\displaystyle\min_{\bm{v}}$ $\displaystyle\quad\|\bm{v}\|_{2}^{2}$
$\displaystyle s.t.$ $\displaystyle\quad\|A\bm{v}\|_{2}^{2}=a$

Denote the eigen decomposition of $A^{T}A=Q\Gamma Q^{T}$ where
$Q=[\bm{q}_{1},\ldots,\bm{q}_{n}]$, $QQ^{T}=Q^{T}Q=I$ and
$\Gamma=diag([\rho_{1},\ldots,\rho_{n}])$, $\rho_{1}\geq\ldots\geq\rho_{n}\geq
0$. Then

$\|A\bm{v}\|_{2}^{2}=\sum_{i=1}^{n}\rho_{i}(\bm{q_{i}}^{T}\bm{v})^{2}$

So

$\|A\bm{v}\|_{2}^{2}\leq\rho_{1}[\sum_{i=1}^{n}(\bm{q_{i}}^{T}\bm{v})^{2}]=\rho_{1}\bm{v}^{T}QQ^{T}\bm{v}=\rho_{1}\|\bm{v}\|_{2}^{2}$

The equality is achieved when $\bm{v}$ is in the direction of $\bm{q}_{1}$,
and $\rho_{1}=\|A^{T}A\|_{2}$. Take $L(\bm{w})=\|A\bm{v}\|_{2}^{2}=a$ then the
theorem holds.

###  G.2 Proof of Theorem 4

Calculate $\Delta_{a}^{*}$: Denote
$f^{*}=\hat{\bm{\alpha}}^{T}K(\cdot,X)+\tilde{f}$, then we have for a
$f\in\mathcal{H}_{s}$, $f=\bm{\alpha}^{T}K(\cdot,X)$, let
$\bm{b}=\hat{\bm{\alpha}}-\bm{\alpha}$, then

$\displaystyle\|f^{*}-f\|^{2}_{\mathcal{H}}$ $\displaystyle=$
$\displaystyle\|\bm{b}^{T}K(\cdot,X)+\tilde{f}\|_{\mathcal{H}}^{2}$
$\displaystyle=$
$\displaystyle\|\bm{b}^{T}K(\cdot,X)\|_{\mathcal{H}}^{2}+\|\tilde{f}\|_{\mathcal{H}}^{2}+2\langle\bm{b}^{T}K(\cdot,X),\tilde{f}\rangle_{\mathcal{H}}$

where we can check

$\displaystyle\langle\bm{b}^{T}K(\cdot,X),\tilde{f}\rangle_{\mathcal{H}}$
$\displaystyle=\sum_{i=1}b_{i}\langle
K(\cdot,\bm{x}_{i}),f^{*}-\hat{\bm{\alpha}}^{T}K(\cdot,X)\rangle_{\mathcal{H}}$
$\displaystyle=\sum_{i=1}b_{i}[\langle
K(\cdot,\bm{x}_{i}),f^{*}\rangle_{\mathcal{H}}-\langle
K(\cdot,\bm{x}_{i}),\hat{\bm{\alpha}}^{T}K(\cdot,X)\rangle_{\mathcal{H}}]$
$\displaystyle=\sum_{i=1}b_{i}[f^{*}(\bm{x}_{i})-\hat{\bm{\alpha}}^{T}K(\bm{x}_{i},X)](\text{By
reproducing property})$ $\displaystyle=\sum_{i=1}b_{i}[y_{i}-y_{i}]=0$

And we further calculate that

$\displaystyle\|\bm{b}^{T}K(\cdot,X)\|_{\mathcal{H}}^{2}$
$\displaystyle=\langle\sum_{i=1}^{n}b_{i}K(\cdot,\bm{x}_{i}),\sum_{j=1}^{n}b_{j}K(\cdot,\bm{x}_{j})\rangle_{\mathcal{H}}$
$\displaystyle=\sum_{i,j=1}^{n}b_{i}b_{j}\langle
K(\cdot,\bm{x}_{i}),K(\cdot,\bm{x}_{j})\rangle$
$\displaystyle=\sum_{i,j=1}^{n}b_{i}b_{j}K(\bm{x}_{i},\bm{x}_{j})=\bm{b}^{T}K\bm{b}$

That is,

$\displaystyle L_{D}(f)=\bm{b}^{T}K\bm{b}+\|\tilde{f}\|_{\mathcal{H}}^{2}$

and

$\displaystyle\inf_{f\in\mathcal{H}_{s}}L_{D}(f)=\|\tilde{f}\|_{\mathcal{H}}^{2}$

It follows that

$\displaystyle\Delta(f)=L_{D}(f)-\inf_{f\in\mathcal{H}_{s}}L_{D}(f)=\bm{b}^{T}K\bm{b}$

We claim that

$\displaystyle\Delta_{a}^{*}=\min_{\bm{b}:\frac{1}{2n}\|K\bm{b}\|_{2}^{2}=a}\bm{b}^{T}K\bm{b}=\frac{1}{\gamma_{1}}\|K\bm{b}\|_{2}^{2}=2na/\gamma_{1}$

where the equality is obtained when $\bm{b}$ is in the direction of the
largest eigenvector of $K$. To see this, we check
$\|K\bm{b}\|_{2}^{2}\leq\gamma_{1}\bm{b}^{T}K\bm{b}$. Recall the
eigendecomposition of $K=G\Gamma G^{T}$ where
$G=[\bm{g}_{1},\ldots,\bm{g}_{n}]$ has orthogonal columns and
$\Gamma=diag(\gamma_{1},\ldots,\gamma_{n})$. Then

$\|K\bm{b}\|_{2}^{2}=\sum_{i=1}^{n}\gamma_{i}^{2}(\bm{g_{i}}^{T}\bm{b})^{2}$

and

$\bm{b}^{T}K\bm{b}=\sum_{i=1}^{n}\gamma_{i}(\bm{g_{i}}^{T}\bm{b})^{2}$

So we have

$\|K\bm{b}\|_{2}^{2}\leq\gamma_{1}[\sum_{i=1}^{n}\gamma_{i}(\bm{g_{i}}^{T}\bm{b})^{2}]=\gamma_{1}\bm{b}^{T}K\bm{b}$

This finishes our claim on $\Delta_{a}^{*}$.

SGD output: By Theorem 1, the SGD output has

$(1-2\epsilon)\gamma_{1}E[\|\bm{b}_{k_{2}}\|_{2}]\leq
E[\|K\bm{b}_{k_{2}}\|_{2}]$

Thus

$\displaystyle E[\Delta^{1/2}(f^{SGD})]$
$\displaystyle=E\left[\sqrt{\sum_{i=1}^{n}\gamma_{i}(\bm{g_{i}}^{T}\bm{b}^{SGD})^{2}}\right]$
$\displaystyle\leq\sqrt{\gamma_{1}}E[(\sum_{i=1}^{n}(\bm{g_{i}}^{T}\bm{b}^{SGD})^{2})^{1/2}]$
$\displaystyle=\sqrt{\gamma_{1}}E\|\bm{b}^{SGD}\|_{2}$
$\displaystyle\leq\sqrt{\gamma_{1}}E[\|K\bm{b}^{SGD}\|_{2}]/[(1-2\epsilon)\gamma_{1}]$
$\displaystyle=\sqrt{2na/\gamma_{1}}/(1-2\epsilon)$
$\displaystyle=\frac{1}{1-2\epsilon}(\Delta^{*}_{a})^{1/2}$
$\displaystyle<(1+4\epsilon)(\Delta^{*}_{a})^{1/2}$

last inequality by let $\epsilon<1/4$.

GD output: By Theorem 2, the GD output has

$\frac{\|K\bm{b}^{GD}\|^{2}_{2}}{\|\bm{b}^{GD}\|^{2}_{2}}\leq(1+\epsilon^{\prime})\gamma_{n}^{2}$

Thus

$\displaystyle\Delta(f^{GD})$
$\displaystyle=\sum_{i=1}^{n}\gamma_{i}(\bm{g_{i}}^{T}\bm{b}^{GD})^{2}$
$\displaystyle\geq\gamma_{n}\sum_{i=1}^{n}(\bm{g_{i}}^{T}\bm{b}^{GD})^{2}$
$\displaystyle=\gamma_{n}\|\bm{b}^{GD}\|_{2}^{2}$
$\displaystyle\geq\gamma_{n}\|K\bm{b}^{GD}\|_{2}^{2}/[(1+\epsilon^{\prime})\gamma_{n}^{2}]$
$\displaystyle=2na/[(1+\epsilon^{\prime})\gamma_{n}]$
$\displaystyle=\frac{\gamma_{1}}{(1+\epsilon^{\prime})\gamma_{n}}\Delta^{*}_{a}$
$\displaystyle>\frac{\gamma_{1}}{\gamma_{n}}(1-\epsilon^{\prime})\Delta^{*}_{a}$
$\displaystyle:=M\Delta_{a}^{*}$

where $M>1$ by taking $\epsilon^{\prime}<1-\gamma_{n}/\gamma_{1}$.

##  Appendix H Experiments

We list the implementation details of the experiments in Section 4 and include
more experiment results. For better presenting, we split into two subsections:
Subsection H.1 includes the details of simulation; Subsection H.2 is about the
NN experiment on FashionMNIST, including the data description, network
structure, and algorithm details, also there are more experiment results in
Subsection H.2 that are not listed in Section 4 due to page limit.

###  H.1 Simulation

This subsection is corresponding to Figure 1.

Data Generation. The training data is simulated as follows: Set $n=10,p=100$,
simulate $X_{n\times p}$ where elements of $X$ are i.i.d. $N(0,1)$; denote
$i$th row of $X$ as $\bm{x}_{i}$, normalize $\bm{x}_{i}$ such that it has
squared $\ell_{2}$ norm in $[.49,1]$; set
$y_{i}=\sum_{j=1}^{p}\sin(x_{i,j})+\epsilon_{i}$ where
$\epsilon_{i}\stackrel{{\scriptstyle i.i.d.}}{{\sim}}N(0,.01)$. The testing
data is simulated in exactly the same way, except that we only simulate $n=5$
testing data.

Kernel Function. We set the kernel function to be the polynomial kernel

$K(\bm{x}_{1},\bm{x}_{2})=(\langle\bm{x}_{1},\bm{x}_{2}\rangle+.01)^{2}$

SGD and GD implementation. Both SGD and GD is run for small and moderate step
sizes. The moderate step size scheme for SGD is: $\eta_{1}=.1$ for the first
$50$ steps, and $\eta_{2}=.01$ for the next $1000$ steps; for GD is:
$\eta_{1}=.5$ for the first $50$ steps, and $\eta_{2}=.05$ for the next $1000$
steps. The small step size scheme for SGD is $\eta=0.01$ for $1050$ steps; for
GD is $\eta=0.05$ for $1050$ steps. Note that the step size for SGD is a
fraction of that for GD, this matches our Theorem 1 and 2 that the step size
of GD is of magnitude $n/2$ times that of SGD.

###  H.2 Neural Network on FashionMNIST

This subsection is corresponding to Figure 2.

Dataset. The original FashionMNIST consist of $60,000$ training data and
$10,000$ testing data. We randomly sample $1,500$ data from original training
data for training, and use all $10,000$ original testing data for testing. All
data entries are normalized to $[0,1]$.

Network structure. we use a $6$-layer ResNet-like [13] Neural Network, and the
structure is as follows

Input $\displaystyle\Rightarrow 7\times 7\text{ Conv
}\Rightarrow\text{BatchNorm}\Rightarrow\text{ReLU}\Rightarrow 3\times 3\text{
MaxPool }$
$\displaystyle\Rightarrow\text{ResBlock1}\Rightarrow\text{ResBlock2}\Rightarrow\text{Global
AvePool}\Rightarrow\text{FC}\Rightarrow\text{output}$

The Residual Blocks are as Figure $7.6.3$ in [30] (without $1\times 1$
convolution). Note that each residual block contains two $3\times 3$
convolutional layers, thus total number of layers is as stated.

Algorithm. We minimize the Cross Entropy Loss objective
$L(\mathbf{w})=\frac{1}{n}\sum_{i=1}^{n}l_{i}(\bf{w})$, where $l_{i}(\bf{w})$
is the loss function at $i$th sample. One step SGD is as follows:

$\displaystyle\bm{w}_{t+1}=\bm{w}_{t}-\eta_{t}\frac{1}{|I|}\sum_{i\in I}\nabla
l_{i}(\bm{w}_{t})$

where $I$ is a randomly sampled subset of $\\{1,\ldots,n\\}$ (uniform random
sample without replacement). We choose the batch size $|I|$ to be $25$.

One step GD is as follows:

$\displaystyle\bm{w}_{t+1}=\bm{w}_{t}-\eta_{t}\nabla L(\bm{w}_{t})$

Both SGD and GD are run using two settings of step sizes $\eta_{t}$. The
moderate step size setting is as follows:

$\displaystyle\eta_{t}=\begin{cases}0.2,&t=1,\ldots,5000\\\
0.02,&t=5001,\ldots,20000\end{cases}$

And the small step size setting has $\eta_{t}=0.02,t=1,\ldots,20000$.

Comparison of convergence direction. Since the loss surface is nonconvex and
the Hessian varies, we follow [29] to measure the convergence direction by
Relative Rayleigh Quotient(RRQ), which normalizes the Rayleigh Quotient by the
maximum eigenvalue of the Hessian as follows

$RRQ(\bm{w})=\frac{\frac{\nabla L(\bm{w})^{\top}}{\|\nabla
L(\bm{w})\|_{2}}\cdot\nabla^{2}L(\bm{w})\cdot\frac{\nabla L(\bm{w})}{\|\nabla
L(\bm{w})\|_{2}}}{\left\|\nabla^{2}L(\bm{w})\right\|_{2}}$

where $L(w)$ is the loss function on the whole training set. A high RRQ
indicates that the convergence direction of $w$ is close to a larger
eigenvector of the Hessian.

Comparison of test accuracy. We set $20$ different random seeds. For each
random seed, we run: SGD with moderate step size, GD with moderate step size,
SGD with small step size, GD with small step size. For each algorithm, we
evaluate its test accuracy once every $500$ steps, and use the average of the
last $5$ values as its test accuracy. We list the test accuracy in Table 1.

Experiment | #1 | #2 | #3 | #4 | #5 | #6 | #7 | #8 | #9 | #10
---|---|---|---|---|---|---|---|---|---|---
SGD + moderate LR | 83.69 | 82.95 | 82.37 | 82.05 | 83.4 | 83.16 | 83.72 | 83.29 | 83.28 | 83.23
GD + moderate LR | 80.93 | 80.79 | 80.79 | 81.80 | 81.68 | 81.12 | 82.43 | 81.63 | 80.94 | 81.54
SGD + small LR | 82.00 | 81.72 | 81.34 | 81.92 | 82.63 | 82.67 | 82.99 | 82.22 | 80.78 | 82.10
GD + small LR | 78.88 | 78.71 | 78.49 | 79.3 | 80.45 | 79.78 | 80.15 | 79.66 | 79.54 | 79.68
Experiment | #11 | #12 | #13 | #14 | #15 | #16 | #17 | #18 | #19 | #20
SGD + moderate LR | 83.12 | 82.92 | 83.58 | 83.47 | 82.35 | 83.57 | 83.59 | 82.43 | 84.21 | 83.12
GD + moderate LR | 82.41 | 81.56 | 81.42 | 80.86 | 81.23 | 81.25 | 81.82 | 80.42 | 81.80 | 82.12
SGD + small LR | 82.62 | 80.66 | 82.01 | 81.01 | 81.32 | 81.66 | 82.12 | 80.78 | 82.28 | 82.48
GD + small LR | 80.08 | 78.29 | 79.93 | 79.36 | 78.9 | 79.69 | 80.2 | 79.62 | 79.98 | 79.69
Table 1: Test Accuracy

We also use one-side Wilcoxon signed-rank test to check if the test accuracy
of different algorithm are significantly different, the result is in Table 2.
All the p-values are significant at $0.01$ level, so we reject the null
hypothesis and conclude that the SGD with moderate step size has test accuracy
significantly higher than all other algorithms.

Null Hypothesis on Test Accuracy | p-value
---|---
SGD + moderate LR $\leq$ GD + moderate LR | $9.54\times 10^{-7}$
SGD + moderate LR $\leq$ SGD + small LR | $9.54\times 10^{-7}$
SGD + moderate LR $\leq$ GD + small LR | $9.54\times 10^{-7}$
Table 2: Wilcoxon signed-rank test result

Additional experiments. We conduct more experiments using different step
sizes. The initial step size is taken in
$\\{1,0.5,0.2,0.1,0.02,0.01,0.005,0.001\\}$, and the step size is divided by a
factor of $10$ after $5000$ steps. The test accuracy is in Figure 3, where we
see that SGD with step size $0.2$ has the best test accuracy, and GD with step
size $0.5$ performs better than GD with any other step sizes, but is still
worse than the best SGD.

Figure 3: Use more step sizes in SGD/GD. The test accuracy is evaluated once
every $500$ iterations, and inside the bracket is the average of the last $5$
test accuracy values.