  We establish upper bounds for the expected excess risk of models trained by
proper iterative algorithms which approximate the local minima. Unlike the
results built upon the strong globally strongly convexity or global growth
conditions e.g., PL-inequality, we only require the population risk to be
\emph{locally} strongly convex around its local minima. Concretely, our bound
under convex problems is of order $\tilde{\cO}(1/n)$. For non-convex problems
with $d$ model parameters such that $d/n$ is smaller than a threshold
independent of $n$, the order of $\tilde{\cO}(1/n)$ can be maintained if the
empirical risk has no spurious local minima with high probability. Moreover,
the bound for non-convex problem becomes $\tilde{\cO}(1/\sqrt{n})$ without such
assumption. Our results are derived via algorithmic stability and
characterization of the empirical risk's landscape. Compared with the existing
algorithmic stability based results, our bounds are dimensional insensitive and
without restrictions on the algorithm's implementation, learning rate, and the
number of iterations. Our bounds underscore that with locally strongly convex
population risk, the models trained by any proper iterative algorithm can
generalize well, even for non-convex problems, and $d$ is large.
