Stochastic gradient descent (SGD) is the workhorse of modern machine learning. Sometimes, there are many different potential gradient estimators that can be used. When so, choosing the one with the best tradeoff between cost and variance is important. This paper analyzes the convergence rates of SGD as a function of time, rather than iterations. This results in a simple rule to select the estimator that leads to the best optimization convergence guarantee. This choice is the same for different variants of SGD, and with different assumptions about the objective (e.g. convexity or smoothness). Inspired by this principle, we propose a technique to automatically select an estimator when a finite pool of estimators is given. Then, we extend to infinite pools of estimators, where each one is indexed by control variate weights. This is enabled by a reduction to a mixed-integer quadratic program. Empirically, automatically choosing an estimator performs comparably to the best estimator chosen with hindsight. In stochastic gradient variational inference (SGVI) there are multiple gradient estimators with varying costs and variances. Estimators may be obtained using the reparameterization trick (Kingma and Welling (2013) ; Rezende et al. (2014) ; Titsias and Lázaro-Gredilla (2014)), the score function method (Williams (1992) ), or other techniques (Titsias and Lázaro-Gredilla (2015) ; Ruiz et al. (2016) ; Agakov and Barber (2004) ). Also, many control variates can be added to an estimator to reduce variance (Miller et al. (2017) (2018)). The cost and variance of an estimator significantly affects optimization convergence speed (Bottou et al. (2018) ). The use of different estimators leads to different optimization performances, and the estimator with optimal cost-variance tradeoff is often situationdependent (for an example see Fig. 1 ). In settings where multiple estimators with varying costs and variances are available, selecting the optimal one is important. Rather than rely on the user to manually select one, we propose that estimator selection could be done adaptively. This paper investigates how, given a pool of gradient estimators, automatically choose one to get the best convergence guarantee for stochastic optimization. We study cost-variance tradeoffs by analyzing the convergence rates of several variants of SGD. We express convergence rates in terms of time rather than iterations. This leads to what we call the "G 2 T principle": A simple rule that predicts, given a pool of gradient estimators, which one results in the best convergence guarantees for optimization. We use the principle to propose two gradient estimator selection algorithms: One for the case in which a finite pool of estimators is available, and other when the pool contains an infinite number of estimators, each indexed by control variate weights (i.e. control variate selection). Notation: We use g(w, ξ), where ξ is a random variable, to denote an unbiased estimator of target's gradient, G 2 (g) to denote a bound on g's expected squared norm, and T (g) to denote the computational cost of computing estimator g(w, ξ), measured in seconds.
We propose a gradient estimator selection algorithm with the aim on improving optimization efficiency.
{"src": "scitldr-AIC_train", "paper_id": "SygQKy3EFB"}