Mirror Descent KL Step

Problem

Perform one mirror descent step with the KL divergence on the probability simplex.

Compute q_i proportional to p_i * exp(-lr * g_i), then normalize so the entries sum to 1. Return the new probability list.

Hint

The exponential tilt followed by renormalization is the KL prox.

case 1

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

expected: [0.4501660026875221,0.549833997312478]

case 2

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

expected: [0.2,0.3,0.5]

case 3

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

expected: [0.9758075451312032,0.02419245486879684]

Starter codePython

def mirror_descent_kl_step(p, g, lr):
    # Your code here
    pass

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