Questions tagged [pac-learning]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
105 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 ...
rivana's user avatar
  • 53
2 votes
2 answers
81 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 ...
rivana's user avatar
  • 53
0 votes
0 answers
16 views

What is the condition under which the estimation error increases (logarithmically) with hypothesis class size for a finite hypothesis class

In section 5.2 error decomposition (p.404) from the online book "Shai et al., Understanding Machine Learning: From Theory to Applications", the authors wrote: As we have shown, for a finite ...
Tran Khanh's user avatar
1 vote
0 answers
40 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 ...
Ayoubayjx's user avatar
  • 122
-1 votes
1 answer
62 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 ...
Sathishkumar Thirumalai's user avatar
2 votes
0 answers
55 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: ...
Tran Khanh's user avatar
0 votes
0 answers
67 views

The hardness of active learning with fixed budget

I have been looking for theoretical papers studying this question of the hardness of PAC active learning algorithms. I found a few papers studying the problem from a fixed perspective (particular ...
rivana's user avatar
  • 53
0 votes
0 answers
51 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 ...
Tomer Gigi's user avatar
1 vote
0 answers
67 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 \...
aome's user avatar
  • 111
0 votes
0 answers
32 views

PAC learning in the convex case with bounded expected risk

In the context of computational learning theory: Let $f(w,z): \mathcal{W} \rightarrow \mathbb{R}$ be convex in $w \in \mathcal{W}$ where $\mathcal{W}$ bounded by R. Over $\mathcal{W}$, $|f| \leq C$. ...
Yakov Dan's user avatar
  • 101
0 votes
1 answer
43 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(...
qc6518's user avatar
  • 1
0 votes
1 answer
105 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 ...
qc6518's user avatar
  • 1
2 votes
0 answers
58 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, ...
Tom Shrimpton's user avatar
1 vote
0 answers
67 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 (...
student3365's user avatar
2 votes
1 answer
157 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 ...
Nick Bishop's user avatar
0 votes
0 answers
39 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 ...
Nick Bishop's user avatar
2 votes
1 answer
234 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 ...
Popescu Claudiu's user avatar
-1 votes
1 answer
170 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 ...
M. Fire's user avatar
2 votes
2 answers
439 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 ...
Marina's user avatar
  • 123
0 votes
2 answers
161 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 ...
gradstudent's user avatar
  • 1,443
1 vote
1 answer
206 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 ...
kd212149's user avatar
-1 votes
1 answer
145 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 ...
KFkf's user avatar
  • 99
0 votes
1 answer
148 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 ...
user27182's user avatar
  • 131
0 votes
0 answers
56 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?
Yo Ruson's user avatar
4 votes
0 answers
105 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) ...
Mahdi Heidarpoor's user avatar
1 vote
0 answers
53 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 ...
Marcel's user avatar
  • 111
2 votes
1 answer
233 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]\...
CrispyMcDiarmid's user avatar
4 votes
0 answers
124 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 ...
zfkmz's user avatar
  • 187
5 votes
1 answer
210 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 ...
Aryeh's user avatar
  • 10.3k
4 votes
1 answer
283 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 $...
Aryeh's user avatar
  • 10.3k
0 votes
0 answers
81 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 ...
Annonymous's user avatar
1 vote
0 answers
91 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 ...
Aryeh's user avatar
  • 10.3k
0 votes
1 answer
157 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 ...
Dr.Raghnar's user avatar
4 votes
2 answers
181 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 $\...
Paul's user avatar
  • 271
7 votes
2 answers
283 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 ...
gradstudent's user avatar
  • 1,443
2 votes
0 answers
103 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 ...
Aryeh's user avatar
  • 10.3k
2 votes
1 answer
135 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 $...
Lemke's user avatar
  • 21
2 votes
1 answer
139 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 ...
Asterix's user avatar
  • 617
8 votes
1 answer
501 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?
Daniel's user avatar
  • 749
1 vote
0 answers
68 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 ...
Daniel's user avatar
  • 749
3 votes
2 answers
791 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}$$ ...
guillefix's user avatar
  • 133
3 votes
1 answer
451 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 ...
gradstudent's user avatar
  • 1,443
1 vote
0 answers
85 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 ...
gradstudent's user avatar
  • 1,443
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 $\...
Annonymous's user avatar
4 votes
1 answer
852 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?
gradstudent's user avatar
  • 1,443
1 vote
0 answers
174 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 ...
gradstudent's user avatar
  • 1,443
2 votes
1 answer
164 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 ...
Kyoungjae Lee's user avatar
1 vote
1 answer
181 views

Does MCMC belong to the statistical query model?

It is known that a wide range of algorithms fall into the statistical query (SQ) learning model by Michael Kearns. Examples include k-means, logistic regression, naive Bayes (NB), SVM, ICA, PCA, ...
Minkov's user avatar
  • 832
5 votes
0 answers
173 views

The Complexity of Properly Learning Decision Trees

Where does this paper prove the middle bullet point of its abstract? I have looked through that paper fairly thoroughly. There are three things I want to read how they're getting around. Reductions ...
user avatar
6 votes
0 answers
199 views

Learning read-once branching programs with membership queries

Let $B=\{0,1\}$. A read-once branching program of width $n$ and size $w$ is given by a graph with layers $0,\ldots, n$, where the first layer has just the starting node, the last layer has nodes ...
Holden Lee's user avatar