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
18 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
1 vote
1 answer
30 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 ...
Tran Khanh's user avatar
4 votes
2 answers
100 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
2 votes
0 answers
61 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
1 vote
0 answers
76 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
0 votes
0 answers
23 views

In the proof of Neural Tangent Kernel stays constant in infinite width limit, why the norm of the dual mapping operator equals operator norm of kernel

For a fixed distribution $p^{in}$ on the input space $ \mathbb{R}^{n_0}$, consider a function space $\mathcal{F}$ defined as $\{{f: \mathbb{R}^{n_0} \rightarrow \mathbb{R}^{n_L}}\}$. On this space, ...
Shuofeng Zhang's user avatar
0 votes
2 answers
527 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 ...
Pro Q's user avatar
  • 103
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
107 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 ...
user3489173's user avatar
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
5 votes
1 answer
683 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
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
0 votes
1 answer
409 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 ...
ToAskOrNotToAsk's user avatar
3 votes
1 answer
526 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
1 vote
2 answers
271 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 ...
nbro's user avatar
  • 40.2k
3 votes
3 answers
961 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.2k
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
2 votes
0 answers
98 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
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
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
62 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
19 votes
1 answer
979 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
1 vote
0 answers
24 views

Given a dataset and a neural network, is there some heuristic or theorem to determine whether this neural network has enough capacity? [duplicate]

What is the consensus regarding NN "capacity" or expressive power? I remember reading somewhere that expressive power grows exponentially with depth, but I cannot seem to find that exact ...
gabe's user avatar
  • 11
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
13 votes
2 answers
6k 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
1 vote
1 answer
398 views

What is the representational capacity of a learning algorithm? [duplicate]

The definition I see for representational capacity is "the family of functions the learning algorithm can choose from when varying the parameters in order to reduce a training objective." (...
curiousgeorge's user avatar
1 vote
1 answer
87 views

Does this $\max$ mean that we need to maximize the regret in this regret formula?

I found that the regret in Online Machine Learning is stated as: $$\operatorname{Regret}_{T}(h)=\sum_{t=1}^{T} l\left(p_{t}, y_{t}\right)-\sum_{t=1}^{T} l\left(h(x), y_{t}\right),$$ where $p_t$ is the ...
FraMan's user avatar
  • 199
1 vote
1 answer
290 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?
OmG's user avatar
  • 1,816
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
2 votes
1 answer
604 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
1 vote
1 answer
83 views

Why is probability that at least one hypothesis out of $k$ being consistent with $m$ training examples $k(1- \epsilon)^m$?

My question is actually related to the addition of probabilities. I am reading on computational learning theory from Tom Mitchell's machine learning book. In chapter 7, when proving the upper bound ...
calveeen's user avatar
  • 1,261
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
2 votes
0 answers
126 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
1 vote
1 answer
259 views

How can a machine learning problem be reduced as a communication problem?

I once heard that the problem of approximating an unknown function can be modeled as a communication problem. How is this possible?
Raphael Augusto's user avatar
1 vote
1 answer
432 views

What do we mean by saying "VC dimension gives a LOOSE, not TIGHT bound"?

From what I understand VC dimension is what establishes the feasibility of learning for infinite hypothesis sets, the only kind we would use in practice. But, the literature (i.e. Learning from Data)...
Stefan Radonjic's user avatar
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
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
2 votes
1 answer
173 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
1 vote
1 answer
265 views

Understanding relation between VC Symmetrization Lemma and Generalization Bounds

I am new in the field of Machine Learning so I wanted to start of by reading more about mathematics and history behind it. I am currently reading, in my opinion, a very good and descriptive paper on ...
Stefan Radonjic's user avatar
2 votes
1 answer
364 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.2k
1 vote
1 answer
448 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 ...
user avatar
1 vote
1 answer
121 views

Can feature engineering change the selection of the model according to the minimum description length?

The definition of MDL according to these slides is: The minimum description length (MDL) criteria in machine learning says that the best description of the data is given by the model which ...
user avatar
2 votes
1 answer
607 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
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
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
2 votes
1 answer
416 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
11 votes
3 answers
495 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
1 vote
1 answer
93 views

Why does the discrepancy measure involve a supremum over the hypothesis space?

I am referring specifically to the disc defined by Kuznetsov and Mohri in https://arxiv.org/pdf/1803.05814.pdf This is a kind of worst case path dependent generalization error. But what is the ...
mathtick's user avatar
  • 141
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
4 votes
2 answers
400 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