Permutation Search of Tensor Network Structures via Local Sampling
Recent works put much effort into tensor network structure search (TN-SS),
aiming to select suitable tensor network (TN) structures, involving the
TN-ranks, formats, and so on, for the decomposition or learning tasks. In this
paper, we consider a practical variant of TN-SS, dubbed TN permutation search
(TN-PS), in which we search for good mappings from tensor modes onto TN
vertices (core tensors) for compact TN representations. We conduct a
theoretical investigation of TN-PS and propose a practically-efficient
algorithm to resolve the problem. Theoretically, we prove the counting and
metric properties of search spaces of TN-PS, analyzing for the first time the
impact of TN structures on these unique properties. Numerically, we propose a
novel meta-heuristic algorithm, in which the searching is done by randomly
sampling in a neighborhood established in our theory, and then recurrently
updating the neighborhood until convergence. Numerical results demonstrate that
the new algorithm can reduce the required model size of TNs in extensive
benchmarks, implying the improvement in the expressive power of TNs.
Furthermore, the computational cost for the new algorithm is significantly less
than that in~\cite{li2020evolutionary}.