Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.
40 votes

What kind of answer does TCS want to the question "Why do neural networks work so well?"

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....
user avatar
  • 10k
27 votes

What kind of answer does TCS want to the question "Why do neural networks work so well?"

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 ...
user avatar
20 votes
Accepted

When to use the Johnson-Lindenstrauss lemma over SVD?

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 ...
user avatar
18 votes
Accepted

Is BPP vs. P a real problem after we know BPP lies in P/poly?

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 ...
user avatar
  • 7,022
15 votes
Accepted

Circuit and Formula Lower Bounds for Separating Sparse Sets of Strings

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 ...
user avatar
11 votes
Accepted

Is testing easier/harder than learning?

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 ...
user avatar
  • 9,800
11 votes
Accepted

Does Approx Carathéodory's theorem implies dimensionality reduction

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 ...
user avatar
11 votes

What kind of answer does TCS want to the question "Why do neural networks work so well?"

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 ...
user avatar
11 votes

Functions that are Not Efficiently Computable but Learnable

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 $...
user avatar
  • 10k
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 ...
user avatar
10 votes

Are there any interesting open questions having to do with submodularity, specially in the intersection of theoretical machine learning?

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 ...
user avatar
  • 14.1k
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 ...
user avatar
  • 10k
9 votes

What is the best place to get BibTeX entries for ICLR and other machine learning papers?

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 ...
user avatar
  • 4,331
8 votes
Accepted

Learning with (Signed) Errors

(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 ...
user avatar
  • 5,963
8 votes
Accepted

minimal finite automata given in-words and out-words

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 ...
user avatar
8 votes
Accepted

What was the significance of Leslie Valiant's, "A Theory of the Learnable?"

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 ...
user avatar
  • 10k
7 votes

Given $f:\{0,1\}^n \rightarrow \{-1,1\}$, find a subcube with large volume and large average value

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}[...
user avatar
  • 2,743
7 votes
Accepted

Data Mining of self-replicators

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 ...
user avatar
7 votes
Accepted

Complexity of finding a consistent hyperplane

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 ...
user avatar
6 votes

Learnability of constraint satisfaction problems CSPs?

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 ...
user avatar
6 votes

Theoretical results for random forests?

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: ...
user avatar
  • 186
6 votes
Accepted

How does the Multiplicative Weights Update method maximize entropy?

Here's one way to look at it, based on usul's comment. Let the gains of each expert $i$ at time $t$ be given by $g_i^t$. Then the expected gains of the algorithm are: $$\sum_{u=1}^{t-1}\sum_i p_i^t ...
user avatar
  • 198
6 votes

Generalization bounds for multiclass learning when the output is vector space?

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 ...
user avatar
  • 10k
6 votes

If machine learning techniques keep improving, what's the role of algorithmics in the future?

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 ...
user avatar
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}{\...
user avatar
  • 10k
6 votes
Accepted

What is the best place to get BibTeX entries for ICLR and other machine learning papers?

As an update, I noticed that DBLP has added ICLR to tracking as of today. Now it has ICLR papers and their bibtex available at https://dblp.uni-trier.de/db/conf/iclr/
user avatar
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. ...
user avatar
  • 881
6 votes
Accepted

Reference Request: Computational Learning Theory

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 ...
user avatar
  • 11.7k
5 votes
Accepted

Theoretical results for random forests?

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 ...
user avatar
5 votes

Are there distribution properties which are "maximally" hard to test?

Sorry for unearthing this post -- it is quite old, but I figured having it answered may not be that bad an idea. First, it looks like you performed your Chernoff bound with some slightly odd setting ...
user avatar
  • 4,331

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