Robust Mixture Learning when Outliers Overwhelm Small Groups

• URL: http://arxiv.org/abs/2407.15792v1
• Date: Mon, 22 Jul 2024 16:51:05 GMT
• Title: Robust Mixture Learning when Outliers Overwhelm Small Groups
• Authors: Daniil Dmitriev, Rares-Darius Buhai, Stefan Tiegel, Alexander Wolters, Gleb Novikov, Amartya Sanyal, David Steurer, Fanny Yang,
• Abstract summary: We study the problem of estimating the means of well-separated mixtures when an adversary may add arbitrary outliers. We propose an algorithm that obtains order-optimal error guarantees for each mixture mean with a minimal list-size overhead.
• Score: 51.49063715477438
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the problem of estimating the means of well-separated mixtures when an adversary may add arbitrary outliers. While strong guarantees are available when the outlier fraction is significantly smaller than the minimum mixing weight, much less is known when outliers may crowd out low-weight clusters - a setting we refer to as list-decodable mixture learning (LD-ML). In this case, adversarial outliers can simulate additional spurious mixture components. Hence, if all means of the mixture must be recovered up to a small error in the output list, the list size needs to be larger than the number of (true) components. We propose an algorithm that obtains order-optimal error guarantees for each mixture mean with a minimal list-size overhead, significantly improving upon list-decodable mean estimation, the only existing method that is applicable for LD-ML. Although improvements are observed even when the mixture is non-separated, our algorithm achieves particularly strong guarantees when the mixture is separated: it can leverage the mixture structure to partially cluster the samples before carefully iterating a base learner for list-decodable mean estimation at different scales.

Related papers

• Fast Semisupervised Unmixing Using Nonconvex Optimization [80.11512905623417]
  We introduce a novel convex convex model for semi/library-based unmixing. We demonstrate the efficacy of Alternating Methods of sparse unsupervised unmixing.
  arXiv  Detail & Related papers  (2024-01-23T10:07:41Z)
• Clustering Mixtures of Bounded Covariance Distributions Under Optimal Separation [44.25945344950543]
  We study the clustering problem for mixtures of bounded covariance distributions. We give the first poly-time algorithm for this clustering task. Our algorithm is robust to $Omega(alpha)$-fraction of adversarial outliers.
  arXiv  Detail & Related papers  (2023-12-19T01:01:53Z)
• Mixture Proportion Estimation Beyond Irreducibility [9.99177526976127]
  We present a resampling-based meta-algorithm that takes any existing MPE algorithm designed to work under irreducibility and adapts it to work under our more general condition. Our approach exhibits improved estimation performance relative to baseline methods and to a recently proposed regrouping-based algorithm.
  arXiv  Detail & Related papers  (2023-06-02T03:32:44Z)
• Compound Batch Normalization for Long-tailed Image Classification [77.42829178064807]
  We propose a compound batch normalization method based on a Gaussian mixture. It can model the feature space more comprehensively and reduce the dominance of head classes. The proposed method outperforms existing methods on long-tailed image classification.
  arXiv  Detail & Related papers  (2022-12-02T07:31:39Z)
• C-Mixup: Improving Generalization in Regression [71.10418219781575]
  Mixup algorithm improves generalization by linearly interpolating a pair of examples and their corresponding labels. We propose C-Mixup, which adjusts the sampling probability based on the similarity of the labels. C-Mixup achieves 6.56%, 4.76%, 5.82% improvements in in-distribution generalization, task generalization, and out-of-distribution robustness, respectively.
  arXiv  Detail & Related papers  (2022-10-11T20:39:38Z)
• On Learning Mixture of Linear Regressions in the Non-Realizable Setting [44.307245411703704]
  We show that mixture of linear regressions (MLR) can be used for prediction where instead of predicting a label, the model predicts a list of values. In this paper we show that a version of the popular minimization (AM) algorithm finds the best fit lines in a dataset even when a realizable model is not assumed.
  arXiv  Detail & Related papers  (2022-05-26T05:34:57Z)
• Beyond Parallel Pancakes: Quasi-Polynomial Time Guarantees for Non-Spherical Gaussian Mixtures [9.670578317106182]
  We consider mixtures of $kgeq 2$ Gaussian components with unknown means and unknown covariance (identical for all components) that are well-separated. We show that this kind of hardness can only appear if mixing weights are allowed to be exponentially small. We develop an algorithm based on the sum-of-squares method with running time quasi-polynomial in the minimum mixing weight.
  arXiv  Detail & Related papers  (2021-12-10T10:51:44Z)
• MIX'EM: Unsupervised Image Classification using a Mixture of Embeddings [44.29313588655997]
  We present MIX'EM, a novel solution for unsupervised image classification. We conduct extensive experiments and analyses on STL10, CIFAR10, and CIFAR100-20 datasets. We achieve state-of-the-art classification accuracy of 78%, 82%, and 44%, respectively.
  arXiv  Detail & Related papers  (2020-07-18T19:24:22Z)
• Consistent Estimation of Identifiable Nonparametric Mixture Models from Grouped Observations [84.81435917024983]
  This work proposes an algorithm that consistently estimates any identifiable mixture model from grouped observations. A practical implementation is provided for paired observations, and the approach is shown to outperform existing methods.
  arXiv  Detail & Related papers  (2020-06-12T20:44:22Z)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  We study the efficient learnability of high-dimensional Gaussian mixtures in the adversarial-robust setting. We provide an algorithm that learns the components of an $epsilon$-corrupted $k$-mixture within information theoretically near-optimal error proofs of $tildeO(epsilon)$. Our main technical contribution is a new robust identifiability proof clusters from a Gaussian mixture, which can be captured by the constant-degree Sum of Squares proof system.
  arXiv  Detail & Related papers  (2020-05-13T16:44:12Z)

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.