Single Loop Gaussian Homotopy Method for Non-convex Optimization
Authors: Hidenori Iwakiri
Yuhang Wang
Shinji Ito
Akiko Takeda
Venue: NeurIPS 2022 Accept (2022)
Keywords: Gaussian homotopy
Gaussian smoothing
Non-convex optimization
Worst-case iteration complexity
Zeroth-order optimization

Abstract: The Gaussian homotopy (GH) method is a popular approach to finding better stationary points for non-convex optimization problems by gradually reducing a parameter value $t$, which changes the problem to be solved from an almost convex one to the original target one. Existing GH-based methods repeatedly call an iterative optimization solver to find a stationary point every time $t$ is updated, which incurs high computational costs. We propose a novel single loop framework for GH methods (SLGH) that updates the parameter $t$ and the optimization decision variables at the same. Computational complexity analysis is performed on the SLGH algorithm under various situations: either a gradient or gradient-free oracle of a GH function can be obtained for both deterministic and stochastic settings. The convergence rate of SLGH with a tuned hyperparameter becomes consistent with the convergence rate of gradient descent, even though the problem to be solved is gradually changed due to $t$. In numerical experiments, our SLGH algorithms show faster convergence than an existing double loop GH method while outperforming gradient descent-based methods in terms of finding a better solution.

Single Loop Gaussian Homotopy Method for Non-convex Optimization
Hidenori Iwakiri" The University of Tokyo, RIKEN AIP 1wakiri-hidenori220 ecc. u-tokyo ac. jp
Yuhang Wang" The University of Tokyo
utyuuhiko@@gaillcc com
Shinji Ito
Akiko Takeda
NEC Corporation, RIKEN AIP
The University of Tokyo, RIKEN AIP takeda@mist. i. w.t.uoooo..ccc ac.
i X-shinji@nec.com com
Abstract
The Gaussian homotopy (GH) method is a popular approach to finding better stationary points for non-convex optimization problems by gradually reducing parameter value i, which changes the problem to solved from an almost convex to the original target iterative optimization solver to find a stationary point every time t is updated, which incurs high computational costs. We propose novel single loop framework for GH methods (SLGH) that updates the parameter and the optimization decision variables at the same. Computational complexity analysis performed on the SLGH algorithm under various situations: either gradient or gradient-free oracle of a GH function can obtained for both deterministic and stochastic settings. The convergence rate of SLGH with tuned hyperparameter becomes consistent with the convergence rate of gradient descent, even though the problem be solved is gradually changed due to f. In numerical experiments, our SLGH algorithms show faster convergence than an existing double loop GH method while outperforming gradient descent- methods in terms of finding better solution.
Existing GH-based methods repeatedly call
Introduction
Let us consider the following non-convex optimization problem:
minimize
f(x),
(1)
#ER*
where f FdRd + a non-convex function. Let us also consider the following stochastic setting:
f(x) = E<(f(x;
where & the random variable following probability distribution from which i.id. samples can be generated. Such optimization problems attract significant attention in machine learning, and at the same time, the need for optimization algorithms that can find stationary point with smaller objective value is growing. For example, though it is often said that simple gradient methods can find global minimizers for deep learning (parameter configurations with zero or near-zero training loss), such beneficial behavior is not universal, noted in [16]; the trainability of neural nets is highly dependent on network architecture design choices, variable initialization, etc. There are also various other highly non-convex optimization problems in machine learning (see e.g., [13]).
"The first two authors contributed equally.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Table 1: Each theorem shows the iteration complexity of SLGH with respect to and the dimension of input space d to reach an c-stationary point in the corresponding problem setting. "const. ? shows the complexity when we treat the decreasing parameter "y as a constant. "tuned y shows the lowest complexity of SLGH attained by updating appropriately, which matches the complexity of the standard first- or zeroth-order methods (see e.g.. Theorem 3.4). We also consider two cases of zeroth-order setting: "exact f" in which we can query the exact or stochastic function value, and "err. f", in which we can only access the function value with bounded error.
1) first-order
zeroth-order
2) exact f Thm. 4.1
3) em. f
a) deterministic
Thm. 3,4
Thm. C.1
O
const. Y
tuned y b) stochastic
(
O
Thm. 3,5
Thm. 4.2
Thm. C.2
const. Y
0 d 8/2
0
0
d
tuned 7
0
O
The Gaussian homotopy (GH) method is designed to avoid poor stationary points by building a sequence of successively smoother approximations of the original objective function f, and it is expected to find a good stationary point with a small objective value for a non-convex problem. More precisely, using the GH function F F(x, t) with parameter t 0 that satisfies F(z, 0) f(x), the method starts from solving an almost convex smoothed function F(x, (1) with some sufficiently large 4 2 0 and gradually changes the optimization problem F(x,() to the original one f(x) while decreasing the parameter 1. The homotopy method developed so far, then, consists of a double loop structure; the outer loop reduces t, and the inner loop solves ming F(x, t) for the fixed t.
Related research on the GH method The GH method is popular owing to its ease of implementa-
tion and the quality of its obtained stationary points, i.c., their function values. The nature of this method was first proposed in [2]. and it was then successfully applied in various fields, including computer vision [24, 3, 4], physical sciences [12] and computation chemistry [29]. [11] introduces machine learning applications for the GH method, and an application to tuning hyperparameters of kernel ridge regression [25] has recently been introduced. Although there have been recent studies
the GH function F(x, t) [19, 20, 11], all existing GH methods use the double loop approach noted above. Moreover, the best of our knowledge, there are no existing works that give theoretical guarantee for the convergence rate except for [1 [1]]. It characterizes a family of non-convex functions for which a GH algorithm converges to global optimum and derives the convergence rate to an <-optimal solution. However, the family covers only a small part of non-convex functions, and it is difficult check whether the required conditions are satisfied for each function. See Appendix A for more discussion on related work.
Motivation for this work This paper proposes novel deterministic and stochastic GH methods employing a single loop structure in which the decision variables æ and the smoothing parameter t updated the same time using individual gradient/derivative information. Using well-known fact in statistical physics on the relationship between the heat equation and Gaussian convolution of f. together with the maximum principle (e.g., [9]) for the heat equation, we can see that solution (x*, t²) minimizing the GH function F(x, t) satisfies t² = 0; thus, x= is also a solution for (1). This observation leads us single loop GH method (SLGH, in short), which updates the current point (rx, 44) simultaneously for min F(x. l). The resulting SLGGH method can be regarded as an application of the steepest descent method the optimization problem, with (x. as variable. We are then able to investigate the convergence rate of our SLGH method so as to achieve an e-stationary point of (1) and (2) by following existing theoretical complexity analyses.
We propose two variants of the SLGH method: SLGH, and SLGH,, which have different update rules for t. SLGH, updates using the derivative of F(x, t) in terms of based the idea of viewing F(z, t) as the objective function with respect to the variable (xx, t). Though this approach is effective in finding good solutions (as demonstrated in Appendix D.4), it requires additional computational cost due to the calculation of OF To avoid this additional computational cost, we also consider

---

SLGH, that uses fixed-rate update rule for t. We also show that both SLGH, and SLGH, have the same theoretical guarantee.
Table I summarizes the convergence rate of our SLGH method to reach an e-stationary point under a number of problem settings. Since the convergence rate depends the decreasing speed of t, we list two kinds of complexity in the table; details are described in the caption.
We consider the three settings in which available oracles differ. In Case 1), the full (or stochastic) gradient of F(x,1) 1) terms of æ available for the deterministic problem (1) (or stochastic problem (2), respectively). However, in this setting, have calculate Gaussian convolution for deriving GH functions and their gradient vectors, which becomes expensive, especially for high-dimensional applications, unless closed-fome expression of Gaussian convolution is possible. While [18] provides closed-form expression for some specific functions f. such as polynomials, Gaussian RBFs, and trigonometric functions, such problem examples are limited. As Case 2), we extend our deterministic and stochastic GH methods to the zeroth-order setting, for which the convolution computation is approximated using only the function values. Another zeroth-order setting, Case 3), is also considered in this paper: the inexact function values (more precisely, the function value with bounded error) can be queried similarly as in the setting in [14]. See Appendix for more details.
Although no existing studies have analyzed the complexity of double loop GH method to find an c- that its inner loop requires the same complexity GD (gradient descent) method up to constants. Furthermore, as noted above, the complexity of the SLGH method with a tuned hyperparameter matches that of GD method. Thus, the SLGH method becomes faster than double loop GH method by around the number of outer loops. The SLGH method is also superior to double loop GH methods from practical perspective, because in order to ensure convergence of their inner loops, we have to set the stepsize conservatively, and furthermore a sufficiently tuned terminate condition must be required.
stationary point,
Contributions We can summarize our contribution as follows:
(1) We propose novel deterministic and stochastic single loop GH (SLGH) algorithms and analyze their convergence rates an e-stationary point. As far as we know, this the first analysis of convergence rates of GH methods for general non-convex problems (1) and (2). For non-convex optimization, the convergence rate SL.GH with a tuned hyperparameter becomes consistent with the convergence rate of gradient descent, even though the problem to be solved is gradually changed due At this time, the SLGH algorithms become faster than a double loop one by around its number of outer loops.
(2) We propose zeroth-order SLGH (ZOSLGH) algorithms based on zeroth-order estimators of gradient and Hessian values, which are useful when Gaussian smoothing convolution is difficult, We also consider the possibly non-smooth case which the accessible function contains error, and we derive the upper bound of the error level for convergence guarantee.
(3) We empirically compare our proposed algorithm and other algorithms in experiments, including artificial highly non-convex examples and black-box adversarial attacks. Results show that the proposed algorithm converges much faster than existing double loop GH method, while it is yet able to find better solutions than are GD-based methods.
Standard Gaussian homotopy methods
Notation:
For an integer N, let [N] == (1, ... N}. We express X(N] := (x for a set of some vectors. We also express the range of the smoothing parameter t as T := [0, f1), where f an initial value of the smoothing parameter. Let ||. denote the Euclidean norm and (00 Ia) denote the d-dimensional standard normal distribution.
Let us first define Gaussian smoothed function.
Definition 2.1. Gaussian smoothed function F(x,t) of f(x) is defined as follows:
F(x, 1) Eoo (/( tn)] / [(x ky)kky)dy
(3)
where k(y) (2TT) exp (-11v11/2) is referred to the Gaussian kemel.
3

---

The idea of Gaussian smoothing is to take an expectation over the function value with a Gaussian distributed random vector u. For any O, the smoothed function F(x, t) is C function, and plays the role of a smoothing parameter that controls the level of smoothing.
Here, let us show the link between Gaussian smoothing and the heat equation [28]. The Gaussian smoothing convolution is basically the solution of the heat equation [28].
a 0t A,ú, a(: f()))
(4)
where A denotes the Laplacian. The solution of the heat equation is ((x,
( f [(y) Uل= - dy. This can be made the same the Gaussian smoothing function F(z, () by scaling its coefficient, which only changes the speed of progression.
Corollary 9 in [21] shows sufficient condition for ensuring that f has the asymptotic strict convexity which the smoothed function Fxx, t) becomes convex if sufficiently large smoothing parameter t is chosen. On this basis, the standard GH method, Algorithm 1, starts with (almost) convex optimization problem F(x,1) t) with large parameter value E R and gradually changes the problem toward the target non-convex f.) F(., 0) by decreasing t gradually. [11] reduces t by multiplying by a factor of 1/2 for each iteration k. [20] focuses more on theoretical work w.r.t. the general setting and do not discuss the update rule for t.
Algorithm Standard GH method (120, 11))
Require:
Objective function f. iteration number T, sequence (4,,..., (T} satisfying 1 > ... lT. Find a solution xi for minimizing (1),
for k = 1 to T do
Find a stationary point TK-1 of F(x, tx41) with the initial solution 2g.-
end for return ZT
3 Single loop Gaussian homotopy algorithm
function ((x) Lo-Lipschitz with a constant Lo if for any x, y E R4, h(v) < La La - yl holds. In addition, h(x) is Ly-smooth with a constant L, if for any x, R |[Vh(z) Vh(y)] v L || y/ holds. Let us here list assumptions for developing algorithms with convergence guarantee. Assumption A1.
ii Objective function J satisfies sup B. (or + [u)]] < oo (In the stochastic setting, satisfies supxERd. E., [1f(x (x + tu: E)]] < co).
(ii) The optimization problem (1) has an optimal value f"
(iii) Objective function f(x) is Lo-Lipschitz and Lmssohhth on Rd (In the stochastic setting, f(r: {) is Li-Lshhc and Lm-stooth on Rd in terms of x for any {
Assumption (i) for making t(r,t) well-defined and enabling to exchange the order of differentiation and integration, as well as Assumption (ii). is mandatory for theoretical analysis with the GH method. Assumption (iii) is often imposed for gradient- methods. This a regular boundedness and smoothness assumption in recent non-convex optimization analyses (see e.g., [1, 17, 7J).
In the remainder of this section, we consider the nature of the GH method and propose a more efficient algorithm, a SLGH algorithm. We then provide theoretical analyses for our proposed SLGH algorithm.
3.1 Motivation
The standard GH algorithm needs to solve an optimization problem for a given smoothing factor in each iteration and manually reduce i, e.g., by multiplying some decreasing factor. To simplify this process, we consider an alternative problem as follows:
minimize F F(x, t). 1ET
55)

---

where F(x, t) is the Gaussian smoothed function of fzz). This single loop structure can reduce the number of iterations by optimizing z and the same time.
The following theorem is a (almost) special case of Theorem 6 in [9], which is studied in statistical physics but may not be well-known in machine learning and optimization communities. This theorem shows that the optimal solution of (5) (a* tt) satisfies t* = O, and thus xx is also a solution for (1). Therefore, we can regard F (xz t) as an objective function in the SLGH method.
Theorem 3.1. Suppose that Assumptions Al (i) and (ii) are satisfied. Unless f is constant a.c., the minimum of the GH function F(x, t) will be always found at = O, and the corresponding æ will be an optimal solution for (1).
We present a proof of this theorem in Appendix B.1. The proof becomes much easier than that in [9] due to its considering specific case.
Let us next introduce an update rule for & utilizing the derivative information. When we solve the aP problem (5) using gradient descent method, the update rule for t becomes tx+1 = tx 1f σt where 7 is a step size. The formula (4) in the heat equation implies that the derivative af is equal to the Laplacian F, i.e., aF
ät
Ør (x)). where Hx(r) is the Hessian of F in terms of æ. Since (z))) represents the sharpness of minima [8], this update rule can sometimes decrease quickly around a minimum and find a better solution. See Appendix D.4 for an example of such a problem.
3.2 SLGH algorithm
Let us next introduce our proposed SLGH algorithm, which has two variants with different update rules for (: SL.GH with a fixed-ratio update rule (SLGH,) and SL.GH with a derivative update rule (SLGH,). SLGH, updates t by multiplying decreasing factor y (c.g.. 0.999) at each iteration. In contrast to this, SLGHa updates É while using derivative information. Details are described in Algorithm 2. Algorithm 2 transforms double loop Algorithm into single loop algorithm. This single loop structure can significantly reduce the number of iterations while ensuring the advantages of the GH method.
Algorithm 2 Deterministi//Soocastti Single Loop GH algorithm (SLGH)
Require: Iteration number T, initial solution initial smoothing parameter t1, step size 3 for x, step size v) for decreasing factor 7 E (0, 1), sufficient small positive value for l = 1 to T do
3G., G2 G {
Va F(x,, (s) (determ.)
1k+1
Va (ak, Ex), &A ~ Pstooc.
ytx (SLGH,)
aF(a du) (determ.)
1++1 -
max (axxmmnn( (4+ -n,,, rla), ef (SIGH.,) G.
06
EN ~ P (stoc.)
Ot
end for
In the stochastic setting of (2), the gradient of F(x, 1) in terms of x is approximated by Vz, () with randomly chosen &, where F F(ar, 1; {) is the GH function of [(x;; E). Likewise, the derivative of F(x, t) in terms of t is approximated by (F(2.).) de The stochastic algorithm in Algorithm 2 uses one sample Ex. We can extend the stochastic approach by M E.M vzF((z, E.) with samples (E....., EMr) } of some batch size M, but for the sake of simplicity, we here assume one sample in each iteration. In this setting, the gradient complexity matches the iteration complexity; thus, we also use the term "iteration complexity" in the stochastic setting. Other methods, such as applied here. According to Theorem 1. the final smoothing parameter needs to be zero. Thus, we
minibatch one by approximating Fz, t)
method [27] and Adam [15] can also be
2 Althooghh the assumptions in Theorem 3.1 are stronger than those in the theorem proved by Evans, the statement of ours is also stronger than that of his theorem, in sense that our theorem guarantees that all optimal solutions satisfy = 0.
5

---

multiply y by even in SLGH, when the decrease of t is insufficient. We also assure that is larger than sufficiently small positive value e' during an update to prevent from becoming negative.
3.3 Convergence analysis for SLGH
Let us next analyze the worst-case iteration complexity for both deterministic and stochastic SLGHs, but, before that, let first show some properties for Gaussian smoothed function F(x: t) under Assumption A1 for the original function f(z). In the complexity analyses in this paper, we always assume that 7 is bounded from above by universal constant 7 < which implies 1/(1-7) O(1).
Lemma 3.2. Let f(x) be a Lo-Lisschitz function. Then, for any > O, its Gaussian smoothed function F(x, 1) will then also be Lo-Lápschitz in terms of x. Let (x) be Li Li-shooth function. Then, for any & >> O, F(r, 1) will also be Li-smooth in terms of x.
Lemma 3.2 indicates that Assumption Al given to the function f(x) also guarantees the same properties for F(x, t). Below, we give some bounds between the smoothed function F(x, t) and the original function (x))
Lemma 3.3. Let f be La-Lápschitz function. Then, for any E Rdd F(x, 1) is also Lovd- Lipschitz in terms of I, for any x, smoothing parameter values L1, b2 >> O, we have [F(x, (1) F(r, t2)l S Lovdlt -2).
On the basis of Lemmas 3.2 and 3.3, the convergence results of our deterministic and stochastic SL.GH algorithms can be given as in Theorems 3.4 and 3.5, respectively. Proofs of the following theorems are given in Appendix B.2. Let us first deal with the deterministic setting.
Theorem 3.4 (Convergence of SLGH, Deterministic setting). Suppose Assumption Al holds, and [1. Then, for any setting
let f = Tg'; k' ke(T) [ Set the stepsize for as 3 1 1/T.,
of the parameter 7, it satisfies VV S e with the iteration complexity of T = 0 ( 12) Further, if we choose y S d x-)))), the iteration complexity can be bounded as T = 0(1/2)
This theorem indicates that if we choose y close to 1, then the iteration complexity can be O (d3/2/2) which is (d3/2) times larger than the 0 -iteraaioon complexity by the standard gradient descent methods [22]. However, we can remove this dependency on d to obtain an iteration complexity matching that of the standard gradient descent, by choosing y S d d as shown in Theorem 3.4. Empirically, settings of y close to 1, e.g., = 0.999, seem to work well enough, as demonstrated in Section 5.
An inner loop of the double loop GH method using the standard GD requires the same complexity as the standard GD method up to constants since the objective smoothed function of inner optimization problem is L1 -smooh function. By considering the above results, we can see that the SLGH algorithm becomes faster than the double loop one by around the number of outer loops.
To provide theoretical analyses in the stochastic setting, we need additional standard assumptions. Assumption A2.
(i) The stochastic function f(x; {) becomes an unbiased estimator of fxx) That is, for any x E RRd, f(x) = IE [f(;; {)] holds.
(ii) For any x E Rdd the variance of the stochastic gradient oracle bounded as - vf(+)]] s o². Here, the expectation is taken w.r.t. random vectors
Eg {Ex)
The following theorem shows the convergence rate in the stochastic setting.
Theorem 3.5 (Convergence of SL.HH, Stochastic setting). Suppose Assumptions Al and A2 hold. Take kn : =00(1/²) and 2zz := O (log,, min min(d-1/2 .d= dd332((22) and define Ko = min kn, kz). Let & == TKs, where k is chosen from a uniform distribution over (Ko + 1, + 2....,T), Set the stepsize for x as 3 = min {1/L,, 1/VT }. Then, for any setting of the parameter 7, satisfies E|IV fi] S e with the iteration complexity T = O (d/E² + /3/2 /2) where the expectation taken w.r.l random vectors {Ex)- Further, if we choose 7 S (max(dd/2, (2/2/223//2222 (3/2(2)) -2(c*), the iteration complexity can be bounded as T ((1/2))
T).

---

We note that the iteration complexity of T = (11/ct) for sufficiently small matches that for the standard stochastic gradient descent (SGD) shown, e.g., by [10].
Zeroth-order single loop Gaussian homotopy algorithm
In this section, we introduce a zeroth-order version of the SLGH algorithms. This ZOSLGH algorithm proposed for those optimization problems in which Gaussian smoothing convolution is difficult to compute, in which only function values can be queried.
4.1 ZOSLGH algorithm
For cases in which only function values accessible, approximations for the gradient in terms of and derivative in terms are needed. [23] has shown that the gradient of the smoothed function F(x, 1) can be represented as
(x,(t,t) = - (L ; tu) f())lu), u (o(,
(6)
Thus, the gradient V, (xx 1) can be approximated by an unbiased estimator dn (z,, 1;
92 (z, uu) (f(x + tu) - f(x)),, (a)
The derivative OF is equal to the trace of the Hessian of F(x, t) because the Gaussian smoothed dt function is the solution of the heat equation OF tr(Hr(z)). We estimate tr(Hr(x)) the basis of the second order Stein's 's identity [26] as follows:
(vv Ia)
H (z)
(f(x + tu) f(x)), v~ Io)
(8)
t2
Thus, the estimator for derivative can be written as:
Or (3r, 1;1)= (v d)(s(r + (v) [(x)) NO..
f²
As for the stochastic setting, f(z) in (7) and (9) is replaced by the stochastic function f(x;() with some randomly chosen sample ç. The gradient V, (xx () of its GH function F(x, t; E) can then be approximated by Gz (2r, 1; E, f(a+ (aug)- f(=nE)) and the derivative oF can be approximated o7 by G,(x,ttE,v) (v e- (-d)(f((+tt tv=g) f(rnE)) (see Algorithm 3 for more details).
Algorithm 3 Deterministic/Soohassie Zeroth-Order Single Loop GH algorithm (ZOSLGH)
Require: Iteration number T, initial solution #1, initial smoothing parameter 4, step size 3 for x, step size v for decreasing factor 7 E (0, 1), sufficient small positive value for = to do
Sample uy from (0,
0k+1 Øb 3Gzzus Gu,u = {{
(T tu ux) (determ.) Ga(an, lui Ex, wa), En P (stoc.)
Sample UR from (0,
1++1 {
7le (SLGH,)
max mmin - 1,G,, 744),e) (SI.H.) Gep = Te (determ.)
Go Eu uw). Ea ~ P (stoc.)
end for
4.2
Convergence analysis for ZOSLGH
We can analyze the convergence results using concepts similar to those used with the first-order SL.GH algorithm. Below are the convergence results for ZOSLGH in both the deterministic and stochastic
7

---

settings. Proofs of the following theorems are given in Appendix B.3, and the definitions of i are provided in the proofs. We start from the deterministic setting, which aimed the deterministic problem (1).
Theorem 4.1 (Convergence of ZOSLGH, Deterministic setting). Suppose Assumption Al holds. Take k == Odd/e 2) and h:2 == (log, , d d=1/2), and define kn min k1 k2). ). Let == T'k, where k' is chosen from uniform distribution over {Kg + 1. + 2..... T.). Set the stepsize for as 3 = 1/(2(d + 4)L,). Then, for any setting of the parameter ", &t satisfies E I with the iteration complexity of T ((d² ),), where the expectation is taken w.r.t random vectors
{ux) and {va). Further, if we choose 7 S d-D(éé (d), the iteration complexity can be bounded as T (dd/e).
This complexity of O(d/²) fory S d= matches that of zeroth-order GD (ZOGD) [23].
Let us next introduce the convergence result for the stochastic setting. As shown in [10], if we take the expectation for our stochastic zeroth-order gradient oracle with respect to both & and u, under Assumption A2 (i), we will have
Pe,uiGz (2, 1; &, w)] R. (x, u) u]] Fa,
Therefore, Ca == -fxx u behaves similarly to ug in the deterministic setting.
Theorem 4.2 (Convergence of ZOSLGH, Stochastic setting). Suppose Assumptions Al and A2 hold. Take kn == ((d/e*) and l22 == O (log,, d-1/2),, and define kn min(ka, k2)- Let à == ww, where K' is chosen from uniform distribution over (Ko 1, kg 2, ..... ,T). Set the stepsize for Then, for any setting of the parameter 7 &o satisfies
x as = min 2(d+-))Li' V(T-ko)(a+1)
with the iteration complexity of D(d//e)) where the expectation is taken w.r.t. random vectors {ux). {vx). and {Ex]- Further, if we choose I d- /d), the iteration complexity can be bounded as T Odd/e).
S f())ll
This complexity of Oddee) yor s /d)) also matches that of ZOSGD [10].
5 Experiments
In this section, we present our experimental results. We conducted two experiments. The first was to compare the performance of several algorithms including the proposed ones, using test functions for optimization. We were able to confirm the effectiveness and versatility of our SLGH methods for highly non-convex functions. We also created a toy problem in which ZOSL.GH,, which utilizes the derivative information St for the update of t, can decrease quickly around minimum and find a better solution than that with ZOSLGH, The second experiment was to generate examples for a black-box adversarial attack with different zeroth-order algorithms. The target models were well-trained DNNS for CIFAR-10 and MNIST, respectively. All experiments were conducted using Python and Tensorflow on Intel Xeon CPU and NVIDIA Tesla P100 GPU. We show the results of only the adversarial attacks due to the space limitations; other results are given in Appendix D.
Generation of per-image black-box adversarial attack example. Let consider the unconstrained black-box attack optimization problem in [6], which is given by
minimize fx) : (00((055tanh (2a) x)) + ||0.5tanh(tanh -((a) + x) all? =
where À is regularization parameter, is the input image data, and tanh is the element wise operator which helps climinate the constraint representing the range of adversarial examples. The first term e(-) of f()) is the loss function for the untargeted attack in [5], and the second term Le distortion is the adversarial perturbation (the lower the better). The goal of this problem to find the perturbation that makes the loss E(-) reach its minimum while keeping L2 distortion small as possible. The initial adversarial perturbation Zo was set to O. We say a successful attack example has been generated when the loss E(-) is lower than the attack confidence (e.g., g.. le 10).
Let us here compare our algorithms, ZOSLGH, and ZOSI.GHa, to three zeroth-order algorithms: ZOSGD [10], ZOAdaMM [6], and ZOGradOpt [11]. ZOGradOpt is homotopy method with

---

double loop structure. In contrast to this, ZOSGD and ZOAdaMM are SGD-based methods and thus do not change the smoothing parameter during iterations.
Table 2 and Figure show results for our experiment. We can see that SGD-based algorithms are able succeed in the first attack with far fewer iterations than GH algorithms (e.g., Figure 1(a), Figure I(d), Accordingly, the value of L2 distortion decreases slightly more than GH methods. However, SGD-based algorithms have lower success rates than do our SLGH algorithms. This is because SGD-based algorithms remain around a local minimum I = 0 when it is difficult to attack, while GH methods can escape the local minima due to sufficient smoothing (e.g.. Figure 1(b), Figure I())). Thus, the SLGH algorithms are, on average, able to decrease total loss over that with SGD-based algorithms. In a comparison within GH methods, ZOGradOpt requires more than 6500 iterations to succeed in the first attack due to its double loop structure (e.g.. Figure 1(c), Figure (()). In contrast this, our SI.GH algorithms achieve high success rate with far fewer iterations. Please note that SLGH, takes approximately twice the computational time per iteration than the other algorithms because needs additional queries for the computation of the derivative in terms See Appendix E for more detailed presentation of the experimental setup and results.
Table 2: Performance of a per-image attack over 100 images CIFAR-ID under 7' 10000 iterations. "Succ. rate" indicates the ratio of success attack, "Avg. iters to 1st succ." is the average number of iterations reach the first successful attack. "Avg. L2 (succ.)" is the average of L2 distortion taken among successful attacks, and "Avg. total loss" is the average of total loss f(z) over 100 samples. Please note that the standard deviations are large since the attack difficulty varies considerably from sample to sample.
Avg. iters succ.
Avg. L2 (succ.)
Methods
Suec. rate
Avg. total loss
SGD algo.
ZOSGD
88%
835 + 1238
0.076 = 0.085
27.70 + 74.80
ZOAdaMM
85%
3335 + 2634
0.050 0.055
20.24 + 62.48
GH algo.
ZOGradOpt
65%
6789 + 1901
0.249
0.159
41.45 + 76.04
ZOSLGH, (7 = 0.999)
93%
4979 +: 756
0.246
0.178
14.26 + 54.61
ZOSI.GH (7 0.999)
92%
4436 + 805
0.150 0.084
16.49 + 58.69
Total ICSS
7000 0055
20 500
COAMIU 5100
300
2008
1000
2004
8010
Baralians
CIFAR- 10, Image ID = 56
(b) CIFAR-10, Image ID 34
(c) CIFAR 10, Image ID 102
Tokal 003
2500
750
1300 33M ba vibrrr
E000 1580
1130
900 2008
1B3 1089 1200 20U0
Baraloon
Barations
(d) MNIST, Image ID 32
(c) MNIST, Image ID 45
(f) MNIST, Image ID 95
Total loss for generating per-image black-box adversarial examples for different images Figure of CIFAR-10 and MNIST (log scale).

---

Summary and future work
We have presented here the deterministic/stocassti SLGH and ZOSLGH algorithms well their convergence results. They have been designed for the purpose of finding better solutions with fewer iterations by simplifying the homotopy process into single loop. We consider this work be a first attempt to improve the standard GH method.
Although this study has considered the case in which the accessible function contains some error and is possibly non-smooth, we assume the underlying objective function to be smooth. Further work should be carried out investigate the case in which the objective function itself is non-smooth.
This work was supported by JSPS KAKENHI Grant Number 19H04069, JST ACT-I Grant Number JPMJPR IUS, and JST ERATO Grant Number JPMJER
Acknowledgements
10

---

References
[1] S. Aydore, T. Zhu, and D. P. Foster. Dynamic local regret for non-convex online forecasting. In Advances in Neural Information Processing Systems, pages 7982-7999 2019.
[2] A. Blake and Zisserman. Visual reconstruction. MIT press, 1987.
[3] Brox and Malik. Large displacement optical flow: descriptor matching in variational motion estimation. IEEE transactions pattern analysis and machine intelligence, 33(3):500- 513, 2010.
[4] G. Bourmaud C. Zach. Descending, lifting or smoothing: Secrets of robust cost optimization. In Proc. ECCV, volume 12, pages 558-574, 2018.
[5] N. Carlini and D. Wagner. Towards evaluating the robustness of neural networks. In 2017 IEEE Symposium Security and Privacy, pages 39-57, 2017.
[6] X. Chen, S. Liu, K. Xu, X. Li, Lin, M. Hong, and D. Cox. Zo-adamm: Zeroth-order adaptive momentum method for black-box optimization. In Advances in Neural Information Processing Systems, pages 7204-7215, 2019.
[7] A. Cutkosky and F. Orabona. Momentum-based variance reduction in non-convex sgd. In Advances in Neural Information Processing Systems, pages 15236-15245. Curran Associates, Inc., 2019.
[8] Laurent Dinh, Razvan Pascanu, Samy Bengio, and Yoshua Bengio. Sharp minima generalize for deep nets. In Proceedings the 34th International Conference on Machine Learning, pages 1019-1028, PMLR, 2017.
[9] L.C. Evans. Partial Differential Equations. American Mathematical Society, 2010.
[10] S. Ghadimi and G. Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 2334):2341-230 2013.
[11] E. Hazan, K. Levy, and Shalev-Shwarte On graduated optimization for stochastic non- convex problems. In Proceedings of the 33rd International Conference on Machine Learning, pages 1833-1841, 2016.
[12] A. A. Hemeda. Homotopy perturbation method for solving systems of nonlinear coupled equations. Applied Mathematical Sciences, (193-96):4777-48000 2012.
[13] Jain and P. Kar. Non-convex optimization for machine learning. Foundations and Trends in Machine Learning, (0(3-)):142 336, 2017.
[14] C. Jin, L. T. Liu, R. Ge, and M. I. Jordan. On the local minima of the empirical risk. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 4901 4910, 2018.
[15] D. Kingma and J. Ba. Adam: method for stochastic optimization. In 3rd International Conference on Learning Representations, 2015.
[16] H. Li, Z. Xu, G. Taylor, C. Studer, and T. Goldstein. Visualizing the loss landscape of neural nets. In Advances Neural Information Processing Systems, pages 6389-6399, 2017.
[17] P. Mertikopoulos, N. Hallak, A. Kavis, and V. Cevher. On the almost sure convergence of stochastic gradient descent in non-convex problems. In Advances in Neural Information Processing Systems, pages 1117-1128. Curran Associates, Inc., 2020.
[18] H. Mobahi, Closed form for some gaussian convolutions. arXiv preprint arXiv: 160..0:6602.0610 2016.
[19] H. Mobahi and J. W. Fisher III. On the link between gaussian homotopy continuation and convex envelopes. In Energy Minimization Methods in Computer Vision and Pattern Recognition, pages 43-56, 2015.
11

---

[20] H. Mobahi and J. W. Fisher III. A theoretical analysis of optimization by gaussian continuation.
In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
[21] H. Mobahi and Ma. Gaussian smoothing and asymptotic convexity. Technical report, Coordinated Science Laboratory, University of Illinois at Urbana-Champaigu 2012.
[22] Y. Nesterov. Introductory Lectures Convex Optimization: basic course. Kluwer Academic Publishers, 2004.
[23] Y. Nesterov and V. Spokoiny. Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17(2):527-566, 2017.
[24] M. Nielsen. Graduated non-convexity by smoothness focusing. In Proceedings of the British Machine Vision Conference, pages 60.1-60.10 BMVA Press, 1993.
[25] W. J. Shao, C. Geißler, and F. Sivrikaya. Graduated optimization of black-box functions. arXiv preprint 1rXiv:1906.01279) 2019.
[26] C. Stein. A bound for the error in the normal approximation to the distribution of a sum of de- pendent random variables. In Proceedings of the Sixth Berkeley Symposium Mathematical Statistics and Probability, Volume 2: Probability Theory. The Regents of the University of California, 1972.
[27] Sutskever, J. Martens, G. Dahl, and G. Hinton. On the importance of initialization and momentum in deep learning. In Proceedings of the 30th International Conference on Machine Learning, pages 1 1139 147. PMLR, 2013.
[28] D. V. Widder. The heat equation. Academic Press, 1976.
[29] Z. Wu. The effective energy transformation scheme as special continuation approach to global optimization with application to molecular conformation. SIAM Journal Optimization, 6(3):748-768, 1996.
12


Reviews:
[{"review_id": "da4qxcV28co", "reviewer": "Reviewer_WqLq", "summary": "This paper studies the Gaussian homotopy method for finding stationary points for non-convex optimization problems. Novel deterministic and stochastic single loop Gaussian homotopy algorithms are proposed, where the decision variable $x$ and the smoothing parameter $t$ are simultaneously updated, in contrast to the double loop Gaussian homotopy algorithms in the existing literature. Also, the corresponding zeroth-order algorithms are developed based on zeroth-order estimators of gradient and Hessian. The convergence rates of the proposed algorithms are analyzed. Empirical evaluations are provided to corroborate the theory.", "questions": "1. For $\\text{SLGH}_{\\mathrm{d}}$, the update of $t_k$ depends on some small $\\epsilon > 0$. What's the role of this $\\epsilon$? What's the relationship between this $\\epsilon$ and the one in the theorems as the error guarantee on the gradient norm?\n\n2. Following the above question, it seems to me that the proof for Theorem 3.4 only works for $SLGH_r$. \nThis is because in line 83 in the appendix, the proof requires $\\sum_{k=1}^T t_k \\leq \\sum_{k=1}^T t_1\\gamma^{k-1}$, which is not necessarily true for $\\text{SLGH}_{\\mathrm{d}}$, as $t_k$ there is always at least $\\epsilon$. \n\n3. In the theorem statements, the $\\hat x$ should be more specified. According to the proofs, the guarantee should be $\\max_{k\\in[T]} \\|\\nabla f(x_k)\\|\\leq \\epsilon$.\n\n4. From the intuition behind the Gaussian homotopy method, this kind of algorithm should perform better than the vanilla gradient descent because it is expected to find a better solution by smoothing the geometry. However, this is not reflected in the theory proved in this paper. ", "limitations": "The authors have adequately addressed the limitations of their work.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper is well-motivated and well-written, and overall the content is easy to follow. The idea to simultaneously update $(x,t)$ is intuitive and natural. The convergence analysis seems to be standard, and I don't see much novelty in this regard (maybe the authors can highlight if there is any special difficulty). The empirical study looks good to me.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Rx45bwRnS5L", "reviewer": "Reviewer_T91c", "summary": "The paper proposes a single loop framework to deal with Gaussian Homotopy (GH) method for non-convex (deterministic and stochastic) optimization $f(x)$. GH approach aims to solve successively smooth surrogates $F(x,t)$ of $f(x)$ for $t \\geq 0$ such that at convergence the minimization of $F(x,0)$ corresponds to a stationnary point of the initial problem. The proposed method coined SLGH (single loop GH) relies on a gaussian smoothing convolution $F(x,t)$ of $f$ that is simultaneously optimized w.r.t to $x$ and $t$ using a (projected-like) gradient descent. SLGH differs from classical approaches that optimizes $F(x,t)$ for pre-specified values of $t$. Two variants of SLGH are provided based respectively on first-order and zeroth-order gradient descent. Convergence analyses in terms of iteration complexity are conducted in each setting. Experimental evaluations on adversarial image crafting illustrate the behaviour of the methods.", "questions": "* In practice the choice of the step-sizes $\\beta$  and $\\eta$ may not be obvious. Is a line-search strategy used to appropriately estimate those parameters?\n* Algorithms 2 and 3 use the parameter $\\epsilon$. Is it the same parameter that is applied in Theorems 3.4, 3.5, 4.1 and 4.2?\n* The paper claims that empirically, settings of $\\gamma$ close to 1, e.g., $\\gamma= 0.999$ work well in practice. Is such a choice efficient computationally? Because it probably induces a slow decrease of $t$ and hence a high iteration complexity.\n* Why the same update policy is not applied to $t$ for SLGH_r in Algorithms 2 and 3?\n* Computation of the Gaussian convolution $F(x,t)$ of $f(x)$ can be computationally demanding, rendering per iteration costly in Algorihm2. Are there typical obbjective functions that are suited for firs-order SLGH?\n* When dealing with stochastic setting of SLGH, does the convergence improve when using a batch size greater than 1?\n* Can the paper provide empirical evaluations of the methods illustrating the derived convergence rates? Also it would be interesting to show convergence results in terms of computation time and compared to plain gradient descent method for instance.\n* Can the authors report fooling rate for different levels of L2 distortion to allow a fair and easy comparison of the methods? ", "limitations": "The paper  discusses the broader impact of the proposed approaches. On my view point the work does not raise any specific issues. \n", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "* The paper is well written and  well  organized. The rationale behind the proposed SLGH is justified and the new aspects brought by  the approach are stated clearly.\n\n* As for a strength, the paper proposes a principled way to design the smoothing function $F(x,t)$ using Gaussian convolution applied to $f(x)$. It also establishes that the minimum of $F(x,t)$ w.r.t $t$ is achieved at $t=0$ giving then the solution to the minimization of $f(x)$. However computing $F(x,t)$ will be a hard task in general leaving the first order optimization method non-applicable in practice. This is mitigated by the proposition of a zeroth-order approach.\n\n* The optimization scheme in Algorithm 2 is rather standard for solving $\\min_{x, t \\geq 0} F(x,t)$. The interesting fact is that $F(x,t)$ inherits boundness and Lipschitzness properties of $f$ that helps implementing Algorithm 2. Key results of the papers are the theoretical iteration complexities to reach an $\\epsilon$ convergence on the gradient norm. Similar results are derived for zeroth-order methods. Generally speaking the first-order methods exhibit reduced iteration complexity.\n\n* GH methods aim to provide solution to the original problem as the minimizer of $F(x,t=0)$ at convergence. However Algorithms 2 and 3 ouput the sought solution as a minimizer of $F(x,t=\\epsilon)$ for some non-null positive $\\epsilon$. It would be interesting to analyze convergence in the iterates $x_k$.\n\n* Reported empirical evaluations in Section 5 are questionable and to argue for the proposed methods. As for the average number of iterations to reach the first successful attack, SGD algorithms perform better than GH methods. Regarding pediction peformance the paper reports the average of total loss $f(x)$ which is meaningless in the context of adversarial attack. The most relevant metric might be the fooling rate as one is interested in the success of attack not in the value of the loss function. Also the performances are compared for different levels of L2 distortion which is highly questionable. As a fair comparison, the considered methods should be evaluated for the same L2 distortion error. \n\n* The authors provide relevant feedback to most reviewers' concerns. Nevertheless the reported experiments on adversarial attack in Section 5 do not prove the effectiveness of the GH approaches. Indeed,  the proposed GH methods lead to a smaller objective value compared to competitors (SGD algos). However they lead to higher fooling rates of the network but at the price of a higher perturbation. Therefore the attacks by GH cannot be claimed better than the ones by SGD algos.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "MVOKvaVMaay", "reviewer": "Reviewer_JQgj", "summary": "In this work, the authors studied the Gaussian homotopy (GH) method for non-convex optimization problems in deterministic and stochastic settings. Compared to the existing GH-based method with the two-loop scheme, they proposed a single-loop GD method that can update the smoothing parameter and optimization variable at the same time. In particular, they showed the computational complexity of the proposed methods in different settings. Finally, experimental results are reported to demonstrate the potential of the proposed methods. ", "questions": "\n(${\\bf 1}$) The idea of the Gaussian smoothed function in Definition 2.1 is very similar to that in Eq (17) of [8]. Could the authors elaborate on the connections and differences between the gaussian homotopy method and the smoothing gradient descent method in [8] and the related paper, like the iteration complexity?\n\n(${\\bf 2}$) In the introduction part, the authors mentioned that \"The Gaussian homotopy is designed to avoid poor stationary points...\". However, in the remaining part of the paper, it seems that the authors cannot illustrate this advantage of the GH method. Could the authors demonstrate this point theoretically or empirically?\n\n(${\\bf 3}$) The smoothing methods usually employ the fixed-ratio update rule for updating the smoothing parameter $t$. In Section 3.2, the authors proposed an interesting derivative update rule. Compared to the fixed-ratio update rule, what is the benefit of the derivative update rule? Can this significantly improve algorithm performance?\n\n(${\\bf 4}$) Could the proposed method be easily extended to the constrained setting? \n", "limitations": "No", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nStrengths: (${\\bf 1}$)  This work has a good contribution to the Gaussian homotopy (GH) methods. The authors not only developed a single-loop GD method but also extended it to the stochastic and zeroth-order settings. Moreover, the complexity analysis of the proposed methods is provided. \n\n(${\\bf 2}$) Overall, the paper is well-written and I think that the authors made good enough technical contributions. \n\nWeaknesses: (${\\bf 1}$) It seems that Assumption A.1 (i) is rather strict, which requires the objective function $f$ to be bounded. Many functions arising in applications don't satisfy this assumption. Thus, this really limits the applications of the GH methods. Note that in [8], no such assumption is imposed. Could this assumption be relaxed? \n\n(${\\bf 2}$) In Figure (1), to better compare function values of the tested method, the authors should use the log-scale plot on the y-axis. From the current figures, the loss function values of most of the tested methods look the same. ", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept