Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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
1answer
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
1answer
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
2answers
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
2answers
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
3answers
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
3answers
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
2answers
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
1answer
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
3answers
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
0answers
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
0answers
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
2answers
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
1answer
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
0answers
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
4answers
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
5answers
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
3answers
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)...