2024-04-18-dagreou24a.md

title	software	abstract	layout	series	publisher	issn	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_author	author	date	address	container-title	volume	genre	issued	pdf	extras
A Lower Bound and a Near-Optimal Algorithm for Bilevel Empirical Risk Minimization	https://github.com/benchopt/benchmark_bilevel	Bilevel optimization problems, which are problems where two optimization problems are nested, have more and more applications in machine learning. In many practical cases, the upper and the lower objectives correspond to empirical risk minimization problems and therefore have a sum structure. In this context, we propose a bilevel extension of the celebrated SARAH algorithm. We demonstrate that the algorithm requires $O((n+m)^{1/2}\epsilon^{-1})$ oracle calls to achieve $\epsilon$-stationarity with $n+m$ the total number of samples, which improves over all previous bilevel algorithms. Moreover, we provide a lower bound on the number of oracle calls required to get an approximate stationary point of the objective function of the bilevel problem. This lower bound is attained by our algorithm, making it optimal in terms of sample complexity.	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	dagreou24a	0	A Lower Bound and a Near-Optimal Algorithm for Bilevel Empirical Risk Minimization	82	90	82-90	82	false	Dagr\'{e}ou, Mathieu and Moreau, Thomas and Vaiter, Samuel and Ablin, Pierre	given family Mathieu Dagréou given family Thomas Moreau given family Samuel Vaiter given family Pierre Ablin	2024-04-18		Proceedings of The 27th International Conference on Artificial Intelligence and Statistics	238	inproceedings	date-parts 2024 4 18	https://proceedings.mlr.press/v238/dagreou24a/dagreou24a.pdf