# Questions tagged [learning-theory]

Questions about the design and analysis of machine learning algorithms.

72 questions
Filter by
Sorted by
Tagged with
16 views

48 views

### Method for combining derivative free optimization results of different data inputs

I am working on an algorithm that has multiple fixed parameters. The algorithm analyzes time series data and spits out a number. The fixed parameters need to be such that this number is as small as ...
30 views

### Is class of threshold functions Agnostic PAC Learnable?

In "Understanding Machine Learning, From Theory to Algorithms" by Shalev and Ben-David, on page 44 example 6.1, it is proved that the class of threshold functions are PAC learnable. on the other hand, ...
50 views

### Labeled points in $\{0,1\}^n$ such that every linear separator requires exponential weights

I want to find labeled samples in $\{0,1\}^n$ such that the Perceptron algorithm takes $2^{\Omega(n)}$ steps to converge. One way to do this would be to find a sequence of labeled examples that are ...
94 views

### PAC learning vs. learning on uniform distribution

The class of function $\mathcal{F}$ is PAC-learnable if there exists an algorithm $A$ such that for any distribution $D$, any unknown function $f$ and any $\epsilon, \delta$ it holds that there exists ...
24 views

### Uniform Convergence and VC Theroy

I've started reading more about statistical learning theory, specifically this paper right here and I cannot understand the following part: It turns out the conditions required to render empirical ...
10 views

### What does “smooth control” here mean?

I came across the following statement in this pdf. This allows the learner to have smooth control over the bias-complexity tradeoff. What does "smooth control" here mean? How do you understand ...
41 views

### What are the basics of CS i should know,before I start my journey into machine learning

I am myself a non-cs graduate and would love to be a machine learning engineer. I have learned to code and know the basics of <...
151 views

### VC dimension of the class of polynomial classifiers of degree $n$

I came across this statement on page 85 of the book "understanding machine learning: from theory to algorithms" The general idea is as follows: Consider a binary classiﬁcation problem with the ...
30 views

### How can I understand the multi-class version of “shattering” intuitively? [closed]

I'm learning machine learning. VC dimension is a good way to measure the complexity of hypothesis class for binary classifier and has a very good intuitive explanation from shattering. When we discuss ...
27 views

### Covering numbers to show that H is agnostically PAC-learnable

Suppose $X=[0,1]$ and $Y=[0,1]$, and we use the squared loss Let's define the hypothesis class $H = {h(x) = (x-a)^2 : a \in [0,1]}$. Question: How can covering numbers be used to show that this ...
74 views

### How do you prove the Natarajan's Lemma intuitively?

Let $H$ be a hypothesis class of multiclass predictors; namely, each $h\in H$ is a function from $X$ to $[k]$. Denote the Natarajan dimension of $H$ by $Ndim(H)$. Hope you can give me an intuitive ...
15 views

### Hypothesis space in AdaBoost or general Machine learning

I was curious about the following: in most learning algorithms, when an algorithm is said to learn a concept class $C$ then the algorithm outputs a function from the hypothesis space $H$ and often ...
65 views

### How can the VC-dimension of Turing machine be finite?

The VC-dimension of a hypothesis class $\mathcal{H}$ is defined to be the size of the maximal set $C$ such that $\mathcal{H}$ cannot shutter. This paper shows that the VC-dimension of the set of all ...
105 views

### Dana Angluin's L* algorithm - Hypothesis inconsistent

is it possible for the Dana Angluin's L* algorithm that a hypothesis is inconsistent? So assume we have a closded observation table for a regular language L. Now after creating the hypothesis we will ...
105 views

### Why is Agnostic PAC learnability a stronger criterion as compared to the PAC learnability?

I am trying to understand the mentioned question. According to me, it should be other way around as it is easier to find hypothesis which is approximately correct compared to the optimal hypothesis in ...
66 views

### Weighting function for Non Uniform Learning

Consider a hypothesis class $H = \cup_{n=1}^{\infty} H_n$, where for every $n\in N$, $H_n$ is finite. Find a weighting function $w : H ->[0, 1]$ such that $\sum_{h \in H} w(h) ≤ 1$ and so that for ...
26 views

### what does this phrase mean: “train a policy network”

I am familiar with the basics (and perhaps a substantial amount of basics) of imitation learning and reinforcement learning. In IL (imitation), we take demonstrations from an assumed expert, which we ...
30 views

### Query complexity of exact learning and combinatorial parameter

When defining the query complexity of exact learning for a concept $c$ (considered as a function from $\{0,1\}^n \mapsto \{0,1\}$) in a concept class $\mathcal{C}$, we often come across the following ...
50 views

### What are good examples of computational theories for A.I. according to David Marr's Definition?

I was reading David Marr's "Artificial Intelligence-A Personal View" and he talks about "computational theory of AI" or what he laters labels as "Type 1" Theory. He provides the example of Chomsky's ...
361 views

### VC dimension of finite unions of one-sided intervals

What is the VC dimension of $k$ finite unions of one-sided intervals: If we take 3 one-sided intervals like $(-\infty, a_1]$, $(-\infty, a_2]$ and $(-\infty, a_3]$, I think union of these ...
36 views

### Does selecting the same arm has the same reward?

In multi-armed bandit problem, we have a set of $K$ arms. In each round $t$, a bandit selects an arm $k$ and receives a reward $r_{kt}$. The objective is to maximize the rewards after $T$ rounds. My ...
54 views

### Automatic learning/discovery of logics

Are there efforts to automatically discover new logics? Logics are simple structures - they have formal language, deduction rules, semantics and certain properties that are proved or discarded for ...
117 views

398 views

### any hope for a universal automatic parser?

Say you are a program, and you are given some source code but you don't know in what language, it can be C++/Java/Python/Lisp/... all you know is that it is highly structured and LR(1) parse-able, and ...
424 views

### The VC dimension when the samples are fixed

The VC dimension is usually used in the following way. There is a space of hypotheses. There is an unknown probability distribution. We sample some training-samples from this distribution. We find the ...
69 views

### In the learning theory version of Occam's razor, why can't I just declare whatever hypothesis I want to be “shortest”?

Occam's razor states that shorter explanations (formally speaking, hypotheses) are more likely to be correct. Indeed this can be formalized: for a hypothesis class $\mathcal H$ one may ascribe ...
127 views

### Is SRM necessary to prove that a countable union of agnostic PAC learnable classes is nonuniformly learnable?

The following I believe is a direct proof of this fact. If a learner is tasked to be $\epsilon$-competitive with a hypothesis $h \in \mathcal H_n$, where $\mathcal H_n$ is agnostic PAC learnable, it ...
54 views

### Is there a non-linear version of ICA?

"Independent Component Analysis" is this : someone is sampling a random vector $s \in \mathbb{R}^d$ such that all its components $s_i$ are mutually independent and $\mathbb{E}[s_i^4] < 3$ and the ...
There are of course $n \choose k$ monotone disjunctions which bounds the VC dimension at $\log_2 {n \choose k}$. I'm wondering if this is bound at $k \log_2 n$? (Possibly follows from combinatorial ...