40
There are a bunch of "no free lunch" theorems in machine learning, roughly stating that there can be no one master learning algorithm that performs uniformly better than all other algorithms (see, e.g., here http://www.no-free-lunch.org/ ). Sure enough, deep learning can be "broken" without much difficulty:
http://www.evolvingai.org/fooling
Hence, to be ...
27
There are two main gaps in our understanding of neural networks: optimization hardness and generalization performance.
Training a neural network requires solving a highly non-convex optimization problem in high dimensions. Current training algorithms are all based on gradient descent, which only guarantees convergence to a critical point (local minimum or ...
20
The two approaches provide very different guarantees.
The JL Lemma says essentially "you give me the error you want, and I'll give you a low dimensional space that captures the distances upto that error". It's also a worst-case pairwise guarantee: for each pair of points, etc etc
The SVD essentially promises "you tell me what dimension you want to live in,...
17
Not sure how much of an answer this is, I'm just indulging in some rumination.
Question 1 could be equally asked about P $\neq$ NP and with a similar answer -- the techniques/ideas used to prove the result would be the big breakthrough more so than the conclusion itself.
For Question 2 I want to share some background and a thought. Pretty much all the ...
15
Yes, any such pair can be separated by a formula of size $O(n)$. More generally, any disjoint pair $P,N\subseteq\{0,1\}^n$ of size $s=|P|+|N|$ can be separated by a decision tree of size $O(s)$, which can be implemented as an $O(s)$-size formula by replacing each query node with $(p\land\cdots)\lor(\neg p\land\cdots)$.
It suffices to observe that there ...
12
BP and most of its variants are proved to converge on graphs without cycles. When you have cycles they show very strange behavior sometimes. For these cases people have tried different approximations schemes, for example Sherali-Adams, Lovasz-Schrijver, and Lasserre Hierarchies.
See [1] for a comprehensive review of these approximations. Also (Wainwright ...
11
If the learning algorithm is proper (i.e. it always produces a hypothesis from the class $F_n$), then it also gives a testing algorithm -- simply run the learning algorithm, and see whether the hypothesis it produced has error rate $<\epsilon$, which can be done with only $\approx 1/\epsilon^2$ samples. If it does, since the hypothesis is in $F_n$, this ...
11
Another take on this question, to add to @Aryeh's remarks: For many other models of learning, we know the "shape" of the hypothesis space. SVMs are the best example of this, in that what you're finding is a linear separator in a (possibly-high dimensional) Hilbert space.
For neural networks in general, we don't have any such clear description or even an ...
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
There is no way to choose the parameters A, B, C, D properly;
as it is the case for most heuristics, the parameters are chosen ''by experience''.
Worse, there is no guarantee that the solution (the array of the outputs)
of this heuristic is indeed a feasible TSP tour!
In this context, perhaps interesting to read: Wilson and Pawley,
On the stability of ...
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
There are many open algorithmic problems. All problems below (other than the last bullet) are NP-hard, so we are interested in the best approximation ratio we can achieve in polynomial time. The following are just a sample:
Given a non-negative submodular function on a universe $U$, find a set $A$ of size at most $k$ maximizing $f(A)$. The best known ...
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
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 approximate Caratheodory theorem goes back to the 60s, and probably way earlier than that (it follows for example from the mistake bound of the preceptron algorithm analysis). As for the dimensionality reduction, the answer is no - the supporting subsets are different subsets, and their number is too large. In particular, the number of possible subsets ...
9
For NeurIPS (previously NIPS), the NeurIPS website itself is a good source: look for a paper, go to its page, and click on the "BibTex" link. Here is a random sample (!):
ICML, COLT, and JMLR appear to have similar BibTex-ready websites: see http://proceedings.mlr.press/. For instance, going to the abstract of a randomly chosen paper from ICML'15:
ICLR ...
8
(wow! after three years of time passing, this is now easy to answer. funny how that goes! --Daniel)
This "Learning with (Signed) Errors" (LWSE) problem, as invented-and-stated above by me (three years ago), trivially reduces from the Extended Learning with Errors (eLWE) problem first introduced in the work Bi-Deniable Public-Key Encryption by O'Neill, ...
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
If your FSM is a DFA, then this is the Minimum Consistent DFA Problem, which is well known in the machine learning community. This problem is NP complete
Gold1978 - Complexity of Automaton Identification from Given Data.
The problem is also known to be hard to approximate within any polynomial factor. Indeed it is even hard to find an NFA whose number of ...
8
I think that "there is a natural limit to what computers can learn", while definitely true, is not one of the main takeaways of Valiant's paper, for two reasons. One is that I could not find any discussion of lower bounds or no-free-lunch results in this paper. Two is that surely statisticians had been aware of such fundamental limitations on learnability ...
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
Most of the patterns in my collection at http://www.ics.uci.edu/~eppstein/ca/replicators/ were found with a somewhat different heuristic search process, that was intended to find puffers but also turns out to work for replicators:
Pick a small random seed pattern
Simulate a moderate number of steps of a modified version of the cellular automaton rule, ...
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
One major task of computational learning theory is to try to handle questions like this for specific classes. In general, if you assume no structure on the hypothesis space, you basically have no choice but to look at each hypotheses individually. On the other hand, if there is a lot of structure, eg. if you assume the hypotheses are linear separators, say ...
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
Sounds like you're trying to learn a map from vector space $X$ to vector space $Y$. The first thing that comes to mind is regression, which is a map from $X$ to $\mathbb{R}$. You can of course perform multiple regressions in parallel -- one for each dimension of $Y$ -- to learn a map from $X$ to $Y$. This has the shortcoming of ignoring any "interaction&...
6
This is a question that has been haunting me recently, so I am glad you asked it.
However, I am less interested in classifying the application areas for which machine learning will dominate the computational approach than I am in the impact on advancement in the field of (traditional) algorithms. What kind of "human-crafted algorithms" research will we ...
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 ...
Only top voted, non community-wiki answers of a minimum length are eligible