PAC Sample Complexity

Problem

Return the PAC sample complexity for a finite hypothesis class:

m >= ceil((ln|H| + ln(1 / delta)) / (2 * epsilon^2))

This is the number of samples needed to learn a hypothesis with error at most epsilon and confidence 1 - delta.

Hint

Halving epsilon quadruples the sample requirement.

case 1

in: [100,0.1,0.05]

expected: 381

case 2

in: [2,0.1,0.1]

expected: 150

case 3

in: [1000,0.05,0.01]

expected: 2303

case 4

in: [10,0.2,0.2]

expected: 49

Starter codePython

import math
def pac_sample_complexity(num_hypotheses, epsilon, delta):
    # Your code here
    pass

4 test cases · run your code against them in the editor