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 ...
- 126
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.3k
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.3k
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.3k
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,451
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.3k
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.3k
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.3k
3
votes
Accepted
Confusion about lower bounds and upper bounds in learning theory
I invariably run into this issue when I teach learning theory. Indeed, the common notation causes a lot of confusion and is logically flawed.
To elaborate on Usul's comment. Upper bounds are of the ...
- 10.3k
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.3k
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.3k
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.3k
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,451
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.3k
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
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.3k
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.3k
2
votes
Accepted
Learning with zero inductive bias
To be more precise, if you want a distribution-free generalization bound, then you must have some inductive bias (these are the no-free-lunch theorems referenced by D.W.). For binary classification, ...
- 10.3k
1
vote
Learning with zero inductive bias
You cannot. See the No free lunch theorem (e.g., here and here and here and many other resources).
- 11.7k
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)=...
- 11.7k
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.3k
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.3k
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 ...
- 111
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.3k
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.3k
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