📊 statistics

Privately Learning Decision Lists and a Differentially Private Winnow

This paper presents new differentially private algorithms for learning decision lists and large-margin halfspaces in both PAC and online models, achieving near-optimal sample complexity and mistake bounds compared to non-private methods.

Original authors: Mark Bun, William Fang

Published 2026-02-10

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Mark Bun, William Fang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a mystery, but there’s a catch: you have to solve it without ever looking at the suspects' faces or knowing their names. You can only look at the "clues" they leave behind (like their footprints or the type of shoes they wear).

This paper is about how to teach a computer to learn patterns (like "if a person wears red shoes, they are a suspect") while strictly protecting the privacy of the individuals involved.

The researchers tackle two specific types of "detective work": Decision Lists and Winnowing.

1. The Decision List: The "Flowchart" Detective

The Concept: A decision list is like a simple flowchart.

If the person is wearing a hat $\rightarrow$ they are a "Type A."
Else, if they are carrying an umbrella $\rightarrow$ they are a "Type B."
Else $\rightarrow$ they are a "Type C."

The Problem: Usually, to build this flowchart, a computer looks at every single person in a crowd to see which rules work best. But if the computer "memorizes" that "the person in the blue hat at 2:00 PM was a Type A," it has leaked that person's private information.

The Solution (DP-GreedyCover): The authors created a way to build this flowchart using something called the "Exponential Mechanism."

The Analogy: Imagine you are picking the best rule for your flowchart, but instead of just picking the absolute best rule, you pick from a hat containing many rules. The "best" rules are at the top of the hat, and the "bad" rules are at the bottom. By adding a little bit of randomness (picking a rule that is almost the best, but not necessarily the best), you ensure that no single person’s data can tip the scales too much. It’s like a jury that makes a decision based on a general consensus rather than being swayed by one single, loud witness.

2. The Winnow: The "Weighty" Detective

The Concept: This is for much more complex patterns. Instead of a simple "if-then" list, imagine you are trying to figure out which of 1,000 different clues are actually important. This is called "learning halfspaces."

The Problem: In an "online" setting, clues come in one by one, like a constant stream of information. You have to make a guess immediately, and if you're wrong, you update your knowledge. If you update your knowledge too specifically based on one mistake, you've "leaked" that the person who caused that mistake was special.

The Solution (DP-Winnow): They created a "Private Winnow" algorithm.

The Analogy: Imagine you are a chef trying to perfect a secret soup recipe. Every time someone tastes it and says "too salty," you adjust the salt.

The Non-Private Way: You change the recipe exactly to suit that one person's taste. (Privacy leak!)
The Private Way (The Paper's Method): You use a "Sparse Vector" technique. Instead of changing the recipe every single time someone complains, you keep a "secret tally" of complaints. You only change the recipe once you’ve reached a certain threshold of complaints.

By waiting until you have a "cluster" of evidence before making a change, you ensure that one single person's opinion doesn't change the recipe. This keeps the recipe (the algorithm) private while still allowing it to eventually become perfect.

Summary: Why does this matter?

In the real world, we use these types of algorithms for high-stakes things like healthcare (predicting disease risk) and finance (detecting fraud).

If a hospital uses a "Decision List" to predict heart disease, they want the list to be accurate, but they cannot allow the list to reveal that "Patient X has a specific heart condition." This paper provides the mathematical "shield" that allows computers to be incredibly smart and accurate while remaining completely respectful of individual privacy.

Technical Summary: Privately Learning Decision Lists and a Differentially Private Winnow

Authors: Mark Bun (Boston University) and William Fang (Boston University)
Venue: 37th International Conference on Algorithmic Learning Theory (ALT 2026)

1. Problem Statement

The paper addresses the challenge of maintaining Differential Privacy (DP) while learning fundamental concept classes in computational learning theory. Specifically, it targets two classic problems:

Learning Decision Lists in the PAC Model: Decision lists (sequences of "if-then-else" rules) are highly interpretable and widely used in sensitive domains like healthcare and finance. While they are efficiently learnable in the non-private Probably Approximately Correct (PAC) model, the authors investigate whether adding privacy constraints significantly degrades their sample complexity or computational efficiency.
Learning Large-Margin Halfspaces in the Online Model: In the online learning setting, a learner must make predictions sequentially, minimizing mistakes against an adversary. The goal is to develop a private version of the Winnow algorithm, which is "attribute-efficient" (its mistake bound depends polylogarithmically on the dimension $d$ ).

2. Methodology

A. For Decision Lists (PAC Model): DP-GreedyCover
The authors propose DP-GreedyCover, an iterative algorithm that mimics Rivest’s classic greedy approach.

Mechanism: Instead of choosing the best feature deterministically (which would leak privacy), the algorithm uses the Exponential Mechanism to select a feature-label pair $(f, b)$ that minimizes classification error on the remaining unclassified samples.
Privacy Analysis: To avoid the massive privacy loss associated with standard composition (which would lead to a sub-optimal sample complexity of $\tilde{O}(|F|^{3/2})$ ), the authors leverage a specialized analysis for iterative Exponential Mechanism-based covering algorithms. They show that the structure follows a template similar to approximate Set Cover, allowing for a much sharper privacy bound.

B. For Halfspaces (Online Model): DP-Winnow
The authors introduce DP-Winnow, a private analog of the Winnow algorithm designed for large-margin halfspaces.

ConfidentWinnow (Subroutine): They first design a non-private variant called ConfidentWinnow. Unlike standard Winnow, it only updates its weight vector when it is either incorrect or "unconfident" (i.e., the prediction margin is too small). This ensures that "confident correct" predictions are robust to the noise introduced by privacy mechanisms.
Sparse Vector Technique (SVT): To handle the privacy of the timing of updates (since the sequence of update rounds can leak information), they integrate the Sparse Vector Technique. This ensures the privacy cost scales with the number of updates rather than the total time horizon $T$ .
Weight Approximation: Instead of releasing the exact weight vector $w$ , the algorithm releases a randomized approximation $\tilde{w}$ obtained by sampling from a multiplicative weights distribution.

3. Key Contributions and Results

Efficient PAC Learning of Decision Lists:
- Result: The algorithm achieves an $(\epsilon, \delta)$ -DP $(\alpha, \beta)$ -PAC learner.
- Complexity: It uses $\tilde{O}(|F| \cdot \log(1/\delta)/\epsilon)$ samples and runs in $\text{poly}(|F|)$ time. This matches the sample complexity of the best non-private algorithms up to logarithmic factors.
Private Online Learning of Halfspaces:
- Result: The algorithm achieves a mistake bound (regret) that is polylogarithmic in the dimension $d$ and the time horizon $T$ , and inverse polynomial in the margin $\rho$ .
- Complexity: The mistake bound is $\tilde{O}\left(\frac{\log^3 d \cdot \log^{5/2}(T/\beta) \cdot \log^2(1/\delta)}{\epsilon^4 \rho^6}\right)$ . This is a significant result because most private online convex optimization techniques scale polynomially with $d$ .
Application to Decision Lists:
- The authors demonstrate that DP-Winnow can be used to privately learn decision lists in the online model, providing a qualitative match to state-of-the-art non-private guarantees.

4. Significance

This paper bridges a critical gap between computational learning theory and privacy-preserving machine learning.

Breaking the Dimensionality Barrier: In the online setting, the authors successfully move beyond algorithms that scale polynomially with dimension $d$ , achieving the "attribute-efficient" polylogarithmic dependence required for high-dimensional data.
Preserving Interpretability: By providing efficient private learners for decision lists, the paper enables the deployment of highly interpretable models in privacy-sensitive, high-stakes environments (like finance and medicine) without sacrificing the efficiency of the learning process.
Theoretical Robustness: The work provides new insights into how structural properties of algorithms (like the "confidence" in Winnow or the "covering" nature of decision lists) can be exploited to achieve optimal privacy-utility trade-offs.