<?xml-model href='http://www.tei-c.org/release/xml/tei/custom/schema/relaxng/tei_all.rng' schematypens='http://relaxng.org/ns/structure/1.0'?><TEI xmlns="http://www.tei-c.org/ns/1.0">
	<teiHeader>
		<fileDesc>
			<titleStmt><title level='a'>Non-asymptotic Convergence of Training Transformers for Next-token Prediction</title></titleStmt>
			<publicationStmt>
				<publisher>The Thirty-Ninth Annual Conference on Neural Information Processing Systems</publisher>
				<date>12/09/2024</date>
			</publicationStmt>
			<sourceDesc>
				<bibl> 
					<idno type="par_id">10631665</idno>
					<idno type="doi"></idno>
					
					<author>R Huang</author><author>Y Liang</author><author>J Yang</author>
				</bibl>
			</sourceDesc>
		</fileDesc>
		<profileDesc>
			<abstract><ab><![CDATA[Transformers have achieved extraordinary success in modern machine learning due to their excellent ability to handle sequential data, especially in next-token prediction (NTP) tasks. However, the theoretical understanding of their performance in NTP is limited, with existing studies focusing mainly on asymptotic performance. This paper provides a fine-grained non-asymptotic analysis of the training dynamics of a one-layer transformer consisting of a self-attention module followed by a feed-forward layer. We first characterize the essential structural properties of training datasets for NTP using a mathematical framework based on partial orders. Then, we design a two-stage training algorithm, where the pre-processing stage for training the feed-forward layer and the main stage for training the attention layer exhibit fast convergence performance. Specifically, both layers converge sub-linearly to the direction of their corresponding max-margin solutions. We also show that the cross-entropy loss enjoys a linear convergence rate. Furthermore, we show that the trained transformer presents non-trivial prediction ability with dataset shift, which sheds light on the remarkable generalization performance of transformers. Our analysis technique involves the development of novel properties on the attention gradient and further in-depth analysis of how these properties contribute to the convergence of the training process. Our experiments further validate our theoretical findings.]]></ab></abstract>
		</profileDesc>
	</teiHeader>
	<text><body xmlns="http://www.tei-c.org/ns/1.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xlink="http://www.w3.org/1999/xlink">
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="1">Introduction</head><p>The transformer architecture <ref type="bibr">(Vaswani et al., 2017)</ref> has revolutionized the field of machine learning, establishing itself as a foundation model for numerous applications, including natural language processing (NLP) <ref type="bibr">(Devlin et al., 2018)</ref>, computer vision <ref type="bibr">(Dosovitskiy et al., 2020)</ref>, and multi-modal signal processing <ref type="bibr">(Tsai et al., 2019)</ref>. In particular, transformers achieve tremendous empirical success in large language models (LLMs) such as GPT-3 <ref type="bibr">(Brown et al., 2020)</ref>. Despite the empirical success, limited theoretical understanding of transformers have caused a series of critical concerns about their robustness, interpretability, and bias issues <ref type="bibr">(Bommasani et al., 2021;</ref><ref type="bibr">Belkin, 2024)</ref>.</p><p>To overcome these issues, recent advances in transformer theory have investigated the convergence of training transformers under theoretically amenable setting such as linear regression <ref type="bibr">(Mahankali et al., 2023;</ref><ref type="bibr">Zhang et al., 2023;</ref><ref type="bibr">Huang et al., 2023)</ref> and binary classification <ref type="bibr">(Tarzanagh et al., 2023b,a;</ref><ref type="bibr">Vasudeva et al., 2024;</ref><ref type="bibr">Li et al., 2023)</ref>. Nevertheless, one of the fundamental task in LLMs and other generative models is next-token prediction (NTP), which involves predicting the next word or token in a sequence, given the previous tokens. In NTP, a few recent theoretical studies have started to investigate the training dynamics of transformers <ref type="bibr">(Tian et al., 2023a;</ref><ref type="bibr">Li et al., 2024)</ref>. However, those works lack of fine-grained non-asymptotic convergence analysis of the training process, posing the following open questions for further investigation:</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>How fast does the training of a transformer converge in NTP?</head><p>In addition, a pre-trained transformer empirically exhibits non-trivial generalization ability. A follow-up question from a theoretical point of view is that</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>Can we show the generalization capability of a trained transformer on unseen data?</head><p>In this paper, we take a first step towards addressing the aforementioned questions by studying the training dynamics of a single layer transformer consisting of a self-attention layer and a feed-forward layer for NTP. We summarize our contribution as follows.</p><p>&#8226; We develop a mathematical framework based on partial order to formally characterize the essential structural properties of the training dataset for next-token prediction. In particular, we introduce a realizable setting for training datasets where the loss can be minimized to near zero, which admits a collocation and query-dependent partial orders. A collocation is a set of token pairs where each token is directly paired with its subsequent token. Query-dependent partial orders is a set of partial orders where each partial order classifies tokens into three categories: optimal tokens, non-optimal tokens and non-comparable tokens. These structural properties define favorable max-margin problems on both the feed-forward layer and the self-attention layer. &#8226; Second, we design a two-stage training algorithm based on normalized gradient descent. In stage 1 of pre-processing, we use the collocation to train the feed-forward layer. In stage 2, we use the entire dataset to train the self-attention layer. We show that the feed-forward layer and the query-key attention matrix converge sublinearly in direction respectively to the max-margin solution for classifying next token from all other tokens in the preprocessing dataset, and to the max-margin solution for classifying the optimal from non-optimal tokens. In addition, the norm of the transformer parameters grows linearly, which further yields a linear convergence rate of the cross-entropy loss. Our two-stage algorithm decouples the training of the feed-forward and attention layers without losing optimality, as stage 1's max-margin solution is judiciously designed to facilitate stage 2's fine-grained classification for optimal token prediction. &#8226; Third, we show that the trained transformer has generalization ability for making non-trivial prediction on unseen data. In particular, the transformer is trained to learn an extended querydependent partial order, where the non-comparable tokens are inserted in between the optimal tokens and non-optimal tokens. Thus, the trained transformer will attend to non-comparable tokens if optimal tokens are not in a new sentence and further make desirable prediction.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2">Related Work</head><p>Inspired by <ref type="bibr">Brown et al. (2020)</ref>, who demonstrated that pre-trained transformers can learn in-context -i.e., learn new tasks during inference with only a few samples -a series of works focus on the expressiveness power of transformers <ref type="bibr">(Aky&#252;rek et al., 2022;</ref><ref type="bibr">Bai et al., 2023;</ref><ref type="bibr">Von Oswald et al., 2023;</ref><ref type="bibr">Fu et al., 2023;</ref><ref type="bibr">Giannou et al., 2023;</ref><ref type="bibr">Lin et al., 2023)</ref>. These studies have shown that there exist parameter configurations such that transformers can perform various algorithms such as gradient descent. Additionally, <ref type="bibr">Edelman et al. (2022)</ref> showed that transformers can represent a sparse function.</p><p>Regarding the training dynamics and optimization of transformers under in-context learning, <ref type="bibr">Ahn et al. (2024)</ref>; <ref type="bibr">Mahankali et al. (2023)</ref>; <ref type="bibr">Zhang et al. (2023)</ref>; <ref type="bibr">Huang et al. (2023)</ref> studied the dynamics of a single attention layer, single-head transformer for the in-context learning of linear regression tasks. <ref type="bibr">Cui et al. (2024)</ref> proved that multi-head attention outperforms single-head attention. <ref type="bibr">Cheng et al. (2023)</ref> showed that local optimal solutions in transformers can perform gradient descent in-context for non-linear functions. <ref type="bibr">Kim and Suzuki (2024)</ref> studied the nonconvex mean-field dynamics of transformers, and <ref type="bibr">Nichani et al. (2024)</ref> established a convergence rate of &#213;(1/t) for the training loss in learning a causal graph. Additionally, <ref type="bibr">Chen et al. (2024)</ref> investigated the gradient flow in training multi-head attention. <ref type="bibr">Chen and Li (2024)</ref> proposed a supervised training algorithm for multi-head transformers.</p><p>Another line of research focuses on the training dynamics of transformers for binary classification problems. <ref type="bibr">Tarzanagh et al. (2023b,a)</ref> demonstrated an equivalence between the optimization dynamics of a single attention layer and a certain SVM problem. While <ref type="bibr">Tarzanagh et al. (2023b,a)</ref> only proved an asymptotic convergence result, <ref type="bibr">Vasudeva et al. (2024)</ref> improved the convergence rate to t -3/4 . <ref type="bibr">Li et al. (2023)</ref> studied the training dynamics of vision transformers and showed that the generalization error can approach zero given sufficient training samples. Additionally, <ref type="bibr">Deora et al. (2023)</ref> investigated the training and generalization error under the neural tangent kernel (NTK) regime.</p><p>For transformers trained on next-token prediction (NTP), <ref type="bibr">Tian et al. (2023a)</ref> analyzed the training dynamics of a single-layer transformer, while <ref type="bibr">Tian et al. (2023b)</ref> studied the joint training dynamics of multi-layer transformers. <ref type="bibr">Li et al. (2024)</ref> demonstrated the asymptotic convergence of transformers trained with a logarithmic loss function for NTP. Although these works provided valuable insights into the training dynamics of transformers for NTP, they did not provide the finite-time convergence analysis, which is the focus of this paper. We remark that <ref type="bibr">Thrampoulidis (2024)</ref> studied NTP without transformer structure.</p><p>Our work is also related to the classical implicit bias framework for training neural networks (NNs).</p><p>In particular <ref type="bibr">Soudry et al. (2018)</ref>; <ref type="bibr">Nacson et al. (2019)</ref>; <ref type="bibr">Ji and Telgarsky (2021)</ref>; <ref type="bibr">Ji et al. (2021)</ref> established convergence rate of gradient descent-based optimization. Phuong and Lampert (2020); <ref type="bibr">Frei et al. (2022)</ref>; <ref type="bibr">Kou et al. (2024)</ref> studied the implicit bias of ReLU/Leaky-ReLU networks on orthogonal data. A comprehensive survey is provided in <ref type="bibr">Vardi (2023)</ref>. However, these works focused on classical neural networks, whereas we investigate the implicit bias of transformers for NTP.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3">Problem Setup</head><p>Notations. All vectors considered in this paper are column vectors. We use 1{A} to denote the indicator function of A, i.e., 1{A} = 1 if A holds, and 1{A} = 0 otherwise. &#8741;W &#8741; represents the Frobenious norm of the matrix W . For a vector v, we use <ref type="bibr">[v]</ref> i to denote the i-th coordinate of v.</p><p>We use &#981;(v) to denote the softmax function, i.e., [&#981;(v)] i = exp(v i )/ j exp(e &#166; j v), which can be applied to any vector with arbitrary dimension. We use {e i } i&#8712; <ref type="bibr">[|V|]</ref> to denote the canonical basis of R |V| , i.e., [e i ] j = 1{i = j}. The inner product &#239;A, B&#240; of two matrices A, B equals to Trace(AB &#166; ).</p><p>Next-token prediction. We consider the task of next-token prediction, which aims to predict the subsequent token in a token sequence given its preceding tokens. Formally, suppose that there exists a finite vocabulary set V &#162; R d that consists of all possible tokens, where d is the dimension of the embedding. Each token x &#8712; V is associated with a unique index I(x) &#8712; {1, 2, . . . , |V|}, where I is the index function. An L-length sentence X = [x 1 , . . . , x L ] &#8712; V L &#162; R d&#215;L is a sequence of L tokens, where L is an integer. We assume that the maximum length of sentences is L max . The subsequent tokens in sentences are generated from a set of ground-truth model {p * L : V L &#8594; V} L&lt;Lmax , where p * L generates the next token x L+1 given the sentence X for any 1 f L &lt; L max . The task of next-token prediction requires us to learn all models {p * L } L&lt;Lmax given a training dataset</p><p>) is also a training sample, since it follows p * &#8467; as well. Decoder-only transformer. A decoder-only transformer is a stack of blocks consisting of a selfattention layer and a feed-forward layer. For simplicity, we consider one-layer transformer, where the self-attention layer is determined by three matrices: W k &#8712; R d&#215;d1 , W q &#8712; R d1&#215;d and W v &#8712; R d2&#215;d , namely key, query, and value matrices, and the feed-forward layer is determined by</p><p>Here d 1 , d 2 are hidden dimensions. Mathematically, given the input X = [x 1 . . . , x L ], we write the one-layer transformer as</p><p>and &#981; is the softmax function. We note that the inner softmax function &#981; is part of the attention model, and the outer softmax function &#981; is the decoder that generates a probability distribution over V for token prediction.</p><p>Reparameterization. We reparameterize the transformer architecture by consolidating the key and query matrices into a unified matrix W kq , such that W kq = W k W q . Similarly, we reparameterize the product of the feed-forward (W o ) and value (W v ) matrices as a single matrix W ov , defined as W ov = W o W v . Such a reparameterization is commonly adopted in transformer theory works <ref type="bibr">(Huang et al., 2023;</ref><ref type="bibr">Tian et al., 2023a;</ref><ref type="bibr">Li et al., 2024;</ref><ref type="bibr">Nichani et al., 2024)</ref>. Thus, the transformer under those reparameterization is given by T</p><p>Cross-entropy loss. Given the training dataset D 0 and the transformer model, we seek to learn p * by minimizing (training) the cross-entropy loss L(&#185;) defined as follows:</p><p>where I(x L+1 ) is the index of x L+1 in V.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4">Realizable Training Dataset and Two-Stage Algorithm</head><p>In this section, we first provide a mathematical framework based on partial order to formally characterize a realizable training dataset for next-token prediction. We will then describe a two-stage algorithm for next-token prediction that we study.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4.1">Realizable Training Dataset</head><p>We characterize a realizable training dataset via two structural properties, where the training loss can be made arbitrarily close to zero. We first provide some intuitions about those two properties.</p><p>Existence of "collocation". First, we note that if a sentence</p><p>x 2 ) is also in the training dataset. In addition, the output of a transformer given one single input token only depends on W ov , i.e. the feed-forward layer. Since training loss can be arbitrarily close to 0, there exists a sequence {W t } such that lim t&#8594;&#8734; -x&#8712;D0 log e &#186; (x) &#166; &#981;(W t x) = 0, where &#186;(x) is the index of next token of x, and the summation is over the case when x is the first token. Due to that &#981;(W t x) is a probability distribution, the equality holds only when &#186; is injective, since otherwise it is an entropy of some distribution which is strictly greater than 0. Therefore, there exists an injective map n : V &#8594; V such that every sentence starts with x, must have a unique next token n(x). We call the set of pairs {x, n(x)} x&#8712;V a collocation. We remark that p * 1 = n. Existence of "order". Second, let us consider the output of a transformer T &#185; given a legal sentence X = [x 1 , . . . , x L ] with the next token x L+1 = p * L (X). The transformer first calculates a convex combination of x 1 , . . . , x L with corresponding weight &#966; &#8467; &#8733; exp(x &#166; &#8467; W kq x L ) for each &#8467; f L. Then, the transformer outputs &#981;( &#8467; W ov x &#8467; &#966; &#8467; ). Recall that the collocation forces x &#8467; to map to n(x &#8467; ), thus &#981;(W ov x &#8467; ) has a peak value at the coordinate equal to I(n(x &#8467; )) (the index of n(x &#8467; )). Hence, T &#185; (X) can only have peak value at the coordinates within the set {I(n(x &#8467; ))} &#8467;fL . If the training loss can be arbitrarily close to 0, it is desirable to have n -<ref type="foot">foot_0</ref> (x L+1 ) &#8712; {x &#8467; } &#8467;fL . Therefore, for those x &#8467; with n(x &#8467; ) = x L+1 , &#966; &#8467; must be larger than &#966; &#8467; &#8242; with n(x &#8467; &#8242; ) &#824; = x L+1 . Finally, it worth noting that &#966; &#8467; depends on the final token x L . This observation motivates us to define query-dependent partial orders on V.</p><p>Definition 1 (x q -partial order) Fix a token x q . An x q -partial order assigns an ordering relationship &gt; x q for certain pairs of tokens in V, and is created as follows. Let D x q 0 be the set of all legal sentences in the training dataset that has the final token (query) x q . Then, for any pair of tokens x, x &#8242; &#8712; V, we assign x &gt; x q x &#8242; if there exists a sentence X = [x 1 , . . . , x L ] &#8712; D x q 0 and x, x &#8242; are tokens in X such that n(x) = x L+1 &#824; = n(x &#8242; ), where x L+1 is the next token of X.</p><p>Note that Definition 1 is a "constructive definition" which might not be well-defined. However, as we are under the setting when the training loss can be arbitrarily close to 0, the aforementioned discussion shows that if x &gt; x q x &#8242; , then &#966; &#8467; &gt; &#966; &#8467; &#8242; , where x = x &#8467; and x &#8242; = x &#8467; &#8242; in some sentence. Thus, exp(xW kq x q ) &gt; exp(x &#8242; W kq x q ), which indeed need to be well-defined. Otherwise, we will have contradictions such as exp(xW kq x q ) &gt; exp(x &#8242; W kq x q ) &lt; exp(xW kq x q ). Mathematically, a well-defined (strict) partial order &gt; on a set V satisfies two axioms <ref type="bibr">(Yannakakis, 1982)</ref>: (i) there is no x &gt; x; (ii) if x &gt; x &#8242; and x &#8242; &gt; x &#8242;&#8242; , then x &gt; x &#8242;&#8242; . Thus, x q -partial order created by D 0 is well-defined for every x q &#8712; V.</p><p>Finally, let us discuss the impact of query-dependent partial orders on D 0 . For a given query x q , the partial order &gt; x q divides tokens in V into four disjoint types.</p><p>&#8226; (Strict) optimal tokens. A token x is optimal, if there is no x &#8242; such that x &#8242; &gt; x q x 1 . &#8226; Confused tokens. A token x is confused, if there exists x &#8242; , x &#8242;&#8242; such that x &#8242; &gt; x q x &gt; x q x &#8242;&#8242; . &#8226; (Strict) non-optimal tokens. A token x is non-optimal if there is no x &#8242; such that x &gt; x q x &#8242;2 . &#8226; Non-comparable tokens. A token x is non-comparable if there is no x &#8242; such that x &gt; x q x &#8242; or</p><p>x &#8242; &gt; x q x.</p><p>In this work, we assume that there are no confused tokens. This assumption simplifies the problem, making it tractable to provide explicit convergence in direction for training a transformer in Section 5. In summary, we make the following structural assumption on the training dataset.</p><p>Assumption 1 (Realizable training dataset) D 0 admits (i) a collocation {x, n(x)} x&#8712;V ; (ii) welldefined query-dependent partial orders, where every x q -partial order has no confused tokens.</p><p>We remark that combining the collocation and query-dependent partial orders, we can regenerate the training dataset as follows. For any sentence with only one token X = [x], the next token is n(x).</p><p>For other sentences X = [x 1 , . . . , x L ], let x &#8467; be optimal under the partial order &gt; x L , and then the next token of X is n(x &#8467; ). We next provide a simple example that justifies Assumption 1.</p><p>Example 1 Consider a language system where the vocabulary consists of four tokens {S, V, O, P}, where S,V,O,P respectively stand for subject, verb, object, and punctuation mark. This system admits the commonly adopted word order <ref type="bibr">(Dryer, 1991)</ref>: S, V, O, P. Let the training dataset be {SVOP, VOP, OPP, PSV}. Let us create the corresponding collocation and the query-dependent partial orders from the dataset. The collocation is {(S, V), (V, O), (O, P), (P, S)}. That is, if a sentence starts with a subject, then the next token is a verb. Similarly, if a sentence starts with a verb, then the next token is an object, and so on. The query-dependent partial orders are created as follows: Partial order under query S. S&gt; S P. Partial order under query O. O&gt; O S, O&gt; O V. Partial order under query V. V&gt; V S. Partial order under query P. O&gt; P P.</p><p>Therefore, if a sentence starts with S (subject), the next token is V (verb) according to the collocation. Then, for the sentence SV, since the query is V and V&gt; V S, the next token of the sentence coincides with the next token of V, which is exactly O (object). Finally, for the sentence SVO, following similar argument, the next token is P (punctuation mark). This example satisfies Assumption 1 and aligns with real-world scenarios. An illustration is provided in Figure <ref type="figure">1</ref>. Additional notations of training data. It is worth noting that there are only finite number of distinct sentences. For ease of presentation, we introduce the following notations. Suppose there are N distinct sentences in the training dataset D 0 indexed by n &#8712; {1, . . . , N }. For each distinct sentence</p><p>Building upon this, with a little abuse of notation, we use n(X (n) ) &#8712; V to denote the subsequent token of the sentence X (n) and In(X (n) ) to denote the index of n(X (n) ).</p><p>We further denote X</p><p>(n)</p><p>-1 as the final token of X (n) , and let T&#185; (X) = W ov X&#981;(X &#166; W kq X</p><p>(n)</p><p>-1 ). Then, the loss function L(&#185;) can be rewritten as follows:</p><p>(1)</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4.2">Training Algorithm</head><p>For the realizable dataset satisfying Assumption 1, we propose a two-stage training algorithm using normalized gradient descent (NGD). The pseudo code of the algorithm is presented in Algorithm 1.</p><p>In Section 5, we show that the two-stage algorithm decouples the training of the feed-forward and attention layers without losing the optimality. This is because the training in stage 1 is designed to yield a suitable max-margin solution, which will enable the training of stage 2 to solve a fine-grained classifcation problem and identify the optimal token for prediction.</p><p>In the first stage of pre-processing, we use the collocation set to train the feed-forward layer W ov .</p><p>For simplicity, we introduce the following notation for the training loss of the feed-forward layer. Given a collocation {x, n(x)} x&#8712;V , which can be obtained through extracting all length-2 sentences in the training dataset D 0<ref type="foot">foot_2</ref> , we use normalized gradient descent to train W ov . Equivalently, the loss function can be written as</p><p>,</p><p>where the self-attention elements are removed because the attention matrices are not trained here. Based on the above loss function, we initialize W (0) ov = 0 &#8712; R |V|&#215;d , and subsequently take an update at each time t by NGD as in line 4 of Algorithm 1.</p><p>In the second stage, we fix the trained feed-forward layer and train the self-attention layer based on the loss function given in Equation (1) and using the entire dataset D 0 . Specifically, we initialize W kq = 0 &#8712; R d&#215;d , and subsequently take an update at each time t by NGD as in line 7 of Algorithm 1.</p><p>Algorithm 1 Two-stage Normalized Gradient Descent 1: Initialization:</p><p>kq ). 8: end for</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="5">Training Dynamics of the Transformer</head><p>In this section, we present the convergence result for Algorithm 1. Before we proceed, we first introduce the following technical assumption, which has been commonly adopted in the previous theoretical studies of transformers <ref type="bibr">(Huang et al., 2023;</ref><ref type="bibr">Li et al., 2024;</ref><ref type="bibr">Tian et al., 2023a)</ref>.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>Assumption 2</head><p>The vocabulary set is orthornormal. Namely, the embedding has unit norm, i.e., &#8741;x&#8741; = 1, and x &#166; x &#8242; = 0 holds for any distinct tokens x and x &#8242; .</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="5.1">Convergence of Training W ov</head><p>To characterize the training dynamics of W ov , we observe that the collocation {(x, n(x))} x&#8712;V defines the following hard-margin problem:</p><p>It can be shown that lim B&#8594;+&#8734; L 0 (BW * ov ) = 0. Thus, the loss function L 0 trains W ov to be the max-margin solution with W ov x distinguishing the next token n(x) from all other tokens in V.</p><p>Since L 0 (&#8226;) is convex, we have the following convergence result on the training of</p><p>ov be updated by Algorithm 1. Then, for any t g 2, we have t&#184;0</p><p>ov &#8741; f t&#184;0 and the following bound holds:</p><p>Moreover, the loss function L 0 satisfies that L 0 (W</p><p>Proposition 1 states that during the training stage 1, the feed-forward layer</p><p>ov converges in direction to W * ov /&#8741;W * ov &#8741; at a rate of O(log t/t), which classifies the next token from all other tokens. In addition, since the norm of W (t) ov increases linearly, the loss L 0 (W (t) ov ) converges linearly to zero, i.e., L 0 (W</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="5.2">Convergence of Training W kq</head><p>Recall that after the training stage 1 with T steps, we obtain a trained feed-forward layer W (T ) ov . Then, we fix W (T ) ov and use normalized gradient descent to train W kq . To characterize the training dynamics of the key-query matrix W kq , we note that each query-dependent partial order also defines a hard-margin problem. Let l(n) &#162; {1, . . . , L (n) } be the set of indices of the optimal tokens of X (n) . Recall that x &#8467; is optimal if there is no</p><p>-1 should correctly classify optimal tokens x &#8467; and non-optimal tokens x &#8467; &#8242; . This is formalized in the following problem:</p><p>We will show that the loss function in Equation ( <ref type="formula">1</ref>) given the well trained W (T ) ov will train W kq towards the max-margin solution W * kq in direction for classifying between the optimal and non-optimal token. We further make the following technical assumption.</p><p>Assumption 3 For any sample X (n) , the number of optimal tokens is not less than the number of non-optimal tokens. Formally, for any non-optimal token x in</p><p>Assumption 3 is consistent with practical and empirical observations, where optimal tokens often demonstrate higher relevance, making them more frequent in subsequent outcomes.</p><p>We now present the convergence result for the training of the key-query matrix in stage 2.</p><p>Theorem 1 Let Assumptions 1-3 hold. Let W * kq be the solution of Equation (3). Let &#184;&lt; O(1) and W (t) kq be updated by Algorithm 1. Then, for any t g 2, we have that t2</p><p>kq &#8741; f t&#184;. In addition, the following inequality holds.</p><p>Theorem 1 states that the key-query matrix W kq converges in direction to the max-margin solution W * kq /&#8741;W * kq &#8741; at a convergence rate of O(log 2 t/t). We further show that the norm of W kq also grows linearly in t, i.e., &#8741;W kq &#8741; = &#8486;(t). Combining these results, we have the following theorem on the convergence of the loss function and the training accuracy.</p><p>Theorem 2 (Loss Convergence) For any training sentence</p><p>L ) be the attention weight. Under the conditions in Theorem 1, there is an absolute constant c 0 such that when T g c 0 &#8741;W * ov &#8741; 5 log(|V|) log T /&#184;0 and t g c 0 N L 4 max &#8741;W * kq &#8741; 6 log 2 t/&#184;, the optimal token weight satisfies min n &#8467; * &#8712;l(n) &#966; (n,t) &#8467; * g (1 + L max exp (-tC 1 ))) -1 . In addition, the loss function L converges linearly 4 to its minimal value:</p><p>4 For fixed W (T ) ov , the minimum loss value L * = |V| exp(-T C0). Then Equation (4) implies L(&#952; (t) )-L * &#8804; L * T C0O(e -C 1 t ) for sufficiently large t, which further implies the linear convergence in t.</p><p>where</p><p>Theorem 2 shows that the training loss converges to its minimum value at a linear convergence rate. Furtherm, for T = &#8486;(log(1/&#1013; 0 )) t = &#8486;(log(1/&#1013;)), the optimal token weight is given by 1/(1 + &#1013;) for any &#1013; &gt; 0, which is close to 1. This implies that the trained transformer attends to the optimal token and thus outputs the correct next token n(x</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="5.3">Proof Sketch of Theorem 1</head><p>The proof consists of the following three main steps. The key proof step lies in carefully analyzing the projection of gradient &#8711; W kq L(&#185; (t) ) onto the token-query outer product</p><p>-1 ) &#166; , max-margin attention weight matrix W * kq , and the trained attention weight matrix W (t) kq .</p><p>Step 1 (Lemma 5). By analyzing</p><p>-1 ) &#166; , we characterize the dynamics of attention weights. Using mathematical induction, we show that the lower bound of optimal token weight is 1/L max .</p><p>Step 2 (Lemma 6). Then, we show that the cosine similarity between the negative gradient and W * kq is strictly larger than the minimum optimal token weight. Utilizing step 1, due to the NGD update, the norm of the key-query matrix W (t) kq can be shown to grow linearly.</p><p>Step 3 (Lemma 7). Finally, we carefully compare the difference between the projections from gradient to the trained attention matrix and max-margin attention matrix. By separately evaluating the impact of the optimal and non-optimal tokens on those projections, we can show the following inequality for some constant C 0 :</p><p>kq &#8741; grows linearly, the dynamics of the attention layer can be shown to converge in direction to the max-margin solution in Equation (3).</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="6">Generalization Ability</head><p>In this section, we prove the generalization ability of the trained transformers. Recall that Theorem 1 shows that</p><p>kq &#8741;/&#8741;W * kq &#8741;. To characterize the generalization ability, it is desirable to use the property of W * kq , which is given in the following result.</p><p>Proposition 2 Under Assumptions 1-2, fix a query token x q , let O x q , N x q , M x q &#162; V be the set of optimal tokens, the set of non-optimal tokens, and the set of non-comparable tokens, under x q -partial order, respectively. Then, the solution W * kq of Equation (3) satisfies x &#166; 0 W * kq x q = 0 for x 0 &#8712; M x q , and</p><p>Recall that non-comparable tokens (see Section 4) under a query x q never appears in any training sentence data with the same query x q . Thus, Proposition 2 implies an interesting generalization capability -each x q -partial order can automatically incorporate more relationships to expand the query-dependent partial orders. Combining Proposition 2 with Theorem 1, we obtain the following theorem on W (t) kq .</p><p>Theorem 3 Under the conditions and notations in Proposition 2, let T = &#8486;(log(1/&#1013;)), and t = &#8486;(log(1/&#1013;)). Then there exists a constant C 0 such that</p><p>Moreover, if the trained transformer takes input X with query x q that consists of a non-comparable token x 0 and non-optimal tokens, then the prediction made by T &#185; (t) (X) is n(x 0 ) with high probability.</p><p>Theorem 3 suggests that a new partial order is created by the trained transformer. Specifically, it inserts the non-comparable tokens between the optimal and non-optimal tokens. The trained transformer can generalize the token prediction to such new sentences as given in Theorem 3.</p><p>We use Example 1 to illustrate the generalization ability described above.</p><p>Example 2 (Generalization to unseen data in Example 1) Recall that in Example 1, the training dataset consists of four sentences: SVOP, VOP, OPP, and PSV. Consider the partial order &gt; P under the punctuation mark P. We have that O&gt; P P and O is an optimal token, P is a non-optimal token, and S,V are non-comparable tokens. We then have the following non-trivial prediction by the trained transformer.</p><p>Case 1. Non-comparable tokens are learned to be "larger" than non-optimal tokens.</p><p>Consider a new (unseen) input sentence SP. Since S is non-comparable before training, but is "larger" than P under the trained key-query matrix W (t) kq , the next predicted token is n(S) = V. Case 2. Optimal tokens remain optimal over all tokens after training.</p><p>Consider a new (unseen) input OSP. O is optimal and S is still "smaller" than O under the trained P-partial order. The trained transformer will consistently predict P.</p><p>In both of the above cases, the trained transformer provides desirable prediction for the unseen sentences. We further note that the effectiveness of both cases can vary during the inference time of the trained transformer. For instance, if the input sequence is SP (subject-punctuation), the output is SPV (subject-P-verb), which follows a logical subject-verb order and is desirable. However, in cases where the input is VP (verb-punctuation), it may be preferable to terminate the sequence after the verb, i.e., VPP, as the verb alone can suffice to convey the intended meaning.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="7">Experiment</head><p>In this section, we verify our theoretical findings via an experiment on a synthetic dataset. Specifically, we randomly generate a realizable dataset as described in Assumption 1 with |V| = 20. Then, we train W  </p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="8">Conclusion</head><p>In this work, we investigated the training dynamics of a single-layer transformer for NTP. We first characterized two structural properties of the training dataset under the realizable setting where the training loss can be made arbitrarily close to zero. These properties allow us to define two max-margin solutions for both the feed-forward layer and the self-attention layer. Then, we showed that both layers converge in direction to their corresponding max-margin solutions sub-linearly, which further yields a linear convergence of the training loss for NTP. We further showed that the well trained transformer can have non-trivial prediction ability on unseen data, which sheds light on the generalization capability of transformers. Our experiments verify our theoretical findings. </p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>A Expression of Gradients</head><p>We first provide the general formula for the gradients of both layers.</p><p>(5)</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>B Proof of Proposition 1</head><p>Recall that we use the loss,</p><p>The updating rule of W ov is that</p><p>We know that L 0 is convex respect to W ov . Therefore, we have</p><p>It is clear that the loss function L reaches the minimum 0 when W ov = &#8710;W * ov , as &#8710; &#8594; &#8734;.</p><p>Lemma 1 Under the initialization W (0) ov and the updating rule Equation (7) with step size &#184;, the following inequality holds.</p><p>Proof. Using Equation ( <ref type="formula">5</ref>), we have</p><p>where (a) is due the constraints that W * ov satisfies. On the other hand,</p><p>where (a) follows from &#8741;AB&#8741; f &#8741;A&#8741;&#8741;B&#8741; for any matrices A and B. Thus, we obtain</p><p>To lower bound the norm of W ov , we recall the updating rule (Equation ( <ref type="formula">7</ref>)).</p><p>For the LHS of the inequality, it suffices to note that at each iteration, the norm &#8741;W</p><p>ov &#8741; increases most &#184;0 due to normalized gradient descent.</p><p>Lemma 2 At each iteration t, the following inequality holds.</p><p>Proof. First, we consider the case when W </p><p>In this case, the result is trivial.</p><p>Then, we consider the case when</p><p>Due the optimality of W * ov , which achieves the minimum norm satisfying the constraints in Equation ( <ref type="formula">2</ref>), we must have that for some x 0 &#8712; V, there exists i 0 &#824; = In(x 0 ) such that the following inequality holds</p><p>.</p><p>Therefore, the loss on</p><p>ov can be lower bounded as follows.</p><p>where (a) is due to the fact that log(1 + x) g x/2 when 0 &lt; x &lt; 1. On the other hand, let</p><p>Then, the loss on W &#8242; ov has the following upper bound.</p><p>where (a) is due to the fact that log(1 + x) &lt; x when x &gt; 0. Thus, L(W</p><p>Due to the convextiy of L 0 , we have</p><p>which finishes the proof.</p><p>Proposition 3 (Restatement of Proposition 1) Under the zero initialization W (0) ov = 0 and updating rule Equation (7), for any t g 2, the following inequality holds.</p><p>Moreover, t&#184;0</p><p>ov &#8741; f t&#184;0.</p><p>Proof. The second argument about the norm of W (t) ov follows directly from Lemma 1. We aim to prove the first part as follows.</p><p>ov &#8741; log(2|V|). By Lemma 2 and the updating rule Equation (7), we have</p><p>where (a) follows from that &#8741;W</p><p>ov &#8741; = &#184;0, and (b) is due to the fact that x 2 -y 2 g 2y(x-y) for any x, y &#8712; R.</p><p>Summing over t starting from 2, we have</p><p>Furthermore, due to Lemma 1,</p><p>Similarly,</p><p>Therefore,</p><p>where (a) follows from Lemma 1 and &#8741;W</p><p>and &#8741;W (t) ov &#8741; g t&#184;0/(2&#8741;W * ov &#8741;) C Proof of Theorem 1 and Theorem 2 C.1 Supporting Lemmas Lemma 3 With zero initialization, under the updating rule Equation (7), for any iteration t, W (t) ov</p><p>satisfies that</p><p>Proof. The proof follows directly from induction and the fact that</p><p>Corollary 1 Under the settings in Proposition 1, let T g 384&#8741;W * ov &#8741; 5 log(2|V|) log T /&#184;0, and</p><p>Proof. The second equality follows directly from Lemma 3.</p><p>To show the first equation, we analyze</p><p>, where (a) follows from Proposition 1, and (b) is due to Lemma 1. On the other hand, we also have</p><p>The proof is finished.</p><p>Thus, for simplicity, we further assume that (e In(x)e i )W (T ) ov x = &#8710; for all x, because (e In(x)e i ) &#372;ov x = &#920;(&#8710;) for large enough iteration. Next, we provide the general form of the projection of the gradient of Key-Query matrix W kq follows from a notation for the token weight.</p><p>The token weight &#966;</p><p>we have</p><p>Proof. Recall that l(n) is the set of indices of the optimal tokens in the sample X (n) . Thus, for any &#8467; * &#8712; l(n), In(x n) ). In addition, we denote T &#185; (X (n) ) by T</p><p>(n)</p><p>&#185; for simplicity. From Equation (6), we have</p><p>where (a) is due to the fact that i&#8712;[|V|] [T</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>(n)</head><p>&#185; ] i = 1 for any &#185;, n.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>Main Steps</head><p>The proof consists of three main steps. First, we show that the optimal token weight has a lower bound. Then, we show that the gradient aligns with the optimal direction. Third, we show that the norm of Key-Query matrix grows linearly. Combining these three steps, we can prove the Theorem 1 and Theorem 2.</p><p>Recall that the updating rule for</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>C.2 Step 1</head><p>We first show that the optiaml token weight has a lower bound during the training.</p><p>Lemma 5 (Lower bound of optimal token weight) Under the zero initialization and updating rule Equation (10), for any iteration t, and any sample X (n) , if l(n) is the set of indices of the optimal token in X (n) , the following inequality holds.</p><p>First, we introduce the notation that &#966;</p><p>as the summation of optimal token weights, and &#966;</p><p>as the summation of non-optimal token weights.</p><p>At t = 0, due to zero initialization, we have &#966; (n,0) &#8467; = 1/L (n) . Moreover, by Assumption 3, for any &#8467; / &#8712; l(n), we have &#966;</p><p>We perform induction the hypothesis: &#966;</p><p>for all &#8467; * &#8712; l(n) and &#8467; / &#8712; l(n).</p><p>Suppose the hypothesis holds for iteration t. Let x (n)</p><p>&#8467; * be the optimal token in the sequence X (n) .</p><p>Fix a sample X (n &#8242; ) . we have (x</p><p>&#8467; * = 0 due to Assumption 1, and (x</p><p>&#8467; * g 0, we immediately have</p><p>&#8467;0 be any non-optiaml token in the sequence X (n &#8242; ) . Then, we have (x</p><p>where the last inequality is due to Assumption 3, the induction hypothesis and i&#8712;[|V|] [T</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>(n)</head><p>&#185; ] i = 1 Therefore, for any n, we have</p><p>For the second argument in the hypothesis, we examine &#966;</p><p>The proof is finished.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>C.3 Step 2</head><p>The following lemma shows that the norm of the Key-Query Matrix increases linearly with the number of iterations.</p><p>Lemma 6 Under the initialization W (0) kq and the updating rule Equation (10), for each iteration t, the following inequality holds.</p><p>Proof.</p><p>We examine the gradient &#8711; W kq L(&#185;) projected onto the optimal direction W * kq /&#8741;W * kq &#8741;.</p><p>where &#966;</p><p>is the summation of optimal token weights, and &#966;</p><p>is the summation of non-optimal token weights.</p><p>On the other hand,</p><p>Thus, we have</p><p>By the updating rule Equation ( <ref type="formula">10</ref>), we have</p><p>In addition, by the triangle inequality,</p><p>kq &#8741;. The proof is completed.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>C.4 Step 3</head><p>We next show that the gradient &#8711; W kq L(&#185; (t) ) is close to the optimal direction W * kq .</p><p>Lemma 7 (Gradient aligns with the optimal direction) Let</p><p>Then, for any t g t 0 , we have</p><p>We point out a few facts that will be frequently used in the proof.</p><p>If a</p><p>The same result holds if a</p><p>is replaced any convex combination of a set of a</p><p>We start the proof by noting that W * kq is the minimum unique solution to the problem</p><p>Therefore, if</p><p>In the following, we focus on the case when W (t) kq</p><p>Then, there must be at least a sentence X (n) , such that W (t) kq</p><p>violates the contraint on X (n) . In other words, we must have</p><p>This implies that for those n, we must have &#966;</p><p>(n,t) &#8467; g exp(-</p><p>kq &#8741; &#8741;W * kq &#8741; ) Thus, we consider two types of samples in the folloiwng.</p><p>Recall that the inner product between the gradient &#8711; W kq L(&#185; (t) ) and any other Key-Query matrix &#185; &#8242; = W &#8242; kq has the following form (Lemma 4). n) ) be the loss on sample X (n) .</p><p>To proceed, we examine the gradient on each sample X (n) with &#966;</p><p>kq &#8741;/&#8741;W * kq &#8741;), which can be divided into two parts.</p><p>We further let</p><p>.</p><p>Thus, we aim to find the relationship A (n,t) + B (n,t) between A (n, * ) + B (n, * ) .</p><p>We first provide the upper bounds for A (n, * ) and B (n, * ) .</p><p>, where (a) is due to the fact that (x</p><p>g 1, and a</p><p>kq &#8741;/&#8741;W * kq &#8741;. On the other hand</p><p>where (a) is due to Equation (11), and (b) is obtained by choosing T = log</p><p>. Thus, we further have</p><p>Next, we analyze B (n,t) , and further divide</p><p>Due to Proposition 4, we have B</p><p>(n, * ) -= 0, and thus</p><p>We then analyze:</p><p>g &#180;0A (n, * ) , where (a) follows from that b * ,&#8467; f -(1 + &#180;0)&#8741;W &#185; ] i = 1 for any &#185;, n, and (c) follows from &#180;0/2 g</p><p>where (a) follows from Equation ( <ref type="formula">11</ref>), (b) is optained by choosing T = log(2&#8741;W (t) kq &#8741;), (c) follows from Lemma 5, and (d) is due to the fact that &#180;0 g</p><p>So far, we have shown that for if &#966;</p><p>Type 2. Now consider sentence X (n) such that &#966;</p><p>Let n 0 be the type 1 sample such that &#966;</p><p>kq &#8741;/&#8741;W * kq &#8741;) Then, we aim to show that</p><p>We further note that [T (n0)</p><p>. Thus,</p><p>where (a) is due to that &#180;0 g</p><p>kq &#8741; g 2(e -1)&#8741;W * kq &#8741;, and</p><p>In summary, we have that</p><p>where &#179; t g (N + 3)&#180;0. The proof is finished. Now, we are ready to prove Theorem 1.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>C.5 Proof of Theorem 1</head><p>Proof of Theorem 1.</p><p>kq &#8741; . By Lemma 7, we have</p><p>&#184;, be defined in Lemma 7. Summing over t from t 0 , we have</p><p>where (a) follows from &#184;f &#8741;W * kq &#8741;/e. Therefore, we have</p><p>Finally, by Lemma 6, and t 0 f 1 + 8L max &#8741;W * kq &#8741; 2 /&#184;, we have &#8741;W (t0) kq &#8741; f 9L max &#8741;W * kq &#8741; 2 , and</p><p>The proof is finished.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>C.6 Proof of Theorem 2</head><p>Proof of Theorem 2.</p><p>Recall that T g 384&#8741;W * ov &#8741; 5 log(2|V|) log T /&#184;0, and &#8710; = T &#184;0/(4&#8741;W * ov &#8741; 2 ) due to Corollary 1 and</p><p>Note that for all &#8467; * &#8712; l(n) and &#8467; / &#8712; l(n)</p><p>f -t4 L max &#8741;W * kq &#8741; 2 , where (a) follows from t g 1696N L 4 max &#8741;W * kq &#8741; 6 log 2 t/&#184;. Therefore,</p><p>where the last inequality follows from t g</p><p>Hence, the loss on the sentence X (n) satisfies that</p><p>Thus, the average loss has upper bound, which is</p><p>D Proof of Proposition 2 and Theorem 3</p><p>D.1 Proof of Proposition 2 Proposition 4 (Restatement of Proposition 2) Under Assumption 2, if W * kq satisfies Equation (3), i.e., W * kq = arg min &#8741;W &#8741;, s.t. (x</p><p>In addition, for each query x q , if there are k optimal tokens under a x q -partial order, m nonoptimal tokens under x q -partial order, then, for any optimal token x * , non-optimal token x, and non-comparable token x 0 , we have</p><p>Proof. Let U &#8712; R d be the rotation matrix such that U x = e I(x) . Because U preserves Frobenius norm, the optimization problem in Equation (3) can be written as</p><p>Notably W * = U W * kq U &#166; . Note that {e I(X (n)</p><p>-1 ) } n forms a standard basis. It suffices to minimize the norm of each column of W subject to the constraint (e I(x (n) &#8467; * )e I(x (n) &#8467; ) ) &#166; W e I(X (n) -1 ) g 1. Let us consider any column c of W , denoted as [w 1 , . . . , w d ] &#166; . Without loss of generality, we assume that, for all X (n) with I(X (n)</p><p>-1 ) = c, the set of indices of the optimal tokens of those samples are {1, . . . , k}, and the set of indices of the non-optimal tokens are {k + 1, . . . , k + m}. Then, the optimization problem Equation ( <ref type="formula">14</ref>) reduces to the following problem min w 2 1 + . . . + w 2 d , s.t. w iw j g 1, &#8704;i f k, j &#8712; A i &#162; {k + 1, . . . , k + m}, (15) where A i is the set of indices of the non-optimal tokens in some samples whose optimal token has index i.</p><p>In other words, each column of the solution of Equation ( <ref type="formula">14</ref>) is the solution of Equation ( <ref type="formula">15</ref>).</p><p>Note that Equation ( <ref type="formula">15</ref>) is a convex problem with linear constraints. The Lagrangian function is</p><p>where we directly set w j = 0 for all j &#8712; {k + m + 1, . . . , d}. That is, non-comparable tokens have value 0.</p><p>By KKT-condition, we have</p><p>where &#188; g 0. The maximum of L * is achieved when &#8711; &#188; L * = 0. This implies that</p><p>Hence, we have w iw j = 1 for all 1 f i f k &lt; j f k + m, which means the optimum of the original problem is achieved on the boundary. Therefore, we reduce the original problem to min</p><p>where x = w k+1 = . . . = w k+m . Hence, the optimal solution is w 1 = . . . = w k = m/(m + k), and</p><p>Therefore, the solution of Equation ( <ref type="formula">15</ref>) satisfies that the "optimal values" are the same and the "non-optimal values" are the same as well. This fact proves that</p><p>And moreover, if there are k optimal tokens under a x q -partial order, m non-optimal tokens under x q -partial order, then, for any optimal token x * and non-optimal token x, we have</p><p>NeurIPS Paper Checklist</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="1.">Claims</head><p>Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?</p><p>Answer: <ref type="bibr">[Yes]</ref> Justification: We provide details of our three main claims made in the abstract in Section 4, Section 5, and Section 6, respectively.</p><p>Guidelines:</p><p>&#8226; The answer NA means that the abstract and introduction do not include the claims made in the paper. &#8226; The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. &#8226; The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. &#8226; It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2.">Limitations</head><p>Question: Does the paper discuss the limitations of the work performed by the authors?</p><p>Answer: [Yes] Justification: Our paper has specified the assumptions (Assumption 1,Assumption 2, and Assumption 3) under which our results hold.</p><p>Guidelines:</p><p>&#8226; The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. &#8226; The authors are encouraged to create a separate "Limitations" section in their paper.</p><p>&#8226; The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. &#8226; The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. &#8226; The authors should reflect on the factors that influence the performance of the approach.</p><p>For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. &#8226; The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. &#8226; If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. &#8226; While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.">Theory Assumptions and Proofs</head><p>Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?</p><p>5. Open access to data and code Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes] Justification: We provide our code in the supplemental. We do not use open source data. Guidelines: &#8226; The answer NA means that paper does not include experiments requiring code. &#8226; Please see the NeurIPS code and data submission guidelines (<ref type="url">https://nips.cc/</ref> public/guides/CodeSubmissionPolicy) for more details. &#8226; While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark). &#8226; The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (<ref type="url">https:  //nips.cc/public/guides/CodeSubmissionPolicy</ref>) for more details. &#8226; The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc. &#8226; The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why. &#8226; At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable). &#8226; Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 6. Experimental Setting/Details Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results? Answer: [Yes] Justification: Our experiment details are provided in Section 7. Guidelines: &#8226; The answer NA means that the paper does not include experiments.</p><p>&#8226; The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. &#8226; The full details can be provided either with the code, in appendix, or as supplemental material.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="7.">Experiment Statistical Significance</head><p>Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [Yes] Justification: As our synthetic dataset and training process is fixed, we do not foresee significant errors. Guidelines:</p><p>&#8226; The answer NA means that the paper does not include experiments.</p><p>&#8226; The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. &#8226; The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).</p><p>&#8226; The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) &#8226; The assumptions made should be given (e.g., Normally distributed errors). &#8226; It should be clear whether the error bar is the standard deviation or the standard error of the mean. &#8226; It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. &#8226; For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). &#8226; If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="8.">Experiments Compute Resources</head><p>Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments? Answer: [Yes] Justification: Our experiment is on synthetic data and is computationally lightweight, which does not require any GPU. The running time is also within a hour. Guidelines:</p><p>&#8226; The answer NA means that the paper does not include experiments.</p><p>&#8226; The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. &#8226; The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. &#8226; The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 9. Code Of Ethics Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics <ref type="url">https://neurips.cc/public/EthicsGuidelines</ref>? Answer: [Yes] Justification: We follow exactly the code of ethics. Guidelines:</p><p>&#8226; The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.</p><p>&#8226; If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. &#8226; The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [NA] Justification: This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here. Guidelines:</p><p>&#8226; The answer NA means that there is no societal impact of the work performed.</p><p>&#8226; If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.</p><p>&#8226; Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. &#8226; The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. &#8226; The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. &#8226; If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="11.">Safeguards</head><p>Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: Our paper is primarily a theoretical work, and does not have such risk. Guidelines:</p><p>&#8226; The answer NA means that the paper poses no such risks.</p><p>&#8226; Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. &#8226; Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. &#8226; We recognize that providing eoective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith eoort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [NA] Justification: Our paper is primarily a theoretical work, and does not use any assets. Guidelines:</p><p>&#8226; The answer NA means that the paper does not use existing assets.</p><p>&#8226; The authors should cite the original paper that produced the code package or dataset.</p><p>&#8226; The authors should state which version of the asset is used and, if possible, include a URL. &#8226; The name of the license (e.g., CC-BY 4.0) should be included for each asset.</p><p>&#8226; For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. &#8226; If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.</p></div><note xmlns="http://www.tei-c.org/ns/1.0" place="foot" n="1" xml:id="foot_0"><p>This is also related to the maximal element in a partially ordered set.</p></note>
			<note xmlns="http://www.tei-c.org/ns/1.0" place="foot" n="2" xml:id="foot_1"><p>This is also related to the minimal element in a partially ordered set.</p></note>
			<note xmlns="http://www.tei-c.org/ns/1.0" place="foot" n="3" xml:id="foot_2"><p>A more general way is to use various standard techniques developed in linguistic analysis<ref type="bibr">(Lehecka, 2015)</ref>.</p></note>
		</body>
		</text>
</TEI>
