11 votes
Accepted

Proper PAC learning VC dimension bounds

My thanks to Aryeh for bringing this question to my attention. As others have mentioned, the answer to (1) is Yes, and the simple method of Empirical Risk Minimization in $\mathcal{C}$ achieves the ...
user avatar
10 votes
Accepted

Difficulty of "learning" rare instances

In the classic PAC learning (i.e., classification) model, rare instances are not a problem. This is because the learner's test points are assumed to come from the same distribution as the training ...
user avatar
  • 10k
6 votes
Accepted

Latest word on cross validation?

It is not hard to see that without additional stability assumptions one won't be able to get high probability bounds. For example consider predicting unbiased coin using majority label in the sample. ...
user avatar
  • 881
6 votes

Proper PAC learning VC dimension bounds

Your questions (1) and (2) are related. First, let's talk about proper PAC learning. It is known that there are proper PAC learners that achieve zero sample error, and yet require $\Omega(\frac{d}{\...
user avatar
  • 10k
6 votes
Accepted

Rademacher complexity and lowerbounds in learning theory

First, let's distinguish between empirical end expected Rademacher complexities. The former is defined for a function class $F$ and sequence of points $X_1,\ldots, X_n$, by $$ \hat R_n(F;X_1,\ldots,...
user avatar
  • 10k
5 votes

Proper PAC learning VC dimension bounds

To add to the currently accepted answer: Yes. The $$O\left(\frac{d}{\varepsilon}\log\frac{1}{\varepsilon}\right)$$ sample complexity upper bound holds for proper PAC learning as well (although it is ...
user avatar
  • 4,341
4 votes
Accepted

Some issues with proof of Fundamental Theorem of Statistical learning

There has been a recent line of work on computable learnability: http://proceedings.mlr.press/v117/agarwal20b/agarwal20b.pdf http://www.learningtheory.org/colt2021/virtual/static/images/agarwal21b.pdf ...
user avatar
  • 10k
4 votes
Accepted

Learning from derivative data

If your function is $f:\mathbb{R}\to\mathbb{R}$, you can "learn" $f'$ as a standard regression problem (linear, polynomial, etc.) and then recover $f$ up to an additive constant by integrating $f'$. ...
user avatar
  • 10k
4 votes
Accepted

Does MCMC belong to the statistical query model?

Let me first clarify what the paper states: "Most algorithmic approaches used in practice and in theory on a wide variety of problems can be implemented using only access to such an [meaning SQ] ...
user avatar
  • 881
4 votes
Accepted

PAC-learning bound with epsilon-cover of hypothesis class

This follows from Massart's finite class lemma. Let $F$ is a binary function class restricted to some set $\{X_1,\ldots,X_n\}$, and let $P_n$ be the empirical (i.e., uniform) measure on this set. Then,...
user avatar
  • 10k
3 votes

VC dimension of the class of all polygons with k vertices

Assuming that the $k$-gon is simple (i.e., does not intersect itself and has no holes) and $k>3$, the two-ears theorem, https://en.wikipedia.org/wiki/Two_ears_theorem implies that it can be ...
user avatar
  • 10k
3 votes

Non-(PAC)-Learnable Classes

The standard no-free-lunch argument can be stated and understood without any knowledge or deep understanding of VC theory. (The upper bound, with its reliance on Sauer’s lemma, is intimately ...
user avatar
  • 10k
3 votes
Accepted

Rademacher complexity beyond the agnostic setting

(a) If you don't assume that you're "competing" against $f\in F$, you must make some assumption about the larger function class to which $f$ belongs -- otherwise, by standard no-free-lunch theorems, ...
user avatar
  • 10k
3 votes

Are there hypothesis classes that are hard to learn but easy to test?

Take the class $\mathcal{M}$ of monotone boolean functions under the uniform distribution on $\{0,1\}^n$: it is known that $O(\sqrt{n}/\varepsilon^2)$ queries are sufficient to test it (even with ...
user avatar
  • 4,341
3 votes
Accepted

Is this a known learning problem?

Well, we wrote a paper on it, so now it's definitely known: https://arxiv.org/abs/2010.09886
user avatar
  • 10k
2 votes

An (unusual?) risk bound

I believe a common name for what you describe as $\mathcal{N}(\mathcal{F},2n)$ is the "growth function". For a concept class $\mathcal{F} = \{ h : X \to \{0,1\} \}$ and $S = (x_1,\dots,x_n) \...
user avatar
  • 121
2 votes
Accepted

Sample complexity for learning Boltzmann Distribution parameters

Under appropriate smoothness conditions (satisfied by the Boltzmann distribution), the maximum likelihood is asymptotically normal. Meaning: the vector $\sqrt n(\theta-\hat\theta)$ will have ...
user avatar
  • 10k
1 vote

Some issues with proof of Fundamental Theorem of Statistical learning

I know it's generally considered bad form to add another answer on top of an accepted one, but this one is by special request and it's a topic that deserves its own discussion. The topic is: Effective ...
user avatar
  • 10k
1 vote

Why non-uniform learnability does not imply PAC learnability?

The following answer is based on chapter 6/7 of the book »Understanding Machine Learning: From Theory to Algorithms«, by Shalev-Shwartz and Ben-David (especially Example 7.1). It states that the ...
user avatar
1 vote

Lower bound of real valued bounded function

You have to specify a loss -- say, $\ell_1$ for simplicity, so the risk of a hypothesis $h$ is $E|h(X)-Y|$. Then at the very least, by reduction to the VC case, to achieve accuracy $\epsilon$ you will ...
user avatar
  • 10k
1 vote

Are there hypothesis classes that are hard to learn but easy to test?

Please define testing precisely (under what distribution? known/unknown?). In the meantime, here is an example of what you may be looking for. Consider the example in the Kearns-Vazirani book, of ...
user avatar
  • 10k
1 vote

About assumptions needed to get convergence of stochastic gradient methods on non-convex objectives

There is a lot of recent work on these questions spurred by interest in deep learning and other non-convex optimization tasks. If the objective is differentiable and smooth (i.e. if the gradient is ...
user avatar
  • 41
1 vote

Sample Complexity for Order Statistics

One way to approach this problem is via the CDF transformation. Consider $Z=F(X)$. We know $Z$ is uniformly distributed in $[0,1]$. Let $Z_{(1)},...,Z_{(m)}$ be the order statistics of these $m$ ...
user avatar

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