A Unified Characterization of Private Learnability via Graph Theory

• URL: http://arxiv.org/abs/2304.03996v4
• Date: Wed, 12 Jun 2024 10:19:23 GMT
• Title: A Unified Characterization of Private Learnability via Graph Theory
• Authors: Noga Alon, Shay Moran, Hilla Schefler, Amir Yehudayoff,
• Abstract summary: We provide a unified framework for characterizing pure and approximate differentially private (DP) learnability. We identify graph-theoretic dimensions that characterize DP learnability: the clique dimension and fractional clique dimension. We also reveal properties of the contradiction graph which may be of independent interest.
• Score: 18.364498500697596
• License: http://creativecommons.org/licenses/by/4.0/
• 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 clique dimension and 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.

Related papers

• Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
  User-generated videos (UGVs) uploaded from mobile phones to social media sites like YouTube and TikTok are short and non-repetitive. We summarize a transitory UGV into several discs in linear time via fast graph sampling based on Gershgorin disc alignment (GDA) We show that our algorithm achieves comparable or better video summarization performance compared to state-of-the-art methods, at a substantially reduced complexity.
  arXiv  Detail & Related papers  (2024-08-03T20:08:02Z)
• Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
  We study the problem of gradient descent learning of a single-index target function $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ under isotropic Gaussian data. We prove that a two-layer neural network optimized by an SGD-based algorithm learns $f_*$ of arbitrary link function with a sample and runtime complexity of $n asymp T asymp C(q) cdot d
  arXiv  Detail & Related papers  (2024-06-03T17:56:58Z)
• Non-Clashing Teaching Maps for Balls in Graphs [0.05356944479760104]
  We show that the associated decision problem B-NCTD$+$ for NCTD$+$ is NP-complete in split, co-bipartite, and bipartite graphs. We also prove that, unless the ETH fails, B-NCTD$+$ does not admit an algorithm running in time $22o(textvc)cdot nO(1)$, nor a kernelization algorithm outputting a kernel with $2o(textvc)cdot nO(1)$.
  arXiv  Detail & Related papers  (2023-09-06T10:02:58Z)
• Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
  Detection of a planted dense subgraph in a random graph is a fundamental statistical and computational problem. We consider detecting the presence of a planted $Gr(ngamma, n-alpha)$ subhypergraph in a $Gr(n, n-beta) hypergraph. Our results are already new in the graph case $r=2$, as we consider the subtle log-density regime where hardness based on average-case reductions is not known.
  arXiv  Detail & Related papers  (2023-04-17T10:38:08Z)
• Learning on the Edge: Online Learning with Stochastic Feedback Graphs [12.83118601099289]
  We study an extension where the directed feedback graph is bandit. In each round every edge in the graph is either realized or not with a distinct probability for each edge. We derive a more efficient algorithm featuring a dependence on weighted versions of the independence and weak domination numbers.
  arXiv  Detail & Related papers  (2022-10-09T11:21:08Z)
• On Optimal Learning Under Targeted Data Poisoning [48.907813854832206]
  In this work we aim to characterize the smallest achievable error $epsilon=epsilon(eta)$ by the learner in the presence of such an adversary. Remarkably, we show that the upper bound can be attained by a deterministic learner.
  arXiv  Detail & Related papers  (2022-10-06T06:49:48Z)
• Random Graph Matching in Geometric Models: the Case of Complete Graphs [21.689343447798677]
  This paper studies the problem of matching two complete graphs with edge weights correlated through latent geometries. We derive an approximate maximum likelihood estimator, which provably achieves, with high probability, perfect recovery of $pi*$. As a side discovery, we show that the celebrated spectral algorithm of [Ume88] emerges as a further approximation to the maximum likelihood in the geometric model.
  arXiv  Detail & Related papers  (2022-02-22T04:14:45Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  We study the problem of efficiently summarizing a short video into several paragraphs, leveraging recent progress in fast graph sampling. Experimental results show that our algorithm achieves comparable video summarization as state-of-the-art methods, at a substantially reduced complexity.
  arXiv  Detail & Related papers  (2021-10-21T18:43:00Z)
• Exact Matching of Random Graphs with Constant Correlation [2.578242050187029]
  This paper deals with the problem of graph matching or network alignment for ErdHos--R'enyi graphs. It can be viewed as a noisy average-case version of the graph isomorphism problem.
  arXiv  Detail & Related papers  (2021-10-11T05:07:50Z)
• Learning Sparse Graph Laplacian with K Eigenvector Prior via Iterative GLASSO and Projection [58.5350491065936]
  We consider a structural assumption on the graph Laplacian matrix $L$. The first $K$ eigenvectors of $L$ are pre-selected, e.g., based on domain-specific criteria. We design an efficient hybrid graphical lasso/projection algorithm to compute the most suitable graph Laplacian matrix $L* in H_u+$ given $barC$.
  arXiv  Detail & Related papers  (2020-10-25T18:12:50Z)
• Block Model Guided Unsupervised Feature Selection [32.21728295212875]
  We present a novel approach for graph-driven unsupervised feature selection for linked data. We take the novel approach of first building a block model on the graph and then using the block model for feature selection. Experimental results show that our method outperforms the state of the art on several real-world public datasets.
  arXiv  Detail & Related papers  (2020-07-05T16:19:47Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.