Accuracy and Confidence in PAC Learning
Sample complexity is not one permanent number for every learning situation. It is a function whose value can change when the accuracy requirement, confidence requirement, or hypothesis class changes.
The Data Requirement Behind PAC Learning
A PAC learner is not described only by the hypothesis it eventually returns. We also need to ask how much training data is needed before that result can be guaranteed to be probably approximately correct. Sample complexity answers this question: it specifies the number of examples required to learn a hypothesis class H under particular accuracy and confidence requirements.
Sample complexity is not one permanent number for every learning situation. It is a function whose value can change when the accuracy requirement, confidence requirement, or hypothesis class changes.
From Requirements to Example Count
The sample-complexity function is commonly written as m_H. Its inputs include the accuracy parameter ε, the confidence parameter δ, and properties of the hypothesis class H. Its output is the number of training examples required for PAC learning under those requirements. Thinking of m_H as a function prevents a common mistake: there is not a single example count that applies to every PAC learning problem.
Changing the Learning Situation
Consider two PAC learning questions. The first uses one pair of accuracy and confidence requirements with hypothesis class H. The second changes one of those requirements or replaces H with another hypothesis class.
- 1Identify the inputs
The sample-complexity function takes the accuracy parameter ε, the confidence parameter δ, and properties of H into account.
- 2Compare the situations
Because at least one input or class property has changed, the relevant value of the sample-complexity function can change.
- 3Avoid a fixed-number interpretation
The number of examples required in the first situation should not automatically be reused for the second situation.
Sample complexity describes a requirement for a specified learning situation, not a permanent number independent of ε, δ, and H.
Accuracy and Confidence Parameters
The parameter ε represents the accuracy requirement, while δ represents the confidence requirement. Together they state how demanding the PAC guarantee must be. If either requirement is changed, the relevant value of the sample-complexity function can change. The source material establishes this dependence, but it does not give a universal numerical rule for how much the value changes in every hypothesis class.
Why H Matters
Sample complexity also depends on properties of the hypothesis class H. Two learning problems can use the same accuracy and confidence parameters while involving different hypothesis classes. Their sample-complexity requirements need not be the same because the class being learned affects the function. For a finite hypothesis class, one relevant dependence is on the logarithm of the size of H.
| What changes | What stays the same | What follows |
|---|---|---|
| The hypothesis class H | ε and δ | The sample-complexity requirements need not be the same. |
| ε or δ | The hypothesis class H | The relevant value of the sample-complexity function can change. |
Sample complexity reflects both learning requirements and properties of the class being learned.
Valid Versus Minimal Functions
PAC learnability may permit many functions that satisfy its requirements. An arbitrary valid sample-complexity function can therefore give an example count that is sufficient for the PAC guarantee without being the smallest possible count. The precisely defined sample complexity is the minimal function: for each ε and δ, it returns the smallest integer that satisfies the PAC requirements.
Two Sufficient Answers
Suppose a particular learning situation has a smallest sufficient example count represented by m*_H(ε, δ). Construct a second function g_H(ε, δ) that asks for more examples than this smallest count while still satisfying the PAC requirements.
- 1Start with the minimal function
m*_H returns the smallest integer that satisfies the PAC requirements for the selected ε and δ.
- 2Allow a larger valid count
g_H can specify a larger count for the same requirements and still be valid if that larger count satisfies the PAC requirements.
- 3Compare their meanings
Both functions can support the guarantee, but only m*_H represents the precisely defined minimal sample complexity.
Validity means the requirement is sufficient; minimality means no smaller integer satisfies the requirements for that ε and δ.
The PAC Guarantee Path
The learning process can be viewed as a requirement-to-guarantee path. First specify the hypothesis class H and the desired accuracy and confidence requirements. Then determine how many examples the sample-complexity function requires. After that amount of training data is available, the PAC statement concerns the hypothesis produced by the learner: it should be probably approximately correct under the specified requirements.
Mistakes About Sample Complexity
Common mistake Treating sample complexity as one permanent number.
What it looks likeAssuming that one example count applies even after ε, δ, or H changes.
Why it failsThe sample-complexity function depends on the accuracy parameter, confidence parameter, and properties of the hypothesis class.
Do this insteadAlways identify the requirements and the hypothesis class before discussing the required number of examples.
Common mistake Assuming that the same ε and δ force the same sample complexity for every class.
What it looks likeComparing two learning problems with different hypothesis classes and declaring that their requirements must match because their parameters match.
Why it failsSample complexity also reflects properties of H.
Do this insteadKeep the hypothesis class as an explicit part of the learning situation.
Common mistake Calling every valid bound the minimal sample complexity.
What it looks likeUsing a sufficient but unnecessarily large example count and labeling it the precise sample complexity.
Why it failsThe precise sample complexity is the smallest integer satisfying the PAC requirements for each ε and δ.
Do this insteadDistinguish an arbitrary valid function from the minimal function.
Common mistake Describing only the returned hypothesis.
What it looks likeExplaining what the learner returns without asking how much training data is needed before the PAC guarantee can be made.
Why it failsSample complexity specifically addresses the amount of training data needed for the guarantee.
Do this insteadDiscuss both the learner's result and the number of examples required to support it.
Check Your Understanding
A learning problem keeps ε and δ fixed but replaces H with a different hypothesis class. Explain why the sample-complexity requirement may change. Then explain how an arbitrary valid sample-complexity function could differ from the minimal function in the new problem.
Hints
- List all the inputs and class properties on which m_H depends.
- Separate the meaning of sufficient from the meaning of smallest.
What do you think happens?
If ε and δ remain fixed but H changes, must the two learning problems have identical sample-complexity requirements?
Reveal answer
No, because sample complexity also depends on properties of H.
The hypothesis class is an input to the sample-complexity function. Two problems with the same accuracy and confidence parameters can therefore have different requirements when their hypothesis classes differ.
Key Takeaways
- 1Sample complexity specifies how many examples are required for a probably approximately correct solution.
- 2The function m_H depends on ε, δ, and properties of the hypothesis class H.
- 3Changing the accuracy or confidence requirements can change the relevant sample-complexity value.
- 4Different hypothesis classes can have different sample-complexity requirements even when ε and δ are the same.
- 5The minimal sample-complexity function returns the smallest integer satisfying the PAC requirements; other valid functions may request more examples.
At a glance
- Sample complexity answers how much training data is needed before a PAC result can be guaranteed.
- Accuracy ε and confidence δ are requirements that help determine the example count.
- The hypothesis class H matters because sample complexity depends on properties of the class being learned.
- A valid sample-complexity function may be sufficient without being minimal.
- The precise sample complexity is the smallest integer that satisfies the PAC requirements for each ε and δ.