A Single-Timescale Method for Stochastic Bilevel Optimization
A Single-Timescale Method for Stochastic Bilevel Optimization
复制标题
DOI：
--
复制
发表时间：
2021-02
期刊：
影响因子：
--
通讯作者：
Tianyi Chen;Yuejiao Sun;Quan-Wu Xiao;W. Yin
中科院分区：
文献类型：
--
作者：
Tianyi Chen;Yuejiao Sun;Quan-Wu Xiao;W. Yin
随机双层优化将经典的随机优化问题从单个目标的最小化推广到依赖于另一个优化问题的解的目标函数的最小化。最近，双层优化在新兴的机器学习应用中重新流行，如超参数优化和模型不可知Meta学习。为了解决这类优化问题，现有的方法需要双循环或两个时间尺度的更新，这是有时效率较低。本文对一类随机双层优化问题提出了一种新的优化方法--单时标随机双层优化方法。STABLE以单循环方式运行，并使用具有固定批大小的单时标更新。为了实现双层问题的（cid：15）-稳定点，STABLE总共需要O（（cid：15）− 2）个样本;为了在强凸情况下实现（cid：15）-最优解，STABLE需要O（（cid：15）− 1）个样本。据我们所知，当STABLE被提出时，它是第一个实现与单级随机优化SGD相同数量级的样本复杂度的双层优化算法。
Stochastic bilevel optimization generalizes the classic stochastic optimization from the minimization of a single objective to the minimization of an objective function that depends on the solution of another optimization problem. Recently, bilevel optimization is regain-ing popularity in emerging machine learning applications such as hyper-parameter optimization and model-agnostic meta learning. To solve this class of optimization problems, existing methods require either double-loop or two-timescale updates, which are some-times 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 (cid:15) -stationary point of the bilevel problem, STABLE requires O ( (cid:15) − 2 ) samples in total; and to achieve an (cid:15) -optimal solution in the strongly convex case, STABLE requires O ( (cid:15) − 1 ) samples. To the best of our knowledge, when STABLE was proposed, it is the first bilevel optimization algorithm achieving the same order of sample complexity as SGD for single-level stochastic optimization.