Online Tensor Learning: Computational and Statistical Trade-offs

Music City Center 

Large tensor learning algorithms are typically computationally expensive and require storing a vast amount of data. In this paper, we propose a unified online Riemannian gradient descent (oRGrad) algorithm for tensor learning, which is computationally efficient, consumes much less memory, and can handle sequentially arriving data while making timely predictions. The algorithm is applicable to both linear and generalized linear models. If the time horizon T is known, oRGrad achieves statistical optimality by choosing an appropriate fixed step size. We find that noisy tensor completion particularly benefits from online algorithms by avoiding the trimming procedure and ensuring sharp entry-wise statistical error, which is often technically challenging for offline methods. The regret of oRGrad is analyzed, revealing a fascinating trilemma concerning the computational convergence rate, statistical error, and regret bound. By selecting an appropriate constant step size, oRGrad achieves an O(T^{1/2}) regret. We then introduce the adaptive-oRGrad algorithm, which can achieve the optimal O(log T ) regret by adaptively selecting step sizes, regardless of whether the time horizon is known.

Tensor

High dimensional statistics

Online learning

Regret analysis 

IMS