Privacy for Free in Efficient Agnostic Halfspace Learning

Privacy for Free in Efficient Agnostic Halfspace Learning Giorgio Racca, Amartya Sanyal, and Vikrant Singhal

arXiv:2611.05208v1 [cs.LG] 3 Nov 2026

Department of Computer Science, University of Copenhagen {g.racca,amsa,vikrant.singhal}@di.ku.dk Abstract We provide the first computationally efficient, differentially private algorithms for agnostically learning halfspaces. In particular, we study three different settings of agnostic learning: improper learning under Gaussian and log-concave marginals; proper learning under Gaussian marginals; and semi-agnostic learning under Gaussian marginals. In all three aforementioned settings, the added cost in the sample complexity due to privacy matches the respective non-private sample complexity, implying that we get privacy for free.

1

Introduction

Learning halfspaces is a classical problem in learning theory. A halfspace is specified by a weight vector w ∈ Rd and a threshold t ∈ R, and classifies a point x ∈ Rd according to sign(⟨w, x⟩ + t). We write P for the distribution of labeled examples and µ = PX for its input marginal. In classical realizable PAC learning, the distribution P is assumed to be linearly separable and the learner is required to output a classifier h with errP (h) ≤ α for any accuracy parameter α ∈ (0, 1). In the agnostic setting, the labels in the dataset may be arbitrary. Thus, the guarantee is relaxed to requiring the learner to output a classifier h with error errP (h) ≤ OPT +α, where OPT is the minimum error achievable by a halfspace under P . This setting allows the data to be noisy or imperfectly separable by a linear decision boundary. Differential privacy (DP) (Dwork et al., 2006) 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, 2023). 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. (2008) provided the first algorithm for agnostic learning of halfspaces whose runtime is polynomial in the dimension for 4 every fixed accuracy. For Gaussian marginals, their complexity scales as dO(1/α ) which was later 2 improved to dO(1/α ) by Diakonikolas et al. (2010). 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) parameters. For Gaussian marginals, Diakonikolas et al. (2021a) provided the first agnostic proper learner for halfspaces Authors are listed in alphabetical order.

1

Marginal

Learner

Error

Gaussian

Improper

OPT +α

Log-concave

Improper

OPT +α

Gaussian

Proper

OPT +α

Gaussian

Proper

C ·OPT +α

e (·) Sample complexity O DG DG + α2 εDP α DL DL + 2 α εDP α3/2 DG 1 DG 1 + + + α2 εDP α α6 εDP α5 d d + 2 α εDP α

Table 1: The rows correspond, respectively, to Theorem 2.1, Theorem D.1, Theorem 3.1, and Theorem 4.1. 2 Here, DG ≍ dO(1/α ) and DL ≍ dexp(O(1/α)) match known rates in the non-private setting (Diakonikolas e suppresses polylogarithmic factors. et al., 2010; Kalai et al., 2008), and O

with somewhat comparable statistical and computational complexity. For DP agnostic learning, Kasiviswanathan et al. (2008) provided the first agnostic private learners for finite classes with sample complexity scaling logarithmically in the size of the hypothesis class. Alon et al. (2020) 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. (2019) provided efficient private agnostic learners, but over infinite domains such as Rd , distribution-free private learning of halfspaces is information-theoretically impossible even in the realisable setting due to their infinite Littlestone dimension (Bun et al., 2015; Alon et al., 2019). Distributional assumptions on the marginal µ are therefore essential for both privacy and computational efficiency. Given the non-private agnostic learners under structured marginals (Kalai et al., 2008; Diakonikolas et al., 2021a), our goal in this work is to obtain matching statistical and computational complexities under differential privacy. 2 However, even under Gaussian marginals, the dO(1/α ) dependence on statistical and therefore computational complexity is likely unavoidable for approaches using polynomial regression due to known SQ lower bounds (Diakonikolas et al., 2021b; Goel et al., 2020). A natural relaxation for the problem is semi-agnostic proper learning, which allows halfspaces h with errP (h) ≤ C · OPT +α, where C is a known universal constant. Non-private learners, under Gaussian marginals, can achieve this guarantee in time polynomial in both d and 1/α simultaneously (Diakonikolas et al., 2022). This raises the natural question of whether the polynomial dependence on d, 1/α can be maintained for semi-agnostic learning under privacy. Together, these lead to the following question: 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 (εDP , δDP )-DP guarantees with respect to the dataset, and their error guarantees hold with high probability. Additionally, all our algorithms e (·) hides factors run in time polynomial in the sample size for every fixed accuracy. Throughout, O polylogarithmic in 1/α, 1/β, 1/εDP , and 1/δDP . Agnostic Improper learning. Our first result in Section 2 gives a private improper agnostic learner under the standard Gaussian marginal. The algorithm relies on private polynomial L1 2

regression using clipped Hermite features of degree O 1/α2 . A key step is to control the effect of clipping on the error and then convert the expected excess-loss bound to a high-probability one. This achieves an error at most OPT +α with high probability using sample complexity     d+p e Dp + Dp where D = (1) n=O p α2 αεDP p 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 D, we extend this approach to known log-concave marginals using p = exp (O (1/α)), incurring an additional α−1/2 factor in the privacy term of Equation (1) (as shown in Table 1). Agnostic Proper learning. In Section 3, we give a proper DP learner for halfspaces under Gaussian marginals with error at most OPT +α. As shown in Table 1, its sample size is   Dp Dp 1 1 e n=O + + + (2) α2 αεDP α6 εDP α5 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 which contains a halfspace with error close to OPT. Finally, creating a discrete cover of halfspaces supported on this space, and using the exponential mechanism leads to the final output. This subspace creation, discretisation, and exponential mechanism costs the last two terms in Equation (2). Semi-Agnostic Proper learning. In Section 4, we give a proper learner under Gaussian marginals with error at most O (OPT) + α. The sample complexity, as described in Table 1, is   d d e + n=O . (3) α2 αεDP The learner works by utilizing a privatized semi-agnostic learner from Diakonikolas et al. (2022) that provides the error guarantee of O (η), where η ≥ OPT is known a priori. However, since we do not know what η is, we search over a small candidate set of η’s by using the said privatized learner, and then pick the best hypothesis using the exponential mechanism on a fresh validation set. 2

2

Remark 1. Note that dO(1/α ) · 1/αc = dO(1/α ) . We fix p for both improper and proper agnostic settings, such that it is the smallest p ∈ N guaranteeing the existence of the polynomial bases that accurately approximate halfspaces. In other words, we use the same p as required by the known non-private counterparts of our algorithms (Diakonikolas et al., 2010; Pesenti et al., 2026). Thus, whatever exponent d has in the sample complexity of the respective non-private learners, we achieve that, while keeping the additional cost in poly (1/α) explicitly outside the exponent of 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 εDP or δDP ) for each of the three Gaussian settings above when εDP = Ω(α). In that sense, we get privacy for free. This is commonly observed in DP statistical estimation (see, e.g., Karwa and Vadhan (2018); Kamath et al. (2019)), and such sample complexity is often tight for various problems, such as mean and covariance estimation (Kamath et al., 2022). Notation. We denote the class of halfspaces by C. For a classifier h : Rd → {±1}, its population error is errP (h) := P(X,Y )∼P [h(X) ̸= Y ] and, given a sample S, its empirical error is err c S (h) := 3

P |S|−1 (x,y)∈S 1{h(x) ̸= y}. Unless stated otherwise, the input marginal is µ = N (0, Id ); the only exception is our result for log-concave marginals (Theorem D.1). We define OPT := inf c∈C errP (c). For a function g : Rd → R and q ∈ {1, 2}, we write ∥g∥Lq (µ) := (EX∼µ [|g(X)|q ])1/q . The formal definition of differential privacy and associated properties are given in Appendix B.2.

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 L1 regression algorithm of Kalai et al. (2008), 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 L1 loss by at most the probability of clipping, which we bound in Lemma C.2. These two properties allow us to fit the coefficients using private convex optimisation (Kulkarni et al., 2021). We then repeat the DP optimisation step on independent samples to boost its success probability and use the exponential mechanism (McSherry and Talwar, 2007) 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 α, β, εDP , δDP
∈ (0, 1/2]. Set p = ⌈Cα−2 ⌉ for a sufficiently large universal constant C > 0, and Dp = d+p p . Suppose −5 d ≥ Cdim α , where Cdim > 0 is a sufficiently large universal constant. Let P be any distribution on Rd × {±1} with marginal µ = N (0, Id ). Then Algorithm 1 is (εDP , δDP )-DP. Given   Dp Dp e n=O + α2 εDP α i.i.d. samples from P , it returns a classifier h satisfying errP (h) ≤ OPT +α with probability at least 1 − β. The algorithm runs in time poly(n). The two terms in the sample complexity arise from statistical estimation and private optimization, respectively. When εDP ≥ α, the privacy term is absorbed into
the statistical term, so privacy is free e Dp /α2 matches the dependence on d of known up to logarithmic factors. The sample complexity O algorithms for non-private agnostic learning of halfspaces under Gaussian marginals (Diakonikolas 2 et al., 2010). Moreover, the d1/α cost is necessary in the statistical query model, even without privacy (Diakonikolas et al., 2021b). In Appendix D, we extend the method to log-concave marginals and establish an analogous guarantee.

2.1

The Algorithm

We represent each input x by its feature vector ψp (x) = (hκ (x))|κ|≤p ∈ RDp of normalized Hermite polynomials (O’Donnell, 2014) of degree at most p. The degree p = ⌈Cα−2 ⌉ suffices to approximate every halfspace in L1 (µ) up to error α (Diakonikolas et al., 2010). To bound the influence of any single example and makepthe regression loss Lipschitz in its coefficients, we clip the feature vectors to norm at most T = 2 Dp : ψ̄p,T (x) := T ψp (x)/ max{T, ∥ψp (x)∥2 }. Then, by Lemma C.2, the

4

Algorithm 1 Private polynomial L1 regression Require: Sample S of sizep n; parameters α, β, εDP , δDP . 1: Set p = ⌈Cα−2 ⌉, T = 2 Dp , k = ⌈log2 (2/β)⌉, M = ⌈C/α⌉, and n0 , m as in (14b)–(14c). 2: Partition S into training blocks S1 , . . . , Sk of size n0 and a validation block Sval of size m. 3: for j = 1, . . . , k do b S over B Dp . 4: v̂j ← output of the (εDP , δDP )-DP optimizer on L j 2 5: end for
6: For (j, ℓ) ∈ [k] × [M ], set tℓ = −1 + (2ℓ − 1)/M and hj,ℓ (x) = sign ⟨v̂j , ψ̄p,T (x)⟩ − tℓ .
7: Sample (ȷ̂, ℓ̂) with probability proportional to exp −εDP m err c Sval (hj,ℓ )/2 . 8: return hȷ̂,ℓ̂ . clipping probability is at most O (α). Given a sample S, the regression step approximately minimizes the empirical L1 loss X b S (v) = 1 ⟨v, ψ̄p,T (Xi )⟩ − Yi (4) L |S| (Xi ,Yi )∈S

D over the unit ball B2 p = {v ∈ RDp : ∥v∥2 ≤ 1}. This loss is convex and T -Lipschitz in v, so we apply

the private convex ERM algorithm of Kulkarni et al. (2021), restated in Lemma B.4. A potential alternative approach is to implement polynomial regression using statistical queries (Kearns, 1998) and then simulate these queries privately (Kasiviswanathan et al., 2008). 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 training blocks of size n0 and a validation block of size m. It runs the private optimizer on each training block to obtain coefficient vectors v̂1 , . . . , v̂k with scores v̂j , ψ̄p,T (x) , and then thresholds them at M evenly spaced points in [−1, 1] to produce kM candidate classifiers. Finally, it selects one candidate using the exponential mechanism (McSherry and Talwar, 2007), scoring each candidate by its fraction err c Sval (·) of misclassified validation examples. Repeating the regression step on k blocks boosts its success probability, and the validation step chooses the coefficient vector and the threshold jointly.

2.2

Analysis

In this section, we outline the accuracy analysis; the full accuracy and privacy proofs are deferred to Appendix C. Define the population loss LP (v) := E(X,Y )∼P ⟨v, ψ̄p,T (X)⟩ − Y and its minimum over the unit ball L⋆ := min∥v∥2 ≤1 LP (v). For a universal constant c ∈ (0, 1/4], we first compare the minimum regression loss with the error of the best halfspace: L⋆ ≤ 2 OPT +2cα.

(5)

We then show that the algorithm returns a classifier whose error satisfies errP (h) ≤ 21 L⋆ + 3cα

(6)

with probability at least 1 − β. Together, these give errP (h) ≤ OPT +4cα ≤ OPT +α with the same probability. 5

We begin with Equation (5), which compares the clipped regression problem with the best halfspace. Fix f ∈ C. By Lemma B.10 (Diakonikolas et al., 2010; Pesenti et al., 2026), there is a polynomial q = ⟨vq , ψp ⟩ with ∥vq ∥2 ≤ 1 and ∥q − f ∥L1 (µ) ≤ cα. Let s(x) := T / max{T, ∥ψp (x)∥2 }, so that ψ̄p,T (x) = s(x)ψp (x). Since ⟨vq , ψ̄p,T (x)⟩ = s(x)q(x) with 0 < s(x) ≤ 1, and |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). The first inequality follows by adding and subtracting s(x)y and applying the triangle inequality. Taking expectations gives LP (vq ) ≤ 2 errP (f ) + ∥q − f ∥L1 (µ) + Eµ [1 − s(X)]. The three terms are the classification error of f , the polynomial approximation error, and the clipping bias. Since 1−s(x) ≤ 1{∥ψp (x)∥2 > T }, Lemma C.2 bounds the last term by cα. Clipping thus enters only through its probability. The approximation error is also at most cα, so LP (vq ) ≤ 2 errP (f ) + 2cα. As ∥vq ∥2 ≤ 1, we have L⋆ ≤ LP (vq ), and taking the infimum over f gives (5). For Equation (6), we first show that at least one of the k regression runs is nearly optimal. The loss is convex and T -Lipschitz and thus for each training block, Lemma B.4 from Kulkarni et al. (2021) bounds the expected optimization error. Then, standard Rademacher complexity bound for linear predictors under L1 loss (Lemma B.7), applied with Eµ ∥ψ̄p,T (X)∥22 ≤ Dp , bounds the expected deviation between the empirical and population losses. We choose n0 so that these two contributions sum to at most cα (see (14b)), giving   E LP (v̂j ) − L⋆ ≤ cα, where the expectation is over Sj and the optimizer’s randomness. Since v̂j lies in the unit ball, its excess loss LP (v̂j ) − L⋆ is non-negative. Markov’s inequality therefore gives LP (v̂j ) ≤ L⋆ + 2cα with probability at least 1/2. The k runs are independent, so with probability at least 1 − 2−k ≥ 1 − β/2, some run j ⋆ satisfies this bound. We next show that thresholding this run yields a good candidate classifier. For any fixed regression output v̂j , a uniformly random threshold τ ∈ [−1, 1] gives expected classification error at most LP (v̂j )/2, where the expectation is over τ (Kalai et al., 2008, see also Fact B.6). Rounding τ to the midpoint of its grid interval makes it uniform over the M grid thresholds and increases the expected classification error by at most 1/(2M ) ≤ cα. Thus, at least one grid threshold has error no larger than this average. On the event that some run j ⋆ satisfies this loss bound, we have that vj ⋆ ) + cα ≤ 12 L⋆ + 2cα. min errP (hj,ℓ ) ≤ 12 LP (b j,ℓ

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 Sval to select among the kM candidate classifiers. By Lemma B.5, with m as in (14c), the selected classifier has error at most cα above the best candidate with probability at least 1 − β/2. A union bound over the training and validation failure events proves Equation (6). p Finally, since T Dp = 2Dp and k = O (log(1/β)), the choices of n0 and m give the sample bound of Theorem 2.1. Computing the features, running the k private optimizers, and evaluating the kM candidates on Sval take poly(n) arithmetic operations. The detailed proof, along with privacy and runtime calculations appear in Appendix C.

6

p Remark 3. The dimension assumption in Theorem 2.1 allows us to use the clipping radius T = 2 Dp . p To obtain a guarantee in every dimension, we instead take T = Dp /(cα) for a sufficiently small universal constant c > 0. Orthonormality and Markov’s inequality give Pr(∥ψp (X)∥2 > T ) ≤ µ

Dp = cα. T2

(7)

Replacing Lemma C.2 with this bound, the same analysis (see Appendix C) establishes the learning guarantee of Theorem 2.1 for every d ≥ 1. The statistical term in the sample complexity remains unchanged, and the privacy term acquires an additional α−1/2 factor.

3

Private Proper Agnostic Learning

The agnostic learner in Section 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 Rd . A halfspace requires only O (d) 2 parameters, compared to dO(1/α ) coefficients for the improper hypothesis, and is faster to evaluate on a point and also easier to interpret. We will adapt the low-rank subspace reduction of Diakonikolas et al. (2021a) 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, 2007) to privately select a halfspace from it. Our main result is stated below. Theorem 3.1 (DP proper agnostic learner). Let α, β, δDP ∈ (0, 1/2) and εDP ∈ (0, 1). Set p = ⌈C0 /(cα)2 ⌉ for a sufficiently 0 and a sufficiently small universal
large universal constant C0 >−5 constant c > 0, let Dp = d+p , and suppose that d ≥ C α for a sufficiently large universal dim p d constant Cdim > 0. Let P be any distribution on R × {±1} with marginal µ = N (0, Id ). Then Algorithm 2 is (εDP , δDP )-DP and, given   1 e Dp + Dp + 1 + n=O α2 εDP α α6 εDP α5 i.i.d. samples from P , returns a halfspace h ∈ C satisfying errP (h) ≤
OPT +α with probability at least 1 − β. The algorithm runs in time 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 E. We use a strengthened version of the of Diakonikolas et al. (2021a), reducing the

subspace 2reduction
4 polynomial
degree from O 1/α to O 1/α . This reduces the subspace dimension from O 1/α6 to O 1/α4 and yields a smaller finite class for the exponential mechanism. We also extend the reduction to labels in [−1, 1]. Lemma 3.2 states
this guarantee. Thus, our sample bound has the same d+p dependence on the dimension as non-private improper p agnostic learning under Gaussian marginals (Diakonikolas et al., 2010), while returning a halfspace. When εDP ≥ α, the privacy terms are absorbed into the statistical terms Dp /α2 + 1/α6 , up to logarithmic factors. In this regime,

privacy comes essentially for free. −4 The factor exp O α log(1/α) in the running time arises from constructing and searching a finite cover of halfspaces of at most this size, so the running time is polynomial in n for every fixed accuracy α. The non-private proper learner of Diakonikolas et al. (2021a) also searches such a cover, and its running time likewise includes a term exponential in poly(1/α).

7

Lemma 3.2. There exist universal constants C0 , C, c0 > 0 such that the following holds. Let  (X,−2U) have any joint distribution with X ∼ N (0, Id ) and |U | ≤ 1. Fix α ∈ (0, 1/2), and set p = C0 α . Let Pp denote the space of polynomials on Rd of degree at most p. Suppose that q ∈ Pp satisfies h i h i E (U − q(X))2 ≤ inf E (U − Q(X))2 + c20 α2 . (8) Q∈Pp

Using just q and α, we can construct a finite class of halfspaces H(q) ⊆ C satisfying log |H(q)| ≤ Cα−4 log(1/α), such that, for every f ∈ C, there exists h ∈ H(q) with E [U (f (X) − h(X))] ≤ Cα. The proof is stated in Appendix E. A natural idea is to obtain the polynomial q from our private improper learner in Theorem 2.1. However, the coefficients vbj obtained in each regression run of Algorithm 1 only satisfy the following L1 guarantee: E(X,Y )∼P

vbj , ψ̄p,T (X) − Y ≤ min E(X,Y )∼P ∥v∥2 ≤1

v, ψ̄p,T (X) − Y + O (α) ,

which does not imply the excess squared-loss bound in Equation (8). Moreover, the function vbj , ψ̄p,T (X) is a linear combination of clipped Hermite features ψ̄p,T (X) and therefore need not be a polynomial as required in Lemma 3.2. We therefore need a different private polynomial construction that directly controls excess squared loss.

3.1

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 features. Write m = E [Y ψp (X)] for the original correlation vector and  and the Hermite  mT = E Y ψ̄p,T (X) for the correlation vector computed using clipped features. Then ∥m − mT ∥2 = sup |E [Y (1 − s(X)) ⟨v, ψp (X)⟩]| ∥v∥2 =1

r h i r   √
2 ≤ E (1 − s(X)) ≤ Pr ∥ψp (X)∥2 > T = O α , µ

where the first inequality uses Cauchy–Schwarz and orthonormality of Hermite functions, and the last inequality uses O (α) bound on the clipping probability from Section 2 (see Lemma C.2). Thus, √ a O ( α) bound on the difference between the original and clipped
correlations only gives an O (α) bound on excess squared loss, whereas Lemma 3.2 requires an O α2 excess squared loss. Therefore, we need our estimated coefficients to be within O (α) of the optimal coefficients. We show that this can be achieved the polynomial for the clipped labels h by constructing i 2 U = s(X)Y , using the loss Ls (Q) = E (U − Q(X)) . Note that |U | = |s(X)Y | ≤ 1. Then, the   corresponding correlation vector is mT = E Y ψ̄p,T (X) = E [U ψp (X)] . By orthonormality of the Hermite basis, mT is exactly the coefficient vector minimizing Ls over Pp . Lemma 3.3. Let X ∼ N (0, Id ), let |U | ≤ 1, and write mT = E [U ψp (X)]. The polynomial qmT (x) = ⟨mT , ψp (x)⟩ is the unique minimizer of Ls over Pp . Dp Proof of Lemma 3.3. Every polynomial in Pp can be written as qw (x) =   ⟨w, ψp (x)⟩ for some w ∈ R . ⊤ Using orthonormality of the Hermite basis, we get E ψp (X)ψp (X) = IDp . Then, h i   Ls (qw ) = E (U − qw (X))2 = E U 2 − 2 ⟨w, mT ⟩ + ∥w∥22 (9)   = E U 2 − ∥mT ∥22 + ∥w − mT ∥22 .

8

Algorithm 2 Private proper learning of Gaussian halfspaces Require: Sample S of size n, accuracy α, failurepprobability β, and privacy parameters (εDP , δDP ). 
d+p 1: Set p = C0 /(cα)2 , Dp = , and T = 2 Dp , where c > 0 is a sufficiently small universal p constant. 2: Split S into disjoint blocks S1 , S2 of size n/2 each, independently of the sample values. p 4T 2 log(1.25/δDP ) 2 3: Draw Z ∼ N (0, σ IDp ) with σ = . εDP !n X 2 Yi ψ̄p,T (Xi ) + Z and set q(x) ← ⟨m, e ψp (x)⟩. 4: m e ← ProjB Dp n 2 (Xi ,Yi )∈S1

5: Construct H(q) using the construction in Lemma 3.2 with accuracy cα.

! 6: Sample h ∈ H(q) with probability proportional to exp

−(εDP /2)

X

1 {h(Xi ) ̸= Yi } .

(Xi ,Yi )∈S2

7: return h.

The first two terms do not depend on w. Thus, the loss is minimized uniquely at w = mT . Thus, our goal is to estimate mT privately. For any estimate m, e using Equation (9), we get that the polynomial qm (x) = ⟨ m, e ψ (x)⟩ satisfies p e Ls (qm e − mT ∥22 . e ) − inf Ls (Q) = ∥m Q∈Pp

It therefore suffices to estimate a coefficient vector m e such that ∥m e − mT ∥2 ≤ c0 cα for some constant c0 > 0. The regression step in Algorithm 2 (Step 4) estimates these correlations using the Gaussian mechanism and projects the estimate onto the coefficient unit ball. Since ∥mT ∥2 ≤ 1, projection cannot increase the estimation error. The following lemma gives the guarantee for the resulting polynomial. Lemma 3.4. Let α, β, δDP ∈ (0, 1/2) and εDP ∈ (0, 1]. Let q be the polynomial constructed in Step 4 of Algorithm 2, using the n/2 independent samples in S1 . Its release
is (εDP , δDP )-differentially e Dp /α2 + Dp /(εDP α) , then, with probability at private, and ∥q∥L2 (µ) ≤ 1 on every run. If n/2 = Ω least 1 − β/2, Ls (q) ≤ inf Ls (Q) + c20 c2 α2 . (10) Q∈Pp

The proof is given in Appendix E.

3.2

Constructing the finite set of halfspaces

We now use the polynomial q computed in Step 4 of Algorithm 2 to construct a finite class of halfspaces. On the event in Lemma 3.4, this polynomial satisfies the squared-loss condition (Equation (8)) of Lemma 3.2 with accuracy cα. We therefore apply Lemma 3.2 in Step 5 to construct H(q). The full algorithm and proof are given in Appendix E. The algorithm follows the subspace and discretization construction of Diakonikolas et al. (2021a). Specifically, we compute h i M = EX∼N (0,Id ) ∇q(X)∇q(X)⊤ and take V to be the span of its eigenvectors
with eigenvalues at least c2 α2 /C0 . They show that the resulting subspace has dimension O α−4 . Discretizing unit normal vectors in V gives a finite 9

class of halfspaces satisfying log |H(q)| = O α−4 log(1/α) . All these operations use only q and the known Gaussian marginal, so Algorithm 2 preserves DP by post-processing (Lemma B.3). Lemma 3.4 guarantees the polynomial q has small excess squared loss for the clipped labels U . Lemma 3.5 next translates this guarantee into classification error for the original labels. Lemma 3.5. Suppose that d ≥ Cdim α−5 for a sufficiently large universal constant Cdim and C is the constant in Lemma 3.2. Let q and H(q) be constructed by Algorithm 2. If q satisfies Equation (10), min errP (h) ≤ OPT +(C/2 + 1)cα.

h∈H(q)

Proof. On the event in the lemma, Lemma 3.2 gives, for every halfspace f ∈ C, an h ∈ H(q) satisfying E [U (f (X) − h(X))] ≤ Ccα. Since errP (h) − errP (f ) = 21 E [Y (f (X) − h(X))] ≤ 12 E [U (f (X) − h(X))] + E [1 − s(X)] , it remains to bound the last term. As s(X) = 1 p outside the clipping event, Lemma C.2 gives   E [1 − s(X)] ≤ P ∥ψp (X)∥2 > T ≤ cα when T = 2 Dp and d ≥ 2p2 /(cα). Thus, H(q) contains a halfspace with error at most OPT +(C/2 + 1)cα.

3.3

Selecting the best halfspace

Finally, Algorithm 2 selects a halfspace from H(q) using the exponential mechanism, with scores equal to the negative empirical errors on S2 . These errors are measured against the original labels Y . Conditional on the released polynomial, H(q) is fixed and independent of S2 . By Lemma B.5, this selection adds at most cα error with probability at least 1 − β/2, provided   
1 1 −4 n = Ω α log(1/α) + log(1/β) + . (11) α2 εDP α Combining this with Lemma 3.4 and taking c sufficiently small gives error at most OPT +α, with probability at least 1 − β. The private regression step uses S1 , while the exponential mechanism uses the disjoint block S2 , each of size n/2. Therefore, post-processing and parallel composition give (εDP , δDP )-privacy for Algorithm 2. 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, so it is proper. Lemma 3.4 guarantees that Algorithm 2 outputs a polynomial satisfying Equation (8) in Lemma 3.2 with accuracy cα, with
probability at least 1 − β/2. Thus, Step 5 constructs H(q) from a subspace of dimension O α−4 . Lemma 3.5 ensures that it contains a halfspace with error at most OPT +(C/2 + 1)cα. When the sample size n satisfies Equation (11), the exponential mechanism adds at most cα error with probability at least 1 − β/2 by Lemma B.5; a union bound and sufficiently small c give the claimed accuracy. Adding the validation sample cost to the sample cost in Lemma 3.4 gives the stated sample complexity. For privacy, note that Step 4 is (εDP , δDP )-DP by Lemma 3.4, Step 5 is post-processing, and Step 6 is εDP -DP on S2 by exponential mechanism, conditioned on the released polynomial. Since S1 and S2 are disjoint, parallel composition makes the entire algorithm (εDP , δDP )-DP.

10

4

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 and 1/α, rather than exponential in 1/α as in 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. (2022) as a subroutine. Roughly speaking, given an upper bound η ≥ OPT, this private subroutine (Algorithm 3) returns a halfspace with error O (η). Then, our main algorithm (Algorithm 4) searches over a small set of candidate values of η and selects a hypothesis using the exponential mechanism. We state our main result below and defer the privacy proof and technical details of the accuracy analysis to Appendix F. Theorem 4.1 (DP semi-agnostic proper learner). Let α, β, εDP , δDP ∈ (0, 1). Let P be any distribution on Rd × {±1} with marginal µ = N (0, Id ). Then Algorithm 4 is (εDP , δDP )-DP and, given   d d e + n=O α2 εDP α i.i.d. samples from P , where d ≥ 16 log(n/β), it returns a halfspace h ∈ C satisfying errP (h) ≤ C · OPT +α with probability at least 1 − β, where C > 0 is a universal constant. The algorithm runs in time poly(n). We make the above assumption on d (Appendix F.2) for ease of exposition. √ p It can be removed by setting the clipping parameter L in Algorithm 3 to a tighter bound of O( d+ log(n/β)), thus simply introducing more polylog terms in the sample complexity that we already omit in our presentation.

4.1

The Algorithm

We first describe the subroutine in Algorithm 3, which takes a known upper bound η ≥ OPT and performs gradient updates using a ramp loss. For a > 0 and b ∈ R, define   if z ≤ b − a, 0 ra,b (z) = z − b + a if b − a < z < b + a, (12)   2a if z ≥ b + a. Algorithm 3 follows Algorithms 1 and 2 from Diakonikolas et al. (2022), 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 τ and the initial weight vector ŵ0 . Diakonikolas et al. (2022) first estimate the threshold from the average of the labels in Dτ , using the inverse Gaussian CDF. We privatise this average by adding Laplace noise, obtaining the threshold estimate τ̂ in Algorithm 3. Next, we compute the initial weight vector ŵ0 by adding Gaussian noise to the average of xy over Dinit in Algorithm 3. The algorithm then keeps τ̂ fixed, and performs gradient descent using the ramp function in Equation (12) and the private threshold τ̂ , with a fresh block Dt in each iteration. Algorithm 3 adds Gaussian noise to each empirical gradient before performing the gradient update. With these modifications, Algorithm 3 privately returns a hypothesis with population classification error O (η) whenever η ≥ OPT, as shown in Proposition 4.2. Since OPT is unknown, Algorithm 4 tries a geometric grid of candidate values η1 , . . . , ηK . For each ηk , it runs Algorithm 3 on a separate subset of the data to obtain a hypothesis hk . The grid is chosen such that at least one of these hypotheses has error O (OPT +α) with high probability. The algorithm then uses the exponential mechanism on a separate validation set Dval to select a hypothesis whose empirical classification error is close to the smallest among these candidates. 11

Algorithm 3 DP Semi-Agnostic Subroutine DPSAS Require: Dataset D of n0 labelled examples, privacy parameters εDP , δDP > 0, and error parameter η. Partition Dataset and Clip for DP 1: s ← Θ(1/ log3/2 (1/η)) and T ← Θ(log4 (1/η)). 2: Partition √ D into Dinit , Dτ , D0 , . . . , DT −1 , each of size m0 ← |D|/(T + 2). 3: L ← 2

d and clip each feature vector in D to have norm at most L. Privately computing threshold τ̂ .

4: κ ← Cη for a universal constant C and ŷ ← E(x,y)∼Dτ [y] + zτ ,

  where zτ ∼ Lap εDP2m0 .  h i1−κ  1+ŷ −1 5: τ̂ ← Φ clip 2 . κ

Privately computing initial weight ŵ0 . 6: w̃0 ← E(x,y)∼Dinit [xy] + z0 , 2L ∼ N (0, σ 2 I) and σ ←

√

2 log(2/δ

)

DP . where z0 εDP m0 w̃0 d−1 uniformly at random. 7: ŵ0 ← ∥w̃ ∥ if ∥w̃0 ∥ ̸= 0, otherwise ŵ0 ∼ S 0 Run DP online gradient descent. 2

8: λ ← eτ̂ /2 s and B ← S d−1 . 9: for t = 0 to T − 1 do 10: 11:

t ϕt ← (π/2)(1 − s2 /64) h , at ← sin(ϕ  it ), and bt ← −τ̂ cos(ϕt ). w·x L̂t (w) ← E(x,y)∼Dt −rat ,bt ∥w∥ y .

û ← ŵt − λ(∇L̂t (ŵt ) + zt+1 ) and ŵt+1 ← projB (û), where zt+1 ∼ N (0, σ 2 (I − ŵt ŵt⊤ )). 13: end for 14: Return ŵT , τ̂ . 12:

4.2

Accuracy

A major component for proving the utility for Algorithm 4 is proving the accuracy guarantees for Algorithm 3. Note that by construction, α ≤ ηk for all k ∈ [K]. In the presentation for the rest of Section 4.2, we will omit the subscript from ηk to refer to the parameter η in Algorithm 3. We write m0 for the number of examples in each of the T + 2 disjoint blocks used by the algorithm; the total sample size for one run is n0 = (T + 2)m0 . Proposition 4.2. Let η ∈ (0, 1/2) and β, εDP , δDP ∈ (0, 1). Let P be any distribution on Rd × {±1} with marginal µ = N (0, Id ) and OPT ≤ η. Then Algorithm 3 is (εDP , δDP )-DP and, given   d d e m0 = O + η 2 εDP η i.i.d. samples from P in each of its blocks, where d ≥ 16 log(n0 /β) for the total sample size n0 , returns a halfspace h ∈ C satisfying errP (h) ≤ Cη with probability at least 1 − β, where C > 0 is a universal constant. We follow the utility analysis of Diakonikolas et al. (2022), with modifications to account for the noise added for privacy. Their analysis starts with a weight vector that makes an angle less than π/2 12

with the optimal halfspace w⋆ . In each iteration, the gradient update reduces this angle until the weight vector is sufficiently close to w⋆ to give the desired error guarantee. We first analyse these updates assuming that our private initialization satisfies this starting condition and that replacing the optimal threshold by our private estimate preserves a small classification and then prove it in 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⋆ , and then use concentration bounds to show that the empirical gradients satisfy the estimates needed for convergence with high probability. We modify these empirical estimates to account for the additional noise added for privacy. The first result describes the structure of the noisy gradient and the updated weight vector. Its proof is given in Appendix F. Claim 4.3 (Modification of Claim C.2 from Diakonikolas et al. (2022)). For any unit vector w ∈ Rd , the DP gradient rule from Algorithm 3 with loss L̂t (w) and stepsize λ corresponds to the update: w − λ∇w L̃t (w) , ∥w − λ∇w L̃t (w)∥ h i
w·x such that ∇w L̃t (w) = E(x,y)∼Dt −y1{|w · x − bt | ≤ at }∇w ∥w∥ + zt+1 , where zt+1 ∼ N 0, (I − ww⊤ )σ 2 √ 2L 2 log(2/δDP ) and σ = . εDP m0 w′ =

Next, we prove the DP analogue of Lemma C.12 from Diakonikolas et al. (2022) 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(projw⊥ x)1{|w · x + τ̂ cos(ϕ)| ≤ sin(ϕ)} and Bϕ = {z ∈ R : |z+τ̂ cos(ϕ)| ≤ sin(ϕ)}. Our GD algorithm outputs f (w, ϕ, x, y) := E(x,y)∼D [g(w, ϕ, x, y)]+z, where z is the Gaussian noise (as in Claim 4.3). Lemma 4.4 (Modification of Lemma C.12 from Diakonikolas et al. (2022)). Let q = Prx∼µ [w·x ∈ Bϕ ]. Assuming that ! p dq log(1/β0 ) log(d/β0 ) d log(1/δDP ) log(1/β0 ) m0 ≥ O + + , η2 q2 ηεDP we have with probability at least 1−β0 that for any unit vector u ∈ Rd , such that E(x,y)∼P [g(w, ϕ, x, y)· u] ≥ 0, the following hold: 1 f (w, ϕ, x, y) · u ≥ E(x,y)∼P [g(w, ϕ, x, y) · u] − O (η) 2 and ∥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 Dt in each iteration t. We use the notation D in this case as a shorthand for Dt , since we are omitting the subscript everywhere. For the first part, Diakonikolas et al. (2022) show the first line of the following. Prx∼Dx [w · x ∈ Bϕ ] − O (η) Pr [w · x ∈ Bϕ ] x∼µ Prx∼µ [w · x ∈ Bϕ ] Prx∼Dx [w · x ∈ Bϕ ] =⇒ u · f (w, ϕ, x, y) ≥ u · E(x,y)∼P [g(w, ϕ, x, y)] − O (η) Pr [w · x ∈ Bϕ ] − ∥z∥ x∼µ Prx∼µ [w · x ∈ Bϕ ]

u · E(x,y)∼D [g(w, ϕ, x, y)] ≥ u · E(x,y)∼P [g(w, ϕ, x, y)]

13

Our private sample complexity allows ∥z∥ ≤ O (η) with probability at least 1−β0 /2 (via concentration of high-dimensional Gaussians). Therefore, this direction of the proof follows by following the remaining steps of the proof from Diakonikolas et al. (2022). We justify the norm bound separately. Let gpop := E[g(w, ϕ, X, Y )] and gb := E(x,y)∼D [g(w, ϕ, x, y)], := so that f = gb + z. Also, define P the population and empirical masses of the band Bϕ by q PrX∼µ [w · X ∈ Bϕ ] and qb := n1 ni=1 1{w · xi ∈ Bϕ }, respectively. If gb = 0, the claim is immediate. Otherwise, define u := gb/|b g |. On the same concentration event on zτ used above, and the argument in Diakonikolas et al. (2022), writing qb/q ∈ [1/2, 2], their argument gives, for every unit vector u, u · gb ≤

qb u · gpop + O (η) . q

If gb = 0, the desired bound is immediate. Otherwise, take u = gb/∥b g ∥. If u · gpop ≥ 0, then ∥b g ∥ ≤ 2 u · gpop + O (η) ≤ 2∥gpop ∥ + O (η) . If u · gpop < 0, then, since qb/q ≥ 1/2, qb 1 u · gpop ≤ u · gpop < 0, q 2 and hence ∥b g ∥ ≤ O (η). Thus, in either case ∥b g ∥ ≤ 2∥gpop ∥ + O (η). The bound ∥z∥ ≤ O (η) implies ∥f ∥ ≤ ∥b g ∥ + ∥z∥ ≤ 2∥gpop ∥ + O (η) , as claimed. 2

Now, writing θ = θ(w, w⋆ ), we get v · E(x,y)∼P [g(w, ϕ, x, y)] ≥ sin(θ)e−t /2 > 0 using Lemma C.3 from Diakonikolas et al. (2022). They then condition on the event Ak on which Lemma C.12 holds, and apply the directional result of Lemma C.12 to v. Hence, the only direction needed in their argument satisfies the positivity condition (E(x,y)∼P [g(w, ϕ, x, y) · u] ≥ 0) required by our restricted statement. This lower bound on v · E(x,y)∼P [g(w, ϕ, x, y)] is then converted into a lower bound on w⋆ · E(x,y)∼P [g(w, ϕ, x, y)], and, together with the norm bound from Lemma C.12, is used to verify the hypotheses of Corollary C.8 and get contraction of the angle between the iterate and w∗ . Next, we show that the DP initialization w0 in our algorithm satisfies the constraints that are needed in the proof of Theorem 1.2 from (Diakonikolas et al., 2022). They require that the dot product of the true weight w∗ with our initialization be strictly more than 0. −τ̂ 2 /2

Claim 4.5. Suppose e |τ̂ |

≥ cη. Then, with probability at least 1 − O (β), if e m0 ≥ O

d + η2

! p d log(1/δDP ) , εDP η

the private initializer satisfies w⋆ · w b0 > 0. −τ̂ 2 /2

We only invoke Claim 4.5 in the above non-trivial regime. In the complementary case e |τ̂ | < Cη, the argument of Diakonikolas et al. (2022) already implies that using the threshold τ̂ with any unit normal vector yields classification error O (η). Hence, no positive-correlation initialization guarantee is needed in this case. Finally, we bound the error on our noisy empirical threshold.

14

Claim 4.6 (Modification of Claim C.9 from (Diakonikolas et al., 2022)). Suppose η, β0 ∈ (0, 1/2), ∗ and w∗ is a unit vector and τ is a threshold,
such that Pr(x,y)∼P [sign(w · x + τ ) ̸= y] ≤ η. Suppose −1 1−κ τ̂ = Φ clip[(1 + E(x,y)∼D [y] + zτ )/2]κ for κ = O (η) is the DP estimate of the threshold τ output by Algorithm 3. If
m0 ≥ O log(1/β0 )/η 2 + log(1/β0 )/εDP η , then with probability at least 1 − β0 , Pr [sign(w∗ · x + τ̂ ) ̸= y] ≤ O (η) . (x,y)∼P

Proof. Diakonikolas et al. (2022) show that satisfying E(x,y)∼D [y] − E(x,y)∼P [y] ≤ O (η) in the proof of Claim C.9 is enough, which is what we need, as well. Thus, E(x,y)∼D [y] + zτ − E(x,y)∼P [y] ≤ O (η) suffices for us, and the rest of the argument follows. We additionally clip the argument of Φ−1 to [κ, 1 − κ], where κ = Cη for a sufficiently small universal constant C > 0. Let pe = (1+E(x,y)∼Db [y]+zτ )/2 and pb = clip(e p, [κ, 1 − κ]). Since zτ is sampled from Laplace distribution with parameter 2/m0 εDP , by the concentration of Laplace distribution, |zτ | ≤ 2 log(1/β0 )/m0 εDP with probability at least 1−β0 . For this to be upper bounded by O (η), having m0 ≥ O (log(1/β0 )/εDP η) suffices. For any p ∈ [0, 1], |b p − p| ≤ |e p − p| + κ. Hence, the clipping introduces at most an additional O (η) error. In particular, taking p = (1 + E(x,y)∼P [y])/2, the above concentration guarantee implies |b p − p| ≤ O (η). Since τb = Φ−1 (b p), the remainder of the proof of Claim C.9 follows as before.

4.3

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. (2022) 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 w0 is not too far in terms of angle from w∗ . We prove in Claim 4.5 that the same holds for our noisy initialization ŵ0 . With these necessary modifications, our proof of accuracy is complete. The grid in Algorithm 4 starts at η1 = Cη α, where Cη > 1 is a universal constant, and uses ηk = 2k−1 η1 for k ∈ [K]. The dataset is partitioned into a validation set Dval and K subsets D1 , . . . , DK . For each k ∈ [K], the subroutine is run on Dk with parameter ηk to obtain hk . 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 (α), but in Algorithm 4, we work with ηk ’s. The idea is that ηk ≥ α for all k ∈ [K]. Now, either ∗ ∗ OPT < η1 , or there must be a k ∗ ∈ [K] \ {1}, such that η1 2k −2 ≤ OPT ≤ η1 2k −1 . We claim that in either case, there exists at least one k ∈ [K], for which hk has error O (OPT +α). When OPT < η1 , then Algorithm 3 will return h, such that the error of h is at most O (η1 ) = O (α) with probability at least 1 − β ′ , where β ′ = β/K (Proposition 4.2). This satisfies the semi-agnostic learning guarantee even if OPT is much smaller than η because α = Θ(η1 ). ∗ ∗ On the other hand, suppose there exists k ∗ ∈ [K] \ {1}, such that η1 2k −2 ≤ OPT ≤ η1 2k −1 . Then with probability at least 1 − (K − 1)β ′ , for all k ≥ k ∗ , Algorithm 3 will return hypotheses hk ,

15

∗

respectively, such that the total error is O (ηk ). Thus for k ∗ , ηk∗ = η1 2k −1 ≤ 2 OPT. This means that hk∗ should satisfy the semi-agnostic error guarantee O (OPT) with no additional additive error. Combining the two together, with probability at least 1 − O (β), there must exist k ∈ [K], such that the semi-agnostic error of hk is at most max{O (α) , O (OPT)}. Now, we just need to show that the final hypothesis returned by Algorithm 4 is accurate. For that, we know that with probability at least 1 − O (β), for all k ∈ [K], the population error errP (hk ) must be close to the empirical error err c Dval (hk ) on Dval using Hoeffding’s inequality; because of our sample complexity, s ! log(K/β) ≤ O (α) . | errP (hk ) − err c Dval (hk )| ≤ O |Dval | With probability at least 1 − O (β), the exponential mechanism returns an h̄, whose empirical error is at most O (α) in addition to the empirical optimal among all hk ’s. From these two additional error sources, we get that h̄ has a population error of at most 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 τ̂ and ŵ0 , or one gradient step), at O (d) cost per use. Since the runs use disjoint data, all K = O (log(1/α)) runs together take O (nd) time. Scoring the K candidates on Dval takes O (nd log(1/α)) time. Since d ≤ n, the total running time is O (nd log(1/α)) = poly(n).

5

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. (2008), 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 (NNF24OC0 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.

16

References Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private PAC learning implies finite Littlestone dimension. In ACM Symposium on Theory of Computing (STOC), 2019. Noga Alon, Amos Beimel, Shay Moran, and Uri Stemmer. Closure properties for private classification and online prediction. In Conference on Learning Theory (COLT), 2020. George E Andrews, Richard Askey, and Ranjan Roy. Special functions. 1999. Pranjal Awasthi, Maria Florina Balcan, and Philip M Long. The power of localization for efficiently learning linear separators with noise. Journal of the ACM (JACM), 2017. Raef Bassily, Mehryar Mohri, and Ananda Theertha Suresh. Differentially private learning with margin guarantees. In Advances in Neural Information Processing Systems (NeurIPS), 2022. Amos Beimel, Shay Moran, Kobbi Nissim, and Uri Stemmer. Private center points and learning of halfspaces. In Conference on Learning Theory (COLT), 2019. Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil Vadhan. Differentially private release and learning of threshold functions. In IEEE Symposium on Foundations of Computer Science (FOCS), 2015. Mark Bun, Roi Livni, and Shay Moran. An equivalence between private classification and online prediction. In IEEE Symposium on Foundations of Computer Science (FOCS), 2020. Amit Daniely. A PTAS for agnostically learning halfspaces. In Conference on Learning Theory (COLT), 2015. Amit Daniely. Complexity theoretic limitations on learning halfspaces. In ACM Symposium on Theory of Computing (STOC), 2016. Ilias Diakonikolas, Daniel M Kane, and Jelani Nelson. Bounded independence fools degree-2 threshold functions. In IEEE Symposium on Foundations of Computer Science (FOCS), 2010. URL https://arxiv.org/abs/0911.3389. Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart. Learning geometric concepts with nasty noise. In ACM Symposium on Theory of Computing (STOC), 2018. Ilias Diakonikolas, Daniel Kane, and Nikos Zarifis. Near-optimal SQ lower bounds for agnostically learning halfspaces and ReLUs under Gaussian marginals. In Advances in Neural Information Processing Systems (NeurIPS), 2020a. Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Non-convex SGD learns halfspaces with adversarial label noise. In Advances in Neural Information Processing Systems (NeurIPS), 2020b. Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Agnostic proper learning of halfspaces under Gaussian marginals. In Conference on Learning Theory (COLT), 2021a. URL https://proceedings.mlr.press/v134/diakonikolas21b.html. Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, and Nikos Zarifis. The optimality of polynomial regression for agnostic learning under Gaussian marginals in the SQ model. In Conference on Learning Theory (COLT), 2021b. 17

Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Learning general halfspaces with adversarial label noise via online gradient descent. In International Conference on Machine Learning (ICML), 2022. URL https://proceedings.mlr.press/v162/diakonikolas22b.html. Ilias Diakonikolas, Daniel Kane, and Lisheng Ren. Near-optimal cryptographic hardness of agnostically learning halfspaces and ReLU regression under Gaussian marginals. In International Conference on Machine Learning (ICML), 2023. Charles F. Dunkl and Yuan Xu. Orthogonal Polynomials of Several Variables. 2014. Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 2014. Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography Conference (TCC), 2006. Vitaly Feldman, Parikshit Gopalan, Subhash Khot, and Ashok Kumar Ponnuswami. New results for learning noisy parities and halfspaces. In IEEE Symposium on Foundations of Computer Science (FOCS), 2006. Spencer Frei, Yuan Cao, and Quanquan Gu. Agnostic learning of halfspaces with gradient descent via soft margins. In International Conference on Machine Learning (ICML), 2021. G Freud, A Giroux, and QI Rahman. Sur l’approximation polynomiale avec poids exp(−|x|). Canadian Journal of Mathematics, 1978. Surbhi Goel, Aravind Gollakota, and Adam Klivans. Statistical-query lower bounds via functional gradients. In Advances in Neural Information Processing Systems (NeurIPS), 2020. Venkatesan Guruswami and Prasad Raghavendra. Hardness of learning halfspaces with noise. SIAM Journal on Computing, 2009. Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American statistical association, 1963. Ziwei Ji, Kwangjun Ahn, Pranjal Awasthi, Satyen Kale, and Stefani Karp. Agnostic learnability of halfspaces via logistic loss. In International Conference on Machine Learning (ICML), 2022. Adam Tauman Kalai, Adam R. Klivans, Yishay Mansour, and Rocco A. Servedio. Agnostically learning halfspaces. SIAM Journal on Computing, 2008. URL https://doi.org/10.1137/ 060649057. Gautam Kamath, Jerry Li, Vikrant Singhal, and Jonathan Ullman. Privately learning highdimensional distributions. In Conference on Learning Theory (COLT), 2019. Gautam Kamath, Argyris Mouzakis, and Vikrant Singhal. New lower bounds for private estimation and a generalized fingerprinting lemma. In Advances in Neural Information Processing Systems (NeurIPS), 2022. Haim Kaplan, Yishay Mansour, Uri Stemmer, and Eliad Tsfadia. Private learning of halfspaces: Simplifying the construction and reducing the sample complexity. In Advances in Neural Information Processing Systems (NeurIPS), 2020.

18

Vishesh Karwa and Salil Vadhan. Finite sample differentially private confidence intervals. In Conference on Innovations in Theoretical Computer Science (ITCS), 2018. Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? In IEEE Symposium on Foundations of Computer Science (FOCS), 2008. Michael Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM (JACM), 1998. Janardhan Kulkarni, Yin Tat Lee, and Daogao Liu. Private non-smooth ERM and SCO in subquadratic steps. In Advances in Neural Information Processing Systems (NeurIPS), 2021. Bo Li, Wei Wang, and Peng Ye. Private realizable-to-agnostic transformation with near-optimal sample complexity. In Conference on Learning Theory (COLT), 2025. Nathan Linial, Yishay Mansour, and Noam Nisan. Constant depth circuits, Fourier transform, and learnability. Journal of the ACM (JACM), 1993. Nick Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine learning, 1988. Doron S Lubinsky. A survey of weighted approximation for exponential weights. arXiv preprint math/0701099, 2007. Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In IEEE Symposium on Foundations of Computer Science (FOCS), 2007. URL https://doi.org/10.1109/FOCS.2007.66. HN Mhaskar and EB Saff. Extremal problems for polynomials with exponential weights. Transactions of the American Mathematical Society, 1984. Huy Lê Nguyễn, Jonathan Ullman, and Lydia Zakynthinou. Efficient private algorithms for learning large-margin halfspaces. In International Conference on Algorithmic Learning Theory (ALT). PMLR, 2020. Ryan O’Donnell. Analysis of Boolean Functions. 2014. Lucas Pesenti, Lucas Slot, and Manuel Wiedmer. Agnostic learning in (almost) optimal time via Gaussian surface area. arXiv preprint arXiv:2603.06027, 2026. Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. 2014. Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Learnability, stability and uniform convergence. The Journal of Machine Learning Research, 2010. Stefan Tiegel. Hardness of agnostically learning halfspaces from worst-case lattice problems. In Conference on Learning Theory (COLT), 2023. URL https://proceedings.mlr.press/v195/ tiegel23a.html.

19

A

Other Related Work

Agnostic learning under structured marginals. Without distributional assumptions, agnostically learning halfspaces is computationally hard, even for weak learning (Guruswami and Raghavendra, 2009; Feldman et al., 2006; Daniely, 2016; Tiegel, 2023). Building on the low-degree Fourier approach of Linial et al. (1993), Kalai et al. (2008) use polynomial L1 regression to obtain improper agnostic learners for halfspaces with error OPT +α under structured marginals, including Gaussian and log-concave distributions. The complexity of this approach is governed by the degree of polynomials needed to approximate halfspaces in L1 . Under Gaussian marginals, Diakonikolas −4 −2 et al. (2010) improved the runtime of Kalai et al. (2008) from dO(α ) to dO(α ) by establishing sharper polynomial approximation bounds. This is essentially optimal: statistical-query algorithms −2 require time dΩ(α ) (Goel et al., 2020; Diakonikolas et al., 2020a, 2021b), and a nearly matching lower bound holds for all polynomial-time algorithms under the subexponential hardness of Learning with Errors (Diakonikolas et al., 2023). However, this approach is improper, as the resulting classifier need not be a halfspace. Diakonikolas et al. (2021a) 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 OPT +α and runtime dpoly(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. (2017) developed a localization-based algorithm achieving O(OPT) + α error under isotropic log-concave marginals. Combining localization with polynomial regression, Daniely (2015) obtains an improper approximation scheme under the uniform spherical marginal, achieving error (1 + γ) OPT +α in time polynomial in d and 1/α for every fixed γ > 0; Diakonikolas et al. (2021a) give a proper analogue under Gaussian marginals. Diakonikolas et al. (2020b) showed that non-convex SGD achieves O(OPT) + α error for homogeneous halfspaces under a broad family of marginals, including isotropic log-concave distributions. For general halfspaces under Gaussian marginals, Diakonikolas et al. (2018) obtained constant-factor guarantees, even in a stronger contamination model allowing corruption of both examples and labels, and Diakonikolas et al. (2022) 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. e OPT) + α error using gradient methods on convex losses, while Ji et al. (2022) (2021) obtain O( e show that logistic regression alone cannot improve on this and obtain O(OPT) + α by adding a hinge-loss refinement step. Private learning. Distribution-free private learning of halfspaces over infinite domains is impossible: already thresholds over R are not privately learnable (Bun et al., 2015), and private learnability is characterized by finite Littlestone dimension (Littlestone, 1988; Alon et al., 2019; Bun et al., 2020). Over finite domains X ⊂ Rd , Beimel et al. (2019) (improved by Kaplan et al. (2020)) give private agnostic learners whose sample complexity grows with log∗ |X|. Generic private realizable-to-agnostic transformations (Alon et al., 2020; Li et al., 2025) are statistically efficient but not computationally efficient in general. Efficient private PAC learners exist under margin assumptions (Nguyễn et al., 2020; Bassily et al., 2022), with guarantees stated for margin-based losses rather than OPT for the 0-1 loss.

20

B

Auxiliary Results

B.1

Concentration Inequalities

Lemma B.1 (Vector Bernstein Inequality). Let U1 , . . . , Un be independent, mean-zero random P vectors in Rd . Suppose that ∥Ui ∥2 ≤ B almost surely for all i ∈ {1, . . . , n}, and let ni=1 E∥Ui ∥22 ≤ v. Then, for every β ∈ (0, 1), with probability at least 1 − β, p n 2v log(2/β) 2B log(2/β) 1X Ui ≤ + . n n 3n i=1

B.2

2

Differential Privacy Tools

Definition B.2 (Differential privacy; Dwork et al., 2006). Let εDP > 0 and δDP ∈ [0, 1). A randomized algorithm A : Z n → Y is (εDP , δDP )-differentially private if, for every pair of datasets S, S ′ ∈ Z n differing in a single example and every measurable set E ⊆ Y, Pr[A(S) ∈ E] ≤ eεDP Pr[A(S ′ ) ∈ E] + δDP . Lemma B.3 (Post-Processing of DP; Dwork and Roth, 2014). If M : X n → Y is (εDP , δDP )-DP, and f : Y → Z is any randomized function, then the algorithm f ◦ M is (εDP , δDP )-DP. Lemma B.4 (Private convex ERM; Kulkarni et al., 2021, Theorem 1.1). Let Ω ⊆ RD be a public, nonempty, compact convex set of Euclidean diameter R, and let ℓ(·; z) : RD → R be a public convex T -Lipschitz loss for every z ∈ Z. For n ≥ 2, 0 < εDP ≤ 1/2, and 0 < δDP ≤ 1/2, there exists an (εDP , δDP )-DP algorithm under replacement adjacency such that, for every S = (Z1 , . . . , Zn ) ∈ Z n , its output vb ∈ Ω satisfies ! p h i T R D log(1/δ ) DP b S (b b S (v) ≤ O E L v ) − min L , v∈Ω nεDP b S (v) := 1 Pn ℓ(v; Zi ), and the expectation is over the algorithm’s randomness. The where L i=1
n algorithm performs O n2 subgradient evaluations and Euclidean projections onto Ω. Proof. Compared to Kulkarni et al. (2021, Theorem 1.1), we use R as an upper bound on the initialization distance and assume convexity and T -Lipschitzness on all of RD , rather than only on
the neighborhood required in the original statement. Their complexity guarantee implies O n2 subgradient evaluations in the stated parameter range, with at most as many Euclidean projections, since each iteration uses one projection and at least one subgradient evaluation. Lemma B.5 (Validation via the exponential mechanism). Let K, m ∈ N, and let h1 , . . . , hK be classifiers independent of Sval ∼ P m . For εDP > 0, select b j ∈ [K] with probability proportional to exp(−εDP merr c Sval (hj )/2). Conditional on the candidates, selection is εDP -differentially private under replacement. For 0 < η < 1, with probability at least 1 − η, r log(4K/η) 2 log(2K/η) errP (hbj ) ≤ min errP (hj ) + 2 + . 2m εDP m j∈[K] Proof. Condition on the candidates. Hoeffding’s inequality (Hoeffding, 1963) 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 −merr c Sval (hj ) has sensitivity one, so the exponential mechanism ensures privacy and gives the second slack term, accounting for suboptimal selection based on empirical errors (McSherry and Talwar, 2007). Allocate failure probability η/2 to each bound. 21

B.3

L1 Regression

Fact B.6 (Random thresholding; Kalai et al., 2008, Proof of Theorem 5). Let τ ∼ Unif[−1, 1]. For every z ∈ R and y ∈ {−1, 1}, we have Prτ [sign(z − τ ) ̸= y] ≤ 12 |z − y| . Lemma B.7 (Uniform deviation for L1 regression). Let φ : X → RD be a fixed feature map such b S (v) be its empirical counterpart on that E∥φ(X)∥22 ≤ D. Let LP (v) = E | ⟨v, φ(X)⟩ − Y |, and let L n S ∼ P . Then, for every R > 0, r   b S (v) ≤ 2R D . ES∼P n sup LP (v) − L n ∥v∥2 ≤R Proof. Let σ1 , . . . , σn be i.i.d. Rademacher random variables, independent of S. Symmetrization (Shalev-Shwartz and Ben-David, 2014, Lemma 26.2) and contraction for the 1-Lipschitz maps t 7→ |t − Yi | (Shalev-Shwartz and Ben-David, 2014, Lemma 26.9) give ES sup ∥v∥2 ≤R



n  2R X b σi φ(Xi ) ES,σ LP (v) − LS (v) ≤ n i=1

. 2

By Jensen’s inequality, and since the cross terms vanish in expectation, the right-hand side is at p Pn 2
1/2 E ∥φ(X )∥ most 2R ≤ 2R D/n. i 2 i=1 n

B.4

Gaussian Marginals

R d and r ∈ [1, ∞), we write ∥f ∥ r r dµ(x) 1/r and := For a probability measure µ on R |f (x)| L (µ)  2 ∥f R ∥L∞ (µ) := inf M ≥ 0 : µ({x : |f (x)| > M }) = 0 . The inner product on L (µ) is ⟨f, g⟩L2 (µ) := f (x)g(x) dµ(x). Lemma B.8 (Hermite basis; O’Donnell, 2014, Proposition 11.33). Let {hm }m≥0 be the normalized univariate Hermite polynomials, defined by e

tx−t2 /2

=

∞ X

tm hm (x) √ . m! m=0

Q P For each multi-index κ = (κ1 , . . . , κd ) ∈ Nd0 , define hκ (x) = dj=1 hκj (xj ) and |κ| = dj=1 κj . Then {hκ }κ∈Nd is a complete orthonormal basis of L2 (N (0, Id )). In particular, {hκ : |κ| ≤ p} is an 0
orthonormal basis for the polynomials of total degree at most p, with dimension d+p p . Lemma B.9 (Mehler’s formula; Andrews et al., 1999, Eq. 6.1.13). Let {hκ }κ∈Nd be the multivariate 0 P Hermite polynomials, orthonormal in L2 (N (0, Id )). For each multi-index κ ∈ Nd0 , write |κ| = dj=1 κj . For every x, y ∈ Rd and ρ ∈ (−1, 1),    2 ∥x∥2 + ∥y∥2 2ρ ⟨x, y⟩ − ρ X 2 2 1 . ρ|κ| hκ (x)hκ (y) = exp  2(1 − ρ2 ) (1 − ρ2 )d/2 d κ∈N0

Lemma B.10 (Unit-norm polynomial approximation of halfspaces under Gaussian measure). Let d ≥ 1, and let {hκ }κ∈Nd be the orthonormal Hermite basis of L2 (N (0, Id )). There exists a universal 0 constant C > 0 such that for every α ∈ (0, 1) and every halfspace c : Rd → {−1, 1}, there is a P polynomial q(x) = |κ|≤p wκ hκ (x) of degree p ≤ Cα−2 with ∥w∥2 ≤ 1 and ∥c − q∥L1 (N (0,Id )) ≤ α. 22

Proof. Write c(x) = fθ (⟨u, x⟩), where fθ (z) = sgn(z − θ) and ∥u∥2 = 1. Let B : R → [0, ∞) be the one-dimensional smoothing kernel of Diakonikolas et al. (2010, Section 4), and define Bλ (t) = λB(λt). By Pesenti et al. (2026, Section 4.2), for every θ ∈ R, there exist λ > 0 and an integer p ≤ Cα−2 , with C independent of θ, such that gθ = Bλ ∗ fθ satisfies ∥fθ − Πp gθ ∥L1 (N (0,1)) ≤ α, 2 where Πp (·) R is the L (N (0, 1))-orthogonal projection onto polynomials of degree at most p. Since R Bλ (t) dt = 1 (Diakonikolas et al., 2010, Lemma 4.4), we have Z |gθ (z)| ≤ Bλ (t)|fθ (z − t)| dt = 1 ∀z. R

Hence ∥Πp gθ ∥L2 (N (0,1)) ≤ ∥gθ ∥L2 (N (0,1)) ≤ 1. P Set q(x) = Πp gθ (⟨u, x⟩). Its degree is at most p, so q = |κ|≤p wκ hκ for some coefficient vector w (Lemma B.8). Since ∥u∥2 = 1, we have ⟨u, X⟩ ∼ N (0, 1) for X ∼ N (0, Id ). Thus, the approximation error and L2 norm of q under N (0, Id ) equal those of Πp gθ under N (0, 1). Finally, orthonormality yields ∥w∥2 = ∥q∥L2 (N (0,Id )) = ∥Πp gθ ∥L2 (N (0,1)) ≤ 1. Fact B.11 (Euclidean covers; Diakonikolas et al., 2021a, Fact 21). For every k ≥ 1 and γ ∈ (0, 1), the unit sphere in Rk has an explicit γ-cover in ℓ2 of size at most (C/γ)k , where C > 0 is a universal constant. Fact B.12 (Gaussian halfspace discretization; Diakonikolas et al., 2021a, Fact 22). Let X ∼ N (0, Id ), let u, v ∈ Rd be unit vectors, and let t1 , t2 ∈ R. Then E[|hu,t p1 (X) − hv,t1 (X)|] = O (∥u − v∥2 ) and E[|hu,t1 (X) − hu,t2 (X)|] = O (|t1 − t2 |). Moreover, if |t| ≥ C log(1/γ), then E[|hv,t (X) − sign(t)|] = O (γ).

B.5

Log-Concave Marginals

A probability measure is log-concave if its density is of the form e−V , where V is convex. Logconcavity is preserved under linear projections, and log-concave distributions have finite moments of all orders. We use the following quantitative density bound for standardized one-dimensional log-concave distributions. Fact B.13 (Bound on the density of log-concave distributions; Kalai et al., 2008, Lemma 6). Let ν be a log-concave distribution on R with mean zero and variance one. Then its density g satisfies g(x) ≤ e · e−|x|/16 for all x ∈ R. The next two results concern weighted polynomial approximation on R with the exponential weight function. They are not specific to log-concave measures. We use them, together with Fact B.13, in the proof of Lemma D.3. Let ∥·∥Lk denote the Lk norm with respect to the Lebesgue measure, and let W (x) := e−|x| . Lemma B.14 (Weighted Nikolskii inequality; Lubinsky, 2007, §9). There is a universal constant C such that, for every p ≥ 1 and every univariate polynomial q of degree at most p, ∥qW ∥L∞ ≤ C log(p + 1) ∥qW ∥L1 . Lemma B.15 (Weighted Jackson estimate; Freud et al., 1978, see also Lubinsky, 2007, §5). Let fθ (z) = sign(z − θ). There exists a universal constant C > 0 such that, for every θ ∈ R and integer p ≥ 2, there is a polynomial q of degree at most p satisfying ∥(q − fθ )W ∥L1 ≤ 23

C . log(p + 1)

Proof. Set Hθ = fθ W . By Freud et al. (1978, Theorem 2.2), taking δ = 1/2, there exists a polynomial q of degree at most p satisfying " # Z ∥Hθ ∥L1 ∥(q − fθ )W ∥L1 ≤ C sup ∥Hθ (· + h) − Hθ ∥L1 + |Hθ (z)| dz . + √ log p |z|≥ p |h|≤1/ log p To bound the first term on the right hand side, first observe that ∥W ′ ∥L1 = 2. Using the fundamental theorem of calculus, we obtain ∥W (· + h) − W ∥L1 ≤ |h| ∥W ′ ∥L1 = 2|h|. Next, fθ (z + h) and fθ (z) differ only when z lies between θ − h and θ. On this interval, their difference has absolute value 2. Since W ≤ 1, ∥(fθ (· + h) − fθ )W ∥L1 ≤ 2|h|. Finally, adding and subtracting fθ (z + h)W (z) and applying the triangle inequality gives ∥Hθ (· + h) − Hθ ∥L1 ≤ ∥W (· + h) − W ∥L1 + ∥(fθ (· + h) − fθ )W ∥L1 ≤ 4|h|. √ R For the remaining terms, |Hθ | = W gives ∥Hθ ∥L1 = 2 and |z|≥√p |Hθ (z)| dz = 2e− p . Substitut√
ing these estimates yields ∥(q − fθ )W ∥L1 ≤ C 6/ log p + 2e− p ≤ C/ log(p + 1). All constants are independent of p and θ.

C

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 (εDP , δDP )-DP under replacement of one labeled example. Proof. The feature map, the partition into blocks, and the algorithm parameters are data-independent. For each example (x, y), the loss v 7→ |⟨v, ψ̄p,T (x)⟩−y| is convex and T -Lipschitz, since ∥ψ̄p,T (x)∥2 ≤ T . As the optimization domain is the public unit ball, Lemma B.4 implies that each regression run is (εDP , δDP )-DP with respect to its training block. All blocks are disjoint, and running the DP gradient descent algorithm with the same privacy parameters independently on each block guarantees (εDP , δDP )-DP by the guarantees of Lemma B.4 and parallel composition. Our output space being defined for the remainder of the computations via v̂j ’s does not violate DP because of post-processing (Lemma B.3). Finally, applying the exponential mechanism (Lemma B.5) on a disjoint validation block of data satisfies εDP -DP. Therefore, by parallel composition, we obtain (ε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 be integers and Dp = d+p p . Let h1 , . . . , hDp enumerate the multivariate Hermite polynomials of degree at most p, orthonormal in L2 (N (0, Id )). Define ψp (x) = (h1 (x), . . . , hDp (x)). For every α ∈ (0, 1) satisfying d ≥ 2p2 /α and X ∼ N (0, Id ), h p i P ∥ψp (X)∥2 > 2 Dp ≤ α. Proof. Write V = ∥ψp (X)∥22 /Dp . Orthonormality gives E[V ] = 1. We claim that 2

Var (V ) ≤ e2p /d − 1.

24

(13)

Assuming this claim, Chebyshev’s inequality gives h p i P ∥ψp (X)∥2 > 2 Dp = P [V − 1 > 3]   E (V − 1)2 ≤ 9 2 /d 2p e −1 ≤ 9 eα − 1 ≤ 9 (e − 1)α ≤ 9 ≤ α.

(since d ≥ 2p2 /α) (by convexity of ex for α ∈ [0, 1])

P 2 It remains to establish (13). For every integer m ≥ 0, define Km (x) = |κ|≤m hκ (x) . In particular, Kp (X) P = Dp V . To compute the second moment of Kp (X), we use the generating m function F (z, x) = ∞ m=0 Km (x)z . Mehler’s formula (restated in Lemma B.9) gives   2 z exp ∥x∥ X 2 1+z 1 . F (z, x) = z |κ| hκ (x)2 = 1−z (1 − z)(1 − z 2 )d/2 d κ∈N0

Since ∥X∥22 ∼ χ2d , its moment-generating function gives, for sufficiently small z, w > 0, 1 E[F (z, X)F (w, X)] = d+1 (1 − z) (1 − w)d+1

 1−

4zw (1 − z)(1 − w)

−d/2 .

Expanding the last factor using the binomial series and comparing coefficients of z p wp yields   p X 4k (d/2)k d + p 2 2 E[Kp (X) ] = , k! p−k k=0

where (a)k =

Qk−1

j=0 (a + j), with (a)0 = 1. We therefore arrive at

E[V 2 ] = ≤

p X 4k (d/2)k k=0 p X

k!

!2

Dp

(2p2 /d)k k!

k=0 2p2 /d

≤e

d+p p−k

,

Q p−j d+p where the first inequality follows from p−k /Dp = k−1 j=0 d+1+j , together with p − j ≤ p and (d/2 + j)/(d + 1 + j)2 ≤ 1/(2d). Since E[V ] = 1, (13) follows. We now turn to the proof of Theorem 2.1. We use Algorithm 1 with the degree-p Hermite feature map ψp . Fix a universal constant c ∈ (0, 1/4] and a sufficiently large universal constant C, depending only on c. Set       p  −2  d+p 2 C p = Cα , Dp = , T = 2 Dp , k = log2 , M= . (14a) β α p 25

Since p ≤ (C + 1)α−2 , choosing Cdim ≥ 2(C + 1)2 /c ensures that d ≥ Cdim α−5 implies d ≥ 2p2 /(cα). Thus Lemma C.2 applies at level cα. Let n0 ≥ 2 be the smallest integer satisfying p r ! T Dp log(1/δDP ) Dp + ≤ cα, (14b) C εDP n0 n0 and set

    1 kM 1 + log , m= C α2 εDP α β

n = kn0 + m.

(14c)

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, Id ), and recall the population regression loss LP (v) = E(X,Y )∼P v, ψ̄p,T (X) − Y , and its minimum L⋆ := min∥v∥2 ≤1 LP (v). b S (v) := n−1 P Additionally, for the training block Sj , write L j 0 (Xi ,Yi )∈Sj v, ψ̄p,T (Xi ) − Yi for the empirical regression loss. We first bound the expected excess regression loss of a single training run. Orthonormality and clipping give Eµ ∥ψ̄p,T (X)∥22 ≤ Dp and ∥ψ̄p,T (x)∥2 ≤ T . The loss is convex and T -Lipschitz on all of RDp , and the optimization domain is the public unit ball, of diameter 2. Fix a population minimizer ⋆ b S (b b v ⋆ ∈ argmin∥v∥2 ≤1 LP (v), so that LP (v ⋆ ) = L⋆ . Adding and subtracting L j vj ) and LSj (v ) give       b S (b b vj ) − L b S (v ⋆ ) + L b S (v ⋆ ) − L⋆ LP (b vj ) − L⋆ = LP (b vj ) − L j vj ) + LSj (b j j i 
h  b S (v) + L b S (b b S (v) + L b S (v ⋆ ) − L⋆ . ≤ sup LP (v) − L v ) − min L j j j j j

(15)

∥v∥2 ≤1

∥v∥2 ≤1

The inequality uses ∥b vj ∥2 ≤ 1. Since v ⋆ is fixed and the examples in Sj are sampled from P , b S (v ⋆ ) = LP (v ⋆ ) = L⋆ . Thus the final term in (15) has mean zero. Taking expectations over Sj ESj L j and the randomness of the private optimizer, Lemmas B.4 and B.7 therefore give r   Dp ⋆ b b E[LP (b vj ) − L ] ≤ E LSj (b vj ) − min LSj (v) + 2 ≤ cα, (16) n0 ∥v∥2 ≤1 where the last inequality follows from the choice of n0 in (14b). We then use the standard confidence-amplification argument based on independent repetition; see, e.g., Shalev-Shwartz et al. (2010, proof of Theorem 26). By (16) and Markov’s inequality, P(LP (b vj ) − L⋆ > 2cα) ≤ 1/2. Since the k training runs are independent, P(minj∈[k] LP (b vj ) > ⋆ −k L + 2cα) ≤ 2 ≤ β/2. Thus, with probability at least 1 − β/2, min LP (b vj ) ≤ L⋆ + 2cα.

(17)

j∈[k]

Next, we argue about the correctness of the choice of our threshold, which requires our grid over [−1, 1] to be fine enough that the bias due to discretization is small, but not so fine that we blow up in terms of our sample complexity and running time when applying the exponential mechanism. If we select a threshold uniformly at random from the continuous interval [−1, 1], then Fact B.6 bounds the expected classification error under a uniform threshold τ ∼ Unif[−1, 1] by half the absolute loss. Then the expected 0-1 loss preserves our agnostic learning error requirements. However, rounding τ to the midpoint of its grid interval yields a threshold that is uniform over {t1 , . . . , tM }. At a fixed x, rounding changes the prediction only if the score ⟨b vj , ψ̄p,T (x)⟩ lies between τ and the midpoint τ is rounded to, which happens with probability at most 1/(2M ). Hence, the expectation of the population error of vbj over the random sampling from the discretized 26

P P grid is M −1 M vj )/2 + 1/(2M ). Since minℓ errP (hj,ℓ ) ≤ M −1 M ℓ=1 errP (hj,ℓ ) ≤ LP (b ℓ=1 errP (hj,ℓ ), conditioned on the event in (17) and taking the minimum over all vbj ’s, we have min errP (hj,ℓ ) ≤ j,ℓ

1 1 1 min LP (b vj ) + ≤ L⋆ + 2cα. 2 j∈[k] 2M 2

(18)

Let h denote the classifier selected by the exponential mechanism on Sval . Conditional on the training outputs, Lemma B.5, with K = kM , η = β/2, and m as in (14c), gives errP (h) ≤ minj,ℓ errP (hj,ℓ ) + cα with probability at least 1 − β/2. Thus, with probability at least 1 − β, errP (h) ≤ L⋆ /2 + 3cα,

(19)

which comes due to sampling and the noise due to the exponential mechanism. We next compare L⋆ with the error of the best halfspace. Fix c0 ∈ C. By Lemma B.10, and the choice of the degree p in (14a), there is a polynomial q = ⟨vq , ψp ⟩ with ∥vq ∥2 ≤ 1 and ∥q − c0 ∥L1 (µ) ≤ cα. Write s(x) := T / max{T, ∥ψp (x)∥2 }, so that ψ̄p,T (x) = s(x)ψp (x). Since 0 < s(x) ≤ 1 and |y| = 1, vq , ψ̄p,T (x) − y = |s(x)q(x) − y| ≤ s(x)|q(x) − y| + 1 − s(x) ≤ |q(x) − c0 (x)| + |c0 (x) − y| + 1 − s(x). Taking expectations over a population example (X, Y ) ∼ P yields LP (vq ) ≤ 2 errP (c0 ) + ∥q − c0 ∥L1 (µ) + Eµ [1 − s(X)].

(20)

Moreover, since 0 ≤ 1−s(x) ≤ 1{∥ψp (x)∥2 > T }, Lemma C.2, applied at level cα, gives Eµ [1−s(X)] ≤ Prµ (∥ψp (X)∥2 > T ) ≤ cα. Since ∥vq ∥2 ≤ 1, we conclude that L⋆ ≤ LP (vq ) ≤ 2 errP (c0 ) + 2cα. Taking the infimum over c0 ∈ C gives L⋆ ≤ 2 OPT +2cα.

(21)

Combining (19) and (21), we obtain the desired errP (h) ≤ OPT +4cα ≤ OPT +α, where the last inequality uses c ≤ 1/4. The choices in (14b) and (14c) satisfy      D D 1 1 2 p p e e n0 = O + , m=O + log , α2 εDP α α2 εDP α β p where the bound on n0 uses T Dp = 2Dp . Since k = O (log(2/β)) and n = kn0 + m, this yields the stated sample bound on n. Finally, we analyse the running time. Computing the clipped Hermite features requires O (pDp ) arithmetic operations per example. Given these features, subgradient evaluation and projection
onto the Euclidean unit ball each take O (Dp ) time, so Lemma B.4 gives a total cost of O kn20 Dp for the k private ERM runs. Evaluating the kM candidate classifiers on the validation sample requires O (kM mDp ) operations. Thus, the overall running time is
O npDp + kn20 Dp + kM mDp = poly (n) , since M ≤ p < Dp ≤ n0 and kn0 + m = n. 27

D

Private Improper Agnostic Learning: Log-Concave Marginals

We extend the learner of Section 2 to known, full-dimensional1 log-concave marginals. The regression, confidence amplification, thresholding, and private validation steps are unchanged. We replace the Hermite features by a polynomial basis that is orthonormal under the marginal. The approximation guarantee in 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 that controls the additional regression loss while keeping the feature norms bounded. Theorem D.1 (DP improper agnostic learner for log-concave marginals). Let α, β ∈ (0, 1) and εDP , δDP ∈
(0, 1/2]. Set p = ⌈exp(C/α)⌉ for a sufficiently large universal constant C > 0, let d Dp = d+p p , and let T be as in (22). Let P be any distribution on R × {±1} with a known, fulldimensional log-concave marginal µ. Then the modification of Algorithm 1 described in Appendix D.1 is (εDP , δDP )-DP and, given p ! Dp T D p e n=O + 2 α εDP α i.i.d. samples from P , returns a classifier h satisfying errP (h) ≤ OPT +α with probability at least 1 − β. The algorithm runs in time poly(n), provided that constructing the orthonormal feature map, evaluating it at an input, and computing T from public information each take time poly(Dp ). p As we show in Remark 3, T = Dp /(cα) is an admissible clipping threshold. Consequently, the
e Dp /α2 + Dp /(εDP α3/2 ) . sample bound is at most O

D.1

The Algorithm

Let µ be a known, full-dimensional log-concave distribution on Rd . We modify Algorithm 1 by replacing the Hermite features with a polynomial basis orthonormal under µ, choosing a clipping threshold adapted to µ, and changing the optimization domain. We increase the polynomial degree to achieve the required approximation accuracy. We keep k, M , and m as in (14a) and (14c), and replace the block size n0 by (27). 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/α)⌉ for a sufficiently large universal constant C > 0. For the optimization D domain, we replace the unit coefficient ball in Algorithm 1 with B2 p (R0 ) := {v ∈ RDp : ∥v∥2 ≤ R0 }, where R0 is the universal constant in Lemma D.3. Next, we recall how to construct an orthonormal basis for the polynomials of degree at most p in L2 (µ). Let mp (x) = (xκ )|κ|≤p be the vector of monomials of degree at most p. Following the standard moment-matrix orthonormalization (Dunkl and Xu, 2014), define the population Gram −1/2 matrix Gp = Eµ [mp (X)mp (X)⊤ ] and set ψp (x) = Gp mp (x). The entries of Gp are the moments of µ through degree 2p. Log-concavity ensures that all moments are finite, while full dimensionality −1/2 guarantees that Gp is positive definite. Since Gp is invertible, the coordinates of ψp span the polynomials of degree at most p. Moreover, Eµ [ψp (X)ψp (X)⊤ ] = IDp , so they form an orthonormal basis of this polynomial space in L2 (µ). In particular, ∥⟨v, ψp ⟩∥L2 (µ) = ∥v∥2 and Eµ ∥ψp (X)∥22 = Dp . This construction based on the moment-matrix provides a general way to obtain the required orthonormal basis. When an explicit basis is available, it may be used directly without forming Gp , 1

The full-dimensionality assumption is without loss of generality since the marginal is known.

28

provided its construction and evaluation satisfy the computational assumption in Theorem D.1. For example, the normalized Hermite basis for the standard Gaussian marginal can be constructed and evaluated in poly(Dp ) arithmetic operations. 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 }. Since µ is known, we can choose the clipping threshold directly from the marginal. For a sufficiently small universal constant c > 0, set ( " )  # t T = min t > 0 : Eµ 1− ≤ cα , (22) ∥ψp (X)∥2 + where (x)+ = max{x, 0}. The argument for (7) uses only orthonormality and therefore also p applies to the present feature map. Since p (1 − t/∥ψp (x)∥2 )+ ≤ 1{∥ψp (x)∥2 > t}, the choice t = Dp /(cα) is admissible, and hence T ≤ Dp /(cα). Depending on the marginal and the parameter regime, marginal-dependent choices may yield a smaller threshold. For example, if µ = N (0, Id ) and p d ≥ 2p2 /(cα), Lemma C.2 shows that T ≤ 2 Dp , so the privacy term improves to O (Dp /(εDP α)).2

D.2

Analysis

In this section, we prove Theorem D.1. We first establish privacy. Proposition D.2. The learner in Theorem D.1 satisfies (εDP , δDP )-DP under replacement of one labeled example. Proof. The feature map, clipping threshold, coefficient ball, and sample partition are public. Since ∥ψ̄p,T (x)∥2 ≤ T , the loss is convex and T -Lipschitz in v on all of RDp . Thus, each regression run is (εDP , δDP )-DP by Lemma B.4. The neighboring-dataset argument in the proof of Proposition C.1 then applies unchanged, establishing (εDP , δDP )-DP for the full learner. 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 L1 and L2 norms under the marginal. The result extends to arbitrary halfspaces by considering their one-dimensional projections. Lemma D.3 (Bounded-norm polynomial approximation of halfspaces under log-concave measures). There exist universal constants C, R0 ≥ 1 such that the following holds. Let µ be a log-concave probability measure on Rd . For every integer p ≥ 2 and halfspace c : Rd → {−1, 1}, there is a polynomial q of degree at most p satisfying ∥q − c∥L1 (µ) ≤ C/ log(p + 1) and ∥q∥L2 (µ) ≤ R0 . In particular, taking p = ⌈exp(C/α)⌉ gives ∥q − c∥L1 (µ) ≤ α. Proof. Consider a log-concave probability measure ν on R with mean zero and variance one, and set fθ (z) = sign(z − θ). We will first prove that there exists a polynomial r of degree at most p satisfying ∥r − fθ ∥L1 (ν) ≤ C/ log(p + 1) and ∥r − fθ ∥2L2 (ν) ≤ C. (23) Assuming the above is true, we next extend it to Rd . Write the halfspace c (x) = sign(⟨u, x⟩ − θ). For X ∼ µ, consider the mean a = Eµ ⟨u, X⟩ and variance b2 = Varµ (⟨u, X⟩) > 0.3 Let ν denote the distribution of the normalized random variable Z = (⟨u, X⟩ − a)/b. Then ν is log-concave, with 2

Lemma C.2 is stated for Hermite features, but any two orthonormal bases of the degree-≤ p polynomials in L2 (µ) differ by an orthogonal matrix, so ∥ψp (x)∥2 is the same for both. 3 If b = 0, take q(x) ≡ sign(a − θ).

29

mean zero and variance one. Apply Equation (23) to f(θ−a)/b and set q(x) = r ((⟨u, x⟩ − a) /b). Since q(X) = r(Z) and c(X) = f(θ−a)/b (Z), this preserves the degree of the polynomial and yields ∥q − c∥L1 (µ) ≤ C/ log(p + 1) and ∥q − c∥2L2 (µ) ≤ C. Since ∥c∥L2 (µ) = 1, using the triangle inequality on q = (q − c) + c gives √ ∥q∥L2 (µ) ≤ ∥q − c∥L2 (µ) + ∥c∥L2 (µ) ≤ C + 1 =: R0 . It remains to prove Equation (23). Let W (z) = exp (− |z| /32) Then using Kalai et al. (2008, Lemma 6) (restated in Fact B.13), the density satisfies g(z) ≤ e exp(−|z|/16).

(24)

Note that fθ (z) W (z) is the product of a sign function and an exponentially decaying weight, so |fθ (z)W (z)| = e−|z|/32 . Then, the approximation theorem of Freud et al. (1978) (restated in Lemma B.15) gives a polynomial r of degree at most p satisfying ∥(r − fθ )W ∥L1 ≤

C . log(p + 1)

(25)

We now bound the L2 error: ∥(r − fθ )W ∥2L2 ≤ ∥(r − fθ )W ∥L∞ ∥(r − fθ )W ∥L1 ≤ (∥rW ∥L∞ + ∥fθ W ∥L∞ )

C log(p + 1)

C ≤ C. ≤ C log(p + 1) log(p + 1)

(26)

Here the first inequality follows from Hölder’s inequality and the second uses Equation (25) and triangle inequality. The third inequality follows from Mhaskar and Saff (1984, Theorem 3.1) (restated in Lemma B.14) and observing that ∥fθ W ∥L∞ ≤ 1. Now using g ≤ eW 2 and W ≤ 1 we can transfer Equations (25) and (26) to a norm with respect to measure induced by ν, to get Equation (23). This completes the proof. We now turn to the proof of Theorem D.1. Fix c ∈ (0, 1/4] as in (22). The block-size condition differs from the Gaussian case only through the radius R0 and the threshold T : let n0 ≥ 2 be the smallest integer satisfying " p r # R0 T Dp log(1/δDP ) Dp ≤ cα. (27) C + R0 εDP n0 n0 Proof of Theorem D.1. Proposition D.2 provides the privacy guarantee. We now prove the accuracy and running time bounds. Write LP (v) = E(X,Y )∼P |⟨v, ψ̄p,T (X)⟩ − Y | and L⋆ = min∥v∥2 ≤R0 LP (v). The minimum exists since the domain is compact and the clipped loss is continuous in v. We first compare L⋆ with the error of the best halfspace. Fix c0 ∈ C. By Lemma D.3, our choice of p gives a polynomial q = ⟨vq , ψp ⟩ such that ∥q − c0 ∥L1 (µ) ≤ cα and ∥vq ∥2 = ∥q∥L2 (µ) ≤ R0 . Let s(x) = T / max{T, ∥ψp (x)∥2 }. Since 1 − s(x) = (1 − T /∥ψp (x)∥2 )+ , (22) gives Eµ [1 − s(X)] ≤ cα. Substituting this into (20) gives LP (vq ) ≤ 2 errP (c0 ) + 2cα. Since ∥vq ∥2 ≤ R0 , taking the infimum over c0 ∈ C yields L⋆ ≤ 2 OPT +2cα. (28)

30

Next, we bound the expected excess regression loss of a single training run. The loss is convex and T -Lipschitz on all of RDp , the optimization domain has diameter 2R0 , and Eµ ∥ψ̄p,T (X)∥22 ≤ Dp . Applying the decomposition in (15), we obtain     ⋆ b b b S (v) E[LP (b vj ) − L ] ≤ E LSj (b vj ) − min LSj (v) + E sup LP (v) − L j ∥v∥2 ≤R0

∥v∥2 ≤R0

p r R0 T Dp log(1/δDP ) Dp + 2R0 ≤ cα. ≤C εDP n0 n0 where the second inequality follows from Lemmas B.4 and B.7, and the last from (27). Since the training runs are independent and the thresholding and validation steps use the same choices of k, M , and m, the argument leading to (19) applies with L⋆ = min∥v∥2 ≤R0 LP (v). Consequently, using (28), errP (h) ≤ OPT +α with probability at least 1 − β. It remains to bound the sample size and running time. Since R0 is a universal constant, (27) gives ! p Dp T Dp log(1/δDP ) + , n0 = O α2 εDP α independent of β, and k = O (log(2/β)). The validation size m is absorbed by this bound. Indeed, Dp ≥ 1, and every point satisfies ∥ψp (x)∥2 ≥ 1 because the constant polynomial has unit L2 (µ) norm. Hence, the expectation in (22) is at leastp(1 − t)+ , so T ≥ 1 − cα ≥ 3/4. This proves the stated bound on n = kn0 + m. Since T ≤ Dp /(cα) by (7), the bound is always at most
e Dp /α2 + Dp /(εDP α3/2 ) . O Finally, we bound the running time, measured in arithmetic operations. By the computational −1/2 hypothesis in Theorem D.1, computing Gp and T takes poly(Dp ) operations. For each example,
−1/2 evaluating ψp (x) = Gp mp (x) takes O (pDp ) operations for the monomials and O Dp2 for the matrix–vector product, and clipping takes O (Dp ) more. The remaining steps are those of Algorithm 1 D with the unit ball replaced by B2 p (R0 ). Projection onto this ball still takes O (Dp ) operations,
so, as in the proof of Theorem 2.1, the private ERM runs and the validation step take O kn20 Dp and O (kM mDp ) operations, respectively. Since p < Dp , the total is
poly(Dp ) + O nDp2 + kn20 Dp + kM mDp = poly(n), where the last equality uses M ≤ p < Dp ≤ n0 and kn0 + m = n.

E

Proofs for Proper Learning with Gaussian Marginals

Proof of Lemma 3.2. We follow the subspace construction in the proof of Diakonikolas et al. (2021a, Proposition 5). Write µ = N (0, Id ). Let q ∗ be the orthogonal projection of r(x) = E[U | X = x] onto Pp . The squared-loss identity gives ∥q − q ∗ ∥L2 (µ) ≤ c0 α. Since |r| ≤ 1, we also have ∥q ∗ ∥L2 (µ) ≤ 1 and ∥q∥L2 (µ) ≤ 1 + c0 α. Consequently, for every Q ∈ Pp , |E [(U − q(X))Q(X)]| = |E [(q ∗ (X) − q(X))Q(X)]| ≤ c0 α ∥Q∥L2 (µ) . (29)   Set M = Eµ ∇q(X)∇q(X)⊤ , and let V be the span of its eigenvectors with eigenvalues at least α2 /C0 . The Hermite derivative identity and trace estimate in Diakonikolas et al. (2021a, Fact 19 and the proof of Lemma 6) give tr(M ) ≤ p ∥q∥2L2 (µ) . It follows that dim(V ) ≤

C0 p(1 + c0 α)2 = O α−4 . 2 α 31

Fix a halfspace f = hw,t and write w = wV + w⊥ for its orthogonal decomposition with respect to V . If w⊥ = 0, then f already has its normal in V . Otherwise, set ξ = w⊥ / ∥w⊥ ∥2 , and define (Aξ g)(x) = EG∼N (0,1) [g (x − ⟨ξ, x⟩ ξ + Gξ)] . Under µ, this is conditional expectation given the projection onto ξ ⊥ . Thus, Aξ is an orthogonal projection in L2 (µ), a contraction in L1 (µ), and preserves Pp . Applying Diakonikolas et al. (2021a, Claim 10) directly gives   ∥q − Aξ q∥2L2 (µ) ≤ E (∂ξ q(X))2 = ξ ⊤ M ξ ≤ α2 /C0 . (30) By Lemma B.10, taking C0 sufficiently large gives a ∈ Pp with ∥a∥L2 (µ) ≤ 1 and ∥f − a∥L1 (µ) ≤ α. Set Q = a − Aξ a. Then ∥Q∥L2 (µ) ≤ 1, Aξ Q = 0, and ∥(f − Aξ f ) − Q∥L1 (µ) ≤ ∥f − a∥L1 (µ) + ∥Aξ (f − a)∥L1 (µ) ≤ 2α. Since |U | ≤ 1 and Aξ Q = 0, we obtain E [U (f (X) − Aξ f (X))] ≤ 2α + E [(U − q(X))Q(X)] + E [(q(X) − Aξ q(X))Q(X)] −1/2

≤ (2 + c0 + C0

)α,

where the last inequality uses Equations (29) and (30). Now, Aξ f (x) = EG [sign(⟨wV , x⟩ + ∥w⊥ ∥2 G + t)] . This is a mixture of halfspaces with unit normals in V , or constant classifiers if wV = 0. Hence one −1/2 such classifier h∗ satisfies E[U (f (X) − h∗ (X))] ≤ (2 + c0 + C0 )α. When w⊥ = 0, take h∗ = f . For the finite class, use the covering and discretization bounds of Diakonikolas et al. (2021a, Fact 21 and Fact 22 with its proof), restated in Facts B.11 and B.12. Normalize the nonzero centers of an α/2-net of the unit ball of V to obtain an α-net V of its unit sphere. Set l p m R = α K0 log(1/α)/α for a sufficiently large universal constant K0 . Define H(q) = {hv,jα : v ∈ V, j ∈ Z, |jα| ≤ R} ∪ {he1 ,R , he1 ,−R } . When V = {0}, omit the first set. The two additional halfspaces approximate the constant classifiers. The discretization bound gives an h ∈ H(q) satisfying P[h(X) ̸= h∗ (X)] = O (α), including when h∗ is constant or has threshold outside [−R, R]. Thus, E [U (f (X) − h(X))] ≤ E [U (f (X) − h∗ (X))] + 2P[h(X) ̸= h∗ (X)] ≤ Cα. Finally, the covering bound gives
log |H(q)| = O ((dim(V ) + 1) log(1/α)) = O α−4 log(1/α) . The construction uses only q and α.

32

Proof of Lemma 3.4. Let m b =

2 n

X

Yi ψ̄p,T (Xi ).

(Xi ,Yi )∈S1

Each summand has norm at most T , so m b has replacement sensitivity 4T /n. The noise scale in Algorithm 2 therefore makes m b + Z (εDP , δDP )-DP by standard Gaussian mechanism (Dwork and Roth, 2014). Projection and construction of q are post-processing and preserve privacy. Write ℓ = log(8/β) and LδDP = log(1.25/δDP ). The centered summands have norm at most 2T and second moment at most Dp . By Lemma B.1, with probability at least 1 − β/4, ! r Dp ℓ T ℓ . ∥m b − mT ∥2 ≤ C1 + n n p √  Gaussian concentration gives, with probability at least 1 − β/4, ∥Z∥2 ≤ σ Dp + 2ℓ . Orthonormality and |U | ≤ 1 imply ∥m pT ∥2 ≤ 1. Projection onto the unit ball therefore cannot increase distance to mT . Using T = 2 Dp , with probability at least 1 − β/2 we obtain ∥m e − mT ∥2 ≤ ∥m b − mT ∥2 + ∥Z∥2 ! r p p p Dp ℓ (Dp + Dp ℓ) LδDP Dp ℓ + + . ≤ C2 n n εDP n For a sufficiently large universal constant K, the condition ! p Dp ℓ Dp ℓ LδDP n≥K + α2 εDP α

(31)

makes this at most c0 cα. By Equation (9), e − mT ∥22 ≤ c20 c2 α2 . Ls (q) − inf Ls (Q) = ∥m Q∈Pp

Finally, projection and orthonormality give ∥q∥L2 (µ) = ∥m∥ e 2 ≤ 1 on every run. Proof of Theorem 3.1. Round n up to an even integer. If one observation in S1 changes, the private polynomial release is followed only by post-processing with S2 fixed. If one observation in S2 changes, the distribution of q is unchanged, and conditional on q, selection is εDP -DP. Thus, the complete algorithm is (ε  DP , δDP )-DP.  Since p = C0 /(cα)2 , choosing Cdim ≥ 2(C0 +1)2 c−5 ensures d ≥ 2p2 /(cα). Thus, the dimension condition needed in Lemma 3.5 follows from the theorem’s assumption. The first two terms in the sample bound imply Equation (31) and hence the event in Lemma 3.4 with probability at least 1 − β/2. On this event, Lemma 3.5 gives min errP (h) ≤ OPT +(C/2 + 1)cα.

h∈H(q)

Condition on any such released polynomial and write K = |H(q)|. Applying Lemma B.5 to the n/2 observations in S2 gives, with probability at least 1 − β/2, r log(8K/β) 4 log(4K/β) b errP (h) ≤ min errP (h) + 2 + . n εDP n h∈H(q) 33

Since log K = O α−4 log(1/α) , the last two terms in the theorem’s sample bound control the dependence on K. The first two terms also control the remaining confidence terms, since Dp ≥ 1. With sufficiently large constants in the sample bound, the selection error is at most cα. A union bound therefore gives, with probability at least 1 − β, errP (b h) ≤ OPT +(C/2 + 2)cα ≤ OPT +α, where the last inequality follows by taking c sufficiently small. Every member of H(q) is a halfspace, so the learner is proper. Finally, we analyse the running time. Computing the clipped Hermite features of the samples in S1 takes O (npDp ) time, and the noisy average and its projection take O (nDp ) more. Since √ ∂i hκ = κi hκ−e
i , the matrix M = E[∇q(X)∇q(X)⊤ ] can be computed exactly from the coefficients
2 3 of q in O d Dp time,

and its eigendecomposition takes O d time. By Lemma 3.2, |H(q)| = exp O α−4 log(1/α) ; each member can be listed in poly(d, 1/α) time and evaluated on S2 in O (nd) time. Thus, the exponential mechanism takes O (nd|H(q)|) time

overall. Since d ≤ Dp ≤ n and 1/α ≤ n, the total running time is poly(n) · exp O α−4 log(1/α) .

F

Missing Details for Semi-Agnostic Learning

Algorithm 4 DP Semi-Agnostic Halfspace Learner Require: Dataset D = ((x1 , y1 ), . . . , (xn , yn )), privacy parameters εDP , δDP > 0, accuracy parameter α, error probability β. Partition dataset for multiple runs and set parameters. 1: Set K ← CK log(1/α) for universal constant CK ≥ 1. 

log(K/β) + log(K/β) αεDP α2 ′ 1 K 3: Partition D into K equal parts D , . . . , D .

2: Let Dval ⊂ D, such that |Dval | = O



. Set D′ ← D \ Dval .

4: Set η1 ← Cη α, and ηk ← 2k−1 η1 for k ∈ [K] and universal constant Cη > 1.

Run Algorithm 3 on each partition with appropriate parameters. 5: for k = 1 to K do

Set hk := (ŵk , τ̂k ) ← DPSASεDP ,δDP ,ηk (Dk ). 7: end for 6:

Run all hk ’s on Dval and pick the best one using exponential mechanism. 8: Let H ← (h1 , . . . , hK ) 9: Define the score function Score(Dval , hk ) := |D1 | val 10: Set ∆ ← 1/|Dval |. 11: Set h̄ ← ExpMechεDP ,H (Score, ∆, Dval ). 12: Return h̄.

F.1

Privacy

We first prove the privacy guarantees of Algorithm 4. 34

P (x,y)∈Dval

1{sign(ŵk · x + τ̂k ) = y}.

Proposition F.1. Algorithm 4 satisfies (O (εDP ) , O (δDP ))-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 τ̂ , the sensitivity of E(x,y)∼D [y] (the average of all the labels) has sensitivity 2/m0 because the labels can be either −1 or 1. Therefore, adding Laplace noise scaled to 2/εDP m0 satisfies εDP -DP. For computing the initial weight vector ŵ0 , we compute the noisy average of xy over the entire dataset Dinit . Since we clip all the data points to within L in ℓ2 norm, and y is either −1 or 1, thepℓ2 sensitivity of this average is 2L/m0 . Thus, adding Gaussian noise to this average scaled to 2L 2 log(2/δDP )/εDP m0 satisfies (ε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 h i w·x E(x,y)∼D −y1{|w · x − bt | ≤ at }∇w ∥w∥ . Therefore, the sensitivity of this average gradient is at most w·x 2 ∇w ∥w∥

m0

≤

2∥x∥ 2L ≤ . m0 m0

p This implies that adding Gaussian noise to the average scaled to 2L 2 log(2/δDP )/εDP m0 satisfies (εDP , δDP )-DP in each iteration. However, in each iteration, a disjoint dataset gets used, so no data point gets used twice for any DP operation. Hence, by parallel composition, we get (εDP , δDP )-DP for this part, as well. Finally, applying parallel composition over the three steps again, we obtain (εDP , δDP )-DP for Algorithm 3. The guarantees of the exponential mechanism in Algorithm 4 imply εDP -DP because the sensitivity of the mean of 0-1 random variables is 1/|Dval |. Since all the DP steps in Algorithm 4 are taken on disjoint and separate datasets, we obtain the required DP guarantee using parallel composition.

F.2

Relevant Assumptions and Regularity Conditions

For simplicity, we assume that the ambient dimension d is large enough. This assumption can be removed by using the exact expressions for concentration inequalities for high-dimensional Gaussians. Assumption F.2 (Assumption on ambient dimension). We assume the following bound on the ambient dimension in terms of the error probability β ∈ (0, 1) and number of samples n ∈ N: 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) be d-dimensional, and Σ = A⊤ A for A ∈ Rd×d . Then the following holds for all t > 0. p Pr[∥AX∥22 > tr(Σ) + 2 tr(Σ2 )t + 2t∥Σ∥2 ] ≤ e−t p Pr[∥AX∥22 < tr(Σ) − 2 tr(Σ2 )t] ≤ e−t 35

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 X1 , . . . , Xn be i.i.d. samples from a d-dimensional Gaussian N (0, I). Then for β ∈ (0, 1), the following holds with probability at least 1 − β. h √ √ i Pr ∀ i ∈ [n] : ∥Xi ∥ ∈ [ 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 samples. √ In Algorithm 3, we set the clipping parameter L = 2 d to ensure that all data points lie completely within the ℓ2 ball of radius L around the origin, and no point gets actually clipped with high probability.

F.3

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 (Diakonikolas et al., 2022), except that the noisy gradient term has Gaussian noise added in the subspace orthogonal to w (which is a known DP quantity) because the weight vectors get ultimately projected onto the unit ball and the GD algorithm will not move in the direction of w. Therefore, by Pythagoras’ theorem, w − λ∇w L̃t (w) term will still have norm at least 1 as the gradient and the noise belong to the same subspace that is orthogonal to w. √ 4 2d log(2/δDP ) Proof of Claim 4.5. In our algorithm w̃0 = w0 + z0 , where z0 ∼ N (0, σ 2 I), σ = , εDP m0 and w0 is as defined by Diakonikolas et al. (2022) in Algorithm 2. We know from the proof of Theorem 1.2 in (Diakonikolas et al., 2022) that w∗ · w0 > ω(η). Therefore, it is sufficient to bound w∗ ·z0 because w∗ · w̃0 > 0 =⇒ w∗ · ŵ0 > 0. Note that for any fixed unit vector w∗ , w∗ ·z0 ∼ N (0, σ 2 ). Applying concentration inequality for 1-D Gaussians, we get that with probability at least 1 − O (β), √ d log(1/δDP ) log(1/β) ∗ |w · z0 | ≤ O < O (η) by plugging in our bound on the sample complexity. εDP m0

36

Related documents

• Learning Sparse Support under Differential Privacy: Adaptive Algorithms and Minimax Limits#1202286
• Optimal Guarantees for Auditing Rényi Differentially Private Machine Learning#216730
• Differentially Private Model-X Knockoffs via Johnson-Lindenstrauss Transform#974216
• Towards Personalized Differentially Private Learning for Decentralized Local Graphs#343375
• Differential Privacy of Decentralized Learning: Centralized Rate Conditions and Nearly Tight Guarantees#1468095