Online and Differentially-Private Tensor Decomposition
This work addresses key algorithmic problems for researchers and practitioners in machine learning and data analysis, offering incremental improvements in privacy and efficiency for tensor decomposition tasks.
The paper tackles the challenges of robustness, memory efficiency, and differential privacy in tensor decomposition by proposing simple variants of the tensor power method, achieving linear memory requirements for online decomposition and efficient privacy guarantees.
In this paper, we resolve many of the key algorithmic questions regarding robustness, memory efficiency, and differential privacy of tensor decomposition. We propose simple variants of the tensor power method which enjoy these strong properties. We present the first guarantees for online tensor power method which has a linear memory requirement. Moreover, we present a noise calibrated tensor power method with efficient privacy guarantees. At the heart of all these guarantees lies a careful perturbation analysis derived in this paper which improves up on the existing results significantly.