\section{Discussions}\label{sec:discussion}


By leveraging the connection between constant step size SGD and Markov chains~\cite{dieuleveut2017}, we provided theoretical results characterizing the bias and the fluctuations of constant step size SGD for non-convex and non-smooth optimization which arises frequently in modern statistical learning. 

\vspace{0.1in}
\noindent\textbf{Estimating the Asymptotic Variance:} As discussed in Section~\ref{sec:cltheory}, in order for using the established CLT to compute confidence intervals in practice, the population expectation $\sdist(\phi)$ and asymptotic variance $\sigma^2_{\sdist}(\phi)$ have to be estimated. We suggest the following three ways to do so:

\begin{itemize}
	\item Estimate them based on sample average of a single trajectory of SGD iterates, i.e., the mean $\sdist(\phi)$ is estimated as $n^{-1}\sum_{k=0}^{n-1}\phi\big(\iter_{k}\big)$ and the variance $\sigma^2_{\sdist}(\phi)$ by adopting the online approach of~\cite{zhu2020fully} to the constant step size setting.
	\item First run $N$ parallel SGD trajectories and compute the average of each trajectory, to obtain $N$ independent observations from the stationary distribution $\pi_\eta$. Next, use the $N$ observations to compute the sample mean and the sample variance estimators for $\sdist(\phi)$ and $\sigma^2_{\sdist}(\phi)$. 
	\item Leverage the online bootstrap and variance estimation approaches proposed in~\cite{fang2018online, su2018statistical,chen2020statistical} for the constant step size SGD setting in order to obtain estimates for $\sdist(\phi)$ and $\sigma^2_{\sdist}(\phi)$.  
\end{itemize}
A theoretical investigation on the relative merits of the above approaches is left as future work.


\iffalse
We can construct confidence intervals around the quantity of interest, the population mean, 
by simply estimating the variance.
But the following statistic is an asymptotically unbiased estimator of the variance term $\sigma^2_{\sdist}(\phi)$ due to \citep[Thm 21.2.6]{douc2018},
\begin{align*}
\frac{1}{n}S_n^2(\phi) &= \frac{1}{n}\Bigg(\sum_{k=0}^{n-1}\big[ \phi\big(\iter_k\big)-\sdist(\phi)\big]\Bigg)^2.
\end{align*}  
\murat{Can we make sure the above expression for the variance is correct?}
Therefore, for a large enough number of iterations, confidence intervals can be constructed around $\sdist(\phi)$,
using the following distribution
\begin{align*}
\mathcal{N}\left(\frac{1}{n}\sum_{k=0}^{n-1}\phi\big(\iter_{k}\big),  
\frac{1}{n^2}\Bigg(\sum_{k=0}^{n-1}\big[ \phi\big(\iter_k\big)-\sdist(\phi)\big]\Bigg)^2\right).
\end{align*}
Unfortunately, we cannot characterize how large the number of iterations should be due to the asymptotic nature of our results, and existing non-asymptotic results only cover the strongly convex case~\cite{anastasiou2019normal}.
\textbf{Coordinate-wise Confidence Intervals:} Our contributions provide a concrete step towards establishing coordinate-wise confidence intervals for parameter estimation by constant step size SGD algorithm for non-convex minimization problems arising in statistical machine learning. Indeed, obtaining coordinate-wise confidence intervals via asymptotic normality is crucial in statistical inference, especially when the parameter space grows with the number of samples~\cite{he2000parameters,loh2017statistical, chernozhukov2013gaussian, chen2019inference}. For example, consider the task of matrix completion in which we are required to estimate the unobserved entries of a true matrix. Such a problem arises in collaborative filtering tasks, where the rows of the matrix correspond to users and columns correspond to items. The entries of the matrix consists of ratings provided by the users for the items. In practice, only partial entries of this matrix is randomly observed and hence using a potentially non-convex matrix completion algorithm~\cite{ge2016matrix, chen2019inference}, one could estimate the unobserved ratings. In this context, due to the random nature of the problem, providing confidence intervals for the estimated rating is crucial. Often times we are only interested in providing confidence intervals for the ratings of particular items by a particular user. This task could be exactly captured by defining the test function $\phi$ appropriately.

\fi


\iffalse

\newpage

\sv{Starting here is the old version for comparison.}

We provided theoretical results characterizing the bias and the fluctuations of constant step size SGD for stochastic non-convex optimization of dissipative objective functions. Our techniques are based on the connection between constant step size SGD and Markov chains~\cite{dieuleveut2017}. We characterized the conditions on the step size under which the SGD iterates attain a unique stationary distribution for dissipative (non-convex) objective functions. Based on this, we established a central limit theorem for understanding the fluctuations of constant step size SGD around the expected value of the stationary distribution. Finally, we characterized the bias between the expected value under this stationary distribution and any first-order critical point of the objective function. There are several avenues for future research which we highlight below.


\textbf{Estimating the Asymptotic Variance:} As discussed in Section~\ref{sec:cltheory}, in order for using the established CLT to compute confidence intervals in practice, the population expectation $\sdist(\phi)$ and asymptotic variance $\sigma^2_{\sdist}(\phi)$ have to be estimated. We suggest the following three ways to do so:

\begin{itemize}[leftmargin=20pt,noitemsep]
	\item Estimate them based on sample average of a single trajectory of SGD iterates, i.e., the mean $\sdist(\phi)$ and variance $\sigma^2_{\sdist}(\phi)$ are estimated respectively as \sv{Stanislav To Do: find references for variance estimation}
	\eq{
		\frac{1}{n}\sum_{k=0}^{n-1}\phi\big(\iter_{k}\big) \qquad~\text{and}~\qquad \frac{1}{n^2}\Bigg(\sum_{k=0}^{n-1}\big[ \phi\big(\iter_k\big)- \frac{1}{n}\sum_{k=0}^{n-1}\phi\big(\iter_{k}\big)  \big]\Bigg)^2.
	}
	\item First run $N$ parallel SGD trajectories and compute the average of each trajectory, to obtain $N$ independent observations from the stationary distribution $\pi_\eta$. Next, use the $N$ observations to compute the sample mean and sample variance estimators for $\sdist(\phi)$ and $\sigma^2_{\sdist}(\phi)$. This approach is a completely parallel bootstrap procedure.
	\item Leverage the online bootstrap approaches proposed in~\cite{fang2018online, su2018statistical} for the constant step size SGD
	setting in order to obtain bootstrap estimates of $\sdist(\phi)$ and variance $\sigma^2_{\sdist}(\phi)$. 
\end{itemize}
A detailed theoretical investigation on the relative merits of the above approaches is left as future work. We also remark that as the constant step size SGD is biased away from the first-order critical points of the objective, developing and analyzing online versions of bias-corrected bootstrap procedures (see, for example~\cite{efron1994introduction, hall2013bootstrap}) are extremely interesting future directions. This would provide the data analyst with a data-driven and algorithm-dependent approach for establishing asymptotically-valid confidence intervals for non-convex statistical learning problems.  

\fi

\iffalse
We can construct confidence intervals around the quantity of interest, the population mean, 
by simply estimating the variance.
But the following statistic is an asymptotically unbiased estimator of the variance term $\sigma^2_{\sdist}(\phi)$ due to \citep[Thm 21.2.6]{douc2018},
\begin{align*}
\frac{1}{n}S_n^2(\phi) &= \frac{1}{n}\Bigg(\sum_{k=0}^{n-1}\big[ \phi\big(\iter_k\big)-\sdist(\phi)\big]\Bigg)^2.
\end{align*}  
\murat{Can we make sure the above expression for the variance is correct?}
Therefore, for a large enough number of iterations, confidence intervals can be constructed around $\sdist(\phi)$,
using the following distribution
\begin{align*}
\mathcal{N}\left(\frac{1}{n}\sum_{k=0}^{n-1}\phi\big(\iter_{k}\big),  
\frac{1}{n^2}\Bigg(\sum_{k=0}^{n-1}\big[ \phi\big(\iter_k\big)-\sdist(\phi)\big]\Bigg)^2\right).
\end{align*}
Unfortunately, we cannot characterize how large the number of iterations should be due to the asymptotic nature of our results, and existing non-asymptotic results only cover the strongly convex case~\cite{anastasiou2019normal}.
\textbf{Coordinate-wise Confidence Intervals:} Our contributions provide a concrete step towards establishing coordinate-wise confidence intervals for parameter estimation by constant step size SGD algorithm for non-convex minimization problems arising in statistical machine learning. Indeed, obtaining coordinate-wise confidence intervals via asymptotic normality is crucial in statistical inference, especially when the parameter space grows with the number of samples~\cite{he2000parameters,loh2017statistical, chernozhukov2013gaussian, chen2019inference}. For example, consider the task of matrix completion in which we are required to estimate the unobserved entries of a true matrix. Such a problem arises in collaborative filtering tasks, where the rows of the matrix correspond to users and columns correspond to items. The entries of the matrix consists of ratings provided by the users for the items. In practice, only partial entries of this matrix is randomly observed and hence using a potentially non-convex matrix completion algorithm~\cite{ge2016matrix, chen2019inference}, one could estimate the unobserved ratings. In this context, due to the random nature of the problem, providing confidence intervals for the estimated rating is crucial. Often times we are only interested in providing confidence intervals for the ratings of particular items by a particular user. This task could be exactly captured by defining the test function $\phi$ appropriately.


\textbf{Algorithmic Inference for Local Minimizers:} In this work, we focussed only on understanding fluctuations of constant step size SGD around the stationary distribution of the SGD iterates for a class of dissipative non-convex objective functions. For several non-convex minimization problems arising in robust statistics, all stationary points have favorable statistical properties~\cite{elsener2018sharp,loh2017statistical}. Hence, our results would be leveraged for such statistical problems. But for several other problems arising in machine learning, only local minimizers have favorable statistical properties~\cite{kawaguchi2016deep,chi2019nonconvex}. For future work, we will focus on quantifying uncertainty of algorithms converging to local minimizers, such as perturbed stochastic gradient descent and stochastic cubic-regularized Newton's methods. 

\fi
{"config": "arxiv", "file": "2006.07904/Sections/discussion.tex"}