Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: The paper proposes a variance reduction based algorithm to solve compositional problems. The idea comes from the stochastically controlled stochastic gradient (SCSG) methods. The paper applies the idea from SCSG to estimating the inner function G(x) and the gradient \nabla f_k to solve compositional problems. The paper provides a theoretical analysis of the query complexity of the algorithm in both convex and non-convex setting. The experiments show the performance of the proposed algorithm is better than other recent methods. The paper seems to be the first attempt to extending stochastically controlled functions to the compositional problems. However, I vote for rejecting this submission for the following concerns. (1) Since SCSG is a member of the SVRG family of algorithms, the difference between this paper and [Xiangru Lian, Mengdi Wang, and Ji Liu, 2017] is not significant enough, especially in the algorithm design and the proof of the theoretical theorem. (2) The formulation of the compositional problems comes from reinforcement learning, risk-averse learning, nonlinear embedding, etc. However, the experiments are only performed on nonlinear-embedding problems. I think performing the experiments on different kinds of problems will be helpful to justify the significance.
review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: This paper proposes a new method for empirical composition problems to which the vanilla SGD is not applicable because it has a finite-sum structure inside non-linear loss functions. A proposed method (named SCCG) is a combination of stochastic compositional gradient descent (SCGD) and stochastically controlled stochastic gradient (SCSG). In a theoretical analysis part, a linear convergence rate and a sub-linear convergence rate are derived under the strong convex and non-convex settings, respectively. In experiments, the superior performance of the method to competitors is verified on both strongly convex and non-convex problems.

Clarity:
The paper is clear and well written.

Quality:
The work is of good quality and is technically sound.

Significance:
The problem treated in this paper is important and contains several applications as mentioned in the paper. Hence, developing an efficient method for this problem is important and interesting. Although derived convergence rates are better than existing primal methods, this paper lacks a comparison with the recently proposed primal-dual method by [A.Devraj & J.Chen (2019)].

[A.Devraj & J.Chen (2019)] Stochastic Variance Reduced Primal Dual Algorithms for Empirical Composition Optimization. NeurIPS, 2019.

A convergence rate obtained in [A.Devraj & J.Chen (2019)] seems faster than that of SCCG for ill-conditioned strongly convex problems. However, there exists a certain setting (large-scale setting) where SCCG outperforms their method. Thus, the contribution of the paper is not lost, but it is better to compare SCCG with the method in [A.Devraj & J.Chen (2019)], empirically and theoretically.
If the authors can show an empirical advantage over their method, it will make the paper stronger.

-----
Update:
I thank the authors for the response and hard work. I am convinced of the advantage of the proposed method. I would like to keep my score.
review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: In the paper, the authors consider composition problems and use the stochastically controlled stochastic gradient method (SCSG) to approximate the gradient G(x) and \nabla f(x). The authors also provide convergence analysis of the proposed method for strongly convex problems and non-convex problems. Authors then conduct experiments on the
mean-variance optimization in portfolio management task and the nonlinear embedding problem, results show that the proposed method is faster. 

The following are my concerns:
1) There are several important related works missing in the paper, e.g., [1][2].  
2) The convergence results of the proposed method in the paper are not state-of-the-art. For a strongly convex case, the result in the paper is O( n+ k^2 min(n, 1/u^2) log1/e), it is not necessarily better than O(n+k^3 log 1/e) in [1] or O(n+kn^{2/3} log 1/e). For a non-convex case, the result in the paper is O(\min{1/e^{9/5}, n^{4/5} / e}), it  is not necessarily better than O(n^{2/3}/e) in [1] or [2]. 
3) More compared results should be conducted in the experiments, e.g. [1][2]. 

[1]Huo, Zhouyuan, et al. "Accelerated method for stochastic composition optimization with nonsmooth regularization." Thirty-Second AAAI Conference on Artificial Intelligence. 2018.
[2] Zhang, Junyu, and Lin Xiao. "A Composite Randomized Incremental Gradient Method." International Conference on Machine Learning. 2019.


review_title: Official Blind Review #3

Meta-review: All the reivewers find the similarity between this paper and the references in terms of the algorithm and the proof. The theoretical results may not better than the existing results.
Decision: Reject