Stochastic bilevel optimization generalizes the classic stochastic
optimization from the minimization of a single objective to the minimization of
an objective function that depends the solution of another optimization
problem. Recently, stochastic bilevel optimization is regaining popularity in
emerging machine learning applications such as hyper-parameter optimization and
model-agnostic meta learning. To solve this class of stochastic optimization
problems, existing methods require either double-loop or two-timescale updates,
which are sometimes less efficient. This paper develops a new optimization
method for a class of stochastic bilevel problems that we term Single-Timescale
stochAstic BiLevEl optimization (STABLE) method. STABLE runs in a single loop
fashion, and uses a single-timescale update with a fixed batch size. To achieve
an $\epsilon$-stationary point of the bilevel problem, STABLE requires ${\cal
O}(\epsilon^{-2})$ samples in total; and to achieve an $\epsilon$-optimal
solution in the strongly convex case, STABLE requires ${\cal O}(\epsilon^{-1})$
samples. To the best of our knowledge, this is the first bilevel optimization
algorithm achieving the same order of sample complexity as the stochastic
gradient descent method for the single-level stochastic optimization.

本论文提出了一种单时间尺度的随机双层最优化算法 (STABLE)，用于解决机器学习中的双层次优化问题，具有较高的效率和样本复杂度。