# Online Tensor Learning: Computational and Statistical Trade-offs, Adaptivity and Optimal Regret

arXiv: https://arxiv.org/abs/2306.03372 · HTML: https://mlsanity.com/paper/2306.03372/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 83 references that are in the map.
- First posted on arXiv 6 Jun 2023.

## Builds on (most cited first, 14 of 14)

- [Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees](https://mlsanity.com/paper/1509.03025/) (2015)
- [Community Detection for Hypergraph Networks via Regularized Tensor Power Iteration](https://mlsanity.com/paper/1909.06503/) (2019)
- [Guarantees of Riemannian Optimization for Low Rank Matrix Completion](https://mlsanity.com/paper/1603.06610/) (2016)
- [Tensor-on-Tensor Regression: Riemannian Optimization, Over-parameterization, Statistical-computational Gap, and Their Interplay](https://mlsanity.com/paper/2206.08756/) (2022)
- [Latent Space Model for Higher-order Networks and Generalized Tensor Decomposition](https://mlsanity.com/paper/2106.16042/) (2021)
- [Implicit Regularization and Entrywise Convergence of Riemannian Optimization for Low Tucker-Rank Tensor Completion](https://mlsanity.com/paper/2108.07899/) (2021)
- [Semi-parametric TEnsor Factor Analysis by Iteratively Projected Singular Value Decomposition](https://mlsanity.com/paper/2007.02404/) (2020)
- [Sparse Bilinear Logistic Regression](https://mlsanity.com/paper/1404.4104/) (2014)
- [Optimal Clustering by Lloyd Algorithm for Low-Rank Mixture Model](https://mlsanity.com/paper/2207.04600/) (2022)
- [On High-dimensional and Low-rank Tensor Bandits](https://mlsanity.com/paper/2305.03884/) (2023)
- [Computationally Efficient and Statistically Optimal Robust High-Dimensional Linear Regression](https://mlsanity.com/paper/2305.06199/) (2023)
- [Riemannian optimization using three different metrics for Hermitian PSD fixed-rank constraints: an extended version](https://mlsanity.com/paper/2204.07830/) (2022)
- [Robust Regularized Low-Rank Matrix Models for Regression and Classification](https://mlsanity.com/paper/2205.07106/) (2022)
- [Computationally Efficient and Statistically Optimal Robust Low-rank Matrix and Tensor Estimation](https://mlsanity.com/paper/2203.00953/) (2022)

## Built on by (most cited first, 4 of 4)

- [High-dimensional Linear Bandits with Knapsacks](https://mlsanity.com/paper/2311.01327/) (2023)
- [Fourier Low-rank and Sparse Tensor for Efficient Tensor Completion](https://mlsanity.com/paper/2505.11261/) (2025)
- [Inference and Uncertainty Quantification for Streaming r-PCA](https://mlsanity.com/paper/2608.18374/) (2026)
- [Tensor Completion using Subspace Information](https://mlsanity.com/paper/2609.24501/) (2026)

## Abstract (arXiv)

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(T1/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. 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.