We consider a variant of online semi-definite programming problem (OSDP): The decision space consists of semi-definite matrices with bounded $\bm{\Gamma}$-trace norm, which is a generalization of trace norm defined by a positive definite matrix $\Gamma.$ To solve this problem, we utilise the follow-the-regularized-leader algorithm with a $\Gamma$-dependent log-determinant regularizer. Then we apply our generalised setting and our proposed algorithm to online matrix completion(OMC) and online similarity prediction with side information. In particular, we reduce the online matrix completion problem to the generalised OSDP problem, and the side information is represented as the $\Gamma$ matrix. Hence, due to our regret bound for the generalised OSDP, we obtain an optimal mistake bound for the OMC by removing the logarithmic factor.
翻译：我们考虑的是在线半无限期编程问题的变体:决定空间包括半无限期矩阵,其约束值为$\bm~Gamma}- trace规范,这是对由正确定矩阵定义的追踪规范的概括化。为了解决这个问题,我们用一个$\Gamma$-依赖日志-确定性规范化的跟踪领导算法,我们使用一个常规设置和我们提议的算法来完成在线矩阵(OMC)和附带信息的在线类似性预测。特别是,我们将在线矩阵完成问题降低到通用的OSDP问题,而侧信息则被作为美元/Gamma$矩阵。因此,由于我们对通用的OSDP感到遗憾,我们通过消除对数因素,获得了为OMC约束的最佳错误。
相关内容
微信扫码咨询专知VIP会员