\section{Introduction}
Let $X_{1},...,X_{n}$ be a {sequence of samples} drawn from a distribution, its empirical mean estimator is defined by
$$\bar X=\frac{X_{1}+...+X_{n}}n.$$
$\bar X$ has an
optimal minimax mean square error among all mean estimators in all models including Gaussian distributions, but its deviation is suboptimal for heavy tail distribution \cite{C12}.

Catoni put forward in his seminal paper \cite{C12} a new ${\rm M}$-estimator for {heavy-tailed} samples with finite variance by solving the following equation about $\theta$
\begin{align*}
\sum_{i=1}^{n}\varphi\big(\beta(X_{i}-{\theta})\big)=0 \ \quad {\rm with} \quad  \ -\log\big(1-x+\frac{|x|^{2}}{2}\big)\leq\varphi(x)\leq\log\big(1+x+\frac{|x|^{2}}{2}\big),
\end{align*}
where $\beta>0$ is a parameter to be tuned and $\varphi$ is non-decreasing and called influence function. The deviation performance of this estimator is much better than $\bar X$. Catoni's idea has been broadly applied to many research problems, see for instance \cite{B-C,W-M,F-W,H18,H,L-M,S-Z-F,X-Z}. The finite variance assumption plays an important role in Catoni's analysis, but it rules out many interesting distributions such as Pareto law \cite{K17,X,C-N-X,J-L-L}, which describes the distributions of wealth and social networks.

We generalize Catoni's ${\rm M}$-estimator to the case in which samples can have finite $\alpha$-th moment with $\alpha \in (1,2)$. Our approach is by replacing Catoni's influence function with the one satisfying $-\log\big(1-x+\frac{|x|^{\alpha}}{\alpha}\big)\leq\varphi(x)\leq\log\big(1+x+\frac{|x|^{\alpha}}{\alpha}\big)$.  The choice of the new influence function is inspired by the Taylor-like expansion developed in \cite{C-N-X}. By an argument very similar to Catnoi's, we obtain a deviation upper bound which coincides with that in \cite{C12} as $\alpha \uparrow 2$ (see Theorem \ref{main1} and Remark \ref{r:MThm} below). Experiment shows that our generalized ${\rm M}$-estimator performs better than the empirical mean estimator, the smaller the $\alpha$ is, the better the performance will be.

Catoni's argument for finding ${\rm M}$-estimator can be split into two steps. The first step is to find two deterministic values $\theta_{-}$ and $\theta_{+}$, both depending on a parameter $\beta$ to be tuned later, such that the ${\rm M}$-estimator $\hat \theta$ falls between $\theta_{-}$ and $\theta_{+}$ with a high probability.  The $\theta_{-}$ and $\theta_{+}$ were obtained explicitly by solving two quadratic algebraic equations $B_{-}(\theta)=0$ and $B_{+}(\theta)=0$ respectively in \cite{C12}, whereas in our setting the corresponding equations are not quadratic and the solutions do not have explicit forms. Alternatively, we first prove that $B_{-}(\theta)=0$ has a largest solution, while $B_{+}(\theta)=0$ has a smallest one, and then use them as a replacement of $\theta_{-}$ and $\theta_{+}$ in our analysis.  The second step is to show that as one chooses $\beta>0$ sufficiently small, the difference between $\theta_{-}$ and $\theta_{+}$ can be as small as we wish,  whence the estimator can be localized in a small interval with a high probability. In our analysis, we also {choose} a sufficiently small $\beta$ (depending on $\alpha$) to make our estimator fall in a small interval with the above special solutions as its two end points. As $\alpha \uparrow 2$, our result coincides with that in \cite{C12}.
\vskip 3mm

As an application of our generalized estimator, we consider the $\ell_{1}$- regression with heavy-tailed samples studied by Zhang et al. \cite{Z-Z} who assumed the samples have finite variance. The linear regression considered in \cite{Z-Z} aims to find the minimizer $\theta^{*}$ of the minimization problem as follows
\begin{align*}
\min_{\mathbf{\theta}\in\mathbf{\Theta}} R_{\ell_{1}}(\theta) \ \ \ \ {\rm with} \ \ \ R_{\ell_{1}}(\theta)=\mathbb{E}_{(\mathbf{x},y)\sim{\bf\Pi}}\big[|\mathbf{x}^{T}\mathbf{\theta}-y|\big],
\end{align*}
where ${\bf\Pi}$ is a probability distribution, and ${ \mathbf{\Theta}\subseteq\mathbb{R}^{d}}$ is the set in which $\theta^{*}$ is located. In practice, $\mathbf{\Pi}$ is not known, one usually draws a data set $\mathcal{T}=(\mathbf{x}_{1},y_{1}),\cdots,(\mathbf{x}_{n},y_{n})$ from $\mathbf{\Pi}$ and considers the following empirical optimization problem:
\begin{align*}
\min_{\mathbf{\theta}\in\mathbf{\Theta}}\widehat{R}_{\ell_{1}}(\mathbf{\theta}) \ \ \ {\rm with} \ \ \ \widehat{R}_{\ell_{1}}(\mathbf{\theta})=\frac{1}{n}\sum_{i=1}^{n}|\mathbf{x}_{i}^{T}\mathbf{\theta}-y_{i}|.
\end{align*}
The theoretical guarantees for bounded or sub-Gaussian distributed ${\bf\Pi}$ have been discussed in many papers, see for instance \cite{B-M,K11,Z-Y-J}.

Inspired by Catoni's work, Zhang et al. considered the case that ${\bf\Pi}$ is {heavy-tailed} with finite variance and proposed a new minimization problem
$$\min_{\mathbf{\theta}\in\mathbf{\Theta}} \widehat R_{\varphi, \ell_{1}}(\theta) \ \ \ {\rm with} \ \ \ \widehat R_{\varphi, \ell_{1}}(\theta)=\frac{1}{n\beta}\sum_{i=1}^{n}\varphi(\beta|y_{i}-\mathbf{x}_{i}^{T}\theta|),$$
where $\varphi$ is the same as that in \cite{C12} and $\beta>0$ is a parameter to be tuned. A new estimator was established from this minimization problem and an error bound was obtained. When the sample size $n$ tends to infinity, this error bound tends to zero.

Thanks to the analysis of Section \ref{deviation}, we extend the results in \cite{Z-Z} to the case in which samples can have finite $\alpha$-th moment with $\alpha \in (1,2)$, our approach is by replacing the original $\varphi$ with the one in Section \ref{deviation} and solving the corresponding minimization problem. We establish a similar error bound for our estimator and prove that it tends to zero as $n \rightarrow \infty$.
\vskip 3mm
The organization of this paper is as follows. In Section \ref{deviation}, we give the deviation analysis of ${\rm M}$-estimator for the case that only $\alpha$-th central moment is known and show that the ${\rm M}$-estimator has a better performance compared with the empirical mean. In Section \ref{empirical}, we state the upper bounds and the corresponding lower bounds on the empirical mean. In the last section, we discuss the $\ell_{1}$-regression with heavy-tailed distributions (variance equals infinity).

\section{A generalized Catoni's ${\rm M}$-estimator and its deviation analysis}\label{deviation}

Let $(X_{i})_{i=1}^{n}$ be a sequence of i.i.d. samples drawn from some unknown probability distribution $\mathbf{\Pi}$ on $\mathbb{R}$.
We assume that there exists some $\alpha \in (1,2)$ such that
{
$$\mathbb{E}|X_{1}|^{\alpha}<\infty.$$}
Further denote
{
\begin{align*}
m=\mathbb{E}[X_{1}], \quad \quad v=\mathbb{E}|X_{1}-m|^{\alpha}.
\end{align*}
}

Inspired from Catoni's idea in \cite{C12} and the Taylor-like expansion develop in \cite{C-N-X}, we consider a non-decreasing function $\varphi:\mathbb{R}\rightarrow\mathbb{R}$ such that
\begin{align}\label{trunc}
-\log\big(1-x+\frac{|x|^{\alpha}}{\alpha}\big)\leq\varphi(x)\leq\log\big(1+x+\frac{|x|^{\alpha}}{\alpha}\big).
\end{align}
The $widest$ possible choice of $\varphi$ (see Figure \ref{figure1}) compatible with these inequalities is
{
\begin{align*}
\varphi(x)=
\begin{cases}
\log\big(1+x+\frac{x^{\alpha}}{\alpha}\big), \quad &x\geq0,\\
-\log\big(1-x+\frac{|x|^{\alpha}}{\alpha}\big), \quad &x<0.
\end{cases}
\end{align*}
}
\begin{figure}
\centering
\includegraphics[height=8cm,width=14cm]{1.eps}
\caption{$widest$ possible choice of $\varphi$}
\label{figure1}
\end{figure}

Let $\beta$ be some {strictly} positive real parameter that will be chosen later and denote the estimator of the mean $m$ by $\hat{\theta},$ which is the solution to the equation
\begin{align*}
\sum_{i=1}^{n}\varphi\big(\beta(X_{i}-\hat{\theta})\big)=0.
\end{align*}
For further use, we denote
\begin{align}\label{con}
r(\theta)=\frac{1}{\beta n}\sum_{i=1}^{n}\varphi\big(\beta(X_{i}-\theta)\big), \quad \theta\in\mathbb{R}.
\end{align}
It is easy to see $r(\theta)$ is a non-increasing random variable since $\varphi$ is non-decreasing.

Let us briefly explain how to find the estimator $\hat \theta$ into the following two steps: the first step is to find two deterministic values $\theta_{-}$ and $\theta_{+}$, both depending on $\beta$, such that $r(\theta_{-})>0>r(\theta_{+})$ with a high probability, from the non-decreasing property of $r$, we know that $\theta_{-}<\hat{\theta}<\theta_{+}$ holds with a high probability; the second is to show that as we choose $\beta>0$ sufficiently small, the difference between $\theta_{-}$ and $\theta_{+}$ can be as small as we wish,  whence the estimator can be localized in a small interval with a high probability.

\begin{lemma}
Keep the same notations and assumptions as above. Then, {for any $\theta \in \mathbb{R}$,} we have
\begin{align}\label{ineq1}
\mathbb{E}\big[\exp\big(\beta nr(\theta)\big)\big]\leq\exp\Big(n\beta(m-\theta)+\frac{2^{\alpha-1}n\beta^{\alpha}}{\alpha}\big(v+|m-\theta|^{\alpha}\big)\Big)
\end{align}
and
\begin{align}\label{ineq2}
\mathbb{E}\big[\exp\big(-\beta nr(\theta)\big)\big]
\leq \exp\Big(-n\beta(m-\theta)+\frac{2^{\alpha-1}n\beta^{\alpha}}{\alpha}\big(v+|m-\theta|^{\alpha}\big)\Big).
\end{align}
\end{lemma}
\begin{proof}
We first recall the ${\rm C}_{r}$-inequality, that is, for any $a,b\in\mathbb{R}$ and $p>0,$ we have
\begin{align*}
|a+b|^{p}\leq\max\{2^{p-1},1\}(|a|^{p}+|b|^{p}),
\end{align*}
 and if $p>1,$ it is easy to verify
\begin{align}\label{CR}
 |a+b|^{p}\leq2^{p-1}(|a|^{p}+|b|^{p}).
\end{align}
Then, noting that $X_{i},$ $i=1,\cdots,n$ are i.i.d., by (\ref{trunc}), we have
\begin{align*}
\mathbb{E}\big[\exp\big(\beta nr(\theta)\big)\big]=&\mathbb{E}\Big[\exp\big[\sum_{i=1}^{n}\varphi\big(\beta(X_{i}-\theta)\big)\big]\Big]\\
=&\Big(\mathbb{E}\Big[\exp\big[\varphi\big(\beta(X_{1}-\theta)\big)\big]\Big]\Big)^{n}\\
\leq&\Big(\mathbb{E}\Big[1+\beta(X_{1}-\theta)+\frac{\beta^{\alpha}}{\alpha}|X_{1}-\theta|^{\alpha}\Big]\Big)^{n},
\end{align*}
and noting that $\alpha\in(1,2),$ by (\ref{CR}), we further have
\begin{align*}
\mathbb{E}\Big[\exp\big(\beta nr(\theta)\big)\Big]\leq&\Big[1+\beta(m-\theta)+\frac{\beta^{\alpha}}{\alpha}\mathbb{E}|X_{1}-m+m-\theta|^{\alpha}\Big]^{n}\\
\leq&\Big[1+\beta(m-\theta)+\frac{2^{\alpha-1}\beta^{\alpha}}{\alpha}(v+|m-\theta|^{\alpha})\Big]^{n}\\
\leq&\exp\Big(n\beta(m-\theta)+\frac{2^{\alpha-1}n\beta^{\alpha}}{\alpha}\big(v+|m-\theta|^{\alpha}\big)\Big),
\end{align*}
where the last inequality is by the inequality $1+x\leq e^{x}$ for any $x\in\mathbb{R},$ (\ref{ineq1}) is proved and the inequality (\ref{ineq2}) can be proved in the same way. The proof is complete.
\end{proof}

According to (\ref{ineq1}) and (\ref{ineq2}), for any {$\epsilon\in(0,\frac{1}{2}),$} we denote
\begin{align*}
B_{+}(\theta)=m-\theta+\frac{(2\beta)^{\alpha-1}}{\alpha}(v+|m-\theta|^{\alpha})+\frac{\log(\epsilon^{-1})}{n\beta},
\end{align*}
\begin{align*}
B_{-}(\theta)=m-\theta-\frac{(2\beta)^{\alpha-1}}{\alpha}(v+|m-\theta|^{\alpha})-\frac{\log(\epsilon^{-1})}{n\beta}.
\end{align*}

\begin{lemma}\label{highprobability}
Keep the same notations and assumptions as above. Then, {for any $\theta \in \mathbb{R}$,} we have
\begin{align}\label{high1}
\mathbb{P}\big(r(\theta)<B_{+}(\theta)\big)\geq1-\epsilon
\end{align}
and
\begin{align}\label{high2}
\mathbb{P}\big(r(\theta)>B_{-}(\theta)\big)\geq1-\epsilon.
\end{align}
In particular, {for any $\theta \in \mathbb{R}$,} we have
\begin{align}\label{high00}
\mathbb{P}\big(B_{-}(\theta)<r(\theta)<B_{+}(\theta)\big)\geq1-2\epsilon.
\end{align}
\end{lemma}

\begin{proof}
By Markov inequality and (\ref{ineq1}), we have
\begin{align*}
\mathbb{P}\big(r(\theta)\geq B_{+}(\theta)\big)=&\mathbb{P}\Big(\exp\big(n\beta r(\theta)\big)\geq\exp\big(n\beta B_{+}(\theta)\big)\Big)\\
\leq&\frac{\mathbb{E}\big[\exp\big(n\beta r(\theta)\big)\big]}{\exp\Big(n\beta\big(m-\theta+\frac{(2\beta)^{\alpha-1}}{\alpha}(v+|m-\theta|^{\alpha})+\frac{\log(\epsilon^{-1})}{n\beta}\big)\Big)}\\
\leq&\frac{\exp\Big(n\beta(m-\theta)+\frac{2^{\alpha-1}n\beta^{\alpha}}{\alpha}\big(v+|m-\theta|^{\alpha}\big)\Big)}
{\exp\Big(n\beta(m-\theta)+\frac{2^{\alpha-1}n\beta^{\alpha}}{\alpha}(v+|m-\theta|^{\alpha})+\log(\epsilon^{-1})\big)\Big)}=\epsilon,
\end{align*}
(\ref{high1}) is proved. With the help of (\ref{ineq2}), (\ref{high2}) can be proved in the same way. The estimate \eqref{high00} immediately follows from \eqref{high1} and \eqref{high2}.
\end{proof}

Let us now consider the following two equations:
\begin{align}\label{equa+}
B_{+}(\theta)=0,
\end{align}
\begin{align}\label{equa-}
B_{-}(\theta)=0,
\end{align}
the following lemma tells us that they both have {at least one solution.}

\begin{lemma}\label{existence}
 Choosing the {strictly}  positive real parameter $\beta$ satisfying
 \begin{align}\label{exisineq}
\beta^{\alpha}v\leq\frac{\alpha-1}{2^{\alpha}}-\frac{\alpha\log(\epsilon^{-1})}{2^{\alpha-1}n}.
\end{align}
Then, both equations (\ref{equa+}) and (\ref{equa-}) have at least one solution. Furthermore, choosing the parameter $\beta$ satisfying
\begin{align}\label{exisineq2}
\frac{(2\beta)^{\alpha-1}}{\alpha}(v+1)+\frac{\log(\epsilon^{-1})}{n\beta}\leq1,
\end{align}
then $\theta_{+}\in(m,m+1]$ and $\theta_{-}\in[m-1,m),$ where $\theta_{+}$ is the smallest solution to the equation $B_{+}(\theta)=0$ and $\theta_{-}$ is the largest solution to the equation $B_{-}(\theta)=0$.
\end{lemma}
\begin{proof}
When $\theta\leq m,$ $B_{+}(\theta)>0.$ When $\theta>m,$ the derivative of function $B_{+}(\theta)$ is
\begin{align*}
B_{+}'(\theta)=-1+(2\beta)^{\alpha-1}(\theta-m)^{\alpha-1}.
\end{align*}
It is easy to verify that $B_{+}(\theta)$ is decreasing in $(m,m+\frac{1}{2\beta})$ and increasing in $[m+\frac{1}{2\beta},\infty),$ so $\theta=m+\frac{1}{2\beta}$ is the minimum point of function $B_{+}(\theta)$ in $(m,\infty).$ What's more, since $\lim_{\theta\rightarrow\infty}B_{+}(\theta)=\infty$ and by (\ref{exisineq}), we have
\begin{align*}
B_{+}(m+\frac{1}{2\beta})=&\frac{(2\beta)^{\alpha-1}}{\alpha}v+\frac{1}{2\alpha\beta}+\frac{\log(\epsilon^{-1})}{n\beta}-\frac{1}{2\beta}\\
=&\frac{2^{\alpha-1}}{\alpha\beta}\big(\beta^{\alpha}v-\frac{\alpha-1}{2^{\alpha}}+\frac{\alpha\log(\epsilon^{-1})}{2^{\alpha-1}n}\big)\leq0.
\end{align*}
When $B_{+}(m+\frac{1}{2\beta})=0,$ that is, $\beta^{\alpha}v=\frac{\alpha-1}{2^{\alpha}}-\frac{\alpha\log(\epsilon^{-1})}{2^{\alpha-1}n},$ then the equation $B_{+}(\theta)=0$ has the unique solution $\theta=m+\frac{1}{2\beta}.$ When $B_{+}(m+\frac{1}{2\beta})<0,$ that is, $\beta^{\alpha}v<\frac{\alpha-1}{2^{\alpha}}-\frac{\alpha\log(\epsilon^{-1})}{2^{\alpha-1}n},$ then the equation $B_{+}(\theta)=0$ has two solutions.

Furthermore, when $\theta\leq m,$
\begin{align*}
B_{+}(\theta)>0,
\end{align*}
which implies that {the smallest solution} $\theta_{+}>m.$ By (\ref{exisineq2}), we have
\begin{align*}
B_{+}(m+1)=-1+\frac{(2\beta)^{\alpha-1}}{\alpha}(v+1)+\frac{\log(\epsilon^{-1})}{n\beta}\leq0.
\end{align*}
Hence, there exists $\tilde{\theta}\in(m,m+1]$ such that $B_{+}(\tilde{\theta})=0.$ Since $\theta_{+}$ is the smallest solution to the equation $B_{+}(\theta)=0,$ we have $\theta_{+}\in(m,m+1].$

By the same argument as above, we can also prove the equation $B_{-}(\theta)=0$ has at least one solution and $\theta_{-}\in[m-1,m)$. The proof is complete.
\end{proof}
\begin{lemma}
Let $\beta, \theta_{-}$ and $\theta_{+}$ be specified in Lemma \ref{existence}. We have
\begin{align}\label{three}
\mathbb{P}\left(\theta_{-} \le \hat{\theta} \le \theta_{+}\right) \ge {1-2 \epsilon}.
\end{align}
\end{lemma}
\begin{proof} By \eqref{high00}, we know that the following event holds with a probability {at least} $1-2\epsilon$:
$$r(\theta_{-})>0 \ \ \ {\rm and} \ \ \ r(\theta_{+})<0.$$
Since $r(\theta)$ is a continuous function and non-increasing,  $r(\theta)=0$ has a solution $\hat \theta$ between $\theta_{-}$ and $\theta_{+}$ such that
$$\theta_{-} \le \hat \theta \le \theta_{+}$$
holds with a probability {at least} $1-2 \epsilon$.
\end{proof}
\begin{remark}
From the above proof, it is easy to deduce (\ref{exisineq}) from (\ref{exisineq2}), that is, (\ref{exisineq2}) is a stronger condition.
\end{remark}

Now, we can give the main result in this section, which can give a deviation upper bound for the ${\rm M}$-estimator $\hat{\theta}$.

\begin{theorem}\label{main1}
For any {$\epsilon\in(0,\frac{1}{2})$} and positive integer $n,$ we assume
\begin{align}\label{assu}
n\geq(\frac{2v+1}{\alpha})^{\frac{\alpha}{\alpha-1}}\frac{2\alpha\log(\epsilon^{-1})}{v}.
\end{align}
Then, the inequality
\begin{align*}
|m-\hat{\theta}|< \frac{2\big(\frac{2\alpha\log(\epsilon^{-1})}{n}\big)^{\frac{\alpha-1}{\alpha}}v^{\frac{1}{\alpha}}}{\alpha-\big(\frac{2\alpha\log(\epsilon^{-1})}{nv}\big)^{\frac{\alpha-1}{\alpha}}}
=O\Big(\big(\log(\epsilon^{-1})\big)^{\frac{\alpha-1}{\alpha}}n^{-\frac{\alpha-1}{\alpha}}\Big)
\end{align*}
holds with probability {at least} $1-2\epsilon.$
\end{theorem}

\begin{remark} \label{r:MThm}
In Theorem \ref{main1}, if we take $\alpha=2,$ then the right hand side is $O\Big(\big(\log(\epsilon^{-1})\big)^{\frac{1}{2}}n^{-\frac{1}{2}}\Big),$ which has the same order as \cite[Proposition 2.4]{C12}.
\end{remark}

\begin{proof}
By (\ref{assu}),  (\ref{exisineq2}) is fulfilled and thus
 Lemma \ref{existence} tells us that the equation
\begin{align*}
B_{+}(\theta)=m-\theta+\frac{(2\beta)^{\alpha-1}}{\alpha}(v+|m-\theta|^{\alpha})+\frac{\log(\epsilon^{-1})}{n\beta}=0
\end{align*}
has the smallest solution $\theta_{+}\in(m,m+1].$ Denote $x=m-\theta,$ $x_{+}=m-\theta_{+}$ and
\begin{align*}
\tilde{B}_{+}(x)=x+\frac{(2\beta)^{\alpha-1}}{\alpha}(v+|x|^{\alpha})+\frac{\log(\epsilon^{-1})}{n\beta},
\end{align*}
then $\tilde{B}_{+}(x_{+})=0$ with $x_{+}\in[-1,0).$ Since $\alpha \in (1,2)$, we further have
\begin{align}\label{coup}
x_{+}+\frac{(2\beta)^{\alpha-1}}{\alpha}(v-x_{+})+\frac{\log(\epsilon^{-1})}{n\beta}\geq0.
\end{align}
By (\ref{exisineq2}), we have $1-\frac{(2\beta)^{\alpha-1}}{\alpha}>0,$ solving \eqref{coup} gives
\begin{align*}
x_{+}\geq-\frac{(2\beta)^{\alpha-1}v+\frac{\alpha\log(\epsilon^{-1})}{n\beta}}{\alpha-(2\beta)^{\alpha-1}}.
\end{align*}
Let $(2\beta)^{\alpha-1}v=\frac{\alpha\log(\epsilon^{-1})}{n\beta},$ i.e., $\beta=\frac{1}{2}\big(\frac{2\alpha\log(\epsilon^{-1})}{nv})^{\frac{1}{\alpha}}$, we have
\begin{align*}
m-\theta_{+}\geq-\frac{2\big(\frac{2\alpha\log(\epsilon^{-1})}{n}\big)^{\frac{\alpha-1}{\alpha}}v^{\frac{1}{\alpha}}}{\alpha-\big(\frac{2\alpha\log(\epsilon^{-1})}{nv}\big)^{\frac{\alpha-1}{\alpha}}}.
\end{align*}
Similarly, we get
\begin{align*}
m-\theta_{-}\leq \frac{2\big(\frac{2\alpha\log(\epsilon^{-1})}{n}\big)^{\frac{\alpha-1}{\alpha}}v^{\frac{1}{\alpha}}}{\alpha-\big(\frac{2\alpha\log(\epsilon^{-1})}{nv}\big)^{\frac{\alpha-1}{\alpha}}}.
\end{align*}
Then, (\ref{three}) implies that the inequality
\begin{align*}
|\hat{\theta}-m| \le \frac{2\big(\frac{2\alpha\log(\epsilon^{-1})}{n}\big)^{\frac{\alpha-1}{\alpha}}v^{\frac{1}{\alpha}}}{\alpha-\big(\frac{2\alpha\log(\epsilon^{-1})}{nv}\big)^{\frac{\alpha-1}{\alpha}}}
\end{align*}
holds with probability at least $1-2\epsilon$.
\end{proof}

The empirical mean estimator is defined by
\begin{align*}
{ \bar{X}=\frac{1}{n}\sum_{i=1}^{n}X_{i},}
\end{align*}
we postpone to study deviation bounds for the empirical mean $\bar{X}$ in Section \ref{empirical} below.

In Figures \ref{figure2}-\ref{figure5}, we compare the bound on the deviations of the ${\rm M}$-estimator $\hat{\theta}$ with the deviations of the empirical mean $\bar{X}$, when the sample distribution is {a Pareto distribution with shape parameter $\frac{2+\alpha}{2}$ and scale parameter $(\frac{2+\alpha}{2-\alpha})^{-\frac{1}{\alpha}}$ (see, e.g., \cite[Chapter 23]{K17}), that is,
\begin{align*}
\mathbb{P}(X_{1}\geq x)=2^{-1}(\frac{2+\alpha}{2-\alpha})^{-\frac{2+\alpha}{2\alpha}}x^{-\frac{2+\alpha}{2}},\quad x\geq(\frac{2+\alpha}{2-\alpha})^{-\frac{1}{\alpha}},
\end{align*}
\begin{align*}
\mathbb{P}(X_{1}\leq x)=2^{-1}(\frac{2+\alpha}{2-\alpha})^{-\frac{2+\alpha}{2\alpha}}(-x)^{-\frac{2+\alpha}{2}},\quad x\leq-(\frac{2+\alpha}{2-\alpha})^{-\frac{1}{\alpha}}.
\end{align*}
By the definition, it is easy to verify that $m=\mathbb{E}X_{1}=0$ and $v=\mathbb{E}|X_{1}-m|^{\alpha}=1$.} We can get figures for the upper bound of $\hat{\theta}$, the {upper bound and lower bound} of ${\bar{X}}$. It is obvious from Figures \ref{figure2}-\ref{figure5} that
the $\hat{\theta}$ has a better performance when $\epsilon$ is small enough.
We can also see that the smaller the $\alpha$ is, the better the performance of
$\hat \theta$ will be comparing with that of ${\bar{X}}$. The parameters for Figures \ref{figure2}-\ref{figure5} are in Table \ref{Tab1}, where $0.001:0.001:0.08$ {means the range of $\epsilon$ is from $0.001$ to $0.08$ with step-size $0.001$. The ranges of $\epsilon$ in Table \ref{Tab1} satisfy \eqref{en} and the values of $n$ in Table \ref{Tab1} satisfy \eqref{assu} and \eqref{en}.}
\begin{table}[htbp]
\centering
\caption{ Parameters in Figures \ref{figure2}-\ref{figure5} }
\begin{tabular}{c|c|c|c}
\hline
&$\alpha$  & $\epsilon$ & n  \\
\hline
Figure \ref{figure2}
& 1.9 & 0.001:0.001:0.08  &   500 \\
 \hline
Figure \ref{figure3}
& 1.8 & 0.001:0.001:0.08  &   500 \\
 \hline
Figure \ref{figure4}
& 1.5 & 0.001:0.001:0.08  &   500 \\
 \hline
Figure \ref{figure5}
& 1.2 & 0.01:0.001:0.08  &  3000 \\
 \hline
\end{tabular}
\label{Tab1}
\end{table}

\begin{figure}
\centering
\includegraphics[height=8cm,width=14cm]{2.eps}
\caption{Deviations of $\hat{\theta}$ from the sample mean, compared with those of empirical mean}
\label{figure2}
\end{figure}

\begin{figure}
\centering
\includegraphics[height=8cm,width=14cm]{3.eps}
\caption{Deviations of $\hat{\theta}$ from the sample mean, compared with those of empirical mean}
\label{figure3}
\end{figure}

\begin{figure}
\centering
\includegraphics[height=8cm,width=14cm]{4.eps}
\caption{Deviations of $\hat{\theta}$ from the sample mean, compared with those of empirical mean}
\label{figure4}
\end{figure}

\begin{figure}
\centering
\includegraphics[height=8cm,width=14cm]{5.eps}
\caption{Deviations of $\hat{\theta}$ from the sample mean, compared with those of empirical mean}
\label{figure5}
\end{figure}

\section{The deviation {upper and lower} bounds of the empirical mean estimator}\label{empirical}
At the end of the previous section, we compare our ${\rm M}$-estimator $\hat \theta$ with the empirical mean $\bar X$. In this section, we will prove the upper bounds and the corresponding lower bounds on the empirical mean used in these comparisons.

\subsection{Upper bounds}

\begin{lemma}\label{empu}
Let $(X_{i})_{i=1}^{n}$ be a sequence of random variables independently drawn from some distribution $\mathbf{\Pi}$ with mean $m$ and $\alpha$-th central moment $v$. Then, denote the empirical mean ${\bar{X}=\frac{1}{n}\sum_{i=1}^{n}X_{i},}$ we have
\begin{align*}
{
\mathbb{P}\Big(|\bar{X}-m|\geq\big(\frac{v}{\epsilon n^{\alpha-1}}\big)^{\frac{1}{\alpha}}\Big)\leq2\epsilon.}
\end{align*}
\end{lemma}

\begin{proof}
Noticing that $(X_{i}-m)_{i=1}^{n}$ are i.i.d. random variables with mean zero, by \cite[Theorem 2]{V-E}, we have
\begin{align*}
\mathbb{E}\big|\sum_{i=1}^{n}[X_{i}-m]\big|^{\alpha}\leq2\sum_{i=1}^{n}\mathbb{E}|X_{i}-m|^{\alpha}=2nv,
\end{align*}
which implies
\begin{align*}
{
\mathbb{P}\Big(|\bar{X}-m|\geq\big(\frac{v}{\epsilon n^{\alpha-1}}\big)^{\alpha}\Big)\leq\frac{\mathbb{E}|\bar{X}-m|^{\alpha}}{\frac{v}{\epsilon n^{\alpha-1}}}
\leq\frac{\frac{1}{n^{\alpha}}\mathbb{E}\big|\sum_{i=1}^{n}[X_{i}-m]\big|^{\alpha}}{\frac{v}{\epsilon n^{\alpha-1}}}\leq2\epsilon,}
\end{align*}
the desired result follows.
\end{proof}

\subsection{Lower bounds}
Comparing with Lemma \ref{empu}, the following lemma gives a lower bound for the deviations of the empirical mean for some specific distributions.

\begin{lemma}\label{emp}
For any value of the $\alpha$-th central moment $v,$ any deviation $\eta>0,$ there is some distribution $\mathbf{\Pi}$ with mean zero and $\alpha$-th {central} moment $v$ such that
\begin{align}\label{lower1}
\mathbb{P}(\bar{X}\geq\eta)=\mathbb{P}(\bar{X}\leq-\eta)\geq\frac{v}{3n^{\alpha-1}\eta^{\alpha}}\big(1-\frac{v}{n^{\alpha}\eta^{\alpha}}\big)^{n-1},
\end{align}
where $\bar{X}=\frac{1}{n}\sum_{i=1}^{n}X_{i}$ with $(X_{i})_{i=1}^{n}$ independently drawn from the distribution $\mathbf{\Pi}.$ Furthermore, if
{
\begin{align}\label{en}
\epsilon<(3e)^{-1} {\text \ \ and \ \ }
n\geq2,
\end{align}
}
the inequality
\begin{align*}
|\bar{X}-m|\geq\big(\frac{v}{3n^{\alpha-1}\epsilon}\big)^{\frac{1}{\alpha}}(1-\frac{3e\epsilon}{n})^{\frac{n-1}{\alpha}}
\end{align*}
holds with probability at least $2\epsilon.$
\end{lemma}

\begin{proof}
Let us consider the random variable $X,$ which has the following distribution:
{
\begin{align*}
\mathbb{P}(X=0)=1-\frac{v}{n^{\alpha}\eta^{\alpha}}, \quad \mathbb{P}(X=n\eta)=\mathbb{P}(X=-n\eta)=\frac{v}{3n^{\alpha}\eta^{\alpha}}
\end{align*}
and
\begin{align*}
\mathbb{P}\big(X\in(x,\infty)\backslash\{n\eta\}\big)=\frac{q}{2\gamma}x^{-\gamma}, \quad x\in(p,\infty)\backslash\{n\eta\}
\end{align*}
\begin{align*}
\mathbb{P}\big(X\in(-\infty,x)\backslash\{-n\eta\}\big)=\frac{q}{2\gamma}|x|^{-\gamma}, \quad x\in(-\infty,-p)\backslash\{-n\eta\},
\end{align*}
where $\gamma\in(\alpha,2),$ $p=\big(\frac{\gamma-\alpha}{\gamma}\big)^{\frac{1}{\alpha}}n\eta$ and $q=\frac{\gamma v}{3}\big(\frac{\gamma-\alpha}{\gamma}\big)^{\frac{\gamma}{\alpha}}(n\eta)^{\gamma-\alpha}.$ It is easy to check that $\mathbb{E}X=0$ and
\begin{align*}
\mathbb{E}|X|^{\alpha}=(n\eta)^{\alpha}\frac{v}{3n^{\alpha}\eta^{\alpha}}+{ (n\eta)}^{\alpha}\frac{v}{3n^{\alpha}\eta^{\alpha}}+\frac{q}{\gamma-\alpha}p^{\alpha-\gamma}=\frac{v}{3}+\frac{v}{3}+\frac{v}{3}=v.
\end{align*}
}

Let $(X_{i})_{i=1}^{n}$ be i.i.d., which have the same distribution as $X.$ Then,
\begin{align*}
\mathbb{P}(\bar{X}\geq\eta)
=\mathbb{P}(\bar{X}\leq-\eta)
\geq\mathbb{P}(\bar{X}=\eta)
\geq \frac{v}{3n^{\alpha-1}\eta^{\alpha}}\big(1-\frac{v}{n^{\alpha}\eta^{\alpha}}\big)^{n-1},
\end{align*}
so (\ref{lower1}) is proved.

Take $\eta=\big(\frac{v}{3n^{\alpha-1}\epsilon}\big)^{\frac{1}{\alpha}}(1-\frac{3e\epsilon}{n})^{\frac{n-1}{\alpha}},$ we have
\begin{align*}
\frac{v}{3n^{\alpha-1}\eta^{\alpha}}\big(1-\frac{v}{n^{\alpha}\eta^{\alpha}}\big)^{n-1}=\epsilon(1-\frac{3e\epsilon}{n})^{-(n-1)}\Big(1-\frac{3\epsilon}{n(1-\frac{3e\epsilon}{n})^{n-1}}\Big)^{n-1}.
\end{align*}
If $\epsilon<(3e)^{-1},$ then $(1-\frac{3e\epsilon}{x})^{x-1}\geq(1-\frac{1}{x})^{x-1}.$ For any $x\geq1,$ we denote $f(x)=(1-\frac{1}{x})^{x-1},$ then
\begin{align*}
f'(x)=&(1-\frac{1}{x})^{x-1}\Big(\log(1-\frac{1}{x})+\frac{(x-1)}{x^{2}(1-\frac{1}{x})}\Big)\\
=&(1-\frac{1}{x})^{x-1}\Big(\log(1-\frac{1}{x})+\frac{1}{x}\Big).
\end{align*}
Noting that $(1-\frac{1}{x})^{x-1}>0,$ let $g(x)=\log(1-\frac{1}{x})+\frac{1}{x}$ for $x\geq1,$ then we have
\begin{align*}
g'(x)=\frac{1}{x^{2}(1-\frac{1}{x})}-\frac{1}{x^{2}}=\frac{1}{x^{2}(x-1)}>0
\end{align*}
and
\begin{align*}
\lim_{x\rightarrow\infty}g(x)=\lim_{x\rightarrow\infty}\big[\log(1-\frac{1}{x})+\frac{1}{x}\big]=0,
\end{align*}
which imply $g(x)\leq0,$ so we have $f'(x)\leq0$ for $x\geq1.$ What's more, we have
\begin{align*}
\lim_{x\rightarrow\infty}f(x)=\lim_{x\rightarrow\infty}(1-\frac{1}{x})^{x-1}=e^{-1},
\end{align*}
which implies $(1-\frac{3e\epsilon}{n})^{n-1}\geq e^{-1}.$ Therefore, we have
\begin{align*}
\frac{v}{3n^{\alpha-1}\eta^{\alpha}}\big(1-\frac{v}{n^{\alpha}\eta^{\alpha}}\big)^{n-1}\geq\epsilon(1-\frac{3e\epsilon}{n})^{-(n-1)}\Big(1-\frac{3e\epsilon}{n}\Big)^{n-1}=\epsilon.
\end{align*}
The proof is complete.
\end{proof}

\section{$\ell_{1}$-regression for heavy-tailed samples having finite $\alpha$-th moment with $\alpha \in (1,2)$}\label{l1regression}

 The linear regression considered in \cite{Z-Z} aims to find the unknown minimizer $\theta^{*}$ of the following minimization problem:
\begin{align}\label{min}
\min_{\mathbf{\theta}\in\mathbf{\Theta}} R_{\ell_{1}}(\theta) \ \ \ \ {\rm with} \ \ \ R_{\ell_{1}}(\theta)=\mathbb{E}_{(\mathbf{x},y)\sim{\bf\Pi}}\big[|\mathbf{x}^{T}\mathbf{\theta}-y|\big],
\end{align}
where ${\bf\Pi}$ is the population's distribution, and {$\mathbf{\Theta} \subseteq \mathbb{R}^d$} is the set in which $\theta^{*}$ is located. In practice, ${\bf\Pi}$ is not known, one usually draws a data set $\mathcal{T}=(\mathbf{x}_{1},y_{1}),\cdots,(\mathbf{x}_{n},y_{n})$ from $\mathbf{\Pi}$ and consider the following empirical optimization problem:
\begin{align*}
\min_{\mathbf{\theta}\in\mathbf{\Theta}}\widehat{R}_{\ell_{1}}(\mathbf{\theta}) \ \ \ {\rm with} \ \ \ \widehat{R}_{\ell_{1}}(\mathbf{\theta})=\frac{1}{n}\sum_{i=1}^{n}|\mathbf{x}_{i}^{T}\mathbf{\theta}-y_{i}|.
\end{align*}

Inspired by Catoni's work, Zhang et al. \cite{Z-Z} considered the case that ${\bf\Pi}$ is heavy tailed with finite variance and proposed a new minimization problem
\begin{align}\label{mintrun}
\min_{\mathbf{\theta}\in\mathbf{\Theta}} \widehat R_{\varphi, \ell_{1}}(\theta) \ \ \ {\rm with} \ \ \ \widehat R_{\varphi, \ell_{1}}(\theta)=\frac{1}{n\beta}\sum_{i=1}^{n}\varphi(\beta|y_{i}-\mathbf{x}_{i}^{T}\theta|),
\end{align}
where $\varphi$ is the same as that in \cite{C12} and $\beta>0$ is to be determined later.

Thanks to the analysis of Section \ref{deviation}, we extend the results in \cite{Z-Z} to the case in which samples can have finite $\alpha$-th moment with $\alpha \in (1,2)$, the approach is by replacing the original $\varphi$ with \eqref{trunc}.

\subsection{Main results of this section}

Before stating the main results, we first give some definitions and assumptions.

\begin{definition} Let $(\mathbf{\Theta},d)$ be a metric space, and $\mathbf{K}$ be a subset of $\mathbf{\Theta}$. Then a subset $\mathcal{N}\subseteq\mathbf{K}$ is called an {$\varepsilon$-net} of $\mathbf{K}$ if for every $\theta\in\mathbf{K}$, we can find a $\tilde{\theta}\in\mathcal{N}$ such that $d(\theta,\tilde{\theta})\leq\varepsilon$. The covering number is the minimal cardinality of the $\varepsilon$-net of $\mathbf{\Theta}$ and denoted by $N(\bf{\Theta},\varepsilon)$.
\end{definition}

We shall assume:

{\bf {Assumption A1}} (i) The domain $\mathbf{\Theta}$ is totally bounded, that is, for any $\varepsilon>0$, there exists a finite $\varepsilon$-net of $\mathbf{\Theta}.$

(ii) The expectation of the $\alpha$-th moment of $\mathbf{x}$ is bounded, that is,
\begin{align*}
\mathbb{E}_{(\mathbf{x,y})\sim\mathbf{\Pi}}[|\mathbf{x}|^{\alpha}]<\infty.
\end{align*}

(iii) The $\ell_{\alpha}$-risk of all $\theta\in\mathbf{\Theta}$ is bounded, that is,
\begin{align*}
\sup_{\theta\in\mathbf{\Theta}}R_{\ell_{\alpha}}(\theta)=\sup_{\theta\in\mathbf{\Theta}}\mathbb{E}_{(\mathbf{x},y)\sim\mathbf{\Pi}}[|y-\mathbf{x}^{T}\theta|^{\alpha}]<\infty.
\end{align*}

Then, we can state the second theorem, which will be proved in subsection \ref{pre}.

\begin{theorem}\label{main2}
Let $\theta^{*}$ and $\hat{\theta}$ be the minimizers of (\ref{min}) and (\ref{mintrun}), respectively. Under {\bf Assumption A1}, for any $\delta\in(0,\frac{1}{2}),$ with probability at least $1-2\delta$, we have
\begin{align*}
&R_{\ell_{1}}(\hat{\theta})-R_{\ell_{1}}(\theta^{*})\\
\leq&2\varepsilon\mathbb{E}|\mathbf{x}_{1}| +\big(\frac{2^{\alpha-1}\varepsilon^{\alpha}}{\alpha} \mathbb{E}|\mathbf{x}_{1}|^{\alpha} +\frac{2^{\alpha-1}+1}{\alpha} \sup_{\theta\in\bf{\Theta}}R_{\ell_{\alpha}}(\theta) \big)\beta^{\alpha-1}+\frac{1}{n\beta} \log\frac{N(\bf{\Theta},\varepsilon)}
{\delta^{2}}
\end{align*}
for any $\varepsilon>0.$ Furthermore, let
\begin{align*}
\beta=\big(\frac{1}{n}\log\frac{N(\mathbf{\Theta},\varepsilon)}{\delta^{2}}\big)^{\frac{1}{\alpha}},
\end{align*}
we have
\begin{align}\label{end}
&R_{\ell_{1}}(\hat{\theta})-R_{\ell_{1}}(\theta^{*})\nonumber\\
\leq&2\varepsilon\mathbb{E}|\mathbf{x}_{1}| +\big(\frac{2^{\alpha-1}\varepsilon^{\alpha}}{\alpha} \mathbb{E}|\mathbf{x}_{1}|^{\alpha}+\frac{2^{\alpha-1}+1}{\alpha}\sup_{\theta\in\bf{\Theta}}R_{\ell_{\alpha}}(\theta)+1\big)
\big(\frac{1}{n}\log\frac{N({\bf \Theta},\varepsilon)}{\delta^{2}}\big)^{\frac{\alpha-1}{\alpha}}.
\end{align}
\end{theorem}

{ In order to compute the covering number, we further assume:}

{\bf Assumption A2} The domain ${\bf{\Theta}}\subseteq\mathbb{R}^{d}$, and its radius is bounded by a constant $r$, that is,
\begin{align*}
|\theta|\leq r ,\quad \forall\theta\in{\bf{\Theta}}.
\end{align*}

Then, we have the following corollary, which will be proved in subsection \ref{pre}.

\begin{corollary}\label{explicit}
Keep the same notations and assumptions in Theorem \ref{main2}. In addition, we suppose the {\bf Assumption A2} holds. Then, for any $\delta\in(0,\frac{1}{2}),$ with probability at least $1-2\delta$, we have
\begin{align*}
&R_{\ell_{1}}(\hat{\theta})-R_{\ell_{1}}(\theta^{*})\\
\leq&\frac{2}{n}\mathbb{E}|\mathbf{x}_{1}|+\big(\frac{2^{\alpha-1}}{\alpha n^{\alpha}} \mathbb{E}|\mathbf{x}_{1}|^{\alpha}+\frac{2^{\alpha-1}+1}{\alpha}\sup_{\theta\in\bf{\Theta}}R_{\ell_{\alpha}}(\theta)+1\big)
\Big(\frac{1}{n}\big(d\log(6nr)+\log\frac{1}{\delta^{2}}\big)\Big)^{\frac{\alpha-1}{\alpha}}\\
=&O\Big(\big(\frac{d\log n}{n}\big)^{\frac{\alpha-1}{\alpha}}\Big).
\end{align*}
\end{corollary}

\subsection{Proof of Theorem \ref{main2} and Corollary \ref{explicit}}\label{pre}

Before proving the Theorem \ref{main2}, we first give the following auxiliary lemmas.

\begin{lemma}\label{first}
Keep the same notations and assumptions as in Theorem \ref{main2}. Then, the following inequality
\begin{align*}
\widehat{R}_{\varphi,\ell_{1}}(\theta^{*})-R_{\ell_{1}}(\theta^{*})\leq\frac{\beta^{\alpha-1}}{\alpha}R_{\ell_{\alpha}}(\theta^{*})+\frac{1}{n \beta}\log\frac{1}{\delta}
\end{align*}
holds with probability at least $1-\delta$.
\end{lemma}

\begin{proof}
Noticing that $(\mathbf{x}_{i},y_{i}),$ $i=1,\cdots,n,$ are i.i.d., by (\ref{trunc}), we have
\begin{align*}
\mathbb{E}\big[\exp\big(n\beta \widehat{R}_{\varphi,\ell_{1}}(\theta^{*})\big)\big]=&\mathbb{E}\big[\exp\big(\sum_{i=1}^{n}\varphi(\beta|y_{i}-{\bf x}_{i}^{T}\theta^{*}|)\big)\big]\\
=&\Big[\mathbb{E}\big[\exp\big(\varphi(\beta|y_{1}-{\bf x}_{1}^{T}\theta^{*}|)\big)\big]\Big]^{n}\\
\leq&\Big[\mathbb{E}\big[1+\beta|y_{1}-{\bf x}_{1}^{T}\theta^{*}|+\frac{\beta^{\alpha}|y_{1}-{\bf x}_{1}^{T}\theta^{*}|^{\alpha}}{\alpha}\big]\Big]^{n},
\end{align*}
then, by the inequality $1+x\leq e^{x}$ for all $x\in \mathbb{R}$, we have
\begin{align*}
\mathbb{E}\big[\exp\big(n\beta \widehat{R}_{\varphi,\ell_{1}}(\theta^{*})\big)\big]
\leq&\big[1+\beta R_{\ell_{1}}(\theta^{*})+\frac{\beta^{\alpha}}{\alpha}R_{\ell_{\alpha}}(\theta^{*})\big] ^{n}\\
\leq& \exp\big(n\beta R_{\ell_{1}}(\theta^{*})+\frac{n\beta^{\alpha}}{\alpha}R_{\ell_{\alpha}}(\theta^{*})\big).
\end{align*}
Therefore, by Markov inequality, we have
\begin{align*}
&\mathbb{P}\Big(n\beta \widehat{R}_{\varphi,\ell_{1}}(\theta^{*})\geq n\beta R_{\ell_{1}}(\hat{\theta})+\frac{n\beta^{\alpha}}{\alpha}R_{\ell_{\alpha}}(\theta^{*})+\log\frac{1}{\delta}\Big)\\
=&\mathbb{P}\Big(\exp\big(n\beta \widehat{R}_{\varphi,\ell_{1}}(\theta^{*})\big)\geq \exp\big(n\beta R_{\ell_{1}}(\theta^{*})+\frac{n\beta^{\alpha}}{\alpha}R_{\ell_{\alpha}}(\theta^{*})+\log\frac{1}{\delta}\big)\Big)\\
\leq&\frac{\mathbb{E}\big[\exp\big(n\beta \widehat{R}_{\varphi,\ell_{1}}(\theta^{*})\big)\big]}{\exp\big(n\beta R_{\ell_{1}}(\theta^{*})+\frac{n\beta^{\alpha}}{\alpha}R_{\ell_{\alpha}}(\theta^{*})+\log\frac{1}{\delta}\big)}\leq\delta.
\end{align*}
The proof is complete.
\end{proof}

\begin{lemma}\label{pre2}
For any $\varepsilon>0,$ {let $\mathcal{N}({\bf\Theta},\varepsilon)$ be an $\varepsilon$-net of ${\bf\Theta}$ with cardinality $N({\bf\Theta},\varepsilon).$} Then, with probability at least $1-\delta$, the following inequality
\begin{align*}
&-\frac{1}{n \beta}\sum_{i=1}^{n}\varphi\big(\beta|y_{i}-\mathbf{x}_{i}^{T}\tilde{\theta}|-\beta\varepsilon|\mathbf{x}_{i}|\big)\\
&\leq-R_{\ell_{1}}(\tilde{\theta})+\varepsilon\mathbb{E}|\mathbf{x}_{1}|+\frac{(2\beta)^{\alpha-1}}{\alpha}\sup_{\theta\in{\bf\Theta}}R_{\ell_{\alpha}}(\theta)
+\frac{(2\beta)^{\alpha-1}\varepsilon^{\alpha}}{\alpha}\mathbb{E}|\mathbf{x}_{1}|^{\alpha}+\frac{1}{n\beta}\log\frac{N({\bf\Theta},\varepsilon)}{\delta}
\end{align*}
holds for all $\tilde{\theta}\in\mathcal{N}({\bf\Theta},\varepsilon).$
\end{lemma}

\begin{proof}
For a fixed $\tilde{\theta}\in\mathcal{N}({\bf\Theta},\varepsilon),$ noticing that $(\mathbf{x}_{i},y_{i}),$ $i=1,\cdots,n,$ are i.i.d., by (\ref{trunc}), we have
\begin{align*}
&\mathbb{E}\big[\exp\big(-\sum_{i=1}^{n} \varphi(\beta|y_{i}-\mathbf{x}_{i}^{T} \tilde{\theta}|-\beta\varepsilon|\mathbf{x}_{i}|)\big)\big]\\
=&\Big[\mathbb{E}\big[\exp\big(-\varphi (\beta|y_{1}-\mathbf{x}_{1}^{T} \tilde{\theta}|-\beta\varepsilon|\mathbf{x}_{1}|)\big)\big]\Big]^{n}\\
\leq&\Big[\mathbb{E}\big[1-\beta|y_{1}- \mathbf{x}_{1}^{T}\tilde{\theta}| +\beta\varepsilon|\mathbf{x}_{1}|+\frac{\beta^{\alpha} (|y_{1}-\mathbf{x}_{1}^{T} \tilde{\theta}|-\varepsilon|\mathbf{x}_{1}|)^{\alpha}}{\alpha} \big]\Big]^{n}\\
=&\Big[1-\beta R_{\ell_{1}}(\tilde{\theta})+\beta\varepsilon \mathbb{E}|\mathbf{x}_{1}| +\frac{\beta^{\alpha}}{\alpha} \mathbb{E}\big[\big||y_{1}-\mathbf{x}_{1}^{T} \tilde{\theta}|-\varepsilon|\mathbf{x}_{1}|\big |^{\alpha}\big]\Big]^{n},
\end{align*}
then, by (\ref{CR}) and the inequality $1+x\leq e^{x}$ for all $x\in \mathbb{R}$, we have
\begin{align*}
&\mathbb{E}\big[\exp\big(-\sum_{i=1}^{n} \varphi(\beta|y_{i}-\mathbf{x}_{i}^{T} \tilde{\theta}|-\beta\varepsilon|\mathbf{x}_{i}|)\big)\big]\\
\leq&\Big[1-\beta R_{\ell_{1}}(\tilde{\theta})+\beta\varepsilon\mathbb{E} |\mathbf{x}_{1}|+\frac{\beta^{\alpha}2^{\alpha-1}}{\alpha}R_{\ell_{\alpha}}(\tilde{\theta})
+\frac{\beta^{\alpha}\varepsilon^{\alpha}2^{\alpha-1}}{\alpha}\mathbb{E}|\mathbf{x}_{1}|^{\alpha}]\Big]^{n}\\
\leq&\exp\Big[n\big(-\beta R_{\ell_{1}}(\tilde{\theta})+\beta\varepsilon\mathbb{E}|\mathbf{x}_{1}|+\frac{\beta^{\alpha}2^{\alpha-1}}{\alpha}R_{\ell_{\alpha}}(\tilde{\theta})
+\frac{\beta^{\alpha}\varepsilon^{\alpha}2^{\alpha-1}}{\alpha}\mathbb{E}|\mathbf{x}_{1}|^{\alpha}]\big)\Big].
\end{align*}
Therefore, by Markov inequality, we have
\begin{align*}
&\mathbb{P}\Big(-\sum_{i=1}^{n} \varphi(\beta|y_{i}-\mathbf{x}_{i}^{T} \tilde{\theta}|-\beta\varepsilon|\mathbf{x}_{i}|)\\
&\qquad\geq n\big(-\beta R_{\ell_{1}}(\tilde{\theta})+\beta\varepsilon\mathbb{E} |\mathbf{x}_{1}|+\frac{\beta^{\alpha}2^{\alpha-1}} {\alpha}R_{\ell_{\alpha}}(\tilde{\theta})
+\frac{\beta^{\alpha}\varepsilon^{\alpha}2^{\alpha-1}}{\alpha} \mathbb{E}|\mathbf{x}_{1}|^{\alpha}]\big) +\log\frac{1}{\delta'}\Big)\\
\leq&\frac{\mathbb{E}\big[\exp\big(-\sum_{i=1}^{n} \varphi(\beta|y_{i}-\mathbf{x}_{i}^{T}\tilde{\theta}| -\beta\varepsilon|\mathbf{x}_{i}|)\big)\big]} {\exp\Big[n\big(-\beta R_{\ell_{1}}(\tilde{\theta})+\beta\varepsilon\mathbb{E} |\mathbf{x}_{1}|+\frac{\beta^{\alpha}2^{\alpha-1}} {\alpha}R_{\ell_{\alpha}}(\tilde{\theta})
+\frac{\beta^{\alpha}\varepsilon^{\alpha}2^{\alpha-1}}{\alpha} \mathbb{E}|\mathbf{x}_{1}|^{\alpha}]\big) +\log\frac{1}{\delta'}\Big]}\leq\delta',
\end{align*}
where $\delta'\in(0,1)$, which will be chosen later. Hence, for a fixed $\tilde{\theta}\in\mathcal{N}({\bf\Theta},\varepsilon),$ with probability at most $\delta',$ we have
\begin{align*}
&-\frac{1}{n\beta}\sum_{i=1}^{n}\varphi(\beta|y_{i}-\mathbf{x}_{i}^{T}\tilde{\theta}|-\beta\varepsilon|\mathbf{x}_{i}|)\\
\geq&-R_{\ell_{1}}(\tilde{\theta})+\varepsilon\mathbb{E}|\mathbf{x}_{1}|+\frac{(2\beta)^{\alpha-1}}{\alpha}R_{\ell_{\alpha}}(\tilde{\theta})
+\frac{(2\beta)^{\alpha-1}\varepsilon^{\alpha}}{\alpha}\mathbb{E}|\mathbf{x}_{1}|^{\alpha}]+\frac{1}{n\beta}\log\frac{1}{\delta'}.
\end{align*}
Therefore, since the set $\mathcal{N}({\bf\Theta},\varepsilon)$ has $N({\bf\Theta},\varepsilon)$ elements, we have
\begin{align*}
&\mathbb{P}\Big(\bigcap_{\tilde{\theta}\in \mathcal{N}({\bf\Theta},\varepsilon)}\big\{-\frac{1}{n\beta}\sum_{i=1}^{n} \varphi(\beta|y_{i}-\mathbf{x}_{i}^{T}\tilde{\theta}| -\beta\varepsilon|\mathbf{x}_{i}|)\leq\\
&\qquad\qquad\quad-R_{\ell_{1}}(\tilde{\theta})+\varepsilon\mathbb{E} |\mathbf{x}_{1}|+\frac{(2\beta)^{\alpha-1}} {\alpha}R_{\ell_{\alpha}}(\tilde{\theta})
+\frac{(2\beta)^{\alpha-1}\varepsilon^{\alpha}}{\alpha} \mathbb{E}|\mathbf{x}_{1}|^{\alpha}]\big)+\frac{1}{n\beta}\log\frac{1}{\delta'}\big\}\Big)\\
\geq&1-N({\bf\Theta},\varepsilon)\delta'.
\end{align*}
Finally, taking $\delta'=\frac{\delta}{N({\bf\Theta},\varepsilon)},$ with probability at least $1-\delta,$ the following inequality
\begin{align*}
&-\frac{1}{n\beta}\sum_{i=1}^{n} \varphi(\beta|y_{i}-\mathbf{x}_{i}^{T}\tilde{\theta}| -\beta\varepsilon|\mathbf{x}_{i}|)\\
\leq&-R_{\ell_{1}}(\tilde{\theta}) +\varepsilon\mathbb{E}|\mathbf{x}_{1}| +\frac{(2\beta)^{\alpha-1}}{\alpha}R_{\ell_{\alpha}} (\tilde{\theta})
+\frac{(2\beta)^{\alpha-1}\varepsilon^{\alpha}}{\alpha} \mathbb{E}|\mathbf{x}_{1}|^{\alpha}] +\frac{1}{n\beta}\log\frac{N({\bf\Theta},\varepsilon)} {\delta}\\
\leq&-R_{\ell_{1}}(\tilde{\theta})+\varepsilon\mathbb{E} |\mathbf{x}_{1}|+\frac{(2\beta)^{\alpha-1}}{\alpha} \sup_{\theta\in{\bf\Theta}}R_{\ell_{\alpha}}(\theta)
+\frac{(2\beta)^{\alpha-1}\varepsilon^{\alpha}}{\alpha} \mathbb{E}|\mathbf{x}_{1}|^{\alpha} +\frac{1}{n\beta}\log\frac{N({\bf\Theta},\varepsilon)}{\delta}
\end{align*}
holds for all $\tilde{\theta}\in\mathcal{N}({\bf\Theta},\varepsilon).$ The proof is complete.
\end{proof}

Based on Lemma \ref{pre2}, we have the following lemma.

\begin{lemma}\label{second}
Keep the same notations and assumptions as in Theorem \ref{main2}. Then, for any $\varepsilon>0,$ the following inequality
\begin{align*}
&R_{\ell_{1}}(\hat{\theta})-\widehat{R}_{\varphi,\ell_{1}}(\hat{\theta})\\
\leq&2\varepsilon\mathbb{E}|\mathbf{x}_{1}|+\frac{(2\beta)^{\alpha-1}}{\alpha}\sup _{\theta\in{\bf \Theta}}R_{\ell_{\alpha}}(\theta)+\frac{(2\beta)^{\alpha-1}\varepsilon^{\alpha}}{\alpha} \mathbb{E}|\mathbf{x}_{1}|^{\alpha}+\frac{1}{n\beta} \log \frac{N({\bf\Theta},\varepsilon)}{\delta}
\end{align*}
holds with probability at least $1-\delta.$
\end{lemma}

\begin{proof}
Since $\hat{\theta}\in\mathbf{\Theta},$ there exists a $\tilde{\theta}\in\mathcal{N}({\bf\Theta},\varepsilon)$ such that
\begin{align*}
|\hat{\theta}-\tilde{\theta}|\leq\varepsilon,
\end{align*}
which implies
\begin{align}\label{l1}
|y_{i}-\mathbf{x}_{i}^{T}\hat{\theta}|\geq|y_{i}-\mathbf{x}_{i}^{T}\tilde{\theta}|-|\mathbf{x}_{i}^{T}(\tilde{\theta}-\hat{\theta})|\geq|y_{i}-\mathbf{x}_{i}^{T} \tilde{\theta}|-\varepsilon|\mathbf{x}_{i}|.
\end{align}
Then, since $\varphi(\cdot)$ is non-decreasing, we have
\begin{align*}
\widehat{R}_{\varphi,\ell_{1}}(\hat{\theta})=\frac{1}{n \beta}\sum_{i=1}^{n}\varphi\big(\beta|y_{i}-\mathbf{x}_{i}^{T}\hat{\theta}|\big)\ge\frac{1}{n\beta}\sum_{i=1}^{n} \varphi\big(\beta|y_{i}-\mathbf{x}_{i}^{T}\tilde{\theta}|-\beta\varepsilon|\mathbf{x}_{i}|\big),
\end{align*}
by Lemma \ref{pre2}, with probability at least $1-\delta$, we have
\begin{align*}
&\widehat{R}_{\varphi,\ell_{1}}(\hat{\theta})\\
	\ge&R_{\ell_{1}}(\tilde{\theta})-\big[\varepsilon\mathbb{E}|\mathbf{x}_{1}|+\frac{(2\beta)^{\alpha-1}}{\alpha} \sup _{\theta \in{\bf\Theta}} R_{\ell_{\alpha}}(\theta)+\frac{(2\beta)^{\alpha-1}\varepsilon^{\alpha}}{\alpha} \mathbb{E}|\mathbf{x}_{1}|^{\alpha}+\frac{1}{n\beta} \log \frac{N({\bf\Theta},\varepsilon)}{\delta}\big].
\end{align*}
What's more, by (\ref{l1}) and triangle inequality, we have
\begin{align*}
R_{\ell_{1}}(\hat{\theta})-R_{\ell_{1}}(\tilde{\theta})=&\mathbb{E}\big[|\mathbf{x}_{1}^{T}\hat{\theta}-y_{1}|-|\mathbf{x}_{1}^{T}\tilde{\theta}-y_{1}|\big]
\leq\mathbb{E}\big[|\mathbf{x}_{1}^{T}\hat{\theta}-\mathbf{x}_{1}^{T}\tilde{\theta}|\big]\leq\varepsilon\mathbb{E}|\mathbf{x}_{1}|,
\end{align*}
which further implies that with probability at least $1-\delta$, the inequality
\begin{align*}
&\widehat{R}_{\varphi,\ell_{1}}(\hat{\theta})\\
	\ge&R_{\ell_{1}}(\hat{\theta})-\big[2\varepsilon\mathbb{E}|\mathbf{x}_{1}|+\frac{(2\beta)^{\alpha-1}}{\alpha} \sup _{\theta \in{\bf\Theta}} R_{\ell_{\alpha}}(\theta)+\frac{(2\beta)^{\alpha-1}\varepsilon^{\alpha}}{\alpha} \mathbb{E}|\mathbf{x}_{1}|^{\alpha}+\frac{1}{n\beta} \log \frac{N({\bf\Theta},\varepsilon)}{\delta}\big]
\end{align*}
{holds.} The proof is complete.
\end{proof}

Now, we can give the proof of Theorem \ref{main2}.

{\bf Proof of Theorem \ref{main2}.}
Recall
\begin{align*}
\widehat{R}_{\varphi,\ell_{1}}(\theta)=\frac{1}{n\beta}\sum_{i=1}^{n}\varphi\big(\beta|y_{i}-\mathbf{x}_{i}^{T}\theta|\big),
\end{align*}
since $\hat{\theta}$ is the minimizer of (\ref{mintrun}), we have
\begin{align*}
\widehat{R}_{\varphi,\ell_{1}}(\hat{\theta})-\widehat{R}_{\varphi,\ell_{1}}(\theta^{*})\leq0,
\end{align*}
which implies
\begin{align*}
&R_{\ell_{1}}(\hat{\theta})-R_{\ell_{1}}(\theta^{*})\\
=&\big(R_{\ell_{1}}(\hat{\theta})-\widehat{R}_{\varphi,\ell_{1}}(\hat{\theta})\big)
+\big(\widehat{R}_{\varphi,\ell_{1}}(\hat{\theta})-\widehat{R}_{\varphi,\ell_{1}}(\theta^{*})\big)+\big(\widehat{R}_{\varphi,\ell_{1}}(\theta^{*})-R_{\ell_{1}}(\theta^{*})\big)\\
\leq&\big(R_{\ell_{1}}(\hat{\theta})-\widehat{R}_{\varphi,\ell_{1}}(\hat{\theta})\big)+\big(\widehat{R}_{\varphi,\ell_{1}}(\theta^{*})-R_{\ell_{1}}(\theta^{*})\big).
\end{align*}
By Lemma \ref{second} and Lemma \ref{first}, we immediately obtain the desired result.
\qed

Now we are at the position to give the proof of Corollary \ref{explicit}.

{\bf Proof of Corollary \ref{explicit}.}  For any $\varepsilon\in(0,1],$ by \cite[Corollary 4.2.13]{Vershynin} we have
\begin{align*}
N(B_{1},\varepsilon)\leq\big(1+\frac{2}{\varepsilon}\big)^{d}\leq(\frac{3}{\varepsilon})^{d},
\end{align*}
{where $B_1=\{x\in \mathbb{R}^d: |x|\leq 1\}$. } Since ${\bf\Theta}\subseteq B_{r}$, we have
\begin{align}\label{number}
\log N({\bf\Theta},\varepsilon)\leq\log N(B_{r},\frac{\varepsilon}{2})\leq d\log\frac{6r}{\varepsilon}.
\end{align}
Therefore, by (\ref{end}) with $\varepsilon=\frac{1}{n},$ we have
\begin{align*}
&R_{\ell_{1}}(\hat{\theta})-R_{\ell_{1}}(\theta^{*})\\
\leq&2\varepsilon\mathbb{E}|\mathbf{x}_{1}|+\big(\frac{2^{\alpha-1}\varepsilon^{\alpha}}{\alpha} \mathbb{E}|\mathbf{x}_{1}|^{\alpha}+\frac{2^{\alpha-1}+1}{\alpha}\sup_{\theta\in\bf{\Theta}}R_{\ell_{\alpha}}(\theta)+1\big)
\big(\frac{1}{n}(d\log\frac{6r}{\varepsilon}+\log\frac{1}{\delta^{2}})\big)^{\frac{\alpha-1}{\alpha}}\\
=&\frac{2}{n}\mathbb{E}|\mathbf{x}_{1}|+\big(\frac{2^{\alpha-1}}{\alpha n^{\alpha}} \mathbb{E}|\mathbf{x}_{1}|^{\alpha}+\frac{2^{\alpha-1}+1}{\alpha}\sup_{\theta\in\bf{\Theta}}R_{\ell_{\alpha}}(\theta)+1\big)
\Big(\frac{1}{n}\big(d\log(6nr)+\log\frac{1}{\delta^{2}}\big)\Big)^{\frac{\alpha-1}{\alpha}}.
\end{align*}
The proof is complete.
\qed

{\bf Acknowledgement.} {LX is supported in part by Macao S.A.R grant FDCT  0090/2019/A2 and University of Macau grant  MYRG2018-00133-FST.}

\bibliographystyle{amsplain}


\section{Introduction}

Exploring generic properties of a class of objects such as sets and/or mappings, $\dots$ is a fundamental problem in Theory of Singularities.  In the paper~\cite{Mather1973} (see also \cite{Ichiki2018}), considering the class of {\it projections}, i.e., the restriction of a linear surjective mapping from a vector space $V$ into a vector space $Y$ to a submanifold $X$ of $V,$  John~N.~Mather asked what properties of mappings are true for a generic projection and he gave answers to several special cases of this question. Motivated by this work and various problems in analysis and optimization \cite{Kim2019,Kim2020}, we consider the question if preserving closedness is a generic property of continuous semi-algebraic mappings. Namely, we study when the image of a closed semi-algebraic set under a continuous semi-algebraic mapping is closed and if the closedness is stable under small linear perturbations. The closedness of such images is of significance in analysis, since it allows one to keep lower semi-continuity of functions and to assure the existence of solutions to various extremum problems (see, for example, \cite{Auslender2003,Pataki2001}).

It is well-known that the closedness of the image of a closed convex set under a linear mapping is not necessarily preserved under small perturbations of the linear mapping (see, for example, \cite[Examples~2.1~and~2.2]{Borwein2009}). On the other hand, it was shown recently in
\cite{Dinh2020-1} (see also \cite{Borwein2009, Borwein2010}) that for a given closed convex set $X$ in $\mathbb{R}^n,$ the set
$$L(\mathbb{R}^n, \mathbb{R}^m) \ \setminus \ \Int(\{F\in L(\mathbb{R}^n, \mathbb{R}^m) \ : \ F(X) \text{ is closed}\})$$
is $\sigma$-porous in $L(\mathbb{R}^n, \mathbb{R}^m)$-the space of all linear mappings from $\mathbb{R}^n$ to $\mathbb{R}^m,$ i.e. small with regard to both measure and category.

The aim of this paper is to prove a similar result by considering a class of sets not necessarily being convex, which is the class of semi-algebraic sets. Precisely, with the definitions given in the next section, the main result of this paper is as follows.

\begin{MainTheorem}
Let $X \subset \mathbb{R}^n$ be a closed semi-algebraic set and let $G \colon X \to \mathbb{R}^m$ be a continuous semi-algebraic mapping. Then the set
$$\{F\in L(\mathbb{R}^n, \mathbb{R}^m) \ : \ (F + G)(X) \text{ is closed}\}$$
is semi-algebraic and contains an open dense semi-algebraic subset of $L(\mathbb{R}^n, \mathbb{R}^m).$
\end{MainTheorem}

Note that in the setting of Semi-Algebraic Geometry, a semi-algebraic subset of $\mathbb{R}^N$ is open dense if and only if  its complement is $\sigma$-porous.  Moreover, although the results presented here still hold for sets/mappings definable in some o-minimal structure (see \cite{Dries1996, Dries1998} for more on the subject), we prefer to work with semi-algebraic sets/mappings for simplicity.  We also emphasize that the technique used in~\cite{Dinh2020-1} for the convex case can not be applied to prove Main Theorem.

In the case where $X$ is a smooth irreducible affine variety in $\mathbb C^n$ of dimension~$\leqslant m$ and $G\colon X\to \mathbb C^m$ is a polynomial mapping, a similar result can be found in~\cite[Theorem~8.2]{Farnik2020}. The proof of this result, which only deals  with finite mappings, exploits the fact that a projection of an affine variety of dimension not greater than $m$ on $\mathbb C^m$ is generically proper (see \cite[Theorem~2.1 and Corollary~2.2]{Farnik2020}). On the other hand, our main result treats continuous semi-algebraic mappings on closed semi-algebraic sets with no constraint on the dimension; in addition, the proof given here is different from that given in~\cite{Farnik2020} .

The rest of the paper is organized as follows. In Section~\ref{SectionPreliminary}, we present some preliminaries of Semi-Algebraic Geometry which will be used later.
The notion and some basic properties of of tangent cone at infinity will be provided in Section~\ref{Section3}.
Finally, the proof of Main Theorem will be completed in Section~\ref{Section5}.

\section{Preliminaries} \label{SectionPreliminary}

\subsection{Notation}
Let $\mathbb{R}^n$ denote the Euclidean space of dimension $n.$ The corresponding inner product (resp., norm) in $\mathbb{R}^n$  is denoted by $\langle x, y \rangle$ for any $x, y \in \mathbb{R}^n$ (resp., $\| x \| := \sqrt{\langle x, x \rangle}$ for any $x \in \mathbb{R}^n$).  We will denote by $\mathbb B^n_r$ and $\mathbb S^{n-1}_r(x),$ respectively, the open ball and the sphere of radius $r$ centered at the origin in $\mathbb R^n.$ For simplicity, we write $\mathbb B^n$ and $\mathbb S^{n-1}$ if $r = 1.$

The closure and the interior of $X\subset\mathbb R^n$ are denoted respectively by $\overline X$ and $\Int (X).$

Let $L(\mathbb R^n,\mathbb R^m)$ denote the set of all linear mappings from $\mathbb{R}^n$ to $\mathbb{R}^m.$ For any linear mapping $F\in L(\mathbb R^n,\mathbb R^m),$ we may identify $F$ with the matrix of $F$ in the canonical bases of $\mathbb R^n$ and $\mathbb R^m,$ and so we can identify $L(\mathbb R^n,\mathbb R^m)$ with $\mathbb{R}^{m \times n}$.

\subsection{Semi-algebraic geometry}

We recall some notions and results of Semi-Algebraic Geometry, which can be found in \cite{Benedetti1990, Bochnak1998, Coste2000-1, Dries1996, Dries1998}.

\begin{definition}{\rm
\begin{enumerate}[{\rm (i)}]
  \item A subset of $\mathbb{R}^n$ is called {\em semi-algebraic} if it is a finite union of sets of the form
$$\{x \in \mathbb{R}^n: \ f(x) = 0 ;\ g_i(x) > 0, i = 1, \ldots, k\}$$
where $f$ and all $g_{i}$ are polynomials.
 \item Let $X \subset \mathbb{R}^n$ and $Y \subset \mathbb{R}^m$ be semi-algebraic sets. A mapping $F \colon X \to Y$ is said to be {\em semi-algebraic} if its graph
$$\{(x, y) \in X \times Y  : \ y = F(x)\}$$
is a semi-algebraic subset of $\mathbb{R}^n\times\mathbb{R}^m.$
\end{enumerate} }
\end{definition}

A major fact concerning the class of semi-algebraic sets is the following theorem.

\begin{theorem}[{Tarski--Seidenberg,  \cite[Theorem 2.3.4]{Benedetti1990}, \cite[Proposition~2.2.7]{Bochnak1998}, \cite[Proposition~1.7]{HaHV2017}}] \label{TarskiSeidenbergTheorem1}
The image of a semi-algebraic set by a semi-algebraic mapping is semi-algebraic.
\end{theorem}

Moreover, we have the following properties:
\begin{enumerate}[{\rm (i)}]
\item The class of semi-algebraic sets is closed with respect to Boolean operators, taking Cartesian product, closure, interior and inverse image under semi-algebraic mappings;
\item A composition of semi-algebraic mappings is a semi-algebraic mapping;
\item The  inverse image of  a  semi-algebraic set  under  a  semi-algebraic mapping is semi-algebraic;
\end{enumerate}

\subsection{Stratification of semi-algebraic sets}

\begin{definition}{\rm
A {\em semi-algebraic stratification} of a semi-algebraic subset $X$ of $\mathbb R^n$ is a finite partition $\mathcal S:=\{X_\alpha\}_{\alpha \in I}$ of $X$ such that:
\begin{enumerate}[\ $\bullet$]
\item Each $X_\alpha$ (called a {\em stratum of the stratification} or, briefly, a {\em stratum of $X$}) is a connected semi-algebraic analytic submanifold of $\mathbb R^n$.

\item The following {\em frontier condition} holds: If ${X_\alpha}\cap \overline{X}_\beta\ne\emptyset$, then ${X_\alpha}\subset \overline{X}_\beta.$
\end{enumerate} }
\end{definition}

The following is well-known (see, for example, \cite[Proposition~2.5.1]{Benedetti1990} and \cite[Proposition~9.1.8]{Bochnak1998}).

\begin{proposition}\label{CD1}
Every semi-algebraic set admits a semi-algebraic stratification.
\end{proposition}

Let $X\subset\mathbb R^n$ be a semi-algebraic set and let $\mathcal S:=\{X_\alpha\}_{\alpha \in I}$ be a semi-algebraic stratification of $X.$ We define the {\em dimension} of $X$ by
$$\dim X:=\max\{\dim X_\alpha:\ \alpha\in I\}.$$
It is not hard to check that this definition of dimension does not depend on the stratification of $X.$ For convenience, set $\dim\emptyset=-1$.
Furthermore, we have the following properties of the dimension; see, for example, \cite[Section~2.8]{Bochnak1998}, \cite[Proposition~1.4]{HaHV2017}, \cite[Property~4.7]{Dries1996}.

\begin{lemma} \label{DimensionLemma}
If $X$ be a non-empty semi-algebraic set in $\mathbb{R}^n,$ then $\dim(\overline{X}\setminus X)<\dim X.$ In particular, $\dim\overline{X}=\dim X.$
\end{lemma}

\begin{lemma}\label{DenseIsOpen}
Let $X\subset\mathbb R^n$ be a semi-algebraic set. The following statements are equivalent.
\begin{enumerate}[{\rm (i)}]
\item $X$ is dense in $\mathbb R^n;$
\item $X$ contains an open dense semi-algebraic subset of $\mathbb R^n;$
\item $\dim(\mathbb{R}^n \setminus X) < n.$
\end{enumerate}
\end{lemma}

\begin{proof}
(i) $\Rightarrow$ (ii).
Let $\mathcal S = \{X_\alpha\}_{\alpha \in I}$ be a semi-algebraic stratification of ${X}.$ Let $Y$ be the union of strata of dimension $n.$
Then it is easy to see that $Y$ has the desired properties.

(ii) $\Rightarrow$ (i). Clearly.

(i) $\Rightarrow$ (iii).  By contradiction, suppose that $\dim (\mathbb{R}^n \setminus X) = n.$
The set $\mathbb{R}^n \setminus X$ is semi-algebraic (because $X$ is semi-algebraic) and hence it contains a nonempty open set. This implies that $\overline{X} \ne \mathbb{R}^n,$ which contradicts the assumption.

(iii) $\Rightarrow$ (i).
Take any $x \not \in X.$ By assumption, $U \cap {X} \ne \emptyset$ for all open sets $U$ containing $x.$ This implies that $x \in \overline{X}$ and hence $X$ is dense in $\mathbb{R}^n.$
\end{proof}

In the sequel we will make use of the following result.

\begin{theorem}[{Hardt, \cite{Hardt1980}}] \label{HardtTheorem}
Let $X$ and $Y$ be respectively semi-algebraic sets in $\mathbb{R}^n$ and $\mathbb{R}^m$, $f \colon X \rightarrow Y$ be a continuous semi-algebraic mapping.
Then there exists a partition of $Y$ into finitely many semi-algebraic subsets $Y_i, i = 1, \ldots, p,$ such that $f$ is semi-algebraically trivial over each $Y_i,$ i.e., there exists a semi-algebraic set $F_i \subset \mathbb{R}^n$ and a semi-algebraic homeomorphism
$h_i \colon f^{-1} (Y_i) \rightarrow Y_i \times F_i$
such that the following diagram commutes
$$\begin{tikzcd}
f^{-1}(Y_i) \arrow {r}{h_i}
\arrow{rd}{f}
& Y_i \times F_i \arrow {d}{\pi} \\
& Y_i
\end{tikzcd}$$
where $\pi$ is the projection on the first factor.
\end{theorem}

As a consequence of Theorem~\ref{HardtTheorem}, we obtain the following useful corollaries.

\begin{corollary}\label{Everywhere}
Let $\mathscr{U} \subset \mathbb R^n\times\mathbb R^m$ be an open dense semi-algebraic set. Then there is a set $\mathscr{V}\subset\mathbb R^m$ containing an open dense semi-algebraic set in $\mathbb R^m$ such that for any $y \in \mathscr{V},$ the semi-algebraic set
$$\mathscr{U}_y:=\{x\in\mathbb R^n:\ (x,y)\in \mathscr{U}\}$$
contains an open dense semi-algebraic set in $\mathbb R^n.$
\end{corollary}

\begin{proof}
Let $f\colon(\mathbb R^n\times\mathbb R^m)\setminus \mathscr{U} \to\mathbb R^m$ be the projection $(x,y)\mapsto y$.
In light of Theorem~\ref{HardtTheorem}, we can write  $\mathbb R^m = \bigcup_{i = 1}^p Y_i$ as a disjoint union of semi-algebraic sets $Y_i \subset \mathbb R^m$ such that $f^{-1}(Y_i)$ is semi-algebraically homeomorphic to $f^{-1}(y_i)\times Y_i,$ for each $i$ and any $y_i\in Y_i.$ Let
$$\displaystyle \mathscr{V} :=\bigcup_{\substack{i=1,\dots,p;\\\dim Y_i=m}}Y_i.$$
Then $\mathscr{V}$ is a semi-algebraic set in $\mathbb R^m$ satisfying $\dim(\mathbb R^m\setminus \mathscr{V})<m.$ By Lemma~\ref{DenseIsOpen}, $\mathscr{V}$ contains an open dense semi-algebraic subset of $\mathbb R^m.$

Assume for contradiction that there exists $y \in \mathscr{V}$ such that $\mathscr{U}_{y}$ does not contain an open dense semi-algebraic set in $\mathbb R^n.$ It follows that $\mathbb R^n\setminus \mathscr{U}_{y}$ contains an open set in $\mathbb R^n,$ which yields that
$$\dim (f^{-1}(y))=\dim((\mathbb R^n\setminus \mathscr{U}_{y})\times\{y\}) = n.$$
Let $i\in\{1,\dots,p\}$ be such that $y\in Y_i.$
Since $f^{-1}(Y_i)$ is semi-algebraically homeomorphic to $f^{-1}(y)\times Y_i,$ it follows that
$$\dim(f^{-1}(Y_i))=\dim(f^{-1}(y))+\dim Y_i=n+m,$$
Hence, $f^{-1}(Y_i)$ contains an open subset of $\mathbb R^n\times\mathbb R^m$. This contradicts the assumption that the set $\mathscr{U}$ is dense in $\mathbb R^n\times\mathbb R^m.$ The corollary is proved.
\end{proof}

\begin{corollary}\label{DimInfinity}
Let $X\subset\mathbb R^n$ be an unbounded semi-algebraic set. For $R>0$ large enough, the following statements hold:
\begin{enumerate}[{\rm (i)}]
\item the dimension of $X\setminus\mathbb B^n_R$ is constant and is called the {\em dimension at infinity} of $X$, denoted by $\dim_\infty X;$
\item the dimension of $X\cap\mathbb{S}^{n - 1}_R$ is constant and equals to $\dim_\infty X - 1.$
\end{enumerate}
\end{corollary}
\begin{proof}
Consider the continuous semi-algebraic function $f \colon X \to \mathbb R, x \mapsto \|x\|.$ In light of Theorem~\ref{HardtTheorem}, we can find a constant $R > 0$ such that $f$ is semi-algebraically trivial over the interval $(R, +\infty).$ From this, the desired conclusion follows easily.
\end{proof}

\subsection{Sard's theorem with parameter}

Next we state a semialgebraic version of Sard's theorem with the
parameter  in a simplified form which is sufficient for the
applications studied here. Given a differentiable map between differentiable
manifolds $f \colon X \rightarrow Y,$ a point $y \in Y$ is called a
{\em regular value} \index{regular value} for $f$ if either $f^{-1}(y)
= \emptyset$ or the derivative map $Df(x) \colon T_xX \rightarrow
T_yY$ is surjective at every point $x \in f^{-1}(y),$ where $T_x X$
and $T_yY$ denote the tangent spaces of $X$ at $x$ and of $Y$ at $y,$
respectively. A point $y \in Y$ that is not a regular value of $f$ is
called a {\em critical value.} The following result is also called Thom's weak transversality theorem.

\begin{theorem}[Sard's theorem with parameter] \label{SardTheorem}
Let $f \colon X \times \mathscr{P} \rightarrow Y$ be a differentiable
semialgebraic map between semialgebraic submanifolds.
If $y \in Y$ is a regular value of $f,$ then there exists a
semialgebraic set $\Sigma \subset \mathscr{P}$
of dimension smaller than the dimension of $\mathscr{P}$ such that$,$ for every $p
\in \mathscr{P} \setminus \Sigma,$ $y$ is a regular value of the map
$f_p \colon X \rightarrow Y, x \mapsto f(x, p).$
\end{theorem}
\begin{proof}
For a proof, we refer the reader to \cite[Theorem~1.3.6]{Goresky1988}, \cite[The Transversality Theorem, page 68]{Guillemin1974} or \cite[Theorem~1.10]{HaHV2017}.
\end{proof}

\section{Tangent cones at infinity}\label{Section3}

In this section, we define and present some properties of tangent cones at infinity of unbounded semi-algebraic sets in $\mathbb R^n.$
First of all, let us agree to call a set $C \subset \mathbb{R}^n$ a {\em cone} if whenever $x \in C,$ then $tx \in C$ for all $t \geqslant 0$.

\begin{definition}{\rm
By the {\em tangent cone at infinity} (known also as the {\em asymptotic cone}) of  a subset $X$ of $\mathbb{R}^n$ we mean the set
\begin{eqnarray*}
C_\infty X :=
\left\{
\begin{array}{llll}v \in \mathbb R^n:& \textrm{there exist sequences } x^k\in X \textrm{ and } t_k\in (0,+\infty) \textrm{ such that }\\
& x^k\to \infty \textrm{ and } t_k x^k\to v \textrm{ as }k\to\infty
\end{array}\right\}.
\end{eqnarray*} }
\end{definition}

The following lemma is a version at infinity of \cite[Lemma~1.2]{Kurdyka1989} (see also \cite[Corollary~2.18]{Fernandes2020}).

\begin{lemma}\label{Lemma32}
Let $X$ be an unbounded semi-algebraic subset of $\mathbb R^n.$ Then $C_\infty X$ is a nonempty closed semi-algebraic cone of dimension at most $\dim_\infty X,$ where $\dim_\infty X$ is defined in Corollary~\ref{DimInfinity}.
\end{lemma}

\begin{proof}
Since the set $X$ is unbounded, there exists a sequence $x^k \in X$ with $x^k\to \infty.$ Then for all sufficiently large $k,$ we have $t_k := \|x^k\|^{-2} \in (0, +\infty).$ Moreover,  $t_k x^k \to 0 \textrm{ as }k\to\infty.$ By definition, $0 \in C_\infty X$ and so $C_\infty X$ is nonempty.

Let $v \in C_\infty X.$ By definition, there exist sequences $x^k \in X$ and $t_k \in (0, +\infty)$ such that
$$x^k\to \infty \quad \textrm{ and } \quad  t_k x^k\to v \textrm{ as }k\to\infty.$$
Take any $\lambda \in (0, +\infty).$ Observe that $\lambda t_k \in (0, +\infty)$ and $(\lambda t_k) x^k \to \lambda v$ as $k \to \infty.$ By definition, then $\lambda v  \in C_\infty X.$ Hence $C_\infty X$ is a cone.

For each $R > 0,$ define
$$A_R :=\{(tx, t) \in \mathbb{R}^n \times (0,+\infty): \ x \in X \setminus \mathbb{B}^n_R\}.$$
Clearly, $A_R$ is a nonempty semi-algebraic set.
Moreover
\begin{equation}\label{sub}C_\infty X \times \{0\} \subset \overline{A}_R \cap (\mathbb{R}^n \times \{0\}) \subset \overline{A}_R \setminus A_R.\end{equation}
Let us prove that
\begin{equation}\label{sup}C_\infty X \times \{0\} \supset \overline{A}_R \cap (\mathbb{R}^n \times \{0\}).\end{equation}
For this, let $(v,0)\in \overline{A}_R \cap (\mathbb{R}^n \times \{0\}).$
If $v=0,$ then clearly $(v,0)\in C_\infty X \times \{0\}.$
So assume that $v\ne 0.$
By definition, there are sequences $x^k\in X \setminus \mathbb{B}^n_R$ and $t_k\in (0,+\infty)$ such that
$$t_k\to 0\ \text{ and }\ t_k x^k\to v.$$
This, together with the fact that $v\ne 0$, implies that $x^k\to\infty.$
Thus, by definition, $v\in C_\infty X $ and so $(v,0)\in C_\infty X \times \{0\}.$
Consequently,~\eqref{sup} holds.
From~\eqref{sub} and~\eqref{sup}, we have
$$C_\infty X \times \{0\} = \overline{A}_R \cap (\mathbb{R}^n \times \{0\}).$$
As $C_\infty X \times \{0\}$ is the intersections of two closed semi-algebraic sets, it follows that $C_\infty X \times \{0\}$ and so $C_\infty X$ are closed semi-algebraic sets.

Finally, observe that $A_R$ is homeomorphic to $(X \setminus \mathbb{B}^n_R)\times (0,+\infty).$ Hence, for all $R$ large enough,
$$\dim A_R = \dim_\infty X + 1,$$
which, combined with Lemma~\ref{DimensionLemma} and~\eqref{sub}, yields
$$\dim C_\infty X  \leqslant \dim (\overline{A}_R \setminus A_R) < \dim A_R = \dim_\infty X + 1.$$
This completes the proof of the lemma.
\end{proof}

\section{Proof of the main theorem}\label{Section5}

The goal of this section is to give a proof of Main Theorem.
First of all, we provide a sufficient condition for the restriction of a linear mapping on a closed semi-algebraic set to be closed.

\begin{lemma}\label{Theorem41}
Let $X\subset\mathbb R^n$ be a closed semi-algebraic set and let $F \colon \mathbb{R}^n \to \mathbb{R}^m$ be a linear mapping. Set $ D := C_\infty X\cap\mathbb S^{n-1}$ and assume that $\ker F\cap D=\emptyset$. Then $F(X)$ is closed.
\end{lemma}

\begin{proof}
Let $y \in \overline{F(X)}.$ Then there is a sequence $x^k\in X$ such that $\displaystyle\lim_{k\to\infty} F(x^k)=y.$ We will show that $x^k$ has a convergent subsequence. For contradiction, assume that $x^k\to\infty$. Passing to a subsequence if necessary, we may suppose that $\displaystyle\lim_{k\to\infty}\frac{x^k}{\|x^k\|} = u \in D.$ Since $D$ is compact and $\ker F \cap D = \emptyset,$ it holds that $\displaystyle\|F(u)\|\geqslant\min_{x\in D}\|F(x)\|>0$ and so
$$\|y\| = \lim_{k\to\infty}\|F(x^k)\|=\lim_{k\to\infty}\|x^k\|\left\|F\left(\frac{x^k}{\|x^k\|}\right)\right\| = +\infty,$$
which is impossible. Therefore the sequence $x^k$ has a cluster point, say $x$. Clearly $x\in X$ and $F(x)=y$, so $y\in F(X)$.
\end{proof}

We are now in a position to prove the main result of the paper.

\begin{proof}[Proof of Main Theorem]

By Theorem~\ref{TarskiSeidenbergTheorem1},  it is not hard to check that the set
$$\{F\in L(\mathbb{R}^n, \mathbb{R}^m) \ : \ (F + G)(X) \text{ is closed}\}$$
is semi-algebraic so it remains to show that it contains an open dense semi-algebraic subset of $L(\mathbb{R}^n, \mathbb{R}^m).$
The proof is divided into two cases. First of all, we consider the case $G\equiv 0$.

\subsubsection*{Case 1: Linear case}

If $n\leqslant m$, then for any $F\in \mathcal{A}$, $F$ is a linear isomorphism from $\mathbb R^n$ onto $F(\mathbb{R}^n)$ and so $F(X)$ is closed.
Thus from now on, suppose that $n > m.$
We consider two sub-cases.

\subsubsection*{Case $1.1$: $d\leqslant m$}\

Set $D := C_\infty X\cap\mathbb S^{n-1}$.
In view of Proposition~\ref{CD1}, let $\mathcal S=\{D_\alpha\}_{\alpha\in I}$ be a semi-algebraic stratification of $D.$
Recall that we identify $L(\mathbb R^n,\mathbb R^m)$ with $\mathbb{R}^{m \times n}$. For each $\alpha \in I$ define the semi-algebraic mapping
$$\Phi_\alpha \colon \mathbb{R}^{m \times n} \times D_\alpha \to \mathbb  R^m, \quad (A, v) \mapsto Av.$$
Write $A=(a_{ij})_{\substack{i=1,\dots,m\\ j=1,\dots,n}}.$ Since $D_\alpha \subset D \subset \mathbb{S}^{n - 1},$ for each $v \in D_\alpha$ there exists an index $i_0,\ 1 \leqslant i_0 \leqslant n,$ such that $v_{i_0} \ne 0,$ and so the Jacobian matrix $D\Phi_\alpha$ of $\Phi_\alpha$ at $(A, v)$ contains the following diagonal matrix
$$\frac{\partial\Phi_\alpha}{\partial(a_{1i_0},\dots,a_{mi_0})} =
\begin{pmatrix}
v_{i_0} & 0 & \cdots & 0\\
0 & v_{i_0} & \cdots & 0\\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & v_{i_0}
\end{pmatrix},$$
which has rank $m.$ Hence $D\Phi_\alpha$ is of maximal rank $m$ at every point $(A,v) \in \mathbb{R}^{m \times n} \times D_\alpha.$ Consequently, $0$ is a regular value of the mapping $\Phi_\alpha.$ By Theorem~\ref{SardTheorem},
$$\mathscr{U}_\alpha := \{A\in \mathbb{R}^{m \times n} :
0 \textrm{ is a regular value of the mapping } \Phi_\alpha(A,\cdot) \colon D_\alpha \to \mathbb{R}^m \}$$
contains an open dense semi-algebraic set in $\mathbb{R}^{m \times n}.$

On the other hand, we have
$$\dim D_\alpha \leqslant \dim D < \dim C_\infty X \leqslant d \leqslant m,$$
where the third inequality follows from Lemma~\ref{Lemma32}. Hence, for each fixed $A\in \mathbb{R}^{m \times n}$, $0$ is a regular value of the mapping $\Phi_\alpha(A,\cdot) \colon D_\alpha \to \mathbb{R}^m$ if and only if
$$\{v \in D_\alpha : \ \Phi_\alpha(A, v) = 0\}  = \emptyset.$$
Therefore, we can write
$$\mathscr{U}_\alpha = \{F\in L(\mathbb R^n,\mathbb R^m):\ \ker F\cap D_\alpha=\emptyset\}.$$
Let $$\displaystyle \mathcal{A}_1 := \bigcap_{\alpha\in I}\mathscr{U}_\alpha = \{F\in L(\mathbb R^n,\mathbb R^m):\  \ker F\cap D=\emptyset\}.$$
Then $\mathcal{A}_1$ contains an open dense semi-algebraic set in $L(\mathbb R^n,\mathbb R^m).$
In view of Lemma~\ref{Theorem41}, $F(X)$ is closed for each $F\in\mathcal {A}_1$.
This end the proof for the case $d\leqslant m.$

\subsubsection*{Case $1.2$: $d> m$}\

The proof for this case is proceeded by induction on $d.$
There are two sub-cases to consider.

\subsubsection*{Case $1.2.1$: $d=n$}\

It is clear that the interior $\Int(X)$ of X is non-empty and open in $\mathbb R^n$.
Set $\partial X := X\setminus\Int(X).$ Then $\partial X$ is a closed semi-algebraic set of dimension less than $d.$
By the inductive assumption, there is an open dense semi-algebraic $\mathcal A_2\subset L(\mathbb R^n,\mathbb R^m)$ such that $F(\partial X)$ is closed for any $F\in\mathcal A_2.$ Let
\begin{equation*}
\mathcal{A} := \{F\in L(\mathbb{R}^n, \mathbb{R}^m)  : \ F\text{ has maximal rank}\},
\end{equation*}
which is an open dense semi-algebraic set in $L(\mathbb{R}^n, \mathbb{R}^m).$  Replace $\mathcal A_2$ by $\mathcal A_2\cap \mathcal A$ if $\mathcal A_2\not\subset \mathcal A.$ Let us prove that $F(X)$ is closed for all $F\in\mathcal A_2$.
To do this, take arbitrarily $y\in \overline{F(X)},$ we will show that $y\in F(X).$
Let $y^k\in F(X)$ be a sequence tending to $y.$
By taking a subsequence if necessary, we can assume that either $F^{-1}(y^k)\cap\partial X\ne\emptyset$ for all $k$ or $F^{-1}(y^k)\cap\partial X=\emptyset$ for all $k$.
In the first case, we have $y\in\overline{F(\partial X)}={F(\partial X)}\subset F(X).$
On the other hand, in the second case, we must have $F^{-1}(y^k) \subset X$ for all $k$
(indeed, if the contrary holds, there are $u^k\in F^{-1}(y^k)\cap X$ and $w^k\in F^{-1}(y^k)\setminus X$ for some $k;$
then the segment joining $u^k$ and $w^k$ must contains a point belonging to $F^{-1}(y^k)\cap\partial X,$ which is a contradiction).
Let $x^k$ be the unique point of the intersection $F^{-1}(y^k)\cap (\ker F)^\perp.$
Since $F$ has maximal rank, the restriction $F|_{(\ker F)^\perp}$ is a linear isomorphism from $(\ker F)^\perp$ onto $\mathbb R^m,$ and hence the sequence $x^k$ must converge to a point $x.$ It is clear that $x\in X$ and $F(x)=y.$
Consequently, $F(X)$ is closed.

\subsubsection*{Case $1.2.2$: $d<n$}\

By {\em Case $1.1$}, there is an open dense semi-algebraic set $\mathcal B_1$ in $L(\mathbb R^n,\mathbb R^d)$ such that $F_1(X)$ is closed for all $F_1\in\mathcal B_1$. For $F_1\in\mathcal B_1$, let
$$\mathcal B_2(F_1):=\{F_2\in L(\mathbb R^d,\mathbb R^m):\ F_2(F_1(X)) \text{ is closed}\}.$$
Observe that $\mathcal B_2(F_1)$ contains an open dense semi-algebraic set.
Indeed, this follows from the inductive assumption if $\dim F_1(X)<d$ and from {\em Case $1.2.1$} if $\dim F_1(X)=d$.
Let
$$\mathcal A_3:=\{F\in L(\mathbb R^n,\mathbb R^m):\ \text{ there are } F_1\in \mathcal B_1 \text{ and } F_2\in \mathcal B_2(F_1) \text{ such that }F=F_2\circ F_1\},$$
which is a semi-algebraic set. It is clear that $F(X)$ is closed for all $F\in\mathcal A_3.$
Let us show that $\mathcal A_3$  is dense in $L(\mathbb R^n,\mathbb R^m)$.
For this, pick arbitrarily $F\in L(\mathbb R^n,\mathbb R^m).$
It is not hard to see that there exist $F_1\in L(\mathbb R^n,\mathbb R^d)$ and $F_2\in L(\mathbb R^d,\mathbb R^m)$ such that $F=F_2\circ F_1.$
Since $\mathcal B_1$ is dense in $L(\mathbb R^n,\mathbb R^d)$, there is a sequence $F_1^k\in\mathcal B_1$ such that
$$\|F_1^k-F_1\|\leqslant \frac{1}{k}.$$
Furthermore, for each $k,$ as $\mathcal B_1(F_1^k)$ is dense in $L(\mathbb R^d,\mathbb R^m)$, there is $F_2^k\in \mathcal B_2(F_1^k)$ such that
$$\|F_2^k-F_2\|\leqslant \frac{1}{k}.$$
Set $F^k:=F_2^k\circ F_1^k.$
We have
$$\begin{array}{lll}\|F^k-F\|&=&\|F_2^k\circ F_1^k-F_2\circ F_1\|\\
&\leqslant& \|F_2^k\circ F_1^k-F_2^k\circ F_1\|+\|F_2^k\circ F_1-F_2\circ F_1\|\\
&\leqslant& \|F_2^k\| \|F_1^k-F_1\|+\|F_2^k-F_2\| \|F_1\|\\
&\leqslant&  \displaystyle \frac{1}{k} \left(\|F_2\| + \frac{1}{k} \right) + \frac{\|F_1\|}{k}.
\end{array}$$
Hence $F^k\to F$ as $k\to\infty.$
Therefore $\mathcal A_3$ is dense in $L(\mathbb R^n,\mathbb R^m).$
By Lemma~\ref{DenseIsOpen}, $\mathcal A_3$ contains an open dense semi-algebraic set in $L(\mathbb R^n,\mathbb R^m).$
This ends the proof for the linear case.

\subsubsection*{Case 2: General case}

Since the set $X$ is closed and the mapping $G$ is continuous, the semi-algebraic set
$$Z := \{(x, y)\in \mathbb{R}^n \times \mathbb{R}^m :\ x \in X,\ y = G(x)\}$$
is closed. Applying {\em Case 1} to $Z,$ we can see that the set
$$\{\mathcal{F} \in L(\mathbb{R}^n \times \mathbb{R}^m, \mathbb{R}^m) :\ \mathcal{F}(Z) \textrm{ is closed} \}$$
contains an open dense semi-algebraic set, say $\mathscr{U} \subset L(\mathbb{R}^n \times \mathbb{R}^m, \mathbb{R}^m).$
Consider the mapping
$$\Phi\colon L(\mathbb{R}^n \times \mathbb{R}^m, \mathbb{R}^m)\to L(\mathbb{R}^n, \mathbb{R}^m) \times L(\mathbb{R}^m, \mathbb{R}^m),\ \mathcal F \mapsto (F_1,F_2),$$
where $F_1 \in  L(\mathbb{R}^n, \mathbb{R}^m)$ and $F_2 \in L(\mathbb{R}^m, \mathbb{R}^m)$ are linear mappings defined as follows
$$F_1(x) :=\mathcal F(x,0) \ \textrm{ and } \ F_2(y):=\mathcal F(0,y) \ \textrm{ for all } \ x \in \mathbb{R}^n,\ y \in \mathbb{R}^m.$$
A simple calculation shows that $\Phi$ is a linear isomorphism. Consequently, $\Phi(\mathscr{U})$ is an open dense semi-algebraic set in $L(\mathbb{R}^n, \mathbb{R}^m) \times L(\mathbb{R}^m, \mathbb{R}^m)$.
In view of Corollary~\ref{Everywhere}, there exists a linear isomorphism $F_2^* \in L(\mathbb{R}^m, \mathbb{R}^m)$ such that  the set
$$\{{F} \in L(\mathbb{R}^n, \mathbb{R}^m) :\ (F, F_2^*) \in \Phi(\mathscr{U}) \}$$
contains an open dense semi-algebraic set in $L(\mathbb{R}^n, \mathbb{R}^m).$ Or, equivalently, the set
$$\{(F_2^*)^{-1} \circ {F} \in L(\mathbb{R}^n, \mathbb{R}^m) :\ (F, F_2^*) \in \Phi(\mathscr{U}) \}$$
contains an open dense semi-algebraic set in $L(\mathbb{R}^n, \mathbb{R}^m).$

Take arbitrarily $(F, F_2^*) \in \Phi(\mathscr{U}).$ Then the image $[\Phi^{-1}(F, F_2^*)](Z)$ is closed, and so is the set $(F_2^*)^{-1} \circ [\Phi^{-1}(F, F_2^*)](Z).$ Observe that
\begin{eqnarray*}
(F_2^*)^{-1} \circ [\Phi^{-1}(F, F_2^*)] (Z)
&=&  \left \{(F_2^*)^{-1} (F(x) + F_2^*(y)) :\ x \in X,\ y = G(x) \right\} \\
&=&  \left \{[(F_2^*)^{-1} \circ F](x) + y :\ x \in X,\ y = G(x) \right\} \\
&=&  \left \{[(F_2^*)^{-1} \circ F](x) + G(x) :\ x \in X \right\}.
\end{eqnarray*}
Hence the last set is also closed. The theorem is proved.
\end{proof}

\subsection*{Acknowledgments}
The first and the third authors were partially supported by the Vietnam Academy of Science and Technology under Grant Number \DD LTE00.01/21-22.
The second author was partially supported by the grant of Narodowe Centrum Nauki number 2019/33/B/ST1/00755.