Stochastic Gradient Descent with Biased but Consistent Gradient Estimators
Authors: Jie Chen
Ronny Luss
Venue:  (2020)
Keywords: Stochastic optimization
biased gradient estimator
graph convolutional networks

Abstract: 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.


Under review as a conference paper at ICLR 2020
STOCHASTIC GRADIENT DESCENT WITH BIASED BUT CONSISTENT GRADIENT ESTIMATORS
Anonymous authors Paper under double-blind review
ABSTRACT
Stochastic gradient descent (SGD), which dates back to the 1950s, is one of the most popular and effective approaches for performing stochastic optimization. Re- search 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 intercon- nected. Recently, Chen et al. (2018) proposed using consistent gradient estima- tor 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 noncon- objectives. We verify the results with illustrative experiments 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.
INTRODUCTION
Consider the standard setting of supervised learning. There exists joint probability distribution P(x, y) of data and associated label and the task is to train predictive model, parameterized by w. that minimizes the expected loss l between the prediction and the ground truth y. Let us organize the random variables as 5 = (r, v) and use the notation E(w; {) for the loss. If & = (x W:). i I,..., n. are iid training examples drawn from P, then the objective function is either one of the following well-known forms:
1 n Σ
expected risk f(w) B[e(w; E)]; empirical risk ((w)
Elu;
Stochastic gradient descent (SGD), which dates back to the seminal work of Robbins & Monro [195T, has become the de-facto optimization method for solving these problems in machine learn- ing. In SGD, the model parameter is updated until convergence with the rule
Wk++1 = w/k
1,2,
where 7 is step size and go is an unbiased estimator of the gradient V f((x).. Compared with the full gradient (as is used in deterministic gradient descent), an unbiased estimator involves only one or few training examples and is usually much more efficient to compute.
1.1 LIMITATION UNBIASED GRADIENT AND REMEDY: CONSISTENT GRADIENT
This scenario, however, does not cover all learning settings. A representative example that leads to costly computation of the unbiased gradient estimator V((w, & graph nodes. Informally speak- ing, graph node & needs to aggregate information from its neighbors. If information is aggregated
For introductory purpose omit the projection operator for constrained problems. All analysis in this work covers projection.

---

Under review as a conference paper at ICLR 2020
across neighborhoods, must request information from its neighbors recursively, which results in inquiring a large portion of the graph. In this case, the sample loss for & involves not only ço but also all training examples within its multihop neighborhood. The worst scenario is that computing Vl(w, &t) costs (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 Ç is involved.
In a recent work, Chen et al. (2018) proposed a consistent gradient estimator as an economic al- ternative to 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 thorough analysis of the convergence behavior of SGD when 9k (2) is consistent estimator of ff(w)). We show that using this estimator results in the same convergence behavior as does using unbiased ones.
Definition 1, An estimator 9* of h, where N denotes the sample size, consistent if g converges
to h in probability: plim oo g N h. That is, for any >> 0, lo Pr(llg" hil > t) 0.
1.2 DISTINCTIONS BETWEEN UNBIASEDNESS AND CONSISTENCY
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 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 con- sistency. 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 gd of h, where N denotes the sample size, is asymptotically unbiased E[g"1 + h.
An estimator can be (asymptotically) unbiased but inconsistent. Consider estimating the mean = μl of the normal distribution [u, o²) by using N independent samples ,,,...,XX XN. The estimator gd Xi (i.e., always use Xi regardless of the sample size N) is clearly unbiased because E[X1] = μc; but it is inconsistent because the distribution of X1 does not concentrate around ju. Moreover, the estimator is trivially asymptotically unbiased.
An estimator can be consistent but biased. Consider estimating the variance = of the normal distribution N NN,, o²) by using N independent samples X Xi..... XNN. The estimator gN [ X)2/N. where X Σ X,/N, has mean a² dN 1)/N and variance 20 1)/N2, Hence, is consistent owing
straightforward invocation of the Chebyshev inequality, by noting that the mean approaches x² and the variance approaches zero. However, the estimator admits nonzero bias d² /NN for any finite N.
An estimator can be consistent but biased even asymptotically. In the preceding example, the bias o2/N approaches zero and hence the estimator asymptotically unbiased. Other examples exist for the estimator to be biased even asymptotically. Consider estimating the quantity h = 0 with an estimator g% that takes the value 0 with probability (N 1)/N and the value N with probability 1/N. Then, the probability that g departs from zero approaches zero and hence it is consistent. However, M] and thus the bias does not vanish N increases.
1.3 CONTRIBUTIONS OF THIS WORK
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 al. 2017 Veličković et al. 201 8), 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 series of graph neural networks. The theory reassures practitioners of doubts on the convergence of their optimization solvers.
2

---

Under review as a conference paper at ICLR 2020
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 analy- sis under the same problem setting. This work opens the opportunity of improving the analysis, in 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 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 far.
2 MOTIVATING APPLICATION: REPRESENTATION LEARNING OF GRAPH NODES
For a motivating application, consider the graph convolutional network model, GCN (Kipf & Welling, 2017). that learns embedding representations of graph nodes. The I-th layer of the net- work is compactly written as
(3) where À is a normalization of the graph adjacency matrix, W is a parameter matrix, and o is nonlinear activation function. The matrix H contains for each row the embedding of graph node input to the I-th layer, and similarly for the output matrix H((+1), With L layers, the network transforms initial feature input matrix ( to the output embedding matrix H()) For node v, the embedding H (14) (v,:) may be fed into a classifier for prediction.
H = (AHH)(()))
Clearly, in order to compute the gradient of the loss for e, one needs the corresponding row of H(L), the rows of (L-11) corresponding to the neighbors of v, and further recursive neighbors across each layer, all the way down (0) The computational cost of the unbiased gradient estimator is rather high. In the worst case, all rows of (0)) are involved.
To resolve the inefficiency, Chen et al. (2118) proposed an alternative gradient estimator that is bi- ased but consistent. The simple and effective idea is 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 network with single layer; theoretical results for more layers straightfor- wardly follow that of Theorem below, through induction.
The approach generalizes the setting from 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
node is generalized a feature function (u), and the output embedding vector // (2) (v,:) for
node is generalized to an embedding function Z(v), where the random variables u and in two sides of the layer reside different probability spaces, with probability measures P(u) and P(v), respectively. Furthermore, the matrix is generalized into a bivariate kernel A(v, u) and the loss é is written function of the output Z(v). Then, ①1 and (3) become
f = Exp ((v) (()()( with ((v) (f A(tr.)X((WaPPl))
(4)
Such functional generalization facilitates sampling on all network layers for defining a gradient estimator. particular, defining B(v) = - Ā(v, u) x) (u) dP(u), simple calculation reveals that the gradient with respect to the parameter matrix W is
G= - (((()) dP(v), where
q(B) Bd (BBW)) and h- too.
Then, one may use iid samples of in the input and iid samples of e in the output to define an estimator of G:
Gat 1 ((.((())), -~ P(v), with Bl(x)= 1 A(e, u, (())) uy P(u).
The gradient estimator Get so defined is consistent; see proof in the supplementary material. Theorem 1. If q is continuous and is finite, then plim plimg,t-oo Get G.
9,10000
3

---

Under review as a conference paper at ICLR 2020
3 SETTING AND NOTATIONS
We now settle the notations for SGD. We are interested in the (constrained) optimization problem
min fww),
wES
where the feasible region is convex. This setting includes the unconstrained case S Rd. We assume that the objective function f R' + R is subdifferentiable; and use @f(w) to denote the subdifferential at w. When necessary to refer to an element of this set, we use the notation h. f' is differentiable, then clearly, @f(w) (w)).
The standard update rule for SGD is wk++1 [g - 7k-k), where gt is the negative search direction at step k "h is the step size, and IIs is the projection onto the feasible region: [=s := argmin ||w u/l. For unconstrained problems, the projection clearly omitted: wh-1 = w/x Ta.r..
Denote by w" the global minimum. We assume that w" an interior point of S, so that the subdiffer- ential of at wn contains zero. For differentiable f. this assumption simply means that Vf(w") = 0.
Typical convergence results are concerned with how fast the iterate wy approaches w", or the func- tion value f(ws) approaches f(w".. Sometimes, the analysis is made convenient through a con- vexity assumption on S. such that the average historical function values f(w;), b,...,,,. is
lowered bounded by f(wxx) ), with Wy being the cumulative moving average Wy = 1 Σm= w
The following definitions are frequently referenced. Definition 3. We say that f is I-strongly convex (with 1 > 0) if for all IR and hn @f(uu)
L
[w) - (u) 2 (bes u) + 2
u/|².
Definition 4. We say that is L-smooth (with L >>>> 0) if it is differentiable and for all w, Rd,
- S T.lw - ull.
CONVERGENCE RESULTS
Recall that an estimator gd of h is consistent for any 0, lim Pr(llg - All c) 0. N-000
(5)
In our setting, h corresponds to element of the subdifferential at step k; i.e., h& E 0f(w)), N corresponds to the negative search direction Jk. and N corresponds the sample size No. That g converges to hg in probability does not imply that ge unbiased. Hence, natural question asks
N₂ as the gradient estimator. This section answers what convergence guarantees exist when using Jk that question.
First, note that the sample size N₂ is associated with only NN= but also the new iterate we We omit the superscript N₁, in these vectors to improve readability.
Similar to the analysis of standard SGD, which built on the premise of the unbiasedness of ga 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, avoid verbosity.
4.1 ASSUMPTIONS
The convergence 55) 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 C > and a nonnegative function 766) the positive axis such that
Pr [1ex hall 2 611/2|1 (0k-1.,9k--1)) < CLe Cie-Neri0
(6)
4

---

Under review as a conference paper at ICLR 2020
for all & > 1 and 8 > 0. A similar assumption is adopted by Homem-de-Merl Mello 2008 that studied stochastic optimization through sample average approximation. In this case, the exponential tail occurs when the individual moment generating functions exist, simple application of the Chernoff bound, For the motivating application GCN, the tail is indeed exponential as evidenced by Figure
Note the conditioning the history 91..... 9k-1 in The reason is that h& (i.e., the gradient Vf(w)) f is differentiable) is by itself a random variable dependent on history. 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 .)..... - is sufficiently clear.
Assumption 1. The gradient estimator 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 5 E (0, 1). define the event
Es (1911 |191 hill S 6||h||| and ||92 h2l - /||/2|| and and ll - hr S 3
Given 66 and any e (0, 1), one easily calculates that if the sample sizes satisfy
N& 2 T(5) log (TC:/c),
for all k, then,
T
T 2 II - (T))2--6
Pr(Es) 2 II (1 Che (2e--N778) k=1
k=1
Hence, all results in this section are established under the event Eg that occurs with probability at least 1 - e, 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 e) and the event Es, 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- -gaddiint condition for standard SGD analysis, we impose the following assumption.
Assumption 2. There exists finite G > 0 such that ||h|| G for all h Of(w) and w E S.
4.2 RESULTS
Let us begin with the strongly convex case. For standard SGD with unbiased gradient estimators, ample results exist that indicate O(1/T") convergence for the expected error, where T is the number of updates; see, e.g., (2.9)-(2.10) 10) of Nemirovski al. (2009) and Section 3.1 of Lacoste-Julie 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 d, which relates to the sample sizes in 77) for guaranteeing satisfaction of the bound with high probability.
Theorem 2. Let f be l-strongly conver with < G/| - w= Assume that T updates are run, with diminishing step size "Ik [(1 8)k] for k = 1,2, T, where 5 = p/TT and < l is an arbitrary constant independent T. Then, for any such p. any e (0, 1), and sufficiently large sample sizes satisfying (7). with probubility at least 1 -
have
G
(1 + p/T)² + p(l p(l- p/T)
|W w0 10 <
(8)
T
(1 p/T//
and
G
(1 p/T?
f f(w')()))))))))) <
p+
1 p/T (1 + log
(9)
2T
Ignoring the logarithmic factor, if any.
5

---

Under review as a conference paper at ICLR 2020
Note the assumption on | in Theorem 2 This assumption is mild since if f is I-strongly convex, it is also I'sstrongly convex for all < I. The assumption is needed in the induction proof of (8) when establishing the base case || w" ||- One may remove this assumption at the cost of cumbersome right-hand side of (8), over which we favor a neater expression in the current form.
With additional smoothness assumption, may eliminate the logarithmic factor in and obtain a result for the iterate WT rather than the running average Wr. The result a straightforward consequence of (8).
Theorem 3. Under the conditions of Theorem 2 additionally let f be L-smooth. Then, for any p satisfying the conditions, any (0, 1), and sufficiently large sample sizes satisfying 7 with probability at least 6. we have
LG f(WT) - f(w)) S 2T
(1+ + p/T)² p(()))/(pppp
(10)
(1-p/T)
In addition to O(L/T) convergence, it is also possible to establish linear convergence (however) a non-vanishing right-hand side, as the following result indicates. To obtain such result, we use constant step size. Bottou et al. (2016) show a similar result for the function value with an additional smoothness assumption smoothness assumption using consistent gradients.
different setting, we give one for the iterate error without the
Theorem 4. Under the conditions of Theorem 2 except that one sets a constant step size c with c < (2l - 5)-1 for all for any p satisfying the conditions, any (0, 1), and sufficiently large sample sizes satisfying (7). with probability at least 1 - c, we have
| - w0 112 < (1 2cl + +c5)== c5)"T~11ww) - w1 + c(1 + +)2
-1 G².
(11)
Compare 11 with in Theorem 2 The former indicates that in the limit, the squared iterate error is upper bounded by positive term proportional to G2; the remaining part of this upper bound decreases at linear speed. The latter, on the other hand, indicates that the squared iterate error in fact will vanish, although does at sublinear speed O(1TT).
For convex (but not strongly convex) typically O(1/ VT) convergence 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, sus ||W u|l = D. Assume that T updates are run, with diminishing step size 7 c for = 1,2, ..... T and for some > 0. Let 8 = P/ where > O is an arbitrary constant inde- pendent T. Then, for any such any e (0, 1), and sufficiently large sample sizes satisfying (7) with probability at least E, we have
G² S(WT) - f(w") 2VT (6+p) D2 D2+
(D+c((1
P
2
1 T
VT
(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 Shaalev-Shwartz & Ben-David (2014). For such result, one assumes that the step size is inversely proportional to vT. 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/vT) convergence results for unbiased gradient estimators; see, e.g., Theorem of Reddi et al. (2116) (which is a simplified consequence of the theory presented in Ghadimi & Lan (2013). We derive 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 7k D11((1 G)GVT) for k 1,2, 1,2,...7 .., T, where Dj [2([(m) (w"")) and (0.

---

Under review as a conference paper at ICLR 2020
is arbitrary constant. Then, for any such 6, any satisfying 77. with probability at least - E, we have
(0, 1), and sufficiently large sample sizes
(1 (1+ (1+G)G
min
[V
(13)
(1-8)V
4.3 INTERPRETATION
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 ((/TT), or linear if one tolerates a non-vanishing upper bound, and the convex and nonconvex cases O(1/VT). These theoretical results, however, are based on assumptions of the sample size N& and the step size T 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 hyperparameters to be tuned against a validation set.
Nevertheless, these results establish a qualitative relationship between the sample size and the opti- mization error. Naturally, to maintain the same failure probability c, the relative gradient estimator error decreases inversely with the sample size Nu. This intuition holds true in the tail bound con- dition (6) with (7). when T()) is monomial or a positive combination of monomials with different degrees. With this assumption, the larger is Ng. the smaller is 5 (and also p. the auxiliary quantity defined in the theorems); hence, the smaller are the error bounds
4.4 REMARKS
Theorem presents a linear convergence result for the strongly convex case, with a non-vanishing right-hand side. In fact, is possible obtain a result with the same convergence rate but vanishing right-band 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 N₂ and the gradient error 5.
Theorem 7. Let f be I-strongly convex and L-smooth with < L. Assume that T updates are run with constant step size 7/k L/L for k 1,2...... Let òz. k 1 be a sequence where lim / S 1. Then, for any positive < 1/I, c 1). and sample sizes
with probability at least 1 log(//)) for 1.22....,7
No T ( (0b6///1111)1111/11)1)))
have
f(WT) fw") (1-1/1)"- +O(E))+
(14)
where ET max (07, (1 1/L + 3)
Here, 5R is the step-dependent gradient error. If it decreases to zero, then so does Er. Theorem adapted from |Frielladdrr Schmidd (2012), who studied unbiased gradients as well as noisy gradients. We separate Theorem 7 from those in Section 4.ction|4.2]ong only for the sake of presentation clarity. The spirit, however, remains the same. Namely, consistent estimators result 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.
5 NUMERICAL ILLUSTRATIONS
In this section, we report several experiments to illustrate the convergence behavior of SGD by using consistent gradient estimators. We base the experiments the training of the GCN model (Kipf & Welling 2017) motivated earlier (ef. Section 2). The code repository will be revealed upon paper acceptance.
5.1
DATA SETS
We three data sets for illustration, one synthetic and two real-world benchmarks.
7

---

Under review as a conference paper at ICLR 2020
The purpose of a synthetic data set to avoid the regularity in the sampling of trainingvvalidationneest examples. The data set, called "Mixture," is a mixture three overlapping Gaussians. The points randomly connected, with 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 al. (2018). See the supplementary material for summary of all data sets.
5.2 (STRONGLY) CONVEX CASE
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 (AXW()))) 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 = ()ftma is the neighborhood aggregation Ax.
Standard batched training in SGD samples a batch (denoted by the index set 41) from the training set and evaluates the gradient of the loss of softmax softmax(A((1 x)x gradient training, we additionally uniformly sample the input layer with another index set To and evaluate instead the gradient of the loss of softmax [o] A(T,, X (Too:))
In the analyzed consistent-
1.4
2
1.2
SGD consizent Isance
conssbrtticamp
560 compatrticanp
1.2
S.D carnis [sargl 1900)
SGB consklert buampe (97)
5GB consabert ivargs 1650)
SGD cornos witi (samplrd))
SGB undeaved
5GB bharg 3220)
5GD intiised
ADAM urdnased
5GB corsater (2))
unblased
560
prbissed
0.8
0.6
0.5
0.6
0.4
0.4
0.2
20
40
60
20
100
20
40
50
50
100
40
60
80
120
opoch [k/ num batch
opach kk num, batch
opach (kc num hatph_bathh
(a) Mixture
(b) Cora
(c) Pubmed
Figure 1: Convergence history for 1-layer GCN, under different training algorithms.
Figure shows the convergence curves as the iteration progresses. The plotted quantity is the over- all loss 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 con- sistent gradient estimators, with varying sample size (T)) Additionally, compare with the Adam training algorithm (Kingma & Ba 2015), which is 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.
important to note that the training loss is only a surrogate measure of the model performance; and often early termination of the optimization acts healthy regularization against over-fitting. In our setting, a small sample size may not satisfy the assumptions of the theoretical results, but proves to be practically useful. In Table | (left), we report the test accuracy attained by different training algorithms at the epoch where validation accuracy peaks. One sees that Adan 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.
8

---

Under review as a conference paper at ICLR 2020
Table 1: Test accuracy (in percentage) and epoch number (inside parentheses) for different GCN
architectures and training algorithms. For the same architecture, initialization is the same. The epoch number the one when best validation accuracy occurs.
l-layer GCN
2-layer GCN
Mixture
Cora
Pubmed
Mixture
Cora
Pubmed
SGD (400)
78.0 (68) 85.8 (97)
86.2 (15)
86.7 (76)
87.1 (34)
87.5 (88)
SGD (800)
77.8 (46)
86.1 (86)
87.9 (68)
86.9 (87)
85.8 (13)
87.6 (87)
SGD (1600)
77.9 (87)
88.6 (35)
86.8 (94)
88.3 (85)
SGD (3200)
88.9 (98)
88.1 (88)
SGD unbiased
78.1 (93)
84.2 (87)
88.1 (75)
86.8 (66)
87.4 (27)
87.9 (90)
Adam unbiased
80.0 (95)
84.9 (21)
88.4 (20)
87.6 (94)
87.0 (04)
88.0 (06)
5.3 NONCONVEX CASE
When GCN has intermediate layers, the loss function is generally nonconvex. A 2-layer GCN reads
P = softmax A ReLU(AXW()) W()), and GCN with more layers is analogous.
We repeat the experiments in the preceding subsection. The results are reported in Figure and Ta- ble [ (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 consistent gradi- ent approaches that with an unbiased one.
1.2
1.2
5GD Lorman aeti [sanz] 400
SGi comea baurg 8257
SGB comselerl AIS:
560 consirent Isangl E001
560 consetertisamp 9781
560 consiterticame 902:
550 consisent (sampt (i)
1.5
560 unblased
560 consitrrtcamp 3250)
SCD untiaeed
ADAM unblased
0.8
560 consitertoampp nZ)
0.8
ADAM unbiased
560 unbiasae
0.6
arbiased
0.5
0.4
0.5
0.2
0.3
0
20
40
50
80
100
epoch |
epach num,
epoch
num,
batch
(a) Mixture
(b) Cora
(c) Pubmed
Figure 2: Convergence history for 2-layer GCN, under different training algorithms.
On the other hand, compared with I-layer GCN, 2-layer GCN yields substantially higher test ac- curacy 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, small sample size (e.g., 400) suffices for achieving results comparable to the state of the art (cf. Chen et al. (2018)).
5.4 PROBABILITY CONVERGENCE
The nature of consistent estimator necessitates characterization of the speed of probability con- vergence 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 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 size N at different levels of estimator error 6, for the initial gradient step in l-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.
function of the sample
Additionally, the case of 2-yyyer GCN is demonstrated by the dashed curves in Figure The curves tend to be straight lines in the limit, which indicates exponential convergence.

---

Under review as a conference paper at ICLR 2020
0.1
failure probabillty
0.001
0.2
0.3
0.0001
1000
2000
3000
4000
5000
sample size
Figure 3: Failure probability versus sample size at different levels of estimator error Solid: 1-layer
GCN; dashed: 2-layer GCN.
6 CONCLUDING REMARKS
To the best of knowledge, this 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' Asprrmottt 2008 (chmmitt et al. (011)) or noisy (Friedlander & Schmidt [012 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 unbi- ased 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 al. 2014] Bottou et al., 2016). Another direction is the development training algorithms for neural networks for large graphs. GCN is only one member of broad fam- ily of message passing neural networks (Gilmer et al. 2017) that suffer from the same limitation of neighhorhood aggregation. Learning in these cases inevitably faces the costly computation of the sample gradient. Hence, a consistent estimator appears to be promising alternative, whose construction is awaiting more innovative proposals.
more computation- and memory-efficient efficient
We are grateful to an anonymous reviewer who inspired us of an interesting use case (other than GCN). Learning rank is machine learning application that constructs ranking models for in- formation retrieval systems. In representative methods such as RankNet (Burges et al. 20055 and subsequent improvements (Burges et al. 2007; Burges 2010). 8y is the ranking function for docu- ment and the learning amounts to minimizing the loss
Σ S log(1 + +E))))) (i.))
where the summation ranges over all pairs of documents such that i is ranked higher than The pairwise information may be organized as a graph and the loss function may be similarly generalized double integral analogous (4. Because of nonlinearity, Monte Carlo sampling of each integral will result in a biased but consistent estimator. Therefore, a new training algorithm to sample i and separately (forming a consistent gradient) and apply SGD. The theory developed in this work offers guarantees of training convergence.
REFERENCES
Léon Bottou, Frank E. Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. arXiv:1606. 04838v3 2016.
Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. In /CLR, 2014.
Chris Burges, Tal Shaked, Erin Renshaw, Ari Lazier, Matt Deeds, Nicole Hamilton, and Greg Hul- lender. Learning rank using gradient descent. In ICML, 2005.
10

---

Under review as a conference paper at ICLR 2020
Christopher J. Burges, Robert Ragno, and Quoe V. Le. Learning to rank with nonsmooth cost functions. In NIPS, 2007.
Christopher J.C. Burges. From RankNet to LambdaRank to LambdaMART: An overview. Technical Report MSR-TR-2010-82, Microsoft Research, 2010.
Jie Chen, Tengfei Ma, and Cao Xiao. FastGCN: Fast learning with graph convolutional networks via importance sampling. In ICLR, 2018.
Alexandre d' Aspremont. Smooth optimization with approximate gradient. SIAM J. Optim., 19(3): 1171-1183, 2008.
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives. In NIPS, 2014.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In NIPS, 2016.
Olivier Devolder, François Glineur, and Yurii Nesterov. First-order methods of smooth convex optimization with inexact oracle. Mathematical Programming,
(atpmmminnn.1(1112111101 146(1-2):37-75,2)) 2014.
Michael P. Friedlander and Mark Schmidt. Hybrid deterministic-stohhaee methods for data fitting.
SIAM J. Sci. Comput., 3:(3):A 13800A1405, 2012.
Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points online stochastic gradient for tensor decomposition. In COLT, 2015.
Saeed Ghadimi and Guanghui Lan. Stochastic first- and zeroth-order methods for nonconvex stochastic programming. SIAM Optim., 23(4):2341 2013.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry, In ICML, 2017.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In AISTATS, 2010.
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NIPS, 2017.
Tito Homem-de-Menn Melllo. On rates of convergence for stochastic optimization problems under nonin- dependent and identically distributed sampling. SIAM J. Optim., 19(2):524-551, 2008
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In NIPS, 2013.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR, 2015.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In ICLRR 2017.
Simon Lacoste-Julien, Mark Schmidt, and Francis Bach. simpler approach obtaining an (11))) convergence rate for the projected stochastic subgradient method. arxiv:1212.2002 2012.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. networks. In ICLR, 2016.
Gated graph sequence neural
Liu. CSC 576: Stochastic gradient "descent" algorithm. https://www.cs. wttp:/ww...reo....mmm.......ooo. 10. pdf 2015.
A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM J. Optim., 1744)1977, 2009.
Sashank J. Reddi, Ahmed Hefny, Suvrit Sra, Barnabas Poczos, and Alex Smola. Stochastic variance reduction for nonconvex optimization. In ICMI., 2016.

---

Under review as a conference paper at ICLR 2020
Herbert Robbins and Sutton Monro. A stochastic approximation method. Ann. Math. Statist., 22(3): 400-407, 1951.
Mark Schmidt, Nicolas L. Roux, and Francis R. Bach. Convergence rates of inexact proximal- gradient methods for convex optimization. In NIPS, 2011.
Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
A PROOFS
A. LEMMAS
Here are a few lemmas needed for the proofs in subsequent subsections.
Lemma 8. Projection is nonexpanding, i.e.,
[IIs(w) [1s(u)] || w/l, Vw, Rd. Proof. Let w'= = (w) and w' = (1)) By the convexity of S, we have
(w w', u' w²) S and (u n', w' u') S 0. Summing these two inequalities, we obtain (w u, w/ u') 2 (w' u', w/ w') Then, by Cauchy-Schwarz,
- 1w''''ll
s (w u, w' - u') s w|w u I|llww ut
which concludes the proof.
Lemma 9. If I-strongly convex, then
Vu E Rdd and by Of(u). (hus u w²) 11lu 111
Proof. Applying Definition twice
f(w") - f(u)= 2 (hu, w" - u)) +
2 I| ul|
f(u) - f(w))
ž ||ue w $13
and summing these inequalities, we conclude the proof. Lemma 10. For any S.
|1++1 w|| < ||w wil2
27yx (gk, 16 w) + +
Proof. It straightforward verify that
| w|| | ( 7k9rk - =w12
< |mw "k.9k - w|l2
[w w 27v (ghs wh w) + 72.1911
where the inequality results from Lemma 8
Lemma 11. If 1lgh - hell S 8 81(/1 ||. then
(1 - bxll - |1ga S (1+ 11)lll1ll1
and
8 (11/4 122 l - w =11) < (gr hvs wh w²) S 5
2 (11hall2 2 + +11 w =1)))).
2
12

---

Under review as a conference paper at ICLR 2020
Proof. For the first displayed inequality, it is straightforward to verify the upper bound
|1 - | + 19 hxll - (1 5)(lb
and similarly the lower bound. For the second displayed inequality, Cauchy Schharr- leads to the upper bound
- 2 (11//111 + ||00 = =31l3)
(ox - his wi w²) S 19 hell 1lwx w= S 811hx1 -1 ||0c -w"l
The lower bound is similarly proved.
A.2 PROOF OF THEOREM
By the weak law of large numbers, B, - B(v) in probability for any v, where the probability space is with respect orem. Applying the law of large numbers again, now for u on separate probability space different from that of u, we conclude that Gst G in probability.
Then, (B), g(B(v)) in probability by the continuous mapping the-
A.3 PROOF OF THEOREM
2 INEQUALITY
S
Applying Lemma 10 with w", have
|| - w 1 s 1|ak w²1 2 (hx Wk - -w> - 27 (at
h2, wk - w²) + +21119111
Applying Lemma 9 with wo and Lemma 11
have
[[ - w0 1 $ || - 11 2 Iuak - w 11? + hxll + ||w =0113) + 72(1 + 5) |
= (1 - 27x + 5) | w w²1l + (7u + n + G2
(15)
In what follows, we show by induction on &s that
(1 + 5)2 6)2k
|ww w²I s
+ 1 8 o².
Then, setting &s = T we can conclude the proof.
First, in the base case when A 1, by assumption have
G² (1 ()+5)3
(1 + 8)
- w011 S p
<
G² <
+
G².
(1 - 8)2
(1 8)2
1 1- 8
Then, in the induction step, taking Y = [[] 8)k} the induction hypothesis, we have
-1 as defined in the theorem on
15) and using
|| 10 12 1k
5k
21 8
(1 + 8)2
8
5
(1 (1+ 8)2
G
G²
8)h
(1 8)2k
1-8 5
(1
8)h:
(lk- 5k
21 8)(1 + 8)2
(Ik:
8k 21
+ 8)8
G² + (1+ 8)2
G2
G2
G
(1 - 5)3k2
(1-5)2k
(1 11-88 8)k
(1- 2)
< 2k 8)2
8(k 1)
(1 (1+
G2 +
G² +
G
G².
(1 8)212
(1 8)k
(1
8)k
(1-6)2R
For the right-hand side, combine the first and the fourth term, and the second and the third term, we obtain
[|w++1 - 11 (k: 1)(1 0)2 O² + a1 (1-8)
8
(1 (1+ 62 +
8
G² <
(1 8) + +1) (1 (1-8) G².
(1 - 8)212
which completes the induction step.
13

---

Under review as a conference paper at ICLR 2020
A.4
PROOF OF THEOREM 2
INEQUALITY
Applying Lemma 10 with w = w", we have
||w w" 1| = 1lwkk ==112 2n (hx, wk w") 27 (gk
hg, wk w²) + +2ll19x11
Applying the definition of strong convexity and Lemmal 11 we have
||=++1 - w²1 $ 1 - w²1 (f - f(w")) - 7x. - ==
+ 7x0(111411 + || - ==(l)) + rh(1 + 8)² /kxl1 11
2 - f(w"((())))))))))))))) + +1 11--wd - n 20 2" + (7 + 72
Rearranging, we have
2[x( [(ww]] - (7xs - 1 8)]l(; w= 11² 7/ 11 (1
Noting that the step size 7/ 5)k} have
(1+
2(f(w)) f(w")((w)))) (1 6)(k 1)[l
(1 (1- (1-0)k((r0+1- G2
5
(1 (1-8)k
Summing from &s to ls ' and multiplying by 1/(2T), we have
1-6
G2
(1 8)2 T
Σ [f(w)) fww)]
2 |1T+11 w 2T
5T
T
By the convexity of f and using the bound Ek 1/k < + log T, and noting that 8 = P.T, we have
f(w) 1 - -
G²
(L+p/TY 1- p/T (1 + log 77)
w'I'
2T
Relaxing the right-hand side through omitting the negative term, we thus conclude the proof.
A.5 PROOF OF THROREM 3
The L-smoothness property implies a second order condition for convex functions:
f(wx) - f(w))("""))))))))r - マ || - u11
Then, applying with & T, we conclude the proof.
A.6
PROOF OF THEOREM
We reuse (5) in the proof of inequality
(8) in Theorem 2
||0+1 w 2| < (1 2%yal + wx w011 + (nxō + +2(1++ +))())
Applying step size 7/ C, we have
| w0 || (1 2et
w011 (co (1+
Unrolling recursion with respect to k; we have
k-1
< = - - 2el + c5)* w - w w01 (c5 6 0
Σ (1
2el + c5)'
1=0
Because 0<1-20 c5 by assumption, we have
Σ
2el + 06)² 2el c8'
which concludes the proof.
14

---

Under review as a conference paper at ICLR 2020
A.7 PROOF OF THEOREM 5
Applying Lemma 10 with w = w", we have
|| w/ 1| S lluk w' w11 2 (h,, Wk w²) 27 (9k
h2, wk - -w)) + + 112
Applying property of convex functions and Lemma 11 have
||w++1- w0 12 - || w012 112 2xx(f(wx) f(w"(()))))))))))) + 0x0(11 112 + ll - -w1l + 2h(1 + 5) 1/2l?
=-2 s(w")] + (1 + 1100 w 11 + (7 + 71(1 + G?
Rearranging, we have
2[5(wx) - [(w ) S (7k + 5) || lork - w w=1 7/ 7 1| - w' || + (6 + 7x (1 + 5)
Summing from 1: = 1 to l = T, relaxing the negative term -7r || || w"| 1 on the right-hand
side, and multiplying by 1/())). we have
71 +
6
[f(wa) f(w"))
[w1
w" 11
T
2T
T
1
+ 8
7k
G
T
+
1108 - - 11
8T + (1 2
7kk
2T
2T
k=2
Applying I|wk - -=1l S D2 for all k. we have
1 T Σ [f(wx) - f(ww)\] (T D
G²
T
8T + 61+ 2
7
2T
2T
Noting that 7 c/VR and 8 = P/vT, we have
[(wx)) - f(wo")] 2VT c +
1
(c+0) D2
D²+ +
G²
PVT ( 1+ VT k=l
2
Σ
T
2T
Vi
By the convexity of f and using the bound
Et 1/VK S VT+ + 1, we have
1 2/2 (c
G²
pVT + c 1+ ) 2 VT+1
f(wr) f(w))-((w)) f(w")
2VT c +D)
D2 D²+
2T
which concludes the proof.
A.8 PROOF OF THEOREM 6
The L-smoothness property implies that
L
1(w++1) S [(wx) + (V (V](wx), Wk+1 wx) +
WR+11 wx 11x
2
Noting that Wk+11 Wi = ~k9k (because S IRd) and applying Lemma we have
[(w++1) S [(wx) - - (he 9k. L2llls11 12 S f(wx)) - 7x(1 - 5)][1x 12 +
L (1 8)2 1 112
Rearranging, we have
L G2
[V < (1
- ( - ( f(w++1)]
2(1 (11-0) 8)
Summing from k 1 T. multiplying by 1/T, and noting that 7 is constant, we have
[f(w]] - f(WT+1)] Ly 6) min [f( < In (1 6)1-
T
2(1 -2- 6)
Because f(wr+1) 2 f(w") and 71 = D11((111111111111111 + 8JGTT] we have
min minl/ (1 5)]
[f(w]] f(ww)] + [m + G2?G2
(1+8)LGD) 2(1-
T
(1 (1-5)VT
which concludes the proof.
15

---

Under review as a conference paper at ICLR 2020
A.9
PROOF OF THEOREM 7
Theorem 2.2 of Friedlander & Schmiidt (2012) states that when the gradient error
llg. hu 0g for all
k 2 1.
(16)
inequality L4 holds. It remains to show that the probability that (16 happens is at least
The assumption on the sample size N2 means that
Cpc-Ner - S <//T.
Then, substituting dg h into assumption 6 yields
Pr [199x - hull 2 dR .1...... S Ose Cae NeT(6e/lbbl)) S e/TT.
Hence, the probability that (16) happens is
T .k-1
II
Pr [190 hxll 2 ox 91. g1......k
which concludes the proof.
B EXPERIMENT DETAILS
B. THE "MIXTURE" DATA SET
The data set is Gaussian mixture with components in d dimensions. The components
N (H, I) with μl = [-0.5, 0]. σ1 = 0.75, μ/ 00.5, 0), d2 0.5, μı = [0. 0.866). and Tg = 0.25 equally weighted but significantly overlap with each other. Random connections made between every pair of points. For points in the same component, the probability that they are connected is Pinta e: for points straddle across components, the probability is Pinter 2e-4. See Figure a) for an illustration of the Gaussian mixture and Figure bb) for the graph adjacency matrix.
7000
2000
45
4.5
5000
0000
-389
(a) Overlapping Gaussians
(b) Adjacency matrix
Figure 4: The "Mixture" data set (input features and graph).
B.2 SUMMARY OF DATA SETS
See Table 2 for summary of the data used in this work.
16

---

Under review as a conference paper at ICLR 2020
Table Data sets.
Mixture
Cora
Pubmed
# Nodes
6,000
2,708
19,717
Edges
16,709
5,429
44,338
# Classes
3
7
3
Features
1,433
500
# Training
2,400
1,208
18,217
Validation
1,200
500
500
Test
2,400
1,000
1,000
Table 3: Hyperparameters for different GCN architectures and training algorithms.
(a) I-layer GCN
Mixture
Cora
Pubmed
Batch size
256
256
256
Regularization
0
SGD learning rate
1et0
1et3
1et3
Adam learning rate
1e-2
1e-1
1e-1
(b) 2-layer GCN
Mixture
Cora
Pubmed
Batch size
256
256
256
Regularization
0
0
Hidden unit
16
16
SGD learning rate
1e+0
1e+2
le+1
Adam learning rate
1e-2
1e-1
1e-1
B.3 (HYPER))ARAMETER
See Table 3 for the hyperparameters used in the experiments. For parameter initialization, we use the Glorot uniform initializer (Glorot & Bengio 2010).
B.4 RUN TIME
See Table for the run time (per epoch). As expected, 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.
Table 4: Time per epoch in seconds.
1-layer GCN
2- GCN
Mixture
Cora
Pubmedd
Mixture
Cora
Pubmed
SGD (400)
0.0035
0.0269
0.1991
0.0103
0.0868
2.5014
SGD (800)
0.0018
0.0455
0.3554
0.0103
0.0974
2.5684
SGD (1600)
0.0027
0.7129
0.0142
3.2032
SGD (3200)
1.1847
3.8895
SGD unbiased
0.0044
0.0737
2.2425
0.0130
0.2031
7,9478
Adam unbiased
0.0049
0.0741
2.2313
0.0143
0.2080
7.9037
17


Reviews:
[{"review_id": "S1gLjxYg9H", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.  \n\nThe paper is well written and the results are convincing. I have a few questions/comments\n\n1. In all the experimental results the loss curves are shown w.r.t. the number of epochs. It is clear that using unbiased SGD, unbiased ADAM is better of than using biased SGD. However, these plots do not tell the complete story as the key point behind using consistent SGD is not achieving lower loss, but actually faster computation. I would suggest that the authors show run-time plots that show how the run-time scales with epochs.\n\n2.  I appreciate the authors efforts in explaining their assumptions and how different assumptions kick in. \n\n3. I wonder if a similar methodology can be applied even to the case of ranking problems (say rank net, see reference below). In ranknet training proceeds via  choosing a pair-of-documents and performing gradient updates w.r.t. the pair. However, if one were to pick a single document, the gradient update w.r.t. that document (d1) should involve all other documents (d2) that are less relevant than d1. My question is does applying the consistent gradient methodology in this paper reveal a new algorithm for training ranknets? ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "ByelWUL8qS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The analysis of the convergence of SGD with biases gradient estimates dates back to Robins&Monroe, but the authors of this paper focused on a recent original algorithm that shows that once can estimate the approximate gradient of a large GNN network, simply by sampling nodes randomly.\n\nWhen I first read of the paper, I was enthusiastic because I did not know the FastGCN approach presented at ICLR the previous year, which showed that the gradient of a GCN could be efficiently approximated by sampling a subset of the nodes. After reading FastGCN, I was less enthusiastic as most of the originality relied on the consistent estimate of the gradient, when t (number of sampled in the neighbours of the output nodes) increases.\n\nThe main contribution of the paper is the proof that the algorithm converge, but there is no theoretical analysis of the key quantity \"t\", which is the number of sampled nodes in the neighbours of the output nodes. I would expect to see the number of sample grow as the algorithm converge to the optimal solution since the gradient needs less bias when the algorithm converges. However, the authors do not address this point.\n\nI did not into the details of the proofs, but it seems to me that they are quite loose and several details such as the functional spaces, and the boundedness assumptions, are not mentioned. Here are few examples:\n- In the first sentence: P(x, y) of data x and associated label y. The space of x, the space of y and the probability space are not defined. In fact, no set in which variables belong is defined in the paper.\n- The Theorem 1 is strange to me. I would assume that one needs some assumption of boundedness of Q and finite moments for P to avoid pathological examples where the integral (for the asymptotic expectation) is infinite, but the finite sum G_{st} is always finite, contradicting the limit in theorem 1. \n\nOverall, while proving that the FastGCN algorithm is consistent is important, it is hard to understand how useful the results are and how they can be useful in practice. For example, what can we interpret or what can we learn from the bounds given by Theorem 2?\n\nFinally, I might miss something, but the empirical results showed do not seem to show better gains than the Adam algorithm. The theory shows that the more bias we have, the less accurate we should be, why isn't it apparent in Table 1. Is there something such as the computational cost of Adam, that I'm missing, especially when looking at the graphs? I'm sorry if I did not get the main message of the experiments, but even after reading the paper 3 times, I did not understand what the authors wanted the reader to conclude with these experiments.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "ByejMHG6FS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nOverall, the paper is well-motivated and well-written however it lacks technically novelty. Under the assumption of exponentially fast convergence to small error, the setup is more like gradient descent (have access to approximate full gradient) than stochastic gradient descent as the paper supposes. The main convergence theorems seem to follow from standard techniques for inexact/noisy gradients. In [1], convergence rates for various first-order methods are proven under the assumption that the error is additive, that is, ||g - h|| <= \\delta. Since the authors implicitly convert the multiplicative error to an additive error in their analysis, their assumptions are comparable to [1]. Also, since the analysis is more like GD, in the strongly-convex setting one can actually get faster convergence rates (logarithmic) as long as \\delta is small (in comparison to the strong convexity parameter) unlike the O(1/T) ones mentioned in the paper.\n\nAdditional comments:\nAssumption - There should be an additive error along with the multiplicative error as in the current setup. If ||h|| is very small then according to the assumption, the estimates of the gradient are very tight; this may not be true. Also, this assumption seems to only be needed for sample complexity purposes, making the tails weaker would only give a larger sample complexity without affecting the convergence rates. Would be good to separate these.\n\nConvergence Analysis - As mentioned above, since the setting is like GD with noisy gradients, a more careful analysis in the strongly convex setting can improve the convergence result. Refer [2] for the standard analysis without noise. \n\nUpper bound on l -  In Thm 2, the authors assume l <= G/||w_1 − w^*||. Why is this needed? Increasing l should make the problem more convex and easier.\n\n[1] Devolder, Olivier, François Glineur, and Yurii Nesterov. \"First-order methods of smooth convex optimization with inexact oracle.\" Mathematical Programming 146, no. 1-2 (2014): 37-75.\n[2] Robert M. Gower. Convergence Theorems for Gradient Descent. https://perso.telecom-paristech.fr/rgower/pdf/M2_statistique_optimisation/grad_conv.pdf", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "Bkx-GC8K5B", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper aims to solve the stochastic optimization problems in machine learning where the unbiased gradient estimator is expensive to compute, and instead use a consistent gradient estimator. The main contributions are the convergence analyses of the consistent gradient estimator for different objectives (i.e., convex, strongly convex, and non-convex). Overall, it is interesting and important, but I still have some concerns.\n\nWhich objective function do the authors aim to minimize, the expected risk or empirical risk? I guess it's the empirical risk, right? If so, the sample size $N$ is constant. This may break the condition (sufficiently large sample sizes satisfying (6)) of theorems (i.e., Theorem 2, 3, 4, 5). Thus, it will narrow the application domains of the theorem.\n\nFor the proofs of theorems, the main difference between SGD and this paper is the involvement of Lemma 9, which is one part of the assumption. Besides, this assumption involves the failure probability $\\epsilon$. The convergence theorem (e.g., Theorem 2) has a probability condition to hold the Eq.(7) (or (8)). Maybe some comments below the theorem can be discussed to decrease $\\epsilon$, although authors discuss it in experiments (\"This phenomenon qualitatively agrees with the theoretical results; namely, larger sample size improves the error bound.\").\n\nFor the experiments, the authors focus on the training of GCN model. I think it can be considered a doubly stochastic sampling process, which is one for the sample and the other for its neighbor. Is that right? Besides, for Figure 1, can the \"SGD unbiased\" be viewed as \"SGD consistent (sampl $n$)\"? If not, I think it's important to compare these two because this will clearly show the performance difference between the unbiased and consistent estimator.\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper analyzes the convergence of SGD with a biased yet consistent gradient estimator. The main result is that this biased estimator results in the same convergence rate as does using unbiased ones. The main application is on learning representations on graphs (e.g., GCNs), and FastGCN is a closely related work. I agree that this paper has valuable contributions, but it can be further strengthened by considering the review comments, such as on the key assumptions.
Decision: Reject