We study the problem of estimating the mean of a random vector given a sample of independent, identically distributed points. We introduce a new estimator that achieves a purely sub-Gaussian performance under the only condition that the second moment of exists. The estimator is based on a novel concept of a…
On-device research index
arXiv research
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.
168,657 papers · 148 categories
Trend · papers per month
48 results for “sub-Gaussian random vectors”
We develop time-uniform confidence spheres for estimating means of random vectors.
problem Sequential mean estimation in high-dimensional spaces.
method Derive time-uniform confidence sphere sequences (CSSs) for various types of random vectors.
result Optimal CSSs for log-concave, sub-Gaussian, and sub- random vectors.
Sparse neural encoding can store more memories as targets become sparser.
problem Storing sparse input-target associations in neural networks.
method Mathematical proofs using properties of random polytopes and sub-gaussian random vector variables.
result The capacity of neural maps increases with sparsity in target layers.
Study on using random subspaces for ERM with various loss functions.
problem Improving learning accuracy with computational savings from random subspaces.
method Random subspaces of a hypothesis space, considering data-dependent subspaces.
result Unified analysis showing computational efficiency can be improved without performance loss.
Study improves self-normalized bounds for vector-valued processes beyond sub-Gaussianity.
problem Limited understanding of self-normalized concentration for vector-valued processes outside sub-Gaussian frameworks.
method Developed concentration inequalities for self-normalized processes with light tails (e.g., Bennett, Bernstein bounds) for vector-valued data.
result Provided new insights and bounds for self-normalized processes with non-sub-Gaussian distributions.
We improve bounds for stochastic processes, especially those with heavy tails.
problem Bounding the concentration of sub- processes with heavy tails.
method Variational approach to concentration, focusing on sub-Gaussian and other tail conditions.
result First dimension-free self-normalized empirical Bernstein inequality.
Proves new concentration inequalities for sub-gaussian and sub-exponential variables.
problem Understanding functions of independent random variables better.
method Sub-gaussian and sub-exponential conditions, Rademacher complexities, Lipschitz function classes.
result Extension of Rademacher complexities to unbounded sub-exponential distributions.
We propose an estimator for the mean of a random vector in that can be computed in time for i.i.d.~samples and that has error bounds matching the sub-Gaussian case. The only assumptions we make about the data distribution are that it has finite mean and covariance; in particular, we mak…
Sharp comparison for sub-Gaussian random variables in convex order.
problem Comparing sub-Gaussian random variables in convex order.
method Proving dominance using moment generating functions and convex functions.
result Sharp comparison established between specific sub-Gaussian random variables.
Random linear mappings are widely used in modern signal processing, compressed sensing and machine learning. These mappings may be used to embed the data into a significantly lower dimension while at the same time preserving useful information. This is done by approximately preserving the distances between data points,…
Algorithmic Gaussianization through Sketching: Converting Data into Sub-gaussian Random Designscs.LG
New algorithm converts data into sub-gaussian designs efficiently.
problem Efficiently converting large datasets into sub-gaussian random designs for robust performance.
method Algorithmic Gaussianization through sketching and averaging, using LESS embeddings.
result Efficient data sketches nearly indistinguishable from sub-gaussian designs.
Quantum algorithm estimates mean with sub-Gaussian error.
problem Estimating mean of quantum-computed random variables.
method Quantum mean estimation algorithm with sub-Gaussian error rate.
result Achieves nearly-optimal quadratic speedup over classical methods.
Andreas Maurer in the paper "A vector-contraction inequality for Rademacher complexities" extended the contraction inequality for Rademacher averages to Lipschitz functions with vector-valued domains; He did it replacing the Rademacher variables in the bounding expression by arbitrary idd symmetric and sub-gaussian var…
The paper provides a method to minimize regret in estimate-then-optimize decision-making.
problem Errors in estimation lead to sub-optimal decisions in data-driven decision-making.
method A novel bound on regret for smooth and unconstrained optimization problems, followed by experimental design to minimize this regret.
result A general procedure for experimental design to minimize regret resulting from estimate-then-optimize.
Concentration inequalities form an essential toolkit in the study of high dimensional (HD) statistical methods. Most of the relevant statistics literature in this regard is based on sub-Gaussian or sub-exponential tail assumptions. In this paper, we first bring together various probabilistic inequalities for sums of in…
Several important families of computational and statistical results in machine learning and randomized algorithms rely on uniform bounds on quadratic forms of random vectors or matrices. Such results include the Johnson-Lindenstrauss (J-L) Lemma, the Restricted Isometry Property (RIP), randomized sketching algorithms, …
We study the algorithmic problem of estimating the mean of heavy-tailed random vector in , given i.i.d. samples. The goal is to design an efficient estimator that attains the optimal sub-gaussian error bound, only assuming that the random vector has bounded mean and covariance. Polynomial-time solutio…
We tackle the problem of estimating a location parameter with differential privacy guarantees and sub-Gaussian deviations. Recent work in statistics has focused on the study of estimators that achieve sub-Gaussian type deviations even for heavy tailed data. We revisit some of these estimators through the lens of differ…
Estimates sub-Gaussian parameter with consistent and optimal rates.
problem Estimating sub-Gaussian parameter from random variables.
method Constrained maximization of empirical weighted cumulant generating function.
result Root-n rate estimator is consistent and optimal under certain conditions.
Sharp concentration inequalities for sub-Orlicz random variables with phase transition at α=2.
problem Developing concentration inequalities for sub-Orlicz random variables with phase transition.
method New theoretical analysis framework involving variance and min/max functions of Orlicz tails.
result Sharp concentration inequalities with phase transition at α=2 for sub-Orlicz random variables.
We extend Kac-Rice formula to compute expected intersections of random submanifolds.
problem Computing expected intersections of random submanifolds.
method Generalized Kac-Rice formula using measure theory and integration.
result Formula computes expected cardinality of preimages of submanifolds via random maps.
RS-NSGD improves SGD convergence for heavy-tailed noise.
problem Nonconvex optimization with heavy-tailed noise.
method Integrates direction normalization into subspace updates.
result Achieves better oracle complexity than full-dimensional normalized SGD.
The paper tackles resource allocation for arms with unknown and random rewards, achieving optimal regret bounds.
problem Allocating resources on arms with unknown and random rewards.
method Developed two algorithms with optimal regret bounds for , demonstrating a phase transition at .
result Achieved optimal gap-dependent and gap-independent regret bounds for .
New estimator accurately estimates mean of real-valued distributions without variance knowledge.
problem Estimating the mean of real-valued distributions without prior variance knowledge.
method Introduces a novel estimator that converges sub-Gaussian and works across distributions with bounded variance.
result The estimator achieves accuracy of σ·(1+o(1))√(2log(1/δ)/n) with parameters n, δ, and σ².
The contraction inequality for Rademacher averages is extended to Lipschitz functions with vector-valued domains, and it is also shown that in the bounding expression the Rademacher variables can be replaced by arbitrary iid symmetric and sub-gaussian variables. Example applications are given for multi-category learnin…
New winsorized mean improves robustness to up to 50% contamination.
problem Improving robustness of mean estimation in the presence of outliers.
method Outlyingness-induced winsorized mean approach.
result Achieves up to 50% contamination robustness with sub-Gaussian performance.
This paper extends the standard chaining technique to prove excess risk upper bounds for empirical risk minimization with random design settings even if the magnitude of the noise and the estimates is unbounded. The bound applies to many loss functions besides the squared loss, and scales only with the sub-Gaussian or …
Efficiently estimates covariance for sub-Weibull vectors with sub-Gaussian rate.
problem Outliers in high-dimensional covariance estimation.
method Cross-Fitted Norm-Truncated Estimator for Sub-Weibull distributions.
result Achieves optimal sub-Gaussian rate with operations.
New method estimates gradients accurately with sharp bounds.
problem Accurate gradient estimation in regression problems.
method Nearest-neighbor based pointwise estimate of gradients.
result Sharp nonasymptotic bounds for gradient estimation.
We propose robust sparse reduced rank regression for analyzing large and complex high-dimensional data with heavy-tailed random noise. The proposed method is based on a convex relaxation of a rank- and sparsity-constrained non-convex optimization problem, which is then solved using the alternating direction method of m…
One-bit clustering method for two-component sub-Gaussian mixture models
problem Clustering in sub-Gaussian mixture models
method One-bit clustering using dithered quantization
result Decaying misclassification rate with exponential signal-to-noise ratio
Random projection (RP) is a classical technique for reducing storage and computational costs. We analyze RP-based approximations of convex programs, in which the original optimization problem is approximated by the solution of a lower-dimensional problem. Such dimensionality reduction is essential in computation-limite…
New concentration inequalities for tensors with heavy-tailed coefficients.
problem Developing bounds for Euclidean functions of tensors with sub-Weibull distributions.
method Extending concentration inequalities to sub-Weibull random tensors, using new inequalities for heavy-tailed random variables and martingale analysis.
result Established a phase transition between sub-gaussian and heavy-tailed regimes for Euclidean functions of tensors.
New method tightens sub-Gaussian concentration inequalities.
problem Estimating variance-type parameters of sub-Gaussian distributions.
method Using sub-Gaussian intrinsic moment norm to maximize normalized moments.
result Provides tighter sub-Gaussian concentration inequalities.
The paper strengthens the classical result of MLE convergence to a Gaussian distribution.
problem The classical result of MLE convergence to a Gaussian distribution.
method Sub-Gaussian concentration and entropic normality of the normalized MLE.
result Entropic central limit theorem for a smoothed version of the estimator.
LinMED is a new linear bandit algorithm with near-optimal regret bound.
problem Optimizing decision-making in linear bandit problems with sub-Gaussian distributions.
method LinMED is a randomized linear bandit algorithm with closed-form arm sampling probabilities.
result LinMED achieves a near-optimal regret bound of up to logarithmic factors.
Vector approximate message passing (VAMP) is a computationally simple approach to the recovery of a signal from noisy linear measurements . Like the AMP proposed by Donoho, Maleki, and Montanari in 2009, VAMP is characterized by a rigorous state evolution (SE) that holds …
A novel algorithm minimizes regret in a multi-agent bandit problem with time-varying random graphs and heterogeneous rewards.
problem Minimizing regret in a multi-agent multi-armed bandit problem with time-varying random graphs and heterogeneous rewards.
method Introduces a novel algorithmic framework combining averaging-based consensus with a weighting technique and upper confidence bound.
result Derives optimal instance-dependent regret upper bounds of order in both sub-gaussian and sub-exponential environments.
Paper proposes robust compressed sensing using generative models.
problem Estimating high-dimensional vectors from noisy linear equations with heavy-tailed or outlier data.
method Inspired by Median-of-Means (MOM), proposes an algorithm for robust recovery.
result Guarantees recovery for heavy-tailed data, even in the presence of outliers.
Improved concentration inequalities for sub-Weibull variables enhance statistical and machine learning applications.
problem Improving concentration inequalities for sub-Weibull random variables.
method Developed new concentration inequalities for sums of independent sub-Weibull random variables, including a new sub-Weibull parameter.
result New concentration inequalities with sharper constants and a mixture of sub-Gaussian and sub-Weibull tails.
New error bounds for noisy phase retrieval problems using empirical risk minimization.
problem Estimating signals in noisy phase retrieval problems.
method Empirical risk minimization (ERM) with new error bounds for different noise patterns.
result Established new error bounds for NPR and NGPR, showing improved performance under various noise conditions.
Heavy-tailed distributions are widely used in robust mixture modelling due to possessing thick tails. As a computationally tractable subclass of the stable distributions, sub-Gaussian -stable distribution received much interest in the literature. Here, we introduce a type of expectation maximization algorithm that e…
In this paper, we study the problem of recovering a group sparse vector from a small number of linear measurements. In the past the common approach has been to use various "group sparsity-inducing" norms such as the Group LASSO norm for this purpose. By using the theory of convex relaxations, we show that it is also po…
Estimation of the covariance matrix has attracted a lot of attention of the statistical research community over the years, partially due to important applications such as Principal Component Analysis. However, frequently used empirical covariance estimator (and its modifications) is very sensitive to outliers in the da…
Sharp sub-Gaussian upper bounds for subsolutions of Trudinger's equation on Riemannian manifoldsmath.AP
Sharp sub-Gaussian bounds for subsolutions of Trudinger's equation on Riemannian manifolds.
problem Bounding weak subsolutions of Trudinger's equation on Riemannian manifolds.
method Proving sub-Gaussian upper bounds for weak subsolutions.
result The upper bounds are sharp for specific classes of manifolds, including \(\mathbb{R}^{n}\).
UCB algorithm adapted for large-scale, non-sub-Gaussian problems.
problem Selecting the best alternative from a large set of options with non-sub-Gaussian performance distributions.
method Adapted UCB algorithm for non-sub-Gaussian settings, focusing on sample size and meta-UCB selection.
result UCB algorithms can achieve sample optimality in large-scale, non-sub-Gaussian problems.
A new method reduces the bias in estimating inverse covariance matrices from sketches.
problem Reducing the bias in estimating inverse covariance matrices from sketches.
method Developed a framework for analyzing inversion bias and proposed a new sketching technique called LEverage Score Sparsified (LESS) embeddings.
result The new sketching technique reduces the inversion bias to for , significantly smaller than the approximation error.
Recovering structured signals from noisy measurements with a novel matrix model.
problem Recovering structured signals from noisy linear observations with a non-standard measurement matrix.
method Proves approximate empirical risk minimizer is a robust estimator under certain conditions.
result Effective rank of measurement matrix can serve as a surrogate for number of measurements.