Questions tagged [sample-complexity]
The sample-complexity tag has no summary.
44 questions
1
vote
0
answers
16
views
Does nonnegativity improve sample complexity for linear classifiers?
Suppose we have data $x_i \sim Normal(0, I_d)$ (i.e. zero mean, unit variance, independent features) and labels $y_i \in {0,1}$, and we are interested in training a linear classifier $f(x) = w^\top x +...
- 11
0
votes
0
answers
23
views
Impact of sample and concept size on reductions to proper PAC learning hardness
In standard hardness proofs showing that proper PAC learning of certain concept classes is not possible unless RP=NP, one reduces an NP-complete decision problem (e.g., Graph 3-Coloring) to the ...
1
vote
1
answer
100
views
Does consistency + poly-time + finite VC-dimension imply PAC learning?
Suppose I have a hypothesis class $\mathcal{H}$ with finite and small VC-dimension.
Also, assume I have a learning algorithm $A$ that, given any labeled sample, produces in polynomial time a ...
0
votes
0
answers
42
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
68
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
55
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
62
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
71
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
199
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
88
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
114
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
113
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
48
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
262
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
267
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