Abstract
Mixture proportion estimation (MPE) is a building block in many weakly supervised classification tasks, including label noise correction, anomaly detection, and semi-supervised learning. Estimators with finite sample guarantees are essential for analyzing algorithms in these domains, but such guarantees have historically been restricted to Euclidean and Hilbert space data. This paper generalises the framework of Blanchard, Lee, and Scott (BLS) to allow extensions to other data types. We deduce novel estimators for metric space data and for randomly compressed Euclidean data, both of which leverage intrinsic geometry to tighten performance guarantees. Finally, we establish a theoretical link between this generalised framework and state-of-the-art estimators specialised for Hilbert space data.
Introduction
Mixture Proportion Estimation (MPE) involves a "contaminated" dataset $F$ that is composed of a mixture of a known "signal" distribution $H$ and an unknown "noise" distribution $G$. The objective is to identify the maximum possible proportion $\kappa$ of the signal present in the mixture: $F = (1 - \kappa)G + \kappa H$.
While MPE is a core component of modern machine learning, it faces two significant hurdles. First is the issue of identifiability: without specific assumptions, the problem is ill-posed, as one cannot easily distinguish between a high signal proportion with one noise distribution and a low signal proportion with another. Second is the curse of dimensionality: existing estimators with rigorous theoretical guarantees often see their performance degrade rapidly as the ambient dimension $d$ of the data increases.
The Generalised BLS Framework
The primary contribution of this work is the introduction of a Generalised BLS estimator (Theorem 2). This serves as a "meta-algorithm" that transforms any uniform deviation bound—a mathematical guarantee of how closely a sample average approximates the true mean—into a consistent MPE estimator. By abstracting the estimator away from specific space requirements, the authors allow MPE to be applied to a much broader range of data structures.
Exploiting Intrinsic Geometry
By applying this generalised framework, the paper develops two novel applications that move beyond standard Euclidean assumptions:
1. Metric Space MPE
Traditional estimators often struggle when data exists in high-dimensional spaces. However, high-dimensional data often resides on lower-dimensional manifolds. The authors develop an estimator for general metric spaces where the convergence rate depends not on the ambient dimension $d$, but on the covering dimension. This describes the intrinsic complexity of the space, allowing for much tighter error bounds when the data has a simple underlying structure despite being embedded in a complex space.
2. Compressive MPE
In many large-scale applications, data is randomly projected or compressed into a lower-dimensional space to save on computation. The authors demonstrate how to estimate proportions directly from this compressed data. By utilizing the Gaussian width of the data's support, they provide guarantees proving that proportions can be estimated effectively without ever needing to reconstruct the original high-dimensional samples. A key insight here is that random projections preserve the "irreducibility" condition—the requirement that the noise $G$ does not contain a hidden copy of the signal $H$—with high probability.
Key Results and Theoretical Unification
The proposed estimators achieve a convergence rate of $O(n^{-1/2})$, where $n$ is the sample size. This is considered the optimal rate for such estimation problems. Furthermore, the bounds provided are often "dimension-free" in the sense that they scale with intrinsic measures (covering dimension or Gaussian width) rather than the raw number of features.
Crucially, the paper provides a theoretical bridge between this generalised BLS approach and the current state-of-the-art kernel-based estimators used in Hilbert spaces (e.g., Ramaswamy et al., 2016). This unifies two previously distinct branches of MPE research, showing they are governed by the same underlying principles.
Limitations and Future Work
While the paper provides robust statistical guarantees, it notes that the computational efficiency of calculating the required infimums in general metric spaces remains a challenge. Additionally, the estimators remain sensitive to the irreducibility assumption; if the signal and noise distributions are not sufficiently separated, performance will naturally decline. Future research may extend this framework to even more complex structured data, such as graphs or trees, using semimetric spaces.
Summary updated