Nearly-Linear Time Private Hypothesis Selection with the Optimal Approximation Factor
approximation factorcandidate distributionscentral modeldensity estimationdifferential privacydifferentially private algorithmefficient algorithmshypothesis selectionopen questionoptimal distancepolylogarithmicquadratic timesample complexitytotal variation distance
Estimating the density of a distribution from its samples is a fundamental problem in statistics. \emph{Hypothesis selection} addresses the setting where, in addition to a sample set, we are given $n$ candidate distributions