\section{Introduction}
Successful applications of a machine learning algorithm require the algorithm to generalize well to unseen data. Thus
understanding and bounding the generalization error of machine learning algorithms is an area of intense theoretical interest and practical importance. The single most popular approach to modern machine learning relies on the use of continuous optimization techniques to optimize the appropriate loss function, most notably the stochastic (sub)gradient descent (SGD) method. Yet the generalization properties of SGD are still not well understood.  


Consider the setting of stochastic convex optimization (SCO). In this problem, we are interested in the minimization of the population risk $F_{\D}(x):=\EE_{\bz\sim \D}[ f(x,\bz) ]$, where $\D$ is an arbitrary and unknown distribution, for which we have access to an i.i.d.~sample of size $n$, $\bS=(\bz_1,\ldots,\bz_n)$; and $f(\cdot,z)$ is convex and Lipschitz for all $z$.
\iffalse
Specifically, consider the standard setting of stochastic convex optimization (SCO). For a domain $\Z$ and a convex body $\X \subset \RR^d$, let $\{f(\cdot,z)\}_{z\in \Z}$ be a family of convex $L$-Lipschitz functions  over $\X$ (for normalization purposes we assume for now that $L=1$ and $\X$ is included in the unit ball). Minimization of population risk is the problem of minimizing
$F_{\D}(x):=\EE_{\bz\sim \D}[ f(x,\bz) ]$,
for an unknown distribution $\D$ over $\Z$, given a dataset $\bS=(\bz_1,\ldots,\bz_n)$ of $n$ i.i.d.~samples from $\D$.
\fi
The performance of an
algorithm ${\cal A}$ is
quantified by its expected {\em excess population risk},
$$ \varepsilon_{\mbox{\footnotesize{risk}}}(\A) :=
\EE[F_{\D}(\A(\bS))]- \min_{x\in \X} F_{\D}(x), $$ where the expectation is taken with respect to the randomness of the sample $\bS$ and internal randomness of $\A$.

A standard way to bound the excess risk is given by its decomposition into optimization error (a.k.a.~training error) and generalization error (see eqn.~\eqref{eqn:risk_decomp} in Sec.~\ref{sec:prelims}). The optimization error can be easily measured empirically but assessing the generalization error requires access to fresh samples from the same distribution. Thus bounds on the generalization error lead directly to provable guarantees on the excess population risk.


Classical analysis of SGD allows obtaining bounds on the excess population risk of one pass SGD. In particular, with an appropriately chosen step size, SGD gives a solution with expected excess population risk of $O(1/\sqrt{n})$ and this rate is optimal \citep{nemirovsky1983problem}. However, this analysis does not apply to multi-pass SGD that is ubiquitous in practice.


In an influential work, \citet{HardtRS16} gave the first bounds on the generalization error of general forms of SGD (such as those that make multiple passes over the data). Their analysis relies on algorithmic stability, a classical tool for proving bounds on the generalization error. Specifically, they gave strong bound on the {\em uniform stability} of several variants of SGD on convex and smooth losses (with $2/\eta$-smoothness sufficing when all the step sizes are at most $\eta$). Uniform stability bounds the worst case change in loss of the model output by the algorithm on the worst case point when a single data point in the dataset is replaced \citep{BousquettE02}.  Formally, for a randomized algorithm ${\cal A}$, loss functions $f(\cdot,z)$ and $S\simeq S^{\prime}$ and $z\in\Z$, let $\gamma_{\cal A}(S,S^{\prime}, z):=f(\A(S),z)-f(\A(S^{\prime}),z)$, where $S\simeq S^{\prime}$ denotes that the two datasets differ only in a single data point. We say ${\cal A}$ is $\gamma$-uniformly stable if
$$\sup_{S\simeq S^{\prime},z}\mathbb{E}[\gamma_{\cal A}(S,S^{\prime},z)]\leq \gamma,$$
where the expectation is over the internal randomness of $\cal{A}.$ Stronger notions of stability can also be considered, e.g., bounding the probability -- over the internal randomness of $\cal{A}$ -- that $\gamma_{\cal A}(S,S^{\prime},z)>\gamma$. 
Using stability,
\cite{HardtRS16} showed that several variants of SGD simultaneously achieve the optimal tradeoff between the excess empirical risk and stability with both being $O(1/\sqrt n)$. Several works have used this approach to derive new generalization properties of SGD \citep{London:2017,Chen:2018,FeldmanV:2019}.


The key insight of \citet{HardtRS16} is that a gradient step on a sufficiently smooth convex function is a nonexpansive operator (that is, it does not increase the $\ell_2$ distance between points). Unfortunately, this property does not hold for nonsmooth losses such as the hinge loss. As a result, no non-trivial bounds on the uniform stability of SGD have been previously known in this case.


Uniform stability is also closely related to the notion of differential privacy (DP). DP upper bounds the worst case change in the output distribution of an algorithm when a single data point in the dataset is replaced \citep{DMNS06}. This connection has been exploited in the design of several DP algorithms for SCO. In particular, bounds on the uniform stability of SGD from \citep{HardtRS16} have been crucial in the design and analysis of new DP-SCO algorithms \citep{wu2017bolt,DworkFeldman18,FeldmanMTT18,BFTT19,FKT19}.


\subsection{Our Results}
We establish tight bounds on the uniform stability of the (stochastic) subgradient descent method on nonsmooth convex losses. These results demonstrate that in the nonsmooth case SGD can be substantially less stable. At the same time we show that SGD has strong stability properties even in the regime when its iterations can be expansive.

For convenience, we describe our results in terms of {\em \stabname} (\UHS), which bounds the output sensitivity in $\ell_2$-norm w.r.t.~an arbitrary change in a single data point. Formally, a (randomized) algorithm has $\delta$-\UHS if 
\begin{equation} \label{eqn:UAS_intro}
\sup_{S\simeq S^{\prime}} \EE\left\| \A(S)-\A(S^{\prime})\right\|_2 \leq \delta.
\end{equation}

This notion is implicit in existing analyses of uniform stability
\citep{BousquettE02,ShwartzSSS10,HardtRS16} and was explicitly defined by \citet{Liu:2017}. 
In this work, we prove stronger -- high probability -- upper bounds on the random variable $\delta_{\cal A}(S,S^{\prime}):=\left\|\A(S)-\A(S^{\prime})\right\|$,\footnote{In fact, for both GD and fixed-permutation SGD we can obtain w.p.~1 upper bounds on $\delta_{\cal A}(S,S^{\prime})$, whereas for sampling-with-replacement SGD, we obtain a high-probability upper bound.} and we provide matching lower bounds for the weaker -- in expectation -- notion of \UHS \eqref{eqn:UAS_intro}.
A summary of our bounds is in Table \ref{tab:summary}. For simplicity, they are provided for constant step size; general step sizes (for upper bounds) are provided in Section \ref{sec:UB}.

\begin{table}[h!]
\centering
\begin{tabular}{| M{2.8cm} | M{3cm} | M{4cm} | M{4.5cm}  | N}
\hline
Algorithm	 & H.p.~upper bound    & Exp.~upper bound  & Exp.~Lower bound &\\[5pt] \hline \small
 GD (full batch)  & $4\big(\eta\sqrt{T}+\frac{\eta T}{n} \big)$ &
 $4\big(\eta\sqrt{T}+\frac{\eta T}{n} \big)$
&   $\Omega\big(\eta\sqrt T+ \frac{\eta T}{n}\big)$       
&\\[6pt]\hline
 \small SGD (w/replacement) &
 $4\big(\eta\sqrt{T}+\frac{\eta T}{n}\big) $
 &$\min\{1,\frac{T}{n}\}4\eta\sqrt{T}+4\frac{\eta T}{n} $

& $\Omega\Big(\min\{1,\frac{T}{n}\}\eta\sqrt{T}+\frac{\eta T}{n}\Big)$ &\\[5pt] \hline
\small SGD (fixed permutation) &
$2\eta\sqrt{T}+4\frac{\eta T}{n}$& $\min\{1,\frac{T}{n}\}2\eta\sqrt{T}+4\frac{\eta T}{n}$
& $\Omega\Big(\min\{1,\frac{T}{n}\}\eta\sqrt{T}+\frac{\eta T}{n}\Big)$ &\\[5pt] \hline
\end{tabular}
\caption{
\iffull
\UHS for variants of GD/SGD, with normalized radius and Lipschitz constant. Here $T$ is the number of iterations and $\eta>0$ is the step size. 
Both upper and lower bounds also are $\min\{2,(\cdot)\}$, due to the feasible domain radius.
\else
\UHS for GD and SGD. Here $T=\#$~iterations; $\eta$ is the step size.
\fi
}
\label{tab:summary}
\end{table}

\iffalse
\begin{table}[h!]
\centering
\begin{tabular}{| M{3cm} | M{5cm} | M{5cm}  | N}
\hline
Algorithm	 & Upper bound  & Lower bound &\\[5pt] \hline \small
 GD (full batch)  &
 $4\big(\eta\sqrt{T}+\frac{\eta T}{n} \big)$
&   $\Omega\big(\eta\sqrt T+ \frac{\eta T}{n}\big)$       
&\\[6pt]\hline
 \small SGD (w/replacement)  &$\min\{1,\frac{T}{n}\}4\eta\sqrt{T}+4\frac{\eta T}{n} $

& $\Omega\Big(\min\{1,\frac{T}{n}\}\eta\sqrt{T}+\frac{\eta T}{n}\Big)$ &\\[5pt] \hline
\small SGD (fixed permutation)  & $\min\{1,\frac{T}{n}\}2\eta\sqrt{T}+4\frac{\eta T}{n}$
& $\Omega\Big(\min\{1,\frac{T}{n}\}\eta\sqrt{T}+\frac{\eta T}{n}\Big)$ &\\[5pt] \hline
\end{tabular}
\caption{
\iffull
\UHS for (batch) SGD. Here $T$ is the number of iterations and $\eta>0$ is the step size. 
Both upper and lower bounds also are $\min\{2,(\cdot)\}$, due to the feasible domain radius.
\else
\UHS for GD and SGD. Here $T=\#$~iterations; $\eta$ is the step size.
\fi
}
\label{tab:summary}
\end{table}
\fi

Compared to the smooth case \citep{HardtRS16}, the main difference is the presence of the additional $\eta\sqrt{T}$ term. This term has important implications for the generalization bounds derived from \UHS. The first one is that the standard step size $\eta=\Theta(1/\sqrt{n})$ used in single pass SGD leads to a vacuous stability bound. Unfortunately, as shown by our lower bounds, this  is unavoidable (at least in high dimension). However, by decreasing the step size and increasing the number of steps, one obtains a variant of SGD with nearly optimal balance between the \UHS and the excess empirical risk. 

We highlight two major consequences of our bounds: 
\begin{itemize}[leftmargin=*]
\item \textbf{Generalization bounds for multi-pass nonsmooth SGD.} We prove that the generalization error of multi-pass SGD  with $K$ passes is bounded by $O((\sqrt{Kn}+K)\eta)$. This result can be easily combined with training error guarantees to provide excess risk bounds for this algorithm. Since training error can be measured directly, our generalization bounds would immediately yield strong guarantees on the excess risk in practical scenarios where we can certify small training error.


\item \textbf{Differentially private stochastic convex optimization for non-smooth losses.} We show that a variant of standard noisy SGD \citep{BST14} with constant step size and $n^2$ iterations yields the optimal excess population risk $O\big(\frac{1}{\sqrt{n}}+\frac{\sqrt{d\log (1/\beta)}}{\alpha n}\big)$ for convex \emph{nonsmooth} losses under $(\alpha,\beta)$-differential privacy. The best previous algorithm for this problem is substantially more involved: it relies on a multi-phase regularized SGD with decreasing step sizes and variable noise rates and uses $O(n^2 \sqrt{\log (1/\beta)})$ gradient computations \citep{FKT19}.

\end{itemize}

\subsection{Overview of Techniques}

\begin{itemize}[leftmargin=*]
\item {\bf Upper bounds.}
When gradient steps are nonexpansive, upper-bounding \UHS requires simply summing the differences between the gradients on the neighboring datasets when the replaced data point is used 
\citep{HardtRS16}. This gives the bound of $\eta T/n$ in the smooth case.


By contrast, in the nonsmooth case, \UHS may increase even when the gradient step is performed on the same function. As a result it may increase in {\em every single iteration}. However, we use the fact  that the difference in the subgradients has negative inner product with the difference between the iterates themselves (by monotonicity of the subgradient). Thus the increase in distance satisfies a recurrence with a quadratic and a linear term. Solving this recurrence leads to our upper bounds.


\item {\bf Lower bounds.}
The lower bounds are based on a function with a highly nonsmooth behavior around the origin. More precisely, it is the maximum of linear functions

plus
a small linear drift that is controlled by a single data point. We show that, when starting the algorithm from the origin, the presence of the linear drift pushes the iterate into a trajectory in which each subgradient step is orthogonal to the current iterate. Thus, if $d \geq \min\{T,1/\eta^2\}$,  we get the $\sqrt{T}\eta$ increase in \UHS. Our lower bounds are also robust to averaging of the iterates. \iffull \else The detailed constructions and analyses can be found in Section~4 of the full version, attached as supplementary material.\fi
\end{itemize}


\subsection{Other Related Work}

Stability is a classical approach to proving generalization bounds pioneered by \citet{RogersWagner78,DevroyeW79,DevroyeW79a}. It is based on analysis of the sensitivity of the learning algorithm to changes in the dataset such as leaving one of the data points out or replacing it with a different one. \iffull The choice of how to measure the effect of the change and various ways to average over multiple changes give rise to a variety of stability notions 
(e.g., \citep{BousquettE02,MukherjeeNPR06,ShwartzSSS10}).\fi\,\! Uniform stability was introduced by \citet{BousquettE02} in order to derive general bounds on the generalization error that hold with high probability. These bounds have been significantly improved in a recent sequence of works \citep{FeldmanV:2018,FeldmanV:2019,BousquetKZ19}. \iffull A long line of work focuses on the relationship between various notions of stability and learnability in supervised setting (see  \citep{Kearns:1999,PoggioRMN04,ShwartzSSS10} for an overview). These works employ relatively weak notions of average stability and derive a variety of asymptotic equivalence results. \fi
\citet{Chen:2018} establish limits of stability in the smooth convex setting, proving that accelerated methods must satisfy strong stability lower bounds. Stability-based data-dependent generalization bounds for continuous losses were studied in \citep{Maurer17,Kuzborskij:2018}.


First applications of uniform stability in the context of stochastic convex optimization relied on the stability of the empirical minimizer for strongly convex losses \citep{BousquettE02}. Therefore a natural approach to achieve uniform stability (and also \UHS) is to add a strongly convex regularizer and solve the ERM to high accuracy \citep{ShwartzSSS10}. Recent applications of this approach can be found for example in \citep{KorenLevy15,Charles:2018,FKT19}. In contrast, our approach does not require strong convexity and applies to all iterates of the SGD and not only to a very accurate empirical minimizer.


Classical approach to generalization relies on \emph{uniform convergence} of empirical risk to population risk.
Unfortunately, without additional structural assumptions on convex functions, a lower bound of $\Omega(\sqrt{d/n})$ on the rate of \emph{uniform convergence} for convex SCO is known \citep{ShwartzSSS10,Feldman:16erm}. The dependence on the dimension $d$ makes the bound obtained via the uniform-convergence approach vacuous in the high-dimensional settings common in modern applications.


Differentially private convex optimization has been studied extensively for over a decade (see, e.g., \citep{CM08,CMS,jain2012differentially,kifer2012private,ST13sparse, BST14,ullman2015private,JTOpt13,talwar2015nearly, BFTT19, FKT19}).

However, until recently, the research focused on minimization of the empirical risk. \iffull Population risk for DP-SCO was first studied by \citet{BST14} who gave an upper bound of $\max\left(\tfrac{d^{\frac{1}{4}}}{\sqrt{n}}, \tfrac{\sqrt{d}}{\alpha n}\right)$ \cite[Sec. F]{BST14} on the excess risk. \fi A recent work of  \citet{BFTT19} established that the optimal rate of the excess population risk for $(\alpha,\beta)$-DP SCO algorithms is $O\big(\frac{1}{\sqrt{n}}+\frac{\sqrt{d\log (1/\beta)}}{\alpha n}\big)$. Their algorithms are relatively inefficient, especially in the nonsmooth case. Subsequently, \citet{FKT19} gave several new algorithms for DP-SCO with the optimal population risk. For sufficiently smooth losses, their algorithms use a linear number of gradient computations. In the nonsmooth case, as mentioned earlier, their algorithm requires $O(n^2\sqrt{\log(1/\beta)})$ gradient computations and is significantly more involved than the algorithm shown here.
{"config": "arxiv", "file": "2006.06914/sec_Introduction.tex"}