Approximately Optimal Core Shapes for Tensor Decompositions

Mehrdad Ghadiri, Matthew Fahrbach, Gang Fu, Vahab Mirrokni
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:11237-11254, 2023.

Abstract

This work studies the combinatorial optimization problem of finding an optimal core tensor shape, also called multilinear rank, for a size-constrained Tucker decomposition. We give an algorithm with provable approximation guarantees for its reconstruction error via connections to higher-order singular values. Specifically, we introduce a novel Tucker packing problem, which we prove is NP-hard, and give a polynomial-time approximation scheme based on a reduction to the 2-dimensional knapsack problem with a matroid constraint. We also generalize our techniques to tree tensor network decompositions. We implement our algorithm using an integer programming solver, and show that its solution quality is competitive with (and sometimes better than) the greedy algorithm that uses the true Tucker decomposition loss at each step, while also running up to 1000x faster.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-ghadiri23a, title = {Approximately Optimal Core Shapes for Tensor Decompositions}, author = {Ghadiri, Mehrdad and Fahrbach, Matthew and Fu, Gang and Mirrokni, Vahab}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {11237--11254}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/ghadiri23a/ghadiri23a.pdf}, url = {https://proceedings.mlr.press/v202/ghadiri23a.html}, abstract = {This work studies the combinatorial optimization problem of finding an optimal core tensor shape, also called multilinear rank, for a size-constrained Tucker decomposition. We give an algorithm with provable approximation guarantees for its reconstruction error via connections to higher-order singular values. Specifically, we introduce a novel Tucker packing problem, which we prove is NP-hard, and give a polynomial-time approximation scheme based on a reduction to the 2-dimensional knapsack problem with a matroid constraint. We also generalize our techniques to tree tensor network decompositions. We implement our algorithm using an integer programming solver, and show that its solution quality is competitive with (and sometimes better than) the greedy algorithm that uses the true Tucker decomposition loss at each step, while also running up to 1000x faster.} }
Endnote
%0 Conference Paper %T Approximately Optimal Core Shapes for Tensor Decompositions %A Mehrdad Ghadiri %A Matthew Fahrbach %A Gang Fu %A Vahab Mirrokni %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-ghadiri23a %I PMLR %P 11237--11254 %U https://proceedings.mlr.press/v202/ghadiri23a.html %V 202 %X This work studies the combinatorial optimization problem of finding an optimal core tensor shape, also called multilinear rank, for a size-constrained Tucker decomposition. We give an algorithm with provable approximation guarantees for its reconstruction error via connections to higher-order singular values. Specifically, we introduce a novel Tucker packing problem, which we prove is NP-hard, and give a polynomial-time approximation scheme based on a reduction to the 2-dimensional knapsack problem with a matroid constraint. We also generalize our techniques to tree tensor network decompositions. We implement our algorithm using an integer programming solver, and show that its solution quality is competitive with (and sometimes better than) the greedy algorithm that uses the true Tucker decomposition loss at each step, while also running up to 1000x faster.
APA
Ghadiri, M., Fahrbach, M., Fu, G. & Mirrokni, V.. (2023). Approximately Optimal Core Shapes for Tensor Decompositions. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:11237-11254 Available from https://proceedings.mlr.press/v202/ghadiri23a.html.

Related Material