Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies decentralized stochastic compositional optimization problem, and proposes two algorithms: GP-DSCGD and GT-DSCGD. They also have convergence guarantee for both algorithms. This problem has significant application in model agnostic meta learning. 

main_review: The problem studied in this paper has significant application in large scale distributed meta learning, so I think this work has nice results except issues discussed below. As far as I know, this paper is the first to study decentralized stochastic compositional optimization, and provide analysis. From my point of view, it is novel. The theoretical analysis looks sound as far as I checked. The theoretical results are supported through experiments. The paper is well-organized and both experimental and theoretical results are clearly presented.

limitations_and_societal_impact: If my understanding is correct, the gradient tracking based algorithm has the same convergence rate with GP-DSCGD, then I was left wondering what would be its significance.

Also, I notice that we need a fairly large batch size $\sqrt{KT}$ to guarantee the convergence and appreciate clarification from authors.  In particular, is it due to the decentralized setting, or the single machine version of the algorithm also needs a large batch size?
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposed two decentralized training methods for stochastic compositional optimization problem and establish the convergence results for them.

main_review: This paper introduces the decentralized training methods to solve the stochastic compositional optimization. Although I don’t get into the whole proof, the techniques used in this paper are fairly standard and the analysis is technically sound. My main concern is the significance of this paper. 

Minor Comments:

1. I suggest the authors replace the ‘fast training methods’ in the title with e.g.’decentralized training’ as this is a paper on the decentralized training, rather than accelerating the convergence (on single machine).

2. Please formalize the definition of $g$ and $f$. Note that the $f$ and $g$ in (1) depends on some random variable, but are deterministic functions in (2) and some parts hereafter.

3. Should it be better to denote the difference of $f^{(k)}$ and $g^{(k)}$ in (4) by the difference of the corresponding random variables? This means the difference are induced by different batch of data that are sampled according to the random variables, which avoid some potential ambiguity. Note that in (3) the authors use some similar notation. I feel the current notations mean that each device have different $f$ and $g$.

4. I would like to ask what’s the relation of the analysis in this paper and analysis of smooth SCGD and smooth distributed SGD. It would be better to illustrate the technical significance beyond the direct combination of the previous work. Specifically, given that the gradient variance are bounded, it’s not so hard to derive Lemma 14 that replace $s_t$ with $h_t$ as emphasized in Line 201-209. It would be more interesting if there’s other technical insight in this paper.

5. For experiments, I think the convergence rate with different $K$ is necessary, as the authors argue it as a main contribution.

I tend to accept this paper, but due to the concern on the technical significance, I would rather assign a conservative score for it.

limitations_and_societal_impact: The authors have properly addressed them.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the stochastic compositional optimization problem under the distributed learning setting. Two decentralized optimization methods are proposed for solving this problem, both of which are based on SCGD method. Theoretical analysis is conducted to provide convergence bound for both methods. Experiments are also carried out accordingly.
main_review: After rebuttal:
The authors' clarification about the overall complexity of the algorithm seems reasonable to me. I decided to raise the score. Hope these discussions about the algorithm complexity can be combined into the final version.

=====================================================

My main concern about this paper is that the theoretical bounds are not well discussed and compared with existing methods.

It is only mentioned in the paper that the number of iterations required by the proposed methods is $T=O(1/(K\epsilon^2))$, the same as decentralized SGD. But according to Corollaries 1 and 3, the proposed methods use the batch size $B=O(\sqrt{KT})$, which depends on the number of nodes $K$ and the number of iterations $T$, while decentralized SGD only needs batch size 1. So, it is unfair to directly compare the number of iterations. The overall computation complexity, which takes both factors into account, should be discussed and compared with decentralized SGD and the single-machine SCGD to see if the proposed methods really have linear speedup and optimal convergence rate.

The values of the hyperparameters used in the experiments are not mentioned. Especially for the batch size, is the theoretically optimal batch size $B=O(\sqrt{KT})$ used here, or just set $B=1$? Also, the batch size of the baseline should also be clarified.

Besides, I guess there are some typos or errors in the convergence analysis part. What is $\beta$? Is it $\beta_t$ is the algorithm? I also failed to locate the term $1/(2\eta L_F)$ mentioned in Remark 2.

One more suggestion: since this paper focus on distributed optimization, it is better to reflect this in the title (though I am not sure if the title can be modified in this stage).
limitations_and_societal_impact: N/A.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper presents two algorithms for distributed optimization of stochastic composite objectives where one is interested in optimizing one outer objective that is computed on points that depend on another function (called the inner objective in the paper).
The authors adapt two strategies for distributed optimization to the stochastic composite optimization problem and derive convergence rates for the general non-convex outer objective problems, that show linear rates w.r.t. the number of devices used (this is probably the main contribution of this paper).
Finally, they present a set of experiments in meta-learning using MAML as meta-learning algorithm.
main_review: Clarity: 
The paper is well written and generally clear. Few exceptions are: 
- missing definition of the non-stochastic versions of g and f, used, for instance, in Eq. (2). I interpret these to be $\mathbb{E} f$ and g, but this should be clarified.
- perhaps, more importantly, I find a discussion on the limit case where K=1 (i.e. only one device) missing. How do the algorithms read in this case? and, what are the similarities/differences with [14]? 
- one case where composite functions emerge in machine learning is bilvel optimization (not limited to the MAML setting). In bilevel optimization typically the term ''inner objective''/inner function is reserved to the (scalar-valued) objective of the inner problem. In this work, $g$ essentially maps to the argmin operator, which is in general not necessarily a function (could be multiple minimizes). I think it would be appropriate to include a brief comment on this after the authors introduce the main assumptions, perhaps also linking to some recent works on stochastic bilevel optimization, e.g. [1].

Originality and significance:
The work seems original and significant to me, as the methods proposed may be applied to many problems of interest in ML, especially in meta-learning. However, I am not particularly an expert in the field of distributed optimization, so cannot evaluate properly this point.

Quality: 
The derivations seem correct to me, although I have not checked carefully the supplementary material.
- One main concern that I have about this work is that I think there is a disconnect between the theoretical results and the experimental section. Specifically, as the authors claim that one main contribution of the paper is about showing linear rates w.r.t. the number of devices, I would have expected some empirical results in this regard. Instead, all the experiments are conducted with only 4 devices, which makes it impossible to appreciate this aspect of the paper. This point should be address in the rebuttal, ideally with some empirical result.

Typos:
- L80 (the) 
- L88 (of) 

[1] Grazzi, Riccardo, Massimiliano Pontil, and Saverio Salzo. "Convergence properties of stochastic hypergradients." International Conference on Artificial Intelligence and Statistics. PMLR, 2021.

____
Post-rebuttal:

Thanks for your reply! I am raising my score and suggest acceptance. 
limitations_and_societal_impact: Not applicable
review_title: null

Meta-review: This paper considers the Stochastic Compositional Optimization on the decentralized training setting, which is an interesting and novel problem, as recognized by reviewers. A decentralized stochastic compositional gradient method is proposed. The proved convergence rate is provided as well. Most reviewers' comments have been addressed. Although we decide to accept this paper, authors should realize that this rate is not tight, comparing to the special case (single machine), which should be explicitly pointed out in the revision.
Decision: Accept (Poster)