10

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 data. Thus, if a region of space is so sparse as to be poorly represented in the training sample, its probability of appearing during the test phase is low. You'...


10

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 $O((d/\varepsilon)\log(1/\varepsilon))$ sample complexity (see Vapnik and Chervonenkis, 1974; Blumer, Ehrenfeucht, Haussler, and Warmuth, 1989). As for (2), ...


10

PAC comes in two flavors -- "information theoretic PAC" and "efficient PAC." The latter asks for computational efficiency whereas the former cares only about sample size. One usually understands which is referred to from context. Indeed, it is not known whether (efficient) PAC learning is NP-hard in general, but results on the cryptographic hardness of ...


9

We know something close to what you want. If you look at Ke Yang's "Honest Statistical Queries" -- there is no noise at all, but only "sampling error". In this model, you pass in a parameter $t$, and the Oracle takes $t$ samples, honestly evaluates the passed-in function (onto {0,1}), and returns the average value of the function on the samples. In ...


8

What you describe is a non-stochastic version of the "functional multi-arm bandit problem": you know you have an unknown function from some class C (does not have to be randomly selected), and you have query access to this function. The goal is to find the element which maximizes the function. As you say, depending on the class C, this may or may not require ...


6

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. With probability $~1/\sqrt{n}$ we get that majority of leave-one-out is exactly the opposite of the excluded point so LOO will give error of 1. Note that the ...


6

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}{\epsilon}\log\frac1\epsilon)$ examples. For a simple proof of the $\epsilon$ dependence, consider the concept class of intervals $[a,b]\subseteq[0,1]$ under the ...


6

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,X_n) = E_\sigma \sup_{f\in F}\frac1n\sum_{i=1}^n \sigma_i f(X_i).$$ The latter is defined for a function class $F$ and distribution $D$, by $$ R_n(F;D) = E_{(X_1,\...


5

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 important to note that it may not lead to a computationally efficient learning algorithm. Which is normal, since unless $\mathsf{NP}=\mathsf{RP}$ is it known ...


4

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'$. Obviously, you will only able to recover $f$ up to an additive constant from the derivative. Update: As for error estimates, here's a simple one. Suppose you've ...


4

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] oracle". So the question is not really whether MCMC "falls into the SQ framework" (the framework does not place any restrictions on computation) but whether the ...


4

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, for any $\epsilon>0$, the empirical Rademacher complexity of $F$ is bounded by $$ R_n(F;X) \le \epsilon + \sqrt{\frac{2\log N_F(\epsilon)}{n}},$$ where $...


3

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 non-adaptive testers) [KhotMinzerSafra15]. learning $\mathcal{M}$ under the uniform distribution, even allowing membership queries, requires $2^{\Omega(\sqrt{n}/\...


3

(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, you will not be able to give any meaningful risk decay rates (which is what Rademacher complexities enable you to do). Alternatively, you could assume something ...


3

Well, we wrote a paper on it, so now it's definitely known: https://arxiv.org/abs/2010.09886


1

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 class $\mathcal{H}$ of all polynomial classifiers over $\mathbb{R}$ is not PAC learnable ($\mathrm{VCdim}(\mathcal{H}) = \infty$). We might rewrite $\mathcal{H}$ as ...


1

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 need at least $$\Omega(d_F(\epsilon)/\epsilon^2) \qquad (*)$$ examples, where $d_F(\epsilon)$ is the fat-shattering dimension of the class $F$ at scale $\...


1

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 learning 3-term DNFs. This class of functions is hard to learn properly. But if "testing" involves evaluating a fixed given 3-term DNF on some randomly drawn points ...


1

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 Lipschitz), then you do not need to assume bounded gradients and there are quite a few assumptions on the noise you can adopt, and they are reviewed (with ...


1

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$ samples (after transforming to Z). It can be shown that $Z_{(t)}\sim \text{Beta}(t,m+1-t)$. Using this, $Z_{(m\cdot k/n)}=F(X_{(m\cdot k/n)})$ is a consistent ...


1

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 approximately normal distribution, with mean $0$ and covariance matrix given by the inverse Fisher matrix, see Section 9 here: http://www.stat.cmu.edu/~larry/=stat705/...


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