AdaGrad Regret Bound

Problem

Compute the AdaGrad regret bound for convex Lipschitz losses.

Return 2 * D * sqrt(sum of squared gradient norms), where D is the diameter and grad_norms_sq lists the squared norm ||g_t||^2 of each round. Return 0.0 when D <= 0 or the list is empty.

Hint

AdaGrad replaces the T factor with the accumulated squared gradient norms.

Test cases

case 1

in: [1,[1,1,1,1]]

expected: 4

case 2

in: [0.5,[4,9]]

expected: 3.605551275463989

case 3

in: [1,[]]

expected: 0

case 4

in: [0,[1]]

expected: 0

Starter codePython

def adagrad_regret_bound(D, grad_norms_sq):
    # Your code here
    pass

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