Tensors, sparse problems and conditional hardness
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2018.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2019
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/120418 |
| _version_ | 1826205375230115840 |
|---|---|
| author | Persu, Elena-Mădălina |
| author2 | Ankur Moitra. |
| author_facet | Ankur Moitra. Persu, Elena-Mădălina |
| author_sort | Persu, Elena-Mădălina |
| collection | MIT |
| description | Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2018. |
| first_indexed | 2024-09-23T13:11:41Z |
| format | Thesis |
| id | mit-1721.1/120418 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T13:11:41Z |
| publishDate | 2019 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1204182019-04-11T10:20:22Z Tensors, sparse problems and conditional hardness Persu, Elena-Mădălina Ankur Moitra. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2018. Cataloged from PDF version of thesis. Includes bibliographical references (pages 101-108). In this thesis we study the interplay between theoretical computer science and machine learning in three different directions. First, we make a connection between two ubiquitous sparse problems: Sparse Principal Component Analysis (SPCA) and Sparse Linear Regression (SLR). We show how to efficiently transform a blackbox solver for SLR into an algorithm for SPCA. Assuming the SLR solver satisfies prediction error guarantees achieved by existing efficient algorithms such as those based on the Lasso, we show that the SPCA algorithm derived from it achieves state of the art performance, matching guarantees for testing and for support recovery under the single spiked covariance model as obtained by the current best polynomial-time algorithms. Second, we push forward the study of linear algebra properties of tensors by giving a tensor rank detection gadget for tensors in the smoothed model. Tensors have had a tremendous impact and have been extensively applied over the past few years to a wide range of machine learning problems for example in developing estimators for latent variable models, in independent component analysis or blind source separation. Unfortunately, their theoretical properties are still not well understood. We make a step in that direction. Third, we show that many recent conditional lower bounds for a wide variety of problems in combinatorial pattern matching, graph algorithms, data structures and machine learning, including gradient computation in average case neural networks, are true under significantly weaker assumptions. This highlights that the intuition from theoretical computer science can not only help us develop faster practical algorithms but also give us a better understanding of why faster algorithms may not exist. by Elena-Mădălina Persu. Ph. D. 2019-02-14T15:49:48Z 2019-02-14T15:49:48Z 2018 2018 Thesis http://hdl.handle.net/1721.1/120418 1084476376 eng MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission. http://dspace.mit.edu/handle/1721.1/7582 108 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Persu, Elena-Mădălina Tensors, sparse problems and conditional hardness |
| title | Tensors, sparse problems and conditional hardness |
| title_full | Tensors, sparse problems and conditional hardness |
| title_fullStr | Tensors, sparse problems and conditional hardness |
| title_full_unstemmed | Tensors, sparse problems and conditional hardness |
| title_short | Tensors, sparse problems and conditional hardness |
| title_sort | tensors sparse problems and conditional hardness |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/120418 |
| work_keys_str_mv | AT persuelenamadalina tensorssparseproblemsandconditionalhardness |