Méthode des poids multiplicatifs

Comme l'algorithme est générique, sa description et son contexte d'utilisation sont vagues et doivent être précisés pour chaque application.

Le processus a lieu en T rondes, avec n experts. Le coût des décisions à la ronde t est décrit par un vecteur m(t) (m_i(t) est le coût de la décision de l'expert i). On note ${\displaystyle w_{i}(t)}$ le poids de l'expert i à la ronde t. La méthode est la suivante[4].

Initialisation: Choisir un réel ${\displaystyle \eta \leq 1/2}$. Associer à chaque expert un poids ${\displaystyle w_{i}(1):=1}$.

Pour t allant de 1 à T :

• Choisir une décision, selon la distribution de probabilité ${\displaystyle p(t)=\{w_{1}(t)/\Phi (t),...,w_{n}(t)/\Phi (t)\}}$ où ${\displaystyle \Phi (t)=\sum _{i}w_{i}(t)}$.
• Observer le vecteur de coûts ${\displaystyle m(t)}$.
• Mettre à jour les poids de la façon suivante: pour tout expert i, ${\displaystyle w_{i}(t+1)=w_{i}(t)(1-\eta m_{i}(t))}$.

Pour tout choix d'expert i, le coût total payé par l'algorithme est majoré par une fonction du coût payé si l'on fait le choix de l'expert i dès le départ. Cette fonction est affine, avec un facteur multiplicatif inférieur à 2 et un facteur additif de l'ordre du logarithme de n. Plus précisément, avec les notations précédentes, pour tout i, si ${\displaystyle \eta \leq 1/2}$ et ${\displaystyle m_{i}(t)\in [-1,1]}$ pour tout i et t :

${\displaystyle \sum _{t=1}^{T}m(t)p(t)\leq \sum _{t=1}^{T}m_{i}(t)+\eta \sum _{t=1}^{T}|m_{i}(t)|+{\frac {\log n}{\eta }}.}$

On compte de nombreuses applications, spécialisations et algorithmes proches[4] - [3].

• L'algorithme fictitious play (en) en théorie des jeux. Dans ce cadre, les experts représente des stratégies pour l'adversaire[3].
• En apprentissage, l'algorithme de boosting Adaboost, mais aussi l'algorithme winnow (en).
• La résolution rapide de certains problème d'optimisation linéaire, notamment le problème de flot multi-commodités.
• Des algorithmes d'approximation de ratio log(n) pour de nombreux problèmes algorithmiques NP-difficiles.
• Des algorithmes pour l'optimisation convexe en ligne.
• Une méthode de dérandomisation pour la géométrie algorithmique.