Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Séance de cours

Optimisation du double primaire: méthode extra-gradient

Dans cours

EE-556: Mathematics of data: from theory to computation

This course provides an overview of key advances in continuous optimization and statistical analysis for machine learning. We review recent learning formulations and models as well as their guarantees

Description

Cette séance de cours couvre l'optimisation primaire-duelle, en se concentrant sur la Méthode Extra-Gradient pour résoudre les problèmes d'optimisation min-max. Il traite de différents cas, des algorithmes comme Proximal-Point, Extra-gradient, et Mirror-Prox, des propriétés de convergence, et des applications pour lisser l'optimisation minimax sans contrainte.

Enseignant·e

Volkan Cevher

Volkan Cevher received the B.Sc. (valedictorian) in electrical engineering from Bilkent University in Ankara, Turkey, in 1999 and the Ph.D. in electrical and computer engineering from the Georgia Institute of Technology in Atlanta, GA in 2005. He was a Research Scientist with the University of Maryland, College Park from 2006-2007 and also with Rice University in Houston, TX, from 2008-2009. Currently, he is an Associate Professor at the Swiss Federal Institute of Technology Lausanne and a Faculty Fellow in the Electrical and Computer Engineering Department at Rice University. His research interests include machine learning, signal processing theory, optimization theory and methods, and information theory. Dr. Cevher is an ELLIS fellow and was the recipient of the Google Faculty Research award in 2018, the IEEE Signal Processing Society Best Paper Award in 2016, a Best Paper Award at CAMSAP in 2015, a Best Paper Award at SPARS in 2009, and an ERC CG in 2016 as well as an ERC StG in 2011.

Source officielle

Concepts associés (26)

Optimisation (mathématiques)

L'optimisation est une branche des mathématiques cherchant à modéliser, à analyser et à résoudre analytiquement ou numériquement les problèmes qui consistent à minimiser ou maximiser une fonction sur un ensemble. L’optimisation joue un rôle important en recherche opérationnelle (domaine à la frontière entre l'informatique, les mathématiques et l'économie), dans les mathématiques appliquées (fondamentales pour l'industrie et l'ingénierie), en analyse et en analyse numérique, en statistique pour l’estimation du maximum de vraisemblance d’une distribution, pour la recherche de stratégies dans le cadre de la théorie des jeux, ou encore en théorie du contrôle et de la commande.

Dualité (optimisation)

En théorie de l'optimisation, la dualité ou principe de dualité désigne le principe selon lequel les problèmes d'optimisation peuvent être vus de deux perspectives, le problème primal ou le problème dual, et la solution du problème dual donne une borne inférieure à la solution du problème (de minimisation) primal. Cependant, en général les valeurs optimales des problèmes primal et dual ne sont pas forcément égales : cette différence est appelée saut de dualité. Pour les problèmes en optimisation convexe, ce saut est nul sous contraintes.

Optimisation convexe

vignette|320x320px|Optimisation convexe dans un espace en deux dimensions dans un espace contraint L'optimisation convexe est une sous-discipline de l'optimisation mathématique, dans laquelle le critère à minimiser est convexe et l'ensemble admissible est convexe. Ces problèmes sont plus simples à analyser et à résoudre que les problèmes d'optimisation non convexes, bien qu'ils puissent être NP-difficile (c'est le cas de l'optimisation copositive). La théorie permettant d'analyser ces problèmes ne requiert pas la différentiabilité des fonctions.

Méthode du gradient conjugué

vignette|Illustration de la méthode du gradient conjugué. En analyse numérique, la méthode du gradient conjugué est un algorithme pour résoudre des systèmes d'équations linéaires dont la matrice est symétrique définie positive. Cette méthode, imaginée en 1950 simultanément par Cornelius Lanczos, Eduard Stiefel et Magnus Hestenes, est une méthode itérative qui converge en un nombre fini d'itérations (au plus égal à la dimension du système linéaire).

Algorithme

thumb|Algorithme de découpe d'un polygone quelconque en triangles (triangulation). Un algorithme est une suite finie et non ambiguë d'instructions et d’opérations permettant de résoudre une classe de problèmes. Le domaine qui étudie les algorithmes est appelé l'algorithmique. On retrouve aujourd'hui des algorithmes dans de nombreuses applications telles que le fonctionnement des ordinateurs, la cryptographie, le routage d'informations, la planification et l'utilisation optimale des ressources, le , le traitement de textes, la bio-informatique L' algorithme peut être mis en forme de façon graphique dans un algorigramme ou organigramme de programmation.

Afficher plus

Séances de cours associées (30)

Méthodes d'optimisation : discussion théorique

Explore les méthodes d'optimisation, y compris les problèmes sans contraintes, la programmation linéaire et les approches heuristiques.

Optimisation du double primaire: méthode extra-gradient

Explore la méthode Extra-Gradient pour l'optimisation Primal-dual, couvrant les problèmes non convexes, les taux de convergence et les performances pratiques.

Techniques d'optimisation : Convexity in Machine Learning

Couvre les techniques d'optimisation dans l'apprentissage automatique, en se concentrant sur la convexité et ses implications pour une résolution efficace des problèmes.

Optimisation sans contraintes : méthode de graduation

Couvre l'optimisation sans contraintes en utilisant la méthode de gradient pour trouver le minimum de la fonction.

Optimisation Primal-dual: Théorie et Calcul

Explore l'optimisation primaire-duelle, la conjugaison des fonctions, la dualité forte, et les méthodes de pénalité quadratique en mathématiques de données.

Afficher plus

Concepts associés (26)

Optimisation (mathématiques)

Dualité (optimisation)

Optimisation convexe

Méthode du gradient conjugué

Algorithme

Afficher plus