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
0
votes
0answers
28 views

Analytic formula for minimum possible error for functions in RKHS ball, on a simple classificaiton problem

Let $X=\mathcal S_{d-1}$ be the unit-sphere in $\mathbb R^d$, and let $K:X \times X \to \mathbb R^d$ be a Mercer kernel (e.g the Laplace kernel). Let $\mathcal H_K$ be the induced RKHS, and for $R \ge ...
3
votes
0answers
102 views

Analytic formula for the eigenvalues of kernel integral operator induced by Laplace kernel $K(x,x') = e^{-c\|x-x'\|}$ on unit-sphere in $\mathbb R^d$

Let $d \ge 2$ be an integer and let $X=\mathcal S_{d-1}$ the unit-sphere in $\mathbb R^d$. Let $\tau_d$ be the uniform distribution on $X$. Define a function $K:X \times X \to \mathbb R$ by $K(x,y) := ...
1
vote
0answers
154 views

Variance-based localized Rademacher complexity for RKHS unit-ball

Let $\mathscr X$ be a compact subset of $\mathbb R^d$ (e.g the unit-sphere). Let $K: \mathscr X \times \mathscr X \to \mathbb R$ be a positive kernel function and let $\mathscr H_K$ be the induced ...
0
votes
0answers
62 views

Lower-bound on expected value of norm of transformation of random vector with iid Rademacher coordinates

Let $n$ be a large positive integer. Let $A$ be a positive-definite matrix such with eigenvalues $\lambda_1 \ge \lambda_2 \ge \ldots \ge \lambda_n$ such that $\lambda_n = o(1) \to 0$ and $\lambda_i=\...
1
vote
0answers
81 views

Concentration for $\sum_{i=1}^n y_i \psi(x_i^\top u)$, for $y_1,\ldots,y_n \sim \{\pm 1\}$ and $x_1,\ldots,x_n$ uniform iid on hypersphere

Let $y_1,\ldots,y_n$ be drawn iid uniformly from $\{\pm 1\}$ and let $x_1,\ldots,x_n$ be drawn iid uniformly from the unit-sphere $(d-1)$-dimensional sphere $\mathbb S_{d-1}$, and independently from ...
3
votes
0answers
157 views

Games and the right mathematical framework for GANs

Generative Adversarial Networks were introduced in http://papers.nips.cc/paper/5423-generative-adversarial-nets and has more than 20000 citations. It is an important topic within deep learning. Are ...
0
votes
0answers
30 views

Bounds on the regularized risk minimizer and risk minimizer?

Some of this is taken from a similar post here, but with modifications. In supervised machine learning, we typically take a Risk Minimization (RM) point of view when formulating a problem. So, what we ...
1
vote
0answers
30 views

Covering number after projection

In these lecture notes on Statistical Learning Theory we find the following definitions for covering numbers: Definition. Let $(\mathcal{W}, d)$ be a metric space and $\mathcal{F} \subset \mathcal{W}$...
1
vote
1answer
99 views

Finite VC dimension > the number of free parameters

I'm looking for an example of the following: A hypothesis class $\mathcal{H}$ such that $\forall h \in \mathcal{H}$, the number of free parameters of $h$ is equal to $n \in \mathbb{N}$ (where $n < ...
0
votes
1answer
244 views

How large sample $m$ is enough [closed]

I have a $D$ probability distribution over $X =R^d$, i have two samples $s_1$ and $s_2$ from $D$, each having size $m_1$, $m_2$, a unit ball centered at origin $B(0)$, defined by $B(0)=\{x \in R^2: \|...
1
vote
0answers
29 views

Fast rates in ERM: Extreme case of low-noise assumption implies non-differentiability

Some context: I am going through some literature on empirical risk minimization for bipartite ranking [1] that shows how certain "low-noise" conditions lead to fast rates of convergence of ...
8
votes
4answers
2k views

How to learn a continuous function?

Let $\Omega \subset \mathbb{R}^m$ be an open subset bounded with a smooth boundary. Problem : Given any bounded continuous function $f:\Omega\to\mathbb{R}$, can we learn it to a given accuracy $\...
1
vote
1answer
187 views

Upper bounding VC dimension of an indicator function class

I would like to upper bound the VC dimension of the function class $ F$ defined as follows: $$ F := \left\{ (x,t) \mapsto \mathbb{1} \left( c_Q\min_{q \in Q} {\|x-q \|}_1 - t > 0 \right) \; | \; Q ...
5
votes
1answer
291 views

Abstract mathematical concepts/tools appeared in machine learning research

I am interested in knowing about abstract mathematical concepts, tools or methods that have come up in theoretical machine learning. By "abstract" I mean something that is not immediately related to ...
0
votes
2answers
198 views

Statistical divergence

Does anyone know about a statistical divergence of this type? \begin{equation} \text{D}(P||Q) = \frac{1}{2} \left[\text{KL}(M||P) + \text{KL}(M||Q)\right] \end{equation} where $M = \frac{1}{2} [P+Q]$....
1
vote
1answer
192 views

Why we use Rademacher complexity for generalization error when we can have a trained function?

Let $G$ be a family of functions mapping from $Z$ to $[a, b]$ and $S=\left(z_{1}, \ldots, z_{m}\right)$ a fixed sample of size $m$ with elements in $Z$ . Then, the empirical Rademacher complexity of $...
20
votes
1answer
2k views

Relation between information geometry and geometric deep learning

Disclaimer: This is a cross-post from a very similar question on math.SE. I allowed myself to post it here after reading this meta post about cross-posting between mathoverflow and math.SE, I did ...
6
votes
0answers
70 views

Functional Equation of Zeta Function on Statistical Model

I've been studying [1] because I was interested in his ideas on the zeta function. I'll define it here (c.f. p. 31): The Kullback-Leibler distance is defined as $$ K(w)=\int q(x)f(x, w)dx\quad f(x,w)...
0
votes
0answers
71 views

Function classes with high Rademacher complexity

My question is two fold, Is there any general understanding of what makes a function class have high Rademacher complexity? (Sudakov minoration would say that one sufficient condition for a class of ...
2
votes
0answers
188 views

Shattering with sinusoids

Let $d \geq 2$ and $K$ some positive integer. Consider distinct points $\theta_1, \ldots, \theta_K\in \mathbb{T}^d$ and (not necessarily distinct) $z_1, \ldots, z_K \in \{-1,1\}$ such that $\sum\...
0
votes
2answers
183 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
1answer
206 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
2answers
195 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
316 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 ...
7
votes
2answers
598 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 ...
2
votes
0answers
157 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
477 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
95 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 ...
4
votes
1answer
1k 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
1answer
346 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
141 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
4answers
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....
2
votes
0answers
275 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
189 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
66 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
804 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
421 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
1answer
557 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
59 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
62 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
162 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
568 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
270 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
144 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
192 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
167 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 ...
12
votes
3answers
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
0answers
395 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
171 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
242 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 ...