dEBORA: Efficient Bilevel Optimization-based low-Rank Adaptation
Authors: Emanuele Zangrando
Sara Venturini
Francesco Rinaldi
Francesco Tudisco
Venue: ICLR 2025 Poster (2025)
Keywords: bilevel optimization
parameter efficient fine-tuning
low-rank
Primary area: optimization

Abstract: Low-rank adaptation methods are a popular approach for parameter-efficient fine-tuning of large-scale neural networks. However, selecting the optimal rank for each layer remains a challenging problem that significantly affects both performance and efficiency. In this paper, we introduce a novel bilevel optimization strategy that simultaneously trains both matrix and tensor low-rank adapters, dynamically selecting the optimal rank for each layer. Our method avoids the use of implicit differentiation in the computation of the hypergradient, and integrates a stochastic away-step variant of the Frank-Wolfe algorithm, eliminating the need for projection and providing identifiability guarantees of the optimal rank structure. This results in a highly efficient and cost-effective training scheme that adaptively allocates the parameter budget across the network layers. On top of a detailed theoretical analysis of the method, we provide different numerical experiments showcasing its effectiveness.

Published as a conference paper at ICLR 2025
DEBORA: EFFICIENT BILEVEL OPTIMIZATION--ASEE BON-RANK ADAPTATION
Emanuele Zangrando', Sara Venturini", Francesco Rinaldi", Francesco Tudisco!
1 Gran Sasso Science Institute, I.' L'Aqui,,, Italy
2 MOBS Lab, Northeastern University, Boston, US
Department of Mathematics, University of Padova, Padova, Italy
"School of Mathematics and Maxwell Institute, University of Edinburgh, UK
5 Miniml.Al AT Ltd, UK
ABSTRACT
Low-rank adaptation methods a popular approach for parameter-effiiien fine- tuming of large-scale neural networks, However, selecting the optimal rank for each layer remains challenging problem that significantly affects both performance and efficiency. In this paper, we introduce novel bilevel optimization strategy that simultaneously trains both matrix and tensor low-rank adapters, dynamically selecting the optimal rank for each layer. Our method avoids the use of implicit differentiation in the computation of the hypergradient, and integrates a stochastic away-step variant of the Frank- Wolle algorithm, eliminating the need for projection and providing identifiability guarantees of the optimal rank structure. This results in highly efficient and cost-effective training scheme that adaptively allocates the parameter budget across the network layers. On top of a detailed theoretical analysis of the method, we provide different numerical experiments showcasing its effectiveness.
INTRODUCTION
Parameter-efficient fine-tuning methods have become essential for adapting large-scale pre-trained models to various downstream tasks without incurring prohibitive computational costs. Low-rank adaptation (LoRA) methods, which involve the addition of low-rank matrices to the existing weights of neural networks, have emerged as a popular solution due to their efficiency and simplicity. These methods keep the main model weights frozen, significantly reducing the number of trainable parameters and making the fine-tuning process more resource-efficient.
However, persistent challenge in this area is the selection of the optimal rank for each low-rank adapter, which is crucial for balancing performance and efficiency. Traditional LoRA methods often rely on a static rank configuration across all layers, leading suboptimal results. Recent approaches such as DyLoRA (Valipour et al., 2023) and AdaLoRA (Zhang et al. 2023) have attempted to address this by dynamically adapting the rank during training, but they still require considerable heuristic tuning or involve expensive steps that can limit their applicability and generalizability.
In this paper, we propose dEBORA (Efficient Bilevel Optimization--asedd low-Rank Adaptation), novel approach that leverages bilevel optimization to simultaneously train matrix and tensor low- rank adapters while dynamically selecting the optimal rank for each layer. Unlike previous bilevel citiiiizttin--aseed methods for low-rank adaptation (Qiang et al. 2024), dEBORA A eliminates the need for implicit differentiation in the computation of the hypergradient, thereby hugely simplifying the resources required by the optimization process. The upper-level aan-addatattinn step is performed by means of a stochastic away-step variant of the Frank- Wolfe algorithm, which not only removes the need for costly projection steps but also provides identifiability guarantees of the optimal rank structure.
We provide detailed theoretical amalysis of our method, establishing its convergence properties and optimality guarantees. Additionally, we conduct extensive numerical experiments across a range of benchmarks, including natural language understanding and generation tasks, demonstrate the

---

Published as a conference paper at ICLR 2025
effectiveness of dEBORA. Our results show that dEBORA outperforms existing low-rank adaptation methods in both efficiency and performance, particularly in settings with stringent parameter budgets.
Our method addresses the key limitations of existing low-rank adaptation techniques in several ways. First, by dynamically adjusting the rank for each layer during training, dEBORA ensures an adaptive allocation of the parameter budget across the network, thereby improving both com- putational efficiency and model performance. Second, the use of bilevel optimization provides a principled framework for handling the interaction between the model parameters and the adaptation budget hyperparameters, resulting in a more robust and theoretically grounded approach to low-rank adaptation.
The rest of this paper is organized as follows: Section 2 reviews related work on parameter-efficiee fine-tuning and low-rank adaptation methods. Section presents the proposed bilevel optimization framework and the dynamic rank adaptation mechanism, while Section the specific structure of the problem is used create an efficient closed-form approximation for the hypergradient. Section [ and Section [ introduce the stochastic version of the away-step Frank- Wolle algorithm for solving the upper-level problem, along with its theoretical properties. Section 7 details the experimental setup and results. Finally, Section S concludes the paper and discusses potential future directions.
RELATED WORK
Parameter-Efficien Fine- Tunnng Large-scale pre-trained models have demonstrated significant improvements across numerous tasks. However, fine-tuning these models for specific downstream tasks often involves updating millions, if not billions, of parameters, leading to substantial computa- tional and memory overhead. This has motivated the development of parameter-efficient fine-tuning (PEFT) techniques, which aim to reduce the number of trainable parameters while maintaining or even enhancing the performance of the model.
One of the seminal works in this area is Low-Rank Adaptation (LoRA) (Hu et al. 2021 which introduces low-rank incremental matrices to the frozen pre-trained weights, significantly reducing the trainable parameters. Inspired by recent findings in c.g. (Li et al. 2018) and (Aghajanyan et al. 202T). which suggest that pre-trained models possess low intrinsic dimension, LoRA leverages this property to achieve efficient adaptation without compromising performance.
Several variants of LoRA have been proposed further improve its efficiency and adaptability. DyLoRA (Valipour et al. (023) dynamically adjusts the ranks of the low-rank matrices during training based on the importance of learned representations, while QLoRA (Dettmers et al.) 2024) introduces quantization techniques to reduce the memory footprint of LoRA, making fine-tuning accessible on hardware with even more limited resources. Another extension is LoraHub (Huang ct al. 2023), which facilitates the modular composition of multiple LoRA modules across different tasks, enhancing the tross-task generalization capability of fine-tuned models.
Similar to our approach, AdaLoRA (Zhang et al. 2023) takes this step further by adaptively allocating the parameter budget based on the importance of different modules within the model. By parameterizing the low-rank updates using a singular value decomposition (SVD) framework, AdaLoRA iteratively prunes less significant singular values, thus optimizing the allocation of the limited parameter budget across the network.
BiLoRA (Qiang et al. 2024) employs a bi-level optimization framework, where the learning of pseudo singular values and vectors is decoupled and assigned to different levels of the optimization hierarchy. This separation mitigates the risk of overfitting by allowing each component to be optimized independently on separate subsets of the training data. This approach is inspired by differentiable architecture search (DARTS) (Liu et al. (219)) where the architecture and weights are optimized on different datasets, preventing overfitting to any particular training set. Unlike the proposed dEBORA, BiLoRA computes the hypergradients "directly" using implicit differentiation, resulting in high computational demand.
Low-Rank Methods for Pre- Pre-Training. Low-rank methods have also been successfully applied during the pre-training and training phases of neural networks, capitalizing on the observation that large models often possess a low intrinsic dimensionality. Techniques like Pufferfish (Wang et al.) 202I), intrinsic dimension reduction (Aghajanyan et al., (202)). and DLRT (Schotthöter et al. [2022 reduce the number of parameters during training, potentially improving both model efficiency and
2

---

Published as a conference paper at ICLR 2025
generalization. Recent developments such (Zangrando al. 2024 Riemmanian optimization to explore the parameter space, dynamically adapting the rank during training and ensuring model accuracy and substantial memory reduction, even with initially incorrect rank estimates. ReLoRA (Lialin et al. 2023) introduces a method for training large models efficiently by applying multiple low-rank updates, achieving significant memory savings while maintaining performance. Galore (Zhao et al., (2024) is based on projecting the gradients onto low-rank subspace, allowing for memory reductions without sacrificing model accuracy.
Bilevel Optimization in Deep Learning. Bilevel optimization, with its origins classical optimiza- tion theory (Colson et al. (007), has gained traction in machine learning for variety of applications, including hyperparameter optimization (Franceschi al., 2018), meta-learning (Finn al. 2017). and neural architecture search (Liu et al. 2019). The core challenge in bilevel optimization lies in the computation the hypergradient, which captures the dependence of the upper-level objective on the lower-level variables. This often scales the complexity of first-order optimization methods to that of second-ordes ones, making it computationally prohibitive for large-scale problems.
To address this challenge. numerous techniques have been proposed to approximate the hypergradient efficiently. Backpropagation through time (BPTT) (Franceschi et al. 2017) is one such approach, along with methods that efficient inverse Hessian approximations (Lorraine et al., (2220) and approximate implicit differentiation (AID) techniques (Grazzi et al. (020). These methods have made bilevel optimization feasible for high-dimensional problems, albeit with trade-offs in terms of computational accuracy and convergence speed.
Our work introduces novel bilevel optimization strategy for parameter-efficient fine-tuning, specifi- cally tailored for low-rank adaptation. By avoiding implicit differentiation and integrating stochastic away-step variant of the Frank- -ronk algorithm, our approach eliminates the need for costly gradient propagations and offers a more scalable solution. This framework allows for adaptive rank selection across network layers, providing a robust and efficient mechanism for fine-tuning.
LOW-RANK ADAPTATION VIA BILEVEL OPTIMIZATION
In this section, we introduce the bilevel optimization framework for fine-tuning low-rank adapters in tensor format, which provides parameter- efficciet adaptation strategy for large pre-trained models.
Consider the adaptation of pre-trained model weights Wo E R through a low-rank update = USVT, where U, E Rax* are the low-rank basis matrices, S is a diagonal matrix containing the singular values 8;, and is the rank of the adaptation. This low-rank formulation can be equivalently expressed as
V USV
Σ 8t Us & U/+
where and denote the i-th columns of U and V. respectively, and @ refers to the outer product of tensors. The rank r directly controls the number of trainable parameters, making this formulation particularly suitable for rank-adaptive parameter-efficient fine-tuning (Zhang et al. (023).
This low-rank adaptation naturally extends to tensor rensor-based models using the CP (canonical polyadic) decomposition. For a layer weight tensor with d modes, Wo E R X-- the low-rank adaptation defined as:
Network Layer
Wo + (B,
z
W
Zi+s
(3)
(BB
Σ
8i u
8 ....8
1=1
where = (UO) (d)) represents the collection of low-rank matrices Uti) e R ( denotes the i-th column of the j-th basis matrix, and (81, (s,,....8,, 8x) 2 0 is vector of nonnegative
3

---

Published as a conference paper at ICLR 2025
parameters representing form of tensor singular values. In this setting, the low-rank adaptation is compactly represented by the basis matrices B and the vector scaling factors s.
To fine-tune V (B,s) while simultaneously minimizing the rank r, introduce bilevel optimization strategy. Given a fine-tuning loss function {BB s; x, v. and a dataset split into two parts Dj and D2, consider objective functions for the two data sets
fi s)
Σ (x.g)ED;
(BB, (B,,;
i= 1 1,2.
D
The fine-tuning process is then formulated as the following bilevel optimization problem:
(upper-level)
fi(B" 222.2l..le
min
(I)
(lower-level)
s.t. (8)
arg min (),
BEVER"1 X"*""
where is a regularization parameter that controls the sparsity of the singular values. The bilevel nature of this problem arises from the fact that the optimal basis matrices 8* (s) for given are determined by minimizing second objective function, (2, s). Moreover, given the nature of the parameterization V none of the objective functions is in general convex, even if L is.
critical aspect of solving bilevel optimization problems computing the hypergradient, which captures how changes in the upper-level parameters affect the lower-level solution B²(ss, By the chain rule, the hypergradient the upper-level objective fi (B3 (s), s) is given by:
d ds (B) = 0B (B' 0, 0. (B),
The key computational challenge lies in determining 0, (s), which represents how the optimal basis (s) changes with Using first-order stationarity conditions, this dependency is governed by the implicit gradient system:
fz
(s), (s),
-,00sf22 (s),
Solving this linear system is necessary to compute the implicit gradient in Equation
Given the computational complexity solving the implicit gradient system exactly, we explore efficient approximation techniques that exploit the structure of the problem. As discussed in Section 2 various methods, such as inverse Hessian approximation and conjugate gradient techniques, have been proposed in the literature. In the following section, we introduce new closed-form approximation that leverages the tensor structure of the problem to significantly reduce computational overhead while maintaining accuracy.
For the sake of simplicity, we decided to limit the theoretical discussion to the Euclidean case. However, everything transfers with minor adjustments to the Riemannian setting by interpreting all the derivatives through their Riemannian counterpart. A similar derivation done for example (Li would be similar those presented there. In particular,
& Ma 2024) and the computations in we have Riemannian manifold only in the lower-level problem (the case we considered in our experiments), the stationarity condition should be interpreted as 0B (z) now the differential restricted to the tangent space (s-(ss) V to the manifold V at the point 5* (s) (with V either the Steifel or the oblique manifold in our case). The implicit gradient equation 3 is derived in the same way by interpreting the Hessian the Riemannian Hessian on V.
where Og f2 (a),
EFFICIENT HYPERGRADIENT APPROXIMATION
As discussed in the previous section, the primary challenge in solving the bilevel optimization problem Equation (I) lies in the fact that first-order methods require second-order information, particularly the calculation of the implicit derivative, which is obtained the solution to Equation (3) While this can be computationally intensive, structured numerical approximations of the Hessian 02 ft (such as diagonal or low-rank approximations) have been employed in prior work ZZang jet al. 2022, Lorraine et al. 2020) to simplify the hypergradient computation. Nonetheless, these approaches come with computational overhead.
4

---

Published as a conference paper at ICLR 2025
In our setting, we exploit the specific parameterization structure of the problem derive efficient closed-form approximation for the hypergradient. This leads to a computationally tractable solution without fully solving the implicit gradient system. The following theorem formalizes this result. For brevity, we will use superscript to denote the evaluation of variables and functions on the optimal pair (B" (s); 8), solution the lower-level problem.
Theorem 4.1 (Hypergradient Approximation). Denote by (2( f2(B,s) as a function of V. In the setring of Section assume that the gradient is locally approximately constant. That is, there exists constants K such that
(B()
vs: 11:1s
Additionally, assume that the following bilinear operator is uniformly invertible and bounded:
(1
sup Bl|a=1
[1 (120
Then, for = (the matrix case), we derive the following closed-form, Hessian-free solution for the approximate hypergradient:
G(s) 0.fi diag ( Byan U* 0 O5-
where 3 refers the Hadamard product (entrywise).
Moreover, the numerical solution obtained by neglecting the Hessian satisfies the following error bound for d d=2 2:
G(s)
(BBB KB.
ds
For 2 (tensor case), a tridiagonal approximation of 0z v leads to the following closed-form approximation:
G(s) = = diag Σ Unii Opw
O5-
with the corresponding error bound:
d Σ
[C(s) _ (B² ds
KB
Σ 2-
We provide detailed proof of this theorem in Appendix We would like moreover to remark that, if the constraint V on the basis B is compact and /2 is twice continuously differentiable, then automatically the first assumption Theorem [.1 is satisfied for Weierstrass theorem. This will naturally hold if we impose orthonormal constraints on the basis, as we will discuss in Section 7
Given the approximation error Theorem 4.1 it important to modify the constraint the upper- level problem to ||s||| < 7 + numerical instability due to division by s. This adjustment ensures that approximation remains particularly in cases where the singular values s; become small. More precisely, one can consider the perturbed L simplex:
7 and 2 entrywise, where >> 0 is small constant to prevent
S {s E E, ||+||| F),
which is still convex and thus amenable to projection- methods, motivating our choice of stochastic Frank-Wolfe for the upper-level problem in the next Section 5
OPTIMIZATION WITH STOCHASTIC AWAY-STEP FRANK-WOLFE
Our goal is to minimize objective function defined the finite sum of a set of functions. The main challenge here lies in the high computational cost: calculating the objective value or its gradient requires aggregating information across all functions in the set, which is substantially more expensive than evaluating these quantities for single function or a bunch of them. This is especially problematic when the set of functions is large, which can quickly make optimization infeasible in practice.
5

---

Published as a conference paper at ICLR 2025
In order solve the bilevel optimization problem in Equation (T. hence proceed as follows: first, we compute an approximate solution to the lower-level problem using a standard stochastic gradient-based method; then we compute a stochastic approximation G(s) of G(s) by sampling minibatch of data to represent the loss fi; finally we use the G(s) to update the solver for the upper-level problem.
The hypergradient approximation G(s) obtained in Theorem 4.1 can be efficiently computed using automatic differentiation. Specifically, to calculate G(s), we first approximate the optimal basis (s) for fixed by optimizing for finite number of steps, then we compute the partial derivative (s), leveraging the fact that automatic differentiation can efficiently compute 0zff in single backpropagation step. By exploiting the structure of the parameterization, this method bypasses the need for full Hessian and allows for scalable fine-tuning even in large-scale settings.
As the upper level is constrained optimization problem with convex simplex constraints, approach it with a stochastic version of the away-step Frank-Wolf' algorithm. This allows us to employ a projection-free approach, which reduces the cost of the upper-level solver and allows us to obtain important theoretical guarantees of convergence to sparse structure in a finite number of steps (See Section 6). At each iteration Sns the main steps of the Frank Wolfe algorithm (Guélat & Marcotte 1986; Beck & Shtern 2017 Bomze et al. 2020) are as follows:
Frank-Wolfe direction Compute search direction h, that minimizes linear local approximation of the upper-level loss function as:
hn 2n Sn
where
2n arg min ((s.) Ts .E.
Note that, as S' is sparse simplex, the variable can be computed in an efficient way by simply looking the entries of G(sn). See Appendix
Convergence criterion Stop if (s,)) hn S P
Away-step direction Compute search direction b,, that maximizes a linear local approximation of the upper-level loss function as:
bn Sn Yns where Yn = arg max (sp)) sEC, with C. {s E S supp (s) supp, (sn)) and (s) [ 8; $). Note that this problem can be solved efficiently as for the FW direction computation by sweeping through the entries of Gssn). ). See Appendix
Steepest direction Set dn hn if (G(ss) h,, 2 T Set d, bn. otherwise.
Line search Choose a = if dn hn. Otherwise, choose a as the largest a such that 8n ad, S. Then choose a² (0, a.ax] using line search.
Update variables Update the current iterate as 8a+1 = on + dn If n 2 no then truncate 8 by removing the entries that are smaller than s and remove the corresponding columns from U and V, effectively reducing the rank of the problem.
The resulting low-rank adaptation scheme is summarized in Algorithms and 2 In the next section, we will see that the proposed algorithm converges in expectation with a sublinear rate (see Theorem 6..2 for further details) and it is also able identify the surface containing a stationary point gets close enough to it (see Theorem 6.5 for further details). Identifying the surface containing a solution is of paramount importance in our framework since it allows us shrink the dimension of the problem under analysis and eventually apply more sophisticated solution techniques in the end. In Appendix G we provide detailed per-iteration cost analysis of dEBORA, together with the real GPU consumption compared with (Zhang et al. 2023).
6 THEORETICAL PROPERTIES OF THE STOCHASTIC AWAY-STEP FRANK-WOLFF ALGORITHM
In this section, we propose a convergence analysis of the fine-tuning strategy. In order to simplify the notation, we let (s) = fi (B), s) where 5 (s) is solution to the lower-level problem. We hence consider, in place of Problem (1). the following optimization problem:
min f()) SES

---

Published as a conference paper at ICLR 2025
Algorithm 1 dEBORA: Efficient Bilevel Optimization- -based low-Rank Adaptation
Input: Choose T, > 0, precision p 0, and truncation step no- Initialize adapters and E
2: For n = 000,,,...
3: Compute G(s,)) stochastic estimation of the hypergradient as Algorithm
4: hn = FW-direction(((ss)) T,);;
5: If Convergence-criterin (C
(G(s,), ht. then STOP
6:
bn
(s,,). Sn: T,E)
7:
d =
( b
8:
On = Linesearch(s,, (8n, dn.)
9:
Set Sn+11 + On
10:
In 2 no then truncate 8n+1 by removing entries smaller than e and reduce rank accordingly
11: End for
Algorithm 2 Stochastic approximation of the hypergradient G(s)
1: Given E S
2: Compute an approximation (s) arg ming (B
3: Sample a data minibatch and define fi as the estimation of fi on it
4: Compute 05. / (B 8) and
5: Assemble G(s) (B* s) diag[B* TongBB+TTghiiB s)] I
and denote with the diameter of S. Moreover, we assume the stochastic approximation G of the hypergradient V is available, such that the following assumption is satisfied. |
Assumption 6.1. Let us denote e(s, 5) = (v ((3)) (s - -3). We assume that for any 8 E S,
there exist > 0 such that
E [e{s, AsES.
(5)
Remark 6.4 will discuss how the proposed analysis transfers to the chosen biased approximation ((s) from A Algorithm? 2 Notice that, by Jensen and Holder inequalities respectively, if Assumption 6. holds, we have the following
[[e((, s)]l B[le(s, 3)]] < [[[e(s, 3)) S.
Note moreover that, the stochastic optimization literature, standard quantify the accuracy of the stochastic first-order oracle assuming bounded variance of the stochastic gradient estimates
(Braun et al. y022;: for every E S, there exists x² > O such that E
V)()) (ss)
S 02
easy see that this assumption on the gradient estimates implies Assumption 6.1 Indeed, have:
T (c(8,8) [[ -
< < -a0))))0000) [ ||s 812 A2A2
-G(s,) hnn and F. with FW E arg min m (V)(s,) (s 8,)} - s, the Frank-Wolfe direction obtained using the exact gradient. Since S is convex set, point s* is said be stationary for the upper-level problem in I when Vf(ss) (
Let us define In -Vf(sn) hip Zr
fssss) of
5*) 2 0 for s E S. Then, g. FW is an optimality measure, if and only if s, S is stationary point. Now show that Assumption 6.1 is satisfied with a sufficiently small X if the stepsize on is generated with suitable line search. Thus, Algorithm Satrrithmm[oom converges in expectation a stationary point at sublinear rate on non-convex objectives with Lipschitz continuous gradient. The constant in the convergence rate depends on the quality of the gradient estimate (the more precise the estimate, the smaller the constant). The proof can be found in Appendix P
i.e. w.
We have biased stochastic estimate of the original hypergradient, F.G] RV
7

---

Published as a conference paper at ICLR 2025
Theorem 6.2. Let { be sequence generated by Algorithm applied to f S. where Vf is
Lipschitz continuous with constant M. G satisfies Assumption 6.1 with
_ 2+ 21
p, 0 0
(7)
and the step size On salisfies
man In
On 2 0n = min
On
(8)
MA A
f(sn) - f(sn + an (n) 2 pan.In
(9)
with some fixed p s.t.
< p (1 A
(10)
2(1 n7}39b W
Then for every T E N.
24 ( - -³)
E [
(11)
Tp(1 - )
where 97 Equations and can be satisfied with suitable line searches/stepsize rules (see, e.g., (Bomze et al. 2020: 2021 Rinaldi & Zefliro 2022)). In particular, Lemma below shows that this is the case for the fixed step size a, an. and the modified Armijo line search rule which sets
min
In
FW and f min,es (()).
US IT
On 8²,
(12)
where j is the smallest non-negative integer such that (8a) - f(sn. + a,,d)) 7ansnn
(13)
with E (0, 1/2) and E (0, 1) being two fixed parameters. The proof can be found in Appendix
Lemma 6.3. Let Assumption 6.7 hold with
2
D. 0 OSn<
(14)
2 2+ 2m
and let ā, being defined as in Equation (8) At iteration if on is determined by
the fixed step size rule then Equation
On = ān.
8 holds and Equation p is satisfied with
(1 A2 M
1-
0 O<PSin min
2(1 9) W: 2(1 + m))
the Armijo line search described in Equations (12 and 13 then
min(1, 25(1 ))),n.
and Equations K and (9)
hold.
Remark 6.4. It is easy to see that Assumption 6.1 holds with that satisfies Equations and [44
when the batch size chosen to build the approximate stochastic hypergradient G(s) is large enough. We also observe that is possible to decompose x in Equation (6) as a first term completely depending on the norm of the Hessian, and second term controlled totally by the stochastic part. In particular, one would decompose the error as
c(s, 3) = (vf(s) -
3) (G(s)- (()
where G(s) is again the closed form estimate of the hypergradient presented in Theorem and G(s) its stochastic counterpart where the objective function is evaluated on data batch. Under the hypothesis that the constant 3 in Theorem 4.1 works across different batches, by using Cauchy- Schwarz and the triangular inequality we get
E[le(s, I]] < K8A [[](G(s) (s
3)|| K3A X,
where now we define X as an upper bound of the third term. particular, this allows to get potentially sharper bounds when estimating the minimal batch size needed to satisfy Equations 7 and (14).
8

---

Published as a conference paper at ICLR 2025
Table 1: DeBERTaV3-bant fine-tuning GLUE benchmark.
Method
Params
MNLI
SST-2
CoLA
QNLI
RTE
MRPC
STS-B
(Ace)
(Ace)
(Mec)
(Aco/F1)
(Acc)
(Ace)
(Acc)
(Cor)
Full FT
184M
89.90
95.63
69.19
92.40/89.80 80
94.03
83.75
89.46
91.60
HAdapter
1.22M
90.13
95.53
68.64
89.27
94.11
84.48
89.95
91.48
PAdapter
1,18M
90.33
95.61
68.77
89.40
94.29
85,20
89.46
91.54
LoRA =
1.33M
90.29
95.29
68.57
90.62/90.61
93.91
85.5
89.75
89.10
oRR
1.27M
90.44
95.64
68.77 68.76
90.59/90.65
94.11
86.00
89.44
91.41
dEBORA 7 16
0.4M
90.01
95.29
68.72
91.88/89.2 20
93.42
83.75
90.16
90.84
dEBORA (Oblique) r 16
L.3MM
90.0
94.83
69.15
62/85.28099
87.33
83.03
91.42
91.24
dEBORA (Stiefel)
0.8M
89.79
95.65
68.39
89.74/86.58
93.83
84.12
91.18
91.54
We now report local identification result related to the Algorithm More specifically, state that our method successfully identifies the manifold containing a stationary point once it is sufficiently close to it. As we already noticed, guarantees of identification of this manifold in finite number of steps is of critical importance within our framework, as it facilitates the reduction of the problem dimensionality and ultimately enables the application of more sophisticated solution techniques in the final stages. In other words, once the optimal face of the simplex is found, we are guaranteed that optimization can continued just there without any repercussion, potentially drastically reducing the number of parameters.
The proof of this result can be found Appendix [ useful theoretical tools and notations. We define the face of S exposed by (.))), with E S, as
To ease the analysis, we first introduce some
F(()((s) arg min V v(())²²
S
and the minimal face of S containing s E S as F(s). We let X, = -V-))) s), S and notice that for stationary point s* of Problem (4) it holds (o(s)) 2 of extreme points in S. Furthermore, we define the value
Ve E V,, where V is the set
MIN (s")
min vEV+(S)
\a(s*)
(15)
with V : > 0}. Finally, we indicate with Br(,) the ball with radius I(x) > 0 centered xr. We have:
Theorem 6.5. Let {un} be sequence generated by Algorithm 1 Let s" E S be stationary point of Problem 4 s.t.
2x - .AMIN
+F((V[(('))= = that is strict complementarity holds in 8"
Then, there exists T(x*) 0 s.I. sn Bree)) FF*"*) then 8841 F(s"). Furthermore if the level set ((f(s)) is such that ((f(s))) S Br(s*) then 8.41 Br(st) F(F(s))
EXPERIMENTAL EVALUATION
In this section, we present numerical experiments to showcase the effectiveness of the proposed bilevel optimization method for fine-tuning low-rank adapters. For fair comparison, the validation set was not used any of the two losses during training. To create the two loss functions fis f2, we randomly partitioned the dataset into equally sized subsets, using one partition for the upper-level loss and the other for the lower-level loss. All experiments were run on a 80GB NVIDIA A.00 GPU.
7.1 GLUE BENCHIARRK
In our first experiment, we fine-tuned DeBERTaV3 (He et al. 2023) on the GLUE benchmark (Wang et al.) 2019), comparing the proposed approach with state-ot of-the-an methods for fine-tuning large language models (LLMs). These include AdaLoRA (Zhang et al.] 2002), LoRA (Hu et al. 2022). Pfeiffer adapter (Pfiiffer al. 202T). Houlsby adapter (Houlsby et al. 2019). and full fine-tuning

---

Published as a conference paper at ICLR 2025
Table 2: Fine-tuning performance on tensor layers. Left: ResNet50 fine-tuning on CIFAR-10. Right: Fine-tuning of Dreambooth Stable Diffusion. First rank refers to the LoRA rank of the UNet layers, the second refers the text encoder. In the parameter count, M stands for million and K for thousands. Initial ranks for AdaLoRA are 8 for each layer.
Method
Val. Accuracy (%)
# Params
Method
Loss
# Params
LoRA (r
89.66
1.17M
LoRA (r 2,
0.245
3.4M
LoRA (r
87.5
588K
LoRA (r r,
0.247
5.5M
LoRA (r 2)
70.03
147K
LoRA (r =
0.241
11.3M
AdaLoRA
93.28
316K
AdaLoRA
0.245
4.7M
AdaLoRA
90.97
79K
AdaLoRA
0.247
1.78M
dEBORA 8
93.74
64K
dEBORÅ 16
0.262
0.4M
dEBORA (Oblique) 16
85.65
66K
JEBORA (Oblique) 16
0.231
0.4M
dEBORA (Stiefel) r 16
85.83
72K
dEBORA (Stiefel) 16
0.252
0.4M
As in Zhang et al. 2023). the adapters were applied to each attention layer, including the query, key, value matrices, and ferd-forward layers. Results are presented Table []]
Additionally, we tested our approach in both unconstrained and constrained settings by forcing the basis matrices have columns of unitary norm (Oblique) or orthonormal columns (Stiefel). As both these constraints form a manifold with an explicit retraction, we compute B by performing first-order stochastic Riemannian optimization [Sato| (202T) the lower level. Given the product nature of the constraints and the relatively small starting rank, retractions in these cases remained computationally affordable.
7.2 FINE-TUNING OF HIGHER-ORDER TENSOR LAYERS (d 2)
In this experiment, evaluate our bilevel optimizer fine-tuning higher-order tensor layers. We tested ResNet50 (He et al. 2013) on CIFAR- 10 (Krizhevsky & Hinton 2009) and Stable Diffusion (Rombach et al. 2021p, with results reported in Table (left) and Table 2 (right), respectively. For ResNet50, we applied adapters to each convolutional layer while retraining the final fully connected layer with an appropriately sized one. All methods used the same training settings: constant learning rate of 5 x 10-1, weight decay of x 10-3 LoRA a 32, and no dropout. We note that the original LoRA implementation (Hu et al. 2022 for convolutional layers uses matrix factorization of the weight tensor, scaling the number of parameters as (rr(F F + C)²)). In contrast, our Ci-like factorization scales more efficiently (r((2)) C C+FF), where F is the number of output features, C is the number of input channels, and l is the kernel size. This more efficient representation reflected in the total number of trainable parameters reported in Table 2 (left). Despite using fewer parameters, our approach competes well with the baselines, particularly in the unconstrained setting, which is computationally less challenging due to the absence of retractions.
For the Stable Diffusion experiment, we inserted adapters into the convolutional layers of the UNet and the linear layers of the text encoder. All models were trained under the same conditions as in (Mangrulkar et al. 2022), and the results reported in Table (right). For AdaLoRA, implemented the same rensor-based convolutional adapter representation used in our method, which led higher compression compared to LoRA, which does utilize tensor factorization. Even with a similar parameterization, our method consistently outperforms the other baselines, achieving better results with fewer effective parameters.
8 CONCLUSION
In this paper, we introduced novel bilevel optimization framework for low-rank adaptation, providing parameter-efficient fine-tuning strategy for large-scale neural networks. Our approach leverages a dynamic rank selection mechanism within a bilevel structure, enabling efficient adaptation while minimizing the number of trainable parameters. A key contribution of our work is the theoretical analysis of the proposed stochastic bilevel optimizer, where we established convergence guarantees. Through variety of experiments the GLUE benchmark. ResNet50, and Stable Diffusion, demonstrated that our method consistently matches or outperforms existing state-of-the-an approaches such AdaLoRA LRR and LoRA, while significantly reducing the parameter count.
10

---

Published as a conference paper at ICLR 2025
FUNDING ACKNOLEDGEMENTS
The work of Francesco Rinaldi has been partially funded by the EuropeanUnion NexxGenerationnUU under the National Recovery and Resilience Plan (NRRP), Mission Component Investment 1.1 Call PRIN 2022 No. 104 of February 2, 2022 of Italian Ministry of University and Research; Project 2022BMB W2A (subject area: PE Physical Sciences and Engineering) "Large-scale optimization for sustainable and resilient energy systems. ", CUP 153D23002310006.
The work of E. Zangrando was funded by the ing". Francesco Tudisco is partially funded by the PRIN-MUR project MOLE code: 20227K5ME7 MUR D.D. financing decree n. 20428 of November 6th, 2024, CUP B53C24006410000 and by the PRIN-PNRR project FIN4GEO within the European Union's Next Generation EU framework, Mission 4, Component 2, CUP P2022BNB97.
project Low-parametric machine learn-
REFERENCES
Armen Aghajanyan, Luke Zettlemoyer. and Sonal Gupta. Intrinsic dimensionality explains the effectiveness of language model fine-tuning, 2020.
Armen Aghajanyan, Sonal Gupta, and Luke Zettlemoyer. Intrinsic dimensionality explains the effectiveness of language model fine-tuning, In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the I Ith International Joint Conference Natural Language Processing (Volume 1: Long Papers), pp. 7319-7328, 2021.
Amir Beck and Shimrit Shtern. Linearly convergent away-step conditional gradient for non-strongly convex functions. Mathematical Programming, 164:1-27, 2017.
Dimitri Bertsekas. Nonlinear Programming, volume 4. Athena Scientific, 2016.
Immanuel M Bomze. Francesco Rinaldi, and Damiano Zeffiro. Active set complexity of the step frank-wolfic algorithm. SIAM Journal on Optimizationn 30(3):2470-2500 2020.
Immanuel M Bomze, Francesco Rinaldi, and Damiano Zeffiro. Frank-wolfe and friends: a journey into projection-free first-order optimization methods. 4OR, 19(3):3133345 2021.
Gábor Braun, Alejandro Carderera, Cyrille W Combettes, Hamed Hassani, Amin Karbasi, Aryan Mokhtari, and Sebastian Pokutta. Conditional gradient methods. arXiv preprint arXiv:2211.14400 2022.
Benoît Colson, Patrice Marcotte, and Gilles Savard. An overview of bilevel optimization. Annals of operations research, 153(1)233-2256, 2007.
Tim Dettmers, Artidoro Pagnoni, Ari Holtzman, and Luke Zettlemoyer. QLoRA: Efficient finetuning of quantized LLMs. Advances in Neural Information Processing Systems, 36, 2024.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meea-nee for fast adaptation of deep networks. Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference Machine Learning, volume 70 of Pruceedings of Machine Learning Research, pp. 1126 1135. PMLR, 06-11 Aug 2017. URL https: htap::://ppoceeddngge mlr.
wtw.piing.................eeeeee wrw.sprsspee...... /
Finnl 7a. html
Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil. Forward and re- verse gradient-based hyperparameter optimization. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference Machine Learning, volume 70 of Pro- ceedings of Machine Learning Research, pp. 1165-1173. PMLR, 06-11 Aug 2017. URL https://proceedinng: m. www..press/eeee httppees//o//fracccccc1111 html]
Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil. Bilevel programming for hyperparameter optimization and leaanng. In International Conference on Machine Learning, pp. 1568-1577 PMLR, 2018.

---

Published as a conference paper at ICLR 2025
Riccardo Grazzi, Luca Franceschi, Massimiliano Pontil, and Saverio Salzo. On the iteration complexity of hypergradient computation. In Hal Daumé III and Aarti Singh (eds.), Pro- ceedings of the 37th International Conference Machine Learning, volume 119 of Pro- ceedings of Machine Learning Research, pp. 3748-3758, PMLR, 13-18 Jul 2020. URL html]
m htttps://proceedin wtt.saa.w.......seeeeeeeee
Jacques Guélat and Patrice Marcotte. Some comments on wolfe's "away step'. Mathematical Programming, 35(1):110-119, 1986.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition, 2015. URL httpt:tt//arratto http://///aaaw..o//aa/////////// http://w..rr/aa///1///1/// 03385
Pengcheng He, Jianfeng Gao, and Weizhu Chen. Debertav3: Improving deberta using electra-style pre-training with mudient-ddieentanlle embedding sharing, 2023. URUattps:/arxxv.
abs 2111. 09543
Neil Houlsby, Andrei Giurgiu, Stanislaw Jastrzebski, Bruna Morrone, Quentin De Laroussilhe, Andrea Gesmundo, Mona Attariyan, and Sylvain Gelly. Parameter-efficient transfer learning for NLP. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning. volume of Proceedings of Machine Learning Research, pp. 2790-2799, PMLR. 09-15 Jun 2019. URL https: http:::://rroceddings. mlr
pJeas//97/hoolssyIIa.. html
Edward J Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. Lora: Low-rank adaptation of large language models. arXiv preprint arXiv:2106.0960 09685, 2021.
Edward J Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang. Lu Wang, and Weizhu Chen. LoRA: Low-rank adaptation of large language models. International Conference Learning Representations, 2022. httpttss:: http:///peewwweeeeeeeeeeeeeeeeee
1d=nZeVKeeFYE9
Chenghao Huang, Qing Liu, Bingyu Lin, Tong Pang, Changlong Du, and Ming Lin. Lorahub: Efficient cross-task generalization via dynamic lora composition. arXiv preprint arXiv:2307. 13266, 2023.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Technical Report 0, University of Toronto, Toronto, Ontario, 2009. URL. /nttts:// cs toronto... wecu:/kriz/eearnieeei featuuute---
Chunyuan Li, Heerad Farkhoor, Rosanne Liu, and Jason Yosinski. Measuring the intrinsic dimension of objective landscapes. In International Conference on Learning Representations, 2018.
Jiaxiang Li and Shigian Ma. Riemannian bilevel optimization. arXiv preprint arXiv:2402.02019, 2024.
Vladislav Lialin, Namrata Shivagunde, Sherin Muckatira, and Anna Rumshisky. Relora: High-rank training through low-rank updates, 2023.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search, 2019. wttp://gggggag//......00 09055)
URL
Jonathan Lorraine, Paul Vicol, and David Duvenaud. Optimizing millions of hyperparameters by implicit differentiation. In Silvia Chiappa and Roberto Calandra (eds.), Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pp. 1540-1552. PMLR, 26-28 Aug 2020. URL httpps:/prroceed.ngs
wwwpsresssse... 08/ 11//oorraine20a... htmmm
Sourab Mangrulkar, Sylvain Gugger, Lysandre Debut, Younes Belkada, Sayak Paul, and Benjamin Bossan. Peft: State-of-the-aat pfrfmeter-efficient fine-tuning methods. https: /github 2022.
12

---

Published as a conference paper at ICLR 2025
Jonas Pfeiffer, Aishwarya Kamath, Andreas Rücklé, Kyunghyun Cho, and Iryna Gurevych. Adapter- fusion: Non-deetru task composition for transfer learning, 2021. URL httph::tp///c.. //axxiv brg/abs/Be 2005. 00247
Rushi Qiang, Ruiyi Zhang, and Pengtao Xie. BiLoRA: Bi-level Optimization Framework for Overfitting-Resillee Low-Rank Adaptation of Large Pre-trained Models. arXiv preprint arXiv:2403. 13037, 2024.
Francesco Rinaldi and Damiano Zeffiro. Avoiding bad steps in frank-wolfe variants. Compulational Optimization and Applications, pp. 1-40, 2022.
Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer. High- resolution image synthesis with latent diffusion models, 2021.
Hiroyuki Sato. Riemannian optimization and its applications, volume 670. Springer, 2021.
Steffen Schotthöfer, Emanuele Zangrando, Jonas Kusch, Gianluea Ceruti, and Francesco Tudisco. Low-rank lottery tickets: finding efficient low-rank neural networks via ma- trix differential equations. In Advances in Neural Information Processing Systems, 2022. URL https::/prroceeddng....eee neurips wwtpppprpccppppp..pppppppp fat.://88000acccaccccc3aaaaaaaee
Mojtaba Valipour, Mehdi Rezagholizadeh, Ivan Kobyzev, and Ali Ghodsi. DyLoRA: Parameter- Efficient Tuning Pre-trained Models using Dynamic Search-Free Low-Rank Adaptation. In Proceedings of the 17th Conference of the European Chapter of the Association for Computational Linguistics, pp. 3274-3287, 2023.
Sara Venturini, Andrea Cristofari, Francesco Rinaldi, and Francesco Tudisco. Learning the right layers data-driven layer-aggregation strategy for semi-supervised learning on multilayer graphs In International Conference on Machine Learning, pp. 15500-35022 PMLR, 2023.
Alex Wang. Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R. Bowman. Glue: A multi-task benchmark and analysis platform for natural language understanding, 2019. URL
https://arxiis org/bb/wworroosss/.///o////bbbss
org abs 804 07461
Hongyi Wang, Saurabh Agarwal, and Dimitris Papailiopoulos. Pufferfish: Communication-effiiiennn models at no extra cost. Proceedings of Machine Learning and Systems, 3:365-386, 2021.
Emanuele Zangrando, Steffen Schotthöfer, Gianluca Ceruti, Jonas Kusch, and Francesco Tudisco. Rank-adaptive spectral pruning of convolutional layers during training. In Advances in Neural Information Processing Systems, 2024.
Qingru Zhang, Minshuo Chen, Alexander Bukharin, Nikos Karampatziakis, Pengcheng He, Cheng, Weizhu Chen, and Tuo Zhao. Adalora: Adaptive budget allocation for parameter-efficien fine- tuning, 2023.
Yihua Zhang, Yuguang Yao, Parikshit Ram, Pu Zhao, Tianlong Chen, Mingyi Hong, Yanzhi Wang, and Sijia Liu. Advancing model pruning via bi-level optimization. In Advances in Neural Information Processing Systems, volume 35, pp. 98309-18322) 2022.
Jawei Zhao, Zhenyu Zhang. Beidi Chen, Zhangyang Wang, Anima Anandkumar, and Yuandong Tian. Galore: Memory-efficien Ilm training by gradient low-rank projection, 2024.
A APPENDIX
In the next sections, we will include the proofs of the results the main text and schematic implementation of the training procedure.
13

---

Published as a conference paper at ICLR 2025
B PROOF OF THEOREM 4.1
The hypergradient equation given in Equation requires just to calculate (sB* i.., a solution of the implicit gradient Equation
8zf00,B* + 0,0=f =.
(16)
Using the chain rule and the fact that f2(B, (2 8)). have that
03 0z0b 0z0g L - 0 LE00 O8 + 8v L. In similar manner, we have that
(17)
0, Lid v = By Li + Oy L2000,0 v
(18)
By plugging Equations and (8) in equation Equation
we get the following:
(oy L2 V 0g V Oy Liog L )0, + og L v 0. V by suitably rearranging this expression, we have Lg V (0.V*0,8' 0,8 - 0, 0² + Bg (3 +0,0gV") =
Ov Li000, V =0,
(19)
Assuming for the moment that 0g L3 = 0, then the solution of Equation is given by the solution
of
a -0,0g
Since (B, 8) is multilinear the basis matrices (U ,.... U, the partial derivatives have diagonal terms equal to zero, i.e. 0 v 0, we get the following system of equations
d
Σ
-,,000 V,, i= 1=.....dd
We hence just need to calculate
Py vos V -yco, Σ Su .... @ @ ....V .... ee
For 2 3, the last system cannot be solved closed form, but given the symmetry Hessian one could exploit the structure through the use of Krylov methods. For d 2 instead, the last calculation leads to the following equality:
Σ 0,, ((2)) Ea @ - @ (2))g
83
By testing the last equation on the left by and on the right by ej we get:
0 U - 63n (22)
that finally leads to
0 (2) 10
[1(2 8,
j8 $3
(() 8 0 9g 0,, 13
We hence get the final hypergradient expression by means of Equation 2
d (B = 0,fi d0agg Ogonf (22)
s-
ds
We are just left to estimate the error between this approximate solution and the real hypergradient. The structure of Equation (19) can be summarized by giving an error estimate for linear system of the form
A(Bz + d) = 0.
A = 0 Lū B V U.
C Ly D V.
b 0, "r = 0.0g
x O.B".
14

---

Published as a conference paper at ICLR 2025
Now let x²' (AB CAb Cd) be the solution of the above linear system, and let
y² = -D- dd the solution of Dr + d = 0, which exactly represents our approximation. Let us define
M = -AB + CD and estimate the distance between the two solutions:
l1y - =1' - = (I - - -
- M Abll & | M -M'CCl + 1IMA|111]]]0)))))
By using the fact that for two invertible linear operators P, Q, the identity (P + Q) -1 p-1 (PPQ + Q) holds, we get that
D - --1---1- - D- - (CD) (C -CD)) (20)
By inserting Equation 200 in the last estimate we get 1ly x=
+| -| |||A|III =a||A||
|ID BMM + ||M-6)
from which, by using the hypothesis the uniform invertibility and boundedness of CD, and the control on the Hessian norm, we get by the use of Neumann expansion for ||AB(CD)="1 I K3 < 1
[(CD)-
33
|M <
S - K
-1
Finally, we get
B²
B
11y - -0-1="11 5
B ||I|C
[bl] |A| & 3K,
K
B
1 K
where the omitted constant is bounded because the basis lies in product of Stiefel manifolds, which are compact, and thus all the terms in parenthesis can be bounded. For the general tensor case > 2, following the previous calculation, a tridiagonal approximation ò of D immediately leads to error bound:
Ily x "I S 3K + ||D - 5-11 S 3K + |D- |||| 1-1 D D11-
By taking the difference
|c(s)- ds (s) $ 110ffi -
- -1
and using the boundedness of [|0p/itl| we get the desired result.
C ADDITIONAL DETAILS FOR SECTION 5
In this section, report additional details the computational cost of the Stochastic Away-Step Frank- Wolfe algorithm presented in Section 5
The optimization problems used to determine the Frank- Wolfe and Away-step directions can be solved efficiently since we are concentrating on minimizing a function over the perturbed T,1 simplex. In the Frank-Wolfe step, indeed minimize linear function over polytope S. We know, by means of the fundamental theorem of linear programming, that one of the vertices of S is solution of such a linear program (See.e.g., (Bertsekas) 2016)). Therefore we simply need evaluate that function on this finite set of elements, a task that can be performed at linear cost. In particular,
( E G(sn)
ifi 0,
G(sn)
$ E G(sn)s + 7G(sn);
otherwise.
with V= (vo, Ui,..., } the set of vertices of our feasible set S. Therefore, if G(s,); 0 yi=1,... r then i O, otherwise we choose i arg min, G(s,); Similarly, in the Away step, simply need to evaluate the function the set of active vertices S, used to describe the iterate. Therefore, if e S, and G(s,), < 0 V E S, then j = 0, otherwise choose j E arg max,ess. G(sn)j-
15

---

Published as a conference paper at ICLR 2025
D PROOF OF THEOREM 6.2
We first notice that, using barycentric coordinates, Problem can be written in the following form:
min f(() Aw s.t.
w = 2 0,
with = [Ug, U1, UI....,0y v/] E Rex(++1), So given a feasible iterate 8n E R" in Problem (4). we can suitably define the non-negative weights w E gr+1 related to the barycentric coordinates and define the set Sn {i wy > 0}. the set of indices related to the so-called active vertices, that the vertices with a positive weight w, in the barycentric coordinates. It is then easy to see that, in this case, the linearized problem defined in the sway-step-direction direction procedure (Step 6 of our algorithm), simply reduces to select the vertex V/ that maximizes the scalar product G(s,) uz, with j E S, = {j : wy > 0}.
The following chain of inequalities holds:
Vf(sn)
Vf(sn) hn 2 Ö(sn) cz
( c Vf(sn) K 2c, (21)
where we used Equations ( and (6) in the second and the last inequality with + = 2x. while the first and the third inequality follow from the definition of hew and hn. In particular.using the definitions of g", 9n and g from Equation 21
write
In
FW
2 In E,
(22)
In 2 In
FW
(23)
Jn In C.
(24)
Using Equations 7 and 22
we also have
S n0ān - c) S 119n
FW
(25)
Now, let distinguish three cases.
A) If u < or maz from Equation (8) it follows that In MA² o maz and on denote the indicator function for this case. We observe that, from Equations 23 and (5)
9n Let A
A
we have
In (1 W.
(26)
Using Equations 99 and 26
we can write
1 (asf(ssa-f(s--aadddd 2 Lapāā 2 LA
Pg
2
2 11
p(1 - 112
(0r
FW )²}
(27)
MA
MA²
As for Sn, by hypothesis, we have either dn = hn = 2 - Sp or dn bn Sn U/ for
some ř, [0: rl. In particular, S.+1 C. S, (i) so that 1S I S + 1.
B) If a, ā. = a aaa and dn hn then ā. = a maz 1. Let 1 denote the indicator function for this case. By the standard descent lemma, we can write
1g(f(sn) f(s++1)} = 1B{f(sn) - f(nn + dn)} 2
M
MA?
2 1 In
dd 2
2 1 9n
2
Using Equation 24h and the fact that
Tme MA²
1, obtain
I I - ((n+1)) 2 1l
In -
MA² 2
2 1B
9n
2
2
16

---

Published as a conference paper at ICLR 2025
From Equations
23
and
25
we also have
In
Fw
3
FW
1
1-3n
3n FW
FW
19n
9n
2
2
2
2
2
Hence, we can write
1
31
p(1 11)2
[s([(*n) - [88+11)] 2 1B
In
FW
2 l
( y
(28)
2
MA
where in the last inequality used Equation (TO) Reasoning as in the case above we also have |Sn+1| 1 | +1
C) If On On on and d, bn Sn 03 for j E S. Then we have w for
i E [ [1:r] S, (5) and w for i Sn {i). In particular, |Sm+1| [S
Now, based on the three cases analyzed above, we partition the iterations {0, 1,.1,.... T 1) into three subsets NA. NB. No and defined follows:
(T {n T: ān an ).
(T = {n < T: ãn = on max dn = hn (T) = (n T: an a maz dn b
We have by induction the recurrence relation proved for S,, that
|ST| - |So < (7) + (T)) [Tc for every T E N.
(29)
Since NT) T ( NB (T) from Equation (2 get
T ST Soo
T
NA (T) + (NB(T))
(30)
2
where we used Saal = = [Sr).
Considering just the good case, where we can have bound on the decrease, using Equations and 28 we can write
27
p(1-1)² 11)2
En [f(s)) f(sa+1)] E, [11 1B) f(s
MA (9 w
(31)
Using Equation 31 and taking full expectations, obtain
[(0) 1 2
[s((s)) [(n+11]
==0
E [f(nn) - -[(x+t1]+++
Σ [ff(s)) f(sn+1)l
Na(T)
NB(T)
p(1 - (1)3
p(1 p(1- - n))
2 [N(T))
min nENx(T)
[Lo
PW ) + [Nn(
min
E [[g FW y2]
MA
nENe(T)
MA
|Na(T)
min
p(1 - 11)²
E [1
FW- 2 + (Nn(T)
min RENe(T)
p(1 11)²
E. 5n
FW12
RENa(T)
MA
MA2
P(1 -2
2 ([NA(T) (Na
min
E [g
MA²
0SnST
P(1 - n)
+
E [o7]
MA²
T p1 -) E
> 2 MA
where the fourth inequality follows from Jensen's 's formula, in the second- last inequality the definition of of and the last inequality is due to Equation (30).
17

---

Published as a conference paper at ICLR 2025
Hence,
2f²M(f(su) - f*)
E [ -
Tp(1 -112
leading to the desired result.
E PROOF OF LEMMA 6.3
The proof partially follows the one in (Venturini et al. 2023). Reasoning as in the proof of Theo- rem 6.2. we have that Equation 24 holds. By the standard descent lemma, we can write
.M dI.
2 ( - c) - a² MA 2
f(sx) f(s. + ad,) 2 agn
Aa R,
(32)
2
where the last inequality follows from Equation (24). At iteration n, a is determined by:
a ān. then we can replace the stepsize in the right-hand side with obtaining
T_ MA
in Equation 32
In (ān
g
Cn
f(sn) f(sn and 2
MA²
2MA
2MA
MA
Using Equation
14) we obtain
In
1
1 1
Fr
f(8.) f(nn + dnd 2
2MA2
MA
1 1
2(1 + 11) MA
Thus, we have
9n [(sa) f(8n + (n 2 P
2 panngn
MA
the Armijo line search, then
f(s.) - f(sn + adn) 2 7agn Va 0,2 (1
7)9m
MA²
Since an is computed by Equations
(2) and
13) we can write
7)@n
0n > min
1,
MA²
1,26 (1
7)9nn
min
MA²
2 min 25(1
17) )
where the second inequality follows from Equation 14 We hence have
an 2 min (I,c
In M
for some e > 0.
We now consider two cases: when c 2 then a, is of course lower bound for the step size On and when < 1 we can still recover Equation by considering M = MM/c instead of
M Lipschitz constant.
F PROOF OF THEOREM 6.5
By the stationarity of s* and by definition of exposed face, write
Ae(s*) 2 0 Yu E V.
(33)
\=))))= =0 iff F(s).
(34)
18

---

Published as a conference paper at ICLR 2025
By continuity, can choose
r(s*) XMIN (5*) -2x >0 s.t.
(35)
2
(0 (s*)) - -T(s*) Va E (VEV((VNF(S)))
(36)
Using Equations (5) and (6) and Equation 36 we can write
((n)) T(: sn) + 2x 2 (sn) (00-)))=
(37)
Therefore,
AMIN (s*) - 2x 0 VE WEVI(VVF(()))
((s.) (v- sn) \s()t) - 2x
where in the first inequality used Equation 37 and in the second inequality we used Equation (34
and the definitions X M (s*) in Equation
15) and r(s") in Equation (35).
The algorithm will then only choose Frank-Wolff iterate 8n+1 1 to stay in the face, so 8n+1 E F. If we further have that the level set (s)(s)) is
away direction that guarantees the new
such that C(f(s)) C Br(e)) then, considering the fact that the sequence {f(s) is non-increasing. can easily that 8n41 Br(s)) (_F(s")
G PER-ITERATION COST OF DEBORA
We can give upper bound on the number of arithmetic operations carried out at every dEBORA iteration: each iteration indeed requires Tmax C, operations, where C, is the cost of one lower-level optimization step with rank r and Timax is the maximal number of iterations for the lower-level optimization step. Notice that C, includes the cost of forward, backward, and the optimization step. In particular, C, is equal the cost of performing one optimization step for (Zhang et al. (2023) without rank adaptation. Moreover, we need to add the cost of calculating the hypergradient which O(Ln??, where L is the number of layers in the neural network (assuming for simplicity layers have square dimensions of dimension n))
Notice that when the correct face identified, the cost of calculating the single iteration at the lower-level C, and the cost of the upper-level step decreases. Finally, we have a linear minimization oracle cost of Orr), and an optional line search with cost ((1). The cost of calculating the Frank- Wolfe direction (Linear minimization oracle) is (r)) because it requires solving the subproblem minges G(s,) s. This a linear minimization problem on convex polytope, its solution lies in one of the vertices for the fundamental theorem of linear programming: since vertices are the null vector and the vectors of the canonical basis, the solution can be found by simply looking at the entries of (sx,)) and finding the smallest one.
Summing up. each iteration of the method has a cost of O(T (Tmaa C, + Lrn") against (CC,) for ) for (Zhang et al. 2023) (including their cost of calculating
(Hu et al. 2022) and a OC,, + Lrn?) the sensitivity metric for rank truncation). While the single iteration of dEBORA is more expensive than the one in (Zhang et al. 2023) by a factor Tiaa (which can be predefined by the user as the maximal number of iterations for the lower-level), in Figure 4 we report different GPU statistics during training on the MRPC task (GLUE benchmark) showing that the effective computing time of JEBORA is competitive. As we can observe from Figure 4 the effective memory consumption is lower together with the average GPU power usage. Moreover, while the cost of single iteration is bigger, the effective time same accuracy is comparable.
19

---

Published as a conference paper at ICLR 2025
GPU time vs accuracy
memory over
Enemy Consumption Over Time
0.90
1.6
JEBORA
Accuracy
300
0.80
1.0
250
0.0
DEBIORA
150
Adal
LdR
100
200
400
600
800
1000
600
800
400
600
800
1000
Time
Time
Figure 1: Time accuracy for Figure 2: GPU memory con- Figure 3: Energy consumption the MRPC task.
sumption for the MRPC task. on the MRPC task.
Figure 4: GPU statistics during training (A100 80GB).
20


Reviews:
[{"review_id": "mV6iIuiG5I", "reviewer": "Reviewer_G2LN", "summary": "This paper introduces dEBORA, a bilevel optimization-based method that dynamically selects the optimal rank for each layer in parameter-efficient fine-tuning of large neural networks. By employing a hypergradient approximation that avoids large-scale computation, dEBORA significantly reduces the computational burden. Additionally, it integrates a stochastic away-step variant of the Frank-Wolfe algorithm, which eliminates the need for projection and ensures the identifiability of the optimal rank structure. Theoretical analysis confirms the convergence and optimality of the approach, while experimental results demonstrate that dEBORA outperforms existing low-rank adaptation methods in both efficiency and performance across various benchmarks.", "questions": "1. The paper introduces a strategy for dynamically selecting the optimal rank $r$ for each layer. However, it is unclear how rank $r$ is adjusted after determining the optimal solution $s$. Is $r$ recalibrated based on the optimal $s$, or is there a specific strategy for automatically tuning $r$? Could the authors clarify this process in detail?\n\n2. In Theorem 4.1, the authors state, \"assume that the gradient is locally approximately constant.\" However, the subsequent equations appear to be formulated in terms of the Hessian. Could the authors clarify the relationship between these two concepts?\n\n3. Regarding equation (3), if the matrix $\\mathcal{B}$ is constrained to lie on a manifold—as mentioned later in the experiments with the Oblique and Stiefel manifolds—would the first-order optimality condition still hold as stated? This consideration could significantly impact the approximations and key results presented in the paper. Could the authors clarify how the manifold constraints influence the formulation of the first-order optimality condition?\n\n4. In equation (35), is it necessary for the authors to clarify the invertibility of the product $AB$? Providing a discussion on this aspect would enhance the understanding of the conditions under which the equation holds.\n\n5. In line 755, the notation $||\\partial_{\\mathcal{B}}f_{2}^{\\*}||$ should be revised to $||\\partial_{\\mathcal{B}}f_{1}^{\\*}||$. Additionally, could the authors clarify where the boundedness of this term originates?\n\n   \n\nThe article contains several typographical and punctuation errors that require careful review by the authors. For example:\n\n- Punctuation errors: in lines 208, 240, 319, 401, and 407, there are missing commas. In line 686, there is an extra period.\n- Line 679: \"By\" should be \"by\".", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "- The paper presents a novel approach to low-rank adaptation by combining bilevel optimization with a dynamic rank-selection strategy, effectively addressing the challenge of parameter-efficient fine-tuning in large neural networks. Furthermore, the avoidance of implicit differentiation through an effective hypergradient approximation is a significant strength, as it reduces both computational costs and complexity.\n- The experimental results are robust and cover a wide range of benchmarks.", "weaknesses": "- Despite providing several theoretical guarantees, the paper lacks clarity in the use of some symbols and definitions of variables, making it difficult for readers to follow the authors' proofs. For instance, the notation $\\otimes$ first appears in line 141, while $\\odot$ is introduced for the first time in line 215 without prior definition. Similarly, $\\Delta$ is introduced in Equation (8) but is only defined in Theorem 6.2, and the variable $V$ is not defined in Equation (21). Additionally, the definition of $\\mu$ is missing in Theorem 6.5. The authors are encouraged to carefully review the paper and provide clear definitions or explanations for variables and symbols, either upon their first appearance or in a comprehensive notation table.\n- Although the overall structure of the paper is reasonable, the authors should consider removing the numbering from equations that are not referenced, as excess numbering creates a cluttered appearance. Furthermore, Equations (30) and (31) are noticeably smaller than the other equations, leading to inconsistencies in formatting. Additionally, the various variables within these equations lack definitions, making it challenging and time-consuming for readers. A careful review of whether each equation requires numbering, along with a focus on maintaining uniform formatting, would enhance the readability of the paper.\n- While the authors mention the recent work BiLoRA (Qiang et al., 2024), no corresponding comparison is presented in the experiments. It would be valuable to understand the rationale behind this omission. Furthermore, while the authors state that they compare against the Pfeiffer adapter (Pfeiffer et al., 2021) and Houlsby adapter (Houlsby et al., 2019), the results do not clearly reflect these comparisons. Clarifying this point and providing results for these benchmarks would strengthen the experimental section.\n\n**References:**\n\n1. Rushi Qiang, Ruiyi Zhang, and Pengtao Xie. BiLoRA: A Bi-level Optimization Framework for Overfitting-Resilient Low-Rank Adaptation of Large Pre-trained Models. arXiv preprint arXiv:2403.13037, 2024.\n2. Jonas Pfeiffer, Aishwarya Kamath, Andreas Rücklé, Kyunghyun Cho, and Iryna Gurevych. Adapterfusion: Non-destructive task composition for transfer learning, 2021. URL https://arxiv.org/abs/2005.00247.\n3. Neil Houlsby, Andrei Giurgiu, Stanislaw Jastrzebski, Bruna Morrone, Quentin De Laroussilhe, Andrea Gesmundo, Mona Attariyan, and Sylvain Gelly. Parameter-efficient transfer learning for NLP. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 2790–2799. PMLR, 09–15 Jun 2019. URL https://proceedings.mlr.press/v97/houlsby19a.html.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SV6QYfFU4C", "reviewer": "Reviewer_AG3z", "summary": "This paper tackles the problem of optimal rank selection in low-rank adaptation methods, which is essential for efficient fine-tuning of large-scale neural networks. The authors propose a bilevel optimization strategy that trains matrix and tensor low-rank adapters while dynamically selecting the best rank per layer. Their approach avoids implicit differentiation, uses a stochastic variant of the Frank-Wolfe algorithm, and provides identifiability guarantees for the optimal rank structure. Theoretical analysis and numerical experiments support the method's efficiency and effectiveness, showcasing adaptive parameter allocation across network layers.", "questions": "See the above \"weakness\".", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tThis paper addresses a longstanding issue in LoRA: selecting the optimal rank for each low-rank adapter, a key factor in balancing model performance and computational efficiency. Whereas traditional PEFT algorithms require manual tuning of this parameter, the authors propose a criterion based on optimization.\n2.\tTo address this issue, it introduces a bilinear optimization approach that alternates between optimizing the LoRA matrices and their ranks, presenting a novel contribution to the PEFT community.\n3.\tWith fewer parameters, the proposed method demonstrates competitive or superior performance compared to existing approaches such as LoRA and AdaLoRA.", "weaknesses": "[key issue] While selecting the optimal rank is indeed critical for LoRA, in many practical applications, concerns about memory consumption and training time are often more pressing. The proposed bilinear optimization approach suggests a reduction in parameter count, but the practical impact on memory usage remains uncertain. A detailed comparison of memory consumption in real-world scenarios would strengthen the paper’s contribution.\n\n[key issue] The proposed method has been evaluated on architectures such as DeBERTa and ResNet. However, the reviewer is interested in its applicability to even larger models. Specifically, would this bilevel optimization approach introduce significant additional computation time? It would be beneficial if the authors could provide both theoretical analysis and empirical results addressing this question. For instance, would the use of a Frank-Wolfe optimization strategy substantially increase training time on large-scale models such as LLaMA2?\n\nIn Theorem 4.1, the condition K≥0 alone appears insufficient to ensure that the gradient is locally constant. Additionally, the assumptions regarding the uniform invertibility and boundedness of the bilinear operator merit further examination for practical feasibility.\nThe parameter τ is tied to the rank selection process, yet its practical setting and impact on memory usage are not fully clarified. \n\nCould the authors discuss guidelines for selecting τ in practice and elaborate on its relationship with memory requirements?\n\nIn line 154, should the parameter s be restricted to nonnegative values? Further clarification on this point would be helpful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oBekTAXifI", "reviewer": "Reviewer_1wqr", "summary": "This work introduces a compact bilevel optimization framework for low-rank adaptation, offering an efficient fine-tuning strategy for large-scale neural networks via dynamic rank selection. Theoretical analysis provides convergence guarantees, and numerical experiments demonstrate that proposed method achieves performance comparable to advanced approaches.", "questions": "- Line 150-151, maybe it's better to use a figure to visualize the bypass in the neural networks.\\\n- Line 159, what's the intuition of splitting dataset to two parts?\\\n- Line 249, I understand you are focusing on the (stochastic) Frank-Wolf with mini batch of data, have you considered the full batch size?\\\n- Line 472, \"randomly partitioned the dataset into equally sized subsets\", did you ensure the label balance for both dataset?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- A relatively fresh application of the Frank-Wolf method.", "weaknesses": "See questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)