# Questions tagged [pac-learning]

PAC is Probably Approximately Correct learning

57 questions
Filter by
Sorted by
Tagged with
52 views

70 views

### Hypothesis class with n elements that shatters a set C of n/2 points

I started learning Advanced Machine Learning and came across a problem that stuck. I would be grateful if you could help me with some ideas or solutions: What is the maximum value of the natural even ...
1 vote
54 views

### What makes an algorithm a PAC learner?

I am new to Machine Learning theory and some of the topics are not very intuitive to me. I don't quite understand how the sample complexity in PAC theorem depends only on the concept class. As we see ...
67 views

### Can weak-learner be defined in the case of regression problem?

weak-learner is often defined relating to PAC learning. However, to the extent I know, I have never seen the definition of weak-learner when regression. That is, the definition of weak-learner on ...
24 views

### Characterizations of uniformly learnable function classes in the distribution-specific setting

Let $X$ be some input domain (a measurable space). Then let $D$ be some class of probability distributions on $X\times\{0,1\}$. We will call such distributions learning tasks. We say that $D$ is ...
10 views

1 vote
84 views

### Has Fundamental Theorem of Statistical Learning been proven for infinite classes of functions?

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 ...
512 views

### What is an "ERM rule" in Understanding Machine Learning by Shai Shalev-Shwartz et al.?

I am reading "Understanding Machine Learning" book by Shalev-Shwartz, Ben David. On the page 48, the theorem 6.7 (The fundamental theorem of statistical learning, FTSL) says: Let $H$ be a ...
1 vote
359 views

### VC-Dimension of Axis-Aligned Right Triangles and 5-point Convex Hull

I am having trouble proving the following fact about the VC dimension of triangles. Consider axis-aligned right triangles in the plane, with the the right angle in the lower left corner. The ...
1 vote
120 views

### how is the expectation of the empirical error based on an i.i.d. sample S is equal to the generalization error?

I am on the 28 page of the book called "foundations of machine learning" by M.Mohri which states that for a fixed hypothesis h,the expected value of the empirical error is equal to ...
153 views

### what's the difference between hypothesis function outputed by algorithm A and polynomial function in the book,"foundations of machine learning"

I am on the 28 page of the book called "foundations of machine learning" by M.Mohri which contains this(in the iamge below) defination of the PAC learning framework.I am a bit coufused about ...
1 vote
158 views

### Why sample complexity must be polynomial for PAC learning?

I'm reading up on Probably Approximately Correct (PAC) learning and most sources require that the sample complexity must be polynomial in $\frac{1}{\epsilon}$ and $\frac{1}{\delta}$, where ${\epsilon}$...
88 views

### Does majority-vote boost weak learners to strong learners?

A learner is a function mapping finite vectors with elements in $X\times\{0, 1\}$ onto binary functions on $X$. Given a set $H$ of binary functions on $X$, we say that: A learner $(\delta, \epsilon)$-...
101 views

### How are bias and variance related to overfitting and model capacity?

Many people use the MSE decomposition to illustrate bias and variance. However, is there any statistical learning theory connecting these concepts? Namely, is there a formula calculating model ...
186 views

### Does a generalization bound that holds with high probability imply a bound that holds in expectation?

I am interested in generalization bounds, for example PAC bounds (Probably Approximately Correct). In particular, I wonder if a high probability bound implies a bound in expectation (or vice versa). ...
1 vote
86 views

### PAC Learnability of axis aligned squares

Ok, so I already know how the pac learnability of an axis aligned rectangle is demonstrated, that is we fix some distribution $D$ over $X$, define $R^* = R_{(a_1^*, b_1^*, a_2^*, b_2^*)}$ the ...
124 views

### PAC Learning for OLS and noisy regression

Hi guys I would like to get some references on PAC Learning for the following settings: PAC Learning type results for OLS. Most materials that tackle OLS are from a statistical point of view, i.e. ...
1k views

### What is Massart Noise?

One of best papers during NeurIPS 2019 - Distribution-Independent PAC Learning of Halfspaces with Massart Noise mentions Massart Noise in the title. What is this type of noise? How is it different ...
1 vote
175 views

1 vote
480 views

### Prove PAC Learnable [closed]

How can I prove that a hypothesis space is PAC learnable? The setup for this is X which is a discrete instance space. H is a set of hypotheses over X. H contains all singleton functions as well as ...
800 views

### What is the utility/significance of PAC learnability and VC dimension?

I've been reading Shalev-Shwartz & Ben-David's book, "Understanding Machine Learning", which presents the PAC theory in its Part I. While the theory of PAC learnability does appear very elegant ...
365 views

### Why noisy data will benefit Bayesian?

Recently I am reading a paper in 2001, Michael D. Ernst, Jake Cockrell, William G. Griswold, David Notkin Dynamically Discovering Likely Program Invariants to Support Program Evolution TSE 2001, in ...
1 vote
127 views

### PAC learnability of real valued function w.r.t. zero loss function

The necessary and sufficient conditions for learning to occur in the task of binary classification are among the fundamental results in learning theory. In the sources I'm familiar with, this theorem ...
214 views

### What characterizes a function that is easy to learn?

When performing machine learning, the performance of the machine learning method is dependent on the original function $f$ that we are trying to learn (let's forget for a moment the non-deterministic ...
2k views

### Complex analysis, Functional analysis for deeper understanding Machine Learning

I want to get deeper into the Machine Learning(theory and application in Finance). I want to ask how relevant are complex analysis and functional analysis as a basis for Machine Learning? Do I need to ...
163 views

### Is machine learning only about estimating programs? [closed]

Q: Can we say that all of machine learning is, essentially, only about finding good estimations of programs? If not, is there any example of a machine learning problem that is not about finding ...
361 views

### What is the PAC function of an AR(2)?

What is the PACF(1) of the following AR(2) process? $y_t = \phi y_{t-2}+\epsilon_t$ with $\epsilon_t \sim WN(0, \sigma^2)$
2k views

### Best approaches for feature engineering?

I have a regression problem. The aim is to estimate the best fitting curve from a set of features. Now I have extracted a set of features that are relevant based on the literatures found. Now the ...
1 vote
667 views

### An example for a finite hypothesis class which is not PAC learnable?

Finite hypothesis class with bounded loss function are PAC learnable. Are there examples for finite hypothesis classes in the case of unbounded loss function, which aren't PAC learnable?
10k views

### Introduction to machine learning for mathematicians

In some sense this is a crosspost of mine from math.stackexchange, and I have the feeling that this site might provide a broad audience. I am looking for a mathematical introduction to machine ...
26k views

### What does PAC learning theory mean?

I am new in machine learning. I am studying a course in machine learning (Stanford University ) and I did not understand what is meant by this theory and what is its utility. I am wondering if someone ...
1 vote
234 views

### Sample complexity for agnostic PAC learning for real valued functions

How many samples are needed for ERM to have $\epsilon$ excess risk relative to the best hypthosis $h^*$? Assume a bounded (and Lipschitz, if needed) loss function. The only survey I have been able to ...
581 views

### Rademacher bounds for unbounded loss functions

All common treatment of PAC bounds based on Rademacher complexity assume a bounded loss function (for a self-contained treatemnt, see this handout by Schapire. However, I could not find any result for ...
267 views

### Is "not-overfitting" a utopian scenario?

We say a model overfits when classification error increases on the test data. The reason behind this is that the training data is not a representative of the distribution from which data is sampled. ...
1 vote