On the Convergence of SGD with Biased Gradients
This work addresses convergence guarantees for biased SGD methods, which are incremental but relevant for applications like distributed learning and derivative-free optimization.
The paper analyzes the convergence of stochastic gradient descent (SGD) with biased gradients, deriving complexity results for smooth non-convex functions and improved rates under the Polyak-Lojasiewicz condition, quantifying how bias magnitude affects accuracy and rates.
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.