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,…
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 matrices”
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.
In recent years, structured matrix recovery problems have gained considerable attention for its real world applications, such as recommender systems and computer vision. Much of the existing work has focused on matrices with low-rank structure, and limited progress has been made matrices with other types of structure. …
Biclustering structures in data matrices were first formalized in a seminal paper by John Hartigan (1972) where one seeks to cluster cases and variables simultaneously. Such structures are also prevalent in block modeling of networks. In this paper, we develop a unified theory for the estimation and completion of matri…
We consider the estimation of large covariance and precision matrices from high-dimensional sub-Gaussian or heavier-tailed observations with slowly decaying temporal dependence. The temporal dependence is allowed to be long-range so with longer memory than those considered in the current literature. We show that severa…
Algorithm estimates top k eigenvectors of shared covariance matrices while preserving privacy.
problem Differentially private PCA with adaptive noise for arbitrary k.
method Iterative algorithm with adaptive noise reduction.
result First algorithm for estimating top k eigenvectors with near-optimal statistical 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.
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.
We study the accuracy of estimating the covariance and the precision matrix of a -variate sub-Gaussian distribution along a prescribed subspace or direction using the finite sample covariance. Our results show that the estimation accuracy depends almost exclusively on the components of the distribution that correspo…
Independent Component Analysis (ICA) is a technique for unsupervised exploration of multi-channel data widely used in observational sciences. In its classical form, ICA relies on modeling the data as a linear mixture of non-Gaussian independent sources. The problem can be seen as a likelihood maximization problem. We i…
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…
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…
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}\).
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, …
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.
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.
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.
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.
The paper improves clustering algorithms for noisy data samples.
problem Clustering small data samples from mixtures of sub-gaussian distributions.
method Semidefinite programming relaxations and debiasing for MAXCUT-based clustering.
result The misclassification error decays exponentially with SNR for SDP1 and BalancedSDP.
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.
Study non-parametric frequency-domain system identification from finite samples.
problem Frequency-domain system identification from limited data.
method Empirical Transfer Function Estimate (ETFE) under sub-Gaussian colored noise and stability assumptions.
result ETFE estimates are concentrated around true values with a finite-sample rate of for all frequencies in the norm.
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.
Thompson Sampling bounds for contextual bandits with sub-Gaussian rewards.
problem Improving the performance of Thompson Sampling in contextual bandits with sub-Gaussian rewards.
method Proved comprehensive bounds on Thompson Sampling expected cumulative regret based on mutual information and lifted information ratio for sub-Gaussian rewards.
result Explicit regret bounds for various contextual bandit scenarios.
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.
Low-Rank Thinningstat.ML
New method reduces summary points for datasets while maintaining quality.
problem Thinning datasets to reduce summary points while maintaining quality.
method Low-rank analysis of sub-Gaussian thinning.
result Guarantees high-quality compression for any distribution and kernel.
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.
Proposes a new model for clustering with heavier tails.
problem Clustering with heavy-tailed data.
method Finite mixture of skewed sub-Gaussian stable distributions, maximum likelihood estimation, EM algorithm.
result The proposed model can robustly handle heavy-tailed data.
New study shows mean estimation algorithms can't beat sub-Gaussian rate in general.
problem Improving mean estimation beyond worst-case scenarios.
method Constructing counterexamples and introducing neighborhood optimality.
result No reasonable estimator can achieve better than sub-Gaussian error rate for any distribution.
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.
Nonparametric Thompson Sampling achieves optimal regret for risk-averse bandits with sub-Gaussian rewards.
problem Optimizing risk-averse bandit problems with sub-Gaussian rewards.
method Anchor-free nonparametric Thompson Sampling algorithm .
result Achieves regret matching the instance-dependent lower bound to leading order in .
We study the concentration of random kernel matrices around their mean. We derive nonasymptotic exponential concentration inequalities for Lipschitz kernels assuming that the data points are independent draws from a class of multivariate distributions on , including the strongly log-concave distributions u…
The paper proves a regret bound for a sub-Gaussian mixture on unbounded data.
problem Tackles the challenge of achieving regret bounds for sub-Gaussian mixtures on unbounded data.
method Uses path-wise (deterministic) regret bounds and a cumulative variance process to derive the bound.
result Shows that on a specific event, the regret is eventually bounded by ln(ln V_T).
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…
Two new algorithms improve robust PCA and Schatten packing.
problem Robustly estimating the top eigenvector of corrupted sub-Gaussian data.
method Two iterative filtering and nearly-linear time algorithms.
result First polynomial-time algorithms for non-trivial covariance estimation.
Paper analyzes SGMs for learning sub-Gaussian distributions without dimensionality constraints.
problem Learning sub-Gaussian distributions in high dimensions with SGMs.
method Introduced complexity notion and proved approximation and generalization rates.
result SGMs can approximate target sub-Gaussian distributions in total variation with dimension-independent rate.
SVGD algorithm converges at rate 1/sqrt(log log n) for sub-Gaussian distributions.
problem Approximating a probability distribution with particles.
method Stein variational gradient descent (SVGD) with finite particles and sub-Gaussian target distribution.
result SVGD achieves a convergence rate of 1/sqrt(log log n) for sub-Gaussian distributions.
New bounds for KRR condition number reveal overfitting phenomena.
problem Characterizing overfitting in KRR with varying kernel spectral decay.
method Derived new bounds for kernel matrices, enhanced test error bounds, and identified feature independence role.
result Identified tempered and catastrophic overfitting phenomena.
Fundamental Bias in Inverting Random Sampling Matrices with Application to Sub-sampled Newtonmath.NA
Corrects bias in random sampling matrices for improved ML methods.
problem Inversion bias in random sampling matrices hampers ML applications.
method Corrects inversion bias for various random sampling methods.
result Establishes local convergence rates for sub-sampled Newton methods.
New algorithms for efficient learning with long-term rewards in contextual bandits.
problem Efficient learning with long-term rewards in contextual bandits.
method Proposes new algorithms leveraging sparsity to discover dependence patterns and arm parameters.
result Regret upper bounds for data-poor and data-rich regimes, showing improved sample complexity.
Paper improves SLCB regret bound for bounded noise.
problem Stochastic linear contextual bandits with bounded noise.
method Set-membership estimation (SME) and optimism in the face of uncertainty (OFU).
result Improved regret bound of .
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…
Improved median of means estimator with tighter bounds.
problem Improving the efficiency and reliability of median of means estimator.
method Modification of the median of means estimator with sub-Gaussian deviation bounds.
result Achieves nearly optimal constants under minimal assumptions.
Flexible model captures varying scales in data clusters.
problem Real-world data often exhibits varying scales or intensities, violating the homogeneity assumption of classical Gaussian mixture models.
method Individual-heterogeneous sub-Gaussian mixture model with an efficient spectral method for exact recovery.
result The method provably achieves exact recovery of true cluster labels under mild separation conditions.
Study shows how over-parameterized classifiers can still perform well on noisy data.
problem Understanding how maximum margin classifiers perform in over-parameterized settings with noisy data.
method Analyzes maximum margin classifiers on sub-Gaussian mixtures, providing risk bounds.
result Characterizes conditions for 'benign overfitting' in linear classification problems.
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
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 characterization limits sampling with inexact scores.
problem Limiting sampling with inexact scores for unbiased results.
method Characterized types of inexact score oracle access.
result Weaker error assumptions rule out tractability of unbiased sampling.
Inspired by the Reward-Biased Maximum Likelihood Estimate method of adaptive control, we propose RBMLE -- a novel family of learning algorithms for stochastic multi-armed bandits (SMABs). For a broad range of SMABs including both the parametric Exponential Family as well as the non-parametric sub-Gaussian/Exponential f…