Category: math.CO
-
Coarsening Causal DAG Models
Coarsening Causal DAG Models arXiv:2601.10531v1 Announce Type: new Abstract: Directed acyclic graphical (DAG) models are a powerful tool for representing causal relationships among jointly distributed random variables, especially concerning data from across different experimental settings. However, it is not always practical or desirable to estimate a causal model at the granularity of given features in…
-
Higher-arity PAC learning, VC dimension and packing lemma
Higher-arity PAC learning, VC dimension and packing lemma arXiv:2510.02420v1 Announce Type: new Abstract: The aim of this note is to overview some of our work in Chernikov, Towsner’20 (arXiv:2010.00726) developing higher arity VC theory (VC$_n$ dimension), including a generalization of Haussler packing lemma, and an associated tame (slice-wise) hypergraph regularity lemma; and to demonstrate that…
-
Lower Bounds for Greedy Teaching Set Constructions
Lower Bounds for Greedy Teaching Set Constructions arXiv:2505.03223v1 Announce Type: new Abstract: A fundamental open problem in learning theory is to characterize the best-case teaching dimension $operatorname{TS}_{min}$ of a concept class $mathcal{C}$ with finite VC dimension $d$. Resolving this problem will, in particular, settle the conjectured upper bound on Recursive Teaching Dimension posed by [Simon…
-
Positivity sets of hinge functions
Positivity sets of hinge functions arXiv:2503.13512v1 Announce Type: new Abstract: In this paper we investigate which subsets of the real plane are realisable as the set of points on which a one-layer ReLU neural network takes a positive value. In the case of cones we give a full characterisation of such sets. Furthermore, we give…