Efficient Gradient Approximation Method for Constrained Bilevel Optimization
Efficient Gradient Approximation Method for Constrained Bilevel Optimization
复制标题
DOI：
10.1609/aaai.v37i10.26473
复制
发表时间：
2023-02
期刊：
影响因子：
--
通讯作者：
Siyuan Xu;Minghui Zhu
中科院分区：
文献类型：
--
作者：
Siyuan Xu;Minghui Zhu
两层优化已被用于许多具有大规模和高维数据的机器学习任务。本文考虑一类带约束的双层优化问题，其中下层优化问题是带有等式和不等式约束的凸优化问题，上层优化问题是非凸优化问题。总的目标函数是非凸的、不可微的。为了解决这个问题，我们提出了一种基于梯度的方法，称为梯度逼近方法，它通过计算当前估计邻域内目标函数的几个代表性梯度来确定下降方向。我们证明了算法渐近收敛于Clarke平稳点集，并通过超参数优化和元学习实验验证了算法的有效性。
Bilevel optimization has been developed for many machine learning tasks with large-scale and high-dimensional data. This paper considers a constrained bilevel optimization problem, where the lower-level optimization problem is convex with equality and inequality constraints and the upper-level optimization problem is non-convex. The overall objective function is non-convex and non-differentiable. To solve the problem, we develop a gradient-based approach, called gradient approximation method, which determines the descent direction by computing several representative gradients of the objective function inside a neighborhood of the current estimate. We show that the algorithm asymptotically converges to the set of Clarke stationary points, and demonstrate the efficacy of the algorithm by the experiments on hyperparameter optimization and meta-learning.