summaries: This paper studies distributed optimization in the presence of straggling computing nodes. In a synchronous distributed optimization approach, the stragglers delay the entire computation as the synchronization operation cannot be performed till every computing nod has completed its task. This paper aims to mitigate the effect of stragglers by proposing Anytime MiniBatch (AMB) approach, where each computing node is allowed to process the different number of samples between two synchronization steps. In particular, each node is given $T$ unit time to process as many samples as it can. After that, the nodes are allowed to aggregate the information among themselves through a consensus mechanism for another $T_c$ unit time. In contrast with this, the usual Fixed MiniBatch (FMB) approach requires each node to process a fixed number of samples before invoking aggregating step. The presence of stragglers can significantly increase the time between two synchronization step and slow down the overall optimization process.

summaries: The paper considers the problem of online stochastic convex optimization in a fully distributed topology. In particular, the authors focus on the synchronous setting and to avoid the slow progress that can be obtained by slow nodes, called stragglers, they propose an online distributed optimization method called Anytime Minibatch (AMB). In the update of AMB rather than fixing the minibatch size, they fix the computation time in each epoch. This characteristic prevents the stragglers from holding up the entire network, while allowing nodes to benefit from the partial work carried out by the slower nodes.

abstractText: Distributed optimization is vital in solving large-scale machine learning problems. A widely-shared feature of distributed optimization techniques is the requirement that all nodes complete their assigned tasks in each computational epoch before the system can proceed to the next epoch. In such settings, slow nodes, called stragglers, can greatly slow progress. To mitigate the impact of stragglers, we propose an online distributed optimization method called Anytime Minibatch. In this approach, all nodes are given a fixed time to compute the gradients of as many data samples as possible. The result is a variable per-node minibatch size. Workers then get a fixed communication time to average their minibatch gradients via several rounds of consensus, which are then used to update primal variables via dual averaging. Anytime Minibatch prevents stragglers from holding up the system without wasting the work that stragglers can complete. We present a convergence analysis and analyze the wall time performance. Our numerical results show that our approach is up to 1.5 times faster in Amazon EC2 and it is up to five times faster when there is greater variability in compute node performance.

authors:
Barry C. Arnold
Richard A. Groeneveld

title: Bounds on expectations of linear systematic statistics based on dependent samples

authors:
Dimitris Bertsimas
Karthik Natarajan
Chung-Piaw Teo

title: Tight bounds on expected order statistics

venue: Probab. Eng. Inf. Sci.,

authors:
Jeffrey Dean
Greg S. Corrado
Rajat Monga
Kai Chen
Matthieu Devin
Quoc V. Le
Mark Z. Mao
Marc’Aurelio Ranzato
Andrew Senior
Paul Tucker
Ke Yang
Andrew Y. Ng

title: Large scale distributed deep networks

venue: In Proceedings of the 25th International Conference on Neural Information Processing Systems,

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

title: Optimal distributed online prediction using mini-batches

venue: Journal of Machine Learning Research,

authors:
John C Duchi
Alekh Agarwal
Martin J Wainwright

title: Dual averaging for distributed optimization: Convergence analysis and network scaling

venue: IEEE Transactions on Automatic control,

authors:
K. Lee
M. Lam
R. Pedarsani
D. Papailiopoulos
K. Ramchandran

title: Speeding up distributed machine learning using codes

venue: IEEE Trans. on Inf. Theory,

authors:
Ji Liu
Stephen J. Wright
Christopher Ré
Victor Bittorf
Srikrishna Sridhar

title: An asynchronous parallel stochastic coordinate descent algorithm

venue: J. Mach. Learn. Res.,

authors:
Angelia Nedic
Asuman Ozdaglar

title: Distributed subgradient methods for multi-agent optimization

venue: IEEE Transactions on Automatic Control,

title: Primal-dual subgradient methods for convex problems

venue: Math. Program.,

authors:
M. Nokleby
W.U. Bajwa

title: Distributed mirror descent for stochastic learning over rate-limited networks

venue: IEEE 7th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP),

authors:
Xinghao Pan
Jianmin Chen
Rajat Monga
Samy Bengio
Rafal Józefowicz

title: Revisiting distributed synchronous sgd

venue: In Int. Conf. on Learning Representations Workshop

authors:
Benjamin Recht
Christopher Re
Stephen Wright
Feng Niu

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

venue: In Advances in Neural Information Processing Systems

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

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

venue: In in Proc. of the Int. Conf. on Artificial Intelligence and Statistics (AISTATS),

authors:
Wei Shi
Qing Ling
Gang Wu
Wotao Yin

title: Extra: An exact first-order algorithm for decentralized consensus optimization

venue: SIAM Journal on Optimization,

authors:
R. Tandon
Q. Lei
A.G. Dimakis
N. Karampatziakis

title: Gradient Coding: Avoiding Stragglers in Distributed Learning

venue: In in Proc. of the Int. Conf. on Int. Conf. on Machine Learning (ICML),

authors:
Konstantinos I Tsianos
Michael G Rabbat

title: Efficient distributed online prediction and stochastic optimization with approximate distributed averaging

venue: IEEE Transactions on Signal and Information Processing over Networks,

authors:
Konstantinos I Tsianos
Sean Lawlor
Michael G Rabbat

title: Push-sum distributed dual averaging for convex optimization

venue: In Decision and Control (CDC),

authors:
John Tsitsiklis
Dimitri Bertsekas
Michael Athans

title: Distributed asynchronous deterministic and stochastic gradient optimization algorithms

authors:
Chenguang Xi
Usman A Khan

title: Dextra: A fast algorithm for optimization over directed graphs

title: Dual averaging methods for regularized stochastic learning and online optimization

authors:
Q. Yu
M. Maddah-Ali
S. Avestimehr

title: Polynomial codes: An optimal design for high-dimensional coded matrix multiplication

venue: In Advances Neural Inf. Proc. Systems,

authors:
Martin Zinkevich
Markus Weimer
Lihong Li
Alex J. Smola

title: Parallelized stochastic gradient descent

heading: 1 INTRODUCTION

text:
The advent of massive data sets has resulted in demand for solutions to optimization problems that are too large for a single processor to solve in a reasonable time. This has led to a renaissance in the study of parallel and distributed computing paradigms. Numerous recent advances in this field can be categorized into two approaches; synchronous Dekel et al. (2012); Duchi et al. (2012); Tsianos & Rabbat (2016); Zinkevich et al. (2010) and asynchronous Recht et al. (2011); Liu et al. (2015). This paper focuses on the synchronous approach. One can characterize synchronization methods in terms of the topology of the computing system, either master-worker or fully distributed. In a master-worker topology, workers update their estimates of the optimization variables locally, followed by a fusion step at the master yielding a synchronized estimate. In a fully distributed setting, nodes are sparsely connected and there is no obvious master node. Nodes synchronize their estimates via local communications. In both topologies, synchronization is a key step.
Maintaining synchronization in practical computing systems can, however, introduce significant delay. One cause is slow processing nodes, known as stragglers Dean et al. (2012); Yu et al. (2017); Tandon et al. (2017); Lee et al. (2018); Pan et al. (2017); S. Dutta & Nagpurkar (2018). A classical requirement in parallel computing is that all nodes process an equal amount of data per computational epoch prior to the initiation of the synchronization mechanism. In networks in which the processing speed and computational load of nodes vary greatly between nodes and over time, the straggling nodes will determine the processing time, often at a great expense to overall system efficiency. Such straggler nodes are a significant issue in cloud-based computing systems. Thus, an important challenge is the design of parallel optimization techniques that are robust to stragglers.
To meet this challenge, we propose an approach that we term Anytime MiniBatch (AMB). We consider a fully distributed topologyand consider the problem of stochastic convex optimization
via dual averaging Nesterov (2009); Xiao (2010). Rather than fixing the minibatch size, we fix the computation time (T ) in each epoch, forcing each node to “turn in” its work after the specified fixed time has expired. This prevents a single straggler (or stragglers) from holding up the entire network, while allowing nodes to benefit from the partial work carried out by the slower nodes. On the other hand, fixing the computation time means that each node process a different amount of data in each epoch. Our method adapts to this variability. After computation, all workers get fixed communication time (Tc) to share their gradient information via averaging consensus on their dual variables, accounting for the variable number of data samples processed at each node. Thus, the epoch time of AMB is fixed to T + Tc in the presence of stragglers and network delays. We analyze the convergence of AMB, showing that the online regret achieves O( √ m̄) performance, which is optimal for gradient based algorithms for arbitrary convex loss Dekel et al. (2012). In here, m̄ is the expected sum number of samples processed across all nodes. We further show an upper bound that, in terms of the expected wall time needed to attain a specified regret, AMB is O( √ n− 1) faster than methods that use a fixed minibatch size under the assumption that the computation time follows an arbitrary distribution where n is the number of nodes. We provide numerical simulations using Amazon Elastic Compute Cloud (EC2) and show that AMB offers significant acceleration over the fixed minibatch approach.

heading: 2 RELATED WORK

text: This work contributes to the ever-growing body of literature on distributed learning and optimization, which goes back at least as far as Tsitsiklis et al. (1986), in which distributed first-order methods were considered. Recent seminal works include Nedic & Ozdaglar (2009), which considers distributed optimization in sensor and robotic networks, and Dekel et al. (2012), which considers stochastic learning and prediction in large, distributed data networks. A large body of work elaborates on these ideas, considering differences in topology, communications models, data models, etc. Duchi et al. (2012); Tsianos et al. (2012); Shi et al. (2015); Xi & Khan (2017). The two recent works most similar to ours are Tsianos & Rabbat (2016) and Nokleby & Bajwa (2017), which consider distributed online stochastic convex optimization over networks with communications constraints. However, both of these works suppose that worker nodes are homogeneous in terms of processing power, and do not account for the straggler effect examined herein. The recent work Pan et al. (2017); Tandon et al. (2017); S. Dutta & Nagpurkar (2018) proposed synchronous fixed minibatch methods to mitigate stragglers for master-worker setup. These methods either ignore stragglers or use redundancy to accelerate convergence in the presence of stragglers. However, our approach in comparison to Pan et al. (2017); Tandon et al. (2017); S. Dutta & Nagpurkar (2018) utilizes work completed by both fast and slow working nodes, thus results in faster wall time in convergence.

heading: 3 SYSTEM MODEL AND ALGORITHM

text:
In this section we outline our computation and optimization model and step through the three phases of the AMB algorithm. The pseudo code of the algorithm is provided in App. A. We defer discussion of detailed mathematical assumptions and analytical results to Sec. 4.
We suppose a computing system that consists of n compute nodes. Each node corresponds to a vertex in a connected and undirected graph G(V,E) that represents the inter-node communication structure. The vertex set V satisfies |V | = n and the edge set E tells us which nodes can communicate directly. Let Ni = {j ∈ V : (i, j) ∈ E, i 6= j} denote the neighborhood of node i. The collaborative objective of the nodes is to find the parameter vector w ∈W ⊆ Rd that solves
w∗ = arg min w∈W F (w) where F (w) := Ex[f(w, x)]. (1)
The expectation Ex[·] is computed with respect to an unknown probability distribution Q over a set X ⊆ Rd. Because the distribution is unknown, the nodes must approximate the solution in (1) using data points drawn in an independent and identically distributed (i.i.d.) manner from Q.
AMB uses dual averaging Nesterov (2009); Dekel et al. (2012) as its optimization workhorse and averaging consensus Nokleby & Bajwa (2017); Tsianos & Rabbat (2016) to facilitate collaboration among nodes. It proceeds in epochs consisting of three phases: compute, in which nodes compute
local minibatches; consensus, in which nodes average their dual variables together; and update, in which nodes take a dual averaging step with respect to the consensus-averaged dual variables. We let t index each epoch, and each node i has a primal variable wi(t) ∈ Rd and dual variable zi(t) ∈ Rd. At the start of the first epoch, t = 1, we initialize all primal variables to the same value w(1) as
wi(1) = w(1) = arg min w∈W h(w), (2)
and all dual variables to zero, i.e., zi(1) = 0 ∈ Rd. In here, h : W → R is a 1-strongly convex function.
Compute Phase: All workers are given T fixed time to compute their local minibatches. During each epoch, each node is able to compute bi(t) gradients of f(w, x), evaluated at wi(t) where the data samples xi(t, s) are drawn i.i.d. from Q. At the end of epoch t, each node i computes its local minibatch gradient:
gi(t) = 1
bi(t) bi(t)∑ s=1 ∇wf ( wi(t), xi(t, s) ) . (3)
As we fix the compute time, the local minibatch size bi(t) is a random variable. Let b(t) := ∑n i=1 bi(t) be the global minibatch size aggregated over all nodes. This contrasts with traditional approaches in which the minibatch is fixed. In Sec. 4 we provide a convergence analysis that accounts for the variability in the amount of work completed by each node. In Sec. 5, we presents a wall time analysis based on random local minibatch sizes.
Consensus Phase: Between computational epochs each node is given a fixed amount of time, Tc, to communicate with neighboring nodes. The objective of this phase is for each node to get (an approximation of) the following quantity:
1
b(t) n∑ i=1 bi(t)[zi(t) + gi(t)] = 1 b(t) n∑ i=1 bi(t)zi(t) + 1 b(t) n∑ i=1 bi(t)∑ s=1 ∇wf ( wi(t), xi(t, s) ) := z̄(t) + g(t). (4)
The first term, z̄(t), is the weighted average of the previous dual variables. The second, g(t), is the average of all gradients computed in epoch t.
The nodes compute this quantity approximately via several synchronous rounds of average consensus. Each node waits until it hears from all neighbors before starting a consensus round. As we have fixed communication time Tc, the number of consensus rounds ri(t) varies across workers and epochs due to random network delays. Let P be a positive semi-definite, doubly-stochastic matrix (i.e., all entries of P are non-negative and all row- and column-sums are one) that is consistent with the graph G (i.e., Pi,j > 0 only if i = j or if (i, j) ∈ E). At the start of the consensus phase, each node i shares its message m(0)i = nbi(t)[zi(t) + gi(t)] with its neighboring nodes. Let [r] stand for [r] ∈ {1, . . . r}. Then, in consensus iteration k ∈ [ri(t)] node i computes its update as
m (k) i = n∑ j=1 Pi,jm (k−1) j = n∑ j=1 (Pi,j) km (0) j .
As long as G is connected and the second-largest eigenvalue of P is strictly less than unity, the iterations are guaranteed to converge to the true average. For finite ri(t), each node will have an error in its approximation. Instead of (4), at the end of the rounds of consensus, node i will have
zi(t+ 1) = z̄(t) + g(t) + ξi(t), (5) where ξi(t) is the error. We use D(ri(t)) ( {yj}j∈V , i ) to denote the distributed averaging affected by ri(t) rounds of consensus. Thus,
zi(t+ 1) = 1
b(t) D(ri(t))
({ nbj(t) [ zj(t) + gj(t) ]]} j∈V , i ) = 1 b(t) m (ri(t)) i . (6)
We note that the updated dual variable zi(t+ 1) is a normalized version of the distributed average solution, normalized by b(t) = ∑n i=1 bi(t).
Update Phase: After distributed averaging of dual variables, each node updates its primal variable as
wi(t+ 1) = arg min w∈W
{〈 w, zi(t+ 1) 〉 + β(t+ 1)h(w) } ; (7)
where 〈·, ·〉 denotes the standard inner product. As will be discussed further in our analysis, in this paper we assume h : W → R to be a 1-strongly convex function and β(t) to be a sequence of positive non-decreasing parameters, i.e., β(t) ≤ β(t+ 1). We also work in Euclidean space where h(w) = ‖w‖2 is a typical choice.

heading: 4 ANALYSIS

text: In this section we analyze the performance of AMB in terms of expected regret. As the performance is sensitive to the specific distribution of the processing times of the computing platform used, we first present a generic analysis in terms of the number of epochs processed and the size of the minibatches processed by each node in each epoch. Then in Sec. 5, in order to illustrate the advantages of AMB, we assert a probabilistic model on the processing time and analyze the performance in terms of the elapsed “wall time” .

heading: 4.1 PRELIMINARIES

text:
We assume that the feasible space W ∈ Rd of the primal optimization variable w is a closed and bounded convex set where D = maxw,u∈W ‖w − u‖. Let ‖ · ‖ denote the `2 norm. We assume the objective function f(w, x) is convex and differentiable in w ∈W for all x ∈ X . We further assume that f(w, x) is Lipschitz continuous with constant L, i.e.
|f(w, x)− f(w̃, x)| ≤ L‖w − w̃‖, ∀x ∈ X, and ∀w, w̃ ∈W. (8) Let ∇f(w, x) be the gradient of f(w, x) with respect to w. We assume the gradient of f(w, x) is Lipschitz continuous with constant K, i.e.,
‖∇f(w, x)−∇f(w̃, x)‖ ≤ K‖w − w̃‖, ∀x ∈ X, and∀w, w̃ ∈W. (9) As mentioned in Sec. 3,
F (w) = E[f(w, x)], (10)
where the expectation is taken with respect to the (unknown) data distribution Q, and thus ∇F (w) = E[∇f(w, x)]. We also assume that there exists a constant σ that bounds the second moment of the norm of the gradient so that
E[‖∇f(w, x)−∇F (w)‖2] ≤ σ2,∀x ∈ X, and∀w ∈W. (11) Let the global minimum be denoted w∗ := arg minw∈W F (w).

heading: 4.2 SAMPLE PATH ANALYSIS

text:
First we bound the consensus errors. Let z(t) be the exact dual variable without any consensus errors at each node
z(t) = z̄(t− 1) + g(t− 1). (12) The following Lemma bounds the consensus errors, which is obtained using (Tsianos & Rabbat, 2016, Theorem 2)
Lemma 1 Let z(r)i (t) be the output after r rounds consensus. Let λ2(P ) be the second eigenvalue of the matrix P and let ≥ 0, then
‖z(r)i (t)− z(t)‖ ≤ , ∀i ∈ [n], t ∈ [τ ], (13) if the number of consensus rounds satisfies
ri(t) ≥ ⌈ log (2 √ n(1 + 2L/ ))
1− λ2(P )
⌉ , ∀i ∈ [n], t ∈ [τ ]. (14)
We characterize the regret after τ epochs, averaging over the data distribution but keeping a fixed “sample path” of per-node minibatch sizes bi(t). We observe that due to the time spent in communicating with other nodes via consensus, each node has computation cycles that could have been used to compute more gradients had the consensus phase been shorter (or nonexistent). To model this, let ai(t) denote the number of additional gradients that node i could have computed had there been no consensus phase. This undone work does not impact the system performance, but does enter into our characterization of the regret. Let ci(t) = bi(t) + ai(t) be the total number of gradients that node i had the potential to compute during the t-th epoch. Therefore, the total potential data samples processed in the t-th epoch is c(t) = ∑n i=1 ci(t). After τ epochs the total number of data points that could have been processed by all nodes in the absence of communication delays is
m = τ∑ t=1 c(t). (15)
An important quantity is the ratio of total potential computations in each epoch to that actually completed. Define the maximum such minibatch “skewness” as
γ = max t∈[τ−1]
c(t+ 1)
b(t) . (16)
It turns out that it is important to compute this skewness across epochs (i.e., c(t+ 1) versus b(t)) in order to bound the regret via a telescoping sum. [Details can be found in the supplementary material.]
In practice, ai(t) and bi(t) (and therefore ci(t)) depend on latent effects, e.g., how many other virtual machines are co-hosted on node i, and therefore we model them as random variables. We bound the expected regret for a fixed sample path of ai(t) and bi(t). The sample paths of importance are ctot(τ) = {ci(t)}i∈V,t∈[τ ] and btot(τ) = {bi(t)}i∈V,t∈[τ ], where we introduce ctot and btot for notational compactness.
Define the average regret after τ epochs as
R(τ) = E [ R|btot(τ), ctot(τ) ] = E  τ∑ t=1 n∑ i=1 ci(t)∑ s=1 [ f ( wi(t), xi(t, s) ) − F (w∗) ] , (17) where the expectation is taken with respect the the i.i.d. sampling from the distribution Q. Then, we have the following bound on R(τ).
Theorem 2 Suppose workers collectively processed m samples after τ epochs, cf. (15), minibatch skewness parameter γ, cf. (16), and let cmax = maxt∈[τ ] c(t), cavg = (1/τ) ∑τ t=1 c(t) and δ = max{t,t′}∈{1,τ−1} |c(t)−c(t′)| be the maximum, average, and variation across c(t). Further, suppose the averaging consensus has additive accuracy , cf. Lemma 1. Then, the expected regret is
R(τ) ≤ cmax[F (w(1))− F (w∗) + β(τ)h(w∗)] + 3K2 2cmaxµ 3/2
4 + δ (( 1 + τ
2
) F (w∗) + h(w∗) ( K + τ1/2c−1/2avg )) τ
+ ( 2KD + γσ2
2 + 2L cmax + 2δKD τ
)√ m. (18)
Theorem 2 is proved in App. B of the supplementary material.
We now make a few comments about this result. First, recall that the expectation is taken with respect to the data distribution, but holds for any sample path of minibatch sizes. Further, the regret bound depends only on the summary statistics cmax, cavg, δ, and γ. These parameters capture the distribution of the processing speed at each node. Further, the impact of consensus error, which depends on the communication speed relative to the processing speed of each node, is summarized in the assumption of uniform accuracy on the distributed averaging mechanism. Thus, Theorem 2 is a sample path result that depends only coarsely on the distribution of the speed of data processing.
Next, observe that the dominant term is the final one, which scales in the aggregate number of samples m. The first term is approximately constant, only scaling with the monotonically increasing β and
cmax parameters. The terms containing characterizes the effect of imperfect consensus, which can be reduced by increasing the number of rounds of consensus. The effect of variability across c(t) is reflected in the terms containing the cmax, cavg and δ parameters. If perfect consensus were achieved ( = 0) then all components of the final term that scales in √ m would disappear except for the term that contains the minibatch skewness parameter γ. It is through this term that the amount of useful computation performed in each epoch (bi(t) ≤ ci(t)) enters the result. In the special case of constant minibatch size cmax = cavg and δ = 0, we have the following corollary.
Corollary 3 If c(t) = c for all t ∈ [τ ] and the consensus error ≤ 1/c, then the expected regret is
R(τ) = O(c+ √ m). (19)
Furthermore, if c = mρ for a constant ρ ∈ (0, 1/2], then R(τ) = O( √ m).

heading: 4.3 EXPECTED REGRET ANALYSIS

text:
We can translate Theorem 2 and Cor. 3 to a regret bound averaged over the sample path. Since the summary statistics cmax, cavg, δ, and γ are sufficient to bound the regret, we assert a joint distribution p over these terms rather than over the sample path btot(τ), ctot(τ). For the following result, we need only specify several moments of the distribution. In Sec. 5 we will take the further step of choosing a specific distribution p.
Theorem 4 Let c̄ = Ep[c(t)] so that m̄ = τ c̄ is the expected total work that can be completed in τ epochs. Also, let 1/b̂ = Ep[1/b(t)]. If averaging consensus has additive accuracy , then the expected regret is bounded by
Ep[R(τ)] ≤ c̄ [ F (w(1))− F (w∗) + β̄(τ)h(w∗) ] + 3K2 2c̄5/2
4 +
( 2KD + c̄σ2
2b̂ + 2L c̄
)√ m̄.
Theorem 4 is proved in App. F of the supplementary material. Note that this expected regret is over both the i.i.d. choice of data samples and the i.i.d. choice of (b(t), c(t)) pairs.
Corollary 5 If ≤ 1/c̄, the expected regret is
Ep[R(τ)] ≤ O(c̄+ √ m̄). (20)
Further, if c̄ = m̄ρ for a constant ρ ∈ (0, 1/2), then E[R] ≤ O( √ m̄).
Remark 1 Note that by letting = 0, we can immediately find the results for master-worker setup.

heading: 5 WALL TIME ANALYSIS

text:
In the preceding section we studied regret as a function of the number of epochs. The advantages of AMB is the reduction of wall time. That is, AMB can get to same convergence in less time than fixed minibatch approaches. Thus, in this section, we caracterize the wall time performance of AMB.
In AMB, each epoch corresponds to a fixed compute time T . As we have already commented, this contrasts with fixed minibatch approaches where they have variable computing times. We refer “Fixed MiniBatch" methods as FMB. To gain insight into the advantages of AMB, we develop an understanding of the regret per unit time.
We consider an FMB method in which each node computes computes b/n gradients, where b is the size of the global minibatch in each epoch. Let Ti(t) denote the amount of time taken by node i to compute b/n gradients for FMB method. We make the following assumptions:
Assumption 1 The time Ti(t) follows an arbitrary distribution with the mean µ and the variance σ2. Further, Ti(t) is identical across node index i and epoch index t. .
Assumption 2 If node i takes Ti(t) seconds to compute b/n gradients in the t-th epoch, then it will take nTi(t)/b seconds to compute one gradient.
Lemma 6 Let Assumptions 1 and 2 hold. Let the FMB scheme have a minibatch size of b. Let b̄ be the expected minibatch size of AMB. Then, if we fix the computation time of an epoch in AMB to T = (1 + n/b)µ, we have b̄ ≥ b.
Lemma 6 is proved in App. G and it shows that the expected minibatch size of AMB is at least as big as FMB if we fix T = (1 + n/b)µ. Thus, we get same (or better) expected regret bound. Next, we show that AMB achieve this in less time.
Theorem 7 Let Assumptions 1 and 2 hold. Let T = (1 + n/b)µ and minibatch size of FMB is b. Let SA and SF be the total compute time across τ epochs of AMB and FMB, respectively, then
SF ≤ ( 1 + σ
µ
√ n− 1 ) SA. (21)
The proof is given in App. G. Lemma 6 and Theorem 7 show that our method attains the same (or better) bound on the expected regret that is given in Theorem 4 but is at most ( 1 + σ/µ √ n− 1 ) faster than traditional FMB methods. In Bertsimas et al. (2006), it was shown this bound is tight and there is a distribution that achieves it. In our setup, there are no analytical distributions that exactly match with finishing time distribution. Recent papers on stragglers Lee et al. (2018); S. Dutta & Nagpurkar (2018) use the shifted exponential distribution to model Ti(t). The choice of shifted exponential distribution is motivated by the fact that it strikes a good balance between analytical tractability and practical behavior. Based on the assumption of shifted exponential distribution, we show that AMB is O(log(n)) faster than FMB. This result is proved in App. H.

heading: 6 NUMERICAL EVALUATION

text: To evaluate the performance of AMB and compare it with that of FMB, we ran several experiments on Amazon EC2 for both schemes to solve two different classes of machine learning tasks: linear regression and logistic regression using both synthetic and real datasets. In this section we present error vs. wall time performance using two experiments. Additional simulations are given in App. I

heading: 6.1 DATASETS

text:
We solved two problems using two datasets: synthetic and real. Linear regression problem was solved using synthetic data. The element of global minimum parameter, w∗ ∈ Rd, is generated from the multivariate normal distribution N (0, I). The workers observe a sequence of pairs (xi(s), yi(s)) where s is the time index, data xi(s) ∈ Rd are i.i.d. N (0, I), and the labels yi(s) ∈ R such that yi(s) = xi(s)
Tw∗+ηi(s). The additive noise sequence ηi(s) ∈ R is assumed to be i.i.dN (0, 10−3). The aim of all nodes is to collaboratively learn the true parameter w∗. The data dimension is d = 105.
For the logistic regression problem, we used the MNIST images of numbers from 0 to 9. Each image is of size 28 × 28 pixels which can be represented as a 784-dimensional vector. We used MNIST training dataset that consists of 60,000 data points. The cost function is the cross-entropy function J
J(y) = − ∑ i 1[y = i]P(y = i|x) (22)
where x is the observed data point sampled randomly from the dataset, y is the true label of x. 1[.] is the indicator function and P(y = i|x) is the predicted probability that y = i given the observed data point x which can be calculated using the softmax function. In other words, P(y = i|x) = ewix/ ∑ j e wjx. The aim of the system is to collaboratively learn the parameter w ∈ Rc×d, where c = 10 classes and d = 785 the dimension (including the bias term) that minimizes the cost function while streaming the inputs x online.

heading: 6.2 EXPERIMENTS ON EC2

text:
We tested the performance of AMB and FMB schemes using fully distributed setup. We used a network consisting of n = 10 nodes, in which the underlying network topology is given in Figure 2 of App. I.1. In all our experiments, we used t2.micro instances and ami-6b211202, a publicly available
Amazon Machine Image (AMI), to launch the instances. Communication between nodes were handled through Message Passing Interface (MPI).
To ensure a fair comparison between the two schemes, we ran both algorithms repeatedly and for a long time and averaged the performance over the same duration. We also observed that the processors finish tasks much faster during the first hour or two before slowing significantly. After that initial period, workers enter a steady state in which they keep their processor speed relatively constant except for occasional bursts. We discarded the transient behaviour and considered the performance during the steady-state.

heading: 6.2.1 LINEAR REGRESSION

text:
We ran both AMB and FMB in a fully distributed setting to solve the linear regression problem. In FMB, each worker computed b = 6000 gradients. The average compute time during the steady-state phase was found to be 14.5 sec. Therefore, in AMB case, the compute time for each worker was set to be T = 14.5 sec. and we set Tc = 4.5 sec. Workers are allowed r = 5 average rounds of consensus to average their calculated gradients.
Figure 1(a) plots the error vs. wall time, which includes both computation and communication times. One can notice AMB clearly outperforms FMB. In fact, the total amount of time spent by FMB to finish all the epochs is larger than that spent by AMB by almost 25% as shown in Figure 1(a) (e.g., the error rate achieved by FMB after 400 sec. has already been achieved by AMB after around 300 sec.). We notice, both scheme has the same average inter-node communication times. Therefore, when ignoring inter-node communication times, this ratio increases to almost 30%.

heading: 6.2.2 LOGISTIC REGRESSION

text:
In here we perform logistic regression using n = 10 distributed nodes. The network topology is as same as above. The per-node fixed minibatch in FMB is b/n = 800 while the fixed compute time in AMB is T = 12 sec. and the communication time Tc = 3 sec. As in the linear regression experiment above, the workers on average go through r = 5 round of consensus.
Figures 1(b) shows the achieved cost vs. wall clock time. We observe AMB outperforms FMB by achieving the same error rate earlier. In fact, Figure 1(b) demonstrates that AMB is about 1.7 times faster than FMB. For instance, the cost achieved by AMB at 150 sec. is almost the same as that achieved by FMB at around 250 sec.

heading: 7 CONCLUSION

text: We proposed a distributed optimization method called Anytime MiniBatch. A key property of our scheme is that we fix the computation time of each distributed node instead of minibatch size. Therefore, the finishing time of all nodes are deterministic and does not depend on the slowest processing node. We proved the convergence rate of our scheme in terms of the expected regret bound. We performed numerical experiments using Amazon EC2 and showed our scheme offers significant improvements over fixed minibatch schemes.

heading: 8 ACKNOWLEDGMENT

text: This work was supported by the National Science Foundation (NSF) under Grant CCF-1217058, by the Natural Science and Engineering Research Council (NSERC) of Canada, including through a Discover Research Grant, by the NSERC Postdoctoral Fellowship, and by the Oman Government Post Graduate Scholarship

heading: A AMB ALGORITHM

text:
The pseudocode of the Anytime Minibatch scheme operating in a distributed setting is given in Algorithm 1. Line 2 is for initialization purpose. Lines 3 − 8 corresponds to the compute phase during which each node i calculates bi(t) gradients. The consensus phase steps are given in lines 9− 21. Each node first averages the gradients (line 9) and calculates the initial messages mi(t) it will share with its neighbours (line 10). Lines 14− 19 corresponds to the communication rounds that results in distributed averaging of the dual variable zi(t+ 1) (line 21). Finally, line 22 represents the update phase in which each node updates its primal variable wi(t+ 1).
For the hub-and-spoke configuration, one can easily modify the algorithm as only a single consensus round is required during which all workers send their gradients to the master node which calculates z(t+ 1) and w(t+ 1) followed by a communication from the master to the workers with the updated w(t+ 1).
Algorithm 1 AMB Algorithm 1: for all t = 1, 2, ... do 2: initialize gi(t) = 0, bi(t) = 0 3: T0 = current_time 4: while current_time− T0 ≤ T do 5: receive input xi(t, s) sampled i.i.d. from Q 6: calculate gi(t) = gi(t) +∇f(wi(t), xi(t, s)) 7: bi(t) + + 8: end while 9: start consensus rounds 10: gi(t) = 1
bi(t) gi(t)
11: m(0)i = nbi(t)[zi(t) + gi(t)] 12: set k = 0 13: T1 = current_time 14: while current_time− T1 ≤ Tc do 15: receive mkj ,∀j ∈ Ni 16: m(k+1)i = ∑ j∈Ni Pi,jm k j 17: send m(k+1)i to all nodes in Ni 18: k + + 19: end while 20: ri(t) = k 21: zi(t+ 1) = 1 b(t)m (ri(t)) i
22: wi(t+ 1) = arg minw∈W { 〈w, zi(t+ 1)〉+ β(t+ 1)h(w) } 23: end for

heading: B PROOF OF THEOREM 2

text:
In this section, we prove Theorem 2. There are three factors impacting the convergence of our scheme; first is that gradient is calculated with respect to f(w, x) rather than directly computing the exact gradient∇wF (w), the second factor is the errors due to limited consensus rounds, and the last factor is that we have variable sized minibatch size over epochs. We bound these errors to find the expected regret bound with respect to a sample path.
Let w(t) be the primal variable computed using the exact dual z(t), cf. 12:
w(t) = arg min w∈W {〈w, z(t)〉+ β(t)h(w)} (23)
From (Tsianos & Rabbat, 2016, Lemma 2), we have
‖wi(t)− w(t)‖ ≤ 1
β(t) ‖zi(t)− z(t)‖, ∀i ∈ [n]
≤ β(t) . (24)
Recall that zi(t) is the dual variable after r rounds of consensus. The last step is due to Lemma 1. Let X(t) be the total set of samples processed by the end of t-th epoch:
X(t) := {xi(t′, s) : i ∈ [n], t′ ∈ [t], s ∈ [c(t)]} . Let E[·] denote the expectation over the data set X(τ) where we recall τ is the number of epochs. Note that conditioned on X(t− 1) the wi(t) and xi(t, s) are independent according to equation 7. Thus,
E [f (wi(t), xi(t, s))] = E [ Exi(t,s) [f (wi(t), xi(t, s)) |X(t− 1)] ] = E [F (wi(t))] . (25)
where equation 25 is due to equation 10. From equation 17 we have
E [ R|btot(τ), ctot(τ) ] = τ∑ t=1 n∑ i=1 ci(t)∑ s=1 E [ f ( wi(t), xi(t, s) ) − F (w∗) ] (26)
= τ∑ t=1 n∑ i=1 ci(t)∑ s=1 E [F (wi(t))− F (w∗)] . (27)
Now, we add and subtract F (w(t)) from equation 17 to get
E[R|btot(τ), ctot(τ)] = τ∑ t=1 n∑ i=1 ci(t)∑ s=1 E [F (w(t))− F (w∗) + F (wi(t))− F (w(t))]
= τ∑ t=1 c(t)E[F (w(t))− F (w∗)] + τ∑ t=1 n∑ i=1 ci(t)E[F (wi(t))− F (w(t))]
≤ τ∑ t=1 c(t)E[F (w(t))− F (w∗)] + τ∑ t=1 n∑ i=1 ci(t)LE[‖wi(t)− w(t)‖] (28)
≤ τ∑ t=1 c(t)E[F (w(t))− F (w∗)] + τ∑ t=1 n∑ i=1 ci(t)L β(t) (29)
= τ∑ t=1 c(t)E[F (w(t))− F (w∗)] + L τ∑ t=1 c(t) β(t) . (30)
Note that equation 28 and equation 29 are due to equation 8 and equation 24. Now, we bound the first term in the following Lemma, which is proved in App. C.
Lemma 8 Let β(t) = K + α(t) where α(t) = √
t µ . Then
τ∑ t=1 c(t)E [F (w(t))− F (w∗)] ≤ c(1)[F (w(1))− F (w∗)] + τ∑ t=2 (c(τ)− c(t))F (w∗)
+ c(τ)β(τ)h(w∗) + τ−1∑ t=1 KD β(t) + τ−1∑ t=1 c(t+ 1)σ2 4b(t)α(t) + K2 2 4 τ−1∑ t=1 c(t+ 1) α(t)β(t)2 + E[ψ] (31)
where
E[ψ] ≤ τ−1∑ t=1 (c(t)− c(t+ 1)) ( (t− 1)F (w∗) + β(t)h(w∗) + 2KD √ µt ) . (32)
In equation 31, the first term is a constant, which depends on the initialization. The fourth and the sixth terms are due to consensus errors and the fifth term is due to noisy gradient calculation. The second and the last term E[ψ] are due to variable minibatch sizes.
Now, the total regret can be obtained by using Lemma 8 in equation 30
E[R|btot(τ), ctot(τ)] ≤ c(1)[F (w(1))− F (w∗)] + τ∑ t=2 (c(τ)− c(t))F (w∗) + c(τ)β(τ)h(w∗)
+ τ−1∑ t=1 KD β(t) + + τ−1∑ t=1 c(t+ 1)σ2 4b(t)α(t) + K2 2 4 τ−1∑ t=1 c(t+ 1) α(t)β(t)2 + E[ψ] + L τ∑ t=1 c(t) β(t) . (33)
Define γ = maxt∈{1,τ−1} c(t+1) b(t) , cmax = maxt∈[τ ] c(t), and δ = max{t,t′}∈{1,τ−1} |c(t) − c(t ′)|. Then
E[R|btot(τ), ctot(τ)] ≤ cmax[F (w(1))− F (w∗) + β(τ)h(w∗)] + τ∑ t=2 δF (w∗)
+ τ−1∑ t=1 KD β(t) + γσ2 4 τ−1∑ t=1 1 α(t) + K2 2cmax 4 τ−1∑ t=1
1
α(t)β(t)2 + E[ψ] + L cmax τ∑ t=1 1 β(t) (34)
In App. D, we bound ∑τ−1 t=1 1 α(t) and ∑τ−1 t=1 1 α(t)β(t)2 terms. Using them, we have
E[R|btot(τ), ctot(τ)] ≤ cmax[F (w(1))− F (w∗) + β(τ)h(w∗)] + δτF (w∗) + 2KD √ µτ
+ 2γσ2
√ µτ
4 +
3K2 2cmaxµ 3/2
4 + 2L cmax
√ µτ + E[ψ] (35)
E[R|btot(τ), ctot(τ)] ≤ cmax[F (w(1))− F (w∗) + β(τ)h(w∗)] + δτF (w∗)
+ 3K2 2cmaxµ 3/2
4 +
( 2KD + γσ2
2 + 2L cmax
) √ µτ + E[ψ] (36)
Now we bound E[ψ]. Using δ = max{t,t′}∈{1,τ−1} |c(t)− c(t′)| in equation 32, we can write
E[ψ] ≤ τ−1∑ t=1 δ ( (t− 1)F (w∗) + β(t)h(w∗) + 2KD √ µt )
≤ δ ( F (w∗)
τ−1∑ t=1 (t− 1) + h(w∗) τ−1∑ t=1 ( K + √ t µ ) + τ−1∑ t=1 2KD √ µt )
≤ δ ( τ2
2 F (w∗) + h(w∗)
( K + √ τ
µ
) τ + 2KD √ µττ ) ≤ δ ( τ
2 F (w∗) + h(w∗)
( K + √ τ
µ
) + 2KD √ µτ ) τ (37)
By substituting equation 37 in equation 36
E[R|btot(τ), ctot(τ)] ≤ cmax[F (w(1))− F (w∗) + β(τ)h(w∗)] + δτF (w∗)
+ 3K2 2cmaxµ 3/2
4 +
( 2KD + γσ2
2 + 2L cmax
) √ µτ
+ δ
( τ
2 F (w∗) + h(w∗)
( K + √ τ
µ
) + 2KD √ µτ ) τ (38)
By rearranging terms
E[R|btot(τ), ctot(τ)] ≤ cmax[F (w(1))− F (w∗) + β(τ)h(w∗)] + 3K2 2cmaxµ 3/2
4
+ δ (( 1 + τ
2
) F (w∗) + h(w∗) ( K + √ τ
µ
)) τ
+ ( 2KD + γσ2
2 + 2L cmax + 2δKD τ
) √ µτ (39)
Let µ = cavg = (1/τ) ∑τ t=1 c(t), then from equation 15 µτ = m and we substitute
E[R|btot(τ), ctot(τ)] ≤ cmax[F (w(1))− F (w∗) + β(τ)h(w∗)] + 3K2 2cmaxµ 3/2
4 + δ (( 1 + τ
2
) F (w∗) + h(w∗) ( K + τ1/2c−1/2avg )) τ
+ ( 2KD + γσ2
2 + 2L cmax + 2δKD τ
)√ m. (40)
This completes the proof of Theorem 2.

heading: C PROOF OF LEMMA 8

text:
Note that g(t) is calculated with respect to wi(t) by different nodes in equation 3. Let ḡ(t) be the minibatch calculated with respect to w(t) (given in equation 23) by all the nodes.
ḡ(t) = 1
b(t) n∑ i=1 bi(t)∑ s=1 ∇wf(w(t), xi(t, s)). (41)
Note that there are two types of errors in computing gradients. The first is common in any gradient based methods. That is, the gradient is calculated with respect to the function f(w, x), which is based on the data x instead of being a direct evaluation of∇wF (w). We denote this error as q(t):
q(t) = ḡ(t)−∇wF (w(t)). (42) The second error results from the fact that we use g(t) instead of ḡ(t). We denote this error as r(t):
r(t) = g(t)− ḡ(t). (43)
Lemma 9 The following four relations hold E[〈q(t), w∗ − w(t)〉] = 0,
E[〈r(t), w∗ − w(t)〉] = KD β(t) ,
E[‖q(t)‖2] = σ 2
b(t) ,
E[‖r(t)‖2] = K 2 2
β(t)2 .
The proof of Lemma 9 is given in App. E. Let lt(w) be the first order approximation of F (w) at w(t):
lt(w) = F (w(t)) + 〈∇wF (w(t)), w − w(t)〉. (44)
Let l̃t(w) be an approximation of lt(w) by replacing ∇wF (w(t)) with g(t)
l̃t(w) = F (w(t)) + 〈g(t), w − w(t)〉 (45) = F (w(t)) + 〈∇wF (w(t)), w − w(t)〉+ 〈q(t), w − w(t)〉+ 〈r(t), w − w(t)〉 (46) = lt(w) + 〈q(t), w − w(t)〉+ 〈r(t), w − w(t)〉. (47)
Note that equation 46 follows since g(t) = q(t) + r(t) +∇wF (w(t)). By using the smoothness of F (w), we can write
F (w(t+ 1)) ≤ lt(w(t+ 1)) + K
2 ‖w(t+ 1)− w(t)‖2
= l̃t(w(t+ 1))− 〈q(t), w − w(t)〉 − 〈r(t), w − w(t)〉+ K
2 ‖w(t+ 1)− w(t)‖2
= l̃t(w) + ‖q(t)‖‖w − w(t)‖+ ‖r(t)‖‖w − w(t)‖+ K
2 ‖w(t+ 1)− w(t)‖2. (48)
The last step is due to the Cauchy-Schwarz inequality. Let α(t) = β(t)−K. We add and subtract α(t)‖w(t+ 1)− w(t)‖2/2 to find
F (w(t+1)) ≤ l̃t(w(t+1))+‖q(t)‖‖w−w(t)‖− α(t)
4 ‖w(t+1)−w(t)‖2 +‖r(t)‖‖w−w(t)‖
− α(t) 4 ‖w(t+ 1)− w(t)‖2 + K + α(t) 2 ‖w(t+ 1)− w(t)‖2.
Note that
‖q(t)‖‖w − w(t)‖ − α(t) 4 ‖w(t+ 1)− w(t)‖2
= ‖q(t)‖2
4α(t) −
[ ‖q(t)‖√ 4α(t) − √ a(t) 4 ‖w(t+ 1)− w(t)‖ ]2 ≤ ‖q(t)‖ 2 4α(t) .
(49)
Similarly, we have that
‖r(t)‖‖w − w(t)‖ − α(t) 4 ‖w(t+ 1)− w(t)‖2 ≤ ‖r(t)‖ 2 4α(t) . (50)
Using equation 49, equation 50, and β(t) = K + α(t) in equation 48 we have
F (w(t+ 1)) ≤ l̃t(w(t+ 1)) + β(t) 2 ‖w(t+ 1)− w(t)‖2 + ‖q(t)‖ 2 4α(t) + ‖r(t)‖2 4α(t) (51)
The following Lemma gives a relation between w(t) and l̃t(w(t))
Lemma 10 The optimization stated in equation 23 is equivalent to
w(t) = arg min w∈W { t−1∑ t′=1 l̃t′(w) + β(t)h(w) } . (52)
By using the result (Dekel et al., 2012, Lemma 8), we have
β(t)
2 ‖w(t+ 1)− w(t)‖2 ≤ t−1∑ t′=1 l̃t′(w(t+ 1)) + (β(t))h(w(t+ 1))
− t−1∑ t′=1 l̃t′(w(t)) + (K + β(t))h(w(t)). (53)
Use equation 51 in equation 53 and substituting in β(t) = K + α(t) we get
F (w(t+ 1)) ≤ lt(w(t+ 1)) + t−1∑ t′=1 l̃t′(w(t+ 1))− t−1∑ t′=1 l̃t′(w(t)) + (K + α(t))h(w(t+ 1))
− (K + α(t))h(w(t)) + ‖q(t)‖ 2 + ‖r(t)‖2
4α(t)
≤ t∑
t′=1 l̃t′(w(t+ 1))− t−1∑ t′=1 l̃t′(w(t)) + (K + α(t+ 1))h(w(t+ 1))
− (K + α(t))h(w(t)) + ‖q(t)‖ 2 + ‖r(t)‖2
4α(t) , (54)
where equation 54 is due to the fact that α(t+ 1) ≥ α(t). Now, we use β(t) = K + α(t), multiply by c(t+ 1) and rewrite
c(t+1)F (w(t+1)) ≤ t∑
t′=1 c̃(t+1)lt′(w(t+1))− t−1∑ t′=1 c̃(t)lt′(w(t))+c(t+1)β(t+1)h(w(t+1))
− c(t)β(t)h(w(t)) + c(t+ 1)‖q(t)‖ 2 + ‖r(t)‖2
4α(t)
− (c(t+ 1)− c(t)) [ t−1∑ t′=1 l̃t′(w(t)) + β(t)h(w(t)) ] . (55)
Summing from t = 1 to τ − 1 we get
τ∑ t=2 c(t)F (w(t)) ≤ τ−1∑ t=1 c(τ)l̃t(w(τ)) + c(τ)β(τ)h(w(τ)) + τ−1∑ t=1 c(t+ 1) ‖q(t)‖2 + ‖r(t)‖2 4α(t)
+ τ−1∑ t=1 (c(t)− c(t+ 1)) [ t−1∑ t′=1 l̃t′(w(t)) + β(t)h(w(t)) ] .
Let ψ be the last two terms, i.e.,
ψ = τ−1∑ t=1 (c(t)− c(t+ 1)) [ t−1∑ t′=1 l̃t′(w(t)) + β(t)h(w(t)) ] . (56)
Then, using Lemma 10
τ∑ t=2 c(t)F (w(t)) ≤ τ−1∑ t=1 c(τ)l̃t(w ∗) + c(τ)β(τ)h(w∗) + τ−1∑ t=1 c(t+ 1) ‖q(t)‖2 + ‖r(t)‖2 4α(t) + ψ.
By substituting in equation 45 we continue
τ∑ t=2 c(t)F (w(t)) ≤ τ−1∑ t=1 c(τ)lt(w ∗) + τ−1∑ t=1 〈q(t), w − w(t)〉+ 〈r(t), w − w(t)〉
+ c(τ)β(τ)h(w∗) + τ−1∑ t=1 c(t+ 1) ‖q(t)‖2 + ‖r(t)‖2 4α(t) + ψ
≤ (τ − 1)c(τ)F (w∗) + τ−1∑ t=1 〈q(t), w − w(t)〉+ 〈r(t), w − w(t)〉
+ c(τ)β(τ)h(w∗) + τ−1∑ t=1 c(t+ 1) ‖q(t)‖2 + ‖r(t)‖2 4α(t) + ψ (57)
where equation 57 is due to convexity of F (w), i.e., ∑τ−1 t=1 lt(w
∗) ≤ (τ − 1)F (w∗). Adding and subtracting terms we find that
τ∑ t=1 c(t)[F (w(t))− F (w∗)] ≤ c(1)[F (w(1))− F (w∗)] + τ∑ t=2 (c(τ)− c(t))F (w∗)
+ τ−1∑ t=1 〈q(t), w − w(t)〉+ 〈r(t), w − w(t)〉
+ c(τ)β(τ)h(w∗) + τ−1∑ t=1 c(t+ 1) ‖q(t)‖2 + ‖r(t)‖2 4α(t) + ψ
Taking the expectation with respect to X(τ − 1)
E [ τ∑ t=1 c(t)[F (w(t))− F (w∗)] ] ≤ c(1)[F (w(1))− F (w∗)] + τ∑ t=2 (c(τ)− c(t))F (w∗)
+ c(τ)β(τ)h(w∗) + τ−1∑ t=1 E[〈q(t), w − w(t)〉] + E[〈r(t), w − w(t)〉]
+ τ−1∑ t=1 c(t+ 1) E[‖q(t)‖2] + [‖r(t)‖2] 4α(t) + E[ψ]
We use the bounds in Lemma 9 to get
E [ τ∑ t=1 c(t)[F (w(t))− F (w∗)] ] ≤ c(1)[F (w(1))− F (w∗)] + τ∑ t=2 (c(τ)− c(t))F (w∗)
+ c(τ)β(τ)h(w∗) + τ−1∑ t=1 KD β(t) + τ−1∑ t=1 c(t+ 1) 4α(t) ( σ2 b(t) + K2 2 β(t)2 ) + E[ψ].
We rewrite by rearranging terms
E [ τ∑ t=1 c(t)[F (w(t))− F (w∗)] ] ≤ c(1)[F (w(1))− F (w∗)] + τ∑ t=2 (c(τ)− c(t))F (w∗)
+ c(τ)β(τ)h(w∗) + τ−1∑ t=1 KD β(t) + τ−1∑ t=1 c(t+ 1)σ2 4b(t)α(t) + K2 2 4 τ−1∑ t=1 c(t+ 1) α(t)β(t)2 + E[ψ] (58)
Now we bound E[ψ]. From equation 56 we find
ψ = τ−1∑ t=1 (c(t)− c(t+ 1)) ( t−1∑ t′=1 l̃t′(w(t)) + β(t)h(w(t)) )
≤ τ−1∑ t=1 (c(t)− c(t+ 1)) ( t−1∑ t′=1 l̃t′(w ∗) + β(t)h(w∗) ) (59)
= τ−1∑ t=1 (c(t)− c(t+ 1)) ( t−1∑ t′=1 (lt′(w ∗) + 〈q(t′), w∗ − w(t′)〉+ 〈r(t′), w∗ − w(t′)〉) + β(t)h(w∗) ) (60) ≤ τ−1∑ t=1 (c(t)− c(t+ 1)) ( (t− 1)F (w∗) + β(t)h(w∗) + t−1∑ t′=1 〈q(t′), w∗ − w(t′)〉+ 〈r(t′), w∗ − w(t′)〉 ) ,
(61)
where equation 59 is due to Lemma 10, equation 60 is simple substitution of equation 45, and the last step is due to convexity of F (w). Now, we take the expectation over data samples X(τ − 1) E[ψ]
≤ τ−1∑ t=1 (c(t)− c(t+ 1))
( (t− 1)F (w∗) + β(t)h(w∗) +
t−1∑ t′=1 E[〈q(t′), w∗ − w(t′)〉] + E[〈r(t′), w∗ − w(t′)〉]
)
≤ τ−1∑ t=1 (c(t)− c(t+ 1))
( (t− 1)F (w∗) + β(t)h(w∗) +
t−1∑ t′=1 KD β(t′)
) (62)
≤ τ−1∑ t=1 (c(t)− c(t+ 1)) ( (t− 1)F (w∗) + β(t)h(w∗) + 2KD √ µt )
(63)
where Lemma 9 is used in equation 62 and the last step is due to equation 64. This completes the proof of Lemma 8.

heading: D PROOF OF BOUNDS USED IN APP. F

text:
We know β(t) = K + α(t). Let α(t) = √
t µ . Then, we have
τ−1∑ t=1 1 β(t) ≤ 2√µτ. (64)
Similarly, τ−1∑ t=1
1
α(t)β(t)2 = τ−1∑ t=1
1
α(t)(K + α(t)2)
≤ τ−1∑ t=1 1 α(t)3
= µ3/2 τ−1∑ t=1 t−3/2
≤ µ3/2 ( 1 + ∫ τ 1 t−3/2dt ) ≤ 3µ3/2. (65)

heading: E PROOF OF LEMMA 9

text:
Note that the expectation with respect to xs(t)
E[f(w(t), xs(t))] = E[F (w(t))]. (66) Also we use the fact that gradient and expectation operators commutes
E[〈∇f(w(t)), xs(t), w(t)〉] = E[〈F (w(t)), w(t)〉]. (67) Bounding E[〈q(t), w∗ − w(t)〉] and E[‖q(t)‖2] follows the same approach as in (Dekel et al., 2012, Appendix A.1) or Tsianos & Rabbat (2016). Now, we find E[〈r(t), w∗ − w(t)〉] E[〈r(t), w∗ − w(t)〉]
= E 〈 1 b(t) n∑ i=1 bi(t)∑ s=1 ∇wf(wi(t), xi(t, s))− 1 b(t) n∑ i=1 bi(t)∑ s=1 ∇wf(w(t), xi(t, s)), w∗ − w(t) 〉 = E 〈 1 b(t) n∑ i=1 bi(t)∑ s=1 ∇wF (wi(t))− 1 b(t) n∑ i=1 bi(t)∑ s=1 ∇wF (w(t)), w∗ − w(t)
〉 = 1
b(t) n∑ i=1 bi(t)E [〈∇wF (wi(t))−∇wF (w(t)), w∗ − w(t)〉]
≤ 1 b(t) n∑ i=1 bi(t)E [‖∇wF (wi(t))−∇wF (w(t))‖‖w∗ − w(t)‖] (68)
≤ 1 b(t) n∑ i=1 bi(t)E [K‖wi(t)− w(t)‖D] (69)
where equation 68 is due to the Cauchy-Schwarz inequality and equation 69 due to equation 9 and D = maxw,u∈W ‖w − u‖. Using equation 24
E[〈r(t), w∗ − w(t)〉] ≤ 1 b(t) n∑ i=1 bi(t)KD β(t)
= KD
β(t) . (70)
Now we find E[‖r(t)‖2].
E[‖r(t)‖2] = E  ∥∥∥∥∥∥ 1b(t) n∑ i=1 bi(t)∑ s=1 ∇wf(wi(t), xi(t, s))−∇wf(w(t), xi(t, s)) ∥∥∥∥∥∥ 2
≤ E   1 b(t) n∑ i=1 bi(t)∑ s=1 ‖∇wf(wi(t), xi(t, s))−∇wf(w(t), xi(t, s))‖ 2
≤ E   1 b(t) n∑ i=1 bi(t)∑ s=1 K ‖wi(t)− w(t)‖ 2
≤  1 b(t) n∑ i=1 bi(t)∑ s=1 K β(t) 2
= K2 2
β(t)2 . (71)

heading: F PROOF OF THEOREM 4

text:
By definition
c(t) = n∑ i=1 ci(t) (72)
where ci(t) is the total number of gradients computed at the node i in the t-th epoch. We assume ci(t) is independent across network and is independent and identically distributed according to some processing time distribution p across epochs. Let c̄ = Ep[c(t)] and let 1/b̂ = Ep[1/b(t)]. From Lemma 8 we have that
τ∑ t=1 c(t)E [F (w(t))− F (w∗)] ≤ c(1)[F (w(1))− F (w∗)] + τ∑ t=2 (c(τ)− c(t))F (w∗)
+ c(τ)β(τ)h(w∗) + τ−1∑ t=1 KD β(t)
+ τ−1∑ t=1 c(t+ 1)σ2 4b(t)α(t) + K2 2 4 τ−1∑ t=1 c(t+ 1) α(t)β(t)2 + E[ψ]. (73)
Let α(t) = √ t/c̄. Now take expectation over the c(t) to get
Ep [ τ∑ t=1 c(t)E [F (w(t))− F (w∗)] ] ≤ c̄[F (w(1))− F (w∗)] + c̄β(τ)h(w∗) + τ−1∑ t=1 KD β(t)
+ τ−1∑ t=1 Ep [ c(t+ 1) 4α(t) ( σ2 b(t) + K2 2 β(t)2 )] + Ep[E[ψ]]
= c̄[F (w(1))− F (w∗)] + c̄β(τ)h(w(τ)) + τ−1∑ t=1 KD β(t)
+ τ−1∑ t=1 c̄ 4α(t) ( σ2 b̂ + K2 2 β(t)2 ) . (74)
The last step is due to the fact that c(t+ 1) and b(t) are independent since these are in two different epochs. Further Ep[E[ψ|c(t)]] = 0. After further simplification through the use of Appendix D, we get
Ep [ τ∑ t=1 c(t)E [F (w(t))− F (w∗)] ] ≤ c̄[F (w(1))− F (w∗) + β̄(τ)h(w(τ))] + 2KD √ c̄τ
+ c̄σ2 √ c̄τ
2b̂ +
3K2 2c̄5/2
4 . (75)
Taking the expectation over c(t) in equation 30, we have
Ep[E[R|btot(τ), ctot(τ)]] ≤ Ep [ τ∑ t=1 c(t)E [F (w(t))− F (w∗)] ] + L τ∑ t=1 c̄ β(t)
≤ c̄[F (w(1))− F (w∗) + β̄(τ)h(w(τ))] + 2KD √ c̄τ + c̄σ2 √ c̄τ
2b̂ +
3K2 2c̄5/2
4 + 2L c̄
√ c̄τ . (76)
By definition
m = τ∑ t=1 c(t). (77)
Then m̄ = Ep = c̄τ . By substituting m̄ and rearranging we find that
Ep[E[R|btot(τ), ctot(τ)]] ≤ c̄[F (w(1))− F (w∗) + β̄(τ)h(w(τ))] + 3K2 2c̄5/2
4
+ ( 2KD + c̄σ2
2b̂ + 2L c̄
)√ m̄ (78)

heading: G PROOF OF THEOREM 7

text:
Proof: Consider an FMB method in which each node computes b/n gradients per epoch, with Ti(t) denoting the time taken to complete the job.
Also consider AMB with a fixed epoch duration of T . The number of gradient computations completed by the i-th node in the t-th epoch is
bi(t) =
⌊ bT
nTi(t) ⌋ ≥ bT nTi(t) − 1. (79)
Therefore, the minibatch size b(t) computed in AMB in the t-th epoch is
b(t) = n∑ i=1 bi(t) ≥ n∑ i=1 bT nTi(t) − n = bT n n∑ i=1 1 Ti(t) − n. (80)
Taking the expectation over the distribution of Ti(t) in (80), and applying Jensen’s inequality, we find that
Ep[b(t)] ≥ bT
n n∑ i=1 Ep [ 1 Ti(t) ] − n ≥ bT n n∑ i=1
1
Ep[Ti(t)] − n = bTµ−1 − n.
where Ep[Ti(t)] = mu. Fixing the computing time to T = (1 + n/b)µ we find that Ep[b(t)] ≥ b, i.e., the expected minibatch of AMB is at least as large as the minibatch size b used in the FMB.
The expected computing time for τ epochs in our approach is
SA = τT = τ(1 + n/b)µ. (81)
In contrast, in the FMB approach the finishing time of the tth epoch is maxi∈[n] Ti(t). Using the result of Arnold & Groeneveld (1979); Bertsimas et al. (2006) we find that
Ep[max i∈[n]
Ti(t)] ≤ µ+ σ √ n− 1, (82)
where σ is the standard deviation of Ti(t). Thus τ epochs takes expected time
SF = τEp[max i∈[n]
Ti(t)] ≤ τ ( µ+ σ √ n− 1 ) (83)
Taking the ratio of the two finishing times we find that
SF SA ≤ µ+ σ
√ n− 1
(1 + n/b)µ =
( 1 + σ
µ
√ n− 1 ) (1 + n/b)−1. (84)
For parallelization to be meaningful, the minibatch size should be much larger than number of nodes and hence b n. This means (1 + n/b) ≈ 1 for any system of interest. Thus,
SF ≤ ( 1 + σ
µ
√ n− 1 ) SA, (85)
This completes the proof of Theorem 7.

heading: H SHIFTED EXPONENTIAL DISTRIBUTION

text:
The shifted exponential distribution is given by
pTi(t)(z) = λ exp (−λ(z − ζ)) , ∀z ≥ ζ (86)
where λ ≥ 0 and ζ ≥ 0. The shifted exponential distribution models a minimum time (ζ) to complete a job, and a memoryless balance of processing time thereafter. The λ parameter dictates the average processing speed, with larger λ indicating faster processing. The expected finishing time is Ep[Ti(t)] = λ−1 + ζ. Therefore,
SA = τT = τ(1 + n/b)(λ −1 + ζ). (87)
By using order statistics, we can find
Ep[max i∈[n]
Ti(t)] = λ −1 log(n) + ζ, (88)
and thus τ epochs takes expected time SF = τ ( λ−1 log(n) + ζ ) (89)
Taking the ratio of the two finishing times we find that
SF SA =
( λ−1 log(n) + ζ ) (1 + n/b)(λ−1 + ζ) . (90)
For parallelization to be meaningful we must have much more data than nodes and hence b n. This means that the first factor in the denominator will be approximately equal to one for any system of interest. Therefore, in the large n regime,
lim n→∞
SF = log(n)
1 + λζ SA, (91)
which is order-log(n) since the product λζ is fixed.

heading: I SUPPORTING DISCUSSION OF NUMERICAL RESULTS OF MAIN PAPER AND ADDITIONAL EXPERIMENTS

text:
In this section, we present additional details regarding the numerical results of Section 6 of the main paper as well as some new results. In Appendix I.1, we detail the network used in Section 6 and, for a point of comparison, implement the same computations in a master-worker network
topology. In Appendix I.2, we model the compute times of the nodes as shifted exponential random variables and, under this model, present results contrasting AMB and FMB performance for the linear regression problem. In Appendix I.3 we present an experimental methodology for simulating a wide variety of straggler distributions in EC2. By running background jobs on some of the EC2 nodes we slow the foreground job of interest, thereby simulating a heavily-loaded straggler node. Finally, in Appendix I.4, we present another experiment in which we also induce stragglers by forcing the nodes to make random pauses between two consecutive gradient calculations. We present numerical results for both settings as well, demonstrating the even greater advantage of AMB versus FMB when compared to the results presented in Section 6.
I.1 SUPPORTING DETAILS FOR RESULTS OF SECTION 6 AND COMPARATIVE RESULTS FOR HUB-AND-SPOKE TOPOLOGY
As there was not space in the main text, in Figure 2 we diagram the connectivity of the distributed computation network used in Section 6. The second largest eigenvalue of the P matrix corresponding to this network, which controls the speed of consensus, is 0.888.
In Section 6, we presented results for distributed logistic regression in the network depicted in Figure 2. Another network topology of great interest is the hub-and-spoke topology wherein a central master node is directly connected to a number of worker nodes, and worker nodes are only indirectly connected via the master. We also ran the MNIST logistic regression experiments for this topology. In our experiments there were 20 nodes total, 19 workers and one master. As in Sec.6 we used t2.micro instances and ami-62b11202 to launch the instances. We set the total batch size used in FMB to be b = 3990 so, with n = 19 worker each worker calculated b/n = 210 gradients per batch. Working with this per-worker batch size, we found the average EC2 compute time per batch to be 3 sec. Therefore, we used a compute time of T = 3 sec. in the AMB scheme while the communication time of Tc = 1 sec. Figure 3 plots the logistical error versus wall clock time for both AMB and FMB in the master-worker (i.e., hub-and-spoke) topology. We see that the workers implementing AMB far outperform those implementing FMB.
I.2 MODELING STRAGGLERS USING A SHIFTED EXPONENTIAL DISTRIBUTION
In this section, we model the speed of each worker probabilistically. Let Ti(t) denote the time taken by worker i to calculate a total of 600 gradients in the t-th epoch. We assume Ti(t) follows a shifted exponential distribution and is independent and identically distributed across nodes (indexed by i) and across computing epochs (indexed by t). The probability density function of the shifted exponential is pTi(t)(z) = λe
−λ(z−ζ). The mean of this distribution is µ = ζ + λ−1 and its variance is λ−2. Conditioned on Ti(t) we assume that worker i makes linear progress through the dataset. In other words, worker i takes kTi(t)/600 seconds to calculate k gradients. (Note that our model allows k to exceed 600.) In the simulation results we present we choose λ = 2/3 and ζ = 1. In the AMB scheme, node i computes bi(t) = 600T/Ti(t) gradients in epoch t where T is the fixed computing time allocated. To ensure a fair comparison between FMB and AMB, T is chosen according to Thm. 7. This means that E[b(t)] ≥ b where b(t) = ∑ i bi(t) and b is the fixed minibatch size used by FMB. Based on our parameter choices, T = (1 + n/b)µ = (1 + n/b) (λ−1 + ζ) = 2.5.
Figure 4 plots the average error rate of the linear regression problem versus wall clock time for both FMB and AMB assuming a distributed computation network depicted in Figure 2. In these results, we
generate 20 sample paths; each sample path is a set {Ti(t)} for i ∈ {1, . . . , 20} and t ∈ {1, . . . 20}. At the end of each of the 20 computing epoch we conduct r = 5 rounds of consensus. As can be observed in Fig. 4, for all 20 sample paths AMB outperforms FMB. One can also observe that there for neither scheme is there much variance in performance across sample paths; there is a bit more for FMB than for AMB. Due to this small variability, in the rest of this discussion we pick a single sample path to plot results for.
Figures 5a and 5b help us understand the performance impact of imperfect consensus on both AMB and on FMB. In each we plot the consensus error for r = 5 rounds of consensus and perfect consensus (r =∞). In Fig. 5a we plot the error versus number of computing epochs while in Figure 5b we plot it versus wall clock time. In the former there is very little difference between AMB and FMB. This is due to the fact that we have set the computation times so that the expected AMB batch size equals the fixed FMB batch size. On the other hand, there is a large performance gap between the schemes when plotted versus wall clock time. It is thus in terms of real time (not epoch count) where AMB strongly outperforms FMB. In particular, AMB reaches an error rate of 10−3 in less than half the time that it takes FMB (2.24 time faster, to be exact).
I.3 PERFORMANCE WITH INDUCED STRAGGLERS ON EC2
In this section, we introduce a new experimental methodology for studying the effect of stragglers. In these experiments we induce stragglers amongst our EC2 micro.t2 instances by running background jobs. In our experiments, there were 10 compute nodes interconnected according to the topology of Figure 2. The 10 worker nodes were partitioned into three groups. In the first group we run two background jobs that “interfere” with the foreground (AMB or FMB) job. The background jobs we used were matrix multiplication jobs that were continuously performed during the experiment. This first group will contain the “bad” straggler nodes. In the second group we run a single background job. These will be the intermediate stragglers. In the third group we do not run background jobs. These will be the non-stragglers. In our experiments, there are three bad stragglers (workers 1, 2, and 3), two intermediate stragglers (workers 4 and 5), and five non-stragglers (workers 6-10).
We first launch the background jobs in groups one and two. We then launch the FMB jobs on all nodes at once. By simultaneously running the background jobs and FMB, the resources of nodes in the first two groups are shared across multiple tasks resulting in an overall slowdown in their computing. The slowdown can be clearly observed in Figure 6a which depicts the histogram of the FMB compute times. The count (“frequency”) is the number of jobs (fixed mini batches) completed as a function of the time it took to complete the job. The third (fast) group is on the left, clustered around 10 seconds per batch, while the other two groups are clustered at roughly 20 and 30 seconds. Figure 6b depicts the same experiment as performed with AMB: first launching the background jobs, and then launching AMB in parallel on all nodes. In this scenario compute time is fixed, so the histogram plots the number of completed batches completed as a function of batch size. In the AMB experiments the bad straggler nodes appear in the first cluster (centered around batch size of 230) while the faster nodes appear in the clusters to the right. In the FMB histogram per-worker batch size was fixed to 585 while in the AMB histograms the compute time was fixed to 12 sec.
We observe that these empirical results confirm the conditionally deterministic aspects of our statistical model of Appendix I.2. This was the portion of the model wherein we assumed that nodes make linear progress conditioned on the time it takes to compute one match. In Figure 6a, we observe it takes the non-straggler nodes about 10 seconds to complete one fixed-sized minibatch. It takes the intermediate nodes about twice as long. Turning to the AMB plots we observe that, indeed, the intermediate stragglers nodes complete only about 50% of the work that the non-straggler nodes do in the fixed amount of time. Hence this “linear progress” aspect of our model is confirmed experimentally.
Figure 7 illustrates the performance of AMB and FMB on the MNIST regression problem in the setting of EC2 with induced stragglers. As can be observed by comparing these results to those presented in Figure 1b of Section 6, the speedup now effected by AMB over FMB is far larger. While in Figure 1b the AMB was about 50% faster than FMB it is now about twice as fast. While previously AMB effect a reduction of 30% in the time it took FMB to hit a target error rate, the reduction now
is about 50%. Generally as the variation amongst stragglers increases we will see a corresponding improvement in AMB over FMB.
I.4 PERFORMANCE WITH INDUCED STRAGGLERS ON AN HPC PLATFORM
We conducted another experiment on a high-performance computing (HPC) platform that consists of a large number of nodes. Jobs submitted to this system are scheduled and assigned to dedicated nodes. Since nodes are dedicated, no obvious stragglers exist. Furthermore, users of this platform do not know which tasks are assigned to which node. This means that we were not able to use the same approach for inducing stragglers on this platform as we used on EC2. In EC2, we ran background simulations on certain nodes to slow them down. But, since in this HPC environment we cannot tell where our jobs are placed, we are not able to place additional jobs on a subset of those same nodes to induce stragglers. Therefore, we used a different approach for inducing stragglers as we now explain.
First, we ran the MNIST classification problem using 51 nodes: one master and 50 worker nodes where workers nodes were divided into 5 groups. After each gradient calculation (in both AMB
and FMB), worker i pauses its computation before proceeding to the next iteration. The duration of the pause of the worker in epoch t after calculating the s-th gradient is denoted by Ti(t, s). We modeled the Ti(t, s) as independent of each other and each Ti(t, s) is drawn according to the normal distribution N (µj , σ2j ) if worker i is in group j ∈ [5]. If Ti(t, s) < 0, then there is no pause and the worker starts calculating the next gradient immediately. Groups with larger µj model worse stragglers and larger σ2j models more variance in that straggler’s delay. In AMB, if the remaining time to compute gradients is less than the sampled Ti(t, s), then the duration of the pause is the remaining time. In other words, the node will not calculate any further gradients in that epoch but will pause till the end of the compute phase before proceeding to consensus rounds. In our experiment, we chose (µ1, µ2, µ3, µ4, µ5) = (5, 10, 20, 35, 55) and σ2j = j
2. In the FMB experiment, each worker calculated 10 gradients leading to a fixed minibatch size b = 500 while in AMB each worker was given a fixed compute time, T = 115 msec. which resulted in an empirical average minibatch size b ≈ 504 across all epochs. Figures 8a and 8b respectively depict the histogram of the compute time (including the pauses) for FMB and the histogram of minibatch sizes for AMB obtained in our experiment. In each histogram, five distinct distributions can be discerned, each representing one of the five groups. Notice that the fastest group of nodes has the smallest average compute time (the leftmost spike in Figure 8a) and the largest average minibatch size (the rightmost distribution in Figure 8b).
In Figure 9, we compare the logistic regression performance of AMB with that of FMB for the MNIST data set. Note that AMB achieves its lowest cost in 2.45 sec while FMB achieves the same cost only at 12.7 sec. In other words, the convergence rate of AMB is more than five times faster than that of FMB.

title: ONLINE DISTRIBUTED OPTIMIZATION


summaries: This submission proposes a reinforcement learning framework based on human emotional reaction in the context of autonomous driving. This relies on defining a reward function as the convex combination of an extrinsic (goal oriented) reward, and an intrinsic reward. This later reward is learnt from experiments with humans performing the task in a virtual environment, for which emotional response is quantified as blood volume pulse wave (BVP). The authors show that including this intrinsic reward lead to a better performance of a deep Q networks, with respect to using the extrinsic reward only.

summaries: Starting from the hypothesis that humans have evolved basic autonomic visceral responses that influence decision making in a meaningful way and that these are at work in driving a car, the authors propose to use such signals within the RL framework. This is accomplished by augmenting the RL reward function with a model learned directly from human nervous system responses. This leads to a

abstractText: As people learn to navigate the world, autonomic nervous system (e.g., “fight or flight”) responses provide intrinsic feedback about the potential consequence of action choices (e.g., becoming nervous when close to a cliff edge or driving fast around a bend.) Physiological changes are correlated with these biological preparations to protect one-self from danger. We present a novel approach to reinforcement learning that leverages a task-independent intrinsic reward function trained on peripheral pulse measurements that are correlated with human autonomic nervous system responses. Our hypothesis is that such reward functions can circumvent the challenges associated with sparse and skewed rewards in reinforcement learning settings and can help improve sample efficiency. We test this in a simulated driving environment and show that it can increase the speed of learning and reduce the number of collisions during the learning stage.

authors: Allen John

title: Photoplethysmography and its application in clinical physiological measurement

venue: Physiological measurement,

authors:
Bandura
Albert
Walters
Richard H

title: Social learning theory, volume 1

venue: Prentice-hall Englewood Cliffs, NJ,

authors:
Chang
Kai-Wei
Krishnamurthy
Akshay
Agarwal
Alekh
Daumé III
Hal
Langford
John

title: Learning to search better than your teacher

venue: In Proceedings of the 32nd International Conference on International Conference on Machine Learning-Volume

authors: Chen Weixuan McDuff Daniel

title: Deepphys: Video-based physiological measurement using convolutional attention networks

venue: arXiv preprint arXiv:1805.07888,

authors:
Chentanez
Nuttapong
Barto
Andrew G
Singh
Satinder P

title: Intrinsically motivated reinforcement learning

venue: In Advances in neural information processing systems,

authors: Daumé Hal Langford John Marcu Daniel

title: Search-based structured prediction

venue: Machine learning,

authors:
Gross
James J

title: Emotion regulation: Affective, cognitive, and social consequences

authors:
Haber
Nick
Mrowca
Damian
Fei-Fei
Li
Yamins
Daniel L. K

title: Learning to play with intrinsicallymotivated self-aware agents

venue: arXiv preprint arXiv:1802.07442,

authors: Ho Jonathan Ermon Stefano

title: Generative adversarial imitation learning

venue: In Advances in Neural Information Processing Systems,

authors:
Jansen
Arthur SP
Van Nguyen
Xay
Karpitskiy
Vladimir
Mettenleiter
Thomas C
Loewy
Arthur D

title: Central command neurons of the sympathetic nervous system: basis of the fight-or-flight response

authors: Jaques Natasha Engel Jesse Ha David Bertsch Fred Picard Rosalind Eck Douglas

title: Learning via social awareness: improving sketch representations with facial feedback

venue: arXiv preprint arXiv:1802.04877,

authors:
L. Fredrickson
Barbara
Levenson
Robert W

title: Positive emotions speed recovery from the cardiovascular sequelae of negative emotions

venue: Cognition & emotion,

authors:
Lerner
Jennifer S
Li
Ye
Valdesolo
Piercarlo
Kassam
Karim S

title: Emotion and decision making

venue: Annual Review of Psychology,

authors: Lin Long-Ji

title: Self-improving reactive agents based on reinforcement learning, planning and teaching

authors:
Loewenstein
George
Lerner
Jennifer S

title: The role of affect in decision making

venue: Handbook of affective science,

authors:
McDuff
Daniel
Gontarek
Sarah
Picard
Rosalind W

title: Remote detection of photoplethysmographic systolic and diastolic peaks using a digital camera

venue: IEEE Transactions on Biomedical Engineering,

authors:
Ng
Andrew Y
Harada
Daishi
Russell
Stuart

title: Policy invariance under reward transformations: Theory and application to reward shaping

venue: In ICML,

authors:
Pathak
Deepak
Agrawal
Pulkit
Efros
Alexei A
Darrell
Trevor

title: Curiosity-driven exploration by self-supervised prediction

venue: In International Conference on Machine Learning,

authors:
Poh
Ming-Zher
McDuff
Daniel J
Picard
Rosalind W

title: Non-contact, automated cardiac pulse measurements using video imaging and blind source separation

venue: Optics express,

authors:
Ross
Stephane
Bagnell
J Andrew

title: Reinforcement and imitation learning via interactive no-regret learning

venue: arXiv preprint arXiv:1406.5979,

authors: Ross Stéphane Gordon Geoffrey Bagnell Drew

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

venue: In Proceedings of the fourteenth international conference on artificial intelligence and statistics,

authors: Russell Stuart

title: Learning agents for uncertain environments

venue: In Proceedings of the eleventh annual conference on Computational learning theory,

authors:
Scheirer
Jocelyn
Fernandez
Raul
Klein
Jonathan
Picard
Rosalind W

title: Frustrating the user on purpose: a step toward building an affective computer

venue: Interacting with computers,

authors: Shah Shital Dey Debadeepta Lovett Chris Kapoor Ashish

title: Airsim: High-fidelity visual and physical simulation for autonomous vehicles

venue: In Field and Service Robotics,

authors:
Srivastava
Nitish
Hinton
Geoffrey E
Krizhevsky
Alex
Sutskever
Ilya
Salakhutdinov
Ruslan

title: Dropout: a simple way to prevent neural networks from overfitting

venue: Journal of machine learning research,

authors:
Wilson
Gillian M
Sasse
M Angela

title: Do users always know what’s good for them? utilising physiological responses to assess media quality

venue: In People and computers XIV—Usability or else!,

authors: Zheng Zeyu Oh Junhyuk Singh Satinder

title: On learning intrinsic rewards for policy gradient methods

venue: arXiv preprint arXiv:1804.06459,

heading: 1 INTRODUCTION

text:
The human autonomic nervous system (ANS) is composed of two branches. One of these, the sympathetic nervous system (SNS), is “hard-wired” to respond to potentially dangerous situations often reducing, or by-passing, the need for conscious processing. The ability to make rapid decisions and respond to immediate threats is one way of protecting oneself from danger. Whether one is in the African savanna or driving in Boston traffic.
The SNS regulates a range of visceral functions from the cardiovascular system to the adrenal system (Jansen et al., 1995). The anticipatory response in humans to a threatening situation is for the heart rate to increase, heart rate variability to decrease, blood to be diverted from the extremities and the sweat glands to dilate. This is the body’s “fight or flight” response.
While the primary role of these anticipatory responses is to help one prepare for action, they also play a part in our appraisal of a situation. The combination of sensory inputs, physiological responses and cognitive evaluation form emotions that influence how humans learn, plan and make decisions (Loewenstein & Lerner, 2003). Intrinsic motivation refers to being moved to act based on the way it makes one feel. For example, it is generally undesirable to be in a situation that causes fear and thus we might choose to take actions that help avoid these types of contexts in future. This is contrasted with extrinsic motivation that involves explicit goals (Chentanez et al., 2005).
Driving is an everyday example of a task in which we commonly rely on both intrinsic and extrinsic motivations and experience significant physiological changes. When traveling in a car at highspeed one may experience a heightened state of arousal. This automatic response is correlated with the body’s reaction to the greater threats posed by the situation (e.g., the need to adjust steering more rapidly to avoid a pedestrian that might step into the road). Visceral responses are likely to preempt accidents or other events (e.g., a person will become nervous before losing control and hitting someone). Therefore, these signals potentially offer an advantage as a reward mechanism compared to extrinsic rewards based on events that occur in the environment, such as a collision. This paper provides a reinforcement learning (RL) framework that incorporates reward functions for achieving task-specific goals and also minimizes a cost trained on physiological responses to
the environment that are correlated with stress. We ask if such a reward function with extrinsic and intrinsic components is useful in a reinforcement learning setting. We test our approach by training a model on real visceral human responses in a driving task.
The key challenges of applying RL in the real-world include the amount of training data required and the high-cost associated with failure cases. For example, when using RL in autonomous driving, rewards are often sparse and skewed. Furthermore, bad actions can lead to states that are both catastrophic and expensive to recover from. While much of the work in RL focuses on mechanisms that are task or goal dependent, it is clear that humans also consider the feedback from the body’s nervous system for action selection. For example, increased arousal can help signal imminent danger or failure to achieve a goal. Such mechanisms in an RL agent could help reduce the sample complexity as the rewards are continually available and could signal success or failure before the end of the episode. Furthermore, these visceral signals provide a warning mechanism that in turn could lead to safer explorations.
Our work is most closely related to that in intrinsically motivated learning (Chentanez et al., 2005; Zheng et al., 2018; Haber et al., 2018; Pathak et al., 2017) that uses a combination of intrinsic and extrinsic rewards and shows benefits compared to using extrinsic rewards alone. The key distinction in our work is that we specifically aim to build intrinsic reward mechanisms that are visceral and trained on signals correlated with human affective responses. Our approach could also be considered a form of imitation learning (Ross et al., 2011; Ross & Bagnell, 2014; Ho & Ermon, 2016; Chang et al., 2015) as we use the signal from a human expert for training. However, a difference is that our signal is an implicit response from the driver versus an explicit instruction or action which might commonly be the case in imitation learning.
The structural credit assignment problem, or generalization problem, aims to address the challenge posed by large parameter spaces in RL and the need to give the agent the ability to guess, or have some intuition about new situations based on experience (Lin, 1992). A significant advantage of our proposed method is the reduced sparsity of the reward signal. This makes learning more practical in a large parameter space. We conduct experiments to provide empirical evidence that this can help reduce the number of epochs required in learning. In a sense, the physiological response could be considered as an informed guess about new scenarios before the explicit outcome is known. The challenge with traditional search-based structured prediction is the assumptions that must be made
in the search algorithms that are required (Daumé et al., 2009). By training a classifier using a loss based on the human physiological response this problem can potentially be simplified.
The core contributions of this paper are to: (1) present a novel approach to learning in which the reward function is augmented with a model learned directly from human nervous system responses, (2) show how this model can be incorporated into a reinforcement learning paradigm and (3) report the results of experiments that show the model can improve both safety (reducing the number of mistakes) and efficiency (reducing the sample complexity) of learning.
In summary, we argue that a function trained on physiological responses could be used as an intrinsic reward or value function for artificially intelligent systems, or perhaps more aptly artificially emotionally intelligent systems. We hypothesize that incorporating intrinsic rewards with extrinsic rewards in an RL framework (as shown in Fig 1) will both improve learning efficiency as well as reduce catastrophic failure cases that occur during the training.

heading: 2 BACKGROUND

heading: 2.1 SYMPATHETIC NERVOUS SYSTEM

text: The SNS is activated globally in response to fear and threats. Typically, when threats in an environment are associated with a “fight of flight" response the result is an increase in heart rate and perspiration and release of adrenaline and cortisol into the circulatory system. These physiological changes act to help us physically avoid danger but also play a role in our appraisal of emotions and ultimately our decision-making. A large volume of research has found that purely rational decision-making is sub-optimal (Lerner et al., 2015). This research could be interpreted as indicating that intrinsic rewards (e.g., physiological responses and the appraisal of an emotion) serve a valuable purpose in decision-making. Thus, automatic responses both help people act quickly and in some cases help them make better decisions. While these automatic responses can be prone to mistakes, they are vital for keeping us safe. Logical evaluation of a situation and the threat it presents is also important. Ultimately, a combination of intrinsic emotional rewards and extrinsic rational rewards, based on the goals one has, is likely to lead to optimal results.

heading: 2.2 REINFORCEMENT LEARNING

text:
We consider the standard RL framework, where an agent interacts with the environment (described by a set of states S), through a set of actions (A). An action at at a time-step t leads to a distribution over the possible future state p(st+1|st, at), and a reward r : S × A → R. In addition, we start with a distribution of initial states p(s0) and the goal of the agent is to maximize the discounted sum of future rewards: Rt = ∑∞ i=t γ
i−tri, where γ is the discount factor. Algorithms such as Deep Q-Networks (DQN) learn a Neural-Network representation of a deterministic policy π : S → A that approximates an optimal Q-function: Q∗(s, a) = Es′∼p(·|s,a)[r(s, a) + γmaxa′∈AQ∗(s′, a′)].
The application of RL techniques to real-world scenarios, such as autonomous driving, is challenging due to the high sample complexity of the methods. High-sample complexity arises due to the creditassignment problem: it is difficult to identify which specific action from a sequence was responsible for a success or failure. This issue is further exacerbated in scenarios where the rewards are sparse. Reward shaping (Ng et al., 1999; Russell, 1998) is one way to deal with the sample complexity problem, in which heuristics are used to boost the likelihood of determining the responsible action.
We contrast sparse episodic reward signals in RL agents with physiological responses in humans. We conject that the sympathetic nervous system (SNS) responses for a driver are as informative and useful, and provide a more continuous form of feedback. An example of one such SNS response is the volumetric change in blood in the periphery of skin, controlled in part through vasomodulation. We propose to use a reward signal that is trained on a physiological signal that captures sympathetic nervous system activity. The key insight being that physiological responses in humans indicate adverse and risky situations much before the actual end-of-episode event (e.g. an accident) and even if the event never occurs. By utilizing such a reward function, not only is the system able to get a more continuous and dense reward but it also allows us to reason about the credit assignment problem. This is due to the fact that an SNS response is often tied causally to the set of actions responsible for the eventual success or failure of the episode.
Our work is related, in spirit, to a recent study that used facial expressions as implicit feedback to help train a machine learning systems for image generation (Jaques et al., 2018). The model produced sketches that led to significantly more positive facial expressions when trained with input of smile responses from an independent group. However, this work was based on the idea of Social Learning Theory (Bandura & Walters, 1977) and that humans learn from observing the behaviors of others, rather than using their own nervous system response as a reward function.

heading: 3 THE PROPOSED FRAMEWORK

text:
Our proposal is to consider a reward function that has both an extrinsic component r and an intrinsic component r̃. The extrinsic component rewards behaviors that are task specific, whereas the intrinsic component specifically aims to predict a human physiological response to SNS activity and reward actions that lead to states that reduce stress and anxiety. The final reward r̂ then is a function that considers both the extrinsic as well as intrinsic components r̂ = f(r, r̃). Theoretically, the function f(·, ·) can be fairly complex and one possibility would be to parameterize it as a neural network. For simplicity, we consider linear combinations of the extrinsic and intrinsic rewards in this paper. Formally, lets consider an RL framework based on a DQN with reward r. We propose to use a modified reward r̂ that is a convex combination of the original reward r and a component that mirrors human physiological responses r̃:
r̂ = λr + (1− λ)r̃ (1)
Here λ is a weighting parameter that provides a trade-off between the desire for task completion (extrinsic motivation) and physiological response (intrinsic motivation). For example, in an autonomous driving scenario the task dependent reward r can be the velocity, while r̃ can correspond to physiological responses associated with safety. The goal of the system then is to complete the task while minimizing the physiological arousal response. The key challenge now is to build a computational model of the intrinsic reward r̃ given the state of the agent.
In the rest of the paper we focus on the autonomous driving scenario as a canonical example and discuss how we can model the appropriate physiological responses and utilize them effectively in this framework. One of the greatest challenges in building a predictive model of SNS responses is the collection of realistic ground truth data. In this work, we use high-fidelity simulations (Shah et al., 2018) to collect physiological responses of humans and then train a deep neural network to predict SNS responses that will ultimately be used during the reinforcement learning process. In particular, we rely on the photoplethysmographic (PPG) signal to capture the volumetric change in blood in the periphery of the skin (Allen, 2007). The blood volume pulse waveform envelope pinches when a person is startled, fearful or anxious, which is the result of the body diverting blood from the extremities to the vital organs and working muscles to prepare them for action, the “fight or flight” response. Use of this phenomenon in affective computing applications is well established and has been leveraged to capture emotional responses in marketing/media testing (Wilson & Sasse, 2000), computer tasks (Scheirer et al., 2002) and many other psychological studies (L. Fredrickson & Levenson, 1998; Gross, 2002). The peripheral pulse can be measured unobtrusively and even without contact (Poh et al., 2010; Chen & McDuff, 2018), making it a good candidate signal for scalable measurement. We leverage the pulse signal to capture aspects of the nervous system response and our core idea is to train an artificial network to mimic the pulse amplitude variations based on the visual input from the perspective of the driver.
To design a reward function based on the nervous system response of the driver in the simulated environment we collected a data set of physiological recordings and synchronized first person video frames from the car. Using this data we trained a convolutional neural network (CNN) to mimic the physiological response based on the input images. Fig 2 shows a section of the recorded blood volume pulse signal with pulse peaks highlighted, notice how the waveform envelope changes.
Reinforcement Learning Environments: We performed our experiments in AirSim (Shah et al., 2018) where we instantiated an autonomous car in a maze. The car was equipped with an RGB camera and the goal for the agent was to learn a policy that maps the camera input to a set of controls (discrete set of steering angles). The agent’s extrinsic reward can be based on various driving related tasks, such as keeping up the velocity, making progress towards a goal, traveling large distances, and can be penalized heavily for collisions. Fig 2 shows example frames captured from the environment. The maze consisted of walls and ramps and was designed to be non-trivial to navigate for the driver.
Intrinsic Reward Architecture: We used a CNN to predict the normalized pulse amplitude derived from the physiological response of the driver. The image frames from the camera sensor in the environment served as an input to the network. The input frames were downsampled to 84 × 84 pixels and converted to grayscale format. They were normalized by subtracting the mean pixel value (calculated on the training set). The network architecture is illustrated in Fig 3. A dense layer of 128 hidden units preceded the final layer that had linear activation units and a mean square error (MSE) loss, so the output formed a continuous signal from 0 to 1.
Training the Reward Network: We recruited four participants (2 male, 2 female) to drive a vehicle around the maze and to find the exit point. All participants were licensed drivers and had at least seven years driving experience. For each participant we collected approximately 20 minutes (∼24,000 frames at a resolution of 256 × 144 pixels and frame rate of 20 frames-per-second) of continuous
driving in the virtual environment (for a summary of the data see Table 1). In addition, the PPG signal was recorded from the index finger of the non-dominant hand using a Shimmer31 GSR+ with an optical pulse sensor. The signal was recorded at 51.6Hz. The physiological signals were synchronized with the frames from the virtual environment using the same computer clock. A standard custom peak detection algorithm (McDuff et al., 2014) was used to recover the systolic peaks from the pulse waveform. The amplitudes of the peaks were normalized, to a range 0 to 1, across the entire recording. Following the experiment the participants reported how stressful they found the task (Not at all, A little, A moderate amount, A lot, A great deal). The participants all reported experiencing some stress during the driving task. The frames and pulse amplitude measures were then used to train the CNN (details in the next section). The output of the resulting trained CNN (the visceral machine) was used as the reward (r̃ = CNN Output) in the proposed framework.

heading: 4 EXPERIMENTS AND RESULTS

text: We conducted experiments to answer: (1) if we can build a deep predictive model that estimates a peripheral physiological response associated with SNS activity and (2) if using such predicted responses leads to sample efficiency in the RL framework. We use DQN as a base level approach and build our proposed changes on top of it. We consider three different tasks in the domain of autonomous driving: (a) keeping the velocity high (r is instantaneous velocity), (b) traveling long straight-line distances from the origin (r is absolute distance from origin) without any mishaps and (c) driving towards a goal (r = 10 if the goal is achieved). While the velocity and distance task provides dense rewards, the goal directed task is an example where the rewards are sparse and episodic. Note that in all three cases we terminate the episode with a high negative reward (r = -10) if a collision happens.

heading: 4.1 HOW WELL CAN WE PREDICT BVP AMPLITUDE?

text:
We trained five models, one for each of the four participants independently and one for all the participants combined. In each case, the first 75% of frames from the experimental recordings were
1http://www.shimmersensing.com/
taken as training examples and the latter 25% as testing examples. The data in the training split was randomized and a batch size of 128 examples was used. Max pooling was inserted between layers 2 and 3, layers 4 and 5, and layers 7 and 8. To overcome overfitting, a dropout layer (Srivastava et al., 2014) was added after layer 7 with rate d1 = 0.5. The loss during training of the reward model was the mean squared error. Each model was trained for 50 epochs after which the training root mean squared error (RMSE) loss was under 0.1 for all models. The RMSE was then calculated on the independent test set and was between 0.10 and 0.19 for all participants (see Table 1). As a naive baseline the testing loss for a random prediction was 0.210 greater on average. In all cases the CNN model loss was significantly lower than the random prediction loss (based on unpaired T-Tests). Fig 4 illustrates how a trained CNN associates different rewards to various situations. Specifically, we show different examples of the predicted pulse amplitudes on an independent set of the frames from the simulated environment. A lower value indicates a higher stress response. Quantitatively and qualitatively these results show that we could predict the pulse amplitude and that pinching in the peripheral pulse wave, and increased SNS response, was associated with approaching (but not necessarily contacting) obstacles. The remaining results were calculated using the model from P1; however, similar data were obtained from the other models indicating that the performance generalized across participants.

heading: 4.2 DOES THE VISCERAL REWARD COMPONENT IMPROVE PERFORMANCE?

text:
We then used the trained CNN as the visceral reward component in a DQN framework and used various values of λ to control the relative weight when compared to the task dependent reward component. Fig 5 shows the mean extrinsic reward per episode as a function of training time. The plots are averaged over 10 different RL runs and we show plots for different values of λ. When λ = 1 that RL agent is executing vanilla DQN, whereas λ = 0 means that there is no extrinsic reward signal. For all three tasks, we observe that the learning rate improves significantly when λ is either non-zero or not equal to 1. The exact value of the optimal λ varies from task to task, due to the slightly different final reward structures in the different tasks. One of the main reasons is that the
rewards are non-sparse with the visceral reward component contributing effectively to the learning. Low values of λ promote a risk-averse behavior in the agent and higher values λ train an agent with better task-specific behavior, but require longer periods of training. It is the mid-range values of λ (e.g. 0.25) that lead to optimal behavior both in terms of the learning rate and the desire to accomplish the mission.

heading: 4.3 DOES THE VISCERAL REWARD COMPONENT HELP REDUCE COLLISIONS?

text: Fig 6 plots how the average length of an episode changes with training time for different values of λ. Note that we consider an episode terminated when the agent experiences a collision, so the length of the episode is a surrogate measure of how cautious an agent is. We observed that a low value of λ leads to longer episodes sooner while high values do not lead to much improvement overall. Essentially, a low value of λ leads to risk aversion without having the desire to accomplish the task. This results in a behavior where the agent is happy to make minimal movements while staying safe. Fig 6 (Distance) shows that the average length of the episodes does not increase with the number of episodes. This is because with increasing numbers of episodes the car travels further but also faster. These two factors cancel one another out resulting in episodes with similar lengths (durations).

heading: 4.4 WHAT IS THE EFFECT OF A DECAYING VISCERAL REWARD?

text:
What happens if we introduce a time varying intrinsic reward that decays over time? We also ran experiments with varying λ:
λ = 1− 1 NEpisode
(2)
Where, NEpisode is the current episode number. As before, the reward was calculated as in Eqn. 1. Therefore, during the first episode λ is equal to zero and the reward is composed entirely of the intrinsic component. As the number of episodes increases the contribution of the intrinsic reward decreases. By episode 95 the intrinsic reward contributes to less than 2% of the total reward. Fig 7 plots the average velocity (left) and average length (right) per episode as the system evolves over time. The blue lines show the performance with a time decaying contribution from the intrinsic reward. These are compared with the best λ (= 0.25) (red lines) from the previous velocity experiments (see Figs 5 and 6). The episode length is quite superior with the time decaying intrinsic reward. This is because we are directly optimizing for safety initially and the agent quickly learns not to crash. This highlights the value of the intrinsic reward in increasing the safety of the vehicle and extending the length of episodes, especially initially, when the vehicle has little knowledge of how to behave.
Figure 8: Comparison of the CNN based intrinsic reward with a reward shaping mechanism. The plots are (left) average extrinsic reward per episode and (right) length of episode as the system evolves and show the advantages of the CNN based
approach in both cases. Number of Episodes 30 50 70 90 110 130 150
A ve ra ge V el oc ity 2.3 2.4 2.5 2.6 2.7
2.8 Velocity
CNN with 6 = 0.25 Heuristic with 6 = 0.25
Number of Episodes 30 50 70 90 110 130 150
A ve
ra ge
L en
gt h
of E
pi so de 20 22 24 26 28 30
32
34 Velocity
CNN with 6 = 0.25 Heuristic with 6 = 0.25

heading: 4.5 HOW DOES THE PERFORMANCE COMPARE TO REWARD SHAPING?

text: Something we question is, is the CNN predicting the SNS responses doing more than predicting distances to the wall and if there are ways in which the original reward can be shaped to include that information? We did RL experiments where we compared the proposed architecture (λ = 0.25) with an agent that replaced the intrinsic reward component with the reward 1− exp[−|distance to wall|]. Note that such distance measures are often available through sensors (such as sonar, radar etc.); however, given the luxury of the simulation we chose to use the exact distance for simplicity. Fig 8 shows both the average reward per episode as well as average length per episode, for the velocity task, as a function of training time. We observed that the agent that had used the CNN for the intrinsic reward component performs better than the heuristic. We believe that the trained CNN is far richer than the simple distance-based measure and is able to capture the context around the task of driving the car in confined spaces (e.g., avoiding turning at high speeds and rolling the car).

heading: 5 CONCLUSION AND FUTURE WORK

text:
Heightened arousal is an key part of the “fight or flight” response we experience when faced with risks to our safety. We have presented a novel reinforcement learning paradigm using an intrinsic reward function trained on peripheral physiological responses and extrinsic rewards based on mission goals. First, we trained a neural architecture to predict a driver’s peripheral blood flow modulation based on the first-person video from the vehicle. This architecture acted as the reward in our reinforcement learning step. A major advantage of training a reward on a signal correlated with the sympathetic nervous system responses is that the rewards are non-sparse - the negative reward starts to show up much before the car collides. This leads to efficiency in training and with proper design can lead to policies that are also aligned with the desired mission. While emotions are important for decision-making (Lerner et al., 2015), they can also detrimentally effect decisions in certain contexts. Future work will consider how to balance intrinsic and extrinsic rewards and include extensions to representations that include multiple intrinsic drives (such as hunger, fear and pain).
We must emphasize that in this work we were not attempting to mimic biological processes or model them explicitly. We were using a prediction of the peripheral blood volume pulse as an indicator of situations that are correlated with high arousal.

title: REINFORCEMENT LEARNING WITH INTRINSIC PHYSIOLOGICAL REWARDS