\label{eq first to conclude}
\end{align}

\begin{align*}
A_M &:=  \sum_{m=1}^{\floor{M/2}} \exp\left( {4} \frac{{\alpha}_{K}}{\beta_{K}} \frac{\gamma}{1-\rho}\set{ m^{1-\rho} - M^{1-\rho} } \right)\frac{\gamma^2}{m^{2 \rho}},
\\
B_M &:=  \sum_{m=\floor{M/2}+1}^{M-1} \exp\left( {4} \frac{{\alpha}_{K}}{\beta_{K}} \frac{\gamma}{1-\rho}\set{ m^{1-\rho} - M^{1-\rho} } \right)\frac{\gamma^2}{m^{2 \rho}}.
\end{align*}

For the first term $A_M$, we observe that, for $m \le \floor{M/2} \le M/2$ and $\frac12<\rho<1$,

\begin{align}
m^{1-\rho} - M^{1-\rho} \le - \frac{\sqrt{2}}{2} \ln(2) (1-\rho)M^{1-\rho}\;.
\end{align}

We then compute

\begin{align}
A_M &\le  \exp\left(- 2\sqrt{2}\ln(2) \gamma \frac{{\alpha}_{K}}{\beta_{K}} M^{1-\rho}  \right) \sum_{m=1}^{\floor{M/2}} \frac{\gamma^2}{m^{2 \rho}} \nonumber
\\
&\le  C_{\rho, \gamma}  \exp\left(- 2\sqrt{2}\ln(2) \gamma \frac{{\alpha}_{K}}{\beta_{K}} M^{1-\rho}  \right). \label{eq upper bound A}
\end{align}

We now study the term $B_M$ which reads

\begin{align*}
B_M = \gamma^2 \exp\left( - {4} \frac{{\alpha}_{K}}{\beta_{K}} \frac{\gamma}{1-\rho} M^{1-\rho}  \right)  \sum_{m=\floor{M/2}+1}^{M-1}\lambda(m)
\end{align*}

where, the map $\lambda$ is defined for $x \ge 1$ by

\begin{align}
\lambda(x) := \exp\left(  {4} \frac{{\alpha}_{K}}{\beta_{K}} \frac{\gamma}{1-\rho} x^{1-\rho}  \right)\frac{1}{x^{2 \rho}}.
\end{align}

We observe that $\lambda$ is increasing on $[\floor{M/2}+1,+\infty)$ when  (<ref>) holds. This leads to

\begin{align*}
\sum_{m=\floor{M/2}+1}^{M-1}\lambda(m) &\le \int_{M/2}^{M} \lambda(x) \ud x\\
& \leq \frac{2^\rho}{M^{\rho}} \int_{M/2}^{M} \exp\left(  {4} \frac{{\alpha}_{K}}{\beta_{K}} \frac{\gamma}{1-\rho} x^{1-\rho}  \right)\frac{1}{x^{\rho}} \ud x
\\
&\le  \frac{ 2^{\rho-  {2} } \beta_{K}}{\gamma{M^\rho \alpha}_{K}}
\exp\left(  {4} \frac{{\alpha}_{K}}{\beta_{K}} \frac{\gamma}{1-\rho} M^{1-\rho}  \right)
\end{align*}

which in turn yields
$ B_M \le  \frac{ \gamma\beta_{K}}{M^\rho \alpha_{K}}.$

Inserting the previous inequality and estimate (<ref>) into (<ref>) concludes the proof,  since $\mathbb{E}\Big[  |\mathfrak{u}_{0}|^2\Big] < \infty$, recall Definition <ref>, step 1. and  $\frac{\alpha_K}{\beta_K} \le 1$ recall Assumption <ref> and (<ref>).

Let us importantly point out that if one choses $\gamma_{m}= \gamma /m$, with $\gamma>0$, then from standard comparison between series and integral $\Gamma_{m} - \Gamma_M \leq \gamma (\ln(m/M)+1)$ so that repeating the computations of the proof of Lemma <ref>, one has to consider the two disjoint cases $\gamma < \frac{\beta_K}{4\alpha_K}$ and $\gamma > \frac{\beta_K}{4\alpha_K}$ in order to provide an upper bound for the quantity of interest $L_{K, M}$. Only the latter allows to obtain the best convergence rate of order $1/M$. However, in practice, the user does not know the exact value of $\frac{\beta_{K}}{4\alpha_{K}}$ so that one will often consider higher values of $\gamma$ than requested which will have the undesirable effect to deteriorate the upper-bound as suggested by the value of $\varrho_1$ in (<ref>). Moreover, as shown in Section <ref>, the value $\frac{\beta_{K}}{4\alpha_{K}}$ actually goes to infinity when the prescribed approximation error $\varepsilon$ goes to zero so that the latter condition becomes more and more stringent.

We now give an upper bound for the error $\cE_P$ defined by (<ref>), with respect to all the algorithm's parameters. These parameters will be chosen in the next section taking into account the precise specification of the functional approximation space.

Suppose that Assumption <ref>, Assumption <ref> (i), (ii) and Assumption <ref> hold. Assume that there exists a positive constant $\eta$ (independent of $N$, $M$ and the basis functions $(\psi)$) such that

\begin{align}\label{eq ass cs control global}
\frac{\kappa_{K}}{h \wedge \alpha_K } L_{K,M}  \le \eta \;.
\end{align}

If $T(1+ 2L^2(1+ h)) < 1$ and
$\delta_{h,\eta}:=\frac{ 16L^2 T (1+\eta)}{1-T(1+ 2L^2(1+ h))} < 1$, then for any $\varepsilon>0$ there exists a positive constant $C_\varepsilon$ such that

\cE_{\mathrm{RM}} \leq C_\varepsilon \frac{\kappa_{K}}{h \wedge \alpha_K } L_{K,M} $$

so that, with the notations of Proposition <ref>, it holds

\begin{align}\label{global:control:error}
\cE_P \le \delta_{h, \varepsilon}^P \cE_0 + C_\varepsilon \left(
\frac{\kappa_{K}}{h \wedge \alpha_K } L_{K,M}  + \cE_{\psi} +  \cE_{\pi} \right).
\end{align}

In practice, $\eta$ will be fixed to be a small constant as the term in the left hand side of (<ref>) should be asymptotically zero.

Proof of Proposition <ref>.

Step 1: From Proposition <ref>, we see that to obtain (<ref>), it remains to control

\begin{align*}
\cE_{\mathrm{RM}} =\max_{1 \le p \le P} \esp{\vvvert \Phi_M(\mathfrak{u}^{p-1}_M) - \Phi(\mathfrak{u}^{p-1}_M)\vvvert^2}.
\end{align*}

Using Lemma <ref>, we have

\begin{align}\label{eq  robbins-monro here}
\esp{\vvvert \Phi_M(\mathfrak{u}^{p-1}_M) - \Phi(\mathfrak{u}^{p-1}_M)\vvvert^2}
\le
\kappa_{K} L_{K,M}(1
+  d N )
+ \frac{\kappa_{K}}{\alpha_{K}} L_{K,M} \esp{\vvvert \Phi(\mathfrak{u}^{p-1}_M) \vvvert^2}.
\end{align}

To conclude the proof, we will in the next step, provide an  upper bound for the term $\esp{\vvvert \Phi(\mathfrak{u}^{p-1}_M) \vvvert^2}$, uniformly with respect to $p$.

Step 2: We denote by $C_\varepsilon$ a constant that may change from line to line along with $\varepsilon$.

From Young's inequality and Lemma <ref>, we obtain

\begin{align*}
\esp{\vvvert \Phi(\mathfrak{u}^p_{M}) \vvvert^2}
(1+\varepsilon) \esp{\vvvert \Phi(\mathfrak{u}^p_{M}) - \bar{\mathfrak{u}}\vvvert^2} + (1+\frac{1}{\varepsilon}) \vvvert \bar{\mathfrak{u}}\vvvert^2
\\
&\le \delta_{h}(1+\varepsilon)  \esp{\vvvert \mathfrak{u}^p_{M} -  \bar{\mathfrak{u}} \vvvert^2} + C_\varepsilon(\cE_\pi + \cE_{\psi}+\vvvert \bar{\mathfrak{u}}\vvvert^2)
\\
&\le \delta_{h}(1+\varepsilon) \esp{\vvvert \mathfrak{u}^p_{M}\vvvert^2}
+ C_\varepsilon(\cE_\pi + \cE_{\psi}+\vvvert \bar{\mathfrak{u}}\vvvert^2)
\end{align*}

up to a modification of $\varepsilon$. From the previous inequality, we readily obtain $ \esp{\vvvert \Phi(\mathfrak{u}^0_{M}) \vvvert^2} \leq C_\varepsilon$. Now, if $p$ is a positive integer, noting again that

\esp{\vvvert \mathfrak{u}^p_{M}\vvvert^2}
\le 2\esp{\vvvert\Phi_M(\mathfrak{u}^{p-1}_{M}) - \Phi(\mathfrak{u}^{p-1}_{M})\vvvert^2}
+ 2 \esp{\vvvert \Phi(\mathfrak{u}^{p-1}_{M})\vvvert^2}

we obtain

\begin{align*}
%\label{eq interm bound unif}
\esp{\vvvert \Phi(\mathfrak{u}^p_{M}) \vvvert^2}
\le
2\delta_{h}(1+\varepsilon)\esp{\vvvert  \Phi(\mathfrak{u}^{p-1}_{M}) \vvvert^2} &+ 2  \delta_{h}(1+\varepsilon) \esp{\vvvert\Phi_{M}(\mathfrak{u}^{p-1}_{M}) - \Phi(\mathfrak{u}^{p-1}_{M})\vvvert^2}
\\
&+C_\varepsilon \bigg( \cE_\pi + \cE_{\psi}+\vvvert \bar{\mathfrak{u}}\vvvert^2\bigg)
\end{align*}

so that using (<ref>), we get

\begin{align*}
%\label{eq bound unif almost final}
\esp{\vvvert \Phi(\mathfrak{u}^p_{M}) \vvvert^2}
\le&
2\delta_{h}(1+\varepsilon)\left(1+\frac{\kappa_{K}}{\alpha_{K}} L_{K,M}\right) \esp{\vvvert  \Phi(\mathfrak{u}^{p-1}_{M}) \vvvert^2}
\\
&+ 2  \delta_{h}(1+\varepsilon)  \kappa_{K} L_{K,M}\left(1+ d N  \right)
+C_\varepsilon \bigg( \cE_\pi + \cE_{\psi}+\vvvert \bar{\mathfrak{u}}\vvvert^2\bigg)\;.
\end{align*}

From (<ref>) and the fact that $\delta_{h, \eta}$, we can set $\varepsilon$ such that $2\delta_{h}(1+\varepsilon)(1+\frac{\kappa_{K}}{\alpha_{K}} L_{K,M}) \le \delta_{h,\eta} (1+\varepsilon)<1$ so that from the above inequality, by induction, for any positive integer $p$, we get

\begin{align*}
\esp{\vvvert \Phi(\mathfrak{u}^p_{M}) \vvvert^2} \le   (\delta_{h,\eta}(1+\varepsilon))^{p}\esp{\vvvert \Phi(\mathfrak{u}^0_{M}) \vvvert^2}+ C_\varepsilon(\cE_\pi + \cE_{\psi}+\vvvert \bar{\mathfrak{u}}\vvvert^2 + \delta_h) \le C_\varepsilon\;,
\end{align*}

which concludes the proof.

We now have all the ingredients to give the proof of the main result announced in Section <ref> on the upper bound for the global convergence error at the initial time.

Proof of Theorem <ref> From the very definition (<ref>) of the global error, we deduce

\begin{align}\label{eq start decompose}
\cE_{\mathrm{MSE}} \le 2\esp{|u(0,\cX_0) - \bar{u}(\cX_0)|^2 + |Y^{\bar{\mathfrak{u}}}_0 - Y^{\mathfrak{u}^P_M}_0|^2}
\end{align}

where we used the notations introduced in (<ref>), (<ref>) and (<ref>). A fortiori, we have

\begin{align} \label{eq interm step decompose}
\esp{|u(0,\cX_0) - \bar{u}_0(\cX_0)|^2} \le \cE_\psi \quad \text{ and } \quad
\esp{|Y^{\bar{\mathfrak{u}}}_0 - Y^{\mathfrak{u}^P_M}_0|^2} \le \cE_P
\end{align}

recalling (<ref>), (<ref>) and (<ref>). Combining (<ref>) and (<ref>) yields

\begin{align}
\cE_{\mathrm{MSE}}  \le 2 \left( \cE_\psi  + \cE_P \right)\,.
\end{align}

We eventually conclude the proof by invoking Proposition <ref> together with Lemma <ref>.

§.§ Convergence  and complexity analysis for sparse grid approximations

For this part, we work in the setting of Section <ref>. Our goal is to prove the theoretical upper-bound on the algorithm's complexity stated in Theorem <ref>.

We first state the following useful estimate.

Suppose that Assumption <ref> is satisfied. Let $\phi:\R^d \rightarrow \R$ be a non-negative measurable function whose support is included in $\cO$ and $\widecheck{\phi}$ be its $1$-periodisation defined by (<ref>). Then, it holds

\begin{align*}
\mathfrak{C}^{-1}\esp{\phi(U)} \le \esp{\widecheck{\phi}(X_{t_n})} = \esp{\phi(\widehat{X}_{t_n})} \le \mathfrak{C} \esp{\phi(U)}
\end{align*}

where $U$ has law $\cU((0,1)^d)$ and $\mathfrak{C}$ is given in Lemma <ref>.

We denote by $x' \mapsto p_X(t_n, x')$ the density function of $X_{t_n}$ given by the Euler-Maruyama scheme taken at time $t_n$ and starting from $\cX_0$ with  law $\cU((0,1)^d)$ at time $0$. Note that we have
$p_X(t_n,x') = \int p^{\pi}(0, t_n, x, x') \1_{(0,1)^d}(x) \ud x $ and using

\begin{align*}
\mathfrak{C}^{-1} \int p(\mathfrak{c} t_n, x - x')\1_{(0,1)^d}(x) \ud x  \leq p_X(t_n,x') \leq \mathfrak{C} \int p(\mathfrak{c} ^{-1}t_n, x'-x) \1_{(0,1)^d}(x) \ud x \,.
\end{align*}

\begin{align*}
\esp{\phi(\widehat{X}_{t_n})} &= \esp{\widecheck{\phi}(X_{t_n})}  \ge \mathfrak{C}^{-1} \int \widecheck{\phi}(x')\int p(\mathfrak{c}  t_n, x - x')\1_{(0,1)^d}(x)\ud x \ud x'
\end{align*}

so that introducing the notation $\Xi = \xi + W_{ \mathfrak{c}  t_n}$,

\begin{align}
\int \widecheck{\phi}(x')\int p(\mathfrak{c}  t_n, x - x')\1_{(0,1)^d}(x)\ud x \ud x' &= \esp{\widecheck{\phi}(\Xi)}
= \esp{{\phi}(\widehat{ \Xi})}
\end{align}

The proof is then concluded by observing that $\cL(\widehat{\Xi}) = \cL(U)$. The proof of the upper-bound follows from similar arguments.

§.§.§ Sparse grid approximation error

We now provide some upper-bound estimates for the sparse grid approximation error.

Under Assumption <ref>, there exists a positive constant $C:=C(T, b, \sigma, d, \lambda_0)$ such that

\begin{align}
\cE_{\psi} \le C 2^{-4\ell} \ell^{d-1}.
\end{align}

To obtain an error of order $\varepsilon^2$ for the quantity $\cE_{\psi}$ one may thus set $\ell_\varepsilon = \log_2(\varepsilon^{-\frac12}|\log_2(\varepsilon)|^{\frac{d-1}{ 4 }})$ so that, for each $n=1, \cdots, N-1$, the number of basis functions required satisfies

\begin{align*}
K_\varepsilon = \varepsilon^{-\frac12}|\log_2(\varepsilon)|^{  \frac{5(d-1)}4 }.
\end{align*}

For $1 \le i \le d$, $n=0, \cdots, N-1$, setting $v_i(t_n, x) = (\sigma^{\top}\nabla_x u)_i(t_n, x)\1_{\set{x \in \cO}}$, $x \in \mathbb{R}^d$, from (<ref>) we have

\begin{align}\label{eq bound hmix}
\|u\|_{H^{k}_{mix}(\mathcal{O})} + \max_{1 \le i \le d}\|v_i\|_{H^{k}_{mix}(\mathcal{O})} \le C.
\end{align}

Moreover, from (<ref>), we obtain

\begin{align*}
(\sigma^\top\nabla_x u)_i(t_n,X_{t_n}) = v_i(t_n, \widehat{X}_{t_n})\,,
\end{align*}

\begin{align*}
\esp{|(\sigma^\top\nabla_x u)(t_n,X_{t_n})-Z^{\mathfrak{u}}_{t_n}|^2} & =  \sum_{i=1}^d  \esp{\Big|v_i(t_n, \widehat{X}_{t_n}) - \sum_{k=1}^{K}\mathfrak{z}^{n, k}_i \psi^{k}_{n}(\widehat{X}_{t_n})\Big|^2}
\\
&\le \mathfrak{C} \sum_{i=1}^d  \esp{\Big|v_i(t_n, U) - \sum_{k=1}^{K}\mathfrak{z}^{n, k}_i \psi^{k}_{n}(U)\Big|^2}
\end{align*}

with $U\sim \mathcal{U}((0,1)^d)$ and where we use the upper-estimate given in Lemma <ref> to obtain the last inequality.
We also recall that

\begin{align}
\esp{|u(0,\cX_0)-Y^{\mathfrak{u}}_0|^2} = \esp{|u(0,U) - \sum_{k=1}^{K}\mathfrak{y}^k \psi^k_y(U)|^2} \,.
\end{align}

From (<ref>) and the previous estimates, we thus deduce

\begin{align}
\cE_{\psi}  &\le C\left(
\inf_{\xi \in \mathscr{V}^y} \|\xi-u(0, .)\|^2_{L^2(\cO)}
\max_{0 \le n \le N-1}
\sum_{i=1}^d\inf_{\xi \in \mathscr{V}^z_n} \|\xi-v_{i}(t_n, .)\|^2_{L^2(\cO)}
\right) \,,
\nonumber \\
%  C \max_{1 \le n \le N-1} 2^{-4\ell} \ell^{d-1}
%  \sum_{\mathbf{j}\in \mathbf{J}^\infty_{d,2}}
%a^{2|\mathbf{j}|_1+d} \sum_{i=1}^d|D^{\mathbf{j}}v_i^n(t_n, .)|^2_\infty \nonumber \\
%  C (1\vee a)^{5d}\max_{1 \le n \le N-1} 2^{-4\ell } \ell^{d-1}
%  \sum_{\mathbf{j}\in \mathbf{J}^\infty_{d,2}}
% \sum_{i=1}^d|D^{\mathbf{j}}v_i^n(t_n,.)|^2_\infty \nonumber \\
& \leq C 2^{-4\ell} \ell^{d-1}, \label{eq control A1}
\end{align}

where for the last inequality we used (<ref>) and (<ref>).

Finally, setting $\ell_\varepsilon = \log_2(\varepsilon^{-\frac12}|\log_2(\varepsilon)|^{\frac{d-1}{ \textcolor{black}{4} }})$ yields $\cE_\psi = O(\varepsilon^2)$ as $\varepsilon \downarrow 0$
and from (<ref>) (see also Remark <ref>) we deduce that in this case
$K_\varepsilon = \varepsilon^{-\frac12}|\log_2(\varepsilon)|^{  \frac{5(d-1)}4 }$.

§.§.§ Norm equivalence constants

We now provide some estimates for the value of $\alpha_{K}$ and $\kappa_{K}$ appearing in Assumption <ref>.
Suppose that Assumption <ref> holds.

In the setting of Section <ref>, there exists a constant $\mathfrak{k} \leq 1$ such that

\begin{align*}
\mathfrak{k} =  \alpha_{K} = \frac1{\kappa_{K}} \;.% \le \bar{C}
\end{align*}

For any $\mathfrak{u} = (\mathfrak{y}, \mathfrak{z}) \in \R^{K^y} \times \R^{d \bar{K}^z}$, any $0 \le n \le N-1$ and any $l \in \left\{1, \cdots, d\right\}$, from (<ref>) we have

\begin{align*}
\esp{|(Z^{\mathfrak{u}}_{t_n})^l|^2}
= \esp{\Big| \sum_{k = 1}^{K} \mathfrak{z}^{n, k}_l  \psi^{k}_n(\widehat{X}_{t_n})\Big|^2}\,,
\end{align*}

Using Lemma <ref>, we obtain

\begin{align}\label{eq encadrement 1}
\mathfrak{C}^{-1}\esp{\Big| \sum_{k = 1}^{K} \mathfrak{z}^{n, k}_l  \psi^{k}_n(U)\Big|^2}
\le
\esp{|(Z^{\mathfrak{u}}_{t_n})^l |^2}
\le
\mathfrak{C}\esp{\Big| \sum_{k = 1}^{K} \mathfrak{z}^{n, k}_l  \psi^{k}_n(U)\Big|^2}\;.
\end{align}

Note that in our setting, $\psi_{n}^{k} = \chi^k$, so it holds

\begin{align}
\int_{\cO}\Big|\sum_{k = 1}^{K} \mathfrak{z}^{n, k}_l  \psi_{n}^{k}(z)\Big|^2
\ud z &= \int_{\cO}\Big|\sum_{k = 1}^{K} \mathfrak{z}^{n, k}_l  \chi^{k}(x)\Big|^2
\ud x\;. \label{eq min z 2}
\end{align}

Since the basis functions $(\chi^k)_{1 \le k \le K}$ forms a Riesz basis [29], there exists a constant $\underline{c}\geq 1$ such that it holds

\begin{align}
\underline{c}^{-1} \sum_{k = 1}^{K} |\mathfrak{z}^{n, k}_l |^2  \le
\int_{[0, 1]^d}\Big|\sum_{k = 1}^{K} \mathfrak{z}^{n, k}_l  \chi^{k}(x)\Big|^2 \ud x
\le \underline{c}
\sum_{k = 1}^{K} |\mathfrak{z}^{n, k}_l |^2
\label{eq min z 3}
\end{align}

Combining (<ref>)-(<ref>)-(<ref>) and taking into account all the component of $Z^{\mathfrak{u}}_{t_n}$, we compute

\begin{align}\label{eq conclusion for z}
\underline{c}^{-1} \mathfrak{C}^{-1} d \sum_{k=1}^{K}  |\mathfrak{z}^{n, k}_l |^2  \le
\esp{|(Z^{\mathfrak{u}}_{t_n}) |^2}
\le \underline{c}  \mathfrak{C} d \sum_{k=1}^{K} |\mathfrak{z}^{n, k}_l |^2 \;.
\end{align}

We also observe that

\begin{align}
\esp{|Y^{\mathfrak{u}}_0|^2}
= \esp{\Big| \sum_{k = 1}^{K} \mathfrak{y}^{k}  \chi^{k}(\cX_0)\Big|^2}\,.
\end{align}

Since $\cX_0 \sim \cU((0,1)^d)$, we similarly deduce that

\begin{align}
\underline{c}^{-1} \sum_{k = 1}^{K} |\mathfrak{y}^{n, k}_l |^2  \le
\esp{|Y^{\mathfrak{u}}_0|^2}
\le \underline{c}
\sum_{k = 1}^{K} |\mathfrak{y}^{n, k}_l |^2.
\label{eq conclusion y}
\end{align}

The proof is concluded by combining (<ref>) and (<ref>) with (<ref>) and setting $\mathfrak{k} = \underline{c}^{-1} \mathfrak{C}^{-1}d^{-1}$.

§.§.§ Complexity analysis

Under Assumption <ref>, one can set

\begin{align}
\beta_{K} = C_d(1+  2^\ell \ell^{d - 1})
\end{align}

for some positive constant $C_d$ which depends on the PDE dimension $d$.

Step 1:  For any $n \in \set{0,\dots,N-1}$, any $\ell \in \set{1,\dots,d}$, one has

\begin{align}
\esp{|\tilde{\omega}^{n,\cdot}_\ell |^4}  &= \esp{\left(\sum_{k=1}^{K} |\tilde{\omega}^{n,k}_\ell|^2\right)^2} \,.
%&\le 2\left(1 + \esp{(\sum_{n=0}^{N-1}\sum_{k=1}^{K_n} ||\omega_n^k||^2 )^2 }\right)
\end{align}

Using Jensen's inequality, we obtain

\begin{align}
\esp{|\tilde{\omega}^{n,\cdot}_\ell |^4}  &\le K \esp{\sum_{k=1}^{K} |\tilde{\omega}^{n,k}_\ell|^4}  \le 3 {d^2}K  \sum_{k=1}^{K} \esp{|\psi_{n}^{k}(\widehat{X}_{t_n})|^4} \;. \label{eq first majo}
\end{align}

From now on, we use the indexation related to the sparse grid description introduced in Remark <ref>, namely, we write

\begin{align}\label{eq start majo}
\sum_{k=1}^{K}  \esp{|\psi_{n}^{k}(\widehat{X}_{t_n})|^4} &= \sum_{(\mathbf{l},\mathbf{i}) \in \cC}\esp{|\psi_{n}^{(\mathbf{l},\mathbf{i})}(\widehat{X}_{t_n})|^4 }
%&\le C_d \sum_{(\mathbf{l},\mathbf{i}) \in \cC_n} 2^{2|\mathbf{l}|_1}
\\
&= \sum_{(\mathbf{l},\mathbf{i}) \in \cC}\esp{|\chi^{(\mathbf{l},\mathbf{i})}(\widehat{X}_{t_n})|^4 }
\end{align}

in our setting.

Step 2:

Using Lemma <ref>, we observe

\begin{align}\label{eq control beta interm 1}
\esp{|\chi^{(\mathbf{l},\mathbf{i})}(\widehat{X}_{t_n})|^4 }  &\le \mathfrak{C}
\esp{|\chi^{(\mathbf{l},\mathbf{i})}(U)|^4}\;.
%\esp{|\chi^{(\mathbf{l},\mathbf{i})}(\tau_n(U)|^4 }
%\nonumber \\
%&=  \esp{\prod_{j=1}^d |\chi^{({l}_j,{i}_j)}(\tau^j_n(X^{x_0}_{t_n}))|^4 } \nonumber \\
%& = \int_{\mathbb{R}^d} \prod_{j=1}^d  |\chi^{({l}_j,{i}_j)}(\tau^j_n(x))|^4 \, p^{\pi}(0, t_n, x_0, x) \, dx \label{eq dim d}
\end{align}

Moreover, we compute

\begin{align*}
\int |\phi^{(l,i)}(x)|^4 \ud x = \int |\phi(2^l x - i)|^4 \ud x \le C 2^{-l}
\end{align*}

and from the definition of $\chi^{(l_j,i_j)}$, we deduce

\begin{align*}
\int |\chi^{({l}_j,{i}_j)}(x)|^4 \ud x \le C 2^{l} \;.
\end{align*}

Combining the previous inequality with  (<ref>) leads to

\begin{align*}
\esp{|\chi^{(\mathbf{l},\mathbf{i})}(\widehat{X}_{t_n})|^4 }  \leq {C} 2^{|\mathbf{l}|_1}\;
\end{align*}

and inserting the previous estimate in (<ref>) yields

\begin{align} \label{eq first step 3}
\sum_{k=1}^{K}  \esp{|\psi_{n}^{k}(\widehat{X}_{t_n})|^4} &\le {C} \sum_{(\mathbf{l},\mathbf{i}) \in \cC} 2^{|\mathbf{l}|_1}.
\end{align}

Step 3:  We now quantify the term appearing in the right-hand side of (<ref>), namely

\begin{align}
Q :=  \sum_{(\mathbf{l},\mathbf{i}) \in \cC} 2^{|\mathbf{l}|_1}
= 1 + \sum_{k=1}^\ell \sum_{\mathbf{l} \in \mathbb{N}^d} 2^{|\mathbf{l}|_1}\1_{\set{\zeta_d(\mathbf{l})=k}}\;.
\end{align}

We denote by $\| \mathbf{l} \|_0 = |\set{j|l_j = 0}|$. For $\mathbf{l} \neq \mathbf{0}$,
recall that $\zeta_d(\mathbf{l}) = |\mathbf{l}|_1 + \|\mathbf{l}\|_0 -(d-1)$ (from the definition of $\zeta_d$). Thus,

\begin{align*}
Q &= 1 + \sum_{k=1}^\ell
\sum_{q=0}^{d-1}
\sum_{\mathbf{l} \in (\mathbb{N}_{>0})^{d-q}}
2^{|\mathbf{l}|_1}\1_{\set{|\mathbf{l}|_1=k+ d-1 -q  \text{ and } \|\mathbf{l}\|_0 = q } }
\\
&= 1 + \sum_{k=1}^\ell \sum_{q=0}^{d-1} 2^{k+ d-1-q} \mathrm{C}_{k + d-q-2}^{d-q-1}
\mathrm{C}_d^q
\end{align*}

recall that $|\set{ \mathbf{l} \in (\mathbb{N}_{>0})^{d-q} \,| \,|\mathbf{l}|_1=k+ d-1 -q}| =\mathrm{C}_{k + d-q-2}^{d-q-1} $.
Introducing $\theta = d-1-q$, we get

\begin{align}
Q = 1 + \sum_{k=1}^\ell d2^k + \sum_{\theta = 1}^{d-1} 2^{1+\theta} \mathrm{C}^{d-1 - \theta}_{d} \sum_{k=1}^\ell 2^{k-1} \mathrm{C}_{k-1+\theta}^{\theta}
\end{align}

From Lemma 3.6 in [12], we know that $\sum_{k=1}^\ell 2^{k-1} \mathrm{C}_{k-1+\theta}^{\theta} = 2^\ell(\frac{\ell^\theta}{\theta!} + O_d(\ell^{\theta-1}))$. We thus obtain

\begin{align*}
Q = 2^\ell\left(\frac{2^d}{(d-1)!}\ell^{d-1} + O_d(\ell^{d-2})\right)
\end{align*}

which combined with (<ref>) yields

\begin{align} \label{eq last step 3}
\sum_{k=1}^{K}  \esp{|\psi_{n}^{k}(\widehat{X}_{t_n})|^4} \le C_d 2^\ell \ell^{d-1}.
\end{align}

Combining the previous inequality with (<ref>), we obtain

\begin{align}
\esp{|\tilde{\omega}^{n,\cdot}_\ell|^4} \le C_d 2^{2\ell} \ell^{2d-2}\;.
\end{align}

Using similar arguments, as the basis function are chosen to be the same in our setting, we also have

\begin{align*}
\esp{|\theta|^4} \le C_d 2^{2\ell} \ell^{2d-2}\;.
\end{align*}

The proof is then concluded recalling the definition of $\beta_{K}$ in (<ref>).

We now turn to the analysis of the convergence and complexity of the full Picard algorithm. The following corollary is a preparatory result and expresses the main convergence results in terms of the parameters $P$, $M$, $\ell$ and $h$.

Suppose that Assumption <ref> as well as (<ref>) and (<ref>)  hold. Set $\gamma_m = \gamma/ m^{\rho}$, for some $\rho \in (1/2, 1)$ and $\gamma > 0$. If $T(1+ 2L^2(1+ h)) < 1$ and $\delta_{h,\eta}=\frac{16L^2 T (1+2\eta)}{1-T(1+ 2L^2(1+ h))} < 1$, then, with the notations of Proposition <ref>, for any $\varepsilon>0$ such that $\delta_{h, \varepsilon}:= \delta_{h, \eta } (1+\varepsilon)<1$ there exist constants $C_\varepsilon:=C(\varepsilon, T, b, \sigma, d, \gamma,\rho)\geq1$, $c := c(T, b, \sigma, d, \gamma) > 0$ such that it holds

\begin{align} \label{global:mean:squared:error:before:complexity}
\cE_P \le \delta_{h, \varepsilon}^P \cE_0 + C_{\varepsilon}
\left(
Ne^{- c \frac{M^{1-\rho}}{1 + 2^\ell\ell^{d-1}}}
+  \frac{ 1 + 2^\ell\ell^{d-1}}{h M^\rho } + 2^{-4\ell}\ell^{d-1} + h
\right) \;.
\end{align}

Combining Proposition <ref> with Theorem <ref> and (<ref>), we obtain

\begin{align}%\label{global:control:error}
\cE_P \le \delta_{h, \varepsilon}^P \cE_0 + C_\varepsilon \left(
\frac{\kappa_{K}}{h \wedge \alpha_{K} } L_{K,M}  + 2^{-4\ell}\ell^{d-1} + h \right).
\end{align}

From Proposition <ref>, we have that $\frac{\kappa_{K}}{h \wedge \alpha_{K} } \le \frac{C}{h}$, which combined with Lemma <ref> gives

\begin{align}
\frac{\kappa_{K}}{h \wedge \alpha_{K} } L_{K,M} &\le \frac{ C_{\rho,\gamma} }{h} \left(e^{- \gamma 2 \sqrt{2} \ln(2)\frac{\mathfrak{k} }{\beta_{K}}M^{1-\rho}}
+  \frac{ \beta_{K}}{\mathfrak{k} M^\rho }
\right)
\\
&\le \frac{ C_{\rho,\gamma} }{h} \left(e^{- c \frac{M^{1-\rho}}{1 + 2^\ell\ell^{d-1}}}
+  \frac{ 1 + 2^\ell\ell^{d-1}}{M^\rho }
\right)
\end{align}

for some positive constant $c$, where we used Lemma <ref> for the last inequality.

We are now ready to establish the complexity of the full Picard algorithm.

Proof of Theorem <ref>
Step 1: Setting the parameters $P$, $N$, $M$, $\ell$ and $\rho$.
We will chose the parameters $P$, $N$, $M$, $\ell$ and $\rho$ in order to achieve a global error $\cE_P$ of order $\varepsilon^2$, as this error controls $\cE_{\mathrm{MSE}}$. We first set $P = 2 |\log_\delta(\varepsilon)|$ and $N_\varepsilon= \ceil*{T\varepsilon^{-2}} $ so that $h_\varepsilon=T/N_\varepsilon\leq \varepsilon^2$. From Theorem <ref>, we also know that setting $\ell_\varepsilon = \log_2(\varepsilon^{-\frac12}|\log_2(\varepsilon)|^{\frac{d-1}{4 } })$, we obtain $\cE_\psi= O_d(\varepsilon^2)$ and $K_\varepsilon = O_d(\varepsilon^{-\frac12}|\log_2(\varepsilon)|^{\textcolor{black}{\frac{5(d-1)}4 }})$.

We now set $M$ such that the term $\frac{K_\varepsilon}{M^\rho h_\varepsilon}$ is of order $\varepsilon^2$, which leads to

\begin{align*}
M_\varepsilon = O_d(\varepsilon^{-\frac9{2 \rho}}|\log_2(\varepsilon)|^{ \textcolor{black}{ \frac{5(d-1)}{4\rho }} })\,.
\end{align*}

For $\iota > 1$, we set $\bar{\rho} = \frac9{10 \iota}$ with the constraint $\bar{\rho} > \frac12$ and we verify that

\begin{align*}
\frac{M_\epsilon^{1-\bar{\rho}}}{K_\varepsilon} \ge c \varepsilon^{5(1-\iota)}|\log_2(\varepsilon)|^{\textcolor{black}{\frac54}(d-1)(\frac1{\bar{\rho}} - 2)}
\end{align*}

for some constant $c>0$. This leads to

\begin{align*}
e^{- c \frac{M_\varepsilon^{1-\bar{\rho}}}{1 + 2^{\ell_\varepsilon} \ell_\varepsilon^{d-1}}}  = o(\varepsilon^4)
\end{align*}

and we also have that (<ref>) is satisfied.

Step 2: Computing the complexity $\cC_\varepsilon$. Recalling Remark <ref>, we see that the overall complexity $\cC_\varepsilon$ to reach the prescribed approximation accuracy $\varepsilon^2$ satisfies

\begin{align*}
\cC_\varepsilon &= P_\varepsilon N_\varepsilon K_\varepsilon M_\varepsilon
\\
&= O_d \left(
|\log_{2}(\varepsilon)| \varepsilon^{-2} \varepsilon^{-\frac12}|\log_2(\varepsilon)|^{\textcolor{black}{\frac{5(d-1)}4}}
\varepsilon^{-5\iota }|\log_2(\varepsilon)|^{ \frac{25(d-1)\iota}{18}}
\right)
\\
&=O_d(\varepsilon^{-\frac52(1+2\iota )}|\log_{2}(\varepsilon)|^{1+ \frac{45+50\iota}{36}(d - 1)} )\;,
\end{align*}

which concludes the proof.

§ APPENDIX

We gather below all the  parameters values used in the various algorithms, examples and basis functions settings.
In particular, we recall that the domain specification is given in (<ref>) and (<ref>) The learning rates are given by (<ref>).

\[ \Gamma(\lambda) := ( \alpha(\lambda ), \beta_1(\lambda), \beta_0(\lambda), m_0(\lambda)) \in \mathbb{R}^4,  \]

we set the  parameters in all the approximating space  $\mathscr{V}^z_n , 1\le n\le N-1$ to be the same: namely $\Gamma(\mathfrak{z}^{n, \cdot}) = \Gamma(\mathfrak{z}^{1, \cdot })$ for all $n\ge 2$. Thus, in the table below, the parameters of the learning rates are simply denoted by:

\[ \Gamma := \{ \Gamma(\mathfrak{y}), \Gamma(\mathfrak{z}^{0, \cdot} ), \Gamma(\mathfrak{z}^{1, \cdot }) \} \in \mathbb{R}^{3\times 4}.  \]

Algorithms     Basis functions      dim     N     M     T      Initial $\mathfrak{z}^{n, k}$     p     $\Gamma$     $\cE_{\mathrm{MSE}} $

8*c Picard Algorithm      8*Pre-wavelets     8*3     8*10      8*100000        8*0.3       8*0      1      c (0.6, 0, 3, 15000),
(0.6, 0, 20, 10000)       0.0286

8 - 10
2      c (0.6, 0, 2, 8000),
(0.6, 0, 10, 8000      0.0247

8 - 10
3      c (0.6, 0, 1, 8000),
(0.6, 0, 5, 8000      0.0219

8 - 10
4      c (0.6, 0, 0.5, 8000),
(0.6, 0, 3, 8000)      0.0207

8 - 10
5      c (0.6, 0, 0.5, 8000),
(0.6, 0, 3, 8000)      0.0201

Parameters for the periodic example

1|c|1*Examples     a     dim     M      N       Initial $y_0$      1* Learning rate

1*cQuadratic     1      5      2000      10        0.5     0.01

1*cLimits to
Picard algorithm     -0.4      2     5000     20        0.3      0.002

2 - 7

-1.5     2      5000      20       0       0.001

example     7*N.A.      2     6000      20       2       0.005

3 - 7
4      6000     20      5         0.005

3 - 7
5       5000      20      5         0.005

3 - 7
10      5000      20      8         0.005

3 - 7
15     5000      20      8         0.005

3 - 7
20     5000       20      8         0.005

3 - 7
25      5000      20      8         0.005

Parameters by model for the deep learning method with $ layers = 4, batchsize = 64$

1|c|2*Examples    1c|2*Basis functions     2* dim     2* N     2*r     3c| 1*Initial value      2* $\Gamma$

$\mathfrak{y} $     $ \mathfrak{z}^{0, \cdot} $      $\mathfrak{z}^{n, k}$

model     Pre-wavelets     5     10      2       0.5       -0.2     0      c (1, 0, 1, 100),
(0.8, 0, 1, 100),
(0.86, 0.02, 0.05, 100)

2 - 9

100     10      3.2         5.5       0     0       c (0.9, 0, 1, 100),
(0.7, 0, 1, 100),
(1, 0.003, 0.01, 1000)

example     3*Pre-wavelets     2     10      2        2       0      0     c (1, 0, 1.5, 1000),
(1, 0, 20, 1000),
(1, 0.003, 0.01, 1000)

3 - 9
4    10      2        5       0      0     c(1, 0, 1, 1000),
(1, 0, 20, 1000),
(1, 0.001, 0.01, 1000)

2 - 9
13*Hat      5     10     2        5      0      0      c (0.95, 0, 0.3, 100),
(1, 0, 5, 100),
(1, 0.001, 0.01, 100)

3 - 9
10     10     2.5         8      0     0      c (0.9, 0, 0.35, 300),
(1, 0, 5, 300),
(1, 0.001, 0.01, 300)

3 - 9
15    10      2.5        8      0      0      c (0.85, 0, 0.3, 500),
(1, 0, 5, 500),
(1, 0.001, 0.01, 500)

3 - 9
20     10     2.5        8      0      0      c(0.8, 0, 0.2, 1000),
(1, 0, 5, 1000),
(1, 0.001, 0.01, 1000)

3 - 9
25     10     2.8        8       0     0      c (0.7, 0, 0.2, 1500),
(1, 0, 5, 1500),
(1, 0.001, 0.01, 1500)

example     13*Hat      1     10     2        0.5       0       0      c (1, 0, 0.5, 100),
(1, 0, 3, 100),
(1, 0.1, 0.1, 100)

3 - 9
2      20     2        0.1      0       0     c (1, 0, 0.5, 100),
(1, 0, 5, 100),
(1, 0.2, 0.5, 100)

3 - 9
5     40     2         0.4    -1       0      c (1, 0, 0.5, 300),
(0.95, 0, 5, 500),
(1, 0.2, 0.1, 500)

3 - 9
8      60    2.2        0.6     1      0.08      c (1, 0, 0.35, 500),
(1, 0, 5, 500),
(1, 0.2, 1, 500)

3 - 9
10     100     2.5       0.1      -1      -0.1      c  (1, 0, 0.35, 500),
(0.95, 0, 5, 500),
(1, 0.2, 1, 500)

Parameters by model for the direct algorithm

1|c|2*Examples    1c|2*Basis functions     2* dim     2* r      3c| 1*Initial value      2* a      2* p      2* $\Gamma$

$\mathfrak{y} $     $ \mathfrak{z}^{0, \cdot} $      $\mathfrak{z}^{n, k}$

model     8*Pre-wavelets      8*5       8*2        8*0.5       8*-0.2     8*0      8*1      1     c (1, 0, 0.8, 100),
(0.9, 0, 1, 100),
(0.84, 0.02, 0.05, 100)

9 -10
2       c (1, 0, 0.3, 100),
(0.9, 0, 0.4, 100),
(0.84, 0.01, 0.02, 100)

9 - 10
$ p \ge 3 $    c (1, 0, 0.2, 100),
(0.9, 0, 0.2, 100),
(0.84, 0.005, 0.01, 100)

2 - 10
1*Hat     1*25      1*2.8       1* 2       1*0.1      1*0    1*1    $1\le p\le 3$     c (0.9, 0, 0.5, 100),
(0.8, 0, 0.8, 100),
(1, 0.003, 0.01, 1000)

example     12*Pre-wavelets     12*4      12*2       12*5       12*0.1      12*-0.01     12*N.A.     1     c (1, 0, 1, 1000),
(1, 0, 20, 1000),
(1, 0.001, 0.01, 1000)

9- 10
2     c(1, 0, 0.3, 1000),
(1, 0, 5, 1000),
(1, 0.0005, 0.005, 1000)

9- 10
3     c (1, 0, 0.2, 1000),
(1, 0, 5, 1000),
(1, 0.0003, 0.003, 1000)

9- 10
4, 5     c (1, 0, 0.15, 1000),
(1, 0, 3, 1000),
(1, 0.0002, 0.002, 1000)

9- 10
$p\ge 6$      c (1, 0, 0.1, 1000),
(1, 0, 2, 1000),
(1, 0.0001, 0.001, 1000)

2- 10
10*Hat     10* 20      10*2.5         10*8     10*0     10*0     10*N.A.     1    c (0.9, 0, 0.6, 1000),
(1, 0, 5, 1000),
(1, 0.001, 0.01, 1000)

9 - 10
2     c (0.9, 0, 0.2, 1000),
(1, 0, 4, 1000),
(1, 0.001, 0.01, 1000)

9 - 10
3    c (0.9, 0, 0.15, 1000),
(1, 0, 3, 1000),
(1, 0.0005, 0.005, 1000)

9 - 10
$p\ge 4$    c (0.9, 0, 0.1, 1000),
(1, 0, 2, 1000),
(1, 0.0005, 0.005, 1000)

4*cLimits to
algorithm     4*Pre-wavelets       4*2       4*2       0.3       0     0       -0.4     $1\le p \le 9$        c (1, 0, 1, 300),
(1, 0, 1, 300),
(1, 0.6, 0.1, 300)

5 - 10
0       0     0     -1.5     $1\le p \le 9$      c (1, 0, 2, 300),
(1, 0, 1, 300),
(1, 0.6, 0.1, 300)

Parameters by model for the Picard algorithm

1|c|2*Examples    1c|2*Basis functions     2* dim     2* r      3c| 1*Initial value      2* N      2* p      2* $\Gamma$

$\mathfrak{y} $     $ \mathfrak{z}^{0, \cdot} $      $\mathfrak{z}^{n, k}$

example     25*Hat      1      2        0.5      0    0       10     $1\le p\le 5$      c(1, 0, $0.5*(0.8)^{p-1}$, 100),
(1, 0, 3$*(0.8)^{p-1}$, 100),
(1, 0.1$*(0.8)^{p-1}$, 0.1$*(0.8)^{p-1}$, 100)

3 - 10
2      2        0.1     0     0      20     $1\le p\le 5$      c  (1, 0, 0.5$*(0.8)^{p-1}$, 100),
(1, 0, 5$*(0.8)^{p-1}$, 100),
(1, 0.2$*(0.8)^{p-1}$, 0.5$*(0.8)^{p-1}$, 100)

3 - 10
5      2      0.4      -2     0     40      $1\le p\le 5$      c (1, 0, 0.5$*(0.8)^{p-1}$, 300),
(0.95, 0, 5$*(0.8)^{p-1}$, 500),
(1, 0.2$*(0.8)^{p-1}$, 0.1$*(0.8)^{p-1}$, 500)

3 - 10
8      2.2       0.6     1       0.08      60     $1\le p\le 5$     c (1, 0, 0.35$*(0.8)^{p-1}$, 500),
(1, 0, 5$*(0.8)^{p-1}$, 500),
(1, 0.2$*(0.8)^{p-1}$, $(0.8)^{p-1}$, 500)

3 - 10
13*10      13*2.5        13*0.1      13*-1      13*-0.1      13*100     1     c(1, 0, 0.25, 500),
(0.95, 0, 4, 500),
(1, 0.15, 0.5, 500)

9 - 10
2      c (1, 0, 0.2, 500),
(0.95, 0, 3, 500),
(1, 0.12, 0.4, 500)

9 - 10
3      c (1, 0, 0.15, 500),
(0.95, 0, 2, 500),
(1, 0.1, 0.3, 500)

9 - 10
$p\ge 4$     c  (1, 0, 0.1, 500),
(0.95, 0, 1, 500),
(1, 0.08, 0.25, 500)

9 - 10
$p\ge 6$      c (1, 0, 0.05, 500),
(0.95, 0, 0.5, 500),
(1, 0.05, 0.2, 500)

Parameters by model for the Picard algorithm

[1]
Bally, V., and Pagès, G.
Error analysis of the optimal quantization algorithm for obstacle
Stochastic Processes and their Applications 106, 1 (2003), 1 –

[2]
Bally, V., and Pagès, G.
A quantization algorithm for solving multidimensional discrete-time
optimal stopping problems.
Bernoulli 9, 6 (2003), 1003–1049.

[3]
Beck, C., E, W., and Jentzen, A.
Machine learning approximation algorithms for high-dimensional fully
nonlinear partial differential equations and second-order backward stochastic
differential equations.
Journal of Nonlinear Science (2017), 1–57.

[4]
Beck, C., Hutzenthaler, M., Jentzen, A., and Kuckuck, B.
An overview on deep learning-based approximation methods for partial
differential equations.
arXiv preprint arXiv:2012.12348 (2020).

[5]
Bender, C., and Denk, R.
A forward scheme for backward sdes.
Stochastic Processes and their Applications 117, 12 (2007),

[6]
Benveniste, A., Métivier, M., and Priouret, P.
Adaptive algorithms and stochastic approximations, vol. 22.
Springer Science & Business Media, 2012.

[7]
Bergman, Y. Z.
Option pricing with differential interest rates.
The Review of Financial Studies 8, 2 (1995), 475–500.

[8]
Bohn, B.
Error analysis of regularized and unregularized least-squares
regression on discretized function spaces.
PhD thesis, Institute for Numerical Simulation, University of Bonn,

[9]
Bohn, B.
On the convergence rate of sparse grid least squares regression.
In Sparse Grids and Applications-Miami 2016. Springer, (2018),
pp. 19–41.

[10]
Bouchard, B., and Touzi, T.
Discrete-time approximation and monte-carlo simulation of backward
stochastic differential equations.
Stochastic Processes and their Applications 111, 2 (2004), 175
– 206.

[11]
Briand, P., and Labart, C.
Simulation of bsdes by wiener chaos expansion.
The Annals of Applied Probability 24, 3 (2014), 1129–1171.

[12]
Bungartz, H.-J., and Griebel, M.
Sparse grids.
Acta numerica 13 (2004), 147–269.

[13]
Chassagneux, J.-F.
Linear multistep schemes for bsdes.
SIAM Journal on Numerical Analysis 52, 6 (2014), 2815–2836.

[14]
Chassagneux, J.-F., and Garcia Trillos, C.
Cubature method to solve bsdes: Error expansion and complexity
Mathematics of Computation 89, 324 (2020), 1895–1932.

[15]
Chassagneux, J.-F., and Richou, A.
Numerical simulation of quadratic bsdes.
The Annals of Applied Probability 26, 1 (2016), 262–304.

[16]
Crisan, D., and Manolarakis, K.
Solving backward stochastic differential equations using the cubature
method: application to nonlinear pricing.
SIAM Journal on Financial Mathematics 3, 1 (2012), 534–571.

[17]
Crisan, D., and Manolarakis, K.
Second order discretization of backward sdes and simulation with the
cubature method.
The Annals of Applied Probability 24, 2 (2014), 652–678.

[18]
Crisan, D., Manolarakis, K., and Nizar, T.
On the monte carlo simulation of bsdes: An improvement on the
malliavin weights.
Stochastic Processes and their Applications 120, 7 (2010), 1133
– 1158.

[19]
Duflo, M.
Algorithmes stochastiques, vol. 23 of Mathématiques &
Applications (Berlin) [Mathematics & Applications].
Springer-Verlag, Berlin, (1996).

[20]
E, W., Han, J., and Jentzen, A.
Deep learning-based numerical methods for high-dimensional parabolic
partial differential equations and backward stochastic differential
Communications in Mathematics and Statistics 5, 4 (2017),

[21]
El Karoui, N., Peng, S., and Quenez, M. C.
Backward stochastic differential equations in finance.
Mathematical finance 7, 1 (1997), 1–71.

[22]
Feuersänger, C.
Sparse grid methods for higher dimensional approximation.
PhD thesis, University of Bonn, (2010).

[23]
Friedman, A.
Partial differential equations of parabolic type.
Prentice-Hall, Inc., Englewood Cliffs, N.J., (1964).

[24]
Frommert, M., Pflüger, D., Riller, T., Reinecke, M., Bungartz, H.-J.,
and Enßlin, T.
Efficient cosmological parameter sampling using sparse grids.
Monthly Notices of the Royal Astronomical Society 406, 2
(2010), 1177–1189.

[25]
Geiss, C., and Labart, C.
Simulation of bsdes with jumps by wiener chaos expansion.
Stochastic Processes and their Applications 126, 7 (2016),

[26]
Gobet, E., Lemor, J.-P., and Warin, X.
A regression-based monte carlo method to solve backward stochastic
differential equations.
The Annals of Applied Probability 15, 3 (2005), 2172–2202.

[27]
Gobet, E., López-Salas, J. G., Turkedjiev, P., and Vázquez, C.
Stratified regression monte-carlo scheme for semilinear pdes and
bsdes with large scale parallelization on gpus.
SIAM Journal on Scientific Computing 38, 6 (2016), C652–C677.

[28]
Gobet, E., Turkedjiev, P., et al.
Approximation of backward stochastic differential equations using
malliavin weights and least-squares regression.
Bernoulli 22, 1 (2016), 530–562.

[29]
Griebel, M., and Oswald, P.
Tensor product type subspace splittings and multilevel iterative
methods for anisotropic problems.
Advances in Computational Mathematics 4, 1 (1995), 171.

[30]
Gu, Y., Yang, H., and Zhou, C.
Selectnet: Self-paced learning for high-dimensional partial
differential equations.
arXiv preprint arXiv:2001.04860 (2020).

[31]
Han, J., Jentzen, A., and E, W.
Overcoming the curse of dimensionality: Solving high-dimensional
partial differential equations using deep learning.
arXiv preprint arXiv:1707.02568 (2017).

[32]
Han, J., Jentzen, A., and E, W.
Solving high-dimensional partial differential equations using deep
Proceedings of the National Academy of Sciences 115, 34 (2018),

[33]
Han, J., Jentzen, A., and E, W.
Algorithms for solving high dimensional pdes: From nonlinear monte
carlo to machine learning.
arXiv preprint arXiv:2008.13333 (2020).

[34]
Han, J., and Long, J.
Convergence of the deep bsde method for coupled fbsdes.
Probability, Uncertainty and Quantitative Risk 5, 1 (2020),

[35]
Henry-Labordère, P., Oudjane, N., Tan, X., Touzi, N., and Warin, X.
Branching diffusion representation of semilinear pdes and monte carlo
Ann. Inst. H. Poincaré Probab. Statist. 55, 1 (02 2019),

[36]
Hu, Y., Nualart, D., and Song, X.
Malliavin calculus for backward stochastic differential equations and
application to numerical solutions.
The Annals of Applied Probability 21, 6 (2011), 2379–2423.

[37]
Huré, C., Pham, H., and Warin, X.
Deep backward schemes for high-dimensional nonlinear pdes.
Mathematics of Computation 89, 324 (2020), 1547–1579.

[38]
Hutzenthaler, M., Jentzen, A., Kruse, T., and E, W.
Multilevel picard iterations for solving smooth semilinear parabolic
heat equations.
arXiv preprint arXiv:1607.03295 (2016).

[39]
Kushner, H. J., and Yin, G. G.
Stochastic approximation and recursive algorithms and
applications, second ed., vol. 35 of Applications of Mathematics (New
Springer-Verlag, New York, (2003).
Stochastic Modelling and Applied Probability.

[40]
Ladyženskaja, O. A., Solonnikov, V. A., and Ural'ceva, N. N.
Linear and quasilinear equations of parabolic type.
Translated from the Russian by S. Smith. Translations of Mathematical
Monographs, Vol. 23. American Mathematical Society, Providence, R.I., (1968).

[41]
Ma, J., and Zhang, J.
Path regularity for solutions of backward stochastic differential
Probability Theory and Related Fields 122, 2 (2002), 163–190.

[42]
Menozzi, S., and Lemaire, V.
On some non asymptotic bounds for the euler scheme.
Electron. J. Probab. 15 (2010), 1645–1681.

[43]
Pagès, G.
Numerical Probability: An Introduction with Applications to
Universitext. Springer International Publishing, (2018).

[44]
Pagès, G., and Sagna, A.
Improved error bounds for quantization based numerical schemes for
bsde and nonlinear filtering.
Stochastic Processes and their Applications 128, 3 (2018), 847
– 883.

[45]
Pardoux, E., and Peng, S.
Adapted solution of a backward stochastic differential equation.
Systems Control Lett. 14, 1 (1990), 55–61.

[46]
Pardoux, E., and Peng, S.
Backward stochastic differential equations and quasilinear parabolic
partial differential equations.
In Stochastic partial differential equations and their
applications (Charlotte, NC, 1991), vol. 176 of Lect. Notes Control
Inf. Sci. Springer, Berlin, (1992), pp. 200–217.

[47]
Pardoux, E., and Tang, S.
Forward-backward stochastic differential equations and quasilinear
parabolic PDEs.
Probab. Theory Related Fields 114, 2 (1999), 123–150.

[48]
Peng, S.
Probabilistic interpretation for systems of quasilinear parabolic
partial differential equations.
Stochastics and Stochastics Reports (Print) (1991).

[49]
Zhang, J.
A numerical scheme for bsdes.
The Annals of Applied Probability 14, 1 (2004), 459–488.


# Towards Generating Adversarial Examples on Mixed-type Data

Han Xu
Zhimeng Jiang
Menghai Pan, Huiyuan Chen, Xiaoting Li, Mahashweta Das, Hao Yang  Michigan
State University, East Lansing, Michigan, USA
<EMAIL_ADDRESS>Texas A&M University, College Station, Texas, USA
<EMAIL_ADDRESS>VISA Research, Palo Alto, California, USA

###### Abstract

The existence of adversarial attacks (or adversarial examples) brings huge
concern about the machine learning (ML) model’s safety issues. For many
safety-critical ML tasks, such as financial forecasting, fraudulent detection,
and anomaly detection, the data samples are usually mixed-type, which contain
plenty of numerical and categorical features at the same time. However, how to
generate adversarial examples with mixed-type data is still seldom studied. In
this paper, we propose a novel attack algorithm M-Attack, which can
effectively generate adversarial examples in mixed-type data. Based on
M-Attack, attackers can attempt to mislead the targeted classification model’s
prediction, by only slightly perturbing both the numerical and categorical
features in the given data samples. More importantly, by adding designed
regularizations, our generated adversarial examples can evade potential
detection models, which makes the attack indeed insidious. Through extensive
empirical studies, we validate the effectiveness and efficiency of our attack
method and evaluate the robustness of existing classification models against
our proposed attack. The experimental results highlight the feasibility of
generating adversarial examples toward machine learning models in real-world
applications.

##  I Introduction

The existence of adversarial attacks (or adversarial examples) [1, 2, 3, 4]
has brought huge concerns when applying machine learning (ML) models to
safety-critical tasks. In many ML applications in Web Service or mobile
applications, the data inputs are often mixed type, which contains both
numerical and categorical features simultaneously. For example, for an online
financial institute, ML models are trained to evaluate whether a loan
applicant has the ability to repay his/her loan. In this scenario, the data
has numerical features, e.g., the applicant’s age, account balance, and annual
income, as well as categorical features including his/her educational
background, occupation type, and marital status. Similarly, in recommender
systems for online shopping, the data also contains both numerical and
categorical information, such as the price and categories of the recommended
items. However, how to conduct adversarial attacks for mixed-type data still
lacks full exploration. Therefore, in this paper, we focus on the problem of
how to generate adversarial examples for mixed-type data. Specifically, we aim
to solve the problem: given a well-trained ML model, how can we perturb a data
sample with an unnoticeable distortion, such that this ML model’s prediction
is misled to give a wrong prediction? The studied problem is crucial in
practice. Recall the above financial institute example: if an unqualified
applicant provides a fake profile that contains a few fraudulent records so
that he/she can fool the trained ML model to get the approval of the loan, it
will cause a huge cost to this financial institute.

To achieve this attacking goal, we face tremendous challenges. First, the
attacker is expected to modify as few features of the original (clean) data as
possible to keep the perturbation behavior unnoticeable and insidious. This
requires the perturbation added on the original sample to be sparse in the
input data space. Notably, there are existing methods for sparse adversarial
attacks in either numerical or categorical data domains, separately. In the
numerical domain, Projected Gradient Descent methods (PGD) are adopted to
guide the search of adversarial examples and project the perturbation into a
continuous $l_{1}$-norm bounded space to stress the sparsity of perturbation
[1, 5]. In the categorical domain, search-based methods [6, 7] are employed to
iteratively find the top-$K$ categorical features, which have the largest
influence to model prediction, and then search optimal perturbation for these
$K$ features. However, our task involves both the numerical and categorical
features and there are still no confirmative methods to generate the optimal
sparse adversarial attack over the targeted searching space, which is a
Cartesian product of a discrete space (for categorical features) and
continuous space (for numerical features). Moreover, our experimental results
in Section V suggest that simply combining existing strategies usually provide
sub-optimal solutions. For example, for an algorithm which first applies the
search-based methods [6, 7] to perturb categorical features, and then applies
$l_{1}$-PGD method [1, 5] to find numerical perturbations, it cannot
successfully find strongest adversarial examples (or leading to the maximal
loss value of the targeted classifier). This fact highlights the necessity to
devise new adversarial attack algorithms exclusively designed for mixed-type
data.

Second, the attacker should also keep the generated adversarial examples to be
seemingly benign. In other words, adversarial examples should be close to the
distribution of original clean data samples. It is hard to achieve this goal
since features in mixed-type data are usually highly correlated. For example,
in Home Credit Default Risk Dataset [8] where the task is to predict a
person’s qualification for a loan, the feature “age” of an applicant is always
strongly related to other numerical features (such as “number of children”)
and categorical features (such as “family status”). In this dataset, if an
attacker perturbs the feature “family status” from “child” to “parent” for an
18-year-old loan applicant, the perturbed sample obviously deviates from the
true distribution of clean data samples (because there are rarely 18-year-old
parents in reality). As a result, the generated adversarial example can be
easily detected as “abnormal” samples, by an defender that applies Out-of-
Distribution (OOD) detection (or Anomaly Detection) methods [9, 10, 11], or
detected by human experts who can judge the authentication of data samples
based on their domain knowledge. Thus, the attacker should generate
adversarial examples, which do not significantly violate the correlation
between any pair of numerical features, as well as any pair of categorical
features, or the pair of categorical and numerical features.

In this paper, to tackle the aforementioned challenges, we proposed M-Attack,
which is a novel attacking framework for mixed-type data. In detail, we first
transform the searching space of mixed-type adversarial examples into a
unified continuous space (see Figure 1). To achieve this goal, we convert the
problem of finding adversarial categorical perturbations into the problem to
find the probabilistic (categorical) distribution which the adversarial
categorical features are sampled from. Therefore, we are facilitated to find
sparse adversarial examples in this unified continuous space, by
simultaneously updating the numerical & categorical perturbation via gradient-
based methods. Furthermore, to generate in-distribution adversarial examples,
we propose a Mix-Mahalanobis Distance to measure and regularize the distance
of an (adversarial) example to the distribution of the clean mixed-type data
samples. Through extensive experiments, we verify that: (1) M-Attack can
achieve better attacking performance compared to representative baselines,
which are the combination of existing numerical & categorical attack methods;
(2) M-Attack can achieve better (or similar) efficiency compared to these
baseline methods; and (3) Mix-Mahalanobis Distance can help the generated
adversarial examples be close to the true distribution of clean data. Our
contribution can be summarized as follows:

  * •

We propose an efficient and effective algorithm, M-Attack, to generate
adversarial examples for mixed-type data.

  * •

We propose a novel measurement, Mixed Mahalanobis Distance, which helps the
generated adversarial examples be close to the true distribution.

  * •

We conduct extensive experiments to validate the feasibility of M-Attack, and
demonstrate the vulnerability of popular classification models against
M-Attack.

##  II Related Works

There has been a rise in the importance of the adversarial robustness of
machine learning models in recent years. Most of the existing works, including
evasion attack, and poison attack, focus on continuous input space, especially
in the image domain [12, 1, 13]. In the image domain, because the data space
(which is the space of pixel values) is continuous, people use gradient-based
methods [1, 5] to find adversarial examples. Based on the gradient attack
methods, various defense methods, such as adversarial training, [1, 14] are
proposed to improve the model robustness. Meanwhile, adversarial attacks
focusing on discrete input data, like text data, which have categorical
features, are also starting to catch the attention of researchers. In the
natural language processing domain, the work [15] discusses the potential to
attack text classification models such as sentiment analysis, by replacing
words with their synonyms. The study [16] proposes to modify the text token
based on the gradient of input one-hot vectors. The method [17] develops a
scoring function to select the most effective attack and a simple character-
level transformation to replace projected gradient or multiple linguistic-
driven steps on text data. In the domain of graph data learning, there are
methods [18] that greedily search the perturbations to manipulate the graph
structure to mislead the targeted models. In a conclusion, when the data space
is discrete, these methods share a similar core idea by applying searched-
based methods to find adversarial perturbations. Although there are well-
established methods for either numerical domain or categorical domain
separately, there is still a lack of studies in mixed-type data. However,
mixed-type data are widely existing in various machine learning tasks in the
physical world. For example, for the fraudulent transaction detection systems
[19, 20] of credit card institutes, the transaction records from cardholders
may include features such as transaction amount (numerical) and the type of
the purchased product (categorical). Similarly, for ML models applying in AI
healthcare [21, 22], i.e., in epidemiological studies [23, 24], the data can
be collected from surveys which ask the respondents’ information, including
their age, gender, race, the type of medical treatment and the expenditure
amount of each type of medical supplies that are used. In recommender systems
[25, 26, 27] in online-shopping websites which are built for product
recommendations, the data can include the purchase history of the clients or
the property of the products, both containing numerical and categorical
features. In this paper, we focus on the problem of how to slightly perturb
the input (mixed-type) data sample of a model to mislead the model’s
prediction. This study can have great significance to help us understand the
potential risk of ML models under malicious perturbations in the applications
mentioned above.

##  III Methodology - M-Attack

In this section, we introduce the details of our proposed method M-Attack.
Before discussing the details of M-Attack, we first provide the necessary
definitions and notations used in this work. For any given sample $x$ with
true label $y\in\mathcal{Y}$, we assume that it contains the numerical
features $x_{n}\in\mathbb{R}^{d_{n}}$ with dimensional $d_{n}$. It also
contains $d_{c}$ categorical features $x_{c}$ (such as race, gender,
education, etc.) and each categorical feature may include a different number
of categories. More specifically, among all categorical features, we denote
each individual categorical feature $x_{c}^{i}$ (e.g., gender), which can be
chosen from $k_{i}$ different categories (e.g., male and female). During the
attacking process, we assume that there is a classifier $F(\cdot)$ that takes
the tuple $(x_{n},x_{c})$ as input, and makes the prediction by
$F(x_{n},x_{c})=\hat{y}\in\mathcal{Y}$.

###  III-A An Overview of M-Attack

In this subsection, we introduce the overall framework of our proposed method
- M-Attack. In this paper, we only consider the scenario that all information
about the model $F(\cdot)$, including its parameters and architecture, is
given to the attacker. Thus, during the test phase, for a test sample $x$,
which contains the numerical feature $x_{n}$ and categorical feature $x_{c}$,
with true label $y$, the attacker aims to find such a perturbed data sample
$x^{\prime}=(x^{\prime}_{n},x^{\prime}_{c})$, which is close to
$(x_{n},x_{c})$, but can mislead the model to make a prediction different from
$y$. To achieve this goal, in our proposed M-Attack, we aim to solve the
following problem to find $(x^{\prime}_{n},x^{\prime}_{c})$ as:

$\displaystyle\begin{split}\max~{}~{}~{}~{}~{}~{}&\mathcal{L}(F(x^{\prime}_{n},x^{\prime}_{c}),y)\\\
\text{s.t. }&\begin{cases}||x^{\prime}_{n}-x_{n}||_{1}\leq\epsilon_{1}\\\
||x^{\prime}_{c}-x_{c}||_{0}\leq\epsilon_{2}\\\
\mathcal{D}((x_{n},x_{c}),(x^{\prime}_{n},x^{\prime}_{c}))\leq\epsilon_{3}\end{cases}\end{split}$
(1)

Specifically, we aim to find such a tuple $(x^{\prime}_{n},x^{\prime}_{c})$
where the model $F(\cdot)$ has the maximized loss value so that the model is
likely to have a wrong prediction. Moreover, we introduce three constraints to
regularize the generated attacks (or perturbations) to be close to the
original sample $(x_{n},x_{c})$:

  1. (i)

We constrain the $l_{1}$ norm distance between the perturbed sample’s
numerical feature $x^{\prime}_{n}$ and the original numerical feature $x_{n}$
so that the perturbation on $x_{n}$ is sparse.

  2. (ii)

We constrain the $l_{0}$ difference between $x_{c}$ and $x_{c}^{\prime}$ so
that the number of changed categorical features is limited.

  3. (iii)

We constrain the distance $\mathcal{D}(\cdot)$ of the pair
$(x^{\prime}_{n},x^{\prime}_{c})$ to $(x_{n},x_{c})$ to keep the perturbed
sample “seemingly” benign. This will help to keep the generated adversarial
examples close to the distribution of clean samples. Thus, the generated
samples are harder to be detected by Out-of-Distribution methods or human
experts. In Section IV, we will make a detailed definition about the distance
$\mathcal{D}(\cdot)$.

It is worth mentioning that: if we don’t consider the constraint (iii), there
already exists well-established methods to partially solve the problem in
Eq.(1). For example, applying $l_{1}$-PGD method [5] can solve the problem
under constraint (i); and applying greedy search [6] can solve the problem
under constraint (ii). Thus, a potential solution for Eq.(1) is that: we first
apply $l_{1}$-PGD [5] to find $x^{\prime}_{n}$ under constraint (i) to
maximize the loss value, and then adopt greedy method [6] to find
$x^{\prime}_{c}$ (or vice versa). However, our proposed method, M-Attack, is a
distinct approach, which simultaneously updates the numerical and categorical
features. This will help M-Attack find better solutions for the optimization
problem because it takes the interaction between numerical and categorical
features into consideration. Next, we will detail how to solve Eq.(1) – In the
remaining subsections of Section III, we will introduce how to achieve the
optimization goal in Eq.(1) which satisfies the first two constraints while
ignoring the third constraint; while in Section IV, we will define Mix-
Mahalanobis Distance $\mathcal{D}(\cdot)$ in detail and involve the constraint
(iii) in the algorithm.

###  III-B Sparse Adversarial Perturbations

Overall, in our proposed M-Attack, in order to find sparse adversarial
perturbations, we introduce a new searching space,
$\mathcal{S}_{n}\times\mathcal{S}_{c}$, which is the Cartesian product of the
Numerical Adversarial Space $S_{n}$ where the adversarial numerical features
$x^{\prime}_{n}$ reside, and Probabilistic Adversarial Space $S_{c}$ where the
adversarial categorical features $x^{\prime}_{c}$ are sampled from.

####  III-B1 Numerical Adversarial Space

We first define the Numerical Adversarial Space to be equal to the space of
samples that satisfy the constraint (i) in Eq.(1):

$\mathcal{S}_{n}=\\{x_{n}^{\prime}:||x^{\prime}_{n}-x_{n}||_{1}\leq\epsilon_{1}\\}$

During the M-Attack, we repeatedly update the numerical features of
$x^{\prime}_{n}$ in the space $\mathcal{S}_{n}$, via an approach similar to
the method Projected Gradient Descent (PGD) [1, 3] which has been designed for
$l_{1}$ adversarial attack. In each step of the PGD algorithm, suppose that
the objective is simply to maximize the value of a function $Q(\cdot)$, and
the current optimized result is $x^{\prime}_{n}$, it first updates
$x^{\prime}_{n}$ along with the direction of gradient ascent:

$x^{\prime\prime}_{n}\leftarrow
x^{\prime}_{n}+\text{argmax}_{||v||_{1}\leq\alpha}~{}~{}v^{T}\nabla
Q(x^{\prime}_{n}).$ (2)

In other words, for each step, we find the $x^{\prime\prime}_{n}$ which can
result in the maximal increase of the loss value. Then, if
$x^{\prime\prime}_{n}$ is out of $\mathcal{S}_{n}$, we project
$x^{\prime\prime}_{n}$ back to the defined numerical adversarial space
$\mathcal{S}_{n}$ by solving a convex optimization problem:

$x_{n}^{\prime}\leftarrow\text{argmin}||x_{n}^{\prime\prime}-x_{n}^{\prime}||_{2},~{}~{}\text{s.t.}~{}~{}x_{n}^{\prime}\in||x_{n}^{\prime}-x_{n}||\leq\epsilon.$

It finds the point residing in $\mathcal{S}_{n}$ which has the smallest
Euclidean distance with $x^{\prime\prime}_{n}$. To solve this convex
optimization problem, we can apply existing convex optimization solvers from
tools like CVXOPT [28] or the method [29].

Figure 1: An overview of the proposed M-Attack. In the forward propagation,
M-Attack generates categorical adversarial perturbation $x^{\prime}_{c}$ from
Probabilistic Distribution $\pi$, and feeds the mixed-type adversarial example
$(x^{\prime}_{n},x^{\prime}_{c})$ into the targeted classifier. In the
backward propagation, M-Attack updates $\pi$ and numerical feature
$x^{\prime}_{n}$ simultaneously.

####  III-B2 Probabilistic Adversarial Space (For Categorical Feature)

To find adversarial perturbations $x^{\prime}_{c}$ for categorical features,
we propose a method to alternatively search in a continuous space
$\mathcal{S}_{c}$, so that we can apply gradient methods to update
$x^{\prime}_{n}$ and $x^{\prime}_{c}$ at the same time. In detail, we assume
that each feature of (adversarial) categorical data $x_{c}^{i}$ follows a
distinct categorical distribution: $\textit{Categorical}(\pi_{i})$, where:

$\pi_{i}=[\pi_{i,0},\pi_{i,1},...,\pi_{i,k_{i}}]\in(0,1)^{k_{i}}=\Pi_{i},$

$k_{i}$ is the number of categories of feature $x_{c}^{i}$. Here, each
$\pi_{i,j}$ represents the probability that the feature $x_{c}^{i}$ belongs to
the category $j$. Thus, the distribution of all categorical features in one
sample can be represented as an array
$\pi=[\pi_{0};\pi_{1};...;\pi_{d_{c}}]\in\Pi_{0}\times\Pi_{1}\times...\times\Pi_{d_{c}}=\Pi$
, and $d_{c}$ is the number of categorical features. Then, in order to
constrain the $l_{0}$ distance between $x^{\prime}_{c}$ and $x_{c}$ in
constraint (ii) of Eq.(1), we define the Probabilistic Adversarial Space
$\mathcal{S}_{c}$ as:

$\mathcal{S}_{c}=\left\\{\pi:\Pr_{x^{\prime}_{c}\sim\pi}(\|x^{\prime}_{c}-x_{c}\|_{0}\geq\epsilon_{2})\leq\delta\right\\}\subseteq\Pi$
(3)

where $\delta$ is the tail probability constraint. Intuitively, by
constraining $\pi$ in space $\mathcal{S}_{c}$, we aim to find a distribution
$\pi$, such that for a sample $x_{c}^{\prime}$ following the distribution
$\pi$, it has a low probability to have the $l_{0}$ distance
$||x^{\prime}_{c}-x_{c}||_{0}$ larger than $\epsilon_{2}$. It is approximately
equivalent to the constraint (ii) in Eq.(1). In our algorithm of M-Attack, we
substitute the $l_{0}$ distance between $x^{\prime}$ and $x$ by calculating
the sum of Cross Entropy Loss between $\pi_{i}$ and $x_{c}^{i}$:
$\mathcal{L}_{CE}(\pi_{i},x_{c}^{i})$ for all features
$i\in\\{1,...,d_{c}\\}$.

$\Pr_{x^{\prime}_{c}\sim\pi}(||x^{\prime}_{c}-x_{c}||_{0}\geq\epsilon_{2})\rightarrow\left[\sum_{i}\mathcal{L}_{CE}(\pi_{i},x_{c}^{i})-\zeta\right]^{+}:=\mathcal{L}_{CE}(\pi,x_{c})$
(4)

It is because $\mathcal{L}_{CE}(x_{c}^{i},\pi_{i})$ approximately measures the
possibility that the generated $(x^{\prime}_{c})^{i}$ (following $\pi$) is
different from $x_{c}^{i}$. Therefore, we use the sum of Cross Entropy
$\sum_{i}\mathcal{L}_{CE}(\pi_{i},x_{c}^{i})$ to approximate the number of
changed features, which is the $l_{0}$ difference
$||x_{c}^{\prime}-x_{c}||_{0}$. In our algorithm, we penalize the searched
$\pi$ when the term $\sum_{i}\mathcal{L}_{CE}(\pi_{i},x_{c}^{i})$ exceeds a
positive value $\zeta$. In this case, we equivalently limit the probability
that the generated samples $x_{c}^{\prime}$ have the number of perturbed
features larger than $\epsilon_{2}$. During the optimization process, we can
update the distribution $\pi$ via gradient-based methods such as Gumbel-
softmax [30].

###  III-C The Attack Framework

With previous components of M-Attack, we eventually transform the original
problem in Eq.(1) into a problem of finding a pair $(x_{n}^{\prime},\pi)$
residing in the space $\mathcal{S}_{n}\times\mathcal{S}_{c}$ satisfying:

$\displaystyle\begin{split}\max~{}~{}~{}~{}~{}~{}&\mathbb{E}_{x^{\prime}_{c}\sim\pi}\left[\mathcal{L}(F(x^{\prime}_{n},x^{\prime}_{c}),y)\right]\\\
\text{s.t.
}&x^{\prime}_{c}\in\mathcal{S}_{n},~{}~{}~{}~{}\pi\in\mathcal{S}_{c}\end{split}$
(5)

The term $\pi$ represents the categorical distribution of (the categorical
part of) adversarial examples. Thus, in Eq.(5), we instead maximize the
expected loss value of samples $x^{\prime}_{c}$ which are generated following
$\pi$. Moreover, for the constraint $\pi\in\mathcal{S}_{c}$, the Cross-Entropy
Loss $\mathcal{L}_{CE}(\pi,x_{c})$ used in Eq.(4) is differentiable in terms
of $\pi$. Thus, we further rewrite the problem to its Lagrangian form:

$\displaystyle\begin{split}\max~{}~{}~{}~{}~{}~{}&\mathbb{E}_{x^{\prime}_{c}\sim\pi}\left[\mathcal{L}(F(x^{\prime}_{n},x^{\prime}_{c}),y)-\alpha\mathcal{L}_{CE}(\pi,x_{c})\right]=Q(x^{\prime}_{n},\pi)\\\
\text{s.t.
}&x^{\prime}_{c}\in\mathcal{S}_{n},~{}~{}~{}~{}\pi\in\mathcal{S}_{c},\end{split}$
(6)

where we denote the objective as $Q(x^{\prime}_{n},\pi)$. In the algorithm of
M-Attack, we apply a gradient descent method to repeatedly update the pair
$(x^{\prime}_{n},\pi)$ to solve the problem above. In detail, refer to the
Algorithm 1 (or Figure 1), in Step 1 and Step 2, we first calculate the
gradients of the loss towards the input sample $x_{n}$ and the latent
probability $\pi$ (for categorical features). In Step 3 and Step 4, we project
the updated features back to the constrained space. During the test phase, we
make a series of sampling and choose the optimal sampling which has the
maximal $Q(\cdot)$. It is worth mentioning that our method simultaneously
updates the numerical and categorical features and the attacking algorithm can
enjoy better effectiveness and efficiency than existing methods.

Algorithm 1 Adversarial Attacks for Mixed-Data M-Attack

Input: Objective function $Q(\cdot)$ defined in Eq.(6), a sample $x$, true
label $y$, number of steps of gradient descent $N$.

Initialize $x^{\prime}_{n}=x_{n},\pi=x_{c}$

for t = $1$ to $N$ do

1\. Update $x^{\prime}_{n}$ by gradient descent via Eq.(2)

2\. Update $\pi$ by gradient descent:
$\pi\leftarrow\pi+\gamma\nabla_{\pi}Q(x^{\prime}_{n},\pi).$

3\. Project $x^{\prime}_{n}$ back to $\mathcal{S}_{n}$.

4\. Project $\pi$ back to the space $\Pi$.

end for

Output: The tuple $(x^{\prime}_{n},\pi)$. The eligible categorical features
are sampled following the probability distribution $\pi$.

##  IV Mixed Mahalanobis Distance

Yet solving the problem in Eq.(5) to satisfy the constraints (i) and (ii)
helps us find sparse perturbations, it is still not adequate to guarantee the
adversarial perturbations unnoticeable. For example, take Figure 2 as an
example, an adversarial attacker perturbs the feature “family status” from
“child” to “parent” for an 18-year-old loan applicant (in Home Credit
Dataset). The perturbed sample can significantly deviate from the clean data
distribution because there are rarely 18-year-old parents in reality. As a
result, the adversarial perturbation can be easily detected as “abnormal
samples” by human experts and they can refuse to let ML models predict these
“abnormal” samples. Moreover, these abnormal samples are also very likely to
be detected by Out-of-Distribution (OOD) detection methods [10, 31]. For
example, the methods [10, 31] first estimate the distribution of clean data
samples via kernel density estimation or via training generative models and
calculate the likelihood of a test sample in the estimated clean data
distribution. Similarly, if a sample’s likelihood score is low, the model can
refuse to make a prediction. It is worth mentioning that OOD detection is
widely applied as defense strategies [32] in image classification tasks.
Therefore, during the attack process, the attacker should also consider
generating adversarial examples, which are close to the clean data
distribution. In other words, we also need to consider the constraint (iii) in
Eq.(5).

###  IV-A Mahalanobis Distance

In order to generate in-distribution adversarial examples, the method in [33]
considers regularizing the Mahalanobis Distance [34, 35] of the generated
adversarial examples to the clean distribution (for numerical data). In
detail, suppose that the clean data samples follow a Gaussian distribution
$\mathcal{P}=\mathcal{N}(\mu,\Sigma)$ with the center $\mu$ and covariance
matrix $\Sigma$, the Mahalanobis Distance measures a sample $x$’s distance to
this distribution $\mathcal{P}$ by calculating:

$\mathcal{D}(x,\mathcal{P})=(x-\mu)^{T}\Sigma^{-1}(x-\mu)$ (7)

Intuitively, the smaller Mahalanobis Distance the sample $x$ has, the larger
density score it will receive. Note that the density function of the
distribution $\mathcal{P}$ is:
$p(x,\mathcal{P})\propto\exp(-\frac{1}{2}(x-\mu)^{T}\Sigma(x-\mu)).$
Therefore, a sample $x$ with a higher density score is more likely to belong
to the distribution $\mathcal{P}$. The attack method in [33] constrains the
sample-wise Mahalanobis distance between the generated adversarial example
$x^{\prime}$ and the clean sample $x$, which is defined as:

$\mathcal{D}(x^{\prime},x,\mathcal{P})=(x^{\prime}-x)^{T}\Sigma^{-1}(x^{\prime}-x)$
(8)

Notably, if $x$ is a clean sample, it will be close to the clean distribution
$\mathcal{P}$, so it will have a small Mahalanobis Distance
$\mathcal{D}(x,\mathcal{P})$. Thus, penalizing the term
$\mathcal{D}(x^{\prime},x,\mathcal{P})$ will help the adversarial example
$x^{\prime}$ also have a small $\mathcal{D}(x^{\prime},\mathcal{P})$ (by
Triangle inequality). Therefore, $x^{\prime}$ is also highly likely to follow
the clean distribution $\mathcal{P}$.

Figure 2: Out-of-Distribution Adversarial Examples can be Easily Detected, by
human experts or OOD detection.

(a) CIS Fraud. (b) Home Credit. (c) Criteo. Figure 3: Imposing Small Mix
Mahalanobis Distance Helps Generating In-Distribution Samples

###  IV-B Mixed Mahalanobis Distance

In this work, we extend the idea of Mahalanobis Distance to mixed-type data.
Overall, we first define a Generalized Covariance Matrix specifically for
mixed-type data, and then we define Mix-Mahalanobis Distance based on the
Generalized Covariance Matrix (similar to the definition in Eq.(8)).
Specifically, we consider that the attacker has the knowledge of a sufficient
amount of clean data samples and we define the clean data matrix,
$X=\\{(x_{n},x_{c})_{j}\\}_{j=1,...,N}$, which is composed of $N$ different
clean samples. We also denote $X=(X_{n},X_{c})$, where each column of $X_{n}$
represents a numerical feature and $X_{c}$ denotes the categorical features.
In $X_{c}$, we encode each categorical feature of each sample into its one-hot
representation. For example, a column in the matrix $X_{c}$ represents whether
the (categorical) feature $i$ of these samples belongs to the category $j$
(e.g. whether the gender is ’female’). Based on this definition of $X$, we can
define the Generalized Covariance Matrix as:

$\hat{\Sigma}_{M}=\frac{1}{N-1}~{}\tilde{X}^{T}\cdot\tilde{X}$ (9)

where $\tilde{X}$ is the centered matrix of $X$: $\tilde{X}=X-\bar{X}$. In
this Generalized Covariance Matrix $\hat{\Sigma}_{M}$, each element
$(\hat{\Sigma}_{M})_{i,j}$ measures the relation between a pair of features
$(i,j)$:

  1. 1.

If feature $i$ is numerical and feature $j$ is numerical, it estimates the
covariance between features $i$ and $j$ as

$(\hat{\Sigma}_{M})_{i,j}=\text{cov}(X[i],X[j])$

  2. 2.

If feature $i$ is numerical and feature $j$ is categorical, since the column
$X[j]$ is the one-hot representation which only contains $0$ and $1$, the term
$(\hat{\Sigma}_{M})_{i,j}$ becomes:

$(\hat{{\Sigma_{M}}})_{i,j}=\frac{N_{0}N_{1}}{N(N-1)}(\bar{X_{0}}[i]-\bar{X_{1}}[i])$

where $N_{0}$ and $N_{1}$ denote the number of samples in $X$ whose feature
$j$ belongs to the category $0$ and $1$ respectively; and $\bar{X_{0}}[i]$ and
$\bar{X_{1}}[i]$ denote the average value of feature $i$ of samples whose
feature $j$ belongs to the category $0$ and category $1$, respectively.
Intuitively, this term measures the interaction between a numerical feature
$i$ and a categorical feature $j$. For example, if
$(\hat{{\Sigma_{M}}})_{i,j}$ is much larger than 0, the average value of
feature $i$ of samples in category $0$ is much larger than that in category
$1$. It suggests that there is a great discrepancy of feature $i$ between
different categories of feature $j$.

  3. 3.

If feature $i$ is categorical and feature $j$ is categorical, it becomes:

$(\hat{{\Sigma_{M}}})_{i,j}=\frac{N_{1,0}\cdot N_{0,1}-N_{0,0}\cdot
N_{1,1}}{N\cdot(N-1)}$

where we use $N_{(\cdot,\cdot)}$ to denote the number of samples that belong
to each individual category (for both feature $i$ & $j$). For example,
$N_{1,0}$ is the number of samples whose feature $i$ is $1$ and feature $j$ is
$0$. The square of this term is widely used as a chi-squared statistic in
correspondence analysis [36] to test the (in)-dependence of two categorical
variables.

Mixed Mahalanobis Distance: Equipped with the Generalized Covariance Matrix,
we follow the strategy similar to Eq.(8) to define the Mahlanobis Distance for
mixed-type data. Since the clean data matrix $X$ contains one-hot
representations, $X$ is not full-rank and $\hat{\Sigma}_{M}$ is not
invertible. Thus, we approximate the inverse covariance matrix
$(\hat{\Sigma}_{M})^{-1}$ by only preserving its first $m$ eigenvectors. In
detail, we first conduct eigenvalue decomposition for $\hat{\Sigma}_{M}$:
$(\hat{\Sigma}_{M})^{\prime}=V\cdot S\cdot V^{-1}$, where $V$ is the
eigenvectors and $S$ is the diagonal matrix whose non-zero elements are the
top $m$ eigenvalues of $\hat{\Sigma}_{M}$. In this way, we get the inverse
covariance matrix $(\hat{\Sigma}_{M})^{-1}=V\cdot S^{-1}\cdot V^{-1}$, and we
have the Mix-Mahalanobis Distance between the adversarial sample $x^{\prime}$
and clean sample $x$ as:

$\mathcal{D}(x^{\prime},x)=(x^{\prime}-x)^{T}(\hat{\Sigma}_{M})^{-1}(x^{\prime}-x)$
(10)

During the algorithm of M-Attack, when we solve the problem in Eq.(1), we can
satisfy the constraint (iii): $\mathcal{D}(x^{\prime},x)\leq\epsilon_{3}$ by
penalizing the large $\mathcal{D}(x^{\prime},x)$. In detail, because the term
$\mathcal{D}(x^{\prime},x)$ is differentiable in terms of $x^{\prime}$, we
have an alternative objective for Eq.(1), which is defined as:

$\displaystyle\begin{split}\max~{}~{}~{}~{}~{}~{}&\mathcal{L}(F(x^{\prime}_{n},x^{\prime}_{c}),y)-\lambda\cdot\mathcal{D}((x^{\prime}_{n},x^{\prime}_{c}),(x_{n},x_{c}))\\\
\text{s.t. }&\begin{cases}||x^{\prime}_{n}-x_{n}||_{1}\leq\epsilon_{1}\\\
||x^{\prime}_{c}-x_{c}||_{0}\leq\epsilon_{2}\\\ \end{cases}\end{split}$ (11)

where $\lambda>0$ controls the trade-off between the loss and Mix-Mahalanobis
Distance. Facilitated with the introduced method in Section III, we can
successfully solve this problem in Eq.(11).

(a) CIS Fraud. $(\epsilon_{1}=0.6,\epsilon_{2}=3,\lambda=6$) (b) CIS Fraud.
$(\epsilon_{1}=0.6,\epsilon_{2}=4,\lambda=6)$ (c) CIS Fraud
$(\epsilon_{1}=0.6,\epsilon_{2}=4,\lambda=10)$ (d) Home Credit.
$(\epsilon_{1}=0.3,\epsilon_{2}=2,\lambda=6)$ (e) Home Credit.
$(\epsilon_{1}=0.3,\epsilon_{2}=4,\lambda=6)$ (f) Home Credit.
$(\epsilon_{1}=0.3,\epsilon_{2}=4,\lambda=10)$ (g) Criteo.
$(\epsilon_{1}=0.6,\epsilon_{2}=3,\lambda=2)$ (h) Criteo.
$(\epsilon_{1}=0.6,\epsilon_{2}=4,\lambda=2)$ (i) Criteo.
$(\epsilon_{1}=0.6,\epsilon_{2}=4,\lambda=4)$ Figure 4: M-Attack vs. Baselines
by comparing Computational Cost and Attack Successful Rate

##  V Experiment

In this section, we validate the effectiveness of our proposed M-Attack and
Mix-Mahalanobis Distance. In detail, in Section V-B, we first verify that
imposing a small Mix-Mahalanobis Distance helps generating in-distribution
adversarial examples. Then, we compare the performance M-Attack with baseline
attack methods in Section V-C and Section V-D. Before introducing the
experimental results, we first introduce the basic experimental settings and
baselines.

###  V-A Experimental Settings

In this subsection, we introduce the datasets and baseline methods studied in
this paper.

####  V-A1 Datasets

We mainly conduct the experiments on three datasets, IEEE-CIS transaction
dataset111https://www.kaggle.com/competitions/ieee-fraud-detection, Home
Credit Default Risk Dataset222https://www.kaggle.com/competitions/home-credit-
default-risk, and Criteo Display Advertising
dataset333https://www.kaggle.com/c/criteo-display-ad-challenge. For all these
datasets, we only preserve the categorical features which have no more than
$50$ categories:

  * •

IEEE-CIS transaction data contains transaction records from e-commerce, which
contain the transaction summary and identify information of clients. The task
is to predict if a transaction is benign or fraudulent. It contains 108
numerical features and 32 categorical features.

  * •

Home Credit Default Risk contains historic records of loan applicant’s
demographic information and bank account information. The goal is to predict
whether a loaner will pay back his/her loan. It contains 73 numerical features
and 28 categorical features.

  * •

The Criteo Display Advertising Challenge Dataset is about solving the machine
learning task: given a user and the webpage he is visiting, whether he will
click on a given advertisement. It contains 13 numerical features and 7
categorical features.

For all datasets, we train a two layer Multilayer Perceptron (MLP) model with
64 hidden nodes for the classification tasks, and we will leave other popular
classifiers, such as tree based methods [37, 38] for one future work.

####  V-A2 Baselines.

To the best of our knowledge, there is no existing (popular) baseline methods
for the studied problem. Therefore, we compare our proposed M-Attack with the
combination of existing attack methods to sequentially perturb the categorical
features and numerical features. In detail, we consider baseline methods:

  * •

$l_{1}$ PGD + Search: It first applies $l_{1}$ PGD [5] to perturb numerical
features. Then, it adopts the search method [7] to perturb categorical
features. The search method first perturbs each categorical one-by-one and
selects the top $\epsilon_{2}$ features with the highest impact on the model
output. Then, it traverses all combinations of these $\epsilon_{2}$ features
to find the perturbation with the highest loss value.

  * •

$l_{1}$ PGD + Greedy: It also conducts $l_{1}$ PGD attack and then finds the
$\epsilon_{2}$ features with the highest impact on the model output. Then, it
perturbs these $\epsilon_{2}$ features greedily. For each feature, it assigns
this feature with the category which leads to maximal loss and keeps the other
perturbed features fixed, so it avoids searching all combinations.

Note we can also first perturb the categorical features, and then perturb the
numerical features. We find this strategy has the similar empirical
performance with our considered baselines, so we only report the performance
“$l_{1}$ PGD + Search” & “$l_{1}$ PGD + Greedy”.

###  V-B Mix Mahalanobis Distance Helps Generating In-Distribution Samples

In this experiment, we first verify that regularizing our proposed Mix-
Mahalanobis Distance can effectively help the generated adversarial examples
to be closer to the clean data distribution. To confirm this point, in all
three datasets, we follow the strategy similar to [31, 39] to first estimate
the distribution of clean data samples, then we test whether the generated
adversarial examples is clearly deviated from our estimated clean data
distribution. Specifically, in our experiment in Figure 3, we apply the Kernel
Density Estimation [10] to estimate the distribution of all clean training
samples. Then, in Figure 3, we calculate the estimated Log-Likelihood (density
score) of clean test samples (green), as well as the generated adversarial
examples (via M-Attack) with a strong Mix Mahalanobis Distance regularization
$\lambda=6$ (blue), and adversarial examples with no Mix Mahalanobis Distance
regularization $\lambda=0$ (red), and report their frequency in each interval
of Log-Likelihood. From the result, we can see that the most clean test
samples (green) have a high Log-Likelihood value, which suggests that they are
close to the estimated clean data distribution. For adversarial examples which
generated via strong Mahalanobis Distance regularization (blue), most samples
also have high Log-Likelihood. However, for adversarial examples which
generated without Mahalanobis Distance regularization (red), they have
significantly lower Log-Likelihood values. Thus, they are significantly
deviated from our estimated clean distribution. As a conclusion, this
experimental results demonstrate that imposing a small Mix Mahalanobis
Distance can help the generated adversarial examples closer to the clean
distribution, which can facilitate the samples evade potential defections.

(a) CIS Fraud. $(\epsilon_{1}=0.3,\epsilon_{2}=2)$ (b) CIS Fraud.
$(\epsilon_{1}=0.3,\epsilon_{2}=4)$ (c) CIS Fraud.
$(\epsilon_{1}=0.6,\epsilon_{2}=2)$ (d) Home Credit.
$(\epsilon_{1}=0.3,\epsilon_{2}=2)$ (e) Home Credit.
$(\epsilon_{1}=0.3,\epsilon_{2}=4)$ (f) Home Credit.
$(\epsilon_{1}=0.6,\epsilon_{2}=2)$ (g) Criteo.
$(\epsilon_{1}=0.3,\epsilon_{2}=2)$ (h) Criteo.
$(\epsilon_{1}=0.3,\epsilon_{2}=4)$ (i) Criteo.
$(\epsilon_{1}=0.6,\epsilon_{2}=2)$ Figure 5: M-Attack vs. Baselines by
comparing M-Distance and Loss Trade-off

###  V-C Effectiveness and Efficiency of M-Attack

Based on the discussion in Section V-B, we conduct experiments to verify
whether M-Attack can evade the OOD detection methods and successfully attack
the model. In this paper, we consider the OOD detection method is based on the
method introduced in Section V-B: if a sample has a low Log-Likelihood value
(smaller than the 10-th percentile of clean samples), we flag it as “abnormal”
and refuse prediction. In Figure 4, we report the successful attacking rate
for each method: for a test sample which the classifier $x$ can correctly
classify, if the model has a wrong prediction after adversarial perturbation,
and it is also not flagged as “abnormal”, we count it as a successful attack.
Meanwhile, we also record the average computing time to generate each
adversarial example (in seconds), where all experiments are conducted in a
single NVIDIA Tesla K80 GPU. From the results in Figure 4, we can see that
M-Attack has higher successful rate compared with baseline methods in CIS and
Criteo dataset. The Home Credit dataset is easier to be attacked, so all
methods can achieve high successful rate. Moreover, in each dataset, we
usually only need perturb a few features to achieve a high successful
attacking rate. In terms of computing cost, the “$l_{1}$ PGD + greedy” method
spend shorter time than other methods. However, M-Attack’s computing cost will
not increase with the increase of perturbation budget $\epsilon_{2}$, because
it always conducts a fixed number of gradient steps.

###  V-D Optimality of M-Attack

To have a deeper understanding of the behavior of M-Attack, in the experiment
in Figure 5, we compare M-Attack with baselines, in terms of their optimality
to solve the main problem in Eq.(1). In Figure 5, in each subfigure (with a
fixed $\epsilon_{1}$ and $\epsilon_{2}$), each single dot reports the average
loss value $\mathcal{L}(F(x^{\prime}),y)$ of targeted classifier and the
average Mix Mahalanobis Distance $\mathcal{D}(x^{\prime},x)$ for 100 randomly
chosen test samples, where the adversarial samples $x^{\prime}$ are obtained
via solving the Eq.(11) with a fixed value $\lambda$ (which controls the
regularization of Mix Mahalanobis Distance). For baseline methods, we can also
control their Mix Mahalanobis Distance by replacing their objective
$\mathcal{L}(F(x^{\prime}),y)$ with
$\mathcal{L}(F(x^{\prime}),y)-\lambda\mathcal{D}(x^{\prime},x)$. In the Figure
5, we report the performance with different choices of $\lambda$ for each
method, to demonstrate the trade-off relation between the maximized loss value
and the Mix Mahalanobis Distance. From the result, we can see when
$\epsilon_{1}$ and $\epsilon_{2}$ are fixed, when different attack methods
achieve the similar Mix Mahalanobis Distance, our proposed M-Attack can always
achieve the highest average loss value. Especially when the average Mix
Mahalanobis Distance is lower, the advantage of M-Attack over baselines is
more obvious. This suggests that the adversarial examples generated via
M-Attack can have better chance to attack the targeted classifier and preserve
the Mix Mahalanobis Distance. It is because M-Attack simultaneously updates
the numerical and categorical perturbations, so it enjoys the benefit to
better optimize the term such as Mix Mahalanobis Distance. Since the
categorical features and numerical features are highly interactive in Mix
Mahalanobis Distance, it is sub-optimal to optimize them sequentially, as the
baseline methods.

##  VI Conclusion

To fill in the research gap on generating adversarial examples with mixed-type
data, in this work, we propose M-Attack, which is designed to attack both the
numerical and the categorical features in a unified gradient-based algorithm.
The experimental results on three real-world datasets illustrate that our
proposed M-Attack can efficiently and effectively find close-to-true-
distribution adversarial examples.

## References

  * [1] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu.  Towards deep learning models resistant to adversarial attacks.  In International Conference on Learning Representations, 2018.
  * [2] Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy.  Explaining and harnessing adversarial examples.  arXiv preprint arXiv:1412.6572, 2014.
  * [3] Florian Tramer and Dan Boneh.  Adversarial training and robustness for multiple perturbations.  Advances in Neural Information Processing Systems, 32, 2019.
  * [4] Xingxing Wei, Siyuan Liang, Ning Chen, and Xiaochun Cao.  Transferable adversarial attacks for image and video object detection.  In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pages 954–960, 2019.
  * [5] Pratyush Maini, Eric Wong, and Zico Kolter.  Adversarial robustness against the union of multiple perturbation models.  In International Conference on Machine Learning, pages 6640–6650. PMLR, 2020.
  * [6] Puyudi Yang, Jianbo Chen, Cho-Jui Hsieh, Jane-Ling Wang, and Michael I Jordan.  Greedy attack and gumbel attack: Generating adversarial examples for discrete data.  J. Mach. Learn. Res., 21(43):1–36, 2020.
  * [7] Hongyan Bao, Yufei Han, Yujun Zhou, Yun Shen, and Xiangliang Zhang.  Towards understanding the robustness against evasion attack on categorical data.  In International Conference on Learning Representations, 2021.
  * [8] Özlem Özdemir and Levent Boran.  An empirical investigation on consumer credit default risk.  Technical report, Discussion Paper, 2004.
  * [9] Weitang Liu, Xiaoyun Wang, John Owens, and Yixuan Li.  Energy-based out-of-distribution detection.  Advances in Neural Information Processing Systems, 33:21464–21475, 2020.
  * [10] Zdravko I Botev, Joseph F Grotowski, and Dirk P Kroese.  Kernel density estimation via diffusion.  The annals of Statistics, 38(5):2916–2957, 2010.
  * [11] Eric Nalisnick, Akihiro Matsukawa, Yee Whye Teh, Dilan Gorur, and Balaji Lakshminarayanan.  Do deep generative models know what they don’t know?  arXiv preprint arXiv:1810.09136, 2018.
  * [12] Ali Shafahi, W Ronny Huang, Mahyar Najibi, Octavian Suciu, Christoph Studer, Tudor Dumitras, and Tom Goldstein.  Poison frogs! targeted clean-label poisoning attacks on neural networks.  Advances in neural information processing systems, 31, 2018.
  * [13] Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Logan Engstrom, Brandon Tran, and Aleksander Madry.  Adversarial examples are not bugs, they are features.  Advances in neural information processing systems, 32, 2019.
  * [14] Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan.  Theoretically principled trade-off between robustness and accuracy.  In International conference on machine learning, pages 7472–7482. PMLR, 2019.
  * [15] Volodymyr Kuleshov, Shantanu Thakoor, Tingfung Lau, and Stefano Ermon.  Adversarial examples for natural language classification problems.  2018\.
  * [16] Javid Ebrahimi, Anyi Rao, Daniel Lowd, and Dejing Dou.  Hotflip: White-box adversarial examples for text classification.  arXiv preprint arXiv:1712.06751, 2017.
  * [17] Ji Gao, Jack Lanchantin, Mary Lou Soffa, and Yanjun Qi.  Black-box generation of adversarial text sequences to evade deep learning classifiers.  In 2018 IEEE Security and Privacy Workshops (SPW), pages 50–56. IEEE, 2018.
  * [18] Wei Jin, Yaxing Li, Han Xu, Yiqi Wang, Shuiwang Ji, Charu Aggarwal, and Jiliang Tang.  Adversarial attacks and defenses on graphs.  ACM SIGKDD Explorations Newsletter, 22(2):19–34, 2021.
  * [19] Richard J Bolton and David J Hand.  Statistical fraud detection: A review.  Statistical science, 17(3):235–255, 2002.
  * [20] Sushmito Ghosh and Douglas L Reilly.  Credit card fraud detection with a neural-network.  In System Sciences, 1994. Proceedings of the Twenty-Seventh Hawaii International Conference on, volume 3, pages 621–630. IEEE, 1994.
  * [21] Trishan Panch, Heather Mattie, and Leo Anthony Celi.  The “inconvenient truth” about ai in healthcare.  NPJ digital medicine, 2(1):1–3, 2019.
  * [22] Sandeep Reddy, Sonia Allan, Simon Coghlan, and Paul Cooper.  A governance model for the application of ai in health care.  Journal of the American Medical Informatics Association, 27(3):491–497, 2020.
  * [23] Kenneth J Rothman, Sander Greenland, Timothy L Lash, et al.  Modern epidemiology, volume 3.  Wolters Kluwer Health/Lippincott Williams & Wilkins Philadelphia, 2008\.
  * [24] Kenneth J Rothman.  Epidemiology: an introduction.  Oxford university press, 2012.
  * [25] Paul Resnick and Hal R Varian.  Recommender systems.  Communications of the ACM, 40(3):56–58, 1997.
  * [26] Jesús Bobadilla, Fernando Ortega, Antonio Hernando, and Abraham Gutiérrez.  Recommender systems survey.  Knowledge-based systems, 46:109–132, 2013.
  * [27] Francesco Ricci, Lior Rokach, and Bracha Shapira.  Introduction to recommender systems handbook.  In Recommender systems handbook, pages 1–35. Springer, 2011.
  * [28] Steven Diamond and Stephen Boyd.  Cvxpy: A python-embedded modeling language for convex optimization.  The Journal of Machine Learning Research, 17(1):2909–2913, 2016\.
  * [29] John Duchi, Shai Shalev-Shwartz, Yoram Singer, and Tushar Chandra.  Efficient projections onto the l 1-ball for learning in high dimensions.  In Proceedings of the 25th international conference on Machine learning, pages 272–279, 2008.
  * [30] Eric Jang, Shixiang Gu, and Ben Poole.  Categorical reparameterization with gumbel-softmax.  In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
  * [31] Shuhuai Ren, Yihe Deng, Kun He, and Wanxiang Che.  Generating natural language adversarial examples through probability weighted word saliency.  In Proceedings of the 57th annual meeting of the association for computational linguistics, pages 1085–1097, 2019.
  * [32] Anisie Uwimana and Ransalu Senanayake.  Out of distribution detection and adversarial attacks on deep neural networks for robust medical image analysis.  arXiv preprint arXiv:2107.04882, 2021.
  * [33] Ecenaz Erdemir, Jeffrey Bickford, Luca Melis, and Sergul Aydore.  Adversarial robustness with non-uniform perturbations.  Advances in Neural Information Processing Systems, 34:19147–19159, 2021.
  * [34] Roy De Maesschalck, Delphine Jouan-Rimbaud, and Désiré L Massart.  The mahalanobis distance.  Chemometrics and intelligent laboratory systems, 50(1):1–18, 2000\.
  * [35] Goeffrey J McLachlan.  Mahalanobis distance.  Resonance, 4(6):20–26, 1999.
  * [36] Michael Greenacre.  Correspondence analysis in practice.  chapman and hall/crc, 2017.
  * [37] Tianqi Chen and Carlos Guestrin.  Xgboost: A scalable tree boosting system.  In Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining, pages 785–794, 2016.
  * [38] Mariana Belgiu and Lucian Drăguţ.  Random forest in remote sensing: A review of applications and future directions.  ISPRS journal of photogrammetry and remote sensing, 114:24–31, 2016\.
  * [39] Chaowei Xiao, Bo Li, Jun Yan Zhu, Warren He, Mingyan Liu, and Dawn Song.  Generating adversarial examples with adversarial networks.  In 27th International Joint Conference on Artificial Intelligence, IJCAI 2018, pages 3905–3911. International Joint Conferences on Artificial Intelligence, 2018.