Online tensor learning: Computational and statistical trade-offs, adaptivity and optimal regret
提出一种在线黎曼梯度下降算法，用于高效处理大规模张量数据，在已知或未知时间范围下均能达到统计最优误差，并揭示了计算收敛速度、统计误差与遗憾之间的三重权衡。
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 entrywise 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(T1/2) regret. We then introduce the adaptive-oRGrad algorithm, which can achieve the optimal O(logT) regret by adaptively selecting step sizes, regardless of whether the time horizon is known. The adaptive-oRGrad algorithm can attain a statistically optimal error rate without knowing the horizon. Comprehensive numerical simulations corroborate our theoretical findings. We show that oRGrad significantly outperforms its offline counterpart in predicting the solar F10.7 index with tensor predictors that monitor space weather impacts.