Mean estimation with sub-Gaussian rates in polynomial time

DOI10.1214/19-AOS1843zbMath1454.62162arXiv1809.07425MaRDI QIDQ2196216

Samuel B. Hopkins

Publication date: 28 August 2020

Published in: The Annals of Statistics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1809.07425

zbMATH Keywords

confidence intervalssemidefinite programmingheavy tailsmultivariate estimationsub-Gaussian ratessum of squares method

Mathematics Subject Classification ID

Estimation in multivariate analysis (62H12) Statistics of extreme values; tail inference (62G32) Semidefinite programming (90C22) General topics in the theory of algorithms (68W01)

Related Items

Robust sub-Gaussian estimation of a mean vector in nearly linear time, Concentration study of M-estimators using the influence function, Optimal robust mean and location estimation via convex programs with respect to any pseudo-norms, Robust multivariate mean estimation: the optimality of trimmed mean, Robustifying Markowitz, Robust supervised learning with coordinate gradient descent, Mean estimation in high dimension, ERM and RERM are optimal estimators for regression problems when malicious outliers corrupt the labels, Unnamed Item, Nearly optimal robust mean estimation via empirical characteristic function, Finite sample properties of parametric MMD estimation: robustness to misspecification and dependence, Robust and efficient mean estimation: an approach based on the properties of self-normalized sums, On Monte-Carlo methods in convex stochastic optimization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Geometric median and robust estimation in Banach spaces
• Sub-Gaussian mean estimators
• Community detection in sparse networks via Grothendieck's inequality
• Random generation of combinatorial structures from a uniform distribution
• The space complexity of approximating the frequency moments
• Relaxing the uniformity and independence assumptions using the concept of fractal dimension
• Sub-Gaussian estimators of the mean of a random vector
• Challenging the empirical mean and empirical variance: a deviation study
• Sub-Gaussian estimators of the mean of a random matrix with heavy-tailed entries
• Do semidefinite relaxations solve sparse PCA up to the information limit?
• Exact matrix completion via convex optimization
• Global Optimization with Polynomials and the Problem of Moments
• Exact Recovery in the Stochastic Block Model
• The Design of Approximation Algorithms
• An approach to obtaining global extremums in polynomial mathematical programming problems
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Determinant Maximization with Linear Matrix Inequality Constraints
• Semidefinite relaxation and nonconvex quadratic optimization
• High Dimensional Change Point Estimation via Sparse Projection
• Robust Estimators in High-Dimensions Without the Computational Intractability
• On the Bit Complexity of Sum-of-Squares Proofs
• Mixture models, robustness, and sum of squares proofs
• Robust moment estimation and improved clustering via sum of squares
• The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime
• Approximability of p → q Matrix Norms: Generalized Krivine Rounding and Hypercontractive Hardness
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• Geometric median in nearly linear time
• Semidefinite programs on sparse random graphs and their application to community detection
• Approximating the Cut-Norm via Grothendieck's Inequality
• Robust Estimation of a Location Parameter
• A Direct Formulation for Sparse PCA Using Semidefinite Programming