# Questions tagged [learning-theory]

Questions about the design and analysis of machine learning algorithms.

78 questions
Filter by
Sorted by
Tagged with
65 views

### A confidence interval algorithm for Disagreement coefficient

My question has to do with the disagreement coefficient in active learning. I've been trying to solve the following question, where I need an algorithm to derive a confidence interval for $\theta$, ...
9 views

### Learning algorithms- difference between a learner (the algorithm) having continuous access to the samples (oracle) vs getting all at start

Is there any fundamental difference between learning algorithms e.g. variants of PAC which have continuous access to examples on which to train (i.e. these are obtained as the algorithm runs, when ...
24 views

### Applications of derivative only, zeroth-order free optimization

I understand what is derivative-free optimization, and I am thinking a similar problem where the function $f$ we are optimizing is unknown and the only information we can acquire is the derivative. In ...
69 views

### Pseudo-dimension of a subset of affine functions

Let's say there are two sets of affine functions. $\mathcal{A} = \{ax +b \mid a,b \in \mathbb{R}\}$ $\mathcal{H} = \{2x + 1, x, 3x + 4, 4x\}$ I know that the $\mathrm{Pdim}(\mathcal{A}) = 2$. From ...
35 views

### Uniform convergence for a class of finite dimension

The following theorem is cited in Balcan, M.F., Sandholm, T. and Vitercik, E., 2019. Estimating approximate incentive compatibility which I am currently reading and it is referenced to David Pollard. ...
15 views

### interplay between evolutionary algorithms and machine learning from neuroscience

Evolutionary algorithms (EA) being those inspired by the natural evolution (mutation and selection), and Machine Learning (ML) motivated by the neural concepts of human and animal learning (brain's ...
33 views

### Is memorization necessary in learning computer science?

Backgrounds Hi guys, I am now trying to teach myself some basic computer science theories. Specifically, I am using the book, CSAPP (computer systems, from a programmer’s perspective) and 15-213 ...
79 views

### AdaBoost - why using such alpha function?

I'm reading the paper where AdaBoost was invented (link), and I couldn't understand why they have chosen the formula α_t = 1/2 * ln((1-ε_t) / ε_t). snippet: ...
44 views

57 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 ...
50 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, ...
52 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 ...
111 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 ...
31 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 ...
43 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 <...
566 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 ...
36 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 ...
30 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 ...
100 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 ...
18 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 ...
75 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 ...
165 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 ...
72 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 ...
27 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 ...
54 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 ...
458 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 ...
37 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 ...
56 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 ...