Introduction
Learning halfspaces is a classical problem in learning theory. A halfspace is specified by a weight vector w ∈ R d w \in\mathbb{R}^{d} w ∈ R d t ∈ R t \in\mathbb{R} t ∈ R x ∈ R d x \in\mathbb{R}^{d} x ∈ R d sign ( ⟨ w , x ⟩ + t ) \operatorname{sign}(\langle w,x\rangle+ t) sign (⟨ w , x ⟩ + t ) P P P μ = P X \mu= P_{X} μ = P X realizable PAC learning, the distribution P P P h h h err P ( h ) ≤ α \operatorname{err}_{P}(h) \le\alpha err P ( h ) ≤ α α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) agnostic setting, the labels in the dataset may be arbitrary. Thus, the guarantee is relaxed to requiring the learner to output a classifier h h h
err P ( h ) ≤ OPT + α , \operatorname{err}_{P}(h) \le\operatorname{OPT} + \alpha, err P ( h ) ≤ OPT + α , where OPT is the minimum error achievable by a halfspace under P P P [21 ] imposes an additional constraint, requiring the distribution of the learner’s output to change only slightly when a single training example is replaced. In this paper, we study whether agnostic halfspace learning can be made differentially private with small computational and statistical overhead relative to non-private learning.
Agnostically learning halfspaces is known to be computationally hard, even for non-private improper learners, i.e., learners whose output need not be a halfspace Tiegel [48 ] . To overcome this, a rich line of work has focused on distributions with structured marginals but arbitrary labels. Under Gaussian and more generally log-concave marginals, Kalai et al. [29 ] provided the first algorithm for agnostic learning of halfspaces whose runtime is polynomial in the dimension for every fixed accuracy. For Gaussian marginals, their complexity scales as d O ( 1 / α 4 ) d^{O(1/\alpha^{4})} d O ( 1/ α 4 ) d O ( 1 / α 2 ) d^{O(1/\alpha^{2})} d O ( 1/ α 2 ) [11 ] . However, their algorithm was improper. A proper algorithm must output a halfspace and can be desirable because a linear halfspace offers a more compact and interpretable representation of the classifier with O ( d ) O(d) O ( d ) [15 ] provided the first agnostic proper learner for halfspaces with somewhat comparable statistical and computational complexity. For DP agnostic learning, Kasiviswanathan et al. [34 ] provided the first agnostic private learners for finite classes with sample complexity scaling logarithmically in the size of the hypothesis class. Alon et al. [2 ] and Li et al. (2025) provided general reductions from agnostic learning to realisable learning. However, their reductions are not shown to be computationally efficient. For halfspaces over finite domains, Beimel et al. [6 ] provided efficient private agnostic learners, but over infinite domains such as R d \mathbb{R}^d R d [7 , 1 ] ). Distributional assumptions on the marginal μ \mu μ [29 , 15 ] ), our goal in this work is to obtain matching statistical and computational complexities under differential privacy.
However, even under Gaussian marginals, the d O ( 1 / α 2 ) d^{O(1/\alpha^2)} d O ( 1/ α 2 ) [16 , 25 ] ). A natural relaxation for the problem is semi-agnostic proper learning , which allows halfspaces h h h
err P ( h ) ≤ C ⋅ O P T + α , \operatorname{err}_{P}(h) \le C\cdot\mathrm{OPT}+\alpha, err P ( h ) ≤ C ⋅ OPT + α , where C C C d d d 1 / α 1/\alpha 1/ α [17 ] ). This raises the natural question of whether the polynomial dependence on d d d 1 / α 1/\alpha 1/ α
What statistical and computational guarantees can DP algorithms get under Gaussian marginals for i) agnostic improper, ii) agnostic proper, and iii) semi-agnostic proper learning of halfspaces?
Our Results
Table 1 summarizes our results. All algorithms satisfy ( ε D P , δ D P ) (\varepsilon_{\mathrm{DP}},\delta_{\mathrm{DP}}) ( ε DP , δ DP ) O ~ ( ⋅ ) \widetilde{O}(\cdot) O ( ⋅ ) 1 / α 1/\alpha 1/ α 1 / β 1/\beta 1/ β 1 / ε D P 1/\varepsilon_{\mathrm{DP}} 1/ ε DP 1 / δ D P 1/\delta_{\mathrm{DP}} 1/ δ DP
Table 1. The rows correspond, respectively, to Theorem 2.1 , Theorem D.1 , Theorem 3.1 , and Theorem 4.1 . Here, D G ≍ d O ( 1 / α 2 ) D_{\mathrm{G}}\asymp d^{O(1/\alpha^2)} D G ≍ d O ( 1/ α 2 ) D L ≍ d exp ( O ( 1 / α ) ) D_{\mathrm{L}}\asymp d^{\exp(O(1/\alpha))} D L ≍ d e x p ( O ( 1/ α )) [11 , 29 ] ), and O ~ \widetilde{O} O
Agnostic Improper learning. Our first result in § 2 gives a private improper agnostic learner under the standard Gaussian marginal. The algorithm relies on private polynomial L 1 L^1 L 1 O ( 1 / α 2 ) O(1/\alpha^2) O ( 1/ α 2 ) + α +\alpha + α
n = O ~ ( D p α 2 + D p α ε D P ) where D p = ( d + p p ) (1) n = \widetilde{O}\left(\frac{D_p}{\alpha^2}+\frac{D_p}{\alpha\varepsilon_{\mathrm{DP}}}\right) \quad\text{where} \quad D_p = \binom{d+p}{p} \tag*{(1)} n = O ( α 2 D p + α ε DP D p ) where D p = ( p d + p ) (1) The first term in Equation (1) is the statistical cost of the problem due to finite samples and the second term is the cost due to privacy. In Appendix § 10 , we extend this approach to known log-concave marginals using p = exp ( O ( 1 / α ) ) p=\exp(O(1/\alpha)) p = exp ( O ( 1/ α )) α − 1 / 2 \alpha^{-1/2} α − 1/2 (1) (as shown in Table 1 ).
Agnostic Proper learning. In § 3 we give a proper DP learner for halfspaces under Gaussian marginals with error at most OPT + α +\alpha + α Table 1 , its sample size is
n = O ~ ( D p α 2 + D p α ε D P + 1 α 6 + 1 ε D P α 5 ) (2) n = \widetilde{O}\left(\frac{D_p}{\alpha^2}+\frac{D_p}{\alpha\varepsilon_{\mathrm{DP}}}+\frac{1}{\alpha^6}+\frac{1}{\varepsilon_{\mathrm{DP}}\alpha^5}\right) \tag*{(2)} n = O ( α 2 D p + α ε DP D p + α 6 1 + ε DP α 5 1 ) (2) The learner works by first estimating a polynomial privately, similar to the improper case, which gives the first two terms in Equation (2) . Then we show that this polynomial can be used to obtain a subspace of dimension O ( α − 4 ) O(\alpha^{-4}) O ( α − 4 ) (2) .
Semi-Agnostic Proper learning. In § 4 , we give a proper learner under Gaussian marginals with error at most O ( O P T ) + α O(\mathrm{OPT})+\alpha O ( OPT ) + α Table 1 , is
n = O ~ ( d α 2 + d α ε D P ) . (3) n = \widetilde{O}\left(\frac{d}{\alpha^2}+\frac{d}{\alpha\varepsilon_{\mathrm{DP}}}\right). \tag*{(3)} n = O ( α 2 d + α ε DP d ) . (3) The learner works by utilizing a privatized semi-agnostic learner from Diakonikolas et al. [17 ] that provides the error guarantee of O ( η ) O(\eta) O ( η ) η ≥ O P T \eta\geq\mathrm{OPT} η ≥ OPT a priori . However, since we do not know what η \eta η η \eta η
Remark 1. Note that d O ( 1 / α 2 ) ⋅ 1 / α c = d O ( 1 / α 2 ) d^{O(1/\alpha^2)}\cdot1/\alpha^c=d^{O(1/\alpha^2)} d O ( 1/ α 2 ) ⋅ 1/ α c = d O ( 1/ α 2 ) p p p p ∈ N p\in\mathbb{N} p ∈ N p p p [11 ] ; Pesenti et al., [45 ] ). Thus, whatever exponent d d d poly ( 1 / α ) \operatorname{poly}(1/\alpha) poly ( 1/ α ) d d d
Remark 2. We additionally note that the added cost in our sample complexity due to DP matches the non-private sample complexity (terms without ε D P \varepsilon_{\mathrm{DP}} ε DP δ D P \delta_{\mathrm{DP}} δ DP ε D P = Ω ( α ) \varepsilon_{\mathrm{DP}}=\Omega(\alpha) ε DP = Ω ( α ) for free . This is commonly observed in DP statistical estimation (see, e.g., [33 , 30 ] ), and such sample complexity is often tight for various problems, such as mean and covariance estimation (Kamath et al., [31 ] ).
Notation. We denote the class of halfspaces by C \mathcal{C} C h : R d → { ± 1 } h:\mathbb{R}^d\to\{\pm1\} h : R d → { ± 1 } err P ( h ) : = P ( X , Y ) ∼ P [ h ( X ) ≠ Y ] \operatorname{err}_{P}(h):=\mathbb{P}_{(X,Y)\sim P}[h(X)\ne Y] err P ( h ) := P ( X , Y ) ∼ P [ h ( X ) = Y ] S S S err ^ S ( h ) : = \widehat{\operatorname{err}}_{S}(h):= err S ( h ) := ∣ S ∣ − 1 ∑ ( x , y ) ∈ S 1 { h ( x ) ≠ y } |S|^{-1}\sum_{(x,y)\in S}\mathbf{1}\{h(x)\ne y\} ∣ S ∣ − 1 ∑ ( x , y ) ∈ S 1 { h ( x ) = y } μ = N ( 0 , I d ) \mu=\mathcal{N}(0,I_d) μ = N ( 0 , I d ) Theorem D.1 ). We define O P T : = inf c ∈ C err P ( c ) \mathrm{OPT}:=\inf_{c\in\mathcal{C}}\operatorname{err}_P(c) OPT := inf c ∈ C err P ( c ) g : R d → R g:\mathbb{R}^d\to\mathbb{R} g : R d → R q ∈ { 1 , 2 } q\in\{1,2\} q ∈ { 1 , 2 } ∥ g ∥ L q ( μ ) : = ( E X ∼ μ [ ∣ g ( X ) ∣ q ] ) 1 / q \|g\|_{L^q(\mu)}:=\left(\mathbb{E}_{X\sim\mu}[|g(X)|^q]\right)^{1/q} ∥ g ∥ L q ( μ ) := ( E X ∼ μ [ ∣ g ( X ) ∣ q ] ) 1/ q § 8 .§ 2 .
Private Improper Agnostic Learning
In this section, we give a differentially private algorithm for agnostically learning halfspaces under Gaussian marginals. We build on the polynomial L 1 L^1 L 1 [29 ] , which fits a low-degree polynomial to the labels and then thresholds its predictions.
To privatize this approach, we need two additional properties. We first need a bounded domain that contains the coefficients of a good polynomial approximation to every halfspace. Working in the orthonormal Hermite basis, the unit-norm approximation guarantee of Lemma B.10 allows us to restrict the coefficient vector to the Euclidean unit ball. Second, we need uniformly bounded feature norms so that the regression loss is Lipschitz in the coefficient vector. We obtain this by clipping the feature vectors. This increases the population L 1 L^1 L 1 Lemma C.2 . These two properties allow us to fit the coefficients using private convex optimisation (Kulkarni et al. [36 ] ). We then repeat the DP optimisation step on independent samples to boost its success probability and use the exponential mechanism (McSherry and Talwar [41 ] ) to privately select among the resulting thresholded classifiers. Our main result is stated as follows.
Theorem 2.1 (DP improper agnostic learner for Gaussian marginals). Let α , β , ε D P , δ D P ∈ ( 0 , 1 / 2 ] \alpha,\beta,\varepsilon_{\mathrm{DP}},\delta_{\mathrm{DP}}\in(0,1/2] α , β , ε DP , δ DP ∈ ( 0 , 1/2 ] p = ⌈ C α − 2 ⌉ p=\lceil C\alpha^{-2}\rceil p = ⌈ C α − 2 ⌉ C > 0 C>0 C > 0 D p = ( d + p p ) D_p=\binom{d+p}{p} D p = ( p d + p ) d ≥ C d i m α − 5 d\ge C_{\mathrm{dim}}\alpha^{-5} d ≥ C dim α − 5 C d i m > 0 C_{\mathrm{dim}}>0 C dim > 0 P P P R d × { ± 1 } \mathbb{R}^d\times\{\pm1\} R d × { ± 1 } μ = N ( 0 , I d ) \mu=\mathcal{N}(0,I_d) μ = N ( 0 , I d ) ( ε D P , δ D P ) (\varepsilon_{\mathrm{DP}},\delta_{\mathrm{DP}}) ( ε DP , δ DP )
n = O ~ ( D p α 2 + D p ε D P α ) n=\widetilde{O}\left(\frac{D_p}{\alpha^2}+\frac{D_p}{\varepsilon_{\mathrm{DP}}\alpha}\right) n = O ( α 2 D p + ε DP α D p ) i.i.d. samples from P P P h h h err P ( h ) ≤ O P T + α \operatorname{err}_P(h)\le\mathrm{OPT}+\alpha err P ( h ) ≤ OPT + α 1 − β 1-\beta 1 − β poly ( n ) \operatorname{poly}(n) poly ( n )
The two terms in the sample complexity arise from statistical estimation and private optimization, respectively. When ε D P ≥ α \varepsilon_{\mathrm{DP}}\ge\alpha ε DP ≥ α O ~ ( D p / α 2 ) \widetilde{O}(D_p/\alpha^2) O ( D p / α 2 ) d d d [11 ] ). Moreover, the d 1 / α 2 d^{1/\alpha^2} d 1/ α 2 [16 ] ). In Appendix § 10 , we extend the method to log-concave marginals and establish an analogous guarantee.
The Algorithm
We represent each input x x x ψ p ( x ) = ( h κ ( x ) ) ∣ κ ∣ ≤ p ∈ R D p \psi_p(x)=(h_\kappa(x))_{|\kappa|\le p}\in\mathbb{R}^{D_p} ψ p ( x ) = ( h κ ( x ) ) ∣ κ ∣ ≤ p ∈ R D p [44 ] ) of degree at most p p p p = ⌈ C α − 2 ⌉ p=\lceil C\alpha^{-2}\rceil p = ⌈ C α − 2 ⌉ L 1 ( μ ) L^1(\mu) L 1 ( μ ) α \alpha α [11 ] ). To bound the influence of any single example and make the regression loss Lipschitz in its coefficients, we clip the feature vectors to norm at most T = 2 D p T=2\sqrt{D_p} T = 2 D p ψ ~ p ( x ) : = T ψ p ( x ) / max { T , ∥ ψ p ( x ) ∥ 2 } \widetilde{\psi}_p(x):=T\psi_p(x)/\max\{T,\|\psi_p(x)\|_2\} ψ p ( x ) := T ψ p ( x ) / max { T , ∥ ψ p ( x ) ∥ 2 } Lemma C.2 , the Algorithm 1 Private polynomial L 1 L^1 L 1
Require: Sample S S S n n n α \alpha α β \beta β ε D P \varepsilon_{\mathrm{DP}} ε DP δ D P \delta_{\mathrm{DP}} δ DP
Set p = ⌈ C α − 2 ⌉ p=\lceil C\alpha^{-2}\rceil p = ⌈ C α − 2 ⌉ T = 2 D p T=2\sqrt{D_p} T = 2 D p k = ⌈ log 2 ( 2 / β ) ⌉ k=\lceil\log_2(2/\beta)\rceil k = ⌈ log 2 ( 2/ β )⌉ M = ⌈ C / α ⌉ M=\lceil C/\alpha\rceil M = ⌈ C / α ⌉ n 0 , m n_0,m n 0 , m
Partition S S S S 1 , … , S k S_1,\ldots,S_k S 1 , … , S k n 0 n_0 n 0 S v a l S_{\mathrm{val}} S val m m m
for j = 1 , … , k j=1,\ldots,k j = 1 , … , k
v ^ j ← \hat{v}_j\leftarrow v ^ j ← ( ε D P , δ D P ) (\varepsilon_{\mathrm{DP}},\delta_{\mathrm{DP}}) ( ε DP , δ DP ) L ^ S j \widehat{L}_{S_j} L S j B 2 D p B_2^{D_p} B 2 D p
end for
For ( j , ℓ ) ∈ [ k ] × [ M ] (j,\ell)\in[k]\times[M] ( j , ℓ ) ∈ [ k ] × [ M ] t ℓ = − 1 + ( 2 ℓ − 1 ) / M t_\ell=-1+(2\ell-1)/M t ℓ = − 1 + ( 2 ℓ − 1 ) / M h j , ℓ ( x ) = sign ( ⟨ v ^ j , ψ ˉ p , T ( x ) ⟩ − t ℓ ) h_{j,\ell}(x)=\operatorname{sign}(\langle\hat{v}_j,\bar{\psi}_{p,T}(x)\rangle-t_\ell) h j , ℓ ( x ) = sign (⟨ v ^ j , ψ ˉ p , T ( x )⟩ − t ℓ )
Sample ( ȷ ^ , ℓ ^ ) (\hat{\jmath},\hat{\ell}) ( ^ , ℓ ^ ) exp ( − ε D P m err ^ S v a l ( h j , ℓ ) / 2 ) \exp(-\varepsilon_{\mathrm{DP}}m\widehat{\operatorname{err}}_{S_{\mathrm{val}}}(h_{j,\ell})/2) exp ( − ε DP m err S val ( h j , ℓ ) /2 )
return h ȷ ^ , ℓ ^ h_{\hat{\jmath},\hat{\ell}} h ^ , ℓ ^
clipping probability is at most O ( α ) O(\alpha) O ( α ) S S S L 1 L^1 L 1
L ^ S ( v ) = 1 ∣ S ∣ ∑ ( X i , Y i ) ∈ S ∣ ⟨ v , ψ ˉ p , T ( X i ) ⟩ − Y i ∣ (4) \widehat{L}_S(v)=\frac{1}{|S|}\sum_{(X_i,Y_i)\in S}\left|\langle v,\bar{\psi}_{p,T}(X_i)\rangle-Y_i\right| \tag*{(4)} L S ( v ) = ∣ S ∣ 1 ( X i , Y i ) ∈ S ∑ ⟨ v , ψ ˉ p , T ( X i )⟩ − Y i (4) over the unit ball B 2 D p = { v ∈ R D p : ∥ v ∥ 2 ≤ 1 } B_2^{D_p}=\{v\in\mathbb{R}^{D_p}:\|v\|_2\le1\} B 2 D p = { v ∈ R D p : ∥ v ∥ 2 ≤ 1 } T T T v v v [36 ] , restated in Lemma B.4 . A potential alternative approach is to implement polynomial regression using statistical queries (Kearns, [35 ] ) and then simulate these queries privately (Kasiviswanathan et al., [34 ] ). For the clipped regression problem of Equation (4), these queries can estimate the expected subgradients. However, making this SQ implementation explicit and replacing its query answers with actual private estimates leads to an algorithm with basically the same structure as ours. For this reason, we do not write the SQ version of this algorithm here.
Next, the regression guarantee holds in expectation, so we repeat the regression step on independent training blocks to ensure that at least one output has small population loss with high probability. Specifically, Algorithm 1 first partitions the sample into k k k n 0 n_0 n 0 m m m v ^ 1 , … , v ^ k \hat{v}_1,\ldots,\hat{v}_k v ^ 1 , … , v ^ k ⟨ v ^ j , ψ ˉ p , T ( x ) ⟩ \langle\hat{v}_j,\bar{\psi}_{p,T}(x)\rangle ⟨ v ^ j , ψ ˉ p , T ( x )⟩ M M M [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] k M kM k M [41 ] ), scoring each candidate by its fraction err ^ S v a l ( ⋅ ) \widehat{\operatorname{err}}_{S_{\mathrm{val}}}(\cdot) err S val ( ⋅ ) k k k
Analysis
In this section, we outline the accuracy analysis; the full accuracy and privacy proofs are deferred to Appendix § 9 . Define the population loss L P ( v ) : = E ( X , Y ) ∼ P [ ⟨ v , ψ ˉ p , T ( X ) ⟩ − Y ] L_P(v):=\mathbb{E}_{(X,Y)\sim P}[\langle v,\bar{\psi}_{p,T}(X)\rangle-Y] L P ( v ) := E ( X , Y ) ∼ P [⟨ v , ψ ˉ p , T ( X )⟩ − Y ] L ∗ : = min ∥ v ∥ 2 ≤ 1 L P ( v ) L^*:=\min_{\|v\|_2\le1}L_P(v) L ∗ := min ∥ v ∥ 2 ≤ 1 L P ( v ) c ∈ ( 0 , 1 / 4 ] c\in(0,1/4] c ∈ ( 0 , 1/4 ]
L ∗ ≤ 2 OPT + 2 c α . (5) L^*\le2\operatorname{OPT}+2c\alpha. \tag*{(5)} L ∗ ≤ 2 OPT + 2 c α . (5) We then show that the algorithm returns a classifier whose error satisfies
err P ( h ) ≤ 1 2 L ∗ + 3 c α (6) \operatorname{err}_P(h)\le\frac{1}{2}L^*+3c\alpha \tag*{(6)} err P ( h ) ≤ 2 1 L ∗ + 3 c α (6) with probability at least 1 − β 1-\beta 1 − β err P ( h ) ≤ OPT + 4 c α ≤ OPT + α \operatorname{err}_P(h)\le\operatorname{OPT}+4c\alpha\le\operatorname{OPT}+\alpha err P ( h ) ≤ OPT + 4 c α ≤ OPT + α
We begin with Equation (5) , which compares the clipped regression problem with the best halfspace. Fix f ∈ C f \in\mathcal{C} f ∈ C [11 , 45 ] ), there is a polynomial q = ⟨ v q , ψ p ⟩ q = \langle v_q, \psi_p\rangle q = ⟨ v q , ψ p ⟩ ∥ v q ∥ 2 ≤ 1 \lVert v_q\rVert_2 \le1 ∥ v q ∥ 2 ≤ 1 ∥ q − f ∥ L 1 ( μ ) ≤ c α \lVert q-f\rVert_{L_1(\mu)} \le c\alpha ∥ q − f ∥ L 1 ( μ ) ≤ c α s ( x ) : = T / max { T , ∥ ψ p ( x ) ∥ 2 } s(x) := T/\max\{T,\lVert\psi_p(x)\rVert_2\} s ( x ) := T / max { T , ∥ ψ p ( x ) ∥ 2 } ψ ‾ p , T ( x ) = s ( x ) ψ p ( x ) \overline{\psi}_{p,T}(x) = s(x)\psi_p(x) ψ p , T ( x ) = s ( x ) ψ p ( x ) ⟨ v q , ψ ‾ p , T ( x ) ⟩ = s ( x ) q ( x ) \langle v_q,\overline{\psi}_{p,T}(x)\rangle= s(x)q(x) ⟨ v q , ψ p , T ( x )⟩ = s ( x ) q ( x ) 0 < s ( x ) ≤ 1 0 < s(x) \le1 0 < s ( x ) ≤ 1 ∣ y ∣ = 1 \lvert y\rvert= 1 ∣ y ∣ = 1
∣ s ( x ) q ( x ) − y ∣ ≤ s ( x ) ∣ q ( x ) − y ∣ + 1 − s ( x ) ≤ ∣ q ( x ) − f ( x ) ∣ + ∣ f ( x ) − y ∣ + 1 − s ( x ) . \begin{aligned}
\lvert s(x)q(x)-y\rvert&\le s(x)\lvert q(x)-y\rvert+ 1-s(x) \\
&\le\lvert q(x)-f(x)\rvert+ \lvert f(x)-y\rvert+ 1-s(x).
\end{aligned} ∣ s ( x ) q ( x ) − y ∣ ≤ s ( x ) ∣ q ( x ) − y ∣ + 1 − s ( x ) ≤ ∣ q ( x ) − f ( x )∣ + ∣ f ( x ) − y ∣ + 1 − s ( x ) . The first inequality follows by adding and subtracting s ( x ) y s(x)y s ( x ) y
L P ( v q ) ≤ 2 err P ( f ) + ∥ q − f ∥ L 1 ( μ ) + E μ [ 1 − s ( X ) ] . L_P(v_q) \le2\operatorname{err}_P(f) + \lVert q-f\rVert_{L_1(\mu)} + \mathbb{E}_{\mu}[1-s(X)]. L P ( v q ) ≤ 2 err P ( f ) + ∥ q − f ∥ L 1 ( μ ) + E μ [ 1 − s ( X )] . The three terms are the classification error of f f f 1 − s ( x ) ≤ 1 { ∥ ψ p ( x ) ∥ 2 > T } 1-s(x) \le\mathbf{1}\{\lVert\psi_p(x)\rVert_2 > T\} 1 − s ( x ) ≤ 1 {∥ ψ p ( x ) ∥ 2 > T } Lemma C.2 bounds the last term by c α c\alpha c α c α c\alpha c α L P ( v q ) ≤ 2 err P ( f ) + 2 c α L_P(v_q) \le2\operatorname{err}_P(f)+2c\alpha L P ( v q ) ≤ 2 err P ( f ) + 2 c α ∥ v q ∥ 2 ≤ 1 \lVert v_q\rVert_2 \le1 ∥ v q ∥ 2 ≤ 1 L ⋆ ≤ L P ( v q ) L^\star\le L_P(v_q) L ⋆ ≤ L P ( v q ) f f f (5) .
For Equation (6) , we first show that at least one of the k k k T T T [36 ] bounds the expected optimization error. Then, standard Rademacher complexity bound for linear predictors under L 1 L_1 L 1 Lemma B.7 ), applied with E μ ∥ ψ ‾ p , T ( X ) ∥ 2 2 ≤ D p \mathbb{E}_{\mu}\lVert\overline{\psi}_{p,T}(X)\rVert_2^2 \le D_p E μ ∥ ψ p , T ( X ) ∥ 2 2 ≤ D p n 0 n_0 n 0 c α c\alpha c α (16) ), giving
E [ L P ( v ^ j ) ] − L ⋆ ≤ c α , \mathbb{E}[L_P(\hat{v}_j)]-L^\star\le c\alpha, E [ L P ( v ^ j )] − L ⋆ ≤ c α , where the expectation is over S j S_j S j v ^ j \hat{v}_j v ^ j L P ( v ^ j ) − L ⋆ L_P(\hat{v}_j)-L^\star L P ( v ^ j ) − L ⋆ L P ( v ^ j ) ≤ L ⋆ + 2 c α L_P(\hat{v}_j) \le L^\star+2c\alpha L P ( v ^ j ) ≤ L ⋆ + 2 c α 1 / 2 1/2 1/2 k k k 1 − 2 − k ≥ 1 − β / 2 1-2^{-k} \ge1-\beta/2 1 − 2 − k ≥ 1 − β /2 j ⋆ j^\star j ⋆
We next show that thresholding this run yields a good candidate classifier. For any fixed regression output v ^ j \hat{v}_j v ^ j τ ∈ [ − 1 , 1 ] \tau\in[-1,1] τ ∈ [ − 1 , 1 ] L P ( v ^ j ) / 2 L_P(\hat{v}_j)/2 L P ( v ^ j ) /2 τ \tau τ [29 ] , see also Fact B.6 ). Rounding τ \tau τ M M M 1 / ( 2 M ) ≤ c α 1/(2M) \le c\alpha 1/ ( 2 M ) ≤ c α j ⋆ j^\star j ⋆
min j , ℓ err P ( h j , ℓ ) ≤ 1 2 L P ( v ^ j ⋆ ) + c α ≤ 1 2 L ⋆ + 2 c α . \min_{j,\ell}\operatorname{err}_P(h_{j,\ell}) \le\frac{1}{2}L_P(\hat{v}_{j^\star})+c\alpha\le\frac{1}{2}L^\star+2c\alpha. j , ℓ min err P ( h j , ℓ ) ≤ 2 1 L P ( v ^ j ⋆ ) + c α ≤ 2 1 L ⋆ + 2 c α . This establishes that the candidate set contains a good classifier. It remains to select one privately. The algorithm uses the exponential mechanism on the independent validation sample S v a l S_{\mathrm{val}} S val k M kM k M Lemma B.5 , with m m m (17) , the selected classifier has error at most c α c\alpha c α 1 − β / 2 1-\beta/2 1 − β /2 (6) .
Finally, since T D p = 2 D p T\sqrt{D_p}=2D_p T D p = 2 D p k = O ( log ( 1 / β ) ) k=\mathcal{O}(\log(1/\beta)) k = O ( log ( 1/ β )) n 0 n_0 n 0 m m m Theorem 2.1 . Computing the features, running the k k k k M kM k M S v a l S_{\mathrm{val}} S val poly ( n ) \operatorname{poly}(n) poly ( n ) § 9 .
Remark 3. The dimension assumption in Theorem 2.1 allows us to use the clipping radius T = 2 D p T = 2\sqrt{D_p} T = 2 D p T = D p / ( c α ) T = \sqrt{D_p}/(c\alpha) T = D p / ( c α ) c > 0 c > 0 c > 0
Pr μ ( ∥ ψ p ( X ) ∥ 2 > T ) ≤ D p T 2 = c α . (7) \Pr_{\mu}(\lVert\psi_p(X)\rVert_2 > T) \le\frac{D_p}{T^2} = c\alpha. \tag*{(7)} μ Pr (∥ ψ p ( X ) ∥ 2 > T ) ≤ T 2 D p = c α . (7) Replacing Lemma C.2 with this bound, the same analysis (see Appendix § 9 ) establishes the learning guarantee of Theorem 2.1 for every d ≥ 1 d \ge1 d ≥ 1 α − 1 / 2 \alpha^{-1/2} α − 1/2
Private Proper Agnostic Learning
The agnostic learner in § 2 is improper since its output need not be a halfspace. In this section, we provide a private proper learner that outputs a halfspace in R d \mathbb{R}^d R d O ( d ) O(d) O ( d ) d O ( 1 / α 2 ) d^{O(1/\alpha^2)} d O ( 1/ α 2 )
We will adapt the low-rank subspace reduction of Diakonikolas et al. [15 ] to design the learner. First, it constructs a finite class of halfspaces from a polynomial with sufficiently small excess squared loss. The resulting class is guaranteed to contain a halfspace whose error is close to the best halfspace. Once we have this finite class of halfspaces, we use the exponential mechanism (McSherry and Talwar, [41 ] ) to privately select a halfspace from it. Our main result is stated below.
Theorem 3.1 (DP proper agnostic learner). Let α , β , δ D P ∈ ( 0 , 1 / 2 ) \alpha,\beta,\delta_{\mathrm{DP}} \in(0,1/2) α , β , δ DP ∈ ( 0 , 1/2 ) ε D P ∈ ( 0 , 1 ) \varepsilon_{\mathrm{DP}} \in(0,1) ε DP ∈ ( 0 , 1 ) p = ⌈ C 0 / ( c α ) 2 ⌉ p = \lceil C_0/(c\alpha)^2\rceil p = ⌈ C 0 / ( c α ) 2 ⌉ C 0 > 0 C_0 > 0 C 0 > 0 c > 0 c > 0 c > 0 D p = ( d + p p ) D_p = \binom{d+p}{p} D p = ( p d + p ) d ≥ C d i m α − 5 d \ge C_{\mathrm{dim}}\alpha^{-5} d ≥ C dim α − 5 C d i m > 0 C_{\mathrm{dim}} > 0 C dim > 0 P P P R d × { ± 1 } \mathbb{R}^d \times\{\pm1\} R d × { ± 1 } μ = N ( 0 , I d ) \mu= \mathcal{N}(0,I_d) μ = N ( 0 , I d ) ( ε D P , δ D P ) (\varepsilon_{\mathrm{DP}},\delta_{\mathrm{DP}}) ( ε DP , δ DP )
n = O ~ ( D p α 2 + D p ε D P α + 1 α 6 + 1 ε D P α 5 ) n = \widetilde{O}\left(\frac{D_p}{\alpha^2} + \frac{D_p}{\varepsilon_{\mathrm{DP}}\alpha} + \frac{1}{\alpha^6} + \frac{1}{\varepsilon_{\mathrm{DP}}\alpha^5}\right) n = O ( α 2 D p + ε DP α D p + α 6 1 + ε DP α 5 1 ) i.i.d. samples from P P P h ∈ C h \in\mathcal{C} h ∈ C err P ( h ) ≤ OPT + α \operatorname{err}_P(h) \le\operatorname{OPT} + \alpha err P ( h ) ≤ OPT + α 1 − β 1-\beta 1 − β poly ( n ) ⋅ exp ( O ( α − 4 log ( 1 / α ) ) ) \operatorname{poly}(n) \cdot\exp(O(\alpha^{-4}\log(1/\alpha))) poly ( n ) ⋅ exp ( O ( α − 4 log ( 1/ α )))
A proof sketch appears at the end of this section, and the full proof is given in Appendix § 11 . We use a strengthened version of the subspace reduction of Diakonikolas et al. [15 ] , reducing the polynomial degree from O ( 1 / α 4 ) O(1/\alpha^4) O ( 1/ α 4 ) O ( 1 / α 2 ) O(1/\alpha^2) O ( 1/ α 2 ) O ( 1 / α 6 ) O(1/\alpha^6) O ( 1/ α 6 ) O ( 1 / α 4 ) O(1/\alpha^4) O ( 1/ α 4 ) [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] Lemma 3.2 states this guarantee.
Thus, our sample bound has the same ( ( d + p p ) ) (d+p \choose p) ( p ) ( d + p ) [11 ] ), while returning a halfspace. When ε D P ≥ α \varepsilon_{\mathrm{DP}} \ge\alpha ε DP ≥ α D p / α 2 + 1 / α 6 D_p/\alpha^2 + 1/\alpha^6 D p / α 2 + 1/ α 6
The factor exp ( O ( α − 4 log ( 1 / α ) ) ) \exp(O(\alpha^{-4}\log(1/\alpha))) exp ( O ( α − 4 log ( 1/ α ))) n n n α \alpha α [15 ] also searches such a cover, and its running time likewise includes a term exponential in poly ( 1 / α ) \operatorname{poly}(1/\alpha) poly ( 1/ α )
Lemma 3.2. There exist universal constants C 0 , C , c 0 > 0 C_0, C, c_0 > 0 C 0 , C , c 0 > 0 ( X , U ) (X,U) ( X , U ) X ∼ N ( 0 , I d ) X \sim\mathcal{N}(0,I_d) X ∼ N ( 0 , I d ) ∣ U ∣ ≤ 1 |U| \le1 ∣ U ∣ ≤ 1 α ∈ ( 0 , 1 / 2 ) \alpha\in(0,1/2) α ∈ ( 0 , 1/2 ) p = ⌈ C 0 α − 2 ⌉ p = \lceil C_0\alpha^{-2}\rceil p = ⌈ C 0 α − 2 ⌉ P p \mathcal{P}_p P p R d \mathbb{R}^d R d p p p q ∈ P p q \in\mathcal{P}_p q ∈ P p
E [ ( U − q ( X ) ) 2 ] ≤ inf Q ∈ P p E [ ( U − Q ( X ) ) 2 ] + c 0 2 α 2 . (8) \mathbb{E}\left[(U-q(X))^2\right] \le\inf_{Q\in\mathcal{P}_p}\mathbb{E}\left[(U-Q(X))^2\right] + c_0^2\alpha^2. \tag*{(8)} E [ ( U − q ( X ) ) 2 ] ≤ Q ∈ P p inf E [ ( U − Q ( X ) ) 2 ] + c 0 2 α 2 . (8) Using just q q q α \alpha α H ( q ) ⊆ C \mathcal{H}(q) \subseteq\mathcal{C} H ( q ) ⊆ C log ∣ H ( q ) ∣ ≤ C α − 4 log ( 1 / α ) \log|\mathcal{H}(q)| \le C\alpha^{-4}\log(1/\alpha) log ∣ H ( q ) ∣ ≤ C α − 4 log ( 1/ α ) f ∈ C f \in\mathcal{C} f ∈ C h ∈ H ( q ) h \in\mathcal{H}(q) h ∈ H ( q ) E [ U ( f ( X ) − h ( X ) ) ] ≤ C α \mathbb{E}[U(f(X)-h(X))] \le C\alpha E [ U ( f ( X ) − h ( X ))] ≤ C α
The proof is stated in Appendix § 11 . A natural idea is to obtain the polynomial q q q Theorem 2.1 . However, the coefficients v ^ j \hat{v}_j v ^ j L 1 L^1 L 1
E ( X , Y ) ∼ P [ ∣ ⟨ v ^ j , ψ ˉ p , T ( X ) ⟩ − Y ∣ ] ≤ min ∥ v ∥ 2 ≤ 1 E ( X , Y ) ∼ P [ ∣ ⟨ v , ψ ˉ p , T ( X ) ⟩ − Y ∣ ] + O ( α ) , \mathbb{E}_{(X,Y)\sim P}\left[\left|\langle\hat{v}_j,\bar{\psi}_{p,T}(X)\rangle-Y\right|\right] \le\min_{\|v\|_2\le1}\mathbb{E}_{(X,Y)\sim P}\left[\left|\langle v,\bar{\psi}_{p,T}(X)\rangle-Y\right|\right] + O(\alpha), E ( X , Y ) ∼ P [ ⟨ v ^ j , ψ ˉ p , T ( X )⟩ − Y ] ≤ ∥ v ∥ 2 ≤ 1 min E ( X , Y ) ∼ P [ ⟨ v , ψ ˉ p , T ( X )⟩ − Y ] + O ( α ) , which does not imply the excess squared-loss bound in Equation (8) . Moreover, the function ⟨ v ^ j , ψ ˉ p , T ( X ) ⟩ \langle\hat{v}_j,\bar{\psi}_{p,T}(X)\rangle ⟨ v ^ j , ψ ˉ p , T ( X )⟩ ψ ˉ p , T ( X ) \bar{\psi}_{p,T}(X) ψ ˉ p , T ( X ) Lemma 3.2 . We therefore need a different private polynomial construction that directly controls excess squared loss.
Constructing a private polynomial with small excess squared loss
To construct the polynomial, we propose a simple estimator based on the correlations between the labels and the Hermite features. For squared-loss regression, these correlations give the coefficients of the optimal polynomial (see Lemma 3.3 below). However, clipping changes the correlations between the labels and the Hermite features. Write m = E [ Y ψ p ( X ) ] m = \mathbb{E}[Y\psi_p(X)] m = E [ Y ψ p ( X )] m T = E [ Y ψ ˉ p , T ( X ) ] m_T = \mathbb{E}[Y\bar{\psi}_{p,T}(X)] m T = E [ Y ψ ˉ p , T ( X )]
∥ m − m T ∥ 2 = sup ∥ v ∥ 2 = 1 ∣ E [ Y ( 1 − s ( X ) ) ⟨ v , ψ p ( X ) ⟩ ] ∣ ≤ E [ ( 1 − s ( X ) ) 2 ] ≤ Pr μ [ ∥ ψ p ( X ) ∥ 2 > T ] = O ( α ) , \begin{aligned}
\lVert m-m_T\rVert_2 = \sup_{\lVert v\rVert_2=1}\left|\mathbb{E}\left[Y(1-s(X))\langle v,\psi_p(X)\rangle\right]\right| \\
&\le\sqrt{\mathbb{E}\left[(1-s(X))^2\right]} \le\sqrt{\Pr_{\mu}\left[\lVert\psi_p(X)\rVert_2>T\right]} = O(\sqrt{\alpha}),
\end{aligned} ∥ m − m T ∥ 2 = ∥ v ∥ 2 = 1 sup ∣ E [ Y ( 1 − s ( X )) ⟨ v , ψ p ( X )⟩ ] ∣ ≤ E [ ( 1 − s ( X ) ) 2 ] ≤ μ Pr [ ∥ ψ p ( X ) ∥ 2 > T ] = O ( α ) , where the first inequality uses Cauchy–Schwarz and orthonormality of Hermite functions, and the last inequality uses O ( α ) O(\alpha) O ( α ) § 2 (see Lemma C.2 ). Thus, a O ( α ) O(\sqrt{\alpha}) O ( α ) O ( α ) O(\alpha) O ( α ) Lemma 3.2 requires an O ( α 2 ) O(\alpha^2) O ( α 2 ) O ( α ) O(\alpha) O ( α )
We show that this can be achieved by constructing the polynomial for the clipped labels U = s ( X ) Y U=s(X)Y U = s ( X ) Y L s ( Q ) = E [ ( U − Q ( X ) ) 2 ] L_s(Q)=\mathbb{E}\left[(U-Q(X))^2\right] L s ( Q ) = E [ ( U − Q ( X ) ) 2 ] ∣ U ∣ = ∣ s ( X ) Y ∣ ≤ 1 |U|=|s(X)Y|\le1 ∣ U ∣ = ∣ s ( X ) Y ∣ ≤ 1 m T = E [ Y ψ ˉ p , T ( X ) ] = E [ U ψ p ( X ) ] m_T=\mathbb{E}[Y\bar{\psi}_{p,T}(X)]=\mathbb{E}[U\psi_p(X)] m T = E [ Y ψ ˉ p , T ( X )] = E [ U ψ p ( X )] m T m_T m T L s L_s L s P p \mathcal{P}_p P p
Lemma 3.3. Let X ∼ N ( 0 , I d ) X\sim\mathcal{N}(0,I_d) X ∼ N ( 0 , I d ) ∣ U ∣ ≤ 1 |U|\le1 ∣ U ∣ ≤ 1 m T = E [ U ψ p ( X ) ] m_T=\mathbb{E}[U\psi_p(X)] m T = E [ U ψ p ( X )] q m T ( x ) = ⟨ m T , ψ p ( x ) ⟩ q_{m_T}(x)=\langle m_T,\psi_p(x)\rangle q m T ( x ) = ⟨ m T , ψ p ( x )⟩ L s L_s L s P p \mathcal{P}_p P p
Proof of Lemma 3.3 . Every polynomial in P p \mathcal{P}_p P p q w ( x ) = ⟨ w , ψ p ( x ) ⟩ q_w(x)=\langle w,\psi_p(x)\rangle q w ( x ) = ⟨ w , ψ p ( x )⟩ w ∈ R D p w\in\mathbb{R}^{D_p} w ∈ R D p E [ ψ p ( X ) ψ p ( X ) T ] = I D p \mathbb{E}[\psi_p(X)\psi_p(X)^\mathsf{T}]=I_{D_p} E [ ψ p ( X ) ψ p ( X ) T ] = I D p
L s ( q w ) = E [ ( U − q w ( X ) ) 2 ] = E [ U 2 ] − 2 ⟨ w , m T ⟩ + ∥ w ∥ 2 2 = E [ U 2 ] − ∥ m T ∥ 2 2 + ∥ w − m T ∥ 2 2 . (9) \begin{aligned}
L_s(q_w)=\mathbb{E}\left[(U-q_w(X))^2\right]=\mathbb{E}[U^2]-2\langle w,m_T\rangle+\lVert w\rVert_2^2 \\
&=\mathbb{E}[U^2]-\lVert m_T\rVert_2^2+\lVert w-m_T\rVert_2^2. \tag*{(9)}
\end{aligned} L s ( q w ) = E [ ( U − q w ( X ) ) 2 ] = E [ U 2 ] − 2 ⟨ w , m T ⟩ + ∥ w ∥ 2 2 = E [ U 2 ] − ∥ m T ∥ 2 2 + ∥ w − m T ∥ 2 2 . (9) Algorithm 2 Private proper learning of Gaussian halfspaces
Require: Sample S S S n n n α \alpha α β \beta β ( ε D P , δ D P ) (\varepsilon_{\mathrm{DP}}, \delta_{\mathrm{DP}}) ( ε DP , δ DP )
Set p = ⌈ C 0 / ( c α ) ⌉ p = \lceil C_0/(c\alpha)\rceil p = ⌈ C 0 / ( c α )⌉ D p = ( d + p p ) D_p = \binom{d+p}{p} D p = ( p d + p ) T = 2 D p T = 2\sqrt{D_p} T = 2 D p c > 0 c > 0 c > 0
Split S S S S 1 , S 2 S_1, S_2 S 1 , S 2 n / 2 n/2 n /2
Draw Z ∼ N ( 0 , σ 2 I D p ) Z \sim\mathcal{N}(0, \sigma^2 I_{D_p}) Z ∼ N ( 0 , σ 2 I D p ) σ = 4 T 2 log ( 1.25 / δ D P ) ε D P n \sigma= \frac{4T\sqrt{2\log(1.25/\delta_{\mathrm{DP}})}}{\varepsilon_{\mathrm{DP}}n} σ = ε DP n 4 T 2 l o g ( 1.25/ δ DP )
m ~ ← Proj B D p 2 ( 2 n ∑ ( X i , Y i ) ∈ S 1 Y i ψ ‾ p , T ( X i ) + Z ) \widetilde{m} \leftarrow\operatorname{Proj}_{B_{D_p}^2}\left(\frac{2}{n}\sum_{(X_i,Y_i)\in S_1}Y_i\overline{\psi}_{p,T}(X_i)+Z\right) m ← Proj B D p 2 ( n 2 ∑ ( X i , Y i ) ∈ S 1 Y i ψ p , T ( X i ) + Z ) q ( x ) ← ⟨ m ~ , ψ p ( x ) ⟩ q(x) \leftarrow\langle\widetilde{m},\psi_p(x)\rangle q ( x ) ← ⟨ m , ψ p ( x )⟩
Construct H ( q ) \mathcal{H}(q) H ( q ) Lemma 3.2 with accuracy c α c\alpha c α
Sample h ∈ H ( q ) h \in\mathcal{H}(q) h ∈ H ( q ) exp ( − ( ε D P / 2 ) ∑ ( X i , Y i ) ∈ S 2 1 { h ( X i ) ≠ Y i } ) \exp\left(-(\varepsilon_{\mathrm{DP}}/2)\sum_{(X_i,Y_i)\in S_2}\mathbf{1}\{h(X_i)\ne Y_i\}\right) exp ( − ( ε DP /2 ) ∑ ( X i , Y i ) ∈ S 2 1 { h ( X i ) = Y i } )
return h h h
The first two terms do not depend on w w w w = m T w = m_T w = m T
Thus, our goal is to estimate m T m_T m T m ~ \widetilde{m} m (9) , we get that the polynomial q m ~ ( x ) = ⟨ m ~ , ψ p ( x ) ⟩ q_{\widetilde{m}}(x) = \langle\widetilde{m},\psi_p(x)\rangle q m ( x ) = ⟨ m , ψ p ( x )⟩
L s ( q m ~ ) − inf Q ∈ P p L s ( Q ) = ∥ m ~ − m T ∥ 2 2 . L_s(q_{\widetilde{m}})-\inf_{Q\in\mathcal{P}_p}L_s(Q)=\|\widetilde{m}-m_T\|_2^2. L s ( q m ) − Q ∈ P p inf L s ( Q ) = ∥ m − m T ∥ 2 2 . It therefore suffices to estimate a coefficient vector m ~ \widetilde{m} m ∥ m ~ − m T ∥ 2 ≤ c 0 c α \|\widetilde{m}-m_T\|_2\le c_0c\alpha ∥ m − m T ∥ 2 ≤ c 0 c α c 0 > 0 c_0>0 c 0 > 0 ∥ m T ∥ 2 ≤ 1 \|m_T\|_2\le1 ∥ m T ∥ 2 ≤ 1
Lemma 3.4. Let α , β , δ D P ∈ ( 0 , 1 / 2 ) \alpha,\beta,\delta_{\mathrm{DP}}\in(0,1/2) α , β , δ DP ∈ ( 0 , 1/2 ) ε D P ∈ ( 0 , 1 ] \varepsilon_{\mathrm{DP}}\in(0,1] ε DP ∈ ( 0 , 1 ] q q q n / 2 n/2 n /2 S 1 S_1 S 1 ( ε D P , δ D P ) (\varepsilon_{\mathrm{DP}},\delta_{\mathrm{DP}}) ( ε DP , δ DP ) ∥ q ∥ L 2 ( μ ) ≤ 1 \|q\|_{L^2(\mu)}\le1 ∥ q ∥ L 2 ( μ ) ≤ 1 n / 2 = Ω ~ ( D p / α 2 + D p / ( ε D P α ) ) n/2=\widetilde{\Omega}(D_p/\alpha^2+D_p/(\varepsilon_{\mathrm{DP}}\alpha)) n /2 = Ω ( D p / α 2 + D p / ( ε DP α )) 1 − β / 2 1-\beta/2 1 − β /2
L s ( q ) ≤ inf Q ∈ P p L s ( Q ) + c 0 2 c 2 α 2 . (10) L_s(q)\le\inf_{Q\in\mathcal{P}_p}L_s(Q)+c_0^2c^2\alpha^2. \tag*{(10)} L s ( q ) ≤ Q ∈ P p inf L s ( Q ) + c 0 2 c 2 α 2 . (10) The proof is given in Appendix § 11 .
Constructing the finite set of halfspaces
We now use the polynomial q q q Lemma 3.4 , this polynomial satisfies the squared-loss condition (Equation (8) ) of Lemma 3.2 with accuracy c α c\alpha c α Lemma 3.2 in Step 5 to construct H ( q ) \mathcal{H}(q) H ( q ) § 11 . The algorithm follows the subspace and discretization construction of Diakonikolas et al. [15 ] . Specifically, we compute
M = E X ∼ N ( 0 , I d ) [ ∇ q ( X ) ∇ q ( X ) T ] . M=\mathbb{E}_{X\sim\mathcal{N}(0,I_d)}\left[\nabla q(X)\nabla q(X)^{\mathsf T}\right]. M = E X ∼ N ( 0 , I d ) [ ∇ q ( X ) ∇ q ( X ) T ] . and take V V V c 2 α 2 / C 0 c^2\alpha^2/C_0 c 2 α 2 / C 0 O ( α − 4 ) O(\alpha^{-4}) O ( α − 4 ) V V V log ∣ H ( q ) ∣ = O ( α − 4 log ( 1 / α ) ) \log|\mathcal{H}(q)| = O\left(\alpha^{-4}\log(1/\alpha)\right) log ∣ H ( q ) ∣ = O ( α − 4 log ( 1/ α ) ) q q q
Lemma 3.4 guarantees the polynomial q q q U U U
Lemma 3.5. Suppose that d ≥ C d i m α − 5 d \ge C_{\mathrm{dim}}\alpha^{-5} d ≥ C dim α − 5 C d i m C_{\mathrm{dim}} C dim C C C q q q H ( q ) \mathcal{H}(q) H ( q ) q q q (10) ,
min h ∈ H ( q ) err P ( h ) ≤ OPT + ( C / 2 + 1 ) c α . \min_{h\in\mathcal{H}(q)} \operatorname{err}_{P}(h) \le\operatorname{OPT}+(C/2+1)c\alpha. h ∈ H ( q ) min err P ( h ) ≤ OPT + ( C /2 + 1 ) c α . Proof. On the event in the lemma, Lemma 3.2 gives, for every halfspace f ∈ C f \in\mathcal{C} f ∈ C h ∈ H ( q ) h \in\mathcal{H}(q) h ∈ H ( q ) E [ U ( f ( X ) − h ( X ) ) ] ≤ C c α \mathbb{E}[U(f(X)-h(X))] \le Cc\alpha E [ U ( f ( X ) − h ( X ))] ≤ C c α
err P ( h ) − err P ( f ) = 1 2 E [ Y ( f ( X ) − h ( X ) ) ] ≤ 1 2 E [ U ( f ( X ) − h ( X ) ) ] + E [ 1 − s ( X ) ] , \operatorname{err}_{P}(h)-\operatorname{err}_{P}(f)=\frac{1}{2}\mathbb{E}[Y(f(X)-h(X))]\le\frac{1}{2}\mathbb{E}[U(f(X)-h(X))]+\mathbb{E}[1-s(X)], err P ( h ) − err P ( f ) = 2 1 E [ Y ( f ( X ) − h ( X ))] ≤ 2 1 E [ U ( f ( X ) − h ( X ))] + E [ 1 − s ( X )] , it remains to bound the last term. As s ( X ) = 1 s(X)=1 s ( X ) = 1 E [ 1 − s ( X ) ] ≤ P [ ∥ ψ p ( X ) ∥ 2 > T ] ≤ c α \mathbb{E}[1-s(X)]\le\mathbb{P}\left[\lVert\psi_p(X)\rVert_2>T\right]\le c\alpha E [ 1 − s ( X )] ≤ P [ ∥ ψ p ( X ) ∥ 2 > T ] ≤ c α T = 2 D p T=2\sqrt{D_p} T = 2 D p d ≥ 2 p 2 / ( c α ) d\ge2p^2/(c\alpha) d ≥ 2 p 2 / ( c α )
Thus, H ( q ) \mathcal{H}(q) H ( q ) OPT + ( C / 2 + 1 ) c α \operatorname{OPT}+(C/2+1)c\alpha OPT + ( C /2 + 1 ) c α
:::
Selecting the best halfspace
Finally, Algorithm 2 selects a halfspace from H ( q ) \mathcal{H}(q) H ( q ) S 2 S_2 S 2 Y Y Y H ( q ) \mathcal{H}(q) H ( q ) S 2 S_2 S 2 c α c\alpha c α 1 − β / 2 1-\beta/2 1 − β /2
n = Ω ( ( α − 4 log ( 1 / α ) + log ( 1 / β ) ) ( 1 α 2 + 1 ε D P α ) ) . (11) n=\Omega\left(\left(\alpha^{-4}\log(1/\alpha)+\log(1/\beta)\right)\left(\frac{1}{\alpha^2}+\frac{1}{\varepsilon_{\mathrm{DP}}\alpha}\right)\right). \tag*{(11)} n = Ω ( ( α − 4 log ( 1/ α ) + log ( 1/ β ) ) ( α 2 1 + ε DP α 1 ) ) . (11) Combining this with Lemma 3.4 and taking c c c OPT + α \operatorname{OPT}+\alpha OPT + α 1 − β 1-\beta 1 − β S 1 S_1 S 1 S 2 S_2 S 2 n / 2 n/2 n /2 ( ε D P , δ D P ) (\varepsilon_{\mathrm{DP}},\delta_{\mathrm{DP}}) ( ε DP , δ DP )
Proof Sketch of Theorem 3.1. Algorithm 2 is the proper private learner achieving the guarantee in Theorem 3.1. Its output belongs to H ( q ) ⊆ C \mathcal{H}(q)\subseteq\mathcal{C} H ( q ) ⊆ C (8) in Lemma 3.2 with accuracy c α c\alpha c α 1 − β / 2 1-\beta/2 1 − β /2 H ( q ) \mathcal{H}(q) H ( q ) O ( α − 4 ) O(\alpha^{-4}) O ( α − 4 ) OPT + ( C / 2 + 1 ) c α \operatorname{OPT}+(C/2+1)c\alpha OPT + ( C /2 + 1 ) c α n n n (11) , the exponential mechanism adds at most c α c\alpha c α 1 − β / 2 1-\beta/2 1 − β /2 c c c ( ε D P , δ D P ) (\varepsilon_{\mathrm{DP}},\delta_{\mathrm{DP}}) ( ε DP , δ DP ) ε D P \varepsilon_{\mathrm{DP}} ε DP S 2 S_2 S 2 S 1 S_1 S 1 S 2 S_2 S 2 ( ε D P , δ D P ) (\varepsilon_{\mathrm{DP}},\delta_{\mathrm{DP}}) ( ε DP , δ DP )
Private Proper Semi-Agnostic Learning
In this section, we provide a DP algorithm for proper semi-agnostic learning of halfspaces whose sample complexity is polynomial in d d d 1 / α 1/\alpha 1/ α 1 / α 1/\alpha 1/ α Theorems 2.1 and 3.1 . The difference between semi-agnostic and agnostic error guarantee is that the former allows a universal constant factor multiplying OPT. We use a privatised version of the non-private gradient descent (on a non-convex function) algorithm of Diakonikolas et al. [17 ] as a subroutine. Roughly speaking, given an upper bound η ≥ \eta\geq η ≥ O ( η ) \mathcal{O}(\eta) O ( η ) η \eta η § 12 .
Theorem 4.1 (DP semi-agnostic proper learner). Let α , β , ε D P , δ D P ∈ ( 0 , 1 ) \alpha,\beta,\varepsilon_{\mathrm{DP}},\delta_{\mathrm{DP}} \in(0,1) α , β , ε DP , δ DP ∈ ( 0 , 1 ) P P P R d × { ± 1 } \mathbb{R}^{d} \times\{\pm1\} R d × { ± 1 } μ = N ( 0 , I d ) \mu= \mathcal{N}(0,I_d) μ = N ( 0 , I d ) ( ε D P , δ D P ) (\varepsilon_{\mathrm{DP}},\delta_{\mathrm{DP}}) ( ε DP , δ DP )
n = O ~ ( d α 2 + d ε D P α ) n = \widetilde{\mathcal{O}}\left(\frac{d}{\alpha^{2}}+\frac{d}{\varepsilon_{\mathrm{DP}}\alpha}\right) n = O ( α 2 d + ε DP α d ) i.i.d. samples from P P P d ≥ 16 log ( n / β ) d \geq16\log(n/\beta) d ≥ 16 log ( n / β ) h ∈ C h \in\mathcal{C} h ∈ C err P ( h ) ≤ C ⋅ O P T + α \operatorname{err}_{P}(h) \leq C\cdot\mathrm{OPT}+\alpha err P ( h ) ≤ C ⋅ OPT + α 1 − β 1-\beta 1 − β C > 0 C>0 C > 0 poly ( n ) \operatorname{poly}(n) poly ( n )
We make the above assumption on d d d § 12 .§ 2 ) for ease of exposition. It can be removed by setting the clipping parameter L L L O ( d + log ( n / β ) ) \mathcal{O}(\sqrt{d}+\sqrt{\log(n/\beta)}) O ( d + log ( n / β ) )
The Algorithm
We first describe the subroutine in Algorithm 3, which takes a known upper bound η ≥ \eta\geq η ≥ a > 0 a>0 a > 0 b ∈ R b \in\mathbb{R} b ∈ R
r a , b ( z ) = { 0 if z ≤ b − a , z − b + a if b − a < z < b + a , 2 a if z ≥ b + a . (12) r_{a,b}(z)=
\begin{cases}
0 & \text{if } z \leq b-a,\\
z-b+a & \text{if } b-a<z<b+a,\\
2a & \text{if } z \geq b+a.
\end{cases} \tag*{(12)} r a , b ( z ) = ⎩ ⎨ ⎧ 0 z − b + a 2 a if z ≤ b − a , if b − a < z < b + a , if z ≥ b + a . (12) Algorithm 3 follows Algorithms 1 and 2 from Diakonikolas et al. [17 ] , with noise added to the computations that access the dataset. The algorithm needs to privately estimate two quantities from the dataset before running gradient descent: the threshold parameter τ \tau τ w ^ 0 \widehat{w}_0 w 0 [17 ] first estimate the threshold from the average of the labels in D τ D_\tau D τ τ ^ \widehat{\tau} τ w ^ 0 \widehat{w}_0 w 0 x y xy x y D i n i t D_{\mathrm{init}} D init τ ^ \widehat{\tau} τ (12) and the private threshold τ ^ \widehat{\tau} τ D t D_t D t
With these modifications, Algorithm 3 privately returns a hypothesis with population classification error O ( η ) \mathcal{O}(\eta) O ( η ) η ≥ \eta\geq η ≥ η 1 , … , η K \eta_1,\ldots,\eta_K η 1 , … , η K η k \eta_k η k h k h_k h k O ( O P T + α ) \mathcal{O}(\mathrm{OPT}+\alpha) O ( OPT + α ) D v a l D_{\mathrm{val}} D val
Algorithm 3 DP Semi-Agnostic Subroutine DPSAS
Require: Dataset $D$ of $n_0$ labelled examples, privacy parameters $\varepsilon_{\mathrm{DP}}, \delta_{\mathrm{DP}} > 0$, and error parameter $\eta$.
Partition Dataset and Clip for DP
1: $s \leftarrow \Theta(1/\log^{3/2}(1/\eta))$ and $T \leftarrow \Theta(\log^4(1/\eta))$.
2: Partition $D$ into $D_{\mathrm{init}}, D_{\tau}, D_0, \ldots, D_{T-1}$, each of size $m_0 \leftarrow |D|/(T+2)$.
3: $L \leftarrow 2\sqrt{d}$ and clip each feature vector in $D$ to have norm at most $L$.
Privately computing threshold $\hat{\tau}$.
4: $\kappa \leftarrow C\eta$ for a universal constant $C$ and $\hat{y} \leftarrow \mathbb{E}_{(x,y)\sim D_{\tau}}[y] + z_{\tau}$,
where $z_{\tau} \sim \operatorname{Lap}\left(\frac{2}{\varepsilon_{\mathrm{DP}}m_0}\right)$.
5: $\hat{\tau} \leftarrow \Phi^{-1}\left(\operatorname{clip}_{\kappa}\left[\frac{1+\hat{y}}{2}\right]^{1-\kappa}\right)$.
Privately computing initial weight $\hat{w}_0$.
6: $\widetilde{w}_0 \leftarrow \mathbb{E}_{(x,y)\sim D_{\mathrm{init}}}[xy] + z_0$,
where $z_0 \sim \mathcal{N}(0,\sigma^2 I)$ and $\sigma \leftarrow \frac{2L\sqrt{2\log(2/\delta_{\mathrm{DP}})}}{\varepsilon_{\mathrm{DP}}m_0}$.
7: $\hat{w}_0 \leftarrow \frac{\widetilde{w}_0}{\|\widetilde{w}_0\|}$ if $\|\widetilde{w}_0\| \ne 0$, otherwise $\hat{w}_0 \sim S^{d-1}$ uniformly at random.
Run DP online gradient descent.
8: $\lambda \leftarrow e^{\pi^2/2}s$ and $B \leftarrow S^{d-1}$.
9: for $t=0$ to $T-1$ do
10: $\phi_t \leftarrow (\pi/2)(1-s^2/64)^t$, $a_t \leftarrow \sin(\phi_t)$, and $b_t \leftarrow -\hat{\tau}\cos(\phi_t)$.
11: $\hat{L}_t(w) \leftarrow \mathbb{E}_{(x,y)\sim D_t}\left[-r_{a_t,b_t}\left(\frac{w\cdot x}{\|w\|}\right)y\right]$.
12: $\hat{u} \leftarrow \hat{w}_t-\lambda(\nabla\hat{L}_t(\hat{w}_t)+z_{t+1})$ and $\hat{w}_{t+1} \leftarrow \operatorname{proj}_B(\hat{u})$,
where $z_{t+1} \sim \mathcal{N}(0,\sigma^2(I-\hat{w}_t\hat{w}_t^{\mathsf{T}}))$.
13: end for
14: Return $\hat{w}_T,\hat{\tau}$.Accuracy
A major component for proving the utility for Algorithm 4 is proving the accuracy guarantees for Algorithm 3. Note that by construction, α ≤ η k \alpha\le\eta_k α ≤ η k k ∈ [ K ] k \in[K] k ∈ [ K ] § 4.2 , we will omit the subscript from η k \eta_k η k η \eta η m 0 m_0 m 0 T + 2 T+2 T + 2 n 0 = ( T + 2 ) m 0 n_0=(T+2)m_0 n 0 = ( T + 2 ) m 0
Proposition 4.2. Let η ∈ ( 0 , 1 / 2 ) \eta\in(0,1/2) η ∈ ( 0 , 1/2 ) β , ε D P , δ D P ∈ ( 0 , 1 ) \beta,\varepsilon_{\mathrm{DP}},\delta_{\mathrm{DP}}\in(0,1) β , ε DP , δ DP ∈ ( 0 , 1 ) P P P R d × { ± 1 } \mathbb{R}^d \times\{\pm1\} R d × { ± 1 } μ = N ( 0 , I d ) \mu=\mathcal{N}(0,I_d) μ = N ( 0 , I d ) OPT ≤ η \operatorname{OPT}\le\eta OPT ≤ η ( ε D P , δ D P ) (\varepsilon_{\mathrm{DP}},\delta_{\mathrm{DP}}) ( ε DP , δ DP )
m 0 = O ~ ( d η 2 + d ε D P η ) m_0=\widetilde{O}\left(\frac{d}{\eta^2}+\frac{d}{\varepsilon_{\mathrm{DP}}\eta}\right) m 0 = O ( η 2 d + ε DP η d ) i.i.d. samples from P P P d ≥ 16 log ( n 0 / β ) d\ge16\log(n_0/\beta) d ≥ 16 log ( n 0 / β ) n 0 n_0 n 0 h ∈ C h\in\mathcal{C} h ∈ C err P ( h ) ≤ C η \operatorname{err}_P(h)\le C\eta err P ( h ) ≤ C η 1 − β 1-\beta 1 − β C > 0 C>0 C > 0
We follow the utility analysis of Diakonikolas et al. [17 ] , with modifications to account for the noise added for privacy. Their analysis starts with a weight vector that makes an angle less than π / 2 \pi/2 π /2 w ∗ w^* w ∗ w ∗ w^* w ∗ Claims 4.5 and 4.6 . They first prove population-level results, where they show that applying population-level gradients will slowly lead us to w ∗ w^* w ∗
The first result describes the structure of the noisy gradient and the updated weight vector. Its proof is given in Appendix § 12 .
Claim 4.3 (Modification of Claim C.2 from Diakonikolas et al. [17 ] ). For any unit vector w ∈ R d w \in\mathbb{R}^d w ∈ R d L ~ t ( w ) \widetilde{L}_t(w) L t ( w ) λ \lambda λ
w ′ = w − λ ∇ w L ~ t ( w ) ∥ w − λ ∇ w L ~ t ( w ) ∥ w' = \frac{w-\lambda\nabla_w\widetilde{L}_t(w)}{\left\lVert w-\lambda\nabla_w\widetilde{L}_t(w)\right\rVert} w ′ = w − λ ∇ w L t ( w ) w − λ ∇ w L t ( w ) such that
∇ w L ~ t ( w ) = E ( x , y ) ∼ D t [ − y 1 { ∣ w ⋅ x − b t ∣ ≤ a t } ∇ w w ⋅ x ∥ w ∥ ] + z t + 1 , \nabla_w\widetilde{L}_t(w) = \mathbb{E}_{(x,y)\sim D_t}\left[-y\mathbf{1}\left\{\left|w\cdot x-b_t\right|\le a_t\right\}\nabla_w\frac{w\cdot x}{\lVert w\rVert}\right]+z_{t+1}, ∇ w L t ( w ) = E ( x , y ) ∼ D t [ − y 1 { ∣ w ⋅ x − b t ∣ ≤ a t } ∇ w ∥ w ∥ w ⋅ x ] + z t + 1 , where z t + 1 ∼ N ( 0 , ( I − w w T ) σ 2 ) z_{t+1}\sim\mathcal{N}\left(0,(\mathbf{I}-ww^{\mathsf{T}})\sigma^2\right) z t + 1 ∼ N ( 0 , ( I − w w T ) σ 2 )
σ = 2 2 log ( 2 / δ D P ) ε D P m 0 . \sigma=\frac{2\sqrt{2\log(2/\delta_{\mathrm{DP}})}}{\varepsilon_{\mathrm{DP}}m_0}. σ = ε DP m 0 2 2 log ( 2/ δ DP ) . Next, we prove the DP analogue of Lemma C.12 from Diakonikolas et al. [17 ] and show that the original additive error guarantees are not affected by the added noise for DP. We keep the notation consistent with theirs, and define g ( w , ϕ , x , y ) = y ( proj w ⊥ x ) 1 { ∣ w ⋅ x + τ ^ cos ( ϕ ) ∣ ≤ sin ( ϕ ) } g(w,\phi,x,y)=y(\operatorname{proj}_{w^\perp}x)\mathbf{1}\{|w\cdot x+\widehat{\tau}\cos(\phi)|\le\sin(\phi)\} g ( w , ϕ , x , y ) = y ( proj w ⊥ x ) 1 { ∣ w ⋅ x + τ cos ( ϕ ) ∣ ≤ sin ( ϕ )} B ϕ = { z ∈ R : ∣ z + τ ^ cos ( ϕ ) ∣ ≤ sin ( ϕ ) } B_\phi=\{z\in\mathbb{R}:|z+\widehat{\tau}\cos(\phi)|\le\sin(\phi)\} B ϕ = { z ∈ R : ∣ z + τ cos ( ϕ ) ∣ ≤ sin ( ϕ )} f ( w , ϕ , x , y ) : = E ( x , y ) ∼ D [ g ( w , ϕ , x , y ) ] + z f(w,\phi,x,y):=\mathbb{E}_{(x,y)\sim D}[g(w,\phi,x,y)]+z f ( w , ϕ , x , y ) := E ( x , y ) ∼ D [ g ( w , ϕ , x , y )] + z z z z Claim 4.3 ).
Lemma 4.4 (Modification of Lemma C.12 from Diakonikolas et al. [17 ] ). Let q = Pr x ∼ μ [ w ⋅ x ∈ B ϕ ] q=\Pr_{x\sim\mu}[w\cdot x\in B_\phi] q = Pr x ∼ μ [ w ⋅ x ∈ B ϕ ]
m 0 ≥ O ( d q log ( 1 / β 0 ) η 2 + log ( d / β 0 ) q 2 + d log ( 1 / δ D P ) log ( 1 / β 0 ) η ε D P ) , m_0\ge O\left(\frac{dq\log(1/\beta_0)}{\eta^2}+\frac{\log(d/\beta_0)}{q^2}+\frac{d\sqrt{\log(1/\delta_{\mathrm{DP}})\log(1/\beta_0)}}{\eta\varepsilon_{\mathrm{DP}}}\right), m 0 ≥ O ( η 2 d q log ( 1/ β 0 ) + q 2 log ( d / β 0 ) + η ε DP d log ( 1/ δ DP ) log ( 1/ β 0 ) ) , we have with probability at least 1 − β 0 1-\beta_0 1 − β 0 u ∈ R d u\in\mathbb{R}^d u ∈ R d E ( x , y ) ∼ P [ g ( w , ϕ , x , y ) ⋅ u ] ≥ 0 \mathbb{E}_{(x,y)\sim P}[g(w,\phi,x,y)\cdot u]\ge0 E ( x , y ) ∼ P [ g ( w , ϕ , x , y ) ⋅ u ] ≥ 0
f ( w , ϕ , x , y ) ⋅ u ≥ 1 2 E ( x , y ) ∼ P [ g ( w , ϕ , x , y ) ⋅ u ] − O ( η ) f(w,\phi,x,y)\cdot u\ge\frac{1}{2}\mathbb{E}_{(x,y)\sim P}[g(w,\phi,x,y)\cdot u]-O(\eta) f ( w , ϕ , x , y ) ⋅ u ≥ 2 1 E ( x , y ) ∼ P [ g ( w , ϕ , x , y ) ⋅ u ] − O ( η ) and
∥ f ( w , ϕ , x , y ) ∥ ≤ 2 ∥ E ( x , y ) ∼ P [ g ( w , ϕ , x , y ) ] ∥ + O ( η ) . \lVert f(w,\phi,x,y)\rVert\le2\left\lVert\mathbb{E}_{(x,y)\sim P}[g(w,\phi,x,y)]\right\rVert+O(\eta). ∥ f ( w , ϕ , x , y )∥ ≤ 2 E ( x , y ) ∼ P [ g ( w , ϕ , x , y )] + O ( η ) . Proof. The proof remains the same, except for accounting for the error due to Gaussian noise. This lemma is applied on independent dataset D t D_t D t t t t D D D D t D_t D t [17 ] show the first line of the following.
u ⋅ E ( x , y ) ∼ D [ g ( w , ϕ , x , y ) ] ≥ u ⋅ E ( x , y ) ∼ P [ g ( w , ϕ , x , y ) ] Pr x ∼ D x [ w ⋅ x ∈ B ϕ ] Pr x ∼ μ [ w ⋅ x ∈ B ϕ ] − O ( η ) Pr x ∼ μ [ w ⋅ x ∈ B ϕ ] u\cdot\mathbb{E}_{(x,y)\sim D}[g(w,\phi,x,y)]\ge u\cdot\mathbb{E}_{(x,y)\sim P}[g(w,\phi,x,y)]\frac{\Pr_{x\sim D_x}[w\cdot x\in B_\phi]}{\Pr_{x\sim\mu}[w\cdot x\in B_\phi]}-O(\eta)\Pr_{x\sim\mu}[w\cdot x\in B_\phi] u ⋅ E ( x , y ) ∼ D [ g ( w , ϕ , x , y )] ≥ u ⋅ E ( x , y ) ∼ P [ g ( w , ϕ , x , y )] Pr x ∼ μ [ w ⋅ x ∈ B ϕ ] Pr x ∼ D x [ w ⋅ x ∈ B ϕ ] − O ( η ) x ∼ μ Pr [ w ⋅ x ∈ B ϕ ] ⟹ u ⋅ f ( w , ϕ , x , y ) ≥ u ⋅ E ( x , y ) ∼ P [ g ( w , ϕ , x , y ) ] Pr x ∼ D x [ w ⋅ x ∈ B ϕ ] Pr x ∼ μ [ w ⋅ x ∈ B ϕ ] − O ( η ) Pr x ∼ μ [ w ⋅ x ∈ B ϕ ] − ∥ z ∥ (13) \Longrightarrow\quad u\cdot f(w,\phi,x,y)\ge u\cdot\mathbb{E}_{(x,y)\sim P}[g(w,\phi,x,y)]\frac{\Pr_{x\sim D_x}[w\cdot x\in B_\phi]}{\Pr_{x\sim\mu}[w\cdot x\in B_\phi]}-O(\eta)\Pr_{x\sim\mu}[w\cdot x\in B_\phi]-\lVert z\rVert \tag*{(13)} ⟹ u ⋅ f ( w , ϕ , x , y ) ≥ u ⋅ E ( x , y ) ∼ P [ g ( w , ϕ , x , y )] Pr x ∼ μ [ w ⋅ x ∈ B ϕ ] Pr x ∼ D x [ w ⋅ x ∈ B ϕ ] − O ( η ) x ∼ μ Pr [ w ⋅ x ∈ B ϕ ] − ∥ z ∥ (13) Our private sample complexity allows ∥ z ∥ ≤ O ( η ) \lVert z\rVert\le O(\eta) ∥ z ∥ ≤ O ( η ) 1 − β 0 / 2 1-\beta_0/2 1 − β 0 /2 [17 ] .
We justify the norm bound separately. Let g p o p : = E [ g ( w , ϕ , X , Y ) ] g_{\mathrm{pop}} := \mathbb{E}[g(w,\phi,X,Y)] g pop := E [ g ( w , ϕ , X , Y )] g ^ : = E ( x , y ) ∼ D [ g ( w , ϕ , x , y ) ] \widehat{g} := \mathbb{E}_{(x,y)\sim\mathcal{D}}[g(w,\phi,x,y)] g := E ( x , y ) ∼ D [ g ( w , ϕ , x , y )] f = g ^ + z f = \widehat{g} + z f = g + z B ϕ B_\phi B ϕ q : = Pr X ∼ μ [ w ⋅ X ∈ B ϕ ] q := \Pr_{X\sim\mu}[w\cdot X\in B_\phi] q := Pr X ∼ μ [ w ⋅ X ∈ B ϕ ] q ^ : = 1 n ∑ i = 1 n 1 { w ⋅ x i ∈ B ϕ } \widehat{q} := \frac{1}{n}\sum_{i=1}^{n}\mathbf{1}\{w\cdot x_i\in B_\phi\} q := n 1 ∑ i = 1 n 1 { w ⋅ x i ∈ B ϕ } g ^ = 0 \widehat{g}=0 g = 0 u : = g ^ / ∥ g ^ ∥ u := \widehat{g}/\lVert\widehat{g}\rVert u := g / ∥ g ∥ z τ z_\tau z τ [17 ] , writing q ^ / q ∈ [ 1 / 2 , 2 ] \widehat{q}/q\in[1/2,2] q / q ∈ [ 1/2 , 2 ] u u u
u ⋅ g ^ ≤ q ^ q u ⋅ g p o p + O ( η ) u\cdot\widehat{g}\le\frac{\widehat{q}}{q}u\cdot g_{\mathrm{pop}}+O(\eta) u ⋅ g ≤ q q u ⋅ g pop + O ( η ) If g ^ = 0 \widehat{g}=0 g = 0 u = g ^ / ∥ g ^ ∥ u=\widehat{g}/\lVert\widehat{g}\rVert u = g / ∥ g ∥ u ⋅ g p o p ≥ 0 u\cdot g_{\mathrm{pop}}\ge0 u ⋅ g pop ≥ 0
∥ g ^ ∥ ≤ 2 u ⋅ g p o p + O ( η ) ≤ 2 ∥ g p o p ∥ + O ( η ) . \lVert\widehat{g}\rVert\le2u\cdot g_{\mathrm{pop}}+O(\eta)\le2\lVert g_{\mathrm{pop}}\rVert+O(\eta). ∥ g ∥ ≤ 2 u ⋅ g pop + O ( η ) ≤ 2 ∥ g pop ∥ + O ( η ) . If u ⋅ g p o p < 0 u\cdot g_{\mathrm{pop}}<0 u ⋅ g pop < 0 q ^ / q ≥ 1 / 2 \widehat{q}/q\ge1/2 q / q ≥ 1/2
q ^ q u ⋅ g p o p ≤ 1 2 u ⋅ g p o p < 0 , \frac{\widehat{q}}{q}u\cdot g_{\mathrm{pop}}\le\frac{1}{2}u\cdot g_{\mathrm{pop}}<0, q q u ⋅ g pop ≤ 2 1 u ⋅ g pop < 0 , and hence ∥ g ^ ∥ ≤ O ( η ) \lVert\widehat{g}\rVert\le O(\eta) ∥ g ∥ ≤ O ( η ) ∥ g ^ ∥ ≤ 2 ∥ g p o p ∥ + O ( η ) \lVert\widehat{g}\rVert\le2\lVert g_{\mathrm{pop}}\rVert+O(\eta) ∥ g ∥ ≤ 2 ∥ g pop ∥ + O ( η ) ∥ z ∥ ≤ O ( η ) \lVert z\rVert\le O(\eta) ∥ z ∥ ≤ O ( η )
∥ f ∥ ≤ ∥ g ^ ∥ + ∥ z ∥ ≤ 2 ∥ g p o p ∥ + O ( η ) , \lVert f\rVert\le\lVert\widehat{g}\rVert+\lVert z\rVert\le2\lVert g_{\mathrm{pop}}\rVert+O(\eta), ∥ f ∥ ≤ ∥ g ∥ + ∥ z ∥ ≤ 2 ∥ g pop ∥ + O ( η ) , as claimed.
Now, writing θ = θ ( w , w ∗ ) \theta=\theta(w,w^*) θ = θ ( w , w ∗ ) v ⋅ E ( x , y ) ∼ P [ g ( w , ϕ , x , y ) ] ≥ sin ( θ ) e − τ 2 / 2 > 0 v\cdot\mathbb{E}_{(x,y)\sim\mathcal{P}}[g(w,\phi,x,y)]\ge\sin(\theta)e^{-\tau^2/2}>0 v ⋅ E ( x , y ) ∼ P [ g ( w , ϕ , x , y )] ≥ sin ( θ ) e − τ 2 /2 > 0 [17 ] . They then condition on the event A k A_k A k v v v ( E ( x , y ) ∼ P [ g ( w , ϕ , x , y ) ⋅ u ] ≥ 0 ) (\mathbb{E}_{(x,y)\sim\mathcal{P}}[g(w,\phi,x,y)\cdot u]\ge0) ( E ( x , y ) ∼ P [ g ( w , ϕ , x , y ) ⋅ u ] ≥ 0 ) v ⋅ E ( x , y ) ∼ P [ g ( w , ϕ , x , y ) ] v\cdot\mathbb{E}_{(x,y)\sim\mathcal{P}}[g(w,\phi,x,y)] v ⋅ E ( x , y ) ∼ P [ g ( w , ϕ , x , y )] w ∗ ⋅ E ( x , y ) ∼ P [ g ( w , ϕ , x , y ) ] w^*\cdot\mathbb{E}_{(x,y)\sim\mathcal{P}}[g(w,\phi,x,y)] w ∗ ⋅ E ( x , y ) ∼ P [ g ( w , ϕ , x , y )] w ∗ w^* w ∗
Next, we show that the DP initialization w 0 w_0 w 0 [17 ] ). They require that the dot product of the true weight w ∗ w^* w ∗
Claim 4.5. Suppose e − τ ^ 2 / 2 ∣ τ ^ ∣ ≥ c η \frac{e^{-\widehat{\tau}^2/2}}{|\widehat{\tau}|}\ge c\eta ∣ τ ∣ e − τ 2 /2 ≥ cη 1 − O ( β ) 1-O(\beta) 1 − O ( β )
m 0 ≥ O ~ ( d η 2 + d log ( 1 / δ D P ) ϵ D P η ) m_0\ge\widetilde{O}\left(\frac{d}{\eta^2}+\frac{\sqrt{d\log(1/\delta_{\mathrm{DP}})}}{\epsilon_{\mathrm{DP}}\eta}\right) m 0 ≥ O ( η 2 d + ϵ DP η d log ( 1/ δ DP ) ) the private initializer satisfies w ∗ ⋅ w ^ 0 > 0 w^*\cdot\widehat{w}_0>0 w ∗ ⋅ w 0 > 0
We only invoke Claim 4.5 in the above non-trivial regime. In the complementary case e − τ ^ 2 / 2 ∣ τ ^ ∣ < C η \frac{e^{-\widehat{\tau}^2/2}}{|\widehat{\tau}|}<C\eta ∣ τ ∣ e − τ 2 /2 < C η [17 ] already implies that using the threshold τ ^ \widehat{\tau} τ O ( η ) O(\eta) O ( η )
Claim 4.6 (Modification of Claim C.9 from Diakonikolas et al., [17 ] ). Suppose η , β 0 ∈ ( 0 , 1 / 2 ) \eta, \beta_0 \in(0,1/2) η , β 0 ∈ ( 0 , 1/2 ) w ∗ \mathbf{w}^* w ∗ τ \tau τ Pr ( x , y ) ∼ P [ sign ( w ∗ ⋅ x + τ ) ≠ y ] ≤ η \Pr_{(x,y)\sim P}[\operatorname{sign}(\mathbf{w}^* \cdot x+\tau)\ne y]\le\eta Pr ( x , y ) ∼ P [ sign ( w ∗ ⋅ x + τ ) = y ] ≤ η τ ^ = Φ − 1 ( clip ( [ 1 + E ( x , y ) ∼ D [ y ] + z τ ] / 2 ) κ 1 − κ ) \hat{\tau}=\Phi^{-1}\left(\operatorname{clip}\left([1+\mathbb{E}_{(x,y)\sim D}[y]+z_\tau]/2\right)_{\kappa}^{1-\kappa}\right) τ ^ = Φ − 1 ( clip ( [ 1 + E ( x , y ) ∼ D [ y ] + z τ ] /2 ) κ 1 − κ ) κ = O ( η ) \kappa=O(\eta) κ = O ( η ) τ \tau τ
m 0 ≥ O ( log ( 1 / β 0 ) η 2 + log ( 1 / β 0 ) ε D P η ) , m_0 \ge O\left(\frac{\log(1/\beta_0)}{\eta^2}+\frac{\log(1/\beta_0)}{\varepsilon_{\mathrm{DP}}\eta}\right), m 0 ≥ O ( η 2 log ( 1/ β 0 ) + ε DP η log ( 1/ β 0 ) ) , then with probability at least 1 − β 0 1-\beta_0 1 − β 0
Pr ( x , y ) ∼ P [ sign ( w ∗ ⋅ x + τ ^ ) ≠ y ] ≤ O ( η ) . \Pr_{(x,y)\sim P}[\operatorname{sign}(\mathbf{w}^*\cdot x+\hat{\tau})\ne y]\le O(\eta). ( x , y ) ∼ P Pr [ sign ( w ∗ ⋅ x + τ ^ ) = y ] ≤ O ( η ) . Proof. Diakonikolas et al. [17 ] show that satisfying ∣ E ( x , y ) ∼ D [ y ] − E ( x , y ) ∼ P [ y ] ∣ ≤ O ( η ) |\mathbb{E}_{(x,y)\sim D}[y]-\mathbb{E}_{(x,y)\sim P}[y]|\le O(\eta) ∣ E ( x , y ) ∼ D [ y ] − E ( x , y ) ∼ P [ y ] ∣ ≤ O ( η ) ∣ E ( x , y ) ∼ D [ y ] + z τ − E ( x , y ) ∼ P [ y ] ∣ ≤ O ( η ) |\mathbb{E}_{(x,y)\sim D}[y]+z_\tau-\mathbb{E}_{(x,y)\sim P}[y]|\le O(\eta) ∣ E ( x , y ) ∼ D [ y ] + z τ − E ( x , y ) ∼ P [ y ] ∣ ≤ O ( η ) Φ − 1 \Phi^{-1} Φ − 1 [ κ , 1 − κ ] [\kappa,1-\kappa] [ κ , 1 − κ ] κ = C η \kappa=C\eta κ = C η C > 0 C>0 C > 0
Let p ~ = ( 1 + E ( x , y ) ∼ D ^ [ y ] + z τ ) / 2 \tilde{p}=(1+\mathbb{E}_{(x,y)\sim\hat{D}}[y]+z_\tau)/2 p ~ = ( 1 + E ( x , y ) ∼ D ^ [ y ] + z τ ) /2 p ^ = clip ( p ~ , [ κ , 1 − κ ] ) \hat{p}=\operatorname{clip}(\tilde{p},[\kappa,1-\kappa]) p ^ = clip ( p ~ , [ κ , 1 − κ ]) z τ z_\tau z τ 2 / m 0 ε D P 2/m_0\varepsilon_{\mathrm{DP}} 2/ m 0 ε DP ∣ z τ ∣ ≤ 2 log ( 1 / β 0 ) / m 0 ε D P |z_\tau|\le2\log(1/\beta_0)/m_0\varepsilon_{\mathrm{DP}} ∣ z τ ∣ ≤ 2 log ( 1/ β 0 ) / m 0 ε DP 1 − β 0 1-\beta_0 1 − β 0 O ( η ) O(\eta) O ( η ) m 0 ≥ O ( log ( 1 / β 0 ) / ε D P η ) m_0\ge O(\log(1/\beta_0)/\varepsilon_{\mathrm{DP}}\eta) m 0 ≥ O ( log ( 1/ β 0 ) / ε DP η ) p ∈ [ 0 , 1 ] p\in[0,1] p ∈ [ 0 , 1 ] ∣ p ^ − p ∣ ≤ ∣ p ~ − p ∣ + κ |\hat{p}-p|\le|\tilde{p}-p|+\kappa ∣ p ^ − p ∣ ≤ ∣ p ~ − p ∣ + κ O ( η ) O(\eta) O ( η ) p = ( 1 + E ( x , y ) ∼ P [ y ] ) / 2 p=(1+\mathbb{E}_{(x,y)\sim P}[y])/2 p = ( 1 + E ( x , y ) ∼ P [ y ]) /2 ∣ p ^ − p ∣ ≤ O ( η ) |\hat{p}-p|\le O(\eta) ∣ p ^ − p ∣ ≤ O ( η ) τ ^ = Φ − 1 ( p ^ ) \hat{\tau}=\Phi^{-1}(\hat{p}) τ ^ = Φ − 1 ( p ^ )
Putting It All Together
Proof of Proposition 4.2. As mentioned earlier, our modifications are needed only for dataset-level results. Claims C.2 and C.9, along with Lemma C.12, are the only ones that needed modifications. Note that the technical results in Appendices B and C from Diakonikolas et al. [17 ] still hold when we are using independent samples for threshold estimation, initialization, and each iteration of gradient descent, so they transfer to our private case, as well. We have shown via Claims 4.3 and 4.6 , and Lemma 4.4 , respectively, that at minimal cost in sample complexity, those results hold. Additionally, they prove that their initial weight vector w 0 w_0 w 0 w ∗ \mathbf{w}^* w ∗ Claim 4.5 that the same holds for our noisy initialization w ^ 0 \hat{w}_0 w ^ 0
The grid in Algorithm 4 starts at η 1 = C η α \eta_1=C_\eta\alpha η 1 = C η α C η > 1 C_\eta>1 C η > 1 η k = 2 k − 1 η 1 \eta_k=2^{k-1}\eta_1 η k = 2 k − 1 η 1 k ∈ [ K ] k\in[K] k ∈ [ K ] D v a l D_{\mathrm{val}} D val K K K D 1 , … , D K D^1,\ldots,D^K D 1 , … , D K k ∈ [ K ] k\in[K] k ∈ [ K ] D k D^k D k η k \eta_k η k h k h_k h k
Proof of Theorem 4.1 . Proposition F.1 provides the privacy guarantees. Now, we complete the proof of accuracy. First, note that the difference between the final error guarantee required to be in O ( α ) O(\alpha) O ( α ) η k \eta_k η k η k ≥ α \eta_k\ge\alpha η k ≥ α k ∈ [ K ] k\in[K] k ∈ [ K ] OPT < η 1 \operatorname{OPT}<\eta_1 OPT < η 1 k ∗ ∈ [ K ] ∖ { 1 } k^*\in[K]\setminus\{1\} k ∗ ∈ [ K ] ∖ { 1 } η 1 2 k ∗ − 2 ≤ OPT ≤ η 1 2 k ∗ − 1 \eta_1 2^{k^*-2}\le\operatorname{OPT}\le\eta_1 2^{k^*-1} η 1 2 k ∗ − 2 ≤ OPT ≤ η 1 2 k ∗ − 1 k ∈ [ K ] k\in[K] k ∈ [ K ] h k h_k h k O ( OPT + α ) O(\operatorname{OPT}+\alpha) O ( OPT + α )
When OPT < η 1 \operatorname{OPT}<\eta_1 OPT < η 1 h h h h h h O ( η 1 ) = O ( α ) O(\eta_1)=O(\alpha) O ( η 1 ) = O ( α ) 1 − β ′ 1-\beta' 1 − β ′ β ′ = β / K \beta'=\beta/K β ′ = β / K η \eta η α = Θ ( η 1 ) \alpha=\Theta(\eta_1) α = Θ ( η 1 )
On the other hand, suppose there exists k ∗ ∈ [ K ] ∖ { 1 } k^*\in[K]\setminus\{1\} k ∗ ∈ [ K ] ∖ { 1 } η 1 2 k ∗ − 2 ≤ OPT ≤ η 1 2 k ∗ − 1 \eta_1 2^{k^*-2}\le\operatorname{OPT}\le\eta_1 2^{k^*-1} η 1 2 k ∗ − 2 ≤ OPT ≤ η 1 2 k ∗ − 1 1 − ( K − 1 ) β ′ 1-(K-1)\beta' 1 − ( K − 1 ) β ′ k ≥ k ∗ k\ge k^* k ≥ k ∗ h k h_k h k O ( η k ) \mathcal{O}(\eta_k) O ( η k ) k ∗ k^* k ∗ η k ∗ = η 1 2 k ∗ − 1 ≤ 2 OPT \eta_{k^*}=\eta_1 2^{k^*-1}\le2\operatorname{OPT} η k ∗ = η 1 2 k ∗ − 1 ≤ 2 OPT h k ∗ h_{k^*} h k ∗ O ( OPT ) \mathcal{O}(\operatorname{OPT}) O ( OPT )
Combining the two together, with probability at least 1 − O ( β ) 1-\mathcal{O}(\beta) 1 − O ( β ) k ∈ [ K ] k\in[K] k ∈ [ K ] h k h_k h k max { O ( α ) , O ( OPT ) } \max\{\mathcal{O}(\alpha),\mathcal{O}(\operatorname{OPT})\} max { O ( α ) , O ( OPT )} 1 − O ( β ) 1-\mathcal{O}(\beta) 1 − O ( β ) k ∈ [ K ] k\in[K] k ∈ [ K ] err P ( h k ) \operatorname{err}_P(h_k) err P ( h k ) err ^ D v a l ( h k ) \widehat{\operatorname{err}}_{D_{\mathrm{val}}}(h_k) err D val ( h k ) D v a l D_{\mathrm{val}} D val
∣ err P ( h k ) − err ^ D v a l ( h k ) ∣ ≤ O ( log ( K / β ) ∣ D v a l ∣ ) ≤ O ( α ) . \left|\operatorname{err}_P(h_k)-\widehat{\operatorname{err}}_{D_{\mathrm{val}}}(h_k)\right|\le\mathcal{O}\left(\sqrt{\frac{\log(K/\beta)}{|D_{\mathrm{val}}|}}\right)\le\mathcal{O}(\alpha). ∣ err P ( h k ) − err D val ( h k ) ∣ ≤ O ( ∣ D val ∣ log ( K / β ) ) ≤ O ( α ) . With probability at least 1 − O ( β ) 1-\mathcal{O}(\beta) 1 − O ( β ) h ˉ \bar{h} h ˉ O ( α ) \mathcal{O}(\alpha) O ( α ) h k h_k h k h ˉ \bar{h} h ˉ max { O ( α ) , O ( OPT ) } + O ( α ) \max\{\mathcal{O}(\alpha),\mathcal{O}(\operatorname{OPT})\}+\mathcal{O}(\alpha) max { O ( α ) , O ( OPT )} + O ( α )
Finally, we bound the running time. Each run of Algorithm 3 uses every sample in its data a constant number of times (for clipping, the estimates of τ ^ \hat{\tau} τ ^ w ^ 0 \hat{w}_0 w ^ 0 O ( d ) \mathcal{O}(d) O ( d ) K = O ( log ( 1 / α ) ) K=\mathcal{O}(\log(1/\alpha)) K = O ( log ( 1/ α )) O ( n d ) \mathcal{O}(nd) O ( n d ) K K K D v a l D_{\mathrm{val}} D val O ( n d log ( 1 / α ) ) \mathcal{O}(nd\log(1/\alpha)) O ( n d log ( 1/ α )) d ≤ n d\le n d ≤ n O ( n d log ( 1 / α ) ) = poly ( n ) \mathcal{O}(nd\log(1/\alpha))=\operatorname{poly}(n) O ( n d log ( 1/ α )) = poly ( n )
Conclusion and Open Problems
We provide the first computationally efficient DP agnostic learners for halfspaces, where privacy comes for free in terms of sample complexity, i.e., the sample complexity overhead due to privacy matches that of the non-private learners. Specifically, we study three settings: improper agnostic, proper agnostic, and semi-agnostic. Our techniques are based on those of the non-private work, albeit with additional steps and analyses to incorporate clipping and noise injection to provide DP guarantees.
One avenue for improvement is in the improper agnostic setting, where we have to explicitly compute the orthonormal basis for each family of distributions when the marginals are known, unlike Kalai et al. [29 ] , who work with the standard polynomial basis for all families of distributions. The only parameter they need to know for their kernel is the degree of the polynomial. An interesting future direction is to find more versatile polynomial bases that admit bounded coefficients for a large family of distributions, or alternatively to learn such a basis privately from the data, removing the need to know the marginal in advance. Another direction is to design efficient DP algorithms for agnostic learning of concept classes beyond halfspaces. Finally, one could explore lower bounds in DP agnostic learning to determine the necessary sample complexity overhead for these problems.
Acknowledgements and AI Disclosure
The authors acknowledge the Novo Nordisk Foundation for support via the Startup grant (NNF24OCO 087820); AS additionally acknowledges support from VILLUM FONDEN via the Young Investigator program (VIL72069).
The main ideas underlying this work were developed by the authors. AI tools were used to help sharpen the parameter dependence of technical lemmas. The authors take full responsibility for the correctness of the results and the content of the final manuscript.
Other Related Work
Agnostic learning under structured marginals. Without distributional assumptions, agnostically learning halfspaces is computationally hard, even for weak learning [26 , 22 , 10 , 48 ] . Building on the low-degree Fourier approach of Linial et al. [38 ] , Kalai et al. [29 ] use polynomial L 1 L_1 L 1 O P T + α \mathrm{OPT}+\alpha OPT + α L 1 L_1 L 1 [11 ] improved the runtime of Kalai et al. [29 ] from d O ( α − 4 ) d^{O(\alpha^{-4})} d O ( α − 4 ) d O ( α − 2 ) d^{O(\alpha^{-2})} d O ( α − 2 ) d Ω ( α − 2 ) d^{\Omega(\alpha^{-2})} d Ω ( α − 2 ) [25 , 13 , 16 ] , and a nearly matching lower bound holds for all polynomial-time algorithms under the subexponential hardness of Learning with Errors [18 ] . However, this approach is improper, as the resulting classifier need not be a halfspace. Diakonikolas et al. [15 ] addressed this limitation by using polynomial regression to identify a subspace containing the normal vector of a near-optimal halfspace; this yields a proper learner with error O P T + α \mathrm{OPT}+\alpha OPT + α d poly ( 1 / α ) d^{\operatorname{poly}(1/\alpha)} d poly ( 1/ α )
Semi-agnostic learning. Motivated by these computational barriers, a related line of work improves computational efficiency by relaxing the agnostic error guarantee. For homogeneous halfspaces, Awasthi et al. [4 ] developed a localization-based algorithm achieving O ( O P T ) + α O(\mathrm{OPT})+\alpha O ( OPT ) + α [9 ] obtains an improper approximation scheme under the uniform spherical marginal, achieving error ( 1 + γ ) O P T + α (1+\gamma)\mathrm{OPT}+\alpha ( 1 + γ ) OPT + α d d d 1 / α 1/\alpha 1/ α γ > 0 \gamma>0 γ > 0 [15 ] give a proper analogue under Gaussian marginals. Diakonikolas et al. [14 ] showed that non-convex SGD achieves O ( O P T ) + α O(\mathrm{OPT})+\alpha O ( OPT ) + α [12 ] obtained constant-factor guarantees, even in a stronger contamination model allowing corruption of both examples and labels, and Diakonikolas et al. [17 ] developed the sample-efficient online gradient descent algorithm on which our private semi-agnostic learner builds. Complementary work studies convex surrogates for homogeneous halfspaces. Under well-behaved marginals, including isotropic log-concave distributions, Frei et al. [23 ] obtain O ~ ( O P T ) + α \widetilde{O}(\sqrt{\mathrm{OPT}})+\alpha O ( OPT ) + α [28 ] show that logistic regression alone cannot improve on this and obtain O ~ ( O P T ) + α \widetilde{O}(\mathrm{OPT})+\alpha O ( OPT ) + α
Private learning. Distribution-free private learning of halfspaces over infinite domains is impossible: already thresholds over R \mathbb{R} R [7 ] , and private learnability is characterized by finite Littlestone dimension [39 , 1 , 8 ] . Over finite domains X ⊂ R d X\subset\mathbb{R}^d X ⊂ R d [6 ] (improved by Kaplan et al. [32 ] ) give private agnostic learners whose sample complexity grows with log ∗ ∣ X ∣ \log^{*}|X| log ∗ ∣ X ∣ [2 ] (Li et al. 2025) are statistically efficient but not computationally efficient in general. Efficient private PAC learners exist under margin assumptions [43 , 5 ] , with guarantees stated for margin-based losses rather than O P T \mathrm{OPT} OPT
Auxiliary Results
Concentration Inequalities
Lemma B.1 (Vector Bernstein Inequality). Let U 1 , … , U n U_1,\ldots,U_n U 1 , … , U n R d \mathbb{R}^d R d ∥ U i ∥ 2 ≤ B \lVert U_i\rVert_2 \le B ∥ U i ∥ 2 ≤ B i ∈ { 1 , … , n } i \in\{1,\ldots,n\} i ∈ { 1 , … , n } ∑ i = 1 n E ∥ U i ∥ 2 2 ≤ v \sum_{i=1}^n \mathbb{E}\lVert U_i\rVert_2^2 \le v ∑ i = 1 n E ∥ U i ∥ 2 2 ≤ v β ∈ ( 0 , 1 ) \beta\in(0,1) β ∈ ( 0 , 1 ) 1 − β 1-\beta 1 − β
∥ 1 n ∑ i = 1 n U i ∥ 2 ≤ 2 v log ( 2 / β ) n + 2 B log ( 2 / β ) 3 n . \left\lVert\frac{1}{n}\sum_{i=1}^n U_i \right\rVert_2 \le\frac{\sqrt{2v\log(2/\beta)}}{n}+\frac{2B\log(2/\beta)}{3n}. n 1 i = 1 ∑ n U i 2 ≤ n 2 v log ( 2/ β ) + 3 n 2 B log ( 2/ β ) . Differential Privacy Tools
Definition B.2 (Differential privacy; Dwork et al., [21 ] ). Let ε D P > 0 \varepsilon_{\mathrm{DP}}>0 ε DP > 0 δ D P ∈ [ 0 , 1 ) \delta_{\mathrm{DP}}\in[0,1) δ DP ∈ [ 0 , 1 ) A : Z n → Y \mathcal{A}:\mathcal{Z}^n\to\mathcal{Y} A : Z n → Y ( ε D P , δ D P ) (\varepsilon_{\mathrm{DP}},\delta_{\mathrm{DP}}) ( ε DP , δ DP ) S , S ′ ∈ Z n S,S'\in\mathcal{Z}^n S , S ′ ∈ Z n E ⊆ Y E\subseteq\mathcal{Y} E ⊆ Y
Pr [ A ( S ) ∈ E ] ≤ e ε D P Pr [ A ( S ′ ) ∈ E ] + δ D P . \Pr[\mathcal{A}(S)\in E]\le e^{\varepsilon_{\mathrm{DP}}}\Pr[\mathcal{A}(S')\in E]+\delta_{\mathrm{DP}}. Pr [ A ( S ) ∈ E ] ≤ e ε DP Pr [ A ( S ′ ) ∈ E ] + δ DP . Lemma B.3 (Post-Processing of DP; Dwork and Roth, [20 ] ). If M : X n → Y M:\mathcal{X}^n\to\mathcal{Y} M : X n → Y ( ε D P , δ D P ) (\varepsilon_{\mathrm{DP}},\delta_{\mathrm{DP}}) ( ε DP , δ DP ) f : Y → Z f:\mathcal{Y}\to\mathcal{Z} f : Y → Z f ∘ M f\circ M f ∘ M ( ε D P , δ D P ) (\varepsilon_{\mathrm{DP}},\delta_{\mathrm{DP}}) ( ε DP , δ DP )
Lemma B.4 (Private convex ERM; Kulkarni et al., [36 ] , Theorem 1.1). Let Ω ⊆ R D \Omega\subseteq\mathbb{R}^D Ω ⊆ R D R R R ℓ ( ⋅ ; z ) : R D → R \ell(\cdot;z):\mathbb{R}^D\to\mathbb{R} ℓ ( ⋅ ; z ) : R D → R T T T z ∈ Z z\in\mathcal{Z} z ∈ Z n ≥ 2 n\ge2 n ≥ 2 0 < ε D P ≤ 1 / 2 0<\varepsilon_{\mathrm{DP}}\le1/2 0 < ε DP ≤ 1/2 0 < δ D P ≤ 1 / 2 0<\delta_{\mathrm{DP}}\le1/2 0 < δ DP ≤ 1/2 ( ε D P , δ D P ) (\varepsilon_{\mathrm{DP}},\delta_{\mathrm{DP}}) ( ε DP , δ DP ) S = ( Z 1 , … , Z n ) ∈ Z n S=(Z_1,\ldots,Z_n)\in\mathcal{Z}^n S = ( Z 1 , … , Z n ) ∈ Z n v ^ ∈ Ω \hat{v}\in\Omega v ^ ∈ Ω
E [ L ^ S ( v ^ ) ] − min v ∈ Ω L ^ S ( v ) ≤ O ( T R D log ( 1 / δ D P ) n ε D P ) , \mathbb{E}\left[\widehat{L}_S(\hat{v})\right]-\min_{v\in\Omega}\widehat{L}_S(v)\le O\left(\frac{TR\sqrt{D\log(1/\delta_{\mathrm{DP}})}}{n\varepsilon_{\mathrm{DP}}}\right), E [ L S ( v ^ ) ] − v ∈ Ω min L S ( v ) ≤ O ( n ε DP T R D log ( 1/ δ DP ) ) , where L ^ S ( v ) : = 1 n ∑ i = 1 n ℓ ( v ; Z i ) \widehat{L}_S(v):=\frac{1}{n}\sum_{i=1}^n\ell(v;Z_i) L S ( v ) := n 1 ∑ i = 1 n ℓ ( v ; Z i ) O ( n 2 ) O(n^2) O ( n 2 ) Ω \Omega Ω
Proof. Compared to Kulkarni et al. [36 ] , we use R R R T T T R D \mathbb{R}^D R D O ( n 2 ) O(n^2) O ( n 2 )
Lemma B.5 (Validation via the exponential mechanism). Let K , m ∈ N K,m\in\mathbb{N} K , m ∈ N h 1 , … , h K h_1,\ldots,h_K h 1 , … , h K S v a l ∼ P m S_{\mathrm{val}}\sim P^m S val ∼ P m ε D P > 0 \varepsilon_{\mathrm{DP}}>0 ε DP > 0 j ^ ∈ [ K ] \hat{j}\in[K] j ^ ∈ [ K ] exp ( − ε D P m err ^ S v a l ( h j ) / 2 ) \exp(-\varepsilon_{\mathrm{DP}}m\widehat{\operatorname{err}}_{S_{\mathrm{val}}}(h_j)/2) exp ( − ε DP m err S val ( h j ) /2 ) ε D P \varepsilon_{\mathrm{DP}} ε DP 0 < η < 1 0<\eta<1 0 < η < 1 1 − η 1-\eta 1 − η
err P ( h j ^ ) ≤ min j ∈ [ K ] err P ( h j ) + 2 log ( 4 K / η ) 2 m + 2 log ( 2 K / η ) ε D P m . \operatorname{err}_P(h_{\hat{j}})\le\min_{j\in[K]}\operatorname{err}_P(h_j)+2\sqrt{\frac{\log(4K/\eta)}{2m}}+\frac{2\log(2K/\eta)}{\varepsilon_{\mathrm{DP}}m}. err P ( h j ^ ) ≤ j ∈ [ K ] min err P ( h j ) + 2 2 m log ( 4 K / η ) + ε DP m 2 log ( 2 K / η ) . Proof. Condition on the candidates. Hoeffding’s inequality (Hoeffding, [27 ] ) and a union bound give the first slack term, accounting for the deviations of validation errors from population errors for both the selected classifier and the best candidate. The score − m err ^ S v a l ( h j ) -m\widehat{\operatorname{err}}_{S_{\mathrm{val}}}(h_j) − m err S val ( h j ) [41 ] ). Allocate failure probability η / 2 \eta/2 η /2
L 1 L^1 L 1 Fact B.6 (Random thresholding; Kalai et al., [29 ] , Proof of Theorem 5). Let τ ∼ Unif [ − 1 , 1 ] \tau\sim\operatorname{Unif}[-1,1] τ ∼ Unif [ − 1 , 1 ] z ∈ R z \in\mathbb{R} z ∈ R y ∈ { − 1 , 1 } y \in\{-1,1\} y ∈ { − 1 , 1 } Pr τ [ sign ( z − τ ) ≠ y ] ≤ 1 2 ∣ z − y ∣ \Pr_{\tau}[\operatorname{sign}(z-\tau) \ne y] \le\frac{1}{2}|z-y| Pr τ [ sign ( z − τ ) = y ] ≤ 2 1 ∣ z − y ∣
Lemma B.7 (Uniform deviation for L 1 L^1 L 1 ϕ : X → R D \phi:\mathcal{X}\to\mathbb{R}^{D} ϕ : X → R D E ∥ ϕ ( X ) ∥ 2 2 ≤ D \mathbb{E}\|\phi(X)\|_{2}^{2}\le D E ∥ ϕ ( X ) ∥ 2 2 ≤ D L P ( v ) = E ∣ ⟨ v , ϕ ( X ) ⟩ − Y ∣ L_P(v)=\mathbb{E}\left|\langle v,\phi(X)\rangle-Y\right| L P ( v ) = E ∣ ⟨ v , ϕ ( X )⟩ − Y ∣ L ^ S ( v ) \widehat{L}_S(v) L S ( v ) S ∼ P n S\sim P^n S ∼ P n R > 0 R>0 R > 0
E S ∼ P n sup ∥ v ∥ 2 ≤ R ( L P ( v ) − L ^ S ( v ) ) ≤ 2 R D n . \mathbb{E}_{S\sim P^n}\sup_{\|v\|_2\le R}\left(L_P(v)-\widehat{L}_S(v)\right)\le2R\sqrt{\frac{D}{n}}. E S ∼ P n ∥ v ∥ 2 ≤ R sup ( L P ( v ) − L S ( v ) ) ≤ 2 R n D . Proof. Let σ 1 , … , σ n \sigma_1,\ldots,\sigma_n σ 1 , … , σ n S S S [46 ] ) and contraction for the 1-Lipschitz maps t ↦ ∣ t − Y i ∣ t\mapsto|t-Y_i| t ↦ ∣ t − Y i ∣ [46 ] ) give
E S sup ∥ v ∥ 2 ≤ R ( L P ( v ) − L ^ S ( v ) ) ≤ 2 R n E S , σ ∥ ∑ i = 1 n σ i ϕ ( X i ) ∥ 2 . \mathbb{E}_S\sup_{\|v\|_2\le R}\left(L_P(v)-\widehat{L}_S(v)\right)\le\frac{2R}{n}\mathbb{E}_{S,\sigma}\left\|\sum_{i=1}^{n}\sigma_i\phi(X_i)\right\|_2. E S ∥ v ∥ 2 ≤ R sup ( L P ( v ) − L S ( v ) ) ≤ n 2 R E S , σ i = 1 ∑ n σ i ϕ ( X i ) 2 . By Jensen’s inequality, and since the cross terms vanish in expectation, the right-hand side is at most 2 R n ( ∑ i = 1 n E ∥ ϕ ( X i ) ∥ 2 2 ) 1 / 2 ≤ 2 R D / n \frac{2R}{n}\left(\sum_{i=1}^{n}\mathbb{E}\|\phi(X_i)\|_2^2\right)^{1/2}\le2R\sqrt{D/n} n 2 R ( ∑ i = 1 n E ∥ ϕ ( X i ) ∥ 2 2 ) 1/2 ≤ 2 R D / n □ \square □
Gaussian Marginals
For a probability measure μ \mu μ R d \mathbb{R}^{d} R d r ∈ [ 1 , ∞ ) r\in[1,\infty) r ∈ [ 1 , ∞ ) ∥ f ∥ L r ( μ ) : = ( ∫ ∣ f ( x ) ∣ r d μ ( x ) ) 1 / r \|f\|_{L^r(\mu)}:=\left(\int|f(x)|^r\,d\mu(x)\right)^{1/r} ∥ f ∥ L r ( μ ) := ( ∫ ∣ f ( x ) ∣ r d μ ( x ) ) 1/ r ∥ f ∥ L ∞ ( μ ) : = inf { M ≥ 0 : μ ( { x : ∣ f ( x ) ∣ > M } ) = 0 } \|f\|_{L^\infty(\mu)}:=\inf\{M\ge0:\mu(\{x:|f(x)|>M\})=0\} ∥ f ∥ L ∞ ( μ ) := inf { M ≥ 0 : μ ({ x : ∣ f ( x ) ∣ > M }) = 0 } L 2 ( μ ) L^2(\mu) L 2 ( μ ) ⟨ f , g ⟩ L 2 ( μ ) : = ∫ f ( x ) g ( x ) d μ ( x ) \langle f,g\rangle_{L^2(\mu)}:=\int f(x)g(x)\,d\mu(x) ⟨ f , g ⟩ L 2 ( μ ) := ∫ f ( x ) g ( x ) d μ ( x )
Lemma B.8 (Hermite basis; O’Donnell, [44 ] ). Let { h m } m ≥ 0 \{h_m\}_{m\ge0} { h m } m ≥ 0
e t x − t 2 / 2 = ∑ m = 0 ∞ h m ( x ) t m m ! . e^{tx-t^2/2}=\sum_{m=0}^{\infty}h_m(x)\frac{t^m}{\sqrt{m!}}. e t x − t 2 /2 = m = 0 ∑ ∞ h m ( x ) m ! t m . For each multi-index κ = ( κ 1 , … , κ d ) ∈ N 0 d \kappa=(\kappa_1,\ldots,\kappa_d)\in\mathbb{N}_0^d κ = ( κ 1 , … , κ d ) ∈ N 0 d h κ ( x ) = ∏ j = 1 d h κ j ( x j ) h_\kappa(x)=\prod_{j=1}^{d}h_{\kappa_j}(x_j) h κ ( x ) = ∏ j = 1 d h κ j ( x j ) ∣ κ ∣ = ∑ j = 1 d κ j |\kappa|=\sum_{j=1}^{d}\kappa_j ∣ κ ∣ = ∑ j = 1 d κ j { h κ } κ ∈ N 0 d \{h_\kappa\}_{\kappa\in\mathbb{N}_0^d} { h κ } κ ∈ N 0 d L 2 ( N ( 0 , I d ) ) L^2(\mathcal{N}(0,I_d)) L 2 ( N ( 0 , I d )) { h κ : ∣ κ ∣ ≤ p } \{h_\kappa:|\kappa|\le p\} { h κ : ∣ κ ∣ ≤ p } p p p ( d + p p ) \binom{d+p}{p} ( p d + p )
Lemma B.9 (Mehler’s formula; Andrews et al., [3 ] ). Let { h κ } κ ∈ N 0 d \{h_\kappa\}_{\kappa\in\mathbb{N}_0^d} { h κ } κ ∈ N 0 d L 2 ( N ( 0 , I d ) ) L^2(\mathcal{N}(0,I_d)) L 2 ( N ( 0 , I d )) κ ∈ N 0 d \kappa\in\mathbb{N}_0^d κ ∈ N 0 d ∣ κ ∣ = ∑ j = 1 d κ j |\kappa|=\sum_{j=1}^{d}\kappa_j ∣ κ ∣ = ∑ j = 1 d κ j x , y ∈ R d x,y\in\mathbb{R}^d x , y ∈ R d ρ ∈ ( − 1 , 1 ) \rho\in(-1,1) ρ ∈ ( − 1 , 1 )
∑ κ ∈ N 0 d ρ ∣ κ ∣ h κ ( x ) h κ ( y ) = 1 ( 1 − ρ 2 ) d / 2 exp ( 2 ρ ⟨ x , y ⟩ − ρ 2 ( ∥ x ∥ 2 2 + ∥ y ∥ 2 2 ) 2 ( 1 − ρ 2 ) ) . \sum_{\kappa\in\mathbb{N}_0^d}\rho^{|\kappa|}h_\kappa(x)h_\kappa(y)=\frac{1}{(1-\rho^2)^{d/2}}\exp\left(\frac{2\rho\langle x,y\rangle-\rho^2\left(\|x\|_2^2+\|y\|_2^2\right)}{2(1-\rho^2)}\right). κ ∈ N 0 d ∑ ρ ∣ κ ∣ h κ ( x ) h κ ( y ) = ( 1 − ρ 2 ) d /2 1 exp ( 2 ( 1 − ρ 2 ) 2 ρ ⟨ x , y ⟩ − ρ 2 ( ∥ x ∥ 2 2 + ∥ y ∥ 2 2 ) ) . Lemma B.10 (Unit-norm polynomial approximation of halfspaces under Gaussian measure). Let d ≥ 1 d\ge1 d ≥ 1 { h κ } κ ∈ N 0 d \{h_\kappa\}_{\kappa\in\mathbb{N}_0^d} { h κ } κ ∈ N 0 d L 2 ( N ( 0 , I d ) ) L^2(\mathcal{N}(0,I_d)) L 2 ( N ( 0 , I d )) C > 0 C>0 C > 0 α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) c : R d → { − 1 , 1 } c:\mathbb{R}^d\to\{-1,1\} c : R d → { − 1 , 1 } q ( x ) = ∑ ∣ κ ∣ ≤ p w κ h κ ( x ) q(x)=\sum_{|\kappa|\le p}w_\kappa h_\kappa(x) q ( x ) = ∑ ∣ κ ∣ ≤ p w κ h κ ( x ) p ≤ C α − 2 p\le C\alpha^{-2} p ≤ C α − 2 ∥ w ∥ 2 ≤ 1 \|w\|_2\le1 ∥ w ∥ 2 ≤ 1 ∥ c − q ∥ L 1 ( N ( 0 , I d ) ) ≤ α \|c-q\|_{L^1(\mathcal{N}(0,I_d))}\le\alpha ∥ c − q ∥ L 1 ( N ( 0 , I d )) ≤ α
Proof. Write c ( x ) = f θ ( ⟨ u , x ⟩ ) c(x)=f_\theta(\langle u,x\rangle) c ( x ) = f θ (⟨ u , x ⟩) f θ ( z ) = sgn ( z − θ ) f_\theta(z)=\operatorname{sgn}(z-\theta) f θ ( z ) = sgn ( z − θ ) ∥ u ∥ 2 = 1 \|u\|_2=1 ∥ u ∥ 2 = 1 B : R → [ 0 , ∞ ) B:\mathbb{R}\to[0,\infty) B : R → [ 0 , ∞ ) [11 ] , and define B λ ( t ) = λ B ( λ t ) B_\lambda(t)=\lambda B(\lambda t) B λ ( t ) = λ B ( λ t )
By Pesenti et al. [45 ] , for every θ ∈ R \theta\in\mathbb{R} θ ∈ R λ > 0 \lambda>0 λ > 0 p ≤ C α − 2 p\le C\alpha^{-2} p ≤ C α − 2 C C C θ \theta θ g θ = B λ ∗ f θ g_\theta=B_\lambda*f_\theta g θ = B λ ∗ f θ
∥ f θ − Π p g θ ∥ L 1 ( N ( 0 , 1 ) ) ≤ α , \|f_\theta-\Pi_p g_\theta\|_{L^1(\mathcal{N}(0,1))}\le\alpha, ∥ f θ − Π p g θ ∥ L 1 ( N ( 0 , 1 )) ≤ α , where Π p ( ⋅ ) \Pi_p(\cdot) Π p ( ⋅ ) L 2 ( N ( 0 , 1 ) ) L^2(\mathcal{N}(0,1)) L 2 ( N ( 0 , 1 )) p p p
Since ∫ R B λ ( t ) d t = 1 \int_{\mathbb{R}}B_\lambda(t)\,\mathrm{d}t=1 ∫ R B λ ( t ) d t = 1 [11 ] ), we have
∣ g θ ( z ) ∣ ≤ ∫ R B λ ( t ) ∣ f θ ( z − t ) ∣ d t = 1 ∀ z . |g_\theta(z)|\le\int_{\mathbb{R}}B_\lambda(t)|f_\theta(z-t)|\,\mathrm{d}t=1\quad\forall z. ∣ g θ ( z ) ∣ ≤ ∫ R B λ ( t ) ∣ f θ ( z − t ) ∣ d t = 1 ∀ z . Hence ∥ Π p g θ ∥ L 2 ( N ( 0 , 1 ) ) ≤ ∥ g θ ∥ L 2 ( N ( 0 , 1 ) ) ≤ 1 \|\Pi_p g_\theta\|_{L^2(\mathcal{N}(0,1))}\le\|g_\theta\|_{L^2(\mathcal{N}(0,1))}\le1 ∥ Π p g θ ∥ L 2 ( N ( 0 , 1 )) ≤ ∥ g θ ∥ L 2 ( N ( 0 , 1 )) ≤ 1
Set q ( x ) = Π p g θ ( ⟨ u , x ⟩ ) q(x)=\Pi_p g_\theta(\langle u,x\rangle) q ( x ) = Π p g θ (⟨ u , x ⟩) p p p q = ∑ ∣ κ ∣ ≤ p w κ h κ q=\sum_{|\kappa|\le p}w_\kappa h_\kappa q = ∑ ∣ κ ∣ ≤ p w κ h κ w w w Lemma B.8 ). Since ∥ u ∥ 2 = 1 \|u\|_2=1 ∥ u ∥ 2 = 1 ⟨ u , X ⟩ ∼ N ( 0 , 1 ) \langle u,X\rangle\sim\mathcal{N}(0,1) ⟨ u , X ⟩ ∼ N ( 0 , 1 ) X ∼ N ( 0 , I d ) X\sim\mathcal{N}(0,I_d) X ∼ N ( 0 , I d ) L 2 L^2 L 2 q q q N ( 0 , I d ) \mathcal{N}(0,I_d) N ( 0 , I d ) Π p g θ \Pi_p g_\theta Π p g θ N ( 0 , 1 ) \mathcal{N}(0,1) N ( 0 , 1 ) ∥ w ∥ 2 = ∥ q ∥ L 2 ( N ( 0 , I d ) ) = ∥ Π p g θ ∥ L 2 ( N ( 0 , 1 ) ) ≤ 1 \|w\|_2=\|q\|_{L^2(\mathcal{N}(0,I_d))}=\|\Pi_p g_\theta\|_{L^2(\mathcal{N}(0,1))}\le1 ∥ w ∥ 2 = ∥ q ∥ L 2 ( N ( 0 , I d )) = ∥ Π p g θ ∥ L 2 ( N ( 0 , 1 )) ≤ 1
Fact B.11 (Euclidean covers; Diakonikolas et al. [15 ] ). For every k ≥ 1 k\ge1 k ≥ 1 γ ∈ ( 0 , 1 ) \gamma\in(0,1) γ ∈ ( 0 , 1 ) R k \mathbb{R}^k R k γ \gamma γ ℓ 2 \ell_2 ℓ 2 ( C / γ ) k (C/\gamma)^k ( C / γ ) k C > 0 C>0 C > 0
Fact B.12 (Gaussian halfspace discretization; Diakonikolas et al. [15 ] ). Let X ∼ N ( 0 , I d ) X\sim\mathcal{N}(0,I_d) X ∼ N ( 0 , I d ) u , v ∈ R d u,v\in\mathbb{R}^d u , v ∈ R d t 1 , t 2 ∈ R t_1,t_2\in\mathbb{R} t 1 , t 2 ∈ R E [ ∣ h u , t 1 ( X ) − h v , t 1 ( X ) ∣ ] = O ( ∥ u − v ∥ 2 ) \mathbb{E}[|h_{u,t_1}(X)-h_{v,t_1}(X)|]=O(\|u-v\|_2) E [ ∣ h u , t 1 ( X ) − h v , t 1 ( X ) ∣ ] = O ( ∥ u − v ∥ 2 ) E [ ∣ h u , t 1 ( X ) − h u , t 2 ( X ) ∣ ] = O ( ∣ t 1 − t 2 ∣ ) \mathbb{E}[|h_{u,t_1}(X)-h_{u,t_2}(X)|]=O(|t_1-t_2|) E [ ∣ h u , t 1 ( X ) − h u , t 2 ( X ) ∣ ] = O ( ∣ t 1 − t 2 ∣ ) ∣ t ∣ ≥ C log ( 1 / γ ) |t|\ge C\sqrt{\log(1/\gamma)} ∣ t ∣ ≥ C log ( 1/ γ ) E [ ∣ h v , t ( X ) − sign ( t ) ∣ ] = O ( γ ) \mathbb{E}[|h_{v,t}(X)-\operatorname{sign}(t)|]=O(\gamma) E [ ∣ h v , t ( X ) − sign ( t ) ∣ ] = O ( γ )
Log-Concave Marginals
A probability measure is log-concave if its density is of the form e − V e^{-V} e − V V V V
Fact B.13 (Bound on the density of log-concave distributions; Kalai et al. [29 ] ). Let ν \nu ν R \mathbb{R} R g g g g ( x ) ≤ e ⋅ e − ∣ x ∣ / 16 g(x)\le e\cdot e^{-|x|/16} g ( x ) ≤ e ⋅ e − ∣ x ∣/16 x ∈ R x\in\mathbb{R} x ∈ R
The next two results concern weighted polynomial approximation on R \mathbb{R} R Lemma D.3 . Let ∥ ⋅ ∥ L k \|\cdot\|_{L^k} ∥ ⋅ ∥ L k L k L^k L k W ( x ) : = e − ∣ x ∣ W(x):=e^{-|x|} W ( x ) := e − ∣ x ∣
Lemma B.14 (Weighted Nikolskii inequality; Lubinsky [40 ] ). There is a universal constant C C C p ≥ 1 p\ge1 p ≥ 1 q q q p p p
∥ q W ∥ L ∞ ≤ C log ( p + 1 ) ∥ q W ∥ L 1 . \|qW\|_{L^\infty}\le C\log(p+1)\|qW\|_{L^1}. ∥ q W ∥ L ∞ ≤ C log ( p + 1 ) ∥ q W ∥ L 1 . Lemma B.15 (Weighted Jackson estimate; Freud et al. [24 ] , see also Lubinsky [40 ] ). Let f θ ( z ) = sign ( z − θ ) f_\theta(z)=\operatorname{sign}(z-\theta) f θ ( z ) = sign ( z − θ ) C > 0 C>0 C > 0 θ ∈ R \theta\in\mathbb{R} θ ∈ R p ≥ 2 p\ge2 p ≥ 2 q q q p p p
∥ ( q − f θ ) W ∥ L 1 ≤ C log ( p + 1 ) . \|(q-f_\theta)W\|_{L^1}\le\frac{C}{\log(p+1)}. ∥ ( q − f θ ) W ∥ L 1 ≤ log ( p + 1 ) C . Proof. Set H θ = f θ W H_\theta=f_\theta W H θ = f θ W [24 ] , taking δ = 1 / 2 \delta=1/2 δ = 1/2 q q q p p p
∥ ( q − f θ ) W ∥ L 1 ≤ C [ sup ∣ h ∣ ≤ 1 / log p ∥ H θ ( ⋅ + h ) − H θ ∥ L 1 + ∥ H θ ∥ L 1 log p + ∫ ∣ z ∣ ≥ p ∣ H θ ( z ) ∣ d z ] . \lVert(q-f_\theta)W\rVert_{L^1}\le C\left[\sup_{|h|\le1/\log p}\lVert H_\theta(\cdot+h)-H_\theta\rVert_{L^1}+\frac{\lVert H_\theta\rVert_{L^1}}{\log p}+\int_{|z|\ge\sqrt{p}}|H_\theta(z)|\,dz\right]. ∥( q − f θ ) W ∥ L 1 ≤ C [ ∣ h ∣ ≤ 1/ l o g p sup ∥ H θ ( ⋅ + h ) − H θ ∥ L 1 + log p ∥ H θ ∥ L 1 + ∫ ∣ z ∣ ≥ p ∣ H θ ( z ) ∣ d z ] . To bound the first term on the right hand side, first observe that ∥ W ′ ∥ L 1 = 2 \lVert W'\rVert_{L^1}=2 ∥ W ′ ∥ L 1 = 2 ∥ W ( ⋅ + h ) − W ∥ L 1 ≤ ∣ h ∣ ∥ W ′ ∥ L 1 = 2 ∣ h ∣ \lVert W(\cdot+h)-W\rVert_{L^1}\le|h|\lVert W'\rVert_{L^1}=2|h| ∥ W ( ⋅ + h ) − W ∥ L 1 ≤ ∣ h ∣ ∥ W ′ ∥ L 1 = 2∣ h ∣ f θ ( z + h ) f_\theta(z+h) f θ ( z + h ) f θ ( z ) f_\theta(z) f θ ( z ) z z z θ − h \theta-h θ − h θ \theta θ 2 2 2 W ≤ 1 W\le1 W ≤ 1 ∥ ( f θ ( ⋅ + h ) − f θ ) W ∥ L 1 ≤ 2 ∣ h ∣ \lVert(f_\theta(\cdot+h)-f_\theta)W\rVert_{L^1}\le2|h| ∥( f θ ( ⋅ + h ) − f θ ) W ∥ L 1 ≤ 2∣ h ∣ f θ ( z + h ) W ( z ) f_\theta(z+h)W(z) f θ ( z + h ) W ( z )
∥ H θ ( ⋅ + h ) − H θ ∥ L 1 ≤ ∥ W ( ⋅ + h ) − W ∥ L 1 + ∥ ( f θ ( ⋅ + h ) − f θ ) W ∥ L 1 ≤ 4 ∣ h ∣ . \lVert H_\theta(\cdot+h)-H_\theta\rVert_{L^1}\le\lVert W(\cdot+h)-W\rVert_{L^1}+\lVert(f_\theta(\cdot+h)-f_\theta)W\rVert_{L^1}\le4|h|. ∥ H θ ( ⋅ + h ) − H θ ∥ L 1 ≤ ∥ W ( ⋅ + h ) − W ∥ L 1 + ∥( f θ ( ⋅ + h ) − f θ ) W ∥ L 1 ≤ 4∣ h ∣. For the remaining terms, ∣ H θ ∣ = W |H_\theta|=W ∣ H θ ∣ = W ∥ H θ ∥ L 1 = 2 \lVert H_\theta\rVert_{L^1}=2 ∥ H θ ∥ L 1 = 2 ∫ ∣ z ∣ ≥ p ∣ H θ ( z ) ∣ d z = 2 e − p \int_{|z|\ge\sqrt{p}}|H_\theta(z)|\,dz=2e^{-\sqrt{p}} ∫ ∣ z ∣ ≥ p ∣ H θ ( z ) ∣ d z = 2 e − p ∥ ( q − f θ ) W ∥ L 1 ≤ C ( 6 / log p + 2 e − p ) ≤ C / log ( p + 1 ) \lVert(q-f_\theta)W\rVert_{L^1}\le C(6/\log p+2e^{-\sqrt{p}})\le C/\log(p+1) ∥( q − f θ ) W ∥ L 1 ≤ C ( 6/ log p + 2 e − p ) ≤ C / log ( p + 1 ) p p p θ \theta θ
Proofs for Improper Learning with Gaussian Marginals
In this section, we prove Theorem 2.1 . We first establish the privacy guarantee of Algorithm 1.
Proposition C.1. Algorithm 1 satisfies ( ε D P , δ D P ) (\varepsilon_{\mathrm{DP}},\delta_{\mathrm{DP}}) ( ε DP , δ DP )
Proof. The feature map, the partition into blocks, and the algorithm parameters are data-independent. For each example ( x , y ) (x,y) ( x , y ) v ↦ ∣ ⟨ v , ψ ˉ p , T ( x ) ⟩ − y ∣ v\mapsto|\langle v,\bar{\psi}_{p,T}(x)\rangle-y| v ↦ ∣ ⟨ v , ψ ˉ p , T ( x )⟩ − y ∣ T T T ∥ ψ ˉ p , T ( x ) ∥ 2 ≤ T \lVert\bar{\psi}_{p,T}(x)\rVert_2\le T ∥ ψ ˉ p , T ( x ) ∥ 2 ≤ T Lemma B.4 implies that each regression run is ( ε D P , δ D P ) (\varepsilon_{\mathrm{DP}},\delta_{\mathrm{DP}}) ( ε DP , δ DP )
All blocks are disjoint, and running the DP gradient descent algorithm with the same privacy parameters independently on each block guarantees ( ε D P , δ D P ) (\varepsilon_{\mathrm{DP}},\delta_{\mathrm{DP}}) ( ε DP , δ DP ) Lemma B.4 and parallel composition. Our output space being defined for the remainder of the computations via v ^ j \hat{v}_j v ^ j Lemma B.3 ). Finally, applying the exponential mechanism (Lemma B.5 ) on a disjoint validation block of data satisfies ε D P \varepsilon_{\mathrm{DP}} ε DP ( ε D P , δ D P ) (\varepsilon_{\mathrm{DP}},\delta_{\mathrm{DP}}) ( ε DP , δ DP )
Next, we establish a tail bound for the Hermite feature norm, which controls the bias introduced by clipping.
Lemma C.2 (Hermite feature norm tail bound). Let d , p ≥ 1 d,p\ge1 d , p ≥ 1 D p = ( d + p p ) D_p=\binom{d+p}{p} D p = ( p d + p ) h 1 , … , h D p h_1,\ldots,h_{D_p} h 1 , … , h D p p p p L 2 ( N ( 0 , I d ) ) L^2(\mathcal{N}(0,I_d)) L 2 ( N ( 0 , I d )) ψ p ( x ) = ( h 1 ( x ) , … , h D p ( x ) ) \psi_p(x)=(h_1(x),\ldots,h_{D_p}(x)) ψ p ( x ) = ( h 1 ( x ) , … , h D p ( x )) α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) d ≥ 2 p 2 / α d\ge2p^2/\alpha d ≥ 2 p 2 / α X ∼ N ( 0 , I d ) X\sim\mathcal{N}(0,I_d) X ∼ N ( 0 , I d )
P [ ∥ ψ p ( X ) ∥ 2 > 2 D p ] ≤ α . \mathbb{P}\left[\lVert\psi_p(X)\rVert_2>2\sqrt{D_p}\right]\le\alpha. P [ ∥ ψ p ( X ) ∥ 2 > 2 D p ] ≤ α . Proof. Write V = ∥ ψ p ( X ) ∥ 2 2 / D p V=\lVert\psi_p(X)\rVert_2^2/D_p V = ∥ ψ p ( X ) ∥ 2 2 / D p E [ V ] = 1 \mathbb{E}[V]=1 E [ V ] = 1
Var ( V ) ≤ e 2 p 2 / d − 1. (14) \operatorname{Var}(V)\le e^{2p^2/d}-1. \tag*{(14)} Var ( V ) ≤ e 2 p 2 / d − 1. (14) Assuming this claim, Chebyshev’s inequality gives
P [ ∥ ψ p ( X ) ∥ 2 > 2 D p ] = P [ V − 1 > 3 ] ≤ E [ ( V − 1 ) 2 ] 9 ≤ e 2 p 2 / d − 1 9 ≤ e α − 1 9 ≤ ( e − 1 ) α 9 ≤ α . \mathbb{P}\left[\lVert\psi_p(X)\rVert_2 > 2\sqrt{D_p}\right] = \mathbb{P}[V-1>3]
\le\frac{\mathbb{E}\left[(V-1)^2\right]}{9}
\le\frac{e^{2p^2/d}-1}{9}
\le\frac{e^\alpha-1}{9}
\le\frac{(e-1)\alpha}{9}
\le\alpha. P [ ∥ ψ p ( X ) ∥ 2 > 2 D p ] = P [ V − 1 > 3 ] ≤ 9 E [ ( V − 1 ) 2 ] ≤ 9 e 2 p 2 / d − 1 ≤ 9 e α − 1 ≤ 9 ( e − 1 ) α ≤ α . where d ≥ 2 p 2 / α d \ge2p^2/\alpha d ≥ 2 p 2 / α e x e^x e x α ∈ [ 0 , 1 ] \alpha\in[0,1] α ∈ [ 0 , 1 ]
It remains to establish (14) . For every integer m ≥ 0 m \ge0 m ≥ 0 K m ( x ) = ∑ ∣ κ ∣ ≤ m h κ ( x ) 2 K_m(x) = \sum_{|\kappa|\le m} h_\kappa(x)^2 K m ( x ) = ∑ ∣ κ ∣ ≤ m h κ ( x ) 2 K p ( X ) = D p V K_p(X) = D_pV K p ( X ) = D p V K p ( X ) K_p(X) K p ( X ) F ( z , x ) = ∑ m = 0 ∞ K m ( x ) z m F(z,x) = \sum_{m=0}^{\infty} K_m(x)z^m F ( z , x ) = ∑ m = 0 ∞ K m ( x ) z m Lemma B.9 ) gives
F ( z , x ) = 1 1 − z ∑ κ ∈ N 0 d z ∣ κ ∣ h κ ( x ) 2 = exp ( z 1 + z ∥ x ∥ 2 2 ) ( 1 − z ) ( 1 − z 2 ) d / 2 . F(z,x)=\frac{1}{1-z}\sum_{\kappa\in\mathbb{N}_0^d}z^{|\kappa|}h_\kappa(x)^2
=\frac{\exp\left(\frac{z}{1+z}\lVert x\rVert_2^2\right)}{(1-z)(1-z^2)^{d/2}}. F ( z , x ) = 1 − z 1 κ ∈ N 0 d ∑ z ∣ κ ∣ h κ ( x ) 2 = ( 1 − z ) ( 1 − z 2 ) d /2 exp ( 1 + z z ∥ x ∥ 2 2 ) . Since ∥ X ∥ 2 2 ∼ χ d 2 \lVert X\rVert_2^2\sim\chi_d^2 ∥ X ∥ 2 2 ∼ χ d 2 z , w > 0 z,w>0 z , w > 0
E [ F ( z , X ) F ( w , X ) ] = 1 ( 1 − z ) d + 1 ( 1 − w ) d + 1 ( 1 − 4 z w ( 1 − z ) ( 1 − w ) ) − d / 2 . \mathbb{E}[F(z,X)F(w,X)]
=\frac{1}{(1-z)^{d+1}(1-w)^{d+1}}
\left(1-\frac{4zw}{(1-z)(1-w)}\right)^{-d/2}. E [ F ( z , X ) F ( w , X )] = ( 1 − z ) d + 1 ( 1 − w ) d + 1 1 ( 1 − ( 1 − z ) ( 1 − w ) 4 z w ) − d /2 . Expanding the last factor using the binomial series and comparing coefficients of z p w p z^pw^p z p w p
E [ K p ( X ) 2 ] = ∑ k = 0 p 4 k ( d / 2 ) k k ! ( d + p p − k ) 2 . \mathbb{E}[K_p(X)^2]
=\sum_{k=0}^{p}\frac{4^k(d/2)_k}{k!}\binom{d+p}{p-k}^2. E [ K p ( X ) 2 ] = k = 0 ∑ p k ! 4 k ( d /2 ) k ( p − k d + p ) 2 . where ( a ) k = ∏ j = 0 k − 1 ( a + j ) (a)_k=\prod_{j=0}^{k-1}(a+j) ( a ) k = ∏ j = 0 k − 1 ( a + j ) ( a ) 0 = 1 (a)_0=1 ( a ) 0 = 1
E [ V 2 ] = ∑ k = 0 p 4 k ( d / 2 ) k k ! ( ( d + p p − k ) D p ) 2 ≤ ∑ k = 0 p ( 2 p 2 / d ) k k ! ≤ e 2 p 2 / d . \mathbb{E}[V^2]
=\sum_{k=0}^{p}\frac{4^k(d/2)_k}{k!}\left(\frac{\binom{d+p}{p-k}}{D_p}\right)^2
\le\sum_{k=0}^{p}\frac{(2p^2/d)^k}{k!}
\le e^{2p^2/d}. E [ V 2 ] = k = 0 ∑ p k ! 4 k ( d /2 ) k ( D p ( p − k d + p ) ) 2 ≤ k = 0 ∑ p k ! ( 2 p 2 / d ) k ≤ e 2 p 2 / d . where the first inequality follows from ( d + p p − k ) / D p = ∏ j = 0 k − 1 p − j d + 1 + j \binom{d+p}{p-k}/D_p=\prod_{j=0}^{k-1}\frac{p-j}{d+1+j} ( p − k d + p ) / D p = ∏ j = 0 k − 1 d + 1 + j p − j p − j ≤ p p-j\le p p − j ≤ p ( d / 2 + j ) / ( d + 1 + j ) 2 ≤ 1 / ( 2 d ) (d/2+j)/(d+1+j)^2\le1/(2d) ( d /2 + j ) / ( d + 1 + j ) 2 ≤ 1/ ( 2 d ) E [ V ] = 1 \mathbb{E}[V]=1 E [ V ] = 1 (14) follows. □
We now turn to the proof of Theorem 2.1 . We use Algorithm 1 with the degree-p p p ψ p \psi_p ψ p c ∈ ( 0 , 1 / 4 ] c\in(0,1/4] c ∈ ( 0 , 1/4 ] C C C c c c
p = ⌈ C α − 2 ⌉ , D p = ( d + p p ) , T = 2 D p , k = ⌈ log 2 2 β ⌉ , M = ⌈ C α ⌉ . (15) p=\left\lceil C\alpha^{-2}\right\rceil,\qquad
D_p=\binom{d+p}{p},\qquad
T=2\sqrt{D_p},\qquad
k=\left\lceil\log_2\frac{2}{\beta}\right\rceil,\qquad
M=\left\lceil\frac{C}{\alpha}\right\rceil. \tag*{(15)} p = ⌈ C α − 2 ⌉ , D p = ( p d + p ) , T = 2 D p , k = ⌈ log 2 β 2 ⌉ , M = ⌈ α C ⌉ . (15) Since p ≤ ( C + 1 ) α − 2 p \le(C+1)\alpha^{-2} p ≤ ( C + 1 ) α − 2 C d i m ≥ 2 ( C + 1 ) 2 / c C_{\mathrm{dim}} \ge2(C+1)^2/c C dim ≥ 2 ( C + 1 ) 2 / c d ≥ C d i m α − 5 d \ge C_{\mathrm{dim}}\alpha^{-5} d ≥ C dim α − 5 d ≥ 2 p 2 / ( c α ) d \ge2p^2/(c\alpha) d ≥ 2 p 2 / ( c α ) Lemma C.2 applies at level c α c\alpha c α n 0 ≥ 2 n_0 \ge2 n 0 ≥ 2
C ( T D p log ( 1 / δ D P ) ε D P n 0 + D p n 0 ) ≤ c α , (16) C\left(\frac{T\sqrt{D_p\log(1/\delta_{\mathrm{DP}})}}{\varepsilon_{\mathrm{DP}}n_0}+\sqrt{\frac{D_p}{n_0}}\right)\le c\alpha, \tag*{(16)} C ( ε DP n 0 T D p log ( 1/ δ DP ) + n 0 D p ) ≤ c α , (16) and set
m = ⌈ C ( 1 α 2 + 1 ε D P α ) log k M β ⌉ , n = k n 0 + m . (17) m=\left\lceil C\left(\frac{1}{\alpha^2}+\frac{1}{\varepsilon_{\mathrm{DP}}\alpha}\right)\log\frac{kM}{\beta}\right\rceil,\qquad n=kn_0+m. \tag*{(17)} m = ⌈ C ( α 2 1 + ε DP α 1 ) log β k M ⌉ , n = k n 0 + m . (17) Proof of Theorem 2.1 . Proposition C.1 establishes privacy. It remains to establish the accuracy, sample complexity, and running time bounds. Write μ = N ( 0 , I d ) \mu=\mathcal{N}(0,I_d) μ = N ( 0 , I d ) L P ( v ) = E ( X , Y ) ∼ P [ ∣ ⟨ v , ψ ˉ p , T ( X ) ⟩ − Y ∣ ] L_P(v)=\mathbb{E}_{(X,Y)\sim P}\left[\left|\langle v,\bar{\psi}_{p,T}(X)\rangle-Y\right|\right] L P ( v ) = E ( X , Y ) ∼ P [ ⟨ v , ψ ˉ p , T ( X )⟩ − Y ] L ⋆ : = min ∥ v ∥ 2 ≤ 1 L P ( v ) L^\star:=\min_{\lVert v\rVert_2\le1}L_P(v) L ⋆ := min ∥ v ∥ 2 ≤ 1 L P ( v ) S j S_j S j L ^ S j ( v ) : = n 0 − 1 ∑ ( X i , Y i ) ∈ S j ∣ ⟨ v , ψ ˉ p , T ( X i ) ⟩ − Y i ∣ \widehat{L}_{S_j}(v):=n_0^{-1}\sum_{(X_i,Y_i)\in S_j}\left|\langle v,\bar{\psi}_{p,T}(X_i)\rangle-Y_i\right| L S j ( v ) := n 0 − 1 ∑ ( X i , Y i ) ∈ S j ⟨ v , ψ ˉ p , T ( X i )⟩ − Y i
We first bound the expected excess regression loss of a single training run. Orthonormality and clipping give E μ ∥ ψ ˉ p , T ( X ) ∥ 2 2 ≤ D p \mathbb{E}_{\mu}\lVert\bar{\psi}_{p,T}(X)\rVert_2^2\le D_p E μ ∥ ψ ˉ p , T ( X ) ∥ 2 2 ≤ D p ∥ ψ ˉ p , T ( x ) ∥ 2 ≤ T \lVert\bar{\psi}_{p,T}(x)\rVert_2\le T ∥ ψ ˉ p , T ( x ) ∥ 2 ≤ T T T T R D p \mathbb{R}^{D_p} R D p v ⋆ ∈ argmin ∥ v ∥ 2 ≤ 1 L P ( v ) v^\star\in\operatorname*{argmin}_{\lVert v\rVert_2\le1}L_P(v) v ⋆ ∈ argmin ∥ v ∥ 2 ≤ 1 L P ( v ) L P ( v ⋆ ) = L ⋆ L_P(v^\star)=L^\star L P ( v ⋆ ) = L ⋆ L ^ S j ( v ^ j ) \widehat{L}_{S_j}(\widehat{v}_j) L S j ( v j ) L ^ S j ( v ⋆ ) \widehat{L}_{S_j}(v^\star) L S j ( v ⋆ )
L P ( v ^ j ) − L ⋆ = [ L P ( v ^ j ) − L ^ S j ( v ^ j ) ] + [ L ^ S j ( v ^ j ) − L ^ S j ( v ⋆ ) ] + [ L ^ S j ( v ⋆ ) − L ⋆ ] ≤ sup ∥ v ∥ 2 ≤ 1 ( L P ( v ) − L ^ S j ( v ) ) + [ L ^ S j ( v ^ j ) − min ∥ v ∥ 2 ≤ 1 L ^ S j ( v ) ] + [ L ^ S j ( v ⋆ ) − L ⋆ ] . (18) \begin{aligned}
L_P(\widehat{v}_j)-L^\star
&=\left[L_P(\widehat{v}_j)-\widehat{L}_{S_j}(\widehat{v}_j)\right]+\left[\widehat{L}_{S_j}(\widehat{v}_j)-\widehat{L}_{S_j}(v^\star)\right]+\left[\widehat{L}_{S_j}(v^\star)-L^\star\right]\\
&\le\sup_{\lVert v\rVert_2\le1}\left(L_P(v)-\widehat{L}_{S_j}(v)\right)+\left[\widehat{L}_{S_j}(\widehat{v}_j)-\min_{\lVert v\rVert_2\le1}\widehat{L}_{S_j}(v)\right]+\left[\widehat{L}_{S_j}(v^\star)-L^\star\right]. \tag*{(18)}
\end{aligned} L P ( v j ) − L ⋆ = [ L P ( v j ) − L S j ( v j ) ] + [ L S j ( v j ) − L S j ( v ⋆ ) ] + [ L S j ( v ⋆ ) − L ⋆ ] ≤ ∥ v ∥ 2 ≤ 1 sup ( L P ( v ) − L S j ( v ) ) + [ L S j ( v j ) − ∥ v ∥ 2 ≤ 1 min L S j ( v ) ] + [ L S j ( v ⋆ ) − L ⋆ ] . (18) The inequality uses ∥ v ^ j ∥ 2 ≤ 1 \lVert\widehat{v}_j\rVert_2\le1 ∥ v j ∥ 2 ≤ 1 v ⋆ v^\star v ⋆ S j S_j S j P P P E S j L ^ S j ( v ⋆ ) = L P ( v ⋆ ) = L ⋆ \mathbb{E}_{S_j}\widehat{L}_{S_j}(v^\star)=L_P(v^\star)=L^\star E S j L S j ( v ⋆ ) = L P ( v ⋆ ) = L ⋆ S j S_j S j Lemmas B.4 and B.7 therefore give
E [ L P ( v ^ j ) − L ⋆ ] ≤ E [ L ^ S j ( v ^ j ) − min ∥ v ∥ 2 ≤ 1 L ^ S j ( v ) ] + 2 D p n 0 ≤ c α , (19) \mathbb{E}[L_P(\widehat{v}_j)-L^\star]\le\mathbb{E}\left[\widehat{L}_{S_j}(\widehat{v}_j)-\min_{\lVert v\rVert_2\le1}\widehat{L}_{S_j}(v)\right]+2\sqrt{\frac{D_p}{n_0}}\le c\alpha, \tag*{(19)} E [ L P ( v j ) − L ⋆ ] ≤ E [ L S j ( v j ) − ∥ v ∥ 2 ≤ 1 min L S j ( v ) ] + 2 n 0 D p ≤ c α , (19) where the last inequality follows from the choice of n 0 n_0 n 0
We then use the standard confidence-amplification argument based on independent repetition; see, e.g., Shalev-Shwartz et al. [47 ] . By (16) and Markov’s inequality, P ( L P ( v ^ j ) − L ⋆ > 2 c α ) ≤ 1 / 2 \mathbb{P}(L_P(\widehat{v}_j)-L^\star>2c\alpha)\le1/2 P ( L P ( v j ) − L ⋆ > 2 c α ) ≤ 1/2 k k k P ( min j ∈ [ k ] L P ( v ^ j ) > L ⋆ + 2 c α ) ≤ 2 − k ≤ β / 2 \mathbb{P}(\min_{j\in[k]}L_P(\widehat{v}_j)>L^\star+2c\alpha)\le2^{-k}\le\beta/2 P ( min j ∈ [ k ] L P ( v j ) > L ⋆ + 2 c α ) ≤ 2 − k ≤ β /2 1 − β / 2 1-\beta/2 1 − β /2
min j ∈ [ k ] L P ( v ^ j ) ≤ L ⋆ + 2 c α . (20) \min_{j\in[k]}L_P(\widehat{v}_j)\le L^\star+2c\alpha. \tag*{(20)} j ∈ [ k ] min L P ( v j ) ≤ L ⋆ + 2 c α . (20) Next, we argue about the correctness of the choice of our threshold, which requires our grid over [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] Fact B.6 bounds the expected classification error under a uniform threshold τ ∼ Unif [ − 1 , 1 ] \tau\sim\operatorname{Unif}[-1,1] τ ∼ Unif [ − 1 , 1 ] τ \tau τ { t 1 , … , t M } \{t_1,\ldots,t_M\} { t 1 , … , t M } x x x ⟨ v ^ j , ψ ˉ p , T ( x ) ⟩ \langle\widehat{v}_j,\bar{\psi}_{p,T}(x)\rangle ⟨ v j , ψ ˉ p , T ( x )⟩ τ \tau τ τ \tau τ 1 / ( 2 M ) 1/(2M) 1/ ( 2 M ) v ^ j \widehat{v}_j v j M − 1 ∑ ℓ = 1 M err P ( h j , ℓ ) ≤ L P ( v ^ j ) / 2 + 1 / ( 2 M ) M^{-1}\sum_{\ell=1}^{M}\operatorname{err}_{P}(h_{j,\ell}) \le L_{P}(\widehat{v}_{j})/2 + 1/(2M) M − 1 ∑ ℓ = 1 M err P ( h j , ℓ ) ≤ L P ( v j ) /2 + 1/ ( 2 M ) min ℓ err P ( h j , ℓ ) ≤ M − 1 ∑ ℓ = 1 M err P ( h j , ℓ ) \min_{\ell}\operatorname{err}_{P}(h_{j,\ell}) \le M^{-1}\sum_{\ell=1}^{M}\operatorname{err}_{P}(h_{j,\ell}) min ℓ err P ( h j , ℓ ) ≤ M − 1 ∑ ℓ = 1 M err P ( h j , ℓ ) (20) and taking the minimum over all v ^ j \widehat{v}_{j} v j
min j , ℓ err P ( h j , ℓ ) ≤ 1 2 min j ∈ [ k ] L P ( v ^ j ) + 1 2 M ≤ 1 2 L ⋆ + 2 c α . (21) \min_{j,\ell}\operatorname{err}_{P}(h_{j,\ell}) \le\frac{1}{2}\min_{j\in[k]}L_{P}(\widehat{v}_{j})+\frac{1}{2M}\le\frac{1}{2}L^{\star}+2c\alpha. \tag*{(21)} j , ℓ min err P ( h j , ℓ ) ≤ 2 1 j ∈ [ k ] min L P ( v j ) + 2 M 1 ≤ 2 1 L ⋆ + 2 c α . (21) Let h h h S v a l S_{\mathrm{val}} S val Lemma B.5 , with K = k M K=kM K = k M η = β / 2 \eta=\beta/2 η = β /2 m m m (17) , gives err P ( h ) ≤ min j , ℓ err P ( h j , ℓ ) + c α \operatorname{err}_{P}(h)\le\min_{j,\ell}\operatorname{err}_{P}(h_{j,\ell})+c\alpha err P ( h ) ≤ min j , ℓ err P ( h j , ℓ ) + c α 1 − β / 2 1-\beta/2 1 − β /2 1 − β 1-\beta 1 − β
err P ( h ) ≤ L ⋆ / 2 + 3 c α , (22) \operatorname{err}_{P}(h)\le L^{\star}/2+3c\alpha, \tag*{(22)} err P ( h ) ≤ L ⋆ /2 + 3 c α , (22) which comes due to sampling and the noise due to the exponential mechanism.
We next compare L ⋆ L^{\star} L ⋆ c 0 ∈ C c_{0}\in\mathcal{C} c 0 ∈ C Lemma B.10 , and the choice of the degree p p p (15) , there is a polynomial q = ⟨ v q , ψ p ⟩ q=\langle v_{q},\psi_{p}\rangle q = ⟨ v q , ψ p ⟩ ∥ v q ∥ 2 ≤ 1 \lVert v_{q}\rVert_{2}\le1 ∥ v q ∥ 2 ≤ 1 ∥ q − c 0 ∥ L 1 ( μ ) ≤ c α \lVert q-c_{0}\rVert_{L^{1}(\mu)}\le c\alpha ∥ q − c 0 ∥ L 1 ( μ ) ≤ c α s ( x ) : = T / max { T , ∥ ψ p ( x ) ∥ 2 } s(x):=T/\max\{T,\lVert\psi_{p}(x)\rVert_{2}\} s ( x ) := T / max { T , ∥ ψ p ( x ) ∥ 2 } ψ ‾ p , T ( x ) = s ( x ) ψ p ( x ) \overline{\psi}_{p,T}(x)=s(x)\psi_{p}(x) ψ p , T ( x ) = s ( x ) ψ p ( x ) 0 < s ( x ) ≤ 1 0<s(x)\le1 0 < s ( x ) ≤ 1 ∣ y ∣ = 1 |y|=1 ∣ y ∣ = 1
∣ ⟨ v q , ψ ‾ p , T ( x ) ⟩ − y ∣ = ∣ s ( x ) q ( x ) − y ∣ ≤ s ( x ) ∣ q ( x ) − y ∣ + 1 − s ( x ) ≤ ∣ q ( x ) − c 0 ( x ) ∣ + ∣ c 0 ( x ) − y ∣ + 1 − s ( x ) . \begin{aligned}
\left|\langle v_q,\overline{\psi}_{p,T}(x)\rangle-y\right|&=|s(x)q(x)-y|\\
&\le s(x)|q(x)-y|+1-s(x)\\
&\le|q(x)-c_0(x)|+|c_0(x)-y|+1-s(x).
\end{aligned} ⟨ v q , ψ p , T ( x )⟩ − y = ∣ s ( x ) q ( x ) − y ∣ ≤ s ( x ) ∣ q ( x ) − y ∣ + 1 − s ( x ) ≤ ∣ q ( x ) − c 0 ( x ) ∣ + ∣ c 0 ( x ) − y ∣ + 1 − s ( x ) . Taking expectations over a population example ( X , Y ) ∼ P (X,Y)\sim P ( X , Y ) ∼ P
L P ( v q ) ≤ 2 err P ( c 0 ) + ∥ q − c 0 ∥ L 1 ( μ ) + E μ [ 1 − s ( X ) ] . (23) L_{P}(v_q)\le2\operatorname{err}_{P}(c_0)+\lVert q-c_0\rVert_{L^{1}(\mu)}+\mathbb{E}_{\mu}[1-s(X)]. \tag*{(23)} L P ( v q ) ≤ 2 err P ( c 0 ) + ∥ q − c 0 ∥ L 1 ( μ ) + E μ [ 1 − s ( X )] . (23) Moreover, since 0 ≤ 1 − s ( x ) ≤ 1 { ∥ ψ p ( x ) ∥ 2 > T } 0\le1-s(x)\le\mathbf{1}\{\lVert\psi_p(x)\rVert_{2}>T\} 0 ≤ 1 − s ( x ) ≤ 1 {∥ ψ p ( x ) ∥ 2 > T } Lemma C.2 , applied at level c α c\alpha c α E μ [ 1 − s ( X ) ] ≤ Pr μ ( ∥ ψ p ( X ) ∥ 2 > T ) ≤ c α \mathbb{E}_{\mu}[1-s(X)]\le\Pr_{\mu}(\lVert\psi_p(X)\rVert_{2}>T)\le c\alpha E μ [ 1 − s ( X )] ≤ Pr μ (∥ ψ p ( X ) ∥ 2 > T ) ≤ c α ∥ v q ∥ 2 ≤ 1 \lVert v_q\rVert_{2}\le1 ∥ v q ∥ 2 ≤ 1 L ⋆ ≤ L P ( v q ) ≤ 2 err P ( c 0 ) + 2 c α L^{\star}\le L_{P}(v_q)\le2\operatorname{err}_{P}(c_0)+2c\alpha L ⋆ ≤ L P ( v q ) ≤ 2 err P ( c 0 ) + 2 c α c 0 ∈ C c_0\in\mathcal{C} c 0 ∈ C
L ⋆ ≤ 2 OPT + 2 c α . (24) L^{\star}\le2\operatorname{OPT}+2c\alpha. \tag*{(24)} L ⋆ ≤ 2 OPT + 2 c α . (24) Combining (22) and (24) , we obtain the desired
err P ( h ) ≤ OPT + 4 c α ≤ OPT + α , \operatorname{err}_{P}(h)\le\operatorname{OPT}+4c\alpha\le\operatorname{OPT}+\alpha, err P ( h ) ≤ OPT + 4 c α ≤ OPT + α , where the last inequality uses c ≤ 1 / 4 c\le1/4 c ≤ 1/4
The choices in (16) and (17) satisfy
n 0 = O ~ ( D p α 2 + D p ϵ D P α ) , m = O ~ ( ( 1 α 2 + 1 ϵ D P α ) log 2 β ) , n_0=\widetilde{O}\left(\frac{D_p}{\alpha^2}+\frac{D_p}{\epsilon_{\mathrm{DP}}\alpha}\right),\qquad
m=\widetilde{O}\left(\left(\frac{1}{\alpha^2}+\frac{1}{\epsilon_{\mathrm{DP}}\alpha}\right)\log\frac{2}{\beta}\right), n 0 = O ( α 2 D p + ϵ DP α D p ) , m = O ( ( α 2 1 + ϵ DP α 1 ) log β 2 ) , where the bound on n 0 n_0 n 0 T D p = 2 D p T\sqrt{D_p}=2D_p T D p = 2 D p k = O ( log ( 2 / β ) ) k=O(\log(2/\beta)) k = O ( log ( 2/ β )) n = k n 0 + m n=kn_0+m n = k n 0 + m n n n
Finally, we analyse the running time. Computing the clipped Hermite features requires O ( p D p ) O(pD_p) O ( p D p ) O ( D p ) O(D_p) O ( D p ) Lemma B.4 gives a total cost of O ( k n 0 2 D p ) O(kn_0^2D_p) O ( k n 0 2 D p ) k k k k M kM k M O ( k M m D p ) O(kMmD_p) O ( k M m D p )
O ( n p D p + k n 0 2 D p + k M m D p ) = poly ( n ) , O\left(npD_p+kn_0^2D_p+kMmD_p\right)=\operatorname{poly}(n), O ( n p D p + k n 0 2 D p + k M m D p ) = poly ( n ) , since M ≤ p < D p ≤ n 0 M\le p<D_p\le n_0 M ≤ p < D p ≤ n 0 k n 0 + m = n kn_0+m=n k n 0 + m = n
Private Improper Agnostic Learning: Log-Concave Marginals
We extend the learner of § 2 to known, full-dimensional1 Lemma D.3 allows us to restrict regression to a coefficient ball of constant radius. We use the known marginal to choose a clipping threshold T T T
Theorem D.1 (DP improper agnostic learner for log-concave marginals). Let α , β ∈ ( 0 , 1 ) \alpha,\beta\in(0,1) α , β ∈ ( 0 , 1 ) ε D P , δ D P ∈ ( 0 , 1 / 2 ] \varepsilon_{\mathrm{DP}},\delta_{\mathrm{DP}} \in(0,1/2] ε DP , δ DP ∈ ( 0 , 1/2 ] p = ⌈ exp ( C / α ) ⌉ p = \lceil\exp(C/\alpha)\rceil p = ⌈ exp ( C / α )⌉ C > 0 C > 0 C > 0 D p = ( d + p p ) D_p = \binom{d+p}{p} D p = ( p d + p ) T T T (25) . Let P P P R d × { ± 1 } \mathbb{R}^d \times\{\pm1\} R d × { ± 1 } μ \mu μ § 10 .§ 1 is ( ε D P , δ D P ) (\varepsilon_{\mathrm{DP}},\delta_{\mathrm{DP}}) ( ε DP , δ DP )
n = O ~ ( D p α 2 + T D p ε D P α ) n = \widetilde{O}\left(\frac{D_p}{\alpha^2} + \frac{T\sqrt{D_p}}{\varepsilon_{\mathrm{DP}}\alpha}\right) n = O ( α 2 D p + ε DP α T D p ) i.i.d. samples from P P P h h h err P ( h ) ≤ OPT + α \operatorname{err}_P(h) \le\operatorname{OPT}+\alpha err P ( h ) ≤ OPT + α 1 − β 1-\beta 1 − β poly ( n ) \operatorname{poly}(n) poly ( n ) T T T poly ( D p ) \operatorname{poly}(D_p) poly ( D p )
As we show in Remark 3, T = D p / ( c α ) T = \sqrt{D_p/(c\alpha)} T = D p / ( c α ) O ~ ( D p / α 2 + D p / ( ε D P α 3 / 2 ) ) \widetilde{O}(D_p/\alpha^2 + D_p/(\varepsilon_{\mathrm{DP}}\alpha^{3/2})) O ( D p / α 2 + D p / ( ε DP α 3/2 ))
The Algorithm
Let μ \mu μ R d \mathbb{R}^d R d μ \mu μ μ \mu μ k k k M M M m m m (15) and (17) , and replace the block size n 0 n_0 n 0 (30) . The private optimization procedure, independent repetitions, thresholding, and private validation remain unchanged. We discuss the changes to Algorithm 1 in greater detail in the remainder of this section.
First, for the existence of a polynomial with good approximating guarantees, we increase the degree p = ⌈ exp ( C / α ) ⌉ p = \lceil\exp(C/\alpha)\rceil p = ⌈ exp ( C / α )⌉ C > 0 C > 0 C > 0 B 2 D p ( R 0 ) : = { v ∈ R D p : ∥ v ∥ 2 ≤ R 0 } B_2^{D_p}(R_0) := \{v \in\mathbb{R}^{D_p}: \|v\|_2 \le R_0\} B 2 D p ( R 0 ) := { v ∈ R D p : ∥ v ∥ 2 ≤ R 0 } R 0 R_0 R 0 Lemma D.3 .
Next, we recall how to construct an orthonormal basis for the polynomials of degree at most p p p L 2 ( μ ) L^2(\mu) L 2 ( μ ) m p ( x ) = ( x κ ) ∣ κ ∣ ≤ p m_p(x) = (x^\kappa)_{|\kappa|\le p} m p ( x ) = ( x κ ) ∣ κ ∣ ≤ p p p p [19 ] ), define the population Gram matrix G p = E μ [ m p ( X ) m p ( X ) T ] G_p = \mathbb{E}_{\mu}[m_p(X)m_p(X)^\mathsf{T}] G p = E μ [ m p ( X ) m p ( X ) T ] ψ p ( x ) = G p − 1 / 2 m p ( x ) \psi_p(x) = G_p^{-1/2}m_p(x) ψ p ( x ) = G p − 1/2 m p ( x ) G p G_p G p μ \mu μ 2 p 2p 2 p G p G_p G p G p − 1 / 2 G_p^{-1/2} G p − 1/2 ψ p \psi_p ψ p p p p E μ [ ψ p ( X ) ψ p ( X ) T ] = I D p \mathbb{E}_{\mu}[\psi_p(X)\psi_p(X)^\mathsf{T}] = I_{D_p} E μ [ ψ p ( X ) ψ p ( X ) T ] = I D p L 2 ( μ ) L^2(\mu) L 2 ( μ ) ⟨ v , ψ p ⟩ L 2 ( μ ) = ∥ v ∥ 2 \langle v,\psi_p\rangle_{L^2(\mu)} = \|v\|_2 ⟨ v , ψ p ⟩ L 2 ( μ ) = ∥ v ∥ 2 E μ [ ∥ ψ p ( X ) ∥ 2 2 ] = D p \mathbb{E}_{\mu}[\|\psi_p(X)\|_2^2] = D_p E μ [ ∥ ψ p ( X ) ∥ 2 2 ] = D p G p G_p G p Theorem D.1 . For example, the normalized Hermite basis for the standard Gaussian marginal can be constructed and evaluated in poly ( D p ) \operatorname{poly}(D_p) poly ( D p )
Finally, we discuss clipping. As in the Gaussian case, we radially clip the feature vectors to obtain a uniform bound on their norms: ψ ˉ p , T ( x ) : = T ψ p ( x ) / max { T , ∥ ψ p ( x ) ∥ 2 } \bar{\psi}_{p,T}(x) := T\psi_p(x)/\max\{T,\lVert\psi_p(x)\rVert_2\} ψ ˉ p , T ( x ) := T ψ p ( x ) / max { T , ∥ ψ p ( x ) ∥ 2 } μ \mu μ c > 0 c > 0 c > 0
T = min { t > 0 : E μ [ ( 1 − t ∥ ψ p ( X ) ∥ 2 ) + ] ≤ c α } . (25) T = \min\left\{t > 0 : \mathbb{E}_{\mu}\left[\left(1-\frac{t}{\lVert\psi_p(X)\rVert_2}\right)_+\right] \le c\alpha\right\}. \tag*{(25)} T = min { t > 0 : E μ [ ( 1 − ∥ ψ p ( X ) ∥ 2 t ) + ] ≤ c α } . (25) where ( x ) + = max { x , 0 } (x)_+ = \max\{x,0\} ( x ) + = max { x , 0 } (7) uses only orthonormality and therefore also applies to the present feature map. Since ( 1 − t / ∥ ψ p ( x ) ∥ 2 ) + ≤ 1 { ∥ ψ p ( x ) ∥ 2 > t } (1-t/\lVert\psi_p(x)\rVert_2)_+ \le\mathbf{1}\{\lVert\psi_p(x)\rVert_2 > t\} ( 1 − t / ∥ ψ p ( x ) ∥ 2 ) + ≤ 1 {∥ ψ p ( x ) ∥ 2 > t } t = D p / ( c α ) t = \sqrt{D_p/(c\alpha)} t = D p / ( c α ) T ≤ D p / ( c α ) T \le\sqrt{D_p/(c\alpha)} T ≤ D p / ( c α ) μ = N ( 0 , I d ) \mu= N(0,I_d) μ = N ( 0 , I d ) d ≥ 2 p 2 / ( c α ) d \ge2p^2/(c\alpha) d ≥ 2 p 2 / ( c α ) Lemma C.2 shows that T ≤ 2 D p T \le2\sqrt{D_p} T ≤ 2 D p O ( D p / ( ε D P α ) ) O(D_p/(\varepsilon_{\mathrm{DP}}\alpha)) O ( D p / ( ε DP α )) 2
Analysis
In this section, we prove Theorem D.1 . We first establish privacy.
Proposition D.2. The learner in Theorem D.1 satisfies ( ε D P , δ D P ) (\varepsilon_{\mathrm{DP}},\delta_{\mathrm{DP}}) ( ε DP , δ DP )
Proof. The feature map, clipping threshold, coefficient ball, and sample partition are public. Since ∥ ψ ˉ p , T ( x ) ∥ 2 ≤ T \lVert\bar{\psi}_{p,T}(x)\rVert_2 \le T ∥ ψ ˉ p , T ( x ) ∥ 2 ≤ T T T T v v v R D p \mathbb{R}^{D_p} R D p ( ε D P , δ D P ) (\varepsilon_{\mathrm{DP}},\delta_{\mathrm{DP}}) ( ε DP , δ DP ) Lemma B.4 . The neighboring-dataset argument in the proof of Proposition C.1 then applies unchanged, establishing ( ε D P , δ D P ) (\varepsilon_{\mathrm{DP}},\delta_{\mathrm{DP}}) ( ε DP , δ DP )
We next prove the bounded-norm polynomial approximation guarantee. The key ingredient is the exponential density bound for one-dimensional log-concave distributions (Fact B.13), which allows us to transfer weighted polynomial approximation bounds to the L 1 L^1 L 1 L 2 L^2 L 2
Lemma D.3 (Bounded-norm polynomial approximation of halfspaces under log-concave measures). There exist universal constants C , R 0 ≥ 1 C,R_0 \ge1 C , R 0 ≥ 1 μ \mu μ R d \mathbb{R}^d R d p ≥ 2 p \ge2 p ≥ 2 c : R d → { − 1 , 1 } c:\mathbb{R}^d \to\{-1,1\} c : R d → { − 1 , 1 } q q q p p p ∥ q − c ∥ L 1 ( μ ) ≤ C / log ( p + 1 ) \lVert q-c\rVert_{L^1(\mu)} \le C/\log(p+1) ∥ q − c ∥ L 1 ( μ ) ≤ C / log ( p + 1 ) ∥ q ∥ L 2 ( μ ) ≤ R 0 \lVert q\rVert_{L^2(\mu)} \le R_0 ∥ q ∥ L 2 ( μ ) ≤ R 0 p = ⌈ exp ( C / α ) ⌉ p=\lceil\exp(C/\alpha)\rceil p = ⌈ exp ( C / α )⌉ ∥ q − c ∥ L 1 ( μ ) ≤ α \lVert q-c\rVert_{L^1(\mu)} \le\alpha ∥ q − c ∥ L 1 ( μ ) ≤ α
Proof. Consider a log-concave probability measure ν \nu ν R \mathbb{R} R f θ ( z ) = sign ( z − θ ) f_\theta(z)=\operatorname{sign}(z-\theta) f θ ( z ) = sign ( z − θ ) r r r p p p
∥ r − f θ ∥ L 1 ( ν ) ≤ C / log ( p + 1 ) and ∥ r − f θ ∥ L 2 ( ν ) 2 ≤ C . (26) \lVert r-f_\theta\rVert_{L^1(\nu)} \le C/\log(p+1) \quad\text{and}\quad\lVert r-f_\theta\rVert_{L^2(\nu)}^2 \le C. \tag*{(26)} ∥ r − f θ ∥ L 1 ( ν ) ≤ C / log ( p + 1 ) and ∥ r − f θ ∥ L 2 ( ν ) 2 ≤ C . (26) Assuming the above is true, we next extend it to R d \mathbb{R}^d R d c ( x ) = sign ( ⟨ u , x ⟩ − θ ) c(x)=\operatorname{sign}(\langle u,x\rangle-\theta) c ( x ) = sign (⟨ u , x ⟩ − θ ) X ∼ μ X\sim\mu X ∼ μ a = E μ ⟨ u , X ⟩ a=\mathbb{E}_{\mu}\langle u,X\rangle a = E μ ⟨ u , X ⟩ b 2 = Var μ ( ⟨ u , X ⟩ ) > 0 b^2=\operatorname{Var}_{\mu}(\langle u,X\rangle)>0 b 2 = Var μ (⟨ u , X ⟩) > 0 3 ν \nu ν Z = ( ⟨ u , X ⟩ − a ) / b Z=(\langle u,X\rangle-a)/b Z = (⟨ u , X ⟩ − a ) / b ν \nu ν (26) to f ( θ − a ) / b f_{(\theta-a)/b} f ( θ − a ) / b q ( x ) = r ( ( ⟨ u , x ⟩ − a ) / b ) q(x)=r((\langle u,x\rangle-a)/b) q ( x ) = r ((⟨ u , x ⟩ − a ) / b ) q ( X ) = r ( Z ) q(X)=r(Z) q ( X ) = r ( Z ) c ( X ) = f ( θ − a ) / b ( Z ) c(X)=f_{(\theta-a)/b}(Z) c ( X ) = f ( θ − a ) / b ( Z ) ∥ q − c ∥ L 1 ( μ ) ≤ C / log ( p + 1 ) \|q-c\|_{L_1(\mu)}\le C/\log(p+1) ∥ q − c ∥ L 1 ( μ ) ≤ C / log ( p + 1 ) ∥ q − c ∥ L 2 ( μ ) 2 ≤ C \|q-c\|_{L_2(\mu)}^2\le C ∥ q − c ∥ L 2 ( μ ) 2 ≤ C ∥ c ∥ L 2 ( μ ) = 1 \|c\|_{L_2(\mu)}=1 ∥ c ∥ L 2 ( μ ) = 1 q = ( q − c ) + c q=(q-c)+c q = ( q − c ) + c
∥ q ∥ L 2 ( μ ) ≤ ∥ q − c ∥ L 2 ( μ ) + ∥ c ∥ L 2 ( μ ) ≤ C + 1 = : R 0 . \|q\|_{L_2(\mu)}\le\|q-c\|_{L_2(\mu)}+\|c\|_{L_2(\mu)}\le\sqrt{C}+1=:R_0. ∥ q ∥ L 2 ( μ ) ≤ ∥ q − c ∥ L 2 ( μ ) + ∥ c ∥ L 2 ( μ ) ≤ C + 1 =: R 0 . It remains to prove Equation (26) . Let W ( z ) = exp ( − ∣ z ∣ / 32 ) W(z)=\exp(-|z|/32) W ( z ) = exp ( − ∣ z ∣/32 ) [29 ] (Lemma 6) (restated in Fact B.13), the density satisfies
g ( z ) ≤ e exp ( − ∣ z ∣ / 16 ) . (27) g(z)\le e\exp(-|z|/16). \tag*{(27)} g ( z ) ≤ e exp ( − ∣ z ∣/16 ) . (27) Note that f θ ( z ) W ( z ) f_\theta(z)W(z) f θ ( z ) W ( z ) ∣ f θ ( z ) W ( z ) ∣ = e − ∣ z ∣ / 32 |f_\theta(z)W(z)|=e^{-|z|/32} ∣ f θ ( z ) W ( z ) ∣ = e − ∣ z ∣/32 [24 ] (restated in Lemma B.15) gives a polynomial r r r p p p
∥ ( r − f θ ) W ∥ L 1 ≤ C log ( p + 1 ) . (28) \|(r-f_\theta)W\|_{L_1}\le\frac{C}{\log(p+1)}. \tag*{(28)} ∥ ( r − f θ ) W ∥ L 1 ≤ log ( p + 1 ) C . (28) We now bound the L 2 L_2 L 2
∥ ( r − f θ ) W ∥ L 2 2 ≤ ∥ ( r − f θ ) W ∥ L ∞ ∥ ( r − f θ ) W ∥ L 1 ≤ ( ∥ r W ∥ L ∞ + ∥ f θ W ∥ L ∞ ) C log ( p + 1 ) ≤ C log ( p + 1 ) C log ( p + 1 ) ≤ C . (29) \begin{aligned}
\|(r-f_\theta)W\|_{L_2}^2\le\|(r-f_\theta)W\|_{L_\infty}\|(r-f_\theta)W\|_{L_1}\le\left(\|rW\|_{L_\infty}+\|f_\theta W\|_{L_\infty}\right)\frac{C}{\log(p+1)} \\
&\le C\log(p+1)\frac{C}{\log(p+1)}\le C. \tag*{(29)}
\end{aligned} ∥ ( r − f θ ) W ∥ L 2 2 ≤ ∥ ( r − f θ ) W ∥ L ∞ ∥ ( r − f θ ) W ∥ L 1 ≤ ( ∥ r W ∥ L ∞ + ∥ f θ W ∥ L ∞ ) log ( p + 1 ) C ≤ C log ( p + 1 ) log ( p + 1 ) C ≤ C . (29) Here the first inequality follows from Hölder’s inequality and the second uses Equation (28) and triangle inequality. The third inequality follows from Mhaskar and Saff [42 ] (Theorem 3.1) (restated in Lemma B.14) and observing that ∥ f θ W ∥ L ∞ ≤ 1 \|f_\theta W\|_{L_\infty}\le1 ∥ f θ W ∥ L ∞ ≤ 1 g ≤ e W 2 g\le eW^2 g ≤ e W 2 W ≤ 1 W\le1 W ≤ 1 (28) and (29) to a norm with respect to measure induced by ν \nu ν (26) . This completes the proof.
We now turn to the proof of Theorem D.1 . Fix c ∈ ( 0 , 1 / 4 ] c\in(0,1/4] c ∈ ( 0 , 1/4 ] (25) . The block-size condition differs from the Gaussian case only through the radius R 0 R_0 R 0 T T T n 0 ≥ 2 n_0\ge2 n 0 ≥ 2
C [ R 0 T D p log ( 1 / δ D P ) ε D P n 0 + R 0 D p n 0 ] ≤ c α . (30) C\left[\frac{R_0T\sqrt{D_p}\log(1/\delta_{\mathrm{DP}})}{\varepsilon_{\mathrm{DP}}n_0}+R_0\sqrt{\frac{D_p}{n_0}}\right]\le c\alpha. \tag*{(30)} C [ ε DP n 0 R 0 T D p log ( 1/ δ DP ) + R 0 n 0 D p ] ≤ c α . (30) Proof of Theorem D.1 . Proposition D.2 provides the privacy guarantee. We now prove the accuracy and running time bounds. Write L P ( v ) = E ( X , Y ) ∼ P ∣ ⟨ v , ψ ˉ p , T ( X ) ⟩ − Y ∣ L_P(v)=\mathbb{E}_{(X,Y)\sim P}|\langle v,\bar{\psi}_{p,T}(X)\rangle-Y| L P ( v ) = E ( X , Y ) ∼ P ∣ ⟨ v , ψ ˉ p , T ( X )⟩ − Y ∣ L ⋆ = min ∥ v ∥ 2 ≤ R 0 L P ( v ) L^\star=\min_{\|v\|_2\le R_0}L_P(v) L ⋆ = min ∥ v ∥ 2 ≤ R 0 L P ( v ) v v v
We first compare L ⋆ L^\star L ⋆ c 0 ∈ C c_0\in\mathcal{C} c 0 ∈ C Lemma D.3 , our choice of p p p q = ⟨ v q , ψ p ⟩ q=\langle v_q,\psi_p\rangle q = ⟨ v q , ψ p ⟩ ∥ q − c 0 ∥ L 1 ( μ ) ≤ c α \|q-c_0\|_{L_1(\mu)}\le c\alpha ∥ q − c 0 ∥ L 1 ( μ ) ≤ c α ∥ v q ∥ 2 = ∥ q ∥ L 2 ( μ ) ≤ R 0 \|v_q\|_2=\|q\|_{L_2(\mu)}\le R_0 ∥ v q ∥ 2 = ∥ q ∥ L 2 ( μ ) ≤ R 0 s ( x ) = T / max { T , ∥ ψ p ( x ) ∥ 2 } s(x)=T/\max\{T,\|\psi_p(x)\|_2\} s ( x ) = T / max { T , ∥ ψ p ( x ) ∥ 2 } 1 − s ( x ) = ( 1 − T / ∥ ψ p ( x ) ∥ 2 ) + 1-s(x)=(1-T/\|\psi_p(x)\|_2)_+ 1 − s ( x ) = ( 1 − T /∥ ψ p ( x ) ∥ 2 ) + (25) gives E μ [ 1 − s ( X ) ] ≤ c α \mathbb{E}_\mu[1-s(X)]\le c\alpha E μ [ 1 − s ( X )] ≤ c α (23) gives L P ( v q ) ≤ 2 err P ( c 0 ) + 2 c α L_P(v_q)\le2\operatorname{err}_P(c_0)+2c\alpha L P ( v q ) ≤ 2 err P ( c 0 ) + 2 c α ∥ v q ∥ 2 ≤ R 0 \|v_q\|_2\le R_0 ∥ v q ∥ 2 ≤ R 0 c 0 ∈ C c_0\in\mathcal{C} c 0 ∈ C
L ⋆ ≤ 2 OPT + 2 c α . (31) L^\star\le2\operatorname{OPT}+2c\alpha. \tag*{(31)} L ⋆ ≤ 2 OPT + 2 c α . (31) Next, we bound the expected excess regression loss of a single training run. The loss is convex and T T T R D p \mathbb{R}^{D_p} R D p 2 R 0 2R_0 2 R 0 E μ ∥ ψ ˉ p , T ( X ) ∥ 2 2 ≤ D p \mathbb{E}_{\mu}\lVert\bar{\psi}_{p,T}(X)\rVert_2^2 \le D_p E μ ∥ ψ ˉ p , T ( X ) ∥ 2 2 ≤ D p (18) , we obtain
E [ L P ( v ^ j ) − L ⋆ ] ≤ E [ L ^ S j ( v ^ j ) − min ∥ v ∥ 2 ≤ R 0 L ^ S j ( v ) ] + E sup ∥ v ∥ 2 ≤ R 0 ( L P ( v ) − L ^ S j ( v ) ) ≤ C R 0 T D p log ( 1 / δ D P ) ε D P n 0 + 2 R 0 D p n 0 ≤ c α . \begin{aligned}
\mathbb{E}[L_P(\hat{v}_j)-L^\star] \le\mathbb{E}\left[\widehat{L}_{S_j}(\hat{v}_j)-\min_{\lVert v\rVert_2\le R_0}\widehat{L}_{S_j}(v)\right]+\mathbb{E}\sup_{\lVert v\rVert_2\le R_0}\left(L_P(v)-\widehat{L}_{S_j}(v)\right) \\
&\le C\frac{R_0T\sqrt{D_p\log(1/\delta_{\mathrm{DP}})}}{\varepsilon_{\mathrm{DP}}n_0}+2R_0\sqrt{\frac{D_p}{n_0}}\le c\alpha.
\end{aligned} E [ L P ( v ^ j ) − L ⋆ ] ≤ E [ L S j ( v ^ j ) − ∥ v ∥ 2 ≤ R 0 min L S j ( v ) ] + E ∥ v ∥ 2 ≤ R 0 sup ( L P ( v ) − L S j ( v ) ) ≤ C ε DP n 0 R 0 T D p log ( 1/ δ DP ) + 2 R 0 n 0 D p ≤ c α . where the second inequality follows from Lemmas B.4 and B.7 , and the last from (30) .
Since the training runs are independent and the thresholding and validation steps use the same choices of k k k M M M m m m (22) applies with L ⋆ = min ∥ v ∥ 2 ≤ R 0 L P ( v ) L^\star=\min_{\lVert v\rVert_2\le R_0}L_P(v) L ⋆ = min ∥ v ∥ 2 ≤ R 0 L P ( v ) (31) , err P ( h ) ≤ OPT + α \operatorname{err}_P(h)\le\operatorname{OPT}+\alpha err P ( h ) ≤ OPT + α 1 − β 1-\beta 1 − β
It remains to bound the sample size and running time. Since R 0 R_0 R 0 (30) gives
n 0 = O ( D p α 2 + T D p log ( 1 / δ D P ) ε D P α ) , n_0=O\left(\frac{D_p}{\alpha^2}+\frac{T\sqrt{D_p\log(1/\delta_{\mathrm{DP}})}}{\varepsilon_{\mathrm{DP}}\alpha}\right), n 0 = O ( α 2 D p + ε DP α T D p log ( 1/ δ DP ) ) , independent of β \beta β k = O ( log ( 2 / β ) ) k=O(\log(2/\beta)) k = O ( log ( 2/ β )) m m m D p ≥ 1 D_p\ge1 D p ≥ 1 ∥ ψ p ( x ) ∥ 2 ≥ 1 \lVert\psi_p(x)\rVert_2\ge1 ∥ ψ p ( x ) ∥ 2 ≥ 1 L 2 ( μ ) L^2(\mu) L 2 ( μ ) (25) is at least ( 1 − t ) + (1-t)_+ ( 1 − t ) + T ≥ 1 − c α ≥ 3 / 4 T\ge1-c\alpha\ge3/4 T ≥ 1 − c α ≥ 3/4 n = k n 0 + m n=kn_0+m n = k n 0 + m T ≤ D p / ( c α ) T\le\sqrt{D_p/(c\alpha)} T ≤ D p / ( c α ) (7) , the bound is always at most O ~ ( D p / α 2 + D p / ( ε D P α 3 / 2 ) ) \widetilde{O}(D_p/\alpha^2+D_p/(\varepsilon_{\mathrm{DP}}\alpha^{3/2})) O ( D p / α 2 + D p / ( ε DP α 3/2 ))
Finally, we bound the running time, measured in arithmetic operations. By the computational hypothesis in Theorem D.1 , computing G p − 1 / 2 G_p^{-1/2} G p − 1/2 T T T poly ( D p ) \operatorname{poly}(D_p) poly ( D p ) ψ p ( x ) = G p − 1 / 2 m p ( x ) \psi_p(x)=G_p^{-1/2}m_p(x) ψ p ( x ) = G p − 1/2 m p ( x ) O ( p D p ) O(pD_p) O ( p D p ) O ( D p 2 ) O(D_p^2) O ( D p 2 ) O ( D p ) O(D_p) O ( D p ) B D p 2 ( R 0 ) B_{D_p^2}(R_0) B D p 2 ( R 0 ) O ( D p ) O(D_p) O ( D p ) Theorem 2.1 , the private ERM runs and the validation step take O ( k n 0 2 D p ) O(kn_0^2D_p) O ( k n 0 2 D p ) O ( k M m D p ) O(kMmD_p) O ( k M m D p ) p < D p p<D_p p < D p
poly ( D p ) + O ( n D p 2 + k n 0 2 D p + k M m D p ) = poly ( n ) , \operatorname{poly}(D_p)+O(nD_p^2+kn_0^2D_p+kMmD_p)=\operatorname{poly}(n), poly ( D p ) + O ( n D p 2 + k n 0 2 D p + k M m D p ) = poly ( n ) , where the last equality uses M ≤ p < D p ≤ n 0 M\le p<D_p\le n_0 M ≤ p < D p ≤ n 0 k n 0 + m = n kn_0+m=n k n 0 + m = n
Proofs for Proper Learning with Gaussian Marginals
Proof of Lemma 3.2 . We follow the subspace construction in the proof of Diakonikolas et al. [15 ] . Write μ = N ( 0 , I d ) \mu=\mathcal{N}(0,I_d) μ = N ( 0 , I d ) q ⋆ q^\star q ⋆ r ( x ) = E [ U ∣ X = x ] r(x)=\mathbb{E}[U\mid X=x] r ( x ) = E [ U ∣ X = x ] P p \mathcal{P}_p P p ∥ q − q ⋆ ∥ L 2 ( μ ) ≤ c 0 α \lVert q-q^\star\rVert_{L^2(\mu)}\le c_0\alpha ∥ q − q ⋆ ∥ L 2 ( μ ) ≤ c 0 α ∣ r ∣ ≤ 1 \lvert r\rvert\le1 ∣ r ∣ ≤ 1 ∥ q ⋆ ∥ L 2 ( μ ) ≤ 1 \lVert q^\star\rVert_{L^2(\mu)}\le1 ∥ q ⋆ ∥ L 2 ( μ ) ≤ 1 ∥ q ∥ L 2 ( μ ) ≤ 1 + c 0 α \lVert q\rVert_{L^2(\mu)}\le1+c_0\alpha ∥ q ∥ L 2 ( μ ) ≤ 1 + c 0 α Q ∈ P p Q\in\mathcal{P}_p Q ∈ P p
∣ E [ ( U − q ( X ) ) Q ( X ) ] ∣ = ∣ E [ ( q ⋆ ( X ) − q ( X ) ) Q ( X ) ] ∣ ≤ c 0 α ∥ Q ∥ L 2 ( μ ) . (32) \left\lvert\mathbb{E}[(U-q(X))Q(X)]\right\rvert=\left\lvert\mathbb{E}[(q^\star(X)-q(X))Q(X)]\right\rvert\le c_0\alpha\lVert Q\rVert_{L^2(\mu)}. \tag*{(32)} ∣ E [( U − q ( X )) Q ( X )] ∣ = ∣ E [( q ⋆ ( X ) − q ( X )) Q ( X )] ∣ ≤ c 0 α ∥ Q ∥ L 2 ( μ ) . (32) Set M = E μ [ ∇ q ( X ) ∇ q ( X ) T ] M=\mathbb{E}_{\mu}\left[\nabla q(X)\nabla q(X)^{\mathsf{T}}\right] M = E μ [ ∇ q ( X ) ∇ q ( X ) T ] V V V α 2 / C 0 \alpha^2/C_0 α 2 / C 0 [15 ] give tr ( M ) ≤ p ∥ q ∥ L 2 ( μ ) 2 \operatorname{tr}(M)\le p\lVert q\rVert_{L^2(\mu)}^2 tr ( M ) ≤ p ∥ q ∥ L 2 ( μ ) 2
dim ( V ) ≤ C 0 p ( 1 + c 0 α ) 2 α 2 = O ( α − 4 ) . \dim(V)\le\frac{C_0p(1+c_0\alpha)^2}{\alpha^2}=O\left(\alpha^{-4}\right). dim ( V ) ≤ α 2 C 0 p ( 1 + c 0 α ) 2 = O ( α − 4 ) . Fix a halfspace f = h w , t f = h_{w,t} f = h w , t w = w V + w ⊥ w = w_V + w_\perp w = w V + w ⊥ V V V w ⊥ = 0 w_\perp= 0 w ⊥ = 0 f f f V V V ξ = w ⊥ / ∥ w ⊥ ∥ 2 \xi= w_\perp/\lVert w_\perp\rVert_2 ξ = w ⊥ / ∥ w ⊥ ∥ 2
( A ξ g ) ( x ) = E G ∼ N ( 0 , 1 ) [ g ( x − ⟨ ξ , x ⟩ ξ + G ξ ) ] . (A_\xi g)(x) = \mathbb{E}_{G \sim\mathcal{N}(0,1)}[g(x - \langle\xi, x\rangle\xi+ G\xi)]. ( A ξ g ) ( x ) = E G ∼ N ( 0 , 1 ) [ g ( x − ⟨ ξ , x ⟩ ξ + G ξ )] . Under μ \mu μ ξ ⊥ \xi^\perp ξ ⊥ A ξ A_\xi A ξ L 2 ( μ ) L^2(\mu) L 2 ( μ ) L 1 ( μ ) L^1(\mu) L 1 ( μ ) P p \mathcal{P}_p P p [15 ] directly gives
∥ q − A ξ q ∥ L 2 ( μ ) 2 ≤ E [ ( ∂ ξ q ( X ) ) 2 ] = ξ ⊤ M ξ ≤ α 2 / C 0 . (33) \lVert q - A_\xi q\rVert_{L^2(\mu)}^2 \leq\mathbb{E}\left[(\partial_\xi q(X))^2\right] = \xi^\top M \xi\leq\alpha^2/C_0. \tag*{(33)} ∥ q − A ξ q ∥ L 2 ( μ ) 2 ≤ E [ ( ∂ ξ q ( X ) ) 2 ] = ξ ⊤ M ξ ≤ α 2 / C 0 . (33) By Lemma B.10 , taking C 0 C_0 C 0 a ∈ P p a \in\mathcal{P}_p a ∈ P p ∥ a ∥ L 2 ( μ ) ≤ 1 \lVert a\rVert_{L^2(\mu)} \leq1 ∥ a ∥ L 2 ( μ ) ≤ 1 ∥ f − a ∥ L 1 ( μ ) ≤ α \lVert f-a\rVert_{L^1(\mu)} \leq\alpha ∥ f − a ∥ L 1 ( μ ) ≤ α Q = a − A ξ a Q = a - A_\xi a Q = a − A ξ a ∥ Q ∥ L 2 ( μ ) ≤ 1 \lVert Q\rVert_{L^2(\mu)} \leq1 ∥ Q ∥ L 2 ( μ ) ≤ 1 A ξ Q = 0 A_\xi Q = 0 A ξ Q = 0
∥ ( f − A ξ f ) − Q ∥ L 1 ( μ ) ≤ ∥ f − a ∥ L 1 ( μ ) + ∥ A ξ ( f − a ) ∥ L 1 ( μ ) ≤ 2 α . \lVert(f-A_\xi f)-Q\rVert_{L^1(\mu)} \leq\lVert f-a\rVert_{L^1(\mu)} + \lVert A_\xi(f-a)\rVert_{L^1(\mu)} \leq2\alpha. ∥( f − A ξ f ) − Q ∥ L 1 ( μ ) ≤ ∥ f − a ∥ L 1 ( μ ) + ∥ A ξ ( f − a ) ∥ L 1 ( μ ) ≤ 2 α . Since ∣ U ∣ ≤ 1 \lvert U\rvert\leq1 ∣ U ∣ ≤ 1 A ξ Q = 0 A_\xi Q = 0 A ξ Q = 0
E [ U ( f ( X ) − A ξ f ( X ) ) ] ≤ 2 α + E [ ( U − q ( X ) ) Q ( X ) ] + E [ ( q ( X ) − A ξ q ( X ) ) Q ( X ) ] ≤ ( 2 + c 0 + C 0 − 1 / 2 ) α , \begin{aligned}
\mathbb{E}[U(f(X)-A_\xi f(X))] \leq2\alpha+ \mathbb{E}[(U-q(X))Q(X)] + \mathbb{E}[(q(X)-A_\xi q(X))Q(X)] \\
&\leq(2+c_0+C_0^{-1/2})\alpha,
\end{aligned} E [ U ( f ( X ) − A ξ f ( X ))] ≤ 2 α + E [( U − q ( X )) Q ( X )] + E [( q ( X ) − A ξ q ( X )) Q ( X )] ≤ ( 2 + c 0 + C 0 − 1/2 ) α , where the last inequality uses Equations (32) and (33) . Now,
A ξ f ( x ) = E G [ sign ( ⟨ w V , x ⟩ + ∥ w ⊥ ∥ 2 G + t ) ] . A_\xi f(x) = \mathbb{E}_G[\operatorname{sign}(\langle w_V,x\rangle+ \lVert w_\perp\rVert_2 G+t)]. A ξ f ( x ) = E G [ sign (⟨ w V , x ⟩ + ∥ w ⊥ ∥ 2 G + t )] . This is a mixture of halfspaces with unit normals in V V V w V = 0 w_V=0 w V = 0 h ∗ h^* h ∗ E [ U ( f ( X ) − h ∗ ( X ) ) ] ≤ ( 2 + c 0 + C 0 − 1 / 2 ) α \mathbb{E}[U(f(X)-h^*(X))] \leq(2+c_0+C_0^{-1/2})\alpha E [ U ( f ( X ) − h ∗ ( X ))] ≤ ( 2 + c 0 + C 0 − 1/2 ) α w ⊥ = 0 w_\perp=0 w ⊥ = 0 h ∗ = f h^*=f h ∗ = f
For the finite class, use the covering and discretization bounds of Diakonikolas et al. [15 ] , restated in Facts B.11 and B.12. Normalize the nonzero centers of an α / 2 \alpha/2 α /2 V V V α \alpha α V \mathcal{V} V
R = α ⌈ K 0 log ( 1 / α ) / α ⌉ R = \alpha\left\lceil K_0\sqrt{\log(1/\alpha)}/\alpha\right\rceil R = α ⌈ K 0 log ( 1/ α ) / α ⌉ for a sufficiently large universal constant K 0 K_0 K 0
H ( q ) = { h v , j α : v ∈ V , j ∈ Z , ∣ j α ∣ ≤ R } ∪ { h e 1 , R , h e 1 , − R } . \mathcal{H}(q) = \{h_{v,j\alpha}: v \in\mathcal{V},\ j \in\mathbb{Z},\ \lvert j\alpha\rvert\leq R\} \cup\{h_{e_1,R},h_{e_1,-R}\}. H ( q ) = { h v , j α : v ∈ V , j ∈ Z , ∣ j α ∣ ≤ R } ∪ { h e 1 , R , h e 1 , − R } . When V = { 0 } V=\{0\} V = { 0 } h ∈ H ( q ) h \in\mathcal{H}(q) h ∈ H ( q ) P [ h ( X ) ≠ h ∗ ( X ) ] = O ( α ) \mathbb{P}[h(X)\ne h^*(X)] = O(\alpha) P [ h ( X ) = h ∗ ( X )] = O ( α ) h ∗ h^* h ∗ [ − R , R ] [-R,R] [ − R , R ]
E [ U ( f ( X ) − h ( X ) ) ] ≤ E [ U ( f ( X ) − h ∗ ( X ) ) ] + 2 P [ h ( X ) ≠ h ∗ ( X ) ] ≤ C α . \mathbb{E}[U(f(X)-h(X))] \leq\mathbb{E}[U(f(X)-h^*(X))] + 2\mathbb{P}[h(X)\ne h^*(X)] \leq C\alpha. E [ U ( f ( X ) − h ( X ))] ≤ E [ U ( f ( X ) − h ∗ ( X ))] + 2 P [ h ( X ) = h ∗ ( X )] ≤ C α . Finally, the covering bound gives
log ∣ H ( q ) ∣ = O ( ( dim ( V ) + 1 ) log ( 1 / α ) ) = O ( α − 4 log ( 1 / α ) ) . \log\lvert\mathcal{H}(q)\rvert= O((\dim(V)+1)\log(1/\alpha)) = O(\alpha^{-4}\log(1/\alpha)). log ∣ H ( q )∣ = O (( dim ( V ) + 1 ) log ( 1/ α )) = O ( α − 4 log ( 1/ α )) . The construction uses only q q q α \alpha α
Proof of Lemma 3.4. Let
m ~ = 2 n ∑ ( X i , Y i ) ∈ S 1 Y i ψ ˉ p , T ( X i ) . \widetilde{m} = \frac{2}{n}\sum_{(X_i,Y_i)\in S_1} Y_i\bar{\psi}_{p,T}(X_i). m = n 2 ( X i , Y i ) ∈ S 1 ∑ Y i ψ ˉ p , T ( X i ) . Each summand has norm at most T T T m ~ \widetilde{m} m 4 T / n 4T/n 4 T / n m ~ + Z \widetilde{m}+Z m + Z ( ε D P , δ D P ) (\varepsilon_{\mathrm{DP}},\delta_{\mathrm{DP}}) ( ε DP , δ DP ) [20 ] . Projection and construction of q q q
Write ℓ = log ( 8 / β ) \ell=\log(8/\beta) ℓ = log ( 8/ β ) L δ D P = log ( 1.25 / δ D P ) L_{\delta_{\mathrm{DP}}}=\log(1.25/\delta_{\mathrm{DP}}) L δ DP = log ( 1.25/ δ DP ) 2 T 2T 2 T D p D_p D p Lemma B.1 , with probability at least 1 − β / 4 1-\beta/4 1 − β /4
∥ m ~ − m T ∥ 2 ≤ C 1 ( D p ℓ n + T ℓ n ) . \lVert\widetilde{m}-m_T\rVert_2 \le C_1\left(\sqrt{\frac{D_p\ell}{n}}+\frac{T\ell}{n}\right). ∥ m − m T ∥ 2 ≤ C 1 ( n D p ℓ + n T ℓ ) . Gaussian concentration gives, with probability at least 1 − β / 4 1-\beta/4 1 − β /4 ∥ Z ∥ 2 ≤ σ ( D p + 2 ℓ ) \lVert Z\rVert_2\le\sigma\left(\sqrt{D_p}+\sqrt{2\ell}\right) ∥ Z ∥ 2 ≤ σ ( D p + 2 ℓ ) ∣ U ∣ ≤ 1 |U|\le1 ∣ U ∣ ≤ 1 ∥ m T ∥ 2 ≤ 1 \lVert m_T\rVert_2\le1 ∥ m T ∥ 2 ≤ 1 m T m_T m T T = 2 D p T=2\sqrt{D_p} T = 2 D p 1 − β / 2 1-\beta/2 1 − β /2
∥ m ~ − m T ∥ 2 ≤ ∥ m ^ − m T ∥ 2 + ∥ Z ∥ 2 ≤ C 2 ( D p ℓ n + D p ℓ n + ( D p + D p ℓ ) L δ D P ε D P n ) . \begin{aligned}
\lVert\widetilde{m}-m_T\rVert_2\le\lVert\widehat{m}-m_T\rVert_2+\lVert Z\rVert_2 \\
&\le C_2\left(\sqrt{\frac{D_p\ell}{n}}+\frac{\sqrt{D_p\ell}}{n}+\frac{(D_p+\sqrt{D_p\ell})\sqrt{L_{\delta_{\mathrm{DP}}}}}{\varepsilon_{\mathrm{DP}}n}\right).
\end{aligned} ∥ m − m T ∥ 2 ≤ ∥ m − m T ∥ 2 + ∥ Z ∥ 2 ≤ C 2 ( n D p ℓ + n D p ℓ + ε DP n ( D p + D p ℓ ) L δ DP ) . For a sufficiently large universal constant K K K
n ≥ K ( D p ℓ α 2 + D p ℓ L δ D P ε D P α ) (34) n\ge K\left(\frac{D_p\ell}{\alpha^2}+\frac{D_p\ell\sqrt{L_{\delta_{\mathrm{DP}}}}}{\varepsilon_{\mathrm{DP}}\alpha}\right) \tag*{(34)} n ≥ K ( α 2 D p ℓ + ε DP α D p ℓ L δ DP ) (34) makes this at most c 0 c α c_0c\alpha c 0 c α (9) ,
L S ( q ) − inf Q ∈ P p L S ( Q ) = ∥ m ~ − m T ∥ 2 2 ≤ c 0 2 c 2 α 2 . L_S(q)-\inf_{Q\in\mathcal{P}_p}L_S(Q)=\lVert\widetilde{m}-m_T\rVert_2^2\le c_0^2c^2\alpha^2. L S ( q ) − Q ∈ P p inf L S ( Q ) = ∥ m − m T ∥ 2 2 ≤ c 0 2 c 2 α 2 . Finally, projection and orthonormality give ∥ q ∥ L 2 ( μ ) = ∥ m ~ ∥ 2 ≤ 1 \lVert q\rVert_{L^2(\mu)}=\lVert\widetilde{m}\rVert_2\le1 ∥ q ∥ L 2 ( μ ) = ∥ m ∥ 2 ≤ 1
Proof of Theorem 3.1. Round n n n S 1 S_1 S 1 S 2 S_2 S 2 S 2 S_2 S 2 q q q q q q ε D P \varepsilon_{\mathrm{DP}} ε DP ( ε D P , δ D P ) (\varepsilon_{\mathrm{DP}},\delta_{\mathrm{DP}}) ( ε DP , δ DP )
Since p = ⌈ C 0 / ( c α ) 2 ⌉ p=\lceil C_0/(c\alpha)^2\rceil p = ⌈ C 0 / ( c α ) 2 ⌉ C d i m ≥ 2 ( C 0 + 1 ) 2 c − 5 C_{\mathrm{dim}}\ge2(C_0+1)^2c^{-5} C dim ≥ 2 ( C 0 + 1 ) 2 c − 5 d ≥ 2 p 2 / ( c α ) d\ge2p^2/(c\alpha) d ≥ 2 p 2 / ( c α ) Lemma 3.5 follows from the theorem’s assumption. The first two terms in the sample bound imply Equation (34) and hence the event in Lemma 3.4 with probability at least 1 − β / 2 1-\beta/2 1 − β /2 Lemma 3.5 gives
min h ∈ H ( q ) err P ( h ) ≤ OPT + ( C / 2 + 1 ) c α . \min_{h\in\mathcal{H}(q)}\operatorname{err}_P(h)\le\operatorname{OPT}+(C/2+1)c\alpha. h ∈ H ( q ) min err P ( h ) ≤ OPT + ( C /2 + 1 ) c α . Condition on any such released polynomial and write K = ∣ H ( q ) ∣ K=|\mathcal{H}(q)| K = ∣ H ( q ) ∣ Lemma B.5 to the n / 2 n/2 n /2 S 2 S_2 S 2 1 − β / 2 1-\beta/2 1 − β /2
err P ( h ^ ) ≤ min h ∈ H ( q ) err P ( h ) + 2 log ( 8 K / β ) n + 4 log ( 4 K / β ) ε D P n . \operatorname{err}_P(\widehat{h})\le\min_{h\in\mathcal{H}(q)}\operatorname{err}_P(h)+2\sqrt{\frac{\log(8K/\beta)}{n}}+\frac{4\log(4K/\beta)}{\varepsilon_{\mathrm{DP}}n}. err P ( h ) ≤ h ∈ H ( q ) min err P ( h ) + 2 n log ( 8 K / β ) + ε DP n 4 log ( 4 K / β ) . Since log K = O ( α − 4 log ( 1 / α ) ) \log K = O\left(\alpha^{-4}\log(1/\alpha)\right) log K = O ( α − 4 log ( 1/ α ) ) K K K D p ≥ 1 D_p \ge1 D p ≥ 1 c α c\alpha c α
A union bound therefore gives, with probability at least 1 − β 1-\beta 1 − β
err P ( h ^ ) ≤ OPT + ( C / 2 + 2 ) c α ≤ OPT + α , \operatorname{err}_P(\hat{h}) \le\operatorname{OPT} +(C/2+2)c\alpha\le\operatorname{OPT}+\alpha, err P ( h ^ ) ≤ OPT + ( C /2 + 2 ) c α ≤ OPT + α , where the last inequality follows by taking c c c H ( q ) \mathcal{H}(q) H ( q )
Finally, we analyse the running time. Computing the clipped Hermite features of the samples in S 1 S_1 S 1 O ( n p D p ) O(npD_p) O ( n p D p ) O ( n D p ) O(nD_p) O ( n D p ) ∂ i h κ = κ i h κ − e i \partial_i h_\kappa=\sqrt{\kappa_i}\,h_{\kappa-e_i} ∂ i h κ = κ i h κ − e i M = E [ ∇ q ( X ) ∇ q ( X ) T ] M=\mathbb{E}[\nabla q(X)\nabla q(X)^{\mathsf{T}}] M = E [ ∇ q ( X ) ∇ q ( X ) T ] q q q O ( d 2 D p ) O(d^2D_p) O ( d 2 D p ) O ( d 3 ) O(d^3) O ( d 3 ) Lemma 3.2 , ∣ H ( q ) ∣ = exp ( O ( α − 4 log ( 1 / α ) ) ) |\mathcal{H}(q)|=\exp\left(O\left(\alpha^{-4}\log(1/\alpha)\right)\right) ∣ H ( q ) ∣ = exp ( O ( α − 4 log ( 1/ α ) ) ) poly ( d , 1 / α ) \operatorname{poly}(d,1/\alpha) poly ( d , 1/ α ) S 2 S_2 S 2 O ( n d ) O(nd) O ( n d ) O ( n d ∣ H ( q ) ∣ ) O(nd|\mathcal{H}(q)|) O ( n d ∣ H ( q ) ∣ ) d ≤ D p ≤ n d\le D_p\le n d ≤ D p ≤ n 1 / α ≤ n 1/\alpha\le n 1/ α ≤ n poly ( n ) ⋅ exp ( O ( α − 4 log ( 1 / α ) ) ) \operatorname{poly}(n)\cdot\exp\left(O\left(\alpha^{-4}\log(1/\alpha)\right)\right) poly ( n ) ⋅ exp ( O ( α − 4 log ( 1/ α ) ) )
Missing Details for Semi-Agnostic Learning
Algorithm 4 DP Semi-Agnostic Halfspace Learner
Require: Dataset D = ( ( x 1 , y 1 ) , … , ( x n , y n ) ) D=((x_1,y_1),\ldots,(x_n,y_n)) D = (( x 1 , y 1 ) , … , ( x n , y n )) ε D P , δ D P > 0 \varepsilon_{\mathrm{DP}},\delta_{\mathrm{DP}}>0 ε DP , δ DP > 0 α \alpha α β \beta β
Partition dataset for multiple runs and set parameters.
Set K ← C K log ( 1 / α ) K\leftarrow C_K\log(1/\alpha) K ← C K log ( 1/ α ) C K ≥ 1 C_K\ge1 C K ≥ 1
Let D v a l ⊂ D D_{\mathrm{val}}\subset D D val ⊂ D ∣ D v a l ∣ = O ( log ( K / β ) α 2 + log ( K / β ) α ε D P ) |D_{\mathrm{val}}|=O\left(\frac{\log(K/\beta)}{\alpha^2}+\frac{\log(K/\beta)}{\alpha\varepsilon_{\mathrm{DP}}}\right) ∣ D val ∣ = O ( α 2 l o g ( K / β ) + α ε DP l o g ( K / β ) ) D ′ ← D ∖ D v a l D'\leftarrow D\setminus D_{\mathrm{val}} D ′ ← D ∖ D val
Partition D ′ D' D ′ K K K D 1 , … , D K D^1,\ldots,D^K D 1 , … , D K
Set η 1 ← C η α \eta_1\leftarrow C_\eta\alpha η 1 ← C η α η k ← 2 k − 1 η 1 \eta_k\leftarrow2^{k-1}\eta_1 η k ← 2 k − 1 η 1 k ∈ [ K ] k\in[K] k ∈ [ K ] C η > 1 C_\eta>1 C η > 1
Run Algorithm 3 on each partition with appropriate parameters.
for k = 1 k=1 k = 1 K K K do
Set h k : = ( w ^ k , τ ^ k ) ← DPSAS ε D P , δ D P , η k ( D k ) h_k:=(\hat{w}_k,\hat{\tau}_k)\leftarrow\operatorname{DPSAS}_{\varepsilon_{\mathrm{DP}},\delta_{\mathrm{DP}},\eta_k}(D^k) h k := ( w ^ k , τ ^ k ) ← DPSAS ε DP , δ DP , η k ( D k )
end for
Run all h k h_k h k D v a l D_{\mathrm{val}} D val
Let H ← ( h 1 , … , h K ) H\leftarrow(h_1,\ldots,h_K) H ← ( h 1 , … , h K )
Define the score function Score ( D v a l , h k ) : = 1 ∣ D v a l ∣ ∑ ( x , y ) ∈ D v a l 1 { sign ( w ^ k ⋅ x + τ ^ k ) = y } \operatorname{Score}(D_{\mathrm{val}},h_k):=\frac{1}{|D_{\mathrm{val}}|}\sum_{(x,y)\in D_{\mathrm{val}}}\mathbf{1}\{\operatorname{sign}(\hat{w}_k\cdot x+\hat{\tau}_k)=y\} Score ( D val , h k ) := ∣ D val ∣ 1 ∑ ( x , y ) ∈ D val 1 { sign ( w ^ k ⋅ x + τ ^ k ) = y }
Set Δ ← 1 / ∣ D v a l ∣ \Delta\leftarrow1/|D_{\mathrm{val}}| Δ ← 1/∣ D val ∣
Set h ˉ ← ExpMech ε D P , H ( Score , Δ , D v a l ) \bar{h}\leftarrow\operatorname{ExpMech}_{\varepsilon_{\mathrm{DP}},H}(\operatorname{Score},\Delta,D_{\mathrm{val}}) h ˉ ← ExpMech ε DP , H ( Score , Δ , D val )
Return h ˉ \bar{h} h ˉ
Privacy
We first prove the privacy guarantees of Algorithm 4.
Proposition F.1. Algorithm 4 satisfies ( O ( ε D P ) , O ( δ D P ) ) (\mathcal{O}(\varepsilon_{\mathrm{DP}}), \mathcal{O}(\delta_{\mathrm{DP}})) ( O ( ε DP ) , O ( δ DP ))
Proof. We show that all different steps of Algorithm 4 that involve referencing the data using Algorithm 3 and the exponential mechanism satisfy DP, and then we apply parallel composition. However, for that, we first need to prove the privacy guarantees of Algorithm 3 by combination of using privacy guarantees of the standard DP mechanisms and parallel composition.
In Algorithm 3, when computing the threshold τ ^ \widehat{\tau} τ E ( x , y ) ∼ D [ y ] \mathbb{E}_{(x,y)\sim D}[y] E ( x , y ) ∼ D [ y ] 2 / m 0 2/m_0 2/ m 0 − 1 -1 − 1 1 1 1 2 / ε D P m 0 2/\varepsilon_{\mathrm{DP}}m_0 2/ ε DP m 0 ε D P \varepsilon_{\mathrm{DP}} ε DP
For computing the initial weight vector w ^ 0 \widehat{w}_0 w 0 x y xy x y D i n i t D_{\mathrm{init}} D init L L L ℓ 2 \ell_2 ℓ 2 y y y − 1 -1 − 1 1 1 1 ℓ 2 \ell_2 ℓ 2 2 L / m 0 2L/m_0 2 L / m 0 2 L 2 log ( 2 / δ D P ) / ε D P m 0 2L\sqrt{2\log(2/\delta_{\mathrm{DP}})}/\varepsilon_{\mathrm{DP}}m_0 2 L 2 log ( 2/ δ DP ) / ε DP m 0 ( ε D P , δ D P ) (\varepsilon_{\mathrm{DP}},\delta_{\mathrm{DP}}) ( ε DP , δ DP )
Next, in each iteration of the gradient descent procedure, we add Gaussian noise to the average gradient vector. From Claim 4.3 , we see that the average gradient is of the form
E ( x , y ) ∼ D [ − y 1 { ∣ w ⋅ x − b t ∣ ≤ a t } ∇ w w ⋅ x ∥ w ∥ ] . \mathbb{E}_{(x,y)\sim D}\left[-y1\{|w\cdot x-b_t|\leq a_t\}\nabla_w\frac{w\cdot x}{\|w\|}\right]. E ( x , y ) ∼ D [ − y 1 { ∣ w ⋅ x − b t ∣ ≤ a t } ∇ w ∥ w ∥ w ⋅ x ] . Therefore, the sensitivity of this average gradient is at most
2 ∥ ∇ w w ⋅ x ∥ w ∥ ∥ m 0 ≤ 2 ∥ x ∥ m 0 ≤ 2 L m 0 . \frac{2\left\|\nabla_w\frac{w\cdot x}{\|w\|}\right\|}{m_0}\leq\frac{2\|x\|}{m_0}\leq\frac{2L}{m_0}. m 0 2 ∇ w ∥ w ∥ w ⋅ x ≤ m 0 2∥ x ∥ ≤ m 0 2 L . This implies that adding Gaussian noise to the average scaled to 2 L 2 log ( 2 / δ D P ) / ε D P m 0 2L\sqrt{2\log(2/\delta_{\mathrm{DP}})}/\varepsilon_{\mathrm{DP}}m_0 2 L 2 log ( 2/ δ DP ) / ε DP m 0 ( ε D P , δ D P ) (\varepsilon_{\mathrm{DP}},\delta_{\mathrm{DP}}) ( ε DP , δ DP ) ( ε D P , δ D P ) (\varepsilon_{\mathrm{DP}},\delta_{\mathrm{DP}}) ( ε DP , δ DP )
Finally, applying parallel composition over the three steps again, we obtain ( ε D P , δ D P ) (\varepsilon_{\mathrm{DP}},\delta_{\mathrm{DP}}) ( ε DP , δ DP )
The guarantees of the exponential mechanism in Algorithm 4 imply ε D P \varepsilon_{\mathrm{DP}} ε DP 1 / ∣ D v a l ∣ 1/|D_{\mathrm{val}}| 1/∣ D val ∣
Relevant Assumptions and Regularity Conditions
For simplicity, we assume that the ambient dimension d d d
Assumption F.2 (Assumption on ambient dimension). We assume the following bound on the ambient dimension in terms of the error probability β ∈ ( 0 , 1 ) \beta\in(0,1) β ∈ ( 0 , 1 ) n ∈ N n\in\mathbb{N} n ∈ N
d ≥ 16 log ( n / β ) . d\geq16\log(n/\beta). d ≥ 16 log ( n / β ) . We do this for ease of notation, but we can make our calculations exact with a few extra lower order terms by not making this assumption.
Next, we state the Laurent-Massart inequality for concentration of high-dimensional Gaussians.
Lemma F.3 (Laurent-Massart inequality). Let X ∼ N ( 0 , I ) X\sim\mathcal{N}(0,\mathbb{I}) X ∼ N ( 0 , I ) d d d Σ = A T A \Sigma=A^{\mathsf{T}}A Σ = A T A A ∈ R d × d A\in\mathbb{R}^{d\times d} A ∈ R d × d t > 0 t>0 t > 0
Pr [ ∥ A X ∥ 2 2 > tr ( Σ ) + 2 tr ( Σ 2 ) t + 2 t ∥ Σ ∥ 2 ] ≤ e − t \Pr\left[\|AX\|_2^2>\operatorname{tr}(\Sigma)+2\sqrt{\operatorname{tr}(\Sigma^2)t}+2t\|\Sigma\|_2\right]\leq e^{-t} Pr [ ∥ A X ∥ 2 2 > tr ( Σ ) + 2 tr ( Σ 2 ) t + 2 t ∥Σ ∥ 2 ] ≤ e − t Pr [ ∥ A X ∥ 2 2 < tr ( Σ ) − 2 tr ( Σ 2 ) t ] ≤ e − t \Pr\left[\|AX\|_2^2<\operatorname{tr}(\Sigma)-2\sqrt{\operatorname{tr}(\Sigma^2)t}\right]\leq e^{-t} Pr [ ∥ A X ∥ 2 2 < tr ( Σ ) − 2 tr ( Σ 2 ) t ] ≤ e − t Using the above, we have the following deterministic regularity condition that we would assume throughout the proof.
Lemma F.4 (Concentration of high-dimensional Gaussians). Let X 1 , … , X n X_1,\ldots,X_n X 1 , … , X n d d d N ( 0 , I ) \mathcal{N}(0,I) N ( 0 , I ) β ∈ ( 0 , 1 ) \beta\in(0,1) β ∈ ( 0 , 1 ) 1 − β 1-\beta 1 − β
Pr [ ∀ i ∈ [ n ] : ∥ X i ∥ ∈ [ d / 2 , 2 d ] ] ≥ 1 − β \Pr\left[\forall i \in[n]: \lVert X_i\rVert\in[\sqrt{d}/2,2\sqrt{d}]\right] \ge1-\beta Pr [ ∀ i ∈ [ n ] : ∥ X i ∥ ∈ [ d /2 , 2 d ] ] ≥ 1 − β Proof. The proof follows by simply applying Assumption F.2, Lemma F.3, and the union bound over all n n n □ \square □
In Algorithm 3, we set the clipping parameter L = 2 d L=2\sqrt{d} L = 2 d ℓ 2 \ell_2 ℓ 2 L L L
Missing Proofs from Section 4
Proof of Claim 4.3. The proof of this claim is the same as that of Claim C.2 from [17 ] , except that the noisy gradient term has Gaussian noise added in the subspace orthogonal to w w w w w w w − λ ∇ w L ~ t ( w ) w-\lambda\nabla_w\widetilde{L}_t(w) w − λ ∇ w L t ( w ) 1 1 1 w w w □ \square □
Proof of Claim 4.5. In our algorithm w ~ 0 = w 0 + z 0 \widetilde{w}_0=w_0+z_0 w 0 = w 0 + z 0 z 0 ∼ N ( 0 , σ 2 I ) z_0\sim\mathcal{N}(0,\sigma^2I) z 0 ∼ N ( 0 , σ 2 I ) σ = 4 2 d log ( 2 / δ D P ) ε D P m 0 \sigma=\frac{4\sqrt{2d\log(2/\delta_{\mathrm{DP}})}}{\varepsilon_{\mathrm{DP}}m_0} σ = ε DP m 0 4 2 d l o g ( 2/ δ DP ) w 0 w_0 w 0 [17 ] in Algorithm 2. We know from the proof of Theorem 1.2 in Diakonikolas et al. [17 ] that w ∗ ⋅ w 0 > ω ( η ) w^*\cdot w_0>\omega(\eta) w ∗ ⋅ w 0 > ω ( η ) w ∗ ⋅ z 0 w^*\cdot z_0 w ∗ ⋅ z 0 w ∗ ⋅ w ~ 0 > 0 ⇒ w ∗ ⋅ w ^ 0 > 0 w^*\cdot\widetilde{w}_0>0\Rightarrow w^*\cdot\widehat{w}_0>0 w ∗ ⋅ w 0 > 0 ⇒ w ∗ ⋅ w 0 > 0 w ∗ w^* w ∗ w ∗ ⋅ z 0 ∼ N ( 0 , σ 2 ) w^*\cdot z_0\sim\mathcal{N}(0,\sigma^2) w ∗ ⋅ z 0 ∼ N ( 0 , σ 2 ) 1 − O ( β ) 1-O(\beta) 1 − O ( β )
∣ w ∗ ⋅ z 0 ∣ ≤ O ( d log ( 1 / δ D P ) log ( 1 / β ) ε D P m 0 ) < O ( η ) \lvert w^*\cdot z_0\rvert\le O\left(\frac{\sqrt{d\log(1/\delta_{\mathrm{DP}})\log(1/\beta)}}{\varepsilon_{\mathrm{DP}}m_0}\right)<O(\eta) ∣ w ∗ ⋅ z 0 ∣ ≤ O ( ε DP m 0 d log ( 1/ δ DP ) log ( 1/ β ) ) < O ( η ) by plugging in our bound on the sample complexity. □ \square □
