Parameter-Free Regret in High Probability with Heavy Tails

Abstract

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 δ, for all comparators u our algorithm achieves regret O ̃(∥u∥T 1/p log(1/δ)) for subgradients with bounded pth moments for some p ∈ (1, 2].

PDF NeurIPS OpenReview Semantic Scholar

Cite

Text

Zhang and Cutkosky. "Parameter-Free Regret in High Probability with Heavy Tails." Neural Information Processing Systems, 2022.

Markdown

[Zhang and Cutkosky. "Parameter-Free Regret in High Probability with Heavy Tails." Neural Information Processing Systems, 2022.](https://mlanthology.org/neurips/2022/zhang2022neurips-parameterfree/)

BibTeX

@inproceedings{zhang2022neurips-parameterfree,
  title     = {{Parameter-Free Regret in High Probability with Heavy Tails}},
  author    = {Zhang, Jiujia and Cutkosky, Ashok},
  booktitle = {Neural Information Processing Systems},
  year      = {2022},
  url       = {https://mlanthology.org/neurips/2022/zhang2022neurips-parameterfree/}
}