# Singularities of Fitzpatrick and convex functions

Dmitry Kramkov111Carnegie Mellon University, Department of Mathematical
Sciences, 5000 Forbes Avenue, Pittsburgh, PA, 15213-3890, USA,
<EMAIL_ADDRESS>The author also has a research position at the University of
Oxford. and Mihai Sîrbu222The University of Texas at Austin, Department of
Mathematics, 2515 Speedway Stop C1200, Austin, Texas 78712,
<EMAIL_ADDRESS>The research of this author was supported in part by
the National Science Foundation under Grant DMS 1908903.

###### Abstract

In a pseudo-Euclidean space with scalar product $S(\cdot,\cdot)$, we show that
the singularities of projections on $S$-monotone sets and of the associated
Fitzpatrick functions are covered by countable $c-c$ surfaces having positive
normal vectors with respect to the $S$-product. By Zajíček [24], the
singularities of a convex function $f$ can be covered by a countable
collection of $c-c$ surfaces. We show that the normal vectors to these
surfaces are restricted to the cone generated by $F-F$, where
$F:=\operatorname*{cl}\operatorname*{range}\nabla f$, the closure of the range
of the gradient of $f$.

Keywords:

convexity, subdifferential, Fitzpatrick function, projection, pseudo-Euclidean
space, normal vector, singularity.

AMS Subject Classification (2020):

26B25, 26B05, 47H05, 52A20.

##  1 Introduction

A locally Lipschitz function $f=f(x)$ on $\real{d}$ is differentiable almost
everywhere, according to the Rademacher’s Theorem. The set of its
singularities

$\Sigma(f):=\left\\{{x\in\real{d}}|\;f\text{ is not differentiable at
}x\right\\}$

can be quite irregular. For instance, for $d=1$, Zahorski [23] (see Fowler and
Preiss [11] for a simple proof) shows that _any_ $G_{\delta\sigma}$ set
(countable union of countable intersections of open sets) of Lebesgue measure
zero is the singular set of _some_ Lipschitz function.

By Zajíček [24], the $\Sigma(f)$ of a convex function $f=f(x)$ on $\real{d}$
has $c-c$ structure: it can be covered by a countable collection of the graphs
of the differences of two convex functions of dimension $d-1$. Short proofs of
the Zajíček theorem can be found in Benyamini and Lindenstrauss [5, Theorem
4.20, p. 93], Thibault [22, Theorem 12.22, p. 1147], and Hajłasz [13]. Alberti
[2] shows that, except for sets with zero $\mathcal{H}^{d-1}$ measure, the
Hausdorff measure of dimension $d-1$, the covering can be achieved with smooth
surfaces. These results yield sharp conditions for the existence and
uniqueness of optimal maps in $\mathcal{L}_{2}$ optimal transport, see Brenier
[6] and Ambrosio and Gigli [3, Theorem 1.26].

Let $E$ be a closed subset of $\real{d}$ and

$d_{E}(x):=\inf_{y\in E}|x-y|,\quad P_{E}(x):=\left\\{{y\in
E}|\;|x-y|=d_{E}(x)\right\\},$

be the Euclidean distance to $E$ and the projection on $E$, respectively.
Erdös [8] proves that the singular set

$\Sigma(P_{E}):=\left\\{{x\in\real{d}}|\;P_{E}(x)\text{ contains at least two
points}\right\\}$

can be covered by countable sets with finite $\mathcal{H}^{d-1}$ measure.
Hajłasz [13] uses [24] and the observation of Asplund [4] that the function

$\psi_{E}(x):=\frac{1}{2}|x|^{2}-\frac{1}{2}d_{E}^{2}(x),\quad x\in\real{d},$

is convex, to conclude that $\Sigma(P_{E})$ has the $c-c$ structure. Albano
and Cannarsa [1] obtain a lower bound on the size of the set $\Sigma(d_{E})$,
where $d_{E}$ is not differentiable.

Let $S$ be a $d\times d$ invertible symmetric matrix with
$m\in\left\\{{0,1,\dots,d}\right\\}$ positive eigenvalues. Motivated by
applications to backward martingale transport in [17], [15], and [16], we
investigate in this paper the singularities of projections on monotone sets in
the pseudo-Euclidean space with the scalar product

$S(x,y):=\left\langle x,Sy\right\rangle=\sum_{i,j=1}^{d}x^{i}S^{ij}y^{j},\quad
x,y\in\real{d}.$

Let $G\subset\real{d}$ be an $S$-monotone or $S$-positive set:

$S(x-y,x-y)\geq 0,\quad x,y\in G.$

For every $x\in\real{d}$, the scalar square to $G$ and the projection on $G$
are given by

$\displaystyle\phi_{G}(x)$ $\displaystyle:=\inf_{y\in G}S(x-y,x-y),$
$\displaystyle P_{G}(x)$ $\displaystyle:=\operatorname*{arg\>min}_{y\in
G}S(x-y,x-y).$

Note that $S$-monotonicity is equivalent to $x\in G\implies x\in P_{G}(x)$ and
that

$\psi_{G}(x):=\frac{1}{2}S(x,x)-\frac{1}{2}\phi_{G}(x),\quad x\in\real{d},$

is the Fitzpatrick function studied in [10], [21], and [18].

The singularities of the projection $P_{G}$ can be classified as

$\displaystyle\Sigma(P_{G})$
$\displaystyle:=\left\\{{x\in\real{d}}|\;P_{G}(x)\text{ contains at least two
points}\right\\}$ $\displaystyle\;={\Sigma}_{0}(P_{G})\cup\Sigma_{1}(P_{G}),$
$\displaystyle{\Sigma}_{0}(P_{G})$
$\displaystyle:=\left\\{{x\in\Sigma(P_{G})}|\;S(y_{1}-y_{2},y_{1}-y_{2})=0\text{~{}for
\emph{all}~{}}y_{1},y_{2}\in P_{G}(x)\right\\},$
$\displaystyle\Sigma_{1}(P_{G})$
$\displaystyle:=\left\\{{x\in\Sigma(P_{G})}|\;S(y_{1}-y_{2},y_{1}-y_{2})>0\text{~{}for
\emph{some}~{}}y_{1},y_{2}\in P_{G}(x)\right\\}.$

By Theorem 4.6, $\Sigma_{1}(P_{G})$ is contained in a countable union of $c-c$
surfaces having strictly positive normal vectors in the $S$-space. The
structure of the zero-order singularities is described in Theorems 4.8 and
4.7. If $m=1$, then ${\Sigma}_{0}(P_{G})$ is covered by a countable number of
hyperplanes having isotropic normal vectors in the $S$-space. If $m\geq 2$,
then ${\Sigma}_{0}(P_{G})$ is covered by a countable family of $c-c$ surfaces
whose normal vectors are positive and almost isotropic in the $S$-space. These
results yield sharp conditions for the existence and uniqueness of backward
martingale maps in [16].

Using similar tools, in Theorem 3.1, we improve the $c-c$ description of
singularities of general convex functions $f=f(x)$ from Zajíček [24] by
showing that the covering surfaces have normal vectors belonging to the cone
generated by $F-F$, where $F:=\operatorname*{cl}\operatorname*{range}\nabla
f$, the closure of the range of the gradient of $f$.

##  2 Parametrization of singularities

We say that a function $g=g(x)$ on $\real{d}$ has _linear growth_ if there is
a constant $K=K(g)>0$ such that

$\left\lvert g(x)\right\rvert\leq K(1+\left\lvert x\right\rvert),\quad
x\in\real{d}.$

We write $\operatorname{dom}{\nabla g}$ for the set of points where $g$ is
differentiable.

Let $j\in\left\\{{1,\dots,d}\right\\}$. We denote by $\mathcal{C}^{j}$ the
collection of compact sets $C$ in $\real{d}$ such that

$y^{j}=1,\quad y\in C.$

Any compact set $C\subset\left\\{{x\in\real{d}}|\;x^{j}>0\right\\}$ can be
rescaled as

$\theta^{j}(C):=\left\\{{\frac{y}{y^{j}}}|\;y\in
C\right\\}\in\mathcal{C}^{j}.$

For $x\in\real{d}$, we denote by $x^{-j}$ its sub-vector without the $j$th
coordinate:

$x^{-j}:=\left({x^{1},\dots,x^{j-1},x^{j+1},\dots,x^{d}}\right)\in\real{d-1}.$

For $C\in\mathcal{C}^{j}$, we write $\mathcal{H}^{j}_{C}$ for the family of
functions $h=h(x)$ on $\real{d}$ having the decomposition:

$h(x)=x^{j}+g_{1}(x^{-j})-g_{2}(x^{-j}),\quad x\in\real{d},$ (1)

where the functions $g_{1}$ and $g_{2}$ on $\real{d-1}$ are convex, have
linear growth, and

$\nabla h(x)\in C,\quad x^{-j}\in\operatorname{dom}{\nabla
g_{1}}\cap\operatorname{dom}{\nabla g_{2}}.$ (2)

The latter property has a clear geometric interpretation. Let $H$ be a closed
set in $\real{d}$ and $x\in H$. Following [20, Definition 6.3 on page 199], we
call a vector $w\in\real{d}$ _regular normal to $H$ at $x$_ if

$\limsup_{\begin{subarray}{c}H\ni y\to x\\\
y\not=x\end{subarray}}\frac{\left\langle w,y-x\right\rangle}{\left\lvert
y-x\right\rvert}\leq 0.$

A vector $w\in\real{d}$ is called _normal to $H$ at $x$_ if there exist
$x_{n}\in H$ and a regular normal vector $w_{n}$ to $H$ at $x_{n}$ such that
$x_{n}\rightarrow x$ and $w_{n}\rightarrow w$.

For a set $B$ in $\real{d}$, we denote by $\operatorname*{conv}{B}$ its convex
hull.

######  Lemma 2.1.

Let $j\in\left\\{{1,\dots,d}\right\\}$, $C\in\mathcal{C}^{j}$, $h$ be given by
(1) for convex functions $g_{1}$ and $g_{2}$ with linear growth, and $H$ be
the zero-level set of $h$:

$H:=\left\\{{x\in\real{d}}|\;h(x)=0\right\\}.$

Then $h\in\mathcal{H}^{j}_{C}$, that is, (2) holds, if and only if for every
$x\in H$, there exists a normal vector $w\in C$ to $H$ at $x$.

###### Proof.

We can assume that $j=1$. Denote $f:=g_{1}-g_{2}$, so that
$h(x)=x^{1}+f(x^{-1})$. We have that
$\operatorname{dom}{\nabla{h}}=\real{}\times\operatorname{dom}{\nabla{f}}$,
$\nabla h(x)=\left({1,\nabla f(x^{-1})}\right)$, and

$H=\left\\{{(-f(u),u)}|\;u\in\real{d-1}\right\\}.$

Denote also $U:=\operatorname{dom}{\nabla g_{1}}\cap\operatorname{dom}{\nabla
g_{2}}\subset\operatorname{dom}{\nabla{f}}$.

$\implies$: Clearly, the gradient $\nabla h(x)$ is a regular normal vector to
$H$ at $x\in\operatorname{dom}{\nabla h}\cap H$. As $U$ is dense in
$\real{d-1}$, the result holds by standard compactness arguments.

$\impliedby$: Let $u\in U$, $v\in\real{d-1}$, and $w=(1,v)\in C$ be a normal
vector to $H$ at $x=(-f(u),u)$. Take a sequence $(x_{n},w_{n})$, $n\geq 1$,
that converges to $(x,w)$ and where $w_{n}$ is a regular normal vector to $H$
at $x_{n}\in H$ with $w_{n}^{1}=1$. Such a sequence exists by the definition
of a normal vector. We can represent $x_{n}=(-f(u_{n}),u_{n})$ for
$u_{n}\in\real{d-1}$ and $w_{n}=(1,v_{n})$ for $v_{n}\in\real{d-1}$.

We claim that $v_{n}$ belongs to the Clarke gradient of $f$ at $u_{n}$:

$v_{n}\in\overline{\partial}f(u_{n}):=\operatorname*{conv}\left\\{{\lim_{m}\nabla
f(r_{m})}|\;\operatorname{dom}\nabla f\ni r_{m}\to u_{n}\right\\}.$

The continuity of $\nabla f$ at $u\in U$ then yields that $v_{n}\to\nabla
f(u)$. Hence, $\nabla f(u)=v$, implying that $\nabla h(x)=(1,\nabla f(u))=w\in
C$.

In order to prove the claim, we write the definition of $w_{n}=(1,v_{n})$
being regular normal to $H$ at $x_{n}=(-f(u_{n}),u_{n})$ as

$\limsup_{\begin{subarray}{c}r\rightarrow u_{n}\\\
r\not=u_{n}\end{subarray}}\frac{-\left({f(r)-f(u_{n})}\right)+\left\langle
v_{n},r-u_{n}\right\rangle}{|f(r)-f(u_{n})|+|r-u_{n}|}\leq 0.$

Using the Lipschitz property of $f$, we obtain that

$\left\langle v_{n},s\right\rangle\leq\limsup_{\delta\downarrow
0}\frac{f(u_{n}+\delta s)-f(u_{n})}{\delta},\quad s\in\real{d-1}.$

By [7, Corollary 1.10], we have that $v_{n}\in\overline{\partial}f(u_{n})$, as
claimed. ∎

We recall that the subdifferential $\partial
f:\;\real{d}\rightrightarrows\real{d}$ of a closed convex function
$f:\;\real{d}\rightarrow\mathbb{R}\cup\left\\{{+\infty}\right\\}$ is defined
as

$\partial f(x):=\left\\{{y\in\real d}|\;\left\langle z,y\right\rangle\leq
f(x+z)-f(x),\,z\in\real{d}\right\\}.$

Clearly, $\operatorname{dom}\partial f:=\left\\{{x\in\real{d}}|\;\partial
f(x)\not=\emptyset\right\\}\subset\operatorname{dom}f:=\left\\{{x\in\real{d}}|\;f(x)<\infty\right\\}$.

The following theorem is our main technical tool for the study of
singularities of convex and Fitzpatrick functions in Sections 3 and 4.

######  Theorem 2.2.

Let $f:\;\real{d}\rightarrow\mathbb{R}\cup\left\\{{+\infty}\right\\}$ be a
closed convex function, $j\in\left\\{{1,\dots,d}\right\\}$, and $C_{1}$ and
$C_{2}$ be compact sets in $\real{d}$ such that

$y^{j}>0,\quad y\in C_{2}-C_{1}.$

There exists a function $h\in\mathcal{H}^{j}_{\theta^{j}(C_{2}-C_{1})}$ such
that

$\displaystyle\Sigma_{C_{1},C_{2}}(\partial f):=$
$\displaystyle\left\\{{x\in\operatorname{dom}{\partial f(x)}}|\;\partial
f(x)\cap C_{i}\not=\emptyset,\,i=1,2\right\\}$ $\displaystyle\subset$
$\displaystyle\left\\{{x\in\real{d}}|\;h(x)=0\right\\}.$

The proof of the theorem relies on Lemma 2.3. For a closed set
$A\subset\real{d}$, we denote

$f_{A}(x):=\sup_{y\in A}\left({\left\langle
x,y\right\rangle-f^{*}(y)}\right),\quad x\in\real{d},$ (3)

where $f^{*}$ is the convex conjugate of $f$:

$f^{*}(y):=\sup_{x\in\real{d}}\left({\left\langle
x,y\right\rangle-f(x)}\right)\in\mathbb{R}\cup\left\\{{+\infty}\right\\},\quad
y\in\real{d}.$

We have that $f_{A}$ is a closed convex function taking values in
$\mathbb{R}\cup\left\\{{+\infty}\right\\}$ if and only if

$A\cap\operatorname{dom}{f^{*}}=\left\\{{x\in
A}|\;f^{*}(x)<\infty\right\\}\not=\emptyset;$

otherwise, $f_{A}=-\infty$. We recall that

$f(x)=\left\langle x,y\right\rangle-f^{*}(y)\iff y\in\partial f(x)\iff
x\in\partial f^{*}(y).$ (4)

######  Lemma 2.3.

Let $f:\;\real{d}\rightarrow\mathbb{R}\cup\left\\{{+\infty}\right\\}$ be a
closed convex function and $C$ be a compact set in $\real{d}$ such that
$C\cap\operatorname{dom}{f^{*}}\not=\emptyset$. Then $f_{C}$ has linear growth
and for every $x\in\real{d}$,

$\displaystyle\partial f_{C}(x)\cap
C=\operatorname{Arg}_{C}(x):=\operatorname*{arg\>max}_{y\in
C}\left({\left\langle x,y\right\rangle-f^{*}(y)}\right)\not=\emptyset,$
$\displaystyle\partial f_{C}(x)=\operatorname*{conv}{\left({\partial
f_{C}(x)\cap C}\right)},$ $\displaystyle\partial f(x)\cap C\not=\emptyset\iff
f(x)=f_{C}(x)\iff\partial f(x)\cap C=\partial f_{C}(x)\cap C.$

In particular, $f_{C}$ is differentiable at $x$ if and only if $\partial
f_{C}(x)\cap C$ is a singleton, in which case

$\partial f_{C}(x)=\left\\{{\nabla f_{C}(x)}\right\\}\in C.$

###### Proof.

Since $C$ is a compact set, $f^{*}$ is a closed convex function, and
$C\cap\operatorname{dom}{f^{*}}\not=\emptyset$, we have that

$\sup_{y\in C}\left\lvert y\right\rvert<\infty,\quad\inf_{x\in
C}f^{*}(x)>-\infty,$

and that $\operatorname{Arg}_{C}(x)$ is a non-empty compact. Let $y_{0}\in
C\cap\operatorname{dom}{f^{*}}$. From the definition of $f_{C}$ we deduce that

$-\left\lvert x\right\rvert\left\lvert y_{0}\right\rvert-f^{*}(y_{0})\leq
f_{C}(x)\leq\left\lvert x\right\rvert\sup_{y\in C}\left\lvert
y\right\rvert-\inf_{y\in C}f^{*}(y),\quad x\in\real{d}.$

It follows that $f_{C}$ has linear growth.

The function

$h(x,y):=\left\langle
x,y\right\rangle-f^{*}(y)\in\real{}\cup\left\\{{-\infty}\right\\},\quad
x,y\in\real{d},$

is linear in $x$ and concave and upper semi-continuous in $y$. Fix
$x\in\real{d}$. We can choose $K$ large enough such that for

$E:=\left\\{{z\in C}|\;f^{*}(z)\leq K\right\\},$

we have that $f_{C}=f_{E}$ in a neighborhood of $x$ and

$\operatorname{Arg}_{C}(x)=\operatorname{Arg}_{E}(x):=\operatorname*{arg\>max}_{y\in
E}\left({\left\langle x,y\right\rangle-f^{*}(y)}\right).$

Since $E$ is compact and the function $h(\cdot,y)$ is finite for $y\in E$, the
classical envelope theorem [14, Theorem 4.4.2, p. 189] yields that

$\displaystyle\partial f_{C}(x)\ $ $\displaystyle=\partial
f_{E}(x)=\partial\max_{y\in
E}h(x,y)=\operatorname*{conv}\bigcup_{y\in\operatorname{Arg}_{E}(x)}\partial_{x}h(x,y)=\operatorname*{conv}\operatorname{Arg}_{E}(x)$
$\displaystyle=\operatorname*{conv}{\operatorname{Arg}_{C}(x)}.$

From the concavity of $h(x,\cdot)$ we deduce that

$\partial f_{C}(x)\cap
C=\left({\operatorname*{conv}{\operatorname{Arg}_{C}(x)}}\right)\cap
C=\operatorname{Arg}_{C}(x).$

Clearly, $f_{C}\leq f$. If $y\in\partial f(x)\cap C$, then $f(x)=\left\langle
x,y\right\rangle-f^{*}(y)\leq f_{C}(x)$. Hence, $f_{C}(x)=f(x)$ and
$y\in\operatorname{Arg}_{C}(x)\subset\partial f_{C}(x)$.

Conversely, let $f_{C}(x)=f(x)$. For every $y\in\partial f_{C}(x)\cap C$, we
have that $f(x)=f_{C}(x)=\left\langle x,y\right\rangle-f^{*}(y)$ and then that
$y\in\partial f(x)\cap C$.

Finally, being a convex function, $f_{C}$ is differentiable at $x$ if and and
only if $\partial f_{C}(x)$ is a singleton. In this case, $\partial
f_{C}(x)=\left\\{{\nabla f_{C}(x)}\right\\}$. ∎

###### Proof of Theorem 2.2.

Hereafter, $i=1,2$. We assume that $\Sigma_{C_{1},C_{2}}(\partial
f)\not=\emptyset$ as otherwise, there is nothing to prove. This implies that
$C_{i}\cap\operatorname{dom}{f^{*}}\not=\emptyset$. Let $C:=C_{1}\cup C_{2}$.
Lemma 2.3 yields that

$\Sigma_{C_{1},C_{2}}(\partial f)=\Sigma_{C_{1},C_{2}}(\partial
f_{C})\cap\left\\{{x\in\real{d}}|\;f(x)=f_{C}(x)\right\\}.$ (5)

To simplify notations we assume that $j=1$. Denote by

$a:=\max_{y\in C_{1}}{y}^{1}<\min_{y\in C_{2}}{y}^{1}:=b.$

We write $x\in\real{d}$ as $(t,u)$, where $t\in\real{}$ and $u\in\real{d-1}$,
and define the saddle function

$g(t,u):=\inf_{s\in\real{}}\left({f_{C}(s,u)-st}\right),\quad
a<t<b,u\in\real{d-1}.$

Select $y_{i}=(q_{i},z_{i})\in C_{i}\cap\operatorname{dom}{f^{*}}$. We have
that

$\displaystyle f_{C}(s,u)$
$\displaystyle\geq\max_{i=1,2}\left({sq_{i}+\left\langle
u,z_{i}\right\rangle-f^{*}(y_{i})}\right).$

Since $q_{1}\leq a<b\leq q_{2}$, it follows from the definition of $g$ that

$-\infty<g(t,u)\leq f_{C}(0,u),\quad a<t<b,u\in\real{d-1}.$

By Lemma 2.3, $f_{C}$ has linear growth. The classical results on saddle
functions, Theorems 33.1 and 37.5 in [19], imply that

  1. (i)

For every $a<t<b$, the function $g(t,\cdot)$ is convex and has linear growth
on $\real{d-1}$.

  2. (ii)

For every $u\in\real{d-1}$, the function $g(\cdot,u)$ is concave and finite on
$(a,b)$.

  3. (iii)

For any $a<t<b$, we have that $(t,v)\in\partial f_{C}(s,u)$ if and only if
$v\in\partial_{u}g(t,u)$ and $-s\in\partial_{t}g(t,u)$. In this case,
$g(t,u)=f_{C}(s,u)-st$.

We take $a<r_{1}<r_{2}<b$ and denote $g_{i}:=g(r_{i},\cdot)$. We verify the
assertions of the theorem for the function

$h(s,u):=s+\frac{1}{r_{2}-r_{1}}\left({g_{2}(u)-g_{1}(u)}\right),\quad
s\in\real{},u\in\real{d}.$

More precisely, we show that

$\Sigma_{C_{1},C_{2}}(\partial
f_{C})=\left\\{{x\in\real{d}}|\;h(x)=0\right\\},$

which together with (5) implies the result.

Let $x=(s,u)$ and $(t_{i},v_{i})\in\partial f_{C}(x)\cap C_{i}$. As $t_{1}\leq
a<r_{i}<b\leq t_{2}$, the convexity of subdifferentials yields that
$(r_{i},w_{i})\in\partial f_{C}(x)$, where

$w_{i}=\frac{t_{2}-r_{i}}{t_{2}-t_{1}}v_{1}+\frac{r_{i}-t_{1}}{t_{2}-t_{1}}v_{2}.$
(6)

By (iii), $g_{i}(u)=f_{C}(x)-sr_{i}$ and then $h(x)=0$.

Conversely, let $x=(s,u)$ be such that $h(x)=0$ or, equivalently,

$-s=\frac{g_{2}(u)-g_{1}(u)}{r_{2}-r_{1}}=\frac{g(r_{2},u)-g(r_{1},u)}{r_{2}-r_{1}}.$

The mean-value theorem yields $r\in[r_{1},r_{2}]$ such that
$-s\in\partial_{t}g(r,u)$. Observe that $a<r<b$. Taking any
$w\in\partial_{u}g(r,u)$, we deduce from (iii) that $y:=(r,w)\in\partial
f_{C}(x)$. As $\partial f_{C}=\operatorname*{conv}\left({\partial f_{C}\cap
C}\right)$, the point $y$ is a convex combination of some $y_{i}\in\partial
f_{C}(x)\cap C_{i}$, $i=1,2$. In particular,
$x\in\Sigma_{C_{1},C_{2}}(\partial f_{C})$.

Finally, let $x=(s,u)$ be such that $h(x)=0$ and $g_{1}$ and $g_{2}$ are
differentiable at $u$. As we have already shown, the gradients $w_{i}:=\nabla
g_{i}(u)$ are given by (6) for some $(t_{i},v_{i})\in\partial f_{C}(x)\cap
C_{i}$. It follows that

$\nabla
h(x)=\left({1,\frac{w_{2}-w_{1}}{r_{2}-r_{1}}}\right)=\left({1,\frac{v_{2}-v_{1}}{t_{2}-t_{1}}}\right)\in\theta^{1}(C_{2}-C_{1}).$

Hence, $h\in\mathcal{H}^{1}_{\theta^{1}(C_{2}-C_{1})}$. ∎

##  3 Singular points of convex functions

For a multi-function $\Psi:\;\real{d}\rightrightarrows\real{d}$ taking values
in closed subsets of $\real{d}$, we denote its domain by

$\operatorname{dom}\Psi:=\left\\{{x\in\real{d}}|\;\Psi(x)\not=\emptyset\right\\}.$

Given an index $j\in\left\\{{1,\dots,d}\right\\}$ and a closed set $A$ in
$\real{d}$, the _singular_ set of $\Psi$ is defined as

$\displaystyle\Sigma^{j}_{A}(\Psi):=\left\\{{x\in\operatorname{dom}\Psi}|\;\exists
y_{1},y_{2}\in\Psi(x)\cap A\text{ with }y_{1}^{j}\not=y_{2}^{j}\right\\}.$

We also write $\Sigma^{j}(\Psi)=\Sigma^{j}_{\real{d}}(\Psi)$ and
$\Sigma(\Psi)=\cup_{j=1,\dots,d}\Sigma^{j}(\Psi)$.

Let $f:\;\real{d}\rightarrow\mathbb{R}\cup\left\\{{+\infty}\right\\}$ be a
closed convex function such that its domain has a non-empty interior:

$D:=\operatorname*{int}\operatorname{dom}f\not=\emptyset.$

It is well-known that $\operatorname{dom}\nabla f:=\left\\{{x\in D}|\;\nabla
f(x)\text{~{}exists}\right\\}$ is dense in $D$ and

$D\setminus\operatorname{dom}\nabla f=\Sigma(\partial f)\cap D=\left\\{{x\in
D}|\;\partial f(x)\text{ is not a point}\right\\}.$

According to [24], see also [2] and [13], this set of _interior_ singularities
can be covered by countable $c-c$ surfaces
$H_{n}=\left\\{{x\in\real{d}}|\;h_{n}(x)=0\right\\}$, $n\geq 1$, where

$h_{n}(x)=x^{j}+g_{n,1}(x^{-j})-g_{n,2}(x^{-j}),\quad x\in\real{d},$

for some $j\in\left\\{{1,\dots,d}\right\\}$ and finite convex functions
$g_{n,1}$ and $g_{n,2}$ on $\real{d-1}$.

Theorem 3.1 and Lemma 2.1 describe the _orientation_ of the covering surface
$H_{n}$ by showing that, at any point, it has a normal vector $w$ with
$w^{j}=1$, that belongs to the cone $K$ generated by $F-F$, where

$F:=\operatorname*{cl}\operatorname*{range}\nabla f=\left\\{{\lim_{n}\nabla
f(x_{n})}|\;x_{n}\in\operatorname{dom}\nabla f\right\\}.$

Of course, this information has some value only if $K$ is distinctively
smaller than $\real{d}$. This is the case for Fitzpatrick functions in the
pseudo-Euclidean space $S$, where according to Theorem 4.5, $K$ contains only
$S$-non-negative vectors. Proposition 3.5 provides the geometric
interpretation of the $\operatorname*{range}\nabla f$ and Lemma 3.3 explains
the special feature of its closure $F$.

It turns out that the same surfaces $(H_{n})$ also cover the singularities of
the Clarke-type subdifferential $\overline{\partial}f$ defined on the
_closure_ of $D$:

$\overline{\partial}f(x):=\operatorname*{cl}\operatorname*{conv}\left\\{{\lim_{n}\nabla
f(x_{n})}|\;\operatorname{dom}\nabla f\ni x_{n}\to x\right\\},\quad
x\in\operatorname*{cl}D.$

By Theorem 25.6 in [19],

$\partial f(x)=\overline{\partial}f(x)+N_{\operatorname*{cl}D}(x),\quad
x\in\operatorname*{cl}D,$

where $N_{A}(x)$ denotes the normal cone to a closed convex set
$A\subset\real{d}$ at $x\in A$:

$\displaystyle N_{A}(x):=$ $\displaystyle\left\\{{s\in\real{d}}|\;\left\langle
s,y-x\right\rangle\leq 0\text{ for all }y\in A\right\\}$ $\displaystyle=$
$\displaystyle\left\\{{s\in\real{d}}|\;s\text{ is a regular normal vector to
}A\text{ at }x\right\\}.$

Recalling that $0\in N_{A}(x)$ for $x\in A$ and
$N_{A}(x)=\left\\{{0}\right\\}$ for $x\in\operatorname*{int}{A}$, we deduce
that

$\displaystyle\operatorname{dom}{\overline{\partial}f}$
$\displaystyle=\operatorname{dom}{\partial f},$ (7)
$\displaystyle\overline{\partial}f(x)$ $\displaystyle\subset\partial
f(x),\quad x\in\operatorname*{cl}D,$ (8)
$\displaystyle\overline{\partial}f(x)$ $\displaystyle=\partial f(x),\quad x\in
D.$ (9)

The diameter of a set $E$ is denoted by $\operatorname{diam}{E}:=\sup_{x,y\in
E}\left\lvert x-y\right\rvert$.

######  Theorem 3.1.

Let $f:\;\real{d}\rightarrow\mathbb{R}\cup\left\\{{+\infty}\right\\}$ be a
closed convex function with
$D:=\operatorname*{int}\operatorname{dom}f\not=\emptyset$. Let
$j\in\left\\{{1,\dots,d}\right\\}$ and $A$ be a closed set in $\real{d}$
containing $\operatorname*{range}\nabla f$. Then

$\displaystyle\Sigma^{j}(\partial f)\cap
D=\Sigma^{j}(\overline{\partial}f)\cap D=\Sigma^{j}_{A}(\partial f)\cap D,$
(10)
$\displaystyle\Sigma^{j}(\overline{\partial}f)\subset\Sigma^{j}_{A}(\partial
f).$ (11)

If $y^{j}=z^{j}$ for all $y,z\in A$, then, clearly, $\Sigma_{A}^{j}(\partial
f)=\emptyset$. Otherwise, for every $n\geq 1$, there exist a compact set
$C_{n}\subset A-A$ with $y^{j}>0$, $y\in C_{n}$, and a function
$h_{n}\in\mathcal{H}^{j}_{\theta^{j}(C_{n})}$ such that

$\Sigma_{A}^{j}(\partial
f)\subset\bigcup_{n}\left\\{{x\in\real{d}}|\;h_{n}(x)=0\right\\}.$ (12)

For any $\epsilon>0$, all $C_{n}$ can be chosen so that
$\operatorname{diam}{\theta^{j}(C_{n})}<\epsilon$.

Taking the unions over $j\in\left\\{{1,\dots,d}\right\\}$, we obtain the
descriptions of the _full_ singular sets $\Sigma(\partial f)$ on $D$,
$\Sigma(\overline{\partial}f)$, and $\Sigma_{A}(\partial f)$. Taking a smaller
$\epsilon>0$ in the last sentence of the theorem, we make the directions of
the normal vectors to the covering surface $H_{n}$ closer to each other. As a
result, $H_{n}$ gets approximated by a hyperplane.

Theorem 3.1 uses a larger closed set $A$ instead of $F$ to allow for more
flexibility in the treatment of singularities of $\partial f$ on the boundary
of $D$. Lemma 3.4 shows that

$\partial f(x)\cap A=\operatorname{Arg}_{A}(x):=\operatorname*{arg\>max}_{y\in
A}\left({\left\langle x,y\right\rangle-f^{*}(y)}\right),\quad
x\in\operatorname*{cl}D.$

In the framework of Fitzpatrick functions in Section 4,
$\operatorname{Arg}_{A}$ becomes a projection on the monotone set $A$ in a
pseudo-Euclidean space.

The proof of Theorem 3.1 relies on some lemmas. We start with a simple fact
from convex analysis.

######  Lemma 3.2.

Let $f:\;\real{d}\rightarrow\mathbb{R}\cup\left\\{{+\infty}\right\\}$ be a
closed convex function attaining a strict minimum at a point $x_{0}$:

$f(x_{0})<f(x),\quad x\in\real{d},\,x\not=x_{0}.$

Then

$f(x_{0})<\inf_{\left\lvert
x-x_{0}\right\rvert\geq\epsilon}f(x),\quad\epsilon>0.$

###### Proof.

If the conclusion is not true, then there exist $\epsilon>0$ and a sequence
$(x_{n})$ with $|x_{n}-x_{0}|\geq\epsilon$ such that $f(x_{n})\rightarrow
f(x_{0})$. As

$z_{n}:=x_{0}+\frac{\epsilon}{\left\lvert
x_{n}-x_{0}\right\rvert}(x_{n}-x_{0})$

is a convex combination of $x_{0}$ and $x_{n}$, we deduce that

$f(z_{n})\leq\max(f(x_{0}),f(x_{n}))=f(x_{n})\to f(x_{0}).$

By compactness, $z_{n}\rightarrow z_{0}$ over a subsequence. Clearly,
$\left\lvert z_{0}-x_{0}\right\rvert=\epsilon$, while by the lower semi-
continuity, $f(z_{0})\leq\liminf f(z_{n})\leq f(x_{0})$. We have arrived to a
contradiction. ∎

The following result explains the special role played by
$\operatorname*{cl}\operatorname*{range}\nabla f$. Recall the notation $f_{A}$
from (3).

######  Lemma 3.3.

Let $f:\;\real{d}\rightarrow\mathbb{R}\cup\left\\{{+\infty}\right\\}$ be a
closed convex function with
$D:=\operatorname*{int}\operatorname{dom}f\not=\emptyset$ and $A$ be a closed
set in $\real{d}$. Then

$f_{A}(x)=f(x),\,x\in\operatorname*{cl}D\iff\operatorname*{range}\nabla
f\subset A.$

In other words, $F:=\operatorname*{cl}\operatorname*{range}\nabla f$ is the
minimal closed set such that $f_{F}=f$ on $\operatorname*{cl}D$.

###### Proof.

$\impliedby$: If $x\in\operatorname{dom}\nabla f$, then $y:=\nabla f(x)\in A$
and (4) yields that

$f(x)=\left\langle x,y\right\rangle-f^{*}(y)=f_{A}(x).$

Since $\operatorname{dom}{\nabla f}$ is dense in $D$, the closed convex
functions $f_{A}$ and $f$ coincide on $\operatorname*{cl}D$.

$\implies$: We fix $x_{0}\in\operatorname{dom}\nabla f$ and set $y_{0}:=\nabla
f(x_{0})$. By the assumption, $f_{A}(x_{0})=f(x_{0})$. If $y_{0}\notin A$,
then the distance between $y_{0}$ and $A$ is at least $\epsilon>0$. According
to (4), the concave upper semi-continuous function

$y\rightarrow\left\langle x_{0},y\right\rangle-f^{*}(y)$

attains a strict global maximum at $y_{0}$ and has the maximum value
$f(x_{0})$. By Lemma 3.2,

$\sup_{\left\lvert y-y_{0}\right\rvert\geq\epsilon}\left({\left\langle
x_{0},y\right\rangle-f^{*}(y)}\right)<f(x_{0}).$

As $A\subset\left\\{{y\in\real{d}}|\;|y-y_{0}|\geq\epsilon\right\\}$, we
arrive to a contradiction:

$f_{A}(x_{0})=\sup_{y\in A}\left({\left\langle
x_{0},y\right\rangle-f^{*}(y)}\right)\leq\sup_{\left\lvert
y-y_{0}\right\rvert\geq\epsilon}\left({\left\langle
x_{0},y\right\rangle-f^{*}(y)}\right)<f(x_{0}).$

Hence, $y_{0}\in A$, as required. ∎

######  Lemma 3.4.

Let $f:\;\real{d}\rightarrow\mathbb{R}\cup\left\\{{+\infty}\right\\}$ be a
closed convex function with
$D:=\operatorname*{int}\operatorname{dom}f\not=\emptyset$. Let $A$ be a closed
set in $\real{d}$ such that $f=f_{A}$ on $\operatorname*{cl}D$. Then

$\displaystyle\partial f(x)\cap
A=\operatorname{Arg}_{A}(x):=\operatorname*{arg\>max}_{y\in
A}\left({\left\langle x,y\right\rangle-f^{*}(y)}\right),\quad
x\in\operatorname*{cl}D,$
$\displaystyle\operatorname{dom}\operatorname{Arg}_{A}\cap\operatorname*{cl}D=\operatorname{dom}\partial
f=\operatorname{dom}\overline{\partial}f,$
$\displaystyle\overline{\partial}f(x)=\partial
f(x)=\operatorname*{conv}{\left({\partial f(x)\cap A}\right)},\quad x\in D,$
$\displaystyle\overline{\partial}f(x)\subset\operatorname*{cl}\operatorname*{conv}\left({\partial
f(x)\cap A}\right),\quad x\in\operatorname{dom}\overline{\partial}f.$

###### Proof.

If $x\in\operatorname{dom}\operatorname{Arg}_{A}\cap\operatorname*{cl}D$ and
$y\in\operatorname{Arg}_{A}(x)$, then

$f(x)=f_{A}(x)=\left\langle x,y\right\rangle-f^{*}(y).$ (13)

Hence, $y\in\partial f(x)\cap A$, by the properties of subdifferentials in
(4).

Conversely, let $x\in\operatorname{dom}\partial f$. Lemma 3.3 shows that
$F:=\operatorname*{cl}\operatorname*{range}\nabla f\subset A$. Accounting for
(7) and (8) and the definition of $\overline{\partial}f(x)$, we obtain that

$\partial f(x)\cap A\supset\partial f(x)\cap
F\supset\overline{\partial}f(x)\cap F\not=\emptyset.$

Let $y\in\partial f(x)\cap A$. From (4) we deduce (13) and then that
$y\in\operatorname{Arg}_{A}(x)$. We have proved the first two assertions of
the lemma.

The fact that $\overline{\partial}f=\partial f$ on $D$ has been already stated
in (9). To prove the second equality in the third assertion, we fix $x_{0}\in
D$ and choose $\epsilon>0$ such that

$B(x_{0},\epsilon):=\left\\{{x\in\real{d}}|\;\left\lvert
x-x_{0}\right\rvert\leq\epsilon\right\\}\subset D.$

The uniform boundedness of $\partial f$ on compacts in $D$ implies the
existence of a constant $K>0$ such that

$\left\lvert y\right\rvert\leq K<\infty,\quad y\in\partial f(x),\,x\in
B(x_{0},\epsilon).$

Denote by $A_{K}:=A\cap\left\\{{x\in\real{d}}|\;\left\lvert x\right\rvert\leq
K\right\\}$. As $\operatorname*{range}\nabla f\subset A$, we deduce from (4)
that

$f(x)=f_{A_{K}}(x),\quad x\in B(x_{0},\epsilon)\cap\operatorname{dom}\nabla
f,$

and then, by the density of $\operatorname{dom}\nabla f$ in $D$, that
$f=f_{A_{K}}$ on $B(x_{0},\epsilon)$. Finally, Lemma 2.3 shows that

$\partial f(x_{0})=\partial
f_{A_{K}}(x_{0})=\operatorname*{conv}\left({\partial f_{A_{K}}(x_{0})\cap
A_{K}}\right)=\operatorname*{conv}\left({\partial f(x_{0})\cap A}\right).$

If $\operatorname{dom}\nabla f\ni x_{n}\to x$ and $\nabla f(x_{n})\to y$,
then, clearly, $y\in F\subset A$. Moreover, $y\in\partial f(x)$, by the
continuity of subdifferentials. The last assertion of the lemma readily
follows. ∎

We are ready to finish the proof of Theorem 3.1.

###### Proof of Theorem 3.1.

Lemma 3.3 shows that $f=f_{A}$ on $\operatorname*{cl}D$. Then, by Lemma 3.4,

$\displaystyle\overline{\partial}f(x)=\partial
f(x)=\operatorname*{conv}{\left({\partial f(x)\cap A}\right)},\quad x\in D,$
$\displaystyle\overline{\partial}f(x)\subset\operatorname*{cl}\operatorname*{conv}\left({\partial
f(x)\cap A}\right),\quad x\in\operatorname{dom}\overline{\partial}f.$

Recalling that $\operatorname{dom}{\partial
f}=\operatorname{dom}{\overline{\partial}f}$, we deduce (10) and (11).

Fix $\epsilon>0$. Let $(x_{n})$ be a dense sequence in $A$ and $(r_{n})$ be an
enumeration of all positive rationals. Denote by $\alpha:=(m,n,k,l)$ the
indexes for which the compacts

$C^{\alpha}_{1}:=\left\\{{x\in A}|\;|x-x_{m}|\leq r_{k}\right\\},\quad
C^{\alpha}_{2}:=\left\\{{x\in A}|\;|x-x_{n}|\leq r_{l}\right\\},$

satisfy the constraints:

$\operatorname{diam}\theta^{j}(C^{\alpha}_{2}-C^{\alpha}_{1})<\epsilon\text{~{}and~{}}x^{j}>0,\;x\in
C_{2}^{\alpha}-C_{1}^{\alpha}.$

We have that

$\Sigma^{j}_{A}(\partial
f)=\bigcup_{\alpha}\Sigma_{C^{\alpha}_{1},C^{\alpha}_{2}}(\partial
f)=\bigcup_{\alpha}\left\\{{x\in\real{d}}|\;\partial f(x)\cap
C^{\alpha}_{i}\not=\emptyset,\,i=1,2\right\\}.$

For every index $\alpha$, Theorem 2.2 yields a function
$h\in\mathcal{H}^{j}_{\theta^{j}(C^{\alpha}_{2}-C^{\alpha}_{1})}$ such that

$\Sigma_{C^{\alpha}_{1},C^{\alpha}_{2}}(\partial
f)\subset\left\\{{x\in\real{d}}|\;h(x)=0\right\\}.$

We have proved (12) and with it the theorem. ∎

We conclude the section with the geometric interpretation of
$\operatorname*{range}\nabla f$. For a closed convex function
$f:\;\real{d}\rightarrow\mathbb{R}\cup\left\\{{+\infty}\right\\}$, we denote
by $\operatorname{epi}f$ its epigraph:

$\operatorname{epi}f:=\left\\{{(x,q)\in\real{d}\times\real{}}|\;f(x)\leq
q\right\\}.$

Let $E$ be a closed convex set in $\real{d}$. A point $x_{0}\in E$ is called
_exposed_ if there is a hyperplane intersecting $E$ only at $x_{0}$. In other
words, there is $y_{0}\in\real{d}$ such that

$\left\langle x-x_{0},y_{0}\right\rangle>0,\quad x\in
E\setminus\left\\{{x_{0}}\right\\}.$

######  Proposition 3.5.

Let $f:\;\real{d}\rightarrow\mathbb{R}\cup\left\\{{+\infty}\right\\}$ be a
closed convex function with
$\operatorname*{int}{\operatorname{dom}f}\not=\emptyset$. Then

$\left\\{{\left({y,f^{*}(y)}\right)}|\;y\in\operatorname*{range}\nabla
f\right\\}=\text{ exposed points of }\operatorname{epi}f^{*}.$

###### Proof.

By definition, $(y_{0},r_{0})$ is an exposed point of
$\operatorname{epi}f^{*}$ if it belongs to $\operatorname{epi}f^{*}$ and

$\left\langle
y-y_{0},x_{0}\right\rangle+(r-r_{0})q_{0}>0,\quad(y,r)\in\operatorname{epi}f^{*}\setminus\left\\{{(y_{0},r_{0})}\right\\},$

for some $(x_{0},q_{0})\in\real{d}\times\real{}$. The definition of
$\operatorname{epi}f^{*}$ ensures that $q_{0}>0$ and $r_{0}=f^{*}(y_{0})$.
Rescaling $(x_{0},q_{0})$ so that $q_{0}=1$, we deduce that the function

${y}\to{\left\langle x_{0},y\right\rangle+f^{*}(y)}$

has the unique minimizer $y_{0}$. This is equivalent to $y_{0}$ being the only
element of $\partial f(-x_{0})$, which in turn is equivalent to
$-x_{0}\in\operatorname{dom}\nabla f$ and $y_{0}=\nabla f(-x_{0})$. ∎

##  4 Singular points of projections in $S$-spaces

We denote by $\mathcal{S}^{d}_{m}$ the family of symmetric $d\times
d$-matrices of full rank with $m\in\left\\{{0,1,\dots,d}\right\\}$ positive
eigenvalues. For $S\in\mathcal{S}^{d}_{m}$, the bilinear form

$S(x,y):=\left\langle x,Sy\right\rangle=\sum_{i,j=1}^{d}x^{i}S_{ij}y^{j},\quad
x,y\in\real{d},$

defines the scalar product on a pseudo-Euclidean space $\real{d}_{m}$ with
dimension $d$ and index $m$, which we call the $S$-space. The quadratic form
$S(x,x)$ is the _scalar square_ on the $S$-space; its value may be negative.

For a closed set $G\subset\real{d}$, we define the _Fitzpatrick-type_ function

$\psi_{G}(x):=\sup_{y\in
G}\left({S(x,y)-\frac{1}{2}S(y,y)}\right)\in\mathbb{R}\cup\left\\{{+\infty}\right\\},\quad
x\in\real{d},$

and the projection multi-function

$\displaystyle P_{G}(x):=$ $\displaystyle\operatorname*{arg\>min}_{y\in
G}S(x-y,x-y)=\operatorname*{arg\>max}_{y\in
G}\left({S(x,y)-\frac{1}{2}S(y,y)}\right),\quad x\in\real{d}.$

Clearly, $\psi_{G}$ is a closed convex function and $P_{G}$ takes values in
the closed (possibly empty) subsets of $G$.

A closed set $G\subset\real{d}$ is called $S$-_monotone_ or $S$-_positive_ if

$S(x-y,x-y)\geq 0,\quad x,y\in G,$

or, equivalently, if its projection multi-function has the natural fixed-point
property:

$x\in P_{G}(x),\quad x\in G.$

We denote by $\mathcal{M}(S)$ the family of closed non-empty $S$-monotone sets
in $\real{d}$. We refer to Fitzpatrick [10], Simons [21], and Penot [18] for
the results on Fitzpatrick functions $\psi_{G}$ associated with
$G\in\mathcal{M}(S)$.

######  Example 4.1 (Standard form).

If $d=2m$ and

$S(x,y)=\sum_{i=1}^{m}\left({x^{i}y^{m+i}+x^{m+i}y^{i}}\right),\quad
x,y\in\real{2m},$

then $S\in\mathcal{S}^{2m}_{m}$ and the $S$-monotonicity means the standard
monotonicity in $\real{2m}=\real{m}\times\real{m}$. For a _maximal_ monotone
set $G$, the function $\psi_{G}$ becomes the classical Fitzpatrick function
from [10].

######  Example 4.2 (Canonical form).

If $\Lambda$ is the _canonical_ quadratic form in $\mathcal{S}^{d}_{m}$:

$\Lambda(x,y)=\sum_{i=1}^{m}x^{i}y^{i}-\sum_{i=m+1}^{d}x^{i}y^{i},\quad
x,y\in\real{d},$

then a closed set $G$ is $\Lambda$-monotone if and only if

$G=\operatorname{graph}{f}:=\left\\{{(u,f(u))}|\;u\in D\right\\},$

where $D$ is a closed set in $\real{m}$ and $f:\;D\rightarrow\real{d-m}$ is a
$1$-Lipschitz function:

$\left\lvert f(u)-f(v)\right\rvert\leq\left\lvert u-v\right\rvert,\quad u,v\in
D.$

In view of the Kirszbraun Theorem, [9, 2.10.43], $G$ is maximal
$\Lambda$-monotone if and only if $D=\real{m}$.

While working on the $S$-space, it is convenient to use appropriate versions
of subdifferential and Clark-type subdifferential for a convex function $f$.
For $x\in\operatorname*{cl}{\operatorname{dom}{f}}$, they are defined as

$\displaystyle\partial^{S}f(x):=$ $\displaystyle\left\\{{y\in\real
d}|\;S(z,y)\leq f(x+z)-f(x),\,z\in\real{d}\right\\}$ $\displaystyle=$
$\displaystyle\left\\{{S^{-1}y\in\real d}|\;\left\langle z,y\right\rangle\leq
f(x+z)-f(x),\,z\in\real{d}\right\\}$ $\displaystyle=$
$\displaystyle\;S^{-1}\partial f(x),$
$\displaystyle\overline{\partial}^{S}f(x):=$ $\displaystyle
S^{-1}\overline{\partial}f(x).$

######  Lemma 4.3.

Let $S\in\mathcal{S}^{d}_{m}$, $G\in\mathcal{M}(S)$, and assume that
$D:=\operatorname*{int}\operatorname{dom}{\psi_{G}}\not=\emptyset$. Then

$\displaystyle\operatorname*{range}{S^{-1}\nabla\psi_{G}}\subset G,$
$\displaystyle\operatorname{dom}{P_{G}}=\operatorname{dom}{\partial^{S}\psi_{G}}=\operatorname{dom}{\overline{\partial}^{S}\psi_{G}},$

and

$\displaystyle\psi_{G}(x)=\psi_{G}^{*}(Sx)=\frac{1}{2}S(x,x),\quad x\in G,$
$\displaystyle P_{G}(x)=\partial^{S}\psi_{G}(x)\cap G,\quad x\in\real{d}.$

###### Proof.

We write $\psi_{G}$ as

$\psi_{G}(x)=g^{*}(x):=\sup_{y\in\real{d}}(\left\langle
x,y\right\rangle-g(y)),\quad x\in\real{d},$

where $g(y)=\frac{1}{2}S^{-1}(y,y)$ for $y\in SG$ and $g(y)=+\infty$ for
$y\not\in SG$. From the definition of $\psi_{G}$ and the $S$-monotonicity of
$G$ we deduce that

$\psi_{G}(x)=\frac{1}{2}S(x,x)-\frac{1}{2}\inf_{y\in
G}S(x-y,x-y)=\frac{1}{2}S(x,x),\quad x\in G,$

and then that

$\psi_{G}(S^{-1}x)\leq g(x),\quad x\in\real{d}.$

As $\psi^{*}_{G}=g^{**}$ and $g^{**}$ is the largest closed convex function
less than $g$, we have that

$\psi_{G}(S^{-1}x)\leq\psi^{*}_{G}(x)\leq g(x),\quad x\in\real{d}.$

Putting together the relations above, we obtain that

$\frac{1}{2}S(x,x)=\psi_{G}(x)\leq\psi^{*}_{G}(Sx)\leq
g(Sx)=\frac{1}{2}S(x,x),\quad x\in G.$

For every $x\in\real{d}$, the values of the Fitzpatrick function $\psi_{G}$
and of the projection multi-function $P_{G}$ can now be written as

$\displaystyle\psi_{G}(x)$ $\displaystyle=\sup_{y\in
G}\left({S(x,y)-\psi_{G}^{*}(Sy)}\right)=\sup_{z\in SG}\left({\left\langle
x,z\right\rangle-\psi_{G}^{*}(z)}\right),$ $\displaystyle P_{G}(x)$
$\displaystyle=\operatorname*{arg\>max}_{y\in
G}\left({S(x,y)-\frac{1}{2}S(y,y)}\right)=S^{-1}\operatorname*{arg\>max}_{z\in
SG}\left({\left\langle x,z\right\rangle-\psi^{*}_{G}(z)}\right).$

The stated relations between $P_{G}$ and $\partial^{S}\psi_{G}$ follow from
Lemma 3.4 as soon as we observe that
$P_{G}(x)=\partial^{S}\psi_{G}(x)=\emptyset$ for $x\notin\operatorname*{cl}D$.
The equality of the domains of $\partial^{S}\psi_{G}$ and
$\overline{\partial}^{S}\psi_{G}$ is just a restatement of (7). Finally, Lemma
3.3 yields the inclusion of $\operatorname*{range}\nabla\psi_{G}$ into $SG$. ∎

To facilitate geometric interpretations, we also adapt the concept of a normal
vector to the product structure of the $S$-space. Let $H$ be a closed set in
$\real{d}$. A vector $w\in\real{d}$ is called $S$-_regular normal to $H$ at
$x\in H$_ if

$\limsup_{\begin{subarray}{c}H\ni y\to x\\\
y\not=x\end{subarray}}\frac{S(w,y-x)}{\left\lvert
y-x\right\rvert}=\limsup_{\begin{subarray}{c}H\ni y\to x\\\
y\not=x\end{subarray}}\frac{\left\langle Sw,y-x\right\rangle}{\left\lvert
y-x\right\rvert}\leq 0.$

A vector $w\in\real{d}$ is called $S$-_normal to $H$ at $x$_ if there exist
$x_{n}\in H$ and an $S$-regular normal vector $w_{n}$ to $H$ at $x_{n}$, such
that $x_{n}\rightarrow x$ and $w_{n}\rightarrow w$. In other words, $w$ is
$S$-(regular) normal to $H$ at $x\in H$ if $Sw$ is (regular) normal to $H$ at
$x$ in the classical Euclidean sense. It is easy to see that if $x\in
P_{H}(z)$, then the vector $z-x$ is $S$-regular normal to $H$ at $x$.

######  Lemma 4.4.

Let $S\in\mathcal{S}^{d}_{m}$, $j\in\left\\{{1,\dots,d}\right\\}$,
$C\in\mathcal{C}^{j}$, $h$ be given by (1) for convex functions $g_{1}$ and
$g_{2}$ with linear growth, and $H$ be the zero-level set of the composition
function $h\circ S$:

$H:=\left\\{{x\in\real{d}}|\;h(Sx)=0\right\\}.$

Then $h\in\mathcal{H}^{j}_{C}$ if and only if for every $x\in H$, there exists
an $S$-normal vector $w\in C$ to $H$ at $x$.

###### Proof.

Let $z\in H$ and $w\in\real{d}$. Setting

$SH:=\left\\{{Sx}|\;x\in H\right\\}=\left\\{{x\in\real{d}}|\;h(x)=0\right\\},$

recalling that $S(w,y-z)=\left\langle w,Sy-Sz\right\rangle$, and using the
trivial inequalities:

$\frac{1}{\lVert S^{-1}\rVert}\left\lvert y-z\right\rvert\leq\left\lvert Sy-
Sz\right\rvert\leq\lVert S\rVert\left\lvert y-z\right\rvert,\quad
y\in\real{d},$

where $\lVert A\rVert:=\max_{\left\lvert x\right\rvert=1}\left\lvert
Ax\right\rvert$ for a $d\times d$ matrix $A$, we deduce that $w$ is normal to
$SH$ at $Sz$ if and only if $w$ is $S$-normal to $H$ at $z$. Lemma 2.1 yields
the result. ∎

Theorem 4.5 and Lemma 4.4 show that the singular sets $\Sigma^{j}(P_{G})$ and
$\Sigma^{j}(\overline{\partial}^{S}\psi_{G})$ can be covered by countable
$c-c$ surfaces that have at each point an $S$-normal vector $w\in G-G$, with
$w^{j}=1$. By the $S$-monotonicity of $G$, such vector $w$ points to the _non-
negative_ direction in the $S$-space: $S(w,w)\geq 0$.

######  Theorem 4.5.

Let $S\in\mathcal{S}^{d}_{m}$, $G\in\mathcal{M}(S)$,
$j\in\left\\{{1,\dots,d}\right\\}$, and assume that
$D:=\operatorname*{int}{\operatorname{dom}{\psi_{G}}}\not=\emptyset$. For
every $n\geq 1$, there exist a compact set $C_{n}\subset G-G$ and a function
$h_{n}\in\mathcal{H}^{j}_{\theta^{j}(C_{n})}$ such that

$\Sigma^{j}(\overline{\partial}^{S}\psi_{G})\subset\Sigma^{j}(P_{G})\subset\bigcup_{n}\left\\{{x\in\real{d}}|\;h_{n}(Sx)=0\right\\}.$

For any $\epsilon>0$, all $C_{n}$ can be chosen such that
$\operatorname{diam}{\theta^{j}(C_{n})}<\epsilon$.

###### Proof.

Let $g(x):=\psi_{G}(S^{-1}x)$, $x\in\real{d}$. Clearly,

$\overline{\partial}^{S}\psi_{G}(x):=S^{-1}\overline{\partial}\psi_{G}(x)=\overline{\partial}g(Sx),\quad
x\in\real{d}.$

Lemma 4.3 shows that $S^{-1}\operatorname*{range}\nabla\psi_{G}\subset G$ and

$P_{G}(x)=\partial^{S}\psi_{G}(x)\cap
G=\left({S^{-1}\partial\psi_{G}(x)}\right)\cap G=\partial g(Sx)\cap G,\quad
x\in\real{d}.$

It follows that

$\displaystyle\Sigma^{j}(\overline{\partial}^{S}\psi_{G})=S^{-1}\Sigma^{j}(\overline{\partial}g),\quad\Sigma^{j}(P_{G})=S^{-1}\Sigma^{j}_{G}(\partial
g),$

and a direct application of Theorem 3.1 yields the result. ∎

A set $A\subset\real{d}$ is called $S$-_isotropic_ if

$S(x-y,x-y)=0,\quad x,y\in A.$

We denote by $\mathcal{I}(S)$ the family of all closed $S$-isotropic subsets
of $\real{d}$.

Motivated by the study of existence and uniqueness of backward martingale
transport maps in [16], we decompose the singular set of $P_{G}$ as

$\displaystyle\Sigma(P_{G})$
$\displaystyle:=\left\\{{x\in\operatorname{dom}{P_{G}}}|\;P_{G}(x)\text{~{}is
not a point}\right\\}=\Sigma_{0}(P_{G})\cup\Sigma_{1}(P_{G}),$
$\displaystyle\Sigma_{0}(P_{G})$
$\displaystyle:=\left\\{{x\in\Sigma(P_{G})}|\;P_{G}(x)\in\mathcal{I}(S)\right\\},$
$\displaystyle\Sigma_{1}(P_{G})$
$\displaystyle:=\left\\{{x\in\Sigma(P_{G})}|\;S(y_{1}-y_{2},y_{1}-y_{2})>0\text{~{}for
\emph{some}~{}}y_{1},y_{2}\in P_{G}(x)\right\\}.$

We further write $\Sigma_{1}(P_{G})$ as

$\Sigma_{1}(P_{G})=\bigcup_{j=1}^{d}\Sigma_{1}^{j}(P_{G}),$

where $\Sigma_{1}^{j}(P_{G})$ consists of $x\in\Sigma(P_{G})$ such that
$S(y_{1}-y_{2},y_{1}-y_{2})>0$ for some $y_{1},y_{2}\in P_{G}(x)$ with
$y_{1}^{j}\not=y_{2}^{j}$.

Theorem 4.6 and Lemma 4.4 show that $\Sigma^{j}_{1}(P_{G})$ can be covered by
countable $c-c$ surfaces that have at each point a strictly $S$-positive
$S$-normal vector $w$ with $w^{j}=1$.

######  Theorem 4.6.

Let $S\in\mathcal{S}^{d}_{m}$, $G\in\mathcal{M}(S)$,
$j\in\left\\{{1,\dots,d}\right\\}$, and assume that
$D:=\operatorname*{int}{\operatorname{dom}{\psi_{G}}}\not=\emptyset$. For
every $n\geq 1$, there exist a compact set $C_{n}\subset G-G$ with

$x^{j}>0\text{~{}and~{}}S(x,x)>0,\quad x\in C_{n},$

and a function $h_{n}\in\mathcal{H}^{j}_{\theta^{j}(C_{n})}$ such that

$\Sigma^{j}_{1}(P_{G})\subset\bigcup_{n}\left\\{{x\in\real{d}}|\;h_{n}(Sx)=0\right\\}.$

For any $\epsilon>0$, all $C_{n}$ can be chosen such that
$\operatorname{diam}{\theta^{j}(C_{n})}<\epsilon$.

###### Proof.

Fix $\epsilon>0$. Let $(x_{n})$ be a dense sequence in $G$ and $(r_{n})$ be an
enumeration of all positive rationals. Denote by $\alpha:=(m,n,k,l)$ the
indexes for which the compact sets

$C^{\alpha}_{1}:=\left\\{{x\in G}|\;|x-x_{m}|\leq r_{k}\right\\},\quad
C^{\alpha}_{2}:=\left\\{{x\in G}|\;|x-x_{n}|\leq r_{l}\right\\},$

satisfy the constraints:

$\operatorname{diam}\theta^{j}(C^{\alpha}_{2}-C^{\alpha}_{1})<\epsilon\text{~{}and~{}}x^{j}>0,\;S(x,x)>0,\;x\in
C_{2}^{\alpha}-C_{1}^{\alpha}.$

We have that

$\Sigma^{j}_{1}(P_{G})=\bigcup_{\alpha}\Sigma_{C^{\alpha}_{1},C^{\alpha}_{2}}(P_{G})=\bigcup_{\alpha}\left\\{{x\in\real{d}}|\;P_{G}(x)\cap
C^{\alpha}_{i}\not=\emptyset,\;i=1,2\right\\}.$

Let, again, $g(x):=\psi_{G}(S^{-1}x)$, $x\in\real{d}$. From Lemma 4.3 we
deduce that

$P_{G}(x)=\left({S^{-1}\partial\psi_{G}(x)}\right)\cap G=\partial g(Sx)\cap
G,\quad x\in\real{d}.$

It follows that

$x\in\Sigma_{C^{\alpha}_{1},C^{\alpha}_{2}}(P_{G})\iff
Sx\in\Sigma_{C^{\alpha}_{1},C^{\alpha}_{2}}(\partial g).$

Applying Theorem 2.2 to each singular set
$\Sigma_{C^{\alpha}_{1},C^{\alpha}_{2}}(\partial g)$, we obtain the result. ∎

The singular set $\Sigma_{0}(P_{G})$ is included into a larger set

$\overline{\Sigma}_{0}(P_{G})=\bigcup_{j=1}^{d}\overline{\Sigma}^{j}_{0}(P_{G}),$

where $\overline{\Sigma}^{j}_{0}(P_{G})$ consists of
$x\in\operatorname{dom}{P_{G}}$ such that $S(y_{1}-y_{2},y_{1}-y_{2})=0$ for
_some_ $y_{1},y_{2}\in P_{G}(x)$ with $y_{1}^{j}\not=y_{2}^{j}$.

Theorem 4.7 and Lemma 4.4 show that $\overline{\Sigma}_{0}^{j}(P_{G})$ can be
covered, for any $\delta>0$, by countable $c-c$ surfaces that have at each
point an $S$-normal vector $w$ such that $w^{j}=1$ and $0\leq
S(w,w)\leq\delta$.

######  Theorem 4.7.

Let $S\in\mathcal{S}^{d}_{m}$, $G\in\mathcal{M}(S)$,
$j\in\left\\{{1,\dots,d}\right\\}$, and assume that
$D:=\operatorname*{int}{\operatorname{dom}{\psi_{G}}}\not=\emptyset$. Let
$\delta>0$. For every $n\geq 1$, there exist a compact set $C_{n}\subset G-G$
with

$x^{j}>0,\;x\in C_{n},\text{~{}and~{}}0\leq
S(x,x)\leq\delta,\;x\in\theta^{j}(C_{n}),$

and a function $h_{n}\in\mathcal{H}^{j}_{\theta^{j}(C_{n})}$ such that

$\overline{\Sigma}^{j}_{0}(P_{G})\subset\bigcup_{n}\left\\{{x\in\real{d}}|\;h_{n}(Sx)=0\right\\}.$

For any $\epsilon>0$, all $C_{n}$ can be chosen such that
$\operatorname{diam}{\theta^{j}(C_{n})}<\epsilon$.

###### Proof.

The proof is almost identical to that of Theorem 4.6. We fix
$\delta,\epsilon>0$ and find a _countable_ family
$(C^{\alpha}_{1},C^{\alpha}_{2})$ of pairs of compact sets
$C^{\alpha}_{i}\subset G$, $i=1,2$, such that

$\displaystyle x^{j}>0,\;x\in
C_{2}^{\alpha}-C_{1}^{\alpha},\text{~{}and~{}}\operatorname{diam}\theta^{j}(C^{\alpha}_{2}-C^{\alpha}_{1})<\epsilon,$
$\displaystyle 0\leq
S(x,x)<\delta,\;x\in\theta^{j}(C_{2}^{\alpha}-C_{1}^{\alpha}),$

and every pair $(y_{1},y_{2})$ of elements of $G$ with
$S(y_{1}-y_{2},y_{1}-y_{2})=0$ and $y_{1}^{j}\not=y_{2}^{j}$ is contained in
some $(C^{\alpha}_{1},C^{\alpha}_{2})$. Then

$\overline{\Sigma}^{j}_{0}(P_{G})\subset\bigcup_{\alpha}\Sigma_{C^{\alpha}_{1},C^{\alpha}_{2}}(P_{G})=\bigcup_{\alpha}S^{-1}\Sigma_{C^{\alpha}_{1},C^{\alpha}_{2}}(\partial
g),$

where $g(x):=\psi_{G}(S^{-1}x)$, $x\in\real{d}$, and Theorem 2.2 applied to
$\Sigma_{C^{\alpha}_{1},C^{\alpha}_{2}}(\partial g)$ yields the result. ∎

The geometric description of the zero order singularities becomes especially
simple if the index $m=1$. In this case, $\overline{\Sigma}^{j}_{0}(P_{G})$
can be covered by countable number of hyperplanes whose $S$-normal vectors are
$S$-isotropic.

######  Theorem 4.8.

Let $S\in\mathcal{S}^{d}_{1}$, $G\in\mathcal{M}(S)$,
$j\in\left\\{{1,\dots,d}\right\\}$, and assume that
$D:=\operatorname*{int}{\operatorname{dom}{\psi_{G}}}\not=\emptyset$. For
every $n\geq 1$, there exist $y_{n},z_{n}\in G$ such that

$y^{j}_{n}-z^{j}_{n}>0,\quad S(y_{n}-z_{n},y_{n}-z_{n})=0,$ (14)

and

$\overline{\Sigma}^{j}_{0}(P_{G})\subset\bigcup_{n}\left\\{{x\in\real{d}}|\;S(x-z_{n},y_{n}-z_{n})=0\right\\}.$

###### Proof.

By the law of inertia for quadratic forms, [12, Theorem 1, p. 297], there
exists a $d\times d$ matrix $V$ of full rank such that

$S=V^{T}\Lambda V,$

where $V^{T}$ is the transpose of $V$ and $\Lambda$ is the diagonal matrix
with diagonal entries $\left\\{{1,-1,\dots,-1}\right\\}$. In other words,
$\Lambda$ is the canonical quadratic form for $\mathcal{S}^{d}_{1}$ from
Example 4.2. As $S(x,x)=\Lambda(Vx,Vx)$, we deduce that
$F:=VG\in\mathcal{M}(\Lambda)$ and

$A\in\mathcal{I}(S)\iff VA\in\mathcal{I}(\Lambda).$

As we pointed out in Example 4.2,

$F=\operatorname{graph}{f}=\left\\{{(t,f(t))}|\;t\in D\right\\},$

for a $1$-Lipschitz function $f:\;D\rightarrow\real{d-1}$ defined a closed set
$D\subset\real{}$.

Let $x=(s,f(s))$ and $y=(t,f(t))$ be distinct elements of $F$, where $s,t\in
D$. We have that $\left\\{{x,y}\right\\}\in\mathcal{I}(\Lambda)$ if and only
if $\left\lvert f(t)-f(s)\right\rvert=\left\lvert t-s\right\rvert$. The
$1$-Lipschitz property of $f$ then implies that

$f(r)=f(s)+\frac{r-s}{t-s}\left({f(t)-f(s)}\right),\quad r\in D\cap[s,t].$

It follows that the collection of all $\Lambda$-isotropic subsets of $F$ can
be decomposed into an intersection of $F$ with at most countable union of line
segments whose relative interiors do not intersect.

The same property then also holds for the $S$-isotropic subsets of $G$. Thus,
there exist $y_{n},z_{n}\in G$, $n\geq 1$, satisfying (14) and such that every
$S$-isotropic subset of $G$ having elements with distinct $j$th coordinates is
a subset of some $S$-isotropic line
$L_{n}:=\left\\{{y_{n}+t(z_{n}-y_{n})}|\;t\in\real{}\right\\}$. In particular,
if $x\in\overline{\Sigma}_{0}^{j}(P_{G})$, then $P_{G}(x)$ intersects some
line $L_{n}$ at distinct $y$ and $z$. We have that

$2S(x-z,y-z)=S(x-z,x-z)+S(y-z,y-z)-S(x-y,x-y)=0.$

As $y,z\in L_{n}\in\mathcal{I}(S)$, we obtain that $S(x-z_{n},y_{n}-z_{n})=0$,
as required. ∎

######  Example 4.9.

Let $d=2$ and $S$ be the standard bilinear form from Example 4.1:

$S(x,y)=S((x_{1},x_{2}),(y_{1},y_{2}))=x_{1}y_{2}+x_{2}y_{1}.$

Let $G\in\mathcal{M}(S)$. As $S(x,x)=2x_{1}x_{2}$, we have that

$\Sigma_{1}(P_{G})=\Sigma^{j}_{1}(P_{G}),\quad j=1,2.$

Theorem 4.6 yields convex functions $g_{1,n}$ and $g_{2,n}$ on and constants
$\epsilon_{n}>0$, $n\geq 1$, such that ($g^{\prime}=g^{\prime}(t)$ is the
derivative of $g=g(t)$)

$\displaystyle\epsilon_{n}\leq
g^{\prime}_{1,n}(t)-g^{\prime}_{2,n}(t)\leq\epsilon_{n}^{-1},\quad
t\in\operatorname{dom}{g^{\prime}_{1,n}}\cap\operatorname{dom}{g^{\prime}_{2,n}},$
$\displaystyle\Sigma_{1}(P_{G})\subset\bigcup_{n}\left\\{{x\in\real{2}}|\;x_{2}=g_{2,n}(x_{1})-g_{1,n}(x_{1})\right\\}.$

Theorem 4.8 yields sequences $(x^{n}_{1})$ and $(x^{n}_{2})$ in such that

$\overline{\Sigma}^{1}_{0}(P_{G})\subset\bigcup_{n}\left\\{{x\in\real{2}}|\;x_{2}=x^{n}_{2}\right\\},\quad\overline{\Sigma}^{2}_{0}(P_{G})\subset\bigcup_{n}\left\\{{x\in\real{2}}|\;x_{1}=x^{n}_{1}\right\\}.$

These results improve [17, Theorem B.12], where $G$ is a maximal monotone set
and $g_{n}:=g_{1,n}-g_{2,n}$ is a strictly increasing Lipschitz function such
that $\epsilon_{n}\leq g^{\prime}_{n}(t)\leq\epsilon^{-1}_{n}$, whenever it is
differentiable.

## Acknowledgments

We thank Giovanni Leoni for pointing out the references [23] and [11]. We also
thank an anonymous referee for constructive remarks and for bringing to our
attention the references [5] and [22].

## References

  * Albano and Cannarsa [1999] Paolo Albano and Piermarco Cannarsa.  Structural properties of singularities of semiconcave functions.  _Ann. Scuola Norm. Sup. Pisa Cl. Sci. (4)_ , 28(4):719–740, 1999.  ISSN 0391-173X.  URL http://www.numdam.org/item?id=ASNSP_1999_4_28_4_719_0.
  * Alberti [1994] Giovanni Alberti.  On the structure of singular sets of convex functions.  _Calc. Var. Partial Differential Equations_ , 2(1):17–27, 1994.  ISSN 0944-2669.  doi: 10.1007/BF01234313.  URL https://doi.org/10.1007/BF01234313.
  * Ambrosio and Gigli [2013] Luigi Ambrosio and Nicola Gigli.  A user’s guide to optimal transport.  In _Modelling and optimisation of flows on networks_ , volume 2062 of _Lecture Notes in Math._ , pages 1–155. Springer, Heidelberg, 2013\.  doi: 10.1007/978-3-642-32160-3˙1.  URL https://doi.org/10.1007/978-3-642-32160-3_1.
  * Asplund [1969] Edgar Asplund.  Čebyšev sets in Hilbert space.  _Trans. Amer. Math. Soc._ , 144:235–240, 1969.  ISSN 0002-9947.  doi: 10.2307/1995279.  URL https://doi.org/10.2307/1995279.
  * Benyamini and Lindenstrauss [2000] Yoav Benyamini and Joram Lindenstrauss.  _Geometric nonlinear functional analysis. Vol. 1_ , volume 48 of _American Mathematical Society Colloquium Publications_.  American Mathematical Society, Providence, RI, 2000.  ISBN 0-8218-0835-4.  doi: 10.1090/coll/048.  URL https://doi.org/10.1090/coll/048.
  * Brenier [1991] Yann Brenier.  Polar factorization and monotone rearrangement of vector-valued functions.  _Comm. Pure Appl. Math._ , 44(4):375–417, 1991\.  ISSN 0010-3640.  doi: 10.1002/cpa.3160440402.  URL https://doi.org/10.1002/cpa.3160440402.
  * Clarke [1975] Frank H. Clarke.  Generalized gradients and applications.  _Trans. Amer. Math. Soc._ , 205:247–262, 1975.  ISSN 0002-9947.  doi: 10.2307/1997202.  URL https://doi.org/10.2307/1997202.
  * Erdös [1946] Paul Erdös.  On the Hausdorff dimension of some sets in Euclidean space.  _Bull. Amer. Math. Soc._ , 52:107–109, 1946.  ISSN 0002-9904.  doi: 10.1090/S0002-9904-1946-08514-6.  URL https://doi.org/10.1090/S0002-9904-1946-08514-6.
  * Federer [1969] Herbert Federer.  _Geometric measure theory_.  Die Grundlehren der mathematischen Wissenschaften, Band 153. Springer-Verlag New York, Inc., New York, 1969.
  * Fitzpatrick [1988] Simon Fitzpatrick.  Representing monotone operators by convex functions.  In _Workshop/Miniconference on Functional Analysis and Optimization (Canberra, 1988)_ , volume 20 of _Proc. Centre Math. Anal. Austral. Nat. Univ._ , pages 59–65. Austral. Nat. Univ., Canberra, 1988\.
  * Fowler and Preiss [2009] Thomas Fowler and David Preiss.  A simple proof of Zahorski’s description of non-differentiability sets of Lipschitz functions.  _Real Anal. Exchange_ , 34(1):127–138, 2009.  ISSN 0147-1937.  URL http://projecteuclid.org/euclid.rae/1242738925.
  * Gantmacher [1998] Felix R. Gantmacher.  _The theory of matrices. Vol. 1_.  AMS Chelsea Publishing, Providence, RI, 1998.  ISBN 0-8218-1376-5.  Translated from the Russian by K. A. Hirsch, Reprint of the 1959 translation.
  * Hajłasz [2022] Piotr Hajłasz.  On an old theorem of Erdös about ambiguous locus.  _Colloq. Math._ , 168(2):249–256, 2022.  ISSN 0010-1354.  doi: 10.4064/cm8460-9-2021.  URL https://doi.org/10.4064/cm8460-9-2021.
  * Hiriart-Urruty and Lemaréchal [2001] Jean-Baptiste Hiriart-Urruty and Claude Lemaréchal.  _Fundamentals of convex analysis_.  Grundlehren Text Editions. Springer-Verlag, Berlin, 2001.  ISBN 3-540-42205-6.
  * Kramkov and Sîrbu [2022] Dmitry Kramkov and Mihai Sîrbu.  Backward martingale transport and Fitzpatrick functions in pseudo-Euclidean spaces, 2022.  URL https://arxiv.org/abs/2209.04664.  To appear in _The Annals of Applied Probability_.
  * Kramkov and Sîrbu [2023] Dmitry Kramkov and Mihai Sîrbu.  Backward martingale transport maps in pseudo-Euclidean spaces, 2023\.  URL https://arxiv.org/abs/2304.08290.
  * Kramkov and Xu [2022] Dmitry Kramkov and Yan Xu.  An optimal transport problem with backward martingale constraints motivated by insider trading.  _Ann. Appl. Probab._ , 32(1):294–326, 2022.  ISSN 1050-5164.  doi: 10.1214/21-AAP1678.
  * Penot [2009] Jean-Paul Penot.  Positive sets, conservative sets and dissipative sets.  _J. Convex Anal._ , 16(3-4):973–986, 2009.  ISSN 0944-6532.
  * Rockafellar [1970] R. Tyrrell Rockafellar.  _Convex analysis_.  Princeton Mathematical Series, No. 28. Princeton University Press, Princeton, N.J., 1970.
  * Rockafellar and Wets [1998] R. Tyrrell Rockafellar and Roger J.-B. Wets.  _Variational analysis_ , volume 317 of _Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]_.  Springer-Verlag, Berlin, 1998.  ISBN 3-540-62772-3.
  * Simons [2007] Stephen Simons.  Positive sets and monotone sets.  _J. Convex Anal._ , 14(2):297–317, 2007.  ISSN 0944-6532.
  * Thibault [2023] Lionel Thibault.  _Unilateral Variational Analysis in Banach Spaces Part II: Special Classes of Functions and Sets_.  World Scientific, 2023.  ISBN ISBN: 978-981-125-816-9.  doi: 10.1142/12797.  URL https://doi.org/10.1142/12797.
  * Zahorski [1950] Z. Zahorski.  Sur la première dérivée.  _Trans. Amer. Math. Soc._ , 69:1–54, 1950.  ISSN 0002-9947.  doi: 10.2307/1990595.  URL https://doi.org/10.2307/1990595.
  * Zajíček [1979] Luděk Zajíček.  On the differentiation of convex functions in finite and infinite dimensional spaces.  _Czechoslovak Math. J._ , 29(104)(3):340–348, 1979.  ISSN 0011-4642.


# Enhancing ML-Based DoS Attack Detection Through Combinatorial Fusion
Analysis

Evans Owusu  Fordham Univ, NY USA
<EMAIL_ADDRESS>Mohamed Rahouti  Fordham Univ., NY USA
<EMAIL_ADDRESS>D. Frank Hsu  Fordham Univ., NY USA
<EMAIL_ADDRESS>Kaiqi Xiong  Cyber Florida, FL USA
<EMAIL_ADDRESS>Yufeng Xin  RENCI, NC USA
<EMAIL_ADDRESS>
###### Abstract

Mitigating Denial-of-Service (DoS) attacks is vital for online service
security and availability. While machine learning (ML) models are used for DoS
attack detection, new strategies are needed to enhance their performance. We
suggest an innovative method, combinatorial fusion, which combines multiple ML
models using advanced algorithms. This includes score and rank combinations,
weighted techniques, and diversity strength of scoring systems. Through
rigorous evaluations, we demonstrate the effectiveness of this fusion
approach, considering metrics like precision, recall, and F1-score. We address
the challenge of low-profiled attack classification by fusing models to create
a comprehensive solution. Our findings emphasize the potential of this
approach to improve DoS attack detection and contribute to stronger defense
mechanisms.

###### Index Terms:

Cognitive diversity (CD), combinatorial fusion analysis (CFA), Denial of
Services (DoS), machine learning (ML), rank function, rank-score
characteristic (RSC) function, and score function

##  I Introduction

DoS attacks threaten online service availability and stability, making server
protection crucial [1]. With evolving digital threats, more sophisticated and
frequent attacks require strong countermeasures to secure networked
infrastructure [2]. While many ML models have been used, there’s a need for
innovative approaches to enhance detection and performance.

While ML has shown promise in various cybersecurity applications, including
denial DoS detection, it is important to recognize its limitations [3]. Among
these limitations, with regard to DoS detection, is the interpretability and
explainability. Specifically, some ML algorithms, especially deep learning
models, are considered black boxes, making it difficult to interpret their
decision-making process. This lack of interpretability and explainability can
hinder trust and make it challenging to understand why a particular decision
or prediction (e.g., whether a networking flow is malicious or benign) was
made.

To overcome such limitations, a holistic approach combining ML with other
techniques, network-level mitigations, anomaly detection, and expert knowledge
can be employed to enhance the accuracy and robustness of DoS detection
systems. In this paper, we introduce a novel methodology based on leveraging
the cutting-edge approach of combinatorial fusion, which harnesses recently
developed algorithms and techniques for model fusion. Our objective is to
combine multiple ML models using combinatorial fusion analysis to achieve
superior DoS attack detection performance and interpretability.

The key contributions of this paper are summarized as follows.

  * •

Examine the key ML models commonly used for DoS attack detection. Such an
examination serves as the ground truth for integrating the combinatorial
fusion analysis (CFA) approach into our ML-based DoS detection.

  * •

CFA approach: Develop an innovative approach based on CFA for combining
multiple ML models in DoS attack detection. Our methodology encompasses
various techniques, including advanced score combination, rank combination,
weighted combination, and the consideration of diversity strength across
multiple scoring systems.

  * •

Conduct performance evaluations to assess the effectiveness of our CFA.
Through comparative analyses, we showcase the significant improvements
achieved in terms of detection accuracy, false positive rates, and overall
precision.

By leveraging the power of the recently developed combinatorial fusion
approach and its associated algorithms, our study aims to push the boundaries
of DoS attack detection. We anticipate that our findings will contribute to
the advancement of more robust and effective defense mechanisms against DoS
attacks, bolstering the uninterrupted availability and security of critical
online services.

##  II Related Work

DoS attack detection continuously gains attention in cybersecurity, with
diverse methods proposed to enhance accuracy [4]. Escalating DoS attacks
prompted increased focus by researchers [5]. Many studies employ ML algorithms
for DoS attack detection, using models like SVMs, Random Forests, and Naive
Bayes. These models analyze network patterns, using features like packet
rates, sizes, and volume to differentiate normal and attack traffic [6].
Further, CNNs, RNNs, and variants extract intricate patterns and temporal
dependencies from network traffic [3], showing promise in accurate attack
identification. Ensemble methods like Bagging, Boosting, and Stacking also
gained traction, combining models to enhance prediction [7]. These approaches
counter individual model limitations, boosting accuracy and robustness.

In recent years, model fusion techniques, such as combinatorial fusion
analysis (CFA), have emerged as practical means of combining multiple ML
models’ performance [8, 9]. These approaches leverage algorithms and metrics
specifically designed to integrate the outputs of different models,
considering their diversity and individual performance. The goal is to
leverage diverse models’ collective knowledge and expertise to achieve higher
accuracy and detection rates [10]. While previous studies have remarkably
contributed to DoS attack detection, our work focuses on the emerging CFA. To
the best of our knowledge, this is the first work that adopts CFA for
examining the performance of ML models-based DoS attack detection. By
combining the strengths of multiple ML models using advanced fusion
techniques, we aim to achieve more accurate and reliable detection results.

##  III Methodology

###  III-A Problem Abstraction

TABLE I: Types of network traffic in the LYCOS-IDS dataset and their training and testing sets. Traffic | Encoding | Train set | Test set
---|---|---|---
Benign | 0 | 330474 | 110158
Bot | 1 | 550 | 183
DDoS | 2 | 71761 | 23920
DoS Goldeneye | 3 | 5073 | 1691
DoS Hulk | 4 | 119241 | 39747
DoS Slowhttptest | 5 | 3649 | 1216
DoS Slowloris | 6 | 4255 | 1418
FTP Patator | 7 | 3001 | 1000
Heartbleed | 8 | 7 | 2
Portscan | 9 | 119197 | 39732
SSH Patator | 10 | 2218 | 739
Webattack Bruteforce | 11 | 1020 | 340
Webattack Sql Injection | 12 | 9 | 3
Webattack XSS | 13 | 489 | 163
Total |  | 660944 | 220,312

Modern DoS attacks (e.g., UDP, DNS, SYN, NTP) jeopardize networking
environments. Existing approaches target DoS detection but struggle with
evolving DoS attacks. Addressing this demands advanced classification using
fusion, stats, and recent attack data. This tailors defense systems to
distinct attack features. Intrusion detection algorithms should evolve beyond
old datasets and traditional methods. Dynamic DoS nature mandates a
comprehensive approach, moving from detection to classification and effective
responses [11].

CFA is an emerging approach for combining results from multiple scoring
systems. These systems are described by a set of statistical attributes or
variables at the data level or by a group of algorithms or models at the
computational informatics level. In this paper, we leverage the CFA approach
to combine the results from six base ML models, namely Linear Discriminant
Analysis (A), Gaussian Naive Bayes (B), Logistic Regression (C), K Nearest
Neighbor (D), Decision Trees (E), and Random Forest (F). The CFA approach is a
process of ensemble reinforcement learning, where all possible rank and score
combinations are considered to find the optimal combination of the candidate
models. We apply this approach to address the problem of DoS detection. To
determine the most effective model fusion performance, our methodology
utilizes the emerging CFA approaches, which involve considering both the score
and rank functions for each model (i.e., scoring system) and applying metrics
such as average score combination, average rank combination, and weighted
combination that factor in the diversity strength or the performance of each
scoring system. Last, we employ a 2-model combination to fuse 6 models,
pairing them 2 at a time.

###  III-B Dataset

We use the LYCOS-IDS2017 dataset created through the LycoSTand flow extractor
[12]. These datasets contain five days’ worth of network flow entries, each
comprising 83 features. In total, there are 1,837,498 entries in the dataset.
To prepare the data for analysis, we used a 75% split for the training set and
25% for the test set as shown in Table I. The types of network traffic in the
dataset and their training and testing sets are summarized by Table I. After
training the six ML models on the training data, we assessed their performance
on unseen data by applying the test dataset to each model. The prediction
probabilities for each model across the different classes were collected. By
convention, the class with the highest probability was selected as the final
prediction for each data entry. These probabilities represent the models’
confidence level in their predictions for the individual data items. The
probabilities generated by the six scoring systems are considered scores for
each individual data entry. This score information formed a new dataset,
including the original data items and the six probabilities obtained from the
models. The CFA algorithm leveraged this new dataset to derive valuable
insights using various CFA approaches discussed later in the paper.

###  III-C Data Pre-processing and Exploratory Analysis (Probabilities and
Confidence Scores)

Probabilities and confidence scores are vital in ML models, especially for
classification. They offer insight into prediction likelihood and confidence
for each label. Models like logistic regression, SVM with probability outputs,
and ensembles like Random Forests and Gradient Boosting provide more than just
class labels. They yield probabilities or confidence scores for each class,
enhancing classification information. Further, probabilities reflect a model’s
certainty in class predictions. A 0.8 probability for Class A indicates strong
belief, while 0.2 suggests lower confidence. This nuanced information aids
decisions, especially in uncertain or multi-class scenarios. Evenly
distributed probabilities signal ambiguity, while high single-class
probabilities show confidence.

Moreover, these probabilities assist in post-processing tasks such as
thresholding, ranking, and model fusion. Thresholds adjust predictions for
precision-recall trade-offs. Ranking classes by probabilities helps select
top-k likely classes, important for uncertainty. Combining models’ predictions
via weighted voting or using probabilities as weights enhances ensemble
accuracy and robustness. In this paper, we collect the probabilities
associated with each prediction, the highest probability among all the classes
for the various data points. Treating these probabilities as scores for each
data point, we explore different CFA metrics to combine them. Our goal is to
identify the optimal approach for combining these scores across multiple
models to develop an effective combined model.

###  III-D Performance Evaluation of Scoring Systems

By employing conventional ensemble methods, we can combine multiple ML
classification models and evaluate their performance using specific metrics.
The approaches used here are voting-based ensembles and collective confidence.

In voting-based ensembles, multiple classification models are trained
independently on the same dataset. During the prediction phase, each model
generates its own set of predictions for a given input, and the final
prediction is determined based on a voting mechanism. There are two main types
of voting-based ensembles, majority voting (each model in the ensemble casts a
vote for the predicted class) and weighted voting (each model’s prediction is
weighted based on its performance). In collective confidence approach, instead
of treating predictions as discrete class labels, we can consider each model’s
confidence scores. One common approach is to calculate the average probability
for each class across all models and select the class with the highest average
probability as the final prediction. This approach accounts for the collective
confidence of the models. Alternatively, the probabilities can be weighted by
the performance of each model, similar to the weighted voting approach, to
assign more importance to models with better performance.

Choosing between weighted voting and using probabilities depends on the
problem and model traits. Finding the right approach might need trial and
error. In our paper, we employ the weighted combination of
probabilities/confidence scores as the CFA metric, named weighted combination
by performance, for two-model fusion. Model weights, assigned by recall
scores, prioritize accurate detection of all attack instances. Lastly,
Stacking is a advanced ensemble method where a meta-model learns to combine
predictions from base models. Ensemble techniques enhance performance by
leveraging model strengths, capturing diverse viewpoints and complex patterns.
Careful experimentation and validation are essential to find the practical
model combination for a classification problem. Next, details are provided for
the key components leveraged from CFA, namely, rank score characterization
(RSC) for the ML models, diversity between RSC functions (scoring systems),
and rank combination vs. score combination.

A scoring system $A$ on the data set $D=\\{d_{1},d_{2},...,d_{n}\\}$,
comprising a score function $s_{A}$ and a derived rank function $r_{A}$, was
proposed in [13]. By sorting the values in descending order in the score
function $s_{A}:D\mapsto\mathbb{R}$, a rank function
$r_{A}:D\mapsto\mathbb{N}$, where $\mathbb{N}=\\{1,2,3,...n\\}$, is obtained.
The RSC function $f_{A}:\mathbb{N}\mapsto\mathbb{R}$ upon scoring system $A$
is expressed as follows:

$f_{A}(i)=s_{A}(r_{A}^{-1}(i))=(s_{A}\circ r_{A}^{-1})(i)$ (1)

Figure 1: Rank score function graph for the six scoring systems. The area
between any two RSC functions represents their diversity.

Cognitive Diversity (CD) between the six systems (${A,B,C,D,E,F}$) is defined
as the difference between the RSC functions of these systems [14]. We explore
the diversity of the RSC functions for each pair of these six scoring systems.
Precisely, we will calculate CD between each pair of the six models. The CD
between two scoring systems $A_{i}$ and $A_{j}$ is denoted by
$CD(A_{i},A_{j})$, which is based on the RSC function of $A_{i}$ and $A_{j}$
that are denoted by $f_{A_{i}}$ and $f_{A_{j}}$, respectively. Given the rank
$k\in\\{1,2,...,n\\}$, CD is defined as:

$CD(A_{i},A_{j})=\sqrt{\frac{1}{n^{2}-n}\sum_{k=1}^{n}{(f_{A_{i}}(k)-f_{A_{j}}(k))^{2}}}$
(2)

The diversity strength of scoring system $A$ is defined as the average CD
between $A$ and all other systems. Let
$D_{j}=\\{d_{1},d_{2},...,d_{n}\\}\subseteq D$ be the labels of each cross-
validation split for the scores $j\epsilon 1,...,P$ generated by the systems,
we obtain the RSC functions of our six scoring systems as:

  1. 1.

The score function, $s_{kj}(d)$, gives a real number to each $d$ in $D_{j}$,
which is the score given by the model $M_{k}$ to the label for $j_{th}$ split.
Having the scores given by each model for each $d$ in $D_{j}$ provides the
score function.

  2. 2.

Sort $s_{kj}(d)$ into descending order and assigning ranks to each candidate
in $D_{j}$ based on the sorted scores results in a rank function $r_{kj}(d)$.
We rank the scores for each model/scoring system to obtain the rank function.

  3. 3.

Compare score functions from multiple scoring systems by applying linear
normalization, which is the following transformation from
$s_{kj}(d):D\rightarrow R$ to $s^{*}_{kj}(d):D\rightarrow[0,1]$ where
$s^{*}_{kj}(d)=\frac{s_{kj}(d)-s_{min}}{S_{max}-S_{min}},d\epsilon D$ and
$s_{max}=max\\{s_{kj}(d)|d\epsilon D\\}$
and $s_{min}=min\\{s_{kj}(d)|d\epsilon D\\}$.

  4. 4.

Derive the RSC functions by sorting the normalized scores for each scoring
system in descending order, using the rank values as keys (aka computational
derivation of RSC function).

  5. 5.

Plot RSC functions on the same x-y coordinate plane to depict their diversity.
The x-axis and the y-axis represent the ranks and normalized scores,
respectively (Fig. 1).

Next, we investigate the superiority between rank combination and score
combination. The rank combination can outperform the score combination under
rigorous constraints/conditions [9]. We explore the conditions for which
efficient performance combinations can be obtained in favor of larger CD
values between each pair of the six ML models. Here, we integrate the results
of $m$ scoring systems, each with its own score function $s_{kj}(d)$ and rank
function $r_{kj}(d)$ for data label $j$, where $k$ represents the scoring
system index. Such techniques include score combination (SC), rank combination
(RC), voting (V), average combination (AC), and weighted combination (WC). We
compute SC, RC, AV, and WC based on the following weighting metrics.

  1. 1.

Average Combination (AC): The average score combination and average rank
combination are computed as $s_{s}(d)=\sum_{i=1}^{m}[w_{i}s_{ij}(d)]$, and
$s_{R}(d)=\sum_{i=1}^{m}[w_{i}r_{ij}(d)]$ where $w_{i}=\frac{1}{m}$, and
$s_{s}$ and $s_{R}$ are the score and rank functions of SC and RC
respectively.

  2. 2.

Weighted combination by diversity strength (WCDS): Weighted score combination
by diversity strength (WSCDS) and weighted rank combination by diversity
strength (WRCDS) are the two metrics considered here, and the weights are
calculated as follows.

$W_{i}=\frac{\textnormal{weight of model i}}{\textnormal{sum of
weights}}=\begin{cases}\frac{1}{N},AC\\\
\frac{ds(A_{i})}{\sum_{i=1}^{N}ds(A_{i})},WCDS\par\end{cases}$ (3)
$WSCDS_{ij}(d)=\frac{(\textnormal{weight of model
i})*s_{ij}(d)}{\textnormal{sum of weights}}$

For WRCDS, replace $s_{ij}(d)$ with $r_{ij}(d)$ and $w_{i}$ with
$\frac{1}{w_{i}}$.

##  IV Evaluation

TABLE II: Two model combination - Weighted score combinations by performance
(recalls) for the data items $d_{1}$ \- $d_{10}$.

$D_{i}$ AB AC AD AE AF BC BD BE BF CD CE CF DE DF EF $d_{1}$ 1 0.76258 1 1 1
0.77052 1 1 1 0.77067 0.77069 0.77077 1 1 1 $d_{2}$ 1 0.99976 1 1 1 0.99976 1
1 1 0.99976 0.99976 0.99976 1 1 1 $d_{3}$ 1 0.54627 1 1 1 0.56144 1 1 1
0.56172 0.56175 0.56191 1 1 1 $d_{4}$ 1 0.54597 1 1 1 0.56115 1 1 1 0.56143
0.56146 0.56162 1 1 1 $d_{5}$ 0.99996 0.55247 1 1 1 0.52705 0.99996 0.99996
0.99996 0.56771 0.56774 0.5679 1 1 1 $d_{6}$ 1 0.54641 1 1 1 0.56158 1 1 1
0.56186 0.5619 0.56205 1 1 1 $d_{7}$ 1 0.98708 1 1 1 0.98635 1 1 1 0.98752
0.98752 0.98753 1 1 1 $d_{8}$ 1 0.98739 1 1 1 0.98727 1 1 1 0.98741 0.98744
0.98744 1 1 1 $d_{9}$ 1 0.53821 1 1 1 0.53929 1 1 1 0.53991 0.53991 0.53991 1
1 1 $d_{10}$ 0.76986 0.76639 0.78936 0.78938 0.78945 0.98505 0.99962 0.99962
0.99962 0.99845 0.99845 0.99845 1 1 1

TABLE III: Rankings of the WSCP results presented in Table II for the data
items $d_{1}$ \- $d_{10}$.

$D_{i}$ AB AC AD AE AF BC BD BE BF CD CE CF DE DF EF $d_{1}$ 1 114936 1 1 1
105351 1 1 1 115227 116010 115949 1 1 1 $d_{2}$ 1 16485 1 1 1 13230 1 1 1
17815 17547 17270 1 1 1 $d_{3}$ 1 176670 1 1 1 157873 1 1 1 175125 175153
175236 1 1 1 $d_{4}$ 1 179070 1 1 1 159554 1 1 1 177513 177561 177623 1 1 1
$d_{5}$ 176598 152728 1 1 1 207139 184970 185096 184279 152473 152519 15495 1
1 1 $d_{6}$ 1 175530 1 1 1 157132 1 1 1 174123 174147 174181 1 1 1 $d_{7}$ 1
37075 1 1 1 37065 1 1 1 38823 39053 38739 1 1 1 $d_{8}$ 1 36857 1 1 1 36161 1
1 1 38925 39134 38825 1 1 1 $d_{9}$ 1 197884 1 1 1 181049 1 1 1 198636 198655
198640 1 1 1 $d_{10}$ 219277 110590 218958 218912 218977 38342 199530 199659
198672 39536 39833 39516 1 1 1

TABLE IV: Performance evaluation of individual models at the class level of
granularity.

A B C D E F $class$ Precision Recall F1score Precision Recall F1score
Precision Recall F1score Precision Recall F1score Precision Recall F1score
Precision Recall F1score $0$ 0.995305 0.933387 0.963352 0.994616 0.169366
0.289444 0.9739 0.913225 0.942587 0.999228 0.998502 0.998865 0.996296 0.998638
0.997466 0.999691 0.999328 0.99951 $1$ 0.995305 0.933387 0.963352 0.096706
0.994536 0.176271 0 0 0 0.983696 0.989071 0.986376 0.994536 0.994536 0.994536
1 1 1 $2$ 0.042553 0.065574 0.051613 0.983337 0.999164 0.991187 0.783516
0.737625 0.759879 0.992537 0.978554 0.985496 0.999958 1 0.999979 1 1 1 $3$
0.999791 0.999833 0.999812 0.356379 0.966292 0.520714 0.589041 0.81372
0.683387 0.960603 0.980485 0.970442 0.968347 0.976937 0.972623 0.969873
0.989947 0.979807 $4$ 0.778788 0.911886 0.840098 0.98708 0.974564 0.980782
0.723168 0.862027 0.786516 0.986929 0.995396 0.991144 0.999874 0.999723
0.999799 1 0.999824 0.999912 $5$ 0.811881 0.809211 0.810544 0.099778 0.814967
0.17779 0.684392 0.814967 0.743994 0.966503 0.972862 0.969672 0.9801 0.972039
0.976053 0.981224 0.988487 0.984842 $6$ 0.816667 0.794781 0.805575 0.034563
0.834274 0.066377 0.375488 0.33921 0.356428 0.975456 0.980959 0.9782 0.991507
0.988011 0.989756 0.992928 0.990127 0.991525 $7$ 0.688797 0.996 0.814391
0.996004 0.997 0.996502 0.531576 0.968 0.686281 0.996004 0.997 0.996502
0.999001 1 0.9995 1 1 1 $8$ 0.333333 1 0.5 1 1 1 0 0 0 1 0.5 0.666667 1 1 1 1
1 1 $9$ 0.958722 0.9926 0.975367 0.471534 0.997257 0.64031 0.99932 0.998339
0.998829 0.999321 0.999799 0.99956 0.999648 0.999924 0.999786 0.999648 0.99995
0.999799 $10$ 0.541325 0.983762 0.698367 0.941482 0.979702 0.960212 0.851852
0.622463 0.719312 0.987887 0.993234 0.990553 0.99594 0.99594 0.99594 0.998645
0.997294 0.997969 $11$ 0.017903 0.061765 0.027759 0.037879 0.102941 0.05538 0
0 0 0.706941 0.808824 0.754458 0.594937 0.414706 0.488735 0.715013 0.826471
0.766712 $12$ 0.001724 0.333333 0.003431 0.04918 1 0.09375 0 0 0 0 0 0 0 0 0 0
0 0 $13$ 0.052947 0.97546 0.100442 0.274874 1 0.431217 0 0 0 0.452991 0.325153
0.378571 1 0.018405 0.036145 0.46789 0.312883 0.375

Figure 2: Performance of models at the class level of granularity. Figure 3:
Recalls of each of the 15 combined models using weighted score combination by
performance at the class level of granularity.

We assess model performance and efficiency at the class level, particularly in
smaller sampled classes. Precise detection and classification of every attack
are crucial, as even one missed attack can be harmful. Thus, our analysis
emphasizes recall as a vital criterion. We employ diverse CFA metrics to
combine models, harnessing strengths and addressing weaknesses. We calculate
average score combination (ASC) and average rank combination (ARC) using the
top 10 flows from 220,312, selected based on ASC and ARC metrics. These flows
show high confidence in the fusion model’s predictions. A small subset of the
CFA dataset has all models with the highest probability scores, indicating
lack of diversity. This tie results in identical top-ranking positions for
both metrics. Although they yield the same outcome at rank 1, differences
arise as rankings progress due to score variations. These metrics demonstrate
distinct behavior with diverse scoring systems.

The weighted score combination by diversity strength and weighted rank
combination by diversity strength are calculated, where the flows represent
the first 10 out of a total of 4187 top-ranked flows. These flows are the ones
in which the fusion model exhibits the highest confidence level in its
prediction. Due to a lack of model diversity at the top-performing data items,
the two above metrics produced the same output at rank position 1. However,
the results vary as we move down the ranks. Table II shows the two-model
combination, weighted score combinations by performance (recalls) for the data
items $d_{1}$ \- $d_{10}$. Recall focuses on the model’s ability to find all
positive instances, measured per each attack class for all models. Last, Table
III summarizes the rankings of the WSCP results presented in the tables
mentioned above for the data items $d_{1}$ \- $d_{10}$. Building upon these
tables, we aim to identify a model that performs well not only on the commonly
observed attacks but also on the low-profiled ones.

While most models individually performed well against many attacks, they faced
difficulty with low-profile attacks. Conversely, models excelling at low-
profile attacks struggled with other attack types. This prompted us to
consider model fusion, leveraging strengths and offsetting weaknesses. Our
goal was to create a robust, comprehensive model by combining individual
outputs, capable of effectively handling low-profile attacks and other
traffic. Our method modifies the soft Voting Classifier as a metric for
generating combined predictions. We average probability scores across classes
for each model, using model recall values as weights for accurate aggregation.
This advanced CFA technique, called weighted combination by performance,
incorporates each model’s recall performance at the attack level, enhancing
fusion with model-specific attack data.

By assigning higher weights to models with higher recall rates for a given
attack, we aimed to prioritize the models that were more adept at correctly
identifying all attacks, including the low-profiled ones. This CFA strategy
proved to be highly effective in enhancing the overall performance of our
methodology. By incorporating the strengths of multiple models, we established
a balanced and robust classification system that improved recall and
reliability. Consequently, we successfully leveraged the individual strengths
of each model, resulting in a more comprehensive and successful approach to
attack identification and classification.

Table IV highlights the performance of individual models, with Model $F$
emerging as the highest performer overall. However, it exhibited significant
weaknesses in accurately classifying the low-profile attack class 12. On the
other hand, Model $B$ demonstrated a flawless performance in identifying low-
profiled attacks. Nonetheless, it fell short of effectively classifying other
types of attacks compared to other models. Figures 2 and 3 visually depict the
performance of the six individual models and their two-model combinations
across various classes, allowing for a comparison of their respective
performances. A best performing models for each attack can be found in Table
V.

Among the various models, Model $BE$ consistently outperformed the others,
exhibiting the highest recall rates for both low-profiled attacks and other
traffic categories. This indicates that Model $BE$ excels in accurately
identifying and classifying attacks, particularly in cases where limited
training data is available. However, it should be noted that Model $BE$
obtained a recall of only 0.1 for attack class 11 which is a potential
weakness. Model $CE$ demonstrated the highest recall of 0.9555882 for attack
class 11, surpassing all other models. Motivated by this observation, we
combined Models $BE$ and $CE$ to explore the possibility of achieving improved
recalls across all attack classes. However, the fusion of these models, Model
$BECE$, did not significantly increase the recall for Class 11.

Table V presents a summary of the performance for individual and combined
models. Notably, Model $DF$ achieved a remarkable 100% recall for the attack
class 4, surpassing the performance of the best individual model in that
category. This highlights the effectiveness of the combined model approach in
achieving higher recall rates. Based on the CFA metric employed, our
recommended fusion model would be to use Model $DF$ for attack class 4 and
then Model $BE$ for all attack classes except class 11, for which Model $CE$
is employed. This combination would yield better overall performance in terms
of recall and outperform the individual models.

Last, while Model $BE$ and Model $CE$ successfully enhanced the recall rates
for all attack classes, developing more advanced fusion techniques may yield
even better results. Overall, our approach of combining models proved
successful in achieving our goal of developing a model that performs well,
particularly in recalling low-profiled attacks.

TABLE V: Best performing models for each class (by recalls). Multiple models for a given class represents a tie. Traffic | Individual | Combined using WSCP
---|---|---
0 | F (99.93) | CF (99.92)
1 | F (100) | AE, AF, BE, CE, DE, DF, EF, BECE
|  | (100)
2 | F (100) | BF, CE, CF, DE, BECE, EF (100 )
3 | A (99.98) | DF (99.05)
4 | F (99.98) | DF (100)
5 | F (98.85) | DF (98.52)
6 | F (99.01) | CF (99.01)
7 | E, F (100) | AE, BE, CE, CF, DE, BECE, EF (100)
8 | A, B, E, F | AB, AC, AD, AE, AF, BC, EF, BD (100)
|  | BE, BF, CD, CE, CF, DE, DF, EF, BECE
9 | F (100) | BF, CF (100)
10 | F (99.73) | CF (99.73)
11 | F (82.65) | CE (95.59)
12 | B (100) | BF, BECE, BC, BD, BE (100)
13 | B (100) | AB, BC, BE (100)

##  V Conclusion

This work uses the fusion approach to enhance ML-based DoS attack detection.
Specifically, we targeted low-profile attack detection, an area where single
models faltered. By merging multiple ML models with advanced CFA metrics, we
improved precision, recall, and F1-score. This produced a highly effective
combined model that nearly perfectly detected all attacks, including low-
profile ones, achieving 100% recall. Unlike most single models, our approach
succeeded in this. CFA methods hold promise for boosting DoS attack detection.
Future work can refine algorithms, explore more scoring systems, and integrate
emerging tech for stronger defense. Advancing in this field ensures secure
online services despite evolving threats.

## References

  * [1] B. B. Gupta and A. Dahiya, _Distributed Denial of Service (DDoS) Attacks: Classification, Attacks, Challenges and Countermeasures_. CRC press, 2021.
  * [2] M. Rahouti, K. Xiong, N. Ghani, and F. Shaikh, “SYNGuard: Dynamic threshold-based SYN flood attack detection and mitigation in software-defined networks,” _IET Networks_ , vol. 10, no. 2, pp. 76–87, 2021\.
  * [3] M. Mittal, K. Kumar, and S. Behal, “Deep learning approaches for detecting DDoS attacks: A systematic review,” _Soft Computing_ , pp. 1–37, 2022\.
  * [4] W. Zhijun, L. Wenjing, L. Liang, and Y. Meng, “Low-rate DoS attacks, detection, defense, and challenges: a survey,” _IEEE Access_ , vol. 8, pp. 43 920–43 943, 2020.
  * [5] J. David and C. Thomas, “Discriminating flash crowds from DDoS attacks using efficient thresholding algorithm,” _JPDC_ , vol. 152, pp. 79–87, 2021, Elsevier.
  * [6] T. E. Ali, Y.-W. Chong, and S. Manickam, “Machine learning techniques to detect a DDoS attack in SDN: A systematic review,” _Applied Sciences_ , vol. 13, no. 5, p. 3183, 2023.
  * [7] V. Deepa, K. M. Sudar, and P. Deepalakshmi, “Design of ensemble learning methods for DDoS detection in SDN environment,” in _ViTECoN_. IEEE, 2019, pp. 1–6.
  * [8] D. F. Hsu, Y.-S. Chung, and B. S. Kristal, “Combinatorial fusion analysis: methods and practices of combining multiple scoring systems,” in _Advanced data mining technologies in bioinformatics_. IGI Global, 2006, pp. 32–62.
  * [9] D. F. Hsu, B. S. Kristal, and C. Schweikert, “Rank-score characteristics (RSC) function and cognitive diversity,” in _International Conference on Brain Informatics_. Springer, 2010, pp. 42–54.
  * [10] L. Hurley, B. S. Kristal, S. Sirimulla, C. Schweikert, and D. F. Hsu, “Multi-layer combinatorial fusion using cognitive diversity,” _IEEE Access_ , vol. 9, pp. 3919–3935, 2020.
  * [11] Q. Tian, C. Guang, C. Wenchao, and W. Si, “A lightweight residual networks framework for DDoS attack classification based on federated learning,” in _INFOCOM WKSHPS_. IEEE, 2021, pp. 1–6.
  * [12] A. Rosay, F. Carlier, E. Cheval, and P. Leroux, “From CIC-IDS2017 to LYCOS-IDS2017: A corrected dataset for better performance,” in _IEEE/WIC/ACM WI-IAT_. ACM, 2021, p. 6. [Online]. Available: https://doi.org/10.1145/3486622.3493973
  * [13] D. Hsu, J. Shapiro, and I. Taksa, “Methods of data fusion in information retreival: Rank vs. score combination,” DIMACS TR 2002, Tech. Rep., 2002.
  * [14] D. F. Hsu, B. S. Kristal, Y. Hao, and C. Schweikert, “Cognitive diversity: A measurement of dissimilarity between multiple scoring systems,” _Journal of Interconnection Networks_ , vol. 19, no. 01, p. 1940001, 2019\.