Answers.Body: <p>Yes, PAC learning can be relevant in practice. There's an area of research that combines PAC learning and Bayesian learning that is called <strong>PAC-Bayesian</strong> (or <strong>PAC-Bayes</strong>) <strong>learning</strong>, where the goal is to find PAC-like bounds for Bayesian estimators. </p>
  
  <p>For example, <strong>Theorem 1 (McAllester’s bound)</strong> of the paper <a href="https://arxiv.org/pdf/1901.05353.pdf" rel="nofollow noreferrer">A primer on PAC-Bayesian learning</a> (2019) by Benjamin Guedj, who provides a nice overview of the topic, shows a certain bound that can be used to design Bayesian estimators. An advantage of PAC-Bayes is that you get bounds on the generalization ability of the Bayesian estimator, so you do not necessarily need to test your estimator on a test dataset. Sections 5 and 6 of the paper go into the details of the real-world applications of PAC-Bayes. </p>
  
  <p>See e.g. <a href="http://jmlr.org/papers/volume16/germain15a/germain15a.pdf" rel="nofollow noreferrer">Risk Bounds for the Majority Vote: From a PAC-Bayesian
  Analysis to a Learning Algorithm</a> (2015) by P. Germain et al. for a specific application of PAC-Bayes. There's also the <a href="https://github.com/GRAAL-Research/majority-vote-bounds" rel="nofollow noreferrer">related Python implementation</a>.</p>
  
  <p>See also <a href="https://bguedj.github.io/icml2019/material/main.pdf" rel="nofollow noreferrer">these related slides</a> and <a href="https://bguedj.github.io/icml2019/index.html" rel="nofollow noreferrer">this blog post</a> (by the same author and John Shawe-Taylor) that will point you to their video tutorials about the topic.</p>
  
  <p>The VC dimension can also be useful in practice. For example, in the paper <a href="http://www.jmlr.org/papers/volume20/17-669/17-669.pdf" rel="nofollow noreferrer">Model Selection via the VC Dimension</a> (2019) M. Mpoudeu et al. describe a method for model selection based on the VC dimension.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-11T03:44:18.933Z
Answers.LastActivityDate: 2020-03-11T04:40:24.590Z
Answers.LastEditDate: 2020-03-11T04:40:24.590Z
Answers.UserDisplayName: nbro
Body: <p>Are PAC learning and VC dimension relevant to machine learning in practice? If yes, what is their practical value?</p>
  
  <p>To my understanding, there are two hits against these theories. The first is that the results all are conditioned on knowing the appropriate models to use, for example, the degree of complexity. The second is that the bounds are very bad, where a deep learning network would take an astronomical amount of data to reach said bounds.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-12-29T16:26:04.890Z
Comments.Text: both of these started out many years before ML theory in (theoretical) computer science and are more abstract. they interrelate to ML theory but are rarely cited by practitioners. VC dimension seems a rough measure of entropy and might correlate somewhat with "total size of model". think it is useful for ML practitioners to have some basic knowledge of TCS & its povs. however knowledge of them might be more relevant to those who are attempting to build new more effective models in the sense of research into ML & not as much tuning individual models for max performance (aka kaggle competitions)
Comments.UserDisplayName: vzn
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-12-31T07:04:11.227Z
Comments.Text: Possibly relevant: https://cs.stackexchange.com/q/75327/755
Comments.UserDisplayName: D.W.
Tags: <machine-learning><computational-learning-theory><pac-learning><vc-dimension><vc-theory>
Title: Are PAC learning and VC dimension relevant to machine learning in practice?
UserDisplayName: FourierFlux
ThreadText: # Are PAC learning and VC dimension relevant to machine learning in practice?
  
  (Asked by: username_0 on 2019-12-29)
  
  Are PAC learning and VC dimension relevant to machine learning in practice? If yes, what is their practical value?
  
  To my understanding, there are two hits against these theories. The first is that the results all are conditioned on knowing the appropriate models to use, for example, the degree of complexity. The second is that the bounds are very bad, where a deep learning network would take an astronomical amount of data to reach said bounds.
  
  **Tags:** machine-learning, computational-learning-theory, pac-learning, vc-dimension, vc-theory
  
  > **Comments:**
  > **username_1**: both of these started out many years before ML theory in (theoretical) computer science and are more abstract. they interrelate to ML theory but are rarely cited by practitioners. VC dimension seems a rough measure of entropy and might correlate somewhat with "total size of model". think it is useful for ML practitioners to have some basic knowledge of TCS & its povs. however knowledge of them might be more relevant to those who are attempting to build new more effective models in the sense of research into ML & not as much tuning individual models for max performance (aka kaggle competitions)  
  > **username_2**: Possibly relevant: https://cs.stackexchange.com/q/75327/755  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_3 on 2020-03-11. Score: 4
  
  Yes, PAC learning can be relevant in practice. There's an area of research that combines PAC learning and Bayesian learning that is called **PAC-Bayesian** (or **PAC-Bayes**) **learning**, where the goal is to find PAC-like bounds for Bayesian estimators.
  
  For example, **Theorem 1 (McAllester’s bound)** of the paper [A primer on PAC-Bayesian learning](https://arxiv.org/pdf/1901.05353.pdf) (2019) by Benjamin Guedj, who provides a nice overview of the topic, shows a certain bound that can be used to design Bayesian estimators. An advantage of PAC-Bayes is that you get bounds on the generalization ability of the Bayesian estimator, so you do not necessarily need to test your estimator on a test dataset. Sections 5 and 6 of the paper go into the details of the real-world applications of PAC-Bayes.
  
  See e.g. [Risk Bounds for the Majority Vote: From a PAC-Bayesian
  Analysis to a Learning Algorithm](http://jmlr.org/papers/volume16/germain15a/germain15a.pdf) (2015) by P. Germain et al. for a specific application of PAC-Bayes. There's also the [related Python implementation](https://github.com/GRAAL-Research/majority-vote-bounds).
  
  See also [these related slides](https://bguedj.github.io/icml2019/material/main.pdf) and [this blog post](https://bguedj.github.io/icml2019/index.html) (by the same author and John Shawe-Taylor) that will point you to their video tutorials about the topic.
  
  The VC dimension can also be useful in practice. For example, in the paper [Model Selection via the VC Dimension](http://www.jmlr.org/papers/volume20/17-669/17-669.pdf) (2019) M. Mpoudeu et al. describe a method for model selection based on the VC dimension.
  
  
  ---
  
  