# 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.

**1**

vote

**1**answer

71 views

### Growth rate of bounded Lipschitz functions on compact finite-dimensional space

Let $\mathcal X$ be a metric space of diameter $D$ and "dimension" (e.g doubling dimension) $d$. Let $L \in [0, \infty]$ and $M \in [0, \infty)$ and consider the class $\mathcal H_{M,L}$ of $L$-...

**0**

votes

**1**answer

111 views

### Is it possible to “solve” iterative (convex/non-convex) optimization problems via learning (one-shot)?

I posted a following question in MSE, but I think it should be posted here in MO. Since I don't know how to transfer the post from MSE to MO, I have pasted the question below. Thank you in advance and ...

**1**

vote

**2**answers

151 views

### Lower bound on misclassification rate of Lipschitz functions in terms of Lipschitz constant

Important note
@MateuszKwaśnicki in the comment section has raised a fundamental issue with the current statement of the problem. I'm trying to bugfix it.
Setup
I wish to show that a Lipschitz ...

**5**

votes

**2**answers

191 views

### VC dimension, fat-shattering dimension, and other complexity measures, of a class BV functions

I wish to show that a function which is "essentially constant" (defined shortly) can't be a good classifier (machine learning). For this i need to estimate the "complexity" of such a class of ...

**1**

vote

**0**answers

45 views

### From Sudakov minoration principle to lowerbounds on Rademacher complexity

For a compact subset $S \subset \mathbb{R}^n$ (and an implicit metric $d$ on it) and $\epsilon >0$ lets define the following $2$ standard quantities,
Let ${\cal P}(\epsilon,S,d)$ be the $\epsilon-...

**1**

vote

**1**answer

89 views

### Packing number of Lipschitz functions

For some $L>0$ say ${\cal L}$ is the space of all $L-$Lipschitz functions mapping $(X,\rho) \rightarrow [0,1]$ where $(X,\rho)$ is a metric space.
For any $\alpha >0$ do we know of a ...

**3**

votes

**0**answers

85 views

### A largest lattice of a given Vapnik-Chervonekis dimension

Prove (or disprove) that a largest lattice of Vapnik-Chervonekis dimension at most $k$ which has at most $n\cdot k$ join-irreducible and $n\cdot k$ meet-irreducible elements is the distributive ...

**2**

votes

**1**answer

152 views

### Covering number of Lipschitz functions

What do we know about the covering number of $L$-Lipschitz functions mapping say, $\mathbb{R}^n \rightarrow \mathbb{R}$ for some $L >0$?
Only 2 results I have found so far are,
That the $\infty$-...

**0**

votes

**0**answers

35 views

### Are there sharper training sample bounds than the Clopper-Pearson bound?

Consider a hypothesis $h: \mathbb{R}^n \rightarrow \mathbb{R}$ and random variables $X \in \mathbb{R}^n, Y \in \mathbb{R}$.
We set $R = P(h(X) \neq Y)$ and $T = (X_i,Y_i)_{i \leq m}$ iid. test ...

**4**

votes

**1**answer

316 views

### Minimize the variance of a Boltzmann distribution

N.B.: Sorry for cross-posting from https://stats.stackexchange.com/posts/347804/edit (I realized it was the wrong venue for the question, but couldn't find an easy way to transfer the question here).
...

**3**

votes

**1**answer

78 views

### Concentration inequalities specialized for log-likelihood / log-density functions

Let $P$ be a probability measure and $f$ be some probability density function (not necessarily related to $P$). Consider the function
$$
L(X_1,\ldots,X_n)
=\frac1n\sum_{i=1}^n\log f(X_i),
\quad
X_i\...

**0**

votes

**0**answers

66 views

### About Rademacher complexity

The following two questions of mine might be related,
Q1 Are there examples of non-trivial function classes known in which some norm bound (like the $L^p$ norm) can be used to carve out a subset of ...

**0**

votes

**0**answers

31 views

### Best Optimization Algorithm: SPSA vs RL and in RL

If I understand correctly, Simultaneous Perturbation Stochastic Approximation is an optimization method whose input parameter is basically just an initial guess given that you can find obtain a "...

**37**

votes

**3**answers

2k views

### Is there research on human-oriented theorem proving?

I know there is already a research community that is working on automatic theorem proving mostly using logic (and things like Coq and ACL2). However, I came across a lecture from a fields medalist W.T....

**1**

vote

**0**answers

133 views

### Relation between pseudo-dimension and Rademacher complexity

With techniques of Dudley's entropy bound and Haussler's upper bound one can show that there exists a constant $C$ such that any class of $\{0,1\}$ indicator functions with Vapnik-Chervonenkis ...

**3**

votes

**1**answer

170 views

### Is this generalization bound proof wrong?

This is an ICML02 paper by Garg, Har-Peled & Roth:
http://sarielhp.org/p/01/bounds/bounds.pdf
The equation after eq. (3) is the well-known symmetrization trick for $\sup_{h\in {\mathcal H}} |E(h)-...

**1**

vote

**1**answer

54 views

### Clarification on margin bound uniform w.r.t. the margin parameter

Theorem 4.5. in the book "Foundations of Machine Learning" by Mohri et al:
http://prlab.tudelft.nl/sites/default/files/Foundations_of_Machine_Learning.pdf
derives a generalization bound to hold ...

**2**

votes

**1**answer

370 views

### Rademacher complexity of composition of functions

I am looking for a bound on the empirical Rademacher complexity of the following class:
$G=\left\{x \rightarrow \frac{h^T f(x)}{\|h\|_2 \cdot \|f(x)\|_2} : h\in R^d, f()=(f_1(),\ldots,f_d()), f_j \in ...

**2**

votes

**1**answer

226 views

### Extension of Talagrand contraction lemma (on empirical Rademacher complexity)

Is the following true?
Let $(x_1,...,x_N)$ be a set of points on the unit sphere $S^{d-1}$.
Let $\ell_x: [-1,1]\rightarrow [0,1]$ be a family of Lipschitz functions indexed by $x\in S^{d-1}$, with ...

**3**

votes

**0**answers

234 views

### VC dimension of axis-parallel boxes on the torus

First the basic definitions: Let $H$ be a family of sets, and let $P$ be a set of points. Then $H$ is said to shatter $P$ if $\{ h \cap P:~h \in H\}=2^P$, that is, if every subset of $P$ can be ...

**1**

vote

**0**answers

49 views

### Approximating or calculating the mutual information of certain binary random vectors

In my studies of applied probability I have recently met the following problem on which I need help:
We consider two binary random (column) vectors $ X,Y \in \{0,1\}^d $ where the mutual ...

**1**

vote

**0**answers

53 views

### Determining when specific gradient descent converges to singular or critical points

In my research on neural networks and learning theory I have recently come across the following problem dealing with gradient descent:
We consider a given column vector $ x=[x_1,x_2,...,x_{d}]^T \...

**1**

vote

**1**answer

100 views

### VC dimension of cone-restricted linear classifiers

Let $\mathcal{C}$ be a pointed, salient cone in $\mathbb{R}^d$. We may also assume that $\mathcal{C}$ is full-dimensional. Consider the set of binary classifiers $$\mathcal{H} = \{\boldsymbol{x}\...

**8**

votes

**0**answers

304 views

### The function space defined by deep neural nets

Given a deep net graph and the activation functions on the hidden vertices do we have a description of the function space spanned by it? (even if for some specific architectures and activation ...

**1**

vote

**1**answer

211 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

126 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

110 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

142 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

43 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(\...

**11**

votes

**3**answers

1k 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

265 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

133 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

214 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

245 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)$ ...

**1**

vote

**1**answer

115 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

179 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 ...

**14**

votes

**1**answer

1k views

### Table with the most seated customers in Chinese restaurant process

Suppose we have some initial configuration of people seated at some tables. We start taking new customers and seat them following Chinese restaurant process. Is there some known work on finding the ...

**-1**

votes

**1**answer

1k 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

463 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

316 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

196 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

295 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

98 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

352 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

881 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

2k 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

808 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 ...

**10**

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

**2**

votes

**5**answers

4k 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

7k 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)...