Yaxiong Liu (Kyushu University)*; Xuanke Jiang (Kyushu university); Kohei Hatano (Kyushu University / RIKEN AIP); Eiji Takimoto (Kyushu University)PMLR Page
Abstract
We consider the expert advice problem with a low rank but noisy loss sequence, where a loss vector lt ∈ [−1, 1]^N in each round t is of the form l_t = U v_t + ϵ_t for some fixed but unknown N × d matrix U called the kernel, some d-dimensional seed vector v_t ∈ R^d , and some additional noisy term ϵ_t ∈ R^N whose norm is bounded by ϵ. This is a generalization of the works of Hazan et al. and Barman et al., where the former only treats noiseless loss and the latter assumes that the kernel is known in advance. In this paper, we propose an algorithm, where we re-construct the kernel under the assumptions, that the low rank loss is noised and there is no prior information about kernel. In this algorithm, we approximate the kernel by choosing a set of loss vectors with a high degree of independence from each other, and we give a regret bound of O(d \sqrt{T} + d^4/3 (Nϵ)^1/3 \sqrt{T}). Moreover, even if in experiment, the proposed algorithm performs better than Hazan’s algorithm and Hedge algorithm.