Learning Structured Distributions From Untrusted Batches: Faster and Simpler

Sitan Chen, Jerry Li, Ankur Moitra

Abstract

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.

Introduction

In modern data collection scenarios, such as federated learning or large-scale crowdsourcing, data is often gathered in "batches" from various sources. While most contributors provide honest data, these systems are inherently vulnerable to a small fraction of malicious actors who may provide adversarially corrupted batches. The challenge is to estimate the true underlying probability distribution $\mu$ despite these untrusted inputs.

This problem, formalized as learning from untrusted batches, has historically presented a trade-off between computational efficiency and sample complexity. Previous research offered two divergent paths: fast, polynomial-time algorithms that required massive amounts of data for large domains, or sample-efficient algorithms that exploited the "shape" of distributions (like log-concavity) but suffered from quasi-polynomial runtimes. This paper bridges that gap, presenting a unified framework that is both fast and sample-efficient.

The Untrusted Batch Model

In the model introduced by Qiao and Valiant, we receive $N$ batches of data, each containing $k$ samples. A fraction $(1-\epsilon)$ of these batches are "good," drawn from the target distribution $\mu$. The remaining $\epsilon$ fraction are "bad" and can be arbitrarily corrupted by an adversary. The goal is to recover $\mu$ with an error that scales optimally with $\epsilon$ and $k$, ideally using a number of batches $N$ that does not depend linearly on the domain size $n$.

Methodology: Synthesizing Structure and Robustness

The core contribution of this work is the synthesis of two powerful techniques: Soft Filtering and Haar Wavelet Analysis.

Soft Filtering

Drawing from recent advances in high-dimensional robust statistics, the algorithm employs a "soft filtering" approach. Rather than attempting to identify and discard malicious batches in a single step—which is often computationally hard—the algorithm maintains a weight for each batch. It iteratively identifies "directions" in the data where the empirical variance significantly exceeds the expected variance for a standard binomial distribution. The algorithm then downweights batches that contribute most to this excess variance. This iterative refinement allows the estimator to converge on the true distribution without the need for hard thresholding.

Haar Wavelets and Shape Constraints

To achieve sublinear sample complexity, the algorithm must exploit the structure of the distribution (e.g., monotonicity, log-concavity, or piecewise polynomial shapes). The authors observe that these shape constraints can be viewed as sparsity constraints when the distribution is represented in the Haar wavelet basis. Structured distributions typically have very few significant sign changes, making them sparse in this basis. By defining a Semidefinite Program (SDP) over a convex relaxation of these Haar-sparse vectors, the algorithm can efficiently search for the "skewed" directions needed for filtering without exploring an exponentially large space.

Technical Innovations

A significant technical simplification in this paper is the removal of the "rounding" step. Previous SDP-based approaches required rounding the solution of the SDP to a concrete vector to perform filtering. This work demonstrates that filtering can be performed directly using the matrix output of the SDP. This not only simplifies the implementation but also provides a more direct theoretical interpretation of the relationship between the cut-norm and robust estimation.

Experimental Results

The authors validated their approach using synthetic datasets, focusing on two scenarios: arbitrary distributions and structured piecewise constant functions.

  1. Sublinear Sample Complexity: The experiments confirmed that the number of batches $N$ required scales with $\log^3(n)$. This is a significant improvement over previous polynomial-time methods; for instance, if the domain size increases from 1,000 to 1,000,000, the required data increases only marginally.
  2. Optimal Error Rates: The algorithm achieves an error of $O(\omega + \frac{\epsilon}{\sqrt{k}} \sqrt{\log 1/\epsilon})$, matching the best known theoretical bounds.
  3. Beating the Oracle: Interestingly, the proposed "Filter" algorithm often outperformed a naive "Oracle" estimator that only saw uncorrupted data. Because the Filter algorithm incorporates the assumed structure of the distribution, it effectively "smooths" the noise even within the good samples, whereas a standard oracle estimator might still be affected by sampling variance.

Conclusion and Future Work

This work provides a "best of both worlds" solution for robustly learning structured distributions, achieving polynomial runtime and sublinear sample complexity. While the algorithm is highly effective for univariate distributions, several avenues for future research remain. There exists a small $\sqrt{\log 1/\epsilon}$ gap between the algorithm's performance and the information-theoretic limit, which may represent a fundamental computational barrier. Additionally, extending these techniques to multi-dimensional distributions and testing the heuristics on non-synthetic, real-world datasets are natural next steps for this research area.

Summary updated

Abstract

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.
BibTeX
@inproceedings{chen2020learning,
  author = {Sitan Chen and Jerry Li and Ankur Moitra},
  title = {{Learning Structured Distributions From Untrusted Batches: Faster and Simpler}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=obafe2EwuU},
}
Figure