FTRL-Proximal Step

Problem

Perform one FTRL-Proximal update for a single coordinate.

With n_old = n, set n = n + g ** 2, sigma = (sqrt(n) - sqrt(n_old)) / lr, and z = z + g - sigma * w. With denom = l2 + sqrt(n) / lr, return w_new = -(z - l1) / denom when z > l1, -(z + l1) / denom when z < -l1, and 0.0 otherwise. Return [w_new, z, n].

Hint

FTRL lazily accumulates gradients and only produces a weight when z escapes the L1 dead zone.

Test cases

case 1

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

expected: [-0.25,1,1]

case 2

in: [1,0.5,4,0.5,0.5,0.1,0]

expected: [-0.18842456267803157,0.8768943743823394,4.25]

case 3

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

expected: [0,0.14403065089105505,1.09]

Starter codePython

def ftrl_step(w, z, n, g, lr, l1, l2):
    # Returns [w_new, z, n]
    # Your code here
    pass

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