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).

Filter by
Sorted by
Tagged with
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 ...
7 votes
4 answers
1k views

Are PAC learnability and the No Free Lunch theorem contradictory?

I am reading the Understanding Machine Learning book by Shalev-Shwartz and Ben-David and based on the definitions of PAC learnability and No Free Lunch Theorem, and my understanding of them it seems ...
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: ...
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 ...
2 votes
1 answer
370 views

How can neural networks approximate any continuous function but have $\mathcal{VC}$ dimension only proportional to their number of parameters?

Neural networks typically have $\mathcal{VC}$ dimension that is proportional to their number of parameters and inputs. For example, see the papers Vapnik-Chervonenkis dimension of recurrent neural ...
10 votes
5 answers
1k views

Why can neural networks generalize at all?

Neural networks are incredibly good at learning functions. We know by the universal approximation theorem that, theoretically, they can take the form of almost any function - and in practice, they ...
3 votes
2 answers
4k views

What's the difference between estimation and approximation error?

I'm unable to find online, or understand from context - the difference between estimation error and approximation error in the context of machine learning (and, specifically, reinforcement learning). ...
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 ...
1 vote
1 answer
31 views

No-Free-Lunch: Calculation of the number of sequences of examples of size $m$

In the proof of No-Free-Lunch Theorem from the book Understanding Machine Learning: From Theory to Algorithms Cambridge University Press, p.37-38, the author wrote: Let $C$ be a subset of the domain ...
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}\...
4 votes
2 answers
103 views

To what extent are neural networks stable across multiple training runs?

Quick question about LLMS (and gradient descent in general): we search the space of neural networks by gradient descending in order to minimize one explicit function but what seems to be happening is ...
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 ...
1 vote
0 answers
78 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 ...
19 votes
1 answer
1k views

What is the number of neurons required to approximate a polynomial of degree n?

I learned about the universal approximation theorem from this guide. It states that a network even with a single hidden layer can approximate any function within some bound, given a sufficient number ...
0 votes
2 answers
635 views

What should I do if my validation score is good, but my test score is bad?

I've trained my artificial neural network, and, as per standard practice, I've picked out the one neural network throughout training that did the best on my validation dataset. That is, the neural ...
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 ...
3 votes
1 answer
84 views

A model for each sub-problem vs one model for the whole problem

Let's say one wants to use a neural net to learn some function $g(x)$. Let's say that we know that $g$ is a combination of two functions (or two sub-problems), $g(x)=f_2(f_1(x))$, and that we have two ...
1 vote
2 answers
277 views

Why was the VC dimension not defined for all configurations of $d$ points?

Let's start with a typical definition of the VC dimension (as described in this book) Definition $3.10$ (VC-dimension) The $V C$ -dimension of a hypothesis set $\mathcal{H}$ is the size of the ...
1 vote
1 answer
110 views

If Least-Squares TD is computationally more expensive, then why is it more data efficient than semi-gradient TD(0)?

In Sutton-Barto (Section: 9.8 Least-Squares TD, page 228): Authors say that Least-Squares TD is the most "data efficient" form of linear TD(0). Later, in this section, they say the ...
9 votes
1 answer
3k views

What are some resources on computational learning theory?

Pretty soon I will be finishing up Understanding Machine Learning: From Theory to Algorithms by Shai Ben-David and Shai Shalev-Shwartz. I absolutely love the subject and want to learn more, the only ...
4 votes
2 answers
410 views

Mathematical foundations of the ability to learn

I am an undergraduate student in applied mathematics with an interest in artificial intelligence. I am currently exploring topics where I could do research. Coming from a mathematical background I am ...
14 votes
6 answers
3k views

Is there actually a lack of fundamental theory on deep learning?

I heard several times that one of the fundamental/open problems of deep learning is the lack of "general theory" on it, because, actually, we don't know why deep learning works so well. Even ...
2 votes
2 answers
3k views

In classification, how does the number of classes affect the model size and amount of data needed to train?

When solving a classification problem with neural nets, be it text or images, how does the number of classes affect the model size and amount of data needed to train? Are there any soft or hard ...
1 vote
1 answer
844 views

What is the minimum number of neurons and hidden layers needed to learn a Boolean function that maps $N$ bits to $1$ bit?

Suppose I have a Boolean function that maps $N$ bits to $1$ bit. If I understand correctly, this function will have $2^{2^N}$ possible configurations of its truth table. What is the minimum number of ...
5 votes
1 answer
737 views

How can I estimate how many photos I need to train ResNet-50 for image classification?

I am working on a project where I have to classify around 1000 unique objects. I'm trying to plan how much training data I will need to collect. I was planning on using ResNet-50. Is there anyway I ...
6 votes
1 answer
295 views

What does "hard for AI" look like?

In theoretical computer science, there is a massive categorization of the difficulty of various computational problems in terms of their asymptotic worst-time computational complexity. There doesn't ...
5 votes
2 answers
328 views

Is it possible to control asymptotic behaviour of neural network models?

Is it possible to specify what the asymptotic behaviour of a Neural Networks (NN) model should be? I am thinking of a NN which tries to learn a mapping $\vec y=f(\vec x)$ with $\vec x$ a vector of ...
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]...
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/...
0 votes
1 answer
442 views

Is it possible to overfit a model on infinite amounts of data?

This is a theoretical question. Is it possible to overfit a model on infinite amounts of data? Let me clarify there are no duplicates. Say, we have a generator function that produces data, with the ...
3 votes
1 answer
543 views

What is meant by "stable training" of a deep learning model?

I have read it said that the "stable training" of a deep learning model is important. What is meant by "stable training" of a deep learning model?
2 votes
1 answer
619 views

How do I prove that $\mathcal{H}$, with $\mathcal{VC}$ dimension $d$, shatters all subsets with size less than $d-1$?

If a certain hypothesis class $\mathcal{H}$ has a $\mathcal{VC}$ dimension $d$ over a domain $X$, how can I prove that $H$ will shatter all subsets of $X$ with size less than $d$, i.e. $\mathcal{H}$ ...
3 votes
3 answers
1k views

How would you intuitively but rigorously explain what the VC dimension is?

The VC dimension is a very important concept in computational/statistical learning theory. However, the first time you read its definition, you may not immediately understand what it really represents ...
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 ...
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 |\...
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?
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 ...
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 ...
4 votes
1 answer
222 views

Does a neural network exist that can learn every possible training data?

The universal approximation theorem states, that a feed-forward network with a single hidden layer containing a finite number of neurons can approximate continuous functions on compact subsets of $R^n$...
13 votes
2 answers
7k views

What are other examples of theoretical machine learning books?

I am looking for a book about machine learning that would suit my physics background. I am more or less familiar with classical and complex analysis, theory of probability, сcalculus of variations, ...
8 votes
3 answers
4k views

What is the difference between hypothesis space and representational capacity?

I am reading Goodfellow et al Deeplearning Book. I found it difficult to understand the difference between the definition of the hypothesis space and representation capacity of a model. In Chapter 5,...
7 votes
2 answers
2k views

How to estimate the capacity of a neural network?

Is it possible to estimate the capacity of a neural network model? If so, what are the techniques involved?
11 votes
3 answers
500 views

Are there any rules of thumb for having some idea of what capacity a neural network needs to have for a given problem?

To give an example. Let's just consider the MNIST dataset of handwritten digits. Here are some things which might have an impact on the optimum model capacity: There are 10 output classes The inputs ...
1 vote
1 answer
298 views

Is the VC Dimension meaningful in the context of Reinforcement Learning?

Is the VC dimension meaningful for reinforcement learning (RL), as a machine learning (ML) method? How?
1 vote
1 answer
465 views

If a neural network is a universal function approximator, can it have any prior beliefs?

Let us confine ourselves to the case where we have a $n$ dimensional input and a $+1$ or $-1$ output. It can be shown that: For every $n$, there exists a dense NN of depth 2, such that it contains ...
2 votes
1 answer
48 views

What does the notation $[m]=\{1, \ldots, m\}$ mean in the equation of the empirical error?

The empirical error equation given in the book Understanding Machine Learning: From Theory to Algorithms is My intuition for this equation is: total wrong predictions divided by the total number of ...
10 votes
2 answers
779 views

What are the learning limitations of neural networks trained with backpropagation?

In 1969, Seymour Papert and Marvin Minsky showed that Perceptrons could not learn the XOR function. This was solved by the backpropagation network with at least one hidden layer. This type of network ...
2 votes
1 answer
121 views

Is there anything theoretically revolutionary about Deep Neural Networks?

In recent years, we have seen quite a lot of impressive display of Deep Neural Network (DNN), as demonstrated most famously by AlphaGo and its cousin programs. But if I understand correctly, deep ...
3 votes
2 answers
508 views

Will a neural network always predict the correct label if it sees the exact same input during training and testing?

If I'm performing a text classification task using a model built in Keras, and, for example, I am attempting to predict the appropriate tag for a given Stack Overflow question: How do I subtract 1 ...
5 votes
4 answers
2k views

How does size of the dataset depend on VC dimension of the hypothesis class?

This might be a little broad question, but I have been watching Caltech youtube videos on Machine Learning, and in this video prof. is trying to explain how we should interpret the VC dimension in ...