Unlocking Global Optimality in Bilevel Optimization: A Pilot Study

We sincerely thank the reviewer for the time and thoughtful review of our submission. We hope our response has addressed your concerns, and we welcome any further comments or questions you may have.

We sincerely thank the reviewer for taking the time to review our submission.

To further address your concern, Q5: Definition of benign landscape and the reason why penalty landscape is easier to yield a benign landscape, we have provided additional visualizations based on the updated Example 1 in the revision.

These visualizations illustrate how the lifted dimensionality helps the penalty function achieve a better landscape compared with the nested objective. We believe this is a critical insight that may worth future development. Hope this further clarifies your concerns, and we welcome any additional comments or questions you may have.

I appreciate the authors' efforts in addressing most of my concerns regarding the soundness of the theorem.

Regarding W3, I remain unconvinced about how the hyperparameters were chosen in alignment with the theorem's development and how the robustness of the theoretical claims would hold under varying parameter values.

Morever, while I acknowledge that I am not an expert in the theoretical aspects, I feel that it remains unclear how the results of this paper can be effectively leveraged for general practical applications in bilevel optimization. Could the authors clarify the practical value of the theorem in the context of bilevel optimization algorithm design and the connection of the theorem to practical insights or implementation suggestions? I believe a key impact of developing theorem analysis is to uncover insights that can effectively guide practical applications.

We thank the reviewer for the insightful feedback and we are glad that our response has solved most of your concerns. Below, we address your remaining concerns.

1. Hyperparameter Selection and Alignment with Theory

Thanks for your question. We demonstrate alignment between theory and practice in the following ways:

• Almost Linear Convergence: PBGD, with appropriately chosen stepsizes, converges almost linearly to the optimal solution in representation learning and data hyper-cleaning, as shown in Figure 3. In this figure, the log of the optimality gap is plotted on the y-axis, and the resulting linear trend with respect to $K$ indicates the log of the optimality gap decreases linearly with $K$, confirming the linear convergence rate shown in Theorems 2–3.
• Impact of penalty constant $\gamma$: Enlarging the penalty constant $\gamma$ reduces the target optimality gap $\epsilon$ in Figure 3, as predicted by the inverse proportionality established in Theorems 2–3. Besides, by choosing varying $\gamma$ from $0.1-500$ for representation learning ($50-100$ for data hyper-cleaning), PBGD all converges to the global optimum with error less than $10^{-3}$, suggesting the robustness of our results in terms of $\gamma$.
• Impact of stepsizes $\alpha$ and $\beta$: While the theoretical upper bounds for stepsizes $\alpha,\beta$ provided in this paper primarily serve to demonstrate the existence of thresholds for convergence and may not be tight, they offer valuable theoretical guidance. In practice, although we cannot verify exact alignment with these bounds, we empirically identify stepsizes that ensure convergence, which also supports the existence of such thresholds in Figure 4. Specifically, stepsizes exceeding these thresholds (e.g. $\alpha=5e^{-10},\beta=1e^{-9}$) cause divergence, while those within the range maintain stability and convergence. Moroever, by choosing varying $\alpha$ and $\beta$ from $1e^{-10}-1e^{-12}$ and $5e^{-10}-1e^{-10}$ respectively, PBGD all converges to the global optimum with error less than $10^{-3}$, suggesting the robustness of our results in terms of $\alpha,\beta$.
• Impact of ratio of stepsizes $\alpha/\beta$: Besides, the empirical threshold for $\alpha=5e^{-10}$ is smaller than $\beta=1e^{-9}$ when $\gamma=10$ for representation learning, which also aligns with the theoretical finding that the threshold $\frac{\alpha}{\beta}={\cal O}(1/\gamma)$ in terms of $\gamma$.

2. Practical Value of the Theorems

Thank you for your question. Our work offers actionable insights for bilevel optimization with global convergence guarantee.

• Choose the level of Overparameterization: Our analysis highlights that overparameterization is critical for ensuring a benign optimization landscape and achieving global convergence; see the model requirement in our paper (Line 373 for representation learning and Line 454-455 for data hyper-cleaning, and empirical verification in Line 2810 and Line 2850). This insight is particularly relevant for applications such as hyperparameter optimization, meta-learning, and adversarial robustness, where overparameterized models are common.
• Choose the type of bilevel algorithms: Previous approaches to global convergence in bilevel optimization often relied on application-specific algorithmic designs, such as semidefinite relaxations, which limit their applicability to general scenarios (see General Response G2 2) for more details). In contrast, our work is the first to establish global convergence for PBGD—a generally applicable bilevel method with stationary convergence guarantees across a broad range of settings. Rather than requiring application-specific modifications on algorithm, our approach only requires theoretical proof adaptations to achieve global convergence, allowing practitioners to confidently apply PBGD and other first-order bilevel algorithms without the risk of getting stuck in local minima or saddle points. Besides, better landscape of penalty reformulation also suggest that using penalty-based gradient descent approaches may help converge to a better point than implicit-gradient-based approaches.
• Choose the update for different problem structure: We propose two tailored update styles to address different bilevel coupling structures: Jacobi-style updates for jointly coupled variables and Gauss-Seidel-style updates for blockwise coupled variables. For problems where the upper- and lower-level variables share a common nature like representation learning, joint updates (Jacobi-style) are more beneficial. Conversely, when the upper- and lower-level variables serve distinct purposes like data hyper-cleaning, sequential updates (Gauss-Seidel-style) are more effective. These styles offer practical guidelines for selecting the most suitable update strategy based on problem characteristics. For instance, our study can be generalized to suggest that Gauss-Seidel-style updates are better suited for tasks like hyperparameter optimization, while Jacobi-style updates align well with meta-learning problem.

By bridging theory and practice, we believe these points offer guidance for practitioners while staying grounded in our theoretical framework. We are happy to further elaborate on any of these points to better highlight the connection between theory and practice.