A General Descent Aggregation Framework for Gradient-Based Bi-Level Optimization

• Published in: IEEE transactions on pattern analysis and machine intelligence 2023-01, Vol.45 (1), p.38-57
• Main Authors: Liu, Risheng, Mu, Pan, Yuan, Xiaoming, Zeng, Shangzhi, Zhang, Jin
• Format: Article
• Language: English
• Subjects: Agglomeration; Algorithms; Approximation algorithms; Bi-level optimization; Cognitive tasks; Computer vision; Convergence; descent aggregation; Dynamical systems; gradient-based method; Heuristic algorithms; hyper-parameter optimization; Iterative methods; Machine learning; meta-learning; Optimization; Source code; Task analysis
• ISSN: 0162-8828; 1939-3539; 2160-9292
• DOI: 10.1109/TPAMI.2022.3140249

In recent years, a variety of gradient-based methods have been developed to solve Bi-Level Optimization (BLO) problems in machine learning and computer vision areas. However, the theoretical correctness and practical effectiveness of these existing approaches always rely on some restrictive conditions (e.g., Lower-Level Singleton, LLS), which could hardly be satisfied in real-world applications. Moreover, previous literature only proves theoretical results based on their specific iteration strategies, thus lack a general recipe to uniformly analyze the convergence behaviors of different gradient-based BLOs. In this work, we formulate BLOs from an optimistic bi-level viewpoint and establish a new gradient-based algorithmic framework, named Bi-level Descent Aggregation (BDA), to partially address the above issues. Specifically, BDA provides a modularized structure to hierarchically aggregate both the upper- and lower-level subproblems to generate our bi-level iterative dynamics. Theoretically, we establish a general convergence analysis template and derive a new proof recipe to investigate the essential theoretical properties of gradient-based BLO methods. Furthermore, this work systematically explores the convergence behavior of BDA in different optimization scenarios, i.e., considering various solution qualities (i.e., global/local/stationary solution) returned from solving approximation subproblems. Extensive experiments justify our theoretical results and demonstrate the superiority of the proposed algorithm for hyper-parameter optimization and meta-learning tasks. Source code is available at https://github.com/vis-opt-group/BDA .