In this paper, we design and analyze a new zeroth-order (ZO) stochastic optimization algorithm, ZO-signSGD, which enjoys dual advantages of gradient-free operations and signSGD. The latter requires only the sign information of  gradient estimates but is able to achieve a comparable  or even better convergence speed than SGD-type algorithms. Our study  shows that ZO signSGD requires $\sqrt{d}$ times more iterations than signSGD, leading to a convergence rate of  $O(\sqrt{d}/\sqrt{T})$ under mild conditions, where $d$ is the number of optimization variables, and $T$ is the number of iterations. In addition, we analyze the effects of different types of gradient estimators on the convergence of ZO-signSGD, and propose two variants of ZO-signSGD that  at least  achieve $O(\sqrt{d}/\sqrt{T})$ convergence rate. On the application side we explore the connection between ZO-signSGD and  black-box adversarial attacks in robust deep learning.   Our empirical evaluations on image classification datasets MNIST and CIFAR-10 demonstrate the superior performance of ZO-signSGD on the generation of   adversarial examples from black-box neural networks. Zeroth-order (gradient-free) optimization has attracted an increasing amount of attention for solving machine learning (ML) problems in scenarios where explicit expressions for the gradients are difficult or infeasible to obtain. One recent application of great interest is to generate prediction-evasive adversarial examples, e.g., crafted images with imperceptible perturbations to deceive a well-trained image classifier into misclassification. However, the black-box optimization nature limits the practical design of adversarial examples, where internal configurations and operating mechanism of public ML systems (e.g., Google Cloud Vision API) are not revealed to practitioners and the only mode of interaction with the system is via submitting inputs and receiving the corresponding predicted outputs BID31 BID27 BID36 BID17 BID3 . It was observed in both white-box and black-box settings 1 that simply leveraging the sign information of gradient estimates of an attacking loss can achieve superior empirical performance in generating adversarial examples BID13 BID28 BID16 . Spurred by that, this paper proposes a zeroth-order (ZO) sign-based descent algorithm (we call it 'ZO-signSGD') for solving black-box optimization problems, e.g. design of black-box adversarial examples. The convergence behavior and algorithmic stability of the proposed ZO-signSGD algorithm are carefully studied in both theory and practice.In the first-order setting, a sign-based stochastic gradient descent method, known as signSGD, was analyzed by BID2 BID1 . It was shown in BID2 that signSGD not only reduces the per iteration cost of communicating gradients, but also could yield a faster empirical convergence speed than SGD BID19 . That is because although the sign operation compresses the gradient using a single bit, it could mitigate the negative effect of extremely components of gradient noise. Theoretically, signSGD achieves O(1/ √ T ) convergence rate under the condition of a sufficiently large mini-batch size, where T denotes the total number of iterations. The work in BID1 established a connection between signSGD and Adam with restrictive convex analysis. Prior to BID2 BID1 , although signSGD was not formally defined, the fast gradient sign method BID13 to generate white-box adversarial examples actually obeys the algorithmic protocol of signSGD. The effectiveness of signSGD has been witnessed by robust adversarial training of deep neural networks (DNNs) BID28 . Given the advantages of signSGD, one may wonder if it can be generalized for ZO optimization and what the corresponding convergence rate is. In this paper, we answer these questions affirmatively.Contributions We summarize our key contributions as follows.• We propose a new ZO algorithm, 'ZO-signSGD', and rigorously prove its convergence rate of O( √ d/ √ T ) under mild conditions. • Our established convergence analysis applies to both mini-batch sampling schemes with and without replacement. In particular, the ZO sign-based gradient descent algorithm can be treated as a special case in our proposed ZO-signSGD algorithm.• We carefully study the effects of different types of gradient estimators on the convergence of ZO-signSGD, and propose three variants of ZO-signSGD for both centralized and distributed ZO optimization.• We conduct extensive synthetic experiments to thoroughly benchmark the performance of ZO-signSGD and to investigate its parameter sensitivity. We also demonstrate the superior performance of ZO-signSGD for generating adversarial examples from black-box DNNs.Related work Other types of ZO algorithms have been developed for convex and nonconvex optimization, where the full gradient is approximated via a random or deterministic gradient estimate BID18 BID29 BID11 BID9 BID10 BID34 BID15 BID12 BID22 BID25 . Examples include ZO-SGD BID11 , ZO stochastic coordinate descent (ZO-SCD) BID22 , and ZO stochastic variance reduced gradient descent (ZO-SVRG) BID26 a; BID14 . Both ZO-SGD and ZO-SCD can achieve O( DISPLAYFORM0 And ZO-SVRG can further improve the iteration complexity to O(d/T ) but suffers from an increase of function query complexity due to the additional variance reduced step, known as 'gradient blending' BID26 ), compared to ZO-SGD. The existing work showed that ZO algorithms align with the iteration complexity of their first-order counterparts up to a slowdown effect in terms of a small-degree polynomial of the problem size d. Motivated by the impressive convergence behavior of (first-order) signSGD and the empirical success in crafting adversarial examples from black-box ML models, in this paper we rigorously prove the O( √ d/ √ T ) convergence rate of ZO-signSGD and its variants under mild conditions. Compared to signSGD, ZO-signSGD suffers a slowdown (proportional to the problem size d) in convergence rate, however, it enjoys the gradient-free advantages. Compared to other ZO algorithms, we corroborate the superior performance of ZO-signSGD on both synthetic and real-word datasets, particularly for its application to black-box adversarial attacks. In the future, we would like to generalize our analysis to nonsmooth and nonconvex constrained optimization problems. BID2 FIG1 , we assume that the ZO gradient estimate of f (x) and its first-order gradient ∇f (x) = x suffer from a sparse noise vector v, where v1 ∈ N (0, 1002 ), and vi = 0 for i ≥ 2. As a result, the used descent direction at iteration t is given bŷ ∇f (xt) + v or ∇f (xt) + v. FIG1 presents the convergence performance of 5 algorithms: SGD, signSGD, ZO-SGD, ZO-signSGD and its variant using the central difference based gradient estimator (10). Here we tune a constant learning rate finding 0.001 best for SGD and ZO-SGD and 0.01 best for signSGD and its ZO variants. As we can see, sign-based first-order and ZO algorithms converge much faster than the stochastic gradient-based descent algorithms. This is not surprising since the presence of extremely noisy component v1 leads to an inaccurate gradient value, and thus degrades the convergence of SGD and ZO-SGD. By contrast, the sign information is more robust to outliers and thus leads to better convergence performance of sign SGD and its variants. We also note that the convergence trajectory of ZO-signSGD using the gradient estimator FORMULA1 coincides with that using the gradient estimator FORMULA6 given by the forward difference of two function values. FIG1 : Comparison of different gradient-based and gradient sign-based first-order and ZO algorithms in the example of sparse noise perturbation. The solid line represents the loss averaged over 10 independent trials with random initialization, and the shaded region indicates the standard deviation of results over random trials. Left: Loss value against iterations for SGD, signSGD, ZO-SGD, ZO-signSGD and ZO-signSGD using the central difference based gradient estimator (10). Right: Local regions to highlight the effect of the gradient estimators (3) and (10) on the convergence of ZO-signSGD.
We design and analyze a new zeroth-order stochastic optimization algorithm, ZO-signSGD, and demonstrate its connection and application to black-box adversarial attacks in robust deep learning
{"src": "scitldr-AIC_train", "paper_id": "BJe-DsC5Fm"}