Rademacher Complexity (Exact)

Problem

Compute the exact empirical Rademacher complexity of a finite hypothesis class. vectors contains each hypothesis evaluated on n points. Average max_h |sum_i sigma_i * h_i| over all 2^n sign vectors sigma, then divide by n. Assume n is small (at most about 12).

Hint

Richer hypothesis classes can correlate with more random sign patterns.

Test cases

case 1

in: [[[1,0]]]

expected: 0.5

case 2

in: [[[1,1]]]

expected: 0.5

case 3

in: [[[1,1],[1,-1]]]

expected: 1

case 4

in: [[[1,0,0],[0,1,0]]]

expected: 0.3333333333333333

Starter codePython

def rademacher_complexity(vectors):
    # Your code here
    pass

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