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

The tag has no usage guidance.

14
votes
1answer
774 views

Is there any paper which summarizes the mathematical foundation of deep learning?

Is there any paper which summarizes the mathematical foundation of deep learning? Now, I am studying about the mathematical background of deep learning. However, unfortunately I cannot know to what ...
2
votes
1answer
89 views

Why the VC dimension of triangles in 2D space is not greater than 7?

I understand that there are sets of 7 points on a circle that can be fully shattered using triangles.But, it is not clear to me why it cannot shatter 8 points. Is there any intuitive way of arriving ...
1
vote
0answers
37 views

Kernel ridge regression with matrix-vector data set $S := \{ X_i, y_i \}_{i=1}^{N}$?

Background: For Kernel ridge regression, I have normally come across the data-set given in vector and scalar form, i.e., $\overline{S}:= \{x_i, \overline{y}_i \}$, where $x_i \in M_{n,1}(\mathbb{R})$ ...
3
votes
1answer
141 views

Why does the assumption $|U_t| \le \frac1{p_{\min}}$ work in this paper?

I am reading a 2009 paper right now "Importance Weighted Active Learning" and on page 5, there is a theorem that uses the inequality $|U_t| \leq \frac{1}{p_{\min}}$. I am not sure how the paper found ...
4
votes
1answer
76 views

Clustering distance

Is there a good notion of distance between partitions of a (fixed, finite) set? The context is this: suppose I have a clustering algorithm, which clusters points using some method or other. Now, I ...
0
votes
0answers
47 views

Using mollifiers (or some other idea) to solve constrained minimax problem

Sorry in advance if this sounds like a more SE question. Consider a continuously parametrized family of $L$-Lipschitz continuous $f_\theta: X \rightarrow \mathbb R_+$ on a metric space $X=(X,d)$. Let ...
3
votes
1answer
53 views

How to value the extent of separation or mixing of point sets in plane?

As the image presented below, the reddish point set is totally separated from the blueish one and the greenish one, while the blueish point set is quite mixed with the greenish one. A number of ...
5
votes
1answer
217 views

Approximation of Wasserstein distance between $p_\theta$ and $p_{\theta + d\theta}$

Given a parametric family of distributions $\{p_\theta\mid\theta \in \Theta\}$, one can show that under some regularity conditions, the following approximation is valid $$\operatorname{KL}(p_\theta\...
1
vote
1answer
111 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
170 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
0answers
34 views

Theoretical justification of time-series forecasting using Takens' embedding

This is a cross-posting where I couldn't get an answer. In the meantime I have tried to improve the original logic: As in Takens original paper about his embedding theorem, consider a compact $m$-...
13
votes
0answers
176 views

Profiles of very high dimensional functions

This question comes from trying to understand the recent success of deep neural nets. Neural networks just (crudely speaking) create a very complicated function of very many variables, and then ...
1
vote
1answer
85 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 ...
11
votes
2answers
456 views

Reference Request: Theoretical Mixing Times Research in Machine Learning / Artificial Intelligence (AI)

I'm doing a PhD in probability theory, focusing mostly on mixing times. It's a pure maths PhD, considering precise models and showing rigorous mixing results. I'm also interested in stuff like machine ...
6
votes
1answer
515 views

graph signal processing

I have read this article https://arxiv.org/abs/1307.5708 about vertix-frequency analysis on graph. David IShuman in this article claims that,"we generalize one of the most important signal ...
2
votes
1answer
134 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 ...
-2
votes
1answer
50 views

Find a columns of matrix $A$ which form a basis of columns space of matrix $A$ [closed]

We have a matrix $A$ whose rows are data records and whose columns are features. We would like to omit useless features such as zero or constant columns, duplicate columns, columns that are equal to ...
1
vote
0answers
156 views

What intuitive concepts in pure math can be used to understand Big data? [closed]

I am not a mathematician but I need mathematicians' general knowledge and that is why I chose this community to ask my question from. As a student/researcher in Data Mining, with background in Pure ...
1
vote
0answers
153 views

On proof of Sauer's lemma

Let $X$ be a (possibly infinite) set. We consider a subset $H$ of the set $\{0,1\}^X$ of functions $X\to\{0,1\}$. Given a finite subset $B\subset X$, we denote by $H_B$ the set of restrictions to $B$ ...
0
votes
0answers
30 views

In paper “Neighbourhood Components Analysis”, how to determine the optimal number of neighbours (K)?

Recently, I am reading the paper "Neighbourhood Components Analysis". At the last paragraph on the second page of the paper, "Notice that by learning the overall scale of A as well as the relative ...
0
votes
0answers
61 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
28 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 "...
0
votes
0answers
43 views

proof in contextual bandits paper on epoch greedy algorithm

I'm reading the following paper on the epoch greedy algorithm for the contextual bandits problem. I have two questions http://hunch.net/~jl/projects/interactive/sidebandits/bandit.pdf I'm unsure ...
5
votes
2answers
302 views

Derivatives of Gaussian processes

A Gaussian process $X$ on Euclidean space $\mathbb R^d$ has a radial basis kernel if for any $u,w\in\mathbb R^d$, we have $$ \mathrm{Cov}(X_u, X_w) = \sigma^2 \exp\left ( -\frac{\left\lVert u-w \right ...
0
votes
1answer
41 views

General results regarding linear separability?

I'm reading up on the theory behind support vector machines and would like a good reference with some general results about linear separability. Specifically, questions like below: Given two ...
3
votes
3answers
255 views

Automatic vs numerical differentiation of a function known from samples

Suppose I have $n$ samples $(x_i, f(x_i))_{i=1}^n$ from an unknown function $f$. I need to approximate (estimate) the derivative $f'(x^*)$ at some new test point $x^*$, that is not necessarily one of ...
1
vote
0answers
28 views

Latent Dirichlet Allocation on Contrived Data

I am doing a project that seems like it might be susceptible to Latent Dirichlet Allocation. However, my data is highly contrived (both in test cases and use cases) and my "words" don't come close to ...
0
votes
1answer
60 views

Learning a Gaussian from noisy observations

Is it possible to learn a distribution over the parameters ($K=\Sigma^{-1}$ and $\mu$) of a Gaussian from noisy measurements of $X$? (Starting with some appropriate prior over the parameters) I know ...
3
votes
1answer
74 views

What is the most appropriate ML technology or math tool for classifying/recognizing 2D scatter plot shapes? [closed]

I would like to be able to automatically classify an input scatter plot into a limited, predefined set of 2-D scatter plots (see attached image), such as a Circle, a Cross, a Straight Line and a Curvy ...