# Geochromatic Numbers

###### Abstract

A geometric graph, $\overline{G}$, is a graph drawn in the plane, with
straight line edges and vertices in general position. A geometric homomorphism
between two geometric graphs $\overline{G}$, $\overline{H}$ is a vertex map
$f:\overline{G}\to\overline{H}$ that preserves vertex adjacency and edge
crossings. The geochromatic number of $\overline{G}$, denoted
$X(\overline{G})$, is the smallest integer $n$ so that there is a geometric
homomorphism from $\overline{G}$ to some geometric realization of $K_{n}$.
Recall that the chromatic number of an abstract graph $G$, denoted $\chi(G)$,
is the smallest integer $n$ for which there is a graph homomorphism from $G$
to $K_{n}$. It is immediately clear that $\chi(G)\leq X(\overline{G})$. This
paper establishes some upper bounds on $X(\overline{G})$ in terms of
$\chi(G)$. For instance, if all crossings are at distance at least 1 from each
other, then $X(\overline{G})\leq 3\chi(G)$. However, there are more precise
results. If all crossing are at distance at least 2, then
$X(\overline{G})\leq\chi(G)+2$. If all crossings are at distance at least 1,
and there is a graph homomorphism $f:G\to K_{n}$ that maps no pair of edges
that cross in $\overline{G}$ to the same edge in $K_{n}$, then
$X(\overline{G})\leq 2n$. Finally, if $\chi(G)\in\\{2,3\\}$ and all crossings
are at distance at least 1, then $X(\overline{G})\leq 2\chi(G)$.

Geochromatic Number when Crossings are Independent

Debra L. Boutin

Department of Mathematics and Statistics

Hamilton College, Clinton, NY 13323

<EMAIL_ADDRESS>
Alice Dean

Department of Mathematics and Statistics

Skidmore College, Clinton, NY 12866

<EMAIL_ADDRESS>
##  1 Introduction

A geometric graph $\overline{G}$ is a simple graph drawn in the plane, on
vertices in general position, with straightline edges. Abstractly what we care
about in a geometric graph is which pairs of vertices are adjacent and which
pairs of edges cross. In particular, two geometric graphs are said to be
isomorphic if there is a bijection between their vertex sets that preserves
adjacencies, non-adjacencies, crossings, and non-crossings.

A natural way to extend the ideas of abstract graph homomorphisms to the
context of geometric graphs is to define a geometric homomorphism as a vertex
map $f:\overline{G}\to\overline{H}$ that preserves both adjacencies and
crossings (but not necessarily non-adjacencies or non-crossings). If such a
map exists, we write $\overline{G}\to\overline{H}$ and say ‘$\overline{G}$ is
(geometrically) homomorphic to $\overline{H}$.’ There are many similarities
between abstract graph homomorphisms and geometric graph homomorphisms, but
there are also great contrasts. Further, results that are straightforward in
abstract graph homomorphism theory can become complex in geometric graph
homomorphism theory.

In abstract graph homomorphism theory (of simple graphs) two vertices cannot
be identified under any homomorphism if and only if they are adjacent. In
Section 2 we review some of the reasons why two vertices might not be able to
be identified under any geometric homomorphism: if they are adjacent; if they
are involved in a common edge crossing; if they are endpoints of an odd length
path each edge of which is crossed by a common edge; if they are endpoints of
a path of length 2 whose edges cross all edges of an odd length cycle.

Recall that one definition for the chromatic number of a graph $G$, denoted
$\chi(G)$, is the smallest integer $n$ so that $G\to K_{n}$. By the
transitivity of homomorphisms, if $G\to H$, then $\chi(G)\leq\chi(H)$.
Analogously, the geochromatic number of a geometric graph $\overline{G}$,
denoted $X(\overline{G})$, is the smallest integer $n$ so that
$\overline{G}\to\overline{K}_{n}$, for some geometric $n$-clique
$\overline{K}_{n}$. We immediately get that $\overline{G}\to\overline{H}$
implies $X(\overline{G})\leq X(\overline{H})$. There are also other parameters
whose relationships are preserved by geometric homomorphisms. The thickness of
a geometric graph, denoted $\theta(\overline{G})$, is the minimum number of
plane layers of $\overline{G}$. In [1] we see that that
$\overline{G}\to\overline{H}$ implies both $\chi(G)\leq\chi(H)$ and
$\theta(\overline{G})\leq\theta(\overline{H})$.

Two crossings in a geometric graph are said to be independent if they have no
vertices in common. Further, we define the distance between two crossings as
the minimum distance between the vertices of the first crossing and the
vertices of the second. Thus, crossings are independent if they are at
distance at least 1. In Section 3 we focus on the geochromatic number of
geometric graphs with given chromatic number and independent crossings. In
Section 4 we briefly discuss a geometric graph coloring that is weaker than
the geochromatic coloring, but might be mistaken for it.

##  2 Background

For additional background on graph homomorphisms, see [6]. For more
information on geometric graphs, see [7, 8]. For other articles on geometric
homomorphisms, see [1, 2, 5, 3, 4].

In abstract graph homomorphism theory, every graph on $n$ vertices is
homomorphic to $K_{n}$. This is not true for geometric graphs. In fact, two
different geometric realizations of the same abstract graph are not
necessarily homomorphic to each other. For example, consider the two geometric
realizations of $K_{6}$ given in Figure 1. The first has a vertex with all
incident edges crossed, the second does not; this can be used to prove that
there is no geometric homomorphism from the first to the second. The second
has more crossings than the first; this can be used to prove that there is no
geometric homomorphism from the second to the first.

Figure 1: Homomorphically distinct realizations of $K_{6}$.

The following observations were proved in [1]. They are replicated here so
that we can use them, but also to give a sense of some of the difficulties of
finding geometric homomorphisms.

######  Theorem 1.

[1]

  1. (a)

Adjacent vertices cannot be identified by any geometric homomorphism.

  2. (b)

Endpoints of edges that cross cannot be identified by any geometric
homomorphism.

  3. (c)

The endpoints of an odd-length path cannot be identified by any geometric
homomorphism if there is an edge that crosses all the edges of the path. See
the geometric graph on the left in Figure 2.

  4. (d)

The endpoints of a path of length 2 cannot be identified by any geometric
homomorphism if its edges cross all edges of an odd-length cycle. See the
geometric graph on the right in Figure 2.

Figure 2: In each, the white vertices cannot be identified

Recall that the definition of geochromatic number of a geometric graph is a
generalization of the chromatic number of a graph $G$, $\chi(G)$, as the
smallest $n$ so that there is a graph homomorphism $G\to K_{n}$. In particular
we have the following definition.

######  Definition 1.

Let $\overline{G}$ be a geometric graph. The geochromatic number of
$\overline{G}$, denoted by $X(\overline{G})$, is the smallest positive integer
$n$ such that $\overline{G}\to\overline{K}_{n}$ for some geometric clique
$\overline{K}_{n}$.

The geochromatic number of $\overline{G}$ must be large enough not only to
accommodate the adjacency relationships among vertices of $\overline{G}$, but
also the crossing relationships among its edges.

In investigating geochromatic numbers, it makes sense to start with the
smallest ones. We can see that $X(\overline{G})=1$ if and only if
$\overline{G}$ has no edges.

Since a geometric graph with a pair of crossing edges requires at least four
colors in a geochromatic coloring, we immediately get that $X(\overline{G})=2$
if and only if $\overline{G}$ is a bipartite plane geometric graph, and that
$X(\overline{G})=3$ if and only if $\overline{G}$ is a 3-chromatic plane
geometric graph. Since deciding whether $\chi(G)\leq 3$ is an NP-complete
problem [9], deciding whether $X(\overline{G})\leq 3$ is NP-complete also.
Theorems in [1] give conditions that are necessary but not sufficient for
$X(\overline{G})=4$, as well as conditions that are sufficient but not
necessary. In [1] we also see that for any $n$ there exists a thickness-2
geometric bipartite graph with geochromatic number $n$. Thus even bounding
both the chromatic number and thickness of a geometric graph does not bound
its geochromatic number.

Similarly, the number of crossings in a geometric graph often tells us little
about its geochomatic number. Above we mentioned that if $\overline{G}$
contains no crossing edges then $X(\overline{G})=\chi(G)\leq 4$. The next
theorem tells us that even if $\overline{G}$ has large number of edge
crossings, all we can say is that $X(\overline{G})\geq 4$.

######  Theorem 2.

For every $k\in{\mathbb{N}}$ there is a geometric graph $\overline{G}$ with
$k$ crossings and $X(\overline{G})=4$.

###### Proof.

Let $\overline{K}_{4}$ be the convex $4$-clique with vertices labeled 1, 2, 3,
4 around the convex hull. If $k=1$, then $\overline{K}_{4}$ is the requested
geometric graph. For $k>1$, start with the star graph $\overline{K}_{1,k}$,
with its $k$ edges spanning an angle of $\frac{\pi}{2}$. Label the central
vertex 0, and the leaves $1,2,\ldots,k$. Cross those edges with a single edge
$\\{k+1,k+2\\}$. Call the resulting graph $\overline{G}$. Thus the crossings
in $\overline{G}$ are the precisely the pairs $\\{0,i\\}$, $\\{k+1,k+2\\}$ for
$i\in\\{1,\ldots,k\\}$. Define $\beta:\overline{G}\to\overline{K}_{4}$ by
$\beta(0)=1$, $\beta(i)=3$ for $i\in\\{1,\ldots,k\\}$, $\beta(k+1)=2$ and
$\beta(k+2)=4$. Thus the edges of the star are mapped to $\\{1,3\\}$, while
the edges of the crossing $K_{2}$ is mapped to $\\{2,4\\}$. Thus
$\beta:\overline{G}\to\overline{K}_{4}$ is a geometric graph homomorphism.∎

It is essential that we be able to quickly determine, without necessarily
visualizing the geometric graph, whether two edges in the graph cross. The two
following lemmas give us explicit tools. Lemma 2 will be used numerous times,
sometimes implicitly, throughout this paper.

######  Lemma 1.

If $S=\\{u,v,x,y\\}$ is a non-convex set of vertices in the plane, then no
pair of edges with both endpoints in $S$ cross.

The above is clear since the geometric $\overline{K}_{4}$ built on the
vertices in $S$ is a non-convex $\overline{K}_{4}$ and therefore has no
crossing edges.

######  Lemma 2.

Let $n\geq 4$ vertices in convex position in the plane be labeled
$1,2,\ldots,n$ around their convex hull. Let $\overline{K}_{n}$ be the convex
$n$-clique built on these vertices. Let $e_{1}=\\{a_{1},a_{2}\\}$ and
$e_{2}=\\{b_{1},b_{2}\\}$ be disjoint edges in $\overline{K}_{n}$. Without
loss of generality, we may assume that $a_{1}<a_{2}$, $b_{1}<b_{2}$ and
$a_{1}<b_{1}$. Then $e_{1}$ and $e_{2}$ cross if and only if
$a_{1}<b_{1}<a_{2}<b_{2}$.

The above is clear since a subset of a convex set is itself convex, and edges
cross if and only if their endpoints alternate as we move around their convex
hull.

##  3 Independent Crossings

######  Definition 2.

In a geometric graph $\overline{G}$ we call an edge involved in a crossing a
crossing edge and call a vertex incident to a crossing edge a crossing vertex.

######  Definition 3.

Two crossings in $\overline{G}$ are said to be at distance $d$ if the minimum
distance between any vertex in one crossing and any vertex in the other
crossing is $d$. Two crossings are said to be independent if they have no
vertices in common. That is, a two crossings are independent if they are at
distance at least 1.

Notice that if all crossings in a geometric graph are at distance at least 2,
then each crossing vertex is adjacent to exactly one other crossing vertex –
the other endpoint of the crossing edge to which it is incident. If all
crossings are at distance at least 1, then a crossing vertex may be adjacent
to many other crossing vertices – only one of which is the other endpoint of
the single crossing edge to which it is incident. Other crossing vertices to
which it may be adjacent are crossing vertices from other crossings that are
at distance 1 from it. Figure 3 shows examples of these situations.

Figure 3: At left: crossings at distance 2; at right: crossings at distance 1

######  Theorem 3.

If all pairs of crossings in $\overline{G}$ are at distance at least 2, then
$X(\overline{G})\leq\chi(G)+2$.

###### Proof.

Suppose $\chi(G)=n$. Let $\overline{K}_{n+2}$ be a convex geometric
$(n+2)$-clique with vertices labeled $1,\ldots,n+2$. Associate the complete
subgraph induced by the set $\\{1,2,\ldots,n\\}$ with $K_{n}$. By assumption
on $\chi(G)$, there is a graph homomorphism $\alpha:G\to K_{n}$.

We will modify $\alpha:G\to K_{n}$ to a homomorphism $\beta:G\to K_{n+2}$ so
that $\beta$ takes crossing of $\overline{G}$ to crossings in
$\overline{K}_{n+2}$. We will only modify $\alpha$ on crossing vertices.; the
images of non-crossing vertices will be the same under $\beta$ and $\alpha$.
The modified homomorphism $\beta$ will map some crossing vertices to one of
$n+1,n+2$. The remaining crossing vertices in that crossing will maintain
their image under $\alpha$. Since $K_{n+2}$ has edges between all pairs of
vertices, as long as the modification of $\alpha$ to $\beta$ maintains the
property that no edge has endpoints mapped to the same vertex, $\beta$ will be
a graph homomorphism. With wise choices justified by Lemma 2, we can ensure
that the resulting graph homomorphism
$\beta:\overline{G}\to\overline{K}_{n+2}$ is a geometric graph homomorphism.

Since pairs of crossing edges are at distance at least 2, they are
independent. Thus no two crossing share a vertex. Therefore, if we modify
$\alpha$ on crossing vertices in one crossing, it does not affect any
modification we may have previously made on another crossing. Further, again
since pairs of crossing edges are at distance at least 2, each crossing vertex
in $\overline{G}$ is adjacent to exactly one other crossing vertex - the other
endpoint of its crossing edge. Thus crossing vertices from distinct crossings
are nonadjacent. Thus in defining $\beta$, we run no risk of mapping two
crossing vertices from different crossings to the same vertex in
$\\{n+1,n+2\\}$. These facts allow us to modify our homomorphism $\alpha:G\to
K_{n}$ to a new homomorphism $\beta:\overline{G}\to\overline{K}_{n+2}$ one
crossing at a time.

Suppose $e_{1}=\\{u,v\\}$ and $e_{2}=\\{x,y\\}$ are a pair of crossing edges
in $\overline{G}$. Note that since $\alpha$ is a graph homomorphism, and
$K_{n}$ is a simple graph, $\alpha(x)\neq\alpha(y)$ and
$\alpha(u)\neq\alpha(v)$. Under the homomorphism $\alpha$, edge
$\alpha(e_{1})$ may have 0, 1 or 2 vertices in common with edge
$\alpha(e_{2})$. Thus the vertices $\alpha(u),\alpha(v),\alpha(x),\alpha(y)$
either induce Case 1): two non-incident edges, or Case 2): two incident edges,
or Case 3): a single edge in $K_{n}$.

Case 1) Suppose the edges are non-incident. If $\alpha(e_{1}),\alpha(e_{2})$
cross in $\overline{K}_{n}$, then we need not modify $\alpha$ on the vertices
of this crossing pair. If the disjoint edges $\alpha(e_{1}),\alpha(e_{2})$
don’t cross in $\overline{K}_{n}$ then, without loss of generality, the two
possible relationships between these edges and the additional vertices, $n+1$
and $n+2$, are illustrated in Figure 4. That is, either Case 1a): the
additional vertices fall between vertices of the two edges, without loss of
generality say between $\alpha(y)$ and $\alpha(u)$, or Case 1b): the
additional vertices fall between the endpoints of one of the edges, without
loss of generality say between $\alpha(x)$ and $\alpha(y)$.

Case 1a) Referring to Figure 4,
$1\leq\alpha(u)<\alpha(v)<\alpha(x)<\alpha(y)\leq n$. Modify the mapping so
that $\beta(v)=n+1$ and $\beta(x)=n+2$, while $\beta=\alpha$ on $u$ and $y$.
Then $\beta(u)<\beta(y)<\beta(v)<\beta(x)$ and therefore $\beta(e_{1})$ and
$\beta(e_{2})$ cross in $\overline{K}_{n+2}$.

Case 1b) Referring to Figure 4,
$1\leq\alpha(y)<\alpha(u)<\alpha(v)<\alpha(x)\leq n$. Modify the mapping so
that $\beta(v)=n+1$, while $\beta=\alpha$ on $u,x$ and $y$. Then
$\beta(y)<\beta(u)<\beta(x)<\beta(v)$ and therefore $\beta(e_{1})$ and
$\beta(e_{2})$ cross in $\overline{K}_{n+2}$.

Case 1a)Add’l Verticesaasdfassdf $\cdots$Case 1b)Add’l Verticesassdasdf
$\vdots$this$\alpha(x)\ $$\alpha(x)\ $$\alpha(v)\ $$\alpha(y)\ $$\alpha(u)\ $

Figure 4: Cases 1a) & 1b)

Case 2) Suppose $\alpha(e_{1})$ and $\alpha(e_{2})$ are distinct but incident
edges in $K_{n}$. In this case, without loss of generality, assume that
$\alpha(v)=\alpha(x)$. The two possible relationships between the associated
crossing vertices and the additional vertices, $n+1$ and $n+2$, are
illustrated in Figure 5. That is, either Case 2a): the additional vertices
fall between leaves of the path, say between $\alpha(y)$ and $\alpha(u)$, or
Case 2b): they fall between the endpoints of one of the edges, say between
$\alpha(x)$ and $\alpha(y)$.

Case 2a) Referring to Figure 5,
$1\leq\alpha(u)<(\alpha(v)=\alpha(x))<\alpha(y)\leq n$. Modify the mapping so
that $\beta(v)=n+1$ and $\beta(y)=n+2$, while $\beta=\alpha$ on $u$ and $x$.
Then $\beta(u)<\beta(x)<\beta(v)<\beta(y)$ and therefore $\beta(e_{1})$ and
$\beta(e_{2})$ cross in $\overline{K}_{n+2}$.

Case 2b) Referring to Figure 5,
$1\leq\alpha(y)<\alpha(u)<(\alpha(v)=\alpha(x))\leq n$. Modify the mapping so
that $\beta(v)=n+1$, while $\beta=\alpha$ on $u,x$ and $y$. Then
$\beta(y)<\beta(u)<\beta(x)<\beta(v)$ and therefore $\beta(e_{1})$ and
$\beta(e_{2})$ cross in $\overline{K}_{n+2}$

thisCase 2a)Add’l Verticesaasdfassdf $\cdots$Case 2b)Add’l Verticesaasdfassdf
$\vdots$$\alpha(v)=\alpha(x)$ adasdcsf$\alpha(y)\ $$\alpha(u)\ $

Figure 5: Cases 2a) & 2b)

Case 3) Suppose $\alpha(e_{1})=\alpha(e_{2})$. In this case, without loss of
generality, assume $\alpha(u)=\alpha(y)$ and $\alpha(v)=\alpha(x)$, and
$\alpha(u)<\alpha(v)$. The relationship of their crossing vertices with the
additional vertices, $n+1$ and $n+2$, is illustrated in Figure 6.

thisCase 3)Add’l Verticesaasdfassdf $\vdots$$\alpha(v)=\alpha(x)$
ada$\alpha(u)=\alpha(y)$ ada

Figure 6: Case 3)

Modify the mapping so that $\beta(y)=n+2$, and $\beta(v)={n+1}$, while
$\beta=\alpha$ on $u$ and $x$. Then $\beta(u)<\beta(x)<\beta(v)<\beta(y)$, and
thus $\beta(e_{1})$ crosses $\beta(e_{2})$.

Thus after modifying $\alpha$ to $\beta$ on each crossing, we’ve defined
$\beta:\overline{G}\to\overline{K}_{n+2}$ as a geometric graph homomorphism.
Thus $X(\overline{G})\leq\chi(G)+2$.∎

There are easy examples of geometric graphs where this bound is not best
possible. A plane geometric graph, and a convex $\overline{K}_{4}$ fall into
this category. It would be interesting to find criteria for when this result
is best possible.

Now we move to considering geometric graphs in which all crossings are
independent, but not necessarily at distance at least 2. The technique used in
the proofs of Theorems 4 and 5 is similar to the one used in the proof of
Theorem 3. The difference is that in Theorem 3 since the minimum distance
between two pairs of crossing edges was 2, no pair of crossing vertices from
distinct edge crossings could be adjacent. Thus there was no risk that in
modifying $\alpha$ to achieve $\beta$ on distinct crossing pairs we might map
adjacent crossing vertices to the same vertex in our geometric clique. When
crossings are independent but not of distance at least 2, we have to be a bit
more careful. In this situation, crossing vertices from distinct crossings may
indeed be adjacent. One solution to this is to base the modification of
$\alpha(v)$ on the image $\alpha(v)$ itself. In this technique, for all $v\in
V(G)$ we will define $\beta(v)$ to be in
$\\{\alpha(v),\alpha(v)+n,\alpha(v)+2n\\}$. Since $\alpha:G\to K_{n}$ is a
homomorphism, if $u,v$ are adjacent vertices in $G$, then
$\alpha(v)\neq\alpha(u)$, and each is between $1$ and $n$. Then the set of the
potential images $\beta(u)$ and $\beta(v)$ are
$\\{\alpha(u),\alpha(u)+n,\alpha(u)+2n\\}$ and
$\\{\alpha(v),\alpha(v)+n,\alpha(v)+2n\\}$. Since these sets are disjoint,
$\beta(v)\neq\beta(u)$ as desired. This is the key behind the following proof.

######  Theorem 4.

Let $\overline{G}$ be a geometric graph with independent crossings. Let $n$ be
an integer so that there exists a homomorphism $\alpha:G\to K_{n}$ in which no
pair of crossing edges are mapped to the same edge. Then $X(G)\leq 2n$.

###### Proof.

Let $\overline{K}_{2n}$ be a convex geometric $2n$-clique with vertices
labeled $1,\ldots,2n$ around the convex hull. Associate the complete subgraph
induced on the convex set $\\{1,2,\ldots,n\\}$ with $K_{n}$. By assumption,
there is a graph homomorphism $\alpha:G\to K_{n}$ in which no pair of edges
that cross in $\overline{G}$ are mapped to the same edge in $K_{n}$. We will
modify this to a geometric graph homomorphism
$\beta:\overline{G}\to\overline{K}_{2n}$.

For this proof we will define $\beta:G\to K_{2n}$ by adding $n$ to images
under $\alpha$ of some crossing vertices. As argued earlier, for any $u,v\in
V(G)$ for which $\alpha(u)\neq\alpha(v)$, with
$\beta(u)\in\\{\alpha(u),\alpha(u)+n\\}$ and
$\beta(v)\in\\{\alpha(v),\alpha(v)+n\\}$, we have $\beta(u)\neq\beta(v)$. Thus
since $\alpha$ is a graph homomorphism and $\beta$ maintains inequality of
vertex images, $\beta$ is also a graph homomorphism.

Let $e_{1}=\\{u,v\\},e_{2}=\\{x,y\\}$ be crossing edges in $\overline{G}$. By
our assumption on $\alpha$, it sends no pair of crossing edges in
$\overline{G}$ to the same edge of $\overline{K}_{n}$. Then $\alpha(e_{1})$
and $\alpha(e_{2})$ share at most one vertex. Thus we have two cases, Case 1):
$\alpha(e_{1})$ and $\alpha(e_{2})$ are disjoint, or Case 2): $\alpha(e_{1})$
and $\alpha(e_{2})$ share precisely one vertex. These are identical to Case 1)
and Case 2) of the proof of Theorem 3. Further, the relationships between the
additional vertices $n+1,\ldots,2n$ and the vertices of $\alpha(e_{1})$ and
$\alpha(e_{2})$ fall into exactly the same subcases here as they did in the
proof of Theorem 3.

Case 1a) Referring to Figure 4 we see that
$1\leq\alpha(u)<\alpha(v)<\alpha(x)<\alpha(y)\leq n$. Define $\beta$ so that
$\beta(v)=\alpha(v)+n$ and $\beta(x)=\alpha(x)+n$, while $\beta=\alpha$ on $u$
and $y$. Then $\beta(u)<\beta(y)<\beta(v)<\beta(x)$ and therefore
$\beta(e_{1})$ and $\beta(e_{2})$ cross.

Case 1b) Referring to Figure 4 we see that
$1\leq\alpha(y)<\alpha(u)<\alpha(v)<\alpha(x)\leq n$. Define $\beta$ so that
$\beta(v)=\alpha(v)+n$, while $\beta=\alpha$ on $u,x$ and $y$. Then
$\beta(y)<\beta(u)<\beta(x)<\beta(v)$ and therefore $\beta(e_{1})$ and
$\beta(e_{2})$ cross.

Case 2a) Referring to Figure 5, we see that
$1\leq\alpha(u)<(\alpha(v)=\alpha(x))<\alpha(y)\leq n$. Define
$\beta(v)=\alpha(v)+n$ and $\beta(y)=\alpha(y)+n$ while $\beta=\alpha$ on $u$
and $x$. Then $\beta(u)<\beta(x)<\beta(v)<\beta(y)$ and therefore
$\beta(e_{1})$ and $\beta(e_{2})$ cross.

Case 2b) Referring to Figure 5, we see that
$1\leq\alpha(y)<\alpha(u)<(\alpha(v)=\alpha(x))\leq n$. Define
$\beta(v)=\alpha(v)+n$, while $\beta=\alpha$ on $u,x$ and $y$. Then
$\beta(y)<\beta(u)<\beta(x)<\beta(v)$ and therefore $\beta(e_{1})$ and
$\beta(e_{2})$ cross.

Thus $\beta:\overline{G}\to\overline{K}_{2n}$ is a geometric graph
homomorphism.∎

Note that the above technique does not always work if a pair of crossing edges
are mapped to a single edge in $K_{n}$ by the homomorphism $\alpha$. For
example, if a pair of crossing edges are mapped to $\\{2,4\\}$ in
$\overline{K}_{10}$ and we added $n=5$ to a subset of
$\alpha(u),\alpha(v),\alpha(x)$ and $\alpha(y)$, the only valid results would
be either a single edge, a path of length 2, or two disjoint edges. In
particular, the result cannot be a crossing pair in $\overline{K}_{10}$.
However, if $\chi(G)=2$ or $3$ this will not be a problem. This is stated as
Theorem 6. But first, the following theorem gives slightly weaker conclusion
in the more general case where we allow homomorphisms that map crossing edges
in $\overline{G}$ to the same edge in $K_{n}$.

######  Theorem 5.

If $\overline{G}$ is a geometric graph with independent crossings, then
$X(G)\leq 3\chi(G)$.

###### Proof.

Let $\chi(G)=n$. Let $\overline{K}_{3n}$ be a convex geometric $3n$-clique
with vertices labeled $1,\ldots,3n$. Associate the $n$-clique induced by the
convex set $\\{1,2,\ldots,n\\}$ with $K_{n}$. Since $\chi(G)=n$, there is a
graph homomorphism $\alpha:G\to K_{n}$. We will modify this to a geometric
homomorphism $\beta:\overline{G}\to\overline{K}_{3n}$.

We will redefine $\alpha$ to $\beta$ on certain crossing vertices of
$\overline{G}$, by adding 0, or $n$ or $2n$ to $\alpha(v)$. With this
definition, as argued previously, if $\alpha(u)\neq\alpha(v)$ then
$\beta(v)\neq\beta(u)$. This guarantees that $\beta$ preserves inequality
given by $\alpha$, and is thus a graph homomorphism. With careful choice, we
can ensure $\beta:\overline{G}\to\overline{K}_{3n}$ is a geometric
homomorphism.

Let $e_{1}=\\{u,v\\},e_{2}=\\{x,y\\}$ be crossing edges in $\overline{G}$.
Note that $\alpha(e_{1})$ and $\alpha(e_{2})$ are either disjoint, share
precisely one vertex, or share both vertices.

Associate the geometric $2n$-clique induced by the convex set
$\\{1,2,\ldots,2n\\}$ with $\overline{K}_{2n}$. If $\alpha(e_{1})$ and
$\alpha(e_{2})$ share at most one vertex, use the method of Theorem 4 to
modify the homomorphism $\alpha:G\to K_{n}$ to a geometric homomorphism
$\beta:\overline{G}\to\overline{K}_{2n}$ where we identify the convex induced
subgraph of $\overline{K}_{3m}$ by the vertices $\\{1,2,\ldots,2n\\}$ as
$\overline{K}_{2n}$. By Theorem 4, this modified homomorphism maps crossing
edges of $\overline{G}$ whose images under $\alpha$ are not identical, to
crossing edges in $\overline{K}_{2n}\subseteq\overline{K}_{3n}$.

Now consider the one case that is not covered in Theorem 4. Suppose that
$\alpha(e_{1})=\alpha(e_{2})$. Without loss of generality, suppose that
$\alpha(u)=\alpha(y)$ and $\alpha(v)=\alpha(x)$ and $\alpha(u)<\alpha(v)$.
Define $\beta(x)=\alpha(x)+n,\beta(u)=\alpha(u)+2n$, while $\beta=\alpha$ on
$y$ and $v$. Then $\beta(y)<\beta(v)<\beta(x)<\beta(u)$. Thus $\beta(e_{1})$
and $\beta(e_{2})$ cross.

Thus after modifying $\alpha$ to $\beta$ on each crossing, we have
$\beta:\overline{G}\to\overline{K}_{3n}$ as a geometric graph homomorphism.∎

Our final theorem regards geometric graphs whose underlying abstract graph has
chromatic number 2 or 3. The technique used to prove the following theorem is
slightly different than the one used earlier. In particular we embed
$\overline{K}_{\chi(G)}$ into $\overline{K}_{2\chi(G)}$ in a slightly
different way and then add 1 to certain crossing vertices. This technique
works well for situations when we can be assured that images of crossing edges
are either incident or identical. It does not always work when images of
crossing edges are disjoint.

######  Theorem 6.

If $\overline{G}$ has independent crossings and $\chi(G)\in\\{2,3\\}$, then
$X(\overline{G})\leq 2\chi(G)$.

###### Proof.

As argued in the previous theorems, because the crossings of $\overline{G}$
are independent, given a graph homomorphism $\alpha:G\to K_{\chi(G)}$, we may
modify $\alpha$ to $\beta$ on vertices of one crossing at a time, with the
images under $\beta$ based on the images under $\alpha$. Our result will be
$\beta:\overline{G}\to K_{2\chi(G)}$, a geometric graph homomorphism. Below
this is done explicitly in each of the cases $\chi(G)=3$ and $\chi(G)=2$.

If $\chi(G)=3$, begin with $\alpha:G\to K_{3}$ and modify to
$\beta:\overline{G}\to\overline{K}_{6}$, the convex 6-clique with vertices
labeled 1, 2, 3, 4, 5, 6 around the convex hull. Here we will consider the
$3$-clique on vertices $1,3,5$ to be $K_{3}$.

Consider a crossing in $\overline{G}$ with edges $e_{1}=\\{u,v\\}$ and
$e_{2}=\\{x,y\\}$. Either $\alpha(e_{1})$ and $\alpha(e_{2})$ are incident in
$K_{3}$ or they are identical. If they are incident, without loss of
generality, assume $\alpha(u)=1,\alpha(v)=\alpha(x)=3$ and $\alpha(y)=5$.
Modify so that $\beta(x)=\alpha(x)+1=4$ while $\beta=\alpha$ on $u,v$ and $y$.
Then $\beta(e_{1})=\\{1,3\\}$ and $\beta(e_{2})=\\{2,5\\}$, a pair of crossing
edges in $\overline{K}_{6}$. If $\alpha(e_{1})$ and $\alpha(e_{2})$ are
identical, without loss of generality, we may assume $\alpha(u)=\alpha(y)=1$
and $\alpha(v)=\alpha(x)=3$. Modify so that $\beta(y)=\alpha(y)+1=2$, and
$\beta(x)=\alpha(x)+1=4$ while $\beta=\alpha$ on $u$ and $v$. Then
$\beta(e_{1})=\\{1,3\\}$ and $\beta(e_{2})=\\{2,4\\}$, crossing edges in
$\overline{K}_{6}$. After applying this process to each crossing in
$\overline{G}$, we have achieved $\beta:\overline{G}\to\overline{K}_{6}$, a
geometric graph homomorphism.

For the case $\chi(G)=2$, we begin with $\alpha:G\to K_{2}$ and modify to
$\beta:\overline{G}\to\overline{K}_{4}$, the convex 4-clique with vertices
labeled 1, 2, 3, 4 around the convex hull. Here we will consider the
$2$-clique on vertices $1,3$ to be $K_{2}$. Since $\alpha$ necessarily maps
crossing edges of $\overline{G}$ to the same edge of $K_{2}$, we can assume
crossing edges $e_{1}=\\{u,v\\}$ and $e_{2}=\\{x,y\\}$ with
$\alpha(u)=\alpha(y)=1$ and $\alpha(v)=\alpha(x)=3$. Define
$\beta(y)=\alpha(y)+1=2$ and $\beta(x)=\alpha(x)+1=4$, while $\beta=\alpha$ on
$u$ and $v$. Thus $\beta(e_{1})=\\{1,3\\}$ and $\beta(e_{2})=\\{2,4\\}$,
crossing edges in $\overline{K}_{4}$. After applying this process to each
crossing in $\overline{G}$, we have achieved
$\beta:\overline{G}\to\overline{K}_{4}$, a geometric graph homomorphism. . ∎

##  4 Pseudo-geochromatic number

It is natural to expect that the definition of $X(\overline{G})$ might be the
same as ‘the smallest integer $n$ so that the vertices of $\overline{G}$ can
be colored with $n$ colors so that distinct colors are given to all vertex
pairs corresponding to edges and to all vertex quadruples corresponding to
crossing edges.’ Call this parameter the pseudo-geochromatic number,
$X^{\prime}(G)$. However, in general $X(\overline{G})\neq
X^{\prime}(\overline{G})$. Consider $\overline{G}$ the geometric graph in
Figure 7. The coloring of the vertices as shown meets the conditions of a
pseudo-geochromatic coloring. A little arguing shows
$X^{\prime}(\overline{G})=5$. However, as shown in Theorem 1(d), the two
vertices colored 5 cannot be identified under any geometric homomorphism.
Further, by Theorem 1(b), no other vertex pair of $\overline{G}$ can be
identified by any homomorphism since each pair is involved in a common
crossing. Thus, we conclude that $X(\overline{G})=6$. This shows that the
conditions for the pseudo-geochromatic number are weaker than the those of the
geochromatic number.

$1$$2$$3$$5$$5$$4$

Figure 7: $X^{\prime}(\overline{G})<X(\overline{G})$

Using this example as inspiration, we can create a family of geometric graphs
with $X(\overline{G})$ arbitrarily larger than $X^{\prime}(\overline{G})$.

$1$$2$$3$$4$$2m+1$$2m+2$$2m+3$$2m+4$$m+1$$m+2$$m+3$$m+4$

Figure 8:

######  Theorem 7.

For any $n\in{\mathbb{Z}}^{+}$ there is a geometric graph $\overline{G}$ for
which $X(\overline{G})-X^{\prime}(\overline{G})=n$.

###### Proof.

Let $n\in{\mathbb{Z}}^{+}$, and $m=n+1$. Construct the geometric graph on $3m$
vertices given in Figure 8. There is the obvious geometric homomorphism to the
convex $K_{3m}$. Thus $X(\overline{G})\leq 3m$.

Let $p:V(\overline{G})\to\\{1,2,\ldots,3m\\}$ be a psuedo-geochromatic
coloring, and $g:V(\overline{G})\to\\{1,2,\ldots,3m\\}$ a geochromatic
coloring.

Let us start with the induced subgraph on $v_{1},v_{m+1},v_{2m+1}$. Since
these vertices form a 3-cycle, each must have a different color under either
coloring. Let $p(v_{1})=g(v_{1})=1$, $p(v_{m+1})=g(v_{m+1})=m+1$, and
$p(v_{2m+1})=g(v_{2m+1})=2m+1$. We will add, and color, the paths of length 2
one at time. Add the path on $v_{2},v_{m+2}$, and $v_{2m+2}$. As drawn, the
edge $\\{v_{2},v_{m+2}\\}$ will cross both $\\{1,m+2\\}$ and $\\{m+1,2m+2\\}$
Thus under both colorings, $v_{2}$ cannot be colored $1,m+1$, or $2m+1$. So
let $p(v_{2})=g(v_{2})=2$. Since the edges $\\{v_{2},v_{m+2}\\}$ and
$\\{v_{2},v_{2m+2}\\}$ do not cross, we may let $p(v_{m+2})=p(v_{2m+2})=m+2$.
However, by Theorem 1(d) since this path of length 2 crosses each edge of our
$C_{3}$, the colors $g(v_{m+1}),g(v_{2m+1})$ must be distinct. Thus let
$g(v_{m+2})=m+2$ and $g(v_{2m+2})=2m+2$. We continue in this manner with each
new path of length 2. For $3\leq i\leq m-1$, consider
$v_{i},v_{m+i},v_{2m+i}$. Because its incident edges cross edges incident to
all previous vertex colors $v_{i}$ will have to be colored differently than
any previous vertex. Thus let $p(v_{i})=g(v_{i})=i$. Since under the coloring
$p$, $\\{v_{1},v_{m+i}\\}$ and $\\{v_{i},v_{2m+i}\\}$ cross edges incident to
vertices colored $\\{1,2,\ldots,i\\}\cup\\{{m+1},\ldots,{m+i-1}\\}$ the two
endpoints of the path must also be colored differently from all
$\\{1,2,\ldots,i\\}\cup\\{{m+1},\ldots,{m+i-1}\\}$. Since the edges
$\\{v_{i},v_{m+i}\\},\\{v_{i},v_{2m+i}\\}$ do not cross, we may let
$p(v_{m+i})=p(v_{2m+i})=m+i$. However, since the edges
$\\{v_{i},v_{m+i}\\},\\{v_{i},v_{2m+i}\\}$ cross every edge of our $C_{3}$,
they cannot be identified by $g$. Thus let $g(v_{m+i})=m+i$ and
$g(v_{2m+i})=2m+i$.

In the coloring $g$ we used all $3m$ available colors; thus
$X(\overline{G})=3m$. While in $p$ we never needed the colors
$2m+2,\ldots,3m$; thus $X^{\prime}(\overline{G})=3m-(m-1)$. Therefore
$X(\overline{G})-X^{\prime}(\overline{G})=m-1=n$, as desired. ∎

##  5 Conflict of Interest

The authors have no conflict of interest to declare.

## References

  * [1] Debra L. Boutin and Sally Cockburn.  Geometric graph homomorphisms.  J. Graph Theory, 69(2):97–113, 2012.
  * [2] Debra L. Boutin, Sally Cockburn, Alice M. Dean, and Andrei M. Margea.  Posets of geometric graphs.  Ars Math. Contemp., 5(2):265–284, 2012.
  * [3] Sally Cockburn.  Preimages of small geometric cycles.  J. Combin. Math. Combin. Comput., 101:233–244, 2017.
  * [4] Sally Cockburn.  Homomorphic preimages of geometric paths.  Discuss. Math. Graph Theory, 38(2):553–571, 2018.
  * [5] Sally Cockburn and Yonghyun Song.  The homomorphism poset of $K_{2,n}$.  Australas. J. Combin., 57:79–108, 2013.
  * [6] Pavol Hell and Jaroslav Nešetřil.  Graphs and homomorphisms, volume 28 of Oxford Lecture Series in Mathematics and its Applications.  Oxford University Press, Oxford, 2004.
  * [7] János Pach.  Finite point configurations.  In Handbook of discrete and computational geometry, 2nd Edition, CRC Press Ser. Discrete Math. Appl., pages 219–238. CRC, Boca Raton, FL, 2004.
  * [8] János Pach, editor.  Towards a theory of geometric graphs.  Contemporary Mathematics 342. American Mathematical Society, Providence, RI, 2004.
  * [9] Larry Stockmeyer.  Planar 3-colorability is polynomial complete.  ACM SIGACT News archive, 5(3):19–25, 1973.


# The objective function equality property of infoGAN for two-layer network

###### Abstract

Information Maximizing Generative Adversarial Network (infoGAN) can be
understood as a minimax problem involving two networks: discriminators and
generators with mutual information functions. The infoGAN incorporates various
components, including latent variables, mutual information, and objective
function. This research demonstrates that the two objective functions in
infoGAN become equivalent as the discriminator and generator sample size
approaches infinity. This equivalence is established by considering the
disparity between the empirical and population versions of the objective
function. The bound on this difference is determined by the Rademacher
complexity of discriminator and generator function class. Furthermore, the
utilization of a two-layer network for both the discriminator and generator,
featuring Lipschitz and non-decreasing activation functions, validates this
equality.

Mahmud Hasan

Department of Mathematics, University of Mississippi, University, MS, 38677,
USA

<EMAIL_ADDRESS>

Keywords: discriminator,infoGAN, GAN, generator, objective function,
Rademacher complexity.

##  1 Introduction

InfoGAN, which stands for Information Maximizing Generative Adversarial
Network [20], is an expansion of the conventional Generative Adversarial
Network (GAN) framework [1]. InfoGAN’s primary objective is to uncover and
manage the structured representations inherent in the data it generates. In
the realm of GANs, there exist various variants based on statistical
properties, such as Conditional GAN (CGAN) as discussed in [3], the $f$-GAN as
explored in [4], and Wasserstein GAN (WGAN). InfoGAN itself has also given
rise to variants like Causal InfoGAN, as described in [5], and Semi-Supervised
InfoGAN (ss-InfoGAN) as detailed in [6].

The InfoGAN has also similar applications like vanilla GAN such as data
imaging, natural language processing, and medical images ([10], [11], [12]). A
recent review on GAN and their applications would be helpful, as discussed in
[21]. However, it’s worth noting that theoretical analysis of InfoGAN remains
relatively rare in the literature. A potential direction for theoretical
examination involves assessing the equivalence of InfoGAN’s objective
functions, comparing the expected objective function to the empirical one, as
elaborated upon later.

Define the generator is $G$ with the sample size $m$ and discriminator $D$
with the sample size $n$ that aims to distinguish between $p_{x}$ and
generator distribution $p_{z}$. Let $z$ be a noise variable that transforms by
the generator distribution $p_{z}$ and real variable X. Consider the GAN
models with both the generator and discriminator function classes
parameterized. The mini-max problem of GAN which is introduced in [1] can be
written as,

$d(D,G)=\min_{G}\max_{D}\left[\mathbb{E}_{p_{x}}[\log
D(x)]+\mathbb{E}_{p_{z}}[1-\log D(G(z))]\right].$ (1)

The infoGAN provides the generator network divide noise variable $z$ into the
incomprehensible noise $z$ and the latent code $c$, so the form of the
generator becomes $G(z,c)$. The info-GAN aims to solve

$d_{I}(D,G)=\min_{G}\max_{D}\left[\mathbb{E}_{p_{x}}[\log
D(x)]+\mathbb{E}_{p_{z}}[1-\log D(G(z))]-\lambda I(c;G(z,c))\right],$ (2)

where $I(c;G(z,c))=H(c)-H(c|G(z,c))$ is the mutual information and $\lambda$
is the regularization term. However, optimizing the $I(c;G(z,c))$ is difficult
since it requires the posterior distribution $P(c|x)$.

In this case, a lower bound $L_{I}(c;Q)$ is obtained for $I(c;G(z,c))$ by
defining an auxiliary distribution $Q(c|x)$ to approximate $P(c|x)$. Then the
objective function of info-GAN written as

$d_{I}(D,G)=\min_{G}\max_{D}\left[\mathbb{E}_{p_{x}}[\log
D(x)]+\mathbb{E}_{p_{z}}[1-\log D(G(z))]-\lambda L_{I}(c;Q)\right].$ (3)

While Equation (3) serves as the primary objective function commonly used in
practical applications, this paper opts to consider and subsequently employ
Equation (2) as the core objective function for its primary findings. This
objective function introduces regularization in the generator variable, a
departure from the majority of existing literature, which typically lacks such
regularization. The existing theoretical research is only based on vanilla GAN
error analysis defined by taking the difference of two objective functions
like in [14], [16], [15], [17]. In this paper, the objective function (2) is
used for equality property for the infoGAN without latent variable $c$ for two
two-layer networks. The objective function in (3) has a noise variable divided
into incomprehensible and latent code $c$. But since the generator creates
mostly fake data and the discriminator classifies it it might not be possible
to have latent code. Besides, $\log x\rightarrow 0$ as $x\rightarrow 0$ which
makes problems in practice. So develop a new objective function without latent
code. The equality property is defined as the equality of the population
version objective function and empirical objective function. The difference
between the population version objective function and the empirical objective
function is bounded by the Rademacher complexity. The Rademacher complexity
bound was derived for the two-layer networks in the case of Lipschitz and the
non-decreasing activation function.

The major contributions of this paper and the format of the paper can be
summarized as follows:

  * •

Section 2 presents the derivation of a regularized objective function from
infoGAN, excluding the latent code.

  * •

Section 3 demonstrates that the difference between the empirical and
population objective functions is bounded by the Rademacher complexity of the
discriminator, generator and both.

  * •

Section 4, formulates the discriminator and generator classes for a two-layer
network. The corresponding weight parameters of the network are constrained by
constants.

  * •

Section 4, we derive upper bounds for the Rademacher complexities in two
cases: $1$-Lipschitz and non-decreasing activation functions. These bounds are
then applied to establish the equality of the objective function differences
for both cases under infinite discriminator and generator sample sizes. Out of
the two equalities presented, one was established for the equality of the
empirical objective function for both the discriminator and generator samples,
while the other equality pertained solely to the empirical objective function
for the discriminator sample.

  * •

Section 5 provides the conclusion and future research direction.

##  2 Objective Function without Latent Code

In the original infoGAN framework, instead of using a single unstructured
noise vector $z$, the authors divided the input noise vector into two parts:
incompressible noise denoted as $z$ and latent code denoted as $c$. The
generator aims to continually update itself to confuse the discriminator. This
suggests that the noise alone cannot produce the latent code $c$ initially. In
some cases, this complexity can be reduced by assuming the absence of the
latent variable, effectively setting $c$ to zero. In this scenario, Equation
(2) becomes:

$\displaystyle d_{I}(D,G)$
$\displaystyle=\min_{G}\max_{D}\left[\mathbb{E}_{p_{x}}[\log
D(x)]+\mathbb{E}_{p_{z}}[1-\log D(G(z))]-\lambda I(0;G(z,0))\right]$
$\displaystyle=\min_{G}\max_{D}\left[\mathbb{E}_{p_{x}}[\log
D(x)]+\mathbb{E}_{p_{z}}[1-\log D(G(z))]-\lambda H(0)+\lambda
H(G(z,0))\right]$ $\displaystyle=\min_{G}\max_{D}\left[\mathbb{E}_{p_{x}}[\log
D(x)]+\mathbb{E}_{p_{z}}[1-\log D(G(z))]+\lambda H(0|G(z,0))\right]$
$\displaystyle=\min_{G}\max_{D}\left[\mathbb{E}_{p_{x}}[\log
D(x)]+\mathbb{E}_{p_{z}}[1-\log D(G(z))]+\lambda H(G(z))\right]$
$\displaystyle=\min_{G}\max_{D}\left[\mathbb{E}_{p_{x}}[\log
D(x)]+\mathbb{E}_{p_{z}}[1-\log
D(G(z))]-\lambda\mathbb{E}_{p_{z}}\log[G(z)]\right].$ (4)

Here, mutual information can be represented equivalently as:
$I(0;G(z,0))=H(0)-H(0|G(z,0))$, where $H$ denotes entropy. Equation (4)
presents the objective function with generator regularization in the case
where the latent code is zero. However, this can lead to issues in practice,
as $\log x\rightarrow 0$ as $x\rightarrow 0$. By replacing $\log$ with a
monotone function $\phi:[0,1]\rightarrow\mathbb{R}$, the objective becomes:

$\displaystyle d_{I}(D,G)$
$\displaystyle=\min_{G}\max_{D}\left[\mathbb{E}_{p_{x}}[\phi
D(x)]+\mathbb{E}_{p_{z}}[1-\phi
D(G(z))]-\lambda\mathbb{E}_{p_{z}}\phi[G(z)]\right].$ (5)

Here, $\phi$ is the measuring function. This can also be written as [10]:

$\displaystyle d_{I}(D,G)$
$\displaystyle=\min_{G}\max_{D}\left[\mathbb{E}_{p_{x}}[\phi
D(x)]+\mathbb{E}_{p_{z}}[1-\phi
D(G(z))]-\lambda\mathbb{E}_{p_{z}}\phi[G(z)]-2\phi(1/2)\right].$ (6)

For $\phi(x)=x$, the final objective function with changing the notations
becomes:

$\displaystyle d_{I}(D,G)$
$\displaystyle=\min_{G}\max_{D}\left[\mathbb{E}_{p_{x}}[D(x)]-\mathbb{E}_{p_{z}}[D(G(z))]-\lambda\mathbb{E}_{p_{z}}G(z)\right].$
(7)

Equation (7) represents the neural network distance with generator
regularization. This equation can be directly applied to enforce
regularization on either the discriminator or the generator. However, it’s
important to note that regularization is specifically relevant to the
generator when there is no latent code involved. In other words, the
regularized objective function is suitable when an unstructured noise variable
is utilized as input in the generator neural network. Suppose that $n$ is the
independent and identical observations $X_{i}\sim p_{x}$, $1\leq i\leq n$, and
the generator produces $m$ independent and identical terms $G(z)\sim p_{z}$,
$1\leq j\leq m$.

We define the two empirical loss functions as follows, based on Equation (7):

$\displaystyle d_{I_{c}}(\hat{D},\hat{G})$
$\displaystyle=\min_{G}\max_{D}\left[\frac{1}{n}\sum_{i=1}^{n}D(x_{i})-\frac{1}{n}\sum_{i=1}^{m}D(G(z_{j}))-\lambda\frac{1}{m}\sum_{i=1}^{n}G(z_{j})\right].$
(8)

and

$\displaystyle d_{I_{c}}(\hat{D},G)$
$\displaystyle=\min_{G}\max_{D}\left[\frac{1}{n}\sum_{i=1}^{n}D(x_{i})-\mathbb{E}_{p_{z}}[D(G(z))]-\lambda\mathbb{E}_{p_{z}}G(z)\right].$
(9)

The equation (8) refers to the empirical objective function for the
discriminator and generator class and (9) refers to the empirical objective
function for the discriminator class. Here, $D(G(z))=D\circ G$ is the
composition of the discriminator and generator.

##  3  Bound of objective function difference

The equality property of infoGAN arises by subtracting (7) from (8).
Considering $\hat{D}$ and $\hat{G}$ as empirical distributions of $D$ and $G$,
respectively, the difference in the objective function can be represented as:

$\displaystyle d_{I_{c}}(\hat{D},\hat{G})-d_{I_{c}}(D,G)$ (10) $\displaystyle
d_{I_{c}}(\hat{D},G)-d_{I_{c}}(D,G)$ (11)

In (10), this indicates the disparity between the empirical distributions of
the discriminator and generator. Meanwhile, (11) exclusively considers the
discriminator. The subsequent two theorems establish boundaries for (10) and
(11), assuming that both the discriminator $D$ and generator $G$ are uniformly
bounded. The proofs for these theorems employ the Cauchy-Schwartz inequality
and McDiarmid’s inequality.

###### Theorem 3.1

Suppose the sets of discriminator functions $D$ and $G$ are symmetric with
$\lVert f\rVert_{\infty}\leq{\mathbb{Q}}_{x}$ and $\lVert
g\rVert_{\infty}\leq{\mathbb{Q}}_{Z}$. Then, for any $f\in D$, $g\in G$, with
probability at least $1-2\delta$ over the random training sample, we have

$\displaystyle d_{I_{c}}(\hat{D},\hat{G})-d_{I_{c}}(D,G)\leq
2{\mathcal{R}_{n}}(D)+2\mathcal{R}_{mn}(D\circ G)-2{\mathcal{R}_{m}}(G)$
$\displaystyle+2Q_{x}\sqrt{\frac{\log(1/\delta)}{2n}}-2Q_{z}(1+\lambda)\sqrt{\frac{\log(1/\delta)}{2m}}$
(12)

and

$\displaystyle d_{I_{c}}(\hat{D},G)-d_{I_{c}}(D,G)\leq
2{\mathcal{R}_{n}}(D)+2Q_{x}\sqrt{\frac{\log(1/\delta)}{2n}}$ (13)

#### Proof.

To prove Theorem 3.1, the supremum properties are utilized:

$\displaystyle d_{I_{c}}(\hat{D},\hat{G})-d_{I_{c}}(D,G)$
$\displaystyle=\sup_{D}\left[\frac{1}{n}\sum_{i=1}^{n}D(x_{i})-\frac{1}{n}\sum_{i=1}^{m}D(G(z_{j}))-\lambda\frac{1}{m}\sum_{i=1}^{n}G(z_{j})\right]$
$\displaystyle\quad-\sup_{D}\left[\mathbb{E}_{p_{x}}D(x)-\mathbb{E}_{p_{z}}D(G(z))-\lambda\mathbb{E}_{p_{z}}G(z)\right]$
$\displaystyle\leq\sup_{D}\left[\frac{1}{n}\sum_{i=1}^{n}D(x_{i})-\mathbb{E}_{p_{x}}D(x)\right]$
$\displaystyle\quad-\sup_{D}\left[\frac{1}{n}\sum_{i=1}^{m}D(G(z_{j}))+\lambda\frac{1}{m}\sum_{i=1}^{n}G(z_{j})-\mathbb{E}_{p_{z}}D(G(z))-\lambda\mathbb{E}_{p_{z}}G(z)\right]$
$\displaystyle\leq\sup_{D}\left[\frac{1}{n}\sum_{i=1}^{n}D(x_{i})-\mathbb{E}_{p_{x}}D(x)\right]$
$\displaystyle\quad-\sup_{D}\left[\frac{1}{n}\sum_{i=1}^{m}D(G(z_{j}))-\mathbb{E}_{p_{z}}D(G(z))\right]$
$\displaystyle\quad-\lambda\left[\frac{1}{m}\sum_{i=1}^{n}G(z_{j})-\mathbb{E}_{p_{z}}G(z)\right].$
(14)

The bounds of the following can be proved using Theorem 3.1 in [17]:

$\displaystyle\sup_{D}\left[\frac{1}{n}\sum_{i=1}^{n}D(x_{i})-\mathbb{E}_{p_{x}}D(x)\right]\leq
2{\mathcal{R}_{n}}(D)+2Q_{x}\sqrt{\frac{\log(1/\delta)}{2n}}.$ (15)

$\displaystyle\sup_{D}\left[\frac{1}{n}\sum_{i=1}^{m}D(G(z_{j}))-\mathbb{E}_{p_{z}}D(G(z))\right]\leq
2\mathcal{R}_{mn}(D\circ G)+2Q_{z}\sqrt{\frac{\log(1/\delta)}{2m}}.$ (16)
$\displaystyle\left[\frac{1}{m}\sum_{i=1}^{n}G(z_{j})-\mathbb{E}_{p_{z}}G(z)\right]\leq
2{\mathcal{R}_{m}}(D)+2Q_{z}\sqrt{\frac{\log(1/\delta)}{2m}}.$ (17)

Substituting (15), (16), and (17) into (14), the bound of (12) is proved.
Similarly, the bound of (13) can be proved using (15).

###### Remark 3.1

The inequalities in (12) and (13) are bounded by the Rademacher complexity of
the discriminator and generator with respect to the sample size. However, when
both $m$ and $n$ tend to infinity, ${\mathcal{R}_{n}}(D)$,
$\mathcal{R}_{mn}(D\circ G)$, and ${\mathcal{R}_{m}}(G)$ approach 0, which
makes the two objective functions in (7) and (8) equal:

$\displaystyle d_{I_{c}}(\hat{D},\hat{G})=d_{I_{c}}(D,G)$ $\displaystyle
d_{I_{c}}(\hat{D},G)=d_{I_{c}}(D,G).$

##  4 Application in a Two-Layer Network

The derived bounds in Theorem 3.1 provide valuable insights when applying the
infoGAN framework in (7) to a two-layer neural network architecture. In this
section, we discuss how these bounds can be useful in analyzing and improving
the performance of such networks. The goal is to minimize the objective
function disparity between the empirical distributions of $\hat{D}$ and
$\hat{G}$, as well as the objective function difference between $\hat{D}$ and
$G$. The derived bounds, as shown in equations (12) and (13), provide upper
limits on the disparity and difference in the objective functions,
respectively. These bounds allow us to assess the potential deviation between
the empirical and true objective functions. Furthermore, the analysis of these
bounds offers insights into the convergence behavior of the two-layer network.

###  4.1 Formation of Two-Layer Network

A two-layer neural network details in [19], [18] consists of two layers of
neurons or nodes: an input layer and an output layer. Consider a two-layer
network for both the discriminator and generator classes, where the first
layer’s units compute arbitrary functions from a given set. Let $v_{i}$ and
$w_{i}$ be weight parameter vectors for the first and second layers of a two-
layer neural network. Suppose $D_{1}$ is a class of [0,1]-valued functions
defined on a set $X$ as follows:

$\displaystyle D_{1}$ $\displaystyle=\left\\{x\rightarrow
s_{1}\left(\sum_{i=1}^{n}v_{i}x_{i}+v_{0}\right):v_{i}\in\mathbb{R},x\in[0,1]^{n},\sum_{i=0}^{n}\lvert
v_{i}\rvert\leq V\right\\}$ (18)

Then define a broader class $D$ as follows:

$\displaystyle D$
$\displaystyle=\left\\{\sum_{i=1}^{l}w_{i}f_{i}+w_{0}:l\in\mathbb{N},f_{i}\in
D_{1},\lvert w_{i}\rvert\leq V\right\\}$ (19)

Similarly, let $p_{j}$ and $r_{j}$ be weight parameter vectors for the first
and second layers. Suppose $G_{1}$ is a class of functions defined on $z$ as
follows:

$\displaystyle G_{1}$ $\displaystyle=\left\\{x\rightarrow
s_{2}\left(\sum_{j=1}^{m}p_{j}z_{j}+p_{0}\right):p_{j}\in\mathbb{R},z\in[0,1]^{m},\sum_{j=0}^{m}\lvert
p_{j}\rvert\leq V\right\\}$ (20)

Define another broader class $G$ as follows:

$\displaystyle G$
$\displaystyle=\left\\{\sum_{j=1}^{k}r_{j}g_{j}+r_{0}:k\in\mathbb{N},g_{j}\in
G_{1},\lvert r_{j}\rvert\leq V\right\\}$ (21)

Here, $s_{1}$ and $s_{2}$ represent activation functions.

Assumptions:

  * •

The classes $D_{1}$ and $G_{1}$ are even.

  * •

$D_{1}$ and $G_{1}$ contain the identically zero function, and
$\mathcal{N}(\epsilon,F_{1},\lVert.\rVert)$ is finite.

  * •

The activation functions $s_{1}$ and $s_{2}$ satisfy the Lipschitz property.

  * •

The activation functions $s_{1}$ and $s_{2}$ are non-decreasing.

Under these assumptions, we evaluate the upper bound for the disparity defined
in equations (12) and (13). The utilization of the two-layer network
architecture is defined in equations (19) and (21) for both the discriminator
and generator, considering the Lipschitz and non-decreasing activation
functions. The derivation of the Rademacher complexity $\mathbb{R}_{n}(D)$ and
the composition of the Rademacher complexity $\mathbb{R}_{mn}(D\circ G)$ for
the case of Lipschitz and non-decreasing activation functions from the two-
layer network.

In the subsequent section, the paper extends the analysis to the case of
Lipschitz and non-decreasing activation functions and derives corresponding
bounds.

###  4.2  Bound for Lipschitz Activation Function

This portion presents the Rademacher bound applied to the Lipschitz activation
function within a two-layer network, serving the purpose of constraining the
disparity in the objective function. The Rademacher complexity of the function
class $D$ with respect to probability distribution $P$ for an i.i.d. sample
$S=(x_{1},x_{2},\ldots,x_{n})$ of size $n$ is defined as follows:

$\displaystyle\mathcal{R}_{n}(D)=\mathbb{E}\left[\sup_{f\in
D}\frac{2}{n}\sum_{i}\tau_{i}f(X_{i})\right]$ (22)

Here, the expectation is taken with respect to $X_{i}$ drawn from the
probability distribution $P_{x}$, and $\tau_{i}$ represents the Rademacher
variable such that
$\text{Prob}(\tau_{i}=1)=\text{Prob}(\tau_{i}=-1)=\frac{1}{2}$.

###### Lemma 4.1

Suppose $s_{1}:\mathbb{R}\rightarrow[0,1]$ is $1$-Lipschitz continuous. Then
for the discriminator class defined in (19), the Rademacher complexity is

$\displaystyle\mathcal{R}_{n}(D)\leq\frac{4V^{2}\sqrt{2\ln|D|}}{n}$ (23)

#### Proof.

The Rademacher complexity bound for the discriminator class $D$ uses Jensen’s
inequality and Massart’s finite lemma to prove the lemma. The weight
parameters for both the discriminator and generator are bounded by $V$. Then,

$\displaystyle\mathcal{R}_{n}(D)$
$\displaystyle=\frac{2}{n}\mathbb{E}\left[\sup_{f\in{\cal
F}}\sum_{i=1}^{n}\tau_{i}f(X_{i})\right]$
$\displaystyle=\frac{2}{n}\mathbb{E}\left[\sup_{f\in{\cal
F}}\sum_{i=1}^{n}\tau_{i}\sum_{i}^{l}w_{i}s\left(\sum_{i=1}^{n}v_{i}X_{i}+v_{0}\right)\right]$
$\displaystyle\leq\frac{2V}{n}\mathbb{E}\left[\sup_{f\in{\cal
F}}\left\|\sum_{i=1}^{n}\tau_{i}s\left(\sum_{i=1}^{n}v_{i}X_{i}+v_{0}\right)\right\|_{1}\right]$
$\displaystyle\leq\frac{2V}{n}\mathbb{E}\left[\sup_{f\in{\cal
F}}\left\|\sum_{i=1}^{n}\tau_{i}s\left(\sum_{i=1}^{n}v_{i}X_{i}+v_{0}\right)\right\|_{\infty}\right]$
$\displaystyle=\frac{2V}{n}\mathbb{E}\left[\sup_{f\in{\cal F}}\max_{1\leq
i\leq
n}\left|\sum_{i=1}^{n}\tau_{i}s\left(\sum_{i=1}^{n}v_{i}X_{i}+v_{0}\right)\right|\right]$
$\displaystyle=\frac{2V}{n}\mathbb{E}\left[\sup_{f\in{\cal
F}}\left|\sum_{i=1}^{n}\tau_{i}s\left(\sum_{i=1}^{n}v_{i}X_{i}+v_{0}\right)\right|\right]$
$\displaystyle\leq\frac{4V}{n}\mathbb{E}\left[\sup_{f\in{\cal
F}}\sum_{i=1}^{n}\tau_{i}s\left(\sum_{i=1}^{n}v_{i}X_{i}+v_{0}\right)\right]$
$\displaystyle\leq\frac{4V}{n}\mathbb{E}\left[\sup_{f\in{\cal
F}}\sum_{i=1}^{n}\tau_{i}\left(\sum_{i=1}^{n}v_{i}X_{i}+v_{0}\right)\right]$
$\displaystyle\leq\frac{4V}{n}\mathbb{E}\left[\sup_{f\in{\cal
F}}\sum_{i=1}^{n}\tau_{i}\left(\sum_{i=1}^{n}v_{i}X_{i}\right)\right]+\frac{4V}{n}\mathbb{E}\left[\sup_{f\in{\cal
F}}\sum_{i=1}^{n}\tau_{i}v_{0}\right]$
$\displaystyle\leq\frac{4V^{2}}{n}\mathbb{E}\left[\sup_{f\in{\cal
F}}\sum_{i=1}^{n}\tau_{i}X_{i}\right]$
$\displaystyle\leq\frac{4V^{2}\sqrt{2\ln|D|}}{n}$

The Lemma 4.1 shows that the upper bound of $\mathcal{R}_{n}(D)$ depends on
the discriminator sample size and the bound of the weight parameters. Since
$V$ is constant, the upper bound depends only on the discriminator sample
size.

###### Lemma 4.2

Suppose $s:\mathbb{R}\rightarrow[0,1]$ is $1$-Lipschitz continuous. For $V\geq
1$, and let $D$ be defined as in (19). Then for $\epsilon\leq V$, then

$\displaystyle\mathcal{R}_{n}(D)\leq\frac{C_{1}V^{3}\log(2n+2)}{\sqrt{n}}.$

#### Proof.

For $\sup\limits_{\theta\in\Theta}\lVert f\rVert_{2}$, the entropy integral
bound for Rademacher Complexity:

$\displaystyle\mathcal{R}_{n}(D)\leq\inf_{0\leq\delta\leq\frac{1}{2}}\left[4\delta+\frac{12}{\sqrt{n}}\int_{1/2}^{\delta}\sqrt{\log
N(\epsilon,D,\lVert.\rVert)}\,d\epsilon\right]$

Anthony and Bartlett (2009) state for the Lipschitz activation function,

$\displaystyle\log N(\epsilon,D,\lVert.\rVert)\leq
50\frac{V^{6}}{\epsilon^{4}}\log(2n+2)$

Then,

$\displaystyle\mathcal{R}_{n}(D)$
$\displaystyle\leq\inf_{0\leq\delta\leq\frac{1}{2}}\left[4\delta+\frac{12\sqrt{50}V^{3}\log(2n+2)}{\sqrt{n}}\int_{1/2}^{\delta}\frac{1}{\epsilon^{2}}\,d\epsilon\right]$
$\displaystyle\leq\frac{C_{1}V^{3}\log(2n+2)}{\sqrt{n}},$ (24)

for some universal constant $C_{1}\geq 0$.

###### Lemma 4.3

Suppose $s_{1}$ and $s_{2}$ are $1$-Lipschitz continous. Then for the
discriminator and generator class defined in (19) and (21) the composition
Rademacher complexity is

$\displaystyle\mathcal{R}_{mn}(D\circ G)\leq\frac{2V^{4}\sqrt{2ln\lvert
G\rvert}}{n}$ (25)

#### Proof.

The proof of this lemma uses a similar

$\displaystyle\mathcal{R}_{mn}(D\circ G)=$
$\displaystyle\frac{2}{n}\mathbb{E}\left[\sup_{f\in{\cal
F}}\sum\limits_{i=1}^{n}\tau_{i}f(\sum\limits_{j=1}^{k}r_{j}g_{j}+r_{0})\right]$
$\displaystyle=\frac{2}{n}\mathbb{E}\left[\sup_{f\in{\cal
F}}\sum\limits_{i=1}^{n}\tau_{i}\sum_{i}^{l}w_{i}s_{1}\left(\sum_{i=1}^{n}v_{i}\left(\sum_{j=1}^{k}r_{j}g_{j}+r_{0}\right)+v_{0}\right)\right]$
$\displaystyle\leq\frac{2V}{n}\mathbb{E}\left[\sup_{f\in{\cal
F}}\left\|\sum_{i=1}^{n}\tau_{i}s_{1}\left(\sum_{i=1}^{n}v_{i}\left(\sum_{j=1}^{k}r_{j}g_{j}+r_{0}\right)+v_{0}\right)\right\|_{1}\right]$
$\displaystyle\leq\frac{2V}{n}\mathbb{E}\left[\sup_{f\in
D}\left\|\sum_{i=1}^{n}\tau_{i}s_{1}\left(\sum_{i=1}^{n}v_{i}\left(\sum_{j=1}^{k}r_{j}g_{j}+r_{0}\right)+v_{0}\right)\right\|_{\infty}\right]$
$\displaystyle=\frac{2V}{n}\mathbb{E}\left[\sup_{f\in{\cal F}}\max_{1\leq
i\leq
n}\left|\sum_{i=1}^{n}\tau_{i}s_{1}\left(\sum_{i=1}^{n}v_{i}\left(\sum_{j=1}^{k}r_{j}g_{j}+r_{0}\right)+v_{0}\right)\right|\right]$
$\displaystyle=\frac{2V}{n}\mathbb{E}\left[\sup_{f\in{\cal
F}}\left|\sum_{i=1}^{n}\tau_{i}s_{1}\left(\sum_{i=1}^{n}v_{i}\left(\sum_{j=1}^{k}r_{j}g_{j}+r_{0}\right)+v_{0}\right)\right|\right]$
$\displaystyle\leq\frac{2V}{n}\mathbb{E}\left[\sup_{f\in{\cal
F}}\sum_{i=1}^{n}\tau_{i}s_{1}\left(\sum_{i=1}^{n}v_{i}\left(\sum_{j=1}^{k}r_{j}g_{j}+r_{0}\right)+v_{0}\right)\right]$
$\displaystyle\leq\frac{2V}{n}\mathbb{E}\left[\sup_{f\in{\cal
F}}\sum_{i=1}^{n}\tau_{i}\left(\sum_{i=1}^{n}v_{i}\left(\sum_{j=1}^{k}r_{j}g_{j}+r_{0}\right)+v_{0}\right)\right]$
$\displaystyle\leq\frac{2V}{n}\mathbb{E}\left[\sup_{f\in{\cal
F}}\sum_{i=1}^{n}\tau_{i}\left(\sum_{i=1}^{n}v_{i}\left(\sum_{j=1}^{k}r_{j}g_{j}+r_{0}\right)\right)\right]+\frac{4V}{n}\mathbb{E}\left[\sup_{f\in{\cal
F}}\sum_{i=1}^{n}\tau_{i}v_{0}\right]$
$\displaystyle\leq\frac{2V^{2}}{n}\mathbb{E}\left[\sup_{f\in{\cal
F}}\sum_{i=1}^{n}\tau_{i}\left(\sum_{j=1}^{k}r_{j}g_{j}+r_{0}\right)\right]$
$\displaystyle\leq\frac{2V^{2}}{n}\mathbb{E}\left[\sup_{f\in{\cal
F}}\sum_{i=1}^{n}\tau_{i}\left(\sum_{j=1}^{k}r_{j}s_{2}\left(\sum_{j=1}^{k}p_{j}z_{j}+p_{0}\right)+r_{0}\right)\right]$
$\displaystyle\leq\frac{2V^{4}}{n}\mathbb{E}\left[\sup_{f\in{\cal
F}}\sum_{i=1}^{n}\tau_{i}z_{j}\right]$ in the case of i=j
$\displaystyle\leq\frac{2V^{4}\sqrt{2ln\lvert G\rvert}}{n}$

The Lemma 4.3 shows that the upper bound of $\mathcal{R}_{mn}(D\circ G)$
depends on both discriminator and generator sample size and bound of weight
parameter. Since $V$ is constant, the upper bound depends on only
discriminator sample size.

###### Corollary 4.1

Suppose $s_{1}$ and $s_{2}:\mathbb{R}\rightarrow[0,1]$ are $1$-Lipschitz
continuous. For $V\geq 1$, let the discriminator and generator classes be
defined as (19) and (21). Then for $\epsilon\leq V$,

$\displaystyle
d_{I_{c}}(\hat{D},\hat{G})-d_{I_{c}}(D,G)\leq\frac{4V^{2}\sqrt{2\ln\lvert
D\rvert}}{n}+\frac{4V^{4}\sqrt{2\ln\lvert
G\rvert}}{n}+2Q_{x}\sqrt{\frac{\log(1/\delta)}{2n}}+2Q_{z}\sqrt{\frac{\log(1/\delta)}{2m}}$

###### Corollary 4.2

Suppose $s_{1}$ and $s_{2}:\mathbb{R}\rightarrow[0,1]$ are $1$-Lipschitz
continuous. For $V\geq 1$, let the discriminator and generator classes be
defined as (19) and (21). Then for $\epsilon\leq V$,

$\displaystyle
d_{I_{c}}(\hat{D},\hat{G})-d_{I_{c}}(D,G)\leq\frac{C_{1}V^{3}\log(2n+2)}{\sqrt{n}}+2Q_{x}\sqrt{\frac{\log(1/\delta)}{2n}}-2Q_{z}(1-\lambda)\sqrt{\frac{\log(1/\delta)}{2m}}$

###### Corollary 4.3

Suppose $s_{1}:\mathbb{R}\rightarrow[0,1]$ is $1$-Lipschitz continuous. For
$V\geq 1$, let the discriminator class be defined as (19). Then for
$\epsilon\leq V$,

$\displaystyle
d_{I_{c}}(\hat{D},G)-d_{I_{c}}(D,G)\leq\frac{4V^{2}\sqrt{2\ln\lvert
D\rvert}}{n}+2Q_{x}\sqrt{\frac{\log(1/\delta)}{2n}}$

###### Corollary 4.4

Suppose $s:\mathbb{R}\rightarrow[0,1]$ is $1$-Lipschitz continuous. For $V\geq
1$, let $D$ be given in (19). Then for $\epsilon\leq V$,

$\displaystyle
d_{I_{c}}(\hat{D},G)-d_{I_{c}}(D,G)\leq\frac{C_{1}V^{3}\log(2n+2)}{\sqrt{n}}+2Q_{x}\sqrt{\frac{\log(1/\delta)}{2n}}.$

###### Remark 4.1

The above four corollaries show the bound of the difference of the objective
function for the two-layer network in the case of the Lipschitz activation
function. Since the input variable bound $V$ and $\delta$ are constants, the
upper bound depends on both discriminator and generator sample sizes.
Moreover, as $m,n\rightarrow\infty$, the right side of the Corollary
approaches zero. Therefore, it is evident that:

$\displaystyle d_{I_{c}}(\hat{D},\hat{G})=d_{I_{c}}(D,G)$ $\displaystyle
d_{I_{c}}(\hat{D},G)=d_{I_{c}}(D,G)$

However, this equality is already evident from Theorem 3.1, as for
$m,n\rightarrow\infty$, the Rademacher complexity approaches zero.
Nevertheless, the above corollaries demonstrate that even an upper bound on
the Rademacher complexity implies the equality of population objective
function and empirical objective function when applying two-layer networks
with Lipschitz activation functions.

###  4.3 Bounding for Non-Decreasing Activation Functions

In this section, we explain the technique for bounding the equations denoted
by (10) and (11) in the case of a non-decreasing activation function. The
methodology involves leveraging the Rademacher complexity of a function class
$D$, which is constrained by the Dudley entropy integral as elucidated in
reference [R1]. This is subsequently combined with the bounding derived from
the covering number from [8]. A similar approach is adopted to bound equation
(11).

###### Corollary 4.5

Assuming a non-decreasing function $s_{1}:\mathbb{R}\rightarrow[0,1]$ and
$V\geq 1$, let the discriminator class $D$ be defined as in (19). For
$\epsilon\leq V$:

$\displaystyle d(\hat{D},G)-d(D,G)\leq
CV\sqrt{\frac{n+3}{n}\log\frac{n}{n+1}}+2Q_{x}\sqrt{\frac{2\log(1/\delta)}{n}}.$
(26)

#### Proof.

Utilizing the Rademacher complexity bound [R1] for
$\sup\limits_{\theta\in\Theta}\lVert f\rVert_{2}$:

$\displaystyle\mathcal{R}_{n}(D)\leq\inf_{0\leq\delta\leq\frac{1}{2}}\left[4\delta+\frac{12}{\sqrt{n}}\int_{1/2}^{\delta}\sqrt{\log
N(\epsilon,D,\lVert.\rVert)}d\epsilon\right].$

Furthermore, according to [8], Corollary 14.15, for $0\leq\epsilon\leq 1$ and
$n+1\leq t$:

$\displaystyle\log N(\epsilon,D,\lVert.\rVert)\leq
5\frac{V^{2}(n+3)}{\epsilon^{2}}\ln\left(\frac{4etV}{\epsilon(n+1)}\right).$

Hence, we have:

$\displaystyle\mathcal{R}_{n}(D)$
$\displaystyle\leq\inf_{0\leq\delta\leq\frac{1}{2}}\left[4\delta+\frac{12\sqrt{5}V\sqrt{n+3}}{\sqrt{n}}\int_{1/2}^{\delta}\frac{1}{\epsilon}\sqrt{\ln\frac{4etV}{\epsilon(n+1)}}d\epsilon\right],$
$\displaystyle\leq CV\sqrt{\frac{n+3}{n}\log\frac{n}{n+1}}$ (27)

where $C\geq 0$ is a universal constant. By substituting (4.3) into Theorem
(3.1), the proof is concluded.

In a parallel proof technique to (4.3), the Rademacher bound of the generator
class can be expressed as:

$\displaystyle\mathcal{R}_{m}(G)\leq CV\sqrt{\frac{m+3}{m}\log\frac{m}{m+1}}$
(28)

###### Corollary 4.6

For non-decreasing functions $s_{1}$ and $s_{2}:\mathbb{R}\rightarrow[0,1]$,
and $V\geq 1$, considering the definitions of discriminator and generator
classes in (19) and (21), and $\epsilon\leq V$:

$\displaystyle d(\hat{D},\hat{G})-d(D,G)\leq
CV\sqrt{\frac{n+3}{n}\log\frac{n}{n+1}}+2Q_{x}\sqrt{\frac{\log(1/\delta)}{2n}}-2Q_{z}(1+\lambda)\sqrt{\frac{\log(1/\delta)}{2m}}.$
(29)

#### Proof.

Considering that $D$ and $G$ are two-layer networks as defined in (19) and
(21), with sample sizes $n$ and $m$ respectively, the sample size of the
composition $D\circ G$ depends on the sample size of the input $z$ to network
$G$, not on the intermediate output of $G$. Thus, the sample size of $D\circ
G$ is $m$.

The Rademacher complexity bound is given in [R1] as:

$\displaystyle\mathcal{R}_{mn}(D\circ
G)\leq\inf_{0\leq\delta\leq\frac{1}{2}}\left[4\delta+\frac{12}{\sqrt{m}}\int_{1/2}^{\delta}\sqrt{\log
N(\epsilon,D\circ G,\lVert.\rVert)}d\epsilon\right].$

According to [8], Corollary 14.15, for the non-decreasing activation functions
$s_{1}$ and $s_{2}$, $0\leq\epsilon\leq 1$ and $m+1\leq t$:

$\displaystyle\log N(\epsilon,D\circ G,\lVert.\rVert)\leq
5\frac{V^{2}(m+3)}{\epsilon^{2}}\ln\left(\frac{4etV}{\epsilon(m+1)}\right).$

Thus, we have:

$\displaystyle\mathcal{R}_{mn}(D\circ G)$
$\displaystyle\leq\inf_{0\leq\delta\leq\frac{1}{2}}\left[4\delta+\frac{12\sqrt{5}V\sqrt{m+3}}{\sqrt{m}}\int_{1/2}^{\delta}\frac{1}{\epsilon}\sqrt{\ln\frac{4etV}{\epsilon(m+1)}}d\epsilon\right],$
$\displaystyle\leq CV\sqrt{\frac{m+3}{m}\log\frac{m}{m+1}}.$ (30)

where $C\geq 0$ is a universal constant. By substituting the inequalities
(4.3), (4.3), and (28) into Theorem (3.1), the proof is concluded.

###### Remark 4.2

In Corollary 4.5, the bound depends on the constant $V$ and the discriminator
sample size $n$. As $m,n\rightarrow{\infty}$, the right-hand side of (26) and
(29) approaches zero, implying:

$\displaystyle d_{I_{c}}(\hat{D},\hat{G})=d_{I_{c}}(D,G)$ $\displaystyle
d_{I_{c}}(\hat{D},G)=d_{I_{c}}(D,G).$

However, for the non-decreasing activation in a two-layer network, the
Rademacher complexity bounds for $G$ and $D\circ G$ are identical, as the
sample size of the input variable $z$ influences the sample size. The
regularization term $\lambda$ remains constant and has no effect as
$m,n\rightarrow{\infty}$. Moreover, if only $m\rightarrow{\infty}$ in (4.3),
both Corollary 4.5 and (29) share the same upper bound:

$\displaystyle d(\hat{D},\hat{G})-d(D,G)$ $\displaystyle\leq
CV\sqrt{\frac{n+3}{n}\log\frac{n}{n+1}}+2Q_{x}\sqrt{\frac{\log(1/\delta)}{2n}}$
$\displaystyle d(\hat{D},G)-d(D,G)$ $\displaystyle\leq
CV\sqrt{\frac{n+3}{n}\log\frac{n}{n+1}}+2Q_{x}\sqrt{\frac{\log(1/\delta)}{2n}}.$

For both cases, as $n\rightarrow{\infty}$:

$\displaystyle d_{I_{c}}(\hat{D},\hat{G})=d_{I_{c}}(D,G)$ $\displaystyle
d_{I_{c}}(\hat{D},G)=d_{I_{c}}(D,G).$

##  5 Conclusion

This paper demonstrates that infoGAN can be formulated as an objective
function with a regularized generator without employing a latent code. This
objective function and its empirical implementation are equivalent when
utilizing both Lipschitz and non-decreasing activation functions in a two-
layer network. However, this equivalence holds true only in scenarios
involving infinitely large discriminator and generator sample sizes. The
Rademacher complexity bound plays a crucial role in establishing this
equality. Investigating this property in the context of the lower bound of the
regularized objective function is a potential direction for future research.

## References

  * [1] I. Goodfellow, J. P. Abadie, M. Mirza, B. Xu, D. W. Farley, S. Ozair, A. Courville, and Y. Bengio. Generative adversarial nets. Advances in Neural Information Processing Systems (NIPS), p. 2672-2680, (2014).
  * [2] S. Arora, R Ge, Y Liang, T Ma, Y Zhang, Generalization and equilibrium in generative adversarial nets (gans). In Proceedings 34th of International conference on machine learning (ICML), p. 224-232, (2017).
  * [3] M. Mirza and S. Osindero, Conditional generative adversarial nets, arXiv preprint arXiv:1411.1784, (2014).
  * [4] S. Nowozin, B. Cseke, and R. Tomioka, f-gan: Training generative neural samplers using variational divergence minimization. Advances in Neural Information Processing Systems (NIPS), p. 271-279, 2016.
  * [5] Y. Wu, J. Donahue, D. Balduzzi, K. Simonyan, and T. Lillicrap, Logan: Latent optimization for generative adversarial networks, arXiv preprint arXiv:1912.00953, (2019).
  * [6] T. Kurutach, A. Tamar, G. Yang, S. J. Russell, and P. Abbeel, Learning plannable representations with causal info gan,Advances in Neural Information Processing Systems (NIPS), p. 8733-8744, (2018).
  * [7] Y. Li, K. Swersky, and R. Zemel. Generative moment matching networks. In Proceedings of the 32nd International conference on machine learning (ICML), p. 1718-1727, (2015).
  * [8] M. Arjovsky, S. Chintala, and L. Bottou. Wasserstein generative adversarial networks. In Proceedings of the 34th International Conference on Machine Learning (ICML), p.214-223, (2017).
  * [9] A. Radford, L. Metz, and S. Chintala. Unsupervised representation learning with deep convolutional generative adversarial networks. In 4th International Conference on Learning Representations (ICLR), (2016).
  * [10] S. Reed, Z. Akata, X. Yan, L. Logeswaran, B. Schiele, and H. Lee. Generative adversarial text to image synthesis. In Proceedings of The 33rd International Conference on Machine Learning (ICML), p. 1060-1069, (2016).
  * [11] J. Y. Zhu, T. Park, P. Isola, and A. A. Efros. Unpaired image-to-image translation using cycle-consistent adversarial networks. In IEEE International Conference on Computer Vision, P. 2242-2251, (2017).
  * [12] X. Yi, E. Walia, and P. S. Babyn. Generative adversarial network in medical imaging: A review. Medical Image Analysis, P. 101552, (2019).
  * [13] S. R. Bowman, L. Vilnis, O. Vinyals, A. M. Dai, R. Jozefowicz, and S. Bengio. Generating sentences from a continuous space. In Proceedings of the 20th SIGNLL Conference on Computational Natural Language Learning, p. 10-21, (2016).
  * [14] T. Liang. How well generative adversarial networks learn distributions. Journal of Machine Learning Research (JMLR), p. 1-41, (2021).
  * [15] K. Ji, Y. Zhou, Y. Liang, Understanding estimation and generalization error of generative adversarial networks. IEEE Transactions on Information Theory, p. 3114-3129, (2021).
  * [16] J. Huang, Y. Jiao, Z. Li, S. Liu, Y. Wang, Y. Yang, An Error Analysis of Generative Adversarial Networks for Learning Distributions. Journal of Machine Learning Research (JMLR), p. 1-43, (2022).
  * [17] P. Zhang, Q. Liu, D. Zhou, T. Xu, and X. He, On the discrimination - generalization trade-off in GANs. In Proceedings International Conference on Learning Representations (ICLR), (2018).
  * [18] M. Anthony and P. L. Bartlett. Learning in Neural Networks: Theoretical Foundations, Cambridge University Press, (1999).
  * [19] P. C. Petersen, Neural Network Theory, University of Vienna. April 18, (2022).
  * [20] X. Chen, Y. Duan, R. Houthooft, J. Schulman, I. Sutskever, P. Abbeel, infoGAN: Interpretable Representation Learning by Information Maximizing Generative Adversarial Nets. Neural Information Processing Systems (NIPS), (2016).
  * [21] J. Gui, Z. Sun, Y. Wen, D. Tao, J. Ye, A Review on Generative Adversarial Networks: Algorithms, Theory, and Applications. IEEE Transactions on Knowledge and Data Engineering, (2023).
  * [22] M. Hasan, G. Wathodkar, M. Muia, ARMA model development and analysis for global temperature uncertainty, Frontiers in Astronomy and Space Sciences, p.1098345, (2023).