The learning-theory tag has no usage guidance.

**0**

votes

**1**answer

35 views

### What is the shatter coefficient / VC - dimension of some hypothesis set?

Let $H:=\{h:\mathbb{N}_0^n \rightarrow \{0,1\}| h(x_1,\cdots,x_n) = \mathbb{1}_0(\sum_{i\in I}{x_i}-\sum_{j \notin I}{x_j}) \text{ for some } I \subset \{1,\cdots,n\}\}$
where $\mathbb{1}$ is the ...

**0**

votes

**0**answers

59 views

### choosing regularization constant in compressive sensing

Given a compressive sensing formulation,
$$\left\| {Ax - b} \right\|_2^2 + \mu {\left\| x \right\|_1}$$
And given curves
(a) $\left\| {Ax - b} \right\|_2^2$ plotted against $\log \left( \mu \...

**0**

votes

**1**answer

53 views

### Request for references about computing or estimating Rademacher complexity

Is Rademacher complexity defined for any space of functions?
Or are there restrictions on the function space over which this can be defined?
For example is the Rademacher complexity defined or has ...

**3**

votes

**1**answer

108 views

### Learn a distribution from distributions on samples

There's many good ways to learn a distribution $p_X$ of an r.v. $X$ over $k$ symbols given many i.i.d. samples $X_1,\ldots, X_n$. The simplest is to use the sample relative frequencies $\hat{f}_X$ as ...

**0**

votes

**0**answers

37 views

### Minimize a function to learn a mapping

I have two questions.
I want to learn a mapping $M$ that minimizes the right-hand side of the following equation:
$E =\frac{1}{N} \sum\limits_{i=1}^N \bigg(\sum\limits_{j=1}^K \alpha_i - \big(\...

**7**

votes

**3**answers

503 views

### Is there research on Machine Learning techniques to discover conjectures (theorems) in a wide range of mathematics beyond mathematical logic?

Although there already exists active research area, so-called, automated theorem proving, mostly work on logic and elementary geometry.
Rather than only logic and elementary geometry, are there ...

**7**

votes

**0**answers

147 views

### Does the Mandelbrot set have infinite VC dimension?

Define a binary classifier for points in the complex plane, whose parameter $\theta$ is an isometry of $\mathbb{C}$, and which classifies $z \in \mathbb{C}$ based on whether or not $\theta(z)$ is in ...

**2**

votes

**0**answers

68 views

### Maximum-likelihood estimation for univariate responses from multivariate data

I am new in the field of machine learning, so I hope I will be able to formulate my question in a clear way...
I have some data represented by vectors $\mathbf{x}_1,\mathbf{x}_2,\ldots,\mathbf{x}_n \...

**7**

votes

**1**answer

175 views

### “Separated” version of Sauer's lemma on VC classes

Sauer's lemma, a well-known result in computational complexity theory, learning theory, and combinatorics, states the following:
Let $\Phi$ be a collection of subsets of a set $U$, and assume that ...

**2**

votes

**1**answer

177 views

### Epsilon-approximations of set systems with finite VC-dimension

ECorollary 6.9 in A Guide to NIP theories by Pierre Simon proves the following
Theorem. For every positive integer $k$ and every positive real $\varepsilon$ there is an integer $n=n(k,\epsilon)$ ...

**0**

votes

**0**answers

53 views

### Recursive parameter estimation for partially observed Ito SDEs

I'm trying to get my head around online (recursive) maximum-likelihood parameter estimation in the language of stochastic processes and in the context of stochastic filtering, i.e. where we have a ...

**5**

votes

**1**answer

130 views

### assumptions on local rademacher complexities

A lot of the work on Local Rademacher complexities of Koltchinskii, and Bartlett for fast rates of convergence is based on Bousquet's version of Talagrand's inequality [1] (Theorem 2.11). However the ...

**-2**

votes

**1**answer

600 views

### AI / Machine Learning related to high/modern/front mathematics [closed]

I major math and cs. and i'm interested in ai/machine learning/data mining.
so i want to know what math subjects are used in frontier of these technology.
especially, high mathematical tool, like ...

**5**

votes

**1**answer

427 views

### Is there a mistake in Vapnik's “Basic Lemma”?

I have a concern about the "Basic Lemma" which Valdimir Vapnik states and proves in his 1998 book Statistical Learning Theory (ch. 14.3, pp. 574–76): It seems like a certain coefficient should have ...

**1**

vote

**2**answers

278 views

### A machine learning application question

I am familiar with basic probabilities, random processes but not so much of machine learning methods. This is the problem I am trying to solve.
I want to predict the nature of user activity on a ...

**0**

votes

**1**answer

142 views

### What is the Bahadur-Anderson Algorithm?

What is the Bahadur-Anderson Algorithm, and which book could one read to learn it?

**1**

vote

**3**answers

287 views

### A sampling and learning question

Suppose there is an oracle that returns a number $b \in \mathbb{Z}_{n}$ whenever I press the button.
We have $b = a + e$, where $a \in \mathbb{Z}_n$ is a fixed number and $e$ is sampled according to ...

**1**

vote

**0**answers

76 views

### Vertex cover for hamming graphs representing sets of bounded VC dimension

Let $S$ be a set of binary vectors (in $\lbrace 0,1 \rbrace^m $) whose VC dimension is $d$. Let $H$ be the Hamming graph generated from this set where each node represents a binary vector and two ...

**0**

votes

**0**answers

241 views

### VC dimension and boolean hypercube subgraphs

Are there any well studied graph theoretic properties that are common to all subgraphs of the boolean hypercubes that have a given VC dimension d.

**3**

votes

**2**answers

563 views

### Vapnik-Chervonenkis dimension of lines in the plane

I'm having some problems with this problem concerning VC dimensions ( http://en.wikipedia.org/wiki/VC_dimension ), I hope for some helping input.
Given a set $L$ of $n$ lines in the plane, define a ...

**4**

votes

**1**answer

1k views

### Monotonicity of the hard EM algorithm.

Consider the problem where we want to find a maximum likelihood estimate of $\theta$, given $X$ and $$P_\theta(Y) = \sum_z P_\theta(Y,x)$$ where $x$ is a latent variable.
I know that the soft EM ...

**2**

votes

**0**answers

720 views

### Classical Multidimensional Scaling

Hi,
I am doing an MDS with a distance matrix coming from geodesic distances between points X on a 3d mesh (ie., not euclidean distances), and try to find points Y in euclidean space which best ...

**8**

votes

**4**answers

2k views

### Reference request for manifold learning

I am interested in learning about manifold learning (no pun intended) and would like to know of some references that discuss the subject from a more geometric perspective. By manifold learning I mean ...

**1**

vote

**5**answers

3k views

### Nodes clusters with a distance matrix

Hi,
I have a (symmetric) matrix $M$ that represents the distance between each pair of nodes. For example,
A B C D E F G H I J K L
A 0 20 20 20 40 60 60 60 100 120 ...

**2**

votes

**3**answers

6k views

### The Polynomial Kernel

I Have seen two versions of the Polynomial Kernel during my time learning Kernel Methods for things such as regression analysis.
1) $\kappa_d(x,y) = (x \cdot y)^d$
2) $\kappa_d(x,y) = (x \cdot y + 1)...

**2**

votes

**1**answer

93 views

### Ranking sources at variable(random) frequencies

Hi,
I have this math modeling problem that I need help with. If I have 3 data sources, each being updated at different frequencies, what would be the best way to rank them so the less frequent ...

**10**

votes

**3**answers

335 views

### disconnected or poorly connected graphs in sport ratings systems

I've briefly read about rating systems that provide rankings to players based only on their performance wrt other players, in the context of chess. (for example, elo). When there is a lot of ...