2024-06-30-chalopin24a.md

title	section	abstract	layout	series	publisher	issn	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_author	author	date	address	container-title	volume	genre	issued	pdf	extras
Non-Clashing Teaching Maps for Balls in Graphs	Original Papers	Recently, Kirkpatrick et al. [ALT 2019] and Fallat et al. [JMLR 2023] introduced non-clashing teaching and showed it to be the most efficient machine teaching model satisfying the benchmark for collusion-avoidance set by Goldman and Mathias. 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 $\text{NCTD}(\mathcal{C})$ of $\mathcal{C}$ is the minimum size of an NCTM for $\mathcal{C}$. $\text{NCTM}^+$ and $\text{NCTD}^+(\mathcal{C})$ are defined analogously, except the teacher may only use positive examples. We study NCTMs and $\text{NCTM}^+\text{s}$ for the concept class $\mathcal{B}(G)$ consisting of all balls of a graph $G$. We show that the associated decision problem $\text{B-NCTD}^+$ for $\text{NCTD}^+$ is NP-complete in split, co-bipartite, and bipartite graphs. Surprisingly, we even prove that, unless the ETH fails, $\text{B-NCTD}^+$ does not admit an algorithm running in time $2^{2^{o(\mathtt{vc})}}\cdot n^{\mathcal{O}(1)}$, nor a kernelization algorithm outputting a kernel with $2^{o(\mathtt{vc})}$ vertices, where $\mathtt{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 $\mathtt{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 $\text{NCTM}^+\text{s}$ or NCTMs for $\mathcal{B}(G)$ of size proportional to its VC-dimension. For Gromov-hyperbolic graphs, we design an approximate $\text{NCTM}^+$ for $\mathcal{B}(G)$ of size $2$, in which only pairs of balls with Hausdorff distance larger than some constant must satisfy the non-clashing condition.	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	chalopin24a	0	Non-Clashing Teaching Maps for Balls in Graphs	840	875	840-875	840	false	Chalopin, J\'{e}r\'{e}mie and Chepoi, Victor and {Mc~Inerney}, Fionn and Ratel, S\'{e}bastien	given family Jérémie Chalopin given family Victor Chepoi given family Fionn Mc Inerney given family Sébastien Ratel	2024-06-30		Proceedings of Thirty Seventh Conference on Learning Theory	247	inproceedings	date-parts 2024 6 30	https://proceedings.mlr.press/v247/chalopin24a/chalopin24a.pdf