2. Červenec 2022
We develop the first fast spectral algorithm to decompose a random third-order tensor over of rank up to O(d^3/2/polylog(d)) . Our algorithm only involves simple linear algebra operations and can recover all components in time O(d^6.05) under the current matrix multiplication time. Prior to this work, comparable guarantees could only be achieved via sum-of-squares [Ma, Shi, Steurer 2016]. In contrast, fast algorithms [Hopkins, Schramm, Shi, Steurer 2016] could only decompose tensors of rank at most O(d^4/3/polylog(d)) . Our algorithmic result rests on two key ingredients. A clean lifting of the third-order tensor to a sixth-order tensor, which can be expressed in the language of tensor networks. A careful decomposition of the tensor network into a sequence of rectangular matrix multiplications, which allows us to have a fast implementation of the algorithm.
The conference is held annually since 1988 and has become the leading conference on Learning theory by maintaining a highly selective process for submissions. It is committed in high-quality articles in all theoretical aspects of machine learning and related topics.
Pro uložení prezentace do věčného trezoru hlasovalo 0 diváků, což je 0.0 %
Prezentace na podobné téma, kategorii nebo přednášejícího