# A Query-Driven Topic Model

Zheng Fang1, Yulan He1,2 and Rob Procter1,2
1Department of Computer Science, University of Warwick
2The Alan Turing Institute, London, UK
<EMAIL_ADDRESS>
###### Abstract

Topic modeling is an unsupervised method for revealing the hidden semantic
structure of a corpus. It has been increasingly widely adopted as a tool in
the social sciences, including political science, digital humanities and
sociological research in general. One desirable property of topic models is to
allow users to find topics describing a specific aspect of the corpus. A
possible solution is to incorporate domain-specific knowledge into topic
modeling, but this requires a specification from domain experts. We propose a
novel query-driven topic model that allows users to specify a simple query in
words or phrases and return query-related topics, thus avoiding tedious work
from domain experts. Our proposed approach is particularly attractive when the
user-specified query has a low occurrence in a text corpus, making it
difficult for traditional topic models built on word co-occurrence patterns to
identify relevant topics. Experimental results demonstrate the effectiveness
of our model in comparison with both classical topic models and neural topic
models.

##  1 Introduction

Topic modeling aims to infer topics from a collection of documents, where a
topic is a salient pattern of the collection and is represented by a
distribution over words. The availability in large volume of new sources of
unstructured data, such as social media, has presented a challenge to
conventional qualitative research methods in the social sciences and
humanities and encouraged the exploration of topic modeling as a potential
solution Melville et al. (2019); Hu et al. (2019); Yao and Wang (2020). In
these studies, topic modeling has been applied to questions centered on
interpretation and meaning. By analyzing words distribution of topics learnt,
researchers can apply inductive reasoning on specific topics and perform a
more in-depth study of related documents, allowing them to identify underlying
topical trends and conduct a more thorough analysis of the data.

One limitation of conventional topic modeling approaches in these studies is
that they can only learn topics from the whole corpus. However, in some cases,
researchers may be interested in topics describing specific concepts or
aspects of the corpus. To identify these topics, researchers have to analyze
words distribution for all topics, thereby making it very time consuming.
Moreover, it could also happen that the target topics may have a very small
presence in the data to be detected directly by a topic model. For instance,
given a set of posts about health, researchers may wish specifically to
analyze the impact of food on health. If the words related to food have a
relatively low frequency of occurrence in the posts, then conventional topic
models such as Latent Dirichlet Allocation (LDA) Blei et al. (2003) may not
find any food-related topics at all. This is caused by the phenomenon of
higher order co-occurrence in conventional topic models Heinrich (2009), which
prevents infrequent words being sampled under the correct topic. While an
information retrieval method could be used to find relevant documents,
identifying key subtopics discussed in these documents will still be a
daunting process.

Figure 1: Our proposed model returns topics relevant to a user-input query, in
this example, ‘ _atheism_ ’. Step 1: user uses a query to define the concept
of interest. Step 2: a query expansion technique is used to expand the input
query to a set of concept words. Step 3: the concept words are utilized to
generate a single topic. Step 4: the single topic is expanded to a set of
subtopics. The retrieved concept-topic and subtopic results allow the user to
do inductive reasoning and have a more in-depth study of related documents. In
Step 3 and Step 4, we present the top weighted words of the topic and their
corresponding weights.

To handle this limitation, weakly-supervised approaches Andrzejewski and Zhu
(2009); Nikolenko et al. (2017); Chen et al. (2013); Andrzejewski et al.
(2011); Yang et al. (2015) have been proposed as a solution and different
types of domain-specific, prior knowledge, such as word correlation Yang et
al. (2015), document and word labels have been introduced. By adding these to
the unsupervised topic model, a set of topics describing the domain knowledge
can be generated. However, this still requires experts to define the domain
knowledge, which may not always be feasible. In addition, the aforementioned
approaches can only generate one topic relevant to the target concept. It is
desirable to distinguish between different contexts about the same concept:
for instance, for the concept ‘ _Middle East_ ’, there might be subtopics
relating to Middle East conflicts and Middle East resorts, respectively. In
our work, we propose a novel approach that automatically generates all
subtopics relevant to the target concept.

In our query-driven topic model, a query phrase is used to define the concept
of interest. As illustrated in Figure 1, a query expansion technique is first
employed to expand the input query to a set of concept words, which are then
utilized to first generate a single topic about the concept, and subsequently
further expanded to a set of subtopics automatically. In summary, our
contributions are four fold: (1) We propose a novel approach which allows
users without expertise knowledge to use a short query rather than predefined
keywords to detect topics of their interests; (2) Our model is novel in its
ability to identify rare topics in text, which would not be possible using
existing topic modeling approaches; (3) Our model is built on the Hierarchical
Dirichlet Process (HDP) and can therefore automatically infer all subtopics
describing the target concept without having to determine the optimal number
of topics beforehand; (4) We evaluate our approach on three datasets and
achieve superior performance compared to both traditional hierarchical topic
models and neural topic models, both quantitatively and qualitatively.111Our
source code can be accessed at: https://github.com/Fitz-like-coding/QDTM.

##  2 Related Work

Earlier work has attempted to solve the problem of identifying specific topics
by using prior knowledge. Andrzejewski et al. (2009) expressed domain
knowledge with two primitives on word pairs called _Must-Links_ and _Cannot-
Links_ , encoding them using a Dirichlet Forest prior. Topic-in-set knowledge
Andrzejewski and Zhu (2009) defines ‘ _z-labels_ ’ as prior knowledge and a
similar idea was introduced by Nikolenko et al. (2017). First-Order Logic has
been proposed as a way to incorporate richer forms of prior knowledge
Andrzejewski et al. (2011). Yang et al. (2015) proposed an efficient method
for incorporating domain knowledge and demonstrated significant speed
improvement with large datasets. El-Assady et al. (2019) presented a framework
that allows users to incorporate the semantics of their domain knowledge in
topic models interactively. Gemp et al. (2019) incorporated informative priors
in an neural topic model for the purpose of semi-supervised topic modeling.
All these approaches require experts to provide domain-specific, prior
knowledge, which is problematic for two reasons: different corpora in the same
domain may contain different information; and it may be costly to specify all
prior knowledge. We take advantage of a query expansion technique and propose
an automatic concept words extractor to help user extract prior knowledge.

Our work is also similar to the Hierarchical Topic Model (HTM) Blei et al.
(2004). HTM is a non-parametric topic model that generates topics in a
hierarchical structure. In our work, we also propose to generate subtopics
from a parent topic. A key difference is that we propose a novel solution to
incorporate domain-specific prior knowledge, making it possible to generate
desirable topics. This is not the case with HTM. Although attempts were made
to introduce prior knowledge in HTM, Perotte et al. (2011) focused on out-of-
sample label prediction which is not the focus of our work while Xu et al.
(2018) still required experts to define word pairs which is problematic as
mentioned earlier.

##  3 Proposed Framework

In outline, our model expands an input query to a set of concept words using a
concept words extractor. These concept words are then fed into a two phases
framework based on a variant of a Hierarchical Dirichlet Process (HDP) to
model all topics relevant to the concept.

###  3.1 Concept Words Extractor

Given an input query $q$, we retrieve a list of documents $d$ according to the
query likelihood score Ceri et al. (2013),

$p(d{\mid}q)\approx\prod_{i=1}^{n}p(q_{i}{\mid}d)$ (1)

where $n$ is the number of tokens in the query and $p(q_{i}{\mid}d)$ is the
probability of query term $q_{i}$ in document $d$. We define two extraction
rules “AND” and “OR” to constrain whether query terms should appear in the
same document or not. We then extract concept words from the retrieved
documents. We adopt three approaches for our purpose.

#### Frequency based extraction (FRE)

The first one simply extracts words with high frequency in the retrieved
documents as our concept words:

${Score(w)}={\sum_{i}^{n}TF(w{\mid}d_{i})}$ (2)

where $n$ is the number of retrieved documents and $TF(w{\mid}d_{i})$ is the
term frequency of word $w$ in document $d_{i}$.

#### KL-Divergence based extraction (KLD)

The second one is inspired by the query expansion technique Carpineto et al.
(2001). By intuition, words relevant to the input query have a high
probability in the retrieved sub-corpus but a low probability in the whole
corpus. The score can be defined as:

${Score(w)}={P_{R}(w)}log{\frac{P_{R}(w)}{P_{C}(w)}}$ (3)

where $P_{R}(w)$ is the probability of word $w$ in the retrieved sub-corpus
and $P_{C}(w)$ is the probability of word $w$ in the whole corpus. We extract
words with high scores as our concept words.

#### Relevance model with word embedding (REL)

This approach extracts concept words from a word-embedding enhanced relevance
model Diaz et al. (2016). The probability assigned to word $w$ by the
relevance model Lavrenko and Croft (2017) is:

${p(w{\mid}RM)}={\sum_{d{\in}R}p(w{\mid}d)p(d{\mid}q)}$ (4)

where $R$ is the retrieved documents set, $p(w{\mid}d)$ is the probability of
word $w$ in document $d$ and $p(d{\mid}q)$ is $d$’s query likelihood from
equation (1). We integrate this model with word embeddings:

$Score(w)=\lambda p(w{\mid}RM)+(1-\lambda)\mbox{sim}(w,q)$ (5)

where $\lambda$ is a hyperparameter and $\mbox{sim}(w,q)$ is the normalized
similarity between word $w$ and the input query $q$. For each term in the
vocabulary list, we calculate its similarity with the input query. We then
take the top $k$ most similar terms and normalize their similarity values. If
$w$ is among the top $k$ similar terms, $\mbox{sim}(w,q)$ would get the
normalized similarity value. Otherwise, $\mbox{sim}(w,q)=0$.

###  3.2 Query-Driven Topic Model

We propose a two-phase framework based on HDP, which is a nonparametric
Bayesian model that can automatically infer the number of topics in a corpus
Teh et al. (2005). It assumes a restaurant (i.e., a document) has a set of
tables and serves dishes (i.e., topics) from a global menu. A single dish is
only served at a single table for all customers (i.e., words) who sit at that
table.

In the first phase, the model infers one topic for each concept, along with
other irrelevant topics. We define this topic as the “ _parent topic_ ” in
later sections. We denote this parent topic of a concept corresponding to the
input query $q$ as $\tilde{z}_{q}$. We incorporate prior knowledge into HDP by
fixing the topic index for concept words in all documents. For words from
concept words $W_{q}$ corresponding to the input query $q$, the topic index
$z$ are known and remain fixed as $\tilde{z}_{q}$, and the probability for
sampling an existing table $t$ for a word $w_{ji}$ at document $j$ and
position $i$ in the Gibbs sampling process is:

$p(t_{ji}=t\mid
t^{-ji},k)\propto\mathbbm{1_{1}}(w_{ji},k_{jt})n_{jt}^{-ji}f_{k_{jt}}^{-w_{ji}}(w_{ji})$

(6)

where $k_{jt}$ is the topic assignment of table $t$ at document $j$ and
$f_{k_{jt}}^{-w_{ji}}(w_{ji})$ is the probability of $w_{ji}$ assigned to
topic $k_{jt}$ after removing the current word and
$\mathbbm{1_{1}}(w_{ji},k_{jt})$ is an indicator function, which takes on
value 0 if $w_{ji}\in W_{q}$ and $k_{jt}{\neq}\tilde{z}_{q}$ and 1 otherwise.
$n_{jt}^{-ji}$ denotes the number of words in document $j$ at table $t$ except
the current word. The probability for sampling a new table $t^{new}$ is:

$p(t_{ji}=t^{new}\mid t^{-ji},k)\propto\alpha p(w_{ji}\mid
t^{-ji},t^{new},{\bf k})$ (7)

where

$\begin{split}p(w_{ji}\mid t^{-ji},t^{new},{\bf
k})=\sum_{k=1}^{k}\frac{m_{k}}{m_{\cdot}+\gamma}f_{k}^{-w_{ji}}(w_{ji})\\\
+\frac{\gamma}{m_{.}+\gamma}f_{k^{new}}^{-w_{ji}}(w_{ji})\end{split}$ (8)

Here, $m_{k}$ denotes the number of tables of topic $k$ and $m_{\cdot}$
denotes the total number of tables. $\gamma$ and $\alpha$ are the
hyperparamenters of the model. $f_{k^{new}}^{-w_{ji}}(w_{ji})=\frac{1}{|V|}$
is the prior density of $w_{ji}$ where $|V|$ is the vocabulary size of the
dataset. If the sampled table is a new table, we sample an existing topic
$k_{j{t^{new}}}$ from:

$p(k_{j{t^{new}}}\mid
t,k^{-j{t^{new}}})\propto\mathbbm{1_{1}}(w_{ji},k_{jt}){m_{k}}f_{k}^{-w_{ji}}(w_{ji})$
(9)

and probability for sampling a new topic $k^{new}$ is:

$p(k_{j{t^{new}}}=k^{new}\mid t,{\bf k}^{-j{t^{new}}})\propto\gamma
f_{k^{new}}^{-w_{ji}}(w_{ji})$ (10)

In the second phase, the model expands the parent topic of each concept
produced in the first phase to a set of subtopics. Let $W_{\tilde{z}_{q}}$ be
the words assigned to the parent topic $\tilde{z}_{q}$ in the first phase, the
probability for sampling an existing table $t$ for a word $w_{ji}$ in the
Gibbs sampling process is:

$p(t_{ji}=t\mid
t^{-ji},k)\propto\mathbbm{1_{2}}(w_{ji},k_{jt})n_{jt}^{-ji}f_{k_{jt}}^{-w_{ji}}(w_{ji})$
(11)

where $\mathbbm{1_{2}}(w_{ji},k_{jt})$ is an indicator function that takes on
value 1 if $w_{ji}{\in}W_{\tilde{z}_{q}}$ and $k_{jt}=\tilde{z}_{q}$ and 0
otherwise. Probability for sampling a new table $t^{new}$ is:

$\begin{split}p(t_{ji}=t^{new}\mid t^{-ji},k)\propto\\\
\mathbbm{1_{2}}(w_{ji},k_{jt})\alpha p(w_{ji}\mid t^{-ji},t^{new},{\bf
k})\end{split}$ (12)

where

$\begin{split}p(w_{ji}\mid t^{-ji},t^{new},{\bf
k})=\sum_{k=1}^{K}\frac{m_{k}}{m_{.}+\gamma}f_{k}^{-w_{ji}}(w_{ji})\\\
+\frac{\gamma}{m_{.}+\gamma}\hat{f}_{k^{new}}^{-w_{ji}}(w_{ji})\end{split}$
(13)

and $\hat{f}_{k^{new}}^{-w_{ji}}(w_{ji})=\frac{1}{|W_{\tilde{z}_{q}}|}$ is the
prior density of $W_{\tilde{z}_{q}}$ where $|W_{\tilde{z}_{q}}|$ is the
vocabulary size of $W_{\tilde{z}_{q}}$. For a new table, probability for
sampling an existing topic $k$ is:

$\begin{split}p(k_{j{t^{new}}}=k\mid t,{\bf k}^{-j{t^{new}}})\propto\\\
\mathbbm{1_{2}}(w_{ji},k_{jt}){m_{k}}{f_{k}}^{-w_{ji}}(w_{ji})\end{split}$
(14)

and probability for sampling a new topic $k^{new}$ subordinate to the parent
topic $\tilde{z}_{q}$ is:

$p(k_{j{t^{new}}}=k^{new}\mid t,{\bf
k}^{-j{t^{new}}})\propto\gamma\hat{f}_{k^{new}}^{-w_{ji}}(w_{ji})$ (15)

The model automatically decides the number of subtopics and we treat the
subtopics produced as the final topics relevant to the target concept.

#### Incorporating Generalized Pólya Urn scheme

To make topics more interpretable, we incorporate word-embeddings by the
Generalized Pólya Urn scheme Li et al. (2016). Pólya Urn scheme is introduced
for colored balls and urns. In the Generalized Pólya Urn scheme, when we draw
a ball of a particular color, two balls of the same color are put back along
with a certain number of balls of the similar colors. In topic modeling
context, a topic can be viewed as an urn while a word can be viewed as a ball
in a certain color and its semantically related words can be viewed as balls
of similar colors. Every time we sample a word $w$ under a parent topic
$\tilde{z}_{q}$, we increase the probability of sampling $w$ under
$\tilde{z}_{q}$, as well as its semantically related concept words. Given pre-
trained word embeddings, we calculate the cosine similarity between word
$w_{i}$ and concept word $w_{q}\in W_{q}$. We then construct a word semantic
relatedness matrix $\mathcal{M}$ Li et al. (2016), consisting of all word
pairs whose cosine similarity is greater than a predefined threshold. We then
construct a promotion matrix $A$ whose elements are efined as:

$\displaystyle A_{i,q}=\begin{cases}1,&\text{if
$(w_{i},w_{q}){\in}\mathcal{M}$ and $w_{i}=w_{q}$}\\\ u,&\text{if
$(w_{i},w_{q}){\in}\mathcal{M}$ and $w_{i}\neq w_{q}$}\\\
0,&\text{otherwise}\end{cases}$ (16)

where $u{\in}(0,1)$ is a predefined promotion weight. When we sample a word
$w$ under topic $\tilde{z}_{q}$, we also promote all its semantically related
concepts words based on the amount of promotion in $A$.

#### Word filtering

Inspired by Wang et al. (2020), we propose a word filtering strategy. Word
filtering can be used to prevent words that have weak ties with the sampled
topic being promoted. For a word $w$ at $i^{th}$ Gibbs sampling iteration, its
semantic cohesion to topic $k$ is:

$CV[k,w_{i}]=\sum_{m=1}^{M}p^{i}(k,m){\cdot}\mbox{cos}\big{(}w_{i},RW^{i}(k,m)\big{)}$
(17)

where $p^{i}(k,m)$ is the probability of $m^{th}$ representative word in topic
$k$ at $i^{th}$ iteration and $M$ is the number of representative words
predefined. The representative words of topic $k{\neq}\tilde{z}_{q}$ at
$i^{th}$ Gibbs sampling iteration are defined by the words ranked by the
topic-word probability in the descending order.
$\mbox{cos}\big{(}w_{i},RW^{i}(k,m)\big{)}$ is the cosine similarity between
word $w_{i}$ and the $m^{th}$ representative word of topic $k$ at $i^{th}$
iteration. The representative words of $\tilde{z}_{q}$ are simply its concept
words.

For the semantic cohesion of word $w$ with different topics $CV[\cdot,w]$, we
map $CV[\cdot,w]$ into an arithmetic progression $\tilde{CV}[\cdot,w]$ ranging
from 0 to 1.0 Wang et al. (2020). We use the following equation to decide if
the GPU is applied to $w$:

$\displaystyle\begin{split}S_{j,w}{\sim}Bernoulli(\lambda_{w,k_{w}})\\\
\lambda_{w,k}=\frac{\tilde{CV}[k,w]}{\tilde{CV}_{max}[k,w]}\end{split}$ (18)

where $S_{j,w}$ indicates whether GPU is applied to word $w$ given document
$j$ and ${\tilde{CV}_{max}}[k,w]$ is the maximal semantic cohesion among all
topics.

We present the details of the Gibbs sampling process of the first phase of our
model in Algorithm 1. We omit the details of the second phase of our model
since it is similar to the first phase. The details of the functions
Initialize($\cdot$) and UpdateCounter($\cdot$) can be found in Appendix C.

Input: initial topic number $K$, hyperparameters $\alpha,\beta,\gamma$, word
semantic relatedness matrix $\mathcal{M}$, documents $D$, and Concept words
$W_{Q}$,

Output: The posterior topic-word distribution

Initialize($K$, $D$, $W_{Q}$);

/* first phase */;

foreach  _$iteration$_ do

Update word-topic coherence using Eq.17

foreach  _document $j\in D$_ do

foreach  _position $i\in j$_ do

Assign table $t\leftarrow t_{ji}$

Assign topic $k\leftarrow k_{jt}$

UpdateCounter($S_{j,w_{ji}}$, $t$, $k$, $False$);

$t_{ji}\leftarrow t\sim p(t_{ji}=t\mid t^{-ji},k)$ (Eq.6-8)

if  _$t==t^{new}$_ then

$k_{jt}\leftarrow k\sim p(k_{j{t^{new}}}=k\mid t,k^{-j{t^{new}}})$ (Eq.9-10)

end if

$S_{j,w_{ji}}\leftarrow updateGPUFlag(j,w_{ji})$ based on Eq.18

UpdateCounter($S_{j,w_{ji}}$, $t_{ji}$, $k_{jt}$, $True$)

end foreach

end foreach

end foreach

Algorithm 1 Query-driven topic model.

##  4 Experiments

We conducted our experiments by two steps. In the fist step, we evaluated the
quality of the parent topics from the first phase of our model. In the second
step, we evaluated the quality of the subtopics from the second phase of our
model.

###  4.1 Setup

#### Datasets

We conducted our experiments on three datasets:
20Newsgroup222http://qwone.com/ jason/20Newsgroups/ contains around 18k
newsgroup posts on 20 topics; TagMyNews333http://acube.di.unipi.it/tmn-
dataset/ contains around 32k short English news from 7 categories;
SearchSnippets Xu et al. (2017) contains 12k short web search snippets from 8
categories.

#### Baselines

We compared our model with six baselines: LDA Blei et al. (2003) is a widely
used topic model; DF-LDA Andrzejewski et al. (2009) incorporates domain
knowledge in LDA with Must-Links and Cannot-Links; SCLDA Yang et al. (2015)
expresses prior knowledge as sparse constraints; ISLDA Nikolenko et al. (2017)
fixes topic index $z$ for certain keywords in all documents. AVITM Srivastava
and Sutton (2017) is a neural topic model based on autoencoding Variational
Inference. We also compared our model with BERT Devlin et al. (2018), a well-
known neural language model, to test its document retrieval ability. To
evaluate the quality of our subtopics towards the target concepts, we compared
our model with HTM Blei et al. (2004), which is also a nonparametric Bayesian
model that can generate subtopics from higher level topics.

#### Parameterization

We set $\alpha=0.5$, $\beta=0.1$ for DF-LDA and $\alpha=0.1$, $\beta=0.01$ for
SCLDA as suggested by the original papers. We set $\alpha=1/K$, $\beta=1/K$
for LDA and ISLDA, where $K$ is the number of topics pre-set for the models,
and found it outperforms the original settings. We set $\alpha=0.1$,
$\gamma=0.1$ and $\eta=0.01$ for HTM as suggested by the original paper and
set the topic hierarchy depth to 3, to make it easier to compare with our
model since topics from the second level of HTM can be considered as the
parent topics and those from the third level as the subtopics of the parent
topics. We set $\alpha=1.0$, $\beta=0.5$ and $\gamma=1.5$ as in the original
HDP paper for our query-driven model, and set the threshold for the cosine
similarity used for the Generalized Pólya Urn scheme to 0.5 and the promotion
weight $u$ to 0.3. The number of representative words $M$ for the word
filtering strategy was set to 10. $\lambda$ for the REL query expansion
technique was set to 0.5 and $k$ was set to 100. In our experiments, we
treated each category as a concept and determined the number of topics for
each baseline model based on the number of categories in the datasets. For
example, if a dataset had 16 categories, we set the number of topics to 17,
using an extra one representing irrelevant information.

Model | 20news | TagMyNews | SearchSnippets
---|---|---|---
| Acc | coherence | Precision@K | Acc | coherence | Precision@K | Acc | coherence | Precision@K
LDA | 0.650 | 0.420 | 0.588 | 0.781 | 0.384 | 0.687 | 0.804 | 0.390 | 0.696
DFLDA | 0.623 | 0.421 | 0.562 | 0.772 | 0.386 | 0.649 | 0.795 | 0.390 | 0.644
SCLDA | 0.666 | 0.402 | 0.622 | 0.804 | 0.418 | 0.745 | 0.816 | 0.414 | 0.796
ISLDA | 0.680 | 0.406 | 0.645 | 0.801 | 0.411 | 0.729 | 0.845 | 0.421 | 0.804
BERT | $-$ | $-$ | 0.156 | $-$ | $-$ | 0.300 | $-$ | $-$ | 0.261
AVITM | 0.504 | 0.494 | 0.381 | 0.728 | 0.482 | 0.583 | 0.678 | 0.461 | 0.596
Query-driven model(FRE) | 0.707 | 0.433 | 0.679 | 0.807 | 0.429 | 0.716 | 0.858 | 0.469 | 0.807
Query-driven model(REL) | 0.601 | 0.452 | 0.557 | 0.837 | 0.444 | 0.749 | 0.851 | 0.501 | 0.780
Query-driven model(KLD) | 0.705 | 0.435 | 0.677 | 0.828 | 0.414 | 0.755 | 0.860 | 0.465 | 0.811
$+$ expert keywords | 0.690 | 0.430 | 0.659 | 0.817 | 0.493 | 0.747 | 0.864 | 0.503 | 0.841
$-$ word filtering | 0.706 | 0.434 | 0.678 | 0.823 | 0.413 | 0.744 | 0.859 | 0.432 | 0.811
$-$ GPU | 0.698 | 0.400 | 0.671 | 0.818 | 0.389 | 0.730 | 0.849 | 0.413 | 0.808

Table 1:  Parent topic evaluation results for three datasets. FRE indicates
frequency based query expansion; REL indicates Word embedding enhanced query
expansion; KLD indicates KL-Divergence based query expansion. BERT here is
only for document retrieval purpose therefore we can’t present the accuracy
and coherence in the table.

For all baseline models, we asked an expert to provide prior knowledge. Each
category in a dataset was associated with 10 keywords provided by the expert.
For DF-LDA, we converted keywords to must-links. Since LDA, DF-LDA, AVITM and
HTM cannot reveal the relationship between a concept and the generated topics
directly, we need a further step to find the relationship between them. We
calculated the average pairwise cosine similarity of the keywords and the
top-10 word embeddings of each topic, and chose the topic with the highest
similarity as the target topic of the concept. For HTM, we use the topics from
the second level of its generated topic hierarchy. For our model, we used
query phrases to represent the main concept of each category. Query phrases
were interpreted directly from category names, e.g., we used “ _computer
graphics_ ” to represent the category “comp.graphics” in the 20Newsgroup
dataset. We removed categories that do not have meaningful names due to the
difficulty of defining the query phrases for these categories, e.g.,
“talk.politics.misc” in the 20Newsgroup dataset. We then selected the top 10
concept words of each query based on the scores from the concept words
extractor. We list expert-defined keywords and query phrase for each category
in Appendix A. All models were trained until convergence. For BERT, we simply
used the query phrases to retrieve relevant documents. We ran each model five
times and present their average performance.

###  4.2 Parent Topic Evaluation

We evaluated the quality of parent topics of our model in terms of document
classification, topic coherence and document retrieval performance. For
document classification, a logistic regression classifier with default
parameter settings was used. We used the topic distribution of each document
as the input and conducted five-fold cross-validation. The topic distribution
of a document represents the probability of each topic in a document. The
quality of the topics can be assessed by the accuracy of text classification
using the topic-level representation. A better classification accuracy means
better latent semantic representations of the topics, indicating the learnt
topics are more discriminative and representative. For topic coherence
measure, we followed Roder et al. Röder et al. (2015) and used the best
performing topic coherence measure C_V based on the external corpus
(Wikipedia). We focused on the top 10 words of our parent topics and used the
Palmetto library algorithm Röder et al. (2015). Higher coherence indicates
better topic interpretability. For document retrieval, we adopted the metric
“precision@K” (P@K), which corresponds to the number of relevant results among
the top $K$ documents. We retrieved documents of each topic based on the
probability of the topic in the documents $p(z|d)$. If a topic can describe
the target concept well, then the top retrieved documents should be relevant
to the concept. In our experiments, we know the ground-truth number of
documents belonging to each category, therefore we set $K$ for each concept to
the actual number of documents from the corresponding category. We only
considered the parent topics and reported the average results. A higher score
indicates the model retrieves more concept-relevant documents, which is
important when a researcher wants to do a more in-depth study of related
documents.

Table 1 shows the performance of our models using three different query
expansion techniques as well as only using expert-defined key words as prior
knowledge. It can be observed that our models using the FRE and KLD query
expansion techniques outperform all baselines except AVITM on almost all
measures, though our model using the FRE query expansion technique has
slightly worse document retrieval performance on the TagMyNews dataset.
Although the model using REL is not as competitive as the models using FRE and
KLD on the 20newsgroup dataset, it has the highest coherence scores on all the
datasets, despite not using any expert-defined keywords as prior knowledge.
This shows that combining word embeddings in query expansion can help produce
more coherent prior knowledge. Although AVITM has better coherence score than
our model on the 20newsgroup and TagMyNews datasets, its poor document
retrieval performance indicates it is unable to find documents relevant to the
target concept. Comparing our query-driven model with or without using expert-
defined keywords, it achieves better coherence scores on the 20Newsgroup
dataset without expert-defined keywords, though it performs slightly worse on
the other two datasets.

As for document classification and document retrieval, our KLD-based model has
better performance than expert-defined keywords on 20newsgroup and TagMyNews,
but does not work well on SearchSnippets. This may be because our concept
words extractor does not work well on short texts. The concept words extracted
from TagMyNews and SearchSnippets are not as competitive as expert defined
keywords. In addition, different interpretations of the same concept word may
also compromise the performance. Interestingly, we also observed that BERT
does not work well on these datasets. Possibly this is because we are using
short query phrases to represent the concepts and BERT only works well for
long queries. A short query may not give enough information about the concept
that’s why we adopted query expansion and topic modeling approaches. Table 2
shows example concept-specific topics extracted from the TagMyNews dataset. It
can be seen that extracted topics are closely related to their respective
concept phrase. Topic extraction results on the other two datasets are shown
in Appendix B.

Concept Phrase |  Top 10 words
---|---
business |  profit, business, bank, sell, usa, sale, credit, price, billion, stock
entertainment |  week, show, star, theater, pop, time, film, tv, sony, wedding
health |  disease, health, study, care, risk, drug, cancer, insurance, people, usa
technology |  google, apple, technology, ipad, china, company, online, intel, service, network
sport game |  game, play, playoff, final, boston, win, series, scored, season, sport

Table 2:  Target concept topics for TagMyNews dataset.

Model | 20news | TagMyNews | SearchSnippets
---|---|---|---
| Diversity | Cohesion | overall | Diversity | Cohesion | overall | Diversity | Cohesion | overall
HTM | 0.94 | 0.54 | 0.51 | 0.93 | 0.53 | 0.49 | 0.86 | 0.49 | 0.42
Query-driven model | 0.71 | 0.79 | 0.56 | 0.68 | 0.79 | 0.54 | 0.74 | 0.76 | 0.56

Table 3:  Topic diversity and cohesion results for subtopics.

#### Ablation study:

We also studied the effectiveness of two major components in the proposed
model: 1) GPU to incorporate word embeddings; 2) word filtering to remove
unimportant words. The last two rows in Table 1 show the performance of our
model using KLD query expansion technique without GPU and word filtering
components. These show that GPU has a big impact for coherence and can help
improve other measures in some extents, while removing word filtering reduces
performance on all measures.

Concept phrase |  Parent topic |  Subtopics
---|---|---
atheism |  people, question, strong, belief, make, god, thing, point, religion, lack |  moral, system, morality, society, nature, objective, human, dream, animal, action
|  |  people, question, thing, make, point, god, argument, belief, claim, true
|  |  science, scientific, theory, result, observation, scientist, experiment, hypothesis, methodology, model
for sale |  sell, sale, original, sold, interested, included, price, offer, box, cd |  sale, offer, price, sell, original, shipping, box, condition, interested, cd
|  |  list, interested, send, mail, address, post, email, original, information, call
business |  3do, government, key, phone, technology, company, business, chip, encryption, clipper |  company, phone, 3do, technology, business, number, system, japanese, computer, make
|  |  government, clipper, encryption, chip, system, nsa, phone, people, security, key
|  |  key, chip, algorithm, number, clipper, encryption, de, escrow, system, secret

Table 4:  Parent topic and the subtopics of the concepts “ _atheism_ ”, “ _for
sale_ ” and “ _business_ ” for the 20newsgroup dataset.

###  4.3 Subtopics Evaluation

We used our model with the KLD-query expansion technique in this evaluation.
We dropped subtopics that have prevalence of less than $0.5\%$ in the corpus
as these subtopics usually are not of interest. We evaluated the quality of
subtopics in terms of topic diversity and topic cohesion444Note that _topic
cohesion_ is different from _topic coherence_ as _topic cohesion_ measure the
relevant between a subtopic and its parent topic.. Topic diversity measures
how much a subtopic overlaps with each other. We define it to be the
percentage of the unique words in the top 25 words of all subtopics
subordinate to the same parent topic Dieng et al. (2020). Higher diversity
indicates more varied topics, while lower diversity indicates more redundant
topics. Topic cohesion measures the relevance between the subtopics and the
parent topic. We define it to be the cosine similarity between the parent
topic embedding and the subtopic embedding. We can get the topic embedding as
the weighted summing of the embeddings of its top 10 associated word. We
combine these two metrics and define the overall quality of a subtopic as
their product.

We report the results in Table 3. It shows that our model outperforms HTM by
topic cohesion measures on all datasets, though with lower topic diversity
scores. The high cohesion score indicates that the subtopics of our model is
highly relevant to the target concept. By taking both measures into a account,
our model achieves relatively better performance. It is expected since we
incorporate domain prior knowledge into our model.

###  4.4 Qualitative Evaluation

We present the qualitative evaluation results in this section. We show a set
of topics produced by our model from the 20newsgroup dataset in Table 4. The
input concept phrases are shown in the left side of the table. For the concept
phrase “ _atheism_ ”, which means the absence of belief in the existence of
deities, we can see that our parent topic is highly relevant to it. The topic
words like “ _question_ ”, “ _belief_ ”, “ _god_ ” and “ _lack_ ” clearly
indicate that the topic is related to the arguments about God. By looking at
the subtopics, we can easily see the first subtopic is about the atheism
morality, the second subtopic is about the arguments between atheism and
theism, and the third subtopic is about the scientific explanation on atheism.
For the concept phrase “ _for sale_ ”, which means selling an item in a
cheaper price, our parent topic includes many relevant words, such as “ _sell_
”, “ _sale_ ”, “ _sold_ ” and “ _price_ ”. The inclusion of “ _box_ ” is less
easy to explain, but could be related to product packaging. As expected, our
subtopic reveals a sub-aspect about the concept that can not be identified
directly from the parent topic: the email subscription for the latest news.
This is reasonable, since merchants usually use email to provide customers
with information about the latest products. The words like “ _interested_ ”, “
_mail_ ”, “ _send_ ”, “ _information_ ” and “ _original_ ” provide more
information about the concept.

The last row of Table 4 presents the topics of the low occurrence query “
_business_ ”, appeared only 294 times in the corpus, which is extremely low
compared with the majority of other words in the corpus. LDA and HTM are
unable to generate relevant topics due to the aforementioned “higher order co-
occurrence” issue, but our model can produce reasonable topics. The topic
words “ _encryption_ ”, “ _key_ ”, “ _phone_ ”, “ _company_ ” and “ _business_
” in the parent topic shows that the topic is related to data encryption for
business. By looking at the subtopics of the topic, we can get a rough idea
that the first subtopic is about a Japanese phone company, since the top
weighted words include “ _japanese_ ”, “ _company_ ”, “ _phone_ ”, “
_technology_ ”. This makes sense since phone companies usually have a strong
requirement for encryption. The second and third subtopics are about
encryption algorithms, since the top weighted words include “ _chip_ ”, “
_nsa_ ”, “ _key_ ” and “ _algorithm_ ”. We further verified that our
interpretation is correct by looking at the top weighted documents of the
topics. This confirms that our model has potential for use in real world
applications.

##  5 Conclusions and Future Work

We presented a novel, query-driven topic model to help identify topics of
interest in large datasets. Instead of asking experts to define keywords for
these topics, we implemented a concept words extractor to automatically
extract concept words and used the GPU model, incorporating word-filtering, to
improve interpretability and performance. To distinguish between different
contexts for the same concept, we further introduced a subtopic modeling
procedure. The procedure can automatically infer all subtopics without having
to determine the optimal number of subtopics beforehand. Experimental results
on three benchmark datasets demonstrate the model’s promise. In the future, we
plan to evaluate our model’s performance using real-world, qualitative
analysis use cases.

## Acknowledgments

This work is partly funded by the EPSRC (grant no. EP/T017112/1,
EP/V048597/1). ZF receives the PhD studentship jointly funded by the
University of Warwick and China Scholarship Council. YH and RP are supported
by Turing AI Fellowships funded by UK Research and Innovation (UKRI) (grant
nos. EP/V020579/1 and EP/N510129/1 respectively).

## References

  * Andrzejewski and Zhu (2009) David Andrzejewski and Xiaojin Zhu. 2009.  Latent dirichlet allocation with topic-in-set knowledge.  In _Proceedings of the NAACL HLT 2009 Workshop on Semi-Supervised Learning for Natural Language Processing_ , pages 43–48.
  * Andrzejewski et al. (2009) David Andrzejewski, Xiaojin Zhu, and Mark Craven. 2009.  Incorporating domain knowledge into topic modeling via dirichlet forest priors.  In _Proceedings of the 26th annual international conference on machine learning_ , pages 25–32.
  * Andrzejewski et al. (2011) David Andrzejewski, Xiaojin Zhu, Mark Craven, and Benjamin Recht. 2011.  A framework for incorporating general domain knowledge into latent dirichlet allocation using first-order logic.  In _Twenty-Second International Joint Conference on Artificial Intelligence_.
  * Blei et al. (2004) David M Blei, Thomas L Griffiths, Michael I Jordan, and Joshua B Tenenbaum. 2004\.  Hierarchical topic models and the nested chinese restaurant process.  _Advances in neural information processing systems_ , 16(16):17–24.
  * Blei et al. (2003) David M Blei, Andrew Y Ng, and Michael I Jordan. 2003.  Latent dirichlet allocation.  _Journal of machine Learning research_ , 3(Jan):993–1022.
  * Carpineto et al. (2001) Claudio Carpineto, Renato De Mori, Giovanni Romano, and Brigitte Bigi. 2001.  An information-theoretic approach to automatic query expansion.  _ACM Transactions on Information Systems (TOIS)_ , 19(1):1–27.
  * Ceri et al. (2013) Stefano Ceri, Alessandro Bozzon, Marco Brambilla, Emanuele Della Valle, Piero Fraternali, and Silvia Quarteroni. 2013.  An introduction to information retrieval.  In _Web information retrieval_ , pages 3–11. Springer.
  * Chen et al. (2013) Zhiyuan Chen, Arjun Mukherjee, Bing Liu, Meichun Hsu, Malu Castellanos, and Riddhiman Ghosh. 2013.  Leveraging multi-domain prior knowledge in topic models.  In _Twenty-Third International Joint Conference on Artificial Intelligence_.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_.
  * Diaz et al. (2016) Fernando Diaz, Bhaskar Mitra, and Nick Craswell. 2016.  Query expansion with locally-trained word embeddings.  _arXiv preprint arXiv:1605.07891_.
  * Dieng et al. (2020) Adji B Dieng, Francisco JR Ruiz, and David M Blei. 2020.  Topic modeling in embedding spaces.  _Transactions of the Association for Computational Linguistics_ , 8:439–453.
  * El-Assady et al. (2019) Mennatallah El-Assady, Rebecca Kehlbeck, Christopher Collins, Daniel Keim, and Oliver Deussen. 2019.  Semantic concept spaces: Guided topic model refinement using word-embedding projections.  _IEEE transactions on visualization and computer graphics_ , 26(1):1001–1011.
  * Gemp et al. (2019) Ian Gemp, Ramesh Nallapati, Ran Ding, Feng Nan, and Bing Xiang. 2019.  Weakly semi-supervised neural topic models.
  * Heinrich (2009) Gregor Heinrich. 2009.  A generic approach to topic models.  In _Joint European Conference on Machine Learning and Knowledge Discovery in Databases_ , pages 517–532. Springer.
  * Hu et al. (2019) Nan Hu, Ting Zhang, Baojun Gao, and Indranil Bose. 2019.  What do hotel customers complain about? text analysis using structural topic model.  _Tourism Management_ , 72:417–426.
  * Lavrenko and Croft (2017) Victor Lavrenko and W Bruce Croft. 2017.  Relevance-based language models.  In _ACM SIGIR Forum_ , volume 51, pages 260–267. ACM New York, NY, USA.
  * Li et al. (2016) Chenliang Li, Haoran Wang, Zhiqian Zhang, Aixin Sun, and Zongyang Ma. 2016.  Topic modeling for short texts with auxiliary word embeddings.  In _Proceedings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval_ , pages 165–174.
  * Melville et al. (2019) Sophie Melville, Kathryn Eccles, and Taha Yasseri. 2019.  Topic modeling of everyday sexism project entries.  _Frontiers in Digital Humanities_ , 5:28.
  * Nikolenko et al. (2017) Sergey I Nikolenko, Sergei Koltcov, and Olessia Koltsova. 2017.  Topic modelling for qualitative studies.  _Journal of Information Science_ , 43(1):88–102.
  * Perotte et al. (2011) Adler Perotte, Frank Wood, Noemie Elhadad, and Nicholas Bartlett. 2011.  Hierarchically supervised latent dirichlet allocation.  _Advances in neural information processing systems_ , 24:2609–2617.
  * Röder et al. (2015) Michael Röder, Andreas Both, and Alexander Hinneburg. 2015.  Exploring the space of topic coherence measures.  In _Proceedings of the eighth ACM international conference on Web search and data mining_ , pages 399–408.
  * Srivastava and Sutton (2017) Akash Srivastava and Charles Sutton. 2017.  Autoencoding variational inference for topic models.  _arXiv preprint arXiv:1703.01488_.
  * Teh et al. (2005) Yee W Teh, Michael I Jordan, Matthew J Beal, and David M Blei. 2005.  Sharing clusters among related groups: Hierarchical dirichlet processes.  In _Advances in neural information processing systems_ , pages 1385–1392.
  * Wang et al. (2020) Rui Wang, Deyu Zhou, and Yulan He. 2020.  Optimising topic coherence with weighted po´ lya urn scheme.  _Neurocomputing_ , 385:329–339.
  * Xu et al. (2017) Jiaming Xu, Bo Xu, Peng Wang, Suncong Zheng, Guanhua Tian, and Jun Zhao. 2017.  Self-taught convolutional neural networks for short text clustering.  _Neural Networks_ , 88:22–31.
  * Xu et al. (2018) Yueshen Xu, Jianwei Yin, Jianbin Huang, and Yuyu Yin. 2018.  Hierarchical topic modeling with automatic knowledge mining.  _Expert Systems with Applications_ , 103:106–117.
  * Yang et al. (2015) Yi Yang, Doug Downey, and Jordan Boyd-Graber. 2015.  Efficient methods for incorporating knowledge into topic models.  In _Proceedings of the 2015 conference on empirical methods in natural language processing_ , pages 308–317.
  * Yao and Wang (2020) Fang Yao and Yan Wang. 2020.  Tracking urban geo-topics based on dynamic topic model.  _Computers, Environment and Urban Systems_ , 79:101419.

## Appendix A: Query and keywords for each category

Concept Phrase | Expert Defined Keywords
---|---
atheism | Agnosticism | theism | deism | islam | paganism | moral | atheist | religions | argument | exist
computer graphics | image | digital | visual | 3d | 2d | visualization | print | geometry | synthesizing | processing
pc hardware | cpu | monitor | keyboard | memory | card | sound | speakers | motherboard | power | pc
mac hardware | touchpad | touchbar | drive | apple | mac | ram | gpu | system | sensors | physical
for sale | product | mail | discount | bargain | shopping | price | sale | propertise | rent | summer
automobile | car | vehicle | transportation | wheel | tire | road | parking | gasoline | energy | driver
motorcycles | bike | scooters | mopads | motorbikes | trowel | commute | helmet | ride | speed | harley
baseball | player | ball | small | hit | team | fielding | batting | runs | nbl | baseball
hockey | puck | nhl | hockey | ice | rink | canada | rubber | curve | skater | guard
encrypt | encoding | decryption | cryptographic | secure | plaintext | ciphertext | key | algorithm | pseudo | private
electronics | equipment | science | electricity | wire | console | computer | outlet | engineering | power | voltage
medicine | medicine | surgery | hospital | climic | doctor | nurse | healthcare | symtoms | prescription | pharmacy
space | rocket | nasa | astronomy | explore | moon | outerspace | spaceship | telescope | satellite | orbit
christian | belief | faith | church | christianity | ethics | culture | ritual | Jesus | bible | truth
guns | law | regulation | usa | victim | murder | violence | litigation | debate | firearms | legal
middle east | israel | Iran | Iraq | war | territory | turkey | attack | soldier | turkey | government

Table A1:  Concept phrases and expert defined keywords for the 20NewsGroup
dataset.

Concept Phrase | Expert Defined Keywords
---|---
business | bank | stock | market | business | economy | financial | investor | profit | price | deal
entertainment | film | movie | music | tv | theater | festival | actor | show | book | hollywood
health | drug | health | cancer | patient | disease | medical | hospital | healthcare | doctor | treatment
technology | apple | google | sony | facebook | internet | mobile | ipad | technology | microsoft | phone
sport game | league | win | player | team | tournament | game | playoff | sport | championship | point

Table A2:  Concept phrases and expert defined keywords for the TagMyNews
dataset.

Concept Phrase | Expert Defined Keywords
---|---
Business | bank | stock | market | business | economy | financial | investor | profit | price | deal
Computers | computer | software | programming | parallel | computing | memory | hardware | driver | cpu | processor
Culture Arts Entertainment | movie | music | art | film | artist | museum | fashion | culture | imdb | actor
Education Science | research | science | journal | university | student | education | scientific | mathematics | theory | school
Car Engineering | engine | electrical | car | wheel | model | automobile | industrial | vehicle | cylinder | jet
Health | drug | health | cancer | patient | disease | medical | hospital | healthcare | doctor | treatment
Politics Society | political | party | democracy | government | republic | parliamentary | representative | president | communist | congress
Sports | league | football | player | team | tournament | game | basketball | sport | hockey | championship

Table A3:  Concept phrases and expert defined keywords for the SearchSnippets
dataset.

## Appendix B: Topics generated for target concepts

Concept Phrase | Top 10 words
---|---
atheism | people | question | thing | god | strong | point | make | belief | argument | evidence
computer graphics | support | file | version | image | list | graphic | program | information | screen | address
pc hardware | drive | pc | disk | scsi | software | modem | port | hard | controller | system
mac hardware | card | mac | monitor | apple | system | video | problem | write | chip | work
for sale | sell | sale | sold | original | interested | included | price | offer | box | cd
automobile | car | auto | automobile | engine | ford | problem | mile | v6 | oil | dealer
motorcycles | bike | riding | ride | motorcycle | rider | battery | buying | dog | back | dod
baseball | run | baseball | game | pitcher | year | hit | player | average | team | good
hockey | game | hockey | team | nhl | night | goal | player | coach | cup | year
encrypt | key | message | chip | encryption | government | clipper | algorithm | system | phone | encrypted
electronics | company | power | line | led | electronics | electronic | circuit | output | work | signal
medicine | patient | medical | treatment | doctor | disease | study | clinical | medicine | food | effect
space | space | nasa | shuttle | launch | satellite | station | moon | 1st | cost | orbit
christian | god | christ | church | christian | love | word | bible | jesus | protestant | truth
guns | gun | control | weapon | child | people | police | fire | law | handgun | amendment
middle east | israel | arab | armenian | jew | israeli | muslim | people | middle | east | war

Table B1:  Topics of target concepts for the 20NewsGroup dataset.

Concept Phrase | Top 10 words
---|---
Business | business | management | marketing | trade | service | market | law | export | job | stock
Computers | computer | computing | software | web | application | system | programming | apple | memory | chip
Culture Arts Entertainment | art | culture | music | american | artist | tradition | history | ancient | museum | band
Education Science | science | education | research | scientific | undergraduate | biology | journal | school | university | fiction
Car Engineering | car | model | engineering | automobile | engine | wheel | auto | electrical | product | motor
Health | health | disease | care | cancer | public | nutrition | information | medical | gov | drug
Politics Society | political | party | democracy | system | military | politics | government | conflict | gov | war
Sports | football | team | soccer | game | sport | hockey | news | tennis | score | player

Table B2:  Topics of target concepts for the SearchSnippets dataset.

## Appendix C: Algorithms

foreach  _document $j\in D$_ do

$k\leftarrow z\neq\tilde{z}_{Q}\sim Multinomial(1/K)$;

foreach  _position $i\in j$_ do

foreach  _$W_{q}\in W_{Q}$_ do

if  _$w_{ji}\in W_{q}$_ then

$k\leftarrow\tilde{z}_{q}$;

break;

end if

end foreach

end foreach

$t\leftarrow 0$;

foreach  _position $i\in j$_ do

$S_{j,w_{ji}}\leftarrow 0$;

$t_{ji}\leftarrow t$;

$k_{jt}\leftarrow k$;

UpdateCounter($S_{j,w_{ji}}$, $t_{ji}$, $k_{jt}$, $True$);

$t\leftarrow t+1$;

end foreach

end foreach

Algorithm 2 Initialize($K$, $D$, $W_{Q}$)

if  _$operation==True$_ then

if  _$t==t^{new}$_ then

$m_{k}\leftarrow m_{k}+1$;

end if

if  _$S_{j,w}==1$_ then

/* To apply GPU */;

foreach  _$(w_{i},w_{q})\in\mathcal{M}$_ do

if  _$w==w_{i}$_ then

$n_{jt}\leftarrow n_{jt}+A_{i,q}$;

$n_{kw}\leftarrow n_{kw}+A_{i,q}$;

end if

end foreach

else

$n_{jt}\leftarrow n_{jt}+1$;

$n_{kw}\leftarrow n_{kw}+1$;

end if

else

if  _$S_{j,w}==1$_ then

/* To remove counts from GPU */;

foreach  _$(w_{i},w_{q})\in\mathcal{M}$_ do

if  _$w==w_{i}$_ then

$n_{jt}\leftarrow n_{jt}-A_{i,q}$;

$n_{kw}\leftarrow n_{kw}-A_{i,q}$;

end if

end foreach

else

$n_{jt}\leftarrow n_{jt}-1$;

$n_{kw}\leftarrow n_{kw}-1$;

end if

if  _$n_{jt}==0$_ then

$m_{k}\leftarrow m_{k}-1$;

end if

end if

Algorithm 3 UpdateCounter($S_{j,w}$, $t$, $k$, $operation$)

Note: $n_{kw}$ denotes the word count of $w$ in topic $k$; $\tilde{z}_{Q}$
denotes the concept related topics.


# Anderson acceleration of gradient methods with energy for optimization
problems

Hailiang Liu†* ,  Jia-Hao He‡ and  Xuping Tian† Dedicated to Professor Stanley
Osher on the occasion of his 80th birthday

###### Abstract.

Anderson acceleration (AA) as an efficient technique for speeding up the
convergence of fixed-point iterations may be designed for accelerating an
optimization method. We propose a novel optimization algorithm by adapting
Anderson acceleration to the energy adaptive gradient method (AEGD)
[arXiv:2010.05109]. The feasibility of our algorithm is examined in light of
convergence results for AEGD, though it is not a fixed-point iteration. We
also quantify the accelerated convergence rate of AA for gradient descent by a
factor of the gain at each implementation of the Anderson mixing. Our
experimental results show that the proposed algorithm requires little tuning
of hyperparameters and exhibits superior fast convergence.

###### Key words and phrases:

Anderson acceleration, gradient descent, energy stability

###### 1991 Mathematics Subject Classification:

65K10, 68Q25

†Department of Mathematics, Iowa State University, Ames, IA, USA

‡Department of Agricultural and Biosystems Engineering, Iowa State University,
Ames, IA, USA

*corresponding author<EMAIL_ADDRESS>
##  1\. Introduction

We are concerned with nonlinear acceleration of gradient methods with energy
for optimization problems of form

(1.1) $\min_{x\in\mathbb{R}^{n}}f(x),$

where $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ is assumed to be differentiable
and bounded from below. Gradient descent (GD), known for its easy
implementation and low computational cost, has been one of the most popular
optimization algorithms. However, the practical performance of this well-known
first-order method is often limited to convex problems. For non-convex or ill-
conditioned problems, GD can develop a zig-zag pattern of subsequent iterates
as iterations progress, resulting in slow convergence. Multiple acceleration
techniques have been proposed to address these deficiencies, including those
in the fast gradient methods [24, 35] and the momentum or heavy-ball method
[6]. Although reasonably effective and computationally efficient, the gradient
descent method with these techniques might still suffer from the step size
limitation.

AEGD (adaptive gradient descent with energy) is an improved variant of GD
originally introduced in [17] to address the step size issue. AEGD adjusts the
effective step size by a transformed gradient and an energy variable. The
method, when applied to the problem (1.1), includes two ingredients: the base
update rule:

(1.2) $x_{k+1}=x_{k}+2\eta r_{k+1}v_{k},\quad r_{k+1}=\frac{r_{k}}{1+2\eta
v^{2}_{k}},$

and the evaluation of the transformed gradient $v_{k}$ as

(1.3) $v_{k}=\frac{\nabla f(x_{k})}{2\sqrt{f(x_{k})+c}}.$

AEGD is unconditionally energy stable with guaranteed convergence in energy
regardless of the size of the base learning rate $\eta>0$ and how $v_{k}$ is
evaluated. Adding momentum through modifying $v_{k}$ can further accelerate
the convergence in both deterministic and stochastic settings [18, 19, 20].

In this paper, we aim to speed up AEGD with another acceleration technique,
called Anderson acceleration (AA) [2]. As a nonlinear acceleration technique,
AA has been used for decades to speed up the convergence of a sequence by
using previous iterates to extrapolate a new estimate. AA is widely known in
the context of fixed-point iterations [37, 40]. Recently, AA has also been
adapted to various optimization algorithms [23, 3, 5, 27, 13, 31]; More
specifically, we refer to [23] for the proximal gradient algorithm, [3] for
the coordinate descent, [5] for primal-dual methods, [27] for the ADMM method,
[13] for the Douglas-Rachford algorithm, and [31] for stochastic algorithms.
All these algorithms can be formulated as involving fixed-point iterations. In
contrast, our work applies AA to an optimization algorithm that is not a
fixed-point iteration.

Convergence analysis of AA for general fixed-point maps has been reported in
the literature only recently [1, 8, 36, 4]. If the fixed point map is a
contraction, the first local convergence results for AA are provided in [1, 8]
for either $m=1$ or general $m$ if the coefficients in the linear combination
remain bounded; see also [36, 4] for further extensions to nonsmooth or
inaccurate function evaluations. But these results do not show how much AA can
help accelerate the convergence rate. Our convergence rates on AA with GD are
for general $m>1$, showing both the linear rate of the GD for strongly convex
objectives and the additional gain from AA. The amount of acceleration at each
AA implementation is quantified by using a projection operator. This improves
a convergence bound in [16] (see Remark 3.3). For contracting fixed point
maps, we refer to [10] for a refined estimate of the convergence gain by AA,
and [34, 38] for further asymptotic linear convergence speed of AA when
applied to more general fixed-point iteration and ADMM, respectively. Sharper
local convergence results of AA remain a hot research topic in this area.

The motivation of this work is to incorporate the two acceleration techniques:
adaptive gradient descent with energy and AA, into one framework so that the
resulting method can take advantage of both techniques. We summarize the main
contributions of this work as follows:

  * •

With AA for GD, we quantify the gain of convergence rate for both quadratic
and non-quadratic minimization problems by a ratio factor of the optimized
gradient compared to that of the vanilla GD.

  * •

We present a modification of AA for AEGD by introducing an extra
hyperparameter that controls the implementation frequency of AA. Our algorithm
(Algorithm 2) is shown to be insensitive to both the step size $\eta$ and the
length of the AA window $m$, thus requiring little hyperparameter tuning.

  * •

We also adapt our algorithm for the proximal gradient algorithm (Algorithm 3)
for solving a class of composite optimization problems whose objective
function is given by the summation of a general smooth and nonsmooth
component.

  * •

We verify the superior performance of our algorithms on both convex and non-
convex tests, also on two machine learning problems. In all cases, our
proposed algorithms exhibit faster convergence than AA with vanilla gradient
descent.

###  1.1. Related work

As its name suggests, AA or Anderson mixing (AM) is an acceleration algorithm
originally developed by D. G. Anderson [2] for solving some nonlinear integral
equations, and it is now commonly used in scientific computations for problems
that can be regarded as involving a fixed-point iteration. Applications
include flow problems [7, 21, 15], electronic structure computations [2, 12],
wave propagation [39, 22], and deep learning [26, 14]. In a broad literature
on this subject, these papers are only meant to show the variety of results
obtained by the AA.

The connection between AA and some other classical methods also facilitates
our understanding of AA. As originally noted by Eyert [11] and clarified by
Fang and Saad [12], AA is remarkably related to a multisecant quasi-Newton
updating. For linear iterations, AA with full-memory (i.e., $m=\infty$ in
Algorithm 1) is essentially equivalent to the generalized minimal residual
(GMRES), as shown in [37, 25, 28]. The acceleration property of AA is also
understood from its close relation to Pulay mixing [29] and to DIIS (Direct
Inversion on the Iterative Subsapce) [30, 8]. AA is also related to other
acceleration techniques for vector sequences, where they are known under
various names, e.g. minimal polynomial extrapolation [33] or reduced rank
extrapolation [9].

###  1.2. Organization

The paper is organized as follows. In Section 2, we start by reviewing the
sequence acceleration method – AA. In Section 3, we recollect the theoretical
results of the fixed-point iterations with AA and then extend the result to GD
with nonlinear iterations. In Section 4, we recall the convergence of AEGD to
explain how to implement AA with AEGD, and further introduce AA-AEGD to the
application of proximal gradient descent. Finally, we present numerical
results in Section 5 and the conclusion in Section 6.

##  2\. Review of Anderson acceleration

AA is an efficient acceleration method for fixed-point iterations
$x_{k+1}=G(x_{k})$, which is assumed to converge to $x^{*}$ such that
$x^{*}=G(x^{*})$. The key idea of the AA is to form a new extrapolation point
by making better use of past iterates. To illustrate this method, we consider
a window of sequence of $k+1$ elements and their updates, denoted by
$X=[x_{0},x_{1},\cdots x_{k}]$ and $Y=G(X)=[G(x_{0}),\cdots,G(x_{k})]$,
respectively. And denote $R_{k}=G(x_{k})-x_{k}$ as the residual at $x_{k}$.
The goal is to find $\alpha\in\mathbb{R}^{k+1}$ such that

(2.1) $y_{k+1}=X\alpha,\quad\alpha^{\top}\mathbf{1}=1$

has a faster convergence rate in the sense that

$\|y_{k+1}-x^{*}\|<<\|x_{k+1}-x^{*}\|,\quad x_{k+1}=G(x_{k}).$

AA determines $\alpha$ by solving the following minimization problem

(2.2) $\alpha={\rm argmin}_{\alpha^{\top}\mathbf{1}=1}\|R\alpha\|_{2},$

where $R=[R_{0},\cdots,R_{k}]$ is the residual matrix. As an extension to AA,
one may modify (2.1) by introducing a variable relaxation parameter
$\beta\in(0,1]$:

$y_{k+1}=[(1-\beta)X+\beta Y]\alpha.$

We summarize the method with the window of length $m$ in Algorithm 1.

Algorithm 1 Anderson Acceleration (AA)

1:$G(\cdot)$: fixed iteration map; $x_{0}$: initialization of the parameter;
$\eta$: step size, $m$: length of the window; $\beta$: relaxation parameter;
$K$: total number of iterations.

2:Set $x_{1}=G(x_{0})$ and $R_{0}=G(x_{0})-x_{0}$.

3:for $k=1\dots,K-1$ do

4: $m_{k}=\min\\{m,k\\}$

5: $R_{k}=G(x_{k})-x_{k}$

6: Solve
$\min_{\alpha^{k}=(\alpha^{k}_{k-m_{k}},\dots,\alpha^{k}_{k})^{\top}}\|\sum_{j=k-m_{k}}^{k}\alpha_{j}^{k}R_{j}\|_{2}^{2}$
subject to $\sum_{j=k-m_{k}}^{k}\alpha_{j}^{k}=1$

7:
$x_{k+1}=(1-\beta)\sum_{j=k-m_{k}}^{k}\alpha_{j}^{k}x_{j}+\beta\sum_{j=k-m_{k}}^{k}\alpha_{j}^{k}G(x_{j})$

8:return $x_{K}$

One notable advantage of AA is that they do not require to know how the
sequence is actually generated, thus the applicability of AA is quite wide. To
apply AA, it is wise to keep in mind the following two aspects:

  * (i)

The method only applies to the regime when the sequence admits a limit, which
requires that the original iteration scheme has a convergence guarantee.

  * (ii)

The residual matrix $R$ can be rank-deficient, then instability may occur in
computing $\alpha$. This would require the use of some regularization
techniques to obtain a reliable $\alpha$ [32]. By solving a regularized least
square problem, $\alpha^{k}$ in Algorithm 1 can be expressed as

(2.3)
$[\alpha_{k-m_{k}}^{k},\cdots,\alpha_{k-1}^{k}]=(U_{k}^{\top}U_{k}+\lambda
I)^{-1}U_{k}^{\top}R_{k},\quad\alpha^{k}_{k}=1-\sum_{j=k-m_{k}}^{k-1}\alpha_{j}^{k}.$

where $U_{k}=[U_{k,k-m_{k}},\cdots,U_{k,k-1}]$ with $U_{k,j}=R_{k}-R_{j}$,
$\lambda>0$ is the regularization parameter introduced by adding

$\lambda\|[\alpha^{k}_{k-m_{k}}\cdots\alpha^{k}_{k-1}]\|^{2}.$

in line 5 of Algorithm 1. This treatment bears further comment, see the
discussion on computing $\alpha$ in Section 4.2.

##  3\. Anderson acceleration for optimization algorithms

The classical method to solve problem (1.1) is Gradient Descent (GD), which is
defined by

(3.1) $x_{k+1}=x_{k}-\eta\nabla f(x_{k}),$

where $\eta>0$ is the step size. This can be viewed as the fixed-point
iteration applied to $G(x)=x-\eta\nabla f(x)$. The fixed point $x^{*}$ of $G$,
which corresponds to $\nabla f(x^{*})=0$, is a stationary point of $f$. To
illustrate how AA helps accelerate GD, we consider the quadratic minimization
problem

(3.2) $f(x)=\frac{1}{2}x^{\top}Ax-b^{\top}x,$

where $A$ is a symmetric positive definite matrix and the eigenvalues of A are
bounded with $\sigma(A)\in[\mu,L]$. For this problem, GD reduces to the
following fixed-point iteration:

(3.3) $x_{k+1}-x^{*}=M(x_{k}-x^{*}),$

where $M=I-\eta A$ and $x^{*}=A^{-1}b$. It can be verified that if
$\eta=\frac{2}{L+\mu}$, then $\|M\|\leq\rho=\frac{L-\mu}{L+\mu}<1$, and
$x_{k}$ converges to $x^{*}$ at a linear rate with

(3.4) $x_{i}-x^{*}=M^{i}(x_{0}-x^{*}),\quad i=1,\cdots,k+1.$

Now we investigate how the convergence rates can be improved using a linear
combination of the previous iterations:

$\displaystyle\|x_{k+1}^{AA}-x^{*}\|=\Bigg{\|}\sum_{i=0}^{k}\alpha_{i}x_{i}-x^{*}\Bigg{\|}$
$\displaystyle=\Bigg{\|}\sum_{i=0}^{k}\alpha_{i}(x_{i}-x^{*})\Bigg{\|}=\|p_{k}(M)(x_{0}-x^{*})\|,$

where we define the polynomial $p_{k}(M)=\sum_{i=0}^{k}\alpha_{i}M^{i}$ and
$p_{k}(1)=1$. Using Chebyshev polynomials, the $l_{2}$ norm of the above error
is bounded by (see Proposition 2.1 in [32]):

$\min_{p_{k}\in
P^{k},p_{k}(1)=1}\|p_{k}(M)(x_{0}-x^{*})\|\leq\left\\{\begin{array}[]{ll}\frac{2\gamma^{k}}{1+\gamma^{2k}}\|x_{0}-x^{*}\|&k<d,\\\
0&\text{otherwise}.\end{array}\right.$

where $P^{k}$ is the subspace of polynomials of degree at most $k$ and

$\gamma=\frac{1-\sqrt{1-\rho}}{1+\sqrt{1-\rho}}<1.$

This when applied to the case $M=I-\eta A$ with $\eta=\frac{2}{L+\mu}$, we
obtain

$\gamma=\frac{\sqrt{\mu+L}-\sqrt{2\mu}}{\sqrt{\mu+L}+\sqrt{2\mu}}.$

This error bound is slightly smaller than that stated in [32, Corollary 2.2].
This is faster (since $\gamma<\rho$) than GD which based on (3.4 admits the
convergence rate of

$\|x_{k+1}-x^{*}\|=\rho^{k+1}\|x_{0}-x^{*}\|.$

For AA with a finite $m$, how AA can help accelerate the convergence of an
optimization method is relatively less understood. We present a simple result
to show the accelerating effect.

######  Theorem 3.1 (Convergence of AA-GD for quadratic functions).

For $f(x)=\frac{1}{2}x^{\top}Ax-b^{\top}x$ with $A^{\top}=A$ and
$\sigma(A)\in[\mu,L]$, Algorithm 1 with $\beta=1$ and
$\eta\leq\frac{2}{L+\mu}$ guarantees

(3.5) $\|\nabla f(x_{k+1})\|/\|\nabla f(x_{k})\|\leq\delta_{k}(1-\eta\mu),$

where $\delta_{k}=\|\Pi_{k}\nabla f(x_{k})\|/\|\nabla f(x_{k})\|\leq 1$. Here
$\Pi_{k}$ is a projection operator defined by
$\Pi_{k}=I-U_{k}(U_{k}^{\top}U_{k}+\lambda I)^{-1}U_{k}^{\top},$ where
$U_{k}=[U_{k,k-m_{k}},\cdots,U_{k,k-1}]$ with $U_{k,j}=\nabla f(x_{k})-\nabla
f(x_{j})$, $\lambda$ is the regularization parameter for computing $\alpha$
(2.3). Moreover, we have the following convergence rate:

(3.6)
$\|x_{k+1}^{AA}-x^{*}\|\leq\prod_{j=0}^{k}\delta_{j}(1-\eta\mu)^{k+1}\left(\frac{L}{\mu}\right)\|x_{0}-x^{*}\|.$

The proof is deferred to Appendix A. This result defines the gain of the
optimization stage at iteration $k$ to be the ratio $\delta_{k}$ of the
optimized gradient compared to that of the vanilla GD.

The above result can be extended to the general non-quadratic case.

######  Theorem 3.2 (Convergence of AA-GD for non-quadratic functions).

For $f(x)\in C^{2}$ and $\sigma(D^{2}f)\in[\mu,L]$, let $x^{*}$ be a minimum
of $f(x)$, $x_{k}$ be the solution generated by Algorithm 1 with $\beta=1$ and
$\eta\leq\frac{2}{L+\mu}$. When $\|x_{k}-x^{*}\|$ is sufficiently small for a
large $k$, we have

(3.7) $\|\nabla f(x_{k+1})\|/\|\nabla
f(x_{k})\|\leq\delta_{k}(1-\eta\mu)+o(k),$

where $o(k)\to 0$ as $k\to\infty$, with $\Pi_{k}$ defined in Theorem 3.1,

$\delta_{k}=\|\Pi_{k}\nabla f(x_{k})\|/\|\nabla f(x_{k})\|\leq 1.$

The proof is deferred to Appendix B.

######  Remark 3.3.

Note that the first term on the right hand side of (3.7) is the same as that
in (3.5) for the quadratic case, and the second term converges to zero of
order

$\omega(\|x_{i}-x^{*}\|),$

where $i=k-m_{k},\cdots,k$, and $\omega(\cdot)$ is a modulus of continuity of
$\nabla^{2}f$. Under stronger assumptions that $\nabla^{2}f$ is also Lipschitz
continuous and $\eta=\frac{2}{L+\mu}$, the convergence bound given in [16,
Theorem 2] corresponds to

$\|\nabla f(x_{k+1})\|/\|\nabla f(x_{k})\|\leq
1-\eta\mu+O(\Delta_{k}),\quad\Delta_{k}:=\max_{i\in[m_{k}]}\|x_{k}-x_{k-i}\|.$

We note that the usual momentum acceleration differs from AA since the former
seeks to modify the algorithmic structures at each iteration. For example,
using two recent iterates, one has the following update rule:

$\displaystyle y_{k}=(1+\beta)x_{k}-\beta x_{k-1},$ $\displaystyle
x_{k+1}=y_{k}-\eta\nabla f(y_{k}).$

This when taking $\beta=(k-1)/(k+2)$ is the celebrated Nesterov’s acceleration
[24, 35], which guarantees optimal convergence with sublinear rate
$O(1/k^{2})$ for convex functions $f(x)$ with L-Lipschitz-continuous
gradients. With AA more historical iterates are used to improve the rate of
convergence of fixed-point iterations. This said, there are also works on
accelerating the Nesterov method by AA [34].

##  4\. Anderson acceleration for AEGD

Having seen the acceleration of AA for GD with the convergence gain quantified
by a factor $\delta_{k}\leq 1$ at $k-$th step, we proceed to see how it may
translate to improved asymptotic convergence behavior for AEGD.

###  4.1. Review of AEGD

Denote $F(x):=\sqrt{f(x)+c}$ with $c\in\mathbb{R}$ such that $f(x)+c>0$. AEGD
is defined by

(4.1a) $\displaystyle v_{k}$ $\displaystyle=\nabla F(x_{k}),$ (4.1b)
$\displaystyle r_{k+1}$ $\displaystyle=\frac{r_{k}}{1+2\eta v^{2}_{k}},$
(4.1c) $\displaystyle x_{k+1}$ $\displaystyle=x_{k}-2\eta r_{k+1}v_{k}.$

Here $v_{k}$ can be written explicitly as $\nabla f(x_{k})/(2F(x_{k}))$, which
represents the descent direction. This method is shown to be unconditional
energy stable in the sense that $r_{k}$, serving as an approximation to
$F(x_{k})$, decreases monotonically regardless of the step size $\eta$.

Note that (4.1c) can be rewritten as

(4.2) $x_{k+1}=x_{k}-\eta_{k}\nabla
f(x_{k}),\quad\eta_{k}=\eta\frac{r_{k+1}}{F(x_{k})},$

which shows that AEGD is not a fixed-point iteration due to the energy
adaptation in the effective step size. However, since AA is a sequence
acceleration technique, we expect AEGD to still gain a speedup from this
technique as long as it is convergent. Indeed, it has been established in [17]
that under some structural conditions on $f$, the sequence $x_{k}$ generated
by AEGD converges to a minimizer $x^{*}$. Below we present the convergence
result of AEGD under the Polyak-Lojasiewicz (PL) condition.

######  Theorem 4.1 (Convergence of AEGD [17]).

Suppose that the objective function $f$ is L-smooth: $\|\nabla^{2}f(x)\|\leq
L$ for any $x\in\mathbb{R}^{n}$ and $\max\|\nabla f(x)\|\leq G_{\infty}$.
Denote $x^{*}\in\operatorname*{arg\\!\min}_{x}f(x)$ and
$r^{*}=\lim_{k\to\infty}r_{k}$, then

$r_{k}>r^{*}>F(x^{*})(1-\eta/\tau),$

where $\tau>0$ is a constant that depends on $F(x^{*}),F(x_{0}),L$ and
$G_{\infty}$. Moreover, for $f$ that further satisfies the PL condition:
$\|\nabla f(x)\|^{2}\geq\mu(f(x)-f(x^{*}))$ for any $x\in\mathbb{R}^{n}$. If
$\max_{j<k}\eta_{j}\leq 1/L$, then $x_{k}\to x^{*}$ and

$\displaystyle\sum_{k=0}^{\infty}\|x_{k+1}-x_{k}\|\leq\frac{4}{\sqrt{2\mu}}\sqrt{f(x_{0})-f(x^{*})},$
$\displaystyle f(x_{k})-f(x^{*})\leq e^{-c_{0}kr_{k}}(f(x_{0})-f(x^{*})),\quad
c_{0}:=\frac{\mu\eta}{\sqrt{f(x_{0})+c}}.$

The convergence result stated above indicates that when $\eta$ is suitable
small, we have

$x_{k}\to
x^{*},\quad\eta_{k}=\eta\frac{r_{k+1}}{F(x_{k})}\to\eta\frac{r^{*}}{F(x^{*})}=\eta^{*}>0.$

Hence asymptotically, AEGD is close to the fixed-point iteration with
$G(x)=x-\eta^{*}\nabla f(x)$ when the $x_{k}$ is close to $x^{*}$.

###  4.2. Algorithm

Based on the above argument, we incorporate AA into AEGD and summarize the
resulting algorithm, named AA-AEGD, in Algorithm 2.

Algorithm 2 AA-AEGD($m,q$) (proposed)

1:$x_{0}$: initialization of the parameter, $c$: a constant satisfies
$f(x)+c>0$; $r_{0}=\sqrt{f(x_{0})+c}\bf{1}$: initialization of the energy
parameter; $\eta$: step size, $m$: length of the window; $\beta$: relaxation
parameter; $K$: total number of iterations.

2:for $k=0\dots,K-1$ do

3: $v_{k}=\nabla f(x_{k})/(2\sqrt{f(x_{k})+c})$

4: $r_{k+1}=r_{k}/(1+2\eta v_{k}^{2})$

5: $x_{k+1}=x_{k}-2\eta r_{k+1}v_{k}$

6: $R_{k}=x_{k+1}-x_{k}$

7: if $k=0\;\text{mod}\;q$ and $k\neq 0$ then

8: Solve
$\min_{\alpha^{k}=(\alpha^{k}_{k-m},\dots,\alpha^{k}_{k})^{\top}}\|\sum_{j=k-m}^{k}\alpha_{j}^{k}R_{j}\|^{2}_{2}$
subject to $\sum_{j=k-m}^{k}\alpha_{j}^{k}=1$

9:
$x_{k+1}^{AA}=(1-\beta)\sum_{j=k-m}^{k}\alpha_{j}^{k}x_{j}+\beta\sum_{j=k-m}^{k}\alpha_{j}^{k}x_{j+1}$

10: $x_{k+1}=x_{k+1}^{AA}$

11:return $x_{K}$

Some implementation techniques in the algorithm will be used in our
experiments. We thus introduce and discuss their effects through experiments
on a quadratic function.

Computation of $\alpha$. The optimization problem in Algorithm 2 can be
formulated as an unconstrained least-squares problem:

(4.3)
$\min_{(\alpha^{k}_{k-m},\dots,\alpha^{k}_{k-1})^{\top}}\Bigg{\|}R_{k}-\sum_{j=k-m}^{k-1}\alpha_{j}^{k}(R_{k}-R_{j})\Bigg{\|}^{2}_{2},\quad\text{set}\quad\alpha_{k}^{k}=1-\sum_{j=k-m}^{k-1}\alpha_{j}^{k},$

which can be solved by standard methods such as QR decomposition with a cost
of $\mathcal{O}(2m^{2}n)$, where $n$ is the dimension in state space. Since
$m$ is typically used less than $10$ in practice, AA can be implemented with
efficient computation. In our experiments, we add a regularization of
$\lambda\|[\alpha^{k}_{k-m}\cdots\alpha^{k}_{k-1}]\|^{2}_{2}$ to (4.3) to
avoid singularity, where $\lambda>0$ is a parameter, as implemented in [32].
The explicit expression of $\alpha^{k}$ is given in (2.3).

AA implementation of frequency. Unlike the standard version presented in
Algorithm 1, which implements AA in every step, Algorithm 2 implements AA in
every $q$ steps. We denote the former version as AA-GD/AEGD($m,1$), and the
latter version as AA-GD/AEGD($m,q$). Obviously, AA($m,q$) requires less
computation than AA($m,1$). Another advantage of AA($m,q$) is that it is less
sensitive to the effect of $\eta$ and $m$, as evidenced by numerical
experiments (see Figure 1). This is a favorable property since it indicates
that the proposed algorithm requires little tuning of hyperparameters.

(a) The effect of $\eta$

(b) The effect of $m$

Figure 1. The effect of $\eta$ and $m$ on AA-GD/AEGD($m,1$) and AA-
GD/AEGD($m,q$) for solving the quadratic problem (3.2) with $\kappa=10^{3}$,
where $\kappa=\sigma_{max}(A)/\sigma_{min}(A)$ is the condition number

###  4.3. Application to proximal gradient algorithm

Consider the following minimization problem

(4.4) $\min_{x\in\mathbb{R}^{n}}L(x)=f(x)+h(x),$

where $f:\mathbb{R}^{n}\to\mathbb{R}$ is $L$-Lipschitz smooth: $\|\nabla
f(x)-\nabla f(y)\|_{2}\leq L\|x-y\|_{2}$, and $h$ is a proper closed and
convex function. In many applications, such as data analysis and machine
learning, $f(x)$ is a convex data fidelity term, and $h(x)$ is a certain
regularization. For example, we take $h(x)=\frac{1}{2}\|x\|^{2}_{2}$ in
Section 5.2 and Section 5.3. A classical method for solving (4.4) is the
Proximal Gradient Algorithm (PGA):

(4.5a) $\displaystyle y_{k+1}$ $\displaystyle=x_{k}-\eta\nabla f(x_{k}),$
(4.5b) $\displaystyle x_{k+1}$ $\displaystyle=\text{Prox}_{\eta h}(y_{k+1}),$

where the proximal operator associated with $h$ is defined as

(4.6) $\text{Prox}_{\eta
h}(y)=\operatorname*{arg\\!\min}_{x}\Bigg{\\{}h(x)+\frac{1}{2\eta}\|x-y\|^{2}_{2}\Bigg{\\}}.$

To apply AA to PGA, [23] treats (4.5a) as the fixed-point iteration
$y_{k+1}=G(y_{k})$ with

(4.7) $G(y)=\text{Prox}_{\eta h}(y)-\eta\nabla f(\text{Prox}_{\eta h}(y)).$

Here AA is applied on the auxiliary sequence $\\{y_{k}\\}$, and the authors in
[23] show that fast convergence of $\\{y_{k}\\}$ will lead to fast convergence
of $\\{x_{k}\\}$.

We apply AA-AEGD to PGA to take advantage of both AA and energy adaptation on
step size. We summarize the resulting scheme in Algorithm 3. Following [23],
we add a step checking (Line 11) to ensure convergence. The numerical results
on the performance of Algorithm 3 are presented in Section 5.2 and Section
5.3.

Algorithm 3 AA- AEGD($m,q$) for solving problem (4.4).

1:$x_{0}$: initialization of the parameter; $y_{0}=x_{0}$; $c$: a constant
satisfies $f(x)+c>0$; $r_{0}=\sqrt{f(x_{0})+c}\bf{1}$: initialization of the
energy parameter; $\eta$: step size; $m$: length of the window; $\beta$:
relaxation parameter; $K$: total number of iterations.

2:for $k=0\dots,K-1$ do

3: $v_{k}=\nabla f(x_{k})/(2\sqrt{f(x_{k})+c})$

4: $r_{k+1}=r_{k}/(1+2\eta v_{k}^{2})$

5: $y_{k+1}=x_{k}-2\eta r_{k+1}v_{k}$

6: $x_{k+1}=\text{Prox}_{\eta h}(y_{k+1})$

7: $R_{k}=y_{k+1}-y_{k}$

8: if $k=0\;\text{mod}\;q$ and $k\neq 0$ then

9: Solve
$\min_{\alpha^{k}=(\alpha^{k}_{k-m},\dots,\alpha^{k}_{k})^{\top}}\|\sum_{j=k-m}^{k}\alpha_{j}^{k}R_{j}\|^{2}_{2}$
subject to $\sum_{j=k-m}^{k}\alpha_{j}^{k}=1$

10:
$y_{k+1}^{AA}=(1-\beta)\sum_{j=k-m}^{k}\alpha_{j}^{k}y_{j}+\beta\sum_{j=k-m}^{k}\alpha_{j}^{k}y_{j+1}$

11: $x_{k+1}^{AA}=\text{Prox}_{\eta h}(y_{k+1}^{AA})$

12: if $f(x_{k+1}^{AA})\leq f(x_{k})-\frac{\eta}{2}\|\nabla
f(x_{k})\|^{2}_{2}$ then

13: $x_{k+1}=x_{k+1}^{AA}$

14:return $x_{K}$

##  5\. Numerical Experiments

In this section, we demonstrate the performance of AA-AEGD on several
optimization problems, including the 2D Rosenbrock function and two machine
learning problems. For parameters, we set $c=1$ for AEGD and AA-AEGD,
$\beta=1$ and $q=m$ for AA-GD/AEGD($m,q$). All experiments are conducted in
Python and run on a laptop with four 2.4 GHz cores and 16 GB of RAM. 111The
code is available at https://github.com/howardjhe/AA-AEGD.git.

In Section 5.1, the effect of $\eta$ and $m$ on AA-GD/AEGD($m,q$) is studied
in the non-convex case. Then the performance of AA-AEGD (Algorithm 2) is
compared with GD, AEGD, and AA-GD. In Section 5.2 and Section 5.3, we further
implement AA-AEGD (Algorithm 3) to solve problems in the form of (4.4). We
employ the large-scale and ill-conditioned datasets, Madelon ($\kappa\approx
2.1\times 10^{4}$) and MARTI0 ($\kappa\approx 7.5\times 10^{3}$), obtained
from the UCI Machine Learning Repository222The Madelon dataset is available
from https://archive.ics.uci.edu/ml/datasets/ and ChaLearn Repository333The
MARTI0 dataset is available from http://www.causality.inf.ethz.ch/home.php,
respectively. As for the parameters used in the competitors, including PGA,
APGA, and AA-PGA, we keep all the same settings as in [23].

###  5.1. Non-convex function

Consider the following 2D Rosenbrock function

$f(x_{1},x_{2})=(1-x_{1})^{2}+100(x_{2}-x_{1}^{2})^{2}.$

This is a non-convex function with a global minimum $(1,1)$. As shown in
Figure 2 (c), the global minimum (marked as the black star) is inside a long,
narrow valley. It takes only several iterations to find the valley, while a
lot more iterations are needed to converge to the global minimum.

We first study the effect of $\eta$ and $m$ on AA-GD/AEGD($m,q$). Since the
feasible ranges of $\eta$ for GD and AEGD are different, we take different
intervals of $\eta$ for the two methods when studying the effect of $\eta$ on
AA-GD/AEGD($m,q$). The interval of $\eta$ for each method is determined as
follows: we first search for $\bar{\eta}$ with which the method reaches the
minimizer with the least iterations; then take
$[\bar{\eta}-\Delta\eta,\bar{\eta}+\Delta\eta]$ as the study interval of
$\eta$. In our experiment, we find $\bar{\eta}_{1}=1.9\times 10^{-4}$ for GD,
and $\bar{\eta}_{2}=6.4\times 10^{-3}$ for AEGD. For both methods, we set
$\Delta\eta=1.9$. The results are presented in Figure 2 (a) (b).

(a) The effect of $\eta$

(b) The effect of $m$

(c) The effect of frequency implementation

(d) The number of iterates

Figure 2. Comparison of AA-AEGD and AA-GD on the 2D Rosenbrock function. The
initial point is set at $(1.5,-0.5)$.

Figure 2 (c) presents a comparison of trajectories of AA-GD/AEGD($m,1$) and
AA-GD/AEGD($m,q$). We observe that compared with AA-GD/AEGD(3,3), the paths of
AA-GD/AEGD(3,1) detour far away from the minimizer. Also, AA-AEGD(3,3) reaches
the minimizer with the shortest path compared with others. A comparison of GD,
AEGD, and AA-GD, AA-AEGD is given in Figure 2 (d).

###  5.2. Constrained logistic regression problem

Consider the logistic regression problem with a bounded constraint:

$\displaystyle\min_{x\in\mathbb{R}^{n}}\frac{1}{M}\sum_{i=1}^{M}\log(1+\exp(-y_{i}a_{i}^{\top}x))+\mu\|x\|_{2}^{2},$
$\displaystyle\mbox{subject to}\ \|x\|_{\infty}\leq 1,$

where $a_{i}\in\mathbb{R}$ are sample data and $y_{i}\in\\{-1,1\\}$ are
corresponding labels to the samples. We set $\mu=10$ and apply
$\lambda=10^{-10}$ as the regularization parameter to (4.3). For this problem,
we set the initial point at $\bm{0}$, and keep the step size, $\eta=1/L_{1}$,
where $L_{1}=\|A\|_{2}^{2}/4M$ with $A=[a_{1},\cdots,a_{M}]$, for PGA, APGA,
and AA-PGA, and $m=5$ for AA-PGA as in [23]. We apply $\eta=2/L_{1}$ to AEGD
on both the Madelon and MARTI0 datasets. $\eta=3/L_{1}$ and $4/L_{1}$ are
adopted in AA-AEGD (Algorithm 3) on the Madelon and MARTI0 datasets,
respectively.

Figure 3 demonstrates the superior performance of AA-AEGD on the constrained
logistic regression problem compared with PGA, APGA, and AA-PGA.

(a) Madelon

(b) MARTI0

Figure 3. Constrained logistic regression problem

###  5.3. Nonnegative least squares

Consider the nonnegative least squares problem

$\displaystyle\min_{x\in\mathbb{R}^{n}}\frac{1}{2M}\|Ax-b\|^{2}_{2}+\mu\|x\|^{2}_{2}$
$\displaystyle\mbox{subject to}\ x\geq 0,$

where $A\in\mathbb{R}^{M\times n}$ is the sample data and $b\in\mathbb{R}^{M}$
are corresponding labels to the samples. We take $\mu=0.1$ and the initial
point as $\bf{0}$. In this problem, we keep the step size, $\eta=1/L_{2}$,
where $L_{2}=\|A\|_{2}^{2}/M$, for PGA, APGA, and AA-PGA, and $m=5$ for AA-PGA
as same in [23]. We apply $\eta=9/L_{2}$ to AEGD for both datasets.
$\eta=9/L_{1}$ and $3/L_{1}$ are employed with AA-AEGD on the Madelon and
MARTI0 datasets, respectively. Overall, AA-AEGD exhibits faster convergence
than AA-GD.

(a) Madelon

(b) MARTI0

Figure 4. Nonnegative least-squares problem

##  6\. Conclusion

In this paper, we developed a novel algorithm of using Anderson acceleration
for the adaptive energy gradient descent (AEGD) in solving optimization
problems. First, we analyzed the gain in convergence rate of AA-GD for
quadratic and non-quadratic optimization problems, and then we explained why
AA can still be exploited with AEGD though it is not a fixed-point iteration.
We deployed AA-AEGD for solving convex and non-convex problems and obtained
superior performance on a set of test problems. Moreover, we applied our
algorithm to the proximal gradient method on two machine learning problems and
observed improved convergence as well. Experiments show encouraging results of
our algorithm and confirm the suitability of Anderson acceleration for
accelerating AEGD in solving optimization problems. With the easy
implementation and excellent performance of AA-AEGD, it merits further study
with more refined convergence analysis.

##  Appendix A Proof of Theorem 3.1

Using $G(x)=x-\eta\nabla f(x)$ and $\nabla f(x)=Ax-b$, we have

$\displaystyle\nabla f(x_{k+1})$ $\displaystyle=Ax_{k+1}-b$
$\displaystyle=A\left(\sum\limits_{j=k-m}^{k}\alpha_{j}^{k}G(x_{j})\right)-b$
$\displaystyle=A\left(\sum\limits_{j=k-m}^{k}\alpha_{j}^{k}(x_{j}-\eta(Ax_{j}-b))\right)-b$
$\displaystyle=\sum\limits_{j=k-m}^{k}\alpha_{j}^{k}[Ax_{j}-\eta
A(Ax_{j}-b)-b]$ $\displaystyle=\sum\limits_{j=k-m}^{k}\alpha_{j}^{k}(I-\eta
A)(Ax_{j}-b)$ $\displaystyle=(I-\eta
A)\sum\limits_{j=k-m}^{k}\alpha_{j}^{k}\nabla f(x_{j}).$

Taking the $l^{2}$-norm on both sides, we get

(A.1) $\|\nabla f(x_{k+1})\|\leq\|I-\eta
A\|\left\|\sum\limits_{j=k-m}^{k}\alpha_{j}^{k}\nabla f(x_{j})\right\|.$

Thus by taking $\eta\leq\frac{2}{L+\mu}$, (A.1) with the Anderson selection of
$\alpha_{j}^{k}$ becomes

(A.2) $\|\nabla
f(x_{k+1})\|\leq(1-\eta\mu)\min_{\alpha^{k}}\left\|\sum\limits_{j=k-m}^{k}\alpha_{j}^{k}\nabla
f(x_{j})\right\|.$

Note that $\sum_{j=k-m}^{k}\alpha_{j}^{k}=1$ we have

(A.3) $\displaystyle\left\|\sum_{j=k-m}^{k}\alpha_{j}^{k}\nabla
f(x_{j})\right\|$ $\displaystyle=\left\|\nabla
f(x_{k})-\sum_{j=k-m}^{k-1}\alpha_{j}^{k}(\nabla f(x_{k})-\nabla
f(x_{j}))\right\|$ $\displaystyle=\left\|\nabla
f(x_{k})-U_{k}\alpha^{k}\right\|,\quad\alpha^{k}:=[\alpha_{k-m}^{k},\cdots,\alpha_{k-1}^{k}].$

By solving the regularized least square problem:

(A.4) $\min_{\alpha\in\mathbb{R}^{m}}\frac{1}{2}\left\|\nabla
f(x_{k})-U_{k}\alpha\right\|^{2}+\frac{\lambda}{2}\|\alpha\|^{2},$

we obtain an explicit expression for the optimal weight vector:

(A.5) $\alpha^{k}_{*}=(U_{k}^{\top}U_{k}+\lambda I)^{-1}U_{k}^{\top}\nabla
f(x_{k}),\quad\alpha^{k}_{k}=1-\alpha^{k}_{*}\cdot{\bf 1}.$

Hence

$\left\|\sum_{j=k-m}^{k}\alpha^{k}_{j}\nabla f(x_{j})\right\|=\|\Pi_{k}\nabla
f(x_{k})\|.$

We thus have

$\|\nabla f(x_{k+1})\|\leq(1-\eta\mu)\|\Pi_{k}\nabla
f(x_{k})\|\leq\delta_{k}(1-\eta\mu)\|\nabla f(x_{k})\|.$

This estimate can be further used to derive the bound on $\|x_{k+1}-x^{*}\|$.
Note that $\nabla f(x_{k+1})=Ax_{k+1}-b=A(x_{k+1}-x^{*}),$ we then have

$\displaystyle\|x_{k+1}-x^{*}\|$ $\displaystyle=\|A^{-1}(A(x_{k+1}-x^{*}))\|$
$\displaystyle\leq\|A^{-1}\|\|\nabla f(x_{k+1})\|$
$\displaystyle\leq\|A^{-1}\|C_{k}(1-\eta\mu)^{k+1}\|A(x_{0}-x^{*})\|$
$\displaystyle\leq C_{k}(1-\eta\mu)^{k+1}\|A\|\|A^{-1}\|\|(x_{0}-x^{*})\|,$

where $\|A\|\|A^{-1}\|$ is the condition number, and
$C_{k}=\prod_{j=0}^{k}\delta_{j}$. Thus, we have

$\|x_{k+1}-x^{*}\|\leq
C_{k}(1-\eta\mu)^{k+1}\left(\frac{L}{\mu}\right)\|(x_{0}-x^{*})\|.$

The proof is complete.

##  Appendix B Proof of Theorem 3.2

Denote $g(\cdot)=\nabla f(\cdot)$ and $g_{k}=\nabla f(x_{k})$, the update of
AA-GD is given by

$x_{k+1}=\sum_{j=k-m}^{k}\alpha^{k}_{j}(x_{j}-\eta g_{j}).$

Set $y_{k}:=\sum_{j=k-m}^{k}\alpha^{k}_{j}x_{j}$, we make the following split:

(B.1) $\eta g_{k+1}=a_{k}+b_{k},$

where

$\displaystyle a_{k}$ $\displaystyle=\eta g_{k+1}-x_{k+1}-(\eta
g(y_{k})-y_{k}),$ $\displaystyle b_{k}$ $\displaystyle=x_{k+1}+(\eta
g(y_{k})-y_{k}).$

We proceed to bound the $l^{2}$-norm of $a_{k}$ and $b_{k}$. First we have

(B.2) $\displaystyle\|a_{k}\|$
$\displaystyle=\|\eta(g_{k+1}-g(y_{k}))-(x_{k+1}-y_{k})\|$
$\displaystyle=\|(\eta D^{2}f(\cdot)-I)(x_{k+1}-y_{k})\|\quad\mbox{where}\
D^{2}f(\cdot)=\int_{0}^{1}D^{2}f(tx_{k+1}+(1-t)y_{k})dt$
$\displaystyle\leq\|\eta D^{2}f(\cdot)-I\|\|x_{k+1}-y_{k}\|$
$\displaystyle=\eta\|\eta
D^{2}f(\cdot)-I\|\left\|\sum_{j=k-m}^{k}\alpha^{k}_{j}(-\eta g_{j})\right\|$
$\displaystyle=\eta\|\eta
D^{2}f(\cdot)-I\|\delta_{k}\|g_{k}\|\quad\mbox{where}\
\delta_{k}:=\frac{\|\Pi_{k}g_{k}\|}{\|g_{k}\|}$
$\displaystyle\leq\eta(1-\eta\mu)\delta_{k}\|g_{k}\|.$

The last inequality is guaranteed by setting $\eta\leq\frac{2}{\mu+L}$. Recall
that $\alpha^{k}$ is chosen by minimizing (A.3), which ensures
$\delta_{k}=\|\Pi_{k}g_{k}\|/\|g_{k}\|\leq 1$.

Using $\alpha^{k}$ defined in (A.5), we now bound $b_{k}$ as follows.

$\begin{split}b_{k}&=\sum_{j=k-m}^{k}\alpha^{k}_{j}(x_{j}-\eta
g_{j})-y_{k}+\eta g(y_{k})\\\
&=x_{k}-y_{k}-\eta(g_{k}-g(y_{k}))+\sum_{j=k-m}^{k-1}\alpha^{k}_{j}((x_{j}-\eta
g_{j})-(x_{k}-\eta g_{k}))\\\ &=(I-\eta
D^{2}f(\ast\ast))(x_{k}-y_{k})+\sum_{j=k-m}^{k-1}\alpha^{k}_{j}(I-\eta
D^{2}f(\ast_{j}))(x_{j}-x_{k}),\end{split}$

where we define

(B.3) $\displaystyle
D^{2}f(\ast_{j})=\int_{0}^{1}D^{2}f(tx_{k-j}+(1-t)x_{k})dt,$ $\displaystyle
D^{2}f(\ast\ast)=\int_{0}^{1}D^{2}f(tx_{k}+(1-t)y_{k})dt.$

Note that

$x_{k}-y_{k}=x_{k}-\alpha^{k}_{k}x_{k}-\sum_{j=k-m}^{k-1}\alpha^{k}_{j}x_{j}=\sum_{j=k-m}^{k-1}\alpha^{k}_{j}(x_{k}-x_{j}).$

Hence $b_{k}$ can be further written as

(B.4) $\begin{split}b_{k}&=\sum_{j=k-m}^{k-1}\alpha^{k}_{j}(I-\eta
D^{2}f(\ast\ast))(x_{k}-x_{j})+\sum_{j=k-m}^{k-1}\alpha^{k}_{j}(\eta
D^{2}f(\ast_{j})-I)(x_{k}-x_{j})\\\
&=\eta\sum_{j=k-m}^{k-1}\alpha^{k}_{j}(D^{2}f(\ast_{j})-D^{2}f(\ast\ast))(x_{k}-x_{j}).\end{split}$

Note that $b_{k}$ would vanish if $f$ were a quadratic function. By mean value
theorem, there exists $\omega\in C[0,\infty)$ and is increasing with
$\omega(0)=0$ such that

$\displaystyle\|D^{2}f(*_{j})-D^{2}f(**)\|$
$\displaystyle\leq\omega(\|*_{j}-**\|)\to 0\quad\text{as}\quad k\to\infty,$

since $x_{k},y_{k}\to x^{*}$ as $k\to\infty$ implies
$*_{j}=t_{1}x_{k-j}+(1-t_{1})x_{k}\to x^{*}$ and
$**=t_{2}x_{k}+(1-t_{2})y_{k}\to x^{*}$ for some $t_{1},t_{2}\in[0,1]$. Denote
$o(k)=\max_{k-m\leq j\leq k-1}\|D^{2}f(*_{j})-D^{2}f(**)\|$, and assume
$x_{j}\in B(x^{*},\epsilon)$ with $\epsilon<1$ for $j=k-m,\cdots k$, (B.4)
leads to

(B.5) $\begin{split}\|b_{k}\|&\leq
o(k)\eta\left\|\sum_{j=k-m}^{k-1}\alpha^{k}_{j}(x_{k}-x_{j})\right\|\\\ &\leq
o(k)\eta\left(\sum_{j=k-m}^{k-1}(\alpha^{k}_{j})^{2}\right)^{1/2}\left(\sum_{j=k-m}^{k-1}\|x_{k}-x_{j}\|^{2}\right)^{1/2}\\\
&\leq o(k)\eta\|\alpha^{k}_{*}\|\sqrt{2m}\\\ &\leq
o(k)\eta\sqrt{2m}\|(U_{k}^{\top}U_{k}+\lambda
I)^{-1}U_{k}^{\top}\|\|g_{k}\|,\end{split}$

where (A.5) is used in the last inequality. With this bound and (B.2), (B.1)
becomes

$\begin{split}\eta\|g_{k+1}\|&\leq\|a_{k}\|+\|b_{k}\|,\\\
&\leq\eta(1-\eta\mu)\delta_{k}\|g_{k}\|+o(k)\eta c\|g_{k}\|.\end{split}$

with $c\geq\sqrt{2m}\|(U_{k}^{\top}U_{k}+\lambda I)^{-1}U_{k}^{\top}\|$. Hence

$\|g_{k+1}\|\leq(1-\eta\mu)\delta_{k}\|g_{k}\|+o(k)c\|g_{k}\|\\\
=\left((1-\eta\mu)\delta_{k}+o(k)c\right)\|g_{k}\|,$

which implies

(B.6)
$\frac{\|g_{k+1}\|}{\|g_{k}\|}\leq(1-\eta\mu)\delta_{k}+co(k)=(1-\eta\mu)\delta_{k}+o(k),$

where

$\delta_{k}=\frac{\|\Pi_{k}g_{k}\|}{\|g_{k}\|}\leq 1.$

## Acknowledgments

This research was partially supported by the National Science Foundation under
Grant DMS1812666.

## References

  * [1] Alex Toth and Carl T. Kelley, _Convergence analysis for Anderson acceleration_ , SIAM Journal on Numerical Analysis 53 (2015), no. 2, 805–819.
  * [2] Donald G. Anderson, _Iterative procedures for nonlinear integral equations_ , Journal of the ACM (JACM) 12 (1965), no. 4, 547–560.
  * [3] Quentin Bertrand and Mathurin Massias, _Anderson acceleration of coordinate descent_ , International Conference on Artificial Intelligence and Statistics, PMLR, 2021, pp. 1288–1296.
  * [4] Wei Bian, Xiaojun Chen, and Carl T. Kelley, _Andersion acceleration for a class of nonsmooth fixed-point problems_ , SIAM Journal on Scientific Computing 43 (2021), no. 5, S1–S20.
  * [5] Raghu Bollapragada, Damien Scieur, and Alexandre d’Aspremont, _Nonlinear acceleration of momentum and primal-dual algorithms_ , Mathematical Programming (2022), 1–38.
  * [6] Boris T. Polyak, _Some methods of speeding up the convergence of iteration methods_ , USSR computational mathematics and mathematical physics 4 (1964), no. 5, 1–17.
  * [7] Jakub Wiktor Both, Kundan Kumar, Jan Martin Nordbotten, and Florin Adrian Radu, _Anderson accelerated fixed-stress splitting schemes for consolidation of unsaturated porous media_ , Computers & Mathematics with Applications 77 (2019), no. 6, 1479–1502.
  * [8] Xiaojun Chen and Carl T. Kelley, _Convergence of the EDIIS algorithm for nonlinear equations_ , SIAM Journal on Scientific Computing 41 (2019), no. 1, A365–A379.
  * [9] R.P. Eddy, _Extrapolating to the limit of a vector sequence_ , Information linkage between applied mathematics and industry, Elsevier, 1979, pp. 387–396.
  * [10] Claire Evans, Sara Pollock, Leo G Rebholz, and Mengying Xiao, _A proof that Anderson acceleration improves the convergence rate in linearly converging fixed-point methods (but not in those converging quadratically)_ , SIAM Journal on Numerical Analysis 58 (2020), no. 1, 788–810.
  * [11] Volker Eyert, _A comparative study on methods for convergence acceleration of iterative vector sequences_ , Journal of Computational Physics 124 (1996), no. 2, 271–285.
  * [12] Haw-ren Fang and Yousef Saad, _Two classes of multisecant methods for nonlinear acceleration_ , Numerical linear algebra with applications 16 (2009), no. 3, 197–221.
  * [13] Anqi Fu, Junzi Zhang, and Stephen Boyd, _Anderson accelerated Douglas–Rachford splitting_ , SIAM Journal on Scientific Computing 42 (2020), no. 6, A3560–A3583.
  * [14] Matthieu Geist and Bruno Scherrer, _Anderson acceleration for reinforcement learning_ , arXiv preprint arXiv:1809.09501 (2018).
  * [15] Pelin G. Geredeli, Leo G. Rebholz, Duygu Vargun, and Ahmed Zytoon, _Improved convergence of the Arrow-Hurwicz iteration for the Navier–Stokes equation via grad-div stabilization and Anderson acceleration_ , Journal of Computational and Applied Mathematics (2022), 114920\.
  * [16] Zhize Li and Jian Li, _A fast Anderson-Chebyshev acceleration for nonlinear optimization_ , International Conference on Artificial Intelligence and Statistics, PMLR, 2020, pp. 1047–1057.
  * [17] Hailiang Liu and Xuping Tian, _AEGD: Adaptive gradient descent with energy_ , arXiv preprint arXiv:2010.05109 (2020).
  * [18] by same author, _An adaptive gradient method with energy and momentum_ , Ann. Appl. Math 38 (2022), no. 2, 183–222.
  * [19] by same author, _Dynamic behavior for a gradient algorithm with energy and momentum_ , arXiv preprint arXiv:2203.12199 (2022), 1–20.
  * [20] by same author, _SGEM: stochastic gradient with energy and momentum_ , arXiv preprint arXiv:2208.02208 (2022), 1–24.
  * [21] P.A. Lott, H.F. Walker, C.S. Woodward, and U.M. Yang, _An accelerated Picard method for nonlinear systems related to variably saturated flow_ , Advances in Water Resources 38 (2012), 92–101.
  * [22] S. Luo and Q.H. Liu, _A fixed-point iteration method for high frequency helmholtz equations_ , J Sci. Comput. 93 (2022), 74.
  * [23] Vien Mai and Mikael Johansson, _Anderson acceleration of proximal gradient methods_ , International Conference on Machine Learning (2020), 6620–6629.
  * [24] Yu E. Nesterov, _A method for solving the convex programming problem with convergence rate $o(1/k^{2})$_, 269 (1983), 543–547.
  * [25] Cornelis W Oosterlee and Takumi Washio, _Krylov subspace acceleration of nonlinear multigrid with application to recirculating flows_ , SIAM Journal on Scientific Computing 21 (2000), no. 5, 1670–1690.
  * [26] M. L. Pasini, J. Yin, V. Reshniak, and M. Stoyanov, _Stable Anderson acceleration for deep learning_ , arXiv preprint (2021), arXiv:2110.14813.
  * [27] Clarice Poon and Jingwei Liang, _Trajectory of alternating direction method of multipliers and adaptive acceleration_ , Advances in Neural Information Processing Systems 32 (2019).
  * [28] Florian A. Potra and Hans Engler, _A characterization of the behavior of the Anderson acceleration on linear problems_ , linear Algebra and its Applications 438 (2013), no. 3, 1002–1011.
  * [29] Péter Pulay, _Convergence acceleration of iterative sequences. the case of SCF iteration_ , Chemical Physics Letters. 73 (1980), no. 2, 393–398.
  * [30] Thorsten Rohwedder and Reinhold Schneider, _An analysis for the DIIS acceleration method used in quantum chemistry calculations_ , Journal of mathematical chemistry 49 (2011), no. 9, 1889–1914.
  * [31] Damien Scieur, Francis Bach, and Alexandre d’Aspremont, _Nonlinear acceleration of stochastic algorithms_ , Advances in Neural Information Processing Systems 30 (2017).
  * [32] Damien Scieur, Alexandre d’Aspremont, and Francis Bach, _Regularized nonlinear acceleration_ , Advances In Neural Information Processing Systems 29 (2016).
  * [33] David A Smith, William F Ford, and Avram Sidi, _Extrapolation methods for vector sequences_ , SIAM review 29 (1987), no. 2, 199–233.
  * [34] Hans De Sterck and Yunhui He, _On the asymptotic linear convergence speed of Andersion acceleration, Nesterov acceleration, and nonlinear GMRES._ , SIAM Journal on Scientific Computing 43 (2021), no. 5, S21–S46.
  * [35] Weijie Su, Stephen Boyd, and Emmanuel Candes, _A differential equation for modeling Nesterov’s accelerated gradient method: theory and insights_ , Advances in neural information processing systems 27 (2014).
  * [36] Alex Toth, J. Austin Ellis, Tom Evans, Steven Hamilton, Carl T. Kelley, Roger Pawlowski, and Stuart Slattery, _Local improvement results for Andersion acceleration with inaccurate function evaluations_ , SIAM Journal on Scientific Computing 39 (2017), no. 5, S47–S65.
  * [37] Homer F. Walker and Peng Ni, _Anderson acceleration for fixed-point iterations_ , SIAM Journal on Numerical Analysis 49 (2011), no. 4, 1715–1735.
  * [38] D. Wang, Y He, and H. De Sterck, _On the asymptotic linear convergence speed of Anderson acceleration applied to ADMM_ , Journal of Scientific Computing 88 (2021), no. 2, 38.
  * [39] Yunan Yang, _Anderson acceleration for seismic inversion_ , Geophysics 86 (2021), no. 1, R99–R108.
  * [40] Junzi Zhang, Brendan O’Donoghue, and Stephen Boyd, _Globally convergent type-I Anderson acceleration for nonsmooth fixed-point iterations_ , SIAM Journal on Optimization 30 (2020), no. 4, 3170–3197.