Accelerating Block Coordinate Descent for LLM Finetuning via Landscape Expansion
Authors: Qijun Luo
Yifei Shen
Liangzu Peng
Dongsheng Li
Xiao Li
Venue: NeurIPS 2025 poster ()
Keywords: Memory efficiency; optimization
Primary area: optimization

Abstract: Finetuning large language models (LLMs) is a resource-intensive task for researchers in academia, with memory constraints posing a key bottleneck. A classic optimization method, block coordinate descent (BCD), significantly reduces memory cost by segmenting the trainable parameters into multiple blocks and optimizing one active block at a time while freezing the others. However, we identify that blindly applying BCD to train LLMs can be inefficient for two reasons. First, optimizing only the active block requires backpropagating through multiple deeper yet inactive blocks, resulting in wasteful computations. Second, the frozen blocks, when they are not quite close to optimality, can narrow the optimization landscape, potentially misguiding the training of the active block. To address these issues simultaneously, we propose integrating BCD with *landscape expansion*, which unfreezes the inactive blocks and updates them in a cost-efficient manner during the same backpropagation as the update to the active block. Experiments on 8B and 70B models demonstrate that our proposed method surpasses memory-efficient baselines and matches Adam's downstream performance while requiring only 24 GB of memory for the 8B model and 300 GB for the 70B model.

Accelerating Block Coordinate Descent for LLM Finetuning via Landscape Expansion
Qijun Luo
Yifei Shen
Liangzu Peng
Dongsheng Li Xiao Li
'The Chinese University of Hong Kong, Shenzhen
Microsoft Research Asia
University of Pennsylvania
Abstract
Finetuning large language models (LLMs) is resource-intensive task for searchers in academia, with memory constraints posing key bottleneck. A classic optimization method, block coordinate descent (BCD), significantly reduces mem- ory cost by segmenting the trainable parameters into multiple blocks and optimizing one active block at time while freezing the others. However, we identify that blindly applying BCD to train LLMs can be inefficient for two reasons. First, optimizing only the active block requires backpropagating through multiple deeper yet inactive blocks, resulting in wasteful computations. Second, the frozen blocks, when they are not quite close to optimality, can narrow the optimization landscape, potentially misguiding the training of the active block. To address these issues simultaneously. we propose integrating BCD with landscape expansion, which unfreczes the inactive blocks and updates them in cost-efficient manner during the same backpropagation as the update to the active block. Experiments on 8B and 70B models demonstrate that our proposed method surpasses memory-efficient baselines and matches Adam's 's downstream performance while requiring only 24 GB of memory for the 8B model and 300 GB for the 70B model.
Introduction
Large language models (LLMs) have gained significant popularity within the research community and industry. To drive progress in this field and satisfy wide range of application needs, researchers most commonly finetune LLMs on diverse datasets tailored to various tasks and objectives. How- ever, finetuning LLMs demands extensive computational resources, with memory being primary constraint. For instance, optimizing model with N billion parameters using Adam requires at least 18N gigabytes of GPU memory (see Section 2). This memory limitation often prevents researchers from experimenting with larger models.
To address this practical challenge, researchers have developed memory efficient algorithms for LLM finetuning such as parameter efficient finetuning (PEFT), including Adapter [11], LoRA [13], prompt tuning [16], prefix tuning [17], etc. These techniques focus training small set of additional parameters while maintaining the original pretrained model unchanged. Other memory efficient methods for full parameter training have also been investigated. For example, Galore [43] applies a low-rank space projection to both the gradient and the optimizer's states to reduce memory consumption. For related works, please refer Section A.
Work done during the internship at Microsoft Research Asia. Conrespondence to Yifei Shen <yifeishheeeeee wwiffeishemmmicrosfff.. com>, Xiao <1 <lixiao@cuhk, edu. en>,
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

In addition to the existing approaches, classic optimization paradigm, known as block coordinate descent (BCD), holds a strong potential for memory efficient LLM finetuning. When optimizing a model with N billion parameters, BCD partitions the model parameters into /) blocks and optimizes over only one active block at a time. Consequently, the memory is decreased from 18 N to 2N + 16.V GB, as only the gradient and optimizer states of the active block need to be stored. In practice, BCD has been the method of choice in many data science problems in the last decade, with a wide array of variants developed for improving memory, performance, convergence, and efficiency; see, e.g.. [12, 2, 41, 36, 33].
In stark contrast to the previous memory efficient methods, and despite its intuitive memory benefits, BCD has been overlooked and rarely explored in the context of deep neural networks (hence LLMs). was not until very recently that [21] proposed BAdam, which integrates BCD into an LLM finetuning framework by training each active block with several Adam steps. Even though BAdam has shown preliminary success in reducing memory cost during training and improving performance at test time, its direct use of vanilla BCD leaves at least two fundamental aspects to be questioned:
Computing the (stochastic) gradient for single active block via backpropagation necessitates calculating the partial derivatives of the activations of multiple deeper yet inactive layers. This wasteful of computation, since these partial derivatives are not used to update their corresponding weights.
Given that the training objective is highly nonconvex, and since all blocks are frozen except for the active one, BCD tends to be misled by its local view of the optimization landscape, which potentially slows down its convergence speed.
Building on the foundation established by BAdam, we propose a simple remedy to the above two issues. Our new algorithmic framework, termed BREAD, is blend of two components: (1) Similarly to BAdam, we update the active block using several Adam steps (the BCD component); (2) differently, unfreeze the inactive blocks and update them using lightweight memory efficient optimization techniques (the landscupe expansion component). Since landscape expansionutilizes the gradients of the activations that are already calculated, it adds minimal additional computation and in fact addresses the wasteful computation issue. Furthermore, the landscape expansioncomponent provides BCD better view of the optimization landscape for better updating the current active block, thereby addressing the second point of concern. In combination, BREAD maintains the memory efficient feature of BCD with improved learning capability and faster convergence. Our main contributions are outlined as follows:
Our research identifies two fundamental limits of vanilla BCD when applied to LLMs: The wasted gradient computation during backpropagation and the suboptimal landscape caused by freezing inactive blocks. These limitations partly explain why the application of BCD in neural networks is uncommon.
Limitations of Standard BCD in LLMs:
We propose a new algorithmic framework termed BREAD, which combines BCD with a landscape expansiontechnique to address these two limitations simultaneously. It unfreezes some of (or all) the inactive blocks and updates them using memory efficient optimization techniques. BREAD maintains the memory efficiency of BCD with improved optimization ability.
Blending BCD with Landscape Expansion:
Excellent Performance: Our experiments on instruction tuning and preference optimization with the Llama 3.B and Llama 3.1-70B models demonstrate that BREAD clearly outper- forms state-of-the-art memory efficient training methods and achieves comparable downstream performance to that of Adam five math benchmarks and MTThencc scores.
2 Preliminaries Block Coordinate Descent for LLM Training
Our main focus lies in improving the efficiency of BCD for finetuning LLMs. Therefore, we first review some preliminary concepts of L.M and BCD in this section.
Objective of training LLMs.. Consider minimizing a general objective function minw H(W)= = n "E==/ (W), where W E Rd. n is the number of data samples. In the context of train- ing/finetuning L.MSs, hy (W) represents the negative log-likelihood of the autoregressive probability Fw [z,] II P w [y) 1y 2y] for the j-th prompt xy and its corresponding j-th output
2

---

Yj. In most LLM models, this autoregressive probability is modeled by transformer architecture [37], and thus W E I encompasses all trainable parameters of the transformer. including the query, key, value, and output attention matrices, as well as the gate, up, and down projection matrices of each transformer layer.
BCD for LLM training. BCD first splits the model parameters into D blocks, i.e., W (W1.... We.-. .e.. WD) where We E Ee and Σe= dN = d. The block partition in such splitring can be very flexible. For instance, the block variable W, can be either single matrix or all the trainable matrices of a transformer layer. Then, at each block iteration, BCD updates only one active block while fixing the others at their most up-to-date values. This makes each sub- problem of BCD a Dx smaller problem compared to the original one if the D blocks are partitioned evenly. Suppose at the (1++1)a 1)-th block iteration the active block is We, BCD optimizes the following problem:
sub-problem
min h(W W.E
E-1 We W441 Wb),
where MooreeN C {1,...., n is batch of the training dataset. Updating from block t = to block é D is counted as one block-epoch. Since it is intractable to solve (1) exactly, one can instead approximate the solution by implementing K Adam steps, as utilized in BAdam [21].
Memory efficiency of BCD. We analyze the memory consumption induced during training under the mixed precision training setting [25]. The memory cost is attributed to the storage of the model parameters, gradients, and optimizer states. We consider an LLM with N billion parameters and express GPU memory consumption in gigabytes (GB). Initially, one must store the FP16 model parameters for the backpropagation (BP) process, requiring 2N memory. Additionally, the optimizer maintains a copy of the model in FP32 precision, consuming another 4N memory. The gradients, momentum, and second moment vectors are all stored in FP32 precision with each requiring 4.N memory. Consequently, the total memory required is at least 18N. For example, in order to train Llama 3-8B or Llama 3-70B model, Adam requires at least 144 GB or 1260 GB of GPU RAM, respectively, which can be prohibitive in limited memory scenarios.
In sharp contrast to Adam, BCD only requires storing the FP32 model parameters, gradients, and optimizer states for the active block We, which is only 1/D of the memory consumption needed for all the parameters. Thus, in addition to maintaining an FP16 model that requires 2N memory, BCD needs total of only 2N 16N memory. Therefore, for training Llama 3-8B Llama 3-70B model and when D = 32 or B- = 80 (partition each transformer layer as block), BCD only needs roughly 20 GB 154 GB of GPU RAM, respectively, which is significantly cheaper compared to
the costs of Adam. We refer to [21] for a more detailed analysis on memory cost.
3 Limitations of BCD for Neural Networks
In this section, we show that while BCD is memory-efficient for training L.Mss, there are two major limitations when applying BCD for neural network training. To ease our analysis, let us consider a L-layer feedforward neural network model:
ze+1 = Sw, (zz), VISESL, L, with 21 = x,
where L is the total number of layers, is the input, fw. is the E-th layer's transformation.
Limitation I: Ineffective utilization of intermediate derivatives during backpropagation. Due to the compositional structure of deep neural networks, taking the stochastic gradient of the ê-th layer's parameters We requires computing the partial derivatives with respect to all the activation values of deeper layers, as shown in the following equation:
aH
OH 0z141
0zo+2 0zz+1
OW;
0ZL+1
dzl
Ōze+i OW,"
where H the objective function of the neural network training problem. During the backpropagation process, optimization methods such as Adam utilizes all the intermediate partial derivatives Te+1
of the activations in (2) for computing the gradients of the I,, I,... + 1-th layers' weight
parameters. However, since BCD only updates the active block We, the term le+1 1 is merely used for
3

---

calculating the gradient of Wi, resulting in ineffective utilization of the computed partial derivatives of the activations during backpropagation.
Limitation I: Convergence slowdown of BCD's sub-problem. To tackle a training problem, optimization methods such Adam optimize over all the trainable parameters W, while the BCD optimization scheme (1) minimizes the objective over only the current active block, keeping the others fixed. Intuitively, BCD appears narrow the optimization landscape of the training problem by freezing most of the parameters in each of its sub-problems, potentially eliminating better search directions that can lead to rapid decrease of the objective function.
To establish such an intuition formally, let us consider the following optimization problem:
min W Wi.WWa W...
H(W) = (Jw.. o Iw.. o / .... Sw, (z),
(3)
where v and y are the input and the label, respectively. fw. is the transformation of l's layer, which can be either transformer layer or feedforward layer. fw... the transformation of output layer, e.g. the language modeling head of transformer model. The following proposition establishes the condition where BCD's sub-problem is strictly suboptimal to the original problem.
Proposition 3.1. (BCD's 's sub-problens may not include optima) Consider the objective (3) with F()) being cross-entropy loss employed in the training of transformer model. When W onu is not of full rank, there exists a pair of (I, y) such that BCD's D's sub-problem is strictly suboptimal to the original problem:
min SW WL)
H(W1, WL. Wour)
min W1... W......
H(W1, WL, W
(4)
We remark that the above incquality is different from a direct conclusion of expressivity power: minw, H (W) 2 minw,, .W (W),, which does not induce the strict suboptimality. In Section D.3, we show that the strict suboptimality issue also exists for regression problem with & loss under relatively mild assumptions.
The inequality (4) characterizes the suboptimality induced by freezing the output layer. We provide further analysis and empirical evidence on the effect of freezing intermediate layers in Section D.3.
Possible slowdown in convergence. Theorem 3.1 is only for sub-problem of BCD, which does not imply that BCD will finally fail to converge. However, the strict incquality proven in Theorem 3.1 implies that BCD's sub-problem may not have the full optimization landscape for some concrete transformer problems, as the optimal solutions are not covered. This narrow landscape issue will potentially slow down the convergence of BCD's sub-problem the optima, as the search direction towards the optimal solutions is excluded.
To address above limitations,
immediate approach is apply Adam inactive blocks well. However, this essentially reverts to using Adam and undermines the memory efficient property of the BCD optimization scheme. In the next section, we will present several memory-efficient approaches to address them.
BREAD Framework and Its Analysis
In this section, we present our framework Block cooRdinate d'Eceent via IAnDscape expansion (BREAD), which solve the two limitations revealed in Section 3 simultaneously, with almost negligi- ble additional memory cost.
4.1 Motivations: Low-rank Expansion Addresses Limitations
The limitations in Section 3 attributes BCD's design of updating only one block parameters a time, primarily for the concern of memory-efficiency. In this section, we demonstrate that both limitations can be effectively addressed by applying low-cost updates on inactive blocks, with only negligible additional memory cost incurred. Formally, our approach is motivated by the following proposition.
Proposition 4.1. (Rank-I Expansion) Under the same assumption as Theorem 3.1, the suboptimality issue can be resolved by introducing rank-1 I update W
min H HW1,.'. WL, W + C) = min H(W1, WL. W Won)) SUC
SUW...

---

where S S (W1," W is the active block parameter, and C' is a rank-1 matrix.
Motivated by the above proposition, we develop the BREAD framework for accelerating BCD by performing low-cost update inactive blocks with almost negligible additional memory cost.
4.2 The BREAD Framework
Algorithm BREAD-LORA
1: Input: Model parameters (Wo) 1i= number of blocks D, iterations per block K, training dataset D {z 8) 1))] batch size B.
2: Initialization: Block-epoch index + 0, inactive block LoRA matrices Uj, VJ and optimizer
states 5 - 0, vij E [P].
3: while stopping criterion not met do
4: generate a block partition = - TD};
5:
1 to do 6: Determine partial updates or full updates J C [P] as in (6);
for one block-epoch
7:
s*.0
<0; // Re-initialize optimizer states for the active block mi
8:
W + ; 3 55;;
9:
for landscape expansion block updates k to do
10:
sample data batch in random- cesddf--eshuffled order D3 = {(1), ~ D: within one backward pass on the data batch D3 do
12:
compute the active block's ' grad. g; and correction matrices' grad. g3.; end within
13:
14:
// Update active block and correction matrices
WL. st.k +- AdammStep (Wa Wt.k-1 9 sn 11)=1);
mi
U V , + AdamStep( (U)
((U)) Vj V },9' " b/k-1);;
17:
end for
W + WLK,, U + K VJt viK 8 + K s.K + None; m
18:
19:
end for
20:
t t ++1
21:
end while
22:
return parameters (W)) L
T==1 and correction matrices (C)}
Similar to BCD framework, BREAD splits the model into D blocks, which can be partitioned either layer-wise or matrix-wise manner. Then, each block sub-problem is approximately solved using K steps. Importantly, BREAD not only optimizes the active block as in BCD, but also the weights of inactive blocks for better optimization landscape memory- manner. We introduce two concrete algorithmic instances for updating inactive blocks with almost negligible additional memory cost.
Algorithm I: Low-rank based expansion. Motivated by Theorem 4.1, we propose to introduce additional trainable low-rank expansion matrices to inactive blocks (We Je where W, is the current active block. The simplest implementation of this idea is to add LoRA with extremely low rank (e.g., rank-4) to inactive blocks.
We + Ve. Up E mm Ve R +L
(5)
We present the detailed procedure in Algorithm 1. For each landscape corrected update (Algorithm 1 line 9-16), we sample a batch of data in a random reshuffled manner, and calculate the gradient of both active block and the expansion matrices within one backward pass. Then, update the active block and expansion matrices with a single Adam step. The optimizer states of the expansion matrices are accumulated throughout the entire algorithm execution, they occupy only negligible memory space.
In the subsequent sections, we refer the Algorithm I as BREAD-LORA. Motivated by the [7], we also propose a variant that uses higher learning rate for U. au > 1, which we refer as BREAD- av LoRA+. We remark that Algorithm naturally allows any low-rank based memory efficient methods for making landscape expansion, e.g., DoRA and PiSSA [20, 24].
5

---

Algorithm II: SGD based expansion. The previous implementation uses low-rank matrices for landscape expansion. We also propose a full-rank landscape expansion method by applying on- the-fly SGD to inactive blocks. Specifically, due to the compositional structure of neural networks, the gradient of the model computed from the deep layers to the shallow layers. The strategy is to perform an SGD update on matrix whenever its (stochastic) gradient is available, and then immediately discard the corresponding gradient after the update. We term this approach as BREAD- SGD. The gradient is computed on-the-fly and only the current block's ' gradient needs to be stored. Thus, the memory overhead is negligible.
Variants of expansion block selection. Based on the derivation of (7), evaluating the gradients of the expansion matrices inexpensive for layers + 1, 1..... ., L. However, the gradient evaluation for layers 'H; computationally efficient variant of BREAD is to add expansion matrices only for layers e + .......... L. This leads two strategies of selecting expansion matrices:
,....,& is more costly, as it requires calculating 0z,+1 for j = I,..., - 1. Therefore, one
[P], J 1et+,.- D}. for efficient backward.
for full backward
(6)
Here, P denotes the total number of expansion matrices.
4.3 Analysis of BREAD
Memory cost analysis. To simplify the analysis, we consider a D-layer neural network where each layer consists of one matrix with dimensions Rmx* BCD requires storing 6 weight (2Dm²), float32 block weight (4m²), gradient (4m²), and optimizer states (8m²). BREAD-LORA introduces additional cost of storing float32 LoRA parameters, gradient, and optimizer states (32 Dmar). BREAD- SGD introduces the cost of storing one block float gradient (2m²). Consider a setting similar to our Llama 3.1 1-B experiment where 4, D 32, and 4096, BREAD-LORA and BREAD-SGD introduces additional memory cost by approximately 1.2% and 2.5%, respectively.
Computational cost analysis. We now show that the additional backward cost is also cheap, since the intermediate partial derivatives used for computing the active block's ' gradient can be directly used for computing expansion matrices' gradients, as have identified in (2). Specifically, the gradient of the expansion matrix Cj can be expressed as
OH OH ŌZL+1 0zzt2 azz+1 aC₁
0EL+1 OzL
0zjt1 aC,
Computed in (2), vj 2
Clearly, when f, computing the (stochastic) gradient of Cj only requires additional computation of (1) which is cheap given the low dimensionality after low-rank factorization representation, 8C, i.., C2 U, We empirically measure the memory and epoch training time in Table 1.
Convergence Analysis. We establish the sample complexity result for BREAD under common assumptions utilized for BCD analysis; see Section D.I for the detailed assumptions, formal theorem statement and proof.
Theorem 4.2. (informal) Let a and 3 be the step size of active block and expansion matrices, respectively. Under assumptions stated in Section D.1, BREAD with deterministic gradient descent method with the following property
- -O(a)))
H(W H. 0(3) Σ IVc, H( (8)
jE(DIV
where Wiik denotes the model parameter at k-th step in block epoch t, block sub sub-problem i. a and B are the step size of the uctive block and expunsion matrices, respectively.
By telescoping equation 8 across = 1,.... K and = I..... D, and apply the step size rule in Section D.I, we show that BREAD finds e approximate stationary point with Oc=-2) iterations.

---

Llama 3.1-8B
Llama 3.1-70B
Method
Peak Memory
GPU hours
GPU
Peak Memory
GPU hours
GPU #
Adam
208.2
A100
1260 GB+
A100
Galore
40.5 GB
31.2
A100
LoRA
25,0 GB
23.6
A100
296.8 GB
213.1
A100
BAdam
21.8 GB
10.6
A100
276.2 GB
119.0
8,100
BREAD-LORA
23.2 GB
13.8
A100
288.6 GB
152.7
8 AA100
BREAD-SGD
23,5 GB
11.2
1 A100
292.1 GB
128.1
8 8A100
Table I: Memory footprint and one-epoch GPU hours for finetuning Llama 3. models on MathIn-
struct dataset. The BREAD's training time is based on the partial implementation introduced in (6).
Estimated memory cost.
5 Experiments
We evaluate the proposed BREAD in finetuning Llama 3.1-8B and Llama 3. 3.1-70B model on math finetuning and instruction tuning tasks, comparing its memory cost, time cost and downstream performance with full training algorithm and memory efficient baselines.
5.1
Setup
We begin by introducing the experimental setup,
Baselines. We compare BREAD with 1) BAdam [21], which applies vanilla BCD algorithm with Adam the inner solver; LoRA [13], which freezes the pre-trained weight and only updates the injected low-rank adapters; 3) Galore [43], which projects the gradient into low-rank spaces for reducing the memory cost; 4) Adam [14], which serves as the full parameter training baseline.
Instruction tuning. We perform supervise finetuning on the Llama 3-B model using Alpaca-GPPi dataset [29], which contains 52K questions and corresponding GPT-4 generated answers. The model is evaluated on MT-bench [44] for examining the model's instruction-following capability.
Math finetuning. We finetune the Llama 3.1-70B and Llama 3.1-8B models MathInstruct dataset [42] for epochs, which contains 260K questions that covers wide range of fields in mathe- matics. The finetuned models are evaluated on 4 in-domain mathematical benchmarks, i.c., GSM8K, MATH, NumGLUE, and AQuA [3, 9, 26, 19], and out-of-domain mathematical benchmarks, i.c., SimulEq [15]. The evaluations respectively. Due to the limited computational resource, we do not include the Adam's ' results for 70B model. Since there is no model parallel implementation released for Galore by the finish of the manuscript, we are unable to report its 70B results as well.
based 0-shot prompt and 4-shot chain-of-thoughe prompt,
Preference optimization. After the instruction tuning, we further align the tuned model using direct preference optimization (DPO) [32] on Ultrafeedback dataset [4]. We use the model finetuned by base model for preference optimization.
Adam in instruction tuning phase
All the experiments are run for epochs. The reported scores are the best one among checkpoints at epoch 1, 2, 3. The detailed parrem-prameters are presented in Section B.
5.2 Memory and Time Cost Measure
In Table 1, we empirically measure the peak memory cost and one epoch's time cost for BREAD- LoRA and other baseline approaches. The GPU hour calculated as the training time x GPU number. We set the LoRA rank to 64 to keep its number of trainable parameters (0.83 billion) close to a single block of BREAD (0.86 billion).
Evidently, both BAdam and BREAD can train 8B model within 24GB memory cost, which is feasible for a single RTX3090 GPU. All of LoRA, BAdam and BREAD can be used to finetune a 70B model with single 8 A A100-40GB node. Compared with BAdam, BREAD consumes slightly higher memory cost and training time under the efficient backward scheme.

---

Base model: Llama 3,1-8B
GSM8K
MATH
NumGLUE
SimulEq
AQuA
Avg.
Method
O-shot
4-shot
D-sbot
4-shot
0-shot
4-sbot
O-shot
4-shot
O-shot
4-sbot
O-shot
4-shot
Base model
17.8
52.5
8.6
23.2
25.7
40.6
12.2
28.8
19.3
43.7
16.7
37.8
Adam
62.3
64.9
17.4
22.9
56.4
56.8
28.6
33.5
44.9
52.8
41.9
46.2
Galore
46.7
57.2
16.2
22.9
42.8
45.0
28.7
32.3
47.8
48.4
36.4
41.2
LoRA-rank80
48.7
58.1
13.7
23.0
34.6
54.4
29.6
29.0
47.3
50.3
34.8
43.0
BAdam
53.9
58.3
17.2
23.6
53.7
57.2
32.5
32.8
50.4
49.6
41.5
44.3
BREAD-LORA
57.0
57.6
20.0
23.7
55.9
58.2
32.5
32.8
49.6
50.0
44.5
BREAD-LORA+
57.8
61.8
20.4
24.6
58.8
32.9
32.7
51.2
51.0
45.8
BREAD-SGD
56.9
60.6
19.6
21.4
58.2
31.5
31.8
48.0
50.8
42.0
44.6
Base model: Llama 3.1-70B
GSM8K
MATH
NumGLUE
SimulEg
AQuA
Avg.
Method
O-shot
4-sbot
0-sbot
4-shot
0-shot
4-shot
O-shot
4-shot
O-shot
4-sbot
O-shot
4-shot
Base mudel
58.8
79.4
24.9
41.4
43.7
55.8
26.3
38.1
52.0
64.2
41.1
51.2
LoRA-rank644
83.8
82.0
41.7
44,2
70.4
69.0
40.3
48.8
61.4
65.8
59,5
62.0
BAdam
81.4
82.9
40.3
43.8
68.1
69.7
50.0
52.7
65.3
70.1
61.0
63.8
BREAD-LORA
83.4
84.2
41.4
44.7
73.1
74,4
51.3
56.8
68.3
70,5
63.5
66.1
BREAD-LORA+
85.6
82.4
41.5
44.4
72.3
73.9
51.3
59.3
68.5
69.7
63.8
65.9
BREAD-SGD
82.8
83.9
40.8
43.7
68.9
69.7
49.7
61.3
62.2
69.7
60.9
65.7
Table Math benchmark results for models finetuned MathInstruct dataset.
Ablation
Boee BRGAD-SCE
BAday E118
Bidan
IASAD-1
SREAD K2G4
Tantnn lme
BRIAD K5L2
BRCAD-1
Trakking
Traamin
BRCAD-13
15/60
12000
17202
N.mber Berstione
Number Ronaioos
Number of Rlaratioo
Figure I: (a) Training loss BAdam and BREAD variants; (b) Effect of block switch frequency K for BREAD-LoRA; (c) Effect of the rank of expansion matrices for BREAD-LoRA.
The reported memory cost is higher than the theoretical value, especially for the 70B model's 's experiments which requires distributed training. This additional memory cost arises from storing activation values and computational buffers, e.g. the gradient buffer for performing reduce scatter operation. Furthermore, the training time may have slight fluctuations for different runs.
Remark.
5.3 Finetuning Performance
Math finetuning. The evaluation re- sults math benchmarks shown in Table 2. For the 8B model's fine- tuning, all the three BREAD vari- ants outperform BAdam both 0- shot and 4-shot average score. The BREAD-LORA+ attains the highest average score, which indicates that the benefits of landscape expansion- approaches will also enhance the BREAD's performance. As for the finetuning 70B model, the best average 0/4-shot score are obtained by BREAD-LORA and BREAD- LoRA+, respectively.
SFT
DPO
Method
GPT-4
GPT-4o
GPT-4
GPT-40
Base model
6.07
4.64
6.63
5.03
Adam
6.63
5.03
7.83
6.08
LoRA
6.52
4.85
7.48
5.95
Galore
6.33
4.78
6.99
5.83
BAdam
6.53
4.88
7.63
5.99
BREAD-LORA
6.77
5.08
7.68
6.12
BREAD-LORA+
6.65
4.88
7.62
6.15
BREAD-SGD
6.68
4.98
7.52
5.93
Table MT-bench scores of finetuning Llama 3.1-

---

Instruction tuning and DPO. We report the MT-bench score evaluated by both GPT-4 and GPT-4o models in Table 3. After SFT, the MT-bench score of all baseline approaches improves over the base model. BREADD-LORA achieves the highest scores in both evaluations, which are even higher than Adam, demonstrating the effectiveness of landscape expansion. Based on the model finetuned by Adam, we further align the model using direct preference optimization (DPO). Notably, BREAD- LoRA and BREAD-LORA+ achieves the highest evaluation score by GPT-4 and GPT-4o model, respectively.
5.4 Convergence Verification
We present 1-epoch training loss of selected BREAD variants in Figure (a). For reference, we also display the loss of BAdam. One can see that all the landscape expansionapprooches accelerates BAdam, which justifies the effectiveness of landscape expansion. The BREAD-SGD is faster than BREAD-LORA, which may attribute to the higher learning rate of the expansion matrices and the high-rank update. Notably, the BREAD-LORA+ attains the fastest convergence, which due to more efficient learning rate assignment of adaptors.
5.5 Ablation Study
In this section, we conduct ablation study to examine the effect of the expansion matrices' rank r and the block switch frequency K of BREAD-LORA.
Effect of K. We present the effect of sub-problem update steps K in Figure 1(b), which is by default 128 in our paper's 's experiments. Evidently, BREAD outperforms BAdam under all choices of K. Notably, increasing K consistently accelerates the convergence of BREAD for the examined range. where BREAD with K = 512 takes only half of the iterations to reach the final training loss of BREAD with K 32. One possible explanation for the phenomenon is that when using larger K, the Adam update will aggregate more historical information in its momentum and second moment term, which leads to better search direction and scaling magnitudes. We leave the scientific study of K as future direction.
Effect of r. The effect of expansion matrices' rank r shown Figure I(c), which is set in our paper. We note that by adding rank-1 expansion matrices, BREAD converges significantly faster than BAdam, which corroborates our observation in Theorem 4.1. BREAD exhibits faster convergence as the rank increases, since larger rank offers higher freedom of search directions.
5.6 Additional Experimental Results
We conduct additional experiments for comprehensive study of the algorithm's 's property. Our main findings are: 1) Convergence versus time. In terms of wall-clock time, BREAD-SGD under efficient backward yields the fastest convergence among the BREAD variants. 2) Effect of ordering strategies. Different block ordering yields similar convergence behavior; see Section E for the detailed results.
6 Conclusion and Discussions on Limitations
This paper investigates the application of a classic optimization method, known as BCD, to the finetuning of LLMs. We pinpoint primary shortcomings of the standard BCD approach when applied to deep neural networks: the unnecessary computational overhead during backpropagation, and the misguiding optimization landscape caused by frozen blocks. To overcome these challenges, we introduce a new method termed BREAD, which unfreezes the inactive blocks and updates them in lightweight manner. Our experimental results demonstrate that BREAD significantly enhances downstream task performance while maintaining the original BCD's memory efficiency.
The convergence theory for BREAD is derived based on SGD expansion, which eases the analysis compared to LoRA-basee expansion. Additionally, our analysis is based on deterministic gradient rather than stochastic setting. We leave the analysis for LoRA- A-based expansion and stochastic setting as future work.
Limitations.
Broader impacts. Our proposed method significantly accelerates BCD method for LLM training. This is a technical algorithmic contribution that does not yield explicit negative societal impacts. However, it carries risk of misuse.

---

Acknowledgments and Disclosure of Funding
We thank the Area Chair and the anonymous reviewers for their insightful comments and suggestions. which have significantly improved the quality of the manuscript.
Xiao Li is supported in part by the National Natural Science Foundation of China (NSFC) under grants 12201534, 12571330, and 12326608, in part by the 1+1+1 (SHH-CCHH(SZ))--H Joint Collaboration Fund under grant 2025 and in part by the Shenzhen Science and Technology Program under grant RCYXX0021008099003000
References
[1] A. Beck. First-Order Methods in Optimization. Society for Industrial and Applied Mathematics, 2017.
[2] K.-W. Chang and D. Roth. Selective block minimization for faster convergence of limited memory large-scale linear models. In Proceedings of the 17th ACM SIGKDD international conference Knowledge discovery and data mining, pages 699-707, 2011.
[3] K. Cobbe, V. Kosaraju, M. Bavarian, M. Chen, H. Jun, L. Kaiser, M. Plappert, J. Tworek, Hilton, R. Nakano, et Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168, 2021.
[4] G. Cui, L. Yuan, N. Ding, G. Yao, W. Zhu, Y. Ni, G. Xie, Z. Liu, and M. Sun. Ultrafeedback: Boosting language models with high-quality feedback. arXiv preprint 1rXiv:2310.0137, 2023.
[5] Dettmers, A. Pagnoni, Holtzman, and L. Zettlemoyer. QLoRA: Efficient finetuning of quantized LLMs. Advances in Neural Information Processing Systems, 36, 2023.
[6] L. Ding, Z. Chen, X. Wang, and W. Yin. Efficient algorithms for sum-of-minimum optimization. In Forty-first International Conference on Machine Learning.
[7] Hayou, N. Ghosh, and Yu. Lora+: Efficient low rank adaptation of large models. arXiv preprint arXiv:2402. 12354, 2024.
[8] K. He, X. Zhang, S. Ren, and J. Sun. Delving deep into rectifiers: Surpassing human-leve performance on imagenet classificatton.. Proceedings of the IEEE international conference on computer vision, pages 1026-1034, 2015.
[9] D. Hendrycks, C. Burns, S. Kadavath, A. Arora, S. Basart, E. Tang, D. Song, and J. Stein- hardt. Measuring mathematical problem solving with the math dataset. arXiv preprint arXiv:2103.03874, 2021.
[10] C. Hildreth. A quadratic programming procedure. Naval Research Logistics Quarterly, 4(1):79- 85, 1957.
[11] N. Houlsby, A. Giurgiu, Jastrzebski, B. Morrone, Q. De Laroussilhe, A. Gesmundo, M. At- tariyan, and S. Gelly. Parameter-efficient transfer learning for NLP. In International Conference on Machine Learning, pages 2799. PMLR, 2019.
[12] C.J. Hsieh, K.-W. Chang, C.-J. Lin, S. Keerthi, and Sundararajan. A dual coordinate descent method for large-scale linear svm. In Proceedings of the 25th international conference on Machine learning, pages 408 415, 2008
[13] E. J. Hu, Shen, Wallis, Z. Allen- -Zhu, Li, S. Wang. L. Wang, and Chen. LoRA: Low-rank adaptation of large language models. arXiv preprint arXiv:2106.0966 2021.
[14] D. P. Kingma. Adam: A method for stochastic optimization. arXiv preprint arXiv: 1412.6980, 2014.
[15] R. Koncel-Kedziorske Roy, A. Amini, N. Kushman, and H. Hajishirzi. Mawps: A math word problem repository. In Proceedings of the 2016 conference of the north american chupter of the association for computational linguisties: human language technologies, pages 1152-1157, 2016.
10

---

[16] B. Lester, R. Al-Rfou, and N. Constant. The power of scale for parameter-effiiiet prompt tuning. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 3045-3059, 2021.
[17] X. L. Li and P. Liang. Prefix- trefix-tuning: Optimizing continuous prompts for generation. In Proceedings of the 59th Anmual Meeting of the Association for Computational Linguistics and the 1 11th International Joint Conference Natural Language Processing, pages 2021.
[18] V. Lialin, S. Muckatira, N. Shivagunde, and A. Rumshisky, ReLoRA: low-rank updates. The Twelfth International Conference on Learning Representations, 2024.
High-rank training through
[19] W. Ling, D. Yogatama, C. Dyer, and P. Blunsom. Program induction by rationale generation: Learning to solve and explain algebraic word problems. arXiv preprint arXiv: (acivv:700s0 700.:04105, 2017.
[20] S.-Y. Liu, C.-Y. Wang. H. Yin, P. Molchanov, Y.-C. F. Wang, K.T.. Cheng, and M.-H. Chen. Dora: Weight-decomposed low-rank adaptation. arXiv preprint arXiv:2402.09355 2024.
[21] Q. Luo, H. Yu, and X. Li. Badam: A memory efficient full parameter training method for large language models. arXiv preprint arXiv:2404.00 028277 2024.
[22] K. Lv, Y. Yang, T. Liu, Q. Gao, Q. Guo, and X. Qiu. Full parameter fine-tuning for large language models with limited resources. arXiv preprint arXiv:2306.09782 2023.
[23] S. Malladi, T. Gao, E. Nichani, A. Damian, D. Lee, D. Chen, and Arora. Fine-tuning language models with just forward passes. Advances in Neural Information Processing Systems, 36, 2023.
[24] Meng, Z. Wang, and M. Zhang. Pissa: Principal singular values and singular vectors adaptation of large language models. arXiv preprint arXiv:2404.02944 2024.
[25] P. Micikevicius, S. Narang, Alben, G. Diamos, E. Elsen, D. Garcia, B. Ginsburg, M. Houston, O. Kuchaiev, G. Venkatesh, et al. Mixed precision training. arXiv preprint 170.0:1710 2017.
[26] S. Mishra, A. Mitra, N. Varshney, B. Sachdeva, Clark, C. Baral, and A. Kalyan, Numglue: A suite of fundamental yet challenging mathematical reasoning tasks. arXiv preprint arXiv:2204.00 055600 2022.
[27] Y. Nesterov. Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM Journal Optimization, 22(2):341-36) 2012.
[28] R. Pan, X. Liu, Diao, Pi, J. Zhang, C. Han, and Zhang, Lisa: layerwise importance sam- pling for memory-efficiiee large language model fine-tuning, Advances in Neural Information Processing Systems, 97:57018-57045 2024.
[29] B. Peng, C. Li, He, M. Galley, and J. Gao. Instruction tuning with gpt-4. arXiv preprint arXiv:230..03277, 2023.
[30] L. Peng and R. Vidal. Block coordinate descent smooth manifolds: Convergence theory and twenty-one examples. Technical report, arXiv:2305. 14744v3 [math.OC], 2023.
[31] L. Peng and W. Yin. Block acceleration without momentum: On optimal stepsizes of block gradient descent for least-squares. arXiv preprint arXiv:2405.16020, 2024.
[32] R. Rafailov, A. Sharma, E. Mitchell, C. D. Manning, S. Ermon, and C. Finn. Direct preference optimization: Your language model is secretly a reward model. Advances in Neural Information Processing Systems, 36, 2024.
[33] P. Richtárik and M. Takáë. Iteration complexity of randomized block-coordinate descent methods for minimizing composite function. Mathematical Programming, 144(1):1-38, 2014.
[34] A. H. Sayed. Inference and Learning from Data: Foundations, volume Cambridge University Press, 2022.

---

[35] H.-J. M. Shi, S. Tu, Y. Xu, and W. Yin. A primer on coordinate descent algorithms. Technical [math.OC], 2016.
report,
[36] E. Treister and J. S. Turek. A block-coordinate descent approach for large-scale sparse inverse covariance estimation. Advances in neural information processing systems, 27, 2014.
[37] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and
I. Polosukhin, Attention is all you need. Advances in Neural Information Processing Systems, 2017.
[38] S. J. Wright. Coordinate descent algorithms. Mathematical Programming, 151(1):3-34, 2015.
[39] S. Wright and Recht. Optimization for data analysis. Cambridge University Press, 2022.
[40] W. Xia, C. Qin, and E. Hazan. Chain LoRA: Efficient fine-tuning of language models via residual learning, arXiv preprint 14Xii:240010415.. 2024.
[41] H.-F. Yu, C.-J. Hsich, K.-W. Chang, and C.-J. Lin. Large linear classification when data cannot fit in memory. ACM Transactions on Knowledge Discovery from Data (TKDD), 5(4):1-23, 2012.
[42] X. Yue, X. Qu, G. Zhang, Y. Fu, W. Huang, H. Sun, Y. Su, and W. Chen. Mammoth: Building math generalist models through hybrid instruction tuning, arXiv preprint arXiv:2309.05653, 2023.
[43] Zhao, Z. Zhang, B. Chen, Z. Wang, A. Anandkumar. and Y. Tian. Galore: Memory-efficient Ilm training by gradient low-rank projection. arXiv preprint vrXiv:2403.03500 2024.
[44] L. Zheng, W.-L. Chiang, Y. Sheng, S. Zhuang, Z. Wu, Y. Zhuang. Z. Lin, Z. Li, D. Li, E. Xing, al. Judging llm-as-a-judge with mt-bench and chatbot arena. Advances in Neurul Information Processing Systems, 36:46595-4660 2023.
[45] Y. Zheng, R. Zhang, J. Zhang, Y. Ye, Z. Luo, and Y. Ma. LlamaFactory: Unified efficient fine-tuning of 100+ language models. arXiv preprint arXiv:2403. 13372, 2024.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The major contributions and scope are properly reflected in abstract and the
summarization contributions Section
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We have summarized the main limitations of this work in Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't It acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
13

---

Justification: In Theorem 3.1, Theorem 4.1, I, and Section D, we list all the assumptions used. In Section D, we provide all the proofs of the theoretical results of this paper.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
We include detailed experiment setup in Section 5.1 and Section B.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
14

---

Answer:
[Yes]
Justification: Our submission includes the data and code for reproducing the main experi- ments of the paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurlPS code and data submission guidelines (https:
ggtgg/uies////// Soleee//ooeSuumissee wwttamiisssioooiiioiiooioiiioiii for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The detailed setting of experiments such as dataset, hyperparameters are included in Section 5.1 and Section B.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: For the MT-bench and math-tuning results in Section 5, we include the results for different base models, different benchmarks, and different judge models.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by emror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
15

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We clearly report the computer resources used in the experiments in Section 5; see, e.g., Table 1.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https://neuripps wwwrris.ee. wttppsscccppppcccpeppcpppppppppe wew.ichhcceeeeeeeeeeenenne.
Answer:
[Yes]
Justification:
The paper follows the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We have summarized the broader impacts of our method in Section 6.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
16

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not release any data or model in this work.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: The used datasets, codes, and models properly cited based on their licenses.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
17

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: Our submission includes the new asset (implementation code). The asset is well documented.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve any crowdsourcing experiments or any research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve any crowdsourcing experiments or any research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
18

---

For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: LLM is only used for improving English writing.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non non-standard components.
Please refer to our LLM policy (https : /ttpe/epps../oooeeeeeeeeeeeeeeee wwt.cc////oooeeeeeeeeeeeccecee c for what should or should not be described.
19

---

Contents
1
Introduction
2 Preliminaries on Block Coordinate Descent for LLM Training
3
Limitations BCD for Neural Networks
4
BREAD Framework and Its Analysis
4.1
Motivations: Low-rank Expansion Addresses Limitations
4.2
The BREAD Framework
4.3
Analysis of BREAD
5
Experiments
5.1
Sctup
5.2
Memory and Time Cost Measure
5.3
Finetuning Performance..
5.4
Convergence Verification
5.5
Ablation Study
5.6
Additional Experimental Results
Conclusion and Discussions on Limitations
A
More Related Works
21
Detailed Experimental Setup
21
C BREAD-SGD Algorithm
22
Convergence Result and Additional Proofs
23
D.I Convergence of BREAD
23
D.2 Proof of Propositions
25
D.3 Analysis of Multi-Layer Model and Cross Entropy Loss
25
D.3.1
Suboptimality Analysis for L-layer Model
25
D.3.2
Suboptimality analysis for cross entropy loss
26
D.3.3
Small Experiment on Multi-layer Neural Network Training
26
Additional Experiments
27
20

---

A More Related Works
Block coordinate descent method. Block coordinate descent (BCD) is a classic optimization paradigm that dates back at least to [10]. It has gained popularity in recent years, due to its scalability and efficiency for many machine learning applications [27, 33, 30, 6, 31 The community seems to converge to a consensus that, in order for BCD to be efficient, the problem it optimizes needs to possess the so-called coordinate- friendll structure [35]. Nevertheless, deep networks are of a compositional nature and not morrdinate-friendde have never mentioned training deep networks as an application of BCD [38, 35, 1, 39, 34). Recently, BAdam [21] was proposed to finetune LLMs based on the BCD framework, where each block sub- problem is approximately solved using several Adam steps. Although BAdam achieved preliminary success, it is based the vanilla BCD framework and shares the fundamental limitations revealed in this work. In light of these, we believe identifying the limitations of BCD for LLM fintuning and fixing them entail certain insights, and this is what makes our contributions non-trivial and valuable.
which is perhaps why recent surveys or books
Memory efficient finetuning. To address memory issue, multiple variants have been proposed. Parameter efficient finetuning (PEFT) methods achieve memory efficiency by only training small portion of (possibly extra) parameters while freezing most of the others, such as Adapter tuning [11], prompt tuning, and prefix tuning [16, 17]. Low-rank adaptation (LoRA) is perhaps the most popular technique that approximates model updates using two smaller, trainable low-rank matrices [13]. LoRA' variants have been proposed to address its rank constraints and further reducing the memory cost [18, 40, 5]. The work [28] proposes to use a layer-wise importance sampling for achieving memory efficiency. Galore [43] projects the gradient into low-rank space that it does not need to store the full gradient and optimizer states in the memory. LOMO updates parameters in real time during the backpropagation process [22], that one can perform SGD) without store stochastic gradients. MeZO offers an alternative by approximating SGD using only forward passes [23], drawing from zeroth-order optimization that estimates stochastic gradients through the difference in function values. While this paper addresses the same application as these methods, they remain orthogonal to the proposed approaches. They can function lightweight updates in the frozen layers for landscape expansion.
B Detailed Experimental Setup
We introduce the detailed hyperparameters and experimental setup in this section.
Global setup. For all the experiments in math finetuning, instruction tuning and direct preference optimization, we fix the effective batch size to be 16 and train the model for 3 epochs. We use DeepSpeed ZeRO-3 to implement all the experiments that require distributed training (shown in Table 1). For all the experiments, we apply gradient checkpointing to reduce the memory cost for storing activation values. We use mixed-preciste datatype except for Galore, where we follow the setup in its paper, using pure BFloat 16 and 8-bit Adam optimizer for reducing the memory cost. We apply cosine learning rate schedule for all the experiments. For instruction tuning task, we set all method's initial learning rate to 1e-6. For math finetuning tasks, we set Adam's 's initial learning rate to 1e-6 and other methods' initial learning rate to le-5. The learning rate ratio for LoRA+ method is set to 16. The implementation of BAdam, Galore, LoRA are based on LLama-Factory [45].
training with BFloat 16 as the low-precision
Math finetuning. We randomly select 100,000 samples from the MathInstruct dataset and finetune all the models using the same samples. The benchmarks scores are evaluated using the MAmmoTH's repository* (without using thogram-ootthuughh).. The rank of correction matrices U and V for BREAD-LORA and BREAD-LORA+ are set to 8. We initialize U as zero, and initialize V from the
Kaiming uniform distribution [8]. i.c. (-u( // (x())) The rank of LoRA is set to 80 and 64 for finetuning Llama 3. --B and Llama 3. 10B. respectively, so that the trainable parameter number of LoRA is close to that of one BAdam/BREAN
active block. We follow the conventional setup to set the LoRA scaling factor a = 4x LoRA rank. We set Galore's 's rank to be 256, with the period of re-calculating the projection matrix being 256. We set K 100 for BAdam and BREAD.
21

---

Instruction tuning and direct preference optimization. The evaluation of MT-bench score is based on FastChat [44] using both GPT-4 and GPT-4o. We use the API "gpt-4-32k 100-3kkk0613"" and fgpt-4o_2024-11-- 2024-11-20" for GPT-4 and GPT-4o, respectively. The maximum sequence is set to 1024 and 2048 for the experiments on Alpaca-GPT4 and UtraFeedhack, respectively. For BAdam and BREAD, we solve each block sub-problem for 128 steps, i.e. K = 128.
C BREAD-SGD Algorithm
We introduce a variant of the BREAD algorithm, termed BREAD-SOR DGD, which employs Adam for updating the active block and on-the-fly SGD for the inactive block. The detailed procedure is outlined in Algorithm Analogous to BREAD, BREAD-SGD partitions the model into D distinct blocks and combines the gradient computation and update steps into singular operation. Specifically, gradients are calculated on a layer-by-layer basis; active layers are updated using Adam, while inactive layers undergo single SGD step. Once an inactive layer is updated, its gradient discarded to enhance memory efficiency.
Algorithm 2 BREAD (SGD variant)
1: Input: Model parameters {W?) number of blocks D, iterations per block K, step size of inactive blocks B
2: Initialization: Block-epoch index + O, and the corresponding optimizer states 83 <- 0,
Vj E [P]
3: while stopping criterion not met do
4: Generate block partition 1......,,
5:
for one block-epoch = to do Select correction matrices' indices J C [P] in (6)
6:
7:
n; + // Re-initialize Adam optimizer states m. + W
8:
W
9:
for landscape corrected block updates
to K do
10:
Sample a data batch random reshuffled order DB = 1,)) ~
11:
within backward pass the data batch Dg do
12:
// Update the active block aH
13:
9
aWe,
14:
Wi.k f.k my F;
+ AdamStep( CosteeppWikke With mi I m
15:
16:
// Correct inactive blocks for E J do
17:
18:
gt aw
Wik + W 3g. 1-k-1
19:
20:
g
1 None
end for
22:
end within
23:
end for
24:
W++1 f- Wi.k. g f- None J.K
25:
end for
26:
1- ++1
27:
end while
28: Return parameters (W/)
22

---

D Convergence Result and Additional Proofs
D.1 Convergence of BREAD
In this section, we establish a preliminary convergence result for the proposed algorithms. For conciseness, we analyze the BREAD-SGD described in Algorithm 2. The analysis of BREAD and BREAD-partial follows similar approach.
Our analysis decouples the error terms induced by the update of active block and inactive blocks, respectively. The descent property of the algorithm is established by analyzing consecutive updates across block epoch. We follow the deterministic setting in [21], leaving the analysis of stochastic cases for the future work. We now introduce the assumptions used in analysis.
Assumption D.1 (Smoothness). The function H (W) L-smooth on W and L-mooothh on block W; for blocks i 1,... DD:
V (W) VwH(W) - L W - WIl.
(9)
0H
OH aw,
$ L W 1.
(10)
OW,
w!
We denote L mXX L; the maximum Lipschitz constant.
Assumption D.2 (Bounded derivatives). The block derivatives Vw, H. (W) are uniformly bounded by a constant along the update trajectory of BREAD:
V| (W) S G,,,=,,...
The Theorem D.1 is standard for analyzing block coordinate descent-type methods [38]. Note that the block-wise smoothness (10) can be naturally induced by the function smoothness (9). The Theorem D.2 is provably satisfied for Adam algorithm under certain generalized smoothness conditions. The Theorem D.2 directly induces the following corollary, which will be used in our analysis.
Corollary D.3 ([21), Corollary D.3). Let A diag (1/ ((o**+>)) denote diagonal
matrix formed by coordinate-wise adaptive step sizes vector. Under Theorem D.2 and with 0 < < we have
1 1
1
A
t. - 1 X
I.
(11)
2G
Lemma D.4 (Re-statement of [21], Lemma D.7). Under the Theorem D.I and Theorem D.2, and given the step size condition a V 2LK2, we have the following bound for the bias between Adam
update and GD update ||e[|| Σ g= |1 (m
k.
|eg112 < 2L,aK X2
12--
Theorem D.5 (Descent of BREAD). Under Theorem D.I and Theorem 1)22, the Algorithm 2 with deterministic gradient achieves the following descent after each block-epoch of updates:
H(W+&+1) -((--))))))WW)))) < (O(a))VV.H("))) 122 H
(12)
X G under the step size choice B 2a 8 < min 2LK 24LKO ALK
6G2
16LK
By telescoping (12) from 1. = 1.... and divide each side by T, we obtain the sample complexity of (W OKK/T). The proof of Theorem D.5 is based on the following Lemma, which establishes the descent property one block sub- probleo...m.
Lemma D.6 (Descent of one block-epoch). Under Theorem D.I and Theorem D.2, the Algorithm update yields the following approximate descent property:
aK
H(W?) H(WL))s
VH
4G
23

---

Proof. The proof of Theorem D.6 is based on the analysis framework of [21]. Additionally, we need to analyze the descent property of the update in correction matrices, At the beginning of block epoch t, block sub-problem i, let W 3,4 be the parameter of block j. W be the full parameter. Let / be the step size for the correction matrices. Based on the smoothness property in Theorem D.1, we have
HW ( H(W
V (W
W W W
+
Σ
L
Whtth
2 JE[D]\
SEIDIVS
(V.H(W W w +
L
W
w..kk1 12
2
1,t
E (-3+ + 2 " >12 + V. W w )
+ [
2
SEIDI
L S E (-B+
3 | 112 + (-a+ 20²) V.H 11 + (V.
SE(DIVi
+ T laG + L L,a²,?)) ) 11
(13)
2
where the equalities is due to the GD update rule, and the last inequality uses Young's inequality and the Adam's update rule. lle || == :े Ex T-
H,A (m,* f.k - (1 - 31) 4.A I|l is the bias of active
block's 's update, where we use 9;" t
to represent V (.H(W for brevity. We have
k
lle
k.k
1
(m² t. - (1 - 99) (.") "Il
k: n=1
1
BT
k
1
96 -9;²²
An 1
k: n=1
k
1
n
B9 87-2 Li Wl w.,'ll
(14)
(1
BT)
For the ease of expression, let 0.th = W Define (((k)2) = 110% -0%-1 11. We have
(1(k) = all Σ
H 1,
m
j=1
:
S aa)
(1)
8 91
X(1 3))
1=1
1=1
1
((1-8) Σ
(g. 11
9i / + (1 96
X(1 3)
F=1
(1 (1) Σ
L L. 11011 - -0 + (1- - 3
X(1 31)
1=1
1
(1 - B1)
Σ
LL =) Σ Bi + (1 3h 1.2
X(1 - 34)
j=1
1=1
az2
X (L, 2) + (1)
(15)
Combine (15), (14) and apply the step size rule, we have
2L,a
lee ||
<
1
I|.
(16)
X²
24

---

Plug (16) back into (13), we have
H(W!htt) (W!
(17)
Σ (-B+ It B (-a a a > (W,
jEIDIVi
8L
V (
(18)
Based on Theorem D.4 and use the fact that V,H < (VH(W-)))l.. we can derive the following bound:
H(W H(
ak V, SG
Σ
5k 8G
| (,W,W"
1
(19)
JEIDN
Proof of Theorem D.5. (19) establishes exact the same descent property as in [21] Corollary D.8. By following the same argument as in [21] (10)-(1),, one can establish the convergence result in Theorem D.5.
D.2 Proof of Propositions
Proof of Theorem 3. We first show that H = 0. One can construct 23 = [1,0, ,0]
0]T and
W3 (y. 0. ... Oj. Note that such choice of 23 is always achievable by choosing a specific W2. Hence, 0 function value can be attained by the constructed feasible point. This yields H after realizing that the objective function must be nonnegative.
In BCD, Wi and W3 fixed. We further assume that the fixed W3 has full column rank. We split our discussion into II: range(W3). In this case, z3 (W, W3) W, y is the unique point that can achieve function value. However, since z3 has at least one negative entry and ø3 2 0 (due to the ReLU activation), we have ||2g- 2312 0. Therefore, we have y U [ 23)1l3
Case y & range W3). We trivially have H > 0 H Case
H
where the last inequality follows from the full column rankness of W3.
Proof of Theorem 4.1. We construct 23 e1 [1,0,-.. ... .OT Let
W (1)
...
where (1)) is the first column of W3. Then, have [[(,, C) y1l |Ce: W3e1 0.
(y
D.3 Analysis of Multi-Layer Model and Cross Entropy Loss
In this section, we generalize the Theorem 3. to L-layer neural network model and cross entropy loss. The corresponding numerical verification are presented in Section E. Let consider L-layer model:
ø1 ((Wr)
2, (W(2-11), 2. L-1
WLEL-11
where (ar) = max(0, is the ReLU activation function and z; E Rdd,
D.3.1 Suboptimality Analysis for I-llayer Model
Let us first consider the general regression loss | 2112. where is the target aim fit.
Effect of freezing W.. When W,, is full column rank, the optimal ø we seek to is the least square solution zi_1 = (W 1. Wr)- "T When 2 contains negative entries, it cannot be fit due to the non-negatyv of the ReLU function, which induces the suboptimality:
min
| -yl2 >
min W1
11 - 11..
W W W2-1
W
25

---

Effect of freezing intermediate layers. Each intermediate layer performs the transformation 2; oWW := M, When W; is trainable, we have range(MM,) R4 when 2;-1 * However, when W; is frozen, range(MM.) is limited to the projected "restricted" column space of W, where "restricted" means that the column combination should be positive, due the positivity of 24-1-
D.3.2 Suboptimality analysis for cross entropy loss
Without loss of generality, let assume that the ground truth label is the first class. The cross entropy loss is given by log (exp /1/ /2 m Dim exp )) where is the number of classes, Consider the case where the weight of the last layer Wt has row with the same weight as the first row, i.e. 3 such that w w able to drive the loss down to log 1.
we have Ùj w 2L-1 W (1) Z1-1 ÿ1 In this case, we will never be
2.
exp ő1
exp V1
1
log
log
log
== exp 9:)
i + exp
While it is not common for WL to have exactly two rows, can expect large error when there are rows that form small angle, i.e.
(1) w
W
2 1.
D.3.3 Small Experiment on Multi-layer Neural Network Training
Below, we conduct a small experiments on training multi-layer neural network to demonstrate the aforementioned suboptimality issue. We treat each layer frequency K = 100. As shown in Figure 2(a), BREAD-LoRA with rank-1 landscape correction converges dramatically faster than BAdam. In particular, BAdam only begins converge rapidly after the 300 steps, when the final layer has been trained. This phenomenon supports our discussion that poorly trained final layer may hinder convergence. In Figure 2(b), show that BREAD boosts the convergence for 8-layer neural network as well, which corroborates our L-layer analysis in Section D.
block, and set the block switch
Training
Training Loss
3.4
1.2
3.2
1.0
3.0
BAGam
51240 (rank))
3
madd update ony.
0.6
3.4
6.4
SAd (mnid)
32
updats only
3.0
teraton
Bention
(a) Training loss of 3-layer model.
(b) Training loss of 8-layer model.
Figure 2: BREAD with rank-1 I landscape expansion converges dramatically faster than BCD.
26

---

E
Additional Experiments
Convergence in time. We finetune the Llama 3.I-8B model on MathInstruct dataset for 3 epochs. and report training loss convergence versus time/iteration in Figure 3. Notably, BREAD-SGD-pane achieves the fastest convergence in terms of time, and BREAD-SGD and BREAD -apttaallll surpasses BAdam at certain points. All the BREAD variants achieve lower training loss than BAdam after epochs.
SAcam
0.65
Convergence versus luration
Micam
0.00
5READ LARA
BREAD (AA.D------------ cardal
0.55
partia
BRIAC SCB parttal
0.50
6.45
0.40
6.35
0.50
30
45
50
0.30
10300
20300
50333
40003
50002
Time (hours)
Number burattoo
(a) Training loss in terms of time.
(b) Training loss in terms of itcration.
Figure 3: Convergence analysis of training loss in terms of time and iteration.
Effect of ordering strategies. We test the ordering strategies of ascending (from input layer to output layer), descending (from output layer to input layer), and random (select the layer random reshuffling manner). As shown in Figure 4, different ordering strategy does not result in evident difference of convergence speed.
BREAD acreedin
BREAD danccii
BIEAD namdom
0.45
3000
5000
2000
12000
35000
Mamber
benatore
Figure 4: Ablation study on block ordering strategies
27


Reviews:
[{"review_id": "mTE04DeWsD", "reviewer": "Reviewer_AjsN", "summary": "This paper proposes a novel approach that integrates block coordinate optimization with LoRA-based fine-tuning for large language models. The combination is well-motivated and tackles an important issue: in neural networks, the computational cost of computing gradients for different parameter blocks is not uniform due to the nature of backpropagation, which contrasts with the typical context in which classical coordinate descent methods are applied. The authors highlight this distinction and develop their method specifically to mitigate the resulting inefficiencies in large-scale model training. Experimental results on several benchmarks demonstrate that the proposed methods outperform existing memory-efficient fine-tuning techniques, providing empirical support for the theoretical insights presented in the paper.", "questions": "In Figure 1(b), the experiments are limited to K=512. Could the authors clarify why this upper bound was chosen? A broader exploration of K might help identify an optimal value and provide practical guidelines for selecting K in different settings.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "__Strengths__\n\n- **Clear Motivation:** Effectively highlights limitations of classical block coordinate descent for neural network training.\n- **Lucid Explanation:** The BREAD framework is explained clearly, with well-presented algorithmic details and connections to existing techniques.\n- **Extensive Evaluation:** Presents comprehensive experiments on multiple benchmarks and model sizes, with ablation studies providing insights into design choices.\n- **Memory Efficiency:** Demonstrates memory efficiency, a critical consideration for large language model training, with detailed memory cost analysis.\n- **Practical Applicability:** Relatively simple to implement and integrate with existing training pipelines.\n\n__Weaknesses__\n\n**Proposition 3.1 (Theory):**\nThe statement of Proposition 3.1 is unclear regarding the role of $W_{\\text{out}}$ on the left-hand side, since minimization is not performed over this variable. Is the strict inequality supposed to hold for all possible $W_{\\text{out}}$? This does not seem to be the case, as the inequality would not hold for $W_{\\text{out}}^**$ that achieves the minimum in the right-hand side. Therefore, it is not clear for which values of $W_{\\text{out}}$ Proposition 3.1 is valid.  \nI would also appreciate a more detailed discussion following Proposition 3.1. For example, if the result only holds for $W_{\\text{out}}$, what about other layers? \nAdditionally, some variables $W$ in this proposition (and possibly elsewhere in the text) are bolded, while others are not, which may cause confusion.  \n\n**Proposition 4.1 (Theory):**\nMy comments regarding Proposition 4.1 are similar to those for Proposition 3.1. However, while I can at least imagine a proof for Proposition 3.1, Proposition 4.1 appears to be incorrect as stated. For example, if we set $L = 0$ (i.e., there is only $W_{\\text{out}}$) and $W_{\\text{out}} = 0$ on the left-hand side, Proposition 4.1 claims that minimization over a rank-1 matrix is equivalent to minimization over the full matrix $W_{\\text{out}}$, which is clearly not the case. It is essential to provide a precise explanation of the conditions under which Proposition 4.1 holds, or to clarify its statement. \nFurthermore, the proof in Appendix D.2 is very brief (only three lines) and does not provide enough detail to clarify the underlying reasoning, making it difficult to assess the validity of the propositions.\n\n**Theorem 4.2 (Theory):**\nFirst, Theorem 4.2 appears to be more of an intermediate result (a descent lemma) rather than a final convergence rate. Typically, at this stage, one would sum over $k$ so that all $H(\\cdot)$ terms except the first and last cancel out, leading to a convergence rate of the form $O(1/\\sqrt{K})$. However, in the BREAD algorithm, the relevant convergence should be with respect to $t$, not $K$, since the number of steps per block is not very large (in your experiments, as I understand, it was at most 512). As a result, the theorem does not actually provide a meaningful convergence guarantee for the overall algorithm.  \nI also do not fully understand why classical convergence results for Adam cannot be applied here, since $t$ is not changing. Similarly, it is unclear why standard results for coordinate descent cannot be used.  \nFinally, Theorem 4.2 is stated for deterministic (full-batch) gradients, which is not realistic for LLM training tasks, where stochastic gradients are always used.\n\n**Typos and Minor Issues**\n- \"landscape expansionutilizes\" (should be \"landscape expansion utilizes\")\n- \"landscape expansioncomponent\" (should be \"landscape expansion component\")\n- \"landscape expansiontechnique\" (should be \"landscape expansion in\")\n- \"landscape expansionapproaches\" (should be \"landscape expansion approaches\")\n- \"simpliest implementaiton\" (should be \"simplest implementation\")\n- \"requries\" (should be \"requires\")\n- \"LoRA’ variants\" (should be \"LoRA variants\" or \"LoRA's variants\")\n- The term \"block-epoch\" is sometimes written as \"block epoch\"; it is preferable to use a consistent form throughout the manuscript.\n\nThis work primarily focuses on the proposed algorithmic framework and its empirical evaluation, while some theoretical aspects and broader experimental validation remain open for future research. In particular, the convergence analysis is limited in scope, and the experiments are conducted on selected tasks and models.\n\nI borderline reject the paper for now, but I look forward to communicating with the authors.", "was_revised": true, "final_justification": "Vote for acceptance", "rebuttal": "We thank the reviewer for the valuable comments. Overall, let us mention that our primary focus lies in proposing the BREAD algorithmic framework (and its practical implementation) that accelerates BCD for LLM finetuning, rather than focusing on theoretical analysis. The derived propositions are mainly intended to motivate the algorithm design, and the convergence result serves a partial explanatory purpose to show that the algorithm is grounded by classic convergence theory. Below, we address your concerns regarding our theoretical results.\n\n**Confusion in Proposition 3.1.** The objective of Proposition 3.1 is to show that fixing $W_{\\text{out}}$ may potentially exclude the optima, which can happen in the BCD update scheme. As stated in Proposition 3.1, we require $W_{\\text{out}}$ in the left hand side to be not full column rank for the strict inequality to hold. Namely, if one fixes $W_{\\text{out}}$ at a degenerate point, optimizing other variables only (such as the scheme of BCD) will attain a strictly higher function value compared to the optimal value (i.e., the left hand side). Then, based on this result we conjecture that this issue may potentially slow down the convergence of BCD's subproblem, as it may not include the optima at all. This observation motivates the design of the BREAD algorithmic framework.\n\nSince the feature learning depends on the model parameterization, characterizing the sub-optimality of BCD's subproblem for other layers (other than the last layer) for an *arbitrary* model is almost impossible. Instead, let us use the following much simplified regression model to demonstrate the effect of fixing one of the other layers. Since the sub-optimality holds for such a simple model, we would then extrapolate that the same issue will likely remain for the training of the much more complicated language models. \n\nConsider the following regression problem\n$$\\min_{W} ||H(W, X) - Y||\\_2^2$$\nwhere the input is $X \\in \\mathbb{R}^{B\\times m}$ and the ground truth label $Y=PX \\in \\mathbb{R}^{B\\times n}$, with rank($P$)=$r$. Suppose H(W, X) is a multi-layer model:\n$$H(W, X):= f_{W_L} \\circ \\cdots f_{W_2} \\circ f_{W_1}(X)$$\n$f_{W_\\ell}(Z):=\\sigma(W_\\ell Z)$,\nwhere $\\sigma(\\cdot)$ is the ReLU activation function. Suppose one fix any $W_\\ell$ with rank($W_\\ell$)<r, then by the rank inequality there always exists $(X, Y$) such that\n$$\\min_{\\{W \\backslash W_\\ell\\}} ||H(W, X) - Y||\\_2^2 > \\min_{W} ||H(W, X) - Y||\\_2^2$$\n\nIn addition, we will change all the $W$ in the paper to boldface to keep consistency. \n\n**Proposition 4.1’s validity.** When L=0, the problem essentially becomes finding $Cx=e_y$. One rank-1 solution is let $C_{:, i}=0 \\ \\forall i \\neq y$, $C_{:, y}=\\frac{x}{||x||_2^2}$. Therefore, Proposition 4.1 correctly holds under the scenario mentioned in the review.\n\n**Clarification on Theorem 4.2.** The sample complexity is established by telescoping the inequality over block epoch $t$ rather than the block subproblem step $K$. We now sketch the derivation of the sample complexity based on the inequality of Theorem 4.2. Let us recall the following definitions: \n\n- $W^t$: Weight at the start of block epoch $t$.\n- $W_i^t$: Weight  at the start of block epoch $t$, block sub-problem $i$.\n- $W_{i}^{t, k}$: Weight at block epoch $t$, block sub-problem $i$, update step $k$.\n\nThe Theorem 4.2 gives\n$$H(W_{i}^{t, k+1})-H(W_{i}^{t, k}) \\leq \\mathcal{O}(\\alpha) ||\\nabla_i H(W_{i}^{t,k})||\\_2^2 - \\mathcal{O}(\\beta) \\sum_j ||\\nabla_{C_j} H(W_i^{t,k})||\\_2^2$$\nSum over $k=1, \\cdots, K$ steps and apply the assumption of smoothness and bounded gradient gives\n$$H(W_{i+1}^t) - H(W_{i}^{t}) \\leq -K \\mathcal{O}(\\alpha) ||\\nabla_i H(W_i^t)||\\_2^2 - K \\mathcal{O}(\\beta) \\sum_j ||\\nabla_{C_j} H(W_i^t)||\\_2^2 + \\mathcal{O}(K^2(\\alpha^3+\\alpha^2\\beta))$$\nSum over blocks $i=1, \\cdots, D$ gives\n$$H(W^{t+1}) - H(W^t)$$ \n$$\\leq-K\\mathcal{O}(\\alpha) \\sum_{i=1}^{D} ||\\nabla_i H(W_i^t)||\\_2^2 - DK\\mathcal{O}(\\beta) \\sum_j ||\\nabla_{C_j} H(W_i^t)||\\_2^2 + \\mathcal{O}(DK^2(\\alpha^3+\\alpha^2\\beta))$$\n$$\\leq -K\\mathcal{O}(\\alpha)||\\nabla_W H(W^t)||\\_2^2 - DK\\mathcal{O}(\\beta) ||\\nabla_C H(W^t)||\\_2^2 + \\mathcal{O}(D^2K^2(\\alpha^3+\\alpha^2\\beta)),$$\nwhere the last inequality follows from the assumption of smoothness and bounded gradient.\n\nLet $\\alpha=\\mathcal{O}(1/\\sqrt{T}), \\beta=\\mathcal{O}(1/\\sqrt{T})$ and telescope the inequality over $t=1, \\cdots, T$, we have\n$$\\frac{1}{T} \\sum_{t=1}^{T}||\\nabla_W H(W^t)||_2^2 = \\mathcal{O}(\\frac{1}{\\sqrt{T}K} + \\frac{K^2}{T^{1.5}}).$$\n\nWe will derive the detailed convergence rate in the next version of our manuscript.\n\n**Why classical Adam's convergence result cannot be applied, since $t$ is not changing.** We clarify that $t$ is the block epoch and changes over training. While one can follow the Adam's analysis to analyze the descent of one block subproblem, the gradient norm of the converged point will contain constant error of $\\mathcal{O}(1/\\sqrt{K})$, as $K$ is a prefixed constant value. To establish the convergence of the algorithm, one needs to jointly analyze the descent of a full block epoch rather than a single block sub-problem.\n\n**Why standard coordinate descent result cannot be used?** The update of the active block uses Adam update rule rather than gradient descent update. Therefore, the bias between Adam update and the true block gradient has to be bounded using a different analysis; see equation 12-14 in Appendix D for the error analysis of Adam update.\n\n**The convergence result is for deterministic case.** Since our main focus for this work is to design a practical algorithmic framework rather than establishing new theoretical convergence result, we consider the convergence under the deterministic setting for compact presentation. We remark that it is possible to combine the current analysis with [1, 2] to derive the convergence under stochastic gradient, which we leave as a future work.\n\n**Typos.** We thank the reviewer for the careful reading of our manuscript, and will revise all the typos in the next version of our manuscript.\n\n**Choice of K beyond 512.** Our preliminary experiments show that once $K$ reaches above 512, the convergence acceleration becomes marginal. Hence, we only present the convergence result up to $K=512$. This may due to that the algorithm will overly optimize one block before moving to the next block and slow down the convergence.\n\nWe hope that our response is satisfactory and addresses all your concerns. If there are any additional questions and concerns, please feel free to let us know during the author-reviewer discussion period. We are more than happy to provide further clarifications.\n\n**References**\n\n[1] Zhang et al, \"Adam can converge without any modification on update rules\", NeurIPS 2022.\n\n[2] Li et al, \"Convergence of Adam under relaxed assumptions\", NeurIPS 2023."}, {"review_id": "D4AWvvNC2X", "reviewer": "Reviewer_rREZ", "summary": "This paper proposes a memory-efficient training method for large language models that addresses limitations of vanilla block coordinate descent (BCD). The authors identify two key issues with applying BCD to neural networks: (1) ineffective utilization of intermediate derivatives during backpropagation, and (2) convergence slowdown due to frozen blocks narrowing the optimization landscape. BREAD addresses these issues by unfreezing inactive blocks and updating them using lightweight methods (LoRA or SGD) during the same backpropagation pass as the active block.", "questions": "1. Generalization: The experiments focus primarily on LLaMA models. How well does the approach transfer to other architectures (e.g., MoE, Qwen models)?\n\n2. Statistical significance: The improvements over BAdam are often small (1-3%). It is suggested to provide statistical significance tests across multiple random seeds and the confidence intervals for the reported improvements.\n\n3. How sensitive is the method to the choice of rank r, frequency K, and the ratio between active/inactive learning rates?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strength**\n1. The two limitations of BCD for neural networks are clearly articulated and theoretically grounded. The observation that computed gradients for deeper layers are wasted when only updating one block is insightful.\n2. Solid theoretical foundation: Propositions 3.1 and 4.1 provide justification for the landscape expansion approach, showing that BCD sub-problems can be strictly suboptimal and that low-rank updates can resolve this issue.\n3. Testing on both 8B and 70B models across multiple tasks (math finetuning, instruction tuning, DPO) with thorough ablation studies demonstrates the method's effectiveness.\n\n**Weakness**\n1. Limited technical novelty: The core insight of using LoRA for inactive blocks is relatively straightforward. While the theoretical analysis is valuable, the algorithmic contribution feels incremental, essentially combining existing BCD with existing LoRA techniques.\n2. No comparison with other recent memory-efficient methods beyond basic baselines (missing comparisons with methods like GaLore, DoRA, etc.)\n3. Proposition 3.1 only applies to specific conditions (non-full rank output layer) and may not generalize broadly. The convergence analysis (Theorem 4.2) is informal and based on deterministic gradients, not the stochastic setting used in practice", "was_revised": true, "final_justification": "I have carefully read the rebuttal and discussion, and my concerns have been addressed. The paper has an interesting discovery, and the proposed method outperforms the SoTA PEFT.", "rebuttal": "We thank the reviewer for the valuable comments. We now address your concerns below.\n\n**Limited novelty: Using LoRA for inactive block is relatively straightforward.** We would respectfully argue that BREAD is a well-motivated algorithmic *framework*, rather than a trivial combination of BCD and LoRA. The framework naturally incorporates BCD with any light weight optimizers (not just LoRA technique) for alleviating the sub-optimality issue and accelerates the convergence of BCD. Specifically, the effectiveness of BREAD framework has been justified through theory, efficient design, and strong empirical results under tight memory constraints. We list the details below. \n\n*Theoretical insight.* In Proposition 3.1, we identified the suboptimal landscape issue of BCD, where optimizing a single block may lead to suboptimal solution. Proposition 4.2 further reveals that low-rank landscape expansion can mitigate this suboptimality and improve the convergence of BCD. To our knowledge, this phenomenon has not been carefully examined in prior work.\n\n*Computational-efficient algorithmic design.* By leveraging the intermediate derivatives computed during the backpropagation of BCD, BREAD calculates the gradient of the expansion matrices without requiring additional backpropagation steps.\n\n*Competitive performance under limited memory budget.* Similar to LoRA and BAdam, BREAD is able to finetune Llama 3.1-70B model with only A100-80GB GPUs. Compared with memory-efficient baselines, the model finetuned by BREAD attains the highest MT-bench score and average math benchmark score in instruction tuning tasks. Notably, BREAD outperforms Adam in supervised finetuning on Alpaca-GPT4, despite its 80\\% less memory consumption.\n\nIn summary, we believe that BREAD is a well-motivated algorithmic framework with theoretical insights, computational-efficient design, and competitive empirical performance, rather than a trivial combination of BCD and LoRA.\n\n**No comparison with memory-efficient optimizers such as Galore, DoRA.** We have actually provided the comparison with Galore in terms of memory cost and downstream performance; see our Table 1-3 in the manuscript. To include more methods, we finetune Llama 3.1-8B using DoRA and ReLoRA under the same setting in Table 2 of the manuscript. We present the results in the following two tables, where we also list other methods for completeness.\n\n| Method          | GSM8K | MATH | NumGLUE | SimulEq | AQuA | Avg.  |\n|-----------------|--------|------|---------|---------|------|--------|\n| Base model      | 17.8   | 8.6  | 25.7    | 12.2    | 19.3 | 16.7   |\n| Adam            | 62.3   | 17.4 | 56.4    | 28.6    | 44.9 | 41.9   |\n| Galore          | 46.7   | 16.2 | 42.8    | 28.7    | 47.8 | 36.4   |\n| LoRA-rank80     | 48.7   | 13.7 | 34.6    | 29.6    | 47.3 | 34.8   |\n| DoRA       | 50.5   | 15.0 | 40.2    | 30.0    | 46.1 | 36.4   |\n| ReLoRA          | 47.9   | 18.3 | 49.5    | 31.1    | 45.3 | 38.4   |\n| BAdam           | 53.9   | 17.2 | 53.7    | 32.5    | 50.4 | 41.5   |\n| BREAD-LoRA      | 57.0   | 20.0 | 55.9    | 32.5    | 49.6 | 43.0   |\n| BREAD-LoRA+     | 57.8   | 20.4 | 56.1    | 32.9    | 51.2 | 43.7   |\n| BREAD-SGD       | 56.9   | 19.6 | 54.1    | 31.5    | 48.0 | 42.0   |\n**Table:** 0-shot score of math finetuning.\n\n| Method          | GSM8K | MATH | NumGLUE | SimulEq | AQuA | Avg.  |\n|-----------------|--------|------|---------|---------|------|--------|\n| Base model      | 52.5   | 23.2 | 40.6    | 28.8    | 43.7 | 37.8   |\n| Adam            | 64.9   | 22.9 | 56.8    | 33.5    | 52.8 | 46.2   |\n| Galore          | 57.2   | 22.9 | 45.0    | 32.3    | 48.4 | 41.2   |\n| LoRA-rank80     | 58.1   | 23.0 | 54.4    | 29.0    | 50.3 | 43.0   |\n| DoRA        | 57.2   | 23.1 | 52.5    | 30.9    | 47.6 | 42.3   |\n| ReLoRA          | 55.7   | 24.2 | 56.0    | 31.5    | 48.7 | 43.2   |\n| BAdam           | 58.3   | 23.6 | 57.2    | 32.8    | 49.6 | 44.3   |\n| BREAD-LoRA      | 57.6   | 23.7 | 58.2    | 32.8    | 50.0 | 44.5   |\n| BREAD-LoRA+     | 61.8   | 24.6 | 58.8    | 32.7    | 51.0 | 45.8   |\n| BREAD-SGD       | 60.6   | 21.4 | 58.2    | 31.8    | 50.8 | 44.6   |\n**Table:** 4-shot score of math finetuning.\n\nNotably, both BAdam and BREAD outperform ReLoRA and DoRA. This suggests that BCD-based algorithm might be more suitable for math finetuning task. We will provide a more comprehensive comparison with memory-efficient optimization algorithms in the next version of our manuscript.\n\n**Proposition 3.1 only applies to specific conditions and Theorem 4.2 is for deterministic case.** Let us mention that the primary focus of this work is to design a practical algorithmic framework rather than focusing on theoretical analysis. The derived propositions are mainly intended to motivate the algorithm framework design, and the convergence result serves a partial explanatory purpose to show that the algorithm is partly grounded by classic convergence theory. We consider the convergence under the deterministic setting for compact presentation. We remark that it is possible to combine the current analysis with those of [1, 2] to derive the convergence under stochastic gradient, which we leave as a future work.\n\n**Generalization to different model architectures.** Thank you for the suggestion. We finetune the Qwen 2.5-7B model using the Alpaca-GPT4 dataset for 3 epochs. The MT-bench scores (with GPT-4 as evaluator) are displayed in the following table:\n\n| Model                 | MT-bench Score |\n|-----------------------|----------------|\n| Qwen 2.5-7B (base model) | 7.23          |\n| Galore                | 7.28           |\n| LoRA-rank80           | 7.48           |\n| BAdam                 | 7.49           |\n| BREAD-LoRA            | 7.73           |\n**Table:** MT-bench scores.\n\nThe BREAD-LoRA method clearly outperforms baseline methods, which demonstrates the effectiveness of BREAD in finetuning models other than Llama series. We will add these results to include the Qwen model in the next version of our manuscript.\n\n**Statistical significance of the result.** Due to the high computational cost of training LLM, it is almost infeasible to perform multiple runs within the limited rebuttal period. We remark that in Figure 1, BREAD consistently and evidently converges faster than BAdam across different choices of rank and block switch frequency. The consistent faster convergence partially justifies BREAD's performance over BAdam in LLM's finetuning.\n\n**Sensitivity of rank, block switch frequency, and learning rate ratio.** First, he ablation study in Figure 1(c) has shown that BREAD with even rank-1 expansion matrix achieves significantly faster convergence than BAdam. As the rank increases, the convergence speed increases as well. Second, the result in Figure 1(b) shows that BREAD consistently achieves faster convergence as the block switch frequency $K$ increases (under a reasonable number, say 512). This may attribute to that when using larger $K$, the Adam optimizer will aggregate more historical information, leading to a better search direction. Third, we observe that using the same learning rate for the active module and expansion matrices consistently lead to stable convergence for all BREAD variants, and achieve acceleration over BAdam. However, when applying a 10$\\times$ larger learning rate in SGD's update of BREAD-SGD, we observe that training will diverge. We conclude that BREAD will safely converge by applying a universal learning rate, and suggest not to assign highly imbalanced learning rate for active and inactive blocks.\n\nWe hope that our response is satisfactory and addresses all your concerns. If there are any additional questions and concerns, please feel free to let us know during the author-reviewer discussion period. We are more than happy to provide further clarifications.\n\n**References**\n\n[1] Zhang et al, \"Adam can converge without any modification on update rules\", NeurIPS 2022.\n\n[2] Li et al, \"Convergence of Adam under relaxed assumptions\", NeurIPS 2023."}, {"review_id": "Mg87zPtYzO", "reviewer": "Reviewer_FNMe", "summary": "Based on the recent memory-efficient fine-tuning method like BAdam, the authors address two key limitations of the BAdam optimizer: computational waste in shallow layers and a slower convergence rate.  They propose BREAD, a novel approach that combines BAdam with either LoRA or in-place SGD (IP-SGD). The paper presents theoretical analyses and several propositions to support the proposed method. The authors conduct a series of experiments under various scenarios to demonstrate the effectiveness of their approach.", "questions": "Besides the above things mentioned in the weakness, I have a few questions and suggestions here. \n\nQuestions: \n1. A key motivation for BREAD-LoRA is to reduce wasted computation. However, a potential inefficiency appears to remain. During backpropagation in the shallow layers, are the partial derivatives for the frozen, pre-trained base model still computed? If so, this would reintroduce the same computational waste that BREAD was designed to eliminate in BAdam. \n2. Since both LoRA and SGD have low memory and training overhead, it seems natural to consider combining them. How would BREAD-LoRA-SGD perform? Could it yield better results?\n3. The authors propose two variants but do not clarify when one should be preferred over the other. Based on the empirical results, BREAD-LORA appears to consistently outperform the alternative.\n\nSuggestions:\n1. In line 196, it is good to acknowledge and mention the work LOMO [1] here. \n2. In Algorithm 1, the notation can be improved and the author should define the notation. Ex. $s_{J}^{t,0}$ and $s_{J}^t$, and the author should also use other symbols than $J$ in line 6 to avoid confusion with $j$. \n3. Since the BREAD is a hybrid method with BCD and LoRA/IP-SGD, it is also good to add the discussion of Addax [2] in their related work, which is also a memory efficient hybrid method. \n\nI hope the authors can address these concerns satisfactorily, in which case I would consider raising my score.\n\n[1] Lv, Kai, et al. \"Full parameter fine-tuning for large language models with limited resources.\" arXiv preprint arXiv:2306.09782 (2023).\n\n[2] Li, Zeman, et al. \"Addax: Utilizing Zeroth-Order Gradients to Improve Memory Efficiency and Performance of SGD for Fine-Tuning Language Models.\" ICLR 2025.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n1. The motivation is clear. The paper focus on two key limitations of the BCD approach: the computational waste from calculating partial derivatives in shallow layers and the challenges of a narrow optimization landscape.\n\n2. The proposed BREAD method offers a novel and clear approach to addressing the limitations of BAdam\n\n3. The experimental evaluation is comprehensive, replicating the full suite of experiments from the original BAdam paper. \n\nWeaknesses: \n\n1. The theoretical convergence rate of  $O(\\epsilon^{-2})$ (Theorem 4.2) is expected, given that the method combines Block Coordinate Descent (BCD) and SGD. The analysis could be strengthened by extending it to the fully stochastic case, a limitation the authors acknowledge.\n\n2. A key motivation for using LoRA is parameter efficiency, as one only needs to store the adapter instead of the full pre-trained model. The proposed BREAD-LoRA method appears to forfeit this advantage by requiring the full model to be stored. Also the inference time will increase with the LoRA adapter. \n\n3. Given that the authors propose two variants, BREAD-LoRA and BREAD-SGD, a natural extension to consider is a combined BREAD-LoRA-SGD approach. Since both LoRA and SGD individually have low memory and computational overhead, this hybrid method could potentially yield better results.", "was_revised": true, "final_justification": "Good paper. Clear accept.", "rebuttal": "We thank the reviewer for the valuable comments. We now address your concerns below.\n\n**The convergence analysis is based on the deterministic assumption.** Since our main focus for this work is to design a practical algorithmic framework (and its practical implementation) rather than establishing new theoretical convergence result, we consider the convergence under the deterministic setting for compact presentation. We remark that it is possible to combine the current analysis with [1, 2] to derive the convergence under stochastic gradient. The important steps would be establishing the approximate descent property (rather descent property) using existing analysis for Adam under stochastic setting, and then providing an overall approximate descent for the BCD loop. Finally, standard telescoping will yield the complexity result. We leave the detailed analysis as future work\n\n**BREAD-LoRA requires storing the full model checkpoint.** Storing the full parameter checkpoint appears to be inevitable when using full parameter optimization methods such as Adam, SGD, and BCD-based methods. While LoRA has the advantage of storing different types of checkpointed adaptors, full parameter finetuning might achieve higher performance, as we have verified in our experiments.\n\n**BREAD-LoRA-SGD might yield better results (W3&Q2).** We thank the reviewer for introducing the interesting idea of applying both LoRA and SGD update for inactive blocks. We apply the method in finetuning Llama 3.1-8B under the same setting in Table 1 of the manuscript. The training loss and downstream scores are shown in the following tables:\n\n| Iteration | BAdam  | BREAD-LoRA | BREAD-LoRA+ | BREAD-SGD | BREAD-SGD-LoRA |\n|------|--------|-------------|--------------|------------|-----------------|\n| 3k   | 0.584  | 0.556       | 0.528        | 0.542      | 0.546           |\n| 6k   | 0.562  | 0.523       | 0.493        | 0.515      | 0.507           |\n| 9k   | 0.551  | 0.510       | 0.478        | 0.503      | 0.485           |\n| 12k  | 0.545  | 0.504       | 0.470        | 0.496      | 0.477           |\n| 15k  | 0.541  | 0.500       | 0.467        | 0.492      | 0.473           |\n\n**Table:** Training loss.\n\n| Method             | GSM8K | MATH | NumGLUE | SimulEq | AQuA | Avg.  |\n|--------------------|--------|------|---------|---------|------|--------|\n| BAdam              | 53.9   | 17.2 | 53.7    | 32.5    | 50.4 | 41.5   |\n| BREAD-LoRA         | 57.0   | 20.0 | 55.9    | 32.5    | 49.6 | 43.0   |\n| BREAD-LoRA+        | 57.8   | 20.4 | 56.1    | 32.9    | 51.2 | 43.7   |\n| BREAD-SGD          | 56.9   | 19.6 | 54.1    | 31.5    | 48.0 | 42.0   |\n| BREAD-LoRA-SGD     | 57.3   | 20.1 | 56.0    | 32.7    | 50.4 | 43.3   |\n**Table:** 0-shot score of math finetuning.\n\n| Method             | GSM8K | MATH | NumGLUE | SimulEq | AQuA | Avg.  |\n|--------------------|--------|------|---------|---------|------|--------|\n| BAdam              | 58.3   | 23.6 | 57.2    | 32.8    | 49.6 | 44.3   |\n| BREAD-LoRA         | 57.6   | 23.7 | 58.2    | 32.8    | 50.0 | 44.5   |\n| BREAD-LoRA+        | 61.8   | 24.6 | 58.8    | 32.7    | 51.0 | 45.8   |\n| BREAD-SGD          | 60.6   | 21.4 | 58.2    | 31.8    | 50.8 | 44.6   |\n| BREAD-LoRA-SGD     | 59.2   | 24.0 | 58.4    | 32.6    | 50.6 | 45.0   |\n**Table:** 4-shot score of math finetuning.\n\nWe observe that BREAD-LoRA-SGD converges evidently faster than both BREAD-LoRA and BREAD-SGD, which supports the hypothesis that applying both memory-efficient optimization algorithms is better than just applying one. For the downstream task, BREAD-LoRA-SGD also slightly outperforms both BREAD-LoRA and BREAD-SGD in terms of average score. Based on these experiments, applying LoRA+ and SGD might yield better result than BREAD-LoRA+. We leave it as an interesting future research direction. In the next version, we will add the suggested variant and BREAD-SGD-LoRA+ (if this LoRA+ version performs well). Thank you again for the nice suggestion. \n\n**Are the gradient of shallow layers computed?** As shown in equation (5), there are two backward modes. The full backward requires computing the gradient of all the layers, while the efficient backward only computes the gradient up to the active layer.\n\n**Suggestion on the choice of BREAD variants.** BREAD-LoRA variant offers faster convergence and better downstream performance over BREAD-SGD. The observation is consistent with the fact that LoRA can converge faster than SGD for finetuning task, especially when SGD is performed in pure bfloat16 precision. We thereby suggest to use BREAD-LoRA or BREAD-LoRA+ for finetuning tasks.\n\n**Suggestions:**\n* **Acknowledge LOMO.** We will acknowledge and mention LOMO when introducing BREAD-SGD in the next version.\n* **Notation definition.** Thank you for the suggestion. The $s_J^t$ refers to the Adam optimizer states of expansion matrices. We will add a definition in the manuscript.\n* **Discussion on Addax.** We thank the reviewer for referring the related work. Addax applies both first-order and zeroth-order update with different batch sizes, where all the layers are equally treated. In contrast, BREAD distinguishes between active and inactive blocks; the active block drives convergence, while the inactive block facilitates landscape expansion. We will discuss the relationship between BREAD and Addax in the next version of our manuscript.\n\nWe hope that our response is satisfactory and addresses all your concerns. If there are any additional questions and concerns, please feel free to let us know during the author-reviewer discussion period. We are more than happy to provide further clarifications."}, {"review_id": "9XefuTjJZ1", "reviewer": "Reviewer_GYiG", "summary": "This paper introduces BREAD, a memory-efficient algorithm for fine-tuning LLMs that improves upon Block Coordinate Descent (BCD). \n\nWhile BCD reduces memory requirements by updating only one block of parameters at a time, the authors identify two critical limitations when applied to neural networks: wasted computation during backpropagation through frozen layers, and a restricted optimization landscape that can slow convergence.\n\nBREAD addresses both issues by unfreezing inactive blocks and updating them using lightweight methods (low-rank matrices or SGD) during the same backpropagation pass. This \"landscape expansion\" adds minimal memory overhead while utilizing already-computed gradients and providing a broader optimization view.", "questions": "Why choose LoRA-rank80 and LoRA-rank64 when comparing with LoRA?\n\nsuggestions:\n\n1.For the assumptions made during the theoretical derivation, additional statistical evidence can be provided to demonstrate that these assumptions are commonly present in practice.\n\n2.Include experimental comparisons with at least 2–3 recent memory-efficient methods.", "limitations": "yes, authors addressed the limitations and potential negative societal impact of their work", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths：\n- The theoretical analysis is thorough and compelling.The paper formally proves BCD's suboptimality issue in neural networks through Proposition 3.1 and demonstrates that rank-1 expansion can resolve it via Proposition 4.1. \n- Systematic ablation experiments on key hyperparameters enhance the credibility of the method.\n\nWeaknesses：\n- Missing comparisons with some recent memory-efficient methods like ReLoRA, LISA, etc.\n- Some theoretical assumptions have not been substantiated to generally hold in the fine-tuning of large language models.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable comments. We now address your concerns below.\n\n**Missing comparison with recent memoy-efficient methods.** Thank you for the suggestion. We finetune Llama 3.1-8B on MathInstruct dataset under the same setting in Table 2 of the manuscript, using the additional ReLoRA and DoRA. The full benchmark score is shown in the following table:\n\n| Method          | GSM8K | MATH | NumGLUE | SimulEq | AQuA | Avg.  |\n|-----------------|--------|------|---------|---------|------|--------|\n| Base model      | 17.8   | 8.6  | 25.7    | 12.2    | 19.3 | 16.7   |\n| Adam            | 62.3   | 17.4 | 56.4    | 28.6    | 44.9 | 41.9   |\n| Galore          | 46.7   | 16.2 | 42.8    | 28.7    | 47.8 | 36.4   |\n| LoRA-rank80     | 48.7   | 13.7 | 34.6    | 29.6    | 47.3 | 34.8   |\n| DoRA       | 50.5   | 15.0 | 40.2    | 30.0    | 46.1 | 36.4   |\n| ReLoRA          | 47.9   | 18.3 | 49.5    | 31.1    | 45.3 | 38.4   |\n| BAdam           | 53.9   | 17.2 | 53.7    | 32.5    | 50.4 | 41.5   |\n| BREAD-LoRA      | 57.0   | 20.0 | 55.9    | 32.5    | 49.6 | 43.0   |\n| BREAD-LoRA+     | 57.8   | 20.4 | 56.1    | 32.9    | 51.2 | 43.7   |\n| BREAD-SGD       | 56.9   | 19.6 | 54.1    | 31.5    | 48.0 | 42.0   |\n**Table:** 0-shot score of math finetuning. \n\n| Method          | GSM8K | MATH | NumGLUE | SimulEq | AQuA | Avg.  |\n|-----------------|--------|------|---------|---------|------|--------|\n| Base model      | 52.5   | 23.2 | 40.6    | 28.8    | 43.7 | 37.8   |\n| Adam            | 64.9   | 22.9 | 56.8    | 33.5    | 52.8 | 46.2   |\n| Galore          | 57.2   | 22.9 | 45.0    | 32.3    | 48.4 | 41.2   |\n| LoRA-rank80     | 58.1   | 23.0 | 54.4    | 29.0    | 50.3 | 43.0   |\n| DoRA        | 57.2   | 23.1 | 52.5    | 30.9    | 47.6 | 42.3   |\n| ReLoRA          | 55.7   | 24.2 | 56.0    | 31.5    | 48.7 | 43.2   |\n| BAdam           | 58.3   | 23.6 | 57.2    | 32.8    | 49.6 | 44.3   |\n| BREAD-LoRA      | 57.6   | 23.7 | 58.2    | 32.8    | 50.0 | 44.5   |\n| BREAD-LoRA+     | 61.8   | 24.6 | 58.8    | 32.7    | 51.0 | 45.8   |\n| BREAD-SGD       | 60.6   | 21.4 | 58.2    | 31.8    | 50.8 | 44.6   |\n**Table:** 4-shot score of math finetuning. \n\nNotably, both BAdam and BREAD outperform ReLoRA and DoRA. This suggests that BCD-based algorithm might be more suitable for math finetuning task. Due to limited computational resource, we are unable to finish the experiment of LISA during the short rebuttal period. We will provide a more comprehensive comparison with memory-efficient optimization algorithms in the next version of our manuscript.\n\n**Some assumptions have not been substantiated to generally hold for LLM finetuning.** We acknowledge that the assumptions such as smoothness and deterministic gradient might not hold for general LLM training. However, without assumptions such as smoothness, it is challenging to establish a meaningful convergence result. Theoretical works (e.g., [1, 2]) that analyze Adam's convergence also require certain type of smoothness to derive the descent of the objective for each step. Additionally, while it is possible to remove the deterministic assumption, the analysis will be unnecessarily intricate and does not bring additional insight about the algorithm. The current convergence result based on deterministic gradient can already serve a partial explanatory purpose to show that the algorithm is grounded by classic convergence theory. We remark that it is possible to combine the current analysis with [1, 2] to derive the convergence under stochastic gradient. The important steps would be establishing the approximate descent property (rather descent property) using existing analysis for Adam under stochastic setting, and then providing an overall approximate descent for the BCD loop. Finally, standard telescoping will yield the complexity result. We leave the detailed analysis as future work.\n\n**Why choosing LoRA-rank80 and LoRA-rank64?** We set LoRA's rank to be 80 and 64 for finetuning 8B and 70B model, respectively. As we explained in Appendix B, we adopt the rank so that the number of trainable parameters of LoRA roughly matches the active block of BAdam/BREAD for a fair comparison.\n\n**Suggestions:**\n\n1. **Statistical evidence for verifying assumptions.** Thank you for the suggestion. In the next version, we would like to exam whether the smoothness condition and gradient boundedness condition will be satisfied for a simple and small LLM. Note that verifying smoothness often needs to bound the spectral norm of Hessian, which is computationally prohibitive for large-scale LLMs. \n\n2. **Include 2–3 recent memory-efficient methods.** Thank you for the suggestion. As we replied previously, we have added comparisons with ReLoRA and DoRA. We will add them in the next version of the manuscript. \n\nWe hope that our response is satisfactory and addresses all your concerns. If there are any additional questions and concerns, please feel free to let us know during the author-reviewer discussion period. We are more than happy to provide further clarifications.\n\n**References**\n\n[1] Zhang et al, \"Adam can converge without any modification on update rules\", NeurIPS 2022.\n\n[2] Li et al, \"Convergence of Adam under relaxed assumptions\", NeurIPS 2023."}]

Author rebuttal:

Meta-review: This paper presents BREAD, a memory-efficient fine-tuning algorithm that enhances Block Coordinate Descent (BCD) by addressing wasted computation and limited optimization landscapes. By updating inactive blocks with lightweight methods during the same backpropagation pass, BREAD achieves better optimization with minimal overhead. 

The rebuttal addressed reviewers' concerns, and the method demonstrates strong empirical performance, outperfoming state-of-the-art PEFT approaches. Overall, this is a well-motivated paper, therefore I recommend acceptance.
Decision: Accept (poster)