text:
An analysis of early developmental trauma in social anxiety disorder and posttraumatic stress disorder
Melanie Bishop1,
David Rosenstein1,
Susanne Bakelaar1 &
Soraya Seedat1
Annals of General Psychiatry volume 13, Article number: 16 (2014) Cite this article
The early contributions of childhood trauma (emotional, physical, sexual, and general) have been hypothesized to play a significant role in the development of anxiety disorders, such as posttraumatic stress disorder (PTSD) and social anxiety disorder (SAD). The aim of this study was to assess childhood trauma differences between PTSD and SAD patients and healthy controls, as measured by the Early Trauma Inventory.
We examined individuals (N = 109) with SAD with moderate/severe early developmental trauma (EDT) (n = 32), individuals with SAD with low/no EDT (n = 29), individuals with PTSD with EDT (n = 17), and healthy controls (n = 31). The mean age was 34 years (SD = 11). Subjects were screened with the Mini-International Neuropsychiatric Interview (MINI), Liebowitz Social Anxiety Scale (LSAS), Clinician-Administered PTSD Scale (CAPS), and Childhood Trauma Questionnaire (CTQ). Analysis of variance was performed to assess group differences. Correlations were calculated between childhood traumas.
Although not statistically significant, individuals with PTSD endorsed more physical and sexual childhood trauma compared with individuals with SAD with moderate/severe EDT who endorsed more emotional trauma. For all groups, physical and emotional abuse occurred between ages 6 and 11, while the occurrence of sexual abuse in individuals with PTSD was at 6–11 years and later (13–18 years) in individuals with SAD with moderate/severe EDT. For emotional abuse in all groups, the perpetrator was mostly a primary female caregiver; for sexual abuse, it was mostly a nonfamilial adult male, while for physical abuse, it was mostly a caregiver (male in PTSD and female in SAD with moderate/severe EDT).
The contribution of childhood abuse to the development of PTSD and SAD and the differences between these groups and other anxiety disorders should not be ignored and attention should be given to the frequency and severity of these events. The relationship of the perpetrator(s) and the age of onset of childhood abuse are also important considerations as they provide a useful starting point to assess impact over the life course. This can, in turn, guide clinicians on the optimal timing for the delivery of interventions for the prevention of PTSD and SAD.
Introduction and background
Early developmental trauma (EDT) or childhood trauma may loosely be defined as any traumatic experience that occurs before 18 years of age [1]. EDT has been linked to the development of anxiety disorders in adulthood [2–5]. Among South Africans, anxiety disorders (15.8%) are the most prevalent lifetime disorders according to the South African Stress and Health (SASH) study, with social anxiety disorder (SAD) at 2.8% and posttraumatic stress disorder (PTSD) at 2.3% [6]. It has been estimated that one in ten children, on average, is neglected or psychologically abused annually and that approximately 4% to 16% are physically abused [7]. Stein et al. in 1996 found in their sample that both adult males and females with an anxiety disorder had higher rates of childhood physical abuse than those without an anxiety disorder [8]. In addition, females with anxiety disorders had higher rates of childhood sexual abuse [8]. Also, Prigerson et al. in 1996 found that psychological abuse and parental loss were risk factors for the development of adult psychiatric disorders [5]. In SAD [9] and PTSD [10], childhood traumas include physical abuse [11–13], sexual abuse [12–18], and emotional abuse [19–23].
Physical and sexual abuse in PTSD and SAD
The association between different subtypes of EDT and anxiety disorders in adults is a complex one. For example, in a national study by Cougle et al. in 2010, childhood physical abuse was specifically associated with PTSD in adults [11]. Furthermore, there was a relationship between sexual and physical abuse experienced in childhood and adult PTSD [11]. Sexual abuse in childhood has also been established to be a risk factor for the development of SAD [18] and PTSD [12, 13, 15, 16] in adulthood. In a study of women from an American cohort, childhood sexual abuse occurred in approximately 10% of women diagnosed with PTSD [17]. This was supported by the findings of Cutajar et al. in 2010 who found sexual abuse was most strongly correlated with PTSD [16]. Also, significantly more females than males who experienced childhood sexual abuse were diagnosed with PTSD [16]. In a separate study, adults with SAD reported higher rates of sexual abuse in childhood compared to healthy controls [14].
Emotional and other abuse in PTSD and SAD
Childhood emotional abuse has been reported to correlate more strongly, than either physical or sexual abuse, with a diagnosis of SAD and depression [20]. According to Kuo et al. in 2011 individuals with SAD had higher rates of childhood emotional abuse and emotional neglect compared to healthy controls [21]. In one study conducted by Simon et al. in 2009, 56% and 39% of individuals with SAD, respectively, experienced childhood emotional abuse and neglect [22]. Kuo et al. in 2011 investigated the frequency of childhood traumas (sexual abuse, physical abuse, physical neglect, emotional abuse, and emotional neglect) as measured by the Childhood Trauma Questionnaire (CTQ) [21]. As mentioned previously, they found that childhood emotional abuse and neglect were more frequently reported by individuals with SAD [21]. Other childhood traumas have been reported in PTSD and SAD. Afifi et al. in 2009 found that a combination of childhood abuse and parental divorce significantly increased the likelihood of a diagnosis of lifetime PTSD in adulthood [24]. Binelli et al. in 2012 found only one significant positive correlation between family violence and SAD, although the assessment of childhood trauma was based on five closed questions (yes/no) relating to five childhood adversities, namely, the loss of someone close, emotional abuse, physical abuse, family violence, and sexual abuse [25].
Age of onset and relationship to perpetrator in PTSD and SAD
The association between EDT subtypes, age of occurrence, and relationship to the perpetrator has not received much attention in the literature [26]. In individuals with PTSD, the onset of childhood sexual abuse (CSA) seems to be between the ages of 6 and 13 years, with a mean duration of 7 years [27]. In one study the age of onset of CSA was approximately 7 years [26]. Also, most perpetrators (87%) of CSA in adults with PTSD were males and were nuclear family members (37%), followed by nonfamily members (35%), and extended family members (28%) [27]. In another study, the age of onset of abuse by a family friend/other perpetrators was significantly associated with social anxiety in adulthood [28]. Most were abused by other perpetrators (e.g., acquaintances, boyfriends, and babysitters) (44%), followed by strangers (40%), other relatives or family members (29%), family friends (16%), and least by their fathers (14%). Furthermore, the average age of onset was 9.85 years [28].
Rationale and aims
Although EDT and other early childhood adversities have been examined in SAD and PTSD, there have been no comparative studies of the frequency and association of EDT subtypes in these disorders. The clinical value of such a comparison between childhood trauma in PTSD and SAD is important as it provides clinicians with information that can be used in interventions with patients with PTSD and SAD. The aim of this study was to assess EDT differences between PTSD and SAD patients and healthy controls. Secondly, we wanted to establish the frequency of events occurring in childhood, as measured by the Early Trauma Inventory (ETI). Thirdly, we wanted to establish the age of onset of childhood abuse and type of perpetrator (relationship to victim and gender) in this sample with SAD and PTSD. Lastly, we correlated childhood traumas as measured by the ETI and childhood traumas measured by the CTQ. We hypothesized that there would be significant group differences, with more childhood trauma overall, and significantly more sexual trauma, reported by the PTSD group. We further hypothesized that (i) the age of onset of EDT and the perpetrators involved would differ between the groups and (ii) childhood trauma as measured by the CTQ would be significantly correlated on the ETI.
This study used clinical data obtained from a larger imaging genetics project whose primary aim was to evaluate group differences in functional magnetic imaging responses in the amygdala by genotype.
Participants were recruited from various community clinics, psychiatric institutions, hospitals, and NGOs. Participants were also recruited through advertising (print, electronic, and media). Participants were recruited over a 3-year period (2010–2013). A total of 109 participants (31 healthy controls, 32 with SAD and moderate/severe EDT, 29 with SAD with low/no EDT, and 17 with PTSD resulting from EDT) were selected in the basis of the presence or absence of SAD/PTSD and the presence/absence of early childhood trauma, using the Mini-International Neuropsychiatric Interview (MINI), the Liebowitz Social Anxiety Scale (LSAS), the Clinician-Administered PTSD Scale (CAPS), and the CTQ. Healthy controls were selected on the basis of absence of any psychiatric disorder and early childhood trauma, as assessed by the MINI and CTQ (a score below 40 on the CTQ), respectively.
The MINI was administered to assess for SAD and PTSD, and exclude comorbid psychiatric conditions, including substance abuse within the previous 12 months of assessment [29]. The LSAS, with a cut-off score of 60, was used to assess for SAD and distinguish between generalized SAD and specific SAD [30]. This clinician-administered questionnaire assesses current social anxiety disorder through 24 questions on a 4-point Likert scale. The CAPS was used to assess for current and lifetime PTSD [31]. The frequency and intensity of PTSD symptoms (as described by the DSM-IV diagnostic criteria) are measured by CAPS on a separate 5-point Likert scales, each ranging from 0 to 4. These ratings are then summarized into a 9-point severity score for each symptom, ranging from 0–8 [32].
The CTQ and ETI were used to assess EDT and to differentiate the low/no and moderate/severe EDT groups with SAD. A score of less than 40 on the CTQ indicated low/no trauma, a score between 40 and 46 was used as a threshold for exclusion, and a score of more than 46 indicated moderate/severe EDT [1]. The CTQ is a robust screening measure of early childhood trauma. It is a retrospective self-report inventory that assesses the five main areas of early developmental trauma: physical abuse, physical neglect, emotional abuse, emotional neglect, and sexual abuse [1]. The ETI is a detailed clinician-administered structured interview that assesses various aspects of developmental trauma: childhood physical abuse, sexual abuse, emotional abuse, and early major adverse life events such as parental loss or serious illness [33]. The ETI provides a structure to systematically assess specific forms of childhood maltreatment. The advantages of using the ETI over the CTQ are that it is able to assess the age of onset, duration, and severity of each trauma, as well as the relationship of the perpetrator to the victim.
The protocol received ethical clearance from the Health Research Ethics Committee at Stellenbosch University, South Africa. The study was conducted according to internationally and locally accepted ethical guidelines, namely, the Declaration of Helsinki and the South African Department of Health's 2004 Guidelines: Ethics in Health Research Structures and Processes. Participation was completely voluntary, and written informed consent was obtained from all participants.
A one-way analysis of variance (ANOVA) was conducted to assess group differences of childhood trauma as measured by the ETI. For significant group differences, Fisher's least significant difference (LSD) post hoc testing was administered. Cross-tabulations between groups (control, SAD with low/no EDT, SAD with moderate/severe EDT, and PTSD) within childhood trauma domains as measured by the ETI were done to calculate the frequency of events experienced, age of onset of abuse, and relationship to perpetrators. Furthermore, nonparametric correlations were performed to assess the significance between childhood trauma on the CTQ (emotional abuse, sexual abuse, physical abuse, emotional neglect, physical neglect, and total childhood trauma) and ETI (general abuse, emotional abuse, physical abuse, sexual abuse, and total childhood trauma). All tests were two-tailed for significance, and significance (p value) was set at .05.
Demographic characteristics
The majority of participants were female (n = 60, 55%), of white ethnicity (n = 72, 66.1%), and single (n = 59, 54.1%). Their age ranged from 20 to 72 years, and the majority had an annual income of more than R60,000 per year (n = 76.8%). The average number of years of education was 15 (SD = 3.2), with a range of 5–24 years, and the majority was employed (n = 71, 65.1%). All participants were fluent in English. With regards to previously diagnosed psychiatric disorder(s), 64 participants had not previously been diagnosed (57.8%), compared to 45 who were previously diagnosed with a psychiatric disorder (41.3%). One participant did not complete the question (0.9%).
Abuse characteristics
Significant group differences (PTSD, SAD with moderate/severe EDT, and controls) were found on the ETI in the domains of physical abuse (p = 0.00), emotional abuse (p = 0.00), sexual abuse (p = 0.00), other childhood trauma (p = 0.00) and total scores (p = 0.00) (Table 1). Fisher's LSD post hoc testing was done to establish between-group differences. There were no significant differences between SAD and PTSD groups. Significant differences in each of the trauma domains (physical abuse, emotional abuse, sexual abuse, other childhood trauma, and total trauma) were found between the PTSD and control groups as well as between SAD and control groups (see Table 2). Although not statistically significant, more general, physical, sexual, and total childhood trauma was experienced by the PTSD group. Only emotional abuse was experienced more in the SAD group.
Table 1 Results of the ANOVAs for differences between groups ( N = 80)
Table 2 LSD post hoc results of ANOVA between groups (PTSD, SAD with moderate/severe EDT, controls)
In the total sample, the most prevalent form of physical abuse reported was being spanked with a hand (n = 96, 88.1%), followed by being hit or spanked with an object (n = 80, 73.4%). This was followed by being burned with a cigarette (n = 53, 48.6%) and being pushed or shoved (n = 42, 38.5%). This is the same order of frequency reported by the SAD with moderate/severe EDT, SAD low/no EDT, and control groups, respectively. For the PTSD group, the most prevalent childhood physical abuse was being hit or spanked with an object (n = 16, 94.1%), followed by being hit with a hand (n = 15, 88.2%), and being burned with a cigarette (n = 9, 52.9%) or pushed or shoved (n = 9, 52.9%) (see Table 3).
Table 3 The frequency of events as measured by the ETI
The most prevalent childhood emotional abuse experienced in the sample was being often shouted or yelled at (n = 58, 53.2%), followed by being often put down or ridiculed (n = 55, 50.5%), and parental failure to understand the participant's needs as a child (n = 53, 48.6%). The most prevalent trauma in the SAD with moderate/severe EDT group, (n = 26, 81.3%)was a lack of understanding of the participant's needs and being often put down or ridiculed bya parent (n = 26). This was followed by often being ignored or made to feel that the person did not count (n = 24, 75%), and often being shouted or yelled at (n = 22, 68.8%). Within the PTSD group, the most prevalent form of emotional abuse experienced as a child was often being shouted or yelled at (n = 12, 70.6%), followed by being put down or ridiculed (n = 11, 64.7%), and often ignored or made to feel like the person did not count (n = 11, 64.7%). The most prevalent emotional abuse experienced in the SAD with low/no EDT group and control groups was being often shouted or yelled at 29% (n = 9) and 51.7% (n = 15), respectively (see Table 3).
The most prevalent form of sexual abuse experienced was being touched in intimate parts in a way that was uncomfortable (n = 30, 27.5%), followed by being exposed to inappropriate comments about sex (n = 28, 25.7%), and being exposed to flashing (n = 22, 20.2). The most prevalent childhood sexual abuse experienced by the SAD with moderate/severe EDT group was exposure to inappropriate comments about sex (n = 13, 40.6%), followed by exposure to flashing (n = 12, 37.5%), and being touched in intimate parts in a way that was uncomfortable (n = 12, 37.5%). The most prevalent sexual abuse experienced by the PTSD group was being touched in intimate parts in a way that was uncomfortable (n = 10, 58.8%), followed by exposure to inappropriate comments about sex (n = 47.1%), and someone trying to have sex with the individual, but not doing so (n = 7, 41.2%). In the SAD group with low/no EDT, the most prevalent childhood sexual abuse experienced was being exposed to inappropriate comments about sex (n = 4, 13.8%). The most prevalent sexual abuse experienced by the control group was being touched in intimate parts in a way that was uncomfortable (n = 6, 19.35%) (see Table 3).
Other childhood traumatic events (defined as general trauma on the ETI)
In the sample as a whole, the most prevalent 'other' childhood traumatic life event was witnessing violence (n = 52, 48.6%), followed by being a victim of major theft (n = 51, 46.5%). This was followed by family mental illness (n = 42, 38.5%) and serious injury/illness of a parent (n = 41, 37.6%). Witnessing violence was the most prevalent traumatic life event in both the SAD with moderate/severe EDT (n = 22, 68.7%) and the PTSD (n = 14, 82.35%) groups. In the SAD with low/no EDT group, the most prevalent traumatic childhood event was being a victim of major theft (n = 13, 44.85), followed by family mental illness (n = 10, 34.5%), and then witnessing violence (n = 9, 31%). In the control group, the most prevalent traumatic childhood event was being a victim of major theft (n = 12, 38.7%) and experiencing a serious personal injury (n = 11, 35.5%) (see Table 3).
In all groups the age of onset of physical and emotional abuse was generally between the age of 6 and 11 years. Sexual abuse in the SAD with moderate/severe EDT and control groups tended to occur between 13 and 18 years of age, while in the PTSD group the age of onset was earlier (6–11 years) (Table 4).
Table 4 Age of onset of childhood traumatic events as measured by the ETI
For physical and emotional abuse, in all groups, the perpetrator was mostly the primary caregiver. In both the SAD with moderate/severe EDT and control groups this was a female caregiver, while for the PTSD group a male primary caregiver was mostly reported. For emotional abuse, the perpetrator most commonly reported by all groups was a female primary caregiver. With regards to the perpetrator of sexual abuse, the most frequently reported perpetrator by all groups was another male adult (Tables 5 and 6).
Table 5 Relationship to perpetrator as measured by the ETI
Table 6 Gender of perpetrators (primary caregivers and other adults)
Correlation between ETI and CTQ
Significant positive correlations were found between all childhood traumas measured on the CTQ (physical abuse, physical neglect, emotional abuse, emotional neglect, and sexual abuse) and the ETI (physical abuse, general abuse, sexual abuse, and emotional abuse) (see Table 7). Nine high correlations (identified as correlation coefficients r > 0.70) were found and are reported in descending order from the strongest correlations to a correlation coefficient of 0.70 [34]. These were (i) childhood emotional abuse (CTQ EA) and total trauma (CTQ total score) (r = 0.87, p = 0.00), (ii) childhood emotional neglect (CTQ EN) and total trauma (CTQ total score) (r = 0.85, p = 0.00), (iii) other traumas experienced during childhood (ETI general trauma score) and total trauma (ETI total score) (r = 0.85, p = 0.00), (iv) emotional abuse during childhood (ETI EA score) and total childhood trauma (ETI total score) (r = 0.76, p = 0.00), (v) childhood physical abuse (CTQ PA) and total childhood trauma (CTQ total score) (r = 0.74, p = 0.00), (vi) childhood physical neglect (CTQ PN score) and total trauma (CTQ total score) (r = 0.73, p = 0.00), (vii) childhood total trauma (CTQ total score) and total trauma on the ETI total score (r = 0.72, p = 0.00), (viii) childhood sexual abuse (CTQ SA) and childhood sexual abuse measured by the ETI (r = 0.71, p = 0.00), and (ix) childhood emotional abuse on the ETI and total trauma on the CTQ (r = 0.70, p = 0.00) (see Table 7).
Table 7 Spearman's nonparametric correlations between childhood traumas measured by CTQ and ETI
The main objective of this study was to investigate differences in the type and amount of childhood trauma in adults with PTSD and SAD. No statistically significant differences were found for these disorders.
This finding suggests that in this sample, childhood traumas (major ALE, physical, sexual, emotional, and total) are not significantly different in individuals with PTSD and SAD with moderate/severe EDT. Previous studies have found that physical abuse [10, 12, 13], sexual abuse [12–18], emotional abuse [19–23], as well as other childhood adversities [24, 25] are linked to the development of both PTSD and SAD. Childhood emotional abuse has been found to correlate more strongly with a diagnosis of social anxiety than either physical or sexual abuse [20]. Previous studies have also documented higher rates of childhood emotional abuse and neglect in adults with SAD compared to healthy controls [21, 22]. Emotional abuse and neglect significantly impact on the development of SAD and PTSD [23]. The results of our study regarding emotional abuse indicates that parents' emotional expression toward their children can have long-lasting effects and contribute to PTSD and SAD in later life. The aforementioned studies, however, did not specifically compare EDT exposure, by severity and type, in these disorders.
With regards to the onset of childhood abuse, Rodriguez et al. in 1996 also found the age of onset of sexual abuse in individuals with PTSD to be around 6 years of age and termination at approximately 13 years, which is similar to our finding in the PTSD group of between 6 and 11 years [27]. This finding is supported by two other studies that found the age of onset of childhood sexual abuse to be approximately 7 years [26] and 9.85 years [28], respectively. There is a paucity of studies on the age of onset of EDT in people with PTSD and SAD, underscoring the need for more investigation in this area to better inform the nature and timing of interventions.
With regards to the perpetrators, our finding of sexual abuse mostly being another nonfamilial male adult is supported by the findings in a previous study of perpetrators of EDT [27]. According to Rodriguez et al. in 1996, perpetrators of CSA in individuals with PTSD were mostly male (87%), nuclear family members, followed by nonfamily members, and lastly by extended family members [27]. Also, Feerick and Snow in 2005 showed in their study that participants were mostly sexually abused by other perpetrators, such as acquaintances, boyfriends, and babysitters, i.e., nonfamilial persons and strangers [28]. Ackerman et al. in 1998 found that if a child was physically abused by a male, the likelihood of a psychiatric diagnosis, including PTSD, was higher than if abused by a female [26]. Overall, physically and sexually abused children were more likely to develop a psychiatric disorder which included PTSD in later life. No further studies focusing on perpetrators of EDT in individuals with SAD or PTSD were found, highlighting a gap that warrants attention in future studies.
ETI and CTQ
All traumas measured by the CTQ were positively correlated with all traumas measured by the ETI. Kuo et al. in 2011 also found that all scales on the CTQ had a significant positive correlation with all subscales, except for sexual abuse and emotional abuse or neglect [21]. Bremner et al. in 2000 tested the convergent validity of the ETI by comparing its domains (physical, sexual, and general) with the components of the Childhood Trauma Severity Index (CLTE) [33]. Significant correlations were calculated between the total score of the ETI and the total score of the CLTE, the physical abuse domain of the ETI and the physical abuse component of the CLTE, as well as between the sexual abuse domain of the ETI and the sexual abuse component of the CLTE [33].
Limitations and recommendations
A number of limitations warrant mention. Firstly, the results of the LSD post hoc testing should be interpreted with caution given that this type of analysis is associated with type 1 error. Secondly, group sizes were small. Thirdly, endorsement of EDT was reliant on the retrospective accounts of participants. This may not always be very accurate with regards to memory recall of traumatic early life events. Recall bias is, therefore, a concern. Recall may also have been affected by the way in which childhood events were assessed [25]. It has been suggested that rather than an exaggeration in the rates, childhood traumas are more likely to be under-reported [35]. In addition, participants varied in age and older participants in particular may have had more difficulty recalling childhood events [36]. The sample may not be demographically representative of the South African population with SAD and PTSD with early trauma. Future studies should include more Black African participants. Furthermore, studies of larger samples that include more qualitative assessments of childhood trauma are needed. In sum, the contribution of EDT to the development of PTSD and SAD and the differences in terms of childhood trauma between these groups, as well as other anxiety disorders, should not be ignored, and attention should be given to the frequency and severity of these events. The relationship between victims of EDT and perpetrators and the age of onset of childhood abuse is another important facet, as it provides a timeline against which the course of abuse and its impact can be tracked over the life trajectory. This can, in turn, provide some guidance to clinicians on the optimal timing and nature of interventions for the prevention of PTSD and SAD.
Bernstein DP, Fink L: Childhood Trauma Questionnaire: a Retrospective Self-Report. Manual. 1998, San Antonio, TX: Psychological Corporation
Brown GW, Harris TO: Aetiology of anxiety and depressive disorders in an inner-city population. Psychol Med. 1993, 23: 143-154. 10.1017/S0033291700038939.
Heim C, Nemeroff CB: The role of childhood trauma in the neurobiology of mood and anxiety disorders: preclinical and clinical studies. Biol Psychiatry. 2001, 49: 1023-1039. 10.1016/S0006-3223(01)01157-X. doi:S0006-3223(01)01157-X
Kendler KS, Hetteman JM, Butera F, Gardner CO, Prescott CA: Life events dimensions of loss, humiliation, entrapment, and danger in the prediction of onsets of major depression and generalized anxiety. Arch Gen Psychiatry. 2003, 60: 789-796. 10.1001/archpsyc.60.8.789.
Prigerson HG, Shear MK, Bierhals AJ, Zonarich DL, Reynolds CF: Childhood adversity, attachment and personality styles as predictors of anxiety among elderly caregivers. Anxiety. 1996, 2: 234-241. 10.1002/(SICI)1522-7154(1996)2:5<234::AID-ANXI5>3.0.CO;2-M.
Herman A, Stein D, Seedat S, Heeringa S, Moomal H, Williams D: The South African Stress and Health [SASH] study: 12 month and lifetime prevalence of common mental disorders. S Afr Med J. 2009, 99 (5): 339-344.
PubMed Central PubMed Google Scholar
Gilbert R, Widom CS, Browne K, Fergusson D, Webb E, Janson S: Burden and consequences of child maltreatment in high- income countries. Lancet. 2008, 373: 68-81. doi:10.1016/S0140-6736(08)61706-7
Stein MB, Walker JR, Anderson G, Hazen AL, Ross CA, Eldridge G, Forde DR: Childhood physical and sexual abuse in patients with anxiety disorders and in a community sample. Am J Psychiatry. 1996, 153 (2): 275-277.
Lieb R, Wittchen HU, Hofler M, Fuetsch M, Stein MB, Marikangas KR: Parental psychopathology, parenting styles and the risk of social phobia in offspring. Arch Gen Psychiatry. 2000, 57: 859-866. 10.1001/archpsyc.57.9.859.
Koenen KC, Moffitt TE, Poulton R, Martin J, Caspi A: Early childhood factors associated with the development of post-traumatic stress disorder: results from a longitudinal birth cohort. Psychol Med. 2007, 37 (2): 181-192. 10.1017/S0033291706009019.http://dx.doi.org/10.1017/S0033291706009019,
Cougle JR, Timpano KR, Sachs-Ericsson N, Keough ME, Riccardi CJ: Examining the unique relationships between anxiety disorders and childhood physical and sexual abuse in the National Comorbidity Survey-Replication. Psychiatry Res. 2010, 177: 150-155. 10.1016/j.psychres.2009.03.008.
Gelinas D: The persisting negative effects of incest. Psychiatry. 1983, 46: 312-322.
Goodwin J: Post-traumatic stress in incest victims. Post-traumatic Stress Disorder in Children. Edited by: Eth S, Pynoos RS. 1985, Washington, DC: American Psychiatric Association
Bandelow B, Torrente A, Wedekind D, Broocks A, Hajak G, Rutter E: Early traumatic life events, parental rearing styles, family history of mental disorders, and birth risk factors in patients with social anxiety disorder. Eur Arch Psychiatry Clin Neurosci. 2004, 254: 397-405. 10.1007/s00406-004-0521-2.
Briere JN, Elliott DM: Immediate and long-term impacts of child sexual abuse. Future Child. 1994, 4 (2): 54-69. 10.2307/1602523.http://dx.doi.org/10.2307/1602523,
Cutajar MC, Mullen PE, Ogloff JRP, Thomas SD, Wells DL, Spataro J: Psychopathology in a large cohort of sexually abused children followed up to 43 years. Child Abuse Negl Int J. 2010, 34 (11): 813-822. 10.1016/j.chiabu.2010.04.004.
Kendler KS, Kessler RC, Walters E: Stressful life events, genetic liability and onset of an episode of major depression. Am J Psychiatr. 1995, 152: 833-842.
Magee WJ: Effects of negative life experiences on phobia onset. Soc Psychiatry Psychiatr Epidemiol. 1999, 34: 343-351. 10.1007/s001270050154.
Bruch MA, Heimberg RG: Differences in perceptions of parental and personal characteristics between generalized and nongeneralised social phobics. J Anxiety Disord. 1994, 8: 155-168. 10.1016/0887-6185(94)90013-2.
Gibb B, Chelminiski I, Zimmerman M: Childhood emotional, physical, and sexual abuse, and diagnoses of depressive and anxiety disorders in adult psychiatric outpatients. Depress Anxiety. 2007, 24: 256-263. 10.1002/da.20238.
Kuo JR, Goldin PR, Werner K, Heimberg RG, Gross JJ: Childhood trauma and current psychological functioning in adults with social anxiety disorder. J Anxiety Disord. 2011, 25 (4): 467-473. 10.1016/j.janxdis.2010.11.011. doi:10.1016/j.janxdis.2010.11.011
Simon NM, Herlands NN, Marks EH, Macini C, Letamendi A, Li Z, Pollack MH, Van Ameringen M, Stein MB: Childhood maltreatment linked to greater symptom severity and poorer quality of life and function in social anxiety disorder. Depress Anxiety. 2009, 26: 1027-1032. 10.1002/da.20604.
Suliman S, Mkabile SG, Fincham DS, Ahmed R, Stein DJ, Seedat S: Cumulative effect of multiple trauma on symptoms of posttraumatic stress disorder, anxiety, and depression in adolescents. Compr Psychiatry. 2009, 50 (2): 121-127. 10.1016/j.comppsych.2008.06.006.http://www.sciencedirect.com/science/article/pii/S0010440X08000916,
Afifi TO, Boman J, Fleisher W, Sareen J: The relationship between child abuse, parental divorce, and lifetime mental disorders and suicidality in a nationally representative adult sample. Child Abuse Negl. 2009, 33 (3): 139-147. 10.1016/j.chiabu.2008.12.009.http://www.sciencedirect.com/science/article/pii/S0145213409000301,
Binelli C, Ortiz A, Muñiz A, Gelabert E, Ferraz L, Filho AS, Crippa JA, Nardi AE, Subira S, Martin-Santos R: Social anxiety and negative early life events in university students. Rev Bras Psiquiatr. 2012, 34: S69-S74.
Ackerman P, Newton J, McPherson W, Jones J, Dykman R: Prevalence of post traumatic stress disorder and other psychiatric diagnoses in three groups of abused children (sexual, physical, and both). Child Abuse Negl. 1998, 22 (8): 759-774. 10.1016/S0145-2134(98)00062-3.
Rodriguez N, Ryan S, Rowan A, Foy D: Posttraumatic stress disorder in a clinical sample of adult survivors of childhood sexual abuse. Child Abuse Negl. 1996, 20: 943-952. 10.1016/0145-2134(96)00083-X.
Feerick MM, Snow KL: The relationship between childhood sexual abuse, social anxiety disorder, and symptoms of posttraumatic stress disorder in women. J Fam Violence. 2005, 20 (6): 409-419. 10.1007/s10896-005-7802-z. doi:10.1007/s10896-005-7802-z
Sheehan DV, Lecrubier Y, Sheehan KH, Amorim P, Janavs J, Weiller E, Hergueta T, Baker R, Dunbar GC: The Mini-International Neuropsychiatric Interview (M.I.N.I.): the development and validation of a structured diagnostic psychiatric interview for DSM-IV and ICD-10. J Clin Psychiatry. 1998, 59: 22-33.
Baker S, Heinrichs N, Kim H, Hofmann S: The Liebowitz social anxiety scale as a self-report instrument: a preliminary psychometric analysis. Behav Res Ther. 2002, 40 (6): 701-715. 10.1016/S0005-7967(01)00060-2.
Blake DD, Weathers F, Nagy LM, Kaloupek DG, Klauminzer G, Charney DS, Keane TM: A clinician rating scale for assessing current and life-time PTSD: the CAPS-1. Behav Ther. 1990, 13: 187-188.
Weathers FW, Keane TM, Davidson JT: Clinician-administered PTSD scale: a review of the first ten years of research. Depress Anxiety. 2001, 13 (3): 132-156. 10.1002/da.1029.
Bremner JD, Vermetten E, Mazure CM: Development and preliminary psychometric properties of an instrument for the measurement of childhood trauma: the early trauma inventory. Depress Anxiety. 2000, 12 (1): 1-12. 10.1002/1520-6394(2000)12:1<1::AID-DA1>3.0.CO;2-W. 1091–4269
Howell DC: Fundamental Statistics for the Behavioural Sciences. 2008, Australia: Thomson Wadsworth, 6
Hardt J, Rutter M: Validity of adult retrospective reports of adverse childhood experiences: review of the evidence. J Child Psychol. 2004, 45 (2): 260-273. 10.1111/j.1469-7610.2004.00218.x.
Spila B, Makara M, Kozak G, Urbańska A: Abuse in Childhood and Mental Disorder in Adult Life. 2008, Canada: Wiley
This work is based on the research supported by the South African Research Chairs Initiative of the Department of Science and Technology and the National Research Foundation of South Africa.
Department of Psychiatry, Faculty of Medicine and Health Sciences, Tygerberg Campus, Stellenbosch University, Cape Town, 7505, South Africa
Melanie Bishop, David Rosenstein, Susanne Bakelaar & Soraya Seedat
Melanie Bishop
David Rosenstein
Susanne Bakelaar
Soraya Seedat
Correspondence to Melanie Bishop.
MB participated in drafting and revising the manuscript, data analysis, interpretation of data, made a substantial contribution to the acquisition of data, and ensured that questions related to the accuracy of the work are appropriately resolved. DR participated in the design of the study, performed statistical analysis, critically revising the manuscript, and made a substantial contribution on the acquisition of data (all clinical data). SB participated in the design of the study, data acquisition, and critically revising the manuscript. SS conceptualized the study and made substantial contributions to the conception and design, analysis of data, revised the manuscript, and provided the final approval of the version to be published. All authors read and approved the final manuscript.
Bishop, M., Rosenstein, D., Bakelaar, S. et al. An analysis of early developmental trauma in social anxiety disorder and posttraumatic stress disorder. Ann Gen Psychiatry 13, 16 (2014). https://doi.org/10.1186/1744-859X-13-16
Early developmental trauma


text:
UMBC Transit
MARC Alert: Penn Line Schedule Change Update
MARC Train appreciates your continued patience with the first days of operation of the new Penn Line schedule. While morning service is operating very well, we recognize that there are challenges in the afternoon and are working to address them. MARC Train and Amtrak management are actively engaged and have managers at key stations to monitor service.
As stated yesterday, we recognize that Train 634 (4:57pm departure from Union Station) is a very crowded train. An additional railcar is now operating on this train, however we cannot add any more cars beyond this extra car. Passengers have asked why this train cannot depart earlier. The fact is that due to the trackwork, no MARC Penn Line trains can depart Union Station between 4:25pm and 4:57pm. This is because there is no way for Amtrak Acela Express and Regional trains to pass MARC trains between Washington and Odenton. The gap between Train 440 (5:28pm) and 642 (5:57pm) is for the same reason.
--Passengers on Train 634 traveling from Union Station to Odenton are strongly encouraged and requested to wait 15 minutes for Train 536 (5:12pm departure). Train 536 arrives at Odenton just 9 minutes after Train 634, operates non-stop from Washington to Odenton, and has ample available seating. By switching to Train 536, Odenton passengers will provide adequate space on Train 634 for passengers who do not have other options and would have to wait between 45 minutes and an hour for the next train to their station.
--Passengers traveling on Train 634 to BWI, Halethorpe, Penn Station, and Martin Airport are requested to ride in the first four cars at the front of the train (the cars directly behind the locomotive) in order to provide adequate space for passengers traveling to Seabrook and Bowie State University, who must ride in the last three cars of the train (the three cars closest to the station in Washington) due to short platforms.
--Bowie State University passengers should note that Train 438 (the 5:25pm departure) now operates non-stop from Union Station to Bowie. Passengers for BWI and Halethorpe are requested to ride in the first four cars at the front of the train (the cars directly behind the locomotive) in order to accommodate Bowie State University passengers, who must ride in the last three cars of the train due to the short platform. We understand that there was confusion yesterday on Train 438 and have verified with Amtrak that Bowie State passengers should be in rear of the train.
Again, MARC Train and Amtrak management are actively engaged and will consider further adjustments as needed. We appreciate your patience and understanding and thank you for riding MARC Train.
Maryland Department of Transportation
UMBC Transit Weather Contingency Plan - Saturday - 01.18.20
Downtown Route - Service Delays 01/11/20
UMBC Transit Weather Contingency Plan - Tuesday - 01.07.20
Service at Pratt & Howard Street - Downtown Route Restored
UMBC Transit Weather Contingency Plan - Monday - 12.16.19

redpajama_set_name: RedPajamaCommonCrawl


text:
\section{Introduction}
\cite{NTK}'s pioneering work showed that a multi-layer perceptron (MLP) trained by gradient descent (GD) evolves like a linear model.
This spurred a flurry of research papers using this insight to tackle the core questions in deep learning theory, from optimization to generalization in both finite and infinite width regimes.
\cite{NTK}'s argument consists of two observations:
\begin{description}
    \item[\textsc{ntkInit}\label{NTKinit}] For the output of a network $f(\xi;w)$ with parameters $w$ given example $\xi$, \cite{NTK} identified the kernel $\mathcal{K}(\xi,\bar{\xi}) = \langle \nabla f(\xi;w),\nabla f(\bar{\xi},w) \rangle$, known as the \emph{Neural Tangent Kernel (NTK)}.
    They showed that if $f$ is parametrized and initialized appropriately, then $\mathcal{K}$ converges to a deterministic kernel $\mathring{\mathcal{K}}$ as the width of the network tends to infinity.
    \item[\textsc{ntkTrain}\label{NTKtrain}] As the infinitely wide network is trained by gradient descent, the NTK remains frozen in its initial state, and the network evolves as by kernel gradient descent with kernel $\mathring{\mathcal K}$
\end{description}

In \cite{yang2}, the \ref{NTKinit} property was proven to hold for \emph{standard architectures}, meaning any composition of MLPs, recurrent neural networks (RNN), LSTMs \cite{lstm}, gated recurrent unit (GRU) \cite{gru}, convolutions \cite{conv2,conv1,conv3,conv4,conv5}, residual connections \cite{res1,res2}, batch normalization \cite{bn}, graph neural networks \cite{graph1,graph2,graph3,graph4,graph5} and attention \cite{attention1,attention2}, along with arbitrary weight sharing between components.
More generally, it holds for any architecture expressible in a so-called \emph{Tensor Program} \cite{yangScalingLimit,yang,yang2,yang3}, of which the standard architectures are a subset.
However, their reasoning is limited to initialization only.

A statement is \emph{architecturally universal} if it holds for any \emph{reasonable} neural architecture.
This is an informal property, but here we will formalize it by taking \emph{reasonable} to be ``expressable in Tensor Programs.''
By the expressiveness of such programs \citep{yang,yang2}, architectural universality is a fairly robust notion that covers present (and, we expect, future) architectures comprehensively.
In this terminology, \citep{yang2} showed that \ref{NTKinit} is architecturally universal.

\paragraph{Our Contribution}
We show the architectural universality of the entire NTK theory by proving \ref{NTKtrain} for the same architectures discussed above, including all standard architectures.
In the process, we introduce a new graphical form of Tensor Programs that is both required in our proofs and useful for the pedagogy of Tensor Programs.

\paragraph{The Tensor Program Series} This paper follows \cite{yangScalingLimit,yang,yang2,yang3,yang4} in the series.
While we number this paper ``IIb'' right after \cite{yang2}, we actually need the complete theoretical foundation developed in III \cite{yang3}.
See \cref{footnote:relyonTP3} for more details.

\section{Background}\label{sec:3}
Let $f(\xi;w) \in \mathbb{R}$ denote the (scalar) output of a neural network parameterized by $w$, given example $\xi$. To understand how the output changes with a slight change in the network parameters $w_0 - \delta w$, we may naively expand the network function using the first order Taylor expansion around a base point $w_0$:
\begin{align}
    f(\xi,w_0 - \delta w) - f(\xi;w_0) \approx \langle\nabla_wf(\xi,w_0),\delta w\rangle.
    \label{eqn:FOTaylor}
\end{align}
Under the SGD algorithm, the weight update $\delta w$ is given by the gradient $\delta w = -\eta \chi(\hat{\xi})\nabla_wf(\hat{\xi};w_0)$ where $\chi(\hat{\xi})$ is the loss derivative, $\hat{\xi}$ is a sample from the training set, and $\eta$ is the learning rate.
Plugging into \cref{eqn:FOTaylor}, we get:
\begin{align}\label{ntk}
    f(\xi,w_0 - \delta w) - f(\xi;w_0) \approx -\eta \chi(\hat{\xi})\mathcal{K}(\xi,\hat{\xi}).
\end{align}
where $\mathcal{K}(\xi,\hat{\xi}) = \langle\nabla_wf(\xi;w_0),\nabla_wf(\hat{\xi};w_0)\rangle$ is the NTK.
The NTK theory of infinitely wide neural networks as first proposed by \cite{NTK} boils down to the the following observations:
\emph{When the width of $f$ tend to infinity, the NTK $\mathcal K$ converges to a fixed kernel $\mathring{\mathcal K}$ at random initialization, independent of the specific instantiation of the weights,
and remains frozen during the optimization process.}
\cref{ntk} then gives an accurate description of the output evolution with if we substitue $\mathcal K$ with $\mathring{\mathcal{K}}$.
The seemingly complex optimization trajectory of SGD therefore reduce to the convex trajectory of kernel gradient descent with a time-independent kernel $\mathring{\mathcal{K}}$.\\
Consider the output of the network $f\in \mathbb{R}^D$ on the full training dataset. As shown in \cite{NTK}, when the $L2$ loss is used the evolution of the output $f_t$ at time $t$ under continuous time GD (i.e.\ gradient flow) takes a simple form:
\begin{align*}
    f_t - f^\star = e^{-\eta \mathring{\mathcal{K}} t}(f_0 - f^\star).
\end{align*}
where $\mathring{\mathcal{K}}\in \mathbb{R}^{D\times D}$ is the full NTK matrix evaluated on the training data, $f^\star$ is the label function,  and $f_0$ is the output at initialization.
Hence, provided $\mathring{\mathcal{K}}$ is full rank, as $t \to \infty$ we have that $f_t \to f^\star$, and the network can fit the training data perfectly.

\paragraph{Previous Approaches vs Ours}
A common theme in showing \ref{NTKtrain} for MLP is to derive high-probability bounds on the deviation of the NTK $\mathcal K$ from its initial value after training
(e.g. \citet{allen-zhu_convergence_2018,du_gradient_2018,zou_stochastic_2018}).%
\footnote{
In the original NTK paper \citep{NTK}, the limit is taken as each layer width goes to infinity sequentially, which already doesn't make sense for weight-tied architectures like RNNs.
}
Obtaining these bounds usually requires developing ad hoc methods on a per-architecture basis, hindering the scalability of the method to other settings.
In the present work we take a more holistic approach, leveraging the recently developed Tensor Programs framework \cite{yangScalingLimit,yang,yang2,yang3}.
It consists of two layers of arguments:
1) The bottom layer analyzes how the \emph{distribution of (pre-)activations} change throughout the course of training;
this crucially leverages the mathematical machinery of the Tensor Programs Master Theorem.%
\footnote{In particular, we need to use the Master Theorem in \citep{yang3}, so \citep{yang2} could not have obtained \ref{NTKtrain} at the same time as \ref{NTKinit}.}
2) The top layer packages these insights systematically via the notion of \emph{paths} so as to apply to any architecture expressible by a Tensor Program.
We will illustrate 1) through examples in \cref{sec:examples} and 2) through figures in \cref{sec:proofsketch}.

\paragraph{Setup and Notations}\label{notations}
In this paper, we will consider the architecture (including depth), data, and training time to be fixed as width $n\to\infty$.%
\footnote{They will affect the rate of convergence to the infinite-width limit, but since we are only concerned with whether convergence occurs, they do not appear in our theorem statements here.}
We describe common notations used in the remainder of the paper.
For simplicity, we will consider SGD with batch size 1 and learning rate $\eta$ (often set to 1 WLOG).%
\footnote{This generalizes readily to any batch size and learning rate.}
We use $\xi_t$ to denote the input and $\mathcal L_t$ to denote the loss function (absorbing the label) at step $t$.
More generally, subscript $t$ on any symbol means \emph{time $t$}.
However, for brevity, we abuse notation and shorthand $f_t$ for $f_t(\xi_t)$, and, for any (pre-)activation $x$, $x_t$ for $x_t(\xi_t)$.%
\footnote{We will not refer to the \emph{function} $x_t: \xi \to x_t(\xi)$ (likewise for $f_t, \chi_t$), so this abuse of notation should cause no confusion.}
We will also write $\chi_t$ for the loss derivative $\mathcal L_t'(f_t)$.
For any vector $x(\xi)$ we define $\delta x_{t+1}(\xi) \mathrel{\raisebox{-0.3ex}{$\odefeq$}} \sqrt{n}\big(x_{t+1}(\xi) - x_t(\xi)\big)$ and $dx(\xi) \mathrel{\raisebox{-0.3ex}{$\odefeq$}} \sqrt{n}\frac{\partial f(\xi)}{\partial x(\xi)}$.
We will track the evolution of $f$ on an arbitrary input $\tilde \xi$.%
\footnote{It might help to think of $\tilde \xi$ as some \emph{test sample}, but it can also fall in the training set.}
Similar to above, we shorthand $\tilde{x}_t,\tilde{f}_t$ for $x_t(\tilde \xi), f_t(\tilde x)$.

\section{Motivating Examples}\label{sec:examples}
The purpose of this section is to illustrate our key ideas via simple, intuitive examples without diving into the specifics of Tensor Programs.
In the process, we will gain insight into how randomness from initialization propagates over the course of training.
As these examples intend to provide the reader with the proper intuition, we use informal arguments alone and relegate all formal statements to the appendix.
For brevity, we will gloss over minor details or routine calculations, but interested readers can see \cref{sec:appebdix_extra} for these omissions.

\paragraph{Key Idea}
It turns out that the random initialization and the overparametrization of weights cause each (pre-)activation vector $x_t(\xi)\in \R^n$, its gradient $dx_t(\xi)\in \R^n$, and its (scaled) change $\delta x_t(\xi) \in \R^n$ every time step $t$ to have roughly iid coordinates, not just initially but \emph{throughout training}.%
\footnote{This is a consequence of the Tensor Program Master Theorem.}
Then, as we shall demonstrate through the examples below, to track the evolution of the neural network function, it suffices to track the evolution of the coordinate distributions of $x(\xi)$, $dx(\xi)$, $\delta x(\xi)$.
We write $Z^{x(\xi)}$, $Z^{dx(\xi)}$, $Z^{\delta x(\xi)} \in \mathbb{R}$ for the random variables corresponding to such coordinate distributions.%
\footnote{As we will explain below, different $Z$s may correlate, reflecting correlations between corresponding vectors.}

Our goal is to derive, from these insights,
\begin{restatable}{claim}{claimNTK}
    \label{claim:NTK}
In the large width limit, $\tilde f_t = f_t(\tilde \xi)$ changes by
\begin{align}\label{kernel_d_1}
    \lim_{n\to\infty} \tilde{f}_{t+1} - \tilde{f}_t = -\mathring\chi_t \mathring{\mathcal{K}}(\tilde{\xi},\xi_t)
\end{align}
at step $t$, where $\mathring{\mathcal{K}}$ is the limiting NTK of the architecture and $\mathring\chi_t = \mathcal L_t'(\lim_{n} f_t)$ is the loss derivative.
\end{restatable}

We start with an example derivation for 1-hidden-layer MLP, before moving on to 2-hidden-layers, where the mathematics quickly become much more involved.

\subsection{1 Hidden Layer}

\label{sec:1LP}

Consider a 1-hidden-layer network with nonlinearity $\phi$:
\begin{align*}
f = V^\top x ,~~~x = \phi(h) ,~~~ h = U\xi
\end{align*}
where $\xi \in \mathbb{R}^d,~ U = \frac{u}{\sqrt{d}} \in \mathbb{R}^{n \times d},~V = \frac{v}{\sqrt{n}} \in \mathbb{R}^{n \times 1}$, for trainable parameter tensor $u$, initialized iid from $\Gaus(0,1)$.
In the interest of clarity we assume the output layer is not trained, and $d=1$.

For a vector $v \in \R^n$, let $v = \Theta(n^{a})$ mean that ``$v$ has coordinates of order $n^a$ when $n$ is large''%
\footnote{\label{foot:vecbigO}
    More rigorously, we mean that $\|v\|^2 / n = \Theta(n^{2a})$.
    Note this is \emph{different} from the common interpretation that $\|v\| = \Theta(n^{a})$.
};
likewise for $o(n^a)$, etc.
Recall the notations $x_t = x_t(\xi_t), \tilde x_t = x_t(\tilde \xi), \delta x_t = \sqrt n(x_t - x_{t-1})$ and likewise for $h_t, \tilde h_t, \delta h_t$.
The key insights are as follows:
\paragraph{Preliminary Calculations}
It turns out $\tilde x_{t+1} - \tilde x_t = \Theta(1/\sqrt n) = o(1)$ so $\delta \tilde x_{t+1} = \sqrt n (\tilde x_{t+1} - \tilde x_t))$ has $\Theta(1)$ coordinates.
Likewise for $\delta \tilde h_{t+1}$.
Consequently, for any $t$ and input $\xi$,
by telescoping,
\begin{align}
    h_t(\xi)
        &= h_0(\xi) + o(1).
        \label{eqn:g0}
\end{align}
Using $\nabla_u f = \frac{1}{\sqrt n} dh_t \xi_t^\top$
and $dh_t = \phi'(h_t) \odot v$, we have:
\begin{align}\label{1delta}
    \delta\tilde{h}_{t+1}
    = -\chi_t\xi_t^\top \tilde{\xi} \phi'(h_t)\odot v.
\end{align}
Also, $\delta\tilde{x}_{t+1} = \sqrt{n}\big(\phi(\tilde{h}_t + \frac{\delta\tilde{h}_{t+1}}{\sqrt{n}}) - \phi(\tilde{h}_t)\big)$.
Since $\delta \tilde h_{t+1} = \Theta(1)$, by intuitive Taylor expansion, we have
\begin{align}\label{1limit}
    \delta\tilde{x}_{t+1} &\approx \phi'(\tilde{h}_t)\odot \delta\tilde{h}_{t+1}.
\end{align}
The change in the output on example $\tilde{\xi}$ from step $t$ to step $t+1$ is given by:
\begin{align}\label{1dynamics}
    \tilde{f}_{t+1} - \tilde{f}_t = V^\top (\tilde{x}_{t+1} - \tilde{x}_t) = v^\top \delta\tilde{x}_{t+1}/n
\end{align}

\paragraph{IID Coordinates}
By definition $v$ has iid coordinates. It turns out $h_t(\xi), \delta h_t(\xi)$ (likewise for $x$) all have approx.\ iid coordinates of size $\Theta(1)$ as well.%
\footnote{Technically, they have iid coordinates only after conditioning on the initial function (GP) $f_0$.
Likewise, when we take expectation in this example (e.g.\ \cref{eqn:1LPexpectation,{eqn:dot}}), it's a conditional expectation of this kind.
See \cref{subsub:first_pass} for a rigorous treatment.
However, to convey the main intuition, we gloss over this technicality here.
\label{foot:condition}}
Let $Z^{\delta \tilde x_t}, Z^v$ denote the random variables encoding the corresponding coordinate distributions; likewise for the other vectors.
Note that $Z^{\delta \tilde x_t}, Z^v$ will in general be correlated, reflecting the coordinatewise correlation between $v$ and $\delta \tilde x_{t}$.

\paragraph{Law of Large Numbers}
and \cref{1dynamics,1delta} imply,
\begin{align}
    &\phantom{{}={}}\lim_{n\to\infty} \tilde{f}_{t+1} - \tilde{f}_t
    = \EV Z^v Z^{\delta \tilde x_{t+1}}
    \label{eqn:fdelta=EZZ}
    \\
    &= -\mathring\chi_t \xi_t^\top \tilde{\xi} \EV \phi'(Z^{\tilde h_t}) \phi'(Z^{h_t}) (Z^v)^2.
    \label{eqn:1LPexpectation}
\end{align}
where $\mathring\chi_t = \mathcal L_t'(\lim_{n} f_t)$ as in \cref{claim:NTK}.

\paragraph{Kernel Expression as Gaussian Expectation}
By \cref{eqn:g0}, in the $n\to\infty$ limit, $Z^{\tilde h_t} = Z^{h_0(\tilde \xi)}$ and $Z^{h_t} = Z^{h_0(\xi_t)}$.
They are independent from $Z^v$ and jointly Gaussian with variances $\|\tilde \xi\|^2, \|\xi_t\|^2$ and covariance $\tilde \xi^\trsp \xi_t$.
So (using the initialization of $v$ to simplify $\EV (Z^v)^2 = 1$),
\begin{align}
    \lim_{n\to\infty} \tilde{f}_{t+1} - \tilde{f}_t
    &= -\mathring\chi_t \xi_t^\top \tilde{\xi} \EV \phi'(Z^{h_t}) \phi'(Z^{\tilde{h}})\label{ntk1}
\end{align}
This can easily be seen to be \cref{kernel_d_1} (recall we assumed for simplicity the output layer $V$ is not trained).

\paragraph{Summary}
Our strategy so far has been computing the form of $Z^{\delta \tilde{x}_{t}}$ and plugging it into \cref{eqn:fdelta=EZZ} to compute the dynamics of the output in the limit.
Note that our approach differs from previous work which mainly focus on proving a bound on the change of the NTK post training.
As the architecture gets more complex, bounding the NTK movement becomes quite complex, but our approach easily scales due to the automation provided by the \emph{Tensor Programs} framework (see \cref{sec:TP}).

In the previous example, the coordinate distribution $Z^{\tilde{x}_{t}}$ took a fairly simple form, which allowed us to intuitively compute the expectation $\EV Z^{\tilde{x}_{t}} Z^v$. Before introducing a method for computing coordinate distributions in a general architecture, we move on to a slightly more involved architecture, with the intention of highlighting the intuition behind the general case.

\subsection{2 Hidden Layers}
\label{sec:2LP}

In this example we consider a model of the form:
\begin{gather*}
f = V^\top x ,~~~x = \phi(h) ,~~~ h = W z\\
z = \phi(g) ,~~~ g = U\xi
\end{gather*}
where $U = \frac{u}{\sqrt{d}} \in \mathbb{R}^{n \times d},~W = \frac{w}{\sqrt{n}} \in \mathbb{R}^{n \times n},~V = \frac{v}{\sqrt{n}} \in \mathbb{R}^{n \times 1}$, for trainable parameters $u,w$, initialized iid from a normal distribution. As before we assume the last layer is not trained, and $d=1$.

Again, we want to establish \cref{claim:NTK} for this model.
As in the 1-hidden-layer example, the dynamics of the output in the limit is still given by \cref{eqn:fdelta=EZZ}.
This time around, the second hidden layer adds nontrivial complexity when evaluating the expectation $\EV Z^vZ^{\delta \tilde{x}_{t+1}}$. As we shall see, this complexity arises from the dependency of $\tilde{x}$ on the $n\times n$ matrices $w$ and $w^\top$, which will make it \emph{wrong} to naively apply LLN arguments. Resolving this complexity will pave the way to a general strategy which we will then be able to apply in any arbitrary architecture.
We now apply the same insights as in the 1-hidden-layer MLP. Namely:

\begin{itemize}
    \item \cref{eqn:g0} continues to hold with $h$ replaced by any of $\{x,h,z,g\}$.
\item After some brief calculations, with $dh_t$ denoting the scaled gradient $\sqrt n \nabla_{h_t} f$,
    \begin{align}
        \delta\tilde{g}_{t+1}
            &\approx -\chi_t\xi_t^\top \tilde{\xi}  \phi'(g_t) \odot \big(W^\top dh_t\big)\label{deltap}\\
        \delta\tilde{h}_{t+1}
            &\approx W\delta \tilde{z}_{t+1} - \chi_t \frac{z_t^\top \tilde{z}_t}{n}\phi'(h_t)\odot v \label{deltag}.
    \end{align}

    \item
    As in the 1-hidden-layer case, for all $x \in \{g,z,h,x\}$, $x_t(\xi),\delta x_t(\xi)$ have iid coordinates of size $\Theta(1)$, as does $v$ by definition.%
    \footnote{Again, this is technically true only after conditioning on $f_0$; see \cref{foot:condition}.}
    Let $Z^{\delta \tilde x_t}, Z^v$ denote the (generally correlated) random variables encoding the corresponding coordinate distributions.
    \item As in \cref{1dynamics}, by naive Taylor expansion we have:
    \begin{align}
        \delta\tilde{z}_{t+1} &\approx \phi'(\tilde{g}_{t})\odot \delta\tilde{g}_{t+1}.\label{deltaq}
    \end{align}
    \item \cref{1dynamics,1limit} in the 1-hidden-layer case continue to hold here.
    Then by \cref{deltag} and Law of Large Numbers,
    \begin{align}
        &\phantom{{}={}}\lim_{n\to\infty} \tilde{f}_{t+1} - \tilde{f}_t
        = \EV Z^v Z^{\delta \tilde x_{t+1}}
        \label{eqn:fdelta=EZZ_2}
        \\
        &= - \mathring \chi_t \xi_t^\top \tilde{\xi}
        \EV [Z^{z_t}Z^{\tilde{z}}]
        \EV [\phi'(Z^{h_t})\phi'(Z^{\tilde{h}})]
        \label{eqn:2LPlayer2NTK}\\
        &\phantom{{}={}}- \mathring \chi_t \xi_t^\top \tilde{\xi}\EV[\phi'(Z^{\tilde{h}_t})Z^{W\delta \tilde{z}_{t+1}}Z^v].
        \label{eqn:1LPexpectation_2}
    \end{align}
    where $\mathring\chi_t = \mathcal L_t'(\lim_{n} f_t)$ as in \cref{claim:NTK}.
\end{itemize}
In this expression, the first term (\cref{eqn:2LPlayer2NTK}) can easily be seen to correspond to the contribution from $w$ to the NTK.
It remains to show that the second (\cref{eqn:1LPexpectation_2}) corresponds to the contribution from $u$.

\paragraph{Challenge of Analyzing \cref{eqn:1LPexpectation_2}}
To do this, we must reason about the coordinate distribution of $W\delta\tilde{z}_{t+1}$ (encoded by random variable $Z^{W\delta\tilde{z}_{t+1}}$) and compute the expectation in \cref{eqn:1LPexpectation_2}.
To understand why this represents a greater challenge than it might first appear, note that from $\delta\tilde{z}_{t+1} \approx \phi'(\tilde{g}_{t})\odot \delta\tilde{g}_{t+1}$ (\cref{deltaq}), the term ${W\delta\tilde{z}_{t+1}}$ hides within itself a dependency on $W^{\top}dh_t$ through $\delta\tilde{g}$ (\cref{deltap}).
While at $t=0$, we may assume $W^\trsp$ be independent of $W$ and obtain the correct results (Gradient Independent Assumption \citep{yangMFResnet,yang2}), this is no longer the case for $t>0$:
$Z^{W\delta\tilde{z}_{t+1}}$ will be nontrivially correlated with $\phi'(Z^{\tilde{h}_t})$ and $Z^v$ (which would be false if $W^\trsp$ can be assumed independent of $W$).
We will give some intuition why later in \cref{eqn:WWtrspExample}.
Now, what is this dependence exactly?
\begin{restatable}{claim}{claimZdot}
    \label{claim:Zdot}
    Based on the above discussion and some easy calculations, $\delta\tilde{z}_{t+1}$ can be written as $\Phi(W^\top dh_t)$ for some $\Phi: \R \to \R$ applied coordinatewise (which will depend on other vectors not of the form $W^\trsp \bullet$).
    Then it turns out\footnotemark[\value{footnote}]
    \begin{align}\label{eqn:dot}
        Z^{W\delta\tilde{z}_{t+1}} = G + Z^{dh_t}\EV \frac{\partial Z^{\delta\tilde{z}_{t+1}}}{\partial Z^{W^\top dh_t}},
    \end{align}
    where $G$ is some Gaussian variable independent from $Z^v$, and $\frac{\partial Z^{\delta\tilde{z}_{t+1}}}{\partial Z^{W^\top dh_t}} \mathrel{\raisebox{-0.3ex}{$\odefeq$}} \Phi'(Z^{W^\top dh_t})$.
\end{restatable}
\paragraph{Getting \cref{claim:NTK}}
Thus, from
\cref{deltaq,deltap}, it follows that:
\begin{align}
Z^{\delta\tilde{z}_{t+1}} &= -\mathring \chi_t \xi_t^\top \tilde{\xi}\phi'(Z^{\tilde{g}_t})\phi'(Z^{g_t})Z^{W^\top dh_t} \label{eqn:delta_z}\\
\EV\frac{\partial Z^{\delta\tilde{z}_{t+1}}}{\partial Z^{W^\top dh_t}} &= -\mathring \chi_t \xi_t^\top \tilde{\xi}\EV[\phi'(Z^{\tilde{g}_t})\phi'(Z^{g_t})]\label{eqn:delta_z_dot_exp}.
\end{align}
Plugging into \cref{eqn:fdelta=EZZ_2,{eqn:dot}}, followed by some straightforward calculation, then yields \cref{claim:NTK}.

\newcommand{\mathbf{x}}{\mathbf{x}}
\newcommand{\mathbf{y}}{\mathbf{y}}
\newcommand{\mathbf{z}}{\mathbf{z}}
\paragraph{Intuition behind \cref{claim:Zdot}}
\cref{eqn:dot} may appear cryptic at first, so let's give some intuition using an example.
Suppose $\Phi$ in \cref{claim:Zdot} is actually identity.
For brevity, we set $\mathbf{x} = dh_t, \mathbf{y} = \delta \tilde z_{t+1}  \in \R^n$.
Then, following straightforward calculation, $W \mathbf{y} = W W^\trsp \mathbf{x}$ has coordinates
\begin{align}
    (W\mathbf{y})_\alpha
    =
        \sum_{\gamma \ne \alpha} \mathbf{x}_\gamma \sum_{\beta=1}^n W_{\alpha\beta} W_{\gamma\beta}
        + \sum_{\beta=1}^n (W_{\alpha\beta})^2 \mathbf{x}_\alpha
        \label{eqn:WWtrspExample}
\end{align}
Now, the second sum converges via LLN to $\mathbf{x}_\alpha$ as $n\to\infty$.
On the other hand, the first sum will converge via CLT to $\Gaus(0, \lim \|\mathbf{x}\|^2/n)$.
Thus, in terms of $Z$s, we have
\begin{align}
    Z^{W\mathbf{y}} = G + Z^\mathbf{x} = G + Z^\mathbf{x} \EV \Phi'
\end{align}
for some Gaussian $G$; this corresponds directly to \cref{eqn:dot}.%
\footnote{
    This example was worked out in \citep{yang2,yang3} as well, though in different contexts.
    Readers needing more explanation may see those works.
}
For general $\Phi$, a similar intuition applies after Taylor expansion of $\Phi$.

\paragraph{Summary}
This 2-hidden-layer example proceeded much the same as the 1-hidden-layer case, with the main exception of analyzing the interaction of the $n\times n$ Gaussian matrix $W$ and $W^\trsp$ (\cref{eqn:1LPexpectation_2}) that occurs after taking at least 1 step of SGD.
This was absent in the 1-hidden-layer case because each weight matrix has at most one side tending to infinity.
Such analysis is crucial to obtaining the right results, as assuming $W^\trsp$ be independent from $W$ would imply $f$ does not move from initialization.%
\footnote{One can see this easily by modifying our calculations above.}

It turns out these two examples have essentially covered all of the core ideas needed to extend the analysis into arbitrary architectures.
To formalize and scale up our calculations, we now turn to the \emph{Tensor Programs} framework.

\begin{figure}[t]
\centering
\includegraphics[width=0.45\textwidth]{figs/reducedNetsorDiagram_cropped.pdf}
\caption{\textbf{Graphical form of \texorpdfstring{{$\textsc{Netsor}\trsp$}}{NetsorT}{} programs for MLP and RNN.}
An empty node corresponds to a G-var (an initial vector or a vector created by \textsc{\ref{instr:matmul}}{}), while a filled node corresponds to an X-var (a vector created by \textsc{\ref{instr:nonlin}}{}).
Each dashed edge corresponds to matrix multiplication by the labeled matrix.
Each gate (connected by solid edges) represents a \textsc{\ref{instr:nonlin}}{} application.
The computation follows the direction of the gates (left-to-right here).
Note we have $W^1 \xi$ instead of $\xi$ as an initial vector because we only allow $\R^n$ vectors; likewise for $U \xi^i$.
For the same reason, we don't express the network output in this graph.}
\label{fig:reduced_programs}
\end{figure}

\section{Tensor Programs}\label{sec:TP}

So far, our results have been obtained by unrolling the SGD updates on toy models with specific architectures, and using informal arguments. Obviously, these computations quickly become unmanageable when the architecture becomes more complex.
The sheer amount of architectural innovations that have sprung up in recent years requires us to adopt a much more general formulation of our results.
To that end, we adopt the Tensor Programs (TP) framework developed in \cite{yang,yang2,yang3}.
In a nutshell, it provides a language for describing typical computations done in the context of neural networks, such as forward and backward propagation.
It is simultaneously simple and expressive, covering all standard architectures \citep{yang,yang2}.
Here we review two basic forms of Tensor Programs, \texorpdfstring{{$\textsc{Netsor}\trsp$}}{NetsorT}{} and \texorpdfstring{{$\textsc{Netsor}\top^+$}}{NetsorT+}{}.
\enlargethispage{\baselineskip}
\begin{defn}\label{defn:simpleNetsorT}
    A \texorpdfstring{{$\textsc{Netsor}\trsp$}}{NetsorT}{} program is just a sequence of $\R^n$ vectors inductively generated via one of the following instructions from an initial set $\mathcal{V}$ of random $\R^n$ vectors and a set $\mathcal{W}$ of random $n\times n$ matrices%
    \begin{description}
        \item [\normalfont\textsc{Nonlin}\label{instr:nonlin}] For $x^{1},\ldots,x^{k}\in\R^{n}$ in the program and any $\psi:\R^{k}\to\R$, we can generate $\psi(x^{1},\ldots,x^{k})\in\R^{n}$
        \item [\normalfont\textsc{MatMul}\label{instr:matmul}] Given $W\in\R^{n\times n}$ and $x\in\R^{n}$, we can generate $Wx\in\R^{n}$ or $W^{\trsp}x\in\R^{n}$
    \end{description}
\end{defn}

\paragraph{Graphical Form}
We propose to represent a \texorpdfstring{{$\textsc{Netsor}\trsp$}}{NetsorT}{} program as a computational graph, where each node in the graph represents vectors (initial or generated), each (dashed) edge represents a \textsc{\ref{instr:matmul}}{}, and each gate represents a \textsc{\ref{instr:nonlin}}{}.
For example, \cref{fig:reduced_programs} shows the computation graphs expressing (the forward passes of) an MLP and an RNN.
We can also express the backpropagation as well (see \cref{fig:backprop}).
Graphically, the initial vectors are the empty nodes with only one edge coming out, toward the direction of computation.
The matrices correspond to (the labels of) the dashed edges.
We can also define the \emph{output vectors} to correspond to the nodes that have only one edge coming out, \emph{against} the direction of computation.

\paragraph{Neural Network Representation}
Each \texorpdfstring{{$\textsc{Netsor}\trsp$}}{NetsorT}{} program can be thought of as computing a function $(\R^n)^{\mathcal V} \times (\R^{n\times n})^{\mathcal W} \to \R^{\mathcal Y}$ taking an instantiation of the initial vectors $\mathcal V$ and matrices $\mathcal W$ and computing the values of all output vectors $\mathcal Y$.
We can say a program \emph{represents a network} if it computes the \emph{body} of it (without the input and output layers), as exemplified by \cref{fig:reduced_programs}.
This is formalized below.
\begin{defn}\label{defn:nnrep}%

    Consider a neural network $f: (\R^d)^k \to \R$ with input embedding matrices $U^1, \ldots, U^k \in \R^{n\times d}$ (not necessarily distinct) and readout matrix $V \in \R^n$, so that $f(\xi^1, \ldots, \xi^k) = V^\trsp \Phi(U^1 \xi^1, \ldots, U^k \xi^k; \Theta)$ for some function $\Phi(x^1, \ldots, x^k; \Theta)$ with parameters $\Theta$.
    We say a \texorpdfstring{{$\textsc{Netsor}\trsp$}}{NetsorT}{} program \emph{represents} $f$ if it computes $\Phi$ (under some correspondence of $\mathcal V \cup \mathcal W$ to $\{x^1, \ldots, x^k\}\cup \Theta$).%
    \footnote{
        We only consider $f$ with scalar output for simplicity but generalization to multi-dimensional output is straightforward.
    }

\end{defn}
For example, the programs in \cref{fig:reduced_programs} resp.\ represent a 3-hidden-layer MLP and an RNN running for 3 steps.
Note that the initial vectors correspond to a combination of input embeddings (e.g.\ $W^1 \xi$) and vector parameters (e.g. biases) and the matrices correspond to matrix parameters (e.g.\ weights).

\paragraph{Intuition for a Program in the Large $n$ Limit}
Typically, the vectors (resp.\ matrices) in a program will be sampled iid like $\Gaus(0, 1)$ (resp.\ $\Gaus(0, 1/n)$), corresponding to the ``standard'' initialization of neural networks.%
\footnote{
    In the original definition of \citep{yang,yang2,yang3}, the vectors can have correlations between them, but we can always rewrite these vectors as linear image of another set of uncorrelated vectors.
}
In such cases, when $n\to\infty$, a program behaves as follows, in a gist:
\begin{description}
    \item[IID Coordinates] Any vector $x \in \R^n$ in the program has roughly iid coordinates.
    We write $Z^x$ for the random variable encoding this coordinate distribution.
    This $Z^x$ may be correlated with $Z^y$ for other vector $y$ in the program, such that, for example, $\lim_{n\to\infty} x^\trsp y/n = \EV Z^x Z^y$.
    \item[Nonlin] $Z^{\psi(x^1, \ldots, x^k)} = \psi(Z^{x^1}, \ldots, Z^{x^k})$.
    \item[MatMul, without $(W, W^\trsp)$-Interaction] Consider a matrix $W \in \mathbb{R}^{n \times n}$
     in the program and any set of $\mathbb{R}^n$ vectors $\mathcal{\mathbf{X}}$ not dependent on vectors of the form $W^\trsp \bullet$.
    Then the set of random variables $\{Z^{Wx}: x \in \mathcal{\mathbf{X}}\}$ are jointly Gaussian with mean zero and covariance $\Cov(Z^{Wx}, Z^{W\tilde{x}}) = \EV Z^x Z^{\tilde{x}}$ for any $x,\tilde{x} \in \mathcal{\mathbf{X}}$.
    If $\bar W \ne W$ is another matrix in the program and $\mathcal{\mathbf{Y}}$ is a set of such vectors w.r.t.\ $\bar W$, then the set $\{Z^{Wx}: x \in \mathcal{\mathbf{X}}\}$ is independent from $\{Z^{\tilde{W}y}: y \in \mathcal{\mathbf{Y}}\}$.
    \item[MatMul, with  $(W, W^\trsp)$-Interaction]
    For general $x$, $Z^{Wx}$ decomposes into a sum of a Gaussian part, identical to $Z^{Wx}$ in the above case, and a correction term.
    This decomposition is a generalization of \cref{eqn:dot}.
\end{description}

See \cref{thm:PLNetsorT+MasterTheorem} for formal details.

\paragraph{\texorpdfstring{{$\textsc{Netsor}\top^+$}}{NetsorT+}{} Programs}
\citep{yang,yang2} showed that \texorpdfstring{{$\textsc{Netsor}\trsp$}}{NetsorT}{} suffices to express the forward and backward passes of most architectures such as ResNet (with Batchnorm), but Transformer and other standard architectures require adding to \texorpdfstring{{$\textsc{Netsor}\trsp$}}{NetsorT}{} a new ``averaging'' instruction%
\footnote{For readers familiar with Tensor Programs, this is equivalent in expressivity to \textsc{Moment}, which is a composition of a \textsc{\ref{instr:nonlin}}{} and this averaging instruction.}
that returns the ``empirical average'' $\f 1 n \sum_{\alpha=1}^n x_\alpha$ of a vector $x \in \R^n$.
In the $n\to\infty$ limit, this scalar converges to $\EV Z^x$ as would be expected from the intuitions above.
This extension of \texorpdfstring{{$\textsc{Netsor}\trsp$}}{NetsorT}{} (called \texorpdfstring{{$\textsc{Netsor}\top^+$}}{NetsorT+}{}) also allows us to express the network output and loss derivative (e.g.\ in contrast to \cref{fig:reduced_programs}), which will be a technical requirement for unrolling the entirety of SGD training inside a single program, a key step in the proof of our main result.
See discussion of proof formalization in \cref{sec:ProvingNTKtrain}.
We can say a \texorpdfstring{{$\textsc{Netsor}\top^+$}}{NetsorT+}{} program \emph{represents a network $f$} if it computes the body of $f$.

\section{Universality of Kernel Dynamics}\label{sec:ProvingNTKtrain}

\citep{yang,yang2} showed that any neural network of standard architecture is represented by a \texorpdfstring{{$\textsc{Netsor}\top^+$}}{NetsorT+}{} program.
Moreover,
\begin{thm}[\citet{yang2}]
    For a neural network as in \cref{setup:main} below, its Neural Tangent Kernel at initialization has a well-defined infinite-width limit $\mathring{\mathcal K}$.
\end{thm}

\begin{setup}[Representable NN in NTK Parametrization]\label{setup:main}
    Suppose a neural network $f$ is represented by a \texorpdfstring{{$\textsc{Netsor}\top^+$}}{NetsorT+}{} program (in the sense of \cref{defn:nnrep}) whose \textsc{\ref{instr:nonlin}}{} all have polynomially bounded derivatives.%
    \footnote{More generally, we can allow any pseudo-Lipschitz function here, but for simplicity we go with the statement in the main text.}
    Adopt the NTK parametrization: for every matrix parameter $W \in \R^{n\times n}$ of $f$, we factor $W = \f 1 {\sqrt n} w$ where $w$ is the trainable parameter;
    likewise, for each input layer matrix $U^i \in \R^{n\times d}$, we factor $U^i = \f 1 {\sqrt d} u^i$,
    and likewise the output matrix $V = \f 1 {\sqrt n} v$, such that $u^i, v$ are trainable.
    Finally, we randomly initialize all trainable parameters iid as $\Gaus(0, 1)$.
\end{setup}

Our main result is to show that the SGD training of such a neural network described in \cref{setup:main} reduces to kernel gradient descent with kernel $\mathring{\mathcal K}$ in the infinite-width limit.

\newcommand{\mathcal{L}}{\mathcal{L}}
\begin{thm}[\ref{NTKtrain} is Architecturally Universal]\label{thm:main}
    Consider training a network $f$ described in \cref{setup:main} via SGD with batch-size 1 and (WLOG) learning rate 1.
    Let $\xi_t$ be the input and $\mathcal{L}_t: \R \to \R$ be the loss function (absorbing the label) at time $t$.
    Suppose $\mathcal{L}_t$ is continuous for all $t$.
    Then, for any $\xi$ and $t$, $f_t(\xi)$ converges almost surely to a random variable $\mathring f_t(\xi)$ as width $\to \infty$, such that
    \begin{align}\label{eq:ntkdynamics}
        \mathring f_{t+1}(\xi) - \mathring f_t(\xi) = - \mathring{\mathcal K}(\xi, \xi_t) \mathcal{L}_t'(\mathring f_t(\xi_t))
    \end{align}
    where $\mathring{\mathcal{K}}$ is the infinite-width NTK (at initialization) of the neural network.
    \end{thm}

The full proof of \cref{thm:main} is given \cref{sec:appendix_main_proof}.

\paragraph{Extension}
We briefly mention several ways our result can be easily extended.
\emph{0) Different batch sizes, learning rate schedules, and nonscalar outputs}.
\emph{1) Variants of NTK parametrization.}
We can deal with any parametrization that scales the same way as NTK parametrization, e.g.\ weights are sampled like $N(0, \sigma^2)$ for any $\sigma$, with the multipliers $\gamma/fanin$ for any $\gamma$.
\emph{2) Variable width}.
In real networks, the width of different layers can often be different (e.g. in ResNet).
Our result can be extended to the case where the widths tend to infinity at a fixed ratio, using the variable-width version of Tensor Programs \citep{yang3}.
\emph{3) Unsupervised and other learning settings}
can be covered because their training and testing computation can be written into Tensor Programs.
\emph{4) Weight decay, momentum, and other optimizer tricks}
can be covered as well as they can be straightforwardly written into Tensor Programs, but in general the kernel will change from step to step in contrast to \cref{thm:main}.

\subsection{Proof Sketch of Special Case}
\label{sec:proofsketch}
To convey the main idea, we give a proof sketch of a simplified problem: we assume
\begin{enumerate*}[label=\arabic*)]
    \item the input, output layers and biases are not trained (the network has only $\R^{n\times n}$ matrices as trainable parameters);
    \item the forward pass does not contain both a weight matrix $W$ and its transpose $W^\trsp$ (but a single matrix $W$ can still be used multiple times without being transposed);%
    \item input space is $\R^d$ (with $k=1$), and $f = V^\top x \in \R$;
    \item the output vector $x$ is a G-var;
    \item the network is represented by a \texorpdfstring{{$\textsc{Netsor}\trsp$}}{NetsorT}{} (instead of \texorpdfstring{{$\textsc{Netsor}\top^+$}}{NetsorT+}{}) program;
    \footnote{This is not common in deep learning, but appears in some weight-tied autoencoders \citep{tied-encoder}.}
\end{enumerate*}
In the appendix, we prove the general case with these simplifications lifted.

It turns out, every \texorpdfstring{{$\textsc{Netsor}\trsp$}}{NetsorT}{} can be simplified into a \emph{standard form} of sorts, which greatly facilitates our proof.
\begin{defn}
    In a \texorpdfstring{{$\textsc{Netsor}\trsp$}}{NetsorT}{} program, a \emph{G-var}%
    \footnote{``G'' because G-vars often are roughly Gaussian vectors}
    is an initial vector or a vector created by \textsc{\ref{instr:matmul}}{}, while an \emph{X-var} is a vector created by \textsc{\ref{instr:nonlin}}{}.%
    \footnote{\emph{Var} is short for \emph{variable}, as the vectors are considered \emph{variables} in the program.
        In previous works, \emph{H-var} refers to any vector in the program; we will not use this terminology.}
    We define a \emph{reduced \texorpdfstring{{$\textsc{Netsor}\trsp$}}{NetsorT}{} program} as a program in which only G-vars are allowed as inputs to a \textsc{\ref{instr:nonlin}}{}, while only an X-var is allowed as input to a \textsc{\ref{instr:matmul}}{}.
\end{defn}
Observe that any \texorpdfstring{{$\textsc{Netsor}\trsp$}}{NetsorT}{} program may be trivially expressed as a reduced \texorpdfstring{{$\textsc{Netsor}\trsp$}}{NetsorT}{} program by: 1) collapsing chains of non-linearities which appear consecutively, and
2) insert a \textsc{\ref{instr:nonlin}}{}  operation with $\psi(x) = x$ in between consecutive G-vars.
Hence, we may safely assume that $f$ is representable by a reduced \texorpdfstring{{$\textsc{Netsor}\trsp$}}{NetsorT}{} program.

\paragraph{Key Idea: Paths}
The examples of \cref{sec:1LP,sec:2LP} exposed several insights, such as the iid-coordinates intuition, important for proving \cref{thm:main}.
Now we discuss the one remaining key idea for scaling up to general architectures:

\begin{figure}[t]
    \centering
    \includegraphics[width=0.45\textwidth]{figs/path_cropped.pdf}
    \caption{\textbf{Paths.}
    A graphical illustration of paths in an MLP and RNN. A path $p$ always starts with an X-var and ends with a G-var.
    In these examples, path length $|p| = 4$.}
    \label{fig:paths}
\end{figure}

\begin{figure}[t]
    \centering
    \includegraphics[width=0.45\textwidth]{figs/path_iso_cropped.pdf}
    \caption{\textbf{Paths Isomorphism.}
    A graphical illustration of path isomorphism for paths $p,q$ with $|p|=|q|=2$ in an MLP and RNN. In the MLP example, $p$ is not isomorphic to $q$ because the weights $W^1,W^2$ defining the vectors $p^1,q^1$ are not identical.
    For the RNN, $p$ is isomorphic to path $q$ because $p^1$ and $q^1$ are defined with the same weight $W$.}
    \label{fig:paths_iso}
\end{figure}

\begin{restatable}[Paths]{defn}{Paths}\label{defn:paths}
In a \texorpdfstring{{$\textsc{Netsor}\trsp$}}{NetsorT}{} program, a path $p$ starts with an X-var and ends with a G-var, alternating between X- and G-vars along the path.
We write $p^{0}$ for the starting X-var, $p^{1}$ for the following G-var, and so on, as well as $p^{-1}$ for the ending G-var (see \cref{fig:paths} for a graphical illustration).
For odd $i$, let $W^{p^{i}}$ denote the defining matrix of G-var $p^{i}$. For two equal length paths $p,q$, we write $p\cong q$ (path $p$ is isomorphic to path $q$) if for all odd $i$, $W^{p^{i}}$ is the same matrix as $W^{q^{i}}$.%
\footnote{Here we are talking about equality of symbols rather than equality of values of those symbols.}
In other words, we say path $p$ is isomorphic to path $q$ if their sequences of \textsc{\ref{instr:matmul}}{} matrices are identical, (but the \textsc{\ref{instr:nonlin}}{} don't have to be, see \cref{fig:paths_iso} for a graphical illustration). Let $|p|$ denote the number of vectors in $p$ (this is always an even number).
\end{restatable}

The collection of paths $p$ starting with an X-var $p^0 = x$ and ending with a G-var $h$ describes all possible pathways of backpropagating an error signal $dh$ at $h$ to an error signal $dx$ at $x$.
Simultaneously, it also describes all possible pathways of forward propagating a change in $x$ to a change in $h$.

\paragraph{Decomposing the Change in $f$ to a Sum over Paths}
Because the gradient $\nabla_W f$ of a weight $W \in \R^{n\times n}$ is the sum of outer products $\sum_{h,x: h=Wx} dh\otimes x$, summing over all G-vars $h$ and X-vars $x$ in the program with $h= Wx$ (where $dh$ denotes $\nabla_h f$), we also have
\[\nabla_W f = \sum_{h,x: h=Wx} \sum_p J^p\otimes x.\]
where
\[(J^p)^\trsp = \frac{\partial f}{\partial p^{-1}}\times\frac{\partial p^{-1}}{\partial p^{-2}}\times\frac{\partial p^{-2}}{\partial p^{-3}}\times...\times \frac{\partial p^{2}}{\partial h}\]
i.e, $J^p$ denotes the error signal at $h$ from  backpropagation through path $p$, and $p$ ranges over all paths starting with $p^0 =x, p^1=h$ and ending with the output node of the underlying program.
Recall $W$ factors as $\f 1 {\sqrt n} w$ where $w$ is the trainable parameter, not $W$.
By the discussion above, updating $w$ with $\nabla_w f = \f 1 {\sqrt n} \nabla_W f$  causes $f$ to change by
\begin{equation}
    \begin{gathered}
            \left\langle \f 1 {\sqrt n} \nabla_W f, \f 1 {\sqrt n} \nabla_W f \right\rangle
            \\
        =
            \f 1 n \sum_{h,x: h=Wx} \sum_{\bar h,\bar x: \bar h=W\bar x} \sum_p \sum_{\bar p} \langle J^p, J^{\bar p} \rangle \langle x, \bar x \rangle.
            \label{eqn:JJ}
    \end{gathered}
\end{equation}
When every parameter $w$ is randomly initialized iid as $\Gaus(0, 1)$, it turns out that $\langle J^p, J_{\bar p} \rangle$ will go to 0 as $n \to \infty$ unless $p \cong \bar p$ (\cref{defn:paths}).
If one think of $J^p$ as a product of random Gaussian matrices (interleaved with other matrices), then this is akin to the fact that, for a mixed moment $M \mathrel{\raisebox{-0.3ex}{$\odefeq$}} \EV \prod_{i = 1}^r Z_{\gamma(i)}, \gamma: [r] \to [k]$ of standard iid Gaussians $Z_1, \ldots, Z_k$, $M$ is nonzero iff every $Z_i$ appears an even number of times in the product.
This means we can replace the 4 nested sums in \cref{eqn:JJ} with the single sum $\sum_{p \cong \bar p}$ and rewrite $x = p^0, \bar x = \bar p ^0$.

We have suppressed dependence on input in \cref{eqn:JJ}.
Being more explicit about it and performing updates on all weights, we have
\begin{equation}
    \begin{gathered}
        f_{t+1}(\xi) - f_t(\xi) \\
        \approx -\mathcal{L}_t'( f_t(\xi_t))\sum_{p \cong \bar p} \langle J^{p}(\xi), J^{\bar p}(\xi_t) \rangle \langle p^0(\xi), \bar p^0(\xi_t) \rangle.
        \label{eqn:deltaf}
    \end{gathered}
\end{equation}
after taking a gradient step on input $\xi_t$ at initialization $t=0$.
(Here $p^0(\xi)$ denotes the vector $p^0$ as a function of $\xi$ at initialization).
However, \cref{eqn:JJ} holds for general $t$ as well:
The key insight is similar to \cref{eqn:g0} in the 1-hidden-layer example, that vectors $p^0(\xi)$, $J^{p}(\xi)$, etc change vanishingly from their initial values as $n \to \infty$, after any number of SGD steps.
Because our arguments above only depend on inner products between vectors, this means that the error in  \cref{eqn:deltaf} for $t > 0$ vanishes as $n \to \infty$.
Finally, at least heuristically, it is straightforward to show the RHS of \cref{eqn:deltaf} is the NTK via a series of calculations exemplified by those in \cref{sec:1LP,sec:2LP}, to get \cref{eq:ntkdynamics}.

\paragraph{Putting It All Together and Proof Formalization}
While the core ideas discussed above are intuitive, making them rigorous at face value would be quite challenging.
Instead we use the machinery offered by the Tensor Programs framework.
The mechanics of the proof then goes as follows:
1) First we unroll SGD of $f$ into a \texorpdfstring{{$\textsc{Netsor}\top^+$}}{NetsorT+}{} program.%
\footnote{\label{footnote:relyonTP3}
    We note that this formalization crucially relies on \texorpdfstring{{$\textsc{Netsor}\top^+$}}{NetsorT+}{} and its Master Theorem from \citep{yang3} because the SGD unrolling cannot be done in \texorpdfstring{{$\textsc{Netsor}\trsp$}}{NetsorT}{}.
    The reason is that we need to express the output and loss derivatives of the network, which are scalars (or at least finite dimensional), and that cannot be done in a \texorpdfstring{{$\textsc{Netsor}\trsp$}}{NetsorT}{} program.
    Furthermore, the Master Theorem from \citep{yang2} only pertains to a specific type of programs that look like the \emph{first} backpropagation after initialization.
    Thus, it cannot deal with the complete unrolling of SGD as we do here, which requires the more advanced Master Theorem from \citep{yang3}.
}
This is similar to the equations in \cref{sec:1LP,sec:2LP}; the key here is to express $\delta x_{t+1} = \sqrt n(x_{t+1} - x_t)$ as a vector in the program, for any (pre-)activation $x$.
2) We apply the \emph{\texorpdfstring{{$\textsc{Netsor}\top^+$}}{NetsorT+}{} Master Theorem} \citep{yang3} to this program.
This yields the coordinate distribution of each vector.
The core insights here are demonstrated by the calculation with the $Z$ random variables in \cref{sec:1LP,sec:2LP}.
3) Finally, we need to show that (the rigorous version of) \cref{eqn:deltaf} indeed recovers the NTK and agrees with \cref{eq:ntkdynamics}.
This is done via an inductive (symbolic) computation, and the path concept in this section plays a key role here.

\section{Related Works}\label{sec:2}

The connection between kernel methods and neural networks has had a long history before its recent resurgence.
The Gaussian Process (NNGP) view of wide neural networks, which characterizes the behaviour of training only the last layer of a wide neural network, has been studied in \cite{gp1,gp2,gp3,gp4,gp5,gp6,gp7}. Since the original NTK paper \cite{NTK}, many works have informally derived the infinite-width NTK for various architectures such as CNNs \cite{arora}, RNN \cite{rnnntk}, attention \cite{attention_ntk}, ensembles \cite{ce} and graph neural networks \cite{graphntk}, but none of them formally proved \ref{NTKinit} or \ref{NTKtrain} for those architectures.
Finite width corrections to the NTK were derived for fully connected networks in \cite{boris,resntk}.
The validity of the NTK theory was empirically studied in \cite{wide} for a variety of architectures.

The Tensor Program framework \cite{yang,yang2,yang3} was introduced in an attempt to unify and generalize the NNGP/NTK theory to a broad range of architectures, eliminating the need to re-develop the theory for each new architecture.
For example, \cite{yang} proved the architectural universality of NNGP correspondence, while \cite{yang2} proved that of \ref{NTKinit}.
On the other hand, \cite{yang3} developed the most general machinery for Tensor Programs and as a corollary constructed a comprehensive theory of nonlinear random matrix theory, that, for example, can calculate the singular value distribution of a wide neural network of any architecture.
Our proofs depend on the machinery of \cite{yang3} crucially, as discussed in \cref{sec:ProvingNTKtrain}.

\enlargethispage{\baselineskip}

\section{Conclusion}

New theories of deep learning almost always start with MLPs, rightly so as they are the simplest case and can often reveal the key insights more clearly.
Of course, as deep learning itself is an applied field, one should always ask whether insights on MLPs extend to more general architectures, i.e.\ whether there is an \emph{architecturally universal extension} of a proposed theory of MLPs.
This is not always easy to answer.

In this paper, we showed that the NTK theory is architecturally universal, but more importantly, we showed that the Tensor Programs technique is a very powerful tool for answering the above question as a matter of routine.
Looking forward, we hope to apply it to generate more novel and general insights.

\newpage
\twocolumn

redpajama_set_name: RedPajamaArXiv


text:
French education reform
andrewiconnell	in France	 May 21, 2015 October 15, 2015 114 Words
Spain's Groundhog Day election
Spain's most unpredictable, messy election in modern times
Theresa May will finally have to give up her red lines to deliver Brexit
Spanish foreign minister interview on Catalan independence
Europe's year of solidarity – and surprises – ahead
What this election means for Brexit
France's unpredictable revolution
5 takeaways from Koblenz far-right populist conference
bbc cambridge catalan catalonia economy election eu migrants europe eurozone france french front national germany greece greek grexit journalism migration photography podemos politics spain spanish spanish election student media ukip university varsity work experience year abroad
Andrew is currently a foreign news editor at Sky News, working with teams of correspondents and producers in London and around the world. He was formerly a producer at CNN International in London.
He was educated at King's College, Cambridge, where he studied French, Spanish, Catalan, Portuguese and Ukrainian. He also studied at Cardiff University and the University of Barcelona.
I've been avidly following the twists and turns of the biggest story in France for a few weeks now – the controversial education reform that the Socialist government is wishing to bring into force despite protests and a lot of noise from the unions and the right of politics. It's a heady mix of education and politics, and it rarely goes smoothly.
Here is my 2-minute report on what has been happening this week with this big debate in France.
andrewiconnell Covering the political and economic news from in and around Europe, analysing how events and rhetoric in the continent are shaping - and threatening - its future. Producer at Sky News. MA Broadcast Journalism graduate, Cardiff University. Languages undergraduate, King's College, Cambridge French, Spanish, Catalan, Portuguese & Ukrainian. Currently learning German & Italian.
Published May 21, 2015 October 15, 2015
#endweek5blues rally in Cambridge
France's olive branch to Greece


It's a well-known proven fact that skinless, boneless chicken breasts are quite tough to grill nicely whereas pork chops do not lag far behind. Then minimize the warmth, remove the lid, add the cheese, exchange the lid and permit the cheese to melt. Add in the reserved pineapple slices and simmer for 10 minutes or till sauce is thickened and pork reaches 145 levels. Dredge each side of the pork chops in the flour combination, and then put aside on a plate. Cook pork chops until bottom side is golden brown, about 1 minute.
Bring to a boil and cook till salt and sugar have dissolved fully. Place the skillet within the oven to preheat as well. Heat oil in a large skillet over medium-excessive. Working with one chop at a time, dredge a pork chop in flour with your left hand, shaking off extra. One more look at these pork chops to convince you that it's worthwhile to try this quickly.
Add the meat broth, butter, salt and pepper. Dip pork chops within the combination (making sure mixture sticks) and sear in a pan of olive oil on medium-high warmth. Warmth oil in a big skillet over mediumhigh. 2Rub the pork chops with olive oil after which dip (coat) each one within the cheese mixture. Prime with the browned pork chops. When the grill is scorching, place the chops straight on the grill grate and prepare dinner 15 minutes turning as soon as halfway by way of.
Carry 1 cup of the water to a boil, add the salt and non-compulsory flavorings, and stir to dissolve the salt. Press the combination over the pork chops to verify they are properly coated in it. Let the pork chops rest for 10 minutes. Pour over pork chops and let marinade for about 20 minutes. Flip chops and fry until other sides are browned and crisp, about 3 minutes longer.
Add enough oil to a large cast iron skillet that the oil will come half-means up the chops. Remove chops to a rack or paper towel to empty. This resting time will give the crust an opportunity to dry on the pork chop. Thin-lower pork chops shall be just cooked via on the similar time that the breading is browned and crisp. Liberally sprinkle the porkchops on each side with the seasoning combination.


text:
Whom to Contact and When 2023-2024 Pre-K Application
Pine Bush Central School District
Albanian Arabic Chinese (Traditional) English French Hindi Macedonian Punjabi Spanish Turkish Urdu
EJ Russell
Pakanasink
Crispell
Parent / Community
Pine Bush Central School District > Parent / Community > Emergency Closings
Emergency Closings
Announcing Emergency/Snow Days
There will be days when, because of hazardous road conditions, school will be delayed or closed. Delays and closings will be posted prominently on the district's website home page and communicated directly to our families through our SchoolMessenger system. Announcements will be made on the following radio stations and websites beginning at 5:45 a.m.:
WALL (1340 AM)
WGNY (1220 AM)
WELV (1269 AM)
WBNR (1260 AM)
WPDH (101.5 FM)
WHUD (100.7 FM)
WSUL (98.3 FM)
When the school district is closed, no transportation will be furnished to BOCES, non-public schools, or after-school activities.
Delays and Early Dismissals
When the Pine Bush Central School District has a two- or three-hour delay, transportation will pick up all of our students on a delayed schedule. This includes students attending OU BOCES, non-public schools and other special education locations. Students will be picked up two hours later than usual on a two-hour delay day and three hours later than usual on a three-hour delay day.
Students will return home on their regular schedule.
When the district dismisses early, transportation will pick up all of our students early, including students attending OU BOCES, non-public schools and other special education locations.
When Pine Bush cancels after-school activities, Boys and Girls Club and Club Kid will also be cancelled. Please make sure you have a plan to accommodate this possibility.
Virtual Instruction
In the event that the district uses all of its allotted emergency closing days, an all-virtual learning day may be scheduled.
Emergency Days
For the 2022-2023 school year, there are four emergency days built into the calendar. Emergency days used so far:
Wednesday, Jan. 25, 2023
The Pine Bush Central School District utilizes numerous contacts and information when making the determination to delay schools, close schools, dismiss schools early, and/or cancel after-school activities and events.
Please know that safety is always our highest concern. The safety of our students and staff comes first, every single day. If we believe we can keep school open safely, that's what we do.
However, the process to determine whether to keep schools open or to close, delay or release early, is exceptionally thorough. District officials are in consultation with town, county and transportation officials well in advance of a potential weather event, right up until the time we make our decision.
In making our decisions, we monitor information from the National Weather Service, Fleet Weather Tracking System, local news channels and the Weather Channel. Each storm behaves differently. We are in close contact with our town highway supervisors about road conditions and their schedules for road crews to prep for the expected conditions as well as plowing, salting and/or sanding during the event.
During inclement weather, our bus company has four members of its staff traveling within the Pine Bush Central School District providing feedback on road conditions.
We are in contact with contiguous school districts as well.
Our Operations and Maintenance Department also weighs in on their progress and ability to have parking areas and walkways clear for staff and students.
Our district is large – encompassing seven towns in three counties. Many areas are at a higher elevation and experience more difficult weather conditions while much of the district may not. We must take into account the entire district when making these decisions. However, parents have the final say and can make the informed choice to keep their children home from school if they are not comfortable with the conditions in their area.
For school closings, based on all information we have gathered, the superintendent or the designee usually makes a determination by 5:30 a.m.
Once a decision is made, messages are sent out to parents using the SchoolMessenger system and a message is posted on our district website. Local radio and television stations are also notified. Through these communication avenues, parents and guardians then are able to plan accordingly for their children and their care.
Once a decision is made, messages are sent out to parents using the SchoolMessenger system. Please make sure your information is up to date so that you receive the proper notifications. Through these communication avenues, parents and guardians then are able to plan accordingly for their children and their care.
If a school emergency should arise that requires an evacuation, the following plan will be put in place:
E. J. Russell Elementary School students will walk to the Church of the Infant Saviour on Rt. 302.
Pakanasink Elementary School students will walk to the Presbyterian Church on the corner of Rt. 302 and Goshen Turnpike.
Circleville Elementary School students will board buses and be transported to the Presbyterian Church on the corner of Rt. 302 and Goshen Turnpike.
Pine Bush Elementary School students will walk to the Pine Bush High School.
After the elementary students are in the alternate sites, buses will pick up the high school and middle school students, transport them home, and return for the elementary students.
Parents must decide in advance what their child will do if school is closed. It is not possible for the school to notify parents in the event of an emergency closing, however, information will be made available on the district Hot Line, which can be accessed by dialing 744-2031, then press 12, then press 3.
Summer School Schedule
Roles of the Board
Watch Recent Meetings
HR / Employment
Engage NY
School-Based Satellite Clinics
Tax Inquiries
State Route 302, Pine Bush, NY 12566
Brian Dunn
This website is maintained by Public Information Specialist Linda Smith. It is the goal of the Pine Bush Central School District that this website is accessible to all users. View our accessibility statement. The district is not responsible for facts or opinions contained on any linked site. Some links and features on this site require the Adobe Acrobat Reader to view. Visit the Adobe website to download the free Acrobat Reader. This website was produced by the Capital Region BOCES Communications Service, Albany, NY. Copyright © 2023. All rights reserved.