Private Center Points and Learning of Halfspaces
Amos Beimel Shay Moran Kobbi Nissim Uri Stemmer


Tachyonic  δ-Tsallis entropy of  a thermal tachyonic BIon
     Aroonkumar Beesham^1[beeshama@unizulu.ac.za], Alireza Sepehri^1,2[alireza.sepehri3@gmail.com]
    December 30, 2023
==================================================================================================


We present a private learner for halfspaces over an arbitrary finite domain X⊂^d with sample complexity (d,2^log^*|X|). The building block for this learner is a differentially private algorithm for locating an approximate center point of m>(d,2^log^*|X|) points – a high dimensional generalization of the median function. Our construction establishes a relationship between these two problems that is reminiscent of the relation between the median and learning one-dimensional thresholds [Bun et al. FOCS '15]. This relationship suggests that the problem of privately locating a center point may have further applications in the design of differentially private algorithms.

We also provide a lower bound on the sample complexity for privately finding a point in the convex hull. For approximate  differential privacy, we show a lower bound of m=Ω(d+log^*|X|), whereas for pure differential privacy m=Ω(dlog|X|).








§ INTRODUCTION


Machine learning models are often trained on sensitive personal information, e.g., when analyzing healthcare records or social media data. There is hence an increasing awareness and demand for privacy preserving machine learning technology.
This motivated the line of works on private learning, initiated by <cit.>, which provides strong (mathematically proven) privacy protections for the training data. Specifically, these works aim at achieving differential privacy, a strong notion of privacy that is now increasingly being adopted by both academic researchers and industrial companies. Intuitively, a private learner is a PAC learner that guarantees that every single example has almost no effect on the resulting classifier. Formally, a private learner is a PAC learner that satisfies differential privacy w.r.t. its training data. The definition of differential privacy is,


Let  be a randomized algorithm that operates on databases.
Algorithm  is (,δ)-differentially private if for any two databases S,S' that differ on one row, and any event T, we have 
[(S)∈ T]≤ e^·[(S')∈ T]+δ. 
The notion is referred to as pure differential privacy when δ=0, and approximate differential privacy when δ>0.


The initial work of <cit.> 
 showed that any concept class C is privately learnable with sample complexity O(log |C|) (we omit in the introduction the dependencies on accuracy and privacy parameters). Non-privately, Θ(VC(C)) samples are necessary and sufficient to PAC learn C, and much research has been devoted to understanding how large the gap is between the sample complexity of private and non-private PAC learners. 

For pure differential privacy, it is known that a sample complexity of Θ(log|C|) is required even for learning some simple concept classes such as one-dimensional thresholds, axis-aligned rectangles, balls, and halfspaces <cit.>. That is, generally speaking, learning with pure differential privacy requires sample complexity proportional to log the size of the hypothesis class. For example, in order to learn halfspaces in ^d, one must consider some finite discretization of the problem, e.g. by assuming that input examples come from a finite set X⊆^d. A halfspace over X is represented using d point from X, and hence, learning halfspaces over X with pure differential privacy requires sample complexity Θ(log|X|  d)=O(dlog|X|). In contrast, learning halfspaces non-privately requires sample complexity O(d). In particular, when the dimension d is constant, learning halfspaces non-privately is achieved with constant sample complexity, while learning with pure differential privacy requires sample complexity that is proportional to the representation length of domain elements.

For approximate differential privacy, the current understanding is more limited. 
Recent results established that the class of one-dimensional thresholds over a domain X⊆ requires sample complexity between Ω(log^*|X|) and 2^O(log^*|X|) (<cit.>). 
On the one hand, these results establish a separation between what can be learned with or without privacy, as they imply that privately learning one-dimensional thresholds over an infinite domain is impossible. 
On the other hand, these results show that, unlike with pure differential privacy, the sample complexity of learning one-dimensional thresholds can be much smaller than log|C|=log|X|. <cit.> also established an upper bound of (d·2^log^*|X|) for privately learning the class of axis-aligned rectangles over X⊆^d. 
In a nutshell, this concludes our current understanding of the sample complexity of approximate private learning. In particular, before this work, it was not known whether similar upper bounds (that grow slower than log|C|) can be established for “richer” concept classes, such as halfspaces, balls, and polynomials.



We answer this question positively, focusing on privately learning halfspaces. The class of halfspaces forms an important primitive in machine learning as learning halfspaces implies learning many other concept classes (<cit.>). In particular, it is the basis of  popular algorithms such as neural nets and kernel machines, as well as various geometric classes (e.g., polynomial threshold functions, polytopes, and d-dimensional balls). 



 §.§ Our Results


Our approach for privately learning halfspaces is based on a reduction to the task of privately finding a point in the convex hull of a given input dataset. That is, towards privately learning halfspaces we first design a sample-efficient differentially private algorithm for identifying a point in the convex hull of the given data, and then we show how to use such an algorithm for privately learning halfspaces.



  
Privately finding a point in the convex hull.


We initiate the study of privately finding a point in the convex hull of a dataset S⊆ X⊆^d. Even though this is a very natural problem (with important applications, in particular to learning halfspaces), it has not been considered before in the literature of differential privacy. One might try to solve this problem using the exponential mechanism of <cit.>, which, given a dataset and a quality function, privately identifies a point with approximately maximum quality. To that end, one must first settle on a suitable quality function such that if a point x∈ X has a high quality then this point is guaranteed to be in the convex hull of S. Note that the indicator function q(x)=1 if and only if x is in the convex hull of S is not a good option, as every point x∈ X has quality either 0 or 1, and the exponential mechanism only guarantees a solution with approximately maximum quality (with additive error larger than 1).

Our approach is based on the concept of Tukey-depth <cit.>. Given a dataset S⊆^d,  a point x∈^d has the Tukey-depth at most ℓ if there exists a set A ⊆ S of size ℓ such that x is not in the convex hull of S∖ A. See <ref> for an equivalent definition that has a geometric flavor. Instantiating the exponential mechanism with the Tukey-depth as the quality function results in a private algorithm for identifying a point in the convex hull of a dataset S⊆ X⊆^d with sample complexity (d,log|X|).[We remark that the domain X does not necessarily contain a point with a high Tukey-depth, even when the input points come from X⊆^d. Hence, one must first extend the domain X to make sure that a good solution exists. This results in a private algorithm with sample complexity O(d^3log|X|).] 

We show that this upper bound can be improved to (d,2^log^*|X|). Our construction utilizes an algorithm by <cit.> for approximately maximizing (one-dimensional) quasi-concave functions with differential privacy (see Definition <ref> for quasi-concavity). To that end, we show that it is possible to find a point with high  Tukey-depth in iterations over the axes, and show that the appropriate functions are indeed quasi-concave. This allows us to instantiate the algorithm of <cit.> to identify a point in the convex hull of the dataset one coordinate at a time. We obtain the following theorem.


Let ≤ 1 and δ < 1/2 and let X ⊂^d. There exists an (,δ)-differentially private algorithm that given a dataset S∈ X^m identifies (w.h.p.) a point in the convex hull of S, provided that   
m=|S|=(d,2^log^*|X|,1/,log1/δ).


In fact, our algorithm returns a point with a large Tukey-depth, which is in particular a point in the convex hull of the dataset. This fact will be utilized by our reduction from learning halfspaces, and will allow us to get improved sample complexity bounds on privately learning halfspaces.




  
A privacy preserving reduction from halfspaces to convex hull.
Our reduction can be thought of as a generalization of the results by <cit.>, who showed that the task of privately learning one-dimensional thresholds is equivalent to the task of privately solving the interior point problem. In this problem, given a set of input numbers, the task is to identify a number between the minimal and the maximal input numbers. Indeed, this is exactly the one dimensional version of the convex-hull problem we consider. However, the reduction of <cit.> does not apply for halfspaces, and we needed to design a different reduction.


Our reduction is based on the sample and aggregate paradigm: 
assume a differentially private algorithm  which gets a (sufficiently large) dataset D⊂^d and returns a point in the convex hull of D. 
This can be used to privately learn halfspaces as follows. 
Given an input sample S, partition it to sufficiently many subsamples S_1,…,S_k, 
and pick for each S_i an arbitrary halfspace h_i which is consistent with S_i. Next, apply  to privately find a point in the convex hull of the h_i's (to this end represent each h_i as a point in ^d+1 via its normal vector and bias), and output the halfspace h corresponding to the returned point. It can be shown that if each of the h_i's has a sufficiently low generalization error, which is true if the sample is big enough, then the resulting (privately computed) halfspace also has a low generalization error. 

Instantiating this reduction with our algorithm for the convex hull we get the following theorem.













Let ≤ 1 and δ < 1/2 and let X ⊂^d. There exists an (,δ)-differentially private (α,β)-PAC learner for halfspaces over examples from X with sample complexity 
m=(d,2^log^*|X|,1/α,log1/βδ).


In particular, for any constant d, <ref> gives a private learner for halfspaces over X⊆^d with sample complexity 2^O(log^*|X|). Before our work, this was known only for d=1.



  
A lower bound for finding a point in the convex hull.
Without privacy considerations, finding a point in the convex hull of the data is trivial. Nevertheless, we show that any (,δ)-differentially private algorithm for this task (in d dimensions) must have sample complexity m=Ω(d/log1/δ+log^* | X|). In comparison, our algorithm requires sample of size at least
Õ(d^2.52^O(log^*| X|)/ϵ) (ignoring the dependency on δ and β).

Recall that the sample complexity of privately learning a class C is always at most O(log|C|). Hence, it might be tempting to guess that a sample complexity of m=O(log|X|) should suffice for privately finding a point in the convex hull of a dataset S⊆ X⊆^d, even with pure (,0)-differential privacy. We show that this is not the case, and that any pure (,0)-differentially private algorithm for this task must have sample complexity m=Ω(d/log|X|).



 §.§ Other Related Work

Most related to our work is the work on private learning and its sample and time complexity by <cit.>. As some of these works demonstrate efficiency gaps between private and non-private learning, alternative models have been explored including semi-supervised learning (<cit.>), learning multiple concepts (<cit.>), and prediction (<cit.>, <cit.>).

<cit.> showed an efficient (non-private) learner for halfspaces that works in (a variant of) the statistical query (SQ) model of <cit.>. It is known that SQ learners can be transformed to preserve differential privacy <cit.>, and the algorithm of <cit.> yields a differentially private efficient learner for halfspaces over examples from X⊆^d with sample complexity (d,log|X|). 

Another related work is that of <cit.> who constructed an algorithm for approximately solving linear programs with differential privacy. While learning halfspaces non-privately easily reduces to solving linear programs, it is not clear whether the results of <cit.> imply a private learner for halfspaces (due to the types of errors they incur).






§ PRELIMINARIES


In this section we introduce a tool that enables our constructions, describe the geometric object we use throughout the paper, and present some of their properties. 



  
Notations. 
The input of our algorithm is a multiset S whose elements are taken (possibly with repetition) from a set X. We will abuse notation and write that S ⊆ X. Databases S_1 and S_2 are called neighboring if they differ in exactly one entry. Throughout this paper we use  and δ for the privacy parameters, α for the error parameter, and β for the confidence parameter, and m for the sample size.
In this appendix we define differentially private algorithms and the PAC learning model.



 §.§ Preliminaries from Differential Privacy
 


Consider a database where each record contains information of an individual. An algorithm is said to preserve differential privacy if a change of a single record of the database (i.e., information of an individual) does not significantly change the output distribution of the algorithm. Intuitively, this means that the information infer about an individual from the output of a differentially-private algorithm is similar to the information that would be inferred had the individual's record been arbitrarily modified or removed. Formally:


  
A randomized algorithm  is (,δ)-differentially private if for all neighboring databases _1,_2∈ X^m, and for all sets ℱ of outputs,

    [(_1) ∈ℱ] ≤exp() ·[(_2) ∈ℱ] + δ,

where the probability is taken over the random coins of . 
When δ=0 we omit it and say that  preserves -differential privacy.

We use the term pure differential privacy when δ=0 and the term approximate differential privacy when δ>0, in which case δ is typically a negligible function of the database size m.

We will later present algorithms that access their input database using (several) differentially private algorithms. We will use the following composition theorems. 


If _1 and _2 satisfy (_1,δ_1) and (_2,δ_2) differential privacy, respectively, then their concatenation (S)=⟨_1(S),_2(S) ⟩ satisfies (_1+_2,δ_1+δ_2)-differential privacy.


Moreover, a similar theorem holds for the adaptive case, where an algorithm  uses  k adaptively chosen differentially private algorithms (that is, when the choice of the next differentially private algorithm that is used depends on the outputs of the previous differentially private algorithms).


An algorithm that adaptively uses k  algorithms that preserves (/k,δ/k)-differential privacy (and does not access the database otherwise) ensures (,δ)-differential privacy.


Note that the privacy guaranties of the above bound deteriorates linearly with the number of interactions. By bounding the expected privacy loss in each interaction (as opposed to worst-case), <cit.> showed the following stronger composition theorem, where privacy deteriorates (roughly) as √(k)+k^2 (rather than k).


Let 0<_0,δ'≤1, and let δ_0∈[0,1]. An algorithm that adaptively uses k algorithms that preserves (_0,δ_0)-differential privacy (and does not access the database otherwise) ensures (,δ)-differential privacy, where =√(2kln(1/δ'))·_0+2k_0^2 and δ = kδ_0+δ'.





 §.§ Preliminaries from Learning Theory


We next define the probably approximately correct (PAC) model of <cit.>.
A concept c:X→{0,1} is a predicate that labels examples taken from the domain X by either 0 or 1.  A concept class C over X is a set of concepts (predicates) mapping X to {0,1}. A learning algorithm is given examples sampled according to an unknown probability distribution  over X, and labeled according to an unknown target concept c∈ C. The learning algorithm is successful when it outputs a hypothesis h that approximates the target concept over samples from . More formally:


The generalization error of a hypothesis h:X→{0,1} is defined as 

    _(c,h)=_x ∼[h(x)≠ c(x)].
 
If _(c,h)≤α we say that h is α-good for c and .



Algorithm  is an (α,β,m)-PAC learner for a concept
class C over X using hypothesis class H if for all 
concepts c ∈ C, all distributions  on X,
given an input of m samples =(z_1,…,z_m), where z_i=(x_i,c(x_i)) and each x_i
is drawn i.i.d. from , algorithm  outputs a
hypothesis h∈ H satisfying

    [_(c,h)  ≤α] ≥ 1-β,

where the probability is taken over the random choice of
the examples in  according to  and the random coins  of the learner .
If H⊆ C then  is called a proper PAC learner; otherwise, it is called an improper PAC learner.



For a labeled sample =(x_i,y_i)_i=1^m, the empirical error of h is

    _S(h) = 1/m |{i : h(x_i) ≠ y_i}|.






























































 §.§ Private Learning

Consider a learning algorithm  in the probably approximately correct (PAC) model of <cit.>. We say that  is a private learner if it also satisfies differential privacy w.r.t. its training data. Formally,


Let  be an algorithm that gets an input =(z_1,…,z_m), where each z_i is a labeled example. Algorithm  is an (,δ)-differentially private (α,β)-PAC learner with sample complexity m for a concept
class C over X using hypothesis class H if


  * Privacy. Algorithm  is (,δ)-differentially private (as in  <ref>);

  * Utility. Algorithm  is an (α,β)-PAC learner for C with sample complexity m using hypothesis class H (as in  <ref>).




Note that the utility requirement in the above definition is an average-case requirement, as the learner is only required to do well on typical samples (i.e., samples drawn i.i.d. from a distribution  and correctly labeled by a target concept c∈ C). In contrast, the privacy requirement is a worst-case requirement, which must hold for every pair of neighboring databases (no matter how they were generated, even if they are not consistent with any concept in C).





 §.§ A Private Algorithm for Optimizing Quasi-concave Functions – 

We next describe properties of an algorithm  of <cit.>. This algorithm
is given a quasi-concave function Q (defined below) and privately finds a point x such that Q(x) is close to its maximum provided that the maximum of Q(x) is large enough
(see (<ref>)). 
   
 
A function Q(·) is quasi-concave if Q(ℓ) ≥minQ(i),Q(j) for every i < ℓ  < j.


 The sensitivity of a function f : X^m → is the smallest k such that for
every neighboring D,D' ∈ X^m, we have |f(D)-f(D')
| ≤ k.











Let Q:X^*×X̃→ be a sensitivity-1 function (that is, for every x ∈X̃, the function
Q(·,x) has sensitivity 1).
Denote T̃=|X̃| and let α≤1/2 and  β,,δ,r be parameters.
There exits an (,δ)-differentially private algorithm, called , such that the following holds.
If  is executed on a database S∈ X^* such that Q(S,·) is quasi-concave and in addition

    max_i∈X̃{Q(S,i)}≥ r ≥
    8^log^* T̃·12 log^* T̃/αlog(192(log^* T̃)^2/βδ),

then with probability at least 1-β the algorithm outputs an index j s.t. 
Q(S,j)≥(1-α)r.



We next present an alternative definition of quasi-concave functions that is more convenient to use.

Let i_ max be a value such that Q(i_ max) is maximal.
A function Q(Â·) is quasi-concave if and only if Q(i) ≤ Q(j) for all i,j∈X̃ such that i < j < i_ max or i_ max < j < i.



  * The function is non-decreasing  before i_ max, that is 
Q(i) ≤ Q(j) for every i,j∈X̃ such that i < j < i_ max, and

  * The function is non-increasing after i_ max, that is 
Q(i) ≥ Q(j) for every i,j∈X̃ such that i_ max < i < j.

 



Let {f_t}_t∈𝒯 be a finite family of quasi-concave functions. Then, f(x)=min_t∈𝒯f_t(x) is also quasi-concave.




Let i ≤ℓ≤ j. Then,

    f(ℓ)    =min_t∈𝒯f_t(ℓ)
       ≥min_t∈𝒯{min{f_t(i),f_t(j)}}f_t is quasi-concave, ∀ t∈𝒯
       = min{min_t∈𝒯f_t(i),min_t∈𝒯 f_t(j)}
       =min{f(i),f(j)}.





















































	
	
















 §.§ Halfspaces, Convex Hull, and Tukey Depth


We next define the geometric objects we use in this paper.












Let X ⊂^d. 
For a_1,…,a_d,w∈, let the halfspace

_a_1,…,a_d,w:X →{0,1}
be defined as _a_1,…,a_d,w(x_1,…,x_d)=1 if and only if  ∑_i=1^d a_i x_i ≥ w. Define the concept class (X) = {_a_1,…,a_d,w}_a_1,…,a_d,w ∈.
We say that a halfspace  contains a point x∈^d if (x)=1.
The hyperplane _a_1,…,a_d,w defined by a_1,…,a_d,w is the set of all points x=(x_1,…,x_d) such that ∑_i=1^d a_i x_i = w.





Let S⊂^d be a finite multiset of points. A point x∈^d is in the convex hull of S if x is a convex combination of the elements of S, that is, there exists non-negative
numbers a_y_y∈ S such that




∑_y∈ S a_y =1 and

∑_y∈ S a_yy=x.



We next define the Tukey median of a point, which is a generalization of a median to ^d.

Let S⊂^d be a finite multiset 
of points. The Tukey depth of a point x∈^d with respect to S, denoted by (x), is the minimum number of points in S contained in a halfspace containing  the point x,
that is, 

    (x)=min_∈_d,T ,(x)=1|y∈ S:(y)=1|.

The Tukey median of S is a point maximizing the Tukey depth. A centerpoint is a point of depth at least |S|/(d + 1). 




The Tukey depth of a point is a sensitivity one function of the 
multiset S.


this definition is not clear to me We say that the direction (a_1,…,a_d)
is in general position with respect to S
if the numbers ∑_i a_iy_i are distinct
when (a_1… a_d) ranges over all points in S. should this be “(y_1… y_d) ranges over all points in S”??
The definition says that no two vectors in S have the same inner product with (a_1,…, a_d). Would it be clearer if stated this way? 
I needed this definition in order to fix the sensitivity argument by Amos, but Uri wanted to use an alternative argument which does not require this definition and then we can remove it.
Note that since S is finite, a standard perturbation argument implies thatthis argument holds because the set S is finite, right? if correct, let's mention this.added.
every halfspace  can be written as
_a_1,…,a_d,w where the direction
(a_1,…,a_d) is in general position with respect to S.
Let 𝖦𝖯(S)⊆ℝ^d denote the set of all directions
that are in general position with respect to S.


[Tukey depth, alternative definition]
Let S⊂^d be a multiset of points. 
For a given a_1,…,a_d∈ define the function

    t_a_1,…,a_d(w)≜min|{(y_1,…,y_d)∈ S: ∑_i=1^d a_i y_i ≥ w}|,|{(y_1,…,y_d)∈ S: ∑_i=1^d a_i y_i ≤ w}|.

Then, 


    (x_1,…,x_n)=min_(a_1,…,a_d)∈t_a_1,…,a_d(∑_i=1^d a_i x_i ).





[Tukey depth, another alternative definition]
Let S⊂^d be a multiset of points. 
The Tukey-depth of a point x is the size of the smallest set A ⊆ S such that x is not in the convex-hull of S ∖ A. 



[<cit.>]
Let S⊂^d be a multiset of points. 
There exists x∈^d such that (x) ≥ |S|/(d + 1). 


Thus, a centerpoint always exists and a Tukey median must be a centerpoint. However, not every centerpoint is a Tukey median. 

We will use the following regarding the set of points of all points whose Tukey depth is at least r.
[see e.g. <cit.>]
Let S⊆^d be a multiset of points and r > 0. 
Define (r) = {x∈ℝ^d : (x) ≥ r}.
Then (r) is a polytope whose faces are supported by affine subspaces 


that are spanned by points from S.

So, for example the set of all Tukey medians is a polytope and if it is d-dimensional then each of its facet is
supported by a hyperplane that passes through d+1 points from S.




§ FINDING A POINT IN THE CONVEX HULL




Our goal is to privately find a point in the convex hull of a set of input points (i.e., the database). We will actually achieve a stronger task and find a point whose Tukey depth is at least |S|/2(d+1) (provided that |S| is large enough). Observe that x is in the convex hull of S if and only if (x) >0. As we mentioned in the introduction, finding a point whose Tukey depth is high results in a better learning algorithms for halfspaces.

The idea of our algorithm is to find the point x=(x_1,…,x_d) coordinate after coordinate: we
use  to find a value x^*_1 that can be extended by some x_2,…,x_d so that the depth of (x_1^*,x_2…,x_d) is close to the depth of the Tukey median, then we find a value x_2^* so that there is a point (x^*_1,x_2^*,x_3…,x_d) whose depth is close to the depth of the Tukey median, and so forth until we find all coordinates.  The parameters in  are set such that in each step we lose depth of at most n/2(d+1)^2 compared to the Tukey median, resulting in a point  (x^*_1,…,x^*_d) whose depth is at most n/2(d+1) less than the depth of the Tukey median, i.e., its depth is at least n/2(d+1).    



 §.§ Defining a Quasi-Concave Function


To apply the above approach, we need to prove that the functions considered in the algorithm 
are quasi-concave.

For every 1 ≤ i ≤ d and every x^*_1,…,x^*_i-1∈, define

    Q_x^*_1,…,x^*_i-1(x_i)≜max_x_i+1,…,x_d ∈ (x^*_1,…,x^*_i-1, x_i,…,x_d).





















We next prove that Q_x^*_1,…,x^*_i-1(x_i) is quasi-concave. Towards this goal, 
we first prove that the function t_a_1,…,a_d(w), defined in <ref>, is quasi-concave.




For every  a_1,…,a_d∈,  the function
t_a_1,…,a_d(w) is quasi-concave.


Define
f_1(w) = |{(y_1,…,y_d)∈ S: ∑_i=1^d a_i y_i ≥ w}|, and 
f_2(w) = |{(y_1,…,y_d)∈ S: ∑_i=1^d a_i y_i ≤ w}|. Note that t_a_1,…,a_d(w) = min{f_1(w),f_2(w)}.
These functions count the number of points in S on the two (closed) sides of the hyperplane _a_1… a_d,w.
The claim follows by Claim <ref> since both f_1,f_2 are quasi-concave
(in fact, both are monotone).








We next prove that the restriction of the Tukey depth function to a line is quasi-concave.
This lemma is implied by Fact <ref> (implying that the set of points whose Tukey depth is at least r is convex). For completeness, we supply a full proof of the claim.



Fix α_1,…,α_d,β_1,…,β_d ∈, and define
_α_1,…,α_d,β_1,…,β_d (t)=(α_1 t+β_1,…,α_d t+β_d ).
The function
_α_1,…,α_d,β_1,…,β_d is  quasi-concave.


Let t_0 < t_1 < t_2 and let (a_1,…,a_d) be a direction that minimizes (α_1 t_1+β_1,…,α_d t_1+β_d ) in (<ref>),
i.e.,
_α_1,…,α_d,β_1,…,β_d (t_1)=(α_1 t_1+β_1,…,α_d t_1+β_d )=t_a_1,…,a_d(∑_i=1^d a_i (α_i t_1+β_i) ).
Consider the function which maps t to ∑_i=1^d a_i (α_i t +β_i)= (∑_i=1^d a_i α_i)t+∑_i=1^d a_i β_i. This function is either increasing or decreasing, thus, by Claim <ref>,

    _α_1,…,α_d,β_1,…,β_d (t_1)     =    t_a_1,…,a_d(∑_i=1^d a_i (α_i t_1+β_i) )
       ≥   mint_a_1,…,a_d(∑_i=1^d a_i (α_i t_0 +β_i) ),
             t_a_1,…,a_d(∑_i=1^d a_i (α_i t_2+β_i) )
       ≥   min( α_1 t_0 +β_1,…, α_d t_0 +β_d),
             ( α_1 t_2 +β_1,…, α_d t_2 +β_d)
        =    min_α_1,…,α_d,β_1,…,β_d (t_0),_α_1,…,α_d,β_1,…,β_d (t_1).



For every 1 ≤ i ≤ d and every x^*_1,…,x^*_i-1∈, the function
Q_x^*_1,…,x^*_i-1(x_i) is a quasi-concave function. Furthermore, Q_x^*_1,…,x^*_i-1(x_i) is a sensitivity 1 function of the multiset S.


Let x_i^0,x_i^1,x_i^2 such that x_i^0 < x_i^1 < x_i^2.
Furthermore, let x_i+1^0,…,x_d^0 and x_i+1^2,…,x_d^2 be points
maximizing the functions (x^*_1,…,x^*_i-1,x_i^0,·,…,·) and (x^*_1,…,x^*_i-1,x_i^2,·,…,·) respectively, that is,
Q_x^*_1,…,x^*_i-1(x_i^b)=(x^*_1,…,x^*_i-1,x_i^b,x_i+1^b,…,x_d^b) for b∈{0,2}. 


Consider the line L:→^d passing through the points (x^*_1,…,x^*_i-1,x_i^b,x_i+1^b,…,x_d^b) 

for b∈{0,2},
and scale its parameter such that L(x_i^b)=(x^*_1,…,x^*_i-1,x_i^b,x_i+1^b,…,x_d^b).

That is, let 

    α_j={[                           0              if  1≤ j ≤ i-1;                           1                   if  j = i; (x_j^0-x_j^2)/(x_i^0-x_i^2)             if  i+1 ≤ j ≤ d ].
 
and 

    β_j={[                                  x^*_j                         if  1≤ j ≤ i-1;                                      0                              if  j = i; (x_i^0 x_j^2-x_i^2x_j^0)/(x_i^0-x_i^2)                        if  i+1 ≤ j ≤ d ].
 
and define L(t)=(α_1 t+β_1,…,α_dt+β_d). 



In particular, for every x∈ the i'th coordinate in L(x) is x.
By Claim <ref> and the definition of Q_x^*_1,…,x^*_i-1,

    Q_x^*_1,…,x^*_i-1(x_i^1) ≥(L(x_i^1)) 
    ≥min(L(x_i^0)), (L(x_i^2))
    = Q_x^*_1,…,x^*_i-1(x_i^0), Q_x^*_1,…,x^*_i-1(x_i^2).


The fact that Q_x^*_1,…,x^*_i-1 has sensitivity 1 is implied by Observation <ref> and the fact that maximum of sensitivity 1 functions is a sensitivity 1 function.




 §.§ Extending the Domain


The input to the private algorithm for finding a point in the convex hull is a dataset of points 
S ⊆ X, where  X is a finite set whose size is at most T.
We note that the dataset S may contain several copies of the same point (i.e. it is a multiset).
By the results of <cit.>, the restriction to subsets of a finite set X is essential (even when d=1).  

Notice that a Tukey median of S might not be a point in X.
Furthermore, the proof that the functions Q_x^*_1,…,x^*_i-1 are  quasi-concave is over the reals.
Therefore, we extend the domain to X̃=∏_i=1^dX̃_̃ĩ 
such that for every dataset S the functions Q_x^*_1,…,x^*_i-1 attain their maximum over the extended domain. 
We will not try to optimize the size of X̃_̃1̃, …, X̃_̃d̃ 
as the dependency of the sample complexity of  on |X̃_̃ĩ| is 2^O(log^* |X̃_̃ĩ|).  


There exists sets X̃_̃1̃, …, X̃_̃d̃ such that
|X̃_̃ĩ| ≤ (dT^d^2(d+1))^2^d for 1 ≤ i ≤ d and
for every dataset S, 
for every 1 ≤ i ≤ d, and for every x^*_1,…,x^*_i-1∈X̃_̃1̃×…×X̃_̃ĩ-̃1̃, there exist  
x^m_i,…,x^m_d∈X̃_̃ĩ×…×X̃_̃d̃ such that

    max_x_i+1,…,x_d ∈ (x^*_1,…,x^*_i-1, x_i,…,x_d)
    = (x^*_1,…,x^*_i-1, x^m_i,…,x^m_d).






For 1≤ i ≤ d, let X_i be the projection of X to the ith coordinate, that is, 
    X_i=x: ∃_x_1,…,x_i-1,x_i+1,…,x_d (x_1,…,x_i-1,x,x_i+1,…,x_d) ∈ X .


The construction heavily exploits <ref>.
Let L denote the set of all affine subspaces that are spanned by points in X_1×⋯× X_d.
Since each such subspace is spanned by at most d+1 points, it follows that | L |≤T^d  d+1≤ T^d(d+1).
By <ref>, for every dataset S and every r>0, 
every vertex of (r) can be written as the intersection of at most d subspaces in L. 
In particular, there exists a Tukey median that is the intersection of at most d subspaces in L.

We construct the sets in iterations where 
we start with X̃_̃j̃=∅ for every 1 ≤ j ≤ d.
In iteration i we do the following: for every x^*_1,…,x^*_i-1∈X̃_1×…×X̃_i-1
and for every d-i subspaces in L such that there exists a unique point x = (x^*_1… x^*_i-1,x_i…,x_d)
in the intersection of these d-i subspaces, we add x_j to X̃_j for all j≥ i.

We next argue that item (ii) in the conclusion of the claim is satisfied:
indeed, by <ref>, this construction contains a vertex of every set of the form 
(r) ∩{x∈^d: x_1 = x^*_1,… x_i-1=x^*_i-1},
for every r>0, i≤ d, and every (x^*_1,…,x^*_i-1)∈X̃_1×…×X̃_i-1.
In particular, by plugging 

    r= max_x_i+1,…,x_d ∈ (x^*_1,…,x^*_i-1, x_i,…,x_d),

it contains a point which satisfies <ref>.
This implies item (ii).

As for item (i), note that the size of X̃_1 is at most | L| d≤ T^d^2(d+1).
Similarly, for i > 1:

    |X̃_i|≤| L| d + | L| d-1|X̃_1| + … 
    + | L| d-i∏_j=1^i-1|X̃_j|≤( d·| L| d)^2^d≤ (dT^d^2(d+1))^2^d.








 §.§ The Algorithm

In <ref>, we present an (,δ)-differentially private algorithm  that with probability at least 1-β finds a point whose Tukey depth is at least n/2(d+1). The informal description of the algorithm appears in the beginning of <ref>.



Let ≤ 1 and δ < 1/2 and X ⊂^d be a set of size at most T.
Assume that the input dataset S⊆ X satisfies 


    |S| =O(d^2.5· 2^O(log^*T +log^*d)log^0.5(1/δ) log(d^2/βδ)/).

Then,  is an (,δ)-differentially private algorithm


that with probability at least 1-β returns a point x^*_1,…,x^*_d such that 
(x^*_1,…,x^*_d)≥| S|/2(d+1).  




The proof of the correctness (utility) of  is proved by induction,
using the correctness of . The privacy proof follows
from the privacy of  and using the advanced composition theorem (<ref>).



  
Utility.
We prove by induction that after step i of the algorithm, with probability at least 1-iβ/d, 
the returned values x^*_1,…,x^*_i satisfy
Q_x^*_1,…,x^*_i-1(x^*_i)≥| S|/d+1(1-i/2d),  i.e., there are (x_i+1,…,x_d)∈X̃_i+1×…×X̃_d 
such that (x^*_1,…,x^*_i,x_i+1,…,x_d)≥| S|/d+1(1-i/2d).


The basis is the induction is i=0: by Claim <ref> the Tukey median has depth at least | S|/(d+1)
and by  Claim <ref>, the median is in X̃_1×⋯×X̃_d.
Thus, with probability 1 there are (x_1,…,x_d)∈X̃_1×…×X̃_d 
such that (x_1,…,x_d)≥| S|/d+1.












Next, by the induction hypothesis for i-1,
with probability at least 1-(i-1)β/d it holds that

    max_x∈X̃_̃ĩ{Q_x^*_1,…,x^*_i-1(x)}≥| S|/d+1-(i-1)| S|/2d(d+1)=r > | S|/2(d+1)≥
    8^log^* T̃·12 log^* T̃/α_0_0log(192(log^* T)^2/β_0δ_0).




Therefore, by <ref>, with probability at least 
(1-β/d)(1-(i-1)β/d)≥ 1 - iβ/d Algorithm
 returns x^*_i∈X̃_i such that 

    Q_x^*_1,…,x^*_i-1(x^*_i)≥ (1-α)r=(1-1/2d)| S|/d+1(1-i-1/2d)>| S|/d+1(1-i/2d).


To conclude, after d steps of the algorithm, (x^*_1,…,x^*_d)≥| S|/2(d+1) with probability at least 1-β. 



  
Privacy.
By <ref>, each invocation of  is
(_0,δ_0)-differentially private.  
invokes  d times. 
Thus, by <ref> (the advanced composition) with δ'=δ/2,
it follows that  is (/2+^2/4ln (2/δ),δ) differentially-private,
which implies (,δ)-privacy whenever ≤ 1 and δ≤ 1/2.


















§ LEARNING HALFSPACES USING CONVEX HULL
 

We describe in <ref> a reduction from learning halfspaces to finding a point in a convex-hull of a multiset of points. Furthermore, we show that if  
the algorithm we use in the reduction finds a point whose Tukey depth is high (as our algorithm from <ref> does), then the required sample complexity of the learning algorithm is reduced. As a result, we get  
an upper bound of Õ(d^4.52^log^*|X| ) on the sample complexity of private learning halfspaces (ignoring the privacy and learning parameters). 
In comparison, using the exponential mechanism of <cit.> results in an (,δ)-deferentially private algorithm whose sample complexity is O(d log |X|), e.g., for the interesting case where X=[T]^d for some T, the complexity is O(d^2 log T). 
Our upper bound is better than the sample complexity of the exponential mechanism when d is small compared to log |T|, in particular when d is constant. 









We start by showing the existence of a set H that is used by the algorithm. We say that a vector (a_1,… ,a_d,w)∈^d+1 represents a halfspace ∈(X)
if (x)=_a_1,…, a_d,w(x) for every x∈ X.
Note that every ∈(X) has many representations.




There exists a set H ⊆^d+1, where | H|≤ 2| X |^d+1
which contains  one representation of each halfspace ∈(X).


By standard 
bounds from discrete geometry, |(X) |≤ 2| X |^d+1 (see, e.g. <cit.>).
For each ∈(X) pick a representation (a_1… a_d,w)∈^d+1.



Assume that Algorithm  used in step <ref> of Algorithm  is an (,δ)-differentialy private algorithm  that finds with probability at least 1-β a point in a convex hull for a multisets S ⊆ X ⊂^d whose Tukey depth is at least r provided that 
|S| ≥ m(d,|X|,,δ,β) for some function m(·,·,·,·,·).

Let ≤ 1, δ≤1/2 and α,β≤ 1 be the privacy and utility parameters.
Then,  is an (,δ)-differentially private (α,β)-PAC learner with sample complexity s for the class (X) for

    s=O( m^2· dlog(m/rα) + log(m/β)/rα)

where m=m(d+1,2|X|^d+1,,δ,β/2).






We first establish the privacy guarantee of the algorithm 
and later argue that it PAC-learns (X).





  
Privacy.
Let S^1,S^2 be two neighboring input samples of size at least s, where s is as in the theorem statement.
Let H_0(S^1),H_0(S^2) denote the list of halfspaces that are derived in step <ref> of the algorithm
when it is applied on S^1,S^2.
Since the h_i's are constructed from mutually disjoint subsamples
it follows that the datasets H_0(S_1) and H_0(S_2) are neighbors.
The (,δ)-privacy guarantee now follows from the privacy gurantee of 
since the size of the H_0(S^i)'s is m=m(d+1,2|X|^d+1,,δ,β/2).



  
Utility.
We next establish that the algorithm learns (X) with confidence 1-β and error α.
Let  denote the target distribution and c∈(X) denote the target concept.
Let S denote the input sample of size at least s that is sampled independently from  and labeled by c.

We first claim that every halfspace h_i∈ H_0 the probability  h_i has error greater than rα/m with respect to the distribution  is at most β/2m.
This follows directly from standard bounds on the (non-private) sample complexity of PAC learning of VC classes,
since the VC dimension of (X) is at most d+1
and since each S_i has size Ω(dlog(1/α') + log(1/β')/α')
where α'=rα/m and β'=β/2m (see e.g. Theorem 6.8 in <cit.>).

We next claim that if h ∈^d+1 errs on a point x=(x_1,…,x_d) then at least r halfspaces in H_0 err on x.
By the assumption in the theorem,  outputs with probability at least 1-β/2 a halfspace h whose Tukey depth is at least r with respect to H_0.
By duality, the set of all halfspaces that err on x is
itself a halfspace in ^d+1 that contains all points
(a_1,…,a_d,w)∈^d such that 𝗌𝗂𝗀𝗇(∑_i=1^d x_i a_i - w) ≠ c(x). Denote this halfspace by h_err.
By assumption, h∈ h_err. 
Thus, since the Tukey Depth of h with respect to H_0 is at least r,
at least r of the halfspaces in H_0 are in h_err,
as required.


We are ready to establish the PAC-learning guarantee.
Assume that _(c,h_i) ≤ rα/m for every  1≤ i ≤ m and that  returns a point whose Tukey rank is at most r.
By the argument above and the union bound, this happens with probability at least 1-β.
Let E_h:X→{0,1} denote the indicator the h errs (i.e. E_h(x)=1 if and only if h(x)≠ c(x)).
Similarly, let E_h_i denote the indicator that h_i∈ H_0 errs.


For every x∈ X:
E_h(x) ≤1/r∑_i=1^m E_h_i(x)
(either E_h(x)=0 or E_h(x)=1 and ∑_i=1^m E_h_i(x)≥ r). 
Therefore, by taking expectation over both sides it follows that with probability at least 1-β: 
_(c,h) = _x∼[E_h(x)] ≤_x∼[1/r∑_i=1^m E_h_i(x)]=
1/r∑_i=1^m_(c,h_i) ≤m/r·(rα/m)= α,
as required.




Using  in step <ref> of Algorithm ,
we get the following corollary (which follows from <ref> and <ref>).


Let ≤ 1, δ <1/2, and X⊆^d be a set.
There exists an (,δ)-differentially private (α,β)-PAC learner with sample complexity s for (X) 
with

    s =  Õ(d^4.52^O(log^*|X| +log^*d)log^1.51/δlog^2 1/β/α).





Corollary <ref> establishes an upper bound on the sample complexity of privately learning halfspaces
whose dependency on the domain size |X| is 2^Olog^*(|X|).
The crux of the algorithm is a reduction to privately publishing a point with a large Tukey depth with respect to a given input dataset.
A drawback of this approach is that the latter task is likely to be computationally difficult (even without privacy constraints), unless the dimension d is constant
 (see <cit.> and references within).

In  we can use an algorithm   that finds a point in the convex hull (i.e., a point whose Tukey depth is at least 1).
The resulting learning algorithm require sample complexity of O(m^2· dlog(m/α) + log(m/β)/α),
where m is the sample complexity of . This may result in a more efficient private learning algorithm for halfspaces as the task of privately finding a point in the convex hull might be easier than the task of privately finding a point with high Tukey degree. Furthermore, in this case, we can use an algorithm that privately finds a hypothesis that is a linear combination with positive coefficients of the hypotheses in H_0. This follows from the observation that if all hypotheses in H_0 are correct on a point x, then any  linear combination with positive coefficients of the hypotheses in H_0 is correct of x.







§ A LOWER BOUND ON THE SAMPLE COMPLEXITY OF PRIVATELY FINDING A POINT IN THE CONVEX HULL


In this section we show a lower bound on the sample complexity of privately finding a point in the convex hull of a database S⊆ X = [T]^d.
We show that any (,δ)-differentially private algorithm for this task must have sample complexity Ω(d/log1/δ).
Our lower bound actually applies to a possibly simpler task of finding a
non-trivial linear combination of the points in the database.

By <cit.>, finding a point in the convex hull (even for d=1) requires sample complexity Ω(log^* T). Thus, together we get a lower bound on the sample complexity of
Ω(d/log1/δ+log^* T).


It may be tempting to guess that, even with pure (,0)-differential privacy, a sample complexity of O(log |X|) = O(dlog T) should suffice for solving this task, as the size of the output space is T^d, because S⊆ [T]^d, and hence (it seems) that one could privately solve this problem using the exponential mechanism of <cit.> with sample complexity that depends logarithmically on the size of the output space. We show that this is not the case, and that any (,0)-differentially private algorithm for this task must have sample complexity Ω(d^2/log T). 




Let T≥2, and d≥10. Let  be an (,δ)-differentially private algorithm that takes a database S⊆ [T]^d of size m and returns, with probability at least 1/2, 

a non-trivial linear combination of the points in S. Then,

    m=Ω(
    min{d^2/log T, d/log1/δ}).



The proof of Theorem <ref> builds on the analysis of <cit.> for lower bounding the sample complexity of releasing approximated answers for counting queries. 


Throughout this proof, we use (S) to denote the set of all non-trivial linear combinations of the points in S. 
Let I={x_1,x_2,…,x_d/2,x'} be a multiset of random points, where each point is chosen independently and uniformly from [T]^d. Also let i be chosen uniformly from {1,2,…,d/2}. Now define the database S containing 2m/d copies of each of x_1,…,x_d/2 and define the database S' containing 2m/d copies of each of x_1,…, x_i-1,x_i+1,…x_d/2,x'. Note that S,S' differ in exactly 2m/d points.



Observe that the points in I are linearly independent with high probability. To see this note that any set V
of size at most d/2 spans at most T^d/2 vectors in [T]^d: indeed, without loss of generality
we may assume that V is independent and therefore
can be completed to a basis ^d by adding d-| V|≥ d/2 unit vectors (since the dimension of V is at most d/2 there is at least one unit vector that it does not span, add this vector to V and continue). Without loss of generality, these unit vectors are e_1,…,e_d/2. Thus, every choice from [T]^d/2 for the last d/2 coordinates can be completed in a most one way to a vector spanned by V (because every element of ^d may be written in a unique way as a linear combination of elements of the resulting basis). This means that a set of (at most) d/2 points spans at most T^d/2 vectors in [T]^d. Hence, by a union bound, the probability that the points in I are not independent is at most d/2· T^-d/2.





Let (b,I) be a procedure that operates on a point b and a set of points I, defined as follows. If I is not linearly independent, or if b∉(I), than the procedure outputs . Otherwise the procedure returns the point x∈ I with the largest coefficient when representing b as a linear combination of the points in I (ties are broken arbitrarily).
Observe that if b∈(S) for a subset S⊆ I and if the points in I are linearly independent then (b,I)∈ S. Let β denote the probability that (S) fails to return a point in (S).  As i is uniform on {1,2,…,d/2} we have

    _I,i,[( (S), I )=x_i]
       ≥_I,[
    [ I  is independent,;            (S)∈(S) ]]
    ·_I,i,[( (S), I )=x_i| 
    [ I  is independent,;            (S)∈(S) ].]
       ≥(1-β-d/2· T^-d/2)·2/d≥1/2d ,

where the second inequality is implied by the fact that i is chosen with uniform distribution from a set of size d/2 and the last inequality is by asserting that β≤1/2, T≥2, and d≥10.

On the other hand observe that if ( (S'), I )=x_i then

	
	(1) (S')∈(I), as otherwise  outputs ,
	(2) I is linearly independent, as otherwise  outputs , and
	(3) (S')∉(I∖{x_i}), as otherwise the coefficient of x_i in (S') is 0, and  will not output x_i.


Let I_-i=I∖{x_i}=x_1,…,x_i-1,x_i+1,…,x_d/2,x' and b←(S'). 
We have that

    _I,i,[( b, I )=x_i]   ≤_I,i,[b∈(I)  and b∉(I_-i)  and  I  is independent ]
    
    
       ≤_I,i,[x_i∈(I_-i∪{b})] 
    
     ≤  T^-d/2,

where the 
last inequality is because x_i is independent of I_-i and b (recall that we denoted b←(S'), and hence, b is a (random) function of I_-i, which is independent of x_i). 

Therefore, by the privacy guarantees of  we get

    1/2d   ≤_I,i,[( (S), I )=x_i]=∑_I,i[I,i]·_[( (S), I )=x_i]
       ≤∑_I,i[I,i]·(e^2 m/d·_[( (S'), I )=x_i]+e^2 m/d· 2δ m/d)
       =e^2 m/d·_I,i,[( (S'), I )=x_i]+e^2 m/d· 2δ m/d
       ≤ e^2 m/d· T^-d/2+e^2 m/d· 2δ m/d.

Solving for m, this means that 
m=Ω(
min{d^2/log T, d/log1/δ}.








abbrvnat



