Skip to main content

Questions tagged [learning-theory]

Questions about the design and analysis of machine learning algorithms.

Filter by
Sorted by
Tagged with
0 votes
0 answers
52 views

Why can't we say that P=NP if we have an infinite text file with solution for every possible SAT combination?

I believe that I have a misunderstanding in the P=NP problem while I was thinking of how can it be proved in a non-constructive manner. We know that we can build an infinitely large text file with ...
TokieSan's user avatar
1 vote
1 answer
30 views

Why we need at most $2n$ examples to determine an axis aligned rectangle

In Ben-David & et al.'s Understanding Machine Learning, the authors wrote: Let $\mathcal{H}_n$ be the class of axis aligned rectangles in $\mathbb{R}^n$ , namely, $$ \mathcal{H}_n = \{h(a_1,\dots,...
Tran Khanh's user avatar
2 votes
0 answers
25 views

Representational power of Neural Neural Networks without a bias term

In a fully connected Neural Network, each perceptron has it's bias term $b$ which is learnt. Often (example, in Linear/ Logistic Regression), when we don't want to treat this bias term explicitly, we ...
Harry's user avatar
  • 21
0 votes
0 answers
27 views

Computational Learning Problem: 3-DNF Reduction

I'm not sure how to solve this problem. Problem statement is: Consider the binary classification problem where X = R d and Y = {0, 1}. Consider the class of Binary classifiers given by intersection of ...
Mr.Zhang's user avatar
0 votes
0 answers
18 views

Transductive Information Maximization vs classification with feature embedding in higher dimensional spaces?

Recent research work has shown that transductive learning/inference outperforms standard methods that were used before, where people embed features in a high dimensional space and then use the ...
Sandra's user avatar
  • 63
1 vote
0 answers
140 views

Transductive Learning vs Inductive Learning in Machine Learning

Several recent research work has shown that transductive learning/inference outperforms inductive learning/inference during classification problems. This has been found in few-shot learning, other ...
Sandra's user avatar
  • 63
0 votes
1 answer
73 views

Question about the proof for the sample complexity of axis-aligned rectangles

The classical proof for the sample complexity of the hypothesis class of axis-aligned rectangles usually begins by stating that our $A(S) \subset R^*$, where $R^*$ is the target function. My only ...
Dragoș Constantin's user avatar
1 vote
0 answers
258 views

Infinite VC Dim not PAC learnable

This is usually shown by an application of the Statistical No Free Lunch Theorem. But is this possible to show this by working simply with the definition of PAC learnability and the sample complexity ...
JustBlaze's user avatar
1 vote
0 answers
54 views

Regarding constant * opt approximation in agnostic learning

In standard agnostic learning, we assume that there is a concept class $H\subseteq \{h:\{0,1\}^n\rightarrow \{0,1\}\}$. Given samples from a distribution $D:\{0,1\}^n\times \{0,1\}\rightarrow [0,1]$, ...
postasguest's user avatar
2 votes
0 answers
68 views

Multi-class sample complexity for PAC learning using "VC dimension"

VC dimension covers the binary classification case, i.e. when we want to get a predictor $X \to \{0, 1\}$. Using VC dimension, we can get the upper bound on the sample complexity for PAC-learning. In ...
Dmitry's user avatar
  • 345
1 vote
0 answers
43 views

Precise definition of Universal Learner in Machine Learning

It is surprising to me that I cannot find a precise definition of universal learner on the internet. I can guess what it should bebut I don't want to make a mistake, therefore I have come here. Here's ...
Suraj's user avatar
  • 11
2 votes
1 answer
47 views

Generalization error bound in case of collaborative learning

I am reading the paper "Collaborative PAC Learning" by Blum et al. So I will try to setup the problem here as to avoid reading the complete section (personalized setting). Assume there are $...
Naren's user avatar
  • 43
2 votes
1 answer
284 views

Understanding halving algorithm in online learning

I am working through "Understanding Machine Learning Theory" by Shai Shalev-Schwartz. In the chapter "Online learning" I came across the halving algorithm, the author uses the ...
Naren's user avatar
  • 43
0 votes
0 answers
46 views

pseudo-dimension for knapsack problem

Let $v_i, s_i$ be the value and size of item $i$, let $\rho \in \mathbb{R}$, n be the maximum number of items. Then we add items based on $\frac{v_i}{s_i^{\rho}}$ in decreasing order. I was trying to ...
Sophie's user avatar
  • 1
1 vote
0 answers
111 views

Hoeffding's inequality applicability for sample complexity

I am trying to determine some bounds for sample complexity. Suppose we have a bounded loss function $\ell$ and target function $f:\mathcal{X}\to\mathcal{Y}$. Hypothesis $h$ is learned, then the ...
somefellow's user avatar
0 votes
1 answer
102 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$, ...
giorgioh's user avatar
  • 317
1 vote
0 answers
27 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 ...
Francis's user avatar
  • 65
0 votes
1 answer
132 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 ...
ABIM's user avatar
  • 73
2 votes
1 answer
64 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. ...
ABIM's user avatar
  • 73
0 votes
1 answer
60 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 ...
yChen's user avatar
  • 1
3 votes
1 answer
111 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: ...
Adi Peled's user avatar
1 vote
1 answer
48 views

Obtaining a set of $O(\log n)$ classifiers using multiplicative weights algorithms

I'm trying to find an algorithm that uses the multiplicative weights algorithm to obtain a set of $O(\log n)$ classifiers that classify a set $X=\{x_1, x_2, ...,x_n\}$ where the set of labels is $l \...
giorgioh's user avatar
  • 317
1 vote
0 answers
104 views

Perceptron - Generalization Bounds & Compression Bounds

A distribution $P$ over $\mathbb{R}^{d} \times\{-1,+1\}$ being $(\gamma, R)$ -separable. We now let $\mathcal{P}_{\gamma}$ denote the set of all $(\gamma, 1)$ separable distributions. For a ...
brianoconner's user avatar
0 votes
1 answer
76 views

Compression Bounds - Determine and Visualize for hypothesis vs VC dimension

I want to visualize or calculate the compression bounds for hypothesis classes. I learnt how to figure out the VC dimension. Let's say I define two hypothesis class. For example: $$ H_k = \{h ∈ (0,1)...
brianoconner's user avatar
2 votes
1 answer
110 views

Sample compression scheme and bounding the VC dimension

There is a compression function takes any sample $S$, for which there exists a function $h ∈ H$ with $L_S(h)$, and compresses it to a subset of $k$ sample points. Similarly, there is a decompression ...
brianoconner's user avatar
1 vote
0 answers
34 views

How is the RKHS norm related to sample complexity or other learning theory properties?

This is a somewhat soft question. Given two reproducing kernel Hilbert spaces (RKHSs) $H_1$ and $H_2$, if their RKHS norms only differ by a constant, i.e., $C_1\|f\|_{H_1}\le \|f\|_{H_2} \le C_2\|f\|_{...
Alex's user avatar
  • 215
1 vote
1 answer
163 views

Density of uniform distribution over two disjoint squares

A probability distribution $P$ over $X \times \{0, 1\}$. $P$ can be defined in term of its marginal distribution over $X$ , which we will denote by $P_X$ and the conditional labeling distribution, ...
brianoconner's user avatar
0 votes
0 answers
146 views

VC dimension of axis-aligned hyperplanes and their complements

This is a problem of VC that I've been trying to solve. Any help is appreciated. Let's assume hypothesis classes $H_{\mathit{init}}$ of initial segments over domain $X = \mathbb R$ and $H_{\mathit{...
brianoconner's user avatar
1 vote
1 answer
400 views

Empirical Risk and True Risk - Generalization Error Proof

I showed that, over an uncountable domain,learner A and a distribution P, such that for every sample size m and all samples S from $P^m$ $$ : L_S(A(S)) − L_P (A(S))| = 1 $$ Now I wanna prove for ...
brianoconner's user avatar
0 votes
1 answer
498 views

What is the VC dimension of the hypothesis class $H=\left\{f_{\theta_{1}, \theta_{2}}: R^{2} \rightarrow\{0,1\} \mid 0<\theta_{1}<\theta_{2}\right\}$?

I would like to know what is the VC dimension of the following hypothesis class. $$H=\left\{f_{\theta_{1}, \theta_{2}}: R^{2} \rightarrow\{0,1\} \mid 0<\theta_{1}<\theta_{2}\right\}$$ where $f_{\...
hinduml's user avatar
  • 11
1 vote
1 answer
98 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 ...
Marnix.hoh's user avatar
0 votes
0 answers
132 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, ...
Moher's user avatar
  • 101
2 votes
1 answer
79 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 ...
Ustad Kadir Misiroglu's user avatar
3 votes
1 answer
223 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 ...
Ernie's user avatar
  • 53
0 votes
1 answer
86 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 ...
Stefan Radonjic's user avatar
1 vote
1 answer
57 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 <...
Fasty's user avatar
  • 111
0 votes
2 answers
3k 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 classification problem with the ...
Ben's user avatar
  • 141
1 vote
0 answers
80 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 ...
Ben's user avatar
  • 141
2 votes
0 answers
43 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 ...
Ilan Aizelman WS's user avatar
0 votes
1 answer
204 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 ...
Ben's user avatar
  • 141
1 vote
0 answers
23 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 ...
wwjohnsmith's user avatar
1 vote
1 answer
99 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 ...
SomeoneHAHA's user avatar
0 votes
1 answer
261 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 ...
Marc's user avatar
  • 223
0 votes
1 answer
90 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 ...
Arka Pal's user avatar
  • 311
1 vote
1 answer
31 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 ...
cgo's user avatar
  • 273
2 votes
0 answers
33 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 ...
Plussoyeur's user avatar
1 vote
0 answers
76 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 ...
Charlie Parker's user avatar
1 vote
1 answer
729 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 ...
Joshna Gunturu's user avatar
1 vote
1 answer
39 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 ...
zdm's user avatar
  • 1,046
2 votes
0 answers
62 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 ...
TomR's user avatar
  • 1,401