All problems
Bregman Proximal Step
Problem
Mirror descent with the negative entropy mirror map gives the exponentiated-gradient update:
x_i proportional to q_i * exp(-eta * grad_i), normalized to sum to 1
Given the current point q, the gradient, and the step size eta, return the updated point.
Hint
Multiplicative updates keep the iterates nonnegative and on the simplex automatically.
Test cases
case 1
in: [[0.5,0.5],[0,0],1]
expected: [0.5,0.5]
case 2
in: [[0.5,0.5],[1,-1],0.5]
expected: [0.26894142136999516,0.731058578630005]
case 3
in: [[1,0],[0,0],1]
expected: [1,0]
case 4
in: [[0.2,0.8],[-1,1],1]
expected: [0.6487856442839393,0.3512143557160607]
Starter codePython
def bregman_prox_step(q, grad, eta):
# Your code here
pass4 test cases · run your code against them in the editor