Characterization of Excess Risk for Locally Strongly Convex Population
  Risk
  We establish upper bounds for the expected excess risk of models trained by
proper iterative algorithms which approximate the global minima (resp. local
minima) under convex (resp. non-convex) loss functions. In contrast to the
existing bounds, our results are not limited to a specific algorithm e.g.,
stochastic gradient descent, and the bounds remain small when the sample size
$n$ is large for an arbitrary number of iterations. In concrete, after a
certain number of iterations, the bound under convex loss functions is of order
$\tilde{\mathcal{O}}(1/n)$. Under non-convex loss functions with $d$ model
parameters such that $d/n$ is smaller than a threshold independent of $n$, the
order of $\tilde{\mathcal{O}}(1/n)$ can be maintained if the empirical risk has
no spurious local minima with high probability. The bound becomes
$\tilde{\mathcal{O}}(1/\sqrt{n})$ if we discard the assumption on the empirical
local minima. Technically, we assume the Hessian of the population risk is
non-degenerate at each local minima. Under this and some other mild smoothness
and boundedness assumptions, we establish our results via algorithmic stability
\citep{bousquet2002stability} and characterization of the empirical risk
landscape. Our bounds are dimensional insensitive and fast converges to zero as
$n$ goes to infinity. These underscore that with locally strongly convex
population risk, the models trained by proper iterative algorithms generalize
well on unseen data even when the loss function is non-convex and $d$ is large.
