On the Generalization Ability of Online Gradient Descent Algorithm Under the Quadratic Growth Condition
Online learning has been successfully applied in various machine learning problems. Conventional analysis of online learning achieves a sharp generalization bound with a strongly convex assumption. In this paper, we study the generalization ability of the classic online gradient descent algorithm under the quadratic growth condition (QGC), a strictly weaker condition than strong convexity. Under some mild assumptions, we prove that the excess risk converges no worse than <inline-formula> <tex-math notation="LaTeX">$O(\log T/T)$ </tex-math></inline-formula> when the data are independently and identically distributed (i.i.d.). When the data are generated from a <inline-formula> <tex-math notation="LaTeX">$\phi $ </tex-math></inline-formula>-mixing process, we achieve the excess risk bound <inline-formula> <tex-math notation="LaTeX">$O(\log T /T+\phi (\tau))$ </tex-math></inline-formula>, where <inline-formula> <tex-math notation="LaTeX">$\phi (\tau)$ </tex-math></inline-formula> is the mixing coefficient capturing the non-i.i.d. attribute. Our key technique is based on the combination of the QGC and the martingale concentrations. Our results indicate that the strong convexity is not necessary to achieve the sharp <inline-formula> <tex-math notation="LaTeX">$O(\log {T}/T)$ </tex-math></inline-formula> convergence rate in online learning. We verify our theories on both synthetic and real-world data.