Sketch Kernel Ridge Regression Using Circulant Matrix: Algorithm and Theory.

Area of Science:

• Machine Learning
• Statistical Modeling
• Computational Science

Background:

• Kernel Ridge Regression (KRR) is a robust nonparametric regression technique.
• Direct KRR computation suffers from high time (O(n^3)) and space (O(n^2)) complexity, limiting its use on large datasets.
• Existing methods struggle to balance accuracy with computational efficiency for large-scale KRR.

Purpose of the Study:

• To develop a novel random sketch technique for Kernel Ridge Regression.
• To improve the scalability and practical applicability of KRR for large datasets.
• To reduce the time and space complexity of KRR estimation.

Main Methods:

• Proposed a new random sketch method utilizing circulant matrices.
• Leveraged the Fast Fourier Transform (FFT) for efficient matrix-vector products.
• Analyzed the theoretical properties and performance of the circulant matrix sketch.

Main Results:

• The circulant matrix sketch achieves linear space complexity and reduced time complexity.
• The proposed method demonstrates comparable accuracy to state-of-the-art KRR approximations.
• Experimental results confirm the efficiency and effectiveness of the random sketch technique.

Conclusions:

• The novel circulant matrix sketch makes Kernel Ridge Regression scalable and practical for large-scale data.
• This approach offers significant improvements in time complexity while maintaining high accuracy.
• The method provides a theoretical guarantee for optimal convergence rates in KRR approximation.