Convex optimization: algorithms and complexity (Q2809807)

This monographs is based on the lectures given in Princeton University in 2013 and 2014 and presents the main complexity theorems in convex optimization and their corresponding algorithms. Starting from the fundamental theory of black-box optimization, the material progresses towards recent advances in structural optimization and stochastic optimization. The presentation of black-box optimization includes the analysis of cutting plane methods, as well as gradient descent schemes. The author pays special attention to non-Euclidean settings and discusses their relevance in machine learning. A gentle introduction to structural optimization, saddle-point mirror prox (Nemirovski's alternative to Nesterov's smoothing), and a concise description of interior point methods has been provided in the book. Stochastic gradient descent, mini-batches, random coordinate descent, and sublinear algorithms have been discussed in stochastic optimization. At the end, the author briefly touches upon convex relaxation of combinatorial problems and the use of randomness to round solutions, as well as random walks based methods.