# 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 ...

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 ...

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$ ...

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\...

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 ...

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&...

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 ...

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. ...

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 ...

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 ...

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$-...

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 ...

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 ...

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)\ \...

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 ...

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....

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 ...

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 ...

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^...

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$ (...

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-...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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)^...

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$...

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 ...

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)...

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 ...

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:
[...

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 ...

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 ...

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{\...

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 ...

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

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...