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 ...
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 ...
  • 10.1k
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. ...
  • 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}{\...
  • 10.1k
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,...
  • 10.1k
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 ...
  • 4,381
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 ...
  • 10.1k
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'$. ...
  • 10.1k
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] ...
  • 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,...
  • 10.1k
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 ...
  • 10.1k
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 ...
  • 10.1k
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, ...
  • 10.1k
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 ...
  • 4,381
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
  • 10.1k
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) \...
  • 121
2 votes

PAC learning over continuous functions

In PAC learning, you specify the function class a priori. Thus, there might not be a function in your class that fits the sample perfectly. You'll typically minimize some empirical risk, such as $L_1$ ...
  • 10.1k
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 ...
  • 10.1k
1 vote

Differing definitions of a weak learner

Suppose that the output of $h,c$ is either $+1$ or $-1$. Then $h(x)c(x)=1$ iff $h(x)=c(x)$. Moreover, if we let $p=\Pr[h(x)=c(x)]$, then $$\begin{align*} \mathbb{E}[h(x)c(x)] &= 1 \cdot \Pr[h(x)=...
  • 11k
1 vote
Accepted

Fat Shattering / VC dimension / Statistical Complexity of piecewise linear functions

I will address the "VC" part. Let $F_{d,k}$ be the collection of all $k$-piecewise linear functions from $\mathbb{R}^d$ to $\mathbb{R}$. Let $H_{d,k}=\mathrm{sign}(F_{d,k})$ be this class ...
  • 10.1k
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 ...
  • 10.1k
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 ...
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 ...
  • 10.1k
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 ...
  • 10.1k
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 ...
  • 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$ ...

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