Attribute-Efficient PAC Learning of Sparse Halfspaces with Constant Malicious Noise Rate

• URL: http://arxiv.org/abs/2505.21430v1
• Date: Tue, 27 May 2025 17:02:28 GMT
• Title: Attribute-Efficient PAC Learning of Sparse Halfspaces with Constant Malicious Noise Rate
• Authors: Shiwei Zeng, Jie Shen,
• Abstract summary: Attribute-efficient learning of sparse halfspaces has been a fundamental problem in machine learning theory.<n>In this paper, we consider that there exists a constant amount of malicious noise in the data and the goal is to learn an underlying $s$-sparse halfspace.<n>Under such conditions, we show that attribute-efficiency can be achieved by simple variants to existing hinge loss minimization programs.
• Score: 10.550885570889527
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Attribute-efficient learning of sparse halfspaces has been a fundamental problem in machine learning theory. In recent years, machine learning algorithms are faced with prevalent data corruptions or even adversarial attacks. It is of central interest to design efficient algorithms that are robust to noise corruptions. In this paper, we consider that there exists a constant amount of malicious noise in the data and the goal is to learn an underlying $s$-sparse halfspace $w^* \in \mathbb{R}^d$ with $\text{poly}(s,\log d)$ samples. Specifically, we follow a recent line of works and assume that the underlying distribution satisfies a certain concentration condition and a margin condition at the same time. Under such conditions, we show that attribute-efficiency can be achieved by simple variants to existing hinge loss minimization programs. Our key contribution includes: 1) an attribute-efficient PAC learning algorithm that works under constant malicious noise rate; 2) a new gradient analysis that carefully handles the sparsity constraint in hinge loss minimization.

Related papers

• Efficient PAC Learning of Halfspaces with Constant Malicious Noise Rate [6.209600119671225]
  We study the problem of computationally efficient PAC learning of halfspaces in the presence of malicious noise.<n>We show that it is possible to achieve constant noise tolerance by minimizing a reweighted hinge loss.
  arXiv  Detail & Related papers  (2024-10-02T02:38:33Z)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  We revisit the input perturbations framework for differential privacy where noise is added to the input $Ain mathcalS$. We first design novel efficient algorithms to privately release pair-wise cosine similarities. We derive a novel algorithm to compute $k$-way marginal queries over $n$ features.
  arXiv  Detail & Related papers  (2024-06-07T12:07:16Z)
• Efficient Active Learning Halfspaces with Tsybakov Noise: A Non-convex Optimization Approach [28.518140532315776]
  We study the problem of computationally label efficient active learning. In this paper, we prove any approximate. first-order stationary light point of a structured un-labeled data set.
  arXiv  Detail & Related papers  (2023-10-23T23:55:28Z)
• Attribute-Efficient PAC Learning of Low-Degree Polynomial Threshold Functions with Nasty Noise [10.550885570889527]
  We study PAC learning of $K$sparse degree-$d$ PTFs on $mathbbRn$. Our main contribution is a new algorithm that runs in time $(nd/epsilon)O(d)$. PAC learns the class up to error rate $epsilon$ with $O(fracK4depsilon2d cdot log5d n)$ even when an $eta leq O(epsilond)
  arXiv  Detail & Related papers  (2023-06-01T13:49:22Z)
• Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
  adversary-resilient distributed optimization, in which. machines can independently compute gradients, and cooperate. Our algorithm is based on a new concentration technique, and its sample complexity. It is very practical: it improves upon the performance of all prior methods when no. setting machines are present.
  arXiv  Detail & Related papers  (2020-12-28T17:19:32Z)
• A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
  We study the problem of PAC learning homogeneous halfspaces in the presence of Tsybakov noise. Our algorithm learns the true halfspace within any accuracy $epsilon$.
  arXiv  Detail & Related papers  (2020-10-04T22:19:06Z)
• The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise [67.27523616312428]
  We study the computational complexity of adversarially robust proper learning of halfspaces in the distribution-independent PAC model. We give a computationally efficient learning algorithm and a nearly matching computational hardness result for this problem.
  arXiv  Detail & Related papers  (2020-07-30T04:18:51Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  We study the learnability of halfspaces in the presence of Tsybakov noise. We give an algorithm that achieves misclassification error $epsilon$ with respect to the true halfspace.
  arXiv  Detail & Related papers  (2020-06-11T14:25:02Z)
• Attribute-Efficient Learning of Halfspaces with Malicious Noise: Near-Optimal Label Complexity and Noise Tolerance [21.76197397540397]
  This paper is concerned with computationally efficient learning of homogeneous sparse halfspaces in $mathbbRd$ under noise. We show that the sample complexity is $tildeObig(frac 1 epsilon s2 log5 d big)$ which also enjoys the attribute efficiency.
  arXiv  Detail & Related papers  (2020-06-06T04:57:39Z)
• Efficiently Learning Adversarially Robust Halfspaces with Noise [69.01459748050453]
  We study the problem of learning adversarially robust halfspaces in the distribution-independent setting. In the realizable setting, we provide necessary and sufficient conditions on the adversarial perturbation sets under which halfspaces are efficiently robustly learnable.
  arXiv  Detail & Related papers  (2020-05-15T17:13:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.