Adaptive Stochastic Natural Gradient Method
for Optimizing Functions with Low Effective
Dimensionality?
Teppei Yamaguchi, Kento Uchida, and Shinichi Shirakawa
Graduate School of Environment and Information Sciences,
Yokohama National University, Yokohama, Japan
yamaguchi-teppei-yc@ynu.jp, uchida-kento-nc@ynu.jp,
shirakawa-shinichi-bg@ynu.ac.jp

Abstract. Black-box optimization algorithms, such as evolutionary algorithms, have been recognized as useful tools for real-world applications.
Several efficient probabilistic model-based evolutionary algorithms, suchas the compact genetic algorithm (cGA) and the covariance matrix adaptation evolution strategy (CMA-ES), can be regarded as a stochastic
natural gradient ascent on statistical manifolds. Our baseline algorithm
is the adaptive stochastic natural gradient (ASNG) method which automatically adapts the learning rate based on the signal-to-noise ratio(SNR) of the approximated natural gradient. ASNG has shown effectiveness in a practical application, but the convergence speed of ASNG deteriorates on objective functions with low effective dimensionality (LED),
where LED means that part of the design variables is ineffective or does
not affect the objective value significantly. In this paper, we propose anelement-wise adjustment method for the approximated natural gradient
based on the element-wise SNR and introduce the proposed adjustment
method into ASNG. The proposed method suppresses the natural gradient elements with the low SNRs, helping to accelerate the learning
rate adaptation in ASNG. We incorporate the proposed method into thecGA and demonstrate the effectiveness of the proposed method on thebenchmark functions of binary optimization.
Keywords: probabilistic model-based black-box optimization · natural
gradient · low effective dimensionality · learning rate adaptation.

1

Introduction

A lot of problems in real-world applications, such as the simulation-based optimization in engineering and the hyperparameter optimization in machine learning, are formulated as black-box optimization problems, that is, the gradient of?

This is an author version of the paper accepted to the 16th International Conference
on Parallel Problem Solving from Nature (PPSN XVI). The final authenticatedversion is available online at https://doi.org/10.1007/978-3-030-58112-1_50.

2

T. Yamaguchi et al.

the objective function cannot be accessed. The population-based black-box optimization methods, including evolutionary algorithms, have succeeded in a wide
range of applications. In general, the performance of evolutionary algorithms
depends on the choice of the hyperparameter, for example, the population sizeand learning rate. Tuning such hyperparameters in real-world applications is
not realistic because the number of function evaluations is usually limited, andthe computational cost for function evaluations is expensive. Therefore, a robust
parameter adaptation mechanism is required in practical situations.
Probabilistic model-based evolutionary algorithms [3,5,6] are promising blackbox optimization methods that define a parametric probability distribution on
the search space and iteratively update the parameters of the distribution to
improve the objective function value of the samples generated from the distribution. Several efficient probabilistic model-based evolutionary algorithms, suchas the compact genetic algorithm (cGA) [6] or the covariance matrix adaptation
evolution strategy (CMA-ES) [5], can be regarded as a stochastic natural gradient ascent on statistical manifolds [9]. In this paper, we focus on the adaptive
stochastic natural gradient (ASNG) method [1] that adapts the learning ratein the stochastic natural gradient methods such as the cGA. In the black-box
optimization, the natural gradient has to be estimated by the Monte Carlo approximation. ASNG measures the reliability of the estimated natural gradientdirection by means of the signal-to-noise ratio (SNR) and tries to keep the SNR
around a constant value by controlling the learning rate. The literature [1] showsthat ASNG can achieve an efficient and robust optimization in the problem of aone-shot neural architecture search for deep learning. However, the convergence
speed of ASNG becomes slow on objective functions with low effective dimensionality (LED), in which part of the variables is ineffective or does not affectthe objective value significantly. Particularly, when redundant variables exist,
the learning rate becomes smaller than necessary because of the low SNR due
to the random walk in the redundant dimensions.
Because LED often appears in high-dimensional problems, including realworld applications [4,7,8], several works tackling LED exist. REMBO [11] projects
a high dimensional search space into a low dimensional subspace using a random
embedding to solve efficiently high-dimensional problems with LED by Bayesian
optimization. REMEDA [10] applies the same idea to the estimation of distribution algorithm. However, the random projection does not reflect the landscapeinformation, and the number of subspace dimensions still remains as a hyperparameter, which should be carefully chosen depending on the target problems.
In this paper, we propose a method for improving ASNG for objective functions with LED. When optimizing the objective functions with LED by ASNG,
the reliabilities of the elements of the estimated natural gradient differ. Precisely,
the SNR of the estimated natural gradient corresponding to the nonsensitive dimensions becomes small. Our idea is to adjust the update direction of the distribution parameters by exploiting the element-wise SNR of the natural gradient.
The proposed method can be regarded as using the element-wise learning ratein ASNG, that is, the larger learning rate is adopted for the large SNR elements.

ASNG Method for Optimizing Functions with LED

3

We incorporate the proposed method into ASNG without breaking its theoretical principal. The experimental results demonstrate that the proposed method,termed ASNG-LED, works efficiently on binary objective functions with LED.

2

Preliminaries

2.1

Stochastic Natural Gradient for Black-Box Optimization

We consider a black-box objective function f : X → R to be maximized on anarbitrary search space X . To realize the black-box optimization, we introduce
the technique called stochastic relaxation to transform the original problem intoa differentiable objective function. Note that the following transformation is thesame as the one considered in the information geometric optimization (IGO)
framework [9] and natural evolution strategies [12].
Let us consider a parametric family of probability distributions P = {Pθ :θ ∈ Θ ⊆ RDθ } on X . The transformed objective function is the expectation off under Pθ , that is,Z
J(θ) :=
f (x)pθ (x)dx = EPθ [f (x)] ,(1)
x∈X

where pθ is the density function of Pθ with respect to (w.r.t.) the reference
measure dx on X . For any x, we assume that the log-likelihood ln pθ (x) is differentiable w.r.t. θ, and there exists a sequence of the distributions approaching the
Dirac Delta distribution δx around x. Then, the maximization of J has the same
meaning as the original problem in the sense that supθ∈Θ J(θ) = Eδx∗ [f (x)] =f (x∗ ) = supx∈X f (x), where x∗ is the global optimal solution.
In this paper, we focus on the special case, as also assumed in [1], that P isrepresented by an exponential family of probability distributions whose density
function is given as pθ (x) = h(x) exp(η(θ)T T (x) − A(θ)), where η : Θ → RDθ isthe normal (canonical) parameter, T : X → RDθ is the sufficient statistics, andA(θ) is the normalization factor. To make it simple, we assume h(x) = 1, andthe parameter of the distribution is represented by θ = Epθ [T (x)], which is called
the expectation parameter. Then, the natural gradient of the log-likelihood is
˜ ln pθ (x) = T (x) − θ, and the inverse of the Fisher information matrix
given by ∇is F(θ)−1 = Epθ [(T (x) − θ)(T (x) − θ)T ]. We note that several known familiesof probability distributions, such as the Gaussian distribution and the Bernoulli
distribution, are included in the exponential family and can be represented by
the expectation parameter.
To maximize J, we consider the update of θ in the metric of the KullbackLeibler (KL) divergence. Then, the steepest direction is given by the natural gradient direction [2] w.r.t. the Fisher metric defined by F(θ). Because the natural
gradient cannot be obtained analytically in the black-box optimization scenario,
we approximate it by Monte Carlo with independent and identically distributed(t)(t)(i.i.d.) samples x1 · · · xN from Pθ(t) . Moreover, we apply the utility transforma(t)(t)
tion u(xi ) based on the ranking of xi w.r.t. f -value. As a result, the estimated4

T. Yamaguchi et al.

natural gradient is obtained as
N

G(θ(t) ) =

1 X
(t)
(t)
u(xi )(T (xi ) − θ(t) ) .
N i=1

(2)

Introducing the learning rate θ > 0, the update rule of θ(t) reads
θ(t+1) = θ(t) + θ G(θ(t) ) .
2.2

(3)

Adaptive Stochastic Natural Gradient (ASNG)

Akimoto et al. [1] developed the adaptive stochastic natural gradient (ASNG)
method by introducing a learning rate adaptation mechanism into the stochastic
natural gradient method using an exponential family of probability distributions
with the expectation parameters. Although the joint optimization of the differentiable and non-differentiable variables is considered in [1], ASNG can apply toa naive black-box optimization without any modification. Here, we explain theoutline of ASNG in the black-box optimization scenario.
In ASNG, the learning rate is represented byθ = δθ /kG(θ(t) )kF(θ(t) )(4)

The update rule (3) with the learning rate in (4) is similar to the trust region
method under the KL divergence with the trust region radius δθ . The adaptation of δθ in ASNG is based on the theoretical insight of the stochastic natural
gradient method. According to [1, Theorem 4], the monotonic improvement of
J is ensured when it holds
(t)
(t)
˜
˜
DKL (θ(t+1) , θ(t) + θ ∇J(θ)) ≤ ζDKL (θ(t) + θ ∇J(θ), θ(t) )(5)

for some ζ > 0 and if θ < (ζf (x∗ ) + J(θ))−1 with some other mild assumptions,where DKL (θ, θ0 ) is the KL divergence between Pθ and Pθ0 . ASNG relaxes thecondition for monotonic improvement to the improvement over τ ∝ δθ−1 iterations. If θ is small enough, it allows the approximation where θ(t) ≈ θ(t+k) andG(θ(t+k) ) is i.i.d. for k = 0, · · · , τ −1. Then, approximation of the KL divergencewith the Fisher metric allows the transformation of the condition in (5) as
τ
−1
X
k=0

θ G(θ(t+k) ) − θ E[G(θ(t) )]√τ2F(θ (t) )≤ ζτ 2θ kE[G(θ(t) )]k2F(θ(t) ) .

(6)Then, the limitation of τ → ∞ in the LHS leadskE[G(θ(t) )]k2F(θ(t) )Tr(Cov[G(θ(t) )]F(θ(t) ))≥1∈ Ω(δθ ) .
ζτ(7)

The LHS in (7) is the SNR of the estimated natural gradient measured w.r.t
Fisher metric. The above discussion indicates that the SNR should be greaterthan a constant value proportional to δθ .

ASNG Method for Optimizing Functions with LED

5

To estimate the lower bound of the SNR, the following accumulations were
proposed in [1]:p1(8)s(t+1) = (1 − β)s(t) + β(2 − β)F(θ(t) ) 2 G(θ(t) )γ (t+1) = (1 − β)2 γ (t) + β(2 − β)kG(θ(t) )k2F(θ(t) ) ,(9)where s(0) = 0 and γ (0) = 0. Finally, introducing hyperparameters α > 1 andβ ∝ δθ , the adaptation of δθ is written as  (t+1) 2kskδθ ← δθ exp β− γ (t+1).
(10)αThis adaptation tries to maintain ks(t+1) k2 /γ (t+1) around α, which makes thelower bound of the SNR proportional to δθ . Note that the condition in (7) issatisfied under this design principle.

3

ASNG for Low Effective Dimensionality

ASNG increases the learning rate when the estimated SNR becomes large anddecreases it when the SNR becomes small. We can intuitively regard the SNR
as a measurement of the reliability of the natural gradient direction. If there
are low-effective or redundant variables in the objective function, the varianceof the natural gradient elements corresponding to such variables becomes large,
resulting in the estimated SNR of G(θ(t) ) and the learning rate becoming smaller
than necessary. Therefore, the performance of ASNG deteriorates on objectivefunctions with LED. To prevent this, we propose a natural gradient adjustment
method for ASNG by using the element-wise SNR.
3.1

Estimation of Element-wise SNR(t)

Let us denote i-th element of G(θ(t) ) as Gi for short. By using a one-hot vector
h(i) whose i-th element is one and other elements are zero, we define the SNR
(t)

of Gi

on the Fisher metric as follows:kE[h(i) ◦ G(θ(t) )]k2F(θ(t) )Tr(Cov[h(i) ◦ G(θ(t) )]F(θ(t) ))(t)=(E[Gi ])2(t)

Var[Gi ].

(11)

To estimate the element-wise SNR, we accumulate ŝ(t) and γ̂ (t) similar to (8)and (9) asqŝ(t+1) = (1 − β̂)ŝ(t) + β̂(2 − β̂)G(θ(t) )(12)γ̂ (t+1) = (1 − β̂)2 γ̂ (t) + β̂(2 − β̂)G(θ(t) ) ◦ G(θ(t) ) ,(13)

where β̂ ∈ (0, 1) is a smoothing factor and ◦ means the element-wise product.
When the learning rate θ is small enough, we can consider θ(t+k) stays around6

T. Yamaguchi et al.

the θ(t) for τ ∝ −1θ updates after t iterations. Therefore, the expectations of i-th
elements of ŝ(t+1) and γ̂ (t+1) are approximated under mild condition as
s
!q
τ
−1
X
2 − β̂
τ
→∞
(t)
(t)
(t+1)
β̂(2 − β̂)E[Gi ] −→E[Gi ] ,
(14)
E[ŝi
]≈
(1 − β̂)k
β̂
k=0
!
τ
−1
X
τ →∞
(t+1)
(t)
(t)
2k
E[γ̂i
]≈
(1 − β̂)
β̂(2 − β̂)E[(Gi )2 ] −→ E[(Gi )2 ] .
(15)
k=0

(t+1)

Moreover, the variance of ŝi(t+1)

Var[ŝi

]≈

τ
−1
X
k=0

is approximated under mild condition as!
(t) τ →∞

(1 − β̂)2k(t)

β̂(2 − β̂)Var[Gi ] −→ Var[Gi ] .

(16)

Therefore, the SNR of the i-th element of G(θ(t) ) can be approximated as(t+1) 2(t)

(E[Gi ])2(t)

Var[Gi ](t+1)

where ξi
3.2

≈

(t+1)

) ]/E[γ̂iE[(ŝi(t+1) 22β̂ −1 − 1 − E[(ŝi(t+1) 2:= (ŝi(t+1)) /γ̂i

(t+1)

]−1

(t+1)

) ]/E[γ̂i

]

≈

ξi

(t+1)

2β̂ −1 − 2 − ξi

(17)

− 1.

Natural Gradient Adjustment Using the Element-wise SNR

The small value of the element-wise SNR estimated by (17) indicates that thecorresponding natural gradient element is unreliable and has a large variance. We
control the element-wise strength of G(θ(t) ) using the element-wise estimationof the SNR; that is, we suppresses the strength of the natural gradient elementswith the low SNRs. Because the denominator in (17) can be approximated by
2β̂ −1 when β̂ is significantly small, the estimation of the SNR is approximately(t)proportional to ξi . Therefore, we employ a Dθ -dimensional adjustment vector(t)
σ (t) using ξi and define σ (t) by the following sigmoid function as
(t)

σi

=

1


(t)

1 + exp −ωξi

 ,

(18)

where ω (> 0) is the gain parameter. Then, we adjust the natural gradientdirection byH(θ(t) ) = σ (t) ◦ G(θ(t) ) .

(19)

When we set ω = ∞, the sigmoid function coincides with the step function, andthe natural gradient update with H(θ(t) ) behaves as a dimensionality reduction
method. We use the adjusted natural gradient H(θ(t) ) in the proposed method
instead of G(θ(t) ), that is, the natural gradient G(θ(t) ) in (3) and (4) is replacedby H(θ(t) ).

ASNG Method for Optimizing Functions with LED

3.3

7

Combination with ASNG

Let us assume F(θ(t) ) is given by a diagonal matrix; for example, the Bernoulli
distribution satisfies this assumption. In such a case, we show the proposed
method can be combined with ASNG without breaking the theoretical principle
described in Section 2.2.
From the condition of monotonic improvement in (5), the search efficiencyof the proposed method with ASNG is guaranteed in a similar way with thatof ASNG. Let us assume β̂ and θ are sufficiently small so that we can consider
σ (t) and θ(t) stay at the same point for τ ∝ δθ−1 iterations. Then, we consider
the relaxation of (5) in the same way as described in Section 2.2, which is given
by
τ
−1
X
k=0

θ H(θ(t+k) ) − θ E[G(θ(t) )]√τ2F(θ (t) )≤ ζτ 2θ kE[G(θ(t) )]k2F(θ(t) ) .

(20)

When taking the limit of τ as τ goes to infinity, the LHS in (20) can be transformed and bounded from upper as


!
Dθ
(t) 2
X
1
−
σ
i
2θ
Fii (θ(t) ) Var[Hi (θ(t) )] +E[Hi (θ(t) )]2 
(21)
(t)
σ
i=1
i
≤ 2θ Tr(Cov[H(θ(t) )]F(θ(t) )) + 2θ kE[H(θ(t) )]k2F(θ(t) ) K (t) ,where K (t) =

(22)

(t)
(t) 2
(t)
i=1 ((1 − σi )/σi ) . Moreover, because σi ≤ 1, we getPDθkE[θ H(θ(t) )]k2F(θ(t) ) ≤ kE[θ G(θ(t) )]k2F(θ(t) ) .

(23)

As a result, we get the sufficient condition of (20) under the limitation of τ askE[H(θ(t) )]k2F(θ(t) )Tr(Cov[H(θ(t) )]F(θ(t) ))≥11∈ Ω(δθ ) ,≥ζτζτ − K (t)(24)

where we assume τ satisfies τ > K (t) /ζ. We note K (t) can be transformed as
K

(t)

=

Dθ
X

(t)

1 − σi
(t)

i=1

σi

!2
=

Dθ
X
i=1

(t)

exp −2ω(ŝi )2
(t)

γ̂i
(t)

!!
−1
(t)

.

(25)

Here, we consider the case that the accumulation of ŝi and γ̂i works ideally.
(t)(t)
Then, replacing (ŝi )2 and γ̂i with their expectations given by (14), (15) and(t)(16) approximates K as!
Dθ(t−1) 2X
4ω(1 − β̂)
(E[Gi
])
(t)
K ≈
exp −
≤ Dθ .
(26)(t−1) 2
(t−1)
β̂
(E[Gi
]) + Var[Gi
]
i=1

8

T. Yamaguchi et al.

Algorithm 1: ASNG-LED
Require: θ(0) {initial distribution parameter}
Require: α = 1.5, δθinit = 1, N = 2, β̂ = Dθ−1
1: t = 0, ∆ = 1, γ = 0, s = 0, γ̂i = 0, ŝi = 0
2: repeat
1/2
3:
set δθ = δθinit /∆ and β = δθ /Dθt(t)
4:compute Gθ (θ ) and σ using (2) and (18)5:
set H(θ(t) ) = σ (t) ◦ G(θ(t) )6:for i = 1 to Dθ do(t)
7:
if Gi 6= 0 then q8:ŝi ← (1 − β̂)ŝi +

(t)

(t)

β̂(2 − β̂)Gi /|Gi |9:γ̂i ← (1 − β̂)2 γ̂i + β̂(2 − β̂)
10:
end if
11:
end for
12:
compute θ and θ(t+1) by (4) and (3) replacing G(θ(t) ) with H(θ(t) )p113:s ← (1 − β)s + β(2 − β)F(θ(t) ) 2 H(θ(t) )/kH(θ(t) )kF(θ(t) )214:γ ← (1 − β) γ + β(2 − β)15:∆ ← ∆ exp(β(γ − ksk2 /α))
16:
t←t+1
17: until termination conditions are met

Thus, we can expect that K (t) becomes not so large and (24) is established when
considering τ > Dθ /ζ. Moreover, we can expect that K (t) becomes small whenβ̂ is set as the small value.
Motivated from the above discussion, we modify the accumulation rule in (8)and (9) by replacing G(θ(t) ) with H(θ(t) ). Namely, the learning rate adaptation
tries to make the lower bound of the SNR of H(θ(t) ) proportional to δθ .

3.4

Implementation of ASNG-LED
1

Referring to [1], we replace F(θ(t) ) 2 H(θ(t) ) and kH(θ(t) )k2F(θ(t) ) in the accumu1

lations of s(t+1) and γ (t+1) with F(θ(t) ) 2 H(θ(t) )/kH(θ(t) )kF(θ(t) ) and 1 for the
(t+1)

(t+1)

(t)

(t)

stable updates. In the same manner, ŝiand γ̂i
accumulate Gi /|Gi |
(t)
(t)
(t+1)
(t+1)
and 1 instead of Gi and |Gi |2 . Because of this modification, ŝiand γ̂i(t)
are not updated when Gi = 0. We set the sample size N as two and apply the(t)ranking-based utility transformation introduced in [1], where u(x1 ) = 1 and
(t)
(t)
(t)
(t)
(t)
u(x2 ) = −1 when f (x1 ) > f (x2 ) (and vice versa), and u(x1 ) = u(x2 ) = 0(t)(t)
when f (x1 ) = f (x2 ). This utility transformation can be generalized for an ar(t)(t)
bitrary sample size as follows: u(xi ) = 1 for best dN/4e samples, u(xi ) = −1(t)for worst dN/4e samples and u(xi ) = 0 otherwise. The proposed method implemented with ASNG, termed ASNG-LED, is summarized in Algorithm 1.

ASNG Method for Optimizing Functions with LED

9Table 1. The benchmark functions used in the experiment. They are D-dimensional
functions of which only d dimensions affect the function value.
Name
Definition

LeadingOnes
Pd Qi
j=1 xji=1

4

Experiment

4.1

Experimental Setting

OneMaxPd
i=1 xi

BinVal
Pd
i−1
xi
i=1 2

We evaluate ASNG-LED on several benchmark functions on D-dimensional binary domain. To simply demonstrate that ASNG-LED works well on functions
with LED, we construct the benchmark functions with LED by injecting theredundant variables that do not affect the function value at all. The modified
benchmark functions listed in Table 1 have d (≤ D) effective dimensions andD − d redundant (ineffective) dimensions. The optimal solutions on these functions are given by vectors whose first d elements are given by 1. These functions
become the same as the widely used binary benchmark functions when D = d.
In LeadingOnes, the effective variables change during the optimization. All thevariables of the OneMax function with D = d have an equal contribution to theobjective value, whereas the effects of the variables in BinVal significantly differ
in each dimension. When D > d, these functions have redundant dimensions,and we particularly expect that ASNG-LED works well in such a situation.
In ASNG-LED, we set the strategy parameters as α = 1.5, β̂ = Dθ−1 , andN = 2. The gain parameter in (18) is set to ω = 1. In our preliminary experiment,
we observed that the impact of the setting of ω is not so significant if it is set toaround one. We use the multivariate Q
Bernoulli distribution, whose probabilityDθ xi
mass function is defined as pθ (x) = i=1
θi (1 − θi )1−xi , where Dθ = D, toapply ASNG to binary optimization problems. The natural gradient of the log˜ ln pθ (x) = x − θlikelihood and the Fisher information matrix are given by ∇and a diagonal matrix with diagonal elements equal to Fii (θ) = θi−1 (1 − θi )−1 ,respectively. We compare the proposed method to ASNG and the cGA. We use
the default parameter setting proposed in [1] and set a sample size of two. ThecGA can be regarded as a stochastic natural gradient with a sample size N = 2,
which is derived by applying the family of Bernoulli distributions to the IGO
framework. In other words, the cGA is an algorithm without the learning rate
adaptation in ASNG. In our experiments, the learning rate of the cGA is fixedas θ = D−1 . Moreover, we incorporate the margin of D−1 into all methods
as done in [1], i.e., the range of θi is restricted to [D−1 , 1 − D−1 ], to leave theprobability of generating arbitrary binary vectors. We ran 50 independent trials
for each method, where all algorithm settings succeeded in finding an optimal
solution in all trials.

00

Optimization time / #EÆective dimensions

cGA

10

106

105

T. Yamaguchi et al. cGA

ASNG

cGA

ASNG

LeadingOnes(D = 1000)
4
10
D = 1000

D=d

1

OneMax (D = 1000)
D = 1000

D=dBinVal (D = 1000)
D=d

106

106

106

104

105

106

ASNG-LED

106
106

5

10
150

200

250

D = 1000
106

300

105

4
350

400

450

100

150

200

250

300

350

400

1
150

104

103

103

450
100
200 300500
400 500

105

105

105100

500

103

105

106

104

104

10
100

ASNG + Proposed

ASNG-LED
102

103

ASNG

100
200300 400
250500100 200 300
400 500150 100 200300
350 400 500
400
100 200 300#EÆective dimensions
103

104

200

250

105

300

350

400

450

500

#EÆective dimesnions

104

100450200 300500
400 500

10

100 200 300100
400 500150

200

250

100

150

300

350

400

450

4

3

250

300

350

400

10 of the optimization time (the number of function evaluations) on
104
Fig. 1. Comparison
100 200 300 400 500
100 200 300 400 500
100 200 300 400 500
the benchmark functions with redundant dimensions (D = 1000) and without redundant dimensions (D = d). The median values and inter-quartile ranges over 50 trials
450
500
100
150
200
250
300
350
400
450
500
are displayed.

#EÆective dimesnions

4.2

Experimental Result and Discussion

Optimization time: We compare the search efficiency of ASNG-LED andbaseline algorithms on the functions with and without redundant dimensions.
We vary the number of effective dimensions as d = 100, 200, 300, 400, and 500,
while the numbers of dimensions are set as D = d and D = 1000 for each benchmark function. We call the former the benchmark functions without redundantdimensions and the latter the benchmark functions with redundant dimensions.
Figure 1 shows the relation between the number of effective dimensions andthe optimization time, which is the number of iterations needed to find one ofthe optimal solutions. We observe that ASNG-LED can reduce the optimization
time on the functions with redundant dimensions compared with ASNG. Also,
the optimization time of ASNG-LED does not increase significantly on the functions with redundant dimensions compared with on the ones without redundantdimensions. The performance improvement against ASNG is highlighted in thecase of the functions with redundant dimensions. We believe the reason is that
ASNG-LED suppressed the strength of the estimated natural gradient corresponding to the redundant dimensions, allowing the adaptation mechanism forthe learning rate to work effectively.
Focusing on LeadingOnes and BinVal, ASNG-LED outperforms ASNG on
functions both with and without redundant dimensions. This is because part ofthe dimensions on these functions does not contribute to the function value significantly or at all during the optimization. More precisely, in LeadingOnes, anyelement following the first 0 in a binary string does not affect the function value
at all. On BinVal, the weights for each bit are greatly different, and the lower
parts of dimensions do not change the function value significantly. Because ofsuch properties, ASNG-LED successfully adjusts the natural gradient estimates

200

250

300

ASNG Method for Optimizing Functions with LED

11

and reduces the undesirable effect of the nonsensitive dimensions for the learning
rate adaptation.
For the results of OneMax without redundant dimensions, we observe that
ASNG-LED requires more optimization time than ASNG. OneMax is a linear
function that has the same weight for each dimension. Therefore, adjusting theelement-wise strength of the update direction does not provide a positive effecton the learning rate adaptation on OneMax. We note, however, the optimization
time on OneMax is greatly shorter than the one on LeadingOnes and BinVal.
Meanwhile, ASNG-LED performs better on OneMax when there is a large number of redundant dimensions. This is because the increased number of redundantdimensions makes the SNR value smaller in the original ASNG, and the performance of ASNG is degraded. In contrast, the accumulated value ksk2 for learning
rate adaptation in the proposed method does not become so small because of
the modification of the accumulation rule.
We note that the performances of the cGA differ between the functions withand without redundant dimensions. This performance difference is caused by
the different learning rate and margin settings of the distribution parametersdescribed in Section 4.1.

Optimization process on functions with and without redundant dimensions: We apply each algorithm to both D = 1000 dimensional benchmark
functions without redundant dimensions (d = D) and ones with d = 500 effective dimensions. Figure 2 shows the transitions of the normalized optimality
gap φ(t), which is defined as φ(t) := 1 − fbest (t)/fopt , where fopt and fbest (t)are the function values for an optimal solution and for the best so far solution
at t-th iteration, respectively. From Figure 2, we can observe that ASNG-LED
converges faster than ASNG except for OneMax without redundant dimensions(D = d = 1000). This implies that the adaptation mechanism of the proposed
method works more efficiently than that of ASNG on the functions with redundant or insignificant dimensions.
To demonstrate how the modification in the proposed method accelerates thelearning rate adaptation, we show the transitions of the trust-region radius δθ onboth OneMax without and with redundant dimensions in Figure 3. We observethat the transitions of the trust-region radius δθ of ASNG and ASNG-LED arealmost the same in OneMax without redundant dimensions, while δθ of ASNGLED is larger than δθ of ASNG in OneMax with redundant dimensions. Because
the exact natural gradient elements corresponding to the redundant dimensions
are zero, the estimates of such elements behave like a random walk. Therefore,ksk2 becomes small against γ if the redundant dimensions exist, resulting in an
unnecessarily small learning rate in ASNG. On the other hand, ASNG-LED tries
to suppress the influence of redundant dimensions on the SNR value to avoid
unnecessarily small learning rate on the adaptation mechanism.

00

12

cGA

The normalized optimality gap
250

300

T. Yamaguchi et al.

LeadingOnes (D = 1000, d = 1000)

ASNG

ASNG + Proposed

OneMax (D = 1000, d = 500)

BinVal (D = 1000, d = 500)

100
10°21

cGA

100
10°1

Normalized optimality gap

10°1

10°3
0.0

0.2

0.4

0.6
°3

0.8

1.0

10= 1000, d =10 500)
LeadingOnes (D
100

10°1

10

104
°3

0.0

0.00.5

10°3
1.2
£107

0.2

0

10
1.0
0.4

£107

350

400

0.4

450

0.6

500

10°116

2000

3000

4000

5000

0 0.8

20000
40000
60000
1.0
1.2

6000
°3

OneMax (D = 1000, d = 10500)80000010°2438000

0010000 20000

2
40000

0.0

10°2
1.0

10°1

50000

70000

£106

80000

10

10°2

£106

0

105

cGA
ASNG
ASNG + Propos

4

BinVal (D = 1000, d = 500)

4
60000

1

2

3

10°6
10°25

10°63

10°56

10°44

10°82

10°63

°101

10

10°90

°2

10°82

10°12010°124

104

°139

10

10°10110°120

0.5

1.2

0.0

1.0

1.5
0
£106

1.4
£106

0.2
100

0.4

1500.60 10000

20000
20000

40000

30000

#Iterations
0.8
1.2
1.4
200 1.0 250
300
£106

40000

3500

#EÆective dimesnions

50000

0

10000
400

2

450

20000

4

6

0

500

30000

8
£106

20000040000

40000050000#Iterations

Fig. 2. Transitions of the optimality gap on the benchmark functions without redundant dimensions (D = d = 1000) and with redundant dimensions (d = 500). The
median values and inter-quartile ranges over 50 trials are displayed.

5

310°280

10°44

10°1

0.8

2

BinVal (D = 1000, d = 500)

OneMax (D = 1000, d = 500)

°1

103

30000
10°6

1

10°25

10°22
10°1

10°20610°28010°2507000

10°16910°243°183

10°95
10°13210°206

10°1

10°2

0.2

1000

106

10°169£107

10LeadingOnes(D = 1000, d = 500)

100

10°2

0.0

0.6

0

10

10°2

°3

10°58

10

10

°2

10°21

10°95

10°49

10°1
10°2

10°2

10°2

10°58

BinVal °132
(D = 1000, d = 1000)

10

10°1
10°2

10°2

ASNG-LED

OneMax (D = 1000, d = 1000)°1

LeadingOnes (D = 1000, d = 1000)

100

ASNG

10°1

Conclusion

We have proposed a method to improve the performance of ASNG on objectivefunctions with LED. The proposed ASNG-LED adjusts the estimated natural
gradient based on the elemental-wise SNR estimation. We confirmed the proposed adjustment can be combined with ASNG without breaking the theoreticalaspect. We implemented ASNG-LED by applying the Bernoulli distribution andevaluated the performance on several benchmark functions on binary domain.
The experimental results showed that ASNG-LED could accelerate the learning
rate adaptation in ASNG and outperform the original ASNG on the functions
with LED. In future work, ASNG-LED with the Gaussian distribution for continuous optimization should be implemented and evaluated. Also, the effectivenessof ASNG-LED should be verified on more realistic problems such as hyperparameter optimization and feature selection. The limitation of ASNG-LED is that it
assumes the irrelevant directions are aligned with the axes, i.e., the performanceof ASNG-LED will degrade by the rotation of the coordinate system. Making
ASNG-LED rotational invariant is another important future work.

Acknowledgments. This work is partially supported by the SECOM Scienceand Technology Foundation and JSPS KAKENHI Grant Number JP20H04240.

°139
60000010100800000

0

150

200

200000250

400000OneMax (D = 1000, d = 1000)

0.30

ASNG

OneMax (D = 1000,ASNG
d =+500)
Proposed

0.30

0.25

ASNG
ASNG + Proposed

0.20
0.25
±µ

ASNG Method for Optimizing Functions with LED
OneMax (D = 1000, d = 1000)

0.15
0.30
0.25

±µ

0.30

ASNG
ASNG-LED

0.20

0.20

0.15

0.15

0.10
0.05

0.10

0.05

0.10

OneMax (D = 1000, d = 500)

0.25

0.10
0.20

0.15

13

0.05
0 0

5000

10000
5000 15000

20000
10000

0 15000
2000

4000

6000
8000
20000

10000

12000
25000

#Iterations

Fig. 3. Transition of the trust-region radius δθ in OneMax with and without redundantdimensions in 0.05
ASNG and ASNG-LED. The median values and inter-quartile ranges
over 50 trials are displayed.
0

References

2000

4000

6000
8000
#Iterations

10000

12000

1. Akimoto, Y., Shirakawa, S., Yoshinari, N., Uchida, K., Saito, S., Nishida, K.: Adaptive stochastic natural gradient method for one-shot neural architecture search. In:
Proceedings of the 36th International Conference on Machine Learning (ICML).
pp. 171–180 (2019)
2. Amari, S.: Natural gradient works efficiently in learning. Neural Computation 10,
251–276 (1998)
3. Baluja, S., Caruana, R.: Removing the genetics from the standard genetic algorithm. In: Proceedings of the 12th International Conference on Machine Learning(ICML). pp. 38–46 (1995)
4. Bergstra, J., Bengio, Y.: Random search for hyper-parameter optimization. Journalof Machine Learning Research 13, 281–305 (2012)
5. Hansen, N., Müller, S.D., Koumoutsakos, P.: Reducing the time complexity of thederandomized evolution strategy with covariance matrix adaptation (CMA-ES).
Evolutionary Computation 11(1), 1–18 (2003)
6. Harik, G.R., Lobo, F.G., Goldberg, D.E.: The compact genetic algorithm. IEEE
Transactions on Evolutionary Computation 3, 287–297 (1999)
7. Hutter, F., Hoos, H., , Leyton-Brown, K.: An efficient approach for assessing hyperparameter importance. In: Proceedings of the 31st International Conference on
Machine Learning (ICML). pp. 754–762 (2014)
8. Lukaczyk, T., Constantine, P., Palacios, F., Alonso, J.: Active subspaces for shape
optimization. In: Proceedings of the 10th AIAA Multidisciplinary Design Optimization Conference. pp. 1–18 (2014)
9. Ollivier, Y., Arnold, L., Auger, A., Hansen, N.: Information-geometric optimization algorithms: A unifying picture via invariance principles. Journal of Machine
Learning Research 18, 1–65 (2017)10. Sanyang, M.L., Kabán, A.: REMEDA: Random embedding EDA for optimising
functions with intrinsic dimension. In: Proceedings of the 14th International Conference on Parallel Problem Solving from Nature. pp. 859–868 (2016)
11. Wang, Z., Hutter, F., Zoghi, M., Matheson, D., de Freitas, N.: Bayesian optimization in a billion dimensions via random embeddings. Journal of Artificial Intelligence Research 55, 361–387 (2016)

14

T. Yamaguchi et al.

12. Wierstra, D., Schaul, T., Glasmachers, T., Sun, Y., Peters, J., Schmidhuber, J.:
Natural evolution strategies. Journal of Machine Learning Research 15, 949–980(2014)