Non-Clashing Teaching Maps for Balls in Graphs
- URL: http://arxiv.org/abs/2309.02876v1
- Date: Wed, 6 Sep 2023 10:02:58 GMT
- Title: Non-Clashing Teaching Maps for Balls in Graphs
- Authors: J\'er\'emie Chalopin, Victor Chepoi, Fionn Mc Inerney, S\'ebastien
Ratel
- Abstract summary: A teaching map is non-clashing if no pair of concepts are consistent with the union of their teaching sets.
We show that the associated decision problem sc B-NCTD$+$ for NCTD$+$ is NP-complete in split, co-bipartite, and bipartite graphs.
- Score: 0.058520770038704165
- 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 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 $\cal{C}$ assigns a
(teaching) set $T(C)$ of examples to each concept $C \in \cal{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 $T(C)$, $C \in \cal{C}$. The non-clashing teaching dimension
NCTD$(\cal{C})$ of $\cal{C}$ is the minimum size of an NCTM for $\cal{C}$.
NCTM$^+$ and NCTD$^+(\cal{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 {\sc B-NCTD$^+$} for NCTD$^+$ is NP-complete in split, co-bipartite,
and bipartite graphs. Surprisingly, we even prove that, unless the ETH fails,
{\sc B-NCTD$^+$} does not admit an algorithm running in time
$2^{2^{o(vc)}}\cdot n^{O(1)}$, nor a kernelization algorithm outputting a
kernel with $2^{o(vc)}$ vertices, where vc is the vertex cover number of $G$.
These are extremely rare results: it is only the second (fourth, resp.) problem
in NP to admit a double-exponential lower bound parameterized by vc (treewidth,
resp.), and only one of very few problems to admit an ETH-based conditional
lower bound on the number of vertices in a kernel. We complement these lower
bounds with matching upper bounds. 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. For Gromov-hyperbolic graphs, we design an
approximate NCTM$^+$ for $\mathcal{B}(G)$ 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) - Coresets for Decision Trees of Signals [19.537354146654845]
We provide the first algorithm that outputs such a $(k,varepsilon)$-coreset for emphevery such matrix $D$.
This is by forging a link between decision trees from machine learning -- to partition trees in computational geometry.
arXiv Detail & Related papers (2021-10-07T05:49:55Z) - 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) - 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) - Nearly Minimax Optimal Reinforcement Learning for Discounted MDPs [99.59319332864129]
We show that UCBVI-$gamma$ achieves an $tildeObig(sqrtSAT/ (1-gamma)1.5big)$ regret, where $S$ is the number of states, $A$ is the number of actions, $gamma$ is the discount factor and $T$ is the number of steps.
In addition, we construct a class of hard MDPs and show that for any algorithm, the expected regret is at least $tildeOmegabig(sqrtSAT/
arXiv Detail & Related papers (2020-10-01T17:57:47Z)
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.