4
$\begingroup$

Let us see Theorem 6.8 in this book, https://www.cs.huji.ac.il/w~shais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf

It gives us a lowerbound (and also an upperbound) on the number of samples needed to learn a 0/1 valued hypothesis class of finite VC

Such a Theorem 6.8 for real valued functions is not known to me!

  • I am wondering why something like fat-shattering dimension not give such bounds (particularly the lowerbound) for real valued classes. So far I cant spot any such result in literature. Is there a known bottleneck to this?
Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ This stuff has definitely been studied and is in the literature. Maybe ask on cstheory stack exchange if noone here gives a reference. $\endgroup$
    – mathworker21
    Commented Mar 31, 2022 at 14:43
  • 2
    $\begingroup$ I feel if this is studied then this is in some quite obscure literature! $\endgroup$
    – Student
    Commented Mar 31, 2022 at 15:28

2 Answers 2

Reset to default
2
$\begingroup$

Theorem 19.5 in Anthony, Martin; Bartlett, Peter L., Neural network learning: Theoretical foundations (1999). gives the lower bound. The agnostic sample complexity of learning a real-valued function class $F \subseteq [0,1]^{X}$ up to error $\epsilon$ is roughly $\Omega(\text{fat}_{4 \epsilon}(F))$. Anthony and Bartlett's lower bound is for quadratic loss, and their proof is based on a reduction to binary classification.

Sridharan provides a lower bound on the minimax value of regression with respect to absolute loss on these notes.

Improve this answer
$\endgroup$
1
$\begingroup$

There certainly are such results.

  • Yes, fat-shattering dimension and pseudo-dimension are used to characterize sample complexity. For example, here are some lecture notes (pdf) I found with a quick internet search.

  • For another thing, Rademacher complexity is defined for real-valued functions and characterizes sample complexity of learning. See Chapter 26 of that book, or other books like Foundations of Machine Learning.

  • In general I think there are several things you could mean by "for real-valued functions". For example, you could be thinking of regression where a hypothesis is of the form $h: X \to \mathbb{R}$ and a label is of the form $y \in \mathbb{R}$, and the loss is $\ell(h(x),y) := (h(x) - y)^2$. This would generally need a different set of tools, at least because the loss is unbounded.

Improve this answer
$\endgroup$
9
  • 1
    $\begingroup$ Hi. I know these references. I don't think these answer my full question. (a) the proofs in those slides do not enable me - as far as I can see - to get a sample complexity lowerbound for the case of real valued functions - they can only give upperbounds on the generalization error in terms of the covering number in general and in terms of fat-shattering-dimension only for the restrictive $[0,1] \rightarrow [0,1]$ class. (b) Rademacher complexity is a distribution dependent bound and hence that is by definition something much weaker a starting point if one is aiming to match this Theorem 6.8 $\endgroup$
    – Student
    Commented Apr 1, 2022 at 11:55
  • 1
    $\begingroup$ @Student I think it would help if you state precisely what statement you want to prove. $\endgroup$
    – usul
    Commented Apr 1, 2022 at 14:39
  • 1
    $\begingroup$ @usul I'm curious. Is there a (text)book reference you know of for this stuff. $\endgroup$
    – mathworker21
    Commented Apr 1, 2022 at 16:09
  • 1
    $\begingroup$ @mathworker21 The textbook that I referred to is pretty much all that there is. $\endgroup$
    – Student
    Commented Apr 1, 2022 at 16:50
  • 1
    $\begingroup$ @usul You can see what Theorem 6.8 in that referred book is achieving : it is giving a lowerbound on the number of samples for achieving agnostic PAC learning for 0/1 valued functions. One of the key things that I am looking for is if an analogue of this is known for real valued functions. $\endgroup$
    – Student
    Commented Apr 1, 2022 at 16:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .