Exponentiated Gradient Time-Varying

Problem

Perform an exponentiated gradient update with a time-varying learning rate.

Use eta = eta0 / sqrt(t) with t at least 1, compute u_i proportional to w_i * exp(-eta * g_i), and return the normalized weights, which stay on the probability simplex. A larger t means a smaller step.

Hint

The multiplicative update is the mirror descent step under the KL divergence.

Test cases

case 1

in: [[0.5,0.5],[0.4,-0.4],0.1,1]

expected: [0.4800106598444182,0.5199893401555817]

case 2

in: [[0.2,0.3,0.5],[0,0,0],1,4]

expected: [0.2,0.3,0.5]

case 3

in: [[0.9,0.1],[-2,1],0.5,16]

expected: [0.9290524666899646,0.0709475333100355]

Starter codePython

def exp_gradient_tv(w, g, eta0, t):
    # Your code here
    pass

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