Questions tagged [pac-learning]
The pac-learning tag has no usage guidance.
57 questions
0
votes
0
answers
25
views
Agnostic PAC learning - equivalent definitions?
Learning model:
Domain set: $\mathcal{X}$,
Label set: $\{0,1\}$,
Hypothesis class: a set $\mathcal{H}$ of binary hypotheses $h:\mathcal{X}\to\{0,1\}$
Data-labels generating distribution: $\mathcal{D}$...
- 1
0
votes
0
answers
54
views
Reference for lower bound for realizable PAC learning sample complexity?
Suppose $\mathcal{F} \subset \{0, 1\}^\mathcal{X}$ be a class of functions and denote by $D_m(f) := \{(X_i, f(X_i))\}_{i=1}^m$ a dataset. Here, $X_i$ are iid samples from distribution $P$ on $\mathcal{...
- 213
0
votes
0
answers
56
views
Necessary and sufficient condition for distribution dependent agnostic learning
A long time ago, it was shown (Benddek 1991 [1]) that a necessary and sufficient condition for agnostic learning in the distribution-dependent setting is a finite cover.
Later, Max Hopkins [2] showed ...
- 122
0
votes
0
answers
19
views
Is there any relation between the size of optimal $\epsilon$-nets and the sample complexity for getting one through IID samples?
A combinatorial $\epsilon$-net is defined as follows:
Let $(X, \mathcal{R})$ be a range space, and let $A \subseteq X$ be a finite subset of $X$. A set $N \subseteq A$ is a combinatorial $\varepsilon$-...
- 716
1
vote
0
answers
32
views
PAC-learning description of (quantum) hypothesis class containing randomness
I was wondering how to correctly describe the following hypothesis class mathematically correctly:
Say I have a quantum circuit which I postprocess by feeding its results into a neural network. How ...
- 11
0
votes
0
answers
36
views
Is there an interpretation of efficiency in learning theory in terms of where the probability mass is concentrated?
Let $\mathcal{X}$ denotes the input space of dimension $n$, $\mathcal{Y}$ denotes the codomain.
In PAC learning with realizability assumption, we assume randomness over covariates $\mathcal{D}_{\...
- 122
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
1
answer
132
views
Confusion about lower bounds and upper bounds in learning theory
In computer science, lower bounds and upper bounds are defined as follow:
$$m \geq g(n) \implies m = \Omega(g(n))$$
$$m \leq g(n) \implies m = \mathcal{O}(g(n))$$
However, in proving lower bounds and ...
- 65
2
votes
2
answers
107
views
Learning with zero inductive bias
I want to understand the intuition behind the classic setting of learning theory, we always assume that the model belongs to some known class. Was there a formal proof that we can or can not learn a ...
- 65
1
vote
0
answers
46
views
Why the measure of information complexities for passive and active learning are increasing in research communities?
I am a PhD student working on the theory of active learning.
Over the years, accepted papers in COLT and ALT for active learning are focused on approaches that almost all of them define new ...
- 122
-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 ...
2
votes
0
answers
205
views
Does PAC learnable imply agnostic PAC learnable for binary classification tasks?
The Fundamental Theorem of Statistical Learning from the book "Shai et al., Understanding Machine Learning: From Theory to Algorithms, Cambridge Press University", is written as follows:
...
- 131
0
votes
0
answers
61
views
Learning a PAC-lernable using agnostic-PAC framework
given H a family of functions which is PAC lernable such that for $\epsilon$ error and $\delta $ confidence interval it required $m(\epsilon,\delta)$ samples.
I understood that if we learn H under ...
1
vote
0
answers
128
views
Proving existence of efficient PAC learning algorithm without noise info given poly-time algorithm with noise upper bound
How would I prove that if there is an efficient algorithm for PAC learning in the presence of classification noise by an algorithm that is given a noise rate upper bound $\eta_0$ ($1/2 > \eta_0 \...
- 111
0
votes
1
answer
44
views
Differing definitions of a weak learner
I've been reading about boosting and have come across basically two definitions of a weak learner. Basically for hypothesis $h$ and target $c$, some definitions says that $h$ is a weak learner if $E[h(...
- 1
0
votes
1
answer
159
views
PAC learning over continuous functions
I'm wondering if it's possible to use PAC learning to learn a continuous function. For example, if we wanted to learn a probability distribution or a CDF, is it valid to train on some set of m ...
- 1
2
votes
0
answers
67
views
Learning boolean functions with input-ouput examples and side-information
The Kushilevitz-Mansour, "low-degree", and Goldreich-Levin algorithms aim to learn a function $f: \{0,1\}^n \rightarrow \{0,1\}$ from a sufficiently large set of input-output examples $(x_i, ...
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
2
votes
1
answer
272
views
Fat Shattering / VC dimension / Statistical Complexity of piecewise linear functions
I am trying to establish a bound on the VC dimension of piecewise linear continuous functions with $k$ pieces. I am aware of an earlier question which tackles this problem in the case of convex ...
- 123
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
2
votes
1
answer
453
views
VC dimension of the class of all polygons with k vertices
VC dimension of the class of convex polygons with $ k $ vertices is known to be $ 2k + 1$.
For the general case I was able to derive a bound of the type $ O(k^2log(k)) $ (probably can be easily ...
- 201
-1
votes
1
answer
304
views
Non-(PAC)-Learnable Classes
I'm learning about PAC-learnability. I've figured out how to show that a class of classifiers is PAC-learnable, but what about if I want to show that a class of classifiers is not PAC-learnable? How ...
- 1
2
votes
2
answers
515
views
Some issues with proof of Fundamental Theorem of Statistical learning
I am reading the book "Understanding Machine Learning" by Shai Shalev-Shwartz and Shai Ben-David.
The theorem 6.7 has several equivalent statements for a class of functions $H$. The first ...
- 123
0
votes
2
answers
169
views
An (unusual?) risk bound
I am told that that a bound on the generalization error of the following form exists in terms of something called the ``shattering coefficient" - but I am not able to reference this quantity in ...
- 1,453
1
vote
1
answer
280
views
Generalization bound for parameters rather than loss functions
I was wondering if it is possible to obtain high probability bounds (provided finite sample size of the training data) for the distance (say in the l-1 or l-2 norm) between the best parameter set and ...
- 11
-1
votes
1
answer
184
views
No free lunch theorem and finite hypothesis classes
I have read the no free lunch theorem(NFLT) section 5.1 of Understanding machine learning by Shai Shalev-Shwartz. There is also this Corollary 4.6 which states any finite hypothesis class is PAC ...
- 99
0
votes
1
answer
165
views
Generalisations of the Fundamental Theorem of Statistical Learning to different tasks and losses
The fundamental theorem of statistical learning gives an equivalence between uniform convergence of the empirical risk to learning in the PAC framework.
I have only seen this stated in the case of ...
- 131
0
votes
0
answers
64
views
Is statistical query learning equivalent to correlational statistical query learning given a fixed distribution?
As title, I saw some paper mentioned they are equivalent, but I'd wonder how to prove they are? is it something to do with PAC as SQ is a restricted version of PAC?
- 1
4
votes
0
answers
107
views
Logic of learning
Does Robust logic (Leslie Valiant), Default logic (Raymond Reiter) and Circumscription logic (John McCarthy) have any relation?
I was Mathematician and Computer Science (dual degree undergraduate) ...
1
vote
0
answers
56
views
Is there a notion of Probably Approximately Correctness in Unsupervised Learning? [closed]
I've been learning a little bit about computational learning theory, but most of what I've seen so far is related to supervised learning. Perhaps dimensionality reduction will be touched on, but not ...
- 111
2
votes
1
answer
312
views
Why non-uniform learnability does not imply PAC learnability?
PAC guarantees provide us a a learning algorithm $A_n(\cdot)$ and sample complexity bound $n_{\mathcal{F}}(\epsilon,\sigma)$ that ensures
$
P\left[L_P(A(\mathcal{D}^n))-L_P(f^*)\leq \epsilon\right]\...
5
votes
0
answers
149
views
Status of the Junta Problem (soft question)
Does the learning theory community in general believe that juntas can be learned in polynomial time?
The naive algorithm works in quasi-polynomial time. MOS's paper shows how to solve the junta ...
- 307
5
votes
1
answer
213
views
Latest word on cross validation?
It's a standard result leave-one-out cross-validation is an unbiased estimator of the risk (see, e.g., Lemma 4.1 in Mohri, Rostamizadeh, Talwalkar). Are there any "better" results? Such as, say, with ...
- 10.6k
4
votes
1
answer
284
views
Is this a known learning problem?
Let $(\mathcal{X},\rho)$ be a metric space (say, $\mathcal{X}=[0,1]$ with the Euclidean metric). Let $\alpha:\mathcal{X}\to[0,1]$ be unknown. Suppose that $\mathcal{X}$ is endowed with a distribution $...
- 10.6k
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
1
vote
0
answers
93
views
Agnostic query learning of decision trees
Gopalan, Kalai, Klivans gave an algorithm
https://dl.acm.org/citation.cfm?id=1374376.1374451
for agnostically learning decision trees $h:\{0,1\}^n\to\{0,1\}$ under the uniform distribution given ...
- 10.6k
0
votes
1
answer
161
views
Lower bound of real valued bounded function
Is well known that the lower bound on number of example necessary to reach a given error for concept classes $\Omega(d/\varepsilon)$ (cf. also
Agnostic PAC sampling lower bound
)
I am looking for the ...
4
votes
2
answers
185
views
Are there hypothesis classes that are hard to learn but easy to test?
Let $H$ be a binary hypothesis class, it is easy to see that if $H$ is (efficiently) properly PAC learnable then it is also (efficiently) testable (here we use the standard notion of within or $\...
- 271
7
votes
2
answers
315
views
About assumptions needed to get convergence of stochastic gradient methods on non-convex objectives
What are the minimal conditions we know of under which we can prove that a stochastic gradient based algorithm can convergence to criticality on a non-convex objective?
Are there any necessary ...
- 1,453
2
votes
0
answers
105
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 ...
- 10.6k
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
1
answer
507
views
Difficulty of "learning" rare instances
Is there any result showing that models (say SVM, Neural-Net, kNN, etc) will have difficulty in learning "rare" instances/tail phenomena?
- 749
1
vote
0
answers
69
views
Learnability of under some characteristics of the distribution
TLDR; is there any results showing that more concentrated (or easier) distributions are easier to learn?
In PAC-learning, the guarantee is given for any underlying distributions. But in reality, we ...
- 749
3
votes
2
answers
962
views
PAC-learning bound with epsilon-cover of hypothesis class
In this video at 43:00, a version of the PAC bound for generalization error $\epsilon$, which I hadn't seen before, is quoted:
$$\epsilon^2 < \frac{\log{|H_\epsilon|} + \log{1/\delta}}{2m}$$
...
- 133
3
votes
1
answer
540
views
Rademacher complexity beyond the agnostic setting
The way I know of to bound generalization error by Rademacher complexity is Theorem 2.4 in this lecture notes, http://ttic.uchicago.edu/~tewari/lectures/lecture9.pdf. Here the quantity on the LHS that ...
- 1,453
1
vote
0
answers
86
views
Reference request for the relationship between approximating degree of Boolean functions and learning algorithms
This paper (http://www.cs.columbia.edu/~rocco/Public/stoc01.pdf) from STOC 2001 is possibly the first paper to show how to convert upperbounds on the $\frac{1}{3}-$approximation degree of a Boolean ...
- 1,453
11
votes
3
answers
2k
views
Proper PAC learning VC dimension bounds
It is well known that for a concept class $\mathcal{C}$ with VC dimension $d$, it suffices to obtain $O\left(\frac{d}{\varepsilon}\log\frac{1}{\varepsilon}\right)$ labelled examples to PAC learn $\...
- 251
4
votes
1
answer
1k
views
Rademacher complexity and lowerbounds in learning theory
Is there any function class known whose Rademacher complexity has a non-trivial lowerbound?
Can the Rademacher complexity be used to lowerbound the generalization error in any learning situation?
- 1,453
1
vote
0
answers
202
views
Boolean functions with high query complexity for PAC learning
The most general theorem for PAC learning of Boolean functions that I am aware of is the theorem in section 3.4 of Ryan O'Donnel's book where its basically shown that Boolean functions whose Fourier ...
- 1,453