Lagrangian is singular, we can only ensure that the Lagrangian vector field is
a semispray of type $k$. It is therefore necessary, in general, to require the
condition of semispray of type $1$ as an additional condition.

Then, for regular Lagrangian systems, when the tangency condition of the
vector field $X\in{\mathfrak{X}}({\cal W})$ solution in the unified formalism
along the submanifold ${\cal W}_{o}$ is required, we obtain not only the
Euler-Lagrange equations for the vector field, but also the remaining $k-1$
systems of equations that the vector field must satisfy to be a semispray of
type $1$.

As we point out in the introduction, a previous and quick presentation of a
unified formalism for higher-order systems was outlined in [13]. Our formalism
differs from this one, since in that article the authors take ${\rm
T}^{k}Q\oplus_{{\rm T}^{k-1}Q}{\rm T}^{*}({\rm T}^{k-1}Q)$ as the phase space
in the unified formalism, instead of ours, which is ${\rm
T}^{2k-1}Q\oplus_{{\rm T}^{k-1}Q}{\rm T}^{*}({\rm T}^{k-1}Q)$. This is a
significant difference, since when we want to recover the dynamical solutions
of the Lagrangian formalism from the unified formalism, the Lagrangian phase
space is ${\rm T}^{2k-1}Q$, instead of ${\rm T}^{k}Q$, which is the bundle
where the Lagrangian function is defined. This fact makes it more natural to
obtain the Lagrangian dynamics as well as the Hamiltonian dynamics, which in
turn is obtained from the Lagrangian one using the Legendre-Ostrogradsky map.

By using any suitable generalization of some of the several formalisms for
first-order non-autonomous dynamical systems [1, 6, 19], a future avenue of
research consists in generalizing this unified formalism for higher-order non-
autonomous dynamical systems. This generalization should also be recovered as
a particular case of the corresponding unified formalism for higher-order
classical field theories. As regards this topic, a proposal for a unified
formalism for higher-order classical field theories has recently been made
[10, 41], which is based on the model presented in [13]. This formulation
allows us to improve some previous models for describing the Lagrangian and
Hamiltonian formalisms. Nevertheless, some ambiguities arise when considering
the solutions of the field equations. We hope that a suitable extension of our
formalism to field theories will enable these difficulties to be overcome and
complete the model given in [10, 41].

## Acknowledgments

We acknowledge the financial support of the Ministerio de Ciencia e Innovación
(Spain), projects MTM2008-00689 and MTM2009-08166-E. We also thank Mr. Jeff
Palmer for his assistance in preparing the English version of the manuscript.

## References

  * [1] R. Abraham and J.E. Marsden, _Foundations of mechanics_ , 2nd ed., Benjamin-Cummings, New York 1978.
  * [2] V. Aldaya and J.A. de Azcarraga, “Variational Principles on r-th order jets of fibre bundles in Field Theory”, J. Math. Phys. 19(9) (1978) 1869.
  * [3] V. Aldaya and J.A. de Azcarraga, “Higher order Hamiltonian formalism in Field Theory”, J. Phys. A 13(8) (1980) 2545–2551.
  * [4] R. Banerjee, P. Mukherjee, and B. Paul, “Gauge symmetry and W-algebra in higher derivative systems”, JHEP 08 (2011) 085.
  * [5] M. Barbero Liñán, A. Echeverría-Enríquez, D. Martín de Diego, M.C. Muñoz-Lecanda, and N. Román Roy, “Skinner-rusk unified formalism for optimal control systems and applications”, J. Math. Phys. A: Math. Theor. 40(40) (2007) 12071–12093.
  * [6] M. Barbero Liñán, A. Echeverría-Enríquez, D. Martín de Diego, M.C. Muñoz-Lecanda, and N. Román-Roy, “Unified formalism for non-autonomous mechanical systems”, J. Math. Phys. 49(6) (2008) 062902.
  * [7] J. Barcelos-Neto and C.P. Natividade, “Hamiltonian Path Integral Formalism with Higher Derivatives”, Zeitsch. Phys. C: Parts. Fields 51(2) (1991) 313–319.
  * [8] C. Batlle, J. Gomis, J.M. Pons, and N. Román-Roy, “Lagrangian and Hamiltonian constraints for second-order singular Lagrangians”, J. Phys. A: Math. Gen. 21(12) (1988) 2693–2703.
  * [9] L.V. Belvedere, R.L.P.L. Amaral, and N.A. Lemos, “Canonical Transformations in a Higher Derivative Field Theory”, Zeitsch. Phys. C: Parts. Fields 66(4) (1995) 613–617.
  * [10] C.M. Campos, M. de León, D. Martín de Diego, and K. Vankerschaver, “Unambigous formalism for higher-order lagrangian field theories”, J. Phys A: Math Theor. 42 (2009) 475207.
  * [11] F. Cantrijn, M. Crampin, and W. Sarlet, “Higher-order differential equations and higher-order Lagrangian mechanics”, Math. Proc. Cambridge Philos. Soc. 99(3) (1986) 565–587.
  * [12] J.F. Cariñena and C. López, “The time-evolution operator for higher-order singular Lagrangians”, Internat. J. Modern Phys. A 7(11) (1992) 2447–2468.
  * [13] L. Colombo, D. Martín de Diego, and M. Zuccalli, “Optimal control of underactuated mechanical systems: a geometric approach”, J. Math. Phys. 51(8) (2010) 083519.
  * [14] J. Cortés, S. Martínez, and F. Cantrijn, “Skinner-Rusk approach to time-dependent mechanics”, Physics Letters A 300 (2002) 250–258.
  * [15] M. de León, J.C. Marrero, and D. Martín de Diego, “A new geometric setting for classical field theories”, Banach Center Publ. 59 (2003) 189–209.
  * [16] M. de León, D. Martín de Diego, and A. Santamaría Merino, “Geometric numerical integration of nonholonomic systems and optimal control problems”, Eur. J. Control 10(5) (2004) 515–524.
  * [17] M. de León and P.R. Rodrigues, _Generalized classical mechanics and field theory_ , North-Holland Math. Studies, vol. 112, Elsevier Science Publishers B.V., Amsterdam 1985.
  * [18] A. Echeverría-Enríquez, C. López, J. Marín-Solano, M.C. Muñoz-Lecanda, and N. Román-Roy, “Lagrangian-Hamiltonian unified formalism for field theory”, J. Math. Phys. 45(1) (2004) 360–380.
  * [19] A. Echeverría-Enríquez, M.C. Muñoz-Lecanda, and N. Román-Roy, “Geometrical setting of time-dependent regular systems. Alternative models.”, Rev. Math. Phys. 3(3) (1991) 301–330.
  * [20] P.L. García and J. Muñoz, “On the geometrical structure of higher order variational calculus”, Procs. IUTAM-ISIMM Symposium on Modern Developments in Analytical Mechanics, Vol. I (Torino, 1982). Atti. Accad. Sci. Torino Cl. Sci. Fis. Math. Natur. 117 (1983) suppl. 1, 127–147.
  * [21] M.J. Gotay and J.M. Nester, “Presymplectic Lagrangian systems. I. The constraint algorithm and the equivalence theorem.”, Ann. Inst. H. Poincaré Sect. A 30(2) (1979) 129–142.
  * [22] M.J. Gotay, J.M. Nester, and G. Hinds, “Presymplectic manifolds and the Dirac-Bergmann theory of constraints”, J. Math. Phys. 19(11) (1978) 2388–2399.
  * [23] X. Gràcia, J.M. Pons, and N. Román-Roy, “Higher-order Lagrangian systems: Geometric structures, dynamics and constraints”, J. Math. Phys. 32(10) (1991) 2744–2763.
  * [24] X. Gràcia, J.M. Pons, and N. Román-Roy, “Higher-order conditions for singular Lagrangian systems”, J. Phys. A: Math. Gen. 25 (1992) 1981–2004.
  * [25] O. Krupkova, “A Geometrical Setting for Higher-Order Dirac-Bergmann Theory of Constraints”, J. Math. Phys. 35(12) (1994) 6557–6576.
  * [26] Y.A. Kuznetsov and M.S. Plyushchay, “(2+1)-dimensional Models of Relativistic-Particles with Curvature and Torsion”, J. Math. Phys. 35(6) (1994) 2772–2784.
  * [27] E. Martínez, _Geometría de ecuaciones diferenciales aplicada a la mecánica_ , Ph.D. thesis, Universidad de Zaragoza 1991.
  * [28] S.A. Martínez, R. Montemayor, and L.F. Urrutia, “Perturbative Hamiltonian constraints for higher order theories”, arXiv:1104.4923v1 [hep-th]Int. J. Mod. Phys A 26(26) (2011) 4661–4686.
  * [29] R. Miron, _The Geometry of Higher-order Hamilton Spaces: Applications to Hamiltonian Mechanics_ , Fundamental Theories of Physics, vol. 132, Springer-Verlag, New York 2003arXiv:1003.2501 [math.DG].
  * [30] M.C. Muñoz-Lecanda and N. Román-Roy, “Lagrangian theory for presymplectic systems”, Ann. Inst. H. Poincaré A 52(1) (1992) 27–45.
  * [31] V.V. Nesterenko, “Singular Lagrangians with higher-order derivatives”, J. Phys. A: Math. Gen. 22(10) (1989) 1673–1687.
  * [32] A. Pais and G.E. Uhlenbeck, “On Field Theories with Non-Localized Action”, Phys. Rev. 79(1) (1950) 145–165.
  * [33] R.D. Pisarski, “Field theory of paths with a curvature-dependent term”, Phys. Rev. D 34(2) (1986) 670–673.
  * [34] M.S. Plyushchay, “Canonical quantization and mass spectrum of relativistic particle: analog of relativistic string with rigidity”, Mod. Phys. Lett. A 3(13) (1988) 1299–1308.
  * [35] M.S. Plyushchay, “The model of relativistic particle with torsion”, Nucl. Phys. B 362 (1991) 54–72.
  * [36] D.J. Saunders, _The geometry of jet bundles_ , London Mathematical Society, Lecture notes series, vol. 142, Cambridge University Press, Cambridge, New York 1989.
  * [37] D.J. Saunders and M. Crampin, “On the Legendre map in higher-order field theories”, J. Phys. A: Math. Gen. 23 (1990) 3169–3182.
  * [38] H.J. Schmidt, “Conformal Relations and Hamiltonian Formulation of Fourth Order Gravity”, Grav. Cosmol. 3 (1997) 266–274.
  * [39] R. Skinner and R. Rusk, “Generalized Hamiltonian dynamics. I. Formulation on ${T^{*}Q}\oplus{TQ}$”, J. Math. Phys. 24(11) (1983) 2589–2594.
  * [40] W.M Tulczyjew, “Sur la différentielle de Lagrange”, C. R. Acad. Sci. Paris Sér. A 280 (1975) 1295–1298.
  * [41] L. Vitagliano, “The Lagrangian-Hamiltonian Formalism for Higher Order Field Theories”, J. Geom. Phys. 60 (2010) 857–873.


# Augmented Random Search for Multi-Objective Bayesian Optimization of Neural
Networks

Mark Deutel
Friedrich-Alexander-Universität
Erlangen, Germany
<EMAIL_ADDRESS>
&Georgios Kontes
Fraunhofer Institute for Integrated Circuits IIS
Nürnberg, Germany
<EMAIL_ADDRESS>
&Christopher Mutschler
Fraunhofer Institute for Integrated Circuits IIS
Nürnberg, Germany
<EMAIL_ADDRESS>
&Jürgen Teich
Friedrich-Alexander-Universität
Erlangen, Germany
<EMAIL_ADDRESS>

###### Abstract

Deploying Deep Neural Networks (DNNs) on tiny devices is a common trend to
process the increasing amount of sensor data being generated. Multi-objective
optimization approaches can be used to compress DNNs by applying network
pruning and weight quantization to minimize the memory footprint (RAM), the
number of parameters (ROM) and the number of floating point operations (FLOPs)
while maintaining the predictive accuracy. In this paper, we show that
existing multi-objective Bayesian optimization (MOBOpt) approaches can fall
short in finding optimal candidates on the Pareto front and propose a novel
solver based on an ensemble of competing parametric policies trained using an
Augmented Random Search Reinforcement Learning (RL) agent. Our methodology
aims at finding feasible tradeoffs between a DNN’s predictive accuracy, memory
consumption on a given target system, and computational complexity. Our
experiments show that we outperform existing MOBOpt approaches consistently on
different data sets and architectures such as ResNet-18 and MobileNetV3.

##  1 Introduction

The deployment of DNNs on tiny devices is restricted to the constraints
imposed by the target platform. Constraints such as <1MB Flash, <512Kb RAM,
and clock speeds in the low MHz range make the design of DNN models for such
platforms challenging. In general, several conflicting objectives and
constraints such as memory availability, inference time, and power consumption
of the deployed DNN model must be considered.

This work investigates multi-objective Bayesian optimization (MOBOpt) of DNN
hyperparameters for embedded devices (such as ARM Cortex-M platforms) using
deep compression. The goal of multi-objective optimization (MOOpt) is to
either maximize or minimize a set of objectives. Assume, without loss of
generality, maximizing some set of objective functions
$f(x)=[f_{1}(x),\dots,f_{n}(x)]\in\mathbb{R}^{n}$, where $n\geq 2$, while
satisfying a set set of constraints $g(x)\geq 0\in\mathbb{R}^{V}$ where $V\geq
0$, $x\in\mathcal{X}\subset\mathbb{R}^{d}$, and $\mathcal{X}$ is a compact
set. Usually, there exists no single solution $x^{*}$ that maximizes all
objectives while also satisfying all $V$ constraints.

######  Definition 1.1.

[6] An objective function evaluation $f(x)$ Pareto-dominates $f(x^{\prime})$,
denoted as $f(x)\succ f(x^{\prime})$, if $f_{m}(x)\geq f_{m}(x^{\prime})$ for
all $m=1,\dots,M$ and there exists at least one $m\in\\{1,\dots,M\\}$ such
that $f_{m}(x)>f_{m}(x^{\prime})$.

######  Definition 1.2.

[6] A set of Pareto-optimal tradeoffs $P(x)$ over a set of samples
$X\subseteq\mathcal{X}$ is called the Pareto front (PF).

$\mathcal{P}(X)=\\{f(x):x\in X,\nexists x^{\prime}\in Xs.t.f(x^{\prime})\succ
f(x)\\}$

$\mathcal{P}_{\text{{feas}}}(X)=\mathcal{P}(\\{x\in X:g(x)\geq 0\\})$ is
defined as the feasible PF.

Hence, the goal of MOOpt is to identify an approximate PF $\mathcal{P}(X_{n})$
of the true PF $\mathcal{P}(X)$ within a search budget of $n$ evaluations. For
problems where the true Pareto-front is not known, the quality of
$\mathcal{P}(X_{n})$ is commonly evaluated using the Hypervolume (HV)
indicator, also called S-metric.

######  Definition 1.3.

[6] The Hypervolume indicator $HV(\mathcal{P}(X)|r)$ is the $M$-dimensional
Lebesgue measure $\lambda_{M}$ of the region dominated by $\mathcal{P}(X)$ and
bounded from below by a reference point $r\in\mathbb{R}^{M}$.

A feasible reference point is usually derived from domain knowledge of the
problem. Multiple PFs can be compared by their HV if they were calculated with
the same reference point and if they share the same objective values.

A common way of addressing MOOpt is by evolutionary algorithms like NSGA-II
[7]. However, these algorithms have a high sample complexity reducing their
effectiveness under a small number of evaluations $n$. As a tradeoff, Bayesian
Optimization (BO) is a strategy to efficiently optimize MOOpt with expensive
objective functions, aiming at minimizing the number of required evaluations.
It treats the objective functions as black-boxes and places a prior over them,
thereby capturing beliefs about their behaviour. Over time, as new samples are
collected, the prior is updated iteratively to form the posterior distribution
over the objective functions, usually with a Gaussian Process (GP). The
posterior, in turn, is used in each iteration to determine the next sample-
point to evaluate by employing an acquisition function as a heuristic to
quantize the "usefulness" of the sample. Traditionally, the acquisition
function is also responsible for balancing the exploration and exploitation
tradeoff. Furthermore, for multiple objectives it is common to scale and
accumulate the objective values to form a single-objective problem [19, 30].

A commonly used acquisition function is the Expected Improvement (EI) [29]

$EI(x)=\mathbb{E}\max(f(x)-f^{*},0)$ (1)

where $f^{*}$ is the objective value of the best observed sample so far. For a
given Bayesian model the EI can be evaluated with an integral over the
posterior distribution either analytically or by Monte-Carlo sampling [35],
which allows to approximate the EI as

$qEI(x)\approx\frac{1}{N}\sum_{i=1}^{N}\max_{j\dots
q}\\{\max(\xi_{i}-f^{*},0)\\},\xi_{i}\sim\mathbb{P}(f(x)\mid\mathcal{D}),$ (2)

where $q$ is the number of samples considered jointly and
$\mathbb{P}(f(x)\mid\mathcal{D})$ is the posterior distribution of the
function $f$ at $x$ given the data $\mathcal{D}$ observed so far.

We provide a methodology that combines DNN compression using filter pruning
[22] and weight quantization [10] with MOBOpt for microcontroller targets.
This allows us to optimize DNNs, considering the objectives of top-1 accuracy,
memory consumption, and FLOPS, using a Bayesian model while minimizing the
number of expensive objective evaluations. Our optimization approach consists
of two building blocks: (1) the multi-objective optimization loop and (2) the
objective functions evaluator. The optimization loop iteratively proposes new
sets of training, pruning and quantization related hyperparameters, using our
novel solver until a termination condition is met. The trained DNN resulting
from the use of each of the proposed sets of hyperparameters is then evaluated
which results in a vector of values, one for each objective. We propose a
novel solver using an ensemble of competing local parameterizable policies
which are iteratively trained on the underlying surrogate model using an
Augmented Random Search (ARS) [26] reinforcement learning (RL) agent. Our
experiments show the effectiveness of our approach in finding optimal DNNs by
comparing our strategy to other state of the art multi-objective optimization
strategies for several use-cases. The obtained solutions can be directly
deployed on common microcontrollers.

The rest of the paper is structured as follows. Sec. 2 discusses related work.
Sec. 3 provides details about our RL-agent and how we integrate it into our
MOBOpt DNN hyperparameter exploration process. We evaluate our approach in
Sec. 4 on several public data sets with different types of neural networks
(Sec. 4.2), and on a synthetic optimization problem (Sec. 4.3). Sec. 5
concludes.

##  2 Related Work

Different approaches for efficient DNN design and optimization have been
prominently discussed in scientific research: Dedicated architectures such as
the MobileNet class [14, 32, 13] have been proposed, introducing scaling
parameters and specialized layers, i.e., depthwise-separable convolutions, to
control size and inference time. Neural Architecture Search (NAS) focuses on
finding DNNs with optimal layer configurations related to a set of target
metrics either by using RL [37] or by relaxing the problem to be
differentiable and then using gradient-based methods [25]. Deep Compression
features a number of techniques, including pruning [22], which dynamically
removes weights during training, and weight quantization [17], which reduces
the resolution at which weights are represented.

Based on these approaches, several deployment pipelines for embedded devices
have been proposed: Han et al. [11] describe a pipeline combining network
pruning, weight quantization and Huffman coding. Follow-up work compares
different pruning and quantization methods [8]. Other pipelines are MCUNet
[24] and Once-for-All [5] which both focus on NAS to find candidates for
deployment.

Finding optimal hyperparameters for DNN training requires expertise and
extensive trial and error. By considering DNN compression and deployment in a
resource- and execution-time-constrained environment, additional tunable
parameters for compression, as well as additional constraints are introduced
that make the optimization problem a tradeoff between multiple objectives.

In scientific research, multi objective optimization (MOOpt) is a well
established approach to solve problems with conflicting objectives. Some of
the most thoroughly explored algorithms are based on multi-objective
evolutionary algorithms (MOEA), e.g., NSGA-II [7]. Probably closest to our
application, Wang et al. [33] explore hyperparameter and compression-parameter
optimization using evolutionary algorithms for DNN deployment in combination
with pruning and quantization. However, due to the population-based nature of
evolutionary algorithms, MOEAs typically require a large number of
evaluations, which in the case of DNN hyperparameter optimization can become
time- and resource-consuming as a large set of networks have to be trained and
evaluated.

As an alternative to MOEAs, algorithms based on Bayesian Optimization (BO)
[29] have been used for MOOpt to minimize the number of function evaluations
by utilizing surrogate models for each objective. A prominent representative
of this Multi-Objective Bayesian Optimization (MOBOpt) class of algorithms is
ParEGO [19], which randomly scales the MOOpt to single-target problems and
then selects a sample based on the maximum expected improvement. Another
recently proposed extension of this approach which specifically aims to tackle
problems with a high-dimensional search spaces suggests employing locally
modeled trust regions over subsets of the complete search space [9, 6].

Combining MOOpt with RL has also been explored: Moffaert et al. [28] propose a
multi-policy RL algorithm that learns Pareto-dominating policies using
Q-learning. There is also work that shows that MOOpt can be solved using Deep
RL [23, 18]. Compared to our work, these approaches do not utilize Bayesian
Optimization (BO) but instead directly apply RL to the objective function of
the MOOpt problem. For our optimization problem this is problematic as
evaluating our objective function, i.e., training a DNN, typically takes a
significant amount of time. Furthermore, complex RL strategies like Q-learning
or DRL introduce significant overhead to the sampling strategy. Instead, we
propose to train a set of competing policies within MOBOpt that implement
candidate sampling using very simplistic Augmented Random Search (ARS) [26] RL
agents. To the best of our knowledge, we are the first to consider the
combination of MOBOpt with RL to solve the specific problem of optimizing
hyper- and compression parameters of DNNs targeting embedded microcontrollers.

Algorithm 1 Multi-Objective Bayesian Optimization with Augmented Random Search

Parameters: search budged $J$, learning rate $\alpha$, directions sampled per
iteration $N$, rollout horizon $H$, constant exploration noise $v$, number of
top-performing directions to use $k$, number of objectives $n$, number of
parameters $p$, number of ARS agents $L$, objective function
$f(x)=[f_{1}(x),\dots,f_{n}(x)]$

Create initial prior by evaluating $f(x)$ several times using Latin-Hypercube
sampling

for $i\leftarrow 1$ to $J$ do

Fit Gaussian Process (GP) by maximising the marginal likelihood of previous
evaluations of $f(x)$.

Select $\\{x_{1},x_{2},\dots,x_{L}\\}$ initial states from
$\mathcal{P}_{feas}$ of previous evaluations using k-means clustering.

repeat

for $l\leftarrow 0$ to $L$ do

Sample directions
$\varphi_{1},\varphi_{2},\dots,\varphi_{N}\in\mathbb{R}^{p\times n}$ with
i.i.d. standard normal entries.

Collect the summed reward of the MC-sampled and scaled posteriors, see
Equations 7 and 8, of $2N$ rollouts over the horizon $H$ from the GP using
local policy $\pi_{l}$ and initial state $x_{l}$.
$\displaystyle\pi_{l,j,k,+}(x)$ $\displaystyle=(\theta_{l,j}+v\varphi_{k})x$
(3) $\displaystyle\pi_{l,j,k,-}(x)$
$\displaystyle=(\theta_{l,j}-v\varphi_{k})x$ (4) $\displaystyle\pi_{l,j}(x)$
$\displaystyle=\theta_{l,j}x$ (5)

for $k\in\\{1,2,\dots,N\\}$.

Sort the directions $k$ by $\max\\{r(\pi_{l,j,k,+}),r(\pi_{l,j,k,-})\\}$,
denote by $\varphi_{k}$ the $k$-th largest direction, and by
$r(\pi_{l,j,k,+})$ and $r(\pi_{l,j,k,-})$, the corresponding rewards.

Update the parameters $\theta_{l}$ of policy $\pi_{l}$ using the top-$k$
performing rollouts (with $\theta_{l,0}=0$)
$\displaystyle\theta_{l,j+1}=\theta_{l,j}+\frac{\alpha}{b\sigma_{R}}\sum_{k=1}^{b}\big{(}r(\pi_{l,j,k,+})-r(\pi_{l,j,k,-})\big{)}\varphi_{k}$
(6)

where $\sigma_{R}$ is the standard deviation of the rewards used in the update
step.

end for

until ARS termination condition is satisfied

Perform rollouts for all initial states $x_{l}\in P_{feas}$ using policy
$\pi_{l}$. For each $\pi_{l}$ select the rollout yielding the highest reward
and evaluate using $f(x)$ and extend the prior with the new evaluation

end for

##  3 Method

We first evaluated multiobjective hyperparameter optimization considering
three well-known Bayesian optimization strategies, namely ParEgo [19], TurBO
[9], and MorBO [6]. However, initial tests yielded ambivalent results across
different seeds and use cases. After analyzing these optimization strategies
using an artificial two-dimensional optimization problem, which we will
discuss in more detail in Section 4.3, we decided to (a) adapt our EI
implementation to not clamp "negative improvement" to zero, but instead
penalize it by an additional hyperparameter (which we set to $1e^{-3}$), and
(b) implement an ARS-based RL agent as our solver, with the goal of better
understanding and exploiting the knowledge encoded by our Bayesian surrogate
model.

To iteratively find new sets of hyperparameters, our optimization process uses
an ensemble of competing multi-layer perceptron (MLP)-based RL agents, in
particular ARS, as a replacement for traditional solvers such as NSGA-II or
ParEGO. The policies consist of two linear layers with a hidden layer size of
64 resulting in a couple of thousand trainable parameters each. Augmented
Random Search is an RL agent which learns a set of linear (or MLP) policies
$\pi_{\theta}$, parameterized by a set of vectors $\theta$, one for each
layer, for controlling a dynamic environment $\mathbb{E}_{\xi}$, with $\xi$
encoding the randomness of the environment, maximizing/minimizing an average
reward/loss $r(\pi_{\theta},\xi)$. ARS achieves this by optimizing over the
set of parameters $\theta$ by utilizing derivative-free optimization with
noisy function evaluations and for each layer iteratively performing updates
using directions of the form
$\frac{r(\pi_{\theta+\nu\varphi},\xi_{1})-r(\pi_{\theta-\nu\varphi},\xi_{2})}{\nu}$
for two i.i.d. random variables $\xi_{1}$ and $\xi_{2}$, $\nu$ a positive real
number ($0.008$ in our case), and $\varphi$ a zero mean Gaussian vector with
i.i.d. standard normal entries. The two rewards
$r(\pi_{\theta+\nu\varphi},\xi_{1})$ and $r(\pi_{\theta-\nu\varphi},\xi_{2})$
are obtained by collecting two sets of trajectory rollouts from the system of
interest in opposing directions. The authors highlight three aspects of their
ARS agent: (1) Scaling the update by the standard deviation $\sigma_{R}$ of
the $2N$ rewards collected at each iteration to prevent harmful variations in
the size of each update step, (2) normalizing the states to ensure that the
policy weights the different components of the states equally, and (3)
considering only the best-performing directions for the updates, which
intuitively ensures that they occur over directions that have received high
rewards.

We initialize the training of our competing ARS agents with different samples
from the current feasible Pareto front. To find the most diverse set of
samples, we perform k-means clustering on the front if it consists of more
elements than we can train policies. To query the objective values, i.e.,
accuracy, memory consumption, and FLOPS, for a proposed set of hyperparameters
of a given DNN architecture, our objective function evaluator first trains,
prunes, and quantizes the DNN. Afterwards, the DNN is converted into source
code using an automatic code generator to accurately asses memory usage of
weights and activation tensors. Our implementation performs this procedure
using the compression and deployment pipeline proposed in [8]. The authors
describe a configurable pipeline that supports both DNN pruning and full
weight quantization. Following their results, we focus our experiments on
iterative filter pruning and post-training static quantization.

We integrated ARS into MOBOpt as a parameterized, trainable solver, which can
thus be seen as an alternative to traditional Bayesian solvers like ParEGO,
see Algorithm 1. Compared to other Bayesian solvers, ARS’s derivative approach
does not rely on second order partial derivatives (Hessian) and is therefore
much less computationally complex. In addition, its random sampling approach
is highly parallelizable, allowing for efficient GPU-accelerated execution.

We define the states $x_{0},x_{1},\dots,x_{L}$ of our $L$ competing agents as
vectors of the parameters of the search space of our optimization problem.
Each agent performs actions based on its trainable policy $\pi_{\theta}$ by
altering the parameter values of its state vector within given bounds. We
train the competing policies of our ARS agents for each sample after
evaluating the objective function by performing rollouts on posteriors sampled
from the GP which we fitted by maximising the marginal likelihood of
previously queried evaluation of the objective function beforehand, compare
[34]. The policy training performed for each sample ends after a maximum
number of training steps has been conducted. To obtain the initial prior for
the GP, we propose candidates during the first couple of iterations of the
optimization using Latin Hypercube sampling [27]. We chose this approach over
random sampling because we found that by using Latin Hypercube sampling, we
could significantly improve the expressiveness of our priors and therefore
enhance the performance of all evaluated GP-based sampling strategies.

As a reward $r(x)$, we first scale our $n=4$ objectives to a single objective
value using augmented Chebyshev scalarization [19], see Equation (7), where
$\rho=0.005$ is a small positive value and $\lambda$ is a weight vector that
we draw uniformly at random at the beginning of each sample. We then calculate
the difference between the scaled objective and the best previously visited
(scaled) objective $f^{*}$ as the reward that the ARS agents maximize, see
Equation (8).

$\displaystyle f_{\lambda}(x)$
$\displaystyle=\max_{j=1}^{n}(\lambda_{j}f_{j}(x))+\rho\sum_{j=1}^{n}\lambda_{j}f_{j}(x)$
(7) $\displaystyle r(x)$
$\displaystyle=\begin{cases}f_{\lambda}(x)-f_{\lambda}(f^{*}),&\text{if
}(f_{\lambda}(x)-f_{\lambda}(f^{*}))>0\\\
1e^{-3}(f_{\lambda}(x)-f_{\lambda}(f^{*})),&\text{otherwise}\end{cases}$ (8)

To avoid having to compute the expected value over the posterior of the GP
when computing the acquisition function, a common approach is to use Monte-
Carlo (MC) sampling as an approximation to evaluating the integral over the
posterior distribution. In our case, we implement a quasi-MC sampling approach
to estimate the reward used to train the ARS agents with a fixed set of base
samples.

As a result, the reward $r(x)$ used by our ARS agents is comparable to
acquisition functions used in traditional Bayesian optimization. In
particular, our approach is similar to the expected improvement (EI) used by
ParEgo, with the notable difference that we consider penalized "negative
improvements" instead of clamping it to zero. The main reason for clamping
"negative improvement" in combination with a Monte Carlo-based evaluation of
the GPs is to increase the attractiveness of regions with high uncertainty,
and is therefore the mechanism of EI to control the tradeoff between
exploration and exploitation. However, we argue that we can still achieve the
desired tradeoff if we instead penalize "negative improvements" by
multiplication with a small constant factor, while allowing our ARS policies
to learn from situations where the current objective function evaluation is
worse than the best previously visited one.

After training the competing ARS agents, we perform several rollouts for each
of them starting from their respective starting points selected from
$\mathcal{P}_{\text{{feas}}}(X)$. We then select the policy that yielded the
overall best reward to propose the next set of hyperparameters to be evaluated
on the objective function in the next sample. A variant of this approach would
be to consider a set of best-performing parametrizations as candidates for a
batched optimization in different segments of the Pareto front.

##  4 Evaluation

We applied our multi-objective DNN hyperparameter optimization on two use-
cases with 150 samples each: (1) Classification of 32x32 RGB images (CIFAR10
dataset [20]), trained with a reduced version of ResNet18 [12] (only three
residual blocks instead of four, 1.6M initial parameters) and (2) Time series
classification of (daily) human activities (DaLiAc) [21] with a window length
of 1024 datapoints, trained with a scaled down version of MobileNetv3 [13]
(2.8M initial parameters). Compared to models commonly used by relevant
benchmarks for embedded AI, e.g., TinyML Perf [4], we did not decrease the
initial numbers of neurons in our DNNs’ trainable layers as our optimization
process uses pruning and therefore dynamically adjusts the exact number of
neurons during training. We trained our models using Stochastic Gradient
Decent (SGD) and exponential learning rate decay. For the optimization, we
assumed 256 KB of RAM, 1 MB of ROM and $1e^{9}$ FLOPS as constraints imposed
by common microcontroller platforms.

The detailed list of hyperparameters considered by our optimizer and their
continuous sampling intervals derived from expert knowledge can be found in
the supplementary material. We consider seven parameters controlling general
properties of DNN training (training length, batch size, properties of the
optimizer and learning rate) and four that control the filter pruning. We use
the automated gradual pruning algorithm [36] to generate our pruning schedule.
It takes a start and end epoch calculated relatively to the number of training
epochs and a number of iterative steps as an input. Our optimization considers
the pruning sparsity hyperparameter, i.e., how many filters are removed, for
each convolutional layer separately. Therefore, the search space considered
increases with the depth of the optimized DNN as for each prunable layer an
additional pruning sparsity parameter is added which means that the search
space is extended by one dimension.

(a) MobileNetv3, DaLiAc.

(b) ResNet, CIFAR10.

Figure 1: Our approach (ARS-MOBOpt) outperformed all other optimization
strategies.

(c) MobileNetv3, DaLiAc.

(d) ResNet, CIFAR10.

Figure 2: Feasible Pareto sets proposed by our RL-based MOBOpt of DNNs (blue)
compared to other Bayesian and evolutionary approaches. In both cases we find
samples dominating those proposed by the other algorithms while meeting
imposed target constraints ($<$1MB ROM, $<$256KB RAM, $<$1e9 FLOPs).

###  4.1 Algorithmic Benchmark

As our first experiment we compared the quality of our approach (ARS-MOBOpt)
to several well-known Bayesian optimization strategies (ParEGO [19], TurBO
[9], MorBO [6]), one evolutionary approach (NSGA-II [7]) and a random sampling
approach as a baseline, see Fig. 2. We gave each optimization strategy a
search budget of 150 samples to evaluate the objective functions and monitored
the improvement of the feasible hypervolume over the samples. For all tested
Bayesian strategies the first 10 samples were conducted as priors using Latin
Hypercube sampling [27]. We normalized our objectives accuracy, ROM
consumption, RAM consumption and FLOPs to their respective constraints an used
the maximum feasible objective value as a common reference when computing the
hypervolume. Furthermore, we performed 5 independent seeds for each strategy
and provide the observed variance in Fig. 2 as well.

Table 1: Excerpt from the results of the multivariate datasets of the UEA &
UCR time series classification benchmark [2] for our ARS strategy (columns
3–7) and ParEGO (columns 8–12). For both strategies, we show the achieved
hypervolume after 150 trials as well as the maximum accuracy. We also show the
minimum memory and FLOPs required to achieve at least 70% accuracy.

Dataset | InceptionTime | ARS | ParEGO
---|---|---|---
| Acc. [%] | HV | Acc. [%] | ROM [Kb] | RAM [Kb] | FLOPs | HV | Acc. [%] | ROM [Kb] | RAM [Kb] | FLOPs
Epilepsy | 98.55 | 0.97 | 97.81 | $120\,512$ | $4920$ | $3\,570\,578$ | 0.93 | 94.16 | $66\,988$ | $3392$ | $2\,050\,650$
BasicMotions | 100.00 | 0.96 | 97.50 | $131\,176$ | $3000$ | $2\,745\,720$ | 0.97 | 97.50 | $86\,696$ | $2500$ | $1\,493\,195$
Cricket | 98.61 | 0.96 | 97.22 | $100\,404$ | $29\,924$ | $16\,020\,432$ | 0.95 | 95.83 | $76\,068$ | $30\,520$ | $10\,139\,994$
ERing | 87.78 | 0.96 | 96.67 | $100\,256$ | $1988$ | $2\,025\,968$ | 0.93 | 93.33 | $73\,196$ | $1228$ | $1\,002\,400$
ArticularyWordRecognition | 98.33 | 0.94 | 95.64 | $150\,516$ | $6180$ | $4\,194\,267$ | 0.92 | 92.36 | $80\,748$ | $5328$ | $2\,127\,501$
UWaveGestureLibrary | 87.81 | 0.91 | 91.67 | $110\,256$ | $6944$ | $5\,779\,512$ | 0.91 | 91.67 | $72\,052$ | $4092$ | $3\,027\,980$
NATOPS | 96.11 | 0.86 | 87.22 | $129\,032$ | $5784$ | $2\,793\,175$ | 0.78 | 78.33 | $100\,264$ | $4944$ | $1\,118\,016$
SelfRegulationSCP1 | 83.96 | 0.79 | 79.85 | $104\,688$ | $22\,400$ | $17\,814\,384$ | 0.78 | 78.73 | $78\,052$ | $22\,400$ | $7\,147\,130$
PEMS-SF | – | 0.76 | 81.50 | $137\,784$ | $554\,832$ | $7\,984\,536$ | 0.79 | 84.97 | $238\,016$ | $555\,756$ | $57\,178\,800$
Heartbeat | 58.05 | 0.73 | 74.51 | $81\,648$ | $99\,224$ | $8\,139\,132$ | 0.73 | 74.02 | $62\,532$ | $99\,224$ | $2\,793\,768$

We share results for two common DNN architectures, MobileNetv3 and ResNet18,
which we trained using two datasets, DaLiAc and CIFAR10, see Fig. 1(a) and
Fig. 1(b). The plots show the observed hypervolume over the number of
optimization samples. Therefore, the resulting curves, one for each
optimization strategy, describe the improvement of the hypervolume. First, all
informed solvers outperformed the independent random sampling baseline for
both use-cases. Second, all the approaches that are based on Bayesian
optimization, i.e., TurBO, MorBO, ParEGO and ARS-MPBOpt, which consider the
constraints of a very tight search budget of 150 samples, performed better
then the evolutionary sampling strategy (NSGA-II). Additionally, for both use-
cases a significant Hypervolume improvement can be observed when using our
ARS-based sampling strategy with 3000 sampling directions, a top-$k$ selection
percentage of 1%, and a rollout horizon of 4 to train the competing policies.
We interpret this to mean that by using a trainable RL-based strategy to
determine new promising parametrizations as the optimization progresses, our
algorithm makes much better use of the knowledge about the search space
encoded in the surrogate model than the other non-trainable Bayesian sampling
approaches.

In addition, we provide qualitative results for both considered use cases, see
Fig. 2. The plots show the Pareto optimal samples for our approach (in blue)
compared to all other algorithms tested, see Fig. 1(c) and Fig. 1(d). For both
use cases, ARS-MOBOpt was able to find samples that are Pareto-dominant over
those proposed by the other algorithms, while satisfying all imposed target
constraints ($<$1MB ROM, $<$256KB RAM, $<$1e9 FLOPs). Moreover, for both use
cases, the number of elements $n$ in the two sets of feasible Pareto optimal
configurations resulting from our approach are larger than the sets found by
the other approaches, implying that our algorithm was able to provide a
significantly larger variety of Pareto optimal samples (deployable DNNs).

To get more insight into the general performance of ARS, we tested it on a
subset of the multivariate datasets of the UEA & UCR time series
classification benchmark [2] and compared ourselves to ParEGO using the same
setup as described above, see Table 1 for all data sets on which reasonable
models with a predictive accuracy of at least 70% are found (and the
supplementary material for a complete listing). To provide context, we also
list reference results for InceptionTime [16], that we took from [2]. We let
both ARS and ParEGO optimize a CNN architecture with a single regular
convolution followed by 10 depth-wise separable convolutions with batchnorm
and with a total of 5 squeeze and excitation blocks [15] after convolutions
10, 8, 6, 4, and 2, followed by adaptive average pooling and a single linear
layer for classification (2.6m initial parameters). Our approach achieves a
better hypervolume than ParEGO in 7 of 10 data sets (and is en par on one data
set). If we also consider data sets where we found models with predictive
accuracies below 70% our approach outperforms ParEGO in approx. two-thirds of
the data sets, see supplementary material. From the results we also see that
compared to ParEGO, our algorithm was generally better at finding DNNs with
higher accuracy scores, but often at the cost of slightly higher memory and
FLOPs requirements.

###  4.2 Robustness and Hyperparameter Selection

(a) Number of sampling directions $N$ performed for each step.

(b) Percentage of top-$k$ performing samples from $N$ selected for policy
updates.

(c) Rollout Horizon $H$ performed by the competing policies

Figure 3: Detailed results examining the effects of the three key ARS
hyperparameters on the achieved hypervolume, 5 seeds each. MobileNetv3, 1.6M
init. params, DaLiAc dataset, window length 1024.

Our proposed ARS sampling strategy can be configured with a number of
hyperparameters that affect the behavior of the ARS algorithm, see Alg. 1. The
quality of the results obtained by our algorithm can vary depending on the
parameterization, see Fig. 3: In general, choosing a learning rate of
$1e^{-3}$, an exploration noise of $1e^{-2}$, a top-$k$ selection rate of
$1\%$, a number of sampling directions between $400$ and $3000$, and a rollout
horizon of $4$ yielded the best results. In the following, we want to further
discuss the impact of key hyperparameters, i.e., the number of sampling
directions $N$, the top-$k$ percentage of directions selected for policy
updates, and the number of steps $H$ taken for each episode (rollout horizon),
to provide a broader understanding of their effects.

First, especially for complex optimization problems with a high-dimensional
parameter space, a high number of sampling directions significantly improved
the hypervolume that our ARS-based sampling strategy was able to achieve,
compared to a low number of directions, which often resulted in a below-
average performance, see Fig. 3(a). However, we also found, that it is not
feasible to increase the number of directions indefinitely to support more and
more complex problems, as this also significantly increases the time required
to train the ARS policies and the memory consumption of our algorithm. We
found that the exact number of sampling directions which is required to obtain
a competitive result is highly correlated with the complexity of the
underlying optimization problem.

Second, when increasing the top-$k$ percentage of sampling directions selected
by ARS to perform policy updates, we observed that only selecting a small
subset of $1\%$ of the sampled directions to perform policy updates improved
the hypervolume achieved by ARS compared to using larger subsets, see Fig.
3(b). Our observation is thus consistent with [26]’s argument for introducing
the hyperparameter as part of ARS. The authors point out that including all
observed rewards in the parameter update can be detrimental to performance
because outliers can easily introduce bias.

Last, we found that an optimal episode length (rollout horizon) is at $H=4$
steps, see Fig. 3(c). Both a significantly smaller and larger episode length
on average resulted in a decreased performance. Still, we want to point out
that we observed a significantly larger variance for longer episode lengths
compared to shorter episode lengths. We interpret this to mean that even
though ARS can perform excellent at longer episode lengths in some cases,
especially at a lower number of samples $<100$, this seems to make the
algorithm more unstable overall and thus less reliable.

###  4.3 Intuition

(a) Bayesian surrogate

(b) EI

(c) Bayesian surrogate

(d) EI

(e) Ground truth

Figure 4: For ParEgo and given two sets of priors marked with red triangles,
Fig. 4(a) to 4(d) show the topography of the two Bayesian surrogates after 40
samples for both the objective value (Fig. 4(a), 4(c)) and the expected
improvement (Fig. 4(b), 4(d)) (Ground truth depicted in Fig. 4(e) [31] and the
global minimum is at $\theta_{0}=15$ and $\theta_{1}=5$).

(f) Bayesian surrogate

(g) EI

(h) Bayesian surrogate

(i) EI

Figure 5: For ARS-MOBOpt and given the same two sets of initial priors as well
as the same ground truth that we both described in Fig. 5, Fig. 4(f) to 4(i)
show the topography of the two Bayesian surrogates after 40 samples for both
the objective value (Fig. 4(f), 4(h)) and the expected improvement (Fig. 4(g),
4(i)). The rollouts for all competing trained policies are shown as lines with
their starting points marked by red crosses.

To better understand why our RL-based solver can improve on other Bayesian
solvers like ParEgo, we analyzed both using a synthetic optimization problem.
Suppose we minimize a two-dimensional single objective optimization problem
[31] using both ParEgo and our approach, see Fig. 5. We chose this problem
because it presents an interesting challenge: it has a landscape with large
areas with little to no gradient combined with some steep minima and maxima.
We provide the topography of the objective function in Fig. 4(e) and show the
respective Bayesian surrogates of ParEgo and ARS-MOBOpt as well as the
topographies of their expected improvement (EI) after 40 trials in Fig. 5 and
5. For our approach (ARS-MOBOpt), we also visualize the rollouts performed
during the validation of the local policies for five selected start points
(red crosses) after the last (40th) sample.

We manually selected two sets of priors (marked as red triangles) to provide
both algorithms with interesting starting situations: First, a situation where
all samples are close together in a region with almost no gradient, see Fig.
4(a) and 4(f). This initialization is interesting because it provides almost
no information about the environment, requiring extensive exploration by the
algorithms before they can exploit found minima. Second, a more general
starting situation with a broader distribution of prior samples, see Fig. 4(c)
and 4(h). This initialization focuses more on evaluating how well the
algorithms can apply the exploration-exploitation tradeoff and how fast they
can find minima. For both priors, we took care not to include samples close to
the global minimum.

Looking at the results proposed by ParEgo (marked as black dots) after 40
samples in Fig. 5, it is clear that for both sets of priors the algorithm
seems to have had a clear focus on exploration, leading to a wide sampling of
the search space. However, looking at Fig. 4(a), this can lead to situations
where even though the global optimum has been found it was not fully
exploited. Furthermore, we argue that this focus on exploration is mainly a
result of the definition of the EI as it does not consider any "negative
improvement". Looking at Figs. 4(d) and 4(b), it is clear that this can result
in large parts of the acquisition function having no gradient. We argue that
this is not optimal when relying on gradient-based solvers, as the ParEgo
implementation typically does.

In comparison, if we look at the result of our proposed ARS-based approach in
Fig. 5, it is clear that our competing local policies, visualized as lines
with red crosses as their starting point, have become experts in solving the
environment around their starting point and can therefore provide sound
solutions even in regions without significant gradients. Therefore, compared
to ParEgo, we observed less undirected exploration and a clearer focus on
exploiting environmental knowledge, compare e.g. Fig. 4(f) and Fig. 4(a).
However, despite this more pronounced focus on exploitation, our solver was
still able to escape local minima when it fell into one, see Fig. 4(h).

##  5 Conclusion

We presented a methodology for efficient multi-objective DNN optimization
based on Bayesian optimization and Augmented Random Search (ARS) for
microcontroller targets. Since the objectives accuracy, ROM consumption, RAM
consumption and FLOPs were expensive to evaluate and we were faced with a
limited search budged, we focused on performing time-efficient optimization of
both DNN hyper- and compression-parameters to enable an optimal deployment on
microcontroller platforms. We provided results for two different problems
considering two datasets and DNN architectures and showed empirically that our
algorithm was able to yield a better feasible Pareto front compared to well-
known Bayesian optimization strategies like ParEGO, TurBO or MorBO as well as
evolutionary algorithms like NSGA-II.

## References

  * [1] T. Akiba, S. Sano, T. Yanase, T. Ohta, and M. Koyama.  Optuna: A Next-generation Hyperparameter Optimization Framework.  KDD ’19, 2019.
  * [2] A. Bagnall, J. Lines, A. Bostrom, J. Large, and E. Keogh.  The great time series classification bake off: a review and experimental evaluation of recent algorithmic advances.  Data Mining and Knowledge Discovery, 31:606–660, 2017.
  * [3] M. Balandat, B. Karrer, D. Jiang, S. Daulton, B. Letham, A. G. Wilson, and E. Bakshy.  BoTorch: A Framework for Efficient Monte-Carlo Bayesian Optimization.  Conference on Neural Information Processing Systems (NeurIPS), 2020.
  * [4] C. Banbury, V. J. Reddi, P. Torelli, J. Holleman, N. Jeffries, C. Kiraly, P. Montino, D. Kanter, S. Ahmed, D. Pau, et al.  Mlperf tiny benchmark.  Conference on Neural Information Processing Systems (NeurIPS), 2021.
  * [5] H. Cai, C. Gan, T. Wang, Z. Zhang, and S. Han.  Once-for-all: Train one network and specialize it for efficient deployment.  In International Conference on Learning Representations, 2020.
  * [6] S. Daulton, D. Eriksson, M. Balandat, and E. Bakshy.  Multi-objective bayesian optimization over high-dimensional search spaces.  In The 38th Conference on Uncertainty in Artificial Intelligence, 2022.
  * [7] K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan.  A fast and elitist multiobjective genetic algorithm: Nsga-II.  IEEE Transactions on Evolutionary Computation, 6(2):182–197, 2002\.
  * [8] M. Deutel, P. Woller, C. Mutschler, and J. Teich.  Deployment of Energy-Efficient Deep Learning Models on Cortex-M based Microcontrollers using Deep Compression.  arXiv:2205.10369, 2022.
  * [9] D. Eriksson, M. Pearce, J. R. Gardner, R. Turner, and M. Poloczek.  Scalable global optimization via local bayesian optimization.  In Proceedings of the 33rd International Conference on Neural Information Processing Systems (NeurIPS), 2019.
  * [10] A. Gholami, S. Kim, Z. Dong, Z. Yao, M. W. Mahoney, and K. Keutzer.  A survey of quantization methods for efficient neural network inference.  arXiv:2103.13630, 2021.
  * [11] S. Han, H. Mao, and W. J. Dally.  Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding.  International Conference on Learning Representations, 2016.
  * [12] K. He, X. Zhang, S. Ren, and J. Sun.  Deep residual learning for image recognition.  In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 770–778, 06 2016.
  * [13] A. Howard, M. Sandler, G. Chu, L.-C. Chen, B. Chen, M. Tan, W. Wang, Y. Zhu, R. Pang, V. Vasudevan, Q. V. Le, and H. Adam.  Searching for mobilenetv3.  arXiv:1905.02244, 2019.
  * [14] A. G. Howard, M. Zhu, B. Chen, D. Kalenichenko, W. Wang, T. Weyand, M. Andreetto, and H. Adam.  Mobilenets: Efficient convolutional neural networks for mobile vision applications.  arXiv:1704.04861, 2017.
  * [15] J. Hu, L. Shen, and G. Sun.  Squeeze-and-excitation networks.  In IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 7132–7141, 2018.
  * [16] H. Ismail Fawaz, B. Lucas, G. Forestier, C. Pelletier, D. F. Schmidt, J. Weber, G. I. Webb, L. Idoumghar, P.-A. Muller, and F. Petitjean.  Inceptiontime: Finding alexnet for time series classification.  Data Mining and Knowledge Discovery, 34:1936–1962, 2020.
  * [17] B. Jacob, S. Kligys, B. Chen, M. Zhu, M. Tang, A. Howard, H. Adam, and D. Kalenichenko.  Quantization and training of neural networks for efficient integer-arithmetic-only inference.  IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2018.
  * [18] S. Kim, I. Kim, and D. You.  Multi-condition multi-objective optimization using deep reinforcement learning.  Journal of Computational Physics, 462:111263, 2022.
  * [19] J. Knowles.  Parego: a hybrid algorithm with on-line landscape approximation for expensive multiobjective optimization problems.  IEEE Transactions on Evolutionary Computation, 10(1):50–66, 2006\.
  * [20] A. Krizhevsky.  Learning Multiple Layers of Features from Tiny Images.  University of Toronto, 2012.
  * [21] H. Leutheuser, D. Schuldhaus, and B. M. Eskofier.  Hierarchical, multi-sensor based classification of daily life activities: comparison with state-of-the-art algorithms using a benchmark dataset.  PloS one, 8(10):e75196, 2013.
  * [22] H. Li, A. Kadav, I. Durdanovic, H. Samet, and H. P. Graf.  Pruning Filters for Efficient ConvNets.  arXiv:1608.08710, 2017.
  * [23] K. Li, T. Zhang, and R. Wang.  Deep reinforcement learning for multiobjective optimization.  IEEE transactions on cybernetics, 51(6):3103–3114, 2020.
  * [24] J. Lin, W.-M. Chen, Y. Lin, j. cohn, C. Gan, and S. Han.  MCUNet: Tiny Deep Learning on IoT Devices.  Conference on Neural Information Processing Systems (NeurIPS), 2020.
  * [25] H. Liu, K. Simonyan, and Y. Yang.  DARTS: Differentiable architecture search.  In International Conference on Learning Representations, 2019.
  * [26] H. Mania, A. Guy, and B. Recht.  Simple random search of static linear policies is competitive for reinforcement learning.  In Advances in Neural Information Processing Systems (NeurIPS), 2018.
  * [27] M. D. McKay, R. J. Beckman, and W. J. Conover.  A comparison of three methods for selecting values of input variables in the analysis of output from a computer code.  Technometrics, 42(1):55–61, 2000.
  * [28] K. V. Moffaert and A. Nowé.  Multi-objective reinforcement learning using sets of pareto dominating policies.  Journal of Machine Learning Research, 15(107):3663–3692, 2014.
  * [29] J. Močkus.  On bayesian methods for seeking the extremum.  In Optimization Techniques IFIP Technical Conference, pages 400–404, 1975.
  * [30] B. Paria, K. Kandasamy, and B. Póczos.  A flexible framework for multi-objective bayesian optimization using random scalarizations.  In Uncertainty in Artificial Intelligence, pages 766–776. PMLR, 2020.
  * [31] K. M. Passino.  Biomimicry for optimization, control, and automation.  Springer Science & Business Media, 2005.
  * [32] M. Sandler, A. Howard, M. Zhu, A. Zhmoginov, and L.-C. Chen.  Mobilenetv2: Inverted residuals and linear bottlenecks.  In 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 4510–4520, 2018.
  * [33] Z. Wang, T. Luo, M. Li, J. T. Zhou, R. S. M. Goh, and L. Zhen.  Evolutionary multi-objective model compression for deep neural networks.  IEEE Computational Intelligence Magazine, 16(3):10–21, 2021.
  * [34] C. Williams and C. Rasmussen.  Gaussian processes for regression.  In D. Touretzky, M. Mozer, and M. Hasselmo, editors, Advances in Neural Information Processing Systems (NeurIPS), volume 8. MIT Press, 1995\.
  * [35] J. T. Wilson, R. Moriconi, F. Hutter, and M. P. Deisenroth.  The reparameterization trick for acquisition functions.  NIPS 2017 Workshop on Bayesian Optimization (BayesOpt 2017), 2017\.
  * [36] M. Zhu and S. Gupta.  To prune, or not to prune: exploring the efficacy of pruning for model compression.  arXiv:1710.01878, 2017.
  * [37] B. Zoph and Q. Le.  Neural architecture search with reinforcement learning.  In International Conference on Learning Representations, 2017.

##  6 Supplementary Material

###  6.1 Training Details & Optimization Variables

We present a multi-objective Bayesian optimization approach for DNN
hyperparameter optimization that uses deep compression, i.e., pruning and
quantization, to find feasible tradeoffs between DNN accuracy and resource
consumption. Furthermore, we present a novel solver based on Augmented Random
Search. An illustration of our process can be found in Fig. 6, with its
implementation based on PyTorch, the Optuna [1] framework and BoTorch [3]. The
implementation consists of two building blocks: (1) the multi-objective
optimization loop marked in blue and (2) a set of objective function
evaluators marked in orange, for which we use the implementation discussed in
[8]. The optimization loop iteratively proposes new sets of hyperparameter
configurations using ARS as its solver until a termination condition is met.

Figure 6: Overview of our proposed RL-based multi-objective Bayesian DNN
hyperparameter optimization approach for microcontroler targets.

We provide a complete listing of the hyperparameters that are optimized and
their search space intervals in Table 2. The first seven parameters are
hyperparameters related to general DNN training, while the last five are
related to compression. Note that each trainable layer (convolutions and
linear layers) has its own optimizable pruning sparsity, and that we use
iterative pruning with the pruning start and pruning end parameters defined
relative to the number of training epochs. The search space intervals are
chosen either based on expert knowledge, e.g., learning rate, momentum or
weight decay, or based on time and hardware constraints of the optimiztion,
e.g., training epochs and batch size.

Table 2: Hyperparameters considered by the multi-objective optimization. Learning rate schedule, pruning start, and end are relative to the epochs. Parameter | Search Space | Interval
---|---|---
epochs | uniform | $[100,500]$
batch size | uniform | $[20,200]$
learning rate (lr) | log. uniform | $[1e^{-5},1e^{-2}]$
momentum | log. uniform | $[0.7,0.99]$
lr schedule | uniform | $[0.4,0.9]$
lr gamma | uniform | $[0.4,0.9]$
weight decay | log. uniform | $[0.6,0.99]$
pruning start | uniform | $[0.0,0.6]$
pruning end | uniform | $[0.8,0.95]$
pruning steps | uniform | $[1,20]$
pruning sparsity | uniform | $[0.1,0.99]$

###  6.2 Complete Listing for UEA & ICR Time Series Classification Benchmark

In Table 3 we provide all results we obtained for the multivariate datasets of
the UEA & UCR time series classification benchmark [2]. We provide results for
our ARS strategy (columns 3–7) and ParEGO (columns 8–12). For both strategies,
we show the achieved hypervolume after 150 trials as well as the maximum
accuracy. We also show the minimum memory and FLOPs required to achieve at
least 70% accuracy. If no trained networks were found that met these
requirements (marked in gray), we show the memory and FLOPs consumption of the
network that achieved the highest accuracy. We provide single objective
reference results for InceptionTime [16] as taken from [2].

Table 3: Results for the multivariate datasets of the UEA & UCR time series
classification benchmark [2] for our ARS strategy (columns 3–7), ParEGO
(columns 8–12) and InceptionTime (column 1) as a reference.

Dataset | InceptionTime | ARS | ParEGO
---|---|---|---
| Acc. [%] | HV | Acc. [%] | ROM [Kb] | RAM [Kb] | FLOPs | HV | Acc. [%] | ROM [Kb] | RAM [Kb] | FLOPs
Epilepsy | 98.55 | 0.97 | 97.81 | $120\,512$ | $4920$ | $3\,570\,578$ | 0.93 | 94.16 | $66\,988$ | $3392$ | $2\,050\,650$
BasicMotions | 100.00 | 0.96 | 97.50 | $131\,176$ | $3000$ | $2\,745\,720$ | 0.97 | 97.50 | $86\,696$ | $2500$ | $1\,493\,195$
Cricket | 98.61 | 0.96 | 97.22 | $100\,404$ | $29\,924$ | $16\,020\,432$ | 0.95 | 95.83 | $76\,068$ | $30\,520$ | $10\,139\,994$
ERing | 87.78 | 0.96 | 96.67 | $100\,256$ | $1988$ | $2\,025\,968$ | 0.93 | 93.33 | $73\,196$ | $1228$ | $1\,002\,400$
ArticularyWordRecognition | 98.33 | 0.94 | 95.64 | $150\,516$ | $6180$ | $4\,194\,267$ | 0.92 | 92.36 | $80\,748$ | $5328$ | $2\,127\,501$
UWaveGestureLibrary | 87.81 | 0.91 | 91.67 | $110\,256$ | $6944$ | $5\,779\,512$ | 0.91 | 91.67 | $72\,052$ | $4092$ | $3\,027\,980$
NATOPS | 96.11 | 0.86 | 87.22 | $129\,032$ | $5784$ | $2\,793\,175$ | 0.78 | 78.33 | $100\,264$ | $4944$ | $1\,118\,016$
SelfRegulationSCP1 | 83.96 | 0.79 | 79.85 | $104\,688$ | $22\,400$ | $17\,814\,384$ | 0.78 | 78.73 | $78\,052$ | $22\,400$ | $7\,147\,130$
PEMS-SF | – | 0.76 | 81.50 | $137\,784$ | $554\,832$ | $7\,984\,536$ | 0.79 | 84.97 | $238\,016$ | $555\,756$ | $57\,178\,800$
Heartbeat | 58.05 | 0.73 | 74.51 | $81\,648$ | $99\,224$ | $8\,139\,132$ | 0.73 | 74.02 | $62\,532$ | $99\,224$ | $2\,793\,768$
HandMovementDirection | 36.49 | 0.60 | 60.81 | $171\,112$ | $23\,564$ | $10\,114\,533$ | 0.45 | 45.95 | $99\,484$ | $18\,588$ | $9\,716\,270$
FingerMovements | 56.00 | 0.59 | 60.00 | $161\,940$ | $6272$ | $3\,100\,887$ | 0.58 | 59.00 | $168\,232$ | $6968$ | $4\,340\,149$
SelfRegulationSCP2 | 47.22 | 0.58 | 58.33 | $105\,120$ | $58\,708$ | $39\,219\,912$ | 0.56 | 56.67 | $183\,456$ | $39\,156$ | $24\,157\,260$
Handwriting | 64.24 | 0.57 | 58.00 | $208\,100$ | $5424$ | $4\,653\,128$ | 0.71 | 72.00 | $130\,684$ | $4752$ | $5\,555\,856$
EigenWorms | – | 0.55 | 60.16 | $211\,472$ | $449\,600$ | $546\,991\,101$ | 0.50 | 53.91 | $142\,288$ | $683\,364$ | $703\,130\,472$
MotorImagery | – | 0.55 | 60.00 | $148\,500$ | $771\,000$ | $83\,765\,403$ | 0.55 | 61.00 | $158\,256$ | $833\,956$ | $190\,908\,344$
EthanolConcentration | 23.19 | 0.53 | 54.02 | $146\,820$ | $59\,040$ | $47\,050\,848$ | 0.49 | 49.43 | $208\,636$ | $45\,484$ | $64\,709\,019$
AtrialFibrillation | 20.00 | 0.53 | 53.33 | $146\,720$ | $21\,512$ | $17\,560\,908$ | 0.59 | 60.00 | $203\,488$ | $16\,760$ | $31\,350\,348$
StandWalkJump | 40.00 | 0.49 | 50.00 | $200\,744$ | $93\,708$ | $59\,756\,631$ | 0.66 | 66.67 | $210\,240$ | $86\,216$ | $143\,958\,397$
DuckDuckGeese | – | 0.39 | 46.00 | $174\,460$ | $1\,453\,136$ | $34\,039\,926$ | 0.34 | 40.00 | $144\,272$ | $1\,452\,868$ | $14\,406\,184$
PhonemeSpectra | – | 0.21 | 21.42 | $215\,612$ | $15\,220$ | $8\,697\,204$ | 0.19 | 19.49 | $178\,176$ | $12\,440$ | $10\,222\,260$