English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Let $p$ be an unknown and arbitrary probability distribution over $[0,1)$. Weconsider the problem of {\em density estimation}, in which a learning algorithmis given i.i.d. draws from $p$ and must (with high probability) output ahypothesis distribution that is close to $p$. The main contribution of thispaper is a highly efficient density estimation algorithm for learning using avariable-width histogram, i.e., a hypothesis distribution with a piecewiseconstant probability density function.  In more detail, for any $k$ and $\epsilon$, we give an algorithm that makes$\tilde{O}(k/\epsilon^2)$ draws from $p$, runs in $\tilde{O}(k/\epsilon^2)$time, and outputs a hypothesis distribution $h$ that is piecewise constant with$O(k \log^2(1/\epsilon))$ pieces. With high probability the hypothesis $h$satisfies $d_{\mathrm{TV}}(p,h) \leq C \cdot \mathrm{opt}_k(p) + \epsilon$,where $d_{\mathrm{TV}}$ denotes the total variation distance (statisticaldistance), $C$ is a universal constant, and $\mathrm{opt}_k(p)$ is the smallesttotal variation distance between $p$ and any $k$-piecewise constantdistribution. The sample size and running time of our algorithm are optimal upto logarithmic factors. The "approximation factor" $C$ in our result isinherent in the problem, as we prove that no algorithm with sample size boundedin terms of $k$ and $\epsilon$ can achieve $C<2$ regardless of what kind ofhypothesis distribution it uses.

Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms