Bilevel optimization has been widely applied in many important machine learning applications such as hyperparameter optimization and meta-learning. Recently, several momentum-based algorithms have been proposed to solve bilevel optimization problems faster. However, those momentum-based algorithms do not achieve provably better computational complexity than $\mathcal{\widetilde O}(\epsilon^{-2})$ of the SGD-based algorithm. In this paper, we propose two new algorithms for bilevel optimization, where the first algorithm adopts momentum-based recursive iterations, and the second algorithm adopts recursive gradient estimations in nested loops to decrease the variance. We show that both algorithms achieve the complexity of $\mathcal{\widetilde O}(\epsilon^{-1.5})$, which outperforms all existing algorithms by the order of magnitude. Our experiments validate our theoretical results and demonstrate the superior empirical performance of our algorithms in hyperparameter applications.


翻译:双级优化已被广泛应用于许多重要的机器学习应用程序, 如超参数优化和元学习。 最近, 提议了一些基于动力的算法, 以更快地解决双级优化问题。 但是, 这些基于动力的算法并没有比基于 SGD 的算法的 $\ mathcal ~ 全局 O} (\\ epsilon ⁇ -2} ) 实现更好的计算复杂性。 在本文中, 我们为双级优化建议了两种新的算法, 第一个算法采用了基于动力的循环迭代, 而第二个算法则采用了嵌入循环的递增梯度估计, 以减少差异。 我们显示, 这两种算法都达到了 $\ mathcal ~ 全局 O} (\ epsilon ⁇ - 1.5} ) 的复杂度, 这比所有基于 SGDD 的算法都高。 我们的实验证实了我们的理论结果, 并展示了我们在超参数应用中的算法的高级经验性表现 。

0
下载
关闭预览

相关内容

专知会员服务
56+阅读 · 2021年4月12日
斯坦福2020硬课《分布式算法与优化》
专知会员服务
118+阅读 · 2020年5月6日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
鲁棒机器学习相关文献集
专知
8+阅读 · 2019年8月18日
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
Ray RLlib: Scalable 降龙十八掌
CreateAMind
9+阅读 · 2018年12月28日
已删除
将门创投
4+阅读 · 2018年6月12日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Neural Architecture Optimization
Arxiv
8+阅读 · 2018年9月5日
Arxiv
3+阅读 · 2017年12月1日
VIP会员
相关资讯
鲁棒机器学习相关文献集
专知
8+阅读 · 2019年8月18日
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
Ray RLlib: Scalable 降龙十八掌
CreateAMind
9+阅读 · 2018年12月28日
已删除
将门创投
4+阅读 · 2018年6月12日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Top
微信扫码咨询专知VIP会员