Improved Generalization Bound and Learning of Sparsity Patterns for Data-Driven Low-Rank Approximation

Shinsaku Sakaue, Taihei Oki
Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, PMLR 206:1-10, 2023.

Abstract

Learning sketching matrices for fast and accurate low-rank approximation (LRA) has gained increasing attention. Recently, Bartlett, Indyk, and Wagner (COLT 2022) presented a generalization bound for the learning-based LRA. Specifically, for rank-$k$ approximation using an $m \times n$ learned sketching matrix with $s$ non-zeros in each column, they proved an $\tilde O(nsm)$ bound on the fat shattering dimension ($\tilde O$ hides logarithmic factors). We build on their work and make two contributions. (1) We present a better $\tilde O(nsk)$ bound ($k \le m$). En route to obtaining this result, we give a low-complexity Goldberg–Jerrum algorithm for computing pseudo-inverse matrices, which would be of independent interest. (2) We alleviate an assumption of the previous study that sketching matrices have a fixed sparsity pattern. We prove that learning positions of non-zeros increases the fat shattering dimension only by $O(ns\log n)$. In addition, experiments confirm the practical benefit of learning sparsity patterns.

Cite this Paper

BibTeX
@InProceedings{pmlr-v206-sakaue23a, title = {Improved Generalization Bound and Learning of Sparsity Patterns for Data-Driven Low-Rank Approximation}, author = {Sakaue, Shinsaku and Oki, Taihei}, booktitle = {Proceedings of The 26th International Conference on Artificial Intelligence and Statistics}, pages = {1--10}, year = {2023}, editor = {Ruiz, Francisco and Dy, Jennifer and van de Meent, Jan-Willem}, volume = {206}, series = {Proceedings of Machine Learning Research}, month = {25--27 Apr}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v206/sakaue23a/sakaue23a.pdf}, url = {https://proceedings.mlr.press/v206/sakaue23a.html}, abstract = {Learning sketching matrices for fast and accurate low-rank approximation (LRA) has gained increasing attention. Recently, Bartlett, Indyk, and Wagner (COLT 2022) presented a generalization bound for the learning-based LRA. Specifically, for rank-$k$ approximation using an $m \times n$ learned sketching matrix with $s$ non-zeros in each column, they proved an $\tilde O(nsm)$ bound on the fat shattering dimension ($\tilde O$ hides logarithmic factors). We build on their work and make two contributions. (1) We present a better $\tilde O(nsk)$ bound ($k \le m$). En route to obtaining this result, we give a low-complexity Goldberg–Jerrum algorithm for computing pseudo-inverse matrices, which would be of independent interest. (2) We alleviate an assumption of the previous study that sketching matrices have a fixed sparsity pattern. We prove that learning positions of non-zeros increases the fat shattering dimension only by $O(ns\log n)$. In addition, experiments confirm the practical benefit of learning sparsity patterns.} }
Endnote
%0 Conference Paper %T Improved Generalization Bound and Learning of Sparsity Patterns for Data-Driven Low-Rank Approximation %A Shinsaku Sakaue %A Taihei Oki %B Proceedings of The 26th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2023 %E Francisco Ruiz %E Jennifer Dy %E Jan-Willem van de Meent %F pmlr-v206-sakaue23a %I PMLR %P 1--10 %U https://proceedings.mlr.press/v206/sakaue23a.html %V 206 %X Learning sketching matrices for fast and accurate low-rank approximation (LRA) has gained increasing attention. Recently, Bartlett, Indyk, and Wagner (COLT 2022) presented a generalization bound for the learning-based LRA. Specifically, for rank-$k$ approximation using an $m \times n$ learned sketching matrix with $s$ non-zeros in each column, they proved an $\tilde O(nsm)$ bound on the fat shattering dimension ($\tilde O$ hides logarithmic factors). We build on their work and make two contributions. (1) We present a better $\tilde O(nsk)$ bound ($k \le m$). En route to obtaining this result, we give a low-complexity Goldberg–Jerrum algorithm for computing pseudo-inverse matrices, which would be of independent interest. (2) We alleviate an assumption of the previous study that sketching matrices have a fixed sparsity pattern. We prove that learning positions of non-zeros increases the fat shattering dimension only by $O(ns\log n)$. In addition, experiments confirm the practical benefit of learning sparsity patterns.
APA
Sakaue, S. & Oki, T.. (2023). Improved Generalization Bound and Learning of Sparsity Patterns for Data-Driven Low-Rank Approximation. Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 206:1-10 Available from https://proceedings.mlr.press/v206/sakaue23a.html.

Related Material