summaries: This paper proposes a model-agnostic explanations model, local explanation of response generation (LERG), for dialogue response generation task. Due to the sequence-to-sequence natrual, previous works, which normal produces a single label as output, are no longer suitable for this task. This paper regards the explanations as the mutual interaction of segments in input and output sentences. Specifically, it views the sequence prediction as uncertainty estimation of a human response and creates explanations by perturbing the input and calculating the certainty change over the human response. The experiment shows that the proposed approach extract both explicit and implicit relations between input and output segments.

summaries: This paper studies the model-agnostic explanations of dialogue response generation and proposes a new called local explanation of response generation (LERG). LERG extracts the sorted importance scores of every input-output segment pair from a dialogue response generation model. It views the sequence prediction as uncertainty estimation of a human response and creates explanations by perturbing the input and calculating the certainty change over the human response. The authors show the proposed LERG adhere to three properties of  an ideal explanation of text generation: (1) unbiased approximation, (2) intra-response consistency and (3) causal cause identification. The experiments on a popular benchmark DailyDialog empirically verify the effectiveness of the proposed approach.

summaries: This work proposes a method to locally explain the dialog response generation process. This method is motivated by the intuition that, such method should answer the question "which parts of the response are influenced the most by parts of the prompt". So the importance scores of every input-output segment pairs are calculated. They also proposed two metrics to evaluate explanations: "necessity" and "sufficiency". The former is defined as the perplexity change after removing top "salient" input features, and the latter is defined based on the intuition a complete explanation should recover model's prediction without the original input.

summaries: The authors propose a method for “explaining” dialogue responses from sequence generation models; that is, determining what parts of the input influence or “explain” certain elements of the output. The method, LERG, is “learned” in one of two ways to assign a score for each input/output token pair indicating the measure of relevance, and ultimately to link the intent between the two. The authors propose that their method must satisfy three properties: unbiased approximation (LERG should explain benefits of picking response given the context); consistency (LERG should explain each generation step); and cause identification (LERG should sort input features by importance). The authors measure the effectiveness of the proposed method in both automatic evaluations and user studies. The automatic evaluations measure the **necessity** and **sufficiency** of the explained segments of the input text by capturing the model perplexity difference when stripping the segments and only including the segments, respectively, essentially measuring how accurate the method’s explanations are at capturing the relevant segments of the input context. Human evaluations display the segments to humans and ask if they can predict the gold response. Both evaluations show their explanation method significantly outperform both random baselines and other methods from the literature.

summaries: The paper addresses the local explanation of sequence generation models, specifically under the dialogue response generation setting, and proposes local explanation of response generation (LERG) that computes the mutual interactions between input and output sequences under perturbations as the explanations. Automatic and human evaluations show that LERG is more effective than other baselines.  Contributions:  1. A new local explanation method for dialogue response generation 2. Such an explanation method could be generalized to other generation models as well 3.  A systematic framework to evaluate the dialogue model explanation quality involving both automatic evaluations and human studies.

abstractText: In comparison to the interpretation of classification models, the explanation of sequence generation models is also an important problem, however it has seen little attention. In this work, we study model-agnostic explanations of a representative text generation task – dialogue response generation. Dialog response generation is challenging with its open-ended sentences and multiple acceptable responses. To gain insights into the reasoning process of a generation model, we propose a new method, local explanation of response generation (LERG), that regards the explanations as the mutual interaction of segments in input and output sentences. LERG views the sequence prediction as uncertainty estimation of a human response and then creates explanations by perturbing the input and calculating the certainty change over the human response. We show that LERG adheres to desired properties of explanation for text generation, including unbiased approximation, consistency, and cause identification. Empirically, our results show that our method consistently improves other widely used methods on proposed automaticand humanevaluation metrics for this new task by 4.4-12.8%. Our analysis demonstrates that LERG can extract both explicit and implicit relations between input and output segments. 1

authors:
David Alvarez-Melis
Tommi Jaakkola

title: A causal framework for explaining the predictions of black-box sequence-to-sequence models

venue: In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing,

authors:
David Alvarez-Melis
Tommi S Jaakkola

title: Towards robust interpretability with self-explaining neural networks

venue: In NeurIPS,

authors:
Nabiha Asghar
Pascal Poupart
Xin Jiang
Hang Li

title: Deep active learning for dialogue generation

venue: In Proceedings of the 6th Joint Conference on Lexical and Computational Semantics (* SEM 2017),

authors:
Pepa Atanasova
Jakob Grue Simonsen
Christina Lioma
Isabelle Augenstein

title: A diagnostic study of explainability techniques for text classification

venue: In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP),

authors:
Mohammad Taha Bahadori
David Heckerman

title: Debiasing concept-based explanations with causal analysis

venue: In International Conference on Learning Representations,

authors:
Mihalj Bakator
Dragica Radosav

title: Deep learning and medical diagnosis: A review of literature

venue: Multimodal Technologies and Interaction,

authors:
Michael Buhrmester
Tracy Kwang
Samuel D Gosling

title: Amazon’s mechanical turk: A new source of inexpensive, yet high-quality data? 2016

authors:
Hanjie Chen
Yangfeng Ji

title: Learning variational word masks to improve the interpretability of neural text classifiers

authors:
Hanjie Chen
Guangtao Zheng
Yangfeng Ji

title: Generating hierarchical explanations on text classification via feature interaction detection

venue: In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics,

authors:
Hanjie Chen
Song Feng
Jatin Ganhotra
Hui Wan
Chulaka Gunasekara
Sachindra Joshi
Yangfeng Ji

title: Explaining neural network predictions on sentence pairs via learning word-group masks

authors:
Angela Fan
Mike Lewis
Yann Dauphin

title: Hierarchical neural story generation

venue: In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers),

authors:
Christopher Frye
Colin Rowat
Ilya Feige

title: Asymmetric shapley values: incorporating causal knowledge into model-agnostic explainability

venue: Advances in Neural Information Processing Systems,

authors:
Christopher Frye
Damien de Mijolla
Tom Begley
Laurence Cowton
Megan Stanley
Ilya Feige

title: Shapley explainability on the data manifold

authors:
Leilani H Gilpin
David Bau
Ben Z Yuan
Ayesha Bajwa
Michael Specter
Lalana Kagal

title: Explaining explanations: An overview of interpretability of machine learning

venue: IEEE 5th International Conference on data science and advanced analytics (DSAA),

authors:
Prakhar Gupta
Jeffrey P Bigham
Yulia Tsvetkov
Amy Pavel

title: Controlling dialogue generation with semantic exemplars

venue: In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies,

authors:
Tom Heskes
Evi Sijben
Ioan Gabriel Bucur
Tom Claassen

title: Causal shapley values: Exploiting causal knowledge to explain individual predictions of complex models

authors:
Jeya Vikranth Jeyakumar
Joseph Noor
Yu-Hsi Cheng
Luis Garcia
Mani Srivastava

title: How can i explain this to you? an empirical study of deep neural network explanation methods

authors:
Rishabh Joshi
Vidhisha Balachandran
Shikhar Vashishth
Alan Black
Yulia Tsvetkov

title: Dialograph: Incorporating interpretable strategygraph networks into negotiation dialogues

title: Machine learning for medical diagnosis: history, state of the art and perspective

venue: Artificial Intelligence in medicine,

authors:
Solomon Kullback
Richard A Leibler

title: On information and sufficiency

venue: The annals of mathematical statistics,

authors:
I Elizabeth Kumar
Suresh Venkatasubramanian
Carlos Scheidegger
Sorelle Friedler

title: Problems with shapley-value-based explanations as feature importance measures

venue: In International Conference on Machine Learning,

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

authors:
Jiwei Li
Will Monroe
Alan Ritter
Dan Jurafsky
Michel Galley
Jianfeng Gao

title: Deep reinforcement learning for dialogue generation

venue: In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing,

authors:
Yanran Li
Hui Su
Xiaoyu Shen
Wenjie Li
Ziqiang Cao
Shuzi Niu

title: DailyDialog: A manually labelled multi-turn dialogue dataset

venue: In Proceedings of the Eighth International Joint Conference on Natural Language Processing (Volume 1: Long Papers),

authors:
Zhaojiang Lin
Andrea Madotto
Yejin Bang
Pascale Fung

title: The adapter-bot: All-in-one controllable conversational model

venue: In Proceedings of the AAAI Conference on Artificial Intelligence,

authors:
Scott M Lundberg
Su-In Lee

title: A unified approach to interpreting model predictions

venue: In Advances in neural information processing systems,

authors:
Seungwhan Moon
Pararth Shah
Anuj Kumar
Rajen Subba

title: Opendialkg: Explainable conversational reasoning with attention-based walks over knowledge graphs

venue: In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics,

authors:
W James Murdoch
Peter J Liu
Bin Yu

title: Beyond word importance: Contextual decomposition to extract interactions from lstms

authors:
Shashi Narayan
Shay B Cohen
Mirella Lapata

title: Don’t give me the details, just the summary! topicaware convolutional neural networks for extreme summarization

venue: In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing,

authors:
Daniel Povey
Arnab Ghoshal
Gilles Boulianne
Lukas Burget
Ondrej Glembek
Nagendra Goel
Mirko Hannemann
Petr Motlicek
Yanmin Qian
Petr Schwarz

title: The kaldi speech recognition toolkit. In IEEE 2011 workshop on automatic speech recognition and understanding, number CONF

venue: IEEE Signal Processing Society,

authors:
Danish Pruthi
Bhuwan Dhingra
Livio Baldini Soares
Michael Collins
Zachary C Lipton
Graham Neubig
William W Cohen

title: Evaluating explanations: How much do explanations from the teacher aid students

authors:
Alec Radford
Karthik Narasimhan
Tim Salimans
Ilya Sutskever

title: Improving language understanding by generative pre-training

authors:
Marc’Aurelio Ranzato
Sumit Chopra
Michael Auli
Wojciech Zaremba

title: Sequence level training with recurrent neural networks

authors:
Marco Tulio Ribeiro
Sameer Singh
Carlos Guestrin

title: why should i trust you?" explaining the predictions of any classifier

venue: In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining,

title: Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead

venue: Nature Machine Intelligence,

authors:
Abigail See
Stephen Roller
Douwe Kiela
Jason Weston

title: What makes a good conversation? how controllable attributes affect human judgments

authors:
Avanti Shrikumar
Peyton Greenside
Anshul Kundaje

title: Learning important features through propagating activation differences

authors:
Eric Michael Smith
Diana Gonzalez-Rico
Emily Dinan
Y-Lan Boureau

title: Controlling style in generated dialogue

venue: arXiv preprint arXiv:2009.10855,

authors:
Erik Strumbelj
Igor Kononenko

title: An efficient explanation of individual classifications using game theory

venue: The Journal of Machine Learning Research,

authors:
Erik Štrumbelj
Igor Kononenko

title: Explaining prediction models and individual predictions with feature contributions

venue: Knowledge and information systems,

authors:
Mukund Sundararajan
Ankur Taly
Qiqi Yan

title: Axiomatic attribution for deep networks

authors:
Yi-Lin Tuan
Yun-Nung Chen
Hung-yi Lee

title: Dykgchat: Benchmarking dialogue generation grounding on dynamic knowledge graphs

venue: In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP- IJCNLP),

authors:
Oriol Vinyals
Quoc Le

title: A neural conversational model

venue: arXiv preprint arXiv:1506.05869,

authors:
Sarah Wiegreffe
Yuval Pinter

title: Attention is not not explanation

venue: In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP),

authors:
Thomas Wolf
Victor Sanh
Julien Chaumond
Clement Delangue

title: Transfertransfo: A transfer learning approach for neural network based conversational agents

venue: NeurIPS 2018 CAI Workshop,

authors:
Zeqiu Wu
Michel Galley
Chris Brockett
Yizhe Zhang
Xiang Gao
Chris Quirk
Rik Koncel-Kedziorski
Jianfeng Gao
Hannaneh Hajishirzi
Mari Ostendorf

title: A controllable model of grounded response generation

authors:
Can Xu
Wei Wu
Yu Wu

title: Towards explainable and controllable open domain dialogue generation with dialogue acts

venue: arXiv preprint arXiv:1807.07255,

authors:
Can Xu
Wei Wu
Chongyang Tao
Huang Hu
Matt Schuerman
Ying Wang

title: Neural response generation with meta-words

authors:
Haiqin Yang
Xiaoyuan Yao
Yiqun Duan
Jianping Shen
Jie Zhong
Kun Zhang

title: Progressive open-domain response generation with multiple controllable attributes

title: Monotonic solutions of cooperative games

venue: International Journal of Game Theory,

authors:
Ruqing Zhang
Jiafeng Guo
Yixing Fan
Yanyan Lan
Jun Xu
Xueqi Cheng

title: Learning to control the specificity in neural response generation

authors:
Saizheng Zhang
Emily Dinan
Jack Urbanek
Arthur Szlam
Douwe Kiela
Jason Weston

title: Personalizing dialogue agents: I have a dog, do you have pets too

authors:
Yizhe Zhang
Siqi Sun
Michel Galley
Yen-Chun Chen
Chris Brockett
Xiang Gao
Jianfeng Gao
Jingjing Liu
William B Dolan

title: Dialogpt: Large-scale generative pre-training for conversational response generation

venue: In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics: System Demonstrations,

heading: 1 Introduction

text:
As we use machine learning models in daily tasks, such as medical diagnostics [6, 19], speech assistants [31] etc., being able to trust the predictions being made has become increasingly important. To understand the underlying reasoning process of complex machine learning models a sub-field of explainable artificial intelligence (XAI) [2, 17, 36] called local explanations, has seen promising results [35]. Local explanation methods [27, 39] often approximate an underlying black box model by fitting an interpretable proxy, such as a linear model or tree, around the neighborhood of individual predictions. These methods have the advantage of being model-agnostic and locally interpretable.
Traditionally, off-the-shelf local explanation frameworks, such as the Shapley value in game theory [38] and the learning-based Local Interpretable Model-agnostic Explanation (LIME) [35] have been shown to work well on classification tasks with a small number of classes. In particular, there has been work on image classification [35], sentiment analysis [8], and evidence selection for question answering [32]. However, to the best of our knowledge, there has been less work studying explanations over models with sequential output and large class sizes at each time step. An attempt by [1] aims at explaining machine translation by aligning the sentences in source and target languages. Nonetheless, unlike translation, where it is possible to find almost all word alignments of the input and output sentences, many text generation tasks are not alignment-based. We further explore explanations over sequences that contain implicit and indirect relations between the input and output utterances.
1Our code is available at https://github.com/Pascalson/LERG.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
In this paper, we study explanations over a set of representative conditional text generation models – dialogue response generation models [45, 55]. These models typically aim to produce an engaging and informative [3, 24] response to an input message. The open-ended sentences and multiple acceptable responses in dialogues pose two major challenges: (1) an exponentially large output space and (2) the implicit relations between the input and output texts. For example, the open-ended prompt “How are you today?” could lead to multiple responses depending on the users’ emotion, situation, social skills, expressions, etc. A simple answer such as “Good. Thank you for asking.” does not have an explicit alignment to words in the input prompt. Even though this alignment does not exist, it is clear that “good” is the key response to “how are you”. To find such crucial corresponding parts in a dialogue, we propose to extract explanations that can answer the question: “Which parts of the response are influenced the most by parts of the prompt?”
To obtain such explanations, we introduce LERG, a novel yet simple method that extracts the sorted importance scores of every input-output segment pair from a dialogue response generation model. We view this sequence prediction as the uncertainty estimation of one human response and find a linear proxy that simulates the certainty caused from one input segment to an output segment. We further derive two optimization variations of LERG. One is learning-based [35] and another is the derived optimal similar to Shapley value [38]. To theoretically verify LERG, we propose that an ideal explanation of text generation should adhere to three properties: unbiased approximation, intra-response consistency, and causal cause identification. To the best of our knowledge, our work is the first to explore explanation over dialog response generation while maintaining all three properties.
To verify if the explanations are both faithful (the explanation is fully dependent on the model being explained) [2] and interpretable (the explanation is understandable by humans) [14], we conduct comprehensive automatic evaluations and user study. We evaluate the necessity and sufficiency of the extracted explanation to the generation model by evaluating the perplexity change of removing salient input segments (necessity) and evaluating the perplexity of only salient segments remaining (sufficiency). In our user study, we present annotators with only the most salient parts in an input and ask them to select the most appropriate response from a set of candidates. Empirically, our proposed method consistently outperforms baselines on both automatic metrics and human evaluation.
Our key contributions are:
• We propose a novel local explanation method for dialogue response generation (LERG).
• We propose a unified formulation that generalizes local explanation methods towards sequence generation and show that our method adheres to the desired properties for explaining conditional text generation.
• We build a systematic framework to evaluate explanations of response generation including automatic metrics and user study.

heading: 2 Local Explanation

text:
Local explanation methods aim to explain predictions of an arbitrary model by interpreting the neighborhood of individual predictions [35]. It can be viewed as training a proxy that adds the contributions of input features to a model’s predictions [27]. More formally, given an example with input features x = {xi}Mi=1, the corresponding prediction y with probability f(x) = Pθ(Y = y|x) (the classifier is parameterized by θ), we denote the contribution from each input feature xi as φi ∈ R and denote the concatenation of all contributions as φ = [φ1, ...,φM ]T ∈ RM . Two popular local explanation methods are the learning-based Local Interpretable Model-agnostic Explanations (LIME) [35] and the game theory-based Shapley value [38].
LIME interprets a complex classifier f based on locally approximating a linear classifier around a given prediction f(x). The optimization of the explanation model that LIME uses adheres to:
ξ(x) = argmin ϕ [L(f,ϕ,πx) + Ω(ϕ)] , (1)
where we sample a perturbed input x̃ from πx(x̃) = exp(−D(x, x̃)2/σ2) taking D(x, x̃) as a distance function and σ as the width. Ω is the model complexity of the proxy ϕ. The objective of ξ(x) is to find the simplest ϕ that can approximate the behavior of f around x. When using a linear classifier
dialog input text outputG
intent
(a) Controllable dialogue models
input text positive
negative
(b) Explanation of classifier
dialog input text outputG
intent
(c) Our concept
Figure 1: The motivation of local explanation for dialogue response generation. (c) = (a)+(b).
φ as the ϕ to minimize Ω(ϕ) [35], we can formulate the objective function as:
φ = argmin φ
Ex̃∼πx(Pθ(Y = y|x̃)−φT z)2 , (2)
where z ∈ {0, 1}M is a simplified feature vector of x̃ by a mapping function h such that z = h(x, x̃) = {�(xi ∈ x̃)}Mi=1. The optimization means to minimize the classification error in the neighborhood of x sampled from πx. Therefore, using LIME, we can find an interpretable linear model that approximates any complex classifier’s behavior around an example x.
Shapley value takes the input features x = {xi}Mi=1 as M independent players who cooperate to achieve a benefit in a game [38]. The Shapley value computes how much each player xi contributes to the total received benefit:
ϕi(x) = �
x̃⊆x\{xi}
|x̃|!(|x|− |x̃|− 1)! |x|! [Pθ(Y = y|x̃ ∪ {xi})− Pθ(Y = y|x̃)] . (3)
To reduce the computational cost, instead of computing all combinations, we can find surrogates φi proportional to ϕi and rewrite the above equation as an expectation over x sampled from P (x̃):
φi = |x|
|x|− 1ϕi = Ex̃∼P (x̃)[Pθ(Y = y|x̃ ∪ {xi})− Pθ(Y = y|x̃)], ∀i , (4)
where P (x̃) = 1 (|x|−1)(|x|−1|x̃| ) is the perturb function.2 We can also transform the above formulation into argmin:
φi = argmin φi
Ex̃∼P (x̃)([Pθ(Y = y|x̃ ∪ {xi})− Pθ(Y = y|x̃)]− φi)2 . (5)

heading: 3 Local Explanation for Dialogue Response Generation

text:
We aim to explain a model’s response prediction to a dialogue history one at a time and call it the local explanation of dialogue response generation. We focus on the local explanation for a more fine-grained understanding of the model’s behavior.
3.1 Task Definition
As depicted in Figure 1, we draw inspiration from the notions of controllable dialogue generation models (Figure 1a) and local explanation in sentiment analysis (Figure 1b). The first one uses a concept in predefined classes as the relation between input text and the response; the latter finds the features that correspond to positive or negative sentiment. We propose to find parts within the input and output texts that are related by an underlying intent (Figure 1c).
We first define the notations for dialogue response generation, which aims to predict a response y = y1y2...yN given an input message x = x1x2...xM . xi is the i-th token in sentence x with length M and yj is the j-th token in sentence y with length N . To solve this task, a typical sequence-to-sequence model f parameterized by θ produces a sequence of probability masses <Pθ(y1|x), Pθ(y2|x, y1), ..., Pθ(yN |x, y<N )> [45]. The probability of y given x can then be computed as the product of the sequence Pθ(y|x) = Pθ(y1|x)Pθ(y2|x, y1)...Pθ(yN |x, y<N ).
2� x̃⊆x\{xi} P (x̃) = 1 (|x|−1) � x̃⊆x\{xi} 1/ �|x|−1 |x̃| � = 1 (|x|−1) � |x̃| �|x|−1 |x̃| � / �|x|−1 |x̃| � = (|x|−1)
(|x|−1) = 1. This affirms that the P (x̃) is a valid probability mass function.
To explain the prediction, we then define a new explanation model Φ ∈ RM×N where each column Φj ∈ RM linearly approximates single sequential prediction at the j-th time step in text generation. To learn the optimal Φ, we sample perturbed inputs x̃ from a distribution centered on the original inputs x through a probability density function x̃ = π(x). Finally, we optimize Φ by ensuring u(ΦTj z) ≈ g(x̃) whenever z is a simplified embedding of x̃ by a mapping function z = h(x, x̃), where we define g as the gain function of the target generative model f , u as a transform function of Φ and z and L as the loss function. Note that z can be a vector or a matrix and g(·), u(·) can return a scalar or a vector depending on the used method. Therefore, we unify the local explanations (LIME and Shapley value) under dialogue response generation as:
Definition 1: A Unified Formulation of Local Explanation for Dialogue Response Generation
Φj = argmin Φj
L(g(yj |x̃, y<j), u(ΦTj h(x̃))), for j = 1, 2, ..., N . (6)
The proofs of unification into Equation 6 can be found in Appendix A. However, direct adaptation of LIME and Shapley value to dialogue response generation fails to consider the complexity of text generation and the diversity of generated examples. We develop disciplines to alleviate these problems.

heading: 3.2 Proposed Method

text:
Our proposed method is designed to (1) address the exponential output space and diverse responses built within the dialogue response generation task and (2) compare the importance of segments within both input and output text.
First, considering the exponential output space and diverse responses, recent work often generates responses using sampling, such as the dominant beam search with top-k sampling [11]. The generated response is therefore only a sample from the estimated probability mass distribution over the output space. Further, the samples drawn from the distribution will inherently have built-in errors that accumulate along generation steps [34]. To avoid these errors we instead explain the estimated probability of the ground truth human responses. In this way, we are considering that the dialogue response generation model is estimating the certainty to predict the human response by Pθ(y|x). Meanwhile, given the nature of the collected dialogue dataset, we observe only one response per sentence, and thus the mapping is deterministic. We denote the data distribution by P and the probability of observing a response y given input x in the dataset by P (y|x). Since the mapping of x and y is deterministic in the dataset, we assume P (y|x) = 1. Second, if we directly apply prior explanation methods of classifiers on sequential generative models, it turns into a One-vs-Rest classification situation for every generation step. This can cause an unfair comparison among generation steps. For example, the impact from a perturbed input on yj could end up being the largest just because the absolute certainty Pθ(yj |x, y<j) was large. However, the impact from a perturbed input on each part in the output should be how much the certainty has changed after perturbation and how much the change is compared to other parts.
Therefore we propose to find explanation in an input-response pair (x, y) by comparing the interactions between segments in (x, y). To identify the most salient interaction pair (xi, yj) (the i-th segment in x and the j-th segment in y), we anticipate that a perturbation x̃ impacts the j-th part most in y if it causes
D(Pθ(yj |x̃, y<j)||Pθ(yj |x, y<j)) > D(Pθ(yj� |x̃, y<j�)||Pθ(yj� |x, y<j�)), ∀j� �= j , (7)
where D represents a distance function measuring the difference between two probability masses. After finding the different part xi in x and x̃, we then define an existing salient interaction in (x, y) is (xi, yj).
In this work, we replace the distance function D in Equation 7 with Kullback–Leibler divergence (DKL) [20]. However, since we reduce the complexity by considering Pθ(y|x) as the certainty estimation of y, we are limited to obtaining only one point in the distribution. We transfer the equation by modeling the estimated joint probability by θ of x and y. We reconsider the joint distributions as Pθ(x̃, y≤j) such that � x̃,y Pθ(x̃, y≤j) = 1 and q(x̃, y) = Pθ,πinv (x̃, y≤j) = Pθ(x, y) such that�
x̃,y q(x̃, y) = � x̃,y Pθ(x, y≤j) = � x̃,y Pθ,πinv (x̃, y≤j) = 1 with πinv being the inverse function
of π. Therefore, D(Pθ(x̃, y≤j)||Pθ(x, y≤j)) = DKL(Pθ(x̃, y≤j)||q(x̃, y≤j)) = �
yj
�
x̃
Pθ(x̃, y≤j) log Pθ(x̃, y≤j) Pθ(x, y≤j) .
(8)
Moreover, since we are estimating the certainty of a response y drawn from data distribution, we know that the random variables x̃ is independently drawn from the perturbation model π. Their independent conditional probabilities are P (y|x) = 1 and π(x̃|x). We approximate the multiplier Pθ(x̃, y≤j) ≈ P (x̃, y≤j |x) = P (x̃|x)P (y|x) = π(x̃|x). The divergence can be simplified to
D(Pθ(x̃, y≤j)||Pθ(x, y≤j)) ≈ �
yj
�
x̃
π(x̃|x) log Pθ(x̃, y≤j) Pθ(x, y≤j) = Ex̃∼π(·|x) log Pθ(x̃, y≤j) Pθ(x, y≤j) . (9)
To meet the inequality for all j and j� �= j, we estimate each value ΦTj z in the explanation model Φ being proportional to the divergence term, where z = h(x, x̃) = {�(xi ∈ x̃)}Mi=1. It turns out to be re-estimating the distinct of the chosen segment yj by normalizing over its original predicted probability.
ΦTj z ∝ Ex̃⊆x\{xi}D(Pθ(x̃, y≤j)||Pθ(x, y≤j)) ≈ Ex̃,x̃⊆x\{xi} log Pθ(x̃, y≤j) Pθ(x, y≤j) . (10)
We propose two variations to optimize Φ following the unified formulation defined in Equation 6.
First, since logarithm is strictly increasing, so to get the same order of Φij , we can drop off the logarithmic term in Equation 10. After reducing the non-linear factor, we use mean square error as the loss function. With the gain function g = Pθ(x̃,y≤j)Pθ(x,y≤j) , the optimization equation becomes
Φj = argmin Φj EP (x̃)( Pθ(x̃, y≤j) Pθ(x, y≤j) −ΦTj z)2, ∀j . (11)
We call this variation as LERG_L in Algorithm 1, since this optimization is similar to LIME but differs by the gain function being a ratio.
To derive the second variation, we suppose an optimized Φ exists and is denoted by Φ∗, we can write that for every x̃ and its correspondent z = h(x, x̃),
Φ∗jz = log Pθ(x̃, y≤j) Pθ(x, y≤j) . (12)
We can then find the formal representation of Φ∗ij by
Φ∗ij = Φ ∗ j1−Φ∗j1i=0
= Φ∗j (z+ ei)−Φ∗jz, ∀x̃ ∈ x\{xi} and z = h(x, x̃) = Ex̃∈x\{xi}[Φ ∗ j (z+ ei)−Φ∗jz] = Ex̃∈x\{xi}[logPθ(yj |x̃ ∪ {xi}, y<j)− logPθ(yj |x̃, y<j)]
(13)
We call this variation as LERG_S in Algorithm 1, since this optimization is similar to Shapley value but differs by the gain function being the difference of logarithm. To further reduce computations, we use Monte Carlo sampling with m examples as a sampling version of Shapley value [41].

heading: 3.3 Properties

text:
We propose that an explanation of dialogue response generation should adhere to three properties to prove itself faithful to the generative model and understandable to humans.
Property 1: unbiased approximation To ensure the explanation model Φ explains the benefits of picking the sentence y, the summation of all elements in Φ should approximate the difference between the certainty of y given x and without x (the language modeling of y).
�
j
�
i
Φij ≈ logP (y|x)− logP (y) . (14)
Algorithm 1: LOCAL EXPLANATION OF RESPONSE GENERATION Input: input message x = x1x2...xM , ground-truth response y = y1y2...yN Input: a response generation model θ to be explained Input: a local explanation model parameterized by Φ // 1st variation – LERG_L for each iteration do
sample a batch of x̃ perturbed from π(x) map x̃ to z = {0, 1}M1 compute gold probability Pθ(yj |x, y<j) compute perturbed probability Pθ(yj |x̃, y<j) optimize Φ to minimize loss function
L = �
j � x̃( Pθ(yj |x̃,y<j) Pθ(yj |x,y<j) −Φ T j z) 2
// 2nd variation - LERG_S for each i do
sample a batch of x̃ perturbed from π(x\{xi}) Φij = 1 m � x̃ logPθ(yj |x̃ ∪ {xi}, y<j)− logPθ(yj |x̃, y<j), for ∀j
return Φij , for ∀i, j
Property 2: consistency To ensure the explanation model Φ consistently explains different generation steps j, given a distance function if
D(Pθ(yj |x̃, y<j), Pθ(yj |x̃∪{xi}, y<j)) > D(Pθ(yj� |x̃, y<j�), Pθ(yj� |x̃∪{xi}, y<j�)), ∀j�, ∀x̃ ∈ x\{xi} , (15) then Φij > Φij� .
Property 3: cause identification To ensure that the explanation model sorts different input features by their importance to the results, if
g(yj |x̃ ∪ {xi}) > g(yj |x̃ ∪ {x�i}), ∀x̃ ∈ x\{xi, x�i} , (16) then Φij > Φi�j We prove that our proposed method adheres to all three Properties in Appendix B. Meanwhile Shapley value follows Properties 2 and 3, while LIME follows Property 3 when an optimized solution exists. These properties also demonstrate that our method approximates the text generation process while sorting out the important segments in both the input and output texts. This could be the reason to serve as explanations to any sequential generative model.

heading: 4 Experiments

text:
Explanation is notoriously hard to evaluate even for digits and sentiment classification which are generally more intuitive than explaining response generation. For digit classification (MNIST), explanations often mark the key curves in figures that can identify digit numbers. For sentiment analysis, explanations often mark the positive and negative words in text. Unlike them, we focus on identifying the key parts in both input messages and their responses. Our move requires an explanation include the interactions of the input and output features.
To evaluate the defined explanation, we quantify the necessity and sufficiency of explanations towards a model’s uncertainty of a response. We evaluate these aspects by answering the following questions.
• necessity: How is the model influenced after removing explanations?
• sufficiency: How does the model perform when only the explanations are given?
Furthermore, we conduct a user study to judge human understandings of the explanations to gauge how trustworthy the dialog agents are.

heading: 4.1 Dataset, Models, Methods

text:
We evaluate our method over chit-chat dialogues for their more complex and realistic conversations. We specifically select and study a popular conversational dataset called DailyDialog [25] because its dialogues are based on daily topics and have less uninformative responses.Due to the large variation of topics, open-ended nature of conversations and informative responses within this dataset, explaining dialogue response generation models trained on DailyDialog is challenging but accessible.3
We fine-tune a GPT-based language model [33, 47] and a DialoGPT [55] on DailyDialog by minimizing the following loss function:
L = − �
m
�
j
logPθ(yj |x, y<j) , (17)
where θ is the model’s parameter. We train until the loss converges on both models and achieve fairly low test perplexities compared to [25]: 12.35 and 11.83 respectively. The low perplexities demonstrate that the models are more likely to be rationale and therefore, evaluating explanations over these models will be more meaningful and interpretable.
We compare our explanations LERG_L and LERG_S with attention [46], gradient [43], LIME [35] and Shapley value [42]. We use sample mean for Shapley value to avoid massive computations (Shapley for short), and drop the weights in Shapley value (Shapley-w for short) due to the intuition that not all permutations should exist in natural language [12, 21]. Our comparison is fair since all methods requiring permutation samples utilize the same amount of samples.4

heading: 4.2 Necessity: How is the model influenced after removing explanations?

text:
Assessing the correctness of estimated important feature relevance requires labeled features for each model and example pair, which is rarely accessible. Inspired by [2, 4] who removes the estimated salient features and observe how the performance changes, we introduce the notion necessity that extends their idea. We quantify the necessity of the estimated salient input features to the uncertainty estimation of response generation by perplexity change of removal (PPLCR), defined as:
PPLCR := exp 1 m [−
� j logPθ(yj |xR,y<j)+ � j logPθ(yj |x,y<j)] , (18)
where xR is the remaining sequence after removing top-k% salient input features.
3We include our experiments on personalized dialogues and abstractive summarization in Appendix E 4More experiment details are in Appendix C
As shown in Figure 2a and Figure 3a5, removing larger number of input features consistently causes the monotonically increasing PPLCR. Therefore, to reduce the factor that the PPLCR is caused by, the removal ratio, we compare all methods with an additional baseline that randomly removes features. LERG_S and LERG_L both outperform their counterparts Shapley-w and LIME by 12.8% and 2.2% respectively. We further observe that Shapley-w outperforms the LERG_L. We hypothesize that this is because LERG_L and LIME do not reach an optimal state.
4.3 Sufficiency: How does the model perform when only the explanations are given?
Even though necessity can test whether the selected features are crucial to the model’s prediction, it lacks to validate how possible the explanation itself can determine a response. A complete explanation is able to recover model’s prediction without the original input. We name this notion as sufficiency testing and formalize the idea as:
PPLA := exp − 1m � j logPθ(yj |xA,y<j) , (19)
where xA is the sequential concatenation of the top-k% salient input features.
As shown in Figure 2b and Figure 3b, removing larger number of input features gets the PPLA closer to the perplexity of using all input features 12.35 and 11.83. We again adopt a random baseline to compare. LERG_S and LERG_L again outperform their counterparts Shapley-w and LIME by 5.1% and 3.4% respectively. Furthermore, we found that LERG_S is able to go lower than the original 12.35 and 11.83 perplexities. This result indicates that LERG_S is able to identify the most relevant features while avoiding features that cause more uncertainty during prediction.
4.4 User Study
To ensure the explanation is easy-to-understand by non machine learning experts and gives users insights into the model, we resort to user study to answer the question: “If an explanation can be understood by users to respond?”
We ask human judges to compare explanation methods. Instead of asking judges to annotate their explanation for each dialogue, to increase their agreements we present only the explanations (Top 20% features) and ask them to choose from four response candidates, where one is the ground-truth, two are randomly sampled from other dialogues, and the last one is randomly sampled from other turns in the same dialogue. Therefore the questionnaire requires human to interpret the explanations but not guess a response that has word overlap with the explanation. The higher accuracy indicates the higher quality of explanations. To conduct more valid human evaluation, we randomly sample 200 conversations with sufficiently
long input prompt (length≥ 10). This way it filters out possibly non-explainable dialogues that can cause ambiguities to annotators and make human evaluation less reliable.
We employ three workers on Amazon Mechanical Turk [7] 6 for each method of each conversation, resulting in total 600 annotations. Besides the multiple choice questions, we also ask judges to claim their confidences of their choices. The details can be seen in Appendix D. The results are listed in Table 1. We observe that LERG_L performs slightly better than LIME in accuracy while maintaining similar annotator’s confidence. LERG_S significantly outperforms Shapley-w in both accuracy and annotators’ confidence. Moreover, these results indicates that when presenting users with only 20% of the tokens they are able to achieve 56% accuracy while a random selection is around 25%.
(a) Implication: find the "hot potato" might indicate "gasoline".
(b) Sociability: find "No" for the "question mark" and "thanks" for the "would like", the polite way to say "want".
(c) Error analysis: related but not the best
Figure 4: Two major categories of local explanation except word alignment and one typical error. The horizontal text is the input prompt and the vertical text is the response.

heading: 4.5 Qualitative Analysis

text: We further analyzed the extracted explanation for each dialogue. We found that these fine-grained level explanations can be split into three major categories: implication / meaning, sociability, and oneto-one word mapping. As shown in Figure 4a, the “hot potato” in response implies the phenomenon of “reduce the price of gasoline”. On the other hand, Figure 4b demonstrates that a response with sociability can sense the politeness and responds with “thanks”. We ignore word-to-word mapping here since it is intuitive and can already be successfully detected by attention models. Figure 4c shows a typical error that our explanation methods can produce. As depicted, the word “carry” is related to “bags”,“suitcases”, and “luggage”. Nonetheless a complete explanation should cluster “carry-on luggages”. The error of explanations can result from (1) the target model or (2) the explanation method. When taking the first view, in future work, we might use explanations as an evaluation method for dialogue generation models where the correct evaluation metrics are still in debates. When taking the second view, we need to understand that these methods are trying to explain the model and are not absolutely correct. Hence, we should carefully analyze the explanations and use them as reference and should not fully rely on them.

heading: 5 Related Work and Discussion

text:
Explaining dialogue generation models is of high interest to understand if a generated response is reasonably produced rather than being a random guess. For example, among works about controllable dialogue generation [15, 26, 37, 40, 48, 50, 51, 53], Xu et al. [49] takes the dialog act in a controllable response generation model as the explanation. On the other hand, some propose to make dialogue response generation models more interpretable through walking on knowledge graphs [18, 28, 44]. Nonetheless, these works still rely on models with complex architecture and thus are not fully interpretable. We observe the lack of a model-agnostic method to analyze the explainability of dialogue response generation models, thus proposing LERG.
Recently, there are applications and advances of local explanation methods [27, 35, 38]. For instance in NLP, some analyze the contributions of segments in documents to positive and negative sentiments [4, 8, 9, 29]. Some move forwards to finding segments towards text similarity [10], retrieving a text span towards question-answering [32], and making local explanation as alignment model in machine translation [1]. These tasks could be less complex than explaining general text generation models, such as dialogue generation models, since the the output space is either limited to few classes or able to find one-to-one mapping with the input text. Hence, we need to define how local explanations on text generation should work. However, we would like to note that LERG serves as a general formulation for explaining text generation models with flexible setups. Therefore, the distinct of prior work can also be used to extend LERG, such as making the explanations hierarchical. To move forward with the development of explanation methods, LERG can also be extended to dealing
5We did a z-test and a t-test [22] with the null hypothesis between LERG_L and LIME (and LERG_S and Shapley). For both settings the p-value was less than 0.001, indicating that the proposed methods significantly outperform the baselines.
6https://www.mturk.com
with off- /on- data manifold problem of Shapley value introduced in [13], integrating causal structures to separate direct / in-direct relations [12, 16], and fusing concept- / feature- level explanations [5].

heading: 6 Conclusion

text: Beyond the recent advances on interpreting classification models, we explore the possibility to understand sequence generation models in depth. We focus on dialogue response generation and find that its challenges lead to complex and less transparent models. We propose local explanation of response generation (LERG), which aims at explaining dialogue response generation models through the mutual interactions between input and output features. LERG views the dialogue generation models as a certainty estimation of a human response so that it avoids dealing with the diverse output space. To facilitate future research, we further propose a unification and three properties of explanations for text generation. The experiments demonstrate that LERG can find explanations that can both recover a model’s prediction and be interpreted by humans. Next steps can be taking models’ explainability as evaluation metrics, integrating concept-level explanations, and proposing new methods for text generation models while still adhering to the properties.

heading: 7 Acknowledgement

text: We thank all the reviewers precious comments in revising this paper. This material is based on work that is partially funded by an unrestricted gift from Google.

title: Local Explanation of Dialogue Response Generation


summaries: The authors consider accelerated training algorithms using gradient compression with error compensation. For this purpose, they incorporated gradient compression and error compensation in the Katyusha algorithm and developed ECKL. The algorithm quantizes both the SG and VR term and keeps track of the quantization error for error compensation in the next iteration.  The paper analyzed the convergence rate and iteration complexity of ECKL for the smooth convex functions and compared it with variants of DIANA both theoretically and via some simple simulations on logistic regression.

summaries: The paper introduces an error compensation variant of the loopless Katyusha, ECLK. Theoretical convergence analysis is given and accelerated linear convergence rate is obtained using contraction operators. Experimental study of ECLK is given on the logistic regression problem for binary classification.

summaries: This paper presents accelerated methods for communication-efficient learning applications. In particular, a loopless Katyusha strategy is introduced to attain the O(\sqrt{L/\mu}) rate for error-compensated methods using stochastic gradient information. These methods are called ECLK. In terms of theoretical iteration complexity and empirical experiments, ECLK is explicitly shown to be more communication efficient and to have a better rate than existing error compensation methods.

summaries: This paper proposed an error compensated based Katyusha method for finite-sum convex problems. The proposed method achieves the same asymptotic convergence rate as its full precision accelerated counterpart. Compared to another related work ADIANA, the proposed method can be applied to contractive compressor.

summaries: This paper considers communication efficient algorithms for SGD. In this model, there are $n$ total workers and each worker has a local smooth convex loss function $f_i$ on $R^d$. The objective is for a coordinator to find an approximate global minimum for an objective function that represents the average loss across all workers while minimizing communication between the workers and the coordinator.   A common approach is for each worker to compute a sketch on their local batch of gradients that allows the coordinator to recover of the top $k$ gradients in magnitude, ideally improving the rate of convergence. However, the challenge with this approach is that the estimator formed by the coordinator using the sketches sent from the workers may not be an unbiased estimator of the overall gradient, which allows error to accumulate over multiple iterations. This paper introduces provable accelerated gradient-methods, in the sense of Nesterov momentum for contractive compressors, which are a general class of stochastic functions that form estimators of the gradient, including the top $k$ estimator.

abstractText: Gradient compression is a recent and increasingly popular technique for reducing the communication cost in distributed training of large-scale machine learning models. In this work we focus on developing efficient distributed methods that can work for any compressor satisfying a certain contraction property, which includes both unbiased (after appropriate scaling) and biased compressors such as RandK and TopK. Applied naively, gradient compression introduces errors that either slow down convergence or lead to divergence. A popular technique designed to tackle this issue is error compensation/error feedback. Due to the difficulties associated with analyzing biased compressors, it is not known whether gradient compression with error compensation can be combined with acceleration. In this work, we show for the first time that error compensated gradient compression methods can be accelerated. In particular, we propose and study the error compensated loopless Katyusha method, and establish an accelerated linear convergence rate under standard assumptions. We show through numerical experiments that the proposed method converges with substantially fewer communication rounds than previous error compensated algorithms.

authors:
A. Agarwal
J.C. Duchi

title: Distributed delayed stochastic optimization

venue: In Advances in Neural Information Processing Systems (NIPS),

authors:
D. Alistarh
D. Grubic
J. Li
R. Tomioka
M. Vojnovic

title: QSGD: Communication-efficient SGD via gradient quantization and encoding

authors:
D. Alistarh
T. Hoefler
M. Johansson
N. Konstantinov
S. Khirirat
C. Renggli

title: The convergence of sparsified gradient methods

venue: In Advances in Neural Information Processing Systems (NeurIPS),

title: Katyusha: The first direct acceleration of stochastic gradient methods

authors:
J. Bernstein
Y.X. Wang
K. Azizzadenesheli
A. Anandkumar

title: SignSGD: Compressed optimisation for non-convex problems

authors:
A. Beznosikov
S. Horváth
P. Richtárik
M. Safaryan

title: On biased compression for distributed learning

venue: arXiv preprint arXiv:2002.12410,

authors:
Chih-Chung Chang
Chih-Jen Lin

title: LIBSVM: A library for support vector machines

venue: ACM Transactions on Intelligent Systems and Technology (TIST),

authors:
Eduard Gorbunov
Dmitry Kovalev
Dmitry Makarenko
Peter Richtárik

title: Linearly converging error compensated SGD

venue: In Neural Information Processing Systems (NeurIPS),

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.2677,

authors:
Filip Hanzely
Peter Richtárik

title: Federated learning of a mixture of global and local models

venue: arXiv preprint arXiv:2002.05516,

authors:
S. Horváth
D. Kovalev
K. Mishchenko
S. Stich
P. Richtárik

title: Stochastic distributed learning with gradient quantization and variance reduction

venue: arXiv preprint arXiv:1904.05115,

authors:
Samuel Horváth
Chen-Yu Ho
L’udovít Horvath
Atal Narayan Sahu
Marco Canini
Peter Richtárik

title: Natural compression for distributed deep learning

venue: arXiv preprint arXiv:1905.10988,

title: Advances and open problems in federated learning

venue: arXiv preprint arXiv:1912.04977,

authors:
Sai Praneeth Karimireddy
Quentin Rebjock
Sebastian U Stich
Martin Jaggi

title: Error feedback fixes SignSGD and other gradient compression schemes

authors:
Ahmed Khaled
Konstantin Mishchenko
Peter Richtárik

title: Tighter theory for local SGD on identical and heterogeneous data

venue: In The 23rd International Conference on Artificial Intelligence and Statistics (AISTATS),

authors:
Jakub Konečný
H. Brendan McMahan
Daniel Ramage
Peter Richtárik

title: Federated optimization: distributed machine learning for on-device intelligence

venue: arXiv preprint arXiv:1610.02527,

authors:
Jakub Konečný
H. Brendan McMahan
Felix Yu
Peter Richtárik
Ananda Theertha Suresh
Dave Bacon

title: Federated learning: strategies for improving communication efficiency

venue: In NIPS Private Multi-Party Machine Learning Workshop,

authors:
D. Kovalev
S.l Horváth
P. Richtárik

title: Don’t jump through hoops and remove those loops: SVRG and Katyusha are better without the outer loop

venue: In Proceedings of the 31st International Conference on Algorithmic Learning Theory (ALT),

authors:
Guanghui Lan
Yi Zhou

title: An optimal randomized incremental gradient method

venue: Mathematical programming,

authors:
Tian Li
Anit Kumar Sahu
Ameet Talwalkar
Virginia Smith

title: Federated learning: challenges, methods, and future directions

authors:
Zhize Li
Dmitry Kovalev
Xun Qian
Peter Richtárik

title: Acceleration for compressed gradient descent in distributed and federated optimization

venue: In Proceedings of the 37th International Conference on Machine Learning (ICML),

authors:
X. Lian
Y. Huang
Y. Li
J. Liu

title: Asynchronous parallel stochastic gradient for nonconvex optimization

authors:
Chenxin Ma
Jakub Konečný
Martin Jaggi
Virginia Smith
Michael I. Jordan
Peter Richtárik
Martin Takáč

title: Distributed optimization with arbitrary local solvers

venue: Optimization Methods and Software,

authors:
H Brendan McMahan
Eider Moore
Daniel Ramage
Seth Hampson
Blaise Agüera y Arcas

title: Communication-efficient learning of deep networks from decentralized data

venue: In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS),

authors:
K. Mishchenko
E. Gorbunov
M. Takáč
P. Richtárik

title: Distributed learning with compressed gradient differences

venue: arXiv preprint arXiv:1901.09269,

title: Introductory lectures on convex optimization: a basic course (Applied Optimization)

venue: Kluwer Academic Publishers,

authors:
Xun Qian
Zheng Qu
Peter Richtárik

title: L-SVRG and L-Katyusha with arbitrary sampling

venue: arXiv preprint arXiv:1906.01481,

authors:
B. Recht
C. Re
S. Wright
F. Niu

title: Hogwild: A lock-free approach to parallelizing stochastic gradient descent

authors:
F. Seide
H. Fu
J. Droppo
G. Li
D. Yu

title: 1-bit stochastic gradient descent and its application to data- parallel distributed training of speech DNNs

venue: Fifteenth Annual Conference of the International Speech Communication Association,

authors:
S.U. Stich
S.P. Karimireddy

title: The error-feedback framework: Better rates for SGD with delayed gradients and compressed communication

authors:
S.U. Stich
J.B. Cordonnier
M. Jaggi

title: Sparsified SGD with memory

title: Local SGD converges fast and communicates little

venue: In International Conference on Learning Representations (ICLR),

authors:
H. Tang
S. Gan
C. Zhang
T. Zhang
J. Liu

title: Communication compression for decentralized training

authors:
H. Tang
X. Lian
T. Zhang
J. Liu

title: DoubleSqueeze: Parallel stochastic gradient descent with double-pass error-compensated compression

venue: In Proceedings of the 36th International Conference on Machine Learning (ICML),

authors:
W. Wen
C. Xu
F. Yan
C. Wu
Y. Wang
H. Li

title: Terngrad: Ternary gradients to reduce communication in distributed deep learning

authors:
Blake Woodworth
Kumar Kshitij Patel
Sebastian U. Stich
Zhen Dai
Brian Bullins
H. Brendan McMahan
Ohad Shamir
Nathan Srebro

title: Is local SGD better than minibatch SGD

authors:
J. Wu
W. Huang
J. Huang
T. Zhang

title: Error compensated quantized SGD and its applications to large-scale distributed optimization

venue: In The 35th International Conference on Machine Learning (ICML),

authors:
Y. You
I. Gitman
B. Ginsburg

title: Scaling SGD batch size to 32k for imagenet training

venue: arXiv preprint arXiv:1708.03888,

heading: 1 Introduction

text:
When training very large scale supervised machine learning problems, such as those arising in the context of federated learning [Konečný et al., 2016b, McMahan et al., 2017, Konečný et al., 2016a] (see also recent surveys [Li et al., 2019, Kairouz, 2019]), distributed algorithms are indispensable. In such settings, communication is generally much slower than (local) computation, which makes it the key bottleneck in the design of efficient distributed systems. There are several ways to tackle this issue, including reliance on large mini-batches [Goyal et al., 2017, You et al., 2017], asynchronous learning [Agarwal and Duchi, 2011, Lian et al., 2015, Recht et al., 2011], local updates [Ma et al., 2017, Stich, 2020, Khaled et al., 2020, Hanzely and Richtárik, 2020, Woodworth et al., 2020] and communication compression (e.g., quantization and sparsification) [Alistarh et al., 2017, Bernstein et al., 2018, Mishchenko et al., 2019, Seide et al., 2014, Wen et al., 2017].
Communication compression. In this work, we focus on the last of these techniques: communication compression. The key idea here is to apply a lossy compression transformation/operator to the messages before they are communicated so as to save on communication time. While compression reduces the communicated bits in each communication round, it introduces errors, and this generally leads to an increase in the number of communication rounds needed to find a solution of any predefined accuracy. Still, compression has been found useful in practice, as the trade-off often seems to prefer compression to no compression.
∗King Abdullah University of Science and Technology, Thuwal, Saudi Arabia †King Abdullah University of Science and Technology, Thuwal, Saudi Arabia; Moscow Institute of Physics
and Technology, Dolgoprudny, Russia ‡Hong Kong University of Science and Technology, Hong Kong
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
Contractive and unbiased compressors. There are two large families of such compression operators: contraction and unbiased compressors [Beznosikov et al., 2020]. A (possibly) randomized map Q : Rd → Rd is called a contraction compressor if there exists a constant 0 < δ ≤ 1 such that
E [ ∥x−Q(x)∥2 ] ≤ (1− δ)∥x∥2, ∀x ∈ Rd. (1)
Further, we say that a randomized map Q̃ : Rd → Rd is an unbiased compressor if there exists a constant ω ≥ 0 such that
E [ Q̃(x) ] = x and E [ ∥Q̃(x)∥2 ] ≤ (ω + 1)∥x∥2, ∀x ∈ Rd. (2)
It is well known that (see, e.g., [Beznosikov et al., 2020]) after appropriate scaling, any unbiased compressor satisfying (2) becomes a contraction compressor. Indeed, it is easy to verify that for any Q̃ satisfying (2), 1ω+1 Q̃ is a contraction compressor satisfying (1) with δ = 1/(ω+1). Thus we can construct corresponding contraction compressor from any unbiased compressor. However, there are empirically very powerful contractive compressors, such as TopK [Alistarh et al., 2018] (described below), which do not arise this way, and because of this, the class of contractive compressors is important in practice. For illustration purposes, we now define two canonical examples of contraction compressors. Let 1 ≤ K ≤ d. The TopK compressor is defined as
(TopK(x))π(i) =
{ (x)π(i) if i ≤ K,
0 otherwise,
where π is a permutation of {1, 2, ..., d} such that (|x|)π(i) ≥ (|x|)π(i+1) for i = 1, ..., d − 1. The RandK compressor is defined as
(RandK(x))i = { (x)i if i ∈ S, 0 otherwise,
where S is chosen uniformly from the set of all K element subsets of {1, 2, ..., d}. For TopK and RandK compressors, we have δ ≥ K/d [Stich et al., 2018]. Some frequently used unbiased compressors include random dithering [Alistarh et al., 2017], random sparsification [Stich et al., 2018], and natural compression [Horváth et al., 2019b]. For more examples of contraction and unbiased compressors, we refer the reader to [Beznosikov et al., 2020].
Related Work. If we assume that the accumulated error is bounded, and in the case of unbiased compressors, the convergence rate of error compensated SGD was shown to be the same as that of vanilla SGD [Tang et al., 2018]. However, if we only assume bounded second moment of the stochastic gradients, in order to guarantee the boundedness of the accumulated quantization error, some decaying factors need to be involved in general, and error compensated SGD is proved to have some advantage over QSGD [Alistarh et al., 2017] in some perspective for convex quadratic problems [Wu et al., 2018]. On the other hand, for contraction compressors, error compensated SGD actually has the same convergence rate as vanilla SGD [Stich et al., 2018, Stich and Karimireddy, 2019, Tang et al., 2019]. Since SGD only has a sublinear convergence rate, these error compensated methods could not get linear convergence rate. If f is non-smooth and ψ = 0, error compensated SGD was studied in [Karimireddy et al., 2019] in the single node case, and the convergence rate is of order O (1/ √ δk).
For variance-reduced methods, QSVRG [Alistarh et al., 2017] handles the smooth case (ψ ≡ 0), and VR-DIANA [Horváth et al., 2019a], ADIANA [Li et al., 2020] handle the composite case (general ψ). However, the compressors of these algorithms need to be unbiased. Error compensation in VR-DIANA and ADIANA does not need to be used since their method successfully employs variance reduction (of the variance introduced by the compressor) instead. Recently, an error compensated method called EC-LSVRG-DIANA which can achieve nonaccelerated linear convergence for the strongly convex and smooth case was proposed in [Gorbunov et al., 2020], but besides the contraction compressor, the unbiased compressor is also needed in the algorithm.
Error compensation. While contractive compressors can be more powerful in practice, they are not unbiased, and this leads to severe difficulties in the algorithm design space, and poses challenges for theoreticians trying to understand the convergence behavior of distributed algorithms using contractive compressors. Indeed, while there is no issue with the use of contractive compressors in the non-distributed setting (which is of course not interesting from a practical point of view) in
combination with standard gradient-type methods, serious convergence issues arise in the distributed setting. Indeed, classical methods such gradient descent can diverge (even exponentially fast) when the TopK compressor is used to compress uplink gradient information [Beznosikov et al., 2020]. Fortunately, this issue can be resolved using the error compensation (EC)4 mechanism, which can be traced back to at least Seide et al. [2014]. However, this mechanism remained a heuristic until recently. To highlight the difficulty of analyzing EC, we remark that the first theoretical breakthroughs applied to the single node regime only [Stich et al., 2018, Stich and Karimireddy, 2019]. More recently, theoretical progress was made in the crucially important distributed setting as well [Beznosikov et al., 2020, Gorbunov et al., 2020]. However, we are still very far in our understanding of optimization algorithms using contractive compressors.
One of the key open problems in this area—the problem we address in this paper in the affirmative— is whether it is possible to design provably accelerated gradienttype methods that work with contractive compressors.
In this paper, we give a confirmed answer by studying error compensation in conjunction with the acceleration mechanism employed in loopless Katyusha (L-Katyusha) [Kovalev et al., 2020, Qian et al., 2019], which is a loopless variant of Katyusha [Allen-Zhu, 2017]. The acceleration in Katyusha or L-Katyusha is an extension of Nesterov’s acceleration [Nesterov, 1983, 2004] in the stochastic regime. Moreover, Katyusha and L-Katyusha can achieve the optimal iteration complexity among randomized methods for solving finite-sum strongly convex optimization problems [Lan and Zhou, 2018].

heading: 2 Problem Description and Summary of Contributions

text: We formally describe the distributed optimization problem we solve in Section 2.1, and then summarize our key contributions in Section 2.2.

heading: 2.1 Problem Description

text:
We consider the composite finite-sum optimization problem
min x∈Rd P (x) :=
{ 1 n n∑ τ=1 f (τ)(x) + ψ(x) } , (3)
where f(x) := 1n ∑ τ f
(τ)(x) is an average of n smooth convex functions, distributed over n compute nodes, and ψ : Rd → R∪ {+∞} is a proper closed convex function representing a possibly nonsmooth regularizer. On each node τ , f (τ)(x) is an average of m smooth convex functions, i.e.,
f (τ)(x) = 1m m∑ i=1 f (τ) i (x), representing the average loss over the training data stored on this node.
We denote the smoothness constants of functions f , f (τ) and f (τ)i using symbols Lf , L̄ and L, respectively.5 These constants are in general related as follows:
Lf ≤ L̄ ≤ nLf , L̄ ≤ L ≤ mL̄. (4)
While we specifically focus on the case when m = 1, our results are also new in the m = 1 case, and hence this regime is relevant as well. We assume throughout that problem (3) has at least one optimal solution x∗.
We will optionally use the following additional assumption for the contraction compressor. The assumption is not necessary, but when used, it will lead to better complexity. Assumption 2.1. E[Q(x)] = δx and E[Q1(x)] = δ1x for all x ∈ Rd, where δ and δ1 are compression parameters of Q and Q1, respectively.
It is easy to verify that RandK compressor satisfies Assumption 2.1 with δ = K/d, and 1ω+1 Q̃, where Q̃ is any unbiased compressor, also satisfies Assumption 2.1 with δ = 1/(ω+1).
4Error compensation is also known under the name error feedback. 5Function f : Rd → R is smooth if it is differentiable, and has L-Lipschitz gradient: ∥∇f(x)−∇f(y)∥ ≤
L∥x− y∥ for any x, y ∈ Rd. L is called the smoothness constant of f .

heading: 2.2 Contributions

text:
We now summarize the main contributions of our work.
Acceleration for error compensation. We develop a new communication efficient algorithm (Algorithm 1) for solving the distributed optimization problem (3) which we call Error Compensated Loopless Katyusha (ECLK). ECLK is the first accelerated error compensated method (this is true even in the non-distributed setting), which we believe is a significant contribution to the field.
Iteration complexity. We obtain the first accelerated linear convergence rate for error compensated methods using contraction operators. Let p ≤ O(δ1), where p ∈ (0, 1] is a parameter of the method described later and δ1 is the compression parameter of Q1 in Algorithm 1 (see Assumption 2.1). Then the iteration complexity of ECLK is
O ((
1 δ + 1 p + √ Lf µ + √ L µpn + 1 δ √ (1−δ)L̄ µp + √ (1−δ)L µpδ ) log 1ϵ ) . (5)
This is an improvement over the previous best known results for error compensated methods in [Beznosikov et al., 2020] and [Gorbunov et al., 2020], where nonaccelerated linear rates were obtained for the smooth case (ψ ≡ 0). Moreover, in oder to obtained a linear rate, Beznosikov et al. [2020] required the assumption that ∇f (τ)(x∗) = 0 for all τ , and also need full gradients to be computed by all nodes. The complexity of EC-LSVRG-DIANA in [Gorbunov et al., 2020] is
O (( ω +m+ Lδµ ) log 1ϵ ) . (6)
When the last term in (6) is dominant and the last two terms in (5) are dominant, the complexity of ECLK is better than that of EC-LSVRG-DIANA if p ≥ O
( (1−δ)L̄µ
L2 + (1−δ)δµ L
) .
If we invoke additional assumptions (Assumption 2.1) on the contraction compressor, the iteration complexity of ECLK is improved to
O ((
1 δ + 1 p + √ Lf µ + √ L µpn + 1 δ √ (1−δ)Lf µp + √ (1−δ)L µpδn ) log 1ϵ ) .
This is indeed an improvement since Lf ≤ L̄ (see (4)), and because of the extra scaling factor of n in the last term. If δ = δ1 = 1, i.e., if no compression is used, we recover the iteration complexity of the accelerated method L-Katyusha [Qian et al., 2019].

heading: 3 Error compensated L-Katyusha

heading: 3.1 Description of the method

text:
In this section we describe our method: error compensated L-Katyusha (see Algorithm 1). Roughly speaking, ECLK is a combination of L-Katyusha, error feedback, and a learning scheme in VRDIANA [Horváth et al., 2019a].
The search direction in L-Katyusha in the distributed setting (n ≥ 1) at iteration k is
1
n n∑ τ=1 ( ∇f (τ)iτk (x k)−∇f (τ)iτk (w k) +∇f (τ)(wk) ) ,
where iτk is sampled uniformly and independently from [m] := {1, 2, ...,m} on the τ -th node for 1 ≤ τ ≤ n, xk is the current iteration, and wk is the current reference point. Whenever ψ is nonzero in problem (3), ∇f(x∗) is nonzero in general, and so is ∇f (τ)(x∗) (it could be nonzero even if ∇f(x∗) = 0 in the non-regularized case). Thus, compressing the direction
∇f (τ)iτk (x k)−∇f (τ)iτk (w k) +∇f (τ)(wk) (7)
directly on each node would cause nonzero noise even if xk and wk converged to the optimal solution x∗. On the other hand, since f (τ)i is L-smooth, ∇f (τ) iτk (xk)−∇f (τ)iτk (w k) could be small if xk and wk are close enough. For the last term ∇f (τ)(wk), we introduce a vector hkτ to learn it iteratively in
a similar way in VR-DIANA. However, we use a contraction compressor rather than an unbiased one. More precisely, we take the update
hk+1τ = h k τ +Q1(∇f (τ)(wk)− hkτ ), (8)
where Q1 is a contraction compressor. h0τ can be initialized by any vector in Rd. It is possible to interprete the learning procedure (8) as one step of the compressed gradient descent method applied to a certain quadratic optimization problem whose unique solution is the vector ∇f (τ)(wk). Now we would expect ∇f (τ)(wk)− hkτ could converge to zero as k → +∞. We substract hkτ from the search direction in (7) to get
gkτ = ∇f (τ) iτk (xk)−∇f (τ)iτk (w k) +∇f (τ)(wk)− hkτ ,
and will add hkτ back after aggregation.
Next we apply the compression and error feedback techniques, i.e., we compress the vector ηL1 g k τ +e k τ on each node to get g̃kτ = Q( η L1 g k τ + e k τ ), where Q is a contraction compressor and L1 is a positive parameter. The accumulated error ek+1τ is updated by the compression error at iteration k. On each node, a scalar ukτ is also maintained, and only u k 1 will be updated. The summation of u k τ for 1 ≤ τ ≤ n is uk, and we use uk to control the update frequency of the reference point wk.6 Each node sends the two compressed vectors g̃kτ , Q1(∇f (τ)(wk) − hkτ ), and a scalar uk+1τ to the other nodes. After aggregating g̃k = 1n ∑n τ=1 g̃ k τ , we add the average vector h k = 1n ∑n τ=1 h k τ after multiplying the stepsize ηL1 to it to get the search direction g̃ k + ηL1h
k. We also use the following standard proximal operator for the update of zk:
proxηψ(x) := argmin y
{ 1 2∥x− y∥ 2 + ηψ(y) } .
The reference point wk will be updated if uk+1 = 1. It is easy to see that wk will be updated with probability p at each iteration. All nodes maintain the same copies of xk, wk, yk, zk, g̃k, hk, and uk.
We need the following assumptions in this section. Assumption 3.1. The two compressors Q and Q1 in Algorithm 1 are contraction compressors with parameters δ and δ1, respectively.
Assumption 3.2. f (τ)i is L-smooth, f (τ) is L̄-smooth, f is Lf -smooth and µf -strongly convex, and ψ is µψ-strongly convex, where µf ≥ 0, µψ ≥ 0, and µ := µf + µψ > 0.

heading: 3.2 Convergence analysis: preliminaries

text:
First, we introduce some perturbed vectors which will be used in the convergence analysis. The perturbed vector is usually used in the analysis of error compensated methods [Karimireddy et al., 2019]. In Algorithm 1, let ek = 1n ∑n τ=1 e k τ , g k = 1n ∑n τ=1 g k τ , and x̃ k = xk − 11+ησ1 e k, z̃k = zk − 11+ησ1 e k for k ≥ 0. Then ek+1 = 1n ∑n τ=1 ( ekτ + η L1 g k τ − g̃kτ ) = ek + ηL1 g
k − g̃k, and from the optimality condition for the proximal operator, we have
z̃k+1 = zk+1 − 11+ησ1 e k+1
= 11+ησ1
( ησ1x k + zk − g̃k − ηL1h k ) − η∂ψ(z k+1 (1+ησ1)L1 )− ek+1 1+ησ1
= 11+ησ1
( ησ1x
k + zk − ek − ηL1 g k − ηL1h
k ) − η∂ψ(z
k+1) (1+ησ1)L1
= 11+ησ1
( ησ1x̃
k + z̃k − ηL1 g k − ηL1h
k ) − η∂ψ(z
k+1) (1+ησ1)L1 . (9)
The above relation plays a vital role in the convergence analysis, and allows us to follow the analysis of original L-Katyusha. In particular, we will use z̃k to construct Lyapunov functions. Next we define some notations which will be used to construct Lyapunov functions. Define Z̃k := L1+ηµ/22η ∥z̃ k −
6We can also use a single shared random variable uk instead.
Algorithm 1 Error Compensated Loopless Katyusha (ECLK)
1: Parameters: stepsize parameters η = 13θ1 > 0, L1 > 0, σ1 = µf 2L1 ≥ 0, θ1, θ2 ∈ (0, 1);
probability p ∈ (0, 1] 2: Initialization: x0 = y0 = z0 = w0 ∈ Rd; u0τ = 0 ∈ R; e0τ = 0 ∈ Rd; h0τ ∈ Rd; u0 = ∑n τ=1 u 0 τ ; h 0 = 1n ∑n τ=1 h 0 τ 3: for k = 0, 1, 2, ... do 4: for τ = 1, ..., n do 5: Sample iτk uniformly and independently in [m] on each node 6: gkτ = ∇f (τ) iτk (xk)−∇f (τ)iτk (w k) +∇f (τ)(wk)− hkτ 7: g̃kτ = Q( η L1 g k τ + e k τ ), h k+1 τ = h k τ +Q1(∇f (τ)(wk)− hkτ ) 8: ek+1τ = e k τ + η L1 g k τ − g̃kτ , uk+1τ = 0 for τ = 2, ..., n
9: uk+11 = { 1 with probability p 0 with probability 1− p
10: Send g̃kτ , Q1(∇f (τ)(wk)− hkτ ), and uk+1τ to the other nodes 11: Receive g̃kτ , Q1(∇f (τ)(wk)− hkτ ), and uk+1τ from the other nodes 12: g̃k = 1n ∑n τ=1 g̃ k τ , u k+1 = ∑n τ=1 u k+1 τ 13: zk+1 = prox η (1+ησ1)L1 ψ ( 1 1+ησ1 ( ησ1x k + zk − g̃k − ηL1h k )) 14: yk+1 = xk + θ1(zk+1 − zk)
15: wk+1 = { yk if uk+1 = 1 wk otherwise
16: xk+1 = θ1zk+1 + θ2wk+1 + (1− θ1 − θ2)yk+1 17: hk+1 = hk + 1n ∑n τ=1Q1(∇f (τ)(wk)− hkτ ) 18: end for 19: end for
x∗∥2, Yk := 1θ1 (P (y k) − P ∗), and Wk := θ2pqθ1 (P (w k) − P ∗) for k ≥ 0, where P ∗ := P (x∗). From the update rule of wk in Algorithm 1, it is easy to see that
Ek[Wk+1] = (1− p)Wk + θ2q Y k, (10)
for k ≥ 0. Let Bf (x, y) := f(x) − f(y) − ⟨∇f(y), x − y⟩ be the Bregman divergence and Ek[·] denote the expectation conditional on xk, yk, zk, wk, hkτ , u k τ , and e k τ . The following lemma reveals the evolution of the other two terms Z̃k and Yk. Lemma 3.3. If L1 ≥ Lf and θ1 + θ2 ≤ 1, then Ek [ Z̃k+1 + Yk+1 ] can be upper bounded by
L1 L1+ηµ/2 Z̃
k + (1− θ1 − θ2)Yk + pqWk + ( L1 2η + µf 2 ) ∥ek∥2 + ( L1 2η + µ 2 ) Ek [ ∥ek+1∥2 ] − 1θ1 ( θ2 − 2LnL1 ) Bf (w k, xk)− 1−θ1−θ2θ1 Bf (y k, xk).
Because of the compression, we have the additional error terms ∥ek∥2 and ∥ek+1∥2 in the evolution of Z̃k and Yk in Lemma 3.3. To upper bound these error terms, we need to analyze the evolution of 1 n ∑n τ=1 e k τ and 1 n ∑n τ=1 ∥hkτ −∇f (τ)(wk)∥2 in the next two lemmas.
Lemma 3.4. The quantity Ek [ 1 n n∑ τ=1 ∥ek+1τ ∥2 ] is upper bounded by the expression
( 1− δ2 ) 1 n n∑ τ=1 ∥ekτ∥2 + 4(1−δ)η2 δnL21 n∑ τ=1 ∥∇f (τ)(wk)− hkτ∥2 + 2(1−δ)η2 L21 ( 4L̄ δ + L ) Bf (w k, xk).
Lemma 3.5. The quantity 1n ∑n τ=1 Ek[∥hk+1τ −∇f (τ)(wk+1)∥2] is upper bounded by the expression(
1− δ12 ) 1 n n∑ τ=1 ∥hkτ −∇f (τ)(wk)∥2 + 4L̄p ( 1 + 2pδ1 ) Bf (y k, xk) + 4L̄p ( 1 + 2pδ1 ) Bf (w k, xk).
Under the additional Assumption 2.1, we need to analyze the evolution of ∥ek∥2 and ∥hk−∇f(wk)∥2 as well, which can be found in the appendix.

heading: 3.3 Convergence analysis: main results

text:
With the above lemmas at hand, we are ready to construct suitable Lyapunov functions which enable us to prove linear convergence. First, we construct the Lyapunov function Φk for the general case. Let L2 := 6Ln + 112(1−δ)L̄ 3δ2 + 28(1−δ)L 3δ + 224(1−δ)L̄p δ2δ1 ( 1 + 2pδ1 ) , and for k ≥ 0 define
Φk := Z̃k + Yk +Wk + 4L1δη · 1 n n∑ τ=1 ∥ekτ∥2 + 56(1−δ) 3θ1δ2δ1L1 · 1 n n∑ τ=1 ∥hkτ −∇f (τ)(wk)∥2.
Then we can get the linear convergence of Φk in the following theorem. Theorem 3.6. Let Assumption 3.1 and Assumption 3.2 hold. If L1 ≥ max{Lf , 3µη}, θ1 + 2θ2 ≤ 1, and θ2 ≥ L23L1 , then we have
E [ Φk ] ≤ ( 1−min ( µ
µ+6θ1L1 , θ1 + θ2 − θ2 q , p(1− q), δ 6 , δ1 6
))k Φ0, ∀k ≥ 0.
If Assumption 2.1 holds, we define the Lyapunov function Ψk as follows. Let L3 := 6Ln + 112(1−δ)Lf
3δ2 + 224(1−δ)L̄ δ2n + 308(1−δ)L 3δn + 224(1−δ)p δ2δ1
( Lf + 9L̄ n )( 1 + 2pδ1 ) , and for k ≥ 0 define
Ψk := Z̃k + Yk +Wk + 4L1δη ∥e k∥2 + 28L1(1−δ)δηn · 1 n n∑ τ=1 ∥ekτ∥2
+ 56(1−δ)ηδ2δ1L1 ∥h k −∇f(wk)∥2 + 504(1−δ)ηδ2δ1nL1 · 1 n n∑ τ=1 ∥hkτ −∇f (τ)(wk)∥2.
Then we can get the linear convergence of Ψk in Theorem 3.7. Theorem 3.7. Let Assumption 2.1 , Assumption 3.1 and Assumption 3.2 hold. If L1 ≥ max{Lf , 3µη}, θ1 + 2θ2 ≤ 1, and θ2 ≥ L33L1 , then we have
E [ Ψk ] ≤ ( 1−min ( µ
µ+6θ1L1 , θ1 + θ2 − θ2 q , p(1− q), δ 6 , δ1 6
))k Ψ0, ∀k ≥ 0.
From Theorems 3.6 and 3.7, by choosing the parameters appropriately, we can obtain the iteration complexity for ECLK. Theorem 3.8. Let Assumption 3.1 and Assumption 3.2 hold. Let L1 = max (L4, Lf , 3µη), θ2 = L4 3max{Lf ,L4} , and
θ1 =  min (√ µ L4pθ2, θ2 ) if Lf ≤ L4p min (√ µ Lf , p3 ) otherwise .
(i) Let L4 = L2. Then with some q ∈ [ 23 , 1), we have E[Φ k] ≤ ϵΦ0 for k ≥ O ((
1 δ + 1 δ1 + 1p + √ Lf µ + √ L2 µp ) log 1ϵ ) .
In particular, if p ≤ O(δ1), then the iteration complexity becomes k ≥ O ((
1 δ + 1 p + √ Lf µ + √ L µpn + 1 δ √ (1−δ)L̄ µp + √ (1−δ)L µpδ ) log 1ϵ ) . (11)
(ii) Let L4 = L3. If Assumption 2.1 holds, then for some q ∈ [ 23 , 1), we have E[Ψ k] ≤ ϵΨ0 for k ≥ O ((
1 δ + 1 δ1 + 1p + √ Lf µ + √ L3 µp ) log 1ϵ ) . If p ≤ O(δ1), the iteration complexity becomes
k ≥ O ((
1 δ + 1 p + √ Lf µ + √ L µpn + 1 δ √ (1−δ)Lf µp + √ (1−δ)L µpδn ) log 1ϵ ) . (12)
From Theorem 3.8, it is easy to see that the optimal p for ECLK is Θ(δ1).
Comparison to ADIANA. ADIANA [Li et al., 2020] is an accelerated and compressed distributed method with any unbiased compressor. The iteration complexity of ADIANA is O ( ω ( 1 + √ L̄ nµ ) log 1ϵ ) when n ≤ ω, and O (( ω + √ L̄ µ + √√ ω n ωL̄ µ ) log 1ϵ ) when n > ω.
If we choose Q and Q1 in ECLK to be the contraction compressor 1ω+1 Q̃ where Q̃ is any unbiased compressor, then δ = δ1 = 1ω+1 , and thus the complexity in (12) becomes
O (( ω + √
Lf µ + √ (ω+1)L µn + (ω + 1) √ ωLf µ + √ ω(ω+1)L µn ) log 1ϵ ) ,
for p = δ1. In this case, the dependency of ω of the iteration complexity of ADIANA is better than that of ECLK. However, the full gradients are computed by all nodes at each iteration in ADIANA, which could be slower than the communication when m is very large. Furthermore, the contraction compressor could be more efficient than the unbiased compressor in practice, i.e., for the same level of compression, δ could be larger than 1/(ω+1). This efficiency of the contraction compressor is the motivation to study the error compensated methods, and in numerical experiments, ECLK is comparable to ADIANA.

heading: 4 Experiments

text:
In this section, we experimentally study the performance of error compensated L-Katyusha (ECLK) used with several contraction compressors on the logistic regression problem for binary classification,
x 7→ log ( 1 + exp(−yiATi x) ) + λ2 ∥x∥ 2,
where {Ai, yi} are the training data points. We use Python 3.7 to perform the experiments. We use the datasets a5a, a9a, w6a, w8a, phishing, and mushrooms from the LIBSVM library [Chang and Lin, 2011]. The regularization parameter was set to λ = 10−3. The number of nodes in our experiments is n = 20, and the optimal solution is obtained by running the uncompressed L-Katyusha for 105 iterations. More experiments can be found in the appendix.
Compressors. We use three contraction compressors: the TopK compressor with K = 1, or the compressor 1ω+1 Q̃, where Q̃ is either the unbiased random dithering compressor with s = √ d levels [Alistarh et al., 2017] or the natural compressor [Horváth et al., 2019b]. For the Top1 compressor, the number of communicated bits for the compressed vector is 64 + ⌈log d⌉, and δ = 1/d. For the random dithering compressor with s = √ d, the number of communicated bits for the compressed vector is 2.8d + 64, and ω = 1 [Alistarh et al., 2017] . For the natural compressor, the number of communicated bits for the compressed vector is 12d, and ω = 1/8 [Horváth et al., 2019b].
Parameter setting. In all the experiments, we search for the optimal stepsize for all tested algorithms. In particular, we use the parameter setting in Theorem 3.8 (i) for ECLK. From Theorem 3.8 (i), we know that we can set values for all parameters if we know values of µ, δ, δ1, p, and Lipschitz constants. For the tested problem, µ = λ. Q andQ1 are chosen to be the same contraction compressor for ECLK, which implies that δ = δ1, and the lower bound for δ can be obtained easily for our used compressors. We set p = δ for ECLK except in Section 4.4. We calculate the theoretical Lf , L̄, and L as Lthf , L̄
th, and Lth, respectively. Then we choose Lf = t ·Lthf , L̄ = t · L̄th, and L = t ·Lth, and search for the best t in the set t ∈ {10−k | k = 0, 1, 2, ...}. We set p = δ for EC-LSVRG-DIANA [Gorbunov et al., 2020]. EC-LSVRG-DIANA requires the use of an additional unbiased compressor; for this we make use of random dithering.

heading: 4.1 Top1 vs random dithering vs natural compression vs no compression

text: First, we compare the uncompressed L-Katyusha method with ECLK with three contraction compressors: Top1, random dithering, and natural compression; see Figure 1. ECLK is orders of magnitude better in terms of communication complexity.

heading: 4.2 Comparison with EC-LSVRG-DIANA and ECGD

text:
Next, we compare ECLK with EC-LSVRG-DIANA [Gorbunov et al., 2020] and error compensated GD (ECGD) using the Top1, random dithering, and natural compressor. Note that ECGD is a special
case of error compensated SGD [Stich et al., 2018] with m = 1, where the full gradient ∇f (τ)(xk) is calculated on each node. Figures 2 and 3 show that ECGD can only converge to a neighborhood of the optimal solution, and that ECLK is considerably faster than EC-LSVRG-DIANA.

heading: 4.3 Comparison with ADIANA

text: Let us denote by ECLK-F the special case of ECLK with m = 1, i.e., the full gradient ∇f (τ)(xk) is calculated on each node. We compare ECLK-F with the accelerated variant of DIANA, called ADIANA [Li et al., 2020], for six data sets. For ADIANA we use two unbiased compressors: random dithering and natural compression. Figure 4 shows that in terms of communication complexity, ECLK-F is comparable to ADIANA, and can be better than ADIANA in some cases.

heading: 4.4 Impact of the update frequency of the reference point

text:
Finally, we test the impact of the update frequency of the reference point p for ECLK with Top1 compressor; see Figure 5. We choose five values for p: δ/3, δ, 3δ, 9δ, and 1. Figure 5 shows that the performance of p = δ is usually better than p = δ/3. As we increase p from p = δ, the performance of ECLK could be improved. However, if p is too large, the performance of ECLK is no better than p = δ, generally.
Acknowledgments and Disclosure of Funding
Xun Qian and Peter Richtárik acknowledge funding by the KAUST Baseline Research Funding Scheme, the Extreme Computing Research Center at KAUST, and administrative support from the Visual Computing Center at KAUST. Tong Zhang acknowledges further funding by GRF 16201320.

title: Error Compensated Distributed SGD can be Accelerated