Efficient Low-Rank Matrix Estimation, Experimental Design, and
  Arm-Set-Dependent Low-Rank Bandits
Kyoungseok Jang Chicheng Zhang Kwang-Sung Jun
We study low-rank matrix trace regression and the related problem of low-rank
matrix bandits. Assuming access to the distribution of the covariates, we
propose a novel low-rank matrix estimation method called LowPopArt and provide
its recovery guarantee that depends on a novel quantity denoted by B(Q) that
characterizes the hardness of the problem, where Q is the covariance matrix of
the measurement distribution. We show that our method can provide tighter
recovery guarantees than classical nuclear norm penalized least squares
(Koltchinskii et al., 2011) in several problems. To perform efficient
estimation with a limited number of measurements from an arbitrarily given
measurement set A, we also propose a novel experimental design criterion that
minimizes B(Q) with computational efficiency. We leverage our novel estimator
and design of experiments to derive two low-rank linear bandit algorithms for
general arm sets that enjoy improved regret upper bounds. This improves over
previous works on low-rank bandits, which make somewhat restrictive assumptions
that the arm set is the unit ball or that an efficient exploration distribution
is given. To our knowledge, our experimental design criterion is the first one
tailored to low-rank matrix estimation beyond the naive reduction to linear
regression, which can be of independent interest.