Questions tagged [sample-complexity]
The sample-complexity tag has no usage guidance.
35
questions
0
votes
0
answers
23
views
An upper bound on sample complexity for state identification given ensemble distinction problem
I am trying to derive Fact 5. in paper 1:
Let $\mathscr{E}=\{\sigma_1,.., \sigma_m\}$ be an ensemble of quantum states in $\mathbb{C}^n$. If there is a POVM $\mathscr{M}$ for the state distinction ...
0
votes
0
answers
94
views
Faster algorithm for sampling unifromly at random
The goal is to come up the simple data structure for sampling a uniform point from a collection of sets, i.e., given a sub-collection
$\mathcal{B}$, sample a point in $\cup \mathcal{B}$
uniformly at ...
- 115
1
vote
0
answers
64
views
Relationship between statistical query lower bounds and "traditional" iid sampling lower bounds
Coming from a more statistical background, it is not clear to me if or how lower bounds in the statistical query (SQ) model imply anything useful about traditional learning problems with iid samples (...
- 19
0
votes
0
answers
34
views
PAC guarantees for linear prediction under the squared loss
I am looking for generalisation bounds under the squared loss, specifically for the class $\mathcal{F}_{\text{lin}} = \{f(x) = \langle w, x \rangle : \|w\| \leq C\}$ of bounded linear predictors. I am ...
- 123
3
votes
1
answer
166
views
Sample complexity lower bound to learn the mode (the value with the highest probability) of a distribution with finite support
Say we have a black-box access to a distribution $\mathcal{D}$ with finite support $\{1,2,...,n\}$ with probability mass function $i \mapsto p_i$. How many samples of $\mathcal{D}$ are needed to learn ...
- 33
6
votes
1
answer
215
views
Lower bound for the OR problem
Let us have booleans $x_1, \cdots, x_n$. Any algorithm that determines $\bigvee_1^n x_i$ with probability at least $2/3$ requires $\Omega(n)$ time. It is not too difficult to prove this, but the proof ...
- 600
0
votes
0
answers
46
views
understanding generalized coupon collector for distributions or learning mixture of distribution
Lets suppose we have a set $S=\{1,\ldots,n\}$ and $P$ is the uniform distribution over two subsets $T_1,T_2\subseteq S$, each of size $m\leq n/100$. Now, suppose somehow is given uniform samples from ...
- 251
3
votes
0
answers
228
views
Understanding Dudley Chaining Argument for Rademacher Bound
I follow the proof of the Dudley chaining/metric entropy bound of the (empirical) Rademacher complexity, but I don't have any intuition for why this bound should be true. In particular, I don't know ...
- 131
5
votes
1
answer
234
views
Qubit gates in google supremacy
The gates in quantum supremacy experiment are nearest-neighbor and have spatial locality. Would this additional information help bolster IBM's argument to perhaps simulate quantum supremacy experiment ...
- 529
0
votes
0
answers
79
views
representation of concept classes and pac learning
I was reading the book of Kearns and Vazirani and I didn't completely understand the following:
Let C be a concept class and suppose we want to PAC learn C, they say first consider a larger ...
- 251
2
votes
1
answer
174
views
How many samples are needed to reconstruct a path?
Consider an input set of vertices $V$ and vertices $s,t\in V$.
The goal is to learn some unknown shortest path from $s$ to $t$; the set of edges of the graph is hidden at first and there may be ...
- 9,368
7
votes
1
answer
233
views
Sampling monotone Boolean functions
I'm interested in sampling monotone increasing Boolean functions on $n$ input bits uniformly at random. I understand that this is equivalent to approximating the Dedekind numbers ($D_n = $ the number ...
- 1,562
10
votes
3
answers
584
views
Is uniform convergence faster for low-entropy distributions?
Let $\mathcal D$ be a probability distribution on $\{0,1\}^d$. Let $X_1, \cdots, X_n \in \{0,1\}^d$ be i.i.d. samples from $\mathcal D$. Let $\mu \in [0,1]^d$ be the mean of $\mathcal D$ and let $\...
- 2,793
2
votes
1
answer
133
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 $...
- 21
2
votes
1
answer
128
views
Sample complexity for learning Boltzmann Distribution parameters
I am trying to think through the number of samples that I would need to estimate the parameters of a Boltzmann partition function to a desirable precision.
Suppose that there are $N$ possible states ...
- 607
8
votes
0
answers
254
views
How to sample a lot of independent uniform spanning trees?
There are a bunch of good algorithms for sampling a uniform spanning tree from a graph $G$. For example, Aldous/Broder and Wilson's algorithm are pretty efficient. However, each of these graphs only ...
- 1,439
1
vote
0
answers
75
views
Complexity of Proportional Sampling
Let $p_1,...,p_n$ be a list of numbers, each specified by $n^{O(1)}$ bits. Let $\mu = \sum_{i} p_i$ be the sum of all numbers in the list. I want to sample from the set $\{1,...,n\}$ where each $j$ is ...
- 1,062
4
votes
0
answers
96
views
Sampling Functions Efficiently vs Pseudorandom Generators
Let $X$ be a set of $n$-bit Boolean functions of the form $f:\{0,1\}^n\rightarrow \{0,1\}$. For instance, $X$ could be the set of $n$-bit monotone Boolean functions, or the set of $n$-bit functions ...
- 1,062
4
votes
1
answer
196
views
How well do subspaces hit sets
Let $S\subset F_2^n$ be a subset of size $\epsilon\cdot 2^n$.
Say I choose a random subspace $V$ of dimension $k$ in $F_2^n$.
I want to know what is the smallest $k$ such that $V$ `hits' $S$, i.e., $V\...
- 209
2
votes
0
answers
167
views
About lower bounding the sample complexity of a distribution
Given a joint probability distribution over a finite number of random variables (each with a finite range space) of which only a certain subset is observable, is there a notion of "sample complexity" ...
- 644
1
vote
0
answers
254
views
How does one sample uniformly at random from an uncountably infinite set?
I want to know if there are any examples of polynomial time algorithms which can sample uniformly at random from a given uncountably infinite set? (assuming it is possible)
Does it help if the sample ...
- 644
2
votes
2
answers
374
views
Coreset and VC dimension
I am trying to understand the notion of $\epsilon$-coreset and its relation with sampling bounds of a range space having a finite VC-dimension. Although both of them give an $\epsilon$-approximation ...
- 629
2
votes
1
answer
247
views
Evaluating the expected value of negatively correlated random variables
A polynomial random process satisfying the following properties converts a fractional point $(x_1, x_2, \ldots, x_n) \in \mathcal{P}$, $(x_i \in [0,1])$ to a random integer point $(X_1, X_2, \ldots, ...
- 93
4
votes
1
answer
860
views
Sample complexity of distinguishing two Gaussian distributions?
Below is a description of the problem:
Suppose I have two $p$-dimensional Gaussian distributions with the same covariance matrix $\Sigma$ and means $\mu_1$, $\mu_0$.
And I can get $n$ samples $X_1^{(...
- 339
3
votes
1
answer
194
views
Almost uniform sampling implies approximate counting
I began studying papers about approximate counting and I keep seeing the above being quoted, without further explanation. I suppose the procedure that yields the result is very well known and that is ...
- 447
2
votes
1
answer
225
views
Determining the number of clusters using property testing algorithm
We say a set of $n$ points in $R^d$ are $k$-clusterable, if all points are covered by k unit balls. We have a property testing algorithm (see section 5 of paper) which consider a promise version of ...
- 629
2
votes
1
answer
102
views
Approximating the value of k in $k$-mean clustering problem
Consider a set of $n$ points in $R^d$ which are covered by some finitely many (say $k$) unit balls. Can we approximate the value of $k$ by querying only sublinear many points. More precisely, by ...
- 629
11
votes
1
answer
275
views
Given $f:\{0,1\}^n \rightarrow \{-1,1\}$, find a subcube with large volume and large average value
Here is a problem with a similar flavor to learning juntas:
Input: A function $f: \{0,1\}^n \rightarrow \{-1,1\}$, represented by a membership oracle, i.e. an oracle that given $x$, returns $f(x)$.
...
- 1,101
24
votes
1
answer
497
views
Sampling satisfiable 3-SAT formulas
Consider the following computational task: We want to sample a 3-SAT formula of $n$ variables (a variant: $n$ variables $m$ clauses) with respect to the uniform probability distribution, conditioned ...
- 5,973
1
vote
2
answers
392
views
algorithms to split data into roughly equal sized quantiles
What is the state-of-the art on algorithms that calculate/estimate approximate quantiles?
I don't even worry about errors in terms of the value of quantiles (here meaning the cutoff) but having ...
- 111
17
votes
1
answer
1k
views
The complexity of sampling (approximately) the Fourier transform of a Boolean function
One thing that quantum computers can do (possibly even with just BPP + log-depth quantum circuits) is to approximate-sample the Fourier transform of a Boolean $\pm 1$-valued function in P.
Here and ...
- 5,973
5
votes
1
answer
318
views
VC-Dimension and sample complexity dependent on size of subsets
I have a range space $(X,R)$, were $R$ is a collection of subsets of $R$ and I have an upper bound $d$ to the VC-dimension of $(X,R)$. Suppose for simplicity that $X$ is finite. Given $\delta\in(0,1)$ ...
- 569
9
votes
1
answer
416
views
What is the proper role of verification in quantum sampling, simulation, and extended-Church-Turing (E-C-T) testing?
Since no answer was given, a flag has been set requesting that this question be converted to a community wiki.
The comments by Aaron Sterling, Sasho Nikolov, and Vor have been synthesized into the ...
6
votes
1
answer
631
views
Efficiently Samplable Distributions
What does it mean for a distribution to be efficiently samplable?
This came up in the discussions about the distributions used in the recent attempted P!=NP proof.
The context was that a ...
- 161
12
votes
2
answers
385
views
Computational query complexity of SQ-learning
It is known that for PAC learning, there are natural concept classes (e.g. subsets of decision lists) for which there are polynomial gaps between the sample complexity needed for information theoretic ...
- 9,820