Talk:Rademacher complexity

Untitled

I have noticed that somebody has removed expectation from the definition of empirical Rademacher complexity. There should be, of course, expectation over the Rademacher variables. My guess is that some probabilist did not like the notation with two expectations and he was right. To be correct, we should write there conditional expectation (conditioning on the sample). -- David Pal —Preceding unsigned comment added by David Pal (talk • contribs) 16:01, 5 July 2010 (UTC)

Untitled

"One can show, for example, that there exists a constant C, such that any class of \{0,1\}-indicator functions with Vapnik-Chervonenkis dimension d has Rademacher complexity upper-bounded by C\sqrt{\frac{d}{m}}".
What is the best known value for C?
Can someone please add a reference to a paper showing this bound to hold? -yonil

Rademacher under expectation of points

Someone should adapt the definition to also account for the expectation of the points themselves, but I lack the experience to do it myself. Plus, this could benefit from a second pair of eyes. I just stumbled upon this and thought it might be of benefit to mention.

Essentially, the definitions given are for given, fixed set of points, and are a good didactic tool to lead to the full Rademacher, which should be defined as taking the expectation of these definitions over all points of given size, under the probability of a set of points over the space they live. Something like:

Failed to parse (unknown function "\coloneqq"): {\displaystyle R(\mathcal F;n) \coloneqq \Exp_{\substack{\sigma\sim \operatorname{Rad}\\\{z_1,\ldots,z_m\}\sim \mathbb P}} \sup_{f\in\mathcal F}\sum_{i=1}^m \sigma_if(z_i) } Kalofoli (talk) 00:10, 19 November 2022 (UTC)