summaries: The paper proposes a RL-based memory management policy for CIL problem. They have two-step formulation of policy, which first determines how to allocate the memory to old and new tasks, then determines how many samples to store per each class within the task. A standard RL framework of policy gradient method is used to optimize their policy. Experimental results how that their RMM can further improve the recent state-of-the-art methods, such as LUCIR or PODNet.

summaries: The paper proposes a new memory sampling strategy which replaces random/herding. The strategy consists of two parts: first level determining the distribution of #samples of each class in memory and second level determining samples to be selected for every class. This is learnt via RL policy. The sampler is trained by emulating a pseudo-CL problem with the data available in the pretraining phase-- where there are an equal number of tasks made as expected in the CL setup to enable transfer. Given a sampling configuration, a CL method trains the model and the performance on the pseudo-CL test set is given as reward to the RL algorithm. This trains the policy components, which optimize sample size and samples per class and train CL. Then, the best policy is used to create the memory which is used to train the actual CL problem with state-of-the-art continual learning approaches. This memory selection achieves better performance than previously used memories across CIFAR100, Imagenet100 and Imagenet1000 datasets.

summaries: This work addresses the problem of memory management in Class Incremental Learning (CLI). In this setup, models store exemplars from old classes and must decide what exemplars to drop to make space to new memories. The authors propose a hierarchical reinforcement learning approach where an agent first chooses how much of the old memory to release to make space for new samples and then it chooses how much of the new space allocate to high-entropy samples and low-entropy samples (they divide new classes in two groups). Experiments show that the the proposed method attains better performance than POD-AANets and LUCIR on CIFAR and ImageNet. In the supplementary material they show that the proposed memory management system also improves the performance of already-existing systems. Additional studies show how policies transfer between datasets, the impact of hierarchical RL, and how old and new memories balance over time.

summaries: A common approach in class-incremental learning is to retain a fixed set of examples of the old classes to help avoid forgetting. The paper presents an approach to dynamically retain exemplars for the class-incremental learning problem. Reinforcement learning is used for dynamic memory management.

abstractText: Class-Incremental Learning (CIL) [40] trains classifiers under a strict memory budget: in each incremental phase, learning is done for new data, most of which is abandoned to free space for the next phase. The preserved data are exemplars used for replaying. However, existing methods use a static and ad hoc strategy for memory allocation, which is often sub-optimal. In this work, we propose a dynamic memory management strategy that is optimized for the incremental phases and different object classes. We call our method reinforced memory management (RMM), leveraging reinforcement learning. RMM training is not naturally compatible with CIL as the past, and future data are strictly non-accessible during the incremental phases. We solve this by training the policy function of RMM on pseudo CIL tasks, e.g., the tasks built on the data of the 0-th phase, and then applying it to target tasks. RMM propagates two levels of actions: Level-1 determines how to split the memory between old and new classes, and Level-2 allocates memory for each specific class. In essence, it is an optimizable and general method for memory management that can be used in any replaying-based CIL method. For evaluation, we plug RMM into two top-performing baselines (LUCIR+AANets and POD+AANets [30]) and conduct experiments on three benchmarks (CIFAR-100, ImageNet-Subset, and ImageNet-Full). Our results show clear improvements, e.g., boosting POD+AANets by 3.6%, 4.4%, and 1.9% in the 25-Phase settings of the above benchmarks, respectively. The code is available at https://class-il.mpi-inf.mpg.de/rmm/.

authors:
Davide Abati
Jakub Tomczak
Tijmen Blankevoort
Simone Calderara
Rita Cucchiara
Babak Ehteshami Bejnordi

title: Conditional channel gated networks for task-aware continual learning

venue: In CVPR,

authors:
Maruan Al-Shedivat
Trapit Bansal
Yura Burda
Ilya Sutskever
Igor Mordatch
Pieter Abbeel

title: Continuous adaptation via meta-learning in nonstationary and competitive environments

venue: In ICLR,

authors:
Rahaf Aljundi
Punarjay Chakravarty
Tinne Tuytelaars

title: Expert gate: Lifelong learning with a network of experts

authors:
Eden Belouadah
Adrian Popescu

title: Il2m: Class incremental learning with dual memory

title: Pattern recognition and machine learning

venue: springer,

authors:
Francisco M. Castro
Manuel J. Marín-Jiménez
Nicolás Guil
Cordelia Schmid
Karteek Alahari

title: End-to-end incremental learning

venue: In ECCV,

authors:
Arslan Chaudhry
Marc’Aurelio Ranzato
Marcus Rohrbach
Mohamed Elhoseiny

title: Efficient lifelong learning with a-gem

authors:
Tianqi Chen
Ian J. Goodfellow
Jonathon Shlens

title: Net2net: Accelerating learning via knowledge transfer

venue: In Yoshua Bengio and Yann LeCun, editors,

authors:
Zhiyuan Chen
Bing Liu

title: Lifelong machine learning

venue: Synthesis Lectures on Artificial Intelligence and Machine Learning,

authors:
Guy Davidson
Michael C Mozer

title: Sequential mastery of multiple visual tasks: Networks naturally learn to learn and forget to forget

authors:
Matthias De Lange
Rahaf Aljundi
Marc Masana
Sarah Parisot
Xu Jia
Ales Leonardis
Gregory Slabaugh
Tinne Tuytelaars

title: Continual learning: A comparative study on how to defy forgetting in classification

venue: tasks. arXiv,

authors:
Matthias De Lange
Rahaf Aljundi
Marc Masana
Sarah Parisot
Xu Jia
Aleš Leonardis
Gregory Slabaugh
Tinne Tuytelaars

title: A continual learning survey: Defying forgetting in classification

authors:
Arthur Douillard
Matthieu Cord
Charles Ollion
Thomas Robert
Eduardo Valle

title: Podnet: Pooled outputs distillation for small-tasks incremental learning

authors:
Qiang Gao
Zhipeng Luo
Diego Klabjan

title: Efficient architecture search for continual learning

venue: arXiv preprint arXiv:2006.04027,

title: Reinforcement learning: An overview

venue: In Proceedings European Symposium on Intelligent Techniques (ESIT-00), Aachen,

title: Monte carlo methods

venue: Springer Science & Business Media,

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

authors:
Saihui Hou
Xinyu Pan
Chen Change Loy
Zilei Wang
Dahua Lin

title: Learning a unified classifier incrementally via rebalancing

authors:
Wenpeng Hu
Zhou Lin
Bing Liu
Chongyang Tao
Zhengwei Tao
Jinwen Ma
Dongyan Zhao
Rui Yan

title: Overcoming catastrophic forgetting for continual learning via model adaptation

authors:
Xinting Hu
Kaihua Tang
Chunyan Miao
Xian-Sheng Hua
Hanwang Zhang

title: Distilling causal effect of data in class-incremental learning

authors:
Shenyang Huang
Vincent François-Lavet
Guillaume Rabusseau

title: Neural architecture search for class-incremental learning

venue: arXiv preprint arXiv:1909.06686,

authors:
Ahmet Iscen
Jeffrey Zhang
Svetlana Lazebnik
Cordelia Schmid

title: Memory-efficient incremental learning through feature adaptation

authors:
Wouter Kool
Herke van Hoof
Max Welling

title: Buy 4 reinforce samples, get a baseline for free

venue: In ICLR Workshops,

authors:
Alex Krizhevsky
Geoffrey Hinton

title: Learning multiple layers of features from tiny images

venue: Technical report, Citeseer,

authors:
Anna Kukleva
Hilde Kuehne
Bernt Schiele

title: Generalized and incremental few-shot learning by explicit learning and calibration without forgetting

venue: In ICCV,

authors:
Yingying Li
Xin Chen
Na Li

title: Online optimal control with linear dynamics and predictions: Algorithms and regret analysis

venue: In NeurIPS,

authors:
Yingying Li
Na Li

title: Online learning for markov decision processes in nonstationary environments: A dynamic regret analysis

venue: In ACC,

authors:
Yingying Li
Aoxiao Zhong
Guannan Qu
Na Li

title: Online markov decision processes with time-varying transition probabilities and rewards

venue: In ICML workshop on Real-world Sequential Decision Making,

authors:
Zhizhong Li
Derek Hoiem

title: Learning without forgetting

venue: IEEE Transactions on Pattern Analysis and Machine Intelligence,

authors:
Yaoyao Liu
Bernt Schiele
Qianru Sun

title: Adaptive aggregation networks for classincremental learning

authors:
Yaoyao Liu
Yuting Su
An-An Liu
Bernt Schiele
Qianru Sun

title: Mnemonics training: Multi-class incremental learning without forgetting

authors:
David Lopez-Paz
Marc’Aurelio Ranzato

title: Gradient episodic memory for continual learning

venue: In NIPS,

authors:
Michael McCloskey
Neal J Cohen

title: Catastrophic interference in connectionist networks: The sequential learning problem

venue: In Psychology of Learning and Motivation,

authors:
K. McRae
P. Hetherington

title: Catastrophic interference is eliminated in pre-trained networks

venue: In CogSci,

authors:
Ameya Prabhu
Philip HS Torr
Puneet K Dokania

title: Gdumb: A simple approach that questions our progress in continual learning

authors:
Jathushan Rajasegaran
Munawar Hayat
Salman Khan
Fahad Shahbaz Khan
Ling Shao

title: Random path selection for incremental learning

venue: NeurIPS,

authors:
Jathushan Rajasegaran
Salman Khan
Munawar Hayat
Fahad Shahbaz Khan
Mubarak Shah

title: itaml: An incremental task-agnostic meta-learning approach

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

title: Sequence level training with recurrent neural networks

title: Connectionist models of recognition memory: Constraints imposed by learning and forgetting functions

venue: Psychological Review,

authors:
Sylvestre-Alvise Rebuffi
Alexander Kolesnikov
Georg Sperl
Christoph H Lampert

title: iCaRL: Incremental classifier and representation learning

authors:
Mengye Ren
Renjie Liao
Ethan Fetaya
Richard S Zemel

title: Incremental few-shot learning with attention attractor networks

authors:
Steven J Rennie
Etienne Marcheret
Youssef Mroueh
Jerret Ross
Vaibhava Goel

title: Selfcritical sequence training for image captioning

authors:
Matthew Riemer
Ignacio Cases
Robert Ajemian
Miao Liu
Irina Rish
Yuhai Tu
Gerald Tesauro

title: Learning to learn without forgetting by maximizing transfer and minimizing interference

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:
Shiqi Shen
Yong Cheng
Zhongjun He
Wei He
Hua Wu
Maosong Sun
Yang Liu

title: Minimum risk training for neural machine translation

authors:
Hanul Shin
Jung Kwon Lee
Jaehong Kim
Jiwon Kim

title: Continual learning with deep generative replay

authors:
Christian Simon
Piotr Koniusz
Mehrtash Harandi

title: On learning the geodesic path for incremental learning

authors:
Xiaoyu Tao
Xinyuan Chang
Xiaopeng Hong
Xing Wei
Yihong Gong

title: Topologypreserving class-incremental learning

authors:
Tom Veniat
Ludovic Denoyer
Marc’Aurelio Ranzato

title: Efficient continual learning with modular networks and task-driven priors

title: Simple statistical gradient-following algorithms for connectionist reinforcement learning

venue: Machine learning,

authors:
Yue Wu
Yinpeng Chen
Lijuan Wang
Yuancheng Ye
Zicheng Liu
Yandong Guo
Yun Fu

title: Large scale incremental learning

authors:
Ziyang Wu
Christina Baek
Chong You
Yi Ma

title: Incremental learning via rate reduction

authors:
Ju Xu
Zhanxing Zhu

title: Reinforced continual learning

authors:
Lu Yu
Bartlomiej Twardowski
Xialei Liu
Luis Herranz
Kai Wang
Yongmei Cheng
Shangling Jui
Joost van de Weijer

title: Semantic drift compensation for class-incremental learning

authors:
Chi Zhang
Nan Song
Guosheng Lin
Yun Zheng
Pan Pan
Yinghui Xu

title: Few-shot incremental learning with continually evolved classifiers

authors:
Bowen Zhao
Xi Xiao
Guojun Gan
Bin Zhang
Shu-Tao Xia

title: Maintaining discrimination and fairness in class incremental learning

authors:
Fei Zhu
Xu-Yao Zhang
Chuang Wang
Fei Yin
Cheng-Lin Liu

title: Prototype augmentation and self-supervision for incremental learning

authors:
Barret Zoph
Quoc V. Le

title: Neural architecture search with reinforcement learning

heading: 1 Introduction

text:
Ideally, AI systems should be adaptive to ever-changing environments—where the data are continuously observed by sensors. Their models should be capable of learning new concepts from data while maintaining the ability to recognize previous ones. In practice, the systems often have constrained memory budgets because of which most of the historical data have to be abandoned [20]. However, deep-learning-based AI systems, when continuously updated using new data and limited historical data, often suffer from catastrophic forgetting, as the updates can override knowledge acquired from previous data [33, 34, 39].
To encourage research on the forgetting problem, Rebuffi et al. [40] defined a standard protocol of class-incremental learning (CIL) for image classification, where the training data of different object classes come in phases. In each phase, the classifier is evaluated on all classes observed so far. As the total memory size is limited [40], CIL systems abandon the majority of the data and only preserve a small number of exemplars, e.g., 20 exemplars per class, which will be used for replaying in subsequent phases. Replaying usually happens for multiple epochs [13, 18, 30, 40], so both the old
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
class exemplars and new class data need to be stored in the limited memory. Existing CIL methods allocate memory between the old and new classes in an arbitrary and static fashion, e.g., 20 per old class vs. 1, 300 per new class for the ImageNet-Full dataset. This causes a serious imbalance between the old and new classes and can exacerbate the problem of catastrophic forgetting.
To address this, we propose to learn an optimal memory management policy for each incremental phase with continuously reinforced model performance and call our method reinforced memory management (RMM). Detailed actions include 1) allocating the memory between the existing (old) and the coming (new) data for each phase, and 2) specifying the memory for each old class according to its recognition difficulty before abandoning any of its data. To this end, we leverage reinforcement learning [26–28, 51, 59] and design a new policy function to contain two sub-functions that propagate two levels of actions in a hierarchical way. Level-1 function determines how to split memory between the old and new data. Its output action is then inputted into the Level-2 function to determine how to allocate memory for each old class. The overall objective of the function is to maximize the cumulative evaluation accuracy across all incremental phases. However, this is not naturally compatible with the standard protocol of CIL [40] where neither past nor future data are accessible for evaluation. To tackle this issue, we propose to pre-train the function on pseudo CIL tasks and then adopt it in the learning process of our target task. In principle, we can build such pseudo tasks using any available categorical data, e.g., the data in the 0-th phase of the target CIL task or the data from another dataset. Even though this is a non-stationary reinforcement learning problem, we can regard the pseudo and target CIL tasks as a sequence of stationary tasks and train the policy function to exploit the dependencies between these consecutive tasks. Such continuous adaptation in non-stationary environments is feasible based on the empirical analysis given in [2].
Technically, we propose the following method to guarantee the transferability of policy functions between pseudo and target CIL tasks. We take a Level-1 action based on the ratio of the number of new classes to the total number of classes observed so far. A lower (higher) ratio will result in weakening the stability (plasticity) of the classification model. Then, we take a Level-2 action for each individual class conditioned on both the Level-1 action and the training entropy of that class. A higher entropy denotes a more difficult class, leading to more memory allocated to the class. For evaluation, we conduct extensive CIL experiments by plugging RMM into two top-performing methods (LUCIR+AANets, POD+AANets) and testing them on three benchmarks (CIFAR-100, ImageNet-Subset, and ImageNet-Full). Our results show the clear and consistent superiority of RMM, e.g., it boosts the state-of-the-art POD+AANets by 3.6%, 4.4%, and 1.9% in the 25-Phase settings of the above benchmarks, respectively.
Our technical contribution is three-fold. 1) A hierarchical reinforcement learning algorithm called RMM to manage the memory in a way that can be conveniently modified through incremental phases
and for different classes. 2) A pseudo task generation strategy that requires only in-domain available data (small-scale) or cross-domain datasets (large-scale), relieving the data incompatibility between reinforcement learning and class-incremental learning. 3) Extensive experiments, visualization, and interpretation for RMM in three CIL benchmarks and using two top models as baselines.

heading: 2 Related Work

text:
Incremental Learning [22, 36, 48, 53, 58] continuously updates the model using data coming in a sequence of phases. Similar tasks are also referred to as continual learning [12, 32] and lifelong learning [3, 9]. Recent papers are either task-incremental learning—each phase corresponds to a task (dataset) that contains new data of all seen classes [7, 10, 19, 29, 43, 47, 57], or classincremental learning (CIL)—each phase contains data of a new set of classes, i.e., classes are unseen [4, 6, 18, 25, 31, 37, 40, 41, 49, 52, 55–57]. This paper is concerned with CIL. The key challenge of CIL is the forgetting problem—older classes are forgotten in later phases. Existing methods tackling this can be divided into three categories: memory-based, regularization-based, and network-architecture-based [11, 35]. Memory-based methods preserved a small subset of the old class data (exemplars) to replay the model on them (together with the new class data), in order to relieve the forgetting of the old classes. Some work [18, 40] proposed heuristic strategies to select more representative exemplars from the old class data, and others [31, 47] tried to generate exemplars in optimizable frameworks. None of them changed the allocation of memory for different classes, i.e., all used an arbitrary and static scheme for memory allocation. Regularization-based methods introduce regularization terms in the loss function to consolidate previous knowledge when training the model on new data. The key idea is to enforce predicted label logits [29, 40], features maps [13, 18], or the topology in the feature space [49] of the new model to be close to that of the previous model. Network-architecture-based methods aim to design “incremental network architectures”. Some work [45, 54] gradually extended the network capacity for new data, while others proposed to freeze partial network parameters [1, 30] to preserve the knowledge of the old classes.
Reinforcement Learning defines an agent that needs to decide its actions in an unknown environment by maximizing the expected cumulative reward. It has been widely applied to many optimization problems, e.g., neural architecture search [54, 59] and neural machine translation [38, 46]. Reinforcement learning has also been introduced to solve incremental learning problems. Xu et al. [54] proposed to increase convolution filters once a new task arrives and optimize the increased number by reinforcement learning. Gao et al. [14] proposed an improved version that makes the minimal expansion of the network, reducing memory and computing overheads. Veniat et al. [50] introduced a modular architecture, where each module represents a different atomic skill, and used the REINFORCE algorithm [51] to optimize it. Huang et al. [21] combined reinforcement learning with Net2Net [8] and designed a NAS-based CIL method. In our work, we also use the REINFORCE algorithm [51], but differ in three aspects. First, we are the first to optimize memory allocation for CIL in a reinforced way. Second, we learn the policy functions on generated pseudo CIL tasks, where we can access both past, and future data (for each incremental phase) and thus are able to compute the cross-phase (long-term) rewards. In contrast, the related work [14, 54] could use only current-phase data to estimate a short-term reward. Third, our reinforcement learning has a hierarchical structure that specially fits the nature of the data stream in the CIL settings.

heading: 3 Preliminaries

text:
Class-Incremental Learning (CIL) usually assumes (N+1) learning phases: an initial phase and N incremental phases during which the number of classes gradually increases till the maximum [13, 18, 20, 31]. We assume that total memoryM is bounded and fixed for all incremental phases [40].M is used to store the exemplars and new coming data as both kinds of data need to be loaded repeatedly during training epochs. In the initial (0-th) phase, data D0, containing the training samples of C0 classes, are used to learn the initial classification model Θ0. In the i-th incremental phase, we splitM into two dynamic partitions: the exemplar memoryMold and new data memoryMnew. We select Et as representative samples of the data seen in the t-th phase, and denote total exemplars E0 ∼ Ei−1 shortly as E0:i−1. We save E0:i−1 intoMold and freeMnew. Then, we observe new data that contain Ci new classes. We randomly load new data intoMnew untilMnew is full, and all the other new data
are discarded. We denote the loaded new data as Di. Then, we initialize Θi with Θi−1, and train it using E0:i−1 ∪ Di. The resulting model Θi will be evaluated with a test set containing all classes observed so far. We repeat this training and testing, and report the average accuracy across all phases.
Reinforcement Learning (RL) aims to learn an optimal policy function π for an agent interacting in an unknown environment [51, 54, 59]. In the CIL scenario, in each incremental phase, the agent observes the current state si from the environment, and then takes an action ai (how to allocate memory) according to the policy function π(ai|si). Subsequently, the environment is updated to a new state si+1 and the reward ri is calculated to optimize the parameters of π(ai|si) through back-propagation. Specifically, the learning objective of π(ai|si) is to maximize the expected cumulative reward Ri = ∑∞ t=i γ
t−irt, where γ ∈ [0, 1) is a discounting factor that determines the weights of future rewards. Please note that in our case, the (N+1)-phase CIL task is a finite horizon problem [15, 59], so we remove the discounting factor and use R = ∑N t=0 rt, which is actually the cumulative validation accuracy of all training CIL tasks. In Section 4, we discuss the proposed RL algorithm for memory allocation and how to generate pseudo tasks for training its policy function.

heading: 4 Reinforced Memory Management (RMM)

text: Our RMM approach learns policy functions that propagate two levels of actions in a hierarchical way, specially designed for CIL. As illustrated in Figure 1 (b), Level-1 determines the memory split between exemplars and new data, and Level-2 allocates the memory for each individual class. We motivate and introduce the formulation of RMM, including the definitions of states, actions, rewards, and hierarchical policy functions in Section 4.1. In Section 4.2, we detail the steps of creating pseudo CIL tasks on which we learn the policy functions. In Section 4.3, we summarize the algorithm.

heading: 4.1 Formulation

text:
In the i-th incremental phase CIL, we manage the memory for two kinds of data: exemplars E0:i−1 and new data Di. For the former, we have access to their images and labels so we can allocate a different memory size to a different class, e.g., based on its recognition difficulty. For the latter, we do not have such access before loading the data (otherwise, causing a violation to the CIL protocol), so we are only able to learn a total memory size, i.e., the memory size for all new classes (and then split it evenly for each individual class). Therefore, the memory management in CIL settings is inherently hierarchical: 1) coarse memory allocation between exemplars and new data; and then 2) fine-grained memory allocation among specific classes. To this end, we modify the standard reinforcement learning into a hierarchical structure.
As illustrated in Figure 2 (a), in the i-th incremental phase of CIL (i.e., the environment), the argent receives a state value si. Level-1 policy πη takes si as the input to produce an action a [1] i ∼ πη(si). a [1] i determines how to split memory between the exemplars and new data. After that, Level-2 policy πφ takes si and a [1] i as inputs to produce the second action a [2] i ∼ πφ(si, a [1] i ) that distributes the exemplar memory for each individual class.
States, defined for our CIL settings, should have two properties. 1) Being transferable between CIL tasks, e.g., from a small-scale CIL task including 50 classes (in total) to a large one including 100 classes. The reason is that we need to transfer the policy functions learned from pseudo CIL tasks (defined in Section 4.2) to the target task. The states, the inputs of policy functions, should also be transferable. 2) Being distinct in each incremental phase. This is to enable the state variable to represent a specific forgetting or data imbalance degree at each different learning phase of the CIL model. To fulfill these properties, we formulate the state in the i-th phase as si = ( Ci∑i−1 t=0 Ct , |Mold||M| ) , where Ci denotes the number of classes in Di,Mold denotes the memory allocated to exemplars E0:i−1, andM is the total memory.
Level-1 Actions. In the 1-st incremental phase, our Level-1 policy function produces an action to allocate the memory for exemplars E0 and new data D1. We denote this action as a[1]1 and assign its value with the ratio of the number of the exemplars |E0| to the memory size |M|, so we have a [1] 1 ∈ (0, 1). In the i-th phase (i ≥ 2), the definition of a [1] i is different to a [1] 1 as it is a relative change over a[1]i−1. Specifically, a [1] i is the ratio of increased (if its value is positive) or decreased (if
negative) memory size ofMold compared to the (i-1)-th phase. Using this definition aims for smooth and continuous memory management. In the formulation, the memory sizes of exemplars E0:i−1 and new data Di are, respectively,
|Mold| = |E0:i−1| = i∑ t=1 a [1] t |M|, |Mnew| = |Di| =
( 1−
i∑ t=1 a [1] t
) |M|. (1)
We set a constrain a[1]i ∈ [−0.1, 0.1] for i ≥ 2. Otherwise, if a [1] i is too big, there are not enough exemplars to fill the memory, as most old-class data has been abandoned. If a[1]i is too small, many exemplars will be permanently deleted in this phase, making it hard or even impossible to adjust Mold back to a high value in the future phases. If ∑i t=1 a [1] t > 1,Mnew will be negative. So, we
force ∑i t=1 a [1] t ≤ 1 by rejection sampling [5], i.e., using πη to output another action until it is feasible to execute. Note that this situation rarely happens in real training, because whenMnew becomes very low, πη tends to produce an action to increase it.
Level-2 Actions. Here, we elaborate on how to get class-specific memory allocation. In the (i−1)-th phase, we split the classes for Di−1 into two groups evenly according to training entropy values: classes with higher values (difficult classes) are in one group and the rest in the other group. Therefore, Level-2 action a[2]i ∈ (0, 1) determines how to split memories between harder and easier classes. During initial experiments, we observed that using two groups already yields improved results and using more groups causes a decrease.
Let MAj and MBj denote the memory allocated for the high-entropy and low-entropy groups, respectively, in the j-th phase (j ≤ i):
|MAj | = a [2] j+1|Ej | = a [2] j+1Cj∑i t=1 Ct |Mold|, |MBj | = (1− a [2] j+1)|Ej | = (1− a[2]j+1)Cj∑i t=1 Ct |Mold|. (2)
Then, we allocate memory evenly to the classes within the group, e.g., if the high-entropy group has 10 classes, each class will have a memory size of 110 |M A j |.
Rewards. The objective of CIL is that the trained model (in any phase) should be efficient to recognize all classes seen so far. It is intuitive and convenient to use the validation accuracy as the reward in each phase. In the i-th phase, the objective of RMM is to maximize the expected cumulative reward, i.e., R = ∑N i=0 ri, where ri denotes the validation accuracy in the i-th phase.
4.2 Optimization
In the CIL protocol, it is impossible to see past or future data in any incremental phase. It is thus not intuitive how to compute cumulative rewards till the last phase. We propose to solve the issue by generating pseudo CIL tasks (where all data are accessible).
Pseudo CIL Tasks should meet two requirements: 1) their training and validation data are fully accessible for computing cumulative rewards, and 2) they have the same format (e.g., the same number of phases) of the target CIL task. Data Sources: For requirement 1, an intuitive solution is to use D0 (available in the 0-th phase). Based on the CIL protocol [13, 18, 20, 30], D0 contains half of the classes of the whole dataset, e.g., 50 classes on CIFAR-100, which supplies enough data to build downsized CIL tasks. When building the tasks, we randomly choose 10% training samples of each
class (from D0) to compose a pseudo validation set (note that we are not allowed to use the original validation set in training). When aiming for larger-scale data in CIL, we can leverage smaller datasets. For example, the pseudo tasks for ImageNet-Subset can be built on the data of CIFAR-100. This is also meaningful to evaluate the transferability of RMM policy functions (discussed in the Ablation Study). Task Generation Protocol is based on requirement 2. If using another dataset, we simply follow its original CIL protocol. If using the data accessed in the 0-th phase (i.e., D0), we can reduce the number of classes (in each phase) by half. For example, for CIFAR-100, we use 50-class D0 to generate a 5-phase pseudo CIL task as follows: loading 25 classes in the 0-th phase, and after that, five classes per phase. To generate another pseudo task, we simply change the order of classes.
Training. We elaborate the steps of learning Level-1 policy πη and Level-2 policy πφ in the following. The goal is to optimize the parameters η and φ by maximizing the expected cumulative reward J(η, φ). We denote any pseudo CIL task and its cumulative reward as T and R, respectively, and have,
J(η, φ) = ET Eπη,πφ [R]. (3)
Policy Gradient Estimation. According to the policy gradient theorem [51], we can compute the gradients for J(η, φ) as follows,
∇η,φJ(η, φ) = ET [ N∑ i=1 Eπη,πφ [∇η,φ log(πη(a [1] i |si)πφ(a [2] i |si, a [1] i ))R] ] . (4)
Following the REINFORCE algorithm [51], we replace the expectations ET [·] and Eπη,πφ [·] with sample averages using the Monte Carlo method [16]. Specifically, in each epoch, we create K pseudo tasks and run each task for Z times, as shown in Figure 3. Thus we can derive the empirical approximation of ∇η,φJ(η, φ) as,
∇η,φJ(η, φ) = 1
ZK K∑ k=1 Z∑ z=1 N∑ i=1 ∇η,φ log(πη(a[1]i |si)πφ(a [2] i |si, a [1] i ))(R k z − b), (5)
where Rkz denotes the z-th reward for the k-th pseudo task Tk, and b denotes the baseline function— the moving average of previous rewards. Using this baseline function is a common trick in RL to reduce the variance of estimated policy gradients [23, 42, 59].
Updating Parameters. We update η and φ in each epoch according to the gradient ascent rule [54, 59]:
η := η + β1∇ηJ(η, φ), φ := φ+ β2∇φJ(η, φ), (6) where β1 and β2 are the learning rates. We iterate this update for m epochs in total.
4.3 Algorithm
Algorithm 1 Learning policy functions in RMM 1: Input: Data D for generating pseudo CIL tasks. 2: Output: Policy functions πη , πφ. 3: Initialize η and φ; 4: for m epochs do 5: for k in 1, ...,K do 6: Create a new pseudo task Tk using D; 7: for z in 1, ..., Z do 8: Initialize classification model Θ0; 9: for i in 0, ..., N do
10: if i ≥ 1 do 11: Observe si and produce a [1] i ∼ πη(si); 12: AllocateMold andMnew using Eq. 1; 13: Produce a[2]i ∼ πφ(a [1] i , si); 14: Allocate {MAj }ij=0 and {MBj }ij=0 using Eq. 2; 15: Update E0:i−1 using herding [40]; 16: Save E0:i−1 inMold and freeMnew; 17: Observe new data and load Di intoMnew randomly; 18: Initialize Θi with Θi−1 and train it using E0:i−1 ∪Di; 19: Compute validation accuracy ri; 20: Compute Rkz = ∑N i=0 ri and update b; 21: Compute∇η,φJ(η, φ) using Eq. 5; 22: Update η and φ using Eq. 6.
Algorithm 1 summarizes the overall training steps of the proposed RMM. There are four loops in the algorithm: 1) we train the RMM agent for m epochs; 2) we create K pseudo CIL tasks in each epoch; 3) we run each pseudo CIL task for Z times; and 4) there are N+1 learning phases each time. Specifically, Line 3 initializes the parameters of policy functions. Line 6 creates the k-th pseudo CIL task. Line 8 initializes the classification model. Lines 10-16 allocate the memory according to the actions produced by RMM policy. Line 17 loads new data. Lines 18-19 train the classification model and compute the accuracy. Line 20 estimates the z-th cumulative reward. Lines 21-22 compute the gradients and update policy functions.

heading: 5 Experiments

text: We evaluate the proposed RMM method on three CIL benchmarks: CIFAR-100 [24], ImageNet-Subset [40], and ImageNet-Full [44], and use two top performing methods LUCIR+AANets and POD+AANets [30] as baselines. Below we introduce the datasets and implementation details (Section 5.1), followed by the experimental results and analyses (Section 5.2).

heading: 5.1 Datasets and Implementation Details

text:
Datasets. We use three benchmarks based on two datasets, CIFAR-100 [24] and ImageNet [44], following common settings [13, 18, 40, 30]. CIFAR-100 [24] contains 60, 000 samples of 32× 32 color images from 100 classes. There are 500 training and 100 test samples for each class. ImageNet (ILSVRC 2012) [44] contains around 1.3 million samples of 224 × 224 color images from 1, 000 classes. There are about 1, 300 training and 50 test samples for each class. ImageNet has two CIL settings: ImageNet-Subset is based on a subset of 100 classes; and ImageNet-Full uses the full set of 1, 000 classes. The 100-class data for the ImageNet-Subset are sampled from ImageNet. For the experiments on PODNet [13] and POD-AANets [30], we use the same class orders and hyperparameters as [13]. For the experiments on LUCIR [18] and LUCIR-AANets [30], we use the same class orders and hyperparameters as [18].
Benchmarks. We follow the benchmark protocol used in [13, 18, 30, 31]. Given a dataset, the initial (the 0-th phase) model is trained on the data of half of the classes. Then, it learns the remaining classes evenly in the subsequentN phases. Assume there is an initial phase andN incremental phases in the CIL system. The total number of incremental phases N is set to be 5, 10 or 25 (for each the setting is called “N -phase” setting). At the end of each individual phase, the learned model in each phase is evaluated on the test set containing all seen classes. In the tables, we report average accuracy over all phases and the last-phase accuracy, where the latter indicates the degree of forgetting.
Network Architectures. Following [18, 30, 40, 52], we use a 32-layer ResNet [40] for CIFAR-100 and an 18-layer ResNet [17] for ImageNet. Please note that it is standard to use a shallower ResNet for ImageNet. The 32-layer ResNet consists of an initial convolution layer and three residual blocks (in a single branch). Each block has ten convolution layers with 3× 3 kernels. The number of filters starts from 16 and is doubled every next block. After these three blocks, there is an average-pooling layer to compress the output feature maps to a feature embedding. The 18-layer ResNet follows the standard settings in [17]. We deploy AANets using the same parameters as its original paper [30].
Method CIFAR-100 ImageNet-Subset ImageNet-Full
N=5 10 25 5 10 25 5 10 25
LwF [29] 56.79 53.05 50.44 58.83 53.60 50.16 52.00 47.87 47.49 iCaRL [40] 60.48 56.04 52.07 67.33 62.42 57.04 50.57 48.27 49.44 LUCIR [18] 63.34 62.47 59.69 71.21 68.21 64.15 65.16 62.34 57.37 Mnemonics [31] 64.59 62.59 61.02 72.60 71.66 70.52 65.40 64.02 62.05 PODNet [13] 64.60 63.13 61.96 76.45 74.66 70.15 66.80 64.89 60.28
For policy functions πη and πφ, we use two-layer FC networks. All actions are discretized at 0.1 intervals to reduce the search space and get a tolerable training overhead.
Hyperparameters and Configuration. The training of the classification model Θ exactly follows the uniform setting in [13, 18, 30, 31]. On CIFAR-100 (ImageNet-Subset/Full), we train it for 160 (90) epochs in each phase, and divide the learning rate by 10 after 80 (30) and then after 120 (60) epochs. Then, we fine-tune the model for 20 epochs using only exemplars (including the preserved exemplars of the new data to be used in future phases). We use an SGD optimizer and an ADAM optimizer for the classification model and policy functions, respectively. More details are given in the supplementary.
Memory Budget. There are two popular settings about memory budget in related work. One uses a bounded memory budget with a fixed capacity for all phases [18, 31, 40]. Another one allows the memory budget to grow along with phases [18, 20, 49]. The first one is more strict and thus used as the major setting in our paper (note that the results and analyses using the second setting are given in the supplementary materials). In every benchmark, the total budget of memory depends on the phase number N . For example, on CIFAR-100, the total memory budget is set as 7, 000 samples when N=5 (7, 000 samples = 10 classes/phase × 500 samples/class + 2, 000 samples). Please note that 2, 000 is a bounded memory budget allocated since the 0-th phase for saving exemplars. More clarifications about memory budget are given in the supplementary. For fair comparison, we re-implement related methods and report the results in Table 1 if their original results (in the respective papers) were obtained in a different setting of memory budget.

heading: 5.2 Results and Analyses

text:
Table 1 presents the results of two state-of-the-art methods (LUCIR+AANets and POD+AANets [30]) w/ and w/o our RMM plugged in, and some recent CIL work [13, 18, 29, 31, 40]. Table 2 shows the ablation study in 6 settings. Figure 4 plots the changes of the average number of exemplars per old/new class for the incremental phases.
Comparing to the State-of-the-Art. From Table 1, we make the following observations. 1) Our RMM consistently improves the two top baselines LUCIR+AANets and POD+AANets [30] in all settings. E.g., LUCIR-AANets w/ RMM and POD-AANets w/ RMM respectively get 2.7% and 3.1% average improvements on the ImageNet-Subset. 2) Our POD-AANets w/ RMM achieves the best performances. Interestingly, we find that our RMM can boost performance more when the number of phases is larger. For example, when N=25, RMM improves POD-AANets by 3.6% and 4.4% on CIFAR-100 and ImageNet-Subset, respectively. These two numbers are 2.3% and 2.1% when N=5.
This indicates that the superiority of our RMM is more obvious in challenging settings (where the forgetting problem is more serious due to the more frequent model re-training through phases).
Ablation Settings. Table 2 shows the results of our ablation study. Row 1 is for the baseline method POD-AANets [30]. Row 2 is for learning only Level-1 policy πη (where each class gets an even split of the memory). Row 3 is for learning both Level-1 policy πη and Level-2 policy πφ in our proposed hierarchical method, and its results are used in Table 1 as “ours”. Row 4 is for using Policy functions Transferred from another dataset (T.P.), which means on the target CIL dataset there is no training of RMM. Here, for CIFAR-100, we use the policy functions learned on ImageNet-Subset, and vice versa. On the last two rows, we show two oracle settings. Row 5 is the upper bound that assumes all past and future data are accessible during training RMM on the target CIL dataset. Row 6 is for using cross-validation (i.e., all past, future, and validation data are accessible) to find the best fixed memory split between old and new class data, e.g., oldnew = 0.7 is chosen and then used in all phases. The details of chosen split rates are given in the supplementary materials.
Ablation Results. Hierarchical: In Table 2, when comparing Row 2 to Row 1, it is clear that leveraging reinforcement learning yields better results as it can derive adaptive memory allocation between old and new data. Using class-specific memory management further increases the model performance (i.e., comparing Row 3 to Row 2), even though we divide the classes into only two groups. T.P. (Transferred Policy functions): Comparing Row 4 to Row 3, we can see that using transferred policy functions (trained on another dataset) achieves comparable performance, and Row 4 does not require any reinforcement learning on the target CIL dataset. Oracle: Comparing Row 3 to Row 5, we see that learning RMM on pseudo CIL tasks is comparable to the upper bound case where all training and validate data are accessible, given the fact that the latter needs higher computational overhead and violates the standard CIL protocol. Row 6 results are consistently lower than ours in Row 3, although cross-validation has access to all past, future, and validation data.
Allocated Memory. Figure 4 shows the change of the average number of samples per class in three ablative settings. Solid and dashed lines represent old and new classes, respectively. From the plots, we have two observations. 1) Learning RMM on the pseudo or target CIL tasks (green and orange lines), we can obtain similar memory management results (i.e., actions). This means the learned policy is transferrable in non-stationary continuous environments. This matches the conclusion of continuous adaptation in [2]. 2) Using our RMM method achieved more balanced memory sizes between exemplars and new data. For example, in the 1-st phase of the 5-phase setting, “UpperBound
1 2 3 4 5 phase (N=5)
RL” and “Two-level RL” allocate around 100 samples for both exemplars and new data. While the baseline setting has 40 and 500 samples for them, respectively. It thus addresses the data imbalance problem for CIL in a learnable way.

heading: 6 Conclusions

text:
We propose the reinforced memory management (RMM) method specially for tackling CIL tasks. The hierarchical reinforcement learning (RL) framework (two levels) in RMM is capable of making more adaptive memory allocation actions than using standard RL (one level). Using the generated pseudo tasks in RMM solves the issue of data incompatibility between CIL and RL. Corresponding experimental results show that the policy trained on these pseudo tasks can be directly applied to target tasks without any computational overhead. Our overall method of RMM is generic, and its trained policy (with or without using an in-domain dataset) can be easily incorporated into exemplar replaying-based CIL methods to boost performance.
Limitations and Societal Impact
We analyse the limitations and potential negative societal impact in the following three aspects.
• Complexity. Training RMM takes an additional time cost. According to Algorithm 1, the cost is O(mKZ) times higher than the time used for the target CIL task. However, the training of RMM policy is offline and can use a different dataset (see Table 2) — RMM pre-learns a robust policy from synthesized pseudo tasks and can be directly applied for memory management in real CIL tasks. The overhead of applying this policy is very little, e.g., 0.63% and 1.12% of the total training time respectively on CIFAR-100 and ImageNet (Subset and Full), taking POD+AANets as the baseline.
• Technical assumptions. We build the framework of RMM based on a series of technical assumptions, which might not directly hold for all real-world continual-learning applications. When applying our method to mission-critical problems, particular care is required when modeling the system.
• Privacy issues. Keeping the old class exemplars has the issue of data privacy. This calls for future research that explicitly forgets or mitigates the identifiable feature of the data.
Acknowledgments and Disclosure of Funding
This research was supported by A*STAR under its AME YIRG Grant (Project No. A20E6c0101), Alibaba Innovative Research (AIR) programme, and Max Planck Institute for Informatics.

title: RMM: Reinforced Memory Management for Class-Incremental Learning


summaries: This paper analyzes local SGD with progressively decreasing communication frequency under the homogeneous data assumption. Unfortunately, the obtained convergence rates are worse than the best-known convergence rates for FedAC (Yuan and Ma) under the same set of assumptions. The paper also analyses One-shot averaging under a slightly different set of assumptions, showing it retains its linear convergence in settings less restrictive than pre-existing literature. Since the major result of this paper is worse than FedAC's guarantee, it is very incremental.    **References**  Yuan, Honglin, and Tengyu Ma. "Federated Accelerated Stochastic Gradient Descent." Advances in Neural Information Processing Systems 33 (2020).

summaries: ## Update after rebuttall  I am satisfied with the authors' response and elevate my score to 6.  ##  This paper presents several new theoretical results on the convergence of Local SGD as well as numerical experiments to check the tightness of the theory. In particular, the authors try and remove logarithmic terms from the bounds of Local SGD by making the communication less frequent as the iteration counter increases. The main results of the paper are:  1. Theorem 1 gives convergence for strongly convex functions under uniform-with-strong-growth noise. I argue in my detailed review that this result looks suboptimal.  2. Theorem 2 gives a result for PL functions with sub-Gaussian noise for one-shot averaging. This result is interesting as it promises a linear speed-up, although under somewhat restrictive assumptions.   3. The experiments show that linear speed-up is lost when the number of communication rounds is chosen smaller than predicted by the theory of Theorem 1.  I tend to vote for rejection of this work, even though I appreciate some of the results obtained here. My main concerns are 1) applicability of the message to neural network training, which is highly relevant to FL; 2) the theoretical improvements appear to be small; 3) some small flaws in the proofs.

summaries: In this paper, the authors study the theoretical speedup of local SGD and one-shot averaging. A synchronization scheme that communicates more frequently at the beginning is also suggested. Some simple numerical experiments are provided to verify the theoretical results.

summaries: This paper investigates the gap between local SGD and One-Shot averaging in communication efficacy and linear speed-up with respect to the number of workers. Through extensive analysis, they show that they can tighten the bound for the number of communication required for local SGD to $\Omega\left(N\right)$, which is the number of workers. They have proved this bound for strongly convex and objectives with PL condition, where the strong convexity can be a special case of it. They use the idea of adaptive local step to have a more frequent communication at the beginning of the training and less frequent one at the end. In their experimental section, they show that their proposal can converge to the same rate as other local SGD approaches and Sync SGD using  $\Omega\left(N\right)$ communication rounds.

abstractText: We consider speeding up stochastic gradient descent (SGD) by parallelizing it across multiple workers. We assume the same data set is shared among N workers, who can take SGD steps and coordinate with a central server. While it is possible to obtain a linear reduction in the variance by averaging all the stochastic gradients at every step, this requires a lot of communication between the workers and the server, which can dramatically reduce the gains from parallelism. The Local SGD method, proposed and analyzed in the earlier literature, suggests machines should make many local steps between such communications. While the initial analysis of Local SGD showed it needs Ω( √ T ) communications for T local gradient steps in order for the error to scale proportionately to 1/(NT ), this has been successively improved in a string of papers, with the state of the art requiring Ω (N ( poly(log T ))) communications. In this paper, we suggest a Local SGD scheme that communicates less overall by communicating less frequently as the number of iterations grows. Our analysis shows that this can achieve an error that scales as 1/(NT ) with a number of communications that is completely independent of T . In particular, we show that Ω(N) communications are sufficient. Empirical evidence suggests this bound is close to tight as we further show that √ N or N communications fail to achieve linear speed-up in simulations. Moreover, we show that under mild assumptions, the main of which is twice differentiability on any neighborhood of the optimal solution, one-shot averaging which only uses a single round of communication can also achieve the optimal convergence rate asymptotically.

authors:
Alistarh Dan
Grubic Demjan
Li Jerry
Tomioka Ryota
Vojnovic Milan

title: QSGD: Communicationefficient SGD via gradient quantization and encoding

venue: Advances in Neural Information Processing Systems

authors:
Allen-Zhu Zeyuan
Li Yuanzhi
Song Zhao

title: On the convergence rate of training recurrent neural networks

authors:
Arjevani Yossi
Shamir Ohad

title: Communication complexity of distributed convex learning and optimization // Advances in neural information processing systems

title: Introduction to nonlinear optimization: Theory, algorithms, and applications with MATLAB

authors:
S Bijral Avleen
D Sarwate Anand
Nathan. Srebro

title: On data dependence in distributed stochastic optimization // arXiv preprint arXiv:1603.04379

authors:
Chang Chih-Chung
Lin Chih-Jen

title: LIBSVM: A library for support vector machines

venue: ACM Transactions on Intelligent Systems and Technology

authors:
Charles Zachary
Papailiopoulos Dimitris

title: Stability and generalization of learning algorithms that converge to global optima

venue: International Conference on Machine Learning

authors:
Chen Xie
Eversole Adam
Li Gang
Yu Dong
Seide Frank

title: Pipelined back-propagation for contextdependent deep neural networks

venue: Thirteenth Annual Conference of the International Speech Communication Association

authors:
Dekel Ofer
Gilad-Bachrach Ran
Shamir Ohad
Xiao Lin

title: Optimal distributed online prediction using mini-batches

venue: Journal of Machine Learning Research

authors:
Dieuleveut Aymeric
Patel Kumar Kshitij

title: Communication trade-offs for Local-SGD with large step size

authors:
Godichon-Baggioni Antoine
Saadane Sofiane

title: On the rates of convergence of parallelized averaged stochastic gradient algorithms // Statistics

authors:
Grubic Demjan
Tam Leo K
Alistarh Dan
Zhang Ce

title: Synchronous multi-gpu deep learning with low-precision communication: An experimental study

venue: Proceedings of the 21st International Conference on Extending Database Technology

authors:
Haddadpour Farzin
Kamani Mohammad Mahdi
Mahdavi Mehrdad
Cadambe Viveck

title: Local SGD with periodic averaging: Tighter analysis and adaptive synchronization

authors:
Hendrikx Hadrien
Bach Francis
Massoulié Laurent

title: An accelerated decentralized stochastic proximal algorithm for finite sums

authors:
Kairouz Peter
McMahan H Brendan
Avent Brendan
Bellet Aurélien
Bennis Mehdi
Bhagoji Arjun Nitin
Bonawitz Keith
Charles Zachary
Cormode Graham
Cummings Rachel

title: Advances and open problems in federated learning

authors:
Karimi Hamed
Nutini Julie
Schmidt Mark

title: Linear convergence of gradient and proximal-gradient methods under the polyak-łojasiewicz condition

venue: Joint European Conference on Machine Learning and Knowledge Discovery in Databases

authors:
A Khaled
K Mishchenko
P. Richtárik

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

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

authors:
Koloskova Anastasia
Loizou Nicolas
Boreiri Sadra
Jaggi Martin
Stich Sebastian U

title: A Unified Theory of Decentralized SGD with Changing Topology and Local Updates

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

title: Federated learning: Strategies for improving communication efficiency

venue: arXiv preprint arXiv:1610.05492

authors:
Lin Tao
Stich Sebastian U
Patel Kumar Kshitij
Jaggi Martin

title: Don’t Use Large Mini-Batches

venue: Use Local SGD // arXiv preprint arXiv:1808.07217

authors:
Lin Yujun
Han Song
Mao Huizi
Wang Yu
Dally Bill

title: Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training

venue: International Conference on Learning Representations

authors:
Madden Liam
Dall’Anese Emiliano
Becker Stephen

title: High probability convergence and uniform stability bounds for nonconvex stochastic gradient descent

title: Parallel gradient distribution in unconstrained optimization

venue: SIAM Journal on Control and Optimization

authors:
McDonald Ryan
Hall Keith
Mann Gideon

title: Distributed training strategies for the structured perceptron // Human language technologies: The 2010 annual conference of the North American chapter of the association for computational linguistics

authors:
McMahan Brendan
Moore Eider
Ramage Daniel
Hampson Seth
Arcas Blaise Aguera y

title: Communication-Efficient Learning of Deep Networks from Decentralized Data

venue: Artificial Intelligence and Statistics

authors:
Mcdonald Ryan
Mohri Mehryar
Silberman Nathan
Walker Dan
Mann Gideon S

title: Efficient largescale distributed training of conditional maximum entropy models // Advances in neural information processing systems

authors:
Rosenblatt Jonathan D
Nadler Boaz

title: On the optimality of averaging in distributed statistical learning // Information and Inference: A Journal of the IMA

authors:
Schmidt Mark
Roux Nicolas Le

title: Fast convergence of stochastic gradient descent under a strong growth condition // arXiv preprint arXiv:1308.6370

authors:
Sergeev Alexander
Del Balso Mike

title: Horovod: fast and easy distributed deep learning in TensorFlow

venue: arXiv preprint arXiv:1802.05799

authors:
Spiridonoff Artin
Olshevsky Alex
Paschalidis Ioannis Ch

title: Robust asynchronous stochastic gradientpush: asymptotically optimal and network-independent performance for strongly convex functions

title: Local SGD Converges

venue: Fast and Communicates Little // International Conference on Learning Representations

authors:
Stich Sebastian U
Cordonnier Jean-Baptiste
Jaggi Martin

title: Sparsified SGD with memory

authors:
Stich Sebastian U
Karimireddy Sai Praneeth

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

authors:
Tang Zhenheng
Shi Shaohuai
Chu Xiaowen
Wang Wei
Li Bo

title: Communication-Efficient Distributed Deep Learning: A Comprehensive Survey

authors:
Wang Jianyu
Joshi Gauri

title: Adaptive communication strategies to achieve the best error-runtime trade-off in local-update SGD // Systems for ML

title: Cooperative SGD: A unified framework for the design and analysis of communication-efficient SGD algorithms // arXiv preprint arXiv:1808.07576

authors:
Wang Jianyu
Sahu Anit Kumar
Yang Zhouyi
Joshi Gauri
Kar Soummya

title: MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling

authors:
Wangni Jianqiao
Wang Jialei
Liu Ji
Zhang Tong

title: Gradient sparsification for communicationefficient distributed optimization

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

title: Is Local SGD Better than Minibatch SGD

authors:
Yadan Omry
Adams Keith
Taigman Yaniv
Ranzato

title: Marc’Aurelio. Multi-gpu training of convnets

venue: arXiv preprint arXiv:1312.5853

authors:
Yu Hao
Yang Sen
Zhu Shenghuo

title: Parallel restarted SGD with faster convergence and less communication: Demystifying why model averaging works for deep learning

venue: Proceedings of the AAAI Conference on Artificial Intelligence

authors:
Yuan Honglin
Ma Tengyu

title: Federated Accelerated Stochastic Gradient Descent

authors:
Zhang Jian
De Sa Christopher
Mitliagkas Ioannis
Ré Christopher

title: Parallel SGD: When does averaging help

venue: arXiv preprint arXiv:1606.07365

authors:
Zhang Shanshan
Zhang Ce
You Zhao
Zheng Rong
Xu Bo

title: Asynchronous stochastic gradient descent for DNN training

venue: IEEE International Conference on Acoustics, Speech and Signal Processing

authors:
Zhang Sixin
Choromanska Anna E
LeCun Yann

title: Deep learning with elastic averaging SGD // Advances in neural information processing systems

authors:
Zhang Yuchen
Duchi John
Jordan Michael I
Wainwright Martin J

title: Information-theoretic lower bounds for distributed statistical estimation with communication constraints

authors:
Yuchen Zhang
C Duchi John
J. Wainwright Martin

title: Communication-efficient algorithms for statistical optimization

venue: Journal of Machine Learning Research. 2013c

authors:
Zhou Fan
Cong Guojing

title: On the convergence properties of a K-step averaging stochastic gradient descent algorithm for nonconvex optimization

venue: Proceedings of the 27th International Joint Conference on Artificial Intelligence

authors:
Zinkevich Martin
Weimer Markus
Li Lihong
Smola Alex J

title: Parallelized stochastic gradient descent // Advances in neural information processing systems

text:
√ T ) communications for T local gradient
steps in order for the error to scale proportionately to 1/(NT ), this has been successively improved in a string of papers, with the state of the art requiring Ω (N ( poly(log T ))) communications. In this paper, we suggest a Local SGD scheme that communicates less overall by communicating less frequently as the number of iterations grows. Our analysis shows that this can achieve an error that scales as 1/(NT ) with a number of communications that is completely independent of T . In particular, we show that Ω(N) communications are sufficient. Empirical evidence suggests this bound is close to tight as we further show that √ N or N3/4 communications fail to achieve linear speed-up in simulations. Moreover, we show that under mild assumptions, the main of which is twice differentiability on any neighborhood of the optimal solution, one-shot averaging which only uses a single round of communication can also achieve the optimal convergence rate asymptotically.

heading: 1 Introduction

text:
Stochastic Gradient Descent (SGD) is a widely used algorithm to minimize convex functions f in which model parameters are updated iteratively as
xt+1 = xt − ηtĝt,
where ĝt is a stochastic gradient of f at the point xt and ηt is the learning rate. This algorithm can be naively parallelized by adding more workers independently to compute a gradient and then average
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
them at each step to reduce the variance in estimation of the true gradient∇f(xt) (Dekel et al., 2012). This method requires each worker to share their computed gradients with each other at every iteration. We will refer to this method as "synchronized parallel SGD."
However, it is widely acknowledged that communication is a major bottleneck of this method for large scale optimization applications (McMahan et al., 2017; Konečnỳ et al., 2016; Lin et al., 2018b). Often, mini-batch parallel SGD is suggested to address this issue by increasing the computation to communication ratio. Nonetheless, too large mini-batch size might degrade performance (Lin et al., 2018a). Along the same lines of increasing the computation over communication effort, local SGD has been proposed to reduce communications (McMahan et al., 2017; Dieuleveut, Patel, 2019). In this method, workers compute (stochastic) gradients and update their parameters locally, and communicate only once in a while to obtain the average of their parameters. Local SGD improves the communication efficiency not only by reducing the number of communication rounds, but also alleviates the synchronization delay caused by waiting for slow workers and evens out the variations in workers’ computing time (Wang, Joshi, 2018b).
On the other hand, since individual gradients of each worker are calculated at different points, this method introduces residual error as opposed to fully synchronized SGD. Therefore, there is a tradeoff between having fewer communication rounds and introducing additional errors to the gradient estimates.
The idea of making local updates is not new and has been used in practice for a while (Mangasarian, 1995; Konečnỳ et al., 2016). However, until recently, there have been few successful efforts to analyze Local SGD theoretically and therefore it is not fully understood yet. Zhang et al. (2016) show that for quadratic functions, when the variance of the noise is higher far from the optimum, frequent averaging leads to faster convergence. The first question we try to answer in this work is: how many communication rounds are needed for Local SGD to have the similar convergence rate of a synchronized parallel SGD while achieving performance that linearly improves in the number of workers?
Stich (2019) was among the first who sought to answer this question for general strongly convex and smooth functions and showed that the communication rounds can be reduced up to a factor of H = O( √ T/N), without affecting the asymptotic convergence rate (up to constant factors), where T is the total number of iterations and N is number of parallel workers.
Focusing on smooth and possibly non-convex functions which satisfy a Polyak-Lojasiewicz condition, Haddadpour et al. (2019) demonstrate that only R = Ω((TN)1/3) communication rounds are sufficient to achieve asymptotic performance that scales proportionately to 1/N .
Recently, Khaled et al. (2020) and Stich, Karimireddy (2019) improve upon the previous works by showing linear speed-up for Local SGD with only Ω (N poly log (T )) communication rounds when data is identically distributed among workers and f is strongly convex. Their works also consider the cases when f is not necessarily strongly convex as well as the case of data being heterogeneously distributed among workers. More recently, Yuan, Ma (2020) proposed a new accelerated method that requires only Ω ( N1/3 poly log (T ) ) communication rounds for linear speed-up. While their results improve upon the earlier work, the communication requirements remain dependent on the total iterations T .
One-Shot Averaging (OSA), a method that takes an extreme approach to reducing communication, involves workers performing local updates until the very end when they average their parameters (Mcdonald et al., 2009; Zinkevich et al., 2010; Zhang et al., 2013c; Rosenblatt, Nadler, 2016; Godichon-Baggioni, Saadane, 2020). This method can be seen as an extreme case of Local SGD with R = 1 and H = T local steps. Dieuleveut, Patel (2019); Godichon-Baggioni, Saadane (2020) provide an analysis of OSA and show that asymptotically, linear speed-up in the number of workers is achieved for a weighted average of iterates. However, both of these works make restrictive assumptions such as uniformly three-times continuously differentiability and bounded second and third derivatives or twice differentiability almost everywhere with bounded Hessian, respectively. The second question we attempt to answer in this work, is whether these assumptions can be relaxed and OSA can achieve linear speed-up in more general scenarios.
In this work, we focus on smooth and strongly convex functions with a general noise model. Our contributions are three-fold:
We notice that FedAC (Yuan, Ma, 2020) has a better dependence on the number of workers N , in expense of (poly logarithmic) dependence on T . With that in mind, we still believe our communication strategy is of independent interest, particularly in the framework of non-accelerated methods. We have performed extensive numerical experiments and comparisons between the two methods and highlighted the regimes where each method outperforms the other.
It is worth mentioning that although the the communication complexity by Woodworth et al. (2020) depends on T , their bound has a lower dependence on condition number κ. Hence, their results are stronger than ours only when κ = Ω(log T ).
The rest of this paper is organized as follows. In the following subsection we outline the related literature and ongoing works. In Section 2 we define the main problem and state our assumptions. We present our theoretical findings in Section 3 followed by numerical experiments in Section 4 and conclusion remarks in Section 5.

heading: 1.1 Related work

text:
There has been a lot of effort in the recent research to take into account the communication delays and training time in designing faster algorithms (McDonald et al., 2010; Zhang et al., 2015; Bijral et al., 2016; Kairouz et al., 2019). See (Tang et al., 2020) for a comprehensive survey of commu-
nication efficient distributed training algorithms considering both system-level and algorithm-level optimizations.
Many works study the communication complexity of distributed methods for convex optimization (Arjevani, Shamir, 2015; Woodworth et al., 2020) and statistical estimation (Zhang et al., 2013b). Woodworth et al. (2020) present a rigorous comparison of Local SGD with H local steps and minibatch SGD with H times larger mini-batch size and the same number of communication rounds (we will refer to such a method as large mini-batch SGD) and show regimes in which each algorithm performs better: they show that Local SGD is strictly better than large mini-batch SGD when the functions are quadratic. Moreover, they prove a lower bound on the worst case of Local SGD that is higher than the worst-case error of large mini-batch SGD in a certain regime. Zhang et al. (2013b) study the minimum amount of communication required to achieve centralized minimax-optimal rates by establishing lower bounds on minimax risks for distributed statistical estimation under a communication budget.
A parallel line of work studies the convergence of Local SGD with non-convex functions Zhou, Cong (2018). Yu et al. (2019) was among the first works to present provable guarantees of Local SGD with linear speed-up. Wang, Joshi (2018b) and Koloskova et al. (2020) present unified frameworks for analyzing decentralized SGD with local updates, elastic averaging or changing topology. The follow-up work of Wang, Joshi (2018a) presents ADACOMM, an adaptive communication strategy that starts with infrequent averaging and then increases the communication frequency in order to achieve a low error floor. They analyze the error-runtime trade-off of Local SGD with nonconvex functions and propose communication times to achieve faster runtime.
Another line of work reduces the communication by compressing the gradients and hence limiting the number of bits transmitted in every message between workers (Lin et al., 2018b; Alistarh et al., 2017; Wangni et al., 2018; Stich et al., 2018; Stich, Karimireddy, 2019).
Asynchronous methods have been studied widely due to their advantages over synchronized methods which suffer from synchronization delays due to the slower workers (Spiridonoff et al., 2020). Wang et al. (2019) study the error-runtime trade-off in decentralized optimization and proposes MATCHA, an algorithm which parallelizes inter-node communication by decomposing the topology into matchings. However, these methods are relatively more involved and they often require full knowledge of the network, solving a semi-definite program and/or calculating communication probabilities (schedules) as in Hendrikx et al. (2019).
The homogeneous data assumption. In this work, we focus on the case when the data distribution is the same across workers. A number of previous works (Khaled et al., 2020; Haddadpour et al., 2019; Stich, 2019; Dieuleveut, Patel, 2019) studied local SGD under this assumption. The assumption is valid when the same data set is either shared across multiple workers in the same cluster, or the assignment of data points to workers is random so that any distributional differences are small. Sharing the data set across multiple workers in this way is a popular strategy to speed up training. For example, such data sharing is implemented in (Chen et al., 2012; Yadan et al., 2013; Zhang et al., 2013a) to speed up training of deep neural networks with multiple GPUs within a single server. While there are many widely used mechanisms such as Horovod (Sergeev, Del Balso, 2018) for synchronous data-parallel distributed training, they share a major communication bottleneck of broadcasting gradients to all workers (Grubic et al., 2018). Local SGD improves on these methods by reducing the communication of model parameters from every iteration to a smaller number of rounds during the entire optimization process. Our approach further reduces the communication overhead by communicating less as the number of iterations grows.

heading: 1.2 Notation

text: For a positive integer s, we define [s] := {1, . . . , s}. We use bold letters to represent vectors. We denote vectors of all 0s and 1s by 0 and 1, respectively. We use ‖ · ‖ for the Euclidean norm of a vector and spectral norm of a matrix. Finally, N (µ, σ2) denotes a normal distribution with mean µ and variance σ2.

heading: 2 Problem formulation

text:
Suppose there are N workers V = {1, . . . , N}, trying to minimize f : Rd → R in parallel. We assume all workers have access to f through noisy gradients. In Local SGD, workers perform local gradient steps and occasionally calculate the average of all workers’ iterates. Each worker i holds a local parameter xti at iteration t. There is a set I ⊂ [T ] of communication times and nodes perform the following update:
xt+1i = { xti − ηtĝti , if t+ 1 /∈ I, 1 N ∑N j=1(x t j − ηtĝtj), if t+ 1 ∈ I,
(1)
where ĝti is an unbiased stochastic gradient of f at x t i. When I = [T ], we recover fully synchronized parallel SGD while I = {T} recovers one-shot averaging. Pseudo-code for Local SGD is provided as Algorithm 1.
Algorithm 1 Local SGD
1: Input: x0i = x 0 for all i ∈ [n], total number of iterations T , the step-size sequence {ηt}T−1t=0 , and
I ⊆ [T ] 2: for t = 0, . . . , T − 1 do 3: for j = 1, . . . , N do 4: evaluate a stochastic gradient ĝtj 5: if t+ 1 ∈ I then 6: xt+1j = 1 N ∑N i=1(x t i − ηtĝti) 7: else 8: xt+1j = x t j − ηtĝtj
9: end if 10: end for 11: end for
Next we state the assumptions that we will use in our results. Note that we will not require all of them to hold at once. Assumption 1 (smoothness). The function f : Rd → R is continuously differentiable and its gradients are L-Lipschitz, i.e.,
‖∇f(x)−∇f(y)‖ ≤ L‖x− y‖, ∀x,y. Assumption 2 (strong convexity). f is µ-strongly convex with µ > 0, i.e.,
f(x) + 〈g,y − x〉+ µ 2 ‖x− y‖2 ≤ f(y), ∀x,y ∈ Rd,∀g ∈ ∂f(x),
where ∂f(x) denotes the set of subgradients of f at x. When f is also continuously differentiable, ∂f(x) = {∇f(x)}.
Note that when f satisfies Assumption 2, it has a unique optimal point x∗ where f(x∗) = f∗ where f∗ = minx f(x). Assumption 3 (Polyak-Łohasiewicz condition). f is µ-Polyak-Łohasiewicz (µ-PL for short) if
‖∇f(x)‖2 ≥ 2µ(f(x)− f∗), ∀x. where f∗ = minx f(x) is the global minimum of f . We further assume that f has a unique optimal point x∗ where f(x∗) = f∗.
When f satisfies both Assumptions 1 and 2 or Assumptions 1 and 3, we define κ = L/µ as the condition number of f .
Strong convexity implies the PL condition but the reverse does not always hold. For instance, the logistic regression loss function satisfies the PL condition over any compact set (Karimi et al., 2016). In fact, a PL function is not even necessarily convex. Charles, Papailiopoulos (2018) show that deep networks with linear activation functions are PL almost everywhere in the parameter space. Allen-Zhu et al. (2018) show, with high probability over random initializations, that sufficiently wide recurrent neural networks satisfy the PL condition. Therefore, the PL condition is more applicable, especially in the context of neural networks (Madden et al., 2020).
Assumption 4 (twice differentiability at the optimum). f is twice continuously differentiable on an open set containing the optimal point x∗.
We make the following assumption on the noise of stochastic gradients, using wti = ĝ t i −∇f(xti) to denote the difference between the stochastic and true gradients. Assumption 5 (uniform with strong-growth noise). Conditioned on the iterate xti, the random variable wti is zero-mean and independent with its expected squared norm error bounded as,
E[‖wti‖2|xti] ≤ c‖∇f(xti)‖2 + σ2, where σ2, c ≥ 0 are constants.
The noise model of Assumption 5 is very general and it includes the common case with uniformly bounded squared norm error when c = 0. As it is noted by Zhang et al. (2016), the advantage of periodic averaging compared to one-shot averaging only appears when c/σ2 is large. Therefore, to study Local SGD, it is important to consider a noise model as in Assumption 5 to capture the effects of frequent averaging. Among the related works mentioned in Table 1, only Stich, Karimireddy (2019) and Haddadpour et al. (2019) analyze this noise model while the rest study the special case with c = 0. SGD under this noise model with c > 0 and σ2 = 0 was first studied in Schmidt, Roux (2013) under the name strong-growth condition. Therefore we refer to the noise model considered in this work as uniform with strong-growth. Assumption 6 (sub-Gaussian noise). Conditioned on the iterate xti, random variable wti is zero-mean, independent and [wti ]l is (σ/ √ d)-sub-Gaussian, for l = 1, . . . , d, i.e.,
E[exp(λ([wti ]l − E[wti ]l))|xti] ≤ exp ( λ2σ2
2d
) , ∀λ ∈ R, l = 1, . . . , d.
Thus, it has uniformly bounded variance E[‖wti‖2|xti] ≤ σ2.
A sub-Gaussian noise model is commonly assumed for deriving concentration bounds for SGD, which we will use to prove our results for OSA.
As already mentioned in the Introduction, the main goal of this paper is to study the effect of communication times on the convergence of the Local SGD and provide better theoretical guarantees. In what follows, we claim that by carefully choosing the communication times, linear speed-up of parallel SGD can be attained with only a small number of communication instances. Moreover, we will obtain a set of sufficient conditions for OSA to achieve linear speed-up.

heading: 3 Convergence results

text:
In this section we present our main convergence results for Local SGD and OSA. In what follows, we denote by x̄t := ( ∑N i=1 x t i)/N the average of the iterates of all workers. Notice that x t i = x̄
t for t ∈ I and i = 1, . . . , N .

heading: 3.1 Local SGD

text:
Let us introduce the notation 0 = τ0 < τ1 < . . . < τR = T, for the communication times. Further, let us define Hi := τi+1 − τi to be the i’th interccommunication interval. Our first theorem gives a performance bound under the assumption that Hi grows linearly with i. Theorem 1. Suppose Assumptions 1 (smoothness), 2 (strong convexity) and 5 (uniform with strong growth noise) hold. Choose the parameters as follows: R such that 1 ≤ R ≤ √
2T and a := d2T/R2e ≥ 1,Hi = a(i+1) and τi+1 = min(τi +Hi, T ) for i = 0, . . . , R− 1. Choose β ≥ max{9κ, 12κ2cmax{ln(3), ln(1 + T/(4κR2))}+ 3κ(1 + c/N)} and set the learning rate as ηt = 3/µ(t+ β), t = 0, 1, . . . , T − 1. Then using Algorithm 1 we have,
E[f(x̄T )]− f∗ ≤ β 2(f(x̄0)− f∗)
T 2 +
9Lσ2
2µ2NT +
144L2σ2
µ3RT .
Corrollary 1. Under the assumptions of Theorem 1, selecting the number of communications R = Ω(κN) we obtain
E[f(x̄T )]− f∗ ≤ β 2(f(x̄0)− f∗)
T 2 +O
( Lσ2
µ2NT
) .
The choice of communication times in Theorem 1 aligns with the intuition that workers need to communicate more frequently at the beginning of the optimization. As the the step-sizes become smaller and workers’ local parameters get closer to the global minimum, they diverge more slowly from each other and therefore, less communication is required to re-align them. The advantage of this communication strategy over fixed periodic averaging has been only empirically shown in Haddadpour et al. (2019). The proof of Theorem 1 can be found in Appendix B.

heading: 3.2 One-shot averaging

text:
The previous literature literature has shown OSA achieves asymptotic linear speed-up under some restrictive assumptions. For instance, Dieuleveut, Patel (2019) show this for three times continuously differentiable functions with second and third uniformly bounded derivatives. Similarly, GodichonBaggioni, Saadane (2020) require the objective function to be strongly convex, twice continuously differentiable almost everywhere, with a bounded Hessian everywhere and gradients satisfying the following condition for some constant Cm and all x ∈ Rd,∥∥∇f(x)−∇2f(x∗)(x− x∗)∥∥ ≤ Cm‖x− x∗‖2. This inequality is similar to the assumption from Dieuleveut, Patel (2019) of uniformly bounded third derivatives. In the following theorem, we relax these assumptions and show that OSA achieves linear speed-up under considerably milder assumptions.
Before proceeding, let us define the step-size sequence {θt} as
θt =
{ 1 L , for t = 0, . . . , t0 − 1,
2t µ(t+1)2 , for t ≥ t0,
(2)
where t0 = b2L/µc. Notice that θt ≤ 1/L for all t. Theorem 2. Under Assumptions 1 (smoothness), 3 (PL condition), 4 (twice differentiability at the optimum) and 6 (sub-Gaussian noise) and with step-size sequence {ηt} = {θt} defined in (2), we have for T ≥ t0,
E [∥∥x̄T − x∗∥∥2] ≤ 4σ2
3µ2NT + o
( 1
T
) .
We are thus able to relax the conditions from the earlier literature, which required everywhere or almost everywhere higher derivatives with uniform bounds on third derivatives to merely twice differentiability at a single point. As a bonus, we also replace strong convexity with the PL condition.
This theorem is proved in Appendix C. The main difference between Theorem 2 and Corollary 1 is that Theorem 2 shows a linear speed-up with only one communication round but with slightly more restrictive assumptions such as sub-Gaussian noise model and twice-differentiable objective function at the optimal point. On the other hand, our results for OSA only require the PL-condition instead of strong convexity.

heading: 4 Numerical experiments

text: To verify our findings and compare different communication strategies in Local SGD, we performed the following numerical experiments, using an Nvidia GTX-1060 GPU and Intel Core i7-7700k processor.

heading: 4.1 Quadratic function with strong-growth condition

text:
As discussed in Zhang et al. (2016); Dieuleveut, Patel (2019), under uniformly bounded variance, oneshot averaging performs asymptotically as well as mini-batch SGD, at least for quadratic functions.
Therefore, to fully capture the importance of the choice of communication times I , we design a hard problem, where noise variance is uniform with strong-growth condition, defined in Assumption 5. Let us define,
F (x) = Eζf(x, ζ), f(x, ζ) := d∑ i=1 i 2 x2i (1 + z1,i) + x >z2, (3)
where ζ = (z1, z2) and z1, z2 ∈ Rd, z1,i ∼ N (0, c1) and z2,i ∼ N (0, c2), ∀i ∈ [d], are random variables with normal distributions. We assume at each iteration t, each worker i samples a ζti and uses ∇f(x, ζti ) as a stochastic estimate of ∇F (x). It is easy to verify that F (x) is 1-strongly convex and d-smooth, F ∗ = 0 and Eζ [‖∇f(x, ζ) − ∇F (x)‖2] = c‖∇F (x)‖2 + σ2, where c = c1 and σ2 = dc2.
We use Local SGD to minimize F (x) using different communication strategies, namely, synchronized SGD where H = 1, H ≈ √ TN Stich (2019), H ≈ (TN)1/3 Haddadpour et al. (2019), R = N with constant H ≈ T/N Stich, Karimireddy (2019); Khaled et al. (2020) and finally the communication strategy proposed in this work with R = N and linearly growing Hi local steps. We used N = 20 workers, T = 1000 iterations, c1 = 1.0 and c2 = 10−10 with d = 3 and step-size sequence ηt = 3/(µ(t+ 1)). To estimate the expected value of errors, we repeated the optimization using each strategy 100 times and reported the average and 1-standard-deviation error bar in Figure 1.
We make the following observations from Figure 1:
• Figure 1(a) shows that a communication strategy with increasing local steps (proposed in this work), outperforms all the other methods, both in transient and final error performance, specifically the one with the same number of communication rounds evenly spread throughout the whole optimization. This confirms the advantage of more frequent communication at the beginning of the optimization, especially when the ratio of c to σ2 in the noise with growth condition is large (see the definition in Assumption 5).
• Figure1(b) shows that our communication method uses fewer communication rounds, 20 versus 28 (Haddadpour et al., 2019), 143 (Stich, 2019) and 1000 rounds for synchronized SGD.
• OSA appears to perform relatively well despite using only one communication round, though not quite as well as other methods. This shows that the choice of communication is important in this experiment. In other words, it is not true that the success of our communication strategy is merely a byproduct of the experiment design, where any communication strategy, as long as it communicates at least once, will succeed.

heading: 4.2 Speed-up curves

text:
In this experiment, we minimize a one-dimensional function defined as,
F (x) =
{ 1 2x
2, x ≤ 0, x2, x > 0,
(4)
using Local SGD with gradients corrupted by a normal noise N (0, σ2). We chose this specific cost function since it is not twice continuously differentiable at the minimizer x∗ = 0 and does not satisfy Assumption 4 required by Theorem 2 for OSA to achieve linear speed-up. The results of this experiment will help us understand whether twice differentiability is a necessary assumption for OSA to obtain a linear speed-up.
The speed-up curve is derived by dividing the expected error of a single worker SGD by the expected error of each method at the final iterate T , over different number of workers N . Thus in the case where the error decreases linearly in the number of workers, we should expect to see a straight line on the graph.
We plot the speed-up curve for N workers using different communication strategies: synchronized SGD, R = N communication rounds with linearly increasing number of local steps Hi, R = N with constant number of local steps H ≈ T/R, as well as OSA with only R = 1 communication at the end. We use the step-size sequence ηt = min{1/L, 2/(µ(t + 1))} with µ = 1, L = 2, and σ = 8, T = 1000.
Our results in Figure 2(a) show that Local SGD with R = N (increasing or constant H) achieves linear speed-up in the number of workers, albeit with a worse constant compared to synchronized SGD. However, OSA fails to scale as N increases. This suggests that the condition of twice differentiability (Assumption 4) is necessary for Theorem 2, as this function satisfies all the other assumptions of that theorem.
While our theoretical results provide only an upper bound onR to achieve linear speed-up, this setting gives us a chance to find out if smaller number of communication rounds are enough. Therefore we repeat this experiment for larger number of workers N and T = 8000, using R ≈ N3/4 and R ≈ N1/2 communication rounds. Our results in Figure 2(b) show that R = N clearly achieves speed-up for larger values of N , as expected and R = 1 and R ≈ N1/2 fail to speed-up. However, R ≈ N3/4 also struggles to linearly speed-up in the number of workers, as the slope of the speed-up curve declines with N increasing. It would be of interest to look into a more granular choice of communication rounds such as R ≈ N0.9 or even R ≈ N0.99 but this would require much larger values of N and T and thus more repeated simulations, which is beyond our computational resources, which were already exhausted by generating Figure 2(b).
It is worth mentioning that in both experiments of Figure 2(a) and 2(b), R = N with increasing H outperforms the one with constant H , even though the noise model used in this experiment is simply uniformly bounded, without strong-growth condition. This further endorses the use of more frequent averaging at the beginning of optimization, when paired with decreasing step-size sequence.

heading: 4.3 Regularized logistic regression

text: We also performed additional numerical experiments with regularized logistic regression using two large real datasets: (i) a national dataset (NSQIP) of surgeries performed in the U.S., seeking to predict short-term hospital re-admissions, which consists of 722101 data points (surgeries) each characterized by d = 231 features, (ii) the a9a dataset from LIBSVM (Chang, Lin, 2011) which includes 32561 data points with d = 124 features. The results of these experiments are presented and discussed in Appendix A.

heading: 5 Conclusion

text:
In this work, we studied the communication complexity of Local SGD and provided an analysis that shows that R = Ω(N) number of communication rounds, independent of the total number of iterations T , is sufficient to achieve linear speed-up. Moreover, we showed only a single round of averaging is needed provided that the objective is twice differentiable at the optimum point. This assumption appears to be necessary, as our simulations show that not only one-shot averaging but using N1/2 or N3/4 communications in local SGD fails to deliver linear speed-up on a simple example which is not twice differentiable at the optimum.
Acknowledgments and Disclosure of Funding
The research was partially supported by the NSF under grants DMS-1664644, CNS-1645681, ECCS1933027 and IIS-1914792, by the ONR under grants N00014-19-1-2571 and N00014-21-1-2844, by the ARO under grant W911NF-1-1-0072, by the NIH under grants R01 GM135930 and UL54 TR004130, by the DOE under grants DE-AR-0001282 and NETL-EE0009696, and by the Boston University Kilachand Fund for Integrated Life Science and Engineering.

title: Communication-efficient SGD: From Local SGD to One-Shot Averaging