Bilevel optimization is an important formulation for many machine learning
problems. Current bilevel optimization algorithms assume that the gradient of
the upper-level function is Lipschitz. However, recent studies reveal that
certain neural networks such as recurrent neural networks (RNNs) and
long-short-term memory networks (LSTMs) exhibit potential unbounded smoothness,
rendering conventional bilevel optimization algorithms unsuitable. In this
paper, we design a new bilevel optimization algorithm, namely BO-REP, to
address this challenge. This algorithm updates the upper-level variable using
normalized momentum and incorporates two novel techniques for updating the
lower-level variable: \textit{initialization refinement} and \textit{periodic
updates}. Specifically, once the upper-level variable is initialized, a
subroutine is invoked to obtain a refined estimate of the corresponding optimal
lower-level variable, and the lower-level variable is updated only after every
specific period instead of each iteration. When the upper-level problem is
nonconvex and unbounded smooth, and the lower-level problem is strongly convex,
we prove that our algorithm requires $\widetilde{\mathcal{O}}(1/\epsilon^4)$
iterations to find an $\epsilon$-stationary point in the stochastic setting,
where each iteration involves calling a stochastic gradient or Hessian-vector
product oracle. Notably, this result matches the state-of-the-art complexity
results under the bounded smoothness setting and without mean-squared
smoothness of the stochastic gradient, up to logarithmic factors. Our proof
relies on novel technical lemmas for the periodically updated lower-level
variable, which are of independent interest. Our experiments on
hyper-representation learning, hyperparameter optimization, and data
hyper-cleaning for text classification tasks demonstrate the effectiveness of
our proposed algorithm.

设计了一种名为 BO-REP 的新的双层优化算法，用于解决具有潜在无界平滑性的神经网络在双层优化问题中的挑战。证明了在随机环境下，该算法需要大约 1/ε^4 次迭代来找到一个 ε- 稳定点，结果与有界平滑度设置和没有均方平滑性的随机梯度的最新复杂度结果相匹配。实验证明了所提出算法在超表征学习、超参数优化和文本分类任务中的有效性。