OptEx: Expediting First-Order Optimization with Approximately Parallelized Iterations
Authors: Yao Shu
Jiongfeng Fang
Ying Tiffany He
Fei Yu
Venue: NeurIPS 2024 poster (2024)
Keywords: Iteration Parallelization
First-Order Optimization
Iteration Complexity
Time Efficiency
Primary area: optimization
TL;DR: We introduce the first general framework that enhances the time efficiency of FOO by leveraging parallel computing to directly mitigate its requirement of many sequential iterations for convergence.

Abstract: First-order optimization (FOO) algorithms are pivotal in numerous computational domains, such as reinforcement learning and deep learning. However, their application to complex tasks often entails significant optimization inefficiency due to their need of many sequential iterations for convergence. In response, we introduce first-order optimization expedited with approximately parallelized iterations (OptEx), the first general framework that enhances the time efficiency of FOO by leveraging parallel computing to directly mitigate its requirement of many sequential iterations for convergence. To achieve this, OptEx utilizes a kernelized gradient estimation that is based on the history of evaluated gradients to predict the gradients required by the next few sequential iterations in FOO, which helps to break the inherent iterative dependency and hence enables the approximate parallelization of iterations in FOO. We further establish theoretical guarantees for the estimation error of our kernelized gradient estimation and the iteration complexity of SGD-based OptEx, confirming that the estimation error diminishes to zero as the history of gradients accumulates and that our SGD-based OptEx enjoys an effective acceleration rate of Θ(√N ) over standard SGD given parallelism of N, in terms of the sequential iterations required for convergence. Finally, we provide extensive empirical studies, including synthetic functions, reinforcement learning tasks, and neural network training on various datasets, to underscore the substantial efficiency improvements achieved by our OptEx in practice.

OptEx: Expediting First-Order Optimization with Approximately Parallelized Iterations
Yao Shu #1 Jiongfeng Fang', Ying Tiffany He", Fei Richard Yu i GGangdong Lab of Al and Digital Economy (SZ). China Cooleee of Computer Science and Software Engineering, Shenzhen University, China
$ School of Information Technology, Carleton University, Canada
Abstract
First-order optimization (FOO) algorithms are pivotal in numerous computational domains, such reinforcement learning and deep learning. However, their appli- cation to complex tasks often entails significant optimization inefficiency due to their need of many sequential iterations for convergence. In response, we intro- duce first-order optimization expedited with approximately parallelized iterations (OptEx), the first general framework that enhances the optimization efficiency of FOO by leveraging parallel computing to directly mitigate its requirement of many sequential iterations for convergence. To achieve this, OptEx utilizes a kernelized gradient estimation that is based on the history of evaluated gradients to predict the gradients required by the next few sequential iterations FOO, which helps to break the inherent iterative dependency and hence enables the approximate paral- lelization of iterations FOO. We further establish theoretical guarantees for the estimation error of our kernelized gradient estimation and the iteration complexity SGD-based OptEx, confirming that the estimation eттor diminishes to zero as the history of gradients accumulates and that our SGD-based OptEx enjoys effective acceleration rate O(vN) over standard SGD given parallelism of N, in terms of the sequential iterations required for convergence. Finally, we provide extensive empirical studies, including synthetic functions, reinforcement learning tasks, and neural network training on various datasets, to underscore the substan- tial efficiency improvements achieved by OptEx in practice. Our implementation is available at Intpp::/ thub. com com/youyve/0ptEs
Introduction
First-order optimization (FOO) algorithms, such as stochastic gradient descent (SGD) [W], Nesterov Accelerated Gradient (NGA) [2], AdaGrad [G], Adam [ etc., have already been the comeestone of many computational disciplines, driving advancements in areas ranging from reinforcement learn- ing [S]] to machine learning [6]]. These algorithms, which are widely known for their straightfor- ward form of iterative gradient-based updates, are fundamental in solving both simple and intricate optimization problems. However, their applications usually encounter substantial optimization in- efficiency, especially when addressing complex functions that not only are expensive in evaluating their function values and gradients but also necessitate a large number of sequential iterations to converge in practice, e.g., deep reinforcement learning [ and neural network training [8].
To this end, parallel computing has been widely used the literature to considerably enhance the op- timization (e.g.. time) efficiency of FOO by reducing the evaluation cost of function and gradient per iteration in FOO [[]] For instance, in the field of neural network training, techniques that are based
# Correspondence to: Yao Shu <shuyao @aw.oac.mmm..c.m.......
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

on parallel computing, e.g., data parallelism [8 IQ, I.I. D2 model parallelism [[3,, and pipeline parallelism [T4. IS], have been employed reduce the evaluation time of loss function and parame- ter gradient by processing multiple input samples and network components concurrently. However, to the best of our knowledge, few efforts have been devoted to leveraging parallel computing to reduce the number of sequential tterations required for convergence to mitigate the optimization inefficiency in FOO. Different from the methods of reducing the evaluation time per iteration during optimization, which requires specialized human efforts in a specific domain (e.g., neural network training), the reduction of sequential iterations is likely to be more general since no such specialized domain efforts required and thus shall enjoy a wider application in practice. This underscores the need to explore the potential of parallelizing sequential iterations in standard FOO.
However, the inherent iterative dependency in FOO where the output of each iteration servers as the input of the next iteration, poses a significant barrier to independent and concurrent iteration execu- tion, thereby making it nearly impossible to realize iteration parallelism within standard FOO. To this end, we develop a novel framework called first-order optimization expedited with approximately parallelized iterations (OptEx) that is capable of bypassing the challenge of inherent iterative de- pendency in standard FOO and therefore make parallelized iterations in FOO possible. Specifically, our framework begins with novel kernelized gradient estimation strategy, which uses the history of gradients during optimization to predict the gradients for any input within the domain such that these estimated gradients be used in standard FOO algorithms to determine the inputs for the next few iterations. We further introduce the techmiques of separable kernel function and local his- tory of gradients to enhance the computational efficiency of this gradient estimation (Sec. I. We then apply standard FOO algorithms with this kernelized gradient estimation to determine the inputs for the next N sequential iterations efficiently (namely proxy updates), aiming to approximate the ground-truth sequential updates and bypass the iteration dependency in standard FOO (Sec. (.2).. Lastly, we complete our approximately parallelized iterations for standard FOO by leveraging paral- lel computing with parallelism of N to concurrently execute standard FOO algorithms over these N inputs obtained from our proxy updates using the ground-truth gradients (Sec. H..3).
Apart from proposing our innovative OptEx framework, we further establish rigorous theoretical guarantees and extensive empirical studies underpinning its efficacy. Specifically, we give theoret- ical bound for the estimation error of our kernelized gradient estimation. Remarkably, this error ap- proaches zero asymptotically as the number of historical gradients increases, ranging across broad spectrum of kernel functions. This suggests that our kernelized gradient estimation can facilitate effective proxy updates to help parallelize sequential iterations in FOO (Slc.5..l). Building on this, we delineate both upper and lower bounds for the sequential iteration complexity of our SGD-based OptEx, showing that our SGD-based OptEx is able to reduce the sequential iteration complexity of standard FOO algorithms at a rate of @ ((VN) with parallelism of N (Sec 5.2). Finally, through ex- tensive empirical studies, including the optimization of synthetic functions, reinforcement learning tasks, and neural network training on both image and text datasets, we demonstrate the consistent advantages of our OptEx in expediting existing FOO algorithms (Sec. B).
To summarize, our contribution to this work includes:
To the best of our knowledge, we are the first to develop a general framework (i.e., OptEx) that can leverage parallel computing to approximately parallelize the sequential iterations in FOO, therehy considerably reducing the sequential iteration complexity of FOO algorithms.
We provide the first upper and lower iteration complexity bound for SGD-baser OptEx, which gives an effective acceleration rate of @(VN) with parallelism of N.
We conduct extensive empirical studies, including the optimization of synthetic function, rein- forcement learning tasks, and neural network training on both image and text datasets, to support the efficacy of our OptEx framework.
2 Related Work
Reduction of Iteration Complexity. In the literature, various techniques have been developed to enhance the optimization efficiency of FOO by improving their sequential iteration complexity. For example, variance reduction strategies [IG 17 [X] have been proposed to accelerate stochastic opti- mization by effectively reducing the gradient variance and therefore aligning the iteration complexity of SGD with that of gradient descent (GD) in expectation. These strategies usually yield significant

---

improvements in high-variance problems whereas their compelling performance is hard to extend low-variance scenarios and deterministic contexts. Meanwhile, adaptive gradient methods, e.g.. AdaGrad [G], Adam [+], and AdaBelief [[19], have been introduced to employ an adaptive learning
rate for retter-performing optimization where fewer iterations are required for convergence. Fur-
thermore, acceleration techniques like the Nesterov method [2] and momentumm-asee updates [20] have also been proven to be capable of reducing the sequential iteration complexity for GD and SGD efficiently. Orthogonal to these established methodologies, our paper introduces parallel computing as a distinct and innovative strategy to further decrease the sequential iteration complexity of FOO. Of note, such an approach not only stands independently but also offers potential for synergistic integration with existing methods, promising enhanced optimization outcomes.
Reduction of Time Complexity Per Iteration using Parallel Computing. In the realm of enhanc- ing the computational efficiency of FOO, parallel computing has emerged as a rescue by reducing the time complexity per iteration in FOO. Particularly in the field of neural network training, data parallelism [&. IIΑ, ML [2]] has been introduced to evaluate the gradients of model parameters w.r.t mini-bated input samples simultaneously. In addition to data parallelism, model parallelism [[3]] has been developed to process various neural network components concurrently. Furthermore, pipeline parallelism [044 [S] divides the neural network into stages and assigns each stage to different device, allowing different stages of the computation to be executed in parallel across the pipeline. However, the tailored nature of these methods constrains their application to wider contexts. Contra- dictory to these case-specified solutions, this paper proposes a general framework that can leverage parallel computing to enhance the optimization efficiency of FOO in wide practical applications.
3 Problem Setup
In this paper, aim to enhance the optimization efficiency of the following stochastic minimization problem by leveraging parallel computing with parallelism of N: min OER
F(0) - E [
(1)
Here, (f( is assumed to follow a specific Gaussian distribution, i.e., ( ~ (N(FF())
for any 0 R., which has already been widely used in the literature [21. LR Besides, adopt a common assumption that V F' is sampled from a Gaussian process, i.c., VF GP K(--))
[24 P5 26 Of note, (II) has found extensive applications in practice, e.g., neural network training and reinforcement learning [28]. Importantly, although our primary focus is on this stochastic optimization, our method can also be applied deterministic optimization (evidenced in Sec. I.
[27]]]
Standard FOO algorithms commonly optimize (I) in an iterative and sequential manner:
0z+1 = FO-OPT V (O,))
(2)
where is the iteration number. Ideally, if parallel computing can be used to parallelize the sequential
iterations in FOO (i.e., to execute several sequential iterations simultancously), it will be able to lead to noticeable improvement in its optimization efficiency since fewer sequential iterations will be required for convergence. Unfortunately. there is an inherent iterative dependency in standard FOO, that is, the output of each iteration (e.g., 0,) is the input of the next iteration t ++ 1. Such an iterative and sequential process makes it nearly impossible to attain 0, and 0,41 concurrently, and therefore parallelize the iterations for established FOO algorithms.
4 The OptEx Framework
To this end, we introduce the first general framework in Algo. with a detailed illustration in Fig. MI namely first-order optimization expedited with approximately parallelized iterations (OptEx), to overcome the aforementioned inherent iterative dependency FOO and facilitate the realization of parallelized iterations therein. To achieve this, we first propose a kernelized gradient estimation with the technique of separable kernel function and local history of gradient to efficiently and effectively estimate the gradient at any input in the domain (Sec. I.. We then follow standard FOO algorithms with this kernelized gradient estimation to approximate the inputs for the next N' sequential iterations to be parallelized (Sec 2 aiming to overcome the inherent iterative dependency in FOO. Lastly, we finish our approximately parallelized iterations by leveraging parallel computing to run standard FOO algorithms on these N inputs concurrently using the ground-trute gradients (Sec. 3
3

---

Algorithm 1: OptEi
Process
Process 2
Process 3
Process N-E Process
Input: FO-OPT, k(.,' ). 0.. T. N, g Ø
0-1
for sequential iteration & [T] do
Peal
2.
Initialization: 0,,0 f 0
He Helfee)
Oza
Update (6) using
with g
NNN-2
VF(O
for proxy step E N do
0
DLN-1
5
0..0 - FO-OPT @ c.. 2 ( (..1))) for process E [N] in parallel do
0,00
vs(o
6
0
Sample f to evaluate V f(O
PEN-
oe
8
0, - FO-OPT(O,,..) 1-11 v.((0..--)
g t 9 (.0.((0....
10
0g
(M)
Figure 1: An illustration of OptEx at iteration
4.1 Kernelized Gradient Estimation
As mentioned in our Sec. E VF is assumed to be sampled from a Gaussian process, i.c., VF GP(O, K(.-)) with kernel function K. Then, for every sequential iteration t of Algo. II conditioned on the history gradients during optimization g A {(O,, (f(e,))== Nu--)) VF then follows the
posterior Gaussian process: VF ~ GP (2(+): E (..)) with the mean function (4((+) and the covariance function (; .) defined as below
(24):
(0) - v (0) U,, + t vec(G.),
(3)
-1 (0, 0') A K (0,0) v. (0) (U, (U,+ V, (0')
where vec(.) vectorizes a matrix into a column vector, G, A [V(0,)) M(t-1) a x N(I - 1)- dimensional matrix, V Vi((0) (0) & [K O, - is a adxx N(t 1)d-dimensional matrices, and U, K( 0.))) M(t-1) is a 1)d N(t d)dddiimesionnl matrices. We therefore propose 7.r'r
use (.))) estimate the gradient any input Rd that is,
((())= 14 (0),
(4)
and covariance (0) - (0,00) to measure the quality of this gradient estimation in a principled way, which will be further theoretically supported in our Sec. 5.1l
However, for every sequential iteration of Algo. with (L), will incur a computational complexity of (t - 1) d))) along with a space complexity of O 1)d). Practically, this presents a requiring substantial number
significant challenge in scenarios with large input dimension of sequential iterations for convergence, such as neural network training
[S]. To mitigate these complexity issues, we introduce two techniques: the separable kernel function and the local history of gradients, to reduce both the computational and space complexities associated with our kernelized gradient estimation, thereby enhaneing its efficiency and practical applicability.
Separable Kernel Function. Let K(--)) -) = k(;;)) where k(:,)) produces a scalar value and is
a d x d identity matrix, and define the N(t - 1 diimensional vector k. (0) [k(0 0,) 0,), and N - 1) x (tt - 1) dimmensiona matrix K, [i<(O,, 0,,) (1 ((-11) 11 we can prove that the Gaussian process in (5) can simplified as the Gaussian process in Prop. I.I (line of Algo. MI..
Proposition 4.1. Ler K(..) k(.,)) I, the posterior mean and covariance in (L) become
(,( [ kr (0) (K,
(K, + +00+) G.
(0,00') k(00 0') k. (0) (K. (K. +o'l) b1(0)))
We slightly abuse the notation f to denote the different functions that are randomly sampled per iteration and (0,, vf(0)) to denote historical evaluation till sequential iteration with parallelism of N.

---

Its proof is in Appx. Prop. shows that with a separable kemne function ((.,)) = k(-.)) I, the multi-output Gaussian process in d-dimensional space can be effectively decoupled into d inde- pendent single-output Gaussian processes. Each of these processes results from the same scalar ker- nel function ki leading to a uniform posterior form shared by all these processes, i.e., the expression
-i in (0) and k(O, -k, (0) K, + +² (,'))) in (0, This thus ky (0) K, -
considerably diminishes the computational complexity, now quantified as O( N(-)))) resulting in a more computationally efficient gradient estimation in practice.
Local History of Gradients. Conventional FOO algorithms predominantly operate by optimizing within a localized region neighboring the initial input 0, [2%]. This therefore indicates that our Algo. I only requires precise gradient estimation within local region. In this context, the use of local gradient history is posited as sufficiently informative for effective kernelized gradient estimation, which can be supported by the theoretical results in [S0] and the empirical evidence in Sec. B As a result, rather than relying on a complete gradient history. we propose to use a localized gradient history of size T, that neighbors 9 to estimate the gradient A. This strategic modification results in substantial reduction of computational complexity to O + Tod) well corresponding decrease in space complexity to (T,d). which is especially beneficial in the situations where To is considerably smaller than ((t- 1) for E [T].
4.2 Multi-Step Proxy Updates
The ability of our kernelized gradient estimation to provide gradient estimation at any input 0 then enables the application of a multi-step gradient estimation. This helps to approximate the inputs for the next N sequential iterations 10,++)= NN11 to be parallelized in standard FOO, given Or. Specifi- cally, in the context of our Algo. M. for every sequential iteration E [T], by employing a first-order optimizer (FO-OPT), we can approximate the inputs required by our parallelized iteration in Sec. B. sequentially as below through our multi-step proxy updates (line 4-5 of Algo. M...
r FO-OPT(00..-1: (4 (Ot,s-)) Vs E [N-
Intuitively, these proxy updates imitate the sequential iterations standard FOO by using only the estimated gradients in our Sec. I. We will show that these proxy updates can provide a reasonably good approximation of the ground-truth updates in Sec. 5.II Meanwhile, despite the iterative and sequential nature of (S), our proxy updates based operations on relatively small-sized matrices (refer to the Prop. I) will still be able to provide significantly enhanced computational efficiency compared to the ground-trun updates based on expensive evaluation of function values and gradients in complex tasks, like neural network training. This effectiveness and efficiency of (5) thus render an essential foundation for achieving parallelized iterations and improved the optimization efficiency FOO.
4.3 Approximately Parallelized Iterations
Upon obtaining the inputs (0,.-1)a== for the next N sequential iterations be parallelized, then finish our approximately parallelized iteration by executing standard FOO algorithms over each of (0.,-11) N based on the ground-trun gradients {V (0, ()), in parallel (line 6-9 of Algo. MI
see also the processes in Fig. II.. That is.
0 = FO-OPT(B,, (),,,.))) Vi E [N]
After that, the final input 0. = (N) will be used in the next sequential iteration (line 10 of Algo. II.. Of note, central to the approximately parallelized iterations in our OptEx framework is the necessity
of evaluating the gradients (V)(0,..-)) ==1 in our Algo. II These evaluations in fact play pivotal roles in reducing the estimation error of our kemnelized gradient estimation and consequently im- proving the performance of our OptEx by augmenting the gradient history near the input 0, with N more evaluations, which will be supported by the theoretical results in our Sec. El and the empirical evidence in our Appx. BR
Theoretical Results
To begin with, we formally present the assumptions mentioned in our Sec. E as below.
5

---

Assumption 1. Vf(0)- (F follows N (0.0²1) for any 0 R..
Assumption 2. VF is sampled from a Gaussian process GP (O.K(:))) where K(..)) -)I and |k(0, 0) S x for any 0 E R.d
Note that the Assump. has already been widely employed in the literature [211 22 23). Meanwhile, it is also common to assume that is sampled from a Gaussian process [24 BTJ implying that VF follows Gaussian process as well [2] AS
[G] (Assump. Eb, i.c., V can be any function in this prior. The inclusion of a separable kernel function in Assump. @ aims to enhance the efficiency of kernelized gradient estimation in Sec. I and simplify theoretical analyses below, whereas our conclusions apply to non-separable kernel functions as well by following our proof techniques.
5.1 Gradient Estimation Analysis
Following the principled idea in kernelized bandit [32, 33 and Bayesian Optimization 34 3 we define the maximal information gain as below
In
max (0, (0.R"
I (vec(( G.,); vec v.))
where T(veo(G,,) (.,); veel v.,) the mutual information between G, [(O)))] and V, [VF(O,)] In essence, 7n encapsulates the maximum amount of information about V that can be gleaned from observing any set of n evaluated gradients, represented as G,,, which is known to be problem dependent measure that is highly related to the kernel function k(+, [32]] Built on this notation, we then provide the following theoretical result for our gradient estimation.
Theorem 1 (Gradient Estimation Error). Let ô E (0, and - d (vd + 1) (n(//)) Given
Assump. M let [ To for any sequential iteration t in Algo. II then for any 0 E K with probability of at least - 5,
4 max o Jmi.
F[V) (0) V a
Σー [0) where (K (x+1/o2) 20 S [0)
Tod
The proof is in Appx. global fulfillment of Assump. D is not a prerequisite. That the assumption that VF sampled from GP K) within a local region will already be sufficient for our kernelized gradient estimation in Sec. 4 to achieve accurate gradient estimation practice. Our Sec. f will later evidence this empirically. Thm. II with upper bound on [=)
It is important to note that since FOO pertains to local optimization, the
illustrates that the efficacy of our kernelized gra-
(v (VTT./To) This means that if Tr,/TT will asymptotically approach zero w.r.t. To. the error of our kernelized gradient esti- mation method will become significantly small given a large number of evaluated gradients To- This consequently facilitates the effectiveness of our proxy updates in (5)) built our kernelized gradient estimation to approximate the ground-truth updates when [ is sufficiently large. Meanwhile, Thm.
dient estimation in the worst case will enjoy a polynomial error rate of O
M with lower bound on Σ² (0)) illustrates that our kernelized gradient estimation in the best case may achieve an exponential error rate of O efficacy of kernelized gradient estimation in Sec. and proxy updates in Sec.
which thus further elaborates the
is important to note that the ratio Too has been demonstrated to asymptotically approach zero for range of kernel functions, evidenced in existing literature [G5]. This therefore underpins the establishment of concrete error bounds for our kernelized gradient estimation where notation Ö is applied to hide the logarithmic factors, delineated as follows:
Corollary (Concrete Error Bounds). Let k((.)) be the radial basis function (RBF) kernel, then
(F( (,)())l = 0
Let ()(,,)) be the Matérn kernel where v is the smoothness parameter, then
[VF(()) n4, (0)) = Ō = (To11(2++d((411))

---

Cor. elucidates that with kernel functions such as RBF and Matérn kernel, the eπror in our kernel- ized gradient estimation indeed will diminish asymptotically w.r.t. Ty- That is, as To increases, the estimation error || (0)) 14, (0)) decreases and consequently the proxy updates in (5) become closer to the ground-truth updates. It important to note that this reduction typically follows non- linear trajectory, suggesting that the effect of an increasing To on our kernelized gradient estimation diminishes when To is reasonably large. This consequently affirms the reasonability of our utility of local history for gradient estimation in Sec. I. which leads to not only accurate but also efficient gradient estimations.
5.2 Iteration Complexity Analysis
We first introduce Assump. & which has been widely applied in stochastic optimization [I66. [6] to underpin the analysis of sequential iteration complexity of our OptEx framework.
Assumption 3. F is L-Lipschitz smooth: ||VF(0) - (F(O')l S l 0') for any 0, 0' R.
To simplify the analysis, we primarily prove the sequential iteration complexity of our SGD-based OptEx where we use min+g(NT) (0+)ll to denote the minimal gradient norm we can achieve within the whole optimization process when applying OptEx with '' sequential iterations and parallelism of N for a clear and fair comparison with standard SGD. Notably, our analysis can also be extended to other FOO-based OptEx by following similar proof idea.
Theorem 2 (Upper Bound). Let 6 E 10, A F(0) inf. F(0), B - max o²) and p -
187T + NV. Under Assump. D-3 by choosing T N 2AL, (1- x) TTo for our SGD-based Algo. II with probability of at least 1 - 6,
V NLTO"P and [g] = To 1
24
No
|FFO S 20V 22
48 ln(1228)
min STTSSN
+ NT
(8)
NT
The proof of Thm. is in Appx. Of note, our Thm. D with N aligns with the established upper bound for standard SGD, as discussed in [5G]] Importantly, our Thm. D elucidates that with parallelism N > 1, our SGD-based OptEx algorithm can expedite the standard SGD by a factor of at least /N/p. where 1/p quantifies the impact of the error introduced by our kernelized gradient estimation. This efficiency gain can be further amplified the accuracy of our kernelized gradient estimation increases (i.e., a decrease in p). which can be achieved by augmenting the number To as discussed in our Sec. 5.1l In addition, Thm. D also demonstrates that for fixed learning rate 7), there exists a constant NNmax: c.g., .Nuxx = 2 (n LT 2 p) in Thm. A the parallelism N should roughly remain below to ensure the fastest convergence of function F to a stationary point. In contrast, if N exceeds N maxx our SGD-based OptEx will underperform due to the increased gradient estimation error. This observation is further supported by the results presented in Appx. B. However, when the learning rate 17 is relatively small (e.g., during fine-tur mee-uuing in practice), the parallelism N can be significantly larger to achieve a further improved speedup.
Theorem 3 (Lower Bound). Let å E (0, A A F(0) - info F(O), B A max o²}, and 2 1 and E 1/),, 3 A (in(x/(r + 1/02)70-1 1- ,a). Then, for any L > 0, O, 2 1,7
there exists F on Rd (Vd do 0 (3/(AL") (T satisfying Assump. D-G and having the following with a probability of at least - 8 when applying SGD-bbased Algo. M with | = To 1,
do min 3,1)
min S
[F((0.))
>
(9)
AVNT
The proof of Thm. is in Appx. Note that when N =1 1, Thm. N aligns with the recognized
lower bound for SGD, as elucidated in [37]] Thm. E illustrates that, with parallelism of N, our SGD-based OptEx can potentially accelerate standard SGD by up to VN /N/(K/(O" (0 )). under the condition that k/(1+1/o1 11/02) S min 1, a²). This upper limit in fact corresponds with the lower bound of the variance in our kernelized gradient estimation, as established in Thm. M. Essentially, the agreement between Thm. and Thm. B, the aspect of parallelism N, demonstrates the tightness of our sequential complexity analysis for SGD-based Algo. II Finally, the combination of Thm. 2 and Thm. enables us to specify the effective acceleration that can be achieved by our WGD-basce OptEx tightly, as shown in our Cor. 0 below.
7

---

Optinality Gup (log scalo)
Ackley (d= 10*)
Oprimality Gap (log scale)
Ackley (d= 10")
Optinality Gap (log scale)
Sphere (d 10")
Optinality Gap (log scale)
Rosenbrock (d 10
.66 Vanilla
.60
Vasilla
-6.
Vasilla
Vauilla
Target
Tuget
Target
Tanget OptEs
OptEs
26
-
OpiEs
OptEs
0000
X-X. X.K. X.xxx.y
xx MoKiyiggng Minko
4
1
dese.
-4-
20
40
20
40
20
40
20 Sequential lirrations (2)
40
Sequential Iterations (I)
Sequential lterations (2)
Sequential Lterations (I)
Figure 2: Comparison of the number of sequential iterations T (I-axis) required by different meth-
ods to achieve the same optimality gap F(0) inf, F(0) (y-axis) for various synthetic functions.
The parallelism N is set and each curve denotes the mean from 5 independent runs.
Corollary 2 (Acceleration Rate). With parallelism of N, the effective acceleration rate achieved by our SGD--used OptEx over standard SGD is O(vN)
6 Experiments
In this section, we use extensive experiments to show that our OptEx framework can considerably enhance the efficiency of FOO with parallel computing, including synthetic experiments (Sec. B.
reinforcement learning (Sec. (..)) and neural network training on various datasets (Sec. k.
6.1 Synthetic Function Minimization
Here, we utilize synthetic functions to demonstrate the enhanced performance of our OptEx frame- work compared to existing baselines, including the standard FOO algorithm, namely Vanilla, and FOO with ideally parallelized iterations, namely Target, which ideally but impractically utilizes the ground- gradient to obtain the inputs for the iterations to be parallelized. More specifically, the Vanilla baseline is equivalent to Algo. M with parallelism of N = 1, and the Target bascline is equivalent to Algo. I with μr (6,,.-1) being replaced with V f( indicating the desired parallelized iteration aim to approximate. We have also provided comprehensive illustration of these baselines in Appx. B. and detailed experimental setup applied here in Appx. B.2.1.
The results in Fig. 2 with o² and N = 5 have demonstrated the efficacy of our OptEx frame- work for deterministic optimization (i.e., o² = 0). Specifically, Fig. D shows that OptEx consis- tently achieves notable speedup in optimization efficiency measured by the number of sequential iterations, which is at least 2x more efficient than the Vanilla baseline, when optimizing with parallelism of N 5 to reach an equivalent level of optimality gap. This is roughly in line with the result of our Cor. El implying the validity of our Cor. Q Mcanwhile, although our OptEx framework slightly underperforms the Target bascline, such phenomenon is in fact quite reasonable since the Target baseline can leverage the ground-truth gradient whereas OptEx relies on the kernelized gradient estimation with estimation error bounded in Thm. to parallelize sequential iterations. This also aligns with the insight from our iteration complexity analysis in Thm. 2 Overall, the results in Fig. have provided strong empirical support for the efficacy of our OptEx in expediting FOO, as theoretically justified in our Sec. 5.2. We also present a number of ablation studies as well as analy- ses Appx. BK to examine the effects of different components in our proposed OptEx framework on its effectiveness.
6.2 Reinforcement Learning
We proceed compare our OptEx framework with previously established baselines under various reinforcement learning tasks with different parameter dimension d from the OpenAl Gym suite [[8]. with the deployment of DQN agents [[9]] Here, the parallelism parameter set to be N 4 and a detailed experimental setup is provided in Appx. B.2.2 The results are presented in Fig. B. As illustrated in Fig. E the integration of parallel computing techniques, including Target and OptEx, considerably outperforms the traditional Vanilla baseline in terms of the optimization efficiency quantified by the number of sequential iterations. More importantly, amongst these methodologies, OptEx consistently demonstrates more stable and superior improvement on the optimization effi-
8

---

Comulative Avernge Reward
Cartpole (d== 17410)
Contalative Averngo Reward
Acrobot (d = 17795)
Cammlative Avenage Keward
Lunar lander (d- 18180)
Cumnlative Avenge Rewred
Mountain car (d 4547)
100
Ar .8--8
-200
-75
-185
75
-300-
-100-
xc. de
Virrts
-125
-8-
Terei
20 20-00---100 -00- 06
-400
Oves
25
-200
50
100
50
100
50
100
50
100
150
Sequuential Everatioss (I)
# Sequential Iverations (T)
&Sequential Iterations (I)
Sequeential Everations (T)
Figure 3: Comparison of the cumulative average reward (y-axis) achieved by different methods to train DQN on RL tasks under various parameter dimension d and a varying number of sequential episodes T (r-axis). The parallelism N is set to 4 and each curve denotes the mean from 3 indepen- dent runs.
0.8
Thain Loss (logg seale)
1.2
Vasill Tarpet
Taaio Loss (log scale)
1.2
Vanilla
Target
0.70
Opels
Optix
Optix
Test Error
-B-
OpeE
1.1
1.1
0.65
1.0
1.0
0.6
x
0
500
1000
50
75
250
500
100
200
Sequential Iterations (T)
Wallelook Time (Sec.)
&Sequential Iiemations (7)
Walleloek Time (Sec.)
(a) CIFAR-10 (d = 2412298)
(b) Shakespeare Corpus (d (d= 1626496)
Figure 4: Comparison of the test eгror or training loss (y-axis) achieved by different optimizers when training deep neural networks on (a) CIFAR-10 and (b) Shakespeare Corpus with a varying number T of sequential iterations or a varying wallclock time (r-axis). The parallelism N is set to 4 and each curve denotes the mean from (for CIFAR-10 10) or (for Shakespeare corpus) independent runs. The wallclock time is evaluated on a single NVIDIA RTX 4090 GPU.
ciency compared with other baselines, which consequently well corroborates the efficacy of OptEx in improving the efficiency of established FOO algorithms. Interestingly, our OptEx framework can even enjoy improved efficiency over the Target baseline where the ground-truth gradient V (-) applied. This is likely because the gradient variance (i.c., (0)]l) in our OptEx framework can asymptotically approach zero by using a large number of history of gradient (refer to our Sec. I. whereas the gradient variance in the Target baseline remains the same.
6.3 Neural Network Training
At last, examine the efficacy of our Optlix in expediting the optimization (i.e., training) of deep neural networks, specifically for image classification and text autoregression tasks. Specifically, we apply our OptEx and the aforementioned baselines to (a) train 10-layer MLP model (d = 2412298) with residual connections [+I] on CIFAR-10 10 [III], and (b) train an autoregressive transformer model (d 16264466 borrowed from the Haiku library [|2]] on a curated collection of works from Shake- speare with parallelism of N = 4. Comprehensive details for the experimental setup are provided in Appx. [3.23]] and the final results iterations and wallclock time are used to quantify the optimization efficiency of different optimizers. Intriguingly, as evidenced by Fig. OptEx consistently outperforms Vanilla by large margin in terms of both training and testing errors across the image and text datasets, given an equal number of sequential iterations T' or alternatively the same wallclock time budget. Remarkably, the efficiency of OptEx approaches that of the theoretically ideal algorithm the Target baseline, which there- fore further verifies the efficacy of our OptEx framework. More results are in Appx. B.L Overall, these empirical results have well verified the capability of OptEx in significantly expediting FOO algorithms as justified by our theorems in Sec. 5, even in the context of deep neural network training.
illustrated in Fig. El where both the number of sequential
7 Conclusion
In conclusion, our OptEx framework represents a significant advancement in FOO. By leveraging kernelized gradient estimation to enable approximately parallelized iterations, OptEx effectively re-

---

duces the number of sequential iterations required for convergence and thus addresses the traditional inefficiencies of FOO. Theoretical analyses and extensive empirical studies validate the reliability and efficacy of OptEx, confirming its potential to expedite optimization processes across various applications. Of note, limitation of OptEx is the additional storage and computational cost intro- duced by the kernelized gradient estimation, which we aim to mitigate further in the future work.
Acknowledgments and Disclosure of Funding
This research is supported by the Guangdong Lab of Al and Digital Economy (SZ) under the Guang- ming Laboratory Genius Nova Programme (Award No: 24410002).
References
[1] Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of math- ematical statistics, pages 400-407, 1951.
[2] Yurii Evgen' evich Nesterov. method of solving a convex programming problem with conver- gence rate o |bigl(k2) (bgggr))))ig)). In Doklady Akademii Nauk, volume 269, pages 543-547. Russian Academy of Sciences, 1983.
[3] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. JMLR, 12(7), 2011.
[4] Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. Proc. ICML, 2014.
[5] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. "XXi:1707.06347,, 2017.
[6] Guanghui Lan. First-order and stochastic optimization methods for machine learning, vol- ume 1. Springer, 2020.
[7] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Toannis Antonoglou, Daan Wierstra, and Martin A. Riedmiller. Playing atari with deep reinforcement learning. 1rXiv:1312.5602, 2013.
[8] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton. ImageNet classification with deep convolutional neural networks. In Proc. NIPS, 2012.
[9] Mahmoud Assran, Arda Aytekin, Hamid Reza Feyzmahdavian, Mikael Johansson, and Michael G. Rabbat. Advances in asynchronous parallel and distributed optimization. Proc. IEEE, 2020.
[10] Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu. Hogwild!: A lock-free approach to parallelizing stochastic gradient descent. In Proc. NeurlPS, 2011.
[11] Volodymyr Mnih, Adrià Puigdomènech Badia, Mehdi Mirza, Alex Graves, Timothy P. Lill- icrap, Tim Harley, David Silver. and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In Proc. ICML, 2016.
[12] Hao Yu, Sen Yang, and Shenghuo Zhu. Parallel restarted SGD with faster convergence and less communication: Demystifying why model averaging works for deep learning. In Proc. AAAI, 2019.
[13] Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Quoe Le, Mark Z. Mao, Mare' Aurelio Ranzato. Andrew W. Senior, Paul A. Tucker, Ke Yang, and Andrew Y. Ng. Large scale distributed deep networks. In Proc. NIPS, 2012.
[14] Aaron Harlap, Deepak Narayanan, Amar Phanishayee, Vivek Seshadri, Nikhil Devanur, Greg Ganger, and Phil Gibbons. Pipedream: Fast and efficient pipeline parallel don training. arXiv preprint (al::1886003777 2018.
10

---

[15] Yanping Huang, Youlong Cheng, Ankur Bapna, Orhan Firat, Dehao Chen, Mia Xu Chen, Hy- oukJoong Lee, Jiquan Ngiam, Quoc V. Le. Yonghui Wu, and Zhifeng Chen. GPipe: Efficient training of giant neural networks using pipeline parallelism. In Proc. NeurIPS, 2019.
[16] Ric Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive vari- ance reduction. In Proc. NIPS, 2013.
[17] Kaiwen Zhou, Fanhua Shang, and James Cheng. A simple stochastic variance reduced algo- rithm with fast convergence rates. In Proc. ICML, 2018.
[18] Othmane Sebbouh, Nidham Gazagnadou, Samy Jelassi, Francis R. Bach, and Robert M. Gower. Towards closing the gap between the theory and practice of SVRG. In Proc. NeurIPS, 2019.
[19] Juntang Zhuang, Tommy Tang, Yifan Ding, Sekhar Tatikonda, Nicha C. Dvoreek, Xenophon Papademetris,, and James S. Duncan. AdaBelief optimizer: Adapting stepsizes by the belief in observed gradients. In Proc. NeurIPS, 2020.
[20] Yanli Liu, Yuan Gao, and Wotao Yin. An improved analysis of stochastic gradient descent with momentum. In Proc. NeurIPS, 2020.
[21] Rui Luo, Jianhong Wang, Yaodong Yang, Jun Wang, and Zhanxing Zhu, Thermostat-asiisted contimoousl--emmpreed Hamiltonian Monte Carlo for bayesian learning. In Proc. NeurlPS, 2018.
[22] Fengxiang He, Tongliang Liu, and Dacheng Tao. Control batch size and learning rate to gener- alize well: Theoretical and empirical evidence. In Proc. NeurIPS, 2019.
[23] Yixin Wu, Rui Luo, Chen Zhang, Jun Wang, and Yaodong Yang. Revisiting the characteristics of stochastic gradient noise and dynamics. KXiv:2109.09833., 2021.
[24] Carl Edward Rasmussen and Christopher K. I. Williams. Gaussian processes for machine learning. Adaptive computation and machine learning. MIT Press, 2006.
[25] Yao Shu, Zhongxiang Dai, Weicong Sng, Arun Verma, Patrick Jaillet, and Bryan Kian Hsiang Low. Zeroth-order optimization with mrajectory-infomma derivative estimation. In Proc. ICLR, 2023.
[26] Yao Shu, Xiaoqiang Lin, Zhongxiang Dai, and Bryan Kian Hsiang Low. Federated zeroth- order optimization using trujectoryiifoomed surrogate gradients. arXiv:2308.044 00088.00077... 2023.
[27] Ian J. Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, Cam- bridge, MA, USA, 2016.
[28] Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018
[29] Léon Bottou, Frank E. Curtis, and Jorge Nocedal. Optimization methods for large-scale ma- chine learning. SIAM Rev., 60(2):223-31 2018.
[30] Armin Lederer, Jonas Umlauft, and Sandra Hirche. Posterior variance analysis of Gaussian processes with application average learning curves. arXiv:1906.01404, 2019.
[31] Zhongxiang Dai, Yao Shu, Bryan Kian Hsiang Low, and Patrick Jaillet. Sample-then-optiiiz batch neural Thompson sampling. In Proc. NeurIPS, 2022.
[32] Sayak Ray Chowdhury and Aditya Gopalan. On kernelized multi-armed bandits. Proc. ICML, 2017.
[33] Zhongxiang Dai, Yao Shu, Arun Verma, Flint Xiaofeng Fan, Bryan Kian Hsiang Low, and Patrick Jaillet. Federated neural bandit. In Proc. ICLR, 2023.
[34] Sayak Ray Chowdhury and Aditya Gopalan, No-regret algorithms for multi-task Bayesian optimization. In Proc. AISTATS, 2021.

---

[35] Niranjan Srinivas, Andreas Krause, Sham M. Kakade, and Matthias W. Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. In Proc. ICML, 2010.
[36] Zijian Liu,, Ta Duy Nguyen, Thien Hang Nguyen, Alina Ene, and Huy Nguyen. High probabil- ity convergence of stochastic gradient methods. In Proc. ICML, 2023.
[37] Yoel Drori and Ohad Shamir. The complexity of finding stationary points with stochastic gradient descent. In Proc. ICML, 2020.
[38] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. OpenAl Gym. 16Xiv:1606.0155 2016.
[39] Volodymyr Mnih, Koray Kavukeuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 518(7540):529-53 -333, 2015.
[40] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proc. CVPR, 2016.
[41] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers features from tiny images. Technical report, Citeseer, 2009.
[42] Tom Hennigan, Trevor Cai, Tamara Norman, Lena Martens, and Igor Babuschkin. Haiku: Sonnet for JAX, 2020.
[43] Beatrice Laurent and Pascal Massart. Adaptive estimation of a quadratic functional by model selection. Annals of Statistics, pages 1302-1338, 2000.
[44] Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning From Theory Algorithms. Cambridge University Press, 2014.
[45] Yann LeCun, Corinna Cortes, and CJ Burges. MNIST handwritten digit database. ATT Labs [Online]. Available: htlp://yann.lecce lecul. cotuum.cm//exub/miis... 2, 2010.
[46] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-Mnist: A novel image dataset for benchmarking machine learning algorithms. 17X7v 2017.
12

---

Appendices
Appendix A Proofs
A.1
Proof of Proposition 1.1
Recall that we have defined ki [k 0,) - and K2 - 1k(O,, 0, 0-)), --r''11 Let @ denote
the Kronecker product, by introducing the fact that K(.') = -((.)) into v, (0) and U, from the Gaussian process posterior (3), we have that
(0) 0, k(0,0,)I
k(0, 0 0, k. (0) I.
(10)
Similarly,
k(0,,0,)I
0,01,
0(0,,0,-11)
U, 0,),
k(00,00,11 0,)1
K, & I.
(11)
k 0 0,-1)
By introducing the results above into the posterior mean and variance in (E), we have
(0) U, +0 vec(G,))
(4(())
[ (0) & 1) K, (1++01)) ve
@ (KT( (0) 1) K + I
(ec
@
(k. (0) 8 1) (K [K:+
vec vec (G)
(12)
(c)
k (0) K, + +
2 @1) vec G _
G. ky (0) K, + +01) -1]
(f)
vec
(g)
[ k (0) (K, + o²)) G2
where (c) come from the bi-linearity of the Kronecker product, i.e., (A (A+B) B) C = ACC+
while (d) is from the inverse of the Kronecker product, i.e.. (A @ B) A -1 8 B- In addition. (e) is due the mixed- -roducct property of the Kronecker product, i... (A () (BD), and (f)) results from the mixed Kronecker matrix-vector product of the Kronecker product, ie., (A & BC) vec(BCA))
(AC) X
Similarly,
(0,00) K (0,0') (0) (U, + o²1)
T (0)
( k(0 0')1 ([ | [0) K, + +021) 81) (k,(0') 1)
(13)
g k(0,0)1
A (0) (K, + +0'1 (,()))
@ (k(0,0) k (0) (K, + 021) -1 k,()0)
13

---

where (b) comes from the result in (I2), (c) results from the mixed-product property of the Kro-
necker product and the fact that k (0) K, + o²T) k,((0) a scalar. This finally concludes
our proof.
A.2 Proof of Theorem III
To begin with, we introduce the following lemmas:
Lemma A.1
Let Ç ~N, and E (0,1) then
P (15112 S SV @d++2(VV+ () ln
21 81
(14)
Lemma A.2 (Lemma 2 in Appx. of [+ For any R and any matrix A, the following hold
I-A (AA +o-1) A o -A
(15)
Lemma A.3 (Sherman-Morriso formula). For any invertible square matrix A and column vectors u, suppose A + uv is invertible, then the following holds
(A + uv
=
=
A
uv
A
(16)
1
1
A
u
Lemma A.4 (Non- (Non-Incraasing Variance Norm). Define variance E. & (0,
0)
with being
the number of gradients employed to evaluate the mean and covariance Prop. Then for any E IRd and n 2 1,
1 [ -
(17)
Proof. We follow the idea in [E and [AS] prove it. Specifically, firstly define k(0,0') (0)) <(0") and Φn A (o(0,))=_ Then the matrix K, in Prop. I. can be reformulated
K, Φ
(18)
and based the definition of 4b a Φ + I
2 (8)
(0) (0) - x(0) on 0n on + +o4) -1
2 250(0))
(
((0) T I- Φn ( + o²1)
11 2(0)
(19)
(c)
0 (0)
(Dr + -021) ((0))
(d) (2 (() T क- (p,))(0))
where (c) comes from Lemma by replacing the matrix A in Lemma AW with the matrix &
14

---

As result,
0 (0)) T Φb (00)
o o') 00 00000 )(0)) I
@
④ nn (0-100000000000000 o' o0)
((0)
(0)(0) Φ -1 n- 0 2 (1 (1+ ((0)) x 1 ((,)))
(00) 1 0,.10 (
()_1(((0) v0(0))
(c)
E (0) - o² (1 (1+ ((0,) T - (00,) 6(0) T x (0,)0((,) - 61)1
E (0)
(20)
where (6) is due to the fact that L, 2b 4 - 2 + ((O))((O,)) and (d) is from Lemma Finally, (f) derives from the positive semi-definin property of +b 1 (0)))) - and $ leading to the conclusion of our proof.
Lemma A.5 (lower Bound of Variance Norm). Following the definition in Lemma for any E IRd and n 2 1,
[0)
2 (ıs + 1/0²)
1
|
- 1
(21)
Proof. Again, we follow the idea in [44 and 225 to prove it. we first prove the following inequality
+ n- (00))
1/2
O..)
1/2
((0))
+ 1/2
((0,)
((0m)
((0,)) (00)((0,)
(22)
(d)
S 0 (()(),)) T((0))
(e)
x no²
where (c) comes from the fact that .n.- 4 n + <0
16 (0_1
T xn ... I and
(e) is due the fact that ((0,)) ((,,) k(,,,, 0,) S K.
Then, based on the reformulation of Σ (0) in (20). we have that
> (0) (a)
o(0))
o (0)
④ n- + (0,)
(b)
2 (0)
1/2
I 1ー 1/2 ((,))((0,,) x-- 1/2
Φ -2120(1)) I
(23)
(c)
a²
6()) TΦ 11 1
x
+ kd
(d)
D (0)
1 Kō
where (c) comes from (2)) This finally concludes our proof.
15

---

Lemma A.6 (Information Gain), Define G, _ (V V. å [VF(O))) and K, & [ 0 Uy) 1,==1 The information gain I(vec( G,); vec vn) has the following form with As- sump. D
[vee((Gr)) vec V..) (ee((..)). - d In (det(I+ +o kk,))
(24)
Proof. Based our Assump. II E. the following holds respectively:
vec(Gnn) vec Vn) ~ (O o² Ina) and vec(G,,) ~ GP (o, (K, + (on, 0
(25)
Due to the fact that H(z) = (n((ee((2TTE)) if M(, Σ). the following holds
[vvec(G,)) vec V n)
H (vec(G,,) H (vec(G,,) vn))
(
det 2 K,, + I²r
② (I))
2 In dot (IT
(c)
In det (2Tee (Kn, + I ] (det (za))*)
In (det (27ea
2
2
(d) 1 det(2Te(K, + I,,)
In
2
dct(2 Inn
(e) In (del([++ 3Kn) (Kk()
2
(26)
where (a) comes from the definition of information gain, (b) derives from the results in (EAS), and (c) is due the fact that det A B) (A)) (det(B))" given the a-dimensional matrix A and x b-dimensional matrix B. In addition, (e) follows from det(AB-) 1) det(A)/ det (B). This then concludes our proof.
Lemma A.7 (Sum Variance). Define the maximal information gain
in
max (0, 1a CR2
[v,eeGG,); v.))
(27)
the following then holds
20² mm
Σ x0
(28)
d
Proof.
To begin with, we show the following inequalities resulting from the matrix determinant
lemma:
det (0 dot ( =(0))(0)())
(29)
det (Φ;) (1 ((0) Φ; 6(0)
16

---

Given S 0², since
E (0)
<
_ 0 - s
|
[k(0,0) _ R from
Lemma
4 we then have ((
6 S 1. As result,
( Φ 6(0)
In 1 + 510) p, 60)
det(
In
d
1=0
( o² In (
del((P))
(30)
( T + +
(c) o In
det(o
( 2 In
(letto=='000 T + 11
( 0² in (dct(I+ +o 0 - Φn))
(N) 20 20-2 In
where (a) follows from the reformulation of > (0) in (I9). (6) results from the fact that x/2 S In(1 + x) for any x E (0, 1), (c) derives from (29). (d) is from the telescoping sum, (e) is due the
fact that (et( = (e I). (f) is from the fact that (AB ) = det (e)(())) (A) det (B), (g) comes
from the Sylvester's is determinant identity, i.e., det( = det(K; + I,) according to the definition of e, and (h) results from the fact that K,, 0 on in (H)) the conclusion in Lemma A. and the definition of Yn.
Following the same idea, given 2 have
20
(
Φ (0))
2k
2x
In
1+
6 4 o(0)
(31)
In
[1 5(0)
x. 9-(0(0)
2%m
Combining the results in and (1), we conclude our proof by
1
Σ 0 =
4 max(R, My dn
(32)
12
0
Proof of our Thm. M Since Σ (0) [m,, (0) VF ~ I(O,I,). according to Lemma A.I. for
any E (0, 1) and a 2 + 2( 7 + (n(5)), with a probability of at least - 8,
(V - n. (0) Σ ( ( (0) VF(0)]
(33)
Va 2 10)
17

---

where (a) is from CauchySchwarz inequality and (b) is from Lemma A. By introducing the results
Lemma A.5 and Lemma A.7 into the result above and letting To n + 1, we conclude our proof.
A.3 Proof of Theorem
In general, follow the idea in [[36] to give high probability convergence for our OptEx algorithm. To begin with, we introduce the following definition and lemma.
Definition A.1 (Sub-Gaussian Random Variable). A random variable X is g-sub-Gaussian exp (xxx))
exp (A²o²) AA such that ||| S J.
Lemma A.8 (Bound for cab-Gaussian Random Variable). Suppose a t-suub-aussiie random
variable, then for any a E R, 0 s b S 2n'
exp ax + +xxx2) S exp (a² (1o2+ 63)00 +))00²++))
(34)
Proof.
(0)
x²
E exp
[x xxx²)
E
exp
a 200 +
402 + boxx²
exp ((1
exp
(a'o²) 2
E
40 + b²
x²
(35)
(a'o²) exp ( 10 + b² 0²
exp
exp (a + b 63)0²²
where (c) comes from the definition of o-sub-Gaussane random variable.
Proof of Thm. D Define
Σ (0,,, 0rwi ifs < N -1 if = N 1,
(0,,,) &
2
(36)
VF(( (4,(0...) if < N -
E(Or,))
(F((O..)) VV((O..)) ifs 11,
and
1 2
X1,0 A w n1(1 - (L-LLL/F(().. 1, (e ( +
| (0 1)l
2
(37)
2 || 2
According to our Lemma A.E and the fact that each dimension of (f(.s) follows an independent Gaussian distribution given Assump. D, the following holds
T
N
VF wii-L
E
exp
ΣΣ
X
< exp
Σ
w (1)²
o 02((0,.-1)
Ei 1 m
2 - / VF ,==)) 20)20000000000000000 (0 +
t=1
N
Wi 2
L
exp
Σ
0
10-000)))00 1/2
2
(38)
18

---

Based on Markov inequality, we have that
N
1
T
wij 2 I.
0 ( (0:--1))
P
exp
r,s
exp
28
2
1=1
I
exp
2 Ex=1 N
X1.s)
(39)
-== Ex=1
wri Lo 11)8-1)12) /(26)
exp
Therefore, with a probability of at least
1 8,
T
N
T
N
wnj L
(
o²( 20 + In
(40)
2
28
which leads to the following inequality with w = w
T
LLL
r11 - (L)EL,,)(()...))) (,0.0--))),,,000--111 +
(0,
2
I 0² (0
1
wi (1-2(11
(F
(0
+ In
26
(41)
Of note, for every proxy step based on SGD:
F(O,,))
(a)
F((0,.-))) VF VF(( 0c,5-1) + L
110 -0,, 02,0-11 1|
2
( F(O F 6 ( (VF((,, (0,,,-)))) +
17
2
(c) F(0 + - -, +
1²L 2
|
222L 2 ||,(00,0-2)]
(42)
where (a) derives from the Lipschitz smoothness of function F (i.e., Assump. B. (b) comes from the standard SGD update and the definition of (O,,,, and (d) a rearrangement of the results in (c).
By introducing the results above into and choosing w 2,81 with B A max(n, o2), we have
F(O + (1))(1-1)880(00-1111 n111 ) |V(O0..-))]
F
F(O
s=1
1=1
I²L 0 (0 )
1
1
+ + In
2
28
F(O + (bir1 -1T.)² -1((1
nL
\V)00.))))
2
I2L 2 20 ((0..--)) + 2n
28
F(0 !! VF
21 02 (
2 (0.,--1)
+ 2.3 In
1
25
(43)
19

---

where (a) comes from 17 - 1/L, (6) is due to the fact that 02(00,0-1) S max o²} = B_ and (c) due to the fact that
" 2 (1 nT)2² - 11(1
n/
2
"
2nI + 11 1²² 2 + nTL,)
2
11
17² L 12 -1)
(44)
2
} 49
By rearranging the result in K and defining 2 (1
+ 1
N. we have
o'Tod
UL ΣΣ
48
(F(Og) -F(0))))))
(0t.--1)
In
NT
NNT
NT
NT
s=1
F(O0) - inn F(0)
+ nLppo" 2 +
48
In
NNT
NT
25
(45)
where the last inequality comes from the fact that F(Or) S inf F(0) and o²
4,,r// (Tod) (333)
where A A F(O,) inf, F(O), conclude our By choosing T 2 24L and 1 NTLo'p proof.
No
Remark 1. The speedup achieved by OptEx matches that of basic sample averaging (i.e., data par- allelism) for stochastic optimization with noisy gradients. However, the speedup from OptEx comes from reduced sequential iterations (first term on the RHS in (9.)). while sample averaging derives from reduced gradient variance (second term on the RHS in (4.S) When gradient noise is already
small in deterministic optimization (e.g., the experiments in Sec. I.),), data parallelism may not provide noticeable speedup. but OptEx can still contribute significantly. Overall, OptEx works in a complementary direction to existing parallelization methods, including sample averaging, to speed up first-order optimization, especially when other methods are not applicable or underperforming as discussed in our Sec. 2)
A.4 Proof of Theorem
We follow the idea in [5n prove Thm. G. We first introduce the following lemma:
Lemma A.9 (Lemma B. 12 in then
Let X; ~ 1)) independently, Z & Σ X² and c E (0,
P S (1 c)m) & exp (- ne
(46)
6
Proof of Thm. B. When n [1/(VTT)),1/ We consider the function
F(0) = ||0|
(47)
where 0 is initialized with //00 AT).
We abuse e(0,) to denote the e0,,.-1) defined in our (36). Based on the update rule of stochastic gradient descent, we then have that
0, 0,-1 - 1) + e(),-)))
+
(1 (1-nL))0-11 (E
(48)
T-1
-[-nL))0 00000 + Σ
111 TL)
--i-1 -0,))
= -
i=0
20

---

Since E(0,) follows O0
(0,)) independently where we abuse (0,) to denote the (0(,
defined in (6G) and 0g is initialized with (O,, I),,, then have that
0 ~ 00 (0.(1) (1 (n-
(0,
A L Σ (/ ((1-m
)0) o2(0.) 1 1
(49)
Let 5 E (0, 1) and = min min[1/11+/00> }² since | )1² - === by introducing the results above into Lemma A. with 1/2 and d 2 do _ 24 BNTnNN/88) with a probability of at least 1- 8,
NT
min TE(TT]
|VFO,)) 1
Σ
|F
NT
dL2
(1 (1=n
7² n-) n1) ())) 22)
2
L
dl?
(1 n1)
+
11 n n 2(r
2
L
1=0
dL
A
1 (1 (1- 1²²
(1 (L-
+
2
L
1- 1- (1-1)
(50)
(1 nL) AL + (1 (1- (1-(1-7Z)) -))))
11
2
2 nL
LL
min
AL,
2
2 1
3
IV
2
min
AL, 2/NT
dg min
AL, 3
IV
Nv
When E [0.1/VVTTI] we consider the function
F(0)= max {1/L. DAT 17
0 [Te, e1
(51)
VVs max (1/L NT 11 7). 0, ... .0.
where 0, is initialized with 0 Similarly, have
7-1-1
1 0, max {1/L, Σ 1
0
7-1
Σ
17
1
1
s(0)),
E/
NN m
1=0
2
max
(52)
and
0, ~ No (11- max
2(r-i-1)
[-1
Pn
Σn
2
o²(
{1/1,, Em!
1=0
2max
111,,,.1 1)
(53)
21

---

Therefore, let e denote the first element of 0,, we have
NT
E
0
(a)
1
AA
max
1/L, Σ T
{ 11/L, NNT 11
2max
(b)
AA max
1/L, Σ exp
NT
In
1 NT
Σ
"1
(54)
11/L, - 11
max
(c) 1
{1/1. 1/L, Σ "
NT
dA max
where (b) comes from the fact that - 2/2 2 exp(In(1/2)a) for all = [0, 1]. In addition, we have
2(7-1-1)
(
n²
1
1
o² 1 ))
1/L1, >NT
k 0
max
11
1
(55)
1 B
1=0
8
1,2
where 3 a max }²}.
Let V denote the CDF of standard normal distribution and follow the idea [37]] by choosing
163/LL
1 1 (1
5 1/L, プm= 77
d > do A
NT
(8/1A11))
(56)
A max
then
(
((L))
dA max (1/L, EAT n)
P
V0713
var
(
dA max {1/I. DAT 1)
(57)
2 P
var (00)
1B/L2
- NT8.
That is, with a probability of at least - 8/(NT),
NT
(1)
dA max
1/L,
Σ 7
(58)
22

---

Since |VF(0,)] =
0 T e:
2
we conclude our proof by applying union
max ( 1/1,>0 m
bound on (58) as below
NT [VF(0,)]
min TE[NT]
NT Σ
VF(())]
d,
(59)
4 max
1/L, D 7)
dg AL
NV
where the last inequality comes from the fact that proof.
[0, [/.1/() This finally concludes our
23

---

Vanilla
OptEx
Target
Process
Process 1
Process 2
Process
Process N-I: Process
Process
Process
Process
Process N-1 Process N
Rel O22
P)(()s)
OLN-2
VS(05))
Pc
x B
pre
vrco 2)
8 co)
6 22
o S
vece S
6
(K-1))
e
e (N-1)
e e
pre
Figure An illustrated comparison among our OptEx and all the baselines iteration
Appendix B Experiments
B.1 Baselines
In this section, we provide an illustrated comparison between our OptEx and all the baselines at iteration in Fig. S Notably, the Target baseline represents an ideal parallelization of the Vanilla baseline. However, this is impractical because the ground-truth gradient (i.e., ff()) required by process [N] to produce the update can not obtained before the start of this process. More specifically, this gradient is the outcome at the end of the corresponding process. In contrast, our Op- tEx framework makes use of the kernelized gradient estimation (i.e., (²(()) to achieve approximated parallelized iterations for FOO as illustrated in our Fig. E, which is more practical and useful.
B.2
Settings
B.2.1
Optimization of Synthetic Functions
Let input 0 = 10.1=1 the Ackley, Sphere, and Rosenbrock functions applied in our synthetic exper- iments are given below, which have been slightly modified compared with the standard ones.
d
1 Σ cos (2m0,)) + 20 + exp(1), (Ackley)
F(0) = - exp
0.2,
7
Σ
00
exp(
7
d 8. (Sphere)
(60)
F(0)
d i=1
F(0) = Σ
- + + -8,)3. (Rosenbrock)
Note that both Ackley and Sphere function achieve their minimum (i.e., min F(0) 0) 0" 0. whereas Rosenbrock function achieves its minimum (i.e., min F(0) = 0) at 0 1.
In this experiment, the parallelism of N 5 is applied and all the baselines introduced in Sec. b. as well as our OptEx are based on Adam [4]] with learning rate of 0.1, 3, = 0.9, and 33 = 0.999. In addition, we employ Matérn kernel- based gradient estimation in OptEx with T, 20.
B.2.2 Optimization of Reinforcement Learning Tasks
Our experimental framework is built on the Deep Q-Network (DQN) algorithm, outlined in [39].
and implemented within the OpenAl Gym environment [38]. This study investigates the effective- ness of different optimizer configurations across classical discrete control tasks provided by Gym.

---

Rosenbrock (d 10")
Rosenbrock 10")
Rosenbrock (d 10")
Rosenbrock (d 10")
Opcimalit Cap sale))
Optinality Gapp Olog suale)
Optnnality Gap Clgg soals)
Optinality Ghip (log soals)
*e Oytashesive
* Ope' (fees)
* Gptl mi
26. Unita 31
-9 Oyei (las)
CytEx um
OyE B)
12
Optii (prd))
OytEx -20
OyEEx
Optba (25
(X 201
7
-
x
10 15
10
Sequential Inerations (I)
Sequential Eterations (T)
Sequencial Iterations (2)
Sequential Iterations (
(a) Parallel vs. Sequential
(b) Choice of 0g
(c) Varying To
(d) Varying N
Figure 6: Ablation studies on the Rosenbrock synthetic function.
Each trial is conducted on a dedicated CPU to maintain consistency in computational conditions. The DQN architecture consists of dual fully connected layers, with 64 or 128 neurons tailored to each task's requirements. Hyperparameters, including a learning rate of 0.001, a reward discount factor of 0.95, and batch size of 256, are applied for fairness and consistency across experiments.
Performance evaluation of the optimizer-enhanced DQN agents is systematically carried out over 100 to 200 episodes per game, employing an e-greedy policy with minimum epsilon of 0.1 and an exponential epsilon decay with rate of 2 1500 A preliminary warm-up phase of either 30 50 episodes, depending on the task, is incorporated to stabilize initial learning dynamics. Besides, all baselines introduced in See 6 and our OptEx are based on Adam[E]] with learning rate of 0.001, 3 = 0.9, and B2 = 0.999. For OptEx, we utilize a Mat' ern kernel-based gradient estimation, with To 150 to accommodate the variance in RL tasks, and parallelism of N is applied.
B.2.3 Optimization of Neural Network Training
In this experiment, we compared our OptEx with other baselines using both image classification and text autoregression tasks. Here, we simply make use of the jax. vmap function to simulate parallel computing and measure the wallelock time for each sequential iteration. We believe that the time efficiency of our OptEx can be further improved when it is more properly implemented on a parallel computing platform. Besides, reduce the computational cost of our kernelized gradient estimation in these nigh-dimensional optimization problems, we propose to use randomly sampled subset of dimensions (e.g.. d = 10 for image classification and d = 108 for text autoregression) from the total d dimension to compute the kernel value k(.,,) each sequential iteration of our OptEx.
Image Classification. In this image classification task, train a 9-layer MLP (including input and output layer) with skip connections on MNIST [ES], Fashion MNIST [46] and 10-layer MLP (including input and output layer) with skip connections on CIFAR-10 [IJ datasets, which have parameter size of d = 978186 for (fashion-JMNIS") and d = 241 2298 for CIFAR-10. Both our OptEx and other baselines are based on SGD [M]] with learning rate of 0.001, a batch size of 512, and parallelism of N = 4. For OptEx, we employ a Matérn kernel-based gradient estimation with To 6.
Text Autoregression. In addition, we further train a simple transformer from Haiku library [22] with parameter size of = 1626496 on the corpus of "Hany Potter and the Sorcerers Stone" and a subset work from Shakespeare. In both tasks, all the basclines introduced in Sec. b and our OptEx are based on SGD [M]] with a learning rate of 0,01, batch size of 256 and parallelism of 4. For OptEx, we employ Matérn kernel-based gradient estimation, where To 10.
B.3 More Results
Ablation Studies on Synthetic Function. To better understand our OptEx algorithm, we have conducted number of ablation studies on the Rosenbrock synthetic function with a dimension of == 10a The results are in Fig. G. which there are 4 different types of comparisons: (a) We have compared our OptEx with vs. without evaluating the intermediate gradients, i.e., (V](0.,-)))= N- at every iteration I, denoting as parallel and sequential respectively in Fig. (a). which aims to
25

---

Train Eroor (log seaks)
-36- Vosilla -Gh
Test Error (log scale)
Vouila
Train Eroo (log scale)
-1.0
-K6- Varila
Erroe (log scale)
-1.0
-00 Vasill
-Ga Tarpe
=+ Opslis
- OptEx
Oyt's
-1.5
-2.-
-2.0
thret www.eoo................... %
-2.5
-2.
1000
500
1000
100
200
100
200
# Sequential htentions (T)
Sequential Iterations (T)
Wallclock Time (Sec.)
Wallelock Time (Sec.)
(a) Sequential Iterations
(b) Wallclock Time
Figure 7: Comparison of the train and test еπrог (i.e.. 1 accuracy in log scale for y-axis) achieved by different optimizers when training MLP with residual connections on MNIST dataset with (a) a varying number I of sequential iteration and (b) a varying wallclock time (z-axis). The parallelism N set to 4 and each curve denotes the mean from independent runs. The wallelock time is evaluated on an AMD EPYC 7763 CPU.
(log seale)
-30 Vasila
Tea Eiror (log seale)
0.5
-ge- Vaulla
Eroo (log scale)
1.00
-We Vieita
Ten Ereer (log sale))
Vanilla
Taepe
-B Tarpet
-
Optli
1.25
-1.2-
-1.0- +
1,50
-1,4
-1.5-
1.5
-1.6-
-175
500
1000
500
1000
100
200
Sequestial Itentiions (?)
Sequential Iteratioss (T)
Wallelook Time (Sec.)
Wallelock Time (Sec.)
(a) Sequential Iterations
(b) Wallclock Time
Figure 8: Comparison of the train and test error (i.e., 1 accuracy in log scale for y-axis) achieved by different optimizers when training MLP with residual connections on the Mashion-MNISS dataset with (a) a varying number T' of sequential iteration and (b) varying wallclock time (z-axis). The parallelism N is set to 4 and each curve denotes the mean from 5 independent runs. Similarly, the wallelock time is evaluated on an AMD EPYC 7763 CPU.
show the importance of these intermediate gradients on accurate gradient estimation and therefore improved convergence of our OptEx as justified in our Sec. E.A. (b) We have compared our OptEx using different principles to choose O, from (0((),) J,-.
(0(0) Ti=1, including using function value (denoted as
func in Fig. B (b)) via 0₂- = arg min "= 1 f(0), using from the process N (denoted as last
in Fig. E (b). i.e., the standard principle in Algo. II) with 0, e())) and using gradient norm (denoted as grad in Fig. B (b)) via 6, = arg min (e() y.
[[ (c) We have compared our OptEx with varying To in Fig. R (c). (d) We have compared our OptEx with varying N in Fig. R (d). All the other experimental settings follow from the same ones in our Appx. B.2.I.
The results presented in Fig. (a) indicate that evaluating intermediate gradients (V)(0.,-)) at each iteration t crucial for achieving better convergence with our OptEx. This improved per- formance likely stems from these evaluations being more aligned with the gradient approximations required at point in our OptEx, which is essential to achieve accurate gradient estimation and therefore well-performing convergence in our OptEx. Consequently, these findings underscore the importance and necessity of line 7 in Algo. MI as discussed in Sec. A.3. Further, Fig. IB (b) shows that utilizing 0 from the final process N (denoted as last) where 6, o..²) typically results in marginally better convergence. This approach maximizes the benefits of parallelism within N pro- cesses, unlike the other methods which often operate under reduced parallelism due to constraints in optimizing 0(^7) Additionally, Fig. f (c) reveals that maintaining a gradient history length of To < 10 generally improves convergence. Extending To beyond 10, however, does not significantly improve outcomes, which thereby validates our theoretical insights from Sec. 5. Finally, Fig. (d) shows that increasing the number of processes when N < 10 improves the iteration complexity of our OptEx. However, as N increases to 20, convergence deteriorates. This observation aligns with the theoretical insights in our Sec. 5.2 which posits that while increasing N up to optimal point Nap: And (LToo) p) enhances convergence, further increases can degrade performance.
26

---

0.8
-06- Vesslla
0.8
-96- Vasilla
-20- Vorill OytE
-96- Vinlla
Train Etree
-8- Teyas
-o- Opticx
Test Error
-O-
-8- Teres
Optlis
Train Eiror
0.70
Test Emvor
0.70
- Optia
0,7-
0.7
0.65
0.65
0.6
0.6
0.60
0.60
500
1000
500
1000
25
50
75
25
75
Sequential ltenations
Sequenial Derations (T)
Wallelock (Sec.)
Wallelock Time (Sec.)
(a) Sequential Iterations
(b) Wallclock Time
Figure 9: Comparison of the train and test error (i.e., 1 accuracy in log scale for y-axis) achieved by different optimizers when training MLP with residual connections on CIFAR-10 dataset with (a) varying number I' of sequential iteration and (b) varying wallclock time (z-axis). The parallelism N set to and each curve denotes the mean from 5 independent runs. Similarly, the wallclock time is evaluated on single NVIDIA RTX 4090 GPU.
Train Loss (log scale)
1.1
X- Vanila
Train Loss (log scale)
1.1
-X- Vanilla
- Tirger Optix
OptFs
1.0
1.0
* %
XX. X 96-
0.9
250
500
100
200
Sequential Iterations (T)
Wallelock Time (Sec.)
Figure 10: Comparison of the training loss (y-axis) achieved by different optimizers when training transformer on the corpus of "Harry Potter and the Sorcerer's 's Stone" with a varying number T of sequential iteration and varying wallclock time (æ-aaxis). The parallelism N is set to 4 and each curve denotes the mean from 3 independent experiments. The wallclock time is evaluated on single NVIDIA RTX 4090 GPU.
Image Classification on MNIST and Fashion-MNIST. We have also compared the training and test errors achieved by different optimizers when training MLP with residual connections the MNIST and Fashion-MNIST datasets. The results in Fig D and Fig indicate that our OptEx consistently improves over the Vanilla baseline and performs comparably to the Target bascline in terms of the number of sequential iteration required to achieve the same level of training or test error. Furthermore, our OptEx significantly improves the time efficiency of training the MLP on both datasets, as evidenced by the results in Fig and Fig N. These findings hence also validate the efficacy of our OptEx in accelerating FOO across various image classification tasks.
Image Classification on CIFAR-10. Besides the test errors presented in Sec. K. we also provide comprehensive comparison of both training and test errors achieved by different optimizers when training an MLP with residual connections on the CIFAR-10 10 dataset. This comparison, shown in Fig El considers varying numbers T' of sequential iterations and varying wallclock time. Due the computational cost of training deep neural networks on CIFAR-10, we evaluate the wallclock time for all optimizers using single NVIDIA RTX 4090 GPU. Notably, similar the results Sec. 6.3. our OptEx consistently outperforms the Vanilla a baseline and performs comparably to the Target baseline in both training and test errors. Additionally, our OptEx considerably enhances the time efficiency of training the MLP on CIFAR-10, 10, as demonstrated by the results in Fig B These results therefore adequately verify the efficacy of our OptEx in expediting FOO.
Autoregression on Text Corpus. In addition to the training results on the Shakespeare corpus, we also present the training loss achieved by different optimizers when training the same transformer on the corpus of "Harry Potter and the Sorcerer's 's Stone" in Fig Remarkably. FIg shows that our OptEx still consistently outperforms the Vanilla baseline and performs comparably to the Target baseline. Moreover, the results in Fig. III demonstrate that our OptEx significantly enhances the time efficiency of training the transformer on the Harry Potter corpus. These findings thus further validate the efficacy of our OptEx in accelerating FOO across various types of learning tasks.
27

---

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 main claims provided in the abstract and introduction can reflect the paper's contributions and scope.
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 or
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.
fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The limitation of the work is provided our Sec. A
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The au- thors 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, c.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 ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low images taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because 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 ad- dress problems of privacy and fairnsss.
While the authors might fear that complete honesty about limitations might used by reviewers grounds for rejection, worse outcome might be that reviewers discover limitations that aren't it acknowledged in the paper. The authors should use their best 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.
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]
28

---

Justification:
The assumptions are summarized in Sec. B and the proofs are provided in the
Appx. A
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 theo- rems.
The proofs can either appear the main paper or supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
All the information is in Appx.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a 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 a dataset and/or model, the authors should describe the steps taken make their results reproducible 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 the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data also be provided via
often one good way accomplish this, but reproducibility detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of model checkpoint, other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) 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 re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors are welcome describe 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., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
29

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
The data and code are provided in the supplemental material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS 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, so No is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (ittps:
wwabbbmmsssoooooiicy.. 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. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification:
All the information is in Appx.
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 appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: All the results reported with mean of multiple independent runs in the figures.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, 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 with given experimental conditions).
30

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
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 I-sigma error bars, but one should state it. The authors should prefer- ably 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 figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
See our Sec. for the details.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or 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 it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: The research conducted in the paper indeed conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
We do not see any societal impact of the work performed.
Guidelines:
The answer NA means that there is 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.
31

---

Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to 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 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 intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards
allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines restrictions 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. Licenses for existing assets
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?
Question:
Answer: [Yes]
Justification: All the data and codes used in the paper are open noun-sourced.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, snperswithcodd www.coocccaaooo datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
If assets are released,
32

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
Justification:
This paper does not release new assets
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mooel as part 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 to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
For crowdsourcing experiments and research with human subjects, does the pa- per include the full text instructions given to participants and screenshots, if applicable, well as details about compensation (if any)?
Question:
Answer: [NA]
Justification: This paper does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, cura- tion, 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/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equiva-
lent) 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 to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
33


Reviews:
[{"review_id": "yReXwTXHHI", "reviewer": "Reviewer_RYzW", "summary": "This paper introduces a new approach for parallelizing stochastic gradient descent for unconstrained, nonconvex, smooth stochastic optimization. The approach is based on building a Gaussian Process surrogate for the true gradient (based on a history of observed stochastic gradients), and uses this surrogate to suggest potential 'future' iterates, by iterating gradient descent using the surrogate. Iterates are then adjusted based on new stochastic gradient estimates, computed in parallel.\n\nThey present worst-case complexity theory that says that being able to compute $N$ stochastic gradients in parallel improves the iteration complexity by a factor of $\\sqrt{N}$, with numerical results on a selection of synthetic problems, reinforcement learning problems, and neural network training problems.", "questions": "How is the next iterate of OptEx defined? Line 10 of Algorithm 1 says it is the final iterate that is chosen, but Figure 1 suggests that the next iterate is somehow taken from a combination of the $\\theta_t^1, \\ldots, \\theta_t^N$ values. Can you please clarify? The latter interpretation would make more sense, otherwise all but one of the parallel evaluations are discarded immediately.\n\nIs the $O(1/\\sqrt{N})$ speedup exactly the same as what you would get by just doing basic sample averaging? That is, at each iteration, just get $N$ different stochastic gradient estimates at the same point and average them (reducing the variance of the estimates). How does your bound compare with this simple use of parallelism?\n\nYou say that \"$\\nabla F$ is assumed to be sampled from the Gaussian Process, $\\nabla F \\sim GP(0, K(\\cdot,\\cdot))$\". Can you please clarify? I read this to mean that this is the assumed prior of your GP surrogate for grad F, but as written it suggests that your actual objective function has - on average - zero gradient, meaning we would expect the 'average point' to be almost stationary?\n\nYou say the \"Target baseline is equivalent to Algo. 1 with [GP mean] being replaced with [stochastic gradient], indicating the desired parallelized iteration we aim to approximate\". Does the 'target' implementation also have the parallel step? If so, we would expect that to give an unfair advantage to 'target', since it does $2N$ stochastic gradient evaluations per outer iteration rather than $N$ for OptEx.", "limitations": "Limitations appear to have been addressed. The theoretical assumptions (e.g. smoothness) are clearly articulated and some practical limitations are addressed in Section 7.\n\nNo potential negative societal impact of this work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. I think the overall approach is an interesting contribution. I particularly like the discussion about the quality of the GP surrogate for the true function and think these results are interesting (Section 5.1). I think this could have useful links with optimization of genuinely complex functions, similar to those typically considered in Bayesian and zeroth order optimization.\n\n2. The numerical results show some promise for the method, and do indeed show promise for a framework for using parallel stochastic gradient evaluations, where this is practical. \n\n3. The paper is clearly written and easy to follow.", "weaknesses": "1. There are gaps in the literature survey of parallelized SGD methods. For example, there is no mention of the highly cited and relevant papers:\n- Recht et al. Hogwild!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent. NeurIPS 2011\n- Mnih et al. Asynchronous Methods for Deep Reinforcement Learning. ICML 2016\n- Yu et al. Parallel Restarted SGD with Faster Convergence and Less Communication. AAAI, 2019\n\n2. It is unclear to me whether the convergence theory (Theorem 2) actually supports the assertion of a $\\sqrt{N}$ speedup from $N$ processes. The RHS gradient bound indeed is $O(1/\\sqrt{N})$, but you are measuring the smallest gradient over $O(N)$ outer iterations. So, doesn't this say that you decrease your gradient by a factor of $O(1/\\sqrt{N})$ after doing $N$ times extra work, which is exactly the convergence rate of SGD under your sub-Gaussian stochastic gradient assumption [33]? The work would also benefit from a direct comparison with just sample averaging of stochastic gradients (see question below).\n\n3. It appears to me that Theorem 3 appears to contradict standard theory (e.g. Bottou, Curtis & Nocedal. Optimization Methods for Large-Scale Machine Learning. SIAM Review, 2018). You claim that the complexity bound for (nonconvex) SGD is tight when applied to the spherical function eq (47), which is strongly convex. However (stochastic) gradient descent with properly chosen stepsizes should converge linearly for this problem, not sublinearly as claimed. Can you explain this potential mismatch in results?\n\n4. For very large problems, it is unrealistic that parallelism will be available, since storing the model and training data may already require parallelism (i.e. a single stochastic gradient evaluation is already computed in parallel). It would be helpful to include a comment about the specific regimes (dimension, dataset size, level of parallelism) where this method is intended to be used.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer RYzW for recognizing the **interesting contribution, promise, and clarity** of our OptEx framework. We address your concerns below.\n\n---\n\n## Responses to Weaknesses\n\n1. Thank you for pointing out this oversight. We appreciate you highlighting these relevant papers on data parallelism. We have referenced some of these works (e.g., [8]) in Section 2 to contrast iteration parallelization with data parallelism. We will include the additional related works you mentioned in our revised paper for a more comprehensive literature survey.\n\n2. Thank you for your insightful comment. Measuring the smallest gradient over $N$ parallel processes is indeed **meaningful and necessary** because our OptEx framework aims to parallelize the $NT$ sequential iterations in SGD. To understand the speedup of OptEx, we follow the common practice in standard SGD to measure the smallest gradients over $NT$ updates (including $N$ parallel processes and $T$ sequential iterations) for a **clear and fair comparison** with standard SGD. Measuring the smallest gradient over $N$ does not decrease the gradient by a factor of $1/\\sqrt{N}$. Instead, OptEx works by **decreasing the number of sequential iterations by a factor of $1/N$ with parallelism $N$** (refer to  the first term on the RHS of Equation 45).\n \n3. Thank you for your thoughtful comment. We would like to clarify that **stochastic** gradient descent (SGD) indeed enjoys only a **sublinear** lower and upper bound (i.e., $\\Theta(1/T)$ for strongly convex functions, as presented in [R1], where the convergence is measured by $E[\\left\\|x_t - x^*\\right\\|^2]$. In our paper, the gap between $\\Theta(1/T)$ in [R1] and $\\Theta(1/\\sqrt{T})$ arises because we measure the convergence of OptEx using $\\left\\| \\nabla F(x_t) \\right\\|^2$, in line with the measurement applied in our Theorem 2 for non-convex functions $F$. When using this measurement for convergence, the $\\Theta(1/\\sqrt{T})$ result in our paper **aligns perfectly** with the existing results for SGD as presented in [34].\n\n    [R1] Nguyen, Phuong_Ha, Lam Nguyen, and Marten van Dijk. \"Tight dimension independent lower bound on the expected convergence rate for diminishing step sizes in SGD.\" Advances in Neural Information Processing Systems 32 (2019).\n\n4. Thank you for the constructive suggestion. OptEx is designed to **complement**, **not replace**, existing parallel approaches (data, model, pipeline) for additional speedup when sufficient computing resources are available (Section 2). In resource-limited scenarios, simpler approaches should be prioritized due to OptEx's complexity. OptEx is most effective when our kernelized gradient estimation is accurate. Empirical results in Section 6.3 show OptEx performs well in **moderate-scale** optimization problems ($d \\approx 10^6$, $N \\leq 10$), achieving significant improvements. We will add these discussions to our revised paper to help practitioners assess OptEx's suitability.\n\n## Responses to Questions\n1. Thank you for pointing out this potential confusion. In our main paper, we choose the next iterate $\\theta_t$ of OptEx to be $\\theta_t^{(N)}$, where all the gradient evaluations ( $\\{\\theta_t^{(i)}\\}_{i=1}^N$) are **not discarded**. These evaluations are used to construct our kernelized gradient estimation for the next iterate (Section 4.3), aiming to reducing estimation error (Theorem 1) and improve convergence (Appendix B.3). Figure 1 aims to suggest that all $N$ processes are **necessary** in each iterate of OptEx to ensure its effective performance. We will add these discussions to our revised paper to make this clearer.\n\n2. The $O(1/\\sqrt{N})$ speedup achieved by OptEx matches that of basic sample averaging for stochastic optimization with noisy gradients. However, the speedup from OptEx comes from **reduced sequential iterations** (first term on the RHS in Equation 45), while sample averaging derives from **reduced gradient variance** (second term on the RHS in Equation 45). When gradient noise is already small or in deterministic optimization (Section 6.1), data parallelism may not provide noticeable speedup, but OptEx can still contribute significantly. Overall, OptEx works in a complementary direction to existing parallelization methods, including sample averaging, to speed up first-order optimization, especially when other methods are not applicable or underperforming (Section 2).\n\n3. Thank you for your question. Similar to the common practice in the Bayesian optimization literature [21], $\\nabla F \\sim GP(0, k(\\cdot, \\cdot))$ means that $\\nabla F$ can be regarded as **being sampled from** a GP prior $GP(0, k(\\cdot, \\cdot))$ (refer to line 213), which is only a prior for $\\nabla F$ and can not infer $\\nabla F=0$ as $\\nabla F$ can be **any** function within this prior. Given an increasing number of gradient histories, we will gain a better understanding of $\\nabla F$, i.e., the GP posterior mean can gradually better approximate $\\nabla F$, as evidenced by our Thm.1. We will add these discussions to our revised paper to clarify this point.\n\n4. Thank you for your question. The 'target' implementation does not have the parallel step due to the inherent iterative dependency in first-order optimization. We treat 'target' as an **ideal, yet impractical**, iteration parallelization (refer to Appendix B.1). This baseline highlights the gap between the ideal and our OptEx, showing that OptEx achieves an acceleration of $\\sqrt{N}$ instead of $N$. We will add these discussions to our revised paper for clarity.\n\n---\n\nWith our elaboration and clarification, we hope our response has addressed your concerns and increased your opinions of our work. We are happy to provide more clarifications if needed.", "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": "kBjLF9LJCh", "reviewer": "Reviewer_ieTR", "summary": "This paper presents OptEx, an approach to parallelize optimization methods by using gradients from previous iterations to predict gradient for subsequent iterations which in turn breaks the serial nature of standard stochastic optimization thereby enabling approximately parallel iterations. The gradient prediction is done using Kernel methods. The paper also presents experimental evidence towards the effectiveness of the proposed approach.", "questions": "Can the authors clarify the speedup offered by utilizing their framework while using acceleration/momentum based methods? Standard mini-batch methods offer different trade-offs particularly wrt batch sizes used while still achieving linear parallelization speedups [1].\n\n[1] Cotter et al: Better Mini-Batch Algorithms via Accelerated Gradient Methods.", "limitations": "N/A.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "This appears to be an interesting contribution, albeit lacking clarity in terms of writing.", "weaknesses": "-- The question of gradient estimation converging to the true gradient seems fairly far-fetched, and there is every reason to believe modeling gradients would essentially carry a constant bias without very strong regularity and realizability conditions. \n\n-- Furthermore, when applied to problems in RL, this becomes even more confounding because of the necessity to explore and using data collected with exploration to in turn construct gradient estimates. I am not sure if I follow how this can be achieved within this framework.\n\n-- The paper's experimental comparison doesn't offer any sources of comparisons against the many different approaches to parallelization that have already been studied in the literature, e.g. mini-batching, model averaging etc.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer ieTR for taking the time to review our paper and appreciate the reviewer's feedback. We would like to provide the following response to address the concerns.\n\n---\n\n> The question of gradient estimation converging to the true gradient seems fairly far-fetched, and there is every reason to believe modeling gradients would essentially carry a constant bias without very strong regularity and realizability conditions.\n\nThank you for your insightful comment. We would like to clarify that Theorem 1 and Corollary 1 theoretically show that our kernelized gradient estimation **asymptotically** converges to the true gradient with respect to the number $T_0$ of gradient history, under our assumptions in Section 5. **This means the estimation error diminishes to nearly zero (not a constant bias) only when $T_0$ is sufficiently large.** If $T_0$ is large enough, thanks to the continuity of gradients, we typically is able to accurately approximate the gradient at any point in a local region. This also aligns with results in Bayesian optimization literature, where function estimation converges to the true function asymptotically without a constant bias, given enough function queries, as evidenced in [32].\n\nWe acknowledge that in practice, obtaining a sufficiently large $T_0$ can be challenging, leading to biased gradient estimation. However, this biased estimation generally provides useful update directions, resulting in the acceleration rate $\\Theta(\\sqrt{N})$ that is achievable by our OptEx framework, as verified by our empirical results in Section 6.\n\nWe hope this clarification addresses your concerns and demonstrates the robustness and potential of our approach.\n\n> Furthermore, when applied to problems in RL, this becomes even more confounding because of the necessity to explore and using data collected with exploration to in turn construct gradient estimates. I am not sure if I follow how this can be achieved within this framework.\n\nAs mentioned in our Appendix B.2.2, our OptEx framework is built on the Deep Q-Network (DQN) algorithm for our RL experiments. In this context, we treat RL as a standard first-order optimization problem, where OptEx aims to accelerate the sequential gradient-based optimization of DQN using parallel computing. The exploration component, which is inherent in the DQN algorithm, does not require additional consideration within the OptEx framework. The exploration strategy used (i.e., the ε-greedy policy) inherently will primarily introduce noisier gradients (i.e., a larger $\\sigma^2$), leading to more biased gradient estimates in our OptEx. Interestingly, our empirical results show that our OptEx is still able to achieve enhanced convergence even in the presence of this increased noise, demonstrating the effectiveness and robustness of our OptEx framework.\n\n> The paper's experimental comparison doesn't offer any sources of comparisons against the many different approaches to parallelization that have already been studied in the literature, e.g. mini-batching, model averaging etc.\n\nOur OptEx framework is in fact a complementary (or orthogonal) approach to the existing parallelization methods, aiming to speedup the first-order optimization in a more general way especially when the other parallelization methods are **not applicable** or **underperforming** rather than replacing them within the scenarios where they already work well (refer to our Sec. 2). For example, mini-batch and model averaging methods are typically used within the context of machine learning and may not be applicable for speeding up other optimization problems where batch sizes and model averaging are not possible, such as the synthetic function in Section 6.1. In contrast, our OptEx framework can provide a compelling speedup in these cases, as evidenced by the results in our Section 6.1. Even within the context of machine learning in our Sec. 6.3, when batch size is already sufficiently large, data parallelism (i.e., mini-batching and model averaging) no long can provide noticeable speedup to the optimization whereas our OptEx can make its novel contributions, as evidenced by the results in our Sec. 6.3 where a large batch size of 256/512 is applied. Overall, since OptEx and other parallelization methods are targeting for different scenarios, it is typically hard to make a fair experimental comparison among these methods.\n\n> Can the authors clarify the speedup offered by utilizing their framework while using acceleration/momentum based methods? Standard mini-batch methods offer different trade-offs particularly wrt batch sizes used while still achieving linear parallelization speedups [1].\n\nThank you for your question. Our OptEx framework is designed to complement existing methods, including acceleration/momentum-based methods (refer to our Sec. 2). When combined with these methods, OptEx is still able to provide additional speedup by parallelizing iterations. For example, in our experiments on synthetic functions (Section 6.1), we used Adam as the baseline optimizer. Our OptEx framework further improved Adam's performance, achieving an acceleration of approximately $\\sqrt{N}$ in practice. This demonstrates the superior effectiveness and wide applicability of OptEx when combined with other optimization techniques. We will make this clearer in our revised paper.\n\n---\n\nWe hope this clarification addresses your concerns and can increase your opinions of our work. We are happy to provide more clarifications.", "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": "QOJMVRojtN", "reviewer": "Reviewer_1m6n", "summary": "The paper \"OptEx: Expediting First-Order Optimization with Approximately Parallelized Iterations\" introduces a novel framework, OptEx, designed to improve the efficiency of first-order optimization (FOO) algorithms by approximately parallelizing their iterations.", "questions": "see weakness", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The introduction of a general framework for parallelizing iterations in FOO is novel and addresses a significant inefficiency in traditional optimization methods.\n2. The paper provides robust theoretical guarantees for the performance of the OptEx framework, including bounds on estimation error and iteration complexity.\n3. The extensive experiments across various domains (synthetic functions, reinforcement learning, and neural network training) demonstrate the practical applicability and efficiency gains of OptEx.", "weaknesses": "1. The kernelized gradient estimation and the associated computational techniques are complex, which might pose challenges for practical implementation and understanding by a broader audience.\n2. The efficiency and scalability of OptEx in very large-scale optimization problems or in highly dynamic environments might be limited\n3. The theoretical guarantees rely on certain assumptions (e.g., the Gaussian distribution of gradients), which may not hold in all practical scenarios, potentially limiting the generality of the results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer 1m6n for recognizing that our OptEx framework is **novel**, it addresses a **significant inefficiency** in traditional optimization methods, and it has **robust theoretical guarantees** and **extensive empirical results** to support its **practical applicability** and **efficiency gains**. We would like to address your concerns below.\n\n---\n\n> The kernelized gradient estimation and the associated computational techniques are complex, which might pose challenges for practical implementation and understanding by a broader audience.\n\nThank you for your feedback. We would like to emphasize that our kernelized gradient estimation and the associated computational techniques are, in fact, quite simple and easy to understand. They involve computations similar to those found in kernel regression (as detailed in Proposition 4.1). Furthermore, our implementation of these techniques is concise, requiring only 16 lines of code (excluding blank lines), which we have provided in our supplementary materials. By following our implementations, we believe that the audience should be able to deploy our method to their problems without significant challenges.\n\n> The efficiency and scalability of OptEx in very large-scale optimization problems or in highly dynamic environments might be limited.\n\nThank you for raising this point. The efficiency and scalability of OptEx in **relatively large-scale** optimization problems have been well demonstrated by our results on neural networks with millions of parameters in Section 6.3. These results adequately highlight the potential of the OptEx framework in accelerating first-order optimization by approximately parallelizing its iterations.\n\nRegarding the **very large-scale** optimization problems and **highly dynamic environments** you mentioned, we would appreciate it if you could provide specific examples for us to explore in future research since different practical scenarios often require specialized adaptations of our OptEx framework to achieve a compelling performance. Overall, we find these directions quite interesting and worthwhile to investigate further. Thank you for bringing them to our attention!\n\n> The theoretical guarantees rely on certain assumptions (e.g., the Gaussian distribution of gradients), which may not hold in all practical scenarios, potentially limiting the generality of the results.\n\nThank you for your insightful comment. If you are referring to our Assumption 1, we would like to clarify that our assumption pertains to the **gradient noise** rather than the **gradient itself** following a Gaussian distribution when dealing with the stochastic optimization problem in Equation 1. This assumption has been widely recognized and applied in the literature [18, 19, 20].\n\nHowever, if you are referring to our Assumption 2,  we agree with you that Assumption 2 (i.e., $\\nabla F$ is sampled from a Gaussian prior $GP(0, k(\\cdot,\\cdot))$) may not hold in all practical scenarios given a predefined kernel $k$, as $k$ may not be the ground truth. Nonetheless, our extensive experiments on synthetic functions, reinforcement learning tasks, and neural network training, as presented in Section 6, have demonstrated that our OptEx framework is in fact quite robust with a predefined kernel $k$ in practice. These experiments show that OptEx can achieve reasonably good performance across various real-world problems, even when Assumption 2 may not necessarily hold.\n\nWe believe these empirical results support the generality of OptEx. If you have any further concerns regarding the generality, we would be happy to address them.\n\n---\n\nWe thank the reviewer for the valuable input and hope our answers can increase your opinions of our work.", "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": "3Mh38QF2aQ", "reviewer": "Reviewer_YWBT", "summary": "The paper proposes a general framework for accelerating first-order optimization methods. The framework leverages parallel computing by estimating the gradients using kernel methods and breaking iterative dependencies. The paper establishes theoretical guarantees that the method gives an acceleration rate of $\\sqrt{N}$ for $N$ parallelism. Then the paper does extensive empirical studies to show the improvements of this framework.", "questions": "Suppose that the step size is very small, can the $N$ potentially be very large?", "limitations": "The authors adequately addressed the limitations.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. Very clearly written. It's immediately clear from the abstract and introduction what kind of work the authors are doing and in the main body the details are given in a very pleasant manner with beautiful plots and formula. The whole paper is well organized with theory and practice covered in style.\n2. Novelty. I'm quickly convinced that the paper's contribution is novel. The related work session well summarizes previous work and it's clear to me that the paper investigates a direction that is distinctively different and important.\n3. A complete story. The paper studies both theoretically and empirically the aspect, with both results agreeing with each other to a certain extent, forming a complete story.", "weaknesses": "The theoretical guarantees rely on assumptions that might not work for $N$ very large, thus limit the extent to which the framework can accelerate optimization.\n\nIn the empirical part, $N$ are not very large, thus unable to show that the framework can accelerate things to great extent in general.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful to Reviewer YWBT for the positive and constructive feedback! We appreciate that the reviewer highly recognizes that our paper is **very well written**, its  contribution is **novel**, and our paper forms a **complete story with both theoretical and empirical supports agreeing with each other**. We would like to address your comments as follows.\n\n---\n\n> The theoretical guarantees rely on assumptions that might not work for $N$ very large, thus limit the extent to which the framework can accelerate optimization. \n> In the empirical part, $N$ are not very large, thus unable to show that the framework can accelerate things to great extent in general.\n> Suppose that the step size is very small, can the $N$ potentially be very large?\n\nThank you for your insightful comments. We acknowledge that when a relatively large learning rate $\\eta$ is applied, the parallelism $N$ of our OptEx framework should not be excessively large to ensure fast convergence to a stationary point, as indicated in line 550 and Equation (45). In this scenario, the error of our kernelized gradient estimation, which is related to $\\rho$ that requires a smaller $N$ to achieve a smaller value, will dominate the convergence of OptEx (refer to the second term on the RHS in Equation 45).\n\nHowever, when the learning rate (i.e., the step size) is very small, $N$ can indeed be potentially very large. In this different scenario, $\\frac{2\\Delta}{\\eta NT}$ (refer to the first term on the RHS in Equation 45) will dominate the convergence of OptEx. Consequently, we can choose a very large $N$ to enjoy a small value of $\\frac{2\\Delta}{\\eta NT}$ and thus achieve fast convergence of OptEx according to Equation 45.\n\nWe support this with additional experimental results following the same setup as in Section 6.1. Using Adam with $\\eta=0.001$,  $T_0=50$, and $N=100$ on Ackley function ($d=10^5$), we observe that when $\\eta$ is small (0.001 vs. 0.1), a large parallelism $N$ (100 vs. 5) can be applied, and our OptEx remains enjoying a speedup of approximately $\\sqrt{N}$.\n\n|         | $T=50$ | $T=100$ | $T=150$ | $T=200$ |\n|---------|--------|---------|---------|---------|\n| Vanilla | 3.0844 | 2.1665  | 1.2413  | **0.5220**  |\n|         | $T=5$  | $T=10$  | $T=15$  | $T=20$  |\n| OptEx   | 0.7578 | 0.7016  | **0.4696**  | 0.2383  |\n\n---\n\nThanks for your insightful questions. We will incorporate these discussions above into our revised version. We hope our clarification will address your concerns and improve your opinion of our work.", "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:

Meta-review: The paper presents OptEx, a first-order optimization framework that enhances the efficiency of first-order optimization algorithms (FOO) through approximately parallelized iterations. OptEx mitigates FOO's reliance on numerous sequential iterations by using kernelized gradient estimation to predict required gradients based on historical data, allowing for approximate parallelization.

The paper establishes theoretical guarantees for the estimation error of the kernelized gradient method and the iteration complexity of SGD-based OptEx, showing that the estimation error approaches zero as gradient history accumulates. Numerical examples are provided to showcase the performance of the method in various settings.

Overall, most reviewers find the paper’s contributions to be novel, interesting, and valuable. Some questions, concerns, and suggestions have arisen during the review process, which the authors have adequately addressed. They are strongly encouraged to incorporate these into the final version of the paper.
Decision: Accept (poster)