BriefGPT.xyz
Mar, 2012
在线矩阵预测的近优算法
Near-Optimal Algorithms for Online Matrix Prediction
HTML
PDF
Elad Hazan, Satyen Kale, Shai Shalev-Shwartz
TL;DR
通过解析关于在线预测问题的与矩阵相关的比较类,提出了一种(beta,tau)-decomposability的性质,进而导出了一个有效的在线学习算法,证明了其对所有(beta,tau)-可分解矩阵的问题都有较优的regret界限,并对三个问题得出了更佳的regret界限和下界。
Abstract
In several online prediction problems of recent interest the comparison class is composed of
matrices
with bounded entries. For example, in the online max-cut problem, the comparison class is
matrices
which repre
→