Primal-Dual Approaches in
Online Algorithms, Algorithmic Game Theory and Online Learning
Date: 10h30, 7th June 2019
Place: Tour 26 – 1er étage – couloir 25/26 – salle 105
Sorbonne université
4 place de Jussieu, Paris (métro Jussieu)
Primal-dual is an elegant and powerful method in optimization and in the design of algorithms. The main idea of the method is to construct feasible primal and dual solutions interactively and an algorithm, together with the analysis, are derived naturally from the primal-dual interaction. In this thesis, we present primal-dual approaches as unified techniques in order to study and build connections between the domains of Online Algorithms, Algorithmic Game Theory and Online Learning.
Primal-duale est une méthode élégante et puissante en optimisation et en algorithmique. La méthode consiste à établir de manière interactive des solutions primals et duales, puis un algorithme, ainsi que son analyse, sont guidés naturellement par l'interaction primal-duale. Dans cette habilitation, nous présentons les approches primal-duales comme techniques unifiées afin d'étudier et de développer des liens entre les domaines de l'algorithmique en ligne, de la théorie des jeux algorithmiques et de l'apprentissage en ligne.
Primal-dual là một phương pháp đẹp và hiệu quả trong tối ưu và trong thiết kế các thuật toán. Ý tưởng chính của phương pháp là xây dựng các nghiệm đối ngẫu và sau đó, thuật toán, cùng với phân tích, sẽ dần dần hình thành từ những tương tác đối ngẫu. Trong luận án này, chúng tôi trình bày các phương pháp đối ngẫu như những kỹ thuật thống nhất để nghiên cứu và kết nối các lĩnh vực: Thuật toán trực tuyến, Lý thuyết trò chơi thuật toán và Học máy trực tuyến.