Efficient streaming algorithms for robust statistics with near-optimal memory.
problem High-dimensional robust statistics tasks in streaming model.
method First efficient streaming algorithms with near-optimal memory requirements.
result Near-optimal error guarantees and space complexity nearly-linear in the dimension for robust mean estimation.
Survey on efficient robust estimators for high-dimensional statistics.
problem Efficient robust mean estimation in high dimensions.
method Emerging algorithmic techniques in theoretical computer science.
result First efficient robust estimators for fundamental tasks.
New algorithms improve privacy in statistical estimation by making them robust.
problem Improving privacy in statistical estimation methods.
method Black-box reduction from privacy to robustness, using Sum-of-Squares method.
result Design of polynomial-time private estimators with optimal tradeoffs among sample complexity, accuracy, and privacy.
Gradient descent solves robust mean estimation in high dimensions.
problem High-dimensional robust mean estimation in the presence of adversarial outliers.
method Gradient descent with a structural lemma showing near-optimal solutions.
result Gradient descent can solve the robust mean estimation problem directly.
New algorithm for robust high-dimensional linear regression is both fast and statistically optimal.
problem Challenges in high-dimensional linear regression under heavy-tailed noise or outliers.
method Projected sub-gradient descent algorithm for sparse and low-rank regression problems.
result Algorithm achieves linear convergence and statistical optimality under various noise conditions.
Develops a computationally tractable high-dimensional differential privacy estimator.
problem Differential privacy in high dimensions is computationally intractable.
method Combines high-dimensional robust statistics with differential privacy techniques.
result A computationally tractable algorithm with dimension-independent privacy loss.
New method improves robust sparse association estimation.
problem Outliers in high-dimensional data.
method Splitting robust estimation into optimization phases, using augmented Lagrangian and adaptive gradient descent.
result Improved precision over existing methods.
Study examines mean estimation in high dimensions with small data.
problem Efficiently estimating mean in high-dimensional data with limited data size.
method Extensive experimentation of various mean estimation techniques.
result Developed robust methods for mean estimation with low data size.
Proposes ARSK for robust and sparse clustering.
problem Outliers and high-dimensional noisy variables in K-means clustering.
method Introduces redundant error component and group sparse penalty for robustness, and weights and sparsity control penalty for noisy variables.
result Superior performance in identifying clusters without outliers and informative variables.
Many conventional statistical procedures are extremely sensitive to seemingly minor deviations from modeling assumptions. This problem is exacerbated in modern high-dimensional settings, where the problem dimension can grow with and possibly exceed the sample size. We consider the problem of robust estimation of sparse…
Factor models are a class of powerful statistical models that have been widely used to deal with dependent measurements that arise frequently from various applications from genomics and neuroscience to economics and finance. As data are collected at an ever-growing scale, statistical machine learning faces some new cha…
Robust methods for high-dimensional linear learning improve performance under heavy-tailed distributions and outliers.
problem Efficient learning in high-dimensional settings with robustness to outliers and heavy-tailed data.
method Two algorithms depending on gradient-Lipschitz loss function, applied to sparse, group-sparse, and low-rank matrix recovery.
result Achieved near-optimal estimation rates under heavy-tails and outliers, with computational cost comparable to non-robust methods.
New methods solve sparse estimation robustly, even with outliers.
problem Sparse estimation in high-dimensional data with outliers.
method Non-convex optimization formulations for robust sparse mean estimation and PCA.
result Any approximate stationary point yields near-optimal solutions.
Low-degree method fails to predict robust subspace recovery problem.
problem Predicting computational tractability of robust subspace recovery problem.
method Low-degree polynomial framework, anti-concentration properties.
result Low-degree method fails to predict computational tractability of robust subspace recovery problem even up to high degree.
New geometric methods improve optimization and data science problems.
problem Improving optimization and data science problems.
method Geometric tools for high-dimensional optimization and statistical data science.
result New algorithms and statistical guarantees for optimization and data science.
Paper proposes differentially private quantile regression for high-dimensional data.
problem Privacy concerns in big data with heterogeneous sensitive personal information.
method Newton-type transformation for reformulating quantile regression into an OLS problem; iterative updates for estimation; debiased estimator for inference; communication-efficient bootstrap.
result Near-optimal statistical accuracy and formal privacy guarantees achieved.
Proves subgaussian distributions are SoS-certifiably subgaussian, enabling efficient algorithms for various statistical tasks.
problem Efficiently learning from subgaussian distributions in high dimensions.
method Universal constant C and polynomial sum of squares (SoS) approach. result Proves subgaussian distributions are SoS-certifiably subgaussian.
New robust method for high-dimensional data analysis in imaging studies.
problem Analyzing high-dimensional data with complex dependence and outliers.
method Robust high-dimensional regression with coefficient thresholding and Huber loss.
result Statistical consistency and computational convergence under high-dimensional settings.
Proposes two-stage robust and sparse distributed inference for large-scale data.
problem Statistical inference in large-scale, high-dimensional, and outlier-contaminated data.
method Two-stage approach: model selection with robust Lasso, fusion of local selections, and bootstrap methods for inference.
result Robust and computationally efficient inference procedures for variable selection, confidence intervals, and standard deviation approximations.
Proposes a new robust expectile regression method for high-dimensional data.
problem Heterogeneity in high-dimensional data with heteroscedastic variance or inhomogeneous covariate effects.
method Iteratively reweighted ℓ1-penalization for robust expectile regression (retire).
result Oracle convergence rate after log(log d) iterations in high-dimensional settings.
Transforms robust algorithms into private ones with optimal error rates.
problem Balancing privacy and robustness in machine learning.
method Black-box transformation method to convert robust algorithms to private ones with optimal error rates.
result Optimal private estimators for various tasks, including Gaussian and PCA.
Framework for efficient statistical estimation with privacy guarantees.
problem Statistical estimation problems with differential privacy constraints.
method High-dimensional Propose-Test-Release (HPTR) framework combining exponential mechanism, robust statistics, and resilience.
result Near-optimal utility guarantees and tight local sensitivity bounds for various statistical problems.
New algorithms balance collaboration and adversarial behavior in linear bandits.
problem Minimizing regret in a collaborative linear bandit problem with adversarial agents.
method Robust collaborative phased elimination algorithm with tight analyses.
result Achieves near-optimal regret bounds of $O\left(α+ 1/\sqrt{M}
ight) \sqrt{dT}$ for good agents.
We consider the problem of robustifying high-dimensional structured estimation. Robust techniques are key in real-world applications which often involve outliers and data corruption. We focus on trimmed versions of structurally regularized M-estimators in the high-dimensional setting, including the popular Least Trimme…
Paper improves robustness certification by integrating ML and logical reasoning.
problem Limited robustness certification under perturbation radius.
method Integrates statistical ML models with logical reasoning using Markov logic networks.
result First certified robustness bound for MLN derived and experimentally validated.
Proposes a method to compare noisy high-dimensional datasets with low-dimensional manifolds.
problem Comparing distributions on manifolds in noisy high-dimensional datasets.
method Linking low-rank structure to manifold geometry, developing a scale-invariant distance measure.
result Superior robustness and statistical power compared to existing methods.
New algorithms robustly estimate mean with near-optimal error rates.
problem Outlier robust mean estimation in high-dimensional data.
method Stability condition and iterative filtering algorithms.
result Optimal error rates with subgaussian rates for robust mean estimation.
HD-BWDM improves clustering validation in high-dimensional data.
problem Determining the right number of clusters in high-dimensional data.
method HD-BWDM integrates random projection, PCA, trimmed clustering, and medoid-based distances.
result HD-BWDM remains stable and interpretable under high-dimensional projections and contamination.
T-Rex uses EM to fit robust factor models in noisy data.
problem Robustly fitting factor models in high-dimensional data with heavy tails and outliers.
method Expectation-Maximization (EM) algorithm based on Tyler's M-estimator for elliptical distributions.
result Demonstrates robustness in direction-of-arrival estimation and subspace recovery.
Efficiently estimates sparse mean from heavy-tailed data.
problem Robustly estimating sparse mean from heavy-tailed distributions.
method Stability-based approach adapted for heavy-tailed data.
result Optimal sample complexity with logarithmic dependence on dimension.
Robust CG methods avoid data corruption and solve structured statistical estimation problems.
problem Data corruption and heavy-tailed data in structured statistical estimation.
method Robustification of Conditional Gradient (CG) type methods using Huber's corruption model and robust mean gradient estimation.
result Robust CG methods converge linearly with correct sample complexity, even for high-dimensional problems.
The problems of outliers detection and robust regression in a high-dimensional setting are fundamental in statistics, and have numerous applications. Following a recent set of works providing methods for simultaneous robust regression and outliers detection, we consider in this paper a model of linear regression with i…
Paper develops robust methods for large-scale testing without tuning parameters.
problem Heavy-tailed data in high-dimensional settings.
method Revisits Hodges-Lehmann estimator for robust inference without tuning parameters.
result Develops confidence intervals and controls false discovery proportion.
This paper bridges outlier-robust estimation in robotics and computer vision with robust statistics.
problem Outlier-robust estimation for geometric perception in robotics and computer vision.
method Adapting and extending robust linear regression and list-decodable regression to non-convex domains and vector-valued measurements.
result Performance guarantees for modern estimation algorithms in the presence of outliers.
Deep neural networks identify robust arbitrage strategies in financial markets.
problem Identifying profitable trading strategies under model ambiguity.
method Data-driven deep neural networks considering high-dimensional financial markets.
result Empirical investigations show profitable trading performances in various market conditions.
Why are classifiers in high dimension vulnerable to "adversarial" perturbations? We show that it is likely not due to information theoretic limitations, but rather it could be due to computational constraints. First we prove that, for a broad set of classification tasks, the mere existence of a robust classifier implie…
Robustly estimates sparse data with corrupted outliers.
problem Adversarial corruption in high-dimensional sparse data.
method Iterative filtering using spectral techniques.
result Achieves near-optimal robustness guarantees.
New algorithm resists contamination in high-dimensional regression with optimal performance.
problem Adversarial and measurement errors in high-dimensional data.
method Adversarial Contamination-resistant Iterative Hard Thresholding (AC-IHT) algorithm.
result Achieves minimax near-optimal estimation and signal-adaptive support recovery.
This work studies adversarial training in high dimensions, revealing key feature trade-offs.
problem Understanding adversarial robustness in high-dimensional settings.
method Introduces a tractable model to study the geometry of data and adversarial attacks.
result Characterizes directions in data associated with robustness vs. usefulness trade-offs.
Paper optimizes hyperparameters for high-dimensional regression models.
problem Optimizing robustness radius in high-dimensional linear regression.
method Distributionally robust optimization (DRO) with high-dimensional asymptotic statistics.
result Optimal hyperparameter selection minimizes estimation error efficiently.
New algorithms robust to adversarial data achieve optimal performance.
problem Adversarial robustness in high-dimensional online learning problems.
method Alternating minimization scheme combining least-squares and convex reweighting.
result Achieves optimal robustness guarantees without distributional assumptions.
This work improves understanding of projection robust optimal transport distances.
problem Understanding the behavior of minimum Wasserstein estimators in high-dimensional and misspecified models.
method Adopting projection robust (PR) optimal transport, establishing statistical properties, proposing IPRW distance, and providing asymptotic guarantees.
result Established fundamental statistical properties and proposed new distances that outperform Wasserstein distances empirically.
Gaussian Graphical Models (GGMs) are popular tools for studying network structures. However, many modern applications such as gene network discovery and social interactions analysis often involve high-dimensional noisy data with outliers or heavier tails than the Gaussian distribution. In this paper, we propose the Tri…
New algorithm estimates robust Gaussian covariance in nearly matrix multiplication time.
problem Estimating robust covariance from corrupted Gaussian samples.
method Developed a novel algorithm achieving near-optimal error in Mahalanobis norm with runtime nearly matrix multiplication time.
result Achieved the same statistical guarantees as previous work but with no dependence on ε in runtime.
Paper proposes robust tensor regression method for tensor data analysis.
problem Outliers in tensor data analysis can make existing methods sensitive.
method Nonconvex relaxation of tensor tubal rank in optimization framework.
result Global convergence of proposed estimation algorithm under mild assumptions.
The paper develops AMP theory for sparse and robust regression with polynomial iterations.
problem Challenges in high-dimensional statistical estimation due to asymptotic theory breakdown.
method Non-asymptotic distributional theory of AMP for sparse and robust regression.
result First finite-sample non-asymptotic distributional theory of AMP for polynomial iterations.
Heavy-tailed outliers are more resilient to robust estimation than adversarial ones.
problem Developing robust estimators for data with outliers.
method Analyzing the relationship between adversarial and heavy-tailed outlier models.
result Optimal estimators for heavy-tailed outliers are also optimal for adversarial settings, but not vice versa.
High-dimensional models become unstable when sample size falls below a critical level, leading to a phase transition.
problem Instability in high-dimensional learning models when sample size is insufficient.
method Proved the necessity of a Fisher eigenvalue threshold for stability, introduced Fisher floor for verification.
result A sharp phase transition between reliable concentration and inevitable failure in high-dimensional learning.