Asymptotic and finite-sample properties of estimators based on stochastic gradients

Efficient optimization procedures, such as stochastic gradient descent, have been gaining popularity for estimation tasks with large amounts of data. In this paper, we introduce an implicit stochastic gradient descent estimation procedure that ameliorates the procedures derived from stochastic approximations a la Robbins & Monro (1951), termed explicit for contrast, by using iterates that are implicitly defined. The implicit iterates are shrinked versions of the explicit iterates, and it can be shown that the amount of shrinkage depends on the observed Fisher information, but this latter quantity needs not be directly computed. The implicit procedure is thus robust to the choice of a scalar hyper-parameter in stochastic gradient descent, known as the learning rate, that affects its asymptotic statistical properties. In contrast, the explicit procedure requires the learning rate to agree with the eigenvalues of the Fisher information matrix of the underlying model parameters in order to be stable. In the context of generalized linear models, we derive analytic formulas for the asymptotic bias and variance of both procedures as estimation methods, and quantify their efficiency loss compared to maximum likelihood. We also show how loss in efficiency can be avoided through careful choice of the parameterization. Our analysis naturally extends to exponential family models, and to a general class of estimation methods through Monte-Carlo stochastic gradient descent, in problems where the likelihood is hard to compute but where it is easy to sample from the underlying model. We demonstrate our theory in an extensive set of experiments involving real and simulated data. Implicit stochastic gradient descent compares favorably to other popular estimation methods, and it is a superior form of stochastic gradient descent when it can be implemented efficiently.