Carlo (MCMC, [@gilks1995markov]; [@metropolis1953equation]; [@hastings1970monte]; [@geman1984gibbs]; [@brooks2011handbook]) have to be adopted, which can be quite slow in practice.

In this article, we propose a novel and efficient algorithm called the stochastic approximate gradient descent (SAGD), as an alternative to SGD for cases where unbiased stochastic gradients cannot be trivially computed. The key idea of SAGD is to construct the stochastic gradient using the Langevin algorithm [@roberts1996exponential; @roberts2002langevin; @cheng2018underdamped], a sampling method whose statistical error can be rigorously quantified. In addition, we use an adaptive sampling scheme that allows larger errors in the early stage of the optimization, and gradually improves the precision as the procedure goes on.

These heuristics are formalized in the SAGD algorithm, and various theoretical results are developed to guarantee its convergence. Moreover, our analysis gives clear rates of the relevant hyperparameters, which provide useful guidelines for practical implementations of SAGD. The highlights and main contributions of this article are as follows:

-   We develop a new computational framework for SGD problems in which a stochastic gradient cannot be trivially obtained. The proposed SAGD algorithm is fully automated with a solid convergence guarantee.

-   New theoretical contributions are made to the underdamped Langevin algorithm for sampling from 