Questions tagged [machine-learning]
The machine-learning tag has no usage guidance.
35 questions from the last 365 days
1
vote
0
answers
32
views
Surjectivity of MLP functions
Suppose that $\mathcal{F}(H,L)$ is a function class of all functions implemented by a multilayer perceptron with ReLU activation, width $H$ and depth $L$. Also, there is a set of all possible value ...
- 61
1
vote
0
answers
45
views
Existence of optimal entropic weights for empirical modeling
Let $\mathcal{X} = [0,1]^n$ be the input space and $\mathcal{Y} = \{1, ..., n_c\}$ be a discrete output space. Let $D = \{(x_i, y_i)\}_{i=1}^N \subset \mathcal{X} \times \mathcal{Y}$ be a training ...
- 111
1
vote
0
answers
55
views
How computationally efficient are kernel tricks? [closed]
"If we compare to non-kernel polynomial regression it is O(Tnp) where is p is dimension of polynomial while kernel polynomial is O(n^2d) + O(T*n^2) where d is original number of attributes, ...
1
vote
0
answers
45
views
Conditions on LR in Gradient Descent
In Introductory Lectures in Convex Optimization by Yurii Nesterov, Section 1.2.3 shows that gradient descent is guaranteed to converge if the step size is chosen either with a fixed step size or ...
- 51
1
vote
0
answers
100
views
PageRank in directed graphs: equivalence of iterative and eigenvalue methods
Given a directed graph $ G $ with $ n $ nodes, we can represent this graph using an adjacency matrix $ A $. The stochastic matrix $ S $ can be derived from the adjacency matrix using the following ...
- 4,058
3
votes
0
answers
120
views
Convergence of gradient descent to critical point
Does there exist a generalization of this theorem by Yurii Nesterov in Introductory Lectures on Convex Optimization (2004) which relaxes the convexity assumption and shows that gradient descent ...
- 51
8
votes
2
answers
693
views
Information theoretical interpretation of Free Energy
When exploring the concept of free energy from an information-theoretic perspective, I often come across statements like:
"Free energy measures the degree of surprise an agent experiences when ...
- 253
2
votes
0
answers
38
views
Cluster minimizing sum of cost of clusters
Given a dataset $X,$ having $p$ features, organize the units $x_i \in X $ into fixed number of clusters $g,$ with fixed cluster size $B.$
Clustering policy: minimize the sum of a linear combination of ...
- 31
1
vote
0
answers
44
views
Constrained random sampling from partitioned sets with quotas
Let $D$ be a finite set, $\mathcal{P} = \{D_{i,j}\}_{(i,j) \in I \times J}$ a partition of $D$, $N: J \to \mathbb{N}$ a quota function, and $k \in \mathbb{N}^+$. A subset $F \subseteq D$ is considered ...
- 11
1
vote
0
answers
27
views
Symplectic aggregation over times steps
I am trying to achieve the following: given a sequence of phase space points $\left\{z_j\right\}=\left\{\left(q_j, p_j\right)\right\}$ for $j=1, \ldots, T$.
Goal: Project this sequence to a single ...
- 29
2
votes
0
answers
153
views
How good is approximation of distance function on the Cayley graph by "Fourier" basis coming from the irreducible representations?
Consider finite group $G$ , symmetric set of its elements $S$, construct a Cayley graph.
Consider $d(g)$ - word metric or distance on the Cayley graph from identity to $g$.
As any function on a group ...
- 24.9k
1
vote
0
answers
40
views
From a constraint satisfaction problem (CSP) to a sudoku grid [closed]
one of the existing methods of solvin a sudoku grid is via constraints satisfaction (CSP), but can we do the inverse ie convert a CSP problem into a sudoku grid and then solve it ?
2
votes
0
answers
167
views
How to choose N policemen positions to catch a drunk driver in the most effective way (on a Cayley graph of a finite group)?
Consider a Cayley graph of some big finite group. Consider random walk on such a graph - think of it as drunk driver. Fix some number $N$ which is much smaller than group size.
Question 1: How to ...
- 24.9k
2
votes
0
answers
198
views
Should a neural network architecture change after a pass in gradient descent?
I'm trying to understand neural networks formally a little better and it was always my understanding that the miracle that happens during backpropagation is that "performing a pass in gradient ...
- 81
1
vote
0
answers
50
views
Interpolation in convex hull
I'm reading a paper, Learning in High Dimension Always Amounts to Extrapolation, that provides a result I don't understand.
It provides this theorem which I do understand:
Theorem 1: (Bárány and ...
1
vote
1
answer
97
views
Bayes classifiers with cost of misclassification
A minimum ECM classifier disciminate the features $\underline{x}$ to belong to class $t$ ($\delta(\underline{x}) = t$) if $\forall j \ne t$:
$$\sum_{k\ne t} c(t|k) f_k(\underline{x})p_k \le \sum_{k\ne ...
- 31
2
votes
1
answer
138
views
How to lower bound the absolute value of the difference of two Kullback-Leibler divergences given the constrains below?
Given that $\min (D[p_1||p_3],D[p_2||p_4])=a$, how to find a lower bound of the difference $\left \vert D[p_1\parallel p_2]-D[p_3\parallel p_4] \right\vert$ with respect to $a$? If the condition is ...
- 31
3
votes
0
answers
125
views
Short path problem on Cayley graphs as language translation task (from "Permutlandski" to "Cayleylandski"(s) :). Reference/suggestion request
Context: Algorithms to find short paths on Cayley graphs of (finite) groups are of some interest - see below.
There can be several approaches to that task. One of ideas coming to my mind - in some ...
- 24.9k
4
votes
1
answer
463
views
Difference between deep neural networks and expectation maximization algorithm
Having had a short encounter with deep neural networks, it seems to boil down to the task of determining the values of a vast amount of parameters.
The expectation maximization algorithm, of which I ...
- 13.2k
6
votes
0
answers
197
views
What are compact manifolds such that GROWTH (of spheres volumes) is well approximated by the Gaussian normal distribution?
Consider some compact Riemannian manifold $M$. Fix some point $p$.
Consider a "sub-sphere of radius $r$" - i.e. set of points on distance $r$ from $p$.
Consider growth function $g(r)$ to be ...
- 24.9k
5
votes
0
answers
127
views
Does the permutohedron satisfy any minimal distortion property for graph metric vs Euclidean distance?
We can look on the permutohedron as a kind of "embedding" of the Cayley graph of $S_n$ to the Euclidean space. (That Cayley graph is constructed by the standard generators, i.e. ...
- 24.9k
3
votes
0
answers
109
views
What Cayley graphs arise as nodes+edges from "nice" polytopes and when are these polytopes convex?
The Permutohedron is a remarkable convex polytope in $R^n$, such that its nodes are indexed by permutations and edges correspond to the Cayley graph of $S_n$ with respect to the standard generators, i....
- 24.9k
2
votes
0
answers
35
views
Continuity of Kernel Mean Embeddings
Given some kernel $k: X \times X \to \mathbb{R}$ with RKHS $H_k$ we say that $k$ is characteristic on the space of signed Radon measures over $X$, denoted by $\mathcal{M}(X)$, if the kernel mean ...
- 161
1
vote
0
answers
35
views
A network to transform/predict one probability distribution to another
I have a random variable of a particular density (e.g., normal), and a known probability distribution (e.g., mixture Gaussian). I used a simple KL measure to predict/transform one another. Now I need ...
- 11
0
votes
0
answers
91
views
Some new questions on Rademacher complexity
For $A\subset R^n$,$A=(a_1,a_2,\dots, a_n)$, $\sigma_i$ are Rademacher random variable.
Is $|\mathbb{E}_\sigma \inf_{a\in A}\sum_{i=1}^n\sigma_ia_i| \le |\mathbb{E}_\sigma \sup_{a\in A}\sum_{i=1}^n\...
- 185
12
votes
2
answers
2k
views
Soft question: Deep learning and higher categories
Recently, I have stumbled upon certain articles and lecture videos that use category theory to explain certain aspects of machine learning or deep learning (e.g. Cats for AI and the paper An enriched ...
- 231
53
votes
1
answer
9k
views
What mathematical problems can be attacked using DeepMind's recent mathematical breakthroughs?
I am a research mathematician at a university in the United States. My training is in pure mathematics (geometry). However, for the past couple of months, I have been supervising some computer science ...
- 765
1
vote
0
answers
164
views
Locally "unshortable" paths in graphs
Setup: Consider a connected graph G, with diameter "d".
Informally: Trivially (by definition of diameter), taking any path $P$ any nodes $P(i) , P(i+k)$ for $k>d$ can be connected by a ...
- 24.9k
22
votes
4
answers
2k
views
Open problems which might benefit from computational experiments
Question: I wonder what are the open problems , where computational experiments might me helpful? (Setting some bounds, excluding some cases, shaping some expectations ).
Grant program: The context of ...
3
votes
1
answer
108
views
When does the optimal model exist in learning theory?
In the context of learning theory, we usually have: data $(x,y)\sim P(x,y)$, with $x\in\mathcal{X}\subseteq\mathbb{R}^d$ and $y\in\mathcal{Y}\subseteq\mathbb{R}^k$, a hypothesis class $\mathcal{F}\...
- 199
9
votes
1
answer
861
views
Sufficient condition for linear separability of a boolean function on $n$ variables
This is a cross-post of two recent questions at math.stackexchange without answers: Q1 and Q2.
A boolean function on an $n$-dimensional hypercube is linearly separable when the convex hulls of the ...
- 1,000
2
votes
1
answer
138
views
expectation of the product of Gaussian kernels and their input
I was wondering if anybody knows how to solve: $$\mathbb{E}{\mathbf{z} \sim \mathcal{N}(\mathbf{0}, \mathbf{I})}\left[ (\mathbf{x}{i} - \mathbf{z})(\mathbf{x}{j} - \mathbf{z})^\top \exp\left( - (\...
- 275
7
votes
2
answers
478
views
Upper bound on VC-dimension of partitioned class
Fix $n,k\in \mathbb{N}_+$.
Let $\mathcal{H}$ be a set of functions from $\mathbb{R}^n$ to $\mathbb{R}$ with finite VC-dimension $d\in \mathbb{N}$. Let $\mathcal{H}_k$ denote the set of maps of the ...
- 364
4
votes
0
answers
156
views
Known relations between mutual information and covering number?
This is a question about statistical learning theory. Consider a hypothesis class $\mathcal{F}$, parameterized by real vectors $w \in \mathbb{R}^p$. Suppose I have a data distribution $D \sim \mu$ and ...
- 141
2
votes
1
answer
63
views
Non-linear transforms of RKHS question
I was reading the paper Norm Inequalities in Nonlinear Transforms (referenced in this question) but ran into difficulties, so I was wondering if anyone could help?
I think I follow the paper until I ...
- 41