Motivated by combinatorial regression problems (which we interpret as low-rank tensor completion), we study noisy completion for positive tensors. Existing approaches convert this into matrix completion, but this is unable to achieve the best statistical rates possible. Here, we show that a specific class of low-rank tensors (namely those parametrized as continuous extensions of hierarchical...