  Mixture proportion estimation (MPE) is the problem of estimating the weight
of a component distribution in a mixture, given samples from the mixture and
component. This problem constitutes a key part in many "weakly supervised
learning" problems like learning with positive and unlabelled samples, learning
with label noise, anomaly detection and crowdsourcing. While there have been
several methods proposed to solve this problem, to the best of our knowledge no
efficient algorithm with a proven convergence rate towards the true proportion
exists for this problem. We fill this gap by constructing a provably correct
algorithm for MPE, and derive convergence rates under certain assumptions on
the distribution. Our method is based on embedding distributions onto an RKHS,
and implementing it only requires solving a simple convex quadratic programming
problem a few times. We run our algorithm on several standard classification
datasets, and demonstrate that it performs comparably to or better than other
algorithms on most datasets.
