Optimal Algorithms for Affinely Constrained, Distributed, Decentralized, Minimax, and High-Order Optimization Problems

Overview

Abstract

Optimization problems are ubiquitous in all quantitative scientific disciplines, from computer science and engineering to operations research and economics. Developing algorithms for solving various optimization problems has been the focus of mathematical research for years. In the last decade, optimization research has become even more popular due to its applications in the rapidly developing field of machine learning.

In this thesis, we discuss a few fundamental and well-studied optimization problem classes: decentralized distributed optimization (Chapters 2 to 4), distributed optimization under similarity (Chapter 5), affinely constrained optimization (Chapter 6), minimax optimization (Chapter 7), and high-order optimization (Chapter 8). For each problem class, we develop the first provably optimal algorithm: the complexity of such an algorithm cannot be improved for the problem class given. The proposed algorithms show state-of-the-art performance in practical applications, which makes them highly attractive for potential generalizations and extensions in the future.

Brief Biography

Dmitry Kovalev is a PhD student at the King Abdullah University of Science and Technology, where he is currently studying Computer Science and doing research in the Visual Computing Center under the supervision of Peter Richtárik. He got his BS degree in Applied Mathematics and Physics at the Moscow Institute of Physics and Technology.