主题：Universality, the New Trend in Development of Optimization Schemes

报告人：Yurii Nesterov, Professor, Catholic University of Louvain

主持人：Yin ZHANG, Presidential Chair Professor, School of Data Science, CUHK-Shenzhen

日期：1 December (Friday), 2023

时间：11:00 AM - 12:00 PM, Beijing Time

形式：Hybrid

地点：103 Meeting Room, Daoyuan Building

SDS视频号直播：

语言：English

摘要：

In the early years of Optimization, the first classical schemes were derived from an abstract concept of approximation (e.g. Gradient method, Newton’s methods, etc.). However, since the development of Complexity Theory for Convex Optimization (Nemirovsky, Yudin 1970’s), the most powerful approaches for constructing efficient (optimal) methods are based on the model of the objective function. This model incorporates the characteristic properties of the corresponding problem class and provides us with a comprehensive information on the behavior of the objective. At the same time, it helps in deriving theoretically unimprovable complexity bounds for the target class.

However, this framework completely neglects the fact that every objective function belongs, at the same time, to many different problem classes. Hence, it should be treated by a method developed for the most appropriate class of problems. However, for the real-life problems, such a choice is seldomly feasible, at least in advance.

In this talk, we discuss several ideas for constructing universal methods, which automatically ensure the best possible convergence rate among appropriate problem classes. The simplest methods of this type adjust to the best power in Holder condition for the target derivative. Our most promising super-universal Regularized Newton’s Method works properly for a wide range of problems, starting from the functions with bounded variation of Hessian up to the functions with Lipschitz continuous third derivative. Thus, being a second-order scheme, it covers all diversity of problems, from the problems traditionally treated by the first-order methods, up to the problems, which are usually attributed to the third-order schemes. For its proper work, no preliminary information on the objective function is needed.

简介：

Yurii Nesterov is a professor at Center for Operations Research and Econometrics (CORE) in Catholic University of Louvain (UCL), Belgium. He received Ph.D. degree (Applied Mathematics) in 1984 at Institute of Control Sciences, Moscow. Starting from 1993 he works at CORE.

His research interests are related to complexity issues and efficient methods for solving various optimization problems. The main results are obtained in Convex Optimization (optimal methods for smooth problems, polynomial-time interior-point methods, smoothing technique for structural optimization, complexity theory for second-order methods, optimization methods for huge-scale problems). He is an author of 6 monographs and more than 150 refereed papers in the leading optimization journals. He got several international prizes and recognitions, among them there are 

• Dantzig Prize from SIAM and Mathematical Programming society (2000),
• John von Neumann Theory Prize from INFORMS (2009),
• SIAM Outstanding paper award (2014)
• Euro Gold Medal from Association of European Operations Research Societies (2016).
• Member of Academia Europaea (2021) and National Academy of Sciences (USA, 2022).
• Lanchester prize from INFROMS (2022)

In 2023, he got the award of World Laureates Association in Computer Sciences or Mathematics.