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

We give highly efficient algorithms, and almost matching lower bounds, for arange of basic statistical problems that involve testing and estimating the L_1distance between two k-modal distributions $p$ and $q$ over the discrete domain$\{1,\dots,n\}$. More precisely, we consider the following four problems: givensample access to an unknown k-modal distribution $p$,  Testing identity to a known or unknown distribution:  1. Determine whether $p = q$ (for an explicitly given k-modal distribution$q$) versus $p$ is $\eps$-far from $q$;  2. Determine whether $p=q$ (where $q$ is available via sample access) versus$p$ is $\eps$-far from $q$;  Estimating $L_1$ distance ("tolerant testing'') against a known or unknowndistribution:  3. Approximate $d_{TV}(p,q)$ to within additive $\eps$ where $q$ is anexplicitly given k-modal distribution $q$;  4. Approximate $d_{TV}(p,q)$ to within additive $\eps$ where $q$ is availablevia sample access.  For each of these four problems we give sub-logarithmic sample algorithms,that we show are tight up to additive $\poly(k)$ and multiplicative$\polylog\log n+\polylog k$ factors. Thus our bounds significantly improve theprevious results of \cite{BKR:04}, which were for testing identity ofdistributions (items (1) and (2) above) in the special cases k=0 (monotonedistributions) and k=1 (unimodal distributions) and required $O((\log n)^3)$samples.  As our main conceptual contribution, we introduce a new reduction-basedapproach for distribution-testing problems that lets us obtain all the aboveresults in a unified way. Roughly speaking, this approach enables us totransform various distribution testing problems for k-modal distributions over$\{1,\dots,n\}$ to the corresponding distribution testing problems forunrestricted distributions over a much smaller domain $\{1,\dots,\ell\}$ where$\ell = O(k \log n).$

Testing $k$-Modal Distributions: Optimal Algorithms via Reductions