Projected Mirror Descent Step

Problem

Perform a mirror descent step with the Euclidean mirror map, then project onto the probability simplex.

Compute y = x - lr * g and return the Euclidean projection of y onto the set of non-negative vectors summing to 1. The projection subtracts a threshold computed from the sorted coordinates; if every sorted test fails, return the one-hot vector at the largest coordinate.

Hint

Sort descending, find the largest active prefix, and subtract its threshold.

Test cases

case 1

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

expected: [0.3,0.7]

case 2

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

expected: [0.2,0.3,0.5]

case 3

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

expected: [1,0]

case 4

in: [[0.4,0.4,0.2],[0.1,0.1,0.1],0.5]

expected: [0.4,0.4,0.19999999999999998]

Starter codePython

def projected_mirror_descent_step(x, g, lr):
    # Your code here
    pass

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