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 what exactly is the polynomial function and why are they passing those parameters(size(c),inverse of delta etc), and how different it is from the hypothesis function outputed by the algorithm A(as specified in the book).

Thank You click here for Image


To be clear, the learning algorithm $\mathcal{A}$ refers to the procedure of selecting a hypothesis $h$ from the restricted hypothesis class $\mathcal{H}$, so if you are selecting $h$ by say minimising empirical risk $\hat{R}_S(h)$, algorithm $\mathcal{A}$ would be empirical risk minimisation. As a point of nomenclature, a hypothesis $h$ is also a function $f$, and the hypothesis class $\mathcal{H}$ can also be viewed as a function class $\mathcal{F}$. For concreteness, a hypothesis $h(x)$ might be a linear classifier indexed by a parameter $\theta$, that is, $h(x) = \mathbb{I}(\theta^Tx \geq 0)$.

The term polynomial function and $poly(1/\epsilon, 1/\delta, n, size(c))$ should not be confused with the above hypothesis $h$, or equivalently, the function $f$; rather, it is a way of specifying the sample complexity of the algorithm $\mathcal{A}$ - think little-Oh and big-Oh notation. Further, each of the arguments in the function $poly(\cdot, \cdot, \cdot, \cdot)$ should not be thought of as parameters in the sense that $\theta$ is a parameter. And that is because those arguments do not parametrise a statistical model in any conventional sense.

The sample complexity, that is, the term on right hand side of the inequality

sample size $m \geq poly(1/\epsilon, 1/\delta, n, size(c))$

is the minimum number of samples required for the bound in $(2.4)$ to hold.

Interpreting the first part of the definition.

If you can find a learning algorithm $\mathcal{A}$ and a polynomial function in your accuracy $\epsilon$, confidence $\delta$, $n$, and the size of the concept class $\mathcal{C}$ such that for any sample size $m$ greater than $poly(1/\epsilon, 1/\delta, n, size(c))$, the bound in $(2.4)$ holds, then your concept class is called PAC-learnable.

In order to better understand what the significance of $poly(\cdot, \cdot, \cdot, \cdot)$ is, the key here is that it is not an exponential function $exp(\cdot, \cdot, \cdot, \cdot)$; that is, the minimum of samples required to learn a concept class is not exponential in $1 / \epsilon$ and $1/ \delta$.

Lastly, I can see how this definition might seem somewhat terse and abstract - consider looking at the examples later in the book, and also order and stochastic order notation i.e. $o(\cdot), O(\cdot), o_P(\cdot), O_P(\cdot)$. It is these entities whose functional forms are being described with terms like $poly(...)$ and $exp(...)$. In my view, fluently understanding these distinctions is important for fully appreciating the arguments made in the book, as this definition shows. It is surprising therefore to not see at least a small note on this somewhere in the Appendix of the book.

A useful nuance to be aware of early, particularly when you start reading more papers in this area, is that statisticians tend to speak of generalisation error, that is, the rate at which the empirical risk converges to the risk as the number of samples increases; whereas computer scientists and those in PAC-learning on the other hand speak in terms sample complexity, that is, the minimum number of samples for an algorithm to be a PAC-learning algorithm. Whilst these perspectives are mathematically equivalent, the former requires stochastic order notation, that is, $o_P (\cdot)$ and $O_P (\cdot)$ notation, the probabilistic cousins of $o(\cdot)$ and $O(\cdot)$.

Here are some other references to supplement the Mohri book on PAC learning if it seems terse:

  • Shalev-Shwartz, S., Ben-David, S. (2014). Understanding Machine Learning - From Theory to Algorithms.. Cambridge University Press.
  • Mitchell, T. M. (1997). Machine Learning. New York: McGraw-Hill.
  • Lehmann, E. (1997). Elements of Large Sample Theory - this one has clear rigorous definitions of $o_P$ and $O_P$ notation.
  • $\begingroup$ Thank you this is very helpful. $\endgroup$
    – Sameer-21B
    Apr 5 '21 at 6:20
  • $\begingroup$ so,is this polynomial function similar to the O(n)(Big O notation) ,which we use to define the time complexity and space complexity of algorithms? $\endgroup$
    – Sameer-21B
    Apr 5 '21 at 6:25
  • $\begingroup$ Yes you are spot on, but there are some subtleties to be aware of. I have edited answer to address this, and to add some further references. Do have a search for "PAC learning" on the Q&A - there are some good answers. $\endgroup$
    – microhaus
    Apr 6 '21 at 11:48
  • $\begingroup$ thanks for the additional details but i have a last doubt regarding m,here m refers to the no. of individual examples(x1,x2....xm) within a sample S right?...or it refers to the no.of samples S drawn from the input space X.? $\endgroup$
    – Sameer-21B
    Apr 7 '21 at 7:56
  • $\begingroup$ The former is correct, $m$ refers to the number of individual examples in a single training sample $S$. $\endgroup$
    – microhaus
    Apr 7 '21 at 11:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.