summaries: Traditional NTM is done with a large encoder and large autoregressive (AR) decoder. Due to the sequential nature of the AR decoder, inference can be slow due to lack of parallelism (unless done at very large batch sizes). Non-Autoregressive (NAR) models have been proposed to alleviate this problem, but all NAR approaches trade off some translation quality for speed gains. In this paper, the authors claim that an alternative to NAR is to speed up standard AR decoding by reallocating network weights and layers to the (easily parallelizable) encoder, and making the decoder a single layer. They claim that this matches the speed of NAR models while keeping the performance of traditional AR models, making it a better choice in the design space than any NAR models. Comparisons are made to CMLM and DisCo NAR models to justify these claims with experimental evidence.

summaries: The authors advocate for fair comparison between autoregressive (AR) and non-autoregressive models (NAR) in non-autoregressive machine translation (NAT) research. They highlight three main aspects where the comparison has not been fair so far in the literature - suboptimal layer allocation, insufficient speed measurement, and lack of knowledge distillation. They perform extensive comparisons between AR and NAR models in these 3 aspects and report interesting results.

summaries: The paper proposes deep encoder and shallow decoder models for auto-regressive NMT. They compare rigorously to NAR models. They also study three factors: layer allocation, speed measurement and knowledge distillation. They include that with a 12E-D1 model they obtain significant speed-up and can outperform the standard 6-6 AR model and almost always beat the NAR model in terms of quality. They also show that NAR models need deep decoders because they need to handle reordering.

abstractText: Much recent effort has been invested in non-autoregressive neural machine translation, which appears to be an efficient alternative to state-of-the-art autoregressive machine translation on modern GPUs. In contrast to the latter, where generation is sequential, the former allows generation to be parallelized across target token positions. Some of the latest non-autoregressive models have achieved impressive translation quality-speed tradeoffs compared to autoregressive baselines. In this work, we reexamine this tradeoff and argue that autoregressive baselines can be substantially sped up without loss in accuracy. Specifically, we study autoregressive models with encoders and decoders of varied depths. Our extensive experiments show that given a sufficiently deep encoder, a single-layer autoregressive decoder can substantially outperform strong non-autoregressive models with comparable inference speed. We show that the speed disadvantage for autoregressive baselines compared to non-autoregressive methods has been overestimated in three aspects: suboptimal layer allocation, insufficient speed measurement, and lack of knowledge distillation. Our results establish a new protocol for future research toward fast, accurate machine translation. Our code is available at https://github.com/jungokasai/deep-shallow.

authors:
Dzmitry Bahdanau
Kyunghyun Cho
Yoshua Bengio

title: Neural machine translation by jointly learning to align and translate

venue: In Proc. of ICLR,

authors:
Antonio Valerio Miceli Barone
Jindřich Helcl
Rico Sennrich
Barry Haddow
Alexandra Birch

title: Deep architectures for neural machine translation

venue: In Proc. of WMT,

authors:
Ondřej Bojar
Christian Buck
Christian Federmann
Barry Haddow
Philipp Koehn
Johannes Leveling
Christof Monz
Pavel Pecina
Matt Post
Herve Saint-Amand
Radu Soricut
Lucia Specia
Aleš Tamchyna

title: Findings of the 2014 workshop on statistical machine translation

authors:
Ondřej Bojar
Rajen Chatterjee
Christian Federmann
Yvette Graham
Barry Haddow
Shujian Huang
Matthias Huck
Philipp Koehn
Qun Liu
Varvara Logacheva
Christof Monz
Matteo Negri
Matt Post
Raphael Rubino
Lucia Specia
Marco Turchi

title: Findings of the 2017 conference on machine translation (WMT17)

authors:
William Chan
Nikita Kitaev
Kelvin Guu
Mitchell Stern
Jakob Uszkoreit

title: KERMIT: Generative insertion-based modeling for sequences, 2019

venue: URL https://arxiv.org/abs/1906

authors:
William Chan
Mitchell Stern
Jamie Ryan Kiros
Jakob Uszkoreit

title: An empirical study of generation order for machine translation

venue: In Proc. of EMNLP,

authors:
Ciprian Chelba
Mia Chen
Ankur Bapna
Noam Shazeer

title: Faster transformer decoding: N-gram masked self-attention, 2020

venue: URL https://arxiv.org/abs/2001.04589

authors:
Raj Dabre
Atsushi Fujita

title: Recurrent stacking of layers for compact neural machine translation models

venue: In Proc. of AAAI,

authors:
Mostafa Dehghani
Stephan Gouws
Oriol Vinyals
Jakob Uszkoreit
Łukasz

title: Universal transformers

authors:
Chris Dyer
Victor Chahuneau
Noah A. Smith

title: A simple, fast, and effective reparameterization of ibm model 2

venue: In Proc. of NAACL,

authors:
Marjan Ghazvininejad
Omer Levy
Yinhan Liu
Luke S. Zettlemoyer

title: Mask-predict: Parallel decoding of conditional masked language models

authors:
Marjan Ghazvininejad
Vladimir Karpukhin
Luke Zettlemoyer
Omer Levy

title: Aligned cross entropy for non-autoregressive machine translation

venue: In Proc. of ICML, 2020a. URL https: //arxiv.org/abs/2004.01655

authors:
Marjan Ghazvininejad
Omer Levy
Luke Zettlemoyer

title: Semi-autoregressive training improves mask-predict decoding, 2020b

venue: URL https://arxiv.org/abs/2001.08785

authors:
Jiatao Gu
James Bradbury
Caiming Xiong
Victor O.K. Li
Richard Socher

title: Nonautoregressive neural machine translation

authors:
Jiatao Gu
Qi Liu
Kyunghyun Cho

title: Insertion-based decoding with automatically inferred generation order

venue: TACL, 2019a. URL https://arxiv.org/abs/1902.01370

authors: Enhong Chen. Jointly masked sequence-to-sequence model for nonautoregressive neural machine translation. In Proc. of ACL

title: URL https://www

title: Optimizing parallel reduction in CUDA

authors:
Hany Hassan
Anthony Aue
Chang Chen
Vishal Chowdhary
Jonathan Clark
Christian Federmann
Xuedong Huang
Marcin Junczys-Dowmunt
William Lewis
Mengnan Li
Shujie Liu
Tie-Yan Liu
Renqian Luo
Arul Menezes
Tao Qin
Frank Seide
Xu Tan
Fei Tian
Lijun Wu
Shuangzhi Wu
Yingce Xia
Dongdong Zhang
Zhirui Zhang
Ming Zhou

title: Achieving human parity on automatic Chinese to English news translation, 2018

venue: URL https://arxiv.org/abs/

authors:
Geoffrey E. Hinton
Oriol Vinyals
Jeffrey Dean

title: Distilling the knowledge in a neural network

venue: In Proc. of NeurIPS Deep Learning and Representation Learning Workshop,

authors:
Hakan Inan
Khashayar Khosravi
Richard Socher

title: Tying word vectors and word classifiers: A loss framework for language modeling

authors:
Łukasz Kaiser
Aurko Roy
Ashish Vaswani
Niki Parmar
Samy Bengio
Jakob Uszkoreit
Noam Shazeer

title: Fast decoding in sequence models using discrete latent variables

venue: In Proc. of ICML,

authors:
Nal Kalchbrenner
Phil Blunsom

title: Recurrent continuous translation models

authors:
Jungo Kasai
James Cross
Marjan Ghazvininejad
Jiatao Gu

title: Non-autoregressive machine translation with disentangled context transformer

authors:
Angelos Katharopoulos
Apoorv Vyas
Nikolaos Pappas
François Fleuret

title: Transformers are rnns: Fast autoregressive transformers with linear attention

authors:
Yoon Kim
Alexander M. Rush

title: Sequence-level knowledge distillation

authors:
Young Jin Kim
Marcin Junczys-Dowmunt
Hany Hassan
Alham Fikri Aji
Kenneth Heafield
Roman Grundkiewicz
Nikolay

title: Bogoychev. From research to production and back: Ludicrously fast neural machine translation

venue: In Proc. of WNGT,

authors:
Nikita Kitaev
Lukasz Kaiser
Anselm Levskaya

title: Reformer: The efficient transformer

authors:
Jason D. Lee
Elman Mansimov
Kyunghyun Cho

title: Deterministic non-autoregressive neural sequence modeling by iterative refinement

authors:
Mike Lewis
Yinhan Liu
Naman Goyal
Marjan Ghazvininejad
Abdelrahman Mohamed
Omer Levy
Ves Stoyanov
Luke Zettlemoyer

title: BART: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension

venue: In Proc. of ACL,

authors:
Xiaoya Li
Yuxian Meng
Arianna Yuan
Fei Wu
Jiwei Li

title: LAVA NAT: A non-autoregressive translation model with look-around decoding and vocabulary attention, 2020

venue: URL https: //arxiv.org/abs/2002.03084

authors:
Zhuohan Li
Zi Lin
Di He
Fei Tian
Tao Qin
Liwei Wang
Tie-Yan Liu

title: Hint-based training for non-autoregressive machine translation

authors:
Jindřich Libovický
Jindřich Helcl

title: End-to-end non-autoregressive neural machine translation with connectionist temporal classification

authors:
Yinhan Liu
Jiatao Gu
Naman Goyal
Xian Li
Sergey Edunov
Marjan Ghazvininejad
Mike Lewis
Luke Zettlemoyer

title: Multilingual denoising pre-training for neural machine translation

venue: TACL,

authors:
Xuezhe Ma
Chunting Zhou
Xian Li
Graham Neubig
Eduard H. Hovy

title: FlowSeq: Nonautoregressive conditional sequence generation with generative flow

authors:
Elman Mansimov
Alex Wang
Kyunghyun Cho

title: A generalized framework of sequence generation with application to undirected sequence models, 2019

venue: URL https://arxiv.org/ abs/1905.12790

authors:
Paulius Micikevicius
Sharan Narang
Jonah Alben
Gregory Diamos
Erich Elsen
David Garcia
Boris Ginsburg
Michael Houston
Oleksii Kuchaiev
Ganesh Venkatesh
Hao Wu

title: Mixed precision training

authors:
Myle Ott
Sergey Edunov
David Grangier
Michael Auli

title: Scaling neural machine translation

authors:
Myle Ott
Sergey Edunov
Alexei Baevski
Angela Fan
Sam Gross
Nathan Ng
David Grangier
Michael Auli

title: fairseq: A fast, extensible toolkit for sequence modeling

venue: In NAACL Demonstrations,

authors:
Kishore Papineni
Salim Roukos
Todd Ward
Wei-Jing Zhu

title: BLEU: a method for automatic evaluation of machine translation

authors:
Hao Peng
Nikolaos Pappas
Dani Yogatama
Roy Schwartz
Noah A. Smith
Lingpeng Kong

title: Random feature attention

title: A call for clarity in reporting BLEU scores

authors:
Ofir Press
Lior Wolf

title: Using the output embedding to improve language models

venue: In Proc. of EACL,

authors:
Qiu Ran
Yankai Lin
Peng Li
Jie Zhou

title: Guiding non-autoregressive neural machine translation decoding with reordering information

authors:
Chitwan Saharia
William Chan
Saurabh Saxena
Mohammad Norouzi

title: Non-autoregressive machine translation with latent alignments

authors:
Jean Senellart
Dakun Zhang
Bo Wang
Guillaume Klein
Jean-Pierre Ramatchandirin
Josep Crego
Alexander Rush

title: OpenNMT system description for WNMT 2018: 800 words/sec on a single-core CPU

venue: In Proc. of WNG,

authors:
Rico Sennrich
Barry Haddow
Alexandra Birch

title: Neural machine translation of rare words with subword units

authors:
Chenze Shao
Jinchao Zhang
Yang Feng
Fandong Meng
Jie Zhou

title: Minimizing the bag-ofngrams difference for non-autoregressive neural machine translation

authors:
Xing Shi
Kevin Knight

title: Speeding up neural machine translation decoding by shrinking run-time vocabulary

authors:
Raphael Shu
Jason Lee
Hideki Nakayama
Kyunghyun Cho

title: Latent-variable nonautoregressive neural machine translation with deterministic inference using a delta posterior

authors:
Mitchell Stern
Noam Shazeer
Jakob Uszkoreit

title: Blockwise parallel decoding for deep autoregressive models

venue: In Proc. of NeurIPS,

authors:
Mitchell Stern
William Chan
Jamie Ryan Kiros
Jakob Uszkoreit

title: Insertion transformer: flexible sequence generation via insertion operations

authors:
Zhiqing Sun
Zhuohan Li
Haoqing Wang
Di He
Zi Lin
Zhihong Deng

title: Fast structured decoding for sequence models

authors:
Ilya Sutskever
Oriol Vinyals
Quoc V. Le

title: Sequence to sequence learning with neural networks

authors:
Lifu Tu
Richard Yuanzhe Pang
Sam Wiseman
Kevin Gimpel

title: ENGINE: Energy-based inference networks for non-autoregressive machine translation

authors:
Ashish Vaswani
Noam Shazeer
Niki Parmar
Jakob Uszkoreit
Llion Jones
Aidan N. Gomez
Łukasz Kaiser
Illia Polosukhin

title: Attention is all you need

authors:
Qiang Wang
Bei Li
Tong Xiao
Jingbo Zhu
Changliang Li
Derek F. Wong
Lidia S. Chao

title: Learning deep transformer models for machine translation

authors:
Yiren Wang
Fei Tian
Di He
Tao Qin
ChengXiang Zhai
Tie-Yan Liu

title: Non-autoregressive machine translation with auxiliary regularization

authors:
Felix Wu
Angela Fan
Alexei Baevski
Yann Dauphin
Michael Auli

title: Pay less attention with lightweight and dynamic convolutions

authors:
Biao Zhang
Deyi Xiong
Jinsong Su

title: Accelerating neural transformer via an average attention network

authors:
Chunting Zhou
Graham Neubig
Jiatao Gu

title: Understanding knowledge distillation in nonautoregressive machine translation

authors:
Jiawei Zhou
Phillip Keung

title: Improving non-autoregressive neural machine translation with monolingual data

heading: 1 INTRODUCTION

text:
Fast, accurate machine translation is a fundamental goal with a wide range of applications both in research and production. State-of-the-art neural machine translation systems generate translations autoregressively where words are predicted one-by-one conditioned on all previous words (Kalchbrenner & Blunsom, 2013; Sutskever et al., 2014; Bahdanau et al., 2015; Wu et al., 2016; Vaswani et al., 2017). This sequential property limits parallelization, since multiple tokens in each sentence cannot be generated in parallel. A flurry of recent work developed ways to (partially) parallelize the decoder with non-autoregressive machine translation (NAR; Gu et al., 2018), thereby speeding up decoding during inference. NAR tends to suffer in translation quality because parallel decoding assumes conditional independence between the output tokens and prevents the model from properly capturing the highly multimodal distribution of target translations (Gu et al., 2018).
Recent work proposed methods to mitigate this multimodality issue, including iterative refinement (e.g., Lee et al., 2018; Ghazvininejad et al., 2019), and modeling with latent variables (e.g., Ma et al., 2019; Shu et al., 2020). These approaches modify the decoder transformer to find a balance between decoding parallelism and translation quality. In this work, however, we adopt a different speed-quality tradeoff. Recent work by Kim et al. (2019) in autoregressive machine translation (AR) suggests that better speed-quality tradeoffs can be achieved by having different depths in the encoder and the decoder. Here, we make a formal argument in favor of deep encoder, shallow decoder configurations and empirically demonstrate better speed-quality tradeoffs for the AR baselines.
∗ Work partially done at Facebook AI.
We provide extensive speed-quality comparisons between iterative NAR models and AR models with varying numbers of encoder and decoder layers. In particular, we use two types of speed measures for translation and discuss their relation to computational complexity. The two measures reflect two different application scenarios: feeding one sentence at a time, and feeding as many words as possible into the GPU memory. The first scenario is designed to simulate, for example, instantaneous machine translation that translates text (or even speech) input from users. This is where current NAR models shine—we can make full use of parallelism across decoding positions in a GPU. For this reason, much prior work in NAR only measures speed using this metric (e.g., Gu et al., 2018; 2019b; Kasai et al., 2020; Li et al., 2020). The second scenario aims at a situation where we want to translate a large amount of text as quickly as possible. In this case, we see that AR models run faster than NAR models by a large margin. Computation at each time step is large enough to exploit parallelism in a GPU, which cancels out the benefit from parallel NAR decoding. Further, AR models can cache all previous hidden states (Ott et al., 2019) and compute each step in linear time complexity with respect to the sequence length. In contrast, NAR models necessitate a fresh run of quadratic self and cross attention in every decoding iteration.
Interestingly, using a deep encoder and a shallow decoder in NAR models fails to retain the original translation accuracy by using 6 layers each (§4.1). This suggests that departure from AR decoding necessitates more capacity in the decoder; the strategy is effective specifically for AR models. In particular, our analysis demonstrates that an NAR decoder requires more layers to learn target word ordering (§5). In summary, our contributions are the following:
• We challenge three conventional assumptions in NAR evaluation: suboptimal layer allocation, lack of distillation for AR baselines, and insufficiently general speed measures. • We provide a complexity analysis and identify an optimal layer allocation strategy that leads to better speed-quality tradeoffs, namely a deep-shallow configuration. • We perform extensive analyses and head-to-head comparisons of AR and strong NAR models on seven standard translation directions. We demonstrate that the accuracy gap between the two model families is much wider than previously thought and that NAR models are unable to capture target word order well without sufficiently deep decoders.

heading: 2 REEVALUATING NON-AUTOREGRESSIVE MACHINE TRANSLATION

text: We critically examine in this section the evaluation practices and assumptions that are widely held in the non-autoregressive neural machine translation (NAR) literature (e.g., Gu et al., 2018; Ghazvininejad et al., 2019; Kasai et al., 2020). In particular, we focus on three aspects: speed measurement (§2.1), layer allocation (§2.2), and knowledge distillation (§2.3).

heading: 2.1 SPEED MEASURES

text:
One major benefit of NAR models over AR ones is their ability to generate text in parallel. Current research on measuring speed has focused solely on the setting of translating one sentence at a time where full parallelization is trivial with a single GPU. However, we argue that this speed measure is not realistic in some scenarios because the GPU memory is finite and the GPU unit in such a setting is underused. To address this issue, we use two translation speed metrics to measure inference speed:
• S1 measures speed when translating one sentence at a time. This metric is used in standard practice and aligns with applications like instantaneous machine translation that translates text input from users immediately. • Smax measures speed when translating in mini-batches as large as the hardware allows. This corresponds to scenarios where one wants to translate a large amount of text given in advance. For instance, such large-batch machine translation is implemented in the Google cloud service.1
For all models, both metrics measure wall-clock time from when the weights are loaded until the last sentence is translated. We report speedups relative to an AR baseline with a 6-layer encoder and a 6-layer decoder following prior work (Gu et al., 2018; Li et al., 2020; Kasai et al., 2020).
1https://cloud.google.com/translate/docs/advanced/batch-translation.

heading: 2.2 LAYER ALLOCATION

text: Current evaluation practice in the NAR literature uses an equal number of layers for the encoder and decoder both in AR baselines and NAR models. However, previous studies in AR machine translation suggest that this allocation strategy leads to a suboptimal speed-quality tradeoff (Barone et al., 2017; Kim et al., 2019). These findings have several implications for evaluating NAR methods. We first discuss the strategy of deep encoder, shallow decoder (§2.2.1), and provide a theoretical analysis of the speed-quality tradeoff in the context of NAR evaluation (§2.2.2). Our analyses are verified empirically in the next section (§3).

heading: 2.2.1 DEEP ENCODER, SHALLOW DECODER

text:
In line with prior work on deep encoders or shallow decoders (Barone et al., 2017; Wang et al., 2019a; Kim et al., 2019), we depart from the convention to allocate an equal number of layers on both sides and explore pairing a deep encoder with a shallow decoder for both AR and NAR methods. Here, we study the impact of such architectures and systematically compare AR and NAR methods.2 As we will show in §3, an AR model with a deep-shallow configuration retains translation accuracy, but can substantially reduce decoding time. This is because at inference time, the encoder accounts for a smaller part of the overhead since its computation can be easily parallelized over source positions; on the other hand, the speedup gains from a lightweight decoder are substantial.
By Layer Full Model
Enc. AR Dec. NAR Dec. AR E-D AR E-1 NAR E-D Total Operations O(N2) O(N2) O(TN2) O(EN2 +DN2) O(EN2 + 1 ⋅N2) O(EN2 +DTN2) Time Complex. O(N) O(N2) O(TN) O(EN +DN2) O(EN +N2) O(EN +DTN)
Table 1: Analysis of transformers. Time complex. indicates time complexity when full parallelization is assumed. N : source/target length; E: encoder depth; D: decoder depth; T : # NAR iterations.

heading: 2.2.2 COMPLEXITY ANALYSIS

text:
This section analyzes the complexities of transformer-based encoders, autoregressive and nonautoregressive decoders. We focus on two key properties: (1) the total amount of operations and (2) time complexity when full parallelization is assumed (Harris, 2007).
Notation For simplicity let us assume the source and target text have the same length N . T is the number of iterations in an iterative NAR method (typically T < N ). Let E and D denote the numbers of encoder and decoder layers.
Table 1 breaks down the comparison. AR and NAR models use the same encoder architecture. There are several interesting distinctions between AR and NAR decoders. First, although their total amounts of operations are both quadratic in sequence length, an NAR decoder with T decoding iterations needs T times more computation. Second, an AR decoder has time complexity quadratic in sequence length. This contrasts with the linear time complexity of an NAR decoder, which is the powerhouse of its S1 speedup (§4.1). This is because the attention computation can be readily parallelized across target positions in NAR decoders.
By such comparisons we make the following key observations:
(a) For both AR and NAR models, the time complexity is dominated by decoders. When T < N , an NAR model has an advantage over its AR counterpart with the same layers. (b) Innocuous as it may seem, the constant T contributes major computational cost in terms of the total operations of NAR models. Empirically, T needs to be at least 4 to perform competitively to AR models (Ghazvininejad et al., 2019; Kasai et al., 2020).
(a) suggests that one can significantly speed up S1 decoding by using shallower decoders, while increasing the encoder depth only results in a mild slowdown. As we will show later in the experiments, AR decoders are much more robust to using fewer layers than NAR decoders. For example,
2Note that Kim et al. (2019) proposed other methods to optimize CPU decoding of AR models, but we do not apply them, to ensure fair comparisons between AR and NAR models.
AR E-1 can decode much faster than AR E-D and comparably to NAR E-D, while retaining the accuracy of AR E-D. From (b), one may expect a different trend in Smax from S1: in large minibatch decoding, an AR model can make use of the GPU’s compute units, since now parallelization happens over the instances in a mini-batch. In other words, under the Smax evaluation where the GPU is running close to its maximum flop/s, NAR can actually be slower since it needs more operations due to its iterative decoding. This is confirmed by our experiments (§4.1).

heading: 2.3 KNOWLEDGE DISTILLATION

text: Most NAR models rely on sequence-level knowledge distillation (Hinton et al., 2015; Kim & Rush, 2016) to achieve a reasonable speed-quality tradeoff, where NAR models are trained on output translations from a (larger) AR model. Nevertheless, standard practice in this area assumes that knowledge distillation is not required for the AR baseline. Here, we aim for fair evaluation by applying distillation to both model families; we depart from previous practice where NAR models trained with distillation are compared with AR models trained without (Ran et al., 2021; Sun et al., 2019; Shu et al., 2020; Zhou et al., 2020; Saharia et al., 2020) with a few exceptions (Ghazvininejad et al., 2019; Kasai et al., 2020). Our analysis (§5) demonstrates that AR models also benefit from knowledge distillation and that the accuracy gap between AR and NAR models is wider than previously established.

heading: 3 EXPERIMENTS

text: We compare NAR and AR models with different layer allocation strategies on standard machine translation datasets of varying languages and sizes. Our results show that deep-shallow AR models provide a better speed-quality tradeoff than NAR models.

heading: 3.1 BASELINES AND COMPARISON

text:
Prior work has proposed various approaches to non-autoregressive machine translation (NAR). These methods must seek a balance between speed and quality: the more decoding parallelization is introduced into a model, the more the output quality deteriorates due to a conditional independence assumption. Some of the existing NAR models rescore the candidates with external autoregressive models (Sun et al., 2019; Li et al., 2020), or apply reordering modules (Ran et al., 2021). We mainly compare with two iterative NAR models (Ghazvininejad et al., 2019; Kasai et al., 2020) because of their strong performance without relying on any external system:
• CMLM (Ghazvininejad et al., 2019) predicts randomly masked target tokens given observed ones as well as the source. At inference time, it first predicts all target words nonautoregressively, and then iteratively masks and predicts the words that the model is least confident about. Following previous practice (Ghazvininejad et al., 2019; 2020b), we decode 5 candidate lengths in parallel (length beam) with T = 4 or T = 10 iterations. • DisCo (Kasai et al., 2020) predicts every target token given an arbitrary subset of the rest of the target tokens. Following Kasai et al. (2020), we use their parallel easy-first inference, and set the maximum number of iterations to 10 and the length beam size to 5.
Knowledge Distillation We apply sequence-level knowledge distillation (Hinton et al., 2015; Kim & Rush, 2016) when training both NAR and AR models (§2.3). For the teacher models, we use left-to-right AR transformer models: transformer-large for EN-DE, EN-ZH, and EN-FR, and transformer-base for EN-RO (Ghazvininejad et al., 2019; Kasai et al., 2020).

heading: 3.2 EXPERIMENTAL SETUP

text:
We experiment with 7 translation directions from four datasets of various training data sizes: WMT14 EN-DE (4.5M pairs, Bojar et al., 2014), WMT16 EN-RO (610K, Bojar et al., 2016), WMT17 EN-ZH (20M, Bojar et al., 2017), and WMT14 EN-FR (36M, EN→FR only). These datasets are all encoded into BPE subwords (Sennrich et al., 2016). We follow the preprocessing and data splits of previous work (EN-DE: Vaswani et al., 2017; EN-RO: Lee et al., 2018; EN-ZH: Hassan et al., 2018; Wu et al., 2019; EN-FR: Gehring et al., 2017). Following previous practice, we use SacreBLEU (Post, 2018) to evaluate EN→ZH performance, and BLEU (Papineni et al., 2002)
for others.3 For all autoregressive models, we apply beam search with size 5 and length penalty 1.0. All models are implemented using fairseq (Ott et al., 2019). S1 and Smax wall-clock time speedups (§2) are evaluated on the same single Nvidia V100 GPU with 16GB memory. We apply half-precision training and inference (Micikevicius et al., 2018; Ott et al., 2019). It speeds up NAR models’ Smax by 30+%, but not S1, in line with previous observations (Kim et al., 2019).
Hyperparameters We follow the hyperparameters of the base sized transformer (Vaswani et al., 2017): 8 attention heads, 512 model dimensions, and 2,048 hidden dimensions for both the encoder and decoder. For each model and dataset, the dropout rate is tuned from [0.1,0.2,0.3] based on development BLEU performance. The EN→FR models are trained for 500K updates, while others for 300K (Kasai et al., 2020). Dev. BLEU is measured after each epoch, and we average the 5 best checkpoints to obtain the final model (Vaswani et al., 2017). See the appendix for further details.

heading: 4 RESULTS AND DISCUSSION

text: We provide in-depth results comparing performance and speedup across AR and NAR models.

heading: 4.1 DEEP ENCODER, SHALLOW DECODER

text:
Fig. 1 shows translation speed-quality tradeoff curves of CMLM, DisCo, and AR models on WMT14 EN-DE and WMT16 EN-RO test data. For each model we plot the results of configurations with varying encoder and decoder depths. For brevity, we denote by E-D a model with an E-layer encoder and a D-layer decoder. All speedups are measured relative to the AR 6-6 baseline (§2).
Firstly, under the 6-6 configuration, the AR model outperforms both CMLM and DisCo by a considerable margin in BLEU, but it achieves the slowest S1 (see Fig. 1A–D). Using a single-layer decoder, AR 6-1 gains a substantial S1 speedup (2.6x for EN→DE and 2.9x for RO→EN), but this comes at a cost of BLEU: 28.34 vs. 27.39 for EN→DE, and 34.57 vs. 34.31 for RO→EN. AR 12-1
3SacreBLEU hash: BLEU+case.mixed+lang.en-zh+numrefs.1+smooth.exp+test.wmt17+tok.zh+version.1.3.7.
lands on a balanced middle ground: it yields similar BLEU to AR 6-6, but its S1 is more than 2.5 times faster. Notably, AR 12-1 achieves even faster S1 than that of the CMLM 6-6 model with 10 iterations. In contrast, NAR 12-1 models generally suffer in BLEU compared to the 6-6 configuration; e.g., 26.75 (DisCo 12-1) vs. 27.35 (DisCo 6-6) in EN→DE.
Interestingly, all NAR models achieve slower Smax than the AR 6-6 baseline (DisCo 6-6: 0.3x; CMLM 6-6 T=10: 0.1x in RO→EN). This is consistent with our complexity analysis in §2.2.2, where we found that with the same layer allocation, iterative NAR models need more total computation than the AR counterpart. AR 12-1 still gains a considerable speedup over AR 6-6 (2.0x in RO→EN). These results suggest that current NAR models have little advantage when translating a large amount of text given in advance, and one should clarify this distinction when discussing translation speed. See Table 5 in the appendix for full results from all four directions.
Table 2 presents results from large bitext experiments, EN↔ZH and EN→FR. We observe similar trends: AR deep-shallow achieves similar BLEU to AR 6-6 while boosting both S1 and Smax speed substantially. For EN↔ZH, AR deep-shallow has a more S1 speedup than DisCo (2.7x vs. 2.5x in EN→ZH, 2.9 vs. 2.6 in ZH→EN). Particularly noteworthy is its performance in EN→FR: 42.04 BLEU, a 1.4 point improvement over the best NAR model. These results illustrate that the strategy of having a deep encoder and shallow decoder remains effective in large bitext settings, when the model has to learn potentially more complex distributions from more samples.
Lastly, Table 3 compares AR deep-shallow to recent iteration-based NAR results. All NAR models use the 6-6 configuration with the base size except that Imputer (Saharia et al., 2020) uses 12 selfattention layers over the concatenated source and target. Overall, our AR deep-shallow models outperform most NAR models, with the only exception being EN→RO where it underperforms Imputer by 0.6 BLEU points. However, each iteration takes strictly more time in the Imputer model than in CMLM or DisCo, since it requires a fresh run of 12-layer self attention over a concatenation of input and output sequences. As we saw in Fig. 1, AR deep-shallow yields comparable S1 to CMLM 6-6 with 4 iterations, which would be about twice as fast as Imputer with 8 iterations.

heading: 4.2 CONSTRAINED VIEWS

text:
In this section, we present two controlled experiments to compare NAR and AR models thoroughly.
S1 Speed Constraint From §4.1 we see that compared to NAR models, AR deep-shallow yields a better translation speed-quality balance—despite being slightly slower in S1 on some of the datasets, it achieves better BLEU across the board. To confirm this result, we further compare an AR deepshallow model against two NAR models, controlling for S1 speed. More specifically, we experiment with NAR models of varying encoder depths, and pair each with as many decoder layers as possible until it reaches AR 12-1’s S1 speed. Fig. 2 (left) shows the results. For CMLM T=4, CMLM T=10, and DisCo, the best configurations of 12-layer encoders were paired up with 12, 4, and 9 decoder layers, respectively. All NAR models improve performance as the encoder becomes deeper and surpass the scores of the 6-6 baselines (shown as squares along x = 6). Nonetheless, there is still a large BLEU gap from AR 12-1. This illustrates that the two NAR models are not able to match AR deep-shallow’s accuracy under the same S1 speed budget.
Layer Constraint We can speed up autoregressive translation (AR) by developing a model with a deep encoder and a one-layer decoder. Here we thoroughly compare layer allocation strategies. Shown in Fig. 2 (middle) are results of NAR and AR methods under the constraint of 12 transformer layers in total. NAR models perform well when the decoder and encoder are balanced with slight tendency to deep encoders. On the other hand, the AR models perform consistently well with 4 or more encoder layers. This confirms that using deep encoders and shallow decoders is more effective in AR models than in NAR ones. Note that the number of parameters in each layer allocation differs since a decoder layer contains 30% more parameters than an encoder layer, due to cross attention.

heading: 5 FURTHER ANALYSIS

text:
Speedup and Batch Size When decoding with large batches, NAR models can be slower than their AR counterpart (§4.1). Here we further study this effect. Fig. 2 (right) plots the relative speedups of different models’ decoding with varying numbers of sentences per batch up to the hardware limit (“max,” §2.1). The speedup by NAR models diminishes as the batch size grows: they have similar decoding speed to AR 6-6 with batch size 50, and become slower with larger batch sizes. In contrast, the speedup from AR deep-shallow decreases much more gradually.
Decoder Depth and Reordering Words From earlier results we see that NAR models need deeper decoders than AR models to perform well. We hypothesize that one reason is that NAR decoders need to learn to adjust to diverging word order between the source and the target: an AR decoder
takes as input all preceding tokens and explicitly learns a conditional distribution, while an NAR decoder needs to learn target word ordering from scratch.
To test this hypothesis, we conduct the following controlled experiment in EN→DE translation. We choose German because of its divergence in word order from English. We first run the fast align tool (Dyer et al., 2013)4 on all bitext data (including the test set), and disable the NULL word feature to ensure that every English word is aligned to exactly one German word. We then shuffle the English words according to the order of their aligned German words. When multiple English words are aligned to the same German word, we keep the original English order. Finally, we apply the same BPE operations as the original data, and train and evaluate various models on the new reordered data. Table 4 (left) shows the results. AR gains the same improvement regardless of the layer configuration; in contrast, NAR 12-1 benefits more than NAR 6-6. This result supports our hypothesis that word reordering is one reason why NAR models need a deeper decoder.
Effects of Distillation We applied sequence-level knowledge distillation (Kim & Rush, 2016) to all models. Here we analyze its effects over the WMT14 EN→DE test data (Table 4 right). An AR transformer large model is used as the teacher model. All models benefit from distillation as indicated by positive ∆, including the AR models.5 Many recent works only compare NAR models trained with distillation to AR models trained without. Our finding shows that that AR models with distillation can be an additional baseline for future NAR research. AR deep-shallow deteriorates much less on the raw data compared to the iterative NAR methods, suggesting that the strategy of speeding up AR models is better suited to modeling raw, complex data than the NAR methods.
1-10 11-20 21-30 31-40 40+ 28
30
32
34
36
Reference Length
B L E U
(A) RO→EN
1-10 11-20 21-30 31-40 40+
14
16
18
20
22
24
26
Reference Length
(B) ZH→EN
1-10 11-20 21-30 31-40 40+ 28
30
32
34
Reference Length
(C) EN→FR AR 6-6 AR Deep-Shallow 12-1
Figure 3: Test BLEU and target length comparisons for the AR 6-6 and deep-shallow 12-1 models.
4https://github.com/clab/fast_align. 5While the same distillation data are used in Ghazvininejad et al. (2019), they report a smaller improvement from distillation in BLEU. There are several potential reasons: we tuned the dropout rate for each model on the validation data and averaged the checkpoints that achieved the top 5 BLEU scores (§3.2). We note that our results are in line with the previous observations (Kim et al., 2019; Zhou et al., 2020; Kasai et al., 2020) where a similar improvement is gained by distilling an AR transformer large model to a base one.
Breakdown by Sentence Length Fig. 3 illustrates the relation between BLEU scores and reference translation lengths. We observe almost identical patterns between AR 6-6 and deep-shallow models, suggesting that they perform similarly regardless of the translation length.
Can we reduce the decoder further? We saw that an autoregressive model with a single-layer decoder and a sufficiently deep encoder can retain the accuracy of the baseline with 6 layers each. One may ask whether we can make the decoder even more compact. Our preliminary experiments showed that we can remove the feed-forward module from the decoder without hurting performance. This increases the S1 speed by 10%. We leave further exploration to future work.
Length Candidates and Smax for NAR Following the original works (Ghazvininejad et al., 2019; Kasai et al., 2020), we fixed the number of length candidates (i.e., the length beam size) to 5 for all NAR models, but a smaller beam size can speed up Smax by allowing more sentences to be fed in a batch. Indeed, we found that NAR models can improve their Smax by reducing the beam size at the expense of some accuracy drop. For example, we observed a loss of 0.5 BLEU points in EN→DE when decreasing the length beam size from 5 to 1. Nonetheless, NAR 6-6 models with beam size 1 still resulted in 0.6–0.9x Smax compared to the AR 6-6 baseline.

heading: 6 FURTHER RELATED WORK

text:
Non-autoregressive Machine Translation In addition to the work already discussed, several other works proposed to iteratively refine (or insert) output predictions (Mansimov et al., 2019; Stern et al., 2019; Gu et al., 2019a; Chan et al., 2019; 2020; Li et al., 2020; Guo et al., 2020). Other approaches include adding a light autoregressive module to parallel decoding (Kaiser et al., 2018; Sun et al., 2019; Ran et al., 2021), partially decoding autoregressively (Stern et al., 2018; 2019), rescoring output candidates autoregressively (e.g., Gu et al., 2018), mimicking hidden states of an autoregressive teacher (Li et al., 2019), training with different objectives than vanilla cross-entropy (Libovický & Helcl, 2018; Wang et al., 2019b; Shao et al., 2020; Tu et al., 2020; Saharia et al., 2020; Ghazvininejad et al., 2020a), reordering input sentences (Ran et al., 2021), training on additional data from an autoregressive model (Zhou & Keung, 2020), and modeling with latent variables (Ma et al., 2019; Shu et al., 2020). The approach of adding a light autoregressive module is closest to our method, but note that we pack all non-autoregressive computation into the encoder.
Optimizing Autoregressive Transformer Prior work has suggested various ways to optimize autoregressive transformers for fast inference. For example, Kim et al. (2019) considered shallow decoders and layer tying (Dabre & Fujita, 2019; Dehghani et al., 2019) on the transformer decoder and found that it sped up inference on CPUs, but not on a GPU, which was our focus. Kim et al. (2019) also explored concurrent streams where multiple batches are fed at once to make better use of a GPU. Shi & Knight (2017) proposed a vocabulary reduction method to speed up the last softmax computation. Senellart et al. (2018) also adopted vocabulary reduction and explored “fat decoder, thin encoder” on RNN-based models. Zhang et al. (2018) used dynamic programming in an average attention network to accelerate inference. Wu et al. (2019) developed a model with dynamic convolutions and compared its speed and accuracy with non-autoregressive models. Other works proposed methods to reduce attention computation in autoregressive transformers (Kitaev et al., 2020; Katharopoulos et al., 2020; Chelba et al., 2020; Peng et al., 2021). Some of these methods can be used orthogonally to further facilitate fast inference in a transformer, but our goal is to fairly reexamine the speed-quality tradeoff between autoregressive and non-autoregressive approaches under the same conditions.

heading: 7 CONCLUSION AND FUTURE WORK

text: We presented theoretical and empirical studies to demonstrate that autoregressive neural machine translation can be dramatically sped up by a simple layer allocation strategy: deep encoder, shallow decoder. Compared to strong non-autoregressive models, deep-shallow autoregressive models achieve substantial improvement in translation quality with comparable inference speed. Our results suggest that layer allocation, knowledge distillation, and speed measurement are important aspects that future work on non-autoregressive machine translation should take into consideration. More generally, a model with a deep encoder and a shallow decoder can be used for any sequence-tosequence task, including large-scale pretraining (Lewis et al., 2020; Liu et al., 2020).

heading: ACKNOWLEDGMENTS

text: We thank Luke Zettlemoyer, Marcin Junczys-Dowmunt, Ofir Press, and Tim Dettmers as well as the anonymous reviewers for their helpful feedback and discussions on this work. This research was in part funded by the Funai Overseas Scholarship to Jungo Kasai. Nikolaos Pappas was supported by the Swiss National Science Foundation under the project UNISON, grant number P400P2 183911.

heading: A APPENDIX

text:
Table 5 provides comparisons of speed and quality in the WMT14 EN−DE and WMT16 EN−RO datasets.
A.2 HYPERPARAMETERS AND SETTING
All of our models are implemented in fairseq (Ott et al., 2019) and trained with 16 Telsa V100 GPUs CUDA 10.1, and cuDNN 7.6.3. We used mixed precision and distributed training over 16 GPUs interconnected by Infiniband (Micikevicius et al., 2018; Ott et al., 2018). Apart from EN↔ZH where we used separate BPE operations, we tie all embeddings (Press & Wolf, 2017; Inan et al., 2017).
We generally follow the hyperparameters chosen in Vaswani et al. (2017); Ghazvininejad et al. (2019); Kasai et al. (2020) regardless of the numbers of encoding and decoding layers.6 Specifically, we list the hyperparameters in Table 6 for easy replication. All other hyperparamter options are left as default values in fairseq.
6We use their code at https://github.com/facebookresearch/Mask-Predict and https: //github.com/facebookresearch/DisCo.
A.3 SAMPLE OUTPUTS
Here we provide translation outputs randomly sampled from the validation data in ZH→EN. We do not find a qualitative difference between AR 6-6 and deep-shallow 12-1 models.

title: DEEP ENCODER, SHALLOW DECODER: REEVALUATING NON-AUTOREGRESSIVE MACHINE TRANSLATION


summaries: The paper under review studies the epoch wise double descent phenomena empirically. The epoch wise double descent phenomena is the observation that the risk of a large neural network trained with SGD first decreases, then increases, and finally decreases again as a function of the epochs or SGD steps. In addition, it proposes a quantity called ``optimization variance (OV)'', and it demonstrate that OV correlates with the test error. Based on this observation, it proposes to early stop when the OV reaches a minimum.

summaries: Having a stopping rule without the validation set is intriguing, especially for datasets with a low number of samples. The authors propose a rule that doesn't require the validation dataset, i.e. it is solely based on training data. It introduces the notion of optimization variance which is different from the variance of gradients.

summaries: The paper studies the trajectory of the test error as a function of training time focusing on Epoch-Wise Double-Descent.  Similar to "Rethinking Bias-Variance Trade-off for Generalization of Neural Networks" by Yang et. al., the paper shows that if one decomposes the test error to bias and variance terms, Double Descent occurs as a function of train time as a result of unimodality of the variance term (while the bias term decreases monotonically).  The paper also introduces a quantity they name optimization variance (OV) and that correlates with the test error (while being only a function of the train set) and can be useful for early stopping.

abstractText: Unlike the conventional wisdom in statistical learning theory, the test error of a deep neural network (DNN) often demonstrates double descent: as the model complexity increases, it first follows a classical U-shaped curve and then shows a second descent. Through bias-variance decomposition, recent studies revealed that the bell-shaped variance is the major cause of model-wise double descent (when the DNN is widened gradually). This paper investigates epoch-wise double descent, i.e., the test error of a DNN also shows double descent as the number of training epoches increases. Specifically, we extend the bias-variance analysis to epoch-wise double descent, and reveal that the variance also contributes the most to the zero-one loss, as in model-wise double descent. Inspired by this result, we propose a novel metric, optimization variance (OV), to measure the diversity of model updates caused by the stochastic gradients of random training batches drawn in the same iteration. OV can be estimated using samples from the training set only but correlates well with the (unknown) test error. It can be used to predict the generalization ability of a DNN when the zero-one loss is used in test, and hence early stopping may be achieved without using a validation set.

authors:
Madhu S Advani
Andrew M Saxe

title: High-dimensional dynamics of generalization error in neural networks

authors:
Zeyuan Allen-Zhu
Yuanzhi Li
Zhao Song

title: A convergence theory for deep learning via overparameterization

venue: In Proc. 36th Int’l Conf. on Machine Learning,

authors:
Devansh Arpit
Stanisław Jastrzębski
Nicolas Ballas
David Krueger
Emmanuel Bengio
Maxinder S Kanwal
Tegan Maharaj
Asja Fischer
Aaron Courville
Yoshua Bengio
Simon Lacoste-Julien

title: A closer look at memorization in deep networks

venue: In Proc. 34th Int’l Conf. on Machine Learning,

authors:
Peter L Bartlett
Philip M Long
Gábor Lugosi
Alexander Tsigler

title: Benign overfitting in linear regression

venue: Proceedings of the National Academy of Sciences,

authors:
Mikhail Belkin
Daniel Hsu
Siyuan Ma
Soumik Mandal

title: Reconciling modern machine learning practice and the classical bias-variance trade-off

authors:
Mikhail Belkin
Daniel Hsu
Ji Xu

title: Two models of double descent for weak features

authors:
Stephen Boyd
Lieven Vandenberghe

title: Convex Optimization

authors:
Niladri Chatterji
Behnam Neyshabur
Hanie Sedghi

title: The intriguing role of module criticality in the generalization of deep networks

venue: In Proc. Int’l Conf. on Learning Representations,

authors:
Laurent Dinh
Razvan Pascanu
Samy Bengio
Yoshua Bengio

title: Sharp minima can generalize for deep nets

title: A unified bias-variance decomposition for zero-one and squared loss

venue: In Proc. of the 17th National Conf. on Artificial Intelligence,

authors:
Jerome Friedman
Trevor Hastie
Robert Tibshirani

title: The Elements of Statistical Learning, volume 1. Springer series in statistics

authors:
Mario Geiger
Arthur Jacot
Stefano Spigler
Franck Gabriel
Levent Sagun
Stéphane d’Ascoli
Giulio Biroli
Clément Hongler
Matthieu Wyart

title: Scaling description of generalization with number of parameters in deep learning

authors:
Stuart Geman
Elie Bienenstock
René Doursat

title: Neural networks and the bias/variance dilemma

venue: Neural Computation,

authors:
Trevor Hastie
Andrea Montanari
Saharon Rosset
Ryan J Tibshirani

title: Surprises in highdimensional ridgeless least squares interpolation

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

venue: In Proc. IEEE Conf. on Computer Vision and Pattern Recognition,

authors:
Reinhard Heckel
Fatih Furkan Yilmaz

title: Early stopping in deep networks: Double descent and how to eliminate it

title: Bias/variance decompositions for likelihood-based estimators

authors:
Dimitris Kalimeris
Gal Kaplun
Preetum Nakkiran
Benjamin Edelman
Tristan Yang
Boaz Barak
Haofeng Zhang

title: SGD on neural networks learns functions of increasing complexity

venue: In Proc. Advances in Neural Information Processing Systems,

authors:
Nitish Shirish Keskar
Dheevatsa Mudigere
Jorge Nocedal
Mikhail Smelyanskiy
Ping Tak Peter Tang

title: On large-batch training for deep learning: Generalization gap and sharp minima

authors:
Diederik P. Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

authors:
Ron Kohavi
David H Wolpert

title: Bias plus variance decomposition for zero-one loss functions

venue: In Proc. 13th Int’l Conf. on Machine Learning,

authors:
Eun Bae Kong
Thomas G Dietterich

title: Error-correcting output coding corrects bias and variance

venue: In Proc. 12th Int’l Conf. on Machine Learning,

title: Learning multiple layers of features from tiny images

authors:
Alex Krizhevsky
Ilya Sutskever
Geoffrey E Hinton

title: ImageNet classification with deep convolutional neural networks

authors:
Yann LeCun
Léon Bottou
Yoshua Bengio
Patrick Haffner

title: Gradient-based learning applied to document recognition

venue: Proceedings of the IEEE,

authors:
Wesley J Maddox
Gregory Benton
Andrew Gordon Wilson

title: Rethinking parameter counting in deep models: Effective dimensionality revisited

title: Understanding overfitting peaks in generalization error: Analytical risk curves for l2 and l1 penalized interpolation

venue: IEEE Journal on Selected Areas in Information Theory,

authors:
Preetum Nakkiran
Gal Kaplun
Yamini Bansal
Tristan Yang
Boaz Barak
Ilya Sutskever

title: Deep double descent: Where bigger models and more data hurt

authors:
Yuval Netzer
Tao Wang
Adam Coates
Alessandro Bissacco
Bo Wu
Andrew Y. Ng

title: Reading digits in natural images with unsupervised feature learning

venue: In Proc. NIPS Workshop on Deep Learning and Unsupervised Feature Learning

authors:
Behnam Neyshabur
Ryota Tomioka
Nathan Srebro

title: Norm-based capacity control in neural networks

venue: In Proc. of the 28th Conf. on Learning Theory,

authors:
Behnam Neyshabur
Srinadh Bhojanapalli
David McAllester
Nati Srebro

title: Exploring generalization in deep learning

authors:
Nasim Rahaman
Aristide Baratin
Devansh Arpit
Felix Draxler
Min Lin
Fred Hamprecht
Yoshua Bengio
Aaron Courville

title: On the spectral bias of neural networks

authors:
Shai Shalev-Shwartz
Shai Ben-David

title: Understanding Machine Learning: From Theory to Algorithms

authors:
Karen Simonyan
Andrew Zisserman

title: Very deep convolutional networks for large-scale image recognition

title: Bias, variance and prediction error for classification rules

venue: Technical report, Department of Preventive Medicine and Biostatistics and Department of Statistics,

title: An overview of statistical learning theory

venue: IEEE Trans. on Neural Networks,

authors:
Huan Wang
Nitish Shirish Keskar
Caiming Xiong
Richard Socher

title: Identifying generalization properties in neural networks

authors:
Han Xiao
Kashif Rasul
Roland Vollgraf

title: Fashion-MNIST: a novel image dataset for benchmarking machine learning

venue: algorithms. CoRR,

authors:
Zitong Yang
Yaodong Yu
Chong You
Jacob Steinhardt
Yi Ma

title: Rethinking bias-variance trade-off for generalization of neural networks

authors:
Chiyuan Zhang
Samy Bengio
Moritz Hardt
Benjamin Recht
Oriol Vinyals

title: Understanding deep learning requires rethinking generalization

authors:
Xiao Zhang
Dongrui Wu

title: Rethink the connections among generalization, memorization and the spectral bias of DNNs

heading: 1 INTRODUCTION

text:
Deep Neural Networks (DNNs) usually have large model capacity, but also generalize well. This violates the conventional VC dimension (Vapnik, 1999) or Rademacher complexity theory (ShalevShwartz & Ben-David, 2014), inspiring new designs of network architectures (Krizhevsky et al., 2012; Simonyan & Zisserman, 2015; He et al., 2016; Zagoruyko & Komodakis, 2016) and reconsideration of their optimization and generalization (Zhang et al., 2017; Arpit et al., 2017; Wang et al., 2018; Kalimeris et al., 2019; Rahaman et al., 2019; Allen-Zhu et al., 2019).
Model-wise double descent, i.e., as a DNN’s model complexity increases, its test error first shows a classical U-shaped curve and then enters a second descent, has been observed on many machine learning models (Advani & Saxe, 2017; Belkin et al., 2019a; Geiger et al., 2019; Maddox et al., 2020; Nakkiran et al., 2020). Multiple studies provided theoretical evidence of this phenomenon in some tractable settings (Mitra, 2019; Hastie et al., 2019; Belkin et al., 2019b; Yang et al., 2020; Bartlett et al., 2020; Muthukumar et al., 2020). Specifically, Neal et al. (2018) and Yang et al. (2020) performed bias-variance decomposition for mean squared error (MSE) and the cross-entropy (CE) loss, and empirically revealed that the bell-shaped curve of the variance is the major cause of modelwise double descent. Maddox et al. (2020) proposed to measure the effective dimensionality of the parameter space, which can be further used to explain model-wise double descent.
Recently, a new double descent phenomenon, epoch-wise double descent, was observed, when increasing the number of training epochs instead of the model complexity1 (Nakkiran et al., 2020). Compared with model-wise double descent, epoch-wise double descent is relatively less explored. Heckel & Yilmaz (2020) showed that epoch-wise double descent occurs in the situation where different parts of DNNs are learned at different epochs, which can be eliminated by proper scaling of step sizes. Zhang & Wu (2020) discovered that the energy ratio of the high-frequency components of a DNN’s prediction landscape, which can reflect the model capacity, switches from increase to
1In practice, some label noise is often added to the training set to make the epoch-wise double descent more conspicuous.
decrease at a certain training epoch, leading to the second descent of the test error. However, this metric fails to provide further information on generalization, such as the early stopping point, or how the size of a DNN influences its performance.
This paper utilizes bias-variance decomposition of the zero-one (ZO) loss (CE loss is still used in training) to further investigate epoch-wise double descent. By monitoring the behaviors of the bias and the variance, we find that the variance plays an important role in epoch-wise double descent, which dominates and highly correlates with the variation of the test error.
Though the variance correlates well with the test error, estimating its value requires training models on multiple different training sets drawn from the same data distribution, whereas in practice usually only one training set is available2. Inspired by the fact that the source of variance comes from the random-sampled training sets, we propose a novel metric, optimization variance (OV), to measure the diversity of model updates caused by the stochastic gradients of random training batches drawn in the same iteration. This metric can be estimated from a single model using samples drawn from the training set only. More importantly, it correlates well with the test error, and thus can be used to determine the early stopping point in DNN training, without using any validation set.
Some complexity measures have been proposed to illustrate the generalization ability of DNNs, such as sharpness (Keskar et al., 2017) and norm-based measures (Neyshabur et al., 2015). However, their values rely heavily on the model parameters, making comparisons across different models very difficult. Dinh et al. (2017) shows that by re-parameterizing a DNN, one can alter the sharpness of its searched local minima without affecting the function it represents; Neyshabur et al. (2018) shows that these measures cannot explain the generalization behaviors when the size of a DNN increases. Our proposed metric, which only requires the logit outputs of a DNN, is less dependent on model parameters, and hence can explain many generalization behaviors, e.g., the test error decreases as the network size increases. Chatterji et al. (2020) proposed a metric called Model Criticality that can explain the superior generalization performance of some architectures over others, yet it is unexplored that whether this metric can be used to indicate generalization in the entire training procedure, especially for some relatively complex generalization behaviors, such as epoch-wise double descent.
To summarize, our contributions are:
• We perform bias-variance decomposition on the test error to explore epoch-wise double descent. We show that the variance dominates the variation of the test classification error.
• We propose a novel metric, OV, which is calculated from the training set only and correlates well with the test classification error.
• Based on the OV, we propose an approach to search for the early stopping point without using a validation set, when the zero-one loss is used in test. Experiments verified its effectiveness.
The remainder of this paper is organized as follows: Section 2 introduces the details of tracing bias and variance over training epochs. Section 3 proposes the OV and demonstrates its ability to indicate the test behaviors. Section 4 draws conclusions and points out some future research directions.

heading: 2 BIAS AND VARIANCE IN EPOCH-WISE DOUBLE DESCENT

text: This section presents the details of tracing the bias and the variance during training. We show that the variance dominates the epoch-wise double descent of the test error.

heading: 2.1 A UNIFIED BIAS-VARIANCE DECOMPOSITION

text:
Bias-variance decomposition is widely used to analyze the generalization properties of machine learning algorithms (Geman et al., 1992; Friedman et al., 2001). It was originally proposed for
2Assume the training set has n samples. We can partition it into multiple smaller training sets, each with m samples (m < n), and then train multiple models. However, the variance estimated from this case would be different from the one estimated from training sets with n samples. We can also bootstrap the original training set into multiple ones, each with n samples. However, the data distribution of each bootstrap replica is different from the original training set, and hence the estimated variance would also be different.
the MSE loss and later extended to other loss functions, e.g., CE and ZO losses (Kong & Dietterich, 1995; Tibshirani, 1996; Kohavi et al., 1996; Heskes, 1998). Our study utilizes a unified bias-variance decomposition that was proposed by Domingos (2000) and applicable to arbitrary loss functions.
Let (x, t) be a sample drawn from the data distribution D, where x ∈ Rd denotes the ddimensional input, and t ∈ Rc the one-hot encoding of the label in c classes. The training set T = {(xi, ti)}ni=1 ∼ Dn is utilized to train the model f : Rd → Rc. Let y = f(x; T ) ∈ Rc be the probability output of the model f trained on T , and L(t,y) the loss function. The expected loss ET [L(t,y)] should be small to ensure that the model both accurately captures the regularities in its training data, and also generalizes well to unseen data.
According to Domingos (2000), a unified bias-variance decomposition3 of ET [L(y, t)] is:
ET [L(t,y)] = L(t, ȳ)︸ ︷︷ ︸ Bias +β ET [L(ȳ,y)]︸ ︷︷ ︸ Variance , (1)
where β takes different values for different loss functions, and ȳ is the expected output:
ȳ = arg min y∗∈Rc ∣∣∑c k=1 y ∗ k=1,y ∗ k≥0 ET [L(y∗,y)]. (2)
ȳ minimizes the variance term in (1), which can be regarded as the “center" or “ensemble" of y w.r.t. different T . Table 1 shows specific forms of L, ȳ, and β for different loss functions (the detailed derivations can be found in Appendix A). This paper focuses on the bias-variance decomposition of the ZO loss, because epoch-wise double descent of the test error is more obvious when the ZO loss is used (see Appendix C). To capture the overall bias and variance, we analyzed Ex,tET [L(t,y)], i.e., the expectation of ET [L(t,y)] over the distribution D.

heading: 2.2 TRACE THE BIAS AND VARIANCE TERMS OVER TRAINING EPOCHS

text:
To trace the bias term Ex,t[L(t, ȳ)] and the variance term Ex,tET [L(ȳ,y)] w.r.t. the training epoch, we need to sample several training sets and train models on them respectively, so that the bias and variance terms can be estimated from them.
Concretely, let T ∗ denote the test set, f(x; Tj , q) the model f trained on Tj ∼ Dn (j = 1, 2, ...,K) for q epochs. Then, the estimated bias and variance terms at the q-th epoch, denoted as B(q) and V (q), respectively, can be written as:
B(q) = E(x,t)∈T ∗ [ L ( t, f̄(x; q) )] , (3)
V (q) = E(x,t)∈T ∗  1 K K∑ j=1 L(f̄(x; q), f(x; Tj , q))  , (4) 3In real-world situations, the expected loss consists of three terms: bias, variance, and noise. Similar to
Yang et al. (2020), we view t as the groundtruth and ignore the noise term.
where
f̄(x; q) = H  K∑ j=1 H(f(x; Tj , q))  , (5) is the voting result of {f(x; Tj , q)}Kj=1.
We should emphasize that, in real-world situations, D cannot be obtained, hence Tj in our experiments was randomly sampled from the training set (we sampled 50% training data for each Tj). As a result, despite of showing the cause of epoch-wise double descent, the behaviors of bias and variance may be different when the whole training set is used.
We considered ResNet (He et al., 2016) and VGG (Simonyan & Zisserman, 2015) models4 trained on SVHN (Netzer et al., 2011), CIFAR10 (Krizhevsky, 2009), and CIFAR100 (Krizhevsky, 2009). SGD and Adam (Kingma & Ba, 2014) optimizers with different learning rates were used. The batchsize was set to 128, and all models were trained for 250 epochs with data augmentation. Prior to sampling {Tj}Kj=1 (K = 5) from the training set, 20% labels of the training data were randomly shuffled to introduce epoch-wise double descent.
Figure 1 shows the expected ZO loss and its bias and variance. The bias descends rapidly at first and then generally converges to a low value, whereas the variance behaves almost exactly the same as the test error, mimicking even small fluctuations of the test error. To stabilize that, we performed additional experiments with different optimizers, learning rates, and levels of label noise (see Appendices E and G). All experimental results demonstrated that it is mainly the variance that contributes to epoch-wise double descent.

heading: 2.3 DISCUSSION

text:
Contradicting to the traditional view that the variance keeps increasing because of overfitting, our experimental results show a more complex behavior: the variance starts high and then decreases rapidly, followed by a bell curve. The difference at the beginning (when the number of epochs is small) is mainly due to the choice of loss functions (see experimental results of bias-variance decomposition for MSE and CE losses in Appendix F). CE and MSE losses, analyzed in the traditional
4Adapted from https://github.com/kuangliu/pytorch-cifar
learning theory, can reflect the degree of difference of probabilities, whereas the ZO loss only the labels. At the early stage of training, the output probabilities are close to random guesses, and hence a small difference in probabilities may lead to completely different labels, resulting in the distinct variance for different loss functions. However, the reason why the variance begins to diminish at the late phase of training is still unclear. We will explore this problem in our future research.

heading: 3 OPTIMIZATION VARIANCE (OV)

text: This section proposes a new metric, OV, to measure the diversity of model updates introduced by random training batches during optimization. This metric can indicate test behaviors without any validation set.

heading: 3.1 NOTATION AND DEFINITION

text:
Section 2 verified the synchronization between the test error and the variance, but its application is limited because estimating the variance requires: 1) a test set, and, 2) models trained on different training sets drawn from the same data distribution. It’d be desirable to capture the test behavior of a DNN using a single training set only, without a test set.
According to the definition in (1), the variance measures the model diversity caused by different training samples drawn from the same distribution, i.e., the outputs of DNN change according to the sampled training set. As the gradients are usually the only information transferred from training sets to models during the optimization of DNN, we need to measure the variance of a DNN introduced by the gradients calculated from different training batches. More specifically, we’d like to develop a metric to reflect the function robustness of DNNs to sampling noises. If the function captured by a DNN drastically varies w.r.t. different training batches, its generalization error is very likely to be poor due to a large variance introduced by the optimization procedure. A similar metric is the sharpness of local minima proposed by Keskar et al. (2017), which measures the robustness of local minima as an indicator of the generalization error. However, this metric is only meaningful for local minima and hence cannot be applied in the entire optimization process.
Mathematically, for a sample (x, t) ∼ D, let f(x;θ) be the logit output of a DNN with parameter θ. Let TB ∼ Dm be a training batch with m samples, g : TB → R|θ| the optimizer outputting the update of θ based on TB . Then, we can get the function distribution Fx(TB) over a training batch TB , i.e., f(x;θ + g(TB)) ∼ Fx(TB). The variance of Fx(TB) reflects the model diversity caused by different training batches. The formal definition of OV is given below. Definition 1 (Optimization Variance (OV)) Given an input x and model parameters θq at the q-th training epoch, the OV on x at the q-th epoch is defined as
OVq(x) , ETB
[ ‖f(x;θq + g(TB))− ETBf(x;θq + g(TB))‖ 2 2 ] ETB [ ‖f(x;θq + g(TB))‖22
] . (6) Note that OVq(x) measures the relative variance, because the denominator in (6) eliminates the influence of the logit’s norm. In this way, OVq(x) at different training phases can be compared. The motivation here comes from the definition of coefficient of variation5 (CV) in probability theory and statistics, which is also known as the relative standard deviation. CV is defined as the ratio between the standard deviation and the mean, and is independent of the unit in which the measurement is taken. Therefore, CV enables comparing the relative diversity between two different measurements.
In terms of OV, the variance of logits, i.e., the numerator of OV, is not comparable across epochs due to the influence of their norm. In fact, even if the variance of logits maintains the same during the whole optimization process, its influence on the decision boundary is limited when the logits are large. Consequently, by treating the norm of logits as the measurement unit, following CV we set OV to ∑ i σ 2 i / ∑ i µ 2 i , where σi and µi represent the standard deviation and the mean of the i-th logit, respectively. If we remove the denominator, the value of OV will no longer has the indication ability for generalization error, especially at the early stage of the optimization process.
5https://en.wikipedia.org/wiki/Coefficient_of_variation
Intuitively, the OV represents the inconsistency of gradients’ influence on the model. If OVq(x) is very large, then the models trained with different sampled TB may have distinct outputs for the same input, leading to high model diversity and hence large variance. Note that here we emphasize the inconsistency of model updates rather than the gradients themselves. The latter can be measured by the gradient variance. The gradient variance and the OV are different, because sometimes diverse gradients may lead to similar changes of the function represented by DNN, and hence small OV. More on the relationship between the two variances can be found in Appendix B.

heading: 3.2 EXPERIMENTAL RESULTS

text:
We calculated the expectation of the OV over x, i.e., Ex[OVq(x)], which was estimated from 1,000 random training samples. The test set was not involved at all.
Figure 2 shows how the test accuracy (solid curves) and Ex[OVq(x)] (dashed curves) change with the number of training epochs. Though sometimes the OV may not exhibit clear epoch-wise double descent, e.g., VGG16 in Figure 2(c), the symmetry between the solid and dashed curves generally exist, suggesting that the OV, which is calculated from the training set only, is capable of predicting the variation of the test accuracy. Similar results can also be observed using different optimizers and learning rates (see Appendix I).
Note that epoch-wise double descent is not a necessary condition for applying OV. As shown in Figure 2 (blue curves), we compared the values of OV and generalization errors of DNNs when there are 0% label noises, from which we can see the curves of generalization errors have no epochwise double descent, yet the proposed OV still works pretty well.
OVq(x) in Figure 2 was estimated on all training batches; however, this may not be necessary: a small number of training batches are usually enough. To demonstrate this, we trained ResNet and VGG on several datasets using Adam optimizer with learning rate 0.0001, and estimated OVq(x) from different number of training batches. The results in Figure 3 show that we can well estimate the OV using as few as 10 training batches.
Another intriguing finding is that even unstable variations of the test accuracy can be reflected by the OV. This correspondence is clearer on simpler datasets, e.g., MNIST (LeCun et al., 1998) and FashionMNIST (Xiao et al., 2017). Figure 4 shows the test accuracy and OV for LeNet-5 (LeCun et al., 1998) trained on MNIST and FashionMNIST without label noise. Spikes of the OV and the test accuracy happen simultaneously at the same epoch.
Our experimental results demonstrate that the generalization ability of a DNN can be indicated by the OV during stochastic training, without using a validation set. This phenomenon can be used to determine the early stopping point, and beyond.

heading: 3.3 EARLY STOPPING WITHOUT A VALIDATION SET

text:
The common process to train a DNN involves three steps: 1) partition the dataset into a training set and a validation set; 2) use the training set to optimize the DNN parameters, and the validation set to determine when to stop training, i.e., early stopping, and record the early stopping point; 3) train the DNN on the entire dataset (combination of training and validation sets) for the same number of epochs. However, there is no guarantee that the early stopping point on the training set is the same as the one on the entire dataset. So, an interesting questions is: is it possible to directly perform early stopping on the entire dataset, without a validation set?
The OV can be used for this purpose. For more robust performance, instead of using the OV directly, we may need to smooth it to alleviate random fluctuations.
As an example, we smoothed the OV by a moving average filter of 10 epochs, and then performed early stopping on the smoothed OV with a patience of 10 epochs. As a reference, early stopping with the same patience was also performed directly on the test accuracy to get the groundtruth. However, it should be noted that the latter is unknown in real-world applications. It is provided for verification purpose only.
We trained different DNN models on several datasets (SVHN: VGG11 and ResNet18; CIFAR10: VGG13 and ResNet18; CIFAR100: VGG16 and ResNet34) with different levels of label noise (10% and 20%) and optimizers (Adam with learning rate 0.001 and 0.0001, SGD with momentum 0.9 and learning rate 0.01 and 0.001). Then, we compared the groundtruth early stopping point and the test accuracy with those found by performing early stopping on the OV6. The results are shown in Figure 5. The true early stopping points and those found from the OV curve were generally close, though there were some exceptions, e.g., the point near (40, 100) in Figure 5(a). However, the test errors, which are what a model designer really cares about, were always close.
3.4 SMALL SIZE OF THE TRAINING SET
For large datasets, a validation set can be easily partitioned from the training set without hurting the generalization performance. Therefore, OV is more useful in the case of small datasets. To this end, we performed experiments with small numbers (2000, 4000, 6000) of the training samples in CIFAR10 to verify the effectiveness of OV in this situation. Considering the limited numbers of training samples, we trained a small Convolution Neural Network (CNN) using Adam optimizer with learning rate 0.0001, whose detailed information can be found in Appendix H.
The experimental results are shown in Figure 6. It can be observed that: a) When the size of the training set is small, OV still correlates well with the generalization performance as a function of the training epochs, which ver-
ifies the validity of our results on small datasets; b) As expected, more training samples usually lead to better generalization performance, which can also be reflected by comparing the values of OV.
6Training VGG11 on SVHN with Adam optimizer and learning rate 0.001 was unstable (see Appendix D), so we did not include its results in Figure 5.

heading: 3.5 NETWORK SIZE

text:
In addition to indicating the early stopping point, the OV can also explain some other generalization behaviors, such as the influence of the network size. To verify that, we trained ResNet18 with different network sizes on CIFAR10 for 100 epochs with no label noise, using Adam optimizer with learning rate 0.0001. For each convolutional layer, we set the number of filters k/4 (k = 1, 2, ..., 8) times the number of filters in the original model. We then examined the OV of ResNet18 with different network sizes to validate its correlation with the test accuracy. Note that we used SGD optimizer with learning rate 0.001 and no momentum to calculate the OV, so that the cumulative influence during training can be removed to make the comparison more fair.
The results are shown in Figure 7. As k increases, the OV gradually decreases, i.e., the diversity of model updates introduced by different training batches decreases when widening ResNet18, suggesting that increasing the network size can improve the model’s resilience to sampling noise, which leads to better generalization performance. The Pearson correlation coefficient between the OV and the test accuracy reached −0.94 (p = 0.0006). Lastly, we need to point out that we did not observe a strong cross-model correlation between the OV and the test accuracy when comparing the generalization ability of significantly different model architectures, e.g., VGG
and ResNet. Our future research will look for a more universal cross-model metric to illustrate the generalization performance.

heading: 4 CONCLUSIONS

text:
This paper has shown that the variance dominates the epoch-wise double descent, and highly correlates with the test error. Inspired by this finding, we proposed a novel metric called optimization variance, which is calculated from the training set only but powerful enough to predict how the test error changes during training. Based on this metric, we further proposed an approach to perform early stopping without any validation set. Remarkably, we demonstrated that the training set itself may be enough to predict the generalization ability of a DNN, without a dedicated validation set.
Our future work will: 1) apply the OV to other tasks, such as regression problems, unsupervised learning, and so on; 2) figure out the cause of the second descent of the OV; and, 3) design regularization approaches to penalize the OV for better generalization performance.

heading: A BIAS-VARIANCE DECOMPOSITION FOR DIFFERENT LOSS FUNCTIONS

text:
This section presents detailed deduction of bias-variance decomposition for different loss functions.
A.1 THE MEAN SQUARED ERROR (MSE) LOSS
For the MSE loss, we have L(t,y) = ‖t−y‖22, and need to calculate ȳ based on (2). We first ignore the constraints and solve the following problem:
ỹ = arg min y∗
ET [‖y∗ − y‖22], (7)
whose solution is ỹ = ET y. It can be easily verified that ỹ satisfies the constraints in (2), and hence ȳ = ỹ = ET y.
Then, we can decompose the MSE loss as: ET [‖t− y‖22] = ET [‖t− ȳ + ȳ − y‖22]
= ET [‖t− ȳ‖22 + ‖ȳ − y‖22 + 2(t− ȳ)T (ȳ − y)] = ‖t− ȳ‖22 + ET [‖ȳ − y‖22] + 0, (8)
where the first term denotes the bias, and the second denotes the variance. We can also get β = 1.
A.2 CROSS-ENTROPY (CE) LOSS For L(t,y) = ∑c k=1 tk log tk yk
, ȳ can be obtained by applying the Lagrange multiplier method (Boyd & Vandenberghe, 2004) to (2):
l(y∗, λ) = ET
[ c∑
k=1
y∗k log y∗k yk
] + λ · ( 1−
c∑ k=1 y∗k
) . (9)
To minimize l(y∗, λ), we need to compute its partial derivatives to y∗ and λ: ∂l
∂y∗k = ET
[ log
y∗k yk + 1
] − λ, k = 1, 2, ..., c
∂l ∂λ = 1− c∑ k=1 y∗k.
By setting these derivatives to 0, we get:
ȳk = 1
Z exp{ET [log yk]}, k = 1, 2, ..., c (10) where Z = ∑c k=1 exp{ET [log yk]} is a normalization constant independent of k.
Because
ET
[ c∑
k=1
αk log ȳk yk
] = − logZ, ∀αk c∑ k=1 αk = 1, (11)
we have:
ET
[ c∑
k=1
tk log tk yk
] = ET [ c∑
k=1
tk
( log
tk ȳk + log ȳk yk
)]
= c∑ k=1 tk log tk ȳk + ET
[ c∑
k=1
tk log ȳk yk
]
= c∑ k=1 tk log tk ȳk − logZ
= c∑ k=1 tk log tk ȳk + ET
[ c∑
k=1
ȳk log ȳk yk
] , (12)
from which we obtain β = 1.
A.3 THE ZERO-ONE (ZO) LOSS
For the ZO loss, i.e., L(t,y) = 1con{H(t) 6= H(y)}, ȳ is the voting result, i.e., H(ET [H(y)]), so that the variance can be minimized. However, the value of β depends on the relationship between ȳ and t.
When ȳ = t, we have:
ET [1con{H(t) 6= H(y)}] = 0 + ET [1con{H(ȳ) 6= H(y)}] = 1con{H(t) 6= H(ȳ)}+ ET [1con{H(ȳ) 6= H(y)}] , (13)
clearly, β = 1.
When ȳ 6= t, we have:
ET [1con{H(t) 6= H(y)}] = PT (H(y) 6= t) = 1− PT (H(y) = t) = 1con{H(t) 6= H(ȳ)} − PT ( H(y) = t
∣∣H(y) = ȳ)PT (H(y) = ȳ) − PT ( H(y) = t
∣∣H(y) 6= ȳ)PT (H(y) 6= ȳ) . (14) Since ȳ 6= H(t), it follows that
PT ( H(y) = t ∣∣H(y) = ȳ) = 0. (15) Then, (14) becomes:
ET [1con{H(t) 6= H(y)}] = 1con{H(t) 6= H(ȳ)} − PT ( H(y) = t ∣∣H(y) 6= ȳ)PT (H(y) 6= ȳ) = 1con{H(t) 6= H(ȳ)} − PT ( H(y) = t
∣∣H(y) 6= ȳ)ET [1con{H(ȳ) 6= H(y)}] , (16) hence, β = −PT ( H(y) = t
∣∣H(y) 6= ȳ).

heading: B CONNECTIONS BETWEEN THE OPTIMIZATION VARIANCE AND THE

text:
GRADIENT VARIANCE
This section shows the connection between the gradient variance and the optimization variance in Definition 1.
For simplicity, we ignore q in OVq(x) and denote g(TB)−ETBg(TB) by g̃(TB). Then, the gradient variance Vg can be written as:
Vg = ETB [ ‖g(TB)− ETBg(TB)‖ 2 2 ] = ETB [ g̃(TB)T g̃(TB) ] . (17)
Denote the Jacobian matrix of the logits f(x;θ) w.r.t. θ by Jθ(x), i.e.,
Jθ(x) = [∇θf1(x;θ),∇θf2(x;θ), ...,∇θfc(x;θ)] , (18)
where fj(x;θ) is the j-th entry of f(x;θ), and c is the number of classes.
Using first order approximation, we have:
f(x;θ + g(TB)) ≈ f(x;θ) + Jθ(x)T g(TB), (19)
and OV (x) can be written as:
OV (x) ≈ ETB
[ g̃(TB)TJθ(x)Jθ(x)T g̃(TB) ] f(x;θ)T f(x;θ) + ETB [O (‖g(TB)‖2)] ≈ ETB [ g̃(TB)TJθ(x)Jθ(x)T g̃(TB) ] f(x;θ)T f(x;θ) . (20)
The only difference between Ex [OV (x)] and Vg is the middle weight matrix Ex [ Jθ(x)Jθ(x) T
f(x;θ)T f(x;θ)
] .
This suggests that penalizing the gradient variance can also reduce the optimization variance.
Figure 8 presents the curves of Vg in the training procedure. It can be observed that Vg also shows some ability to indicate the generalization performance. However, compared with the results in Figure 2, we can see that OV demonstrates a stronger power for indicating the generalization error than Vg . More importantly, Vg loses its comparability when the network size increases, while OV
can be more reliable to architectural changes with the middle weight matrix Ex [ Jθ(x)Jθ(x) T
f(x;θ)T f(x;θ)
] to
normalize Vg , which is illustrated in Figure 7.
We also notice that ‖ETBg(TB)‖ 2 2 is usually far less than ETB ‖g(TB)‖ 2 2, hence Vg and the gradient norm ETB ‖g(TB)‖ 2 2 almost present the same curves in the training procedure.
VGG11
VGG13
VGG16

heading: C BEHAVIORS OF DIFFERENT LOSS FUNCTIONS

text:
Many different loss functions can be used to evaluate the test performance of a model. They may have very different behaviors w.r.t. the training epochs. As shown in Figure 9, the epoch-wise double descent can be very conspicuous on test error, i.e., the ZO loss, but barely observable on CE and MSE losses, which increase after the early stopping point. This is because at the late stage of training, model outputs approach 0 or 1, resulting in the increase of the CE and MSE losses on the misclassified test samples, though the decision boundary may be barely changed. When rescaling the weights of the last layer by a positive real number, the ZO loss remains the same because of the untouched decision boundary, whereas the CE and MSE losses are changed. Thus, we perform bias-variance decomposition on the ZO loss to study epoch-wise double descent.
D VGG11 ON SVHN BY ADAM OPTIMIZER WITH LEARNING RATE 0.001
Training VGG11 on SVHN by Adam optimizer with learning rate 0.001 is unstable, as shown in Figure 14(a). Figure 10 shows the test error and optimization variance. For 0% and 10% label noise, the test error stays large (the test accuracy is low) for a long period in the early phase of training. The optimization variance is also abnormal.

heading: E LOSS, BIAS AND VARIANCE W.R.T. DIFFERENT LEVELS OF LABEL NOISE

text:
Label noise makes epoch-wise double descent more conspicuous to observe (Nakkiran et al., 2020). If the variance is the major cause of double descent, it should match the variation of the test error
when adding different levels of label noise. Figure 11 shows an example to compare the loss, variance, and bias w.r.t. different levels of label noise. Though label noise impacts both the bias and the variance, the latter appears to be more sensitive and shows better synchronization with the loss. For instance, when we randomly shuffle a small percentage of labels, say 10%, a valley clearly occurs between 20 and 50 epoches for the variance, whereas it is less obvious for the bias. In addition, it seems that the level of label noise does not affect the epoch at which the loss reaches its first minimum. This is surprising, because the label noise is considered highly related to the complexity of the dataset. Our future work will explore the role label noise plays in the generalization of DNNs.
Loss
Var
Bias

heading: F BIAS AND VARIANCE TERMS W.R.T. DIFFERENT LOSS FUNCTIONS

heading: G BIAS AND VARIANCE TERMS W.R.T. DIFFERENT OPTIMIZERS AND LEARNING RATES

heading: H DETAILED INFORMATION OF THE SMALL CNN MODEL

text: We present the detailed information of the architecture trained with small numbers of training samples. It consists of two convolutional layers and two fully-connected layers, as shown in Table 2.

heading: I OPTIMIZATION VARIANCE AND TEST ACCURACY W.R.T. DIFFERENT OPTIMIZERS AND LEARNING RATES

title: OPTIMIZATION VARIANCE: EXPLORING GENERAL-