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 online gradient-based algorithms to inexactness depends on factors such as decision dimension, gradient norm, function variations, alignment of gradients, and function curvature. We verify our results numerically and experimentally, bridging a significant knowledge gap. As a case study, we introduce a general online optimization algorithm to explore the interplay between bias and variance with dynamic regret.