Unconstrained Online Learning with Unbounded Losses
Unconstrained Online Learning with Unbounded Losses
复制标题
DOI：
10.48550/arxiv.2306.04923
复制
发表时间：
2023-06
期刊：
影响因子：
--
通讯作者：
Andrew Jacobsen;Ashok Cutkosky
中科院分区：
文献类型：
--
作者：
Andrew Jacobsen;Ashok Cutkosky
在线学习的算法通常需要一个或多个有界性假设：域是有界的，损失是Lipschitz的，或者两者兼而有之。在本文中，我们开发了一个新的设置与无界域和非Lipschitz损失的在线学习。对于这种情况，我们给出了一个算法，保证了在次梯度满足$g t le G+L w t的任何问题上，R T（u）le的结果为O（G u 2 T），并证明了这个界在没有进一步假设的情况下是不可改进的.我们利用这个算法来开发新的鞍点优化算法，收敛于对偶间隙在无界域，即使在没有有意义的曲率。最后，我们提供了第一个算法实现非平凡的动态遗憾在一个无界域的非Lipschitz损失，以及匹配的下限。当损失平滑时，我们的动态后悔算法的后悔自动提高到一个新的L^{*}$界。
Algorithms for online learning typically require one or more boundedness assumptions: that the domain is bounded, that the losses are Lipschitz, or both. In this paper, we develop a new setting for online learning with unbounded domains and non-Lipschitz losses. For this setting we provide an algorithm which guarantees $R_{T}(u)\le \tilde O(G\|u\|\sqrt{T}+L\|u\|^{2}\sqrt{T})$ regret on any problem where the subgradients satisfy $\|g_{t}\|\le G+L\|w_{t}\|$, and show that this bound is unimprovable without further assumptions. We leverage this algorithm to develop new saddle-point optimization algorithms that converge in duality gap in unbounded domains, even in the absence of meaningful curvature. Finally, we provide the first algorithm achieving non-trivial dynamic regret in an unbounded domain for non-Lipschitz losses, as well as a matching lower bound. The regret of our dynamic regret algorithm automatically improves to a novel $L^{*}$ bound when the losses are smooth.