A Unified Characterization of Private Learnability via Graph Theory

Noga Alon, Shay Moran, Hilla Schefler, Amir Yehudayoff
Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:94-129, 2024.

Abstract

We provide a unified framework for characterizing pure and approximate differentially private (DP) learnability. The framework uses the language of graph theory: for a concept class $\mathcal{H}$, we define the contradiction graph $G$ of $\mathcal{H}$. Its vertices are realizable datasets and two datasets $S,S’$ are connected by an edge if they contradict each other (i.e., there is a point $x$ that is labeled differently in $S$ and $S’$). Our main finding is that the combinatorial structure of $G$ is deeply related to learning $\mathcal{H}$ under DP. Learning $\mathcal{H}$ under pure DP is captured by the fractional clique number of $G$. Learning $\mathcal{H}$ under approximate DP is captured by the clique number of $G$. Consequently, we identify graph-theoretic dimensions that characterize DP learnability: the \emph{clique dimension} and \emph{fractional clique dimension}. Along the way, we reveal properties of the contradiction graph which may be of independent interest. We also suggest several open questions and directions for future research.

Cite this Paper

BibTeX
@InProceedings{pmlr-v247-alon24a, title = {A Unified Characterization of Private Learnability via Graph Theory}, author = {Alon, Noga and Moran, Shay and Schefler, Hilla and Yehudayoff, Amir}, booktitle = {Proceedings of Thirty Seventh Conference on Learning Theory}, pages = {94--129}, year = {2024}, editor = {Agrawal, Shipra and Roth, Aaron}, volume = {247}, series = {Proceedings of Machine Learning Research}, month = {30 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v247/alon24a/alon24a.pdf}, url = {https://proceedings.mlr.press/v247/alon24a.html}, abstract = {We provide a unified framework for characterizing pure and approximate differentially private (DP) learnability. The framework uses the language of graph theory: for a concept class $\mathcal{H}$, we define the contradiction graph $G$ of $\mathcal{H}$. Its vertices are realizable datasets and two datasets $S,S’$ are connected by an edge if they contradict each other (i.e., there is a point $x$ that is labeled differently in $S$ and $S’$). Our main finding is that the combinatorial structure of $G$ is deeply related to learning $\mathcal{H}$ under DP. Learning $\mathcal{H}$ under pure DP is captured by the fractional clique number of $G$. Learning $\mathcal{H}$ under approximate DP is captured by the clique number of $G$. Consequently, we identify graph-theoretic dimensions that characterize DP learnability: the \emph{clique dimension} and \emph{fractional clique dimension}. Along the way, we reveal properties of the contradiction graph which may be of independent interest. We also suggest several open questions and directions for future research.} }
Endnote
%0 Conference Paper %T A Unified Characterization of Private Learnability via Graph Theory %A Noga Alon %A Shay Moran %A Hilla Schefler %A Amir Yehudayoff %B Proceedings of Thirty Seventh Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2024 %E Shipra Agrawal %E Aaron Roth %F pmlr-v247-alon24a %I PMLR %P 94--129 %U https://proceedings.mlr.press/v247/alon24a.html %V 247 %X We provide a unified framework for characterizing pure and approximate differentially private (DP) learnability. The framework uses the language of graph theory: for a concept class $\mathcal{H}$, we define the contradiction graph $G$ of $\mathcal{H}$. Its vertices are realizable datasets and two datasets $S,S’$ are connected by an edge if they contradict each other (i.e., there is a point $x$ that is labeled differently in $S$ and $S’$). Our main finding is that the combinatorial structure of $G$ is deeply related to learning $\mathcal{H}$ under DP. Learning $\mathcal{H}$ under pure DP is captured by the fractional clique number of $G$. Learning $\mathcal{H}$ under approximate DP is captured by the clique number of $G$. Consequently, we identify graph-theoretic dimensions that characterize DP learnability: the \emph{clique dimension} and \emph{fractional clique dimension}. Along the way, we reveal properties of the contradiction graph which may be of independent interest. We also suggest several open questions and directions for future research.
APA
Alon, N., Moran, S., Schefler, H. & Yehudayoff, A.. (2024). A Unified Characterization of Private Learnability via Graph Theory. Proceedings of Thirty Seventh Conference on Learning Theory, in Proceedings of Machine Learning Research 247:94-129 Available from https://proceedings.mlr.press/v247/alon24a.html.

Related Material