2024-06-30-alon24a.md

title	section	abstract	layout	series	publisher	issn	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_author	author	date	address	container-title	volume	genre	issued	pdf	extras
A Unified Characterization of Private Learnability via Graph Theory	Original Papers	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.	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	alon24a	0	A Unified Characterization of Private Learnability via Graph Theory	94	129	94-129	94	false	Alon, Noga and Moran, Shay and Schefler, Hilla and Yehudayoff, Amir	given family Noga Alon given family Shay Moran given family Hilla Schefler given family Amir Yehudayoff	2024-06-30		Proceedings of Thirty Seventh Conference on Learning Theory	247	inproceedings	date-parts 2024 6 30	https://proceedings.mlr.press/v247/alon24a/alon24a.pdf