All Questions
25 questions
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
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
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
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
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
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
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
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
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
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
0
answers
59
views
How to calculate the unifrom entropy or VC dimension of the following class of functions?
When dealing with U process I meet with such a uniform entropy to calculate.
For any $\eta>0$, function class $\mathcal{F}$ containing functions $f=\left(f_{i, j}\right)_{1 \leq i \neq j \leq n}: \...
- 11
3
votes
1
answer
243
views
Independent input feature z can be removed: if y=f(x+z,z), then y=g(x)?
Let $y\in \mathbb{R}$ and $\mathbf{x},\mathbf{z}\in\mathbb{R}^p$ be random variable and random vectors. Assume $y=f(\mathbf{x}+\mathbf{z},\mathbf{z})$ for some function $f$.
Is the following statement ...
- 193
6
votes
2
answers
344
views
Entropy & difference between max and min values of probability mass
Let $X$ be a random variable with probability mass function $p(x) = \mathbb{P}[X = x]$.
I know entropy $H(X)$ of $X$ measures the uncertainty of $X$ and
a large value of $H(X)$ means $p(x)$ is nearly ...
- 163
1
vote
1
answer
251
views
Using Hoeffding inequality for risk / loss function
I've got a question to the Hoeffding Inequality which states, that for data points $X_1, \dots, X_n \in X$, which are i.i.d. according to a probability measure $P$ on $X$, we find an upper bound for:
$...
- 13
2
votes
1
answer
185
views
Bayes risk of binary classification problem with conditionally independent covariates
In the setting of this problem, $\eta(\vec{x})$ is $P(Y=1|\vec{X}=\vec{x})$, $Y \in \{0,1\}$, and $X \in R^d$. Being the true probability know, the classification rule is simply $\eta(\vec{x})>0.5 \...
0
votes
1
answer
3k
views
In linear regression, we have 0 training error if data dimension is high, but are there similar results for other supervised learning problems?
I tried posting this question on Cross Validated (the stack exchange for statistics) but didn't get an answer, so posting here:
Let's consider a supervised learning problem where $\{(x_1,y_1) \dots (...
- 1,467
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
0
votes
1
answer
105
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.
...
- 301
4
votes
0
answers
638
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,467
1
vote
0
answers
45
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, ...
- 39
1
vote
0
answers
151
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 ...
- 19
4
votes
5
answers
7k
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 ...
- 171
6
votes
1
answer
1k
views
Why the Fisher information matrix is equal to the Hessian matrix of the Kullback–Leibler distance at the true parameter?
I'm reading 《Algebraic geometry and statistical learning theory》.My problem is why the Fisher information matrix is equal to the Hessian matrix of the Kullback–Leibler distance at the true parameter?...
- 103
3
votes
1
answer
171
views
Why does the assumption $|U_t| \le \frac1{p_{\min}}$ work in this paper?
I am reading a 2009 paper right now "Importance Weighted Active Learning" and on page 5, there is a theorem that uses the inequality $|U_t| \leq \frac{1}{p_{\min}}$. I am not sure how the paper found ...
- 33
8
votes
2
answers
976
views
Approximation of Wasserstein distance between $p_\theta$ and $p_{\theta + d\theta}$
Given a parametric family of distributions $\{p_\theta\mid\theta \in \Theta\}$, one can show that under some regularity conditions, the following approximation is valid
$$\operatorname{KL}(p_\theta\...
- 6,853