#  Time-Aware Ancient Chinese Text Translation and Inference

$\star$Ernie Chang文, $\circ$Yow-Ting Shiue文, $\star$Hui-Syuan Yeh, $\star$Vera
Demberg
$\star$Dept. of Language Science and Technology, Saarland University
$\circ$Dept. of Computer Science, University of Maryland, College Park
<EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

In this paper, we aim to address the challenges surrounding the translation of
ancient Chinese text: (1) The _linguistic gap_ due to the difference in eras
results in translations that are poor in quality, and (2) most translations
are missing the contextual information that is often very crucial to
understanding the text. To this end, we improve upon past translation
techniques by proposing the following: We reframe the task as a _multi-label
prediction task_ where the model predicts both the translation and its
particular era. We observe that this helps to bridge the linguistic gap as
chronological context is also used as auxiliary information. We validate our
framework on a parallel corpus annotated with chronology information and show
experimentally its efficacy in producing quality translation outputs. We
release both the code and the data111https://github.com/orina1123/time-aware-
ancient-text-translation for future research.

00footnotemark: 000footnotetext: 文These authors contributed equally.

##  1 Introduction

The Chinese language inherits a lot of phrases from ancient time Bao-chuan
(2008); Liu (2019) and is spoken by roughly $1.3$ billion native speakers.
However, the language’s ancient variant (or _ancient Chinese_) is mastered by
a few and proved to be a bottleneck in understanding the essence of the
Chinese culture. Building a translation system from the ancient Chinese to the
modern text thus serves a few important purposes: (I) The ancient Chinese is
considered as an essential part of the curriculum in all of the Chinese-
speaking regions222This includes the mainland China, Taiwan, Singapore,
Malaysia, etc. , so an ancient Chinese translation system can be used to
bolster the immediate understanding of ancient texts. (II) Further, the
translation system can help to settle the linguistic debate with regard to the
era of origin of an independent segment of text. This is especially useful for
the identification of a discovered artifacts where carbon dating cannot
pinpoint the exact era, but where their linguistic features can formulate a
clear-cut dynasty or time period.

However, it is not without challenge in constructing such translation systems.
One primary obstacle lies in the extensive timeline where ancient texts can be
derived – one segment of ancient text can come from the Pre-Qin (先秦) era, and
another coming from the Song dynasty (宋朝), which are roughly about $700$ years
apart. This gap witnessed a drastic evolution of linguistic properties where
the usage of phrases became imbued with different meanings. Besides, different
eras often consist of various amounts of available data, and thus the same
translation model training will be exposed to data imbalance, which
complicates the design of the translation systems and limits their
generalizability. On the other hand, past attempts at building such
translation systems yield poor performance that renders them practically
unusable as-is in the practical settings Zhang et al. (2018); Liu et al.
(2019) – these efforts are still largely limited as parallel data is scarce
for some eras.

Recent advances in machine translation and text style transfer/generation
utilize semi-supervised techniques to tackle similar challenges by aligning
latent representations from different styles for the low resource scenarios
Shen et al. (2017); Hu et al. (2017); Rao and Tetreault (2018); Prabhumoye et
al. (2018); Jin et al. (2019); Chang et al. (2020, 2021c, 2020, 2021b, 2021a);
Su et al. (2020). To this end, we aim to bridge this gap that makes the
following contributions:

  * •

We showed that having ancient Chinese text of all eras in a single corpus is
not ideal as they are difficult to model jointly as a single distribution, and
that the additional _chronological context_ helps to improve translation of
ancient Chinese to modern Chinese sentences.

  * •

For future research in this direction, we release our code and parallel data
consisting of annotated _chronological identifiers_ which allow to infer the
approximate era of the written text in the practical settings.

|  Text | Chronological Period
---|---|---
Source (Ancient Chinese) |  孟子曰：道在尔而求诸远，事在易而求之难。 |
Reference |  孟子说：道路在近旁而偏要向远处去寻求，事情本来很容易而偏要向难处下手。 (Menzie said: “The right path is just beside but people take far away ones instead; things are easy but people handle them with difficult ways.”) | pre-qin
System (Modern Chinese) |  孟子说：道理在于尔而求得远方，事情在于易而求得难 。 | pre-qin
Source (Ancient Chinese) |  秦昭王召见，与语，大说之，拜为客卿。 |
Reference |  秦昭王便召见了蔡泽，跟他谈话后，很喜欢他，授给他客卿职位。 (The King of Qin summoned Mr. Ze Cai and, after talking to him, liked him and gave him a government official position for foreigners.) | han
System (Modern Chinese) |  秦昭王召见他，与他谈话，非常高兴，拜他为客卿。 | han
Source (Ancient Chinese) |  太子曰：吾君老矣，非骊姬，寝不安，食不甘。 |
Reference |  太子说：我父亲年老了，没有骊姬将睡不稳、食无味。 (The Prince said: “My father is old. Without this girl, Li, he cannot sleep well or eat well.”) | han
System (Modern Chinese) |  太子说：我国君已经老了，不是骊姬的姬妾，吃不甘。 | han
Table 1: Examples of system output consisting of the _ancient Chinese source_
, _modern Chinese reference_ and the _chronological period prediction_.

##  2 Background

At a fine-grained view, the notion of “ancient Chinese” may not be considered
a single language with a static word-meaning mapping. Therefore, we direct our
efforts toward three particular eras: Pre-Qin (先秦), Han (汉), and Song (宋) to
verify the hypothesis that the chronology of a text directly influences the
word meaning and model performance. In particular, _Pre-Qin_ and _Han_ are
closer chronologically, so we expect their model performances to be closer
than that between _Pre-Qin_ and _Song_ , as was shown in other ancient text
translation Park et al. (2020).

One reason for this difference is the use of polysemous single-character
words, which are highly ambiguous. Some words begin to lose meanings over
time. For example, in ancient Chinese, the word 看(‘kàn’) has many meanings
such as “to visit” and “to listen”, in addition to the major modern meaning,
“to look”.

As the language evolved, vocabulary changed and lexical semantic shift took
place, creating diachronic semantic gaps that may introduce subtle differences
in the understanding of the text. For instance, the earliest known meaning of
“看” is “to look into the distance”. The meaning of “to look at something
closely” emerged during the Han period and eventually became the prominent
meaning of this verb in modern Chinese. In sum, the language change across
time suggests a modeling approach that is aware of when the text was written.

##  3 Task Formulation

We assume two nonparallel datasets $A$ and $M$ of sentences in _Ancient
Chinese (zh-a)_ and _Modern Chinese (zh-m)_ respectively.A parallel dataset
$P$ that contains the pairs of sentences in both variants of text is also
present. The sizes of the three datasets are denoted as $|A|$, $|M|$ and
$|P|$, respectively. As the nonparallel data is abundant but the parallel data
is limited, size $|A|$, $|M|\gg|P|$. The main objective is to convert the
input ancient Chinese text $a$ to its modern variant $m$. This task is akin to
style transfer, or if the text are drastically different, machine translation.
In this paper, we are only concerned with the direction from zh-a to zh-m.
Additionally, we include the prediction of the chronological period of the
ancient text as an auxiliary task.

##  4 Proposed Framework

Our framework translates the given ancient Chinese text (section 4.1) while
providing additional chronological context information (section 4.2) (see
Table 1). We train the _translation model_ in a semi-supervised manner such
that cheap and easy-to-obtain modern Chinese text can be utilized in the
training process. To better select from the pool of generated candidates in a
time-aware way, we use the multi-label prediction model as both the _reranker_
and the _chronology predictor_.The predicted chronological period also
provides users with crucial context for understanding the ancient text.

###  4.1 Semi-Supervised Translation Model

Our sequence-to-sequence model is based on the Transformer Vaswani et al.
(2017) encoder-decoder architecture. Given an input, the encoder first
converts it into an intermediate vector, and then the decoder takes the
intermediate representation as input to generate a target output. In what
follows, we describe the training objectives that allows the translation model
to utilize augmented monolingual data.

#### Semi-Supervised Objectives.

Inspired by the previous work on CycleGANs (Zhu et al., 2017) and dual
learning (He et al., 2016; Chang et al., 2021a, b), our method trains the
initial model in both forward and backward directions, and defines a semi-
supervised optimization objective that combines direct supervision
($L_{supervised}$) and a language model loss ($L_{lm}$) over the parallel data
$P$, and two monolingual corpora $A$ and $M$:

$L=L_{supervised}(P)+L_{lm}(A)+L_{lm}(M)$

where $L_{supervised}(P)$ utilizes the aligned sentence pairs in $P$ to
perform domain alignment, ensuring that the representation of the ancient
Chinese text can be semantically aligned with its modern variant. Moreover,
_the semi-supervised training allows us to augment monolingual modern Chinese_
for language modeling. Empirically, we found that this benefits the forward
translation from zh-a to zh-m and proves to be a viable way for improving the
system.

###  4.2 Multi-Label Prediction

Further, we improve upon the translation model via the use of the _chronology
inference_ and _translation reranking_ via the dual-purpose _multi-label
prediction model_. Specifically, we pretrain a modern Chinese language model
then fine-tune this model in a task-specific manner to help predicting the
chronological period and using it to also rank the translation model’s
predictions.

#### Chronology Inference.

To do so, we first pretrain a large-scale language model on the monolingual
modern Chinese corpus following objectives in Radford et al. (2019) for GPT-2.
This enables the model to be familiarized with the language semantics where
some of which are transferrable to the ancient text. Next, we continue to
train the GPT-2 model to perform conditional task-specific generation by
maximizing the joint probability $p_{\mbox{GPT-2}}(a,m,c)$, where $a$ is the
ancient Chinese text, $m$ is the modern Chinese text, and $c$ represents the
contextual information as the chronological period of the ancient text.
Specifically, for each sentence pair, the ancient Chinese tokens $w^{a}_{i}$,
the modern Chinese tokens $w^{m}_{j}$, and the chronological period are
concatenated into “[zh_a] $w^{a}_{1}\cdots w^{a}_{|a|}$ [zh_m]
$w^{m}_{1}\cdots w^{m}_{|m|}$ [chron] $c$”, and the model is trained to
maximize the probability of this sequence.

#### Quality Estimation for Reranking.

At inference time, we append each of the chronology labels to the translation
outputs, then allow the multi-label prediction model to predict their
qualities. Specifically, the fine-tuned LM computes the negative log loss on
each of the triplets $(a,m^{\prime},c^{\prime})$ from the upstream
_translation model_ by appending _exhaustively_ all possible _chronology
labels_ $c^{\prime}$ to the end of the generated sequence $m^{\prime}$
following the same format as above and selecting the best.

##  5 Dataset Construction

We obtain parallel ancient-modern Chinese sentence pairs, and nonparallel
ancient (zh-a) and modern Chinese (zh-m) sentences from two sources Liu et al.
(2019); Shang et al. (2019). Table 2 summarizes the data we used for the
experiments.

#### Chronology Annotation.

In this paper, we focus on translating ancient prose. There are a total of
28,807 ancient Chinese prose sentences. We annotate each of these sentences
with the Chinese historical period (dynasty) in which it was written.
Specifically, we consider three chronology labels: pre-qin (先秦), han (汉), and
song (宋). The annotation is based on the source of the sentences, i.e., which
ancient book the sentences are taken from. The total number of annotated
sentences for each period is 1,244, 20,460, and 7,103 respectively. This
annotation scheme can be adopted for a larger set of periods when ancient text
of a wider time span is available.

#### Parallel Data.

For the sentences with chronology annotation, we randomly assign 10% sentences
to the development set and test set respectively. The remaining sentences are
used as training data. We further supplement the parallel training data with
4,760 sentences from ancient Chinese poems, each also with a modern Chinese
translation. The final training, development and test set statistics and be
found in Table 2.

#### Nonparallel Data.

We extend the source-side data by including 269,409 more ancient poem
sentences without translation. For extending target-side data, we add 77,687
sentences from modern lyrics, following Shang et al. (2019). The details of
nonparallel data are also shown in Table 2.

|  | # sentences | # characters
---|---|---|---
Nonparallel | zh-a | 269,409 | 4M
| zh-m | 77,687 | 826K
Parallel | Train | 27,807 | (524K, 797K)
| Dev | 2,880 | (59K, 88K)
| Test | 2,880 | (60K, 90K)

Table 2: Statistics of the dataset. For each part of the dataset, the number
of sentences and the (source, target) number of characters are shown.

##  6 Experimental Settings

| BLEU
---|---
Training Objectives | All | pre-qin | han | song
$L_{supervised}$ Liu et al. (2019) | 19.59 | 14.41 | 20.02 | 19.13
$L_{supervised}+L_{lm}(M)$ | 23.05 | 15.97 | 23.32 | 23.17
$L_{supervised}+L_{lm}(M)+L_{lm}(A)$ | 23.15 | 14.15 | 23.34 | 23.72
\+ share decoder embeddings | 24.38 | 15.70 | 24.52 | 24.99
\+ time-aware reranking | 24.51 | 15.50 | 24.62 | 25.24

Table 3: Ancient to modern Chinese translation performance. BLEU scores are
calculated with 1 to 4 character n-grams.

We tokenized both ancient and modern Chinese text by splitting characters. The
vocabulary sizes are 4,824 and 4,600 respectively. We built our model upon the
Fairseq toolkit333https://github.com/pytorch/fairseq. The architecture is
Transformer with about 54M parameters, which largely follows the configuration
of Liu et al. (2019). Translations were generated with beam size 5, and we
consider top 5 candidates for reranking. For the _multi-label prediction
model_ , we adapted existing code444https://github.com/Morizeyao/GPT2-Chinese
to build a GPT-2 Language Model reranker with approximately 82M parameters.
First, we pre-trained the model with 1.2 GB of Chinese Wikipedia text. Then,
we fine-tuned the pre-trained model with the chronologically-annotated
training data. For each ancient-modern sentence pair with chronology
information, we form a text-period query string with the scheme described in
section 4.2. We select the final model according to perplexity computed on the
development set.

##  7 Main Results

Overall, we observe from Table 3 and 4 that the use of the multi-label
prediction model not only allows for better context than pure translation, but
also helps to boost the general performance on the translation tasks.
Moreover, _translations of ancient text chronologically closer to modern
Chinese ( han and song) tend to yield better performances, as the semantic
gaps are generally smaller_. We also demonstrate that the semi-supervised
training which avail of the additional nonparallel text helps to improve the
translation model even further. Specifically, zh-m nonparallel data enhances
the decoder’s ability to generate modern Chinese, while zh-a nonparallel data
may help the encoder to maintain crucial semantic information. We achieved a
BLEU score of $23.15$ in this setting. As the source and target side
vocabularies have a large overlap, we experimented with sharing decoder
embeddings and got +$1.23$ BLEU improvement, which may also serve as an
evidence that there are still ancient components in modern Chinese. Finally,
reranking further boosted the BLEU score to $24.51$.

Period (# test) | Precision | Recall | F1
---|---|---|---
pre-qin (117) | 0.05 | 0.53 | 0.09
han (2043) | 0.85 | 0.57 | 0.68
song (720) | 0.85 | 0.27 | 0.41
Accuracy |  |  | 0.49
Macro avg. | 0.58 | 0.45 | 0.39
Weighted avg. | 0.82 | 0.49 | 0.59

Table 4: Performance of Chronology Inference

Figure 1: Confusion matrix for Chronology Inference

#### Error Analysis.

We perform _human evaluation_ on $100$ randomly sampled output instances and
observe them to be high in _adequacy_ and _fluency_ , $4.06$ and $3.68$
respectively, on a scale of $0$-$5$. This was done by averaging the fluency
and adequacy ratings of three domain experts. Further, we also observe that
the chronology of text impacts the model performance as in Table 3. Leveraging
zh-m nonparallel data is most helpful for translating text from the song
period, which is much closer to modern Chinese compared to the text from the
other two periods. Further, from Figure 1 we observe that the chronology
inference depends very much on the _data scarcity_ and the _closeness_ of
chronological periods. On the Chinese historical timeline, han is very close
to pre-qin, but han and song are more separated. Another source of difficulty
is that ancient Chinese writings tend to quote a considerable amount of text
written in previous time periods. For example, a history book written in the
song period may inherit narratives written in pre-qin and han for the history
before han. As a result, it is challenging to perform chronology inference
based solely on the linguistic properties of individual sentences.
Nevertheless, chronological inference can still provide useful signals for the
translation model to better capture semantic differences across time.

##  8 Conclusion

In this paper, we present a framework that translates ancient Chinese texts
into its modern correspondence in low resource scenarios with very little
parallel data and a larger set of nonparallel sentences without ancient-modern
alignment information. We display the importance and usefulness of chronology
inference as an auxiliary task that hints at potential diachronic semantic
gaps. We hope to extend this research to further model additional contextual
information about each era.

## Acknowledgements

This research was funded in part by the German Research Foundation (DFG) as
part of SFB 248 “Foundations of Perspicuous Software Systems”. We sincerely
thank the anonymous reviewers for their insightful comments that helped us to
improve this paper.

## References

  * Bao-chuan (2008) LI Bao-chuan. 2008.  Illustrations of antique meanings of the chinese phrases.  _Journal of Radio & TV University (Philosophy & Social Sciences)_, 3.
  * Chang et al. (2020) Ernie Chang, Jeriah Caplinger, Alex Marin, Xiaoyu Shen, and Vera Demberg. 2020.  Dart: A lightweight quality-suggestive data-to-text annotation tool.  _arXiv preprint arXiv:2010.04141_.
  * Chang et al. (2021a) Ernie Chang, Vera Demberg, and Alex Marin. 2021a.  Jointly improving language understanding and generation with quality-weighted weak supervision of automatic labeling.  _Proceedings of EACL 2021_.
  * Chang et al. (2021b) Ernie Chang, Xiaoyu Shen, Dawei Zhu, Vera Demberg, and Hui. Su. 2021b.  Neural data-to-text generation with lm-based text augmentation.  _Proceedings of EACL 2021_.
  * Chang et al. (2021c) Ernie Chang, Hui-Syuan Yeh, and Vera Demberg. 2021c.  Does the order of training samples matter? improving neural data-to-text generation with curriculum learning.  _Proceedings of EACL 2021_.
  * He et al. (2016) Di He, Yingce Xia, Tao Qin, Liwei Wang, Nenghai Yu, Tie-Yan Liu, and Wei-Ying Ma. 2016.  Dual learning for machine translation.  In _Advances in Neural Information Processing Systems_ , pages 820–828.
  * Hu et al. (2017) Zhiting Hu, Zichao Yang, Xiaodan Liang, Ruslan Salakhutdinov, and Eric P Xing. 2017\.  Toward controlled generation of text.  In _Proceedings of the 34th International Conference on Machine Learning-Volume 70_ , pages 1587–1596. JMLR. org.
  * Jin et al. (2019) Zhijing Jin, Di Jin, Jonas Mueller, Nicholas Matthews, and Enrico Santus. 2019.  Unsupervised text style transfer via iterative matching and translation.  _arXiv preprint arXiv:1901.11333_.
  * Liu et al. (2019) Dayiheng Liu, Kexin Yang, Qian Qu, and Jiancheng Lv. 2019.  Ancient–modern chinese translation with a new large training dataset.  _ACM Transactions on Asian and Low-Resource Language Information Processing (TALLIP)_ , 19(1):1–13.
  * Liu (2019) Yu Liu. 2019.  现代汉语常用文言虚词的语块教学 [formulaic language instruction of classical grammatical words in modern chinese].  _Chinese as a Second Language. The journal of the Chinese Language Teachers Association, USA_ , 54(2):122–144.
  * Park et al. (2020) Chanjun Park, Chanhee Lee, Yeongwook Yang, and Heuiseok Lim. 2020.  Ancient korean neural machine translation.  _IEEE Access_ , 8:116617–116625.
  * Prabhumoye et al. (2018) Shrimai Prabhumoye, Yulia Tsvetkov, Ruslan Salakhutdinov, and Alan W Black. 2018\.  Style transfer through back-translation.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 866–876. Association for Computational Linguistics.
  * Radford et al. (2019) Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. 2019.  Language models are unsupervised multitask learners.  _OpenAI Blog_ , 1(8).
  * Rao and Tetreault (2018) Sudha Rao and Joel Tetreault. 2018.  Dear sir or madam, may i introduce the gyafc dataset: Corpus, benchmarks and metrics for formality style transfer.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)_ , pages 129–140. Association for Computational Linguistics.
  * Shang et al. (2019) Mingyue Shang, Piji Li, Zhenxin Fu, Lidong Bing, Dongyan Zhao, Shuming Shi, and Rui Yan. 2019.  Semi-supervised text style transfer: Cross projection in latent space.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 4937–4946, Hong Kong, China. Association for Computational Linguistics.
  * Shen et al. (2017) Tianxiao Shen, Tao Lei, Regina Barzilay, and Tommi Jaakkola. 2017.  Style transfer from non-parallel text by cross-alignment.  In _Advances in neural information processing systems_ , pages 6830–6841.
  * Su et al. (2020) Hui Su, Xiaoyu Shen, Zhou Xiao, Zheng Zhang, Ernie Chang, Cheng Zhang, Cheng Niu, and Jie Zhou. 2020.  Moviechats: Chat like humans in a closed domain.  In _Proceedings of EMNLP 2020_ , pages 6605–6619.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  In _Advances in neural information processing systems_ , pages 5998–6008.
  * Zhang et al. (2018) Zhiyuan Zhang, Wei Li, and Xu Sun. 2018.  Automatic transferring between ancient chinese and contemporary chinese.  _arXiv preprint arXiv:1803.01557_.
  * Zhu et al. (2017) Jun-Yan Zhu, Taesung Park, Phillip Isola, and Alexei A Efros. 2017.  Unpaired image-to-image translation using cycle-consistent adversarial networks.  In _Proceedings of the IEEE international conference on computer vision_ , pages 2223–2232.


# Superconductivity and normal-state properties of kagome metal RbV3Sb5 single
crystals

Qiangwei Yin†, Zhijun Tu†, Chunsheng Gong†, Yang Fu, Shaohua Yan, and Hechang
Lei<EMAIL_ADDRESS>Department of Physics and Beijing Key Laboratory of Opto-
electronic Functional Materials $\&$ Micro-nano Devices, Renmin University of
China, Beijing 100872, China

###### Abstract

We report the discovery of superconductivity and detailed normal-state
physical properties of RbV3Sb5 single crystals with V kagome lattice. RbV3Sb5
single crystals show a superconducting transition at $T_{c}\sim$ 0.92 K.
Meanwhile, resistivity, magnetization and heat capacity measurements indicate
that it exhibits anomalies of properties at $T^{*}\sim$ 102 - 103 K, possibly
related to the formation of charge ordering state. When $T$ is lower than
$T^{*}$, the Hall coefficient $R_{\rm H}$ undergoes a drastic change and sign
reversal from negative to positive, which can be partially explained by the
enhanced mobility of hole-type carriers. In addition, the results of quantum
oscillations show that there are some very small Fermi surfaces with low
effective mass, consistent with the existence of multiple highly dispersive
Dirac band near the Fermi energy level.

Two-dimensional (2D) kagome lattice composed of corner-sharing triangles and
hexagons is one of the most studied systems in the last decades due to its
unique structural feature. On the one hand, if only the spin degree of freedom
is considered, insulating magnetic kagome materials can host some exotic
magnetism ground states, like quantum spin liquid state, because of the nature
of strongly geometrical frustration for kagome lattice Balents ; Shores ;
HanTH ; FuM . On the other hand, when the charge degree of freedom becomes
dominant (partial filling), the band topology starts to manifest its features
in kagome metals, such as nontrivial Dirac points and flat band in the band
structure KangM ; LiuZ ; KangM2 . More interestingly, when both of spin and
charge degrees of freedom exist, many of exotic phenomena appear in the
correlated magnetic kagome metals. For example, in ferromagnetic Fe3Sn2 and
TbMn6Sn6 kagome metals, due to the spin orbital coupling and broken of time
reversal symmetry, the Chern gap can be opened at the Dirac point, leading to
large anomalous Hall effect (AHE), topological edge state and large magnetic-
field tunability YeL ; YinJX ; YinJX2 . Moreover, antiferromagnetic Mn3Sn and
ferromagnetic Co3Sn2S2 kagome metals exhibit large intrinsic AHE, which is
related to the existence of Weyl node points in these materials Kuroda ; LiuE
; WangQ .

Besides the intensively studied magnetic kagome metals, other correlation
effects and ordering states in partially filled kagome lattice have also
induced great interests. Theoretical studies suggest that the doped kagome
lattice could lead to unconventional superconductivity Balents ; Anderson ; Ko
; WangWS ; Kiesel . Especially, when the kagome lattice is filled near van
Hove filling, the Fermi surface (FS) is perfectly nested and has saddle points
on the $M$ point of Brillouin zone (BZ) WangWS . Depends on the variations of
on-site Hubbard interaction $U$ and Coulomb interaction on nearest-neighbor
bonds $V$, the system can develop different ground states, including
unconventional superconductivity, ferromagnetism, charge bond order and charge
density wave (CDW) order and so on WangWS ; Kiesel . However, the realizations
of superconducting and charge ordering states are still scarce in kagome
metals.

In very recent, a novel family of kagome metals AV3Sb5 (A = K, Rb and Cs) was
discovered Ortiz1 . Among them, KV3Sb5 and CsV3Sb5 exhibit superconductivity
with transition temperature $T_{c}=$ 0.93 and 2.5 K, respectively Ortiz2 ;
Ortiz3 . The proximity-induced spin-triplet superconductivity was also
observed in Nb/KV3Sb5 devices WangY . More importantly, theoretical
calculations and angle-resolved photoemission spectroscopy (ARPES) demonstrate
that there are several Dirac nodal points near the Fermi energy level ($E_{\rm
F}$) with a non-zero $Z_{2}$ topological invariant in KV3Sb5 and CsV3Sb5
Ortiz1 ; Ortiz2 ; Ortiz3 ; YangSY . Moreover, AV3Sb5 exhibits transport and
magnetic anomalies at $T^{*}\sim$ 80 K - 110 K Ortiz1 ; Ortiz2 ; Ortiz3 . The
X-ray diffraction (XRD) and scanning tunnelling microscopy (STM) measurements
on KV3Sb5 and CsV3Sb5 indicate that there is a 2$\times$2 superlattice
emerging below $T^{*}$, i.e., the formation of charge order (CDW-like state)
Ortiz2 ; JiangYX . Furthermore, the STM spectra show that this charge order
has a chiral anisotropy, which can be tuned by magnetic field and may lead to
the anomalous Hall effect (AHE) at low temperature even KV3Sb5 does not
exhibit magnetic order or local moments YangSY ; JiangYX ; Kenney .

Motivated by these studies, in this work, we carried out a comprehensive study
on physical properties of RbV3Sb5 single crystals. We find that RbV3Sb5 shows
a superconducting transition at $T_{c}\sim$ 0.92 K, which coexist with the
anomalies of properties at $T^{*}\sim$ 102 - 103 K. This could be related to
the emergence of charge ordering state. Below $T^{*}$, the transport
properties change significantly, possibly rooting in the dramatic changes of
electronic structure due to the formation of charge order. Furthermore, the
analysis of low-temperature quantum oscillations indicates that there are
small Fermi surfaces (FSs) with low effective mass in RbV3Sb5, revealing the
existence of highly dispersive bands near the Fermi energy level $E_{\rm F}$.

Single crystals of RbV3Sb5 were grown from Rb ingot (purity 99.75%), V powder
(purity 99.9%) and Sb grains (purity 99.999%) using the self-flux method
Ortiz2 . The eutectic mixture of RbSb and Rb3Sb7 is mixed with VSb2 to form a
composition with 50 at.% RbxSby and 50 at.% VSb2 approximately. The mixture
was put into an alumina crucible and sealed in a quartz ampoule under partial
argon atmosphere. The sealed quartz ampoule was heated to 1273 K for 12 h and
soaked there for 24 h. Then it was cooled down to 1173 K at 50 K/h and further
to 923 K at a slowly rate. Finally, the ampoule was taken out from the furnace
and decanted with a centrifuge to separate RbV3Sb5 single crystals from the
flux. Except sealing and heat treatment procedures, all of other preparation
processes were carried out in an argon-filled glove box in order to prevent
the reaction of Rb with air and water. The obtained crystals have a typical
size of 2 $\times$ 2 $\times$ 0.02 mm3. RbV3Sb5 single crystals are stable in
the air. XRD pattern was collected using a Bruker D8 X-ray diffractometer with
Cu $K_{\alpha}$ radiation ($\lambda=$ 0.15418 nm) at room temperature. The
elemental analysis was performed using the energy-dispersive X-ray
spectroscopy (EDX). Electrical transport and heat capacity measurements were
carried out in a Quantum Design physical property measurement system
(PPMS-14T). The longitudinal and Hall electrical resistivity were measured
using a five-probe method and the current flows in the $ab$ plane of the
crystal. The Hall resistivity was obtained from the difference in the
transverse resistivity measured at the positive and negative fields in order
to remove the longitudinal resistivity contribution due to the voltage probe
misalignment, i.e.,
$\rho_{yx}(\mu_{0}H)=[\rho_{yx}(+\mu_{0}H)-\rho_{yx}(-\mu_{0}H)]/2$. The
$c$-axial resistivity was measured by attaching current and voltage wires on
the opposite sides of the plate-like crystal. Magnetization measurements were
performed in a Quantum Design magnetic property measurement system (MPMS3).

Figure 1: (a) Crystal structure of RbV3Sb5. The big green, small red, medium
blue and cyan balls represent Rb, V, Sb1 and Sb2 sites, respectively. (b) XRD
pattern of a RbV3Sb5 single crystal. Inset: photo of typical RbV3Sb5 single
crystals on a 1 mm grid paper.

As shown in the left panel of Fig. 1(a), RbV3Sb5 has a layered structure with
hexagonal symmetry (space group $P6/mmm$, No. 191). It consists of Rb layer
and V-Sb slab stacking along $c$ axis alternatively, isostructural to KV3Sb5
and CsV3Sb5 Ortiz1 . The key structural ingredient of this material is two-
dimensional (2D) kagome layer formed by the V atoms in the V-Sb slab (right
panel of Fig. 1(a)). There are two kinds of Sb sites and the Sb atoms at Sb1
site occupy at the centers of V hexagons when another Sb atoms at Sb2 site
locate below and above the centers of V triangles, forming graphene-like
hexagon layers. The XRD pattern of a RbV3Sb5 single crystal (Fig. 1(b))
reveals that the crystal surface is parallel to the $(00l)$-plane. The
estimated $c$-axial lattice constant is about 9.114 Å, close to previously
reported values Ortiz1 . The thin-plate-like crystals (inset of Fig. 1(b)) are
also consistent with the layered structure of RbV3Sb5. The measurement of EDX
by examination of multiple points on the crystals gives the atomic ratio of Rb
: V : Sb = 0.90(6) : 3 : 5.07(4) when setting the content of V as 3. The
composition of Rb is slightly less than 1, indicating that there may be small
amount of Rb deficiencies in the present RbV3Sb5 crystals.

Fig. 2(a) exhibits the temperature dependence of in-plane resistivity
$\rho_{ab}(T)$ and $c$-axial resistivity $\rho_{c}(T)$ of RbV3Sb5 single
crystal from 2 K to 300 K. The zero-field $\rho_{ab}(T)$ exhibits a metallic
behavior in the measured temperature range and the residual resistivity ratio
(RRR), defined as $\rho_{ab}$(300 K)/$\rho_{ab}$(2 K), is about 44, indicating
the high quality of crystals. At $T^{*}\sim$ 103 K, the $\rho_{ab}(T)$ shows
an inflection point and it is related to the onset of charge ordering
transition Ortiz2 ; JiangYX . It should be noted that the $T^{*}$ is higher
than those in KV3Sb5 and CsV3Sb5 Ortiz2 ; Ortiz3 , implying that the
relationship between $T^{*}$ and the lattice parameters (or ionic radius of
alkali metal) is not monotonic. At $\mu_{0}H=$ 14 T, $\rho_{ab}(T)$ is
insensitive to magnetic field when $T>T^{*}$ but the significant
magnetoresistance (MR) appears gradually below $T^{*}$. On the other hand, the
$\rho_{c}(T)$ has a much larger absolute value than the $\rho_{ab}(T)$. The
ratio of $\rho_{c}/\rho_{ab}$ is about 7 at 300 K and increases to about 33
when temperature is down to 2 K, manifesting a significant 2D nature of
RbV3Sb5. However this anisotropy is smaller than that in CsV3Sb5, which could
be partially ascribed to the smaller interlayer spacing between two V-Sb slabs
Ortiz2 . More importantly, in contrast to $\rho_{ab}(T)$, the $\rho_{c}(T)$
shows a remarkable upturn starting from $T^{*}$ with a maximum at about 97 K
and this behavior is distinctly different from that in CsV3Sb5Ortiz2 . It
suggests that the $\textbf{q}_{\rm CDW}$ in RbV3Sb5 might have a $c$-axial
component, leading to the significantly gapped FS along the $k_{z}$ direction.
Similar behavior has also been observed in PdTeI with CDW vector
$\textbf{q}_{\rm CDW}$ = (0, 0, 0.396) LeiHC  and GdSi with spin density wave
(SDW) vector $\textbf{q}_{\rm SDW}$ = (0, 0.483, 0.092) FengY . Fig. 2(b)
exhibits the $\rho_{ab}(T)$ as a function of temperature below 1.3 K. It can
be seen that there is a sharp resistivity drop appearing in the $\rho_{ab}(T)$
curve at zero field and it corresponds to the superconducting transition. The
onset superconducting transition temperature $T_{c,\rm onset}$ determined from
the cross point of the two lines extrapolated from the high-temperature normal
state and the low-temperature superconducting state is 0.92 K with the
transition width $\Delta T_{c}=$ 0.17 K. This $T_{c}$ is lower than that of
CsV3Sb5 ($T_{c}\sim$ 2.5 K) but very close to that of KV3Sb5 ($T_{c}\sim$ 0.93
K) Ortiz2 ; Ortiz3 .

Figure 2: (a) Temperature dependence of $\rho_{ab}(T)$ and $\rho_{c}(T)$ at
zero field and 14 T between 2 K and 300 K. (b) Temperature dependence of zero-
field $\rho_{ab}(T)$ below 1.3 K. (c) Temperature dependence of $M(T)$ at
$\mu_{0}H=$ 1 T for $H\parallel c$ with ZFC and FC modes. (d) Temperature
dependence of $C_{p}(T)$ at zero field between 2 K and 117 K. Inset: $C_{p}/T$
vs. $T^{2}$ at low temperature region. The red solid line represents the
linear fit using the formula $C_{p}/T=\gamma+\beta T^{2}$.

The charge ordering transition also has a remarkable influence on the magnetic
property of RbV3Sb5. As shown in Fig. 2(c), the magnetization $M(T)$ curve
exhibits a relatively weak temperature dependence with a small absolute value
above $T^{*}$, reflecting the Pauli paramagnetism of RbV3Sb5. In contrast,
when $T<T^{*}$, there is a sharp drop in the $M(T)$ curve because of the
decreased carrier density originating from the partially gapped FS by the
charge ordering transition. In addition, the nearly overlapped zero-field-
cooling (ZFC) and field-cooling (FC) $M(T)$ curves also suggest that this
anomaly should be due to certain density wave transition not an
antiferromagnetic one. Fig. 2(d) shows the temperature dependence of heat
capacity $C_{p}(T)$ of RbV3Sb5 single crystals measured between $T=$ 2 and 117
K at zero field. It can be seen that there is a jump at $\sim$ 102 K, in
agreement with the $T^{*}$ obtained from resistivity and magnetization
measurements. The jump in $C_{p}(T)$ curve of RbV3Sb5 is similar to those of
KV3Sb5 and CsV3Sb5 Ortiz1 ; Ortiz2 ; Ortiz3 , suggesting the same origin of
this anomaly of heat capacity from the charge ordering transition. The
electronic specific heat coefficient $\gamma$ and phonon specific heat
coefficient $\beta$ can be obtained from the linear fit of low-temperature
heat capacity using the formula $C_{p}/T=\gamma+\beta T^{2}$ (inset of Fig.
2(d)). The fitted $\gamma$ and $\beta$ is 17(1) mJ mol-1 K-2 and 3.63(2) mJ
mol-1 K-4, respectively. The latter one gives the Debye temperature
$\Theta_{D}=$ 168.9(3) K using the formula
$\Theta_{D}=(12\pi^{4}N\rm{R}/5\beta)^{1/3}$, where $N$ is the number of atoms
per formula unit and R is the gas constant. The electron-phonon coupling
$\lambda_{e-ph}$ can be estimated with the values of $\Theta_{D}$ and $T_{c}$
using McMillan’s formula McMillan ,

$\lambda_{e-ph}=\frac{1.04+\mu^{\ast}\ln(\Theta_{D}/1.45T_{c})}{(1-0.62\mu^{\ast})\ln(\Theta_{D}/1.45T_{c})-1.04}$
(1)

where $\mu^{\ast}$ is the repulsive screened Coulomb potential and is usually
between 0.1 and 0.15. Assuming $\mu^{\ast}=$ 0.13, the calculated
$\lambda_{e-ph}$ is about 0.489, implying that RbV3Sb5 is a weakly coupled BCS
superconductor Allen .

Figure 3: (a) and (b) Field dependence of MR and $\rho_{yx}(T,\mu_{0}H)$ at
various temperatures up to 9 T. Inset of (a) shows the field dependence of MR
at 2 K with the field up to 14 T. The red line represents the fit using the
formula MR $=A(\mu_{0}H)^{\alpha}$. (c) Temperature dependence o $R_{\rm
H}(T)$ obtained from the linear fits of $\rho_{yx}(T,\mu_{0}H)$ curves. (d)
Temperature dependence of $R_{\rm H}/\rho_{ab}(0)$. Inset: the enlarged part
of $R_{\rm H}/\rho_{ab}(0)$ near $T^{*}$ and the vertical red line represents
the temperature of $T^{*}$.

The MR [$=(\rho_{ab}(\mu_{0}H)-\rho_{ab}(0))/\rho_{ab}(0)$] of RbV3Sb5 is
negligible above $T^{*}$ and increases gradually below $T^{*}$ (Fig. 3(a)),
consistent with the $\rho_{ab}(T)$ data (Fig. 2(a)). At low temperature, the
MR does not saturate up to 14 T and the Shubnikov-de Haas (SdH) quantum
oscillations (QOs) can be clearly observed at low-temperature and high-field
region (inset of Fig. 3(a)). The MR at 2K can be fitted using the formula MR
$=A(\mu_{0}H)^{\alpha}$ with $\alpha=$ 1.001(5) (inset of Fig. 3(a)), such
linear behavior of MR extends to $T^{*}$, especially at $\mu_{0}H>$ 3 T. Fig.
3(b) shows the field dependence of Hall resistivity $\rho_{yx}(T,\mu_{0}H)$ at
several typical temperatures. At high temperature, the values of
$\rho_{yx}(T,\mu_{0}H)$ are negative with nearly linear dependence on field.
When decreasing temperature below 50 K, the $\rho_{yx}(T,\mu_{0}H)$ becomes
positive but the linear field dependence is almost unchanged at high-field
region. Similar to the MR curves, the SdH QOs appear at low temperatures. The
Hall coefficient $R_{\rm H}$ obtained from the linear fits of
$\rho_{yx}(T,\mu_{0}H)$ curves are shown in Fig. 3(c). The strong temperature
dependence of $R_{\rm H}$ implies that RbV3Sb5 is a multi-band metal,
consistent with theoretical calculations and ARPES measurements of KV3Sb5 and
CsV3Sb5 Ortiz1 ; Ortiz2 ; YangSY . At high temperature, the negative $R_{\rm
H}$ suggests that the electron-type carriers are dominant, which could
originate from the electron pockets around $\Gamma$ and $K$ points of BZ
Ortiz1 ; Ortiz2 ; YangSY . The most remarkable feature is that the weakly
temperature dependent $R_{\rm H}$ starts to decrease rapidly below $T^{*}$ and
changes its sign to positive at about 40 K. Such behavior is very similar to
the typical CDW materials NbSe2 and TaSe2 Naito , and SDW system GdSi FengY .
Both theory and STM results indicate that the $\textbf{q}_{\rm CDW}$ connects
the $M$ point when the Fermi level is close to the van Hove filling as in the
case of AV3Sb5 JiangYX ; WangWS ; Kiesel ; Ortiz1 ; Ortiz2 . Moreover, there
are a band with van Hove singularity and a pair of Dirac-cone like bands near
the $M$ point JiangYX , which can form hole pockets especially when the
$E_{\rm F}$ shifts downward slightly due to the slight Rb deficiency Ortiz1 ;
Ortiz2 . Therefore, the charge order may lead to the gap opening of hole bands
not electron ones. It seems very peculiar that the $\rho_{ab}(T)$ becomes
smaller with positive $R_{\rm H}$ in the charge ordering state even though the
portions of hole-type FSs are gapped. Here, we explain this phenomenon in the
framework of two-band model. According to the two band model at low-field
region Ziman ,

$R_{\rm
H}=\frac{\rho_{yx}}{\mu_{0}H}=\frac{n_{h}\mu_{h}^{2}-n_{e}\mu_{e}^{2}}{e(n_{h}\mu_{h}+n_{e}\mu_{e})^{2}}$
(2)

where $\mu_{e,h}$ and $n_{e,h}$ are the mobilities and densities of electron-
and hole-type carriers, respectively. Because of zero-field
$\rho_{ab}(0)=1/\sigma_{ab}(0)=1/(n_{h}e\mu_{h}+n_{e}e\mu_{e})$, it has,

$R_{\rm
H}/\rho_{ab}(0)=\frac{n_{h}\mu_{h}^{2}-n_{e}\mu_{e}^{2}}{n_{h}\mu_{h}+n_{e}\mu_{e}}$
(3)

The derived $R_{\rm H}/\rho_{ab}(0)$ with the dimension of mobility is shown
in Fig. 3(d). According to eq. (3), if the $n_{e}\mu_{e}^{2}$ is much larger
than the $n_{h}\mu_{h}^{2}$ which should be the case above $T^{*}$, the
$R_{\rm H}/\rho_{ab}(0)$ is negative and the $1/|R_{\rm H}|$ will be close to
$n_{e}$, which is about 1.6$\times$1022 cm-3 at 300 K. On the other hand, when
the $T$ is just below $T^{*}$, the $\mu_{h}$ may still not increase remarkably
and the $n_{h}$ decreases continuously because the FS reconstruction has not
finished yet, manifesting from the drops of $M(T)$ curves shown in Fig. 2(c)
This would result in an even negative value of $R_{\rm H}/\rho_{ab}(0)$, which
can be clearly seen in the inset of Fig. 3(d). In contrast, when the $T$ is
far below $T^{*}$ ($<$ 70 K), the $n_{h}$ becomes insensitive to temperature
and the $\mu_{h}$ may be much larger than the $\mu_{e}$ because both of
electron and hole mobilities have the temperature dependence $BT^{-n}$ with
different $B$ and $n$ values. It will lead to a sign reversal of $R_{\rm
H}/\rho_{ab}(0)$ to positive even the $n_{h}$ is smaller than the value above
$T^{*}$. This also explains the even smaller $\rho_{ab}(T)$ below $T^{*}$.
Since the strongly CDW-like coupled portions of FSs near $M$ point may play a
negative role in conductivity above $T^{*}$, the carrier scattering around
this area can be effectively reduced when entering charge ordering state, and
thus the $\mu_{h}$ can enhance significantly Valla . Similar discussion about
the sign change of $R_{\rm H}$ has been developed by Ong for 2D multiband
system and applied to Sr2RuO4 and CDW material 2H-NbSe2 Ong ; Mackenzie ; LiL
.

Figure 4: (a) SdH QOs
$\Delta\rho_{ab}=\rho_{ab}-\left\langle\rho_{ab}\right\rangle$ as a function
of 1/($\mu_{0}H$) at various temperatures. (b) FFT spectra of the QOs between
4 T and 14 T at various temperatures. (c) The temperature dependence of FFT
amplitude of $F_{\alpha}$ frequency. The solid line is the fit using the LK
formula to extract the effective mass.

Analysis of SdH QOs provides insight on the features of FSs and carriers
further. After subtracting the slowly changed part of $\rho_{ab}(\mu_{0}H)$
($\equiv\left\langle\rho_{ab}\right\rangle$), the oscillation parts of
resistivity $\Delta\rho_{ab}=\rho_{ab}-\left\langle\rho_{ab}\right\rangle$ as
a function of 1/($\mu_{0}H$) for $H\|c$ at several representative temperatures
are shown in Fig. 4(a). The amplitudes of QOs decrease with increasing
temperature or decreasing field, but still observable at 30 K. The fast
Fourier transform (FFT) spectra of the QOs reveal two principal frequencies
$F_{\alpha}=$ 33.5 T and $F_{\beta}=$ 117.2 T (Fig. 4(b)). Both of them are
slightly smaller than those in KV3Sb5 YangSY , indicating RbV3Sb5 has smaller
extremal orbits of FSs than KV3Sb5. According to the Onsager relation
$F=(\hbar/2\pi e)A_{F}$ where $A_{F}$ is the area of extremal orbit of FS, the
determined $A_{F}$ is 0.0032 and 0.011 Å-2 for $\alpha$ and $\beta$ extremal
orbits, respectively. These $A_{F}$s are very small, taking only about 0.0934
% and 0.321 % of the whole area of BZ in the $k_{x}-k_{y}$ plane when taking
the lattice parameter $a=$ 5.4715 Å Ortiz1 . The effective mass $m^{*}$ can be
extracted from the temperature dependence of the amplitude of FFT peak using
the Lifshitz-Kosevich (LK) formula,

$\Delta\rho_{ab}\propto\frac{X}{\sinh X}$ (4)

where $X=2\pi^{2}k_{B}T/\hbar\omega_{c}=14.69m^{*}/\mu_{0}H_{\rm avg}$ with
$\hbar\omega_{c}$ being the cyclotron frequency and $\mu_{0}H_{\rm avg}$ (= 9
T) being the average value of the field window used for the FFT of QOs
Shoenberg ; Rhodes . As shown in Fig. 4(c), the temperature dependence of FFT
amplitude of $F_{\alpha}$ can be fitted very well using eq. (4) and the
obtained $m^{*}$ is 0.091(2) $m_{e}$, where $m_{e}$ is the bare electron mass.
This value is even smaller than that in KV3Sb5 (0.125 $m_{e}$ for the $\alpha$
orbit) YangSY . The small extremal cross sections of FSs accompanying with
such light $m^{*}$ could be related to the highly dispersive bands near either
$M$ point or along the $\Gamma-K$ path of BZ Ortiz1 ; Ortiz2 ; YangSY ;
JiangYX .

In summary, we carried out the detailed study on physical properties of
RbV3Sb5 single crystals grown by the self-flux method. RbV3Sb5 single crystals
exhibit a superconducting transition at $T_{c,\rm onset}$ = 0.92 K with a
weakly coupling strength, accompanying with anomalies of properties at
$T^{*}\sim$ 102 - 103 K. The high-temperature anomaly could be related to the
formation of charge ordering state and it results in the sign change of
$R_{\rm H}$, which can be partially ascribed to the enhancement of mobility
for hole-type carriers due to the reduced carrier scattering by the gapping of
strongly CDW-like coupled portions of FSs. Furthermore, there are some very
small FSs with rather low $m^{*}$, indicating the existence of highly
dispersive bands near $E_{\rm F}$ in RbV3Sb5. Moreover, due to the similar
electronic structure of RbV3Sb5 to KV3Sb5 and CsV3Sb5 Ortiz1 , RbV3Sb5 should
also be a candidate of $Z_{2}$ topological metal. Therefore, the V-based
kagome metals AV3Sb5 provide a unique platform to explore the interplay
between nontrivial band topology, electronic correlation and possible
unconventional superconductivity.

This work was supported by National Natural Science Foundation of China (Grant
No. 11822412 and 11774423), Ministry of Science and Technology of China (Grant
No. 2018YFE0202600 and 2016YFA0300504), Beijing Natural Science Foundation
(Grant No. Z200005), and Fundamental Research Funds for the Central
Universities and Research Funds of Renmin University of China (RUC) (Grant No.
18XNLG14 and 19XNLG17).

† Q.W.Y, Z.J.T. and C.S.G. contributed equally to this work.

## References

  * (1) L. Balents, Nature 464, 199-208 (2010).
  * (2) M. P. Shores, E. A. Nytko, B. M. Bartlett, and D. G. Nocera, J. Am. Chem. Soc. 127, 13462-13463 (2005).
  * (3) T.-H. Han, J. S. Helton, S. Chu, D. G. Nocera, J. A. Rodriguez-Rivera, C. Broholm, and Y. S. Lee, Nature 492, 406-410 (2012).
  * (4) M. Fu, T. Imai, T.-H. Han, and Y. S. Lee, Science 350, 655-658 (2015).
  * (5) M. Kang, L. Ye, S. Fang, J.-S. You, A. Levitan, M. Han, J. I. Facio, C. Jozwiak, A. Bostwick, E. Rotenberg, M. K. Chan, R. D. McDonald, D. Graf, K. Kaznatcheev, E. Vescovo, D. C. Bell, E. Kaxiras, J. van den Brink, M. Richter, M. P. Ghimire, J. G. Checkelsky, and R. Comin,, Nat. Mater. 19, 163-169 (2020).
  * (6) Z. Liu, M. Li, Q. Wang, G. Wang, C. Wen, K. Jiang, X. Lu, S. Yan, Y. Huang, D. Shen, J.-X. Yin, Z. Wang, Z. Yin, H. Lei, and S. Wang, Nat. Commun. 11, 4002 (2020).
  * (7) M. Kang, S. Fang, L. Ye, H. C. Po, J. Denlinger, C. Jozwiak, A. Bostwick, E. Rotenberg, E. Kaxiras, J. G. Checkelsky, and R. Comin, Nat. Commun. 11, 4004 (2020).
  * (8) L. Ye, M. Kang, J. Liu, F. von Cube, C. R. Wicker, T. Suzuki, C. Jozwiak, A. Bostwick, E. Rotenberg, D. C. Bell, L. Fu, R. Comin, and J. G. Checkelsky, Nature 555, 638-642 (2018).
  * (9) J.-X. Yin, W. Ma, T. A. Cochran, X. Xu, S. S. Zhang, H.-J. Tien, N. Shumiya, G. Cheng, K. Jiang, B. Lian, Z. Song,G. Chang, I. Belopolski, D. Multer, M. Litskevich, Z.-J. Cheng, X. P. Yang, B. Swidler, H. Zhou, H. Lin, T. Neupert, Z. Wang, N. Yao, T.-R. Chang, S. Jia, and M. Z. Hasan, Nature 583, 533-536 (2020).
  * (10) J.-X. Yin, S. S. Zhang, H. Li, K. Jiang, G. Chang, B. Zhang, B. Lian, C. Xiang, I. Belopolski, H. Zheng, T. A. Cochran, S.-Y. Xu, G. Bian, K. Liu, T.-R. Chang, H. Lin, Z.-Y. Lu, Z. Wang, S. Jia, W. Wang, and M. Z. Hasan, Nature 562, 91-95 (2018).
  * (11) K. Kuroda, T. Tomita, M.-T. Suzuki, C. Bareille, A. A. Nugroho, P. Goswami, M. Ochi, M. Ikhlas, M. Nakayama, S. Akebi, R. Noguchi, R. Ishii, N. Inami, K. Ono, H. Kumigashira, A. Varykhalov, T. Muro, T. Koretsune, R. Arita, S. Shin, T. Kondo, and S. Nakatsuji, Nat. Mater. 16, 1090-1095 (2017).
  * (12) E. Liu, Y. Sun, N. Kumar, L. Muechler, A. Sun, L. Jiao, S.-Y. Yang, D. Liu, A. Liang, Q. Xu, J. Kroder, V. Süß, H. Borrmann, C. Shekhar, Z. Wang, C. Xi, W. Wang, W. Schnelle, S. Wirth, Y. Chen, S. T. B. Goennenwein, and C. Felser, Nat. Phys. 14, 1125-1131 (2018).
  * (13) Q. Wang, Y. Xu, R. Lou, Z. Liu, M. Li, Y. Huang, D. Shen, H. Weng, S. Wang, and H. Lei, Nat. Commun. 9, 3681 (2018).
  * (14) P. W. Anderson, Mater. Res. Bull. 8, 153-160 (1973).
  * (15) W.-H. Ko, P. A. Lee, and X.-G. Wen, Phys. Rev. B 79, 214502 (2009).
  * (16) W.-S. Wang, Z.-Z. Li, Y.-Y. Xiang, and Q.-H. Wang, Phys. Rev. B 87, 115135 (2013).
  * (17) M. L. Kiesel, C. Platt, and R. Thomale, Phys. Rev. Lett. 110, 126405 (2013).
  * (18) B. R. Ortiz, L. C. Gomes, J. R. Morey, M. Winiarski, M. Bordelon, J. S. Mangum, I. W. H. Oswald, J. A. Rodriguez-Rivera, J. R. Neilson, S. D. Wilson, E. Ertekin, T. M. McQueen, and E. S. Toberer, Phys. Rev. Mater. 3, 094407 (2019).
  * (19) B. R. Ortiz, S. M. L. Teicher, Y. Hu, J. L. Zuo, P. M. Sarte, E. C. Schueller, A. M. M. Abeykoon, M. J. Krogstad, S. Rosenkranz, R. Osborn, R. Seshadri, L. Balents, J. He, and S. D. Wilson, Phys. Rev. Lett. 125, 247002 (2020).
  * (20) B. R. Ortiz, P. M. Sarte, E. Kenney, M. J. Graf, S. M. L. Teicher, R. Seshadri, and S. D. Wilson, arXiv: 2012.09097 (2020).
  * (21) Y. Wang, S.-Y. Yang, P. K. Sivakumar, B. R. Ortiz, S. M. L. Teicher, H. Wu, A. K. Srivastava, C. Garg, D. Liu, S. S. P. Parkin, E. S. Toberer, T. McQueen, S. D. Wilson, and M. N. Ali, arXiv: 2012.05898 (2020).
  * (22) S.-Y. Yang, Y. Wang, B. R. Ortiz, D. Liu, J. Gayles, E. Derunova, R. Gonzalez-Hernandez, L. Šmejkal, Y. Chen, S. S. P. Parkin, S. D. Wilson, E. S. Toberer, T. McQueen, and M. N. Ali, Sci. Adv. 6, eabb6003 (2020).
  * (23) Y.-X. Jiang, J.-X. Yin, M. M. Denner, N. Shumiya, B. R. Ortiz, J. He, X. Liu, S. S. Zhang, G. Chang, I. Belopolski, Q. Zhang, M. S. Hossain, T. A. Cochran, D. Multer, M. Litskevich, Z.-J. Cheng, X. P. Yang, Z. Guguchia, G. Xu, Z. Wang, T. Neupert, S. D. Wilson, and M. Z. Hasan, arXiv: 2012.15709 (2020).
  * (24) E. M. Kenney, B. R. Ortiz, C. Wang, S. D. Wilson, and M. J. Graf, arXiv: 2012.04737 (2020).
  * (25) H. C. Lei, K. Liu, J.-i. Yamaura, S. Maki, Y. Murakami, Z.-Y. Lu, and H. Hosono, Phys. Rev. B 93, 121101(R) (2016).
  * (26) Y. Feng, J. Wang, D. M. Silevitch, B. Mihaila, J. W. Kim, J.-Q. Yan, R. K. Schulze, N. Woo, A. Palmer, Y. Ren, J. van Wezel, P. B. Littlewood, and T. F. Rosenbaum, Proc. Natl. Acad. Sci. 110, 3287-3292 (2013).
  * (27) W. L. McMillan, Phys. Rev. 167, 331-344 (1968).
  * (28) P. B. Allen and R. C. Dynes, Phys. Rev. B 12, 905-922 (1975).
  * (29) M. Naito and S. Tanaka, J. Phys. Soc. Jpn. 51, 219-227 (1982).
  * (30) J. M. Ziman, Electrons and Phonons, Clarendon Press, Oxford, England (1960).
  * (31) T. Valla, A. V. Fedorov, P. D. Johnson, P-A. Glans, C. McGuinness, K. E. Smith, E. Y. Andrei, and H. Berger, Phys. Rev. Lett. 92, 086104 (2004).
  * (32) N. P. Ong, Phys. Rev. B 43, 193-201 (1991).
  * (33) A. P. Mackenzie, N. E. Hussey, A. J. Diver, S. R. Julian, Y. Maeno, S. Nishizaki, and T. Fujita, Phys. Rev. B 54, 7425-7429 (1996).
  * (34) L. Li, J. Shen, Z. Xu, and H. Wang, Int. J. Mod. Phys. B 19, 275-279 (2005).
  * (35) D. Shoenberg, Magnetic Oscillations in Metals, Cambridge University Press, Cambridge, England (1984).
  * (36) D. Rhodes, S. Das, Q. R. Zhang, B. Zeng, N. R. Pradhan, N. Kikugawa, E. Manousakis, and L. Balicas, Phys. Rev. B 92, 125152 (2015).


# Last Iterate Convergence in Overparameterized GANs

Elbert Du  Elbert Du

(May 2021)

###### Abstract

In this work, we showed that the Implicit Update and Predictive Methods
dynamics introduced in prior work satisfy last iterate convergence to a
neighborhood around the optimum in overparameterized GANs, where the size of
the neighborhood shrinks with the width of the neural network. This is in
contrast to prior results, which only guaranteed average iterate convergence.

##  1 Introduction

One of the new and exciting results from the last few years is the Neural
Tangent Kernel (NTK) [1], which shows that as we increase the width of every
layer in a neural network to $\infty$, the function computed by the neural
network approaches a linear function. This makes it possible to analyze the
convergence of neural networks with only the assumption that they are
sufficiently wide, and [3] proves the convergence of wide GANs using projected
gradient descent in the average iterate.

In this paper, I adapt the analysis from [2] to demonstrate convergence of
Implicit Update (IU) dynamics and Predictive Methods (PM) to a neighborhood
around the optimum, with the size of this neighborhood shrinking with the
width of the neural network. To do this, I separate the error term from the
known analysis in a manner similar to that of [3] and then compute the
convergence rate and the size of the neighborhood by combining these two
terms.

##  2 Brief Overview of Liao et. al’s approach

The first key lemma from this paper (slightly abridged here, I left out some
assumptions to avoid getting bogged down in the details of this lemma as this
is only for motivating my approach) is one that allows us to bound the
convergence using regret:

######  Lemma 1.

If our sequence of functions $\\{(f_{t},u_{t})\\}_{t=1}^{T}$ satisfies

$\frac{1}{T}\sum_{t=1}^{T}\phi(f_{t},u_{t})\leq\min_{f}\frac{1}{T}\sum_{t=1}^{T}\phi(f,u_{t})+\epsilon_{f}$

and

$\frac{1}{T}\sum_{t=1}^{T}\phi(f_{t},u_{t})\geq\max_{u}\frac{1}{T}\sum_{t=1}^{T}\phi(f_{t},u)-\epsilon_{u}$

Then the primal error can be bounded by $\epsilon_{f}+\epsilon_{u}$.

Given this, we now just need to compute regret for one of the players. Let
$\theta_{t}$ be the parameters at time $t$, $\theta$ be the optimum,
$\phi_{t}$ be the function computed by our model at time $t$, and let
$\hat{\phi_{t}}$ be the linear approximation of $\phi_{t}$ given to us by NTK.
Then, we can write our regret as following expression:

$\left(\frac{1}{T}\sum_{t=1}^{T}\phi_{t}(\theta_{t})-\frac{1}{T}\sum_{t=1}^{T}\hat{\phi_{t}}(\theta_{t})\right)+\left(\frac{1}{T}\sum_{t=1}^{T}\hat{\phi_{t}}(\theta_{t})-\frac{1}{T}\sum_{t=1}^{T}\hat{\phi_{t}}(\theta)\right)+\left(\frac{1}{T}\sum_{t=1}^{T}\hat{\phi_{t}}(\theta)-\frac{1}{T}\sum_{t=1}^{T}\phi_{t}(\theta)\right)$

The first term is the error of the linear approximation over all of the
parameters over time, and the third term is the error of the linear
approximation at the optimum. These can be handled by looking at the error of
the linear approximation presented in the NTK.

Then, the second term is simply the difference between the average iterate of
our linear approximation and the optimum in the linear approximation. This can
be computed using known methods in convex optimization. As such, we can see
the power of separating out the error term and directly applying known results
for the linear case.

##  3 Last Iterate Results

For our proofs, we will use the following lemma, which is the fourth statement
in Lemma B.1 from [3]:

######  Lemma 2.

Given a neural network with $H$ layers each of width
$m=\Omega(d^{3/2}B^{-1}H^{-3/2}\log^{3/2}(m^{1/2}B^{-1}))$, where $d$ is the
number of dimensions in the input, the weight vector $W$ always satisfies
$||W-W_{0}||_{2}\leq B$ for $B=O(m^{1/2}H^{-6}\log^{-3}m)$ and initialization
at $W_{0}$, then with probability at least $1-e^{-\Omega(\log^{2}m)}$,

$\left\lVert\nabla_{W}f(x,W)-\nabla_{w}\hat{f}(x,W)\right\rVert_{2}=O\left(B^{1/3}m^{-1/6}H^{5/2}\log^{1/2}m\right)$

We will additionally assume that $C$ is invertible, and then we will prove the
following simplifying lemma:

######  Lemma 3.

Given a two-player game with utility function $U(\theta,\omega)$ linear in
both $\theta$ and $\omega$, solving the game is equivalent to solving some
game of the form

$U^{\prime}(\theta,\omega)=\theta^{T}C\omega$

###### Proof.

Since $U$ is linear, we can write

$U(\theta,\omega)=v_{1}^{T}\theta+\theta^{T}C\omega+v_{2}^{T}\omega+c$

Then, applying a translation:

$U(\theta-\theta_{0},\omega-\omega_{0})=v_{1}^{T}(\theta-\theta_{0})+(\theta-\theta_{0})^{T}C(\omega-\omega_{0})+v_{2}^{T}(\omega-\omega_{0})+c$

We note that $v_{1}^{T}\theta_{0}$, $\theta_{0}^{T}C\omega_{0}$, and
$v_{2}^{T}\omega_{0}$ are all constants, so we can group them together with
$c$ into a constant $c^{\prime}$. Then, we have

$U(\theta-\theta_{0},\omega-\omega_{0})=v_{1}^{T}\theta+\theta^{T}C\omega-\theta_{0}^{T}C\omega-\theta^{T}C\omega_{0}+v_{2}^{T}\omega+c^{\prime}$

We can now set $\theta_{0}^{T}C=v_{2}^{T}$ and $C\omega=v_{1}$, and we end up
with

$U(\theta-\theta_{0},\omega-\omega_{0})=\theta^{T}C\omega+c^{\prime}$

and solving this game is equivalent to solving

$U^{\prime}(\theta,\omega)=\theta^{T}C\omega$

so we can assume WLOG that we are optimizing a utility function

$U(\theta,\omega)=\theta^{T}C\omega.$

∎

Now, we are not actually working with linear functions. Rather, we are working
in a setting where both players are represented by overparameterized neural
networks. Hence, for finite widths, we instead have

$U(\theta,\omega)=\theta^{T}C\omega+U^{\prime}(\theta,\omega)$

where $U^{\prime}$ is a function with gradient bounded by lemma 2.

###  3.1 Convergence of IU

######  Theorem 4.

The IU dynamics converges to a neighborhood of size

$O\left(\frac{1}{1-1/\sqrt{2}}r^{1/3}m^{-1/6}H^{5/2}\log^{1/2}m\frac{\sqrt{\lambda_{\max}(CC^{T})}}{\lambda_{\min}(CC^{T})}\right)$

around the optimum.

###### Proof.

Recall the IU dynamics:

$\theta_{t+1}=\theta_{t}-\eta\nabla_{\theta}U(\theta_{t+1},\omega_{t+1})$
$\omega_{t+1}=\omega_{t}-\eta\nabla_{\omega}U(\theta_{t+1},\omega_{t+1})$

We can rewrite this as:

$\begin{bmatrix}\theta_{t+1}\\\
\omega_{t+1}\end{bmatrix}=\begin{bmatrix}\theta_{t}\\\
\omega_{t}\end{bmatrix}-\eta\begin{bmatrix}0&C\\\
-C^{T}&0\end{bmatrix}\cdot\begin{bmatrix}\theta_{t+1}\\\
\omega_{t+1}\end{bmatrix}+\eta\begin{bmatrix}\nabla
U^{\prime}_{\theta}(\theta_{t+1},\omega_{t+1})\\\ \nabla
U^{\prime}_{\omega}(\theta_{t+1},\omega_{t+1})\end{bmatrix}$

Now, rearranging some terms,

$\left(I+\eta\begin{bmatrix}0&C\\\
-C^{T}&0\end{bmatrix}\right)\begin{bmatrix}\theta_{t+1}\\\
\omega_{t+1}\end{bmatrix}=\begin{bmatrix}\theta_{t}\\\
\omega_{t}\end{bmatrix}+\eta\begin{bmatrix}\nabla
U^{\prime}_{\theta}(\theta_{t+1},\omega_{t+1})\\\ \nabla
U^{\prime}_{\omega}(\theta_{t+1},\omega_{t+1})\end{bmatrix}$

If we now apply lemma 2 and the triangle inequality,

$\left(I+\eta\begin{bmatrix}0&C\\\
-C^{T}&0\end{bmatrix}\right)\left\lVert\begin{bmatrix}\theta_{t+1}\\\
\omega_{t+1}\end{bmatrix}\right\rVert_{2}\leq\left\lVert\begin{bmatrix}\theta_{t}\\\
\omega_{t}\end{bmatrix}\right\rVert_{2}+O\left(r^{1/3}m^{-1/6}H^{5/2}\log^{1/2}m\eta\right)$

We can bound the LHS by taking the largest singular value of
$K=I+\eta\begin{bmatrix}0&C\\\ -C^{T}&0\end{bmatrix}$. Note that

$KK^{T}=\begin{bmatrix}I+\eta^{2}CC^{T}&0\\\ 0&I+\eta^{2}C^{T}C\end{bmatrix}$

so the singular values are at least $\sqrt{1+\eta^{2}\lambda_{\min}(CC^{T})}$.
If we plug in $\eta=\frac{1}{\sqrt{\lambda_{\max}(CC^{T})}}$, then we can make
the approximation:

$\sigma_{\min}(K)\geq\sqrt{1+\eta^{2}\lambda_{\min}(CC^{T})}\geq
1+\left(\sqrt{2}-1\right)\frac{\lambda_{\min}(CC^{T})}{\lambda_{\max}(CC^{T})}$

where $\sigma_{\min}(K)$ is the least singular value of $K$.

Thus, if we now plug in $c$ for the constant of the big-O term,

$\left\lVert\begin{bmatrix}\theta_{t+1}\\\
\omega_{t+1}\end{bmatrix}\right\rVert_{2}\leq\frac{1}{1+(\sqrt{2}-1)\lambda_{\min}(CC^{T})/\lambda_{\max}(CC^{T})}\left\lVert\begin{bmatrix}\theta_{t}\\\
\omega_{t}\end{bmatrix}\right\rVert_{2}+cr^{1/3}m^{-1/6}H^{5/2}\log^{1/2}m\eta$
$\left\lVert\begin{bmatrix}\theta_{t+1}\\\
\omega_{t+1}\end{bmatrix}\right\rVert_{2}\leq\left(1-\left(1-\frac{1}{\sqrt{2}}\right)\frac{\lambda_{\min}(CC^{T})}{\lambda_{\max}(CC^{T})}\right)\left\lVert\begin{bmatrix}\theta_{t}\\\
\omega_{t}\end{bmatrix}\right\rVert_{2}+cr^{1/3}m^{-1/6}H^{5/2}\log^{1/2}m\eta$

So the smallest distance we can guarantee we reach is $(\theta,\omega)$ such
that

$\left\lVert\begin{bmatrix}\theta\\\
\omega\end{bmatrix}\right\rVert_{2}\left(1-\frac{1}{\sqrt{2}}\right)\frac{\lambda_{\min}(CC^{T})}{\lambda_{\max}(CC^{T})}=cr^{1/3}m^{-1/6}H^{5/2}\log^{1/2}m\eta$

or equivalently,

$\left\lVert\begin{bmatrix}\theta\\\
\omega\end{bmatrix}\right\rVert_{2}=\frac{c}{1-1/\sqrt{2}}r^{1/3}m^{-1/6}H^{5/2}\log^{1/2}m\frac{\sqrt{\lambda_{\max}(CC^{T})}}{\lambda_{\min}(CC^{T})}$

and this goes to $0$ as $m\rightarrow\infty$.

Now, to analyze the time it takes to converge to this bound, suppose that we
have

$\left\lVert\begin{bmatrix}\theta_{t}\\\
\omega_{t}\end{bmatrix}\right\rVert_{2}\geq\frac{c}{1-1/\sqrt{2}}r^{1/3}m^{-1/6}H^{5/2}\log^{1/2}m\frac{\sqrt{\lambda_{\max}(CC^{T})}}{\lambda_{\min}(CC^{T})}+\delta$

Then, we can upper bound the linear approximation error term with

$\left(1-\frac{1}{\sqrt{2}}\right)\frac{\lambda_{\min}(CC^{T})}{\lambda_{\max}(CC^{T})}\left(\left\lVert\begin{bmatrix}\theta_{t}\\\
\omega_{t}\end{bmatrix}\right\rVert_{2}-\delta\right)$

so we get that

$\left\lVert\begin{bmatrix}\theta_{t+1}\\\
\omega_{t+1}\end{bmatrix}\right\rVert_{2}\leq\left\lVert\begin{bmatrix}\theta_{t}\\\
\omega_{t}\end{bmatrix}\right\rVert_{2}-\left(1-\frac{1}{\sqrt{2}}\right)\frac{\lambda_{\min}(CC^{T})}{\lambda_{\max}(CC^{T})}\delta$

which means our distance to the neighborhood shrinks by a factor of at least
$\left(1-\left(1-\frac{1}{\sqrt{2}}\right)\frac{\lambda_{\min}(CC^{T})}{\lambda_{\max}(CC^{T})}\right)$,
giving us the bound that after $T$ steps, we will be at distance at most

$\frac{c}{1-1/\sqrt{2}}r^{1/3}m^{-1/6}H^{5/2}\log^{1/2}m\frac{\sqrt{\lambda_{\max}(CC^{T})}}{\lambda_{\min}(CC^{T})}+\epsilon$

where

$T\geq\left\lceil(2+\sqrt{2})\frac{\lambda_{\max}(CC^{T})}{\lambda_{\min}(CC^{T})}\log\frac{r}{\epsilon}\right\rceil$

∎

###  3.2 Convergence of PM

######  Theorem 5.

The PU dynamics converges to a neighborhood of size

$\frac{\gamma\lambda_{\min}(CC^{T})}{\lambda_{\max}(CC^{T})+\gamma^{2}\lambda^{2}_{\max}(CC^{T})}\frac{(\gamma+1)\alpha}{\beta}$

around the optimum.

###### Proof.

The PM dynamics are defined as follows:

Predictive step:

$\theta_{t+1/2}=\theta_{t}-\gamma\nabla_{\theta}U(\theta_{t},\omega_{t})$
$\omega_{t+1/2}=\omega_{t}-\gamma\nabla_{\omega}U(\theta_{t},\omega_{t})$

Gradient step:

$\theta_{t+1}=\theta_{t}-\eta\nabla_{\theta}U(\theta_{t+1/2},\omega_{t+1/2})$
$\omega_{t+1}=\omega_{t}-\eta\nabla_{\omega}U(\theta_{t+1/2},\omega_{t+1/2})$

Furthermore, for notational convenience, we will let

$\alpha=cr^{1/3}m^{-1/6}H^{5/2}\log^{1/2}m$

Now, to prove the convergence, we analyze the vector of errors in the term
$\eta\nabla_{\theta}U(\theta_{t+1/2},\omega_{t+1/2})$ when compared to if we
replaced $U$ with its linear approximation.

We let $\theta^{\prime}_{t+1/2}=\theta_{t}-\gamma C\omega_{t}$ and
$\omega^{\prime}_{t+1/2}=\omega_{t}-\gamma C\theta_{t}$. This is the
predictive step we would have gotten with the linear approximation. Similarly,
we let $\theta^{\prime}_{t+1}$ and $\omega^{\prime}_{t+1}$ be the updates
according to the linear approximation using $\theta^{\prime}_{t+1/2}$ and
$\omega^{\prime}_{t+1/2}$.

$\theta_{t+1}=\theta_{t}-\eta
C\omega_{t+1/2}+\eta\nabla_{\theta}U^{\prime}(\theta_{t+1/2},\omega_{t+1/2})=\theta_{t}-\eta
C\omega^{\prime}_{t+1/2}-\eta\gamma
C\nabla_{\theta}U^{\prime}(\theta_{t},\omega_{t})+\eta\nabla_{\theta}U^{\prime}(\theta_{t+1/2},\omega_{t+1/2})$

and similarly for $\omega_{t+1}$.

Now, we note that this is the same as the equation we get with the exact
bilinear form, except we’re adding two error terms involving
$\nabla_{\theta}U^{\prime}$. As such, just as above, we can plug in
$\omega^{\prime}_{t+1/2}=\omega_{t}-\gamma C\theta_{t}$ and we get

$\begin{bmatrix}\theta_{t+1}\\\
\omega_{t+1}\end{bmatrix}=\left(I-\eta\begin{bmatrix}\gamma CC^{T}&C\\\
-C^{T}&\gamma C^{T}C\end{bmatrix}\right)\cdot\begin{bmatrix}\theta_{t}\\\
\omega_{t}\end{bmatrix}-\eta\gamma\begin{bmatrix}\nabla_{\theta}U^{\prime}(\theta_{t},\omega_{t})\\\
\nabla_{\omega}U^{\prime}(\theta_{t},\omega_{t})\end{bmatrix}+\eta\begin{bmatrix}\nabla_{\theta}U^{\prime}(\theta_{t+1/2},\omega_{t+1/2})\\\
\nabla_{\omega}U^{\prime}(\theta_{t+1/2},\omega_{t+1/2})\end{bmatrix}$

Now, we plug in

$\eta=\frac{\gamma\lambda_{\min}(CC^{T})}{\lambda_{\max}(CC^{T})+\gamma^{2}\lambda^{2}_{\max}(CC^{T})}$

and similarly to above, we can bound the largest singular value of
$K=\left(I-\eta\begin{bmatrix}\gamma CC^{T}&C\\\ -C^{T}&\gamma
C^{T}C\end{bmatrix}\right)$. Doing this exactly as in Liang and Stokes, we get
that it is upper bounded by

$\sqrt{1-\frac{\gamma^{2}\lambda^{2}_{\min}(CC^{T})}{\gamma^{2}\lambda^{2}_{\max}(CC^{T})+\lambda_{\max}(CC^{T})}}.$

For convenience, let this be $1-\beta$. Then, we have

$\left\lVert\begin{bmatrix}\theta_{t+1}\\\
\omega_{t+1}\end{bmatrix}\right\rVert_{2}\leq(1-\beta)\cdot\left\lVert\begin{bmatrix}\theta_{t}\\\
\omega_{t}\end{bmatrix}\right\rVert_{2}+\eta\gamma\alpha+\eta\alpha$

So just like with IU, we get that the value the norm converges to is

$\beta\left\lVert\begin{bmatrix}\theta\\\
\omega\end{bmatrix}\right\rVert_{2}=\eta\gamma\alpha+\eta\alpha$

$\left\lVert\begin{bmatrix}\theta\\\
\omega\end{bmatrix}\right\rVert_{2}=\frac{\gamma\lambda_{\min}(CC^{T})}{\lambda_{\max}(CC^{T})+\gamma^{2}\lambda^{2}_{\max}(CC^{T})}\frac{(\gamma+1)\alpha}{\beta}$

and since the error terms just give us an additive factor, we end up getting
the same rate of convergence just like with IU. More specifically, after

$T\geq
2\frac{\gamma^{2}\lambda_{\max}^{2}(CC^{T})+\lambda_{\max}(CC^{T})}{\gamma^{2}\lambda_{\min}(CC^{T})}\log\frac{r}{\epsilon}$

iterations, we have

$\left\lVert\begin{bmatrix}\theta_{t}\\\
\omega_{t}\end{bmatrix}\right\rVert_{2}\leq\frac{\gamma\lambda_{\min}(CC^{T})}{\lambda_{\max}(CC^{T})+\gamma^{2}\lambda^{2}_{\max}(CC^{T})}\frac{(\gamma+1)\alpha}{\beta}+\epsilon$

and again, all of these terms are constant except for $\alpha$ which goes to
$0$ as the width approaches $\infty$, so in the infinite width limit this does
give us exact convergence as we would expect. ∎

##  4 Future Work: Solving CO and OMD

###  4.1 Attempting to work with CO

Recall the CO dynamics: if we define the function

$R(\theta,\omega)=\frac{1}{2}\left(\left\lVert\nabla_{\theta}U(\theta,\omega)\right\rVert^{2}+\left\lVert\nabla_{\omega}U(\theta,\omega)\right\rVert^{2}\right)$

Then,

$\theta_{t+1}=\theta_{t}-\eta\left[\nabla_{\theta}U(\theta_{t},\omega_{t})+\gamma\nabla_{\theta}R(\theta_{t},\omega_{t})\right]$
$\omega_{t+1}=\omega_{t}-\eta\left[\nabla_{\omega}U(\theta_{t},\omega_{t})+\gamma\nabla_{\omega}R(\theta_{t},\omega_{t})\right]$

In the simple bilinear case analyzed in Liang and Stokes, this is identical to
PM. However, in our case, if we expand out $R(\theta,\omega)$, we get

$R(\theta,\omega)=\frac{1}{2}\left(\left\lVert
C\omega+\nabla_{\theta}U^{\prime}(\theta,\omega)\right\rVert^{2}+\left\lVert
C\theta+\nabla_{\omega}U^{\prime}(\theta,\omega)\right\rVert^{2}\right)$
$=C\omega\omega^{T}C^{T}+2\omega^{T}C^{T}\nabla_{\theta}U^{\prime}(\theta,\omega)+\nabla_{\theta}U^{\prime}(\theta,\omega)^{T}\nabla_{\theta}U^{\prime}(\theta,\omega)+C\theta\theta^{T}C^{T}+2\theta^{T}C^{T}\nabla_{\omega}U^{\prime}(\theta,\omega)+\nabla_{\omega}U^{\prime}(\theta,\omega)^{T}\nabla_{\omega}U^{\prime}(\theta,\omega)$

So when we try to compute $\theta_{t+1}$, we get many terms with complicated
second order derivatives that I was not able to compute bounds for in the time
frame of this project. However, if we are able to bound the L2 norm of the
gradient of each of the terms above, then we should be able to finish in the
same manner as with IU and PM.

###  4.2 Attempting to work with OMD

Recall the definition of OMD:

$\theta_{t+1}=\theta_{t}-2\eta\nabla_{\theta}U(\theta_{t},\omega_{t})+\eta\nabla_{\theta}U(\theta_{t-1},\omega_{t-1})$
$\omega_{t+1}=\omega_{t}-2\eta\nabla_{\omega}U(\theta_{t},\omega_{t})+\eta\nabla_{\omega}U(\theta_{t-1},\omega_{t-1})$

In this case, we have an even larger issue. When we apply our update rule, if
we define $R_{1}$ and $R_{2}$ as follows like in the bilinear case:

$R_{1}=\frac{\left(I-2\eta\begin{bmatrix}0&C\\\
-C^{T}&0\end{bmatrix}\right)+\left(I-4\eta^{2}\begin{bmatrix}CC^{T}&0\\\
0&C^{T}C\end{bmatrix}\right)^{1/2}}{2}$
$R_{2}=\frac{\left(I-2\eta\begin{bmatrix}0&C\\\
-C^{T}&0\end{bmatrix}\right)-\left(I-4\eta^{2}\begin{bmatrix}CC^{T}&0\\\
0&C^{T}C\end{bmatrix}\right)^{1/2}}{2}$

Now, our equation when we include the error terms looks like this:

$\begin{bmatrix}\theta_{t+1}\\\
\omega_{t+1}\end{bmatrix}=(R_{1}+R_{2})\begin{bmatrix}\theta_{t}\\\
\omega_{t}\end{bmatrix}-R_{1}R_{2}\begin{bmatrix}\theta_{t-1}\\\
\omega_{t-1}\end{bmatrix}-2\eta\begin{bmatrix}\nabla_{\theta}U^{\prime}(\theta_{t},\omega_{t})\\\
\nabla_{\omega}U^{\prime}(\theta_{t},\omega_{t})\end{bmatrix}+\eta\begin{bmatrix}\nabla_{\theta}U^{\prime}(\theta_{t-1},\omega_{t-1})\\\
\nabla_{\omega}U^{\prime}(\theta_{t-1},\omega_{t-1})\end{bmatrix}$

If we attempt to group the terms to establish a recursion like in Liang and
Stokes, we end up getting something that looks like

$\begin{bmatrix}\theta_{t+1}\\\
\omega_{t+1}\end{bmatrix}-R_{2}\begin{bmatrix}\theta_{t}\\\
\omega_{t}\end{bmatrix}+2\eta\begin{bmatrix}\nabla_{\theta}U^{\prime}(\theta_{t},\omega_{t})\\\
\nabla_{\omega}U^{\prime}(\theta_{t},\omega_{t})\end{bmatrix}=R_{1}\left(\begin{bmatrix}\theta_{t}\\\
\omega_{t}\end{bmatrix}-R_{2}\begin{bmatrix}\theta_{t-1}\\\
\omega_{t-1}\end{bmatrix}+\eta
R_{1}^{-1}\begin{bmatrix}\nabla_{\theta}U^{\prime}(\theta_{t-1},\omega_{t-1})\\\
\nabla_{\omega}U^{\prime}(\theta_{t-1},\omega_{t-1})\end{bmatrix}\right)$

Unfortunately, $R_{-1}$ is most certainly not $2I$, so we cannot apply the
recursion all the way down on the right hand side like we can with the
bilinear case. As such, we would need to figure out a new way to analyze this
if we want to prove its convergence (if it even converges).

##  5 A Note on Motivating Early Stopping

In my slides, I mistakenly believed that all of the weights varied by
$O(m^{-1/2})$ from initialization, and missed the fact that the last layer can
vary arbitrarily. As such, the intuition that the initialization got close to
the optimum faster than the training was false.

Even so, there is a different idea which may motivate early stopping found in
my methods here:

One can note that my bounds are rather loose: the vector we are adding from
our error term is not necessarily in the same direction as our current state.
As such, if we assume the error to be a random vector chosen uniformly from
all sufficiently small vectors, we should instead expect it to sometimes even
bring us closer to $0$. As such, as soon as we are within say $\alpha/10$ of
the bound proven for either PM or IU here, there is a high probability (close
to 1/2) that the error term will end up pushing us inside the neighborhood
that we proved we can converge to. Then, we expect to essentially bounce
around within this neighborhood (note that our proof can be extended to show
that once we enter the neighborhood, we will never leave it). As such, as soon
as we enter the neighborhood, there does not appear to be any meaning in
continuing to train unless we can determine some properties about the
direction of the error vector.

This provides some intuition as to why early stopping may be good. If we have
some way to tell that at some iteration, we are very close to the optimum (for
example, maybe halfway into the ball around the optimum), then stopping there
would generally be better than continuing for a fixed number of iterations
past there and then stopping.

##  6 Other Future Work

I did not analyze the last-iterate convergence of Simultaneous Gradient Ascent
(SGA) in the overparameterized setting here. SGA does not converge in the
bilinear case, but if we consider optimizing the square loss rather than just
the loss, we go from a bilinear utility function to a quadratic utility
function. In this setting, we are approximating a quadratic function in both
the $\theta$ player and the $\omega$ player, so we have strong convexity. As
such, it may be possible to show that SGA will converge in the last-iterate
using squared loss.

It is with squared loss that Liao et al. was able to prove the average iterate
convergence of projective gradient descent. As such, this would also be a
promising avenue to look into for further convergence results.

## References

  * [1] Arthur Jacot, Franck Gabriel, and Clément Hongler.  Neural tangent kernel: Convergence and generalization in neural networks, 2020.
  * [2] Tengyuan Liang and James Stokes.  Interaction matters: A note on non-asymptotic local convergence of generative adversarial networks, 2019.
  * [3] Luofeng Liao, You-Lin Chen, Zhuoran Yang, Bo Dai, Zhaoran Wang, and Mladen Kolar.  Provably efficient neural estimation of structural equation model: An adversarial approach, 2020.


* [17] R. E. Gompf, _Toward a topological characterization of symplectic manifolds_ , J. Symplectic Geom. 2 (2004), no. 2, 177–206.
  * [18] R. E. Gompf and A. I. Stipsicz, _$4$ -manifolds and Kirby calculus_, Graduate Studies in Mathematics, vol. 20, American Mathematical Society, Providence, RI, 1999.
  * [19] R. Goto and K. Hayano, _$C^{\infty}$ -logarithmic transformations and generalized complex structures_, J. Symplectic Geom. 14 (2016), no. 2, 341–357.
  * [20] M. Gualtieri, _Generalized complex geometry_ , Ann. of Math. (2) 174 (2011), no. 1, 75–123.
  * [21] M. Gualtieri, S. Li, A. Pelayo, and T. S. Ratiu, _The tropical momentum map: a classification of toric log symplectic manifolds_ , Math. Ann. 367 (2017), no. 3-4, 1217–1258.
  * [22] N. Hitchin, _Generalized Calabi-Yau manifolds_ , Q. J. Math. 54 (2003), no. 3, 281–308.
  * [23] Y. Lekili, _Wrinkled fibrations on near-symplectic manifolds_ , Geom. Topol. 13 (2009), no. 1, 277–318. Appendix B by R. İnanç Baykur.
  * [24] N. C. Leung and M. Symington, _Almost toric symplectic four-manifolds_ , J. Symplectic Geom. 8 (2010), no. 2, 143–187.
  * [25] R. B. Melrose, _The Atiyah-Patodi-Singer index theorem_, Research Notes in Mathematics, vol. 4, A K Peters, Ltd., Wellesley, MA, 1993.
  * [26] E. Miranda and G. Scott, _The geometry of $E$-manifolds_, 2018. arXiv:1802.02959. To appear in Revista Matemática Iberoamericana.
  * [27] P. Orlik and F. Raymond, _Actions of the Torus on 4-Manifolds. I_ , Transactions of the American Mathematical Society 152 (1970), no. 2, 531–559.
  * [28] A. Pelayo and S. Vũ Ngọc, _Semitoric integrable systems on symplectic 4-manifolds_ , Invent. Math. 177 (2009), no. 3, 571–597.
  * [29] R. Torres, _Constructions of generalized complex structures in dimension four_ , Comm. Math. Phys. 314 (2012), no. 2, 351–371.
  * [30] R. Torres and J. Yazinski, _On the number of type change loci of a generalized complex structure_ , Lett. Math. Phys. 104 (2014), no. 4, 451–464.
  * [31] J.-C. van der Meer, _The Hamiltonian Hopf bifurcation_, Lecture Notes in Mathematics, vol. 1160, Springer-Verlag, Berlin, 1985.
  * [32] N. T. Zung, _Symplectic Topology of Integrable Hamiltonian Systems, II: Topological Classification_ , Compositio Mathematica (2003), no. 2, 125–156.