Year: 2019

Abstract:
We consider composition problems of the form 1 n ∑n i=1 Fi( 1 n ∑n j=1Gj(x)). Composition optimization arises in many important machine learning applications: reinforcement learning, variance-aware learning, nonlinear embedding, and many others. Both gradient descent and stochastic gradient descent are straightforward solution, but both require to compute 1 n ∑n j=1Gj(x) in each single iteration, which is inefficient-especially when n is large. Therefore, with the aim of significantly reducing the query complexity of such problems, we designed a stochastically controlled compositional gradient algorithm that incorporates two kinds of variance reduction techniques, and works in both strongly convex and non-convex settings. The strategy is also accompanied by a mini-batch version of the proposed method that improves query complexity with respect to the size of the mini-batch. Comprehensive experiments demonstrate the superiority of the proposed method over existing methods.

text: We consider composition problems of the form 1n ∑n i=1 Fi( 1 n ∑n j=1Gj(x)). Composition optimization arises in many important machine learning applications: reinforcement learning, variance-aware learning, nonlinear embedding, and many others. Both gradient descent and stochastic gradient descent are straightforward solution, but both require to compute 1n ∑n j=1Gj(x) in each single iteration, which is inefficient-especially when n is large. Therefore, with the aim of significantly reducing the query complexity of such problems, we designed a stochastically controlled compositional gradient algorithm that incorporates two kinds of variance reduction techniques, and works in both strongly convex and non-convex settings. The strategy is also accompanied by a mini-batch version of the proposed method that improves query complexity with respect to the size of the mini-batch. Comprehensive experiments demonstrate the superiority of the proposed method over existing methods.

heading: 1 INTRODUCTION
text: In this paper, we study the following composition minimization problem,
min x∈RN
{ f(x) def = F (G(x)) def = 1
n n∑ i=1 Fi
( 1
n n∑ j=1 Gj(x)
)} , (1.1)
where f : RN → R is differentiable and possibly non-convex, each Fi: RM → R is a smooth function, each Gi: RN → RM is a mapping function, both the numbers of Fi’s and Gj’s are assumed to be n for simplicity We call G(x):= 1n ∑n j=1Gj(x) the inner function, and F (w):= 1 n ∑n i=1 Fi(w) the outer function. Many machine learning problems can be cast as composition problems that include two finite-sum structures: reinforcement learning (Sutton et al., 1998; Wang et al., 2017; Liu et al., 2016), variance-averse learning (Lian et al., 2017), and nonlinear embedding (Hinton & Roweis, 2003; Dikmen et al., 2015). In particular,
• (reinforcement learning) The S × S system of Bellman equations Wang et al. (2017) can be written as minx∈RS ‖E[B]x− E[b]‖2, where E[B] = I − γPπ , γ ∈ (0, 1) is a discount factor, Pπ is the transition probability under policy π, and E[b] is the expected state transition reward. This is one of key problems in reinforcement learning for evaluating the value of a policy π.
• (risk-averse learning) The risk-averse learning Lian et al. (2017) aims to maximize the expected return while control the variance (or risk) in the meantime:
minx − Ea[h(x; a)] + λVara[h(x; a)], where h(x; a) is the loss function including a random variable a, λ > 0 is a regularization parameter.
• (nonlinear embedding) Stochastic nonlinear embedding Hinton & Roweis (2003) aims to map a group of points from a high dimensional space to a low dimensional space by minimizing the KL divergence. It is a non-convex composition optimization
minx ∑ t KL(p·|t ‖ q·|t) := ∑ t ∑ i pi|t log pi|t qi|t , (1.2)
where pi|t and qi|t are the conditional probabilities w.r.p. {zi}ni=1 and {xi}ni=1,
pi|t = d(zt,zi)∑ j 6=t d(zt,zj) , qi|t = d(xt,xi)∑ j 6=t d(xt,xj) ,
where d(·, ·) is the dissimilar distance function between two samples.
To solve the composition optimization including the finite-sum structure in (1.1), two most straightforward approaches are the gradient descent (GD) and the stochastic gradient descent (SGD). However, it is extremely expensive to scan all the inner functions (for both SGD and GD) as well as all the outer functions (for GD) in each iteration. However, note that, unlike solving common stochastic optimization problems, randomly sampling one inner function and one outer function does not give an unbiased estimate for the true gradient; that is, Ei∼[n],j∼[n][(∂Gj(x))T∂Fi(G̃(x))] 6= ∇f(x), where G̃(x)is the estimation of G(x). The key to solving this composition objective is how to estimate the value of G(xk) and its Jacobian with high accuracy using only a few samples in each iteration.
Recently, many stochastic optimization methods solving the composition problem have been developed, such as the stochastic gradient based method and the variance-reduction based method. For example, stochastic compositional gradient descent (SCGD) (Wang et al., 2017; Liu et al., 2016) estimates the inner function G(x) by using an iterative weighted average of the past values of G(x), and then performs the stochastic quasi-gradient iteration. The advantage of this method is that convergence rate does not depend on n; however, it queries more samples to the desired point. Another set of approaches is based on variance reduction – for instance, compositional stochastic variance reduction gradient (Compositional-SVRG) (Lian et al., 2017) estimates the inner function G(x) and the gradient of function f(x) by using the variance reduction technique; however, the derived linear convergence rate is related to n. Motivated by a few recent works (Lei & Jordan, 2017; Lei et al., 2017; Allen-Zhu, 2017) that focus on the stochastically controlled gradient, we were inspired to look for a way to improve the query complexity and reduce the dependence on n to solve the composition optimization in (1.1).
Hence, this paper presents a novel and more efficient method named stochastically controlled compositional gradient (SCCG) for solving composition problems involving a two-finite-sum structure. The result is improved query complexity over existing approaches. Further, all results in this paper can be easily extended to cases where the number of Fi and the number of Gj are different. The main contributions of this article are summarized below.
• We provide a stochastically controlled function to estimate the inner function G(x). Inspired by stochastically controlled stochastic gradient (SCSG) (Lei & Jordan, 2017) that estimates the gradient, G(x) can also be estimated by using a snapshot x̃s, in which G(x̃s) is not computed directly, but is estimated through a random subset from [n]. This is the first time that a stochastically controlled function has been incorporated into the process of estimating the inner function. We have also analyzed how the size of the subset might influence the query complexity for both strongly convex and non-convex functions.
• We provide a stochastically controlled compositional gradient to estimate the∇f(x). However, there are two potential situations that could be encountered in the estimation process that can impede convergence. First, the expectation of the gradient is no longer an unbiased estimation; and, second, the gradient of f(x̃s) at the snapshot is formed by two random subsets, which are used for the functions Fi and Gj respectively. Moreover, the biased gradient bring more difficulty in proving the convergence, which are greatly different from those encountered in (Lei & Jordan, 2017; Lian et al., 2017; Lei et al., 2017). To address these scenarios, we have identified a bound on the size of the subsets that are used to estimate the gradient. The details of the analysis can be referred to Section 3.1 and 3.2.
• A mini-batch version of the proposed algorithm is also provided for both strongly convex and non-convex functions. The corresponding query complexities are improved according to the size of the mini-batch. More information can be referred to Section 3.3.

heading: 1.1 RESULTS
text: Following the classical benchmark for a general problem, the composition algorithm is also to find a point x satisfying f(x) − f(x∗) ≤ for a convex function, where x∗ is the optimal point in the strongly convex function, and ‖∇f(x)‖2 ≤ for a non-convex function, respectively. The elegance
of a composition algorithm is evaluated based on its query complexity, defined as the number of queries in a given sampling oracle that are needed to compute the gradient. Here, we give the query complexities of the composition problem in Table 1, which offers an insightful comparison to other algorithms.
Strongly convex function The query complexity for the strongly convex function is O((min{n, 1/( µ2)}+ L2f/µ2min{n, 1/µ2}) log(1/ )). The result is the general form for the strongly convex composition and is equal to or better than the query complexity in (Lian et al., 2017) and (Liu et al., 2017a).
Non-convex function The query complexity is O(min{1/ 9/5, n4/5/ }), which is better than the result in (Liu et al., 2016) and comparable to the result in (Liu et al., 2017b).
Mini-batch 1 For the mini-batch version, the query complexity can be improved to some extent, that is O((min{n, 1/( µ2)}+ L2f/(bµ2)min{n, 1/µ2}) log(1/ )). and O(min{1/ 9/5, n4/5/ }/b1/5) for strongly convex and non-convex functions, respectively, which are better than mini-batch variance reduced stochastic compositional proximal gradient method (VRSC-PG) (Huo et al., 2018) and mini-batch Composite SAGA (C-SAGA) (Yuan et al., 2019) when b=1/µ and min {n, 1/ }2/3 for strongly convex and non-convex functions, respectively.

heading: 1.2 RELATED WORK
text: As the amount of data we have at our disposal grows, stochastic optimization has become a popular technique in the realm of machine and deep learning, particularly for optimizing finite-sum functions. The typical algorithms for solving such problems include stochastic gradient descent (Ghadimi & Lan, 2016), SVRG (Johnson & Zhang, 2013; Reddi et al., 2016), stochastic dual coordinate ascent (SDCA) (Shalev-Shwartz & Zhang, 2014; 2013) and the accelerated Nesterov’s method (Nesterov, 2013), accelerated randomized proximal coordinate (APCG) (Lin et al., 2014; 2015) and Katyusha method (Allen-Zhu, 2017). The standard procedure for optimizing a problem with a finite-sum structure is to randomly select one or a block of components to estimate the gradient. However, knowing that the estimated gradient usually has a large variance, the gradient of the function is estimated from a snapshot to appropriately reduce the variance – in other words, the procedure includes a variance reduction mechanism.
Composition optimization problems can also be solved with the above algorithms, but the twofinite-sum structures in composition problems mean that when the gradient of the inner function is estimated directly, the query complexity can substantially increase. Recently, Wang et al. (2017) proposed a method based on first-order SCGD to overcome this issue where the variable and the inner function are updated alternately in two steps. The method has a query complexity ofO( −7/2) for a general function andO( −5/4) for a strongly convex function. Liu et al. (2016) employed Nes-
1b denotes the size of the mini-batch, can be obtained through the η ≤ 1 from Theorem 1 and Theorem 2.
terov’s method to accelerate the composition problem, reachingO( −5/4) andO( −9/4) for strongly convex and non-convex functions, respectively. Ghadimi et al. (2018) proposed a nested averaged stochastic approximation method to find an approximate stationary point within the problem, resulting in a sample complexity of O(1/ 2). However, these methods estimate the inner function using an iterative weighted average of the past function.
The other stream of solutions focuses on variance reduction technology. For instance, Lian et al. (2017) initially applied the SVRG-based method to estimate the inner function G(x) and the gradient of the function f(x), which yields a linear convergence rate. Subsequently, Liu et al. (2017a) and Devraj & Chen (2019) applied a dual-based method to composition problem, which also yields a linear convergence rate. Devraj & Chen (2019) also applied the stochastic variance reduced primal-dual algorithms to composition problem. Yu & Huang (2017) turned to an ADMM-based Boyd (2011) method and provided an analysis of convex functions that do not rely on Lipschitz smoothness. Moreover, Liu et al. (2017b) went a step further and considered non-convex functions, analyzing the query complexity with both inner and outer functions of different sizes. Lin et al. (2018) considered non-smooth convex composition functions, offering an incremental first-order oracle complexity analysis. Zhang & Xiao (2019) and Huo et al. (2018) also provided an randomized incremental gradient method for the composition problem including regularization.
Many recent articles have discussed variance reduction methods that estimate the gradient from a random subset rather than through direct computation. Lei & Jordan (2017), for example, proposed an SCSG method for a convex finite-sum function. They then applied it to a non-convex problem in (Lei et al., 2017) by using less than a single pass to compute the gradient at the snapshot point. Furthermore, Allen-Zhu (2017) proposed the Natasha1.5 algorithm, in which the gradient for each epoch is based on a random subset. Moreover, the objective function has the regularization term. Liu et al. (2018) applied an SCSG based method to the zeroth-order optimization problems with the finite-sum function. Recently, Yuan et al. (2019) applied the stochastic recursive gradient descent method to the composition problem.
The rest of paper is organized as follows: in Section 2, we give preliminaries used for analyzing the proposed algorithm. Section 3 presents the SCSG-based method for the strongly convex and non-convex composition problem and the corresponding mini-batch version. In Section 4, we give the experimental results. We conclude our paper in Section 5.

heading: 2 PRELIMINARIES
text: Throughout this paper, we use the Euclidean norm denoted by ‖ · ‖. We use i ∈ [n] to denote that i is generated from [n] = {1, 2, ..., n}. We denote by (∂G(x))T∇F (G(x)) the full gradient of the function f , ∂G(x) the Jacobian of G, and (∂Gj(x))T∇Fi(G(x)) as the stochastic gradient of the function f , where i and j are randomly and independently selected from [n]. We use A = |A| to denote the number of elements in the set A, and define GA(x) = 1A ∑ 1≤j≤AGA[j](x). We use
E to denote the expectation, that is EA[v] = 1A ∑
1≤i≤A vA[i]. Note that all the variables such as subsets A and B, elements i and j are independently selected from [n], in particular, the element in A and B are independent. So we use E in instead of Ei, Ej ,EA and EB except when explicitly stated otherwise. Recall definitions on Lipschitz function, smooth function and strongly convex.
Definition 1. For function p on X , ∀x, y ∈ X , A function p is a Bp-Lipschitz, that is ‖p(x)− p(y)‖ ≤ Bp‖x− y‖; A function p is a Lp-smooth, that is ‖∇p(x)−∇p(y)‖ ≤ Lp‖x− y‖; A function p is a µ-strongly convex, that is p (y) ≥ p (x)+〈p (x) , y−x〉+µ/2‖x− y‖2.
Through our discussions, we make the following assumptions,
Assumption 1. Let BG, LF and Lf be positive scalars, 2
• Gj is BG-Lipschitz, j ∈ [n], that is ‖Gj(x)−Gj(y)‖ ≤ BG‖x− y‖.
• Fi is LF -smooth, i ∈ [n], that is ‖∇Fi(x)−∇Fi(y)‖ ≤ LF ‖x− y‖. 2In the strongly convex composition problem, the upper bounded Jacobian does not imply that the gradient of f(x) is upper bounded since we do not require the gradient of Fi is upper bounded. Moreover, in the experimental section, we will show that the Jacobian of G(x) is bounded.
• For function Fi(G(x)), there exists a constant Lf satisfying ‖(∂Gj(x))T∇Fi(G(x)) − (∂Gj(y)) T∇Fi(G(y))‖ ≤ Lf‖x− y‖,∀i, j ∈ [n].
• We assume that i and j are independently and randomly selected from [n], z ∈ RM , x ∈ RN , then E[(∂Gj(x))T∇Fi(z)] = (∂G(x))T∇F (z).
Furthermore, we define H1 and H2 are the upper bounds on the variance of G(x) and (∂G(x))T∇F (y), respectively, that is,
1 n n∑ i=1 ‖G(x)−Gi(x)‖2 ≤ H1, 1n2 n∑ j=1 n∑ i=1 ∥∥(∂G(x))T∇F (y)− (∂Gj(x))T∇Fi(y)∥∥2 ≤ H2. In the paper, we denote by xsk the k-th inner iteration at s-th epoch. But in each epoch analysis, we drop the superscript s and denote by xk for xsk. We let x
∗ be the optimal solution of the convex f(x). Throughout the convergence analysis, we use O(·) notation to avoid many constants, such as BG, LF , and Lf , that are irrelevant with the convergence rate.

heading: 3 STOCHASTICALLY CONTROLLED COMPOSITIONAL GRADIENT
text: In this section, we present the variance-reduction based method for the composition problem, which can be used for both the strongly convex function and non-convex function. Before describing the proposed algorithm, we recall the original SVRG (Johnson & Zhang, 2013). The general process of SVRG works as follows. The update process is divided into S epochs, and each of the epoch consists of K iterations. At the beginning of each epoch, SVRG defines a snapshot vector x̃s, and then compute the full gradient ∇f(x̃s). In the inner iteration of the current epoch, SVRG defines the estimated gradient by randomly selecting ik from [n] at the k-th iteration,
(∂G(xk)) T∇Fik(G(xk))− (∂G(x̃s))T∇Fik(G(x̃s)) +∇f(x̃s). (3.1)
However, for the composition problem, there are also variance-reduction based methods in (Lian et al., 2017; Liu et al., 2017a;b). The difference with SVRG is that there is another estimated function for G(x), which also has the finite-sum structure. These methods define the estimated function as
G̃k = GA(xk)−GA(x̃s) +G(x̃s), (3.2)
where A is the mini-batch formed by randomly sampling from [n]. Whereas, as the number of the inner functionGj and the outer function Fi increase, it is not reasonable to compute the full gradient of f(x) and the full function G(x) directly for each epoch.
Extending from the SCSG (Lei et al., 2017; Lei & Jordan, 2017) and Natasha1.5 (Allen-Zhu, 2017), we present a new algorithm SCCG for the composition problem as shown in Algorithm 1. 3 We introduce two subsets D1 and D2, which are independent with each other and randomly selected from [n], respectively. We defineD = D1∪D2 as a new variable, which is important in analyzing the convergence. Firstly, D1 is used for estimating the inner function. Based on the variance reduction technique, the estimated inner function at k-th iteration of s-th epoch is
Ĝk = GA(xk)−GA(x̃s) +GD1(x̃s), (3.3)
where the subset of A is the same as in (3.2). Note that A and D are independent with each other. The difference with (3.2) is that the third term in (3.3) is computed under the subset D1 rather than [n]. Throughout the paper, we assume that |A| ≤ |D1|. Secondly, D2 is used to estimate the outer function F . The key distinguish with (Lei et al., 2017; Lei & Jordan, 2017; Allen-Zhu, 2017) is the biased full gradient of f(x̃s). We define this estimated full gradient of f(x̃s) for each epoch as ∇f̂D(x̃s) = (∂GD1(x̃s))T∇FD2(GD1(x̃s)). Though EA,D[∇f̂D(x̃s)] 6= ∇f(x̃s), we could still estimate the gradient of the f(xk) by
∇f̃k = (∂Gjk(xk))T∇Fik(Ĝk)− (∂Gjk(x̃s))T∇Fik(GD1(x̃s)) +∇f̂D(x̃s), (3.4) 3The parameters’ setting can be referred to Theorem 1 and Theorem 2 for the strongly convex and non-
convex function, respectively.
Algorithm 1 Stochastically Controlled Compositional Gradient (SCCG) for the strongly convex or non-convex composition problem Require: K, S, η , x̃0 and D = D1 ∪ D2, where D1 and D2 are mini-batches.
for s = 0, 1, 2, · · · , S − 1 do Sample from [n] for D times to form mini-batch D1 Sample from [n] for D times to form mini-batch D2 ∇f̂D(x̃s) = (∂GD1(x̃s))T∇FD2(GD1(x̃s)) x0 = x̃s for k = 0, 1, 2, · · · ,K − 1 do
Sample from [n] to form mini-batch A Ĝk = GA(xk)−GA(x̃s) +GD1(x̃s) Uniformly and randomly pick ik and jk from [n] Compute the estimated gradient∇f̃k from (3.4) xk+1 = xk − η∇f̃k
end for Update x̃s+1 = xK , or x̃s+1 = xr, r is randomly selected from [K − 1]
end for Output: x̂sk is uniformly and randomly chosen from s ∈ {0, ..., S − 1} and k ∈ {0, ..,K − 1}.
where ik and jk are randomly selected from [n] at the k-th iteration for functions F and G, respectively. Furthermore, Eij ,jkA,D[∇f̃k] 6= ∇f(xk) as well. This gives us more discussion about the upper bound with respect to the estimated function and the gradient under the new random subset D (more details can be referred to appendix).

heading: 3.1 SCCG FOR THE STRONGLY CONVEX CASE
text: In this subsection, we analyze the query complexity for the strongly convex composition problem and show that our result is better or comparable to the previous methods. Furthermore, we discuss the query complexity under different value with respect to n, µ and
Theorem 1. In Algorithm 1, for the µ-strongly convex problem, suppose Assumption 1 holds, let the step size is η ≤ µ/(135L2f ), the subset size of A is A = min{n, 128B4GL2F /µ2}, the subset size of D1 and D2 are both D = min { n, 5 ( 16B4GL 2 FH1 + 4H2 ) /(4 µ2) } , the number of the inner iteration is K ≥ 540L2f/µ2, the number of outer iteration is S ≥ 1/(log(1/ρ)) log(2E‖x̃0 − x∗‖2/ ).
Then, the query complexity is (D +KA)S = O (( min { n, 1 µ2 } + L2f µ2 min { n, 1µ2 }) log (1/ ) ) .
As can be seen from the above result, Theorem 1 presents the general query complexity under different parameters ( the details of parameters’ setting can be referred to the Appendix.). Comparing n with corresponding parameters, we analyze the query complexity separately. We remove the parameters such as B2G, L 2 F , H1 and H2, and analyze the size with the order of 1/µ
2. We consider three internals of n while the min value of the function in the above query complexity will take different results:
• 1/µ2 ≤ 1/( µ2) ≤ n. When n is large enough such that we can obtain the query complexity is O((1/( µ2) + L2f/µ4) log(1/ )). This result avoids the situation that computing the full gradient of f(x) and the full function G(x) for the large-scale number of n. What’s more, this result is better than Compositional-SVRG (Lian et al., 2017; Liu et al., 2017a).
• 1/µ2 ≤ n ≤ 1/( µ2). When n is smaller than 1/( µ2), the query complexity becomes O((n+ L2f/µ4) log(1/ )), which is the same as Compositional-SVRG (Lian et al., 2017). However, we need to compute the full gradient of ∇f(x̃s) as in (3.1). The estimation of inner function G(x) is the same as in (Lian et al., 2017).
• n ≤ 1/µ2 ≤ 1/( µ2). When n is the smallest one, the query complexity becomes O((n+ L2fn/µ2) log(1/ )). The result has a similar form to SVRG (Johnson & Zhang, 2013). This also gives us an intuition that the inner function should be computed directly rather than estimated if n is small.

heading: 3.2 SCCG FOR THE NONCONVEX CASE
text: In the previous subsection, we showed convex SCCG converges to the optimal point with improved query complexity. A natural question is whether the proposed algorithm can improve the performance of the non-convex problem. We provide an affirmative answer. In this subsection, we present the query complexity for the non-convex composition problem in term of stationarity gap ||∇f(x)||2. Theorem 2. In Algorithm 1, for non-convex function, suppose Assumption 1 holds, let the step size is η = min{1/n2/5, 2/5}, the size of the subset D1 and D2 are D = min {n,O(1/ )}, the size of subset A is A = min {n,O (1/η)}, the number of inner iteration is K ≤ O ( 1/η3/2 ) , the total
number of iteration is T = O (1/ ( η)), in order to obtain E[‖∇f(x̂sk)‖2] ≤ , the query complexity is O ( min { 1/ 9/5, n4/5/ }) .
From the above result, we analyze the query complexity of the non-convex problem separately: 1) when n ≥ 1/ , our query complexity becomes O(1/ 9/5), which is independent on n. This is better than the query complexity of the accelerated method in (Liu et al., 2016), in which the query complexity does not depend on n as well. 2) when n ≤ 1/ , the query complexity becomes O(n4/5/ ), which is consistent with the result of (Liu et al., 2017b) in solving the problem (1.1).

heading: 3.3 MINI-BATCH VERSION OF SCCG
text: In this subsection, we present the mini-batch version of the proposed method in Algorithm 2 (in appendix) and obtain the corresponding query complexities for both the strongly convex and the non-convex functions, which provably benefit from mini-batching. As the process of the proof is similar to that of Theorem 1 and Theorem 2, and the difference with Algorithm 1 is the computation of the gradient of f(x) (the corresponding proof of bound is in appendix), we could directly present the corresponding results for both the strongly convex and the non-convex problems.
Corollary 1. In Algorithm 2, for the µ-strongly convex problem, suppose Assumption 1 holds, let the step size η ≤ bµ/(135L2f ), the number of the inner iteration isK ≥ 540L2f/(bµ2), in order to obtain
E‖x̃s − x∗‖2 ≤ , the query complexity is O (( min { n, 1 µ2 } + L2f bµ2 min { n, 1µ2 }) log (1/ ) ) .
Corollary 2. In Algorithm 2, for the non-convex problem, suppose Assumption 1 holds, let the step size η = b3/5 min{1/n2/5, 2/5}, the number of the inner iteration is K ≤ O ( b1/2/(η3/2) ) , in
order to obtain E[‖∇f(x̂sk)‖2] ≤ , the query complexity is (1/b1/5)O ( min { 1/ 9/5, n4/5/ }) .
From the above-given query complexity results for the strongly convex and non-convex problems, we can see that both of their step size η and the number of inner iteration K are larger than the corresponding ones in the non-mini-batch version. These two key parameters lead to the improved query complexity for both strongly convex and non-convex functions.

heading: 4 EXPERIMENTS
text: In this section, we evaluate the performance of our proposed algorithm on the strongly convex and non-convex functions, respectively.
SCCG for strongly convex function4 To verify the effectiveness of the algorithm, we use the mean-variance optimization in portfolio management5:
minx∈Rd − 1n ∑n i=1 〈ri, x〉+ 1 n ∑n i=1(〈ri, x〉 − 1 n n∑ i=1 〈ri, x〉)2,
where ri ∈ RN , i ∈ [n] is the reward vector, and x ∈ RN is the invested quantity. In the experimental setting, we set n=3000, |A|≈ n2/3, |D1| = 2400, 2600, 2800, which are denoted as SCCG (2400), SCCG (2600) and SCCG (2800). The reward vectors are generated on Gaussian distribution
4Our aim is to compare our general variance-reduce based method with the stochastic composition gradient method, and also to verify the proposed algorithm, thus we do not include SVRG-based method.
5This formulation is just used to verify our proposed algorithm. In appendix, we show the bounded Jacobian.
with the condition number of its covariance matrix denoted by κcov . Furthermore, we consider three conditions numbers, κcov=10, 30 and 50. We compare our algorithm with the stochastic gradient based methods SCGD and accelerated stochastic method ASC-PG. Figure 1 shows the performance of the gap between the value function and optimal value, we observe that our algorithm is better than stochastic gradient methods, SCGD and ASC-PG.
SCCG for non-convex function For the non-convex function, we apply the proposed SCCG method to the nonlinear embedding problem in (1.2). We consider the distance of low-dimension space between xi and xj as 1/(1 + ‖xi − xj‖2), i, j ∈ [n]. Then, the problem can be formulated as the problem in (1.1), in which the details can be referred to the appendix. We consider three datasets: mnist, Olivetti faces and COIL-20 including different sample sizes and dimensions, 1000× 784, 400 × 4096 and 1440× 16384. Our experiment is to verify our proposed algorithm, thus we set D1 = D2 in default and choose three different sizes of sample set D1, which are smaller than n. For example, for the case of mnist, we choose |D1| = 400, 600, 800, which are denoted as SCCG (400), SCCG (600) and SCCG (800). Furthermore, we also set |A|≈ n2/3, where n is the total number of samples. Figure 2 shows the norm of the gradient, and Figure 3 (in appendix) shows the objection value. We compare our algorithm with the stochastic gradient based method (SCGD and ASC-PG), and observe that our proposed algorithm is better than SCGD and ASC-PG on both the norm of the gradient and objective function. Additional experiments on reinforcement learning are given in appendix.

heading: 5 CONCLUSION
text: In this paper, we propose the variance reduction based method for the strongly convex and nonconvex composition problems. We apply the stochastically controlled stochastic gradient to estimate inner function G(x) and the gradient of f(x). The query complexity of our proposed algorithm is better than or equal to the current methods on both strongly convex and non-convex functions. Furthermore, we also present the corresponding mini-batch version of the proposed method, in which the query complexities are improved as well. Experimental results also confirm that our algorithm achieves better query complexity in a real-world problem.

heading: A TECHNICAL TOOL
text: For the subset A ⊆ [n], we present the following lemma that the variance of a random variable decreases by a factor |A| if we choose |A| independent elements from [n] and average them. The proof process is trivial However, it is an important tool for analyzing the query complexity under the different sizes of the subsets.
Lemma 1. If v1, ..., vn ∈ Rd satisfy ∑n i=1 vi =
~0, andA is a non-empty, uniform random subset of [n] and A = |A|, that is elements in A are uniformly selected from [n] without replacement, then
EA ∥∥ 1 A ∑ b∈A vb ∥∥2 ≤ I(A<n)A 1n n∑ i=1 ||vi||2.
Furthermore, if elements in A are independently selected from [n] with replacement,, then
EA ∥∥ 1 A ∑ b∈A vb ∥∥2 = 1An n∑ i=1 ||vi||2.
Proof. Based on the ∑n i=1 vi = ~0, and permutation and combination,
For the case that A is a non-empty, uniformly random subset of [n], we have
EA ∥∥∥∑
b∈A vb ∥∥∥2 =EA [∑ b∈A ‖vb‖2 ] + 1
CAn ∑ i∈[n]
〈 vi,
CA−1n−1 (A− 1) n− 1 ∑ i 6=j vj
〉
=A 1
n ∑n i=1 ‖vi‖2 + A (A− 1) n (n− 1) ∑ i∈[n] 〈 vi, ∑ i 6=j vj 〉 =A 1
n ∑n i=1 ‖vi‖2 + A (A− 1) n (n− 1) ∑ i∈[n] 〈vi,−vi〉
= A (n−A) (n− 1) 1 n ∑n i=1 ‖vi‖2
≤AI (A < n) 1 n ∑n i=1 ‖vi‖2,
where CnA refer to the number of the combination of n things taken A at a time without repetition. Thus, we have
EA ∥∥∥∥ 1A∑b∈A vb ∥∥∥∥2 = 1A2EA∥∥∥∑b∈A vb∥∥∥2 ≤ I (A < n)A 1n n∑ i=1 ‖vi‖2.
For the case that the element in A is randomly and independently selected from [n], we have
EA ∥∥∥∑
b∈A vb ∥∥∥2 =EA [∑ b∈A ‖vb‖2 ] + 2EA [∑ 1≤b<A 〈 vb, ∑ b<k≤A vk 〉] =B 1
n ∑n i=1 ‖vi‖2 + 2EA [∑ 1≤b<A 〈 E [v] , ∑ b<k≤A vk 〉] =A 1
n ∑n i=1 ‖vi‖2 +A (A− 1) ‖E [v]‖2 (A.1)
=A 1
n ∑n i=1 ‖vi‖2.
Based on Lemma 1, we can obtain the inequality with two-variables D1 and D2, which are used for the gradient of f(x).
Lemma 2. If w1, ..., wn ∈ RM×N and v1, ..., vn ∈ RM satisfy ( 1n ∑ i∈[n] wi) T( 1n ∑ j∈[n] vj) = w̄Tv̄, and D = [D1,D2] is a non-empty, uniform random subset consist of D1 and D2, which are independently and uniformly selected from [n], D = |D1| = |D2|, then
ED ∥∥∥∥ 1|D1| |D2| (∑ d1∈D1 wd1 )T (∑ d2∈D2 vd2 ) − w̄v̄ ∥∥∥∥2 =ED ∥∥∥∥ 1D2 (∑ [d1,d2]∈D ( (wd1) Tvd2 − w̄Tv̄ ))∥∥∥∥2
≤ I ( D2 < n2 ) D2 1 n2 n∑ i,j=1 ∥∥(wi)Tvj − w̄Tv̄∥∥2.

heading: B BOUND ANALYSIS OF SCCG FOR THE COMPOSITION PROBLEM

heading: B.1 BOUNDS ANALYSIS OF THE ESTIMATED FUNCTION AND THE GRADIENT
text: Here, we mainly give different kinds of bounds for the proposed algorithm, such as EA,D1‖Ĝk − G(xk)‖2, ED‖EA,ik,jk [∇f̃k]−∇f(xk)‖2 and Eik,jk,A,D‖∇f̃k−∇f(xk)‖2. These bounds will be used to analyze the convergence rate and query complexity. These bounds are all based on Assumption 1. Parameters such as BG, BF , LG, LF and Lf in the bound are all from these Assumptions. We do not define the exact value of parameters such as h, A and D, which have a great influence on the convergence but will be clearly defined in the query analysis. Our proposed bounds are similar to that of (Lian et al., 2017; Liu et al., 2017a;b), but, the difference lies on that there is an extra subset D, which shows an interesting phenomenon. That is when the subset D is equal to [n], the corresponding bounds are the same as in (Lian et al., 2017; Liu et al., 2017a;b). However, it is the independent subset D that gives more general query complexity result for the problem (1.1). The following bounds are all used for the composition problem for both convex and non-convex problems based on the Lemma 1 and Lemma 2. For simplicity, we drop the superscript ik, jk, A and D for the expectation with E in the proof.
Lemma 3. Suppose Assumption 1 holds, for Ĝk defined in (3.3) with D = |D1| and A = |A|, we have
EA,D1‖Ĝk −G(xk)‖2 ≤ 4 I (A < n)
A B2GE‖xk − x̃s‖ 2 + 6 I (D < n) D H1.
Proof. By the definition of Ĝk in (3.3), we have
E‖Ĝk −G(xk)‖2 =E‖Ĝk −GD1(xk) +GD1(xk)−G(xk)‖2 1© ≤2E‖Ĝk −GD1(xk)‖2 + 2E‖GD1(xk)−G(xk)‖ 2
2© ≤4 I (A < n)
A B2GE‖xk − x̃s‖ 2 + 6 I (D < n) D H1,
where 1© follows from ||a1 + a2||2 ≤ 2a21 + 2a22; 2© is based on Lemma 1 and the following inequality: Through adding and subtracting the term G(xk)−G(x̃s), we have
E‖Ĝk −GD1(xk)‖2
=E‖GA(xk)−GA(x̃s) +GD1(x̃s)−GD1(xk)‖ 2
=E‖GA(xk)−GA(x̃s)− (G(xk)−G(x̃s)) + (G(xk)−G(x̃s)) +GD1(x̃s)−GD1(xk)‖ 2 1© ≤2E‖GA(xk)−GA(x̃s)− (G(xk)−G(x̃s)))‖2 + 2E‖GD1(x̃s)−GD1(xk)− (G(x̃s)−G(xk))‖ 2 2© ≤2 I (A < n)
A Ei‖Gi(x̃s)−Gi(xk)‖2 + 2E‖GD1(x̃s)−G(x̃s)‖ 2 + 2E‖−GD1(xk) +G(xk)‖ 2
3© ≤2 I (A < n)
A B2GE‖xk − x̃s‖ 2 + 4 I (D < n) D H1,
where 1© follows from ||a+b||2 ≤ 2a2+2b2; 2© is based on Lemma 1; 3© follows from the bounded function of G and the upper bound of variance of G. Note that A and xk are independent; and D and x̃s are independent.
Lemma 4. Suppose Assumption 1 holds, for Ĝk defined in (3.3) and ∇f̃k defined in (3.4) with D = [D1,D2] and D = |D1| = |D2|, we have
ED‖EA,ik,jk [∇f̃k]−∇f(xk)‖2 ≤4B4GL2F ( 4 I (A < n)
A
) E‖xk − x̃s‖2
+ 32B2GL 2 F I(D < n) D H1 + 4 I(D2 < n2) D2 H2.
Proof. Through adding and subtracting the terms of
(∂G(xk)) T∇F (G(xk)), (∂GD1(x̃s))T∇FD1(G(x̃s)), (∂G(x̃s))T∇F (G(x̃s)),
we have ED‖EA,ik,jk [ ∇f̃k ] −∇f(xk)‖2
=E ∥∥∥(∂G(xk))T∇F (Ĝk)− (∂G(x̃s))T∇F (GD1(x̃s)) +∇f̂D(x̃s)−∇f(xk)∥∥∥2
1© ≤4E ∥∥∥(∂G(xk))T∇F (Ĝk)− (∂G(xk))T∇F (G(xk))∥∥∥2 + 4E
∥∥(∂G(x̃s))T∇F (G(x̃s))− (∂G(x̃s))T∇F (GD1(x̃s))∥∥2 + 4E
∥∥∥∇f̂D(x̃s)− (∂GD1(x̃s))T∇FD2(G(x̃s))∥∥∥2 + 4E
∥∥(∂GD1(x̃s))T∇FD2(G(x̃s))− (∂G(x̃s))T∇F (G(x̃s))∥∥2 2© ≤4B2GL2FE
∥∥∥Ĝk −G(xk)∥∥∥2 + 4B2GL2FE‖G(x̃s)−GD1(x̃s)‖2 + 4B2GL2FE‖G(x̃s)−GD1(x̃s)‖2 + 4 I(D2 < n2)D2 H2 3© ≤4B4GL2F ( 4 I (A < n)
A
) E‖xk − x̃s‖2 + 32B2GL2F
I(D < n) D H1 + 4 I(D2 < n2) D2 H2,
where 1© follows from ||a1 + a2 + a3 + a4||2 ≤ 4a21 + 4a22 + 4a23 + 4a24; 2© is based on the bounded Jacobian of G and the smoothness of F in Assumption 1, and the upper bound of variance in Lemma 2. 3© is based on Lemma 3 and the upper bound of variance of G(x). Note thatA and xk are independent; and D and x̃s are independent.
Lemma 5. Suppose Assumption 1 holds, for Ĝk defined in (3.3) and ∇f̃k defined in (3.4) with D = [D1,D2] and D = |D1| = |D2|, we have
Eik,jk,A,D‖∇f̃k −∇f (xk)‖2 ≤40B2GL2F I(D < n)
D H1 + 5 I(D2 < n2) D2 H2
+5B4GL 2 F
( L2f
B4GL 2 F
+ 4 I (A < n)
A
) E‖xk − x̃s‖2.
Proof. Through adding and subtracting the term of (∂Gj(xk))T∇Fi(G(xk)), (∂Gj(x̃s))
T∇Fi(G(x̃s)), (∂G(x̃s))T∇F (G(x̃s)), (∂GD1(x̃s))T∇FD1(G(x̃s)) (Note that, D and x̃s are independent), we have
E‖∇f̃k −∇f (xk)‖2 =E ∥∥∥(∂Gj(xk))T∇Fi(Ĝk)− (∂Gj(x̃s))T∇Fi(GD1(x̃s)) +∇f̂D(x̃s)−∇f(xk)∥∥∥2
1© ≤5E ∥∥(∂Gj(xk))T∇Fi(G(xk))− (∂Gj(x̃s))T∇Fi(G(x̃s))− (∇f(xk)− (∂G(x̃s))T∇F (G(x̃s)))∥∥2
+ 5E ∥∥∥(∂Gj(xk))T∇Fi(Ĝk)− (∂Gj(xk))T∇Fi(G(xk))∥∥∥2
+ 5E ∥∥(∂Gj(x̃s))T∇Fi(G(x̃s))− (∂Gj(x̃s))T∇Fi(GD1(x̃s))∥∥2
+ 5E ∥∥∥∇f̂D(x̃s)− (∂GD1(x̃s))T∇FD2(G(x̃s))∥∥∥2
+ 5E ∥∥(∂GD1(x̃s))T∇FD2(G(x̃s))− (∂G(x̃s))T∇F (G(x̃s))∥∥2
2© ≤5L2fE‖xk − x̃s‖ 2 + 5B2GL 2 FE ∥∥∥Ĝk −G(xk)∥∥∥2 + 5B2GL2FE‖G(x̃s)−GD1(x̃s)‖2
+ 5B2GL 2 FE‖G(x̃s)−GD1(x̃s)‖ 2 + 5 I(D2 < n2) D2 H2
3© ≤5B4GL2F
( L2f
B4GL 2 F
+ 4 I (A < n)
A
) E‖xk − x̃s‖2 + 40B2GL2F
I(D < n) D H1 + 5 I(D2 < n2) D2 H2,
where 1© follows from ||a1 + a2 + a3 + a4 + a5||2 ≤ 5a21 + 5a22 + 5a23 + 5a24 + 5a25; 2© is based on E[‖X −E[X]‖2] = E[X2−‖E[X]‖2] ≤ E[X2], the smoothness of Fi, the bounded Jacobian of G(x) and the smoothness of F in Assumption 1, and the upper bound of the variance. 3© is based on Lemma 3.
As can be seen from the above results directly, when A and D increase, the upper bounds are close to the bounds in (Lian et al., 2017; Liu et al., 2017a;b). Though there are extra terms with respect to A and D, they give us another direction for analyzing the convergence rate and query complexity. The convergence rate not only depends on the convergence sequence, but also the terms including the event function I. Thus, we can obtain the lower bound range of A and D that is related to . Furthermore, this lemma can be applied to analyze the convergence rate and query complexity of the convex and non-convex composition problem.

heading: C PROOF OF SCCG METHOD FOR COMPOSITION PROBLEM

heading: C.1 PROOF OF SCCG METHOD FOR STRONGLY CONVEX COMPOSITION PROBLEM
text: In this section, we analyze the proposed algorithm for the strongly convex composition problem. We first present the convergence of the proposed algorithm and then give the query complexity. Though the proof is similar to that of (Lian et al., 2017) and (Xiao & Zhang, 2014), we present a more clear and simple process as there is an extra term derived from the subset D. In order to ensure the convergence of the proposed algorithm, we obtain the desired parameters’ setting, such as A, D, K, η and h. Based on the setting, we can obtain the corresponding query complexity, which is better than or equal to the SVRG-based method in (Lian et al., 2017) and (Liu et al., 2017a). This is in fact that the event function I has an influence on the size of A and D.

heading: C.1.1 CONVERGENCE ANALYSIS
text: Based on the strong convex and smoothness of the function of f(x), we provide the convergence sequence, in which the parameters are not defined. But the sequences motivate us to consider the parameters’ setting such that lead to the desired convergence rate. Note that, D and x̃s are independent.
Theorem 3. Suppose Assumption 1 holds, in Algorithm 1, let h > 0, η > 0, A = |A|, D = |D1| = |D2|, K is the number of the inner iteration, x∗ is the optimal point, we have
E‖x̃S − x∗‖2 ≤ ρSE‖x̃0 − x∗‖2 + ρ3 ρ1
1− ρS
1− ρ ,
where ρ = ( 1K + ρ2)/ρ1, ρ2 and ρ3 defined (V , V1 are defined in (C.4) and (C.5).)
ρ1 =
( 2µ− h− 4V 1 h − ( 12L2f + 10V ) η ) η, (C.1)
ρ2 =2
( 2V 1
h + 5
( L2f + V ) η ) η, (C.2)
ρ3 = 1
h η
4 5 V1 + 2η 2V1. (C.3)
Proof. By the update of xk in Algorithm 1, we have
E‖xk+1 − x∗‖2 =E‖xk − x∗‖2 − 2ηE〈∇f̃k, xk − x∗〉+ η2E ∥∥∥∇f̂k∥∥∥2
=E‖xk − x∗‖2 − 2ηE〈∇f(xk) + EA,i,j [ ∇f̃k ] −∇f(xk), xk − x∗〉+ η2E ∥∥∥∇f̂k∥∥∥2 =E‖xk − x∗‖2 − 2ηE〈∇f(xk), xk − x∗〉 − 2ηE〈EA,i,j [ ∇f̃k ] −∇f(xk), xk − x∗〉
+ η2E ∥∥∥∇f̂k +∇f(xk)−∇f(xk)∥∥∥2
1© ≤E‖xk − x∗‖2 − 2ηµE‖xk − x∗‖2 + η 1 h E ∥∥∥EA,i,j [∇f̃k]−∇f(xk)∥∥∥2 + hηE‖xk − x∗‖2
+ 2η2 ( E‖∇f(xk)‖2 + E ∥∥∥∇f̃k −∇f(xk)∥∥∥2) =E‖xk − x∗‖2 − (2ηµ− hη)E‖xk − x∗‖2 + η 1 h E ∥∥∥EA,i,j [∇f̃k]−∇f(xk)∥∥∥2
+ 2η2 ( E‖∇f(xk)−∇f(x∗)‖2 + E ∥∥∥∇f̃k −∇f(xk)∥∥∥2) 2© ≤E‖xk − x∗‖2 − (2ηµ− hη)E‖xk − x∗‖2 + η 1
h
( 4V ‖xk − x̃s‖2 + V2 ) + 2η2 ( L2fE‖xk − x∗‖ 2 + 5 ( L2f + V ) ‖xk − x̃s‖2 + V1
) =E‖xk − x∗‖2 − ( 2µ− h− 4V 1 h − ( 12L2f + 10V ) η ) ηE‖xk − x∗‖2
+ 2 ( 2V 1
h + 5
( L2f + V ) η ) ηE‖x̃s − x∗‖2 + 1
h ηV2 + 2η
2V1,
where
V =B4GL 2 F
( 4 I (A < n)
A
) , (C.4)
V1 =40B 2 GL 2 F I(D < n) D H1 + 5 I(D2 < n2) D2 H2, (C.5)
V2 =32B 2 GL 2 F I(D < n) D H1 + 4 I(D2 < n2) D2 H2 = 4 5 V1, (C.6)
1© is based on ||a1 + a2||2 ≤ 2a21 + 2a22 and 〈a1, a2〉 ≤ h||a1||2 + 1h ||a2|| 2, h > 0; 2© is based on strongly-convex of f in Assumption 1, and Lemma 4, 5.
Summing up from k = 0 to k = K − 1, we have
E‖xK − x∗‖2 ≤ E‖x0 − x∗‖2 − ρ1 K−1∑ k=0 E‖xk − x∗‖2 +Kρ2E ‖x̃s − x∗‖+Kρ3,
where
ρ1 =
( 2µ− h− 4V 1 h − ( 12L2f + 10V ) η ) η,
ρ2 =2
( 2V 1
h + 5
( L2f + V ) η ) η,
ρ3 = 1
h ηV2 + 2η
2V1.
For x0 = x̃s, by arranging, we have
ρ1E‖x̃s+1 − x∗‖2 ≤ 1
K E‖x0 − x∗‖2 + ρ2E‖x̃s − x∗‖2 + ρ3 −
1
K E‖xK − x∗‖2 ≤ ( 1
K + ρ2
) E‖x̃s − x∗‖2 + ρ3.
we assume that ρ1 > 0 in (C.1), then we can obtain
E‖x̃S − x∗‖2 ≤ρSE‖x̃0 − x∗‖2 + ρ3 ρ1 S∑ s=0 ρs
≤ρSE‖x̃0 − x∗‖2 + ρ3 ρ1
1− ρS
1− ρ , (C.7)
where ρ = ( 1K + ρ2)/ρ1, ρ2 and ρ3 defined in (C.2) and (C.3), the last inequality is based on the formula of geometric progression.
Thus, if x̃S converges to the optimal point x∗, we need to ensure that ρ < 1 and the second term ρ3(1− ρS)/(ρ1(1− ρ)) is less than /2. Actually, ifD = n, the second term is equal to zero, which will be similar to the convergence results in (Lian et al., 2017) and (Liu et al., 2017a).

heading: Proof of Theorem 1
text: Proof. In order to keep the proposed algorithm converge, we consider the parameters’ setting, we first ensure that ρ1 > 0 in (C.1), and then define
ρ = ( 1
K + ρ2)/ρ1, (C.8)
that require ρ < 1, where ρ2 defined in (C.2). Thus, the convergence sequence is
E‖x̃S − x∗‖2 ≤ ρSE‖x̃0 − x∗‖2 + ρ3 ρ1 S∑ s=0 ρs ≤ ρSE‖x̃0 − x∗‖2 + ρ3 ρ1 1 1− ρ .
We ensure ρ3ρ1 1 1−ρ ≤ 1 2 , where ρ3 defined in (C.3), that we can derive the size of the D. In the following we analyze the parameters’ setting such that satisfying the above requirement.
1. In order to ensure ρ1 > 0 in (C.1), we consider the parameter h, η and A,
(a) h = µ, consider ρ1 in (C.1), we should require that h ≤ µ, however, V in (C.4) has the relationship with A and D. In order to keep A small enough, we set the upper bound of h. Thus, we set h = µ.
(b) A = min { n, 128B4GL 2 F 1 µ2 } , based on the setting of h, we require that V/h < µ16 .
Thus, we have
V = B4GL 2 F ( 4 I(A<n)A ) ≤ 8B4GL2F I(A<n) A ≤ 1 16µ 2.
For V defined in (C.4), if A < n, we have A ≥ 128B4GL2F 1µ2 ,
otherwise, A = n satisfy the requirement. Thus, we have A = min { n, 128B4GL 2 F 1 µ2 } .
(c) η ≤ 3µ 53L2f , back to the target of ρ1 > 0, we require that η ≤ 3µ53L2f ≤ 3 4µ 12L2f+ 10 8 L 2 f
≤ 3 4µ
12L2f+ 10 8 µ
2 = µ−4 1µV
12L2f+10V = 2µ−h−4 1hV 2L2f+10(L2f+V )
, note that µ ≤ Lf by the definition in preliminaries.
2. In order to ensure ρ < 1 in (C.8), we first consider ρ1 and ρ2 in (C.1) and (C.2). By the setting of h = µ and V < µ2/16, we have,
ρ1 ≥ ( µ− 2L2fη − ( 1
4 µ+ 10
( L2f + 1 16 µ2 ) η )) η ≥ ( 3 4 µ− 101 8 L2fη ) η, (C.9)
ρ2 ≤4 1
µ η
1
16 µ2 + 10
( L2f + 1 16 µ2 ) η2 ≤ ( 1 4 µ+ 10 ( L2f + 1 16 µ2 ) η ) η ≥ ( 1 4 µ+ 85 8 L2fη ) η.
(C.10)
We require that ρ = 1Kρ1 + ρ2 ρ1 < 1, and analyze the two terms separately,
(a) In order to ρ2ρ1 < 1 2 , that is
ρ2 ρ1 <
( 1 4µ+ 85 8 L 2 fη ) η(
3 4µ− 101 8 L 2 fη ) η < 1 2 .
We get η ≤ µ 135L2f .
(b) In order to 1Kρ1 < 1 2 , that is
1
Kρ1 <
1 2Kρ2 ≤ 1 2K (
1 4µ+ 10 ( L2f + 1 16µ 2 ) η ) η
≤ 1 2K (
1 4µ+ 85 8 L 2 fη ) η ≤ 1 2K ( 1 4µη ) < 1 2 .
Thus, we have K ≥ 540L 2 f
µ2 .
3. Consider the term ρSE‖x̃0 − x∗‖2 + ρ3ρ1 1 1−ρ , we analyze them separately,
(a) In order to ensure ρ3ρ1 1 1−ρ ≤ 1 2 , that is
ρ3 ρ1
1 1− (
1 Kρ1 + ρ2ρ1
) = ρ3 ρ1 − 1K − ρ2 ≤ ρ3 ρ1 − 1K − 1 2ρ1 ≤ ρ31 2ρ1 − 1 K ≤ 2ρ3 ρ1 ≤ 1 2 .
Based on the bound of ρ1 in (C.9), the definition of V1 in (C.5) and the step size η mentioned above, we have i. For V
2
1 µηV2 + 2η 2V1
ρ1 = 2 1 µV2 + 2ηV1 3 4µ− 101 8 L 2 fη = 4 5 1 µV1 + 2ηV1 3 4µ− 101 8 L 2 fη =
( 4 5µ + 2η ) V1
3 4µ− 101 8 L 2 fη ≤ ,
thus, we have
V1 ≤ 4
5 µ2 ≤
( 3 4 − 101 8 1 135 ) 4 5 + 2 135 µ2 ≤ ( 3 4 − 101 8 1 135 ) µ 4 5µ + 2 µ 135µ2 ≤ 3 4µ− 101 8 L 2 f µ 135L2f 4 5µ + 2 µ 135L2f ≤ 3 4µ− 101 8 L 2 fη( 4 5µ + 2η
) ii. If D < n, we can obtain D ≥ 54 µ2 ( 20B4GL 2 FH1 + 5H2 ) , other-
wise D = 0, the above inequality is correct. Thus, we obtain D = min { n, ( 16B4GL 2 FH1 + 4H2 ) 5 4 µ2 } .
(b) In order to ensure ρSE‖x̃0 − x∗‖2 ≤ 12 , we need the number of the outer iterations
S ≥ 1 log (1/ρ)
log 2E‖x̃0 − x∗‖2 .
All in all, we consider the query complexity based on above parameters’ setting. For each outer iteration, there will be (D +KA) queries. Thus, the query complexity is
(D +KA)S = O (( min { n, 1
µ2 } + L2f µ2 min { n, 1 µ2 }) log (1/ ) ) .

heading: C.2 PROOF OF SCCG METHOD FOR NON-CONVEX COMPOSITION PROBLEM

heading: C.2.1 RELATED BOUNDS
text: Lemma 6. Suppose Assumption 1 hold, in Algorithm 1, we can obtain the following new sequence with respect to f(xk) and ||xk − x̃s||2, let h > 0, η > 0, A = |A| and D = |D1| = |D2|, we have
E[f(xk+1)] + ck+1E‖xk+1 − x̃s‖2 ≤ E[f(xk)] + ckE‖xk − x̃s‖2 − uk‖∇f(xk)‖2 + Jk,
where
W =B4GL 2 F
( 4 I (A < n)
A + 4 I (D < n) D
) , (C.11)
ck =ck+1
( 1 + ( 2
h + 4hW
) η + 10 ( L2f +W ) η2 )
+ 2Wη + 5(L2f +W )Lfη 2, (C.12)
uk =
(( 1
2 − hck+1
) η − (Lf + 2ck+1) η2 ) , (C.13)
W1 =20B 2 GL 2 F I(D < n) D H1 + 5 I(D2 < n2) D2 H2, (C.14)
Jk =
( 1
2 + hck+1
) 4
5 W1η + (Lf + 2ck+1)W1η
2. (C.15)
Proof. Consider the upper bound of f(xk+1) and ‖xk+1 − x̃s‖2, respectively,
• Base on the smoothness of f in Assumption 1 and take expectation with respective to ik, jk, we have
Ei,j [f(xk+1)]
≤E [f(xk)]− ηE〈∇f(xk),∇f̃k〉+ Lf 2 η2E ∥∥∥∇f̃k∥∥∥2 =E [f(xk)]− ηE〈∇f(xk),∇f̃k −∇f(xk) +∇f(xk)〉+
Lf 2 η2E ∥∥∥∇f̃k∥∥∥2 =E [f(xk)]− ηE〈∇f(xk),∇f(xk)〉 − η〈∇f(xk),E [ ∇f̃k ] −∇f(xk)〉+
Lf 2 η2E ∥∥∥∇f̃k −∇f(xk) +∇f(xk)∥∥∥2 ≤E [f(xk)]− ηE‖∇f(xk)‖2 + 1
2 ηE‖∇f(xk)‖2 +
1 2 ηE ∥∥∥EA,i,j [∇f̃k]−∇f(xk)∥∥∥2
+ Lf 2 η2 ( 2E‖∇f(xk)‖2 + 2E ∥∥∥∇f̃k −∇f(xk)∥∥∥2)
=E [f(xk)]− 1
2 ηE‖∇f(xk)‖2 +
1 2 ηE ∥∥∥EA,i,j [∇f̃k]−∇f(xk)∥∥∥2 + Lfη2(E‖∇f(xk)‖2 + E∥∥∥∇f̃k −∇f(xk)∥∥∥2)
=E [f(xk)]− ( 1
2 η − Lfη2
) E‖∇f(xk)‖2 + 1 2 ηE ∥∥∥EA,i,j [∇f̃k]−∇f(xk)∥∥∥2 + Lfη2E∥∥∥∇f̃k −∇f(xk)∥∥∥2,
where the last inequality is based on ||a1 + a2||2 ≤ 2a21 + 2a22.
• Base on the update of xk in Algorithm 1 and take expectation with respective to ik, jk, we have,
Ei.j‖xk+1 − x̃s‖2 =E‖xk − x̃s‖2 − 2ηE〈∇f̃k, xk − x̃s〉+ η2E ∥∥∥∇f̃k∥∥∥2
=E‖xk − x̃s‖2 − 2ηE〈∇f̃k −∇f(xk) +∇f(xk), xk − x̃s〉] + η2E ∥∥∥∇f̃k∥∥∥2
=E‖xk − x̃s‖2 − 2ηE〈∇f(xk), xk − x̃s〉]− 2η〈E [ ∇f̃k ] −∇f(xk), xk − x̃s〉]
+ η2E ∥∥∥∇f̃k −∇f(xk) +∇f(xk)∥∥∥2
≤E‖xk − x̃s‖2 + hη‖∇f(xk)‖2 + hη ∥∥∥E [∇f̃k]−∇f(xk)∥∥∥2 + 2
h ηE‖xk − x̃s‖2 + η2 ( 2E‖∇f(xk)‖2 + 2E ∥∥∥∇f̃k −∇f(xk)∥∥∥2)
= ( 1 + 2
h η
) E‖xk − x̃s‖2 + ( hη + 2η2 ) E‖∇f(xk)‖2 + hηE ∥∥∥E [∇f̃k]−∇f(xk)∥∥∥2 + 2η2E∥∥∥∇f̃k −∇f(xk)∥∥∥2, where the inequality is based on 2〈a1, b2〉 ≤1/h‖a1‖2+h‖a2‖2, ∀h > 0, and ||a1+a2||2 ≤ 2a21 + 2a 2 2.
Combine above equalities and Lemma 4, 5, we form a Lyapunov function,
E[f(xk+1)] + ck+1E‖xk+1 − x̃s‖2 =E[f(xk)]− ( 1
2 η − Lfη2
) ‖∇f(xk)‖2 + 1 2 η ∥∥∥E [∇f̃k]−∇f(xk)∥∥∥2 + Lfη2∥∥∥∇f̃k −∇f(xk)∥∥∥2
+ ck+1
(( 1 + 2
h η
) E‖xk − x̃s‖2 + ( hη + 2η2 ) ‖∇f(xk)‖2 + hη ∥∥∥E [∇f̃k]−∇f(xk)∥∥∥2 + 2η2∥∥∥∇f̃k −∇f(xk)∥∥∥2) =E[f(xk)] + ck+1 ( 1 + 2
h η
) E‖xk − x̃s‖2 − (( 1
2 − ck+1h
) η − (Lf + 2ck+1) η2 ) ‖∇f(xk)‖2
+ ( Lfη 2 + 2η2ck+1 ) ∥∥∥∇f̃k −∇f(xk)∥∥∥2 + (1
2 η + hηck+1 )∥∥∥E [∇f̃k]−∇f(xk)∥∥∥2 ≤E[f(xk)] + ckE‖xk − x̃s‖2 − uk‖∇f(xk)‖2 + Jk,
where
uk =
(( 1
2 − hck+1
) η − (Lf + 2ck+1) η2 ) ;
W1 =40B 2 GL 2 F I(D < n) D H1 + 5 I(D2 < n2) D2 H2; W2 = 4
5 W1;
Jk =
( 1
2 + hck+1
) W2η + (Lf + 2ck+1)W1η 2;
W =B4GL 2 F
( 4 I (A < n)
A
) ;
ck =ck+1
( 1 + ( 2
h + 4hW
) η + 10 ( L2f +W ) η2 ) + 2Wη + 5(L2f +W )Lfη 2.
Based on the above inequality with respect to the sequence E[f(xk)] + ckE‖xk − x̃s‖2 and Algorithm 1, we can obtain the convergence form in which the parameters are not clear defined.
Theorem 4. In Algorithm 1, suppose Assumption 1 holds, we can obtain the following new sequence with respect to f(xk) and ||xk− x̃s||2. K is the number of inner iterations, S is the number of inner iterations, we have
u0E[‖∇f(x̂sk)‖2] ≤ f(x0)− f(x∗)
KS + J0,
where x̂sk is the output point, J0 and u0 are defined in (C.15) and (C.13).
Proof. Based on the update for ck in (C.12), we can see that ck > ck+1. As ck is a decreasing sequence, we have u0 < uk and Jk < J0. Then, we get
u0E[‖∇f(xk)‖2] ≤ E[f(xk)] + ckE[‖xk − x̃s‖2]− (E[f(xk+1)] + ck+1E[‖xk+1 − x̃s‖2]) + J0.
Sum from k = 0 to k = K − 1, we can get
1
K K−1∑ k=0 uE[‖∇f(xk)‖2] ≤ E[f(x0)]− (E[f(xK)] + cKE[‖xK − x̃s‖2]) K + J0
≤ E[f(x0)]− E[f(xK)] K + J0.
Since x0 = x̃s, let x̃s+1 = xK , we obtain,
1
K K−1∑ k=0 u0E[‖∇f(xk)‖2] ≤ E[f(x̃s)]− E[f(x̃s+1)] K + J0.
Summing the outer iteration from s = 0 to S − 1, we have
u0E[‖∇f(x̂sk)‖2] = 1
S S−1∑ s=0 1 K K−1∑ k=0 u0E[‖∇f(xsk)‖ 2 ] + J0
≤ E[f(x̃0)]− E[f(x̃S)] KS + J0 ≤ f(x0)− f(x∗) KS + J0,
where xsk indicates the s-th outer iteration at k-th inner iteration, and x̂ s k is uniformly and randomly chosen from s = {0, ..., S − 1} and k={0, ..,K − 1}.

heading: C.2.2 CONVERGENCE ANALYSIS
text: Base on Algorithm 1, the analysis of convergence is based on the smoothness of f(x) and the update of x under the Lyapunov function to form the convergence sequence. Theorem 1 shows that our proposed algorithm can converge to the stationary point.
The convergence proof is similar to that of (Liu et al., 2017b; Reddi et al., 2016), however, our algorithm considers the inexact computation of the gradient at the beginning of each epoch. Thus, we derive the different parameters’ setting. In particular, the number of the subset D and A depend on the min function. Intuitively, we can compute the gradient and inner function based on the subset rather on the whole sample. Moreover, considering the convergence results, we can see that the step size η has the relationship with many parameters, such as the subset A, inner iteration K and the total iteration T .

heading: Proof of Theorem 2
text: Proof. In order to have E[‖∇f(x̂sk)‖2] ≤ , that is
E[‖∇f(x̂sk)‖2] ≤ Lf (f(x0)−f(x∗)) u0SK + J0/u0 ≤ 2 + 2 ≤ ,
we consider the corresponding parameters’ setting:
1. For the first term, consider ck defined in (C.12) define ck = ck+1Y + U , for k = K, we have
cK =
( 1
Y
)K ( c0 + U
Y − 1 ) − U Y − 1 ,
where
Y =1 +
( 2
h + 4hW
) η + 10 ( B4GL 2 F +W ) η2,
U =2Wη + 5(L2f +W )Lfη 2 > 0.
By setting cK → 0, we obtain
c0 = UY K Y − 1 − U Y − 1
= U ( Y K − 1 ) Y − 1 .
Then, putting the Y and U into the above equation. We have
c0 = 2Wη + 5(L2f +W )Lfη 2( 2 h + 4hW ) η + 10 ( L2f +W ) η2 C = 2W + 5(L2f +W )Lfη( 2 h + 4hW ) + 10 ( L2f +W ) η C, (C.16)
where C = Y K − 1. Because c0 has the influence on the parameters such as K, C and u0, we analyze them separately,
(a) For K and C, based on the character of function (
1 + 1t2
)t1 → e,6 as t1, t2 → +∞
and t1t2 < 1, and the function is also the increasing function with an upper bound of e, we require
K < 1/
(( 2
h + 4hW
) η + 10 ( L2f +W ) η2 ) , (C.17)
thus, we have C < e− 1. (b) For u0 defined in (C.13), in order to keep uk > 0, we need to keep c0h < 1/4. If
c0h < 1/4, there exits a constant ũ such that u0 = ũη. In order to satisfy c0h < 1/4, combine with (C.16) and C < e− 1, that is
c0h ≤ 2W + 5(L2f +W )Lfη(
2 h + 4hW
) + 10 ( L2f +W ) η h (e− 1) ≤ 1 4 ,
i. By setting h = 1 5 √ L3fη , there exist w̃ > 0, based on above inequality, we have
W ≤ 16L3fη + 50L 3.5 f
√ ηη 9.6 + 34L3fη − 50 √ L3fηη < w̃L3fη
Thus, combine with the definition of W in (C.11), we require that
W = B4GL 2 F
( 4 I(A < n)
A
) ≤ 8B4GL2F
I(A < n) A
≤ w̃L3fη = O ( L3fη ) .
If A < n, we require A ≥ O ( B4GL 2 F /(L 3 fη) )
. Thus, we have A = min {n,O (1/η)}.
ii. Based on the setting of h and W , combing with (C.17), we have
K < 1( 10 √ L3fη + 4
5 √ L3fη w̃L3fη
) η + 10 ( L2f + w̃L 3 fη ) η2
= 1( 10 √ L3fη + 4 5 √ L3fη ) η + 10 ( L2f + η ) η2 = O
( 1
(Lfη) 3/2
) .
6Here the ’e’ is the Euler number, approximate to 2.718.
2. For the second term about J0, as u0 = w1η, we require
J0 ũη = 1 ũ
( 1
2 + hc0
) W2 + (Lf + 2c0)W1η
≤ 1 ũ W1
( 3
5 + Lfη +
1 2 η √ η ) ≤ 1 ũ ( 20B2GL 2 FH1 + 5H2 )(3 5 + Lfη + η √ η ) I(D < n) D ≤ 1 2 ,
Then, if D < n, we require that
D ≥ 2 ũ ( 20B2GL 2 FH1 + 5H2 ) ( 3 5 + 1 2Lfη + c0η √ η ) = O ( 1 ) .
Thus, we set D = min {n,O(1/ )}.
3. Based on the first term Lf (f(x0)−f(x ∗))
ηSK ≤ 1 2 , the total number of iteration is T = SK =
2Lf (f(x0)−f(x∗)) η .
Thus, based on the above parameters’ setting, we can ensure that E[‖∇f(x̂sk)‖2] ≤ . Based on the parameters’ setting, that is D = min {n,O(1/ )}, A = min {n,O (1/η)}, K ≤ O ( 1/η3/2 ) , and T = O (1/ ( η)), we have,
O ( T
K (D +KA)
) =O ( 1
η
( D
K +A )) =O ( 1
η
( min { n, 1 } η3/2 + 1
η )) =O ( 1 ( min { n, 1 } η1/2 + 1
η2 )) ≥O ( min { 1
9/5 , n4/5
}) ,
where the optimal η = min { 1/n2/5, 2/5 } .

heading: D PROOF FOR THE MINI-BATCH OF THE SCCG TO THE COMPOSITION PROBLEM
text: We provide the Mini-batch version of SCCG:
The following lemma is distinguish with Lemma 5 in which the estimated gradient γ is obtained through b times repeat.
Lemma 7. Suppose Assumption 1 holds, for Ĝk defined in (3.3) and Λ defined in Algorithm 2 with D = [D1,D2] and D = |D1| = |D2|, we have
Eik,jk,A,D‖Λ−∇f (xk)‖2 ≤5B4GL2F
( L2f
bB4GL 2 F
+ 4 I (A < n)
A + 4 I (D < n) D
) E‖xk − x̃s‖2
+ 20B2GL 2 F I(D < n) D H1 + 5 I(D2 < n2) D2 H2,
Proof. Through adding and subtracting the term of 1b ∑
(i,j)∈Ib (∂Gj(xk))
T∇Fi(G(xk)),
1 b ∑ (i,j)∈Ib (∂Gi(x̃s)) T∇Fi(G(x̃s)), and (∂G(x̃s))T∇F (G(x̃s)), (∂GD1(x̃s))T∇FD1(G(x̃s)), we have
E‖Λ−∇f (xk)‖2
Algorithm 2 Mini-batch version of SCCG Require: K, S, η (learning rate), x̃0 and D = [D1,D2]
for s = 0, 1, 2, · · · , S − 1 do Sample from [n] for D times to form mini-batch D1 Sample from [n] for D times to form mini-batch D2 ∇f̂D(x̃s) = (∂GD1(x̃s))T∇FD2(GD1(x̃s)) x0 = x̃s for k = 0, 1, 2, · · · ,K − 1 do
Sample from [n] to form mini-batch A Ĝk = GA(xk)−GA(x̃s) +GD1(x̃s) Λ0 = 0 for t=1,...,b do
Uniformly and randomly pick ik and jk from [n] Compute the estimated gradient∇f̃k from (3.4) Λt+1 = Λt +∇f̃k
end for Λ = Λb/b xk+1 = xk − ηΛ
end for Update x̃s+1 = xK , or x̃s+1 = xr, r is randomly selected from [K − 1]
end for Output: x̂sk is uniformly and randomly chosen from s ∈ {0, ..., S − 1} and k ∈ {0, ..,K − 1}.
1© ≤5E ∥∥∥∥∥∥1b ∑
(i,j)∈Ib
(∂Gj(xk)) T∇Fi(G(xk))− (∂Gj(x̃s))T∇Fi(G(x̃s))− ( ∇f(xk)− (∂G(x̃s))T∇F (G(x̃s)) )∥∥∥∥∥∥ 2
+ 5E ∥∥∥∥∥∥1b ∑
(i,j)∈Ib
(∂Gj(xk)) T∇Fi(Ĝk)− (∂Gj(xk))T∇Fi(G(xk)) ∥∥∥∥∥∥ 2
+ 5E ∥∥∥∥∥∥1b ∑
(i,j)∈Ib
(∂Gj(x̃s)) T∇Fi(G(x̃s))− (∂Gj(x̃s))T∇Fi(GD1(x̃s)) ∥∥∥∥∥∥ 2
+ 5E ∥∥∥∇f̂D(x̃s)− (∂GD1(x̃s))T∇FD2(G(x̃s))∥∥∥2
+ 5E ∥∥∥(∂GD1(x̃s))T∇FD2(G(x̃s))− (∂G(x̃s))T∇F (G(x̃s))∥∥∥2
2© ≤5 b L2fE‖xk − x̃s‖ 2 + 5B2GL
2 FE ∥∥∥Ĝk −G(xk)∥∥∥2 + 5B2GL2FE‖G(x̃s)−GD1(x̃s)‖2
+ 5B2GL 2 FE‖G(x̃s)−GD1(x̃s)‖ 2 + 5 I(D2 < n2) D2 H2
3© ≤5B4GL2F
( L2f
bB4GL 2 F
+ 4 I (A < n)
A
) E‖xk − x̃s‖2 + 40B2GL2F
I(D < n) D H1 + 5 I(D2 < n2) D2 H2,
where 1© follows from ||a1 + a2 + a3 + a4 + a5||2 ≤ 5a21 + 5a22 + 5a23 + 5a24 + 5a25, and 2© is based on E[‖X − E[X]‖2] = E[X2 − ‖E[X]‖2] ≤ E[X2] and Lemma 1, the smoothness of Fi, the bounded Jacobian of G(x) and the smoothness of F in Assumption 1, and the upper bound of variance in Lemma 2. 3© is based on Lemma 3.
Proof of Corollary 2
Proof. Based on the parameters’ setting, that is D = min {n,O(1/ )}, A = min {n,O (b/η)}, K ≤ O ( b1/2/η3/2 ) , and T = O (1/ ( η)), we have,
O ( T
K (D +KA)
) =O ( η3/2
b1/2η
( min { n, 1 } + b1/2b
η3/2η
)) = O ( η1/2
b1/2
( min { n, 1 } + b3/2
η5/2 )) = 1
b1/2 O
( min { n, 1 } η1/2 + b3/2
η2 ) ≥ 1 b1/5 O ( min { n4/5 , 1 9/5 }) ,
where the optimal η = b3/5 min { 1/n2/5, 2/5 } .

heading: E EXPERIMENT

heading: E.1 RISK-AVERSE LEARNING
text: To verify the effectiveness of the algorithm, we use the mean-variance optimization in portfolio management7:
min x∈Rd − 1 n n∑ i=1 〈ri, x〉+ 1 n n∑ i=1 (〈ri, x〉 − 1 n n∑ i=1 〈ri, x〉)2,
where ri ∈ RN , i ∈ [n] is the reward vector, and x ∈ RN is the invested quantity. The objective function can be transformed as the composition of two finite-sum functions in (1.1) with the following forms:
Gj(x) =[x, 〈rj , x〉]T, y = 1
n ∑n j=1 Gj(x) = [y1, y2] T,
Fi(y) =− 〈ri, y1〉+ (〈ri, y1〉 − y2)2, j, i ∈ [n].
where y1 ∈ RM and y2 ∈ R. Note that the function Gj(x) = [x, 〈rj , x〉], and the corresponding Jacobian is [I, e]>, where I ∈ RN×N is a unit matrix, and e ∈ RN×1 is all-ones vector. It is straightforward to prove that the norm of the Jacobian is bounded, i.e. Gj(x) is BG-Lipschitz. We choose such example of the composition problem to verify the efficiency of the proposed algorithms, because it has been widely used in related researches (Lian et al., 2017; Wang et al., 2017; Lin et al., 2018). The source code package will be released as soon as possible to ensure the reproducibility.

heading: E.2 NON-LINEAR EMBEDDING
text: For the non-convex function, we apply the proposed SCCG method to the nonlinear embedding problem in (1.2). We consider the distance of low-dimension space between xi and xj as 1/(1 + ‖xi − xj‖2), i, j ∈ [n]. Then, the problem can be formulated as the problem in (1.1). In particular,
1
n ∑n i=1 Fi (y) = 1 n ∑n i=1 Fi ( 1 n ∑n j=1 Gj (x) ) ,
where
y = 1
n ∑n j=1 Gj(x);
Gj(x) =
[ x,
n 1 + ‖x1 − xj‖2 − 1, ..., n 1 + ‖xn − xj‖2 − 1
]T ;
Fi(y) =n ∑n
k=1 pk|i(‖yi − yk‖ 2 + log(yn+k)), i, j ∈ [n].
7This formulation is just used to verify our proposed algorithm.
Note that, consider the function g (x) = 11+x2 , its gradient is∇g (x) = 2x (1+x2)2 . For different value of x, we can see that |x| ≥ 1⇒ ( 1 + x2
)2 ≥ x; |x| < 1⇒ ( 1 + x2
)2 ≥ 1 > x. Thus, we obtain |∇g (x)| ≤ 2, which is upper bounded. Based on this results, we can obtain that the norm of Jacobian is also bounded. Moreover, in practice, wo do not compute the Jacobian directly as the dimension is large. The matrix of Jacobian is sparse due to the random subset, which greatly save much space.
We consider three datasets: mnist, Olivetti faces and COIL-20 with different sample sizes and dimensions, 1000× 784, 400 × 4096 and 1440× 16384. Our experiment is to verify our proposed algorithm, thus, we set D1 = D2 in default and choose three different sizes of sample set D1, which are smaller than n. For example, for the case of mnist, we choose |D1| = 400, 600, 800, which are denoted as SCCG (400), SCCG (600) and SCCG (800). Furthermore, we also set |A|≈ n2/3, where n is the total number of samples. Figure 2(in the main paper) shows the norm of the gradient, and Figure 3 shows the function value. We compare our algorithm with stochastic gradient based method (SCGD and ASC-PG) and observe that our proposed algorithm is better than SCGD and ASC-PG on both the norm of the gradient and objective function.

heading: E.3 REINFORCEMENT LEARNING
text: We consider the policy value evaluation in reinforcement learning. Let the policy of interest be π, total states be S, and the value function of state be V π at state s1,
V π (s1) = Eπ {Rs1,s2 + γV π (s2) |s2} , s1, s2 ∈ [S],
where Rs1,s2 is the reward of moving from state s1 to s2, and the expectation is taking over state s2 conditioned on state s1. We assume V π(s) ≈ΦTs w∗ for some w∗ ∈ Rd, where Φ is the linear map of the feature used to approximate the value of the state. Then, the problem can be formulated as the Bellman residual minimization problem, that is
min w S∑ i=1 〈Φi, w〉 − S∑ j=1 Pπi,j (Ri,j + γ 〈Φj , w〉) 2, where γ is a discount factor, rij is the random reward of transition from i to state j. Our proposed algorithm can be applied to the above problem, which can be formulated as the composition problem by taking
gj (w) =S [ 〈Φ1, w〉 , ..., 〈Φ2, w〉 , Pπ1,j (R1,j + γ 〈Φj , w〉) , ..., PπS,j (RS,j + γ 〈Φj , w〉) ]T ;
g (w) = S∑ j=1 gi (w) = y = [ y1 y2 ] ;
fi (y) =S‖y1,i − y2,i‖2.
In the experiments, parameters Pπ , Φ and R are randomly selected. We implement on three data with the size of n = 500, 1000, 1500. And we set |D1| = 0.95 ∗ n, 0.9 ∗ n, 0.8n, respectively for different value of n. We set b = |A|≈ n2/3 based on our theory analysis. Figure 4 and 5 show the experimental results, which demonstrate that our proposed method is better than the nonvariance reduction based methods SCGD and ASC-PG on both the objective value and the norm of the gradient.

Review summaries:
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.