Scalable Binary Tensor Factorization

Beyza Ermiş Boğaziçi University, Guillaume Bouchard Xerox Research Centre Europe
Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, PMLR R12:815-822, 2014.

Abstract

Binary matrices and tensors are popular data structures that need to be efficiently approxi- mated by low-rank representations. A standard approach is to minimize the logistic loss, well suited for binary data. In many cases, the num- ber m of non-zero elements in the tensor is much smaller than the total number n of possible en- tries in the tensor. This creates a problem for large tensors because the computation of the lo- gistic loss has a linear time complexity with n. In this work, we show that an alternative approach is to minimize the quadratic loss (root mean square error) which leads to algorithms with a training time complexity that is reduced from O(n) to O(m), as proposed earlier in the restricted case of alternating least-square algorithms. In addi- tion, we propose and study a greedy algorithm that partitions the tensor into smaller tensors, each approximated by a quadratic upper bound. This technique provides a time-accuracy trade- off between a fast but approximate algorithm and an accurate but slow algorithm. We show that this technique leads to a considerable speedup in learning of real world tensors.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR12-university14w, title = {Scalable Binary Tensor Factorization}, author = {University, Beyza Ermi\c{s} Bo\u{g}azi{\c{c}}i and Europe, Guillaume Bouchard Xerox Research Centre}, booktitle = {Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence}, pages = {815--822}, year = {2014}, editor = {Zhang, Nevin L. and Tian, Jin}, volume = {R12}, series = {Proceedings of Machine Learning Research}, month = {23--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r12/main/assets/university14w/university14w.pdf}, url = {https://proceedings.mlr.press/r12/university14w.html}, abstract = {Binary matrices and tensors are popular data structures that need to be efficiently approxi- mated by low-rank representations. A standard approach is to minimize the logistic loss, well suited for binary data. In many cases, the num- ber m of non-zero elements in the tensor is much smaller than the total number n of possible en- tries in the tensor. This creates a problem for large tensors because the computation of the lo- gistic loss has a linear time complexity with n. In this work, we show that an alternative approach is to minimize the quadratic loss (root mean square error) which leads to algorithms with a training time complexity that is reduced from O(n) to O(m), as proposed earlier in the restricted case of alternating least-square algorithms. In addi- tion, we propose and study a greedy algorithm that partitions the tensor into smaller tensors, each approximated by a quadratic upper bound. This technique provides a time-accuracy trade- off between a fast but approximate algorithm and an accurate but slow algorithm. We show that this technique leads to a considerable speedup in learning of real world tensors.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Scalable Binary Tensor Factorization %A Beyza Ermiş Boğaziçi University %A Guillaume Bouchard Xerox Research Centre Europe %B Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2014 %E Nevin L. Zhang %E Jin Tian %F pmlr-vR12-university14w %I PMLR %P 815--822 %U https://proceedings.mlr.press/r12/university14w.html %V R12 %X Binary matrices and tensors are popular data structures that need to be efficiently approxi- mated by low-rank representations. A standard approach is to minimize the logistic loss, well suited for binary data. In many cases, the num- ber m of non-zero elements in the tensor is much smaller than the total number n of possible en- tries in the tensor. This creates a problem for large tensors because the computation of the lo- gistic loss has a linear time complexity with n. In this work, we show that an alternative approach is to minimize the quadratic loss (root mean square error) which leads to algorithms with a training time complexity that is reduced from O(n) to O(m), as proposed earlier in the restricted case of alternating least-square algorithms. In addi- tion, we propose and study a greedy algorithm that partitions the tensor into smaller tensors, each approximated by a quadratic upper bound. This technique provides a time-accuracy trade- off between a fast but approximate algorithm and an accurate but slow algorithm. We show that this technique leads to a considerable speedup in learning of real world tensors. %Z Reissued by PMLR on 04 October 2026.
APA
University, B.E.B. & Europe, G.B.X.R.C.. (2014). Scalable Binary Tensor Factorization. Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R12:815-822 Available from https://proceedings.mlr.press/r12/university14w.html. Reissued by PMLR on 04 October 2026.

Related Material