Efficient Curvature-Aware Hypergradient Approximation for Bilevel Optimization

Thank you for your valuable feedback. We will address each point in detail. The figures and the tables mentioned below are in this anonymous link: https://drive.google.com/file/d/1lCY1UF3isNnoujM8AGCPIdJlRqHctj-b/view?usp=sharing

Essential References Not Discussed:

• Comparison with fully first-order methods (numerical evaluation): We clarify that we have compared our method with the fully first-order method F2SA [1] in Experiments (Section 4.2 and 4.3). Our method consistently outperforms F2SA, even when using small batch sizes (64 or 256). It is worth noting that, based on the results from [2,3], F2SA is considered a SOTA fully first-order bilevel algorithm.

  Furthermore, we conducted additional experiments on meta-learning using the Omniglot and miniImageNet (approximately 3GB) datasets, with 4-layer convolutional neural networks (CNN4). We compared our NBO with the SOTA algorithms PZOBO [4] and qNBO [5]. The results, presented in Fig. 1 and 2 of the anonymous link, show that NBO consistently outperforms the other methods on both datasets, highlighting the effectiveness of our framework.

  Note that PZOBO is a widely used Hessian-free bilevel algorithm, while qNBO is a recently proposed curvature-aware algorithm that employs the quasi-Newton method to solve the lower-level problem.

• More references: First, among the references mentioned by the reviewer, [R1, R2, R4] focus on nonconvex lower-level problems, whereas our work focuses on strongly convex lower-level problems. Second, the reference [R3] does not propose a new bilevel algorithm but rather provides an improved analysis for SOBA. Since SOBA is a special case of our NBO framework (as noted in Remark 2.1 (i) of our work), their analysis also applies to our NSBO-SGD when $T=0$.

  We appreciate the reviewer’s suggestions and will include these references in our work. Additionally, we have added a summary table for the stochastic setting that incorporates the references mentioned by the reviewer, as shown in Table 1 in the anonymous link (the second page).

Other Strengths And Weaknesses:

• In the stochastic setting, we also establish a theoretical improvement: As stated after Theorem 3.7, our NSBO-SGD improves upon the SOTA result of AmIGO by a factor of $\log \kappa$ in the stochastic setting, where AmIGO also employs a large batch size.
• Concern about batch size: The large batch size we choose helps achieve better sample complexity. If the batch size is set to $O(1)$, we can obtain a sample complexity of $O(\kappa^{16} \epsilon^{-2})$, which is worse than $O(\kappa^9 \epsilon^{-2})$ in Theorem 3.7. It is also worth noting that SOBA is a special case of our NBO framework.
• Extension to non-strongly convex problems: The NBO framework is primarily designed for bilevel optimization problems with a strongly convex structure. For non-strongly convex problems, existing methods often involve reformulating the original problem to incorporate a strongly convex structure. Once this structure is established, our NBO framework can be applied. For instance, we compared the BAMM method [7] and BAMM+NBO (i.e., using NBO to compute $d_x^k$ in BAMM). The result, presented in Fig. 3 of the anonymous link, shows that BAMM+NBO significantly outperforms BAMM, highlighting the effectiveness of the NBO framework.
• Comparison with fully first-order methods (convergence rate and complexity): Please see Table 1 in the anonymous link for the stochastic setting. For the deterministic setting, we will add a new row to Table 1 in our paper, presented in Table 2 of the anonymous link (the second page).

[1] Kwon et al., A fully first-order method for stochastic bilevel optimization, ICML 2023.

[2] Chen et al., Near-optimal nonconvex-strongly-convex bilevel optimization with fully first-order oracles. arXiv preprint 2023.

[3] Chen et al., On finding small hyper-gradients in bilevel optimization: Hardness results and improved analysis. COLT 2024.

[4] Sow et al., On the convergence theory for hessian-free bilevel algorithms, NeurIPS 2022.

[5] Fang et al., qNBO: quasi-Newton Meets Bilevel Optimization, ICLR 2025.

[6] Arbel et al., Amortized implicit differentiation for stochastic bilevel optimization, ICLR 2022.

[7] Liu et al., Averaged Method of Multipliers for BiLevel Optimization without Lower-Level Strong Convexity, ICML 2023.

Thank you for your thorough review and valuable feedback. We will address each point in detail below. The figures mentioned below are in this anonymous link: https://drive.google.com/file/d/1v6ftNYExUb_ClkgoS7b9wU2Q3nNY1IsP/view?usp=sharing

Other Strengths And Weaknesses:

• Concern about batch size: The large batch size we choose helps achieve better sample complexity. If the batch size is set to $O(1)$, we can obtain a sample complexity of $O(\kappa^{16} \epsilon^{-2})$, which is worse than $O(\kappa^9 \epsilon^{-2})$ in Theorem 3.7. Since SOBA is a special case of our NBO framework (as noted in Remark 2.1 (i) of our work), their analysis also applies to our NSBO-SGD when $T=0$. Moreover, a large batch size related to $\epsilon$ or $K$ is commonly used in the stochastic bilevel optimization literature (see, e.g., Ji et al., 2021; Arbel & Mairal, 2022).

• Our improvements in the stochastic setting and in practice: In theory, as stated after Theorem 3.7, our NSBO-SGD improves upon the SOTA result of AmIGO by a factor of $\log \kappa$ in the stochastic setting, where AmIGO also employs a large batch size.

  In practice, our algorithms show significant advantages in experiments, even when using small batch sizes (64 or 256). Additionally, we add experiments on meta-learning using the Omniglot and miniImageNet (about 3GB) datasets, with CNN4 networks. We compared our NBO with the SOTA algorithms PZOBO in [1] and qNBO in [2]. The results, presented in Fig. 1 and 2 of the anonymous link, demonstrate that NBO consistently outperforms the other methods on both datasets.

  [1] Sow et al., On the convergence theory for hessian-free bilevel algorithms, NeurIPS 2022.

  [2] Fang et al., qNBO: quasi-Newton Meets Bilevel Optimization, ICLR 2025.

Other Comments Or Suggestions:

Thank you for your careful reading. We will address each point as follows:

• Line 39: We will revise it.
• Line 131: This sentence represents the second aspect of our motivation. Although we have not fully utilized this point, we still believe it is important.
• Line 150: Here we use warm-start for $u$ and will make revisions to clarify this.
• Line 303: We will revise it.
• Algorithm 3 and 5: The initialization point $w^{-1,k}=0$ is correct. With this initialization, we obtain $w^{0,k}=\gamma_k d_u^k$ (where $d_u^k$ is defined in Line 150), ensuring that the second equality in (44) holds.
• Theorem 3.2 and 3.7: BOX 1 and 2 represent the initialization strategies of Algorithm 2 and 4, respectively. We will add an introduction before these theorems.
• Summary: Depending on the available space in the final manuscript, we will consider adding a summary table for the stochastic setting.
• Box 2: Thank you for pointing out the typo. $B_0$ and $B_0^{'}$ should be replaced by $B_{0,n}$ and $B^{'}_{0,q}$ respectively, while maintaining the same batch size.
• Line 1049: We will revise it.
• Line 1142-1143: The constant $\frac{1}{2}$ arises from $2 \times (\frac{1}{2})^2$.
• Section E.2 and the first line of section E.2: We will revise them.
• Equation (52): We will revise it.

Questions For Authors:

• Concern about warm-start: The reason we use warm-start for $u$ but not for $v$ is that $v$ directly affects $||y^{k+1}-y^{k}||$, while $u$ does not. Indeed, in the $k$-th iteration of NBO, $v^k$ serves as an inexact approximation of the Newton direction $v^*(x^k,y^k):=[\nabla_{22}^2g(x^k,y^k)]^{-1} \nabla_2 g(x^k,y^k)$, whereas $y^{k}$ approximates $y^*(x^{k})$. We update $y^{k+1}= y^k - v^k$ using a single inexact Newton step. If we further compute $v^{k+1} = v^{k} - \gamma_k d_v^{k}$ (using one-step gradient descent with warm-start), according to the Lyapunov function argument, we estimate $||v^{k+1} - v^*(x^{k+1},y^{k+1})|| \leq (1-\gamma_{k} \mu)||v^{k} - v^*(x^{k},y^{k})|| + ||v^*(x^{k+1},y^{k+1})-v^*(x^{k},y^{k})||. (1)$ Similar to $y^*(x)$ and $u^*(x)$, $v^*(x,y)$ is Lipschitz continuous and we can get $||v^*(x^{k+1},y^{k+1})-v^*(x^{k},y^{k})||\leq \frac{2L_{g,1}}{\mu}(||x^{k+1} - x^{k}||+||y^{k+1} - y^{k}||). (2)$

  Note that $||y^{k+1} - y^{k}||\leq ||v^k-v^*(x^{k},y^{k})||+||v^*(x^{k},y^{k})||\leq ||v^k-v^*(x^{k},y^{k})||+\frac{L_{g,1}}{\mu}||y^{k}-y^*(x^k)||. (3)$ Substituting (2) and (3) into (1), we obtain $||v^{k+1} - v^*(x^{k+1},y^{k+1})|| \leq (1-\gamma_{k} \mu+\frac{2L_{g,1}}{\mu})||v^{k} - v^*(x^{k},y^{k})|| + others.$

  Since $1-\gamma_{k} \mu+\frac{2L_{g,1}}{\mu}>1$ when $\gamma_{k}\leq 1/L_{g,1}$, the Lyapunov function argument fails to hold, indicating that the above warm-start strategy for $v$ is problematic. If multi-step gradient descent is performed for $v$, we choose to initialize at 0 because, in this setting, when $T=0$, NBO reduces to the single-loop algorithm framework proposed by (Dagréou et al., 2022) .

Thank you for your valuable comments and suggestions. We will address each point in detail below. The referenced figures are compiled in a single-page PDF (containing only figures) available at the anonymous link: https://drive.google.com/file/d/15xqtvUMRk7Ah7Gi5hnvBQWyuZ6W15zX8/view?usp=sharing

Other Strengths And Weaknesses & Questions For Authors:

• Extension to lower-level non-strongly convex problems: The NBO framework is primarily designed for bilevel optimization problems with a strongly convex structure. For non-strongly convex problems, existing methods typically involve reformulating the original problem to incorporate a strongly convex structure. Once this structure is established, our NBO framework can be applied. For instance, in BAMM method [1], when $g$ is merely convex, an aggregation function $\phi_{\mu} = \mu f + (1 - \mu) g$ is defined, which is strongly convex when $f$ is strongly convex, then an approximated hypergradient $d_x^k$ can be computed by replacing $g$ with $\phi_{\mu}$. We compared the BAMM method and BAMM+NBO (i.e., using NBO to compute $d_x^k$ in BAMM) on the toy example (13) in [1]. The result, presented in Fig. 1 of the anonymous link, shows that BAMM+NBO significantly outperforms BAMM, highlighting the effectiveness of the NBO framework. Due to space constraints, we primarily focused on strongly convex lower-level problems in this work, which limited our ability to fully showcase the versatility of NBO. We appreciate your valuable suggestions and will include additional discussion in the revised manuscript to further demonstrate the versatility of NBO.

Other Comments Or Suggestions:

Thank you for pointing this out. We will revise this citation typo.

[1] Liu et al., Averaged Method of Multipliers for BiLevel Optimization without Lower-Level Strong Convexity, ICML 2023.

Thank you for your valuable comments and suggestions. We will address each point in detail below. The referenced figures are compiled in a single-page PDF (containing only figures) available at the anonymous link: https://drive.google.com/file/d/1ZEzn2mKcwrPzlBeziFpC1mKGWDeyq6-C/view?usp=sharing

Methods And Evaluation Criteria:

• Combine with Bregman-based methods:
  • The improvements of our NBO framework and Bregman-based methods stem from two different perspectives: the NBO framework improves hypergradient approximation (related to updates of the lower-level variable $y$), while Bregman-based methods use mirror descent to update the upper-level variable $x$.
  • Thank you for your constructive suggestion. The idea of combining our NBO framework with Bregman-based methods is both interesting and promising. To explore this, we conducted a numerical experiment where we used the NBO framework to approximate the hypergradient, followed by updating $x$ using the mirror descent method. We then compared SBiO-BreD in [1] and SBiO-BreD+NSBO (i.e., using our proposed framework to compute $w\_t$ in SBiO-BreD) in the context of data hyper-cleaning. The result, presented in Fig. 1 of the anonymous link, demonstrates that SBiO-BreD+NSBO significantly outperforms SBiO-BreD, highlighting the effectiveness of the NBO framework.

Experimental Designs Or Analyses & Relation To Broader Scientific Literature:

• Comparison against other curvature-aware algorithms: We would like to clarify that we have compared our method with SHINE in Experiments (Section 4.2 and 4.3). SHINE is a popular curvature-aware algorithm that employs the quasi-Newton method to solve the lower-level problem.

Essential References Not Discussed:

• Comparison against exact Hessian methods: Directly computing the Hessian and its inverse is both time-consuming and memory-consuming. In our setting, using the Hessian-vector product is a more practical choice, as it can be efficiently computed and stored with modern automatic differentiation frameworks. To demonstrate this, we conducted a numerical experiment comparing NBO with the exact Hessian inverse (implemented using jax.hessian and jnp.linalg.inv) and NBO-GD for hyperparameter optimization on synthetic data. The result in Fig. 2 of the anonymous link shows that NBO with the exact Hessian inverse is significantly slower.
• About comparison against Bregman-based methods, please see the response to "Methods And Evaluation Criteria".

Other Strengths And Weaknesses:

• Scalability to large dimensional problems: Thanks for the suggestion. As shown in Fig. 3 of the anonymous link, we evaluated the scalability of NBO by testing hyperparameter optimization on synthetic data while progressively increasing the problem dimension.
• Extension to non-strongly convex problems: The NBO framework is primarily designed for bilevel optimization problems with a strongly convex structure. For non-strongly convex problems, existing methods typically involve reformulating the original problem to incorporate a strongly convex structure. Once this structure is established, our NBO framework can be applied. For instance, we compared the BAMM method [2] and BAMM+NBO (i.e., using NBO to compute $d_x^k$ in BAMM). The result, presented in Fig. 4 of the anonymous link, shows that BAMM+NBO significantly outperforms BAMM, highlighting the effectiveness of the NBO framework. Due to space constraints, we primarily focused on strongly convex lower-level problems in this work, which limited our ability to fully showcase the versatility of NBO. We appreciate your valuable suggestions and will include additional discussion in the revised manuscript to further demonstrate the versatility of NBO.

[1] Huang et al., Enhanced bilevel optimization via bregman distance, NeurIPS 2022.

[2] Liu et al., Averaged Method of Multipliers for BiLevel Optimization without Lower-Level Strong Convexity, ICML 2023.