Smoothed Online Learning: Theory and Applications
Many of the algorithms and theoretical results surrounding modern machine learning are predicated on the assumption that data are independent and identically distributed. Motivated by the numerous applications that do not satisfy this assumption, many researchers have been interested in relaxations...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Massachusetts Institute of Technology
2024
|
| Online Access: | https://hdl.handle.net/1721.1/155382 |
| _version_ | 1811073319011614720 |
|---|---|
| author | Block, Adam B. |
| author2 | Rakhlin, Alexander |
| author_facet | Rakhlin, Alexander Block, Adam B. |
| author_sort | Block, Adam B. |
| collection | MIT |
| description | Many of the algorithms and theoretical results surrounding modern machine learning are predicated on the assumption that data are independent and identically distributed. Motivated by the numerous applications that do not satisfy this assumption, many researchers have been interested in relaxations of this condition, with online learning being the weakest such assumption. In this setting, the learner observes data points one at a time and makes predictions, before incorporating the data into a training set with the goal of predicting new data points as well as possible. Due to the lack of assumptions on the data, this setting is both computationally and statistically challenging. In this thesis, we investigate the statistical rates and efficient algorithms achievable when the data are constrained in a natural way motivated by the smoothed analysis of algorithms. The first part covers the statistical rates achievable by an arbitrary algorithm without regard to efficiency, covering both the fully adversarial setting and the constrained setting in which improved rates are possible. The second part of the thesis focuses on efficient algorithms for this constrained setting, as well as special cases where bounds can be improved under additional structure. Finally, in the third part we investigate applications of these techniques to sequential decision making, robotics, and differential privacy. We introduce a number of novel techniques, including a Gaussian anti-concentration inequality and a new norm comparison for dependent data. |
| first_indexed | 2024-09-23T09:31:13Z |
| format | Thesis |
| id | mit-1721.1/155382 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T09:31:13Z |
| publishDate | 2024 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1553822024-06-28T03:53:23Z Smoothed Online Learning: Theory and Applications Block, Adam B. Rakhlin, Alexander Massachusetts Institute of Technology. Department of Mathematics Many of the algorithms and theoretical results surrounding modern machine learning are predicated on the assumption that data are independent and identically distributed. Motivated by the numerous applications that do not satisfy this assumption, many researchers have been interested in relaxations of this condition, with online learning being the weakest such assumption. In this setting, the learner observes data points one at a time and makes predictions, before incorporating the data into a training set with the goal of predicting new data points as well as possible. Due to the lack of assumptions on the data, this setting is both computationally and statistically challenging. In this thesis, we investigate the statistical rates and efficient algorithms achievable when the data are constrained in a natural way motivated by the smoothed analysis of algorithms. The first part covers the statistical rates achievable by an arbitrary algorithm without regard to efficiency, covering both the fully adversarial setting and the constrained setting in which improved rates are possible. The second part of the thesis focuses on efficient algorithms for this constrained setting, as well as special cases where bounds can be improved under additional structure. Finally, in the third part we investigate applications of these techniques to sequential decision making, robotics, and differential privacy. We introduce a number of novel techniques, including a Gaussian anti-concentration inequality and a new norm comparison for dependent data. Ph.D. 2024-06-27T19:49:18Z 2024-06-27T19:49:18Z 2024-05 2024-05-15T16:20:10.126Z Thesis https://hdl.handle.net/1721.1/155382 Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) Copyright retained by author(s) https://creativecommons.org/licenses/by-nc-nd/4.0/ application/pdf Massachusetts Institute of Technology |
| spellingShingle | Block, Adam B. Smoothed Online Learning: Theory and Applications |
| title | Smoothed Online Learning: Theory and Applications |
| title_full | Smoothed Online Learning: Theory and Applications |
| title_fullStr | Smoothed Online Learning: Theory and Applications |
| title_full_unstemmed | Smoothed Online Learning: Theory and Applications |
| title_short | Smoothed Online Learning: Theory and Applications |
| title_sort | smoothed online learning theory and applications |
| url | https://hdl.handle.net/1721.1/155382 |
| work_keys_str_mv | AT blockadamb smoothedonlinelearningtheoryandapplications |