Multiclass versus Binary Differentially Private PAC Learning

Satchit Sivakumar, Mark Bun, Marco Gaboardi

Introduction

In machine learning, training models on sensitive data—such as medical records or financial histories—without compromising individual privacy is a critical challenge. Differentially Private (DP) PAC Learning provides the mathematical framework to study this. While binary private learning (e.g., deciding between "Healthy" or "Sick") is well-understood, multiclass learning (deciding among $k$ labels) has remained a significant hurdle.

Previously, the "cost" of privacy in multiclass learning, measured by sample complexity, grew exponentially with both the number of classes and the complexity of the problem. This paper provides a breakthrough "bridge" between simple binary classification and complex multiclass learning within the DP framework. The authors present a generic reduction that allows researchers to solve multiclass private learning problems by breaking them down into a series of binary ones, leading to a doubly exponential improvement in sample efficiency over previous methods.

The Generic Reduction Method

The authors propose a generic reduction that avoids learning a multiclass function $f: \mathcal{X} \to [k]$ all at once. Instead, they treat the label as a bitstring. To learn a label among $k$ possibilities, the algorithm only needs to learn $\log(k+1)$ bits.

Generic reduction from multiclass to binary private learning

The core algorithm operates in three main steps:

  1. Data Splitting: The sensitive training dataset is divided into $\log(k+1)$ separate partitions.
  2. Binary Learning: For each bit position $i$, a standard binary DP learner (Algorithm B) is used to learn the $i$-th bit of the target label using one of the data partitions.
  3. Reconstruction: The predicted bits are combined (converted from binary to decimal) to form the final multiclass prediction.

Because each partition of the data is used for only one binary learner, the privacy "leakage" is strictly controlled. The theoretical heavy lifting of the paper is a mathematical proof demonstrating that if the original multiclass problem is "learnable" (i.e., has a bounded multiclass Littlestone dimension), then each of these artificial binary problems is also learnable with a bounded binary Littlestone dimension.

To prove this, the authors introduce a new combinatorial tool called the $\Psi$-Littlestone dimension, extending an online learning version of a concept used in classical (non-private) learning theory.

Key Insights and Results

  • The "Bit-by-Bit" Revelation: Learning a multiclass label "one bit at a time" is proven to be a formally sound method to preserve privacy while maintaining high accuracy, rather than just a practical heuristic.
  • Connecting Online and Private Learning: The paper reinforces the deep connection between online learning and private learning. It demonstrates that the Littlestone dimension—a measure of online learning difficulty—is the "master key" for multiclass privacy.
  • Doubly Exponential Improvement: The new approach yields a sample complexity with a polynomial dependence on the Littlestone dimension ($d$) and a poly-logarithmic dependence on the number of classes ($k$). This is a massive leap over previous best bounds, which were exponential in both parameters.
  • Concrete Bounds and Tightness: The authors show that a multiclass class with Littlestone dimension $d$ can be privately learned using $\tilde{O}(d^6 \log^8(k+1))$ samples. Furthermore, they prove that their relationship between multiclass and binary Littlestone dimensions is nearly tight.

Limitations and Future Work

While the theoretical improvements are substantial, the paper notes several limitations and avenues for future research:

  • The $d^6$ Factor: The polynomial dependence on the Littlestone dimension ($d^6$) remains quite high. However, if binary private learning becomes more efficient in the future, this multiclass reduction will automatically inherit those efficiency gains.
  • Realizable Setting: The current work focuses on the "realizable" setting, assuming a perfect classifier exists within the chosen hypothesis class. Extending these tight bounds to the "agnostic" setting (where the best classifier might still make mistakes) is an open challenge.
  • Computational Efficiency: The paper focuses on sample complexity rather than computational complexity. Some of the underlying binary learners used in the reduction may still be computationally expensive to execute in practice.

Summary updated

Abstract

We show a generic reduction from multiclass differentially private PAC learning to binary private PAC learning. We apply this transformation to a recently proposed binary private PAC learner to obtain a private multiclass learner with sample complexity that has a polynomial dependence on the multiclass Littlestone dimension and a poly-logarithmic dependence on the number of classes. This yields a doubly exponential improvement in the dependence on both parameters over learners from previous work. Our proof extends the notion of $\Psi$-dimension defined in work of Ben-David et al. [JCSS, 1995] to the online setting and explores its general properties.
BibTeX
@inproceedings{sivakumar2021multiclass,
  author = {Satchit Sivakumar and Mark Bun and Marco Gaboardi},
  title = {{Multiclass versus Binary Differentially Private PAC Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=RsNYEVyd-4B},
}
Figure