# Questions tagged [pac-learning]

PAC is Probably Approximately Correct learning

62 questions
Filter by
Sorted by
Tagged with
8 views

### extending PAC bound result to validation set generalization error

I PAC-bound I learned consider the following decompistion: $R(f) = R_n(f) + \left(R(f) - R_n(f)\right)$ where $R(f)$ is the test error, $R_n(f)$ is the training error $\left(R(f) - R_n(f)\right)$ is ...
13 views

### Generalization bound on out of distribution data

Assume we have two sets of data $X_1$ and $X_2$ drawn from two different distributions. Are the loss of the empirical risk minimizer of $X_1$ on $X_2$: $l_{X_2}(f_{X_1})$ the same as the loss of the ...
1 vote
9 views

### Extending efficient PAC learning with classification noise to statistical query model with unlabeled random draws for axis-aligned rectangles in $R^2$

I have proven that if $C$, a concept class, is efficiently learnable from statistical queries using $H$, a representation class over $X$, then $C$ is efficiently PAC learning using $H$ in the presence ...
14 views

### Does PAC bound or MLE imply the distribution of empirical risk minimizer?

We know that PAC bounds tell us the empirical risk on training data cannot be too different from the true risk. My question is, does this result imply empirical risk minimizer also cannot be too far ...
29 views

### Could we code a program to compute VC-dimension of any given hypothesis class?

I've been studying machine learning theory and the fundamental theorem of the statistical learning for a while, but I still didn't found a general algorithm that could compute the VC dimension of any ...
99 views

### What does it mean to say in PAC learning that if the running time of the algorithm is polynomial in 1/e and 1/d, the sample size must be also poly

In the context of PAC learning, why it is true to say that if an algorithm A is a PAC-learning algorithm, then the sample size required by it must also be polynomial, i.e., how to properly interpret ...
21 views

### What is the mathematical term for a real world categorical function that yields several categories for the same inputs?

Background and Color Contextually, this is pertaining to machine learning and natural language processing. Specifically, it has to do with the labeling of real world data for partitioning by a machine ...
70 views

1 vote
100 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 ...
982 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
855 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
496 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 ...
208 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 ...
336 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}$...
147 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)$-...
191 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 ...
591 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). ...
163 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 ...
359 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 ...
663 views

1 vote
538 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 ...
971 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 ...
534 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
152 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 ...
238 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 ...
3k 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 ...
164 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 ...
439 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
696 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?