3cm3cm2.5cm2.2cm

# Topological complexity of finding flex points on cubic plane curves

Weiyan Chen  Weiyan Chen, Yau Mathematical Sciences Center, Ning Zhai,
Tsinghua University, Haidian District, Beijing 100084, China.
<EMAIL_ADDRESS>and  Zheyan Wan  Zheyan Wan, Yanqi Lake Beijing Institute
of Mathematical Sciences and Applications, Hefangkou Village, Huaibei Town,
Huairou District, Beijing 101408, China<EMAIL_ADDRESS>
###### Abstract.

We prove a lower bound for the topological complexity, in the sense of Smale,
of the problem of finding a flex point on a cubic plane curve. The key is to
bound the Schwarz genus of a cover associated to this problem. We also show
that our lower bound for the complexity is close to be the best possible.

###### Key words and phrases:

cubic plane curves, topological complexity, Schwarz genus

######  Mathematics Subject Classification:

55R80, 55M30

##  1\. Introduction

Smale [10] introduced the notion of topological complexity and proved a lower
bound for the topological complexity of the problem of finding roots of a
polynomial. Smale’s lower bounds were later improved by many authors, such as
Vassiliev [11], De Concini-Procesi-Salvetti [4], and Arone [1]. In this paper,
we study the topological complexity of another enumerative problem: the
problem of finding flex points on a cubic plane curve.

A cubic plane curve in $\mathbb{CP}^{2}$ is the locus of a homogeneous
polynomial $F(x,y,z)$ of degree 3. A flex point on a plane curve is where the
curve intersects its tangent line with multiplicity $\geq 3$. Every smooth
cubic plane curve has 9 distinct flex points. For $\epsilon>0$, we consider
the following problem

> $\text{FindFlex}(\epsilon)$: given a smooth cubic plane curve, find a point
> in $\mathbb{CP}^{2}$ that is within $\epsilon$ distance from a flex point of
> the given curve.

Here distance is by the Fubini-Study metric on $\mathbb{CP}^{2}\cong
S^{5}/S^{1}$ induced by the round metric on $S^{5}$. Following Smale [10], we
consider an _algorithm_ to be a finite rooted tree, consisting of a root for
the input, leaves for the output, and internal nodes of the following two
types:

> _computation nodes_ and  _branching nodes_ .

An algorithm is said to _solve_ the problem $\text{FindFlex}(\epsilon)$ if it
inputs a cubic plane curve and outputs a point satisfying the requirement. The
_topological complexity_ of an algorithm is the number of branching nodes in
the tree. The topological complexity of the problem
$\text{FindFlex}(\epsilon)$ is the minimum of the topological complexity of
all algorithms solving the problem. We defer more details to Section 5.

######  Theorem 1.1.

For any $\epsilon<\pi/3$, the topological complexity of
$\text{FindFlex}(\epsilon)$ is at least 7.

A key tool for bounding the topological complexity is the Schwarz genus of
covers, introduced by A. Schwarz [9].

######  Definition.

The _Schwarz genus_ of a cover $E\xrightarrow[]{\xi}B$ is the minimal $k$ such
that $B$ can be covered by $k$ many open subsets on which the projection map
$\xi$ has a continuous section. Notation in this paper: $g({\xi})$ or
$g(E/B).$

We will focus on the following covering map. Define

$\displaystyle\mathcal{X}:=\big{\\{}F(x,y,z)\ |\ F\textrm{ is a nonsingular
homogeneous polynomial of degree 3}\big{\\}}/\mathbb{C}^{\times}$
$\displaystyle\widetilde{\mathcal{X}}_{\text{flex}}:=\big{\\{}(F,p)\in\mathcal{X}\times\mathbb{CP}^{2}\
|\ p\textrm{ is a flex point on the curve defined by }F\big{\\}}.$

In particular $\mathcal{X}=\mathbb{CP}^{9}-\\{\text{singular curves}\\}$. The
map $\widetilde{\mathcal{X}}_{\text{flex}}\to\mathcal{X}$ given by
$(F,p)\mapsto F$ is a 9-fold covering. The main topological theorem of the
paper is the following:

######  Theorem 1.2.

$8\leq g(\widetilde{\mathcal{X}}_{\text{flex}}/\mathcal{X})\leq 9.$

We will prove the lower and the upper bounds in the theorem using different
methods. Proving the lower bound is the most difficult part of the proof where
we will use Leary’s computation of the cohomology of certain $p$-groups [8].
By a standard argument, the Schwarz genus minus one gives a lower bound for
the topological complexity. Hence, Theorem 1.2 implies Theorem 1.1 above.

Whether $g(\widetilde{\mathcal{X}}_{\text{flex}}/\mathcal{X})$ is equal to 8
or 9 remains open. In the last section of the paper, we show that
$g(\widetilde{\mathcal{X}}_{\text{flex}}/\mathcal{X})=8$ if a particular
cohomology class $\mathfrak{o}_{8}$ vanishes. Moreover, we prove that
$3\mathfrak{o}_{8}=0$ in Proposition 6.2. This leads us to make the following
conjecture.

######  Conjecture 1.3.

$g(\widetilde{\mathcal{X}}_{\text{flex}}/\mathcal{X})=8.$

######  Remark (Broader context).

Our work is part of a broader program: to understand how complex it is to
solve enumerative problems in algebraic geometry. Here “solve” can have
various meanings, according to which “solvability” will be determined by
different invariants.

For example, Galois discovered that a polynomial equation of degree 5 or
higher cannot be solved by radicals because its Galois group is not solvable.
In his 1870 treatise on Galois theory [7], Jordan noticed that many
enumerative problems in algebraic geometry also have Galois groups which
control solvability in radicals. However, the study of Galois group in
enumerative geometry remained dormant until Harris’ 1979 paper “Galois groups
of enumerative problems” [6].

Hilbert asked the the following question known as the Hilbert’s thirteenth
problem: How far can the solution to a degree 7 polynomial equation be
simplified? See [5] for a modern formulation of the problem. In 1975, Brauer
[3] introduced the notion of resolvent degree, which determines how far the
solution to a polynomial equation can be simplified. Brauer’s work was mostly
forgotten (never cited) until 2018, when Farb-Wolfson [5] revisited Brauer’s
treatment. More importantly, Farb-Wolfson proposed the research program to
study the resolvent degree of enumerative problems in general.

Our work is inspired by the aforementioned works of Harris and Farb-Wolfson.
We aim to do what they did but for topological complexity: use this invariant
which was originally defined for polynomial equations to study other
enumerative problems. These three invariants - Galois groups, resolvent
degree, and topological complexity - provide different ways to measure how
complex it is to solve enumerative problems, whether the solutions are by
radicals, by algebraic functions in fewer variables, or by algorithms.

### Acknowledgement

We would like to thank Jintai Ding, Benson Farb, Wouter van Limbeek, Craig
Westerland, and Jesse Wolfson for helpful conversations. WC first heard about
the problem of bounding topological complexity of enumerative problems from
Benson Farb and Jesse Wolfson in a class which they co-taught at the
University of Chicago in 2016. WC particularly thanks Wouter van Limbeek for
his suggestion which eventually points to a proof of Proposition 6.4 below. WC
is partially supported by the Young Scientists Fund of the National Natural
Science Foundation of China (Grant No. 12101349).

##  2\. Previous results

In this section, we recalled several standard results that we will use later
in our proofs. None of the results in this section is due to us.

###  2.1. General results about Schwarz genus

All results mentioned in this subsection were proven by Schwarz in [9].

######  Proposition 2.1 ([9], page 71).

Let $i^{*}\xi$ denote the pullback of a cover $\xi:E\to B$ along a continuous
map $i:B^{\prime}\to B$. Then $g(i^{*}\xi)\leq g(\xi)$.

######  Theorem 2.2 ([9], page 71).

Consider a covering $F\to E\xrightarrow{\xi}B$. Let $\xi^{*k}$ denote the
fiberwise join bundle $F^{*k}\to E_{k}\xrightarrow{\xi^{*k}}B$ where $F^{*k}$
is the topological join of $F$ with itself $k$ times. Then $g(\xi)\leq k$ if
and only if $\xi^{*k}$ has a continuous section.

######  Corollary 2.3 ([9], page 76).

If $\xi:E\to B$ is a covering where $B$ is a CW complex of dimension $d$, then
$g(\xi)\leq d+1.$

###### Proof Theorem 2.2 $\Rightarrow$ Corollary 2.3.

By obstruction theory, the obstruction to extending a section of
$\xi^{*(d+1)}$ to its $i$-skeleton is a cohomology class in
$\mathrm{H}^{i+1}(B,\pi_{i}(F^{*(d+1)}))$. We know the cohomology group
vanishes for $i\geq d=\dim B$. If $i\leq d-1$, then $\pi_{i}(F^{*(d+1)})=0$
since $F^{*(d+1)}$ is always $(d-1)$-connected. There is no obstruction to a
section of $\xi^{*(d+1)}$. ∎

######  Theorem 2.4 ([9], page 98).

Suppose that $\xi:Y\to X$ is a Galois $\Gamma$-cover with a classifying map
$cl:X\to B\Gamma$ where $B\Gamma$ is the classifying space of the discrete
group $\Gamma$. If

$\mathrm{H}^{i}(B\Gamma;A)\xrightarrow{cl^{*}}\mathrm{H}^{i}(X;A)\text{ is
nonzero for some $i$ and some $\Gamma$-module $A$,}$

then $g(\xi)\geq i+1$.

###  2.2. The Hesse pencil and the Hessian group

Now we recall several classical facts about cubic plane curves. We refer to
Section 2 and Section 4 of a paper by Artebani and Dolgachev [2] for proofs
and further discussions on these results.

Every smooth cubic plane curve is projectively equivalent to a curve of the
form:

(2.1) $F_{\lambda}:x^{3}+y^{3}+z^{3}-3\lambda xyz=0$

for some $\lambda\in\mathbb{C}$ such that $\lambda^{3}\neq 1$. This
1-parameter family of cubic plane curves $F_{\lambda}$ is called the _Hesse
pencil_. The _Hessian group_ is the subgroup $\Gamma$ of
$\mathrm{Aut}(\mathbb{CP}^{2})=\mathrm{PGL}_{3}(\mathbb{C})=\mathrm{GL}_{3}(\mathbb{C})/\mathbb{C}^{\times}$
preserving the Hesse pencil:

(2.2) $\Gamma:=\big{\\{}g\in\mathrm{PGL}_{3}(\mathbb{C}):\text{ for any
}\lambda,\ \ g\cdot F_{\lambda}=F_{\mu}\text{ for some }\mu\big{\\}}.$

Here $g\cdot F$ denotes $F$ under a change of coordinates $g\cdot
F(x,y,z):=F(g^{-1}(x,y,z))$.

The flex points on any smooth cubic plane curve $F$ in $\mathbb{CP}^{2}$ form
an abstract configuration of 9 points and 12 lines where each point lies on 4
lines and each line contains 3 points, called the _Hesse configuration_. In
particular, there is a bijection taking points to points and lines to lines:

(2.3) $\\{\text{flex points on
$F$}\\}\xrightarrow[]{\cong}\mathbb{A}^{2}(\mathbb{F}_{3})$

Here the affine space $\mathbb{A}^{2}(\mathbb{F}_{3})$ is the vector space
$\mathbb{F}_{3}^{2}$ but without a choice of the origin. All curves in the
Hesse pencil (2.1) share the same set of 9 flex points. The natural action of
the Hessian group $\Gamma$ on the left hand side of (2.3) preserves lines.
Hence, we have a group homomorphism below which turns out to be an
isomorphism:

$\Gamma\xrightarrow[]{\cong}\mathrm{Aut}(\mathbb{A}^{2}(\mathbb{F}_{3}))={\mathrm{ASL}_{2}(\mathbb{F}_{3})}\cong\mathbb{F}^{2}_{3}\rtimes\mathrm{SL}_{2}(\mathbb{F}_{3}).$

In particular, $\Gamma$ is a finite group of order 216. We choose a flex
$p_{0}=[1:-1:0]$ to be the identity of $F_{\lambda}$ as an elliptic curve. The
remaining 8 flex points are precisely the 3-torsion points. After the choice,
the affine bijection (2.3) becomes an isomorphism of abelian groups. The
subgroup $\Gamma_{0}\leq\Gamma$ fixing $p_{0}$ is mapped to the subgroup
$\mathrm{SL}_{2}(\mathbb{F}_{3})\leq{\mathrm{ASL}_{2}(\mathbb{F}_{3})}$ fixing
the origin.

The Hessian group $\Gamma\subset\mathrm{PGL}_{3}(\mathbb{C})$ can be generated
by the following four elements:

(2.4) $A=\begin{bmatrix}0&0&1\\\ 1&0&0\\\ 0&1&0\\\ \end{bmatrix},\
B=\begin{bmatrix}1&0&0\\\ 0&w&0\\\ 0&0&w^{2}\\\ \end{bmatrix},\
C=\begin{bmatrix}1&0&0\\\ 0&1&0\\\ 0&0&w\\\ \end{bmatrix},\
D=\begin{bmatrix}w^{2}&w&1\\\ w&w^{2}&1\\\ 1&1&1\\\ \end{bmatrix}$

where $w:=e^{2\pi i/3}$. In particular, $C$ and $D$ generate the subgroup
$\Gamma_{0}\cong\mathrm{SL}_{2}(\mathbb{F}_{3})$, while $A$ and $B$ generate a
normal subgroup isomorphic to $\mathbb{F}_{3}^{2}$ which acts freely and
transitively on $\mathbb{A}^{2}(\mathbb{F}_{3})$ as translations.

##  3\. Upper bound for Schwarz genus

In this section, we prove the upper bound in Theorem 1.2.

######  Theorem 3.1.

$g(\widetilde{\mathcal{X}}_{\text{flex}}/\mathcal{X})\leq 9$.

######  Lemma 3.2.

Let $\mathcal{H}:=\\{\lambda\in\mathbb{C}\ |\ \lambda^{3}\neq 1\\}$ denote the
space that parameterizes smooth curves in the Hesse pencil (2.1). The Hessian
group $\Gamma$ acts on $\mathcal{H}$ as its automorphism group and acts freely
on $\mathrm{PGL}_{3}(\mathbb{C})$ by multiplication from the right. There is a
diffeomorphism

$\mathcal{X}\cong\mathrm{PGL}_{3}(\mathbb{C})\underset{\Gamma}{\times}\mathcal{H}$

where the right hand side denotes the quotient space by the diagonal action of
$\Gamma$ on the product.

###### Proof.

Consider the map

$\phi:\mathrm{PGL}_{3}(\mathbb{C})\times\mathcal{H}\longrightarrow\mathcal{X}$

given by $\phi(g,\lambda)=g\cdot F_{\lambda}$. This map is surjective since
every smooth cubic plane curve is projectively equivalent to a curve in the
Hesse pencil. The fibers of $\phi$ are precisely orbits of the Hessian group
$\Gamma$ acting diagonally on the product. This action is free since $\Gamma$
acts freely on $\mathrm{PGL}_{3}(\mathbb{C})$ as a subgroup. In particular,
$\phi$ is a Galois $\Gamma$-cover and induces the diffeomorphism in the lemma.
∎

Similarly, we can define a map
$\psi:\mathrm{PGL}_{3}(\mathbb{C})\times\mathcal{H}\longrightarrow\widetilde{\mathcal{X}}_{\text{flex}}$
by $\psi(g,\lambda)=(g\cdot F_{\lambda},\ g\cdot p_{0})$ where
$p_{0}=[1:-1:0]$ is one of the common flex points of curves in the Hesse
pencil. The fibers of $\psi$ are orbits of $\Gamma_{0}$, the subgroup of
$\Gamma$ fixing $p_{0}$, acting diagonally on the product. Hence, we obtain
the following proposition.

######  Proposition 3.3.

The following diagram commutes

${\widetilde{\mathcal{X}}_{\text{flex}}}$${\mathrm{PGL}_{3}(\mathbb{C})\underset{\Gamma_{0}}{\times}\mathcal{H}}$${\mathcal{X}}$${\mathrm{PGL}_{3}(\mathbb{C})\underset{\Gamma}{\times}\mathcal{H}}$$\scriptstyle{\phi}$$\scriptstyle{\cong}$$\scriptstyle{\psi}$$\scriptstyle{\cong}$

where the horizontal maps are diffeomorphisms, and the vertical maps are
9-to-1 covers.

###### Proof of Theorem 3.1.

By Proposition 3.3, it suffices to show that the cover

(3.1)
$\mathrm{PGL}_{3}(\mathbb{C})\underset{\Gamma_{0}}{\times}\mathcal{H}\to\mathrm{PGL}_{3}(\mathbb{C})\underset{\Gamma}{\times}\mathcal{H}$

has Schwarz genus $\leq 9$. Consider the natural projection

$p:\mathrm{PGL}_{3}(\mathbb{C})\underset{\Gamma}{\times}\mathcal{H}\to\mathrm{PGL}_{3}(\mathbb{C})/\Gamma$

given by projecting onto the first coordinates. It is straightforward to check
that the cover in (3.1) is the pullback of the cover

$\mathrm{PGL}_{3}(\mathbb{C})/\Gamma_{0}\to\mathrm{PGL}_{3}(\mathbb{C})/\Gamma$

via the map $p$. Since Schwarz genus is nonincreasing under pullback
(Proposition 2.1), it now suffices to show that

$g(\mathrm{PGL}_{3}(\mathbb{C})/\Gamma_{0}\to\mathrm{PGL}_{3}(\mathbb{C})/\Gamma)\leq
9.$

Finally, observe that $\mathrm{PGL}_{3}(\mathbb{C})$ deformation retracts onto
the projective unitary group
$\mathrm{PU}_{3}=\mathrm{U}_{3}/Z(\mathrm{U}_{3})$. We have
$\Gamma\subseteq\mathrm{PU}_{3}$ since $\Gamma$ is generated by projective
unitary matrices shown in (2.4). Therefore,
$\mathrm{PGL}_{3}(\mathbb{C})/\Gamma$ is homotopy equivalent to
$\mathrm{PU}_{3}/\Gamma$ which is a closed manifold of real dimension 8. By
Corollary 2.3, we have

$g(\mathrm{PGL}_{3}(\mathbb{C})/\Gamma_{0}\to\mathrm{PGL}_{3}(\mathbb{C})/\Gamma)\leq
1+8=9.$

∎

##  4\. Lower bound for Schwarz genus

In this section, we prove the lower bound in Theorem 1.2.

######  Theorem 4.1.

$g(\widetilde{\mathcal{X}}_{\text{flex}}/\mathcal{X})\geq 8$

Let $K$ denote the subgroup of $\Gamma$ generated by the two elements
$A,B\in\Gamma$ as in (2.4)

(4.1) $K:=\langle A,B\rangle.$

Notice that $K$ is abstractly isomorphic to a product of cyclic groups
$C_{3}\times C_{3}$.

######  Proposition 4.2.

Let $BK$ denote the classifying space of $K$. Consider the classifying map
$cl:\mathrm{PU}_{3}/K\to BK$ associated to the principal $K$-cover
$\mathrm{PU}_{3}\to\mathrm{PU}_{3}/K$.

  1. (1)

The following induced map is nonzero:

$H^{7}(BK;\mathbb{F}_{3})\xrightarrow[]{cl^{*}}H^{7}(\mathrm{PU}_{3}/K;\mathbb{F}_{3})$

  2. (2)

In particular, $g(\mathrm{PU}_{3}\to\mathrm{PU}_{3}/K)\geq 8.$

###### Proof Proposition 4.2 $\Rightarrow$ Theorem 4.1.

Consider the Fermat cubic curve

$F_{0}(x,y,z)=x^{3}+y^{3}+z^{3}.$

The subgroup $K=\langle A,B\rangle$ preserves $F_{0}$. Hence, the map
$g\mapsto g\cdot F_{0}$ gives a well-defined map

$\phi:\mathrm{PU}_{3}/K\to\mathcal{X}.$

Moreover, we claim that the pullback of the cover
$\widetilde{\mathcal{X}}_{\text{flex}}\to\mathcal{X}$ along the map $\phi$ is
exactly the cover $\mathrm{PU}_{3}\to\mathrm{PU}_{3}/K$. This is because
$K\cong C_{3}\times C_{3}$ acts on the 9 flex points of $F_{0}$ freely and
transitively as translations of $\mathbb{A}^{2}(\mathbb{F}_{3})$. By
Proposition 2.1, we have

$g(\widetilde{\mathcal{X}}_{\text{flex}}\to\mathcal{X})\geq
g(\mathrm{PU}_{3}\to\mathrm{PU}_{3}/K)\geq 8.$

∎

###### Proof of Proposition 4.2.

(2) directly follows from (1) by Theorem 2.4. We focus on (1).

The first step is to factor the classifying map $cl:\mathrm{PU}_{3}/K\to BK$
into a composition of two maps. Define $\widetilde{P}:=p^{-1}(K)$ where
$p:\mathrm{U}_{3}\to\mathrm{PU}_{3}$ in the natural projection. Then we have a
central extension of groups

(4.2) $1\to\mathrm{U}_{1}\to\widetilde{P}\xrightarrow[]{p}K\to 1.$

Notice that $\mathrm{PU}_{3}/K$ and $\mathrm{U}_{3}/\widetilde{P}$ are the
same space by definitions. Then we have the following commutative diagram:

(4.3)
$\textstyle{\mathrm{H}^{i}(BK;\mathbb{F}_{3})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{cl^{*}}$$\scriptstyle{p^{*}}$$\textstyle{\mathrm{H}^{i}(\mathrm{PU}_{3}/K;\mathbb{F}_{3})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{=}$$\textstyle{\mathrm{H}^{i}(B\widetilde{P};\mathbb{F}_{3})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\phi}$$\textstyle{\mathrm{H}^{i}(\mathrm{U}_{3}/\tilde{P};\mathbb{F}_{3}),}$

where $B\widetilde{P}$ denotes the classifying space of the topological group
$\widetilde{P}\leq\mathrm{U}_{3}$. To show that $cl^{*}$ is nonzero when
$i=7$, we will show that the image of $p^{*}$ is not contained in the kernel
of $\phi$.

The central extension (4.2) induces a fibration $B\mathrm{U}_{1}\to
B\widetilde{P}\xrightarrow[]{p}BK$. The Serre spectral sequence associated to
this fibration had been worked out by Leary [8].

######  Theorem 4.3 (Leary, Theorem 2 in [8]).

$H^{*}(B\widetilde{P};\mathbb{F}_{3})$ is generated by elements
$y,y^{\prime},x,x^{\prime},c_{2},c_{3}$ of degrees $1,1,2,2,4,6$,
respectively, subject to the following relations:

$\displaystyle xy^{\prime}$ $\displaystyle=x^{\prime}y$ $\displaystyle
x^{3}y^{\prime}$ $\displaystyle=x^{\prime 3}y$ $\displaystyle c_{2}y$
$\displaystyle=-x^{2}y$ $\displaystyle c_{2}y^{\prime}$
$\displaystyle=-x^{2}y^{\prime}$ $\displaystyle c_{2}x$ $\displaystyle=-x^{3}$
$\displaystyle c_{2}x^{\prime}$ $\displaystyle=-x^{\prime 3}$ $\displaystyle
c_{2}^{2}$ $\displaystyle=x^{4}+x^{\prime 4}-x^{2}x^{\prime 2}.$

Moreover, $c_{2}$ and $c_{3}$ are the pullbacks of the second and third Chern
classes in $H^{*}(B\mathrm{U}_{3};\mathbb{Z})$ via the inclusion
$\widetilde{P}\hookrightarrow\mathrm{U}_{3}$ and modulo 3. The first Chern
class pulls back to $c_{1}=yy^{\prime}.$

Recall that $H^{*}(BC_{3};\mathbb{F}_{3})$ is a free graded algebra generated
by $\tilde{y}$ and $\tilde{x}$ of degree 1 and 2, respectively. Since $K\cong
C_{3}\times C_{3}$, we can find generators
$\tilde{y},\tilde{y}^{\prime},\tilde{x},\tilde{x}^{\prime}$ for
$H^{*}(\mathrm{B}K;\mathbb{F}_{3})$ by the Künneth formula. By Leary’s proof
of Theorem 4.3 in [8], the map $p^{*}$ in (4.3) sends the generators
$\tilde{y},\tilde{y}^{\prime},\tilde{x},\tilde{x}^{\prime}$ to
$y,y^{\prime},x,x^{\prime}$, respectively. Hence, we have the following
presentation of subring:

$p^{*}\big{(}H^{*}(BK;\mathbb{F}_{3})\big{)}=\langle
y,y^{\prime},x,x^{\prime}\rangle/(xy^{\prime}-x^{\prime}y,x^{3}y^{\prime}-x^{\prime
3}y)$

where the quotient ideal is given by the first two relations in Theorem 4.3.
In particular, on $H^{7}$, we have:

(4.4)
$p^{*}\big{(}H^{7}(BK;\mathbb{F}_{3})\big{)}=\mathrm{span}\\{yx^{3},yx^{2}x^{\prime},yxx^{\prime
2},yx^{\prime
3},y^{\prime}x^{3},y^{\prime}x^{2}x^{\prime},y^{\prime}xx^{\prime
2},y^{\prime}x^{\prime 3}\\}.$

Those elements above spanned $p^{*}\big{(}H^{7}(BK;\mathbb{F}_{3})\big{)}$,
but subject to linear relations in the ideal
$(xy^{\prime}-x^{\prime}y,x^{3}y^{\prime}-x^{\prime 3}y)$.

Next, we study the kernel of $\phi$ in (4.3). We first recall some basic facts
about the Serre spectral sequence of the universal principal
$\mathrm{U}_{3}$-bundle:

(4.5) $\mathrm{U}_{3}\to E\mathrm{U}_{3}\to B\mathrm{U}_{3}$

By Borel’s Transgression Theorem, each generator $a_{2i-1}$ of
$H^{2i-1}(\mathrm{U}_{3};\mathbb{Z})$ transgresses to the $i$-th Chern class
in $H^{2i}(B\mathrm{U}_{3};\mathbb{Z})$ for $i=1,2,3$.

Now, the fibration

(4.6) $\mathrm{U}_{3}\to\mathrm{U}_{3}/\widetilde{P}\to B\widetilde{P}$

is homotopy equivalent to the pullback of the universal bundle (4.5) along a
classifying map $B\widetilde{P}\to B\mathrm{U}_{3}$. Consequently, in the
(cohomological) Serre spectral sequence of (4.6), each generator $a_{2i-1}$ of
$H^{2i-1}(\mathrm{U}_{3};\mathbb{F}_{3})$ transgresses to $c_{i}\in
H^{2i}(B\widetilde{P};\mathbb{F}_{3})$ as in Theorem 4.3. Hence, the kernel of
$\phi:H^{*}(B\widetilde{P};\mathbb{F}_{3})\to
H^{*}(\mathrm{U}_{3}/\widetilde{P};\mathbb{F}_{3})$ is the ideal generated by
$c_{1},c_{2},c_{3}.$ In particular, on $H^{7}$, we have

$\text{Ker}\phi=c_{1}\mathrm{H}^{5}(B\tilde{P};\mathbb{F}_{3})+c_{2}\mathrm{H}^{3}(B\tilde{P};\mathbb{F}_{3})+c_{3}\mathrm{H}^{1}(B\tilde{P};\mathbb{F}_{3}).$

By the relations in Theorem 4.3, we have that

(4.7) $\displaystyle\ \ \ \ \ \ \ \ \ \ \
c_{1}\mathrm{H}^{5}(B\tilde{P};\mathbb{F}_{3})=(yy^{\prime})\cdot\mathrm{span}\\{yx^{2},yxx^{\prime},yx^{\prime
2},c_{2}y,y^{\prime}x^{2},y^{\prime}xx^{\prime},y^{\prime}x^{\prime
2},c_{2}y^{\prime}\\}=0,$ (4.8) $\displaystyle
c_{2}\mathrm{H}^{3}(B\tilde{P};\mathbb{F}_{3})=c_{2}\cdot\mathrm{span}\\{yx,yx^{\prime}=y^{\prime}x,y^{\prime}x^{\prime}\\}$

where

$\displaystyle c_{2}yx$ $\displaystyle=$ $\displaystyle-x^{2}yx=-yx^{3},$
$\displaystyle c_{2}y^{\prime}x^{\prime}$ $\displaystyle=$
$\displaystyle-x^{\prime 2}y^{\prime}x^{\prime}=-y^{\prime}x^{\prime 3},$
(4.9) $\displaystyle c_{2}yx^{\prime}$ $\displaystyle=$
$\displaystyle-x^{2}yx^{\prime}=-yx^{2}x^{\prime},$

and

(4.10) $\displaystyle
c_{3}\mathrm{H}^{1}(B\tilde{P};\mathbb{F}_{3})=c_{3}\cdot\mathrm{span}\\{y,y^{\prime}\\}.$

In particular, we find an element $yxx^{\prime
2}=y^{\prime}x^{2}x^{\prime}\in\text{Im}p^{*}$ but $yxx^{\prime
2}=y^{\prime}x^{2}x^{\prime}\not\in\text{Ker}\phi$. Hence,
$\text{Im}p^{*}\not\subseteq\text{Ker}\phi$. Therefore,
$cl^{*}:\mathrm{H}^{7}(BK;\mathbb{F}_{3})\to\mathrm{H}^{7}(\mathrm{PU}_{3}/K;\mathbb{F}_{3})$
is nonzero.

∎

##  5\. Topological complexity of flex-finding algorithms

Following Smale [10], we consider an _algorithm_ to be a finite rooted tree,
consisting of a root for the input, leaves for the output, and internal nodes
of the following two types:

  * •

_Computation nodes_ , which receives a sequence of real numbers, computes
using rational operations $+,\ -,\ \times,\ \div\ $, and gives another
sequence of real numbers to the next node;

  * •

_Branching nodes_ , which go right or left according to whether an inequality
$h\leq 0$ is true or false, where $h$ is one of the real numbers in the
sequence which the node receives.

An algorithm is said to _solve_ the following problem

> $\text{FindFlex}(\epsilon)$: given a smooth cubic plane curve, find a point
> in $\mathbb{CP}^{2}$ that is within $\epsilon$ distance from a flex point of
> the given curve.

if it inputs a sequence of real numbers recording the real and imaginary parts
of the coefficients of $F(x,y,z)$ defining an arbitrary cubic plane curve and
outputs a sequence of real numbers recording the real and imaginary parts of
the coordinates of a point $[x:y:z]$ in $\mathbb{CP}^{2}$ satisfying the
requirement. The _topological complexity_ of an algorithm is the number of
branching nodes in the tree. The topological complexity of the problem
$\text{FindFlex}(\epsilon)$ is the minimum of the topological complexity of
all algorithms solving the problem.

We now prove Theorem 1.1 which gives a lower bound for the topological
complexity of any algorithm that finds a flex point on cubic plane curves.
Theorem 1.1 directly follows from Theorem 4.1 together with the following
proposition.

######  Proposition 5.1.

For any $\epsilon<\pi/3$, the topological complexity of the problem
$\text{FindFlex}(\epsilon)$ is at least
$g(\widetilde{\mathcal{X}}_{\text{flex}}/\mathcal{X})-1$.

This proposition is a direct analog of the “Smale principle” as Vassiliev
calls it (Section 2.3 in [11]). Specifically, Smale proved that the
topological complexity of the problem of finding all roots within $\epsilon$
of a complex polynomial $f(z)$ is bounded from below by the Schwarz genus of
the cover associated to the problem minus one, for all $\epsilon$ sufficiently
small (See Theorem A in [10]). After his proof, Smale remarked that the
argument works in “considerably greater generality”. Our proof of Proposition
5.1 below is a slight modification of Smale’s argument. Even better, we can
get an explicit bound $\pi/3$ for how small $\epsilon$ needs to be.

###### Proof.

It suffices to show that any algorithm with $k$ leaves (and hence with $k-1$
branching nodes) solving the problem $\text{FindFlex}(\epsilon)$ gives an open
cover of $\mathcal{X}$ with $k$ subsets and a section of the cover
$\widetilde{\mathcal{X}}_{\text{flex}}\to\mathcal{X}$ defined on each subset.

The explicit upper bound $\pi/3$ comes from the following observation: the
distance between any two flex points on an arbitrary smooth cubic plane curve
is exactly $2\pi/3$. To see this, it suffices to consider only those curves
$F_{\lambda}$ in the Hesse pencil (2.1) because every cubic curve is
projective equivalent to a curve in the Hesse pencil and the Fubini-Study
metric on $\mathbb{CP}^{2}$ is $\mathrm{PGL}_{3}(\mathbb{C})$-invariant.
Moreover, any pair of flex points of $F_{\lambda}$ has the same distance
because the action of $\Gamma\subset\mathrm{PGL}_{3}(\mathbb{C})$ on the 9
flex points is 2-transitive, _i.e._ transitive on pairs of distinct elements.
Finally, the distance between two flex points of $F_{\lambda}$, for example,
$[1:-1:0]$ and $[1:-e^{2\pi/3}:0]$, is $2\pi/3$.

Suppose we are given an algorithm solving $\text{FindFlex}(\epsilon)$ with
output leaves numbered $i=1,\cdots,k$. Let $V_{i}$ denote the subset of
$\mathcal{X}$ consisting of all those inputs that will arrive at the $i$-th
output leaf of the algorithm. Then $\mathcal{X}$ as a set is a disjoint union
of $V_{i}$’s. Moreover, each $V_{i}$ is the intersection of a closed subset in
$\mathcal{X}$, consisting of inputs satisfying $h\leq 0$ at each branching
node where the path from the input root to the $i$-th output leaf goes to the
right, and an open subset in $\mathcal{X}$, consisting of inputs not
satisfying $h\leq 0$ at each branching node where the same path goes to the
left. The algorithm gives a map $\phi_{i}:V_{i}\to\mathbb{CP}^{2}$ for each
$i=1,\cdots,k$ such that for any $F\in V_{i}$, the point $\phi_{i}(F)$ is
$\epsilon$-close to a flex point of $F$. By the Tietze Extension Theorem,
$\phi_{i}$ can be extended to an open subset $U_{i}\supseteq V_{i}$ satisfying
the same property: any $F\in U_{i}$, the point $\phi_{i}(F)$ is
$\epsilon$-close to a unique flex point of $F$, which we denote by $s_{i}(F)$.
The flex point $s_{i}(F)$ is unique because $\epsilon<\pi/3$, which is one
half of the distance between any two distinct flex points on $F$. Now we have
an open cover $U_{i}$’s of $\mathcal{X}$ by $k$ many subsets, on which there
is a section $s_{i}:U_{i}\to\widetilde{\mathcal{X}}_{\text{flex}}$ of the
cover $\widetilde{\mathcal{X}}_{\text{flex}}\to\mathcal{X}$. ∎

######  Remark.

Unlike Smale’s proof in [10], our proof works in greater generality if we
allow algorithms to have computation nodes by continuous functions, rather
than by rational functions only.

##  6\. What is left to determine the Schwarz genus?

Theorem 1.2 shows that $g(\widetilde{\mathcal{X}}_{\text{flex}}/\mathcal{X})$
is either 8 or 9. What do we need to determine which one is the case?

Applying Theorem 2.2 to the cover
$\widetilde{\mathcal{X}}_{\text{flex}}\to\mathcal{X}$, we see that
$g(\widetilde{\mathcal{X}}_{\text{flex}}/\mathcal{X})\leq 8$ if and only if
the fiber bundle

(6.1) $F^{*8}\to E_{8}\to\mathcal{X}$

has a continuous section where $F$ denotes the fiber of
$\widetilde{\mathcal{X}}_{\text{flex}}\to\mathcal{X}$. Since $F$ is just a set
of 9 points, $F^{*8}$ is a wedge of 7-spheres. The first obstruction to a
section of the bundle above is

$\mathfrak{o}_{8}\in H^{8}(\mathcal{X};\pi_{7}(F^{*8})).$

Moreover, one can show that

$\pi_{7}(F^{*8})\cong\widetilde{H}_{0}(F;\mathbb{Z})^{\otimes
8}\cong(\mathbb{Z}^{8})^{\otimes 8}.$

######  Proposition 6.1.

$g(\widetilde{\mathcal{X}}_{\text{flex}}/\mathcal{X})=8$ if and only if the
first obstruction $\mathfrak{o}_{8}$ is zero.

###### Proof.

The “only if” part follows from obstruction theory. To prove the “if” part, we
need to show that there can be no further obstruction after the first one.
However, we proved in Proposition 3.3 that the cover
$\widetilde{\mathcal{X}}_{\text{flex}}\to\mathcal{X}$ is a pullback of a cover
$\mathrm{PU}_{3}/\Gamma_{0}\to\mathrm{PU}_{3}/\Gamma$. Hence, those
obstruction classes on $\mathcal{X}$ are pullbacks of the corresponding
obstruction classes on $\mathrm{PU}_{3}/\Gamma$. Now recall that
$\mathrm{PU}_{3}/\Gamma$ is an 8-dimensional manifold and thus has no nonzero
cohomology class beyond dimension 8. ∎

We are not able to determine whether $\mathfrak{o}_{8}$ is zero or not. One
difficulty is that the coefficient module $(\mathbb{Z}^{8})^{\otimes 8}$ is
too big for explicit calculation by hand or by a computer. However, we can
prove that $\mathfrak{o}_{8}$ is a 3-torsion element.

######  Proposition 6.2.

$3\mathfrak{o}_{8}=0$ in $H^{8}(\mathcal{X};\pi_{7}(F^{*8}))$.

######  Lemma 6.3.

Let $Z\to E\to B$ be a fiber bundle and let $\mathfrak{o}_{i}\in
H^{i}(B;\pi_{i-1}(Z))$ be the first obstruction class to a section of it. If
there is a degree-$d$ cover $\tilde{B}$ of the base $B$ such that the pullback
of the bundle to $\tilde{B}$ has a continuous section, then
$d\mathfrak{o}_{i}=0$.

###### Proof.

Let $p:\widetilde{B}\to B$ denote the covering map. We know that
$p^{*}\mathfrak{o}_{i}=0$ since the pullback bundle has a section. Now, we
have a composition of maps

$\displaystyle H^{i}(B;\pi_{i-1}(Z))\xrightarrow[]{p^{*}}$ $\displaystyle
H^{i}(\widetilde{B};\pi_{i-1}(Z))$
$\displaystyle\xrightarrow{{tr}}H^{i}(B;\pi_{i-1}(Z))$ (6.2)
$\displaystyle\mathfrak{o}_{i}\mapsto$ $\displaystyle p^{*}\mathfrak{o}_{i}=0$
$\displaystyle\mapsto d\mathfrak{o}_{i}$

where $tr$ denotes the transfer map. Hence, $d\mathfrak{o}_{i}=0$. ∎

###### Proof of Proposition 6.2.

The pullback of the fiber bundle (6.1) along the degree-$9$ cover
$\widetilde{\mathcal{X}}_{\text{flex}}\to\mathcal{X}$ has a continuous section
given by the natural inclusion of fibers $F\to F^{*8}$. Lemma 6.3 implies that
$9\mathfrak{o}_{8}=0$.

We claim that to prove Proposition 6.2, it suffices to prove the following

> Claim: There is a degree-24 covering $p:Y\to\mathcal{X}$ such that the
> pullback of the covering
> $\widetilde{\mathcal{X}}_{\text{flex}}\to\mathcal{X}$ along $p$ has Schwarz
> genus $\leq 8$.

Assuming the claim, we have that $24\mathfrak{o}_{8}=0$ by Lemma 6.3. Then we
have that $3\mathfrak{o}_{8}=3\cdot(9\mathfrak{o}_{8})-24\mathfrak{o}_{8}=0.$

Now we focus on proving the claim. Again, recall from our proof of Proposition
3.3 that the cover $\widetilde{\mathcal{X}}_{\text{flex}}\to\mathcal{X}$ is a
pullback of the cover

(6.3) $\mathrm{PU}_{3}/\Gamma_{0}\to\mathrm{PU}_{3}/\Gamma$

along a map $\mathcal{X}\to\mathrm{PU}_{3}/\Gamma$. Since Schwarz genus is
nonincreasing under pullback (Proposition 2.1), in order to prove the claim
stated above, it suffices to prove the same claim where we replace
$\mathcal{X}$ by $\mathrm{PU}_{3}/\Gamma$ and
$\widetilde{\mathcal{X}}_{\text{flex}}$ by $\mathrm{PU}_{3}/\Gamma_{0}$. Next,
we consider the degree-24 covering map

$p:\mathrm{PU}_{3}/K\to\mathrm{PU}_{3}/\Gamma$

where again $K$ denotes the subgroup defined in (4.1). The cover has degree 24
because $|\Gamma|=216$ and $|K|=9$. Since $K\cap\Gamma_{0}=1$, the pullback of
the cover (6.3) along $p$ is the cover

$\mathrm{PU}_{3}\to\mathrm{PU}_{3}/K.$

We are done if we can show the following:

######  Proposition 6.4.

$g(\mathrm{PU}_{3}\to\mathrm{PU}_{3}/K)\leq 8$.

###### Proof.

Our strategy is to find a closed subgroup $H\cong\mathrm{U}_{1}$ inside
$\mathrm{PU}_{3}$ such that the action of $K$ from the right on the (left)
coset space $H\backslash\mathrm{PU}_{3}$ is free. If we can find such $H$,
then we have the following pullback diagram of covers:

${\mathrm{PU}_{3}}$${H\backslash\mathrm{PU}_{3}}$${\mathrm{PU}_{3}/K}$${H\backslash\mathrm{PU}_{3}/K}$

Then Proposition 6.4 will follow from Proposition 2.1 and Corollary 2.3,
together with the observation that the double coset space
$H\backslash\mathrm{PU}_{3}/K$ is a manifold of dimension $8-1=7$.

Now let’s find such $H\leq\mathrm{PU}_{3}$. We just need $H$ to satisfy that

$H\cap gKg^{-1}=1,\ \ \ \ \forall g\in\mathrm{PU}_{3}.$

We claim that the subgroup

$H:=\\{\mathrm{diag}(1,z,z)\ |\ z\in\mathrm{U}_{1}\\}$

suffices. Even though eigenvalues of elements in $\mathrm{PU}_{3}$ are only
well-defined up to simultaneous multiplication of a scalar, the total number
of distinct eigenvalues is well-defined for elements in $\mathrm{PU}_{3}$. By
a straightforward computation, we check that every nontrivial element in
$K=\langle A,B\rangle$ has 3 distinct eigenvalues. However, every nontrivial
element in $H$ has 2 distinct eigenvalues. Hence, $H$ intersects trivially
with any conjugate of $K$ in $\mathrm{PU}_{3}$. ∎

∎

######  Remark.

Is it possible to improve our arguments above to get better lower or upper
bounds for $g(\widetilde{\mathcal{X}}_{\text{flex}}/\mathcal{X})$? It seems
not for the following reasons.

We obtained the lower bound
$g(\widetilde{\mathcal{X}}_{\text{flex}}/\mathcal{X})\geq 8$ in Theorem 4.1 by
showing that $g(\mathrm{PU}_{3}\to\mathrm{PU}_{3}/K)\geq 8$ in Proposition
4.2. Now Proposition 6.4 tells us that our previous argument cannot be
improved to obtain any stronger lower bound.

In the opposite direction, one might hope to improve the upper bound
$g(\widetilde{\mathcal{X}}_{\text{flex}}/\mathcal{X})\leq 9$ in Theorem 3.1 by
adapting our proof of Proposition 6.4 to the cover
$\mathrm{PU}_{3}/\Gamma_{0}\to\mathrm{PU}_{3}/\Gamma$ if we replace $K$ by the
larger group $\Gamma$. This is not possible because one can show that any
closed subgroup $H$ in $\mathrm{PU}_{3}$ will have a nontrivial intersection
with some conjugate of $\Gamma$.

## References

  * [1] G. Arone.  A note on the homology of $\Sigma_{n}$, the Schwartz genus, and solving polynomial equations.  Contemporary Mathematics, 399:1, 2006.
  * [2] M. Artebani and I. Dolgachev.  The Hesse pencil of plane cubic curves.  Enseign. Math. (2), 55(3-4):235–273, 2009.
  * [3] R. Brauer.  On the resolvent problem.  Annali di Matematica Pura ed Applicata, 102(1):45–55, 1975.
  * [4] C. De Concini, C. Procesi, and M. Salvetti.  On the equation of degree 6.  Commentarii Mathematici Helvetici, 79:605–617, 2004.
  * [5] B. Farb and J. Wolfson.  Resolvent degree, hilbert’s 13th problem and geometry.  L’Enseignement Mathématique, 65(3):303–376, 2020.
  * [6] J. Harris.  Galois groups of enumerative problems.  Duke Math. J., 46(4):685–724, 1979.
  * [7] C. Jordan.  Traité des substitutions et des équations algébriques, volume 1.  Gauthier-Villars, 1870.
  * [8] I. J. Leary.  The mod-$p$ cohomology rings of some $p$-groups.  Math. Proc. Cambridge Philos. Soc., 112(1):63–75, 1992.
  * [9] A. Schwarz.  The genus of a fiber space.  Amer. Math. Soc. Transl., 2, 1966.
  * [10] S. Smale.  On the topology of algorithms. I.  J. Complexity, 3(2):81–89, 1987.
  * [11] V. A. Vassiliev.  Complements of discriminants of smooth maps: topology and applications, volume 98 of Translations of Mathematical Monographs.  American Mathematical Society, Providence, RI, 1992.  Translated from the Russian by B. Goldfarb.


# A Novel Theoretical Framework for Exponential Smoothing

Enrico Bernardi Dipartimento di Scienze Statistiche Paolo Fortunati,
Università di Bologna, Bologna, Italy. e-mail<EMAIL_ADDRESS>Alberto Lanconelli Dipartimento di Scienze Statistiche Paolo Fortunati,
Università di Bologna, Bologna, Italy. e-mail<EMAIL_ADDRESS>Christopher S. A. Lauria Dipartimento di Scienze Statistiche Paolo Fortunati,
Università di Bologna, Bologna, Italy. e-mail<EMAIL_ADDRESS>
###### Abstract

Simple Exponential Smoothing is a classical technique used for smoothing time
series data by assigning exponentially decreasing weights to past observations
through a recursive equation; it is sometimes presented as a rule of thumb
procedure. We introduce a novel theoretical perspective where the recursive
equation that defines simple exponential smoothing occurs naturally as a
stochastic gradient ascent scheme to optimize a sequence of Gaussian log-
likelihood functions. Under this lens of analysis, our main theorem shows that
-in a general setting- simple exponential smoothing converges to a
neighborhood of the trend of a trend-stationary stochastic process. This
offers a novel theoretical assurance that the exponential smoothing procedure
yields reliable estimators of the underlying trend shedding light on long-
standing observations in the literature regarding the robustness of simple
exponential smoothing.

Key words and phrases: exponential smoothing, stochastic gradient ascent,
maximum likelihood.

AMS 2020 classification: 65K05, 62F12.

##  1 Introduction

Formally defined in Brown, (1956), and then further developed in Brown, (1959)
and Brown, (1963), Simple Exponential Smoothing (SES) was initially introduced
to generate forecasts for time series data by giving more weight to recent
observations while exponentially diminishing the influence of older data.
Mathematically, the SES procedure is succinctly captured by a straightforward
recursive expression

$\displaystyle S_{t+1}=S_{t}+\alpha(X_{t+1}-S_{t}),$ (1.1)

where $X_{t+1}$ denotes the observation at time $t+1$, $0<\alpha<1$ is the so
called _smoothing parameter_ and $S_{0}\in\mathbb{R}$ is a chosen initial
value.
SES enjoyed success in multiple applications, Winters, (1960), Makridakis et
al., (1982), Gross and Craig, (1974), and was generalized in a number of ways;
a taxonomy can be found in Hyndman et al., (2002), Taylor, (2003) and Gardner
Jr, (2006). A remarkable property of SES is its robustness with regards to the
assumed data generating process, a quality observed in several publications,
Cohen, (1963), Cox, (1961), Tiao and Xu, (1993). Furthermore, Bossons, (1966)
showed that SES tends to be largely unaffected by specification errors, while
Hyndman, (2001) explains how ARIMA model selection errors can significantly
amplify mean square deviations when compared to SES.
Despite its success in empirical settings SES has sometimes been criticized
for being ”an ad hoc procedure with no statistical rationale”, as recounted in
Gardner Jr, (2006). The main procedure used to theoretically justify
exponential smoothing methods has been to define statistical models for which
the optimal forecasts are equivalent to those obtained from the exponential
smoother. In Muth, (1960) two models are provided for which the optimal
forecasts are given by the SES equation with appropriately chosen smoothing
parameter. More recently, Ord et al., (1997) defined a class of state-space
models with a single source of error for which the forecasts are given by the
Holt-Winters exponential smoother Winters, (1960); subsequently, Hyndman et
al., (2002) extended the work of Ord et al., (1997) to include numerous other
exponential smoothing procedures. For a clear and comprehensive presentation
of the state space framework for exponential smoothing see Hyndman et al.,
(2008).
In this paper, we will establish a novel bound on the estimates generated by
SES that holds in a surprisingly general setting. Our approach involves a
clear statistical rationale, derived from the classical theory of maximum
likelihood estimation, that sheds light on longstanding observations in the
literature concerning the robustness properties of SES. The paper is organized
as follows: in subsection 2 we show how SES can be viewed as time varying
stochastic gradient ascent scheme. In subsection 3 we formally state our main
result and in section 4 we provide some relevant simulations. Section 5 will
be dedicated to the proof of the main result.

##  2 Exponential Smoothing as Stochastic Gradient Ascent

A trend-stationary stochastic process is a stochastic process from which a
function of time can be subtracted, leaving a stationary process. Formally, a
stochastic process $\\{X_{t}\\}_{t\in\mathbb{N}}$, is said to be trend
stationary if

$\displaystyle X_{t}=m_{t}^{\star}+\epsilon_{t},\quad t\in\mathbb{N},$ (2.1)

for some sequence of real numbers $\\{m_{t}^{\star}\\}_{t\in\mathbb{N}}$,
called _trend_ , and some weakly stationary sequence
$\\{\epsilon_{t}\\}_{t\in\mathbb{N}}$ with $\mathbb{E}[\epsilon_{t}]=0$ and
$\mathtt{cov}(\epsilon_{t},\epsilon_{s})\coloneqq\gamma(t,s)=\gamma(t-s)$ for
all $t,s\in\mathbb{N}$; here, $\gamma:\mathbb{Z}\rightarrow\mathbb{R}$ is an
even positive definite function. In this setting, SES has been used as a
method for estimating the trend $\\{m_{t}^{\star}\\}_{t\in\mathbb{N}}$ through
the observed values $\\{X_{t}\\}_{t\in\mathbb{N}}$, Brockwell and Davis,
(2009).
We will now show how SES (1.1) can be cast as a stochastic gradient ascent
algorithm employed for solving an optimization problem. First we relabel the
SES recursive equation (1.1) by defining $\hat{m}_{t+1}\coloneqq S_{t}$, for
all $t\geq 1$, resulting in

$\displaystyle\hat{m}_{t+1}=(1-\alpha)\hat{m}_{t}+\alpha X_{t},\quad
t\in\mathbb{N}$ (2.2)

Now the sequence $\\{\hat{m}_{t}\\}_{t\in\mathbb{N}}$ is simply a delayed
version of (1.1): $\hat{m}_{t+1}$ is an estimate for $m^{*}_{t}$ and not for
$m^{*}_{t+1}$. Taking as initial value the common choice $\hat{m}_{1}=X_{1}$
we then rewrite equation (2.2) as

$\displaystyle\hat{m}_{t+1}=\hat{m}_{t}+\alpha(X_{t}-\hat{m}_{t})=\hat{m}_{t}+\tilde{\alpha}\frac{d}{d\hat{m}}\left[\ln\left(\frac{1}{\sqrt{2\pi\gamma(0)}}e^{-\frac{(X_{t}-\hat{m})^{2}}{2\gamma(0)}}\right)\right]\Big{|}_{\hat{m}=\hat{m}_{t}},\quad
t\in\mathbb{N}$ (2.3)

with $\tilde{\alpha}:=\alpha\gamma(0)$. If the sequence
$\\{\epsilon_{t}\\}_{t\in\mathbb{N}}$ in (2.1), and hence
$\\{X_{t}\\}_{t\in\mathbb{N}}$, is Gaussian (such assumption can be relaxed,
see Remark 2.2 below), then the expression between square brackets in (2.3)
coincides with the log-likelihood of $X_{t}$ evaluated at $\hat{m}_{t}$; from
this point of view the scheme (2.3) takes the form of a stochastic gradient
ascent algorithm with constant learning rate $\tilde{\alpha}$. Notice however
that, at each time $t$, the stochastic gradient employed belongs to a
different Gaussian: this type of algorithm is employed in the optimization
literature to track an optimum that moves through time.
Tracking a sequence of optima through time is a problem that has already been
considered in a variety of settings, see for instance Polyak, (1987), Popkov,
(2005), Zinkevich, (2003), Bubeck et al., (2008), Cao et al., (2019). Using
the nomenclature of Simonetto et al., (2020), these types of problems have
been called _time-varying_ optimization problems since their aim is to find
the optima $t\mapsto m^{*}_{t}\coloneqq\operatorname*{arg\,max}f(t,m)$ of a
sequence of objective functions $\\{f(t,\cdot)\\}_{t\in\mathbb{N}}$. A
computationally efficient manner to track the optima is via recursive schemes
that utilize the gradient of the sequence $\\{f(t,\cdot)\\}_{t\in\mathbb{N}}$
Simonetto et al., (2016), Simonetto and Dall’Anese, (2017). The simplest
prototypical algorithmic procedure that has been considered is to employ a
standard gradient ascent scheme where at the $t$-th iteration the gradient is
computed with respect to the $t$-th objective function, in formulas:

$\displaystyle\hat{m}_{t+1}=\hat{m}_{t}+\alpha\frac{d}{d\hat{m}}f(t,\hat{m})\Big{|}_{\hat{m}=\hat{m}_{t}},\quad
t\in\mathbb{N},$ (2.4)

where $\alpha>0$ is the so-called _learning rate_. If the distance between
optimizers at subsequent times is uniformly upper bounded, then running the
recursive equation (2.4) will track the solution trajectory up to a
neighborhood Simonetto et al., (2020). We can now observe that taking

$\displaystyle
f(t,\hat{m})\coloneqq\mathbb{E}\left[\ln\left(\frac{1}{\sqrt{2\pi\gamma(0)}}e^{-\frac{(X_{t}-\hat{m})^{2}}{2\gamma(0)}}\right)\right]$
(2.5)

equation (2.4) becomes

$\displaystyle\hat{m}_{t+1}=\hat{m}_{t}+\alpha\frac{d}{d\hat{m}}\mathbb{E}\left[\ln\left(\frac{1}{\sqrt{2\pi\gamma(0)}}e^{-\frac{(X_{t}-\hat{m})^{2}}{2\gamma(0)}}\right)\right]\Big{|}_{\hat{m}=\hat{m}_{t}},\quad
t\in\mathbb{N},$

that through a stochastic approximation of the expected value Robbins and
Monro, (1951) is analogous to equation (2.3). The trend
$\\{m_{t}^{*}\\}_{t\in\mathbb{N}}$ is the solution to the optimization problem
defined by the sequence of objective functions

$\left\\{\mathbb{E}\left[\ln\left(\frac{1}{\sqrt{2\pi\gamma(0)}}e^{-\frac{(X_{t}-\hat{m})^{2}}{2\gamma(0)}}\right)\right]\right\\}_{t\in\mathbb{N}}.$

Therefore, the SES method (2.2) for trend estimation is equivalent to a time
varying stochastic gradient ascent algorithm that tracks the maxima of the
log-likelihoods associated with the observations (2.1).

######  Remark 2.1.

If the trend $\\{m_{t}^{*}\\}_{t\in\mathbb{N}}$ is constant, i.e.
$m_{t}^{*}=m^{*}$ for all $t\in\mathbb{N}$, we have a single objective
function to maximize, as is canonical in the classical theory of maximum
likelihood estimation. In this case one can simply use the arithmetic mean to
estimate $m^{*}$.

######  Remark 2.2.

In the case where the sequence $\\{\epsilon_{t}\\}_{t\in\mathbb{N}}$ is not
Gaussian, and thus for $t\in\mathbb{N}$ the random variable $X_{t}$ has
probability density function $x\mapsto p(\cdot-m_{t})$ for some non negative
$p$ with $\int_{\mathbb{R}}p(x)dx=1$ and absolute maximum at the origin, we
can still run a stochastic gradient ascent algorithm to track the trend
$\\{m_{t}\\}_{t\in\mathbb{N}}$ as

$\displaystyle\hat{m}_{t+1}$
$\displaystyle=\hat{m}_{t}+\alpha\frac{d}{d\hat{m}}\ln
p(X_{t}-\hat{m})\Big{|}_{\hat{m}=\hat{m}_{t}}.$

Now, by an application of the Mean Value Theorem we can write

$\displaystyle\hat{m}_{t+1}$
$\displaystyle=\hat{m}_{t}+\alpha\frac{d}{d\hat{m}}\ln
p(X_{t}-\hat{m})\Big{|}_{\hat{m}=\hat{m}_{t}}$
$\displaystyle=\hat{m}_{t}+\alpha\frac{d}{d\hat{m}}\ln
p(X_{t}-\hat{m})\Big{|}_{\hat{m}=X_{t}}+\alpha\frac{d^{2}}{d\hat{m}^{2}}\ln
p(X_{t}-\hat{m})\Big{|}_{\hat{m}=\xi_{t}}(\hat{m}_{t}-X_{t})$
$\displaystyle=\hat{m}_{t}+\alpha\frac{d^{2}}{d\hat{m}^{2}}\ln
p(X_{t}-\hat{m})\Big{|}_{\hat{m}=\xi_{t}}(\hat{m}_{t}-X_{t});$ (2.6)

here we have utilized the fact that $X_{t}$ is the maximum likelihood
estimator of $m_{t}^{*}$ while $\xi_{t}$ belongs to the segment
$[X_{t},\hat{m}_{t}]$. If classical conditions to prove convergence of
gradient ascent apply (see for instance Polyak, (1987)), i.e. the function
$\hat{m}\rightarrow-\ln p(x-\hat{m})$ is strongly convex with convexity
constant $\ell$ and has Lipschitz continuous derivative with constant $L$
(both constants $\ell,L$ being independent of $x$), then we can bound the
second derivative as $\ell\leq-\frac{d^{2}}{d\hat{m}^{2}}\ln
p(X_{t}-\hat{m})\Big{|}_{\hat{m}=\xi_{t}}\leq L$. Therefore, replacing
$-\frac{d^{2}}{d\hat{m}^{2}}\ln p(X_{t}-\hat{m})\Big{|}_{\hat{m}=\xi_{t}}$
with an appropriately chosen constant $\rho\in[\ell,L]$ one reduces equation
(2.2) to

$\displaystyle\hat{m}_{t+1}=\hat{m}_{t}+\alpha\rho(X_{t}-\hat{m}_{t}),$

that, up to a reparametrization of the learning rate, coincides with (2.2).
This remark suggests that viewing the SES procedure as a stochastic gradient
ascent algorithm can be appropriate even outside the Gaussian case.

######  Remark 2.3.

Equation (2.2) may also be viewed as a time-varying stochastic gradient
descent algorithm used to minimize the quadratic cost functions

$\displaystyle\hat{m}\mapsto\frac{1}{2}\mathbb{E}[(\hat{m}-X_{t})^{2}],\quad
t\in\mathbb{N}$

where the gradient of the objective function is replaced by its random
selection $(\hat{m}_{t}-X_{t})$. These objective functions will for each time
$t$ achieve their minimum at the desired $m_{t}^{*}=\mathbb{E}[X_{t}]$. Under
these lens SES may be understood as a time varying M-estimator, Godambe,
(1991), Hayashi, (2011), obviating the necessity for an a priori assumption
regarding the Gaussian distribution of the observations.

The aim of the present paper is to prove novel quantitative estimates for the
performance of SES (2.2) by utilizing techniques from the optimization
literature. We will show that, under only two assumptions, SES tracks the
trend $\\{m_{t}^{*}\\}_{t\in\mathbb{N}}$ of a trend-stationary stochastic
process $\\{X_{t}\\}_{t\in\mathbb{N}}$ up to a neighborhood. Our result
provides novel insights on how to choose the smoothing parameter, and
showcases how SES performs well in a wide variety of settings shedding light
on the robustness properties of SES. A similar approach, where the
observations are independent, but their distribution belongs to a wider class
than the one studied here can be found in Lanconelli and Lauria, (2023),
Bernardi et al., (2023) ; there the authors prove that after a certain number
of iterations the stochastic gradient method, used to estimate a time-varying
parameter, is able to improve on the naive estimator given by maximizing the
single observation log-likelihood.

##  3 Assumptions and statement of the main result

We now collect the assumptions needed to prove our main theorem.

######  Assumption 3.1 (Trend-stationarity of the observations).

The stochastic process $\\{X_{t}\\}_{t\in\mathbb{N}}$ is trend-stationary with

$\displaystyle X_{t}=m_{t}^{\star}+\epsilon_{t},\quad t\in\mathbb{N};$ (3.1)

the trend $\\{m_{t}^{\star}\\}_{t\in\mathbb{N}}$ is a sequence of real numbers
while $\\{\epsilon_{t}\\}_{t\in\mathbb{N}}$ is a weakly stationary sequence
with $\mathbb{E}[\epsilon_{t}]=0$ and
$\mathtt{cov}(\epsilon_{t},\epsilon_{s})\coloneqq\gamma(t,s)=\gamma(t-s)$ for
all $t,s\in\mathbb{N}$; the function $\gamma:\mathbb{Z}\rightarrow\mathbb{R}$
is even and positive definite.

The next assumption concerns the evolution of the trend
$\\{m_{t}^{\star}\\}_{t\in\mathbb{N}}$.

######  Assumption 3.2 (Lipschitz continuity of the trend).

There exists a positive constant $K$ such that

$\displaystyle|m_{t+1}^{\star}-m_{t}^{\star}|\leq K\quad\mbox{ for all
$t\in\mathbb{N}$}.$

Assumption 3.2 is canonical in the time-varying optimization literature, see
for example Simonetto et al., (2020), Cao et al., (2019), Wilson et al.,
(2019) and Bernardi et al., (2023).: a control on the behavior of the sequence
of optima is needed to be able to shadow it.

We can now state our main theorem.

######  Theorem 3.3.

Let Assumptions 3.1 and 3.2 hold. Then, running equation

$\displaystyle\begin{cases}\hat{m}_{t+1}=(1-\alpha)\hat{m}_{t}+\alpha
X_{t},\quad t\in\mathbb{N};\\\ \hat{m}_{1}=X_{1},\end{cases}$ (3.2)

with $\alpha\in]0,1[$ we obtain

$\displaystyle\limsup_{t\rightarrow\infty}\mathbb{E}[(\hat{m}_{t+1}-m_{t}^{\star})^{2}]\leq\frac{\alpha}{2-\alpha}\gamma(0)+\frac{2\alpha}{2-\alpha}\sum_{k\geq
1}\gamma(k)(1-\alpha)^{k}+\frac{(1-\alpha)^{2}}{\alpha^{2}}K^{2}.$ (3.3)

The proof of Theorem 3.3, presented in Section 5, ensues through the
application of methodologies conventionally employed in the optimization
literature for establishing the convergence of stochastic gradient algorithms.
Theorem 3.3 elucidates the conditions under which SES is poised to be
efficacious, thereby offering valuable insight regarding the potential utility
of employing SES within different applied settings. Moreover, the generality
of the conditions under which Theorem 3.3 holds explain the robustness
properties of SES; even in the case of model misspecification (when SES does
not represent the optimal estimator with respect to a certain data generating
process) it will still converge under the Lipschitz trend Assumption 3.2 to a
neighborhood of the true trend.
We also observe that as $\alpha$ approaches zero the first two terms on the
right-hand side of inequality (3.3) converges to zero, whereas the third term
diverges. This phenomenon arises due to the inadequacy of a small $\alpha$’s
to effectively capture the evolving dynamics of the sequence
$\\{m_{t}^{\star}\\}_{t\in\mathbb{N}}$. Consequently, selecting an $\alpha$
that diminishes with time, in accordance with the conventional approach in the
optimization literature dealing with static optima, proves to be less
efficacious in improving convergence.

######  Remark 3.4.

The right-hand side of inequality (3.3) clarifies the contribution of the
assumptions to the performance of the method. Given the learning rate $\alpha$
we have:

$\displaystyle\underbrace{\frac{\alpha}{2-\alpha}\gamma(0)}_{\text{Variance of
the
observations}}\quad+\quad\quad\underbrace{\frac{2\alpha}{2-\alpha}\sum_{k=1}^{\infty}\gamma(k)(1-\alpha)^{k}}_{\text{Correlation
structure}}\quad+\quad\underbrace{\frac{(1-\alpha)^{2}}{\alpha^{2}}K^{2}}_{\text{Dynamics
of the trend}}.$

The first term increases with the variance of the observations, the second one
is ruled by the covariances between observations at different times while the
third is due to the time evolution of the trend. When one possesses prior
knowledge regarding the covariance structure of the underlying process and the
temporal dynamics of the trend, the information can be effectively leveraged
to optimize the selection of a suitable value for the parameter $\alpha$.

##  4 Simulations

In this section we present simulations showcasing how SES converges to a
neighborhood of the trend $\\{m_{t}^{\star}\\}_{t\in\mathbb{N}}$ of a trend-
stationary stochastic process $\\{X_{t}\\}_{t\in\mathbb{N}}$: we consider the
cases where the stationary process $\\{\epsilon_{t}\\}_{t\in\mathbb{N}}$ is
given by a moving avarage process $\mathtt{MA(1)}$ and an autoregressive model
$\mathtt{AR(1)}$.

###  4.1 The moving average case

We simulate observations of the form

$\displaystyle X_{t}=m_{t}^{\star}+\epsilon_{t},\quad t\in\mathbb{N},$

where $t\mapsto m_{t}^{\star}$ evolves linearly and in a sinusoidal fashion
while $\\{\epsilon_{t}\\}_{t\in\mathbb{N}}$ is an $\mathtt{MA(1)}$ process
defined as

$\displaystyle\epsilon_{t}=\frac{\eta_{t}+a\eta_{t-1}}{\sqrt{1+a^{2}}},\quad
t\in\mathbb{N}.$ (4.1)

Here, $a\in\mathbb{R}$ and the elements of the sequence
$\\{\eta_{t}\\}_{t\in\mathbb{N}}$ are independent Gaussian random variables
with zero mean and unit variance. We then run SES given by Equation (3.2),
starting from $\hat{m}_{0}=8$ and we showcase the tracking trajectory in
Figure 1.

(a)

(b)

Figure 1: The evolution of $\\{m_{t}^{\star}\\}_{t\in\mathbb{N}}$ in subfigure
1(a) is given by the equation $m_{t}^{\star}=m_{t-1}^{*}+0.1$, starting from
$m_{0}^{*}=2$, while $a=2$. The evolution of
$\\{m_{t}^{\star}\\}_{t\in\mathbb{N}}$ in subfigure 1(b) is given by the
equation $m_{t}^{\star}=\sin(\pi t/1000)$, starting from $t=0$, while $a=2$.
The SES in both subfigures is iterated $1000$ times with $\hat{m}_{0}=8$ and
$\alpha=0.1$.

(a)

(b)

Figure 2: The evolution of $\\{m_{t}^{\star}\\}_{t\in\mathbb{N}}$ in subfigure
2(a) is given by the equation $m_{t}^{\star}=m_{t-1}^{*}+0.1$, starting from
$m_{0}^{*}=2$, while $a=-0.4$. The evolution of
$\\{m_{t}^{\star}\\}_{t\in\mathbb{N}}$ in subfigure 2(b) is given by the
equation $m_{t}^{\star}=\sin(\pi t/1000)$, starting from $t=0$, while
$a=-0.4$. The SES in both subfigures is iterated $1000$ times with
$\hat{m}_{0}=8$ and $\alpha=0.1$.

The auto-covariance function of the stochastic process defined in (4.1) is

$\displaystyle\gamma(t)=\begin{cases}1,&\text{if $t=0$};\\\
\frac{a}{1+a^{2}},&\text{if $|t|=1$};\\\ 0,&\text{if $|t|\geq 1$};\end{cases}$

thus choosing $a<0$ we obtain a negative covariance that should aid
convergence as implied by Theorem 3.3. In Figure 2 we run the SES with
$a=-0.4$. Comparing Figures 1 and 2 we notice that the neighborhood to which
SES converges is smaller in the case of negative covariance, as expected.

###  4.2 The autoregressive case

We simulate observations of the form

$\displaystyle X_{t}=m_{t}^{\star}+\epsilon_{t},\quad t\in\mathbb{N},$

where $t\mapsto m_{t}^{\star}$ evolves linearly and in a sinusoidal fashion
while $\\{\epsilon_{t}\\}_{t\in\mathbb{N}}$ is an $\mathtt{AR(1)}$ process
defined as

$\displaystyle\epsilon_{t+1}=\theta\epsilon_{t}+\eta_{t},\quad t\in\mathbb{N}$
(4.2)

where $\theta\in]0,1[$ and the sequence $\\{\eta_{t}\\}_{t\in\mathbb{N}}$ is
made of independent Gaussian random variables with mean zero and unit
variance. The auto-covariance function of the stochastic process defined in
(4.2) is

$\gamma(t)=\theta^{|t|}\gamma(0),\quad t\in\mathbb{N}.$

In Figure 3 we showcase the results.

(a)

(b)

Figure 3:  The evolution of $\\{m_{t}^{\star}\\}_{t\in\mathbb{N}}$ in
subfigure 3(a) is given by the equation $m_{t}^{\star}=0.1+0.01t$, starting
from $t=0$, while $\theta=0.2$. The evolution of
$\\{m_{t}^{\star}\\}_{t\in\mathbb{N}}$ in subfigure 3(b) is given by the
equation $m_{t}^{\star}=\sin(\pi t/1000)$, starting from $t=0$, while
$\theta=0.2$. The SES is iterated $1000$ times with $\hat{m}_{0}=8$ and
$\alpha=0.1$.

##  5 Proof of the main result

To ease the notation we set $\beta\coloneqq 1-\alpha$ and notice that equation
(3.2) admits the solution

$\displaystyle\hat{m}_{t}=\beta^{t-1}\hat{m}_{1}+\alpha\sum_{j=1}^{t-1}\beta^{t-1-j}X_{j},\quad
t\in\mathbb{N}.$ (5.1)

On the other hand, subtracting $m_{t}^{\star}$ from both sides of equation
(3.2) we get

$\displaystyle\hat{m}_{t+1}-m_{t}^{\star}=\beta(\hat{m}_{t}-m_{t}^{\star})+\alpha(X_{t}-m_{t}^{\star}),$
(5.2)

and taking squares we obtain

$\displaystyle(\hat{m}_{t+1}-m_{t}^{\star})^{2}=\beta^{2}(\hat{m}_{t}-m_{t}^{\star})^{2}+2\alpha\beta(\hat{m}_{t}-m_{t}^{\star})(X_{t}-m_{t}^{\star})+\alpha^{2}(X_{t}-m_{t}^{\star})^{2}.$
(5.3)

We now focus on the product $(\hat{m}_{t}-m_{t}^{\star})(X_{t}-m_{t}^{\star})$
and rewrite it with the help of (5.1) as

$\displaystyle(\hat{m}_{t}-m_{t}^{\star})(X_{t}-m_{t}^{\star})=$
$\displaystyle\hat{m}_{t}(X_{t}-m_{t}^{\star})-m_{t}^{\star}(X_{t}-m_{t}^{\star})$
$\displaystyle=$
$\displaystyle\left(\beta^{t-1}\hat{m}_{1}+\alpha\sum_{j=1}^{t-1}\beta^{t-1-j}X_{j}\right)(X_{t}-m_{t}^{\star})-m_{t}^{\star}(X_{t}-m_{t}^{\star})$
$\displaystyle=$
$\displaystyle\beta^{t-1}\hat{m}_{1}(X_{t}-m_{t}^{\star})+\alpha\sum_{j=1}^{t-1}\beta^{t-1-j}(X_{j}-m_{j}^{\star})(X_{t}-m_{t}^{\star})$
$\displaystyle+\alpha\sum_{j=1}^{t-1}\beta^{t-1-j}m_{j}^{\star}(X_{t}-m_{t}^{\star})-m_{t}^{\star}(X_{t}-m_{t}^{\star}).$
(5.4)

A substitution of the last member of (5) into equation (5.3) gives

$\displaystyle(\hat{m}_{t+1}-m_{t}^{\star})^{2}=$
$\displaystyle\beta^{2}(\hat{m}_{t}-m_{t}^{\star})^{2}+2\alpha\beta^{t}\hat{m}_{1}(X_{t}-m_{t}^{\star})$
$\displaystyle+2\alpha^{2}\beta\sum_{j=1}^{t-1}\beta^{t-1-j}(X_{j}-m_{j}^{\star})(X_{t}-m_{t}^{\star})$
$\displaystyle+2\alpha^{2}\beta\sum_{j=1}^{t-1}\beta^{t-1-j}m_{j}^{\star}(X_{t}-m_{t}^{\star})$
$\displaystyle-2\alpha\beta m_{t}^{\star}(X_{t}-m_{t}^{\star})$
$\displaystyle+\alpha^{2}(X_{t}-m_{t}^{\star})^{2};$

if we now take the expectation of both sides above, recalling that
$\mathbb{E}[X_{t}]=m_{t}^{\star}$ and $\mathtt{cov}(X_{t},X_{s})=\gamma(t-s)$
for all $t,s\in\mathbb{N}$, we get

$\displaystyle\mathbb{E}[(\hat{m}_{t+1}-m_{t}^{\star})^{2}]=\beta^{2}\mathbb{E}[(\hat{m}_{t}-m_{t}^{\star})^{2}]+2\alpha^{2}\sum_{j=1}^{t-1}\beta^{t-j}\gamma(t-j)+\alpha^{2}\gamma(0).$

or equivalently,

$\displaystyle\mathbb{E}[(\hat{m}_{t+1}-m_{t}^{\star})^{2}]=\beta^{2}\mathbb{E}[(\hat{m}_{t}-m_{t}^{\star})^{2}]+2\alpha^{2}\sum_{k=0}^{t-1}\beta^{k}\gamma(k)-\alpha^{2}\gamma(0).$
(5.5)

Here we added the term corresponding to $j=t$ and renamed $t-j$ as $k$.

The next step consists in rewriting (5.5) as a recursive equation for
$t\mapsto\mathbb{E}[(\hat{m}_{t+1}-m_{t}^{\star})^{2}]$. First of all, we
observe that

$\displaystyle\mathbb{E}[(\hat{m}_{t}-m_{t}^{\star})^{2}]$
$\displaystyle=\mathbb{E}[(\hat{m}_{t}-m_{t-1}^{*}+m_{t-1}^{*}-m_{t}^{\star})^{2}]$
$\displaystyle=\mathbb{E}[(\hat{m}_{t}-m_{t-1}^{*})^{2}]+(m_{t}^{\star}-m_{t-1}^{*})^{2}-2(m_{t}^{\star}-m_{t-1}^{*})\mathbb{E}[\hat{m}_{t}-m_{t-1}^{*}];$

thus, utilizing the notation

$\displaystyle
D_{t+1}\coloneqq\mathbb{E}[(\hat{m}_{t+1}-m_{t}^{\star})^{2}],\quad
v_{t+1}\coloneqq\mathbb{E}[\hat{m}_{t+1}-m_{t}^{\star}]\quad\mbox{ and }\quad
K_{t}\coloneqq m_{t}^{\star}-m_{t-1}^{*}$

we can reformulate equation (5.5) as

$\displaystyle
D_{t+1}=\beta^{2}(D_{t}+K_{t}^{2}-2K_{t}v_{t})+2\alpha^{2}\sum_{k=0}^{t-1}\beta^{k}\gamma(k)-\alpha^{2}\gamma(0).$
(5.6)

Notice that exploiting (5.2) one can easily see that the sequence
$\\{v_{t}\\}_{t\in\mathbb{N}}$ solves the recursive equation

$\displaystyle\begin{cases}v_{t+1}=\beta v_{t}-\beta K_{t},\quad
t\in\mathbb{N};\\\ v_{1}=0;\end{cases}$ (5.7)

where we have set $m_{0}^{\star}=m_{1}^{\star}$ to obtain

$\displaystyle
v_{1}=\mathbb{E}[\hat{m}_{1}-m_{0}^{\star}]=\mathbb{E}[X_{1}-m_{1}^{\star}]=0.$

In fact,

$\displaystyle\hat{m}_{t+1}-m_{t}^{\star}$
$\displaystyle=\beta(\hat{m}_{t}-m_{t}^{\star})+\alpha(X_{t}-m^{*}_{t})$
$\displaystyle=\beta(\hat{m}_{t}-m_{t-1}^{*}+m_{t-1}^{*}-m_{t}^{\star})+\alpha(X_{t}-m^{*}_{t}),$

and upon taking expectations of both sides we obtain equation (5.7).
Therefore, the solution to (5.7) takes the form

$\displaystyle v_{t}=-\sum_{h=1}^{t-1}\beta^{t-h}K_{h},\quad t\in\mathbb{N}$

and substituting this expression in (5.6) gives

$\displaystyle D_{t+1}$
$\displaystyle=\beta^{2}\left[D_{t}+K_{t}^{2}+2K_{t}\sum_{h=1}^{t-1}\beta^{t-h}K_{h}\right]+2\alpha^{2}\sum_{k=0}^{t-1}\beta^{k}\gamma(k)-\alpha^{2}\gamma(0)$
$\displaystyle=\beta^{2}D_{t}+\beta^{2}\left[\left(K_{t}+\sum_{h=1}^{t-1}\beta^{t-h}K_{h}\right)^{2}-\left(\sum_{h=1}^{t-1}\beta^{t-h}K_{h}\right)^{2}\right]+2\alpha^{2}\sum_{k=0}^{t-1}\beta^{k}\gamma(k)-\alpha^{2}\gamma(0)$
$\displaystyle=\beta^{2}D_{t}+\beta^{2+2t}\left[\left(\beta^{-t}K_{t}+\sum_{h=1}^{t-1}\beta^{-h}K_{h}\right)^{2}-\left(\sum_{h=1}^{t-1}\beta^{-h}K_{h}\right)^{2}\right]+2\alpha^{2}\sum_{k=0}^{t-1}\beta^{k}\gamma(k)-\alpha^{2}\gamma(0)$
$\displaystyle=\beta^{2}D_{t}+\beta^{2+2t}\left[c_{t}^{2}-c_{t-1}^{2}\right]+2\alpha^{2}\sum_{k=0}^{t-1}\beta^{k}\gamma(k)-\alpha^{2}\gamma(0),$

where we have set

$\displaystyle
c_{t}:=\beta^{-t}K_{t}+\sum_{h=1}^{t-1}\beta^{-h}K_{h}=\sum_{h=1}^{t}\beta^{-h}K_{h},\quad
t\in\mathbb{N}.$

The preceding computation shows that $\\{D_{t}\\}_{t\in\mathbb{N}}$ solves

$\displaystyle\begin{cases}D_{t+1}=\beta^{2}D_{t}+\beta^{2+2t}\left[c_{t}^{2}-c_{t-1}^{2}\right]+2\alpha^{2}\sum_{k=0}^{t-1}\beta^{k}\gamma(k)-\alpha^{2}\gamma(0),\quad
t\in\mathbb{N};\\\ D_{1}=0,\end{cases}$

whose solution can be represented as

$\displaystyle
D_{t}=\beta^{2t}c_{t-1}^{2}+\alpha^{2}\sum_{i=0}^{t-1}\beta^{2i}\left(2\sum_{k=0}^{t-i-2}\beta^{k}\gamma(k)-\gamma(0)\right),\quad
t\in\mathbb{N},$

or equivalently,

$\displaystyle
D_{t}=\beta^{2t}c_{t-1}^{2}+2\alpha^{2}\sum_{k=0}^{t-2}\gamma(k)\sum_{i=0}^{t-2-k}\beta^{2i+k}-\alpha^{2}\gamma(0)\sum_{i=0}^{t-1}\beta^{2i}.$
(5.8)

The last step of the proof consists in obtaining an upper bound for

$\displaystyle\limsup_{t\to+\infty}\mathbb{E}[(\hat{m}_{t+1}-m_{t}^{\star})^{2}]=\limsup_{t\to+\infty}D_{t+1};$

to this aim we now study the asymptotic behavior of the terms appearing in the
right hand side of (5.8). Recalling that
$c_{t}:=\sum_{h=1}^{t}\beta^{-h}K_{h}$ and $K_{t}:=m_{t}^{\star}-m_{t-1}^{*}$,
with the help of Assumption 3.2 we can write

$\displaystyle|c_{t}|\leq
K\sum_{h=1}^{t}\beta^{-h}=K\left(\frac{1-\beta^{-t-1}}{1-\beta^{-1}}-1\right),$

and hence

$\displaystyle\limsup_{t\to+\infty}\beta^{2(t+1)}c_{t}^{2}\leq\limsup_{t\to+\infty}K^{2}\left(\frac{\beta^{t+1}-1}{1-\beta^{-1}}-\beta^{t+1}\right)^{2}=K^{2}\frac{\beta^{2}}{\alpha^{2}}.$

A simple algebraic manipulation on the second term in (5.8) gives

$\displaystyle
2\alpha^{2}\sum_{k=0}^{t-2}\gamma(k)\sum_{i=0}^{t-2-k}\beta^{2i+k}=\frac{2\alpha}{2-\alpha}\left[\sum_{k=0}^{t-2}\gamma(k)\beta^{k}-\beta^{2t-2}\sum_{k=0}^{t-2}\gamma(k)\beta^{-k}\right];$

notice that

$\displaystyle\beta^{2t-2}\sum_{k=0}^{t-2}\gamma(k)\beta^{-k}=\beta^{t}\sum_{k=0}^{t-2}\gamma(k)\beta^{t-2-k}=\beta^{t}\sum_{j=0}^{t-2}\gamma(t-2-j)\beta^{j},$

and hence from the Cauchy-Schwarz inequality we can conclude that

$\displaystyle\limsup_{t\to+\infty}\left|\beta^{2t-2}\sum_{k=0}^{t-2}\gamma(k)\beta^{-k}\right|=$
$\displaystyle\limsup_{t\to+\infty}\left|\beta^{t}\sum_{j=0}^{t-2}\gamma(t-2-j)\beta^{j}\right|$
$\displaystyle\leq$
$\displaystyle\limsup_{t\to+\infty}\beta^{t}\sum_{j=0}^{t-2}|\gamma(t-2-j)|\beta^{j}$
$\displaystyle\leq$
$\displaystyle\gamma(0)\limsup_{t\to+\infty}\beta^{t}\sum_{j=0}^{t-2}\beta^{j}=0.$

Therefore, for the second term in (5.8) we can write

$\displaystyle\limsup_{t\to+\infty}2\alpha^{2}\sum_{k=0}^{t-2}\gamma(k)\sum_{i=0}^{t-2-k}\beta^{2i+k}=\frac{2\alpha}{2-\alpha}\sum_{k\geq
0}\gamma(k)\beta^{k}.$

Thus we may conclude that

$\displaystyle\limsup_{t\to+\infty}\mathbb{E}[(\hat{m}_{t+1}-m_{t}^{\star})^{2}]\leq\frac{\alpha}{2-\alpha}\gamma(0)+\frac{2\alpha}{2-\alpha}\sum_{k\geq
1}\gamma(k)\beta^{k}+\frac{\beta^{2}}{\alpha^{2}}K^{2}.$

## References

  * Bernardi et al., (2023) Bernardi, E., Lanconelli, A., and Lauria, C. S. (2023).  Online learning via maximum likelihood.  [Preprint].
  * Bossons, (1966) Bossons, J. (1966).  The effects of parameter misspecification and non-stationarity on the applicability of adaptive forecasts.  Management Science, 12(9):659–669.
  * Brockwell and Davis, (2009) Brockwell, P. J. and Davis, R. A. (2009).  Time series: theory and methods.  Springer science & business media.
  * Brown, (1956) Brown, R. G. (1956).  Exponential smoothing for predicting demand.  Little.
  * Brown, (1959) Brown, R. G. (1959).  Statistical forecasting for inventory control.  (No Title).
  * Brown, (1963) Brown, R. G. (1963).  Smoothing, Forecasting and Prediction of Discrete Time Series.  Englewood Cliffs.
  * Bubeck et al., (2008) Bubeck, S., Stoltz, G., Szepesvári, C., and Munos, R. (2008).  Online optimization in x-armed bandits.  In Koller, D., Schuurmans, D., Bengio, Y., and Bottou, L., editors, Advances in Neural Information Processing Systems, volume 21. Curran Associates, Inc.
  * Cao et al., (2019) Cao, X., Zhang, J., and Poor, H. V. (2019).  On the time-varying distributions of online stochastic optimization.  In 2019 American Control Conference (ACC), pages 1494–1500.
  * Cohen, (1963) Cohen, G. D. (1963).  A note on exponential smoothing and autocorrelated inputs.  Operations research, 11(3):361–367.
  * Cox, (1961) Cox, D. R. (1961).  Prediction by exponentially weighted moving averages and related methods.  Journal of the Royal Statistical Society: Series B (Methodological), 23(2):414–422.
  * Gardner Jr, (2006) Gardner Jr, E. S. (2006).  Exponential smoothing: The state of the art—part ii.  International journal of forecasting, 22(4):637–666.
  * Godambe, (1991) Godambe, V. P. (1991).  Estimating functions.  Oxford University Press.
  * Gross and Craig, (1974) Gross, D. and Craig, R. J. (1974).  A comparison of maximum likelihood, exponential smoothing and bayes forecasting procedures in inventory modelling.  International Journal of Production Research, 12(5):607–622.
  * Hayashi, (2011) Hayashi, F. (2011).  Econometrics.  Princeton University Press.
  * Hyndman, (2001) Hyndman, R. (2001).  It’s time to move from what to why’.  International Journal of Forecasting, 17(1):567–570.
  * Hyndman et al., (2008) Hyndman, R., Koehler, A. B., Ord, J. K., and Snyder, R. D. (2008).  Forecasting with exponential smoothing: the state space approach.  Springer Science & Business Media.
  * Hyndman et al., (2002) Hyndman, R. J., Koehler, A. B., Snyder, R. D., and Grose, S. (2002).  A state space framework for automatic forecasting using exponential smoothing methods.  International Journal of forecasting, 18(3):439–454.
  * Lanconelli and Lauria, (2023) Lanconelli, A. and Lauria, C. S. (2023).  Maximum likelihood with a time varying parameter.  Statistical Papers.
  * Makridakis et al., (1982) Makridakis, S., Andersen, A., Carbone, R., Fildes, R., Hibon, M., Lewandowski, R., Newton, J., Parzen, E., and Winkler, R. (1982).  The accuracy of extrapolation (time series) methods: Results of a forecasting competition.  Journal of forecasting, 1(2):111–153.
  * Muth, (1960) Muth, J. F. (1960).  Optimal properties of exponentially weighted forecasts.  Journal of the american statistical association, 55(290):299–306.
  * Ord et al., (1997) Ord, J. K., Koehler, A. B., and Snyder, R. D. (1997).  Estimation and prediction for a class of dynamic nonlinear statistical models.  Journal of the American Statistical Association, 92(440):1621–1629.
  * Polyak, (1987) Polyak, B. T. (1987).  Introduction to Optimization (Translations Series in Mathematics and Engineering).  Optimization Software.
  * Popkov, (2005) Popkov, A. Y. (2005).  Gradient methods for nonstationary unconstrained optimization problems.  Automation and Remote Control, 66(6):883–891.
  * Robbins and Monro, (1951) Robbins, H. and Monro, S. (1951).  A stochastic approximation method.  The Annals of Mathematical Statistics, 22(3):400–407.
  * Simonetto et al., (2020) Simonetto, A., Dall’Anese, E., Paternain, S., Leus, G., and Giannakis, G. B. (2020).  Time-varying convex optimization: Time-structured algorithms and applications.  Proceedings of the IEEE, 108(11):2032–2048.
  * Simonetto and Dall’Anese, (2017) Simonetto, A. and Dall’Anese, E. (2017).  Prediction-correction algorithms for time-varying constrained optimization.  IEEE Transactions on Signal Processing, 65(20):5481–5494.
  * Simonetto et al., (2016) Simonetto, A., Mokhtari, A., Koppel, A., Leus, G., and Ribeiro, A. (2016).  A class of prediction-correction methods for time-varying convex optimization.  IEEE Transactions on Signal Processing, 64(17):4576–4591.
  * Taylor, (2003) Taylor, J. W. (2003).  Exponential smoothing with a damped multiplicative trend.  International journal of Forecasting, 19(4):715–725.
  * Tiao and Xu, (1993) Tiao, G. C. and Xu, D. (1993).  Robustness of maximum likelihood estimates for multi-step predictions: the exponential smoothing case.  Biometrika, 80(3):623–641.
  * Wilson et al., (2019) Wilson, C., Veeravalli, V. V., and Nedić, A. (2019).  Adaptive sequential stochastic optimization.  IEEE Transactions on Automatic Control, 64(2):496–509.
  * Winters, (1960) Winters, P. R. (1960).  Forecasting sales by exponentially weighted moving averages.  Management science, 6(3):324–342.
  * Zinkevich, (2003) Zinkevich, M. (2003).  Online convex programming and generalized infinitesimal gradient ascent.  In Proceedings of the Twentieth International Conference on International Conference on Machine Learning, ICML’03, page 928–935. AAAI Press.