Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: This paper provides a convergence analysis for asynchronous optimisation in the case where non-smoothness imposes the use of sub gradients and non-convexity (combined with asynchrony) introduces more challenging staleness (delay) issues than in the convex case.

strength:
the paper tackles one of the hardest settings to be analysed in distributed optimisation, and packages it in a readable continuous-time framework.

weakness: 
as far as I went into the details, I couldn't understand how the authors tackle one the biggest problem in non-convex + asynchrony: coherence of gradients. 

Specifically, my sole question to the authors is how does their analysis take into account (sub)gradients that are delayed *and* not in the same half-space as the current non-biased estimator of the gradient ? These (sub)-gradients will act in an almost malicious manner. (as usual in distributed computing, where asynchrony can be modelled by a malicious scheduler).
Maybe my reading made me miss where this is handled, if a precise pointer is given I will upgrade my score.
review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: This paper proposes a model to study asynchronous stochastic subgradient methods for minimizing a nonsmooth nonconvex function. Studying stochastic subgradient methods in the nonsmooth nonconvex setting is already very challenging. Throwing asynchronous updates into the mix further complicates the analysis. This is overcome by proposing a model for asynchrony which captures the salient features of computation platforms, while being amenable to analysis.

The main drawback of this paper is that the experiments seem to suggest that, although asynchronous methods do a good job optimizing training metrics (loss, accuracy), the models they train do not generalize as well as using synchronous SGD. This demotivates the need for the theory developed in this paper - rather, the theory is ahead of it's time. The paper could be significantly strengthened by reporting an example application where using an asynchronous stochastic subgradient method is advantageous for training deep networks.

The notation and discussion in Sec 3.1 is pretty heavy. Can you explain how this model differs from other models of asynchrony, e.g., as put forward in the well-known book by Bertsekas and Tsitsiklis on Parallel and Distributed Computation?

The main convergence result (Theorem 1) holds for a continuous-time process, following the typical analysis of stochastic approximation algorithms. However, practitioners rarely use a diminishing step size, especially for training deep networks. Is it possible to quantify the effect of using a constant step size? (E.g., in stochastic approximation analyses for smooth functions, one typically gets a "law of large numbers" which ensures convergence of the average, and a "central limit theorem" which bounds the distance of any realization of the process to its mean. Is there an analogous CLT for this setting?)

In the experiments, the SGD with DataParallel is effectively using a mini-batch size that is 3-5x larger than that of a single worker. In this case one would expect to be able to use a larger learning rate too (since there is less noise). Evidence for this is provided in Goyal et al., "ImageNet in 1 hour". Did you try tuning the learning rate separately for each method?

How were the parameters of the deep CNNs used in the experiments divided into blocks? This choice should affect the average time to evaluate a block gradient, right? Computing the gradient of parameters in the lowest layer requires doing a full forward and backward, while computing the gradient of higher layers should be faster since it doesn't require a full backward pass. Did you measure the average time to compute a block gradient, and could you report it in the paper? Did you divide into blocks based on layer? Are all parameters within the same block part of the same filter at a given layer?

The last paragraph of Sec 4 talks about the necessity of momentum, but it isn't clear what evidence this claim is based on.



review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: This paper analyzes convergence of asynchronous methods on general non-smooth and non-convex functions (typically arising from deep leaning). Stochastic sub-gradient asynchronous methods are of particular challenging when coupled with complicated hardware behavior of modern NUMA architecture. To validate the analysis, and study the impact of momentum, variable partitioning, numerical experiments on deep learning training are given.

A major concern to me is that the assumptions made in the analyze may be too restrictive. For example, Assumption 3.1.1 regarding the unbiasedness of the stochastic sub-gradients may not hold for since the Clarke sub-differentiation is not additive. The Clarke sub-differentiation of |x| and -|x| are not included in their average which is zero, therefore the Assumption 3.1.1 is not true for tame functions (as cited in the paper) . If this assumption were not true, all the proof arguments based on Martingale differences may not be follow to prove Theorem 3.1. 

There are a few typos which make the paper hard to understand. Is the momentum variable  u_i^kc in Algorithm 1 a central variable, as x_i? It seems to be yes since the update needs a lock. But why there is an kc on its index, which is not the case for x_i? 

In terms of numerical results, the system specification is not so clear to me why it includes a diverse asynchronous system settings. Even though Figure 1 shows convergence in terms cross-entropy loss, which is not directly related to validate Theorem 3.1 since it is not clear what is going on with x_t.

The paper would be of great interest if the global shared memory asynchronous model is made more precise in the main body of the paper. At a first glace, it is not clear what is the benefit (or what insights) using this model to analyze these algorithms, compared to simplistic models in literature. 
review_title: Official Blind Review #3

Meta-review: This paper considers an interesting theoretical question. However, it would add to the strength of the paper if it was able to meaningfully connect the considered model as well as derived methodology to the challenges and performance that arise in practice. 
Decision: Reject