Questions tagged [computational-learning-theory]

For questions related to computational learning theory (or, in short, learning theory), which is a research subfield of artificial intelligence devoted to studying the design and mathematical analysis of machine learning algorithms. Computational learning theory (COLT) is largely concerned with computational and data efficiency. A seminal paper in COLT is Valiant's "A theory of the learnable" (1984).

21 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
4 votes
0 answers
189 views

How to show Sauer's Lemma when the inequalities are strict or they are equalities?

I have the following homework. We proved Sauer's lemma by proving that for every class $H$ of finite VC-dimension $d$, and every subset $A$ of the domain, $$ \left|\mathcal{H}_{A}\right| \leq |\...
Ben's user avatar
  • 253
3 votes
0 answers
122 views

Are No Free Lunch theorem and Universal Approximation theorem contradictory in the context of neural networks?

To my understanding NFL states that, we cannot have an hypothesis (let's assume it is an approximator like NN in this case) class that can't achieve certain accuracy parameters $\leq \epsilon$ with ...
user avatar
3 votes
0 answers
228 views

What is the relation between the definition of learnability of Vapnik and Gold and learnability of neural networks?

Gold showed that a language can be learned only if it contains a finite set of sentences. We know that deep neural networks can implement any function. Does this contradict the Gold's result? What ...
XL _At_Here_There's user avatar
2 votes
0 answers
65 views

Is orthogonal initialization still useful when hidden layer sizes vary?

Pytorch's orthogonal initialization cites "Exact solutions to the nonlinear dynamics of learning in deep linear neural networks ", Saxe, A. et al. (2013), which gives as reason for the ...
Gabi's user avatar
  • 121
2 votes
0 answers
103 views

What is the effect of K in K-NN on the VC dimension?

What is the effect of K in K-NN on the VC dimension? When K increases, is the VC dimension decreased or increased, or we can't say anything about this? Is there a reference book that discusses this?
robot learning's user avatar
2 votes
0 answers
128 views

What is the relationship between PAC learning and classic parameter estimation theorems?

What are the differences and similarities between PAC learning and classic parameter estimation theorems (e.g. consistency results when estimating parameters, e.g. with MLE)?
FourierFlux's user avatar
2 votes
1 answer
175 views

An infinite VC dimensional space vs using hierarchical subspaces of finite but growing VC dimensions

I have the following scenario. I have a binary classification problem, whose underlying function is a step function. The probability distribution of feature vectors is a uniform over the domain. Case ...
Rajesh D's user avatar
  • 121
2 votes
0 answers
203 views

How can I show that the VC dimension of the set of all closed balls in $\mathbb{R}^n$ is at most $n+3$?

How can I show that the VC dimension of the set of all closed balls in $\mathbb{R}^n$ is at most $n+3$? For this problem, I only try the case $n=2$ for 1. When $n=2$, consider 4 points $A,B,C,D$ and ...
j200932's user avatar
  • 181
2 votes
0 answers
971 views

A problem about the relation between 1-oracle and 2-oracle PAC model

This problem is about two-oracle variant of the PAC model. Assume that positive and negative examples are now drawn from two separate distributions $\mathcal{D}_{+}$ and $\mathcal{D}_{-} .$ For an ...
j200932's user avatar
  • 181
2 votes
0 answers
80 views

How to Prove This Inequality, Related to Generalization Error (Not Using Rademacher Complexity)?

This is an inequality on page 36 of the Foundations of Machine Learning by Mohri, but the author only states it without proof. $$ \mathbb{P}\left[\left|R(h)-\widehat{R}_{S}(h)\right|>\epsilon\right]...
j200932's user avatar
  • 181
2 votes
0 answers
220 views

Convert a PAC-learning algorithm into another one which requires no knowledge of the parameter

This is part of the exercise 2.13 in the book Foundations of Machine Learning (page 28). You can refer to chapter 2 for the notations. Consider a family of concept classes $\left\{\mathcal{C}_{s}\...
j200932's user avatar
  • 181
1 vote
0 answers
79 views

Where can I find the solutions to the problems in the book "An Introduction to Computational Learning Theory"?

I have been going through "An Introduction to Computational Learning Theory" (Kearns-Vazirani). I don't know if my solutions to the problems are correct and have no other way of checking my ...
aome's user avatar
  • 111
1 vote
0 answers
55 views

Can the Jacobian of a Neural Network be Full Column Rank?

Let $\mathcal{X}$ be the input data space and $\mathcal{Y}$ be the output data space. $f: \mathcal{X} \to \mathcal{Y}$ is a function represented by some Neural Network. Is it possible to to check if ...
BJMG's user avatar
  • 21
1 vote
1 answer
177 views

What is the relevance of the concept size to the time constraints in PAC learning?

My question is about the relevance of concept size to the polynomial-time/example constraints in efficient PAC-learning. To ask my question precisely I must first give some definitions. Definitions: ...
OlimData's user avatar
1 vote
0 answers
21 views

Characterize the high probability bound for learning algorithm

Suppose we have a dataset $S = (x_1, \dots x_n)$ drawn i.i.d from distribution $D$, a learning algorithm $A$ and error function $err$. The performance of $A$ is therefore defined by the error/...
Vassily's user avatar
  • 111
1 vote
0 answers
24 views

Does distribution of data augmentation parameters matter?

Idea Let's say we have simple pictures dataset containing 40x40 images of digits. We have only one image of each digit. We want to use that as training set, but we need more data, so we use data ...
MASTER OF CODE's user avatar
1 vote
0 answers
48 views

How can I estimate the minimum number of training samples needed to get interesting results with WGAN?

Let's say we have a WGAN where the generator and critic have 8 layers and 5 million parameters each. I know that the greater the number of training samples the better, but is there a way to know the ...
FalseSemiColon's user avatar
1 vote
0 answers
63 views

Can an ML model sort a random sequence of numbers from 1 to $ 2^{2^{512}} $ in our universe in infinite time?

I am pondering on the question in the title. As a human being, somehow I can sort a random sequence of numbers from 1 to $ 2^{2^{512}} $ in our universe in infinite time (But I am not sure.). Can an ...
verdery's user avatar
  • 688
1 vote
0 answers
72 views

How estimate the minimum size of an autoencoder to overfit the training data?

Given e.g. $1$M vectors of $1000$ floating points each, where every point in vectors is sampled from a uniform distribution between $-1$ to $1$, how to estimate the minimum network size required ...
ENECO's user avatar
  • 21
0 votes
0 answers
13 views

How can we quantify "hardness to learn" for a general function in machine learning?

It's for sure that some functions are harder to learn than others. For example, a linear function is super easy to learn. However, a cryptographic encryption with secret key is unlearnable, and cannot ...
Marc_12's user avatar
0 votes
0 answers
19 views

Can manual feature extraction be considered a part of a learning algorithm?

A learning algorithm is a tuple $(\mathcal{H}, \mathcal{O}, \mathcal{L})$ where $\mathcal{H}$, $\mathcal{O}$ and $\mathcal{L}$ are the hypothesis class, optimizer and loss function respectively. We ...
ado sar's user avatar
  • 150