Stylized Dialogue Response Generation Using Stylized Unpaired Texts

Generating stylized responses is essential to build intelligent and engaging dialogue systems. However, this task is far from well-explored due to the difficulties of rendering a particular style in coherent responses, especially when the target style is embedded only in unpaired texts that cannot be directly used to train the dialogue model. This paper proposes a stylized dialogue generation method that can capture stylistic features embedded in unpaired texts. Specifically, our method can produce dialogue responses that are both coherent to the given context and conform to the target style. In this study, an inverse dialogue model is first introduced to predict possible posts for the input responses, and then this inverse model is used to generate stylized pseudo dialogue pairs based on these stylized unpaired texts. Further, these pseudo pairs are employed to train the stylized dialogue model with a joint training process, and a style routing approach is proposed to intensify stylistic features in the decoder. Automatic and manual evaluations on two datasets demonstrate that our method outperforms competitive baselines in producing coherent and style-intensive dialogue responses.

Introduction
Building a conversational agent that can produce stylized and coherent responses has been one of the major challenges in dialogue systems . Such an agent can not only yield more vivacious dialogues but also deliver more engaging conversations by taking advantage of the linguistic style matching phenomenon (Niederhoffer and Pennebaker, 2002), which suggests that people tend to adjust their linguistic style during communication to pursue higher engagement. * Corresponding Author: aihuang@tsinghua.edu.cn The pleasure is all mine, my lady.√ The pleasure is all mine, sir.  Figure 1: A pipelined approach to produce formal dialogue responses. For a post x, a response y is first produced using a dialogue model and then it is transferred to a formal response y using a text style transfer model.
Generating stylized dialogue responses has been investigated in various studies, where the definition of styles covers a variety of subtle concepts, such as sentiment (Shen et al., 2017b), emotion , or persona (Li et al., 2016b). Despite the success, previous studies are generally conducted in a fully supervised setting that requires to use dialogue pairs in the target style. However, in most cases, the stylistic features we want to capture are embedded in unpaired texts that can not be directly utilized by these supervised models .
Few studies for dialogue modeling have been proposed to capture the stylistic features embedded in unpaired texts. Specifically, Niu and Bansal (2018) employs a style-aware reinforce loss, and  resorts to a joint continuous latent space. However, despite the reported feasibility, we argue that due to the discrete nature of texts and subtle definition of text styles, it is hard to produce coherent and style-specific responses by relying on sparse reinforce signals or controlling continuous representations.
Note that we can also implement a straightforward stylized dialogue generation pipeline with the help of an unsupervised text style transfer model (Hu et al., 2017), which can be trained using stylized unpaired texts. Specifically, for a post x, a non-stylized dialogue response y is first generated using a regular dialogue model, and then y is transferred to a stylized response y using a text style transfer model. However, this approach may hurt the coherence between x and y since the style transferring process is unaware of x and thus may introduce improper contents. As shown in Figure 1, the style transfer model generates a strong stylistic word "sir" to emphasize the formality of y. However, this makes y incoherent with x since x is most likely to be issued by a female.
In this paper, we propose to build a stylized dialogue generation model that can capture stylistic features embedded in a set of unpaired texts D s . Specifically, in order to tackle the problem of lacking stylized dialogue pairs, an inverse dialogue model is built to predict posts based on the responses, and a set of stylized pseudo dialogue pairs are constructed by producing pseudo posts for texts in D s . Then a stylized dialogue model is trained using these pseudo pairs, and a joint training process is introduced to enhance the coherency between the post and the resulting responses. Moreover, our dialogue models are parameterized using the Transformer-based encoderdecoder framework, and initialized with the pretrained GPT weights (Radford et al., 2018). A style routing approach is devised to fuse a style embedding in each decoder block of the stylized dialogue model to intensify the stylistic features in the decoding process.
We evaluate our method on two datasets with two distinct writing styles: 1) Jinyong novels 1 in Chinese, and 2) formality in English writing. Automatic and human evaluations show that our method significantly outperforms competitive baselines with a large margin in generating coherent dialogue responses while rendering stronger stylistic features.
Our contributions can be summarized as: 1) A novel method is proposed to build a stylized dialogue model that can capture stylistic features embedded in unpaired texts. Specifically, an inverse dialogue model is introduced to generate stylized pseudo dialogue pairs, which are further utilized in a joint training process. An effective style routing approach is devised to further intensify the stylistic features in the decoder. 1 Jinyong is a famous Chinese writer who wrote many Kung Fu novels.
2) Automatic and human evaluations on two datasets show that our method outperforms competitive baselines with a large margin in producing stylized and coherent dialogue responses.

Related Work
Stylized dialogue generation has attracted numerous attentions in recent years Niu and Bansal, 2018). With a rather wide definition of styles, various studies that focus on controllable dialogue generation have been categorized as "stylized" dialogue generation, such as generating personalized (Li et al., 2016b) or emotional  dialogues. However, the training process of these dialogue model usually require dialogue pairs in the target style, whereas our study aims to capture stylistic features embedded in unpaired texts.
Moreover, the styles defined in most previous studies are deeply fused with the text contents (Tikhonov et al., 2019). Enforcing these styles may limit the expressive ability of the dialogue model because there are contradictions between certain semantic contents and style categories. For example, it is hard, if not impossible, for a service agent to yield comforting contents when enforcing a negative sentiment. Unlike most previous works, our study investigates to model the writing styles that are "orthogonal" to the text semantic, so that the contents we want to deliver will not be constrained by the style we intend to render.
Text style transfer is a related but different task compared to our work. Specifically, these text style transfer models aim to preserve the style-agnostic contents of the input text (Fu et al., 2018). In contrast, our study aims to produce coherent responses rather than to preserve the contents of the posts. Early works on this task focus to disentangle the representation of styles and contents (Hu et al., 2017;Shen et al., 2017a;Prabhumoye et al., 2018). However, recent studies argue the effectiveness of such disentanglement (Lample et al., 2019), and propose to revise the latent codes using classifiers (Liu et al., 2020;Wang et al., 2019). Some works are also proposed to render the target styles by replacing stylistic words (Wu et al., 2019a,b).
We have also noticed a recent work that considers a contextual constraint in the text style transferring process (Cheng et al., 2020). However, although being feasible, the training of this model requires style-labelled parallel data. This hinders us from directly employing this model in our study since these parallel data are usually unavailable. Back translation is a popular approach that has been widely employed in various NLP tasks such as machine translation (Sennrich et al., 2016), dialogue data augmentation (Su et al., 2020), and text style transfer Lample et al., 2019;Dai et al., 2019). This approach is similar to the inverse dialogue model introduced in our study. However, different from previous approaches that focus on modeling the one-to-one mapping between the source and target languages, our inverse dialogue model tries to capture the oneto-many mappings between the responses and posts with the help the proposed joint training process. In our study, the diversity of the generated pseudo posts are enhanced using a sampling approach.

Task Definition
In this study, we propose to build a stylized dialogue model without utilizing dialogue pairs in the target style. Specifically, our method takes as input two sets of data in the training stage: 1) M unpaired texts D s = {t 1 , ..., t M } in the writing style S 1 ; 2) N dialogue pairs D p = { x 1 , y 1 , ..., x N , y N } with style S 0 , where x i and y i is the post and response, respectively. Our stylized dialogue model aims to generate a response y that is coherent to a given post x while exhibiting a certain style S i (i = 0, 1): (1)

Model Overview
Our model consists of two mirrored sub-modules ( Figure 2): (1). A stylized dialogue module (i.e., e and d in Figure 2) that can produce a stylized response y based on a given post x and a style label S i (i = 0, 1). A style routing approach is devised  (2). An inverse dialogue module (i.e.,ê andd in Figure 2) that aims to produce pseudo posts x based on an input response y. Note that the inverse dialogue model is introduced to tackle the problem of lacking dialogue pairs in style S 1 , i.e., we can regard the texts in D s as possible dialogue responses and use the predicted pseudo posts to construct pseudo dialogue pairs in style S 1 . Therefore, we omit the style label in the inverse decoderd to encourage it to focus more on the semantic aspect of the dialogue.
The dialogue modules in our study are parameterized using the Transformer-based encoder and decoder architecture (Vaswani et al., 2017) and are initialized using pretrained GPT (Radford et al., 2019) weights. Further, we also follow previous works (Golovanov et al., 2019) to share the weights of the encoder and decoder from the same submodule to save memories. Particularly, the weights of e and d are shared, and the weights ofê andd are shared.
Moreover, to better capture the one-to-many phenomenon and alleviate the problem of producing trivial posts in the inverse dialogue model, a top-k sampling scheme is employed to sample multiple pseudo posts for each stylized text in D s , and all these posts are utilized in the training process. Further, a joint training process is also introduced to train these two sub-modules in an iterative fashion to enhance the coherency of the response.

Style Routing
There exist various approaches to condition the decoder d on the style label. For example, employing a special style token as the start token (Lample et al., 2019), or adding a style embedding to each word embedding . However, these approaches only incorporate the style representation in the input layer of the decoder, whereas the higher layers are not affected.
In this study, a style routing approach is devised to enhance existing approaches to stylize d in the stylized dialogue model (see Figure 3). Specifically, in each decoder block, we first fuse the representation of the post x and previously decoded token sequence y p using the attention routing mechanism , i.e., two sequences of representations, R prev , R post ∈ R l×h , are first calculated: where e w (y p ) ∈ R l×h denotes the embedding of y p and it is used as the query in MMHA and MHA, which represent the masked and un-masked multi-head attention operation, respectively. l is the length of y p , and h is the hidden size. e w (x) is the output of the encoder. A sequence of fused representations R avg is obtained as: Then for a given style S i , a style embedding e s (S i ) ∈ R 1×h is allocated and e s (S i ) is routed into R avg by adding it to each time step of the sequence: Also note that the fusion operation in Eq. 4 and 5 is similar to some previous studies that try to incorporate additional contexts in a transformerbased decoder (Golovanov et al., 2019). However, different from these approaches that focus to model sequential contexts, the styles modeled in our study are categorical, and more priority is allocated to the style representation in our model. Moreover, we are the first to use such style routing approach in the stylized dialogue generation task.

Joint Training
The training of our model involves the following losses: 1) standard maximum log likelihood losses Algorithm 1 Joint training process Step > N f then 7: Dpp ← empty set. 8: Sample ns stylized texts D b s = {ti} ns i=1 ⊂ Ds 9: for each ti ∈ D b s do 10: Decode m posts {x ij } m j=1 from pd(x|ê(ti)) 11: The loss L p2r and L r2p is used to train the stylized dialogue model and inverse dialogue model, respectively; 2) an inverse dialogue loss evaluated on texts from D s : in which x is the pseudo post sampled from the inverse dialogue model.
Note that the gradient back-propagation through the loss L inv is intractable due to the indifferentiable sampling process in Eq. 8. In this study, we approximate the ideal back-propagation process through L inv by truncating the gradients associated with the sampling operation. Specifically, when optimizing L inv , the parameters of the inverse dialogue model are fixed, and the stylized dialogue model is trained with pseudo posts x that are sampled from the inverse dialogue model. Similar approaches have been proven to be effective in other NLP tasks (Lample et al., 2018;He et al., 2020). However, unlike previous works that use the greedy decoding scheme, our study employs the top-k sampling scheme with beam search to produce x since the mapping between dialogue responses and posts is not unique. The greedy decoding scheme may limit the diversity of the decoded pseudo posts and lead to sub-optimal performance.  To facilitate the learning with the above gradient approximation approach, a joint training process is introduced to train the model literately. Specifically, in each training iteration, we first update the stylized and inverse dialogue model by optimizing the losses L p2r and L r2p using a batch of dialogue pairs sampled in D p . Further, a batch of stylized sentences D b s are sampled from D s . For each sentence t i ∈ D b s , m pseudo posts x i1 , ..., x im are sampled from the inverse dialogue model, and m pseudo dialogue pairs x ij , t i , (j = 1, ..., m) in the style S 1 are constructed. These pseudo pairs are used to train the stylized dialogue model with the loss L inv . Moreover, to avoid corrupted pseudo posts at the beginning of the training process, we pre-train the inverse dialogue model on L r2p for N f steps before using it to decode pseudo posts. The detailed training process is summarized in Algorithm 1.

Dataset
Our method is evaluated on two datasets with two distinct styles (see statistics in Table 1).
1) WDJN: We collect 300K Weibo Dialogues (style S 0 ) as D p and sampled 95.1K stylized texts from Jinyong's Novels (style S 1 ) as D s . Moreover, we also extracted 2K dialogue pairs from Jinyong's novels with hand-designed rules. These dialogues are used as the test set D t together with 2K additional Weibo dialogues. Note that all the Weibo dialogues in our WDJN dataset (both training and testing) are manually inspected and filtered by annotators.
Also note that to prevent the model from copying stylistic phrases in the post when producing Jinyong style responses in the testing phase, we erase the stylistic features related to Jinyong's writing from the posts in these 2K Jinyong style dialogues in D t using the back translation approach . Moreover, all the resulting posts are manually checked and revised to ensure the stylis-tic features related to style S 1 are erased. More details about the WDJN dataset can be find the Appendix A. The WDJN dataset will be released for public use.
2) TCFC (Wu et al., 2020): This dataset focuses on the formality in English writing. We sampled 217.2K informal dialogue pairs (style S 0 ) as D p and 500.0K formal texts (style S 1 ) as D s from the original dataset, and used the test data in the original dataset as our test set D t , which contains 1,956 manually-crafted dialogue pairs (978 informal pairs and 978 formal pairs).

Implementation Details
For experiments on the WDJN and TCFC dataset, we used the pre-trained CDial-GPT  and DialoGPT (size 345M)  model to initialize the dialogue modules, respectively. The top-K sampling process in Algorithm 1 employs a K = 20 and beam size of 4 (WDJN) or 2 (TCFC). The value of N f is set to 300. The training of our model stops after 10 iteration epochs on D p (WDJN) or after 8,000 steps of updates (TCFC). See Appendix B for more details of the reproduction guidance.

Baselines
We choose two groups of baselines: The first group contains dialogue models with different style modeling scheme: 1) S2S (Golovanov et al., 2019): a strong Transformer-based dialogue model that is only trained on D p . This baseline can only produce responses in style S 0 ; 2) SLM: the "Fusion" model proposed by Niu and Bansal (2018), in which an independent stylized language model is trained on D s , and the distributions decoded from the S2S baseline and the stylized LM are fused when producing responses in style S 1 ; 3) SRL: the "RL" model proposed by Niu and Bansal (2018), in which a reinforce signal produced by a style classifier is used to enforce the style S 1 ; 4) SFusion : A fused latent space is built using a multi-task training scheme. Specifically, for each post, six responses are sampled, and two classifiers are used to rank these responses for the styles.
The second group of baselines are built using the pipelined approach, i.e., different unsupervised text style transfer models are trained on texts from D s and D p , and responses produced by the S2S baseline (in style S 0 ) are transferred to exhibit the target   Table 3: Automatic and manual evaluation results for responses with style S 0 . All differences between our model and baselines are significant with p-value <0.01 except for the ones marked with *.
style S 1 using these models: 5) S2S+BT: a backtranslation-based text style transfer model (He et al., 2020); 6) S2S+CT: a model that tries to entangle the latent code for styles and contents (Wang et al., 2019); 7) S2S+PTO: a model that renders the target style by replacing stylistic words (Wu et al., 2019a). Note that for baselines SLM, SRL and all the baselines in the second group, the responses generated by the S2S baseline are used as their responses for the S 0 style since they can only produce responses in S 1 once trained. Moreover, for fair comparisons, we implemented baselines 1-3 using the same architecture and hyper-parameters as in our model. For baselines 4-7, we used the official codes released by the authors. Note that it is non-trivial to utilize the pre-trained GPT model in the baseline SFusion since it handles fixed-length latent codes.

Automatic Evaluation
Metrics: We first used automatic metrics to evaluate the response quality of our model: 1). BLEU (Papineni et al., 2002) was used to measure n-gram (n=1, 2) overlap between the generated responses and the reference responses; 2). Distinct (Dist.) (Li et al., 2016a) measures the proportion of unique n-grams in the generated responses (n=2).
To evaluate the style intensity of the each model, we first trained two text style classifiers (i.e., BERT (Devlin et al., 2019) and SVM) and then calculated the style intensity score as the portion of generated responses that conform to the target style based on these classifiers. In our study, the texts from D p and D s were used to train the classifiers for the WDJN experiments, and the formal/informal texts from the GYAFC dataset (Rao and Tetreault, 2018) were used to train the classifiers for the TCFC experiments. The accuracy of the BERT and SVM classifier on the holdout test set was 98.52% and 94.20% respectively for the WDJN experiments, and 93.98% and 89.57% respectively for the TCFC experiments (see Appendix C for more details).   Table 4: Automatic and manual evaluation results of ablation models for responses with style S 0 and S 1 . All differences between our model and ablation models are significant with p-value <0.05 except for the ones marked with *.

Results
in style S 1 (Table 2) and S 0 ( Table 3). Note that the baseline S2S is not included in Table 2 since it can not produce responses in style S 1 . Similarly, only the baselines S2S and SFusion are contained in Table 3. Significance tests are performed between the results of our model and all the baselines using the t-test with bootstrap resampling (Koehn, 2004). As can be seen from the automatic results, our method outperforms all the baselines with large margins when generating dialogue responses in style S 1 (Table 2), and achieves competitive performance when producing responses in style S 0 (Table 3). This indicates that our model can produce high quality responses that are both coherent to the given context and consistent to the target style. We can further observe that: 1). The pipelined approaches achieve lower BLEU scores comparing to our method. This verifies our claim that the response coherency is affected by the style transferring process. Similar results are also observed in manual evaluation. 2). The high diversity (i.e., Dist. scores) of the baselines on the TCFC dataset come along with a dramatic decrease on the BLEU scores. This is because that these baselines overfit to the diverse colloquial phrases in the informal responses, and fail to render responses in style S 1 , which are more formal and less diverse.
Also note that the style intensity scores for human generated responses (last row in Table 2 and 3) do not match the accuracy of our style classifiers. This is because that the train data of these classifiers involve non-conversational texts, which leads to mismatches when testing using conversational responses. To alleviate this mismatch, we performed manual evaluations to concrete our analysis.

Manual Evaluation
Metrics: For a given post, dialogue responses with different styles were generated using our model and all the baselines. Three annotators were re-cruited from the crowd-sourcing platform to evaluate these responses from three aspects: 1) Fluency (Flu.): whether the response is fluent and free from grammar errors; 2) Coherency (Coh.): whether the response is coherent with the dialogue context; 3) Style Intensity (Style): whether the response conforms to the given style. Each metric is rated among {0, 1, 2}, in which 0 means worst and 2 best. Moreover, the Harmonic Average (i.e, HAvg.) of above measures is also reported.
Results: We sampled 300 posts from D t for each of these two datasets. Fleiss's kappa κ (Randolph, 2005) was used to measure the annotation agreement between annotators. Specifically, for Flu., Coh., and Style, the κ value was 0.69, 0.50, 0.86, respectively on the WDJN dataset (indicating substantial, moderate, and substantial agreement), and 0.44, 0.31, 0.42, respectively on the TCFC dataset (indicating moderate, fair, and moderate agreement).
As shown in Table 2, our model surpasses all the baselines significantly on style intensity (except for S2S+CT on the WDJN dataset, which comes with dramatic decreases on the fluency and coherency scores) when producing responses in style S 1 , and it achieves competitive or higher fluency and coherency scores. This verifies the superiority of our method in producing coherent and style intensified dialogue responses. Moreover, results in table 3 also shows that our model achieved competitive performance when generating responses in style S 0 .
Another interesting observation from the results in Table 2 and 3 is the trade-off between the coherency and style intensity when generating stylized dialogue responses, i.e., the high style intensity usually comes at the cost of a low coherency. For example, the model S2S+CT achieves the best style intensity score on the WDJN dataset (1.50) when producing responses in style S 1 , but it obtains the  worst coherency (0.19) score. This phenomenon is also observed in various previous studies (Niu and Bansal, 2018;. Nevertheless, our model achieves a competitive coherency while producing style-intensive responses. Also note that the baselines SFusion, SRL, and S2S+CT generally yield low HAvg. scores on both datasets. This verifies our claim that it is hard to generate stylized and coherent responses relying on the sparse reinforce signals (i.e., SRL) or continuous latent codes (i.e., SFusion and S2S+CT).
The superiority of our method to generate stylized dialogue responses is further demonstrated by analyzing the style intensity scores of responses with different levels of coherency. Specifically, all the annotated responses that are generated with a designated style of S 1 were collected and categorized into three groups based on the coherency scores (i.e., 0, 1, or 2) they received. The averaged style intensity score for each group was calculated and shown in Figure 4. It can be seen that our model achieves the highest style intensity scores in all coherency groups. This further demonstrates that the responses produced by our method are more style-intensive than those by the baselines.

Ablation Study
Ablation studies were performed to verify the effect of each component in our method. Specifically, the following variants were tested: 1) without the style routing approach (w/o Rout.), i.e., the style embedding is not explicitly incorporated in each decoder block as in Eq.5. The decoder d is stylized by employing a style token as the start token and adding a style embedding to each word embedding; 2) Without the joint training process (w/o JointT), i.e., an inverse dialogue model is first trained, and then a fixed set of pseudo pairs are generated and used to train the stylized dialogue model. Note that the same amount of pseudo pairs were used to optimize the loss L inv in this variant as it is used in Algorithm 1; 3) Without using the top-K sampling scheme when producing pseudo posts (w/o Samp.), i.e., pseudo pairs are decoded greedily; 4) Without using the pre-trained GPT weights (w/o PreT).
As shown in Table 4, our model achieves the highest BLEU and Coh. scores among all the ablation models. We can further observe that: 1) Almost all our variants surpass the baselines with a large margin on the style intensity score. This verifies the feasibility of our framework in capturing stylistic features; 2) Removing the joint training process (w/o JointT) or the top-K sampling scheme (w/o Samp.) makes the dialogue models over-fit to render more stylistic features while failing to achieve high BLEU and Coh. scores. However, we argue that since our stylized decoder is already strong in capturing stylistic features, it is critical to utilize the proposed joint training and top-K sampling scheme to improve the response coherency; 3) The pre-training approach significantly improves the diversity and coherency of the generated responses. Table 5 shows some dialogue responses generated by our model and the baselines on the two datasets. We can observe that the models that directly manipulate the continuous latent space (i.e., SFusion and S2S+CT) yield non-fluent responses. This is TCFC dataset Pseudo Post: Are you enjoying the new album? Text in S1: Yes, I am. I am loving her last cd. Pseudo Post: I'm so tired of golf. Text in S1: What is the point of golf? Pseudo Post: Hey, are you going to the game tonight? Text in S1: Hardly, I live up north. Maybe next time.

WDJN dataset
Pseudo Post: I am very, very sad today (今天的我,伤心的 不得了) Text in S1: Are your hurt? (你受伤了么？) Pseudo Post: Did anyone come to see me today?
(大哥，有人来啦。) Pseudo Post: I'm going to kill you today (今天我要杀了你) Text in S1: Dude, you could have killed me, but you didn't.
(老兄，刚才你本可杀我，没有下手。) because that it hard to build a smooth latent space for discrete texts. Moreover, pipelined approaches either fail to convert the inputs to the target style (i.e., S2S+PTO on the WDJN dataset), or hurt the coherency between the response and the post (i.e., S2S+BT, S2S+CT, and S2S+PTO on the TCFC dataset). In addition, we sampled some of these pseudo pairs generated by the inverse dialogue model in the training phase (Table 6). It can be seen that these pseudo pairs are generally of high quality both in fluency and coherency.

Conclusion
In this paper, we present a stylized dialogue generation method that can produce coherent and styleintensive responses by utilizing stylized unpaired texts. An inverse dialogue model is introduced in our method to produce stylized pseudo dialogue pairs, which are used in a joint training process to train the stylized dialogue model. Further, a style routing approach is introduced to intensify stylistic features in the decoding process. We demonstrate our method on two datasets with two different styles: Chinese Jinyong novels and formality in English writing. Automatic and manual evaluation shows that our method outperforms competitive baselines in producing coherent and style-intensive responses. As future works, we will extend this method to other stylized text generation tasks.


extfieldsofstudy:
Computer Science
Mathematics

text:
Tight last-iterate convergence rates for no-regret learning in multi-player games

We study the question of obtaining last-iterate convergence rates for no-regret learning algorithms in multi-player games. We show that the optimistic gradient (OG) algorithm with a constant step-size, which is no-regret, achieves a last-iterate rate of $O(1/\sqrt{T})$ with respect to the gap function in smooth monotone games. This result addresses a question of Mertikopoulos&Zhou (2018), who asked whether extra-gradient approaches (such as OG) can be applied to achieve improved guarantees in the multi-agent learning setting. The proof of our upper bound uses a new technique centered around an adaptive choice of potential function at each iteration. We also show that the $O(1/\sqrt{T})$ rate is tight for all $p$-SCLI algorithms, which includes OG as a special case. As a byproduct of our lower bound analysis we additionally present a proof of a conjecture of Arjevani et al. (2015) which is more direct than previous approaches.

Introduction
In the setting of multi-agent online learning ( [SS11,CBL06]), K players interact with each other over time. At each time step t, each player k ∈ {1, . . . , K} chooses an action z (t) k ; z (t) k may represent, for instance, the bidding strategy of an advertiser at time t. Player k then suffers a loss ℓ t (z (t) k ) that depends on both player k's action z (t) k and the actions of all other players at time t (which are absorbed into the loss function ℓ t (·)). Finally, player k receives some feedback informing them of how to improve their actions in future iterations. In this paper we study gradient-based feedback, meaning that the feedback is the vector g (t) A fundamental quantity used to measure the performance of an online learning algorithm is the regret of player k, which is the difference between the total loss of player k over T time steps and the loss of the best possible action in hindsight: formally, the regret at time T is An algorithm is said to be no-regret if its regret at time T grows sub-linearly with T for an adversarial choice of the loss functions ℓ t . If all agents playing a game follow no-regret learning algorithms to choose their actions, then it is well-known that the empirical frequency of their actions converges to a coarse correlated equilibrium (CCE) ([MV78, CBL06]). In turn, a substantial body of work (e.g., [CBL06, DP09, EDMN09, CD11, VZ13, KKDB15, BTHK15, MP17, MZ18, KBTB18]) has focused on establishing for which classes of games or learning algorithms this convergence to a CCE can be strengthened, such as to convergence to a Nash equilibrium (NE).
However, the type of convergence guaranteed in these works generally either applies only to the timeaverage of the joint action profiles, or else requires the sequence of learning rates to converge to 0. Such guarantees leave substantial room for improvement: a statement about the average of the joint action profiles a no-regret learning algorithm with constant step size? (⋆) We measure the proximity of an action profile z = (z 1 , . . . , z K ) to equilibrium in terms of the total gap function at z (Definition 3): it is defined to be the sum over all players k of the maximum decrease in cost player k could achieve by deviating from its action z k .
[LZMJ20] took initial steps toward addressing (⋆), showing that if all agents follow the online gradient descent algorithm, then for all λ-cocoercive games, the action profiles z (t) = (z (t) 1 , . . . , z (t) K ) will converge to equilibrium in terms of the total gap function at a rate of O(1/ √ T ). Moreover, linear last-iterate rates have been long known for smooth strongly-monotone games ([Tse95, GBV + 18, LS18, MOP19b, AMLJG19, ZMM + 20]), a sub-class of λ-cocoercive games. Unfortunately, even λ-cocoercive games exclude many important classes of games, such as bilinear games, which are the adaptation of matrix games to the unconstrained setting. Moreover, this shortcoming is not merely an artifact of the analysis of [LZMJ20]: it has been observed (e.g. [DISZ17, GBV + 18]) that in bilinear games, the players' actions in online gradient descent not only fail to converge, but diverge to infinity. Prior work on last-iterate convergence rates for these various subclasses of monotone games is summarized in Table 1 for the case of perfect gradient feedback; the setting for noisy feedback is summarized in Table 2 in Appendix A.4.

Our contributions
In this paper we answer (⋆) in the affirmative for all monotone games (Definition 1) satisfying a mild smoothness condition, which includes smooth λ-cocoercive games and bilinear games. Many common and well-studied classes of games, such as zero-sum polymatrix games ( [BF87,DP09,CCDP16]) and its generalization zero-sum socially-concave games ([EDMN09]) are monotone but are not in general λ-cocoercive. Hence our paper is the first to prove last-iterate convergence in the sense of (⋆) for the unconstrained version of these games as well. In more detail, we establish the following: • We show in Theorem 5 and Corollary 6 that the actions taken by learners following the optimistic gradient (OG) algorithm, which is no-regret, exhibit last-iterate convergence to a Nash equilibrium in smooth, monotone games at a rate of O(1/ √ T ) in terms of the global gap function. The proof uses a new technique which we call adaptive potential functions (Section 3.1) which may be of independent interest.
• We show in Theorem 7 that the rate O(1/ √ T ) cannot be improved for any algorithm belonging to the class of p-SCLI algorithms (Definition 5), which includes OG.
The OG algorithm is closely related to the extra-gradient (EG) algorithm ([Kor76, Nem04]), 2 which, at each time step t, assumes each player k has an oracle O k which provides them with an additional gradient at a slightly different action than the action z (t) k played at step t. Hence EG does not naturally fit into the standard setting of multi-agent learning. One could try to "force" EG into the setting of multi-agent learning by taking actions at odd-numbered time steps t to simulate the oracle O k , and using the even-numbered time steps to simulate the actions z (t) k that EG actually takes. Although this algorithm exhibits last-iterate convergence at a rate of O(1/ √ T ) in smooth monotone games when all players play according to it [GPDO20], it is straightforward to see that it is not a no-regret learning algorithm, i.e., for an adversarial loss function the regret can be linear in T (see Proposition 10 in Appendix A.3).
Nevertheless, due to the success of EG at solving monotone variational inequalities, [MZ18] asked whether similar techniques to EG could be used to speed up last-iterate convergence to Nash equilibria. Our upper bound for OG answers this question in the affirmative: various papers ([CYL + 12, RS12, RS13, HIMM19]) have observed that OG may be viewed as an approximation of EG, in which the previous iteration's gradient is used to simulate the oracle O k . Moreover, our upper bound of O(1/ √ T ) applies in many games for which the approach used in [MZ18], namely Nesterov's dual averaging ([Nes09]), either fails to converge (such as bilinear games) or only yields asymptotic rates with decreasing learning rate (such as smooth strictly monotone games). Proving last-iterate rates for OG has also been noted as an important open question in [HIMM19, Table 1]. At a technical level, the proof of our upper bound (Theorem 5) uses the proof technique in [GPDO20] for the last-iterate convergence of EG as a starting point. In particular, similar to [GPDO20], our proof proceeds by first noting that some iterate z (t * ) of OG will have gradient gap O(1/ √ T ) (see Definition 2; this is essentially a known result) and then showing that for all t ≥ t * the gradient gap only increases by at most a constant factor. The latter step is the bulk of the proof, as was the case in [GPDO20]; however, since each iterate of OG depends on the previous two iterates and gradients, the proof for OG is significantly more involved than that for EG. We refer the reader to Section 3.1 and Appendix B for further details.
The proof of our lower bound for p-SCLI algorithms, Theorem 7, reduces to a question about the spectral radius of a family of polynomials. In the course of our analysis we prove a conjecture by [ASSS15] about such polynomials; though the validity of this conjecture is implied by each of several independent results in the literature (e.g., [AS16,Nev93]), our proof is more direct than previous ones.
Lastly, we mention that our focus in this paper is on the unconstrained setting, meaning that the players' losses are defined on all of Euclidean space. We leave the constrained setting, in which the players must project their actions onto a convex constraint set, to future work.

Related work
Multi-agent learning in games. In the constrained setting, many papers have studied conditions under which the action profile of no-regret learning algorithms, often variants of Follow-The-Regularized-Leader (FTRL), converges to equilibrium. However, these works all assume either a learning rate that decreases over time ([MZ18, ZMB + 17, ZMA + 18, ZMM + 17]), or else only apply to specific types of potential games ([KKDB15, KBTB18, PPP17, KPT09, CL16, BEDL06, PP14]), which significantly facilitates the analysis of last-iterate convergence. 3 Such potential games are in general incomparable with monotone games, and do not even include finitestate two-player zero sum games (i.e., matrix games). In fact, [BP18] showed that the actions of players following FTRL in two-player zero-sum matrix games diverge from interior Nash equilibria. Many other works ([HMC03, MPP17, KLP11, DFP + 10, BCM12, PP16]) establish similar non-convergence results in both discrete and continuous time for various types of monotone games, including zero-sum polymatrix games. Such non-convergence includes chaotic behavior such as Poincaré recurrence, which showcases the insufficiency of on-average convergence (which holds in such settings) and so is additional motivation for the question (⋆).

Monotone variational inequalities & OG.
The problem of finding a Nash equilibrium of a monotone game is exactly that of finding a solution to a monotone variational inequality (VI). OG was originally introduced by [Pop80], who showed that its iterates converge to solutions of monotone VIs, without proving explicit rates. 4 It is also well-known that the averaged iterate of OG converges to the solution of a monotone VI at a rate of O(1/T ) ([HIMM19, MOP19a, RS13]), which is known to be optimal ([Nem04, OX19, ASM + 20]). Recently it has been shown ([DP18, LNPW20]) that a modification of OG known as optimistic multiplicativeweights update exhibits last-iterate convergence to Nash equilibria in two-player zero-sum monotone games, but as with the unconstrained case ([MOP19a]) non-asymptotic rates are unknown. To the best of our knowledge, the only work proving last-iterate convergence rates for general smooth monotone VIs was [GPDO20], which only treated the EG algorithm, which is not no-regret. There is a vast literature on solving VIs, and we refer the reader to [FP03] for further references.

Preliminaries
Throughout this paper we use the following notational conventions. For a vector v ∈ R n , let v denote the Euclidean norm of v. For v ∈ R n , set B(v, R) := {z ∈ R n : v − z ≤ R}; when we wish to make the dimension explicit we write B R n (v, R). For a matrix A ∈ R n×n let A σ denote the spectral norm of A.
We let the set of K players be denoted by K := {1, 2, . . . K}. Each player k's actions z k belong to their action set, denoted Z k , where Z k ⊆ R n k is a convex subset of Euclidean space. Let Z = K k=1 Z k ⊆ R n , where n = n 1 + · · · + n K . In this paper we study the setting where the action sets are unconstrained (as in [LZMJ20]), meaning that Z k = R n k , and Z = R n , where n = n 1 + · · · + n K . The action profile is the vector z := (z 1 , . . . , z K ) ∈ Z. For any player k ∈ K, let z −k ∈ k ′ =k Z k ′ be the vector of actions of all the other players. Each player k ∈ K wishes to minimize its cost function f k : Z → R, which is assumed to be twice continuously differentiable. The tuple G := (K, (Z k ) K k=1 , (f k ) K k=1 ) is known as a continuous game. At each time step t, each player k plays an action z (t) k ; we assume the feedback to player k is given in the form of the gradient −k ) of their cost function with respect to their action z (t) k , given the actions z (t) −k of the other players at time t. We denote the concatenation of these gradients by F G (z) := (∇ z1 f 1 (z), . . . , ∇ zK f K (z)) ∈ R n . When the game G is clear, we will sometimes drop the subscript and write F : Z → R n .
Equilibria & monotone games. A Nash equilibrium in the game G is an action profile z * ∈ Z so that for each player k, it holds that for any z ′ k ∈ Z k . Throughout this paper we study monotone games: In such a case, we say also that F G is a monotone operator.
The following classical result characterizes the Nash equilibria in monotone games: In the unconstrained setting, if the game G is monotone, any Nash equilibrium z * satisfies F G (z * ) = 0. Conversely, if F G (z) = 0, then z is a Nash equilibrium.
In accordance with Proposition 1, one measure of the proximity to equilibrium of some z ∈ Z is the norm of F G (z): Definition 2 (Gradient gap function). Given a monotone game G with its associated operator F G , the gradient gap function evaluated at z is defined to be F G (z) .
It is also common ([MOP19a, Nem04]) to measure the distance from equilibrium of some z ∈ Z by adding the maximum decrease in cost that each player could achieve by deviating from their current action z k : Definition 3 (Total gap function). Given a monotone game G = (K, (Z k ) K k=1 , (f k ) K k=1 ), compact subsets Z ′ k ⊆ Z k for each k ∈ K, and a point z ∈ Z, define the total gap function at z with respect to the set . At times we will slightly abuse notation, and for F := F G , write TGap Z ′ F in place of TGap Z ′ G . As discussed in [GPDO20], it is in general impossible to obtain meaningful guarantees on the total gap function by allowing each player to deviate to an action in their entire space Z k , which necessitates defining the total gap function in Definition 3 with respect to the compact subsets Z ′ k . We discuss in Remark 4 how, in our setting, it is without loss of generality to shrink Z k so that Z k = Z ′ k for each k. Proposition 2 below shows that in monotone games, the gradient gap function upper bounds the total gap function: is a monotone game, and compact subsets Z ′ k ⊂ Z k are given, where the diameter of each Z ′ k is upper bounded by D > 0. Then For completeness, a proof of Proposition 2 is presented in Appendix A.
Special case: convex-concave min-max optimization. Since in a two-player zero-sum game G = ({1, 2}, (Z 1 , Z 2 ), (f 1 , f 2 )) we must have f 1 = −f 2 , it is straightforward to show that f 1 (z 1 , z 2 ) is convex in z 1 and concave in z 2 . Moreover, it is immediate that Nash equilibria of the game G correspond to saddle points of f 1 ; thus a special case of our setting is that of finding saddle points of convex-concave functions ([FP03]). Such saddle point problems have received much attention recently since they can be viewed as a simplified model of generative adversarial networks (e.g., [GBV + 18, DISZ17, CGFLJ19, GHP + 18, YSX + 17]).
Optimistic gradient (OG) algorithm. In the optimistic gradient (OG) algorithm, each player k performs the following update: z where g The following essentially optimal regret bound is well-known for the OG algorithm, when the actions of the other players z (t) −k (often referred to as the environment's actions) are adversarial: In Proposition 3, z * k is defined by The assumption in the proposition that z (t) k ≤ D may be satisfied in the unconstrained setting by projecting the iterates onto the region B(0, D) ⊂ R n k , for some D ≥ z * k , without changing the regret bound. The implications of this modification to (OG) are discussed further in Remark 4.

Last-iterate rates for OG via adaptive potential functions
In this section we show that in the unconstrained setting (namely, that where Z k = R n k for all k ∈ K), when all players act according to OG, their iterates exhibit last-iterate convergence to a Nash equilibrium. Our convergence result holds for games G for which the operator F G satisfies the following smoothness assumption: Assumption 4 (Smoothness). For a monotone operator F : Z → R n , assume that the following first and second-order Lipschitzness conditions hold, for some ℓ, Λ > 0: Here ∂F : Z → R n×n denotes the Jacobian of F .
By the definition of F G (·), when all players in a game G act according to (OG) with constant step size η, then the action profile z (t) takes the form The main theorem of this section, Theorem 5, shows that under the OG updates (3), the iterates converge at a rate of O(1/ √ T ) to a Nash equilibrium with respect to the gradient gap function: Theorem 5 (Last-iterate convergence of OG). Suppose G is a monotone game so that F G satisfies Assumption 4. For some Then the iterates z (T ) of OG (3) for any η ≤ min 1 150ℓ , 1 1711DΛ satisfy: By Proposition 2, we immediately get a bound on the total gap function at each time T : Corollary 6 (Total gap function for last iterate of OG). In the setting of Theorem 5, let Z ′ k := B(z We made no attempt to optimize the consants in Theorem 5 and Corollary 6, and they can almost certainly be improved.
Remark 4 (Bounded iterates). Recall from the discussion following Proposition 3 that it is necessary to project the iterates of OG onto a compact ball to achieve the no-regret property. As our guiding question (⋆) asks for last-iterate rates achieved by a no-regret algorithm, we should ensure that such projections are compatible with the guarantees in Theorem 5 and Corollary 6. For this we note that [MOP19a, Lemma 4(b)] showed that for the dynamics (3) without constraints, for all t ≥ 0, z (t) − z * ≤ 2 z (0) − z * . Therefore, as long as we make the very mild assumption of a known a priori upper bound z * ≤ D/2 (as well as z , if all players act according to (3), then the updates (3) remain unchanged if we project onto the constraint sets Z k := B(0, 3D) at each time step t. This observation also serves as motivation for the compact sets Z ′ k used in Corollary 6: the natural choice for Z ′ k is Z k itself, and by restricting Z k to be compact, this choice becomes possible.

Proof overview: adaptive potential functions
In this section we sketch the idea of the proof of Theorem 5; full details of the proof may be found in Appendix B. First we note that it follows easily from results of [HIMM19] that OG exhibits best-iterate convergence, i.e., in the setting of Theorem 5 we have, for each T > 0, min 1≤t≤T F G (z (t) ) ≤ O(1/ √ T ). 5 The main contribution of our proof is then to show the following: if we choose t * so that ) . This was the same general approach taken in [GPDO20] to prove that the extragradient (EG) algorithm has last-iterate convergence. In particular, they showed the stronger statement that F G (z (t) ) may be used as an approximate potential function in the sense that it only increases by a small amount each step: However, their approach relies crucially on the fact that for the EG algorithm, z (t+1) depends only on z (t) .
For the OG algorithm, it is possible that (6) fails to hold, even when F G (z (t) ) is replaced by the more natural choice of (F G (z (t) ), F G (z (t−1) )). 6 Instead of using F G (z (t) ) as a potential function in the sense of (6), we propose instead to track the behavior of F (t) , whereF and the matrices C (t−1) ∈ R n×n are defined recursively backwards, i.e., C (t−1) depends directly on C (t) , which depends directly on C (t+1) , and so on. For an appropriate choice of the matrices C (t) , we show that . This modification of (6) is enough to show the desired upper bound of F G (z (T ) ) ≤ O(1/ √ T ). To motivate the choice ofF (t) in (7) it is helpful to consider the simple case where F (z) = Az for some A ∈ R n×n , which was studied by [LS18]. Simple algebraic manipulations using (3) (detailed in Appendix B) show that, for the matrix C := (I+(2ηA) 2 ) 1/2 −I 2 , we haveF (t+1) = (I − ηA + C)F (t) for all t. It may be verified that we indeed have A (t) = A and C (t) = C for all t in this case, and thus (7) may be viewed as a generalization of these calculations to the nonlinear case.
Adaptive potential functions. In general, a potential function Φ(F G , z) depends on the problem instance, here taken to be F G , and an element z representing the current state of the algorithm. Many convergence analyses from optimization (e.g., [BG17,WRJ18], and references therein) have as a crucial element in their proofs a statement of the form Φ(F G , z (t+1) ) Φ(F G , z (t) ). For example, for the iterates z (t) of the EG algorithm, [GPDO20] (see (6)) used the potential function Φ(F G , z (t) ) := F G (z (t) ) .
Our approach of controlling the the norm of the vectorsF (t) defined in (7) can also be viewed as an instantion of the potential function approach: since each iterate of OG depends on the previous two iterates, the state is now given by v (t) := (z (t−1) , z (t) ). The potential function is given by Φ OG (F G , v (t) ) := F (t) , whereF ⊤ is defined in (7) and indeed only depends on v (t) once F G is fixed since v (t) determines z (t ′ ) for all t ′ ≥ t (as OG is deterministic), which in turn determine C (t−1) . However, the potential function Φ OG is quite unlike most other choices of potential functions in optimization (e.g., [BG17]) in the sense that it depends globally on F G : For any t ′ > t, a local change in adapts to the behavior of F G at iterates later on in the optimization sequence, we call it an adaptive potential function. We are not aware of any prior works using such adaptive potential functions to prove last-iterate convergence results, and we believe this technique may find additional applications.

Lower bound for convergence of p-SCLIs
The main result of this section is Theorem 7, stating that the bounds on last-iterate convergence in Theorem 5 and Corollary 6 are tight when we require the iterates z (T ) to be produced by an optimization algorithm satisfying a particular formal definition of "last-iterate convergence". Notice that that we cannot hope to prove that they are tight for all first-order algorithms, since the averaged iteratesz (T ) := 1 Theorem 2]. Similar to [GPDO20], we use p-stationary canonical linear iterative methods (p-SCLIs) to formalize the notion of "last-iterate convergence". [GPDO20] only considered the special case p = 1 to establish a similar lower bound to Theorem 7 for a family of last-iterate algorithms including the extragradient algorithm. The case p > 1 leads to new difficulties in our proof since even for p = 2 we must rule out algorithms such as Nesterov's accelerated gradient descent ([Nes75]) and Pólya's heavy-ball method ([Pol87]), a situation that did not arise for p = 1.
For simplicity, we restrict our attention to monotone operators F arising as F = F G : R n → R n for a two-player zero-sum game G (i.e., the setting of min-max optimization). For simplicity suppose that n is even and for z ∈ R n write z = (x, y) where x, y ∈ R n/2 . Define F bil n,ℓ,D to be the set of ℓ-Lipschitz operators F : R n → R n of the form F (x, y) = (∇ x f (x, y), −∇ y f (x, y)) ⊤ for some bilinear function f : R n/2 × R n/2 → R, with a unique equilibrium point z * = (x * , y * ), which satisfies z * ∈ D D := B R n/2 (0, D) × B R n/2 (0, D). The following Theorem 7 uses functions in F bil n,ℓ,D as "hard instances" to show that the O(1/ √ T ) rate of Corollary 5 cannot be improved by more than an algorithm-dependent constant factor.
Theorem 7 (Algorithm-dependent lower bound for p-SCLIs). Fix ℓ, D > 0, let A be a p-SCLI, and let z (t) denote the tth iterate of A. Then there are constants c A , T A > 0 so that the following holds: For all T ≥ T A , there is some F ∈ F bil n,ℓ,D so that for some initialization z (0) , . . . , z (−p+1) ∈ D D and T ′ ∈ {T, T + 1, . . . , T + p − 1}, it holds that TGap D2D We remark that the order of quantifiers in Theorem 7 is important: if instead we first fix a monotone operator F ∈ F bil n,ℓ,D corresponding to some bilinear function f (x, y) = x ⊤ My, then as shown in [LS18, Theorem 3], the iterates z (T ) = (x (T ) , y (T ) ) of the OG algorithm will converge at a rate of e , which eventually becomes smaller than the sublinear rate of 1/ √ T . 8 Such "instance-specific" bounds are complementary to the minimax perspective taken in this paper.
We briefly discuss the proof of Theorem 7; the full proof is deferred to Appendix C. As in prior work proving lower bounds for p-SCLIs ([ASSS15, IAGM19]), we reduce the problem of proving a lower bound on TGap DD G (z (t) ) to the problem of proving a lower bound on the supremum of the spectral norms of a family of polynomials (which depends on A). Recall that for a polynomial p(z), its spectral norm ρ(p(z)) is the maximum norm of any root. We show: Proposition 8. Suppose q(z) is a degree-p monic real polynomial such that q(1) = 0, r(z) is a polynomial of degree p − 1, and ℓ > 0. Then there is a constant C 0 > 0, depending only on q(z), r(z) and ℓ, and some µ 0 ∈ (0, ℓ), so that for any µ ∈ (0, µ 0 ), The proof of Proposition 8 uses elementary tools from complex analysis. The fact that the constant C 0 in Proposition 8 depends on q(z), r(z) leads to the fact that the constants c A , T A in Theorem 7 depend on A. Moreover, we remark that this dependence cannot be improved from Proposition 8, so removing it from Theorem 7 will require new techniques: Proposition 9 (Tightness of Proposition 8). For any constant C 0 > 0 and µ 0 ∈ (0, ℓ), there is some µ ∈ (0, µ 0 ) and polynomials q(z), r(z) so that sup ν∈[µ,ℓ] ρ(q(z) − ν · r(z)) < 1 − C 0 · µ. Moreover, the choice of the polynomials is given by The choice of polynomials q(z), r(z) in (9) are exactly the polynomials that arise in the p-SCLI analysis of Nesterov's AGD [ASSS15]; as we discuss further in Appendix C, Proposition 8 is tight, then, even for p = 2, because acceleration is possible with a 2-SCLI. As byproducts of our lower bound analysis, we additionally obtain the following: • Using Proposition 8, we show that any p-SCLI algorithm must have a rate of at least Ω A (1/T ) for smooth convex function minimization (again, with an algorithm-dependent constant). 9 This is slower than the O(1/T 2 ) error achievable with Nesterov's AGD with a time-varying learning rate.
• We give a direct proof of the following statement, which was conjectured by [ASSS15]: for polynomials q, r in the setting of Proposition 8, for any 0 . Using this statement, for the setting of Theorem 7, we give a proof of an algorithm-independent Though the algorithm-independent lower bound of Ω(ℓD 2 /T ) has already been established in the literature, even for non-stationary CLIs (e.g., [ASM + 20, Proposition 5]), we give an alternative proof from existing approaches.

Discussion
In this paper we proved tight last-iterate convergence rates for smooth monotone games when all players act according to the optimistic gradient algorithm, which is no-regret. We believe that there are many fruitful directions for future research. First, it would be interesting to obtain last-iterate rates in the case that each player's actions is constrained to the simplex and they use the optimistic multiplicative weights update (OMWU) algorithm. [DP18, LNPW20] showed that OMWU exhibits last-iterate convergence, but non-asymptotic rates remain unknown even for the case that F G (·) is linear, which includes finite-action polymatrix games. Next, it would be interesting to determine whether Theorem 5 holds if (2) is removed from Assumption 4; this problem is open even for the EG algorithm ([GPDO20]). Finally, it would be interesting to extend our results to the setting where players receive noisy gradients (i.e., the stochastic case). As for lower bounds, it would be interesting to determine whether an algorithm-independent lower bound of Ω(1/ √ T ) in the context of Theorem 7 could be proven for stationary p-SCLIs. As far as we are aware, this question is open even for convex minimization (where the rate would be Ω(1/T )).

A Additional preliminaries
A.1 Proof of Proposition 2 Proof of Proposition 2. Fix a game G, and let F = F G : Z → R n . Monoticity of F gives that for any fixed Summing the above for k ∈ K and using the definition of the total and gradient gap functions, as well as Cauch-Schwarz, gives that

A.2 Optimistic gradient algorithm
In this section we review some additional background about the optimistic gradient algorithm in the setting of no-regret learning. The starting point is online gradient descent; player k following online gradient descent produces iterates z k and the other players' actions z (t) −k at time t. Online gradient descent is a noregret algorithm (in particular, it satisfies the same regret bound as OG in Proposition 3); it is also closely related to the follow-the-regularized-leader (FTRL) ([SS11]) algorithm from online learning. 10 The optimistic gradient (OG) algorithm ([RS13, DISZ17]) is a modification of online gradient descent, for which player k performs the following update: where again g −k ) for t ≥ 0. As way of intuition behind the updates (OG), [DISZ17] observed that OG is closely related to the optimistic follow-the-regularized-leader (OFTRL) algorithm from online learning: OFTRL augments the standard FTRL update by using the gradient g (t) k at time t as a prediction for the gradient at time t + 1. When the actions z (t) −k of the other players are predictable in the sense that they do not change quickly over time, then such a prediction using g (t) k is reasonably accurate and can improve the speed of convergence to an equilibrium ([RS13]).

A.3 Linear regret for extragradient algorithm
In this section we review the definition of the extragradient (EG) algorithm, and show that if one attempts to implement it in the setting of online multi-agent learning, then it is not a no-regret algorithm. Given a monotone game G and its corresponding monotone operator F G : Z → R n and an initial point u (0) ∈ R n the EG algorithm attempts to find a Nash equilibrium z * (i.e., a point satisfying F G (z * ) = 0) by performing the updates: where Π Z (·) denotes Euclidean projection onto the convex set Z. Assuming Z contains a sufficiently large ball centered at z * , this projection step has no effect for the updates shown above when all players perform EG updates (see Remark 4); the projection is typically needed, however, for the adversarial setting that we proceed to discuss in this section (e.g., as in Proposition 3). It is easy to see that the updates (10) and (11) can be rewritten as −1) )))). Note that these updates are somewhat similar to those of OG when expressed as (23) and (24), with w (t) in (23) and (24) playing a similar role to u (t) in (10) and (11). A key difference is that the iterate u (t) is needed to update z (t) in (11), whereas this is not true for the update to z (t) in (23). Since in the standard setting of online multi-agent learning, agents can only see gradients corresponding to actions they play, in order to implement the above EG updates in this setting, we need two timesteps for every timestep of EG. In particular, the agents will play actions where v k . Unfortunately, as we show in Proposition 10 below, in the setting when the other players' actions z (t) −k are adversarial (i.e., players apart from k do not necessarily play according to EG), the algorithm for player k given by the EG updates (12) and (13) can have linear regret, i.e., is not a no-regret algorithm. Thus the EG algorithm is insufficient for answering our motivating question (⋆).
Proposition 10. There is a set Z = K k=1 Z k together with a convex, 1-Lipschitz, and 1-smooth function f 1 : Z → R so that for an adversarial choice of z (t) −k , the EG updates (12) and (13) produce a sequence v −k ) for any T > 0. Proof. We take K = 1, k = 1, n = 2, Z 1 = Z 2 = [−1, 1], and f 1 : Suppose that player 1 initializes at v It follows that for t ≥ 0 we have v 2 ) = 0 whereas the following two possible boundedness assumptions: where σ t > 0 and τ t > 0 are sequences of positive reals (typically taken to be decreasing with t). Often it is assumed that σ t is the same for all t, in which case we write σ = σ t . Noise model (Abs) is known as absolute random noise, and (Rel) is known as relative random noise [LZMJ20]. The latter is only of use in the unconstrained setting in which the goal is to find z * with F G (z * ) = 0. While we restrict Table 2 to 1st order methods, we refer the reader also to the recent work of [LBJM + 20], which provides last-iterate rates for stochastic Hamiltonian gradient descent, a 2nd order method, in "sufficiently bilinear" games.
As can be seen in Table 2, there is no work to date proving last-iterate rates for general smooth monotone games. We view the problem of extending the results of this paper and of [GPDO20] to the stochastic setting (i.e., the bottom row of Table 2) as an interesting direction for future work.  Table 1; ℓ, Λ are the Lipschitz constants of FG, ∂FG, respectively, and c > 0 is a sufficiently small absolute constant. The right-hand column contains algorithms implementable as online no-regret learning algorithms: stochastic optimistic gradient (Stoch. OG) or stochastic gradient descent (SGD). The left-hand column contains algorithms not implementable as no-regret algorithms, which includes stochastic extragradient (Stoch. EG), stochastic forward-backward (FB) splitting, double stepsize extragradient (DSEG), and stochastic variance reduced extragradient (SVRE). SVRE only applies in the finite-sum setting, which is a special case of (Abs) in which f k is a sum of m individual loss functions f k,i , and a noisy gradient is obtained as ∇f k,i for a random i ∈ [m]. Due to the stochasticity, many prior works make use of a step size ηt that decreases with t; we make note of whether this is the case ("ηt decr.") or whether the step size ηt can be constant ("ηt const."). For simplicity of presentation we assume Ω(1/t) ≤ {τt, σt} ≤ O(1) for all t ≥ 0 in all cases for which σt, τt vary with t. Reported bounds are stated for the total gap function (Definition 3); leading constants and factors depending on distance between initialization and optimum are omitted.

Stochastic Game class
Not implementable as no-regret Implementable as no-regret µ-strongly monotone  In this section we prove Theorem 5. In Section B.1 we show that OG exhibits best-iterate convergence, which is a simple consequence of prior work. In Section B.1 we begin to work towards the main contribution of this work, namely showing that best-iterate convergence implies last iterate convergence, treating the special case of linear monotone operators F (z) = Az. In Section B.3 we introduce the adaptive potential function for the case of general smooth monotone operators F , and finally in Section B.4, using this choice of adaptive potential function, we prove Theorem 5. Some minor lemmas used throughout the proof are deferred to Section B.5.

B.1 Best-iterate convergence
Throughout this section, fix a monotone game G satisfying Assumption 4, and write F = F G , so that F is a monotone operator (Definition 1). Recall that the OG algorithm with constant step size η > 0 is given by: In Lemma 11 we observe that some iterate z (t * ) of OG has small gradient gap.
In the remainder of this section we present our main technical contribution in the context of Theorem 5, showing that for a fixed T , the last iterate z (T ) does not have gradient gap F (z (T ) ) much larger than min 1≤t≤T max 0≤s≤2 F (z (t+s) ) .

B.2 Warm-up: different perspective on the linear case
Before treating the case where F is a general smooth monotone operator, we first explain our proof technique for the case that F (z) = Az for some matrix A ∈ R n×n . This case is covered by [LS18, Theorem 3] 11 ; the discussion here can be viewed as an alternative perspective on this prior work.
Assume that F (z) = Az for some A ∈ R n×n throughout this section. Let z (t) be the iterates of OG, and define Thus the updates of OG can be written as The extra-gradient (EG) algorithm is the same as the updates (19) where the square root of I + (2ηA) 2 may be defined via the power series It is easy to check that C is well-defined as long as η ≤ O(1/ℓ) ≤ O(1/ A σ ), and that CA = AC. Also note that C satisfies Finally setw (t) = w (t) + Cz (t−1) , so thatw (t) corresponds (under the PEG interpretation of OG) to the iterates w (t) of EG, plus an "adjustment" term, Cz (t) , which is O((ηA) 2 ). Though this adjustment term is small, it is crucial in the following calculation:w Since C, A commute, the above implies that F (w (t+1) ) = (I − ηA + C)F (w (t) ). Monotonicity of F implies that for η = O(1/ℓ), we have I − ηA + C σ ≤ 1. It then follows that F (w (t+1) ) ≤ F (w (t) ) , which establishes that the last iterate is the best iterate.

B.3 Setting up the adaptive potential function
We next extend the argument of the previous section to the smooth convex-concave case, which will allow us to prove Theorem 5 in its full generality. Recall the PEG formulation of OG introduced in the previous section: where again z (t) denote the iterates of OG (15). As discussed in Section 3.1, the adaptive potential function is given by F (t) , wherẽ for some matrices C (t) ∈ R n×n , −1 ≤ t ≤ T , to be chosen later. Then: where (Recall that ∂F (·) denotes the Jacobian of F .) We state the following lemma for later use: Proof. For all z ∈ R n , monotonicity of F gives that ∂F (z) + ∂F (z) ⊤ is PSD, which means that so are A (t) + (A (t) ) ⊤ , B (t) + (B (t) ) ⊤ . Similarly, (1) gives that for all z ∈ R n , ∂F (z) σ ≤ ℓ, from which we get A (t) σ ≤ ℓ, B (t) σ ≤ ℓ by the triangle inequality. The remaining three inequalities are an immediate consequence of the triangle inequality and the fact that ∂F is Λ-Lipschitz (Assumption 4). Now define the following n × n matrices: Moreover, for a positive semidefinite (PSD) matrix S ∈ R n×n and a vector v ∈ R n , write v 2 S := v ⊤ Sv, so that for a matrix M ∈ R n×n and a vector v ∈ R n , we have Then by (26), Next we define C (T ) = 0 and for −1 ≤ t < T , 12 Notice that the definition of C (t−1) in (28) depends on C (t) , which depends on C (t+1) , and so on. By (27) and (25), it follows that Our goal from here on is two-fold: (1) to prove an upper bound on I − ηA (t) + C (t) σ , which will ensure, by (30), that F (t+1) F (t) , and (2) to ensure that F (t) is an (approximate) upper bound on F (z (t) ) for all t, so that in particular upper bounding F (T ) suffices to upper bound F (z (T ) ) . These tasks will be performed in the following section; we first make a few remarks on the choice of C (t−1) in (28): Remark 6 (Specialization to the linear case & experiments). In the case that the monotone operator F is linear, i.e., F (z) = Az, it is straightforward to check that the matrices C (t−1) as defined in (28) are all equal to the matrix C defined in (21) and A (t) = B (t) = A for all t. A special case of a linear operator F is that corresponding to a two-player zero-sum matrix game, i.e., where the payoffs of the players given actions x, y, are ±x ⊤ My. In experiments we conducted for random instances of such matrix games, we observe that the adaptive potential functionF (t) closely tracks F (z (t) ), and both are monotonically decreasing with t. It seems that any "interesting" behavior whereby F (z (t) ) grows by (say) a constant factor over the course of one or more iterations, but whereF (t) grows only by much less, must occur for more complicated monotone operators (if at all). We leave a detailed experimental evaluation of such possibilities to future work.
Remark 7 (Alternative choice of C (t) ). It is not necessary to choose C (t−1) as in (28). Indeed, in light of the fact that it is the spectral norms I − ηA (t−1) + C (t−1) σ that control the increase in F (t−1) to F (t) , it is natural to try to set The reason for the constraint * defined in (32) is to ensure that F (t+1) 2 ≤ F (t) 2 (M (t) ) ⊤ M (t) (so that (29) is replaced with an inequality). The reason for the constraint C σ ≤ 1/10 is to ensure that F (z (T ) ) ≤ O F (T ) . Though the asymptotic rate of O(1/ √ T ) established by the choice of C (t−1) in (28) is tight in light of Theorem 7, it is possible that a choice of C (t−1) as in (31) could lead to an improvement in the absolute constant. We leave an exploration of this possibility to future work.

B.4 Proof of Theorem 5
In this section we prove Theorem 5 using the definition ofF (t) in (25), where C (t−1) is defined in (28). We begin with a few definitions: for positive semidefinie matrices S, T, write S T if T − S is positive semidefinite (this is known as the Loewner ordering). We also define To understand the definition of the matrices D (t) in (33), note that, in light of the equality for a square matrix X for which I − X is invertible, we have, for t ≤ T , Thus, to upper bound I − A (t−1) + C (t−1) , it will suffice to use the below lemma, which generalizes [GPDO20, Lemma 12] and can be used to give an upper bound on the spectral norm of I − ηA (t−1) + η 2 A (t) B (t) + D (t) for each t: Lemma 13. Suppose A 1 , A 2 , B, D ∈ R n×n are matrices and K, L 0 , L 1 , L 2 , δ > 0 so that: It follows that I − A 1 + A 2 B + D σ ≤ 1 + (K + 400) δ 2 .
Proof of Lemma 13. We wish to show that /2, so that R 1 , R 2 , S are positive semidefinite and J 1 , J 2 , K are anti-symmetric.

Lemma 15 uses backwards induction (on t) to establish bounds on the matrices C (t) .
Lemma 15 (Backwards induction lemma). Suppose that there is some L 0 > 0 so that for all t ≤ T , we have max{η A (t) σ , η B (t) σ } ≤ L 0 ≤ 1/200 and ηℓ ≤ 2/3. Then: 2. The matrices C (t) are well-defined, i.e., I − ηA (t) + C (t) is invertible for each t ∈ [T ], and the spectral norm of its inverse is bounded above by √ 2.
4. For all t < T , it holds that for J 1 = 8L 2 0 and J 2 = 30L 2 0 η 2 (ηΛ) 2 . Proof. The proof proceeds by backwards induction on t. The base case t = T clearly holds since C (T ) = 0. As for the inductive step, suppose that items 1 through 4 hold at time step t, for some t ≤ T . Then by (28) and L 0 ≤ √ 2−1 2 , establishing item 1 at time t − 1.
Next we establish items 4 and 5 at time t − 1. First, we have where the final inequality uses ηℓ ≤ 2/3.
Lemma 16. Suppose that the pre-conditions of Lemma 15 (namely, those in its first sentence) hold. Then for each t ∈ [T ], we have and Proof. By Lemma 17, for any ǫ > 0, Also, for any ǫ > 0, where (63)  Choosing ǫ = 3L 0 and using the definition of D (t) in (33), it follows from the above displays that which establishes (61).
Finally we are ready to prove Theorem 5; for convenience we restate it here.
• We calculate that holds as long as L 0 ≤ 1/150.
The conclusion of Theorem 5 is an immediate conclusion of item 2 at time T , since 4δ ≤ 5δ 0 = 60D η √ T .

B.5 Helpful lemmas
Lemma 17 (Young's inequality). For square matrices X, Y, we have, for any ǫ > 0, Applying the previous lemma to the cross terms in the quantity XX ⊤ when using the decomposition X = Y + (X − Y), we obtain the following.
Lemma 18. For square matrices X, Y, we have, for any ǫ > 0, In particular, choosing ǫ = 1 gives Lemma 19 is an immediate corollary of the two lemmas above: Lemma 19. For square matrices X, Y, we have Lemma 20. For square matrices X, Y such that Y σ ≤ M , we have Proof. For any v, we have YXv 2 ≤ M 2 Xv 2 .

C Proofs for Section 4
In this section we prove Theorem 7, and as byproducts of our analysis additionally prove the results mentioned at the end of Section 4. Recall from Section 4 that F bil n,ℓ,D is defined to be the set of ℓ-Lipschitz operators F : R n → R n of the form for which A is of full rank and −A −1 b ∈ D D := B R n/2 (0, D) × B R n/2 (0, D). Note that each F ∈ F bil n,ℓ,D can be written as the min-max gradient operator F (x, y) = (∇ x f (x, y) ⊤ , −∇ y f (x, y) ⊤ ) ⊤ corresponding to the function We next note that when F ∈ F bil n,ℓ,D , the p-SCLI updates of Definition 5 can be rewritten as follows: Observation 22. Suppose that A is a p-SCLI. Then there are constants α j , β j , γ, δ ∈ R, 0 ≤ j ≤ p − 1, depending only on A, so that for an instance F of the form F (z) = Az + b, and an arbitrary set of p initialization poitns z (0) , . . . , z (−p+1) ∈ R n , the iterates z (t) of A satisfy for t ≥ 1 and C j (A) = α j A + β j I n for 0 ≤ j ≤ p − 1 and N(A) = γA + δI n .
In the case of OG with a constant step size η, for F (z) = Az + b, we may rewrite (15) as All lower bounds we prove in this section will apply more generally to any iterative algorithm A whose updates are of the form (78) when restricted to instances F (z) = Az + b.
The remainder of this section is organized as follows. In Section C.1, we prove Theorem 7. In Section C.2 we prove Proposition 8, which is used in the proof of Theorem 7, and Proposition 9, showing that Proposition 8 is tight in a certain sense. In Section C.3 we prove a conjecture of [ASSS15], which is similar in spirit to Proposition 8 and leads to an algorithm-independent version of Theorem 7 (with a weaker quantitative bound). Finally, in Section C.4, we discuss another byproduct of our analysis, namely a lower bound for p-SCLIs for convex function minimization.
C.1 p-SCLI lower bounds for the class F bil n,ℓ,D Notation. For a square matrix A, let ρ(A) be its spectral radius, i.e., the maximum magnitude of an eigenvalue of A. For matrices A 1 ∈ R n1×m1 , A 2 ∈ R n2×m2 , let A 1 ⊗ A 2 ∈ R (n1n2)×(m1m2) be the tensor product (also known as Kronecker product) of A 1 , A 2 .
We will need the following standard lemma: Lemma 23. For a square matrix C and all k ∈ N, we have C k σ ≥ ρ(C) k .
Next we prove Theorem 7, restated below for convenience.
Theorem 7 (restated). Fix ℓ, D > 0, let A be a p-SCLI 14 , and let z (t) denote the tth iterate of A. Then there are constants c A , T A > 0 so that the following holds: For all T ≥ T A , there is some F ∈ F bil n,ℓ,D so that for some initialization z (0) , . . . , z (−p+1) ∈ D D and some T ′ ∈ {T, T + 1, . . . , T + p − 1}, it holds that TGap D2D Proof of Theorem 7. Take F (z) = Az + b, where A, b are of the form shown in (76), with M = ν · I for some ν ∈ (0, ℓ]. Notice that A therefore depends on the choice of ν (which will be specified later), but for simplicity of notation we do not explicitly write this dependence. The outline of the proof is to first eliminate some corner cases in which the iterates of A do not converge and then reduce the statement of Theorem 7 to that of Proposition 8. There are a few different ways to carry out this reduction: we follow the linear algebraic approach of [ASSS15], but an approach of a different flavor using elementary ideas from complex analysis is given in [Nev93, Section 3.7].
Since F ∈ F bil n,ℓ,D , we have that the equilibrium z * = (x * , y * ) ∈ D D satisfies B R n/2 (x * , D)×B R n/2 (y * , D) ⊂ D 2D . Then, from [GPDO20, Eq. (22)], it follows that TGap D2D F (z) ≥ D F (z) for any z ∈ R n . Therefore, to prove Theorem 7 it suffices to show the lower bound F (z (T ′ ) ) ≥ cAℓD √ T . We consider the dynamics of the iterates of A for various choices of z (0) , . . . , z (−p+1) ∈ D D . To do so, we define the block matrices: and the block vectors Then the updates of A as in (78) can be written in the following form, for F (z) = Az + b: Hence Recall that Observation 22 gives us C j (A) = α j · A + β j · I n , and N(A) = γ · A + δ · I n , for some real numbers α j , β j , γ, δ where 0 ≤ j ≤ p − 1.
We now consider several cases: is not invertible for some choice of ν ∈ (0, ℓ] (which determines A as explained above). First suppose that C(A) − I np is not invertible. Note that the row-space of C(A) − I np contains the row-space of the following matrix: If C 0 (A) + · · · + C p−1 (A) − I n is full-rank, then the row-space ofC additionally contains the row-space of I n 0 · · · 0 ∈ R n×np , and thusC, and so C(A)−I would be full-rank. Thus C 0 (A)+· · ·+C p−1 (A)−I n is not full-rank. But we can write: But since M is a nonzero multiple of the identity matrix, if the above matrix is not full-rank, it must be identically 0, i.e., p−1 j=0 C j (A) = I n . Hence p−1 j=0 β j = 1, p−1 j=0 α j = 0. Thus, for any choice of the matrix A ∈ R n×n , if we choose b = 0 (so that F (z) = Az), and if z (0) = · · · = z (−p+1) = z for some z ∈ R n , it holds that for all t ≥ 1, the iterates z (t) of Z satisfy z (t) = z. We now choose M = ℓ · I n/2 and z = z (0) = D/ n/2 · 1 ∈ R n , so that z (0) − A −1 b = z (0) ∈ D D . Then for all t ≥ 0, Similarly, if N(A) is not invertible for some choice of ν ∈ (0, ℓ], then by choice of A we must have that γ = δ = 0, i.e., N(A) = 0 for all choices of ν. Thus, choosing w (0) = 0 and b = D/ n/2 · 1 ∈ D D , and so for all t ≥ 0, F (z (t) ) = F (z (0) ) = b = √ 2D. Thus in this case we get the lower bound for T ≥ T A := ℓ 2 .
p−1 j=0 β j = 1. This case contains the case in which the iterates z (t) of the p-SCLI converge to the true solution −A −1 b for all A, b, and is thus the main nontrivial case (in particular, it is the case in which we use Proposition 8).

C.2 Proof of Propositions 8 and 9
In this section we prove Propositions 8 and 9.
We remark also that the case k ≥ 3 can be dealt with directly, without appealing to Theorem 25: again let w 0 = b(µ), so that (85) holds. Then there exists some kth root u 0 ∈ ∆ of w 0 so that a ′ (0) · u 0 = re iθ for some θ ∈ [−π/3, π/3] and r > 0. Then for sufficiently small u 0 (which can be made arbitrarily small by taking µ ↓ 0).
The polynomials in (86) are closely related to Nesterov's accelerated gradient descent (AGD); we discuss this connection further in Remark 8.
We are not aware of any reference in the literature directly claiming to prove the statement of Conjecture 24. However, we will show two distinct proofs of Conjecture 24: the first is an indirect proof showing how Conjecture 24 may be derived indirectly as a consequence of prior works ([Nev93, AS16]), and the second is a direct proof using basic principles from complex analysis.
Before continuing, we introduce some further notation.
Notation. For a polynomial s(z), write ρ(s) to be the spectral radius of s, i.e., ρ(s) = max{|z| : s(z) = 0} is the maximum magnitude of a root of s. LetĈ = C ∪ {∞} denote the Riemann sphere. For z ∈ C, r > 0, let D(z, r) := {w ∈ C : |w − z| < r} denote the (open) disk of radius r centered at z. Set ∆ = D(0, 1) and H := {z ∈ C : ℑ(z) > 0} to be the upper half-plane (here ℑ(z) denotes the imaginary part of z). We refer the reader to [Ahl79] for further background on complex analysis.
(We use Lemma 26 in (92).) Let S t denote the set of polynomials s t with complex coefficients of degree at most t such that s t (0) = 1. (Note in particular that the polynomials p t defined above belong to S t for each t.) It follows from Theorem 3.6.3, and Example 3. |s t (ν)| 1/t = ℓ/µ − 1 ℓ/µ + 1 .
(In more detail, the quantity on the left-hand-side of (93), which is called the optimal reduction factor of the region [µ, ℓ] in [Nev93] and denoted by η [µ,ℓ] therein, is shown in [Nev93, Theorem 3.6.3] to be equal to e −G(0) , where G : C − [µ, ℓ] → R is the Green's function for the region C − [µ, ℓ]. Then [Nev93, Example 3.8.3] explicitly computes the Green's function and shows that e −G(0) is the quantity on the right-hand-side of (93)).
The desired conclusion follows by taking ǫ ↓ 0, thus completing the proof of Theorem 25. We remark that an alternative approach to establishing (93) without appealing to the heavy machinery of Green's functions is to use [AS16, Lemma 2] directly, which shows that The approach to proving Conjecture 24 described above is unsatisfying in that it first passes a statement about polynomials (namely, Conjecture 24) to a statement about matrices (namely, about lim inf t sup ν∈[µ,ℓ] C(ν) t 1/t σ ), relying on a nontrivial uniform version of Gelfand's formula ([Koz09]), before passing back to a statement about polynomials and using either [AS16] or [Nev93] to establish (93). It is natural to wonder whether there is a direct proof of Conjecture 24 which operates on the polynomials q(z), r(z) directly, without bounding the optimal reduction factor in (93) and constructing the matrices C(ν). We next give such a direct proof of Conjecture 24, which follows from basic facts from complex analysis.
The conclusion of Proposition 29 is known even for non-stationary p-CLIs and without the superfluous 1/ √ p factor (e.g., it follows from Proposition 5 in [ASM + 20]), but our proof is new since it involves Theorem 25, which does not seem to have been previously known in the literature. We are hopeful that Theorem Define, for each t ≥ 0, . . .
We will choose S = ν · I n , for some ν ∈ (0, ℓ] to be chosen later. Thus f (x) − f (x * ) = 1 2ν Sx + b 2 . Next we proceed exactly as in the proof of Theorem 7, with S taking the role of A there. In particular, we define C(S) exactly as in (79), where C j (S) = α j · A + β j · I n , N(S) = γ · S + δ · I n , where α j , β j , γ, δ ∈ R are the constants associated with the p-SCLI A. Cases 1, 2, and 3a of the proof (namely, the ones in which the algorithm does not converge) proceed in exactly the same way and we omit the details.
Remark 8. As in Theorem 7, the lower bound in Proposition 30 involves an algorithm-dependent constant c A due to the reliance on Proposition 8. We remark that the iterates x (t) of gradient descent satisfy f (x (t) ) − f (x * ) ≤ O(ℓD 2 /T ) for any ℓ-smooth convex function f , so Proposition 8 is tight up to the algorithm-dependent constant c A . Nesterov's AGD improves the rate of gradient descent to O(ℓD 2 /T 2 ), but is non-stationary (i.e., requires a changing step size). The polynomials in Proposition 9 (i.e., (9)) showing the necessity of an algorithm-dependent constant in Proposition 8 correspond under the reduction outlined in the proof of Proposition 30 to running Nesterov's AGD with a fixed learning rate. We do not know if such an algorithm (for an appropriate choice of the arbitrary but fixed learning rate) can lead to an arbitrarily large constant factor speedup over the rate O(ℓD 2 /T ) of gradient descent. We believe this is an interesting direction for future work.