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
|
Abstract:
|
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.