2021-03-18-chen21f.md

title	abstract	layout	series	publisher	issn	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_author	author	date	address	container-title	volume	genre	issued	pdf	extras
Accumulations of Projections—A Unified Framework for Random Sketches in Kernel Ridge Regression	Building a sketch of an n-by-n empirical kernel matrix is a common approach to accelerate the computation of many kernel methods. In this paper, we propose a unified framework of constructing sketching methods in kernel ridge regression (KRR), which views the sketching matrix S as an accumulation of m rescaled sub-sampling matrices with independent columns. Our framework incorporates two commonly used sketching methods, sub-sampling sketches (known as the Nyström method) and sub-Gaussian sketches, as special cases with m=1 and m=infinity respectively. Under the new framework, we provide a unified error analysis of sketching approximation and show that our accumulation scheme improves the low accuracy of sub-sampling sketches when certain incoherence characteristic is high, and accelerates the more accurate but computationally heavier sub-Gaussian sketches. By optimally choosing the number m of accumulations, we show that a best trade-off between computational efficiency and statistical accuracy can be achieved. In practice, the sketching method can be as efficiently implemented as the sub-sampling sketches, as only minor extra matrix additions are needed. Our empirical evaluations also demonstrate that the proposed method may attain the accuracy close to sub-Gaussian sketches, while is as efficient as sub-sampling-based sketches.	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	chen21f	0	Accumulations of Projections—A Unified Framework for Random Sketches in Kernel Ridge Regression	2953	2961	2953-2961	2953	false	Chen, Yifan and Yang, Yun	given family Yifan Chen given family Yun Yang	2021-03-18		Proceedings of The 24th International Conference on Artificial Intelligence and Statistics	130	inproceedings	date-parts 2021 3 18	http://proceedings.mlr.press/v130/chen21f/chen21f.pdf	label link Supplementary PDF http://proceedings.mlr.press/v130/chen21f/chen21f-supp.pdf