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.
Median-of-means sampling outperforms mean-of-means for large sample sizes in numerical integration.
problem Improving numerical integration accuracy in high dimensions.
method Median-of-means sampling compared to mean-of-means using RQMC methods.
result Median-of-means sampling is superior for large sample sizes, while mean-of-means is better for smaller sample sizes.
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.
We propose a new clustering algorithm that is robust to the presence of outliers in the dataset. We perform Lloyd-type iterations with robust estimates of the centroids. More precisely, we build on the idea of median-of-means statistics to estimate the centroids, but allow for replacement while constructing the blocks.…
Paper introduces MoM-KDE for robust density estimation robust to anomalous data.
problem Density estimation robustness to anomalous data.
method Combines Kernel Density Estimation and Median-of-Means principle.
result Achieves competitive results with lower computational complexity compared to other robust estimators.
New method improves mean estimation for heavy-tailed data.
problem Estimating mean of heavy-tailed distributions.
method Median-of-Means (MoM) with symmetrization technique.
result Improved sample complexity bound for mean estimation.
A regularized risk minimization procedure for regression function estimation is introduced that achieves near optimal accuracy and confidence under general conditions, including heavy-tailed predictor and response variables. The procedure is based on median-of-means tournaments, introduced by the authors in [8]. It is …
Introduces robust convex clustering with Median of Means for better data clustering.
problem Challenges in convex clustering with high-dimensional data and noise/outliers.
method Integrates convex clustering with Median of Means estimator for robustness and efficiency.
result Enhanced clustering performance on large-scale datasets compared to existing methods.
A new PCA method robust to outliers using Median of Means.
problem PCA's failure to detect true structure in noisy data.
method Median of Means (MoM) approach for robust PCA.
result Achieves optimal convergence rates without assumptions on outliers.
Proposes a robust clustering method using the Median-of-Means estimator.
problem Noise and outliers in data affect clustering quality and require specifying the number of clusters.
method Integrates model-based and centroid-based clustering methods using the Median-of-Means estimator.
result Mitigates noise effects and estimates the number of clusters automatically.
Paper shows MoM is optimal under adversarial contamination for certain distributions.
problem Optimality of MoM under adversarial contamination.
method Upper and lower bounds for MoM's error under adversarial contamination.
result MoM is (minimax) optimal for distributions with finite variance and infinite variance with finite absolute moments.
Paper introduces robust deep learning method for handling random data corruption.
problem Random corruption in deep learning data due to limited quality of data.
method Inspired by median-of-means and Le Cam's principle, introduces a new approach.
result Demonstrates the approach performs well in practice and is a promising alternative to standard training methods.
Study improves generalization bounds for machine learning models in the presence of outliers.
problem Improving model robustness against outliers in machine learning.
method Median-of-Means (MoM) estimator and concentration properties analysis under contamination.
result Derives generalization guarantees for pairwise learning in contaminated data.
Mean embeddings provide an extremely flexible and powerful tool in machine learning and statistics to represent probability distributions and define a semi-metric (MMD, maximum mean discrepancy; also called N-distance or energy distance), with numerous successful applications. The representation is constructed as the e…
Improved MoM estimator enhances classical shadows protocol for quantum measurements.
problem Efficient estimation of expectation values with reduced measurement shots.
method Modified median-of-means estimator with optimal constants and U-statistics.
result Improved performance of modified estimator for Clifford measurements.
Paper tackles robust offline RL with heavy-tailed rewards.
problem Real-world applications often encounter heavy-tailed rewards, challenging offline RL.
method Proposes ROAM and ROOM algorithms using median-of-means method for robust off-policy evaluation and OPO.
result Demonstrates superior performance on heavy-tailed reward datasets compared to existing methods.
New algorithm robustly learns from corrupted demonstrations, even with constant fraction of noise.
problem Learning from corrupted demonstrations where a fraction of data is noise or outliers.
method Proposes a novel robust algorithm using a Median-of-Means (MOM) objective.
result Guarantees accurate policy estimation even with constant fraction of outliers, similar to classical methods in expert demonstration settings.
This paper extends Median-of-Means to new learning problems involving pairwise comparisons.
problem Learning from pairwise comparisons in machine learning.
method Segmenting data into blocks, comparing pairs of decision rules, and declaring the winner based on majority performance.
result The Median-of-Means approach maintains robustness and performance under various sampling schemes.
New robust estimators achieve subgaussian bounds using VC-dimension.
problem Robust estimation of sparse and corrupted data.
method Use of VC-dimension to measure statistical complexity.
result First robust estimators for sparse estimation with subgaussian rate.
A new UCB algorithm for heavy-tailed bandits with near-optimal regret.
problem Sequential decision making in uncertain environments with heavy-tailed rewards.
method Data-driven, distribution-free UCB algorithm combining resampled median-of-means and UCB.
result Near-optimal regret bound for heavy-tailed distributions.
New method estimates optimizer for convex stochastic problems.
problem Estimating optimizer for convex stochastic optimization problems.
method Median-of-means tournament procedure for heavy-tailed data.
result Optimal statistical performance in heavy tailed situations.
New method robustifies topological data analysis against outliers.
problem Outliers make topological data analysis unstable.
method Proposed a robust distance function (MoM Dist) for persistent homology.
result MoM Dist sublevel filtrations and weighted filtrations are consistent estimators in adversarial settings.
Paper shows robust estimators converge to true risk minimizers at optimal rates.
problem Understanding asymptotic properties of robust risk minimizers.
method Investigates robust analogues of empirical risk minimization, focusing on median of means estimator.
result Robust minimizers converge to true minimizers at optimal rates and have similar asymptotic variance.
Paper proposes robust compressed sensing using generative models.
problem Estimating high-dimensional vectors from noisy linear equations with heavy-tailed or outlier data.
method Inspired by Median-of-Means (MOM), proposes an algorithm for robust recovery.
result Guarantees recovery for heavy-tailed data, even in the presence of outliers.
This work robustifies Wasserstein distance estimation with MoM estimators for outlier-polluted data.
problem Estimating Wasserstein distance between two distributions with outliers.
method Introducing MoM-based robust estimators for Wasserstein distance.
result Consistent MoM-based estimators for Wasserstein distance with convergence rates.
Study robust linear regression without distributional assumptions for heavy-tailed responses.
problem Linear regression with heavy-tailed responses and no distributional assumptions.
method Combining truncated least squares, median-of-means, and aggregation theory to construct a non-linear estimator.
result Achieves excess risk of order d/n with optimal sub-exponential tail. New algorithms for stochastic linear bandits with heavy-tailed payoffs achieve nearly optimal regret.
problem Stochastic linear bandits with heavy-tailed payoffs.
method Median of means and dynamic truncation.
result Sublinear regret bound of O(d21T1+ε1) for ε∈(0,1]. Paper develops a new algorithm for sparse signal recovery.
problem Sparse signal recovery from noisy observations.
method Iterative Stochastic Optimization using Stochastic Mirror Descent.
result Linear convergence during preliminary phase of the routine.
We survey some of the recent advances in mean estimation and regression function estimation. In particular, we describe sub-Gaussian mean estimators for possibly heavy-tailed data both in the univariate and multivariate settings. We focus on estimators based on median-of-means techniques but other methods such as the t…
Unified framework for robust clustering under various dissimilarity measures.
problem Improving center-based clustering methods to handle outliers and non-Euclidean data.
method Median-of-Means (MoM) estimation framework with uniform concentration bounds.
result Strong consistency and error rate of O(n−1/2) under mild conditions. Unified framework for robust linear predictions without distributional assumptions.
problem Robust linear predictions in the presence of outliers and model misspecification.
method Unified robust framework for linear prediction problems on Hilbert spaces, using Median of Means (MoM) approach.
result Achieves an error rate of \(O(\max\left\{|\mathcal{O}|^{1/2}n^{-1/2}, |\mathcal{I}|^{1/2}n^{-1}
ight\}+ε)\) for misspecification level \(ε\), matching best-known rates.
This paper presents a class of new algorithms for distributed statistical estimation that exploit divide-and-conquer approach. We show that one of the key benefits of the divide-and-conquer strategy is robustness, an important characteristic for large distributed systems. We establish connections between performance of…
The stochastic multi-armed bandit problem is well understood when the reward distributions are sub-Gaussian. In this paper we examine the bandit problem under the weaker assumption that the distributions have moments of order 1+ε, for some ε∈(0,1]. Surprisingly, moments of order 2 (i.e., finite variance) are suffi…
This work studies applications and generalizations of a simple estimation technique that provides exponential concentration under heavy-tailed distributions, assuming only bounded low-order moments. We show that the technique can be used for approximate minimization of smooth and strongly convex losses, and specificall…
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.
SNAP improves robust computation by emphasizing trustworthy items and downweighting outliers.
problem Improving robustness in computation, especially in high-dimensional settings.
method SNAP assigns weights based on mutual agreement, suppressing outlier contributions.
result SNAP ensures outliers contribute negligibly to computations, even in high-dimensional settings.
To improve the off-sample generalization of classical procedures minimizing the empirical risk under potentially heavy-tailed data, new robust learning algorithms have been proposed in recent years, with generalized median-of-means strategies being particularly salient. These procedures enjoy performance guarantees in …
Paper uses DNN-based MoM-GAN to estimate contaminated data distributions.
problem Estimating distributions of data with outliers or contamination.
method Combines GAN and MoM estimation with DNN for modeling.
result DNN-based MoM-GAN achieves better error bounds than other methods.
Paper addresses robust federated linear bandits against Byzantine attacks.
problem Byzantine attacks on a small fraction of agents in federated learning.
method Proposes a geometric median-based robust aggregation oracle.
result Achieves sublinear regret bound of ildeO(T3/4) robust to fewer than half Byzantine agents. Robust score matching improves parameter estimation in contaminated data.
problem Parameter estimation in data contaminated by outliers.
method Geometric median of means to develop a robust score matching procedure.
result Consistent parameter estimates in contaminated data settings.
GROS combines estimators robustly in metric spaces.
problem Combining estimators in metric spaces for robustness.
method Divide sample into groups, compute estimators, combine robustly.
result GROS is sub-Gaussian with a proven break-down point.
Robustifies Markowitz portfolios to reduce transaction costs and improve performance.
problem Markowitz portfolios are unreliable due to estimation errors and extreme weights.
method Projected gradient descent and robust statistics for stable weights and costs.
result Robustified Markowitz portfolios have lower turnover and maintain or improve performance.
A new method for streaming PCA provides confidence intervals for eigenvector entries.
problem Uncertainty quantification for individual entries in streaming PCA.
method Oja's algorithm, Bernstein-type concentration bound, Central Limit Theorem, subsampling algorithm.
result Sharp concentration bound and Central Limit Theorem for streaming PCA entries.
In linear stochastic bandits, it is commonly assumed that payoffs are with sub-Gaussian noises. In this paper, under a weaker assumption on noises, we study the problem of \underline{lin}ear stochastic {\underline b}andits with h{\underline e}avy-{\underline t}ailed payoffs (LinBET), where the distributions have finite…
Accelerated optimization methods improve robustness and privacy in estimation.
problem Improving robustness and privacy in estimation methods.
method Accelerated gradient methods based on Frank-Wolfe and projected gradient descent, with tailored learning rates and Nesterov's momentum.
result Reduction in iteration complexity, leading to stronger statistical guarantees.
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.
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.
New algorithm reduces heavy-tailed linear bandits' computational cost.
problem Stochastic linear bandits with heavy-tailed noise.
method One-pass online mirror descent with adaptive Huber regression.
result Near-optimal regret bound with reduced computational cost.