Uniform Convergence Gap

Problem

Return the uniform convergence gap bound from a union bound over a finite hypothesis class:

gap = sqrt(ln(2 * |H| / delta) / (2m))

With probability 1 - delta, every hypothesis has true risk within gap of its empirical risk.

Hint

The gap scales logarithmically in the number of hypotheses.

case 1

in: [10,100,0.05]

expected: 0.17308183826022852

case 2

in: [2,50,0.1]

expected: 0.19206455826398416

case 3

in: [1,10,0.5]

expected: 0.26327688477341593

case 4

in: [100,1000,0.01]

expected: 0.07036862778446133

Starter codePython

import math
def uniform_convergence_gap(num_hypotheses, m, delta):
    # Your code here
    pass

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