We present a private learner for halfspaces over an arbitrary finite domain @math with sample complexity @math . The building block for this learner is a differentially private algorithm for locating an approximate center point of @math 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 [ 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 @math , whereas for pure differential privacy @math .
@cite_19 showed an efficient (non-private) learner for halfspaces that works in (a variant of) the statistical query (SQ) model of @cite_12 . It is known that SQ learners can be transformed to preserve differential privacy , and the algorithm of @cite_19 yields a differentially private efficient learner for halfspaces over examples from @math with sample complexity @math . Another related work is that of @cite_10 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 @cite_10 imply a private learner for halfspaces (due to the types of errors they incur).
@cite_19 @cite_10 @cite_12
2069730673 1995897489
The perceptron algorithm, developed mainly in the machine learning literature, is a simple greedy method for finding a feasible solution to a linear program (alternatively, for learning a threshold function). In spite of its exponential worst-case complexity, it is often quite useful, in part due to its noise-tolerance and also its overall simplicity. In this paper, we show that a randomized version of the perceptron algorithm along with periodic rescaling runs in polynomial-time. The resulting algorithm for linear programming has an elementary description and analysis. In this paper, we study the problem of learning in the presence of classification noise in the probabilistic learning model of Valiant and its variants. In order to identify the class of “robust” learning algorithms in the most general way, we formalize a new but related model of learning from statistical queries . Intuitively, in this model a learning algorithm is forbidden to examine individual examples of the unknown target function, but is given acess to an oracle providing estimates of probabilities over the sample space of random examples. One of our main results shows that any class of functions learnable from statistical queries is in fact learnable with classification noise in Valiant's model, with a noise rate approaching the information-theoretic barrier of 1 2. We then demonstrate the generality of the statistical query model, showing that practically every class learnable in Valiant's model and its variants can also be learned in the new model (and thus can be learned in the presence of noise). A notable exception to this statement is the class of parity functions, which we prove is not learnable from statistical queries, and for which no noise-tolerant algorithm is known.