Accumulations of Projections--A Unified Framework for Random Sketches in
Kernel Ridge Regression
- URL: http://arxiv.org/abs/2103.04031v1
- Date: Sat, 6 Mar 2021 05:02:17 GMT
- Title: Accumulations of Projections--A Unified Framework for Random Sketches in
Kernel Ridge Regression
- Authors: Yifan Chen, Yun Yang
- Abstract summary: Building a sketch of an n-by-n empirical kernel matrix is a common approach to accelerate the computation of many kernel methods.
We propose a unified framework of constructing sketching methods in kernel ridge regression.
- Score: 12.258887270632869
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: 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\"om 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.
Related papers
- Stochastic Gradient Descent for Gaussian Processes Done Right [86.83678041846971]
We show that when emphdone right -- by which we mean using specific insights from optimisation and kernel communities -- gradient descent is highly effective.
We introduce a emphstochastic dual descent algorithm, explain its design in an intuitive manner and illustrate the design choices.
Our method places Gaussian process regression on par with state-of-the-art graph neural networks for molecular binding affinity prediction.
arXiv Detail & Related papers (2023-10-31T16:15:13Z) - Sharp Analysis of Sketch-and-Project Methods via a Connection to
Randomized Singular Value Decomposition [14.453949553412821]
We develop a theoretical framework for obtaining sharp guarantees on the convergence rate of sketch-and-project methods.
We show that the convergence rate improves at least linearly with the sketch size, and even faster when the data matrix exhibits certain spectral decays.
Our experiments support the theory and demonstrate that even extremely sparse sketches exhibit the convergence properties predicted by our framework.
arXiv Detail & Related papers (2022-08-20T03:11:13Z) - Algorithmic Gaussianization through Sketching: Converting Data into
Sub-gaussian Random Designs [22.925108493465363]
We provide an algorithmic framework for gaussianizing data distributions via averaging.
We show that it is possible to efficiently construct data sketches that are nearly indistinguishable from sub-gaussian random designs.
arXiv Detail & Related papers (2022-06-21T12:16:45Z) - Distributed Sketching for Randomized Optimization: Exact
Characterization, Concentration and Lower Bounds [54.51566432934556]
We consider distributed optimization methods for problems where forming the Hessian is computationally challenging.
We leverage randomized sketches for reducing the problem dimensions as well as preserving privacy and improving straggler resilience in asynchronous distributed systems.
arXiv Detail & Related papers (2022-03-18T05:49:13Z) - Newton-LESS: Sparsification without Trade-offs for the Sketched Newton
Update [88.73437209862891]
In second-order optimization, a potential bottleneck can be computing the Hessian matrix of the optimized function at every iteration.
We show that the Gaussian sketching matrix can be drastically sparsified, significantly reducing the computational cost of sketching.
We prove that Newton-LESS enjoys nearly the same problem-independent local convergence rate as Gaussian embeddings.
arXiv Detail & Related papers (2021-07-15T17:33:05Z) - Learning-Augmented Sketches for Hessians [54.97773807211337]
We show how to design learned sketches for the Hessian in the context of second order methods.
We show empirically that learned sketches, compared with their "non-learned" counterparts, improve the approximation accuracy for important problems.
arXiv Detail & Related papers (2021-02-24T14:50:59Z) - Learning the Positions in CountSketch [51.15935547615698]
We consider sketching algorithms which first compress data by multiplication with a random sketch matrix, and then apply the sketch to quickly solve an optimization problem.
In this work we propose the first learning algorithm that also optimize the locations of the non-zero entries.
We show this algorithm gives better accuracy for low rank approximation than previous work, and apply it to other problems such as $k$-means clustering for the first time.
arXiv Detail & Related papers (2020-07-20T05:06:29Z) - Distributed Sketching Methods for Privacy Preserving Regression [54.51566432934556]
We leverage randomized sketches for reducing the problem dimensions as well as preserving privacy and improving straggler resilience in asynchronous distributed systems.
We derive novel approximation guarantees for classical sketching methods and analyze the accuracy of parameter averaging for distributed sketches.
We illustrate the performance of distributed sketches in a serverless computing platform with large scale experiments.
arXiv Detail & Related papers (2020-02-16T08:35:48Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.