Unverified

Better Differentially Private Learning Algorithms with Margin Guarantees

For binary labels $y\in\{-1,+1\}$ , define the empirical $\rho$ -margin error of a predictor $h$ on a sample $S$ by

\widehat R_S^\rho(h)=\mathbb E_{(x,y)\sim S} [\mathbf 1\{yh(x)\leq\rho\}],

and let $R_D(h)=\Pr_{(x,y)\sim D}[yh(x)\leq0]$ .

Problem 1.

For the linear and kernel-based predictors described above, are there $(\epsilon,\delta)$ -DP algorithms achieving essentially the same guarantees as the known algorithms, with more favorable polynomial dependence on $m$ and $d$ in their running time?

Problem 2.

Let $\mathcal H_{\mathrm{NN}}^\Lambda$ be the family of $L$ -layer feed-forward neural networks on $B^d(r)$ whose weight matrices have Frobenius norm at most $\Lambda$ . Is it possible to prove a margin-based generalization guarantee for private learning with no explicit dependence on the network size? In particular, can a DP algorithm output $h^{\mathrm{Priv}}$ such that

R_D(h^{\mathrm{Priv}})\leq \min_{h\in\mathcal H_{\mathrm{NN}}^\Lambda}\widehat R_S^\rho(h) +O\!\left(\frac{r\Lambda^L}{\rho\sqrt m} +\frac{r^2(2\Lambda)^{2L}}{\rho^2\epsilon m}\right)?

Download

Abstract

The design of efficient differentially private learning algorithms with dimension-independent learning guarantees is a central challenge in privacy-preserving machine learning. A recent work gives confidence-margin guarantees for linear and kernel-based classification and for certain classes of neural networks. Despite these positive results, two fundamental questions remain open: whether the linear and kernel algorithms can have more favorable computational cost, and whether neural-network margin guarantees can avoid explicit dependence on network size.

Background and progress

Let $\mathcal X\subseteq B^d(r)$ , where $B^d(r)=\{x\in\mathbb R^d:\|x\|_2\leq r\}$ , and let $\mathcal H_{\mathrm{Lin}}=\{x\mapsto\langle w,x\rangle:w\in B^d(\Lambda)\}$ . Bassily, Mohri, and Suresh give an $(\epsilon,\delta)$ -differentially private algorithm whose output $w^{\mathrm{Priv}}$ satisfies, with high probability,

R_D(w^{\mathrm{Priv}})\leq \min_{w\in B^d(\Lambda)}\widehat L_S^\rho(w) +\widetilde O\!\left(\frac{\Lambda r}{\rho\sqrt{\min(1,\epsilon)m}}\right),

where $m$ is the sample size, $R_D$ is classification error, and $\widehat L_S^\rho$ is empirical $\rho$ -hinge loss [Bassily et al., 2022]. Their construction uses a Johnson--Lindenstrauss embedding and private empirical-risk minimization, and costs $\widetilde O(md)$ time. A finite-dimensional approximation gives the same margin term for a bounded ball in a shift-invariant-kernel RKHS, but costs $\widetilde O(m^3d)$ time [Bassily et al., 2022].

For $L$ -layer feed-forward networks on $B^d(r)$ , with every weight matrix having Frobenius norm at most $\Lambda$ and every hidden layer having width $N$ , the same work gives a computationally inefficient pure-DP algorithm with a dimension-independent confidence-margin bound. The bound scales linearly with the total number of neurons and contains explicit factors $NL$ . It is more favorable than uniform-convergence bounds depending on the input dimension and total number of edges, but is potentially far from non-private neural-network margin bounds [Bartlett et al., 2017]. In particular, it is unclear whether the explicit dependence on $NL$ is necessary. The two open questions are posed directly in [Bassily et al., 2022].

Reference papers

Open Problem: Better Differentially Private Learning Algorithms with Margin GuaranteesRaef Bassily, Mehryar Mohri, Ananda Theertha SureshProceedings of Thirty Fifth Conference on Learning Theory · 2022 ↗
Differentially Private Learning with Margin GuaranteesRaef Bassily, Mehryar Mohri, Ananda Theertha SuresharXiv preprint arXiv:2204.10376 · 2022
Spectrally-Normalized Margin Bounds for Neural NetworksPeter L. Bartlett, Dylan J. Foster, Matus J. TelgarskyAdvances in Neural Information Processing Systems · 2017

Better Differentially Private Learning Algorithms with Margin Guarantees

Problem 1.

Problem 2.

Coming soon

Organizer