Robust and Provable Guarantees for Sparse Random Embeddings
- URL: http://arxiv.org/abs/2202.10815v1
- Date: Tue, 22 Feb 2022 11:15:59 GMT
- Title: Robust and Provable Guarantees for Sparse Random Embeddings
- Authors: Maciej Skorski, Alessandro Temperoni, Martin Theobald
- Abstract summary: We improve upon the guarantees for sparse random embeddings provided by Freksen at al. (NIPS'18) and Jagadeesan (NIPS'18)
We show that (a) our bounds are explicit as opposed to the guarantees provided previously, and (b) our bounds are guaranteed to be sharper by practically significant constants.
We empirically demonstrate that our bounds significantly outperform prior works on a wide range of real-world datasets.
- Score: 72.24615341588846
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this work, we improve upon the guarantees for sparse random embeddings, as
they were recently provided and analyzed by Freksen at al. (NIPS'18) and
Jagadeesan (NIPS'19). Specifically, we show that (a) our bounds are explicit as
opposed to the asymptotic guarantees provided previously, and (b) our bounds
are guaranteed to be sharper by practically significant constants across a wide
range of parameters, including the dimensionality, sparsity and dispersion of
the data. Moreover, we empirically demonstrate that our bounds significantly
outperform prior works on a wide range of real-world datasets, such as
collections of images, text documents represented as bags-of-words, and text
sequences vectorized by neural embeddings. Behind our numerical improvements
are techniques of broader interest, which improve upon key steps of previous
analyses in terms of (c) tighter estimates for certain types of quadratic
chaos, (d) establishing extreme properties of sparse linear forms, and (e)
improvements on bounds for the estimation of sums of independent random
variables.
Related papers
- Statistical Inference for Temporal Difference Learning with Linear Function Approximation [62.69448336714418]
Temporal Difference (TD) learning, arguably the most widely used for policy evaluation, serves as a natural framework for this purpose.
In this paper, we study the consistency properties of TD learning with Polyak-Ruppert averaging and linear function approximation, and obtain three significant improvements over existing results.
arXiv Detail & Related papers (2024-10-21T15:34:44Z) - A Non-negative VAE:the Generalized Gamma Belief Network [49.970917207211556]
The gamma belief network (GBN) has demonstrated its potential for uncovering multi-layer interpretable latent representations in text data.
We introduce the generalized gamma belief network (Generalized GBN) in this paper, which extends the original linear generative model to a more expressive non-linear generative model.
We also propose an upward-downward Weibull inference network to approximate the posterior distribution of the latent variables.
arXiv Detail & Related papers (2024-08-06T18:18:37Z) - Probabilistic Conformal Prediction with Approximate Conditional Validity [81.30551968980143]
We develop a new method for generating prediction sets that combines the flexibility of conformal methods with an estimate of the conditional distribution.
Our method consistently outperforms existing approaches in terms of conditional coverage.
arXiv Detail & Related papers (2024-07-01T20:44:48Z) - Characterizing Overfitting in Kernel Ridgeless Regression Through the Eigenspectrum [6.749750044497731]
We prove the phenomena of tempered overfitting and catastrophic overfitting under the sub-Gaussian design assumption.
We also identify that the independence of the features plays an important role in guaranteeing tempered overfitting.
arXiv Detail & Related papers (2024-02-02T10:36:53Z) - Exact Non-Oblivious Performance of Rademacher Random Embeddings [79.28094304325116]
This paper revisits the performance of Rademacher random projections.
It establishes novel statistical guarantees that are numerically sharp and non-oblivious with respect to the input data.
arXiv Detail & Related papers (2023-03-21T11:45:27Z) - Conformal Frequency Estimation using Discrete Sketched Data with
Coverage for Distinct Queries [35.67445122503686]
This paper develops conformal inference methods to construct a confidence interval for the frequency of a queried object in a very large discrete data set.
We show our methods have improved empirical performance compared to existing frequentist and Bayesian alternatives in simulations.
arXiv Detail & Related papers (2022-11-09T00:05:29Z) - Efficient Private SCO for Heavy-Tailed Data via Averaged Clipping [40.69950711262191]
We consider differentially private convex optimization for heavy-tailed data with the guarantee of being differentially private (DP)
We establish new convergence results and improved complexity bounds for the proposed algorithm called AClipped-dpSGD for constrained and unconstrained convex problems.
arXiv Detail & Related papers (2022-06-27T01:39:15Z) - Differential Privacy Guarantees for Stochastic Gradient Langevin
Dynamics [2.9477900773805032]
We show that the privacy loss converges exponentially fast for smooth and strongly convex objectives under constant step size.
We propose an implementation and our experiments show the practical utility of our approach compared to classical DP-SGD libraries.
arXiv Detail & Related papers (2022-01-28T08:21:31Z) - Random extrapolation for primal-dual coordinate descent [61.55967255151027]
We introduce a randomly extrapolated primal-dual coordinate descent method that adapts to sparsity of the data matrix and the favorable structures of the objective function.
We show almost sure convergence of the sequence and optimal sublinear convergence rates for the primal-dual gap and objective values, in the general convex-concave case.
arXiv Detail & Related papers (2020-07-13T17:39:35Z)
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.