Divide-and-Conquer Learning with Nyström: Optimal Rate and Algorithm

Kernel Regularized Least Squares (KRLS) is a fundamental learner in machine learning. However, due to the high time and space requirements, it has no capability to large scale scenarios. Therefore, we propose DC-NY, a novel algorithm that combines divide-and-conquer method, Nyström, conjugate gradient, and preconditioning to scale up KRLS, has the same accuracy of exact KRLS and the minimum time and space complexity compared to the state-of-the-art approximate KRLS estimates. We present a theoretical analysis of DC-NY, including a novel error decomposition with the optimal statistical accuracy guarantees. Extensive experimental results on several real-world large-scale datasets containing up to 1M data points show that DC-NY significantly outperforms the state-of-the-art approximate KRLS estimates.

Authors

• Rong Yin Institute of Information Engineering, CAS School of Cyber Security, University of Chinese Academy of Sciences
• Yong Liu
• Lijing Lu Peking University Chinese Academy of Science
• Weiping Wang Institute of Information Engineering, Chinese Academy of Sciences
• Dan Meng

Keywords

No keywords are indexed for this paper.