Matrix estimation with adaptive samples
Abstract/Contents
- Abstract
- Datasets commonly have missing values, and in many applications, such as recommendation systems, supervised learning, and causal inference, the data can be modeled as a partially observed matrix and the missing values are imputed via a matrix estimation procedure. Most prior literature focuses on the case when samples are missing uniformly at random. However, in certain applications, the decision-maker can choose which entries of the matrix are observed. In the first part of this dissertation, we show theoretical guarantees on column space recovery of a matrix that is growing in one dimension (new columns are added), where the decision-maker can observe a small number of entries of each column, using either random or active sampling. We demonstrate that the theoretically-motivated active sampling strategy can empirically lead to better estimation of not only the column space, but of the entire matrix. In the second part of this dissertation, we study a related problem where the decision of which entries of each new column to observe is modeled as a multi-armed semi-bandit problem, where we allow the decision-maker to choose multiple actions in each round. We use our matrix estimation techniques to provide regret guarantees when the arm selection is performed via the well-known Thompson sampling framework
Description
| Type of resource | text |
|---|---|
| Form | electronic resource; remote; computer; online resource |
| Extent | 1 online resource |
| Place | California |
| Place | [Stanford, California] |
| Publisher | [Stanford University] |
| Copyright date | 2020; ©2020 |
| Publication date | 2020; 2020 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Kim, Carolyn |
|---|---|
| Degree supervisor | Bayati, Mohsen |
| Degree supervisor | Leskovec, Jurij |
| Thesis advisor | Bayati, Mohsen |
| Thesis advisor | Leskovec, Jurij |
| Thesis advisor | Baiocchi, Michael |
| Thesis advisor | Brunskill, Emma |
| Degree committee member | Baiocchi, Michael |
| Degree committee member | Brunskill, Emma |
| Associated with | Stanford University, Computer Science Department |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Carolyn Kim |
|---|---|
| Note | Submitted to the Computer Science Department |
| Thesis | Thesis Ph.D. Stanford University 2020 |
| Location | https://purl.stanford.edu/xh148jh6142 |
Access conditions
- Copyright
- © 2020 by Carolyn Kim
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...