Timezone: »
Poster
Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms
Siu On Chan · Ilias Diakonikolas · Rocco A Servedio · Xiaorui Sun
Let $p$ be an unknown and arbitrary probability distribution over $[0 ,1)$. We consider the problem of \emph{density estimation}, in which a learning algorithm is given i.i.d. draws from $p$ and must (with high probability) output a hypothesis distribution that is close to $p$. The main contribution of this paper is a highly efficient density estimation algorithm for learning using a variable-width histogram, i.e., a hypothesis distribution with a piecewise constant probability density function. In more detail, for any $k$ and $\eps$, we give an algorithm that makes $\tilde{O}(k/\eps^2)$ draws from $p$, runs in $\tilde{O}(k/\eps^2)$ time, and outputs a hypothesis distribution $h$ that is piecewise constant with $O(k \log^2(1/\eps))$ pieces. With high probability the hypothesis $h$ satisfies $\dtv(p,h) \leq C \cdot \opt_k(p) + \eps$, where $\dtv$ denotes the total variation distance (statistical distance), $C$ is a universal constant, and $\opt_k(p)$ is the smallest total variation distance between $p$ and any $k$-piecewise constant distribution. The sample size and running time of our algorithm are both optimal up to logarithmic factors. The ``approximation factor'' $C$ that is present in our result is inherent in the problem, as we prove that no algorithm with sample size bounded in terms of $k$ and $\eps$ can achieve $C < 2$ regardless of what kind of hypothesis distribution it uses.
Author Information
Siu On Chan (Microsoft Research)
Ilias Diakonikolas (University of Southern California)
Rocco A Servedio (Columbia University)
Xiaorui Sun (Columbia University)
More from the Same Authors
-
2018 Poster: Robust Learning of Fixed-Structure Bayesian Networks »
Yu Cheng · Ilias Diakonikolas · Daniel Kane · Alistair Stewart -
2018 Poster: Sharp Bounds for Generalized Uniformity Testing »
Ilias Diakonikolas · Daniel M. Kane · Alistair Stewart -
2018 Poster: Testing for Families of Distributions via the Fourier Transform »
Alistair Stewart · Ilias Diakonikolas · ClĂ©ment L Canonne -
2018 Spotlight: Sharp Bounds for Generalized Uniformity Testing »
Ilias Diakonikolas · Daniel M. Kane · Alistair Stewart -
2017 Poster: Linear regression without correspondence »
Daniel Hsu · Kevin Shi · Xiaorui Sun -
2011 Poster: Learning large-margin halfspaces with more malicious noise »
Phil Long · Rocco A Servedio -
2011 Poster: Algorithms and hardness results for parallel large margin learning »
Rocco A Servedio · Phil Long -
2011 Spotlight: Algorithms and hardness results for parallel large margin learning »
Rocco A Servedio · Phil Long -
2008 Poster: Adaptive Martingale Boosting »
Phil Long · Rocco A Servedio -
2008 Spotlight: Adaptive Martingale Boosting »
Phil Long · Rocco A Servedio -
2007 Spotlight: One-Pass Boosting »
Zafer Barutcuoglu · Phil Long · Rocco A Servedio -
2007 Poster: One-Pass Boosting »
Zafer Barutcuoglu · Phil Long · Rocco A Servedio -
2007 Spotlight: Boosting the Area under the ROC Curve »
Phil Long · Rocco A Servedio -
2007 Poster: Boosting the Area under the ROC Curve »
Phil Long · Rocco A Servedio -
2006 Poster: Attribute-efficient learning of linear threshold functions under unconcentrated distributions »
Phil Long · Rocco A Servedio