Dependent online kernel learning with constant number of random Fourier features

Area of Science:

• Machine Learning
• Statistical Learning Theory

Background:

• Online kernel learning traditionally assumes independent and identically distributed (i.i.d.) training data.
• Existing methods achieve optimal convergence rates under i.i.d. assumptions but are limited in practical scenarios.

Purpose of the Study:

• To investigate the sampling complexity of random Fourier features in online kernel learning under non-i.i.d. assumptions.
• To analyze the impact of data distribution deviations on learning performance.

Main Methods:

• Theoretical analysis of random Fourier features under non-i.i.d. settings.
• Derivation of convergence rates for excess risk.
• Empirical validation using artificial and real-world datasets.

Main Results:

• Demonstrates that constant sampling complexity is maintained even with non-i.i.d. data.
• Establishes a convergence rate of O(logT/T + ϕ) for excess risk, where ϕ quantifies non-i.i.d. extent.
• Experimental results confirm theoretical findings on both synthetic and large-scale datasets.

Conclusions:

• The findings extend the applicability of random Fourier features to more realistic, non-i.i.d. online learning scenarios.
• The study provides a theoretical framework and empirical evidence for understanding learning dynamics beyond i.i.d. data assumptions.