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/

Zendy Plus

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

Zendy Tools

Zendy Open

Bregman divergences $D_\phi$ are a class of divergences parametrized by aconvex function $\phi$ and include well known distance functions like$\ell_2^2$ and the Kullback-Leibler divergence. There has been extensiveresearch on algorithms for problems like clustering and near neighbor searchwith respect to Bregman divergences, in all cases, the algorithms depend notjust on the data size $n$ and dimensionality $d$, but also on a structureconstant $\mu \ge 1$ that depends solely on $\phi$ and can grow without boundindependently.  In this paper, we provide the first evidence that this dependence on $\mu$might be intrinsic. We focus on the problem of approximate near neighbor searchfor Bregman divergences. We show that under the cell probe model, anynon-adaptive data structure (like locality-sensitive hashing) for$c$-approximate near-neighbor search that admits $r$ probes must use space$\Omega(n^{1 + \frac{\mu}{c r}})$. In contrast, for LSH under $\ell_1$ the bestbound is $\Omega(n^{1+\frac{1}{cr}})$.  Our new tool is a directed variant of the standard boolean noise operator. Weshow that a generalization of the Bonami-Beckner hypercontractivity inequalityexists "in expectation" or upon restriction to certain subsets of the Hammingcube, and that this is sufficient to prove the desired isoperimetric inequalitythat we use in our data structure lower bound.  We also present a structural result reducing the Hamming cube to a Bregmancube. This structure allows us to obtain lower bounds for problems underBregman divergences from their $\ell_1$ analog. In particular, we get a(weaker) lower bound for approximate near neighbor search of the form$\Omega(n^{1 + \frac{1}{cr}})$ for an $r$-query non-adaptive data structure,and new cell probe lower bounds for a number of other near neighbor questionsin Bregman space.

A directed isoperimetric inequality with application to Bregman near neighbor lower bounds