On variance reduction for stochastic smooth convex optimization with multiplicative noise
Preprint
Abstract
We propose stochastic approximation (SA) methods for stochastic smooth convex optimization (SSCO) with a general distribution. Typically, it is assumed an oracle with an upper bound $\sigma^2$ on its variance (OUBV). Differently, we suppose an oracle with \emph{multiplicative noise} (OMN), a setting rarely addressed before. This is a more aggressive but realistic framework where the oracle may have an unbounded variance. Our schemes use dynamic sampling and achieve optimal iteration complexity (number of iterations) with an optimal or near-optimal oracle complexity (number of samples). For non-strongly convex SSCO, we use an accelerated SA method a la FISTA which achieves, given tolerance $\epsilon>0$, the optimal iteration complexity of $\mathcal{O}(\epsilon^{-\frac{1}{2}})$ with a near-optimal oracle complexity of $\mathcal{O}(\epsilon^{-2})[\ln(\epsilon^{-\frac{1}{2}})]^2$. This improves upon Ghadimi and Lan [Math. Program., 156:59-99, 2016] where it is assumed an OUBV. For strongly convex SSCO, we propose a SA method with optimal iteration complexity of $\mathcal{O}(\ln(\epsilon^{-1}))$ and optimal oracle complexity of $\mathcal{O}(\epsilon^{-1})$. This improves upon Byrd et al. [Math Program, 134:127-155, 2012] where it is also assumed an OUBV. Our bounds depend on the local variances $\sigma(x^*)^2$ at solutions $x^*$ and the per unit distance multiplicative variance $\sigma^2_L$. In case of an OUBV, our bounds are sharper than the mentioned works since typically $\max\{\sigma(x^*)^2,\sigma_L^2\}\ll\sigma^2$. For strongly convex SSCO, our bounds show a localization property: the more well-conditioned the problem is or the larger the initial batch size is, the more our bounds approach those obtained if it was assumed an OUBV with $\sigma^2:=\sigma(x^*)^2$, where $x^*$ is the unique solution. This error bound is exactly achieved if the condition number has a known upper bound.
Keywords
All Related Versions
This publication has 40 references indexed in Scilit:
- Convergence of Stochastic Proximal Gradient AlgorithmApplied Mathematics & Optimization, 2019
- Accelerated gradient methods for nonconvex nonlinear and stochastic programmingMathematical Programming, 2015
- Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithmMathematical Programming, 2015
- Incremental constraint projection methods for variational inequalitiesMathematical Programming, 2014
- Gradient methods for minimizing composite functionsMathematical Programming, 2012
- Sample size selection in optimization methods for machine learningMathematical Programming, 2012
- Pegasos: primal estimated sub-gradient solver for SVMMathematical Programming, 2010
- Primal-dual subgradient methods for convex problemsMathematical Programming, 2007
- Stochastic Approximation and Recursive Algorithms and Applications2003
- A simulation-based approach to two-stage stochastic programming with recourseMathematical Programming, 1998