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....
16
According to Garey and Johnson (p. 174), REGULAR EXPRESSION NON-UNIVERSALITY is PSPACE-complete. This is the problem of deciding whether a regular expression over $\{0,1\}$ does not generate all strings. So your problem is also PSPACE-complete.
Here is one way to see that the OP's problem is in PSPACE. Given a DFA $A$ and a regular expression $r$, construct ...
14
As @TsuyoshiIto suggests, there is an $O(n\log n)$-time algorithm for this problem, due to Edelsbrunner and Preparata. In fact, their algorithm finds a convex polygon with the minimum possible number of edges that separates the two point sets. They also prove an $\Omega(n\log n)$ lower bound for the more general problem in the algebraic decision tree model;...
14
I don't know if you'll consider the following a non-trivial bound, but here I go.
First, to be clear so that we're not confusing $c$-DNF with $k$-term DNF (which I often do), an $c$-DNF formula over variables $x_1, \ldots, x_n$ is of the form $\vee_{i=1}^{k}(\ell_{i,1} \wedge \ell_{i,2} ... \ell_{i,c})$ where $\forall 1 \le i \le k$ and $1 \le j \le c$, $\...
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
Yes, some lower bounds are known. For example, assuming $NP \neq coNP$, you cannot even properly learn read-thrice DNF formulas in polynomial time. There is a whole paper developing such hardness results using something called the "representation problem".
To answer your linked-to question: Schapire, in his dissertation, in addition to proving that "weak ...
11
I'll take a shot at your first question:
Are there examples of natural function families that quantum computers can learn faster than classical computers given cryptographic assumptions?
Well, it depends on the exact model and the resource being minimized. One option is to compare the sample complexity (for distribution-independent PAC learning) of the ...
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
Sorry I'm late -- it's a wonderful question! As others have already pointed out, that's exactly why I asked the question in my BQP vs. PH paper, and why I spent 4 or 5 months working on it without success back in 2008. One way to answer the question would have been to prove a much more general statement that I called the "Generalized Linial-Nisan ...
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
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 ...
8
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), ...
7
I believe you would enjoy Theory of Classification: A Survey of Recent Advances by Boucheron, Bousquet, and Lugosi. In particular, it starts by building up basic generalization theory via Rademacher complexities, introduces some useful tools (like the contraction principle, whose proof you can track down in Shai&Shai's notes referenced in the answer by ...
7
The LPN problem is indeed believed to be hard, but like most problems we believe are hard, the main reason for it is that many smart people have tried to find an efficient algorithm and failed.
The best "evidence" for LPN's hardness comes from the high statistical query dimension of the parity problem. Statistical queries capture most known learning ...
7
Sorry, but there is lots of evidence that not only is this problem a pain in the univariate case, but moreover that having few dimensions actually makes things worse.
For evidence of the difficulty, please see Proposition 15 in Section 6 ("Exponential dependence on $k$ is inevitable") and the related Figure 1 of the following paper, the follow-up to Ankur ...
7
For some material more recent than Kearns and Vazirani, you could check out Rocco Servedio's lecture notes for Advanced Topics in Computational Learning Theory, or the notes from Sasha Rakhlin's class.
7
Kearns and Vazirani is maybe a bit old, but good introduction.
7
This is not a complete answer, but it's too long to be a comment.
I think I found an example for which the bound $\lceil \log_2 N_X \rceil$ is not tight.
Consider the following poset. The ground set is $X=\{a_1, a_2, b_1, b_2\}$, and $a_i$ is smaller than $b_j$ for all $i,j\in\{1,2\}$. The other pairs are incomparable. (The Hasse diagram is a $4$-cycle).
...
7
In their paper Every Poset Has a Central Element, Linial and Saks show (Theorem 1) that the number of queries required to solve the ideal identification problem in a poset $X$ is at most $K_0 \log_2 i(X)$, where $K_0 = 1/(2 - \log_2(1 + \log_2 5))$ and $i(X)$ is the number of ideals of $X$. What they call an "ideal" is actually a lower set and there is an ...
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
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
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
To drive home the point of anonymous moose's example, consider the concept class that consists of functions that output 1 on only one point in {0,1}^n. The class is of size 2^n, and 2^n queries are needed in the worst-case. Take a look at worst-case Teaching Dimension (Goldman & Schapire) which provides something similar to what you're looking for.
Only top voted, non community-wiki answers of a minimum length are eligible
