The complexity of optimization beyond convexity
Abstract/Contents
- Abstract
- Gradient descent variants are the workhorse of modern machine learning and large-scale optimization more broadly, where objective functions are often non-convex. Could there be better general-purpose optimization methods than gradient descent, or is it in some sense unimprovable? This thesis addresses this question from the perspective of the worst-case oracle complexity of finding near-stationary points (i.e., points with small gradient norm) of smooth and possibly non-convex functions. On the negative side, we prove a lower bound showing that gradient descent is unimprovable for a natural class of problems. We further prove the worst-case optimality of stochastic gradient descent, recursive variance reduction, cubic regularization of Newton's method and high-order tensor methods, in each case under the set of assumptions for which the method was designed. To prove our lower bounds we extend theory of information-based oracle complexity to the realm of non-convex optimization. On the positive side, we use classical techniques from optimization (namely Nesterov momentum and Krylov subspace methods) to accelerate gradient descent in a large subclass of non-convex problems with higher-order smoothness. Furthermore, we show how recently proposed variance reduction techniques can further improve stochastic gradient descent when stochastic Hessian-vector products available
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 | Carmon, Yair Menachem |
|---|---|
| Degree supervisor | Duchi, John |
| Thesis advisor | Duchi, John |
| Thesis advisor | Boyd, Stephen P |
| Thesis advisor | Candès, Emmanuel J. (Emmanuel Jean) |
| Thesis advisor | Sidford, Aaron |
| Degree committee member | Boyd, Stephen P |
| Degree committee member | Candès, Emmanuel J. (Emmanuel Jean) |
| Degree committee member | Sidford, Aaron |
| Associated with | Stanford University, Department of Electrical Engineering |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Yair Carmon |
|---|---|
| Note | Submitted to the Department of Electrical Engineering |
| Thesis | Thesis Ph.D. Stanford University 2020 |
| Location | electronic resource |
Access conditions
- Copyright
- © 2020 by Yair Menachem Carmon
- 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...