FLOPS: Forward Learning with OPtimal Sampling
Authors: Tao Ren
Zishi Zhang
Jinyang Jiang
Guanghao Li
Zeliang Zhang
Mingqian Feng
Yijie Peng
Venue: ICLR 2025 Poster (2025)
Keywords: stochastic optimization
zeroth-order optimization
bp-free training
Primary area: optimization
TL;DR: Design an optimal query allocator for forward learning

Abstract: Given the limitations of backpropagation, perturbation-based gradient computation methods have recently gained focus for learning with only forward passes, also referred to as queries. Conventional forward learning consumes enormous queries on each data point for accurate gradient estimation through Monte Carlo sampling, which hinders the scalability of those algorithms. However, not all data points deserve equal queries for gradient estimation. In this paper, we study the problem of improving the forward learning efficiency from a novel perspective: how to reduce the gradient estimation variance with minimum cost? For this, we allocate the optimal number of queries within a set budget during training to balance estimation accuracy and computational efficiency. Specifically, with a simplified proxy objective and a reparameterization technique, we derive a novel plug-and-play query allocator with minimal parameters. Theoretical results are carried out to verify its optimality. We conduct extensive experiments for fine-tuning Vision Transformers on various datasets and further deploy the allocator to two black-box applications: prompt tuning and multimodal alignment for foundation models. All findings demonstrate that our proposed allocator significantly enhances the scalability of forward-learning algorithms, paving the way for real-world applications. The implementation is available at https://github.com/RTkenny/FLOPS-Forward-Learning-with-OPtimal-Sampling.

Published as a conference paper at ICLR 2025
FLOPS: FORWARD LEARNING WITH OPTIMAL SAM- PLING
Tao Ren 122, Zishi Zhang a JJinynn Jiang' 1.2 Guanghao Li Zeliang Zhang Mingqian Feng', Vijie Pengl.2f
Guanghua School of Management, Peking University Xiangjiang Laboratory
3 Tsinghua Shenzhen International Graduate School, Tsinghua University
4 Huazhong University of Science and Technology Johns Hopkins University
(rtkenny, zi zishi shang,,,,, j minynng..a.. jia.inannnnsttt. jinyang.jianggeeseee wwt.eett..pueedu... Ligh24 mam.iaiis.a. tsinghua. edu. en, bust04268gmmi com, mfenng 00 ji edu, pengyi jie@pku. edu, on
ABSTRACT
Given the limitations of backpropagation, perturbation-based gradient computa- tion methods have recently gained focus for learning with only forward passes. also referred to as queries. Conventional forward learning consumes enormous queries on each data point for accurate gradient estimation through Monte Carlo sampling, which hinders the scalability of those algorithms. However, not all data points deserve equal queries for gradient estimation. In this paper, we study the problem of improving the forward learning efficiency from novel perspective: how to reduce the gradient estimation variance with minimum cost? For this, we allocate the optimal number of queries within a set budget during training to balance estimation accuracy and computational efficiency. Specifically, with simplitied proxy objective and a reparameterization technique, we derive a novel plug-and sal--and-llal -lay query allocator with minimal parameters. Theoretical results are carried out to verify its optimality. We conduct extensive experiments for fine- tuning Vision Transformers on various datasets and further deploy the allocator to black-box applications: prompt tuning and multimodal alignment for foun- dation models. All findings demonstrate that our proposed allocator significantly enhances the scalability of forward-learning algorithms, paving the way for real- world applications. The implementation is available at ht:ps:////// / com/ www.owaad--aeeainrree Learning OPE ima --Samplin
INTRODUCTION
Ever since the success of backpropagation (BP) (Rumelhart et al. 1986), researchers have sought alternate methods to bypass the iterative computation of the backward pass for the sake of efficiency, interpretability, and biological plausibility (Ma et al., 2020] Nøkland 2016 Jaacot et al.. 2018). Moreover, existing practical scenarios urge for scalable forward learning methods, when the black- box nature renders taking the derivative infeasible or difficult. For example, as the model parameters increase, machine learning (ML) systems usually integrate with third-party black-box APIs (Achiam ct al. 2023).
There have been continuous efforts to develop learning algorithms that rely solely the forward pass (Lillicraper et al. 2020). The forward learning uses multiple queries on one data point to estimate the gradient (Spall) 1992]
al. 2024). The high dimensionality and the rugged loss landscape of ML problems pose arduous challenges for deriving a low-variance gradient estimator. Current literature has demonstrated that sufficient number of queries on each data point is necessary for successful training (Chen et al.] 2023 Zhang et al. 2024). To achieve good gradient estimation and task performance, all existing methods equally assign a large number of queries different data points, neglecting the varying difficulty of gradient estimation at these data.
These authors contributed equally to this work.
Corresponding author.

---

Published as a conference paper at ICLR 2025
However, it is not always helpful for the forward learning algorithms to increase the number of queries. Especially for the large model training on a large dataset, it usually requires an ex- tensive number of queries. which poses great challenges to the memory and computation cost. For example, The forward-forwand (FA) (Nøkland (006) are only capable of training multilayer perceptrons MNIST (LeCun 1998) or CIFAR (Krizhevsky et al. 2200). To scale up the forward algorithm to large model training on large datasets, DeepZero (Chen al. 2023) and Mezo (Malladi et al. 2023) explore the use of simultaneous perturbation stochastic approximation (SPSA) (Spall) 1992) in training the convolu- tion network from scratch and fine-tune the language model, respectively. But with such "large" scale optimization problem, DeepZero requires 192 queries to train pruned ResNet-20 with only 12K parameters. Mezo needs meticulously selected prompts to ensure performance, and its gra- dient estimator is too noisy due to insufficient query numbers, thus suffering from highly unstable performance.
(FF) (Hinton 2022) algorithm and the feedback alignment
There is great challenge required to be considered carefully in forward learning. On the one hand, consuming large amounts of queries on every data point results in high computational costs and long training time. On the other hand, using insufficient queries tional costs but lead to unstable performance. Efficiently utilizing the queries with limited memory and computation budget is at the core of the scalability for forward learning reduce the gradient estimation variance and improve the model training efficiency.
memory and computa-
To achieve a good balance between the query cost and gradient estimation variance, we propose to study the query allocation problem under the forward learning framework. In our paper, we first unify the different estimators under the perturbation-based framework and formulate the allocation problems. Then, we propose the optimal allocation by constructing a query budget allocator to assign queries adaptively following a data-aware paradigm. An overview of our method and the Specifically, our contribution can be
comparison with previous work can be found in Figure [| summarized as follows,
1. We unify different fP-free methods under the framework of perturbation- bbased optimiza- tion. We are the first formulate the query allocation problem for forward learning in the literature.
2. We find simplified objective for the allocation problem and solve it via the likelihood ratio method in lightweight style. With the optimal allocation, we can compress the queries to the minimum number of 20.
3. We theoretically deduce that the enhancement in allocation is assured by a defined lower bound. The allocator would assign the queries for different data in mini-batch according to the variance of the gradient estimation. Intuitively, the estimator with high variance would be assigned with more queries, and vice versa.
4. We conduct extensive experiments to fine-tune Vision Transformer (Dosovitskiy 2020) on challenging datasets, including ImageNet-1K [eng et al. (2009). achieving sfate-of-the- art performance in forward learning. Furthermore, we apply the proposed method to two real-world black-box problems: black-box prompt tuning and alignment between founda- tion models. Our approach demonstrates scalability and efficiency improvements over all baselines, including backpropagation (BP).
RELATED WORK
Backkropagation-free learning. People have explored various algorithms without backpropagat-
ing the error (Wierstra et al. 2014 Frenkel et al. 2021 Journé et al. [022 Kao & Hariharan [024). Frenkel et al. (2021) eliminates the feedback pathway by leveraging fixed random projections of tar- get labels to hidden layers. Kao & Hariharan (2024) employs a dual-network structure to propagate input and target signals in anti-parallel directions. Forward gradient (Baydin et al.) 2022 Silver et al., 2021). applying the chain rule from a different direction than BP, utilizes forward-mi mode au- tomatic differentiation (AD) to train the ML model. Forward-mode AD needs specific AD software and full access to the model structure. Therefore, training the deep model under black-box scenarios not feasible by the forward gradient (Ren al. 2022).
2

---

Published as a conference paper at ICLR 2025
Perturbation f()
Black box module
Target module ((:0)
Black box module d ()
Evaluation module
1:1:1
(a) Vanilla (equal allocation)
Loss value ((x.2,0)
Perturbation z ~ fO
Black-hox module +1()
Target module (::0)
* Black-bon module (2
Evaluation module
As
Allocator P(A]A:b)
Loss ((s.,,,)
(b) A daptivv allocation
Figure 1:
Illustration of allocating the query budget of the forward learning paradigm. As shown in (a), previous methods equally allocate the query across different data. Our method, as shown in (b), adaptively allocate the queries under theoretically guaranteed optimality.
Perturbation-based forward learning. Built on the theory of stochastic optimization, researchers have devised surrogate methods to approximate the first-order gradients, such SPSA (Spall 1992). The SPSA injects noise with opposite signs into the model parameters to form a finite-difference style estimator. Recently. Mezo (Malladi al. 2023) applied SPSA fine-tune the language model. DeepZero (Chen et al. (023) integrates SPSA with sparsity and trains the network from scratch with many queries. However, their methods still have some limitations and their query budgets are equally allocated, neglecting the data difference. Jiang et al. (2023) extends the likelihood ratio (LR) estimator to train wide range of neural networks, whereas LR has not been verified on modern-seal architectures, such as Transformers [Vaswani 2017), leaving significant gap for further research to improve the scalability of forward learning.
Machine learning for black box scenarios. The applications real-world black-box scenarios call for scalable BP-free algorithms. When deploying ML algorithms on specific hardware systems, computation resources are limited and BP becomes infeasible. In the fields of physics and chemistry, MI. models have to interact with environments that include non-differentiable operations (Momeni al. 2023 Gu et al.. 2021). Moreover, extremely large models are often only accessible through third-party API (Sun et al. (022). Evolutionary algorithms and reinforcement learning have been applied to tune the prompt for the black-box language model (Diao et al. 2022).
Advanced technique for data sampling and reshuffting. In the literature on stochastic optimiza- tion, apart from uniform sampling, people have designed various methods sample data points from the dataset by importance sampling (Zhao & Zhang 2015). reshuffling (Lu et al. 2022). etc. Their method can reduce the variance of the stochastic gradient. Their methods share some similar- ities with our OPtimal Sampling. However, the key distinction between our work and the existing methods lies in the probability spaces considered. While the existing methods focus on reducing variance in the probability space associated with "sampling data points from the dataset", our ap- proach focuses on perturbation-bant forward learning, where the variance lies in the probability space of the injected noise for gradient estimation.
3 A UNIFIED PERSPECTIVE OF PERTURBATION-BASIE FORWARD LEARNING
Given a generic neural network with no assumption on its architecture, the input is denoted as x Rd=, and the output is given by y = (2((((() (z); E Rdy, where di (-) and Φb(-) box parts, and sp:; 8) is the targeted module with trainable parameters A E θ C d Conducting backpropagation through d1 (+) and @2(-) is infeasible or difficult. Training the neural network is to solve such optimization problem: minøee * Exex L(y), where X' is the dataset for training.
(-) are black-
and C(-) is an evaluation procedure yielding the loss feedback. The growing scale of parameters in modern neural networks and the dataset makes gradient-based methods the only feasible solution. Since forward learning do not rely on the chain rules to compute the true gradient, the primary challenge remains in estimating the gradient accurately and efficiently.
3

---

Published as a conference paper at ICLR 2025
In addition to approaches requiring computation graphs like BP, forward-learingg algorithms esti- mate gradients by perturbing the neural activity (intermediate output or parameter of the targeted module cp;; 8)) and observing the impact of the injected perturbation on the final loss value, thereby solving the stochastic version of the problem: mingee aid Ezex (ew(()((())) where 2 is the
injected noise with density f(-).
Forward learning algorithms can be divided into two categories: the LR family and the SPSA/ES family. The LR family perturb the intermediate output of the targeted module to perform estimation Jiang et al. 2023) i.e., = (2()(01(1);;) + 2). The gradient can be estimated by
VoE(CC())
GLL 0, 2)] A Ee- ( (() 0) 0) In f()),,
(1)
where Dya E Rd xd. denote the Jacobian matrix of a E R with respect to E R
The SPSA/ES family injects noise to the parameters (Spall 1992. Salimans et al. 2017 i... y (2(p(01 (z); + z)). For continuous noise distributions, the gradient estimation can be derived as special case of equality [ as follows:
VoE[C(u)] FewseeG 0, & ( In f())),
which takes the same form termed the evolutionary strategies (ES) estimation (Salimans al. 2017]. The SPSA is special case of ES which uses Gaussian noise 2 ~ (V, o²Ia) and applies an antithetic variable trick for variance reduction equality (2). The SPSA can be interpreted as randomized finite differences in high-dimensional space. It takes the form
V VolE(C(v)] = (eewvo)GsSSSA(L 0,)]
= Eg -
((())(((()))))) =)) - [(0)(p(01()))0 2)))]-
(3)
20
To estimate the expectation of gradient according to equation and 3). both SPSA/ES and LR family Monte Carlo sampling. With A queries Monte-Carlo sampling esti- mate the gradient on data point x, the corresponding estimations take the sample-average form Vol(y) = - Σd i=i G(x, 2;), where is sampled independently from f(-) and G(v, 0 2,) is the i sample of the corresponding gradient estimator (G(xz, 0, 24) can be GLR(Æ, 0, 21), GEs 0, 2,) or GSPSA(T, (Ir, 0, 2)).
The parameter is updated iteratively with mini-batch of data points randomly drawn from X, denoted as {21.-.. ... ,BB), where B is the batch size. We denote the gradient estimation data zÿ as (o = A; E G(I,, 0, z..)), where Ay denotes the allocated query size, and the batch- wise gradient estimation is voL(O,) = B EE (oL.(()). The updating recursion can be written as
1 01+1 0. 0c 17: TB Σ (oC 0. TB A G(z,,0,za))
(4)
where 0g is the network parameter at the 1-th step, and т) is the learning rate.
By default, the query amount A; allocated to estimate the gradient associated with each data point zy is equally allocated. However, the difficulty of gradient estimation and the model performance differ over data points. To conserve computational resources while maintaining the quality of gradient estimation, the number of queries should be properly allocated across data within the mini-batch. Utilizing the likelihood ratio technique, we propose universal accelerator for all perturbation- based training methods from a data-aware perspective.
4 OPTIMAL SAMPLING VIA LIKELIHOOD RATIO METHOD
4.1 GAUSSIAN ALLOCATOR AND BERNOULLI ALLOCATER
Definition. The query allocator is defined as a random vector A = (A), AA), where each component A, represents the (relative) number of queries allocated the j-th data point in the batch.
4

---

Published as a conference paper at ICLR 2025
The allocator is assumed to follow probability measure A ~ P(A[>: T), which is parameterized by À E A and conditioned on features L such as the loss. At each step of neural network training, sample of A is drawn from this distribution, and queries allocated to data points based on the sample. In this work, we select a Gaussian Allocator (GA)
A ~ N 2),
where À == (1, E Rd x R The matrix E captures the correlation structure between data points and facilitates the allocation of queries. Intuitively, structurally similar data points possess similar levels of importance, leading to similar trend in query allocation. It is important note that GA has a positive probability of generating negative samples. In practice, any data point receiving a negative allocation assigned zero queries.
Bernoulli Allocator (BA) is another lightweight alternative, similar to the idea in Qin et al. 2023 In an equal allocation scenario, each data in the batch receives A queries. The BA introduces probabilistic mechanism where, with probability the number of queries assigned to data point is reduced A/2: otherwise, it remains at A. The probability p the only parameter of the allocator. The BA is in the form of a conditional probability distribution
p. <
P(Aj = =
(6)
0.
2
where Lj is the clean loss on data zj. and L is the mean of loss value in the batch(we use the loss value without injected noise into the network).
is important to note that A represents the relative number of queries, and thus the actual allocation proportion to the j-th data point is given by A//E. A,. This definition eliminates the need for imposing a fixed total budget constraint in the following allocator optimization problem. However, as consequence, we must specify that the total query budget per step is fixed at Ao = A B during the training process. Note that, since the data points selected in the mini-batch differ at each step, A is actually function of t. For simplicity of notation, we omit this dependency in the remainder of the paper.
4.2 OPTIMIZATION OF THE QUERY ALLOCATOR.
We employ a gradient-based based method to optimize the allocator parameters X, introducing an addi- tional optimization step before each iteration of neural network training. However, by formulating an equivalent optimization objective and utilizing reparameterization techniques, ensure that this auxiliary optimization remains computationally lightweight and incurs minimal overhead.
Our objective is to maximize the performance improvement this step, i.e..
arg max (4(()) E PAMP(-IN A AEA
-1s((0+)))-, C0,0
where C, is the loss corresponding to the j-th data point. Assuming that Cj is L-smooth, Vj 1, -.... B, and θ is convex set, we can derive a lower bound of the optimization objective (A.
B Σ J=1
- 3 - - LIV
PL(A) > LB.(A) 2 EANPHI
(8)
Inequality (8) (the proof is provided in Appendix A.I closely resembles the Descent Lemma com- monly used the analysis of gradient descent. The lower bound LB, is often utilized as a surrogate optimization objective in the literature on adaptive step size (Pirotta et al. 2013) and adaptive batch size (Papini et al. 2017). Since our decision variable is À now, we can further simplify the form of (A). Before proceeding, according to the Central Limit Theorem, it is canonical to assume that the perturbation based gradient estimator (O)) A, Σ. G(I,, Pe 21,). 2ng f(),
1.... B, approximately follows a d-dimensional Gaussian distribution.
Assumption 1. Vj = 1,.... ... B, (0)) ~ N + where red and Edit are the expectation and the covariance matrix of G(a,, 0,, [(.), respectively.
5

---

Published as a conference paper at ICLR 2025
Theorem (Equivalent Objective). Suppose that the Assumption 7 holds, maximizing the lower bound (X) over À E A is equivalent to minimizing
B Σ
J₂(A) - BA-P(IA)
TT
G
(9)
Aj
7 j
over À E A, i.e,
max LB,(A) PEA
min (A).
X
The equivalent expression (9) of the optimization objective makes the optimization of the allocator both computationally and statistically tractable (see the proof in Appendix [A.2]. First, it demon- strates that the optimization of the allocator is independent of both the smoothness parameter L and the expectation n of the estimator sample. Consequently, we can avoid estimating these unknown and bias-inducing high- ligh-dimnssonal parameters. More importantly, the optimization the allocator does not require estimating the off-diaggnal elements of the covariance matrix Σ/.4 which can be statistically and computationally challenging (Fan et al. 2008), especially since D is of dimen- sion d², It only requires estimating the trace of DG i.e., the sum of the diagonal variances, which significantly reduces the computational complexity.
Moreover, adopt a subsampling technique in which the trace of the covariance matrix corre- sponding to the parameters of the deep layers of the neural network serves as an approximation for the overall trace. This approximation is justified as these layers typically account for the majority of the variance in the model. In practice, prior to the optimization process of the allocator, we sample small number of initial queries for each data point to estimate Tr(EZ)). ). In the subsequent compu- tations, Tr(2%))) is replaced by its estimate in a plug-in manner. In addition, from Theorem 1 can see that generally data points with higher variance should be allocated more query resources.
Then, the gradient of (A) with respect allocator parameter À is given by
B
Vi Tr V In(P(A)
VAJ((A) VAE
Σ
T
(10)
The LR gradient estimator for the allocator takes the sample average form
k
VAJ(A)
VAIn(P(A()))
(11)
K
are i.id samples from P(-I)) and K is the number of sampling from P(-IA). At each step of neural network training, we employ the above gradient estimator to search for the optimal allocator parameter X; A arg max J(X). Let LBI and LB represent the lower bound of the cumulative performance improvement of the neural network after T' steps of training when using the optimal allocator A" P(-[ and using equal allocator A equal respectively. Then the difference between these two allocation strategies is lower bound by the following expression.
where (a) (A(4) ............ .A.
(A)
Theorem (Theoretical Improvement). Suppose that the Assumption I holds, then we have
B(LBi LBequal
mi L Σ jsk
VTT(I/))
2 VIT(I"))) 2 0.
2BA0
Theorem (sce the proof in Appendix A.3) quantifies the superiority of our proposed optimal alloca- tor over the vanilla equal allocation strategy. The greater the differences in Tr(E%/) across different data points (i.e., the stronger the heterogeneity), the more pronounced the superiority of the optimal allocator, and this difference equals zero if and only if all Tr(E)))) equal.

---

Published as a conference paper at ICLR 2025
4.3 REPARAMETERIZATION OF THE GAUSSIAN ALLOCATOR.
The original parameter dimension of the Gaussian allocator is B + B(B+1) which might be prob- lematic due its high dimensionality. To reduce the dimensionality of the allocator's optimization problem and to incorporate more relevant features, we adopt reparameterization approach, i.e., imposing a specific structure the parameter X.
Drawing inspiration from the literature on data pruning (Qin ct al. 2023). the loss value serves as strong indicator of the data point's characteristics. Therefore, we assume that the mean of the allocator follows linear structure:
== Po + B1
where = Tanh(C(x; 0:))) the "clean" loss without injected noise. The original loss value is processed through Tanh function constraint + within the range [-1,1]. The initial value for fo and B1 are A and A/2, respectively.
For the covariance structure Σ, based on the observation that similar data may have similar influ- ences the training of neural networks, reparameterize the covariance matrix follows: the covariance between the allocation of the i-th data point and the j-th data point is
dijj 2y²
E(i,j) = o'exp
where di,j is the cosine similarity of the embedding between the i-th and the j-th data points. o² and 72 are two parameters that control the scale and decay of the covariance, respectively. The is initialized as A/5 and y is initialized as 1. This kernel-based reparameterization form, also known as the Radial Basis Function (RBF), is widely used in Gaussian process regression and Bayesian Optimization literature (Shahriari et al. 2015). It enables us to model dependencies between data based their pairwise distances.
By applying the reparameterization techniques to the covariance matrix E and mean vector μu, the original high-dimensional optimization problem for these parameters has been effectively trans- formed into a more manageable optimization problem for 4 variables À = (Bo, 0, The pseu-
docode for the forward learning under optimal allocation is in Appendix B
EXPERIMENTS
5.1 FINETUNING VISION TRANSFORMER
We evaluate model's performance using a diverse set of widely used benchmark datasets, each chosen for its unique characteristics and specific challenges contributing to a comprehensive analysis of our method's generalization across different domains: ImageNet (Deng et al. 2009), Caltech 101 FFei-Fei et al. 2004), Food101 (Bossard et al. 2014), Flowers 102 (Nilsback
Experimental setting:
& Zisserman 2008). CIFARTO/100 (Krizhevsky al. 2009). and EuroSAT (Helber al., 2019).
Evaluation metrics: We focus on image classification and evaluate the performance by accuracy in different training contexts: BP, LR, and SPSA. We compare the performance with and without the query allocation. The GA is employed for all experiments.
Using different gradient estimators, we conduct full-parameters fine-tuning for the Vision Trans- former (both base and large model). We include DeepZero (SPSA with n queries, denoted as n- SPSA), Mezo (SPSA with only 2 queries), and LR with equally allocated query budgets baselines in our experiments. For the SPSA-based methods, we include a version with the optimal allocator (OPS-SPSA) to compare with their corresponding baselines. We apply the same settings to the LR, comparing the optimally allocated version (OPS-LR) with the vanilla version.
We train the network for 10 epochs with the learning rate x 10-4 and the Adam optimizer. The batch size is 128. All the methods in our experiments use the same query budgets, except for Mezo, which uses only 2 queries per data point in accordance with its original memory- settings. As shown in Table I OPS-LR outperforms all other methods. In contrast, Mezo with only query performs poorly in the experiment. On the contrary, DeepZero achieves acceptable accuracy compared with Mezo. The phenomenon suggests that adequate number of queries is crucial for

---

Published as a conference paper at ICLR 2025
Table Classification accuracy (%) for finetuning vit on downstream dataset.
Model
Method
ImageNet
Callech101
Food101
Flowers102
CIFARI0/100
EuroSAT
BP (upper bound)
80.5
92.2
92.4
93.5
96.3/90/
91.9
Mezo (2 queries)
9.3
42.6
37.3
38.2
42.1 37.55
39.8
Mezo (n-SPSA)
54.8
77.2
76.7
80.2
84.4/71.5
78.4
ViT-base
Deep/ero (n-SPSA)
55.6
77.8
78.4
85.6 70.2
78.8
LR OPS-SPSA (Ours)
57.3
85.5
87.6
86.5
87.7 80.8
82.9
60.8
87.3
87.6
85.6
89.5 82.2
83.2
OPS-LR (Ours)
65.8
88.9
88.4
91.6
93.2 88.7
89.3
BP (upper bound)
81.7
93.4
93.3
94.2
98.2 13.5
93.4
Mezo (2 queries)
10.7
45.6
38.8
40.5
38.9
41.7
Mezo (n-SPSA)
56.7
78.8
78.4
78.5
86.7 74.3
79.2
ViT-Large
DeepZero (n-SPSA)
56.4
79.5
78.9
79.6
/
80.1
58.2
87.7
86.8
88.4/81.4
85.7
OPS-SPSA (Ours)
62.2
88.6
88.
87.3
91.3/ 83.9
87.6
OPS-LR (Ours)
67.6
90.2
89.5
92.3
/
90.1
the success of perturbation- bbasd methods since the gradient's variance must be properly controlled. The OPS-SPSA achieves better accuracy than the DeepZero with equally allocated budget. Our proposed optimal allocator provides universal acceleration across all perturbation- Moreover, LR achieves higher accuracy than DeepZero, suggesting that LR is better gradient estimator than the SPSA in this experiment context. Please refer to the Appendix C.I for the details and further analysis.
methods.
5.2 BLACK-BOL -OX TUNING FOR MODEL AS SERVICE
We can tune the prompts for vision-language models (VLMs) in Modevces-a-Service (MaaS) environment using the OPS- LR framework, as shown in Figure - We address the chal- lenge of fine-tuning VLMs without access to model internals or gradient information through a scalable black-bor optimiza- tion approach. We use CLIIP (Rafford al. (021), with em- bedding dimensions of Dr 512 for the text encoder and
Black Box Vision Language Model
Crance
Basoder
Imonder
D, = 756 for the image encoder, as the backbone foundation model. Both the text encoder and the image encoder are kept frozen as black-box modules.
Tunable prefix suffix prompt tokens injected into the text and image token sequences, respectively: ST (ds,Pr,er) er] E R(1+xr+wr)x Dr is the input sequence for text encoder, S eds,er,,pl E p[(+mrtu))xD) for the image counterpart. Previous researches have suggested that large foundation models have low intrinsic dimensions. Therefore, it is plausible to project the original embedding space onto low-dimension subspace: pr = 2T Wr; WT Edy &Dr 2r E Ba xdr and アı = 21 W7; W1 E dd 22 E R xd, WT and W, with a Gaussian distribution. With the projection, our black-box tuning problem is reduced to di- mensions of dr + d, DT D,. The optimization problem, using the cross-entropy loss, takes the form:
Allecator
LR/SPSA
Figure 2: illustration paradigm of tine-tuning the prompt for black- box vision language model.
the projection matrix. The projection matrix is kept frozen after being initialized
Z arg max [((er, er]: 0 [2T Dr, 21 Dyl:-),
(12)
27.21
where Z is the unified formulation of [æT, 27]. By applying the OPS-LR framework, we can opti- mize the black-boo box prompt tuming problems without access to the model structure. We can achieve accuracy of 69.7% 99.7% ImageNet by tuning only few thousand parameters, surpassing the perfor- mance of other black-box methods and Manual Prompting (Radford et al., (02T). The performance shown in Table Please refer the Appendix C for more details.
8

---

Published as a conference paper at ICLR 2025
5.3 ALIGNMENT BETWEEN BLACK- BOX FOUNDATION MODEL
Foundation models like GPT (Brown 2020),
Table 2: Classification accuracy (%) for black- box prompt tuning.
I.LaMa Touvron et al. (2023), Vicuna Chiang
et 2023), and CLIP (Radford al., 2021 con- lain rich domain knowledge from the pretraining. Multimodal tasks, such as video captioning (Kr- Ishna et al. (017) and video grounding Gao et al.
Methods OPS-LR OPS-SPSA
ImageNet
Caltech101
Food101
65.1
90.5
82.7
64.2
89.3
81.5
2.17). require models to have sufficient cross- domain understanding, and proper alignment be- tween different modalities is essential.
LR SPSA
62.5
87.4
79.2
60.7
85.3
77.6
Manual Prompt
57.9
83.3
76.4
Aligning foundation models from single modal-
ity more economical approach than pretraining from scratch using multimodal data. It com- mon practice to add adapter between the visual encoder and the Large Language model. The adapter is a linear projector, g(),, that projects the visual embedding to the textual embedding space. Since foundation models contain billions of parameters, the backward pass through the model quires extra memory for storing the computation graph, and recursive computations through such a large pre-trained model are time-consuming. Our OPS-LR framework efficiently bypasses the need for recursive computation to estimate the gradient with large foundation model in between, as shown in Figure
The training paradigm for the multimodal alignment follows an autoregressive style using image-text pairs 1,7 >. We use a frozen CLIP ViT-L/14 as the visual encoder, denoted as ViT. The CLS tokens of the output sequence of ViT are utilized as the global feature for the frame. We denote the visual token after projection as Z, = g ((ViT(I)CLL) The visual token is then concatenated with the text tokens sequence: 17 (1, l2, ..., mm]. where [f,, 12, ..., [m]] is the text tokens sequence with a length of Consequently, we train the adapter on the concatenated se- quence with the autoregressive objective the LLM. We report the wall time for the feature alignment procedure the LCS- 558K dataset (Liu et al., 2024). Our OPS-LR framework can re- duce almost half of the training time since the recursive backward computation is skipped. From Figure [ the wall time with or without the allocator is almost the same, which further illustrates that our allocator is lightweight and has minimal impact on runtime.
FLOPS
Uar
Lungage Mead
Amuaae OERR
Figure 3: illustration alignment between foundation model for video understanding. Please refer to the Appendix
for more details.
5.4 ABLATION STUDY
We conduct an ablation study using ViT-base on the CIFAR100 dataset. We investigate the neces- sity of the allocation policy for the forward-learning training and determine whether GA BA is the better allocator. Furthermore, we discern the varying degrees of difficulty in estimation across different network components. The results are shown in Figure
Impact of different query budgets. To further investigate the necessity of the procedure of query budget allocation, com- pare the performance increment under various query budgets for different allocation policies. Traditionally, the queries are equally allocated (EA) across different data. The performance improvements offered by GA and BA are considerably more sig- nificant than those of EA. When the number of queries per data small, the benefit from the allocation is still non-ignorable. other words, the more query budget you have, the greater the improvement gains from allocation. Meanwhile, the ablation on different transformer layers indicates that the variance of the gra- dient increases as the layer goes deeper, which validates our sub- sampling technique.
Wall Clock Time
Time oo
SPSA
Figure 5: Wall clock time for feature alignment between dif- ferent methods.

---

Published as a conference paper at ICLR 2025
IA-LR
BA-SPSA
GA-LR
GASPSA
SPSA
codite siilant
Coaftre Simil
CONSTO simils
querics point
querics point
queries point
(a) Key matrix layer-
(b) Key matrix of layer- 12.
(c) FFN layer-1.
C00000 Smilaaty
CNNRro somilaait
84
106
206
306
400
100
200
300
400
100
200
300
400
queries per data point
queries per data point
querics per data point
(d) Key matrix of layer-1. 1.
(e) Key matrix of layer- 12.
(f) FFN of layer-12.
Figure 4: Ablation study on the effect of different allocators and estimation difficulty at different layers. We show the cosine similarity between the estimated and gradients. We estimate the gradient of the Key matrix in multi-head attention (MHA) and the first linear layer in the feed- forward network (FFN)), Layer is adjacent the embedding and the layer 12 is adjacent the classification head.
Impact of different allocators, Gaussian or Bernoulli. We compare different allocators in Figures 4la), (b). a and (e). GA controls the allocation with the mean vectors and the covariance matrix. The covariance matrix captures the similarity between different data points, Structurally similar data points possess similar levels of importance. Therefore, the allocation policy for those data points should be correlated. If the covariance matrix is diagonal, the similarity between data points is ignored, which could undermine the performance of the allocation strategy. Compared with the GA, the BA is simpler strategy. Intuitively, it prunes the queries on unimportant data points to eliminate unnecessary computation. Our ablation study suggests that GA superior to BA.
Estimation on different components of Transformer. We present the cosine similarity results on the multi-head attention (MHA) and the feed-forward network (FFN) Figures 4a-4(c) and (T). Estimation the FFN is easier than the MHA. In the Transformer block, the MHA precedes the FFN, which may explain this phenomenon. The low cosine similarity on MHA attention of deep layers may lead the performance gap large-scale dataset like ImageNet. It is also worth noting that a large number of queries when training Transformer can improve the estimation quality. How- ever, the memory cost of increasing queries is extremely high since the complexity of the attention module is On²)) Integrating efficient MHA techniques, such as Flash Attention (Dao et al. 2022). left for future work.
CONCLUSIONS
In this paper, we present a unified perspective on forward learning through a perturbation-basel framework and propose an optimal query allocation strategy to enhance its efficiency. By leveraging a likelihood ratio-based objective and reparameterized Gaussian allocator, our method adaptively distributes queries based on data-specific gradient estimation difficulty, ensuring an optimal balance between computational cost and estimation accuracy. Theoretical analysis guarantees the optimality of our allocation strategy, while extensive experiments demonstrate its effectiveness in fine-tuning Vision Transformers and addressing real-world black-box optimization problems, such as prompt tuning and multimodal model alignment. Our results show that the proposed method significantly improves the scalability of forward learning, achieving state-of-the--e performance compared to isting approaches. While our method significantly improves scalability, closing the gap with back- propagation remains an open challenge for future research.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Iige Akkaya, Florencia Leoni Ale- man, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, al. Gpt-4 technical report. arXiv preprint arXiv:2303.0877 2023.
Atilim Günes Baydin, Barak A Pearlmutter, Don Syme, Frank Wood, and Philip Torr. Gradients without backpropagation. arXiv preprint arXiv:2202.08587. 2022.
Lukas Bossard, Matthieu Guillaumin, and Luc Van Gool. Food-101-minn discriminative compo- nents with random forests. In Computer vision-ECCV 2014: 13th European conference, zurich, Switzerland, September 6-12, 2014, proceedings, part VI 13, pp. 44.4466611. Springer, 2014.
Tom B Brown. Language models are few-shot learners. arXiv preprint arXiv:2005. 14165, 2020.
Aochuan Chen, Yimeng Zhang, Jinghan Jia, James Diffenderfer, Jiancheng Liu, Konstantinos Parasyris, Yihua Zhang, Zheng Zhang, Bhavya Kailkhura, and Sijia Liu. Deepzero: Scaling up zeroth-order optimization for deep model training, arXiv preprint arXiv:2310.02025, 2023.
Wei-Lin Chiang, Zhuohan Li, Zi Lin, Ying Sheng, Zhanghao Wu, Hao Zhang, Lianmin Zheng, Siyuan Zhuang, Yonghao Zhuang, Joseph E Gonzalez, et al. Vicuna: An open-source chatbot impressing gpt-4 with 90% " chatgpt quality. See https:/vvicua. Imsys. org (accessed 14 April 2023), 2(3):6, 2023.
Tri Dao, Dan Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. Flashattention: Fast and memory- efficient exact attention with io-awareness. Advances Neural Information Processing Systems, 35:16344 2022.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scall scale hi- erarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. 248 255. leee, 2009.
Shizhe Diao, Zhichao Huang, Ruijia Xu, Xuechun Li, Yong Lin, Xiao Zhou, and Tong Zhang- Black-box prompt learning for pre-trained language models. arXiv preprint arXiv:2201.0853), 2022.
Alexey Dosovitskiy, An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010. 1929, 2020.
Jianqing Fan, Yingying Fan, and Jinchi Lv. High dimensional covariance matrix estimation using factor model. Journal of Econometrics, 147(():188-11))) 2008.
Li Fei-Fei, Rob Fergus, and Pietro Perona. Learning generative visual models from few training examples: An incremental bayesian approach tested 101 object categories. In 2004 conference on computer vision and pattern recognition workshop, pp. 178-178. IEEE, 2004.
Charlotte Frenkel, Martin Lefebvre, and David Bol. Learning without feedback: Fixed random learning signals allow for feedforward training of deep neural networks. Frontiers neuro- science, 15:629892, 2021.
Jiyang Gao, Chen Sun, Zhenheng Yang, and Ram Nevatia. Tall: Temporal activity localization via language query. In Proceedings of the IEEE international conference on computer vision, pp- 5267-5275, 2017.
Jiaqi Gu, Hanqing Zhu, Chenghao Feng. Zixuan Jiang, Ray Chen, and David Pan. L2ight: Enabling on-chip learning for optical neural networks via efficient in-situ subspace optimization. Advances in Neural Information Processing Systems, 34:8649 8661, 2021.
Patrick Helber, Benjamin Bischke, Andreas Dengel, and Damian Borth. Eurosat: A novel dataset and deep learning benchmark for land use and land cover classification. IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, 12(7)22217-2226, 2019.
Geoffrey Hinton. The forward-forwart algorithm: Some preliminary investigations. arXiv preprint 2...22222.133455 2022.
11

---

Published as a conference paper at ICLR 2025
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kemel: Convergence and gen- eralization in neural networks. Advances in neural information processing systems, 31, 2018.
Jinyang Jiang, Zeliang Zhang, Chenliang Xu, Zhaofei Yu, and Yijie Peng. One forward is enough for neural network training via likelihood ratio method. arXiv preprint arXiv:2305.08000 2023.
Adrien Journé, Hector Gareia Rodriguez, Qinghai Guo, and Timoleon Moraitis. Hebbian deep learning without feedback. arXiv preprint arXiv:2209. /1833, 2022.
Chia- Kao and Bharath Hariharan. Counter-current learning: A biologically plausible dual network approach for deep learning. arXiv preprint arXiv:2409. /9841, 2024.
Ranjay Krishna, Kenji Hata, Frederic Ren, Li Fei-Fei, and Juan Carlos Niebles. Dense-captioning events in videos. In Proceedings of the IEEE international conference on computer vision, pp- 706-715, 2017.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical report, 2009.
Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. com/exdb/mmist// 1998.
Timothy P Lillicrap. Adam Santoro, Luke Marris, Colin J Akerman, and Geoffrey Hinton. Back- propagation and the brain. Nature Reviews Neuroscience, 21(6)3335-366, 2020.
Haotian Liu, Chunyuan Li, Qingyang Wu, and Yong Jae Lee. Visual instruction tuning. Advances in neural information processing systems, 36, 2024.
Yucheng Lu, Si Yi Meng, and Christopher De Sa. general analysis of example-sclection for stochastic gradient descent. In International Conference on Learning Representations (ICLR), volume 10, 2022.
Wan-Duo Kurt Ma, JP Lewis, and W Bastiaan Kleijn. The hsic bottleneck: Deep learning without back-propagation. In Proceedings of the AAAI conference artificial intelligence, volume 34, pp. 505555055222 2020.
Sadhika Malladi, Tianyu Gao, Eshaan Nichani, Alex Damian, Jason Lee, Danqi Chen, and Sanjeev Arora. Fine-tuning language models with just forward passes. Advances in Neural Information Processing Systems, 36:53038-53075, 2023.
Ali Momeni, Babak Rahmani, Matthieu Malléjac, Philipp Del Hougne, and Romain Fleury. Backpropagation-Fii training of deep physical neural networks. Science, 32966676 2023.
Maria-Elena Nilsback and Andrew Zisserman. Automated flower classification over large number of classes. In 2008 Sixth Indian conference on computer vision, graphics & image processing, pp- 722-729. IEEE, 2008
Arild Nøkland. Direct feedback alignment provides learning in deep neural networks. Advances in neural information processing systems, 29, 2016.
Matteo Papini, Matteo Pirotta, and Marcello Restelli. Adaptive batch size for safe policy gradients. Advances in neural information processing systems, 30, 2017.
Matteo Pirotta, Marcello Restelli, and Luca Bascetta. Adaptive step-size for policy gradient meth- ods. Advances Neural Information Processing Systems, 26, 2013.
Ziheng Qin, Kai Wang, Zangwei Zheng, Jianyang Gu, Xiangyu Peng. Zhaopan Xu, Daquan Zhou, Lei Shang, Baigui Sun, Xuansong Xie, et al. Infobatch: Lossless training speed up by unbiased dynamic data pruning. arXiv preprint arXiv:2303. 04947, 2023.
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International conference on machine learning, pp- PMLR, 2021.
12

---

Published as a conference paper at ICLR 2025
Mengye Ren, Simon Komblith, Renjie Liao, and Geoffrey Hinton. Scaling forward gradient with local losses. arXiv preprint arXiw:2210.03310, 2022.
David E Rumelhart, Geoffrey Hinton, and Ronald J Williams. Learning representations by back- propagating errors. nature, 523(6088):533-536, 1986.
Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and Ilya Sutskever. Evolution strategies as scalable alternative to reinforcement learning. arXiv preprint arXiv:/703.0380 2017.
Bobak Shahriari, Kevin Swersky, Ziyu Wang, Ryan P Adams, and Nando De Freitas. Taking the human out of the loop: A review of bayesian optimization. Proceedings of the IEEE, 104(1); 148-175, 2015.
David Silver, Anirudh Goyal, Ivo Danihelka, Matteo Hessel, and Hado van Hasselt. Learning by directional gradient descent. In International Conference on Learning Representations, 2021.
James C Spall. Multivariate stochastic approximation using simultaneous perturbation gradient approximation. IEEE Transactions on Automatic Control, 37(3)3332-31,, 1992.
Tianxiang Sun, Yunfan Shao, Hong Qian, Xuanjing Huang, and Xipeng Qiu. Black-box tuning for sanguage-mode sooodel-as-a-serviie In International Conference on Machine Learning, pp. 20841- 20855. PMLR, 2022.
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, al. Llama: Open and efficient foundation language models. arXiv preprint S.Xiv:2302.13971, 2023.
A Vaswani. Attention is all you need. Advances in Neural Information Processing Systems, 2017.
Daan Wierstra, Tom Schaul, Tobias Glasmachers, Yi Sun, Jan Peters, and Jürgen Schmidhuber. Natural evolution strategies. The Journal of Machine Learning Research, 15(1):949-98) 2014.
Yihua Zhang, Pingzhi Li, Junyuan Hong, Jiaxiang Li, Yimeng Zhang, Wenqing Zheng, Pin-Yu Chen, Jason D Lee, Wotao Yin, Mingyi Hong, et al. Revisiting zeroth-order optimization for memory-efficient Ilm fine-tuning: A benchmark. arXiv preprint arXiv:2402.11592 2024.
Peilin Zhao and Tong Zhang. Stochastic optimization with importance sampling for regularized loss minimization. In international conference on machine learning, pp. 1-9. PMLR, 2015.
13

---

Published as a conference paper at ICLR 2025
A THEORETICAL DETAILS
A.1 PROOF OF INEQUALITY
P1(()) 2 BA-P(IA Σ
(oL,(0.) - 1 (1
Proof. For each loss function Lj. by exploiting Taylor's theorem, we have
L-(0ct1) - L,(0,) = So ('' L, + T(0++1 0z)) dr
dr
(13)
f (VoL;(0; ( 06)). 0c+1 0t) dr.
By adding and subtracting VoLy((:).
!. (Vo,((0)), 0,-1 01) dr / (VoC, 7 -()) - VoC,(0)). 0011 0i) dr
13
(V.), 0.11 - / (VoL, 7(0+11 0e)) VoL,( 01:1 Oe) dr.
(14)
Now we focus on the second term in 14). By the Cauchy- Sehhay--SShwaazzzeuuuliigg we have (VeL, + T(0++ - 0,)) - VoL, (0t), 0.+1 0,)1 = [1c0:/00-07002-1100---///1111110
And according the L-smoothness assumption, we have
(V + T6.+1 - 8,)) - (e,i( - LIT 8:)1 = - -
Therefore, the second term in (14) becomes
(oL2(00 + - 0.)) VoL,(O.), 0c+1 0c) dt
(15)
//' TT|10+41-16 0.112 dr -
-- -110+11 0
Combining 14p and 15
and substitute 0s+1 = 0g + ne V o ((:)). we have
(, + n V.C(6.) (,)) 2 nh f (0,), vo(())) - V Then, taking expectation over A ~ P(-12) and summing over j.
(o.,(0.) 1 2 (T
PL(A) EA-P(HA) Σ
which completes the proof.
A.2
PROOF OF THEOREM 1
Proof.
B LB, =
1 1 L/| 2(
(ee
(.)) -
i=1
(16)
17t
vol,(0.)) T VoC)(0.)
1 デ" Lll
1 VoL,
E
B
j=1
j=1
where voL,(0.) ~ Nura _e)
and j 1,... B. Then, by taking the conditional expectation.
14

---

Published as a conference paper at ICLR 2025
LB; = EA
B
E
Σ
B
(ol)(0))
voc,)))
2"62
1
Σ
B
(0,)(
/
/
A
B
B
==1
(17)
Vj = 1, ... B, the expected inner product on the LHS of 17
Th
(O,) voC
VoL,
A
The
(OL,(0.).
(18)
B
Next, we focus on the expected squared norm on the RHS of I7
E 2.,
L
||A
1
ΣΣ
B
E
(o,)
(ola(())) (
aa).
(19)
B
For j # k, we have
E VoL,(
A
(m
(m))
PG
(20)
For k, we express (0,) as the sum of the mean and a zero-mean normal random vector:
VoL,(0.) p + Z,
DL
where ~ NO, +/).. meaning Z is a zero-mean random vector with covariance
Then we
A
have
E Vol A = E
(nG + +2)
(mé + +2) A
E
T
P& +2 (uti)
2 - Z A
(21)
|
+ + [2 Z|A]
21) for Z ~ No0, xt
The expected value of the quadratic form Z Z in the covariance matrix, i.e..
A3 ) is given by the trace of
E
2
Tr
G
(22)
A
Therefore, with 20
21
and
22 we have
B
B
19 =
Tr
G
(23)
B
A
1=1
Then, with 17
18 and (3
we have
LB,(A) E EA- A)
(O.)
j=1
(24)
1
1
ΣΣ
B
L B
B
+ j=l
B
Tr
G
Ay
Notice that, 1 is independent of the allocation A, which only depends on the estimator type and the parameters of the injected noise in the perturbation. Therefore, it is easy to see that maximizing the lower bound (B,())
(A) over X E A is equivalent to minimizing
B
JA(A) A EAMP(IN
Σ
TH
(25)
A
1=1
over À E A.
15

---

Published as a conference paper at ICLR 2025
A.3 PROOF OF THEOREM 2
Proof. Based on the optimality of X at step 6, we know that for any GA following (u, E), the corresponding B(LB(A) < [L( Now, if set Σ BxxB. the Gaussian distribution be- comes deterministic, and the query allocation becomes a fixed, non-random strategy. To establish lower bound for E(LB;) E(LB,qua)) we construct optimal deterministic allocator A as the intermediary strategy between A and A equul, which satisfies
B(LB, ((LB( S B(LB)),
where LBdet is lower bound of the PI corresponding to A det.
For the optimal deterministic allocator Adet, we aim maximize the objective function
Tr
(( =
A
subject to the constraint Σ A, Ag- The Lagrangian function is
B
B Σ
L
Ao
A
j=1
where À is the Lagrange multiplier. Take the partial derivative of with respect to each A, and set it to zero.
aL
Tr
A = 0. A3
0A,
Then have
Tr(Dig)
Ag
det
Ao
Σ
Then corresponding objective
ΣP Tr(ZSt) 2
Tr(2
B
Tr(2)))
det)
det)
Σ
A
Ao
j=1
Ao
ER
VTTEE
As for the equal allocator Aqqual
Au the corresponding objective function becomes
Ao
Tr(Stt
B
J. (((auua))
Tr(x)d
B
Ao
1=1
B
j=1
follows that
2
ES V (T(EE))
B
(A equall equula
Tr
Ao
Ag j=1
Notice that
B B
B -
(H / 2
Tr (
Σ
TT(
= =Σ
1=1
1=1
jick
Then
(r(EZ)) (T( 2
Je( (quua)) (A(ee))
Σ
Ao
jck
16

---

Published as a conference paper at ICLR 2025
This difference is always non non-negative and equals zero if and only if all Tr(=g)) equal. Then we have
mi L
B LB
R
(TB
Σ
(Je (oqual) Je (A
2B
(26)
T
m2 L
(T((Z)) - ----VV--- Tr(EE
2
AD
jzk
which completes the proof.
B PSEUDOCODE
Algorithm Perturbation- based training via optimal allocation
Input: Target module (p(:; 0), loss function L(-). dataset X, noise density f()) allocator
P(A[X, b), update interval M.
1: Initialize network parameter 0 and allocator parameter A.
2: repeat
3: f+
4: for one mini-batch B-11 non-overlapping sampled in X' do
5: Compute the loss, C(y), without injected noise.
6: Sample initial queries to estimate Tr
7: repeat
8:
Update the by estimated gradient following until À converges
9:
10:
Sample the allocation decision A ~ P(A|>, b) for the mini-batch. Augment the (.; - according to = -AA,, A2,... An). for 0g E 0 do
11:
12:
13:
Compute the C(yle) with = ~~ f(-) injected to the 0,)
Update O by estimated gradient following (T) or (3) with A queries. end for
15:
t 1.
17:
end for
18:
until network parameter converges.
Output: Network parameter 6.
C EXPERIMENT DETAILS
Platform: All the experiments are conducted on a machine with NVIDIA A800 GPUs. Each A800 GPU has 80GB of memory.
C.I EXPERIMENTS FOR VIT
Datasets: ImageNet: Over 1.2 million images in 1,000 classes, standard large-scale challenge for object classification. Caltech101: 9,144 images across 101 categories, focusing on object recog- nition with varying perspectives and poses. Food101: 101,000 images in 101 food categories, presenting challenges in texture, lighting, and fine-grained classification. Flower102: 8,189 images across 102 flower species, testing subtle feature recognition. CIFAR-10/100 Consisting of 60,000 32x32 images, CIFAR-10 has 10 classes, while CIFAR- 100 has 100 classes, offering challenges in small-scale image classification with increasing complexity in category distinctions. EuroSAT: 27,000 satellite images in 10 land-use categories, challenging models to perform in remote sensing tasks. All the input images resized 224 before entering the ViT backbone.
ViT-base: The base model has 12 transformer layers. The hidden dimension is 786, with 12 heads for the multi-head attention. The intermediate dimension for feed-forward mlp is 3072. 12 layers
17

---

Published as a conference paper at ICLR 2025
equally divided into three groups from bottom to top. The standard deviation of the injected Gaussian noise for each group is initialized as 1 x 10-6, s x 10 10-4, 10-1,1 111 10-3, The query budget for each group is 20 queries per data. The query budget for the classification head is also 20 queries per data.
The large model has 24 transformer layers. The hidden dimension is 1024, with 16 heads for the multi-head attention. The intermediate dimension for feed-forward mip is 4096. 24 layers are equally divided into four groups from bottom to top. The standard deviation of the injected Gaussian noise for each group is initialized as 5 x 10-6, 1 x 10-s, x 10-1, 1, x 10-3, The query budget for each group is 20 queries per data. The query budget for the classification head is 20 queries per data.
ViT-large:
We use the CLS token on lop the Transformer backbone to calculate the cosine similarity between different data points, d in the kernel for reparameterization. The pruned queries for the BA will be equally allocator the other unpruned data points to ensure the total number of queries is the same.
Table 3: Results of ViT-hase under natural noise and adversarial noise.
Natural Noise
Adversarial Noise
Datasets
Methods
Original
Gaussian
Uniform
Poisson
FGSM
I-FGSM MI-FGSM
BP
80.5
78.4
65.9
44.2
15.2
10.9
9.9
ImageNet
OPS-LR
65.8
65.4
65.4
60.3
34.5
15.6
13.8
OPS-SPSA
60.8
58.2
59.3
55.2
33.7
13.5
12.3
BP
92.4
88.3
84.7
66.4
19.6
12.3
10.5
Food101
OPS-LR
88.4
85.3
82.1
70.3
37.2
25.2
18.6
OPS-SPSA
87.6
84.7
80.3
70.4
36.4
23.6
15.3
BP
90.7
83.8
75,2
43.5
18.3
9.3
7.5
CIFARIO0
OPS-LR
88.7
84.3
77.6
52.9
25.4
14.8
12.3
OPS-SPSA
82.2
79.3
76.8
48.2
22.5
13.8
9.4
Furthermore, we assess the robustness of BP, OPS-LR, and OPS-SPSA across three data sets ImtgeNn,,,,,,, Food101, and mary task efficacy: accuracy of classification on unaltered samples (Original): 2) Endurance against natural corruption: accuracy of classification Gaussian, uniform, and Poisson disturbances; 3) Robustness to adversarial attacks: accuracy of classification on samples altered by adversarial tactics, specifically the fast gradient sign method (FGSM), iterative fast gradient sign method (I-FGSM), and momentum-bases iterative fast gradient sign method (MI-FGSM). For adversarial assaults, we cap the allowable perturbation per pixel at 8/255, and for I-FGSM and MI-FGSM, we limit the iteration count to maximum of 5. In our evaluations, we encompass achieves the best accuracy the original data. However, the robustness of OPS-LR and OPS-SPSA superior to BP. Especially under adversarial attacks, the perturbation methods have a significant advantage over BP.
Evaluation of robustness:
three distinct criteria: Pri-
datasets tainted with natural noise, incorporating
entire test set for corruption assessment. As shown Table 3
C.2 EXPERIMENTS FOR BLACK-BIL BOX TUNING
We use the open-source CLIP with ViT-B/32 as the visual encoder. The intrinsic dimension, dr dr. 1000. The visual prompt length is 10 and the text prompt length is 12. The batch size is 64. We use 60 queries per data to tune the intrinsic dimension. We use Adam optimizer with a learning rate of 10-4 and train for 50 epochs with early stopping. All methods the same 16-shot split for training and are evaluated on the full test sets for evaluation.
C.3 EXPERIMENTS FOR MULTIMODAL ALIGNMENT
Vicuma v1.5 7B the Large Language Model and train the 7B version. We train epoch for the feature alignment by an Adam optimizer with the learning rate of 5 x 10 and cosine learning rate decay. The batch size is 64 and the query budget is 60 queries per data.
18

---

Published as a conference paper at ICLR 2025
C.4 EXTENDED ABLATION
BA-RR
BA-SPSA
GALR
GA-PPAA
SPSA
COoDEe Similant
Co0lne simiboriy
Conlre simiburit
230
320
queties per data point
queties per data point
queties per point
(a) Key matrix of layer-1.
(b) Key matrix of layer- 12.
(c) Key matrix of layer-24.
06
0.5
Conlze simlanit
C00000 similantt
Co000e similantt
6.
0.5
60
0.0
00
110
180
quelies data point
quesics data point
Quesics data point
(d) Key matrix of layer-1.
Key matrix of layer-12.
(1) Key matrix of layer-24.
0.5
0.5
costze Siilanty
Cosine Aimiurrty
conine similrity
206
queries per data point
quesies per data point
quesies per point
(g) FFN of layer-1.
(h) FFN of layer-12.
(i) FFN of layer-24.
Figure 6: We show the cosine similarity between the estimated and true gradients. We compare LR and SPSA estimators on the Key matrix of the multi-head attention. The estimation of the feed- forward network is also included. Layer is the Transformers layer adjacent to the embedding and layer 24 is adjacent to the classification head.
We provide more extensive ablation study on ViT-Large following the same setting the main text. Figures 6 (C) and ( show the result of LR and SPSA estimator, respectively. Both the estimators can benefit from the allocation and the Gaussain allocator has better performance than the Bernoulli allocator. The gradient of deep layer like layer is more difficult to estimate than the shallow layer and the corresponding variance accounts for most of the variance of the whole model. Comparing Figures on the multi-head attention. In practice, is recommended to add gradient clipping to the multi-head attention layer.
to D-, estimation the ferd-forward network is easier than
19


Reviews:
[{"review_id": "1L1X9ulxbW", "reviewer": "Reviewer_oVeC", "summary": "This paper examines perturbation-based gradient computation methods tailored for forward-only learning. The authors introduce an optimal sampling strategy based on a Gaussian Allocator designed to maximize performance improvements incrementally. They evaluate this approach using pretrained transformers and demonstrate that it outperforms selected baseline methods.", "questions": "For enhanced clarity, please focus on the weaknesses section, which includes my raised questions.\n\nConcerning reproducibility, I reviewed the supplementary material, presumably the code. However, the absence of a README file and the presence of numerous extraneous files make it challenging to determine which files are essential. Additionally, the provided code lacks meaningful comments and contains a lot of debug information, which further complicates understanding its logic. If the authors aim to demonstrate reproducibility through the attached code, I recommend including a clean version of the code with detailed instructions in a README file to at least guide reviewers through the main logic.", "limitations": "", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "1. The empirical accuracy results for ViT and CLIP appear to surpass those of the baselines. The authors have also conducted essential ablation studies to further validate their findings.\n\n2. While the text in Figures 2 and 3 is smaller than the standard text size, making it challenging to read, the color combinations used in these figures are visually appealing.", "weaknesses": "1. Sections 3 and 4 introduce several undefined annotations, leading to ambiguity in the exposition. For instance, Line 148 mentions a term \"a\" whose role and relation to Equation (1) are unclear—is it a distribution, a hidden representation, or something else? Furthermore, \"G(·)\" on Line 160 and \"y_j\" on Line 164 are undefined, with no clarification of the indexing or distribution from which j is sampled. Additionally, Equation (9)'s term \"K\" lacks a defined scope. The abbreviation \"LR\" is also used without definition. The paper introduces many terms that, while relevant, obscure the main contributions. I recommend a thorough review of these sections to clarify the foundational concepts and distinctly outline the problems the paper aims to solve.\n\n2. The rationale behind formulating the optimization of the query allocator as maximizing Equation (5) is not sufficiently clear. A deeper analysis of this formulation is necessary. Moreover, the paper mentions only the initialization of a Gaussian Allocator, which might suggest a broader applicability than is actually the case. Either a comparative analysis of different allocators should be included, or the focus on the Gaussian allocator should be explicitly stated in the abstract and introduction to manage expectations.\n\n3. I have several concerns regarding the experimental results presented in Table 1, which utilizes a pretrained ViT network. Firstly, the rationale for the notably small number of queries for baseline methods, such as only 2 for Mezo, is not explained. What is the expected number of queries for your OPS-LR model in comparison? In Line 344, you mention alignment with Mezo's original memory-efficient setting, but detailed statistical data on memory consumption and training time for both baseline methods and your approach are lacking. Additionally, the experiments are conducted on pretrained models like ViT and CLIP, but the performance of models trained from scratch is not shown. It is crucial to demonstrate whether OPS-LR offers any advantages over these baselines when applied to models not pretrained. Furthermore, the validation datasets used are generally small, with all except ImageNet containing under 150,000 images. There is also concern that using pretrained transformers on the well-known ImageNet dataset could lead to performance biases due to data leakage.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7g9GgE4LpN", "reviewer": "Reviewer_5nkq", "summary": "The paper introduces FLOPS: Forward Learning with Optimal Sampling, which aims to improve the efficiency of gradient estimation in forward-only learning methods by optimally allocating computational resources (queries) across data points within each mini-batch. The approach is motivated by the limitations of backpropagation, particularly in settings where only forward passes are feasible or desirable, such as in black-box optimization scenarios.  With a simplified proxy objective and a reparameterization technique, the authors derive a novel plug-and-play query allocator with minimal parameters. Extensive experiments show the superior performance of this method. Theoretical analysis is also provided.", "questions": "1. Please refer to Weakness 1. Is it possible to integrate the proposed method into a callable class or function without rewriting model architectures like Linear and Conv2d to implement the specific add_noise operation?\n\n2. Please refer to Weakness 2. Could you provide detailed memory usage for different methods during training for a more thorough comparison? I noticed that the code uses a repeat operation to expand the batch for varying numbers of queries on different data. Does this operation increase memory usage?\n\n3. The authors mention in the main text that 'All the methods in the experiments use the same query budgets, except for Mezo, which uses only 2 queries per data point in accordance with its original memory-efficient setting.' However, could you provide a more detailed comparison of runtime (e.g., clock time) compared to other ZO methods and the BP baseline?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The idea of dynamically allocating different numbers of queries to each data point within a batch during training is novel, which is indeed a point that previous zeorth-order optimization (forward learning) methods have not considered.\n\n2. The proposed method is intuitive. The approach of leveraging a Gaussian Allocator (GA) combined with a likelihood ratio method introduces a creative solution to minimize gradient estimation variance. Through appropriate approximations, the computational cost is effectively reduced. Theoretical analysis is also provided.\n\n3. The experimental setup is extensive and reasonable, and the results are convincing. Both prompt tuning for large models and multimodal alignment for foundation models are promising application scenarios for zeroth-order (ZO) methods, and the proposed approach demonstrates good performance on these tasks.", "weaknesses": "1. Although the authors provide part of the source code, I believe the coding is not advisable. Specifically, the authors override nn.Linear to create a custom Linear class and similarly override nn.Conv2d to create a custom Conv2d class. This approach results in the proposed method being tied to a specific model architecture, making it difficult to adapt to other architectures. In fact, existing zeroth-order optimization methods, such as ZO-SGD [1], ZO-AdaMM [2], and DeepZero [3], all have core optimization logic that can be implemented by inheriting from torch.optim.Optimizer, thereby aligning with gradient-based methods like SGD. Alternatively, they can be integrated into a specific function for easier migration.\n\n2. One important reason why zeroth-order optimization is suitable for large model prompt fine-tuning is that these methods do not require backpropagation, which significantly saves memory compared to gradient-based methods like SGD. However, in the experimental results presented in the main paper, only the fine-tuning results are provided, without comparing their memory usage with backpropagation and other zeroth-order optimization methods.\n\n[1] Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341–2368, 2013.\n\n[2] Xiangyi Chen, Sijia Liu, Kaidi Xu, Xingguo Li, Xue Lin, Mingyi Hong, and David Cox. ZO-AdaMM: Zeroth-order adaptive momentum method for black-box optimization. NeurIPS, 32, 2019.\n\n[3] Chen A, Zhang Y, Jia J, et al. Deepzero: Scaling up zeroth-order optimization for deep model training[J]. arXiv preprint arXiv:2310.02025, 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KpqOyBs4HJ", "reviewer": "Reviewer_HWGc", "summary": "This paper proposes an efficient query allocation strategy for forward-learning algorithms in gradient computation, reducing query usage by focusing on data points that need it most. Using a simplified objective and reparameterization, the authors introduce a lightweight query allocator that minimizes gradient estimation variance with low computational cost. Both experiments and theoretical analysis are provided.", "questions": "1) I am curious about why other methods that utilize all queries would perform worse than this method, that utilizes limited quries for each data.  Since MEZO is tailored to another baseline, using the same hyperparameters might not be entirely fair. Have you considered tuning MEZO with more available queries per data point for comparison?\n2) What is the exact computational cost when using all queries for each data point compared to your allocation method under different budget constraints?\n\nIf reasonable answers are provided, I will consider rasing scores accordingly.", "limitations": "", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) The motivation is clear: optimizing the allocation of queries to effectively reduce computational overhead.\n2) The experimental results show strong performance relative to the baselines.\n3) The study provides both experimental and theoretical results, offering a well-rounded evaluation.", "weaknesses": "1) I am curious about why other methods that utilize all queries would perform worse than this method, that utilizes limited quries for each data. \n2) The comparison of exact computational cost between equally using all queries for each data point and your allocation method is unknown. However, it is one of the main motivation.  \n\nMinor:   \n3) In the abstract, the phrase “propose to allocate the optimal number of queries over each data” isn’t entirely accurate, as a total query budget must be pre-defined rather than learning an optimal number. Perhaps rephrasing to “allocate the optimal number of queries within a set budget” would be clearer.   \n4) Table 2 is not well-formatted and appears misaligned.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "g2A5zQREyu", "reviewer": "Reviewer_dE4A", "summary": "This paper presents an approach for optimizing a differentiable sampler in forward learning in foundation models, supported by theoretical proofs and extensive empirical evaluations. The work lies at the intersection of zeroth-order optimization and sampling optimization.", "questions": "1. **Clarification on LR and OPS-LR**: The distinction between LR and OPS-LR is not clear. More explanation would be appreciated.\n\n2. **Clarification on experiments**: Do the experiments include cross-validation with multiple random seeds? If not, please show the experiment results with multiple seeds with dataset cross-validation. If yes, please provide more details.\n\n3. **Ablation studies**: The proposed algorithms update four parameters. What if only three or two of them are updated? Which parameters are dispensable for this process? Conducting these experiments would provide more insights into the paper's contributions.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 3, "strengths": "1. The empirical evaluation is comprehensive, demonstrating significant performance improvements through query sampler optimization.", "weaknesses": "1. **Overall outline and structure**: The paper builds upon DeepZero and Mezo by devising an optimization allocation for forward learning. However, the idea of optimal allocation is not new in the ML context. Papers such as \"Stochastic Optimization with Importance Sampling\" or \"A General Analysis of Example-Selection for Stochastic Gradient Descent\" (and several derived works) have explored similar concepts. For me, the main difference here is the focus on forward learning (or zeroth-order optimization) rather than backpropagation. The authors are encouraged to: (1) Review and mention this existing research (strongly encouraged) and (2) Compare these methods with their proposed algorithm (encouraged). Addressing these points would strengthen the paper's contribution and contextualize it within the field.\n\n2. **Introduction and framing**:\nThe decision to begin with biologically plausible algorithms (BioPA) seems unexpected and may not effectively frame the paper's contributions. Nevertheless, the general scheme could be unfolded more clearly:\n     1. The citation of Jacot et al. for \"learning high-level representation\" appears unrelated in the BioPA context.\n     2. Consider including more relevant BioPA works such as \"Direct Random Target Projection\" [1], \"SoftHebb\" [2], and \"Counter-Current Learning\" [3]\n\n3. **Writing and proofreading**:\n   - Correct typographical errors (e.g., \"Current Literature\" should be \"Current literature\")\n   - Address factual inaccuracies (e.g., L48 states that the FF algorithm is only capable of training MLPs on MNIST, but results for CIFAR are also presented)\n   - Provide explanations for abbreviations (e.g., SPSA, LR)\n\n4. **Related Work section**: The first subsection could be restructured. When discussing backpropagation-free learning, it's typically in the context of multi-layered neural networks. Also, including evolution theory and particle swarm optimization seem tangential. I suggest reorganizing this section and incorporating the suggested papers for a more focused discussion.\n\nReferences\n\n[1] \"Learning Without Feedback: Fixed Random Learning Signals Allow for Feedforward Training of Deep Neural Networks\" (Frontiers in Neuroscience, 2021)\n\n[2] \"Hebbian Deep Learning Without Feedback\" (ICLR 2023)\n\n[3] \"Counter-Current Learning: A Biologically Plausible Dual Network Approach for Deep Learning\" (NeurIPS 2024)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)