Efficient Algorithms for Learning Monophonic Halfspaces in Graphs

• URL: http://arxiv.org/abs/2405.00853v2
• Date: Mon, 17 Jun 2024 23:04:58 GMT
• Title: Efficient Algorithms for Learning Monophonic Halfspaces in Graphs
• Authors: Marco Bressan, Emmanuel Esposito, Maximilian Thiessen,
• Abstract summary: We prove several novel results for learning monophonic halfspaces in the supervised, online, and active settings. Our main result is that a monophonic halfspace can be learned with near-optimal complexity in time in $n = |V(G)|$. We also show that the concept class can be enumerated with delay $operatornamepoly(n)$, and that empirical risk can be performed in time $2omega(G)operatornamepoly(n)$.
• Score: 7.619404259039284
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of learning a binary classifier on the vertices of a graph. In particular, we consider classifiers given by monophonic halfspaces, partitions of the vertices that are convex in a certain abstract sense. Monophonic halfspaces, and related notions such as geodesic halfspaces,have recently attracted interest, and several connections have been drawn between their properties(e.g., their VC dimension) and the structure of the underlying graph $G$. We prove several novel results for learning monophonic halfspaces in the supervised, online, and active settings. Our main result is that a monophonic halfspace can be learned with near-optimal passive sample complexity in time polynomial in $n = |V(G)|$. This requires us to devise a polynomial-time algorithm for consistent hypothesis checking, based on several structural insights on monophonic halfspaces and on a reduction to $2$-satisfiability. We prove similar results for the online and active settings. We also show that the concept class can be enumerated with delay $\operatorname{poly}(n)$, and that empirical risk minimization can be performed in time $2^{\omega(G)}\operatorname{poly}(n)$ where $\omega(G)$ is the clique number of $G$. These results answer open questions from the literature (Gonz\'alez et al., 2020), and show a contrast with geodesic halfspaces, for which some of the said problems are NP-hard (Seiffarth et al., 2023).

Related papers

• Self-Directed Learning of Convex Labelings on Graphs [11.286983359775512]
  We study the problem of learning the clusters of a given graph in the self-directed learning setup. No results previously existed specifically for self-directed node classification on graphs.
  arXiv  Detail & Related papers  (2024-09-02T19:13:26Z)
• 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)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations. The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
  arXiv  Detail & Related papers  (2022-06-17T17:55:43Z)
• 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)
• On the Power of Localized Perceptron for Label-Optimal Learning of Halfspaces with Adversarial Noise [4.8728183994912415]
  We study em online active learning of homogeneous halfspaces in $mathbbRd$ with adversarial noise. Our main contribution is a Perceptron-like active learning algorithm that runs in time. Our algorithm learns the underlying halfspace with near-optimal label complexity.
  arXiv  Detail & Related papers  (2020-12-19T22:04:10Z)
• Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
  We study the complexity of PAC learning halfspaces in the presence of Massart (bounded) noise. We show that there an exponential gap between the information-theoretically optimal error and the best error that can be achieved by a SQ algorithm.
  arXiv  Detail & Related papers  (2020-12-17T16:43:11Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  We show that there exists an $epsilon$-cover for $S$ of cardinality $M = (k/epsilon)O_d(k1/d)$. Building on our structural result, we obtain significantly improved learning algorithms for several fundamental high-dimensional probabilistic models hidden variables.
  arXiv  Detail & Related papers  (2020-12-14T18:14:08Z)
• 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)
• Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvability [39.01599245403753]
  In particular, we study the problem of learning halfspaces under Massart noise with rate $eta$. We show any SQ algorithm requires super-polynomially many queries to achieve $mathsfOPT + epsilon$. We also study our algorithm for learning halfspaces under Massart noise empirically and find that it exhibits some appealing fairness properties.
  arXiv  Detail & Related papers  (2020-06-08T17:59:11Z)

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.