Does online gradient descent (and variants) still work with biased gradient and variance?

Deterministic bias and stochastic unbiased noise in gradients can affect the performance of online learning algorithms. While existing studies provide bounds for dynamic regret under these uncertainties, they offer limited insight into the specific functionality of the algorithms. This paper investigates the efficacy of online gradient-based algorithms (OGD) with inexact gradients, quantifying the degree of tolerance to these uncertainties and identifying conditions for ensuring robustness. Our analysis reveals that bias and variance function independently, and the tolerance of OGD to inexactness depends on factors such as decision dimension, gradient norm, function variations, alignment of gradients, and function curvature. We verify results numerically and experimentally and introduce a general online optimization algorithm as a case study.