All Questions
27 questions
1
vote
1
answer
216
views
Rademacher complexity of function class $(x,y) \mapsto 1[|yf(x)-\alpha| \ge \beta]$ in terms of $\alpha$, $\beta$, and Rademacher complexity of $F$
Let $X$ be a measurable space and let $P$ be a probability distribution on $X \times \{\pm 1\}$. Let $F$ be a function class on $X$, i.e., a collection of (measurable) functions from $X$ to $\mathbb R$...
- 12.9k
3
votes
2
answers
358
views
Minimax optimal multiple hypothesis test
Let us consider the following two-player game
between Chooser and Guesser.
There is a finite set $\Omega$
and $k$ probability distributions
on $\Omega$, denoted by $
\mathcal{P}
=\{P_1,\ldots,P_k\}
$.
...
- 165
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}\...
- 12.7k
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 ...
1
vote
0
answers
100
views
$L_1$ convergence rates for multivariate kernel density estimation
Let $X$ be a random variable on $\mathbb R^d$ with probability density function $f$, and let $X_1,\ldots,X_n$ of $X$ be $n$ iid copies of $X$. Given a bandwidth parameter $h=h_n > 0$ and a kernel $...
1
vote
1
answer
199
views
Rademacher complexity for a family of bounded, nondecreasing functions?
Let $\{\phi_k\}_{k=1}^K$ be a family of functions mapping from an interval $[a, b]$ to $[-1, 1]$.
That is, $\phi_k \colon[ a,b] \to [-1, 1]$ are nondecreasing maps on some finite interval $[a, b] \...
- 420
1
vote
1
answer
176
views
Tight upper-bounds for the Gaussian width of intersection of intersection of hyper-ellipsoid and unit-ball
Let $\Lambda$ be a positive-definite matrix of size $n$ and let $R \ge 0$, which may depend on $n$. Consider the set $S := \{x \in \mathbb R^n \mid \|x\|_2 \le R,\,\|x\|_{\Lambda^{-1}} \le 1\}$ where $...
- 6,853
1
vote
0
answers
24
views
Minimax statistical estimation of proximal transform $\mbox{prox}_g(\theta_0)$, from linear model data $y_i := x_i^\top \theta_0 + \epsilon_i$
tl;dr: My question pertains the subject of minimax estimation theory (mathematical statistics), in the context of linear regression.
Given a vector $\theta_0 \in \mathbb R^d$, consider the linear ...
- 6,853
1
vote
0
answers
417
views
Conditions for equivalence of RKHS norm and $L^2(P)$ norm
Let $K$ be a psd kernel on an abstract space $X$ and let $H_K$ be the induced Reproducing Kernel Hilbert Space (RKHS). Let $P$ be a probability measure on $X$ such that $H_K \subseteq L^2(P_X)$ and ...
- 6,853
0
votes
0
answers
97
views
Verification of a certain computation of VC dimension
Disclaimer: I'm not very familiar with the concept of VC dimensions and how to manipulate such objects. I'd be grateful if expects on the subject (learning theory, probability), could kindly proof ...
- 6,853
0
votes
0
answers
195
views
Upper-bound for bracketing number in terms of VC-dimension
Let $P$ be a probability distribution on a measurable space $\mathcal X$ (e.g;, some euclidean $\mathbb R^m$) and let $F$ be a class of funciton $f:\mathcal X \to \mathbb R$. Given, $f_1,f_2 \in F$, ...
- 6,853
4
votes
0
answers
164
views
Convergence rates for kernel empirical risk minimization, i.e empirical risk minimization (ERM) with kernel density estimation (KDE)
Let $\Theta$ be an open subset of some $\mathbb R^m$ and let $P$ be a probability distribution on $\mathbb R^d$ with density $f$ in a Sobolev space $W_p^s(\mathbb R^d)$, i.e all derivatives of $f$ ...
- 6,853
1
vote
0
answers
233
views
Variance-based localized Rademacher complexity for RKHS unit-ball
Let $\mathscr X$ be a compact subset of $\mathbb R^d$ (e.g the unit-sphere). Let $K: \mathscr X \times \mathscr X \to \mathbb R$ be a positive kernel function and let $\mathscr H_K$ be the induced ...
- 6,853
1
vote
0
answers
99
views
Covering number after projection
In these lecture notes on Statistical Learning Theory we find the following definitions for covering numbers:
Definition. Let $(\mathcal{W}, d)$ be a metric space and $\mathcal{F} \subset \mathcal{W}$...
3
votes
1
answer
294
views
Concentration inequalities specialized for log-likelihood / log-density functions
Let $P$ be a probability measure and $f$ be some probability density function (not necessarily related to $P$). Consider the function
$$
L(X_1,\ldots,X_n)
=\frac1n\sum_{i=1}^n\log f(X_i),
\quad
X_i\...
- 6,541
15
votes
1
answer
1k
views
Table with the most seated customers in Chinese restaurant process
Suppose we have some initial configuration of people seated at some tables. We start taking new customers and seat them following Chinese restaurant process. Is there some known work on finding the ...
CommunityBot
- 1
2
votes
0
answers
448
views
Relation between pseudo-dimension and Rademacher complexity
With techniques of Dudley's entropy bound and Haussler's upper bound one can show that there exists a constant $C$ such that any class of $\{0,1\}$ indicator functions with Vapnik-Chervonenkis ...
- 517
3
votes
1
answer
213
views
Is this generalization bound proof wrong?
This is an ICML02 paper by Garg, Har-Peled & Roth:
http://sarielhp.org/p/01/bounds/bounds.pdf
The equation after eq. (3) is the well-known symmetrization trick for $\sup_{h\in {\mathcal H}} |E(h)-...
- 3,958
2
votes
1
answer
658
views
Extension of Talagrand contraction lemma (on empirical Rademacher complexity)
Is the following true?
Let $(x_1,...,x_N)$ be a set of points on the unit sphere $S^{d-1}$.
Let $\ell_x: [-1,1]\rightarrow [0,1]$ be a family of Lipschitz functions indexed by $x\in S^{d-1}$, with ...
- 517
1
vote
1
answer
86
views
Clarification on margin bound uniform w.r.t. the margin parameter
Theorem 4.5. in the book "Foundations of Machine Learning" by Mohri et al:
http://prlab.tudelft.nl/sites/default/files/Foundations_of_Machine_Learning.pdf
derives a generalization bound to hold ...
- 26
2
votes
1
answer
1k
views
Rademacher complexity of composition of functions
I am looking for a bound on the empirical Rademacher complexity of the following class:
$G=\left\{x \rightarrow \frac{h^T f(x)}{\|h\|_2 \cdot \|f(x)\|_2} : h\in R^d, f()=(f_1(),\ldots,f_d()), f_j \in ...
2
votes
1
answer
327
views
Recursive parameter estimation for partially observed Ito SDEs
I'm trying to get my head around online (recursive) maximum-likelihood parameter estimation in the language of stochastic processes and in the context of stochastic filtering, i.e. where we have a ...
- 1,675
3
votes
1
answer
269
views
Learn a distribution from distributions on samples
There's many good ways to learn a distribution $p_X$ of an r.v. $X$ over $k$ symbols given many i.i.d. samples $X_1,\ldots, X_n$. The simplest is to use the sample relative frequencies $\hat{f}_X$ as ...
- 219
5
votes
1
answer
373
views
assumptions on local rademacher complexities
A lot of the work on Local Rademacher complexities of Koltchinskii, and Bartlett for fast rates of convergence is based on Bousquet's version of Talagrand's inequality [1] (Theorem 2.11). However the ...
CommunityBot
- 1
6
votes
1
answer
526
views
Is there a mistake in Vapnik's "Basic Lemma"?
I have a concern about the "Basic Lemma" which Valdimir Vapnik states and proves in his 1998 book Statistical Learning Theory (ch. 14.3, pp. 574–76): It seems like a certain coefficient should have ...
- 24.8k
1
vote
2
answers
362
views
A machine learning application question
I am familiar with basic probabilities, random processes but not so much of machine learning methods. This is the problem I am trying to solve.
I want to predict the nature of user activity on a ...
- 186