# Density estimation in linear time Source: [Density estimation in linear time]() Collection index: [llms.txt]() Data updated: 2025-10-28T13:56:23.020Z Authors: Satyaki Mahalanabis, Daniel Stefankovic Published: 2007-12-18T03:30:05.000Z ## Abstract We consider the problem of choosing a density estimate from a set of distributions F, minimizing the L1-distance to an unknown distribution (Devroye, Lugosi 2001). Devroye and Lugosi analyze two algorithms for the problem: Scheffe tournament winner and minimum distance estimate. The Scheffe tournament estimate requires fewer computations than the minimum distance estimate, but has strictly weaker guarantees than the latter. We focus on the computational aspect of density estimation. We present two algorithms, both with the same guarantee as the minimum distance estimate. The first one, a modification of the minimum distance estimate, uses the same number (quadratic in \|F\|) of computations as the Scheffe tournament. The second one, called \`\`efficient minimum loss-weight estimate,'' uses only a linear number of computations, assuming that F is preprocessed. We also give examples showing that the guarantees of the algorithms cannot be improved and explore randomized algorithms for density estimation. ## Recorded benchmark results A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage. - [Hypothesis Selection on Local Differential Privacy (LDP) model](): Hypothesis Selection; Local Differential Privacy (LDP) model; Approximation Factor: 3. ## Original sources and implementation [Original paper]() [PDF]()