  Tensor completion is a core machine learning algorithm used in recommender
systems and other domains with missing data. While the matrix case is
well-understood, theoretical results for tensor problems are limited,
particularly when the sampling patterns are deterministic. Here we bound the
generalization error of the solutions of two tensor completion methods, Poisson
loss and atomic norm minimization, providing tighter bounds in terms of the
target tensor rank. If the ground-truth tensor is order $t$ with CP-rank $r$,
the dependence on $r$ is improved from $r^{2(t-1)(t^2-t-1)}$ in
arXiv:1910.10692 to $r^{2(t-1)(3t-5)}$. The error in our bounds is
deterministically controlled by the spectral gap of the sampling sparsity
pattern. We also prove several new properties for the atomic tensor norm,
reducing the rank dependence from $r^{3t-3}$ in arXiv:1711.04965 to $r^{3t-5}$
under random sampling schemes. A limitation is that atomic norm minimization,
while theoretically interesting, leads to inefficient algorithms. However,
numerical experiments illustrate the dependence of the reconstruction error on
the spectral gap for the practical max-quasinorm, ridge penalty, and Poisson
loss minimization algorithms. This view through the spectral gap is a promising
window for further study of tensor algorithms.
