3

Nous proposons une borne inférieure sur le nombre d’appels aux oracles nécessaire pour résoudre le problème de minimisation de risque empirique bi-niveaux. Nous montrons que SRBA, une adaptation bi-niveaux de SARAH, est quasi-optimale en terme de complexité, de la même manière que son homologue simple niveau.

Nous proposons un nouveau cadre qui permet d’adapter facilement n’importe quel algorithme stochastique pour des problèmes bi-niveaux. Dans ce cadre, on proposo SOBA, une adaptation de la SGD, et SABA, une adaptation de SAGA.