Skip to main content
Share Your Experience: Take the 2024 Developer Survey
41 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....
Aryeh's user avatar
  • 10.6k
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 ...
Antonio Valerio Miceli-Barone's user avatar
22 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 ...
usul's user avatar
  • 7,615
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 ...
Emil Jeřábek's 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 ...
Suresh Venkat's 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 $...
Aryeh's user avatar
  • 10.6k
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 ...
S. Hanneke's user avatar
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 ...
Aryeh's user avatar
  • 10.6k
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 ...
Clement C.'s user avatar
  • 4,471
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 ...
Aryeh's user avatar
  • 10.6k
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 ...
Sasho Nikolov's user avatar
7 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/
gungunba's user avatar
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 ...
Gara Pruesse's user avatar
6 votes
Accepted

Learning a coin's bias (localized)

Write $p=p_0=1-q$. We may assume that $\epsilon<\eta \le p\le 1/2$. Then the sample complexity is of order $\log(1/\delta)$ times the reciprocal of the relative entropy $D((p,q)||(p+\epsilon,q-\...
Yuval Peres's 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}{\...
Aryeh's user avatar
  • 10.6k
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. ...
Vitaly's 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 ...
Lev Reyzin's user avatar
  • 12k
6 votes
Accepted

What's the intuition behind Rademacher complexity?

The standard "intuition" is that the Rademacher complexity quantifies the ability of the function class $F$ to fit symmetric random noise: a low value (close to 0) means that this ability is ...
Aryeh's user avatar
  • 10.6k
5 votes

Textbook/resources for a beginning researcher in (Machine) Learning Theory

People are going to recommend http://www.cs.nyu.edu/~mohri/mlbook/ and http://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf -- so I ...
Aryeh's user avatar
  • 10.6k
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 ...
Clement C.'s user avatar
  • 4,471
5 votes
Accepted

Adversarial Machine Learning, Learning with (Malicious) noise

In the proof of the positive result in [2] you are referring to, namely Theorem 2, the argument goes as follows. For every possible concept $L_i$ of the hypothesis class $\mathcal{H} = \{L_1,\dots, ...
Clement C.'s user avatar
  • 4,471
5 votes

Learning a coin's bias (localized)

Yuval Peres gave the answer in terms of the Kullback-Leibler divergence. Another way is to recall that the sample complexity will be captured by the inverse of the squared Hellinger distance between ...
Clement C.'s user avatar
  • 4,471
5 votes
Accepted

Understanding the No Free Lunch Theorem

You're asking about optimization and universal search, BUT machine-learning is tagged and you're wondering about "a uniform distribution on an infinite" discrete set so perhaps this will be helpful. ...
Aryeh's user avatar
  • 10.6k
5 votes

Proper PAC learning VC dimension bounds

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 ...
Clement C.'s user avatar
  • 4,471
5 votes
Accepted

Oncina-Garcia RPNI algorithm for learning DFAs

The algorithm is named RPNI, not RNPI. Given that the language generating the inputs is regular and that enough examples are given (the characteristic set), the algorithm returns the canonical (i.e., ...
Roman Manevich's user avatar
5 votes

What are some good resources for strengthening my theoretical foundation for machine learning?

I suggest Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Mitzenmacher and Upfal. Probability is at the foundation of machine learning and it's one of the weakest ...
Aryeh's user avatar
  • 10.6k
5 votes
Accepted

Complexity of constructing minimum depth decision trees

I think I can see a fairly easy reduction from 3DM. Let $B=\{0^J\}$, i.e., it is a singleton set with the only zero element. The points of $A$ correspond to the points of the 3DM that are to be ...
domotorp's user avatar
  • 14k
5 votes
Accepted

Is there an equivalent to VC-dimension for density estimation as opposed to classification?

For distributions with finite support of size $d$, when the error metric is the $\ell_1$ distance, the analogue of VC dimension is exactly $d$. (In fact, it's pretty much the VC dimension -- since to ...
Aryeh's user avatar
  • 10.6k
4 votes
Accepted

Convergence and representation theorems for machine learning

I recommend Neural Network Learning: Theoretical Foundations by Anthony and Bartlett. You'll find exhaustive answers to your questions there. Very briefly, theoretical learning problems tend to ...
Aryeh's user avatar
  • 10.6k
4 votes
Accepted

Are biases necessary to make neural networks universal approximators when using sigmoid activations?

No, you don't need a bias. You can have a "dummy" input (input(n+1) in your formualtion) which is always set to 1. Then the bias term is absorbed into the weights.
Aryeh's user avatar
  • 10.6k

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