Bilevel optimization has found extensive applications in modern machine learning problems such as hyperparameter optimization, neural architecture search, meta-learning, etc. While bilevel problems with a unique inner minimal point (e.g., where the inner function is strongly convex) are well understood, such a problem with multiple inner minimal points remains to be challenging and open. Existing algorithms designed for such a problem were applicable to restricted situations and do not come with a full guarantee of convergence. In this paper, we adopt a reformulation of bilevel optimization to constrained optimization, and solve the problem via a primal-dual bilevel optimization (PDBO) algorithm. PDBO not only addresses the multiple inner minima challenge, but also features fully first-order efficiency without involving second-order Hessian and Jacobian computations, as opposed to most existing gradient-based bilevel algorithms. We further characterize the convergence rate of PDBO, which serves as the first known non-asymptotic convergence guarantee for bilevel optimization with multiple inner minima. Our experiments demonstrate desired performance of the proposed approach.
翻译:双层优化在超参数优化、神经结构搜索、元学习等现代机器学习问题中找到了广泛的应用。虽然人们非常了解具有独特内部最低点的双层问题(例如,内部功能具有很强的共性),但多重内部最低点的问题仍然具有挑战性和开放性。针对此类问题的现有算法适用于有限的情况,没有完全一致的保证。在本文中,我们采用了双级优化的重新制定,以限制优化,并通过初级双层优化算法(PDBO)解决问题。PDBO不仅解决了多重内部小型挑战,而且具有完全一级效率,而不涉及二级的黑森和雅各布计算,而不是大多数现有的基于梯度的双级算法。我们进一步描述PDBO的趋同率,这是第一个已知的双级优化与多个内部微型的不依赖性融合保证。我们的实验显示了拟议方法的预期性表现。