7

In 1996 Papadimitriou and Yannakakis noted that there exists an $n^{O(\log n)}$ brute-force algorithm (where $n$ is the size of the input) for computing VC-dimension of a 0-1 matrix by checking all the subsets of size up to the trivial bound, the logarithm of the number of hypotheses. Manurangsi and Rubinstein later showed this bound basically cannot be ...


4

I'm not sure if claims about optimal constants are meaningful when trying to optimize all 3; often it is the case that one can be made better at the expense of another. One way to simplify the issue is to look at the expectation, so you only have to deal with one constant. This is the approach taken by Devroye-Lugosi (the book suggested by Clément). The ...


3

Pseudo dimension and fat shattering dimension are (some of the) analogue of VC dimension in the regression setting. See https://ttic.uchicago.edu/~tewari/lectures/lecture15.pdf (section 3)


1

Daniely et al had some works on the subject back in 2012--2015. In particular, it is referred to (there) as "multiclass learning". Here are two works on this: Multiclass learnability and the ERM principle Multiclass Learning Approaches: A Theoretical Comparison with Implications Unfortunately, my knowledge of this is limited to knowing the authors ...


Only top voted, non community-wiki answers of a minimum length are eligible