text:
\section{Introduction}

The study of overfitting phenomenon has been an important topic in statistics and machine learning. From classical statistical learning theory,  we understand that when the number of model parameters is large compared to the amount of data, the generalization error can be excessively large even if  the training error is small. This phenomenon is usually known as overfitting. For this reason, dimension reduction or feature selection mechanisms such as principle component analysis (PCA) and shrinkage methods are often required in the training phase to reduce model dimension and avoid overfitting.

In recent years, deep neural networks have achieved  great successes in practical applications. Researchers have found out that overparameterized neural networks usually achieve superior performance \citep{GRS:18,LL2018,NLBLS:19,ALL:19,ADHLW:19}. Moreover, these models are often trained with simple  regularization and do not need dimension reduction procedures. This phenomenon is sometimes referred to as \emph{benign overfitting} \citep{BLLT:19}.  To understand it, we need a new statistical framework to study generalization errors.

Although there is much practical evidence on the benefit of overparameterization, the existing theoretical study mainly focuses on linear models (see, e.g., \citealp{BLLT:19, Nakkiran19, AKT:19}) or neural networks with certain special data structures (see, e.g., \citealp{LL2018}). The main purpose of our paper is to systematically investigate the generalization error for a risk minimization problem when the number of parameters $p$ is much larger than the sample size $N$. In particular, we establish a generalization error bound for  stochastic gradient descent (SGD) solutions for both convex (e.g., linear regression and logistic regression) and non-convex problems (some $M$-estimators and neural networks). We focus our study on the SGD algorithm because it has been widely used in large-scale data learning due to its computational and memory efficiency.

Let us briefly introduce our setup of the overfitting problem and the SGD algorithm. We consider the following population risk minimization problem under a loss function $F$, which can be either convex or non-convex:
\begin{equation}\label{eq:sto_opt}
w^*=\mathop{\rm argmin}_w F(w),\quad F(w):=\mathbb{E}_\zeta f(w,\zeta).
\end{equation}
In \eqref{eq:sto_opt}, $w\in \mathbb{R}^p$ is a $p$-dimensional parameter vector,  $\zeta$ denotes a random sample from a certain probability distribution,  and $f(\,\cdot\,,\zeta)$ is the loss function on each individual data $\zeta$. The global minimizer $w^*$ is often the true model parameter in  statistical estimation problems. In practice, the distribution of $\zeta$ is usually unknown, and one only has the access to $N$ \emph{i.i.d.} samples  $\zeta_1,\ldots,\zeta_N$ from the population. Instead of minimizing the population risk $F(w)$ in \eqref{eq:sto_opt}, it is more practical  to minimize the empirical loss function
\begin{equation}\label{eq:empirical}
\hat{F}(w)=\frac1N \sum_{i=1}^N f(w,\zeta_i).
\end{equation}
Often, instead of directly minimizing the empirical loss, an extra regularization term is sometimes added to the empirical loss to avoid overfitting. In this paper,  we consider the most commonly used ridge or Tikhonov regularization.
 The corresponding regularized empirical loss function takes the following form,
\begin{equation}\label{eq:reg}
\widehat{F}_\lambda(w):=\widehat{F}(w)+\dfrac{\lambda}{2} \|w\|^2=\frac1N\sum_{i=1}^N f_\lambda(w,\zeta_i),\quad  f_\lambda(w,\zeta):=f(w,\zeta)+\dfrac{\lambda}{2} \|w\|^2.
\end{equation}
The weight of regularization is controlled by $\lambda$, which is a tuning parameter. \blue{When $\lambda=0$, this corresponds to the ridgeless regression. We will study this setup in this paper, which corresponds to ``implicit regularization''. }One popular way to optimize $\widehat{F}_\lambda$ in machine learning is via SGD. In particular, for a generic initialization parameter  $w_0$, SGD is an iterative algorithm, where the $(n+1)$-th iterate $w_{n+1}$ is updated according to the following equation,
\begin{align}
\label{eq:sgd_iter}
w_{n+1}: =w_{n} -\eta \nabla f_\lambda(w_{n}, \zeta_n) =w_{n} -\eta \left( \nabla f(w_{n}, \zeta_n) +\lambda w_n \right).
\end{align}
By running through $N$ samples, SGD outputs the $N$-th iterate $w_N$ as the final estimator of $w^*$.
\blue{Notably, SGD iterates are affected by the stochasticity of the data samples $\zeta$. To reduce such noise and improve accuracy, the averaged SGD (ASGD) method uses the average iterate
\[
\bar{w}_N=\frac{1}{N}\sum_{i=1}^N w_i
\]
as the final estimator of $w^*$.}
In SGD iterations \eqref{eq:sgd_iter}, the hyper-parameter $\eta$ is known as the stepsize. In our paper, we consider using a constant stepsize, which is  a popular choice in practice \citep{BM11}. The value of $\eta$ will be discussed later in our theoretical results.
Moreover, in \eqref{eq:sgd_iter}, the gradient is taken with respect to the parameter vector $w$. For notational simplicity, we will use ``$\nabla$" as a short notation for ``$\nabla_w$" throughout the paper.

\iffalse
\blue{
In practice, SGD is often implemented with mini-batch data to reduce the noise within stochastic gradient. With regularization, mini-batch SGD implementation can be formally written as
\[
w_{n+1}: =w_{n} -\frac{1}{J}\eta \sum_{k=Jn+1}^{J(n+1)}(\nabla f(w_{n}, z_k)+\lambda w_n),
\]
where i.i.d. data $\{z_{Jn+1},\ldots, z_{J(n+1)}\}$ forms the $n$-th batch of data. Our framework can apply to mini-SGD as well. To see this, we simply let
$\zeta_n=\{z_{Jn+1},\ldots, z_{J(n+1)}\}$ and
\[
\tilde{f}(w,\zeta_n)=\frac{1}{J} \sum_{k=Jn+1}^{J(n+1)}f(w_{n}, z_k).
\]
Note that $\mathbb{E} \tilde{f}(w,\zeta_n)=\mathbb{E} f(w,z_i)=F(w)$. It is also straight forward to see that applying our SGD formulation \eqref{eq:sgd_iter} on $\tilde{f}$ with $\zeta_n$ gives the same mini-batch SGD. To simplify our discussion, we will focus on the case with \eqref{eq:sgd_iter}. Interested readers can apply the transformation above to generalize our results to mini-batch SGD.
}
\fi

When the sample size $N$ is much larger than the dimensionality  $p$, it is expected  that $w_N$ would be close to $w^*$ under certain conditions. However, in an overparameterized setting where $N$ is less than $p$,  the solution $w_N$ can be far away from $w^*$. In this case, estimating the underlying parameter accurrately usually requires strong assumptions. However, for many machine learning tasks, it is of more interest in achieving small generalization error, which is defined as follows,
\begin{equation}\label{eq:generalization}
G(w_N)=F(w_N)-F(w^*).
\end{equation}
The main purpose of the paper is to provide an upper bound of the generalization error in \eqref{eq:generalization} in  overparameterized settings. We will characterize the scenarios where such a generalization error bound is independent of $p$ or only involves in poly-logarithmic factors of $p$.

\subsection{Main results and paper organization}
The main message of this paper is as follows. For a large class of statistical learning problems where the \emph{effective dimension} is low (see the rigorous definition in Section  \ref{sec:nooverfit}), the stochastic gradient descent (SGD) algorithm with proper ridge regularization will not overfit even if the ambient model dimension is much larger than the sample size. In particular, we will show that the generalization error has at most poly-logarithmic dependence on the ambient model dimension $p$.

In  Section \ref{sec:generalize},  we present a framework for generalization error analysis.
This framework is designed to handle
\blue{ high dimensional regression problems.
We will separately discuss two scenarios. In the first scenario, the true parameter is weakly sparse with a dimension independent $l_2$ norm.
In this case, we show ridgeless SGD has been sufficient to obtain dimension independent generalization error (Theorem \ref{thm:Asgd}).
In the second scenario, the true parameter is dimension independent only under some problem-specific norms.
In this more challenging case, we show SGD can achieve dimension independent generalization error by proper amount of ridge penalty (Theorem \ref{thm:sgd}).}
The upper bound of the generalization error is provided. Using linear regression as an illustrative example,  we show that  each term in the generalization bound has a strong statistical interpretation (see Section \ref{sec:SA}). The upper bound also leads to practical guidelines on the rates of  problem-related parameters, which are given by Corollary \ref{cor:selectpara_online}.

While Theorem \ref{thm:sgd} provides an  error bound on generalization, for this error bound to be almost dimension-independent, we require the \emph{effective dimension} to be small. Section \ref{sec:nooverfit} first formally defines the general notion of \emph{low effective dimension}, which can essentially be described by 1) the loss function has a fast decaying Hessian spectrum, and  2) the true parameter is either sparse or uniformly bounded along Hessian's eigen-directions.

In Section \ref{sec:linear}, we carefully investigate
generalization errors in various linear models. We consider the cases of finite projections of infinite-dimensional models and linear regression with redundant features.
In these scenarios, we quantify when the overparameterization does not hurt the generalization performance.

Our generalization result can also be applied to a wide range of nonlinear models. In Section \ref{sec:non_linear}, we study both convex nonlinear models such as logistic regression and non-convex models such as $M$-estimator with the Tukey's biweight loss function \citep{Tukey:60} and two-layer neural networks. We show that the low effective dimension naturally occurs in these applications.

\subsection{Related works}
High dimensional statistical learning with low effective dimension is a common idea in principal component analysis (PCA) and  functional data analysis applications \citep{Jol02,RS05}.  To implement PCA,  we first find a $k^*$-dimensional subspace  of which the truncated variability  contains a significant proportion (e.g., $95\%$)  of the full model variability. Then we project the problem onto this subspace and conduct the data analysis on it. In general, the truncated dimension $k^*$ needs to be less than the sample size $N$, and the statistical problem needs to  be well-conditioned in the $k^*$-dimensional subspace. {While we also require the existence of a low effective dimension}, the problem setting considered in this paper is fundamentally different from the classical PCA problem. In our setting, the SGD algorithm directly runs on the original problem space of dimension $p$,  and there is no projection step. Moreover, we do not need the problem to be well-conditioned in the ambient space.
We would argue that our setting is more useful for practical applications since it is difficult to find a proper truncation dimension $k^*$ and PCA is intractable with rank-deficient data.

In recent years, the generalization error bounds for linear models in overparameterized settings have been carefully investigated in the literature, see, e.g.,  \cite{BLLT:19, Nakkiran19, AKT:19, Hastie19}.  Our result is different from these existing results in the following perspectives:
\begin{enumerate}[1)]
	\item  Nonlinearity: Most of these works focus on linear models. For example, \cite{BLLT:19} defined two notions of \emph{effective ranks}  of the data covariance matrix in linear models and expressed the generalization error bound in terms of effective ranks.  A more detailed comparison between our low effective rank conditions and the ones in \cite{BLLT:19}  will be provided in Remark \ref{rem:comparewithBLLT}. 	In addition, \cite{Hastie19} developed the generalization error bound for the composition of an activation function and a linear model. Our work also requires conditions similar to small effective ranks, but they are simpler in formulation, as discussed in Section \ref{sec:nooverfit}. Moreover, our results can be applied to  general nonlinear  models.

	\item Anisotropic spectrum and regularization: \cite{Nakkiran19} and \cite{Hastie19} focus their studies on cases with isotropic or well-conditioned regressor covariance matrices. Our study focuses on cases with anisotropic regressor covariance, of which the minimum eigenvalue decays to zero.
	Moreover, since \blue{online learning has the implicit regularization effect }and the ridge penalty is applied in certain scenarios, we do not have the ``double descent'' phenomenon as in other literature \citep{BHM:18,BHMM:19}. A recent paper by \cite{NVKM:20} also showed that for certain linear regression
	models with isotropic data distribution, the ridge penalty regularized regression (in the offline setting) can avoid the ``double descent'' phenomenon.

	\item Online optimization: The aforementioned works mainly focus on offline optimization. For example, \cite{BLLT:19}, \cite{Nakkiran19}, and \cite{Hastie19} show that the generalization error of the offline linear regression solution is closely related to the spectrum of the design matrix.
	In particular, when the minimum eigenvalue is close to zero, the offline learning results become unstable because of singular matrix-inversions.
	Since the design matrix relies on data realization, such instability can only be studied through random matrix theories (RMT).
	While these studies of offline linear regression are interesting and technically deep, their dependence on RMT makes the extensions to nonlinear models difficult.
	In comparison, online learning methods process one data point at a time and do not involve the inversion of design matrices, which facilitates the study of general nonlinear models.

	Moreover, in terms of practical applications, online optimization methods such as SGD are  appealing due to their low per-iteration complexity compared to offline optimization.  Therefore, this paper focuses on the generalization error for  online learning in overparameterized settings.

\end{enumerate}

For online optimization, the stochastic gradient descent (SGD), which dates back to \cite{robbins1951}, is perhaps the most widely used method in practice. The convergence rates of the SGD for convex loss functions have been well studied in the literature (see, e.g., \citealp{zhang2004solving}, \citealp{nesterov2008confidence}, \citealp{BM11},  \citealp{Lan12OSGD}, \citealp{Bach:12}, \citealp{bach2013non}). For the constant stepsize SGD,  \cite{BM11} provided the generalization error bound in Theorem 1 of their paper. However, their bound has an explicit linear dependence on $p$, which is not applicable to the overparameterized setting. Our paper provides a more refined generalization error bound, which incorporates the Hessian spectrum to capture the ``low dimension effect'' in the overparameterized setting.
\blue{  When ridge regularization is presented, existing results show that the generalization error is dimension independent \citep{shalev2014understanding, zhang2005learning,carratino2018learning}. But, in general, these results need the norm of population gradient $\nabla F$ to be dimension independent (See Section 14.5.3 in  \cite{shalev2014understanding}). Our new results do not have this restriction but only require  stochastic gradient  variance to be independent of the dimension. This is a much less stringent  restriction because the variance can be reduced by various techniques (see, e.g., \cite{johnson2013accelerating}).}

\iffalse
\begin{enumerate}[1)]
	\item  Nonlinearity: the results of \cite{BLLT:19} and \cite{Nakkiran19} focus mostly on linear regression scenarios. \cite{Hastie19} considers extensions to models of form $y=\sigma(w^Tx)$, which is quite restrictive and far from complex models such as neural networks. While we still use linear regression to provide statistical interpretations, but our framework can in principle be applied to general nonlinear models.
	\item Anisotropic spectrum and regularization: \cite{Nakkiran19} and \cite{Hastie19} focus their studies on the isotropic or well conditioned cases.
	This is quite different from our angle, as the motivating example in Section \ref{sec:motivate} is unlikely to be well conditioned.
	\cite{BLLT:19} also studies linear regression generalization error with low effective dimensions. But it considers only ridgeless regression, and likewise \cite{Nakkiran19}. Using ridge regression in general helps the generalization error, so in our results, we do not have the ``double descent" phenomena exist in the other works. This indicates ridge regression is more practical and deserves better understanding. Our study shows how should the regularization parameter depend on the Hessian spectrum. This is not discussed in existing works.
	\item Online optimization: all existing works discuss only offline optimization. Online optimization is important in practice due to its computational complexity. It also offers implicit regularization, which further improves the generalization bounds. Aside from these practical benefits, it is actually significantly easier to analyze than offline optimization. For example, \cite{BLLT:19}, \cite{Nakkiran19} and \cite{Hastie19} all show that offline linear regression generalization error is closely connect to the spectrum of the design matrix. The design matrix relies on data realization, so its spectrum can only be studied through random matrix theories. While such studies are interesting by themselves, they are technical and not easily generalizable for other models. This partly explain why our framework can applies to general nonlinear models.
\end{enumerate}
\fi

Overparameterized neural network (NN) is a very active research direction.
There are several existing works explaining why overfitting does not happen in large NN   \citep{GRS:18,LL2018,NLBLS:19,ALL:19,ADHLW:19, EMW19, EMWGD19}.
Interestingly, the conditions they impose are largely similar to  the ones we will use.
Namely, they require the high dimensional input data and the Frobenius norm of true weight matrices to be  bounded by constants. For this to be true, only a small portion of the data or model components can be significantly active, which satisfies  the concept of low effective dimension.

On the other hand, our study of two-layer NN in Section \ref{sec:NN} is different from existing results in the following perspectives.  One popular way to analyze generalization error is by analyzing the Rademacher complexity \citep{GRS:18, NLBLS:19, EMW19}, which can be used to establish an upper bound of the difference between training error and generalization error  (see, e.g.,  Theorem 3.3 of \cite{MRT18}). However, these results are usually derived in an offline optimization setting, while our paper focuses on the result from online SGD.  \cite{LL2018} and \cite{ALL:19} both studied NN generalization error with SGD iterations. But they mainly focused on classification scenarios where the loss function is bounded. Moreover, \cite{LL2018} required the loss function to be of a logistic form, and \cite{ALL:19} studied the running average generalization error. Our results can be applied to regression NN with unbounded loss functions. \cite{ADHLW:19} and  \cite{EMWGD19} studied NN generalization bound with deterministic gradient descent. Moreover, their studies assume a certain data angle or Gram matrix to have a strictly positive minimal eigenvalue. Please see Section \ref{sec:NN} for more detailed comparisons with these works.

\section{A Generalization Bound}
\label{sec:generalize}
In this section, we present a general result on the generalization bound for the SGD solution from \eqref{eq:sgd_iter}.

\subsection{Preliminaries: high dimensional norms and non-convex energy landscape}
\label{sec:prelim}
\blue{ The main issue this paper tries to understand is the high dimensional generalization error when using SGD as the training method.
In some simple scenarios, the true model parameters are ``sparse", so $\|w^*\|$ does not grow with the dimension.
This allows us to measure the distance between SGD iterate $w_n$ and $w^*$ directly.
In other scenarios, $w^*$ can be very dense, and $\|w^*\|$ may grow linearly or even faster with the dimension.
To resolve this issue, we define  the following norms: }
\begin{defn}\label{defn}
	Given a matrix $A\in \mathbb{R}^{p\times p}$ and $\lambda$, we decompose $\mathbb{R}^p=S_\lambda\oplus S_\bot$, where $S_\lambda$ consists of eigenvectors of $A$ with eigenvalues above $\lambda >0$ and $S_\bot$ is the orthogonal complement of $S_\lambda$. Given any vector $v$, denote its decomposition as $v=v_\lambda+v_\bot$, where $v_\lambda\in S_\lambda$ and $v_\bot\in S_\bot$. Then define
	\begin{align}\label{def:newnorm}
	\|v\|^2_{A}=v^TA v,\quad \|v\|^2_{A,\lambda}:=\lambda\|v_\lambda\|^2+ v_\bot^TAv_\bot.
	\end{align}
\end{defn}
 We introduce the norm $\|v\|^2_A$, whose value can be independent of the ambient dimension $p$.   The second norm $\|v\|^2_{A,\lambda}$ is a truncated version of the first norm, it essentially truncates all eigenvalues of $A$ above $\lambda$ to $\lambda$.
It is easy to see that $\|v\|^2_{A,\lambda}\leq \|v\|^2_A$. We introduce the second norm  because $\|v\|^2_{A,\lambda}$ converges to zero when the regularization parameter $\lambda$ does, while $\|v\|^2_A$ is independent of $\lambda$.

\blue{ It is well known that SGD works well for convex problems. This is also true for our theoretical analysis, which works best in convex settings.
On the other hand, many practical problems are non-convex,
which makes the statistical learning problem technically more challenging.}
 First, the function $F$ can have multiple local minima, and each local minimum has an attraction basin, which is a ``valley" in the graph of $F$.
Within each valley, we assume that $F$ is \blue{ locally convex.
Machine learning and theoretical deep learning literature often study the scenarios that local minima lie in large and shallow valleys, which lead to more stable generalization performance.}

\blue{Suppose $\mathcal{D}$ is the attraction basin of the optimal solution $w^*$ in \eqref{eq:sto_opt}, initializing SGD in $\mathcal{D}$ will generate iterates converging to $w^*$  with high probability.  So a natural question is the gap between the estimator learned from SGD and $w^*$.}
On the other hand, if the SGD iterates  take place outside $\mathcal{D}$, the output can be irrelevant to the properties of $w^*$.
\blue{ Therefore, we need to introduce a stopping time $\tau$, which describes the first time SGD exits $\mathcal{D}$:
\[
\tau=\min\{n: w_n\notin \mathcal{D}\},
\]
where $w_n$ is the $n$-th SGD iterate defined in \eqref{eq:sgd_iter}. Our generalization analysis will assume the SGD iterates stay within $\mathcal{D}$. We will also provide bounds of probability that SGD leaves $\mathcal{D}$. }

\blue{While it is reasonable to assume that $w^*$ as a local minimum is in the valley $\mathcal{D}$, verifying this assumption can be difficult. For example, because we do not have access to the population loss function $F$ or the Hessian directly, to check the convexity of $F$, we need to investigate $\widehat{F}$ instead. There will be a certain inaccuracy due to the randomness in $\widehat{F}$.  As another example, while we know the Hessian of $F$ is positive semidefinite at $w^*$ because $w^*$ is a local minimum, $F$ does not have to be convex in the neighborhood  $w^*$. For both these examples, it is more accurate to say $F$ is ``approximately convex" in $\mathcal{D}$. Our analysis can also extend to such very challenging cases by introducing proper regularizations.  On the other hand,  if $F$ is very non-convex in $\mathcal{D}$, then one should not expect that SGD will produce good learning results. Therefore, to achieve a reasonable generalization error, we need $F$ to be very close to convex.  In many applications, this can be done by choosing either a very large sample size $N$ or a very small neighborhood around $w^*$. }

Based on our discussion, we have the following assumption on the population risk function,
\begin{aspt}
	\label{aspt:convex}
	The optimal solution $w^*$ of the population risk $F$ has a neighborhood $\mathcal{D}$, such that for some positive semidefinite (PSD) matrix $A$ and $\delta \in [0,1/2)$,
	\begin{equation}\label{eq:cond}
	-\delta A\preceq  \nabla^2F(w) \preceq A,\quad \forall \; w\in \mathcal{D}.
	\end{equation}
\end{aspt}
In Assumption \ref{aspt:convex} and in the sequel, for two symmetric matrices $C, D$, $C\preceq D$ indicates that $D-C$ is positive semidefinite (PSD). The upper bound on the Hessian matrix $\nabla^2F(w) \preceq A$ is widely assumed in the statistical literature.
The parameter $\delta$ above describes the level of non-convexity. In particular, $\delta=0$ indicates that $F$ is convex within $\mathcal{D}$.
However, our condition in \eqref{eq:cond} is more general since $\delta$ can be strictly positive, which allows $F$ to be non-convex.
On the other hand, although our generalization error bound holds for $\delta\in [0,1/2)$, for this upper bound to be smaller than a certain threshold, $\delta$ needs to be small.  Please see Corollary \ref{cor:selectpara_online} for the exact dependence of $\delta$ in the upper bound.

\subsection{\blue{Generalization bound with sparse true parameter }}
\label{sec:main}
\blue{ We will discuss two possible scenarios with high dimensional machine learning. In the first case, the true parameter $w^*$ is sparse or weak so that its $l_2$ norm does not depend on the dimension. In this case, we have the following results: }
	\blue{
\begin{thm}
	\label{thm:Asgd}
	Under Assumption \ref{aspt:convex}, suppose $w_0\in \mathcal{D}$ and  there is a constants $r$ and $c_r$  such that
	\begin{equation}
	\label{eqn:sgvarianceless}
	\mathbb{E} \| \nabla f(w,\zeta)-\nabla F(w)\|^2\leq  r^2+c_r |(w-w^*)^T\nabla F(w)|,\quad \forall w\in \mathcal{D}.
	\end{equation}
	Then if the ridgeless SGD stepsize $\eta$ and the regularization parameter  $\lambda$ satisfy
	\begin{align*}
	\eta \leq\min\Big\{ \frac1{4(1+c_r)(\|A\|+\lambda)}, 1\Big\}, \quad 2\delta \|A\| \leq \lambda \leq 1,
	\end{align*}
we have the generalization error for the averaged SGD,
	\begin{align}
	\label{eqn:opt2ASGD}
	&\mathbb{E} \left[1_{\tau\geq N-1} G(\bar{w}_N)\right]\leq \frac{2\mathbb{E} \|w_0-w^*\|^2}{N\eta}+2\eta r^2+8\lambda\|w^*\|^2,
	\end{align}
	where the generalization error $G$ is defined in \eqref{eq:generalization} and $\bar{w}_N=\frac1N\sum_{i=0}^{N-1} w_i $ is the averaged SGD iterate.
\end{thm}
We note that when $F$ is locally convex in $\mathcal{D}$ (i.e., $\delta=0$ in \eqref{eq:cond}), this result incorporates the implicit regularization case by setting $\lambda=0$. The generalization error bound in \eqref{eqn:opt2ASGD} contains three terms. The first term decays with the sample size $N$. The second term is controlled by the stepsize $\eta$.
The last term $8\lambda\|w^*\|^2$ is a bias caused by the regularization. Since $F_\lambda$ is different from $F$, the minimizer of   $F_\lambda$ is also different from $w^*$.
In other words, if $F$ is convex in $\mathcal{D}$ (i.e., $\delta=0$), it is actually better to do rigdeless regression by setting $\lambda=0$. Note that in this case of implicit regularization, the generalization error bound in \eqref{eqn:opt2ASGD} is dimensional independent when  $\|w^*\|^2$ is dimension independent with the initialization  $w_0=\mathbf{0}$.
}

\subsection{Generalization bound with non-sparse true parameter}
\blue{ In some scenarios, $\|w^*\|$ may grow with the dimension.  While the results in Theorem \ref{thm:Asgd} still hold, the estimate \eqref{eqn:opt2ASGD} is no longer dimension independent. In this case, the learning cannot rely only on implicit regularization. We will need to introduce regularization and high dimensional norms as in Definition \ref{defn} for these problems: }
\begin{thm}
	\label{thm:sgd}
	Under Assumption \ref{aspt:convex}, suppose $w_0\in \mathcal{D}$ and  there is a constants $r$ and $c_r$  such that
	\begin{equation}
	\label{eqn:sgvariance}
	\mathbb{E} \| \nabla f(w,\zeta)-\nabla F(w)\|^2\leq  r^2+c_r r^2\min\{G(w),\|w\|^2\},\quad \forall w\in \mathcal{D}.
	\end{equation}
	Then if the SGD hyper-parameters, the stepsize $\eta$ and the regularization parameter $\lambda$, satisfy
	\begin{align*}
	\eta \leq \min \Big\{1, \dfrac{\lambda}{12\|A\|^2+6 \lambda^2+6c_r r^2}, \dfrac{1}{12\|A\|}, \frac{\lambda}{6c_r\|A\|r^2} \Big\},
	\quad 4\delta\|A\|\leq \lambda\leq 1,
	\end{align*}
\blue{	we have
	\begin{align}\label{eqn:opt2}
	\mathbb{E} [ G(w_{N})1_{\tau\geq N}] &\leq  4 \|w^*\|^2_{A,\lambda}+\frac{C_1}{\lambda} (\eta + \delta) \\
	\notag
	&\quad +\exp(-\tfrac14\lambda N \eta  )\mathbb{E} [ G(w_0)+ 4N\|A\|\|w_0\|^2 ],
	\end{align}
	with $C_1=60\|A\| \left(r^2+\|w^*\|_A^2\right) + 10\|w^*\|_A^2$. }
\end{thm}
\blue{ While it is not completely new that SGD on convex ridge regression has dimension independent generalization error \citep{shalev2014understanding, zhang2005learning,carratino2018learning}, in general, these results need the norm of gradient $\nabla F$ to be dimension independent (See Section 14.5.3 in \cite{shalev2014understanding}). Theorem \ref{thm:sgd} does not have this restriction. In fact, the population gradient $\nabla F$ can be unbounded in many applications (e.g., linear regression).  In contrast, our assumption for the stochastic gradient is imposed on its variance, see
\eqref{eqn:sgvariance}. This is a much relaxed assumption because the variance can be reduced by various techniques (e.g., \cite{johnson2013accelerating}) or simply by increasing the mini-batch size for stochastic gradient computation.  }

\subsection{\blue{SGD configuration with given  generalization error target }}
In Section \ref{sec:nooverfit}, we will explicitly define the low effective dimension so that $C_1$ and the upper bound in \eqref{eqn:opt2}  are independent of dimension $p$, or depend on $p$ only via a polynomial logarithmic factor.
This differentiates our result from the estimates in existing literature on SGD, e.g., \cite{BM11}. In particular, most existing results do not take the Hessian spectrum into consideration, so they will have linear or stronger dependence on the dimension $p$; while our results do not necessarily have such dependence.

In the upper bound \eqref{eqn:opt2}, each term  carries a strong statistical interpretation, which will be illustrated using linear models in the next subsection (see Section \ref{sec:SA}).
In particular, the term $\|w\|^2_{A,\lambda}$ in \eqref{eqn:opt2}
can be interpreted as the bias caused by minimizing $F_\lambda$ instead of $F$, it decays with the regularization parameter $\lambda$ shrinking to zero. The term $\frac{C_1\eta}{\lambda}$ is the variance induced by the SGD algorithm, which increases as $\lambda$ decreases. This reveals that under our current problem setting, $\lambda$ controls a bias-variance tradeoff. Ideally, we can choose  small $\lambda$ and stepsize $\eta$ to make both the bias and variance small. However, this comes with a price. As the convergence rate scales with $\lambda\eta$, so using small $\lambda$ and $\eta$ need to be compensated with a large sample size $N$ (i.e., the number of iterations in SGD).

We can quantify these tradeoffs by considering a practical scenario where a generalization error is pre-fixed to be $\epsilon$, then our results provide guidelines on how to tune the parameters:
\blue{
\begin{cor}[Corollary of Theorem \ref{thm:Asgd}]\label{cor:selectpara_onlineridgeless}
	Suppose there is an universal constant $C_0$ such that
	\[
	\| w^*\|^2, \| w_0-w^*\|^2 \leq C_0.
	\]
	Given any $\epsilon>0$, if the regularization parameter $\lambda(\epsilon)$, the stepsize $\eta(\epsilon)$, the non-convexity parameter $\delta(\epsilon)$, and the sample size  $N(\epsilon)$ satisfy
	\begin{align}
	\label{eq:parameter2.5}
	&\lambda(\epsilon) \leq \min \left\{ \frac{\epsilon}{8C_0},1\right\},\quad  \delta(\epsilon) \leq \min \Big\{ \frac{\epsilon}{16C_0\|A\|}, \frac{1}{2\|A\|}\Big\},  \\
	\notag
	& \eta(\epsilon) <\min\left\{ \frac1{2(1+c_r)(\|A\|+\lambda(\epsilon))},\frac{\epsilon}{2r^2},1\right\},\quad N(\epsilon) > \frac{2C_0}{\epsilon\eta(\epsilon)},
	\end{align}
	then $\mathbb{E} [ G(\bar{w}_N)1_{\tau\geq N} ] \leq 3\epsilon$. \end{cor}
}

\begin{cor}[Corollary of Theorem \ref{thm:sgd}]\label{cor:selectpara_online}
	Given any $\epsilon>0$, if the regularization parameter $\lambda(\epsilon)$, the stepsize $\eta(\epsilon)$, the non-convexity parameter $\delta(\epsilon)$, and the sample size  $N(\epsilon)$ satisfy
	\begin{align}
	\label{eq:parameter}
	&4 \| w^*\|_{A,\lambda(\epsilon)}^2< \epsilon, \quad \delta(\epsilon) \leq \frac{\lambda(\epsilon)\epsilon}{C_1} , \quad \eta(\epsilon) < \frac{\lambda(\epsilon)\epsilon}{C_1},  \\
	\notag
	& N(\epsilon) > \max\left\{ \frac{-4\log\{\epsilon/2\mathbb{E} [ G(w_0) ] \}}{\lambda(\epsilon) \eta(\epsilon)}, \frac{-8\log\{\epsilon\lambda(\epsilon)\eta(\epsilon)/(64\|A\|\mathbb{E} [ \|w_0\|^2 ]) \}}{\lambda(\epsilon) \eta(\epsilon)}  \right\},
	\end{align}
	and the conditions of Theorem \ref{thm:sgd} hold, then $\mathbb{E} [ G(w_N)1_{\tau\geq N} ] \leq 4\epsilon$.
\end{cor}

It is noteworthy that \eqref{eqn:opt2} only discusses the scenario where SGD iterates stay in the domain $\mathcal{D}$.
This is necessary since all our conditions are imposed only within $\mathcal{D}$. Once an SGD iterate leaves $\mathcal{D}$, there is no particular reason it can get back to  $\mathcal{D}$.
Another possible improvement is to find an upper bound for the conditional generalization error $\mathbb{E}[G(w_N)|\tau\geq N]$. But this is not feasible when $\mathcal{D}$ is a general region. For example, if $\mathcal{D}$ is the intersection between any set and $\{w:G(w)\geq G(w_0)-1\}$, the conditional expectation will be larger than $G(w_0)-1$, while $\{\tau\geq N\}$ may have a nonzero occurrence probability.
 In Section \ref{sec:conclusion}, we will briefly discuss how to remedy such a restriction in practice through data splitting

\blue{
In practice, SGD is often implemented with mini-batch data to reduce the noise within stochastic gradient. With regularization, the mini-batch SGD with batch-size $J$ can be formally written as
\[
w_{n+1}: =w_{n} -\frac{1}{J}\eta \sum_{k=Jn+1}^{J(n+1)}(\nabla f(w_{n}, \zeta_k)+\lambda w_n),
\]
where \emph{i.i.d.} data $\{\zeta_{Jn+1},\ldots, \zeta_{J(n+1)}\}$ forms the $n$-th batch of data. Our results can be extended to  mini-batch SGD as well. To see this, we simply let
$z_n=\{\zeta_{Jn+1},\ldots, \zeta_{J(n+1)}\}$ and
\[
\tilde{f}(w,z_n)=\frac{1}{J} \sum_{k=Jn+1}^{J(n+1)}f(w_{n}, \zeta_k).
\]
Note that $\mathbb{E} \tilde{f}(w,z_n)=\mathbb{E} f(w,\zeta_i)=F(w)$. It is also straight forward to see that applying our SGD formulation \eqref{eq:sgd_iter} on $\tilde{f}$ with $z_n$ leads to the mini-batch SGD. Applying our results, e.g. Corollaries \ref{cor:selectpara_onlineridgeless} and \ref{cor:selectpara_online}, to mini-batch  SGD requires simple modifications for only two parameters. First, the variance of stochastic gradient $\nabla \tilde{f}(w,z)$ is only $\frac{1}{J}$ of the variance of $\nabla f(w,\zeta)$,  so the parameter $r^2$ in mini-batch SGD should be $\frac{1}{J}$ of $r^2$ in the standard SGD. Second, because each iteration of the mini-batch SGD requires $J$ data samples, so the overall sample size should be $NJ$.
}

\subsection{Statistical interpretation in linear models and bias-variance tradeoff}
\label{sec:SA}

To facilitate better understanding our results, we will use linear models to illustrate the statistical interpretation of each term in the generalization upper bound in \eqref{eqn:opt2}.
In linear regression, each \emph{i.i.d.} observation contains a pair of dependent and response  variables, $\zeta_i = (x_i, y_i)\in \mathbb{R}^p\times \mathbb{R}$, where $y_i$ is generated by the following model
\begin{equation}\label{eq:linear_model0}
y_i = x_i^{T} w^* + \xi_i.
\end{equation}
In \eqref{eq:linear_model0},  $w^*$ is the true regression coefficient, and  the noise term $\xi_i$ is independent of $x_i$ with zero mean and a finite variance $\sigma^2$. For the ease of illustration, we assume $x_i \sim \mathcal{N}(0, \Sigma)$. The generalization error of this linear model takes the following form,
\begin{align}
\label{eqn:linloss1}
G(w) =\mathbb{E}\Big[ \frac12(y_i-w^T x_i)^2-\frac12(y_i-(w^*)^T x_i)^2 \Big]= \frac{1}{2} (w-w^*)^T\Sigma(w-w^*).
\end{align}
From \eqref{eqn:linloss1}, we can see that $G(w)$ has a strong dependence on the structure of $\Sigma$. Let us denote the eigenvalues of $\Sigma$ by  $\lambda_1\geq \lambda_2\geq\cdots\geq \lambda_p$, and the eigenvector corresponding to $\lambda_i$ by $v_i$. Then the parameter error, $v^T_i(w-w^*)$, contributes to $G(w)$ via the factor $\lambda_i$.

It is well known that SGD can be interpreted as a stochastic approximation of the gradient descent \citep{robbins1951}, namely we can rewrite \eqref{eq:sgd_iter} as
\begin{equation}\label{eq:sgd_stoc_approx}
w_{n+1}=w_n-\eta\nabla F_\lambda(w_n)+\eta \xi_n,
\end{equation}
where $\xi_n=-\nabla f(w_n,\zeta_n)+\nabla F(w_n)$ is the noise in stochastic gradient. For the quadratic loss with the ridge penalty  $F_\lambda$, the SGD iterates in \eqref{eq:sgd_stoc_approx} take the following form,
\begin{equation}
\label{eqn:SA}
w_{n+1}=w_n-\eta\Sigma (w_n-w^*)-\eta \lambda w_n+\eta \xi_n=(I-(\Sigma+\lambda I)\eta)(w_n-w^*_\lambda)+w^*_\lambda+\eta \xi_n,
\end{equation}
where $w^*_\lambda:=(\Sigma+\lambda I)^{-1}\Sigma w^*$ is the minimizer of $F_\lambda(w)=\mathbb{E} \frac{1}{2} (y- w^T x)^2 + \frac{\lambda }{2} \|w\|^2$.

It is easy to see that $w_n$ then follows a vector autoregressive (VAR) model (see, e.g.,  Chapter 8 of \citealp{Tsay}). For the ease of discussion,  we simply treat $\xi_n$ as $\mathcal{N}(0,\frac{r^2}{p}I)$, so $\mathbb{E} \|\xi_n\|^2=r^2$ as we assumed in Theorem \ref{thm:sgd}.
Admittedly, the independent Gaussian assumption here contradicts our anisotropic assumption. We are assuming it here to gain an intuitive understanding.
Then the stationary distribution of $w_n$ in \eqref{eqn:SA} is a Gaussian $\mathcal{N}(\mu,V)$. Take expectation and covariance on both sides of  \eqref{eqn:SA}, and the $\mu$ and $V$ take the following form (see Chapter 8.2.2 of \citealp{Tsay} ),
\[
\mu=(I-(\Sigma+\lambda I)\eta)(\mu-w^*_\lambda)+w^*_\lambda\Rightarrow \mu=w^*_\lambda,
\]
\[
V=(I-(\Sigma+\lambda I)\eta)V(I-(\Sigma+\lambda I)\eta)+\frac{\eta^2 r^2}{p} I.
\]
When the stepsize $\eta\leq \|\Sigma+\lambda I\|^{-1}$, $(\Sigma+\lambda I)^2\eta\preceq \Sigma+\lambda I $, so
\[
V=\frac{r^2\eta}{p}(2(\Sigma+\lambda I)-(\Sigma+\lambda I)^2\eta)^{-1}\preceq \frac{r^2\eta}{p}(\Sigma+\lambda I)^{-1}.
\]
These results give us the limiting average generalization error
\begin{align}
\notag
\lim_{n\to \infty}\mathbb{E} G(w_n)&=\frac{1}{2}(w^*_\lambda-w^*)^T \Sigma(w^*_\lambda-w^*)+\frac12\text{tr}(V\Sigma)\\
\label{eqn:biasvar}
&\leq G(w^*_\lambda)+\frac{r^2\eta}{2p}\text{tr}((\Sigma+\lambda I)^{-1}\Sigma).
\end{align}
The first term $G(w^*_\lambda)$ is the bias caused by using regularization. Indeed, the optimizer of $F_\lambda$ is $w^*_\lambda$ rather than  $w^*$. Recall that $(\lambda_i, v_i)$ are the eigenvalues and eigenvectors of $\Sigma$. We define $a_i=\langle v_i, w^*\rangle$ and further express $G(w^*_\lambda)$  in \eqref{eqn:biasvar} as follows,
\begin{align*}
G(w^*_\lambda)&=\frac12 ((\Sigma+\lambda I)^{-1}\Sigma w^*-w^*)^T\Sigma((\Sigma+\lambda I)^{-1}\Sigma w^*-w^*)\\
&=\frac12 \lambda^2(w^*)^T(\Sigma+\lambda I)^{-1}\Sigma (\Sigma+\lambda I)^{-1}w^*=\frac12\sum_{i=1}^p  \frac{\lambda^2 \lambda_i a_i^2}{(\lambda+\lambda_i)^2}.
\end{align*}
Note that when $\lambda_i\geq 0$, $\frac{\lambda^2\lambda_i}{(\lambda_i+\lambda)^2}\leq \frac{\lambda^2\lambda_i}{\lambda^2}=\lambda_i$, and by Young's inequality $\frac{\lambda^2\lambda_i}{(\lambda_i+\lambda)^2}\leq \frac{\lambda^2\lambda_i}{4\lambda_i\lambda}\leq \lambda$. Therefore, we have the following upper bound of $G(w^*_\lambda)$
\begin{equation}\label{eq:G_upper}
G(w^*_\lambda)\leq \frac12\sum_{i=1}^p (\lambda\wedge \lambda_i) a_i^2=\frac12\|w^*\|_{\Sigma,\lambda}.
\end{equation}
The upper bound in \eqref{eq:G_upper} is essentially the first term in \eqref{eqn:opt2} by noticing that $\Sigma = A = \nabla^2 F(w)$ in linear regression, which  gives an upper bound for the bias.

For the second variance term in \eqref{eqn:biasvar},
\begin{equation}\label{eq:var}
\text{var}(\lambda):= \frac{r^2\eta}{2p}\text{tr}((\Sigma+\lambda I)^{-1}\Sigma)=\frac{r^2\eta}{2p}\sum_{i=1}^p \frac{\lambda_i}{\lambda_i+\lambda}\leq\frac{r^2\eta}{2p}\sum_{i=1}^p \frac{\lambda_i}{\lambda}=\frac{\eta r^2\lambda_1}{2\lambda}.
\end{equation}
This upper bound is essentially the second term in the generalization upper bound in \eqref{eqn:opt2}, as it  depends linearly on $\eta, \lambda^{-1}, \lambda_1 r^2$.

The first two terms in  \eqref{eqn:opt2} are based on the limiting average generalization error. With finite SGD iterations, the iterate $w_n$ may not reach the limiting distribution. On the other hand, for VAR models, it is well known that the speed of convergence for $w_n$ is exponential, and the convergence rate is closely related to  the minimum eigenvalue  $\lambda_{\min}((\Sigma+\lambda I)\eta)=\lambda\eta$
(see, e.g., \citealp{Tsay} Chapter 8.2.2). The finite iterate error leads to the third term of $\exp(-\frac14\lambda \eta N)$ in generalization error bound in \eqref{eqn:opt2}.

\blue{ In the special case that $\lambda=0$, \eqref{eqn:biasvar} reduces to
\[
\lim_{n\to \infty}\mathbb{E} G(w_n)\leq G(w^*)+\frac{r^2\eta}{2p}\text{tr}(I)=r^2\eta.
\]
}

Finally, we consider the scenario where $\Sigma$ is indefinite with $\delta=-\lambda_{\min}(\Sigma)>0$. While the population loss $F$ is non-convex, when adopting $\lambda>2\delta$, we have that $\Sigma+\lambda I$ is positive definite and $F_\lambda$ is convex.
Then the generalization upper bounds need to be updated by replacing $\lambda$ with $\lambda-\delta$, which leads to a perturbation on the  order of $\delta$. In particular, note that by Young's inequality, the derivative of the bias term with respect to $\lambda$ is bounded by
\[
|\partial_\lambda G(w^*_\lambda)|=\sum_{i=1}^p  \frac{\lambda \lambda^2_i a_i^2}{(\lambda+\lambda_i)^3}\leq
\sum_{i=1}^p  \frac{\lambda_i a_i^2}{4(\lambda+\lambda_i)}\leq \frac{1}{4\lambda}\sum_{i=1}^p \lambda_ia_i^2=\frac{\|w^*\|^2_\Sigma}{4\lambda}.
\]
The derivative of the variance term with respect to $\lambda$ in \eqref{eq:var} is bounded by Young's inequality,
\[
|\partial_\lambda \text{var}(\lambda)|=\frac{r^2\eta}{2p}\sum_{i=1}^p \frac{\lambda_i}{(\lambda_i+\lambda)^2}\leq
\frac{r^2\eta}{2p}\sum_{i=1}^p \frac{\lambda_1}{\lambda^2}\leq \frac{r^2 \eta\lambda_1}{2\lambda^2}.
\]
Therefore, replacing $\lambda$ with $\lambda-\delta$ to handle non-convexity,  we need to add the following term in the generalization error bound,
\[
\delta |\partial_\lambda F(w^*_\lambda)|+\delta |\partial_\lambda \text{var}(\lambda)|\leq \delta\left(\frac{\|w^*\|^2_\Sigma}{4\lambda}+\frac{r^2\lambda_1 \eta}{2\lambda^2}\right).
\]
This term can be further upper bounded by the last term of \eqref{eqn:opt2}.

\section{Low Effective Dimension}
\label{sec:nooverfit}

Given the generalization error bound in Theorem \ref{thm:sgd}, we introduce the concept of ``low effective dimension'' and show that the generalization error bound in \eqref{eqn:opt2} can be independent (or dependent poly-logarithmically) of the ambient dimension $p$ in an overparameterized regime. We will use the $O$ and $\Omega$ notations to hide constants independent of $p$ and use the $\widetilde{O}$ and $\widetilde{\Omega}$ notations to hide constants depend poly-logarithmically on $p$.
In particular, we introduce the following standard asymptotic notations: $A_\epsilon=O(f(\epsilon)), B_\epsilon=\widetilde{O}(f(\epsilon)), C_\epsilon=\Omega(f(\epsilon)), D_\epsilon=\widetilde{\Omega}(f(\epsilon))$. These notations mean that there exist some universal constants $c$ and $C>0$ such that,
\[
A_\epsilon\leq Cf(\epsilon),\quad B_\epsilon\leq C(\log p)^{c} f(\epsilon),\quad  C_\epsilon\geq Cf(\epsilon),\quad D_\epsilon\geq C(\log p)^c f(\epsilon).
\]

\subsection{Initialization and stochastic gradient variance}
We investigate the terms that appear in the generalization bound \eqref{eqn:opt2}: whether they can be independent of $p$; and how they affect the necessary sample size $N(\epsilon)$ in \eqref{eq:parameter}.

First, we notice that the terms related to initialization $w_0$, i.e., $\mathbb{E} \|w_0\|^2$ and $\mathbb{E} G(w_0)$,  appear in the sample size $N(\epsilon)$ in \eqref{eq:parameter}. If the region $\mathcal{D}=\mathbb{R}^p$, we can often choose appropriate $w_0$ so that $\mathbb{E} \|w_0\|^2$ and $\mathbb{E} G(w_0)$ are independent of $p$. For example, for linear regression loss function in \eqref{eqn:linloss1}, we can pick $w_0=0$, then $\mathbb{E} G(w_0)=\frac12 \|w^*\|^2_A$ with $A=\Sigma$, which will be bounded by an $O(1)$ constant as shown below.  For a restrictive region $\mathcal{D}$,  although $\mathbb{E} \|w_0\|^2$ and $\mathbb{E} G(w_0)$ may scale as a polynomial function of $p$,  $N(\epsilon)$ only depends logarithmically on these two terms. Therefore,  the dimension dependence of $N(\epsilon)$ is only logarithmic.

Second, we consider the stochastic gradient variance $r^2$, which contributes to the term $C_1$ in \eqref{eqn:opt2}. In a typical setting, it scales roughly as the squared population gradient, i.e.,
\begin{align*}
\mathbb{E} \|\nabla f(w,\zeta)-\nabla F(w)\|^2&\approx O(\mathbb{E} \|\nabla F(w)\|^2)\\
&=O(\mathbb{E} \|\nabla F(w)-\nabla(F(w^*))\|^2)\\
&=O(\mathbb{E} \|\nabla^2F(w) (w-w^*)\|^2)\\
&\mbox{Assume that $w\sim \mathcal{N}(0,I_p)$ and $\nabla^2 F\preceq A$}\\
&=O\big(\|A\|(\|w^*\|_A^2+\text{tr}(A))\big).
\end{align*}
We will see such an approximation holds for many applications of interest. Moreover, we have $\|A\|\leq\text{tr}(A)$, which can often be $p$-independent as discussed below. The scale of $\|w^*\|_A$ will also be discussed next.

From the discussion above, we only need to focus on two terms in \eqref{eqn:opt2}, $\|w^*\|_{A}$ and $\|w^*\|_{A,\lambda}$. For the generalization error to be small and independent of $p$, we need to show $\|w^*\|_{A}$ is dimension independent and $\|w^*\|_{A,\lambda}$ decreases as $\lambda$ decreases.

\subsection{Low effective dimension settings}
\label{sec:low_eff}
In this section, we formally define two settings of low effective dimension  as Assumptions \ref{aspt:sparse} and \ref{aspt:trace}. In Sections \ref{sec:linear} and \ref{sec:non_linear}, we will show that these assumptions easily hold for a wide range of convex and non-convex statistical models.

\subsubsection{Sparse true parameter}

The first setting is characterized in the following assumption.

\begin{aspt}
	\label{aspt:sparse}
	The followings are true
	\begin{enumerate}[1)]
		\item  $\|A\|$ with $A$ defined in Assumption \ref{aspt:convex} is bounded by  an $O(1)$ constant.
		\item $\|w^*\|$ is  bounded by an $O(1)$ constant.
		\item $r^2,c_r$  defined in  Theorem \ref{thm:sgd} are  bounded by $O(1)$ constants.
		\item The initial values $\mathbb{E} \|w_0\|^2$ and $\mathbb{E} G(w_0)$  grow polynomially with $p$.
	\end{enumerate}
\end{aspt}

Assumption \ref{aspt:sparse} can be interpreted as a weak sparsity condition for $w^*$, since there can  be only a few significant components in $w^*$. Sparsity assumption is a very common condition in the statistical literature. However, our assumption only assumes that the $\ell_2$-norm of $w^*$, instead of the $\ell_0$-norm, is bounded. As compared to the $\ell_0$-norm, the $\ell_2$-norm is rotation-free. In addition, we do not need to apply any projection or shrinkage procedures on the SGD iterates.

\blue{ Under Assumption \ref{aspt:sparse},  Corollary \ref{cor:selectpara_online} can be simplified as the following generalization error bound, which shows that the necessary sample size depends on $p$ in a poly-logarithmic factor.  }
\blue{
\begin{prop}\label{prop:sparse}
	Under the conditions in Corollary \ref{cor:selectpara_onlineridgeless} and Assumption \ref{aspt:sparse},  given any $\epsilon>0$, when
	\begin{equation}\label{eqn:sparsity}
	\lambda(\epsilon) = O(\epsilon ), \ \delta(\epsilon) = O(\epsilon), \ \eta(\epsilon)  = O(\epsilon), \ N(\epsilon) = \Omega\Big(\frac{1}{\epsilon^2}\Big),
	\end{equation}
	we have  $\mathbb{E} [ G(\bar{w}_{N})1_{\tau\geq N-1} ] \leq 3\epsilon$.
Moreover, for any $p_0\geq 0$, there are  $A=O(1/p_0)$, if $\mathcal{D}=\{w: \|w-w^*\|^2\leq A\}$, we have
	\[
	\mathbf{P}(\tau\leq N)\leq p_0.
	\]
	Alternatively, if $\delta=0$, for any $\alpha>0$, we take
	\[
	\lambda(\epsilon) = 0, \ \eta(\epsilon)  = O(\epsilon^{1+\alpha}), \ N(\epsilon) = \Omega\Big(\frac{1}{\epsilon^{2+\alpha}}\Big),
	\]
	we have  $\mathbb{E} [ G(\bar{w}_N)1_{\tau\geq N-1} ] \leq 3\epsilon$. Meanwhile, for any $A>\mathbb{E}\|w_0-w^*\|^2$, if $\mathcal{D}=\{w: \|w-w^*\|^2\leq A\}$, we have
	\[
	\mathbf{P}(\tau\leq N) \leq \frac{\mathbb{E} \|w_{0}-w^*\|^2+  O(\epsilon^{\alpha})}{A}.
	\]
\end{prop}
Proposition \ref{prop:sparse} consists of two parts. The first part shows that the generalization error is of order $O(1/\sqrt{N})$ if the non-convexity is of the same order. The second part demonstrates how to bound the probability of SGD escaping the convexity region $\mathcal{D}$ if it is a ball centered at $w^*$. For all $\delta\geq 0$, $A$ needs to be of order $1/\delta$ so that the chance of escaping is less than $\delta$. If the problem is convex in $\mathcal{D}$, $\mathcal{D}$ just need to include $w_0$ to ensure the chance of no-escaping is nonzero. In both cases, the escape is harder when the radius $\sqrt{A}$ is larger. This also explains why machine learning literature is in favor of local-minima in large valleys.
}

\subsubsection{Non-sparse true parameter}
The second setting is technically more interesting, which assumes the data has a low effective dimension in the following sense.  When we say
a component or a linear combination of components of $w$ is effective,  it means that the loss function $F$ has a significant dependence on it. This can be analyzed through the eigen-decomposition of $\nabla^2 F(w)$ or its upper bound $A$ in \eqref{eq:cond}.   Let $(\lambda_i, v_i)$ be the eigenvalue-eigenvectors of $A$, where $\lambda_i$ are arranged in decreasing order. Then a small $\lambda_i$ indicates that $F$ has a weak dependence along the direction of $v_i$.  For the model to have a low effective dimension, there will be only constantly many $\lambda_i$ being significant, while the remaining eigenvalues in sum have a negligible contribution to the overall loss function.  We formally formulate this setting into the following assumption.
\begin{aspt}
	\label{aspt:trace}
	The followings are true
	\begin{enumerate}[1)]
		\item $\text{tr}(A)$ with $A$ defined in Assumption \ref{aspt:convex} is bounded by an $\widetilde{O}(1)$ constant.
		\item  the true parameter $w^*$ is bounded in each of $A$'s eigen-direction, in the sense that
		\begin{equation}\label{eq:W_A_S}
		\|w^*\|_{A,S}:=\max_i\{|\langle v_i,w^*\rangle|, i=1,\ldots,p \}=\widetilde{O}(1).
		\end{equation}
		\item $r^2,c_r$  defined in  Theorem \ref{thm:sgd} are bounded by $\widetilde{O}(1)$ constants.
		\item The initial values $\mathbb{E} \|w_0\|^2$ and $\mathbb{E} G(w_0)$  grow polynomially with $p$.
	\end{enumerate}
\end{aspt}

By Cauchy Schwartz inequality,  we have $\|w^*\|_{A,S}\leq \|w^*\|.$ So Assumption \ref{aspt:trace}  condition 2) is weaker than Assumption  \ref{aspt:sparse} condition 2).  In particular, it can include important cases where we only have upper and lower bounds on each of $w^*$'s components, and $A$ is known to be a diagonal matrix. These cases are not covered by Assumption \ref{aspt:sparse}. On the other hand, the spectrum profile of $A$ will be required to choose the regularization parameter as shown in the following proposition.
\blue{
\begin{prop}
	\label{prop:spetrum}
	By the following inequalities,
	\[
	\|w^*\|^2_A\leq \text{tr}(A)\|w^*\|^2_{A,S},\quad \|w^*\|^2_{A,\lambda}\leq \|w^*\|^2_{A,S}\sum_{i=1}^p \lambda\wedge \lambda_i.
	\]
	Assumption \ref{aspt:trace} implies that  $\|w^*\|_A =\widetilde{O}(1)$ and $\|w^*\|^2_{A,\lambda} =\widetilde{O} \left(\sum_{i=1}^p \lambda\wedge \lambda_i\right).$
	Moreover, under the conditions in Corollary \ref{cor:selectpara_online} and Assumption \ref{aspt:trace},  given any $\epsilon>0$, if the eigenvalues of $A$ follows,
	\begin{enumerate}[1)]
		\item Exponential decay: $\lambda_i=e^{-ci}$ for some constant $c>0$, and setting
	\[
		\lambda=\widetilde{O}(\frac{\epsilon}{|\log \epsilon|}), \
		\delta(\epsilon)=\widetilde{O}\left(\frac{\epsilon^3}{|\log \epsilon|^2}\right),\ \eta(\epsilon)=\widetilde{O}\left(\frac{\epsilon^2}{|\log \epsilon|}\right),\ N(\epsilon)=\widetilde{\Omega}\left(\frac{|\log \epsilon|^3}{\epsilon^3}\right),
		\]
		we have  $\mathbb{E} [ G(w_N)1_{\tau\geq N} ] \leq 4\epsilon$.
		\item Polynomial decay: $\lambda_i=i^{-c}$ for some constant $c>0$,  and setting
		\[
		\lambda(\epsilon) = \widetilde{O}\Big( \epsilon^{
			\frac{c+1}{c}} \Big), \ \delta(\epsilon) = \widetilde{O}\Big( \epsilon^{\frac{3c+2}{c}} \Big), \ \eta(\epsilon)  = \widetilde{O}\Big( \epsilon^{\frac{2c+1}{c}} \Big), \ N(\epsilon) = \widetilde{\Omega}\Big(\frac{|\log(\epsilon)|}{\epsilon^{\frac{3c+2}{c}}}\Big),
		\]
		we have  $\mathbb{E} [ G(w_N)1_{\tau\geq N} ] \leq 4\epsilon$.
	\end{enumerate}
     In both cases,  we have
	\begin{align*}
	\mathbb{E} [ G(w_{N\wedge \tau}) ] \leq &\mathbb{E} [ G(w_0) ]+ \widetilde{O}(\epsilon |\log \epsilon|).
	\end{align*}
	So if $\mathcal{D}=\{w: G(w)\leq (1+a)\mathbb{E} [G(w_0)] \}$, then
	\[
	\mathbf{P}(\tau<N)\leq  \frac{1}{1+a} + \widetilde{O}(\epsilon |\log \epsilon| ).
	\]
\end{prop}
}

We remark that the parameter of the spectrum decay (e.g., the constant $c$ in polynomial decay spectrum) is often assumed to be known for many functional data analysis problems \citep{HH07,CH08}. From Proposition \ref{prop:spetrum}, for both exponential decay and polynomial decay of the Hessian spectrum,  the sample size $N$ only depends on $p$ in a poly-logarithmic factor.

\blue{ Similar to Proposition \ref{prop:sparse},
the second part of this result demonstrates how to bound the probability of SGD escaping the convexity region $\mathcal{D}$ if it is the sub-level set with $w^*$ inside.
The parameter $a$ controls the size of $\mathcal{D}$. A larger $a$ produces a larger $\mathcal{D}$ and hence a smaller escape probability.  }

\begin{rem}
	\label{rem:comparewithBLLT}
	It is interesting to compare our low effective dimension settings with the conditions used in \cite{BLLT:19}. For their main result, Theorem 4 in \cite{BLLT:19}, to yield dimension-independent generalization error bound, three conditions (formulated in our notation) need to hold: 1) $\|w^*\|^2$  is bounded by a constant; 2) $\text{tr}(A)$ is bounded by a constant; 3) the spectrum of $A$ decays not so fast so that, for some $k$, $\sum_{i\geq k} \lambda_i\geq bN \lambda_k$ with some constant $b$. In comparison, our Assumption \ref{aspt:sparse} only requires conditions 1) and 2), but not the technical condition 3). Moreover, our result can also work under Assumption \ref{aspt:trace} where only $\|w^*\|^2_{A,S}$, instead of $\|w^*\|^2$, needs to be bounded.
\end{rem}

\section{Overparameterization in Linear Regression}
\label{sec:linear}
In general, overparameterization may lead to overfitting, but this sometimes can be avoided. Our main result, Theorem \ref{thm:sgd}, provides a general tool to understand why overfitting sometimes happens and sometimes  does not. In this section, we will demonstrate how to apply our results on linear regression models in various high dimensional settings. This section is technically straightforward and is mainly used for pedagogical purpose.  The discussions on more technically challenging  cases for nonlinear and  non-convex models are provided in the next section.

\subsection{Linear regression}
First of all, we will find out the problem related parameters in Theorem \ref{thm:sgd} when applying to linear regression models. As in Section \ref{sec:SA}, we consider \emph{i.i.d.} data points form $\zeta_i = (x_i, y_i)\in \mathbb{R}^p\times \mathbb{R}$, where the response is generated by
\begin{equation}\label{eq:linear_model}
y_i = x_i^{T} w^* + \xi_i.
\end{equation}
In \eqref{eq:linear_model}, $w^* \in \mathbb{R}^p$ is the true model-parameter to be estimated. $\xi_i\in \mathbb{R}$ are observation noise terms in the observation process,
and we assume they are \emph{i.i.d.} with zero mean and variance $\sigma^2$.  For simplicity, we assume that the data $x_i$ are \emph{i.i.d.}  Gaussian distributed, i.e., $x_i \sim \mathcal{N}(0,\Sigma)$. As a remark, our proof also  allows the non-Gaussian distribution with finite fourth moments.

The regression loss of parameter $w$ on data $\zeta_i$ is
\begin{equation}\label{eq:lossfun}
f(w, \zeta_i) = \frac{1}{2} (x_i^T w -y_i)^2.
\end{equation}
Plugging (\ref{eq:linear_model}) into (\ref{eq:lossfun}) and taking expectation, and we  find the population loss function
\begin{align}\label{eq:polossfun}
F(w) = \frac{1}{2} (w-w^*)^T\Sigma(w-w^*)+\dfrac{1}{2}\sigma^2.
\end{align}
Now we show the problem related parameters in Theorem \ref{thm:sgd} can be set as below:
\begin{prop}
	\label{prop:linregression}
	For linear regression, Assumption \ref{aspt:convex} holds with $A=\Sigma, \delta=0, \mathcal{D}=\mathbb{R}^p$.
	When $w_0=0, \mathbb{E} G(w_0)=\frac12 \|w^*\|^2_\Sigma$, the stochastic gradient variance bounds in \eqref{eqn:sgvarianceless} and \eqref{eqn:sgvariance} hold with
	\[
	r^2=2\sigma^2 \text{tr}(\Sigma)+12\text{tr}(\Sigma)\|w^*\|^2_\Sigma,\quad c_r=\frac{6}{\sigma^2}\max\{\|\Sigma\|,1\}.
	\]
\end{prop}
As a consequence, by Proposition \ref{prop:sparse}, Assumption \ref{aspt:sparse} holds if $\|w^*\|^2$ and $\text{tr}(\Sigma)$ are $O(1)$ constants, and the necessary sample size $N(\epsilon)$ in Corollary \ref{cor:selectpara_online} is independent of $p$.
Similarly, by Proposition \ref{prop:spetrum}, Assumption \ref{aspt:trace} holds if $\|w^*\|_{A,S}^2$ and $\text{tr}(\Sigma)$ are $\widetilde{O}(1)$ constants, and the sample size $N(\epsilon)$ depends on $p$ only via a polynomial logarithmic factor.

\subsection{High dimensional data with principle components}
\label{sec:motivate}

The low effective dimension settings in Section \ref{sec:nooverfit} naturally rise in many high dimensional problems.
For example, in image processing or functional data analysis (see e.g. \citealp{RS05, HH07, CH08, FJR15, XY18}), the data are in general assumed to take place in a  Hilbert space $(H, \langle \,\cdot\,,\,\cdot\,\rangle)$ with potentially infinitely many orthonormal basis functions $\{e^j,j=1,2,\ldots\}$. Each data can be written as
\begin{equation}\label{eq:data}
x_i=\sum_{j=1}^\infty a^j_i e^j.
\end{equation}
Suppose $a^j_i$ are independent Gaussian random variables with mean zero and variance $\sigma_j^2$. Note that
$
\mathbb{E} \langle x_i, x_i\rangle=\sum_{j=1}^\infty \sigma_j^2.
$
Therefore, for each data $x_i\in H$, we assume that $\sum_{j=1}^\infty \sigma_j^2<\infty$ so that the norm of the data is bounded, which implicitly requires $\sigma_j$ decaying to zero \citep{HH07}. Given the form of $x_i$ in \eqref{eq:data}, the linear regression model takes the following form,
\begin{equation}
\label{eqn:inf}
y_i=\langle x_i,w^*\rangle+\xi_i,
\end{equation}
where $w^*=\sum_{j=1}^\infty w^{*,j} e^j$. If we assume $w^*\in H$, then $\langle w^*, w^*\rangle=\sum_{j=1}^\infty (w^{*,j})^2<\infty$.

When training this ``infinite dimensional'' linear regression model in \eqref{eqn:inf}, we would need  a finite projection ${\mathcal{P}}_p: H\mapsto \mathbb{R}^p$.   When the basis functions are available, one natural choice of the projection is
\[
{\mathcal{P}}_p x_i={\mathcal{P}}_p\left(\sum_{j=1}^\infty a^j_i e^j\right):=[a^1_i, \ldots a^p_i]^T.
\]
Then the $p$-dimensional linear regression model is formulated as
\begin{equation}
\label{eqn:projp}
y_i=({\mathcal{P}}_p x_i)^T w^*_p+\xi_i^p.
\end{equation}
It is worthwhile noticing that the true infinite dimensional model in \eqref{eqn:inf} is compatible with the finite dimensional model in \eqref{eqn:projp}, in the sense that
\[
w^*_p={\mathcal{P}}_p w^*=[w^{*,1},\ldots, w^{*,p}]^T,\quad \xi_i^p=\xi_i+\sum_{j=p+1}^\infty w^{*,j}a^j_i.
\]
Since $a^j_i$ are independent Gaussian random variables, we have $\xi_i^p\sim \mathcal{N}(0,\sigma_{\xi,p}^2)$ with
\[
\sigma^2_{\xi,p}:=\sigma^2+\sum_{j=p+1}^\infty \sigma_j^2(w^{*,j})^2\leq \sigma^2+\|w^*\|_{\Sigma}^2, \quad \|w^*\|_{\Sigma}^2:=\sum_{j=1}^\infty \sigma_j^2(w^{*,j})^2.
\]
In the finite dimensional model \eqref{eqn:projp}, the data  ${\mathcal{P}}_p x_i$ has the population covariance matrix $\Sigma_p=\text{diag}(\sigma_1^2,\ldots, \sigma_p^2),$ whose trace is bounded by
\[
\text{tr}(\Sigma_p)=\sum_{j=1}^p \sigma_j^2 \leq \sum_{j=1}^\infty \sigma_j^2.
\]
Therefore, by Proposition \ref{prop:linregression}, the problem related parameters in Theorem \ref{thm:sgd} are
\begin{align}
\notag
&A_p=\Sigma_p,\quad\text{with}\quad \text{tr}(A_p)\leq \sum_{j=1}^\infty \sigma_j^2,\quad \|A_p\|=\sigma_1^2,\\
\label{eq:trace_A_p}
&r_p^2=2\sigma^2_{\xi,p}\text{tr}(\Sigma_p)+12\text{tr}(\Sigma_p)\|w_p^*\|^2_{\Sigma_p}\leq 2(\sigma^2+7\|w^*\|^2_\Sigma)\sum_{j=1}^\infty \sigma_j^2,\\
\notag
&  c_{r,p}^2=\frac{6}{\sigma^2_{\xi,p}}\max\{1,\sigma_1^2\}\leq \frac{6}{\sigma^2}\max\{1,\sigma_1^2\}.
\end{align}
Moreover, if we use $w_0=0$, then $\mathbb{E} \|w_0\|^2=0$ and
\[
\mathbb{E} G(w_0)=\frac12\|w^*_p\|^2_{\Sigma_p}\leq \|w^*\|^2_\Sigma.
\]
Note that
\[
\|w^*\|^2_\Sigma=\sum_{j=1}^\infty \sigma_j^2(w^{*,j})^2\leq \|w^*\|_\infty^2\sum_{j=1}^\infty \sigma_j^2,\quad \|w^*\|_\infty:=\max_{1\leq j}|w^{*,j}|.
\]
So as long as $\|w^*\|_\infty$ is finite, the upper bounds above are independent of dimension $p$.

When the true loading parameter $w^*$ is an element of $H$, $\|w^*_p\|^2\leq \langle w^*, w^*\rangle<\infty$. Then we can check that all items of Assumption \ref{aspt:sparse} hold. So by Proposition \ref{prop:sparse}, we know that the generalization error is dimension-independent. Moreover, this does not require any information of the spectrum decay profile.

More generally, we only need that each component of the true loading parameter $w^*$  is bounded, and $w^*$ does not need to be an element of $H$ itself. In particular, we note that
\[
\|w^*_p\|_{\Sigma_p,S}=\max_{1\leq j\leq p} |w^{*,j}| \leq \|w^*\|_\infty.
\]
Therefore, if $\|w^*\|_\infty$ is finite, Assumption \ref{aspt:trace} holds  (but in general Assumption \ref{aspt:sparse} does not). Then by Proposition \ref{prop:spetrum},  the generalization error can be dimension independent when we know the spectrum decay profile.

\begin{figure}[!t]
	\centering
	\begin{subfigure}{.45\textwidth}
		\includegraphics[width=1.1\textwidth]{Sec1-2_alpha1.eps}
		\caption{$w^{*,j}=j^{-1}$, $\sigma^2_j=j^{-2}$}
	\end{subfigure}
	\begin{subfigure}{.45\textwidth}
		\includegraphics[width=1.1\textwidth]{Sec1-2_ind100.eps}
		\caption{$w^{*,j}=j^{-1}$, $\sigma^2_j\equiv 1$}
	\end{subfigure}
	\begin{subfigure}{.45\textwidth}
		\includegraphics[width=1.1\textwidth]{Sec3-2_alpha1.eps}
		\caption{$w^{*,j}\equiv 1$, $\sigma^2_j=j^{-2}$}
	\end{subfigure}
	\begin{subfigure}{.45\textwidth}
		\includegraphics[width=1.1\textwidth]{Sec3-2_ind100.eps}
		\caption{$w^{*,j}\equiv 1$, $\sigma^2_j \equiv 1$}
	\end{subfigure}
	\caption{Generalization error bar plot with high dimensional linear regression for different settings of  $w^*_p$ and $\Sigma_p$.   The $x$-axis is the dimension and $y$-axis is the generalization error. }
	\label{fig:intro}
\end{figure}

As a simple demonstration, we run some simulations of SGD on linear regression model \eqref{eqn:projp} and present them in Figure \ref{fig:intro}. We run SGD on \eqref{eqn:projp} with the sample size $N=500$ and the regularization parameter $\lambda=0.01$. The covariance spectrum of predictors is set to be $\sigma^2_j=j^{-2}$ so that $\text{tr}(A_p)$ in \eqref{eq:trace_A_p} is a constant, and the true parameter is set to be $w^{*,j}=j^{-1}$ for $1 \leq j \leq p$ so that $\|w^*\|_{\Sigma}$ is bounded. The problem dimension ranges from $p=100$ to $p=1000$, which can be larger than the sample size.  We use the final SGD output $w_{500}$ as the estimator and compute the generalization error as in \eqref{eqn:linloss1}. We repeat this experiment $1000$ times and compute the mean and standard deviation. We plot the error bar plot in  the upper left panel of Figure \ref{fig:intro}. As one can see, the generalization error does not increase as the dimension increases, even when $p \gg N$. As a comparison experiment, we run simulations with the same settings except for $\sigma^2_j\equiv 1$. We plot the generalization error in the upper right panel of Figure \ref{fig:intro}, which clearly shows the overfitting phenomenon, even when the dimension is in a lower range.

The similar story repeats when the true parameter $w^{*,j}\equiv 1$ (i.e., the case when $\|w^*\|_{\infty}$ is bounded), where the plots are given by the lower panels in Figure \ref{fig:intro}. As one can see, the generalization error with the decaying spectrum still remains stable against the increase of dimension, and it does not change much from the previous setting where the components of $w^*$ are decaying. Meanwhile, overfitting with constant spectrum (i.e., $\sigma^2_j\equiv 1$) becomes stronger. This simple illustrative example justifies that the low effective dimension helps to address the overfitting issue, even when the dimension $p$ is much larger than the sample size $N$.

\subsection{Overfitting with redundant features}
Another interesting setting of overparameterization is to consider adding redundant predictors to an existing model. In this scenario, the  true model is low dimensional with the true parameter $w^*\in \mathbb{R}^{d}$. Suppose  we do not know the true model and collect additional features $z \in \mathbb{R}^{p-d}$, so that the overparameterized linear model is written as
\begin{equation}
\label{eqn:redund}
y_i=x_i^Tw^*+z_i^T u^*+\xi_i,
\end{equation}
where $w^* \in \mathbb{R}^d$, $u^*=0$, and  $[x_i;z_i]$ is jointly Gaussian with mean zero and covariance
\[
\Sigma_p=\begin{bmatrix} \Sigma_x & B\\ B^T  &\Sigma_z \end{bmatrix}.
\]
We assume that $\|\Sigma_z\|\leq \|\Sigma_x\|$ for the ease of discussion.
Then, $\Sigma_p$ being PSD implies that $\|B\|\leq \|\Sigma_x\|$. Since we do not impose any restriction on $B$ other than $\Sigma_p$ being PSD,   our setting allows the possibility that some components of $z_i$ to be highly correlated or even identical with the ones of $x_i$. This, in general, leads to highly singular design matrices and unstable offline learning results.

We apply Proposition \ref{prop:linregression} and find $A_p=\Sigma_p$. By triangular inequality, for any vectors $x$ and $z$,
\[
\|\Sigma_p[x;z]\|=\|[\Sigma_x x+Bz; B^Tx+\Sigma_z z]\|\leq 2\|\Sigma_x\|\|[x;z]\|\Rightarrow \|\Sigma_p\|\leq 2\|\Sigma_x\|.
\]
For simplicity, we initialize with $[w_0;u_0]=0$, so
\[
\mathbb{E} G(w_0,u_0)=\frac12\|w_0-w^*\|^2_{\Sigma_x}+\frac12\|u_0\|_{\Sigma_z}^2=\frac12\|w^*\|^2_{\Sigma_x}.
\]
Moreover, we have
\[
c_{r,p}=\frac{6}{\sigma^2}\max\{\|\Sigma_p\|,1\}\leq \frac{6}{\sigma^2}\max\{2\|\Sigma_x\|,1\},
\]
and
\[
\|[w^*,u^*]\|_{\Sigma_p,S}=\|w^*\|_\infty,\quad \|[w^*,u^*]\|^2=\|w^*\|^2.
\]
These upper bounds are all independent of $p$, or the choice of $\Sigma_z$ and $B$.

Meanwhile,
\begin{equation}\label{eq:r_p}
r^2_p=2(\sigma^2+6\|w^*\|^2_{\Sigma_x}) (\text{tr}(\Sigma_x)+ \text{tr}(\Sigma_z)),\quad \text{tr}(A_p)=\text{tr}(\Sigma_x)+\text{tr}(\Sigma_z).
\end{equation}
Given these simple calculation, we find that the only problem related parameters that depend on $z$ are $r^2_p$ and $\text{tr}(A_p)$ in \eqref{eq:r_p} through $\text{tr}(\Sigma_z)$.
Therefore, our theory indicates that there is a simple dichotomy on whether  the model \eqref{eqn:redund} will overfit.

If $\text{tr}(\Sigma_z)$ is bounded by a constant independent of $p$,  Proposition \ref{prop:sparse} applies, which indicates that the generalization error is also independent of the ambient dimension $p$. This can happen if we select data features in $z$ as PCA components. For example, suppose that the redundant data is in the form of $\sum_{j=1}^\infty a_{i}^j e^j$ as in the setting of  \eqref{eq:data}, and we collect the $p-d$ dimensional principle components as  $z_i=[a_i^1,\ldots, a_i^{p-d}]^T$. Then $\text{tr}(\Sigma_z)=\sum_{j=1}^{p-d}\sigma_j^2<\sum_{j=1}^\infty \sigma_j^2$, which is independent of $p$.

If $\text{tr}(\Sigma_z)$ grows with $p$,  model \eqref{eqn:redund} may overfit. For simplicity, we consider a special case where $\Sigma_z=I_{p-d}, B=0$. In other words, the redundant features are independent with each other and the features of $x$. Then our derivation shows that $r^2_p=O(p)$. This indicates that the learning results may overfit.

To demonstrate this dichotomy, we simulate the SGD learning results and present their generalization error in Figure \ref{fig:redun}. In particular, we set $d=5$ with true parameter $w^*=[1,1,1,1,1], \Sigma_x=I_5, \sigma^2=1$. We let $B=0$ and choose first that $\Sigma_z$ to be diagonal with decaying entries $\frac{1}{j^2}$. We run SGD with 500 iterations and compute the generalization error of the final iterate. We repeat this 1000 times and plot the  error bar plot in the left panel of Figure \ref{fig:redun}. As we can see, the generalization error is stable against the increase of the dimension $p$. In comparison, if we use $\Sigma_z=I_{p-d}$, the learning results overfit, as we can see from the right panel of Figure \ref{fig:redun}.

\begin{figure}[!t]
	\centering
	\begin{subfigure}[t]{.46\textwidth}
		\includegraphics[width=1.1\textwidth]{Sec3-4_alpha1.eps}
		\caption{$\Sigma_z$ is a diagonal matrix with decaying entry $(\Sigma_{z})_{jj}=\frac{1}{j^2}$.}
	\end{subfigure}
	\begin{subfigure}[t]{.46\textwidth}
		\includegraphics[width=1.1\textwidth]{Sec3-4_ind100.eps}
		\caption{$\Sigma_z=I_{p-d}$.}
	\end{subfigure}
	\caption{Generalization error bar plot with high dimensional redundant features for two different cases of $\Sigma_z$. The $x$-axis is the dimension $p$ and $y$-axis is the generalization error. }
	\label{fig:redun}
\end{figure}

\section{Overparameterization for Nonlinear and Non-convex Models}
\label{sec:non_linear}

In this section, we apply our main theorem and corollaries in Section \ref{sec:nooverfit} to several important nonlinear and non-convex statistical problems, such as logistic regression, M-estimator with Tukey's biweight loss function, and two-layer neural networks.

\subsection{Logistic regression}
We consider the logistic regression for binary classification with $N$ \emph{i.i.d.} data $\zeta_i=(x_i,y_i)$. The binary response $y_i$ takes values within $\{ -1, 1\}$ with probability
\begin{align*}
\mathbf{P}(y_i=y|x_i) = \dfrac{1}{1+\exp(-yx_i^{T}w^*)},\quad y=\pm 1,
\end{align*}
where  $w^{*} \in \mathbb{R}^p$ is the true parameter to be estimated. We assume the predictors $x_i$ are \emph{i.i.d.} with  $\mathbb{E}x_ix_i^T = \Sigma$.
For each data, we adopt the negative log-likelihood as the loss function
\begin{align*}
f(w, \zeta_i):=\log(1+\exp(-y_ix_i^{T}w)),
\end{align*}
and the corresponding population loss is given by
\begin{align*}
F(w) = \mathbb{E}f(w, \zeta) &= \mathbb{E}\log(1+\exp(-yx^{T}w)).
\end{align*}

The problem related parameters in Theorem \ref{thm:sgd} can be set by the following proposition.
\begin{prop}
	\label{prop:logit}
	For logistic regression, Assumption \ref{aspt:convex} holds with $A=\Sigma, \delta=0, \mathcal{D}=\mathbb{R}^p$.
	When $w_0=0, \mathbb{E} G(w_0)=\log 2=O(1)$, the stochastic gradient variance bound in \eqref{eqn:sgvariance} holds with
	\[
	r^2= \text{tr}(\Sigma),\quad c_r=0.
	\]
\end{prop}

As a consequence, by Proposition \ref{prop:sparse}, Assumption \ref{aspt:sparse} holds if $\|w^*\|^2$ and $\text{tr}(\Sigma)$ are $O(1)$ constants, and the sample size $N(\epsilon)$ in Corollary \ref{cor:selectpara_online} is independent of $p$.
Similarly, by Proposition \ref{prop:spetrum}, Assumption \ref{aspt:trace} holds if $\|w^*\|_{\Sigma,S}^2$ and $\text{tr}(\Sigma)$ are $\widetilde{O}(1)$ constants, and the sample size $N(\epsilon)$ depends on $p$ only via a poly-logarithmic factor.

\subsection{$M$-estimator with Tukey's biweight loss function}

In this non-convex example, we assume that the data $\zeta_i=(x_i, y_i)$ are generated from a linear model
\begin{equation}\label{eq:tukey_model}
y_i=x_i^T w^*+\xi_i.
\end{equation}
We assume $x_i\sim \mathcal{N}(0,\Sigma)$, and $\xi_i$ are i.i.d. mean-zero noises with finite fourth moment.  We adopt the \emph{non-convex} Tukey's biweight loss function as follows for the purpose of robust estimation
\[
\rho(u)=\begin{cases}
\frac{c^2}6[1-(1-(u/c)^2)^3] \quad &\text{if } \ |u|\leq c;\\
\frac{c^2}6\quad \quad&\text{if }\ |u|>c. \\
\end{cases}
\]
Then the individual data loss function  and the population loss are given by,
\[
f(w,\zeta)=\rho(x^Tw-y )=\rho(x^T (w-w^*)-\xi),\quad  F(w)=\mathbb{E}\rho(x^T (w-w^*)-\xi).
\]
\begin{prop}
	\label{prop:Mest}
	For the $M$-estimator with Tukey's biweight loss in \eqref{eq:tukey_model},  the model true parameter $w^*$ is a local minimum if and only if
	\[
	c_0=\mathbb{E} [(1-(\xi/c)^2)(1-5(\xi/c)^2)1_{|\xi|\leq c}] >0.
	\]
	In that case,  Assumption \ref{aspt:convex} holds with any $\delta\geq 0$, $A=\Sigma$ and
	\[
	\mathcal{D}=\{w: \|w-w^*\|_\Sigma \leq \tfrac{c_0+\delta}{16}\}.
	\]
	Moreover, the stochastic gradient variance bound in \eqref{eqn:sgvariance} holds with
	\[
	r^2= \text{tr}(\Sigma),\quad c_r=0.
	\]
\end{prop}

Since $G(w_0)\leq \max_u \rho(u)=\frac{c^2}{6}$, by Proposition \ref{prop:sparse}, Assumption \ref{aspt:sparse} holds if $\|w^*\|^2, \|w_0\|^2$ and $\text{tr}(\Sigma)$ are $O(1)$ constants, and the sample size $N(\epsilon)$ in Corollary \ref{cor:selectpara_online} is independent of $p$.
Similarly, by Proposition \ref{prop:spetrum}, Assumption \ref{aspt:trace} holds if $\|w_0\|_\infty,\|w^*\|_{\Sigma,S}^2$ and $\text{tr}(\Sigma)$ are $\widetilde{O}(1)$ constants, and the sample size $N(\epsilon)$ depends on $p$ only via a polynomial logarithmic factor.

\subsection{Two-layer neural network}
\label{sec:NN}

In this example, we consider applying our result to two-layer neural networks (NN).
We assume that every data point $\zeta = (x, y)$ consists of a  $p$-dimensional predictor $x \sim \mathcal{N}(0,\Sigma)$ and  a univariate response $y \in \mathbb{R}$. We assume that the response is generated by
\[
y=g(w,x)+\xi, \quad \mathbb{E}\xi=0, \quad \mathbb{E}\xi^2=\sigma^2_0.
\]
The function $g$ takes the form of a two-layer NN:
\begin{equation}\label{eqn:g2NN}
g(w,x)=c^T\psi(b x+a)=\sum_{i=1}^k c_i \psi(b_i^Tx+a_i).
\end{equation}
In \eqref{eqn:g2NN}, $a$ and $c$ are $k$-dimensional vectors with $a_i$ and $c_i$ being their components. The notation $b$ is a $p$ by $k$ matrix, and $b_i$ denotes the $i$-th column of $b$ with  $i=1,\ldots, k$. We impose no restriction on $k$ and it can depend on $p$ in general.  We denote all the parameters by $w=[a;b_1,\ldots, b_k;c]\in \mathbb{R}^{(p+2)k}$.
In \eqref{eqn:g2NN}, $\psi$ denotes the activation function. Popular choices of $\psi$ include the rectified linear unit (ReLu), sigmoid function, and the hyperbolic tangent. Here, we do not require $\psi$ to take a specific form but only satisfy certain regularity assumptions for some constant $C>0$,
\begin{equation}\label{eqn:psi}
\psi(0)=0,\quad |\dot{\psi}(x)|\leq C,\quad |\ddot{\psi}(x)|\leq C.
\end{equation}
It is easy to verify that hyperbolic tangent satisfies these requirements, and the sigmoid also satisfies these if we shift its center to zero. The condition $\psi(0)=0$ is mainly for the ease of technical derivations. Although ReLu does not have continuous derivatives, one can find a smooth approximation to meet these requirements.

Since we consider the regression problem, the squared loss function is given by
\[
f(w,\zeta)=(y-g(w,x))^2=(g(w^*,x)+\xi -g(w,x))^2.
\]
We also introduce the following $(p+2)k$ by $(p+2)k$ block-diagonal matrix
\[
\Sigma^\star=\text{diag}\{I_k, \Sigma,\Sigma\ldots, \Sigma, I_k\}.
\]
This matrix introduces a high dimensional norm
\[
\|w\|_{\Sigma^\star}^2=w^T\Sigma^\star w=\|a\|^2+\sum_{i=1}^k \|b_i\|^2_{\Sigma}+\|c\|^2.
\]
Recall that $b_i$ is of dimension $p$, its contribution to $\|w\|_{\Sigma^\star}^2$ is  $\|b_i\|^2_\Sigma$. By Proposition \ref{prop:spetrum}, $\|b_i\|^2_\Sigma\leq \text{tr}(\Sigma)\|b_i\|^2_{\Sigma,S}$, which can be independent  of $p$ under suitable conditions.

We are ready to show that  the two-layer NN will not overfit in some overparameterized settings.

\begin{prop}
	\label{prop:2LNN}
	Assume the activation function satisfies the condition in \eqref{eqn:psi}.
	With the two-layer NN defined in \eqref{eqn:g2NN},  Assumption \ref{aspt:convex} holds for any $\delta \in (0, 1/4]$ with
	\[
	A=C_0(w^*)\Sigma^\star,\quad \mathcal{D}=\{w: \|w-w^*\|_{\Sigma^\star} \leq \delta C_1(w^*)\|w^*\|_{\Sigma^\star}\}.
	\]
	For any $w_0\in \mathcal{D}, G(w_0)\leq C_2(w^*)\|w^*\|_{\Sigma^\star}^4$, the stochastic gradient variance bound in \eqref{eqn:sgvariance} holds with
	\[
	r^2= C_3(w^*), c_r=0.
	\]
	The exact values of the problem related parameters are given by
	\begin{align*}
	&C_0(w^*)=7C^2\|w^*\|^2_{\Sigma^\star}, \quad
	C_1(w^*)=\frac{2}{9\sqrt{2}(2\|w^*\|_{\Sigma^\star}+1)}, \quad C_2(w^*)=C^2\|w^*\|^4_{\Sigma^\star},\\
	&C_3(w^*)=8\sqrt{3}(1+\text{tr}(\Sigma))C^2 \|w^*\|^2_{\Sigma^\star}\big(C^2 \|w^*\|_{\Sigma^\star}^4+\sigma_0^2\big).
	\end{align*}
\end{prop}
As a consequence, by Proposition \ref{prop:sparse}, Assumption \ref{aspt:sparse} holds if
\begin{equation}
\label{tmp:cond1}
\max\left\{\|a^*\|^2+\sum_{i=1}^k\|b^*_i\|^2+\|c^*\|^2,\text{tr}(\Sigma),\|w_0\|_\infty\right\}=O(1),
\end{equation}
and the sample size $N(\epsilon)$ is independent of $p$. Similarly, by Proposition \ref{prop:spetrum}, Assumption \ref{aspt:trace} holds if
\begin{equation}
\label{tmp:cond2}
\max\left\{k, \text{tr}(\Sigma),\|w_0\|_\infty, |a_i|, |c_i|, |v_j^Tb_i|,  i=1,\ldots,k,j=1,\ldots,p\right\}=\widetilde{O}(1),
\end{equation}
where $v_j$ are the eigenvectors of $\Sigma$. Then the sample size $N(\epsilon)$ depends on $p$ only via a polynomial logarithmic factor.

It is worthwhile mentioning that a similar version of  Condition \eqref{tmp:cond1} can also be found in \cite{NLBLS:19}. In particular, \cite{NLBLS:19} assumed $\|c^*\|^2,\sum_{i=1}^k \|b^*_i\|^2$ to be $O(1)$ while the parameter $a$ is set to be $0$. There is no variance assumption of $x_i$ in \cite{NLBLS:19}, but it is assumed that $\mathbb{E}\|x_i\|^2$ is $O(1)$, which is equivalent to requesting $\text{tr}(\Sigma)=O(1)$ in our setting.

When the width of the hidden layer $k$ is a fixed constant, the second condition \eqref{tmp:cond2} is in general less restrictive than the first one \eqref{tmp:cond1}, since it allows $\|b^*_i\|$ to grow with $p$.  When $k$ grows with $p$, only the first condition is applicable, and it requires that $\|a^*\|^2+\sum_{i=1}^k\|b^*_i\|^2+\|c^*\|^2$ is bounded by $O(1)$. In other words, we need either $k=O(1)$ or the true parameters to be bounded by $O(1)$ to prevent overfitting. This can also be understood intuitively. Note that the  output  of the two-layer NN in  \eqref{eqn:g2NN} is a sum of $k$ objects. Therefore, if $k$ grows with $p$, the output of \eqref{eqn:g2NN}  will diverge, which contradicts the common assumption that $g$ is bounded (see, e.g., \citealp{LL2018, NLBLS:19, ALL:19}).  Our result is consistent with the results in  \cite{ALL:19}, in the sense that \cite{ALL:19} also showed that the sample size needs to grow with $k$. It is also possible to rescale $g$ by multiplying \eqref{eqn:g2NN} with a factor $\frac{1}{k}$ or $\frac{1}{\sqrt{k}}$, as done by \cite{ADHLW:19},  so that the generalization error is independent of the parameter $k$.
\section{Conclusions and Future Works}
\label{sec:conclusion}
One classical canon of statistics is that high dimensional models are prone to overfitting when the data sample size is not sufficiently large.
However, many existing models, such as neural networks (NN), exhibit stable generalization error despite being overparameterized.
This paper developed an analysis framework of the generalization error for high dimensional regularized online learning.
The error bound can be  interpreted as a bias-variance tradeoff through a simplified stochastic approximation.
This result indicates that overparameterization does not lead to overfitting if the model has a low effective dimension.
We demonstrated how to apply this framework on various models such as linear regression, logistic regression, $M$-estimator with Tukey's biweight loss, and two-layer NN.

There are a few future directions. First,  the generalization bound in Theorem \ref{thm:sgd} only applies when the SGD iterates stay in a local region $\mathcal{D}$ near the true parameter $w^*$. Although it is a common assumption when analyzing non-convex models,  this assumption might  be difficult to check in practice.
To address this challenge, a simple data splitting can serve as a remedy. In practice, we may split the data into two parts and run SGD through the first half.  If $w_{N/2}$ gives us some rough ideas on how to construct $\mathcal{D}$, we can use $w_{N/2}$ as an  initialization and run SGD on the second half of the data.
In the process, we can check whether the iterates stay in $\mathcal{D}$, and then Theorem \ref{thm:sgd} provides us an upper bound for the generalization error of $w_N$.  Of course, it would be an interesting future work on how to construct $\mathcal{D}$ based on the SGD solution from the first half of the data.

Second, our framework indicates that the ambient model dimension itself may not be a good indicator of model complexity,  especially in  overparameterized settings.
The quantity that characterizes the data variability  may lead to new information criterion for model selection in the overparameterized setting. Such results may extend the classical criteria such as the AIC and BIC.

\blue{ Last but not least, regularization and overparameterization are good tools to handle misspecified models. \citet{Hastie19}
has discussed this issue for linear regression problems. How to extend our results to nonlinear misspecified models will be very interesting.  }

\section*{Acknowledgement}
Xi Chen would like to thank the support from NSF via the grant IIS-1845444.
Qiang Liu would like to thank the support from Singapore MOE via the grant R-146-000-258-114.
Xin T. Tong would like to thank the support from Singapore MOE via the grant R-146-000-292-114.
The authors also thank the suggestions made by the editor and anonymous reviewers.

\newpage


text:
I will never forget this day
Our world is changing essay writer
High horse courting essay
James joyces araby summary of an
The story ends with Little Chandler attempting, and failing, to calm his son down when he was crying, which makes his wife angry. Another describes Joyce, lying on the deck of a ship, hearing the voices of the choirboys from the nearby cathedral of Our Lady.
Nonetheless, the notion of the epiphany remains slightly obscure and even somewhat confusing. With shame and anger rising within him, he is alone in Araby.
I wanted to zoom out, however, and see how Joyce used the location changes—the physical activity of James joyces araby summary of an story—to interact with the stream of conscious narrative in which Joyce writes. His feelings affects his view towards the girl that she loves.
There are several epiphanies that centre on social visits to the home of the MP David Sheehy. Freemason an international secret society having as its principles brotherliness, charity, and mutual aid.
I think that this moment occurs because, after his efforts to escape his life by his aimless wandering and drinking, he ultimately realizes that he is trapped in his life.
Then the writer puts roadblocks in the way of the boy and the reader: He goes all the way to the Araby bazaar to realize that the trip was pointless. Flashes of Unintellectual Light in. The Epiphany as the Evanescent Moment: One aspect of the story that the maps contribute to is the vast amount of street covered by Corley and Lenehan on their walk.
Because his uncle, who holds the money that will make the excursion possible, has been out drinking. He is so put off by all his disappointments and her tone of voice, however, that he at once decides not to buy anything.
If you would like to authenticate using a different subscribed institution that supports Shibboleth authentication or have your own login and password to Project MUSE, click 'Authenticate'. He was awakened to the fact that he was just dreaming that girl and that fact causes his anger. Free essay on Analysis of Araby by James Joyce available totally free at echeat.
This method hopefully led to a greater authenticity and understanding of the works. This actually lead me to discover how to interpret the text via mapping by allowing me to formulate what I will be referring to as active and passive traveling.
His path is also small compared to the journey that he takes in his mind. Joyce used the idea of the dark by telling us how different life does the boy has. They travel around the same part of Dublin again and again, which represents their circuitous journey of beguiling a girl and getting her to steal for them until they find a new girl.
The extent to which this was consciously recognized in Dublin at the time is also worth noting. Learn exactly what happened in this chapter, scene, or section of Dubliners and what it means. Gallaher refers to Paris and London as places full of excitement and opportunity not available at home in Dublin.
At the end of "Araby," the narrator has an epiphany when he decides to give up on his love for Mangan's sister. The only sound is "the fall of the coins" as men count their money. Even in the bustle of the weekly grocery shopping, he carries with him a feeling about her that amounts to something like mystical rapture.
Additionally, most of the places mentioned and all of the street names actually exist in the city of Dublin and can be easily mapped. In The Orchard, the girl chose to lie to the boy but at the end she was still hurt. He loved her without any hesitations.
The vivid imagery in Araby by James Joyce is used to express the narrators romantic feelings and situations throughout the story. Without the help of the third boy, Leo, the two decided not to engaged the hecklers. She mentions that he travels as far as Thomas Street in order to find work.
In fact, there are five entire paragraphs of exposition that occur during the drive of about two miles. Kerman works in a little office on Crowe Street and Mr. Hesitantly, he approaches one of the few stalls still open, one selling pottery. When he is home and fails to console his child, it shows how he is not in control of his life anymore, how his choice to stay in Dublin and live a boring, generic life has taken away his control to travel and experience the world like Gallaher has.
The map allows for interpretation of that journey as compared to his shorter walking path. This added reality, though the stories and characters themselves are fictional, provides a connection to the story.
The Irish Times, for example, published lengthy preview articles about each bazaar during the weeks before they opened, and almost daily reports on the proceedings after they had been launched. The one by the English Franciscan Friar Pacificus Baker is noted for its lush, pious language and could have influenced the boy's couching his sexual feelings for the girl in pious images.
The significance of the number of times Paris and London are mentioned mirrors the significance that the two cities hold in the mind of the main character, Little Chandler.Dubliners: Theme Analysis, Free Study Guides and book notes including comprehensive chapter analysis, complete summary analysis, author biography information, character profiles, theme analysis, metaphor analysis, and top ten quotes on classic literature.
librariavagalume.com In James Joyces Dubliners the use of irony and sensory disconnect are what structure the recurring themes of the stories. The themes include entrapment, with escaping routine life for its horrors, misery, and agony. The stories Eveline, Araby, A. A summary of "Araby" in James Joyce's Dubliners.
Learn exactly what happened in this chapter, scene, or section of Dubliners and what it means. Perfect for acing essays, tests, and quizzes, as well as for writing lesson plans. Dubliners by James Joyce is a good reading choice for advanced level 12th-grade students. As his first published work of ("Araby" and "The Dead"), because the reader's revelation about the character's condition satisfies Joyce's purpose in writing the story.
"Araby" contains many themes and traits common to Joyce in general and Dubliners in particular. As with many of the stories in the collection, "Araby" involves a character going on a journey, the end result of which is fruitless, and ends with the character going back to where he came from.
In James Joyce's story "Araby", what does the fence symbolize? Update Cancel. ad by Hubble. What is the summary of the short story "Araby?" What is Araby really about?
How does James Joyce's "Araby" handle the topic of childhood? Are we all that little boy in James Joyce's Araby? Expectedly hoping to get something from the Bazaar only to be.
Business plan for planet fitness
Process essay on how to make pasta
Bbc world business report 2015 chrysler
Thomas hardy country complex and pessimistic fatalism english literature essay
Mixtures and solutions
Explain the importance of building physical activity into everyday routines
Philosophie essay wettbewerb sh
Study essay test
Research papers on spanning tree
Riders to the sea play analysis

redpajama_set_name: RedPajamaCommonCrawl


It only seems like yesterday that schools shut for the Easter break, although many schools all over the country are now at the end of another half term break.
If your little ones have just spent the week off school, and you've done your best to keep them entertained with a variety of activities, the chances are that your home has been left in a bit of a state.
It doesn't take much for uncleanliness and untidiness to build up when the kids are at home all day every day for a week, and finding the time to get the home looking back to its best can feel near on impossible- especially when you're also trying to juggle a busy career.
Cleaning your home after the half term havoc can involve a number of very time-consuming tasks- such as wiping, dusting, vacuuming and trying to get pesky stains out of carpets and upholstery- and the best way to deal with these tasks is to let a professional take care of them.
A house cleaning professional will arrive at your home more than prepared to tackle the aftermath of the half term holidays- and you won't even have to lift so much as a duster yourself.


text:
101 Marvel Characters
101 Marvel Character Comic Book Debuts
By: AAAStateofPlay.com
Marvel Comics got its start way back in 1939, but at the time it was known as Timely Comics. In fact, it wasn't known as Marvel Comics until 1961 which also marked the beginning of one of the company's most prolific decades. The era saw the launch of some of their most iconic characters including the Fantastic Four, the X-Men, and several characters that have been dominating the box office over the past several years such as Spider-Man, Iron Man, Doctor Strange, The Black Panther, Captain Marvel and more.
The minds behind these characters and storylines are many but Jack Kirby, Steve Ditko, and of course: Stan Lee, are undeniably the most influential. Since Marvel's inception, Stan Lee and others have developed over 8,000 characters. This chart from AAAStateofPlay.com includes 101 characters, heroes, villains, and antiheroes alike in an illustrated timeline. Starting in 1939, this timeline includes Marvel's first hero, Namor the Sub-Mariner, historical heroes such as Captain America, bizarre oddities such as Armless Tiger Man, "Defenders" of New York City such as Daredevil and Luke Cage, ruthless "heroes" like The Punisher and Wolverine, icons of the 1990s such as Gambit, Deadpool, and Carnage, and even more recent additions like Knull and Ironheart.


text:
How These 5 Stay-at-Home Moms Stay Ahead
It is a truth well acknowledged that stay-at-home moms have their work cut out for them. Stay at home mothers work really hard in maintaining their house, babies, and their own lives simultaneously, which together make for a very demanding job in itself. Amidst all of that, it is very hard for them to consider their own health and fitness and work towards those. But it is not completely impossible. Social media is full of mothers who make it a point to balance their work, health and baby-care. So, in case you are a mother who is looking for inspiration, here are five stay-at-home moms who you should follow to get regular tips and updates on how they continue to stay fit despite being stay at home moms:
1. Anna Strode
A post shared by Anna Strode (@bubs2bikinis) on Aug 21, 2018 at 1:45pm PDT
This stay at home mom of two boys and a girl became quite an Instagram sensation. She worked hard to get fit and shares with other moms out there what she does via her posts. She makes it clear that a mom can work out with your toddler(s) straddling around. She claims that she has a very easy routine that she follows daily and keeps herself fit. She jogs for around 20 minutes does exercise for 30 mins daily and that's it. What exercises? She does cardio sessions and resistance workouts. You can go and check her account on Instagram @bubs2bikinis where you can check out her posts and get even more inspired.
2. Poppy Montgomery
A post shared by Poppy Montgomery (@therealpoppymontgomery) on Aug 9, 2018 at 9:06am PDT
You may know her from the TV series Without a Trace after which, she quit acting to take care of her one-year-old kid. Poppy as an actress as well as a stay-at-home mom always maintained her fitness. She says that having a sound body is the first step of having a sound mind. While she got back to her acting chops, she quit again and became a full-time stay-at-home mother and still maintains her fitness. She squeezes in her workout routine in midst of handling her kids four times a day. Her routine includes a mix of strength training, yoga and Pilates which she does for about an hour, four days a week.
3. Rhea Durham
Image source: Kevin Mazur/WireImage
The wife of Mark Wahlberg, Rhea quit her modelling career to stay home and take care of their four kids. She was always committed to being a stay-at-home mom and still is and doing a tremendous job at it. With a supremely fit husband like Mark, you would expect her to be fit. She believes that Mark and her both know the importance of staying fit. They both have different routines with Mark hitting the gym at 4 AM every morning but Rhea has a more practical approach for herself. She trains with her trainer Gunnar Peterson hits the gym whenever she gets some time.
4. Candace Cameron Bure
A post shared by Candace Cameron Bure (@candacecbure) on Aug 1, 2018 at 6:41pm PDT
This woman quit her acting career to focus on seeing her children grow. She confessed that it was a very hard decision to make. But what has stayed constant is her health. She has been in a top-notch shape since she quit acting. According to her, it does require a lot of work. Primarily, she is on a vegan diet and tries to maintain that diet to its core. Other than that, she does cardio, high-intensity interval training (HIIT) and resistance training five days a week with two rest days.
5. Julia Sweeney
She left her career in Hollywood behind to be a full-time stay-at-home mom. She beat cancer and got back to her life as it was nothing. Now 57, she has been a big inspiration to all stay-at-home moms by sharing her views on what counts as fit. She believes that it is okay to have a broader figure as long as you feel fit. She maintains a healthy diet and keeps her body healthy by doing daily activities like taking long, refreshing walks.
by Staff Writer · Published March 27, 2019
Top 10 Best Mommy and Me Android Apps
by Staff Writer · Published May 4, 2018 · Last modified April 18, 2019
19 Must-Have Baby Gadgets for Parenting in 2019
by Staff Writer · Published March 4, 2019 · Last modified March 27, 2019
Next story 5 Easy Workout Routines Busy Moms Can Do in 5 Minutes
Previous story 10 Must Have Workout Clothes for Stylish Moms


Eagan High School theater kicks off a new year with the delightfully humorous fall play, One Man Two Guvnors. Set in the British seaside town of Brighton, charming but cunning Francis is hired as a bodyguard for Roscoe Crabbe, a small-time hood from the East side of London. Francis also takes another job working for Stanley, and has to maneuver his way through having two jobs without his guvnors finding out.
Senior lead Grant Davis plays the role of Francis, a hungry, clumsy and somewhat dumb man. He works for two separate people when he is not supposed to. "It's been challenging not laughing on stage. It's a really genuinely funny show, all my castmates are really hilarious," Davis said.
Directing also poses all sorts of obstacles in bringing the show together. "The greatest challenge for doing comedy, especially a really physical comedy, is it's all about the timing and the execution of the physical comedy. We have a guy falling into the pit, it's a delicate balance, if the audience is worried they won't laugh," Director Ms. Owzarek said.
One Man Two Guvnors will be shown October 7, October 11, October 12, and October 13, all at 7:00 p.m. Tickets can be purchased on the Eagan High School website and before each performance for only $5.


Impetux has been awarded AGAIN with the Innovative SME seal. This certification is awarded by the Spanish Ministry of Science, Innovation and Universities in recognition of the investment done in research. We really have an innovative soul!