We give a proper constant-factor agnostic learner for affine halfspaces under full-dimensional log-concave marginals. For arbitrary binary labels, the algorithm uses independent labeled samples and returns a single affine halfspace with error at most COPT+ε. Its sample and real-arithmetic complexity are polynomial in dimension, inverse accuracy, and the logarithm of the reciprocal failure probability. The mean and covariance of the marginal need not be known, and the sample complexity can be made linear in this logarithmic confidence factor. The main geometric result compares global disagreement with disagreement on a balanced restriction: for a minority halfspace of mass p, global disagreement is within universal constant factors of p times conditional disagreement, provided the latter is sufficiently small. To construct the restriction from noisy labels, we estimate the minority cap's mean and covariance robustly, approximately minimize the classical zonoid-depth dual objective, and expand a superlevel set to a marginal quantile. The disagreement comparison cancels the noise amplification caused by conditioning and allows the learned halfspace to be used on the entire space. The analysis combines degree-four sum-of-squares moment bounds for log-concave laws with a translation-based reduction from balanced affine learning to homogeneous halfspace learning.
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.
Giorgio Racca, Amartya Sanyal, Vikrant Singhal
Department of Computer Science, University of Copenhagen
We study the problem of computationally efficient proper agnostic learning of multidimensional concept classes under the Gaussian distribution. In this setting, given i.i.d. labeled samples from an unknown distribution over Rd×{±1} whose marginal on Rd is Gaussian, the goal is to output a hypothesis from a target class F whose 0-1 loss is within ε of that of the best classifier in F. We give the first efficient proper agnostic learning algorithm for arbitrary Boolean functions of K halfspaces under Gaussian marginals. Our algorithm runs in time dO(K2log(1/ε)/ε2)+(K/ε)O(K3/ε2.5). Prior to our work, the only known algorithm for K≥2 was brute-force search, with run-time exponential in d. Moreover, the dependence of our run-time on the dimension d matches that of the best known improper learning algorithm, namely dO(K2/ε2). For the special case of a single halfspace (K=1), the best previous run-time was dO(1/ε4)+(1/ε)O(1/ε6). Our algorithm improves this to dO(1/ε2)+(1/ε)O(1/ε2.5). Once again, the dependence on d matches that of the best known improper algorithm, namely dO(1/ε2). Furthermore, the dependence of our run-time on the dimension d is essentially optimal in the statistical query model.
We study three problems that involve identifying homogeneous halfspaces under Gaussian distributions: agnostic learning, one-sided reliable learning, and fairness auditing. In each of these problems, we are given labeled examples (x,y) drawn from an unknown distribution on Rd×{−1,+1}, whose marginal distribution on x is standard Gaussian and on y is arbitrary. The goal of each problem is to output a homogeneous halfspace that approaches the best-fitting homogeneous halfspace in terms of its corresponding loss measure. We prove near-optimal computational hardness results for these problems under the widely believed hardness assumption of the Learning With Errors (LWE) problem. Prior hardness results for these problems were mostly established for general halfspaces; our findings extend some of these hardness results to homogeneous halfspaces. Remarkably, our lower bound strictly generalizes over prior works and narrows the gap between the upper and lower bounds for agnostically learning homogeneous halfspaces under Gaussian marginals.