Finite-budget low-rank adaptation by gradient descent

Fix positive integers $d,k,n$, an integer $1\le r\le \min (d,k)$, a frozen matrix $W_0\in {\mathbb{R}}^{d\times k}$, a nonzero scale $c\in \mathbb{R}$, a finite ordered data list $(x_i,y_i{)}_{i=1}^n$ with $x_i\in {\mathbb{R}}^k$, and, for each data entry, a loss program ${\mathrm{\ell }}_i$ that returns a real scalar wherever its primitive calls are defined. Let $T\ge 0$ be a finite integer, let $I_0,\dots ,I_{T-1}$ be fixed finite nonempty ordered lists of indices in $\{1,\dots ,n\}$ (repeated indices are allowed), let ${\eta }_0,\dots ,{\eta }_{T-1}\ge 0$ be finite step sizes, and supply an initial matrix $A_0\in {\mathbb{R}}^{r\times k}$. The procedure has no dropout or random initialization; any random initialization must be sampled externally and supplied as $A_0$. Set $B_0=0\in {\mathbb{R}}^{d\times r}$.

Represent each loss evaluation by a specified finite real-arithmetic program with a scalar output. Each primitive is continuously differentiable on a declared open domain or is piecewise continuously differentiable, with finitely many open branch regions, a continuously differentiable formula on each region, and a separately specified primal boundary value when one is defined. Here $C^1$ means totally differentiable with continuous derivative. Check admissibility at the current factors on each step; a strict branch used at one step need not be the branch used at another.

$L_t(A,B)=\frac{1}{\mathrm{\mid }{I}_t\mathrm{\mid }}{\sum }_{i\in I_t}{\mathrm{\ell }}_i\text{\hspace{0.17em}⁣}((W_0+cBA)x_i)$

Starting with $t=0$, perform the following finite loop while $t<T$:

1. Evaluate the displayed program at $(A_t,B_t)$, visiting its primitive calls in evaluation order. At the first call with no primal value, return DOMAIN_ERROR with the current factors and step index $t$. At the first defined piecewise primitive whose input lies on a branch boundary or has ambiguous branch selection, return NONDIFFERENTIABLE with the current factors and step index $t$. If every primitive call has a value and every piecewise primitive is on a unique strict branch, run reverse-mode automatic differentiation on this same scalar-output program at $(A_t,B_t)$, with the selected branch choices, with respect to the ordered list of all entries of $A_t$ followed by all entries of $B_t$, each matrix flattened row by row. If reverse mode returns either failure status, return it with the current factors and step index $t$. No factor update is made on a failure status.
2. If reverse mode returns gradients, reshape the first and second blocks into $G_t^A\in {\mathbb{R}}^{r\times k}$ and $G_t^B\in {\mathbb{R}}^{d\times r}$, respectively, and set

$A_{t+1}=A_t-{\eta }_t{G}_t^A,B_{t+1}=B_t-{\eta }_t{G}_t^B\mathrm{.}$

Increment $t$ by one.

After $T$ successful updates, return SUCCESS, the matrices $A_T,B_T$, and the merged weight $W_0+c{B}_T{A}_T$. At $T=0$ return the supplied $A_0$, zero $B_0$, and $W_0$ without evaluating a loss. This is a finite real-arithmetic procedure; it asserts no convergence, minimization, generalization, floating-point accuracy, speed, or memory guarantee.

Low-rank adaptation of a linear layer: the factor shapes, frozen base matrix, and updated matrix used here.

Finite straight-line computational programs and real-arithmetic tapes: finite ordered real-arithmetic graph, C1 primitive, admissible domain, and strict-branch conventions.

Reverse-mode automatic differentiation for a scalar graph output: scalar-output reverse sweep and its domain-error and branch-boundary statuses.

Hu et al., §4.1: frozen base weights, trainable factors, and merged weights

MIT OCW, §§8.3–8.4: reverse-mode accumulation for finite scalar objectives