$|{\mbox{cod}}(G/N)|=13$. By Lemma 2.3, we have $G/N\cong\textup{{U}}_{4}(2)$
or $G/N\cong\textup{{S}}_{4}(q)$ for $q=2^{f}>4$.

In the first case, the element $3^{4}\cdot
5\in{\mbox{cod}}(\textup{{U}}_{4}(2))$ but it is not in
${\mbox{cod}}({\mbox{O'N}})$.

In the second case, $q^{4}(q-1)^{2}\in{\mbox{cod}}(\textup{{S}}_{4}(q))$.
However, by a complete search there is no integer $q$ such that
$q^{4}(q-1)^{2}$ equals an element in ${\mbox{cod}}({\mbox{O'N}})$, a
contradiction.

$|{\mbox{cod}}(G/N)|=14$. By Lemma 2.3, we have $G/N\cong\textup{{U}}_{4}(3)$,
$G/N\cong{}^{2}\textup{{F}}_{4}(2)^{\prime}$ or $G/N\cong\textup{{J}}_{3}$.
However, the codegree sets of $\textup{{U}}_{4}(3)$,
${}^{2}\textup{{F}}_{4}(2)^{\prime}$ and $\textup{{J}}_{3}$ have $2^{4}\cdot
3^{6}$, $3^{3}\cdot 5^{2}\cdot 13$ and $2^{7}\cdot 3^{5}\cdot 19$,
respectively, but none of these numbers are in ${\mbox{cod}}({\mbox{O'N}})$.
This contradicts ${\mbox{cod}}(G/N)\subseteq{\mbox{cod}}(G)$.

$|{\mbox{cod}}(G/N)|=15$. By Lemma 2.3, we have $G/N\cong\textup{{G}}_{2}(3)$.
However, the element $2^{5}\cdot 3^{6}\cdot 13$ is only present in the
codegree set of $\textup{{G}}_{2}(3)$ and not in the codegree set of O’N,
which contradicts ${\mbox{cod}}(G/N)\subseteq{\mbox{cod}}(G)$.

$|{\mbox{cod}}(G/N)|=16$. By Lemma 2.3, we have $G/N\cong\textup{{A}}_{9}$ or
$G/N\cong\textup{{J}}_{2}$. If $G/N\cong\textup{{A}}_{9}$ case, $2^{4}\cdot
3^{3}\cdot 5\in{\mbox{cod}}(\textup{{A}}_{9})$ but is not in
${\mbox{cod}}({\mbox{O'N}})$, while in the $\textup{{J}}_{2}$ case $2^{6}\cdot
3^{3}\cdot 5^{2}\in{\mbox{cod}}(\textup{{J}}_{2})$ but $2^{6}\cdot 3^{3}\cdot
5^{2}\not\in{\mbox{cod}}({\mbox{O'N}})$. This contradicts
${\mbox{cod}}(G/N)\subseteq{\mbox{cod}}(G)$.

$|{\mbox{cod}}(G/N)|=17$. Then $G/N\cong\textup{{M}}^{c}L$ or
${\mbox{PSL}}(4,3)$. However, $2^{7}\cdot 5^{3}\cdot 11$ is only in
${\mbox{cod}}(\textup{{M}}^{c}L)$ and not ${\mbox{cod}}({\mbox{O'N}})$, a
contradiction. If $G/N={\mbox{PSL}}(4,3)$, the element $2^{3}\cdot
3^{6}\in{\mbox{cod}}({\mbox{PSL}}(4,3))$ but it is not in
${\mbox{cod}}({\mbox{O'N}})$.

$|{\mbox{cod}}(G/N)|=18$. We have
$G/N\cong\textup{{G}}_{2}(4),\textup{{S}}_{4}(5)$ or HS.

If $G/N\cong\textup{{S}}_{4}(5)$, then $5^{4}\cdot 13\in{\mbox{cod}}(G/N)$. If
$G/N\in\textup{{G}}_{2}(4)$, then $2^{12}\cdot 3^{3}\cdot 5\cdot
7\in{\mbox{cod}}(G/N)$. If $G/N\cong{\mbox{HS}}$, $2^{8}\cdot 3^{2}\cdot
11\in{\mbox{cod}}(G/N)$. None of these elements are in
${\mbox{cod}}({\mbox{O'N}})$, a contradiction.

Having ruled out all other cases, we conclude $G/N\cong{\mbox{O'N}}$.  $\hbox
to0.0pt{$\sqcap$\hss}\sqcup$

######  Lemma 3.16.

Let $G$ be a finite group with
${\mbox{cod}}(G)={\mbox{cod}}(\textup{{M}}_{24})$. If $N$ is the maximal
normal subgroup of $G$, it we have $G/N\cong\textup{{M}}_{24}$.

###### Proof.

As $G/N$ is a non-abelian simple group,
${\mbox{cod}}(G/N)\subseteq{\mbox{cod}}(G)$, so we have that
${\mbox{cod}}(G/N)=4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19$ or
$G/N\cong\textup{{G}}_{2}(q)$.

$|{\mbox{cod}}(G/N)|=4$. By Lemma 2.3, $G/N\cong{\mbox{PSL}}(2,k)$ where
$k=2^{f}\geq 4$, with $k^{2}-1\in{\mbox{cod}}(G/N)$. By a complete search
$k^{2}-1$ does not equal an element of ${\mbox{cod}}(\textup{{M}}_{24})$ since
none of the nontrivial codegrees are odd. This is a contradiction.

$|{\mbox{cod}}(G/N)|=5$. By Lemma 2.3, $G/N\cong{\mbox{PSL}}(2,k)$ where $k$
is a power of an odd prime number. We have $\displaystyle
k(k-\epsilon(k)\in{\mbox{cod}}(G/N)$, where $k=(-1)^{(k-1)/2}$. By a complete
search, $k(k+1)$ cannot be equal to any of the nontrivial elements in
${\mbox{cod}}(\textup{{M}}_{24})$ for any integer $k$, a contradiction.

$|{\mbox{cod}}(G/N)|=6$. By Lemma 2.3, $G/N\cong{\mbox{PSL}}(3,4)$ or
$G/N\cong{}^{2}B_{2}(q)$, with $q=2^{2n+1}$.

If $G/N\cong{\mbox{PSL}}(3,4)$ then $3^{2}\cdot 5\cdot
7\in{\mbox{cod}}({\mbox{PSL}}(3,4))$ but $3^{2}\cdot 5\cdot
7\not\in{\mbox{cod}}(\textup{{M}}_{24})$, contradicting
${\mbox{cod}}(G/N)\subseteq{\mbox{cod}}(G)$.

If $G/N\cong{}^{2}B_{2}(q)$, notice that
$(q-1)(q^{2}+1)\in{\mbox{cod}}({}^{2}B_{2}(q))$. By a complete search
$(q-1)(q^{2}+1)$ does not equal an element of
${\mbox{cod}}(\textup{{M}}_{24})$ for any integer $q$, a contradiction.

$|{\mbox{cod}}(G/N)|=7$. By Lemma 2.3, we have $G/N\cong{\mbox{PSL}}(3,3)$,
$\textup{{M}}_{11}$, $\textup{{A}}_{7}$ or $\textup{{J}}_{1}$. The elements
$2^{2}\cdot 3^{2}\cdot 13$, $2^{3}\cdot 3^{3}\cdot 11$, $2^{2}\cdot 3\cdot
5\cdot 7$, $3\cdot 5\cdot 11\cdot 19$ are in the codegrees of
${\mbox{PSL}}(3,3)$, $\textup{{M}}_{11}$, $\textup{{A}}_{7}$ or
$\textup{{J}}_{1}$, respectively. However, none of these are elements of
${\mbox{cod}}(\textup{{M}}_{24}$, a contradiction.

$|{\mbox{cod}}(G/N)|=8$. By Lemma 2.3, we have $G/N\cong{\mbox{PSU}}(3,q)$
with $4<q\not\equiv-1\pmod{3}$, $G/N\cong{\mbox{PSL}}(3,q)$ with
$4<q\not\equiv 1\pmod{3}$ or $G/N\cong\textup{{G}}_{2}(2)^{\prime}$.

If $G/N\cong{\mbox{PSU}}(3,q)$, then
$q^{3}(q^{2}-q+1)\in{\mbox{cod}}({\mbox{PSU}}(3,q))$. By a complete search,
$q^{3}(q^{2}-q+1)$ does not equal an element of
${\mbox{cod}}(\textup{{M}}_{24})$ for any integer $q$, since none of these
elements are odd in ${\mbox{cod}}(\textup{{M}}_{24}$.

If $G/N\cong{\mbox{PSL}}(3,q),$ we have
$q^{3}(q^{2}+q+1)\in{\mbox{cod}}({\mbox{PSL}}(3,q))$. By a complete search,
$q^{3}(q^{2}+q+1)$ does not equal an element of
${\mbox{cod}}(\textup{{M}}_{24})$ for any integer $q$, a contradiction.

Furthermore, $3^{3}\cdot 7\in{\mbox{cod}}(\textup{{G}}_{2}(2)^{\prime})$ but
$3^{3}\cdot 7\not\in{\mbox{cod}}(\textup{{M}}_{24})$, a contradiction.

$|{\mbox{cod}}(G/N)|=9$. By Lemma 2.3, we have $G/N\cong{\mbox{PSL}}(3,q)$
with $4<q\equiv 1\pmod{3}$ or $G/N\cong{\mbox{PSU}}(3,q)$ with
$4<q\equiv-1\pmod{3}$.

By a complete search, these expressions do not equal any element of
${\mbox{cod}}(\textup{{M}}_{24})$ for any nontrivial codegree is even in
${\mbox{cod}}(G)$.

$|{\mbox{cod}}(G/N)|=10$. By Lemma 2.3, we have $G/N\cong\textup{{M}}_{22}$.
However, $2^{7}\cdot 3\cdot 5\cdot 11$ is only present in
${\mbox{cod}}(\textup{{M}}_{22})$ and not in
${\mbox{cod}}(\textup{{M}}_{24})$, contradicting
${\mbox{cod}}(G/N)\subseteq{\mbox{cod}}(G)$.

$|{\mbox{cod}}(G/N)|=11$. Lemma 2.3, we have $G/N\cong{\mbox{PSL}}(4,2)$,
$G/N\cong\textup{{M}}_{12}$, $G/N\cong\textup{{M}}_{23}$ or
$G/N\cong{}^{2}\textup{{G}}_{2}(q)$ for $q=3^{2f+1},f\geq 1$.
${\mbox{cod}}({\mbox{PSL}}(4,2)),{\mbox{cod}}(\textup{{M}}_{12})$ and
${\mbox{cod}}(\textup{{M}}_{23})$ contain $3^{2}\cdot 5\cdot 7,2^{2}\cdot
3\cdot 5\cdot 11$ and $2^{7}\cdot 7\cdot 11$, respectively, none of which are
elements of ${\mbox{cod}}(\textup{{M}}_{24})$.

Furthermore, $(q^{2}-1)(q^{2}-q+1)\in{\mbox{cod}}({}^{2}\textup{{G}}_{2}(q))$.
By a complete search, this element does not equal an element of
${\mbox{cod}}(ON)$ for any integer root for $q$, contradicting
${\mbox{cod}}(G/N)\subseteq{\mbox{cod}}(G)$.

$|{\mbox{cod}}(G/N)|=12$. By Lemma 2.3, we have $G/N\cong\textup{{S}}_{4}(4)$.
However, $2^{7}\cdot 5^{2}\cdot 17$ is in of
${\mbox{cod}}(\textup{{S}}_{4}(4))$ and not in ${\mbox{cod}}({\mbox{O'N}})$,
contradicting ${\mbox{cod}}(G/N)\subseteq{\mbox{cod}}(G)$.

$|{\mbox{cod}}(G/N)|=13$. By Lemma 2.3, we have $G/N\cong\textup{{U}}_{4}(2)$
or $G/N\cong\textup{{S}}_{4}(q)$ for $q=2^{f}>4$. If
$G/N\cong\textup{{U}}_{4}(2)$, the element $3^{4}\cdot
5\in{\mbox{cod}}(\textup{{U}}_{4}(2))$ but it is not in
${\mbox{cod}}({\mbox{O'N}})$.

Furthermore, $q^{4}(q-1)^{2}\in{\mbox{cod}}(\textup{{S}}_{4}(q))$. However, by
a complete search there is no integer $q$ such that $q^{4}(q-1)^{2}$ equals an
element in ${\mbox{cod}}(\textup{{M}}_{24})$, a contradiction.

$|{\mbox{cod}}(G/N)|=14$. By Lemma 2.3, we have $G/N\cong\textup{{U}}_{4}(3)$,
$G/N\cong{}^{2}\textup{{F}}_{4}(2)^{\prime}$ or $G/N\cong\textup{{J}}_{3}$.
However, the codegree sets of $\textup{{U}}_{4}(3)$,
${}^{2}\textup{{F}}_{4}(2)^{\prime}$ and $\textup{{J}}_{3}$ have $2^{4}\cdot
3^{6}$, $3^{3}\cdot 5^{2}\cdot 13$ and $2^{7}\cdot 3^{5}\cdot 19$,
respectively, but none of these numbers are in
${\mbox{cod}}(\textup{{M}}_{24})$, a contradiction.

$|{\mbox{cod}}(G/N)|=15$. By Lemma 2.3, we have $G/N\cong\textup{{G}}_{2}(3)$.
However, the element $2^{5}\cdot 3^{6}\cdot 13$ is only present in the
codegree set of $\textup{{G}}_{2}(3)$ and not in the codegree set of
$\textup{{M}}_{24}$, a contradiction.

$|{\mbox{cod}}(G/N)|=16$. By Lemma 2.3, we have $G/N\cong\textup{{A}}_{9}$ or
$G/N\cong\textup{{J}}_{2}$. If $G/N\cong\textup{{A}}_{9}$, $2^{4}\cdot
3^{3}\cdot 5\in{\mbox{cod}}(\textup{{A}}_{9})$ but is not in
${\mbox{cod}}(\textup{{M}}_{24})$, while in the $\textup{{J}}_{2}$ case
$2^{6}\cdot 3^{3}\cdot 5^{2}\in{\mbox{cod}}(\textup{{J}}_{2})$ but $2^{6}\cdot
3^{3}\cdot 5^{2}\not\in{\mbox{cod}}(\textup{{M}}_{24})$. This contradicts
${\mbox{cod}}(G/N)\subseteq{\mbox{cod}}(G)$.

$|{\mbox{cod}}(G/N)|=17$. Then $G/N\cong\textup{{M}}^{c}L$ or
${\mbox{PSL}}(4,3)$. However, $2^{7}\cdot 5^{3}\cdot 11$ is only in
${\mbox{cod}}(\textup{{M}}^{c}L)$ and not ${\mbox{cod}}(\textup{{M}}_{24})$
contradiction. If $G/N={\mbox{PSL}}(4,3)$, the element $2^{3}\cdot
3^{6}\in{\mbox{cod}}({\mbox{PSL}}(4,3))$ but it is not in
${\mbox{cod}}(\textup{{M}}_{24})$.

$|{\mbox{cod}}(G/N)|=18$. We have $G/N\cong\textup{{G}}_{2}(4)$,
$\textup{{S}}_{4}(5)$ or HS. If $G/N\cong\textup{{S}}_{4}(5)$, then
$5^{4}\cdot 13\in{\mbox{cod}}(G/N)$. If $G/N\in\textup{{G}}_{2}(4)$. then
$2^{12}\cdot 3^{3}\cdot 5\cdot 7\in{\mbox{cod}}(G/N)$. If
$G/N\cong{\mbox{HS}}$, $2^{8}\cdot 3^{2}\cdot 11\in{\mbox{cod}}(G/N)$. None of
these elements are ${\mbox{cod}}(\textup{{M}}_{24})$, a contradiction.

$|{\mbox{cod}}(G/N)|=19$. $G/N$ must be isomorphic to O’N. However,
$2^{4}\cdot 3^{4}\cdot 7^{2}\cdot 31\in{\mbox{cod}}({\mbox{O'N}})$ but it is
not an element of ${\mbox{cod}}(\textup{{M}}_{24})$, a contradiction.

$|{\mbox{cod}}(G/N)|=20$. $G/N$ must be isomorphic to $\textup{{G}}_{2}(q)$.
We may find from [19] that $(q^{6}-1)(q^{2}-1)$ is a codegree of
$\textup{{G}}_{2}(q)$. However, from a complete search, we may find that there
does not exist an integer $q$ such that $(q^{6}-1)(q^{2}-1)$ is equal to an
element of ${\mbox{cod}}(\textup{{M}}_{24})$, a contradiction.

Having ruled out all other cases, we conclude $G/N\cong\textup{{M}}_{24}$.
$\hbox to0.0pt{$\sqcap$\hss}\sqcup$

Now we give the proof of Theorem 1.1.

###### Proof.

Suppose that the theorem is not true and let $G$ be a minimal counterexample.
Then $G$ is perfect by Remark 2.8. Let $N$ be a maximal normal subgroup of
$G$. We have $G/N\cong H$ by Lemmas 3.1-3.7 and $N>1$. By the choice of $G$,
$N$ is a minimal normal subgroup of $G$. Otherwise there exists a nontrivial
normal subgroup of $L$ of $G$ such that $L$ is included in $N$. Then
${\mbox{cod}}(G/L)={\mbox{cod}}(H)$ for
${\mbox{cod}}(H)={\mbox{cod}}(G/N)\subseteq{\mbox{cod}}(G/L)\subseteq{\mbox{cod}}(G)={\mbox{cod}}(H)$
and $G/L\cong H$ for $G$ is a minimal counterexample, a contradiction.

Step 1: $N$ is the unique minimal normal subgroup of $G$.

Otherwise we assume $M$ is another minimal normal subgroup of $G$. Then
$G=N\times M$ for $G/N$ is simple and $N\cong M\cong H$ for $M$ is also a
maximal normal subgroup of $G$. If $H\cong\textup{{S}}_{4}(4)$, choose
$\psi_{1}\in\mbox{Irr}(N)$ and $\psi_{2}\in\mbox{Irr}(M)$ such that
${\mbox{cod}}(\psi_{1})={\mbox{cod}}(\psi_{2})=2^{8}\cdot 5^{2}$. Set
$\chi=\psi_{1}\cdot\psi_{2}\in\mbox{Irr}(G)$. Then
${\mbox{cod}}(\chi)=(2^{8}\cdot 5^{2})^{2}$, a contradiction. In other cases,
we can also obtain a contradiction similarly.

Step 2: $\chi$ is faithful for each $\chi\in\mbox{Irr}(G|N)$.

It can be easily checked that $N$ is not contained in the kernel of $\chi$ for
each $\chi\in\mbox{Irr}(G|N)$. Then the kernel of $\chi$ is trivial by Step 1.

Step 3: $N$ is elementary abelian.

Assume to the contrary that $N$ is not abelian. Thus $N=S^{n}$ where $S$ is a
non-abelian simple group. By Lemmas 2.1 and 2.2, we see that there exists a
non-principal character $\psi\in\mbox{Irr}(N)$ that extends to some
$\chi\in\mbox{Irr}(G)$. Then $\ker(\chi)=1$ by Step 2 and
${\mbox{cod}}(\chi)=|G|/\chi(1)=|N|/\psi(1)\cdot|G/N|$. This is a
contradiction since $|G/N|$ is divisible by ${\mbox{cod}}(\chi)$.

Step 4: We show that $C_{G}(N)=N$.

First, ${\bf{C}}_{G}(N)\unlhd G$. Since $N$ is abelian by Step 3, there are
two cases: either ${\bf{C}}_{G}(N)=G$ or ${\bf{C}}_{G}(N)=N$. If
${\bf{C}}_{G}(N)=N$, we are done.

Suppose ${\bf{C}}_{G}(N)=G$. Therefore $N$ must be in the center of $G$ and
$|N|$ is a prime by Step 1. Since $G$ is perfect, we must have ${\bf Z}(G)=N$
and $N$ is isomorphic to a subgroup of the Schur multiplier of $G/N$ [10,
Corollary 11.20].

If $H$ is isomorphic to $\textup{{S}}_{4}(4)$, $\textup{{S}}_{4}(q)$,
$q=2^{f}>4$ or ${}^{2}\textup{{F}}_{4}(2)^{\prime}$, then by [7] the Schur
multiplier of $H$ is trivial which means $N=1$, a contradiction.

If $H$ is isomorphic to $\textup{{U}}_{4}(2)$, then $G$ is isomorphic to
$2.\textup{{U}}_{4}(2)$ by [7]. We note that $2.\textup{{U}}_{4}(2)$ has a
character of degree $16$ which means $3240\in{\mbox{cod}}(G)$, and this is a
contradiction.

If $H$ is isomorphic to $\textup{{U}}_{4}(3)$, then $G$ is isomorphic to
$2.\textup{{M}}_{22}$ or $3.\textup{{M}}_{22}$ by [7]. For
$2.\textup{{M}}_{22}$ we have a character of degree $26,892$. This gives a
codegree of $840\in{\mbox{cod}}(G)$, a contradiction. For
$3.\textup{{M}}_{22}$ we have a character of degree $729$. So $2^{3}\cdot
3^{7}\cdot 5\cdot 7\in{\mbox{cod}}(G)$, a contradiction.

If $H$ is isomorphic to $\textup{{J}}_{3}$, then $G$ is isomorphic to
$3.\textup{{J}}_{3}$ by [7]. We note that $3.\textup{{J}}_{3}$ has a character
of degree $26,163$ which means $1920\in{\mbox{cod}}(G)$, and this is a
contradiction.

If $H$ is isomorphic to $\textup{{G}}_{2}(3)$, then $G$ is isomorphic to
$3.\textup{{G}}_{2}(3)$ by [7]. We note that $3.\textup{{G}}_{2}(3)$ has a
character of degree $5832$ which means $2184\in{\mbox{cod}}(G)$, and this is a
contradiction.

If $H$ is isomorphic to $\textup{{A}}_{9}$, then $G$ is isomorphic to
$2.\textup{{A}}_{9}$ by [7]. We note that $2.\textup{{A}}_{9}$ has a character
degree of $8$ which means that $45360\in{\mbox{cod}}(G)$, contradiction. If
$H$ is isomorphic to $\textup{{J}}_{2}$, then $G$ is isomorphic to
$2.\textup{{J}}_{2}$ by [7]. We note that $2.\textup{{J}}_{2}$ has a character
degree of $6$ which means that $201600\in{\mbox{cod}}(G)$, a contradiction.

If $H\cong{\mbox{PSL}}(4,3)$, then $G$ is isomorphic to $2.{\mbox{PSL}}(4,3)$
by [7]. We note that $40$ is a character degree of $2.{\mbox{PSL}}(4,3)$, so
$303264\in cod(G)$, a contradiction.

If $H\cong\textup{{M}}^{c}\textup{{L}}$ then $G$ is isomorphic to
$3.\textup{{M}}^{c}\textup{{L}}$ by [7]. We note that $126$ is a character
degree of $3.\textup{{M}}^{c}\textup{{L}}$, so $21384000\in{\mbox{cod}}(G)$, a
contradiction.

If $H\cong\textup{{S}}_{4}(5)$, then $G$ is isomorphic to
$2.\textup{{S}}_{4}(5)$ by [7]. We note that $12$ is a character degree of
$2.\textup{{S}}_{4}(5)$ so $780000\in{\mbox{cod}}(G)$, a contradiction.

If $H\cong\textup{{G}}_{2}(4)$, then $G$ is isomorphic to
$2.\textup{{G}}_{2}(4)$ by [7]. We note $2.\textup{{G}}_{2}(4)$ has a
character degree of $12$ so $41932800\in{\mbox{cod}}(G)$, a contradiction.

If $H\cong{\mbox{HS}}$, then $G$ is isomorphic to $2.{\mbox{HS}}$ by [7]. We
note that $56$ is a character degree of $2.{\mbox{HS}}$ which means that
$1584000\in{\mbox{cod}}(G)$, a contradiction.

If $H\cong{\mbox{O'N}}$, then $G$ is isomorphic to $3.{\mbox{O'N}}$ by [7]. We
note that $342$ is a character degree of $3.{\mbox{O'N}}$ so $4042241280$ is
in ${\mbox{cod}}(G)$, a contradiction.

If $H\cong\textup{{M}}_{24}$, then the Schur multiplier of $H$ is trivial by
[7], implying $N=1$, a contradiction.

If $H\cong\textup{{G}}_{2}(q)$, then the Schur multiplier of $H$ is trivial by
[19], implying $N=1$, a contradiction.

Thus $C_{G}(N)=N$.

Step 5: Let $\lambda$ be a non-principal character in $\mbox{Irr}(N)$ and
$\theta\in\mbox{Irr}(I_{G}(\lambda)|\lambda)$. We show that
$\frac{|I_{G}(\lambda)|}{\theta(1)}\in{\mbox{cod}}(G)$. Also, $\theta(1)$
divides $|I_{G}(\lambda)/N|$ and $|N|$ divides $|G/N|$. Especially,
$I_{G}(\lambda)<G$, i.e. $\lambda$ is not $G$-invariant.

Let $\lambda$ be a non-principal character in $\mbox{Irr}(N)$. Given
$\theta\in\mbox{Irr}(I_{G}(\lambda)|\lambda)$. Note that
$\chi=\theta^{G}\in\mbox{Irr}(G)$ and
$\chi(1)=|G:I_{G}(\lambda)|\cdot\theta(1)$ by Clifford theory (see chapter 6
of [10]). Then $\ker(\chi)=1$ by Step 2 and
${\mbox{cod}}(\chi)=\frac{|I_{G}(\lambda)|}{\theta(1)}$. Especially, we have
that $\theta(1)=\theta(1)/\lambda(1)$ divides $|I_{G}(\lambda)/N|$, and then
$|N|$ divides $\frac{|I_{G}(\lambda)|}{\theta(1)}$. Since
${\mbox{cod}}(G)={\mbox{cod}}(G/N)$ and $|G/N|$ is divisible by every element
in ${\mbox{cod}}(G/N)$, we have that $|N|\mid|G/N|$.

Next we show $I_{G}(\lambda)<G$. Otherwise we may assume $I_{G}(\lambda)=G$.
Then $\mathrm{ker}(\lambda)\unlhd G$. Furthermore $\mathrm{ker}(\lambda)=1$ by
Step 1 and $N$ is a cyclic subgroup with prime order by Step 3. Therefore
$G/N$ is abelian for $G/N=N_{G}(N)/C_{G}(N)\leq\mbox{Aut}(N)$ by Normalizer-
Centralizer Theorem, a contradiction.

Step 6: Final contradiction.

By Step 3, $N$ is an elementary abelian $p$-subgroup for some prime $p$ and we
assume $|N|=p^{n}$. By the Normalizer-Centralizer Theorem, $H\cong
G/N=N_{G}(N)/C_{G}(N)\leq\mbox{Aut}(N)$ Then we have that $n>1$. Note that in
general $\mbox{Aut}(N)={\mbox{GL}}(n,p)$. By Step 5, $|N|\mid|G/N|$ so we need
only to look at the prime power divisors of $|H|$.

(Case 1) $H\cong\textup{{S}}_{4}(4)$

Now $|H|=2^{8}\cdot 3^{2}\cdot 5^{2}\cdot 17$. It follows easily that $|H|$
does not divide $|{\mbox{GL}}(n,2)|$ when $2\leq n\leq 7$,
$|{\mbox{GL}}(2,3)|$, or $|{\mbox{GL}}(2,5)|$.

Thus $|N|=2^{8}$. By Step 5, we know that
$\frac{|T|}{\theta(1)}\in{\mbox{cod}}(G)$ and we show that $|N|$ divides
$\frac{|T|}{\theta(1)}$. Upon inspection of the codegrees of $G$, we have that
$\frac{|T|}{\theta(1)}$ must equal to $2^{8}\cdot 3\cdot 5^{2}$, $2^{8}\cdot
3^{2}\cdot 5$, $2^{8}\cdot 5^{2}$, $2^{8}\cdot 3\cdot 5$, or $2^{8}\cdot 17$.
Thus $\frac{|T/N|}{\theta(1)}=3\cdot 5^{2}$, $3^{2}\cdot 5$, $5^{2}$, $3\cdot
5$, or $17$. From this, we conclude that $|T/N|_{2}=|\theta(1)|_{2}$. By
chapter 6 of [10], we note that $|T/N|$ is a sum of squares which are of the
same form as $\theta(1)^{2}$. Thus, we know that $|T/N|_{2}=1$. But then,
$|G/N:T/N|=|G:T|\geq 2^{8}$, a contradiction.

(Case 2) $H\cong\textup{{U}}_{4}(2)$. Now $|H|=2^{6}\cdot 3^{4}\cdot 5$. If
$|{\mbox{GL}}(n,2)|$ when $2\leq n\leq 5$ or $|{\mbox{GL}}(m,3)|$ when $2\leq
m\leq 3$, it can be checked that $|H|$ doesn’t divide the order
$|\mbox{Aut}(N)|$.

If $|{\mbox{GL}}(6,2)|$ and $|{\mbox{GL}}(4,3)|$, we have that $|H|$ divides
the order $|\mbox{Aut}(N)|$.

The first circumstance is that $|N|=2^{6}$. By Step 5, we know that
$\frac{|T|}{\theta(1)}\in{\mbox{cod}}(G)$ and we show that $|N|$ divides
$\frac{|T|}{\theta(1)}$. Upon inspection of the codegrees of $G$, we have that
$\frac{|T|}{\theta(1)}$ must equal to $2^{6}\cdot 3^{4}$, $2^{6}\cdot 3^{3}$,
$2^{6}\cdot 3^{2}$ or $2^{6}\cdot 5$. Thus $\frac{|T/N|}{\theta(1)}=3^{4}$,
$3^{3}$, $3^{2}$ or $5$. From this, we conclude that
$|T/N|_{2}=|\theta(1)|_{2}$. In any case, whenever we have the $p$-parts of
$|T/N|$ and $\theta(1)$ equal to each other, we know that they must both be
$1$. This is because $|T/N|$ is a sum of squares of the same form as
$\theta(1)^{2}$ by chapter 6 of [10]. Hence, we have $|T/N|_{2}=1$. But then,
$|G/N:T/N|=|G:T|\geq 2^{6}$, a contradiction.

Another situation is that $|N|=3^{4}$. By Step 5, we know that
$\frac{|T|}{\theta(1)}\in{\mbox{cod}}(G)$ and we show that $|N|$ divides
$\frac{|T|}{\theta(1)}$. Upon inspection of the codegrees of $G$, we have that
$\frac{|T|}{\theta(1)}$ must equal to $2^{6}\cdot 3^{4}$, $2^{5}\cdot 3^{4}$,
$2^{4}\cdot 3^{4}$, $2^{3}\cdot 3^{4}$ or $3^{4}\cdot 5$. Then
$\frac{|T/N|}{\theta(1)}=2^{6}$, $2^{5}$, $2^{4}$, $2^{3}$ or $5$. From this,
we conclude that $|T/N|_{3}=|\theta(1)|_{3}$. By chapter 6 of [10], we note
that $|T/N|$ is a sum of squares which are of the same form as
$\theta(1)^{2}$. Thus, we know that $|T/N|_{3}=1$. But then,
$|G/N:T/N|=|G:T|\geq 3^{4}$, a contradiction.

(Case 3) $H\cong\textup{{S}}_{4}(q)$, for $q=2^{f}$, $q>4$.

Note that $\gcd(q^{2}+1,q+1)=1$ and $\gcd(q^{2}+1,q-1)=1$ and
$\gcd(q+1,q-1)=1$ or $2$. Thus, $q^{4}$ is the largest power of a prime that
divides the order of $\textup{{S}}_{4}(q)$, where $q=2^{f}>4$. Then, $|N|\leq
q^{4}$. Let $K$ be a maximal subgroup of $\textup{{S}}_{4}(q)$ such that
$T/N\leq K$. Then is a maximal subgroup of $G/N$. If $K$ is not the type in
Lemma 2.5, then $|G:T|\geq q^{4}$, a contradiction. Therefore $K$ is of type
in Lemma 2.5. If $K$ is of type ${C_{q-1}}^{2}:D_{8}$, then
$|G:T|\geq\frac{1}{8}q^{4}(q^{2}+1)(q+1)^{2}$, and thus $|G:T|>q^{4}$, a
contradiction. If $K$ is of type ${C_{q+1}}^{2}:D_{8}$, then
$|G:T|\geq\frac{1}{8}q^{4}(q^{2}+1)(q-1)^{2}$, and thus $|G:T|>q^{4}$, a
contradiction. If $K$ is of type ${C_{q^{2}+1}}:4$, then
$|G:T|\geq\frac{1}{4}q^{4}(q+1)^{2}(q-1)^{2}$, and thus $|G:T|>q^{4}$, a
contradiction. If $K$ is of type $SO_{4}^{+}(q)$, then $|G:T|\geq
2q^{2}(q^{2}+1)(q+1)(q-1)$, and thus $|G:T|>q^{4}$, a contradiction. If $K$ is
of type $S_{z}(q)$, then $|G:T|\geq q^{2}(q+1)^{2}(q-1)$, and thus
$|G:T|>q^{4}$, a contradiction. When the maximal subgroup is one of these
cases, this means that it is a contradiction for $|G/N|>q^{4}$.

(Case 4) $H\cong\textup{{U}}_{4}(3)$. Now $|H|=2^{7}\cdot 3^{6}\cdot 5\cdot
7$. We note that $|\textup{{U}}_{4}(3)|$ does not divide $|{\mbox{GL}}(n,2)|$
when $2\leq n\leq 7$ or $|{\mbox{GL}}(m,3)|$ when $2\leq m\leq 5$.

Thus $|N|=3^{6}$. By Step 5, we know that
$\frac{|T|}{\theta(1)}\in{\mbox{cod}}(G)$ and we show that $|N|$ divides
$\frac{|T|}{\theta(1)}$. Upon inspection of the codegrees of $G$, we have that
$\frac{|T|}{\theta(1)}$ must equal to $2^{7}\cdot 3^{6}$, $2^{5}\cdot 3^{6}$,
$2^{4}\cdot 3^{6}$, $2^{3}\cdot 3^{6}$, $3^{6}\cdot 7$ or $3^{6}\cdot 5$. Thus
$\frac{|T/N|}{\theta(1)}=2^{7}$, $2^{5}$, $2^{4}$, $2^{3}$, $7$, or $5$ and we
conclude that $|T/N|_{3}=|\theta(1)|_{3}$. By chapter 6 of [10], we note that
$|T/N|$ is a sum of squares which are of the same form as $\theta(1)^{2}$.
Thus, we know that $|T/N|_{3}=1$. But then, $|G/N:T/N|=|G:T|\geq 3^{6}$, a
contradiction.

(Case 5) $H\cong{{}^{2}\textup{{F}}_{2}(2)}^{\prime}$. Note that
$|H|=2^{11}\cdot 3^{3}\cdot 5^{2}\cdot 13$. We can also simply check that
$|H|$ does not divide the order of any possible general linear group with
these conditions.

(Case 6) $H\cong\textup{{J}}_{3}$. Note that $|H|=2^{7}\cdot 3^{5}\cdot 5\cdot
17\cdot 19$. Similarly, we can check that $|H|$ does not divide
$|{\mbox{GL}}(n,2)|$ when $2\leq n\leq 7$ or $|{\mbox{GL}}(m,3)|$ when $2\leq
n\leq 5$.

(Case 7) $H\cong\textup{{G}}_{2}(3)$. Now $|H|=2^{6}\cdot 3^{6}\cdot 7\cdot
13$. We can also simply check that $|H|$ does not divide $|{\mbox{GL}}(n,2)|$
when $2\leq n\leq 6$ or $|{\mbox{GL}}(m,3)|$ when $2\leq m\leq 5$.

Thus $|N|=3^{6}$. By Step 5, we know that
$\frac{|T|}{\theta(1)}\in{\mbox{cod}}(G)$ and we show that $|N|$ divides
$\frac{|T|}{\theta(1)}$. Upon inspection of the codegrees of $G$, we have that
$\frac{|T|}{\theta(1)}$ must equal to $2^{5}\cdot 13\cdot 3^{6}$, $13\cdot
7\cdot 3^{6}$, $2^{6}\cdot 3^{6}$, $2^{3}\cdot 7\cdot 3^{6}$, $3^{6}\cdot
2^{5}$, $3^{6}\cdot 13$, $2^{3}\cdot 3^{6}$, or $3^{6}\cdot 7$. Thus
$\frac{|T/N|}{\theta(1)}=2^{5}\cdot 13$, $13\cdot 7$, $2^{6}$, $2^{3}\cdot 7$,
$2^{5}$, $2^{3}$, $13$ or $7$ and we conclude that
$|T/N|_{3}=|\theta(1)|_{3}$. By chapter 6 of [10], we note that $|T/N|$ is a
sum of squares which are of the same form as $\theta(1)^{2}$. Thus, we know
that $|T/N|_{3}=1$. But then, $|G/N:T/N|=|G:T|\geq 3^{6}$, a contradiction.

(Case 8) $H\cong\textup{{A}}_{9}$. Now $|H|=2^{6}\cdot 3^{4}\cdot 5\cdot 7$.
By inspection, $|H|$ only divides $|{\mbox{GL}}(n,2)|$ when $n=6$.

By Step $5$, we know that $\frac{|T|}{\theta(1)}\in{\mbox{cod}}(G)$ and that
$|N|\mid\frac{|T|}{\theta(1)}$, so $\frac{|T|}{\theta(1)}=2^{6}\cdot 3\cdot
5$, $2^{6}\cdot 3^{3}$, $2^{6}\cdot 3^{4}$, $2^{6}\cdot 3\cdot 5\cdot 7$, or
$2^{6}\cdot 3^{3}\cdot 5$. Then $\frac{|T/N|}{\theta(1)}=3\cdot 5$, $3^{3}$,
$3^{4}$, $3\cdot 5\cdot 7$, or $3^{3}\cdot 5$. By chapter $6$ of [10], we note
that $|T/N|$ is a sum of squares of numbers with the same form as
$\theta(1)^{2}.$ This implies $|T/N|_{2}=1$. Thus $|G/N:T/N|=|G:T|\geq
2^{6}>|G:T|$, a contradiction.

(Case 9) $H\cong\textup{{J}}_{2}$. Now $|H|=2^{7}\cdot 3^{3}\cdot 5^{2}\cdot
7$. By inspection, $|H|$ does not divide $|{\mbox{GL}}(n,2)|$ with $2\leq
n\leq 7$, $|{\mbox{GL}}(m,3)|$ with $2\leq m\leq 3$, or $|{\mbox{GL}}(2,5)|$.

(Case 10) $H\cong{\mbox{PSL}}(4,3)$. Now $|H|=2^{7}\cdot 3^{6}\cdot 5\cdot
13$. By inspection, $|H|$ does not divide $|{\mbox{GL}}(n,2)|$ with $2\leq
n\leq 7$ or $|{\mbox{GL}}(m,3)|$ with $2\leq m\leq 3$. Thus $|N|=3^{4},3^{5}$,
or $3^{6}$.

Suppose $|N|=3^{4}$. Let $K$ be a maximal subgroup of $\mathrm{PSL}(4,3)$ such
that $T/N\leq K$. Then $K$ is a maximal subgroup of $G/N$. If $K$ is not of
the type $3^{3}:\mathrm{L}_{3}(3)$, then $|G:T|>3^{4}$ by Lemma 2.6, a
contradiction. By Step $5$, we can again deduce that
$\frac{|T|}{\theta(1)}=2^{6}\cdot 3^{6}\cdot 5,2^{7}\cdot 3^{5}\cdot
5,2^{5}\cdot 3^{6}\cdot 5,2^{7}\cdot 3^{6},2^{6}\cdot 3^{4}\cdot 13,2^{6}\cdot
3^{4}\cdot 5,2^{5}\cdot 3^{6},2^{6}\cdot 3^{5},2^{2}\cdot 3^{6}\cdot
5,2^{5}\cdot 3^{4}\cdot 5,2^{7}\cdot 3^{4},3^{6}\cdot 13,2^{5}\cdot 3^{5}$, or
$2^{3}\cdot 3^{6}$. Thus, $\frac{|T/N|}{\theta(1)}=2^{6}\cdot 3^{2}\cdot
5,2^{7}\cdot 3\cdot 5,2^{5}\cdot 3^{2}\cdot 5,2^{7}\cdot 3^{2},2^{6}\cdot
13,2^{6}\cdot 5,2^{5}\cdot 3^{2},2^{6}\cdot 3,2^{2}\cdot 3^{2}\cdot
5,2^{5}\cdot 5,2^{7},3^{2}\cdot 13,2^{5}\cdot 3$, or $2^{3}\cdot 3^{2}$. We
conclude that $\frac{|T/N|_{3}}{\theta(1)_{3}}\leq 3^{2}$, i.e.
$\frac{|T/N|_{3}}{3^{2}}\leq\theta(1)_{3}$. By chapter $6$ of [10], $|T/N|$ is
a sum of squares which are of the same form as $\theta(1)^{2}$, we know that
$|T/N|_{3}\leq 3^{4}$. If $K\cong 3^{3}:\mathrm{L}_{3}(3)$, then $|T/N|\leq
3^{4}\cdot 2^{4}\cdot 13$, and so $|G/N:T/N|=|G:T|\geq 3^{2}\cdot 2^{3}\cdot
5>3^{4}>|G:T|$, a contradiction. If $K\cong 3^{3}:\mathrm{L}_{3}(3)$, then
$|T/N|\leq 3^{4}\cdot 2^{4}\cdot 13$, and so $|G/N:T/N|=|G:T|\geq 3^{2}\cdot
2^{3}\cdot 5>3^{4}>|G:T|$, a contradiction.

Suppose $|N|=3^{5}$. Let $K$ be a maximal subgroup of $\mathrm{PSL}(4,3)$ such
that $T/N\leq K$. Then $K$ is a maximal subgroup of $G/N$. If
$K\cong(4\times\mathrm{A}_{6}):2$, $\mathrm{S}_{6}$, or
$\mathrm{S}_{4}\times\mathrm{S}_{4}$, then $|G:T|>3^{4}$ by Lemma 2.6, a
contradiction. By Step $5$, we can again deduce that
$\frac{|T|}{\theta(1)}=2^{6}\cdot 3^{6}\cdot 5$, $2^{7}\cdot 3^{5}\cdot 5$,
$2^{5}\cdot 3^{6}\cdot 5$, $2^{7}\cdot 3^{6}$, $2^{5}\cdot 3^{6}$, $2^{6}\cdot
3^{5}$, $2^{2}\cdot 3^{6}\cdot 5$, $3^{6}\cdot 13$, $2^{5}\cdot 3^{5}$, or
$2^{3}\cdot 3^{6}$. Thus, $\frac{|T/N|}{\theta(1)}=2^{6}\cdot 3\cdot 5$,
$2^{7}\cdot 5$, $2^{5}\cdot 3\cdot 5$, $2^{7}\cdot 3$, $2^{5}\cdot 3$,
$2^{6}$, $2^{2}\cdot 3\cdot 5$, $3\cdot 13$, $2^{5}$, or $2^{3}\cdot 3$. We
conclude that $\frac{|T/N|_{3}}{\theta(1)_{3}}\leq 3$, i.e.
$\frac{|T/N|_{3}}{3}\leq\theta(1)_{3}$. By chapter $6$ of [10], $|T/N|$ is a
sum of squares which are of the same form as $\theta(1)^{2}$, we know that
$|T/N|_{3}\leq 3^{2}$. If $K\cong 3^{3}:\mathrm{L}_{3}(3)$, then $|T/N|\leq
3^{2}\cdot 2^{4}\cdot 13$, and so $|G/N:T/N|=|G:T|\geq 3^{4}\cdot 2^{3}\cdot
5>3^{5}>|G:T|$, a contradiction. If $K\cong\mathrm{U}_{4}(2)$, then $|T/N|\leq
3^{2}\cdot 2^{7}\cdot 5$, and so $|G/N:T/N|=|G:T|\geq 3^{4}\cdot
13>3^{5}>|G:T|$, a contradiction. If $K\cong
3^{4}:2(\mathrm{A}_{4}\times\mathrm{A}_{4}).2$, then $|T/N|\leq 3^{2}\cdot
2^{6}$, and so $|G/N:T/N|=|G:T|\geq 3^{4}\cdot 2\cdot 5\cdot 13>3^{5}>|G:T|$,
a contradiction.

Suppose $|N|=3^{6}$. By Step $5$, we can again deduce that
$\frac{|T|}{\theta(1)}=2^{6}\cdot 3^{6}\cdot 5,2^{5}\cdot 3^{6}\cdot
5,2^{7}\cdot 3^{6},2^{5}\cdot 3^{6},2^{2}\cdot 3^{6}\cdot 5,3^{6}\cdot 13$, or
$2^{3}\cdot 3^{6}$. Thus, $\frac{|T/N|}{\theta(1)}=2^{6}\cdot 5,2^{5}\cdot
5,2^{7},2^{5},2^{2}\cdot 5,13$, or $2^{3}$. We conclude that
$|T/N|_{3}=|\theta(1)|_{3}$. By chapter $6$ of [10], $|T/N|$ is a sum of
squares which are of the same form as $\theta(1)^{2}$, we know that
$|T/N|_{3}=1$ and $|G/N:T/N|=|G:T|\geq 3^{6}>|G:T|$, a contradiction.

(Case 11) $H\cong\textup{{M}}^{c}\textup{{L}}$. Now $|H|=2^{7}\cdot 3^{6}\cdot
5^{3}\cdot 7\cdot 11$. By inspection, $|H|$ does not divide
$|{\mbox{GL}}(n,2)|$ with $2\leq n\leq 7$, $|{\mbox{GL}}(m,3)|$ with $2\leq
m\leq 6$, or $|{\mbox{GL}}(l,5)|$ with $2\leq l\leq 3$.

(Case 12) $H\cong\textup{{S}}_{4}(5)$. Now $|H|=2^{6}\cdot 3^{2}\cdot
5^{4}\cdot 13$. By inspection, $|H|$ does not divide $|{\mbox{GL}}(n,2)|$ with
$2\leq n\leq 6$, $|{\mbox{GL}}(2,3)|$, or $|{\mbox{GL}}(l,5)|$ with $2\leq
l\leq 3$.

Thus $|N|=5^{4}$. By Step $5,$ we know that
$\frac{|T|}{\theta(1)}\in{\mbox{cod}}(G)$ and that
$|N|\mid\frac{|T|}{\theta(1)}$, so $\frac{|T|}{\theta(1)}=2^{2}\cdot 3\cdot
5^{4},5^{4}\cdot 13,2^{3}\cdot 3\cdot 5^{4},2^{2}\cdot 3^{2}\cdot
5^{4},2^{4}\cdot 3\cdot 5^{4},2^{3}\cdot 3^{2}\cdot 5^{4},2^{5}\cdot 3\cdot
5^{4}$, or $2^{6}\cdot 3^{2}\cdot 5^{4}.$ This implies
$\frac{|T/N|}{\theta(1)}=2^{2}\cdot 3,13,2^{3}\cdot 3,2^{2}\cdot
3^{2},2^{4}\cdot 3,2^{3}\cdot 3^{2},2^{5}\cdot 3$, or $2^{6}\cdot 3^{2}$. We
conclude that $|T/N|_{5}=|\theta(1)|_{5}$. By chapter $6$ of [10], $|T/N|$ is
a sum of squares which are of the same form as $\theta(1)^{2}$, we know that
$|T/N|_{5}=1$ and $|G/N:T/N|=|G:T|\geq 5^{4}>|G:T|$, a contradiction.

(Case 13) $H\cong\textup{{G}}_{2}(4)$. Now $|H|=2^{12}\cdot 3^{3}\cdot
5^{2}\cdot 7\cdot 13$. By inspection, $|H|$ does not divide
$|{\mbox{GL}}(n,2)|$ with $2\leq n\leq 11$, $|{\mbox{GL}}(m,3)|$ with $m=2,3$,
or $|{\mbox{GL}}(2,5)|$.

Thus $|N|=2^{12}$. By Step $5$, we know that
$\frac{|T|}{\theta(1)}\in{\mbox{cod}}(G)$ and that
$|N|\mid\frac{|T|}{\theta(1)}$, so $\frac{|T|}{\theta(1)}=2^{12}\cdot 13$,
$2^{12}\cdot 3\cdot 5$, $2^{12}\cdot 3\cdot 7$, $2^{12}\cdot 3^{2}\cdot 5$,
$2^{12}\cdot 3\cdot 5^{2}$, or $2^{12}\cdot 3^{3}\cdot 5\cdot 7$. This implies
$|T/N|=13$, $3\cdot 5$, $3\cdot 7$, $3^{2}\cdot 5$, $3\cdot 5^{2}$, or
$3^{3}\cdot 5\cdot 7$. We conclude that $|T/N|_{2}=|\theta(1)|_{2}$. By
chapter $6$ of [10], $|T/N|$ is a sum of squares which are of the same form as
$\theta(1)^{2}$, we know that $|T/N|_{2}=1$ and $|G/N:T/N|=|G:T|\geq
2^{12}>|G:T|$, a contradiction.

(Case 14) $H\cong{\mbox{HS}}$. Now $|H|=2^{9}\cdot 3^{2}\cdot 5^{3}\cdot
7\cdot 11$. By inspection, $|H|$ does not divide $|{\mbox{GL}}(n,2)|$ with
$2\leq n\leq 9$, $|{\mbox{GL}}(m,3)|$ with $m=2$, or $|{\mbox{GL}}(l,5)|$ with
$2\leq l\leq 3$.

(Case 15) $H\cong{\mbox{O'N}}$. Now $|H|=2^{9}\cdot 3^{4}\cdot 5\cdot
7^{3}\cdot 11\cdot 19\cdot 31$. By inspection, $|H|$ does not divide
$|{\mbox{GL}}(n,2)|$ with $2\leq n\leq 9$, $|{\mbox{GL}}(m,3)|$ with $2\leq
m\leq 4$, or $|{\mbox{GL}}(l,7)|$ with $2\leq l\leq 3$.

(Case 16) $H\cong\textup{{M}}_{24}$. Now $|H|=2^{10}\cdot 3^{3}\cdot 5\cdot
7\cdot 11\cdot 23$. By inspection, $|H|$ does not divide $|{\mbox{GL}}(n,2)|$
with $2\leq n\leq 10$, or $|{\mbox{GL}}(m,3)|$ with $2\leq m\leq 3$.  $\hbox
to0.0pt{$\sqcap$\hss}\sqcup$

## References

  * [1] N. Ahanjideh, Nondivisibility among irreducible character co-degrees, Bull. Aust. Math. Soc. 105 (2022), 68-74.
  * [2] F. Alizadeh, H. Behravesh, M. Ghaffarzadeh, M. Ghasemi, S. Hekmatarah, Groups with few codegrees of irreducible characters, Comm. Algebra 47 (2019), 1147-1152.
  * [3] K. Aziziheris, F. Shafiei, F. Shirjian, Simple groups with few irreducible character degrees, J. Algebra Appl. 20 (2021), 2150139.
  * [4] A. Bahri, Z. Akhlaghi, B. Khosravi, An analogue of Huppert’s conjecture for character codegrees, Bull. Aust. Math. Soc. 104 (2021), 278-286.
  * [5] M. Bianchi, D. Chillag, M. L. Lewis, E. Pacifici, Character degree graphs that are complete graphs, Proc. Amer. Math. Soc, 135 (2007), no. 3, 671-676.
  * [6] D. Chillag and M. Herzog, On character degrees quotients, Arch. Math. 55 (1989), 25-29.
  * [7] J. H. Conway, R. T. Curtis, S. P. Norton, R. A. Parker, R. A. Wilson, Atlas of Finite Groups, Oxford University Press, London, 1984.
  * [8] M. Gintz, M. Kortje, M. Laurence, Y. Liu, Z. Wang, Y. Yang, On the characterization of some non-abelian simple groups with few codegrees, Comm. Algebra 50 (2022), 3932-3939.
  * [9] H. Guan, X. Zhang, Y. Yang, Recognizing ${}^{2}G_{2}(q)$ using the codegree set, Bull. Aust. Math. Soc., accepted.
  * [10] I. M. Isaacs, Character Theory of Finite Groups, Academic Press, New York, NY, 1976.
  * [11] G. James, A. Kerber, The Representation Theory of the Symmetric Group, Addison-Wesley Publishing Company, 1981.
  * [12] Y. Liu, Y. Yang, Huppert’s analogue conjecture for ${\mbox{PSL}}(3,q)$ and ${\mbox{PSU}}(3,q)$, preprint, arXiv:2209.02660.
  * [13] G. Malle, A. Moretó, Nonsolvable groups with few character degrees, J. Algebra 294 (2005), 117-126.
  * [14] A. Moretó, Complex group algebras of finite groups: Brauer’s problem 1. Adv. Math. 208 (2007), no. 1, 236-248.
  * [15] G. Qian, Y. Wang, H. Wei, Co-degrees of irreducible characters in finite groups, J. Algebra 312 (2007), 946-955.
  * [16] J. Bray, D. Holt, C. Roney-Dougal, The Maximal Subgroups of the Low-Dimensional Finite Classical Groups, London Mathematical Society Lecture Note Series 407, Cambridge University Press, 2013.
  * [17] M. Suzuki, On a class of doubly transitive groups, Ann. Math. 75 (1962), 105-145.
  * [18] H. N. Ward, On Ree’s series of simple groups, Trans. Amer. Math. Soc. 121 (1966), 62-89.
  * [19] Hung P. Tong-Viet et al. On Huppert’s conjecture for $G_{2}(q),q\geq 7$, J. Pure Appl. Algebra (2012).


# Boosting Diffusion Models with an Adaptive Momentum Sampler

Xiyu Wang, Anh-Dung Dinh, Daochang Liu, Chang Xu
School of Computer Science, Faculty of Engineering, The University of Sydney,
Australia
<EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Diffusion probabilistic models (DPMs) have been shown to generate high-quality
images without the need for delicate adversarial training. However, the
current sampling process in DPMs is prone to violent shaking. In this paper,
we present a novel reverse sampler for DPMs inspired by the widely-used Adam
optimizer. Our proposed sampler can be readily applied to a pre-trained
diffusion model, utilizing momentum mechanisms and adaptive updating to smooth
the reverse sampling process and ensure stable generation, resulting in
outputs of enhanced quality. By implicitly reusing update directions from
early steps, our proposed sampler achieves a better balance between high-level
semantics and low-level details. Additionally, this sampler is flexible and
can be easily integrated into pre-trained DPMs regardless of the sampler used
during training. Our experimental results on multiple benchmarks demonstrate
that our proposed reverse sampler yields remarkable improvements over
different baselines. We will make the source code available.

## Introduction

Deep generative modeling has emerged as a popular area of research due to its
significance in comprehending and managing data. In image generation, GANs
have dominated the field since its birth in Goodfellow et al.. Compared to
other loglikelihood generative models (Kingma and Welling 2013; Hinton and
Salakhutdinov 2006; Shao et al. 2021), GANs show superiority over them in
terms of both quality and diversity. However, the employment of adversarial
training in GANs causes instability during its training and mode collapse,
requiring specific optimization techniques and architectures.

(a) DDPM

(b) Our (DDPM + AM)

Figure 1:  Current DPMs’ reverse sampling processes often exhibit severe
vibration, which can lead to excessive noise or missing high-level components
in the generated images. To address this issue, this paper proposes a new
sampler with adaptive momentum (AM).

As an alternative to adversarial training, iterative models such as Diffusion
Probabilistic Models (DPMs) (Ho, Jain, and Abbeel 2020; Song et al. 2020) have
emerged as promising option. Denoising Diffusion Probabilistic Model (DDPM)
(Ho, Jain, and Abbeel 2020), and its variants (Nichol and Dhariwal 2021; Song,
Meng, and Ermon 2020) are one of the streams based on the iterative process
whose process includes two phases. The first phase is to diffuse the image
into a predefined Gaussian noise, and the second phase will try to reverse the
trajectory to recover the image. As a recent development, Denoising Diffusion
Implicit Model (DDIM) (Song, Meng, and Ermon 2020) devises an accelerated
version by turning DDPM into an implicit process and facilitates the reduction
of the number of time steps during image generation. Meanwhile, the score-
based scheme (Song and Ermon 2019, 2020; Song et al. 2020) is a theoretical
version that works on the same mechanism. The main difference of the score-
based model lies in its utilization of analytic tools, Stochastic Differential
Equations (SDEs), to diffuse and denoise the image. The two iterative schemes
of diffusion models and score-based models are unified upon the crucial
connection observed in DDIM between its optimization technique and Ordinary
Differential Equations (ODEs). Therefore, we focus on the diffusion models in
this paper since the two categories belong to the same broader generalization.

Figure 2: The images presented are generated from the final iteration,
$\bar{x}_{0}$, after running 1000 steps of DDPM with our novel sampler with
different scales of momentum. The momentum value ($b$) progressively increases
from left to right (0 to 1.75), indicating an increasing reliance on earlier
steps. With larger momentum, the final images prioritize intricate patterns
and textures while also maintaining shapes and contours. By demonstrating the
impact of varying momentum degrees, these final images provide an intuitive
illustration of the adaptive momentum sampler’s ability to improve low-level
details while retaining high-level semantics.

The original reverse process in DPMs, based on the Markovian chain (Ho, Jain,
and Abbeel 2020), can be regarded as one of the simple numerical solutions of
the diffusion process’s Stochastic Differential Equations (SDEs). However,
this vanilla reverse generative iteration used in DPMs, e.g., DDPM or DDIM,
tends to meet narrow valleys, small humps, leading to excessive noise or
missing high-level element in the generated images as the example in Fig.
1(a). One reason for this is that the vanilla sampler used in DPMs employs
noisy updates at each time step, which can lead to unstable sampling.
Additionally, DDPM’s use of a Markov process exacerbates this issue by
deriving a new update direction at each step, without considering the global
trajectory across steps. These limitations have motivated us to develop a new
sampler that can more effectively explore the updating signals across steps,
in order to stabilize the sampling process and facilitate the diffusion
model’s escape from local optima. In this paper, we bring a new training-free
reverse sampler for diffusion models to increase the quality of the generated
samples by imitating the well-known Adam optimizer (Kingma and Ba 2014), which
has shown excellent performance in neural network training. Specifically, the
proposed sampler acts in a non-Markovian manner by accumulating a velocity
vector across steps to smooth the update direction. A moving average of
second-order moments is also maintained to adaptively adjust the update pace,
which serves as a natural form of step-size annealing.

The first benefit of this new sampler is the foremost being a better trade-off
between generating high-level semantics, such as shapes and outlines, and
restoring low-level details, such as fine texture. To illustrate this point,
we refer to Fig. 2, which depicts samples generated using different scales of
momentum. As observed, employing a larger momentum that heavily re-uses the
update direction of early steps leads to augmented details while still
preserving high-level information. This phenomenon aligns with the two stages
of learning for likelihood-based models (Rombach et al. 2022), where the first
stage focuses on learning high-frequency details, while the second stage
focuses on learning conceptual compositions. With a suitable momentum value,
the adaptive momentum in our sampler coordinates these two learning stages,
thus effectively balancing between high-level and low-level information.

The second benefit of the proposed sampler is its flexibility to be easily
integrated with existing pre-trained diffusion models. This non-parameterized
sampler requires no additional training, and its momentum is dynamically
adjusted on the fly during sampling. This adaptability is particularly
advantageous in mitigating the train-test gap, as the sampler can be easily
plugged into diffusion models pre-trained with different samplers or
customized settings.

Experimental results on five common benchmarks, CIFAR-10 (Krizhevsky, Hinton
et al. 2009), CelebA (Liu et al. 2018), ImageNet (Deng et al. 2009), LSUN (Yu
et al. 2015) and CelebA-HQ (Karras et al. 2017), show that the proposed
adaptive momentum sampler improves both DDPM and DDIM in terms of generating
quality. In summary, the contribution of this paper is to newly propose a
balanced, flexible, and highly-performing sampler that can be easily applied
to pre-trained diffusion models.

## Related works

Diffusion Probabilistic Models (Ho, Jain, and Abbeel 2020) has been used as
one of the effective generative models that avoid the adversarial training
from GANs (Goodfellow et al. 2014). By enabling the reverse process of
diffusion, Denoising Diffusion Probabilistic Models (DDPMs) can reconstruct
images. However, as previously mentioned, DDPMs suffer from the issue of
expensive computation time due to their large iterative time steps. To address
this problem, DDIM (Song, Meng, and Ermon 2020) ”implicates” the model and
allows it to run with far fewer iterations, significantly reducing the
inference time compared to DDPM.

On the other hand, a score-based model via SDE is also a fresh approach to the
diffusion model, where both the diffusion process and the denoising process
are modeled by SDEs. Yang Song et al.(Song and Ermon 2019) first propose to
generate samples from latent noise via the Dynamic Langevin Sampling
technique. The author utilized the denoising score approximating scheme
(Vincent 2011) where the trajectory of noise is recorded in the scoring
network $s_{\theta}$. The network is trained via Noise Conditional Score
Networks. With the concurrent development of the DDPM/DDIM (Song, Meng, and
Ermon 2020) along with the score-based models, and these two schemes both
utilize diffusion and denoising schemes as their main mechanisms, Yang Song
(Song et al. 2020) proposes to model the diffusion process via a Stochastic
Differential Equation (SDE) to unify the two streams. The diffusion process is
modeled as the solution to an Ito SDE. The objective is to construct a
diffusion process $\\{\mathbf{x}(t)\\}^{T}_{t=0}$, the time index $t\in[0,T]$
is a continuous variable with $\mathbf{x}(0)\sim p_{0}$ belongs to the
original data distribution.

Improved Denoising Probabilistic Models (Dhariwal and Nichol 2021; Dockhorn,
Vahdat, and Kreis 2021; Zheng et al. 2022) propose to improve the quality of
DDPM by using conditional information. While the achieved performance is
significant, the two models need to train an additional classifier to achieve
noise-aware information. Furthermore, the labels necessary for training these
models are also exorbitant to collect in many practical tasks. In this work,
we avoid using additional information besides training images. (Kim et al.
2022) improves the DDPM by softening the static truncation hyperparameters
into a random variable. Ho et al.in (Ho et al. 2022) also propose cascaded
diffusion models that show superior synthetic images compared to DDPM.
However, these works require re-training the expensive DDPM to achieve little
better results compared to the original baselines. In this work, we propose a
momentum scheme that can behave on a pre-trained DDPM model. Thus, we could
avoid large training DDPM/DDIM models, while still achieving fruitful results
from improving image quality.

## Preliminary

### Denoising Diffusion Probabilistic Model

Generally, Gaussian diffusion models are utilized to approximate the data
distribution $\mathbf{x}_{0}\sim q(\mathbf{x}_{0})$ by
$p_{\theta}(\mathbf{x}_{0})$. $p_{\theta}(\mathbf{x}_{0})$ is modelled to be
the form of latent variables models:

$\displaystyle\begin{split}p_{\theta}(\mathbf{x}_{0})&=\int
p_{\theta}(\mathbf{x}_{0:T})d\mathbf{x}_{1:T},\text{where}\\\
p_{\theta}(\mathbf{x}_{0:T})&=p_{\theta}(\mathbf{x}_{T})\prod_{t=1}^{T}p_{\theta}^{(t)}(\mathbf{x}_{t-1}|\mathbf{x}_{t})\end{split}$

where $x_{1},x_{2},...,x_{T}$ are latent variables with the same dimensions
with $x_{0}$.

$\displaystyle q(\mathbf{x}_{1:T}|\mathbf{x}_{0}):=$
$\displaystyle\prod_{t=1}^{T}q\left(\mathbf{x}_{t}|\mathbf{x}_{t-1}\right)\
,\text{where }$ (1) $\displaystyle
q\left(\mathbf{x}_{t}\mid\mathbf{x}_{t-1}\right):=$
$\displaystyle\mathcal{N}\left(\mathbf{x}_{t};\sqrt{1-\beta_{t}}\mathbf{x}_{t-1},\beta_{t}\mathbf{I}\right)\
.$

Thus, the diffusion process from a data distribution to a Gaussian
distribution for time step $t$ can be expressed as:

$\mathbf{x}_{t}=\sqrt{\alpha_{t}}\mathbf{x}_{0}+\sqrt{1-\alpha_{t}}\epsilon\
,$ (2)

where the $\alpha_{t}:=\prod_{i=0}^{t}\left(1-\beta_{i}\right)$ and
$\epsilon\sim\mathcal{N}(\mathbf{0,I})$. The Ho et al.(Ho, Jain, and Abbeel
2020) trains a U-net (Ronneberger, Fischer, and Brox 2015) model $\theta$ to
fit the data distribution $\mathbf{x}_{0}$ by maximizing the following
variational lower-bound:

$\displaystyle\max_{\theta}\mathbb{E}_{q\left(\mathbf{x}_{0}\right)}\left[\log
p_{\theta}\left(\mathbf{x}_{0}\right)\right]\leq$ (3)
$\displaystyle\max_{\theta}\mathbb{E}_{q\left(\mathbf{x}_{0},\mathbf{x}_{1},\ldots,\mathbf{x}_{T}\right)}\left[\log
p_{\theta}\left(\mathbf{x}_{0:T}\right)-\log
q\left(\mathbf{x}_{1:T}\mid\mathbf{x}_{0}\right)\right]\ ,$

where the $q\left(\mathbf{x}_{1:T}\mid\mathbf{x}_{0}\right)$ is certain
inference distribution, which could be calculated by the Bayes theorem with
$\mathbf{x}_{0}$ and $\mathbf{x}_{T}$, over the latent variable.

### Denoising Diffusion Implicit Model

DDPM’s dependence on the Markovian process has two main problems. First, due
to the Markovian property, the generative process is forced to have a similar
number of time steps to the diffusion process. Secondly, the stochastic
process causes uncertainty in the synthetic images. This challenges the image
interpolation in the latent space.

DDIM generalizes the DDPM as a Non-Markovian process. Different from the Eq.
1, $x_{t-1}$ is conditioned by both $x_{t}$ and $x_{0}$:

$q_{\sigma}(\mathbf{x}_{1:T}|\mathbf{x}_{0})=q_{\sigma}(\mathbf{x}_{T}|x_{0})\prod_{t=2}^{T}q_{\sigma}(\mathbf{x}_{t-1}|\mathbf{x}_{t},\mathbf{x}_{0})$
(4)

Where $q_{\sigma}(\mathbf{x}_{t-1}|\mathbf{x}_{t},\mathbf{x}_{0})$ is chosen
so that
$q_{\sigma}(x_{T}|x_{0})=\mathcal{N}(\sqrt{\alpha_{T}}x_{0},(1-\alpha_{T})\mathbf{I})$:

$\displaystyle\begin{split}q_{\sigma}(\mathbf{x}_{t-1}|\mathbf{x}_{t},\mathbf{x}_{0})=&\mathcal{N}(\sqrt{\alpha_{t-1}}\mathbf{x_{0}}+\\\
&\sqrt{1-\alpha_{t-1}-\sigma^{2}_{t}}\frac{\mathbf{x}_{t}-\sqrt{\alpha_{t}}\mathbf{x}_{0}}{\sqrt{1-\alpha_{T}}},\sigma_{t}^{2}\mathbf{I})\end{split}$

From Eq. 2, $\mathbf{x}_{t}$ can be obtained by sampling $\mathbf{x}_{0}\sim
q(x_{0})$ and $\epsilon_{t}\sim\mathcal{N}(0,\mathbf{I})$. By training the
model $\epsilon_{\theta}^{(t)}$ to predict $\epsilon_{t}$ at each time step,
$x_{0}$ predicting function $f_{\theta}^{(t)}$ is defined as:

$f_{\theta}^{(t)}(\mathbf{x}_{t})=\frac{\mathbf{x}_{t}-\sqrt{1-\alpha_{t}}\epsilon_{\theta}^{(t)}(\mathbf{x}_{t})}{\sqrt{\alpha_{T}}}$

This results in the whole generative process as:

$p_{\theta}^{(t)}(\mathbf{x}_{t-1}|\mathbf{x}_{t})=\begin{cases}\mathcal{N}(f_{\theta}^{(1)}(\mathbf{x}_{1}),\sigma_{1}^{2}\mathbf{I})\quad&\text{if
}t=1\\\
q_{\sigma}(\mathbf{x}_{t-1}|\mathbf{x}_{t},f_{\theta}^{(t)}(\mathbf{x}_{t}))&\text{otherwise},\end{cases}$

$\theta$ is optimized as Eq. 3 with
$q_{\sigma}(\mathbf{x}_{1:T}|\mathbf{x}_{0})$ is defined in Eq. 4. Based on
the defined generative process, given a sample $\mathbf{x}_{t}$, we could
sample the $\mathbf{x}_{t-1}$ as:

$\displaystyle\mathbf{x}_{t-1}=$
$\displaystyle\sqrt{\alpha_{t-1}}\underbrace{\left(\frac{\mathbf{x}_{t}-\sqrt{1-\alpha_{t}}\epsilon_{\theta}^{(t)}(\mathbf{x}_{t})}{\alpha_{t}}\right)}_{\mathrm{predicted\
\mathbf{x}_{0}}}+$
$\displaystyle\underbrace{\sqrt{1-\alpha_{t-1}-\sigma_{t}^{2}}\cdot\epsilon_{\theta}^{(t)}(\mathbf{x}_{t})}_{\mathrm{direction\
pointing\ to\ \mathbf{x}_{t}}}\
+\underbrace{\sigma_{t}\epsilon_{t}}_{\mathrm{random\ noise}}$ (5)

where
$\sigma_{t}=\eta\sqrt{(1-\alpha_{t-1})/(1-\alpha_{t})}\sqrt{1-\alpha_{t}/\alpha_{t-1}}$
and $\eta=0$ (Song, Meng, and Ermon 2020) or $\eta=1$ (Song, Meng, and Ermon
2020) or $\eta=\sqrt{(1-\alpha_{t})/(1-\alpha_{t-1})}$ (Ho, Jain, and Abbeel
2020). Yang Song et al.(Song and Ermon 2019) have proved that when
$\eta=\sqrt{(1-\alpha_{t})/(1-\alpha_{t-1})}$ the Eq. 5 is essentially a
different discretization to the same reverse-time SDEs and Jiaming Song (Song,
Meng, and Ermon 2020) shows that when $\eta=0$ the Eq. 5 similarity to Euler
integration for solving ODEs. We provide when the $\eta=1$ is the one type of
DDPM, the reverse process is approximate solution of the same reverse-time
SDEs in Appendix B.

## Methodology

In this paper, we propose a training-free Adaptive Momentum Sampler to
generate high-quality images, which can build long-term communications between
the previously explored path and the current denoising direction. The first
part of this section presents how to integrate the basic momentum method into
the origin inference process of DDPM/DDIM. After that, we illustrate how to
effectively adjust the pacing rate for denoising with the moving average of
the squared prior increments. In each part, we also show the design of how to
trade-off between high- and low-level information.

Figure 3:  The line chart shows one pixel value of generated $\mathbf{x}_{t}$
(blue line) and the predicted $\mathbf{x}_{0}$ (orange line) in DDPM reverse
process as Eq. 5. The top and bottom pictures are the corresponding $t$-th
generated $\mathbf{x}_{t}$ and predicted $\mathbf{\hat{x}}_{0}$.

### Momentum Sampler

We leverage the momentum method to achieve a better reverse process for
diffusion models. The momentum method is widely used in accelerating the
optimization of gradient flow in neural network training. The memorization of
previously searched directions contributes to the optimizer’s overcoming
narrow valleys, small humps. We find that the momentum method can also benefit
the reverse process of diffusion SDEs and ODEs.

Inspired by SGD with momentum in optimizing neural networks, we replace the
Euler-Maruyama method with the momentum method in the reverse process of
diffusion models to avoid the plight mentioned. As shown in the Fig. 3, there
is a phenomenon observed during the sampling phase: the process of reverse
sampling $\mathbf{x}_{t}$ (blue line) is noisy with many vibrations, while the
prediction of $\mathbf{x}_{0}$ from Eq. 5 (red line) is relatively stable and
tractable. Therefore, the sampling process contains some trend information,
enabling our momentum sampler to utilize such information and improve the
sampling procedure

However, the three terms in Eq. 5 are interdependent and complement each
other, therefore we jointly track the history of these terms using a single
momentum term. We first repeat the Eq. 5 as an incremental form of
$\mathbf{x}$. For brevity, we let the $\bar{\mathbf{x}}_{t}=\
\frac{\mathbf{x}_{t}}{\sqrt{\alpha_{t}}}$ and the
$\mu=\left(\sqrt{\frac{1-\alpha_{t-1}-\sigma_{t}^{2}}{\alpha_{t-1}}}-\sqrt{\frac{1-\alpha_{t}}{\alpha_{t}}}\right)$.
And then, we can formulate the increment of $\bar{\mathbf{x}}_{t}$ and rewrite
the DDPM (or DDIM) iteration Eq. 5, as:

$\displaystyle\mathbf{d\bar{x}}_{t}=$ $\displaystyle\
\mu\cdot\epsilon_{\theta}^{(t)}(\mathbf{x}_{t})+\frac{\sigma_{t}}{\sqrt{\alpha_{t-1}}}\cdot\epsilon_{t}\
\mathrm{,}$ (6) $\displaystyle\mathbf{\bar{x}}_{t-1}=$ $\displaystyle\
\mathbf{\bar{x}}_{t}+\mathbf{d\bar{x}}_{t}\ \mathrm{.}$

Instead of only relying on the single last step result to generate samples, we
incorporate the effects of prior directions as follows:

$\displaystyle\mathbf{m}_{t-1}=$ $\displaystyle\enspace
a\cdot\mathbf{m}_{t}+b\cdot\mathbf{d\bar{x}}_{t}\ \mathrm{,}$
$\displaystyle\mathbf{\bar{x}}_{t-1}=$
$\displaystyle\enspace\mathbf{\bar{x}}_{t}+\mathbf{m}_{t-1}\ \mathrm{,}$

where the $a$ is the damping coefficient, and the $a$ is a history-dependent
velocity coefficient. Since the superposition property of the Gaussian
distribution, we use the spherical difference, $a^{2}+b^{2}=1$, to balance the
momentum and current value. The $\mathbf{m}_{t}$ is the current momentum of
$t$-th iteration, and the $\mathbf{m}_{T}=\mathbf{0}$. The strength of the
momentum method is controlled by the $a$ and $b$ coefficient.

### Adaptive Momentum Sampler

In this section, we study how to adapt the learning rate based on the running
average of recent magnitudes of the increment, $\mathbf{d\bar{x}}_{t}$.
Besides the momentum-based sampling process only depending on the advantage of
momentum by using a moving average, the idea of Root Mean Square Propagation
(Mukkamala and Hein 2017) (RMSProp) can also be applied to the probabilistic
diffusion models generation process. To be more specific, we imitate RMSProp
to automatically tailor the step size with a decaying average on each pixel.
In this way, the process solver will focus on the most recently observed
partial gradients and discard history from the extreme past as shown in Fig. 3
blue line.

We propose an Adaptive Momentum sampling process that adapts the learning
rates of each pixel per time step The adaptive adjusting of denoising step
size is based not only on the average first moment but also on the average of
the second moments of the gradients. Based on the momentum sampling process,
we use a $\mathbf{v_{t}}$ to store an exponentially decaying average of prior
squared increment:

$\displaystyle\mathbf{v}_{t-1}\hskip 3.41418pt=$
$\displaystyle\enspace(1-c)\cdot\mathbf{v_{t}}+c\cdot\left\|\mathbf{d\bar{x}}_{t}\right\|^{2}_{2}$
(7) $\displaystyle\mathbf{m}_{t-1}=$ $\displaystyle\enspace
a\cdot\mathbf{m}_{t}+b\cdot\mathbf{d\bar{x}}_{t}$ (8)
$\displaystyle\mathbf{\bar{x}}_{t-1}=$
$\displaystyle\enspace\mathbf{\bar{x}}_{t}+\frac{\mathbf{m}_{t-1}}{\sqrt{\mathbf{v}_{t-1}}+\zeta}\
\mathrm{,}$

where the $c$ is the decay rate to control the moving averages of squared
increment, and the $\mathbf{v_{t}}$ is the current averages of prior squared
increment, and the $\mathbf{v_{T}}=\mathbf{1}$, and the $\zeta$ is a smoothing
term (a small number) to avoid any division by 0. We use this moving average
of second-order moments to make the reverse process concentrate on the current
high-frequency information to avoid the image being over-smooth. Compared with
the low-frequency information, the high-frequency information, such as the
pattern and fine texture of images, is more sensitive to the second-order
increment $\mathbf{d\bar{x}}$. In this assumption, the pacing rate of the
high-frequency information will be adaptively magnified, while the pacing rate
of the low-frequency information is relatively stable. The adaptive momentum
sampler can future balance between high-frequency and low-frequency
information.

Algorithm 1 illustrates the adaptive momentum sampler process. Specifically,
we use the momentum increment, $\mathbf{m}_{t-1}$, to replace the current
increment of the $t$-th iteration of noised image. The $a_{t}$ and $b_{t}$
build a trade-off between the former and current time-dependent score
function, demonstrating a strong numerical solver of the reverse process. As
shown in Fig. 2, this adjustment can force the reverse sampling process to
focus only on the early steps to generate more high-level semantics, such as
shapes and outlines, and smooth the low-level information, such as the
detailed pattern and texture. The $c$ controls the exponential decay
proportion for the second-moment estimates. In order to avoid excessive
changes in the magnitude of the momentum increment for each pixel, we amass
the square of the $\mathbf{d\bar{x}}_{t}$’s $L_{2}$ norm and set the
$\mathbf{v}_{T}=1$ during the implement. The basic momentum sampler could be
considered as a particular case of the adaptive momentum solver when $c=1$ all
the time. If $a=0$, $b=1$, and $c=1$ for all the $t$-th iterations, the
sampling process would degenerate to the original DDPM or DDIM generation
process.

Figure 4: This toy example on one-dimensional data to produce two points
$x=-2$ and $x=4$ in 200 steps. The background is the heat map with 10,000
samples. Additionally, the cyan and gold lines represent the value of the
generation sampling process with the original DDPM sampler and our momentum
sampler.

### Synthetic Data and Analyze.

In this section, we will compare the generation process of the vanilla sampler
with our proposed adaptive momentum sampler, both in practice and in theory.

#### Visualization

To perform a quantitative analysis, we trained a diffusion model to generate
1-dimension toy data with two points ($x=-2$ and $x=4$) over 200 timesteps. In
Fig. 4, we provide a visual representation of the differences between the
original DDPM sampler and our proposed adaptive momentum sampler during the
sampling process. The heatmaps in the background display the distribution of
values for 10,000 samples generated by the original DDPM sampler and our
adaptive momentum sampler, respectively. The lighter the color in the
background, the greater the number of samples.

Algorithm 1 Sampling with the Adaptive Momentum

1: Initialization:
$\mathbf{x_{T}}\sim\mathcal{N}(\mathbf{0,I}),\mathbf{m}=\mathbf{0},\mathbf{v_{T}}=\mathbf{1}$

2: for $t=T,\cdots,1$ do

3: $\epsilon_{t}\sim\mathcal{N}\left(\mathbf{0,I}\right)$ if $t>1$, else
$\epsilon_{t}=\mathbf{0}$

4: Update $\mathbf{d\bar{x}}_{t}$ based on Equation 6

5: $\mathbf{v}_{t-1}\hskip
3.41418pt=(1-c)\cdot\mathbf{v_{t}}+c\cdot\left\|\mathbf{d\bar{x}}_{t}\right\|^{2}_{2}$

6: $\mathbf{m}_{t-1}=a\cdot\mathbf{m}_{t}+b\cdot\mathbf{d\bar{x}}_{t}$

7: $\mathbf{x}_{t-1}\hskip
3.69899pt=\sqrt{\alpha_{t-1}}\left(\frac{\mathbf{x}_{t}}{\sqrt{\alpha_{t}}}+\frac{\mathbf{m}_{t-1}}{\sqrt{\mathbf{v}_{t-1}}+\zeta}\right)$

8: end for

9: return $\mathbf{x}_{0}$

Specifically, the heat map generated by the adaptive momentum sampler is
lighter, especially around the points $x=-2$ and $x=4$, indicating that it can
more precisely produce the value of point. Furthermore, the generation trace
of the adaptive momentum sampler is more stable, exhibiting less trembling,
while the generation trace of the original DDPM sampler (gold line) features
significant ineffective vibrations. Notably, for the gold line, the final
value generated by the vanilla DDPM sampler is inaccurate. In contrast, the
adaptive momentum sampler can more easily escape from narrow valleys, ensuring
continuity in the generation process and producing a more accurate final value
at last step.

#### Second-Order Approximation

We conducted a preliminary analysis to compare our method with the original
method. As per Song et al. (Song et al. 2020), the sampling process of
DDPM/DDIM uses a first-order approximation of numerical SDEs/ODEs solvers.
Building on this conclusion, we demonstrate in Appendix B that our method
represents a second-order approximation of SDEs/ODEs. Instead of utilizing the
Euler-Maruyama method for numerical solving SDEs/ODEs, we predict the next
result by utilizing the midpoint method with previously generated results and
the current state. This approach allows us to demonstrate that our method
converges to the actual sample of the pre-trained model of DDPM.

In general, the adaptive momentum sampler typically employs historical data to
facilitate a smoother generation process, as demonstrated by the gold line in
Fig 4 for DDPM+AM. By contrast, the gold line in Fig 4 for DDPM illustrates
early time steps characterized by wild swings, which can lead to misguided
outcomes and large variance values for the final point.

## Experiments

In this section, we quantitatively demonstrate the effectiveness of our
proposed sampling method. First, we provide the experimental setup. Next, the
method is quantitatively evaluated against the baseline samplers. The
improvement compared to the baseline will be highlighted on different
datasets. Lastly, an ablation study will be offered to inspect the impact of
each hyper-parameter.

### Experimental Setup

Datasets. Following most of the setup in DDPM/DDIM and Latent Diffusion Models
(LDM) (Rombach et al. 2022), we utilize CIFAR10 (Krizhevsky, Hinton et al.
2009) ($32\times 32$), CelebA (Liu et al. 2018) ($64\times 64$), ImageNet
(Deng et al. 2009) ($64\times 64$), LSUN (Yu et al. 2015) ($256\times 256$)
and CelebA-HQ (Karras et al. 2017) ($256\times 256$) in our experiments.

Configurations. We mainly employ the original DDIM, DDPM, Analytic-DPM (Bao et
al. 2022) and LDM in our comparisons as these schemes are solid and compact
baselines. Nonetheless, our proposed schemes can be applied to other improved
variants as well. For DDPM/DDIM and Analytic-DPM, the same pre-trained
diffusion models are used for the generation. The pre-trained models for
CIFAR10, LSUN and CelebA-HQ are collected from the DDPM (Ho, Jain, and Abbeel
2020), and the pre-trained models for CelebA and ImageNet are collected from
DDIM (Song, Meng, and Ermon 2020), and IDDPM (Song and Ermon 2020)
respectively. Besides, we also use the pre-trained models from LDM (Rombach et
al. 2022) for high-resolution image generation. The sampling steps are set to
4000 on ImageNet and 1000 on other datasets. For the Eq. 5, we select three
$\eta$ values, the $\eta=0$ will be equivalent to DDIM, $\eta=1$ will be a
DDPM case in (Song, Meng, and Ermon 2020), and $\eta=\hat{\eta}$ is another
DDPM case in its original paper (Ho, Jain, and Abbeel 2020). For settings
where the sampling step does not equal the original pre-trained model, we
follow the same strategy proposed in the DDIM, which replaces the $\alpha_{t}$
with the corresponding scaled $\alpha_{\tau}$. All the hyperparameters for the
sampling process are presented in Appendix. Our experiments run on one node
with 8 NVIDIA A100 GPUs. Except for CelebA, the generation process is
accelerated with the mixed-precision technique. We use ‘AM’ to denote sampling
with our proposed adaptive momentum scheme.

Table 1: The low-resolution image generation results on CIFAR10 (32 $\times$
32), ImageNet (64 $\times$ 64) and CelebA (64 $\times$ 64) measured in IS
$\uparrow$ and FID $\downarrow$. Note that a same pre-trained diffusion model
is utilized on each dataset with different sampling strategies. The
improvement of the adaptive momentum sampling (‘+AM’) is remarkable on most of
the datasets compared to the baselines in terms of FID. It is reasonable for
our method to have similar IS to baselines, since the adaptive momentum mainly
smooth the sampling trajectory which have no impact on changing the labels of
the image, while IS is sensitive to inter-class diversity only.

| CIFAR10 | ImageNet | CelebA |
---|---|---|---|---
Sampler | IS | FID | IS | FID | FID |
DDIM ($\eta=0$) | 8.16 $\pm$ 0.15 | 3.98 | 16.40 $\pm$ 0.25 | 19.09 | 3.40 |
DDIM + AM | 8.16 $\pm$ 0.15 | 3.81 | 16.35 $\pm$ 0.28 | 18.85 |  3.24 [0.08em] Analytic-DDIM | 8.32 $\pm$ 0.09 | 4.66 | 16.29 $\pm$ 0.30 | 17.63 | 3.26
Analytic-DDIM + AM | 8.30 $\pm$ 0.10 | 3.50 | 16.35 $\pm$ 0.28 | 17.51 | 3.14 |
DDPM ($\eta=1$) | 8.22 $\pm$ 0.09 | 4.72 | 17.14 $\pm$ 0.20 | 16.55 | 5.78 |
DDPM + AM | 8.41 $\pm$ 0.09 | 3.53 | 17.14 $\pm$ 0.21 | 16.32 |  2.50 [0.08em] Analytic-DDPM | 8.51 $\pm$ 0.09 | 4.01 | 17.16 $\pm$ 0.21 | 16.42 | 5.21
Analytic-DDPM + AM | 8.52 $\pm$ 0.09 | 3.53 | 17.15 $\pm$ 0.22 | 16.19 | 2.29 |
DDPM ($\eta=\hat{\eta}$) | 8.39 $\pm$ 0.15 | 3.16 | 17.15 $\pm$ 0.18 | 16.38 | 3.26 |
DDPM + AM | 8.46 $\pm$ 0.08 | 3.03 | 17.15 $\pm$ 0.19 | 16.05 | 3.17 |

Table 2: The high-resolution image generation results on CelebA-HQ (256
$\times$ 256) , Church (256 $\times$ 256) and Bedroom (256 $\times$ 256)
measured in FID $\downarrow$. The improvement of the adaptive momentum
sampling (‘+AM’) is remarkable on all of the datasets compared to the
baselines in terms of FID.

Sampler | CelebA-HQ | Church | Bedroom
---|---|---|---
DDIM ($\eta=0$) | 10.53 | 10.84 | 7.39
DDIM + AM | 9.73 | 8.17 |  5.91 [0.08em] LDM-DDIM | 9.29 | 3.98 | 3.87
LDM-DDIM + AM | 9.13 | 3.77 | 3.54
DDPM ($\eta=1$) | 12.34 | 7.81 | 6.24
DDPM + AM | 10.97 | 7.74 |  5.54 [0.08em] LDM-DDPM | 10.79 | 3.99 | 3.28
LDM-DDPM + AM | 10.47 | 3.92 | 3.21

Measurements. Similar to many other generative models (Goodfellow et al. 2014;
Bao et al. 2022; Nichol and Dhariwal 2021; Ho, Jain, and Abbeel 2020), we
mainly adopt two evaluation metrics which are Frechet Inception Score (FID)
and Inception Score (IS) (Lucic et al. 2018; Borji 2019). IS is highly
correlated with human-annotators (Salimans et al. 2016). Nevertheless, this
measure is often referred to as a method to measure inter-class diversity and
is less sensitive to the diversity of the images inside one label (Lucic et
al. 2018; Borji 2019). In contrast, FID can detect intra-class mode collapsing
as well (Lucic et al. 2018). As a result, FID is considered a better measure
for image generation tasks. A lower FID value indicates better performance,
while a larger IS is better. For each experiment, we draw 50K samples for
evaluation.

Figure 5: Generated samples for ImageNet and CelebA-HQ

### Overall Performance

Our proposed sampling scheme is first compared with the baseline samplers of
DDPM and DDIM in Table 1 and 2. The same pre-trained diffusion DDPM/DDIM is
used on each dataset to generate the data with vanilla samplers and samplers
combined with our adaptive momentum (the ‘+AM’ rows). Analytic-DPM (Bao et al.
2022), and LDM (Rombach et al. 2022) sampler is also used as a baseline to
justify our effectiveness on different diffusion schemes.

The results in Table 1 show the improvement of the adaptive momentum sampling
over baselines on most low-resolution datasets (lower than 64x64) regarding
FID. For the CelebA dataset, the proposed method performs significantly better
than DDPM with $\eta=1$. It not only outperforms the baselines by around 50%
but also achieves the state-of-the-art for this dataset which reaches around
2.29 FID. For CIFAR10, although the FID has been very low for the baselines,
we still have some rooms to improve from 3.16 to 3.03.

Table 2 shows that our adaptive momentum scheme leads to significant
improvements in most baselines when applied to high-resolution datasets such
as CelebA-HQ, LSUN Church, and LSUN Bedroom. We also demonstrate the
compatibility of our approach with a popular high-resolution model, Latent
Diffusion Models, which indicates that our method can be easily incorporated
into other DPM-based methods. These results demonstrate the flexibility of our
adaptive momentum scheme in improving the performance of various generative
models.

Fig. 5 presents a qualitative comparison of synthetic samples generated using
different methods. In comparison to the original DDPM sampler, our proposed
adaptive momentum sampler produces images with more realistic details and
pronounced object outlines, confirming its ability to balance high-level and
low-level information more effectively. For instance, our method enhances
image details while preserving original patterns, such as the recovered person
structure in row 2 column 4 and the enhanced facial details (forehead hair) in
the last picture of the 2nd row.

### Ablation Study

This subsection investigates different aspects of the settings, including
different time steps and hyperparameters’ effects.

Table 3: This table displays the FID $\downarrow$ scores for generation
results obtained using varying numbers of sampling steps.

| Sampling Steps
---|---
Sampler | 25 | 50 | 100 | 1000
DDIM ($\eta=0$) | 6.24 | 4.77 | 4.25 | 3.98
Analytic-DDIM | 9.96 | 6.02 | 4.88 | 4.66 [0.08em] DDIM + AM | 6.15 | 4.76 | 4.38 | 3.81
DDPM ($\eta=1$) | 14.44 | 8.23 | 5.82 | 4.72
Analytic-DDPM | 8.50 | 5.50 | 4.45 | 4.31 [0.08em] DDPM + AM | 7.19 | 4.10 | 3.61 | 3.53

#### Different Sampling Steps.

Table 3 illustrates the performance of our method when fewer sample steps are
used for acceleration on CIFAR10. The proposed method could perform better or
be comparable when using different sampling steps. On most of the settings, we
can provide up to 50% performance enhancements over the original DDPM sampler.
It is observed that the improvement is significant on the larger number of
sample steps while less evident on the smaller ones. This makes sense,
possibly because using a small number of sampling steps is not always
sufficient for accurate momentum estimation and noise suppression.

Table 4: This table presents the results of a hyperparameter experiment
measuring FID $\downarrow$ for our method. The best results among different
values of $b$ and $c$ are marked in boxes, and the best results of each full
column are shown in bold.

| Sampling Steps
---|---
Sampler | 25 | 50 | 100 | 1000
DDPM ($\eta=1$) | 14.44 | 8.23 | 5.82 | 4.72
DDPM + AM ($b=0.05$) | 14.43 | 8.13 | 5.71 | 4.68
DDPM + AM ($b=0.1$) | 10.13 | 6.52 | 5.88 | 4.09
DDPM + AM ($b=0.15$) | 7.25 | 4.41 | 3.65 | 3.54
DDPM + AM ($b=0.2$) | 20.26 | 5.07 | 4.04 | 3.98
DDPM + AM ($c=0.001$) | 7.23 | 4.39 | 3.64 | 3.54
DDPM + AM ($c=0.005$) | 7.22 | 4.35 | 3.62 | 3.53
DDPM + AM ($c=0.01$) | 7.19 | 4.33 | 3.61 | 3.53
DDPM + AM ($c=0.1$) | 7.61 | 4.10 | 3.67 | 3.85

#### Hyper-Parameters & Ablation Study.

Considering about the effects of $b$ and $c$ in the Eq. 7 and 8, we setup with
different values as in Table 4 on CIFAR10. The first five lines illustrate how
the FID of the generated images changes as the $b$ increases when $c=0$. In
general, the image quality will first increase and then decrease. When the
$b=0.15$, the FID achieves the lowest value for image generation in different
sampling steps, which is the best trade-off point. The last four lines show
how the $b$ influence the sampling results when $b=0.15$. Similarly, the FID
first decreases and then increases when the $b$ decrease. The last four rows
reflect the impact of $c$ with $b=0.15$, where the most of best performance is
obtained at $c=0.01$. Empirically, different denoising steps can share the
same hyper-parameters as shown in Table 3 and Appendix. Thus, we only need to
find $b_{\max}$ like $10^{-3},10^{-2}$ or $10^{-1}$ in the small denoising
steps, e.g., 100 or 200. Most of hyperparameter values are shared across
different datasets. We suggest choosing $b=10^{-3}$ or $10^{-2}$ and $c=0.01$
for high-resolution images as default.

Table 4 also presents the results of an ablation study on our proposed method,
the Adaptive Momentum Sampler. The first five rows display the outcomes when
the sampling process only utilizes the moving average of the moment increment.
Moreover, the comparison between the first and fourth rows reveals that our
proposed method outperforms the original reverse process sampler, underscoring
the efficacy of the momentum idea. Furthermore, comparing the fourth and
eighth rows, we observe that introducing adaptivity through the moving average
of second-order moments further enhances the performance of our adaptive
momentum sampler, which demonstrates its excellent generalization ability.

## Conclusion

In this work, we propose a training-free sampler to improve the generated
images of Diffusion Generative Models, especially for discrete discrete time
steps settings. Through extensive experiments, we found out that the adaptive
momentum sampler helps to smooth the denoising trajectory and, hence, improves
the quality of the generated images. In future works, we will expand the
scheme to continuous settings as well as with solid theoretical versions.

## References

  * Bao et al. (2022) Bao, F.; Li, C.; Zhu, J.; and Zhang, B. 2022.  Analytic-DPM: an analytic estimate of the optimal reverse variance in diffusion probabilistic models.  _arXiv preprint arXiv:2201.06503_.
  * Borji (2019) Borji, A. 2019.  Pros and Cons of GAN evaluation measures.  _Computer Vision and Image Understanding_ , 179: 41–65.
  * Deng et al. (2009) Deng, J.; Dong, W.; Socher, R.; Li, L.-J.; Li, K.; and Fei-Fei, L. 2009.  Imagenet: A large-scale hierarchical image database.  In _2009 IEEE conference on computer vision and pattern recognition_ , 248–255. Ieee.
  * Dhariwal and Nichol (2021) Dhariwal, P.; and Nichol, A. 2021.  Diffusion models beat gans on image synthesis.  _Advances in Neural Information Processing Systems_ , 34: 8780–8794.
  * Dockhorn, Vahdat, and Kreis (2021) Dockhorn, T.; Vahdat, A.; and Kreis, K. 2021.  Score-based generative modeling with critically-damped langevin diffusion.  _arXiv preprint arXiv:2112.07068_.
  * Goodfellow et al. (2014) Goodfellow, I.; Pouget-Abadie, J.; Mirza, M.; Xu, B.; Warde-Farley, D.; Ozair, S.; Courville, A.; and Bengio, Y. 2014.  Generative Adversarial Nets.  In Ghahramani, Z.; Welling, M.; Cortes, C.; Lawrence, N.; and Weinberger, K., eds., _Advances in Neural Information Processing Systems_ , volume 27. Curran Associates, Inc.
  * Hinton and Salakhutdinov (2006) Hinton, G. E.; and Salakhutdinov, R. R. 2006.  Reducing the dimensionality of data with neural networks.  _science_ , 313(5786): 504–507.
  * Ho, Jain, and Abbeel (2020) Ho, J.; Jain, A.; and Abbeel, P. 2020.  Denoising diffusion probabilistic models.  _Advances in Neural Information Processing Systems_ , 33: 6840–6851.
  * Ho et al. (2022) Ho, J.; Saharia, C.; Chan, W.; Fleet, D. J.; Norouzi, M.; and Salimans, T. 2022\.  Cascaded Diffusion Models for High Fidelity Image Generation.  _J. Mach. Learn. Res._ , 23: 47–1.
  * Karras et al. (2017) Karras, T.; Aila, T.; Laine, S.; and Lehtinen, J. 2017.  Progressive growing of gans for improved quality, stability, and variation.  _arXiv preprint arXiv:1710.10196_.
  * Kim et al. (2022) Kim, D.; Shin, S.; Song, K.; Kang, W.; and Moon, I.-C. 2022.  Soft truncation: A universal training technique of score-based diffusion model for high precision score estimation.  In _International Conference on Machine Learning_ , 11201–11228. PMLR.
  * Kingma and Ba (2014) Kingma, D. P.; and Ba, J. 2014.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_.
  * Kingma and Welling (2013) Kingma, D. P.; and Welling, M. 2013.  Auto-encoding variational bayes.  _arXiv preprint arXiv:1312.6114_.
  * Krizhevsky, Hinton et al. (2009) Krizhevsky, A.; Hinton, G.; et al. 2009.  Learning multiple layers of features from tiny images.
  * Liu et al. (2018) Liu, Z.; Luo, P.; Wang, X.; and Tang, X. 2018.  Large-scale celebfaces attributes (celeba) dataset.  _Retrieved August_ , 15(2018): 11.
  * Lucic et al. (2018) Lucic, M.; Kurach, K.; Michalski, M.; Gelly, S.; and Bousquet, O. 2018.  Are GANs created equal? a large-scale study.  _Advances in neural information processing systems_ , 31.
  * Mukkamala and Hein (2017) Mukkamala, M. C.; and Hein, M. 2017.  Variants of RMSProp and Adagrad with logarithmic regret bounds.  In _International conference on machine learning_ , 2545–2553. PMLR.
  * Nichol and Dhariwal (2021) Nichol, A. Q.; and Dhariwal, P. 2021.  Improved denoising diffusion probabilistic models.  In _International Conference on Machine Learning_ , 8162–8171. PMLR.
  * Rombach et al. (2022) Rombach, R.; Blattmann, A.; Lorenz, D.; Esser, P.; and Ommer, B. 2022.  High-resolution image synthesis with latent diffusion models.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 10684–10695.
  * Ronneberger, Fischer, and Brox (2015) Ronneberger, O.; Fischer, P.; and Brox, T. 2015.  U-net: Convolutional networks for biomedical image segmentation.  In _Medical Image Computing and Computer-Assisted Intervention–MICCAI 2015: 18th International Conference, Munich, Germany, October 5-9, 2015, Proceedings, Part III 18_ , 234–241. Springer.
  * Salimans et al. (2016) Salimans, T.; Goodfellow, I.; Zaremba, W.; Cheung, V.; Radford, A.; and Chen, X. 2016.  Improved techniques for training GANs.  _Advances in neural information processing systems_ , 29.
  * Shao et al. (2021) Shao, H.; Xiao, Z.; Yao, S.; Sun, D.; Zhang, A.; Liu, S.; Wang, T.; Li, J.; and Abdelzaher, T. 2021.  ControlVAE: Tuning, Analytical Properties, and Performance Analysis.  _IEEE transactions on pattern analysis and machine intelligence_.
  * Song, Meng, and Ermon (2020) Song, J.; Meng, C.; and Ermon, S. 2020.  Denoising diffusion implicit models.  _arXiv preprint arXiv:2010.02502_.
  * Song and Ermon (2019) Song, Y.; and Ermon, S. 2019.  Generative modeling by estimating gradients of the data distribution.  _Advances in neural information processing systems_ , 32.
  * Song and Ermon (2020) Song, Y.; and Ermon, S. 2020.  Improved techniques for training score-based generative models.  _Advances in neural information processing systems_ , 33: 12438–12448.
  * Song et al. (2020) Song, Y.; Sohl-Dickstein, J.; Kingma, D. P.; Kumar, A.; Ermon, S.; and Poole, B. 2020.  Score-based generative modeling through stochastic differential equations.  _arXiv preprint arXiv:2011.13456_.
  * Vincent (2011) Vincent, P. 2011.  A connection between score matching and denoising autoencoders.  _Neural computation_ , 23(7): 1661–1674.
  * Yu et al. (2015) Yu, F.; Seff, A.; Zhang, Y.; Song, S.; Funkhouser, T.; and Xiao, J. 2015.  LSUN: Construction of a large-scale image dataset using deep learning with humans in the loop.  _arXiv preprint arXiv:1506.03365_.
  * Zheng et al. (2022) Zheng, G.; Li, S.; Wang, H.; Yao, T.; Chen, Y.; Ding, S.; and Li, X. 2022.  Entropy-Driven Sampling and Training Scheme for Conditional Diffusion Generation.  In _European Conference on Computer Vision_ , 754–769. Springer.

## Appendix for “Boosting Diffusion Models with an Adaptive Momentum Sampler”

In this section, we provide additional experiments, proof and generated
samples about the adaptive momentum sampler.

##  Appendix A Experiments

In this section we show how we choose the hyperparameter and additional
experiments on CIFAR10, ImageNet, CelebA, CelebA-HQ, LSUN bedroom and Church
with different methods and the momentum’s adaptive properties.

### Hyperparameter Details

Table 5: Hyperparameters setting for CIFAR10, ImageNet, CelebA with different
methods

Method |  | CIFAR10 | ImageNet | CelebA
---|---|---|---|---
DDIM + AM ($\eta=0$) | $b$ | 0.4 | $1\times 10^{-3}$ | $1\times 10^{-3}$
$c$ | 0.9999 | 0.9999 | 0.9999
Analytic-DDIM + AM | $b$ | 0.4 | $1\times 10^{-3}$ | $1\times 10^{-3}$
$c$ | 0.9999 | 0.9999 | 0.9999
DDPM + AM ($\eta=1$) | $b$ | 0.15 | 0.15 | 0.15
$c$ | 0.999 | 0.999 | 0.9
Analytic-DDPM + AM | $b$ | 0.15 | 0.15 | 0.15
$c$ | 0.999 | 0.999 | 0.9
DDPM + AM ($\eta=\hat{\eta}$) | $b$ | 0.125 | $1\times 10^{-3}$ | $1\times 10^{-3}$
$c$ | 0.999 | 0.999 | 0.9

Table 6: Hyperparameter setting for CelebA-HQ, LSUN Church and Bedroom with
different methods.

Method |  | CelebA-HQ | Church | Bedroom
---|---|---|---|---
DDIM + AM ($\eta=0$) | $b$ | $1\times 10^{-3}$ | $3\times 10^{-3}$ | $1.5\times 10^{-3}$
$c$ | 0.9999 | 0.9999 | 0.9999
LDM-DDIM + AM | $b$ | $1\times 10^{-3}$ | $1\times 10^{-3}$ | $1\times 10^{-3}$
$c$ | 0.999 | 0.999 | 0.999
DDPM + AM ($\eta=1$) | $b$ | $1\times 10^{-2}$ | $1\times 10^{-2}$ | $5\times 10^{-2}$
$c$ | 0.999 | 0.999 | 0.999
LDM-DDPM + AM | $b$ | $1\times 10^{-3}$ | $1.5\times 10^{-3}$ | $1\times 10^{-3}$
$c$ | 0.999 | 0.999 | 0.999

Tables 5 and 6 provide an overview of the hyperparameters $b$ and $c$ used in
our method to obtain the results presented in Tables 1 and 2, respectively.
Notably, we observ that the hyperparameter choices for the same dataset using
a different method (DDPM/DDIM) are similar. Similarly, for the same pre-
trained model and similar sampling method, such as ”DDPM + AM” and ”Analytic-
DDPM + AM”, the hyperparameter choices can be also similar.

Overall, we recommend using $b_{\max}=10^{-3}$ or $10^{-2}$ and $c=0.999$ as
the default hyperparameters for achieving satisfactory improvements, with the
exception of the CIFAR10 dataset.

### Different Combinations of $a$ and $b$

Figure 6:  Samples generated by DDPM-AM with different $a$ and $b$
combinations. From left to right, the $b_{\max}$ is increase from 0.005 to 0.2
for four line pictures

In this subsection, we employ the generated samples to further demonstrate the
reason behind our choice of $a^{2}+b^{2}=1$, as illustrated in Fig.6.
Specifically, we consider two combinations of $a$ and $b$: $a+b=1$ or
$a^{2}+b^{2}=1$. At a high level, the momentum of $\bar{\mathbf{x}}$ can
adjust the current search direction based on the previously explored path.
When $a+b=1$, as depicted in Fig.6, this adjustment can force the reverse
sampling process to focus only on the early steps, emphasizing high-level
semantics such as shapes and outlines while smoothing out low-level
information such as patterns and textures. On the other hand, when
$a^{2}+b^{2}=1$, the sum of $a$ and $b$ exceeds 1 since $a,b<1$. In this
scenario, the momentum method can preserve or even enhance more detailed
information, including low-level semantics as shown in Fig. 6. As a result, we
typically choose $a^{2}+b^{2}=1$ to strike a better trade-off between high-
level and low-level semantics.

### Additional Different Sampling Steps Experiments

Table 7 and Table 8 show the performance of our method when fewer sample steps
are used for acceleration. The proposed method could achieve better or
comparable performance when using different sampling steps. As mentioned
above, it is observed that the improvement is significant on the larger number
of sample steps, while less evident on the smaller ones. This makes sense
possibly because using a small number of sampling steps is not always
sufficient for accurate momentum estimation and noise suppression.

Table 7: LSUN Bedroom image generation results measured in FID $\downarrow$,
with different numbers of sumpling steps used.

| Bedroom
---|---
dim($\tau$) | 25 | 50 | 100 | 1000
DDIM ($\eta=0$) | 7.75 | 6.54 | 6.52 | 7.39
FastDPM-DDIM | 9.86 | 8.37 | 9.94 | \- [0.08em] DDIM + AM | 7.78 | 6.42 | 6.02 | 5.90
DDPM ($\eta=1$) | 19.12 | 10.96 | 6.91 | 6.24
FastDPM-DDPM | 20.12 | 10.12 | 7.98 | \- [0.08em] DDPM + AM | 18.14 | 7.90 | 5.43 | 5.46

Table 8: LSUN Church image generation results measured in FID $\downarrow$,
with different numbers of sumpling steps used.

| Church
---|---
dim($\tau$) | 25 | 50 | 100 | 1000
DDIM ($\eta=0$) | 11.26 | 10.57 | 10.64 | 10.84 [0.08em] DDIM + AM | 10.62 | 9.17 | 8.67 | 8.17
DDPM ($\eta=1$) | 17.92 | 9.98 | 7.84 | 7.81 [0.08em] DDPM + AM | 17.95 | 9.11 | 7.57 | 7.74

### Rate-Distortion Trade-Off

Figure 7: The rate-distortion trade-off on CIFAR-10. The proposed momentum
scheme could achieve a better balance between high-level semantics and low-
level details.

The rate-distortion curves of a trained model using both adaptive momentum
inference and baseline inference schemes are plotted in Fig. 7. It was
criticized in the literature that diffusion models tend to spend much more
rates, i.i., model capacity, on restoring imperceptible distortions than high-
level semantics (Ho, Jain, and Abbeel 2020; Rombach et al. 2022), which is
also observed in Fig. 7 for the baseline scheme. In contrast, the newly
adaptive proposed momentum sampling is able to straighten the curve and thus
strike a better balance between generating high-level semantics and low-level
details. This could provide a possible explanation for the improved generation
performance observed in our experiments. Note that it is reasonable for the
red curve to have larger rates, which are computed by the cumulative sum of
the variational bound terms (Ho, Jain, and Abbeel 2020), since the momentum
inference is being applied to a model pre-trained without momentum. We expect
that incorporating an adaptive momentum strategy into the training process
could further enhance the rate-distortion trade-off as well as the generation
quality in future works.

##  Appendix B Proofs

In this section, we provide proofs that the reverse process is a first-order
approximation of the reverse-time SDEs, while our proposed method, the
adaptive momentum sampler, constitutes a second-order approximation of the
reverse-time SDEs/ODEs.

### Reverse Diffusion Sampling

Our proposed method leverage the adaptive momentum to enhance the reverse
solver. Thus, it is important to prove that the DDPM/DDIM sampler is a
solution of the reverse-time SDEs/ODEs. Yang Song et al.(Song and Ermon 2019)
have proved that when $\eta=\sqrt{(1-\alpha_{t})/(1-\alpha_{t-1})}$ the Eq. 5
is essentially a different discretization to the same reverse-time SDEs and
Jiaming Song (Song, Meng, and Ermon 2020) shows that when $\eta=0$ the Eq. 5
similarity to Euler integration for solving ODEs.

Here, we provide when the $\eta=1$ is the one type of DDPM, the reverse
process (Eq. 5) is approximate solution of the same reverse-time SDEs.
According to the DDPM (Ho, Jain, and Abbeel 2020), the forward process can be
rewrite as:

$\mathbf{\bar{x}}_{t}=\mathbf{\bar{x}}_{t-1}+\sqrt{\frac{\beta_{t}}{\alpha_{t}}}\
\epsilon\ \text{,}$ (9)

where the $\mathbf{\bar{x}}_{t}=\mathbf{x}_{t}/\alpha_{t}$,
$\beta_{t}=1-\alpha_{t}/\alpha_{t-1}$ and
$\epsilon\sim\mathcal{N}(\mathbf{0,I})$. Thus, based on (Song and Ermon 2019),
the reverse-time SDE will be:

$\mathbf{\bar{x}}_{t-1}=\mathbf{\bar{x}}_{t}+\frac{\beta_{t}}{\alpha_{t}}\bigtriangledown_{\mathbf{\bar{x}}}\log{p_{t}(\mathbf{\bar{x}})}+\sqrt{\frac{\beta_{t}}{\alpha_{t}}}\
\epsilon_{t}\ \text{,}$ (10)

where $\log{p_{t}(\mathbf{\bar{x}})}$ is the score of $p_{t}$. From the (Song,
Meng, and Ermon 2020), we can get that
$\bigtriangledown_{\mathbf{\bar{x}}}\log{p_{t}(\mathbf{\bar{x}})}=-\sqrt{\frac{1-\alpha_{t}}{\alpha_{t}}}\
\epsilon_{\theta}^{(t)}(\alpha_{t}\mathbf{\bar{x}}_{t})$. Therefore, we can
rewrite the Eq. 5 ($\eta=1$) as:

$\displaystyle\mathbf{\bar{x}}_{t-1}=$ $\displaystyle\
\mathbf{\bar{x}}_{t}+\sqrt{\frac{\alpha_{t}}{1-\alpha_{t}}}\left(\frac{\alpha_{t}-\alpha_{t-1}}{\alpha_{t-1}\alpha_{t}}\right)\epsilon_{\theta}^{(t)}(\mathbf{x}_{t})+$
$\displaystyle\sqrt{\frac{(1-\alpha_{t-1})(\alpha_{t-1}-\alpha_{t})}{(1-\alpha_{t})\alpha_{t-1}^{2}}}\epsilon_{t}$
$\displaystyle=$ $\displaystyle\
\mathbf{\bar{x}}_{t}+\frac{\beta_{t}}{\alpha_{t}}\bigtriangledown_{\mathbf{\bar{x}}}\log{p_{t}(\mathbf{\bar{x}})}+\sqrt{\frac{(1-\beta_{t})(1-\beta_{t}-\alpha_{t})\beta_{t}}{(1-\alpha_{t})\alpha_{t}}}\
\epsilon_{t}$ $\displaystyle\approx$ $\displaystyle\
\mathbf{\bar{x}}_{t}+\frac{\beta_{t}}{\alpha_{t}}\bigtriangledown_{\mathbf{\bar{x}}}\log{p_{t}(\mathbf{\bar{x}})}+\sqrt{\frac{\beta_{t}}{\alpha_{t}}}\
\epsilon_{t}$

Therefore, the sampler of Eq. 5 ($\eta=0$, $1$ or
$\sqrt{(1-\alpha_{t})/(1-\alpha_{t-1})}$) used as the baseline in this paper
is fundamentally another discretization to the same reverse-time SDEs/ODEs. We
further propose the adaptive momentum sampler based on these DDPM/DDIM reverse
process to improve the quality of generated images.

### Second-Order Approximation

In this study, we present a mathematical demonstration that our proposed
method, the Adaptive Momentum Sampler, converges to the true sample of the
model. Furthermore, we conduct a preliminary mathematical analysis showing
that the momentum sampler constitutes a second-order approximation of
SDEs/ODEs. Consistent with Song et al. (Song et al. 2020), the DDPM/DDIM
algorithm exhibits similarities to the Euler method for solving the following
SDEs/ODEs:

$\mathbf{\bar{x}}_{t-1}=\mathbf{\bar{x}}_{t}+\
\mu\epsilon_{\theta}^{t}(\mathbf{x}_{t})+\frac{\sigma_{t}}{\sqrt{\alpha_{t-1}}}\cdot\epsilon_{t}\
\mathrm{,}$ (11)

where $\bar{\mathbf{x}}_{t}=\ \frac{\mathbf{x}_{t}}{\sqrt{\alpha_{t}}}$ and
$\mu=\left(\sqrt{\frac{1-\alpha_{t-1}-\sigma_{t}^{2}}{\alpha_{t-1}}}-\sqrt{\frac{1-\alpha_{t}}{\alpha_{t}}}\right)$.
We can rewrite Eq. 11 as the first-order numerical procedure with
$\mathbf{d\bar{x}}_{t}=\mathbf{\bar{x}}_{t}-\mathbf{\bar{x}}_{t-1}$:

$\mathbf{d\bar{x}}_{t}=-\mu\cdot\epsilon_{\theta}^{(t)}(\mathbf{x}_{t})-\frac{\sigma_{t}}{\sqrt{\alpha_{t-1}}}\cdot\epsilon_{t}\
\mathrm{,}$ (12)

Consider using a second-order numerical solver for DDPM/DDIM, the resulting
equation is given by:

$\mathbf{d^{2}\bar{x}}_{t}+\lambda\mathbf{d\bar{x}}_{t}=-\mu\cdot\epsilon_{\theta}^{(t)}(\mathbf{x}_{t})-\frac{\sigma_{t}}{\sqrt{\alpha_{t-1}}}\cdot\epsilon_{t}\
\mathrm{,}$ (13)

where the parameter $\lambda$ acts as a friction term. Furthermore, this
former 13 can be rewrite as:

$\displaystyle\mathbf{d\bar{x}}_{t}$ $\displaystyle=\eta\ \mathrm{,}$
$\displaystyle-\mathbf{d^{2}\bar{x}}_{t}$
$\displaystyle=-\mathbf{d\eta}=\lambda\eta+\mu\cdot\epsilon_{\theta}^{(t)}(\mathbf{x}_{t})+\frac{\sigma_{t}}{\sqrt{\alpha_{t-1}}}\cdot\epsilon_{t}\
\mathrm{.}$

With the midpoint method:

$\displaystyle\mathbf{\bar{x}}_{t}-\mathbf{\bar{x}}_{t-1}=$
$\displaystyle\eta_{t-0.5}\ \mathrm{,}$ (14)
$\displaystyle\eta_{t+0.5}-\eta_{t-0.5}=$ $\displaystyle\lambda\
\frac{\eta_{t+0.5}+\ \eta_{t-0.5}}{2}$
$\displaystyle-\mu\epsilon_{\theta}^{t}(\mathbf{x}_{t})-\frac{\sigma_{t}}{\sqrt{\alpha_{t-1}}}\cdot\epsilon_{t}\
\mathrm{,}$ (15)

we can reformulate these two Eq. 14 and Eq. 15 to get the same Momentum
Sampler formula as in main paper:

$\displaystyle\mathbf{\bar{x}}_{t-1}$
$\displaystyle=\enspace\mathbf{\bar{x}}_{t}+\mathbf{m}_{t-1}\ \mathrm{,}$
$\displaystyle\mathbf{m}_{t-1}$ $\displaystyle=\enspace
a\cdot\mathbf{m}_{t}+b\cdot(\mu\cdot\epsilon_{\theta}^{(t)}(\mathbf{x}_{t})+\frac{\sigma_{t}}{\sqrt{\alpha_{t-1}}}\cdot\epsilon_{t})\
\mathrm{,}$

where $\mathbf{m}_{t}=-\eta_{t+0.5}$, $a=(2-\lambda)/(2+\lambda)$ and
$b=-2/(2+\lambda)$. Moreover, by modifying the implicit difference method, it
is clear that the our method is a second-order approximation of SEDs/ODEs.

##  Appendix C Samples

In this section, we show more samples in Fig. 8 (CIFAR10), Fig. 9 (CelebA),
Fig. 10 (Church) and Fig. 11 (Bedroom).

(a) DDIM-AM

(b) DDPM-AM

Figure 8: CIFAR10 samples from 1000 step DDIM-AM (up) and DDPM-AM (down)

(a) DDIM-AM

(b) DDPM-AM

Figure 9: CelebA samples from 1000 step DDIM-AM (up) and DDPM-AM (down)

(a) DDIM-AM

(b) DDPM-AM

Figure 10: LSUN Church samples from 1000 step DDIM-AM (up) and DDPM-AM (down)

(a) DDIM-AM

(b) DDPM-AM

Figure 11: LSUN Bedroom samples from 1000 step DDIM-AM (up) and DDPM-AM (down)