Questions tagged [machine-learning]
The machine-learning tag has no usage guidance.
77
questions with no upvoted or accepted answers
18
votes
0
answers
308
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 ...
- 96.1k
11
votes
0
answers
165
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,065
8
votes
0
answers
326
views
Monotonicity of log determinant of Gaussian kernel matrix
Let \begin{equation} k({x},{y}) = \sigma \exp\left(-\frac{(x-y)^2}{2\theta^2}\right)\end{equation}
be a squared-exponential (Gaussian) kernel, with $\sigma,\vartheta>0$. Consider, for a set of $N$ ...
- 55
8
votes
0
answers
120
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\...
- 855
6
votes
0
answers
190
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.5k
6
votes
0
answers
341
views
Signature and cusp geometry of hyperbolic knots
Nature recently published a paper titled “Advancing mathematics by guiding human intuition with AI”. Using the power of linear algebra and calculus machine learning, the authors link "geometric&...
- 2,273
6
votes
1
answer
459
views
Why is this nonlinear transformation of an RKHS also an RKHS?
I came across this paper (beginning of page 6) where they stated that if $f,h\in \mathcal{H}$, where $\mathcal{H}$ is an RKHS, then $l_{h,f}=\left|f(x)-h(x)\right|^q$ where $q\geq 1$ also belongs to ...
- 383
5
votes
0
answers
119
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.5k
5
votes
0
answers
213
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 ...
- 6,181
5
votes
0
answers
188
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 ...
- 28.4k
5
votes
0
answers
184
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$-...
- 51
4
votes
0
answers
141
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
4
votes
0
answers
120
views
Progress on "Un-Alching" ML?
So, a couple of years ago I watched both Ali Rahimi's NIPS speech "Machine Learning is Alchemy",
(where he talks about how the field lacks a solid, overarching, theoretical foundation) and ...
- 41
4
votes
0
answers
151
views
Can we show equivalence of two distributions based on their statistics?
Let $p,q$ be two distributions on $\mathbb{R}^d$. Let $f:\mathbb{R}^d\times\mathbb{R}^d\rightarrow\mathbb{R}$. Under what conditions does $\mathbb{E}_{x\sim p}f(x,z)=\mathbb{E}_{x\sim q}f(x,z)\ \...
- 57
3
votes
0
answers
116
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.5k
3
votes
0
answers
96
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.5k
3
votes
0
answers
64
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
3
votes
0
answers
58
views
How to prove emprical risk converges to expectation risk as $n\to \infty$?
For example, for a classical binary classification:
$x \in \mathbb{R}^d$ and $y \in\{0,1\}$
let empirical risk be
$R_{\ell}^n(f):=\frac{1}{n} \sum_{i=1}^n \ell\left(f\left(X_i\right), Y_i\right)$
and ...
- 51
3
votes
0
answers
167
views
What is the meaning of big-O of a random variable?
I encountered this problem in a book "Pattern Recognition and Machine Learning" by Christopher M. Bishop. I excerpt it below:
screenshot of the book
In the excerpt, the big-O notation $O(\xi^...
- 31
3
votes
0
answers
226
views
What is the VC-dimension of regular convex k-gons in the plane?
Recall the relevant definitions:
Let $H$ be a family of sets in $\mathbb{R}^d$. The intersection of $H$ with a point set $C$ is defined as $H\cap C = \{h\cap C\mid h\in H\}$. The VC-dimension of $H$ (...
- 131
3
votes
0
answers
563
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-...
- 1,427
3
votes
0
answers
467
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 ...
- 163
2
votes
0
answers
139
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.5k
2
votes
0
answers
164
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.5k
2
votes
0
answers
192
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
2
votes
0
answers
29
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 ...
- 91
2
votes
0
answers
111
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
2
votes
0
answers
78
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
2
votes
0
answers
42
views
can we get a family of classifiers $\left\{f_n\right\}_{n \in N}$such that $\lim_{n->∞} (E_{(X_1, Y_1), ...,(X_n, Y_n) \sim \rho}[R(f_n)]-R(f_B))=0 $
For a given classifier $f: \mathbb{R}^d \mapsto\{0,1,2\}$, let
$$
R(f):=\mathbb{E}_{(X, Y) \sim \rho}\left[\mathbb{1}_{f(X) \neq Y}\right]
$$
$f_B$ the Bayes classifier.
can we get a family of ...
- 51
2
votes
0
answers
130
views
Training an energy-based model (EBM) using MCMC
I'm reading this paper about training energy-based models (EBMs) and don't understand the parameters that we are training for? The part that is relevant to the question is in pages 1-4. Here is the ...
- 201
2
votes
0
answers
86
views
Nuclear norm minimization of convolution matrix (circular matrix) with fast Fourier transform
I am reading a paper Recovery of Future Data via Convolution Nuclear Norm Minimization. Here, I know there is a definition for convolution matrix.
Given any vector $\boldsymbol{x}=(x_1,x_2,\ldots,x_n)^...
- 21
2
votes
0
answers
44
views
Combining SVD subspaces for low dimensional representations
Suppose we have matrix $A$ of size $N_t \times N_m$, containing $N_m$ measurements corrupted by some (e.g. Gaussian) noise. An SVD of this data $A = U_AS_A{V_A}^T$ can reveal the singular vectors $U_A$...
- 21
2
votes
0
answers
270
views
Covering/Bracketing number of monotone functions on $\mathbb{R}$ with uniformly bounded derivatives
I am interested in the $\| \cdot \|_{\infty}$-norm bracketing number or covering number of some collection of distribution functions on $\mathbb{R}$.
Let $\mathcal{F}$ consist of all distribution ...
- 93
2
votes
0
answers
44
views
Convergent algorithm for minimizing nonconvex smooth function
Let $\Phi$ be the Gaussian CDF and for $\gamma\ge 0$ and $h>0$, define a loss function $\ell_h:\{\pm 1\} \times \mathbb R$ by
$$
\ell_{\gamma,h}(y,y') := \phi_{\gamma,h}(yy') := \Phi((yy'-\gamma)/h)...
- 6,843
2
votes
0
answers
37
views
Stochastic gradient descent in 'stronger' settings
I am minimzing a function $F(x) = \mathbb E(f(x,\Xi))$ where $\Xi$ is some random value, by a stochastic gradient descent that generates a random number $\xi$ from the distribution of $\Xi$ at each ...
- 686
2
votes
0
answers
80
views
A question about fundamental invariants in the context of neural networks
I'm reading in depth the first part of the following paper: https://arxiv.org/pdf/1804.10306.pdf, paying specific attention to the following result, that I re-write here for the sake of convenience:
[...
- 133
2
votes
0
answers
105
views
What is known about gradient descent on quadratic models (not loss functions!)
Let $\mathcal X$ be any set, and $f:\mathcal X\times\mathbb R^n\to\mathbb R$ be a differentiable model, meaning that for any fixed first argument, $f$ is differentiable in its second argument. Then we ...
- 633
2
votes
0
answers
49
views
What are some beginner's references on algebraically structured (statistical) models, and their connection with group actions and Fourier transform?
I asked this question on Cross Validated a few days ago, but didn't really get a favorable response, so asking here to see if I get any.
I'm looking at the description of a short-term position in ...
- 223
2
votes
0
answers
208
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{\...
- 245
2
votes
0
answers
91
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 ...
- 31
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,\...
user128095
1
vote
0
answers
29
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 ...
- 21
1
vote
0
answers
40
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
23
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
1
vote
0
answers
45
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
0
answers
30
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
1
vote
0
answers
163
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.5k
1
vote
0
answers
80
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
0
answers
128
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 ...
- 28.4k
1
vote
0
answers
32
views
Convergent gradient-type scheme for solving smooth nonconvex constrained optimization problem
Let $x_1,\ldots,x_n \in \mathbb R^d$ and $y_1,\ldots,y_n \in \{\pm 1\}$, and $\epsilon, h \gt 0$. Define $\theta(t) := Q((t-\epsilon)/h)$, where $Q(z) := \int_{z}^\infty \phi (z)\mathrm{d}z$ is the ...
- 6,843