New primitives for convex optimization and graph algorithms
Abstract/Contents
- Abstract
- Iterative methods, especially those from convex optimization, form the basis of much of the modern algorithmic landscape. The success of such methods relies on their generality: methods such as gradient descent and Newton's method typically converge to high-quality minimizers with only minimal assumptions placed on the objective. However, in many real-world settings the theoretical guarantees obtained by such algorithms are often insufficient to see use in practice. This thesis addresses this issue by developing methods for convex optimization and graph algorithms by exploiting problem-specific structure. Part I gives a state-of-the-art algorithm for solving Laplacian linear systems, as well as a faster algorithm for minimum-cost flow. Our results are achieved through novel combinations of classical iterative methods from convex optimization with graph-based data structures and preconditioners. Part II gives new algorithms for several generic classes of structured convex optimization problems. We give near-optimal methods for minimizing convex functions admitting a ball-optimization oracle and minimizing the maximum of N convex functions, as well as new algorithms for projection-efficient and composite convex minimization. Our results are achieved through a more refined understanding of classical accelerated gradient methods, and give new algorithms for a variety of important machine learning tasks such as logistic regression and hard margin SVMs. Part III discusses advancements in algorithms for the discrete optimal transport problem, a task which has seen enormous interest in recent years due to new applications in deep learning. We give simple and parallel algorithms for approximating discrete optimal transport, and additionally demonstrate that these algorithms can be implemented in space-bounded and streaming settings. By leveraging our machinery further, we also give improved pass-complexity bounds for graph optimization problems (such as bipartite matching and transshipment) in the semi-streaming model.
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 | 2022; ©2022 |
| Publication date | 2022; 2022 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Jambulapati, Arun |
|---|---|
| Degree supervisor | Gerritsen, Margot (Margot G.) |
| Degree supervisor | Iaccarino, Gianluca |
| Thesis advisor | Gerritsen, Margot (Margot G.) |
| Thesis advisor | Iaccarino, Gianluca |
| Thesis advisor | Sidford, Aaron |
| Degree committee member | Sidford, Aaron |
| Associated with | Stanford University, Institute for Computational and Mathematical Engineering |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Arun Jambulapati. |
|---|---|
| Note | Submitted to the Institute for Computational and Mathematical Engineering. |
| Thesis | Thesis Ph.D. Stanford University 2022. |
| Location | https://purl.stanford.edu/nb901rw0203 |
Access conditions
- Copyright
- © 2022 by Arun Jambulapati
- License
- This work is licensed under a Creative Commons Attribution Non Commercial Share Alike 3.0 Unported license (CC BY-NC-SA).
Also listed in
Loading usage metrics...