Stochastic Gradient Descent with Biased but Consistent Gradient Estimators

Understand

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.