A Variable Sample-Size Stochastic Quasi-Newton Method for Smooth and Nonsmooth Stochastic Convex Optimization

In the last several years, stochastic quasi-Newton (SQN) methods have assumed increasing relevance in solving a breadth of machine learning and stochastic optimization problems. Inspired by recently presented SQN schemes [1]-[3], we consider merely convex and possibly nonsmooth stochastic programs and utilize increasing sample-sizes to allow for variance reduction. To this end, we make the following contributions. (i) A regularized and smoothed variable sample-size BFGS update (rsL-BFGS) is developed that can accommodate nonsmooth convex objectives by utilizing iterative regularization and smoothing; (ii) A regularized variable sample-size SQN (rVS-SQN) is developed that admits a rate and oracle complexity bound of {O}(1/k^{1-\varepsilon}) and {O}(\epsilon^{-(3+\varepsilon)/(1-\varepsilon)}), respectively (where \varepsilon, \varepsilon > 0 are arbitrary scalars), improving on past rate statements; (iii) By leveraging (rsL-BFGS), we develop rate statements for the function of the ergodic average through a regularized and smoothed VS-SQN scheme that can accommodate nonsmooth (but smoothable) functions with the convergence rate {O}(1/k^{1/3-2\varepsilon}).