On the Generalization Ability of Online Gradient Descent Algorithm Under the Quadratic Growth Condition

Area of Science:

• Machine Learning
• Online Learning Algorithms
• Statistical Learning Theory

Background:

• Online learning is widely used in machine learning.
• Traditional analysis relies on strong convexity for sharp generalization bounds.

Purpose of the Study:

• To analyze the generalization ability of online gradient descent under the quadratic growth condition (QGC).
• To demonstrate that strong convexity is not essential for achieving optimal convergence rates in online learning.

Main Methods:

• Utilizing the quadratic growth condition (QGC), a relaxation of strong convexity.
• Applying martingale concentration inequalities.
• Analyzing both independently and identically distributed (i.i.d.) and $\phi$-mixing data settings.

Main Results:

• Proving an excess risk convergence rate of $O(\log T/T)$ for i.i.d. data under QGC.
• Achieving an excess risk bound of $O(\log T /T+\phi (\tau))$ for $\phi$-mixing processes.
• Demonstrating theoretical results with synthetic and real-world data.

Conclusions:

• The quadratic growth condition (QGC) is sufficient for achieving sharp $O(\log T/T)$ convergence rates in online learning.
• Strong convexity is not a prerequisite for optimal performance in these online learning scenarios.