Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: 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.

Which 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.

For 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.").

For 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.

review_title: Official Blind Review #4

final_score: rating: 3: Weak Reject
review_content: 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.

When 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.

The 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.

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

Overall, 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?

Finally, 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.

review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: 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 is well written and the results are convincing. I have a few questions/comments

1. 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.

2.  I appreciate the authors efforts in explaining their assumptions and how different assumptions kick in. 

3. 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? 
review_title: Official Blind Review #1

final_score: rating: 1: Reject
review_content: 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.

Overall, 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.

Additional comments:
Assumption - 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.

Convergence 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. 

Upper 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.

[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.
[2] Robert M. Gower. Convergence Theorems for Gradient Descent. https://perso.telecom-paristech.fr/rgower/pdf/M2_statistique_optimisation/grad_conv.pdf
review_title: Official Blind Review #2

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