summaries: This work uses GANs to recover clean faces from occluded counterparts. The effectiveness of the proposed method is verified qualitatively and quantitatively on CelebA-HQ. The proposed framework can be generalized to several face-related tasks, such as unconstrained face recognition. Although the novelty of the method is not really impressive, the proposed method seems to be useful for face-related applications and the experimental results are convincing to me.

summaries: The paper proposes a complex generative framework for image completion (particularly human face completion). It aims at solving the following challenges: 1) complete the human face at both low and high resolution; 2) control the attribute of the synthetic content; 3) without the need of complex post-processing. To achieve so, this paper proposes a progressively attentive GAN to complete face image at high resolution with multiple controllable attributes in a single forward pass without post-processing. Particularly it introduces a frequency-oriented attentive module (FAM) to attend on finer details.

abstractText: Face completion is a challenging task with the difficulty level increasing significantly with respect to high resolution, the complexity of “holes" and the controllable attributes of filled-in fragments. Our system addresses the challenges by learning a fully end-to-end framework that trains generative adversarial networks (GANs) progressively from low resolution to high resolution with conditional vectors encoding controllable attributes. We design a novel coarse-to-fine attentive module network architecture. Our model is encouraged to attend on finer details while the network is growing to a higher resolution, thus being capable of showing progressive attention to different frequency components in a coarse-to-fine way. We term the module Frequency-oriented Attentive Module (FAM). Our system can complete faces with large structural and appearance variations using a single feed-forward pass of computation with mean inference time of 0.54 seconds for images at 1024× 1024 resolution. A pilot human study shows our approach outperforms state-of-the-art face completion methods. The code will be released upon publication.

authors:
Connelly Barnes
Eli Shechtman
Adam Finkelstein
Dan B Goldman

title: Patchmatch: A randomized correspondence algorithm for structural image editing

venue: ACM Trans. Graph.,

authors:
Marcelo Bertalmio
Guillermo Sapiro
Vincent Caselles
Coloma Ballester

title: Image inpainting

venue: In Proceedings of the 27th annual conference on Computer graphics and interactive techniques,

authors:
Marcelo Bertalmio
Luminita Vese
Guillermo Sapiro
Stanley Osher

title: Simultaneous structure and texture image inpainting

venue: IEEE Transactions on image processing,

authors:
Adrian Bulat
Georgios Tzimiropoulos

title: How far are we from solving the 2d & 3d face alignment problem?(and a dataset of 230,000 3d facial landmarks)

venue: In International Conference on Computer Vision,

authors:
Wengling Chen
James Hays

title: Sketchygan: Towards diverse and realistic sketch to image synthesis

venue: arXiv preprint arXiv:1801.02753,

authors:
Xi Chen
Yan Duan
Rein Houthooft
John Schulman
Ilya Sutskever
Pieter Abbeel

title: Infogan: Interpretable representation learning by information maximizing generative adversarial nets

venue: In Advances in Neural Information Processing Systems,

authors:
Yunjey Choi
Minje Choi
Munyoung Kim
Jung-Woo Ha
Sunghun Kim
Jaegul Choo

title: Stargan: Unified generative adversarial networks for multi-domain image-to-image translation

venue: arXiv preprint arXiv:1711.09020,

authors:
Antonio Criminisi
Patrick Perez
Kentaro Toyama

title: Object removal by exemplar-based inpainting

venue: In Computer Vision and Pattern Recognition,

authors:
Soheil Darabi
Eli Shechtman
Connelly Barnes
Dan B Goldman
Pradeep Sen

title: Image melding: Combining inconsistent images using patch-based synthesis

authors:
Emily Denton
Sam Gross
Rob Fergus

title: Semi-supervised learning with context-conditional generative adversarial networks

venue: arXiv preprint arXiv:1611.06430,

authors:
Emily L Denton
Soumith Chintala
Rob Fergus

title: Deep generative image models using a laplacian pyramid of adversarial networks

venue: In Advances in neural information processing systems,

authors:
Alexei A Efros
Thomas K Leung

title: Texture synthesis by non-parametric sampling

venue: In Computer Vision,

authors:
Pablo Garrido
Levi Valgaerts
Ole Rehmsen
Thorsten Thormahlen
Patrick Perez
Christian Theobalt

title: Automatic face reenactment

authors:
Ian Goodfellow
Jean Pouget-Abadie
Mehdi Mirza
Bing Xu
David Warde-Farley
Sherjil Ozair
Aaron Courville
Yoshua Bengio

title: Generative adversarial nets

authors:
Karol Gregor
Ivo Danihelka
Alex Graves
Danilo Jimenez Rezende
Daan Wierstra

title: Draw: A recurrent neural network for image generation

venue: arXiv preprint arXiv:1502.04623,

authors:
James Hays
Alexei A Efros

title: Scene completion using millions of photographs

venue: In ACM Transactions on Graphics (TOG),

authors:
Jia-Bin Huang
Sing Bing Kang
Narendra Ahuja
Johannes Kopf

title: Image completion using planar structure guidance

venue: ACM Transactions on Graphics (TOG),

authors:
Satoshi Iizuka
Edgar Simo-Serra
Hiroshi Ishikawa

title: Globally and locally consistent image completion

venue: In International Conference on Machine Learning,

authors:
Phillip Isola
Jun-Yan Zhu
Tinghui Zhou
Alexei A Efros

title: Image-to-image translation with conditional adversarial networks

venue: arXiv preprint arXiv:1611.07004,

authors:
Justin Johnson
Alexandre Alahi
Li Fei-Fei

title: Perceptual losses for real-time style transfer and super-resolution

venue: In European Conference on Computer Vision,

authors:
Takuhiro Kaneko
Kaoru Hiramatsu
Kunio Kashino

title: Generative attribute controller with conditional filtered generative adversarial networks

venue: In IEEE Conference on Computer Vision and Pattern Recognition (CVPR),

authors:
Tero Karras
Timo Aila
Samuli Laine
Jaakko Lehtinen

title: Progressive growing of gans for improved quality, stability, and variation

venue: arXiv preprint arXiv:1710.10196,

authors:
Diederik Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

venue: arXiv preprint arXiv:1412.6980,

title: Image completion using global optimization

authors:
Vivek Kwatra
Arno Schödl
Irfan Essa
Greg Turk
Aaron Bobick

title: Graphcut textures: image and video synthesis using graph cuts

venue: In ACM Transactions on Graphics (ToG),

authors:
Anat Levin
Assaf Zomet
Yair Weiss

title: Learning how to inpaint from global image statistics

venue: In null,

authors:
Kai Li
Feng Xu
Jue Wang
Qionghai Dai
Yebin Liu

title: A data-driven approach for facial expression synthesis in video

venue: In Computer Vision and Pattern Recognition (CVPR),

authors:
Yijun Li
Sifei Liu
Jimei Yang
Ming-Hsuan Yang

title: Generative face completion

venue: arXiv preprint arXiv:1704.05838,

authors:
Guilin Liu
Fitsum A Reda
Kevin J Shih
Ting-Chun Wang
Andrew Tao
Bryan Catanzaro

title: Image inpainting for irregular holes using partial convolutions

venue: arXiv preprint arXiv:1804.07723,

authors:
Andrew L Maas
Awni Y Hannun
Andrew Y Ng

title: Rectifier nonlinearities improve neural network acoustic models

venue: In Proc. ICML,

authors:
Mehdi Mirza
Simon Osindero

title: Conditional generative adversarial nets

venue: arXiv preprint arXiv:1411.1784,

authors:
Alejandro Newell
Kaiyu Yang
Jia Deng

title: Stacked hourglass networks for human pose estimation

authors:
Deepak Pathak
Philipp Krahenbuhl
Jeff Donahue
Trevor Darrell
Alexei A Efros

title: Context encoders: Feature learning by inpainting

authors:
Patrick Pérez
Michel Gangnet
Andrew Blake

title: Poisson image editing

venue: In ACM Transactions on graphics (TOG),

authors:
Olaf Ronneberger
Philipp Fischer
Thomas Brox

title: U-net: Convolutional networks for biomedical image segmentation

venue: In International Conference on Medical Image Computing and ComputerAssisted Intervention,

authors:
Olga Russakovsky
Jia Deng
Hao Su
Jonathan Krause
Sanjeev Satheesh
Sean Ma
Zhiheng Huang
Andrej Karpathy
Aditya Khosla
Michael Bernstein

title: Imagenet large scale visual recognition challenge

venue: International Journal of Computer Vision,

authors:
Patsorn Sangkloy
Jingwan Lu
Chen Fang
Fisher Yu
James Hays

title: Scribbler: Controlling deep image synthesis with sketch and color

authors:
Ashish Shrivastava
Tomas Pfister
Oncel Tuzel
Josh Susskind
Wenda Wang
Russ Webb

title: Learning from simulated and unsupervised images through adversarial training

venue: arXiv preprint arXiv:1612.07828,

authors:
Karen Simonyan
Andrew Zisserman

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

venue: arXiv preprint arXiv:1409.1556,

authors:
Justus Thies
Michael Zollhöfer
Marc Stamminger
Christian Theobalt
Matthias Nießner

title: Face2face: Real-time face capture and reenactment of rgb videos

authors:
Dmitry Ulyanov
Andrea Vedaldi
Victor Lempitsky

title: Instance normalization: The missing ingredient for fast stylization

venue: arXiv preprint arXiv:1607.08022,

authors:
Ting-Chun Wang
Ming-Yu Liu
Jun-Yan Zhu
Andrew Tao
Jan Kautz
Bryan Catanzaro

title: Highresolution image synthesis and semantic manipulation with conditional gans

venue: arXiv preprint arXiv:1711.11585,

authors:
Yonatan Wexler
Eli Shechtman
Michal Irani

title: Space-time completion of video

venue: IEEE Transactions on pattern analysis and machine intelligence,

authors:
Marta Wilczkowiak
Gabriel J Brostow
Ben Tordoff
Roberto Cipolla

title: Hole filling through photomontage

venue: In BMVC,

authors:
Wenqi Xian
Patsorn Sangkloy
Jingwan Lu
Chen Fang
Fisher Yu
James Hays

title: Texturegan: Controlling deep image synthesis with texture patches

venue: arXiv preprint arXiv:1706.02823,

authors:
Chao Yang
Xin Lu
Zhe Lin
Eli Shechtman
Oliver Wang
Hao Li

title: High-resolution image inpainting using multi-scale neural patch synthesis

venue: arXiv preprint arXiv:1611.09969,

authors:
Raymond A Yeh
Chen Chen
Teck Yian Lim
Alexander G Schwing
Mark Hasegawa-Johnson
Minh N Do

authors:
Jiahui Yu
Zhe Lin
Jimei Yang
Xiaohui Shen
Xin Lu
Thomas S Huang

title: Generative image inpainting with contextual attention

venue: arXiv preprint arXiv:1801.07892,

authors:
Jun-Yan Zhu
Taesung Park
Phillip Isola
Alexei A Efros

title: Unpaired image-to-image translation using cycle-consistent adversarial networks

venue: arXiv preprint arXiv:1703.10593,

heading: 1 INTRODUCTION

text:
Image completion is a technique to replace target regions, either missing or unwanted, of images with synthetic content so that the completed images look natural, realistic and appealing. Two types of methods have been used: data similarity driven methods and data distribution based generative methods. In the first paradigm, texture synthesis or patch matching are usually used (Efros & Leung, 1999; Kwatra et al., 2003; Criminisi et al., 2003; Wilczkowiak et al., 2005; Komodakis, 2006; Barnes et al., 2009; Darabi et al., 2012; Huang et al., 2014; Wexler et al., 2007). The second paradigm learns the underlying distribution governing the data generation with respect to the context and is able to synthesize novel content. Much progress (Iizuka et al., 2017; Yeh et al., 2017; Li et al., 2017; Yang et al., 2016; Denton et al., 2016; Pathak et al., 2016; Yu et al., 2018; Liu et al., 2018) has been made since the generative adversarial network (GAN) was proposed (Goodfellow et al., 2014).
We adopt the data distribution based generative method and focus on human face completion in this paper. Three important issues are addressed. First, previous methods are only able to complete faces at low resolutions (e.g. 176 × 216 (Iizuka et al., 2017) and 256 × 256 (Yu et al., 2018)). Second, most approaches cannot control the attributes of the synthesized content. Previous methods focus on generating random realistic content. However, users may want to complete the missing parts with certain properties (e.g. expressions). Third, most existing approaches (Iizuka et al., 2017; Yeh et al., 2017; Li et al., 2017) require post processing (e.g. Poisson Blending (Pérez et al., 2003)) or complex inference process (e.g. thousands of optimization iterations (Yeh et al., 2017) or repeatedly feeding an incomplete image to CNNs at multiple scales (Yang et al., 2016)).
To overcome the above limitations, we propose a novel progressively attentive GAN to complete face images at high resolution with multiple controllable attributes in a single forward pass without any post processing. We utilize facial landmarks as backbone guidance of face structures and propose a straightforward method of integrating them in our system. The training methodology of growing GANs progressively (Karras et al., 2017) is used to generate high-resolution images end-to-end. To avoid distorting the learned coarse structures when the network is growing to a higher resolution, we design a novel Frequency-oriented Attentive Module (FAM) to encourage the model to attend on finer details (i.e. higher-frequency structures, see Figure 1). A conditional version of our network is designed so that the appearance properties (e.g. male or female), and facial expressions of the synthesized faces can be controlled. Moreover, we design a set of loss functions inducing the network
to blend the synthesized content with the contexts in a realistic way. Our method was compared with state-of-the-art approaches on a high-resolution face dataset CelebA-HQ (Karras et al., 2017). Both the evaluations and a pilot user study showed that our approach completed face images significantly more naturally than existing methods.
The main contributions of this paper are: (i) We propose a progressively attentive GAN architecture, which incorporates a novel frequency-oriented attention mechanism, to complete face images with random masks in much higher resolution than existing methods. (ii) A conditional version of our model is designed to control multiple attributes of the synthesized content. (iii) Our framework is able to complete images in a single forward pass, without any post-processing, and thus fast.

heading: 2 RELATED WORK

text:
There is a large body of image completion literature. Early non-learning based algorithms (Efros & Leung, 1999; Bertalmio et al., 2000; 2003) complete missing content by propagating information from known neighborhoods, based on low level cues or global statistics (Levin et al., 2003). Texture synthesis and patch matching based approaches (Efros & Leung, 1999; Kwatra et al., 2003; Criminisi et al., 2003; Wilczkowiak et al., 2005; Komodakis, 2006; Barnes et al., 2009; Darabi et al., 2012; Huang et al., 2014; Wexler et al., 2007) find similar structures from the context of the input image or from an external database (Hays & Efros, 2007) and then paste them to fill in the holes.
Recent learning based methods have shown the capability of CNNs to complete large missing content. Based on existing GANs, the Context Encoder (CE) (Pathak et al., 2016) encodes the contexts of masked images to latent representations, and then decodes them to natural content images, which are pasted into the original contexts for completion. However, the synthesized content of CE is often blurry and has inconsistent boundaries. Given a trained generative model, Yeh et al. (Yeh et al., 2017) propose a framework to find the most plausible latent representations of contexts to complete masked images. The Generative Face Completion model (GFC) (Li et al., 2017) and the Global and Local Consistent model (GL) (Iizuka et al., 2017) use both global and local discriminators, combined with post processing, to complete images more coherently. Built on GL, Yu et al. (Yu et al., 2018) design a contextual attention layer (CTX) to help the model borrow contextual information from distant locations. Liu et al. (Liu et al., 2018) incorporates partial convolutions to handle irregular masks. Unfortunately, these approaches can only complete face images in relatively low resolutions (e.g. 176 x 216 (Iizuka et al., 2017) and 256× 256 (Yu et al., 2018)). Yang et al. (Yang et al., 2016) combine a global content network and a texture network, and the networks are trained at multiple scales repeatedly to complete high-resolution images (512× 512). Like the patch matching based approaches, Yang et al. assume that the missing content always shares some similar textures with the context, which is improbable for the face completion task.
Many methods try to generate high quality images and stabilize the training process. The Laplacian GAN (Denton et al., 2015) uses a a cascade of CNNs to synthesize images from coarse to fine by generating high frequency information at different layers. The Deep Recurrent Attentive Writer (DRAW) architecture (Gregor et al., 2015), which is a spatial attention mechanism, generates images iteratively by learning to read and write parts of images at each time-step with a sequence of variational auto-encoders (VAEs). Unfortunately, these techniques are unable to synthesize high-resolution images (e.g. 64× 64 (Gregor et al., 2015; Denton et al., 2015)). Karras et al. (Karras et al., 2017) put forward a progressive training methodology (Progressive GAN) to grow GANs from low to high resolution, and are able to generate realistic 1024× 1024 images. However, since all the parameters remain trainable at the growing stage, learned coarse structures can be altered and distorted, and thus the training process of Progressive GANs is usually unstable. Note that these generative models cannot be applied to the image completion task directly because they aim at generating natural content which are not necessarily consistent with the image contexts.

heading: 3 APPROACH

heading: 3.1 PROBLEM FORMULATION

text:
Denoted by Λ an image lattice (e.g., 1024 × 1024 pixels). Let IΛ be an RGB image defined on the lattice Λ. Denote by Λt and Λc the target region to complete and the remaining context region respectively which form a partition of the lattice.Without loss of generality, we assume Λt is a single connected component region.IΛt is masked out with the same gray pixel value. Let MΛ be a binary mask image with all pixels in MΛt being 1 and all pixels in MΛc being 0. For notational simplicity, we will omit the subscripts Λ, Λt and Λc when the text context is clear.
The objective of image completion is to generate a synthesized image Isyn that looks natural, realistic and appealing for an observed image Iobs with the target region IobsΛt masked out in the ground-truth full image Igt. Furthermore, it is desirable to control the completion according to a set of attributes which are assumed to be independent from each other (e.g., to respect the underlying intrinsic ambiguities due to the loss of information in the target region). Let A = (a1, · · · , aN ) be a N -dim vector with ai ∈ {0, 1} encoding if a corresponding attribute appears (ai = 1) or not (ai = 0) (e.g. the “Male” attribute in Figure 5). We define the generator as,
Isyn = G(Iobs,M,A; θG), subject to I syn Λc ≈ IobsΛc (1)
where θG collects all parameters of the generator, and ≈ represents the two context regions, IsynΛc and IobsΛc , need to kept very similar (both to be elaborated later).

heading: 3.2 THE PROPOSED METHOD

text:
The proposed method is built on progressive GANs with well-executed combination between the network architecture, appropriate receipt of loss functions and a novel FAM.
Denote by Gr and Dr the generator and discriminator at resolution r respectively, where r ∈ {1, · · · , R} is the index of resolution (e.g., r = 1 represents 4 × 4 and r = R = 9 represents 1024× 1024). Accordingly, we have the observed corrupted image, its corresponding binary mask and its ground-truth uncorrupted image (in training only), Iobsr , Mr and I gt r at each resolution.
The generator, Gr takes as input the observed data XGr and the attribute vector A, then outputs a completed image Isynr . It consists of two components,
Isynr = Gr(X G r , A; θGr ) = G compl r (G enc r (X G r ; θGencr ), A; θGcomplr ), (2)
where Gencr (·) encodes the input XGr to a latent low dimensional vector. The latent vector is concatenated with the attribute vector. The concatenated vector plays the role of the noise random variable z in the original GAN. Then, Gcomplr (·) transforms the concatenated vector to a sample Isynr (i.e., the completed image). Gencr and G compl r are mirrored to each other in the form of U-shape networks (Ronneberger et al., 2015; Newell et al., 2016). θGr = (θGencr , θGcomplr ).
The discriminator, Dr classifies its input XDr and has two output branches, the fake versus real classification branch and the attribute prediction branch. It consists of three components: a shared feature backbone and two head classifiers. We have,
Dr(X D r ; θDr ) = {Dclsr (Fr(XDr ; θFr ); θDclsr ), D attr r (Fr(XDr ; θFr ); θDattrr )} (3)
Where the feature backbone, Fr(XDr ; θFr ) computes the feature map. On top of the feature map, the first head classifier, Dcls(·) computes binary classification between real and fake, and the second one, Dattr(·) predicts an attribute vector. All the parameters of the discriminator are collected by θDr = (θFr , θDclsr , θDattrr ). We note that the discriminator is only needed in training. We will omit the notations for parameters in equations when no confusion is caused.
Progressive Growing of Generators and Discriminators. Following the methodology proposed in (Karras et al., 2017), we start with training G1 and D1. Then, at the growing stage r (r > 1), Gr = (Gr−1, G fade−in r ) is first created on top of the previous trained stage Gr−1 with newly added layers Gfade−inr , and both of them are trainable in a fade-in process for smooth transition. The discriminators grow in the same way. The alternation of Gr−1 in training stage Gr may lead to the instability of the growing process and the loss of learned structures of the underlying image distribution, which motivates the proposed FAM in growing generators (Section 3.2.1).
Inputs for Generators and Discriminators, XGr and X D r . We have,
XGr = (Î obs r ,Mr, Lr) and X D r = (Ir, Lr) (4)
where Lr represents the facial landmarks. Recent works (Isola et al., 2016; Wang et al., 2017; Zhu et al., 2017; Sangkloy et al., 2017; Xian et al., 2017; Chen & Hays, 2018) have shown the capability of GANs to translate sketches or edges to photo-realistic images. Given a corrupted image, it is better if the model is able to “draw” a sketch of face first, which provides a backbone guidance for image
completion. We utilize the following methods to compute landmarks (Figure 2).
• In training, we extract landmarks from the uncorrupted image at 256 × 256 resolution using an off-the-shelf pre-trained Face Alignment Network (FAN) (Bulat & Tzimiropoulos, 2017) which achieved very good results for faces in the wild.
• In testing, to predict landmarks from corrupted images, we first train a single stage face completion network at 256× 256 resolution, denoted by GL, using reconstruction loss (Section 3.2.2) only. For a testing image, we use GL to generate a blurry completed image from which the landmarks are extracted with FAN.
L is up-sampled or down-sampled to Lr to match the size of networks at different resolutions. Ir in XDr represents either the uncorrupted image or the image synthesized by Gr. For Î obs r in X G r , we have Îobs1 = I obs 1 , and Î obs r is the output of FAM (r > 1) as described in following section.

heading: 3.2.1 FAM: THE PROPOSED FREQUENCY-ORIENTED ATTENTIVE MODULE

text:
Figure 3 illustrates the proposed FAM. To obtain a smooth transition from low to high resolutions, we design a FAM architecture (i.e. the red components in Figure 3), which is a frequency-oriented attention mechanism integrated along with the resolution change, so that the model learns filters to encourage Gfade−inr (blue components in Figure 3) to read and write information that are important at level r, but have not been handled well at level r − 1. By doing those, • Our model attends on higher frequency signals as resolution increases (see Figure 1), thus improv-
ing the completion performance. • Our model preserves what have been learned in previous progressive stages, thus furthering the
stability of progressive GANs.
Existing approaches (Gregor et al., 2015; Yu et al., 2018) use spatial attention mechanisms to encourage networks to attend to selected parts of images (e.g. rectangular regions), while FAM is an attention model in the frequency domain. But different from a regular band-pass filter, the filters generated by FAM is predicted based on semantics of images which are enforced by the objective function (Eqn. 10), and thus is also sensitive to locations inferred on-the-fly in a coarse-to-fine manner. For instance, the model pays more attention to eye regions where the rich details aggregate, especially at a high resolution.
Recall that at the growing stage r (r > 1) in training, we haveGr = (Gr−1, Gfade−inr ). In the vanilla progressive GANs, we will compute the completed image Isynr = Gr(I obs r ,Mr, Lr, A) (simplified from Eqn. 2 for clarity). The previously trained Gr−1 can be changed while optimizing the stage r, which may lead to unexpected updating. Our FAM prevents Gr−1 from changing to wrong directions. To that end, we first introduce a read module which utilizes a read filter F̂read to extract the most valuable information in both Iobsr and I obs r−1,
Îobsr , Î obs r−1 = read(I obs r , I obs r−1, F̂read), (5)
which is implemented by,
Îobsr = F̂read (1−Mr) Iobsr , (6) Îobsr−1 = Downsample((1− F̂read) (1−Mr) Ĩobsr−1), (7)
where denotes element-wise multiplication. Ĩobsr−1 is up-sampled from Iobsr−1 to match the resolution of Iobsr . Ĩ obs r−1 represents the blurred (i.e. low-frequency) version of I obs r since high-frequency information is lost when Iobsr−1 is down-sampled from I obs r . The read filter F̂read is defined by,
F̂read = β · Fread + γ, β : {
2α, 2− 2α, γ : { 0, α ≤ 0.5 2α− 1, 0.5 < α ≤ 1.0 (8)
where Fread is computed by Fread = ToFilter(G fixed r−1 (I obs r−1,Mr−1, Lr−1)) using a trained generator Gfixedr−1 with fixed weights and a small trainable network ToFilter. α is a weight increasing linearly from 0 to 1 proportional to the number of seen images during growing. F̂read starts as an all-zero filter, is adjusted by a trainable ToFilter at the growing stages and eventually increased to all ones.
As illustrated in Figure 3, given the outputs from the read module, Îobsr and Î obs r−1, we can generate the corresponding completed images, Isynr and the up-sampled I syn r−1 respectively, and the write filter Fwrite. Then, to generate the final completed image at stage r, we also introduce a write module,
Îsynr =write(I syn r , I syn r−1, F̂write) (9)
=(Isynr · α+ I syn r−1 · (1− α)) (1−Mr) + (F̂write Isynr + (1− F̂write) I syn r−1) Mr,
where F̂write = β ·Fwrite +γ and Fwrite is predicted from the last feature maps. At a low resolution, both the read and write module exploit more on the low-frequency information, but gradually move to exploit higher-frequency information when resolution increases under the guidance of minimizing the objective function (Eqn. 10). Fread and Fwrite can be discarded when the growing process is done. A testing image only needs to go through one generator that is independent of FAM (blue flow in Figure 3). This is more efficient than the Laplacian GAN (Denton et al., 2015) that requires feeding a testing sample to a cascade of generators, and uses multiple discriminators in training.

heading: 3.2.2 LOSS FUNCTIONS

text:
Beside extending the original adversarial loss function, we design three new loss functions to enforce sharp image completion.
Adversarial Loss Given an uncorrupted image Igt, its attribute vector A, a mask M , landmarks L, and the corresponding corrupted image Iobs we define the loss by, ladv(Igt,M,L, Iobs, A|G,D) = log (1−Dcls(Isyn, L) + logDcls(Igt, L), where Isyn = G(Iobs,M,L,A)).
Attribute Loss Similar to the InfoGAN models (Chen et al., 2016; Choi et al., 2017), for the attribute prediction head classifier in the discriminator, we define the attribute loss based on cross-entropy between the predicted attribute vector, Âreal = Dattr(Ireal, L) and Âobs = Dattr(Iobs, L) and the corresponding targets, A for both a real uncorrupted image and a synthesized image. We have, lattr(I
gt, A,M, Iobs|G,D) = CrossEntropy(A, Âgt) + CrossEntropy(A, Âobs). Reconstruction Loss Since our method generates the entire completed face rather than only the target region, we define a wighted reconstruction loss lrec to preserve both the target region and the context region, which is defined as, lrec(Igt,M,L, Iobs, A|G) = ‖κ M Idiff‖1 + ‖(1 − κ) (1−M) Idiff‖1, where Idiff = Igt − Isyn and κ is the trade-off parameter. Feature Loss In additional to the reconstruction loss in terms of pixel values, we also encourage the synthesized image to have a similar feature representation (Johnson et al., 2016) based on a pre-trained deep neural network φ. Let φj be the activations of the jth layer of φ, the feature loss is defined by, lfeat(Igt,M,L, Iobs, A|φ,G) = ‖φj(Igt) − φj(Isyn))‖22. In our experiments, φj is the relu2_2 layer of a 16-layer VGG network (Simonyan & Zisserman, 2014) pre-trained on the ImageNet dataset (Russakovsky et al., 2015).
Boundary Loss To make the generator learn to blend the synthesized target region with the original context region seamlessly, we further define a close-up reconstruction loss along the boundary of the mask. Similar to (Yeh et al., 2017), we first create a weighted kernel w based on the mask image M . w is computed by blurring the mask boundary in M with a mean filter so that the pixels closer to the mask boundary are assigned larger weights. The kernel size of the mean filters is seven in our experiments. We have, lbdy(Igt,M,L, Iobs, A|G) = ‖w (Igt − Isyn)‖1. Our model is trained end-to-end by integrating the expected loss of the different loss functions defined above under the minimax game setting. We have,
min G max D Ladv(G,D) + λ1Lattr(G,D) + λ2Lrec(G) + λ3Lfeat(G,φ) + λ4Lbdy(G). (10)
Where λi’s are trade-off parameters between different loss terms.
Training without Multiple Controllable Attributes. To that end, since it is a special case of the proposed formulation stated above, we can simply remove the components involving attributes such as the attribute loss in a straightforward way. The resulting system still enjoys end-to-end learning.

heading: 4 EXPERIMENTS

text:
Datasets and Experiment Settings We used the CelebA-HQ (Karras et al., 2017) dataset for evaluation. It contains 30,000 aligned face images at 1024× 1024 resolution. The dataset is split randomly while ensuring there is no identity overlap between test/training sets: 3,009 images for testing, and 26,991 for training. There were two types of masks: center and random. The center mask was a square region in the middle of the image with a side length of half the size of the image. The random masks, generated in a similar way to previous methods (Iizuka et al., 2017; Yu et al., 2018), were rectangular regions with random width-to-height ratios, sizes and locations covering about 5% to 25% of the original images. Hyper-parameters used for training are listed in the supplemental materials.
Quality Comparison with the Context Encoder Our method was compared with the Context Encoder (CE) (Pathak et al., 2016) on high-resolution face completion. Since the original networks
of CE were designed for 128× 128 images, we used a naive approach to fit it to different resolutions. One, two, and three convolutional layers were added to the encoder, decoder and discriminator for 256 × 256, 512 × 512 and 1024 × 1024 networks respectively. The result (Figure 4) shows that, when the resolution increased, our method learned details incrementally and synthesized sharper faces, while CE generated poorer images with more distortions.
Quantitative Comparison with State-of-the-art Methods As noted in literatures (Yeh et al., 2017; Yu et al., 2018), reconstruction metrics such as mean L1, L2 errors and peak signal-to-noise ratio (RSNR) that are commonly used are not good quantitative evaluation metrics for inpainting methods since image completion aims at completing missing regions with plausible content rather than reconstructing it. As a reference, we show the comparison between our method and state-of-theart models at their reported resolutions respectively: 128 × 128 for GL with center masks (using implementation of (Yu et al., 2018)) and 256× 256 for CTX with random masks (Table 1). Semantic Completion We first trained a high-resolution (1024 × 1024) model with center masks (examples shown in Figure 5) to test whether our model is capable of learning high-level semantics and structures of faces and synthesize large missing regions. The second model was trained with random masks, but was able to handle arbitrary (e.g. irregular hand-drawn) shapes of masks. The result (Figure 5) shows that our model was able to capture the anatomical structures of faces and generate content that is consistent with the holistic semantics.
Attribute Controller Unlike previous image completion techniques (Iizuka et al., 2017; Yeh et al., 2017; Li et al., 2017; Yang et al., 2016; Pathak et al., 2016; Yu et al., 2018) that generate only random plausible content, our network completes faces with structurally meaningful content whose appearances and expressions are controllable. Existing approaches (Mirza & Osindero, 2014; Choi et al., 2017; Kaneko et al., 2017) can only control facial expressions roughly (e.g. smiling or not smiling). In contrast, our model is able to control subtle expressions. In the experiment, the face appearance was conditioned on a “Male” attribute and we used landmarks from source actors to control the synthesized expressions (Figure 5). This 512× 512 model was trained from scratch. The example demonstrates the potential application of our method in face reenactment (Li et al., 2012; Garrido et al., 2014; Thies et al., 2016).
Computation Time Our model, once trained, is able to complete a face image with a single forward pass, resulting in much higher efficiency. We tested our model with a Titan Xp GPU by processing 3000 1024 × 1024 images with 512 × 512 holes. The mean completion time is 0.54 second per image. Unlike our model, existing CNN-based high-resolution in-painting approaches often need much longer time to process an image. For instance, it took about 1 min for the model of Yang et al. (Yang et al., 2016) to complete a 512× 512 image with a Titan X GPU. User Study We compared our method with CTX (Yu et al., 2018), which is the state-of-the-art CNN-based face completion approach capable of completing face images at 256× 256 resolution, with a pilot user study at 256 × 256 resolution with random masks. 27 subjects (15 male and 12 female participants, with ages from 22 to 32) were volunteered to participate.
There were four sessions of pairwise A/B tests. Each time, a user was shown two images and asked choose the more realistic one. In the first session, two images completed from the same image by different methods were chosen. In session two to four, a real image and a corresponding synthesized image were shown. In the first session, time was unlimited. In session two to four, images were on display for 250ms, 1000ms, 4000ms respectively. The result (Figure 6) shows that there were significantly more images generated by our method being favored by the viewers. Overall, our approach generated sharper images with more details and fewer distortions.
Limitations Though our method has low inference time, the training time is long due to the progressive growing of networks. In our experiment, it took about three weeks to train a 1024× 1024 model on a Titan Xp GPU. Additionally, by carefully zooming in our results, we find that our high-resolution model fails to learn low-level skin textures, such as furrows and sweat holes. Moreover, the model
could generate distorted content while removing large parts (e.g. hats) or synthesize some plausible but unnatural faces (Figure 7). Furthermore, For facial expression transfer, our method requires that the head poses of the source and target faces are similar. These issues are left for future work.

heading: 5 CONCLUSION

text: We propose a progressive GAN with frequency-oriented attentive modules (FAM) for high-resolution and fast face completion, which learns face structures from coarse to fine guided by the FAM. By consolidating information across all scales, our model not only outperforms state-of-the-art methods by generating sharper images in low resolution, but is also able to synthesize faces in higher resolutions than existing techniques. A conditional version of our model allows users to control the properties of generated images explicitly with attribute vectors and landmarks. Our system is designed in an end-to-end manner, in that it learns to generate completed faces directly and more efficiently.

heading: A APPENDIX

text:
A.1 ABLATION STUDY
The encoder-decoder structure has been widely used in image completion networks (Pathak et al., 2016; Iizuka et al., 2017; Li et al., 2017). However, the encoding process is a lossy compression, which makes it difficult to reconstruct the original contextual regions. Additionally, since much contextual information is lost during the encoding process, it is also difficult for the encoder to reconstruct content that perfectly match the context. UNet adds skip connections between the mirrored layers of the encoder and decoder, consolidating information from all previous layers, rather than depending on only the latent code. Therefore, UNet can be used to generate a completed image conditioned on the corrupted input. Unfortunately, if UNet is applied to image completion networks directly, it will be much easier for the generator to reconstruct the context than the content, resulting in inconsistent colors and textures along boundaries, which often causes the vanishing gradient problem
where both the generator and discriminator stop learning when the synthesized content is still blurry (Figure 8).
We try to solve this problem from two aspects. First, we adopt the method of training GANs progressively. Our model starts at a low resolution, so that it is difficult for the discriminator to capture the inconsistency between content and context regions. When the network grows, since the lower-resolution is already trained, the inconsistency between context and content regions is reduced. Second, we design the boundary loss and weighted reconstruction loss, which encourage the network focus more on synthesizing the boundary and content regions respectively. The feature loss also helps stabilizing the training by encouraging the synthesized images to have similar high-level features to real samples. These two improvements have improved the performance significantly.
The image quality is further enhanced by incorporating FAM. First, the reader and writer act as band-pass filters that minimize the influence of high-frequency noise on low-level network parameters, and thus avoiding distorting the already-learned global structures. Second, FAM is predicted from the facial semantics so that it encourages the model to focus on learning features in regions with richer details. For instance, the eyes synthesized by models trained with FAM are much sharper, more vivid and realistic.
This ablation study was run at 256× 256 to provide an intuitive illustration of the impact of different components of our method. Since the training of high-resolution models was very time consuming, a more thorough ablation study is left for future work.
A.2 HIGH-RESOLUTION COMPLETION RESULTS
More high resolution face completion results with various mask types are demonstrated in Figure 9 and Figure 10. Additionally, Figure 11 and Figure 12 represent two ways to control expressions
and appearances. In the first example (Figure 11), we use a two-dimensional attribute vector [“Smiling”, “Male”] without landmarks as inputs. In the second one, an attribute [“Male”] is used with landmarks extracted from source actors (Figure 12). The results show that both methods can control the expressions and appearances explicitly. But more subtle expressions can be controlled with landmarks. Moreover, we present more examples of attention filters during growing process in Figure 13.
A.3 TRAINING DETAILS
The progressive training process is illustrated in Figure 14. At a resolution lower than 1024×1024, the input face images, masks, landmarks and real images are all down-sampled with average pooling to fit the given scale. One of the major challenges of generating high resolution images is the limitation of Graphics Processing Unit (GPU) memory. Most completion networks use Batch Normalization (Ioffe & Szegedy, 2015) to avoid covariate shift. However, with the limited GPU memory, only a small number of batch sizes are supported at high resolution, resulting in low quality of generated images. We use the Instance Normalization (Ulyanov et al., 2016), similar to Zhu et al. (Zhu et al., 2017), and update D with a history of completed images instead of the latest generated one (Shrivastava et al., 2016) to stabilize training.
At the growing stage, new layers are added for both D and G and these layers are faded in with current networks smoothly. After the fade-in process, the network is trained on more images for stabilization. We used 300K, and 150K training images for resolution [8 × 8 to 256 × 256] and [512×512, 1024×1024] respectively at growing stage, and 600K, 430K images for 4×4 and [8×8 to 1024× 1024] at stabilizing stage respectively.
In the experiments, the reconstruction trade-off parameter was set to κ = 0.7 to focus more on the target region. To balance the effects of different objective functions, we used λattr = 2, λrec = 500, λfeat = 8, and λbdy = 5000. The Adam solver (Kingma & Ba, 2014) was employed with a learning rate of 0.0001.
A.4 NETWORK STRUCTURE
The generator G in our model is implemented by a U-shape network architecture consisting of the first component Genc transforming the observed image and its mask to a latent vector and the second componentGcompl transforming the concatenated vector (latent and attribute) to the completed image. There are residual connections between layers in Genc and the counterpart in Gcompl similar in the spirit to the U-Net (Ronneberger et al., 2015) and the Hourglass network (Newell et al., 2016) to consolidate information across multiple scales. Figure 15 illustrates the two structures of a layer in the generator for training without and with attributes respectively, which are adapted from the U-Net and Hourglass network.
Every convolutional layer (Conv) is followed by an Instance Normalization (InsNorm) and a LeakyReLU layer, except that the Conv before the latent vector (i.e. the second Conv layer in Table 2) is not followed by an InsNorm. Additionally, the there are no InsNorms or LeakyReLUs after the last Convs of both Dcls and Dattr. All Convs used in the residual block of the skip connections of our conditional model have a kernel size of three and a stride of one.
Since we use Instance Normalization rather than Batch Normalization, the batch size is not an important hyper-parameter. Technically, for faster computation, we use as large a batch size as possible so long as it does not exceed the GPU memory limit.
Tables 2 and 4 demonstrate the architecture of the components of the generator G while Tables 5 shows the components of the discriminator D. In Table 5, depending on the operation of the skip connection (Skip), the number of filters is either doubled (for a concatenation operation) or remains the same (for an addition operation).
r x r cubes in the figure represent convolutional layers that handle resolution r. For the conditional
version, attribute labels Aobs are concatenated to the latent vectors. The discriminator D splits into two branches in the final layers: Dcls that classifies if an input image is real, and Dattr that predicts attribute vectors. Note that XG and XD are both a set of inputs as defined in the paper. We use images in this Figure as a simplified illustration.

title: PROGRESSIVELY ATTENTIVE GANS


summaries: There has been a lot of work on limited precision training and inference for deep learning hardware, but in most of this work, the accumulators for the multiply-and-add (FMA) operations that occur for inner products are chosen conservatively or treated as having unlimited precision. The authors address this with  an analytical method to predict the number of mantissa bits needed for partial summations during the forward, delta and gradient computation ops for convolutional and fully connected layers. They propose an information theoretic approach to argue that by using fewer bits of mantissa in the accumulator than necessary, the variance of the resulting sum is less than what it would have been if sufficient bits of mantissa were used. This is surprising to me, as quantization is usually modeled as _adding_ noise, leading to an _increase_ in variance (Mc Kinstry et al. 2018), so this is a nice counterexample to that intuition. Unfortunately the result is presented in a way that implies the variance reduction is what causes the degradation in performance, while obviously (?) it's just a symptom of a deeper problem. E.g., adding noise or multiplying by a constant to get the variance to where it should be, will not help the network converge. The variance is just a proxy for lost information. The authors should make this more clear.

summaries: The authors conduct a thorough analysis of the numeric precision required for the accumulation operations in neural network training. The analysis is based on Variance Retention Ratio (VRR), and authors show the theoretical impact of reducing the number of bits in the floating point accumulator. And through extensive benchmarks with popular vision models, the authors demonstrate the practical performance of their theoretical analysis.

abstractText: Efforts to reduce the numerical precision of computations in deep learning training have yielded systems that aggressively quantize weights and activations, yet employ wide high-precision accumulators for partial sums in inner-product operations to preserve the quality of convergence. The absence of any framework to analyze the precision requirements of partial sum accumulations results in conservative design choices. This imposes an upper-bound on the reduction of complexity of multiply-accumulate units. We present a statistical approach to analyze the impact of reduced accumulation precision on deep learning training. Observing that a bad choice for accumulation precision results in loss of information that manifests itself as a reduction in variance in an ensemble of partial sums, we derive a set of equations that relate this variance to the length of accumulation and the minimum number of bits needed for accumulation. We apply our analysis to three benchmark networks: CIFAR-10 ResNet 32, ImageNet ResNet 18 and ImageNet AlexNet. In each case, with accumulation precision set in accordance with our proposed equations, the networks successfully converge to the single precision floating-point baseline. We also show that reducing accumulation precision further degrades the quality of the trained network, proving that our equations produce tight bounds. Overall this analysis enables precise tailoring of computation hardware to the application, yielding areaand power-optimal systems.

authors:
A.M. Castaldo
R.C. Whaley
A.T. Chronopoulos

title: Reducing floating point error in dot product using the superblock family of algorithms

venue: SIAM journal on scientific computing, 31(2):1156–1174.

authors:
Chen
C.-Y.
J. Choi
K. Gopalakrishnan
V. Srinivasan
S. Venkataramani

title: Exploiting approximate computing for deep learning acceleration

venue: Design, Automation, Test in Europe Conference Exhibition (DATE).

title: Shake-shake regularization

venue: arXiv preprint arXiv:1705.07485.

authors:
X. Glorot
Y. Bengio

title: Understanding the difficulty of training deep feedforward neural networks

venue: Proceedings of the thirteenth international conference on artificial intelligence and statistics, pages 249–256.

authors:
P. Goyal
P. Dollár
R. Girshick
P. Noordhuis
L. Wesolowski
A. Kyrola
A. Tulloch
Y. Jia
K. He

title: Accurate, large minibatch sgd: training imagenet in 1 hour

venue: arXiv preprint arXiv:1706.02677.

authors:
S. Gupta
A. Agrawal
K. Gopalakrishnan
P. Narayanan

title: Deep learning with limited numerical precision

venue: International Conference on Machine Learning, pages 1737–1746.

authors:
S. Han
H. Mao
W.J. Dally

title: Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding

venue: arXiv preprint arXiv:1510.00149.

authors:
S. Han
J. Pool
J. Tran
W. Dally

title: Learning both weights and connections for efficient neural network

venue: Advances in neural information processing systems, pages 1135–1143.

authors:
K. He
X. Zhang
S. Ren
J. Sun

title: Delving deep into rectifiers: Surpassing human-level performance on imagenet classification

venue: Proceedings of the IEEE international conference on computer vision, pages 1026–1034.

title: The accuracy of floating point summation

venue: SIAM Journal on Scientific Computing, 14(4):783–799.

authors:
I. Hubara
M. Courbariaux
D. Soudry
R. El-Yaniv
Y. Bengio

title: Binarized neural networks

venue: Advances in neural information processing systems, pages 4107–4115.

authors:
U. Köster
T. Webb
X. Wang
M. Nassar
A.K. Bansal
W. Constable
O. Elibol
S. Gray
S. Hall
L Hornof

title: Flexpoint: An adaptive numerical format for efficient training of deep neural networks

venue: In Advances in Neural Information Processing Systems,

authors:
D. Lin
S. Talathi
S. Annapureddy

title: Fixed point quantization of deep convolutional networks

venue: International Conference on Machine Learning, pages 2849–2858.

authors:
J.L. McKinstry
S.K. Esser
R. Appuswamy
D. Bablani
J.V. Arthur
I.B. Yildiz
D.S. Modha

title: Discovering low-precision networks close to full-precision networks for efficient embedded inference

venue: arXiv preprint arXiv:1809.04191.

authors:
T.G. Robertazzi
S.C. Schwartz

title: Best “ordering” for floating-point addition

venue: ACM Transactions on Mathematical Software (TOMS), 14(1):101–110.

authors:
C. Sakr
Y. Kim
N. Shanbhag

title: Analytical guarantees on numerical precision of deep neural networks

venue: International Conference on Machine Learning, pages 3007–3016.

authors:
N. Wang
J. Choi
D. Brand
Chen
C.-Y.
K. Gopalakrishnan

title: Training deep neural networks with 8-bit floating point numbers

venue: Advances in neural information processing systems.

authors:
B. Widrow
I. Kollár

title: Quantization noise

venue: Cambridge University Press, 2:5.

authors:
S. Wu
G. Li
F. Chen
L. Shi

title: Training and inference with integers in deep neural networks

venue: arXiv preprint arXiv:1802.04680.

authors:
S. Zhou
Y. Wu
Z. Ni
X. Zhou
H. Wen
Y. Zou

title: Dorefa-net: Training low bitwidth convolutional neural networks with low bitwidth gradients

venue: arXiv preprint arXiv:1606.06160.

authors:
C. Zhu
S. Han
H. Mao
W.J. Dally

title: Trained ternary quantization

heading: 1 INTRODUCTION

text:
Over the past decade, deep learning techniques have been remarkably successful in a wide spectrum of applications through the use of very large and deep models trained using massive datasets. This training process necessitates up to 100’s of ExaOps of computation and Gigabytes of storage. It is, however, well appreciated that a range of approximate computing techniques can be brought to bear to significantly reduce this computational complexity (Chen et al., 2018) - and amongst them, exploiting reduced numerical precision during the training process is extremely effective and has already been widely deployed (Gupta et al., 2015).
There are several reasons why reduced precision deep learning has attracted the attention of both hardware and algorithms researchers. First, it offers well defined and scalable hardware efficiency, as opposed to other complexity reduction techniques such as pruning (Han et al., 2015b;a), where handling sparse data is needed. Indeed, parameter complexity scales linearly while multiplication hardware complexity scales quadratically with precision bit-width (Zhou et al., 2016). Thus, any advance towards truly binarized networks (Hubara et al., 2016) corresponds to potentially 30x - 1000x complexity reduction in comparison to single precision floating-point hardware. Second, the mathematics of reduced precision has direct ties with the statistical theory of quantization (Widrow and Kollár, 2008). In the context of deep learning, this presents an opportunity for theoreticians to derive analytical trade-offs between model accuracy and numerical precision (Lin et al., 2016; Sakr et al., 2017).
∗Work done while at IBM Research.
Most ongoing efforts on reduced precision deep learning solely focus on quantizing representations and always assume wide accumulators, i.e., ideal summations. The reason being reduced precision accumulation can result in severe training instability and accuracy degradation, as illustrated in Figure 1 (a) for ResNet 18 (ImageNet) model training. This is especially unfortunate, since the hardware complexity in reduced precision floating-point numbers (needed to represent small gradients during training) (Wang et al., 2018; Micikevicius et al., 2017) is dominated by the accumulator bit-width. To illustrate this dominance we developed a model underpinned by the hardware synthesis of low-precision floating-point units (FPU), that translates precision into area complexity of the FPU. Comparisons obtained from this model are shown in Figure 1 (b). We observe that accumulating in high precision severely limits the hardware benefits of reduced precision computations. This presents a new angle to the problem of reduced precision deep learning training which concerns determining suitable accumulation precision and forms the basis of our paper. Our findings are that the accumulation precision requirements in deep learning training are nowhere near 32-b, and in fact could enable further complexity reduction of FPUs by a factor of 1.5 ∼ 2.2×.

heading: 1.1 RELATED WORKS

text:
Our work is concerned with establishing theoretical foundations for estimating the accumulation bit precision requirements in deep learning. While this topic has never been addressed in the past, there are prior works in both deep learning and high performance computing communities that align well with ours.
Most early works on reduced precision deep learning consider fixed-point arithmetic or a variation of it (Gupta et al., 2015). However, when considering quantization of signals involving the backpropagation algorithm, finding a suitable fixed-point configuration becomes challenging due to a weak handle on the scalar dynamic range of the back-propagated signals. Thus, hardware solutions have been sought, and, accordingly, other number formats were considered. Flexpoint (Köster et al., 2017) is a hybrid version between fixed-point and floating-point where scalars in a tensor are quantized to 16-b fixed-point but share 5-b of exponenent to adjust the dynamic range. Similarly, WAGE (Wu et al., 2018) augments Flexpoint with stochastic quantization and enables integer quantization. All of these schemes focused on representation precision, but mostly used 32-bit accumulation. Another option is to use reduced precision floating-point as was done in MPT (Micikevicius et al., 2017), which reduces the precision of most signals to 16-b floating-point, but observes accuracy degradation when reducing the accumulation precision from 32-b. Recently, Wang et al. (2018) quantize all representations to 8-b floating-point and experimentally find that the accumulation could be in 16-b with algorithmic contrivance, such as chunk-based accumulation, to enable convergence.
The issue of numerical errors in floating-point accumulation has been classically studied in the area of high performance computing. Robertazzi and Schwartz (1988) were among the first to statistically estimate the effects of floating-point accumulation. Assuming a stream of uniformly and exponentially distributed positive numbers, estimates for the mean square error of the floating-
point accumulation were derived via quantization noise analysis. Because such analyses are often intractable (due to the multiplicative nature of the noise), later works on numerical stability focus on worst case estimates of the accumulation error. Higham (1993) provide upper bounds on the error magnitude by counting and analyzing round-off errors. Following this style of worst case analysis, Castaldo et al. (2008) provide bounds on the accumulation error for different summing algorithms, notably using chunk-based summations. Different approaches to chunking are considered and their benefits are estimated. It is to be noted that these analyses are often loose as they are agnostic to the application space. To the best of our knowledge, a statistical analysis on the accumulation precision specifically tailored to deep learning training remains elusive.

heading: 1.2 CONTRIBUTIONS

text: Our contribution is both theoretical and practical. We introduce the variance retention ratio (VRR) of a reduced precision accumulation in the context of the three deep learning dot products. The VRR is used to assess the suitability, or lack thereof, of a precision configuration. Our main result is the derivation of an actual formula for the VRR that allows us to determine accumulation bit-width for precise tailoring of computation hardware. Experimentally, we verify the validity and tightness of our analysis across three benchmarking networks (CIFAR-10 ResNet 32, ImageNet ResNet 18 and ImageNet AlexNet).

heading: 2 BACKGROUND ON FLOATING-POINT ARITHMETIC

text:
The following basic floating-point definitions and notations are used in our work: Floating-point representation: A b-bit floating-point number a has a signed bit, e exponent bits, and m mantissa bits so that b = 1 + e + m. Its binary representation is (Bs, B ′ 1, . . . , B ′ e, B ′′ 1 , . . . , B ′′ m) ∈ {0, 1}b and its value is equal to: a = (−1)Bs × 2E × (1 + M)
where E = −(2e−1 − 1) + ∑e i=1B ′ i2 (e−i) and M = ∑m i=1B ′′ i 2 −i. Such number is called a (1, e,m) floating-point number. Floating-point operations: One of the most pervasive arithmetic functions used in deep learning is the dot product between two vectors which is the building block of the generalized matrix multiplication (GEMM). A dot product is computed in a multiply-accumulate (MAC) fashion and thus requires two floating-point operations: multiplication and addition. The realization of an ideal floating-point operation requires a certain bit growth at the output to avoid loss of information. For instance, in a typical MAC operation, if c ← c + a × b where a is (1, ea,ma) and b is (1, eb,mb), then c should be (1,max(ea, eb) + 2,ma + mb + 1 + ∆E), which depends on the bit-precision and the relative exponent difference of the operands ∆E . However, it is often more practical to pre-define the precision of c as (1, ec,mc), which requires rounding immediately after computation. Such rounding might cause an operand to be completely or partially truncated out of the addition, a phenomenon called ”swamping” (Higham, 1993), which is the primary source of accumulation errors.

heading: 3 ACCUMULATION VARIANCE

text:
The second order statistics (variance) of signals are known to be of great importance in deep learning. For instance, in prior works on weight initialization (Glorot and Bengio, 2010; He et al., 2015), it is customary to initialize random weights subject to a variance constraint designed so as to prevent vanishing or explosion of activations and gradients. Thus, such variance engineering induces fine convergence of DNNs. Importantly, in such analyses, the second order output statistics of a dot product are studied and expressed as a function of that of the accumulated terms, which are assumed to be independent and having similar variance. A fundamental assumption is: V ar(s) = nV ar(p), where V ar(s) and V ar(p) are the variances of the sum and individual product terms, respectively, and n is the length of the dot product. One intuition concerning accumulation with reduced precision is that, due to swamping, some product terms may vanish from the summation, resulting in a lower variance than expected: V ar(s) = ñV ar(p), where ñ < n. This constitutes a violation of a key assumption and effectively leads to the re-emergence of the difficulties in training neural networks with improper weight initialization which often harms the convergence behavior (Glorot and Bengio, 2010; He et al., 2015).
Input Feature Maps (IFM) Output Feature Maps (OFM)
IFM Width (IW) OFM Width (OW)
IF M
H ei
gh t
(IH )
O FM
H ei
gh t
(O H
)
Input Channel Number (ICN)
Output Channel Number (OCN)
Kernel Width (KW)
Ke rn
el H
ei gh t (K H)
Accumulation length = ICN x KW x KH
(a)
Input Feature Maps (IFM) Derivatives Output Feature Maps (OFM) Derivatives
IFM Width (IW) OFM Width (OW)
IF M
H ei
gh t
(IH )
O FM
H ei
gh t
(O H
)
Output Channel Number (OCN)
Kernel Width (KW) Kernel Height (KH)
Accumulation length = OCN x KW x KH
Input Channel Number (ICN)
(b)
Elementwise Product of Input Activations and Output Derivatives
Product Width (PW)
Pr od
uc t H
ei gh t (P H )
Accumulation length = BS x PW x PH
Weight Gradients (2D
Slice)
Batch Size (BS)
(c)
Figure 2: The three GEMM calls, and hence accumulations, in one iteration of the back-propagation algorithm: (a) the forward propagation (FWD), (b) the backward propagation (BWD), and (c) gradient computation (GRAD). The accumulation of these three GEMMs is across multiple dimensions (mini-batch size, feature maps, output channels etc.) and their lengths are usually very long.
To explain the poor convergence of our ResNet 18 run (Figure 1 (a)), we evaluate the behavior of accumulation variance across layers. Specifically, we check the three dot products of a backpropagation iteration: the forward propagation (FWD), the backward propagation (BWD), and the gradient computation (GRAD), as illustrated in Figure 2. Indeed, there is an abnormality in reduced precision GRAD as shown in Figure 3. It is also observed that the abnormality of variance is directly related to accumulation length. From Figure 3, the break point corresponds to the switch from the first to the second residual block. The GRAD accumulation length in the former is much longer (4×) than the latter. Thus, evidence points to the direction that for a given precision, there is an accumulation length for which the expected variance cannot be properly retained due to swamping. Motivated by these observations, we propose to study the trade-offs among accumulation variance, length, and mantissa precision.
Before proceeding, it is important to note that our upcoming analysis differs, in style, from many works on reduced precision deep learning where it is common to model quantization effects as additive noise causing increased variance (McKinstry et al., 2018). Our work does not contradict such findings, since prior arts have considered representation quantization whose effects are, by nature, different from intermediate roundings in partial sums.

heading: 4 MANTISSA PRECISION REQUIREMENTS ANALYSIS

text:
We assume sufficient exponent precision throughout and treat reduced precision floating-point arithmetic as an unbiased form of approximate computing, as is customary. Thus, our work focuses on associating second order statistics to mantissa precision.
We consider the accumulation of n terms {pi}ni=1 which correspond to the element-wise product terms in a dot product. The goal is to compute the correct nth partial sum sn where si = ∑i i′=1 pi′ .
We assume, as in (He et al., 2015), that the product terms {pi}ni=1 are statistically independent, zeromean, and have the same variance σ2p. Thus, under ideal computation, the variance of sn (which is equal to its second moment) should be V ar(sn)ideal = nσ2p. However, due to swamping effects, the variance of sn under reduced precision is V ar(sn)swamping 6= V ar(sn)ideal.
Let the product terms {pi}ni=1 and partial sum terms {si} n i=1 have mp and macc mantissa bits, respectively. Our key contribution is a formula for the variance retention ratio V RR = V ar(sn)swampingV ar(sn)ideal . The VRR, which is always less than or equal to unity, is a function of n, mp, and macc only, which needs no simulations to be computed. Furthermore, to preserve quality of computation under reduced precision, it is required that V RR → 1. As it turns out, the VRR for a fixed precision is a curve with ”knee” with respect to n, where a break point in accumulation length beyond which a certain mantissa precision is no longer suitable can be easily identified. Accordingly, for a given accumulation length, the mantissa precision requirements can be readily estimated.
Before proceeding, we formally define swamping. As illustrated in Figure 4, the bit-shift of pi due to exponent difference may cause partial (e.g., stage 1-4) or full truncation of pi’s bits, called swamping. We define (1) ”full swamping” which occurs when |si| > 2macc |pi+1|, and (2) ”partial swamping” which occurs when 2macc−mp |pi+1| < |si| ≤ 2macc |pi+1|. These two swamping types will be fully considered in our analysis.

heading: 4.1 VARIANCE RETENTION RATIO

text:
In the lemma below, we first present a formula for the VRR when only full swamping is considered. Lemma 1. The variance retention ratio of a length n accumulation using macc mantissa bits, and when only considering full swamping, is given by:
V RRfull swamping =
∑n−1 i=2 iqi + nq̃n
kn (1) where qi = 2Q (
2macc√ i
)( 1− 2Q ( 2macc√ i−1 )) , q̃n = 1 − 2Q ( 2macc√ n ) , k = ∑n−1 i=2 qi + q̃n is a
normalization constant, and Q denotes the elementary Q-function.
The proof is provided in Appendix A. A preliminary check is that a very large value of macc in (1) causes all {qi}n−1i=1 terms to vanish and q̃n to approach unity. This makes V RR → 1 for high precision as expected. On the other hand, if we assume macc to be small, but let n → ∞, we get nq̃n → 0 because the Q-function term will approach 1 exponentially fast as opposed to the n term which is linear. Furthermore, the terms inside the summation having a large iwill vanish by the same argument, while the n term in the denominator will make the ratio decrease and we would expect V RR → 0. This means that with limited precision, there is little hope to achieve a correct result when the accumulation length is very large. Also, the rapid change in VRR from 0 to 1 indicates that VRR can be used to provide sharp decision boundary for accumulation precision.
The above result only considers full swamping and is thus incomplete. Next we augment our analysis to take into account the effects of partial swamping. The corresponding formula for the VRR is provided in the following theorem. Theorem 1. The variance retention ratio of a length n accumulation using mp and macc mantissa bits for the input products and partial sum terms, respectively, is given by:
V RR =
∑n−1 i=2 (i− α)+qi1{i>α} + ∑mp jr=2
(n− αjr )+q′i1{n>αjr} + nk3 kn
(2)
where (x)+ = { x if x > 0 0 otherwise , 1A = { 1 if A is true 0 otherwise ,
α = 2 macc−3mp
3
∑mp j=1 2 j(2j − 1)(2j+1 − 1), qi = 2Q ( 2macc√ i )( 1− 2Q ( 2macc√ i−1 )) ,
αjr = 2macc−3mp
3
∑jr−1 j=1 2
j(2j − 1)(2j+1 − 1), q′jr = Njr−12Q ( 2macc−mp+jr−1√ n )( 1− 2Q ( 2macc−mp+jr√ n )) ,k = k1 + k2 + k3,
k1 = ∑n−1 i=2 qi1{i>α}, k2 = ∑mp jr=2 q′i1{n>αjr}, and k3 = 1− 2Q ( 2macc−mp+1√ n ) .
The proof is provided in Appendix B. Observe the dependence on macc, mp, and n. Therefore, in what follows, we shall refer to the VRR in (2) as V RR(macc,mp, n). Once again, we verify the extremal behavior of our formula. A very large value ofmacc in (2) causes k1 ≈ k2 ≈ 0 and k3 ≈ 1. This makes V RR→ 1 for high precision as expected. In addition, assuming small macc and letting n → ∞, we get nk3 → 0 because k3 decays exponentially fast due to the Q-function term. By the same argument, q′jr → 0 for all jr and qi → 0 for all but small values of i. Thus, the numerator will be small, while the denominator will increase linearly in n causing V RR → 0. Thus, once more, we establish that with limited accumulation precision, there is little hope for a correct result.

heading: 4.2 VRR WITH CHUNK BASED ACCUMULATIONS

text:
Next we consider an accumulation that uses chunking. In particular, assume n = n1×n2 so that the accumulation is broken into n2 chunks, each of length n1. Thus, n2 accumulations of length n1 are performed and the n2 intermediate results are added to obtain sn. This simple technique is known to greatly improve the stability of sums (Castaldo et al., 2008). The VRR can be used to theoretically explain such improvements. For simplicity, we assume two-level chunking (as described above) and same mantissa precision macc for both inter-chunk and intra-chunk accumulations. Applying the above analysis, we may obtain a formula for the VRR as provided in the corollary below, which is proved in Appendix C. Corollary 1. The variance retention ratio of an length n = n1 × n2 accumulation with chunking, where n1 is the chunk size and n2 is the number of chunks, using mp and macc mantissa bits for the input products and partial sum terms, respectively, is given by:
V RRchunking = V RR(macc,mp, n1)× V RR (macc,min (macc,mp + log2(n1)) , n2) (3)

heading: 4.3 VRR WITH SPARSITY

text:
It is common to encounter sparse operands in deep learning dot products. Since addition of zero is an identity operation, the effective accumulation length is often less than as described by the network topology. Indeed, for a given accumulation, supposedly of length n, if we can estimate the non-zero ratio (NZR) of its incoming product terms, then the effective accumulation length is NZR× n. Thus, when an accumulation is known to have sparse inputs with known NZR, a better estimate of the VRR is
V RRsparsity = V RR(macc,mp, NZR× n). (4)
Similarly, when considering the VRR with chunking, we may use knowledge of sparsity to obtain the effective intra-accumulation length as NZR × n1. This change is reflected both in the VRR of the intra-chunk accumulation and the input precision of the inter-chunk accumulation:
V RRchunking and sparsity = V RR(macc,mp, NZR× n1) × V RR (macc,min (macc,mp + log2(NZR× n1)) , n2) (5)
In practice, the NZR can be estimated by making several observations from baseline data. Using an estimate of the NZR makes our analysis less conservative.

heading: 4.4 USAGE OF ANALYSIS

text:
For a given accumulation setup, one may compute the VRR and observe how close it is from the ideal value of 1 in order to judge the suitability of the mantissa precision assignment. It turns out that when measured as a function of accumulation length n for a fixed precision, the VRR has a breakdown region. This breakdown region can very well be observed when considering what we define as the normalized exponential variance lost:
v(n) = en(1−V RR) (6)
In Figure 5 (a,b) we plot v(n) for different values of macc when considering both normal accumulation and chunk-based accumulation with a chunk-size of 64. The value of mp is set to 5-b, corresponding to the product of two numbers in (1,5,2) floating-point format (Wang et al., 2018). We consider macc to be suitable for a given n only if v(n) < 50. The reason being, in all plots, the
variance lost rapidly increases when v(n) > 50 and n increases. On the other hand, when v(n) < 50 and n decreases, the variance lost quickly drops to zero. This choice of a cut-off value is thus chosen purely based on the accumulation length and precision.
In addition, when performing chunk-based accumulation, the chunk size is a hyperparameter that, a priori, cannot be determined trivially. Castaldo et al. (2008) identified an optimal chunk size minimizing the loose upper bound on the accumulation error they derived. In practice, they did not find the accumulation error to be sensitive to the chunk-size. Neither did Wang et al. (2018) who performed numerical simulations. By sweeping the chunk size and observing the accumulation behavior on synthetic data, it was found that chunking significantly reduces accumulation error as long as the chunk size is not too small nor too large. Using our analysis, we provide a theoretical justification. Figure 5 (c) shows the VRR for various accumulation setups, including chunking when the chunk size is sweeped. For each case we see that chunking raises the VRR to a value close to unity. Furthermore, the VRR curve in that regime is ”flat”, meaning that a specific value of chunk size does not matter as long as it is not too small nor too large. One intuition is that a moderate chunk size prevents both inter- and intra-chunk accumulations to be as large as the original accumulation. In our upcoming chunking experiments we use a chunk size of 64 as was done by Wang et al. (2018).

heading: 5 NUMERICAL RESULTS

text:
Using the above analysis, we predict the mantissa precisions required by the three GEMM functions for training the following networks: ResNet 32 on the CIFAR-10 dataset, ResNet 18 and AlexNet on the ImageNet dataset. Those benchmarks were chosen due to both their popularity and topologies which present large accumulation lengths, making them good candidates against which we can verify our work. We use the same configurations as (Wang et al., 2018), in particular, we use 6-b of exponents in the accumulations, and quantize the intermediate tensors to (1,5,2) floating-point format and keep the final layer’s precision in 16 bit. The technique of loss scaling (Micikevicius et al., 2017) is used in order to limit underflows of activation gradients. A single scaling factor of 1000 was used for all models tested.
In order to realize rounding of partial sums, we modify the CUDA code of the GEMM function (which, in principle, can be done using any framework). In particular, we add a custom rounding function where the partial sum accumulation occurs. Quantization of dot product inputs is handled similarly.
The predicted precisions for each network and layer/block are listed in Table 1 for the case of normal and chunk-based accumulation with a chunk size of 64. Several insights are to be noted.
• The required accumulation precision for CIFAR-10 ResNet 32 is in general lower than that of the ImageNet networks. This is simply because, the network topology imposes shorter dot products. • Though, topologically, the convolutional layers in the two ImageNet networks are similar, the precision requirements do vary. Specifically, the GRAD accumulation depends on the feature map
dimension which is mostly dataset dependent, yet AlexNet requires less precision than ResNet 18. This is because the measured sparsity of the operands was found to be much higher for AlexNet. • Figure 5 suggests that chunking decreases the precision requirements significantly. This is indeed observed in Table 1, where we see that the benefits of chunking reach up to 6-b in certain accumulations, e.g., the GRAD acccumulation in the first ResBlock of ImageNet ResNet 18.
Because our predicted precision assignment ensures the VRR of all GEMM accumulations to be close to unity, we expect reduced precision training to converge with close fidelity to the baseline. Since our work focuses on accumulation precision, in our experiments, the baseline denotes accumulation in full precision. For a fair comparison, all upcoming results use (1,5,2) representation precision. Thus, the effects of reduced precision representation are not taken into account.
The goal of our experiments is to investigate both the validity and conservatism of our analysis. In Figure 6, we plot the convergence curves when training with our predicted accumulation precision for a normal accumulation. The runs corresponding to chunk-based accumulations were also performed but are omitted since the trend is similar. Furthermore, we repeat all experiments with precision perturbation (PP), meaning a specific reduction in precision with respect to our prediction. For instance, PP = 0 indicates our prediction while PP = −1 corresponds to a one bit reduction. Finally, in order to better visualize how the accumulation precision affect convergence, we plot in Figure 6 (d) the accuracy degradation as a function of precision perturbation for each of our three networks with both normal and chunk-based accumulations. The following is to be noted:
• When PP = 0, the converged accuracy always lies within 0.5% of the baseline, a strong indication of the validity of our analysis. We use a 0.5% accuracy cut-off with respect to the baseline as it corresponds to an approximate error bound for neural networks obtained by changing the random numbers seed (Goyal et al., 2017; Gastaldi, 2017). • When PP < 0, a noticeable accuracy degradation is observed, most notably for ImageNet ResNet 18. The converged accuracy is no longer within 0.5% of the baseline. Furthermore, a clear trend observed is that the higher the perturbation, the worse the degradation. • ImageNet AlexNet is more robust to perturbation than the two ResNets. While PP = −1 causes a degradation strictly > 0.5%, it is not much worse than the PP = 0 case. This observation aligns with that from neural net quantization that Alexnet is robust due to its over-parameterized network structure (Zhu et al., 2016). But the trend of increasing degradation remains the same. • Figure 6 (d) suggests that the effects of PP are more pronounced for a chunk-based accumulation. Since the precision assignment itself is lower (Table 1), a specific precision perturbation corresponds to a relatively higher change. For example, decreasing one bit from a 6-b assignment is more important than decreasing one bit from a 10-b assignment. Further justification can be obtained by comparing Figures 5 (a) and 5 (b) where consecutive lines are less closely aligned for the chunk-based accumulation, indicating more sensitivity to precision perturbation.
Thus, overall, our predictions are adequate and close to the limits beyond which training becomes unstable. These are very encouraging signs that our analysis is both valid and tight.

heading: 6 CONCLUSION

text: We have presented an analytical method to predict the precision required for partial sum accumulation in the three GEMM functions in deep learning training. Our results prove that our method is able to accurately pinpoint the minimum precision needed for the convergence of benchmark networks to the full-precision baseline. Our theoretical concepts are application agnostic, and an interesting extension would be to consider recurrent architectures such as LSTMs. In particular, training via backpropagation in time could make the GRAD accumulation very large depending on the number of past time-steps used. In such a case, our analysis is of great relevance to training precision optimization. On the practical side, this analysis is a useful tool for hardware designers implementing reduced-precision FPUs, who in the past have resorted to computationally prohibitive brute-force emulations. We believe this work addresses a critical missing link on the path to truly low-precision floating-point hardware for DNN training.

heading: ACKNOWLEDGMENT

text: This work is supported in part by IBM Research; IBM SoftLayer; IBM Cognitive Computing Cluster (CCC); IBM-ILLINOIS Center for Cognitive Computing Systems Research (C3SR) - a research collaboration as part of the IBM AI Horizons Network; and C-BRIC, one of six centers in JUMP, a Semiconductor Research Corporation (SRC) program sponsored by DARPA. The authors would like to thank I-Hsin Chung, Ming-Hung Chen and Silvia Melitta Mueller for helpful discussions and support.

heading: A PROOF OF LEMMA 1

text:
In order to compute the VRR, we first need to compute V ar(sn) during swamping, i.e., V ar(sn)swamping = Eswamping [ s2n ] , where the equality holds by application of Assumptions 1 and 2. To do so, we rely on the Law of Total Expectation. Indeed, assume that A is the set of events that describe all manners in which the accumulation sn experiencing swamping can occur, and let P (A) be the probability of event A ∈ A. Hence, by the Law of Total Expectation, we have that
V ar(sn)swamping = ∑ A∈A E [ s2n ∣∣∣∣A]P (A) (7) It is in fact a difficult task to enumerate and describe all events inA. Thus we consider a reduced set of events Â ⊂ A which is representative enough of the manners in which the accumulation occurs, yet tractable so that it can be used as a surrogate to A in (7). We shall form the set Â by application of Assumption 3, 4, and 5 as we proceed.
We consider a scenario where the first occurrence of full swamping is at iteration i of the summation for i = 2 . . . n− 1. This happens if:
|si| > 2macc |pi+1| & |si′ | < 2macc |pi′+1| for i′ = 1 . . . i− 1. (8)
Instead of looking at the actual absolute value of an incoming product term, we replace it by its typical value of σp. Furthermore, we simplify the condition of no swamping prior to iteration i by only considering the accumulated sum at the previous iteration. This is due to Assumption 3 which allows us toconsider a simplified scenario where the accumulation is monotonic in the iterations leading to full swamping. Hence, our simplified condition for the first occurrence of full swamping at iteration i is given by: |si−1| < 2maccσp < |si|. As iteration i corresponds to a full swamping event, we may invoke Assumption 4 and treat each of the two inequalities above independently. Finally, we invoke Assumption 5: since full swamping happens at itertion i, then the result of the accumulation is sn = si since the computation in the following iterations is halted.
Thus, the event set Â we construct for our analysis consists of the mutually exclusive events {Ai}n−1i=2 where Ai is the event that full swamping occurs for the first time at iteration i under the above assumptions. The condition for event i to happen is given by (8). By Central Limit Theorem, which we use by virtue of the si being a summation of independent, indentically distributed product terms, we have that si ∼ N (0, iσ2p), so that:
P (Ai) = 2Q
( 2macc√
i
)( 1− 2Q ( 2macc√ i− 1 )) = qi. (9)
Furthermore, by Assumption 5 we have:
E [ s2n ∣∣∣∣Ai] = E [s2i ] = iσ2p. (10) We also add to our space of events, the event An where no full swamping occurs over the course of the accumulation. This event happens if |sn| < 2maccσp and thus has probability P (An) = 1 −
2Q (
2macc√ n ) = q̃n. Since this event corresponds to the ideal scenario, we have E [ s2n ∣∣∣∣An] = nσ2p. Thus, under the above conditions we have:
V ar(sn)swamping = 1
k n∑ i=2 E [ s2n ∣∣∣∣Ai]P (Ai) = σ2pk ( n−1∑ i=2 iqi + nq̃n ) (11)
where k = ∑n−1 i=2 qi + q̃n is a normalization constant needed as Â does not describe the full probability space.
Consequently we obtain (1) as formula for the VRR completing the proof for Lemma 1.

heading: B PROOF OF THEOREM 1

text:
First, we do not change the description of the events {Ai}n−1i=2 above. Notably, by Assumption 5, once full swamping occurs, i.e., |si| > 2maccσp, the computation is stuck and stops. The probability of this event is P (Ai) as above. However, to account for partial swamping, we alter the result of
E [ s2n ∣∣∣∣Ai]. Indeed, partial swamping causes additional loss of variance. When the input product terms have mp bits of mantissa, then before event Ai can occur, the computation should go through each of the mp stages described in Figure 4. We again use Assumption 3 and consider a typical scenario for each of the mp stages of partial swamping preceding a full swamping event whereby the accumulation is monotonic and the magnitude of the incoming product term is close to its typical value σp. Under this assumption, stage j is expected to happen for the following number of iterations:
Nj = 2 macc+1−(mp−j) = 2macc−mp+j+1 (12)
for j = 1 . . .mp. At stage j, j least significant bits in the representation of the incoming product term are truncated (swamped). The variance lost because of this truncation, which we call fractional variance loss E[f2j ], can be computed by assuming the truncated bits are equally likely to be 0 or 1 (Assumption 6), so that:
E[f2j ] = σ 2 p 2j−1∑ k=0 1 2j ( 2−mpk )2 = σ2p2 −2mp (2 j − 1)(2j+1 − 1)
6 (13)
Hence, the total fractional variance lost before the occurrence of even Ai is NjE[f2j ]. Thus, we update the value of variance conditioned on Ai as follows:
E [ s2n ∣∣∣∣Ai] = (iσ2p −NjE[f2j ])+ = σ2p i− 2macc−3mp 3 mp∑ j=1 2j(2j − 1)(2j+1 − 1)  +
(14)
where we used the operator (x)+ = { x if x > 0 0 otherwise
in order to guarantee that the variance is
positive. Effectively, we neglect the events Ai where i is so small that the variance retained is less than the variance lost due to partial swamping. In other words, an event whereby full swamping occurs very early in the accumulation is considered to have zero probability and we replace P (Ai) in (9) by:
P (Ai) = qi1{i>α} (15) where qi = 2Q (
2macc√ i
)( 1− 2Q ( 2macc√ i−1 )) as in (9), 1 is the indicator function, and α =
2macc−3mp
3
∑mp j=1 2
j(2j − 1)(2j+1 − 1) as in (14). In addition, some boundary conditions need to be accounted for. These include the cases when no full swamping happens before the accumulation is complete but partial swamping does happen. We again consider a typical scenario as above and append our event setA with mp− 1 boundary events{ A′jr }mp jr=2
, where the event A′jr corresponds to the case where the computation has gone through stage jr − 1 of partial swamping but has not reached stage jr yet. The condition for this event is σp2
macc−mp+jr−1 < |sn| < σp2macc−mp+jr and occurs typically for up to Njr−1 iterations. The total fractional variance lost is:
σ2p jr−1∑ j=1 Nj 2j−1∑ k=0 1 2j ( 2−mpk )2 = σ2p 2macc−3mp3 jr−1∑ j=1 2j(2j − 1)(2j+1 − 1) (16)
Hence,
E [ s2n ∣∣∣∣A′jr] = σ2p (n− αjr )+ (17) where αjr = 2macc−3mp
3
∑jr−1 j=1 2 j(2j −1)(2j+1−1). And the probability of event A′jr is given by:
P (A′jr ) = q ′ jr1{n>αjr} (18) where q′jr = Njr−12Q ( 2macc−mp+jr−1√ n )( 1− 2Q ( 2macc−mp+jr√ n )) , the multiplication by Njr−1 reflects the number of iterations the event may occur for.
Finally, the event An is updated and corresponds to the case where neither partial nor full swamping occurs. The condition for this event is |sn| < 2macc−mp+1 and has a probability P (An) = 1 − 2Q (
2macc−mp+1√ n
) .
Putting things together, we use the law of total expectation as in (7) to compute:
V ar(sn)swamping =
σ2p k n−1∑ i=2 (i− α)+qi1{i>α} + mp∑ jr=2 (n− αjr )+q′i1{n>αjr} + nk3  (19) where k = k1 + k2 + k3, k1 = ∑n−1 i=2 P (Ai), k2 = ∑mp jr=2
P (A′jr ), and k3 = P (An). Hence, the formula for the VRR in (2) in the theorem follows and this concludes the proof.

heading: C PROOF OF COROLLARY 1

text:
Applying the above analysis, we may compute the variance of the intermediate results as σ2pn1V RR(macc,mp, n1). To compute the variance of the final result, first note that the mantissa precision of the incoming terms to the inter-chunk accumulation (the results from the intra-chunk accumulation) is min (macc,mp + log2(n1)). The reason being that since the intra-chunk accumulation uses macc mantissa bits, the mantissa cannot grow beyond macc due to the rounding nature of the floating-point accumulation. However, if macc is large enough and n1 is small enough, it is most likely that the mantissa has not grown to the maximum. Assuming accumulation of terms having statistically similar absolute value as was done for the VRR analysis, then the bit growth of the mantissa is logarithmic in n1 and starts at mp.
Hence, the variance of the computed result sn when chunking is used is:
V ar(sn)chunking = σ 2 pn1V RR(macc,mp, n1)
× n2V RR (macc,min (macc,mp + log2(n1)) , n2) (20)
and hence the VRR with chunking can be computed using (3) in Corollary 1. This completes the proof.

title: ACCUMULATION BIT-WIDTH SCALING FOR ULTRA- LOW PRECISION TRAINING OF DEEP NETWORKS