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
- Conditionally valid Probabilistic Conformal Prediction [57.80927226809277]
We develop a new method for creating prediction sets that combines the flexibility of conformal methods with an estimate of the conditional distribution.
We demonstrate the effectiveness of our approach through extensive simulations, showing that it outperforms existing methods in terms of conditional coverage.
arXiv Detail & Related papers (2024-07-01T20:44:48Z) - Online Learning Approach for Survival Analysis [1.0499611180329806]
We introduce an online mathematical framework for survival analysis, allowing real time adaptation to dynamic environments and censored data.
This framework enables the estimation of event time distributions through an optimal second order online convex optimization algorithm-Online Newton Step (ONS)
arXiv Detail & Related papers (2024-02-07T08:15:30Z) - 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) - 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) - Private Robust Estimation by Stabilizing Convex Relaxations [22.513117502159922]
$(epsilon, delta)$-differentially private (DP)
$(epsilon, delta)$-differentially private (DP)
$(epsilon, delta)$-differentially private (DP)
arXiv Detail & Related papers (2021-12-07T07:47:37Z) - Privacy Preserving Recalibration under Domain Shift [119.21243107946555]
We introduce a framework that abstracts out the properties of recalibration problems under differential privacy constraints.
We also design a novel recalibration algorithm, accuracy temperature scaling, that outperforms prior work on private datasets.
arXiv Detail & Related papers (2020-08-21T18:43:37Z) - 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) - Improved guarantees and a multiple-descent curve for Column Subset
Selection and the Nystr\"om method [76.73096213472897]
We develop techniques which exploit spectral properties of the data matrix to obtain improved approximation guarantees.
Our approach leads to significantly better bounds for datasets with known rates of singular value decay.
We show that both our improved bounds and the multiple-descent curve can be observed on real datasets simply by varying the RBF parameter.
arXiv Detail & Related papers (2020-02-21T00:43:06Z)
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.