  Bilevel optimization has been recently used in many machine learning problems
such as hyperparameter optimization, policy optimization, and meta learning.
Although many bilevel optimization methods have been proposed, they still
suffer from the high computational complexities and do not consider the more
general bilevel problems with nonsmooth regularization. In the paper, thus, we
propose a class of enhanced bilevel optimization methods with using Bregman
distance to solve bilevel optimization problems, where the outer subproblem is
nonconvex and possibly nonsmooth, and the inner subproblem is strongly convex.
Specifically, we propose a bilevel optimization method based on Bregman
distance (BiO-BreD) to solve deterministic bilevel problems, which achieves a
lower computational complexity than the best known results. Meanwhile, we also
propose a stochastic bilevel optimization method (SBiO-BreD) to solve
stochastic bilevel problems based on stochastic approximated gradients and
Bregman distance. Moreover, we further propose an accelerated version of
SBiO-BreD method (ASBiO-BreD) using the variance-reduced technique, which can
achieve a lower computational complexity than the best known computational
complexities with respect to condition number $\kappa$ and target accuracy
$\epsilon$ for finding an $\epsilon$-stationary point. We conduct data
hyper-cleaning task and hyper-representation learning task to demonstrate that
our new algorithms outperform related bilevel optimization approaches.
