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.
99
questions
1
vote
2
answers
303
views
Use covering number to get uniform concentration from pointwise concentration
Let $\Theta$ be a subset of a metric space. Suppose $(X_\theta)_{\theta \in \Theta}$ is a random process on $\Theta$ which is $L$-Lipschitz and with the property that there exists constants $A, B>0$...
1
vote
1
answer
377
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$-...
1
vote
2
answers
336
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 ...
2
votes
2
answers
506
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 ...
8
votes
2
answers
1k
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 ...
3
votes
0
answers
300
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-...
2
votes
1
answer
1k
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
102
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 ...
6
votes
1
answer
3k
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$-...
4
votes
1
answer
380
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
258
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\...
38
votes
4
answers
3k
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....
2
votes
0
answers
413
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
208
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
82
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
1k
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
609
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 ...
5
votes
1
answer
941
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
87
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
72
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
231
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
682
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
357
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
145
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
310
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
208
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 ...
13
votes
3
answers
2k
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
422
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
187
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
284
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
325
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)$ ...
2
votes
1
answer
303
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
333
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 ...
15
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 ...
0
votes
1
answer
2k
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 ...
6
votes
1
answer
521
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
360
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
365
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
309
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
123
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
541
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
2k
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
2
answers
3k
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
858
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
3k
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
5k
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
13k
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
100
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
400
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 ...