A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
Nyström subsampling with Tikhonov regularization for covariate shift adaptation under misspecified case
We study Nyström type subsampling approaches to large scale kernel methods, and prove learning bounds in the statistical learning setting, where random sampling and high probability estimates are considered. In particular, we prove that these approaches can achieve optimal learning bounds, provided the subsampling leve…
This paper studies a Nyström type subsampling approach to large kernel learning methods in the misspecified case, where the target function is not assumed to belong to the reproducing kernel Hilbert space generated by the underlying kernel. This case is less understood, in spite of its practical importance. To model su…
In the setting of nonparametric regression, we propose and study a combination of stochastic gradient methods with Nyström subsampling, allowing multiple passes over the data and mini-batches. Generalization error bounds for the studied algorithm are provided. Particularly, optimal learning rates are derived considerin…
Nyström approximation for scalable operator learning
In this paper, we study random subsampling of Gaussian process regression, one of the simplest approximation baselines, from a theoretical perspective. Although subsampling discards a large part of training data, we show provable guarantees on the accuracy of the predictive mean/variance and its generalization ability.…
Efficiently approximates kernel mean embeddings using Nyström method.
Efficient tensor kernel method reduces memory usage and computational cost for sparse regression.
Simulating the time-evolution of quantum mechanical systems is BQP-hard and expected to be one of the foremost applications of quantum computers. We consider classical algorithms for the approximation of Hamiltonian dynamics using subsampling methods from randomized numerical linear algebra. We derive a simulation tech…
We propose and study kernel conjugate gradient methods (KCGM) with random projections for least-squares regression over a separable Hilbert space. Considering two types of random projections generated by randomized sketches and Nyström subsampling, we prove optimal statistical results with respect to variants of norms …
Boosting Nyström improves accuracy of matrix approximations.
Stochastic gradient descent optimizes Nyström samples for kernel matrix approximation.
Paper analyzes Nyström regularization for time series forecasting with sequential sub-sampling.
New method circumvents curse of dimensionality in Laplacian estimation.
Derives kernel PCA with Nyström method for scalability.
Improved Nyström approximation for kernel quadrature with theoretical guarantees.
This paper proposes a new Nystrom-based clustering algorithm for large-scale data.
In recent years, the spectral analysis of appropriately defined kernel matrices has emerged as a principled way to extract the low-dimensional structure often prevalent in high-dimensional data. Here we provide an introduction to spectral methods for linear and nonlinear dimension reduction, emphasizing ways to overcom…
Nyström KPCA balances computational efficiency and statistical accuracy.
The Nystrom method is a popular technique that uses a small number of landmark points to compute a fixed-rank approximation of large kernel matrices that arise in machine learning problems. In practice, to ensure high quality approximations, the number of landmark points is chosen to be greater than the target rank. Ho…
Kernel -means clustering can correctly identify and extract a far more varied collection of cluster structures than the linear -means clustering algorithm. However, kernel -means clustering is computationally expensive when the non-linear feature map is high-dimensional and there are many input points. Kernel …
Clarifies connections between Nyström and SVGP methods for scalable GPs.
Paper uses Koopman operator and Nyström method for efficient nonlinear control.
Method uses NMF for clustering with partial distance measurements.
This paper tackles scalability issues in kernel logistic regression for large datasets.
The Nyström methods have been popular techniques for scalable kernel based learning. They approximate explicit, low-dimensional feature mappings for kernel functions from the pairwise comparisons with the training data. However, Nyström methods are generally applied without the supervision provided by the training labe…
We develop an improved bound for the approximation error of the Nyström method under the assumption that there is a large eigengap in the spectrum of kernel matrix. This is based on the empirical observation that the eigengap has a significant impact on the approximation error of the Nyström method. Our approach is bas…
Paper proposes Nyström sketches for better adaptive compressive learning.
This paper improves spectral clustering for large datasets using the Nystrom method.
The Nyström method improves learning efficiency for convex losses.
We give the first algorithm for kernel Nyström approximation that runs in *linear time in the number of training points* and is provably accurate for all kernel matrices, without dependence on regularity or incoherence conditions. The algorithm projects the kernel onto a set of landmark points sampled by their *rid…
Nystrom approximation speeds up kernel model training.
The Nystrom method is an efficient technique used to speed up large-scale learning applications by generating low-rank approximations. Crucial to the performance of this technique is the assumption that a matrix can be well approximated by working exclusively with a subset of its columns. In this work we relate this as…
The Nystrom method has been popular for generating the low-rank approximation of kernel matrices that arise in many machine learning problems. The approximation quality of the Nystrom method depends crucially on the number of selected landmark points and the selection procedure. In this paper, we present a novel algori…
The abstract presents a new theorem using Ross-Witt Nyström correspondence and Berndtsson's theorem.
Two algorithms estimate Wasserstein distance matrices from few entries for manifold learning.
Incremental versions of batch algorithms are often desired, for increased time efficiency in the streaming data setting, or increased memory efficiency in general. In this paper we present a novel algorithm for incremental kernel PCA, based on rank one updates to the eigendecomposition of the kernel matrix, which is mo…
Improved KSD test for faster GoF testing.
Efficiently tests two distributions using Nyström approximation of MMD.
New methods improve efficiency of sampling algorithms for complex systems.
A new method selects a representative subsample for efficient kernel density estimation.
In this paper we demonstrate that tempering Markov chain Monte Carlo samplers for Bayesian models by recursively subsampling observations without replacement can improve the performance of baseline samplers in terms of effective sample size per computation. We present two tempering by subsampling algorithms, subsampled…
Paper improves clustering risk bounds for kernel k-means.
Kernel methods have achieved very good performance on large scale regression and classification problems, by using the Nyström method and preconditioning techniques. The Nyström approximation -- based on a subset of landmarks -- gives a low rank approximation of the kernel matrix, and is known to provide a form of impl…
This paper optimizes subsampling for large datasets using Poisson distribution.
SQUEAK reduces space complexity for Nystrom approximations in KRR.
Skyformer uses Gaussian kernel and Nyström method to speed up self-attention in transformers.
Improved kernel Stein discrepancy for large-scale data.