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.
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.
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.
Extends inequality for Rademacher complexities using p-stable variables.
problem Improving Rademacher complexity bounds using p-stable variables. method Extends contraction inequality to p-stable variables for 1<p<2. result New bounds for Rademacher complexities with p-stable variables. Extended contraction inequality for Rademacher complexities to vector-valued functions.
problem Bounding Rademacher complexities for vector-valued functions.
method Extended contraction inequality for Lipschitz functions with vector-valued domains, using symmetric and sub-gaussian variables.
result Rademacher variables can be replaced by arbitrary symmetric and sub-gaussian variables in the bounding expression.
Optimizes sub-Gaussian matrices for preserving data distances.
problem Improving the performance of sub-Gaussian matrices in preserving data distances.
method Analyzes sub-Gaussian matrices and their dependence on the sub-Gaussian norm, presenting optimal bounds.
result Optimal dependence on the sub-Gaussian norm for sub-Gaussian matrices as near isometries on sets.
New private algorithms estimate location parameters with sub-Gaussian deviations.
problem Estimating location parameters with differential privacy and sub-Gaussian deviations for heavy-tailed data.
method Design two private algorithms for estimating the median and mean under differential privacy, showing sub-Gaussian deviations for unbounded random variables.
result Private median and mean estimators achieve sub-Gaussian deviations, unlike non-private counterparts which can have strictly worse deviations.
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.
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 σ².
We develop a new bound for estimating CVaR from samples of an unbounded random variable.
problem Estimating CVaR from i.i.d. samples of an unbounded random variable.
method Derive a one-sided concentration bound for a CVaR estimator.
result A novel concentration bound for CVaR estimation.
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.
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.
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.
New algorithm models data robustly with sub-Gaussian stable distributions.
problem Robust mixture modelling of heavy-tailed data.
method Expectation maximization algorithm for sub-Gaussian stable distributions.
result Sub-Gaussian stable distributions improve robustness in mixture modelling.
New estimator for mean of random vector achieves sub-Gaussian performance.
problem Estimating the mean of a random vector with sub-Gaussian performance.
method Introduces a multivariate median-based estimator under the condition of finite second moment.
result Achieves purely sub-Gaussian performance with only second moment condition.
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.
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 b∈[0,1], demonstrating a phase transition at b=1/2. result Achieved optimal gap-dependent and gap-independent regret bounds for b∈[0,1]. 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.
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.
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.
Improved Lasso estimator speeds up variable selection.
problem Efficient variable selection in high-dimensional data.
method Stability principle-based generalized debiased Lasso.
result Significantly reduces computational cost of resampling-based methods.
Faster mean estimation with sub-Gaussian error bounds.
problem Estimating the mean of a random vector with optimal statistical efficiency.
method An estimator for the mean of a random vector in R^d with optimal statistical efficiency and sub-Gaussian error bounds.
result Achieves optimal statistical efficiency with sub-Gaussian error bounds and a significantly faster runtime.
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.
Paper develops new inequalities for high-dimensional statistics under sub-Weibull tail assumptions.
problem High-dimensional statistical methods under sub-Weibull tail assumptions.
method Develops new concentration inequalities for sums of independent random variables under sub-Weibull tail assumptions.
result Concentration inequalities match asymptotics of central limit theorem and match sub-Gaussian tail behavior.
We obtain a tight distribution-specific characterization of the sample complexity of large-margin classification with L2 regularization: We introduce the margin-adapted dimension, which is a simple function of the second order statistics of the data distribution, and show distribution-specific upper and lower bounds on…
Paper proposes Sp-GD for sparse max-affine regression with theoretical guarantees.
problem Sparse max-affine regression model selection and estimation.
method Sparse Gradient Descent (Sp-GD) initialization using sparse PCA and covering search.
result Sp-GD provides ε-accurate estimates with optimal number of observations.
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.
The paper reviews and improves concentration inequalities for statistical inference.
problem Analyzing statistical inference in various settings with high-dimensional data.
method Review and improvement of concentration inequalities for different types of random variables and statistical measures.
result Fresh new results and improved bounds with sharper constants.
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.
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.
CascadeBAI identifies best arms in cascading bandits with fixed confidence.
problem Finding the best set of items in cascading bandits with limited feedback.
method Developed CascadeBAI algorithm, derived upper and lower bounds on time complexity, introduced left-sided sub-Gaussian random variables.
result CascadeBAI is optimal in some practical regimes and performs well with limited feedback.
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 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 ρext−NPTSSG. result Achieves regret matching the instance-dependent lower bound to leading order in logn. 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).
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.
Paper extends chaining technique for empirical risk minimization bounds.
problem Empirical risk minimization with unbounded noise and estimates.
method Chaining technique applied to random design settings, proving excess risk bounds.
result Proves upper bounds for empirical risk minimization with sub-Gaussian or subexponential noise.
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.
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 O(logT). 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.
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.
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
Proposes a method to learn both constraints and objective functions from data.
problem Data-driven inverse optimization for mixed-integer linear programs (MILPs).
method Two-stage approach: first learns constraints, then estimates objective-function weights conditioned on learned constraints.
result Proposes and validates a method for learning both objective functions and constraints from data.
Study improves least squares estimation for heavy-tailed errors.
problem Improving least squares estimation under heteroscedastic and heavy-tailed errors.
method Analyzes the rate of convergence of least squares estimator under bounded conditional variance and finitely many moments of errors.
result Upper bounds on rates of convergence of LSE for heavy-tailed errors are found.