Algorithm identifies Pareto set in bandits with contaminated feedback.
problem Identifying Pareto set in multi-objective bandits with adversarial contamination.
method Sample median-based multi-objective adaptive elimination algorithm.
result Sample complexity bound that depends on contamination probability.
A robust loss for anomaly mitigation and unsupervised contamination classification
problem Detecting and mitigating contamination in supervised and unsupervised settings
method Neural Bayesian Anomaly Mitigation (NBAM)
result Recovering the structure of contamination and identifying label-flip pairs
This paper studies active learning in the context of robust statistics. Specifically, we propose a variant of the Best Arm Identification problem for \emph{contaminated bandits}, where each arm pull has probability ε \varepsilon ε of generating a sample from an arbitrary contamination distribution instead of the true und…
Neural networks compress and sample WDN contamination dynamics efficiently.
problem Infrastructure monitoring of complex, networked systems like water distribution networks is expensive and challenging.
method Developed Graph Fourier Transform (GFT) operators and neural networks (NN) for efficient data collection and inference.
result High accuracy reconstruction of contamination dynamics using only 5-10% of the sample set.
Efficiently estimates mean in contaminated Gaussian data with near-optimal sample complexity.
problem Robust mean estimation in the presence of mean-shift contamination.
method First computationally efficient algorithm with near-optimal sample complexity and polynomial-time running.
result Approximates the target mean to any desired accuracy with constant fraction of outliers tolerated.
Robust covariance testing requires significantly more samples in contaminated data.
problem Testing the covariance matrix of a high-dimensional Gaussian in the presence of contamination.
method We study the problem in the Huber's contamination model, distinguishing between the identity matrix and matrices far from it in Frobenius norm.
result The sample complexity of covariance testing increases dramatically to Ω ( d 2 ) Ω(d^2) Ω ( d 2 ) in the contaminated setting. Trimming helps in conformal prediction when it separates anomaly scores.
problem Effectiveness of trimming in conformal prediction under contamination.
method Analyse fixed-threshold trimming as a replacement of the contaminated calibration law with a retained law.
result Trimming helps when it separates anomaly scores, reducing clean-target coverage to a one-dimensional score-CDF transfer problem.
Study sample complexity of robust binary hypothesis testing under different contamination models.
problem Analyzing the sample complexity of robust binary hypothesis testing under various contamination models.
method Examined three standard contamination models: ε-additive (Huber), ε-subtractive, and ε-total variation (TV). Provided explicit formulas for least favourable distributions and compared sample complexities across models.
result Sample complexities are highly unstable in the contamination parameter ε and comparable up to constant-factor rescaling of ε across models.
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.
New test ensures quality of shared data in machine learning.
problem Ensuring quality of external data in machine learning tasks.
method Distribution-free two-sample testing procedures grounded in conformal outlier detection.
result Identifies valuable external data agents for model personalization.
Efficiently estimates sparse linear regression with heavy-tailed and outlier-contaminated data.
problem Estimating sparse linear regression coefficients with heavy-tailed and outlier-contaminated data.
method Efficient computation of estimators with sharp error bounds.
result Sharp error bounds for efficient estimators.
Many machine learning problems can be characterized by mutual contamination models. In these problems, one observes several random samples from different convex combinations of a set of unknown base distributions. It is of interest to decontaminate mutual contamination models, i.e., to recover the base distributions ei…
Near-optimal algorithms for mean estimation and linear regression with Gaussian covariates and Huber contamination.
problem Gaussian mean estimation and linear regression with Gaussian covariates in the presence of Huber contamination.
method Near-optimal algorithms with optimal error guarantees, achieving sample complexity n = i l d e O ( d / ε 2 ) n = ilde{O}(d/ε^2) n = i l d e O ( d / ε 2 ) and almost linear runtime. result First sample near-optimal and almost linear-time algorithms with optimal error guarantees for both problems.
The paper tackles best arm identification in contaminated bandits with optimal error guarantees and sample complexity.
problem Best arm identification in stochastic bandits with adversarial reward contamination.
method Proposes two algorithms: a gap-based algorithm and a successive elimination-based algorithm for sub-Gaussian bandits.
result Asymptotically optimal sample complexity for both algorithms.
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.
Robust estimators for Gaussian sparse tasks with optimal error under contamination.
problem Robust mean estimation, PCA, and linear regression in the presence of Huber contamination.
method Novel multidimensional filtering method for sparse regime.
result Optimal error guarantees within constant factors for Gaussian robust k k k -sparse mean estimation. Study shows efficient algorithms for noiseless linear regression require quadratic sample complexity in contamination rate.
problem Efficient algorithms for noiseless linear regression under Gaussian covariates with oblivious contamination.
method Formal evidence using Statistical Query complexity.
result Any efficient Statistical Query algorithm requires VSTAT complexity at least Ω(d^(1/2)/α^2).
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.
Study minimax robustness in statistical estimation under Wasserstein contamination.
problem Adversarial perturbations in statistical data.
method Developed minimax theory for ℓ q r \ell_q^r ℓ q r losses under Wasserstein- r r r contaminations. result Exact minimax risk identified for joint contaminations in location estimation and prediction in linear regression.
Study on estimating Gaussian mean with missing data in high dimensions.
problem Estimating Gaussian mean in high dimensions with missing data due to realizable contamination.
method Statistical Query model, Low-Degree Polynomials, PTF tests, and algorithms.
result Established information-computation gap and developed efficient algorithms.
New algorithms achieve optimal robustness in stochastic convex optimization under contamination.
problem Determining optimal rates for robust stochastic convex optimization under ε ε ε -contamination. method Developed novel algorithms achieving minimax-optimal excess risk under ε ε ε -contamination model without stringent assumptions. result Achieved minimax-optimal excess risk (up to logarithmic factors) under ε ε ε -contamination model. We develop and demonstrate a probabilistic method for classifying rare objects in surveys with the particular goal of building very pure samples. It works by modifying the output probabilities from a classifier so as to accommodate our expectation (priors) concerning the relative frequencies of different classes of obj…
A new Heckman selection model uses a bivariate contaminated normal distribution for more accurate data analysis.
problem Sample selection biases in econometric data analysis.
method Introduces a Heckman selection model using a bivariate contaminated normal distribution and presents an efficient ECM algorithm for parameter estimation.
result The proposed model outperforms normal and Student's t counterparts in real data analysis and simulation studies.
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.
The paper shows how training with synthetic data can lead to model improvement, not degradation, under certain conditions.
problem Model collapse in iterative training on contaminated sources.
method Statistical analysis of iterative training on a mixture of true and synthetic data.
result Training with synthetic data can lead to model improvement, not degradation, under specific conditions.
New method calibrates ambiguity sets for robust decision-making under contamination.
problem Minimizing worst-case expected loss over distributional shifts in out-of-sample environments.
method Bulk-calibrated credal ambiguity sets that learn a high-mass bulk set from data and bound tail contributions.
result Closed-form, finite robust objective and tractable optimization for various losses and geometries.
Robustly aligns datasets with partial GW distance to handle contamination.
problem Aligning contaminated datasets using Gromov-Wasserstein distances.
method Proposes a partial GW distance estimator to minimize distortion from outliers.
result The partial GW distance estimator is minimax optimal and near-optimal in finite samples.
Study tackles contamination and heterogeneity in multi-task learning, improving robustness and personalization.
problem Challenges in integrating related tasks due to contamination and heterogeneity.
method Proposes a filtering-based robust multi-task gradient descent method to estimate global and clean task-specific minimizers.
result Demonstrates improved robustness and personalization compared to existing methods.
Replacing MSE with f-divergence in diffusion models improves robustness under data contamination.
problem Improving robustness of diffusion models under data contamination.
method Replacing MSE with f-divergence in diffusion models.
result Empirical improvement in performance under data contamination.
Study improves MMD estimation for two distributions with mismeasured data.
problem Estimating MMD under contaminated data.
method Partial identification of MMD bounds with a fast convergence rate.
result Proposes a method to estimate MMD bounds that converge faster than alternatives.
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.
Many machine learning problems can be characterized by mutual contamination models. In these problems, one observes several random samples from different convex combinations of a set of unknown base distributions and the goal is to infer these base distributions. This paper considers the general setting where the base …
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.
A new method detects distribution shifts faster than existing CTMs.
problem Detecting distribution shifts in data streams with contamination issues.
method Uses a fixed reference dataset to compare each new sample, avoiding contamination.
result Detects distribution shifts faster and more reliably than standard CTMs.
A contamination in a 3-manifold is an object interpolating between the contact structure and the lamination. Contaminations seem to provide a link between 3-dimensional contact geometry and the classical topology of 3-manifolds, as described in a separate paper. In this paper we deal with contaminations carried by bran…
New method for selective prediction under interventions learns causal structure from data.
problem Tight uncertainty sets in selective conformal prediction under unknown interventional settings.
method Partial causal structure learning for descendant indicators, contamination-robust coverage theorem, algorithms for descendant discovery and distance estimation.
result Valid selective conformal prediction under contamination up to 30% with controlled coverage.
Theoretical study on AI models' resilience to data contamination during recursive training.
problem Data contamination in recursive training of generative AI models.
method General framework with minimal assumptions on real data distribution and flexible generative models.
result Contaminated recursive training converges with a rate equal to the minimum of baseline model's rate and contamination fraction.
When the residents of Flint learned that lead had contaminated their water system, the local government made water-testing kits available to them free of charge. The city government published the results of these tests, creating a valuable dataset that is key to understanding the causes and extent of the lead contamina…
Study shows robust method for estimating density ratios even with heavy contamination.
problem Estimating density ratios in the presence of heavy contamination.
method Weighted density ratio estimation (DRE) with doubly strong robustness.
result Weighted DRE achieves sparse consistency under heavy contamination.
Generative models can still learn from contaminated data, but with limitations.
problem How much contamination can generative models tolerate?
method Characterized robustness under contaminated enumerations, proving generation is achievable for all countable collections if contamination fraction converges to zero.
result Generation under contamination is achievable for all countable collections if contamination fraction converges to zero, but dense generation is strictly less robust.
New framework for weakly supervised learning from label proportions.
problem Lack of consistent learning procedure and theoretical training criterion for LLP.
method Pose LLP as mutual contamination models (MCMs) and establish unbiased losses and generalization error bounds.
result Established novel technical results for MCMs and proposed a new experimental setting.
Motivated by applications of bandit algorithms in education, we consider a stochastic multi-armed bandit problem with ε \varepsilon ε -contaminated rewards. We allow an adversary to give arbitrary unbounded contaminated rewards with full knowledge of the past and future. We impose the constraint that for each time t t t the…
Paper introduces RAS for robust MTL with contamination.
problem Representation-based multi-task learning struggles with contamination.
method Robust and Adaptive Spectral (RAS) method.
result RAS prevents negative transfer and performs well with up to 80% contamination.
SHIFT improves robustness in estimating dose-response functions with heavy-tailed contamination.
problem Outliers bias estimates of average dose-response functions in heavy-tailed data.
method SHIFT combines cross-fit nuisance orthogonalization, Welsch-loss, and defensive OLS refit.
result SHIFT reduces RMSE from 1.03 to 0.33 on localized contamination test.
Improved robust regression with clean covariates achieves better rates than Huber's model.
problem Robust regression under adaptive contamination of responses with clean covariates.
method Exploiting clean covariates to construct an estimator achieving better rates than Huber's model.
result Improved estimation rate even with constant contamination, achieving consistency.
According to the United Nations World Water Assessment Programme, every day, 2 million tons of sewage and industrial and agricultural waste are discharged into the worlds water. In order to address this pervasive issue of increasing water pollution, while ensuring that the global population has an efficient, accurate, …
New method estimates discrete distributions while protecting privacy.
problem Estimating discrete distributions with local differential privacy.
method Combining robust learning and local differential privacy.
result Minimax estimation rate of ε d / α 2 k + d 2 / α 2 k n ε\sqrt{d/α^2 k}+\sqrt{d^2/α^2 kn} ε d / α 2 k + d 2 / α 2 k n under privacy constraint. Bayesian method estimates contamination factor for unsupervised anomaly detection.
problem No good methods for estimating contamination factor in unsupervised anomaly detection.
method Bayesian approach using mixture formulation of anomaly detector outputs.
result Estimated contamination factor distribution is well-calibrated and improves anomaly detection performance.