Is Margin Sufficient for Non-Interactive Private Distributed Learning?

§ Problem Statement

Setup

Let $X$ be a domain and let $C$ be a class of Boolean functions $f:X\to\{-1,1\}$ . For $d\ge 1$ , let $B_d(1)=\{u\in\mathbb{R}^d:\|u\|_2\le 1\}$ . The margin complexity of $C$ , denoted $MC(C)$ , is the minimum $M\ge 1$ such that there exist a dimension $d$ and an embedding $\Psi:X\to B_d(1)$ with the property that for every $f\in C$ there exists a vector $w\in B_d(1)$ satisfying

\min_{x\in X} f(x)\,\langle w,\Psi(x)\rangle \ge \frac{1}{M}.

(Non-interactive local differential privacy.) Let $Z=X\times\{-1,1\}$ . An $\varepsilon$ -local randomizer is a randomized map $R:Z\to W$ such that for all $z,z'\in Z$ and all measurable events $S\subseteq W$ ,

\Pr[R(z)\in S] \le e^{\varepsilon}\Pr[R(z')\in S].

A non-interactive $\varepsilon$ -LDP (distribution-independent) PAC learner for $C$ works as follows: given $n$ i.i.d. labeled examples $(x_i,y_i)$ where $x_i\sim D$ for an arbitrary distribution $D$ over $X$ and $y_i=f(x_i)$ for some unknown target $f\in C$ , each example is accessed only once by applying a fixed (non-adaptive) $\varepsilon$ -local randomizer to produce messages $w_i=R(x_i,y_i)$ ; the learner then outputs a hypothesis $h:X\to\{-1,1\}$ .

Unsolved Problem

Problem 1. Does there exist a polynomial $p(\cdot)$ such that for every class $C$ , every accuracy parameter $\alpha\in(0,1/2)$ , and every distribution $D$ over $X$ , there is a non-interactive $1$ -LDP PAC learner that, using

n \le p\bigl(MC(C),1/\alpha\bigr)

examples, outputs (with probability at least $2/3$ over its randomness and the sample) a hypothesis $h$ satisfying $\Pr_{x\sim D}[h(x)\ne f(x)]\le \alpha$ for every target $f\in C$ ?

§ Discussion

Loading discussion…

§ Significance & Implications

This problem asks whether a single geometric complexity parameter, $MC(C)$ , suffices to guarantee efficient (polynomial-sample) distribution-independent PAC learning in the strict non-interactive $1$ -LDP model, where each user sends only one privatized message and the server cannot adapt queries across users. A positive answer would give a broadly applicable, model-specific characterization of which Boolean classes admit one-round locally private learning with sample complexity controlled by $MC(C)$ and $1/\alpha$ . A negative answer would demonstrate that polynomial margin complexity alone does not capture the information constraints of non-interactive local privacy, implying that either additional structure/complexity measures or interaction is inherently necessary for some classes even when $MC(C)$ is small.

§ Known Partial Results

Daniely et al. (2019): Daniely and Feldman (COLT 2019) formulate the question of whether polynomial margin complexity implies efficient non-interactive locally differentially private PAC learning (distribution-independently) for Boolean concept classes.
Daniely et al. (2019): The open problem isolates margin complexity as the candidate controlling parameter and fixes the learning model to the strongest common non-interactivity requirement: one privatized message per example with no adaptivity across examples.

§ References

[1]

Open Problem: Is Margin Sufficient for Non-Interactive Private Distributed Learning?

Amit Daniely, Vitaly Feldman (2019)

Conference on Learning Theory (COLT), PMLR 99

📍 Open-problem note in COLT proceedings.

Link ↗

[2]

Open Problem: Is Margin Sufficient for Non-Interactive Private Distributed Learning? (PDF)

Amit Daniely, Vitaly Feldman (2019)

Conference on Learning Theory (COLT), PMLR 99

📍 Proceedings PDF.

Link ↗

§ Tags

colt-open-problem learning-theory differential-privacy