Accelerating Stochastic Composition Optimization
Consider the stochastic composition optimization problem where the objective is a composition of two expected-value functions. We propose a new stochastic firstorder method, namely the accelerated stochastic compositional proximal gradient (ASC-PG) method, which updates based on queries to the sampling oracle using two different timescales. The ASC-PG is the first proximal gradient method for the stochastic composition problem that can deal with nonsmooth regularization penalty. We show that the ASC-PG exhibits faster convergence than the best known algorithms, and that it achieves the optimal sample-error complexity in several important special cases. We further demonstrate the application of ASC-PG to reinforcement learning and conduct numerical experiments.
The paper extends the accelerated SCGD algorithm in [Wang et.al, 2016] with proximal setting to handle nonsmooth regularization, and present refined convergence results in some cases. Some experiment is conducted on reinforcement learning on small synthetic dataset. 
First of all, the novelty and originality is a big concern.   - Most elements are inherited from an early journal paper [Wang et.al, 2016], including the motivation example, the accelerated algorithm itself, results for strongly convex case, and application to dynamic programming.    - The only novelty of the paper is to extend ASCG to proximal setting, which however, is quite trivial. Not to mention the fact that,  the main Theorem 1 assumes no nonsmooth penalty term. So literally, this paper has not really done what they claimed - address nonsmooth regularization penalty without deteriorating the convergence rate.    -The "optimally" strongly convexity condition is not substantially different from strongly convexity. Theorem 2 is more or less just a repetition of Theorem 7 in [Wang et.al, 2016], except with a slightly more general choice of learning rate.   Overall, I don't feel the paper has a substantial contribution.    Secondly, several statements are confusing and could be misleading.   1. The authors claim that the inner and outer random variables w, v can be dependent, but assumes unbiased stochastic oracles given in Assumption 1.1. This seems to be a contradiction, if (w,v) are dependent, then Assumption 1.1 might not be possible. So it feels like the algorithm is limited to independent (w,v). Due to this same reason, the proposed algorithm might not handle the motivating example,  risk-averse learning, since the inner and outer random variables are the same.  2. Somehow the two motivating examples cannot be directly or explicitly reformulated to the form (1). I would suggest the authors to provide some details here on what are the exact functions f, g.  Also, the reformulation (3) does not look quite right to me.   3. In theorem 1, the convergence criterion (taking average of gradient norms) is not common nor expressive enough to imply the rate. It would be more useful to see directly how the gradient of the last iterate converge to zero. Since the criterion used here is different from [Wang et.al, 2016], it is not very appropriate to compare the rates or claim any kind of improvement.    Thirdly, the applicability of the proposed algorithm in reinforcement learning seems quite limited.    - In order to  translate the Bellman residual minimization problem into (1), an extra O(S) inner expectation terms needed to be introduced, which does not look very elegant. Also, this implies that the proposed algorithm can only handle finite state MDP with reasonably small number of states. As shown in their experiments, the largest instance  has only 100 states.   - For the interest of machine learning community, results on real and large-scale datasets should be provided.   Lastly, here are some minor issues.   1. The authors claim that the objective function (3) is optimally strongly convex and later use it in experiments,  so either proof or references should be provided.  2. In Experiment 1 and 2, there is no nonsmooth penalty, so the proposed ASC-PG algorithm is almost nothing different from the ASC-GD algorithm except with a smarter choice of learning rate. The authors should clarify this when making the comparison. In Experiment 3, it also makes sense to compare to the proximal extension of GTD2-MP algorithm.   3. The following reference, also provides a O(1/t) convergence rate for stochastic composition problems when inner function is linear. The authors might want to provides some discussion on the algorithmic differences.  Dai, Bo, et al. "Scalable kernel methods via doubly stochastic gradients." Advances in Neural Information Processing Systems. 2014.  4. Line 139: function F(x) is not defined until in line 144.    5. Line 53:  nonlinearity in distribution of v. Shouldn't it be w?  6. Line 228: ||w_k-w^*||=O(1/k) missing square?