Non-Clashing Teaching Maps for Balls in Graphs

• URL: http://arxiv.org/abs/2309.02876v2
• Date: Mon, 29 Jul 2024 14:10:52 GMT
• Title: Non-Clashing Teaching Maps for Balls in Graphs
• Authors: Jérémie Chalopin, Victor Chepoi, Fionn Mc Inerney, Sébastien Ratel,
• Abstract summary: We show that the associated decision problem B-NCTD$+$ for NCTD$+$ is NP-complete in split, co-bipartite, and bipartite graphs. We also prove that, unless the ETH fails, B-NCTD$+$ does not admit an algorithm running in time $22o(textvc)cdot nO(1)$, nor a kernelization algorithm outputting a kernel with $2o(textvc)cdot nO(1)$.
• Score: 0.05356944479760104
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recently, Kirkpatrick et al. [ALT 2019] and Fallat et al. [JMLR 2023] introduced non-clashing teaching and showed it is the most efficient machine teaching model satisfying the Goldman-Mathias collusion-avoidance criterion. A teaching map $T$ for a concept class $\mathcal{C}$ assigns a (teaching) set $T(C)$ of examples to each concept $C \in \mathcal{C}$. A teaching map is non-clashing if no pair of concepts are consistent with the union of their teaching sets. The size of a non-clashing teaching map (NCTM) $T$ is the maximum size of a teaching set $T(C)$, $C \in \mathcal{C}$. The non-clashing teaching dimension NCTD$(\mathcal{C})$ of $\mathcal{C}$ is the minimum size of an NCTM for $\mathcal{C}$. NCTM$^+$ and NCTD$^+(\mathcal{C})$ are defined analogously, except the teacher may only use positive examples. We study NCTMs and NCTM$^+$s for the concept class $\mathcal{B}(G)$ consisting of all balls of a graph $G$. We show that the associated decision problem B-NCTD$^+$ for NCTD$^+$ is NP-complete in split, co-bipartite, and bipartite graphs. Surprisingly, we even prove that, unless the ETH fails, B-NCTD$^+$ does not admit an algorithm running in time $2^{2^{o(\text{vc})}}\cdot n^{O(1)}$, nor a kernelization algorithm outputting a kernel with $2^{o(\text{vc})}$ vertices, where vc is the vertex cover number of $G$. We complement these lower bounds with matching upper bounds. These are extremely rare results: it is only the second problem in NP to admit such a tight double-exponential lower bound parameterized by vc, and only one of very few problems to admit such an ETH-based conditional lower bound on the number of vertices in a kernel. For trees, interval graphs, cycles, and trees of cycles, we derive NCTM$^+$s or NCTMs for $\mathcal{B}(G)$ of size proportional to its VC-dimension, and for Gromov-hyperbolic graphs, we design an approximate NCTM$^+$ of size 2.

Related papers

• Efficient Continual Finite-Sum Minimization [52.5238287567572]
  We propose a key twist into the finite-sum minimization, dubbed as continual finite-sum minimization. Our approach significantly improves upon the $mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$ requires. We also prove that there is no natural first-order method with $mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$, establishing that the first-order complexity of our method is nearly tight.
  arXiv  Detail & Related papers  (2024-06-07T08:26:31Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  Multi-head attention layer is one of the key components of the transformer architecture that sets it apart from traditional feed-forward models. In this work, we initiate the study of provably learning a multi-head attention layer from random examples. We prove computational lower bounds showing that in the worst case, exponential dependence on $m$ is unavoidable.
  arXiv  Detail & Related papers  (2024-02-06T15:39:09Z)
• On character table of Clifford groups [0.0]
  We construct the character table of the Clifford group $mathcalC_n$ for $n=1,2,3$. As an application, we can efficiently decompose the (higher power of) tensor product of the matrix representation. As a byproduct, we give a presentation of the finite symplectic group $Sp(2n,2)$ in terms of generators and relations.
  arXiv  Detail & Related papers  (2023-09-26T11:29:35Z)
• A Unified Characterization of Private Learnability via Graph Theory [18.364498500697596]
  We provide a unified framework for characterizing pure and approximate differentially private (DP) learnability. We identify graph-theoretic dimensions that characterize DP learnability: the clique dimension and fractional clique dimension. We also reveal properties of the contradiction graph which may be of independent interest.
  arXiv  Detail & Related papers  (2023-04-08T12:25:08Z)
• 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)
• Random Graph Matching in Geometric Models: the Case of Complete Graphs [21.689343447798677]
  This paper studies the problem of matching two complete graphs with edge weights correlated through latent geometries. We derive an approximate maximum likelihood estimator, which provably achieves, with high probability, perfect recovery of $pi*$. As a side discovery, we show that the celebrated spectral algorithm of [Ume88] emerges as a further approximation to the maximum likelihood in the geometric model.
  arXiv  Detail & Related papers  (2022-02-22T04:14:45Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  We study the problem of efficiently summarizing a short video into several paragraphs, leveraging recent progress in fast graph sampling. Experimental results show that our algorithm achieves comparable video summarization as state-of-the-art methods, at a substantially reduced complexity.
  arXiv  Detail & Related papers  (2021-10-21T18:43:00Z)
• Linear Bandits on Uniformly Convex Sets [88.3673525964507]
  Linear bandit algorithms yield $tildemathcalO(nsqrtT)$ pseudo-regret bounds on compact convex action sets. Two types of structural assumptions lead to better pseudo-regret bounds.
  arXiv  Detail & Related papers  (2021-03-10T07:33:03Z)
• 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)
• Algorithms and Hardness for Linear Algebra on Geometric Graphs [14.822517769254352]
  We show that the exponential dependence on the dimension dimension $d in the celebrated fast multipole method of Greengard and Rokhlin cannot be improved. This is the first formal limitation proven about fast multipole methods.
  arXiv  Detail & Related papers  (2020-11-04T18:35:02Z)
• Phase Transitions in Rate Distortion Theory and Deep Learning [5.145741425164946]
  We say that $mathcalS$ can be compressed at rate $s$ if we can achieve an error of $mathcalO(R-s)$ for encoding $mathcalS$. We show that for certain "nice" signal classes $mathcalS$, a phase transition occurs: We construct a probability measure $mathbbP$ on $mathcalS$.
  arXiv  Detail & Related papers  (2020-08-03T16:48:49Z)

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.