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

arXiv: https://arxiv.org/abs/1804.05368 · HTML: https://mlsanity.com/paper/1804.05368/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Apr 2018.

## Built on by (most cited first, 2 of 2)

- [A Retrospective Approximation Approach for Smooth Stochastic Optimization](https://mlsanity.com/paper/2103.04392/) (2021)
- [Adaptive First- and Second-Order Algorithms for Large-Scale Machine Learning](https://mlsanity.com/paper/2111.14761/) (2021)

## Abstract (arXiv)

Classical theory for quasi-Newton schemes has focused on smooth deterministic unconstrained optimization while recent forays into stochastic convex optimization have largely resided in smooth, unconstrained, and strongly convex regimes. Naturally, there is a compelling need to address nonsmoothness, the lack of strong convexity, and the presence of constraints. Accordingly, this paper presents a quasi-Newton framework that can process merely convex and possibly nonsmooth (but smoothable) stochastic convex problems. We propose a framework that combines iterative smoothing and regularization with a variance-reduced scheme reliant on using increasing sample-sizes of gradients. We make the following contributions. (i) We develop a regularized and smoothed variable sample-size BFGS update (rsL-BFGS) that generates a sequence of Hessian approximations and can accommodate nonsmooth convex objectives by utilizing iterative regularization and smoothing. (ii) In strongly convex regimes with state-dependent noise, the proposed variable sample-size stochastic quasi-Newton scheme admits a non-asymptotic linear rate of convergence while the oracle complexity of computing an ε-solution is O(kappam+1/ε) where kappa is the condition number and m≥ 1. In nonsmooth (but smoothable) regimes, using Moreau smoothing retains the linear convergence rate. To contend with the possible unavailability of Lipschitzian and strong convexity parameters, we also provide sublinear rates; (iii) In merely convex but smooth settings, the regularized VS-SQN scheme rVS-SQN displays a rate of O(1/k(1-varepsilon)). When the smoothness requirements are weakened, the rate for the regularized and smoothed VS-SQN scheme worsens to O(k-1/3). Such statements allow for a state-dependent noise assumption under a quadratic growth property.