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 revisit the problem of learning from untrusted batches introduced by Qiaoand Valiant [QV17]. Recently, Jain and Orlitsky [JO19] gave a simplesemidefinite programming approach based on the cut-norm that achievesessentially information-theoretically optimal error in polynomial time.Concurrently, Chen et al. [CLM19] considered a variant of the problem where$\mu$ is assumed to be structured, e.g. log-concave, monotone hazard rate,$t$-modal, etc. In this case, it is possible to achieve the same error withsample complexity sublinear in $n$, and they exhibited a quasi-polynomial timealgorithm for doing so using Haar wavelets.  In this paper, we find an appealing way to synthesize the techniques of[JO19] and [CLM19] to give the best of both worlds: an algorithm which runs inpolynomial time and can exploit structure in the underlying distribution toachieve sublinear sample complexity. Along the way, we simplify the approach of[JO19] by avoiding the need for SDP rounding and giving a more directinterpretation of it through the lens of soft filtering, a powerful recenttechnique in high-dimensional robust estimation. We validate the usefulness ofour algorithms in preliminary experimental evaluations.

Learning Structured Distributions From Untrusted Batches: Faster and Simpler