On the Optimality of the Median-of-Means Estimator under Adversarial Contamination

• URL: http://arxiv.org/abs/2510.07867v1
• Date: Thu, 09 Oct 2025 07:17:09 GMT
• Title: On the Optimality of the Median-of-Means Estimator under Adversarial Contamination
• Abstract summary: We present upper and lower bounds for the error of MoM under adversarial contamination.<n>We show that MoM is (minimax) optimal in the class of distributions with finite variance.<n>We also provide lower bounds for MoM's error that match the order of the presented upper bounds, and show that MoM is sub-optimal for light-tailed distributions.
• Score: 8.243212777125752
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Median-of-Means (MoM) is a robust estimator widely used in machine learning that is known to be (minimax) optimal in scenarios where samples are i.i.d. In more grave scenarios, samples are contaminated by an adversary that can inspect and modify the data. Previous work has theoretically shown the suitability of the MoM estimator in certain contaminated settings. However, the (minimax) optimality of MoM and its limitations under adversarial contamination remain unknown beyond the Gaussian case. In this paper, we present upper and lower bounds for the error of MoM under adversarial contamination for multiple classes of distributions. In particular, we show that MoM is (minimax) optimal in the class of distributions with finite variance, as well as in the class of distributions with infinite variance and finite absolute $(1+r)$-th moment. We also provide lower bounds for MoM's error that match the order of the presented upper bounds, and show that MoM is sub-optimal for light-tailed distributions.

Related papers

• Maximum Mean Discrepancy with Unequal Sample Sizes via Generalized U-Statistics [12.514069914597782]
  Two-sample testing techniques often assume equal sample sizes from the two distributions of the Maximum Mean Discrepancy (MMD)<n>Applying these methods in practice can require discarding valuable data, unnecessarily reducing test power.<n>We address this long-standing limitation by extending the theory of generalized U-statistics and applying it to the usual MMD estimator.<n>This generalization also provides a new criterion for optimizing the power of an MMD test with unequal sample sizes.
  arXiv  Detail & Related papers  (2025-12-16T01:29:50Z)
• Learning Parametric Distributions from Samples and Preferences [19.879505582147807]
  We show that preference-based M-estimators achieve a better variance than sample-only M-estimators.<n>We propose an estimator achieving an estimation error scaling of $mathcalO (1/n)$ -- a significant improvement over the $Theta (1/sqrtn)$ rate attainable with samples alone.
  arXiv  Detail & Related papers  (2025-05-29T15:33:43Z)
• Minimax Optimality of the Probability Flow ODE for Diffusion Models [8.15094483029656]
  This work develops the first end-to-end theoretical framework for deterministic ODE-based samplers.<n>We propose a smooth regularized score estimator that simultaneously controls both the $L2$ score error and the associated mean Jacobian error.<n>We demonstrate that the resulting sampler achieves the minimax rate in total variation distance, modulo logarithmic factors.
  arXiv  Detail & Related papers  (2025-03-12T17:51:29Z)
• Theory on Score-Mismatched Diffusion Models and Zero-Shot Conditional Samplers [49.97755400231656]
  We present the first performance guarantee with explicit dimensional dependencies for general score-mismatched diffusion samplers.<n>We show that score mismatches result in an distributional bias between the target and sampling distributions, proportional to the accumulated mismatch between the target and training distributions.<n>This result can be directly applied to zero-shot conditional samplers for any conditional model, irrespective of measurement noise.
  arXiv  Detail & Related papers  (2024-10-17T16:42:12Z)
• Flow matching achieves almost minimax optimal convergence [50.38891696297888]
  Flow matching (FM) has gained significant attention as a simulation-free generative model. This paper discusses the convergence properties of FM for large sample size under the $p$-Wasserstein distance. We establish that FM can achieve an almost minimax optimal convergence rate for $1 leq p leq 2$, presenting the first theoretical evidence that FM can reach convergence rates comparable to those of diffusion models.
  arXiv  Detail & Related papers  (2024-05-31T14:54:51Z)
• A Uniform Concentration Inequality for Kernel-Based Two-Sample Statistics [4.757470449749877]
  We show that these metrics can be unified under a general framework of kernel-based two-sample statistics.<n>This paper establishes a novel uniform concentration inequality for the aforementioned kernel-based statistics.<n>As illustrative applications, we demonstrate how these bounds facilitate the component of error bounds for procedures such as distance covariance-based dimension reduction.
  arXiv  Detail & Related papers  (2024-05-22T22:41:56Z)
• Partial identification of kernel based two sample tests with mismeasured data [5.076419064097733]
  Two-sample tests such as the Maximum Mean Discrepancy (MMD) are often used to detect differences between two distributions in machine learning applications. We study the estimation of the MMD under $epsilon$-contamination, where a possibly non-random $epsilon$ proportion of one distribution is erroneously grouped with the other. We propose a method to estimate these bounds, and show that it gives estimates that converge to the sharpest possible bounds on the MMD as sample size increases.
  arXiv  Detail & Related papers  (2023-08-07T13:21:58Z)
• Keep it Tighter -- A Story on Analytical Mean Embeddings [0.6445605125467574]
  Kernel techniques are among the most popular and flexible approaches in data science. Mean embedding gives rise to a divergence measure referred to as maximum mean discrepancy (MMD) In this paper we focus on the problem of MMD estimation when the mean embedding of one of the underlying distributions is available analytically.
  arXiv  Detail & Related papers  (2021-10-15T21:29:27Z)
• Fast Batch Nuclear-norm Maximization and Minimization for Robust Domain Adaptation [154.2195491708548]
  We study the prediction discriminability and diversity by studying the structure of the classification output matrix of a randomly selected data batch. We propose Batch Nuclear-norm Maximization and Minimization, which performs nuclear-norm on the target output matrix to enhance the target prediction ability. Experiments show that our method could boost the adaptation accuracy and robustness under three typical domain adaptation scenarios.
  arXiv  Detail & Related papers  (2021-07-13T15:08:32Z)
• A Unified Joint Maximum Mean Discrepancy for Domain Adaptation [73.44809425486767]
  This paper theoretically derives a unified form of JMMD that is easy to optimize. From the revealed unified JMMD, we illustrate that JMMD degrades the feature-label dependence that benefits to classification. We propose a novel MMD matrix to promote the dependence, and devise a novel label kernel that is robust to label distribution shift.
  arXiv  Detail & Related papers  (2021-01-25T09:46:14Z)
• Minimax Optimal Estimation of KL Divergence for Continuous Distributions [56.29748742084386]
  Esting Kullback-Leibler divergence from identical and independently distributed samples is an important problem in various domains. One simple and effective estimator is based on the k nearest neighbor between these samples.
  arXiv  Detail & Related papers  (2020-02-26T16:37:37Z)
• Distributionally Robust Bayesian Quadrature Optimization [60.383252534861136]
  We study BQO under distributional uncertainty in which the underlying probability distribution is unknown except for a limited set of its i.i.d. samples. A standard BQO approach maximizes the Monte Carlo estimate of the true expected objective given the fixed sample set. We propose a novel posterior sampling based algorithm, namely distributionally robust BQO (DRBQO) for this purpose.
  arXiv  Detail & Related papers  (2020-01-19T12:00:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.