These authors contributed equally to this work.

[1,2]Francesca Ferlaino These authors contributed equally to this work.

[3]Massimo Mannarelli These authors contributed equally to this work.

These authors contributed equally to this work.

These authors contributed equally to this work.

1]Universität Innsbruck, Fakultät für Mathematik, Informatik und Physik,
Institut für Experimentalphysik, 6020 Innsbruck, Austria

2]Institut für Quantenoptik und Quanteninformation, Osterreichische Akademie
der Wissenschaften, Technikerstraße 21a, Innsbruck, 6020, Austria

3]Laboratori Nazionali del Gran Sasso, INFN, Via G.Acitelli, 22, Assergi (AQ),
I-67100, Italy

4]Gran Sasso Science Institute, Viale Francesco Crispi, 7, L’Aquila, I-67100,
Italy

# Exploring pulsar glitches with dipolar supersolids

Thomas Bland<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Elena Poli<EMAIL_ADDRESS>Silvia
Trabucco<EMAIL_ADDRESS>[  [  [  [

###### Abstract

Glitches are sudden spin-up events that interrupt the gradual spin-down of
rotating neutron stars. They are believed to arise from the rapid unpinning of
vortices in the neutron star inner crust. The analogy between the inner crust
of neutron stars and dipolar supersolids allows to investigate glitches.
Employing such analogy, we numerically analyze the vortex trapping mechanism
and how the matter density distribution influences glitches. These results
pave the way for the quantum simulation of celestial bodies in laboratories.

###### keywords:

Neutron stars, dipolar supersolids

##  1 Introduction

In physics, analogies are extremely powerful tools. They give the opportunity
to look at physical phenomena from different perspectives, favoring
connections between very disparate research fields. In some cases, appropriate
analogies can be used to explore phenomena happening in seemingly unreachable
objects, such as neutron stars (NSs). In recent work, we established an
intriguing analogy between the inner crust of NSs and ultracold dipolar
supersolids and used it to investigate the anomalies in the rotation frequency
of NSs, known as glitches [1].

Neutron stars are among the most mysterious and extreme objects populating our
universe. Their observed mass $\sim 1-2M_{\odot}$, where $M_{\odot}$ is the
solar mass, is compressed by the gravitational attraction into a radius of
about $10$ km. They are believed to form after the gravitational collapse of
massive progenitor stars in so-called supernova type II events [2, 3]. After a
very short time period, on the order of seconds, they cool down and reach a
stable configuration with gravitational pull balanced by the combined effect
of degenerate Fermi pressure and repulsive short-range strong interaction.
Inside NSs the matter density increases with radial depth, determining an
onion-like equilibrium structure [4, 5, 6, 7, 8, 9, 10, 11]. The outer crust
is a solid material consisting of a lattice of neutron-rich nuclei. As the
density increases in the inner crust, nuclei are packed so tightly that
neutrons start dripping out, overlapping with each other, and forming a
superfluid background. The neutron superfluid density distribution is not
uniform but partially retains the same crystalline order of the underlying
protons [12]. From this perspective, the inner crust of a NS is simultaneously
solid and superfluid. Finally, the core of NSs consists of a homogeneous
superfluid of neutrons, protons and electrons. Muons, heavy hadrons and more
exotic particles may be present as well [2, 3, 4].

In the majority of cases, NSs are observed as pulsars: regularly rotating
emitters of electromagnetic radiation. The first documented signs of these
elusive celestial bodies were periodic radio frequency flashes discovered in
1967, resembling a galactic lighthouse [13, 14, 15, 16], so perfect that some
interpreted it as an attempt at alien communication. The lighthouse effect
results from the misalignment between the rotation and magnetization axes
leading to a secular loss of rotational energy with a corresponding slow
decrease of the pulsar rotation frequency, $\Omega$. Apart from this steady
spinning down, it has been observed that the rotation frequency of pulsars
occasionally shows anomalous jumps–called “glitches”–in the form of an abrupt
speed-up of the pulsar rotation followed by a slow relaxation close to its
original value. It is precisely the observations of such pulsar glitches that
have provided the first evidence of superfluidity in neutron-star interiors
[17, 18, 19, 20, 21, 16].

Glitches can be seen as the consequence of the trapping and releasing of
vortices within a crystalline structure in the interior of NSs. However,
unlike superfluids observed on Earth, which contain tens or hundreds of
vortices, NSs are expected to generate up to $\sim$1017 vortices, posing a
nontrivial question regarding how the results obtained with few vortex systems
could be scaled. Due to the underlying crystalline structure, superfluid
vortices cannot move freely: they are forced to position themselves between
the crystal sites [22, 23, 24, 25, 26]. When the radiation emission slows down
the outer crust, the vortices trapped in the inner crust fix their speed, and
they do not allow the neutron superfluid component to slow down in parallel
with the outer crust and any stellar component that is electromagnetically
tightly coupled. Eventually, this unbalanced situation cannot be maintained;
an array of vortices escapes from the inner crust, transferring angular
momentum to the outer crust. Then, the outer crust spins up, resulting in a
glitch. Although the sketched mechanism is plausible, there is no direct
evidence that it is the right one.

In [1] we explored whether such phenomenon can be reproduced using ultracold
atoms. The field of ultracold quantum gases has proven to be an ideal tool for
simulating various quantum phenomena, as it allows exceptionally precise
experimental control over external conditions and internal interactions [27,
28, 29, 30, 31, 32, 33, 34, 35, 36]. In this field, an object exhibiting both
superfluid and crystalline properties, known as a “supersolid” [37], is well-
known [38, 39, 40, 41, 42, 43, 44]. Recently, supersolids were realized in
experiments with ultracold dipolar atoms [40, 41, 42], behaving like small
magnets. Atoms such as erbium and dysprosium, when cooled to temperatures near
absolute zero, organize into a liquid with both a crystalline structure and
superfluid properties. This first experimental observation occurred
simultaneously in 2019 in three different laboratories in Innsbruck, Pisa, and
Stuttgart. The supersolid phase was observed with crystallization in 2D [43,
44], and recently quantum vortices were observed in dipolar superfluids [45]
using magnetostirring. The same technique was employed to produce vortices in
supersolids [46]. These results indicate that we might soon expect the
experimental observation of glitches in rotating ultracold atoms.

The present paper is organized as follows. In Sec. 2 we briefly review how the
NS inner crust evolution can be simulated with ultracold atoms. The vortex
structure and dynamics are described in Sec. 3 employing the so-called
imprinting procedure. We draw our conclusions in Sec. 4.

##  2 Methods

We consider an ultracold gas of 164Dy bosons confined in an optical trap.
Appropriately tuning the s-wave interaction $a_{s}$, it is possible to drive
the system into a supersolid phase [47]. Rotating 2D supersolids can host
quantized vortices [48, 49, 50, 46], thus allowing us to investigate the
vortex dynamics underlying pulsar glitches.

In the numerical simulation, we prepare an initial state rotating with
constant angular velocity, then we apply an external torque to mimic the
pulsar’s secular loss of angular velocity. The time evolution of the system is
determined by two coupled equations: the angular momentum balance equation,
taking into account that an external torque is applied to the system, and the
extended Gross-Pitaevskii equation, which determines the evolution of the
macroscopic wavefunction.

For both dipolar supersolids and NSs, the total angular momentum can be cast
as

$L_{\text{tot}}=L_{\text{s}}+L_{\text{vort}}\,,$ (1)

where $L_{\text{s}}$ is the solid component, and $L_{\text{vort}}$ is the sum
of the angular momenta of vortices. In supersolids, one has access to the
total angular momentum, as the expectation value of the system angular
momentum, and the solid-part angular momentum. Thus, we use the above
expression to obtain $L_{\text{vort}}$. Notice that $L_{\text{vort}}$ cannot
be numerically evaluated counting the number of vortices, as is typically done
in homogeneous superfluids, because the vortex angular momentum depends on its
position in the trap [51, 50]. The solid-part angular momentum is given by

$L_{\text{s}}=I_{\text{s}}\Omega\,,$ (2)

where $I_{\text{s}}$ is the solid moment of inertia. This quantity should not
be confused with the moment of inertia $I_{\text{mass}}$ determined by the
matter distribution. They differ because a supersolid does not in general
respond to an applied external torque as a rigid body, hence
$I_{\text{s}}/I_{\text{mass}}\leq 1$. The mass and supersolid moment of
inertia coincide only when all the atoms form droplets; in this case the whole
mass of the system rigidly responds to an external torque. We model the
$I_{\text{s}}$ component as

$I_{\text{s}}(t)=(1-f_{\text{NCRI}})I_{\text{mass}}(t)\,,$ (3)

where the non-classical rotational inertia coefficient, $f_{\text{NCRI}}$,
captures the reduced rotational response of the system [37]. For a homogeneous
superfluid $f_{\text{NCRI}}=1$, while $f_{\text{NCRI}}=0$ for a rigid body.
Assuming that this quantity is not strongly dependent on the rotation
frequency, we approximate

$f_{\text{NCRI}}=1-\frac{I_{\text{s,0}}}{I_{\text{mass,0}}}\,,$ (4)

where $I_{\text{s,0}}$ and $I_{\text{mass,0}}$ are the values extrapolated in
the limit of vanishing rotation [37].

In NSs, the torque originates from the electromagnetic emission of radiation
that tends to slowly spin down the star. Such an effect is mimicked in dipolar
supersolids by externally ramping down the trap rotation frequency. The
angular momentum evolution of both NSs and supersolids can then be written as

$\dot{L}_{\text{s}}=-N_{\text{em}}-\dot{L}_{\text{vort}}\,,$ (5)

where $N_{\text{em}}$ is the external torque and we used the angular momentum
decomposition in Eq. (1). From Eq. (2) we obtain that

$\displaystyle
I_{\text{s}}\dot{\Omega}=-N_{\text{em}}-\dot{L}_{\text{vort}}-\dot{I}_{\text{s}}\Omega\,,$
(6)

where $\dot{I}_{\text{s}}$ characterizes the variation of the solid component
inertia. In NSs’ glitches, this final term is assumed to be negligible. In any
case, it cannot be directly linked to any astrophysical observable, so far. In
supersolids, we can trace the full system evolution, hence we evaluate it
using Eq. (3). Assuming constant $f_{\text{NCRI}}$,

$\dot{I}_{\text{s}}=(1-f_{\text{NCRI}})\dot{I}_{\text{mass}}(t)\,,$ (7)

where the mass moment of inertia for a rotation along the $\hat{z}$–axis can
be evaluated from the standard definition:

$I_{\text{mass}}=\langle x^{2}+y^{2}\rangle\,.$ (8)

The expectation value is computed using the macroscopic wavefunction
$\Psi(\mathbf{r},t)$: the solution of the extended Gross-Pitaevskii equation
(eGPE) [52, 53, 54, 55],

$\displaystyle i\hbar\frac{\partial\Psi}{\partial
t}=(1-i\gamma)\left[\mathcal{L}[\Psi;a_{s},a_{\text{dd}},\bm{\omega}]-\Omega\hat{L}_{z}\right]\Psi\,.$
(9)

where $\mathcal{L}$ is the eGPE operator and
$\hat{L}_{z}=x\hat{p}_{y}–y\hat{p}_{x}$ is the appropriate angular momentum
operator. The interparticle interactions depend on the s-wave scattering
length, $a_{s}$, and the dipole-dipole scattering length, $a_{\text{dd}}$, see
[1] for more details. The dipole-dipole interaction in 164Dy is such that
$a_{\text{dd}}\simeq 130.8a_{0}$, where $a_{0}$ is the Bohr radius.

The evolution is not unitary since a small dissipation parameter, $\gamma$, is
included. In this way, we can impart a rotation in the system when the trap is
being rotated. For $\gamma=0$ a supersolid in a circularly symmetric trap
would not respond to any change in the rotation frequency. We present here the
results of numerical simulations for $\gamma=0.05$, however changing this
value in a reasonable range does not strongly affect our results [1].
Dissipation implies that the total energy is not conserved, mimicking the fact
that in realistic systems part of the energy is transformed in heat. On the
other hand, the total atom number of particles is conserved, thus we assume
negligible particle leaks. We have taken constant
$N=\int\text{d}^{3}\textbf{r}|\Psi|^{2}=3\times 10^{5}$, which serves to
properly normalize the macroscopic wavefunction, and trap frequencies
$\omega_{r}=2\pi\times 50$ Hz and $\omega_{z}=2\pi\times 130$ Hz.

Figure 1: Frame of the three-dimensional simulation of the rotating supersolid
obtained with $a_{s}=91a_{0}$ and initial rotation frequency
$\Omega(0)=0.5\omega_{r}$, see the text for more details. The red clusters
indicate high number density. The combined effect of the dipole-dipole
interaction and s-wave repulsion favors the formation of superfluid clusters.
The black lines are the vortex cores. Vortices are trapped in between the high
density clusters. Close to the boundary, vortices are not straight lines: they
bend to follow the curvature of the optical trap.

The evolution of the system is obtained by recursively solving Eqs. (6) and
(9). We begin with solving the eGPE with initial conditions given in imaginary
time, at fixed $\Omega(0)=0.5\omega_{r}$. This provides the initial
wavefunction. Then, we evaluate $L_{\text{tot}}=\langle\hat{L}_{z}\rangle$ and
the superfluid angular momentum is obtained from Eq. (1), namely
$L_{\text{vort}}=L_{\text{tot}}-L_{\text{s}}$. From the mass distribution we
determine the mass momentum of inertia and the variation of the solid moment
of inertia is computed using Eq. (7). The updated rotation frequency is then
evaluated by means of Eq. (6) and it is fed in the eGPE, which is solved to
provide the updated wavefunction. Then the cycle starts over. In Fig. 1 we
report a frame of the three-dimensional simulation of the rotating supersolid.
The red clusters correspond to high number density, they result from the
interplay between the contact s-wave repulsion and the long range dipole-
dipole interaction. Vortices (black lines), are found in the low density
regions, between the clusters and close to the trap boundary.

Fig. 2 shows that with increasing values of $a_{s}$ the rotation frequency
jump during a glitch becomes bigger [1], while for $a_{s}=86a_{0}$, glitches
are not observed: the rotation frequency smoothly changes in time. The reason
of this behavior is that for $a_{s}=86a_{0}$ the superfluid component between
droplets almost completely vanishes. With increasing $a_{s}$ the interdroplet
superfluid increases and vortices carry a larger fraction of angular momentum.
When the trap spins down these vortices cannot adiabatically migrate towards
the trap surface: they are pinned by the crystal. The unpinning process is not
smooth: a vortex unpins only when the lag between the solid and the vortex
components is sufficiently large. As a consequence, during a glitch there is a
sudden and relatively large angular momentum ejection due to the unpinned
vortices, which is transferred to the droplets, see Eq. (6).

Figure 2: Supersolid glitches for different values of the s-wave scattering
length, $a_{s}$. The blue line is obtained with $a_{s}=86a_{0}$, the orange
line with $a_{s}=88a_{0}$, the green line with $a_{s}=91a_{0}$ and the red
line with $a_{s}=92a_{0}$.

##  3 Analyzing the vortex structure and dynamics

A semi-quantitative description of the vortex structure and dynamics can be
obtained by imprinting a vortex line in a specific position of a non-rotating
supersolid. This allows us to understand how a vortex modifies the matter
distribution, as well as to estimate the vortex energy cost. In the imprinting
procedure the total wavefunction is approximated multiplying the ground state
wavefunction $\Psi_{0}(\textbf{r})$ of a nonrotating supersolid by the ansatz
wave function

$\Phi_{v}(x,y;x_{0},y_{0})=\frac{\sqrt{(x-x_{0})^{2}+(y-y_{0})^{2}}}{\sqrt{(x-x_{0})^{2}+(y-y_{0})^{2}+\Lambda^{-2}}}e^{i\theta}\,,$
(10)

that imprints a vortex with phase $\theta=\arctan(y/x)$ on the top of the non-
rotating background. Here $\Lambda$ is a regulator [56] and ($x_{0},y_{0}$) is
the vortex center. Since $\Phi_{v}$ is independent of the $z$–coordinate, the
vortex extends as a straight line along the $z$–direction.

Actually, in rotating dipolar supersolids the phase profile is not an
azimuthal 2$\pi$ winding, but rather a complex pattern modified by the
underlying crystal structure [50]. Moreover, the finite size of the trap
determines the bending of vortex lines close to the trap boundary, see Fig. 1.
However, the simple ansatz that the total wavefunction is

$\Psi(\textbf{r};x_{0},y_{0})=\Psi_{0}(\textbf{r})\Phi_{v}(x,y;x_{0},y_{0})\,,$
(11)

with $\bm{r}=(x,y)$, captures the main features of the expected force field
felt by vortices in a rotating trap [1], in particular close to the trap
center where the vortex lines are straight. This is due to the fact, confirmed
by numerical simulations, that rotation does not strongly perturb the droplet
structure.

Figure 3: Energy cost of vortex seeding. Left panel: column density in
$\mu$m-2. High density regions correspond to superfluid clusters self-
organized in a nearly-triangular crystalline lattice. Right panel: energy cost
of imprinting a vortex to a non-rotating dipolar supersolid, in units of
$\hbar\omega_{z}$. The black lines show the $30\%$ (dashed) and $85\%$ (solid)
contours of the maximum column density. The energy peaks where the number
density is larger. Both plots are obtained with $N=3\times 10^{5}$ bosons,
trap frequency $\bm{\omega}=(\omega_{r},\omega_{z})=2\pi\times(50,130)$Hz, and
scattering lengths $a_{\text{dd}}=130.8a_{0}$ and $a_{s}=90a_{0}$, see the
main text for more details.

The way in which the matter distribution shapes the vortex structure can be
inferred from Fig. 3. The left panel shows the column density profile of the
nonrotating supersolid (obtained integrating the total density along the
$z$–direction). Peaks of the column density correspond to clusters of 164Dy
bosons. In the region between clusters the density is much smaller. The right
panel of Fig. 3 shows the energy cost imprinting a vortex at any given
position. It is obtained by evaluating the energy with the wavefunction given
in Eq. (11), over the full spatial range. Note that the vortex energy cost
peaks coincide with the number density peaks: vortices prefer to sit in low-
density regions.

Figure 4: Energy cost of imprinting a vortex in a nonrotating supersolid at
$x=0$ varying $y$ for three different values of $\Lambda$, see Eq. (10). The
peak at $x=0,y=0$, coincides with the number density absolute maximum: it is
the most unfavorable position for a vortex. The local maxima at $y\simeq
6\mu$m coincide with the density local maxima. In between the local density
maxima, for $\Lambda=2\,\mu$m-1 and $3\,\mu$m-1, there are two minima and a
local maximum. The local maximum corresponds to a saddle point, while the two
minima are the pinning sites. From the energy difference between the first
minimum and the saddle point, one can estimate the unpinning energy barrier
$\simeq 10^{-3}\hbar\omega_{z}$. For $\Lambda=1$ such energy barrier tends to
vanish.

In Fig. 4 we report the vortex energy cost at $x=0$ varying $y$, for different
values of $\Lambda$. The central peak coincides with the central cluster of
bosons. It is the absolute maximum: this is the least favorable position to
place a vortex. The other local maxima correspond to the nearest clusters,
while minima correspond to the pinning sites. Starting from the centre and
increasing $|y|$, the energy cost decreases until it reaches a local minimum.
In other words, a vortex trying to move from $x=0,y=0$, along the
$y$–direction feels a potential well at $y\simeq 1.8\,\mu$m, and then a small
barrier given by the difference between the energy at the local maximum at
$y\simeq 3\,\mu$m (actually a saddle point) and the energy at the local
minimum at $y\simeq 1.8\,\mu$m. Such energy barrier is of the order of
$10^{-3}\hbar\omega_{z}$. Note that this barrier tends to vanish for
$\Lambda=1\mu$m-1. In the real time simulation, we observe vortex pinning in
these local minima, which however may differ in numerical simulations with
systems of smaller size [35].

Regarding the vortex dynamics, the real time numerical simulations developed
in [1] allowed us to follow the vortex starting from the ground state. In a
rotating trap, all vortices are initially pinned in local minima of the
density. When the trap’s rotation velocity is ramped down, one or more
vortices may suddenly unpin along the more energetically favorable direction
[57]. Useful information on the vortex motion can be obtained by the
imprinting procedure. In particular, one can imprint a vortex in an
energetically unstable point and then follow its evolution. At distances from
the vortex core less than $\Lambda^{-1}$, imprinted vortices can be treated as
point-like objects [58]. Whether this is a good approximation is hard to
judge, since in supersolids the healing length is not well-defined, see
however the discussion in [49].

Figure 5: Streamlines of the vortex velocity field obtained using Eq. (13)
with the column number density (in units $\mu$m-2) obtained for a non-rotating
supersolid with $a_{s}=90a_{0}$. Left panel is for vanishing dissipation,
$\gamma=0$, the vortex velocity is tangent to the isodensity lines. Right
panel includes dissipation, with $\gamma=0.05$. In this case, there is a
radial velocity component that drives the vortex to the local minima of the
number density.

In any case, within such approximation, the vortex velocity follows from the
general expression valid in an inhomogeneous Bose-Einstein condensates [59,
60, 61]

$\bm{v}_{v}=\frac{\hbar}{m}\left\\{\nabla(\Phi-\gamma\log\sqrt{\rho})-\bm{\hat{z}}\times\nabla(\log\sqrt{\rho}+\gamma\Phi)\right\\}+\bm{\Omega}\times\bm{r}\,,$
(12)

that depends on the density and phase of the condensate in the absence of the
vortex. In principle, all contributions to the vortex velocity may be of
comparable importance [60]. However, in the supersolid ground state in the
absence of vortices, the phase is homogeneous, while space gradients of the
density are large. Thus, in the corotating frame we approximate

$\bm{v}_{v}\simeq-\frac{\hbar}{m}\left\\{\gamma\nabla\log\sqrt{\rho}+\bm{\hat{z}}\times\nabla\log\sqrt{\rho}\right\\}=\bm{v}_{\perp}+\bm{v}_{\parallel}\,,$
(13)

consisting of two components: $\bm{v}_{\perp}$ and $\bm{v}_{\parallel}$,
orthogonal and tangential to the isodensity surfaces, respectively. Note that
the $\bm{v}_{\perp}$ component, which pushes vortices away from high density
regions, is proportional to the dissipation parameter. In the absence of
dissipation the vortex cannot seek the most energetically favorable position,
its energy is frozen. Indeed, for $\gamma=0$ the system is conservative: from
Eq. (13), the vortex velocity components can be written as

$\dot{x}_{v}=-\frac{\hbar}{2m}\partial_{x}\log\rho\,,\quad\dot{y}_{v}=\frac{\hbar}{2m}\partial_{y}\log\rho\,,$
(14)

and thus $d\log\rho/dt=0$, meaning that along an orbit $\rho$ is constant.
Since isodensity lines are closed curves, vortices follow periodic stable
orbits. There are however exceptions. Orbits consisting of minima and maxima
of the density are just points. Moreover, orbits including a saddle point are
not periodic: they terminate at the saddle point. Regarding the periodic
orbits, we distinguish those around density maxima from those around density
minima. Including dissipation, see Eq. (13), the former develop an unstable
focus, while the latter have an asymptotically stable focus.

Figure 5 shows the streamlines obtained using the column number density,
$\rho(x,y)$, of a nonrotating supersolid. Different column densities
correspond to different colors while the arrows represent the vortex velocity.
For vanishing dissipation ($\gamma=0$), left panel of Fig. 5, the vortex
velocity is always tangent to the isodensity lines. Vortices close to the
droplet centre move following almost circular lines. They rotate around the
centre of the droplet, pretty much as vortices rotate along circles
corresponding to isodensity lines of a Bose-Einstein condensate confined in an
axially symmetric optical trap. The effect of dissipation is shown in the
right panel of Fig. 5. The vortex velocity has now a component along the
gradient of the density. Vortices tend to spiral out from the high density
region towards places where the gradient of the density vanishes: local minima
of the density distribution. This behavior is depicted in Fig. 6 which shows
an orbit of a vortex that was initially in a high density region.

Intriguingly, for $\gamma\ll 1$, orbits spiraling out of the high density
region tend to a hexagonal path that is a semistable limit cycle. From the
velocity field orientation one can see that the actual stable points
correspond to the vertices of the first Brillouin zone, that is, a honeycomb
lattice rotated by $45^{\circ}$ with respect to the semistable limit cycle. In
order to better understand these aspects, we turn to a simplified model.

Figure 6: Vortex orbit obtained using Eq. (13) for a nonrotating supersolid
with $\gamma=0.05$ and $a_{s}=90a_{0}$. The column number density is in units
$\mu$m-2. The vortex spirals out the high density region toward a density
minimum.

###  3.1 Triangular toy model

The vortex velocity in Eq. (13) depends only on the matter density
distribution and not directly on the interaction potential. Hence, assuming
that there exists an interaction potential that produces a certain matter
distribution, we can determine the corresponding vortex velocity.

As a toy model for the supersolid density modulation one can take

$\rho(\bm{r})=\rho_{0}\left(1+C\sum_{i=1}^{3}\cos(\bm{q}_{i}\cdot\bm{r})\right)\,,$
(15)

where the vectors

$\bm{q}_{1}=q(0,1)\,,\quad\bm{q}_{2}=q(\sqrt{3}/2,-1/2)\,,\quad\bm{q}_{3}=-q(\sqrt{3}/2,1/2)\,,$
(16)

indicate the vertices of a 2D triangular lattice. Hereafter we will take
$q=1$, meaning that distances are measured in units of $1/q$. The the density
contrast is

$\frac{\rho_{\textbf{max}}-\rho_{\textbf{min}}}{\rho_{\textbf{max}}+\rho_{\textbf{min}}}=\frac{9C}{4+3C}\,,$
(17)

and thus $0\leq C\leq 2/3$. For definiteness, we take $C=0.3$, meaning that
the density ranges between $0.7\rho_{0}$ and $1.3\rho_{0}$. Such matter
density distribution is smoother than the one produced by the model with
dipole-dipole and s-wave interactions. However, it has the same space symmetry
and given its simplicity it is possible to be easily analyzed.

Figure 7: Triangular model, see Eq. (15), with $C=0.3$, in the case of
vanishing dissipation. The number density is measured in units of $\rho_{0}$,
distances in units of $1/q$. Left: streamlines (in black) and first Brillouin
zone (in red). Right: stationary points and orbits. Red stars correspond to
maxima of the number density, while green dots are minima. In both cases,
orbits around these points are periodic. Filled black squares correspond to
density saddle points. Orbits passing through a saddle point form a hexagonal
path. A vortex that moves along such a path terminates at a saddle point.

The left panel of Fig. 7 shows the density plot in units of $\rho_{0}$, the
first Brillouin zone (in red) of the central lattice point and streamlines (in
black) for vanishing dissipation. The first Brillouin zone is a hexagon with
vertices at the density minima. As in the case of the supersolid discussed
above, since for $\gamma=0$ the system is conservative, streamlines form
closed paths.

If we indicate with $\bm{x}_{v}=(x,y)$ the vortex position, for vanishing
dissipation we obtain an analytical first integral given by

$y(x)=\pm\arccos\left\\{-\frac{1}{2}\cos\left(\frac{\sqrt{3}}{2}x\right)\pm\frac{1}{2\sqrt{2}}\sqrt{2\left[1+2\cos\left(\frac{y_{0}}{2}\right)\right]^{2}-1+\cos(\sqrt{3}x)}\right\\}\,,$
(18)

where $y_{0}\equiv y(x=0)$. The first integral is shown in the right panel of
Fig. 7 for different values of $y_{0}$. For $y_{0}\ll 1$, we can linearize and
obtain the circular orbit

$y^{2}+x^{2}=y_{0}^{2}\,,$ (19)

around the density maxima (in red). With increasing values of $y_{0}$ circles
are deformed until, for $y_{0}=\pi$, the first integral is a hexagon centered
at a red star. Such hexagons enclose all the periodic orbits centered at the
density maximum and are rotated $45^{\circ}$ with respect to the first
Brillouin zone. Note that each orbit starting from a point exactly on the
hexagon terminates at one of the saddle points (in black). For
$\pi<y_{0}<4/3\pi$, periodic orbits are instead around density minima (in
green). From the right panel of Fig. 7, one can see that the whole plane can
be tiled in hexagons and triangles. Hexagons are centered at density maxima,
while triangles are instead centered at density minima.

Figure 8: Triangular model, see Eq. (15), with $C=0.3$ and $\gamma=0.05$. The
number density is measured in units of $\rho_{0}$, distances in units of
$1/q$. Left: dissipation deforms periodic orbits; streamlines converge to
density minima. Right: orbit of a vortex starting in the high density region.
The vortex first spirals out the unstable point and it is then attracted by an
asymptotically stable focus.

Fig. 8 shows the streamlines (left) as well as an example of orbit (right)
including dissipation, with $\gamma=0.05$. As in the case of supersolid
described in the previous section, when $\gamma>0$, orbits are deformed.
Maxima of the number density become unstable focus points, while minima become
asymptotically stable focus points. No periodic orbits exist: all orbits
terminate in an asymptotically stable fixed point. In more detail, orbits
starting in the high density region spiral out until they reach the boundary
of one of the triangles surrounding a green dot, shown in the right panel of
Fig. 7. Then, vortices are captured by the corresponding attractor. The time
needed to reach an attractor starting from a point in the high density region
depends on $1/\gamma$. For $\gamma\to 0$, such time diverges. A detailed
analysis of the vortex time evolution as well as of the basins of attraction
is underway.

##  4 Conclusion

We have numerically simulated the inner crust of NSs with a supersolid of
164Dy atoms. These two apparently different systems share several key
ingredients. They have a high density crystalline structure, made of neutron
rich nuclei in NSs, and of clusters of bosons in the quantum gas. A superfluid
bath embeds the crystalline structure, in NSs it is a neutron superfluid,
while in supersolids it is a boson superfluid. Finally, in both cases the
periodic structure consists of superfluid matter, thus both systems can be
viewed as a supersolids.

When a supersolid is put in rotation, quantized vortices organize themselves
between the crystal sites. We have provided an extended discussion of the
energy variation arising from the presence of vortices. During an imposed
braking process, vortices are pinned, and thus the superfluid component does
not spin down. A glitch event happens when a vortex leaves its pinning site.
The pinning sites as well as the direction of vortex percolation can be
inferred by analyzing the energy profile obtained imprinting a vortex on the
top of the nonrotating system. Insight on the vortex evolution can be gained
by a simple toy model with triangular symmetry. The appealing feature of such
model is that in the non-dissipative case an exact first integral exists,
which allows to better understand vortex orbits.

These findings establish a strong connection between quantum mechanics and
astrophysics, offering a new perspective on the inner nature of NSs. A better
understanding of glitches will provide valuable insights into the internal
structure and dynamics of nuclear matter under extreme conditions, which
cannot be directly realized through terrestrial laboratory experiments.
Therefore, the existence of an analogous system on Earth, dipolar supersolids,
presents an unparalleled opportunity to replicate and test the vortex and
crystal dynamics inside NSs, opening new avenues for the quantum simulation of
celestial bodies.

Acknowledgements

This study received support from the European Research Council through the
Advanced Grant DyMETEr (No. 101054500), the QuantERA grant MAQS by the
Austrian Science Fund (FWF) (No. I4391-N), the DFG/FWF via Dipolare E2 (No.
I4317-N36) and a joint-project grant from the FWF (No. I4426). E.P.
acknowledges support by the FWF within the DK-ALM (No. W1259-N27). T.B.
acknowledges financial support by the ESQ Discovery programme (Erwin
Schrödinger Center for Quantum Science & Technology), hosted by the Austrian
Academy of Sciences (ÖAW).

## References

  *   * Poli et al. [2023] Poli, E., Bland, T., White, S.J.M., Mark, M.J., Ferlaino, F., Trabucco, S., Mannarelli, M.: Glitches in Rotating Supersolids. Phys. Rev. Lett. 131(22), 223401 (2023) https://doi.org/10.1103/PhysRevLett.131.223401 arXiv:2306.09698 [cond-mat.quant-gas]
  * Shapiro and Teukolsky [1983] Shapiro, S.L., Teukolsky, S.A.: Black Holes, White Dwarfs, and Neutron Stars: the Physics of Compact Objects. A Wiley-interscience publication. Wiley, New York, USA (1983)
  * Glendenning [2000] Glendenning, N.K.: Compact Stars: Nuclear Physics, Particle Physics, and General Relativity. Springer, New York, USA (2000)
  * Haensel and Pichon [1994] Haensel, P., Pichon, B.: Experimental nuclear masses and the ground state of cold dense matter. Astron. Astrophys. 283(1), 313–318 (1994) https://doi.org/10.48550/arXiv.nucl-th/9310003 arXiv:nucl-th/9310003 [nucl-th]
  * Lattimer and Prakash [2001] Lattimer, J.M., Prakash, M.: Neutron star structure and the equation of state. Astrophys. J. 550, 426 (2001) https://doi.org/%****␣proceeding_glitches.tex␣Line␣575␣****10.1086/319702 arXiv:astro-ph/0002232 [astro-ph]
  * Douchin and Haensel [2001] Douchin, F., Haensel, P.: A unified equation of state of dense matter and neutron star structure. Astron. Astrophys. 380, 151 (2001) https://doi.org/10.1051/0004-6361:20011402 arXiv:astro-ph/0111092 [astro-ph]
  * Haensel et al. [2007] Haensel, P., Potekhin, A.Y., Yakovlev, D.G.: Neutron Stars 1: Equation of State and Structure vol. 326. Springer, New York, USA (2007). https://doi.org/10.1007/978-0-387-47301-7
  * Potekhin et al. [2013] Potekhin, A.Y., Fantina, A.F., Chamel, N., Pearson, J.M., Goriely, S.: Analytical representations of unified equations of state for neutron-star matter. Astron. Astrophys. 560, 48 (2013) https://doi.org/10.1051/0004-6361/201321697 arXiv:1310.0049 [astro-ph.SR]
  * Sharma et al. [2015] Sharma, B.K., Centelles, M., Viñas, X., Baldo, M., Burgio, G.F.: Unified equation of state for neutron stars on a microscopic basis. Astron. Astrophys. 584, 103 (2015) https://doi.org/10.1051/0004-6361/201526642 arXiv:1506.00375 [nucl-th]
  * Blaschke and Chamel [2018] Blaschke, D., Chamel, N.: Phases of dense matter in compact stars. Astrophys. Space Sci. Libr. 457, 337–400 (2018) https://doi.org/10.1007/978-3-319-97616-7_7 arXiv:1803.01836 [nucl-th]
  * Fiorella Burgio and Fantina [2018] Fiorella Burgio, G., Fantina, A.F.: Nuclear Equation of state for Compact Stars and Supernovae. Astrophys. Space Sci. Libr. 457, 255–335 (2018) https://doi.org/10.1007/978-3-319-97616-7_6 arXiv:1804.03020 [nucl-th]
  * Negele and Vautherin [1973] Negele, J.W., Vautherin, D.: Neutron star matter at subnuclear densities. Nucl. Phys. A207, 298–320 (1973) https://doi.org/10.1016/0375-9474(73)90349-7
  * Hewish et al. [1968] Hewish, A., Bell, S.J., Pilkington, J.D.H., Scott, P.F., Collins, R.A.: Observation of a rapidly pulsating radio source. Nature 217(5130), 709–713 (1968) https://doi.org/10.1038/217709a0
  * Hamil et al. [2015] Hamil, O., Stone, J.R., Urbanec, M., Urbancová, G.: Braking index of isolated pulsars. Phys. Rev. D 91(6), 063007 (2015) https://doi.org/10.1103/PhysRevD.91.063007 arXiv:1608.01383 [astro-ph.HE]
  * Kaspi and Kramer [2016] Kaspi, V.M., Kramer, M.: Radio Pulsars: The Neutron Star Population & Fundamental Physics. In: 26th Solvay Conference on Physics: Astrophysics and Cosmology (2016)
  * Zhou et al. [2022] Zhou, S., Gügercinoğlu, E., Yuan, J., Ge, M., Yu, C.: Pulsar Glitches: A Review. Universe 8(12), 641 (2022) https://doi.org/10.3390/universe8120641 arXiv:2211.13885 [astro-ph.HE]
  * Baym et al. [1969] Baym, G., Pethick, C., Pines, D., Ruderman, M.: Spin up in neutron stars: The future of the vela pulsar. Nature 224, 872 (1969) https://doi.org/10.1038/224872a0
  * Ruderman [1972] Ruderman, M.: Pulsars: structure and dynamics. Ann. Rev. Astron. Astrophys. 10, 427–476 (1972) https://doi.org/10.1146/annurev.aa.10.090172.002235
  * Pines [1991] Pines, D.: In: Ventura, J., Pines, D. (eds.) Neutron Stars as Cosmic Hadron Physics Laboratories: What Glitches Teach Us, pp. 57–70. Springer, Dordrecht (1991). https://doi.org/10.1007/978-94-011-3536-8_5 . https://doi.org/10.1007/978-94-011-3536-8_5
  * Link et al. [1999] Link, B., Epstein, R.I., Lattimer, J.M.: Pulsar constraints on neutron star structure and equation of state. Phys. Rev. Lett. 83, 3362–3365 (1999) https://doi.org/10.1103/PhysRevLett.83.3362 arXiv:astro-ph/9909146
  * Haskell and Melatos [2015] Haskell, B., Melatos, A.: Models of Pulsar Glitches. Int. J. Mod. Phys. D 24(03), 1530008 (2015) https://doi.org/10.1142/S0218271815300086 arXiv:1502.07062 [astro-ph.SR]
  * Anderson and Itoh [1975] Anderson, P.W., Itoh, N.: Pulsar glitches and restlessness as a hard superfluidity phenomenon. Nature 256, 25–27 (1975) https://doi.org/10.1038/256025a0
  * Alpar [1977] Alpar, M.A.: Pinning and Threading of Quantized Vortices in the Pulsar Crust Superfluid. Astrophys. J. 213, 527–530 (1977) https://doi.org/10.1086/155183
  * Alpar et al. [1984a] Alpar, M.A., Pines, D., Anderson, P.W., Shaham, J.: Vortex creep and the internal temperature of neutron stars. I - General theory. Astrophys. J. 276, 325–334 (1984) https://doi.org/10.1086/161616
  * Alpar et al. [1984b] Alpar, M.A., Anderson, P.W., Pines, D., Shaham, J.: Vortex creep and the internal temperature of neutron stars. II - VELA pulsar. Astrophys. J. 278, 791–805 (1984) https://doi.org/10.1086/161849
  * Link et al. [1992] Link, B., Epstein, R.I., Van Riper, K.A.: Pulsar glitches as probes of neutron star interiors. Nature 359(6396), 616–618 (1992) https://doi.org/10.1038/359616a0
  * Altman et al. [2021] Altman, E., et al.: Quantum Simulators: Architectures and Opportunities. PRX Quantum 2(1), 017003 (2021) https://doi.org/10.1103/PRXQuantum.2.017003 arXiv:1912.06938 [quant-ph]
  * Tsakadze et al. [1973] Tsakadze, D., Tsakadze, S.D., et al.: Measurement of the relaxation time on acceleration of vessels with helium II and superfluidity in pulsars. Soviet Physics-JETP 37, 918–921 (1973)
  * Tsakadze and Tsakadze [1980] Tsakadze, J.S., Tsakadze, S.J.: Properties of slowly rotating helium II and the superfluidity of pulsars. Journal of Low Temperature Physics 39, 649 (1980) https://doi.org/10.1007/BF00114899
  * Warszawski and Melatos [2011] Warszawski, L., Melatos, A.: Gross-Pitaevskii model of pulsar glitches. Mon. Not. Roy. Astron. Soc. 415, 1611 (2011) https://doi.org/10.1111/j.1365-2966.2011.18803.x arXiv:1103.6090 [astro-ph.SR]
  * Warszawski et al. [2012] Warszawski, L., Melatos, A., Berloff, N.: Unpinning triggers for superfluid vortex avalanches. Phys. Rev. B 85, 104503 (2012) https://doi.org/10.1103/PhysRevB.85.104503 arXiv:1203.5133 [cond-mat.other]
  * Warszawski and Melatos [2013] Warszawski, L., Melatos, A.: Knock-on processes in superfluid vortex avalanches and pulsar glitch statistics. Mon. Not. Roy. Astron. Soc. 428, 1911 (2013) https://doi.org/10.1093/mnras/sts108 arXiv:1210.2203 [astro-ph.HE]
  * Graber et al. [2017] Graber, V., Andersson, N., Hogg, M.: Neutron stars in the laboratory. International Journal of Modern Physics D 26(08), 1730015 (2017)
  * You et al. [2024] You, J., Yi, S., Deng, Y.: Self-Ordered Supersolid in Spinor Condensates with Cavity-Mediated Spin-Momentum-Mixing Interactions (2024) arXiv:2404.11157 [cond-mat.quant-gas]
  * Alaña et al. [2024] Alaña, A., Modugno, M., Capuzzi, P., Jezek, D.M.: Phase-induced vortex pinning in rotating supersolid dipolar systems (2024) arXiv:2405.05099 [cond-mat.quant-gas]
  * Magierski et al. [2024] Magierski, P., Barresi, A., Makowski, A., Pecak, D., Wlazłowski, G.: Quantum vortices in fermionic superfluids: from ultracold atoms to neutron stars (2024) arXiv:2406.14158 [cond-mat.quant-gas]
  * Leggett [1970] Leggett, A.J.: Can a solid be ”superfluid”? Phys. Rev. Lett. 25, 1543–1546 (1970) https://doi.org/10.1103/PhysRevLett.25.1543
  * Li et al. [2017] Li, J.-R., Lee, J., Huang, W., Burchesky, S., Shteynas, B., Top, F.Ç., Jamison, A.O., Ketterle, W.: A stripe phase with supersolid properties in spin–orbit-coupled bose–einstein condensates. Nature 543(7643), 91–94 (2017)
  * Léonard et al. [2017] Léonard, J., Morales, A., Zupancic, P., Esslinger, T., Donner, T.: Supersolid formation in a quantum gas breaking a continuous translational symmetry. Nature 543(7643), 87–90 (2017)
  * Böttcher et al. [2019] Böttcher, F., Schmidt, J.-N., Wenzel, M., Hertkorn, J., Guo, M., Langen, T., Pfau, T.: Transient supersolid properties in an array of dipolar quantum droplets. Phys. Rev. X 9, 011051 (2019) https://doi.org/10.1103/PhysRevX.9.011051
  * Tanzi et al. [2019] Tanzi, L., Lucioni, E., Famà, F., Catani, J., Fioretti, A., Gabbanini, C., Bisset, R.N., Santos, L., Modugno, G.: Observation of a dipolar quantum gas with metastable supersolid properties. Phys. Rev. Lett. 122, 130405 (2019) https://doi.org/10.1103/PhysRevLett.122.130405
  * Chomaz et al. [2019] Chomaz, L., Petter, D., Ilzhöfer, P., Natale, G., Trautmann, A., Politi, C., Durastante, G., Bijnen, R.M.W., Patscheider, A., Sohmen, M., Mark, M.J., Ferlaino, F.: Long-Lived and Transient Supersolid Behaviors in Dipolar Quantum Gases. Phys. Rev. X 9, 021012 (2019) https://doi.org/10.1103/PhysRevX.9.021012
  * Norcia et al. [2021] Norcia, M.A., Politi, C., Klaus, L., Poli, E., Sohmen, M., Mark, M.J., Bisset, R.N., Santos, L., Ferlaino, F.: Two-dimensional supersolidity in a dipolar quantum gas. Nature 596(7872), 357–361 (2021)
  * Bland et al. [2022] Bland, T., Poli, E., Politi, C., Klaus, L., Norcia, M., Ferlaino, F., Santos, L., Bisset, R.: Two-dimensional supersolid formation in dipolar condensates. Physical Review Letters 128(19), 195302 (2022)
  * Klaus et al. [2022] Klaus, L., Bland, T., Poli, E., Politi, C., Lamporesi, G., Casotti, E., Bisset, R.N., Mark, M.J., Ferlaino, F.: Observation of vortices and vortex stripes in a dipolar condensate. Nature Physics 18(12), 1453–1458 (2022) https://doi.org/10.1038/s41567-022-01793-8
  * Casotti et al. [2024] Casotti, E., Poli, E., Klaus, L., Litvinov, A., Ulm, C., Politi, C., Mark, M.J., Bland, T., Ferlaino, F.: Observation of vortices in a dipolar supersolid (2024) arXiv:2403.18510 [cond-mat.quant-gas]
  * Recati and Stringari [2023] Recati, A., Stringari, S.: Supersolidity in ultracold dipolar gases. Nature Rev. Phys. 5(12), 735–743 (2023) https://doi.org/10.1038/s42254-023-00648-2 arXiv:2405.09537 [cond-mat.quant-gas]
  * Roccuzzo et al. [2020] Roccuzzo, S.M., Gallemí, A., Recati, A., Stringari, S.: Rotating a supersolid dipolar gas. Phys. Rev. Lett. 124, 045702 (2020) https://doi.org/10.1103/PhysRevLett.124.045702
  * Gallemí et al. [2020] Gallemí, A., Roccuzzo, S.M., Stringari, S., Recati, A.: Quantized vortices in dipolar supersolid bose-einstein-condensed gases. Phys. Rev. A 102, 023322 (2020) https://doi.org/10.1103/PhysRevA.102.023322
  * Ancilotto et al. [2021] Ancilotto, F., Barranco, M., Pi, M., Reatto, L.: Vortex properties in the extended supersolid phase of dipolar bose-einstein condensates. Phys. Rev. A 103, 033314 (2021) https://doi.org/10.1103/PhysRevA.103.033314
  * Butts and Rokhsar [1999] Butts, D., Rokhsar, D.: Predicted signatures of rotating bose–einstein condensates. Nature 397, 327–9 (1999) https://doi.org/10.1038/16865
  * Wächtler and Santos [2016] Wächtler, F., Santos, L.: Quantum filaments in dipolar bose-einstein condensates. Phys. Rev. A 93, 061603 (2016) https://doi.org/10.1103/PhysRevA.93.061603
  * Bisset et al. [2016] Bisset, R.N., Wilson, R.M., Baillie, D., Blakie, P.B.: Ground-state phase diagram of a dipolar condensate with quantum fluctuations. Phys. Rev. A 94, 033619 (2016) https://doi.org/10.1103/PhysRevA.94.033619
  * Ferrier-Barbut et al. [2016] Ferrier-Barbut, I., Kadau, H., Schmitt, M., Wenzel, M., Pfau, T.: Observation of quantum droplets in a strongly dipolar bose gas. Phys. Rev. Lett. 116, 215301 (2016) https://doi.org/10.1103/PhysRevLett.116.215301
  * Chomaz et al. [2016] Chomaz, L., Baier, S., Petter, D., Mark, M.J., Wächtler, F., Santos, L., Ferlaino, F.: Quantum-fluctuation-driven crossover from a dilute bose-einstein condensate to a macrodroplet in a dipolar quantum fluid. Phys. Rev. X 6, 041039 (2016) https://doi.org/10.1103/PhysRevX.6.041039
  * Bradley and Anderson [2012] Bradley, A.S., Anderson, B.P.: Energy spectra of vortex distributions in two-dimensional quantum turbulence. Phys. Rev. X 2, 041001 (2012) https://doi.org/10.1103/PhysRevX.2.041001
  * Liu et al. [2024] Liu, I.-K., Prasad, S.B., Baggaley, A.W., Barenghi, C.F., Wood, T.S.: Vortex depinning in a two-dimensional superfluid. Journal of Low Temperature Physics, Special Issue: Quantum Fluids and Solids (QFS2023) (2024) https://doi.org/10.1007/s10909-024-03064-7
  * Fetter [1966] Fetter, A.L.: Vortices in an imperfect bose gas. IV. Translational Velocity. Phys. Rev. 151, 100–104 (1966) https://doi.org/10.1103/PhysRev.151.100
  * Pomeau and Rica [1994] Pomeau, Y., Rica, S.: Dynamics of a model of supersolid. Phys. Rev. Lett. 72, 2426–2429 (1994) https://doi.org/%****␣proceeding_glitches.tex␣Line␣1475␣****10.1103/PhysRevLett.72.2426
  * Groszek et al. [2018] Groszek, A.J., Paganin, D.M., Helmerson, K., Simula, T.P.: Motion of vortices in inhomogeneous bose-einstein condensates. Phys. Rev. A 97, 023617 (2018) https://doi.org/10.1103/PhysRevA.97.023617
  * Bland et al. [2023] Bland, T., Lamporesi, G., Mark, M.J., Ferlaino, F.: Vortices in dipolar Bose-Einstein condensates. Comptes Rendus. Physique 24, 133–152 (2023) https://doi.org/10.5802/crphys.160


##  1 Proofs for Section LABEL:sec:discounted-vaw ()

###  1.1 Equivalence to FTRL and Mirror Descent

We accomplish our analysis of the discounted VAW forecaster using the
equivalence in the following proposition, proving both optimistic FTRL and and
optimistic mirror descent interpretations of the discounted VAW forecaster.
eq:discounted-vaw-update:ftrl is perhaps the most natural interpretation of
the update: it says that the discounted VAW forecaster chooses the $\w$ which
minimizes the _discounted sum_
$h_{t}(\w)+\gamma\ell_{\tmm}(\w)+\gamma^{2}\ell_{t-2}(\w)+\ldots$, thus
placing greater emphasis on the most-recent losses and the hint function
$h_{t}(\w)$. However, it is not at all obvious how to analyze the dynamic
regret of the discounted VAW forecaster when interpreted in this FTRL-like
form. Rather, the key to our results in this work is to instead approach the
analysis through the lens of the mirror descent update (eq:discounted-vaw-
update:md). Interestingly, a similar mirror descent interpretation was used in
the seminal work of azoury2001relative, though they did not account for an
arbitrary $\yhint_{t}$ and they did not refer to the algorithm in terms of
mirror descent. propositionDiscountedVAWUpdate (Discounted VAW Forecaster) Let
$\gamma\in(0,1]$, $\lambda>0$, $\yhint_{1}=0$, and $\yhint_{t}\in\R$ for
$t>1$. Define $h_{t}(\w)=\half(\yhint_{t}-\inner{\xt,\w})^{2}$ and
$\ell_{0}(\w)=\frac{\lambda}{2}\norm{\w}^{2}_{2}$. Recursively define
$\Sigma_{t}=\xt\xt^{\top}+\gamma\Sigma_{\tmm}$ starting from
$\Sigma_{0}=\lambda I$, let $\psi_{t}(\w)=\half\norm{\w}^{2}_{\Sigma_{t}}$ and
set $w_{1}=\argmin_{w\in\R^{d}}\psi_{1}(w)=\zeros$. Then the following are
equivalent

$\displaystyle\argmin_{\w\in\R^{d}}$ $\displaystyle
h_{t}(\w)+\gamma\sum_{s=0}^{\tmm}\gamma^{t-1-s}\ell_{s}(s)$ (1)
$\displaystyle\argmin_{\w\in\R^{d}}$ $\displaystyle(\gamma\ell_{\tmm}-\gamma
h_{\tmm}+h_{t})(\w)+\gamma D_{\psi_{\tmm}}(\w|\wtmm)$ (2)

######  Remark 1.1.

Note that with $\gamma=0$, eq:discounted-vaw-update:ftrl,eq:discounted-vaw-
update:md prescribe choosing any $\wt$ satisfying
$\inner{\wt,\xt}=\yhint_{t}$. The choice is not unique, but nevertheless it
will often be convenient to refer to an algorithm which greedily predicts
$\yhint_{t}$ on each round as an instance of alg:discounted-vaw with
$\gamma=0$.

######  Proof 1.2.

The result follows by showing that eq:discounted-vaw-
update:ftrl,eq:discounted-vaw-update:md are both equivalent to eq:discounted-
vaw-update:closed-form. First consider the former, eq:discounted-vaw-
update:ftrl. From the first-order optimality condition we have

$\displaystyle\zeros$ $\displaystyle=\grad
h_{t}(\wt)+\gamma\sum_{s=0}^{\tmm}\gamma^{\tmm-s}\grad\ell_{s}(\wt)$
$\displaystyle=-(\yhint_{t}-\inner{\xt,\wt})\xt-\gamma\sum_{s=1}^{\tmm}\gamma^{\tmm-s}(\y_{s}-\inner{\x_{s},\wt})\x_{s}+\gamma^{t}\lambda\wt,$

where the last line recalls that we defined
$\ell_{0}(\w)=\frac{\lambda}{2}\norm{\w}^{2}_{2}$. Hence,

$\displaystyle\brac{\gamma^{t}\lambda
I+\sum_{s=1}^{t}\gamma^{t-s}\x_{s}\x_{s}^{\top}}\wt$
$\displaystyle=\yhint_{t}\xt+\sum_{s=1}^{t}\gamma^{t-s}\y_{s}\x_{s}$
$\displaystyle\implies\wt$ $\displaystyle=\brac{\gamma^{t}\lambda
I+\sum_{s=1}^{t}\gamma^{t-s}\x_{s}\x_{s}^{\top}}^{\inv}\sbrac$
$\displaystyle=\Sigma_{t}^{\inv}\sbrac{\yhint_{t}\xt+\gamma\sum_{s=1}^{\tmm}\gamma^{\tmm-s}y_{s}\x_{s}},$

where the last line can be seen by unrolling the recursion for $\Sigma_{t}$.

Likewise, consider eq:discounted-vaw-update:md. From the first-order
optimality condition $\wt=\argmin_{\w\in\R^{d}}(\gamma\ell_{\tmm}-\gamma
h_{\tmm}+h_{t})(\w)+\gamma D_{\psi_{\tmm}}(\w|\wt)$, we have

$\displaystyle\zeros$ $\displaystyle=\gamma(\grad\ell_{\tmm}(\wt)-\grad
h_{\tmm}(\wt))+\grad
h_{t}(\wt)+\gamma\sbrac{\grad\psi_{\tmm}(\wt)-\grad\psi_{\tmm}(\wtmm)}$
$\displaystyle=-\gamma\ytmm\xtmm+\gamma\yhint_{\tmm}\xtmm-\yhint_{t}\xt+\xt\xt^{\top}\wt+\gamma\Sigma_{\tmm}\wt-\gamma\Sigma_{\tmm}\wtmm$
$\displaystyle=-\gamma\ytmm\xtmm+\gamma\yhint_{\tmm}\xtmm-\yhint_{t}\xt+\Sigma_{t}\wt-\gamma\Sigma_{\tmm}\wtmm,$

where the last line observes that
$\Sigma_{t}=\xt\xt^{\top}+\gamma\Sigma_{\tmm}$ by construction. Hence, re-
arranging we have

$\displaystyle\Sigma_{t}\wt$
$\displaystyle=\yhint_{t}\xt+\gamma\ytmm\xtmm-\gamma\yhint_{\tmm}\xtmm+\gamma\Sigma_{\tmm}\wtmm$
and unrolling the recursion:
$\displaystyle=\yhint_{t}\xt+\gamma\ytmm\xtmm-\gamma\yhint_{\tmm}\xtmm+\gamma\sbrac{\yhint_{\tmm}\xtmm+\gamma\y_{t-2}\x_{t-2}-\gamma\yhint_{t-2}\xt+\gamma\Sigma_{t-2}\w_{t-2}}$
$\displaystyle=\yhint_{t}\xt+\gamma\ytmm\xtmm+\gamma^{2}\y_{t-2}\x_{t-2}-\gamma^{2}\yhint_{t-2}\x_{t-2}+\gamma^{2}\Sigma_{t-2}\w_{t-2}$
$\displaystyle=\ldots$
$\displaystyle=\yhint_{t}\xt-\gamma^{\tmm}\yhint_{1}\x_{1}+\gamma\sum_{s=1}^{\tmm}\gamma^{\tmm-s}\y_{s}\x_{s}$
$\displaystyle=\yhint_{t}\xt+\gamma\sum_{s=1}^{\tmm}\gamma^{\tmm-s}\y_{s}\x_{s},$

for $\yhint_{1}=0$. Hence, applying $\Sigma_{t}^{\inv}$ to both sides we have

$\displaystyle\wt$
$\displaystyle=\Sigma_{t}^{\inv}\sbrac{\yhint_{t}\xt+\gamma\sum_{s=1}^{\tmm}\gamma^{\tmm-s}\y_{s}\x_{s}}$

###  1.2 Proof of Theorem LABEL:thm:general-discounted-vaw

*

######  Proof 1.3.

Begin by applying the regret template provided by lemma:discounted-vaw-decomp:

Finally, since the regret does not depend on $h_{T+1}(\cdot)$ we may set
$h_{T+1}(\cdot)\equiv 0$ in the analysis and hide constants to arrive at the
stated bound.

####  1.2.1 Proof of Lemma 1.2.1

The following lemma provides the base regret decomposition that we use as a
jumping-off point to prove thm:general-discounted-vaw. The result follows
using mostly standard mirror descent analysis, though with a bit of additional
care to handle issues related to the discounted regularizer.
lemmaDiscountedVAWDecomp Let $\gamma\in(0,1]$. Then for any sequence
$\vec{\cmp}=(\cmp_{1},\ldots,\cmp_{T})$ in $\R^{d}$, alg:discounted-vaw
guarantees

$\displaystyle R_{T}(\vec{\cmp})$ $\displaystyle\leq\sumtT
D_{\psi_{t}}(\cmp_{t}|\wt)-D_{\psi_{\tpp}}(\cmp_{t}|\wtpp)$
$\displaystyle\qquad+\sumtT h_{\tpp}(\cmp_{t})-h_{t}(\cmp_{t})$
$\displaystyle\qquad+\sumtT\half(\yt-\yhint_{t})^{2}\norm{\xt}^{2}_{\Sigma_{t}^{\inv}}$

######  Proof 1.4.

We will proceed following a mirror-descent-based analysis, and thus begin by
exposing the terms $(\gamma\ell_{t}-\gamma h_{t}+h_{\tpp})(\wtpp)$ observed in
the mirror-descent interpretation of the update (eq:discounted-vaw-update:md):

$\displaystyle R_{T}(\vec{\cmp})$
$\displaystyle=\sumtT\ell_{t}(\wt)-\ell_{t}(\cmp_{t})$
$\displaystyle=\sumtT\gamma\sbrac{\ell_{t}(\wt)-\ell_{t}(\cmp_{t})}+(1-\gamma)\sumtT\ell_{t}(\wt)-\ell_{t}(\cmp_{t})$
$\displaystyle=\sumtT\gamma\sbrac{(\ell_{t}-h_{t})(\wt)-(\ell_{t}-h_{t})(\cmp_{t})}+\sumtT\gamma
h_{t}(\wt)-\gamma h_{t}(\cmp_{t})$
$\displaystyle\qquad+(1-\gamma)\sumtT\ell_{t}(\wt)-\ell_{t}(\cmp_{t})$
$\displaystyle=\sumtT\gamma\sbrac{(\ell_{t}-h_{t})(\wtpp)-(\ell_{t}-h_{t})(\cmp_{t})}+\sumtT\gamma
h_{t}(\wt)-\gamma h_{t}(\cmp_{t})$
$\displaystyle\qquad+\gamma\sumtT(\ell_{t}-h_{t})(\wt)-(\ell_{t}-h_{t})(\wtpp)$
$\displaystyle\qquad+(1-\gamma)\sumtT\ell_{t}(\wt)-\ell_{t}(\cmp_{t})$
$\displaystyle=\sumtT(\gamma\ell_{t}-\gamma
h_{t}+h_{\tpp})(\wtpp)-(\gamma\ell_{t}-\gamma h_{t}+h_{\tpp})(\cmp_{t})$
$\displaystyle\qquad+\sumtT\gamma h_{t}(\wt)-h_{\tpp}(\wtpp)+\sumtT
h_{\tpp}(\cmp_{t})-\gamma h_{t}(\cmp_{t})$
$\displaystyle\qquad+\gamma\sumtT(\ell_{t}-h_{t})(\wt)-(\ell_{t}-h_{t})(\wtpp)$
$\displaystyle\qquad+(1-\gamma)\sumtT\ell_{t}(\wt)-\ell_{t}(\cmp_{t})$ Re-
arranging factors of $\gamma$ from the second-line and observing that $\sumtT
h_{t}(\wt)-h_{\tpp}(\wtpp)=h_{1}(\w_{1})-h_{T+1}(\w_{T+1})$:
$\displaystyle=\sumtT(\gamma\ell_{t}-\gamma
h_{t}+h_{\tpp})(\wtpp)-(\gamma\ell_{t}-\gamma h_{t}+h_{\tpp})(\cmp_{t})$
$\displaystyle\qquad+\sumtT
h_{t}(\wt)-h_{\tpp}(\wtpp)+\sumtT-(1-\gamma)h_{t}(\wt)+(1-\gamma)h_{t}(\cmp_{t})+\sumtT
h_{\tpp}(\cmp_{t})-h_{t}(\cmp_{t})$
$\displaystyle\qquad+\gamma\sumtT(\ell_{t}-h_{t})(\wt)-(\ell_{t}-h_{t})(\wtpp)$
$\displaystyle\qquad+(1-\gamma)\sumtT\ell_{t}(\wt)-\ell_{t}(\cmp_{t})$
$\displaystyle=\sumtT(\gamma\ell_{t}-\gamma
h_{t}+h_{\tpp})(\wtpp)-(\gamma\ell_{t}-\gamma h_{t}+h_{\tpp})(\cmp_{t})$
$\displaystyle\qquad+h_{1}(\w_{1})-h_{T+1}(\w_{T+1})+\sumtT
h_{\tpp}(\cmp_{t})-h_{t}(\cmp_{t})$
$\displaystyle\qquad+\gamma\sumtT(\ell_{t}-h_{t})(\wt)-(\ell_{t}-h_{t})(\wtpp)$
$\displaystyle\qquad+(1-\gamma)\sumtT(\ell_{t}-h_{t})(\wt)-(\ell_{t}-h_{t})(\cmp_{t})$
(3)

Moreover, from the first-order optimality condition
$\wtpp=\argmin_{\w\in\R^{d}}(\gamma\ell_{t}-\gamma h_{t}+h_{\tpp})(\w)+\gamma
D_{\psi_{t}}(\w|\wt)$, we have

$\displaystyle\inner{\grad(\gamma\ell_{t}-\gamma
h_{t}+h_{\tpp})(\wtpp)+\gamma\grad\psi_{t}(\wtpp)-\gamma\grad\psi_{t}(\wt),\wtpp-\cmp_{t}}\leq
0$

so re-arranging:

$\displaystyle\inner{\grad(\gamma\ell_{t}-\gamma
h_{t}+h_{\tpp})(\wtpp),\wtpp-\cmp_{t}}$
$\displaystyle\leq\gamma\inner{\grad\psi_{t}(\wt)-\grad\psi_{t}(\wtpp),\wtpp-\cmp_{t}}$
$\displaystyle=\gamma D_{\psi_{t}}(\cmp_{t}|\wt)-\gamma
D_{\psi_{t}}(\cmp_{t}|\wtpp)-\gamma D_{\psi_{t}}(\wtpp|\wt),$

where the last line uses the three-point relation for bregman divergences,
$\inner{\grad f(w)-\grad
f(\w^{\prime}),\w^{\prime}-\cmp}=D_{f}(\cmp|\w)-D_{f}(\cmp|\w^{\prime})-D_{f}(\w^{\prime}|\w)$.
Thus,

$\displaystyle\sumtT(\gamma\ell_{t}-\gamma
h_{t}+h_{\tpp})(\wtpp)-(\gamma\ell_{t}-\gamma h_{t}+h_{\tpp})(\cmp_{t})$
$\displaystyle\qquad\overset{(a)}{=}\sumtT\inner{\grad(\gamma\ell_{t}-\gamma
h_{t}+h_{\tpp})(\wtpp),\wtpp-\cmp_{t}}-D_{\gamma\ell_{t}-\gamma
h_{t}+h_{\tpp}}(\cmp_{t}|\wtpp)$ $\displaystyle\qquad\leq\sumtT\gamma
D_{\psi_{t}}(\cmp_{t}|\wt)-\gamma D_{\psi_{t}}(\cmp_{t}|\wtpp)-\gamma
D_{\psi_{t}}(\wtpp|\wt)-D_{\gamma\ell_{t}-\gamma
h_{t}+h_{\tpp}}(\cmp_{t}|\wtpp)$
$\displaystyle\qquad\overset{(b)}{=}\sumtT\gamma
D_{\psi_{t}}(\cmp_{t}|\wt)-\gamma
D_{\psi_{t}}(\cmp_{t}|\wtpp)-D_{h_{\tpp}}(\cmp_{t}|\wtpp)-\gamma
D_{\psi_{t}}(\wtpp|\wt)$ $\displaystyle\qquad\overset{(c)}{=}\sumtT\gamma
D_{\psi_{t}}(\cmp_{t}|\wt)-D_{\psi_{\tpp}}(\cmp_{t}|\wtpp)-\gamma
D_{\psi_{t}}(\wtpp|\wt)$ $\displaystyle\qquad=\sumtT
D_{\psi_{t}}(\cmp_{t}|\wt)-D_{\psi_{\tpp}}(\cmp_{t}|\wtpp)-(1-\gamma)D_{\psi_{t}}(\cmp_{t}|\wt)-\gamma
D_{\psi_{t}}(\wtpp|\wt),$

where $(a)$ uses the definition of Bregman divergence to re-write
$f(\w)-f(\cmp)=\inner{\grad f(\w),\w-\cmp}-D_{f}(\cmp|\w)$, $(b)$ observes
that
$\gamma(\ell_{t}-h_{t})(\w)=\gamma\brac{\half\yt^{2}-\half\yhint_{t}^{2}+(\yhint_{t}-\yt)\inner{\xt,\w}}$,
so $D_{\gamma\ell_{t}-\gamma
h_{t}+h_{\tpp}}(\cdot|\cdot)=D_{h_{\tpp}}(\cdot|\cdot)$ due to the invariance
of Bregman divergences to linear terms, and $(c)$ recalls that
$\Sigma_{\tpp}=\xtpp\xtpp^{\top}+\gamma\Sigma_{t}$ so that overall we have:

$\displaystyle\gamma
D_{\psi_{t}}(\cmp_{t}|\wtpp)+D_{h_{\tpp}}(\cmp_{t}|\wtpp)$
$\displaystyle=\frac{\gamma}{2}\norm{\cmp_{t}-\wtpp}^{2}_{\Sigma_{t}}+\half\inner{\xtpp,\cmp_{t}-\wtpp}^{2}$
$\displaystyle=\half\norm{\cmp_{t}-\wtpp}^{2}_{\Sigma_{\tpp}}$
$\displaystyle=D_{\psi_{\tpp}}(\cmp_{t}|\wtpp).$

Plugging this back into eq:discounted-vaw-decomp:initial, we have

$\displaystyle R_{T}(\vec{\cmp})$ $\displaystyle\leq\sumtT
D_{\psi_{t}}(\cmp_{t}|\wt)-D_{\psi_{\tpp}}(\cmp_{t}|\wtpp)$
$\displaystyle\qquad+h_{1}(\w_{1})-h_{T+1}(\w_{T+1})+\sumtT
h_{\tpp}(\cmp_{t})-h_{t}(\cmp_{t})$
$\displaystyle\qquad+\gamma\sumtT(\ell_{t}-h_{t})(\wt)-(\ell_{t}-h_{t})(\wtpp)-D_{\psi_{t}}(\wtpp|\wt)$
$\displaystyle\qquad+(1-\gamma)\sumtT(\ell_{t}-h_{t})(\wt)-(\ell_{t}-h_{t})(\cmp_{t})-D_{\psi_{t}}(\cmp_{t}|\wtpp).$

Finally, observe that for any $u,v\in\R^{d}$,
$(\ell_{t}-h_{t})(u)-(\ell_{t}-h_{t})(v)=(\yhint_{t}-\yt)\inner{\xt,u-v}$, so
an application of Fenchel-Young inequality yields

$\displaystyle(\ell_{t}-h_{t})(u)-(\ell_{t}-h_{t})(v)-D_{\psi_{t}}(v|u)$
$\displaystyle=(\yhint_{t}-\yt)\inner{\xt,u-v}-\half\norm{u-v}^{2}_{\Sigma_{t}}$
$\displaystyle\leq\half(\yt-\yhint_{t})^{2}\norm{\xt}^{2}_{\Sigma_{t}^{\inv}}.$

Applying this in the last two lines of the previous display yields

$\displaystyle R_{T}(\vec{\cmp})$ $\displaystyle\leq\sumtT
D_{\psi_{t}}(\cmp_{t}|\wt)-D_{\psi_{\tpp}}(\cmp_{t}|\wtpp)$
$\displaystyle\qquad\underbrace{h_{1}(\w_{1})-h_{T+1}(\w_{T+1})}_{\leq
0}+\sumtT h_{\tpp}(\cmp_{t})-h_{t}(\cmp_{t})$
$\displaystyle\qquad\gamma\sumtT\half(\yt-\yhint_{t})^{2}\norm{\xt}^{2}_{\Sigma_{t}^{\inv}}+(1-\gamma)\sumtT\half(\yt-\yhint_{t})^{2}\norm{\xt}^{2}_{\Sigma_{t}^{\inv}}$
$\displaystyle\leq\sumtT
D_{\psi_{t}}(\cmp_{t}|\wt)-D_{\psi_{\tpp}}(\cmp_{t}|\wtpp)$
$\displaystyle\qquad+\sumtT h_{\tpp}(\cmp_{t})-h_{t}(\cmp_{t})$
$\displaystyle\qquad+\sumtT\half(\yt-\yhint_{t})^{2}\norm{\xt}^{2}_{\Sigma_{t}^{\inv}}$

####  1.2.2 Proof of Lemma 1.2.2

The following lemma bounds the sum of divergence terms. Intuitively, the goal
here is to remove all instances of $\wt$ from the analysis, since in an
unbounded domain any terms depending on $\wt$ will be hard to quantify and
could be arbitrarily large in general. lemma:general-discounted-vaw-
divergences shows how get rid of the $\wt$-dependent terms left in the bound
from lemma:discounted-vaw-decomp, such that only dependencies on the
comparators $\cmp_{t}$ remain. lemmaGeneralDiscountedVAWDivergences Under the
same conditions as lemma:discounted-vaw-decomp,

$\displaystyle\sumtT
D_{\psi_{t}}(\cmp_{t}|\wt)-D_{\psi_{\tpp}}(\cmp_{t}|\wtpp)+\sumtT
h_{\tpp}(\cmp_{t})-h_{t}(\cmp_{t})$
$\displaystyle\leq\frac{\gamma\lambda}{2}\norm{\cmp_{1}}^{2}_{2}+h_{T+1}(\cmp_{T})+\gamma\sum_{t=1}^{T-1}F_{t}^{\gamma}(\cmp_{\tpp})-F_{t}^{\gamma}(\cmp_{t}).$

where $F_{t}^{\gamma}(\w)=\sum_{s=0}^{t}\gamma^{t-s}\ell_{s}(\w)$.

######  Proof 1.5.

Observe that by lemma:loss-divergence we have
$D_{\ell_{t}}(u|v)=\half\inner{\xt,u-v}^{2}=D_{h_{t}}(u|v)$ for any $u,v\in
W$. Hence, letting $F_{t}^{\gamma}(\w)=\sum_{s=0}^{t}\gamma^{t-s}\ell_{s}(\w)$
and $\hat{F}_{t}^{\gamma}(\w)=h_{t}(\w)+\gamma F_{\tmm}^{\gamma}(\w)$, and
recalling
$\psi_{t}(\w)=\half\norm{\w}^{2}_{\Sigma_{t}}=\frac{\gamma^{t}\lambda}{2}\norm{\w}^{2}_{2}+\half\sum_{s=1}^{t}\gamma^{t-s}\inner{\x_{s},\w}^{2}$,
we have $D_{\psi_{t}}(u|v)=D_{\hat{F}_{t}^{\gamma}}(u|v)$ for any
$u,v\in\in\R^{d}$. Thus:

$\displaystyle\sumtT
D_{\psi_{t}}(\cmp_{t}|\wt)-D_{\psi_{\tpp}}(\cmp_{t}|\wtpp)$
$\displaystyle\qquad=D_{\psi_{1}}(\cmp_{1}|\w_{1})-D_{\psi_{T+1}}(\cmp_{T}|\w_{T+1})+\sum_{t=2}^{T}D_{\psi_{t}}(\cmp_{t}|\wt)-D_{\psi_{t}}(\cmp_{\tmm}|\wt)$
$\displaystyle\qquad=D_{\psi_{1}}(\cmp_{1}|\w_{1})-D_{\psi_{T+1}}(\cmp_{T}|\w_{T+1})+\sum_{t=2}^{T}D_{\hat{F}_{t}^{\gamma}}(\cmp_{t}|\wt)-D_{\hat{F}_{t}^{\gamma}}(\cmp_{\tmm}|\wt)$
$\displaystyle\qquad=D_{\psi_{1}}(\cmp_{1}|\w_{1})-D_{\psi_{T+1}}(\cmp_{T}|\w_{T+1})+\sum_{t=2}^{T}\hat{F}_{t}^{\gamma}(\cmp_{t})-\hat{F}_{t}^{\gamma}(\cmp_{\tmm})-\inner{\grad\hat{F}_{t}^{\gamma}(\wt),\cmp_{t}-\cmp_{\tmm}}.$

Moreover, by prop:discounted-vaw-update we have

$\displaystyle\wt=\argmin_{w\in\R^{d}}h_{t}(\w)+\gamma\sum_{s=0}^{\tmm}\gamma^{t-1-s}\ell_{s}(\w)=\argmin_{w\in\R^{d}}\hat{F}_{t}^{\gamma}(\w),$

hence by convexity of $\hat{F}_{t}^{\gamma}$ and the first-order optimality
condition we have $\grad\hat{F}_{t}^{\gamma}(\wt)=\zeros$, so overall we have

$\displaystyle\sum_{t=1}^{T}D_{\psi_{t}}(\cmp_{t}|\wt)-D_{\psi_{t}}(\cmp_{t}|\wtpp)+\sumtT
h_{\tpp}(\cmp_{t})-h_{t}(\cmp_{t})$
$\displaystyle\qquad=D_{\psi_{1}}(\cmp_{1}|\w_{1})-D_{\psi_{T+1}}(\cmp_{T}|\w_{T+1})+\sum_{t=2}^{T}\hat{F}_{t}^{\gamma}(\cmp_{t})-\hat{F}_{t}^{\gamma}(\cmp_{\tmm})+\sumtT
h_{\tpp}(\cmp_{t})-h_{t}(\cmp_{t})$
$\displaystyle\qquad=D_{\psi_{1}}(\cmp_{1}|\w_{1})-D_{\psi_{T+1}}(\cmp_{T}|\w_{T+1})+\sum_{t=2}^{T}\sbrac{h_{t}(\cmp_{t})-h_{t}(\cmp_{\tmm})+\gamma
F_{\tmm}^{\gamma}(\cmp_{t})-\gamma F_{\tmm}^{\gamma}(\cmp_{\tmm})}+\sumtT
h_{\tpp}(\cmp_{t})-h_{t}(\cmp_{t})$
$\displaystyle\qquad=D_{\psi_{1}}(\cmp_{1}|\w_{1})-D_{\psi_{T+1}}(\cmp_{T}|\w_{T+1})+\gamma\sum_{t=1}^{T-1}F_{t}^{\gamma}(\cmp_{\tpp})-F_{t}^{\gamma}(\cmp_{t})+\sum_{t=2}^{T}h_{\tpp}(\cmp_{t})-h_{t}(\cmp_{\tmm})+h_{2}(u_{1})-h_{1}(u_{1})$
$\displaystyle\qquad=D_{\psi_{1}}(\cmp_{1}|\w_{1})-D_{\psi_{T+1}}(\cmp_{T}|\w_{T+1})+h_{T+1}(\cmp_{T})-h_{1}(\cmp_{1})+\gamma\sum_{t=1}^{T-1}F_{t}^{\gamma}(\cmp_{\tpp})-F_{t}^{\gamma}(\cmp_{t}).$

Finally, observe that with $\w_{1}=\zeros$ and $\yhint_{1}=0$ we have

$\displaystyle
D_{\psi_{1}}(\cmp_{1}|\w_{1})=\psi_{1}(\cmp_{1})-\psi_{1}(\zeros)-\inner{\grad\psi_{1}(\zeros),\cmp_{1}}=h_{1}(\cmp_{1})+\gamma\ell_{0}(\cmp_{1})=h_{1}(\cmp_{1})+\frac{\gamma\lambda}{2}\norm{\cmp_{1}}^{2}_{2}$

so we can express the bound as the bound as

$\displaystyle\sum_{t=1}^{T}D_{\psi_{t}}(\cmp_{t}|\wt)-D_{\psi_{t}}(\cmp_{t}|\wtpp)+\sumtT
h_{\tpp}(\cmp_{t})-h_{t}(\cmp_{t})$
$\displaystyle\qquad\leq\frac{\gamma\lambda}{2}\norm{\cmp_{1}}^{2}_{2}+h_{T+1}(\cmp_{T})+\gamma\sum_{t=1}^{T-1}F_{t}^{\gamma}(\cmp_{\tpp})-F_{t}^{\gamma}(\cmp_{t}).$

###  1.3 Proof of Lemma LABEL:lemma:discounted-terms

The following lemma bounds the variability and stability terms from
thm:general-discounted-vaw to expose a more explicit trade-off in terms of the
discount factor $\gamma$. LABEL:lemma:discounted-terms Let
$\ell_{0},\ell_{1},\ldots,\ell_{T}$ be arbitrary non-negative functions,
$0<\gamma\leq\beta<1$, and
$F_{t}^{\gamma}(\w)=\sum_{s=0}^{t}\gamma^{t-s}\ell_{s}(\w)$. For all $t$,
define

$\displaystyle\bar{d}_{t}^{\beta}(u,v)=\frac{1}{\sum_{s=0}^{t}\beta^{t-s}}\sum_{s=0}^{t}\beta^{t-s}\sbrac{\ell_{s}(u)-\ell_{s}(v)}_{+}$

and let
$P_{T}^{\beta}(\vec{\cmp})=\sum_{t=1}^{T-1}\bar{d}_{t}^{\beta}(\cmp_{\tpp},\cmp_{t})$.
Then for any $V_{T}\geq 0$,

$\displaystyle\gamma\sum_{t=1}^{T-1}\sbrac{F_{t}^{\gamma}(\cmp_{\tpp})-F_{t}^{\gamma}(\cmp_{t})}+\Log{\frac{1}{\gamma}}V_{T}\leq\frac{\beta}{1-\beta}P_{T}^{\beta}(\vec{\cmp})+\frac{1-\gamma}{\gamma}V_{T}$

######  Proof 1.6.

The first summation can be bounded as

$\displaystyle\gamma\sum_{t=1}^{T-1}\sbrac{F_{t}^{\gamma}(\cmp_{t})-F_{t}^{\gamma}(\cmp_{\tmm})}$
$\displaystyle=\gamma\sum_{t=1}^{T-1}\sum_{s=0}^{t}\gamma^{t-s}\sbrac{\ell_{s}(\cmp_{\tpp})-\ell_{s}(\cmp_{t})}$
$\displaystyle\leq\gamma\sum_{t=1}^{T-1}\sum_{s=0}^{t}\gamma^{t-s}\sbrac{\ell_{s}(\cmp_{\tpp})-\ell_{s}(\cmp_{t})}_{+}$
$\displaystyle\leq\beta\sum_{t=1}^{T-1}\sum_{s=0}^{t}\frac{\sum_{s^{\prime}=0}^{t}\beta^{t-s^{\prime}}}{\sum_{s^{\prime}=0}^{t}\beta^{t-s^{\prime}}}\beta^{t-s}\sbrac{\ell_{s}(\cmp_{\tpp})-\ell_{s}(\cmp_{t})}_{+}$
$\displaystyle\leq\frac{\beta}{1-\beta}\sum_{t=1}^{T-1}\sum_{s=0}^{t}\frac{\beta^{t-s}}{\sum_{s^{\prime}=0}^{t}\beta^{t-s^{\prime}}}\sbrac{\ell_{s}(\cmp_{\tpp})-\ell_{s}(\cmp_{t})}_{+}$
$\displaystyle=\frac{\beta}{1-\beta}P_{T}^{\beta}(\vec{\cmp}),$

where the last inequality uses
$\sum_{s=0}^{t}\beta^{t-s}=\frac{1-\beta^{t+1}}{1-\beta}\leq\frac{1}{1-\beta}$.
Using this along with the elementary inequality $\Log{x}\leq x-1$, for any
$V_{T}\geq 0$ we have

$\displaystyle\gamma\sum_{t=1}^{T-1}\sbrac{F_{t}^{\gamma}(\cmp_{t})-F_{t}^{\gamma}(\cmp_{\tmm})}+\Log{\frac{1}{\gamma}}V_{T}$
$\displaystyle\leq\frac{\beta}{1-\beta}P_{T}^{\beta}(\vec{\cmp})+\brac{\frac{1}{\gamma}-1}V_{T}$
$\displaystyle=\frac{\beta}{1-\beta}P_{T}^{\beta}(\vec{\cmp})+\frac{1-\gamma}{\gamma}V_{T}$

###  1.4 Existence of a Good Discount Factor

The following lemma establishes the existence of a discount factor that will
lead to favorable tuning of the $\gamma$-dependent terms in lemma:discounted-
terms. lemmaGoodDiscountExistence Let $\ell_{0},\ell_{1},\ldots$ be arbitrary
non-negative functions, $V_{T}\geq 0$, denote
$\bar{d}_{t}^{\gamma}(u,v)=\frac{\sum_{s=0}^{t}\gamma^{t-s}\sbrac{\ell_{s}(u)-\ell_{s}(v)}_{+}}{\sum_{s=0}^{t}\gamma^{t-s}}$
for $\gamma\in[0,1]$, and let
$P_{T}^{\gamma}(\vec{\cmp})=\sum_{t=1}^{T-1}\bar{d}_{t}^{\gamma}(\cmp_{\tpp},\cmp_{t})$.
Then there is a $\gamma^{*}\in[0,1]$ such that

$\displaystyle\gamma^{*}=\frac{\sqrt{V_{T}}}{\sqrt{V_{T}}+\sqrt{P_{T}^{\gamma^{*}}(\vec{\cmp})}}.$

######  Proof 1.7.

First, notice that that any such $\gamma$ with the stated property must be in
$[0,1]$ since

$\displaystyle
0\leq\frac{\sqrt{V_{T}}}{\sqrt{V_{T}}+\sqrt{P_{T}^{\gamma}(\vec{\cmp})}}\leq\frac{\sqrt{V_{T}}}{\sqrt{V_{T}}}=1.$

Next, observe that the condition can be equivalently expressed as follows:

$\displaystyle\gamma$
$\displaystyle=\frac{\sqrt{V_{T}}}{\sqrt{V_{T}}+\sqrt{P_{T}^{\gamma}(\vec{\cmp})}}$
$\displaystyle\iff\sqrt{V_{T}}(1-\gamma)$
$\displaystyle=\gamma\sqrt{P_{T}^{\gamma}(\vec{\cmp})}$
$\displaystyle=\gamma\sqrt{\sum_{t=1}^{T-1}\sum_{s=0}^{t}\frac{\gamma^{t-s}}{\sum_{s=0}^{t}\gamma^{t-s}}\sbrac{\ell_{s}(\cmp_{\tpp})-\ell_{s}(\cmp_{t})}_{+}}$
$\displaystyle=\gamma\sqrt{\sum_{t=1}^{T-1}\sum_{s=0}^{t}\frac{\gamma^{t-s}}{1-\gamma^{t+1}}(1-\gamma)\sbrac{\ell_{s}(\cmp_{\tpp})-\ell_{s}(\cmp_{t})}_{+}}$
$\displaystyle\iff\sqrt{V_{T}(1-\gamma)}$
$\displaystyle=\gamma\sqrt{\sum_{t=1}^{T-1}\sum_{s=0}^{t}\frac{\gamma^{t-s}}{1-\gamma^{t+1}}\sbrac{\ell_{s}(\cmp_{\tpp})-\ell_{s}(\cmp_{t})}_{+}}.$

The quantity on the LHS begins at $\sqrt{V_{T}}$ (for $\gamma=0$) and then
decreases to $0$ as a function of $\gamma$. Likewise, the RHS begins at 0 (for
$\gamma=0$) and increases as a function of $\gamma$, approaching $\infty$ as
$\gamma\to 1$. Hence, there must be some $\gamma\in[0,1]$ at which the two
lines cross, and hence a $\gamma\in[0,1]$ which satisfies the above relation,
so there is a $\gamma\in[0,1]$ such that

$\displaystyle\gamma=\frac{\sqrt{V_{T}}}{\sqrt{V_{T}}+\sqrt{P_{T}^{\gamma}(\vec{\cmp})}}.$

###  1.5 Proof of Theorem LABEL:thm:oracle-tuning-discounted-vaw

Now combining everything we’ve seen in the previous sections, we can easily
prove the following bound for the discounted VAW forecaster under _oracle
tuning_ of the discount factor. *

######  Proof 1.8.

lemma:good-discount-existence shows that for any sequence
$\vec{\cmp}=(\cmp_{1},\ldots,\cmp_{T})$, there is a $\gamma^{*}\in[0,1]$ such
that

$\displaystyle\gamma^{*}=\frac{\sqrt{d\sumtT\half(\yt-\yhint_{t})^{2}}}{\sqrt{d\sumtT\half(\yt-\yhint_{t})^{2}}+\sqrt{P_{T}^{\gamma^{*}}(\vec{\cmp})}},$

so choosing $\gamma=\gamma^{*}$ and applying thm:general-discounted-vaw, we
have

$\displaystyle R_{T}(\vec{\cmp})$
$\displaystyle\leq\frac{\gamma^{*}\lambda}{2}\norm{\cmp_{1}}^{2}_{2}+\frac{d}{2}\max_{t}(\yt-\yhint_{t})^{2}\Log{1+\frac{\sumtT\norm{\x_{t}}^{2}_{2}}{\lambda
d}}$
$\displaystyle\qquad+\gamma^{*}\sum_{t=1}^{T-1}\sbrac{F_{t}^{\gamma^{*}}(\cmp_{\tpp})-F_{t}^{\gamma^{*}}(\cmp_{t})}+\frac{d}{2}\Log{1/\gamma^{*}}\sumtT(\yt-\yhint_{t})^{2}$
$\displaystyle\overset{(*)}{\leq}\frac{\lambda}{2}\norm{\cmp_{1}}^{2}_{2}+\frac{d}{2}\max_{t}(\yt-\yhint_{t})^{2}\Log{1+\frac{\sumtT\norm{\x_{t}}^{2}_{2}}{\lambda
d}}$
$\displaystyle\qquad+\frac{\gamma^{*}}{1-\gamma^{*}}P_{T}^{\gamma^{*}}(\vec{\cmp})+\frac{1-\gamma^{*}}{\gamma^{*}}\frac{d}{2}\sumtT(\yt-\yhint_{t})^{2}$
$\displaystyle=\frac{\lambda}{2}\norm{\cmp_{1}}^{2}_{2}+\frac{d}{2}\max_{t}(\yt-\yhint_{t})^{2}\Log{1+\frac{\sumtT\norm{\x_{t}}^{2}_{2}}{\lambda
d}}+\sqrt{2dP_{T}^{\gamma^{*}}(\vec{\cmp})\sumtT(\yt-\yhint_{t})^{2}}$

where $(*)$ uses lemma:discounted-terms (with $\beta=\gamma=\gamma^{*}$). The
stated result follows by hiding lower-order terms.