LancBiO: Dynamic Lanczos-aided Bilevel Optimization via Krylov Subspace

Authors: Yan Yang, Bin Gao, Ya-xiang Yuan
Primary area: optimization
Keywords: bilevel optimization, lanczos process, krylov subspace

Abstract:
Bilevel optimization, with broad applications in machine learning, has an intricate hierarchical structure. Gradient-based methods have emerged as a common approach to large-scale bilevel problems. However, the computation of the hyper-gradient, which involves a Hessian inverse vector product, confines the efficiency and is regarded as a bottleneck. To circumvent the inverse, we construct a sequence of low-dimensional approximate Krylov subspaces with the aid of the Lanczos process. As a result, the constructed subspace is able to dynamically and incrementally approximate the Hessian inverse vector product with less effort and thus leads to a favorable estimate of the hyper-gradient. Moreover, we propose a provable subspace-based framework for bilevel problems where one central step is to solve a small-size tridiagonal linear system. To the best of our knowledge, this is the first time that subspace techniques are incorporated into bilevel optimization. This successful trial not only enjoys $\mathcal{O}(\epsilon^{-1})$ convergence rate but also demonstrates efficiency in a synthetic problem and two deep learning tasks.

Decision: accept (poster)
Reviewer scores: 5, 6, 5, 5

Reviews and discussion:
<thread>
creation date:
1730488827255

thread_type:
official_review

<thread_object>
creator: reviewer_clsw

<content>
summary:
This work proposes two novel algorithms, SubBiO and LancBiO, for solving bilevel optimization problems in which the lower-level problem is strongly convex. The main contribution lies in incorporating the Krylov subspace and the Lanczos process into bilevel optimization, achieving a more accurate hypergradient estimate by efficiently and dynamically solving the associated linear system. Under certain conditions, the authors establish non-asymptotic convergence for LancBiO and conduct an empirical study to validate the efficiency of both SubBiO and LancBiO.

strengths:
$\textbf{S1:}$ The introduction of subspace techniques into bilevel optimization is well-motivated. The explanations of how the proposed SubBiO and LancBiO algorithms relate to existing methods are helpful. 

$\textbf{S2:}$ A convergence rate guarantee is provided for LancBiO under certain conditions. 

$\textbf{S3:}$ To empirically justify the improvement achieved by accurately solving the associated linear system, the experiments report the residual norm of the linear system.

weaknesses:
For the theory, the main concerns are as follows:

$\textbf{W1: Assumption 3.10}.$ Based on (10), Assumption 3.10 depends on the step size, $\lambda$. However, in Lemma 3.11 and Theorem 3.12, $\lambda$ is specified to satisfy $\lambda\sim \mathcal{O}(\frac{1}{m^4})$. Under this setting, it seems that Assumption 3.10 may not hold when $m$ is sufficiently large. Therefore, in general, how can Assumption 3.10 be checked—either theoretically or empirically? A bit more discussion on these issues would be helpful. 

$\textbf{W2: Theoretical results lack discussion}.$ In reading Theorem 3.12, it is unclear how the results compare to other bilevel algorithms, as some existing algorithms (e.g., deterministic SOBA) also reach an \epsilon-stationary point within $\mathcal{O}(\epsilon^{-1})$ outer iterations.  
Additionally, there is no complexity analysis. For example, what is the number of oracle calls required to reach an $\epsilon$-stationary point? Typically, bilevel optimization literature provides the number of gradient, Hessian-vector, and Jacobian-vector products required to reach a stationary point with precision $\epsilon$. 


$\textbf{W3: Lack of convergence analysis for SubBiO}.$ Given that SubBiO has a simpler structure than LancBiO, it would be beneficial to include a theoretical analysis or, if not feasible, to discuss the reasons for its absence.

For the experiments, the main concern is as follows:

$\textbf{W4: Experiments could be expanded}.$ The experiments could be more comprehensive. For example, it would be beneficial to include additional competing bilevel methods, especially Hessian-free algorithms like F2SA (Kwon et al., ICML 2023). Additionally, using more datasets in the data hyper-cleaning and logistic regression tasks would help validate the efficiency of both SubBiO and LancBiO.

questions:
Apart from the questions raised in the Weaknesses section, some additional questions are as follows:

$\textbf{Q1:}$ In the implementation of SubBiO, how is the two-dimensional subproblem in line 4 solved? A bit more discussion on these choices would be helpful. 

$\textbf{Q2:}$ In the convergence analysis of LancBiO, the hyperparameter $m_0$ plays an important role, but it is not included in the experiments. Could the authors clarify why? 

$\textbf{Q3:}$ Can the authors provide more detail on why the Lanczos process in Algorithm 2 does not affect the final convergence guarantee? A brief proof sketch of Theorem 3.12 would be helpful.

Suggestions for improvement that did not affect the score:

$\textbf{About $m_0$ in Lemma 3.11 and Theorem 3.12:}$ First, $m_0$ in Lemma 3.11 should satisfy $m_0 = \Omega(1)$, meaning $m_0$ must be greater than some positive constant, as implied at the end of the proof of Lemma G.4. Second, $m_0$ in Theorem 3.12 should be set to $m_0 = \Omega(\log m)$, following from lines 1643–1647 and equation (63) in the proof of Lemma H.2.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730625734129

thread_type:
official_review

<thread_object>
creator: reviewer_nghd

<content>
summary:
This work presents an approach for bilevel optimization using Krylov subspace methods and the Lanczos process to approximate inverse-Hessian vector products. The method constructs low-dimensional Krylov subspaces and solves tridiagonal linear systems, achieving convergence to an $\epsilon$-stationary point with $\mathcal{O}(\epsilon^{-1})$ complexity. Experimental evaluations are conducted to illustrate its performance.

strengths:
The paper introduces a novel modification to the Lanczos process by re-linearising the objective functions within the iteration, specifically for bilevel optimization. This reduces large-scale subproblems to smaller tridiagonal linear systems, and the explanation provides a potential framework for applying subspace techniques in this context.

weaknesses:
I identify two weaknesses:

1.To my knowledge, many recent advances in bilevel optimization have focused on addressing problems where the function is not necessarily strongly convex, or even non-convex. The strong convexity assumption in this paper may be overly stringent, potentially limiting the method's applicability to a broader range of optimization problems.

2.The proposed method is technically constrained to deterministic settings. While LancBiO can be extended to stochastic scenarios, its performance in these settings has been inconsistent. It remains uncertain whether LancBiO can be effectively adapted for stochastic environments, which is crucial for many practical applications. For example, despite including experiments in stochastic settings, SOBA seems to perform better, indicating challenges in extending LancBIO effectively.

questions:
Could the authors provide further details on extending LancBiO to stochastic scenarios? Additionally, could they elaborate on how the Lanczos process ensures convergence in stochastic settings?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730648826558

thread_type:
official_review

<thread_object>
creator: reviewer_h14n

<content>
summary:
The paper addresses the complexities of bilevel optimization, a framework widely used in machine learning applications. It introduces a novel approach that utilizes the Lanczos process to construct low-dimensional Krylov subspaces, aiming to alleviate the computational challenges associated with hypergradient calculations. By avoiding the direct computation of the Hessian inverse, the proposed method demonstrates improved efficiency and achieves a convergence rate of $ O(\epsilon^{-1}) $. The authors present a theoretical foundation for their approach and validate it through experiments on synthetic problems and deep learning tasks.

strengths:
- **Innovative Approach**: The incorporation of subspace techniques into bilevel optimization is novel and contributes significantly to the field, potentially opening new avenues for research.
- **Theoretical Rigor**: The paper offers a solid theoretical framework that is well-justified, providing confidence in the proposed method's validity and effectiveness.
- **Empirical Validation**: The experimental results show promising performance improvements over existing methods, suggesting practical applicability in real-world scenarios.
- **Clarity of Presentation**: The paper is well-organized, making complex concepts accessible to readers, which enhances its impact.

weaknesses:
- **Limited Scope of Experiments**: While the experimental results are promising, they are conducted on a limited set of problems. Broader validation across diverse benchmarks would strengthen the paper's claims.
- **Assumptions in Theory**: The theoretical results rely on certain assumptions that may not hold in all contexts, potentially limiting the generalizability of the findings.
- **Lack of Comparison with More Methods**: The paper could benefit from comparisons with additional state-of-the-art bilevel optimization methods to contextualize the improvements more clearly.

questions:
1. How does the proposed method perform in scenarios where the lower-level problem is not strongly convex? 
2. Can the authors elaborate on how the method scales with increasing dimensions in the bilevel optimization problems?
3. Are there any limitations observed when applying the proposed method to non-standard bilevel optimization problems, such as those with noisy or sparse data?
4. Could the authors provide more detailed insights into the computational complexity of solving the small-size tridiagonal linear system mentioned?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730718126066

thread_type:
official_review

<thread_object>
creator: reviewer_szwj

<content>
summary:
This paper investigates a gradient based method for solving bilevel optimization problems with a strongly convex lower-level objective. To enhance the efficiency of hypergradient computation, the paper employs the Krylov subspace method alongside the Lanczos process to accelerate the solution of the linear systems involved. The paper presents non-asymptotic convergence results for the proposed method. Numerical experiments on data hyper-cleaning, synthetic problems, and logistic regression demonstrate its effectiveness.

strengths:
1. This work leverages the Krylov subspace method and the Lanczos process to solve the linear system involved in hypergradient computation, providing a new approach for efficiently approximating the hypergradient.

2. A non-asymptotic convergence rate of $O(\epsilon^{-1})$ is established.

weaknesses:
1. The description of Algorithm 2 is somewhat unclear, particularly in relation to the theoretical convergence result in Theorem 3.12. Theorem 3.12 requires the step size for $x$ to be zero during the initial few steps in each epoch, implying that before updating $x$, the algorithm must obtain a $y_k$ sufficiently close to $y^*(x_k)$, as also reflected in the theoretical analysis. This indicates that the epoch $h$ functions primarily as an outer loop index, where at each iteration $h$, the algorithm first solves the lower level problem to obtain a $y_k$ that is sufficiently close to the lower level solution before proceeding to update $x$. However, in other gradient based algorithms, such as SOBA, this requirement for $y_k$ to be close to the lower-level solution is not imposed.

2. In the convergence analysis, the proof of Theorem 3.12 , the step size for $x$ must be very small to ensure stability of the Krylov subspace method and the dynamic Lanczos process in LancBiO as $x_k$ is updated. It appears that the inclusion of the dynamic Lanczos process constrains the step size for $x$, potentially making it smaller than in algorithms without this process, such as SOBA. However, the paper lacks a discussion of this issue.

3. The parameter $m$, which defines the dimension of the Krylov subspace in LancBiO, should play a crucial role in the efficiency of the Krylov subspace method and hence the performance of LancBiO. However, the convergence analysis does not show how the choice of $m$ impacts the performance of LancBiO.

4. The convergence analysis requires an unusual assumption, Assumption 3.10, which is not present in other works, such as SOBA. Why is Assumption 3.10 necessary? Is it because $y_k$ generated by LancBiO cannot be guaranteed to converge to $y^*_k$ ?

questions:
Is the proposed algorithm applicable in a stochastic setting?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732351223667

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response

comment:
We sincerely thank all the reviewers for their insightful critiques and valuable suggestions regarding our manuscript. We thank all the reviewers for acknowledging our contributions and finding our work novel. We are the first to introduce subspace techniques to bilevel optimization, which is provable and of great potential. We have responded to the reviews individually and **updated a new manuscript version**. Here, we provide a general summary of our improvements to enhance the work.

- We have **enriched the experiments** from the following aspects and made the **code publicly** available, which is attached to the submission.
    1. Two Hessian-free algorithms, F2SA [1] and HJFBiO [2], are evaluated in the experiments, providing a more comprehensive comparison.
    2. The data hyper-cleaning task is evaluated on two additional datasets, Fashion-MNIST and Kuzushiji-MNIST (see Figure 8 and Figure 9). The proposed LancBiO performs better than other algorithms and showcases robustness across various datasets.
    3. We test algorithms on a synthetic problem under different problem dimensions (see Table 2 for illustration).

- Thanks to the reviewers’ comments, we are enlightened that **Assumption 3.10 can be circumvented** by a more detailed analysis. Specifically, in the original version, **only the proof of Lemma H.2** resorts to Assumption 3.10. Therefore, in the updated version, we remove Assumption 3.10 and modify the proof of Lemma H.2 locally. The modification does not alter the convergence result of this paper.

In the updated PDF, the modified content is highlighted in blue for easier identification. Specifically, the extension on experiments is recorded in **Appendix I**. The theoretical improvements are outlined in **Appendix J** to facilitate comparison with the original proof, and they will be merged into Appendix H in the next version of our paper.

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

[2] Optimal Hessian/Jacobian-free nonconvex-PL bilevel optimization. ICML(oral), 2024
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper investigates bilevel optimization problems with a strongly convex lower-level objective, introducing novel algorithms, SubBiO and LancBiO, that leverage Krylov subspace methods and the Lanczos process to efficiently approximate hypergradients without directly computing the Hessian inverse. The proposed methods construct low-dimensional Krylov subspaces to solve tridiagonal linear systems, achieving improved efficiency and convergence to stationary points with theoretical non-asymptotic guarantees. Empirical evaluations on synthetic problems, data hyper-cleaning, and logistic regression tasks validate the methods’ effectiveness, demonstrating their potential for applications in machine learning.