Stochastic gradient descent (SGD), which dates back to the 1950s, is one of the most popular and effective approaches for performing stochastic optimization. Research on SGD resurged recently in machine learning for optimizing convex loss functions and training nonconvex deep neural networks. The theory assumes that one can easily compute an unbiased gradient estimator, which is usually the case due to the sample average nature of empirical risk minimization. There exist, however, many scenarios (e.g., graphs) where an unbiased estimator may be as expensive to compute as the full gradient because training examples are interconnected. Recently, Chen et al. (2018) proposed using a consistent gradient estimator as an economic alternative. Encouraged by empirical success, we show, in a general setting, that consistent estimators result in the same convergence behavior as do unbiased ones. Our analysis covers strongly convex, convex, and nonconvex objectives. We verify the results with illustrative experiments on synthetic and real-world data. This work opens several new research directions, including the development of more efficient SGD updates with consistent estimators and the design of efficient training algorithms for large-scale graphs.
 Consider the standard setting of supervised learning. There exists a joint probability distribution P (x, y) of data x and associated label y and the task is to train a predictive model, parameterized by w, that minimizes the expected loss between the prediction and the ground truth y. Let us organize the random variables as ξ = (x, y) and use the notation (w; ξ) for the loss. If ξ i = (x i , y i ), i = 1, . . . , n, are iid training examples drawn from P , then the objective function is either one of the following well-known forms: expected risk f (w) = E[ (w; ξ)]; empirical risk f (w) = 1 n n i=1 (w; ξ i ). Stochastic gradient descent (SGD), which dates back to the seminal work of Robbins & Monro (1951) , has become the de-facto optimization method for solving these problems in machine learning. In SGD, the model parameter is updated until convergence with the rule where γ k is a step size and g k is an unbiased estimator of the gradient ∇f (w k ). Compared with the full gradient (as is used in deterministic gradient descent), an unbiased estimator involves only one or a few training examples ξ i and is usually much more efficient to compute.
Convergence theory for biased (but consistent) gradient estimators in stochastic optimization and application to graph convolutional networks
{"src": "scitldr-AIC_train", "paper_id": "rygMWT4twS"}