We propose stochastic rank-$1$ bandits, a class of online learning problems
where at each step a learning agent chooses a pair of row and column arms, and
receives the product of their values as a reward. The main challenge of the
problem is that the individual values of the row and column are unobserved. We
assume that these values are stochastic and drawn independently. We propose a
computationally-efficient algorithm for solving our problem, which we call
Rank1Elim. We derive a $O((K + L) (1 / \Delta) \log n)$ upper bound on its
$n$-step regret, where $K$ is the number of rows, $L$ is the number of columns,
and $\Delta$ is the minimum of the row and column gaps; under the assumption
that the mean row and column rewards are bounded away from zero. To the best of
our knowledge, we present the first bandit algorithm that finds the maximum
entry of a rank-$1$ matrix whose regret is linear in $K + L$, $1 / \Delta$, and
$\log n$. We also derive a nearly matching lower bound. Finally, we evaluate
Rank1Elim empirically on multiple problems. We observe that it leverages the
structure of our problems and can learn near-optimal solutions even if our
modeling assumptions are mildly violated.

本文基于 stochastic rank-1 bandits 提出了 computationally-efficient 算法 Rank1Elim，该算法可解决在线学习问题，在 rank-1 矩阵中找到最大的条目，且在 K + L，1 / Δ 和 log n 方面的遗憾是线性的。

随机 Rank-1 赌博机

Stochastic Rank-1 Bandits

Compressed sensing of simultaneously sparse and low-rank matrices enables
recovery of sparse signals from a few linear measurements of their bilinear
form. One important question is how many measurements are needed for a stable
reconstruction in the presence of measurement noise. Unlike conventional
compressed sensing for sparse vectors, where convex relaxation via the
$\ell_1$-norm achieves near optimal performance, for compressed sensing of
sparse low-rank matrices, it has been shown recently Oymak et al. that convex
programmings using the nuclear norm and the mixed norm are highly suboptimal
even in the noise-free scenario.
We propose an alternating minimization algorithm called sparse power
factorization (SPF) for compressed sensing of sparse rank-one matrices. For a
class of signals whose sparse representation coefficients are fast-decaying,
SPF achieves stable recovery of the rank-1 matrix formed by their outer product
and requires number of measurements within a logarithmic factor of the
information-theoretic fundamental limit. For the recovery of general sparse
low-rank matrices, we propose subspace-concatenated SPF (SCSPF), which has
analogous near optimal performance guarantees to SPF in the rank-1 case.
Numerical results show that SPF and SCSPF empirically outperform convex
programmings using the best known combinations of mixed norm and nuclear norm.

通过稀疏低秩矩阵的压缩感知技术，提出了一种交替最小化算法，可以稳定地恢复这种信号及其外积形成的秩为 1 的矩阵，并在一定测量数目的情况下实现信息理论基础极限的对数倍内。