  We analyze the complexity of biased stochastic gradient methods (SGD), where
individual updates are corrupted by deterministic, i.e. biased error terms. We
derive convergence results for smooth (non-convex) functions and give improved
rates under the Polyak-Lojasiewicz condition. We quantify how the magnitude of
the bias impacts the attainable accuracy and the convergence rates (sometimes
leading to divergence).
  Our framework covers many applications where either only biased gradient
updates are available, or preferred, over unbiased ones for performance
reasons. For instance, in the domain of distributed learning, biased gradient
compression techniques such as top-k compression have been proposed as a tool
to alleviate the communication bottleneck and in derivative-free optimization,
only biased gradient estimators can be queried. We discuss a few guiding
examples that show the broad applicability of our analysis.
