# Two-Tailed Averaging

Gábor Melis
<EMAIL_ADDRESS>
DeepMind, UCL; London, UK

###### Abstract

Tail Averaging improves on Polyak averaging’s non-asymptotic behaviour by
excluding a number of leading iterates of stochastic optimization from its
calculations. In practice, with a finite number of optimization steps and a
learning rate that cannot be annealed to zero, Tail Averaging can get much
closer to a local minimum point of the training loss than either the
individual iterates or the Polyak average. However, the number of leading
iterates to ignore is an important hyperparameter, and starting averaging too
early or too late leads to inefficient use of resources or suboptimal
solutions. Our work focusses on improving generalization, which makes setting
this hyperparameter even more difficult, especially in the presence of other
hyperparameters and overfitting. Furthermore, before averaging starts, the
loss is only weakly informative of the final performance, which makes early
stopping unreliable. To alleviate these problems, we propose an anytime
variant of Tail Averaging intended for improving generalization not pure
optimization, that has no hyperparameters and approximates the optimal tail at
all optimization steps. Our algorithm is based on two running averages with
adaptive lengths bounded in terms of the optimal tail length, one of which
achieves approximate optimality with some regularity. Requiring only the
additional storage for two sets of weights and periodic evaluation of the
loss, the proposed Two-Tailed Averaging algorithm is a practical and widely
applicable method for improving generalization.

##  1 Introduction

For the series of iterates produced by Stochastic Gradient Descent (SGD)
(Robbins and Monro, 1985) to converge to a local minimum point of the training
loss, the learning rate must be annealed to zero. Polyak averaging (Polyak and
Juditsky, 1992; Ruppert, 1988) improves on SGD and achieves a statistically
optimal convergence rate by averaging all iterates to produce the final
solution. Tail or suffix averaging (Jain et al., 2018; Rakhlin et al., 2011)
takes this further and improves the non-asymptotic behaviour by dropping a
number of leading iterates from the average, speeding up the decay of the
effect of the initial state while allowing the learning rate to stay constant.
Both of these properties are advantageous in practice, where a finite number
of optimization steps are taken, and because large learning rates may bias
optimization towards flatter and wider minima, which improves generalization
(Hochreiter and Schmidhuber, 1997; Keskar et al., 2016). Focussing on large
learning rates and generalization, Izmailov et al. (2018) propose Stochastic
Weight Averaging (SWA), which takes the same form as Tail Averaging but is
motivated from an ensembling point of view.

Tail Averaging starts after a given number of optimization steps. Setting this
hyperparameter to minimize the training loss already poses some difficulties,
which only become more pronounced and numerous in the context of
generalization, our primary focus in this work.

  * $\bullet$

Triggering averaging too early is inefficient as the average must grow long to
forget early weights.

  * $\bullet$

Triggering averaging too late is inefficient as it does not use valuable
information.

  * $\bullet$

Tuning dependent hyperparameters becomes harder.

  * $\bullet$

Early stopping is unreliable due to learning curves having a sudden drop at
the onset of averaging.

missing

Motivated by these problems, we propose the Two-Tailed Averaging algorithm
with the following features:

  * $\bullet$

_Anytime_ : An estimate of the optimal tail is available at all optimization
steps.

  * $\bullet$

_Adaptive_ : It has no hyperparameters. The number of weights averaged (the
_length_ of the tail) is determined adaptively based on the evolution of
generalization performance.

  * $\bullet$

_Optimal once in a while_ : The tail length achieves near optimality
regularly.

missing

The algorithm is very easy to implement. Its principal cost is the storage for
a second running average, and it also performs more evaluations of
generalization performance (e.g. the validation loss). The main idea, sketched
in Figure 1, is to maintain two running averages of optimization iterates: a
_short_ and a _long_ one, with the long average being our estimate of the
optimal weights.

Figure 1: Example evolution of the two running averages of weights over
optimization steps. Line segments indicate running averages whose length (the
number of optimization iterates averaged) is represented on the y axis. The
two averages start out the same, but after the first evaluation, there is
always one short (S) and one long (L) average, where the long one has more
iterates averaged and a better loss. When the loss with the short one is not
worse than with the long average, the long one is reset, and the short average
becomes the long one. These switch points are marked by dotted lines. In any
interval labeled with L, there is at least one point where the length of the
long average is near optimal.

##  2 Related Works

###  2.1 Averaging in Pure Optimization

Polyak averaging as originally proposed (Ruppert, 1988; Polyak and Juditsky,
1992) computes the equally weighted average
$\bar{\theta}_{t}=\frac{1}{t+1}\sum_{i=0}^{t}\theta_{i}$ of all iterates
$\theta_{i}$ from the optimizer up to the current time step $t$. The
convergence rate of $\bar{\theta}_{t}$ was analyzed in the convex case with an
appropriately decaying learning rate. Beyond this strictest interpretation,
Polyak (or Polyak–Ruppert) averaging may refer to using $\bar{\theta}_{t}$
without the convexity assumption, without a decaying learning rate, or with
another optimizer such as Adam (Kingma and Ba, 2014).

In practice, where finite budget considerations override the asymptotic
optimality guarantees offered by theory, Polyak averaging may refer to an
exponential moving average (EMA) of the form

$\displaystyle\bar{\theta}_{0}$ $\displaystyle=\theta_{0},$ (1)
$\displaystyle\bar{\theta}_{t}$
$\displaystyle=(1-\beta_{t})\theta_{t}+\beta_{t}\bar{\theta}_{t-1}$
$\displaystyle(t\geq 1),$

where $\beta_{t}<1$ may be a constant near $1$ or it may be scheduled as in
Martens (2020). The idea here is to improve the rate of decay of the effect of
the initial error by downweighting early iterates.

Tail Averaging (TA) (Jain et al., 2018), also known as Suffix Averaging
(Rakhlin et al., 2011), considers a finite optimization budget of $n$ steps
with a constant learning rate. At the cost of introducing a hyperparameter $s$
to control the start of averaging, it improves the rate of decay of the effect
of the initial error while obtaining near-minimax rates on the variance. Tail
Averaging is defined as

$\displaystyle\bar{\theta}_{t}$ $\displaystyle=\theta_{t}$
$\displaystyle\qquad(t<s),$ (2) $\displaystyle\bar{\theta}_{t}$
$\displaystyle=\frac{1}{t-s+1}\sum_{i=s}^{t}\theta_{i}$
$\displaystyle\qquad(t\geq s).$

Alternatively, the number of iterates to average may change in proportion to
the current time step:

$\displaystyle\bar{\theta}_{t}$ $\displaystyle=\frac{1}{\lceil
ct\rceil}\sum_{i=t+1-\lceil ct\rceil}^{t}\theta_{i}$
$\displaystyle\qquad(t\geq s),$

where $c\in(0,1)$ is a hyperparameter. Roux (2019) discusses how to
approximate averages of this form without excessive storage needs but do not
consider how to automatically adjust the length.

All in all, we have discussed a few representative averaging methods intended
for pure optimization but often repurposed for improving generalization by
tuning their hyperparameters. Although there are interesting developments in
this area (Shamir and Zhang, 2013; Lacoste-Julien et al., 2012), we now move
on to the main focus of this work, averaging for improving generalization.

###  2.2 Averaging for Generalization

In work parallel to Tail Averaging, Izmailov et al. (2018) propose Stochastic
Weight Averaging (SWA), an additional stage of optimization with a constant or
cyclical learning rate, which computes an equally weighted average of
iterates. SWA can be motivated heuristically in the following way: with the
high learning rate, it seeks out wider and flatter basins in the training loss
surface to improve generalization, but the high learning rate also prevents it
from reaching the bottom of the basin, so the weights bounce around it, thus
taking their average should land closer to the minimum point. The SWA
algorithm is almost identical to Tail Averaging (except for a possibly
cyclical learning rate and a periodic subsampling of iterates), but it is
motivated from the angle of ensembling and generalization not of optimization.

If our goal is to improve generalization, the decision of when to start
averaging the weights should depend on generalization performance. Indeed,
Merity et al. (2017) propose an algorithm much like SWA, where averaging is
triggered when the validation loss does not improve for a fixed number of
optimization steps, which trades one hyperparameter for another and is
sensitive to noise in the evaluation of the generalization loss. In other
related work, Guo et al. (2022) investigate the repeated application of SWA.
Their method is not informed by the validation loss and requires the schedule
of multiple SWA stages to be specified. Finally, taking the exponential moving
average of iterates is also sensitive to its hyperparameter, the decay rate.

In summary, existing averaging methods for generalization that behave well in
practice all have one or more hyperparameters to govern the weighting of early
iterates. Tuning these hyperparameters can be costly, particularly in the
presence of other hyperparameters and when training runs take a long time.
Furthermore, even with their hyperparameters, these methods are not flexible
enough to estimate the optimal average at multiple optimization steps in
general. We address these issues in the present work. The rest of this chapter
is structured as follows. In Section 3, we formally define the problem to
solve. In Section 4, we provide a description of the algorithm, whose
properties are analyzed in Section 5. We verify our analysis experimentally in
Section 6 and discuss the validity of our assumptions in Section 5.1.

##  3 Problem Statement

Let $\Theta$ be the parameter (or weight) space, $\theta_{t}\in\Theta$
$(t\in\mathbb{N}_{0})$ a sequence of iterates produced by stochastic
optimization with $\theta_{0}$ being the initial value, and
$f\colon\Theta\to\mathbb{R}$ the generalization loss function. We may choose
the generalization loss to simply be the validation loss, or it may measure
performance on a down-stream task. We assume the generalization loss is
evaluated periodically, every $E\in\mathbb{N}$ optimization steps, and it is
at these points $n\in[0,E,2E,3E,\dots]$ where we would like to know how many
of the most recent iterates to average to minimize it. Here and in the
following, $t$ and $n$ (with or without subscripts) are assumed to be from
$\mathbb{N}_{0}$ and $[0,E,2E,3E,\dots]$, respectively, and _loss_ always
refers to $f$. Denoting the average of most recent $\Delta$ iterates up to
time step $t$ with
$\operatorname*{avg}(t,\Delta)=\frac{1}{\Delta}\sum_{i=t+1-\Delta}^{t}\theta_{i}$,
we define the optimal averaging length as

$\displaystyle\mathcal{O}(t)=\operatorname*{arg\,min}_{\Delta\in[1,\dots,t]}f(\operatorname*{avg}(t,\Delta)).$

Our task is to approximate $\mathcal{O}(n)$ and
$\operatorname*{avg}(n,\mathcal{O}(n))$ at all evaluation steps $n$ during
optimization.

The trivial algorithm to find $\mathcal{O}(n)$, which saves all $\theta_{i}$
and performs a search over $\Delta\in[1,\dots,n]$ to minimize
$f(\operatorname*{avg}(n,\Delta))$, has prohibitive storage and evaluation
cost, proportional to $n$. Even assuming that $f$ improves monotonically in
$\Delta$ up to its optimum, the cost is still proportional to
$\mathcal{O}(n)$. Our proposed algorithm approximates $\mathcal{O}(n)$ and
$\operatorname*{avg}(n,\mathcal{O}(n))$ with a constant cost.

##  4 The Algorithm

Algorithm 1 The core Two-Tailed Averaging algorithm. It has 2 running
averages, a short one $\theta^{S}$ and a long one $\theta^{L}$ with $S\leq L$
number of optimization iterates averaged. If the loss with $\theta^{S}$
becomes lower or equal to the loss with $\theta^{L}$, then we empty the long
average, which becomes the short one.

1:generalization loss function $f$, optimization iterates $\theta_{t}$,
evaluation period $E$

2:$S,\theta^{S},L,\theta^{L}$ $\leftarrow$ $0,\mathbf{0},0,\mathbf{0}$

3:

4:procedure $add\\_weights$($\theta$)

5: $S,\theta^{S}$ $\leftarrow$ $S+1,\theta^{S}+(\theta-\theta^{S})/(S+1)$

6: $L,\theta^{L}$ $\leftarrow$ $L+1,\theta^{L}+(\theta-\theta^{L})/(L+1)$

7:

8:procedure $switch$

9: $S,L,\theta^{L}$ $\leftarrow$ $0,S,\theta^{S}$

10:

11:function $evaluate\\_and\\_adapt$($\theta,f$)

12: $F^{S},F^{L}$ $\leftarrow$ $f(\theta^{S}),f(\theta^{L})$

13: if $F^{S}\leq F^{L}$ then

14: $F^{L}$ $\leftarrow$ $F^{S}$

15: $switch()$

16: return $F^{L},\theta^{L},L$

17:

18:for $t\leftarrow 1,2,\dots$ do

19: $add\\_weights(\theta_{t})$

20: if $t\bmod E=0$ then

21: $f_{\bar{\theta}},\bar{\theta},len$ $\leftarrow$
$evaluate\\_and\\_adapt(\theta_{t},f)$

22: $report(t,f_{\bar{\theta}},\bar{\theta},len)$

Algorithm 1 specifies the core of Two-Tailed Averaging (2TA) in pseudocode,
which works as follows. The training loop iterates over weights $\theta_{t}$
produced by a stochastic optimizer, incorporating them into the short and long
running averages $\theta^{S}$, $\theta^{L}$ with lengths $S$ and $L$. Then,
every $E$ steps, the loss is evaluated with the short average $\theta^{S}$ and
with the long average $\theta^{L}$, giving $F^{S}$ and $F^{L}$. If $F^{S}$ is
at least as good as $F^{L}$, then we switch: the long average is reset, and
since that makes it the shorter of the two averages, we must switch their
labels. In other words, on a switch, the long average continues from the
current short average and the short average is restarted (see Figure 1). For
time step $t$, the estimate of the optimal averaging length is $L$, and
$\theta^{L}$ is the corresponding average.

Algorithm 2 Extensions to Two-Tailed Averaging. This is the version
recommended for use in practice. The parts unchanged from Algorithm 1 are
grayed out. There are two extensions. First, the short and long averages are
reset if they are stagnating (i.e. they have not improved for a few
evaluations). This reset heuristic makes the algorithm quicker to adapt when 4
is violated (see Section 5.1). Second, we defer to non-averaged weights very
early in training.

1:function $evaluate\\_and\\_adapt$($\theta,f$)

2: $F^{1},$$F^{S},F^{L}$ $\leftarrow$
$f(\theta),$$f(\theta^{S}),f(\theta^{L})$

3: if $F^{S}\leq F^{L}$ or $F^{L}$ is stagnating then

4: $F^{L}$ $\leftarrow$ $F^{S}$

5: $switch()$

6: else if $F^{S}$ is stagnating then

7: $S$ $\leftarrow$ $0$

8: if $L>1$ and $F^{1}\leq F^{L}$ then

9: if $L=E$ then

10: $S,L$ $\leftarrow$ $0,0$

11: return $F^{1},\theta,1$

12: return $F^{L},\theta^{L},L$

In Algorithm 2, we present two heuristic extensions to the core algorithm.
First, the long and short averages are reset if they have not improved for a
few evaluations. This reset heuristic is intended to handle cases where the
averages become too long, perhaps due to optimization escaping from one basin
of attraction to a better one or due to the loss surface changing in a non-
stationary environment. Second, we defer to the non-averaged weights very
early in training, where $f(\theta_{t})$ is still improving rapidly enough
that averaging the minimum $E$ iterates is worse than not averaging at all.

##  5 Analysis of the Algorithm

Our analysis hinges on simplifying assumptions, which follow from, for
example, a monotonically decreasing loss and averaging producing diminishing
returns as the length increases. They represent idealized circumstances; we
discuss their validity and failures in Section 5.1.

######  Assumption 1.

For all $n$, as a function of $\Delta\in[0,E,2E,\dots,\mathcal{O}_{E}(n)]$,
$f(\operatorname*{avg}(n,\Delta))$ is monotonically decreasing, where
$\mathcal{O}_{E}(n)=\lfloor\mathcal{O}(n)/E\rfloor E$. That is, for any given
evaluation step $n$, averaging more iterates from the past monotonically
improves $f$ until about the optimum length.

missing

######  Assumption 2.

For all $n$ and $n_{+}$, such that $n_{+}\geq\mathcal{O}^{E}(n)$,
$f(\operatorname*{avg}(n,\mathcal{O}^{E}(n)))\leq
f(\operatorname*{avg}(n,n_{+}))$, where
$\mathcal{O}^{E}(n)=\lceil\mathcal{O}(n)/E\rceil E$. That is, averaging
slightly more than optimal is better than averaging a lot more.

missing

######  Assumption 3.

$\forall n\colon\exists n_{s}\colon\mathcal{O}(n+n_{s})-\mathcal{O}(n)<n_{s}$,
that is, the optimal average forgets over a sufficiently long interval.

missing

######  Assumption 4.

$\mathcal{O}(n)\leq\mathcal{O}(n+E)$, that is, the optimal number of weights
to average is monotonically increasing from one evaluation to the next.

missing

Let $S(t)$, $\theta^{S}(t)$, $L(t)$, and $\theta^{L}(t)$ stand for the values
of variables $S$, $\theta^{S}$, $L$, and $\theta^{L}$ in Algorithm 1,
respectively, after $t$ times through the loop. Similarly, let
$S^{\prime}\\!(t)$, $\theta^{S^{\prime}\\!\\!}(t)$, $L^{\prime}\\!(t)$, and
$\theta^{L^{\prime}\\!\\!}(t)$ stand for the values of the same variables at
the same iteration but after 19 (i.e. before the possible switch of the short
and long averages). Furthermore, we introduce the shorthands
$f^{X}(t)=f(\operatorname*{avg}(t,X(t)))$ for
$X\in\\{S,S^{\prime},L,L^{\prime},\mathcal{O}\\}$ with $f^{X}(t)=+\infty$ if
$X(t)=0$.

######  Definition 1 (Switch point).

We say that $n$ is a switch point if at $t=n$ 15 is executed, that is, when
the short average becomes at least as good as the long average with respect to
the loss, and consequently the long average is reset. We denote the most
recent switch point before iteration $t$ with $\mathrm{SP}(t)$, where
$\mathrm{SP}(t)<t$. If there is no such switch point, then
$\mathrm{SP}(t)=-1$.

missing

4 states that the optimal averaging length monotonically increases, so to
simplify the analysis, without loss of generality, we assume throughout that
the raw loss $F^{1}$ has already been eclipsed by $F^{L}$ at the first
evaluation. We also assume that the reset heuristic cannot trigger. In effect,
we ignore the extensions in Algorithm 2 and analyze the core logic in
Algorithm 1. For the proofs of the following propositions, see Appendix A.

$0$$1$$2$$3$$4$$5$$6$$\mathcal{O}(n)$$\mathcal{O}(n+E)$$\mathcal{O}(n+2E)$$S^{\prime}\\!(n)$$S^{\prime}\\!(n+E)$$S^{\prime}\\!(n+2E)$$L^{\prime}\\!(n)$$L^{\prime}\\!(n+E)$$L^{\prime}\\!(n+2E)$$\Delta/E$$loss$$f(\operatorname*{avg}(n,\Delta))$$f(\operatorname*{avg}(n+E,\Delta))$$f(\operatorname*{avg}(n+2E,\Delta))$$\mathcal{O}(.)$$S^{\prime}\\!(.)$$L^{\prime}\\!(.)$
Figure 2: Idealized illustration of switching. The three curves show the loss
as a function of averaging length at three subsequent evaluations (at
optimization steps $n$, $n+E$, and $n+2E$). The raw loss keeps improving,
hence later evaluations have lower loss curves. The optimal averaging length
increases, $\mathcal{O}(n)\leq\mathcal{O}(n+E)\leq\mathcal{O}(n+2E)$, as per
4. At $t=n+2E$, where the loss of the short average dips below the loss of the
long average, the long average is reset, and the short average becomes the
long average, so we have $S(n+2E)=0$ and $L(n+2E)=S^{\prime}\\!(n+2E)$.

######  Proposition 1 (Bounds for the averaging lengths).

The lengths of the short and long averages are bounded as
$S(n)<\mathcal{O}(n)$ and $L(n)<2\mathcal{O}(n)+E$.

missingmissing

######  Proposition 2 (Infinite number of switch points).

Switch points keep coming, that is, $\forall n\colon\exists n_{s}\geq
n\colon\mathrm{SP}(n_{s})\neq-1$.

missingmissing

######  Proposition 3 (Once-in-a-while optimality).

Between any two subsequent switch points $n_{1}$ and $n_{2}$, the long average
is nearly optimal at least once. Formally, $\exists n\in[n_{1},n_{2}-E]\colon
L(n)=\mathcal{O}^{E}(n)\lor L(n)=\mathcal{O}_{E}(n)$.

missingmissing

In short, we have shown that the long average is at most twice as long as
optimal, there are infinitely many switch points, and between any two switch
points the long average is approximately optimal at least once. Our results
are in terms of lengths of averages, and relating the actual loss with the
long average $f^{L}$ to the loss with the optimal length $f^{\mathcal{O}}$
would be desirable. Here, we informally point out that, all things being
equal, the worse $f^{L}$ gets relative to $f^{\mathcal{O}}$, the quicker
$f^{S}$ is to catch up with $f^{L}$, making long periods of highly suboptimal
solution less likely. Formalizing this notion requires making further
assumptions about the loss-vs-averaging-length function (of the kind plotted
in Figure 2) and would make analysis considerably more cumbersome.

###  5.1 When Assumptions Fail

To augment the theoretical analysis, which is based on idealized assumptions,
we make the following observations. The strongest assumption by far is 1. It
says that increasing the averaging length monotonically improves $f$ until the
optimum. Since stochastic optimization produces noisy iterates, this does not
hold exactly in practice. However, the length of the shortest average is one
evaluation period, and its variance is inversely proportional to $E$. Thus,
the likelihood of noise posing a problem can be very small. In terms of the
loss, the algorithm is fairly robust to when the assumption holds only
approximately because small deviations of $f(\operatorname*{avg}(n,\Delta))$
from monotonicity can change switch times only when $f^{S}$ and $f^{L}$ are
close.

2 says that averaging slightly more iterates than optimal (i.e. rounded up to
the evaluation period) is better than averaging a lot more. This is a weak
assumption due to subsequent iterates being highly correlated. If it is
violated sporadically, the algorithm can fail to detect when the short average
becomes longer than optimal, which delays the switch.

3 failing means that the optimal average incorporates all new iterates without
ever dropping old ones. In this case, the short average, which is always
shorter than optimal, will be a constant number of iterates behind and its
loss will converge to the loss of the optimal average. If the long average is
shorter than optimal, then the same argument applies to it. If the long
average is longer than optimal, then eventually a switch will happen. In
either case, the loss of the long average converges to that of the optimal
average.

Regarding 4, $\mathcal{O}(n)\leq\mathcal{O}(n+E)$ can fail if the improvement
of the raw loss accelerates, but that is a rather uncommon and temporary
occurrence. It may also fail if the raw loss has started to worsen due to
overfitting or optimization has escaped from one basin to the next and the
average is slowly climbing the ridge separating them or when the loss
landscape changes during learning in a non-stationary environment. With the
exception of accelerating improvement, these are likely to be caught by the
reset heuristic, wherein the long average is reset if its loss does not
improve for a few evaluations (see Algorithm 2). The reset heuristic can
trigger when it should not, i.e. when 4 holds. Such a spurious reset makes the
estimate of the long average worse either directly or indirectly by delaying
the next switch. Either way, without further violations of this assumption,
the algorithm recovers by the next switch. Note that 2TA cannot in general
correct overfitting, although the reset heuristic may help in the unlikely
event that overfitting is transitory.

All in all, we can expect the algorithm to display some degree of robustness
to minor violations of the assumptions. In practice, we recommend choosing a
reasonably large $E$ to reduce the noise originating from the stochasticity of
optimization.

###  5.2 A Note on Pure Optimization

Applying 2TA to pure optimization is unlikely to bring about practical
benefits because of the evaluation cost. For example, if $f$ computes the loss
over the entire training set and evaluation is performed every epoch, then the
cost of optimization is effectively doubled. Furthermore, as we have pointed
out above, 1 does not hold exactly with stochastic optimization: the short
average can get lucky and become better than the long one (causing a switch)
but then quickly succumb to variance and become worse as new iterates are
added to it. Thus, the averaged weights of Algorithms 1 and 2 do not converge
in the strict sense, although this point is somewhat moot because – due to the
mismatch between the true and the training losses – convergence in the
training loss is almost never desirable when optimizing for generalization.
Nevertheless, it is instructive to consider how the algorithm behaves when $f$
is the training loss as the limit of the common case where $f$ is the
validation loss, both the training and the validation sets consist of i.i.d.
samples from the same distribution, and their sizes tend to infinity.
Focussing on the setting where convergence results are available for Polyak
and Tail Averaging, we show in Appendix B that 2TA converges in probability to
the optimum in ordinary least squares regression. We also show that the losses
of the short averages at switch points monotonically decrease if $f$ is
convex.

##  6 Experiments

Figure 3: Validation loss with Two-Tailed Averaging (2TA, green), Tail
Averaging (TA, orange), and an exponential moving average (EMA, blue) of
weights on language modelling on Penn Treebank. For both TA and EMA, their
hyperparameters (the start time and the decay rate) were tuned to minimize the
final loss, so it is not a surprise that all three have similar optima. 2TA
has no hyperparameters and produces much better early solutions. These two
factors make tuning easier and early stopping much more reliable.
Additionally, the noise in the raw loss is effectively smoothed out. Note that
while the 2TA loss decreases monotonically, gentler and steeper slopes are
manifest before and after switch points, respectively. Figure 4: Length of the
long average ($L$) vs number of evaluations of 2TA in Figure 3. Note how the
heights of both peaks and valleys increase almost monotonically. Also, the
correspondence between this figure and the schematic in Figure 1 is
illustrated on one of the $S$ and $L$ intervals.

Tail Averaging or Stochastic Weight Averaging have been shown previously to be
beneficial not only in theory and on simulated data (Jain et al., 2018) but
also in language modelling (Merity et al., 2017; Melis et al., 2019) and image
classification (Izmailov et al., 2018) experiments. Hence, in this work, we
restrict our attention to experiments in a single domain to corroborate the
analysis in Section 5. Our goals are to _i)_ verify that 2TA is on par with
well-tuned TA and EMA, _ii)_ explore the effect of basing the switching logic
on the training instead of the validation loss, _iii)_ demonstrate robustness
to the choice of evaluation period, _iv)_ and check whether the assumptions in
Section 5 hold in practice.

In particular, we trained a recurrent language model with several
hyperparameters on Penn Treebank (Mikolov et al., 2010) using the Rectified
Adam optimizer (Liu et al., 2019), evaluating every 1000 optimization steps.
The hyperparameters were tuned separately for 2TA, TA eq. 2, and EMA eq. 1.
Figure 3 shows that the final validation losses with all methods are very
close, but early losses with 2TA are much better. This is expected because TA
and EMA are not flexible enough to produce optimal averaging lengths at
multiple points along the learning curve despite having an extra
hyperparameter. Conversely, 2TA has at least one nearly optimal solution
between any two subsequent peaks (i.e. switch points) in Figure 4 despite
having no hyperparameters.

We also tried the version of the algorithm where the switching logic was based
on comparison of the training losses of the short and long averages instead of
the validation losses, but the true validation losses were reported. On this
particular language modelling task, the best validation loss with the modified
algorithm worsened moderately (3.93 vs 3.92) and was well below the raw
validation loss (4.02). Results on the test set exhibited the same gap. Since
the modified 2TA was minimizing the training loss, the smoothness of the
reported validation losses observed in Figure 3 were lost in the process.
Similar results were obtained by scheduling a learning rate drop without
averaging.

To explore the effect of the evaluation period $E$, we tuned models with four
times larger and four times smaller $E$ than in our previously discussed
experiments. As expected, the best final results were very close to each
other, with shorter periods having an advantage early in training as the raw
loss $F^{1}$ was more quickly eclipsed by $F^{L}$.

In addition, we found that the assumptions made in Section 5 held rather well:
$F^{L}$ in Figure 3, and the averaging lengths tended to change monotonically
(see heights of peaks and valleys in Figure 4), making our length-based
theoretical results more closely linked to the actual loss. When that was not
the case, we found that the raw loss $F^{1}$ had started to worsen due to
overfitting or, much more rarely, optimization had entered a new basin,
violating 4. Figure 5 and Figure 6 demonstrate the reset heuristic being
triggered in these cases. Finally, TA and 2TA having almost identical final
validation losses weakly supports our assumptions, although a conclusive
demonstration would need to plot the results obtained with TA tuned separately
for each evaluation.

##  7 Conclusions

Figure 5: Raw (green) and 2TA (orange) validation loss with overfitting. The
averaged loss bottoms out due to overfitting. Thus when the averages are reset
(twice), the validation loss does not recover. Although the losses reported
after the reset are suboptimal, it does not really matter as a better loss was
reported already.

(a) Validation loss $F^{L}$.

(b) Length $L$.

Figure 6: Example of optimization entering a new basin. At $t=40E$ the
validation loss with the long average bottoms out and starts to slightly
worsen. This is detected at $t=43E$, and both averages are reset. With the
averages now way too short, the loss spikes but then recovers.

Tail averaging improves on Polyak averaging’s non-asymptotic behaviour by
excluding a number of leading iterates of stochastic optimization from its
calculations. In practice, with a finite number of optimization steps and a
learning rate that cannot be annealed to zero, Tail Averaging can get much
closer to a local minimum point of the training loss than either the
individual iterates or the Polyak average. However, the number of leading
iterates to ignore is an important hyperparameter, and starting averaging too
early or too late leads to inefficient use of resources or suboptimal
solutions. Our work focussed on improving generalization, which makes setting
this hyperparameter even more difficult, especially in the presence of other
hyperparameters and overfitting. Furthermore, before averaging starts, the
loss is only weakly informative of the final performance, which makes early
stopping unreliable. To alleviate these problems, we propose an anytime
variant of Tail Averaging intended for improving generalization not pure
optimization that has no hyperparameters and approximates the optimal tail at
all optimization steps. Our algorithm is based on two running averages with
adaptive lengths bounded in terms of the optimal tail length, one of which
achieves approximate optimality with some regularity.

In summary, we presented a variant of Tail Averaging and Stochastic Weight
Averaging based on two running averages. Compared to them, Two-Tailed
Averaging requires additional storage for the second running average and
relies on periodic evaluation of generalization performance. In return, 2TA
removes a hyperparameter and provides an estimate of the optimal tail at all
optimization steps. This makes hyperparameter tuning easier and early
evaluation more representative of final performance, allowing it to support
early and anytime stopping better. Owing to its simplicity, low implementation
cost and adaptivity, 2TA is a practical and widely applicable method for
improving generalization.

Looking beyond the scope of this work, exploring the relationship between
iterate averaging and learning rate schedules is a promising direction as
existing (Merity et al., 2017) and our own limited experimental results
indicate that dropping the learning rate and Tail Averaging perform
comparably. The properties of our algorithm are particularly compelling for
continual learning: by allowing the learning rate to remain high and being
able to adapt the averaging length to changing circumstances, 2TA lets the
model maintain high plasticity while reaping the benefits of averaging.

In addition, averaging weights can be viewed as a cheap approximation to
averaging predictions when the averaged weights reside in a region with a
suitable geometry. The combination of averaging weights within such regions
and averaging predictions over regions (each with its own weight average)
could potentially achieve a better loss than weight averaging alone at much
lower storage and evaluation cost than pure prediction averaging. We leave
these avenues for future work to explore.

## References

  * Guo et al. (2022) Hao Guo, Jiyong Jin, and Bin Liu.  Stochastic weight averaging revisited.  _arXiv preprint arXiv:2201.00519_ , 2022.
  * Hochreiter and Schmidhuber (1997) Sepp Hochreiter and Jürgen Schmidhuber.  Flat minima.  _Neural computation_ , 9(1):1–42, 1997.
  * Izmailov et al. (2018) Pavel Izmailov, Dmitrii Podoprikhin, Timur Garipov, Dmitry Vetrov, and Andrew Gordon Wilson.  Averaging weights leads to wider optima and better generalization.  _arXiv preprint arXiv:1803.05407_ , 2018.
  * Jain et al. (2018) Prateek Jain, Sham Kakade, Rahul Kidambi, Praneeth Netrapalli, and Aaron Sidford.  Parallelizing stochastic gradient descent for least squares regression: mini-batching, averaging, and model misspecification.  _Journal of Machine Learning Research_ , 18, 2018.
  * Keskar et al. (2016) Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang.  On large-batch training for deep learning: Generalization gap and sharp minima.  _arXiv preprint arXiv:1609.04836_ , 2016.
  * Kingma and Ba (2014) Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * Lacoste-Julien et al. (2012) Simon Lacoste-Julien, Mark Schmidt, and Francis Bach.  A simpler approach to obtaining an o (1/t) convergence rate for the projected stochastic subgradient method.  _arXiv preprint arXiv:1212.2002_ , 2012.
  * Liu et al. (2019) Liyuan Liu, Haoming Jiang, Pengcheng He, Weizhu Chen, Xiaodong Liu, Jianfeng Gao, and Jiawei Han.  On the variance of the adaptive learning rate and beyond.  _arXiv preprint arXiv:1908.03265_ , 2019.
  * Martens (2020) James Martens.  New insights and perspectives on the natural gradient method.  _The Journal of Machine Learning Research_ , 21(1):5776–5851, 2020.
  * Melis et al. (2019) Gábor Melis, Tomáš Kočiskỳ, and Phil Blunsom.  Mogrifier LSTM.  _arXiv preprint arXiv:1909.01792_ , 2019.
  * Merity et al. (2017) Stephen Merity, Nitish Shirish Keskar, and Richard Socher.  Regularizing and optimizing LSTM language models.  _arXiv preprint arXiv:1708.02182_ , 2017.
  * Mikolov et al. (2010) Tomas Mikolov, Martin Karafiát, Lukas Burget, Jan Cernockỳ, and Sanjeev Khudanpur.  Recurrent neural network based language model.  In _Interspeech_ , volume 2, page 3, 2010.
  * Polyak and Juditsky (1992) Boris T Polyak and Anatoli B Juditsky.  Acceleration of stochastic approximation by averaging.  _SIAM journal on control and optimization_ , 30(4):838–855, 1992.
  * Rakhlin et al. (2011) Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan.  Making gradient descent optimal for strongly convex stochastic optimization.  _arXiv preprint arXiv:1109.5647_ , 2011.
  * Robbins and Monro (1985) Herbert Robbins and Sutton Monro.  A stochastic approximation method.  In _Herbert Robbins Selected Papers_ , pages 102–109. Springer, 1985\.
  * Roux (2019) Nicolas Le Roux.  Anytime tail averaging, 2019.
  * Ruppert (1988) David Ruppert.  Efficient estimations from a slowly convergent Robbins-Monro process.  Technical report, Cornell University Operations Research and Industrial Engineering, 1988.
  * Shamir and Zhang (2013) Ohad Shamir and Tong Zhang.  Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes.  In _International conference on machine learning_ , pages 71–79. PMLR, 2013.
  * Yu et al. (2020) Lu Yu, Krishnakumar Balasubramanian, Stanislav Volgushev, and Murat A Erdogdu.  An analysis of constant step size SGD in the non-convex regime: Asymptotic normality and bias.  _arXiv preprint arXiv:2006.07904v2_ , 2020.

##  Appendix A Proofs for the Analysis of the Algorithm

First, we list a couple of basic properties then restate the propositions from
Section 5 and provide proofs.

######  Proposition 4 (Basic properties).

$\forall t\geq E\colon$ and $\forall n\geq E\colon$

  1. (i)

$E\mathrel{|}S(n)$, $E\mathrel{|}L(n)$

  2. (ii)

$S(n)\leq L(n)\leq n$

  3. (iii)

$f^{S}(n)>f^{L}(n)$

  4. (iv)

$L(t)=S(t)+S^{\prime}\\!(\mathrm{SP}(t))$ if $\mathrm{SP}(t)\neq-1$ else
$L(t)=S(t)$

missing

missing

Item i states that the averaging lengths are multiples of the evaluation
period; ii follows from that the lengths increase by 1 at every iteration
except at switches, where $S$ is reset to $0$; iii is because we switch if it
is not true; and iv expresses that all long averages except the first are
continuations of the previous short average.

See 1

  * We prove $S(n)<\mathcal{O}(n)$ by contradiction. Suppose $\mathcal{O}(n_{0})\leq S(n_{0})$ for some $n_{0}$. As $\mathcal{O}(n)$ is monotonically increasing and $S(n)$ increases by $E$, there exists $n\leq n_{0}$ such that $\mathcal{O}^{E}(n)=S(n)$. Since $S(n)\leq L(n)$ (by ii of Proposition 4), from 2 and $\mathcal{O}^{E}(n)=S(n)\leq L(n)$, we have that $f^{S}(n)\leq f^{L}(n)$, which contradicts iii of Proposition 4.

Next, we prove $L(n)<2\mathcal{O}(n)+E$. From iv of Proposition 4, we have
that at the beginning, when there has not yet been a switch, $L(t)=S(t)$, else
$L(t)=S(t)+S^{\prime}\\!(\mathrm{SP}(t))$ for all $t$. In the first case,
$L(n)=S(n)<\mathcal{O}(n)<2\mathcal{O}(n)+E$, and we are done.

In the second, usual case, $L(n)=S(n)+S^{\prime}\\!(\mathrm{SP}(n))$. That is,
the length of the current long average is the sum of the lengths of the
current and the previously finished short average. Since $S(n)<\mathcal{O}(n)$
and $S^{\prime}\\!(\mathrm{SP}(n))=S(\mathrm{SP}(n)-E)+E$, so
$L(n)<\mathcal{O}(n)+S(\mathrm{SP}(n)-E)+E$, from which
$L(n)<\mathcal{O}(n)+\mathcal{O}(\mathrm{SP}(n)-E)+E$. Finally, from the
monotonicity of $O$ in 4, $\mathcal{O}(\mathrm{SP}(n)-E)\leq\mathcal{O}(n)$,
we get $L(n)<2\mathcal{O}(n)+E$. ∎

missing

See 2

  * Because $S(n)<\mathcal{O}(n)$ and $S(n)$ increases by $E$ between switch points, it must catch $\mathcal{O}(n)$ at some step $n_{s}$ because $\mathcal{O}(n)$ grows more slowly by 3. At the point where $S(n_{s})=\mathcal{O}^{E}(n_{s})$, $f^{S}(n_{s})\leq f^{L}(n_{s})$ by 2, thus there must be a switch. ∎

missing

See 3

  * Since $S(n)<\mathcal{O}(n)$ and $E\mathrel{|}S(n)$ for all $n$, so $S^{\prime}\\!(n_{1})\leq\mathcal{O}^{E}(n_{1})$. Then it is either that $S^{\prime}\\!(n_{1})=\mathcal{O}^{E}(n_{1})$ or $S^{\prime}\\!(n_{1})<\mathcal{O}(n_{1})$. Since at switch points $L(n)=S^{\prime}\\!(n)$, in the former case, we conclude the proof with $L(n_{1})=\mathcal{O}^{E}(n_{1})$. Considering the latter case, $L(n_{1})=S^{\prime}\\!(n_{1})<\mathcal{O}(n_{1})$, so $L(n_{1})\leq\mathcal{O}_{E}(n_{1})$. Also, switches happen when $f^{S^{\prime}\\!\\!}(n)\leq f^{L^{\prime}\\!\\!}(n)$, but as per 1 this can happen only if $\mathcal{O}(n)<L^{\prime}\\!(n)$. Thus for $n_{2}$ to be a switch point, it must be that $\mathcal{O}(n_{2})<L^{\prime}\\!(n_{2})=L(n_{2}-E)+E$, hence $\mathcal{O}_{E}(n_{2})\leq L(n_{2}-E)$. Combining it with $L(n_{1})\leq\mathcal{O}_{E}(n_{1})$, we get $L(n_{1})\leq\mathcal{O}_{E}(n_{1})\leq\mathcal{O}_{E}(n_{2})\leq L(n_{2}-E)$. Therefore, since $L(n)$ and $\mathcal{O}_{E}(n)$ are monotonically increasing over $[n_{1},n_{2}-E]$, both take values that are multiples of $E$, and $L$ overtakes $\mathcal{O}_{E}$ while not skipping any such value, there must be a point $n$ where $L$ is equal to $\mathcal{O}_{E}$. ∎

missing

##  Appendix B Properties of 2TA in the Pure Optimization Setting

Here, we prove the claim from Section 5.2 that 2TA converges to the optimal
weights in the ordinary least squares regression setting, where the
generalization and training losses are the same.

######  Definition 2 ($N$th switch point).

For all $N\in\mathbb{N}$, we define three random variables:

  * $\bullet$

$Q_{N}\in[E,2E,\dots]$ is the time step corresponding to the $N$th switch
point.

  * $\bullet$

$F_{N}=f(\theta^{S^{\prime}}(Q_{N}))$ is the loss with the $N$th short average
just before it becomes the long average.

  * $\bullet$

$S_{N}=S^{\prime}(Q_{N})$ is the final length of the $N$th short average.

missing

missing

From now on, we use $N$ to index switch points or to refer to short averages
that end at that switch point.

######  Proposition 5.

If the generalization loss function $f$ is convex, then
$(F_{N})_{N\in\mathbb{N}}$ is monotonically decreasing.

missing

  * The long-averaged weights are a convex combination of the weights of the current and the previous short averages:

$\displaystyle\theta^{L^{\prime}\\!\\!}(n)=\alpha\theta^{S^{\prime}\\!\\!}(n)+(1-\alpha)\theta^{S^{\prime}\\!\\!}(\mathrm{SP}(n))$
$\displaystyle\alpha=\frac{S^{\prime}\\!(n)}{S^{\prime}\\!(n)+S^{\prime}\\!(\mathrm{SP}(n))}\in(0,1).$

Switching happens when $f(\theta^{S^{\prime}}(n))\leq
f(\theta^{L^{\prime}}(n))$. Expanding $\theta^{L^{\prime}\\!\\!}(n)$ and using
that $f$ is convex, we get

$\displaystyle f(\theta^{S^{\prime}\\!\\!}(n))$ $\displaystyle\leq
f(\theta^{L^{\prime}\\!\\!}(n))$
$\displaystyle=f(\alpha\theta^{S^{\prime}\\!\\!}(n)+(1-\alpha)\theta^{S^{\prime}\\!\\!}(\mathrm{SP}(n)))$
$\displaystyle\leq\alpha
f(\theta^{S^{\prime}\\!\\!}(n))+(1-\alpha)f(\theta^{S^{\prime}\\!\\!}(\mathrm{SP}(n))),$

from which,
$(1-\alpha)f(\theta^{S^{\prime}\\!\\!}(n))\leq(1-\alpha)f(\theta^{S^{\prime}\\!\\!}(\mathrm{SP}(n)))$.
Using $\alpha<1$, we get $f(\theta^{S^{\prime}\\!\\!}(n))\leq
f(\theta^{S^{\prime}\\!\\!}(\mathrm{SP}(n)))$. This is true at all switch
points, hence $F_{N+1}\leq F_{N}$ for all $N$. ∎

missing

Note that in non-convex settings, the above monotonicity property could be
enforced also by changing the switching condition to
$f(\theta^{S^{\prime}\\!\\!}(n))\leq\min(f(\theta^{L^{\prime}\\!\\!}(n)),\allowbreak
f(\theta^{S^{\prime}\\!\\!}(\mathrm{SP}(n)))$. However, this would make the
algorithm less able to adapt to violations of 4.

######  Proposition 6.

Assume that the loss function is bounded from below, the
$(F_{N})_{N\in\mathbb{N}}$ sequence monotonically decreases, and that
$(\theta_{t})_{t\in\mathbb{N}_{0}}$ approaches a stationary distribution with
a density. Then, $L(t)\mathrel{\mathop{\to}\limits^{\vbox
to0.0pt{\kern-3.0pt\hbox{$\scriptstyle p$}\vss}}}\infty$.

missing

  * First, we prove $S_{N}\mathrel{\mathop{\to}\limits^{\vbox to0.0pt{\kern-3.0pt\hbox{$\scriptstyle p$}\vss}}}\infty$ by contradiction. Assume that $S_{N}\centernot{\mathrel{\mathop{\to}\limits^{\vbox to0.0pt{\kern-3.0pt\hbox{$\scriptstyle p$}\vss}}}}\infty$.

    1. (i)

_For some $l_{0}\in\mathbb{N}$ and $\epsilon_{0}>0$, there are infinitely many
$N^{+}\in\mathbb{N}$ such that $P(S_{N^{+}}=l_{0})>\epsilon_{0}$._
_Proof._ By the definition of convergence in probability,
$S_{n}\mathrel{\mathop{\to}\limits^{\vbox
to0.0pt{\kern-3.0pt\hbox{$\scriptstyle p$}\vss}}}\infty$ is equivalent to
$\forall l\in\mathbb{N}\colon\lim_{N\to\infty}P(S_{N}\leq l)=0$. Suppose that
is false, hence $\exists l\in\mathbb{N},\epsilon>0\colon\forall
N\in\mathbb{N}\colon\exists N^{+}>N\colon P(S_{N^{+}}\leq l)>\epsilon$. Then,
we have an infinite number of short averages $N^{+}$ that are at most length
$l$ with at least $\epsilon$ probability: $P(S_{N^{+}}\leq l)>\epsilon$. Since
$l$ is finite, for all such $N^{+}$, there exists $l_{N^{+}}\in\mathbb{N}$
such that $P(S_{N^{+}}=l_{N^{+}})>\epsilon/l$. Hence, there must be at least
one $l_{0}\leq l$ and $\epsilon_{0}>0$ such that
$P(S_{N^{+}}=l_{0})>\epsilon_{0}$ for infinitely many $N^{+}$.

    2. (ii)

_The final losses of the short averages converge in probability:
$F_{N}\mathrel{\mathop{\to}\limits^{\vbox
to0.0pt{\kern-3.0pt\hbox{$\scriptstyle p$}\vss}}}F^{*}$._
_Proof._ From the assumption that the loss function is bounded from below and
that all realizations of the $F_{N}$ sequence decrease monotonically, all
realizations must converge, which implies almost sure convergence hence
convergence in probability.

    3. (iii)

_Let $F^{l_{0}+}_{N}$ denote what the loss of $N$th short average at length
$l_{0}$ would be if the algorithm were modified to perform no switching for
this short average only. Then, $P(F^{*}\leq F^{l_{0}+}_{N}\leq F_{N-1})\to
0$._
_Proof._ We have assumed that iterates converge to a stationary distribution
with a density. Note that this rules out convergence in the strict sense,
which would require a zero-variance stationary distribution. For any random
variable $X$ with a density, $lim_{\delta\to 0}P(a\leq X\leq a+\delta)=0$ for
all $a\in\mathbb{R}$. By ii, $F_{N}\mathrel{\mathop{\to}\limits^{\vbox
to0.0pt{\kern-3.0pt\hbox{$\scriptstyle p$}\vss}}}F^{*}$, so for all
$\epsilon>0$, $P(F_{N}-F^{*}<\epsilon)$ is close to $1$ for all large enough
$N$. With $F_{N-1}-F^{*}$, the size of the interval into which
$F^{l_{0}+}_{N}$ must fit, thus bounded uniformly in probability, we get
$P(F^{*}\leq\smash{F^{l_{0}+}_{N}}\leq F_{N-1})\to 0$.

missing

We assumed that $S_{N}\centernot{\mathrel{\mathop{\to}\limits^{\vbox
to0.0pt{\kern-3.0pt\hbox{$\scriptstyle p$}\vss}}}}\infty$ and in i showed that
$P(S_{N^{+}}=l_{0})>\epsilon_{0}$ for some $l_{0}\in\mathbb{N}$,
$\epsilon_{0}>0$ and infinitely many $N^{+}$. Since $S_{N}=l_{0}$ implies
$F_{N}=F^{l_{0}+}_{N}$ for any $N$, we have that
$P(F_{N^{+}}=\smash{F^{l_{0}+}_{N^{+}}})>\epsilon_{0}$. However, due to the
monotonicity assumption, $F^{*}\leq F_{N}\leq F_{N-1}$ for all $N$, hence
$P(F^{*}\leq\smash{F^{l_{0}+}_{N^{+}}}\leq F_{N^{+}-1})>\epsilon_{0}$, which
contradicts $P(\smash{F^{*}}\leq\smash{F^{l_{0}+}_{N}}\leq F_{N-1})\to 0$ from
iii.

Finally, every long average except the first is a continuation of the previous
short average, that is, for all $t\geq E$, $L(t)\geq
S^{\prime}(\mathrm{SP}(t))$ and $S^{\prime}(\mathrm{SP}(t))=S_{N}$ for some
$N$. Therefore, $S_{N}\mathrel{\mathop{\to}\limits^{\vbox
to0.0pt{\kern-3.0pt\hbox{$\scriptstyle p$}\vss}}}\infty$ implies that
$L(t)\mathrel{\mathop{\to}\limits^{\vbox
to0.0pt{\kern-3.0pt\hbox{$\scriptstyle p$}\vss}}}\infty$. ∎

missing

######  Proposition 7.

Consider applying SGD with a constant learning rate to an ordinary least
squares problem with unique minimum point $\theta^{\star}$. Then, for a
sufficiently low learning rate,
$\theta^{L}(t)\mathrel{\mathop{\to}\limits^{\vbox
to0.0pt{\kern-3.0pt\hbox{$\scriptstyle p$}\vss}}}\theta^{\star}$.

missing

  * The loss function is convex, so $F_{N}$ is monotonically decreasing by Proposition 5. It is also bounded from below, and it satisfies Assumptions 2.1-2.3 of Yu et al. (2020), hence – by Proposition 2 therein – SGD iterates admit a unique stationary distribution for an appropriately bounded learning rate. Thus, appealing to Proposition 6, we have that $L(t)\mathrel{\mathop{\to}\limits^{\vbox to0.0pt{\kern-3.0pt\hbox{$\scriptstyle p$}\vss}}}\infty$. In the ordinary least squares regression setting, Jain et al. (2018) prove that Tail Averaging converges to the optimum with an appropriately bounded learning rate. Hence, by choosing a learning rate that satisfies both bounds and leveraging the fact that $\theta^{L}(t)$ is a tail average, we get $\theta^{L}(t)\mathrel{\mathop{\to}\limits^{\vbox to0.0pt{\kern-3.0pt\hbox{$\scriptstyle p$}\vss}}}\theta^{\star}$. ∎

missing

Paralleling strict convergence results for Polyak and Tail Averaging, we have
proved that 2TA converges in probability to the optimum in the ordinary least
squares regression setting when $f$ is the training loss. We stress again that
2TA is not intended for pure optimization, and this result is to serve as a
characterization of behaviour in the infinite data case.

With pure optimization very much a secondary consideration, we provide only
weak, anecdotal support for the rate of convergence: the length of the long
average tended to increase exponentially in all experiments described in
Section 6 and also on simple synthetic data. Intuitively, this is to be
expected when $f$ is locally convex because at stationarity, every time a
short average finishes at length $l$, it halves the probability mass available
for subsequent short averages to finish at that length:
$P(\smash{F^{l}_{N+1}}\leq F_{N}\mid S_{N+1}\geq l,\ S_{N}=l)\to
0.5P(\smash{F^{l}_{N}}\leq F_{N-1}\mid S_{N}\geq l)$. This halving effect is
strongest at the same length, but in diminished form, it extends to longer
averages due to the similarity of their distributions.


11institutetext: Goldsmiths, University of London, London, UK 11email:
{n.jamalian<EMAIL_ADDRESS>
22institutetext: Nokia Bell Labs, Cambridge, UK 22email:
{marios.constantinides, sagar.joglekar<EMAIL_ADDRESS>

# Our Nudges, Our Selves: Tailoring Mobile User Engagement Using Personality

Nima Jamalian 11 Marios Constantinides(✉) 22 Sagar Joglekar 22 Xueni Pan 11
Daniele Quercia 22

###### Abstract

To increase mobile user engagement, current apps employ a variety of
behavioral nudges, but these engagement techniques are applied in a one-size-
fits-all approach. Yet the very same techniques may be perceived differently
by different individuals. To test this, we developed HarrySpotter, a location-
based AR app that embedded six engagement techniques. We deployed it in a
2-week study involving 29 users who also took the Big-Five personality test.
Preferences for specific engagement techniques are not only descriptive but
also predictive of personality traits. The Adj. $R^{2}$ ranges from 0.16 for
conscientious users (encouraged by competition) to 0.32 for neurotic users
(self-centered and focused on their own achievements), and even up to 0.61 for
extroverts (motivated by both exploration of objects and places). These
findings suggest that these techniques need to be personalized in the future.

###### Keywords:

mobile engagement gamification personality traits personalization.

##  1 Introduction

User engagement is crucial for the success of mobile apps, especially in
modern Internet companies [20]. Mobile apps employ various techniques to
capture users’ attention and increase their engagement. For example,
Foursquare introduced game mechanics to enhance engagement [24]. Users could
check-in at venues and inform their friends about their location. However,
since not all friends may use the app, incentivizing early adopters became
vital for the app’s success. To motivate early adopters, Foursquare introduced
badges, appealing to their desire for status. By default, the app shared this
activity on social media platforms like Twitter, creating a sense of
accomplishment and effectively engaging users. In general, engagement
strategies, such as badges and rewards [4, 32]), encompass various mechanisms
to increase user engagement [10]. However, most current mobile apps follow a
one-size-fits-all approach [23, 33], where all users are exposed to the same
engagement techniques.

While users’ personality has been extensively studied in various domains and
linked to diverse aspects including online browsing behavior [3, 19, 30] and
patterns of behavior collected with smartphones [35], limited research has
investigated its influence on mobile user engagement. To explore the
relationship between personality and engagement strategies, we developed and
deployed a location-based Augmented Reality (AR) mobile app called
HarrySpotter, which incorporates six engagement techniques.

In this study, we made three sets of contributions. First, we developed
HarrySpotter, a location-based app that enables users to annotate real-world
objects. We conducted a two-week in-the-wild study involving 29 participants,
resulting in a collection of 503 annotated objects. Second, we analyzed the
engagement techniques chosen by users when capturing these objects and
examined their correlation with their Big-Five personality traits. Our
findings revealed that competition-based techniques discouraged agreeable
users but encouraged conscientious users. Techniques promoting exploration of
objects and places were particularly appealing to extroverts and individuals
open to new experiences. Additionally, techniques focusing on personal
achievements were found to motivate neurotic users. Lastly, we found that
these preferences for specific engagement techniques not only correlated with
personality traits but also had predictive value. The Adj. $R^{2}$ values
ranged from 0.16 for conscientious users to 0.32 for neurotic users and as
high as 0.61 for extroverts.

##  2 Related Work

User engagement is a critical factor in the success of various digital
experiences, including websites, mobile apps, and online platforms [20]. It
refers to the level of involvement, interaction, and interest that users have
with a product or service [28], resulting in increased engagement. Similarly,
mobile user engagement is described by the level of engagement users have with
mobile apps on their smartphones or tablets. Factors such as intuitive user
interface design, personalized content delivery, and interactive features play
a significant role in fostering mobile user engagement [36, 22]. Push
notifications, in-app messaging, and social sharing features also contribute
to enhancing mobile user engagement [18].

Gamification techniques also play a crucial role in fostering engagement [10,
12]. Gamification involves applying game elements and mechanics to non-game
contexts to enhance engagement, motivation, and participation [10]. It taps
into people’s natural inclination for competition, achievement, and
recognition, making it a powerful tool for motivating and incentivizing users
[14]. By incorporating game-like features such as points, badges,
leaderboards, challenges, and rewards, mobile app developers can transform
mundane tasks or activities into more enjoyable and immersive experiences.
Rewards can take various forms, such as adding points or levels, to entice
users to engage with an app to earn these rewards [27, 24]. Badges and
leaderboards are also popular gamification elements, which were shown to boost
motivation [4]. Additionally, gamification strategies have been used to
increase users’ physical activity. For example, Althoff et al. [1] conducted a
study on the impact of Pokémon GO [26], an augmented reality (AR) location-
based game, and found that the game led to a more than 25% increase in users’
physical activity.

While previous studies have explored the use of gamification strategies to
engage mobile app users in a variety of tasks or games, the relationship
between these strategies and a user’s personality remains relatively
unexplored. The purpose of this study is to investigate whether different
individuals perceive the same gamification strategies differently.

##  3 The Big-Five Personality

The Big-Five personality model assigns individuals scores [11], representing
the main personality traits of Openness, Conscientiousness, Extroversion,
Agreeableness, and Neuroticism. We hypothesized the relationship between these
traits and our six engagement strategies, and summarized the positive and
negative relationships of these hypotheses in Table 1.

_Openness_ is associated with descriptive terms such as imaginative,
spontaneous, and adventurous. Individuals high in Openness are more likely to
try new methods of communication, including social networking sites or mobile
apps. For example, studies have reported that individuals high in Openness
tend to utilize a greater number of features that facilitate exploration in
such technologies [31].

_Conscientiousness_ is associated with traits like ambition, resourcefulness,
and persistence. Individuals high in Conscientiousness are less likely to
engage in mobile content generation. They often view computer-mediated
communication as a distraction from their daily tasks [2]. However, when they
do engage in such communication, they tend to approach it in a highly
methodical and competitive manner. Their motivation is often driven by a
desire for positive competition [13].

_Extraversion_ is associated with descriptive terms such as sociability,
activity, and excitement seeking. Individuals high in Extraversion typically
prefer face-to-face interactions and are less inclined to utilize social
networking sites or mobile apps. However, if they do join such platforms, they
often participate in multiple groups, contribute content, and are motivated by
the positive aspect of exploration as a means of social stimulation [29].

_Agreeableness_ is associated with descriptive terms such as trusting,
altruistic and tender-minded. Individuals high in Agreeableness, who are less
competitive [13] and less likely to share content [2], are more likely to be
negatively motivated by rewards or competition.

_Neuroticism_ is associated with descriptive terms such as emotional liability
and impulsiveness. Individuals with high levels of Neuroticism exhibit diverse
behaviors across different media platforms. They tend to use the Internet and
mobile apps as a means to alleviate loneliness, share accurate personal
information in anonymous online forums (e.g., chat rooms), exercise control
over their shared information on mobile devices [5], and focus on their own
achievements in positive ways [21].

Table 1: Question statements assessing HarrySpotter’s six engagement
strategies. Positive and negative signs indicate the association of these
engagement strategies with each personality trait as found in prior
literature, and empty cells indicate that no reference has been found. O:
Openness; C: Conscientiousness; E: Extraversion; A: Agreeableness; and N:
Neuroticism.

Strategy | Question Statement | O | C | E | A | N
---|---|---|---|---|---|---
Q1(Point Rewards) | I pay attention to others’ spell energy scores. |  |  |  | - |
Q2(Place Rewards) | I am proud of my mayorships. |  |  |  | - | +
Q3(Game with Yourself) | When I play the game, I feel I am representing my house. |  |  |  |  | +
Q4(Social Connection) | With HarrySpotter, I track the competition among the four houses. |  | + |  | - |
Q5(Object Discovery) | HarrySpotter motivated me to discover new objects. | + |  | + |  |
Q6(Place Discovery) | HarrySpotter motivated me to visit new places. | + |  | + |  |

##  4 HarrySpotter

Figure 1: HarrySpotter’s gameplay elements: _a) Onboarding_ : set up account
and complete the sorting hat quiz; _b) Exploration_ : location-based features
(e.g., keeping track of mayorship around you), and leaderboard; _c) Mayorship_
: AR experience for claiming mayorship (a mage would appear to challenge the
user for mayorship); and _d) Annotation:_ capture and annotate objects.

We developed a mobile app called HarrySpotter, which incorporates gameplay
elements inspired by the popular Harry Potter series. Authored by J.K.
Rowling, the Harry Potter series revolves around the adventures of a young
wizard named Harry Potter, his friends, and their quest to defeat the dark
wizard Lord Voldemort. Our app draws inspiration from the series’ concept of
affiliation through four houses, namely Gryffindor (known for courage and
bravery), Hufflepuff (emphasizing hard work and patience), Ravenclaw
(highlighting intelligence and learning), and Slytherin (representing
ambitions and cunning). HarrySpotter was developed using the Unity game engine
for both Android and iOS platforms. The app uses the Mapbox SDK for location-
based features, and Vuforia SDK to deliver an augmented reality experience,
particularly during the process of claiming a mayorship.

HarrySpotter employs six strategies to engage users in the task of annotating
objects: Point Rewards, Places Rewards, Game with Yourself, Social Connection,
Object Discovery, and Place Discovery. These strategies were initially derived
from the work of Lindqvist et al. [24], but were modified to align with our
gameplay’s requirements. For example, the effectiveness of badges in
Lindqvist’s study was evaluated using the question statement: “I pay attention
to the badges that others earn.” In our case, to assess the effectiveness of
point rewards (which function as a type of badge), we adapted the statement
to: “I pay attention to others’ spell energy scores” (Table1). Additionally,
as our gameplay includes two types of rewards—points and place rewards—we
categorized them separately, resulting in a total of six strategies,
contrasting with the five strategies described in [24].

Point and Place Rewards: Previous research has demonstrated the effectiveness
of reward systems, such as points, in engaging users with mobile apps [4]. In
HarrySpotter, users are rewarded with spell energy for annotating new objects
(Figure 1d), which reflects their ability to claim mayorships of places. When
a user annotates an object, the app compares the user-generated label (object
name) with the label automatically detected by an image classifier running on
our server. The classifier used is a deep-learning ResNet-162 model with a top
5% accuracy of 94.2% on ImageNet classes. The semantic distance between the
user-generated label and the automatically detected label is computed using
WordNet [25]. If they match, the user receives extra spell energy.
Additionally, the app tracks previously scanned object types and rewards the
user when they scan a new type for the first time. However, if the user scans
the same object type repeatedly, the reward amount decreases until it reaches
the minimum of 10 points. This design choice ensures that the user’s score
does not reach zero and maintains a balance between engagement and avoiding
penalization, such as providing incorrect labels or repetitive images.

Game With Yourself: Users have the option to play the game alone, engaging in
various single-player elements such as object annotation, places, and
challenging mayorships (Figure 1b-d). When it comes to mayorships, a user can
become the mayor of a place. Subsequently, other users have the opportunity to
visit that place and challenge the current mayor. This feature adds a
competitive aspect to the game, even when playing individually.

Social Connection: Previous research has demonstrated that leaderboards are
effective in enhancing user performance in various tasks [4]. In HarrySpotter,
during the onboarding process, users respond to a series of questions inspired
by the Harry Potter sorting hat quiz (Figure 1a) and are sorted into one of
the Harry Potter houses [15]. Through the leaderboard, we encourage users to
actively participate in the game and contribute to their respective houses’
efforts in claiming mayorships of different places.

Object Discovery: Enabling users to explore and discover new places or objects
is a crucial aspect of location-based apps. Previous research has demonstrated
that incorporating points of interest (similar to Pokémon GO) encourages users
to engage with the app while on the move and at various locations [1]. In
HarrySpotter, we motivate users to explore different locations by allowing
them to become mayors of real places (Figure 1c). When a user is within the
mayorship location range, an AR mage appears and challenges the user for
mayorship. The user’s spell energy (points) plays a significant role in their
chances of claiming the mayorship. To strike the right balance, we set the
mayorship range to an 80-meter radius based on empirical evidence. Lower
ranges limited accessibility, while higher ranges diminished proximity and
overall engagement. Through this strategy, we encourage users to discover and
scan objects they may have overlooked in new locations, fostering exploration
and engagement.

Place Discovery. Previous research on the motivations behind using location-
based apps has revealed that users are driven by their curiosity to obtain
information about specific points of interest [24]. This curiosity acts as an
incentive for users to actively pursue becoming the mayor of those places. In
HarrySpotter, when a user successfully claims mayorships of places, their map
visually represents a sense of territorial ownership (Figure 1b). For example,
if a user belongs to Hufflepuff house and becomes a mayor, their map pins will
be displayed in yellow, symbolizing their affiliation with Hufflepuff.

##  5 User Study

Participants and Ethical Considerations. We deployed HarrySpotter in a 2-week
study with 29 users (13 female), aged between 18-49 years (median = 34). To be
eligible for the study, participants were required to own an Android or iOS
smartphone and be located in London, UK. In compliance with GDPR and the Data
Protection Act, all individual user data were anonymized to ensure the privacy
and confidentiality of the participants. The study was approved by the Ethics
Committee of Goldsmiths, University of London.

Procedure. All participants underwent a pre-screening process where we
collected demographic information and obtained the unique identifier of their
device for generating the app download link. After installing the app,
participants were prompted to grant access to the camera and location. Basic
instructions were provided on how to use the app, such as annotating objects,
with no specific guidelines on what to annotate or how frequently. To maintain
study integrity, no information regarding the relationship between personality
and engagement techniques was revealed to the participants.

Materials and Apparatus. At the end of the study, we administered a 6-item
questionnaire (Table 1) and the 10-item TIPI personality questionnaire [11].
The 6-item questionnaire included statements derived from [24] and had
previously been validated in the context of the Foursquare app to assess
users’ motivations for engagement. Participants rated both questionnaires
using a 7-point Likert scale (1: Strongly Disagree; 7: Strongly Agree).

Self-reports and Big-Five personality traits. We coded the Likert-scale
answers to the 6-item questionnaire and the TIPI [11]. On average, our
participants scored as follows on a 1-7 scale: average in Openness
($\mu\textrm{=5.14}$, $\sigma\textrm{=0.8}$), high in Conscientiousness
($\mu\textrm{=5.12}$, $\sigma\textrm{=0.85}$), average in Neuroticism
($\mu\textrm{=4.59}$, $\sigma\textrm{=0.85}$), average in Agreeableness
($\mu\textrm{=4.5}$, $\sigma\textrm{=0.71}$), and low in Extraversion
($\mu\textrm{=4.43}$, $\sigma\textrm{=0.94}$). These trait distributions
aligned with the normative personality values derived from a large sample of
the U.S. population [34].

Annotations. Each annotation in our study involved storing the raw image and
its corresponding label in a database. To ensure data quality, we implemented
checks for image duplication and semantic correctness. To prevent duplication,
we utilized FAISS [17], a framework for indexing images based on visual
similarity. This allowed us to retrieve the most visually similar images for
comparison. We penalized scores for each annotation based on visual similarity
to the user’s previously uploaded images. For instance, if an image closely
resembled a previously captured one, the user would not receive a reward in
the form of spell energy. To assess semantic correctness, we first subjected
the uploaded image to an off-the-shelf object detector [6]. We then calculated
the WordNet semantic distance [25] between the detected label and the user-
generated label. The awarded spell energy was proportional to the semantic
similarity, discouraging grossly inaccurate or garbled labels. Regarding
annotation quantity, we recorded the total number of annotations $n_{k}$
uploaded by each user $k$ along with their respective images. For annotation
quality, three independent annotators rated each annotation on a 1-5 Likert
scale, with 5 indicating a perfect match between the image and the user-
generated label. For example, if an image depicted a “computer mouse” and the
user’s label was “mouse,” the annotator would assign a score of 5. To ensure
reliable results, we calculated a Fleiss kappa score of 0.57, indicating
moderate to good agreement among the three annotators. We compiled a set of
$n$ images $I$ annotated by each user $k$ as ${I_{1},I_{2},...,I_{n}}$. The
quality score for user $k$ was determined by the median of the quality scores
assigned to their $n$ annotated images.

Before using the six self-reports and the quantity and quality of annotation
metrics into our regression models, we conducted a Shapiro-Wilk test for
normality. As the eight variables exhibited skewed distributions, we applied a
log transformation to them. Among the five personality traits, only
Extraversion showed a slight skewness, so we also applied a log transformation
to it.

##  6 Results

To ease the interpretation of our results, we applied a min-max transformation
to scale our variables within the range of [0-100]. We first examined the
pairwise correlation among personality traits, the six self-reports, and the
quantity and quality of annotations metrics. We found that neurotic users
discovered fewer objects (r=-0.37, p<0.1). Additionally, these users tended to
take pride in their mayorships (r=0.44, p<0.05) and their affiliation with
their respective Harry Potter house (r=0.47, p<0.05). Conversely, Extroverts
and those high in Openness liked to discover new objects (r=0.44, p<0.05 and
r=0.39, p<0.05, respectively) and new places (r=0.38, p<0.05 and r=0.35,
p<0.1, respectively).

Table 2: Linear regressions that predict the Big-Five personality traits from the six self-reports and the quantity and quality of annotations. Significant predictors with $p$ values $<$ .05 are marked in bold. The most predictable personality trait was Extraversion ($M_{E}$), while the least predictable was Conscientiousness ($M_{C}$). $\boldsymbol{M_{O}}$: $\boldsymbol{\emph{Adj $R^{2}$}=0.28}$, Durbin-Watson = 1.96, AIC = 0.47 |  |  |
---|---|---|---
Predictor | $\beta$ | std. error |  $p$-value
Intercept | 0.42 | 0.13 | 0.005
Q1(Point Rewards) | -1.08 | 0.36 | 0.01
Q2(Place Rewards) | 0.42 | 0.35 | 0.23
Q5(Object Discover) | 0.84 | 0.27 | 0.01
$\boldsymbol{M_{C}}$: $\boldsymbol{\emph{Adj $R^{2}$}=0.16}$, Durbin-Watson = 1.15, AIC = -7.48 |  |  |
Predictor | $\beta$ | std. error |  $p$-value
Intercept | 0.57 | 0.12 | 0.00
Q3(Game with Yourself) | 0.59 | 0.22 | 0.01
Q6(Place Discovery) | -0.48 | 0.23 | 0.04
$\boldsymbol{M_{E}}$: $\boldsymbol{\emph{Adj $R^{2}$}=0.61}$, Durbin-Watson = 1.88, AIC = -14 |  |  |
Predictor | $\beta$ | std. error |  $p$-value
Intercept | 0.48 | 0.19 | 0.02
Q2(Place Rewards) | -0.60 | 0.22 | 0.01
Q4(Social Connection) | -0.72 | 0.22 | 0.00
Q5(Object Discovery) | 0.53 | 0.22 | 0.02
Q6(Place Discovery) | 0.99 | 0.28 | 0.00
Quantity | -0.37 | 0.12 | 0.00
Quality | 0.18 | 0.16 | 0.27
$\boldsymbol{M_{A}}$: $\boldsymbol{\emph{Adj $R^{2}$}=0.21}$, Durbin-Watson = 1.84, AIC = -12.86 |  |  |
Predictor | $\beta$ | std. error |  $p$-value
Intercept | 0.57 | 0.11 | 0.00
Q1(Point Rewards) | -0.45 | 0.24 | 0.07
Q3(Game with Yourself) | 0.21 | 0.21 | 0.31
Q5(Object Discovery) | -0.37 | 0.24 | 0.13
Q6(Place Discovery) | 0.71 | 0.29 | 0.02
$\boldsymbol{M_{N}}$: $\boldsymbol{\emph{Adj $R^{2}$}=0.32}$, Durbin-Watson = 2.79, AIC = -3.68 |  |  |
Predictor | $\beta$ | std. error |  $p$-value
Intercept | 0.36 | 0.14 | 0.02
Q2(Place Rewards) | 0.37 | 0.26 | 0.17
Q4(Social Connection) | 0.58 | 0.27 | 0.04
Q6(Place Discovery) | -0.58 | 0.29 | 0.06
Quantity | -0.32 | 0.14 | 0.03

Considering these significant correlations, one might wonder whether it is
possible to predict users’ personality traits based on their self-reports and
the quantity and quality annotation metrics. Using these metrics as
predictors, we fitted five linear regression models (Table 2) to predict the
Big-Five personality dimensions and determined the best set of predictors
using the stepAIC function [37]. Overall, our findings indicate that
predicting certain personality dimensions, such as Extraversion (Adj. $R^{2}$
= 0.61), was relatively easier compared to others like Conscientiousness (Adj.
$R^{2}$ = 0.16).

As expected, users with non-competitive traits (high in Agreeableness)
demonstrated a lack of motivation for competing with others
($\beta_{\textrm{(Q1(Point Rewards))}}\textrm{=-0.45}$). On the other hand,
conscientious users, known for their organizational skills, exhibited
motivation for competition ($\beta_{\textrm{(Q1(Point
Rewards))}}\textrm{=0.59}$) among the four houses but moderately predicted
their personality trait (Adj. $R^{2}$=0.16). Individuals open to new
experiences and extroverts were primarily motivated by the discovery of new
objects ($\beta_{\textrm{(Q5(Object Discovery))}}\textrm{=0.84}$ and
$\beta_{\textrm{(Q5(Object Discovery))}}\textrm{=0.53}$, respectively).
Moreover, individuals open to new experiences did not find motivation in
competing with others ($\beta_{\textrm{(Q1)}}\textrm{=-1.08}$), while
extroverts were not motivated by mayorships ($\beta_{\textrm{(Q2(Place
Rewards))}}\textrm{=-0.60}$) or representing their own house
($\beta_{\textrm{(Q1(Point Rewards))}}\textrm{=-0.72}$). Emotionally unstable
users (neurotics) found motivation in representing their own house
($\beta_{\textrm{(Q4(Social Connection))}}\textrm{=0.58}$) but not in the
discovery of new places ($\beta_{\textrm{(Q6(Place
Discovery))}}\textrm{=-0.58}$), leading them to discover fewer objects
($\beta_{\textrm{(Quantity)}}\textrm{=-0.32}$).

##  7 Discussion and Conclusion

Mobile user engagement is commonly pursued through a range of techniques;
however, there is a tendency to apply these techniques uniformly to all users,
adopting a one-size-fits-all approach. To investigate the possibility that
individuals may perceive engagement techniques differently, we created
HarrySpotter, a location-based augmented reality (AR) app that enables users
to annotate real-world objects using six distinct engagement techniques. By
deploying HarrySpotter and analyzing data from 29 users, we found that
agreeable users were not motivated by competition, while conscientious users
were motivated by it to a greater extent. As expected, individuals open to new
experiences and extroverts were motivated by exploration, while neurotics
exhibited a stronger drive towards personal achievements. These preferences
for specific engagement techniques also predicted personality traits to
different extents (e.g., Extraversion with an Adj. $R^{2}$ of 0.61, while
Conscientiousness with an Adj. $R^{2}$ of 0.16), suggesting that engagement
strategies should be tailored to one’s personality.

From a theoretical perspective, our work is situated within the domain of
adaptive user interfaces (AUI). The effectiveness of an AUI hinges on the
ability to construct and utilize individual user profiles, allowing for the
delivery of personalized versions of the user interface [16, 9, 8, 7].
Building upon this foundation, we envision that our methodology could be
employed to enhance user models with specific characteristics, such as
personality traits. This, in turn, could facilitate the personalization of
user interfaces in various contexts, such as advancing levels in a gamified
app or completing tasks. From a practical standpoint, our findings can inform
the design of personalized engagement strategies. To illustrate, let us
consider the scenario of mobile crowdsourcing systems, where a one-size-fits-
all approach has proven ineffective in engaging users for specific tasks, such
as object annotation [33]. By incorporating brief personality questionnaires,
for example during account setup (e.g., the TIPI [11] questionnaire, which can
be completed in a minute), mobile developers can implement in-app mechanisms
to dynamically infer personality traits, thereby adapting engagement
strategies based on users’ interactions.

Our work has three limitations that warrant further research efforts. Firstly,
our findings are specific to the HarrySpotter game and this particular cohort.
Future studies could extend our methodology to different types of mobile apps.
For example, developing tailored strategies for Conscientiousness could
enhance prediction accuracy by incorporating logging mechanisms for organized
individuals. Secondly, the slight skew in Extraversion may be due to self-
selection bias, as introverted individuals are less likely to engage with such
apps. Future studies should replicate our methodology with larger and
culturally diverse populations. Lastly, while our two-week study provided
ample data, longer deployments can explore user retention and preferences more
comprehensively, thereby enhancing our understanding of personalized
engagement strategies.

## References

  * [1] Althoff, T., White, R.W., Horvitz, E.: Influence of pokémon go on physical activity: study and implications. Journal of Medical Internet Research 18(12), e315 (2016). https://doi.org/10.2196/jmir.6759
  * [2] Amichai-Hamburger, Y., Vinitzky, G.: Social network use and personality. Computers in Human Behavior 26(6), 1289–1295 (2010). https://doi.org/10.1016/j.chb.2010.03.018
  * [3] Bachrach, Y., Kosinski, M., Graepel, T., Kohli, P., Stillwell, D.: Personality and patterns of facebook usage. In: Proceedings of the ACM Web Science Conference. pp. 24–32 (2012). https://doi.org/10.1145/2380718.2380722
  * [4] Bräuer, P., Mazarakis, A.: Badges or a leaderboard? how to gamify an augmented reality warehouse setting. In: GamiFIN. pp. 229–240 (2019), https://ceur-ws.org/Vol-2359/paper20.pdf
  * [5] Butt, S., Phillips, J.G.: Personality and self reported mobile phone use. Computers in Human Behavior 24(2), 346–360 (2008). https://doi.org/10.1016/j.chb.2007.01.019
  * [6] Cheng, B., Collins, M.D., Zhu, Y., Liu, T., Huang, T.S., Adam, H., Chen, L.C.: Panoptic-deeplab. In: ICCV COCO + Mapillary Joint Recognition Challenge Workshop (2019)
  * [7] Constantinides, M., Dowell, J.: User interface personalization in news apps. In: CEUR Workshop Proceedings. vol. 1618. CEUR workshop Proceedings (2016), https://ceur-ws.org/Vol-1618/INRA_paper2.pdf
  * [8] Constantinides, M., Dowell, J.: A framework for interaction-driven user modeling of mobile news reading behaviour. In: Proceedings of the 26th Conference on User Modeling, Adaptation and Personalization. pp. 33–41 (2018). https://doi.org/10.1145/3209219.3209229
  * [9] Constantinides, M., Dowell, J., Johnson, D., Malacria, S.: Exploring mobile news reading interactions for news app personalisation. In: Proceedings of the ACM International Conference on Human-Computer Interaction with Mobile Devices and Services. pp. 457–462 (2015). https://doi.org/10.1145/2785830.2785860
  * [10] Deterding, S.: Gamification: designing for motivation. Interactions 19(4), 14–17 (2012). https://doi.org/10.1145/2212877.2212883
  * [11] Gosling, S.D., Rentfrow, P.J., Swann Jr, W.B.: A very brief measure of the big-five personality domains. Journal of Research in Personality 37(6), 504–528 (2003). https://doi.org/10.1016/S0092-6566(03)00046-1
  * [12] Hakulinen, L., Auvinen, T., Korhonen, A.: The effect of achievement badges on students’ behavior: An empirical study in a university-level computer science course. International Journal of Emerging Technologies in Learning 10(1) (2015). https://doi.org/10.3991/ijet.v10i1.4221
  * [13] Halko, S., Kientz, J.A.: Personality and persuasive technology: an exploratory study on health-promoting mobile applications. In: International Conference on Persuasive Technology. pp. 150–161. Springer (2010). https://doi.org/10.1007/978-3-642-13226-1_16
  * [14] Hamari, J., Koivisto, J., Sarsa, H.: Does gamification work?–a literature review of empirical studies on gamification. In: 2014 47th Hawaii international conference on system sciences. pp. 3025–3034. IEEE (2014). https://doi.org/10.1109/HICSS.2014.377
  * [15] Jakob, L., Garcia-Garzon, E., Jarke, H., Dablander, F.: The science behind the magic? the relation of the harry potter “sorting hat quiz” to personality and human values. Collabra: Psychology 5(1) (2019). https://doi.org/10.1525/collabra.240
  * [16] Jameson, A.: Adaptive interfaces and agents. In: The Human-Computer Interaction Handbook, pp. 459–484. CRC press (2007)
  * [17] Johnson, J., Douze, M., Jégou, H.: Billion-scale similarity search with gpus. IEEE Transactions on Big Data (2019). https://doi.org/10.1109/TBDATA.2019.2921572
  * [18] Kim, S., Baek, T.H.: Examining the antecedents and consequences of mobile app engagement. Telematics and Informatics 35(1), 148–158 (2018). https://doi.org/10.1016/j.tele.2017.10.008
  * [19] Kosinski, M., Bachrach, Y., Kohli, P., Stillwell, D., Graepel, T.: Manifestations of user personality in website choice and behaviour on online social networks. Machine Learning 95(3), 357–380 (2014). https://doi.org/10.1007/s10994-013-5415-y
  * [20] Lalmas, M., O’Brien, H., Yom-Tov, E.: Measuring user engagement. Synthesis Lectures on Information Concepts, Retrieval, and Services 6(4), 1–132 (2014). https://doi.org/10.2200/S00605ED1V01Y201410ICR038
  * [21] Lane, W.: The influence of personality traits on mobile phone application preferences. Journal of Economics and Behavioral Studies 4(5), 252–260 (2012). https://doi.org/10.22610/jebs.v4i5.325
  * [22] Leiras, M.: Mobile User Engagement: New Apps versus Mainstream Apps. Ph.D. thesis, Universidade do Porto (Portugal) (2017)
  * [23] Levitas, D.: There is no one-size-fits-all approach to mobile apps. https://www.adexchanger.com/data-driven-thinking/no-one-size-fits-approach-mobile-apps/ (2017), accessed: June 2023
  * [24] Lindqvist, J., Cranshaw, J., Wiese, J., Hong, J., Zimmerman, J.: I’m the mayor of my house: examining why people use foursquare-a social-driven location sharing application. In: Proceedings of the ACM CHI Conference on Human Factors in Computing Systems. pp. 2409–2418 (2011). https://doi.org/10.1145/1978942.1979295
  * [25] Miller, G.A.: WordNet: An electronic lexical database. MIT press (1998)
  * [26] Niantic: PokemonGo. https://pokemongolive.com (2016), accessed: April 2023
  * [27] Nicholson, S.: A recipe for meaningful gamification. In: Gamification in Education and Business, pp. 1–20. Springer (2015). https://doi.org/10.1007/978-3-319-10208-5_1
  * [28] O’Brien, H.L., Toms, E.G.: What is user engagement? a conceptual framework for defining user engagement with technology. Journal of the American society for Information Science and Technology 59(6), 938–955 (2008). https://doi.org/10.1002/asi.20801
  * [29] Phillips, J.G., Butt, S., Blaszczynski, A.: Personality and self-reported use of mobile phones for games. CyberPsychology & Behavior 9(6), 753–758 (2006). https://doi.org/10.1089/cpb.2006.9.753
  * [30] Quercia, D., Kosinski, M., Stillwell, D., Crowcroft, J.: Our twitter profiles, our selves: Predicting personality with twitter. In: 2011 IEEE third international conference on privacy, security, risk and trust and 2011 IEEE third international conference on social computing. pp. 180–185. IEEE (2011). https://doi.org/10.1109/PASSAT/SocialCom.2011.26
  * [31] Ross, C., Orr, E.S., Sisic, M., Arseneault, J.M., Simmering, M.G., Orr, R.R.: Personality and motivations associated with facebook use. Computers in Human Behavior 25(2), 578–586 (2009). https://doi.org/10.1016/j.chb.2008.12.024
  * [32] van Roy, R., Deterding, S., Zaman, B.: Collecting pokémon or receiving rewards? how people functionalise badges in gamified online learning environments in the wild. International Journal of Human-Computer Studies 127, 62–80 (2019). https://doi.org/10.1016/j.ijhcs.2018.09.003
  * [33] Rula, J.P., Navda, V., Bustamante, F.E., Bhagwan, R., Guha, S.: No “one-size fits all” towards a principled approach for incentives in mobile crowdsourcing. In: Proceedings of the Workshop on Mobile Computing Systems and Applications. pp. 1–5 (2014). https://doi.org/10.1145/2565585.2565603
  * [34] Soto, C.J., John, O.P., Gosling, S.D., Potter, J.: Age differences in personality traits from 10 to 65: Big five domains and facets in a large cross-sectional sample. Journal of Personality and Social Psychology 100(2), 330 (2011). https://doi.org/10.1037/a0021717
  * [35] Stachl, C., Au, Q., Schoedel, R., Gosling, S.D., Harari, G.M., Buschek, D., Völkel, S.T., Schuwerk, T., Oldemeier, M., Ullmann, T., et al.: Predicting personality from patterns of behavior collected with smartphones. Proceedings of the National Academy of Sciences 117(30), 17680–17687 (2020). https://doi.org/10.1073/pnas.1920484117
  * [36] Sutcliffe, A.: Designing for user experience and engagement. Why Engagement Matters: Cross-Disciplinary Perspectives of User Engagement in Digital Media pp. 105–126 (2016). https://doi.org/10.1007/978-3-319-27446-1_5
  * [37] Zhang, Z.: Variable selection with stepwise and best subset approaches. Annals of Translational Medicine 4(7) (2016). https://doi.org/10.21037/atm.2016.03.35