Questions tagged [machine-learning]
The machine-learning tag has no usage guidance.
199 questions
1
vote
0
answers
31
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
54
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
118
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
687
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.8k
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.8k
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.8k
4
votes
1
answer
462
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.8k
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.8k
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.8k
2
votes
0
answers
34
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 ...
- 191
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.8k
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 ...
- 988
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
477
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
154
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
57
votes
10
answers
10k
views
A clear map of mathematical approaches to Artificial Intelligence
I have recently become interested in Machine Learning and AI as a student of theoretical physics and mathematics, and have gone through some of the recommended resources dealing with statistical ...
1
vote
0
answers
85
views
Approximation of continuous function by multilayer Relu neural network
For continuous/holder function $f$ defined on a compact set K， a fix $L$ and $m_1,m_2,\dots,m_L$, can we find a multilayer Relu fully connected network g with depth $L$ and each $i$-th layer has width ...
- 781
1
vote
2
answers
221
views
Beating the $1/\sqrt n$ rate of uniform-convergence over a linear function class
Let $P$ be a probability distribution on $\mathbb R^d \times \mathbb R$, and let $(x_1,y_1), \ldots, (x_n,y_n)$ be an iid sample of size $n$ from $P$. Fix $\epsilon,t\gt 0$. For any unit-vector $w \in ...
- 6,853
1
vote
0
answers
134
views
Matrix valued word embeddings for natural language processing
In natural language processing, an area of machine learning, one would like to represent words as objects that can easily be understood and manipulated using machine learning. A word embedding is a ...
3
votes
1
answer
165
views
Why is the logistic regression model good? (and its relation with maximizing entropy)
Suppose we're trying to train a classifier $\pi$ for $k$ classes that takes as input a feature vector $x\in\mathbb{R}^n$ and outputs a probability vector $\pi(x)\in\mathbb{R}^k$ such that $\sum_{v=1}^...
- 7,527
9
votes
1
answer
323
views
Who introduced the term hyperparameter?
I am trying to find the earliest use of the term hyperparameter. Currently, it is used in machine learning but it must have had earlier uses in statistics or optimization theory. Even the multivolume ...
- 879
2
votes
0
answers
115
views
Equivalence of score function expressions in SDE-based generative modeling
I am studying the paper "Score-Based Generative Modeling through Stochastic Differential Equations" (arXiv:2011.13456) by Yang et al. The authors use the following loss function (Equation 7 ...
- 43
8
votes
1
answer
583
views
Geometric formulation of the subject of machine learning
Question:
what is the geometric interpretation of the subject of machine learning and/or deep learning?
Being "forced" to have a closer look at the subject, I have the impression that it ...
- 13.2k
1
vote
0
answers
109
views
Problems Correction of "Algebra, Topology, Differential Calculus, and Optimization Theory For Computer Science and Machine Learning "' [closed]
Where I can find the problems correction of this book " Algebra, Topology, Differential Calculus, and Optimization Theory For Computer Science and Machine Learning "
- 11
3
votes
0
answers
81
views
Prove the convergence of the LASSO model in the presence of limited eigenvalues
I am researching the properties of the Lasso model $\hat \beta:= \operatorname{argmin} \{\|Y-X\beta\|_2^2/n+\lambda\|\beta\|_1\}$, specifically its convergence when the data satisfies restricted ...
- 39
11
votes
0
answers
169
views
Worst margin when halving a hypercube with a hyperplane
Consider the $n$-cube $C_n=\lbrace-1,1\rbrace^n$ and the problem of partitioning it into halves with hyperplanes through the origin that avoid all its points. We can parameterize the hyperplanes by ...
- 1,085
2
votes
0
answers
93
views
Curve fitting with "rough" loss functions
Many real-valued classification and regression problems can be framed as minimization in the following way.
Setup:
Let $\Theta \in \mathbb{R}^p$ be the parameter space that we are searching over.
For ...
- 200
5
votes
1
answer
2k
views
Mathematics research relating to machine learning
What branch/branches of math are most relevant in enhancing machine learning (mostly in terms of practical use as opposed to theoretical/possible use)? Specifically, I want to know about math research ...
- 173
1
vote
1
answer
126
views
Adjoint sensitivity analysis for a cost functional under an ODE constraint
I am trying to recover the result given by equation 10 in the article here. I am unable to get rid of the integral, any help would be much appreciated. To keep the description as self contained as ...
- 55
2
votes
1
answer
73
views
Convergence of minimiser of empirical risk to minimiser of population risk
Let $X_1, \dots, X_n \sim \mu$ be some random elements of a space $\mathcal{X}$. Let $H$ be a Hilbert space of functions $f: S \to \Re$ with norm $\|\cdot\|_H$.
Let $\|f^*\|_{L_2(\mu)} < \infty$ ...
- 337