Uniform Learnability

Nonuniform learnability allows the sample-size requirement to depend on the competing hypothesis.

Programming

Why the Hypothesis Matters

A learnability guarantee describes when a learning algorithm can achieve a specified result from a sufficiently large sample. In nonuniform learnability, the required sample size is allowed to depend on more than the desired accuracy and confidence. It may also depend on the particular hypothesis h with which the algorithm is competing.

This is the central distinction: the definition does not require one fixed sample-size requirement to apply identically to every hypothesis. Instead, the requirement can be evaluated for the particular hypothesis under consideration.

How does changing the competing hypothesis h change the required sample size?

The Three Inputs

The sample-size function is written as m_NUL_H(ϵ, δ, h). Its three inputs are accuracy ϵ, confidence δ, and the competing hypothesis h. The notation says that the sample-size requirement associated with the hypothesis class H is evaluated using all three of these inputs.

ϵ represents the desired accuracy.
δ represents the desired confidence parameter.
h represents the particular competing hypothesis.

What does the sample-size function take as inputs, and how do accuracy ϵ, confidence δ, and hypothesis h flow into the required sample size?

Reading the Formal Definition

A hypothesis class is nonuniformly learnable when there exist an appropriate learning algorithm A and a sample-size function m_NUL_H such that the learning guarantee applies whenever the available sample size satisfies m ≥ m_NUL_H(ϵ, δ, h), for the relevant accuracy ϵ, confidence δ, and competing hypothesis h.

The definition therefore has two existence requirements. First, there must be a learning algorithm A. Second, there must be a function m_NUL_H that determines the required sample size. The function is evaluated using ϵ, δ, and h.

The inequality m ≥ m_NUL_H(ϵ, δ, h) compares two quantities. The left side, m, is the actual number of available examples. The right side is the requirement produced by the sample-size function for the selected accuracy, confidence, and hypothesis. The inequality is satisfied when the available sample contains at least the required number of examples.

What does the inequality mean about the available sample size m and the minimum number of examples required for hypothesis h?

Tracing a Hypothesis-Dependent Requirement

Comparing Two Hypotheses

Interpret the sample-size requirements for two competing hypotheses, h₁ and h₂, while keeping ϵ and δ fixed.

Step 1: The sample-size function receives the same accuracy ϵ and confidence δ in both cases.

Step 2: For the first comparison, the function is evaluated as m_NUL_H(ϵ, δ, h₁).

Step 3: For the second comparison, the function is evaluated as m_NUL_H(ϵ, δ, h₂).

Step 4: Because h is an input, the two evaluations are allowed to produce different sample-size requirements. The definition does not state which hypothesis must receive the larger requirement.

Step 5: For either hypothesis, the available sample size must satisfy the corresponding inequality: m ≥ m_NUL_H(ϵ, δ, h₁) or m ≥ m_NUL_H(ϵ, δ, h₂).

Nonuniform learnability permits the required sample size to vary with the competing hypothesis, while still using accuracy and confidence as inputs.

This example is intentionally symbolic. The source establishes that h is an input and that the requirement may depend on h, but it does not provide a numerical formula or determine whether h₁ or h₂ must require more examples.

Algorithm and Guarantee

The learning algorithm and the sample-size function play different roles. The algorithm A is the procedure whose learning behavior is being guaranteed. The function m_NUL_H determines how many examples are required for the chosen ϵ, δ, and h. Nonuniform learnability requires both to exist.

The condition m ≥ m_NUL_H(ϵ, δ, h) connects them to the data. When the available sample size meets or exceeds the requirement produced for the selected inputs, the definition's learning guarantee is considered under a sufficiently large sample.

How does the learning algorithm use at least the required number of training examples to achieve the specified accuracy and confidence?

Uniform and Nonuniform Requirements

Requirement style	How the hypothesis appears	Meaning
One fixed requirement	The requirement is not varied by the particular hypothesis	The same sample-size requirement is treated as applying across hypotheses.
Nonuniform requirement	h is an input to m_NUL_H(ϵ, δ, h)	The required sample size is allowed to depend on the hypothesis used for comparison.

The contrast is about how the sample-size requirement is expressed. Nonuniform learnability does not use one fixed requirement for every hypothesis. It uses a function whose inputs include the particular h. The source does not specify a formula for that function or the direction in which the requirement changes when h changes.

What is the difference between one sample-size bound shared by all hypotheses and bounds that vary with the hypothesis?

Common Interpretation Errors

Treating m_NUL_H(ϵ, δ, h) as one fixed sample size for every hypothesis.
The competing hypothesis h is an input to the sample-size function, so the requirement is allowed to depend on which hypothesis is being used for comparison.
Fix: Read the function as being evaluated separately for the selected ϵ, δ, and h.
Forgetting that accuracy and confidence are also inputs.
The function receives accuracy ϵ, confidence δ, and the competing hypothesis h.
Fix: Name all three inputs whenever you explain the sample-size requirement.
Reading m ≥ m_NUL_H(ϵ, δ, h) as an equation.
The symbol ≥ means that m may be equal to or greater than the requirement.
Fix: Interpret the condition as requiring the available sample to meet or exceed the number produced by the function.
Assuming the source determines which hypothesis requires more examples.
The source establishes dependence on h but does not give a formula or state the direction of change for a particular pair of hypotheses.
Fix: State only that the requirements may differ, unless an additional formula or guarantee is provided.

Check Your Interpretation

MEDIUM

Explain in your own words what must exist for a hypothesis class to be nonuniformly learnable, and interpret every symbol in m ≥ m_NUL_H(ϵ, δ, h).

Hints

Name the two existence requirements in the definition.
Identify the three inputs to the sample-size function.
Explain the difference between the available sample size m and the required sample size.

Your attempt (not saved)

What do you think happens?

Suppose ϵ and δ remain fixed but h changes from h₁ to h₂. Does the notation allow the required sample size to change?

Reveal answer

Answer: Yes

The competing hypothesis h is an input to m_NUL_H(ϵ, δ, h), so the sample-size requirement is allowed to depend on the selected hypothesis. The definition does not specify which of h₁ or h₂ receives the larger requirement.

Key Takeaways

Nonuniform learnability requires both an appropriate learning algorithm A and a sample-size function m_NUL_H.
The sample-size function takes accuracy ϵ, confidence δ, and the competing hypothesis h as inputs.
Because h is an input, the required number of examples may vary with the hypothesis.
The condition m ≥ m_NUL_H(ϵ, δ, h) means that the available sample size must meet or exceed the requirement for the selected inputs.
The notation does not provide a numerical formula or determine which hypothesis must require more examples.