@article{Yin_Liu_Lu_Wang_Meng_2020, title={Divide-and-Conquer Learning with Nyström: Optimal Rate and Algorithm}, volume={34}, url={https://ojs.aaai.org/index.php/AAAI/article/view/6147}, DOI={10.1609/aaai.v34i04.6147}, abstractNote={<p>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.</p>}, number={04}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Yin, Rong and Liu, Yong and Lu, Lijing and Wang, Weiping and Meng, Dan}, year={2020}, month={Apr.}, pages={6696-6703} }