Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

The tag has no usage guidance.

2
votes
0answers
31 views

Lower bounds for SRM?

This question is about structural risk minimization and model selection. Let $H_n$ be the collection of all binary classifiers on some fixed set with an $n$-bit description length in some fixed ...
2
votes
0answers
62 views

Sample Complexity for Order Statistics

I have a sample complexity question which seems fairly basic, but for which I'm having trouble finding a reference. Let $F$ be an unknown distribution over $[0,1]$. Denote by $X_{k:n}$ the $k$th of $...
1
vote
0answers
46 views

Average margin bounds for separable SVM

Suppose we're training a linear separator in the realizable PAC setting. Given $m$ labeled examples $(x_i,y_i)$ in $\mathbb R^d\times\{-1,1\}$, a (consistent) linear separator is a vector $w\in\mathbb ...
0
votes
0answers
40 views

Function that maps non-linear distribution to normal distribution while maintaining distance

I have a collection $X$ of 10 million $(x,y,z)$ 3-tuples, where $x$, $y$, and $z$ are all numbers between 0 and 1. The distribution of $x$, $y$, and $z$ values are complex, and the distributions of $...
3
votes
2answers
156 views

How can AIC converge in the limit when even 2 parameter models can have infinite VC dimension?

AIC-based model-selection converges to zero error in the limit, and also has finite-sample convergence that is rate-optimal with respect to worst case minimax error [1]. (Note that AIC refers to ...
4
votes
1answer
88 views

Design a sampling process to select an element with probability proportional to its appear probability in a simulation

We are given a black box $A$ that can do a simulation. Each time running box A gives a sample $S \in 2^X$ where $X$ is a finite ground set. Let $\Pr[x]$ be the probability that $x \in X$ appears in ...
1
vote
0answers
51 views

To what extent supervised learning ERM learn first-order knowledge

Suppose I have a collection of (hidden) first-order rules: $$ \mathcal{R}: \{ Q_i(x) => P_i(x) \}_{i=1}^{k} $$ all defined over $x \in \mathcal{X}$. I can use these rules and (automatically) ...
0
votes
0answers
59 views

Applications for non-commutative Khinchine inequality

I am looking for the applications of non-commutative Khinchine inequality (see below) in case when Rademacher random variables are tight by the condition $\sum_{i=1}^N\varepsilon_i=M, \, -N \leq M\leq ...
-1
votes
1answer
144 views

Application of the inequality with expectations

Let $\Vert\cdot\Vert$ is a norm in $R^n$. Let $x_1,\dots,x_N$ non-independent Rademacher random variables random variables (variables which are uniform on $\{-1, 1\}$). . By $E$ we denote an ...
0
votes
1answer
56 views

Learning a discrete distribution in $\ell_r$ norm

Let $P=(p_1,\ldots,p_d)$ be a distribution on $[d]$. Given $n$ iid draws from $P$, we construct some empirical estimate $\hat P_n=(\hat p_{n,1},\ldots,\hat p_{n,d})$. Let us define the $r$-risk by $$ ...
13
votes
0answers
193 views

Differential privacy and data poisoning

A differentially private algorithm takes datasets containing inputs and produces randomized outputs, such that no small change in the dataset can shift the distribution of outputs by too much. This ...
3
votes
2answers
373 views

Learning a coin's bias (localized)

It's well known that the minimax sample complexity for estimating the bias $p$ of a coin to additive error $\epsilon$ with confidence $\delta$ is $\Theta(\epsilon^{-2}\log(1/\delta))$. What if we ...
-1
votes
1answer
98 views

L1 / Variational Distance between distributions [closed]

My statistics knowledge is somewhat poor, so I have to ask one (dumb) question. Let $\beta$ be a real number in the interval $\big[0, \frac{1}{2}\big)$ and $\mathcal{D}_1, \mathcal{D}_2, \mathcal{D}...
7
votes
2answers
237 views

What is the connection between moments of Gaussians and perfect matchings of graphs?

Today, I heard the following statement in a talk: The 4th moment of a $1$-dimensional Gaussian distribution with mean $0$ and variance $1$ is the same as the number of perfect matchings of a ...
1
vote
1answer
81 views

Learning from derivative data

In many machine learning algorithm, it is often assumed that outputs of unknown function and their corresponding inputs are given to estimate the unknown function. However, I wonder whether there ...
2
votes
0answers
65 views

Impossibility result on metric learning?

Are there any fundamental limitations (impossibility results) known for metric learning? Are there any direct connection reduction from/to that I can use results in clustering? (e.g. this: 2 ) 2 ...
1
vote
0answers
94 views

Maximal correlation vs correlation coefficient when one RV is Gaussian

Last week I asked a question on MOF (see here), but I got no reply. So I am asking my question here. Let a pair of random variables $(X,Y)$ be continuous random variables (i.e., they both have ...
8
votes
1answer
377 views

Exponential Concentration Inequality for Higher-order moments of Gaussian Random Variables

Let $X_1,\ldots, X_n$ be $n$ i.i.d. copies of Gaussian random variable $X \sim N(0, \sigma^2)$. It is known that \begin{align} \mathbb{P}\Bigl( \Bigl|\frac{1}{n}\sum_{j=1}^n X_j \Bigl| >t\Bigr) &...
2
votes
1answer
131 views

Tolerance parameter of statistical query model and adaptivity

It seems that the reasonable assumption for the tolerance parameter of statistical query model is roughly $1/\sqrt{n}$, which is obtained from concentration inequalities (see, e.g., Definition 2.3 of ...
4
votes
3answers
189 views

Approximating distributions from samples

One claim I find in many papers about identity testing, and closeness testing is that any distribution over $[n]$ can be approximated to within $\ell_1$ distance $\epsilon$ in $O\left(\frac{n}{\...
0
votes
0answers
46 views

Establishing causality under conditions of certainty

I'm currently reading "Causality: Models, Reasoning, and Inference" by Judea Pearl. Early on, he states that the development assumes that there are no certain entailments, no 1 or 0 probabilities -- ...
3
votes
1answer
412 views

An upper bound for chi-square divergence in terms of KL divergence for general alphabets

In my research I need an upper bound for chi-square divergence in terms KL divergence which works for general alphabets. To make this precise, note that for two probability measures $P$ and $Q$ ...
0
votes
0answers
107 views

Orlicz Norm and a result on expectation

I am reading a paper which is mainly about Dobrushin's contraction coefficient and its generalization. In page 27, the following is defined: Consider an arbitrary, non-negative, convex function $\psi:\...
3
votes
0answers
73 views

One kind of dependence relation between a pair of random variables

I have been working on privacy and come across a neat problem. Suppose two random variables $X$ and $Y$, over finite alphabets $\mathcal{X}$ and $\mathcal{Y}$, are given with joint distribution $P_{...
2
votes
0answers
119 views

Strong Dependence

I asked this question on MO, but no answer. I don't know if this definition has been already given. Suppose $X$ and $Y$ are two random variables over finite alphabets $\mathcal{X}$ and $\mathcal{Y}$...
7
votes
2answers
257 views

Maximizing the number of heads in $N$ tosses by choosing which coin to toss

Assume you have two coins $A,B$ with biases $P_A,P_B$ respectively. We would like to make $N$ coin tosses and get the maximal number of heads possible. Unfortunately, we know $P_B$, but $P_A$ is ...
1
vote
0answers
235 views

What's the meaning of the class indicator matrix when transforming the class label matrix into it in canonical correlation analysis?

When using canonical correlation analysis (CCA), we can integrate the dataset and label information via transforming the class label matrix Y into the class indicator matrix T. Such as: $T = (YY^T)^½Y$...
6
votes
1answer
276 views

Proof Haar matrices satisfy JL lemma

The Johnson-Lindenstrauss lemma says roughly that for any collection $S$ of $n$ points in $\mathbb{R}^d$, there exists a linear map $f:\mathbb{R}^d \rightarrow \mathbb{R}^k$ where $k = O(\log n/\...
4
votes
0answers
458 views

Practical Implications of Kolmogorov's Result on the Universal Approximation Theorem with Neural Networks

After having read matus's beautiful answer in this thread explaining (among other things) Kolmogorov's result regarding the Universal Approximation Theorem with Neural Networks, I wonder: if just $\...
2
votes
0answers
187 views

Expected probability of error in Vapnik's book

In Vapnik's book "Statistical Learning Theory", Theorem 10.5 states that - for a Support Vector Machine - the expected probability of error (of the optimal hyperplane) is upper bounded by $1/(l+1)$ ...
14
votes
2answers
304 views

Theoretical guarantees for running times of belief propagation methods?

Belief propagation has been shown to be a very powerful method through research in probabilistic graphical models. However, I don't know anything about BP that's comparable to MCMC methods where we ...
11
votes
4answers
514 views

Lower bound for testing closeness in $L_2$ norm?

I was wondering if there was any lower bound (in terms of sample complexity) known for the following problem: Given sample oracle access to two unknown distributions $D_1$, $D_2$ on $\{1,\dots,n\}$, ...
5
votes
1answer
1k views

What happens if you minimize $D_{KL}(P_{parameters} || P_{data})$ under the Kullback-Leibler divergence?

If $D_{KL}$ is the Kullback-Leibler divergence, minimizing $D_{KL}(P_{data}||P_{parameters})$ performs maximum likelihood estimation of the parameters. What happens if you minimize $D_{KL}(P_{...
1
vote
1answer
194 views

How to choose a correct prior

Consider a Bernoulli experiment, such as flipping a not necessarily fair coin, which results in a positive outcome (heads) with probability $p$ and with a negative outcome (tails) with probability $(1-...
0
votes
3answers
660 views

Algorithm Suggestion for Scoring System - weighted solution

I'm trying to validate a series of words that are provided by users. I'm trying to come up with a scoring system that will determine the likelihood that the series of words are indeed valid words. ...
7
votes
1answer
818 views

Streaming Algorithms: Motivations for estimating frequency moments

The celebrated AMS paper "The space complexity of approximating the frequency moments" defines the problem as following: Let $a_1, a_2,\dotsc, a_m$ be a sequence of integers where each $a_j \in \{1,2,...
2
votes
0answers
38 views

Lower bounds for minimum variance estimators in limited space

Cramer-Rao, Rao-Blackwell and Lehmann-Scheffé, all give you ways to prove that a statistical estimator has the lowest variance possible. Is there any CS related work on the minimum variance ...
3
votes
1answer
335 views

Estimator for sum of independent and identically distributed (iid) variables

This is a repost of a question at math.stackexchange, but I was told by a reliable source that people around here might be able to help me, so I thought I'd give it a shot. Consider the Chernoff ...
1
vote
0answers
152 views

Distribution of number of unique items in a sample

Suppose we're sampling a discrete random variable from a distribution f, n times. Is there a simple analytical formulation for the expected number of unique items we obtain, or for the distribution of ...
11
votes
1answer
413 views

Distinguishing between $N$ quantum states

Given a quantum state $\rho_A$ chosen uniformly at random from a set of $N$ mixed states $\rho_1 ... \rho_N$, what is the maximum average probability of correctly identifying $A$? This problem can be ...
5
votes
2answers
598 views

Is analogy between database and probability concepts legitimate?

In Relational Databases: Tutorial for Statisticians Joe R. Hill casts probability view onto database theory. In Table 1 the author summarized the parallels between the two disciplines, describing ...
1
vote
0answers
117 views

High Dimensional Volume (HDV) estimator for Entropy estimation

I am writing a program using high-dimensional volume (HDV) estimator to estimate entropy and mutual information for variable selection. Let $ D = (x^i_1, x^i_2, ..., x^i_M)$, N is the number of data ...
4
votes
2answers
1k views

Multiplication of normal distributions

Suppose X_1, ..., X_k are iid standard Gaussian variables, for some k > 1. Then, what is the distribution of X := X_1 * ... * X_k ? Can it be approximated by a Gaussian, maybe for large k ?
-2
votes
1answer
468 views

Distributing items randomly into groups of equal size

Given n items (20% type A, 80% type B), I'm looking for a way to distribute them randomly into g groups of equal size. It must be possible for one group to end up with As in the majority but it must ...
23
votes
1answer
669 views

Estimating a percentile among distributed nodes without revealing values

I have a fairly unique problem to solve and I am hoping somebody here can give me some insight into how to best tackle it. Problem: Suppose a list of N numbers is shared among a set of participants ...
4
votes
1answer
157 views

Measures of “correlation” between two orderings

An easy question perhaps? Taking a (fictional) concrete example, let's say I have two ranking methods for HTML documents: PageRank and HITS. I derive an ordered list over the same set of documents ...
2
votes
2answers
319 views

Generate a sequence of numbers

I want to generate an infinite sequence of numbers between $0$ and $9$ such that the percentage of number $i$ appearing in the sequence is $p_i$. Let $p=\lbrace p_0,...,p_9\rbrace$. Another agent $B$ ...
0
votes
1answer
135 views

Analysis of variables of varying numbers

i work with amino acid sequences and i want to use a selfmade model to tell me something about it, lets call it f(seq). Now i want to know the contribution of every position in the sequence onto the ...
7
votes
3answers
600 views

What subjects, topics does a computer science graduate need to learn to apply available machine learning frameworks, esp. SVMs

I want to teach myself enough machine learning so that I can, to begin with, understand enough to put to use available open source ML frameworks that will allow me to do things like: Go through the ...
8
votes
1answer
225 views

Circuit complexity and statistical tests

A few years ago, I took a class on complexity theory from Steven Rudich, and I remember him giving an interesting lecture connecting statistical tests (as found in statistics departments!) with ...