A Variable Sample-Size Stochastic Quasi-Newton Method for Smooth and Nonsmooth Stochastic Convex Optimization
Afrooz Jalilzadeh, Angelia Nedić, Uday V. Shanbhag, Farzad Yousefian · 2018
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/k1-ε) and O(ε-(3+ε)/(1-ε)), respectively (where 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/k1/3-2ε).