{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,22]],"date-time":"2026-10-22T23:51:42Z","timestamp":1792713102204,"version":"4.5.0"},"reference-count":38,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["FA8750-12-C-0323"],"award-info":[{"award-number":["FA8750-12-C-0323"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Matrix Anal. Appl."],"published-print":{"date-parts":[[2017,1]]},"abstract":"<jats:p>Kernel ridge regression is a simple yet powerful technique for nonparametric regression whose computation amounts to solving a linear system. This system is usually dense and highly ill-conditioned. In addition, the dimensions of the matrix are the same as the number of data points, so direct methods are unrealistic for large-scale datasets. In this paper, we propose a preconditioning technique for accelerating the solution of the aforementioned linear system. The preconditioner is based on random feature maps, such as random Fourier features, which have recently emerged as a powerful technique for speeding up and scaling the training of kernel-based methods, such as kernel ridge regression, by resorting to approximations. However, random feature maps only provide crude approximations to the kernel function, so delivering state-of-the-art results by directly solving the approximated system requires the number of random features to be very large. We show that random feature maps can be much more effective in forming preconditioners, since under certain conditions a not-too-large number of random features is sufficient to yield an effective preconditioner. We empirically evaluate our method and show it is highly effective for datasets of up to one million training examples.<\/jats:p>","DOI":"10.1137\/16m1105396","type":"journal-article","created":{"date-parts":[[2017,10,18]],"date-time":"2017-10-18T13:07:50Z","timestamp":1508332070000},"page":"1116-1138","source":"Crossref","is-referenced-by-count":69,"title":["Faster Kernel Ridge Regression Using Sketching and Preconditioning"],"prefix":"10.1137","volume":"38","author":[{"given":"Haim","family":"Avron","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kenneth L.","family":"Clarkson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David P.","family":"Woodruff","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2017,10,18]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-008-9110-x"},{"key":"atypb2","unstructured":"A. E. Alaoui and M. W. Mahoney,\n                      Fast randomized kernel ridge regression with statistical guarantees\n                      , in Proceedings of Neural Information Processing Systems (NIPS), 2015."},{"key":"atypb3","first-page":"1","author":"Avron H.","year":"2017","journal-title":"Germany"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/090767911"},{"key":"atypb5","unstructured":"H. Avron, H. Nguyen, and D. Woodruff,\n                      Subspace embeddings for the polynomial kernel\n                      , Advances in Neural Information Processing Systems 27 (NIPS 2014)."},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1080\/00401706.2015.1111261"},{"key":"atypb7","first-page":"185","author":"Bach F. R.","year":"2013","journal-title":"NJ"},{"key":"atypb8","unstructured":"G. Blanchard and N. Kr\u00e4mer,\n                      Optimal learning rates for kernel conjugate gradient regression\n                      , Advances in Neural Information Processing Systems 23 (NIPS 2010)."},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"L. Bottou, O. Chapelle, D. DeCoste, and J. Weston,\n                      Large-Scale Kernel Machines (Neural Information Processing)\n                      , MIT Press, Cambridge, MA, 2007.","DOI":"10.7551\/mitpress\/7496.001.0001"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00400-6"},{"key":"atypb11","first-page":"66","volume":"18","author":"Chen J.","year":"2017","journal-title":"J. Mach. Learn. Res."},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1137\/120903002"},{"key":"atypb13","first-page":"2454","author":"Chen J.","year":"2016","journal-title":"Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)"},{"key":"atypb14","first-page":"11","author":"Cohen M. B.","year":"2016","journal-title":"ICALP."},{"key":"atypb15","first-page":"2529","author":"Cutajar K.","year":"2016","journal-title":"New York"},{"key":"atypb16","unstructured":"B. Dai, B. Xie, N. He, Y. Liang, A. Raj, M.F. Balcan, and L. Song,\n                      Scalable kernel methods via doubly stochastic gradients\n                      , Advances in Neural Information Processing Systems 27 (NIPS 2014)."},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/s00211-010-0331-6"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"G. Fung and O. L. Mangasarian,\n                      Proximal support vector machine classifiers\n                      , in Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2001.","DOI":"10.1145\/502512.502527"},{"key":"atypb19","first-page":"567","volume":"28","author":"Gittens A.","year":"2013","journal-title":"GA"},{"key":"atypb20","first-page":"19","volume":"32","author":"Hamid R.","year":"2014","journal-title":"China"},{"key":"atypb21","first-page":"205","author":"Huang P.","year":"2014","journal-title":"Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP)"},{"key":"atypb22","first-page":"981","volume":"13","author":"Kumar S.","year":"2012","journal-title":"J. Mach. Learn. Res."},{"key":"atypb23","unstructured":"Z. Lu, A. May, K. Liu, A. Bagheri Garakani, D. Guo, A. Bellet, L. Fan, M. Collins, B. Kingsbury, M. Picheny, and F. Sha,\n                      How to Scale Up Kernel Methods to Be as Good as Deep Neural Nets\n                      , ArXiv e-prints, 2014,https:\/\/arxiv.org\/abs\/1411.4000."},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1137\/120866580"},{"key":"atypb25","unstructured":"V. I. Morariu, B. V. Srinivasan, V. C. Raykar, R. Duraiswami, and L. S. Davis,\n                      Automatic online tuning for fast Gaussian summation\n                      , Advances in Neural Information Processing Systems 21 (NIPS 2008)."},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1145\/2493252.2493254"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1145\/2427023.2427030"},{"key":"atypb28","unstructured":"A. Rahimi and B. Recht,\n                      Random features for large-scale kernel machines\n                      , Advances in Neural Information Processing Systems 20 (NIPS 2007)."},{"key":"atypb29","unstructured":"V. C. Raykar and R. Duraiswami,\n                      Fast large scale Gaussian process regression using approximate matrix-vector products\n                      , in Proceedings of the Learning workshop, 2007."},{"key":"atypb30","unstructured":"C. Saunders, A. Gammerman, and V. Vovk,\n                      Ridge regression learning algorithm in dual variables\n                      , in Proceedings of the 15th International Conference on Machine Learning (ICML), Madison, WI, (1998), pp. 515-521."},{"key":"atypb31","unstructured":"J. R. Shewchuk,\n                      An Introduction to the Conjugate Gradient Method Without the Agonizing Pain\n                      , Technical report, Carnegie Mellon University, Pittsburgh, PA, 1994."},{"key":"atypb32","unstructured":"B. V. Srinivasan, Q. Hu, N. A. Gumerov, R. Murtugudde, and R. Duraiswami,\n                      Preconditioned Krylov solvers for kernel regression\n                      , ArXiv e-prints, 2014,http:\/\/arxiv.org\/abs\/1408.1237."},{"key":"atypb33","unstructured":"S. Tu, R. Roelofs, S. Venkataraman, and B. Recht,\n                      Large scale kernel learning using block coordinate descent\n                      , ArXiv e-prints, 2016,http:\/\/arxiv.org\/abs\/1602.05310."},{"key":"atypb34","unstructured":"C. K. I. Williams and M. Seeger,\n                      Using the Nystr\u00f6m method to speed up kernel machines\n                      , Advances in Neural Information Processing Systems 13 (NIPS 2000)."},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1561\/0400000060"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2015.2494219"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1214\/16-AOS1472"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1162\/0899766054323008"}],"container-title":["SIAM Journal on Matrix Analysis and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/16M1105396","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:10:49Z","timestamp":1787325049000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M1105396"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1]]},"references-count":38,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["10.1137\/16M1105396"],"URL":"https:\/\/doi.org\/10.1137\/16m1105396","relation":{},"ISSN":["0895-4798","1095-7162"],"issn-type":[{"value":"0895-4798","type":"print"},{"value":"1095-7162","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,1]]}}}