
Generalization of the CASH Problem (REF )
Generalization for more flexible pipelines.
We can extend the problem formulation (REF ) to enable optimization
over the ordering of the functional modules. For example, we can choose between
`preprocessor \(\rightarrow \)  transformer \(\rightarrow \)  feature selector' OR `feature selector
\(\rightarrow \)  preprocessor \(\rightarrow \)  transformer'. The ordering of \(T \le N\)  modules can
be optimized by introducing \(T^2\)  Boolean variables \(\mathbf {o} = \lbrace  o_{ik}\colon i,k \in [T] \rbrace \) , where \(o_{ik} = 1\)  indicates that module \(i\)  is placed
at position \(k\) . The following constraints are then needed:

\(\sum _{k \in [T]} o_{ik} = 1, \forall i \in [T]\) , indicating that
module \(i\)  is placed at a single position, and

\(\sum _{i \in [T]} o_{ik} = 1 \forall k \in [T]\)  enforcing that only
one module is placed at position \(k\) .

These variables and constraints can be added to \(\mathbf {z}\)  in problem
(REF ) (\(\mathbf {z}= \lbrace  \mathbf {z}_1, \ldots , \mathbf {z}_N, \mathbf {o} \rbrace \) ). The resulting
formulation still obeys the generic form of (REF ), which as we will
demonstrate in the following section, can be efficiently solved by an operator
splitting framework like ADMM. We can also extend the above formulation to
allow the choice of multiple algorithms from the same module. Note that we
increase the combinatorial complexity of the problem as we extend the
formulation.

Artificial black-box objective
We want to devise an artificial black-box objective to study the behaviour of
the proposed schemes and baselines that matches the properties of the AutoML
problem (REF ) where

The same pipeline (the same algorithm choices \(\mathbf {z}\)  and the same
hyperparameters \(\theta \) ) always gets the same value.

The objective is not convex and possibly non-continuous.

The objective captures the conditional dependence between \(\mathbf {z}_i\)  and
\(\theta _{ij}\)  – the objective is only dependent on the hyper-parameters
\(\theta _{ij}\)  if the corresponding \(z_{ij} = 1\) .

Minor changes in the hyper-parameters \(\theta _{ij}\)  can cause only
small changes in the objective.

The output of module \(i\)  is dependent on its input from module \(i-1\) .

Novel artificial black-box objective.
To this end, we propose the following novel black-box objective that emulates
the structure of (REF ):

For each \((i,j), i \in [N], j \in [K_i]\) , we fix a weight vector
\(\mathbf {w}_{ij}\)  (each entry is a sample from \(\mathcal {N}(0,1)\) ) and a
seed \(s_{ij}\) .

We set \(f_0 = 0\) .

For each module \(i\) , we generate a value
\(v_i = \sum _{j} z_{ij} \left| \frac{\mathbf {w}_{ij}^\top \theta _{ij}}{\mathbf {1}^T \theta _{ij}} \right|\) 
which only depends
on the \(\theta _{ij}\)  corresponding to the \(z_{ij} = 1\) , and the
denominator ensures that the number (or range) of the hyper-parameters
does not bias the objective towards (or away from) any particular
algorithm.

We generate \(n\)  samples \(\lbrace  f_{i,1}, \ldots , f_{i,n} \rbrace  \sim \mathcal {N}(f_{i-1}, v_i)\)  with the fixed seed \(s_{ij}\) , ensuring that
the same value will be produced for the same pipeline.

\(f_i = \max \limits _{m = 1, \ldots , n} | f_{i,m} |\) .


Output \(f_N\)

The basic idea behind this objective is that, for each operator, we create a
random (but fixed) weight vector \(\mathbf {w}_{ij}\)  and take a weighted
normalized sum of the hyper-parameters \(\theta _{ij}\)  and use this sum as the
scale to sample from a normal distribution (with a fixed seed \(s_{ij}\) ) and pick
the maximum absolute of \(n\)  (say 10) samples. For the first module in the
pipeline, the mean of the distribution is \(f_0 = 0.0\) . For the subsequent
modules \(i\)  in the pipeline, the mean \(f_{i-1}\)  is the output of the previous
module \(i-1\) . This function possesses all the aforementioned properties of the
AutoML problem (REF ).
In black-box optimization with this objective, the black-box evaluations are
very cheap in contrast to the actual AutoML problem where the black-box
evaluation requires a significant computational effort (and hence
time). However, we utilize this artificial objective to evaluate the black box
optimization schemes when the computational costs are dominated by the actual
derivative-free optimization and not by the black-box evaluations.

ADMM Decomposition for (REF )
Introduction of continuous surrogate loss.
We begin by proposing a surrogate loss of problem (REF ), which can
be defined over the continuous domain. With \(\widetilde{\mathcal {D}}_{ij}\)  as
the continuous relaxation of the integer space \(\mathcal {D}_{ij}\)  (if
\(\mathcal {D}_{ij}\)  includes integers ranging from \(\lbrace l, \ldots , u \rbrace \subset \mathbb {Z}\) , then \(\widetilde{\mathcal {D}}_{ij} = [ l, u ] \subset \mathbb {R}\) ),
and \(\widetilde{\theta }^d\)  as the continuous surrogates for \(\theta ^d\)  with
\(\widetilde{\theta }_{ij} \in \widetilde{\mathcal {D}}_{ij}\)  (corresponding to \(\theta _{ij}\in \mathcal {D}_{ij}\) ), we utilize a surrogate loss function \(\widetilde{f}\)  for
problem (REF ) defined solely over the continuous domain with
respect to \(\theta \) :
\( \widetilde{f} \left(\mathbf {z}, \left\lbrace \theta ^c, \widetilde{\theta }^d \right\rbrace \right) \mathrel {\mathop :}=f\left(\mathbf {z}, \left\lbrace \theta ^c, \mathcal {P}_{\mathcal {D}} \left( \widetilde{\theta }^d \right)\right\rbrace  \right),\) 

where
\(\mathcal {P}_{\mathcal {D}} ( \widetilde{\theta }^d ) = \lbrace  \mathcal {P}_{\mathcal {D}_{ij}} (\widetilde{\theta }_{ij}^d ), \forall i \in [N], j \in [K_i] \rbrace \) 
is the projection of the continuous surrogates onto the integer set. This
projection is necessary since the black-box function is defined (hence
can only be evaluated) on the integer sets \(\mathcal {D}_{ij}\) s, not the
relaxed continuous set \(\widetilde{\mathcal {D}}_{ij}\) s. Note that this
projection and has an efficient closed form. Given the above definitions, we
have the following equivalent form of the problem (REF ):
\(\displaystyle \min _{\mathbf {z}, \theta ^c, \widetilde{\theta }^d, \delta }\widetilde{f} \left(\mathbf {z}, \left\lbrace \theta ^c, \widetilde{\theta }^d \right\rbrace \right) \operatornamewithlimits{\text{subject to}}\left\lbrace \begin{array}{l}\mathbf {z}_i \in \lbrace 0,1 \rbrace ^{K_i}, \mathbf {1}^{\top } \mathbf {z}_i = 1, \forall i \in [N] \\\theta _{ij}^c \in \mathcal {C}_{ij},\widetilde{\theta }_{ij}^d \in \widetilde{\mathcal {D}}_{ij},\forall i \in [ N ], j \in [ K_i ] \\\delta _{ij} \in \mathcal {D}_{ij}, \forall i \in [ N ], j \in [ K_i ] \\\widetilde{\theta }_{ij}^d = \delta _{ij}, \forall i \in [ N ], j \in [ K_i ],\end{array}\right.\) 

where the equivalence between problems (REF ) &
(REF ) is established by the equality constraint
\(\widetilde{\theta }_{ij}^d = \delta _{ij} \in \mathcal {D}_{ij}\) , implying
\(\mathcal {P}_{\mathcal {D}_{ij}} ( \widetilde{\theta }_{ij}^d )= \widetilde{\theta }_{ij}^d \in \mathcal {D}_{ij} \) 
and \(\widetilde{f} (\mathbf {z}, \lbrace \theta ^c, \widetilde{\theta }^d \rbrace  ) =f(\mathbf {z}, \lbrace \theta ^c, \widetilde{\theta }^d \rbrace  )\) ,
thereby making the objective functions in problems (REF ) and
(REF ) equal. We highlight that the introduction of the continuous
surrogate loss (REF ) is the key to efficiently
handling AutoML problems (REF ) by allowing us to perform
theoretically grounded operator splitting methods, e.g., ADMM, over mixed
continuous/integer hyper-parameters and integer model selection variables.

Operator splitting from ADMM.
Using the notation that \(I_\mathcal {X}(\mathbf {x}) = 0\)  if
\(\mathbf {x} \in \mathcal {X}\)  else \(+\infty \) , and defining the sets

\( \mathcal {Z} & = \left\lbrace \mathbf {z}\colon \mathbf {z}= \lbrace  \mathbf {z}_i \colon \mathbf {z}_i \in \lbrace 0,1 \rbrace ^{K_i},\mathbf {1}^{\top } \mathbf {z}_i = 1, \forall i \in [N] \rbrace \right\rbrace , \\ \mathcal {C} & = \left\lbrace \theta ^c \colon \theta ^c = \lbrace  \theta _{ij}^c \in \mathcal {C}_{ij}\forall i \in [N], j \in [K_i] \rbrace \right\rbrace , \\ \mathcal {D} & = \left\lbrace \delta \colon \delta = \lbrace  \delta \in \mathcal {D}_{ij}\forall i \in [N], j \in [K_i] \rbrace \right\rbrace , \\ \widetilde{\mathcal {D}} & = \left\lbrace \widetilde{\theta }^d \colon \widetilde{\theta }^d = \lbrace \widetilde{\theta }_{ij}^d \in \widetilde{\mathcal {D}}_{ij}\forall i \in [N], j \in [K_i] \rbrace \right\rbrace ,\) 


we can re-write problem (REF ) as

\( \displaystyle \min _{\mathbf {z}, \theta ^c, \widetilde{\theta }^d, \delta } \widetilde{f}\left(\mathbf {z}, \left\lbrace \theta ^c, \widetilde{\theta }^d \right\rbrace  \right)+ I_\mathcal {Z}(\mathbf {z}) + I_\mathcal {C}(\theta ^c)+ I_{\widetilde{\mathcal {D}}}(\widetilde{\theta }^d) + I_\mathcal {D}(\delta )\operatornamewithlimits{\text{subject to}}\ \ \widetilde{\theta }^d = \delta ,\) 


with the corresponding augmented Lagrangian function

\(\mathcal {L} & ( \mathbf {z}, \theta ^c, \widetilde{\theta }^d, \delta , \lambda ) \mathrel {\mathop :}=\\\nonumber & \widetilde{f} \left(\mathbf {z}, \left\lbrace \theta ^c, \widetilde{\theta }^d \right\rbrace \right) + I_\mathcal {Z}(\mathbf {z}) + I_\mathcal {C}(\theta ^c)+ I_{\widetilde{\mathcal {D}}}(\widetilde{\theta }^d) + I_\mathcal {D}(\delta )+ \lambda ^\top \left( \widetilde{\theta }^d - \delta \right)+ \frac{\rho }{2} \left\Vert  \widetilde{\theta }^d - \delta \right\Vert _2^2,\) 


where \(\lambda \)  is the Lagrangian multiplier, and \(\rho > 0\)  is a penalty
parameter for the augmented term.
ADMM [1]} alternatively minimizes the augmented
Lagrangian function (REF ) over two blocks of variables,
leading to an efficient operator splitting framework for nonlinear programs with
nonsmooth objective function and equality constraints. Hence
ADMM solves the original problem (REF ) when reformulated as problem
(REF ) with a sequence of easier sub-problems. Specifically, ADMM
solves problem (REF ) by alternatively minimizing (REF )
over variables \(\lbrace {\theta ^c}, {\widetilde{\theta }^d} \rbrace  \) , and
\(\lbrace  \delta , \mathbf {z} \rbrace  \) . This can be equivalently converted into
3 sub-problems over variables \(\lbrace {\theta ^c}, {\widetilde{\theta }^d}\rbrace \) ,
\(\delta \)  and \(\mathbf {z}\) , respectively. ADMM decomposes the
optimization variables into two blocks and alternatively minimizes the augmented
Lagrangian function (REF ) in the following manner at any ADMM
iteration \(t\) :

\(\left\lbrace  \theta ^c{}^{(t+1)}, \widetilde{\theta }^d{}^{(t+1)} \right\rbrace & = \operatornamewithlimits{arg\,min}_{\theta ^c, \widetilde{\theta }^d} \mathcal {L} \left(\mathbf {z}{}^{(t)}, \theta ^c, \widetilde{\theta }^d, \delta {}^{(t)},\lambda {}^{(t)}\right) \\ \left\lbrace  \delta {}^{(t+1)}, \mathbf {z}{}^{(t+1)} \right\rbrace & = \operatornamewithlimits{arg\,min}_{\delta , \mathbf {z}} \mathcal {L}\left(\mathbf {z}, \theta ^c{}^{(t+1)}, \widetilde{\theta }^d{}^{(t+1)}, \delta ,\lambda {}^{(t)}\right) \\ \lambda {}^{(t+1)} & =\lambda {}^{(t)} + \rho \left(\widetilde{\theta }^d{}^{(t+1)} - \delta {}^{(t+1)}\right).\) 


Problem (REF ) can be simplified by removing constant terms to get

\(\nonumber \left\lbrace  \theta ^c{}^{(t+1)}, \right.& \left. \widetilde{\theta }^d{}^{(t+1)} \right\rbrace  \\& = \operatornamewithlimits{arg\,min}_{\theta ^c, \widetilde{\theta }^d} \quad \widetilde{f} \left(\mathbf {z}{}^{(t)}, \left\lbrace \theta ^c, \widetilde{\theta }^d \right\rbrace \right) + I_\mathcal {C}(\theta ^c) + I_{\widetilde{\mathcal {D}}}(\widetilde{\theta }^d) \\\nonumber & \quad \quad \quad \quad \quad \quad + \lambda {}^{(t)}{}^\top \left( \widetilde{\theta }^d - \delta {}^{(t)} \right)+ \frac{\rho }{2} \left\Vert  \widetilde{\theta }^d - \delta {}^{(t)} \right\Vert _2^2, \\& = \operatornamewithlimits{arg\,min}_{\theta ^c, \widetilde{\theta }^d} \quad \widetilde{f} \left(\mathbf {z}{}^{(t)}, \left\lbrace \theta ^c, \widetilde{\theta }^d \right\rbrace \right) + I_\mathcal {C}(\theta ^c) + I_{\widetilde{\mathcal {D}}}(\widetilde{\theta }^d)+ \frac{\rho }{2} \left\Vert  \widetilde{\theta }^d - \mathbf {b} \right\Vert _2^2 \\\nonumber & \quad \quad \quad \quad \quad \quad \mbox{ where } \mathbf {b}= \delta {}^{(t)} - \frac{1}{\rho } \lambda {}^{(t)}.\) 


A similar treatment to problem () gives us

\( \left\lbrace  \delta {}^{(t+1)}, \mathbf {z}{}^{(t+1)} \right\rbrace & = \operatornamewithlimits{arg\,min}_{\delta , \mathbf {z}} \quad \widetilde{f} \left(\mathbf {z}, \left\lbrace \theta ^c{}^{(t+1)}, \widetilde{\theta }^d{}^{(t+1)}\right\rbrace  \right) + I_\mathcal {Z}(\mathbf {z}) \\\nonumber & \quad \quad \quad \quad \quad \quad + I_\mathcal {D}(\delta )+ \lambda {}^{(t)}{}^\top \left( \widetilde{\theta }^d{}^{(t+1)} - \delta \right)+ \frac{\rho }{2} \left\Vert  \widetilde{\theta }^d{}^{(t+1)} - \delta \right\Vert _2^2, \\ & = \operatornamewithlimits{arg\,min}_{\delta , \mathbf {z}} \quad \widetilde{f} \left(\mathbf {z}, \left\lbrace \theta ^c{}^{(t+1)}, \widetilde{\theta }^d{}^{(t+1)}\right\rbrace  \right) + I_\mathcal {Z}(\mathbf {z}) \\\nonumber & \quad \quad \quad \quad \quad + I_\mathcal {D}(\delta )+ \frac{\rho }{2} \left\Vert  \mathbf {a} - \delta \right\Vert _2^2\mbox{ where } \mathbf {a} =\widetilde{\theta }^d{}^{(t+1)} + \frac{1}{\rho } \lambda {}^{(t)}.\) 


This simplification exposes the independence between \(\mathbf {z}\)  and \(\delta \) ,
allowing us to solve problem () independently for \(\mathbf {z}\)  and
\(\delta \)  as:

\( \delta {}^{(t+1)} & = \operatornamewithlimits{arg\,min}_{\delta } \quad I_\mathcal {D}(\delta ) + \frac{\rho }{2}\left\Vert  \mathbf {a} - \delta \right\Vert _2^2 \mbox{ where }\mathbf {a} = \widetilde{\theta }^d{}^{(t+1)} + \frac{1}{\rho } \lambda {}^{(t)}, \\ \mathbf {z}{}^{(t+1)} & = \operatornamewithlimits{arg\,min}_\mathbf {z}\quad \widetilde{f} \left(\mathbf {z}, \left\lbrace \theta ^c{}^{(t+1)}, \widetilde{\theta }^d{}^{(t+1)}\right\rbrace  \right) + I_\mathcal {Z}(\mathbf {z}).\) 


So we are able to decompose problem (3) into problems (),
(REF ) and () which can be solved iteratively
along with the \(\lambda ^{(t)}\)  updates (see Table 1).

ADMM parameter sensitivity
The performance of ADMM is dependent on the choice of the penalty parameter
\(\rho > 0\)  for the augmented term in the augmented Lagrangian
(REF ). Figure REF  shows the
dependence of adaptive precision ADMM on \(\rho \)  with the artificial black-box
objective (Appendix ). The results indicate that adaptive
ADMM for CASH is fairly robust to the choice of \(\rho \) .
<FIGURE>
Empirical Evaluation of ADMM vs. JOPT on OpenML
data
We compare the performance of the adaptive precision ADMM with different
sub-problem solvers to JOPT(BO) (BO on the joint problem with all the variables)
on 8 OpenML [2]} binary classification data sets where we
optimize for the area under the ROC curve on 10% of the data as the validation
set. Both adaptive precision ADMM and JOPT(BO) are executed for 1 hour with 10
repetitions, and the incumbent objective is averaged over the 10
repetitions. All evaluations were run single-threaded on a 8 core 8GB CentOS
virtual machines. For each data set, we note the objective \(f_J\)  achieved by
JOPT(BO) at the end of 1 hour and note the time \(T_A\)  (in seconds) required by
adaptive precision ADMM to reach that objective. Then we also note the best
objective achieved by ADMM at the end of 1 hour \(f_A\) . The speedup \(S\)  for ADMM
is computed as \(S = \frac{3600}{T_A}\)  and the improvement (in %) \(I = 100 *\frac{f_J - f_A}{f_J}\) .
We consider two versions of adaptive precision ADMM – (i) using BO for both the
(REF ) and () to get AdADMM(BO,BO), and (ii) using
BO for the (REF ) and Combinatorial multi-armed bandits (Ba) for
the () to get AdADMM(BO,Ba). The improvements of ADMM over
JOPT(BO) are summarized in Table REF , indicating significant
speedup (over \(10\times \)  in most cases) and further improvement (over \(10\%\)  in
many cases).
Table REF  shows that between AdADMM(BO,BO) and
AdADMM(BO,Ba), the latter provides significantly higher speedups, but the
former provides higher additional improvement in the final objective. This
demonstrates ADMM's flexibility, for example, allowing choice between faster or
more improved solution.
<TABLE>
ADMM Decomposition for (REF ) with black-box
constraints
Without loss of generality, we assume that
\(\epsilon _m \ge 0\)  for \(m \in [M]\) . By introducing scalars
\(u_m \in [0, \epsilon _m]\) , we can reformulate the inequality constraint
(REF ) as the equality constraint together with a box constraint

\( g_m\left(\mathbf {z}, \left\lbrace  \theta ^c, \theta ^d \right\rbrace  \right)-\epsilon _m + u_m = 0, u_m \in [0, \epsilon _m],~ m \in [M].\) 

We then introduce a continuous surrogate black-box functions \(\widetilde{g}_m\) 
for \(g_m, \forall m \in [M]\)  in a similar manner to \(\widetilde{f}\)  given by
(REF ). Following the reformulation of
(REF ) that lends itself to the application of ADMM, the version
with black-box constraints (REF ) can be equivalently
transformed into

\( \displaystyle \min _{\mathbf {z}, \theta ^c, \widetilde{\theta }^d, \delta }\widetilde{f} \left(\mathbf {z}, \left\lbrace \theta ^c, \widetilde{\theta }^d \right\rbrace \right) \operatornamewithlimits{\text{subject to}}\left\lbrace  \begin{array}{l}\mathbf {z}_i \in \lbrace 0,1 \rbrace ^{K_i}, \mathbf {1}^{\top } \mathbf {z}_i = 1, \forall i \in [N] \\\theta _{ij}^c \in \mathcal {C}_{ij}, \widetilde{\theta }_{ij}^d \in \widetilde{\mathcal {D}}_{ij}, \forall i \in [ N ], j \in [ K_i ] \\\delta _{ij} \in \mathcal {D}_{ij}, \forall i \in [ N ], j \in [ K_i ] \\\widetilde{\theta }_{ij}^d = \delta _{ij}, \forall i \in [ N ], j \in [ K_i ] \\u_m \in [0, \epsilon _m], \forall m \in [M] \\\widetilde{g}_m \left(\mathbf {z}, \left\lbrace \theta ^c, \widetilde{\theta }^d \right\rbrace \right) - \epsilon _m + u_m = 0, \forall m \in [M].\end{array} \right.\) 

Compared to problem (REF ), the introduction of auxiliary variables
\(\lbrace  u_m\rbrace \)  enables ADMM to incorporate black-box equality constraints
as well as elementary white-box constraints.
Defining \(\mathcal {U} = \lbrace  \mathbf {u} \colon \mathbf {u} = \lbrace  u_m \in [0,\epsilon _m] \forall m \in [M] \rbrace  \rbrace \) , we can go through the mechanics of ADMM
to get the augmented Lagrangian with \(\lambda \)  and \(\mu _m \forall m \in [M]\)  as
the Lagrangian multipliers and \(\rho > 0\)  as the penalty parameter as follows:

\( \begin{split}\mathcal {L} & \left( \mathbf {z}, \theta ^c, \widetilde{\theta }^d, \delta , \mathbf {u}, \lambda ,\mu  \right) = \\& \widetilde{f} \left(\mathbf {z}, \left\lbrace \theta ^c, \widetilde{\theta }^d \right\rbrace \right) + I_\mathcal {Z}(\mathbf {z}) + I_\mathcal {C}(\theta ^c)+ I_{\widetilde{\mathcal {D}}}(\widetilde{\theta }^d) + I_\mathcal {D}(\delta )+ \lambda ^\top \left( \widetilde{\theta }^d - \delta \right)+ \frac{\rho }{2} \left\Vert  \widetilde{\theta }^d - \delta \right\Vert _2^2 \\& + I_\mathcal {U}(\mathbf {u}) + \sum _{i=1}^{M} \mu _m \left( \widetilde{g}_m \left(\mathbf {z}, \left\lbrace \theta ^c, \widetilde{\theta }^d \right\rbrace \right) - \epsilon _m + u_m \right) + \frac{\rho }{2} \sum _{i=1}^{M} \left(\widetilde{g}_m \left(\mathbf {z}, \left\lbrace \theta ^c, \widetilde{\theta }^d \right\rbrace \right) - \epsilon _m + u_m \right)^2.\end{split}\) 

ADMM decomposes the optimization variables into two blocks for alternate
minimization of the augmented Lagrangian in the following manner at any ADMM
iteration \(t\) 

\( \left\lbrace  \theta ^c{}^{(t+1)}, \widetilde{\theta }^d{}^{(t+1)},\mathbf {u}{}^{(t+1)}\right\rbrace  & = \operatornamewithlimits{arg\,min}_{\theta ^c, \widetilde{\theta }^d, \mathbf {u}}\mathcal {L}\left( \mathbf {z}{}^{(t)}, \theta ^c, \widetilde{\theta }^d, \delta {}^{(t)},\mathbf {u}, \lambda {}^{(t)}, \mu {}^{(t)} \right) \\ \left\lbrace  \delta {}^{(t+1)}, \mathbf {z}{}^{(t+1)} \right\rbrace & = \operatornamewithlimits{arg\,min}_{\delta , \mathbf {z}} \mathcal {L}\left(\mathbf {z}, \theta ^c{}^{(t+1)}, \widetilde{\theta }^d{}^{(t+1)}, \delta ,\mathbf {u}{}^{(t+1)}, \lambda {}^{(t)}, \mu {}^{(t)} \right) \\ \lambda {}^{(t+1)} & = \lambda {}^{(t)} + \rho \left(\widetilde{\theta }^d{}^{(t+1)} - \delta {}^{(t+1)} \right) \\ \forall m \in [M],\ \ \mu _m{}^{(t+1)} & = \mu _m{}^{(t)} +\rho \left( \widetilde{g}_m ( \mathbf {z}{}^{(t+1)}, \lbrace \theta ^c{}^{(t+1)},\widetilde{\theta }^d{}^{(t+1)} \rbrace  ) - \epsilon _m + u_m{}^{(t+1)}\right).\) 


Note that, unlike the unconstrained case, the update of the augmented Lagrangian
multiplier \(\mu _m\)  requires the evaluation of the black-box function for the
constraint \(g_m\) . Simplifying problem (REF ) gives us

\( \begin{split}\min _{\theta ^c, \widetilde{\theta }^d, \mathbf {u}} & \quad \widetilde{f} \left( \mathbf {z}{}^{(t)}, \left\lbrace \theta ^c, \widetilde{\theta }^d \right\rbrace  \right) \\& \quad \quad \quad + \frac{\rho }{2} \left[\left\Vert  \widetilde{\theta }^d - \mathbf {b} \right\Vert _2^2 + \sum _{i=1}^{M} \left[\widetilde{g}_m \left( \mathbf {z}{}^{(t)}, \left\lbrace \theta ^c, \widetilde{\theta }^d\right\rbrace  \right) - \epsilon _m + u_m +\frac{1}{\rho }\mu _m{}^{(t)} \right]^2 \right] \\& \operatornamewithlimits{\text{subject to}}\left\lbrace  \begin{array}{l}\theta _{ij}^c \in \mathcal {C}_{ij} \forall i \in [N], j \in [K_i],\\\widetilde{\theta }_{ij}^d \in \widetilde{\mathcal {D}}_{ij} \forall i \in [N], j\in [K_i], \\u_m \in [0, \epsilon _m],\end{array} \right. \mbox{ where } \mathbf {b} = \delta {}^{(t)} -\frac{1}{\rho } \lambda {}^{(t)},\end{split}\) 

which can be further split into active and inactive set of continuous variables
based on the \(\mathbf {z}{}^{(t)}\)  as in the solution of problem ()
(the \(\theta \) -min problem). The main difference from the unconstrained case in
problem () (the \(\theta \) -min problem) to note here is that
the black-box optimization with continuous variables now has \(M\)  new variables
\(u_m\)  (\(M\)  is the total number of black-box constraints) which are active in
every ADMM iteration. This problem (REF ) can be solved in the same
manner as problem () (\(\theta \) -min) using SMBO or TR-DFO
techniques.
Simplifying and utilizing the independence of \(\mathbf {z}\)  and \(\delta \) , we can split
problem () into the following problem for \(\delta \) 

\( \min _{ \delta } \quad \frac{\rho }{2} \Vert  \delta - {\mathbf {a}} \Vert _2^2 \quad \operatornamewithlimits{\text{subject to}}\delta _{ij} \in \mathcal {D}_{ij} \forall i \in [N], j \in [K_i]\mbox{ where } \mathbf {a} = \widetilde{\theta }^d{}^{(t+1)} + \frac{1}{\rho }\lambda {}^{(t)},\) 

which remains the same as problem (REF ) (the \(\delta \) -min
problem) in the unconstrained case, while the problem for \(\mathbf {z}\)  becomes

\( \begin{split}\min _\mathbf {z}& \quad \widetilde{f} (\mathbf {z}, \lbrace \theta ^c{}^{(t+1)},\widetilde{\theta }^d{}^{(t+1)} \rbrace  ) \\& \quad \quad \quad + \frac{\rho }{2} \sum _{i=1}^{M} \left[\widetilde{g}_m ( \mathbf {z}, \lbrace \theta ^c{}^{(t+1)}, \widetilde{\theta }^d{}^{(t+1)} \rbrace ) - \epsilon _m + u_m{}^{(t+1)} + \frac{1}{\rho }\mu _m{}^{(t)} \right]^2 \\& \operatornamewithlimits{\text{subject to}}\mathbf {z}_i \in \lbrace 0,1 \rbrace ^{K_i}, \mathbf {1}^{\top } \mathbf {z}_i = 1, \forall i \in [N].\end{split}\) 

The problem for \(\mathbf {z}\)  is still a black-box integer programming problem, but now
with an updated black-box function and can be handled with techniques proposed
for the combinatorial problem () in the absence of black-box
constraints (the \(\mathbf {z}\) -min problem).
