Minibatch Stochastic Three Points Method for Unconstrained Smooth Minimization
Authors: Soumia Boucherouite
Grigory Malinovsky
Peter Richtárik
El houcine Bergou
Venue: Submitted to ICLR 2023 (2023)
Keywords: Zero-order optimization
Machine Learning.

Abstract: In this paper, we propose a new zero order optimization method called minibatch stochastic three points (MiSTP) method to solve an unconstrained minimization problem in a setting where only an approximation of the objective function evaluation is possible. It is based on the recently proposed stochastic three points (STP) method (Bergou et al., 2020). At each iteration, MiSTP generates a random search direction in a similar manner to STP, but chooses the next iterate based solely on the approximation of the objective function rather than its exact evaluations. We also analyze our method’s complexity in the nonconvex and convex cases and evaluate its performance on multiple machine learning tasks.

Under review as a conference paper at ICLR 2023
MINIBATCH STOCHASTIC THREE POINTS METHOD FOR UNCONSTRAINED SMOOTH MINIMIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
In this paper, we propose a new zero order optimization method called minibatch stochastic three points (MiSTP) method to solve an unconstrained minimization problem in a setting where only an approximation of the objective function evalu- ation is possible. is based the recently proposed stochastic three points (STP) method (Bergou et al.) 2020). At each iteration, Mi STP generates a random search direction in similar manner STP, but chooses the next iterate based solely on the approximation of the objective function rather than its exact evaluations. We also analyze our method's complexity in the nonconvex and convex cases and evaluate its performance on multiple machine learning tasks.
INTRODUCTION
In this paper we consider the following unconstrained finite-sum optimization problem:
1
min
((x)
f(()
=ERd
where each f:: R2 IR is smooth objective function. Such kind of problems arise in large body of machine learning (ML) applications including logistic regression (Conroy & Sajda 2012), ridge regression (Shen et al., 2013), least squares problems (Suykens & Vandewalle] 1999). and deep neu- ral networks training. The formulation ① can express the distributed optimization problem across agents, where each function f. represents the objective function of agent i, or the optimization problem where each fü is the objective function associated with the data point i. We assume that we work in the Zero Order (ZO) optimization settings, i.e., we do not have access to the derivatives of any function fi and only functions evaluations are available. Such situation arises in many fields and may occur due to multiple reasons, for example: (i) many optimization problems, there only availability of the objective function as the output of a black-box or simulation oracle and hence the absence of derivative information (Conn et al. 2009p. (ii) There are situations where the objective function evaluation is done through an old software. Modification of this software provide first- order derivatives may be too costly or impossible (Conn et al. 2009 Nesterov & Spokoiny 2017). (iii) In some situations, derivatives of the objective function are not available but can be extracted. This necessitates access and good understanding of the simulation code. This process is considered invasive to the simulation code and also very costly in terms of coding efforts (Kramer (IV) In the case of using a commercial software that evaluates only the functions, it is impossible to compute the derivatives because the simulation code is inaccessible (Kramer al. 2011] Conn al.)
201
2009) (V) In the case of having access only to noisy function evaluations, computing derivatives useless because they are unreliable (Conn et al., 2009). ZO optimization has been used in many MI. applications, for instance: hyperparameters tuning of ML models (Turner et al.) 2021 P.cch et al. 22088), multi-agent target tracking (Al-Abri et al. 202T), policy optimization in reinforcement learning algorithms (Malik et al. 2020 Li et al. 2020), maximization of the area under the curve (AUC) GGannarr & Scheinberg 2017). automatic speech recognition (Watanabe & Roux 2014). and the generation of black-box adversarial attacks on deep neural network classifiers (Ughi et al.) 2021). Google Vizier system (Golovin et al. (017) which is the de facto parameter tuning engine at Google is also based on ZO optimization.
There exist many ZO methods that solve problem I.. most of them approximate the gradient us- ing gradient smoothing techniques such as the popular two-point gradient estimator (Nesterov &

---

Under review as a conference paper at ICLR 2023
Spokoiny 2017). Ghadimi & Lan 2013) proposed a stochastic version of the algorithm proposed by Nesterov & Spokoiny 2017) (called RSGF) in the case of function values being stochastic rather than deterministic. [Lu et al. (2018) also proposed ZO stochastic variance reduced method (called ZO-SVRG) based on the minibatch variant of SVRG method (Reddi et al. 2016). 70-SVRG can use different gradient estimators namely RandGradEst, Avg-RandGradFEst, and CoordGradEsst presented
Liu et al. (2018). Another popular class of ZO methods is Direct-Search (DS) methods. They de- termine the next iterate based solely on function values and does not develop approximation of the derivatives or build surrogate model of the the objective function (Conn et al. (009). For comprehensive view about classes of ZO methods we refer the reader to a survey by Larson et al.) (2019). More related to our work, Bergou et al. (2020) proposed ZO method called Stochastic Three Points (STP) which general variant direct search methods. each training itera- tion, STP generates random search direction according to a certain probability distribution and updates the iterate as follow:
x = arg mf - ass), f(x c + f(x)
where > O is the stepsize. STP is simple, very easy to implement, and has better complexity bounds than deterministic direct search (DDS) methods. Due its efficiency and simplicity, STP paved the way for other interesting works that are conducted for the first time, namely the first work on importance sampling in random direct search setting ( (ST11s is method) (Bibi et al. 2020) and the first ZO method with heavy ball momentum (SMTP) and with importance sampling (SMTP Gorbunov et al. 2020). To solve problem I STP evaluates two times at each iteration, which means performing two computations using all the training data for update of the parameters. In fact, proceeding in such manner is not all the time efficient. In cases when the total number of training samples extremely large, such in the case of large scale machine learning, becomes computationally expensive to use all the dataset at each iteration of the algorithm. Moreover, training an algorithm using minibatches of the data could be as efficient or better than using the full batch as in the case of SGD (Gower et al. 2019). Motivated by this, we introduced Mi STS to extend STP to the case of using subsets of the data each iteration of the training process.
We consider in this paper the finite-sum problem as it is largely encountered in ML applications, but our approach is applicable to the more general case where we not have necessarily the finite-sum structure and only an approximation of the objective function can be computed. Such situation may happen, for instance, in the case where the objective function the output of a stochastic oracle that provides only noisylstochastic evaluations.
1.1 CONTRIBUTIONS
In this section, we highlight the key contributions of this work.
We propose M STP method extend the STP method (Bergou et al. 2020) the case of using only an approximation of the objective function at each iteration.
We analyse our method's complexity in the case of nonconvex and convex objective func- tion.
We present experimental results of the performance of Mi.TP on multiple MI. tasks, namely ridge regression, regularized logistic regression, and training of neural net- work. We evaluate the performance of Mi STP with different minibatch sizes and in com- parison with Stochastic Gradient Descent (SGD) (Gower al. 2019) and other ZO meth- ods.
1.2 OUTLINE
The paper is organized as follow: In section 2 we present our STP method. In section we describe the main assumptions on the random search directions which ensure the convergence of our method, These assumptions are the same as the ones used for STP (Bergou et al. 2020). Then,
in section 2.2 we formulate the key lemma for the iteration complexity analysis. In section 3
analyze the worst case complexity our method for smooth nonconvex and convex problems. In section
4 we present and discuss experiments results. In section 4.1 report the results ridge regression and regularized logistic regression problems, and section 4.2 we report the result on neural networks. Finally, conclude in section
2

---

Under review as a conference paper at ICLR 2023
1.3 NOTATION
Throughout the paper, D will denote probability distribution over R We use Ej [-] to denote the expectation. Eg []] to denote the expectation over the randomness quantities, and for two random variables X and Y, E[X]Y] denotes the expectation of X given Y. (r,y) v) x: corresponds to the inner product of x and y. We denote also by ||2 the f--norm, and by || norm dependent on D. We denote by fs:
conditional to other random
fb(œ) =
Σ (ix),
(2)
B
VEB
where is a subset on indexes chosen from the set [1.2...., n2 and [B] is its cardinal.
2 MISTP METHOD
Our minibatch stochastic three points (MISTP) algorithm is formalized below Algorithm Algorithm 1: Minibatch Stochastic Three Points (MiSTP)
Initialization
Choose To E Rdd positive stepsizes {ax probability distribution on Rdd
For h
0,
Generate random vector 8₁P D
Choose elements the subset B₁ u.a.r
3. Let 24 = + 0r and x_ Ix - 04
4. Tk+1 arg min fa. (x_), fa. (x+), fB, (x+)
Due to the randomness of the search directions s and the minibatches B₁ for k 2 O, the iterates are also random vectors for all value f(xo) is deterministic).
1. The starting point Fg is random (the initial objective function
Lemma 1. For x: E IR such that is independent from B, i.e. the choice of does not depend on the choice of B. fe(x) is an unbiased estimator of (x))
Proof. See appendix A, section A.1.
Throughout the paper, we assume that fi. (for nn...,n) is differentiable, and has Li-Lisschitz gradient. We assume also that f bounded from below.
Assumption 1. The objective functionn fo (for ,,...,n) is Le-smooth with Li > and f is bounded from below by f. E R. That is, fa has a Lipschitz continuous gradient with Lipschitz constant Ls:
[V),(()) - VS((i)l22 S Lallæ - vll2.
Yx, E Rdd
and f(x) fo for all x E Idd.
Assumption 2. We assume that the variance of fT(x) is bounded for all IRd:
< < < <0
This assumption is very common in the stochastic optimization literature (Larson et al. 2019 section 6). Note that we put the subscript [8] o B to mention that this deviation may be dependent on the minibatch size. Consider, for example, the case of sampling minibatches uniformly with replacement. In such case, the expected deviation between f and fs satisfy Es Ex((f(z) f (z) for all x Rdd independent from B where = suPpeR & EE
f(x))² (See appendix A, section A.2). Note that, given that the function f(y) y² is convex on R and using Jensen's inequality we have: (Esllf(z) - fz( < (x](f(x) fa(x)))?]. Therefore, Es Ef])f(x) fs(x))] S o18--
B

---

Under review as a conference paper at ICLR 2023
2.1 ASSUMPTION THE DIRECTIONS
Our analysis in the sequel of the paper will be based on the following key assumption.
Assumption 3. The probability distribution D on R has the following properties:
1. The quantity E.-D || is positive and finite. Without loss of generality, in the rest of this paper we assume that it is equal to 1.
2. There is a constant jrD > and norm || DD on TR such that for all E Rd
E E
(g. s) PDllgllD.
As proved in the STP paper (Bergou et al. 2020). multiple distributions satisfy this assumption. For example: the uniform distribution the unit sphere in R the normal distribution with zero mean and d x d identity as the covariance matrix, the uniform distribution over standard unit basis vectors (ei,... ed} in Rd, the distribution on S 31, ... sd where (51, $a} form orthonormal basis of R
2.2 KEY LEMMA
Now, we establish the key result which will be used to prove the main properties of our algorithm.
Lemma 2. If A'Assupttions// and holld then for all k 2 0,
L
Ok+1 S 02 uDDagh +
2 0 + 0
(4)
where LB, = Be EieB, Li L = L(L = 1/2 Em Li. Og = E[s(xx)) and
(()(l()))) and [B&l is the minibatch size.
Proof. We have: f(xx-1)- (#x+1) S (f(xx+1) fB. (2x+1) i.e. f(xx+1) S fB. (#k+1) + [f(*++1) fB. (Ix+1)] (5)
We have: Økt1 arg min(mmi.... (oh (4.sk), fs. (ot + aa.sk), fs. (#x)), therefore: fI, (#k+1) S SB. (ak + a45k) (6). From ss-smoothness fa we have:
fi(0x + a4ss) S f((xx) + (V)((z)), ansh) + Li ||aussi11
2
By summing over fi for i E By and multiplying by 1/ we get:
LB. ||or 11
fB, (an + anssk)
S S8. (Ix) + (V (Ix) s2) +
L.s. a |1sx1112 (8)
f8, (xx) + or fWs (Ix), 8k)
2
By using inequalities 5 (6 and 8 we get:
LBa [(xx+1) S8, (xx) an (V (Tx), sn) oill
sx
E
k+1
where k+1 = (f(*+11) - fs. (# B, By taking the expectation conditioned on Fy and sy and using assumption 2 we get: L
E[s(xz+ sx] S (xx) + as (V/(xx), 8n) +
a
8x
1| + 0
2
Similarly, we get (see details in appendix A, section A.3):
L
)(f( sn] < f(x)) - ax (Vf(xx), sx) +
a
088
2
From the inequalities above conclude:
L a 1111 + 0
B(f(xx-1))=s sal & f(xx) - anl (VF( 8x)
2
4

---

Under review as a conference paper at ICLR 2023
By taking the expectation over Sy and using inequality 3 get:
Eif( - f(xx) - axpp|\/f(a>)) + a + 088)
By taking expectation in the above inequality and due to the tower property of the expectation we get:
a -
COMPLEXITY ANALYSIS
We first state, in theorem 1 the most general complexity result of MiSPP where we do make any additional assumptions on the objective functions besides smoothness of fis for i 1..... n1 and boundedness of f. The proofs follow the same reasoning as the ones in STP (Bergou et al. 2020 we defer them to the appendix.
Theorem (nonconvex case). Let Assumptions 2 and 3 3be satisfied and 0 < (upe)
21 Choose
a fixed stepsize oy = a with (uDe- ((DDC)2 22o B )/ If
(NDE+ / ((DD))2 -2 /L)BBLLLL
K 2 k(E) def
f(xo) - f- UDEE 4 018
1,
(8)
then ming= 0. K E [ S s. In particular, have: Cooptmml MDE/L
Proof. see appendix A, section A.4
We now state the complexity of MiSTP in case convex J. To do so, we add the following assumption:
Assumption 4. We assume that I is convex, has minimizer Va, and has bounded level set at vo:
Ro
def
= max (1<x - I.1ld f(x) S [(m)) < +00,
where | def
max (E, x)
| < }} defines the dual norm to || IlD.
Note that if the above assumption holds, then whenever f(x) I f(zo), we get f(x) f(x,) $ (Vf(x), z.) [V](=)]lp(r x.)² ((=))/
[V](r)|b|| z. i
Ra Vf())l That is,
vf(x))l 2 f(x) - f(x.)
Ro
Theorem 2 (convex case). Let Assumptions
and be satisfied. Let e > and d
(upe)²
choose constant stepsize a 1LR
SHD T.Ro
If
LR
4([(w))) - [(xa))
K >
log
(10)
then [[((x) [(x-)) S.
Proof. see appendix A, section A.5
4 NUMERICAL RESULTS
In this section, we report the results of some experiments conducted in order to evaluate the ef- ficiency of MiSTP. All the presented results averaged over 10 runs of the algorithm and the confidence intervals (the shaded region in the graphs) are given by μ + where μ is the mean and is the standard deviation. For each minibatch size, we choose the learning rate by performing
5

---

Under review as a conference paper at ICLR 2023
n- 1000, d= 60
60
r-A,a-1
20
1=0,0=0.1
r- 1000, 1=1
500,0 0.1
=00,a==
== 0.01
r- 50,0=001
15
=0.0,000011
2
0.00
1 10.a
1.000.000
T-1.8-0.00
5
10
5
20
100
150
200
300
350
400
Epochs
Epochs
Figure 1:
Performance of MiSTP with different minibatch sizes on ridge regression problem. On the left, the abalone dataset. On the right, the splice dataset.
grid search on the values 1,0.1,0.01,.. and select the one that gives the best performance, de- notes the minibatch size, i.e., f = |B] In all our implementations, the starting point Ho sampled from the standard Gaussian distribution. The distribution D used to sample search directions, unless specified otherwise, is the normal distribution with zero mean and d x identity as the covariance matrix.
4.1 MISTP ON RIDGE REGRESSION AND REGULARIZED LOGISTIC REGRESSION PROBLEMS
We performed experiments on ridge regression and regularized logistic regression. They are prob- lems with strongly convex objective function f.
the case ridge regression we solve:
min
[f()
Σ (Ali, v1)²
[
(11)
ERd 2n
and in the case regularized logistic regression we solve:
#2dd 2n Σ In(1 exp--Axp(-=AA
min [f(x)
"
À |
(12)
In both problems A E nxd R" are the given data and À >> 0 is the regularization parameter For logistic regression:
{-1, 13"h and all the values in the first column of A are equal to For both problems we set À = 1/n. The experiments of this section are conducted using LIBSVM
datasets (Chang & Lin 2011).
we evaluate the performance of MiSTP when using different minibatch sizes. In section 4.2 we evaluate the performance of MiSTP compared SGD, and in section 4.1.3 we compare the performance of MiSTP with some other 70 methods.
In section 4.1.1
4.1.1 MISTP WITH DIFFERENT MINIBATCH SIZES
Figures D andd show the performance of MiSTP when using different minibatch sizes. From these figures we see good performance of Mi MTP... For different minibatch sizes, generally converges faster than the original STP (the full batch) in terms of number of epochs. We notice also that there an optimal minibatch size that gives the best performance for each dataset: among the tested values, for the "abalone" dataset it is equal to 50, for 'splice' dataset it is 1, for 'ala" and 'australian' datasets is 10. All those optimal minibatch sizes are just very small subset of the whole dataset which results in less computation at each iteration. Those results also show that could get good performance when using only an approximation of the objective function using a small subset of the data rather than the exact function evaluations.
It is known that the value of the first feature must be 1 for all the training inputs when performing logistic regression. When using LIBSVM datasets add this column the data.

---

Under review as a conference paper at ICLR 2023
n- 1605, d- 124
1.4
T-
1.0
5 = 0.2
a0001
100.
100, a0.00
t= 50,
8
T- 50.0 0.01
10,
10,0 0.001
0.6
0.4
0.4
0.2
0.2
100
250
10
50
70
Fpochs
Epochs
Figure 2: Performance of MiSTP with different minibatch sizes on regularized logistic regression problem. On the left, the ala dataset. On the right, the australian dataset.
Ouggr Geop
GeaST dsep
500
5GD
50-
100
30
20
20
10
10
15 Iterations
20
25
20
15
20
25
Iterations
T- 10C,
10"2, Asco 10
T- 7. BALSTS
10"1, 0000 10
9G0
MISTP
2-
1000 12CB
0
100
200
300
lterations
Iterations
Figure 3: Performance of MiSTe and SCD on ridge regression problem using real data from LIB- SVM. Above, abalone dataset: n = 4177 and Below, ala dataset :n 1605 and 123.
4.1.2 MTSTP VS. SGD
In this section we report some results of experiments conducted in order to compare the performance of MiSTP to SGD. For both methods, we used the same starting point at each run and the same minibatch at each iteration.
Figures and 4 show results of experiments on ridge regression and regularized logistic regression problems respectively. More results are presented in Appendix B. From these experiments see that in most of the cases, Mi STP is able to converge to a good approximation or exactly the same solution as SGD. MiSTP also gives competitive performance problem is small, i.e., d is less or around 10. When the dimension of the problem is big, i.c., d is of order of tens, Mi.STE needs more iterations compared to SGD to converge to just an approximation of the solution. In all cases, we see that the number of iterations that MiSTP needs to converge increases as the batch size decreases. It also increases as the dimension while SGD is slightly affected by this. In Appendix B, report the values of the approximation fE alongside f for multiple minibatch sizes. We can see that starting from a given batch size (generally get
SGD when the dimension of the
the problem increases
when r 2 500 for the given datasets) fs is good approximation of f which shows that the same results when training a model with only a subset of the data as when using all available samples. Consequently, this results in less computations.
7

---

Under review as a conference paper at ICLR 2023
7- 100, Gyeem - 100"), Psop
-,0g0,0ppp -1
T- D, draspp - 10 Aspo -1
10-
0.7
HSSTP
KISTF
08
0.6
0 0.4
044
0.1
20
Iterations
100. Sypap Soop
Ruuerp 10 0 Aggp
500
5GD
MISTP
MISTP
0.5
0.4
300
1003
1500
2009
50
100
150 Iterations
200
250
300
Iterstoons
Figure 4: Performance MiSTP and SGD on regularized logistic regression problem using real data from LIBSVM. Above, australian dataset: n = 690 and d = 15. Below, ala dataset n 1605 and d 124.
4.1.3 MISTP VS. OTHER ZERO-ORDER METHODS
In this section, we compare the performance of MiSTP with three other ZO optimization methods. The first is RSCF, proposed by Ghadimi & Lan (2013). In this method, at iteration k, the iterate is updated as follow:
So, (ur + musE) Sag (1Rx)
2h+1 2b
ag
(13)
where 14 E 10, is the finite differences parameter, ag is the stepsize, 8 random vector following the uniform distribution on the unit sphere, and B3 is a randomly chosen minibatch. The second is ZO-SVRG proposed by Liu et al. (2018, Algorithm 2). For this method, at iteration k, the gradient estimation of f&, at Iy given by:
L (fr, (xx + (us)) fis. (2x))s8
fB. (mx)
(14)
where > 0 is the smoothing parameter and s is a random direction drawn from the uniform distribution over the unit sphere. And the last is ZO-CD (ZO coordinates descent method), in this method, at iteration k. the iterate updated follow:
for (at + ue:)
- fis. (2r pres)
g15
es
(15)
24
where μ > 0 is smoothing parameter and e; E Idd for i E [d] is standard basis vector with 1 at its ith coordinate and elsewhere.
The distribution DD used here for STP is the uniform distribution on the unit sphere. For RSGF, 20-SVRG, and ZO-CD, we chose μ* = μ = 10-1
Figure 5) shows the objective function values against the number of function queries of the differ- ent ZO methods using different minibatch sizes. Note that one function query the evaluation of one ft for i E [n] at given point. From figure (5) we see that, the ridge regression problem, MiSTP, RSGF, and ZO-CD show competitive performance while 20-SVRG needs much more func- tion queries converge. On the regularized logistic regression problem, MiSTP outperforms all the other methods. RSGF, 20-CD, and RO-SVRG need almost 5 times function queries to converge than Mi STP for 100 and around times more function queries than Mi STP for 50.
8

---

Under review as a conference paper at ICLR 2023
1000, 60
1000, d=
T- z- 0.01 NI57
53.a 0.1 MIST
ai m.l RSGF
10 20-5VIG 0.01
32,a 10 20-5VIG
5
105
163
zim
11- 2805,
1.0
0.5
2.66
0.6
0.4
0.4
function queries
Sunctiiin queries
163
Figure 5: Comparison of MiSTP, RSGF, ZV-SVRG, and 20-CD. Above: ridge regression problem using the splice dataset. Below: regularized logistic regression problem using the ala dataset.
4.2 MISTP IN NEURAL NETWORKS
Figure 6 shows the results of experiments using MiSTP as the optimizer in a multi-layer neural network (NN) for MNIST digit (LeCun et al. 1998) classification with different minibatch sizes. The architecture we used has three fulle-connected layers of size 256, 128, 10, with ReLU activation after the first two layers and Softmax activation function after the last layer. The loss function is the categorical cross entropy. From figure 6 we observe that the minibatch size 6000 outperforms the minibatch size 3000 and the full batch, it converges faster better accuracy and loss values. r == 6000 1/10 of the dataset (we used the whole MNIST dataset which has 60000 samples), leads to less computation time each iteration than using all the 60000 samples. Besides it largely outperforms the full batch. Those results prove that minibatch training is more efficient than the full batch training and that we can find an optimal minibatch size that leads to efficient training of an NN in terms of performance and computation effort.
betch --3000 2.0.
10
1000 0-0
Soothe
Epoth
Figure 6: Comparison of different minibatch sizes for MiSTP in multi-layer neural network.
CONCLUSION
In this paper, we proposed the MiSTP method extend the STP method case of using only an approximation of the objective function at each iteration assuming the error between the objective function and its approximation is bounded. MiSTP sample the search directions the same way as STP, but instead of comparing the objective function at three points it compares approximation. We derived our method's complexity the case nonconvex and convex objective function. The presented numerical results showed encouraging performance of Mi STP. In some settings, it showed superior performance over the original STP. There are a number of interesting future works to further extend method, namely deriving a rule find the optimal minibatch size, comparing the performance of MiSTP with other zero-order methods on deep neural networks problems, extending Mi STP to the case of distributed learning, and investigating Mi STP in the non-smooth case.

---

Under review as a conference paper at ICLR 2023
REFERENCES
S. AI-Abri, T. X. Lin, R. S. Nelson, and F. Zhang. A derivative-free distributed optimization algo- rithm with applications in multi-agent target tracking. 2021 American Control Conference (ACC), pp. 3844-3849, 2021.
E. H. Bergou, Gorbunov, and P. Richtárik. Stochastic three points method for unconstrained smooth minimization. SIAM Journal Optimization, 30(4):2726-274)) 2020.
A. Bibi, E. H. Bergou, O. Sener, B. Ghanem, and P. Richtárik. A stochastic derivative-free optimiza- tion method with importance sampling: Theory and learning to control. Proceedings of the 34th AAAI Conference on Artificial Intelligence, pp. 3275-3282, 2020.
C. C. Chang and C. J. Lin. Libsvm: a library for support vector machines. ACM Transactions on Intelligent Systems and Technology (TIST), 2011.
A. R. Conn, K. Scheinberg, and N. Vicente. Introduction to derivative free optimization. Society for Industrial and Applied Mathematics (SIAM), 2009.
B. Conroy and Sajda. Fast, exact model selection and permutation testing for 12-regularized logistic regression. Artificial Intelligence and Statistics, pp. 246-24222244452 266,254, 2012.
S. Ghadimi and G. Lan. Stochastic first- and zeroth-order methods for nonconvex stochastic pro- gramming. SIAM Journal on Optimization, 23(4):2341-2368 2013.
H. Ghanbari and K. Scheinberg, Black-box optimization in machine learning with trust region based derivative free algorithm. arXiv: 1703.06925 2017.
D. Golovin, B. Solnik, S. Moitra, G. Kochanski, J. Karro, and D. Sculley. Google vizier: A service for black-box optimization. KDD '17: Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1487-1495, 2017.
E. Gorbunov, A. Bibi, O. Sener, E. H. Bergou, and P. Richtarik. A stochastic derivative free opti- mization method with momentum. ICLR 2020, 2020.
R. M. Gower, N. Loizou, X. Qian, A. Sailanbayev, E. Shulgin, and P. Richtárik. Sgd: General anal- ysis and improved rates. Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 5200-5209, 2019.
O. Kramer, D. E. Ciaurri, and S. Koziel, Derivative-free optimization. Computational Optimization, Methods and Algorithms, ed by S. Koziel and X.-S. Yang, Springer, pages 61-83, 2011.
Larson, M. Menickelly, and S. M. Wild. Derivative-fre optimization methods. Acta Numerica, 28:287-404, 2019.
Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, (6(11):2278-2322 1998.
Y. Li, Y. Tang, R. Zhang, and N. Li. Distributed reinforcement learning for decentralized linear quadratic control: A derivative-free policy optimization approach. Proceedings of the 2nd Con- ference on Learning for Dynamics and Control, PMLR,
2020.
Liu, B. Kailkhura, P.-.. Chen, P. Ting, S. Chang, and Amini. Zeroth-order stochastic vari- ance reduction for nonconvex optimization. Advances in Neural Information Processing Systems (NeurIPS), pp. 3731-3741, 2018.
D. Malik, A. Pananjady, K. Bhatia, K. Khamaru, P. L. Bartlett, and M. J. Wainwright. Derivative-free methods for policy optimization: Guarantees for linear quadratic systems. Journal of Machine Learning Research, 21(21):1-51, 2020.
Y. Nesterov and V. Spokoiny, Random gradient-fir free minimization of convex functions, Foundations of Computational Mathematics, 17:527-566, 2017.
10

---

Under review as a conference paper at ICLR 2023
P.Koch, O. Golovidov, S. Gardner, B. Wujek, J. Griffin, and Y. Xu. Autotune: A derivative-free optimization framework for hyperparameter tuning. KDD '18: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 443 443-452, 2018.
S. Reddi, A. Hefny, S. Sra, Poczos, and A. Smola. Stochastic variance reduction for nonconvex optimization. International conference on machine learning, pp. 314-323, 2016.
X. Shen, M. Alam, F. Fikse, and L. Rönnegård. A novel generalized ridge regression method for quantitative genetics. Genetics, 193(4): 1268, 2013.
A. Suykens and Vandewalle. Least squares support vector machine classifiers. Neural process- ing letters, 93))2933-300, 1999.
R. Turner, D. Eriksson, M. McCourt, J. Kiili, E. Laaksonen, Z. Xu, and I. Guyon. Bayesian optimiza- tion is superior to random search for machine learning hyperparameter tuning: Analysis of the black-box optimization challenge 2020. Proceedings of Machine Learning Research, 133:3-26, 2021.
G. Ughi, V. Abrol, and J. Tanner. An empirical study of derivattve- targeted black-box attacks deep neural networks. Optimization and Engineering, 2021.
algorithms for
S. Watanabe and J. Le Roux. Black box optimization for automatic speech recognition. Acoustics, Speech and Signal Processing (ICASSP), 2014 IEEE International Conference, pp. 2014.


Reviews:
[{"review_id": "zUjRbT89eKP", "reviewer": "Reviewer_jzrD", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies smooth zeroth-order optimization and extends the STP method to the finite-sum setting. The proposed method is very simple and easy to implement. The authors also provide convergence analysis and empirically verified the efficiency of the proposed method.", "summary_of_the_review": "Overall, I think the proposed method is interesting, but the experiments part greatly reduces the quality of this paper.\n\n---\n\nAfter rebuttal:\n\nI'm disappointed that the paper does not contain experiments on problems for which gradients are not available. Thus I will keep my score.", "strength_and_weaknesses": "Strength:\n\n1. The paper is well-written and easy to follow.\n2. The MiSTP method is simple and easy to implement. It only needs an approximation of the function evaluation.\n\nWeaknesses:\n\nMy main concern is about the experiments. All models used in the experiments (ridge regression, regularized logistic regression, and fully connected NN) can be efficiently solved by gradient-based methods. None of these methods require the use of zeroth-order optimization. I suggest the authors perform experiments on some ML applications where computing gradients is intractable. The authors may refer to the experiments of the ZO-SVRG paper(Liu et al., 2018).\n\nother concerns:\n\n1. Thm 1 and 2 require $\\sigma_{|B|}<O(\\epsilon^2)$, which means that the batch size may be proportional to $\\epsilon^{-2}$. Since $\\epsilon$ could be very small, the batch size may be very large.\n2. I suggest the authors briefly introduce the main difficulty of extending STP to MiSTP.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "h1SGG1ZBOy", "reviewer": "Reviewer_dcdP", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper presented the mini-batch extension of STP method in the finite-sum problem. The paper analyzed the complexity of minibatch STP in both non-convex and convex cases and examine the performance of MiSTP under various settings. The experiment showed that MiSTP converged faster than STP in terms of number of epochs. It also compared MiSTP with SGD and showed that MiSTP could converge to a good approximation or exactly the same solution as SGD. Moreover, MiSTP  compares favorably against several state-of-the-art ZO methods.\n\n\n\n", "summary_of_the_review": "Overall, the paper provides a novel zeroth-order algorithm for stochastic convex and nonconvex optimization. Both theoretical analysis and experimental results are  well-supported. However, I still have some concern about the technical contribution. I am not fully convinced why the proposed method is more advantageous over existing algorithms. Maybe I missed something, any theoretical or application insights are welcome. ", "strength_and_weaknesses": "### Strength\n\n1. It's easy to follow and understand the technical details. The paper is well organized and quite readable. The theoretical analysis is sound. \n\n2. The experiments are quite detailed, which clearly demonstrates the great performance of  MiSTP in a wide range of problems. \n\n\n### Weakness\n\n- Since the paper considers finite sum setting, developing a variance reduced algorithm can substantially enrich the contribution and solidness of the paper\n\n- It is not clear to me what theoretical advantage MiSTP has, compared with existing algorithm such as RSGF or ZO-SVRG. \n\n- In the theoretical part the authors show the complexity under convex and non convex case but the experiment part is about strong convex problem. Can you also develop the rate for strongly convex setting?\n\nA minor issue:\nShould we call the algorithm a zeroth-order method as opposed to zero-order method? ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "dI30_t1FfLp", "reviewer": "Reviewer_KsoD", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This submission proposes a minibatch stochastic three points method, which only requires an approximation of the objective function at each iteration. It is an extension of a previous work of stochastic three points method that requires the exact evaluation of objective functions.", "summary_of_the_review": "I tend to vote for rejection based on the current manuscript being lack of motivation,  not having adequate comparison to existing methods and not showing novelty in terms of analysis techniques.", "strength_and_weaknesses": "Strengthes:\nCompared to STP, evaluating objective value on a batch of data instead of the full data can make the algorithms much more practical.\n\nWeakness:\n\n1. The motivation of this work is not well justified. What are the advantages of using this STP-type algorithms compared to other existing works such as two-point estimators? Even though STP was proposed in another work, it is still necessary to clearly discuss the motivation in order to help the audience to understand the significance of this work. \n\n2. Given the existing STP work, this submission extends it to a version that only requires an approximation of the objective instead of an accurate evaluation. What are the challenges in the analysis? Can the introduced noise by inaccurate estimation of objective values just be controlled in similar way to in the analysis of stochastic gradient descent? Therefore, I wonder what are the specific challenges and key techniques to solve these challenges in this submission?\n\n3. The experiments in Section 4.1 are for easy problems where gradients can be easily computed and so SGD are applicable. And experiments in Section 4.2 are not compared with other zero order methods. Hence, the true performance of the proposed MiSTP is questionable. Besides, the problems in Section 4.1 are strongly convex which expect better complexity rates than those in Theorem 1 and Theorem 2. Maybe the authors can consider to add the analysis of strongly convex cases as well.\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "YMAVv9dAKL", "reviewer": "Reviewer_o1C6", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this submission, the authors study zeroth-order optimization methods for minimizing deterministic finite-sum problem. In particular, the authors present mini-batch three points zeroth-order method in which the objective function is calculated at three different points at each iteration over a fixed mini-batch of functions from the finite-sum. They also present sample complexity of their proposed method for both convex and nonconvex settings and conduct some numerical experiments to show performance of the algorithm.", "summary_of_the_review": "The contribution is incremental and the results have not been presented clearly.", "strength_and_weaknesses": "The idea of the manuscript is similar to that of (Bergou et al., 2020) and the only difference is that the approximation of the objective function is considered for the three-point estimate over mini-batches. However, the authors assume that they can calculate the objective function at different points over a fixed choice of functions from the finite-sum which is not truly stochastic setting. Moreover, no noise is involved in estimating each $f_i$. The sample complexities have been proposed based on $\\mu_D$ which hides the dependence on the problem dimension. The numerical experiments have been also conducted just over low-dimensional settings. No comparison with existing results has been presented.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject