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 ...
- 18k
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 $...
- 10.1k
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 ...
- 126
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 ...
- 10.1k
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 ...
- 881
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 ...
- 1,419
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 ...
- 18k
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,...
- 10.1k
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: ...
- 186
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}{\...
- 10.1k
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 ...
- 4,361
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. ...
- 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 ...
- 11.8k
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, ...
- 10.1k
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 ...
- 66
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 ...
- 10.5k
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 (...
- 881
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-\...
- 441
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 ...
- 4,361
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 ...
- 4,361
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., ...
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 ...
- 10.1k
4
votes
Accepted
Applications of Takens' theorem to TCS?
Takens himself did some CS work although not TCS work. He did some attractor reconstruction stuff with neural networks, for example (https://clgiles.ist.psu.edu/papers/NC-2000-learning-chaos-nn.pdf) ...
- 56
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'$. ...
- 10.1k
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 ...
- 4,361
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 ...
- 5,444
4
votes
Accepted
$L_\mathcal{D}(A(S)) \le 0.1$ with prob at least $0.9$ implies PAC learnability
The end of the proof of Theorem 7.2 explicitly states "Using the fundamental theorem of statistical learning, this implies that the VC dimension of $\mathcal{H}_n$ must be finite, and therefore $\...
- 4,361
4
votes
Accepted
About learning a single Gaussian in total-variation distance
Essentially, this follows from three facts:
learning a Gaussian in total variation distance $\delta$ is equivalent to learning its two parameters, $\mu,\Sigma$, to (respectively) $\ell_2$ and ...
- 4,361
4
votes
Reference Request: Computational Learning Theory
I have a list of references (incomplete) that may interest you: https://kiranvodrahalli.github.io/links/#resources-notes-textbooks-monographs-classes-etc
(second all the existing suggestions).
- 41
4
votes
Accepted
Testing for finite expectation
This seems to be addressed in the following paper by Joseph P. Romano, Section 3 [1] (specifically, Example 1):
Example 1 (Finite versus not finite mean). Let $X$ be $X_1, \dots, X_n$, $n$ i.i.d. ...
- 4,361
Only top scored, non community-wiki answers of a minimum length are eligible