  We revisit the problem of learning from untrusted batches introduced by Qiao
and Valiant [QV17]. Recently, Jain and Orlitsky [JO19] gave a simple
semidefinite programming approach based on the cut-norm that achieves
essentially 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 with
sample complexity sublinear in $n$, and they exhibited a quasi-polynomial time
algorithm 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 in
polynomial time and can exploit structure in the underlying distribution to
achieve sublinear sample complexity. Along the way, we simplify the approach of
[JO19] by avoiding the need for SDP rounding and giving a more direct
interpretation of it through the lens of soft filtering, a powerful recent
technique in high-dimensional robust estimation. We validate the usefulness of
our algorithms in preliminary experimental evaluations.
