Scale-Invariant Unconstrained Online Learning
Scale-Invariant Unconstrained Online Learning
复制标题
尺度不变的无约束在线学习
DOI：
10.1016/j.tcs.2019.11.016
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
W. Kotłowski
中科院分区：
文献类型：
--
作者：
W. Kotłowski
我们考虑一个在线监督学习问题，其中的实例（输入向量）和比较器（权重向量）都是无约束的。我们利用一个自然的规模不变性对称在我们的无约束设置：预测的最佳比较器下的任何线性变换的情况下是不变的。我们的目标是设计在线算法，也享受这个属性，即规模不变。我们从坐标不变性的情况开始，其中单个坐标（特征）可以任意重新缩放。我们给出了一个算法，它实现了基本上最佳的遗憾界在这个设置中，表示通过一个坐标明智的规模不变范数的比较器。然后，我们研究一般不变性关于任意线性变换。我们首先给出了一个否定的结果，表明没有算法可以实现一个有意义的界在最坏的情况下的尺度不变范数的比较。接下来，我们用一个肯定的结果来补充这个结果，提供一个“几乎”达到期望界限的算法，只会在实例的相对大小方面产生对数开销。
We consider an online supervised learning problem, in which both the instances (input vectors) and the comparator (weight vector) are unconstrained. We exploit a natural scale invariance symmetry in our unconstrained setting: the predictions of the optimal comparator are invariant under any linear transformation of the instances. Our goal is to design online algorithms which also enjoy this property, i.e. are scale-invariant. We start with the case of coordinate-wise invariance, in which the individual coordinates (features) can be arbitrarily rescaled. We give an algorithm, which achieves essentially optimal regret bound in this setup, expressed by means of a coordinate-wise scale-invariant norm of the comparator. We then study general invariance with respect to arbitrary linear transformations. We first give a negative result, showing that no algorithm can achieve a meaningful bound in terms of scale-invariant norm of the comparator in the worst case. Next, we compliment this result with a positive one, providing an algorithm which “almost” achieves the desired bound, incurring only a logarithmic overhead in terms of the relative size of the instances.
通过硬币投注训练深度网络，无需学习率
DOI：
--
发表时间：
2017
期刊：
Advances in Neural Information Processing Systems 30
影响因子：
--
作者：
Orabona, Francesco;Tommasi, Tatiana
通讯作者：
Tommasi, Tatiana