Learning Distributions from Samples and Qualities

We study parameter estimation when each sample from a continuous parametric distribution is accompanied by a binary quality label governed by the same unknown parameter. By imposing hard feasibility constraints, deterministic labels can accelerate estimation from the classical n-1/2 rate of smooth quality-aware M-estimators to n-1. Combining PAC guarantees with local error-to-parameter conversions, we establish this rate for both identifiable and finitely ambiguous quality classifiers, with likelihood information resolving the latter ambiguity. When the quality model is known only up to an additive constant, we construct threshold-free pairwise preferences from oppositely labeled samples and retain the accelerated rate despite the unknown threshold. We further show that pointwise qualities and pairwise preferences are incomparable: either can be strictly more informative than the other. Our assumptions hold for Gaussian, Laplace, and exponential families under thresholded log-likelihood rewards. Finally, a minimax lower bound establishes the optimal n-1 dependence on sample size, up to logarithmic and dimension-dependent factors, while experiments confirm the benefits of constraint-based estimation.