Frank-Wolfe Step

Problem

Perform one Frank-Wolfe step over the probability simplex.

The linear minimization oracle picks the one-hot vertex s at the smallest gradient component, with the lowest index winning ties. Return x_new = (1 - gamma) * x + gamma * s as a list.

Hint

The simplex oracle is one-hot at the smallest gradient entry.

Test cases

case 1

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

expected: [0.25,0.75]

case 2

in: [[0.2,0.3,0.5],[2,1,3],0.25]

expected: [0.15000000000000002,0.475,0.375]

case 3

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

expected: [0.7,0.3]

Starter codePython

def frank_wolfe_step(x, grad, gamma):
    # Your code here
    pass

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