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.