\section{Introduction}
Concentration inequalities are essential tools for ensuring the validity of many statistical procedures; let us cite for instance \cite{FMS} for classification problems,
\cite{M03} for model selection, and \cite{BRT} for high dimensional procedures (see also \cite{AD11} and \cite{Z17} in a dependent framework).

These inequalities are not easy to prove in a dependent context; up to now this has  been done under quite restrictive assumptions,
and mainly for bounded functionals of the variables in a stationary/homogeneous context. As a non exhaustive list,
let us quote \cite{Sa00}, \cite{Ri00}, \cite{DGW04}, \cite{Ad08}, \cite{DF15} and \cite{DG15}.
Among these references, the case of unbounded functionals has been  investigated in \cite{Ad08}  for geometrically ergodic Markov chains,  and in
\cite{DF15} for iterated random functions satisfying a mean-contraction condition (see condition \eqref{contract} below, with $F_n=F$).

In the paper \cite{DF15}, the authors obtained very precise inequalities for Lipschitz
functionals of the chain, by assuming moreover a Lipschitz condition on the function that generates the chain (see condition  \eqref{c2old} below).
However, this last condition is in fact quite restrictive, and does not hold for many natural models satisfying the  mean-contraction  property.

In the present paper we  enlarge the class of Markov chains studied in \cite{DF15}, by considering non-homogeneous Markov chains obtained through composition of random functions
(see the recursive mechanism \eqref{Mchain} below), and by making no extra assumptions  than the (uniform) mean-contraction \eqref{contract}.
As in \cite{DF15},
we shall use the decomposition of the functional of the chain in terms of martingale differences, as first introduced by Yurinskii \cite{Yu}. This method  is well adapted to the non-homogeneous Markov context, because it is   intrinsically a non-stationary method.
Following this approach, we obtain deviation and moment inequalities for separately Lipschitz functionals of the chain that are driven by the distribution of some
dominating random variables.

The present article was conceived within the general framework  of non stationary time series, which is now widely discussed in the context global warming \cite{C00}.
Besides temperatures or ozone concentration, most of the real life phenomena present trends and periodicities. A first excellent view of those questions may be found in \cite{BD87}, but this is a  linear view of time series analysis. It appears important to consider cases where the dynamic of the models itself is non time-homogeneous.
For instance  \cite{Da18} and \cite{BD17} provide different views for a more relevant  dynamical approach including local stationarity and non-periodic features.
The present paper aims at developing reasonable concentration and probability inequalities for  non-homogeneous Markov chains able to model some of the above features.

Before going into further details, let us give a simple class of examples to which our results apply.
We consider a generalized ${\mathbb R}^k$-valued  auto-regressive processes
\begin{equation}\label{GARM}
X_{n}= A_n X_{n-1} + B_n  \, ,
\end{equation}
where $A_n$ is a random $k \times k$  matrix and $B_n$ is an ${\mathbb R}^k$-valued random variable. Here $\varepsilon_n= (A_n, B_n)$ are independent random
variables, and $(\varepsilon_n)_{n \geq 2}$ is independent of the initial random variable $X_1$. Let $| \cdot |$ be a norm on ${\mathbb R}^k$.
Then, the Markov chain $X_n$  satisfies the mean contraction condition  \eqref{contract} for the norm  $| \cdot |$  as soon as
\begin{equation}\label{MCGA}
\sup_{n \geq 2} {\mathbb E}[|A_n|] \leq \rho \quad \text{for some $\rho <1$},
\end{equation}
where as usual $|A_n|= \sup_{|x|=1} |A_n x|$.

Model \eqref{GARM} contains a lot of natural examples (see for instance \cite{DF}, Sections 2.2 and 2.3), but does not fit within the framework of \cite{DF15}; moreover, it
has no reason to be mixing in the sense of Rosenblatt \cite{Ro} without further assumptions on the distribution of $(\varepsilon_n)_{n \geq 2}$. Recall that the chain
$X_n$ is non-homegeneous, since we do not assume here that the variables $\varepsilon_n$ are iid.

Let now $f: ({{\mathbb R}^k})^n \mapsto {\mathbb R}$ be a separately Lipschitz function, such that
\begin{equation} \label{SepLip}
|f(x_1, x_2, \ldots, x_n)-f(x'_1, x'_2, \ldots, x'_n)| \, \leq \, |x_1-x'_1|+\cdots +  |x_n-x'_n| \, ,
\end{equation}
and let also $S_n= f(X_1, \ldots, X_n) - {\mathbb E} [f(X_1, \ldots, X_n)]$.

For simplicity, let us consider the case where the chain starts at $X_1=0$. Assuming  that
$ \|A_n\|_p^p:= {\mathbb E}[|A_n|^p] < \infty$ and $\| B_n\|_p^p:={\mathbb E}[|B_n|^p]< \infty$ for any $n\geq 2$ and some $p>1$, we infer from \eqref{HGA}
(control of the ${\mathbb L}^p$-norm of the dominating  variables $H_k(X_{k-1}, \varepsilon_k)$ defined in \eqref{defHk}) and Propositions \ref{MZIP} and \ref{VBEI} that
$$
\| S_n \|_p^p \leq    C(p, \rho)  \left(
 \sum_{k=3}^n \|X_{k-1}\|_p^2 \|A_k\|_p^2 + \sum_{k=2}^n   \|B_k\|_p^2 \right)^{2}  \quad \text{if $p\geq 2$},
$$
and
$$
\| S_n \|_p^p \leq    C(p, \rho)  \left (
 \sum_{k=3}^n \|X_{k-1}\|_p^p \|A_k\|_p^p + \sum_{k=2}^n   \|B_k\|_p^p \right ) \quad \text{if $p \in (1,2)$},
$$
for some constant $C(p, \rho)$ depending only on $(p, \rho)$. These inequalities are satisfactory, because if $X_n=B_n$ for $n \geq 2$ (case $A_n =0$), we recover  for $p \geq 2$ the
usual Marcinkiewicz-Zygmund inequalities  (see \cite{R09}) for ${\mathbb L}_p$-norms of sums of independent random variables, and for $p \in (1,2)$ the usual von Bahr-Esseen inequalities
(see \cite{P10}).  Note that, under the stronger condition  than \eqref{MCGA}: $\sup_{n \geq 2} \|A_n\|_p \leq \rho$
(${\mathbb L}^p$-contraction), and if $\sup_{n \geq 2} \|B_n\|_p  < \infty$, we obtain that $\|S_n\|_p = O(\sqrt n)$ if $p\geq 2$ and $\|S_n\|_p = n^{1/p}$ if $p \in (1,2)$, which is exactly what we could expect
for ${\mathbb L}^p$-norms of partial sums in  a quasi-stationary regime.

Under more restrictive conditions on $(A_n, B_n)_{n \geq 2}$, one can also obtain some semi-exponential bounds for the deviation
of $S_n$. For the sake of simplicity, let us assume  that  $\sup_{n \geq 2} \|A_n\|_\infty \leq \rho$ (uniform contraction) and that
there exist $\kappa >0, \alpha \in (0,1)$ such that
\begin{equation}\label{unifexp}
  \sup_{k \geq 2}  {\mathbb E}\left [ \exp   \left \{  \kappa |B_k|^{\frac{2\alpha}{1- \alpha}} \right \}\right ] < \infty  \, .
\end{equation}
It is then easy to see that dominating variables $H_k(X_{k-1}, \varepsilon_k)$ defined in \eqref{defHk} also satisfy the uniform bound
\eqref{unifexp} (for the same $\alpha$ and a different $\kappa$, say $\kappa'$). Hence, it follows from Proposition \ref{propExp} that
\begin{eqnarray}\label{finintro}
  {\mathbb P}\left( | S_n | \geq  n x\right)
   \leq   C( x)  \exp\left\{- K x^{2\alpha} n^\alpha \right\} \, ,
\end{eqnarray}
for any $x>0$,
where  the positive constant $K$ depends only on $(\rho, \alpha, \kappa')$, and
$$
C(x)=  2+ c(\alpha, \rho, \kappa')    \left( \frac{1 }
{ x^{2\alpha} }  + \frac{1}{  x^2 } \right) \, .
$$
In particular, we obtain from \eqref{finintro} the following moderate deviation behavior: for any $\delta \in (1/2, 1]$, there exist $a>0$ such that
\begin{equation}\label{etlabete}
 {\mathbb P}\left( | S_n | \geq  n^\delta \right)= O \left ( \exp \left \{ - a n^{\alpha(2\delta -1)}  \right \} \right ) \, .
\end{equation}
 Note that, for $\delta=1$,  this is in accordance with the best possible
rate for large deviation of sums of martingale differences (see Theorem 2.1 in \cite{Fx1}).

\section{Composition of random functions}\label{SEC2}

Let $(\Omega, {\mathcal A}, {\mathbb P})$ be a probability space.
Let $({\mathcal X}, d)$ and  $({\mathcal Y}, \delta)$ be two complete separable metric spaces.
Let $(\varepsilon_i)_{i \geq 2}$ be a sequence of independent  ${\mathcal Y}$-valued
random variables. Let $X_1$ be a ${\mathcal X}$-valued random variable independent of $(\varepsilon_i)_{i \geq 2}$. We consider the Markov chain $(X_i)_{i \geq 1}$
such that
\begin{equation}\label{Mchain}
X_n=F_n(X_{n-1}, \varepsilon_n), \quad \text{  $n\geq 2$},
\end{equation}
where $F_n: {\mathcal X} \times {\mathcal Y} \rightarrow {\mathcal X}$
is such that
\begin{equation}\label{contract}
{\mathbb E}\big [ d\big(F_n(x, \varepsilon_n), F_n(x', \varepsilon_n)\big) \big] \leq
\rho \, d(x, x')
\end{equation}
for some constant $\rho \in [0,1)$ not depending on $n$.

\smallskip

In the paper \cite{DF15}, the authors studied a class of homogeneous Markov chains (that is, with  $F_n=F$ and   $(\varepsilon_i)_{i \geq 2}$ a sequence of  i.i.d.\ random variables) satisfying \eqref{contract} and
the condition
\begin{equation}\label{c2old}
d(F(x,y), F(x,y')) \leq C \,\delta(y,y')
\end{equation}
for some positive constant $C$. Under this additional constraint, they obtained  very precise upper bounds for the deviation of separately Lipschitz functionals
of the chain; this is possible, because in that case, the martingales differences $M_k$ from McDiarmid's decomposition are bounded by a function of $\varepsilon_k$, which is then independent of the past $\sigma$-field of the chain.

However, condition \eqref{c2old} is quite restrictive, and is not satisfied for many natural models (a short list of such models is presented below). In the present paper, we shall not assume that
\eqref{c2old} is satisfied. In this more general setting, the dominating random variables are
\begin{equation}\label{defHk}
H_k(X_{k-1}, \varepsilon_k) \quad \text{where} \quad
H_{k}(x,y)= \int d(F_k(x,y),F_k(x,y'))P_{\varepsilon_k}(dy')
\end{equation}
(see Proposition \ref{McD} below).  The main difference with \cite{DF15} is that these dominating random variables are no longer independent from the past
$\sigma$-field of the chain. Hence, the  deviations bounds that we obtain are not as precise  as in \cite{DF15}, but apply to a much larger class of
(non homogeneous) Markov chains.

\smallskip

\begin{rem}\label{remalpha}
Note that if \eqref{contract} holds for the distance $d$, then, for any $\alpha \in (0,1]$,  it also hold for the distance
$d_\alpha(x,y)=(d(x,y))^\alpha$ with $\rho^\alpha$ instead of $\rho$.
 This is elementary, but nevertheless important:
it means that we can also obtain concentration inequalities for separately Lipschitz functions with respect to $d_\alpha$ by controlling
the behavior of $H_{k,\alpha}(X_{k-1}, \varepsilon_k)$ (whose definition is as in \eqref{defHk} for the distance $d_\alpha$).
Note that separately Lipschitz functions with respect to $d_\alpha$ are less and less regular as $\alpha$ approaches 0.

\end{rem}

\smallskip

\begin{rem}
Let us quote an error in the paper \cite{DF15}. The inequality (1.4) of that paper gives an upper bound for the
quantity ${\mathbb E}[H(d(X_n,x_0))]$ when $H$ is any increasing function from ${\mathbb R}^+$ to ${\mathbb R}^+$.
However this upper bound is not true in general under the assumption (1.2) of \cite{DF15} (which is similar to our assumption
\eqref{contract}), but it holds  under the much more restrictive assumption $  d(F(x, y), F(x', y))  \leq
\rho \, d(x, x')$. The error comes from the fact that the first version of the paper  \cite{DF15} was written under this more restrictive assumption.
Note that this wrong inequality was not used at any points in the proofs of the main results in \cite{DF15}, but only in Items 4 of Remarks 3.1 and 3.2
(which are therefore not correct).

\end{rem}

\subsection{Examples}
In this subsection, we give a non exhaustive list of models satisfying condition \eqref{contract}, and we show how to control the
moments of the dominating  variables $H_k(X_{k-1}, \varepsilon_k)$ defined by \eqref{defHk}. For the sake of simplicity, we shall only deal with the moments
of order $p$ of $H_k(X_{k-1}, \varepsilon_k)$, but similar computations may be done for exponential moments.
We refer to \cite{DFT12} and \cite{Da18} for more examples.

\begin{itemize}
\item
{\bf ARCH-type  models}. For which
$$
F_n(x,y)=M_{\theta_n}(x,y), \qquad \mbox{with}\quad M_{\theta}(x,y)=\sqrt{a^2x^2+b^2} \cdot y, \quad \theta=(a,b)\, .
$$
Thus the non stationarity appears simply from changes in the parameter $\theta_n=(a_n,b_n)$.
In that case \eqref{contract} is satisfied for $d(x,x')= |x-x'|$ provided $\sup_{n \geq 2}|a_n|{\mathbb E}[ |\varepsilon_n| ] = \rho$
for some $\rho <1$.

\medskip

For these models
$$
H_k(X_{k-1}, \varepsilon_k)= \sqrt{a_k^2X_{k-1}^2+b_k^2} \int | \varepsilon_k-y| P_{\varepsilon_k}(dy) \, ,
$$
and the moments of order $p$ of $H_k(X_{k-1}, \varepsilon_k)$ satisfy
$$
  \| H_k(X_{k-1}, \varepsilon_k) \|_p^p \leq 2^{p-1} {\mathbb E} \left [ \left (a_k^2X_{k-1}^2+b_k^2 \right )^{p/2}\right ] \| \varepsilon_k \|_p^p \, , \ \ \ p\geq 1.
$$

Those models are easy to extend in an $\R^k$-valued framework.
For instance, one can consider
$X_{n}= A_n(X_{n-1}) \, \varepsilon_n$, where $A_n(x)$ is a $k\times k$ matrix and $\varepsilon_n$  are ${\mathbb R}^k$-valued random variables.
Let $| \cdot |$ be a norm on ${\mathbb R}^k$, and $|A|= \sup_{|x|=1} |A_n x|$ be the associated
  matrix norm.  Now, if
$|A_n(x) -A_n(x')|  \leq a_n |x-x'|$,
then the  condition \eqref{contract} is satisfied as soon as  $\sup_{n \geq 2} a_n {\mathbb E}[ |\varepsilon_n| ] = \rho$
for some $\rho <1$.

\item  {\bf Switching models.} Many analogous models can be provided with a switching, e.g.\ for the first ARCH-model, such  a parametric model is given with ${\cal X}=\R$, ${\cal Y}=\R\times\{0,1\}$, a parameter $\theta=(a,b,a',b')\in \R^4$ and
$$
 M_\theta(x,y)=y_2\sqrt{a^2x^2+b^2} \cdot y_1+(1-y_2)\sqrt{a'^2x^2+b'^2} \cdot y_1 \, .
$$
Here $(\varepsilon_n)_{n \geq 2}$ is a sequence of independent random variables with values in ${\mathbb R} \times \{0, 1 \}$. Using the notation
$\varepsilon_n=(\varepsilon_n^{(1)}, \varepsilon_n^{(2)})$, we see that condition \eqref{contract} is satisfied as soon as
$$
  \sup_{n \geq 2} \  \left ( (1-\E [\varepsilon_n^{(2)}])|a_n|+ \E[\varepsilon_n^{(2)}]|a_n'| \right)\E[|\varepsilon_n^{(1)}|]= \rho
$$
for some $\rho <1$.

Now, similar computations as for the first example lead to
\begin{multline*}
  \| H_k(X_{k-1}, \varepsilon_k) \|_p^p \leq 4^{p-1} {\mathbb E} \left [ \left (a_k^2X_{k-1}^2+b_k^2 \right )^{p/2}\right ] \left \| \varepsilon_k^{(1)}  \varepsilon_k^{(2)} \right \|_p^p \\
  + 4^{p-1} {\mathbb E} \left [\left (a'^2_kX_{k-1}^2+b'^2_k \right )^{p/2}\right ]\left \| \varepsilon_k^{(1)} (1- \varepsilon_k^{(2)}) \right \|_p^p , \, \ \ \ p\geq 1.
\end{multline*}

\item {\bf Generalized ${\mathbb R}^k$-valued  auto-regressive processes}. We consider here the Model \eqref{GARM} presented in the introduction.
Recall that $A_n$ is a random $k \times k$  matrix and $B_n$ is an ${\mathbb R}^k$-valued random variable. Here $\varepsilon_n= (A_n, B_n)$ are independent random
variables, and $(\varepsilon_n)_{n \geq 2}$ is independent of the initial random variable $X_1$.  Model \eqref{GARM} is a composition of random functions as in \eqref{Mchain},
with
$$F_n(x,y)=F(x,y)=y_1 x + y_2 \, . $$

Let $| \cdot |$ be a norm on ${\mathbb R}^k$, and let  as usual $|A_n|= \sup_{|x|=1} |A_n x|$. The condition \eqref{contract} is satisfied as soon as
\eqref{MCGA} holds.

\medskip

For these models
$$
H_k(X_{k-1}, \varepsilon_k) \leq | X_{k-1}|  \int  |A_k-y  | P_{A_k}(dy) +  \int | B_k-y| P_{B_k}(dy) \, ,
$$
and the moments of order $p$ of $H_k(X_{k-1}, \varepsilon_k)$ satisfy
\begin{equation}\label{HGA}
  \| H_k(X_{k-1}, \varepsilon_k) \|_p^p \leq 4^{p-1} {\mathbb E} \left  [ |X_{k-1}|^p \right ] {\mathbb E} \left [ |A_k|^p \right ] + 4^{p-1} {\mathbb E} \left [ |B_k|^p \right ] , \ \ \ \ p\geq 1.
\end{equation}

\item {\bf INAR($1$) type models.} In this case, let $y=(y_0,y_1,y_2,\dots,y_p,\ldots)\in {\cal Y}=\N^{\N}$ and   $\varepsilon=(\varepsilon^{(0)},\varepsilon^{(1)},\ldots,\varepsilon^{(p)},\ldots)$, where $(\varepsilon^{(1)},\ldots,\varepsilon^{(p)},\ldots)$ is a sequence of i.i.d. integer valued random variables. The function $F$ is then given by
 $$
F(x,y)=y_0+\textbf{1}_{\{x\neq 0\}}\sum_{k=1}^x y_k\,.
$$
Here,  $(\varepsilon_n)_{n \geq 2}$ is an i.i.d.\ sequence distributed as $\varepsilon$. It is then easy to see that \eqref{contract} is satisfied
provided $\rho={\mathbb E}[\varepsilon^{(1)}]< 1$.

\medskip

We shall now give some hints to control the moments of the dominating random variables  $H_k(X_{k-1}, \varepsilon_k)$.
Let $ \tilde \varepsilon_k$ be distributed as $\varepsilon_k$ and  independent of $(\varepsilon_k, X_{k-1})$. We then have
that
$$
 H_k(X_{k-1}, \varepsilon_k) = {\mathbb E} \big[d(F_k(X_{k-1},\varepsilon_k),F_k(X_{k-1},\tilde \varepsilon_k)) \big| X_{k-1}, \varepsilon_k \big]   .
$$

For the INAR(1) model, we have
$$
H_k(X_{k-1}, \varepsilon_k)= \E \bigg[ \Big | (\varepsilon_k^{(0)}- \tilde \varepsilon_k^{(0)})+\textbf{1}_{\{X_{k-1}\neq 0\}}\sum_{i=1}^{X_{k-1}}
 ( \varepsilon^{(i)}_k - \tilde \varepsilon^{(i)}_k)\Big |  \  \bigg  | X_{k-1}, \varepsilon_k \bigg]\\
$$
By contraction, we get that
$$
 \| H_k(X_{k-1}, \varepsilon_k) \|_p^p \leq  \bigg \| (\varepsilon_k^{(0)}- \tilde \varepsilon_k^{(0)})+\textbf{1}_{\{X_{k-1}\neq 0\}}\sum_{i=1}^{X_{k-1}}
 ( \varepsilon^{(i)}_k - \tilde \varepsilon^{(i)}_k)\bigg \|_p^p , \, \ \ \ \ p\geq 1.
$$
For $p \geq 2$, applying the Marcinkiewicz-Zygmund inequality given in \cite{R09}, we  get that
$$
 \| H_k(X_{k-1}, \varepsilon_k) \|_p^p \leq  2^{(p-2)/2}  \|  \varepsilon^{(0)}-\tilde \varepsilon^{(0)}\|_p^p +  (p-1)^{p/2} 2^{(p-2)/2} {\mathbb E} \left [X_{k-1}^{ p/2} \right] \|  \varepsilon^{(1)}-\tilde \varepsilon^{(1)}\|_p^p \, .
$$
For $p \in (1,2)$, applying  the von-Bahr Essen inequality given in \cite{P10}, we get that
$$
 \| H_k(X_{k-1}, \varepsilon_k) \|_p^p \leq    \|  \varepsilon^{(0)}-\tilde \varepsilon^{(0)}\|_p^p +  2^{2- p} {\mathbb E} \left[X_{k-1} \right] \|  \varepsilon^{(1)}-\tilde \varepsilon^{(1)}\|_p^p \, .
$$

Note that non-stationary variants of this model can be obtained by considering  independent (but non i.i.d.)\ $\varepsilon_n$'s, with the constraint:
$\sup_{n\geq 2} {\mathbb E}[\varepsilon_n^{(1)}] < 1$.
\item
{\bf GLM-Poisson models.} Besides the standard ARCH-models the simplest case is that of Poisson ARCH--models, where $(\varepsilon_n)_{n \geq 2}$ is a
sequence of i.i.d.\ unit Poisson processes.
Consider a sequence of  functions $f_n:\mathbb{N}\to \mathbb{R}^+$
and set
$$
F_n(x,y)=y(f_n(x)),
$$
where $y:\mathbb{R}^+\to \mathbb{N}$ denotes a function.
In that case, the condition \eqref{contract} is satisfied if $|f_n(x)-f_n(x')|\leq \rho |x-x'|$ for any $n\geq 2$, any $x,x' \in {\mathbb N}$, and some $\rho <1$.

\medskip

For these models,
$$
H_k(X_{k-1},\varepsilon_k)= \E\big[| \varepsilon(f_k(X_{k-1}))-\varepsilon_k(f_k(X_{k-1}))|\big|\varepsilon_k,X_{k-1}\big]   ,
$$
where $ \varepsilon$ is a unit Poisson process independent of $(X_{k-1}, \varepsilon_k)$. By contraction, we get that
$$
 \| H_k(X_{k-1}, \varepsilon_k) \|_p^p \leq 2^{p-1} \| \varepsilon_k(f_k(X_{k-1}))\|_p^p= 2^{p-1}  {\mathbb E} \left [Q_p(f_k(X_{k-1})) \right ]   ,
$$
where $Q_p(t)=\| \varepsilon(t)\|_p^p$. Note that, when $p$ is an integer, $Q_p$  denotes the Stirling polynomial defined through Stirling numbers
(see the Lemma A-1 in \cite{DFT12} from \cite{FLO06}).
\item {\bf GLM--GARCH Poisson models}.
One can give numerous extensions of the previous model. Keeping the same notations, one can consider
$f_n:  \mathbb{R}^+ \times \mathbb{N}\to \mathbb{R}^+$,
and
$$
F_n(x,y)=(f_n(x), y(f_n(x)),
$$
where $x=(\lambda, z) \in  \mathbb{R}^+ \times \mathbb{N}$.
Let
$|x|=|\lambda|+a|z|$. Then
$$
{\mathbb E} [ | F_n(x, \varepsilon)- F_n(x', \varepsilon_n)|] \leq (1+a) | |f_n(x)-f_n(x')| \, ,
$$
and
\eqref{contract} is true provided that
$|f_n(x)-f_n(x')|\leq L_n |x-x'|$ and $\sup_{n \geq 2} L_n (1+a) = \rho $ for some $\rho <1$.

\medskip

For these models,
$$
H_k(X_{k-1},\varepsilon_k)= a \E\big[| \varepsilon(f_k(X_{k-1}))-\varepsilon_k(f_k(X_{k-1}))|\big|\varepsilon_k,X_{k-1}\big]   ,
$$
where $ \varepsilon$ is a unit Poisson process independent of $(X_{k-1}, \varepsilon_k)$. Hence, the moments of order $p$
of $H_k(X_{k-1},\varepsilon_k)$ can be controlled exactly as in the previous example.
\end{itemize}

\section{Separately Lipschitz functions of $X_1, \ldots , X_n$}
\setcounter{equation}{0}
Let $f: {\mathcal X}^n \mapsto {\mathbb R}$ be a separately Lipschitz function, such that
\begin{equation} \label{codiMD}
|f(x_1, x_2, \ldots, x_n)-f(x'_1, x'_2, \ldots, x'_n)| \, \leq \, d(x_1,x'_1)+\cdots +  d(x_n, x'_n) \, .
\end{equation}
Let
\begin{equation}\label{Sn}
S_n \, := \, f(X_1, \ldots , X_n) -{\mathbb E}[f(X_1, \ldots , X_n)]\, .
\end{equation}
We   introduce the natural filtration of the chain, that is  ${\mathcal F}_0=\{\emptyset, \Omega \}$
and for all $k \in {\mathbb{N}}^{*}$,
${\mathcal F}_k= \sigma(X_1, X_2,  \ldots, X_k)$.
Define
\begin{equation}\label{gk}
g_k(X_1, \ldots , X_k) \, = \, {\mathbb E}[f(X_1, \ldots, X_n)|{\mathcal F}_k]
\end{equation}
and
\begin{equation}\label{dk}
M_k\,= \, g_k(X_1, \ldots, X_k)-g_{k-1}(X_1, \ldots, X_{k-1})  .
\end{equation}
For all $k \in [1, n-1]$, let
$$
S_k:=M_1+M_2+\cdots + M_k  ,
$$
and notice that, by the definition of $M_k$'s, the functional $S_n$ introduced in
\eref{Sn} satisfies
$$
S_n \, = \, M_1+M_2+\cdots + M_n   .
$$
Thus $S_k$ is a martingale adapted to the natural filtration ${\mathcal F}_k$.
This representation appears in
Yurinskii \cite{Yu} and in p.\ 33 of the monograph by Milman and Schechtman \cite{MS}.
In the setting of separately Lipschitz functions of independent random variables ({\it i.e.}\ when $X_i=\varepsilon_i$)
it has been used by  McDiarmid \cite{M}  to get an exponential bound
on tail probabilities ${\mathbb P}(S_n \geq x), x\geq 0$.

The following Proposition, similar to Proposition 2.1 in \cite{DF15},  collects some interesting properties of
the function  $g_k$ and of the martingale difference $M_k$.

\begin{prop}\label{McD}
For all $k \in {\mathbb N}$
and any $\rho$ in $[0, 1)$, denote $K_k(\rho)=(1-\rho^{k+1})/(1-\rho)= 1 + \rho + \cdots + \rho^{k}$.
Let $(X_i)_{i \geq 1}$ be a Markov chain satisfying \eref{Mchain} for some
functions $F_n$ satisfying \eref{contract}. Let $g_k$ and $M_k$ be defined
by
\eref{gk} and \eref{dk} respectively.
\begin{enumerate}
\item
The function $g_k$ is separately Lipschitz, and satisfies
$$
\big|g_k(x_1, x_2, \ldots, x_k)-g_k(x'_1, x'_2, \ldots, x'_k) \big| \leq d(x_1,x'_1)+\cdots + d(x_{k-1}, x'_{k-1})+ K_{n-k}(\rho) d(x_k, x'_k) \, .
$$
\item Denote by $P_{X_1}$  and $P_{\varepsilon_k}$   the distribution of $X_1$ and the
distribution of  $\varepsilon_k$  respectively. Let $G_{X_1}$ and $H_{k}$ be  two functions defined as follows
$$
G_{X_1}(x)=\int d(x, x') P_{X_1}(dx') \quad \text{and}
\quad
H_{k}(x,y)= \int d(F_k(x,y),F_k(x,y'))P_{\varepsilon_k}(dy') \, .
$$
Then, the martingale difference  $M_k$  satisfies
$$
   |M_1| \leq K_{n-1}(\rho) G_{X_1}(X_1) \quad
   \text{and } \quad
   |M_k|\leq K_{n-k}(\rho)  H_{k}(X_{k-1}, \varepsilon_k), \ \  \, k \in [2, n].
$$
\end{enumerate}
\end{prop}
\begin{rem}\label{remc2}
Assume moreover that $F_n$ satisfies
\begin{equation}\label{c2}
d(F_n(x,y), F_n(x,y')) \leq C(x) \,\delta(y,y')
\end{equation}
for some function $C(x)  \geq 0$ not depending on $n$, and
let $G_{k}$ be the  function defined by
$$
G_{k}(y)= \int\delta(y,y')P_{\varepsilon_k}(dy') \, \
   \text{ for all $k \in [2, n]$}.
$$
Then $H_{k}(x,y) \leq C(x)G_{k}(y)$
and, consequently,
$$
 |M_k|\leq K_{n-k}(\rho)C(X_{k-1})  G_{k}(\varepsilon_k) \, \
   \text{ for all $k \in [2, n]$}.
$$
Note that \eqref{c2} is a non-uniform version of \eqref{c2old}, which is satisfied for many examples (for instance the three first
examples of Section 2). However, it seems quite difficult to check for INAR or GLM type models, while the moments of the dominating variables
$H_k(X_{k-1}, \varepsilon_k)$ are easy to control for such models (see Section \ref{SEC2}).
\end{rem}

\noindent {\emph {Proof}.} The first point will be proved by recurrence in the backward sense.
For $k=n,$ the result is obvious due to  $g_n=f$. Suppose it is true at step $k$, and let us prove it
at step $k-1$. By definition
$$
g_{k-1}(X_1, \ldots, X_{k-1})={\mathbb E}[g_k(X_1, \ldots, X_k)|{\mathcal F}_{k-1}]= \int g_k(X_k, \ldots, X_{k-1}, F_k(X_{k-1},y)) P_{\varepsilon_k}(dy)\, .
$$
Then it is easy to see that
\begin{multline}\label{triv1}
|g_{k-1}(x_1, x_2, \ldots, x_{k-1})-g_{k-1}(x'_1, x'_2, \ldots, x'_{k-1})|  \\ \leq \, \int \Big|g_k(x_1, x_2, \ldots, F_k(x_{k-1},y))-g_k(x'_1, x'_2, \ldots, F_k(x'_{k-1},y)) \Big|
P_{\varepsilon_k}(dy)\, .
\end{multline}
Now, by assumption and condition \eref{contract},
\begin{multline}\label{triv2}
\int \Big|g_k(x_1, x_2, \ldots, F_k(x_{k-1},y))-g_k(x'_1, x'_2, \ldots, F_k(x'_{k-1},y)) \Big|
P_{\varepsilon_k}(dy)\\
\leq d(x_1,x'_1)+\cdots + d(x_{k-1}, x'_{k-1})+ K_{n-k}(\rho) \int d(F_k(x_{k-1},y), F_k(x'_{k-1},y))P_{\varepsilon_k}(dy)
\\
\leq d(x_1,x'_1)+\cdots  + (1+\rho K_{n-k}(\rho)) d(x_{k-1}, x'_{k-1}) \\
\leq d(x_1,x'_1)+\cdots  +  K_{n-k+1}(\rho) d(x_{k-1}, x'_{k-1}) \, .
\end{multline}
The point 1 follows from \eref{triv1} and \eref{triv2}.

Next, we  prove the point 2. First notice that
$$
|M_1|=\bigg|g_1(X_1)-\int g_1(x)P_{X_1}(dx)\bigg|\leq
 K_{n-1}(\rho)\int d(X_1,x)P_{X_1}(dx)=K_{n-1}(\rho) G_{X_1}(X_1) \, .
$$
Similarly, for all $k \geq 2$,
\begin{align*}
 |M_k| \,& =\, \Big|g_k(X_1, \cdots, X_k)-{\mathbb E}[g_k(X_1, \cdots, X_k)|{\mathcal F}_{k-1}]\Big|\\
 &\leq \, \int \Big |g_k(X_1, \cdots, F_k(X_{k-1}, \varepsilon_k))-g_k(X_1, \cdots, F_k(X_{k-1}, y))\Big| P_{\varepsilon_k}(dy)\\
 &\leq \, K_{n-k}(\rho)\int  d(F_k(X_{k-1},\varepsilon_k),
 F_k(X_{k-1}, y))P_{\varepsilon_k}(dy)
 \, = \, K_{n-k}(\rho)
  H_{k}(X_{k-1},\varepsilon_k) \, .
\end{align*}
This completes the proof of Proposition \ref{McD}.
\hfill\qed

\section{Deviation inequalities for the functional $S_n$} \label{deviationiq}

\setcounter{equation}{0}
Let $(X_i)_{i \geq 1}$ be a Markov chain satisfying \eref{Mchain} for some
functions $F_n$ satisfying \eref{contract}.
In this section, we apply inequalities for martingales to bound up
the deviation of the functional $S_n$ defined by \eref{Sn}. Some of these inequalities
are direct applications of known inequalities, and some deserve a short proof.

Denote by $S_{2,n}= S_{n}-M_1$, and let $a_n$ be a sequence of positive numbers. Then, for any $x>0$,
\begin{align}
  {\mathbb P}\Big(  S_n \geq  a_n x\Big)
   &\leq {\mathbb P}\Big(  M_1 \geq  a_n x/2\Big)+ {\mathbb P}\Big(  S_{2,n} \geq  a_n x/2\Big) \nonumber \\
    &\leq {\mathbb P}\bigg(  G_{X_1}(X_1) \geq  \frac{a_n x }{  2 K_{n-1} (\rho)} \bigg) + {\mathbb P}\Big(  S_{2,n} \geq  a_n x/2\Big)   =: I_1(a_n, x)+ I_2(a_n, x) \, , \label{ineq001}
\end{align}
and note that the same bound is valid for ${\mathbb P}(  -S_n \geq  a_n x)$ by replacing the term
$I_2(a_n, x)$ by $\tilde I_2(a_n, x):= {\mathbb P}(  -S_{2,n} \geq  a_n x/2)$.

The  term  $I_1(a_n, x)$ will be most of the time  negligible, and represents  the direct influence of the initial distribution of the chain.
For instance, when the chain starts from a point $X_1=x_1$,  then $G_{X_1}(X_1)=0$ and $I_1(a_n, x)=0.$
The main difficulty is to give an upper bound for  $I_2(a_n, x)$, which is the purpose of the present paper.

\subsection{A first exponential bound}
Under a sub-Gaussian  type condition, we obtain the following proposition.
\begin{prop} \label{BerProp}
Assume that there exists a positive constant $\epsilon$   such that,
for any integer $k\geq 2$,
\begin{equation}\label{Bercond02}
\mathbb{E}\left[ \big(H_{k}(X_{k-1}, \varepsilon_k) \big)^l  \right] \leq \frac{1}{2} \frac{  l! \,\epsilon ^{l-2}  }{(l-1)^{l/2}}  \mathbb{E}\left[  \big( H_{k}(X_{k-1}, \varepsilon_k) \big)^2 \right]
\textrm{ for all}\ l\geq  2.
\end{equation}
 Then,  for any   $ x>0$,
\begin{align}
  \mathbb{P}\Big( \pm S_n \geq x V_n  \Big)
   &\leq I_1(V_n, x)+ \exp\bigg\{ - \frac{(x/2)^2}{  1+ \sqrt{ 1+ x \epsilon  K_{n-2} (\rho)
  /\sigma_n   }  + x   \epsilon K_{n-2} (\rho)/2\sigma_n   } \bigg\} \label{jnsk01}\\
 &\leq  I_1(V_n, x)+ \exp\bigg\{ - \frac{(x/2)^2}{  2 \big( 1+ x   \epsilon K_{n-2} (\rho)  / 2\sigma_n   \big)} \bigg\},\label{jnsk02}
\end{align}
where $$V_n^2 =  \sum_{k=2}^{n} K_{n-k}^2(\rho) \mathbb{E}\big[ \big( H_{k}(X_{k-1}, \varepsilon_k) \big)^2 \big] \ \   and \ \   \sigma_n^2=  \frac1n V_n^2.$$
\end{prop}

\begin{rem} Let us give some comments on Proposition \ref{BerProp}.
\begin{enumerate}
\item Condition \eqref{Bercond02} is in fact a sub-Gaussian condition. On can check that it is satisfied provided
$$   \inf_{k \geq 2} {\mathbb E}\big[ \big( H_{k}(X_{k-1}, \varepsilon_k) \big)^2 \big]    >0  $$
and
$$ \sup_{k \geq 2}  {\mathbb E}\Big[ \exp  \Big\{ c \, \big( H_{k}(X_{k-1}, \varepsilon_k)\big)^2 \Big\} \Big]  < \infty $$ for some positive constant $c$ not depending on $k$.

\item Assume that $${\mathbb E}\Big[\exp  \left\{ c \, \sqrt{G_{X_1}(X_1)} \right\}\Big] < \infty$$ for some positive constant $c$, and that
$$ 0< \liminf_{n\rightarrow \infty}\sigma_n    \leq \limsup_{n\rightarrow \infty}\sigma_n < \infty.$$   Then, it follows from Proposition \ref{BerProp} that
\begin{eqnarray}
\mathbb{P}\left( \pm S_n \geq  n  \right)   = O \left( \exp\left\{ - C \sqrt n  \right\} \right)
\end{eqnarray}
for some positive constant $C$.
\end{enumerate}
\end{rem}

\noindent\emph{Proof.}
 By Taylor's expansion of $e^x$ and the fact that $\mathbb{E} [S_{2,n}]=0$, we have, for all $t\geq 0,$
 \begin{eqnarray}\label{sxsa}
 \mathbb{E}\bigg[\exp\bigg\{t \frac{ S_{2,n}}{\sqrt{n}} \bigg \}\bigg] = 1+ \sum_{k=2}^{\infty} \frac{t^k}{k!}  \mathbb{E}\Big[\Big(\frac{ S_{2,n}}{\sqrt{n}}\Big)^k \Big].
\end{eqnarray}
Using   Rio's inequality (see Theorem 2.1 of \cite{R09}): for any $p\geq 2,$
\begin{eqnarray}\label{R}
\Big(\mathbb{E}[|S_{2,n}|^p] \Big)^{2/p} \leq  (p-1)  \sum_{i=2}^n  \big(\mathbb{E}[|M_i|^p] \big)^{2/p}  ,
\end{eqnarray}
we get, for all $k\geq 2,$
\begin{eqnarray}\label{ssxsfsd}
\mathbb{E}[|S_{2,n}|^k] \leq (k-1)^{k/2} \Big(\sum_{i=2}^n \big(\mathbb{E}[|M_i|^k] \big)^{2/k}\Big)^{k/2}.
\end{eqnarray}
Hence, by H\"{o}lder's  inequality, inequality (\ref{ssxsfsd}) implies that, for all $k\geq 2,$
\begin{eqnarray}\label{sddd}
\mathbb{E}[|S_{2,n}|^k] \leq (k-1)^{k/2} n^{k/2-1} \sum_{i=2}^n  \mathbb{E}[|M_i|^k]  .
\end{eqnarray}
Applying the last inequality to (\ref{sxsa}), we obtain
 \begin{eqnarray}\label{bnlts}
\mathbb{E}\bigg[\exp\bigg\{t \frac{ S_{2,n}}{\sqrt{n}} \bigg \}\bigg] \leq 1+ \sum_{k=2}^{\infty} \Big( \frac{t^k}{k!}  (k-1)^{k/2} n^{ -1 } \sum_{i=2}^n  \mathbb{E}[|M_i|^k] \Big).
\end{eqnarray}
 By points 2 of Proposition \ref{McD} and (\ref{Bercond02}), we deduce that,
for any integer $i\geq 2$,
\begin{eqnarray*}
\mathbb{E}[|M_i|^l] &\leq&  \mathbb{E}[|K_{n-i}(\rho) H_{i}(X_{i-1}, \varepsilon_i)|^l ] \\
&\leq& \frac{1}{2} \frac{  l! \,(K_{n-2}(\rho) \epsilon )^{l-2}  }{(l-1)^{l/2}}   \mathbb{E}[ (K_{n-i}(\rho)H_{i}(X_{i-1}, \varepsilon_i))^2]  \ \ \ \ \  \ \ \textrm{for all}\ l\geq  2.
\end{eqnarray*}
Hence  condition
(\ref{Bercond02}) implies that, for all $0\leq t < (K_{n-2}(\rho) \epsilon)^{-1}$,
 \begin{eqnarray}\label{ineq23}
\mathbb{E}\bigg[\exp\bigg\{t \frac{ S_{2,n}}{\sqrt{n}} \bigg \}\bigg] \leq 1+ \sum_{k=2}^{\infty}  \frac{ \ \sigma_n^2}{2 } \, t^k (K_{n-2}(\rho) \epsilon )^{k-2} = 1+   \frac{t^2 \sigma_n^2  }{2\,(1- t K_{n-2}(\rho) \epsilon )} .
\end{eqnarray}
By the inequality $1+x \leq e^x  ,$ it follows that, for all $0\leq t < (K_{n-2}(\rho) \epsilon)^{-1}$,
 \begin{eqnarray*}
\mathbb{E}\bigg[\exp\bigg\{t \frac{ S_{2,n}}{\sqrt{n}} \bigg \}\bigg] \ \leq \   \exp \Bigg\{ \frac{t^2  \sigma_n^2  }{2\,(1- t  K_{n-2}(\rho)\epsilon)}   \Bigg\}.
\end{eqnarray*}
Applying Markov's inequality,   it is then easy to see that, for all $0\leq t < \sigma_n(K_{n-2}(\rho) \epsilon)^{-1}$ and  $ x \geq 0,$
\begin{eqnarray*}
  \mathbb{P}\left(   S_{2,n} \geq x  V_n /2   \right)
   \leq   \exp\Big\{ - t x /2\Big \} \mathbb{E}\left[   \exp\bigg\{t \frac{ S_{2,n}}{V_n } \bigg \} \right].
\end{eqnarray*}
Hence
\begin{eqnarray*}
  \mathbb{P}\left(   S_{2,n} \geq x  V_n /2   \right)
    &\leq& \inf_{0\leq t <\sigma_n (K_{n-2}(\rho) \epsilon)^{-1}}  \exp\bigg\{ - t x /2 + \frac{  t^2    }{2\,(1- t \, K_{n-2}(\rho)\epsilon/ \sigma_n)}    \bigg \} \\
    &=& \exp\bigg\{ - \frac{(x/2)^2}{  1+ \sqrt{ 1+ x K_{n-2}(\rho)\epsilon
  /\sigma_n   }  + x   K_{n-2}(\rho)\epsilon /2\sigma_n   } \bigg\},
\end{eqnarray*}
which gives   (\ref{jnsk01}).   Using the   inequality
$   \sqrt{ 1+ x K_{n-2}(\rho)\epsilon / \sigma_n    }  \leq  1+  x K_{n-2}(\rho)\epsilon /2 \sigma_n ,$
we get  (\ref{jnsk02})  from (\ref{jnsk01}).  \qed

\subsection{Semi-exponential  bounds}\label{Bersec}
In the case where the variables $H_{k}(X_{k-1}, \varepsilon_k)$ have semi-exponential moments, the following proposition holds.

\begin{prop}\label{propExp}
Let $\alpha \in (0,1)$.
Assume that there exists a constant $C_1$ such that, for any integer $k\geq 2$,
\begin{equation} \label{Bernsteinmoment}
  \mathbb{E}\,\Big[\exp\Big\{ \Big(H_{k}(X_{k-1}, \varepsilon_k)\Big)^{\frac{2\alpha}{1-\alpha}} \Big \}  \Big] \leq C_1  .
\end{equation}
Then, for any $x> 0$,
\begin{eqnarray}\label{mainineq01}
  {\mathbb P}\left(\pm  S_n \geq  n x\right)
   \leq I_1(n, x) +  C(\alpha, x)  \exp\left\{-\left(\frac{ x  }{ 8 K_{n-2}(\rho)}\right)^{2\alpha} n^\alpha\ \right\} \, ,
\end{eqnarray}
where
\[
C(\alpha,  x)=  2+ 35  C_1     \left( \frac{K_{n-2}^{2\alpha}(\rho) }
{ x^{2\alpha} 4^{2-3\alpha}}  + \frac{4 K_{n-2}^2(\rho)}{  x^2 }
\left( \frac{3(1-\alpha)}{2\alpha}\right)^{\frac{ 1-\alpha}{\alpha}} \right)
\]
depends on $n$ only through the term $K_{n-2}(\rho)$.
\end{prop}

\begin{rem}\label{rem01}
Let us comment on inequality  \eref{mainineq01}.
Assume  moreover that
\begin{equation}\label{Bernsteinmoment1}
 \mathbb{E}\,\left[\exp\left\{ c\Big( G_{X_1}(X_1)\Big)^{\alpha  }  \right \} \right]  \leq   C_2 ,
\end{equation}
for two positive constants $c, C_2$.
Then, it follows from \eqref{mainineq01} that
\begin{eqnarray}\label{LU00}
\mathbb{P}\left( \pm S_n \geq  n  \right)   = O \left( \exp\left\{ - C  n^{\alpha}     \right\} \right),
\end{eqnarray}
for some positive constant $C$.
This rate is in accordance with the best possible rate for large deviation of partial sums of martingales differences,
as proved in  Theorem 2.1 of  \cite{Fx1}.
For partial sums of independent random variables, the rate  \eqref{LU00}  holds under weaker conditions on  exponential moments, see Lanzinger and Stadtm\"{u}ller \cite{LS00}.
\end{rem}

\noindent\emph{Proof.}   From point 2 of Proposition \ref{McD} and condition (\ref{Bernsteinmoment}), it is  easy to see that,
   for any  $k \in [2, n],$
\begin{eqnarray}\label{fin36}
\mathbb{E}\,\left[ \exp\left\{  |K_{n-2}^{-1}(\rho)M_k|^{\frac{2\alpha}{1-\alpha}} \right\} \right]  \leq   C_1 .
\end{eqnarray}
Applying Theorem 2.1 of  Fan et al. \cite{Fx1} to the martingale sequence
 $(K_{n-2}^{-1} (\rho)M_k, \mathcal{F}_k)_{k=2,..,n}$, we get, for any $x> 0$,
\begin{eqnarray}
 I_2(n, x)
   \leq C(\alpha, x)  \exp\left\{-\left(\frac{ x  }{ 8 K_{n-2}(\rho)}\right)^{2\alpha} n^\alpha\ \right\} . \label{ineq003}
\end{eqnarray}
Combining the inequalities (\ref{ineq001})  and (\ref{ineq003}),  we obtain  the desired inequality.
   \hfill\qed

 \medskip

   For the next proposition, let us introduce the random variables
 \begin{equation}\label{M2cond}
 L_k(X_{k-1}),  \quad \text{where} \quad L_k(x)= \int (H_k(x, y))^2 P_{\varepsilon_k}(dy) \, ,
 \end{equation}
 and note that
 $$
  L_k(X_{k-1})   = \mathbb{E}\,\left[ \left( H_{k}(X_{k-1}, \varepsilon_k) \right)^2     \big | X_{k-1} \right].
 $$
 According to Proposition \ref{McD}, for any $k \geq 2$, ${\mathbb E}[M_k^2|{\mathcal F}_{k-1}] \leq K_{n-k}(\rho) L_k(X_{k-1})$.

\begin{prop} \label{pr43} Assume  (\ref{c2}), and
let $\alpha \in (0,1)$.
Assume that there exist two constants  $C_1$ and  $C_2$ such that, for any integer $k\geq 2, n \geq 2$,
\begin{equation}\label{cond3.5}
\mathbb{E}\left[\exp\bigg\{ \Big(\frac{1}{n} \sum_{k=2}^n   L_k(X_{k-1})  \Big)^{\frac{\alpha}{1-\alpha} } \bigg \} \right ] \leq C_1
\end{equation}
and
\begin{equation}\label{cond3.6}
  \mathbb{E}\,\left[\exp\left\{ \Big(  H_{k}(X_{k-1}, \varepsilon_k) \Big)^{\frac{\alpha}{1-\alpha}} \right \}  \right] \leq C_2.
\end{equation}
Then, for all  $x> 0$,
\begin{multline}\label{mainineq02}
 \mathbb{P}\left( \pm S_{n}\geq n x  \right)  \leq  I_1(n, x) +
 \exp\left\{-\frac{( x K_{n-2}^{-1}(\rho)  /2)^{1+ \alpha} }{2\big( 1 + x K_{n-2}^{-1}(\rho) /6 \big)} n^\alpha  \right\} \\ +
 (C_1 + nC_2)  \exp\left\{ -  \left(   x K_{n-2}^{-1} (\rho)/2 \right)^\alpha n^\alpha  \right \}   .
\end{multline}
\end{prop}
\begin{rem}
According to Remark \ref{rem01},  under the conditions  \eref{cond3.5},  \eref{cond3.6} and \eref{Bernsteinmoment1},  we have
\begin{eqnarray}
\mathbb{P}\left( \pm S_n \geq  n  \right)   = O \left( \exp\left\{ - C  n^{\alpha}     \right\} \right),
\end{eqnarray}
for some positive constant $C$. This rate is in accordance with the best possible rate for large deviation of partial sums of martingales differences,
as proved in  Corollary 2.3  of  \cite{Fx1}.
Note that if $\alpha \in [1/2,1)$, the condition \eqref{cond3.5} is true provided that
\begin{equation}\label{bisbis}
 \sup_{k \geq 2} \mathbb{E}\left[\exp\bigg\{  ( L_k(X_{k-1}) )^{\frac{\alpha}{1-\alpha} } \bigg \} \right ] \leq C_1 \, .
\end{equation}
For $\alpha \in [1/2, 1)$, the two conditions \eqref{bisbis} and \eqref{cond3.6} are clearly less restrictive than \eqref{Bernsteinmoment}, so   Proposition \ref{pr43}
is more precise than Proposition \ref{propExp} in the regime of large deviation. However, it does not allow to control moderate deviations
$\mathbb{P}\left( \pm S_n \geq  n^\delta  \right)$ for $\delta$ close to $1/2$, which is possible via Proposition \ref{propExp} (see
for instance \eqref{etlabete}).
\end{rem}

\medskip

\noindent\emph{Proof.} From point 2 of Proposition \ref{McD} and condition (\ref{cond3.6}), it is  easy to see that, for any  $k \in [2, n],$
\begin{eqnarray*}
\mathbb{E}\,\left[ \exp\left\{  |K_{n-2}^{-1}(\rho)M_k|^{\frac{\alpha}{1-\alpha}} \right\} \right]
 \leq  C_2.
\end{eqnarray*}
For any  $k \in [2, n],$
\begin{eqnarray}
\mathbb{E}\,\left[ |K_{n-2}^{-1}(\rho) M_k|^2 \Big| \mathcal{F}_{k-1} \right]    &\leq&   \mathbb{E}\,\left[ \left(K_{n-2}^{-1}(\rho) K_{n-k}(\rho)H_{k}(X_{k-1}, \varepsilon_k) \right)^2
 \Big| \mathcal{F}_{k-1} \right]     \nonumber\\
 &\leq&   \mathbb{E}\,\Big[ \Big( H_{k}(X_{k-1}, \varepsilon_k) \Big)^2     \Big| \mathcal{F}_{k-1} \Big]  .
\end{eqnarray}
Thus
$$\sum_{k=2}^n \mathbb{E}\,\Big[ |K_{n-2}^{-1}(\rho) M_k|^2 \Big| \mathcal{F}_{k-1} \Big] \leq    \sum_{k=2}^n \mathbb{E}\,\Big[ \Big( H_{k}(X_{k-1}, \varepsilon_k) \Big)^2     \Big| \mathcal{F}_{k-1} \Big] =  \sum_{k=2}^n L_k(X_{k-1}) .$$
Using Theorem 2.2 of Fan et al. \cite{Fx1}, we have
\begin{multline*}
  \mathbb{P}\bigg( K_{n-2}^{-1}(\rho) S_{2,n}\geq n K_{n-2}^{-1}(\rho) x/2\ \ \mbox{and}\ \ \sum_{k=2}^n L_k(X_{k-1}) \leq n
 v^2\    \bigg) \\
   \leq \exp\left\{-\frac{(  K_{n-2}^{-1}(\rho) x/2)^2 }{2\big(   n^{\alpha-1 }v^2+\frac{1}{3}(  K_{n-2}^{-1}(\rho) x/2)^{2-\alpha} \big)} n^\alpha  \right\}  + nC_2  \exp\Bigg\{ -  \Big( \frac{   x }{2 K_{n-2}(\rho)} \Big)^\alpha n^\alpha  \Bigg \}.
\end{multline*}
From the last inequality, we deduce that
\begin{eqnarray*}
I_2(n, x)\!\!  &\leq& \!\! \exp\left\{-\frac{(  K_{n-2}^{-1}(\rho) x/2)^2 }{2\big(   n^{\alpha-1 }v^2+\frac{1}{3}(  K_{n-2}^{-1}(\rho) x/2)^{2-\alpha} \big)} n^\alpha  \right\}  + nC_2  \exp\Bigg\{ -  \Big( \frac{   x }{2 K_{n-2}(\rho)} \Big)^\alpha n^\alpha  \Bigg \}  \\
 &&\, + \, \mathbb{P}\bigg(   \sum_{k=2}^n L_k(X_{k-1})  >
 nv^2\    \bigg).
\end{eqnarray*}
Using the exponential Markov  inequality and the condition \eqref{cond3.5},
we get, for all $ v>0$,
\begin{eqnarray}
\mathbb{P}\bigg(   \sum_{k=2}^n L_k(X_{k-1})  >
 n v^2\    \bigg)\leq C_1 \exp\Big\{ -  v^{\frac{2\alpha}{1-\alpha} } \Big \}. \nonumber
\end{eqnarray}
Taking $v^2 = (x n  K_{n-2}^{-1} (\rho)/2)^{(1-\alpha)/2}$, we have, for all $x>0$,
$$
I_2(n, x) \leq
\exp\left\{-\frac{( x K_{n-2}^{-1}(\rho)  /2)^{1+ \alpha} }{2\big( 1 + x K_{n-2}^{-1}(\rho) /6 \big)} n^\alpha  \right\}  +
 (C_1 + nC_2)  \exp\left\{ -  \left(   x K_{n-2}^{-1} (\rho)/2 \right)^\alpha n^\alpha  \right \}  \, .
$$

Combining the last inequality and   (\ref{ineq001}), we obtain the desired  inequality. \hfill\qed

\subsection{Fuk-Nagaev type  bound}
We now consider the case where the random variables
$H_{k}(X_{k-1}, \varepsilon_k), k\geq 2,$ have only a weak moment of order $p > 2$.
For any real-valued random variable $Z$ and any $p\geq 1$, define the weak
moment of order $p$  by
\begin{equation}\label{weakp}
\|Z\|_{w,p}^p=\sup_{x>0} x^p{\mathbb P}(|Z|>x)\, .
\end{equation}
The following proposition is a  Fuk-Nagaev type inequality (cf.\  Fuk \cite{F73} and Nagaev \cite{N79}; see also Fan \textit{et al.}\ \cite{FGL17} and Rio \cite{R17} for martingales).
\begin{prop}\label{pro3}
Let  $p\geq 2$ and $\delta>0$, and consider the variables $L_k(X_{k-1})$  defined in \eqref{M2cond}.
Assume that there exist two constants  $C_1$ and  $C_2$ such that, for any integer $k\geq 2$,
\begin{equation}\label{cond3.7}
\left \|  \frac{1}{n} \sum_{k=2}^n L_k(X_{k-1})  \right \|_{w,p+ \delta}^{p+ \delta} \leq C_1
\end{equation}
and
\begin{equation}\label{cond3.8}
\left \| H_{k}(X_{k-1}, \varepsilon_k) \right \|_{w,p+ \delta}^{p+ \delta} \leq C_2.
\end{equation}
Then, for all  $x> 0$,
\begin{equation}
 \mathbb{P}\left( \pm S_{n}\geq n x  \right)    \leq I_1(n, x) +  \exp\left\{-\frac{(   K_{n-2}^{-1}(\rho)  /2)^2 }{2\left(n^{-1/(p+\delta)}  x^{-1}+\frac{1}{6}   K_{n-2}^{-1}(\rho)    \right)} (nx)^{\delta/(p+\delta) }  \right\}
    + \  \frac{C_1+ C_2}{n^{p-1} x^{p }}  \, .   \label{sfdw}
\end{equation}
\end{prop}

\begin{rem}\label{commentFNI}
 Let us comment on Proposition \ref{pro3}.
\begin{enumerate}
\item If  there exists a constant $C_3$ such that
\begin{equation}\label{seinsntq}
\left|\left|G_{X_1}(X_1) \right|\right|_{w,p-1}^{p-1} \leq   C_3 ,
\end{equation}
then, for any $x> 0$,
\begin{eqnarray}
 I_1(n, x) ={\mathbb P}\bigg(  G_{X_1}(X_1) \geq  \frac{n x }{  2 K_{n-1} (\rho)} \bigg)\leq (2 K_{n-1} (\rho))^{p-1}  \frac{C_3}{(nx)^{p-1}}  .
\end{eqnarray}
 Thus under  conditions \eref{cond3.7},  \eref{cond3.8} and  \eref{seinsntq},   we have
\begin{equation*}
\mathbb{P}\left( \pm S_n \geq  n  \right)   = O \left( \frac{1}{n^{p-1}}  \right)   .
\end{equation*}
 \item Assume  moreover that $F_n$ satisfies \eref{c2}. Then, according to Remark \ref{remc2},
 Proposition \ref{pro3} remains valid when   $H_{k}(X_{k-1}, \varepsilon_k)$ is replaced by $C(X_{k-1})  G_k(\varepsilon_k) .$
 Since  $C(X_{k-1})$ and $G_k(\varepsilon_k)$ are independent, we easily see that
 $$ L_k(X_{k-1}) \leq (C(X_{k-1}) )^2\mathbb{E} \left [ (G_k(\varepsilon_k))^2\right ] $$
 and
 \begin{equation}
  \left \| C(X_{k-1})  G_k(\varepsilon_k) \right \|^{p+\delta}_{w, p + \delta}    \leq {\mathbb E} \left [ \big(C(X_{k-1}) \big)^{p+\delta} \right]
  \left \| G_k(\varepsilon_k)\right \|^{p+\delta}_{w, p + \delta} \,  .
\end{equation}
Thus if
 \begin{equation*}\label{trivial1}
 {\mathbb E} \left [ \big( C (X_{k-1}) \big) ^{p+\delta}    \right]  \leq C_3  \ \ \ \textrm{and} \ \ \  \left \| G_k(\varepsilon_k)\right \|^{p+\delta}_{w, p + \delta} \leq C_4 \, ,
\end{equation*}
then  condition (\ref{cond3.8}) is satisfied with $C_2=C_3C_4.$ Of course, the same computations may be done by interchanging $C(X_{k-1})$
and $G_k(\varepsilon_k)$. Hence, if
\begin{equation*}\label{trivial2}
 {\mathbb E} \left [ \big( G_k(\varepsilon_k) \big)^{p+\delta}    \right]  \leq C_3  \ \ \ \textrm{and} \ \ \  \left \| C(X_{k-1})\right \|^{p+\delta}_{w, p + \delta} \leq C_4 \, ,
\end{equation*}
then  condition (\ref{cond3.8}) still holds with $C_2=C_3C_4.$
\end{enumerate}
\end{rem}

\medskip

\noindent\emph{Proof.}
To prove Proposition \ref{pro3}, we need the following inequality whose proof can be found in Fan  \textit{et al.}\  \cite{FGL12} (cf. Corollary 2.3 and Remark 2.1 therein).
\begin{lem}
\label{leedm1} Assume that $(\xi_i, {\mathcal G}_i)_{i\geq 1}$ are square integrable martingale differences, and let
$Z_n= \xi_1 + \cdots + \xi_n$ and $ \langle Z \rangle_n = \sum_{k=1}^n {\mathbb E}[\xi_k^2 |{\mathcal G}_{k-1}]$.   Then,
for all $ x, y, v > 0$,
\begin{equation*}
{\mathbb P}\Big( Z_n \geq x  \  \textrm{and} \ \langle Z\rangle_n \leq v^2   \Big)
  \leq    \exp\left\{- \frac{x^2}{2(v^2+ \frac{1}{3}xy)} \right\}+ \mathbb{P}\left( \max_{1\leq i \leq n} \xi_{i}>y  \right).
\end{equation*}
\end{lem}
\noindent By Lemma \ref{leedm1}  and Markov's inequality,  it follows that, for all $ x, y, v > 0$,
\begin{multline*}
  \mathbb{P}\left( K_{n-2}^{-1}(\rho) S_{2,n}\geq n K_{n-2}^{-1}(\rho) x/2\ \ \mbox{and}\ \ \sum_{k=2}^n L_k(X_{k-1}) \leq n v^2\    \right) \\
   \leq \exp\left\{-\frac{( n K_{n-2}^{-1}(\rho) x/2)^2 }{2\big(  n v^2+\frac{1}{6}  n K_{n-2}^{-1}(\rho) x y   \big)}   \right\}  +\mathbb{P}\left( \max_{2\leq i \leq n} K_{n-2}^{-1}(\rho) M_i \geq y  \right).
\end{multline*}
It is easy to see that,  for all $   y  > 0$,
\begin{align*}
\mathbb{P}\left( \max_{2\leq i \leq n} K_{n-2}^{-1}(\rho) M_i \geq y  \right)
 & \leq  \sum_{i=2}^n \mathbb{P}\left(  K_{n-2}^{-1}(\rho) M_i \geq y  \right)
  \leq  n  C_2 y^{-(p+\delta)} ,
\end{align*}
and that, for all $v>0$,
\begin{equation*}
  \mathbb{P}\left( \sum_{k=2}^n L_k(X_{k-1})    > n v^2   \right)
   \leq  C_1  v^{-2(p+\delta)}.
\end{equation*}
Thus,  for all $ x, y, v > 0$,
\begin{eqnarray*}
I_2(n, x)  \leq
   \exp\left\{-\frac{( n K_{n-2}^{-1}(\rho) x/2)^2 }{2\big(   n v^2+\frac{1}{6}  n K_{n-2}^{-1}(\rho) x y   \big)}   \right\}   + \frac{nC_2}{ y^{p+\delta}}  +  \frac{C_1}{ v^{2(p+\delta)}  } .
\end{eqnarray*}
Taking $y =   (nx)^{p/(p+\delta) }$ and $v^{2(p+\delta)} = n^{p-1} x^p $  in the last inequality, we obtain,
 for all $ x > 0$,
\begin{eqnarray*}
I_2(n, x)  \leq
   \exp\left\{-\frac{(   K_{n-2}^{-1}(\rho)  /2)^2 }{2\big( n^{-1/(p+\delta)}  x^{-1} +\frac{1}{6}   K_{n-2}^{-1}(\rho)    \big)} (nx)^{\delta/(p+\delta) }  \right\}   +   \frac{C_1+ C_2}{n^{p-1} x^{p }}   .
\end{eqnarray*}
Combining the last inequality and   (\ref{ineq001}), we obtain the desired  inequality. \hfill\qed

\subsection{von Bahr-Esseen's inequality, weak form}
We now consider the case where the variables $G_{X_1}(X_1)$ and
$H_k(X_{k-1}, \varepsilon_k)$ have only a weak moment of order $p \in (1,2)$.

\begin{prop}\label{weakVBEI}
Let $p \in (1, 2)$. Assume that there exists positive constants $A_k(p)$ such that, for any $k \in [2,n]$,
\begin{equation}\label{weakVB}
  \left \|H_k(X_{k-1}, \varepsilon_k)\right \|_{w,p}^p \leq A_k(p)
  \, .
\end{equation}
Then, for any $x>0,$
\begin{equation}\label{weakVBE}
 {\mathbb P}(|S_n| \geq x) \leq 2 I_1(1,x)+ \frac{2^pC_p B_p(n,\rho)}{x^p}\, ,
\end{equation}
where
 $$
 C_p= \frac{4p}{p-1} +\frac{8}{2-p}\,
$$
and
 $$
B_p(n,\rho)=   \sum_{k=2}^n \left(K_{n-k}(\rho)\right)^p  A_k(p) \,.
$$
\end{prop}

\begin{rem}
Let us comment on Proposition \ref{weakVBEI}.
\begin{enumerate}
\item Contrary to the previous inequalities of Section \ref{deviationiq}, this inequality is truly non-stationary, in the sense that
it is expressed in terms of the weak moments $\|H_k(X_{k-1}, \varepsilon_k) \|_{w,p}^p$, without assuming a uniform bound (in $k$) on these moments.
This will also be the case of the moment inequalities of Section \ref{SECMOM}.
\item Assume  moreover that $F_n$ satisfies \eref{c2}. Then, according to Remark \ref{remc2},
 Proposition \ref{pro3} remains true if  condition   \eref{weakVB} is replaced by
\begin{equation}\label{weakVfdB}
  \left \| C(X_{k-1})  G_k(\varepsilon_k) \right \|_{w,p}^p \leq A_k(p) \, .
\end{equation}
In particular, if either
$$
{\mathbb E} \left [  (C(X_{k-1}))^p       \right]  \leq A_{1,k}(p)  \ \ \ \textrm{and} \ \ \  \left \| G_k(\varepsilon_k)\right \|^{p}_{w, p} \leq A_{2,k}(p)
$$
or
$$
 {\mathbb E} \left [  (G_k(\varepsilon_k))^p   \right]  \leq A_{1,k}(p)  \ \ \ \textrm{and} \ \ \  \left \| C(X_{k-1})\right \|^{p}_{w, p} \leq A_{2,k}(p) \, ,
$$  hold,
then condition \eqref{weakVfdB} is satisfied  with $A_k(p)=A_{1,k}(p)A_{2,k}(p)$.

\item Assume that  $\|   G_{X_1}(X_1) \|_{w,p-1}< \infty$ and that
$B_p(n,\rho) =O(n)$, then
\begin{equation*}
\mathbb{P}\left( |S_n| \geq  n  \right)   = O \left( \frac{1}{n^{p-1}}  \right)  .
\end{equation*}

\end{enumerate}
\end{rem}

\noindent\emph{Proof.} By Proposition 3.3 of Cuny \emph{et al.}  \cite{CDM17}, we have, for  any $x>0,$
\begin{equation}\label{inew01}
 {\mathbb P}(|S_{2,n}|\geq x/2) \leq  \frac{2^p C_p}{x^p}\, \sum_{k=2}^n   \left\| M_k\right\|_{w,p}^p  .
\end{equation}
From point 2 of Proposition \ref{McD} and condition (\ref{weakVB}),  it follows that,
for any  $k \in [2, n],$
\begin{equation}\label{inew03}
 \left \| M_k\right\|_{w,p}^p  \leq   \left \|  K_{n-k}(\rho)     H_{k}(X_{k-1}, \varepsilon_k) \right \|_{w,p}^p  \leq   \left(K_{n-k}(\rho) \right)^p   A_k(p).
\end{equation}
Combining  \eref{inew01}  and  \eref{inew03}, we obtain the desired inequality.  \hfill\qed

\section{Moment inequalities}\label{SECMOM}

In this section, we shall control the ${\mathbb L}_p$-norm of the functional $S_n$, for $p>1$. The upper bounds will be expressed in terms of
the moments of order $p$ of the dominating random variables $H_{k} (X_{k-1}, \varepsilon_k)$. Let us emphasize that all the inequalities of these
section are completely non-stationary, in the sense that we shall  not assume a uniform bound (in $k$) on $\|H_k(X_{k-1}, \varepsilon_k) \|_{p}^p$.

\subsection{Marcinkiewicz-Zygmund type inequality}
We assume in this subsection  that the dominating random variables $G_{X_1}(X_1) $  and $H_{k} (X_{k-1}, \varepsilon_k)$ have a moment of order $p \geq 2$.
\begin{prop}\label{MZIP}
Let $p \geq 2$. Assume that there exist    positive constants $A_k(p)$   such that
\begin{equation}\label{shnbs}
 \mathbb{E}  \Big[\big(G_{X_1}(X_1)\big)^{p} \Big]  \leq A_1(p), \quad \text{and for $k \in [2,n]$} \quad \mathbb{E} \Big[ \big(H_{k} (X_{k-1}, \varepsilon_k)\big)^p  \Big]   \leq A_k(p)  .
\end{equation}
Then
\begin{equation}\label{MZI}
  \| S_n \|_p \leq   \sqrt{ A_p(n,\rho)}\, ,
\end{equation}
 where
 $$
A_p(n,\rho)= \big(K_{n-1}(\rho) \big)^2 \big(A_1(p) \big)^{2/p} +
(p-1) \sum_{k=2}^n \big(K_{n-k}(\rho) \big)^2  \big(A_k(p) \big)^{2/p}\, .
$$
\end{prop}
\begin{rem}
Assume  moreover that $F_n$ satisfies \eref{c2}. Then, according to Remark \ref{remc2},
 inequality \eref{MZI} remains true if the second condition of  \eref{shnbs} is replaced by
\begin{equation} \label{weaker}
  {\mathbb E} \left [(C(X_{k-1}))^p \right ] {\mathbb E} \left [ (G_k(\varepsilon_k))^p \right ]
  \leq A_k(p) \, .
\end{equation}
\end{rem}

\noindent\emph{Proof.} Applying Theorem 2.1 of Rio \cite{R09}, we get
 $$
\| S_n \|_p^2  \leq \|M_1\|_p^2 +(p-1) \sum_{k=2}^n  \| M_k \|_p^2 \, .
$$
By Proposition \ref{McD}  and condition (\ref{shnbs}), it follows that
\begin{eqnarray*}
\| S_n \|_p^2   &\leq&   \big(K_{n-1}(\rho)\big)^2  \left( {\mathbb E} \left[  \big(  G_{X_1}(X_1)\big)^p\right]  \right)^{\frac 2 p} + (p-1)
    \sum_{k=2}^n \big(K_{n-k}(\rho)\big)^2 \big({\mathbb E} \left[  \big( H_{k}(X_{k-1}, \varepsilon_k)   \big)^p\right]\big)^{\frac 2 p} \\
    &\leq&   \big(K_{n-1}(\rho)\big)^2  \big( {\mathbb E}  \left[  \big(  G_{X_1}(X_1)\big)^p\right]  \big)^{\frac 2 p} + (p-1)
    \sum_{k=2}^n \big(K_{n-k}(\rho)\big)^2 \big( {\mathbb E} \left[ \big(H_{k}(X_{k-1}, \varepsilon_k)\big)^p \right]\big)^{\frac 2 p} \\
    &\leq&  A_p(n,\rho),
\end{eqnarray*}
which gives the desired inequality. \hfill\qed

\subsection{Rosenthal's inequality}
Under the same assumptions as in the previous subsection, one can prove the following Rosenthal-type inequality.
\begin{prop} \label{Ros}
Let $p\geq 2$, and consider the variables $L_k(X_{k-1})$  defined in \eqref{M2cond}. If  \eqref{shnbs} holds,
then there exists a constant $C_p$ depending only on $p$ such that
\begin{equation}
\|S_n\|^p_p   \leq C_p \bigg(  \mathbb{E}\Big[ \Big( \big(K_{n-1}(\rho) \big)^2 A_1(2)  +     \sum_{k=2}^n \big( K_{n-k} (\rho)\big)^2 L_k(X_{k-1})  \Big)^{p/2} \Big]
+   \sum_{k=1}^n \big(K_{n-k}(\rho) \big)^p  A_k(p) \bigg).  \label{vBEs}
\end{equation}
\end{prop}
\begin{rem}
Assume that $F_n$ satisfies \eref{c2}.  Then, according to Remark \ref{remc2},
 it follows from the proof of Proposition \ref{Ros} that
 inequality \eref{vBEs} remains true if the second condition of  \eref{shnbs} is replaced by \eqref{weaker}.
\end{rem}
\noindent\emph{Proof.} From point 2 of Proposition \ref{McD},  it is easy to see that
\begin{equation*}
   \sum_{k=1}^n\mathbb{E}[ M_k^2 |\mathcal{F}_{k-1}]  \leq \big( K_{n-1} (\rho)\big)^2 \mathbb{E}  [ \big(G_{X_1}(X_1) \big)^{2} ]+  \sum_{k=2}^n \big( K_{n-k}(\rho) \big)^2
   L_k(X_{k-1}) \, ,
\end{equation*}
and that
\begin{align*}
   \sum_{k=1}^n\mathbb{E}[| M_k|^p]  &\leq \big( K_{n-1} (\rho) \big)^p \mathbb{E} [ \big( G_{X_1}(X_1) \big)^{p} ]+    \sum_{k=2}^n \big( K_{n-k} (\rho)\big)^p \mathbb{E} \big[  \big( H_{k} (X_{k-1}, \varepsilon_k) \big)^p   \big] \\
   & \leq \big( K_{n-1}(\rho)\big)^p A_1(p)  +     \sum_{k=2}^n  \big(K_{n-k}(\rho) \big)^p A_k(p)  .
\end{align*}
The desired inequality is then a direct consequence of
Rosenthal's inequality for martingales (see for instance Theorem 2.12 of Hall and Heyde \cite{HH80}).   \hfill\qed

\subsection{von Bahr-Esseen's inequality}
In this subsection, we assume that the dominating random variables $G_{X_1}(X_1)$
and $H_{k}  (X_{k-1}, \varepsilon_k)$ have  a moment of order $p \in (1,2]$.
\begin{prop}\label{VBEI}
Let  $p \in (1, 2]$,  and assume that  \eqref{shnbs} holds.
Then
\begin{equation}\label{vBE}
  \| S_n \|_p^p  \leq     A_p(n,\rho) ,
\end{equation}
 where
\begin{equation}\label{Ap}
A_p(n,\rho)= \big( K_{n-1}(\rho) \big )^p A_1(p)  +
2^{2-p}   \sum_{k=2}^n \big( K_{n-k}(\rho) \big)^p  A_k(p) \, .
\end{equation}
\end{prop}

\begin{rem}
Assume that $F_n$ satisfies \eref{c2}. Then,   according to Remark \ref{remc2}, it follows from the proof of Proposition \ref{VBEI} that
  inequality \eref{vBE} remains true if the second condition of  \eref{shnbs} is replaced by \eqref{weaker}\end{rem}
\noindent\emph{Proof.} Using an improvement of the von Bahr-Esseen inequality  (see  inequality (1.11) in Pinelis \cite{P10}), we have
$$
\| S_n \|_p^p \leq \|M_1\|_p^p +  \tilde C_p \sum_{k=2}^n  \| M_k \|_p^p \, ,
$$
where the constant $\tilde C_p$ is described in Proposition 1.8 of Pinelis \cite{P10}, and is such that $\tilde C_p \leq 2^{2-p}$
for any $p \in [1,2]$.
By Proposition \ref{McD}, it follows that
\begin{align*}
\| S_n \|_p^p   &\leq    \big(  K_{n-1}(\rho) \big)^p   {\mathbb E} \left[  \big(  G_{X_1}(X_1) \big)^p \right]    + \tilde C_p
    \sum_{k=2}^n \big( K_{n-k}(\rho) \big)^p {\mathbb E} \left[ \big(  H_{k}(X_{k-1}, \varepsilon_k) \big)^p  \right] \\
    &\leq   \big( K_{n-1}(\rho) \big)^p A_1(p)   +
\tilde C_p    \sum_{k=2}^n \big( K_{n-k} (\rho)\big)^p A_k(p) \, ,
\end{align*}
which is the desired inequality. \hfill\qed

\medskip

\paragraph{Aknowledgements} P. Doukhan wants to thank Tianjin  University for its hospitality.
His work has been developed within the MME-DII center of excellence (ANR-11-LABEX-0023-01) \& PAI-CONICYT MEC N$^o$ 80170072.
X. Fan has been partially  supported by the  National Natural Science Foundation of China (Grant no.\ 11601375).


\section{Introduction}\label{sec:intro}

With the advent of social media platforms and e-commerce systems, such as Amazon and Netflix, users express their preferences in multiple domains~\cite{AliannejadiRC17,RafailidisC16,RafailidisC17}. For example, users can rate items from different domains, such as books and retail products on Amazon, or users express their opinion on different social media platforms, such as Facebook and Twitter. The sparsity of user preferences in each domain limits the recommendation accuracy of collaborative filtering strategies~\cite{CREM10,Her04,Kor09}. To overcome the shortcomings of single-domain models, cross-domain recommendation strategies exploit\footnote{Different from multimedia retrieval~\cite{RafailidisNM11} and cross-domain retrieval~\cite{sigir/RafailidisC16}, in this study cross-domain recommendation aims at capturing multi-preferences across different platforms.} the additional information of user preferences in multiple auxiliary/source domains to face the sparsity problem and leverage the recommendation accuracy in a target domain~\cite{LI09}. The source domains can be categorized based on users' and items' overlaps, that is, full-overlap, and partial or non user/item overlap between the domains~\cite{CREM11,TKDD15}. In this study, we focus on partial users' overlaps between the target and the source domains, as it reflects on the real-world setting, where for instance users open multiple accounts on social media platforms or interact with different types of content on the same platform~\cite{Khan17}. Generating cross-domain recommendations is a challenging task, as the source domains might be a potential source of noise, for example, if user preferences differ in the multiple domains, then the source domains are likely to introduce noise in the learning of the target domain~\cite{BER07,CREM11,GAO13,PAN10}. Therefore, cross-domain recommendation strategies aim to learn how to transfer the knowledge of user preferences from different domains by weighting the importance of users' different behaviors accordingly.

In the relevant literature cross-domain recommendation strategies, such as~\cite{GAO13,HU13,LI09,Lon14}, form user and item clusters to capture the relationships between multiple domains at a cluster level, thus tackling the sparsity problem; and then weigh the user preferences to generate the top-$N$ recommendations in the target domain. However, such cross-domain strategies linearly combine the cluster-based  user preferences in the target domain, which does not reflect on the real-world world scenario with users having complex behaviors across domains. More recently, to capture the non-linear associations of users' different preferences in multiple domains a few deep learning architectures have been designed for cross-domain recommendation~\cite{EL15,Hu18,Wang19}. Although these cross-domain deep learning strategies try to learn the non-linearity in users' multi-aspect preferences across domains, they do not account for the different complexities/scales of multiple domains, which might reduce the quality of recommendations. For example, if the source domains are richer than the target domain, existing deep learning cross-domain recommendation algorithms learn how to recommend items in the source domains and consider the target domain as noise. Therefore, a pressing challenge resides on how to adapt the learning process of neural architectures in cross-domain deep learning strategies, while considering the different complexities/scales of multiple domains. In particular, deep learning strategies of user preferences in various domains need to be properly balanced so that the neural network's parameters converge to robust shared parameters that are useful across all domains.

Recently, various deep learning strategies have been introduced to perform balanced learning of different tasks with various complexities/scales in natural language processing~\cite{Has17}, speech synthesis~\cite{Wu15}, image segmentation~\cite{Heg17} and object detection~\cite{Red17}. Multi-task deep learning strategies aim to find this balance by controlling the forward pass in a neural network e.g., by either constructing explicit statistical relationships between features or optimizing multi-task network architectures~\cite{Ken18,Mis16}. However, these neural models do not capture users' multiple preferences across domains, and ignore the complexity/scale of user preferences in a domain that might be too dominant when optimizing the model parameters.

In this paper, we propose an Adaptive Deep Learning model for Cross-domain recommendation, namely ADC. In particular our contribution is summarized as follows:

\begin{itemize}
\item We design a neural architecture and formulate a cross-domain loss function to capture the non-linear associations between user preferences across different domains.
\item We propose an efficient algorithm for cross-domain loss balancing which directly tunes gradient magnitudes and adapts the learning rates based on the domains' complexities when training the model. In doing so, ADC controls and adjusts the contribution of each domain when optimizing the model parameters.
\end{itemize} In our experiments on six cross-domain recommendation tasks from Amazon, we show the superiority of the proposed ADC model over other baseline methods, demonstrating the effectiveness of the proposed adaptive neural learning strategy.

The remainder of the paper is organized as follows, Section~\ref{sec:rel} reviews related work of cross-domain recommendation, and then Section~\ref{sec:prop} presents the proposed ADC model. Finally, in Section~\ref{sec:exp} we evaluate the performance of the proposed model against other baseline models, and Section~\ref{sec:conc} concludes the study.

\section{Related Work}\label{sec:rel}
Cross-domain recommendation algorithms differ in how the perform knowledge transfer of user preferences across domains to produce recommendations~\cite{Khan17}. For example, the graph-based method of~\cite{CREM11} models the similarity relationships as a direct graph and explore all possible paths connecting users or items to capture the cross-domain relationships. Hu et al.~\cite{HU13} model a cubic user-item-domain matrix (tensor), and by applying factorization the respective latent space is constructed to generate cross-domain recommendations. Li et al.~\cite{LI09} compute user and item clusters for each domain, and then encode the cluster-based patterns in a shared codebook. Finally, the knowledge of user preferences is transferred across domains through the shared codebook. Gao et al.~\cite{GAO13} calculate the latent factors of user-clusters and item-clusters to construct a common latent space, which represents the preference patterns e.g., rating patterns, of user clusters on the item clusters. Then, the common cluster-based preference pattern that is shared across domains is learned following a subspace strategy, so as to control the optimal level of sharing among multiple domains. Cross-domain collaborative filtering with factorization machines (FMs), presented in~\cite{Lon14}, is a state-of-the-art cross-domain recommendation which extends FMs~\cite{Rendle12}. It is a context-aware approach which applies factorization on the merged domains, aligned by the shared users, where the source domains are used as context.  However, these cross-domain recommendation strategies do not capture the non-linearity of users' preferences in multiple domains~\cite{Hu18}.

To overcome the limitations of linear cluster-based strategies, Elkahky et al.~\cite{EL15} propose a multi-view deep learning approach for content-based recommendation across domains. In their model, the item and user features are acquired from different sources of Microsoft products, such as Windows Apps recommendation, News recommendation, and Movie/TV recommendation. Wang et al.~\cite{Wang19} introduce a multi-task feature learning algorithm for knowledge graph enhanced recommendation, introducing a deep end-to-end framework that utilizes a knowledge graph embedding task for the recommendation task. The two tasks are associated by cross and compress units, which automatically share latent features and learn high-order interactions between items in the recommendation system and entities in the knowledge graph. Hu et al.~\cite{Hu18} jointly learn neural networks to generate cross-domain recommendations based on stich units~\cite{Mis16}, introducing a shared auxiliary matrix to couple two hidden layers when training the networks in parallel. However, these deep learning strategies for cross-domain recommendation ignore the domains' different complexities during learning and do not weigh the loss functions accordingly. Consequently, the non-weighting of domains' loss functions might degrade the quality of recommendations as we will show in our experiments in Section~\ref{sec:exp}.

\section{The Proposed ADC Model} \label{sec:prop}
\subsection{Cross-domain Loss Function} \label{sec:cross}
In our setting we assume that we have $p$ different domains, where $n_k$ and $m_k$ are the numbers of users and items in the $k$-th domain, respectively, with $k=1,\dots,p$. In each matrix $R^{(k)}$, we store the user-item interactions  e.g., ratings, number of clicks or views, and so on.
We define two disjoint sets, a set ${\mathcal{I}^+_u}^{(k)}$ of observed items that user $u$ has already interacted with in domain $k$, and a set ${\mathcal{I}^-_u}^{(k)}$ of  unobserved items. For each observed item $i^+\in {\mathcal{I}^+_u}^{(k)}$, we randomly sample negative/unobserved items $i^-\in {\mathcal{I}^-_u}^{(k)}$, for each user $u$. According to the Bayesian Pairwise Ranking (BPR) criterion~\cite{BPR}, the goal is to learn to rank the observed items higher than the unobserved ones, having the following single-domain loss function for each domain $k$:
\begin{equation} \label{eq:loss}
L_k = - \sum_{(u, i^+,i^-)} \log \sigma({\mathbf{u}^{(k)}_u}^\top {\mathbf{v}^{(k)}_{i+}} - {\mathbf{u}^{(k)}_u}^\top  {\mathbf{v}^{(k)}_{i-}})
\end{equation}
where $\sigma(x)=1/\big(1+\exp(-x)\big)$ is the logistic sigmoid function. For each domain $k$ we consider the user latent vectors ${\mathbf{u}^{(k)}_u} \in \mathbb{R}^{d \times 1}$ and item latent vectors ${\mathbf{v}^{(k)}_i} \in \mathbb{R}^{d \times 1}$, with $u=1,\ldots,n_k$,  $i=1,\ldots,m_k$ and $d$ being the number of latent dimensions.

In this study we consider users' partial overlaps across the $p$ domains. This means that at the same time we have to regularize the different user latent vectors of the same user $u$ across all the domains. Notice that a user might not exist in all the $p$ domains. In case that user $u$ does not appear in a $k$-th domain we average her latent vector by all the latent vectors of the domains that she expressed her preferences. Thus, we reformulate the single-domain loss function of Equation~\ref{eq:loss} as follows:

\begin{multline} \label{eq:loss2}
L_k = - \sum_{(u, i^+,i^-)} \log \sigma({\mathbf{u}^{(k)}_u}^\top {\mathbf{v}^{(k)}_{i+}} - {\mathbf{u}^{(k)}_u}^\top  {\mathbf{v}^{(k)}_{i-}})  \\ +   \lambda\sum\limits_{q \neq k} || \mathbf{u}_u^{(q)} - \mathbf{u}_u^{(k)} ||_2^2
\end{multline}
where the last term expresses the approximation error of the user latent vectors in domains $q$ and $k$, and $\lambda$ controls the regularization. Provided that we have $p$ different domains, in our problem we have to jointly learn all the $p$ different single-domain loss functions of Equation~\ref{eq:loss2}, formulating the following \emph{cross-domain loss function}:
\begin{equation} \label{eq:loss3}
L_{cross} = \sum_{k=1}^{p}w_k L_k
\end{equation}

\textbf{Weights' Adaptive Learning.} Weights $w_k$ control the influence of each single-domain loss function when optimizing the joint cross-domain loss function. In our problem we have to perform adaptive learning of weights $\{w_1,w_2,\ldots,w_p \}$ while training our model based on the cross-domain loss function in Equation~\ref{eq:loss3}. As we will show in Section~\ref{sec:arc} a weight $w_k$  directly couples to the backpropagated gradient magnitudes for each domain, thus the challenge is to find the optimal value for each $w_k$ at each learning step that balances the contribution of each domain to the learning process of the cross-domain loss function. To optimize the weights $w_k$, we propose an adaptive learning algorithm in our model's cross-domain neural network that penalizes the network when backpropagated gradients from any domain are too large or too small (Section~\ref{sec:adap}). The correct balance is achieved when domains are learned at similar rates; if a domain is learned relatively quickly, then its weight $w_k$ should decrease relative to other domain weights to allow other domains to more influence the model training. In particular, when learning the weights of the cross-domain loss function we aim to the following goals:

\begin{itemize}
\item Provided that the $p$ different domains might have different complexity, we have to adaptively learn the weight $w_k$ of each domain in each iteration/epoch during the optimization. To achieve this, we have to compute the gradients of the weights accordingly, by placing gradient norms for the $p$ different domains on a common scale based on their relative magnitudes.
\item In addition, we have to dynamically adjust gradient norms so that the $p$ different single-domain loss functions in Equation~\ref{eq:loss3} are minimized at similar learning rates.
\end{itemize}

\subsection{ADC Neural Architecture}\label{sec:arc}
\begin{figure*} [t]
  \centering
    \includegraphics[width=0.55\textwidth]{figure.pdf}
\caption{An overview of the proposed ADC model. The MLP network with $h$ hidden layers computes the non-linear associations between the user latent vectors in the $p$ domains. The decoupled hidden reprentations $\mathbf{z}_u^{(k)}$ are learned based on the weights in a matrix $W$ using a loss function $L_{grad}$. Finally, the weights $w_k$ of the cross-domain loss function $L_{cross}$ are adjusted based on the gradients $\nabla L_{grad}$ in each backpropagation step.} \label{fig:over}
\end{figure*}

Figure~\ref{fig:over} presents an overview of the proposed cross-domain neural network, which consists of the following components:

\textbf{(1):} The input layer at the bottom of our architecture is a concatenated vector $\mathbf{u}_{con}$ of the $p$ latent vectors of user $u$. To initialize the user latent vectors we factorize  each matrix $R^{(k)}$ separately, that is minimizing the approximation error $\sum_{(u,i)} || R^{(k)}_{ui} - {\mathbf{u}^{(k)}_u}^\top {\mathbf{v}^{(k)}_{i}} ||^2$ for each domain $k=1,\ldots,p$.

\textbf{(2):} The MLP network with the $h$ hidden layers is a fully-connected network with ReLU activations. The MLP network tries to learn the non-linear associations between the user latent vectors. This is achieved by computing the MLP network's weights $\mathcal{A}$ via standard gradient descent in the backward pass of the backpropagation algorithm.

\textbf{(3):} The hidden representations of the ($h$-th) last shared layer of the MLP network is split/decoupled into $p$ different $d$-dimensional representations $\mathbf{z}_u^{(k)}$, which are called \emph{decoupled hidden representations} for each domain $k$ and are computed based on the weights in matrix $W$. In particular, matrix $W$ is the last shared layer of weights of the decoupled hidden representations where we perform adaptive learning and apply normalization to gradients based on a loss function $L_{grad}$ to consider the different complexities of each domain $k$, as we will describe in Section~\ref{sec:adap}.

\textbf{(4):} Having computed the gradients $\nabla w_k L_{grad}$,  $\forall k=1,\ldots,p$, we update/adjust the weights $w_k$ of the cross-domain loss function $L_{cross}$.

\subsection{Adaptive Learning in the Cross-domain Neural Network}\label{sec:adap}
\textbf{Gradient Norms \& Learning Rates.}  In our proposed neural architecture we consider the following gradient norms and learning rates:
\begin{itemize}
\item $G_W^{(k)}(t) = || \nabla_W w_k(t)L_k(t) ||_2$: the $L2$ norm of the gradient of the weighted single-domain loss $w_k(t)L_k(t)$ with respect to the weights in $W$.
\item $\hat{G}_W(t)=E_{dom}[G_W^{(k)}(t)]$: the average gradient norm across all the $p$ domains at iteration $t$.
\item $\tilde{L}_k(t)=L_k(t)/L_k(0)$: the single-domain loss learning ratio for domain $k$ at iteration $t$. Lower values of $\tilde{L}_k(t)$ correspond to a faster learning rate for domain $k$. In our implementation we set $L_k(0) = \log{(p)}$.
\item $r_k(t)=\tilde{L}_k(t)/E_{dom}[\tilde{L}_k(t)]$: the relative inverse learning rate of the $k$-th domain.
\end{itemize}

\textbf{The Loss Function $L_{grad}$.} At the $t$-th iteration of our algorithm the cross-domain loss function is formulated as follows,  $L_{cross}(t) = \sum_{k=1}^{p}w_k(t) L_k(t)$. As stated in Section~\ref{sec:cross} our model has to compute a common scale for gradient magnitudes, and control the learning rates of the different domains at the last layer of the decoupled hidden representations. The common scale for gradients is the average gradient norm $\hat{G}_W(t)$ which serves as a baseline at each iteration $t$ to determine the relative gradient sizes. The relative inverse learning rate of a domain $r_k(t)$ is used to rate balance the gradients of all $p$ domains. The higher the value of $r_k(t)$, the higher the gradient magnitudes should be for domain $k$, forcing the respective single-domain loss function $L_k(t)$ to be learned more quickly. Therefore, the gradient norm for the $k$-th domain is computed as follows:
\begin{equation}\label{eq:tun}
G_W^{(k)}(t) \leftarrow \hat{G}_W(t) [r_k(t)]^\gamma , \quad \forall k=1,\ldots,p
\end{equation}
We define a hyperparameter $\gamma$ as the \emph{asymmetry parameter} of our model which controls the strength of forcing the single-domain loss functions $L_k$ to be learned at a common learning rate. In cases where domains are very different in their complexity, leading to significantly different learning rates between the domains over the optimization algorithm, a higher value of $\gamma$ should be used to enforce stronger learning rate balancing. On the other hand, when domains are more symmetric a lower value of $\gamma$ is required. Note that $\gamma$=0 will set the norms of the backpropagated gradients from each domain to be equal to $W$. The effects of $\gamma$ on the model's performance is further studied in Section~\ref{sec:param} .

Equation~\ref{eq:tun} gives a target norm for each $k$-th domain's gradient norm. In our algorithm we have to update our loss weights $w_k(t)$ to move the gradient norm towards the target norm for each domain. We define an $L1$ loss function $L_{grad}$ between the actual and target gradient norms at each iteration for each domain, summed over all domains as follows:
\begin{equation}\label{eq:lgrad}
\min_{w_k} L_{grad} = \sum_{k=1}^p || G_W^{(k)}(t) - \hat{G}_W(t) [r_k(t)]^\gamma ||_1
\end{equation}
When differentiating the loss $L_{grad}$ with respect to the weight $w_k$, we treat the target gradient norm $\hat{G}_W(t) [r_k(t)]^\gamma$ as a fixed constant, with $w_k$ controlling the gradient magnitude per domain. The computed gradients $\nabla w_k L_{grad}$ are then used to update each $w_k$ via gradient descent as shown in Figure~\ref{fig:over}.

Our adaptive learning algorithm of the proposed ADC model in the cross-domain neural network is outlined as follows. Having computed the user and item latent vectors for each domain separately, then we initialize the weight $w_k$ of the cross-domain loss function $L_{cross}$. To initialize the MLP network's weights in $\mathcal{A}$, we first train our model with random initializations using only one hidden layer in the MLP network. Then, the trained parameters are used to initialize the MLP network's weights for $h$ hidden layers. Finally, we split our training data into mini-batches of concatenated vectors $\mathbf{u}_{con}$, and in each iteration we train our model to adjust the weights $w_k$ while minimizing the cross-domain loss function $L_{cross}$, as described in Section~\ref{sec:arc}.

\section{Experimental Evaluation} \label{sec:exp}
\subsection{Cross-domain Recommendation Tasks} Our experiments were performed on six cross-domain tasks from the Amazon dataset\footnote{\url{https://snap.stanford.edu/data/}}~\cite{Les07}. The items are grouped in categories/domains, and we evaluate the performance of our model on the six largest domains. The main characteristics of the evaluation data are presented in Table~\ref{tab:data}, showing the sparsity in user preferences for each domain. Notice that the domains have different complexities/scales, corresponding to the real-world setting. For example, the largest domain ``music'' contains 174K ratings of 69K users on 24K items, whereas the smallest domain ``toys'' has 13K ratings of 9K users on 3K items.

\begin{table}[h]
\centering
\caption{The six cross-domain recommendation tasks.} \label{tab:data}
\vspace{-0.2cm}
\begin{center}%
\begin{tabular}{l@{\quad\quad}c@{\quad}c@{\quad}c@{\quad}c}\hline
Domain & Users & Items & Ratings & Density (\%) \\ \hline
electronics & 18,649 & 3,975  &  23,009 & 0.031\\
kitchen & 16,114 & 5,511  & 19,856 & 0.022\\
toys & 9,924 & 3,451 & 13,147 & 0.038\\
dvd & 49,151 & 14,608 & 124,438 & 0.017\\
music & 69,409 & 24,159 & 174,180  & 0.010\\
video & 11,569  &5,223  & 36,180  & 0.059\\ \hline
\end{tabular}
\end{center}
\end{table}

\subsection{Evaluation Protocol} In each out of the six cross-domain recommendation tasks, the goal is to generate recommendations for a target domain, while the remaining five domains are considered as source domains. We trained the examined models on the 50\% of the ratings of the six domains. For each cross-domain recommendation task, we used 10\% of the ratings in the target domain as cross-validation set to tune the models' parameters and evaluate the examined models on the remaining test ratings. To remove user rating bias from our results, we considered an item as relevant if a user has rated it above her average ratings and irrelevant otherwise~\cite{Rec17}. We measured the quality of the top-$N$ recommendations in terms of the ranking-based metrics recall and Normalized Discounted Cumulative Gain (NDCG@N). Recall is the ratio of the relevant items in the top-$N$ ranked list over all the relevant items for each user. NDCG measures the ranking of the relevant items in the top-$N$ list. For each user the Discounted Cumulative Gain (DCG) is defined as: $$DCG@N = \sum_{j=1}^{N}{\frac{2^{rel_j}-1}{\log_2{j+1}}}$$ where $rel_j$ represents the relevance score of item $j$, that is binary in our case, i.e., relevant or irrelevant. NDCG is the ratio of DCG/iDCG, where iDCG is the ideal DCG value given the ratings in the test set. We repeated our experiments five times and in our results we report average recall and NDCG over the five runs.

\subsection{Compared Methods}
In our experiments we compare the following methods:
\begin{itemize}
\item \emph{\textbf{BPR}}~\cite{BPR}: a baseline ranking model that tries to rank the observed/rated items over the unobserved ones. BPR is a single-domain method and does not exploit users' preferences across different domains when generating recommendations.
\item \emph{\textbf{CLFM}}~\cite{GAO13}: a cross-domain Cluster-based Latent Factor Model which uses joint non-negative tri-factorization to construct a latent space to represent the rating patterns of user clusters on the item clusters from each domain, and then generates the cross-domain recommendations based on a subspace learning strategy.
\item \emph{\textbf{CDCF}}~\cite{Lon14}: a cross-domain collaborative filtering strategy that extends factorization machines (FMs) by factorizing the merged domains, aligned by the shared users.
\item \emph{\textbf{ScoNet}}~\cite{Hu18}: a cross-domain model that jointly learns stich networks, with a shared auxiliary matrix to couple two hidden layers when training the networks in parallel. In our experiments, we used the variant of ScoNet with $L1$-norm to force the matrices to be sparse, as suggested in~\cite{Hu18}.
\item \emph{\textbf{ADC}}: the proposed cross-domain model that performs adaptive weighting of the cross-domain loss function, by adjusting the learning rates and gradient magnitudes, to control the influence of each domain when training the model based on the domains' complexities.
\end{itemize}

\begin{table}[t]
\centering
\caption{Performance evaluation in terms of NDCG@10. Bold values denote the best scores, using the paired t-test ($p<$0.05). } \label{tab:res1}
\vspace{-0.2cm}
\begin{center}%

\begin{tabular}{l@{\quad}c@{\quad}c@{\quad}c@{\quad}c@{\quad}c@{\quad}c}\hline
			 	& BPR  & CLFM & CDCF & ScoNet & ADC & Improv. (\%)\\\hline
electronics 		&	0.1938 &	0.2385 &	0.2577 &	0.2791 &	\textbf{0.3037} & \textbf{8.81}  \\
kitchen 			&	0.1356	 & 0.1502 &	0.1589 &	0.1774 &	\textbf{0.1952} & \textbf{10.03}\\
toys			&	0.1624	 & 0.1763 &	 0.1894 & 0.2013 & \textbf{0.2195} & \textbf{9.04}\\
dvd 		&	.0.3847	& 0.4012 &	0.4457 &	0.4662 &	\textbf{0.4980} & \textbf{6.82}\\
music 	&	0.3291	& 0.3728	& 0.4032	& 0.4322	 & \textbf{0.4748}	&  \textbf{9.85}\\
video 			&	 0.5421 &	0.5711 &	0.6336 &	0.6805 &	\textbf{0.7073} & \textbf{3.93} \\ \hline
\end{tabular}
\end{center}
\end{table}

\begin{figure*}[t]
\centering
\begin{tabular}{cc}
\hspace{-0.5cm}\includegraphics[width=\columnwidth]{1.pdf} & \hspace{-0.75cm}\includegraphics[width=\columnwidth]{2.pdf}\\
\hspace{-0.5cm}\includegraphics[width=\columnwidth]{3.pdf} & \hspace{-0.75cm} \includegraphics[width=\columnwidth]{4.pdf} \\
\hspace{-0.5cm}\includegraphics[width=\columnwidth]{5.pdf} & \hspace{-0.75cm}\includegraphics[width=\columnwidth]{6.pdf}\\
\end{tabular}
\vspace{-0.1cm}\caption{Effect on recall when varying the top-$N$ recommendations.} \label{fig:res1}
\end{figure*}

\subsection{Performance Evaluation}
Table~\ref{tab:res1} presents the performance of the examined models in terms of NDCG@10. In addition, Figure~\ref{fig:res1} reports the experimental results in terms of recall when varying the number of top-$N$ recommendation in 5, 10, 15 and 20. On inspection of the results, we observe that all the cross-domain recommendation strategies outperform the single-domain BPR strategy in all cases, indicating the crucial role of incorporating the knowledge of user preferences from multiple domain when generating recommendations. Compared to the cluster-based strategies CLFM and CDCF, the most competitive deep learning model ScoNet performs better, as ScoNet can capture the non-linearity in user preferences across the six domains. Using the paired t-test we found that ADC is superior over all the competitive approaches for $p<$0.05. The proposed ADC model achieves an average improvement of 6.14 and 8.08\% in term of recall and NDCG respectively, when compared with the second best method ScoNet. This occurs because ADC not only can compute the non-linear associations among users' different preferences in the six domains based on the cross-domain loss function of our neural architecture, but also ADC adjusts the weights of each single-domain loss function and controls the contribution of each domain when training the models based on the domains' complexities.

\begin{figure*}[t]
\centering
\begin{tabular}{cc}
\includegraphics[width=\columnwidth]{7.pdf} \hspace{0.1cm} & \includegraphics[width=\columnwidth]{8.pdf} \\
\includegraphics[width=\columnwidth]{9.pdf}  \hspace{0.1cm} & \includegraphics[width=\columnwidth]{10.pdf}\\
 \includegraphics[width=\columnwidth]{11.pdf} \hspace{0.1cm} &  \includegraphics[width=\columnwidth]{12.pdf} \\
\end{tabular}
\vspace{-0.1cm}\caption{Effect on NDCG when varying the number of shared hidden layers $h$ in our cross-domain neural architecture of Figure~\ref{fig:over}.} \label{fig:res2}
\end{figure*}

\subsection{Parameter Analysis} \label{sec:param}
\textbf{The influence of the shared hidden layers.} In the proposed ADC model to better capture the non-linearity of user preferences in multiple domains, we use $h$ shared hidden layers as illustrated in our cross-domain neural architecture of Figure~\ref{fig:over}, in order to train the model parameters based on the cross-domain loss function via our adaptive learning strategy. The number of $h$ hidden shared layers is an important parameter of our ADC model, demonstrating the importance of deep learning when generating cross-domain recommendations. In this set of experiments, we fix the number of negative samples $|{\mathcal{I}^-_u}^{(k)}|$=5 for each observed rating/sample of each domain, and the number of latent dimensions $d$=100. Notice that we keep the number of negative samples and latent dimensions fixed as we observed that after the fixed values ADC did not significantly increase the recommendation accuracy without paying off in terms of computational cost.  Figure~\ref{fig:res2} presents the effect on NDCG when varying the number of hidden layers from 1 to 5 by a step of 1. On inspection of the results in Figure~\ref{fig:res2} we set $h$=2 for the smallest domain ``toys'', $h$=4 for the largest domains ``dvd'' and ``music'', while for the remaining domains ``electronics'', ``kitchen'' and ``video'' that have similar complexities/scales we set $h$=3. Clearly, the number of hidden layers depends on the complexity/scale of the target domain, where more hidden layers are required for larger target domains.

\begin{figure*}[t]
\begin{tabular}{cc}
\includegraphics[width=\columnwidth]{13.pdf} \hspace{0.1cm} & \includegraphics[width=\columnwidth]{14.pdf} \\
\includegraphics[width=\columnwidth]{15.pdf}  \hspace{0.1cm} & \includegraphics[width=\columnwidth]{16.pdf}\\
 \includegraphics[width=\columnwidth]{17.pdf} \hspace{0.1cm} &  \includegraphics[width=\columnwidth]{18.pdf} \\
\end{tabular}
\vspace{-0.1cm}\caption{Effect on NDCG when varying the \emph{asymmetry} parameter $\gamma$ in the loss function $L_{grad}$.} \label{fig:res3}
\end{figure*}

\textbf{The effect of the asymmetry parameter.} As stated in Section~\ref{sec:adap}, the hyperparameter $\gamma$ controls the adjustment of gradients magnitudes and learning rates for each domain in the loss function $L_{grad}$ of Equation~\ref{eq:tun} based on the domains' complexities/scales. In Figure~\ref{fig:res3} we examine the performance of the proposed ADC model when varying the hyperparameter $\gamma$ in [0, 0.5, 1, 1.5, 2, 2.5, 3]. Notice that lower $\gamma$ values are  required for more symmetric domains, while higher $\gamma$ values penalize the network when backpropagated gradients from any domain are too large or too small. The special case of $\gamma$= 0 corresponds to equal weights $w_k$=1 in the cross-domain loss function of Equation~\ref{eq:loss3}. Clearly, as we can observe from the results from Figure~\ref{fig:res3}, ADC under-performs when setting   $\gamma$ = 0. This occurs because of the asymmetry in the evaluation domains, as shown in Table~\ref{tab:data}, demonstrating that our adaptive learning strategy plays a key role in the performance of the proposed ADC model. Due to the asymmetric nature of the evaluation domains, we set $\gamma=2$ based on the experimental results of Figure~\ref{fig:res3} for all domains, as the model becomes unstable for different $\gamma$ values. In the exceptional case of the largest domain ``music'' we fix $\gamma=1.5$, as the ``music''  domain has the highest complexity, thus is less affected by the gradient and learning rate balancing of our adaptive learning strategy.

To further evaluate the performance of our adaptive learning strategy we repeated our experiments by splitting the six domains of Table~\ref{tab:data} into the following two symmetric subsets of domains, that is, the two largest domains in Set 1=\{``dvd'', ``music''\} and the remaining domains in Set 2=\{``electronics'', ``kitchen'', ``toys'', ``video''\}. The best $\gamma$ values are 1 and 0.5 for Set 1 and Set 2, respectively. As expected, compared to the case of all six domains, less balancing (lower $\gamma$ value) in the loss function $L_{grad}$ is required, as both subsets Set 1 and Set 2 are more symmetric. Finally, to further verify the importance of our adaptive learning strategy, we repeated our experiments by generating an extremely asymmetric subset Set 3=\{``music'',  ``toys''\}, that is, the largest and smallest domains respectively. In this asymmetric case of Set 3 we fix $\gamma$=2.5, requiring more balancing (higher $\gamma$ value) compared to the case of all six domains. Our experimental results confirm that indeed an adaptive learning strategy is needed when generating cross-domain recommendation for domains with different complexities/scales.

\section{Conclusions}\label{sec:conc}
In this paper we presented ADC, an adaptive deep learning strategy for cross-domain recommendations. The two key factors of ADC are (i) to capture the non-linear associations of user preferences across domains by formulating a joint cross-domain loss function in our deep learning strategy and (ii) to adjust and weigh the influence of each domain when optimizing the model parameters based on the domains' complexities by applying an adaptive learning algorithm. Our experimental evaluation on six cross-domain recommendation tasks demonstrated the effectiveness of the proposed ADC model, evaluated against other state-of-the-art methods. Compared to the second best method, the proposed ADC model attains an average improvement of 6.14 and 8.08\%  in terms of recall and NDCG in all runs. In addition, we evaluated the performance of the proposed ADC model, when the adjustment of the weights in the cross-domain loss function is missing, demonstrating the importance of the proposed adaptive deep learning strategy. Furthermore, we studied the performance of ADC in the cases of both symmetric and asymmetric subsets of domains, and we observed that in both cases the proposed adaptive deep learning strategy has a stable performance, by adjusting the weights when optimizing the model parameters accordingly.

An interesting future direction is to exploit the proposed cross-domain balancing mechanism for social event detection~\cite{RafailidisSLSD13}, information diffusion~\cite{AntarisRN14,RafailidisN15}, exploiting social information~\cite{Rafailidis16a,sigir/RafailidisC16a} and capturing users' preference dynamics~\cite{RafailidisKM17,RafailidisN15a}. In addition, as future work, we plan to extend the proposed model for sequential recommendations in cross-domain tasks. Generating sequential recommendations is a challenging task, where the goal is to predict the next item that a user will select. Although there are many single-domain strategies for sequential recommendation, such as the studies reported in~\cite{Pas18,Quad17,Yuan19}, the case of cross-domain reflects better on the real-world scenario, where not only we have to capture users' sequential behaviors, but transfer this knowledge across different domains.

\bibliographystyle{unsrt}