Learning Structured Distributions From Untrusted Batches: Faster and Simpler

Sitan Chen, Jerry Li, Ankur Moitra

Introduction

This paper tackles a fundamental challenge in robust statistics: learning a probability distribution when data arrives in batches, some of which are intentionally corrupted by an adversary. The authors present a novel algorithm that achieves the "best of both worlds" for this untrusted batches setting. It runs in polynomial time and exploits the underlying structure of the data (such as log-concavity or piecewise polynomials) to achieve sublinear sample complexity. By combining semidefinite programming (SDP) with Haar wavelet analysis, the method provides a faster, simpler, and more robust way to handle adversarial noise in scenarios like federated learning.

The Problem: Untrusted Batches

Imagine collecting data from thousands of users in a crowdsourcing or federated learning application. Most users are "honest" and provide a small batch of samples from a distribution similar to the target distribution $\mu$. However, a small fraction ($\epsilon$) of users are "malicious," providing batches designed to trick the model.

In this setting, previous research faced significant trade-offs:

  1. Efficiency vs. Robustness: Some algorithms were fast but required a massive number of samples proportional to the domain size $n$, which is problematic for high-dimensional data.
  2. Structure vs. Speed: Other algorithms could leverage the "shape" of the distribution to reduce sample requirements but were computationally expensive, running in quasi-polynomial time.

The authors bridge this gap with an algorithm that is both computationally efficient (polynomial time) and sample-efficient (sublinear in $n$).

Methods: LEARNWITHFILTER

The paper introduces an algorithm called LEARNWITHFILTER, built on three technical pillars:

  • Soft Filtering: This iterative approach to robust estimation maintains weights for each batch. In each step, it calculates a "skewness" score. If a batch contributes too much to the skewness in a specific direction, its weight is reduced. Once the skewness is sufficiently low, the weighted average of the remaining batches yields a robust estimate of the true distribution.
  • SDP for Skewness without Rounding: To find the direction of maximum skewness, the authors use a Semidefinite Programming (SDP) relaxation. A key innovation is that they do not "round" the SDP solution back to a simple vector. They demonstrate that the matrix-based skewness measure from the SDP is sufficient for filtering, dramatically simplifying both the algorithm and its theoretical proof.
  • Haar Wavelets for Structure: To exploit the shape of the distribution, they use Haar wavelets. Structured distributions are "sparse" in the Haar basis. By constraining the SDP to look for skewness only in analytically sparse directions, the algorithm can learn the distribution using far fewer batches than an unstructured approach would require.

Experiments and Key Results

The authors evaluated their approach using synthetic datasets to precisely control corruption levels and distribution structures. They tested arbitrary distributions using the $A_{\ell/2}$ norm and structured distributions (piecewise constant functions) using Total Variation (TV) / $L_1$ distance.

Performance on arbitrary distributions measured in A_ell/2 distance

Key Insights: * The Variance Proxy: Standard variance checks fail because even "good" multinomial batches have high variance in certain directions. The authors use a "variance proxy"—the difference between observed variance and the expected variance of a clean batch—to isolate adversarial effects. * Shape as a Regularizer: Incorporating Haar wavelet constraints into the SDP allows the algorithm to use the expected structure of the distribution as a shield against noise.

Performance on structured distributions measured in L_1 distance

Performance Highlights: * Theoretical Guarantee: The algorithm estimates an $s$-part, degree-$d$ piecewise polynomial distribution to within an error of $O(\eta + \omega + \frac{\epsilon}{\sqrt{k}} \sqrt{\log 1/\epsilon})$ in TV distance. * Sample Complexity: The number of required batches scales with $\log^3 n$ (independent of the domain size $n$), making it highly effective for large domains. * Outperforming the Oracle: As seen in the $L_1$ distance results, LEARNWITHFILTER often outperformed the "oracle" estimator (which knows exactly which batches are good but ignores distribution structure). By exploiting structure, the algorithm effectively "denoises" even the honest batches when sample sizes are small.

Limitations and Future Work

  • The Statistical Gap: There remains a known gap of $\sqrt{\log 1/\epsilon}$ between what is information-theoretically possible and what current polynomial-time algorithms achieve. This gap might be unavoidable for efficient algorithms.
  • Sample Complexity Tightness: While sublinear, the dependence on the number of pieces ($s$) and degree ($d$) might be improvable from $s^2 d^2$ to $sd$.
  • Real-World Validation: Applying this theoretical framework to real-world federated learning datasets (e.g., image or text data) is a crucial next step.

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 μ 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.
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