Online Program Home
My Program

Abstract Details

Activity Number: 513 - Topics in Monte Carlo Simulation
Type: Contributed
Date/Time: Wednesday, July 31, 2019 : 10:30 AM to 12:20 PM
Sponsor: Section on Statistical Computing
Abstract #306984
Title: A Second-Order Adaptive Sampling Framework for Stochastic Gradient Descent
Author(s): David Newton* and Raghu Pasupathy
Companies: Purdue University and Purdue University
Keywords: stochastic gradient descent; stochastic optimization; machine learning; big data; stochastic approximation

We introduce a second-order adaptive sampling recursive framework to solve smooth stochastic optimization problems that have become ubiquitous in training machine learning models using large datasets. The framework we introduce has the familiar structure of stochastic approximation (or stochastic gradient descent) but with the facility of gradient and Hessian-inverse estimators obtained through adaptive sampling, that is, obtained using historical and current information. We first provide sufficient conditions for convergence in $L_2$-norm of the proposed framework. We then characterize the convergence rate of the iterates for a concrete choice of step size and the sampling rate to be used within the recursion. Interestingly, the convergence rate resulting from these choices attains the Cramer-Rao lower bound for unbiased estimators. This result appears to be the first of its kind and potentially explains the reported strong empirical behavior of a number of second-order adaptive sampling heuristics that have appeared recently in the literature.

Authors who are presenting talks have a * after their name.

Back to the full JSM 2019 program