Low-rank Tensor Learning with Nonconvex Overlapped Nuclear Norm Regularization
This work addresses a computational bottleneck in tensor learning for researchers and practitioners, though it is incremental as it builds on existing nonconvex regularization and optimization techniques.
The paper tackles the computational expense of extending nonconvex regularization to low-rank tensor learning by developing an efficient solver based on the proximal average algorithm, which avoids costly tensor operations and improves accuracy over state-of-the-art methods on tensor completion tasks.
Nonconvex regularization has been popularly used in low-rank matrix learning. However, extending it for low-rank tensor learning is still computationally expensive. To address this problem, we develop an efficient solver for use with a nonconvex extension of the overlapped nuclear norm regularizer. Based on the proximal average algorithm, the proposed algorithm can avoid expensive tensor folding/unfolding operations. A special "sparse plus low-rank" structure is maintained throughout the iterations, and allows fast computation of the individual proximal steps. Empirical convergence is further improved with the use of adaptive momentum. We provide convergence guarantees to critical points on smooth losses and also on objectives satisfying the Kurdyka-Łojasiewicz condition. While the optimization problem is nonconvex and nonsmooth, we show that its critical points still have good statistical performance on the tensor completion problem. Experiments on various synthetic and real-world data sets show that the proposed algorithm is efficient in both time and space and more accurate than the existing state-of-the-art.