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.

Filter by
Sorted by
Tagged with
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$...
dohmatob's user avatar
  • 6,716
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$-...
dohmatob's user avatar
  • 6,716
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 ...
user550103's user avatar
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 ...
dohmatob's user avatar
  • 6,716
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 ...
dohmatob's user avatar
  • 6,716
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-...
gradstudent's user avatar
  • 2,136
2 votes
1 answer
997 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 ...
gradstudent's user avatar
  • 2,136
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 ...
Lviv Scottish Book's user avatar
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$-...
gradstudent's user avatar
  • 2,136
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). ...
dohmatob's user avatar
  • 6,716
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\...
JohnA's user avatar
  • 680
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....
Charlie Parker's user avatar
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 ...
axk's user avatar
  • 517
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)-...
axk's user avatar
  • 517
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 ...
axk's user avatar
  • 517
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 ...
axk's user avatar
  • 517
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 ...
axk's user avatar
  • 517
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 ...
Kurisuto Asutora's user avatar
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 ...
groupoid's user avatar
  • 580
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 \...
groupoid's user avatar
  • 580
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}\...
S.B.'s user avatar
  • 215
8 votes
0 answers
681 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 ...
gradstudent's user avatar
  • 2,136
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 ...
user avatar
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 \...
user40780's user avatar
  • 867
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 ...
Student's user avatar
  • 555
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 ...
chausies's user avatar
  • 131
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 ...
Xingdong Zuo's user avatar
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 ...
Peter Schmidt-Nielsen's user avatar
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 \...
guigux's user avatar
  • 607
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 ...
Kurisuto Asutora's user avatar
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)$ ...
Domenico Zambella's user avatar
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 ...
S.Surace's user avatar
  • 1,675
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 ...
user3429697's user avatar
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 ...
Stakhanov's user avatar
  • 151
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 ...
user56238's user avatar
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 ...
Mathias's user avatar
  • 303
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 ...
anni's user avatar
  • 11
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?
Martin Henry's user avatar
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 ...
Richard's user avatar
  • 11
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 ...
Arun's user avatar
  • 11
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.
Arun's user avatar
  • 11
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 ...
Cain's user avatar
  • 393
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 ...
Arthur B's user avatar
  • 1,882
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 ...
WhitAngl's user avatar
  • 481
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 ...
Chirag Lakhani's user avatar
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 ...
Yassin Ezbakhe's user avatar
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)...
mrehayden's user avatar
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 ...
sup's user avatar
  • 23
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 ...
benc's user avatar
  • 201

1
2