Bilevel optimization enjoys a wide range of applications in hyper-parameter optimization, meta-learning and reinforcement learning. However, bilevel optimization problems are difficult to solve. Recent progress on scalable bilevel algorithms mainly focuses on bilevel optimization problems where the lower-level objective is either strongly convex or unconstrained. In this work, we tackle the bilevel problem through the lens of the penalty method. We show that under certain conditions, the penalty reformulation recovers the solutions of the original bilevel problem. Further, we propose the penalty-based bilevel gradient descent (PBGD) algorithm and establish its finite-time convergence for the constrained bilevel problem without lower-level strong convexity. Experiments showcase the efficiency of the proposed PBGD algorithm.
翻译:双层优化在超参数优化、元学习和强化学习等领域中具有广泛应用。然而,双层优化问题很难解决。近期对于可扩展双层算法的进展主要集中在下层目标函数是强凸或者无约束的情况。在本研究中,我们通过惩罚方法来解决双层问题。我们证明了在某些条件下,惩罚重构可以恢复原始双层问题的解。进一步,我们提出了基于惩罚的双层梯度下降(PBGD)算法,并证明了其在没有下层强凸的情况下,对于约束双层问题的有限时间收敛性。实验展示了所提出的PBGD算法的效率。