Borne inférieure de compléxité et algorithme quasi-optimal pour la minimisation de risque empirique bi-niveaux

Abstract

L’optimisation à deux niveaux est un thème animant de plus en plus les communautés d’apprentissage statistique et de traitement du signal. Dans de nombreuses applications en apprentissage, les fonctions internes et externes sont des moyennes empiriques. Avec une grande quantité de données, les méthodes stochastiques sont des méthodes de choix pour la minimisation de risque empirique. Nous proposons ici une borne inférieure sur le nombre d’appels aux oracles nécessaire pour résoudre ce problème avec une précision $\epsilon$. Aussi, nous donnons un algorithme dont la complexité atteint cette borne inférieure. En ce sens, cet algorithme est quasi-optimal.

Type
Publication
XXIXème Colloque Francophone de Traitement du Signal et des Images GRETSI