Expert advice problem with noisy low rank loss

We consider the expert advice problem with a low rank but noisy loss sequence, where a loss vector $l_{t} \in [-1,1]^N$ in each round $t$ is of the form $l_{t} = U v_{t} + \epsilon_{t}$ for some fixed but unknown $N \times d$ matrix $U$ called the kernel, some $d$-dimensional seed vector $v_{t} \in \mathbb{R}^{d}$, and some additional noisy term $\epsilon_t \in \mathbb{R}^{N}$ whose norm is bounded by $\epsilon$. 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\epsilon)^{1/3}\sqrt{T})$. Moreover, even if in experiment, the proposed algorithm performs better than Hazan’s algorithm and Hedge algorithm.