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
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 ...
mark mark's user avatar
  • 763
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 ...
heleone's user avatar
  • 151
14 votes
1 answer
572 views

What are the state-of-the-art results on the generalization ability of deep learning methods?

I've read a few classic papers on different architectures of deep CNNs used to solve varied image-related problems. I'm aware there's some paradox in how deep networks generalize well despite ...
Shirish Kulhari's user avatar
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, ...
Ilya's user avatar
  • 133
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 ...
Alexander Soare's user avatar
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 ...
S.L. Barth is on codidact.com's user avatar
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 ...
Nico A's user avatar
  • 201
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 ...
PMaynard's user avatar
  • 248
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,...
Qwarzix's user avatar
  • 83
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 ...
Jonathan Azpur's user avatar
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?
jaeger6's user avatar
  • 308
7 votes
1 answer
796 views

Are PAC learning and VC dimension relevant to machine learning in practice?

Are PAC learning and VC dimension relevant to machine learning in practice? If yes, what is their practical value? To my understanding, there are two hits against these theories. The first is that ...
FourierFlux's user avatar
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 ...
Stella Biderman's user avatar
6 votes
1 answer
355 views

Is there a way of converting a neural network to another one that represents the same function?

I have read the paper Neural Turing Machines and the paper On the Computational Power of Neural Nets about the computational power of neural networks. However, it isn't still clear to me one thing. ...
ViniciusArruda's user avatar
6 votes
2 answers
158 views

Can we teach an artificial intelligence through sentences?

Could we teach an AI with sentences such as "ants are small" and "the sky is blue"? Is there any research work that attempts to do this?
zooby's user avatar
  • 2,206
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 ...
Stefan Radonjic's user avatar
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 ...
Tyler Hilbert's user avatar
5 votes
3 answers
10k views

How can the generalization error be estimated?

How would you estimate the generalization error? What are the methods of achieving this?
kenorb's user avatar
  • 10.5k
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 ...
Ken Grimes's user avatar
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 ...
Matheo's user avatar
  • 143
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 ...
Asvin's user avatar
  • 141
4 votes
2 answers
260 views

Why does estimation error increase with $|H|$ and decrease with $m$ in PAC learning?

Why does estimation error increase with $|H|$ and decrease with $m$ in PAC learning? I came across this statement in the section 5.2 of the book "understanding machine learning: from theory to ...
Ben's user avatar
  • 253
4 votes
1 answer
1k views

Can neural networks with a sigmoid as the activation function of the output layer approximate continuous functions?

Neural networks are commonly used for classification tasks, in fact from this post it seems like that's where they shine brightest. However, when we want to classify using neural networks, we often ...
ABIM's user avatar
  • 545
4 votes
1 answer
562 views

In deep learning, do we learn a continuous distribution based on the training dataset?

At least at some level, maybe not end-to-end always, but deep learning always learns a function, essentially a mapping from a domain to a range. The domain and range, at least in most cases, would be ...
ashenoy's user avatar
  • 1,409
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$...
John Doe's user avatar
  • 143
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
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). ...
stoic-santiago's user avatar
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 ...
nbro's user avatar
  • 40.5k
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 ...
thx1138's user avatar
  • 31
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?
The Pointer's user avatar
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 ...
Gilad Deutsch's user avatar
3 votes
1 answer
720 views

What is the maximum number of dichotomies in a square?

I am new to machine learning. I am reading this blog post on the VC dimension. $\mathcal H$ consists of all hypotheses in two dimensions $h: R^2 → \{−1, +1 \}$, positive inside some square boxes and ...
Rain's user avatar
  • 31
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
2 answers
1k views

What is the difference between a learning algorithm and a hypothesis?

What's the distinction between a learning algorithm $A$ and a hypothesis $f$? I'm looking for a few concrete examples, if possible. For example, would the decision tree and random forest be considered ...
Shirish Kulhari's user avatar
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 ...
conscious_process's user avatar
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}$ ...
user avatar
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 ...
user30381's user avatar
2 votes
1 answer
629 views

Is there any practical application of knowing whether a concept class is PAC-learnable?

A concept class $C$ is PAC-learnable if there exists an algorithm that can output a hypothesis with probability at least $(1-\delta)$ (the "probably" part), and an error that is less than $\epsilon$ (...
calveeen's user avatar
  • 1,261
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 ...
nbro's user avatar
  • 40.5k
2 votes
1 answer
421 views

How does the number of stacked LSTM layers or units in each layer affect the model complexity?

I playing around sequence modeling to forecast the weather using LSTM. How does the number of layers or units in each layer exactly affect the model complexity (in an LSTM)? For example, if I ...
Manojk07's user avatar
  • 121
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 ...
Graviton's user avatar
  • 261
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