Global Optimization with a Power-Transformed Objective and Gaussian Smoothing
Authors: Chen Xu
Venue: ICML 2025 poster (2025)
Keywords: Nonconvex optimization
zeroth-order
Gaussian smoothing
exponential power transform
Primary area: optimization->zeroorder_and_blackbox_optimization
TL;DR: We propose a zeroth-order method for optimizing a non-convex function, which applies Gaussian smoothing and Stochastic Gradient Ascent to the (exponential) power of the objective.

Abstract: We propose a novel method, namely Gaussian Smoothing with a Power-Transformed Objective (GS-PowerOpt), that solves global optimization problems in two steps: (1) perform a (exponential) power-$N$ transformation to the not necessarily differentiable objective $f:\mathbb{R}^d\rightarrow \mathbb{R}$ and get $f_N$, and (2) optimize the Gaussian-smoothed $f_N$ with stochastic approximations. Under mild conditions on $f$, for any $\delta>0$, we prove that with a sufficiently large power $N_\delta$, this method converges to a solution in the $\delta$-neighborhood of $f$'s global optimum point, at the iteration complexity of $O(d^4\varepsilon^{-2})$. If we require that $f$ is differentiable and further assume the Lipschitz condition on $f$ and its gradient, the iteration complexity reduces to $O(d^2\varepsilon^{-2})$, which is significantly faster than the standard homotopy method. In most of the experiments performed, our method produces better solutions than other algorithms that also apply the smoothing technique.

Global Optimization with a Power-Transformed Objective and Gaussian
Smoothing
Chen Xu
Abstract
cally optimal solution (Mertikopoulos et al., 2020; Lei et al., 2019; Choromanska et al., 2015).
We propose a novel method, namely Gaussian Smoothing with a Traef-rranfor Objective (GS-PowerOpt), that solves global optimization problems in two steps: (1) perform (exponen- tial) power-N transformation to the not necessar- ily differentiable objective f : I2 + I and get fN. and (2) optimize the Gaussian-mmoothed JN with stochastic approximations. Under mild con- ditions on /. for any 8 > O, we prove that with sufficiently large power Ns. this method con- verges to solution in the 5-neighborhood of f's global optimum point, at the iteration complexity of e If we require that f is differentiable and further assume the Lipschitz condition on f and its gradient, the iteration complexity reduces to O which is significantly faster than the standard homotopy method. In most of the ex- periments performed, our method produces better solutions than other algorithms that also apply the smoothing technique.
Gaussian smoothing (e.g., Section 3 in (Nesterov & Spokoiny, 2017)) refers to convolving S with Gaussian density to obtain a surrogate objective
(M) == (e
(2)
where N denotes multivariate Gaussian distribution, O is called the scaling parameter, and Ia denotes a d x d identity matrix. The smoothing effect possibly eliminates certain local extremes of the objective, and this technique is applied by the widely used homotopy methods for global optimizations.
Homotopy (e.g., (Mobahi & Fisher, 2015)), also called the graduated continuation, is class of methods that aim to find global solution to (1), with many applications in machine learning (Xu et al., 2016; Iwakiri et al., 2022). It converts the original problem to
max WER4,021
(14
where g is a random vector with a pre-selected distribu- tion, such as a standard multivariate Gaussian distribu- tion (Gaussian Homotopy, GH) or a uniform distribution in unit sphere. Based the observation that μ arg max [() approaches' xt as decreases to 0, the standard homotopy method adopts double-loop mech- anism: the outer loop iteratively decreases a, and for each fixed value of a, the inner loop solves max, Eff + ot)], with the solution found in the current inner loop as the starting search point in the next inner loop.
1. Introduction
In this work, we consider the global optimization problem of
max #ESCRd
f(x)
(1)
where S is compact set and f S + R is a continuous and possibly non-concave function with a unique global maximum point x= = arg max f (xx). The minimize- version of this problem is often encountered machine learning, such model trainings and adversarial attacks in computer vision. The gradient-based algorithms are com- monly used, such as the (stochastic) gradient descent. In general, these methods only guarantee to approximate lo-
The double-logg loop mechanism is costly in time. To tackle this issue, (Iwakiri et al., 2022) proposes single-loop Gaus- sian homotopy (SLGH) method that updates both and a in each iteration. Although SLGH aims at the global optimums, in theory, it only guarantees to approximate a local optimum², which is not necessarily global one. time-efficien algorithm that aims the global maximum still to be found.
Department of Engineering, Shenzhen MSU-BIT Univer- sity, Shenzhen, China. Correspondence to: Chen Xu <xuchen smbu.cdu.en>.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Note that E[f + + f(1) if a = 0. Theorem 4.1 in (Twakiri et al., 2022) shows that SLGH ap- proximates a solution such (V) =

---

Power Transform and Gaussian Smoothing
Therefore, in this work, we propose a new method, namely the Gaussian Smoothing with a Power-Transformed Objec- tive (GS- GoS-PowerOOp), which adopts single-loop mechanism and aims at the global optimum. Specifically, with ø > 0 and a sufficiently large N >> O, it solves the surrogate prob- lem of max, Bx-Nip, (.) (a)], where fNv (x) modi- fies/ I by putting more weight to its global maximum point x². The functional form of (xx) can be either f (x) or (N According our theory (see Subsection 3.1 for preview), GS-PowerOpp converges to a neighborhood of the solution x" to (1) at the iteration complexity of O)) This complexity can be improved to O if the com- monly assumed Lipschitz conditions hold. The majority of experiments in Section 5 show that the GS- GSS-PowerOpt-ban -aaee algorithm (e.g,, EPGS, introduced later) outperforms other algorithms that also apply the smoothing technique.
N, R, and E be selected so that NR --- is positive semi-definite. This indicates that our EPGS (see Section 2), for which I = 0 and Σ ola. is not a special case of theirs, since -o II is negative definite and violates their requirement. Moreover, their theory on the distance between the optimum point of the new surrogate and x' is incomplete (see Section 3.2 in (Dvijotham et al., 2014)). For optimal-control problems. (Roulet et al., 2020) study the surrogate objective that is similar to G(u), and pro- vide a theoretical analysis on the corresponding algorithm's convergence to stationary point. However, the relation be- tween this stationary point and the global optimum point x* is not revealed. The proposed surrogate objective in (Chen et al., 2024) is (1 - N + log (Bg=-i1o.E) [e ((++t))))) where N E [0, 1]. This is very different from our require- ment that N is sufficiently large (see Theorem 2.1). Also, their theory (i.e., Theorem 10 in (Chen et al., 2024)) bounds [f f(((")) with O(Na²) + G(N, a) where G( ((N,os o) is in general nonlinear in N, which does not imply an im- provement for increasing the value of N.
Related Work. The homotopy methods, firstly proposed in (Blake& & Zisserman, 1987), are intensively studied in the field of machine learning for global optimization problems. (Mobahi & Fisher, 2015) derives a bound for the worst scenario of the GH algorithm in deterministic setting (i.e., the expectation E is computed accurately), while (Hazan al., 2016) provides a convergence analysis in a stochastic setting (i.c., E is estimated with samples). (Gao & Sener, 2022) changes the distribution of the perturbation & from the commonly used Gaussian or uniform to the distribution that minimizes the estimation error of the gradient v [ + E)]. (Lin et al., 2023) proposes an algorithm for learning the whole solution path produced by the homotopy. Specifically, their algorithm learns a model (o) that predicts (for any 0) the solution to min,, V Vullg-Wio,.1a (f (1 + e)), where & is the set of model parameters to be trained.
As shown later in Eq. (5), GS- GS-PooerOpt iteratively gener- ates solution candidates and update its internal state (i.e.. 14:) using candidates' evaluations. This pattern is shared by many evolutionary algorithms (EA), such simulated annealing (Van Laarhoven et al., 1987), particle swarm opti- mization (PSO, e.g.. (Miranda, 2018) and Section 3.1.5 in (Locatelli & Schoen, 2013)), the cross-entropy method for optimization (Boer et al., 2005), and the covariance matrix adaptation evolution strategy (CMA-ES, (Hansen & Oster- meier, 2001)). However, GS-PowerOpt is distinct from the EA algorithms in its construction of the surrogate objective Ba~N( La) (a)) and its use of the stochastic gradient method for optimization.
The smoothing technique and the homotopy method have a large number of successful applications in machine learning, such as neural network training (Hazan et al., 2016), adver- sarial attack on image classification models (Iwakiri al., 2022), solving L₁ Le-reuularized least-square problems ((Xiao & Zhang, 2012)), neural combinatorial optimization (Gao & Sener, 2022), improving the optimization algorithms of stochastic gradient descent and Adam (Starnes & Webster, 2024), and so on.
Contribution. This paper introduces a novel zeroth-order method, GS- OS--owerr for solving global optimization problems, with the contributions summarized as follows.
1. To our knowledge, this is the first work that proposes the idea' of putting sufficiently large weight on the global maximum values of the objective, to decrease the distance between the optimum point before and after Gaussian smoothing (i.e.. ||0 =²ll). It provides a theoretical foundation (Theorem 2.1 and Lemma 3.4), as well as motivations, for future studies to find better ways of weight shifting than power transforms.
There are a few existing studies (Dvijotham et al., 2014; Roulet et al., 2020; Chen et al., 2024) that replace the original f with surrogate objective that also involves the exponential transformation (((+E)) before smooth- ing. But their works are different from ours. (Dvijotham et al., 2014) proposes to minimize the surrogate objective of G(H)= := N log (Eg~ N ((+++)))) + 4u²" Ru. The theory' that justifies this surrogate objective requires that
2. In theory, compared to the iteration complexity of Old of the standard zeroth-order (ZO) homo- topy method analyzed in Theorem 5.1 of (Hazan et al., 2016). GS- GS-PowerOpt is much faster at the iteration complexity of O(d?:-2 under the Lipschitz condi-
AAcorrding to Theorem 3.1 in (Dvijotham et al., 2014), min, C(u, Σ) is convex problem given that NR. - -- is posi- tive definite and C is convex.
*(Diioohaa et al., 2014; Roulet et al., 2020; Chen al., 2024), which involve power transforms, have not mentioned this idea.
2

---

Power Transform and Gaussian Smoothing
tions (see Section 3.5) and does require the strong assumption of "a-nice". Compared to the ZO meth- ods in (Ghadimi & Lan, 2013; Chen et al., 2019) and ZO-SLGH, the main advantage of GS-PowerOpt lies in its ability to approximate the global solution. The majority of our experiments show that ranks highest among all these algorithms that apply smoothing (see Section 5.4).
1.0
1.0
0.8
0.8
0.6
0.6
0.4
Run
0.4
=
= 0.1
0.2
N 5
0.2
N = 0.4
3. Our convergence analysis in Corollary 3.9 does not require the Lipschitz condition on the original objec- tive f. which is assumed in the theoretical analysis of homotopy methods in other studies (Hazan et al., 2016; Iwakiri et al., 2022). Therefore, our analysis applies to more situations.
15
0.0
0.0
0
0
μ
H
(a) Gauss. Smooth of fa
(b) Gauss. Smooth e
Figure 1: Graph of approximated FN.o(1). (n). where
4. The theory derived in this work is on the distance be- tween the found solution and the optimal one, while the convergence analysis in other studies on homo- topy (Hazan et al., 2016; Iwakiri et al., 2022) is on the objective value of the found solution. Therefore, our theory has a wider range of applications (e.g.. for problems that concern the distance between the found solution and the true one, such as inverse problems (Arridge et al., 2019) and adversarial attacks in image recognitions).
FN, (N) is defined as (a) En- (z)] (b)
Ez-N(( (e o 0.5, and f(u) = log( (n +
0.5) 10- -log(o 0.5)² + 10-2) + for |n| S and f(n) 0 for [u] 1. All function graphs scaled to have maximum value of 1 for easier comparisons.
that places more weight on the objective I's maximum value (by increasing the gap between f(x*) and f-values at other points) before performing Gaussian smoothing. Based on GS-PowerOpt, we design two algorithms", Power Gaus- sian Smoothing (PGS) and Exponential Power Gaussian Smoothing (EPGS), which are featured with replacing the original objective f(x) with a (exponential) power transfor- mation. Specifically, with a and N as two hyper-parameter PGS solves max, (1 [ [NN(( (X) and EPGS solves max, (p Le (e- [=)], both using a stochastic gradi- ent ascent algorithm derived in this paper. which does not require the differentiability of f.
Road Map. Section 2 describes GS-PowerOpt and the intuition behind it. Its theoretical convergence analy- sis is performed in Section 3 and 4 (see Subsection 3.1 for a preview). Numerical experiments are included in Section 5. Section 6 provides a guidance on select- ing values of the hyper-parameters, and Section 7 con- cludes. The appendix includes a table of notations, proofs to all our theoretical results (lemma, theorem, corol- lary and proposition), details of certain compared algo- rithms, and hyper-paramen All our codes can be found at http: //tp:://tiee chen- reen-reeeeacc/GGe wwweeeerrcc/c--Poeeraaeee www.-oooweerraoooooeoee form.
values used in our experiments. com/
2.2. Theoretical Justification of the Motivation
In Theorem 2.1, we lay the ground for justifying the intuition that motivates PowerOOt:::: Given a > O, for any 8 > O. there exists a threshold such that whenever N exceeds this threshold, the global maximum point arg max, Fx lies within a ó-neighborhood of æ", where Fx == Ex~N(n, ta) [fN (x:) and
2. GS-PowerOpt: The Proposed Method
2.1. Motivation
Intuitively, if we modify f(x) to put sufficiently large weight on its global maximum point x", then 14 == arg max, Ee>Nin. [x)) should get close enough to x² One way of such modification is by taking (exponential) powers of f, if f(=*)= 1. The difference f (x*) (æ) is positively related with the power N. which indicates that more weight is put on xx as N increases. Figure I verifies this intuition with an example. As shown in these two toy examples, fu' approaches x" as N increases.
f (x),
2 S otherwise,
fN(#)
(PGS setting);
0,
(4)
e f(x). 0,
x E otherwise.
fx(
(EPGS setting).
Theorem 2.1. Let f S C. - R. be continuous func- tion that is possibly non-concave (and non-negative only for the case of PGS), where S is compact. Assume that I has a global maximum x such that
=2 f(x) <
From the above intuition, we propose GS- GS-PowerOpt for soly- ing the global optimization problem (1). a new method
'See Algorithm for the two algorithms.
3

---

Power Transform and Gaussian Smoothing
(Exp) power-N N transform
Gaussian Smoothing
Stochastic Gradident Ascent, P
Algorithm PGS/EPGS for Solving (1)
f(x)
fx(x)
(p)
The power N > O, the scaling parameter 0, the objective f. the initial value po. the number K of sampled points for gradient approximation, the total number 'I' of μ-updates, and the learning rate schedule {ax]
Input:
Figure 2: A Flowchart of GS-PowerOpt
f(x*) for any 8 > 0. For any > O and any N > define
for from 0 to T do
(N (V2To)d mERR
[
fN(x)e
110-n12
dx, po IRd 20d
Independently sample from the multivariate Gaussian distribution (u,, a la) and obtain {
Mc+1 = pr + a, FN, (Pt)/ IIV/ F (P+)ll, where V FN. (14) is defined below (5).
where fN is defined in for either PGS or EPGS. Then, for any M > 0 and 5 > O such that B(x"; 6) == fo IRd || - x=1 S 8) C S, there exists N8.,,M > O, such that whenever N > N...,M. for any ||p||| I M and any E f1.2,... ......... d} we have that: DFr(p..) > if pa < x; -6, 8p:
end for
Return {1r from which μ is selected to approxi-
mate (e.g., μ == arg max,r (2.. f (2))..
and (Fy(p=) Ops. < if P1 x. + 5. Here, p4 and xi denote the tth entry of μ and x", respectively.
Remark 2.2. The inequalities in Theorem 2.1 imply that any stationary point μí' (if any) of FN.. (14) within the region
3. Convergence Analysis
3.1. Preview of the Main Theoretical Results
||a||| & M satisfies |n! - x; & 8 for all i E (1,2,....}) Proposition 2.3. Given a > 0 and > 0, FN. (4) in Theorem 2.1 attains global max at some fx* E Rdd
In this section, we prove our main theoretical results, Lemma 3.4 and Corollary 3.9, which indicate that GS- PowerOpt converges to an arbitrarily small neighborhood of x= := arg max f (ax). Specifically, we show that, for any fixed 5 and any fixed >> O, given N larger than some (ō, a ddeepnndett threshold, all the stationary points of FN.. (1) lie in 6-neighborhood of xt (Lemma 3.4), and the stochastic gradient ascent in Eq. (5) converges to one of these stationary points with the iteration complexity of ON (d 2) (Corollary 3.9 and Remark 3.10). This com- plexity is derived from the bound given in Theorem 3.7, whose proof requires Lemma 3.5 and 3.6.
2.3. Solution Updating Rule of GS-PowerOpt
For the optimization problem (I), based on Theorem 2.1, with the pre-selected hyper-parameters N and > 0, GS- PowerOpt follows a stochastic gradient ascent scheme to solve max FN.- (1t). Specifically, the rule for updating the
solution candidate is
GS PSSPoowrOpt:
Mi+1 = uh a, (N,) (5)
where (FN) := EK (2x f)fN(
Furthermore, with additional conditions f, we prove that the complexity is improved to ON (d&e-2) in Subsection 3.5, and that the dependence of the O-factor on N can be removed (Corollary 4.2).
) k==1 independently sampled from the multivari- ate Gaussian distribution N(,, o² Ia), and fx(()) is de- fined in (4). Note that FNN (H:) is a sample estimate of 22 N, (11), since
{ax)
3.2. Notations in Section 3
(1)
(V22T) -a (d+2) {
1m-
In this section, let 8 > 0 and o >> 0 be fixed, and 8 satisfies
(x (e)-H)fx(z)e 2nd
dx
DERU
= - Te -11)
Sx = {u Rd: 114 - 2 s 5,1 (1,2..... d}} C S,
(6)
(7)
where i denotes the eth entry, x= == arg max (xx) and S is f's compact domain as specified in Assumption 3.1. Let > 0 be such that all the stationary points (if any) of FN.. (H) within the region || VdM lie in Sa s, where M is specified in Assumption 3.1. Such an N exists because of Theorem 2.1 (see Remark 2.2), and its value depends on 8, o, and VdM. Unless needed for clarity, we omit the subscripts in FN.0(H) as they remain fixed throughout the rest of Section 3, and write F(H) instead. F()))) refers to the gradient of F with respect to p.
where the interchange of differentiation and integral in the second line can be justified by Lebesgue's s dominated con- vergence theorem. A flowchart of the algorithm is given in Figure 2.
Based on GS-PowerOpt, PGS and EPGS are designed in Algorithm 1. They normalize the gradient before updating the solution, which is a common practice to stabilize results. An effective method to avoid computation overflows caused by a large N- V-value can be found in Appendix B.

---

Power Transform and Gaussian Smoothing
3.3. Assumptions and Lemmas
times of 1e-updating by (5). we have that
(o...r [B[| VF
Here, 7 E (0, 1 1/2) is a parameter in the learning rate a == (1 + 1) 11/224)))) Co = fx(2²) - F(uo) 2f (x)) Σi=1 (1+2)), 1= Co(1 22-00 and C2 max (1,2/Cr).
Assumption 3.1. Assume that f(x): : S + R is a function satisfying the conditions specified in Theorem 2.1, where S < SM := {x E Rd |z,| I M, {1, .... d]}. for some M > 0.
Remark 3.10. The iteration complexity is approximately Ox(d' if is close to 0. Also, the dependence of the big-O factor on N can be removed with an additional assumption. See Corollary 4.2 for this point.
Assumption 3.2. Assume that the learning rate og satisfies
0t > 0,
Σ
t00, and Σ of <
+00.
t=0
1=0
3.5. Improved Iteration Complexity under Lipschitz Conditions
Lemma 3.3. Under Assumption 3.1, (M) and VN (1) are well-defined for all μ E Rd.
In Proposition 3.11, we re-derive the coefficient I. in Lemma 3,5 under the Lipschitz condition on the objective f and its first derivative J.. The new value of L does not depend on the dimension d. With this result, the iteration complexity in Corollary 3.9 becomes ON (2P when y is close 0.
Lemma 3.4. Under Assumption 3.1, any stationary point of FN (p) in R belongs to Sw (defined in (7)).
Lemma 3.5. Under Assumption 3.1, for any a > O, the objective function FN is Lipschitz Smooth. That is, for any ,1, 122 E ERR..
Proposition 3.11. Assume Assumption 3.1, f(x) = 0 on the boundary of f's domain, the Lipschitz condition f: - f(y) S Lollæ - yll. and the Lipschitz condition on Vf:
[VFNoo V VNN S L1lle11 p2l1,
where L = 2do -loo2fs((e (x"" and [N(x*) = f (x*) for PGS and fx(x²) = ((((() for EPGS.
- ()x) two statements are true.
/ S Ta f|a - yll. Then, the following
Lemma 3.6. Under Assumption 3.1, for any a > 0, let & FN (1) be defined in (5). Then, V (n))) (+) < G. where
[V 0) FVN(u, S Tllps u2l holds for any μ1. M2 E Rd, where L (N (x") + N(N 1 (x=))=)))))))))))))))))))))))( under the PGS setting, and under the EPGS
do2 (x'), for PGS; 2N(a)))(
L= (NL N f(x)) + 2
G G
for EPGS.
setting.
2. The iteration complexity in Corollary 3.9 reduces to ON((de ((d=-1))/(1221))
3.4. Iteration Complexity
Theorem 3.7. Let {mm C R.d be produced by following the iteration rule of (5), with pre-selected and determinis- tic Pn and all the involved terms defined as in Section 3.2. Then, under Assumption 3. and 3.2, we have that
Remark 3.12. "f(x) 0 on the boundary of f's domain" is assumed without loss of generality, since we can continu- ously extend f to a larger domain to make it true.
The Lipschitz condition is common in literature. For ex- ample, the convergence analysis for the standard homotopy method requires the Lipschiz assumption on f (see Theorem 5.1 in (Hazan et al., 2016)), and the convergence analysis for ZOSLGH requires the Lipschitz condition on both f and f (see Assumption Al in (lwakiri et al., 2022)).
Σ ago 2 (EIIFF(()))) 1=0
(F(o"))F(H))+L0
ai
1=0
where L and G are as defined in Lemma 3.5 and Lemma 3.6, respectively.
Remark 3.8. The inequality in Theorem 3.7 implies that milk m (o.1....T E[I[V ((+t)l) approaches 0 as T + oo, since the right-hand side is finite and E at = co. Fur- thermore, the iteration complexity of this convergence is
4. Removing the Iteration Complexity's Dependence on N
Lemma 3.4 and Corollary 3.9 imply that GS-PowerOpt con- verges to ô-neighborhood of x" at the iteration complexity of (dt 2). To ensure the convergence to a smaller neighborhood of x=", we need to decrease 5. However, this possibly requires larger N for Lemma 3.4 and Corollary 3.9 to hold (recall N's definition in Subsection 3.2), and in turn increases the iteration complexity of O₂ (dt=-?) The following additional assumption removes the complexity's
given in Corollary 3.9 when a; == (t 1++11-112+))) (11/2+9)
Corollary 3.9. Suppose Assumption 3.1 and 3.2 hold. Let {pt) be produced by the stochastic gradient ascent rule (5) of GS OS-PowerOpt, with a pre-selected and deterministic pso. Then, for any E E (0, 1), after
T> (C, (C
5

---

Power Transform and Gaussian Smoothing
dependence on N, and guarantees an iteration complexity of 2 regardless of how close the positive 5 is to 0. Assumption 4.1. f() E [o,1) 1) for the PGS case, and [(x) < 0 for the EPGS case.
Fitness Ki) EPGS
Fitness Kig) PGS
8-
EPGS-20 case
PGS 20 cass
EPGS case
cast
In practice, this assumption can be realized if we know an upper bound of the objective f(-). For example, if it is known that f(-) < B. then we can proceed EPGS with the new objective function fi := f - B (ʃ' and fi share the same global maximum point x )² Also, least shown by our experiments (Table 1- 4), GS ES-PowerOpt works well for objectives that do not necessarily satisfy this assumption.
0
MSE mi A):
EPGS
MSE m. /1) PGS
0.15
0.35
EPGS-7D
PGS-2D
EPGS 50 ca2e
PGS 5D case
0.10-
6.10-
0.06-
0.0E
Corollary 4.2. Under Assumption 3.1 and 4.1, the iteration complexity in Corollary 3.9 becomes O(d22=11 (21(1-22)))))) and the iteration complexity in Point of Proposition 3. 11 becomes ((d==1))//1 from N.
0.00-
0.00
both of which are independent
Figure 4: Effects of Increasing N. For each N, we perform the algorithm 100 times to stabilize re- sults, and obtain { Eks f/x)) and Σm MSE(m1, / are plot- ΣL Ei (M + 0.5)²/d,
Remark 4.3. Note that the two complexities approach -2 and O2d2g=2), respectively, 7 - 0.
1100
k=1 The average fitness
ted, where MSE(m p4x) ==
5. Experiments
1.0, and f is defined in (8). Note that x" m. has all its entries equal to -0.5.
5.1. Effects of Increasing Powers
We illustrate the improvements made by increasing N for PGS/EPGS through an example problem of max fxx) where
The performances of other popular global algorithms (maximize-version) are reported for comparison, including (1) a standard homotopy method STD STD-Hoootopy; (2) two zeroth-order single-loop Gaussian homotopy algorithms, ZOSLGHd and ZOSLGHr (see the determinsitic version of Algorithm 3 in (Iwakiri et al., 2022)); (3) the gradient-ascent version of the zeroth-order algorithm of ZOSGD (see Equa- tion (1) in (Chen et al., 2019) and Section 2. in (Ghadimi & Lan, 2013)) and ZOAdaMM (Algorithm in (Chen et al., 2019))?, which were also used for comparisons in (Iwakiri et al., 2022); (4) as well as CMA-ES (Hansen Oster- meier, 2001; Hansen et al., 2019), one of the ttate-of-the-art evolutionary algorithms.
(xx) -olo [| m1|
log([1== (ooo([[===mm))))) m2l | 2+10-2)
(8) the global maximum point m E I2 has all its entries equal to -0.5, and the local maximum point m2 E TRd has all its
entries equal to 0.5. The graph of its 2D-version is plotted in Figure 3 (a).
With each value of N. we perform both the PGS and EPGS in Algorithm 1 to solve this problem. The experiments are done in two settings, one is two-dimensional (d = 2) and the other is five-dimensional (d = 5). More details can be found in Appendix E.
More details and discussions on the compared algorithms can be found in Appendix D. The selected hyper-parameter values of all algorithms can be found in Appendix F.
The results, plotted in Figure 4, show that, as N increases, the distance between the produced solution μ² and the global maximum point x" approaches zero (see the decreas- ing MSE curve in the plot), which is consistent with Theo- rem 2.1 and the idea that F(u)''s maximum fz" approaches the global maximum point x" of f as we put more weight on f(x=")
Ackley. The Ackley objective function is character- ized by numerous local optima and a single global op- timum. We solve the max-version of the correspond- ing problem, which is max(a,)) f(z, v) and f y) 20e 2.e-0.2.00.000
(coos((2))++ooss((2)))) ,The graph of this function is plotted in Figure 3(b). From both the func-
5.2. Performance on Benchmark Objective Functions
'A deterministic version SLGH for solving the optimiza- tion problem of max, fax,, with f being a deterministic function. ZOSGG and ZOAdaMM were originally designed to solve (3). We take their solutions to (3) as solutions (1), and treat the scaling parameter in (3) as a hyper-parameter.
In this subsection, we test the performance of PGS and EPGS on solving (1), with the objective f being either of the two popular benchmark objective functions, the Ackley and the Rosenbrock (maximize-version).
6

---

Power Transform and Gaussian Smoothing
1.25
100
(a) Two-log Objective
(b) Ackley Func. (Max-Version)
(c) Rosenbrock Fune. (Max- Version).
Figure 3: Graph of the Benchmark Objective Functions.
Table Performances on Maximizing Ackley. "Iter. Taken" refers the number of iterations taken reach the best found solution. All numbers are rounded to keep most 3 decimal places.
Table Performances on Maximizing Rosenbrock. The differences between this experiment and that in Table are: The number T of iterations is set 1000, and the initial solution candidate is taken 140 [-3.0, 2.0]. For PGS, the Rosenbrock is added by 20, 000 to ensure the search agent only encounter positive values. The global maximum point of the Rosenbrock function is (1,1).
Algorithm
Iter. Taken
Best
Solution f(H")
Found (H*")
CMA-ES
116
(0.0, 0.0)
22.718
EPGS (N 1)
143
(0.001, 0.0)
22.683
Algorithm
Iter.
Best
Solution f(w²)
PGS (NV 20)
141
(0.001, 0.002)
22.678
Taken
Found (μ*)
ZOSLGHr
131
-0.002)0.000)
22.621
CMA-ES
72
(1.0, 1.0).
0.0
ZOAdaMM
158
00.005,0.0011
22.613
EPGS (N 3)
487.
(0.999, 1.000)
-0.017
7OSLGHd
123
(-0.003, -0.001)
22.61
STD-Homotopp
624
(0.903, 0.885)
-2.401
ZOSGD
174
(0.005, 0.007)
22.596
PGS (N = 1)
513
(0.773, 1.025)
-22.84
Him-Hoooyypy
194
(0.962, 0.946)
17.58
ZOAdaMM
852
(0.004, 0.618).
-39.206
ZOSLGHr
148
(0.105, 0.938).
-88.477
ZOSGD
45
(0.272, 1.173).
-121.14
tional form and the graph, is not difficult to see that f(r, y)
ZOSLGHd
471
(-0.447,1.991)
-137.016
attains its maximum at xx' (0, 0).
The solutions and their f-values found by each of the com- pared algorithms are reported in Table For each algo- rithm, the total number of iterations is set as 200, and K 100 samples are used for each solution update. The hyper-parameters selected by trials. For each set of dyper-parameter candidates, we perform 100 experiments and take the average to stabilize the results (so all the re- ported numbers are averages). The initial solution value for each experiment is drawn from a multivariate Gaussian with mean 140 = [5.0, 5.0] and covariance 0.01/2.
The performance of each algorithm is recorded in Table 2, which shows that the performances of CMA-ES and EPGS are close, and are significantly better than those of other algorithms.
5.3. Performance on the Black-box Targeted Adversarial Attack
Let C be a black-box" image classifier. The targeted adver- sarial attack on refers to the task modifying the pixels of given image a so that C(a + x:) is equal to a pre-specified target label T. We perform attacks in the most difficult case the target label T is pre-selected be the one with the smallest predicted probability. Another goal of this task is to minimize the perturbation size ||æ:|| Hence, we set the
The results in the table show that all the algorithms perform well and are close each other, except STD-Hoomt
Rosenbrock. The Rosenbrock objective is known to be difficult to optimize, since its global optimum point x" (1.0, 1.0) is surrounded by a flat curved plane (see Figure 3(c)). The problem to solved is max f(x y), where fxx,y) 100(y - 22 (1 x)²
A black-hox classifier refers to classification model whose parameters are not accessible.

---

Power Transform and Gaussian Smoothing
loss
Table 3: Targeted Adversarial Attack on 100 MNIST im- ages (per-image). For each image attack, we set the initial perturbation 140 = O, and Trotal = 1, 500. The success rate (SR) is the portion of successful attacks out of the 100 attacks. R2 || I|. and T are the averages defined below in the main text. The numbers in the parentheses are sam- ple standard deviations. STD-Htp is STD-Homotopy for short. For EPGS, N is selected to be 0.05. See Table 10 in the Appendix for the produced adversarial images for four randomly selected images.
L(x) := max(max C(a + x) - +x), x) + \|| i7T
where C(a + æ), denotes the predicted logit (i.e., log probability) for the tth class, R is hyper-parameter that controls the certainty level of the attack, À is a regular- ization coefficient (we set À = in our experiments), T ;= arg min, C(a);, and || denotes the L2 norm of (i.e., the square root of the sum of squares of entries in at). This loss function resembles the popular one designed in (Carlini& & Wagner, 2017).
Algorithm
SR
R
|A01
T
With EPGS and other compared algorithms, we perform ad- versarial attacks on 100 randomly selected images from each of two image datasets, the set of MNIST handwritten digits (LeCun et al., 1998) and the CIFAR-10 10 set (Krizhevsky & Hinton, 2009). Specifically, the goal is to solve:
CMA-ES
100%
(9%(4%)
(.61()
(489
EPGS
100%
87%(5%)
3.01(..60)
397())
ZOSGD
100%
85%(5%)
3.14(0.61)
1427(242)
ZOSLGHd
100%
74%()9%)
4.21(0.71)
1490(24)
ZOSLGHr
100%
(1%())%))
4.86(0.81)
476(658)
ZOAdaMM
100%
29%()7%)
6.88(1.15)
45(15)
max (x) == -L(x))
STD-Htp
97%
- -4%(37%)
8.25(1.09)
530()64)
BER
where d is the total number of pixels in each image. For Figure-MNIST images, d= = 28 x 28, and for CIFAR-10 images, d = 32 x 32 x 3. We call ff as the fitness function.
if the predicted log probability of the target label is at least a. = 0.001 greater than that of other classes (i.e.. C(a + 1 max C(a + st); >> k). We say that an attack is successful if the produced {,mm Tigttaa contain at least one successful perturbation. If the attack is suc- cessful, let pm denote the successful perturbation with the largest 1ta-value among {um, ) Fegus and let T'm denote the number of iterations taken by the algorithm to produce
The classifier is robust convolutional neural network (CNN) trained using the technique of defensive distillation". The distillation temperature is set at 100, which leads high level of robustness (Carlini & Wagner, 2017). In the MNIST attacks, our trained classifier C has a classification accuracy of 97.4% on the testing images. In the CIFAR-10 attacks, the trained C has a test accuracy of 86.2%.
Min We use R2 a + 14) == 1 Dd 12
to measure
The hyper-parameters of all the tested algorithms are se- lected by trials and can be found in Appendix F. For ZO-SLGHd, ZO-SLGHr, and ZO-AdaMM, the hyper- parameters reported in Appendix E. of (Iwakiri et al., 2022) are included in our candidate set, since they performed sim- ilar tasks.
the similarity between a and the perturbed image a + p. where a; and i4 denote the 3th pixel (entry) of a and μ., respectively, and ā denotes the mean of {a.).
With the above notations, we construct four measures on the performances of an algorithm. One is the success rate, which refers to the ratio of successful image attacks out of the total number of attacks (100). The second measure is the average R², which equals R² := Emes R² (amm am + p |/S]. where S denotes the set of indices of the successful attacks and p denotes the optimal perturbation for the m figure. The third one is the average || of (llpe ll Ilmes where || denotes the -oom. The last measure is the average T of (Tm) mes.
We choose EPGS over PGS for this task since the fitness function f()) can be negative, which makes EPGS more convenient to apply. But note that we can modify fxx by adding large positive constant to facilitate PGS.
Experiments on MNIST. For each image am that is ran- domly drawn from the dataset, where m E {1, 2.., 100), and each algorithm, we perform an attack (i.c., exper- iment) of Trotal iterations. Let {Mmm)) Trotal- denote all the perturbations (solutions) produced in these Trotal iterations. We say that perturbation ja is successful
The results are reported in Table 3, from which we see that EPGS has a high -s-oe of 87% (ranks among the top 2). indicating that the perturbed image is closest to the original one (N² = 100% implies that a and + l are identical). Also, the average number of iterations taken by EPGS to reach the optimal perturbation is 397, which is among the two fastest algorithms.
"We borrow the code by (Carlini & Wagner, 2017) for training the classifier from ht ats / //gitttutt thub. cwm/ car in /n__ aaaassktttkkk,, which applies TensorFlow (Abadi et al., 2015) for model training. We changed the layer structure in the neural network either increase accuracy decrease computa- tion complexity while maintaining the accuracy.
Experiments on CIFAR-10. With 100 randomly drawn
8

---

Power Transform and Gaussian Smoothing
Table 4: Targeted Adversarial Attack on 100 CIFAR-10
tion for GS-PowerOpt to work. To illustrate this point, we perform additional experiment with EPGS
images (per-image) For each image attack, we set 14o = 0 and Trotal = 1, 500. For EPGS, N is selected as 0.03. See Table 11 in the Appendix for the produced adversarial images for four randomly selected images.
objec- tive with two global maxima: f(x)) = - log(I] m mi 1| + 10-5) log( x - m2yl + +00 10-9), where m, = [- and m2 = [5). A hundred trials are performed, where N = and each Mo is randomly sampled around the ori- gin. The mean square error between the found solution and one of the two global maximum point is close to O, with its average (over the 100 trials) equal to 1.4 x 10-5 and its sample standard deviation equal to 1.6 x 10-s, This example indicates that GS-P PowerOpt is capable of locating at least one of the multiple global optima. We leave the corresponding theoretical analysis in our future works.
Algorithm
SR
Ra
|
T
ZOSLGHd
98%
(1%)
1.72().32)
(410(411)
ZOSLGHr
98%
98%((%%
2.66(0.68)
456(345)
EPGS
98%
98%)
3.05(0.57)
748(248)
CMA-ES
99%
75%(25%%
10.06(2.35)
(399)
ZOAdaMM
100%
58%()39%
13.13(2.71)
58(31)
ZOSGD
62%
99%((1%
1.19(..19)
(64(349)
STD-Htp
52%
87%((1%)
7.54().57)
566(396)
6. Guidance on Choosing Hyper-parameters
Although larger N guarantees convergence of GS- PowerOpt to a smaller neighborhood of x" in theory (see Subsection 3.1), it also leads to a higher variance of of the update term FN (1z) in Eq. (5), which in turn decreases the efficiency of the algorithm in practice. Therefore, we recommend to start from a moderate N and incrementally in- crease its value during tuning. Although the proper starting value of N may vary for different problems, based our experience, 5 for PGS and 0.1 for EPGS are good choices.
images from the CIFAR-10 10 test set, we repeat the per-image targeted adversarial attacks. Their results are reported in Table 4. These results are in general better than those in the MNIST attacks, which we believe is because of the lower accuracy of the trained CIFAR-I0 CNN (86.0% vs 97.8%).
The results show that EPGS produces a success rate of 98% and scores in the top three with respect to R Specifically, the R--value of 98% indicates that the perturbed image produced by EPGS is very close to the original image, which is consistent with our goal that the perturbation size || || should be small.
While large a increases the exploration range for each I update, it also increases the sample complexity of the algorithm. Our experiments show that a o-value of 10% of the search radius for x is good starting value for tuning.
5.4. Summary on Experiment Results
7. Conclusion and Future Work
Comparing to algorithms that use the smoothing technique (which excludes CMA-ES), PGS and EPGS ranked among the tops in all the tasks we performed. Specifically, in the tasks of Ackley, Rosenbrock, and MNIST-attack (Table 2 and 3), EPGS has the highest fitness value f(=") than other algorithms except CMA-ES. For CIFAR- 10 attacks (Table 4), EPGS's 1t score equals that of the best (ZOSLGHd). In sum, EPGS outperforms other algorithms that also ap- ply smoothing techniques in the majority of the performed experiments.
The convergence analysis and numerical results show that the easily implemented optimization method of GS- PowerOpt stands out among its peers that also apply smooth- ing techniques. Our work provides a foundation for future studies to explore more efficient ways to increase the gap between f(x") and f values other points before smooth- ing.
Acknowledgements
While EPGS underperforms CMA-ES in experiments of Ackley, Rosenbrock, and MNIST, beats CMA-ES in the CIFAR-10 task with comparable success rate and signifi- cantly smaller perturbation norm (see Table 4). Moreover, to the best of our knowledge, the theoretical convergence guar- antee for CMA-ES on general non-convex objectives is less developed, providing a competitive edge to PowerOpt.
We thank the anonymous reviewers for their valuable com- ments and suggestions for improving this paper.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
5.5. The Case of Multiple Global Maxima
Although the convergence theory (e.g.. Theorem 2.1) re- quires the condition that the objective f has a unique global maximum, a sufficient rather than a necessary condi-
9

---

Power Transform and Gaussian Smoothing
References
Ghadimi, S. and Lan, G. Stochastic first-and zeroth-order
methods for nonconvex stochastic programming. SIAM journal on optimization, 23(44)2341-2368, 2013.
Abadi, M., Agarwal, A., Barham, P., Brevdo, E., Chen, Z., Citro, C., Corrado, G. S., Davis, A., Dean, J., Devin, M.. Ghemawat, S., Goodfellow, I. H., A., Irving, G., Isard, M., Jia, Y. Jozefowicz, R., Kaiser, L., Kudlur, M., Levenberg, J., Mane, D., Monga, R., Moore, S., Murray, D., Olah, C., Schuster, M., Shlens, J., Steiner, B., Sutskever, I. Talwar, K., Tucker, P. Vanhoucke, V., Vasudevan, V., Viegas, F., Vinyals, O., Warden, P. Wattenberg, M., Wicke, M., Yu, Y., and Zheng, X. Tensorflow: Large-scale machine learning on het- erogeneous distributed systems, 2015. URL https: //www. www.ww.wssrffow..co org/
Hansen, N. and Ostermeier, A. Completely derandomized self-adaptation in evolution strategies. Evolutionary com- putation, 922::159-193 -95, 2001.
Hansen, N., Akimoto, Y., and Baudis, P. CMA-ES/pyymaon Github, 2019, zenodo 200.63559333
Hazan, E., Levy, K. Y., and Shalev-Shwartz, S. On grad- uated optimization for stochastic non-convex problems. In Proceedings of The 33rd International Conference on Machine Learning, volume 48, pp.
Arridge, S., Maass, P., Öktem, O., and Schönlieb, C.-B. Solving inverse problems using data-driven models. Acta Numerica, 28:1-1744 2019. 2019.
2016.
Iwakiri, H., Wang. Y., Ito, S., and Takeda, A. Single loop gaussian homotopy method for non-convex optimization. Advances in Neural Information Processing Systems, volume 35, pp. 7065-7076, 2022.
Blake, A. and Zisserman, A. Visual Reconstruction. MIT press, 1987.
Boer, P. D., Kroese, D. P., Mannor, S., and Rubinstein, R. Y. tutorial on the cross-entropy method. Ann. Oper. Res., 134(1):19-67, 2005. doi: 10. 00.10077/114499-005555744
Krizhevsky, A. and Hinton, G. Learning multiple layers of features from tiny images. Technical Report TR-2009, University of Toronto, 2009.
Carlini, N. and Wagner, D. Towards evaluating the bustness of neural networks. In 2017 IEEE Symposium on Security and Privacy (SP), pp. 39-57, 2017. doi: 10.1109/SP.2017.49
LeCun, Y., Bottou, L.,, Bengio, Y., and Haffner, Gradient- based learning applied document recognition. Proceed- ings of the IEEE, 86(1 1):2278-2324, 1998.
Chen, J., Guo, Z., Li, H., and Chen, C. P. Regularizing scale- adaptive central moment sharpness for neural networks. IEEE Transactions Neural Networks and Learning Systems, 35(5), 2024.
Lei, Y., Hu, T., Li, G., and Tang, K. Stochastic gradient descent for nonconvex learning without bounded gradient assumptions. IEEE transactions on neural networks and learning systems, 31(10):4394 4400, 2019.
Chen, X., Liu, S., Xu, K., Li, X., Lin, X., Hong, M., and Cox, D. Zo-adamm: Zeroth-order adaptive momentum method for black-box optimization. Advances in neural information processing systems, 32, 2019.
Lin, X., Yang. Z., Zhang, X., and Zhang, Q. Continuation path learning for homotopy optimization. In Proceed- ings of the 40th International Conference Machine Learning, volume 202, pp. 21288-21311, PMLR, 2023,
Choromanska, A., Henaff, M., Mathieu, M., Arous, G. B., and LeCun, Y. The loss surfaces of multilayer networks. In Proceedings of the Eighteenth International Confer- ence on Artificial Intelligence and Statistics, volume 38 of Proceedings of Machine Learning Research, pp. 192-204.
Locatelli, M. and Schoen, F. Global Optimization: Theory, Algorithms. and Applications. SIAM, Philadelphia, PA, 2013. doi:
Magnus, J. R. and Neudecker, H. Matrix Differential Cal- culus with Applications in Statistics and Econometrics. John Wiley & Sons Ltd, 2019.
PMLR. 2015.
Dvijotham, K., Fazel, M., and Todorov, Universal con- vexification via risk-aversion. Proceedings the Thir- fieth Conference on Uncertainty in Artificial Intelligence, 2014.
Mertikopoulos, P., Hallak, N., Kavis, A., and Cevher, V. On the almost sure convergence of stochastic gradient descent in non-convex problems. Advances in Neural Information Processing Systems, 33:1117-1128, 2020.
Gao, K. and Sener, O. Generalizing Gaussian smoothing for random search. In Proceedings of the 39th International Conference on Machine Learning, volume 162, pp. 7077- 7101. PMLR, 2022.
Miranda, L. J. V. PySwarms, a research-toolki for particle swarm optimization in python. Journal of Open Source Software, 3, 2018, doi: 10.21 105/joss.00433.
10

---

Power Transform and Gaussian Smoothing
Mobahi, H. and Fisher, J. W. A theoretical analysis of opti-
mization by gaussian continuation. In Proceedings of the
AAAI Conference on Artificial Intelligence, volume 29, pp. 1205-1211, 2015. doi: 10.1609/aaai. http:/aaaiiii9........ 22911.9356.
Nesterov, Y. and Spokoiny, V. Random gradient-free mini- mization of convex functions. Foundations of Computa- tional Mathematics, 17(2):577-566, 2017.
Roulet, V., Fazel, M., Srinivasa, S., and Harchaoui, 7.
On the convergence of the iterative linear exponential quadratic gaussian algorithm to stationary points. In 2020 American Control Conference (ACC), pp. 132-137. IEEE, 2020.
Starnes, A. and Webster, C. Improved performance of stochastic gradients with gaussian smoothing, 2024. URL https: //t.vvaaavvvvv//aa///a//.a.a.aaa org/ abs/ 22111 00531.
Van Laarhoven, J., Aarts, E. H., van Laarhoven, P. J., and Aarts, H. Simulated annealing. Springer, 1987.
Xiao, L. and Zhang, T. A -gradiet homotopy method for the 11-regularized least-squares problem. In Proceedings of the 29th International Conference on Ma- chine Learning (ICML-12), pp. 839-848 886,,4,,222 2012.
Xu, Y., Yan, Y., Lin, Q., and Yang, T. Homotopy smoothing for non-smooth problems with lower complexity than o(1/e). In Advances in Neural Information Processing Systems, volume 29, 2016.

---

Power Transform and Gaussian Smoothing
A. Table of Notations
Notation
Description
Reference
S
compact set in R
Theorem 2.1
f
The real-valued objective function, which is further assumed be non-negative for PGS.
Eq. (1) or Theorem
2.1
æ
The global maximum point of f.
The 7th entry of x², where The 1t entry of μa E IRd, where i E 2
21.,...,
(7)
Hi
(7)
N(p.ola
A multivariate standard Gaussian distribution, where μ R
Eq. (2)
> O, and la denotes the x d identity matrix.
(u)
(x))
N
N > and N E R. In Section 3, it is assumed to be greater than a threshold (see Section 3.2 for details).
[x(x)
The (exponential) power of f. extended to Rd.
Eq. (4)
(1)
Fr = (a)=
Theorem 2.1
F(R)
The abbreviation FN where N and are fixed.
Section 3.2.
F(()).
The gradient of F (p)) with respect to μa.
Eq. (6).
(FN(U,
(1)
A sample estimate of a² D2VFNN. (11).
Eq. (5)
S
A d-neighborhood of x= in Rd, where ō > O.
Eq. (7)
L
The Lipschitz coefficient of V (
Lemma 3.5.
G
The upper bound of E F())
Lemma 3.6.
||^|||
||>||| = Ei=
2 where x
[x1 22 xz] E Rd.
B. PGS/EGPS with A Baseline to Avoid Computation Overflows
An effective method to avoid computation overflows caused by large N-value in Algorithm is modify the gradient estimate as V F(4)) = K E (2 -1:)5 (æx), where (()) (æx) = if a. & S, and
(f( for PGS: -( for EPGS,
1 (xx) =
dg E S. This modification produces the same p-updates as in Algorithm 1 because of the gradient-normalization step. call this algorithm as PGS (EPGS) with a baseline.
C. Proofs to Theoretical Results
C.1. Proof to Theorem 2.1 for EPGS
Theorem 2.1 Let S C d R be continuous function that is possibly ron-concave (and non-negative only for the case of PGS). where S is compact. Assume that f has global maximun x" such that suPm:[[=-=* [[28 f(x) < f(x)) (x"))) for
any > 0. For a > and any N > 0, define
(N) = (V2TO))-
JEERS (N(
le le-212 20 dx.
l E Rd
where fN defined in (4) for either PGS or EPGS. Then, for any M > and 5 > such that B(x= :8) = for E Rd | -w=x0"| < 0} C S. there exists No.,,M M O, such that whenever N Na..,M any || M and any i (1, ..., d}
we have that: (Fx(p.)) > if μ1 < x - ô, and (Fx(p 3p.
< Of > x + 8. Here, ps and x; denote the ith entry of
Op.
and x", respectively.
Here, we provides the proof for the EPGS setting, and the proof for the PGS setting is similar.
12

---

Power Transform and Gaussian Smoothing
Recall that for EPGS, (xx)) = { (())) E S:
For any given 5 - 128 ((x and D& == (Va + 1(22 Using this symbol, we re-write FN, (1) as
Proof.
0. define V
0,
otherwise.
(N,o(H) = DaN (N) = DDN (HN,o(u) + Rx,o(H)),
(9)
where
10-u12
(x:o(())=(V2TTT))
e e-NDs fN
2nd dx,
WERd
Ls c -Na (N
(N) :=(2TT) ((=
20 dx,
(N) = (=V2TT))
NDr (NDefx(z)e
1x-ull
20
dæ,
(x)((=)
where ; 5) ; fax E R | ---1 < 6}. The main idea of the proof is to first show that
x01
[Hv.=(H)
dominates
Ops
BRN (pe) Ops;
if N is sufficiently large, and then that the sign of ( satisfies the declared property in the theorem.
8p4
We derive upper bound for
BR (m)) 8t::
For any f Rd.
a (
le-ull? NNDs
|0g - -4sle"
20 6
fN( (x))da
0p4
(v 2m 2
2 =(="());))
|m=ull?
|0g -Msle"
20
(V27)2o042
20 Be0
11g Ms/e
Is=Hl| 20
6
N(V-
Da) Da)
(V2
N(V--Ds) DD))
1m-u12 2nd dx
|1S uole
ZERd
1
(og (
D(V--Ds)
11
20 dx
V2TO
JRERR
1
|r.- -
20 dx
(10)
3
ZEER
N(V--Da) D.)
1
120lyle-v0 =dd((2ou),
y: 2z - 4b
3
3
v 22
yER
V2
N(V- D2)
ye
dy.
VTO
V2
N(V- Da)
v²
dyy
VITO
V2
NVV- D.)
dd
VTO
N2 (Vo--Do)
ViOo
where the third inequality sign is because ||20 - x01 120 f(x) < Vs. and the fifth inequality sign is from the separability of a multivariate integral.
Since f is continuous, for ca == f(x²) D3 0 (because V/8 < f(x") )) there exists 8' (0, such that whenever | x01 || 8',
f(x) 2 f(x") -68 -6= D3 Vg.
(11)
13

---

Power Transform and Gaussian Smoothing
Using this result, we derive a lower bound for
when pall - M and 1 x²} > 6.
Opc
@HN
[ti -ale NDs (x)ee
1m-He 20"
dx
8p:
|rg -M:le
1z-ull 20
N(f(2)) Do) dar, since ((x";6) C S
(V27))0042
=EB((=0;8)
|2q Mile
412
20
c N(F())
dx
2
2 x 181)
(12)
|m-a|
(6 8
dæ
(2T))
xEB(x 18))
1ill dx,
(6 8'
a n|12 S 2(1x=|12 -11113),
(V2 JxEB(=+;8)) (8)
(6 8e 21 V(8'
where the fourth line is implied by
(N(())))DD)) -Ds) because of (11);
1 141 (c:; xx)) (2) /4)l 2 |
pul
x4 x 8 0 8'.
In the last line of (12),
|all dæ.
V(8,, d(),, = (V2m)oodt2 (
The positive number No.,, is constructed by solving the following inequality for N, which involves the two bounds in (10)
and (12).
N(V Pa)
M22 d')e V(
< <6
Vio
The solution of this inequality is
In
V v2
(8
22 8')e क ('',,d,0))
N
V Dí
where V. Ds 0 and the numerator is negative for sufficiently large M > 0. Therefore, whenever ||l|| S M,
|p4- 271 6, and
In
Ta (8 V2
8')e V(8 (d,ddo))
N > No. = max
0,
V8- Ds
we have
2R (1)
(VV-N(
N² (8 8')e 2 V(8 vV,dd 5
0 0H
(13)
VTO
When N > No. ||aa|| S MM and Mi > x7
+
(G..o(p)
(H..o(p)
@RN.o(u)
0p:
Op:
le-y!? -()
Dz) @RN(U,
(24 -i)e
(ot42 BE :6)
0p,
(HN.o
+ (RN.o(H)
(14)
Ops
Opu
@R (1))
by (13)
+
Op:
Op.
0,
14

---

Power Transform and Gaussian Smoothing
where the third line is because the integrand of the first term is always negative in the integration region.
On the other hand, when N > M. |all - M, and ia < xz -
(
(H)
aRN. (
+
aps
Ope
OHHNN (1)
ORN (1)
Spi
(15)
oR
- [iRN. (1L)
> (13)
(13)
Ops
0.
Then, (14) and (15) imply the result the theorem since
8GN.o(M) Op;
and
OFN.-(() (e) Op:
share the same sign (see Eq. (9)).
C.2. Proof to Proposition 2.3
Proposition 2.3 Given a > 0 and N > 0, (1) in Theorem 2.1 has global max point p
Proof. Since a > 0 and N > 0 are fixed, we denote (M) by F(u) for convenience. Recall that F(u) 2 0 because of the definition of fN in (4). Our proof applies the following two results, whose proofs will be given later.
1. F(u) is Lipschitz, which indicates the continuity.
2. pll-+o (()) = O.
From I"s definition, it is trivial to see that there exists some μí' E Rd such that F(u)) > 0. Define é' := F(u'). From point 2, there exists M > such that, whenever | > M, F(u) < <é
Now, consider the closed ball (0; M') == {u E Rd /1 S M'), where M' > M and μ E B(O; M'). From the extreme value theorem, the continuity of F and the compactness of (0;; M') indicate that attains maximum μ² on B(0; M'). That is, f Rd, and F(x")= 2 F(z) for any μ ((0; M"). Therefore,
F(u") 2 F(u') = > F(u), for any μ & ((0
This indicates that fe is the global maximum point of F in Rdd
Finally, it remains to prove Point and 2.
Proof to Point 1. From Lemma 3.3, the gradient V exists. Hence, from the mean value theorem (e.g., Theorem 5.10 in (Magnus& & Neudecker, 2019)), for any fl, f2 E Rd,, there exists that lies the line segment connecting μn and μ2 that
[F(m)) - ((2)) (F( - 42)
||VF(e) | p2ll. Cauchy Schwarz Inequality
o = Be-N (=)(()) - #ell, proof same as (6).
V2d oVT [N( -22l1
where the last inequality is derived using the last inequality derived in the proof for Lemma 3.3. This proves Point Proof to Point 2. Since S dRd is compact, it is bounded. Assume that S B(0; M) for some M > 0. Then, fx(Ø) 0 if |||||| > M. Hence,
[m--a]2 fN(()) 20
F(u)=
dx
(V2TT)d |slli [N(
(1ll Mi2 dx, whenever |||||| > M,
(V2r))d -
0, as | 00,
15

---

Power Transform and Gaussian Smoothing
where the second line is because || [a] if ||||| M.
14
|0]|
pa
M, which further implies - -1|0: rall S -(1 M)²
C.3. Proof to Lemma 3.3
Lemma 3.3 Under Assumption 3.1, PN, (1)) and (1)) are well-defined for all μ Rd.
Proof. By the definition of F (11) in Theorem 2.1, PN. [[)x(())] and V VN (1)) = El(ar (w)] where the expectation is taken with respect to ~ (N,, Lg). To prove that FN (H)) and VFv (H) are well-defined, it sufficies to prove that (x)) < +00 and (2; [x))f((z)) < +oc, for each i E {1, ..., d}. The former inequality holds since Ifv (x)) is bounded by Assumption 3.1 (the condition that f is continuous on its compact domain implies the boundedness of I (z))). The latter inequality holds because
Bi - Pa)
S fN(E" )LB x4
Mil
(x("
[= dx.
[2q Mile
2
00
(N(
2² 1y e
20 dy,
y: = F2 - Pi:
ViTO
-00
(x²)
2ye 20 dy,
2/TT
(x
2 6 dyf
(N(#")
e 10 dl, 1: y²
2ITO
(x()
(-20² in dt
2
2f (x=)o/ VT < t00.
This finishes the proof for Lemma 3.3.
C.4. Proof to Lemma 3.4
Lemma 3.4 Under Assumption 1. any stationary point of F(p)) in Rd belongs to Su which is defined in (7).
Remark C.1. Proposition 2.3 shows that F(u) has least one stationary point.
Proof. For any point μ Sm.,a 6, we show that FF()) + O. On one hand, μ E SM- Sex 5s then ||ا||| S VdM and FF)) because of the definition of N in Section 3.2.
On the other hand, if μ & SM, there is at least one j such that |py1 M. Then,
I- (N(x))
(F(μ)
SmeRe (z, M1je
2-
0pg
(v2
dddt2
(ne 11)e In-y1²
(x)
by (4),
(
negative,
if Uj > M;
positive, if Hg -M,
where the last equality is because x, E > | S M by Assumption 3.1. In sum, for any point μ $ Sa VF #0, which further implies that any stationary point of F(u) belongs S 88
16

---

Power Transform and Gaussian Smoothing
C.5. Proof to Lemma 3.5
Lemma 3.5 Under Assumption 3.1, for any a > the objective function FN.o is Lipschitz. Smooth. That is, for any M1, R
IVFN, (p1) - ( S Lil H2ll,
where L 2do - aado=ffx(et' "xx(""), and fN(=*) = f (a*) for the case of PGS and fx(x²) = (N((")) for the case of EPGS.
For Proof. The idea to bound each entry of the difference, a vector in Rd on the left-hand side (LHS). For each E {1,2, d), define ge(Hz) as the hth entry of ( E Rd. Then, for the 7 entry of the difference on LHS,
(p:) (p2) = (2 (1)l, by Mean Value Theorem (e.g., Theorem 5.10 in (Magnus & Neudecker, 2019)),
- (a(())lll Mill. by Cauchy Schwarz Inequality,
< 2o f fxx -ills proof given later,
where v is some point the line segment connecting fai and μ2, and Vgi(v) (1) denotes the inner product of the two vectors in R. This further implies
(V - ( S 2do 2 "N - mill
which is the desired result.
Now, it remains to prove for each i {1, (1. and each μ E Rd that [a))) s 2vdo-2fx(z"). It sufficies to derive a bound for each entry of (gi(u) R2, Specifically, for its jth entry:
1s Hll
0g. (u) 0μ1
a SaeRu(0; M:)fN(z)e
20 dx
by (6)
(V2m))do+2
Opt
dig SmERd (N(()) lmm dæ + --
InERo (I; mi) Mi)SN(()e 1m-z! dæ (V27)do042
". x22(x((") ( SpERS lx; Mi Milloz Myle 11l- dæ (V2T))
SN(x)) 2 0 by (4),
l1 110-212
So )ogl((()))) x~2(x((²) SaSR ((;; - 11:32 + (xz M1) 1,)
20
dx
2(v 2(
(,)-
o 2N )2 J2, (T, m2i)²e
20
dx,
o - + o " + (x(=")o-Varla (oi 1xfx(x*) < 20 fx
2/2TTO
where the interchange of differentiation and integral in the second line is by Lebesgue's 's dominated convergence theorem, and the fifth line is because of the separability of the multivariate integral. Here, d.j = if = j. and 6.₃ 0 if + j. The above bound for (g) implies [g.(H)) $ 2 ff(xx)) This finishes the proof for Lemma 3.5.
0pg
C.6. Proof Lemma 3.6
Lemma 3.6 Under Assumption 3.1, for any a > 0, let V FN. be defined (5), Then, [[][VEN.o())))) < G, where
G { d | (x*); for PGS;
do222N
for EPGS.
17

---

Power Transform and Gaussian Smoothing
Proof.
E
[ (o) (e)
K²
km mm1
$ fa(
Bll(a Mc) (4)1
K
K
(x()
Blll( - pIlll;
K
t=
S fM(x))
B B|[ |r||]B[[1a 1
1=1
= =~'""")0
d denotes the number of dimensions,
where (xx (x) me) denotes the inner product of the two vectors, the expectation E is over the random vectors Tk Bt (M, 0² Ia), and the fourth line is from the application of the Cauchy-Schwar inequality expectations. Replacing J (x') 2N f(x") for EPGS and (xx) f for PGS gives the desired result.
C.7. Proof to Theorem 3.7
Theorem 3.7 Let {mo T&d be produced by following the iteration rule of (5), with pre-selected and deterministic No and all the involved terms defined in Section 3.2. Then, under Assumption 3.1 and 3.2, we have that
T- and ( fN ((((=)))FF(())))) + LG
Σ
where L and G are as defined in Lemma 3.5 and Lemma 3.6, respectively.
Proof. By the Gradient Mean Value Theorem, there exists Vc E Rd such that Vr, lies between 14+1, and Pe, for each of the ith entry, and
F(p4+1) =F(,) - (VF() Me),
=F(M) (VF(4))) - (1) + (VF(u)) VF(M) - 14)
=F(M) ==((V (VF(4) - (F(c:))(4441 14)
2F(p,) (V - L|(e, Hell || - Hell, by Lemma 3.5,
2 (VF()))))))) All mel1
= =F((: (VF(( - - [x
where denotes the vector transpose, and the second inequality is because Vt, is between Pe+14 and Pr.s- Taking the expectation of the left-end and right-end of the above derived inequality gives
E[F(((1)) ZE (p)) (E(F(()) a LEEII(E -
(16)
2E(F(m) + (E L,
where the second inequality is because of Lemma 3.6, and for the first inequality, note that
([VVF())) -E (VFF())) (F by o(
Taking the from to T - 1 on both sides of (16) gives
T-1 LG Σ o
[[F()T)] B(F + Σ a. "
t=0
1=
18

---

Power Transform and Gaussian Smoothing
Re-organizing the terms gives
a,o ( B[F(Ho)] + LG
$ fN(x=)) - F(HO) + IG
Σ
1=0
This finishes the proof for Theorem 3.7.
C.8. Proof to Corollary 3.9
Corollary 3,9 Suppose Assumption 3.1 and 3.2 hold. Let {pr} be produced by the stochastic gradient ascent rule (5) of GS-PowerOpt, with a pre-selected and deterministic po Then, for any E (0, 1), after
T> (CiCzde-1)3/1e -0
times of pe-updating by (5), we have that m [l| <. Here, 7 E (0.1/2) is a parameter in the learning rate == (t + 1)/24))))) Co fN((*) - F(HO) + 2f (x") E (1412)), C1 Co(1 -2y)0 and C2 = max (,
Proof. For any non-negative integer 1, define
== min
(17)
(E.........
Then,
T-1
T-1 aorn, Vr,
Σ
arorvr vT S
since V/41 S P4 for each 0,
< and [V(()))))
since v4 - B[| from (17),
< fN((=)) F(MO) I.G Σ
2
from Theorem 3.7,
S fN((2') - F(MO) - -20 f (x*)
(1+27),
d comes from L in Lemma 3.5 and G in Lemma 3.6,
t=1
[N(x²) F(JOo) + 2/ (xx)
(1+27)
L.
since d > 1 and fx(#") 2 F(ua),
1=1
= Codl,
where Co = fN((x')) F(H0) + +2f2
Σ (1+2g) < 0c.
(18)
Therefore, we have
Σ
a vT S Codf.
t=ol
19

---

Power Transform and Gaussian Smoothing
Since or (1 1)- (1/22+)) dividing both the left-end and the right-end of the above inequality by Ei=o 0,0² gives
Cod
MT 5
21=1 (1/22+))
Cod?
0² S (11/2t1))
Cod2
2 -7 - -7)
Cod
when T >> 22/(1-21)
22 - 1/2/(22 7)
d²
Co
C1 72-7"
where C1 02(1/2)/(( -7) --)
In sum, we have
d²
vr S 01 T3-
whenever T> 22/(1-21)
(19)
Define C2 == 2/C11, Given any & E (0, 1), whenever T> -1CC(==11//(22211 0(((==1)))(0-2))) we have
T> (C3CidE=)))/(L-2)) (C1C2)2/U-21) 22/(1-211,
and
d²
d²
ur 5 from (19) Ci T3-7 (c
C1
C2
times of updating μr by GS-PowerOpt, eT This implies that after T -(((E=11)/11-21)
minge (0, 1.2....... (()))) <.
C.9. Proof to Proposition 3.11
Proposition 3.11 Assume Assumption 3.1, f(x) = 0 on the boundary of f's domain, the Lipschitz condition on f: [f(z) - f(y)l < Lollæ - yll, and the Lipschitz condition on f: [[[ - Vf()il & Lı|l yll. Then, the following two statements are true.
1. IN (1i) VNN (12) < Dllp1 u2ll holds for any 14, A12 E Rd,, where L = (NI NNN 1)L3fN-2 (x²))) under the PGS setting, and L (N Nf(=") + 2 Lge under the EPGS setting.
2. The teration complexity in Corollary 3.9 reduces Ow (12/111//1--211)
Proof to Point I. We extend the domain of f from S to Bd such that (xx) = for any x + S. Clearly, after the domain extension, the two Lipschitz conditions hold R.d. From (4), with the extended f.
(x)), Nlww) (EPGS setting).
(PGS setting):
fx(#) -
By definition,
(N) = SnnN
= -V2mm) d [ MERS
(N(W (0m)))=1777 1 da
JEERS SN(U + of)e 1612 de, x = μ gg
(V2R) d
= -Be-vorr,
20

---

Power Transform and Gaussian Smoothing
Let V denotes the first derivative with respect μ.. Under the PGS setting, Then,
IVFN,o((11) (M2)l
[IEIVSN( (1) - V/N(H12 aE)IIl
||E[N| ( VfN(() - (ves
= (/IBL/"~ (V/x(()))) - V(N((22)) + (11) (12x)
- V(N(P22)) + NT. - -
S NN ||| u2 N(V 1)8 Lo - f(u2,e)
- ANfN~1(a L1 [11 - p2l + NNN - 12f L - -ell
- (N "x L1 + N(N - ->=))>
p2ll:
where full = μm + o. 42,5 = μ2 + og. the first inequality sign is derived using the formula
10 of ||Ex]] S B||a=1 and
the result that || V fl I Lo from the Lipschitz condition on f. and the second inequality sign is derived using the formula a- - 1-
(a- - b) En a"6N~2-1,
Under the EPGS setting, V (n + oE) = (( oE). Then,
( (M2)) LEVV + =E) - VIN + oE)l
MIILETENNSMII. s) (VIN(MI, v(N(H2E)) + (e flmn)) -NNims)))
Bl E// V/N(HZ))) + NL Nluna))
& NE( La |1 - 12 N Lollmn - pell, by mean-value theorem,
(NIIeN -N
-22l--
Proof Point Point 2 can be proved from modified version of the proof to Corollary 3.9. Specifically, when deriving (18), replacing Lemma 3.5 by Point of Proposition 3.1 1 removes the dependence of L on d, which decreases the power of d by on the right-end of (18). This in turn replaces d by d in the rest of the proof to Corollary 3.9, and finally leads to the desired iteration complexity in Point 2 of Proposition 3.11. Note that Co needs to be redefined accordingly in (18). D
C.10. Proof to Corollary 4.2
Corollary 4.2 Under Assumption 3.1 and 4.1, the iteration complexity in Corollary 3.9 becomes (((8{=1)y0/(-2))) and the iteration complexity in Point 2 of Proposition 3.11 becomes ((dd=-1)//0-21)) both of which are independent from N.
Proof. The dependence of the iteration complexity (I((f==-1)a/(11 in Corollary 3.9 on N comes from Co fNv (ax) F(Ha) + 2 (a=) Een (1(12)), Assumption 4.1 guarantees that Corollary 3.9 still holds true if Co is redefined
as
Co 11++2 (1 (1-2.)
which is independent from N. To prove that Corollary 3.9 still holds true with the above new definition of Co, we only need to modify the last line of (18)
This makes the iteration complexity in Corollary 3.9 become
in the proof to Corollary 3.9:
fx(=")- -(p)))F(()))) + (x Σ (1422) d < 1+ Σ b (1+22)) de = Cod?
This inequality can be derived from Jensen's inequality and the fact that Fuclidean norm || || convex.
21

---

Power Transform and Gaussian Smoothing
where the inequality can be justified by [x((") E [0, 1) (a result immediately implied by Assumption 4.1).
Next, we prove that the iteration complexity in Point 2 of Proposition 3.11 becomes O((de=)))/(1-21) under Assumption 4.1. Let be defined as in (17).
T Σ
C s fN(x=") F(HO) + L.G
Σ
2
2
from the third line in (18),
t=
S ffv(x") F(HOO) + Ldo f2(x')
2
from Lemma 3.6,
1=0
00
SN((=') F(NO) + 2do2
Σ
0i
2
since [N(#²) 1),
SN((x') F(HO) + B(L1 + do
2
from (20) given below,
1=0
$ (1+ B(L1 + 06)0² 2 Σ a af)d,
2m0
0 where Co 1 + B(L1 + O
Cod,
ai.
In sum, we have Ero a I Cod, where Co 1 + B(L1 + L8) Ei af is independent from N. This result, and the rest of the proof (where the term dl is replaced by d) to Corollary 3.9 after Eq. (18), gives the desired iteration complexity of (((de-1)2/(a22))
Finally, it remains to prove for some constant B > 0,
S B(I + T2.-
(20)
Under the PGS setting, from Point of Proposition 3.11, L = 1 + N(N 1)L38N-2(x*) (x*)). f(x*) e [0, 1).
Since
lim N
NFN" = lim N
N(N - (x") 0,
which implies both (N=1(x") and N(N 1)f (x²) are upper bounded by constant B for all N 2 0. This implies L < B(L + LZ).
Under the EPGS setting, from Point of Proposition 3.11, (N ((w0") + N2 (Tee")))))) Since s(x*) < O.
lim Ne N((a")
lim N
NS(0)) =0,
N N
which implies both N(a") and N2 NT(m") are upper bounded by a constant B for all N 2 0. This implies < B(4++ + (2).
D. More Details and Discussions on Compared Algorithms
D.I. Zeroth-order Gradient Algorithms
The two zeroth-order gradient algorithms, ZO-SGD (Ghadimi & Lan, 2013)) and ZO-AdaMM (Chen et al., 2019), aim to solve max, E[x + og]. Here, & denotes a random noise and we select it to be a standard multi-variate Gaussian vector. For non-concave maximization problems, they are theoretically guaranteed to converge to stationary points of f. In our experiments, we take the scaling parameter a as hyper-parameter
22

---

Power Transform and Gaussian Smoothing
D.2. STD-Hoomt
STD-Homotopy is standard homotopy algorithm for optimization. It has a double-loop mechanism. The inner loop updates the solution μ4 with fixed scaling parameter until no improvements of f(v,, made, and the outer loop decays iteratively. In this algorithm, the term (F,, σ)) is an estimate LEn-N(,. - ()f(()) Ne (f which is used to update μs.
Algorithm 2 STD- HT--Hooot
The maximum of iteration number Tiotsl > the initial scaling parameter O, the objective f. the initial value Ma, the number K of sampled points for gradient approximation, the maximum number N₂ of times gets updated, the maximum Tp of the number of times μe gets updated for each value of a, the tolerance number for no improvements of (())) for any fixed σ, the decay factor E (0, 1), and the learning rate a₁ > O.
Input:
Initialize 1 = 0, Rgg = O.
while t - Teotal and nh < No do
0, True.
while T2 and = True and t S Total do
Independently and uniformly sample K points {vx ] from the uniform sphere in R Compute 24. 14 0.k. for each k.
Compute the gradient estimate (F o) = 1 K Ex= (ax (xx)
14++1 = 14 + a4 V VI (pt,
if maxx (fx(e(((+)); f( f(u), f f(1+-++1)} S f(H(-)) then
=False.
end if
t 11 1, 1.
end while
σ = y0, nie nr + 1. end while Return((u,,) ).
D.3. ZO-SGD
The zeroth-order stochastic gradient ascent (ZO-SGD) is maximize-version of Equation (1) (Chen al., 2019), whose gradient estimate method is from (Nesterov & Spokoiny, 2017). The gradient-ascent version of this algorithm in Algorithm 3.
Algorithm 3 ZO-SGD
Input::
The scaling parameter > O, the objective f, the initial value E Rd the number K of sampled points for gradient approximation, the total number of p-updates, and the learning rate schedule {ai)T-. for t from to - do Independently and uniformly sample K points { from the uniform sphere in Rdd Compute the gradient estimate
(fpp ovx) - f())))o
VF 0)
Σ
P111 = p4 + 04 (FN(M, end for Return((UT).
23

---

Power Transform and Gaussian Smoothing
E. Details on the Experiments for Figure 4
The set of N-values is {10, 20, .... ] for PGS and {1.0, 1.5, 2.0, 4.5] for EGS. For each value and each algorithm. we do 100 trials to stabilize the result. In each trial, the initial solution candidate μo is uniformly sampled from C (ær e |= [-1.0, 1.0], E (1,2, ) where I; represents the ith entry of æ. We the initial learning rate as 0.1, the scaling parameter as 0.5, and the total number of solution updates 1000. The objective for PGS is modified be fi (x: == [()) + 10 to ensure that the PGS agent will not encounter negative fitness values during the 1000 updates.
F. Hyper-parameters
For experiments on the benchmark test functions (Table and 2), the set of hyyper-paramete values with the smallest mean square error (averaged over the 100 experiments) between the true and estimated solutions are selected. The of candidate values, well the selected values, are listed in Table and 7.
For the image attacks (Table 3 and 4), for each set of the hyper-parameter candidate values, we randomly choose 10 images to attack. The set with the highest average fitness value (average over the 10 image attacks) will be selected. Table 8 and 9 reports the candidate set and the selected values.
Table 6: Syyper-parametes for Optimizing Ackley. The candidate set for learning rates is : (-1, 0001.. The candidate set for smoothing parameters is S := {.1, 1.0, 2.0}. t in ZO-SLGHd and ZO-SLGHr is the initial scaling parameter. l in ZO-AdaMM is the scaling parameter. The set of candidate values that lead to the minimum mean square error between the true solution and the found solution will selected. For CMA-ES, do denotes the initial standard deviation.
Selected Values
Candidates
CMA-ES
0g 1.5 au 11, N 1. 1.0.
σo 1.,
EPGS
Ne (1,2,3), ag E L
PGS
on .1, N =20, 1.0.
N
20, 20, on E o. E. a
STD-Homotopy
II
5. a = 2.0,
Tμ 500, = 100, No
10.
70-SL-GHd
001,
= .001, 4
B E [.1, E f11, 4 S. e
2.0, 7 .99
{.99, .95..
ZO-SLGHr
0001,
0.1, 7
BE (.999, .95), ES
.995
Z0-AdaMM
B1 5, 8/ = 5, = 0.1,
a C. 8 E (, 9). 32 (11.3,55, EES
1.0.
ZO-SGD
Q = 1, 0 = 1.0.
a a MES.
G. Adversarial Images
We randomly select four images [4m]4==1 from the image set and perform a per-image adversarial attack on each of them, using each of the compared algorithms. Table 10 and 11 report the adversarial image a. + n with the highest R² score, given that the attack is successful. That is. pm arg max, pm E TT R2 (am: am pm,)), where {mm.) T denote the sequence of perturbations generated during the m attack, and T is set at the same value (1,500) as in Table 3 and 4. According to the results in Table 10 and 11, the performances the compared algorithms are consistent with the statistics reported in Table 3 and 4.
24

---

Power Transform and Gaussian Smoothing
Table 7: syper-parameters for Optimizing Rosenbrock. The candidate set for learning rates is c (.2, .0,,,,,011111.. .0..0001..000 .0001). The candidate set for smoothing parameters is S (1.0, 2.0). &1 in ZO-SLGHd and ZO-SLGHr is the initial scaling 1,000aa
parameter. μ in ZO-AdaMM is the scaling parameter. For EPGS and PGS, dx 1,000+t' The set of candidate values that lead to the minimum mean square error between the true solution and the found solution will be selected.
Selected Values
Candidates
CMA-ES
On .1. ag = .1, N 1 = 1.0.
on E 5,,,
EPGS
E (1,2,3), d E E.
PGS
Qg ., =1,0- 1.0.
Ne [1,3,5) ag E E
STD-Homotopy
2,, ? -2.0 2.0,,
7 (2
Тμ 500, = 100, No
10.
ZO-SLGHd
B = .0011, = .011 t =
B E C. E (11,.01, 001),, t
S, E
2.0, 7 = .999
{-99, .955, .999].
ZO-SLGHr
= .0001, 1 2.0, 7
B C, 7 E (.999, .95), ES
.999.
ZO-AdaMM
B1 5, 82 5, 2. a C, 81 E (,5, 32 (1,,3, PES
2.0.
Z0-SGD
= .001, 2.0.
a E C, MES.
Table Hyper-parameters for MNIST Attack. The candidate set for (initial) smoothing parameters is := (1.0,.1). The hyper-parameter symbols for each algorithm the same their source publications. For example, i ZO-SLGHd and ZO-SLGHr denotes the initial scaling parameter, μ in ZO-AdaMM is the scaling parameter, and a denotes constant learning rate. The number 784 equals the dimensional number d. It appears in the candidate set since it is taken from (Iwakiri et al., 2022), who performed similar experiments. The set of candidate values that lead to the highest fitness (averaged over the 10 image attackes) are be selected. For CMA-ES, d denotes the initial standard deviation.
Selected Values
Candidates (Ą4*)
CMA-ES
Gg .05.
an (.05,.1,
EPGS STD-Homotopy
.I, N -05, 1.
N E (.02, .04, .05), a (.1, S.
5, 7 -5, 1.0.,
E {.5.8)) a [.5, S.
т₁ 500,
= =100, N₂
10.
ZO-SLGHd
B = 10-4, = 1/784,
B E (1/784, 10-4, ..1., E {.1/744, 10-3), 3,44 4 e
t = 1, 7 = .995
S. E (.999.
Z0-SLGHr
4 4 11
B E (10-1 1,784,,
E (.999, (.999,9995). (55),,, 4 E.
.95.
ZO-AdaMM
B1 9, 8n a 1.
E (100/784, .011 3 E (55.9), B2 e
1.
{.1, u E
ZO-SGD
= 10 11
a
25

---

Power Transform and Gaussian Smoothing
Table 9: Hyper-pan sareer-arammters for CIFAR-10 10 Attack. The candidate set for (initial) smoothing parameters is S {1.0, .1}. The symbols are the same as those in Table 8. The set of candidate values that lead to the highest fitness (averaged over the 10 image attackes) are be selected.
Selected Values
Candidates (1²*)
CMA-ES
Ou .05.
Ou .1.
EPGS
= .1, = =.03, a = .I.
E (.02, .44, at E (.1, e..
STD-Homotopy
.5. 7 -8. σ ..
2 (.5.8)..c as (.1.5), 0e
Тμ 300, = 100, No
10.
70-SL-GHd
3 = .01 /3072, = 10
B E (.01 (.01/3072, 11. (10 10 ") e
1 = 1.0, = .999
S. E [.995, .999).
ZO-SLGHr
= .01 03/077 t = 11,7
B E 01/33072..1,,7 E (.999, t E..
.955.
ZO-AdaMM
B1 9, 32 a .1
a E (5/3072,.001,, 31 (.5, B2 e
(11,3),,
ZO-SGD
.01 01/3072, == .1
100 S.
26

---

Power Transform and Gaussian Smoothing
Table 10: Adversarial images for MNIST, produced by algorithms that apply the smoothing techniques. The adversarial target label T arg min; (C(a)); is the label with the minimum predicted probability. All attacks successful.
Test Image ID
9953
3850
4962
3886
Co
2
6
C(
Original Image
Adversarial Target Label T
9
3
6
2
6
c
EPGS la 1*)
90%
88%
78%
93%
6
C1
ZO-SLGHd (a a )*)
70%
61%
41%
76%
6o
6
ZO-SLGHr aa +x)
68%
55%
14%
74%
Co
6
c
ZO-SGD la a + 4*)
85%
76%
61%
87%
6a
C
ZO-AdaMM R2 a + 1**)
50%
36%
15%
60%
6
6
STD-Homotopy R (a, a + 4*)
21%
15%
- -19%
61%
27

---

Power Transform and Gaussian Smoothing
Table 11: Adversarial images for CIFAR-IO, 10, produced by algorithms that apply the smoothing techniques. The adversarial target label 7 arg min, (C(a)); is the label with the minimum predicted probability. Unsuccessful attacks (i.e., predicted label is different from the adversarial target) are marked with "Unsuccessful".
Test Image ID
9953
3850
4962
3886
Original Image
True Label
7 (i.e., Horse) 1(i.e,, Automobile)
(i.e., Truck) 4 (i.e., Deer)
3 (i.e., Cat)
8 (i.e., Ship) 7 (i.e., Horse)
Adversarial Target Label T
4 (i.e., Deer)
EPGS R (a. a + 1*))
96.0%
99.3%
99.0%
96.1%
ZO-SLGHd R +²a
99.2%
99.6%
99.6%
98.3%
ZO-SLGHr 1e a 4*)
97.7%
99.5%
98.8%
94.3%
ZO-SGD 12 a + )
Unsuccessful.
99.6%
99.8%
99.1%
Z0-AdaMM R2 a +²)
39.6%
92.0%
84.9%
39.7%
STD-Homotopy R² (a, a + 1²)
Unsuccessful.
Unsuccessful.
93.2%
92.8%
28


Reviews:
[{"review_id": "LTdomsSMxw", "reviewer": "Reviewer_T8wQ", "summary": "This paper presents a new method for global nonconvex optimization, wherein the objective is first re-weighted either via a power-transformation or an exponential transformation, and then Gaussian smoothing is applied. A handful of theoretical analyses are provided for the method (assuming perfect integration of expectations), including a sufficient condition for transforming all stationary points into a neighborhood of the global optimizer, and an iteration complexity analysis. Experiments to illustrate the effectiveness of the proposed method are provided on low-dimensional nonconvex benchmark problems and on MNIST and CIFAR-10 image classification problems.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "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": "Thank you for your detailed and insightful comments! They are very helpful for us to improve the manuscript. As suggested, we will \n* include CMA-ES in our experiment for comparisons. \n* use the $L_2$-norm of the perturbation $\\mu$ as the distance metric instead of $R^2$. \n\nWith the above changes, we perform experiments in Table 1 and 2 with CMA-ES and re-run our experiments in Table 3-4. The image pixels are normalized to lie in [-1,1]. The results are as follows.\n\n**Table R1. CMA-ES on Benchmarks**\n| Test Fcn. | Iter. Taken | $\\mu^*$ | $f( \\mu^*)$ |\n|-|-|-|-|\n| Ackley  | 117 | (0.0, 0.0) | 22.718 |\n| Rosenbrock   | 70 | (1.0, 1.0) | 0.0 |\n\n**Table R2. MNIST**\n| Algorithm | S-rate | $\\lVert \\mu^* \\rVert$ | $\\bar{T}$ |\n|-|-|-|-|\n| CMA-ES | 100%  | **2.81**(0.61) | 1489(12) |\n| EPGS (N = 0.02) |100% | **2.97**(0.54)  | 429(105) |\n| ZO-SGD   | 100% |  **3.14**(0.61) | 1426(241) |\n| ZO-SLGHd   | 100% |4.07(0.64) | 1485(51) |\n| ZO-SLGHr  | 100% | 4.83(0.81) | (475)(657) |\n| ZO-AdaMM  | 100% | 6.89(1.15) | 44(15) |\n| STD-Homotopy   | 97% | 8.25(1.09) | 529(264) |\n\n**Table R3. CIFAR10**\n| Algorithm| S-rate | $\\lVert \\mu^* \\rVert$ | $\\bar{T}$|\n|-|-|-|-|\n| CMA-ES  | 99% | 10.06(2.35) | 157(399) |\n| EPGS (N = 0.03) | 98% | **3.04**(0.54)  | 748(247)|\n| ZO-SGD   | 62% | 1.189(0.61) | 764(348) |\n| ZO-SLGHd  | 98% |**1.72**(0.64) | 1290(411) |\n| ZO-SLGHr  | 98% | **2.66**(0.67) | (456)(344) |\n| ZO-AdaMM  | 100% | 13.13(2.71) | 44(15) |\n| STD-Homotopy | 52% | 7.54(1.56) | 566(396) |\n\n# Results Summary\nFrom Table 1, 2, R1, and R2, we see that CMA-ES is the winner. EPGS ranks in the top three and its performance is close to CMA-ES. Table R3 shows that, although EPGS and the two ZO-SLGH has its success rates 1-2% lower than AdaMM and CMA-ES, their perturbation norms are significantly lower. Therefore, we consider them as the top three in this task.\nAlso, we noticed that the CIFAR10 task took significantly more time for CMA-ES than other algorithms to run, which we believe is due to its high computational complexity incurred by updating the covariance matrix.\n\n**Conclusion:** EPGS is the only one that is always in the top 3, and its performance is close to that of the winner. Please see my reply to Reviewer JoQA (Section 3.1) for more comparisons between EPGS and CMA-ES.\n\n# Answers to Questions in \"Other Comments or Suggestions\"\n1. Yes, we meant to assume that $f$ has a unique global optimizer $x^*$ and will corrected.\n\n2. In Line 72, we apologize that we did not state the result in Theorem 10 in (Chen et al., 2024) correctly. The correct statement is \"their theory (i.e., Theorem 10 in (Chen et al., 2024)) bounds $|f(x^*)-f(\\mu^*)|$ with $O(N\\sigma^2)+G(N,\\sigma)$\" where $G(N,\\sigma)$ is in general non-linear in $N$. Therefore, neither increasing $N$ nor decreasing $N$ necessarily lead to an improvement.\n\n3. We will move the definition of $F_N$ in Section 2.2 before Figure 1.\n\n4. Yes, the integration is over $\\mathbb{R}^d$.\n\n5. We will add intuitive explanations to the theoretical results in the revision.\n\n6. In experiments, we did not change the initial value $\\mu_0$ when selecting $N$ by trials. But what you proposed can be an adptive method for speeding up the selection of $N$. We believe poor initializations near local optimums will not affect GSPTO's performance much, given a large value of $N$ and enough samples in each iteration. The reason that we do not start with a very large value of $N$ is, it may lead to a large variance of the updating term in Eq. (5), and in turn significantly increase the sample requirement of GSPTO.\n\n7. We will correct the typo.\n\n8. We will include CMA-ES in our experiments in the revision.\n\n9. We will change as suggested.\n\n10. Please note that by PSO we refer to particle swarm optimization.\n\n11. We will change as suggested.\n\n12. This was probably a typo. We will correct it.\n\n13. We will correct $C$ to $\\mathcal{C}$ as suggested.\n\n14. Yes, it should be an $L_2$-norm.\n\n15. Yes, we will change ``Figure MNIST\" to MNIST.\n\n16 and 17. We will remove the parentheses as suggested.\n\n18. We will used $L_2$-norm as suggested.\n\n19. As suggested, we performed new MNIST attacks (same as those in Table 1, including CMA-ES) where $\\epsilon \\tanh(\\mu)$ is used instead of $\\mu$ as the perturbation to strictly constrain the image attack budget. Here, $\\tanh$ is the entry-wise hyperbolic tangent function. \nWhen $\\epsilon$ is set as the typical value of $2\\times (8/255)\\approx 0.0627$, none of the tested algorithms is successful in any of the 20 attacks. Clearly, more hyper-parameter tunings are needed for all these algorithm. We are probably not able to finish it before the author response deadline, and we apologize for it. Though, there is another way **to address your concern** regarding the attack budget. In both Table R2 and R3, the average $L_2$-norm of the successful perturbations produced by EPGS are among the lowest three, indicating a good budget efficiency of EPGS.", "claims_and_evidence": "In general, the claims are supported by clear evidence (e.g., mathematical proof for the theoretical results). Comparisons to stronger evolutionary algorithms such as CMA-ES would provide more convincing evidence of the experimental conclusions.", "methods_and_evaluation_criteria": "The methods and evaluation criteria make sense for the problem at hand, for the most part. One issue is that an $R^2$ value is used to measure similarity between nominal and attacked images, which is not the standard metric used by the robust ML community.", "theoretical_claims": "Based on a brief overview of the proofs in the appendix, the theoretical claims appear to grounded in rigorous analysis.", "experimental_designs_or_analyses": "The experiments are sound/valid for the most part. One issue is that the attack strength is not explicitly constrained to be the same amongst the various methods being tested on the image classification attack tasks. This has the potential to make the reported success rates misleading.", "relation_to_broader_scientific_literature": "This paper focuses on nonconvex optimization, which is applicable to essentially every domain of science and engineering. The paper does a relatively good job at relating the proposed method back to similar techniques in nonconvex global optimization, coming from smoothing methods and evolutionary algorithms.", "essential_references_not_discussed": "N/A.", "other_strengths_and_weaknesses": "The paper introduces a nice idea for turning nonconvex optimization into an easier-to-solve problem. The theoretical analyses are very thorough. Overall, the paper is pretty well-written.\n\nFor specific weaknesses and concerns, see my \"Other Comments Or Suggestions\" below.", "other_comments_or_suggestions": "1. Line 42: In general, for a continuous function $f$, it must be that $f(x^*) = \\sup_{x\\ne x^*}f(x)$ (removing the maximizer does not change the supremum). For example, if $f(x) = -x^2$ and $\\mathcal{S} = [-1,1]$, then $f(x^*) = \\max_{x\\in \\mathcal{S}} f(x) = 0$ and $\\sup_{x \\in \\mathcal{S} \\setminus \\{0\\}}f(x) = 0$. Perhaps what you meant to say here is that you are assuming $x^*$ to be a unique global maximizer?\n2. Line 72, Column 2: \"...which does not imply an improvement for increasing the value of $N$.\" But it does seem to for decreasing values of $N$, does it not?\n3. Figure 1 caption: The notation $F_N$ is used here before it is defined in Section 2.2.\n4. Theorem 1: Do you mean to integrate over $x\\in\\mathbb{R}^d$ instead of $x\\in\\mathbb{R}^k$?\n5. The theoretical results are quite dense. It would be nice to accompany them with some intuitive descriptions, at least for the most important results such as Corollary 3.9.\n6. Section 6.1 (experiments): Does this convergence of $\\mu^*$ towards the global optimizer $x^\\star$ depend on how you initialize your stochastic gradient algorithm at each level of $N$? In other words, are you taking $\\mu_0$ for problem $N$ to be $\\mu^*$ from problem $N-1$? What happens if you don't do this? Is your method for converging to the global optimizer robust against poor initializations? If so, why bother ever using small or moderately sized $N$?\n7. Typo in Footnote 7: \"designed to solves\" should be \"designed to solve\".\n8. I would think that you would want to include CMA-ES [1] in your comparison against evolutionary algorithms, as it remains one of the state-of-the-arts in that area.\n9. I suggest re-wording \"features with a numerous number of local optimums\" to \"features numerous local optima\".\n10. \"shows that EPGS and PSO are superior than other algorithms on this task\" It looks like this is not necessarily the case. Based on the listed objective values, EPGS is second best on this task (with particle swarm being best), and PSO is only fourth best and does not find the optimizer $(1,1)$. I suggest re-wording your descriptions around this experiment to coincide with the numerical results being reported.\n11. The values listed in the right-most column of Tables 1 and 2 should be put into math mode. Currently, the formatting makes the negative signs in Table 2 look like hyphens, rather than mathematical negative signs.\n12. If the maximum number of iterations in the Table 2 experiment (Rosenbrock) is $T=1000$, how come ZO-AdamM uses 1736 iterations?\n13. Line 347, Column 2: To maintain consistency, I suggest using the notation $\\mathcal{C}$ in your definition of $\\mathcal{T}$ rather than $C$.\n13. Line 347, Column 2: Do you mean $\\ell_2$-norm instead of $L_1$ norm?\n14. In a few places, you write \"Figure-MNIST\", where I think you meant just \"MNIST\".\n15. Line 365, Column 2: Remove the double parentheses in ((Carlini & Wagner, 2017)).\n16. Footnote 9: Remove the double parentheses in ((Abadi et al., 2015)).\n17. Sections 4.3.1 and 4.3.2 (MNIST and CIFAR-10 experiments): I have not seen anyone use an $R^2$ value as a similarity metric for nominal and attacked images in the robustness literature. Why wouldn't you use a norm-based measure of distance? That's what you're using in your regularization term, so it seems a bit odd to all of a sudden switch to reporting $R^2$ values. Can you at least justify your choice of similarity metric by citing another work from the robust ML literature that uses the $R^2$ value?\n18. Your experimental comparisons in Sections 4.3.1 and 4.3.2 seem like they need more controls. Specifically, in comparing attack methods, you really should enforce the same limitation on attack budgets for each method. This is usually done in the literature by enforcing a norm constraint, e.g., $\\|\\mu\\| \\le \\epsilon$ for some attack radius $\\epsilon$ used to encode the attacker's strength. Without such a constraint, the success rate that you report could be meaningless, since, in theory, some optimization algorithm may inherently favor the first term in your optimization objective over the regularization term, resulting in more effort being placed in successfully attacking the system, even at the expense of using a large-magnitude attack.\n\n\n[1] Hansen, Nikolaus, and Andreas Ostermeier. \"Completely derandomized self-adaptation in evolution strategies.\" Evolutionary computation 9.2 (2001): 159-195.", "questions_for_authors": "See \"Other Comments Or Suggestions\" above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vauxsEq3VH", "reviewer": "Reviewer_JoQA", "summary": "This paper deals with global optimization of non-concave functions on compact domains - basically where regular gradient methods get stuck in local optima. The authors introduce a method called Gaussian Smoothing with a Power-Transformed Objective (GSPTO). It works in two steps: first, they transform the objective function using a power function (either $f(x)^N$ or $e^{N f(x)}$), then apply Gaussian smoothing by convolving with a Gaussian kernel. The main insight is that with a large enough power $N$, you can make the smoothed function's maximum get arbitrarily close to the true global maximum $x^*$.\n\nMain contributions:\n- they prove that with mild conditions (continuity and a gap between global max and other points), you can pick a large enough $N$ so the smoothed function's maximizer is within any $\\delta$-neighborhood of $x^*$. They show iteration complexities of $O(d^4 \\epsilon^{-2})$ generally and $O(d^2 \\epsilon^{-2})$ with Lipschitz conditions.\n- they present two versions - **PGS** (using $f(x)^N$) and **EPGS** (using $e^{N f(x)}$). Both update solutions using zeroth-order stochastic gradient ascent with Gaussian samples.\n- they test on standard benchmarks (Ackley and Rosenbrock functions) and high-dimensional adversarial attacks (MNIST and CIFAR-10). Results show their method beats other smoothing approaches and competes well with state-of-the-art global optimization methods.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "Thank you for your detailed and insightful comments! They are very helpful for us to improve the manuscript. \n\n# 1. Replies to \"Questions For Authors\"\n## 1.1 Guidance on Choosing $N$ and $\\sigma$\nWhen tuning, we recommend to start from a moderate $N$, rather than a large $N$, since it increases the variance of the updating term in Eq. (5), which requires more samples for GSPTO to be stable. Based on our experience, the user may start from 10 and increase by 10 each time. For EPGS, we recommend the user to start from 1 and increase by less than 1 each time. For high-dimensional problems like image attacks, we recommend to start from $N=0.01$. \n\n$\\sigma$ controls exploration. A large $\\sigma$ decreases the solution accuracy, while a small one drags down the algorithm's efficiency. Based on experience, we recommend to set it at 10% of the data scale.\n\n\n## 1.2 Parameter Sensitivity\nAccording to our experiment results record when selecting hyper-parameter by trials, our method is robust to moderate change of $N$. Take the MNIST attack as an example, the average $R^2$ is 81.2% when $N=0.01$, 83.3% when $N=0.02$, and 83.2% when $N=0.03$ (the S-rates are all 100%). Note that a change of 0.01 in $N$ is not small, since $N=1$ is extremely large and will cause a computation overflow.\n\nI also performed experiments when $N=1$ (using EPGS with a baseline to prevent computation overflow, see Appendix) on 10 MNIST figures with a max of 2000 iterations. The success rate decreases to 60%, with an increase in the average $R^2$ to the level of 90.5%.\n\n\n## 1.3.The Case of Multi Global Optima \nThanks for asking this question. We really appreicate it.\n\nOur convergence analysis does not apply to the objective $f$ with multiple global maxima. The proof to Theorem 2.1 requires that $f$ has a unique global maximum. \n\nHowever, intuitively, when $f$ has multiple global maxima, if $N$ is sufficiently large, the Guassian smoothed function $F_N(\\mu,\\sigma)$ should have multiple global maxima (and no local maxima) which coincide with those of $f$. This intuition is verified by a simple experiment we performed using the example in Figure 1,  if we modify $f$ so that the two maximum points $x^*_1$ and $x^*_2$ have the same $f$-values, the graph of $F_N(\\mu,\\sigma)$ has two global maximum points: $\\mu^*_1=x_1^*$ and $\\mu^*_2=x_2^*$.\n\nWe also performed experiments with the two-log objective in Figure 2a of the paper, where the two maxima are set to have equal heights. Then, we performed 100 experiments with EPGS on this objective, in the same procedure in Table 1. The average distance from the produced solution to one of the global maxima is $3.2\\times 10^{-5}$, which indicates EPGS is able to locate one of the global maxima.\n\nWe leave further investigations and the corresponding theoretical work to our future researches.\n\n## 1.4. Handling Zero-maxima and Negative Values of $f$\nIf we know that $f$ has a zero global maximum or $f$ is always negative, then we can define a new objective $f_1(x):=\\max${$f(x)+\\eta,0$}, where $\\eta>0$ can be manually selected or $|f(x_q)|$, where $x_q$ is any point in $f$'s domain. Then, $f_1$ is non-negative and shares the common global optimum point $x^*$ as $f$ does. We can then proceed PGS with $f_1$.\n\nIf $f$ has both positive and negative values, we can define the new objective as $f_1(x):=\\max${$f(x),0$} and proceed PGS on it, since $f_1(x)$ also shares the common global maximum point as $f$ does.\n\nAn alternative method for the above two cases is to apply EPGS instead of PGS on $f$, since EPGS does not require that $f$ is positive.\n\n# 2. Replies to \"Essential References Not Discussed\"\nWe will add the literature of evolutionary algorithms to our revision, such as simulated annealing, cross-entropy method (CEM) for optimization, and the covariance matrix adaptation evolution strategy. GSPTO is indeed related to these methods, especially the CEM. Thank you for pointing this out.\n\n# 3. Replies to \"Other Comments or Suggestions\"\nWe will include CMA-ES and simulated annealing in the experiment in the revision to our paper.\n\n## 3.1 Comparing with CMA-ES\nAs suggested, we performed experiments in our Table 1-4 with CMA-ES. The results are posted in Table R1-R3 in my reply to Reviewer T8wQ. From the results we can see that, although CMA-ES outperforms GSPTO on benchmark test functions and MNIST attack, their performances are close. On the CIFAR10 task, EPGS outperforms CMA-ES in attack qualities (i.e., smaller perturbation norms).\n\nAnother advantage of GSPTO over CMA-ES lies in its theoretical convergence guarantee, which provides an iteration complexity bound (Corollary 3.9). While CMA-ES has theoretical convergence results for certain function classes (e.g., convex-quadratic functions), such guarantees are less developed for the general stochastic, non-convex setting, to the best of our knowledge.\n\n## 3.2 A Diagram Explaining GSPTO Procedure\nWe will add such a diagram to the revision. Thank you for pointing this out.", "claims_and_evidence": "- The paper claims that with a big enough power N, the maximizer of their smoothed, transformed function gets really close to the true global optimum x*. They back this up with formal proofs in Theorem 2.1 and Corollary 3.9, and their experiments show that as N gets larger, the mean squared distance to x* actually does decrease.\n\n- For convergence speed, they show their algorithm reaches an ε-approximate stationary point in  $O(d^4 \\epsilon^{-2})$ iterations generally, and this improves to $O(d^2 \\epsilon^{-2})$ when the function has Lipschitz smoothness. These complexity results use standard assumptions and they clearly show how this improves on previous methods.\n\n- In their experiments on benchmark functions and adversarial attack problems, the proposed methods (particularly EPGS) outperform the baselines by achieving better objective values and perturbation quality. They ran lots of trials and included standard deviations, so the results seem statistically solid.", "methods_and_evaluation_criteria": "The paper combines power transforms with Gaussian smoothing, which makes sense - the transform boosts the global optimum and makes the smoothed landscape easier to navigate with gradient ascent. They give us two variants to handle different cases (one for non-negative objectives, another for general cases).\n\nFor evaluation, they compare against several global optimization methods - standard homotopy approaches, single-loop Gaussian homotopy variants, zeroth-order methods (ZO-SGD, ZO-AdaMM), and PSO.\n\nTheir metrics are straightforward - for benchmark functions, they report best objective value and iteration count. For the adversarial attack experiments, they use success rate and an $R^2$ similarity score (which measures perturbation size), covering both how effective and efficient the method is.\n\nThe experiments cover both simple synthetic functions and complex real-world problems with high dimensions. They run multiple independent trials to ensure the results aren't just lucky, tune hyperparameters using a candidate set approach, and provide all the detailed settings in the supplementary material.", "theoretical_claims": "The paper's main theoretical result (Theorem 2.1) shows that with a big enough power N, the maximizer of the smoothed objective will be within any $\\delta$-neighborhood of the true global maximum $x^*$. This works because there's a gap between f(x^*) and the function values at other points.\n\nFor convergence, they prove that their stochastic gradient ascent approach will reach a stationary point of the smoothed objective, with the complexity results given in Corollary 3.9.\n\nWhen they add Lipschitz conditions, they get a better complexity bound of $O(d^2 \\epsilon^{-2})$. I checked that all the proofs are in the appendix and the assumptions are clearly laid out.", "experimental_designs_or_analyses": "The paper tests their approach on standard benchmark functions like Ackley and Rosenbrock, plus they do high-dimensional adversarial attacks on MNIST and CIFAR-10. They compare against a good mix of baselines including both smoothing methods and evolutionary algorithms.\n\nFor statistical validity, they run multiple experiments (100 trials for the benchmarks) and include standard deviations in their results. I appreciate that their analysis is fair - they don't hide when other methods like PSO work better on certain problems, and they discuss how sensitive their method is to initialization and parameter choices.", "relation_to_broader_scientific_literature": "The authors do a decent job positioning their work in the context of homotopy and smoothing methods literature. They make clear distinctions between their approach and previous work by Hazan et al. (2016) and Iwakiri et al. (2022). \n\nI appreciate how they differentiate their method from other approaches using exponential transforms (works by Dvijotham et al., Roulet et al., and Chen et al.) - mainly by emphasizing their focus on the \"sufficiently large\" power regime.\n\nOne limitation I noticed is that while they compare to PSO, they should really have included references to other important global optimization techniques like CMA-ES and simulated annealing. This would provide readers with a more complete context for understanding where this method fits in the broader optimization landscape.", "essential_references_not_discussed": "The paper could benefit from discussing a few important global optimization approaches:\n\n- The authors should consider referencing CMA-ES (Hansen & Ostermeier), which remains one of the most effective evolutionary algorithms for continuous global optimization problems.\n  \n- I think a brief mention of simulated annealing would be valuable to show how the proposed method relates to this classical global search technique.\n  \n- The cross-entropy method seems relevant here, especially since it would provide context for the exponential weighting concepts used in the paper.", "other_strengths_and_weaknesses": "Strengths:\n- The approach is quite novel and has solid theoretical foundations, filling an important gap in global optimization methods.\n- The paper shows meaningful theoretical improvements in iteration complexity compared to existing methods.\n- The experiments are thorough and cover a good range of problems - both synthetic benchmarks and real-world applications.\n- I appreciate the attention to reproducibility with detailed supplementary materials.\n\nWeaknesses:\n- The method requires tuning two new hyperparameters ($N$ and $\\sigma$) but doesn't provide much practical guidance on selecting good values.\n- It's not entirely clear how the method would scale to extremely high-dimensional problems.\n- The theory assumes there's a unique global optimum - what happens with multiple global optima isn't addressed.\n- The empirical evaluation would be stronger with comparisons to more global optimization techniques like CMA-ES and simulated annealing.", "other_comments_or_suggestions": "I think the paper could be improved with some practical guidelines on how to choose the hyperparameters N and \\sigma. It's not very clear how to select these values for new problems.\n\nThe authors might want to look into some kind of adaptive scheme where N increases gradually during optimization - this could help with convergence.\n\nThe comparison would be stronger if they included more global optimization methods as baselines. In particular, CMA-ES seems like an obvious comparison that's missing.\n\nThe paper doesn't address how the method would behave with multiple global optima, or in cases where the global maximum is only slightly better than local maxima. This limitation should be discussed.\n\nA simple diagram showing how the algorithm works would make the method easier to understand for readers. Even a basic flowchart would help clarify the approach.", "questions_for_authors": "- How do you recommend users select an appropriate value for the power $N$ in GSPTO? Did you employ any specific heuristics or adaptive approach in your experiments? I'm curious about practical guidance for balancing optimization performance against convergence stability.\n\n- I'm wondering about parameter sensitivity - how robust is your algorithm to suboptimal choices of $N$ and $\\sigma$? What degradation in performance occurs if $N$ is chosen too small or excessively large?\n\n- What happens when the objective function has multiple global optima? Does your theoretical analysis extend to guarantee convergence to at least one of them?\n\n- Since PGS requires $f(x) \\geq 0$, what's your recommendation for handling objectives with zero maxima or negative values?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wvQyTj921J", "reviewer": "Reviewer_XuWj", "summary": "This paper applies the Gaussian smoothing technique to solve non-smooth optimization problems. With Gaussian smoothing, the original possibly non-smooth function can be transformed into a smoothed problem, and their method also composites the objective function with the power function or the exponential function. They derived convergence of their methods and show global convergence even for non-convex problems.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "Thank you for your valuable comments! They are very important for us to improve the manuscript. \n# 1. An additional assumption is needed if we require an exact convergence to $x^*$\nYour intuition is right. Our theory needs an additional assumption to ensure a convergence to the exact point of $x^*=\\arg\\max_{x}f(x)$. Cor 3.9 only guarantees that GSPTO converges in probability to a $\\delta$-neighborhood $\\mathcal{S}_{x^*,\\delta}$ of $x^*$. For an exact convergence to $x^*$, we need to decrease $\\delta$ to 0, which requires the increase of $N$ to infinity. However, when $N\\rightarrow \\infty$, the factor in the big-O term in Cor 3.9 may also approach infinity. Specifically, the big-O term equals $ (C_2C_1d^2\\epsilon^{-1})^{2/(1-2\\gamma)}$, where the factor $C_2C_1$ depends on $N$ (see Proof to Cor 3.9 below). For $C_1C_2$ to have an upper bound $C$ that is free of $N$ (which implies a guarantee on the exact convergence to $x^*$ as $N\\rightarrow \\infty$), we need an additional assumption: \n\n**Assumption** *$f(x) \\in [0,1]$ for the PGS case, and $f(x)\\leq 0$ for the EPGS case.*\n\nDue to the limit of reply length, please find the proof for \"this assumption implies that $C$ is free of $N$\" in my reply to Reviewer VChF in Section 1.3.\n\n# 2. Corollary 3.9 implies convergence to the neighborhood of $x^*$\nFirst, we make a correction in Cor 3.9: \n\n$\\mathbb{E}[||\\nabla F(\\mu_t) ||^2 \\|$ in Cor 3.9 should be corrected to $\\nu_t:=\\min_{\\tau\\in \\mathcal{T} }\\mathbb{E}[||\\nabla F(\\mu_\\tau) ||^2 ]$, where $\\mathcal{T}:=${$0,1,2,...,t$}.\n\nDefine $\\mu_T'$ as the point that minimizes $\\mathbb{E}[||\\nabla F(\\mu_t)||^2]$ over $t\\in\\$ {$0,1,2,...,T$}. We prove that, in probability, $\\mu_T'$ converges to a point in $S_{x^*,\\delta}$ as $T\\rightarrow \\infty$. Specifically, \n$$ \\lim_{T\\rightarrow \\infty} \\mathbb{E}[||\\nabla F(\\mu_T')||^2]= \\lim_{T\\rightarrow \\infty} \\nu_t = ^{\\text{by Cor. 3.9}} 0. $$\nThis mean-square convergence implies $\\lim_{T\\rightarrow\\infty}\\nabla F(\\mu_T')=0\\in\\mathbb{R}^d$ in probability. Hence, $\\mu_T'$ converges to a stationary point of $F(\\cdot)$ in probability, which lie in $\\mathcal{S}_{x^*,\\delta}$ from Cor. 3.9.\n\n# 3. Reasons why $\\mathcal{S}$ does not need to be convex\nThis is because the new objective function $F_N(\\mu,\\sigma)$ is defined and differentiable over $\\mu\\in \\mathbb{R}^d$ (see Theorem 2.1 and Eq.(6) in the paper). So the search space is $\\mathbb{R}^d$ regardless the shape of $\\mathcal{S}$. A potential issue is $\\mu_{\\infty}'\\notin \\mathcal{S}$. But it can be avoided in the case where $x^*$ is an interior point of $\\mathcal{S}$, by increasing $N$ to the a level such that $\\mathcal{S}_{x^*,\\delta}\\subset \\mathcal{S}$. \n\n# 4. Proof to Corollary 3.9\nPart (I) of Cor 3.9 states that all max points of $F_N$ lies in $\\mathcal{S}_{x^*,\\delta}$, and Part (II) gives the iteration complexity bound on $\\nu_t$ (defined above in the correction part). Part (I) is an immediate implication from Lemma 3.4, whose proof is provided in the appendix. So we skip the proof for (I). \n## Proof to Part (II)\nPart (II) is implied from Theorem 3.7. Same as in Lemma 3.4, we write $F_N(\\mu,\\sigma)$ as $F(\\mu)$ for short, where $N$ is fixed and specified at the beginning of Section 3.1.\nLet $\\nu_t$ be defined as above in Point 2. Then,\n$$\\sum_{t=0}^{T-1} \\alpha_t \\sigma^2 \\nu_{T} \\leq  \\sum_{t=0}^{T-1} \\alpha_t  \\sigma^2\\mathbb{E}[\\|\\nabla F(\\mu_t)\\|^2], \\quad \\text{ from (1),}$$\n$$\\leq f(x^*) - F(\\mu_{0}) + L G \\sum_{t=0}^\\infty \\alpha_t^2, \\quad \\text{from Theorem 3.7,}$$\n$$ \\leq f_N(x^*) - F(\\mu_{0}) + 2d^2f_N^3(x^*) \\sum_{t=1}^\\infty t^{-(1+2\\gamma)},\\quad \\text{ from Lemma 3.5 and 3.6}, $$\n$$ \\leq C_0 d^2,\\quad C_0:=f_N(x^*) - F(\\mu_{0}) + 2f_N^3(x^*) \\sum_{t=1}^\\infty t^{-(1+2\\gamma)}.$$\nTherefore, we have\n$$\\sum_{t=0}^{T-1} \\alpha_t \\sigma^2 \\nu_{T}\\leq  C_0 d^2. $$\n\nWhen $\\alpha_t=(t+1)^{-(1/2+\\gamma)}$, dividing both the two sides of the above inequality by $\\sum_{t=0}^{T-1}\\alpha_t\\sigma^2$ gives\n$$ \\nu_T\\leq\\frac{C_0d^2}{\\sigma^2\\sum_{t=1}^{T} t^{-(1/2+\\gamma)}} $$\n$$ <\\frac{C_0d^2}{\\sigma^2\\int_{1}^Tt^{-(1/2+\\gamma)}dt} $$\n$$ =\\frac{C_0d^2}{\\sigma^2(T^{\\frac{1}{2}-\\gamma}-1)/(\\frac{1}{2}-\\gamma)} $$\n$$ <\\frac{C_0d^2}{\\sigma^2(T^{\\frac{1}{2}-\\gamma}/2)/(\\frac{1}{2}-\\gamma)},\\quad\\text{when }T>2^{2/(1-2\\gamma)}, $$\n$$ = C_1 \\frac{d^2}{T^{\\frac{1}{2}-\\gamma}},\\quad \\text{where } C_1:=\\frac{C_0}{\\sigma^2(1/2)/(\\frac{1}{2}-\\gamma)}. $$\n\nIn sum, \n$$ \\nu_T \\leq C_1 \\frac{d^2}{T^{\\frac{1}{2}-\\gamma}},\\quad \\text{ whenever }T>2^{2/(1-2\\gamma)}. \\tag{2}$$\n\nDefine $C_2:=\\max${$1, 2/C_1$}. Given any $\\epsilon\\in(0,1)$, whenever $T> (C_2C_1d^2\\epsilon^{-1})^{2/(1-2\\gamma)}=O((d^2\\epsilon^{-1})^{2/(1-2\\gamma)})$, we have\n$$ T>(C_2C_1d^2\\epsilon^{-1})^{2/(1-2\\gamma)}>(C_1C_2)^{2/(1-2\\gamma)}\\geq 2^{2/(1-2\\gamma)}, $$\nand\n$$ \\nu_T \\leq^{\\text{from }(2)}  C_1 \\frac{d^2}{T^{\\frac{1}{2}-\\gamma}} < C_1 \\frac{d^2}{(C_2C_1d^2\\epsilon^{-1})^{\\frac{2}{1-2\\gamma}(\\frac{1}{2}-\\gamma)}} =\\frac{\\epsilon}{C_2}\\leq \\epsilon.$$\n$\\square$", "claims_and_evidence": "I actually doubt their claim of global convergence, which is supported by Corollary 3.9 in the manuscript. However, the proof of Corollary 3.9 is not provided and there is only a brief discussion before the corollary. I'm quite surprised when seeing this result, because 1) it is, in general, very difficult to find the global optimal solution of non-convex problems; 2) Theorem 3.7 before Corollary 3.9 only gives the convergence of the gradient which is natural, and deriving convergence of the variable to the global optimum from the convergence of gradient is impractical especially when there is no strong conditions imposed.\n\nMoreover, the constraint set $S$ is not even assumed to be convex, which is a bit weird to me.\n\nConcluding all the above, I would like the authors to check whether some conditions are missed.", "methods_and_evaluation_criteria": "Limited novelty, but practical performance is good.", "theoretical_claims": "Checked, but didn't find the proof of the key result in Corollary 3.9.", "experimental_designs_or_analyses": "Yes, seems fine.", "relation_to_broader_scientific_literature": "Not sure.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "The result is strong, and I hope they can clarify it.", "other_comments_or_suggestions": "I would be happy to raise my score if my concerns can be clarified.", "questions_for_authors": "No", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Mgfz96JJfs", "reviewer": "Reviewer_VChF", "summary": "The paper studies graduated optimization (aka homotopy methods), and proposes a fairly simple method based on exponentiating the objective and applying Gaussian smoothing. A convergence analysis is provided, as well as numerical experiments.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "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": "Thank you for your valuable comments! They are very important for us to improve the manuscript. \n# 1. Answers to ``Questions For Authors\" \n## 1.1 Answer to the first question on the curse of dimensionality\nIt seems that the classic curse of dimensionality you mentioned applies to the sample complexity, while the convergence analysis result in our paper (Corollary 3.9) gives an \\textit{iteration complexity} bound. Specifically, the expression  \n$T = O\\left( (d^2 \\varepsilon^{-1})^{2/(1 - 2\\gamma)} \\right)$ \nrepresents the number of iterations required for the expectation $\\mathbb{E}[\\|\\nabla F(\\mu_T)]\\|^2$ to be less than $\\varepsilon$. This does not directly specify the number of function evaluations (queries) needed, which determines the sample complexity. Hence, this result does not bypass the classic curse of dimensionality.\n\n## 1.2 Answer to the second question on the use of Theorem 2.1\nHere, we view $F_N(\\mu,\\sigma)$ as a function of $\\mu$.\n\n1. In Theorem 2.1, within the region ${\\mu\\in\\mathbb{R}^d: \\|\\mu\\|< M}$, the bounds ``$\\frac{\\partial F_{N}(\\mu,\\sigma)}{\\partial \\mu_i}>0$ if $\\mu_i<x_i^*-\\delta$, and $\\frac{\\partial F_{N}(\\mu,\\sigma)}{\\partial \\mu_i}<0$ if $\\mu_i>x_i^*+\\delta$\" imply that $\\frac{\\partial F_{N}(\\mu,\\sigma)}{\\partial \\mu_i}=0$ can only occur in the range of $\\mu_i\\in [x_i^*-\\delta,x^*+\\delta]$. This holds for all $i\\in$ {$1,2,...,d$}. Therefore, all the stationary points of $F_N(\\mu,\\sigma)$ in the region ${\\mu\\in\\mathbb{R}^d: \\|\\mu\\|< M}$ lie in the $\\delta$-neighborhood of $x^*:=\\arg\\max_{x}f(x)$. This neighborhood $\\mathcal{S}_{x^*,\\delta}$ is defined in Eq. (4) in the paper. \n\n2. Theorem 2.1 leads to Lemma 3.4, which states that given any $\\delta>0$, when $N$ is sufficiently large, all the stationary points of $F_N(\\mu,\\sigma)$ in $\\mathbb{R}^d$ lie in $\\mathcal{S}_{x^*,\\delta}$.  \n\n3. Corollary 3.9 states that the sequence ${\\mu_t}$ produced by GSPTO converges to a stationary point, which lies in the $\\delta$-neighborhood $\\mathcal{S}_{x^*,\\delta}$ because of point 2. \n\n\n\n## 1.3 Answer to the third question on constants-blow-up issues\nThank you for pointing this out. We will add the following assumption to the revision, so that the problem dependent constants (e.g., $L$ in Lemma 3.5) and the big-O factors will have an upper bounded independent from $N$.  \n\n**Assumption**: *$f(x)\\leq 1$ for the PGS case and $f(x)\\leq 0$ for the EPGS case.*\n\nUnder this assumption, from Eq. (4), $f_N(x)\\in[0,1]$ for all $N>0$. We briefly explain why it enables the big-O factor in Corollary 3.9 to have an upper bound that is independent from $N$. Specifically, \nthe big-O term is\n$ (C_2C_1d^2\\epsilon^{-1})^{2/(1-2\\gamma)}, $\nwhere $C_2=\\max$ {$1,1/C_1$} and\n$$C_1=(1-2\\gamma)\\sigma^{-2}\\left(f_N(x^*) - F_N(\\mu_{0},\\sigma) + 2f_N^3(x^*) \\sum_{t=1}^\\infty t^{-(1+2\\gamma)}\\right)>0.$$\nThen, \"$f_N\\leq 1$ for all $N$\" implies the second inequality below\n$$C_1C_2\\leq (1+C_1)\\leq  (1-2\\gamma)\\sigma^{-2}(1+\\sum_{t=1}^\\infty t^{-(1+2\\gamma)})=C.$$\n\n**Remarks on the Assumption**. In practice, this assumption can be realized if we know an upper bound of the objective $f(\\cdot)$ in its domain. For example, if we know that $f<B$, then we can define the new objective as $f_1:=f-B$ and proceed EPGS with $f_1$ (note that $f$ and $f_1$ have the same maximum points). \n\nIn practice, at least shown in our experiments, our algorithms work well for objective functions that do not necessarily satisfy this assumption. The main reason is because, in these experiments, a small value of $N$ is sufficient to produce good results (e.g., $N\\leq 0.03$ in Table 3 and 4).\n\n\n# 2. Replies to ``Other Comments Or Suggestions\" \n* Figure 1a and 1b look very similar to each other. But they are different. For example, a difference lies in the intersection between the green curve ($N=5$) and the red curve ($f(\\mu)$).\n* Yes, you are right. We will add the word of $unique$ in front of \"global maximum\" in line 42 (left column), and in front of \"global maximum\" in Theorem 2.1.\n* Thank you for pointing this out. We will change the name to GS-PowerOpt.", "claims_and_evidence": "Essentially the main claim of the paper is that it \"makes sense\" to exponentiate (or raise to a fixed power) a maximization objective since this increases the gap between the maximum and other (sub-optimal) points.\nI find this strategy dubious, although I cannot find any specific mistakes in the manuscript (I did not go over the proofs in the appendix in detail). Exponentiating the objective indeed increases the gap to the optimum of sub-optimal points, but at the same time it increases the Lipschitz constant and smoothness constant by the same factor. Indeed, the big-O factors in the paper hide constants which are exponential in $N$. Thus I'm not really sure how to make sense out of the results.", "methods_and_evaluation_criteria": "Yes, the proposed methods make sense for the problem or application at hand.", "theoretical_claims": "I did not check the correctness of the theoretical claims in the appendix.", "experimental_designs_or_analyses": "I did not check the validity of the experiments.", "relation_to_broader_scientific_literature": "The paper seems to do a good job relating its contributions to prior work on this topic.", "essential_references_not_discussed": "-", "other_strengths_and_weaknesses": "The paper is written fairly well overall and not so difficult to follow.", "other_comments_or_suggestions": "Minor comments:\n\n- Figure 1a and 1b looks identical after the incorporated normalization.\n\n- The analysis seems to only hold when the global maximum is unique, which should be mentioned explicitly.\n\n- The name of the main algorithm GSPTO resembles (at least to me) the term \"Gestapo\". Therefore I kindly suggest the authors to reconsider its naming.", "questions_for_authors": "Maybe this is because I am not very familiar with the graduated optimization literature, but I can't really make sense out of the main results. I'd appreciate the author's responses to the following questions:\n\n- How is it that the classic curse of dimensionality does not apply here? A simple and classic lower bound asserts that for non-convex functions, an exponential (in the dimension) number of queries are needed in order to find a global minimum. What assumption here facilitates this?\n\n- Theorem 2.1, which seems to be the main technical crux of this submissions, is hard for me to digest. The statement proves certain bounds on the partial derivatives with respect to the smoothing center's coordinates mu_i. How should one interpret this result? Why is this useful/helpful later on?\n\n- As I mentioned earlier, if the problem dependent constants blow-up as well, how can it be useful to exponentiate the problem?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes a novel Gaussian smoothing algorithm based on an exponential transformation. The proposed method is sound and theoretically supported, although the assumptions are not ideal. Experimental results show improvements over previous Gaussian smoothing algorithms and performance on par with evolutionary methods (which are not as amenable to theory). Therefore, I would recommend acceptance.
Decision: Accept (poster)