\begin{document}

\title{An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Bias}

 \author{
Lu Yu\thanks{
Department of Statistical Sciences at
 the University of Toronto, and Vector Institute~~\texttt{luyu@utstat.toronto.edu}
 }~~~~
Krishnakumar Balasubramanian\thanks{
Department of Statistics, University of California, Davis~~\texttt{kbala@ucdavis.edu}
 }~~~~
 Stanislav Volgushev\thanks{
Department of Statistical Sciences at
 the University of Toronto~~\texttt{stanislav.volgushev@utoronto.ca}
 }~~~~
 Murat A. Erdogdu\thanks{
  Department of Computer Science and Department of Statistical Sciences at
   the University of Toronto, and Vector Institute~~\texttt{erdogdu@cs.toronto.edu}
 }
}

\maketitle

\begin{abstract}
 Structured non-convex learning problems, for which critical points have favorable statistical properties, arise frequently in statistical machine learning. Algorithmic convergence and statistical estimation rates are well-understood for such problems. However, quantifying the uncertainty associated with the underlying training algorithm is not well-studied in the non-convex setting. In order to address this short-coming, in this work, we establish an asymptotic normality result for the constant step size stochastic gradient descent (SGD)  algorithm---a widely used algorithm in practice. Specifically, based on the relationship between SGD and Markov Chains~\cite{dieuleveut2017}, we show that the average of SGD iterates is asymptotically normally distributed around the expected value of their unique invariant distribution, as long as the non-convex and non-smooth objective function satisfies a dissipativity property. We also characterize the bias between this expected value and the critical points of the objective function under various local regularity conditions. Together, the above two results could be leveraged to construct confidence intervals for non-convex problems that are trained using the SGD algorithm.
 \end{abstract}


\input{Sections/intro}
\input{Sections/mainresults_clt}
\input{Sections/mainresults_bias}
\input{Sections/examples}
\input{Sections/discussion}


\section*{Acknowledgements}
MAE is partially funded by NSERC Grant [2019-06167], Connaught New Researcher Award, CIFAR AI Chairs program, and CIFAR AI Catalyst grant. KB is partially supported by a seed grant from the Center for Data Science and Artificial Intelligence Research, UC Davis. SV is partially supported by a discovery grant from NSERC of Canada and a Connaught New Researcher Award. 
{The authors thank Yichen Zhang for helpful comments on an earlier version of this manuscript.}


\bibliographystyle{amsalpha}
\bibliography{./bib}

\newpage
\input{Sections/proofs}

\end{document}
{"config": "arxiv", "file": "2006.07904/main.tex"}