summaries: The authors study SGD algorithms for problems where obtaining unbiased gradients is potentially computationally expensive. In such cases while obtaining, unbiased gradients is expensive, it might be possible to establish consistent estimators of the gradient. The authors then establish that SGD algorithm when run with consistent gradient estimators (but not necessarily unbiased) have similar convergence properties as SGD algorithms when run with unbiased gradient estimators.  The example problem class considered is the problem of learning embeddings for graph problems, where the task is to get embeddings for nodes. Such embeddings can be used to do node classification or solve any other downstream task that involves the nodes of the graph. For such graph problems learning embeddings requires us  to look at the neighbours of a node, neighbours-of-neighbours and so on, which means that in the worst case calculating gradient w.r.t. a single node can be of time complexity O(N).  Consistent gradient estimators have been proposed for such graph problems in the past but this paper establishes theoretical properties of SGD with such estimators.   The paper studies stochastic optimization with consistent (may not be unbiased) estimators. This problem is well-motivated through the example of learning graph representations where consistent estimators are easier to obtain than unbiased one. Under the assumption that the estimate converges to the consistent gradient exponentially fast w.r.t. the sample size, the authors give convergence rates for convex, strongly-convex and non-convex optimization. The authors validate their theory through synthetic experiments.
abstractText: Stochastic gradient descent (SGD), which dates back to the 1950s, is one of the most popular and effective approaches for performing stochastic optimization. Research on SGD resurged recently in machine learning for optimizing convex loss functions and training nonconvex deep neural networks. The theory assumes that one can easily compute an unbiased gradient estimator, which is usually the case due to the sample average nature of empirical risk minimization. There exist, however, many scenarios (e.g., graphs) where an unbiased estimator may be as expensive to compute as the full gradient because training examples are interconnected. Recently, Chen et al. (2018) proposed using a consistent gradient estimator as an economic alternative. Encouraged by empirical success, we show, in a general setting, that consistent estimators result in the same convergence behavior as do unbiased ones. Our analysis covers strongly convex, convex, and nonconvex objectives. We verify the results with illustrative experiments on synthetic and real-world data. This work opens several new research directions, including the development of more efficient SGD updates with consistent estimators and the design of efficient training algorithms for large-scale graphs.
references.authors: Léon Bottou Frank E. Curtis Jorge Nocedal
references.title: Optimization methods for large-scale machine learning
references.authors: Joan Bruna Wojciech Zaremba Arthur Szlam Yann LeCun
references.title: Spectral networks and locally connected networks on graphs
references.venue: In ICLR,
references.authors: Chris Burges Tal Shaked Erin Renshaw Ari Lazier Matt Deeds Nicole Hamilton Greg Hullender
references.title: Learning to rank using gradient descent
references.venue: In ICML,
references.authors: Christopher J. Burges Robert Ragno Quoc V. Le
references.title: Learning to rank with nonsmooth cost functions
references.venue: In NIPS,
references.authors: Christopher J.C. Burges
references.title: From RankNet to LambdaRank to LambdaMART: An overview
references.venue: Technical Report MSR-TR-2010-82, Microsoft Research,
references.authors: Jie Chen Tengfei Ma Cao Xiao
references.title: FastGCN: Fast learning with graph convolutional networks via importance sampling
references.venue: In ICLR,
references.authors: Alexandre d’Aspremont
references.title: Smooth optimization with approximate gradient
references.venue: SIAM J. Optim.,
references.authors: Aaron Defazio Francis Bach Simon Lacoste-Julien
references.title: SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives
references.venue: In NIPS,
references.authors: Michaël Defferrard Xavier Bresson Pierre Vandergheynst
references.title: Convolutional neural networks on graphs with fast localized spectral filtering
references.venue: In NIPS,
references.authors: Olivier Devolder François Glineur Yurii Nesterov
references.title: First-order methods of smooth convex optimization with inexact oracle
references.venue: Mathematical Programming,
references.authors: Michael P. Friedlander Mark Schmidt
references.title: Hybrid deterministic-stochastic methods for data fitting
references.venue: SIAM J. Sci. Comput.,
references.authors: Rong Ge Furong Huang Chi Jin Yang Yuan
references.title: Escaping from saddle points — online stochastic gradient for tensor decomposition
references.venue: In COLT,
references.authors: Saeed Ghadimi Guanghui Lan
references.title: Stochastic first- and zeroth-order methods for nonconvex stochastic programming
references.venue: SIAM J. Optim.,
references.authors: Justin Gilmer Samuel S. Schoenholz Patrick F. Riley Oriol Vinyals George E. Dahl
references.title: Neural message passing for quantum chemistry
references.authors: Xavier Glorot Yoshua Bengio
references.title: Understanding the difficulty of training deep feedforward neural networks
references.venue: In AISTATS,
references.authors: William L. Hamilton Rex Ying Jure Leskovec
references.title: Inductive representation learning on large graphs
references.venue: In NIPS,
references.authors: Tito Homem-de-Mello
references.title: On rates of convergence for stochastic optimization problems under nonindependent and identically distributed sampling
references.venue: SIAM J. Optim.,
references.authors: Rie Johnson Tong Zhang
references.title: Accelerating stochastic gradient descent using predictive variance reduction
references.venue: In NIPS,
references.authors: Diederik P. Kingma Jimmy Ba
references.title: Adam: A method for stochastic optimization
references.venue: In ICLR,
references.authors: Thomas N. Kipf Max Welling
references.title: Semi-supervised classification with graph convolutional networks
references.venue: In ICLR,
references.authors: Simon Lacoste-Julien Mark Schmidt Francis Bach
references.title: A simpler approach to obtaining anO(1/t) convergence rate for the projected stochastic subgradient method
references.authors: Yujia Li Daniel Tarlow Marc Brockschmidt Richard Zemel
references.title: Gated graph sequence neural networks
references.venue: In ICLR,
references.authors: Ji Liu
references.title: Stochastic gradient “descent
references.venue: algorithm. https://www.cs.rochester. edu/u/jliu/CSC-576/class-note-10.pdf,
references.authors: A. Nemirovski A. Juditsky G. Lan A. Shapiro
references.title: Robust stochastic approximation approach to stochastic programming
references.venue: SIAM J. Optim.,
references.authors: Sashank J. Reddi Ahmed Hefny Suvrit Sra Barnabas Poczos Alex Smola
references.title: Stochastic variance reduction for nonconvex optimization
references.venue: In ICML,
references.authors: Herbert Robbins Sutton Monro
references.title: A stochastic approximation method
references.venue: Ann. Math. Statist.,
references.authors: Mark Schmidt Nicolas L. Roux Francis R. Bach
references.title: Convergence rates of inexact proximalgradient methods for convex optimization
references.venue: In NIPS,
references.authors: Shai Shalev-Shwartz Shai Ben-David
references.title: Understanding Machine Learning: From Theory to Algorithms
references.authors: Petar Velic̆ković Guillem Cucurull Arantxa Casanova Adriana Romero Pietro Liò Yoshua Bengio
references.title: Graph attention networks
references.venue: In ICLR,
sections.heading: 1 INTRODUCTION
sections.text: Consider the standard setting of supervised learning. There exists a joint probability distribution P (x, y) of data x and associated label y and the task is to train a predictive model, parameterized by w, that minimizes the expected loss ` between the prediction and the ground truth y. Let us organize the random variables as ξ = (x, y) and use the notation `(w; ξ) for the loss. If ξi = (xi, yi), i = 1, . . . , n, are iid training examples drawn from P , then the objective function is either one of the following well-known forms:
  expected risk f(w) = E[`(w; ξ)]; empirical risk f(w) = 1
  n n∑ i=1 `(w; ξi). (1)
  Stochastic gradient descent (SGD), which dates back to the seminal work of Robbins & Monro (1951), has become the de-facto optimization method for solving these problems in machine learning. In SGD, the model parameter is updated until convergence with the rule1
  wk+1 = wk − γkgk, k = 1, 2, . . . , (2)
  where γk is a step size and gk is an unbiased estimator of the gradient∇f(wk). Compared with the full gradient (as is used in deterministic gradient descent), an unbiased estimator involves only one or a few training examples ξi and is usually much more efficient to compute.
sections.heading: 1.1 LIMITATION OF UNBIASED GRADIENT AND REMEDY: CONSISTENT GRADIENT
sections.text: This scenario, however, does not cover all learning settings. A representative example that leads to costly computation of the unbiased gradient estimator ∇`(w, ξi) is graph nodes. Informally speaking, a graph node ξi needs to aggregate information from its neighbors. If information is aggregated
  1For introductory purpose we omit the projection operator for constrained problems. All analysis in this work covers projection.
  across neighborhoods, ξi must request information from its neighbors recursively, which results in inquiring a large portion of the graph. In this case, the sample loss ` for ξi involves not only ξi, but also all training examples within its multihop neighborhood. The worst case scenario is that computing ∇`(w, ξi) costs O(n) (e.g., for a complete graph or small-world graph), as opposed to O(1) in the usual learning setting because only the single example ξi is involved.
  In a recent work, Chen et al. (2018) proposed a consistent gradient estimator as an economic alternative to an unbiased one for training graph convolutional neural networks, offering substantial evidence of empirical success. A summary of the derivation is presented in Section 2. The subject of this paper is to provide a thorough analysis of the convergence behavior of SGD when gk in (2) is a consistent estimator of ∇f(wk). We show that using this estimator results in the same convergence behavior as does using unbiased ones. Definition 1. An estimator gN of h, where N denotes the sample size, is consistent if gN converges to h in probability: plimN→∞ g N = h. That is, for any > 0, limN→∞ Pr(‖gN − h‖ > ) = 0.
sections.heading: 1.2 DISTINCTIONS BETWEEN UNBIASEDNESS AND CONSISTENCY
sections.text: It is important to note that unbiased and consistent estimators are not subsuming concepts (one does not imply the other), even in the limit. This distinction renders the departure of our convergence results, in the form of probabilistic bounds on the error, from the usual SGD results that bound instead the expectation of the error.
  In what follows, we present examples to illustrate the distinctions between unbiasedness and consistency. To this end, we introduce asymptotic unbiasedness, which captures the idea that the bias of an estimator may vanish in the limit. Definition 2. An estimator gN of h, where N denotes the sample size, is asymptotically unbiased if E[gN ]→ h.
  An estimator can be (asymptotically) unbiased but inconsistent. Consider estimating the mean h = µ of the normal distribution N(µ, σ2) by using N independent samples X1, . . . , XN . The estimator gN = X1 (i.e., always useX1 regardless of the sample sizeN ) is clearly unbiased because E[X1] = µ; but it is inconsistent because the distribution of X1 does not concentrate around µ. Moreover, the estimator is trivially asymptotically unbiased.
  An estimator can be consistent but biased. Consider estimating the variance h = σ2 of the normal distribution N(µ, σ2) by using N independent samples X1, . . . , XN . The estimator gN =∑N i=1(Xi − X)2/N , where X = ∑N i=1Xi/N , has mean σ
  2(N − 1)/N and variance 2σ4(N − 1)/N2. Hence, it is consistent owing to a straightforward invocation of the Chebyshev inequality, by noting that the mean approaches σ2 and the variance approaches zero. However, the estimator admits a nonzero bias σ2/N for any finite N .
  An estimator can be consistent but biased even asymptotically. In the preceding example, the bias σ2/N approaches zero and hence the estimator is asymptotically unbiased. Other examples exist for the estimator to be biased even asymptotically. Consider estimating the quantity h = 0 with an estimator gN that takes the value 0 with probability (N − 1)/N and the value N with probability 1/N . Then, the probability that gN departs from zero approaches zero and hence it is consistent. However, E[gN ] = 1 and thus the bias does not vanish as N increases.
sections.heading: 1.3 CONTRIBUTIONS OF THIS WORK
sections.text: To the best of our knowledge, this is the first work that studies the convergence behavior of SGD with consistent gradient estimators, which result from a real-world graph learning scenario that will be elaborated in the next section. With the emergence of graph deep learning models (Bruna et al., 2014; Defferrard et al., 2016; Li et al., 2016; Kipf & Welling, 2017; Hamilton et al., 2017; Gilmer et al., 2017; Velic̆ković et al., 2018), the scalability bottleneck caused by the expensive computation of the sample gradient becomes a pressing challenge for training (as well as inference) with large graphs. We believe that this work underpins the theoretical foundation of the efficient training of a series of graph neural networks. The theory reassures practitioners of doubts on the convergence of their optimization solvers.
  Encouragingly, consistent estimators result in a similar convergence behavior as do unbiased ones. The results obtained here, including the proof strategy, offer convenience for further in-depth analysis under the same problem setting. This work opens the opportunity of improving the analysis, in a manner similar to the proliferation of SGD work, from the angles of relaxing assumptions, refining convergence rates, and designing acceleration techniques.
  We again emphasize that unbiasedness and consistency are two separate concepts; neither subsumes the other. One may trace that we intend to write the error bounds for consistent gradient estimators in a manner similar to the expectation bounds in standard SGD results. Such a resemblance (e.g., in convergence rates) consolidates the foundation of stochastic optimization built so far.
sections.heading: 2 MOTIVATING APPLICATION: REPRESENTATION LEARNING OF GRAPH NODES
sections.text: For a motivating application, consider the graph convolutional network model, GCN (Kipf & Welling, 2017), that learns embedding representations of graph nodes. The l-th layer of the network is compactly written as H(l+1) = σ(ÂH(l)W (l)), (3) where Â is a normalization of the graph adjacency matrix, W (l) is a parameter matrix, and σ is a nonlinear activation function. The matrix H(l) contains for each row the embedding of a graph node input to the l-th layer, and similarly for the output matrix H(l+1). With L layers, the network transforms an initial feature input matrix H(0) to the output embedding matrix H(L). For a node v, the embedding H(L)(v, :) may be fed into a classifier for prediction.
  Clearly, in order to compute the gradient of the loss for v, one needs the corresponding row ofH(L), the rows ofH(L−1) corresponding to the neighbors of v, and further recursive neighbors across each layer, all the way down to H(0). The computational cost of the unbiased gradient estimator is rather high. In the worst case, all rows of H(0) are involved.
  To resolve the inefficiency, Chen et al. (2018) proposed an alternative gradient estimator that is biased but consistent. The simple and effective idea is to sample a constant number of nodes in each layer to restrict the size of the multihop neighborhood. For notational clarity, the approach may be easier to explain for a network with a single layer; theoretical results for more layers straightforwardly follow that of Theorem 1 below, through induction.
  The approach generalizes the setting from a finite graph to an infinite graph, such that the matrix expression (3) becomes an integral transform. In particular, the input feature vector H(0)(u, :) for a node u is generalized to a feature function X(u), and the output embedding vector H(1)(v, :) for a node v is generalized to an embedding function Z(v), where the random variables u and v in two sides of the layer reside in different probability spaces, with probability measures P (u) and P (v), respectively. Furthermore, the matrix Â is generalized into a bivariate kernel Â(v, u) and the loss ` is written as a function of the output Z(v). Then, (1) and (3) become
  f = Ev∼P (v)[`(Z(v))] with Z(v) = σ (∫ Â(v, u)X(u)W dP (u) ) . (4)
  Such a functional generalization facilitates sampling on all network layers for defining a gradient estimator. In particular, defining B(v) = ∫ Â(v, u)X(u) dP (u), simple calculation reveals that the gradient with respect to the parameter matrix W is
  G := ∇f = ∫ q(B(v)) dP (v), where q(B) = BT∇h(BW ) and h = ` ◦ σ.
  Then, one may use t iid samples of u in the input and s iid samples of v in the output to define an estimator of G:
  Gst := 1
  s s∑ i=1 q(Bt(vi)), vi ∼ P (v), with Bt(v) := 1 t t∑ j=1 Â(v, uj)X(uj), uj ∼ P (u).
  The gradient estimator Gst so defined is consistent; see a proof in the supplementary material. Theorem 1. If q is continuous and f is finite, then plims,t→∞Gst = G.
sections.heading: 3 SETTING AND NOTATIONS
sections.text: We now settle the notations for SGD. We are interested in the (constrained) optimization problem
  min w∈S f(w),
  where the feasible region S is convex. This setting includes the unconstrained case S = Rd. We assume that the objective function f : Rd → R is subdifferentiable; and use ∂f(w) to denote the subdifferential at w. When it is necessary to refer to an element of this set, we use the notation h. If f is differentiable, then clearly, ∂f(w) = {∇f(w)}. The standard update rule for SGD is wk+1 = ΠS(wk − γkgk), where gk is the negative search direction at step k, γk is the step size, and ΠS is the projection onto the feasible region: ΠS(w) := argminu∈S ‖w − u‖. For unconstrained problems, the projection is clearly omitted: wk+1 = wk − γkgk.
  Denote byw∗ the global minimum. We assume thatw∗ is an interior point of S, so that the subdifferential of f atw∗ contains zero. For differentiable f , this assumption simply means that∇f(w∗) = 0. Typical convergence results are concerned with how fast the iterate wk approaches w∗, or the function value f(wk) approaches f(w∗). Sometimes, the analysis is made convenient through a convexity assumption on f , such that the average of historical function values f(wi), i = 1, . . . , k, is lowered bounded by f(wk), with wk being the cumulative moving average wk = 1k ∑k i=1 wi.
  The following definitions are frequently referenced. Definition 3. We say that f is l-strongly convex (with l > 0) if for all w, u ∈ Rd and hu ∈ ∂f(u),
  f(w)− f(u) ≥ 〈hu, w − u〉+ l
  2 ‖w − u‖2.
  Definition 4. We say that f is L-smooth (with L > 0) if it is differentiable and for all w, u ∈ Rd, ‖∇f(w)−∇f(u)‖ ≤ L‖w − u‖.
sections.heading: 4 CONVERGENCE RESULTS
sections.text: Recall that an estimator gN of h is consistent if for any > 0,
  lim N→∞
  Pr(‖gN − h‖ > ) = 0. (5)
  In our setting, h corresponds to an element of the subdifferential at step k; i.e., hk ∈ ∂f(wk), gN corresponds to the negative search direction gk, andN corresponds to the sample sizeNk. That gNkk converges to hk in probability does not imply that gNkk is unbiased. Hence, a natural question asks what convergence guarantees exist when using gNkk as the gradient estimator. This section answers that question.
  First, note that the sample size Nk is associated with not only gNkk , but also the new iterate w Nk k+1. We omit the superscript Nk in these vectors to improve readability.
  Similar to the analysis of standard SGD, which is built on the premise of the unbiasedness of gk and the boundedness of the gradient, in the following subsection we elaborate the parallel assumptions in this work. They are stated only once and will not be repeated in the theorems that follow, to avoid verbosity.
sections.heading: 4.1 ASSUMPTIONS
sections.text: The convergence (5) of the estimator does not characterize how fast it approaches the truth. One common assumption is that the probability in (5) decreases exponentially with respect to the sample size. That is, we assume that there exists a step-dependent constant Ck > 0 and a nonnegative function τ(δ) on the positive axis such that
  Pr ( ‖gk − hk‖ ≥ δ‖hk‖ ∣∣∣ g1, . . . , gk−1) ≤ Cke−Nkτ(δ) (6)
  for all k > 1 and δ > 0. A similar assumption is adopted by Homem-de-Mello (2008) that studied stochastic optimization through sample average approximation. In this case, the exponential tail occurs when the individual moment generating functions exist, a simple application of the Chernoff bound. For the motivating application GCN, the tail is indeed exponential as evidenced by Figure 3.
  Note the conditioning on the history g1, . . . , gk−1 in (6). The reason is that hk (i.e., the gradient ∇f(wk) if f is differentiable) is by itself a random variable dependent on history. In fact, a more rigorous notation for the history should be filtration, but we omit the introduction of unnecessary additional definitions here, as using the notion g1, . . . , gk−1 is sufficiently clear.
  Assumption 1. The gradient estimator gk is consistent and obeys (6).
  The use of a tail bound assumption, such as (6), is to reverse-engineer the required sample size given the desired probability that some event happens. In this particular case, consider the setting where T SGD updates are run. For any δ ∈ (0, 1), define the event
  Eδ = { ‖g1 − h1‖ ≤ δ‖h1‖ and ‖g2 − h2‖ ≤ δ‖h2‖ and . . . and ‖gT − hT ‖ ≤ δ‖hT ‖ } .
  Given (6) and any ∈ (0, 1), one easily calculates that if the sample sizes satisfy
  Nk ≥ τ(δ)−1 log(TCk/ ), (7)
  for all k, then,
  Pr(Eδ) ≥ T∏ k=1 (1− Cke−Nkτ(δ)) ≥ T∏ k=1 (1− /T ) ≥ 1− .
  Hence, all results in this section are established under the event Eδ that occurs with probability at least 1− , a sufficient condition of which is (7). The sole purpose of the tail bound assumption (6) is to establish the relation between the required sample sizes (as a function of δ and ) and the event Eδ , on which convergence results in this work are based. One may replace the assumption by using other tail bounds as appropriate. It is out of the scope of this work to quantify the rate of convergence of the gradient estimator for a particular use case. For GCN, the exponential tail that agrees with (6) is illustrated in Section 5.4.
  Additionally, parallel to the bounded-gradient condition for standard SGD analysis, we impose the following assumption.
  Assumption 2. There exists a finite G > 0 such that ‖h‖ ≤ G for all h ∈ ∂f(w) and w ∈ S.
sections.heading: 4.2 RESULTS
sections.text: Let us begin with the strongly convex case. For standard SGD with unbiased gradient estimators, ample results exist that indicateO(1/T ) convergence2 for the expected error, where T is the number of updates; see, e.g., (2.9)–(2.10) of Nemirovski et al. (2009) and Section 3.1 of Lacoste-Julien et al. (2012). We derive similar results for consistent gradient estimators, as stated in the following Theorem 2. Different from the unbiased case, it is the error, rather than the expected error, to be bounded. The tradeoff is the introduction of the relative gradient estimator error δ, which relates to the sample sizes as in (7) for guaranteeing satisfaction of the bound with high probability.
  Theorem 2. Let f be l-strongly convex with l ≤ G/‖w1 − w∗‖. Assume that T updates are run, with diminishing step size γk = [(l − δ)k]−1 for k = 1, 2, . . . , T , where δ = ρ/T and ρ < l is an arbitrary constant independent of T . Then, for any such ρ, any ∈ (0, 1), and sufficiently large sample sizes satisfying (7), with probability at least 1− , we have
  ‖wT − w∗‖2 ≤ G2
  T
  [ (1 + ρ/T )2 + ρ(l − ρ/T )
  (l − ρ/T )2
  ] , (8)
  and
  f(wT )− f(w∗) ≤ G2
  2T
  [ ρ+ (1 + ρ/T )2
  l − ρ/T (1 + log T )
  ] . (9)
  2Ignoring the logarithmic factor, if any.
  Note the assumption on l in Theorem 2. This assumption is mild since if f is l-strongly convex, it is also l′-strongly convex for all l′ < l. The assumption is needed in the induction proof of (8) when establishing the base case ‖w1−w∗‖. One may remove this assumption at the cost of a cumbersome right-hand side of (8), over which we favor a neater expression in the current form.
  With an additional smoothness assumption, we may eliminate the logarithmic factor in (9) and obtain a result for the iterate wT rather than the running average wT . The result is a straightforward consequence of (8). Theorem 3. Under the conditions of Theorem 2, additionally let f be L-smooth. Then, for any ρ satisfying the conditions, any ∈ (0, 1), and sufficiently large sample sizes satisfying (7), with probability at least 1− , we have
  f(wT )− f(w∗) ≤ LG2
  2T
  [ (1 + ρ/T )2 + ρ(l − ρ/T )
  (l − ρ/T )2
  ] . (10)
  In addition to O(1/T ) convergence, it is also possible to establish linear convergence (however) to a non-vanishing right-hand side, as the following result indicates. To obtain such a result, we use a constant step size. Bottou et al. (2016) show a similar result for the function value with an additional smoothness assumption in a different setting; we give one for the iterate error without the smoothness assumption using consistent gradients. Theorem 4. Under the conditions of Theorem 2, except that one sets a constant step size γk = c with 0 < c < (2l− δ)−1 for all k, for any ρ satisfying the conditions, any ∈ (0, 1), and sufficiently large sample sizes satisfying (7), with probability at least 1− , we have
  ‖wT − w∗‖2 ≤ (1− 2cl + cδ)T−1‖w1 − w∗‖2 + δ + c(1 + δ)2
  2l − δ G2. (11)
  Compare (11) with (8) in Theorem 2. The former indicates that in the limit, the squared iterate error is upper bounded by a positive term proportional to G2; the remaining part of this upper bound decreases at a linear speed. The latter, on the other hand, indicates that the squared iterate error in fact will vanish, although it does so at a sublinear speed O(1/T ). For convex (but not strongly convex) f , typically O(1/ √ T ) convergence is asserted for unbiased gradient estimators; see., e.g., Theorem 2 of Liu (2015). These results are often derived based on an additional assumption that the feasible region is compact. Such an assumption is not restrictive, because even if the problem is unconstrained, one can always confine the search to a bounded region (e.g., an Euclidean ball). Under this condition, we obtain a similar result for consistent gradient estimators. Theorem 5. Let f be convex and the feasible region S have finite diameter D > 0; that is, supw,u∈S ‖w− u‖ = D. Assume that T updates are run, with diminishing step size γk = c/ √ k for k = 1, 2, . . . , T and for some c > 0. Let δ = ρ/ √ T where ρ > 0 is an arbitrary constant independent of T . Then, for any such ρ, any ∈ (0, 1), and sufficiently large sample sizes satisfying (7), with probability at least 1− , we have
  f(wT )− f(w∗) ≤ 1
  2 √ T
  [( 1
  c + ρ
  ) D2 +G2 ( ρ+ c ( 1 +
  ρ√ T
  )2√ 1 + 1
  T
  )] . (12)
  One may obtain a result of the same convergence rate by using a constant step size. In the case of unbiased gradient estimators, see Theorem 14.8 of Shalev-Shwartz & Ben-David (2014). For such a result, one assumes that the step size is inversely proportional to √ T . Such choice of the step size is common and is also used in the next setting.
  For the general (nonconvex) case, convergence is typically gauged with the gradient norm. One again obtains O(1/ √ T ) convergence results for unbiased gradient estimators; see, e.g., Theorem 1 of Reddi et al. (2016) (which is a simplified consequence of the theory presented in Ghadimi & Lan (2013)). We derive a similar result for consistent gradient estimators. Theorem 6. Let f be L-smooth and S = Rd. Assume that T updates are run, with constant step size γk = Df/[(1 + δ)G √ T ] for k = 1, 2, . . . , T , where Df = [2(f(w1)− f(w∗))/L] 1 2 , and δ ∈ (0, 1)
  is an arbitrary constant. Then, for any such δ, any ∈ (0, 1), and sufficiently large sample sizes satisfying (7), with probability at least 1− , we have
  min k=1,...,T
  ‖∇f(wk)‖2 ≤ (1 + δ)LGDf
  (1− δ) √ T . (13)
sections.heading: 4.3 INTERPRETATION
sections.text: All the results in the preceding subsection assert convergence for SGD with the use of a consistent gradient estimator. As with the use of an unbiased one, the convergence for the strongly convex case is O(1/T ), or linear if one tolerates a non-vanishing upper bound, and the convex and nonconvex casesO(1/ √ T ). These theoretical results, however, are based on assumptions of the sample sizeNk and the step size γk that are practically challenging to verify. Hence, in a real-life machine learning setting, the sample size and the learning rate (the initial step size) are treated as hyperparameters to be tuned against a validation set.
  Nevertheless, these results establish a qualitative relationship between the sample size and the optimization error. Naturally, to maintain the same failure probability , the relative gradient estimator error δ decreases inversely with the sample size Nk. This intuition holds true in the tail bound condition (6) with (7), when τ(δ) is a monomial or a positive combination of monomials with different degrees. With this assumption, the larger is Nk, the smaller is δ (and also ρ, the auxiliary quantity defined in the theorems); hence, the smaller are the error bounds (8)–(13).
sections.heading: 4.4 REMARKS
sections.text: Theorem 4 presents a linear convergence result for the strongly convex case, with a non-vanishing right-hand side. In fact, it is possible to obtain a result with the same convergence rate but a vanishing right-hand side, if one is willing to additionally assume L-smoothness. The following theorem departs from the set of theorems in Section 4.2 on the assumption of the sufficient sample size Nk and the gradient error δ.
  Theorem 7. Let f be l-strongly convex and L-smooth with l < L. Assume that T updates are run with constant step size γk = 1/L for k = 1, 2, . . . , T . Let δk, k ≥ 1 be a sequence where limk→∞ δk+1/δk ≤ 1. Then, for any positive η < l/L, ∈ (0, 1), and sample sizes
  Nk ≥ τ(δk/‖hk‖)−1 log(TCk/ ) for k = 1, 2, . . . , T,
  with probability at least 1− , we have
  f(wT )− f(w∗) ≤ (1− l/L)T−1[f(w1)− f(w∗)] +O(ET ), (14)
  where ET = max{δ2T , (1− l/L+ η)T }.
  Here, δk is the step-dependent gradient error. If it decreases to zero, then so does ET . Theorem 7 is adapted from Friedlander & Schmidt (2012), who studied unbiased gradients as well as noisy gradients. We separate Theorem 7 from those in Section 4.2 only for the sake of presentation clarity. The spirit, however, remains the same. Namely, consistent estimators result in the same convergence behavior (i.e., rate) as do unbiased ones. All results require an assumption on sufficient sample size owing to the probabilistic convergence of the gradient estimator.
sections.heading: 5 NUMERICAL ILLUSTRATIONS
sections.text: In this section, we report several experiments to illustrate the convergence behavior of SGD by using consistent gradient estimators. We base the experiments on the training of the GCN model (Kipf & Welling, 2017) motivated earlier (cf. Section 2). The code repository will be revealed upon paper acceptance.
sections.heading: 5.1 DATA SETS
sections.text: We use three data sets for illustration, one synthetic and two real-world benchmarks.
  The purpose of a synthetic data set is to avoid the regularity in the sampling of training/validation/test examples. The data set, called “Mixture,” is a mixture of three overlapping Gaussians. The points are randomly connected, with a higher probability for those within the same component than the ones straddling across components. See the supplementary material for details of the construction. Because of the significant overlap, a classifier trained with independent data points unlikely predicts well the component label, but a graph-based method is more likely to be successful.
  Additionally, we use two benchmark data sets, Cora and Pubmed, often seen in the literature. These graphs are citation networks and the task is to predict the topics of the publications. We follow the split used in Chen et al. (2018). See the supplementary material for a summary of all data sets.
sections.heading: 5.2 (STRONGLY) CONVEX CASE
sections.text: The GCN model is hyperparameterized by the number of layers. Without any intermediate layer, the model can be considered a generalized linear model and thus the cross-entropy loss function is convex. Moreover, with the use of an L2 regularization, the loss becomes strongly convex. The predictive model reads P = softmax(ÂXW (0)), where X is the input feature matrix and P is the output probability matrix, both row-wise. One easily sees that the only difference between this model and logistic regression P = softmax(XW (0)) is the neighborhood aggregation ÂX .
  Standard batched training in SGD samples a batch (denoted by the index set I1) from the training set and evaluates the gradient of the loss of softmax(Â(I1, :)XW (0)). In the analyzed consistentgradient training, we additionally uniformly sample the input layer with another index set I0 and evaluate instead the gradient of the loss of softmax( n|I0| Â(I1, I0)X(I0, :)W (0)).
  Figure 1 shows the convergence curves as the iteration progresses. The plotted quantity is the overall loss on all training examples, rather than the batch loss for only the current batch. Hence, not surprisingly the curves are generally quite smooth. We compare standard SGD with the use of consistent gradient estimators, with varying sample size |I0|. Additionally, we compare with the Adam training algorithm (Kingma & Ba, 2015), which is a stochastic optimization approach predominantly used in practice for training deep neural networks.
  One sees that for all data sets, Adam converges faster than does standard SGD. Moreover, as the sample size increases, the loss curve with consistent gradients approaches that with an unbiased one (i.e., standard SGD). This phenomenon qualitatively agrees with the theoretical results; namely, larger sample size improves the error bound. Note that all curves in the same plot result from the same parameter initialization; and all SGD variants apply the same learning rate.
  It is important to note that the training loss is only a surrogate measure of the model performance; and often early termination of the optimization acts as a healthy regularization against over-fitting. In our setting, a small sample size may not satisfy the assumptions of the theoretical results, but it proves to be practically useful. In Table 1 (left), we report the test accuracy attained by different training algorithms at the epoch where validation accuracy peaks. One sees that Adam and standard SGD achieves similar accuracies, and that SGD with consistent gradient sometimes surpasses these accuracies. For Cora, a sample size 400 already yields an accuracy noticeably higher than do Adam and standard SGD.
sections.heading: 5.3 NONCONVEX CASE
sections.text: When GCN has intermediate layers, the loss function is generally nonconvex. A 2-layer GCN reads P = softmax(Â · ReLU(ÂXW (0)) ·W (1)), and a GCN with more layers is analogous. We repeat the experiments in the preceding subsection. The results are reported in Figure 2 and Table 1 (right). The observation of the loss curve follows the same as that in the convex case. Namely, Adam converges faster than does unbiased SGD; and the convergence curve with a consistent gradient approaches that with an unbiased one.
  On the other hand, compared with 1-layer GCN, 2-layer GCN yields substantially higher test accuracy for the data set Mixture, better accuracy for Cora, and very similar accuracy for Pubmed. Within each data set, the performances of different training algorithms are on par. In particular, a small sample size (e.g., 400) suffices for achieving results comparable to the state of the art (cf. Chen et al. (2018)).
sections.heading: 5.4 PROBABILITY CONVERGENCE
sections.text: The nature of a consistent estimator necessitates a characterization of the speed of probability convergence for building further results, such as the ones in this paper. The speed, however, depends on the neural network architecture and it is out of the scope of this work to quantify it for a particular use case. Nevertheless, for GCN we demonstrate empirical findings that agree with the exponential tail assumption (6). In Figure 3 (solid curves), we plot the tail probability as a function of the sample size N at different levels of estimator error δ, for the initial gradient step in 1-layer GCN. For each N , 10,000 random gradient estimates were simulated for estimating the probability. Because the probability is plotted in the logarithmic scale, the fact that the curves bend down indicates that the convergence may be faster than exponential.
  Additionally, the case of 2-layer GCN is demonstrated by the dashed curves in Figure 3. The curves tend to be straight lines in the limit, which indicates an exponential convergence.
sections.heading: 6 CONCLUDING REMARKS
sections.text: To the best of our knowledge, this is the first work that studies the convergence behavior of SGD with consistent gradient estimators, and one among few studies of first-order methods that employ biased (d’Aspremont, 2008; Schmidt et al., 2011) or noisy (Friedlander & Schmidt, 2012; Devolder et al., 2014; Ge et al., 2015) estimators. The motivation originates from learning with large graphs and the main message is that the convergence behavior is well-maintained with respect to the unbiased case. While we analyze the classic SGD update formula, this work points to several immediate extensions. One direction is the design of more efficient update formulas resembling the variance reduction technique for unbiased estimators (Johnson & Zhang, 2013; Defazio et al., 2014; Bottou et al., 2016). Another direction is the development of more computation- and memory-efficient training algorithms for neural networks for large graphs. GCN is only one member of a broad family of message passing neural networks (Gilmer et al., 2017) that suffer from the same limitation of neighborhood aggregation. Learning in these cases inevitably faces the costly computation of the sample gradient. Hence, a consistent estimator appears to be a promising alternative, whose construction is awaiting more innovative proposals.
  We are grateful to an anonymous reviewer who inspired us of an interesting use case (other than GCN). Learning to rank is a machine learning application that constructs ranking models for information retrieval systems. In representative methods such as RankNet (Burges et al., 2005) and subsequent improvements (Burges et al., 2007; Burges, 2010), si is the ranking function for document i and the learning amounts to minimizing the loss∑
  (i,j)
  sj − si + log(1 + esi−sj ),
  where the summation ranges over all pairs of documents such that i is ranked higher than j. The pairwise information may be organized as a graph and the loss function may be similarly generalized as a double integral analogous to (4). Because of nonlinearity, Monte Carlo sampling of each integral will result in a biased but consistent estimator. Therefore, a new training algorithm is to sample i and j separately (forming a consistent gradient) and apply SGD. The theory developed in this work offers guarantees of training convergence.
sections.heading: A PROOFS
sections.heading: A.1 LEMMAS
sections.text: Here are a few lemmas needed for the proofs in subsequent subsections. Lemma 8. Projection is nonexpanding, i.e.,
  ‖ΠS(w)−ΠS(u)‖ ≤ ‖w − u‖, ∀w, u ∈ Rd.
  Proof. Let w′ = ΠS(w) and u′ = ΠS(u). By the convexity of S, we have
  〈w − w′, u′ − w′〉 ≤ 0 and 〈u− u′, w′ − u′〉 ≤ 0.
  Summing these two inequalities, we obtain 〈w − u,w′ − u′〉 ≥ 〈w′ − u′, w′ − u′〉. Then, by Cauchy–Schwarz,
  ‖w′ − u′‖2 ≤ 〈w − u,w′ − u′〉 ≤ ‖w − u‖‖w′ − u′‖,
  which concludes the proof.
  Lemma 9. If f is l-strongly convex, then
  〈hu, u− w∗〉 ≥ l‖u− w∗‖2, ∀u ∈ Rd and hu ∈ ∂f(u).
  Proof. Applying Definition 3 twice
  f(w∗)− f(u) ≥ 〈hu, w∗ − u〉+ l
  2 ‖w∗ − u‖2
  f(u)− f(w∗) ≥ + l 2 ‖u− w∗‖2,
  and summing these two inequalities, we conclude the proof.
  Lemma 10. For any w ∈ S,
  ‖wk+1 − w‖2 ≤ ‖wk − w‖2 − 2γk〈gk, wk − w〉+ γ2k‖gk‖2.
  Proof. It is straightforward to verify that
  ‖wk+1 − w‖2 = ‖ΠS(wk − γkgk)− w‖2
  ≤ ‖wk − γkgk − w‖2
  = ‖wk − w‖2 − 2γk〈gk, wk − w〉+ γ2k‖gk‖2,
  where the inequality results from Lemma 8.
  Lemma 11. If ‖gk − hk‖ ≤ δ‖hk‖, then
  (1− δ)‖hk‖ ≤ ‖gk‖ ≤ (1 + δ)‖hk‖,
  and −δ
  2 (‖hk‖2 + ‖wk − w∗‖2) ≤ 〈gk − hk, wk − w∗〉 ≤
  δ 2 (‖hk‖2 + ‖wk − w∗‖2).
  Proof. For the first displayed inequality, it is straightforward to verify the upper bound
  ‖gk‖ ≤ ‖hk‖+ ‖gk − hk‖ ≤ (1 + δ)‖hk‖,
  and similarly the lower bound. For the second displayed inequality, Cauchy–Schwarz leads to the upper bound
  〈gk − hk, wk −w∗〉 ≤ ‖gk − hk‖ · ‖wk −w∗‖ ≤ δ‖hk‖ · ‖wk −w∗‖ ≤ δ
  2 (‖hk‖2 + ‖wk −w∗‖2).
  The lower bound is similarly proved.
sections.heading: A.2 PROOF OF THEOREM 1
sections.text: By the weak law of large numbers, Bt(v) → B(v) in probability for any v, where the probability space is with respect to u. Then, q(Bt(v))→ q(B(v)) in probability by the continuous mapping theorem. Applying the law of large numbers again, now for v on a separate probability space different from that of u, we conclude that Gst → G in probability.
sections.heading: A.3 PROOF OF THEOREM 2, INEQUALITY (8)
sections.text: Applying Lemma 10 with w = w∗, we have
  ‖wk+1 − w∗‖2 ≤ ‖wk − w∗‖2 − 2γk〈hk, wk − w∗〉 − 2γk〈gk − hk, wk − w∗〉+ γ2k‖gk‖2.
  Applying Lemma 9 with u = wk and Lemma 11, we have
  ‖wk+1 − w∗‖2 ≤ ‖wk − w∗‖2 − 2γkl‖wk − w∗‖2 + γkδ(‖hk‖2 + ‖wk − w∗‖2) + γ2k(1 + δ)2‖hk‖2
  = (1− 2γkl + γkδ)‖wk − w∗‖2 + (γkδ + γ2k(1 + δ)2)G2. (15)
  In what follows, we show by induction on k that ‖wk − w∗‖2 ≤ [ (1 + δ)2
  (l − δ)2k +
  δ
  l − δ
  ] G2.
  Then, setting k = T we can conclude the proof.
  First, in the base case when k = 1, by assumption we have
  ‖wk − w∗‖2 ≤ G2 l2 ≤ (1 + δ) 2 (l − δ)2 G2 ≤
  [ (1 + δ)2
  (l − δ)2 +
  δ
  l − δ
  ] G2.
  Then, in the induction step, taking γk = [(l − δ)k]−1 as defined in the theorem on (15) and using the induction hypothesis, we have
  ‖wk+1 − w∗‖2 ≤ lk − δk − 2l + δ
  (l − δ)k
  [ (1 + δ)2
  (l − δ)2k +
  δ
  l − δ
  ] G2 + [ δ
  (l − δ)k +
  (1 + δ)2
  (l − δ)2k2
  ] G2
  = (lk − δk − 2l + δ)(1 + δ)2
  (l − δ)3k2 G2 + (lk − δk − 2l + δ)δ (l − δ)2k G2 + δ (l − δ)k G2 + (1 + δ)2 (l − δ)2k2 G2
  ≤ (k − 2)(1 + δ) 2
  (l − δ)2k2 G2 + δ(k − 1) (l − δ)k G2 + δ (l − δ)k G2 + (1 + δ)2 (l − δ)2k2 G2.
  For the right-hand side, combine the first and the fourth term, and the second and the third term, we obtain
  ‖wk+1 − w∗‖2 ≤ (k − 1)(1 + δ)2
  (l − δ)2k2 G2 +
  δ (l − δ) G2 ≤ (1 + δ)
  2
  (l − δ)2(k + 1) G2 +
  δ
  (l − δ) G2,
  which completes the induction step.
sections.heading: A.4 PROOF OF THEOREM 2, INEQUALITY (9)
sections.text: Applying Lemma 10 with w = w∗, we have
  ‖wk+1 − w∗‖2 ≤ ‖wk − w∗‖2 − 2γk〈hk, wk − w∗〉 − 2γk〈gk − hk, wk − w∗〉+ γ2k‖gk‖2.
  Applying the definition of strong convexity and Lemma 11, we have
  ‖wk+1 − w∗‖2 ≤ ‖wk − w∗‖2 − 2γk[f(wk)− f(w∗)]− γkl‖wk − w∗‖2
  + γkδ(‖hk‖2 + ‖wk − w∗‖2) + γ2k(1 + δ)2‖hk‖2
  = −2γk[f(wk)− f(w∗)] + (1− γkl + γkδ)‖wk − w∗‖2 + (γkδ + γ2k(1 + δ)2)G2.
  Rearranging, we have
  2[f(wk)− f(w∗)] ≤ (γ−1k − l + δ)‖wk − w ∗‖2 − γ−1k ‖wk+1 − w ∗‖2 + (δ + γk(1 + δ)2)G2.
  Noting that the step size γk = [(l − δ)k]−1, we have 2[f(wk)− f(w∗)] ≤ (l − δ)(k − 1)‖wk −w∗‖2 − (l − δ)k‖wk+1 −w∗‖2 +G2 [ δ + (1 + δ)2
  (l − δ)k
  ] .
  Summing from k = 1 to k = T and multiplying by 1/(2T ), we have
  1
  T T∑ k=1 [f(wk)− f(w∗)] ≤ − l − δ 2 ‖wT+1 − w∗‖2 + G2 2T
  [ δT + (1 + δ)2
  l − δ T∑ k=1 1 k
  ] .
  By the convexity of f and using the bound ∑T k=1 1/k ≤ 1 + log T , and noting that δ = ρ/T , we have
  f(wT )− f(w∗) ≤ − l − δ
  2 ‖wT+1 − w∗‖2 +
  G2
  2T
  [ ρ+ (1 + ρ/T )2
  l − ρ/T (1 + log T )
  ] .
  Relaxing the right-hand side through omitting the negative term, we thus conclude the proof.
sections.heading: A.5 PROOF OF THEOREM 3
sections.text: The L-smoothness property implies a second order condition for convex functions:
  f(wk)− f(w∗) ≤ L
  2 ‖wk − w∗‖2.
  Then, applying (8) with k = T , we conclude the proof.
sections.heading: A.6 PROOF OF THEOREM 4
sections.text: We reuse (15) in the proof of inequality (8) in Theorem 2:
  ‖wk+1 − w∗‖2 ≤ (1− 2γkl + γkδ)‖wk − w∗‖2 + (γkδ + γ2k(1 + δ)2)G2.
  Applying step size γk = c, we have
  ‖wk+1 − w∗‖2 ≤ (1− 2cl + cδ)‖wk − w∗‖2 + (cδ + c2(1 + δ)2)G2.
  Unrolling recursion with respect to k, we have
  ‖wk+1 − w∗‖2 ≤ (1− 2cl + cδ)k‖w1 − w∗‖2 + (cδ + c2(1 + δ)2) k−1∑ i=0 (1− 2cl + cδ)iG2.
  Because 0 < 1− 2cl + cδ < 1 by assumption, we have k−1∑ i=0 (1− 2cl + cδ)i < 1 2cl − cδ ,
  which concludes the proof.
sections.heading: A.7 PROOF OF THEOREM 5
sections.text: Applying Lemma 10 with w = w∗, we have ‖wk+1 − w∗‖2 ≤ ‖wk − w∗‖2 − 2γk〈hk, wk − w∗〉 − 2γk〈gk − hk, wk − w∗〉+ γ2k‖gk‖2.
  Applying a property of convex functions and Lemma 11, we have ‖wk+1 − w∗‖2 ≤ ‖wk − w∗‖2 − 2γk[f(wk)− f(w∗)] + γkδ(‖hk‖2 + ‖wk − w∗‖2) + γ2k(1 + δ)2‖hk‖2 = −2γk[f(wk)− f(w∗)] + (1 + γkδ)‖wk − w∗‖2 + (γkδ + γ2k(1 + δ)2)G2. Rearranging, we have
  2[f(wk)− f(w∗)] ≤ (γ−1k + δ)‖wk − w ∗‖2 − γ−1k ‖wk+1 − w ∗‖2 + (δ + γk(1 + δ)2)G2. Summing from k = 1 to k = T , relaxing the negative term −γ−1T ‖wT+1 − w∗‖2 on the right-hand side, and multiplying by 1/(2T ), we have
  1
  T T∑ k=1 [f(wk)− f(w∗)] ≤ γ−11 + δ 2T ‖w1 − w∗‖2
  + T∑ k=2 γ−1k + δ − γ −1 k−1 2T ‖wk − w∗‖2 + G2 2T
  [ δT + (1 + δ)2
  T∑ k=1 γk
  ] .
  Applying ‖wk − w∗‖2 ≤ D2 for all k, we have
  1
  T T∑ k=1 [f(wk)− f(w∗)] ≤ (γ−1T + δT )D 2 2T + G2 2T
  [ δT + (1 + δ)2
  T∑ k=1 γk
  ] .
  Noting that γk = c/ √ k and δ = ρ/ √ T , we have
  1
  T T∑ k=1 [f(wk)− f(w∗)] ≤ 1 2 √ T ( 1 c + ρ ) D2 + G2 2T [ ρ √ T + c ( 1 + ρ√ T )2 T∑ k=1 1√ k ] .
  By the convexity of f and using the bound ∑T k=1 1/ √ k ≤ √ T + 1, we have
  f(wT )− f(w∗) ≤ 1
  2 √ T
  ( 1
  c + ρ
  ) D2 + G2
  2T
  [ ρ √ T + c ( 1 +
  ρ√ T
  )2√ T + 1 ] ,
  which concludes the proof.
sections.heading: A.8 PROOF OF THEOREM 6
sections.text: The L-smoothness property implies that
  f(wk+1) ≤ f(wk) + 〈∇f(wk), wk+1 − wk〉+ L
  2 ‖wk+1 − wk‖2.
  Noting that wk+1 − wk = −γkgk (because S = Rd) and applying Lemma 11, we have
  f(wk+1) ≤ f(wk)− γk〈hk, gk〉+ Lγ2k‖gk‖2
  2 ≤ f(wk)− γk(1− δ)‖hk‖2 +
  Lγ2k(1 + δ) 2‖hk‖2
  2 .
  Rearranging, we have
  ‖∇f(wk)‖2 ≤ [γk(1− δ)]−1 [f(wk)− f(wk+1)] + Lγk(1 + δ)
  2G2
  2(1− δ) .
  Summing from k = 1 to k = T , multiplying by 1/T , and noting that γk is constant, we have
  min k ‖∇f(wk)‖2 ≤
  [γ1(1− δ)]−1
  T [f(w1)− f(wT+1)] +
  Lγ1(1 + δ) 2G2
  2(1− δ) .
  Because f(wT+1) ≥ f(w∗) and γ1 = Df/[(1 + δ)G √ T ], we have
  min k ‖∇f(wk)‖2 ≤
  [γ1(1− δ)]−1
  T [f(w1)− f(w∗)] +
  Lγ1(1 + δ) 2G2
  2(1− δ) =
  (1 + δ)LGDf
  (1− δ) √ T ,
  which concludes the proof.
sections.heading: A.9 PROOF OF THEOREM 7
sections.text: Theorem 2.2 of Friedlander & Schmidt (2012) states that when the gradient error
  ‖gk − hk‖ < δk for all k ≥ 1, (16)
  inequality (14) holds. It remains to show that the probability that (16) happens is at least 1− . The assumption on the sample size Nk means that
  Cke −Nkτ(δk/‖hk‖) ≤ /T.
  Then, substituting δk = δ‖hk‖ into assumption (6) yields Pr ( ‖gk − hk‖ ≥ δk ∣∣∣ g1, . . . , gk−1) ≤ Cke−Nkτ(δk/‖hk‖) ≤ /T. Hence, the probability that (16) happens is
  T∏ k=1
  [ 1− Pr ( ‖gk − hk‖ ≥ δk ∣∣∣ g1, . . . , gk−1)] ≥ T∏ k=1 (1− /T ) ≥ 1− ,
  which concludes the proof.
sections.heading: B EXPERIMENT DETAILS
sections.heading: B.1 THE “MIXTURE” DATA SET
sections.text: The data set is a Gaussian mixture with c = 3 components in d = 2 dimensions. The components N (µi, σ2i I) with µ1 = [−0.5, 0], σ1 = 0.75, µ2 = [0.5, 0], σ2 = 0.5, µ3 = [0, 0.866], and σ3 = 0.25 are equally weighted but significantly overlap with each other. Random connections are made between every pair of points. For points in the same component, the probability that they are connected is pintra = 1e-3; for points straddle across components, the probability is pinter = 2e-4. See Figure 4(a) for an illustration of the Gaussian mixture and Figure 4(b) for the graph adjacency matrix.
sections.heading: B.2 SUMMARY OF DATA SETS
sections.text: See Table 2 for a summary of the data sets used in this work.
sections.heading: B.3 (HYPER)PARAMETERS
sections.text: See Table 3 for the hyperparameters used in the experiments. For parameter initialization, we use the Glorot uniform initializer (Glorot & Bengio, 2010).
sections.heading: B.4 RUN TIME
sections.text: See Table 4 for the run time (per epoch). As expected, a smaller sample size is more computationally efficient. SGD with consistent gradients runs faster than the standard SGD and Adam, both of which admit approximately the same computational cost.