Will Bilevel Optimizers Benefit from Loops
Bilevel optimization has arisen as a powerful tool for solving a variety of
machine learning problems. Two current popular bilevel optimizers AID-BiO and
ITD-BiO naturally involve solving one or two sub-problems, and consequently,
whether we solve these problems with loops (that take many iterations) or
without loops (that take only a few iterations) can significantly affect the
overall computational efficiency. Existing studies in the literature cover only
some of those implementation choices, and the complexity bounds available are
not refined enough to enable rigorous comparison among different
implementations. In this paper, we first establish unified convergence analysis
for both AID-BiO and ITD-BiO that are applicable to all implementation choices
of loops. We then specialize our results to characterize the computational
complexity for all implementations, which enable an explicit comparison among
them. Our result indicates that for AID-BiO, the loop for estimating the
optimal point of the inner function is beneficial for overall efficiency,
although it causes higher complexity for each update step, and the loop for
approximating the outer-level Hessian-inverse-vector product reduces the
gradient complexity. For ITD-BiO, the two loops always coexist, and our
convergence upper and lower bounds show that such loops are necessary to
guarantee a vanishing convergence error, whereas the no-loop scheme suffers
from an unavoidable non-vanishing convergence error. Our numerical experiments
further corroborate our theoretical results.