  Bilevel optimization has shown its utility across various machine learning
settings, yet most algorithms in practice require second-order information,
making it challenging to scale them up. Only recently, a paradigm of
first-order algorithms emerged, capable of effectively addressing bilevel
optimization problems. Nevertheless, the practical efficiency of this paradigm
remains unverified, particularly in the context of large language models
(LLMs). This paper introduces the first scalable instantiation of this paradigm
called ScaleBiO, focusing on bilevel optimization for large-scale LLM data
reweighting. By combining with a recently proposed memory-efficient training
technique called LISA, our novel algorithm allows the paradigm to scale to
34-billion-parameter LLMs on eight A40 GPUs, marking the first successful
application of bilevel optimization under practical scenarios for large-sized
LLMs. Empirically, extensive experiments on data reweighting verify the
effectiveness of ScaleBiO for different-scaled models, including GPT-2,
LLaMA-3-8B, GPT-NeoX-20B, and Yi-34B, where bilevel optimization succeeds in
filtering irrelevant data samples and selecting informative samples.
Theoretically, ScaleBiO ensures the optimality of the learned data weights,
along with a convergence guarantee matching the conventional first-order
bilevel optimization paradigm on smooth and strongly convex objectives.
