summaries: This work presents the goal-conditioned supervised learning algorithm (GCSL), which learns goal conditioned policies using only behavioral-cloning of the agent's own actions.  The intuition behind the algorithm is the goal of an observed trajectory can be identified after the fact, by simply looking at the states reached during that trajectory.  GCSL treats each executed action as a sample from the expert policy conditioned on each of the states reached after that action is taken.  Given a distribution over goal states, GCSL alternates between executing its current goal-conditioned policy on randomly selected goals, and learning to imitate the generated actions conditioned on the states they actually reached.  Experimental results demonstrate superior performance against a base (non-goal conditioned) RL algorithm (TRPO), and against another approach to learning goal-conditioned polices (TD3-HER), on a relatively diverse set of control problems.

summaries: This paper proposes a method to learn to reach goals in an RL environment. The method is based on principles of imitation learning. For instance, beginning with an arbitrary policy that samples a sequence of state-action pairs, in the next iteration, the algorithm treats the previous policy as an expert by relabeling its ending state as a goal. The paper shows that the method is theoretically sound and effective empirically for goal-achieving tasks.

abstractText: Imitation learning algorithms provide a simple and straightforward approach for training control policies via standard supervised learning methods. By maximizing the likelihood of good actions provided by an expert demonstrator, supervised imitation learning can produce effective policies without the algorithmic complexities and optimization challenges of reinforcement learning, at the cost of requiring an expert demonstrator – typically a person – to provide the demonstrations. In this paper, we ask: can we use imitation learning to train effective policies without any expert demonstrations? The key observation that makes this possible is that, in the multi-task setting, trajectories that are generated by a suboptimal policy can still serve as optimal examples for other tasks. In particular, in the setting where the tasks correspond to different goals, every trajectory is a successful demonstration for the state that it actually reaches. Informed by this observation, we propose a very simple algorithm for learning behaviors without any demonstrations, user-provided reward functions, or complex reinforcement learning methods. Our method simply maximizes the likelihood of actions the agent actually took in its own previous rollouts, conditioned on the goal being the state that it actually reached. Although related variants of this approach have been proposed previously in imitation learning settings with example demonstrations, we present the first instance of this approach as a method for learning goal-reaching policies entirely from scratch. We present a theoretical result linking self-supervised imitation learning and reinforcement learning, and empirical results showing that it performs competitively with more complex reinforcement learning methods on a range of challenging goal reaching problems.

authors:
Marcin Andrychowicz
Filip Wolski
Alex Ray
Jonas Schneider
Rachel Fong
Peter Welinder
Bob McGrew
Josh Tobin
OpenAI Pieter Abbeel
Wojciech Zaremba

title: Hindsight experience replay

venue: In Advances in Neural Information Processing Systems,

title: Residual algorithms: Reinforcement learning with function approximation

venue: In Machine Learning Proceedings

authors:
Aude Billard
Sylvain Calinon
Ruediger Dillmann
Stefan Schaal

title: Robot programming by demonstration

venue: Springer handbook of robotics,

authors:
Daniel S Brown
Wonjoon Goo
Prabhat Nagarajan
Scott Niekum

title: Extrapolating beyond suboptimal demonstrations via inverse reinforcement learning from observations

authors:
Yiming Ding
Carlos Florensa
Mariano Phielipp
Pieter Abbeel

title: Goal conditioned imitation learning

authors:
Benjamin Eysenbach
Ruslan Salakhutdinov
Sergey Levine

title: Search on the replay buffer: Bridging planning and reinforcement learning

venue: arXiv preprint arXiv:1906.05253,

authors:
Scott Fujimoto
David Meger
Doina Precup

title: Off-policy deep reinforcement learning without exploration

venue: arXiv preprint arXiv:1812.02900,

authors:
Sergiu Goschin
Ari Weinstein
Michael Littman

title: The cross-entropy method optimizes for quantiles

venue: In International Conference on Machine Learning,

authors:
David Held
Xinyang Geng
Carlos Florensa
Pieter Abbeel

title: Automatic goal generation for reinforcement learning agents

authors:
Peter Henderson
Riashat Islam
Philip Bachman
Joelle Pineau
Doina Precup
David Meger

title: Deep reinforcement learning that matters

venue: In Thirty-Second AAAI Conference on Artificial Intelligence,

authors:
Todd Hester
Matej Vecerik
Olivier Pietquin
Marc Lanctot
Tom Schaul
Bilal Piot
Dan Horgan
John Quan
Andrew Sendonaris
Ian Osband

title: Deep q-learning from demonstrations

authors:
Ahmed Hussein
Mohamed Medhat Gaber
Eyad Elyan
Chrisina Jayne

title: Imitation learning: A survey of learning methods

venue: ACM Computing Surveys (CSUR),

title: Learning to achieve goals

venue: In International Joint Conference on Artificial Intelligence (IJCAI),

authors:
Sham Kakade
John Langford

title: Approximately optimal approximate reinforcement learning

venue: In Proceedings of the Nineteenth International Conference on Machine Learning,

authors:
Aviral Kumar
Justin Fu
George Tucker
Sergey Levine

title: Stabilizing off-policy q-learning via bootstrapping error reduction

venue: arXiv preprint arXiv:1906.00949,

authors:
Timothy P Lillicrap
Jonathan J Hunt
Alexander Pritzel
Nicolas Heess
Tom Erez
Yuval Tassa
David Silver
Daan Wierstra

title: Continuous control with deep reinforcement learning

venue: arXiv preprint arXiv:1509.02971,

authors:
Corey Lynch
Mohi Khansari
Ted Xiao
Vikash Kumar
Jonathan Tompson
Sergey Levine
Pierre Sermanet

title: Learning latent plans from play

authors:
Shie Mannor
Reuven Y Rubinstein
Yohai Gat

title: The cross entropy method for fast policy search

venue: In Proceedings of the 20th International Conference on Machine Learning

authors:
Borislav Mavrin
Shangtong Zhang
Hengshuai Yao
Linglong Kong
Kaiwen Wu
Yaoliang Yu

title: Distributional reinforcement learning for efficient exploration

venue: arXiv preprint arXiv:1905.06125,

authors:
Shakir Mohamed
Danilo Jimenez Rezende

title: Variational information maximisation for intrinsically motivated reinforcement learning

venue: In Advances in neural information processing systems,

authors:
Ofir Nachum
Mohammad Norouzi
Dale Schuurmans

title: Improving policy gradient by exploring under-appreciated rewards

venue: arXiv preprint arXiv:1611.09321,

authors:
Ashvin V Nair
Vitchyr Pong
Murtaza Dalal
Shikhar Bahl
Steven Lin
Sergey Levine

title: Visual reinforcement learning with imagined goals

authors:
Mohammad Norouzi
Samy Bengio
Navdeep Jaitly
Mike Schuster
Yonghui Wu
Dale Schuurmans

title: Reward augmented maximum likelihood for neural structured prediction

venue: In Advances In Neural Information Processing Systems,

authors:
Junhyuk Oh
Yijie Guo
Satinder Singh
Honglak Lee

title: Self-imitation learning

authors:
Deepak Pathak
Parsa Mahmoudieh
Guanghao Luo
Pulkit Agrawal
Dian Chen
Yide Shentu
Evan Shelhamer
Jitendra Malik
Alexei A Efros
Trevor Darrell

title: Zero-shot visual imitation

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops,

authors:
Jan Peters
Stefan Schaal

title: Reinforcement learning by reward-weighted regression for operational space control

venue: In Proceedings of the 24th international conference on Machine learning,

title: Alvinn: An autonomous land vehicle in a neural network

authors:
Vitchyr Pong
Shixiang Gu
Murtaza Dalal
Sergey Levine

title: Temporal difference models: Modelfree deep rl for model-based control

venue: arXiv preprint arXiv:1802.09081,

authors:
Aravind Rajeswaran
Vikash Kumar
Abhishek Gupta
Giulia Vezzani
John Schulman
Emanuel Todorov
Sergey Levine

title: Learning complex dexterous manipulation with deep reinforcement learning and demonstrations

venue: arXiv preprint arXiv:1709.10087,

authors:
Stephane Ross
Geoffrey Gordon
Drew Bagnell

title: A reduction of imitation learning and structured prediction to no-regret online learning

venue: Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics,

authors:
Nikolay Savinov
Alexey Dosovitskiy
Vladlen Koltun

title: Semi-parametric topological memory for navigation

venue: arXiv preprint arXiv:1803.00653,

authors:
Tom Schaul
Daniel Horgan
Karol Gregor
David Silver

title: Universal value function approximators

venue: In International conference on machine learning,

authors:
John Schulman
Sergey Levine
Pieter Abbeel
Michael Jordan
Philipp Moritz

title: Trust region policy optimization

venue: Proceedings of the 32nd International Conference on Machine Learning,

authors:
Jan Storck
Sepp Hochreiter
Jürgen Schmidhuber

title: Reinforcement driven information acquisition in non-deterministic environments

venue: In Proceedings of the international conference on artificial neural networks, Paris,

authors:
Evangelos Theodorou
Jonas Buchli
Stefan Schaal

title: A generalized path integral control approach to reinforcement learning

venue: journal of machine learning research,

authors:
John N Tsitsiklis
Benjamin Van Roy

title: Analysis of temporal-diffference learning with function approximation

heading: 1 INTRODUCTION

text:
Reinforcement learning (RL) algorithms hold the promise of providing a broadly-applicable tool for automating control, and the combination of high-capacity deep neural network models with RL extends their applicability to settings with complex observations and that require intricate policies. However, RL with function approximation, including deep RL, presents a challenging optimization problem. Despite years of research, current deep RL methods are far from a turnkey solution: most popular methods lack convergence guarantees (Baird, 1995; Tsitsiklis & Van Roy, 1997) or require prohibitive numbers of samples (Schulman et al., 2015; Lillicrap et al., 2015). Moreover, in practice, many commonly used algorithms are extremely sensitive to hyperparameters (Henderson et al., 2018). Besides the optimization challenges, another usability challenge of RL is reward function design: although RL automatically determines how to solve the task, the task itself must be specified in a form that the RL algorithm can interpret and optimize. These challenges prompt us to consider whether there might exist a general method for learning behaviors without the need for complex, deep RL algorithms.
Imitation learning is an alternative paradigm to RL that provides a simple and straightforward approach for training control policies via standard supervised learning methods. By maximizing the likelihood of good actions provided by an expert demonstrator, supervised imitation learning can produce effective policies without the algorithmic complexities and optimization challenges of RL. Supervised learning algorithms in deep learning have matured to the point of being robust and reliable, and imitation learning algorithms have demonstrated success in acquiring behaviors robustly and reliably from high-dimensional sensory data such as images (Rajeswaran et al., 2017; Lynch
et al., 2019). The catch is that imitation learning methods require an expert demonstrator – typically a human – to provide a number of demonstrations of optimal behavior. Obtaining expert demonstrations can be challenging; the large number of demonstrations required limits the scalability of such algorithms. In this paper, we ask: can we use ideas from imitation learning to train effective policies without any expert demonstrations, retaining the benefits of imitation learning, but making it possible to learn goal-directed behavior autonomously from scratch?
The key observation for making progress on this problem is that, in the multi-task setting, trajectories that are generated by a suboptimal policy can serve as optimal examples for other tasks. In particular, in the setting where the tasks correspond to reaching different goal states, every trajectory is a successful demonstration for the state that it actually reaches. Similar observations have been made in prior works as well (Kaelbling, 1993; Andrychowicz et al., 2017; Nair et al., 2018; Mavrin et al., 2019; Savinov et al., 2018), but have been used to motivate data reuse in off-policy RL or semiparametric methods. Our approach will leverage this idea to obtain near-optimal goal-conditioned policies without RL or reward functions.
The algorithm that we study is, at its core, very simple: at each iteration, we run our latest goalconditioned policy, collect data, and then use this data to train a policy with supervised learning. Supervision is obtained by noting that each action that is taken is a good action for reaching the states that actually occurred in future time steps along the same trajectory. This algorithm resembles imitation learning, but is self-supervised. This procedure combines the benefits of goal-conditioned policies with the simplicity of supervised learning, and we theoretically show that this algorithm corresponds to a convergent policy learning procedure. While several prior works have proposed training goal-conditioned policies via imitation learning based on a superficially similar algorithm (Ding et al., 2019; Lynch et al., 2019), to our knowledge no prior work proposes a complete policy learning algorithm based on this idea that learns from scratch, without expert demonstrations. This procedure reaps the benefits of off-policy data re-use without the need for learning complex Q functions or value functions. Moreover, we can bootstrap our algorithm with a small number of expert demonstrations, such that it can continue to improve its behavior self supervised, without dealing with the challenges of combining imitation learning with off-policy RL.
The main contribution of our work is a complete algorithm for learning policies from scratch via goal-conditioned imitation learning, and to show that this algorithm can successfully train goalconditioned policies. Our theoretical analysis of self-supervised goal-conditioned imitation learning shows that this method optimizes a lower bound on the probability that the agent reaches the desired goal. Empirically, we show that our proposed algorithm is able to learn goal reaching behaviors from scratch without the need for an explicit reward function or expert demonstrations.

heading: 2 RELATED WORK

text:
Our work addresses the same problem statement as goal conditioned reinforcement learning (RL) (Andrychowicz et al., 2017; Held et al., 2018; Kaelbling, 1993; Nair et al., 2018), where we aim to learn a policy via RL that can reach different goals. Learning goal-conditioned policies is quite challenging, especially when provided only sparse rewards. This challenge can be partially mitigated by hindsight relabeling approaches that relabel goals retroactively (Kaelbling, 1993; Schaul et al., 2015; Pong et al., 2018; Andrychowicz et al., 2017). However, even with relabelling, the goalconditioned optimization problem still uses unstable off-policy RL methods. In this work, we take a different approach and leverage ideas from supervised learning and data relabeling to build offpolicy goal reaching algorithms which do not require any explicit RL. This allows GCSL to inherit the benefits of supervised learning without the pitfalls of off-policy RL. While, in theory, on-policy algorithms might be used to solve goal reaching problem as well, their inefficient use of data makes it challenging to apply these approaches to real-world settings.
Our algorithm is based on ideas from imitation learning (Billard et al., 2008; Hussein et al., 2017) via behavioral cloning (Pomerleau, 1989) but it is not an imitation learning method. While it is built on top of ideas from supervised learning, we are not trying to imitate externally provided expert demonstrations. Instead, we build an algorithm which can learn to reach goals from scratch, without explicit rewards. A related line of work (Hester et al., 2018; Brown et al., 2019) has explored how agents can leverage expert demonstrations to bootstrap the process of reinforcement learning. While GCSL is an algorithm to learn goal-reaching policies from scratch, it lends itself naturally
to bootstrapping from demonstrations. As we show in Section 5.4, GCSL can easily incorporate demonstrations into off-policy learning and continue improving, avoiding many of the challenges described in Kumar et al. (2019b).
Recent imitation learning algorithms propose methods that are closely related to GCSL. Lynch et al. (2019) aim to learn general goal conditioned policies from “play” data collected by a human demonstrator, and Ding et al. (2019) perform goal-conditioned imitation learning where expert goal-directed demonstrations are relabeled for imitation learning. However, neither of these methods are iterative, and both require human-provided expert demonstrations. Our method instead iteratively performs goal-conditioned behavioral cloning, starting from scratch. Our analysis shows that performing such iterated imitation learning on the policy’s own sampled data actually optimizes a lower bound on the probability of successfully reaching goals, without the need for any expert demonstrations.
The cross-entropy method (Mannor et al., 2003), self-imitation learning (Oh et al., 2018), rewardweighted regression (Peters & Schaal, 2007), path-integral policy improvement (Theodorou et al., 2010), reward-augmented maximum likelihood (Norouzi et al., 2016; Nachum et al., 2016), and proportional cross-entropy method (Goschin et al., 2013) selectively weight policies or trajectories by their performance during learning, as measured by then environment’s reward function. While these may appear procedurally similar to GCSL, our method is fully self-supervised, as it does not require a reward function, and is applicable in the goal-conditioned setting. Additionally, our algorithm continues to perform well in the purely off-policy setting, where no new data is collected, a key difference from other algorithms (Lynch et al., 2019; Ding et al., 2019).
A few works similar to ours in spirit study the problem of learning goal-conditioned policy without external supervision. Zero-shot visual imitation uses an inverse model with forward consistency to learn from novelty seeking behavior, but lacks convergence guarantees and requires learning a complex inverse model Pathak et al. (2018). Semi-parametric methods (Savinov et al., 2018; Eysenbach et al., 2019) learn a policy similar to ours but do so by building a connectivity graph over the visited states in order to navigate environments, which requires large memory storage and computation time that increases with the number of states.

heading: 3 PRELIMINARIES

text:
Goal Reaching We consider the goal reaching in an environment defined by the tuple 〈S,A, T , ρ(s0), T, p(g)〉. S andA correspond to the state and action spaces respectively, T (s′|s, a) to the transition kernel, ρ(s0) to the initial state distribution, T the horizon length, and p(g) to the distribution over goal states g ∈ S . We aim to find a time-varying goal-conditioned policy π(·|s, g, h): S × S × [T ]→ ∆(A), where ∆(A) is the probability simplex over the action space A and h is the remaining horizon. We will say that a policy is optimal if it maximizes the probability the specified goal is reached at the end of the episode:
J(π) = Eg∼p(g) [ Pπg (sT = g) ] . (1)
It is important to note here that we are not considering the notion of optimality to be finding the shortest path to the goal, but merely saying that the trajectory must reach the goal at the end of T time-steps. This problem can equivalently be cast in reinforcement learning. The modified state space S ′ = S × S × [T ] contains the current state, goal, and the remaining horizon; the modified transition kernel T ′ ((s′, g′, h′) | (s, g, h), a) = T (s′ | s, a) · 1(d = d′, h′ = h − 1) appropriately handles the modified state space; and the reward function r((s, g, h)) = 1(s = g, h = 0) depends on both the goal and the time step. Because of the special structure of this formulation, off-policy RL methods can relabel an observed transition ((s, g, h), a, (s′, g, h− 1)) to that of a different goal g′ and different horizon h′ like ((s, g′, h′), a, (s′, g′, h′ − 1)). A common approach is to relabel trajectories with the goal they actually reached instead of the commanded goal, and often referred to as hindsight experience replay (Andrychowicz et al., 2017; Nair et al., 2018).
Imitation Learning We consider algorithms for goal-reaching that use behavior cloning, a standard method for imitation learning. In behavior cloning for goal-conditioned policies, an expert policy provides demonstrations for reaching some target goals at the very last timestep, and we aim to find a policy that best predicts the expert actions from the observations. More formally,
given a dataset D = {{s00, a00, s01, a01, ....s0T }, {s10, a10, s11, a11, ....s1T }, ...}, and a set of stochastic, time-varying policies Π, the behavior-cloned policy corresponds to
πBC = arg max π∈Π E(sT−h,aT−h,sT )∼D [log π(aT−h|sT−h, sT , h)] .
Goal-conditioned imitation learning (Lynch et al., 2019) investigate a similar formalism that makes an additional assumption on the quality of the expert demonstrations: that the expert is optimal not just for reaching sT , but also optimal for reaching all the states s1, . . . sT−1 preceding it. This corresponding policy is
πGCIL = arg max π∈Π E(st,at,st+h)∼D [log πθ(at|st, st+h, h)] for t, h > 0 and t+ h ≤ T . (2)
Note that Lynch et al. (2019) implement a special case of this objective where the policy is independent of the horizon. In the next section, we will discuss how repeatedly alternating between data collection and goal-conditioned imitation learning can be used to learn a goal-reaching policy. Perhaps surprisingly, this procedure optimizes the objective in Equation 1, without relying on expert demonstrations.

heading: 4 LEARNING GOAL-CONDITIONED POLICIES WITH SELF-IMITATION

text:
The goal-conditioned imitation learning results in prior work show that expert demonstrations can provide supervision not only for the task the expert was aiming for, but also for reaching any state along the expert’s trajectory (Lynch et al., 2019; Ding et al., 2019). Can we design a procedure that uses goal-conditioned behavior cloning as a subroutine, that does not need any expert demonstrations, but that nonetheless optimizes a well-defined reward function?
In this work, we show how the idea of imitation learning with data relabeling can be re-purposed to construct a learning algorithm that is able to learn how to reach goals from scratch without any expert demonstrations. We shed light on the reasons that imitation learning with data relabeling is so powerful, and how building an iterative algorithm out of this procedure gives rise to a method that optimizes a lower bound on a reinforcement learning objective, while providing a number of benefits over standard RL algorithms. It is important to note here that we are not proposing an imitation learning algorithm, but an algorithm for learning how to reach goals from scratch without any expert demonstrations. We are simply leveraging ideas from imitation learning to build such a goal reaching algorithm.

heading: 4.1 GOAL REACHING VIA ITERATED IMITATION LEARNING

text:
First, consider goal conditioned imitation learning via behavioral cloning with demonstrations (Equation 2). This scheme works well given expert data D, but expert data is unavailable when we are learning to reach goals from scratch. Can we use goal conditioned behavior cloning to learn how to reach goals from scratch, without the need for any expert demonstrations?
To leverage behavior cloning when learning from scratch, we use the following insight: while an arbitrary trajectory from a sub-optimal policy may be suboptimal for reaching the intended goal, it may be optimal for reaching some other goal. In the goal-reaching formalism defined in Equation 1, recall a policy is optimal if it maximizes the probability that the goal is reached at the last timestep of an episode. This notion of optimality doesn’t have to take the direct or shortest path to the goal, it simply has to eventually reach the goal. Under this notion of optimality, we can use a simple data relabeling scheme to construct an expert dataset from an arbitrary set of trajectories. Consider a trajectory τ = {s1, a1, s2, a2, . . . , sT , aT } obtained by commanding the policy πθ(a|s, g, h) to reach some goal g. Although the actions may be suboptimal for reaching the commanded goal g, they do succeed at reaching the states st+1, st+2, . . . that occur later in the observed trajectory. More precisely, for any timestep t and horizon h, the action at in state st is likely to be a good action for reaching st+h in h timesteps, and thus useful supervision for πθ(·|st, st+h, h). This step of autonomous relabeling allows us to convert suboptimal trajectories into optimal goal reaching trajectories for different goals, without the need for any human intervention. To obtain a concrete algorithm, we can relabel all such timesteps and horizons in a trajectoryto create an expert dataset according to Dτ = {(st, at, st+h, h) : t, h > 0, t+ h ≤ T}. Because the relabelling procedure is valid for any horizon h ≤ T , we can relabel every such combination to create ( T 2 ) optimal tuples of (s, a, g, h) from a single trajectory.
This relabeled dataset can then be used to perform goal-conditioned behavioral cloning to update the policy πθ. While performing one iteration of goal conditioned behavioral cloning on the relabeled dataset is not immediately sufficient to reach all desired goals, we will show that this procedure does in fact optimize a lower bound on a well-defined reinforcement learning objective. As described concretely in Algorithm 1, the algorithm proceeds as follows: (1) Sample a goal from a target goal distribution p(g). (2) Execute the current policy π(a|s, g, h) for T steps in the environment to collect a potentially suboptimal trajectory τ . (3) Relabel the trajectory according to the previous paragraph to add ( T 2 ) new expert tuples (st, at, st+h, h) to the training dataset. (4) Perform supervised learning on the entire dataset to update the policy π(a|s, g, h) via maximum likelihood. We term this iterative procedure of sampling trajectories, relabelling them, and training a policy until convergence goalconditioned supervised learning (GCSL).
Algorithm 1 Goal-Conditioned Supervised Learning (GCSL) 1: procedure GCSL 2: Initialize policy π1(· | s, g, h) and dataset D((s, a, g, h)) 3: for k = 1, 2, 3, . . . do 4: Sample g ∼ p(g) and execute πk in environment trying to reach g 5: Log trajectory τ = (s0, a0, s1, a1, . . . sT , aT ) 6: Add tuples {(st, at, st+h, h) : t, h > 0, t+ h ≤ T} to the dataset D 7: Optimize the policy πk+1 ← arg maxπθ E(s,a,g,h)∼D [log πθ(a | s, g, h)] 8: end for 9: end procedure
The GCSL algorithm (described above) provides us with an algorithm that can learn to reach goals from the target distribution p(g) simply using iterated behavioral cloning. The resultant goal reaching algorithm is off-policy, uses low variance gradients, and is simple to implement and tune without the need for any explicit reward function engineering or demonstrations. Additionally, since this algorithm is off-policy and does not require a value function estimator, it is substantially easier to bootstrap from demonstrations when real demonstrations are available, as our experiments will show in Section 5.4.

heading: 4.2 THEORETICAL JUSTIFICATION

text:
While the GCSL algorithm is simple to implement, does this algorithm actually solve a well-defined policy learning problem? In this section, we argue that GCSL maximizes a lower bound on the probability for a policy to reach commanded goals.
We start by writing the probability that policy π conditioned on goal g produces trajectory τ as π(τ |g) = p(s0) ∏T h=0 π(at|st, g, h)T (st+1|st, at). We define G(τ) = sT as final state of a trajec-
tory. Recalling Equation 1, the target goal-reaching objective we wish to maximize is the probability of reaching a commanded goal:
J(π) = Eg∼p(g) [ Pπg (sT = g) ] = E g∼p(g),
τ∼π(τ |g) [1[G(τ) = g]] .
In the language of reinforcement learning, we are optimizing a multi-task problem where the reward in each task is an indicator that a goal was reached. The distribution over tasks (goals) of interest is assumed to be pre-specified as p(g). In the on-policy setting, GCSL performs imitation learning on trajectories commanded by the goals that were reached by the current policy, an objective that can be written as
JGCSL(π) = Eτ∼Eg [πold(·|g)] [ T∑ h=0 log π(at|st,G(τ), h) ] .
Here, πold corresponds to a copy of π through which gradients do not propagate, following the notation of Schulman et al. (2015). Our main result, which is derived in the on-policy data collection setting, shows that optimizing JGCSL(π) optimizes a lower bound on the desired objective, J(π) (proof in Appendix B):
Theorem 4.1. Let JGCSL and J be as defined above. Then, J(π) ≥ JGCSL(π) + C, Where C is a constant that does not depend on π.
Note that to prevent J(π) and JGCSL(π) from being zero, the probability of reaching a goal under π must be nonzero - in scenarios where such a condition does not hold, the bound remains true, albeit vacuous. The tightness of this bound can be controlled by the effective error in the GCSL objective - we present this, alongside a technical analysis of the bound in Appendix B.1. This indicates that in the regime with expressive policies where the loss function can be minimized well, GCSL will improve the expected reward.

heading: 5 EXPERIMENTS

text:
In our experimental evaluation, we aim to answer the following questions:
1. Does GCSL effectively learn goal-conditioned policies from scratch?
2. Does the performance of GCSL improve over successive iterations?
3. Can GCSL learn goal-conditioned policies from high-dimensional image observations?
4. Can GCSL incorporate demonstration data more effectively than standard RL algorithms?

heading: 5.1 EXPERIMENTAL DETAILS

text:
We consider a number of simulated control environments: 2-D room navigation, object pushing with a robotic arm, and the classic Lunar Lander game, shown in Figure 2. The tasks allow us to study the performance of our method under a variety of system dynamics, both low-dimensional state inputs and high-dimensional image observations, and in settings with both easy and difficult exploration. For each task, the target goal distribution corresponds to a uniform distribution over all reachable configurations. Performance of a method is quantified by the distance of the agent to the goal at the last timestep (not by the number of time-steps to the goal as is sometimes considered in goal reaching). We present full details about the environments, evaluation protocol, and hyperparameter choices in Appendix A.
For the practical implementation of GCSL, we parametrize the policy as a neural network that takes in state, goal, and horizon as input and outputs a parametrized action distribution. We find that omitting the horizon from the input to the policy still provides good results, despite the formulation suggesting that the optimal policy is most likely non-Markovian. We speculate that this is due to optimal actions changing only mildly with different horizons in our tasks. Full details about the implementation for GCSL are presented in Appendix A.1.

heading: 5.2 LEARNING GOAL-CONDITIONED POLICIES

text:
We evaluate the effectiveness of GCSL for reaching goals on the domains visualized in Figure 2, both from low-dimensional proprioception and from images. To better understand the performance of our algorithm, we compare to two families of reinforcement learning algorithms for solving goalconditioned tasks. First, we consider off-policy temporal-difference RL algorithms, particular TD3HER (Eysenbach et al., 2019; Held et al., 2018), which uses hindsight experience replay to more efficiently learn goal-conditioned value functions. TD3-HER requires significantly more machinery than our simple procedure: it maintains a policy, a value function, a target policy, and a target value function, all which are required to prevent degradation of the learning procedure. We also compare with on-policy reinforcement learning algorithms such as TRPO (Schulman et al., 2015) that cannot leverage data relabeling, but often provide more stable optimization than off-policy methods. Because these methods cannot relabel data, we provide an epsilon-ball reward corresponding to reaching the goal. Details for the training procedure for these comparisons, along with hyperpa-
rameter and architectural choices, are presented in Appendix A.2. Videos and further details can be found at https://sites.google.com/view/gcsl/.
We first investigate the learning performance of these algorithms from low-dimensional sensor observations, as shown in Figure 3. We find that on the pushing and lunar lander domains, GCSL is able to reach a larger set of goals consistently than either RL algorithm. Although TD3 is able to fully solve the navigation task, on the other domains which require synthesis of more challenging control behavior, the algorithm makes slow, if any, learning progress. Given a limited amount of data, TRPO performs poorly as it cannot relabel or reuse data, and so cannot match the performance of the other two algorithms. When scaling these algorithms to image-based domains, which we evaluate in Figure 4, we find that GCSL is still able to learn goal-reaching behaviors on several of these tasks. albeit slower than from state. For most tasks, from both state and images, GCSL is able to reach within 80% of the desired goals and learn at a rate comparable to or better than previously proposed off-policy RL methods. This evaluation demonstrates that simple iterative self-imitation is a competitive scheme for reaching goals in challenging environments which scales favorably with dimensionality of state and complexity of behaviors.

heading: 5.3 ANALYSIS OF LEARNING PROGRESS AND LEARNED BEHAVIORS

text:
To better understand the learning behaviors of the algorithm, we investigate how GCSL performs as we vary the quality and quantity of data, the policy class we optimize over, and the relabelling technique (Figure 5). Full details for these scenarios can be found in Appendix A.4.
First, we consider how varying the policy class can affect the performance of GCSL. In Section 5.1, we hypothesized that optimizing over a Markovian policy class would be performant over maintaining a non-Markovian policy. We find that allowing policies to be time-varying (”Time-Varying Policy” in Figure 5) can drastically speed up training on small domains, as these non-Markovian optimal policies can be fit more closely. However, on domains with active exploration challenges such as the Pusher, exploration using time-varying policies is ineffective, and degrades performance.
We investigate how the quality of the data in the dataset used to train the policy affects the learned policy. We consider two variations of GCSL: one which collects data using a fixed policy (”Fixed Data Collection” in Figure 5) and another which limits the size of the dataset to be
small, forcing all the data to be on-policy (”On-Policy” in Figure 5). When collecting data using a fixed policy, the learning progress of the algorithm demonstratedly decreases, which indicates that the iterative loop of collecting data and training the policy is crucial for converging to a performant solution. By forcing the data to be all on-policy, the algorithm cannot utilize the full set of experiences seen thus far and must discard data. Although this on-policy process remains effective on simple domains, the technique leads to slower learning progress on tasks requiring more challenging control.

heading: 5.4 INITIALIZING WITH DEMONSTRATIONS

text:
Because GCSL can perform self-imitation from arbitrary data sources, the algorithm is amenable to initialization from prior exploration or from demonstrations. In this section, we study how GCSL performs when incorporating expert demonstrations as initializations. Our results comparing GCSL and TD3 in this setting corroborate the existing hypothesis that off-policy value function RL algorithms are challenging to integrate with initialization from demonstrations Kumar et al. (2019a).
We consider the setting where an expert provides a set of demonstration trajectories, each for reaching a different goal. GCSL requires no modifications to incorporate these demonstrations - it simply adds the expert data to the initial dataset, and begins the training procedure. In contrast, multiple prior works have proposed additional algorithmic changes to off-policy TD-based methods to in-
corporate data from expert demonstrations (Kumar et al., 2019a). We compare the performance of GCSL to one such variant of TD3-HER in incorporating expert demonstrations on the robotic pushing environment in Figure 6 (Details in Appendix A.5). Although TD3 achieves better performance with the demonstrations than when learning from scratch, it drops in performance at the beginning of training, which means TD3 regresses from the initial behavior-cloned policy, an undesirable characteristic for initializing from demonstrations. In contrast, GCSL scales favorably, learns faster than from scratch, and effectively incorporates the expert demonstrations. We believe this benefit largely comes from not needing to train an explicit critic, which can be unstable when trained using highly off-policy data such as demonstrations (Kumar et al., 2019b).
6 DISCUSSION AND FUTURE WORK
In this work, we proposed GCSL, a simple algorithm for learning goal-conditioned policies that uses imitation learning, while still learning autonomously from scratch. This method is exceptionally simple, relying entirely on supervised learning to learn policies by relabeling its own previously collected data. This method can easily utilize off-policy data, seamlessly incorporate expert demonstrations when they are available, and can learn directly from image observations. Although several prior works have explored similar algorithm designs in an imitation learning setting (Ding et al., 2019; Lynch et al., 2019), to our knowledge our work is the first to derive a complete iterated algorithm based on this principle for learning from scratch, and the first to theoretically show that this method optimizes a lower bound on a well-defined reinforcement learning objective.
While our proposed method is simple, scalable, and readily applicable, it does have a number of limitations. The current instantiation of this approach provides limited facilities for effective exploration, relying entirely on random noise during the rollouts to explore. More sophisticated exploration methods, such as exploration bonuses (Mohamed & Rezende, 2015; Storck et al., 1995), are difficult to apply to our method, since there is no explicit reward function that is used during learning. However, a promising direction for future work would be to reweight the sampled rollouts based on novelty to effectively incorporate a novelty-seeking exploration procedure. A further direction for future work is to study whether the simplicity and scalability of our method can make it possible to perform goal-conditioned reinforcement learning on substantially larger and more varied datasets. This can in principle enable wider generalization, and realize a central goal in goal-conditioned reinforcement learning — universal policies that can succeed at a wide range of tasks in diverse environments.

heading: A EXPERIMENTAL DETAILS

text:
A.1 GOAL-CONDITIONED SUPERVISED LEARNING (GCSL)
GCSL iteratively performs maximum likelihood estimation using a dataset of relabelled trajectories that have been previously collected by the agent. Here we present details about the policy class, data collection procedure, and other design choices. We parametrize a time-invariant policy using a neural network which takes as input state and goal, and returns probabilities for a discretized grid of actions of the action space. For the state-based domains, the neural network is a feedforward network with two hidden layers of size 400 and 300 respectively. For the image-based domains, both the observation image and the goal image are first preprocessed through three convolutional layers, with kernel size 5, 3, 3 and channels 16, 32, 32 respectively. When executing in the environment, data is sampled according to an exploratory policy which increases the temperature of the current policy: πexplore(a|s, g) ∝ π(a|s, g)α. The replay buffer stores trajectories and relabels on the fly, with the size of the buffer subject only to memory constraints.
A.2 RL COMPARISONS
We perform experimental comparisons with TD3-HER (Fujimoto et al., 2018; Andrychowicz et al., 2017). We relabel transitions as ((s, g), a, (s′, g)) gets relabelled to ((s, g′), a, (s′, g′)), where g′ = g with probability 0.1, g′ = s′ with probability 0.5, and g′ = st for some future state in the trajectory st with probability 0.4. As described in Section 3, the agent receives a reward of 1 and the trajectory ends if the transition is relabelled to g′ = s′, and 0 otherwise. Under this formalism, the optimal Qfunction, Q ∗ (s, a, g) = exp(−T (s, g)), where T (s, g) is the minimum expected time to go from s to g. Both the Q-function and the actor for TD3 are parametrized as neural networks, with the same architecture (except final layers) for state-based domains and image domains as those for GCSL.
We also compare to TRPO (Schulman et al., 2015), an on-policy RL algorithm. Because TRPO is on-policy, we cannot relabel goals, and so we provide a surrogate -ball indicator reward function: r(s, g) = 1(d(s, g) < ), where is chosen appropriately for each environment. To maximize the data efficiency of TRPO, we performed a coarse hyperparameter sweep over the batch size for the algorithm. Just as with TD3, we mimic the same neural network architecture for the parametrizations of the policies as GCSL.
A.3 TASK DESCRIPTIONS
For each environment, the goal space is identical to the state space. For the image-based experiments, images were rendered at resolution 84× 84× 3. 2D Room Navigation This environment requires an agent to navigate to points in an environment with four rooms that connect to adjacent rooms. The state space has two dimensions, consisting of the cartesian coordinates of the agent. The agent has acceleration control, and the action space has two dimensions. The distribution of goals p(g) is uniform on the state space, and the agent starts in a fixed location in the bottom left room.
Robotic Pushing This environment requires a Sawyer manipulator to move a freely moving block in an enclosed play area with dimensions 40 cm × 20 cm. The state space is 4-dimensional, consistsing of the cartesian coordinates of the end-effector of the sawyer agent and the cartesian coordinates of the block. The Sawyer is controlled via end-effector position control with a threedimensional action space. The distribution of goals p(g) is uniform on the state space (uniform block location and uniform end-effector location), and the agent starts with the block and end-effector both in the bottom-left corner of the play area.
Lunar Lander This environment requires a rocket to land in a specified region. The state space includes the normalized position of the rocket, the angle of the rocket, whether the legs of the rocket are touching the ground, and velocity information. Goals are sampled uniformly along the landing region, either touching the ground or hovering slightly above, with zero velocity.
A.4 ABLATIONS
In Section 5.3, we analyzed the performance of the following variants of GCSL (Figure 7).
1. Inverse Model - This model relabels only states and goals that are one step apart: {(st, at, st+h, h) : t > 0, h = 1}
2. On-Policy Only the most recent 10000 transitions are stored and trained on. 3. Fixed Data Collection Data is collected according to a uniform policy over actions. 4. Time-Varying Policy Policies are are conditioned on the remaining horizon. Alongside
the state and goal, the policy gets a reverse temperature encoding of the remaining horizon as input.
A.5 INITIALIZING WITH DEMONSTRATIONS
We train an expert policy for robotic pushing using TRPO with a shaped dense reward function, and collect a dataset of 200 trajectories, each corresponding to a different goal. To train GCSL using these demonstrations, we simply populate the replay buffer with these trajectories at the beginning of training, and optimize the GCSL objective using these trajectories to warm-start the algorithm. Initializing a value function method using demonstrates requires significantly more attention: we perform the following procedure. First, we perform goal-conditioned behavior cloning to learn an initial policy πBC . Next, we collect 200 new trajectories in the environment using a uniform data collection scheme. Using this dataset of 400 trajectories, we perform policy evaluation on πBC to learn QπBC using policy evaluation via bootstrapping. Having trained such an estimate of the Qfunction, we initialize the policy and Q-function to these estimates, and run the appropriate value function RL algorithm.

heading: B PROOF OF THEOREM 4.1

text:
We will assume a discrete state space in this proof, and denote a trajectory as τ = {s0, a0, . . . , sT , aT }. Let the notation G(τ) = sT denote the final state of a trajectory, which represents the goal that the trajectory reached. As there can be multiple paths to a goal, we let τg = {τ : G(τ) = g} denote the set of trajectories that reach a particular goal g. We abbreviate a policy’s trajectory distribution as π(τ |g) = p(s0) ∏T t=0 π(at|st, g)T (st+1|st, at). The target goal-reaching objective we wish to optimize is the probability of reaching a commanded goal,
J(π) = Eg∼p(g),τ∼π(τ |g)[1[G(τ) = g]]
The distribution over tasks (goals) is assumed to be pre-specified as p(g). GCSL optimizes the following objective, where the log-likelihood of the actions conditioned on the goals actually reached by the policy, G(τ):
JGCSL(π) = Eτ∼Eg[πold(·|g)] [ T∑ t=0 log π(at|st,G(τ)) ]
Here, using notation from Schulman et al. (2015), πold is a copy of the policy π through which gradients do not propagate. To analyze how this objective relates to J(π), we first analyze the relationship between J(π) and a surrogate objective, given by
Jsurr(π) = Eg∼p(g) ∑ τ∈τg πold(τ |g) log π(τ |g)  As Jsurr(π) and J(π) have the same gradient for all π, the differ by some π-independent constant C1, i.e. J(π) = Jsurr(π) + C1.
We can now lower-bound the surrogate objective via the following:
Jsurr(π) = Eg∼p(g) ∑ τ∈τg πold(τ |g) log π(τ |g)  = Eg∼p(g)
[∑ τ 1[G(τ) = g]πold(τ |g) log π(τ |G(τ)) ] = ∑ g p(g) ∑ τ log π(τ |G(τ))πold(τ |g)1[G(τ) = g]
= ∑ τ log π(τ |G(τ)) ∑ g p(g)πold(τ |g)1[G(τ) = g]
= ∑ τ log π(τ |G(τ)) ∑ g p(g)πold(τ |g)− ∑ τ log π(τ |G(τ)) ∑ g p(g)πold(τ |g)1[G(τ) 6= g]
(3) ≥ ∑ τ log π(τ |G(τ)) ∑ g p(g)πold(τ |g)
= Eτ∼Eg[πold(τ |g)][log π(τ |G(τ))].
The final line is our goal-relabeling objective: we train the policy to reach goals we reached g′. The inequality holds since log π(τ) is always negative. The inequality is loose by a term related to the probability of not reaching the commanded goal.
Since the initial state and transition probabilities do not depend on the policy, we can simplify log π(τ |G(τ)) as (by absorbing non π-dependent terms into C2):
Eτ∼Eg [πold(τ |g)][log π(τ |G(τ))] = Eτ∼Eg [πold(τ |g)] [ log p(s0) + T∑ t=0 log π(at|st,G(τ)) + log T (st+1|st, at) ]
= Eτ∼Eg [πold(τ |g)] [ T∑ t=0 log π(at|stG(τ)) ] + C2
= JGCSL(π) + C2.
Combining this result with the bound on the expected return completes the proof, namely that J(π) ≥ JGCSL(π) + C1 + C2. Note that in order for J(π) and JGCSL(π) to not be degenerate, the probability of reaching a goal under πold must be non-zero. This assumption is reasonable, and matches the assumptions on ”exploratory data-collection” and full-support policies that are required by Q-learning and policy gradient convergence guarantees.
B.1 QUANTIFYING THE QUALITY OF THE APPROXIMATION
We now seek to better understand the gap introduced by Equation 3 in the analysis above. We define Pπold(G(τ) 6= g) to be the probability of failure under πold and p(g). We overload the notation πold(τ) = Eg[πold(τ |g)], and additionally define pwrong(τ) and pright(τ)the conditional distribution of trajectories under πold given that it did not reach and did the commanded goal respectively.
In the following section, we show that the gap can be controlled by the probability of making a mistake, Pπold(G(τ) 6= g), and DTV (pwrong(τ), pright(τ)), a measure of the difference between the distribution of trajectories that must be relabelled and those not.
We rewrite Equation 3 as follows: Jsurr(π) = ∑ τ log π(τ |G(τ)) ∑ g p(g)πold(τ |g)− ∑ τ log π(τ |G(τ)) ∑ g p(g)πold(τ |g)1[G(τ) 6= g]
= Eτ∼πold [log π(τ |G(τ))]− Pπold (G(τ) 6= g))Eτ∼pwrong(τ) [log π(τ |G(τ))]
Define D to be the Radon-Nikodym derivative of pwrong(τ) wrt πold(τ)
= Eτ∼πold [log π(τ |G(τ))]− Pπold (G(τ) 6= g))Eτ∼πold [D log π(τ |G(τ))] = (1− Pπold (G(τ) 6= g))Eτ∼πold [log π(τ |G(τ))]
+ Pπold (G(τ) 6= g))Eτ∼πold [(1−D) log π(τ |G(τ))]︸ ︷︷ ︸ Relevant Gap
The first term is affine with respect to the GCSL loss, so the second term is the error we seek to understand.
|Relevant Gap| = Pπold (G(τ) 6= g) |Eτ∼πold [(1−D) log π(τ |G(τ))]| ≤ Pπold(G(τ) 6= g)Eτ∼πold [|1−D|]Eτ∼πold [log π(τ |G(τ))] = 2Pπold(G(τ) 6= g)DTV (Eg[πold(τ |g)], pwrong(τ))Eτ∼πold [log π(τ |G(τ))] = 2Pπold(G(τ) 6= g)(1− Pπold(G(τ) 6= g))DTV (pright(τ), pwrong(τ))Eτ∼πold [log π(τ |G(τ))]
The inequality is maintained because of the nonpositivity of log π(τ), and the final step holds because πold(τ) is a mixture of pwrong(τ) and pright(τ). This derivation shows that the gap between Jsurr and JGCSL (up to affine consideration) can be controlled by 1) the probability of reaching the wrong goal and 2) the divergence between the conditional distribution of good trajectories and those which must be relabelled. As either term goes to 0, the bound becomes tight.
We now show that sufficiently optimizing the GCSL objective causes the probability of reaching the wrong goal to be bounded close to 0, and thus bounds the gap close to 0.
Suppose we collect trajectories from a policy πdata. Mimicking the notation from before, we define πdata(τ) = Eg∼p(g)[πdata(τ |g)]. For convenience, we define π∗data(at|st, g) ∝∫ τ\at πdata(τ)1(G(τ) = g)1(st(τ) = st) to be the conditional distribution of actions for a given state given that the goal g is reached at the end of the trajectory. If this conditional distribution is not defined, we let π∗data(at|st, g) be uniform, so that π∗data(at|st, g) is well-defined for all states, goals, and timesteps. Lemma B.1. Consider an environment with deterministic dynamics in which all goals are reachable in T timesteps, and a behavior policy πdata which is exploratory: πdata(at|st, g) > 0 for all (a, s, g) (for example epsilon-greedy exploration). Suppose the GCSL objective is sufficiently optimized, so that for all s, g ∈ S, and time-steps t ∈ {1, . . . , T}, DTV (π(at|st, g), π∗data(at|st, g)) ≤ . Then, the probability of making a mistake Pπ(G(τ) 6= g) can be bounded above by T
Proof. We show the result through a coupling argument, similar to Schulman et al. (2015); Kakade & Langford (2002); Ross et al. (2011). Because DTV (π(at|st, g), π∗data(at|st, g)) ≤ , we can define a (1 − )-coupled policy pair (π, π∗data), which takes differing actions with probability . By a union bound over all timesteps, the probability that π and π∗data take any different actions throughout the trajectory is bounded by T , and under assumptions of deterministic dynamics, take the same trajectory with probability 1 − T . Under assumption of deterministic dynamics and all goals being reachable from the initial state distribution in T timesteps, the policy π∗data(at|st, g) satisfies Pπ∗data(G(τ) 6= g) = 0. Because π ∗ data reaches the goal with probability 1, this implies that π must also reach the goal with probability at least 1− T . Thus, Pπ(G(τ) 6= g) ≤ T .

heading: C EXAMPLE TRAJECTORIES

text: Figure 8 below shows parts of the state along trajectories produced by GCSL. In Lunar Lander, this state is captured by the rocket’s position, and in 2D Room Navigation it is the agent’s position. While these trajectories do not always take the shortest path to the goal, they do often take fairly direct paths to the goal from the initial position avoiding very roundabout trajectories.


summaries: This paper addresses security of distributed optimization algorithm under Byzantine failures. These failures usually prevent convergence of training neural network models. Focusing on the asynchronous SGD algorithm implemented with a parameter-server, the authors propose to use stochastic line search ideas to detect whether the gradients are good descent directions or not. It applies to a general scenario including repeated and unbounded Byzantine failures.

summaries: This paper investigates the security of distributed asynchronous SGD. Authors propose Zeno++, worker-server asynchronous implementation of SGD which is robust to Byzantine failures. To ensure that the gradients sent by the workers are correct, Zeno++ server scores each worker gradients using a “reference” gradient computed on a “secret” validation set.  If the score is under a given threshold, then the worker gradient is discarded.

abstractText: We propose Zeno++, a new robust asynchronous Stochastic Gradient Descent (SGD) procedure which tolerates Byzantine failures of the workers. In contrast to previous work, Zeno++ removes some unrealistic restrictions on workerserver communications, allowing for fully asynchronous updates from anonymous workers, arbitrarily stale worker updates, and the possibility of an unbounded number of Byzantine workers. The key idea is to estimate the descent of the loss value after the candidate gradient is applied, where large descent values indicate that the update results in optimization progress. We prove the convergence of Zeno++ for non-convex problems under Byzantine failures. Experimental results show that Zeno++ outperforms existing approaches.

authors:
D. Alistarh
Z. Allen-Zhu
J. Li

title: Byzantine stochastic gradient descent

venue: arXiv preprint arXiv:1803.08917,

authors:
P. Blanchard
R. Guerraoui
J. Stainer

title: Machine learning with adversaries: Byzantine tolerant gradient descent

venue: In Advances in Neural Information Processing Systems,

authors:
X. Cao
L. Lai

title: Robust distributed gradient descent with arbitrary number of byzantine attackers

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

authors:
L. Chen
H. Wang
Z.B. Charles
D.S. Papailiopoulos

title: Draco: Byzantine-resilient distributed training via redundant gradients

venue: In ICML,

authors:
Y. Chen
L. Su
J. Xu

title: Distributed statistical machine learning in adversarial settings: Byzantine gradient descent

venue: POMACS,

authors:
G. Damaskinos
E.M.E. Mhamdi
R. Guerraoui
R. Patra
M. Taziki

title: Asynchronous byzantine machine learning

venue: arXiv preprint arXiv:1802.07928,

authors:
S. Dutta
G. Joshi
S. Ghosh
P. Dube
P. Nagpurkar

title: Slow and stale gradients can win the race: Error-runtime trade-offs in distributed sgd

authors:
J. Feng
H. Xu
S. Mannor

title: Distributed robust learning

venue: arXiv preprint arXiv:1409.5937,

title: Robust statistics. In International Encyclopedia of Statistical Science, pages 1248–1251

authors:
A. Krizhevsky
G. Hinton

title: Learning multiple layers of features from tiny images

authors:
L. Lamport
R. Shostak
M. Pease

title: The byzantine generals problem

venue: ACM Transactions on Programming Languages and Systems (TOPLAS),

authors:
L. Lamport
R.E. Shostak
M.C. Pease

title: The byzantine generals problem

venue: ACM Trans. Program. Lang. Syst.,

authors:
X. Lian
W. Zhang
C. Zhang
J. Liu

title: Asynchronous decentralized parallel stochastic gradient descent

authors:
S. Merity
N.S. Keskar
R. Socher

title: Regularizing and Optimizing LSTM Language Models

venue: arXiv preprint arXiv:1708.02182,

title: An Analysis of Neural Language Modeling at Multiple Scales

venue: arXiv preprint arXiv:1803.08240,

authors:
E.M.E. Mhamdi
R. Guerraoui
S. Rouault

title: The hidden vulnerability of distributed learning in byzantium

venue: arXiv preprint arXiv:1802.07927,

title: Gradient methods for minimizing functionals

venue: Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki,

authors:
L. Su
N.H. Vaidya

title: Fault-tolerant multi-agent optimization: Optimal iterative distributed algorithms

venue: In PODC,

title: Defending non-bayesian learning against adversarial attacks

venue: arXiv preprint arXiv:1606.08883,

authors:
C. Xie
O. Koyejo
I. Gupta

title: Phocas: dimensional byzantine-resilient stochastic gradient descent

venue: arXiv preprint arXiv:1805.09682,

authors:
C. Xie
O.O. Koyejo
I. Gupta

title: Zeno: Byzantine-suspicious stochastic gradient descent

authors:
D. Yin
Y. Chen
K. Ramchandran
P. Bartlett

title: Byzantine-robust distributed learning: Towards optimal statistical rates

venue: arXiv preprint arXiv:1803.01498,

authors:
S. Zheng
Q. Meng
T. Wang
W. Chen
N. Yu
Z.-M. Ma
T.-Y. Liu

title: Asynchronous stochastic gradient descent with delay compensation

venue: In Proceedings of the 34th International Conference on Machine Learning-Volume

authors:
Z. Zhou
P. Mertikopoulos
N. Bambos
P.W. Glynn
Y. Ye
L.-J. Li
L. Fei-Fei

title: Distributed asynchronous optimization with unbounded delays: How slow can you go

authors:
M. Zinkevich
J. Langford
A.J. Smola

title: Slow learners are fast

heading: 1 INTRODUCTION

text:
Synchronous training and asynchronous training are the two most common paradigms of distributed machine learning. On the one hand, synchronous training requires, periodically, the global updates at the server to be blocked until all the workers respond. In contrast, for asynchronous training, the server updates the global model immediately after a worker responds. Theoretical and experimental analysis (Dutta et al., 2018) suggests that synchronous training is more stable with less noise, but can also be slowed down by the global barrier across all the workers. Asynchronous training is generally faster, but needs to address instability and noisiness due to staleness. In this paper, we focus on asynchronous training.
We study the security of distributed asynchronous Stochastic Gradient Descent (SGD) in a centralized worker-server architecture, also known as the Parameter Server (or PS) architecture. In the PS architecture, there are server nodes and worker nodes. When combined with an asynchronous SGD approach, each worker pulls the global model from the servers, estimates the gradients using the local portion of the training data, then sends the gradient estimates to the servers. The servers update the model as soon as a new gradient is received from any worker.
The security of machine learning has gained increasing attention in recent years. In particular, tolerance to Byzantine failures (Blanchard et al., 2017; Chen et al., 2017; Yin et al., 2018; Feng et al., 2014; Su and Vaidya, 2016a;b; Xie et al., 2018b; Alistarh et al., 2018; Cao and Lai, 2018) has become an important topic in the distributed machine learning literature. Byzantine failures are well-studied for the distributed systems (Lamport et al., 1982a). However, in distributed machine learning, Byzantine failures have unique properties. In brief, the goal of Byzantine workers is to prevent convergence of the model training. By construction, Byzantine failures (Lamport et al., 1982b) assume the worst case, i.e., the Byzantine workers can behave arbitrarily. Such failures may be caused by a variety of reasons including but not limited to: hardware/software bugs, vulnerable communication channels, poisoned datasets, or malicious attackers. To make things worse, groups of Byzantine workers can collude, potentially resulting in more harmful attacks. It is also clear that as the worst case, Byzantine failures generalize benign failures such as hardware or software errors.
Unlike previous work (Damaskinos et al., 2018), we tackle Byzantine tolerance in a more general scenario. The Byzantine tolerance of asynchronous SGD is challenging in this case because of:
• Asynchrony. The lack of synchrony incurs additional noise for the stochastic gradients. Such noise makes it more difficult to distinguish the Byzantine gradients from the benign ones, especially as Byzantine behavior may exacerbate staleness.
• Unpredictable successive updates. The lack of synchronous scheduling makes it possible for the server to receive updates from Byzantine workers successively. Thus, even in the standard scenario,
where less than half of the workers are Byzantine, the server can be suffocated by successive Byzantine gradients.
• Unbounded number of Byzantine workers. For the Byzantine tolerance in fully asynchronous training, the assumption of a bounded number of Byzantine workers is meaningless. In Byzantinetolerant synchronous training (Blanchard et al., 2017; Chen et al., 2017; Yin et al., 2018; Xie et al., 2018b;a), the servers can compare the candidate gradients with each other, and utilize the majority assumption to filter out the harmful gradients, or use robust aggregation to bound the error. However, such strategies are infeasible in asynchronous training, since there is nothing to compare to or aggregate. Aggregating the successive gradients is also meaningless since the successive gradients could all be pushed by the same Byzantine worker. Furthermore, although most of the previous work (Blanchard et al., 2017; Chen et al., 2017; Yin et al., 2018; Feng et al., 2014; Su and Vaidya, 2016a;b; Alistarh et al., 2018; Cao and Lai, 2018) assumes a majority of honest workers, this requirement is not guaranteed to be satisfied in practice.
The key idea of our approach is to estimate the descent of the loss value after the candidate gradient is applied to the model parameters, based on the Byzantine-tolerant synchronous SGD algorithm, Zeno (Xie et al., 2018b). Intuitively, if the loss value decreases, the candidate gradient is likely to result in optimization progress. For computational efficiency, we also propose a lazy update.
To the best of our knowledge, this paper is the first to theoretically and empirically study Byzantinetolerant fully asynchronous SGD with anonymous workers, and potentially an unbounded number of Byzantine workers. In summary, our contributions are:
• We propose Zeno++, a new approach for Byzantine-tolerant fully asynchronous SGD with anonymous workers.
• We show that Zeno++ tolerates Byzantine workers without any limit on either the staleness or the number of Byzantine workers.
• We prove the convergence of Zeno++ for non-convex problems. • Experimental results validate that 1) existing algorithms may fail in practical scenarios, and 2)
Zeno++ gracefully handles such cases.

heading: 2 RELATED WORK

text:
Most of the existing Byzantine-tolerant SGD algorithms focus on synchronous training. Chen et al. (2017); Su and Vaidya (2016a;b); Yin et al. (2018); Xie et al. (2018a) use robust statistics (Huber, 2011) including the geometric median, coordinate-wise median, and trimmed mean as Byzantinetolerant aggregation rules. Blanchard et al. (2017); Mhamdi et al. (2018) propose Krum and its variants, which select the candidates with minimal local sum of Euclidean distances. Alistarh et al. (2018) utilize historical information to identify harmful gradients. Chen et al. (2018) use coding theory and majority voting to recover correct gradients. Most of these synchronous algorithms assume that most of the workers are non-Byzantine. However, in practice, there are no guarantees that the number of Byzantine workers can be controlled. Xie et al. (2018b); Cao and Lai (2018) propose synchronous SGD algorithms for an unbounded number of Byzantine workers.
Recent years have witnessed an increasing number of large-scale machine learning algorithms, including asynchronous SGD (Zinkevich et al., 2009; Lian et al., 2018; Zheng et al., 2017; Zhou et al., 2018). Damaskinos et al. (2018) proposed Kardam, which to our knowledge is the only prior work to address Byzantine-tolerant asynchronous training. Kardam utilizes the Lipschitzness of the gradients to filter out outliers. However, Kardam assumes a threat model much weaker than ours. The major differences in the threat model are listed as follows:
• Verification of worker identity. Unlike Kardam, we do not require verifying the identities of the workers when the server receives gradients. Kardam uses the so-called empirical Lipschitz coefficient, to test the benignity of the gradient sent by a specific worker. Such a mechanism keeps the record of the empirical Lipschitz coefficient of each worker. Thus, whenever a gradient is received, the Kardam server must be able to identify the identity/index of the worker. However, since Byzantine workers can behave arbitrarily, they can fake their identities/indices when sending gradients to the servers. Thus, Kardam assumes a threat model much weaker than the traditional
Byzantine failure/threat model. Note that for synchronous training, the server can partially counter the index spoofing attack by simply filtering out all the gradients with duplicated indices. However, such an approach is infeasible for asynchronous training.
• Bounded staleness of workers/limit of successive gradients. Unlike Kardam, we do not require bounded staleness of the workers. Kardam requires that the number of gradients successively received from a single worker is bounded above. To be more specific, on the server, any sequence of successively received gradients of length 2q + 1 must contain at least q + 1 gradients from honest workers. However, in real-world asynchronous training, such an assumption is very difficult to satisfy.
• A majority of honest workers. Unlike Kardam, we do not require a majority of honest workers. Kardam requires that the number of Byzantine workers is less than one-third of the total number of workers – much stronger restriction than the standard setting that allows for the number of Byzantine workers to be up to 50% of the total number of workers. Zeno++ further extends this guarantee to allow for not only 50%, but also a majority of Byzantine workers.

heading: 3 MODEL

text:
We consider the following optimization problem: minx∈Rd F (x), where F (x) = 1 m ∑ i∈[m] Ezi∼Dif(x; zi), for ∀i ∈ [m], zi is sampled from the local data Di on the ith device.
We solve this problem in a distributed manner with m workers. Each worker trains the model on local data. In each iteration, the ith worker will sample n independent data points from the dataset Di, and compute the gradient of the local empirical loss Fi(x) = 1n ∑n j=1 f(x; zi,j),∀i ∈ [m], where zi,j ∼ Di is the jth sampled data on the ith worker. When there are no Byzantine failures, the servers update the model whenever a new gradient is received:
xt+1 = xt − γtgτ , gτ = 1
n ∑ j∈[n] ∇f(xτ ; zi,j), τ ≤ t, i ∈ [m].
When there are Byzantine failures, gτ can be replaced by arbitrary value (Damaskinos et al., 2018). Formally, we define the threat model as follows. Definition 1. (Threat Model). When the server receives a gradient estimator g̃τ , it is either correct or Byzantine. If sent by a Byzantine worker, g̃τ is assigned arbitrary value. If sent by an honest worker, the correct gradient is 1n ∑n j=1∇f(xτ ; zi,j), τ ≤ t, i ∈ [m]. Thus, we have
g̃τ = { arbitrary value, if sent by a Byzantine worker, 1 n ∑n j=1∇f(xτ ; zi,j), τ ≤ t, i ∈ [m], otherwise.
We assume that q out of m workers are Byzantine, where q ≤ m. Furthermore, the indices of Byzantine workers can change across different iterations.

heading: 4 METHODOLOGY

text: In this section, we introduce Zeno++, a Byzantine-tolerant asynchronous SGD algorithm based on inner-product validation. Zeno++ is a computationally efficient version of its prototype: Zeno+.

heading: 4.1 ZENO+

text:
Like Zeno (Xie et al., 2018b), we compute a score for each candidate gradient estimator by using the stochastic zero-order oracle. However, in contrast to the existing synchronous SGD with majority-
based aggregation methods, we need a hard threshold to decide whether a gradient is accepted, as sorting is not meaningful in asynchronous settings. This descent score is described next.
Definition 2. (Stochastic Descent Score (Xie et al., 2018b)) Denote fs(x) = 1ns ∑ns j=1 f(x; zj), where zj’s are i.i.d. samples drawn from S, where S 6= Di,∀i ∈ [m], and ns is the batch size of fs(·). For any gradient estimator (correct or Byzantine) g, model parameter x, learning rate γ, and a constant weight ρ > 0, we define its stochastic descent score as follows: Scoreγ,ρ(g, x) = fs(x)− fs(x− γg)− ρ‖g‖2. Remark 1. Note that we assume that the dataset S for computing fs(·) is different from the training dataset, e.g., can be a separated validation dataset. In other words, S 6= D1 6= · · · 6= Dm 6= ∪mi=1Di.
The score defined in Definition 2 is composed of two parts: the estimated descent of the loss function, and the magnitude of the update. The score increases when the estimated descent of the loss function, fs(x)− fs(x− γg), gets larger. We penalize the score by −ρ‖g‖2, so that the change of the model parameter will not be too large. A large descent suggests faster convergence. Observe that even when a gradient is Byzantine, a small magnitude indicates that it will be less harmful to the model.
Using the stochastic descent score, we can set a hard threshold parameterized by to filter out candidate gradients with relatively small scores. The detailed algorithm is outlined in Algorithm 1.
Algorithm 1 Zeno+ Server: 1: x0 ← rand(), t← 1 . Initialization 2: repeat 3: Randomly sample zj ∼ S, ∀j ∈ [ns] to compute fs (Note: S 6= D1 6= · · · 6= Dm) 4: Receive g̃ from an arbitrary worker 5: Normalize g = cg̃ such that ‖g‖2 = ‖∇fs(xt−1)‖2, c > 0 6: if Scoreγ,ρ(g, xt−1) ≥ −γ then 7: xt ← xt−1 − γg, t← t+ 1 8: end if 9: until Convergence Worker i = 1, . . . ,m: 1: function WORKER (HONEST) 2: repeat 3: Pull xτ from the server 4: Draw random samples zi,j ∼ Di, ∀j ∈ [n], compute g̃ ← 1n ∑ j∈[n]∇f(xτ ; zi,j)
5: Push g̃ to the server 6: until Convergence 7: end function

heading: 4.2 ZENO++

text:
Calculating the stochastic descent score for every candidate gradient can be computationally expensive. To reduce the computation overhead, we approximate it by its first-order Taylor’s expansion.
Definition 3. (Approximated Stochastic Descent Score) Denote fs(x) = 1ns ∑ns j=1 f(x; zj), where zj’s are i.i.d. samples drawn from S , where S 6= Di,∀i ∈ [m], and ns is the batch size of fs(·). For any gradient estimator (correct or Byzantine) g, model parameter x, learning rate γ, and a constant weight ρ > 0, we approximate its stochastic descent score as follows:
Scoreγ,ρ(g, x) ≈ γ 〈∇fs(x), g〉 − ρ‖g‖2.
In brief, Zeno++ is a computationally efficient version of Zeno+ which uses this approximated stochastic descent score, combined with lazy updates. The detailed algorithm is shown in Algorithm 2. Compared to Zeno, we highlight several new techniques in Zeno++ (Algorithm 2), specially designed for asynchronous training: 1) re-scaling the candidate gradient (Line 6); 2) first-order Taylor’s expansion (Line 7); 3) hard threshold instead of comparison with the others (Line 7); 4) lazy update for reducing the computation overhead (Line 9).
Before moving forward, we wish to highlight several practical remarks for Zeno++:
• Preparing the validation dataset for Zeno++: The dataset S used for calculating v (the validation gradient of Zeno++) can be collected in many ways. It can be a separate validation dataset provided by a trusted third party. Another reasonable choice is that, a group of trusted workers can upload local data perturbed by additional noise (to help protect the users’ privacy). Typically, the validation dataset is small and different from the training dataset, thus can only be used to validate the gradients, and cannot be directly used for training, as shown in Section 6.
• Scheduling ZenoUpdater(x): ZenoUpdater(x) updates v in the background. It will only be triggered when the global model xt is updated and the server is idle. Another scheduling strategy is to trigger ZenoUpdater(x) after every k iterations. Thus, k is the upper bound of the delay of v. A reasonable choice is k = m, so that ideally v is updated after all the m workers respond.
• Computational efficiency: We can reduce the computation overhead of the Zeno++ server by decreasing the mini-batch size ns, or the frequency of the activation of ZenoUpdater(x). However, doing so will potentially incur larger noise for v, which makes a trade-off.
Algorithm 2 Zeno++ Server: 1: x0 ← rand(), t← 1 . Initialization 2: repeat 3: repeat 4: Receive g̃ from an arbitrary worker 5: Read v with lock (v may be from an old version of x: v = ∇fs(xτ ), τ ≤ t− 1) 6: Normalize g = cg̃ such that ‖g‖2 = ‖v‖2, c > 0 7: until γ 〈v, g〉 − ρ‖g‖2 ≥ −γ 8: xt ← xt−1 − γg, t← t+ 1 9: Lazy update of v: Run non-blocking ZenoUpdater(xt), if idle, or after every k iterations 10: until Convergence 11: function ZENOUPDATER(x) 12: Randomly sample zj ∼ S, ∀j ∈ [ns] to compute fs (Note: S 6= D1 6= · · · 6= Dm) 13: Write with lock: v ← ∇fs(x) = 1ns ∑ns j=1∇f(x; zj) 14: end function Worker i = 1, . . . ,m: 1: function WORKER (HONEST) 2: repeat 3: Pull xτ from the server 4: Draw random samples zi,j ∼ Di, ∀j ∈ [n], compute g̃ ← 1n ∑ j∈[n]∇f(xτ ; zi,j)
5: Push g̃ to the server 6: until Convergence 7: end function

heading: 5 THEORETICAL GUARANTEES

text:
In this section, we prove the convergence of Zeno++ (Algorithm 2) under Byzantine failures. We start with definitions used in the convergence analysis.
Definition 4. (Smoothness) Differentiable f(x) satisfies L-smoothness if there exists L > 0 such that ∀x, y, f(y)− f(x) ≤ 〈∇f(x; z), y − x〉+ L2 ‖y − x‖ 2. Definition 5. (Polyak-Łojasiewicz (PL) inequality) Differentiable f(x) satisfies the PL inequality (Polyak, 1963) if there exists µ > 0, such that ∀x: f(x)− f(x∗) ≤ 12µ‖∇f(x)‖ 2.

heading: 5.1 CONVERGENCE GUARANTEES

text:
We prove the convergence of Algorithm 2 for non-convex problems with the following assumption.
Assumption 1. (Bounded server delay) For Zeno++, we assume that the delay of the validation gradient v is upper-bounded. Without loss of generality, suppose the current model is xt, and v = ∇fs(xτ ), where τ ≤ t. We assume that for ∀t, t− τ ≤ k.
Remark 2. Zeno++ does not require bounded delay for the workers. The bounded delay requirement in Assumption 1 is only for the validation gradient v on the server, not for the workers.
We first analyze the convergence of functions that satisfy the PL inequality.
Theorem 1. Assume that F (x) and fs(x) are L-smooth and satisfy the PL inequality. Assume that for ∀x, the correct gradients and validation gradients are upper-bounded: ‖∇F (x)‖2 ≤ V1, ‖∇fs(x)‖2 ≤ V1, and the validation gradients are always non-zero and lower-bounded: ‖∇fs(x)‖2 ≥ V2, where 0 < V2 ≤ V1. Furthermore, we assume that the validation set is close to the training set, which implies bounded variance: E [ ‖∇fs(x)−∇F (x)‖2 ] ≤ V3,∀x. Taking γ < min(1, 1L ) and ρ ≥ α √ γV1 2µV2 , after T global updates, Algorithm 2 converges to a global optimum:
E [F (xT )− F (x∗)] ≤ (1− α √ γ)T [F (x0)− F (x∗)] +
√ γ
α O(k2V1 + V3 + ).
Remark 3. The assumption of the lower bounded gradient ‖∇fs(x)‖2 ≥ V2 is necessary. We need ∇fs(x) 6= 0, so that the normalization in Line 6 and inner product in Line 7 of Algorithm 2 are feasible. In practice, if we have a mini-batch with zero gradient∇fs(x) = 0 on server, we can simply draw additional samples and add them to the mini-batch, until such gradient is non-zero.
For general smooth but non-convex functions, we have the following convergence guarantee.
Theorem 2. Assume that F (x) and fs(x) are L-smooth and potentially non-convex. Assume that for ∀x, the true gradients and validation gradients are upper-bounded: ‖∇F (x)‖2 ≤ V1, ‖∇fs(x)‖2 ≤ V1, and the validation gradients are always non-zero and lower-bounded: ‖∇fs(x)‖2 ≥ V2, where 0 < V2 ≤ V1. Furthermore, we assume that the validation set is close to the training set, which implies bounded variance: E [ ‖∇fs(x)−∇F (x)‖2 ] ≤ V3,∀x. Taking γ < min(1, 1L ) and ρ ≥ α √ γV1 V2
, after T global updates, Algorithm 2 converges to a critical point: E [∑ t∈[T ] ‖∇F (xt−1)‖2 ]
T ≤ E [F (x0)− F (x∗)] α √ γT +
√ γ
α O(k2V1 + V3 + ).
Furthermore, if we take γ = 1LT , then we have E[
∑ t∈[T ] ‖∇F (xt−1)‖
2] T ≤ O
( 1
α √ T
) .
Remark 4. ρ controls the trade-off between the acceptance ratio and the convergence rate. Large positive ρmakes the convergence faster, but fewer candidate gradients pass the test of Zeno++. Small positive ρ increases the acceptance ratio, but may also potentially slow down the convergence or incur larger variance. We use α > 0 to bridge ρ to the convergence rate and the variance. Larger α makes ρ larger, which improves the convergence rate, but also enlarges the variance. Using non-zero potentially results in negative thresholds, which enlarges the acceptance ratio, but also increases the false negative ratio (the ratio of Byzantine gradients that are not filtered out by Zeno++).

heading: 6 EXPERIMENTS

text: In this section, we evaluate the proposed algorithm, Zeno++. Note that we do not evaluate the prototype algorithm Zeno+, since its computation overhead is too large for practical settings. Due to the space limitation, zoomed figures and additional experiments (including evaluation on an additional label-flipping attack, and testing the sensitivity to hyperparameters) are presented in the appendix.

heading: 6.1 DATASETS AND EVALUATION METRICS

text:
We conduct experiments on the benchmark CIFAR-10 image classification dataset (Krizhevsky and Hinton, 2009), which is composed of 50k images for training and 10k images for testing. We use a convolutional neural network (CNN) with 4 convolutional layers followed by 2 fully connected layers. The detailed network architecture can be found in our submitted source code (will be released upon publication). In the 50k images for training, we randomly extracted 2.5k of them as the validation set for Zeno++, the remaining are randomly partitioned onto all the workers. In each experiment, we launch 10 worker processes. We repeat each experiment 10 times and take the average. Each experiment is composed of 200 epochs, where each epoch is a full pass of the training dataset. We simulate asynchrony by drawing random delay from a uniform distribution in the range of [0, kw], where kw is the maximum worker delay (different from the maximum server delay k of Zeno++).
We use top-1 accuracy on the testing set and the cross-entropy loss function on the training set as the evaluation metrics. We also report the false positive rate (FP), which is the ratio of correct gradients that are recognized as Byzantine and filtered out by Zeno++ or the Kardam baseline.

heading: 6.1.1 BASELINES

text:
We use the asynchronous SGD without failures/attacks as the gold standard, which is referred to as AsyncSGD without attack. Since Kardam is the only previous work on Byzantine-tolerant asynchronous SGD, we use it as the baseline.
One may conjecture that Zeno++ is analogous to training on the validation data. To explore this, we consider training only on S – assumed to be clean data on the server, i.e., update the model only using v = ∇fs(x) on the server, without using any workers. We call this baseline Server-only. We fine-tune the learning rate and show the best results of Server-only.

heading: 6.2 NO ATTACK

text:
We first test the convergence when there are no attacks. In all the experiments, we take the learning rate γ = 0.1, mini-batch size n = ns = 128, ρ = 0.002, = 0.1, k = 10. For Kardam, we take q = 2 (i.e. here Kardam assumes that there are 2 Byzantine workers). The result is shown in Figure 1. Zeno++ converges a little bit slower than AsyncSGD, but faster than Kardam, especially when the worker delay is large. When kw = 10, Zeno++ converges much faster than Kardam. Server-only performs badly on both training and testing data.
50 100 150
Global Epoch
0.4
0.6
0.8
T o p -1
a c c u ra
c y
(a) Top-1 accuracy on testing set, kw = 5.
50 100 150
Global Epoch
0
0.5
1
1.5
2
2.5
L o s s
AsyncSGD without attack Kardam, FP=80.6 Zeno++, FP=47.4 Server-only
(b) Cross entropy on training set, kw = 5.
50 100 150
Global Epoch
0.2
0.4
0.6
0.8
T o p -1
a c c u ra
c y
(c) Top-1 accuracy on testing set, kw = 10.
50 100 150
Global Epoch
0
0.5
1
1.5
2
L o s s
AsyncSGD without attack Kardam, FP=87.7 Zeno++, FP=49.4 Server-only
(d) Cross entropy on training set, kw = 10.
Figure 1: Convergence without attacks, with different maximum worker delays kw. ρ = 0.002, = 0.1, k = 10 for Zeno++. FP refers to the fraction of false positive detect ions i.e. incorrect prediction that a message is Byzantine.

heading: 6.3 SIGN-FLIPPING ATTACK

text: We test the Byzantine-tolerance to the “sign-flipping” attack, which was proposed in Damaskinos et al. (2018). In such attacks, the Byzantine workers send−10∇f(x) instead of the correct gradient∇f(x) to the server. In all the experiments, we take the learning rate γ = 0.1, mini-batch size n = ns = 128, ρ = 0.002, = 0.1, k = 10. The result is shown in Figure 2, with different number of Byzantine workers q. It is shown that when q = 4, Zeno++ converges slightly slower than AsyncSGD without attacks, and much faster than Kardam. Actually, we observe that Kardam fails to make progress when the worker delay is large. When the number of Byzantine workers gets larger (q = 8), the convergence of Zeno++ gets slower, but it still makes reasonable progress, while AsyncSGD and Kardam fail. Note that Kardam performs even worse than Server-only, which means that Kardam is not even as good as training on a single honest worker. Thus, when there are Byzantine workers, distributed training with Kardam is meaningless.

heading: 6.4 DISCUSSION

text:
Kardam performs surprisingly badly in our experiments. The experiments in Damaskinos et al. (2018) focus on dampening staleness when there are no Byzantine failures. For Byzantine tolerance, Damaskinos et al. (2018) only reports that Kardam filters out 100% of the Byzantine gradients, which matches the results in our experiments. However, we observe that in addition to filtering out 100% of the Byzantine gradients, Kardam also filters nearly 100% of the correct gradients. In Figure 2, we
50 100 150
Global Epoch
0
0.2
0.4
0.6
0.8
T o p -1
a c c u ra
c y
(a) Top-1 accuracy on testing set, kw = 5, q = 4.
50 100 150
Global Epoch
0
1
2
3
L o s s
AsyncSGD without attack AsyncSGD Kardam, FP=98.5 Zeno++, FP=47.9 Server-only
(b) Cross entropy on training set, kw = 5, q = 4.
50 100 150
Global Epoch
0
0.2
0.4
0.6
0.8
T o p -1
a c c u ra
c y
(c) Top-1 accuracy on testing set, kw = 15, q = 4.
50 100 150
Global Epoch
0
1
2
3
L o s s
AsyncSGD without attack AsyncSGD Kardam, FP=99.8 Zeno++, FP=56.7 Server-only
(d) Cross entropy on training set, kw = 15, q = 4.
50 100 150
Global Epoch
0
0.2
0.4
0.6
0.8
T o p -1
a c c u ra
c y
(e) Top-1 accuracy on testing set, kw = 5, q = 8.
50 100 150
Global Epoch
0
1
2
3
L o s s
AsyncSGD without attack AsyncSGD Kardam, FP=99.7 Zeno++, FP=52.7 Server-only
(f) Cross entropy on training set, kw = 5, q = 8.
50 100 150
Global Epoch
0
0.2
0.4
0.6
0.8
T o p -1
a c c u ra
c y
(g) Top-1 accuracy on testing set, kw = 15, q = 8.
50 100 150
Global Epoch
0
1
2
3
L o s s
AsyncSGD without attack AsyncSGD Kardam, FP=99.8 Zeno++, FP=60.5 Server-only
(h) Cross entropy on training set, kw = 15, q = 8.
Figure 2: Convergence with sign-flipping attacks with different maximum worker delays kw. For any correct gradient g, if selected to be Byzantine, g will be replaced by −10g. q ∈ {4, 8} out of the 10 workers are Byzantine. ρ = 0.002, = 0.1, k = 10 for Zeno++. FP refers to the fraction of false positive detect ions i.e. incorrect prediction that a message is Byzantine.
report that the false positive rate of Kardam is nearly 99%, which makes the convergence extremely slow. To make things worse, Kardam does not even perform as good as Server-only, which makes the distributed training with Kardam totally meaningless. One reason why Kardam performs badly is that we use a more general threat model in this paper, which does not guarantee an important assumption of Kardam, namely “any sequence of successively received gradients of length 2q + 1 must contain at least q + 1 gradients from honest workers”. It is clear that this assumption is quite strong, as in an asynchronous setting, Byzantine workers can easily send long sequences of erroneous responses. Our approach does not depend on such a strong assumption.
In all the experiments, Zeno++ converges faster than the baselines when there are Byzantine failures. Although the convergence of Zeno++ is slower than AsyncSGD when there are no attacks, we find that it provides a reasonable trade-off between security and convergence speed. In general, larger worker delay kw and more Byzantine workers q add more error and noise to the gradients, which slows down the convergence, because there are fewer valid gradients for the server to use. Zeno++ can filter out most of the harmful gradients at the cost of FP ≈ 50%. Note that Server-only is an extreme case that only uses the server and the validation dataset to train the model in a non-distributed manner, which will not be affected by Byzantine workers. However, only using the validation data is not enough for training, as shown in Figure 1. Similarly in practice, we can use a small dataset separated from the training data for cross-validation, but will never directly train the model only on such validation dataset. Furthermore, as shown in Figure 2, Zeno++ performs much better than Server-only. Thus, we can draw to the conclusion that Zeno++ is efficiently training the model on the honest workers in a distributed manner, which is not equivalent to training on the validation dataset only.
On average, the server computes nsk = 12.8 gradients in each iteration, since the validation gradient v of Zeno++ is updated after every k = 10 iterations. Thus, the workload on the server is much smaller than a worker. Furthermore, since we can parallelize the workload on the server and workers, the computation overhead of v can be hidden, so that Zeno++ can benefit from distributed training.

heading: 7 CONCLUSION

text: We propose a novel Byzantine-tolerant fully asynchronous SGD algorithm: Zeno++. The algorithm provably converges. Our empirical results show good performance compared to previous work. In future work, we will explore variations of our approach for other settings such as federated learning.

heading: A PROOFS

text:
A.1 ZENO++
We first analyze the convergence of the functions whose gradients grow as a quadratic function of sub-optimality.
Theorem 1. Assume that F (x) and fs(x) have L-smoothness and PL inequality (potentially nonconvex). Assume that for ∀x, the true gradients and stochastic gradients are upper-bounded: ‖∇F (x)‖2 ≤ V1, ‖∇fs(x)‖2 ≤ V1, and the stochastic gradients for Zeno testing are always non-zero and lower-bounded: ‖∇fs(x)‖2 ≥ V2, where 0 < V2 ≤ V1. Furthermore, we assume that the validation set is close to the training set, which implies bounded variance: E [ ‖∇fs(x)−∇F (x)‖2 ] ≤ V3,∀x. Taking γ < min(1, 1L ) and ρ ≥ α √ γV1 2µV2 , after T global updates, Algorithm 2 converges to a global optimum:
E [F (xT )− F (x∗)] ≤ (1− α √ γ)T [F (x0)− F (x∗)] +
√ γ
α O(k2V1 + V3 + ).
Proof. If any gradient estimator g passes the test of Zeno++, then we have 〈∇fs(xτ ),−γg〉 ≤ −ρ‖g‖2 + γ , where τ ≤ t− 1. Thus, we have 〈∇F (xt−1),−γg〉 ≤ 〈∇F (xt−1)−∇fs(xτ ),−γg〉 − ρ‖∇fs(xτ )‖2 + γ
≤ −ρV2 V1 ‖∇F (xt−1)‖2 + γ 2 ‖∇F (xt−1)−∇fs(xτ )‖2 + γ 2 ‖∇fs(xτ )‖2 + γ
≤ −ρV2 V1 ‖∇F (xt−1)‖2 + γ‖∇F (xτ )−∇fs(xτ )‖2 + γ‖∇F (xt−1)−∇F (xτ )‖2 + γ 2 V1 + γ
≤ −ρV2 V1 ‖∇F (xt−1)‖2 + γV3 + γ‖∇F (xt−1)−∇F (xτ )‖2 + γ 2 V1 + γ .
‖∇F (xt−1)−∇F (xτ )‖2 can be upper-bounded using L-smoothness and the bounded delay: ‖∇F (xt−1)−∇F (xτ )‖2 ≤ L2‖xt−1 − xτ‖2 ≤ L2k2γ2V1. Again, using smoothness, taking ρ ≥ α √ γV1
2µV2 , we have
E [F (xt)− F (x∗)]
≤ F (xt−1)− F (x∗) + 〈∇F (xt−1),−γE[g]〉+ Lγ2
2 E‖g‖2
≤ F (xt−1)− F (x∗)− ρ V2 V1 ‖∇F (xt−1)‖2 + γV3 + L2k2γ3V1 + γ 2 V1 + Lγ 2 V1 + γ
≤ F (xt−1)− F (x∗)− ρ V2 V1 ‖∇F (xt−1)‖2 + γO(k2V1 + V3 + )
≤ [ 1− 2µρV2
V1
] [F (xt−1)− F (x∗)] + γO(k2V1 + V3 + )
≤ (1− α√γ) [F (xt−1)− F (x∗)] + γO(k2V1 + V3 + ). By telescoping and taking total expectation, after T global updates, we have
E [F (xT )− F (x∗)] ≤ (1− α √ γ)T [F (x0)− F (x∗)] +
√ γ
α O(k2V1 + V3 + ).
For general smooth but non-convex functions, we have the following convergence guarantee.
Theorem 2. Assume that F (x) and fs(x) are L-smooth and potentially non-convex. Assume that for ∀x, the true gradients and stochastic gradients are upper-bounded: ‖∇F (x)‖2 ≤ V1, ‖∇fs(x)‖2 ≤ V1, and the stochastic gradients for Zeno testing are always non-zero and lowerbounded: ‖∇fs(x)‖2 ≥ V2, where 0 < V2 ≤ V1. Furthermore, we assume that the validation set is close to the training set, which implies bounded variance: E [ ‖∇fs(x)−∇F (x)‖2 ] ≤ V3,∀x. Taking γ < min(1, 1L ) and ρ ≥ α √ γV1 V2
, after T global updates, Algorithm 2 converges to a critical point: E [∑ t∈[T ] ‖∇F (xt−1)‖2 ]
T ≤ E [F (x0)− F (x∗)] α √ γT +
√ γ
α O(k2V1 + V3 + ).
Furthermore, if we take γ = 1LT , then we have E [∑ t∈[T ] ‖∇F (xt−1)‖2 ]
T ≤ O
( 1
α √ T
) .
Proof. Similar to Theorem 1, we have
〈∇F (xt−1),−γg〉 ≤ −ρ V2 V1 ‖∇F (xt−1)‖2 + γO(k2V1 + V3 + ).
Using smoothness, taking ρ ≥ α √ γV1 V2
, we have E [F (xt)]
≤ F (xt−1) + 〈∇F (xt−1),−γE[g]〉+ Lγ2
2 E‖g‖2
≤ F (xt−1)− ρ V2 V1 ‖∇F (xt−1)‖2 + γO(k2V1 + V3 + ) ≤ F (xt−1)− α √ γ‖∇F (xt−1)‖2 + γO(k2V1 + V3 + ).
Thus, we have
‖∇F (xt−1)‖2 ≤ E [F (xt−1)− F (xt)]
α √ γ
+
√ γ
α O(k2V1 + V3 + ).
By telescoping and taking total expectation, after T global updates, we have E [∑ t∈[T ] ‖∇F (xt−1)‖2 ]
T ≤ E [F (x0)− F (x∗)] α √ γT +
√ γ
α O(k2V1 + V3 + ).
Furthermore, if we take γ = 1LT , then we have E [∑ t∈[T ] ‖∇F (xt−1)‖2 ]
T ≤ O
( 1
α √ T
) .
A.2 ZENO+
Theorem 3. Assume that F (x) and fs(x) have L-smoothness has µ-strong convexity. Assume that for ∀x, the true gradients and stochastic gradients are upper-bounded: ‖∇F (x)‖2 ≤ V1, ‖∇fs(x)‖2 ≤ V1, and the stochastic gradients for Zeno testing are always non-zero and lowerbounded: ‖∇fs(x)‖2 ≥ V2, where 0 < V2 ≤ V1. Furthermore, we assume that the validation set is close to the training set, which implies bounded variance: E [ ‖∇fs(x)−∇F (x)‖2 ] ≤ V3,∀x. Taking γ < min(1, 1L ) and ρ ≥ α √ γV1 2µV2 − µγ 2
2 , after T global updates, Algorithm 1 converges to a global optimum:
E [F (xT )− f(x∗)] ≤ (1− α √ γ)T [F (x0)− f(x∗)] +
√ γ
α O(V1 + V3 + ).
Proof. Using µ-strong convexity, we have
〈∇fs(x),−γg〉+ µγ2
2 ‖g‖2 ≤ fs(x− γg)− fs(x) ≤ −ρ‖g‖2 + γ .
Note that ‖∇fs(x)‖ 2
‖∇F (x)‖2 ≥ V2 V1 . Thus, we have 〈∇fs(x),−γg〉 ≤ − ( ρ+ µγ2
2
) ‖∇fs(x)‖2 + γ ≤ − ( ρ+ µγ2
2 ) V2 V1 ‖∇F (x)‖2 + γ .
Then, we have 〈∇F (x),−γg〉 = 〈∇fs(x),−γg〉+ 〈∇F (x)−∇fs(x),−γg〉 = 〈∇fs(x),−γg〉+ γ 〈(∇F (x)−∇fs(x) ),−g〉
≤ 〈∇fs(x),−γg〉+ γ
2 ‖∇F (x)−∇fs(x)‖2 +
γ 2 ‖g‖2.
Taking the expectation on both sides, we have 〈∇F (x),−γE[g]〉 ≤ − ( ρ+ µγ2
2 ) V2 V1 ‖∇F (x)‖2 + γ 2 (V1 + V3) + γ .
Using L-smoothness, conditional on x, we have E [F (x− γg)− F (x)]
≤ 〈∇F (x),−γE[g]〉+ Lγ 2
2 E‖g‖2 ≤ − ( ρ+ µγ2
2 ) V2 V1 ‖∇F (x)‖2 + γ 2 (V1 + V3) + Lγ2 2 V1 + γ
≤ − ( ρ+ µγ2
2 ) V2 V1 ‖∇F (x)‖2 + γO(V1 + V3 + ).
Again, using µ-strong convexity, we have
F (x)− F (x∗) ≤ 1
2µ ‖∇F (x)‖2.
Thus, we have E [F (x− γg)− f(x∗)] ≤ [ 1− 2µ ( ρ+ µγ2
2 ) V2 V1 ] [F (x)− f(x∗)] + γO(V1 + V3 + ).
Taking xt−1 = x, and xt = x− γg, we have E [F (xt)− f(x∗)] ≤ [ 1− 2µ ( ρ+ µγ2
2 ) V2 V1 ] [F (xt−1)− f(x∗)] + γO(V1 + V3) + .
Take ρ ≥ α √ γV1
2µV2 − µγ
2
2 , we have E [F (xt)− f(x∗)] ≤ (1− α √ γ) [F (xt−1)− f(x∗)] + γO(V1 + V3 + ).
By telescoping and taking total expectation, after T global updates, we have E [F (xT )− f(x∗)]
≤ (1− α√γ)T [F (x0)− f(x∗)] + 1− (1− α√γ)T
1− (1− α√γ) γO(V1 + V3 + )
≤ (1− α√γ)T [F (x0)− f(x∗)] + √ γ
α O(V1 + V3 + ).

heading: B ADDITIONAL EXPERIMENTS

text:
B.1 NO ATTACK
We first test the convergence when there are no attacks. In all the experiments, we take the learning rate γ = 0.1, mini-batch size n = ns = 128, ρ = 0.002, = 0.1, k = 10. For Kardam, we take
q = 2 (Kardam pretends that there are 2 Byzantine workers). The result is shown in Figure 3. We can see that Zeno++ converges a little bit slower than AsyncSGD, but faster than Kardam, especially when the worker delay is large. When kw = 10, Zeno++ converges much faster than Kardam.
B.2 SIGN-FLIPPING ATTACK
We test the Byzantine-tolerance to “sign-flipping” attack, which is proposed in Damaskinos et al. (2018). In such attacks, the Byzantine workers send−10∇f(x) instead of the correct gradient∇f(x) to the server. In all the experiments, we take the learning rate γ = 0.1, mini-batch size n = ns = 128, ρ = 0.002, = 0.1, k = 10. The result is shown in Figure 4 and 5, with different number of Byzantine workers q.
B.3 LABEL-FLIPPING ATTACK
We test the Byzantine tolerance to the label-flipping attacks. When such kind of attacks happen, the workers compute the gradients based on the training data with “flipped" labels, i.e., any label ∈ {0, . . . , 9}, is replaced by 9− label. Such kind of attacks can be caused by data poisoning or software failures. In all the experiments, we take the learning rate γ = 0.1, mini-batch size n = ns = 128, ρ = 0.002, = 0.1, k = 10. The result is shown in Figure 6 and 7, with different number of Byzantine workers q.
B.4 SENSITIVITY TO HYPERPARAMETERS
In Figure 8 and 9, we show how the hyperparameters ρ, , and k affect the convergence. In general, Zeno++ is insensitive to . Larger ρ and k slow down the convergence.
B.5 RESNET20 ON CIFAR-10
We test the Byzantine-tolerance on ResNet20 v1 (https://keras.io/examples/cifar10_resnet/) and CIFAR-10 dataset. We show the top-1 accuracy on the testing set.
In Figure 11, we show the convergence when there are no attacks. Zeno++ converges as good as AsyncSGD. In Figure 12, we show the convergence when there are sign-flipping attacks.
In Figure 13 and 14, we test Zeno++ with 2 different types of random attacks. In Figure 13, for any correct gradient g, if selected to be Byzantine, any element of g will be replaced by a IID random value drawn from a Gaussian distribution with 0 mean and 5 variance, while in Figure 14, any element of Byzantine g will be added by a IID random value drawn from a Gaussian distribution with 0 mean and 5 variance.
B.6 LSTM ON WIKITEXT-2
We test the Byzantine-tolerance on LSTM-based language model. The model is from https://github.com/salesforce/awd-lstm-lm (Merity et al., 2017; 2018), trained on WikiText-2 dataset. We use 600 hidden units per layer. We show the perplexity (the smaller the better) on the testing set.
In Figure 15, we show the convergence when there are no attacks. Zeno++ converges as good as AsyncSGD. In Figure 16 and 17, we show the convergence when there are sign-flipping attacks, with different number of Byzantine workers.

title: ZENO++: ROBUST FULLY ASYNCHRONOUS SGD