Parameter-free Regret in High Probability with Heavy Tails
Jiujia Zhang,Ashok Cutkosky
We present new algorithms for online convex optimization over unbounded domains that obtain parameter-free regret in high-probability given access only to potentially heavy-tailed subgradient estimates. Previous work in unbounded domains con- siders only in-expectation results for sub-exponential subgradients. Unlike in the bounded domain case, we cannot rely on straight-forward martingale concentration due to exponentially large iterates produced by the algorithm. We develop new regularization techniques to overcome these problems. Overall, with probability at most u03b4, for all comparators u our algorithm achieves regret O u0303(u2225uu2225T 1/p log(1/u03b4)) for subgradients with bounded pth moments for some p u2208 (1, 2].
