TY - JOUR AU - Yin, Rong AU - Liu, Yong AU - Lu, Lijing AU - Wang, Weiping AU - Meng, Dan PY - 2020/04/03 Y2 - 2024/03/29 TI - Divide-and-Conquer Learning with Nyström: Optimal Rate and Algorithm JF - Proceedings of the AAAI Conference on Artificial Intelligence JA - AAAI VL - 34 IS - 04 SE - AAAI Technical Track: Machine Learning DO - 10.1609/aaai.v34i04.6147 UR - https://ojs.aaai.org/index.php/AAAI/article/view/6147 SP - 6696-6703 AB - <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> ER -