Applications and limits of convex optimization
Every algorithmic learning problem becomes vastly more tractable when reduced to a convex program, yet few can be simplified this way. At the heart of this thesis are two hard problems with unexpected convex reformulations. The Paulsen problem, a longstanding open problem in operator theory, was rec...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Massachusetts Institute of Technology
2022
|
| Online Access: | https://hdl.handle.net/1721.1/145023 |
| _version_ | 1826217363837550592 |
|---|---|
| author | Hamilton, Linus |
| author2 | Moitra, Ankur |
| author_facet | Moitra, Ankur Hamilton, Linus |
| author_sort | Hamilton, Linus |
| collection | MIT |
| description | Every algorithmic learning problem becomes vastly more tractable when reduced to a convex program, yet few can be simplified this way. At the heart of this thesis are two hard problems with unexpected convex reformulations. The Paulsen problem, a longstanding open problem in operator theory, was recently resolved by Kwok et al [40]. We use a convex program due to Barthe to present a dramatically simpler proof with an accompanying efficient algorithm that also achieves a better bound. Next, we examine the related operator scaling problem, whose fastest known algorithm uses convex optimization in non-Euclidean space. We expose a fundamental obstruction to such techniques by proving that, under realistic noise conditions, hyperbolic space admits no analogue of Nesterov’s accelerated gradient descent. Finally, we generalize Bresler’s structure learning algorithm from Ising models to arbitrary graphical models. We compare our results to a recent convex programming reformulation of the same problem. Notably, in variants of the problem where one only receives partial samples, our combinatorial algorithm is almost unaffected, whereas the convex approach fails to get off the ground. |
| first_indexed | 2024-09-23T17:02:29Z |
| format | Thesis |
| id | mit-1721.1/145023 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T17:02:29Z |
| publishDate | 2022 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1450232022-08-30T03:01:24Z Applications and limits of convex optimization Hamilton, Linus Moitra, Ankur Massachusetts Institute of Technology. Department of Mathematics Every algorithmic learning problem becomes vastly more tractable when reduced to a convex program, yet few can be simplified this way. At the heart of this thesis are two hard problems with unexpected convex reformulations. The Paulsen problem, a longstanding open problem in operator theory, was recently resolved by Kwok et al [40]. We use a convex program due to Barthe to present a dramatically simpler proof with an accompanying efficient algorithm that also achieves a better bound. Next, we examine the related operator scaling problem, whose fastest known algorithm uses convex optimization in non-Euclidean space. We expose a fundamental obstruction to such techniques by proving that, under realistic noise conditions, hyperbolic space admits no analogue of Nesterov’s accelerated gradient descent. Finally, we generalize Bresler’s structure learning algorithm from Ising models to arbitrary graphical models. We compare our results to a recent convex programming reformulation of the same problem. Notably, in variants of the problem where one only receives partial samples, our combinatorial algorithm is almost unaffected, whereas the convex approach fails to get off the ground. Ph.D. 2022-08-29T16:27:54Z 2022-08-29T16:27:54Z 2022-05 2022-06-07T15:33:53.299Z Thesis https://hdl.handle.net/1721.1/145023 In Copyright - Educational Use Permitted Copyright MIT http://rightsstatements.org/page/InC-EDU/1.0/ application/pdf Massachusetts Institute of Technology |
| spellingShingle | Hamilton, Linus Applications and limits of convex optimization |
| title | Applications and limits of convex optimization |
| title_full | Applications and limits of convex optimization |
| title_fullStr | Applications and limits of convex optimization |
| title_full_unstemmed | Applications and limits of convex optimization |
| title_short | Applications and limits of convex optimization |
| title_sort | applications and limits of convex optimization |
| url | https://hdl.handle.net/1721.1/145023 |
| work_keys_str_mv | AT hamiltonlinus applicationsandlimitsofconvexoptimization |