Parameter-free Regret in High Probability with Heavy Tails
Parameter-free Regret in High Probability with Heavy Tails
复制标题
DOI：
10.48550/arxiv.2210.14355
复制
发表时间：
2022-10
期刊：
影响因子：
--
通讯作者：
Jiujia Zhang;Ashok Cutkosky
中科院分区：
文献类型：
--
作者：
Jiujia Zhang;Ashok Cutkosky
我们提出了在无界域上进行在线凸优化的新算法，该算法在仅能获取可能是重尾的次梯度估计的情况下，以高概率获得无参数的遗憾值。先前在无界域上的工作仅考虑了次指数次梯度的期望结果。与有界域的情况不同，由于算法产生的指数级大的迭代值，我们不能依赖直接的鞅集中不等式。我们开发了新的正则化技术来克服这些问题。总体而言，对于所有比较器\(\mathbf{u}\)，以至多为\(\delta\)的概率，对于某些\(\mathfrak{p} \in (1, 2]\)，具有有界\(\mathfrak{p}\)阶矩的次梯度，我们的算法实现了遗憾值\(\tilde{O}(\| \mathbf{u} \| T^{1/\mathfrak{p}} \log (1/\delta))\)。
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 considers 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 $\delta$, for all comparators $\mathbf{u}$ our algorithm achieves regret $\tilde{O}(\| \mathbf{u} \| T^{1/\mathfrak{p}} \log (1/\delta))$ for subgradients with bounded $\mathfrak{p}^{th}$ moments for some $\mathfrak{p} \in (1, 2]$.