Optimal recovery of tensor slices
We consider the problem of large scale matrix recovery given side information in the form of additional matrices of conforming dimension. This is a parsimonious model that captures a number of interesting problems including context and location aware recommendations, personalized ‘tag’ learning, dem...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
MLResearch Press
2021
|
| Online Access: | https://hdl.handle.net/1721.1/130460 |
| _version_ | 1826188062310268928 |
|---|---|
| author | Farias, Vivek F. Li, Andrew A. |
| author2 | Sloan School of Management |
| author_facet | Sloan School of Management Farias, Vivek F. Li, Andrew A. |
| author_sort | Farias, Vivek F. |
| collection | MIT |
| description | We consider the problem of large scale matrix recovery given side information in the form of additional matrices of conforming dimension. This is a parsimonious model that captures a number of interesting problems including context and location aware recommendations, personalized ‘tag’ learning, demand learning with side information, etc. Viewing the matrix we seek to recover and the side information we have as slices of a tensor, we consider the problem of Slice Recovery, which is to recover specific slices of a tensor from noisy observations of the tensor. We provide an efficient algorithm to recover slices of structurally ‘simple’ tensors given noisy observations of the tensor’s entries; our definition of simplicity subsumes low-rank tensors for a variety of definitions of tensor rank. Our algorithm is practical for large datasets and provides a significant performance improvement over state of the art incumbent approaches to tensor recovery. We establish theoretical recovery guarantees that under reasonable assumptions are minimax optimal for slice recovery. These guarantees also imply the first minimax optimal guarantees for recovering tensors of low Tucker rank and general noise. Experiments on data from a music streaming service demonstrate the performance and scalability of our algorithm. |
| first_indexed | 2024-09-23T07:54:01Z |
| format | Article |
| id | mit-1721.1/130460 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T07:54:01Z |
| publishDate | 2021 |
| publisher | MLResearch Press |
| record_format | dspace |
| spelling | mit-1721.1/1304602022-09-23T09:29:53Z Optimal recovery of tensor slices Farias, Vivek F. Li, Andrew A. Sloan School of Management Massachusetts Institute of Technology. Operations Research Center We consider the problem of large scale matrix recovery given side information in the form of additional matrices of conforming dimension. This is a parsimonious model that captures a number of interesting problems including context and location aware recommendations, personalized ‘tag’ learning, demand learning with side information, etc. Viewing the matrix we seek to recover and the side information we have as slices of a tensor, we consider the problem of Slice Recovery, which is to recover specific slices of a tensor from noisy observations of the tensor. We provide an efficient algorithm to recover slices of structurally ‘simple’ tensors given noisy observations of the tensor’s entries; our definition of simplicity subsumes low-rank tensors for a variety of definitions of tensor rank. Our algorithm is practical for large datasets and provides a significant performance improvement over state of the art incumbent approaches to tensor recovery. We establish theoretical recovery guarantees that under reasonable assumptions are minimax optimal for slice recovery. These guarantees also imply the first minimax optimal guarantees for recovering tensors of low Tucker rank and general noise. Experiments on data from a music streaming service demonstrate the performance and scalability of our algorithm. 2021-04-12T20:18:40Z 2021-04-12T20:18:40Z 2017-04 2021-04-06T17:44:27Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/130460 Farias, Vivek F. and Andrew A. Li. "Optimal recovery of tensor slices." Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, April 2020, Fort Lauderdale, Florida, MLResearch Press, 2017. © 2017 The Author(s) en http://proceedings.mlr.press/v54/farias17a.html Proceedings of the 20th International Conference on Artificial Intelligence and Statistics Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf MLResearch Press Proceedings of Machine Learning Research |
| spellingShingle | Farias, Vivek F. Li, Andrew A. Optimal recovery of tensor slices |
| title | Optimal recovery of tensor slices |
| title_full | Optimal recovery of tensor slices |
| title_fullStr | Optimal recovery of tensor slices |
| title_full_unstemmed | Optimal recovery of tensor slices |
| title_short | Optimal recovery of tensor slices |
| title_sort | optimal recovery of tensor slices |
| url | https://hdl.handle.net/1721.1/130460 |
| work_keys_str_mv | AT fariasvivekf optimalrecoveryoftensorslices AT liandrewa optimalrecoveryoftensorslices |