The 2024 Developer Survey results are live! See the results

# Questions tagged [pac-learning]

For questions related to Probably Approximately Correct (PAC) learning, a framework for mathematical analysis of machine learning algorithms, which was introduced in the paper "A Theory of the Learnable" (1984) by Leslie G. Valiant.

17 questions
Filter by
Sorted by
Tagged with
16 views

### Showing Axis-Aligned Rectangles With Noise Are PAC-Learnable (FML, Problem 2.6)

I asked the following in Math Stack Exchange and was told "You may be more likely to get an answer on stats.stackexchange.com". I figured this is a more suitable place. In what follows, an ...
1 vote
47 views

### Using the definition of APAC learning and uniform convergence in practice

I am currently studying "Understanding Machine Learning from Theory to Practice" written by Shai Shalev-Shwartz and Shai Ben-David. I want to understand how i can use the Definitions and ...
1 vote
84 views

### Where can I find the solutions to the problems in the book "An Introduction to Computational Learning Theory"?

I have been going through "An Introduction to Computational Learning Theory" (Kearns-Vazirani). I don't know if my solutions to the problems are correct and have no other way of checking my ...
• 111
1 vote
183 views

### What is the relevance of the concept size to the time constraints in PAC learning?

My question is about the relevance of concept size to the polynomial-time/example constraints in efficient PAC-learning. To ask my question precisely I must first give some definitions. Definitions: ...
• 19
1 vote
21 views

### Characterize the high probability bound for learning algorithm

Suppose we have a dataset $S = (x_1, \dots x_n)$ drawn i.i.d from distribution $D$, a learning algorithm $A$ and error function $err$. The performance of $A$ is therefore defined by the error/...
• 111
1 vote
62 views

### What is the expectation of an empirical model in model based RL?

In the paper - "Action Elimination and Stopping Conditions for the Multi-Armed Bandit and Reinforcement Learning Problems", on page 1083, on the 6th line from the bottom, the authors define ...
• 78
703 views

### Is there any practical application of knowing whether a concept class is PAC-learnable?

A concept class $C$ is PAC-learnable if there exists an algorithm that can output a hypothesis with probability at least $(1-\delta)$ (the "probably" part), and an error that is less than $\epsilon$ (...
• 1,281
129 views

### What is the relationship between PAC learning and classic parameter estimation theorems?

What are the differences and similarities between PAC learning and classic parameter estimation theorems (e.g. consistency results when estimating parameters, e.g. with MLE)?
• 853
283 views

### Is there a notion of generalization in unsupervised learning?

I've been learning a little bit about generalization theory, and in particular, the PAC (and PAC-Bayes) approach to thinking about this problem. So, I started to wonder if there is an analogous ...
• 133
3k views

### What are some resources on computational learning theory?

Pretty soon I will be finishing up Understanding Machine Learning: From Theory to Algorithms by Shai Ben-David and Shai Shalev-Shwartz. I absolutely love the subject and want to learn more, the only ...
• 258
1k views

### Are PAC learnability and the No Free Lunch theorem contradictory?

I am reading the Understanding Machine Learning book by Shalev-Shwartz and Ben-David and based on the definitions of PAC learnability and No Free Lunch Theorem, and my understanding of them it seems ...
991 views

### A problem about the relation between 1-oracle and 2-oracle PAC model

This problem is about two-oracle variant of the PAC model. Assume that positive and negative examples are now drawn from two separate distributions $\mathcal{D}_{+}$ and $\mathcal{D}_{-} .$ For an ...
• 181