19
The question seems somewhat under-specified in the sense that it did not specify the desired error probability of the procedure. Assuming one means constant error probability, then the above is indeed the best I know. For a detailed discussion see Sec 2.5.2.4 in my book "The Foundations of Cryptography - Volume 1" available at http://www.wisdom.weizmann.ac....
12
Recent work by Alon, Moran, and Yehudayoff gives an $O(n/\log n)$ approximation algorithm. Let $d$ be the VC-dimension of a sign matrix $S$. The idea is that
there exists an efficiently computable matrix $M$ with sign pattern $S$ such that $\mathrm{rank}\ M = O(n^{1-1/d})$;
the sign rank of $S$ is at least $d$.
So the algorithm computes $M$ and outputs ...
11
I will formalize a variant of this question where "efficiency" is replaced by "computability".
Let $C_n$ be the concept class of all languages $L\subseteq\Sigma^*$
recognizable by Turing machines on $n$ states or fewer.
In general, for $x\in\Sigma^*$ and $f\in C_n$, the problem of evaluating
$f(x)$ is undecidable.
However, suppose we have access to a (...
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 ...
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
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'...
9
I assume you want an efficient algorithm, e.g., one whose running time is polynomial in $n$. (If you don't care about running time, then heuristically about $4n/\lg m$ samples should suffice to uniquely determine $a,b,m,p$, and you can use exhaustive search over all possible $2^{4n}$ parameter choices to find the correct one. Of course, the running time 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 ...
9
The main thing missing from your list is the beautiful 2006 paper of Klivans and Sherstov. They show there that PAC-learning even depth-2 threshold circuits is as hard as solving the approximate shortest vector problem.
9
Let me clarify the question a bit first:
Agnostic learning conjunctions is known to be NP-hard only if the learner needs to be proper (output a conjunctions as a hypothesis) and work for any input distribution. The reductions in FGKP06 are for the uniform distribution and to the best of my knowledge there is no similar result for general distributions.
But ...
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 ...
7
Juntas can be tested in an attribute efficient manner given a membership query oracle: http://www.cs.cmu.edu/~eblais/papers/TestingJuntas.pdf Testing is an easier problem than learning, and the attribute efficient result is relatively recent. This might be a good place to start poking around.
Incidentally, the hard part about learning juntas is just ...
7
The question is about recovering with membership queries for which it is well known that O( k log n) queries suffice (via BCH codes see Hoffmeister's paper or my COLT 2005 paper). In terms of lower bounds \Omega(k log n) trivially follows from counting the number of parities and using the fact that they are all completely uncorrelated (basic packing-based ...
7
Here is a better bound on the sample complexity. (Although the computational complexity is still $n^k$.)
Theorem. Assume there exists a subcube $S$ of size $2^{n-k}$ such that $|\mathbb{E}_{x \in S}[f(x)]| \geq 0.12$. With $O(2^k \cdot k \cdot \log n)$ samples we can, with high probability, identify a subcube $S'$ of size $2^{n-k}$ such that $|\mathbb{E}_{x ...
7
For the very limited situation in which $k=1$ and we're only interested in functions whose domain is $\{0,1\}^n$, the VC dimension is $\lfloor \log_2(n+1) + 1 \rfloor$.
The upper bound follows essentially from Sasho's argument: there are $2+2n$ 1-juntas on $n$ variables, and if there were more than $\log_2$ of that many inputs, we could find a function that ...
7
Second version, hopefully correct.
I claim that solving the feasibility problem $\exists? x: Ax \le b$ reduces in strongly polynomial time to finding a linear separator. Then it's easy to reduce linear programming to the feasibility problem.
Let us first reduce the strict feasibility problem $\exists? x: Ax < b$ to finding a linear separator. Towards ...
6
You are probably looking for this paper:
Víctor Dalmau and Peter Jeavons, Learnability of quantified formulas, TCS 306 485–511, 2003. doi:10.1016/S0304-3975(03)00342-6
In short, the learning complexity of a family of quantified formulas over a finite domain of values is determined by its clone of polymorphisms. This includes CSPs as a special case of ...
6
I guess you already had a look at Breiman's 2001 paper about RF. I can just point out a few other references:
Empirical comparisons of different RF simplifications that allow proving theorems: Narrowing the Gap: Random Forests In Theory and In Practice
This is the newest reference I can provide. In this paper you can also find some citations of Biau's ...
6
No, you cannot. See Thm 2.1 of http://link.springer.com/article/10.1007%2FBF02187833 (it says that a random family gives an example, with appropriately chosen parameters).
6
The discussion in the comments below indicades that I have misunderstood the question. My answer is premised on the Oracle taking no input and returning $(x, f(x))$ where $x \sim p$ or $x \sim q$, depending on $f \in F$. This is apparently not what's being asked.
Because the target distribution is fixed for every target $f^* \in F$, the PAC-sample upper ...
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,\...
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
This was proven in
M. Talagrand. Sharper bounds for Gaussian and empirical processes. The Annals of Probability, pages 28–76, 1994.
This is mentioned in e.g. this paper (Section 1.1.2), which does a pretty good job (in my opinion) of summarizing the landscape.
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
Another good introductory book is "Foundations of Machine Learning" by Mohri et al.: https://www.amazon.com/Foundations-Machine-Learning-Mehryar-Mohri/dp/0262039400/. It has a large overlap with the Shai and Shai book, but also quite a bit of content that they don't cover.
There are also good books and surveys on more advanced or specialized topics:
...
5
For the Boolean n-cube $(\{0, 1\}^n, \leq)$ (or, equivalently, for the poset $(2^S, \subseteq)$ of all subsets of an n-element set), the answer is given by Korobkov and Hansel's theorems (from 1963 and 1966, respectively). Hansel's theorem [1] states that an unknown monotone Boolean function (i.e., an unknown monotone predicate on this poset) can be learned ...
5
Following Simone's answer, Gerard Biau has several very good papers looking at convergence and consistency for random forests. The analyses are for slightly simplified versions of the algorithm compared to Breiman 2001, but less simplified than previous results.
Biau's papers (along with his collaborators) are all available on his website:
http://www....
5
Rather than computing the VC dimension of a particular function class, it's usually more interesting to understand how generic properties of a function class relate to its VC dimension. For example, function spaces with linear dimension $d$ have VC-dim at most $d$. You can also bound the VC-dim of a function class realized by circuits with bounded depth/...
5
Depth-2 TC0 probably can't be PAC learned in subexponential time over the uniform distribution with a random oracle access. I don't know of a reference for this, but here's my reasoning: We know that parity is only barely learnable, in the sense that the class of parity functions is learnable in itself, but once you do just about anything to it (such as ...
5
I don't have a solution to this problem, but the analogous case where the two distributions are discrete has been analyzed in the cryptographic literature.
Suppose we want to distinguish between two distributions $\mathcal{D}_0$, $\mathcal{D}_1$, where these two distributions are "close". Suppose we have $n$ observations (i.e., a sequence of $n$ numbers ...
Only top voted, non community-wiki answers of a minimum length are eligible
