Gaussian Follow-The-Perturbed-Leader

新算法在无偏平滑在线学习中实现了最优遗憾

研究人员开发了一种新的平滑在线学习算法，该算法在无偏设置下实现了亚线性遗憾，而无需对基本度量进行采样或依赖于完美预测的标签。这种名为高斯扰动领导者跟随（Gaussian Follow-The-Perturbed-Leader）的新方法是无参数的，这意味着它不需要了解基本度量、平滑参数或范围。它使用对经验风险最小化预言机的一次调用，为具有VC维度d的二元类别实现了\ufffdO(d\sqrt{T/\sigma})的最优遗憾界限。