  In this paper, a new theory is developed for first-order stochastic convex
optimization, showing that the global convergence rate is sufficiently
quantified by a local growth rate of the objective function in a neighborhood
of the optimal solutions. In particular, if the objective function $F(\mathbf
w)$ in the $\epsilon$-sublevel set grows as fast as $\|\mathbf w - \mathbf
w_*\|_2^{1/\theta}$, where $\mathbf w_*$ represents the closest optimal
solution to $\mathbf w$ and $\theta\in(0,1]$ quantifies the local growth rate,
the iteration complexity of first-order stochastic optimization for achieving
an $\epsilon$-optimal solution can be $\widetilde O(1/\epsilon^{2(1-\theta)})$,
which is optimal at most up to a logarithmic factor. To achieve the faster
global convergence, we develop two different accelerated stochastic subgradient
methods by iteratively solving the original problem approximately in a local
region around a historical solution with the size of the local region gradually
decreasing as the solution approaches the optimal set. Besides the theoretical
improvements, this work also includes new contributions towards making the
proposed algorithms practical: (i) we present practical variants of accelerated
stochastic subgradient methods that can run without the knowledge of
multiplicative growth constant and even the growth rate $\theta$; (ii) we
consider a broad family of problems in machine learning to demonstrate that the
proposed algorithms enjoy faster convergence than traditional stochastic
subgradient method. We also characterize the complexity of the proposed
algorithms for ensuring the gradient is small without the smoothness
assumption.
