# Non-existence of Ulrich modules over Cohen-Macaulay local rings

Srikanth B. Iyengar  Department of Mathematics
University of Utah
Salt Lake City, UT 84112
U.S.A.  ,  Linquan Ma  Department of Mathematics
Purdue University
West Lafayette, IN 47907
U.S.A.  ,  Mark E. Walker  Department of Mathematics
University of Nebraska
Lincoln, NE 68588
U.S.A.  and  Ziquan Zhuang  Department of Mathematics
Johns Hopkins University
Baltimore, MD 21218
U.S.A.

###### Abstract.

Over a Cohen-Macaulay local ring, the minimal number of generators of a
maximal Cohen-Macaulay module is bounded above by its multiplicity. In 1984
Ulrich asked whether there always exist modules for which equality holds; such
modules are known nowadays as Ulrich modules. We answer this question in the
negative by constructing families of two dimensional Cohen-Macaulay local
rings that have no Ulrich modules. Some of these examples are Gorenstein
normal domains; others are even complete intersection domains, though not
normal.

###### Key words and phrases:

Cohen-Macaulay ring, section ring, Ulrich module, Ulrich sheaf

###### 2020 Mathematics Subject Classification:

13C13 (primary); 13H10, 13C14, 14F06 (secondary)

##  1\. Introduction

An _Ulrich module_ over a commutative noetherian local ring $R$ is a nonzero
maximum Cohen-Macaulay (MCM) $R$-module $U$ with the property that its minimal
number of generators, $\nu_{R}(M)$, is equal to is Hilbert-Samuel
multiplicity, $e_{R}(U)$. In [2] such modules are referred to as “maximally
generated” MCM modules because the inequality $\nu_{R}(M)\leq e_{R}(M)$ holds
for any MCM $R$-module $M$.

The mere existence of an Ulrich $R$-module has striking implications. For
instance, it implies that Lech’s conjecture holds for $R$: For any flat local
map $R\to S$ of local rings, one has $e(R)\leq e(S)$; see, for instance, [8,
pg. 69], or [15, Theorem 2.11]. Moreover, if $R$ admits an Ulrich module with
the additional property that its class in the Grothendieck group coincides
with the class of a free module, then for any $R$-module $L$ of finite length
and finite projective dimension, one has $\operatorname{length}(L)\geq e(R)$;
see [12] for more general results.

The existence of Ulrich modules is known in the following cases.

  1. $\bullet$

When $\dim R\leq 1$. For $\dim(R)=0$, the residue field $R/\mathfrak{m}$ is
Ulrich and for $\dim R=1$, the ideal $\mathfrak{m}^{e(R)-1}$ is Ulrich as an
$R$-module [2, 2.1].

  2. $\bullet$

Hypersurfaces and, more generally, local rings $R$ such that
$\operatorname{gr}_{\mathfrak{m}}(R)$ is a complete intersection [10].

  3. $\bullet$

When $\dim R\leq 2$ and $R$ is a standard graded ring over a field; the Cohen-
Macaulay case is in [2] and the general case follows from [4].

  4. $\bullet$

Complete local rings $R$ with $\dim R\leq 2$ and
$\operatorname{Proj}(\operatorname{gr}_{\mathfrak{m}}(R))$ geometrically
reduced. This result will appear in forthcoming work by the first three
authors.

See E. Coskun’s article [3] for a nice survey on Ulrich modules and Ulrich
sheaves.

Ulrich asked [20, §3] whether every Cohen-Macaulay local ring admits an
Ulrich111He did not refer to them as “Ulrich modules”, of course. module. Yhee
[21] constructed local domains of dimension two that have no Ulrich modules.
However, these examples are not Cohen-Macaulay.

In this work, we answer Ulrich’s original question in the negative:

######  Theorem 1.1.

There exist Gorenstein normal domains, and complete intersection local
domains, of dimension two that have no Ulrich modules.

This result packages Theorems 4.1 and 5.1.

Our technique for producing such examples involves a relationship between
Ulrich modules on $R$ and Ulrich sheaves on the projective scheme
$E\coloneqq\operatorname{Proj}(\operatorname{gr}_{\mathfrak{m}}(R))$.
Specifically, if $U$ is an Ulrich module, then the coherent sheaf
$\mathcal{F}$ on $E$ associated to the graded module
$\operatorname{gr}_{\mathfrak{m}}U$ is an Ulrich sheaf. When $R$ has dimension
two, $E$ is a curve and every curve admits an Ulrich sheaf, and thus at first
glance this approach seems unpromising. However, $\mathcal{F}$ extends to the
blowup of $\operatorname{Spec}R$ at $\mathfrak{m}$. For the rings occurring in
Theorem 1.1, we show no such “extendable” Ulrich sheaves exist on $E$. See
Section 2 for details.

Our examples can be obtained by starting with an ample line bundle
$\mathcal{L}$ on a projective curve $C$ such that $\Gamma(C,\mathcal{L})=0$
and the canonical pairing

$\Gamma(C,\mathcal{L}^{2})\otimes_{k}\Gamma(C,\mathcal{L}^{j})\longrightarrow\Gamma(C,\mathcal{L}^{j+2})$

is a surjection for all $j\geq 2$. In this situation, the local ring $R$
obtained by localizing (or completing) the section ring
$S\coloneqq\bigoplus_{j\geq 0}\Gamma(C,\mathcal{L}^{j})$ at its homogeneous
maximal ideal, cannot have any Ulrich modules; see Corollary 3.2.

The simplest situation in which this occurs is when $C$ is a smooth quartic
plane curve and $\mathcal{L}$ is a non-effective theta characteristic. There
are $36$ choices for such an $\mathcal{L}$ (assuming $k$ is algebraically
closed of characteristic not $2$), and each choice leads to a complete
Gorenstein normal domain of dimension two without any Ulrich modules. The
complete intersection example in Theorem 1.1 arises from the singular
projective plane curve $C$ cut out by the polynomial
$(y^{3}+x^{2}z)^{2}-x^{3}z^{3}$ and a line bundle $\mathcal{L}$ satisfying
$\mathcal{L}^{2}\cong\mathcal{O}_{C}(1)$.

##  2\. Ulrich modules and Ulrich sheaves

Let $(R,\mathfrak{m},k)$ be a noetherian local ring with maximal ideal
$\mathfrak{m}$ and residue field $k$. Let $M$ be a nonzero finitely generated
$R$-module. The Krull dimension and depth of $M$ are denoted $\dim_{R}M$ and
$0pt_{R}M$, respectively. The $R$-module $M$ is _maximal Cohen-Macaulay_ if it
is finitely generated and $0pt_{R}M=\dim R$. We write $\nu_{R}(M)$ for the
minimal number of generators of $M$, and $e_{R}(M)$ for its Hilbert-Samuel
multiplicity with respect to the ideal $\mathfrak{m}$.

### Ulrich modules

Any maximal Cohen-Macaulay $R$-module $M$ satisfies $\nu_{R}(M)\leq e_{R}(M)$;
see [20, Section 3]. When $e_{R}(M)=\nu_{R}(M)$ and $M$ is nonzero it is said
to be an _Ulrich module_.

Assume $k$ is infinite and let $J\subseteq\mathfrak{m}$ be a minimal reduction
of $\mathfrak{m}$. For every maximal Cohen-Macaulay $R$-module $M$, we have

$e(\mathfrak{m},M)=e(J,M)=\ell_{R}(M/JM)\geq\ell(M/\mathfrak{m}M)\,.$

Thus a nonzero maximal Cohen-Macaulay module $M$ is Ulrich if and only if
$JM=\mathfrak{m}M$ for one (or equivalently, every) minimal reduction $J$ of
$\mathfrak{m}$.

### Ulrich sheaves

Let $X$ be a projective scheme over a field and let $\mathcal{O}_{X}(1)$ be a
very ample line bundle on $X$. A coherent sheaf $\mathcal{F}$ is called an
_Ulrich sheaf for $(X,\mathcal{O}_{X}(1))$_ if it is nonzero and one of the
following equivalent conditions holds:

  1. (1)

$\operatorname{H}^{i}(X,\mathcal{F}(-j))=0$ for all $1\leq j\leq\dim(X)$, and
all $i$.

  2. (2)

$\operatorname{H}^{i}(X,\mathcal{F}(j))=0$ except when $i=0$, $j\geq 0$ or
$i=\dim(X)$, $j\leq-\dim(X)-1$.

Suppose $\pi\colon X\to\mathbb{P}^{n}_{k}$ is a finite map such that
$\pi^{*}\mathcal{O}_{\mathbb{P}^{n}_{k}}(1)=\mathcal{O}_{X}(1)$; such a map
exists when $k$ is infinite. Then a coherent sheaf $\mathcal{F}$ on $X$ is
Ulrich if and only if
$\pi_{*}\mathcal{F}\cong\mathcal{O}_{\mathbb{P}^{n}_{k}}^{r}$ for some integer
$r\geq 1$; see Eisenbud and Schreyer [4].

The definition of an Ulrich sheaf depends on the very ample line bundle
$\mathcal{O}_{X}(1)$. We suppress $\mathcal{O}_{X}(1)$ when it is clear from
the context. For instance, when $R$ is a standard graded noetherian ring over
a field and $X=\operatorname{Proj}(R)$, we take $\mathcal{O}_{X}(1)$ to be the
coherent sheaf associated to $R(1)$.

######  Remark 2.1.

If $\dim(X)=1$, then $\mathcal{F}$ is an Ulrich sheaf if and only if
$\mathcal{F}(-1)$ has no cohomology and $\mathcal{F}\neq 0$. Thus the
existence of an Ulrich sheaf for $(X,\mathcal{O}_{X}(1))$ is equivalent to the
existence of a nonzero coherent sheaf on $X$ with no cohomology, and the
latter property does not depend on the choice of $\mathcal{O}_{X}(1)$.

### Rees algebras and blowups

Let $R$ be a local ring and $M$ a finitely generated $R$-module. Consider the
graded $R$-module

$\mathscr{R}_{\mathfrak{m}}(M)\coloneqq\bigoplus_{n\geqslant
0}(\mathfrak{m}^{n}M)t^{n}\,.$

Then $\mathscr{R}_{\mathfrak{m}}(R)$ is a graded $R$-algebra, called the _Rees
ring_ of $R$ with respect $\mathfrak{m}$, and $\mathscr{R}_{\mathfrak{m}}(M)$
is a finitely generated graded $\mathscr{R}_{\mathfrak{m}}(R)$-module. The
canonical map $R\to\mathscr{R}_{\mathfrak{m}}(R)$ induces the morphism

$p\colon\operatorname{Bl}_{\mathfrak{m}}(R)\coloneqq\operatorname{Proj}(\mathscr{R}_{\mathfrak{m}}(R))\longrightarrow\operatorname{Spec}R\,.$

This is the _blowup_ of $\operatorname{Spec}R$ at $\\{\mathfrak{m}\\}$. The
_strict transform_ of an $R$-module $M$ is the coherent sheaf on
$\operatorname{Bl}_{\mathfrak{m}}(R)$ associated to the
$\mathscr{R}_{\mathfrak{m}}(R)$-module $\mathscr{R}_{\mathfrak{m}}(M)$.

The _associated graded_ module of $M$ is

$\operatorname{gr}_{\mathfrak{m}}(M)=k\otimes_{R}\mathscr{R}_{\mathfrak{m}}(M)=\bigoplus_{n\geqslant
0}(\mathfrak{m}^{n}M/\mathfrak{m}^{n+1}M)t^{n}\,.$

Thus $\operatorname{gr}_{\mathfrak{m}}(R)$ is a standard graded $k$-algebra
and the $\operatorname{gr}_{\mathfrak{m}}(R)$-module
$\operatorname{gr}_{\mathfrak{m}}(M)$ is finitely generated over
$\operatorname{gr}_{\mathfrak{m}}(R)$ by
${\operatorname{gr}_{\mathfrak{m}}(M)}_{0}$.

Set $E=\operatorname{Proj}(\operatorname{gr}_{\mathfrak{m}}(R))$; this is the
exceptional fiber of the blowup $p$.

${E}$${\operatorname{Bl}_{\mathfrak{m}}(R)}$${\operatorname{Spec}k}$${\operatorname{Spec}R}$$\scriptstyle{q}$$\scriptstyle{j}$$\scriptstyle{p}$

The strict transform of $M$ can also be described as the quotient
$p^{*}M/\Gamma_{E}(p^{*}M)$.

######  Lemma 2.2.

Let $U$ be an Ulrich $R$-module and $\mathcal{F}$ be the strict transform of
$U$. Then $\mathbf{L}{j}^{*}\mathcal{F}\cong j^{*}\mathcal{F}$ in
$\operatorname{D}^{b}(\operatorname{coh}E)$ and $j^{*}\mathcal{F}$ is an
Ulrich sheaf on $E$.

###### Proof.

Since $U$ is an Ulrich $R$-module, the graded
$\operatorname{gr}_{\mathfrak{m}}(R)$-module
$\operatorname{gr}_{\mathfrak{m}}(U)$ is Ulrich, in that it is maximal Cohen-
Macaulay, generated in degree $0$, and its multiplicity is equal to the number
of generators. This is proved in [2, Corollary 1.6] under additional
assumptions on $R,U$. Here is an argument in the general case.

The multiplicity and minimal number of generators of
$\operatorname{gr}_{\mathfrak{m}}(U)$ as a module over
$\operatorname{gr}_{\mathfrak{m}}(R)$ coincide with the corresponding
invariants of the $R$-module $U$. Thus the crucial point is that
$\operatorname{gr}_{\mathfrak{m}}(U)$ is maximal Cohen-Macaulay. We can assume
the residue field of $R$ is infinite, and hence that there exists an
$U$-regular sequence, say $\boldsymbol{x}\coloneqq x_{1},\dots,x_{d}$, such
that $\boldsymbol{x}U=\mathfrak{m}U$. Since $\boldsymbol{x}$ is $U$-regular,
one has an isomorphism of $\operatorname{gr}_{(\boldsymbol{x})}(R)$-modules

$(U/\boldsymbol{x}U)[X_{1},\dots,X_{d}]\xrightarrow{\ \cong\
}\operatorname{gr}_{(\boldsymbol{x})}(U)\quad\text{with
$X_{i}\mapsto\overline{x}_{i}$.}$

Here $\overline{x}_{i}$ denotes the residue class of $x_{i}$ in
$(\boldsymbol{x})/(\boldsymbol{x})^{2}$. Therefore
$\operatorname{gr}_{(\boldsymbol{x})}(U)$ is a maximal Cohen-Macaulay module
over $\operatorname{gr}_{(\boldsymbol{x})}(R)$. It remains to observe that
this module is isomorphic to $\operatorname{gr}_{\mathfrak{m}}(U)$, since
$\boldsymbol{x}U=\mathfrak{m}U$.

It follows that $j^{*}\mathcal{F}$, which is the coherent sheaf associated to
$\operatorname{gr}_{\mathfrak{m}}(U)$, is an Ulrich sheaf; see [4, Proposition
2.1]. The coherent sheaf $\mathcal{F}(1)$ is the sheaf associated to
$\mathscr{R}_{\mathfrak{m}}(\mathfrak{m}U)$ and the map
$\mathcal{F}(1)\to\mathcal{F}$ induced by
$t\colon\mathcal{O}_{B}(1)\to\mathcal{O}_{B}$, where
$B=\operatorname{Bl}_{\mathfrak{m}}(R)$, arises from the canonical inclusion

$\mathscr{R}_{\mathfrak{m}}(\mathfrak{m}U)=\bigoplus_{i\geqslant
0}\mathfrak{m}^{i+1}U\subseteq\bigoplus_{i}\mathfrak{m}^{i}U=\mathscr{R}_{\mathfrak{m}}(U)\,.$

In particular, the map $\mathcal{F}(1)\to\mathcal{F}$ is injective. This
proves that $\mathbf{L}{j}^{*}\mathcal{F}\cong j^{*}\mathcal{F}$. ∎

In the context of the Lemma 2.2, one has also
$\mathbf{R}{\pi}_{*}\mathcal{F}\cong U$. Moreover, the result has a converse,
and this can be used to construct Ulrich modules over certain two dimensional
rings. These results will appear in forthcoming work by the first three
authors (we will not use them in the sequel though).

##  3\. Criteria for non-existence

In this section we identify obstructions to the existence of an Ulrich module
over a local ring in terms of the geometry of the blowup at its maximal ideal.

######  Theorem 3.1.

Let $R$ be a noetherian ring and $\mathfrak{m}\subset R$ a maximal ideal with
$\dim R_{\mathfrak{m}}\geq 2$. Let
$\operatorname{Bl}_{\mathfrak{m}}(R)\to\operatorname{Spec}R$ be the blowup at
$\\{\mathfrak{m}\\}$ and $E$ the exceptional fiber of the blowup. If there
exists a locally principal ideal sheaf ${\mathcal{I}}$ on
$\operatorname{Bl}_{\mathfrak{m}}(R)$ and an integer $n\geq 2$ such that
${\mathcal{I}}^{n}$ defines $E$ in $\operatorname{Bl}_{\mathfrak{m}}(R)$, then
neither the local ring $R_{\mathfrak{m}}$ nor its $\mathfrak{m}$-adic
completion has any Ulrich modules.

###### Proof.

Let $\widehat{R}_{\mathfrak{m}}$ denote the $\mathfrak{m}$-adic completion of
$R_{\mathfrak{m}}$. Since the maps $R\to R_{\mathfrak{m}}$ and
$R\to\widehat{R}_{\mathfrak{m}}$ are flat, it is easy to verify that the
hypotheses carry over to both $R_{\mathfrak{m}}$ and
$\widehat{R}_{\mathfrak{m}}$. Thus we can assume in the rest of the argument
that $R$ is local, with maximal ideal $\mathfrak{m}$, and that $\dim R\geq 2$.

In what follows we write $B$ instead of $\operatorname{Bl}_{\mathfrak{m}}(R)$.
Observe that ${\mathcal{I}}^{n}\cong\mathcal{O}_{B}(1)$. Let $W$ be the
subscheme of $B$ cut out by $\mathcal{I}$.

We first consider the case when $\dim R=2$; equivalently, $\dim W=1$.

Assume to the contrary that there exists an Ulrich $R$-module $U$. Let
$\mathcal{F}$ be the strict transform of $U$ and $\mathcal{U}$ the sheaf on
$E$ associated to $\operatorname{gr}_{\mathfrak{m}}(U)$. We may identify
$\mathcal{U}$ with $\mathcal{F}/{\mathcal{I}}^{n}\mathcal{F}$. Setting
${\mathcal{U}}_{j}$ to be the coherent sheaf on $E$ given by
${\mathcal{I}}^{j}\mathcal{F}/{\mathcal{I}}^{n}\mathcal{F}$, we obtain a
filtration

$0=\mathcal{U}_{n}\subseteq\cdots\subseteq\mathcal{U}_{0}=\mathcal{U}$

of coherent sheaves on $E$. Identifying the sub-quotients with their
restrictions to $W$, for each $i$ one gets

${\mathcal{U}}_{i}/{\mathcal{U}}_{i+1}\cong\mathcal{U}|_{W}\otimes_{\mathcal{O}_{W}}\mathcal{L}^{i}$

where $\mathcal{L}=\mathcal{I}/{\mathcal{I}}^{2}$ is the line bundle that is
the restriction of $\mathcal{I}$ to $W$. Observe that $\mathcal{L}$ is ample
because $\mathcal{L}^{n}\cong{\mathcal{I}}^{n}/{\mathcal{I}}^{n+1}$ is the
restriction of $\mathcal{O}_{B}(1)$ to $W$.

Set $\mathcal{G}\coloneqq({\mathcal{U}}_{0}/{\mathcal{U}}_{1})(-1)$, again
viewed as a sheaf on $W$. Since $\dim W=1$ one has that $\dim\mathcal{G}=1$ as
well and hence the function

$\chi(\mathcal{G}\otimes\mathcal{L}^{j})=\mathrm{rank}_{k}\operatorname{H}^{0}(W,\mathcal{G}\otimes\mathcal{L}^{j})-\mathrm{rank}_{k}\operatorname{H}^{1}(W,\mathcal{G}\otimes\mathcal{L}^{j})$

is strictly increasing in $j$. Indeed
$\chi(\mathcal{G}\otimes\mathcal{L}^{j})$ is a polynomial function in $j$ of
degree at most one, by [19, Lemma 33.4.5.1], and since $\mathcal{L}$ is ample
and $\dim\mathcal{G}=1$, this polynomial must be linear with positive slope.
See [6, Propositions 23.78, 23.79] for more precise results.

The filtration of $\mathcal{U}$ above gives an injection and a surjection:

$\mathcal{G}\otimes\mathcal{L}^{n-1}\hookrightarrow{\mathcal{U}}(-1)\quad\text{and}\quad{\mathcal{U}}(-1)\twoheadrightarrow\mathcal{G}\,.$

Since $\mathcal{U}$ is an Ulrich sheaf, ${\mathcal{U}}(-1)$ has no cohomology;
see Remark 2.1. Combined with the fact that $\dim W=1$ one gets

$\operatorname{H}^{0}(W,\mathcal{G}\otimes\mathcal{L}^{n-1})=0=\operatorname{H}^{1}(W,\mathcal{G})$

and therefore that

$\chi(\mathcal{G}\otimes\mathcal{L}^{n-1})\leq 0\leq\chi(\mathcal{G})\,.$

Since $n\geq 2$, this contradicts the fact that
$\chi(\mathcal{G}\otimes\mathcal{L}^{j})$ is strictly increasing.

This completes the proof when $\dim R=2$.

It remains to explain the reduction to this case. So suppose $\dim R\geq 3$
and let $U$ be an Ulrich $R$-module. By enlarging the residue field if needed
we can assume it is infinite. One can then find a system of parameters
$\boldsymbol{x}\coloneqq x_{1},\dots,x_{d}$ of $R$ that is a regular sequence
on $U$ and such that $\boldsymbol{x}U=\mathfrak{m}U$. Let

$R^{\prime}=R/(x_{1},\dots,x_{d-2})\quad\text{and}\quad
U^{\prime}=U/(x_{1},\dots,x_{d-2})U.$

It is clear that the $R^{\prime}$-module $U^{\prime}$ is Ulrich. So it
suffices to show the hypotheses still hold for the ring $R^{\prime}$.

Let $B$ and $B^{\prime}$ denote the blowups of $\operatorname{Spec}R$ and
$\operatorname{Spec}R^{\prime}$ at their respective closed points, and let $E$
and $E^{\prime}$ be the corresponding exceptional fibers. It is
straightforward to verify that the following diagram of rings is co-cartesian:

${\mathscr{R}_{\mathfrak{m}}(R)}$${\mathscr{R}_{\mathfrak{m}R^{\prime}}(R^{\prime})}$${\operatorname{gr}_{\mathfrak{m}}(R)}$${\operatorname{gr}_{\mathfrak{m}R^{\prime}}(R^{\prime})}$

It thus follows that the square below is cartesian:

${E^{\prime}}$${E}$${B^{\prime}}$${B}$

Our hypothesis is that the ideal $\mathcal{J}$ cutting $E$ out of $B$
satisfies $\mathcal{J}=\mathcal{I}^{n}$ for some locally principal sheaf of
ideals $\mathcal{I}$ on $B$ and integer $n\geq 2$. Let $\mathcal{I}^{\prime}$
and $\mathcal{J}^{\prime}$ denote the pull-back of $\mathcal{I}$ and
$\mathcal{J}$, respectively, to $B^{\prime}$. Since the square above is
cartesian, $\mathcal{J}^{\prime}$ coincides with the ideal cutting out
$E^{\prime}$ from $B^{\prime}$ and hence it is locally generated by a non-
zero-divisor. Since $\mathcal{J}=\mathcal{I}^{n}$, we have
$\mathcal{J}^{\prime}=(\mathcal{I}^{\prime})^{n}$, and since $\mathcal{I}$ is
locally principal, so is $\mathcal{I}^{\prime}$. Thus, all the assumptions are
valid for $R^{\prime}$, as desired. ∎

Here is one source of rings satisfying the hypotheses of the preceding result.

### Section rings

The section ring of a line bundle $\mathcal{L}$ over a scheme $V$ is:

$\operatorname{S}(V,\mathcal{L})\coloneqq\bigoplus_{j\geqslant
0}\Gamma(V,\mathcal{L}^{j})\,.$

When $k$ is a field, $V$ is a proper $k$-scheme, and $\mathcal{L}$ is ample,
$\operatorname{S}(V,\mathcal{L})$ is a finitely generated graded $k$-algebra.

######  Corollary 3.2.

Let $V$ be a projective $k$-scheme with $\dim V\geq 1$, let $\mathcal{L}$ be
an ample line bundle on $V$, and $S=\operatorname{S}(V,\mathcal{L})$ the
section ring of $\mathcal{L}$. Suppose there is an integer $a\geq 2$ so that
the following conditions hold:

  1. (1)

$S_{0}=k$ and $S_{j}=0$ for $1\leq j\leq a-1$;

  2. (2)

the multiplication map $S_{a}\otimes_{k}S_{j}\to S_{a+j}$ is surjective for
all $j\geq a$.

Then for $\mathfrak{m}=S_{\geqslant 1}$, neither the local ring
$S_{\mathfrak{m}}$ nor its $\mathfrak{m}$-adic completion admits an Ulrich
module.

###### Proof.

We claim that as schemes over $\operatorname{Spec}S$ one has

$\operatorname{Bl}_{\mathfrak{m}}(S)\cong\operatorname{\mathbf{Spec}}_{V}(\mathrm{Sym}(\mathcal{L}))\quad\text{where
$\mathrm{Sym}(\mathcal{L})$ is the sheaf of algebras $\bigoplus_{i\geqslant
0}\mathcal{L}^{i}$.}$

To verify this, we first verify by an induction on $j$ that
$\mathfrak{m}^{j}=S_{\geqslant ja}$ for all $j\geq 0$.

The base case $j=1$ is clear. Assuming the desired equality holds for some
$j\geq 1$, one gets equalities

$\mathfrak{m}^{j+1}=\mathfrak{m}\mathfrak{m}^{j}=S_{\geqslant a}\cdot
S_{\geqslant aj}=S_{\geqslant(j+1)a}$

where the second one is by the induction hypothesis, and the last one is
immediate from condition (2) in the statement.

The equality $\mathfrak{m}^{j}=S_{\geqslant ja}$ justifies the first
isomorphism below:

$\displaystyle\operatorname{Bl}_{\mathfrak{m}}(S)\cong\operatorname{Proj}\big{(}\bigoplus_{j\geqslant
0}S_{\geqslant
ja}t^{j}\big{)}\cong\operatorname{Proj}\big{(}\bigoplus_{j\geqslant
0}S_{\geqslant
j}t^{j}\big{)}\cong\operatorname{\mathbf{Spec}}_{V}(\mathrm{Sym}(\mathcal{L}))\,,$

The second one holds as $\oplus_{j\geqslant 0}S_{\geqslant ja}t^{j}$ is the
$a$-th Veronese subring of $\oplus_{j\geqslant 0}S_{\geqslant j}t^{j}$, and
the last isomorphism holds because $\mathcal{L}$ is ample; see [7, Section
8.7.3] or [11, Paragraph 6.2.1]. These isomorphisms are compatible with
projections to $\operatorname{Spec}S$.

This justifies the claim about the blowup.

The exceptional fiber $E$ of the blowup
$\operatorname{Bl}_{\mathfrak{m}}(S)\to\operatorname{Spec}S$ is the subscheme
of $\operatorname{Bl}_{\mathfrak{m}}(S)$ cut out by $\mathcal{L}^{a}$, that is
to say that

$E\cong\operatorname{\mathbf{Spec}}\left(\frac{\mathrm{Sym}(\mathcal{L})}{\mathcal{L}^{a}\,\mathrm{Sym}(\mathcal{L})}\right)\,.$

As $V$ is the subscheme of $\operatorname{Bl}_{\mathfrak{m}}(S)$ cut out by
$\mathcal{L}$ and $a\geq 2$, we can apply Theorem 3.1 to get the desired
result. ∎

######  Remark 3.3.

Conditions (1) and (2) imply that $S$ is generated as a $k$-algebra by its
components in degrees $[a,2a-1]$. However the latter condition is weaker: the
$k$-algebra $k[x,y]$ with $|x|=2$ and $|y|=3$ is generated by its components
in degrees $[2,3]$, but the map $S_{2}\otimes_{k}S_{4}\to S_{6}$ is not
surjective for $y^{2}$ is not in the image.

Corollary 3.2 brings up the question: When is a noetherian graded ring over a
field the section ring of an ample line bundle on a projective scheme? Here is
one answer; it is extrapolates from [11, Proposition 2.1], where the result is
stated for normal domains. The argument does not require these conditions, and
we sketch a proof, to convince ourselves.

######  Lemma 3.4.

Let $k$ be a field and $S$ a noetherian $\mathbb{N}$-graded $k$-algebra with
$S_{0}=k$ and $0ptS\geq 2$. Then $S$ is the section ring of an ample line
bundle on a projective scheme over $k$ if and only if there exist homogeneous
elements $x_{0},\dots,x_{d}$ in $S$ such that
$\sqrt{(x_{0},\dots,x_{d})}=S_{\geqslant 1}$ and the $\mathbb{Z}$-graded rings
$S_{x_{i}}$ has a unit of degree $1$.

###### Proof.

Suppose $S=\operatorname{S}(X,\mathcal{L})$. Choose an integer $m\gg 0$ such
that $\mathcal{L}^{m}$ and $\mathcal{L}^{m+1}$ are very ample (see [9, Theorem
II, 7.6] and [14, Theorem 1.2.6]) and let $s_{1},\dots,s_{r}$ and
$t_{1},\dots,t_{l}$ be bases of $\Gamma(X,\mathcal{L}^{m})$ and
$\Gamma(X,\mathcal{L}^{m+1})$, respectively. One can check that the radical of
the ideal generated by $x_{ij}=s_{i}t_{j}$, for $1\leq i\leq r$ and $1\leq
j\leq l$, is $S_{\geqslant 1}$ and that $t_{j}^{2}/x_{ij}$ in $S_{x_{ij}}$ is
a unit of degree 1.

For the converse, by computing global sections using Čech cover associated to
the sequence $\boldsymbol{x}=(x_{0},\dots,x_{d})$, one gets an exact sequence

$0\longrightarrow\operatorname{H}_{\mathfrak{m}}^{0}(S)\longrightarrow
S\xrightarrow{\ \sigma\ }\bigoplus_{j\geqslant
0}\operatorname{H}^{0}(\operatorname{Proj}S;\widetilde{S(j)})\longrightarrow\operatorname{H}_{\mathfrak{m}}^{1}(S)_{j\geqslant
0}\longrightarrow 0\,,$

where $\mathfrak{m}\coloneqq S_{\geqslant 1}$, the homogeneous maximal ideal
of $S$. Since $0ptS\geq 2$, we deduce that the map $\sigma$, which is a map of
graded $k$-algebras, is an isomorphism. The hypothesis on $\boldsymbol{x}$
translates to the existence of an open cover

$\operatorname{Proj}S=D(x_{0})\cup\cdots\cup D(x_{d})$

such that one has an isomorphism of $\mathbb{Z}$-graded rings
$S_{x_{i}}\cong[S_{x_{i}}]_{0}[t^{\pm 1}]$, where $|t|=1$. Using this it is
easy to check that the natural map

$\widetilde{S(i)}\otimes\widetilde{S(j)}\longrightarrow\widetilde{S(i+j)}$

is an isomorphism for all integers $i,j$. Hence
$\mathcal{L}\coloneqq\widetilde{S(1)}$ is invertible and
$\widetilde{S(j)}\cong\mathcal{L}^{j}$. It follows that $S$ is the section
ring of the ample line bundle $\mathcal{L}$ on $\operatorname{Proj}S$. ∎

Here is another special case of Theorem 3.1.

######  Corollary 3.5.

Let $(R,\mathfrak{m},k)$ be a noetherian local ring such that $\dim R\geq 2$.
Let $\operatorname{Bl}_{\mathfrak{m}}(R)\to\operatorname{Spec}R$ be the blowup
of $\\{\mathfrak{m}\\}$ and $E$ the exceptional fiber of the blowup. If
$\operatorname{Bl}_{\mathfrak{m}}(R)$ is locally factorial (for instance,
regular) and $E$ is irreducible but not reduced, then $R$ has no Ulrich
modules.

###### Proof.

Set $W\coloneqq E_{\mathrm{red}}$. The hypothesis implies that it is an
integral scheme and hence an integral Weil divisor on
$\operatorname{Bl}_{\mathfrak{m}}(R)$. Since
$\operatorname{Bl}_{\mathfrak{m}}(R)$ is locally factorial, we know that $W$
is a Cartier divisor and $[E]=n[W]$ for some $n\geq 2$, since $E$ is not
reduced. Thus Theorem 3.1 applies. ∎

Our interest in the formulation above is that it applies also when $R$ is not
itself a section ring. To illustrate this, we revisit the example constructed
by Yhee [21].

### Yhee’s example revisited

Let $k$ be a field, $S=k[\boldsymbol{x}]$ the polynomial ring over $k$ in
indeterminates $\boldsymbol{x}=x_{1},\dots,x_{d}$, and set
$\mathfrak{m}=(\boldsymbol{x})$. Fix an integer $n\geq 2$, set
$J=\mathfrak{m}^{n}$ and $R=k\oplus J$, viewed as a subring of $S$. Then $R$
cannot be a section ring, for it is not $S_{2}$.

We claim that the ring $R$ satisfies the hypothesis of Corollary 3.5.

Indeed, the cokernel of the inclusion
$\mathscr{R}_{J}(R)\subseteq\mathscr{R}_{J}(S)$ is $S/R$, and in particular
finite dimensional as a $k$-vector space. Thus one gets the first isomorphism
below:

$\operatorname{Bl}_{J}(R)\xleftarrow{\ \cong\
}\operatorname{Bl}_{J}(S)\cong\operatorname{Bl}_{\mathfrak{m}}(S)\cong\mathbb{P}^{d-1}_{S}\,.$

The second isomorphism holds as $\mathscr{R}_{J}(S)$ is the $n$th Veronese
subring of $\mathscr{R}_{\mathfrak{m}}(S)$; this holds because
$J=\mathfrak{m}^{n}$. In particular $\operatorname{Bl}_{J}(R)$ is regular. The
exceptional fiber of the blowup is
$E=\operatorname{Proj}(\operatorname{gr}_{J}(R))$ where

$\operatorname{gr}_{J}(R)=k\oplus\frac{\mathfrak{m}^{n}}{\mathfrak{m}^{2n}}\oplus\frac{\mathfrak{m}^{2n}}{\mathfrak{m}^{3n}}\oplus\cdots.$

Observe that the ideal sheaf, say $\mathcal{I}$, corresponding to
$\mathfrak{m}^{n+1}\operatorname{gr}_{J}(R)$ is nilpotent, of order $n$, and
nonzero; the latter holds because $n\geq 2$. So $E$ is not reduced. It is
irreducible because $E/\mathcal{I}$ is the projective scheme associated to the
$k$-algebra

$k\oplus\bigoplus_{i\geqslant
1}\frac{\mathfrak{m}^{ni}}{\mathfrak{m}^{ni+1}},$

which is isomorphic to the $n$th Veronese subring of $S$, so
$E/\mathcal{I}\cong\mathbb{P}^{d-1}_{k}$.

##  4\. Examples: Complete intersections

In this section we construct complete intersection local rings, some of which
are domains, that have no Ulrich modules. Let $k$ be a field and consider the
$k$-algebra

$S\coloneqq\frac{k[s,t,x,y,z]}{(s^{2}-x^{3},st-f(x,y,z),t^{2}-z^{3})}$

where $f(x,y,z)$ is a homogeneous polynomial in $k[x,y,z]$ of the form

$f(x,y,z)=y^{3}+f_{2}(x,z)y^{2}+f_{1}(x,z)y+f_{0}(x,z)$

where each $f_{i}(x,z)$ is in $k[x,z]$. Set the degree of $x,y,z$ to $2$ and
that of $s,t$ to $3$. Then $S$ is an $\mathbb{N}$-graded ring, with
homogeneous maximal ideal $\mathfrak{m}\coloneqq S_{\geqslant 2}$.

######  Theorem 4.1.

For any choice of $f(x,y,z)$ satisfying the condition above neither the local
ring $S_{\mathfrak{m}}$ nor its $\mathfrak{m}$-adic completion has an Ulrich
module. They are both complete intersections of dimension $2$.

###### Proof.

It suffices to verify that the graded $k$-algebra $S$ has the following
properties:

  1. (a)

It is a complete intersection ring, with $\dim S=2$;

  2. (b)

It satisfies the conditions (1) and (2) of Corollary 3.2, with $a=2$;

  3. (c)

It is the section ring of an ample line bundle on a projective curve.

Then Corollary 3.2 yields the desired conclusion.

Proof of (a): It is clear that $\operatorname{gr}_{\mathfrak{m}}(S)$ is a
quotient of the ring

$\frac{k[s,t,x,y,z]}{(s^{2},st,t^{2},x^{3}z^{3}-f(x,y,z)^{2})}\,.$

Since $f(x,y,z)$ is monic in $y$ we get that $\dim S\leq 2$. On the other
hand, $S$ is defined by three relations, so it must be a complete intersection
ring, with $\dim S=2$.

Proof of (b): Evidently $S_{0}=k$ and $S_{1}=0$. Let $R$ be the second
Veronese subring of $S$. It is clear from the relations defining $S$ that $R$
is the $k$-sub-algebra of $S$ generated by $x,y,z$. As an $R$-module, $S$ is
generated by $1,s,t$. It follows that $S_{2}\cdot S_{j}=S_{j+2}$ for $j\geq
2$.

Proof of (c): We use the criterion from Lemma 3.4. The elements $x,z$ form a
homogeneous system of parameters for $S$. The element $s/x$ is of degree $1$
in $S_{x}$, and invertible, with inverse $s/x^{2}$. By symmetry, $t/z$ is a
unit of degree $1$ in $S_{z}$.

This completes the proof of the theorem. ∎

The preceding theorem provides a family of complete intersections with no
Ulrich modules. Special values of $f(x,y,z)$ yield rings with further
interesting properties.

### The case $f(x,y,z)=y^{3}+x^{2}z$

Then the ring in question is a domain

$S\coloneqq\frac{k[s,t,x,y,z]}{(s^{2}-x^{3},st-(y^{3}+x^{2}z),t^{2}-z^{3})}.$

For $k=\mathbb{Q}$, this claim can be verified using, for instance, Macaulay2.
Here is a sketch of an argument for general $k$: Since $x$ is a parameter in
$S$, it is not a zero-divisor, so it suffices to check that the ring
$S[x^{-1}]$ is a domain. One has

$S[x^{-1}]=\frac{A[x^{-1},s]}{(s^{2}-x^{3})}\quad\text{where}\quad
A=\frac{k[x,y,z]}{((y^{3}+x^{2}z)^{2}-x^{3}z^{3})}$

It thus suffices to verify that $A$ is a domain and $x^{3}$ does not have a
square-root in the fraction field of $A$.

The property that $A$ is a domain translates to the irreducibility of the
polynomial $(y^{3}-x^{2}z)^{2}-x^{3}z^{3}$. Specializing $y=1$, it suffices to
verify that the polynomial

$x^{4}z^{2}-x^{3}z^{3}-2x^{2}z+1$

is irreducible. This can be done easily using the Newton polytope associated
to this polynomial, as described in Gao [5]: The polytope is a triangle with
vertices

$v_{0}=(0,0),v_{1}=(3,3),v_{2}=(4,2).$

The greatest common divisor of the coordinates of $v_{0}-v_{1}$ and
$v_{0}-v_{2}$ is $1$, so the polytope is integrally indecomposable, by [5,
Corollary 4.5]. We conclude that polynomial in question is irreducible; see
[5, p. 507].

Finally, if $x^{3}$ has a square-root in the fraction field of $A$, then so is
$x$. Thus there exist nonzero elements $a,b\in A$ such that $a^{2}x=b^{2}$.
Since $A$ can be standard graded, with degrees of $x,y,z$ equal to $1$, this
is not possible since the highest degree term in $a^{2}x$ has odd degree while
the highest degree term in $b^{2}$ has even degree.

### The case $f(x,y,z)=y^{3}$ and $k$ is algebraically closed

The complete intersection in question is then

$S\coloneqq\frac{k[s,t,x,y,z]}{(s^{2}-x^{3},st-y^{3},t^{2}-z^{3})}$

and this is interesting, for it is closely connected to Yhee’s construction
[21] of domains (not Cohen-Macaulay) that have no Ulrich modules.

Indeed, according to Macaulay2, the ring $S$ has three minimal prime ideals.
Evidently, for any of minimal prime $\mathfrak{p}$ the domain $S/\mathfrak{p}$
(or rather it localization at the maximal ideal) cannot have Ulrich modules,
for any Ulrich module over it would be Ulrich over $S_{\mathfrak{m}}$. Again
according to Macaulay2, one of the prime ideals is

$\mathfrak{p}=(s^{2}-x^{3},st-xyz,z^{3}-t^{2},y^{2}-xz,sz^{2}-xyt,yzs-x^{2}t)$

as an ideal in the underlying polynomial ring. The assignment

$s\mapsto u^{3},t\mapsto v^{3},x\mapsto u^{2},y\mapsto uv,z\mapsto v^{2}$

induces an isomorphism of $k$-algebras

$S/\mathfrak{p}\cong k[u^{2},uv,v^{2},u^{3},v^{3}]\subset k[u,v].$

This subring on the right differ from the subring $k+(u,v)^{2}$ considered in
[21], as discussed in the previous section, only in containing
$u^{2}v,uv^{2}$, and one can argue as in [21] to deduce that $S/\mathfrak{p}$
does not have Ulrich modules.

The same analysis carries over to the quotient of $S$ by the other minimal
primes. Summing up, the complete intersection ring $S$ above can be thought of
being obtained by gluing three copies of the (non Cohen-Macaulay) ring
constructed by Yhee in [21], as discussed in the previous section.

######  Remark 4.2.

More generally, consider the $k$-algebra

$S\coloneqq\frac{k[s_{1},\dots,s_{n},x_{ij}\mid 1\leq i\leq j\leq
n]}{(s_{i}s_{j}-x_{ij}^{3}\mid 1\leq i\leq j\leq n)}\,.$

Then $S_{\mathfrak{m}}$ is a complete intersection of dimension $n$, and an
argument similar to the proof of Theorem 4.1 shows that $S_{\mathfrak{m}}$
does not admit Ulrich modules. Moreover the ideal $(x_{11},\dots,x_{nn})$ is a
minimal reduction of $\mathfrak{m}$; it is easy to check the other variables
are integral over this ideal. Thus

$\displaystyle e(S_{\mathfrak{m}})$
$\displaystyle=\operatorname{length}\left(\frac{S}{(x_{11},\dots,x_{nn})}\right)$
$\displaystyle=\operatorname{length}\left(\frac{k[s_{1},\dots,s_{n},x_{ij}\mid
1\leq i<j\leq n]}{(s_{1}^{2},\dots,s_{n}^{2},s_{i}s_{j}-x_{ij}^{3}\mid 1\leq
i<j\leq n)}\right)$ $\displaystyle=2^{n}\cdot 3^{\binom{n}{2}}.$

where the last equality follows because the ring in question is a finite free
extension of $k[s_{1},\dots,s_{n}]/(s_{1}^{2},\dots,s_{n}^{2})$ of degree
$3^{\binom{n}{2}}$. Note that $S_{\mathfrak{m}}$ is far from a strict complete
intersection, as the product of the $\mathfrak{m}$-adic orders of the defining
equations is $2^{\binom{n+1}{2}}$.

One thus gets a family of complete intersections with no Ulrich modules, and
for which the difference between the orderand its multiplicity is arbitrarily
large.

##  5\. Examples: Gorenstein normal domains

In this section we construct Gorenstein normal domains with no Ulrich modules.

Let $C$ be a smooth non-hyperelliptic curve of genus $g\geq 3$ (e.g. a smooth
plane quartic), and let $\mathcal{L}$ be a non-effective theta characteristic
on $C$. In other words,

$\mathcal{L}^{\otimes
2}\cong\omega_{C}\quad\text{and}\quad\Gamma^{0}(C,\mathcal{L})=0\,.$

It is a classical result [16] (see also [1]) that non-effective theta
characteristic exists on any smooth curve. For example, one can take

$C=\operatorname{Proj}\frac{\mathbb{C}[x,y,z]}{(x^{4}+y^{4}+z^{4})}\,.$

There is an ample line bundle $\mathcal{L}$ on $C$ such that
$\mathcal{L}^{2}=\omega_{C}$ and $\Gamma(C,\mathcal{L})=0$. In fact, for any
plane quartic, there are $2^{2g}=64$ theta characteristics, but only $28$ of
them are effective (corresponding to the $28$ bitangents); see [9, Exercise
IV, 2.3(h)].

######  Theorem 5.1.

Set $S\coloneqq\operatorname{S}(C,\mathcal{L})$ and let $\mathfrak{m}$ be the
homogeneous maximal ideal of $S$. Then neither the local ring
$S_{\mathfrak{m}}$ nor its completion at $\mathfrak{m}$ admits an Ulrich
module. They are both Gorenstein and normal.

###### Proof.

To begin with $S$ is normal because it is the section ring of smooth
projective variety, with respect to an ample invertible sheaf; see [18,
Section 1]. It is also Gorenstein by [13, Proposition 3.14(4)]. These
conditions are then inherited by $S_{\mathfrak{m}}$ and its completion. For
the rest, we show that the conditions in Corollary 3.2 are satisfied with
$a=2$.

Indeed, since $C$ is not hyperelliptic, the canonical ring
$\operatorname{S}(\omega_{C})$ is generated in degree 1 by a classical theorem
of Max Noether. As $\mathcal{L}^{\otimes 2}\cong\omega_{C}$, we deduce that
the multiplication map $\mathrm{Sym}^{m}(S_{2})\to S_{2m}$ is surjective for
all integer $m$, hence $S_{2}\otimes_{k}S_{j}\to S_{2+j}$ is also surjective
for all even integer $j\geq 2$. On the other hand, the line bundle
$\mathcal{L}^{\otimes 3}$ on $C$ is Castelnuovo-Mumford $0$-regular (with
respect to the very ample line bundle $\omega_{C}$). To see this, it suffices
to note that $\chi(\mathcal{L})=0$ by Riemann-Roch, and hence

$\operatorname{H}^{1}(C,\mathcal{L}^{\otimes
3}\otimes\omega_{C}^{-1})=\operatorname{H}^{1}(C,\mathcal{L})=\operatorname{H}^{0}(C,\mathcal{L})=0\,.$

By [14, Theorem 1.8.3], it follows that the multiplication map
$S_{3}\otimes\mathrm{Sym}^{m}(S_{2})\to S_{2m+3}$ is also surjective for all
integer $m$, which in turn implies the surjectivity of
$S_{2}\otimes_{k}S_{j}\to S_{2+j}$ for all odd integer $j\geq 3$. This
verifies the condition (2) from Corollary 3.2, while condition (1) is clear
from the choice of $\mathcal{L}$. ∎

######  Remark 5.2.

With $g$ the genus of the curve $C$, a direct computation gives that the
Hilbert series of the ring $S$ in Theorem 5.1 is

$\frac{(1-2t+(g+1)t^{2}-2t^{3}+t^{4})}{(1-t)^{2}}$

If $S$ were a complete intersection, the numerator would be product of
cyclotomic polynomials. One can check that this is not the case.

######  Remark 5.3.

The ring $S_{\mathfrak{m}}$ in Theorem 5.1 is not a rational singularity. In
fact, rational surface singularities have minimal multiplicities (that is to
say, the multiplicity is one less than the embedding dimension, see [17,
Theorem on page 94]), and such rings admit Ulrich modules, see [2, Proposition
2.5]. It is an interesting question to find an example of a rational
singularity with no Ulrich modules.

######  Acknowledgements.

Many thanks to Kevin Tucker for helpful conversations concerning this work.
The authors were partly supported by National Science Foundation (NSF) grants
DMS-2001368 (SBI); DMS-2302430 (LM); DMS-1952366 (LM); DMS-2200732 (MW);
DMS-2240926 (ZZ), and DMS-2234736 (ZZ). Ma was also partly supported by a
fellowship from the Sloan Foundation and by a grant from the Institute for
Advanced Study School of Mathematics. Zhuang was also partly supported by a
Clay research fellowship, as well as a Sloan fellowship.

This material is based upon work supported by the NSF under Grant No.
DMS-1928930 and by the Alfred P. Sloan Foundation under grant G-2021-16778,
while the first three authors were in residence at the Simons Laufer
Mathematical Sciences Institute (formerly MSRI) in Berkeley, California,
during the Spring 2024 semester.

## References

  * [1] Robert Auffarth, Gian Pietro Pirola, and Riccardo Salvati Manni, _Torsion points on theta divisors_ , Proc. Amer. Math. Soc. 145 (2017), no. 1, 89–99. MR 3565362
  * [2] Joseph P. Brennan, Jürgen Herzog, and Bernd Ulrich, _Maximally generated Cohen-Macaulay modules_ , Math. Scand. 61 (1987), no. 2, 181–203. MR 947472
  * [3] Emre Coskun, _A survey of Ulrich bundles_ , Analytic and algebraic geometry, Hindustan Book Agency, New Delhi, 2017, pp. 85–106. MR 3728127
  * [4] David Eisenbud and Frank-Olaf Schreyer, _Resultants and Chow forms via exterior syzygies_ , J. Amer. Math. Soc. 16 (2003), no. 3, 537–579, With an appendix by Jerzy Weyman. MR 1969204
  * [5] Shuhong Gao, _Absolute irreducibility of polynomials via Newton polytopes_ , J. Algebra 237 (2001), no. 2, 501–520. MR 1816701
  * [6] Ulrich Görtz and Torsten Wedhorn, _Algebraic geometry I_ , Advanced Lectures in Mathematics, Vieweg + Teubner, Wiesbaden, 2010, Schemes with examples and exercises. MR 2675155
  * [7] A. Grothendieck, _Éléments de géométrie algébrique. II. Étude globale élémentaire de quelques classes de morphismes._ , Inst. Hautes Études Sci. Publ. Math. (1961), no. 8, 222. MR 217084
  * [8] Douglas Allen Hanes, _Special conditions on maximal Cohen-Macaulay modules, and applications to the theory of multiplicities_ , ProQuest LLC, Ann Arbor, MI, 1999, Thesis (Ph.D.)–University of Michigan. MR 2699070
  * [9] Robin Hartshorne, _Algebraic geometry_ , Graduate Texts in Mathematics, vol. No. 52, Springer-Verlag, New York-Heidelberg, 1977. MR 463157
  * [10] J. Herzog, B. Ulrich, and J. Backelin, _Linear maximal Cohen-Macaulay modules over strict complete intersections_ , J. Pure Appl. Algebra 71 (1991), no. 2-3, 187–202. MR 1117634
  * [11] Eero Hyry and Karen E. Smith, _On a non-vanishing conjecture of Kawamata and the core of an ideal_ , Amer. J. Math. 125 (2003), no. 6, 1349–1410. MR 2018664
  * [12] Srikanth B. Iyengar, Linquan Ma, and Mark E. Walker, _Multiplicities and Betti numbers in local algebra via lim Ulrich points_ , Algebra Number Theory 16 (2022), no. 5, 1213–1257. MR 4471041
  * [13] János Kollár, _Singularities of the minimal model program_ , Cambridge Tracts in Mathematics, vol. 200, Cambridge University Press, Cambridge, 2013, With a collaboration of Sándor Kovács.
  * [14] Robert Lazarsfeld, _Positivity in algebraic geometry. I_ , Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics [Results in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics], vol. 48, Springer-Verlag, Berlin, 2004, Classical setting: line bundles and linear series. MR 2095471
  * [15] Linquan Ma, _Lim Ulrich sequences and Lech’s conjecture_ , Invent. Math. 231 (2023), no. 1, 407–429. MR 4526825
  * [16] D. Mumford, _On the equations defining abelian varieties. I_ , Invent. Math. 1 (1966), 287–354. MR 204427
  * [17] Miles Reid, _Chapters on algebraic surfaces_ , Complex algebraic geometry (Park City, UT, 1993), IAS/Park City Math. Ser., vol. 3, Amer. Math. Soc., Providence, RI, 1997, pp. 3–159. MR 1442522
  * [18] Karen E. Smith, _Fujita’s freeness conjecture in terms of local cohomology_ , J. Algebraic Geom. 6 (1997), no. 3, 417–429. MR 1487221
  * [19] The Stacks project authors, _The stacks project_ , https://stacks.math.columbia.edu, 2024.
  * [20] Bernd Ulrich, _Gorenstein rings and modules with high numbers of generators_ , Math. Z. 188 (1984), no. 1, 23–32. MR 767359
  * [21] Farrah C. Yhee, _Ulrich modules and weakly lim Ulrich sequences do not always exist_ , Forum Math. Sigma 11 (2023), Paper No. e71, 14. MR 4627095


77institutetext: Department of Quantitative Biomedicine, University of Zurich,
Switzerland 22institutetext: International School of Medicine, Istanbul
Medipol University, Turkey 33institutetext: Department of Computer Science,
ETH Zurich, Switzerland 44institutetext: Department of Computer Engineering,
Bogazici University, Turkey 55institutetext: Department of Endodontics,
Istanbul Medipol University, Turkey 66institutetext: Perelman School of
Medicine, University of Pennsylvania, USA 77institutetext: Center of Dental
Medicine, University of Zurich, Switzerland

* Corresponding author: 77email<EMAIL_ADDRESS>
# DENTEX: An Abnormal Tooth Detection with Dental Enumeration and Diagnosis
Benchmark for Panoramic X-rays

Ibrahim Ethem Hamamci 1 *1 * Sezgin Er 22 Enis Simsar 33 Atif Emre Yuksel 44
Sadullah Gultekin 44 Serife Damla Ozdemir 55 Kaiyuan Yang 11 Hongwei Bran Li
11 Sarthak Pati 66 Bernd Stadlinger 77 Albert Mehl 77 Mustafa Gundogar 55
Bjoern Menze 11

###### Abstract

Panoramic X-rays are frequently used in dentistry for treatment planning, but
their interpretation can be both time-consuming and prone to error. Artificial
intelligence (AI) has the potential to aid in the analysis of these X-rays,
thereby improving the accuracy of dental diagnoses and treatment plans.
Nevertheless, designing automated algorithms for this purpose poses
significant challenges, mainly due to the scarcity of annotated data and
variations in anatomical structure. To address these issues, the Dental
Enumeration and Diagnosis on Panoramic X-rays Challenge (DENTEX) has been
organized in association with the International Conference on Medical Image
Computing and Computer-Assisted Intervention (MICCAI) in 2023. This challenge
aims to promote the development of algorithms for multi-label detection of
abnormal teeth, using three types of hierarchically annotated data: partially
annotated quadrant data, partially annotated quadrant-enumeration data, and
fully annotated quadrant-enumeration-diagnosis data, inclusive of four
different diagnoses. In this paper, we present the results of evaluating
participant algorithms on the fully annotated data, additionally investigating
performance variation for quadrant, enumeration, and diagnosis labels in the
detection of abnormal teeth. The provision of this annotated dataset,
alongside the results of this challenge, may lay the groundwork for the
creation of AI-powered tools that can offer more precise and efficient
diagnosis and treatment planning in the field of dentistry. The evaluation
code and datasets can be accessed at
https://github.com/ibrahimethemhamamci/DENTEX.

###### Keywords:

DENTEX, challenge, tooth, dental enumeration, diagnosis, panoramic X-ray,
object detection, machine learning

##  1 Introduction

Oral health is an integral part of overall well-being, and precise diagnosis
and treatment are vital for the maintenance of healthy teeth and gums [1].
Panoramic X-rays are extensively used in dentistry to provide an inclusive
view of the oral cavity, thus aiding in treatment planning for various dental
conditions [2]. Nonetheless, interpreting these images can be a laborious
task, often diverting clinicians from vital clinical activities [3].
Furthermore, the risk of misdiagnosis is substantial as general practitioners
might lack specialized training in radiology, and communication errors due to
work exhaustion can exacerbate this [4].

Recent advancements in artificial intelligence (AI) have opened the door to
automated dental radiology analysis [5]. Yet, creating automated algorithms
for panoramic X-ray analysis is challenging due to anatomical variations [6]
and the shortage of publicly accessible annotated data [7]. Despite these
hurdles, the potential benefits of incorporating AI in dental radiology
analysis are substantial, promising improved treatment outcomes and patient
satisfaction [8]. As a result, there is an escalating demand for research in
this area to explore and develop effective AI algorithms for dental radiology
analysis.

To address this gap, we introduce the Dental Enumeration and Diagnosis on
Panoramic X-rays Challenge (DENTEX) held in collaboration with the
International Conference on Medical Image Computing and Computer-Assisted
Intervention (MICCAI) in 2023. The primary objective of this challenge is to
facilitate the development and evaluation of algorithms capable of detecting
abnormal teeth accurately, including dental enumeration and associated
diagnosis. This not only aids precise treatment planning but also enables
practitioners to perform procedures with minimal errors [9].

This challenge presents three categories of hierarchically annotated data
along with supplemental unlabeled X-rays for potential pre-training, all
annotated according to the Fédération Dentaire Internationale (FDI) system
[10], as illustrated in Fig.1. The first dataset, partially labeled,
encompasses anatomical quadrants. The second, also partially labeled, extends
this to include the enumeration and localization of all visible teeth. The
third dataset, fully labeled, provides a comprehensive perspective, detailing
quadrants, enumerations, and diagnoses for each abnormal tooth, thereby
defining the localization and classification tasks of the benchmark.
Ultimately, the data—divided into these three subsets—directs the development
of participant algorithms, which will be evaluated based on their proficiency
in deciphering the complete spectrum of labels in the third dataset,
culminating in the detection of abnormal teeth marked with three labels, as
showcased in Fig.2.

In this paper, we present the results of the DENTEX evaluation and examine the
performance variation for quadrant, enumeration, and diagnosis labels in
abnormal tooth detection. Our challenge aims to provide insights into the
efficacy of AI in dental radiology and its potential to enhance dental
practice.

Figure 1: The hierarchical organization of the annotated data used in the
DENTEX. The data is structured into three levels: (a) quadrant-only for
quadrant detection, (b) quadrant-enumeration for tooth detection, and (c)
quadrant-enumeration-diagnosis for abnormal tooth detection.

##  2 Materials & Methods

###  2.1 Data

The DENTEX dataset includes panoramic dental X-rays acquired from three
distinct institutions. These images were captured under standard clinical
conditions, yet they vary in terms of equipment used and imaging protocols
followed. This leads to a diversity in image quality, reflecting the
heterogeneity of clinical practice. The X-rays are taken from patients aged 12
years and above, randomly chosen from the hospital’s database to preserve
patient privacy and confidentiality.

The dataset is structured hierarchically to facilitate the effective use of
the FDI system. As shown in Fig. 1, it consists of three types of data: (a)
693 X-rays labeled only for quadrant detection, (b) 634 X-rays labeled for
tooth detection with quadrant and tooth enumeration classifications, and (c)
1005 X-rays fully labeled for abnormal tooth detection with quadrant, tooth
enumeration, and diagnosis classifications. The diagnosis class includes four
categories: caries, deep caries, periapical lesions, and impacted teeth. An
additional dataset of 1571 unlabeled X-rays is also available for pre-training
purposes. All the necessary permissions have been obtained from the ethics
committee, and the data is released publicly under a Creative Commons
Attribution (CC-BY) license.

####  2.1.1 Annotation Protocol.

DENTEX provides three hierarchically annotated datasets that facilitate
various dental detection tasks: (0) plain images without annotations for
optional pretraining, (1) quadrant-only annotations for quadrant detection,
(2) quadrant-enumeration annotations for tooth detection, and (3) quadrant-
enumeration-diagnosis annotations for abnormal tooth detection. While it may
seem redundant to provide a quadrant detection dataset, it is crucial for
utilizing the FDI Numbering System [10]. The FDI system is a globally used
system that assigns each quadrant of the mouth a number from 1 through 4: the
top right is 1, the top left is 2, the bottom left is 3, and the bottom right
is 4 [11]. Then, each tooth and molar are numbered from 1 through 8, with 1
starting at the front middle tooth and the numbers increasing as we go farther
back. For example, the back tooth on the lower left side would be 48 according
to FDI notation, signifying quadrant 4, tooth number 8. Therefore, the
quadrant segmentation dataset can significantly simplify the dental
enumeration task, even though evaluations will be made only on the fully
annotated third data.

All annotations in the DENTEX dataset are meticulously crafted by a team of
dental experts. Specifically, each image is annotated by a final-year dental
student, and these annotations are further verified and corrected by one of
three expert dentists with over 15 years of experience. As a result, the
annotated data in DENTEX is of the highest quality and accuracy, making it a
valuable resource for dental research.

####  2.1.2 Data Split for Evaluation and Training.

The DENTEX dataset consists of three types of annotated data: (1) partially
annotated quadrant data, (2) partially annotated quadrant-enumeration data,
and (3) fully annotated quadrant-enumeration-diagnosis data. The first two
data types are intended for training and development purposes, while the third
type is used for both training and evaluations.

The fully annotated third dataset, composed of 1005 panoramic X-rays, is
divided into training, validation, and testing subsets, comprising 705, 50,
and 250 images respectively, in accordance with standard machine learning
practices [12, 13]. Ground truth labels are provided only for the training
data, while the validation data is offered without associated ground truth,
and the testing data remains hidden from participants.

Participants are allowed to use additional public data for augmenting the
provided DENTEX dataset or for pre-training models on such datasets to enhance
performance. However, they must ensure that all the data they use is publicly
available. Additionally, they must document the use of external data clearly
in their final short paper submission, providing details on the dataset and
its source.

###  2.2 Performance Evaluation

Participants in the DENTEX Challenge are encouraged to submit their results on
the online evaluation platform for both the training and validation datasets.
However, the test dataset remains undisclosed to the participants. Instead,
they are required to upload their proposed methods in a containerized format
for the final testing phase. To evaluate the performance of the participating
teams, the DENTEX Challenge utilizes a comprehensive set of metrics, including
$AP_{50},AP_{75},AP,$ and $AR$ [14]. These performance evaluation metrics are
calculated based on the fully annotated testing dataset, which includes
quadrant-enumeration-diagnosis data for the quadrant, enumeration, and
diagnosis aspects of dental image analysis. This results in a total of 12
metrics, 4 for each of the three labels of abnormal teeth, used for evaluating
the performance of the participating teams.

Following the VerSe challenge [15] and the Brain Tumor Segmentation (BraTS)
challenge [16], we use a point-based ranking process. This ranking process for
the DENTEX Challenge involves comparing every possible pair of teams for each
metric using the Wilcoxon Signed Rank Test [17]. In each comparison, the team
that performs statistically better (with a p-value $<$ 0.001) earns one point.
After comparisons have been completed, each team has a total point count,
which reflects the number of times it outperformed its counterparts. To
further enhance the robustness and reliability of the ranking system,
bootstrapping techniques [18] are incorporated by resampling 10% of the data
and repeating the ranking process for the remaining x-ray images. This
generates a total point count for each team for every excluded X-ray image.
The total point counts are then combined to establish the final ranking for
the DENTEX Challenge.

The final top three ranked participating teams, according to their evaluation
on the testing data, will be invited to MICCAI 2023 to present their methods
and results and to receive their awards.

###  2.3 Participation Timeline

The challenge commences with the release of the training dataset, which
includes imaging data and the corresponding ground-truth labels. Participants
begin by designing and training their methods using this training dataset. The
validation data is released within three weeks after the training data,
allowing participants to obtain preliminary results on unseen data.
Participants can report these results in their submitted short papers, in
addition to their cross-validated results on the training data. The ground
truth of the validation data is not provided to the participants, but multiple
submissions to the online evaluation platform are permitted.

Finally, all participants will be evaluated and ranked based on the same
unseen testing data, which will not be made available to the participants.
After uploading their containerized method to the evaluation platforms, the
final top-ranked participating teams will be announced at the 2023 MICCAI
Meeting.

Figure 2: Desired output from the final model, illustrating well-defined
bounding boxes for abnormal teeth. The corresponding quadrant (Q), enumeration
(N), and diagnosis (D) labels are also displayed.

###  2.4 Baseline Method

Our baseline approach, HierarchicalDet, presents a framework for multi-label,
hierarchically labeled tooth detection [19]. This method utilizes a diffusion-
based model for hierarchical object detection, an approach that has seen
promising applications in different medical fields, such as segmentation [20],
classification [21], reconstruction [22], and image generation [23].

The baseline method comprises two primary components: an image encoder that
extracts high-level features from input images, and a detection decoder that
refines the initial noisy boxes using the features. The diffusion process in
this method is similar to the one used in DiffusionDet [24], which perceives
object detection as a denoising diffusion process that transitions from noisy
boxes to object boxes.

To enhance the performance of the baseline model, we incorporate a
hierarchical learning architecture that leverages hierarchically annotated
data and an innovative noisy box manipulation technique. This architecture
enables us to use previously inferred boxes for improved detection accuracy,
while the innovative noisy box manipulation technique promotes efficient
learning from partially annotated data.

Furthermore, our baseline method integrates multi-label object detection using
a customized Detectron2 library [25], designed to handle partial annotations.
We strategically freeze the classification heads corresponding to unlabeled
classes, exploiting all available information to bolster our model’s ability
to work with partially labeled data.

##  3 Results

This section will be written in thorough detail after the challenge.

##  4 Discussion

In this paper, we present the design of the Dental Enumeration and Diagnosis
on Panoramic X-Rays (DENTEX) Challenge, organized at MICCAI 2023.

###  4.1 Algorithm Design

In this section, we will discuss the design of the submitted approaches. This
section will be elaborated in detail following the completion of the
challenge.

###  4.2 Limitations of the Study

This study has several significant limitations worth discussing. First, the
hierarchical labeling structure of our data results in partially annotated
datasets for both the quadrant and quadrant-enumeration categories. This
partial annotation may potentially impede the performance of the algorithms by
providing limited information during the model training process.

Moreover, our dataset is limited in terms of the quantity of labeled and
unlabeled panoramic X-Rays, thereby restricting the potential for both
supervised training and self-supervised pretraining approaches. The fact that
our data originates exclusively from three institutes, instead of being
collected from a variety of cohorts, could also limit the generalizability of
our findings.

With regard to data annotation, our dataset is labeled by dentistry students,
with experienced dentists verifying these annotations. Despite the
meticulousness of this approach in an attempt to minimize labeling bias,
discrepancies may still exist due to variations in the expertise levels among
students and dentists. Such inconsistencies could negatively impact the
performance of the trained models and the reliability of the evaluation
metrics.

Lastly, it is critical to acknowledge that the Average Precision (AP) and
Average Recall (AR) metrics, widely used to evaluate object detection, have
notable limitations. These include sensitivity to class imbalance, lack of
specificity, insensitivity to false positives, challenges associated with
threshold selection, inaccuracies arising from interpolation, susceptibility
to the number of samples, limited applicability to specific tasks, and limited
interpretability. These potential issues could result in misleading
performance scores, complicating the accurate assessment of a model’s true
performance.

## Acknowledgments

We are grateful to all the data contributors, annotators, and participants for
their time and efforts.

## References

  * [1] M. S. Tonetti, P. Bottenberg, G. Conrads, P. Eickholz, P. Heasman, M.-C. Huysmans, R. López, P. Madianos, F. Müller, I. Needleman, et al., “Dental caries and periodontal diseases in the ageing population: call to action to protect and enhance oral health and well-being as an essential component of healthy ageing–consensus report of group 4 of the joint efp/orca workshop on the boundaries between caries and periodontal diseases,” Journal of clinical periodontology, vol. 44, pp. S135–S144, 2017.
  * [2] J.-J. Hwang, Y.-H. Jung, B.-H. Cho, and M.-S. Heo, “An overview of deep learning in the field of dentistry,” Imaging science in dentistry, vol. 49, no. 1, pp. 1–7, 2019.
  * [3] A. Kumar, H. S. Bhadauria, and A. Singh, “Descriptive analysis of dental x-ray images using various practical methods: A review,” PeerJ Computer Science, vol. 7, p. e620, 2021.
  * [4] M. A. Bruno, E. A. Walker, and H. H. Abujudeh, “Understanding and confronting our mistakes: the epidemiology of error in radiology and strategies for error reduction,” Radiographics, vol. 35, no. 6, pp. 1668–1676, 2015.
  * [5] S. AbuSalim, N. Zakaria, M. R. Islam, G. Kumar, N. Mokhtar, and S. J. Abdulkadir, “Analysis of deep learning techniques for dental informatics: A systematic literature review,” in Healthcare, vol. 10, p. 1892, MDPI, 2022\.
  * [6] A. E. Yüksel, S. Gültekin, E. Simsar, Ş. D. Özdemir, M. Gündoğar, S. B. Tokgöz, and İ. E. Hamamcı, “Dental enumeration and multiple treatment detection on panoramic x-rays using deep learning,” Scientific reports, vol. 11, no. 1, pp. 1–10, 2021.
  * [7] N. A. El Joudi, M. B. Othmani, F. Bourzgui, O. Mahboub, and M. Lazaar, “Review of the role of artificial intelligence in dentistry: Current applications and trends,” Procedia Computer Science, vol. 210, pp. 173–180, 2022.
  * [8] R. Pauwels, “A brief introduction to concepts and applications of artificial intelligence in dental imaging,” Oral Radiology, vol. 37, no. 1, pp. 153–160, 2021.
  * [9] F. De Angelis, N. Pranno, A. Franchina, S. Di Carlo, E. Brauner, A. Ferri, G. Pellegrino, E. Grecchi, F. Goker, and L. V. Stefanelli, “Artificial intelligence: A new diagnostic software in dentistry: A preliminary performance diagnostic study,” International Journal of Environmental Research and Public Health, vol. 19, no. 3, p. 1728, 2022.
  * [10] D. V. Tuzoff, L. N. Tuzova, M. M. Bornstein, A. S. Krasnov, M. A. Kharchenko, S. I. Nikolenko, M. M. Sveshnikov, and G. B. Bednenko, “Tooth detection and numbering in panoramic radiographs using convolutional neural networks,” Dentomaxillofacial Radiology, vol. 48, no. 4, p. 20180051, 2019.
  * [11] A. J. Van Wijk and S. P. Tan, “A numeric code for identifying patterns of human tooth agenesis: a new approach,” European journal of oral sciences, vol. 114, no. 2, pp. 97–101, 2006.
  * [12] S. Yadav and S. Shukla, “Analysis of k-fold cross-validation over hold-out validation on colossal datasets for quality classification,” in 2016 IEEE 6th International conference on advanced computing (IACC), pp. 78–83, IEEE, 2016.
  * [13] S. Pati, S. P. Thakur, İ. E. Hamamcı, U. Baid, B. Baheti, M. Bhalerao, O. Güley, S. Mouchtaris, D. Lang, S. Thermos, et al., “Gandlf: the generally nuanced deep learning framework for scalable end-to-end clinical workflows,” Communications Engineering, vol. 2, no. 1, p. 23, 2023.
  * [14] J. Redmon, S. Divvala, R. Girshick, and A. Farhadi, “You only look once: Unified, real-time object detection,” in Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 779–788, 2016.
  * [15] A. Sekuboyina, M. E. Husseini, A. Bayat, M. Löffler, H. Liebl, H. Li, G. Tetteh, J. Kukačka, C. Payer, D. Štern, et al., “Verse: A vertebrae labelling and segmentation benchmark for multi-detector ct images,” Medical image analysis, vol. 73, p. 102166, 2021.
  * [16] B. H. Menze, A. Jakab, S. Bauer, J. Kalpathy-Cramer, K. Farahani, J. Kirby, Y. Burren, N. Porz, J. Slotboom, R. Wiest, et al., “The multimodal brain tumor image segmentation benchmark (brats),” IEEE transactions on medical imaging, vol. 34, no. 10, pp. 1993–2024, 2014.
  * [17] R. F. Woolson, “Wilcoxon signed-rank test,” Wiley encyclopedia of clinical trials, pp. 1–3, 2007.
  * [18] S. Abney, “Bootstrapping,” in Proceedings of the 40th annual meeting of the Association for Computational Linguistics, pp. 360–367, 2002.
  * [19] I. E. Hamamci, S. Er, E. Simsar, A. Sekuboyina, M. Gundogar, B. Stadlinger, A. Mehl, and B. Menze, “Diffusion-based hierarchical multi-label object detection to analyze panoramic dental x-rays,” arXiv preprint arXiv:2303.06500, 2023.
  * [20] B. Kim, Y. Oh, and J. C. Ye, “Diffusion adversarial representation learning for self-supervised vessel segmentation,” arXiv preprint arXiv:2209.14566, 2022.
  * [21] Y. Yang, H. Fu, A. Aviles-Rivero, C.-B. Schönlieb, and L. Zhu, “Diffmic: Dual-guidance diffusion network for medical image classification,” arXiv preprint arXiv:2303.10610, 2023.
  * [22] Z.-X. Cui, C. Cao, S. Liu, Q. Zhu, J. Cheng, H. Wang, Y. Zhu, and D. Liang, “Self-score: Self-supervised learning on score-based models for mri reconstruction,” arXiv preprint arXiv:2209.00835, 2022.
  * [23] I. E. Hamamci, S. Er, E. Simsar, A. Tezcan, A. G. Simsek, F. Almas, S. N. Esirgun, H. Reynaud, S. Pati, C. Bluethgen, et al., “Generatect: Text-guided 3d chest ct generation,” arXiv preprint arXiv:2305.16037, 2023\.
  * [24] S. Chen, P. Sun, Y. Song, and P. Luo, “Diffusiondet: Diffusion model for object detection,” arXiv preprint arXiv:2211.09788, 2022.
  * [25] Y. Wu, A. Kirillov, F. Massa, W.-Y. Lo, and R. Girshick, “Detectron2,” 2019.


P}[f(X)]-\operatorname*{\mathbb{E}}_{X\sim Q}[f(X)]|\leq\text{TV}(P,Q)$ for
every measurable function $f$ with $\|f\|_{\infty}\leq 1$, the RHS is further
upper bounded by $\text{TV}(\mathcal{Q}_{t},\mathcal{Q}_{t+1})-\eta$. The
proof of Lemma 4.8 is completed by taking the expectation over
$s_{t}\sim\mathcal{D}_{t}$.

##  Appendix F Proof of Lower Bounds (Theorem 5.1 and Theorem 5.2)

###  F.1 Proof of Theorem 5.1

This section proves the regret lower bounds for Algorithm 2 and Algorithm 3
stated in Theorem 5.1. We split the analysis into two subsections, and in each
subsection we prove a large regret both when the sample size parameter $n$ is
large and small.

####  F.1.1 Lower Bound Analysis for Algorithm 2

We shall only prove the regret lower bound $\Omega(\sqrt{dT\sigma^{-1/2}})$
under the assumption $\sigma\geq\max\\{d/|\mathcal{X}|,(d/T)^{2}\\}$, for a
smaller $\sigma$ only makes the worst-case regret larger, and the other lower
bounds follow from this case by taking $\sigma=d/|\mathcal{X}|$ and
$\sigma=(d/T)^{2}$, respectively. We split the analysis into two cases
depending on the choice of parameter $n$.

##### Case I: Large $n$.

When $n$ is large, or more specifically, when $n\geq T/\sqrt{\sigma}$,
consider the behavior of Algorithm 2 on the following instance. Consider any
domain $\mathcal{X}$ where $|\mathcal{X}|$ is an integral multiple of $d$, and
partition $\mathcal{X}=\cup_{j=1}^{d}\mathcal{X}_{j}$ into $d$ sets
$\\{\mathcal{X}_{j}\\}_{j\in[d]}$ with an equal size. Consider the following
hypothesis class:

$\displaystyle\mathcal{H}=\\{h\mathrel{\mathop{\mathchar
58\relax}}\mathcal{X}\to\\{\pm 1\\}\mid h\text{ is a constant on
}\mathcal{X}_{i},\forall i\in[d]\\}.$ (127)

Clearly $\mathcal{H}$ has VC dimension $d$. The adversary chooses a hypothesis
$h^{\star}\in\mathcal{H}$ uniformly at random, and sets $x_{t}$ to be
uniformly distributed on $\mathcal{X}$. As for the label $y_{t}$, the
adversary sets $y_{t}=h^{\star}(x_{t})$. This adversary is $1$-smooth, and the
best expert in $\mathcal{H}$ incurs a zero loss under this realizable setting.
We claim that for each of the first $\min\\{T,c\sqrt{nd}\\}$ time steps, for
an absolute constant $c>0$ sufficiently small, Algorithm 2 makes a mistake
with $\Omega(1)$ probability. Summing over these steps, the expected regret of
Algorithm 2 is then $\Omega(\min\\{T,c\sqrt{nd}\\})$, which gives Theorem 5.1
by our assumption $n\geq T/\sqrt{\sigma}$.

To prove this claim, we need the following lemma.

######  Lemma F.1 (Minimum Error on Hallucinated Samples).

For $N\sim\text{\rm Poi}(n)$ hallucinated samples
$(x_{1},y_{1}),\cdots,(x_{N},y_{N})$, if $n\geq d$, it holds that

$\displaystyle\mathbb{P}\left(\sum_{i=1}^{N}y_{i}\cdot\mathbf{1}(x_{i}\in\mathcal{X}_{j})\geq\sqrt{\frac{n}{d}}\right)=\Omega(1),\qquad\forall
j\in[d].$ (128)

###### Proof.

For $j\in[d]$, let $n_{j,+},n_{j,-}$ denote the number of hallucinate samples
$(x_{i},y_{i})$ with $x_{i}\in\mathcal{X}_{j}$ and $y_{i}=\pm 1$,
respectively. By the Poisson subsampling property, $\\{n_{j,\pm}\\}_{j\in[d]}$
are mutually independent $\text{Poi}(n/(2d))$ random variables. By definition
of $\mathcal{H}$, we have

$\displaystyle
n_{j,+}-n_{j,-}=\sum_{i=1}^{N}y_{i}\cdot\mathbf{1}(x_{i}\in\mathcal{X}_{j}).$
(129)

Consequently, the quantity of interest is $n_{j,+}-n_{j,-}$. As $n/d\geq 1$,
by the Poisson tail property, both events $n_{j,+}\geq n/(2d)+\sqrt{n/d}/2$
and $n_{j,-}\leq n/(2d)-\sqrt{n/d}/2$ happen with $\Omega(1)$ probability, and
their independence gives the claimed result. ∎

Since $(d/T)^{2}\leq\sigma\leq 1$, we have $T\geq d$ and thus $n\geq
T/\sqrt{\sigma}\geq d$, the premise of Lemma F.1 holds. Consequently, at each
time step $t\leq\min\\{T,c\sqrt{nd}\\}$ with $x_{t}\in\mathcal{X}_{j}$, with
$\Omega(1)$ probability there are at least $\sqrt{n/d}$ net positive labels in
the hallucinated samples, while the learner has only observed at most $\alpha
c\sqrt{n/d}$ labels in the history with probability at least $1-1/\alpha$, by
Markov’s inequality. By choosing constants $c>0$ small and $\alpha>0$ large,
the perturbed leader will predict $+1$ depending only on the hallucination,
and this prediction is independent of the choice of $h^{\star}$ and thus
incurs an error with probability $1/2$. This proves the claim that before time
$\min\\{T,c\sqrt{nd}\\}$, there is always $\Omega(1)$ probability of error.

##### Case II: Small $n$.

Now we turn to the scenario where $n<T/\sqrt{\sigma}$. Consider the following
learning instance: choose $\mathcal{X}_{0}\subseteq\mathcal{X}$ with
$|\mathcal{X}_{0}|=\sigma|\mathcal{X}|\geq d$, the adversary always chooses
$x_{t}\sim\mathcal{U}(\mathcal{X}_{0})$, which is $\sigma$-smooth. Assuming
that $|\mathcal{X}_{0}|$ is an integral multiple of $d$, we partition
$\mathcal{X}_{0}=\cup_{j=1}^{d}\mathcal{X}_{j}$ into $d$ subsets with equal
size. Condition on each $\mathcal{X}_{j}$, consider an alternating label
sequence:

$\displaystyle(y_{t}\mathrel{\mathop{\mathchar
58\relax}}x_{t}\in\mathcal{X}_{j})_{t=1}^{T}=(+1,-1,+1,-1,\cdots).$ (130)

The hypothesis class $\mathcal{H}$ consists of $2^{d}$ functions:

$\displaystyle\mathcal{H}=\\{h\mathrel{\mathop{\mathchar
58\relax}}\mathcal{X}\to\\{\pm 1\\}\mid h\text{ is a constant on
}\mathcal{X}_{j},\forall j\in[d],\text{ and }h(x)\equiv 1,\forall
x\in\mathcal{X}\backslash\mathcal{X}_{0}\\}.$ (131)

Clearly $\mathcal{H}$ has VC dimension $d$, and the best hypothesis in
$\mathcal{H}$ incurs a cumulative loss $T/2$.

Now we examine the performance of Algorithm 2. Let $r_{j}$ be the difference
between the number of $+1$ and $-1$ labels in the hallucinated samples with
feature in $\mathcal{X}_{j}$, similar to the proof of Lemma F.1 we have
$r_{j}=n_{j,+}-n_{j,-}$ for independent Poisson random variables
$n_{j,+},n_{j,-}\sim\text{Poi}(n\sigma/2d)$. Suppose that ties are broken by
always predicting $-1$ when calling the ERM oracle, we observe that Algorithm
2 always makes a mistake when $x\in\mathcal{X}_{j}$ and $r_{j}=0$ – this is
the same counterexample where Follow-The-Leader (FTL) makes a mistake at every
step. Moreover, when $r_{j}\neq 0$, Algorithm 2 makes $T/2$ mistakes, same as
the best expert in $\mathcal{H}$. Consequently, the expected regret of
Algorithm 2 is at least $T\cdot\mathbb{P}(r_{j}=0)$, where

$\displaystyle\mathbb{P}(r_{j}=0)$
$\displaystyle=\operatorname*{\mathbb{E}}_{N\sim\text{Poi}(n\sigma/d)}\left[\mathbb{P}\left(\text{Bin}(N,\frac{1}{2})=\frac{N}{2}\right)\right]=\operatorname*{\mathbb{E}}_{N\sim\text{Poi}(n\sigma/d)}\left[\Omega\left(\frac{\mathbf{1}(N\text{
is even})}{\sqrt{N+1}}\right)\right]$ (132)
$\displaystyle\overset{\rm(a)}{=}\Omega\left(\frac{\mathbb{P}_{N\sim\text{Poi}(n\sigma/d)}(N\text{
is
even})}{\sqrt{n\sigma/d+1}}\right)\overset{\rm(b)}{=}\Omega\left(\frac{1}{\sqrt{n\sigma/d+1}}\right)=\Omega\left(\min\left\\{1,\sqrt{\frac{d}{n\sigma}}\right\\}\right).$
(133)

In the above display, (a) follows from the conditional Jensen’s inequality,
and (b) is due to

$\displaystyle\mathbb{P}_{N\sim\text{Poi}(\lambda)}(N\text{ is
even})=\sum_{k=0}^{\infty}e^{-\lambda}\frac{\lambda^{2k}}{(2k)!}=e^{-\lambda}\cdot\frac{e^{\lambda}+e^{-\lambda}}{2}\geq\frac{1}{2}.$
(134)

This leads to the claimed regret lower bound in Theorem 5.1.

####  F.1.2 Lower Bound Analysis for Algorithm 3

Similar to the lower bound analysis for Algorithm 2, we also split into the
cases where $n$ is large and $n$ is small, respectively. Recall that for
Algorithm 3, the parameter $n$ is the number of random draws from $K$ hints at
each future time.

##### Case I: Large $n$.

We first focus on the case where $n\geq\sqrt{K}$. Consider the following
learning instance: the domain $\mathcal{X}$ is $[dK]$, and we partition
$\mathcal{X}$ into $\cup_{j=1}^{d}\mathcal{X}_{j}$ each of size $K$. At each
time, the subsets $\mathcal{X}_{j}$ are given as the hint cyclically. Consider
the same construction of $\mathcal{H}$ and the adversary in Section F.1.1,
except that each $x_{t}$ is now uniformly distributed in the $K$-hint set.

The regret analysis is essentially the same as Section F.1.1. For every $t\leq
T/2$, the learner in Algorithm 3 essentially generates $(T-t)n\geq
T\sqrt{K}/4$ uniformly random samples (with replacement) in $\mathcal{X}$. A
similar analysis to Lemma F.1 shows that for each $j\in[d]$, with $\Omega(1)$
probability there are $\Omega(\sqrt{K^{1/2}T/d})$ more $+1$ labels than $-1$
labels within $\mathcal{X}_{j}$ in the hallucinated samples. Consequently, for
$t\leq\min\\{T/2,\Omega((dT)^{1/2}K^{1/4}\\}$, two calls of the ERM oracle in
Algorithm 3 will return the same hypothesis, and the learner’s prediction is
always $+1$. Similar to Section F.1.1, these time steps lead to an
$\Omega(\min\\{T,(dT)^{1/2}K^{1/4}\\})$ regret.

##### Case II: Small $n$.

Next we turn to the case where $n<\sqrt{K}$. Again, we construct $\mathcal{X}$
to be the disjoint union of $d$ sets $\\{\mathcal{X}_{j}\\}_{j\in[d]}$ each of
size $K$, while construct $\mathcal{H}$ in a different way as follows: pick
one element $x_{j}^{\star}$ from each $\mathcal{X}_{j}$, and

$\displaystyle\mathcal{H}=\\{h\mathrel{\mathop{\mathchar
58\relax}}\mathcal{X}\to\\{\pm 1\\}\mid h(x)=1,\forall
x\notin\\{x_{1}^{\star},\cdots,x_{d}^{\star}\\}\\}.$ (135)

In other words, $\mathcal{H}$ shatters the set
$\\{x_{1}^{\star},\cdots,x_{d}^{\star}\\}$, while is always $1$ on other
inputs. Clearly the VC dimension of $\mathcal{H}$ is $d$.

The learning process is divided into $d$ epochs, each of length $T/d$. During
the $j$-th epoch, the adversary chooses $x_{t}=x_{j}^{\star}$, presents the
set $\mathcal{X}_{j}$ to the learner as the hint, and sets the following
alternating sequence of $y$:

$\displaystyle(y_{1},y_{2},y_{3},\cdots)=(+1,-1,+1,-1,\cdots).$ (136)

The best expert in $\mathcal{H}$ incurs a cumulative loss of $T/2$. For the
performance of Algorithm 3, let $r_{j}^{\star}$ be the difference between the
number of $+1$ and $-1$ labels in the hallucinated samples with input
$x_{j}^{\star}$. One can check that if $r_{j}^{\star}\neq 0$, the learner
makes half of the mistakes along the alternating sequence; if
$r_{j}^{\star}=0$, the fraction of mistakes becomes $3/4$ (Algorithm 3
cyclically predicts a wrong label and makes a random guess). Consequently, the
expected regret of Algorithm 3 is lower bounded by
$\Omega(T\cdot\mathbb{P}(r_{j}^{\star}=0))$. To compute this probability, note
that $r_{j}^{\star}=2M-N$, with $N\sim\text{Bin}(T/d,n/K)$ being the number of
observations $x_{j}^{\star}$ in the hallucinated data, and $M\mid
N\sim\text{Bin}(N,1/2)$. Using a similar argument to Section F.1.1, this
probability is lower bounded by $\Omega(\min\\{1,\sqrt{dK/(nT)}\\})$, as
desired.

###  F.2 Proof of Theorem 5.2

The proof of Theorem 5.2 uses a similar idea to [HK16]. There are two lower
bound arguments in [HK16]: one reduces the problem to the Aldous’ problem, and
the other is based on an explicit construction of the hard instance. Although
both arguments could work for our problem, we adopt the latter which
corresponds to Theorem 25 of [HK16]. In the sequel, we will always take the
domain size $|\mathcal{X}|=1/\sigma$ so that the smooth adversary becomes the
usual adaptive adversary. In the next subsections, we first prove the theorem
for the simpler case $d=1$, and then generalize our argument for any VC
dimension $d$.

####  F.2.1 The case $d=1$.

We first show how the argument in [HK16] proves the claimed
$\omega(\sqrt{|\mathcal{X}|})$ computational lower bound when
$T=\sqrt{|\mathcal{X}|}=\sqrt{1/\sigma}$. Assuming that
$N\triangleq\sqrt{|\mathcal{X}|}$ is an integer, we partition the domain
$\mathcal{X}$ into disjoint subsets $\mathcal{X}_{1},\cdots,\mathcal{X}_{N}$,
each of size $N$. For each $x\in\mathcal{X}$, we associate two independent
Rademacher variables $\varepsilon(x)$ and $\varepsilon^{\star}(x)$, and they
are mutually independent across different $x\in\mathcal{X}$. For each
$i\in[N]$, the adversary chooses
$x_{i}^{\star}\sim\mathcal{U}(\mathcal{X}_{i})$, and sets the hypothesis class
$\mathcal{H}=\\{h_{x}\\}_{x\in\mathcal{X}}$ with

$\displaystyle
h_{x}(x^{\prime})=\begin{cases}\varepsilon^{\star}(x^{\prime})&\text{if
}x=x_{i}^{\star},x^{\prime}=x_{j}^{\star},\text{ and }i\geq j,\\\
\varepsilon(x^{\prime})&\text{otherwise.}\end{cases}$ (137)

At each time $t\in[N]$, the adversary sets $x_{t}=x_{t}^{\star}$, and
$y_{t}=h_{x_{N}^{\star}}(x_{t})=\varepsilon^{\star}(x_{t}^{\star})$. Under
this setting, [HK16] proved the following lower bound.

######  Theorem F.2 (Theorem 25 of [HK16], restated).

Given access to the ERM oracle, any proper algorithm achieving an expected
regret at most $N/4$ requires $\Omega(N)=\Omega(\sqrt{|\mathcal{X}|})$ running
time.

Here by running time, we assume that each oracle call takes unit time, and
maintaining each element in the input $\\{(x_{i},y_{i})\\}_{i\in I}$ to the
oracle also takes unit time. We also sketch the proof idea of Theorem F.2 for
completeness: the crucial observation is that, when the learner feeds the
input $\\{(x_{i},y_{i})\\}_{i\in I}$ to the ERM oracle, the oracle can always
return some $h\in\\{h_{0},h_{x_{1}^{\star}},\cdots,h_{x_{j}^{\star}}\\}$,
where $h_{0}$ is any hypothesis in
$\mathcal{H}\backslash\\{h_{x_{1}^{\star}},\cdots,h_{x_{N}^{\star}}\\}$, and
$j\in[N]$ is the largest index such that $x_{j}^{\star}\in\\{x_{i}\\}_{i\in
I}$. See Lemma 27 of [HK16] for a proof. Therefore, the label
$y_{t}=\varepsilon^{\star}(x_{t}^{\star})$ at time $t$ will look random to the
learner _unless_ the learner has seen a function $h_{x_{s}^{\star}}$ for some
$s\geq t$. By the above observation, this occurs only if the learner has set
one (or more) of $\\{x_{s}^{\star}\\}_{s\geq t}$ as the input to the ERM
oracle, but this requires one to find a random element in a size-$N$ set and
thus take $\Omega(N)$ time (note that a proper algorithm only observes
$\\{x_{1}^{\star},\cdots,x_{t-1}^{\star}\\}$ at time $t$). Consequently, with
$o(N)$ running time, the learner suffers from an $\Omega(N)$ loss with high
probability, while the best expert incurs zero loss - giving the $\Omega(N)$
regret.

Since the restriction of $\mathcal{H}$ on any two elements
$\\{x,x^{\prime}\\}$ with $x<x^{\prime}$ could only be one of the three
possibilities:
$\\{(\varepsilon(x),\varepsilon(x^{\prime})),(\varepsilon^{\star}(x),\varepsilon(x^{\prime})),(\varepsilon^{\star}(x),\varepsilon^{\star}(x^{\prime}))\\}$,
the VC dimension of $\mathcal{H}$ is $1$. Therefore, Theorem F.2 gives a valid
proof of Theorem 5.2 when $d=1$ and $T=\sqrt{1/\sigma}$. For
$T<\sqrt{1/\sigma}$, the above construction still gives the $\Omega(T)$ regret
lower bound given $o(\sqrt{|\mathcal{X}|})$ computational time. For general
$T>\sqrt{1/\sigma}$, we make the following modification to the adversary:
partition the time horizon $[T]$ into $N$ intervals $T_{1},\cdots,T_{N}$, each
of length $T/N$. For each $i\in[N]$ and $t\in T_{i}$, the adversary sets
$x_{t}=x_{i}^{\star}$, and

$\displaystyle y_{t}=\begin{cases}h_{x_{N}^{\star}}(x_{t})&\text{with
probability }\frac{1}{2}+\delta,\\\ -h_{x_{N}^{\star}}(x_{t})&\text{with
probability }\frac{1}{2}-\delta.\end{cases}$ (138)

Consequently, the best expert $h_{x_{N}^{\star}}$ incurs an expected
cumulative loss $(1/2-\delta)T$. Meanwhile, as long as the learner cannot
distinguish the distributions $\text{Bern}(1/2+\delta)^{\otimes(T/N)}$ and
$\text{Bern}(1/2-\delta)^{\otimes(T/N)}$, she is not able to estimate
$\varepsilon^{\star}(x_{i}^{\star})$ based on labels $\\{y_{t}\\}_{t\in
T_{i}}$ in the $i$-th interval. This condition is fulfilled when
$\delta\asymp\sqrt{N/T}$. In addition, a similar argument for Theorem F.2
shows that with an $o(N)$ computational time, the learner cannot predict
future $x_{s}^{\star}$ either. Therefore, any proper learner with
$o(N)=o(\sqrt{|\mathcal{X}|})$ computational time must incur a regret
$\Omega(\delta T)=\Omega(\sqrt{T|\mathcal{X}|^{1/2}})$, which is precisely the
statement of Theorem 5.2 for $d=1$.

####  F.2.2 General $d$.

In this section we lift the hypothesis construction for $d=1$ to general $d$.
Since $1/\sigma\geq d$, we assume that $1/(\sigma d)$ is an integer. Partition
$\mathcal{X}=\cup_{j=1}^{d}\mathcal{X}_{j}$ each of size $|\mathcal{X}|/d$, we
apply the hypothesis class $\mathcal{H}$ in the previous section to each
$\mathcal{X}_{j}$, and set the entire hypothesis class as

$\displaystyle\mathcal{H}_{d}=\left\\{h=(h_{1},\cdots,h_{d})\in\mathcal{H}^{d}\mathrel{\mathop{\mathchar
58\relax}}h|_{\mathcal{X}_{j}}=h_{j},\forall j\in[d]\right\\}.$ (139)

Clearly the VC dimension of $\mathcal{H}_{d}$ is $d$. The adversary is
constructed as follows: partition $[T]$ into $d$ sub-intervals
$T_{1},\cdots,T_{d}$, each of size $T/d$. For the $i$-th sub-interval, we run
the subroutine in the previous section independently on $\mathcal{X}_{i}$. Now
suppose that the total runtime is $o(\sqrt{d|\mathcal{X}|})$, then for at
least half of the sub-intervals, the runtime during each such interval is
$o(\sqrt{|\mathcal{X}|/d})$. By the lower bound for $d=1$, the expected regret
during each such sub-interval is

$\displaystyle\Omega\left(\min\left\\{\frac{T}{d},\sqrt{\frac{T}{d}\cdot\left(\frac{|\mathcal{X}|}{d}\right)^{1/2}}\right\\}\right)=\Omega\left(\min\left\\{\frac{T}{d},\sqrt{T\cdot\left(\frac{|\mathcal{X}|}{d^{3}}\right)^{1/2}}\right\\}\right).$
(140)

Summing over at least $d/2$ such independent sub-problems, the total regret
lower bound is then $\Omega(\min\\{T,\sqrt{T(d|\mathcal{X}|)^{1/2}}\\})$,
establishing the claim of Theorem 5.2.

##  Appendix G Statistical Upper Bounds

###  G.1 Smoothed Online Learning

In this section, we present a statistical upper bound achieved by a
computationally inefficient algorithm. The $\mathscr{Q}$ be the algorithm that
runs Hedge on a finite subset $\mathcal{H}^{\prime}$ on $\mathcal{H}$, where
$\mathcal{H}^{\prime}$ is a $\epsilon$-cover of $\mathcal{H}$ with respect to
the uniform distribution $\mathcal{U}(\mathcal{X})$. The regret upper bound of
this algorithm is bounded as follows.

######  Theorem G.1 (Statistical Upper Bound for Smoothed Online Learning).

For any $\sigma$-smooth adversary $\mathscr{D}_{\sigma}$, the algorithm
$\mathscr{Q}$ described above has regret upper bound

$\displaystyle\operatorname*{\mathbb{E}}[\textsc{Regret}(T,\mathscr{D}_{\sigma},\mathscr{Q})]\in\widetilde{O}\left(\sqrt{Td\log\left(\frac{T}{d\sigma}\right)}+Gd\log\left(\frac{T}{d\sigma}\right)\right).$
(141)

###### Proof.

Let $\mathcal{H}^{\prime}$ be the smallest $\epsilon$-cover of $\mathcal{H}$
with respect to the uniform distribution, i.e., for any $h\in\mathcal{H}$,
there exists a proxy $h^{\prime}\in\mathcal{H}^{\prime}$ such that
$\operatorname*{\mathbb{E}}_{x\sim\mathcal{U}(\mathcal{X})}\left[|h(x)-h^{\prime}(x)|\right]\leq\epsilon$.
By lemma D.2, the size of $\mathcal{H}$ can be upper bounded in terms of the
pseudo dimension $d$:

$\displaystyle\log(|\mathcal{H}^{\prime}|)=\log\mathcal{N}(\epsilon,\mathcal{H},L_{1}(\mathcal{U}(\mathcal{X})))\leq\widetilde{O}\left(d\log\\!\left(\frac{1}{\epsilon}\right)\right),$
(142)

where $\widetilde{O}$ hide factors that are $\log\log(1/\epsilon)$. Based on
the net $\mathcal{H}^{\prime}$, we also define function class $\mathcal{G}$ as
follows.

$\displaystyle\mathcal{G}=\left\\{g_{h,{h^{\prime}}}(x)=|h(x)-{h}^{\prime}(x)|\mathrel{\mathop{\mathchar
58\relax}}h\in\mathcal{H},{h}^{\prime}\in{\mathcal{H}}^{\prime}\text{ is its
proxy}.\right\\}$ (143)

Now consider the following regret decomposition:

$\displaystyle\operatorname*{\mathbb{E}}[\textsc{Regret}(T)]=$
$\displaystyle\operatorname*{\mathbb{E}}\\!\left[\sum_{t=1}^{T}l(\widehat{y}_{t},y_{t})-\inf_{h\in\mathcal{H}}\\!L(h,s_{1\mathrel{\mathop{\mathchar
58\relax}}T})\right]$ (144) $\displaystyle=$
$\displaystyle\operatorname*{\mathbb{E}}\\!\left[\sum_{t=1}^{T}l(\widehat{y}_{t},y_{t})-\inf_{h^{\prime}\in{\mathcal{H}}^{\prime}}\\!L(h^{\prime},s_{1\mathrel{\mathop{\mathchar
58\relax}}T})\right]+\operatorname*{\mathbb{E}}\\!\left[\inf_{{h^{\prime}}\in{\mathcal{H}^{\prime}}}L(h^{\prime},s_{1\mathrel{\mathop{\mathchar
58\relax}}T})-\inf_{h\in\mathcal{H}}L(h,s_{1\mathrel{\mathop{\mathchar
58\relax}}T})\right]$ (145)

Note that the first term is precisely the regret of Hedge on the cover
$\mathcal{H}^{\prime}$. It is thus bounded by

$\displaystyle\operatorname*{\mathbb{E}}\\!\left[\sum_{t=1}^{T}l(\widehat{y}_{t},y_{t})-\inf_{h^{\prime}\in{\mathcal{H}}^{\prime}}\\!L(h^{\prime},s_{1\mathrel{\mathop{\mathchar
58\relax}}T})\right]\leq
O\left(\sqrt{T\log|\mathcal{H}^{\prime}|}\right)\in\widetilde{O}\left(\sqrt{Td\log\\!\left(\frac{1}{\epsilon}\right)}\right).$
(146)

As for the second term, we reformulate it in terms of class $\mathcal{G}$:

$\displaystyle\operatorname*{\mathbb{E}}\\!\left[\inf_{{h^{\prime}}\in{\mathcal{H}^{\prime}}}L(h^{\prime},s_{1\mathrel{\mathop{\mathchar
58\relax}}T})-\inf_{h\in\mathcal{H}}L(h,s_{1\mathrel{\mathop{\mathchar
58\relax}}T})\right]=\operatorname*{\mathbb{E}}\\!\left[\sup_{h\in\mathcal{H}}\inf_{{h^{\prime}}\in{\mathcal{H}^{\prime}}}\sum_{t=1}^{T}l(h^{\prime}(x_{t}),y_{t})-l(h(x_{t}),y_{t})\right]$
(147) $\displaystyle\overset{(a)}{\leq}$
$\displaystyle\operatorname*{\mathbb{E}}\\!\left[\sup_{h\in\mathcal{H}}\inf_{{h^{\prime}}\in{\mathcal{H}^{\prime}}}\sum_{t=1}^{T}G|h(x_{t})-h(x_{t})|\right]=G\cdot\operatorname*{\mathbb{E}}_{\mathscr{D}}\\!\left[\sup_{g\in\mathcal{G}}\sum_{t=1}^{T}g(x_{t})\right],$
(148)

where $(a)$ is because the loss function $l$ has Lipschitz constant $G$.
Analogous to [HRS22, Claim 3.4], we apply the coupling argument in Lemma D.1
to replace the adaptive sequence $x_{t}$s by $z_{t,k}$s that are sampled
independently from the uniform distribution. Thus we obtain

$\displaystyle\operatorname*{\mathbb{E}}_{\mathscr{D}}\\!\left[\sup_{g\in\mathcal{G}}\sum_{t=1}^{T}g(x_{t})\right]\leq
T^{2}(1-\sigma)^{K}+\operatorname*{\mathbb{E}}_{\mathcal{U}(\mathcal{X})}\left[\sup_{g\in\mathcal{G}}\sum_{t=1}^{T}\sum_{i=1}^{K}g(z_{t,k})\right].$
(149)

The expected supremum can be further bounded in terms of the magnitude of
$\mathcal{G}$ (i.e., $\epsilon$) as well as the pseudo dimension of the
original hypothesis class $\mathcal{H}$. Using the bound in Lemma G.2, and
together with Equation 148, we obtain

$\displaystyle\operatorname*{\mathbb{E}}[\textsc{Regret}(T)]\leq\widetilde{O}\left(\sqrt{Td\log\left(\frac{1}{\epsilon}\right)}+G\left(T^{2}(1-\sigma)^{K}+TK\epsilon+\sqrt{TK\epsilon
d\log\\!\left(\frac{1}{\epsilon}\right)}\right)\right).$ (150)

In order to satisfy the condition on $n$ in lemma G.2 and to make the failure
probability of the coupling argument sufficiently small, we take
$\alpha=10\log(T)$, $K=\frac{\alpha}{\sigma}$,
$\epsilon=\Theta\left(\frac{d\sigma}{T\log(T)}\log\left(\frac{T\log(T)}{d\sigma}\right)\right)$.
With this choice of parameters, we have $T^{2}(1-\sigma)^{K}=o(1)$ and

$\displaystyle\operatorname*{\mathbb{E}}[\textsc{Regret}(T)]\leq$
$\displaystyle
O\left(\sqrt{Td\log\left(\frac{1}{\epsilon}\right)}+G\left(\frac{T\log(T)}{\sigma}\epsilon+\sqrt{\frac{T\log(T)}{\sigma}\epsilon
d\log\\!\left(\frac{1}{\epsilon}\right)}\right)\right)$ (151)
$\displaystyle\leq$
$\displaystyle\widetilde{O}\left(\sqrt{Td\log\left(\frac{T}{d\sigma}\right)}+Gd\log\left(\frac{T}{d\sigma}\right)\right),$
(152)

as desired. ∎

######  Lemma G.2 (Concentration for the expected value of supreme).

When
$n\geq\Omega\left(\frac{d}{\epsilon}\log\\!\left(\frac{1}{\epsilon}\right)\right)$,
we have

$\displaystyle\operatorname*{\mathbb{E}}_{x_{1\mathrel{\mathop{\mathchar
58\relax}}n}\overset{\text{iid}}{\sim}\mathcal{U}(\mathcal{X})}\left[\sup_{g\in\mathcal{G}}\sum_{i=1}^{n}g(x_{i})\right]\leq
O\left(n\epsilon+\sqrt{n\epsilon
d\log\\!\left(\frac{1}{\epsilon}\right)}\right).$ (153)

###### Proof.

We will use the bound on expected values of suprema of empirical processes in
[GK06, Theorem 3.1]. To apply their result, the first step is to establish a
bound on the $L_{2}(P)$-covering number of class $\mathcal{G}$. Let
$P_{n}=\frac{1}{n}\sum_{i=1}^{n}\delta_{x_{i}}$ be the empirical distribution
based on independent samples $x_{1},\cdots,x_{n}$. A similar argument to
[BKP97, Lemma 2] gives us

$\displaystyle\mathcal{N}(\epsilon,\mathcal{G},L_{2}(P_{n}))\leq\mathcal{N}(\frac{\epsilon}{2},\mathcal{H},L_{2}(P_{n}))^{2}.$
(154)

Thus we obtain

$\displaystyle\log\mathcal{N}(\epsilon,\mathcal{G},L_{2}(P_{n}))\leq
2\log\mathcal{N}(\frac{\epsilon}{2},\mathcal{H},L_{2}(P_{n}))\leq
2\log\mathcal{M}(\frac{\epsilon}{2},\mathcal{H},L_{2}(P_{n}))\leq
O\left(d\log(\frac{1}{\epsilon})\right),$ (155)

where $\mathcal{M}$ denotes the packing number and the last inequality is due
to [Bar06, Theorem 3.1]. Therefore, for the function $H(x)=O(d\log x)$, we can
guarantee that for any $\epsilon>1$,

$\displaystyle\log\mathcal{N}(\epsilon,\mathcal{G},L_{2}(P_{n}))\leq
H(1/\epsilon),$ (156)

satisfying the condition of [GK06, Theorem 3.1]. Therefore, when
$n\geq\Omega\left(\frac{H\left(1/\epsilon\right)}{\epsilon}\right)=\Omega\left(\frac{d}{\epsilon}\log\\!\left(\frac{1}{\epsilon}\right)\right)$,
[GK06] gives us

$\displaystyle\operatorname*{\mathbb{E}}_{\mathcal{U}}\left[\sup_{g\in\mathcal{G}}\sum_{i=1}^{n}\left(g(x_{t})-\operatorname*{\mathbb{E}}[g(x_{t})]\right)\right]\leq
O\left(\sqrt{n\epsilon H(1/\epsilon)}\right)=O\left(\sqrt{n\epsilon
d\log\\!\left(\frac{1}{\epsilon}\right)}\right).$ (157)

Finally, since $\operatorname*{\mathbb{E}}_{\mathcal{U}}g(x)\leq\epsilon$ for
any $g\in\mathcal{G}$, we obtain

$\displaystyle\operatorname*{\mathbb{E}}\left[\sup_{g\in\mathcal{G}}\sum_{i=1}^{n}g(x_{t})\right]\leq
O\left(n\epsilon+\sqrt{n\epsilon
d\log\\!\left(\frac{1}{\epsilon}\right)}\right),$ (158)

and the proof is complete. ∎

###  G.2 Transductive Online Learning with $K$ Hints

######  Theorem G.3 (Statistical Upper Bound for $K$-hint Transductive
Learning).

In the setting of transductive online learning with $K$ hints, there is an
algorithm that achieves regret $\widetilde{O}\left(G\sqrt{Td\log(K)}\right)$,
where $d$ is the pseudo dimension of the hypothesis class $\mathcal{H}$, and
$G$ is the Lipschitz constant of loss function $l$.

###### Proof.

The proof is similar to Theorem G.1. Let $\mathcal{H}^{\prime}$ be an
$\epsilon$-cover of $\mathcal{H}$ with respect to the uniform distribution
over the set of hints, i.e., $\mathcal{U}(Z_{1\mathrel{\mathop{\mathchar
58\relax}}T})$. By Lemma D.2, we have
$\log|\mathcal{H}^{\prime}|\in\widetilde{O}\left({d\log(1/\epsilon)}\right)$.
Consider the algorithm that runs Hedge on $\mathcal{H}^{\prime}$. We have the
following regret decomposition:

$\displaystyle\operatorname*{\mathbb{E}}[\textsc{Regret}(T)]=$
$\displaystyle\operatorname*{\mathbb{E}}\\!\left[\sum_{t=1}^{T}l(\widehat{y}_{t},y_{t})-\inf_{h\in\mathcal{H}}\\!L(h,s_{1\mathrel{\mathop{\mathchar
58\relax}}T})\right]$ (159) $\displaystyle=$
$\displaystyle\operatorname*{\mathbb{E}}\\!\left[\sum_{t=1}^{T}l(\widehat{y}_{t},y_{t})-\inf_{h^{\prime}\in{\mathcal{H}}^{\prime}}\\!L(h^{\prime},s_{1\mathrel{\mathop{\mathchar
58\relax}}T})\right]+\operatorname*{\mathbb{E}}\\!\left[\inf_{{h^{\prime}}\in{\mathcal{H}^{\prime}}}L(h^{\prime},s_{1\mathrel{\mathop{\mathchar
58\relax}}T})-\inf_{h\in\mathcal{H}}L(h,s_{1\mathrel{\mathop{\mathchar
58\relax}}T})\right].$ (160)

Since the first term is the regret of Hedge on $\mathcal{H}^{\prime}$, it is
bounded by
$O(\sqrt{T\log|\mathcal{H}^{\prime}|})\in\widetilde{O}\left(\sqrt{Td\log\\!\left(\frac{1}{\epsilon}\right)}\right)$.
As for the second term, use the same definition of $\mathcal{G}$ and the fact
that $\\{x_{1},\cdots,x_{T}\\}\subset\\{z_{1,1},\cdots,z_{T,K}\\}$, we obtain

$\displaystyle\operatorname*{\mathbb{E}}\\!\left[\inf_{{h^{\prime}}\in{\mathcal{H}^{\prime}}}L(h^{\prime},s_{1\mathrel{\mathop{\mathchar
58\relax}}T})-\inf_{h\in\mathcal{H}}L(h,s_{1\mathrel{\mathop{\mathchar
58\relax}}T})\right]\leq$ $\displaystyle
G\cdot\operatorname*{\mathbb{E}}\\!\left[\sup_{g\in\mathcal{G}}\sum_{t=1}^{T}g(x_{t})\right]\leq
G\cdot\sup_{g\in\mathcal{G}}\sum_{t=1}^{T}\sum_{k=1}^{K}g(z_{t,k})\leq
O\left(GTK\epsilon\right).$ (161)

Finally, letting $\epsilon=\frac{1}{KT}$ completes the proof. ∎