A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise

• URL: http://arxiv.org/abs/2501.09691v1
• Date: Thu, 16 Jan 2025 17:44:18 GMT
• Title: A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise
• Authors: Ilias Diakonikolas, Nikos Zarifis,
• Abstract summary: We study the problem of PAC learning $gamma$-margin halfspaces in the presence of Massart noise. Our algorithm is simple and practical, relying on online SGD on a carefully selected sequence of convex losses.
• Score: 36.29182619215646
• License:
• Abstract: We study the problem of PAC learning $\gamma$-margin halfspaces in the presence of Massart noise. Without computational considerations, the sample complexity of this learning problem is known to be $\widetilde{\Theta}(1/(\gamma^2 \epsilon))$. Prior computationally efficient algorithms for the problem incur sample complexity $\tilde{O}(1/(\gamma^4 \epsilon^3))$ and achieve 0-1 error of $\eta+\epsilon$, where $\eta<1/2$ is the upper bound on the noise rate. Recent work gave evidence of an information-computation tradeoff, suggesting that a quadratic dependence on $1/\epsilon$ is required for computationally efficient algorithms. Our main result is a computationally efficient learner with sample complexity $\widetilde{\Theta}(1/(\gamma^2 \epsilon^2))$, nearly matching this lower bound. In addition, our algorithm is simple and practical, relying on online SGD on a carefully selected sequence of convex losses.

Related papers

• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  We show that any efficient SQ algorithm for the problem requires sample complexity at least $Omega(d1/2/(maxp, epsilon)2)$. Our lower bound suggests that this quadratic dependence on $1/epsilon$ is inherent for efficient algorithms.
  arXiv  Detail & Related papers  (2023-07-13T18:59:28Z)
• Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise [50.64137465792738]
  We study the problem of PAC $gamma$-margin halfspaces with Random Classification Noise. We establish an information-computation tradeoff suggesting an inherent gap between the sample complexity of the problem and the sample complexity of computationally efficient algorithms.
  arXiv  Detail & Related papers  (2023-06-28T16:33:39Z)
• Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
  We study the complexity of PAC learning halfspaces in the presence of Massart noise. We show that no-time Massart halfspace learners can achieve error better than $Omega(eta)$, even if the optimal 0-1 error is small.
  arXiv  Detail & Related papers  (2022-07-28T17:50:53Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  We study the problem of PAC learning halfspaces on $mathbbRd$ with Massart noise under Gaussian marginals. Our results qualitatively characterize the complexity of learning halfspaces in the Massart model.
  arXiv  Detail & Related papers  (2021-08-19T16:16:48Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  Given an MDP with $S$ states, $A$ actions, the discount factor $gamma in (0,1)$, and an approximation threshold $epsilon > 0$, we provide a model-free algorithm to learn an $epsilon$-optimal policy. For small enough $epsilon$, we show an improved algorithm with sample complexity.
  arXiv  Detail & Related papers  (2020-06-06T13:34:41Z)
• Efficient active learning of sparse halfspaces with arbitrary bounded noise [34.406103025985445]
  We study active learning of homogeneous $s$-sparse halfspaces in $mathbbRd$ under the setting where the unlabeled data distribution is isotropic log-concave. Under high levels of label noise, the label complexity bounds achieved by computationally efficient algorithms are much worse. This is the first efficient algorithm with label complexity in $frac11-2eta$ in this setting, which is label-efficient even for $eta$ arbitrarily close to $frac12$.
  arXiv  Detail & Related papers  (2020-02-12T08:28:24Z)

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.