Questions tagged [machine-learning]
The machine-learning tag has no usage guidance.
184
questions
0
votes
0
answers
99
views
Relation between test and train error with gradient descent iterates
My question is about establishing an inequality between population error and expected training error (i.e, expected training error < population error) for a model trained with gradient descent on a ...
1
vote
1
answer
1k
views
References for "second order" random walk on graphs (used in "node2vec" paper)?
The "word2vec" family of methods provided a great breakthrough in natural language processing.
The methods assign to each word a vector in $R^{n}$, such that the "similar" words ...
5
votes
0
answers
204
views
Distance of two points in Grassmannian using Plücker coordinate
Let $G(q,D)$ be the Grassmannian of $q$-dimensional vector spaces in $\mathbb{R}^D$, where $q \le D$ are positive integers. In the paper, a distance between two points of $G(q,D)$ are defined as ...
8
votes
4
answers
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 $\...
5
votes
1
answer
197
views
Hermite polynomial after rotation
When we consider the $n$-dimensional standard normal distribution, the orthogonal basis is $\{H_S(x)\}_{S}$ where $H_S(x) = \prod_{k=1}^n H_{s_k}(x_k)$. Here $H_*(x)$ is the normalized probabilist's ...
1
vote
1
answer
531
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 ...
52
votes
5
answers
8k
views
Why do bees create hexagonal cells ? (Mathematical reasons)
Question 0 Are there any mathematical phenomena which are related to the form of honeycomb cells?
Question 1 Maybe hexagonal lattices satisfy certain optimality condition(s) which are related to it? ...
7
votes
1
answer
397
views
Does the plane clustered to minimize sum distances^2 to clusters centers ( inertia / "K-means") produce hexagonal clusters / hexagonal lattice?
"K-means" is the most simple and famous clustering algorithm, which has numerous applications.
For a given as an input number of clusters it segments set of points in R^n to that given number of ...
2
votes
1
answer
206
views
Uniform Lipschitz function approximation by shallow neural networks
Fix $d\in \mathbb{N}$. Let $F_1$ be the set of all 1-Lipschitz functions mapping $[0, 1]^d$ to $\mathbb{R}$.
For $\varphi: \mathbb{R} \rightarrow \mathbb{R}$ and $m \in \mathbb{N}$, let $N_\varphi^m$ ...
0
votes
1
answer
104
views
Independence in a sequential problem with observations getting added to buckets
Consider a sequence of random observations $(O(t))_{t\geq 1}$, with $O(t)=(D(t),J(t),Y(t))$. Denote $\mathcal{F}(t) := \sigma(O(1),\ldots,O(t))$, the filtration induced by the first $t$ observations.
...
7
votes
1
answer
494
views
Books to develop a unified view of statistics and information theory?
I hope to understand the connection between statistics and information theory in a deep philosophical sense.
I suppose the best place to start would be David MacKay's Information Theory, Inference, ...
11
votes
1
answer
674
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 ...
2
votes
0
answers
195
views
Inequality on the Kullback-Leibler divergence
Let us define the arithmetic, geometric, and harmonic means of $x,y \in \mathbb{R}$ weighted by $\alpha =(\alpha_x,\alpha_y) \in [0,1]$, respectively as
\begin{equation}
a_\alpha(x,y) = \frac{\...
0
votes
2
answers
277
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]$....
2
votes
0
answers
486
views
Comparison of concentrations of different $L^p$-norms of (sub) Gaussian distributions
It's well-known that the Euclidean $2$-norm of subgaussian random vectors concentrates in high dimensions, e.g. when $X \sim \mathcal{N}(0,I_n),$ (or in general $X$ is subgaussian with independent co-...
0
votes
2
answers
172
views
Help with a definition of a two-person game in a referenced paper
In the paper "Finding Mixed Nash Equilibria of Generative Adversarial Networks" the authors write in equation (1) on page 2:
Consider the classical formulation of a two-player game with
finitely ...
1
vote
0
answers
44
views
What is the number of iterations needed for the message passing algorithm to converge when applied to an acyclic factor graph?
I understand that the message passing algorithm (Belief Propagation algorithm), when applied to a factor graph consists in an exchange in messages between the factor nodes and the variable nodes, ...
14
votes
6
answers
3k
views
Mathematical physics without partial derivatives
Remark: All the answers so far have been very insightful and on point but after receiving public and private feedback from other mathematicians on the MathOverflow I decided to clarify a few notions ...
2
votes
0
answers
86
views
Variational forms of non-convex functions
I am trying to understand what kind of variational forms exist for non-convex functions. Alternatively, are there conjugate forms which attain strong duality? For a non-convex function $f$, I am ...
1
vote
0
answers
50
views
sequential learning reference request [closed]
I would like to find a book for master math student about the following topics.
I don't know the field and I don't want to be lost in details so if it could be an straight forward please.
I'm a ...
8
votes
0
answers
118
views
Positive definite kernels on categories
I'm wondering if there is any work on studying positive definite kernels on (the objects of a) category. By this I mean for a category $\mathcal{C}$, find a function
$$
K: Ob\mathcal{C} \times Ob\...
16
votes
2
answers
1k
views
Physical interpretation of the Manifold Hypothesis
Motivation:
Most dimensionality reduction algorithms assume that the input data are sampled from a manifold $\mathcal{M}$ whose intrinsic dimension $d$ is much smaller than the ambient dimension $D$. ...
0
votes
0
answers
425
views
Artificial intelligence simulating mathematicians (what a distopia!)
This is kind of soft and naive question, so feel free to shame on me :)
I start from the fact that, in my opinion, what humans are interested in about mathematics are things that we find deep and ...
36
votes
8
answers
17k
views
How useful is differential geometry and topology to deep learning?
After seeing this article https://www.quantamagazine.org/an-idea-from-physics-helps-ai-see-in-higher-dimensions-20200109/ I wanted to ask myself how useful of an endeavor would it be if one goes ...
16
votes
1
answer
828
views
Are primes linearly separable?
Let $X_1,\cdots,X_n$ be finite subsets of some set $Z$. Then the symmetric difference metric space:
$$d(X_i,X_j) = \sqrt{ |X_i|+|X_j|-2|X_i\cap X_j|}$$
can be embedded in Euclidean space. The value $|...
0
votes
1
answer
81
views
a probability density algorithm that is not sensitive to the initial condition
There are many algorithms to estimate the density of probability distributions. I am looking for one that is not sensitive to the initial condition. For instance, Expectation–maximization algorithm ...
1
vote
1
answer
159
views
Perturbation of the value of a general-sum game at a equilibirium
Consider a general-sum game with $N$ players. Let $u_i(a_1, \ldots, a_N)\colon \prod_{i=1}^N A_i \rightarrow \mathbb{R} $ be the payoff of the player $i\in \{ 1, \ldots, N \}$ when each player takes ...
0
votes
1
answer
454
views
Optimal solution to cross entropy loss in the continuous case
This could be a simple question but I don't have a satisfying answer.
Setup. Suppose that we have $K$ different classes, and consider cross entropy loss which maps a probability vector in the ...
2
votes
0
answers
193
views
Extension of universal approximation theorem
Let $I_d:=[0,1]^d$ with $d\ge 2$. Define $C(I_d):=\{F: I_d\to\mathbb R \mbox{ is continuous}\}$ and
$$N(I_d):=\{F\in C(I_d): F(x)=\sum_{k=1}^n f_k(v_k\cdot x), \mbox{ where } n\ge 1 \mbox{ and } f_1,\...
1
vote
1
answer
187
views
What subjects of Fourier analysis have had more effect on machine learning? [closed]
What is the salient uses of Fourier analysis in machine learning? What subjects of Fourier analysis have had more effect on machine learning?
Please mention the references.
3
votes
1
answer
313
views
Statistical model vs. statistical learning theory
I am interested in the relation between a statistical model $(\Omega, \mathcal{F}, (\mathbb{P}^\theta : \theta\in\Theta))$,
where the hypotheses are "$\mathbb{P}^\theta$ is a good approximation of the ...
2
votes
1
answer
617
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 $...
23
votes
1
answer
4k
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
...
1
vote
0
answers
187
views
Solution to a Strongly Convex Non-smooth Minimization Problem involving an L1 Norm
Let $X \in \mathbb{R}^{n \times d}, w \in \mathbb{R}^d, y \in \{\pm 1\}^{n}, \alpha \in [0,1], \lambda \in \mathbb{R}$. I have an expression that looks as follows
$\frac{1}{2}\|Xw -y \|_{2}^2 + \...
1
vote
0
answers
99
views
Plethora of variant neural networks?
Since a decade ago when new life was breathed in to neural networks in the form of deep learning a plethora of different architectures have come about. Is there a reference that gives compendium of ...
1
vote
0
answers
69
views
A mathematical area capable of describing nonstationary game-like problem [closed]
Here is my definition of the problem that I am trying to model:
Let's have two agents and an environment. Each agent can do two types of actions. They are either supporting the environment or don't. ...
3
votes
1
answer
1k
views
How to inference the dual form of perceptron?
The model of perceptron is a linear binary classifier, which is $f(x)=\mathbb{sign}(w^Tx+b)$. $x$ is the datapoint as $w$ as well as $b$ are the parameters.
The cost function of Primal Perceptron is $...
1
vote
1
answer
191
views
Can we order random variables in a measurable way in a general setup?
Let
$(\Omega,\mathcal A,\operatorname P)$ be a probability space
$(E,\mathcal E)$ be a measurable space
$n\in\mathbb N$
$X_1,\ldots,X_n$ be $(E,\mathcal E)$-valued random variables on $(\Omega,\...
52
votes
1
answer
5k
views
Mathematics of imaging the black hole
The first ever black hole was "pictured" recently, per an announcement made on 10th April, 2019. See for example: https://www.bbc.com/news/science-environment-47873592 .
It has been claimed that ...
5
votes
1
answer
240
views
Generating function for lattice paths making aribitrary (i,j)-up-right move in one step and fitting rectangular (m,n)?
There is the following beautiful formula (see Qiaochu Yuan excellent blog):
$$ \sum_{\lambda \in Young~diagrams~fitting~rectangle~m~n} q^{Box~count(="area~under~the~curve")~of~\lambda} = \binom{n+m}{...
1
vote
0
answers
148
views
Clarification about the ϵ -net argument
I have been reading the paper Do GANs learn the distribution? Some theory and empirics.
In Corollary D.1, they reference the paper Generalization and Equilibrium in Generative Adversarial Nets which ...
1
vote
1
answer
164
views
Error metric for joint estimation of mean and variance
Background:
Let $\mu:\mathbb{R}^n\to\mathbb{R}$ and $\sigma:\mathbb{R}^n\to\mathbb{R}_+$ be two unknown functions, and consider a stochastic model of the form
$$
\mathbb{E}[Y\mid\mathbf{x}] = \mu(\...
5
votes
0
answers
187
views
Algebraic/relational structures produced using evolutionary/machine learning algorithms?
Are there examples of algebraic structures which have been constructed using evolutionary algorithms and possibly machine learning algorithms? I am looking for algebraic structures like lattices ...
3
votes
0
answers
435
views
Simple (?) question on inner product in reproducing kernel Hilbert space
I'm following the gentle introduction to Reproducing Kernel Hilbert Spaces From Zero to Reproducing Kernel Hilbert Spaces in Twelve Pages or Less by Hal Daumé III. I believe the author fully ...
0
votes
1
answer
219
views
Cross entropy loss is not twice differentiable?
I was reading a recent theory paper in machine learning by Kenji Kawaguchi and Leslie Pack Kaelbling
https://arxiv.org/pdf/1901.00279.pdf
and the authors seem to suggest in section 2.2 that cross-...
4
votes
5
answers
6k
views
Proof of Bellman optimality equation for finite Markov Decision Processes
This question has already been posed in Cross Validated without receiving a correct formal answer, so I reformulate it here to gain attention of mathematicians. I am referring to chapter 3 of Sutton ...
9
votes
0
answers
258
views
How sensitive are Neural Networks to weight change?
Let's consider the space of feedforward neural networks with a given structure: $L$ layers, $m$ neurones per layer, ReLu activation, input dimension $d$, output dimension $k$.
Which means I'm ...
9
votes
1
answer
2k
views
Is There an Induction-Free Proof of the 'Be The Leader' Lemma?
This lemma is used in the context of online convex optimisation. It is sometimes called the 'Be the Leader Lemma'.
Lemma:
Suppose $f_1,f_2,\ldots,f_N$ are real valued functions with the same ...
1
vote
0
answers
150
views
Hypergraph partitioning and bipartite graph partitioning
Are hypergraph partitioning, and bipartite graph partitioning related, or equivalent, given that hypergraphs can be represented as bipartite graphs?
In the first case, we want to partition the set of ...
0
votes
3
answers
239
views
Clustering on tree
I am looking for a method that would identify clusters in a tree-like structure. In the figure below you can see a very simple example where one can visually identify distinct branches with a lot of ...