Stochastic Approximation of Smooth and Strongly Convex Functions: Beyond the $O(1/T)$ Convergence Rate

Stochastic approximation (SA) is a classical approach for stochastic convex\noptimization. Previous studies have demonstrated that the convergence rate of\nSA can be improved by introducing either smoothness or strong convexity\ncondition. In this paper, we make use of smoothness and strong convexity\nsimultaneously to boost the convergence rate. Let $\\lambda$ be the modulus of\nstrong convexity, $\\kappa$ be the condition number, $F_*$ be the minimal risk,\nand $\\alpha>1$ be some small constant. First, we demonstrate that, in\nexpectation, an $O(1/[\\lambda T^\\alpha] + \\kappa F_*/T)$ risk bound is\nattainable when $T = \\Omega(\\kappa^\\alpha)$. Thus, when $F_*$ is small, the\nconvergence rate could be faster than $O(1/[\\lambda T])$ and approaches\n$O(1/[\\lambda T^\\alpha])$ in the ideal case. Second, to further benefit from\nsmall risk, we show that, in expectation, an $O(1/2^{T/\\kappa}+F_*)$ risk bound\nis achievable. Thus, the excess risk reduces exponentially until reaching\n$O(F_*)$, and if $F_*=0$, we obtain a global linear convergence. Finally, we\nemphasize that our proof is constructive and each risk bound is equipped with\nan efficient stochastic algorithm attaining that bound.\n