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.5k
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.5k
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 ...
Andrew Morgan's 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 ...
Sasho Nikolov'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.5k
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 ...
Clement C.'s user avatar
  • 4,461
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,...
Aryeh's user avatar
  • 10.5k
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
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
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,461
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,461
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
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.5k
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 $\...
Clement C.'s user avatar
  • 4,461
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) ...
Howon's user avatar
  • 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'$. ...
Aryeh's user avatar
  • 10.5k
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 ...
Clement C.'s user avatar
  • 4,461
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 ...
Hermann Gruber's user avatar
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 ...
Clement C.'s user avatar
  • 4,461
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).
kiranv's user avatar
  • 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. ...
Clement C.'s user avatar
  • 4,461
4 votes
Accepted

What is tightest known (VC-style) sample complexity bound for uniform convergence of empirical means?

I'm not sure if claims about optimal constants are meaningful when trying to optimize all 3; often it is the case that one can be made better at the expense of another. One way to simplify the issue ...
Aryeh's user avatar
  • 10.5k
3 votes

VC dimension of intersection of half-spaces

It has been recently shown by Csikos, Kupavskii, Mustafa in "Optimal Bounds on the VC-dimension" that the VC dimension of $k$-fold unions (or intersections or XORs) of half-spaces in $R^d$ ...
Aryeh's user avatar
  • 10.5k
3 votes
Accepted

Rademacher complexity beyond the agnostic setting

(a) If you don't assume that you're "competing" against $f\in F$, you must make some assumption about the larger function class to which $f$ belongs -- otherwise, by standard no-free-lunch theorems, ...
Aryeh's user avatar
  • 10.5k
3 votes
Accepted

Rademacher complexity for piecewise-linear convex function

Since we're talking about real-valued functions, rather than VC-dimension, you probably want the fat-shattering one. The $\gamma$-fat-shattering of linear functions with $\ell_2$ norm bounded by $B$ ...
Aryeh's user avatar
  • 10.5k
3 votes
Accepted

"Learning" when test and train distributions don't match

In general, the results are pretty strongly negative --- fairly strong assumptions are needed for something like this to work. As an extreme case, suppose that training and testing distributions have ...
Aryeh's user avatar
  • 10.5k
3 votes
Accepted

Is Bayes optimal RL of a finite set of DFAs feasible?

Even determining whether there is a policy which always succeeds is NP-complete, by a reduction from constructing optimal decision trees (Hyafil and Rivest, Constructing Optimal Binary Decision Trees ...
zeb's user avatar
  • 376
3 votes
Accepted

Is this a known learning problem?

Well, we wrote a paper on it, so now it's definitely known: https://arxiv.org/abs/2010.09886
Aryeh's user avatar
  • 10.5k

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