  The popularity of bi-level optimization (BO) in deep learning has spurred a
growing interest in studying gradient-based BO algorithms. However, existing
algorithms involve two coupled learning rates that can be affected by
approximation errors when computing hypergradients, making careful fine-tuning
necessary to ensure fast convergence. To alleviate this issue, we investigate
the use of recently proposed adaptive step-size methods, namely stochastic line
search (SLS) and stochastic Polyak step size (SPS), for computing both the
upper and lower-level learning rates. First, we revisit the use of SLS and SPS
in single-level optimization without the additional interpolation condition
that is typically assumed in prior works. For such settings, we investigate new
variants of SLS and SPS that improve upon existing suggestions in the
literature and are simpler to implement. Importantly, these two variants can be
seen as special instances of general family of methods with an envelope-type
step-size. This unified envelope strategy allows for the extension of the
algorithms and their convergence guarantees to BO settings. Finally, our
extensive experiments demonstrate that the new algorithms, which are available
in both SGD and Adam versions, can find large learning rates with minimal
tuning and converge faster than corresponding vanilla SGD or Adam BO algorithms
that require fine-tuning.
