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.
New gossip algorithms improve robustness of rank-based statistics in decentralized systems.
problem Ensuring robustness in decentralized AI and edge intelligence systems, especially in the presence of corrupted or adversarial data.
method Developed asynchronous gossip algorithms for computing rank-based statistics.
result First convergence rate bound for asynchronous gossip-based rank estimation.
Learning in the presence of outliers is a fundamental problem in statistics. Until recently, all known efficient unsupervised learning algorithms were very sensitive to outliers in high dimensions. In particular, even for the task of robust mean estimation under natural distributional assumptions, no efficient algorith…
Survey of robust statistical methods for efficient computation.
problem Efficient robust statistical methods for various forms of data contamination and heavy-tailed distributions.
method Survey and technical connections between robustness forms, showing efficient algorithms.
result Same algorithmic ideas lead to efficient estimators for robustness in different settings.
Paper develops efficient algorithms for robust distributed learning with statistical guarantees.
problem Limited communication power and adversarial node behaviors in distributed learning.
method Surrogate likelihood framework and median/trimmed mean operations.
result Provable robustness against Byzantine failures and optimal statistical rates.
Bandit algorithms struggle with consistent performance and robustness.
problem Achieving consistent and robust performance in stochastic multi-armed bandit settings.
method Analyzing regret minimization trade-offs and proposing distribution-oblivious algorithms.
result Logarithmic regret is inconsistent and super-logarithmic regret is necessary for consistent learning.
New bandit algorithms focus on extreme values, outperforming existing methods.
problem Optimizing decisions based on extreme values rather than expected values.
method Robust statistics-based algorithms with vanishing extremal regret.
result The proposed algorithms achieve superior performance compared to existing methods.
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.
New voting rules protect against strategic voting by robust statistics.
problem Strategic voting can skew election outcomes.
method Revisit Mallows model, develop robust estimator.
result Efficient estimator achieves nearly optimal robustness.
In large-scale distributed learning, security issues have become increasingly important. Particularly in a decentralized environment, some computing units may behave abnormally, or even exhibit Byzantine failures -- arbitrary and potentially adversarial behavior. In this paper, we develop distributed learning algorithm…
The paper investigates AI robustness through experiments and statistical analysis.
problem Inaccurate AI predictions can lead to safety and adoption issues.
method Design of experiments framework to study AI classification robustness.
result AI algorithms' robustness is influenced by various factors.
Paper improves statistical efficiency of median-of-means estimator for Byzantine robust distributed inference.
problem Byzantine robustness in distributed learning systems.
method Variance reduced median-of-means (VRMOM) estimator for Byzantine robust distributed inference.
result Achieves a fast convergence rate with only a constant number of rounds of communications.
Linear regression models contaminated by Gaussian noise (inlier) and possibly unbounded sparse outliers are common in many signal processing applications. Sparse recovery inspired robust regression (SRIRR) techniques are shown to deliver high quality estimation performance in such regression models. Unfortunately, most…
Paper develops robust policy evaluation for reinforcement learning with outlier and heavy-tailed rewards.
problem Outlier contamination and heavy-tailed rewards in reinforcement learning.
method Develops a fully online robust policy evaluation procedure and efficient statistical inference.
result Establishes the Bahadur-type representation of the estimator and develops an online inference procedure.
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.
We study a recently proposed large-scale distributed learning paradigm, namely Federated Learning, where the worker machines are end users' own devices. Statistical and computational challenges arise in Federated Learning particularly in the presence of heterogeneous data distribution (i.e., data points on different de…
Privacy improves robustness in statistical estimation.
problem Sparse mean estimation under privacy constraints.
method Sum-of-Squares method and exponential-time mechanisms.
result Private algorithms matching optimal tradeoffs are not known, but achieved via Sum-of-Squares.
This thesis improves practical reinforcement learning methods with robustness, scalability, and efficiency.
problem Improving reinforcement learning methods for practical applications.
method Analyzes and develops robust, scalable, and efficient reinforcement learning algorithms.
result Proves the efficiency and robustness of new RL methods.
In this paper, we develop connections between two seemingly disparate, but central, models in robust statistics: Huber's epsilon-contamination model and the heavy-tailed noise model. We provide conditions under which this connection provides near-statistically-optimal estimators. Building on this connection, we provide…
This paper introduces online algorithms to estimate robust geometric median in large data streams.
problem Detecting outliers in large data sets using robust statistical measures.
method Online stochastic Newton methods for estimating the geometric median.
result Rates of convergence for online estimation of the geometric median.
Paper explores using bootstrap methods to improve SGD's stability and robustness.
problem Improving the stability and robustness of SGD.
method Investigates empirical bootstrap approaches for SGD from algorithmic stability and statistical robustness perspectives.
result Demonstrates construction of purely distribution-free confidence intervals using bootstrap SGD.
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.
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.
Distributionally Robust Optimization (DRO) has been shown to provide a flexible framework for decision making under uncertainty and statistical estimation. For example, recent works in DRO have shown that popular statistical estimators can be interpreted as the solutions of suitable formulated data-driven DRO problems.…
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.
Novel algorithm reduces privacy noise in machine learning.
problem High privacy noise in machine learning algorithms.
method Robust statistics, specifically median and trimmed mean, to bound sensitivity of SGD iterates.
result Improved privacy-utility trade-off with reduced noise and computational efficiency.
New algorithms for best arm identification in bandits robust to misspecified parameters.
problem Inconsistent learning performance of traditional MAB algorithms when parameters are misspecified.
method Proposes two classes of asymptotically near-optimal algorithms for statistically robust MAB under fixed-budget pure exploration.
result Establishes fundamental performance limits and proposes algorithms that are asymptotically near-optimal.
New algorithm learns mixtures of any constant number of Gaussians robustly.
problem Learning mixtures of Gaussians with robustness guarantees.
method New method using differential operations on generating functions to prove polynomial identifiability.
result First provably robust algorithm for mixtures of any constant number of Gaussians.
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.
PRIME algorithm estimates mean while ensuring privacy and robustness.
problem Privacy and robustness in shared data analysis.
method Introduces PRIME, the first efficient algorithm for both privacy and robustness.
result Achieves both privacy and robustness for a wide range of distributions.
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.
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.
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.
RESIST improves decentralized learning resilience against MITM attacks.
problem Decentralized learning's vulnerability to MITM attacks.
method Multistep consensus gradient descent framework with robust statistics-based screening methods.
result Achieves algorithmic and statistical convergence for various ERM problems.
Paper introduces robust learning methods using coordinate gradient descent.
problem Supervised learning with corrupted features and labels.
method Coordinate gradient descent combined with robust estimators of partial derivatives.
result Robust learning methods with nearly identical numerical complexity to non-robust ones.
Algorithm estimates mixtures of arbitrary Gaussians robustly in presence of corruptions.
problem Estimating mixtures of arbitrary Gaussians in the presence of a constant fraction of arbitrary corruptions.
method Polynomial-time algorithm using partial clustering and tensor decomposition.
result Resolves the main open problem in several previous works on algorithmic robust statistics.
Survey of robust clustering methods for hotspot detection.
problem Detecting false positives in spatial hotspot mapping.
method Statistically rigorous clustering techniques.
result Survey of models and algorithms for robust clustering.
The paper tackles misspecification in contextual bandits by incorporating arm-specific variables.
problem Misspecification in contextual bandits due to unexplained inter-arm heterogeneity.
method Develops robust contextual bandit algorithms (RoLinUCB and RoLinTS) that incorporate arm-specific variables to address misspecification.
result The developed algorithms bound the n-round Bayes regret and show superior performance in various misspecification scenarios. 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.
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.
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.
New algorithm optimizes robust estimation under mixed local and global corruptions.
problem Combining local and global corruptions in robust statistics.
method Information-theoretic approach using sliced-Wasserstein metric.
result Optimal error achieved in polynomial time for stronger local perturbations.
New robust algorithms improve learning with feature feedback.
problem Interactive learning with discriminative feature feedback.
method Developed new robust interactive learning algorithms with improved mistake bounds.
result Achieved significantly lower mistake bounds in adversarial and stochastic settings.
Correntropy is a second order statistical measure in kernel space, which has been successfully applied in robust learning and signal processing. In this paper, we define a nonsecond order statistical measure in kernel space, called the kernel mean-p power error (KMPE), including the correntropic loss (CLoss) as a speci…
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 on robustness in linear regression models, focusing on adversarial perturbations.
problem Understanding and improving robustness in linear regression models to adversarial perturbations.
method Developed a two-stage adversarial learning framework that incorporates model structure information.
result Proved the consistency and developed the Bahadur representation of the adversarially robust estimator.
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.
We analyze SGAs for statistical inference via asymptotics, improving tuning methods.
problem Improper tuning of SGAs for optimization and sampling.
method Characterize large-sample asymptotics of SGAs via step-size and sample-size scaling limits.
result Iterate averaging with large step size is robust and asymptotically has covariance proportional to MLE's.