BriefGPT.xyz
Oct, 2020
带多个提示的在线线性优化
Online Linear Optimization with Many Hints
HTML
PDF
Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, Manish Purohit
TL;DR
本文研究一种在线线性优化问题,其中学习者在每一轮进行决策之前可以访问K个'暗示'向量。本文设计了一种算法,可以在存在带有成本向量正相关性的K个暗示的凸组合时获得对数后悔,这显著扩展了以前只考虑K=1情况的相关工作。为了实现这一点,我们开发了一种方法,将许多任意OLO算法组合起来,以实现后验情况下最小后悔的对数更差因素,该结果独立地具有利益。
Abstract
We study an
online linear optimization
(OLO) problem in which the learner is provided access to $K$ "hint" vectors in each round prior to making a decision. In this setting, we devise an algorithm that obtains logarithmic
→