Mean Nystr\"om Embeddings for Adaptive Compressive Learning
- URL: http://arxiv.org/abs/2110.10996v1
- Date: Thu, 21 Oct 2021 09:05:58 GMT
- Title: Mean Nystr\"om Embeddings for Adaptive Compressive Learning
- Authors: Antoine Chatalic, Luigi Carratino, Ernesto De Vito, Lorenzo Rosasco
- Abstract summary: We study the idea of performing sketching based on data-dependent Nystr"om approximation.
We show for k-means clustering and Gaussian modeling that for a fixed sketch size, Nystr"om sketches indeed outperform those built with random features.
- Score: 25.89586989444021
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: Compressive learning is an approach to efficient large scale learning based
on sketching an entire dataset to a single mean embedding (the sketch), i.e. a
vector of generalized moments. The learning task is then approximately solved
as an inverse problem using an adapted parametric model. Previous works in this
context have focused on sketches obtained by averaging random features, that
while universal can be poorly adapted to the problem at hand. In this paper, we
propose and study the idea of performing sketching based on data-dependent
Nystr\"om approximation. From a theoretical perspective we prove that the
excess risk can be controlled under a geometric assumption relating the
parametric model used to learn from the sketch and the covariance operator
associated to the task at hand. Empirically, we show for k-means clustering and
Gaussian modeling that for a fixed sketch size, Nystr\"om sketches indeed
outperform those built with random features.
Related papers
- Disentangled Representation Learning with the Gromov-Monge Gap [65.73194652234848]
Learning disentangled representations from unlabelled data is a fundamental challenge in machine learning.
We introduce a novel approach to disentangled representation learning based on quadratic optimal transport.
We demonstrate the effectiveness of our approach for quantifying disentanglement across four standard benchmarks.
arXiv Detail & Related papers (2024-07-10T16:51:32Z) - Asymptotically free sketched ridge ensembles: Risks, cross-validation, and tuning [5.293069542318491]
We employ random matrix theory to establish consistency of generalized cross validation (GCV) for estimating prediction risks of sketched ridge regression ensembles.
For squared prediction risk, we provide a decomposition into an unsketched equivalent implicit ridge bias and a sketching-based variance, and prove that the risk can be globally tuning by only sketch size in infinite ensembles.
We also propose an "ensemble trick" whereby the risk for unsketched ridge regression can be efficiently estimated via GCV using small sketched ridge ensembles.
arXiv Detail & Related papers (2023-10-06T16:27:43Z) - Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
This paper proposes a flexible algorithmic framework for graph learning under low-rank structural constraints.
The problem is expressed as penalized maximum likelihood estimation of an elliptical distribution.
We leverage geometries of positive definite matrices and positive semi-definite matrices of fixed rank that are well suited to elliptical models.
arXiv Detail & Related papers (2022-10-21T13:19: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) - Asymmetric compressive learning guarantees with applications to
quantized sketches [15.814495790111323]
We present a framework to train audio event classification on large-scale datasets.
We study the relaxation where this map is allowed to be different for each phase.
We then instantiate this framework to the setting of quantized sketches, by proving that the LPD indeed holds for binary sketch contributions.
arXiv Detail & Related papers (2021-04-20T15:37:59Z) - Cloud2Curve: Generation and Vectorization of Parametric Sketches [109.02932608241227]
We present Cloud2Curve, a generative model for scalable high-resolution vector sketches.
We evaluate the generation and vectorization capabilities of our model on Quick, Draw! and KMNIST datasets.
arXiv Detail & Related papers (2021-03-29T12:09:42Z) - Accumulations of Projections--A Unified Framework for Random Sketches in
Kernel Ridge Regression [12.258887270632869]
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.
arXiv Detail & Related papers (2021-03-06T05:02:17Z) - 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) - 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.