# Questions tagged [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).

18 questions
Filter by
Sorted by
Tagged with
16 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 ...
14 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 ...
27 views

23 views

### Understanding 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 ...
35 views

### Query on another perspective on Deep Learning

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 ...
47 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 ...
143 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 ...