Questions tagged [sample-complexity]
The sample-complexity tag has no usage guidance.
42 questions
0
votes
0
answers
24
views
Sample complexity of covariance matrix estimation of a Gaussian random variable (with explicit constants)
I'm seeking an explicit bound for the number of samples required to estimate the covariance matrix of a Gaussian distribution. In https://arxiv.org/pdf/1011.3027v7 (end of page 31), the following ...
0
votes
0
answers
25
views
Is there a relation between packing number and disagreement coefficient in the active learning setting?
This is a question for active learning experts: Let $\mathcal{X}$ be the input space equipped with a distribution $\mathcal{D}$ and let $\mathcal{H}$ be a hypothesis class, $h \in \mathcal{H}$ our ...
- 65
0
votes
0
answers
57
views
Is it possible to estimate the positive outcomes of a boolean function using an optimized version of Goldreich-Levin?
Let $\mathcal{X} = \{-1,1\}^n$ and $h: \mathcal{X} \to \{-1,1\}$, h can be expanded in the basis of monomials for the uniform distribution, or also can have a distribution free expansion (Gram-Schmidt ...
- 65
2
votes
0
answers
44
views
definition of P-samplable distribution that allows non-binary fractions
Arora and Barak (in chapter 18, on average-case complexity) define a polynomial-time samplable (or P-samplable) distribution $D$ (actually a family $\{D_n\}$, for each output length $n$) as having an ...
1
vote
0
answers
54
views
what are some Lower bound for finding large fourier coefficients of boolean function (above a threshold)?
Is there some known lower bounds for estimating large fourier coefficients of boolean functions? And were there any comparison of tightness with the upper bound of Goldreich Levin algorithm?
- 65
2
votes
0
answers
57
views
Does Goldreich-Levin algorithm for finding large Fourier coefficients have time complexity upper bound = sample complexity upper bound?
I'm currently working on finding better bounds for Goldreich-Levin algorithm for estimating large Fourier coefficients of a boolean function.
I was surprised seeing that the upper bounds for time ...
- 65
-1
votes
1
answer
141
views
Unable to understand the Sample complexity of PAC learning
I have been studying from the book "Understanding Machine Learning - From Theory to Algorithms" by Shai Shalev-Shwartz and Shai Ben-David
I am struck at corollary 3.2 which states that
Every ...
1
vote
0
answers
70
views
Is there an efficient Goldreich-Levin algorithm that generalizes to agnostic PAC setting?
Goldreich Levin algorithm is an algorithm that based on some assumption (boundness on Fourier coefficients) outputs the indices for most significant Fourier coefficients of a boolean function, however ...
- 65
0
votes
0
answers
104
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
80
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
43
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
216
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
225
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 ...
- 630
0
votes
0
answers
49
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
299
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
239
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 ...
- 549
0
votes
0
answers
90
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,508
8
votes
1
answer
272
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,582
10
votes
3
answers
722
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,813
2
votes
1
answer
141
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
148
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 ...
- 627
8
votes
0
answers
294
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,479
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,072
4
votes
0
answers
97
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,072
4
votes
1
answer
201
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\...
- 289
2
votes
0
answers
187
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" ...
- 654
1
vote
0
answers
353
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 ...
- 654
2
votes
2
answers
393
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 ...
- 639
2
votes
1
answer
265
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
5
votes
1
answer
1k
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^{(...
- 349
3
votes
1
answer
212
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
237
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 ...
- 639
2
votes
1
answer
104
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 ...
- 639
11
votes
1
answer
287
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
25
votes
1
answer
524
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,793
1
vote
2
answers
440
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
18
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,793
5
votes
1
answer
344
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
422
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
728
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
408
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,910