# Questions tagged [learning-theory]

This tag is used for questions that are related with following branches: Statistical learning theory, Machine learning, Vapnik–Chervonenkis theory (VC theory) and all other branches that are studied and applied in the area of learning theory that involves various kinds of mathematics.

102 questions
Filter by
Sorted by
Tagged with
56 views

### Probability of $P(\sum_{i=1}^n X_i \le \sum_{i=1}^n a_i)$ given that $P(X_i \le a_i) \ge p_i$

I encounter this problem where I am given a sequence of independent continuous random variables $\{X_i\}_{i=1}^n$ and constants $\{a_i\}_{i=1}^n$ and I know that $P(X_i\le a_i)\ge p_i$ where $p_i$ are ...
1 vote
53 views

### VC-dimension of intersection

Let $A$ and $B$ be sets of real-valued functions on $X$. Are there any reasonably tight bounds on the VC-dimension of $A\cap B$ in terms of the VC-dimensions of $A$ and $B$?
• 5,261
70 views

### How to naturally define an output space with certain properties

Consider the following regression problem $v=A(u) + \varepsilon$ for some operator $A:\mathcal{U} \rightarrow \mathcal{V}$ and some function spaces $\mathcal{U},\mathcal{V}$, mapping from $\mathcal{X}$...
64 views

### VC dimension of full-dimensional closed polyhedral cone in $\mathbb R^d$

Consider a fixed set of vectors $\{x_i\}_{i\in[n]}$ in $\mathbb R^d$ and closed polyhedral cone $C = \{w \in \mathbb R^d : w^\top x_i \geq 0, \forall i \in [n]\}$ with full dimension i.e. $C$ contains ...
338 views

### Minimax optimal multiple hypothesis test

Let us consider the following two-player game between Chooser and Guesser. There is a finite set $\Omega$ and $k$ probability distributions on $\Omega$, denoted by $\mathcal{P} =\{P_1,\ldots,P_k\}$. ...
• 6,415
103 views

• 6,843
93 views

• 422
1 vote
130 views

### Distribution-free learning vs distribution-dependent learning

I came across some papers studying the problem of distribution-free learning, and I am interested in knowing the exact definition of distribution-free learning. I have searched some literature: In ...
• 11
120 views

### Progress on "Un-Alching" ML?

So, a couple of years ago I watched both Ali Rahimi's NIPS speech "Machine Learning is Alchemy", (where he talks about how the field lacks a solid, overarching, theoretical foundation) and ...
• 41
1 vote
170 views

• 6,843
163 views

### Convergence rates for kernel empirical risk minimization, i.e empirical risk minimization (ERM) with kernel density estimation (KDE)

Let $\Theta$ be an open subset of some $\mathbb R^m$ and let $P$ be a probability distribution on $\mathbb R^d$ with density $f$ in a Sobolev space $W_p^s(\mathbb R^d)$, i.e all derivatives of $f$ ...
• 6,843
338 views

### Bounds on the number of samples needed to learn a real valued function class

Let us see Theorem 6.8 in this book, https://www.cs.huji.ac.il/w~shais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf It gives us a lowerbound (and also an ...
• 555
1 vote
57 views

• 11
829 views

### Abstract mathematical concepts/tools appeared in machine learning research

I am interested in knowing about abstract mathematical concepts, tools or methods that have come up in theoretical machine learning. By "abstract" I mean something that is not immediately related to ...
288 views

### Statistical divergence

Does anyone know about a statistical divergence of this type? $$\text{D}(P||Q) = \frac{1}{2} \left[\text{KL}(M||P) + \text{KL}(M||Q)\right]$$ where $M = \frac{1}{2} [P+Q]$....
• 245
670 views

### Why we use Rademacher complexity for generalization error when we can have a trained function?

Let $G$ be a family of functions mapping from $Z$ to $[a, b]$ and $S=\left(z_{1}, \ldots, z_{m}\right)$ a fixed sample of size $m$ with elements in $Z$ . Then, the empirical Rademacher complexity of \$...
• 53