Most existing studies on linear bandits focus on the one-dimensional
characterization of the overall system. While being representative, this
formulation may fail to model applications with high-dimensional but favorable
structures, such as the low-rank tensor representation for recommender systems.
To address this limitation, this work studies a general tensor bandits model,
where actions and system parameters are represented by tensors as opposed to
vectors, and we particularly focus on the case that the unknown system tensor
is low-rank. A novel bandit algorithm, coined TOFU (Tensor Optimism in the Face
of Uncertainty), is developed. TOFU first leverages flexible tensor regression
techniques to estimate low-dimensional subspaces associated with the system
tensor. These estimates are then utilized to convert the original problem to a
new one with norm constraints on its system parameters. Lastly, a
norm-constrained bandit subroutine is adopted by TOFU, which utilizes these
constraints to avoid exploring the entire high-dimensional parameter space.
Theoretical analyses show that TOFU improves the best-known regret upper bound
by a multiplicative factor that grows exponentially in the system order. A
novel performance lower bound is also established, which further corroborates
the efficiency of TOFU.

TOFU 算法研究了一个基于张量表示的线性赌博模型，其中系统参数和行动由张量表示，特别关注未知系统张量为低秩张量的情况。它首先利用灵活的张量回归技术估计与系统张量相关联的低维子空间，然后利用这些估计将原始问题转化为具有系统参数范数约束的新问题，最后采用 TOFU 算法，它利用这些约束来避免探索整个高维参数空间，理论分析表明，TOFU 在比先前的最佳后悔上界改善的倍数增加了一个随着系统阶数呈指数增长的系数，同时 TOFU 还建立了一个新的性能下限，进一步证明了 TOFU 的效率。

高维和低秩张量赌博机

On High-dimensional and Low-rank Tensor Bandits

This paper presents Tofu, a system that partitions very large DNN models
across multiple GPU devices to reduce per-GPU memory footprint. Tofu is
designed to partition a dataflow graph of fine-grained tensor operators in
order to work transparently with a general-purpose deep learning platform like
MXNet. In order to automatically partition each operator, we propose to
describe the semantics of an operator in a simple language which represents
tensors as lambda functions mapping from tensor coordinates to values. To
optimally partition different operators in a dataflow graph, Tofu uses a
recursive search algorithm that minimizes the total communication cost. Our
experiments on an 8-GPU machine show that Tofu enables the training of very
large CNN and RNN models. It also achieves 25% - 400% speedup over alternative
approaches to train very large models.

Tofu 是一个系统，它可以将超大的 DNN 模型分割到多个 GPU 设备上以减少每个 GPU 的内存占用，该系统采用数据流图的方式透明地与 MXNet 等通用深度学习平台配合使用，通过一种描述算子语义的简单语言，实现自动划分。通过递归搜索算法来优化划分，并在 8-GPU 机器上的实验中展现了训练超大 CNN 和 RNN 模型的能力，在速度方面则比其他方法提高了 25% 至 400%。