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

Best query complexity of Goldreich-Levin / Kushilevitz-Mansour learning algorithm

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

Approximating the sign rank of a matrix

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 ...
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
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
Accepted

Does learning conjunctions with malicious noise reduce to learning conjunctions with random noise?

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

On the status of learnability inside $\mathsf{TC}^0$

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

What is the VC Dimension of the $k-$Junta class

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 ...
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

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

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
Accepted

Rademacher complexity and lowerbounds in learning theory

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

Tight VC bound for agnostic learning

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

Sample complexity of distinguishing two Gaussian distributions?

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

Tolerance parameter of statistical query model and adaptivity

What you are saying is that given $N$ random samples one cannot simulate an algorithm that makes $T$ queries to VSTAT$(N)$. If the $T$ queries are chosen adaptively then one might need more samples (...
user avatar
  • 881
5 votes

On the status of learnability inside $\mathsf{TC}^0$

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

Resource listing models with known VC dimension

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, ...
user avatar
  • 10k
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
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-\...
user avatar
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 ...
user avatar
  • 4,331
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 ...
user avatar
  • 4,331
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., ...
user avatar
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 ...
user avatar
  • 10k
4 votes

Property testing in other metrics?

The work of Berman, Raskhodnikova, and Yaroslavtsev [1] introduces testing of functions $f\colon [n]^d\to \mathbb{R}$ with regard to $L_p$ distances, for $p\geq 1$. It is meant to capture situations ...
user avatar
  • 4,331
4 votes

Minimizing residual finite state automata

Let the "DFA $\to$ NFA" problem denote the following: Given a DFA $A$ and an integer $k$, is there an NFA with at most $k$ states equivalent to $A$? Similarly, let "DFA $\to$ RFSA" denote the problem ...
user avatar
4 votes
Accepted

Learning from derivative data

If your function is $f:\mathbb{R}\to\mathbb{R}$, you can "learn" $f'$ as a standard regression problem (linear, polynomial, etc.) and then recover $f$ up to an additive constant by integrating $f'$. ...
user avatar
  • 10k

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