Title: STOCHASTICALLY CONTROLLED COMPOSITIONAL GRADIENT FOR COMPOSITION PROBLEMS

Abstract: We consider composition problems of the form
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=1 G j (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.

1. INTRODUCTION:

In this paper, we study the following composition minimization problem, where f : R N → R is differentiable and possibly non-convex, each F i : R M → R is a smooth function, each G i : R N → R M is a mapping function, both the numbers of F i 's and G j 's are assumed to be n for simplicity We call G(x):= 1 n n j=1 G j (x) the inner function, and F (w):= 1 n n i=1 F i (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

min x∈R S 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: min x -E a [h(x; a)] + λVar a [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

EQUATION

where p i|t and q i|t are the conditional probabilities w.r.p. {z i } n i=1 and {x i } n i=1 , p i|t = d(zt,zi) j =t d(zt,zj ) , q i|t = d(xt,xi) j =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, E i∼[n],j∼ [n] [(∂G j (x)) T ∂F i ( G(x))] = ∇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(x k ) 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 F i and the number of G j 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 xs , 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 F i and G j 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.

1.1. RESULTS:

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 Algorithm Strongly Convex Non-convex SCGD (Wang et al., 2017) O(1/ 3/2 ) O(1/ 4 ) Acc-SCGD (Wang et al., 2017) O(1/ 5/4 ) O(1/ 7/2 ) ASC-PG (Liu et al., 2016) O(1/ 5/4 ) O(1/ 9/4 ) SC-SVRG (Liu et al., 2017b )

O n + L 2 f /µ 4 log (1/ ) O(n 4/5 / )

mini-batch VRSC-PG (Huo et al., 2018 )

O n + L 2 f /µ 3 log (1/ ) O(n 2/3 / ) mini-batch C-SAGA (Yuan et al., 2019) O n + L 2 f /µ 3 log (1/ ) O(n 2/3 / ) SCCG O min n, 1 µ 2 + L 2 f µ 2 min n, 1 µ 2 log (1/ ) O(min{ 1 9/5 , n 4/5 }) mini-batch SCCG (b= 1 µ ,min {n, 1 } 2 3 ) O min n, 1 µ 2 + L 2 f µ min n, 1 µ 2 log (1/ ) O(min{ 1 5/3 , n 2/3 })

Table 1 : Comparison of the query complexity with different algorithms. Note: µ and L f are defined in the Preliminary Section. b is the size of the mini-batch.

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 )} + L 2 f /µ 2 min{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 , n 4/5 / }), which is better than the result in (Liu et al., 2016) and comparable to the result in (Liu et al., 2017b) .

Mini-batch1 For the mini-batch version, the query complexity can be improved to some extent, that is O((min{n, 1/( µ 2 )} + L 2 f /(bµ 2 )min{n, 1/µ 2 }) log(1/ )). and O(min{1/ 9/5 , n 4/5 / }/b 1/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.

1.2. RELATED WORK:

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 of O( -7/2 ) for a general function and O( -5/4 ) for a strongly convex function. Liu et al. (2016) employed Nes-terov's method to accelerate the composition problem, reaching O( -5/4 ) and O( -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.

2. PRELIMINARIES:

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 (∂G j (x)) T ∇F i (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

G A (x) = 1 A 1≤j≤A G A[j] (x). We use E to denote the expectation, that is E A [v] = 1 A 1≤i≤A v A[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 E i , E j ,E A and E B 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 B p -Lipschitz, that is p(x) -p(y) ≤ B p x -y ; A function p is a L p -smooth, that is ∇p(x) -∇p(y) ≤ L p 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 B G , L F and L f be positive scalars, 2

• G j is B G -Lipschitz, j ∈ [n], that is G j (x) -G j (y) ≤ B G x -y . • F i is L F -smooth, i ∈ [n], that is ∇F i (x) -∇F i (y) ≤ L F x -y .

• For function F i (G(x)), there exists a constant L f satisfying (∂G j (x))

T ∇F i (G(x)) - (∂G j (y)) T ∇F i (G(y)) ≤ L f x -y , ∀i, j ∈ [n].

• We assume that i and j are independently and randomly selected from

[n], z ∈ R M , x ∈ R N , then E[(∂G j (x)) T ∇F i (z)] = (∂G(x)) T ∇F (z).

Furthermore, we define H 1 and H 2 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) -G i (x) 2 ≤ H 1 , 1 n 2 n j=1 n i=1 (∂G(x)) T ∇F (y) -(∂G j (x)) T ∇F i (y) 2 ≤ H 2 .

In the paper, we denote by x s k the k-th inner iteration at s-th epoch. But in each epoch analysis, we drop the superscript s and denote by x k for x s k . 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 B G , L F , and L f , that are irrelevant with the convergence rate.

3. STOCHASTICALLY CONTROLLED COMPOSITIONAL GRADIENT:

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 xs , 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 i k from [n] at the k-th iteration,

(∂G(x k )) T ∇F i k (G(x k )) -(∂G(x s )) T ∇F i k (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

Gk = G A (x k ) -G A (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 function G j and the outer function F i 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 D 1 and D 2 , which are independent with each other and randomly selected from [n], respectively. We define D = D 1 ∪D 2 as a new variable, which is important in analyzing the convergence. Firstly, D 1 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

Ĝk = G A (x k ) -G A (x s ) + G D1 (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 D 1 rather than [n]. Throughout the paper, we assume that |A| ≤ |D 1 |. Secondly, D 2 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

EQUATION

Algorithm 1 Stochastically Controlled Compositional Gradient (SCCG) for the strongly convex or non-convex composition problem Require: K, S, η , x0 and D = D 1 ∪ D 2 , where D 1 and D 2 are mini-batches.

for s = 0, 1, 2, • • • , S -1 do Sample from [n] for D times to form mini-batch D 1 Sample from [n] for D times to form mini-batch D 2 ∇ fD (x s ) = (∂G D1 (x s )) T ∇F D2 (G D1 (x s )) x 0 = xs for k = 0, 1, 2, • • • , K -1 do Sample from [n] to form mini-batch A Ĝk = G A (x k ) -G A (x s ) + G D1 (x s )

Uniformly and randomly pick i k and j k from [n] Compute the estimated gradient ∇ fk from (3.4)

x k+1 = x k -η∇ fk end for Update xs+1 = x K , or xs+1 = x r , r is randomly selected from [K -1] end for Output: xs

k is uniformly and randomly chosen from s ∈ {0, ..., S -1} and k ∈ {0, .., K -1}.

where i k and j k are randomly selected from [n] at the k-th iteration for functions F and G, respectively. Furthermore,

E ij ,j k A,D [∇ fk ] = ∇f (x k )

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).

3.1. SCCG FOR THE STRONGLY CONVEX CASE:

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

η ≤ µ/(135L 2 f ), the subset size of A is A = min{n, 128B 4 G L 2 F /µ 2 }, the subset size of D 1 and D 2 are both D = min n, 5 16B 4 G L 2 F H 1 + 4H 2 /(4 µ 2 ) , the number of the inner iter- ation is K ≥ 540L 2 f /µ 2 , the number of outer iteration is S ≥ 1/(log(1/ρ)) log(2E x0 -x * 2 / ). Then, the query complexity is (D + KA) S = O min n, 1 µ 2 + L 2 f µ 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 B 2 G , L 2 F , H 1 and H 2 , 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 complex- ity is O((1/( µ 2 ) + L 2 f /µ 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 + L 2 f /µ 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 + L 2 f n/µ 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.

3.2. SCCG FOR THE NONCONVEX CASE:

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/n 2/5 , 2/5 }, the size of the subset D 1 and

D 2 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 s k ) 2 ] ≤ , the query complexity is O min 1/ 9/5 , n 4/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).

3.3. MINI-BATCH VERSION OF SCCG:

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µ/(135L 2 f ), the number of the inner iteration is K ≥ 540L 2 f /(bµ 2 ), in order to obtain E xs -x * 2 ≤ , the query complexity is O min n, 1

µ 2 + L 2 f 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 η = b 3/5 min{1/n 2/5 , 2/5 }, the number of the inner iteration is K ≤ O b 1/2 /(η 3/2 ) , in order to obtain E[ ∇f (x s k ) 2 ] ≤ , the query complexity is (1/b 1/5 )O min 1/ 9/5 , n 4/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.

4. EXPERIMENTS:

In this section, we evaluate the performance of our proposed algorithm on the strongly convex and non-convex functions, respectively.

SCCG for strongly convex function 4 To verify the effectiveness of the algorithm, we use the mean-variance optimization in portfolio management 5 :

min x∈R d -1 n n i=1 r i , x + 1 n n i=1 ( r i , x -1 n n i=1 r i , x ) 2 ,

where

r i ∈ R N , i ∈ [n]

is the reward vector, and x ∈ R N is the invested quantity. In the experimental setting, we set n=3000, |A|≈ n 2/3 , |D 1 | = 2400, 2600, 2800, which are denoted as SCCG (2400), SCCG (2600) and SCCG (2800). The reward vectors are generated on Gaussian distribution 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 x i and x j as 1/(1

+ x i -x j 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 D 1 = D 2 in default and choose three different sizes of sample set D 1 , which are smaller than n. For example, for the case of mnist, we choose |D 1 | = 400, 600, 800, which are denoted as SCCG (400), SCCG (600) and SCCG (800). Furthermore, we also set |A|≈ n 2/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.

5. CONCLUSION:

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.

A TECHNICAL TOOL:

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 v 1 , ..., v n ∈ R d satisfy n i=1 v i = 0,

and A 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

E A 1 A b∈A v b 2 ≤ I(A<n) A 1 n n i=1 ||v i || 2 .

Furthermore, if elements in A are independently selected from [n] with replacement,, then

E A 1 A b∈A v b 2 = 1 An n i=1 ||v i || 2 .

Proof. Based on the n i=1 v i = 0, and permutation and combination, For the case that A is a non-empty, uniformly random subset of [n], we have

E A b∈A v b 2 =E A b∈A v b 2 + 1 C A n i∈[n] v i , C A-1 n-1 (A -1) n -1 i =j v j =A 1 n n i=1 v i 2 + A (A -1) n (n -1) i∈[n] v i , i =j v j =A 1 n n i=1 v i 2 + A (A -1) n (n -1) i∈[n] v i , -v i = A (n -A) (n -1) 1 n n i=1 v i 2 ≤AI (A < n) 1 n n i=1 v i 2 ,

where C n A refer to the number of the combination of n things taken A at a time without repetition. Thus, we have

E A 1 A b∈A v b 2 = 1 A 2 E A b∈A v b 2 ≤ I (A < n) A 1 n n i=1 v i 2 .

For the case that the element in A is randomly and independently selected from [n], we have

E A b∈A v b 2 =E A b∈A v b 2 + 2E A 1≤b<A v b , b<k≤A v k =B 1 n n i=1 v i 2 + 2E A 1≤b<A E [v] , b<k≤A v k =A 1 n n i=1 v i 2 + A (A -1) E [v] 2 (A.1) =A 1 n n i=1 v i 2 .

Based on Lemma 1, we can obtain the inequality with two-variables D 1 and D 2 , which are used for the gradient of f (x).

Lemma 2. If w 1 , ..., w n ∈ R M ×N and v 1 , ..., v n ∈ R M satisfy ( 1 n i∈[n] w i ) T ( 1 n j∈[n] v j ) = wT v, and D = [D 1 , D 2 ]

is a non-empty, uniform random subset consist of D 1 and D 2 , which are independently and uniformly selected from

[n], D = |D 1 | = |D 2 |, then E D 1 |D 1 | |D 2 | d1∈D1 w d1 T d2∈D2 v d2 -wv 2 =E D 1 D 2 [d1,d2]∈D (w d1 ) T v d2 -wT v 2 ≤ I D 2 < n 2 D 2 1 n 2 n i,j=1 (w i ) T v j -wT v 2 .

B BOUND ANALYSIS OF SCCG FOR THE COMPOSITION PROBLEM B.1 BOUNDS ANALYSIS OF THE ESTIMATED FUNCTION AND THE GRADIENT:

Here, we mainly give different kinds of bounds for the proposed algorithm, such as

E A,D1 Ĝk - G(x k ) 2 , E D E A,i k ,j k [∇ fk ] -∇f (x k ) 2 and E i k ,j k ,A,D ∇ fk -∇f (x k ) 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 B G , B F , L G , L F and L f 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 i k , j k , A and D for the expectation with E in the proof.

Lemma 3. Suppose Assumption 1 holds, for Ĝk defined in (3.3) with D = |D 1 | and A = |A|, we have

E A,D1 Ĝk -G(x k ) 2 ≤ 4 I (A < n) A B 2 G E x k -xs 2 + 6 I (D < n) D H 1 .

Proof. By the definition of Ĝk in (3.3), we have

E Ĝk -G(x k ) 2 =E Ĝk -G D1 (x k ) + G D1 (x k ) -G(x k ) 2 1 ≤2E Ĝk -G D1 (x k ) 2 + 2E G D1 (x k ) -G(x k ) 2 2 ≤4 I (A < n) A B 2 G E x k -xs 2 + 6 I (D < n) D H 1 ,

where 1 follows from ||a 1 + a 2 || 2 ≤ 2a 2 1 + 2a 2 2 ; 2 is based on Lemma 1 and the following inequality: Through adding and subtracting the term G(x k ) -G(x s ), we have

E Ĝk -G D1 (x k ) 2 =E G A (x k ) -G A (x s ) + G D1 (x s ) -G D1 (x k ) 2 =E G A (x k ) -G A (x s ) -(G(x k ) -G(x s )) + (G(x k ) -G(x s )) + G D1 (x s ) -G D1 (x k ) 2 1 ≤2E G A (x k ) -G A (x s ) -(G(x k ) -G(x s ))) 2 + 2E G D1 (x s ) -G D1 (x k ) -(G(x s ) -G(x k )) 2 2 ≤2 I (A < n) A E i G i (x s ) -G i (x k ) 2 + 2E G D1 (x s ) -G(x s ) 2 + 2E -G D1 (x k ) + G(x k ) 2 3 ≤2 I (A < n) A B 2 G E x k -xs 2 + 4 I (D < n) D H 1 ,

where 1 follows from ||a + b|| 2 ≤ 2a 2 + 2b 2 ; 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 x k are independent; and D and xs are independent.

Lemma 4. Suppose Assumption 1 holds, for Ĝk defined in (3.3) and ∇ fk defined in (3.4) with

D = [D 1 , D 2 ] and D = |D 1 | = |D 2 |, we have E D E A,i k ,j k [∇ fk ] -∇f (x k ) 2 ≤4B 4 G L 2 F 4 I (A < n) A E x k -xs 2 + 32B 2 G L 2 F I(D < n) D H 1 + 4 I(D 2 < n 2 ) D 2 H 2 .

Proof. Through adding and subtracting the terms of

(∂G(x k )) T ∇F (G(x k )), (∂G D1 (x s )) T ∇F D1 (G(x s )), (∂G(x s )) T ∇F (G(x s )),

we have

E D E A,i k ,j k ∇ fk -∇f (x k ) 2 =E (∂G(x k )) T ∇F ( Ĝk ) -(∂G(x s )) T ∇F (G D1 (x s )) + ∇ fD (x s ) -∇f (x k ) 2 1 ≤4E (∂G(x k )) T ∇F ( Ĝk ) -(∂G(x k )) T ∇F (G(x k )) 2 + 4E (∂G(x s )) T ∇F (G(x s )) -(∂G(x s )) T ∇F (G D1 (x s )) 2 + 4E ∇ fD (x s ) -(∂G D1 (x s )) T ∇F D2 (G(x s )) 2 + 4E (∂G D1 (x s )) T ∇F D2 (G(x s )) -(∂G(x s )) T ∇F (G(x s )) 2 2 ≤4B 2 G L 2 F E Ĝk -G(x k ) 2 + 4B 2 G L 2 F E G(x s ) -G D1 (x s ) 2 + 4B 2 G L 2 F E G(x s ) -G D1 (x s ) 2 + 4 I(D 2 < n 2 ) D 2 H 2 3 ≤4B 4 G L 2 F 4 I (A < n) A E x k -xs 2 + 32B 2 G L 2 F I(D < n) D H 1 + 4 I(D 2 < n 2 ) D 2 H 2 ,

where 1 follows from ||a 1 + a 2 + a 3 + a 4 || 2 ≤ 4a 2 1 + 4a 2 2 + 4a 2 3 + 4a 2 4 ; 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 that A and x k are independent; and D and xs are independent.

Lemma 5. Suppose Assumption 1 holds, for Ĝk defined in (3.3) and ∇ fk defined in (3.4) with

D = [D 1 , D 2 ] and D = |D 1 | = |D 2 |, we have E i k ,j k ,A,D ∇ fk -∇f (x k ) 2 ≤40B 2 G L 2 F I(D < n) D H 1 + 5 I(D 2 < n 2 ) D 2 H 2 +5B 4 G L 2 F L 2 f B 4 G L 2 F + 4 I (A < n) A E x k -xs 2 .

Proof. Through adding and subtracting the term of (∂G j (x k )) T ∇F i (G(x k )), (∂G j (x s )) T ∇F i (G(x s )), (∂G(x s )) T ∇F (G(x s )), (∂G D1 (x s )) T ∇F D1 (G(x s )) (Note that, D and xs are independent), we have

E ∇ fk -∇f (x k ) 2 =E (∂G j (x k )) T ∇F i ( Ĝk ) -(∂G j (x s )) T ∇F i (G D1 (x s )) + ∇ fD (x s ) -∇f (x k ) 2 1 ≤5E (∂G j (x k )) T ∇F i (G(x k )) -(∂G j (x s )) T ∇F i (G(x s )) -∇f (x k ) -(∂G(x s )) T ∇F (G(x s )) 2 + 5E (∂G j (x k )) T ∇F i ( Ĝk ) -(∂G j (x k )) T ∇F i (G(x k )) 2 + 5E (∂G j (x s )) T ∇F i (G(x s )) -(∂G j (x s )) T ∇F i (G D1 (x s )) 2 + 5E ∇ fD (x s ) -(∂G D1 (x s )) T ∇F D2 (G(x s )) 2 + 5E (∂G D1 (x s )) T ∇F D2 (G(x s )) -(∂G(x s )) T ∇F (G(x s )) 2 2 ≤5L 2 f E x k -xs 2 + 5B 2 G L 2 F E Ĝk -G(x k ) 2 + 5B 2 G L 2 F E G(x s ) -G D1 (x s ) 2 + 5B 2 G L 2 F E G(x s ) -G D1 (x s ) 2 + 5 I(D 2 < n 2 ) D 2 H 2 3 ≤5B 4 G L 2 F L 2 f B 4 G L 2 F + 4 I (A < n) A E x k -xs 2 + 40B 2 G L 2 F I(D < n) D H 1 + 5 I(D 2 < n 2 ) D 2 H 2 ,

where 1 follows from

||a 1 + a 2 + a 3 + a 4 + a 5 || 2 ≤ 5a 2 1 + 5a 2 2 + 5a 2 3 + 5a 2 4 + 5a 2 5 ; 2 is based on E[ X -E[X] 2 ] = E[X 2 -E[X] 2 ] ≤ E[X 2

], the smoothness of F i , 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.

C PROOF OF SCCG METHOD FOR COMPOSITION PROBLEM C.1 PROOF OF SCCG METHOD FOR STRONGLY CONVEX COMPOSITION PROBLEM:

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.

C.1.1 CONVERGENCE ANALYSIS:

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 xs are independent.

Theorem 3. Suppose Assumption 1 holds, in Algorithm 1, let h > 0, η > 0, A = |A|, D = |D 1 | = |D 2 |,

K is the number of the inner iteration, x * is the optimal point, we have

E xS -x * 2 ≤ ρ S E x0 -x * 2 + ρ 3 ρ 1 1 -ρ S 1 -ρ ,

where ρ = ( 1 K + ρ 2 )/ρ 1 , ρ 2 and ρ 3 defined (V , V 1 are defined in (C.4) and (C.5).)

ρ 1 = 2µ -h -4V 1 h -12L 2 f + 10V η η, (C.1) ρ 2 =2 2V 1 h + 5 L 2 f + V η η, (C.2) ρ 3 = 1 h η 4 5 V 1 + 2η 2 V 1 . (C.3)

Proof. By the update of x k in Algorithm 1, we have

E x k+1 -x * 2 =E x k -x * 2 -2ηE ∇ fk , x k -x * + η 2 E ∇ fk 2 =E x k -x * 2 -2ηE ∇f (x k ) + E A,i,j ∇ fk -∇f (x k ), x k -x * + η 2 E ∇ fk 2 =E x k -x * 2 -2ηE ∇f (x k ), x k -x * -2ηE E A,i,j ∇ fk -∇f (x k ), x k -x * + η 2 E ∇ fk + ∇f (x k ) -∇f (x k ) 2 1 ≤E x k -x * 2 -2ηµE x k -x * 2 + η 1 h E E A,i,j ∇ fk -∇f (x k ) 2 + hηE x k -x * 2 + 2η 2 E ∇f (x k ) 2 + E ∇ fk -∇f (x k ) 2 =E x k -x * 2 -(2ηµ -hη) E x k -x * 2 + η 1 h E E A,i,j ∇ fk -∇f (x k ) 2 + 2η 2 E ∇f (x k ) -∇f (x * ) 2 + E ∇ fk -∇f (x k ) 2 2 ≤E x k -x * 2 -(2ηµ -hη) E x k -x * 2 + η 1 h 4V x k -xs 2 + V 2 + 2η 2 L 2 f E x k -x * 2 + 5 L 2 f + V x k -xs 2 + V 1 =E x k -x * 2 -2µ -h -4V 1 h -12L 2 f + 10V η ηE x k -x * 2 + 2 2V 1 h + 5 L 2 f + V η ηE xs -x * 2 + 1 h ηV 2 + 2η 2 V 1 ,

where

V =B 4 G L 2 F 4 I (A < n) A , (C.4) V 1 =40B 2 G L 2 F I(D < n) D H 1 + 5 I(D 2 < n 2 ) D 2 H 2 , (C.5) V 2 =32B 2 G L 2 F I(D < n) D H 1 + 4 I(D 2 < n 2 ) D 2 H 2 = 4 5 V 1 , (C.6) 1 is based on ||a 1 + a 2 || 2 ≤ 2a 2 1 + 2a 2 2 and a 1 , a 2 ≤ h||a 1 || 2 + 1 h ||a 2 || 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 x K -x * 2 ≤ E x 0 -x * 2 -ρ 1 K-1 k=0 E x k -x * 2 + Kρ 2 E xs -x * + Kρ 3 ,

where

ρ 1 = 2µ -h -4V 1 h -12L 2 f + 10V η η, ρ 2 =2 2V 1 h + 5 L 2 f + V η η, ρ 3 = 1 h ηV 2 + 2η 2 V 1 .

For x 0 = xs , by arranging, we have

ρ 1 E xs+1 -x * 2 ≤ 1 K E x 0 -x * 2 + ρ 2 E xs -x * 2 + ρ 3 - 1 K E x K -x * 2 ≤ 1 K + ρ 2 E xs -x * 2 + ρ 3 .

we assume that ρ 1 > 0 in (C.1), then we can obtain

E xS -x * 2 ≤ρ S E x0 -x * 2 + ρ 3 ρ 1 S s=0 ρ s ≤ρ S E x0 -x * 2 + ρ 3 ρ 1 1 -ρ S 1 -ρ , (C.7)

where ρ = ( 1 K + ρ 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 xS 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, if D = 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) .

Proof of Theorem 1:

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 xS -x * 2 ≤ ρ S E x0 -x * 2 + ρ 3 ρ 1 S s=0 ρ s ≤ ρ S E x0 -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, 128B 4 G L 2 F 1 µ 2 ,

based on the setting of h, we require that V /h < µ 16 . Thus, we have

V = B 4 G L 2 F 4 I(A<n) A ≤ 8B 4 G L 2 F I(A<n) A ≤ 1 16 µ 2 . For V defined in (C.4), if A < n, we have A ≥ 128B 4 G L 2 F 1 µ 2 , otherwise, A = n satisfy the requirement. Thus, we have A = min n, 128B 4 G L 2 F 1 µ 2 . (c) η ≤ 3µ 53L 2 f , back to the target of ρ 1 > 0, we require that η ≤ 3µ 53L 2 f ≤ 3 4 µ 12L 2 f + 10 8 L 2 f ≤ 3 4 µ 12L 2 f + 10 8 µ 2 = µ-4 1 µ V 12L 2 f +10V = 2µ-h-4 1 h V 2L 2 f +10(L 2 f +V )

, note that µ ≤ L f 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 ≥ µ -2L 2 f η - 1 4 µ + 10 L 2 f + 1 16 µ 2 η η ≥ 3 4 µ - 101 8 L 2 f η η, (C.9) ρ 2 ≤4 1 µ η 1 16 µ 2 + 10 L 2 f + 1 16 µ 2 η 2 ≤ 1 4 µ + 10 L 2 f + 1 16 µ 2 η η ≥ 1 4 µ + 85 8 L 2 f η η. (C.10)

We require that ρ = 1 Kρ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 η ≤ µ 135L 2 f . (b) In order to 1 Kρ1 < 1 2 , that is 1 Kρ 1 < 1 2Kρ 2 ≤ 1 2K 1 4 µ + 10 L 2 f + 1 16 µ 2 η η ≤ 1 2K 1 4 µ + 85 8 L 2 f η η ≤ 1 2K 1 4 µη < 1 2 .

Thus, we have K ≥ 540

EQUATION

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 -1 K -ρ 2 ≤ ρ 3 ρ 1 -1 K -1 2 ρ 1 ≤ ρ 3 1 2 ρ 1 -1 K ≤ 2ρ 3 ρ 1 ≤ 1 2 .

Based on the bound of ρ 1 in (C.9), the definition of V 1 in (C.5) and the step size η mentioned above, we have i. For V

2 1 µ ηV 2 + 2η 2 V 1 ρ 1 = 2 1 µ V 2 + 2ηV 1 3 4 µ -101 8 L 2 f η = 4 5 1 µ V 1 + 2ηV 1 3 4 µ -101 8 L 2 f η = 4 5µ + 2η V 1 3 4 µ -101 8 L 2 f η ≤ , thus, we have V 1 ≤ 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 µ 135L 2 f 4 5µ + 2 µ 135L 2 f ≤ 3 4 µ -101 8 L 2 f η 4 5µ + 2η ii. If D < n, we can obtain D ≥ 5 4 µ 2 20B 4 G L 2 F H 1 + 5H 2 , other- wise D = 0, the above inequality is correct. Thus, we obtain D = min n, 16B 4 G L 2 F H 1 + 4H 2 5 4 µ 2 . (b) In order to ensure ρ S E x0 -x * 2 ≤ 1

2 , we need the number of the outer iterations

S ≥ 1 log (1/ρ) log 2E x0 -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 + L 2 f µ 2 min n, 1 µ 2 log (1/ ) . C.2 PROOF OF SCCG METHOD FOR NON-CONVEX COMPOSITION PROBLEM C.2.1 RELATED BOUNDS

Lemma 6. Suppose Assumption 1 hold, in Algorithm 1, we can obtain the following new sequence with respect to f

(x k ) and ||x k -xs || 2 , let h > 0, η > 0, A = |A| and D = |D 1 | = |D 2 |, we have E[f (x k+1 )] + c k+1 E x k+1 -xs 2 ≤ E[f (x k )] + c k E x k -xs 2 -u k ∇f (x k ) 2 + J k ,

where

W =B 4 G L 2 F 4 I (A < n) A + 4 I (D < n) D , (C.11) c k =c k+1 1 + 2 h + 4hW η + 10 L 2 f + W η 2 + 2W η + 5(L 2 f + W )L f η 2 , (C.12) u k = 1 2 -hc k+1 η -(L f + 2c k+1 ) η 2 , (C.13) W 1 =20B 2 G L 2 F I(D < n) D H 1 + 5 I(D 2 < n 2 ) D 2 H 2 , (C.14) J k = 1 2 + hc k+1 4 5 W 1 η + (L f + 2c k+1 ) W 1 η 2 . (C.15)

Proof. Consider the upper bound of f (x k+1 ) and x k+1 -xs 2 , respectively,

• Base on the smoothness of f in Assumption 1 and take expectation with respective to i k , j k , we have

E i,j [f (x k+1 )] ≤E [f (x k )] -ηE ∇f (x k ), ∇ fk + L f 2 η 2 E ∇ fk 2 =E [f (x k )] -ηE ∇f (x k ), ∇ fk -∇f (x k ) + ∇f (x k ) + L f 2 η 2 E ∇ fk 2 =E [f (x k )] -ηE ∇f (x k ), ∇f (x k ) -η ∇f (x k ), E ∇ fk -∇f (x k ) + L f 2 η 2 E ∇ fk -∇f (x k ) + ∇f (x k ) 2 ≤E [f (x k )] -ηE ∇f (x k ) 2 + 1 2 ηE ∇f (x k ) 2 + 1 2 ηE E A,i,j ∇ fk -∇f (x k ) 2 + L f 2 η 2 2E ∇f (x k ) 2 + 2E ∇ fk -∇f (x k ) 2 =E [f (x k )] - 1 2 ηE ∇f (x k ) 2 + 1 2 ηE E A,i,j ∇ fk -∇f (x k ) 2 + L f η 2 E ∇f (x k ) 2 + E ∇ fk -∇f (x k ) 2 =E [f (x k )] - 1 2 η -L f η 2 E ∇f (x k ) 2 + 1 2 ηE E A,i,j ∇ fk -∇f (x k ) 2 + L f η 2 E ∇ fk -∇f (x k ) 2 ,

where the last inequality is based on

||a 1 + a 2 || 2 ≤ 2a 2 1 + 2a 2 2 .

• Base on the update of x k in Algorithm 1 and take expectation with respective to i k , j k , we have,

E i.j x k+1 -xs 2 =E x k -xs 2 -2ηE ∇ fk , x k -xs + η 2 E ∇ fk 2 =E x k -xs 2 -2ηE ∇ fk -∇f (x k ) + ∇f (x k ), x k -xs ] + η 2 E ∇ fk 2 =E x k -xs 2 -2ηE ∇f (x k ), x k -xs ] -2η E ∇ fk -∇f (x k ), x k -xs ] + η 2 E ∇ fk -∇f (x k ) + ∇f (x k ) 2 ≤E x k -xs 2 + hη ∇f (x k ) 2 + hη E ∇ fk -∇f (x k ) 2 + 2 h ηE x k -xs 2 + η 2 2E ∇f (x k ) 2 + 2E ∇ fk -∇f (x k ) 2 = 1 + 2 h η E x k -xs 2 + hη + 2η 2 E ∇f (x k ) 2 + hηE E ∇ fk -∇f (x k ) 2 + 2η 2 E ∇ fk -∇f (x k ) 2 ,

where the inequality is based on 2 a 1 , b 2 ≤1/h a 1 2 +h a 2 2 , ∀h > 0, and ||a

1 +a 2 || 2 ≤ 2a 2 1 + 2a 2 2 .

Combine above equalities and Lemma 4, 5, we form a Lyapunov function,

E[f (x k+1 )] + c k+1 E x k+1 -xs 2 =E[f (x k )] - 1 2 η -L f η 2 ∇f (x k ) 2 + 1 2 η E ∇ fk -∇f (x k ) 2 + L f η 2 ∇ fk -∇f (x k ) 2 + c k+1 1 + 2 h η E x k -xs 2 + hη + 2η 2 ∇f (x k ) 2 + hη E ∇ fk -∇f (x k ) 2 + 2η 2 ∇ fk -∇f (x k ) 2 =E[f (x k )] + c k+1 1 + 2 h η E x k -xs 2 - 1 2 -c k+1 h η -(L f + 2c k+1 ) η 2 ∇f (x k ) 2 + L f η 2 + 2η 2 c k+1 ∇ fk -∇f (x k ) 2 + 1 2 η + hηc k+1 E ∇ fk -∇f (x k ) 2 ≤E[f (x k )] + c k E x k -xs 2 -u k ∇f (x k ) 2 + J k ,

where

u k = 1 2 -hc k+1 η -(L f + 2c k+1 ) η 2 ; W 1 =40B 2 G L 2 F I(D < n) D H 1 + 5 I(D 2 < n 2 ) D 2 H 2 ; W 2 = 4 5 W 1 ; J k = 1 2 + hc k+1 W 2 η + (L f + 2c k+1 ) W 1 η 2 ; W =B 4 G L 2 F 4 I (A < n) A ; c k =c k+1 1 + 2 h + 4hW η + 10 L 2 f + W η 2 + 2W η + 5(L 2 f + W )L f η 2 .

Based on the above inequality with respect to the sequence E[f (x k )] + c k E x k -xs 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 (x k ) and ||x k -xs || 2 . K is the number of inner iterations, S is the number of inner iterations, we have

u 0 E[ ∇f (x s k ) 2 ] ≤ f (x 0 ) -f (x * ) KS + J 0 ,

where xs k is the output point, J 0 and u 0 are defined in (C.15) and (C.13).

Proof. Based on the update for c k in (C.12), we can see that c k > c k+1 . As c k is a decreasing sequence, we have u 0 < u k and J k < J 0 . Then, we get

u 0 E[ ∇f (x k ) 2 ] ≤ E[f (x k )] + c k E[ x k -xs 2 ] -(E[f (x k+1 )] + c k+1 E[ x k+1 -xs 2 ]) + J 0 .

Sum from k = 0 to k = K -1, we can get

1 K K-1 k=0 uE[ ∇f (x k ) 2 ] ≤ E[f (x 0 )] -(E[f (x K )] + c K E[ x K -xs 2 ]) K + J 0 ≤ E[f (x 0 )] -E[f (x K )] K + J 0 .

Since x 0 = xs , let xs+1 = x K , we obtain,

1 K K-1 k=0 u 0 E[ ∇f (x k ) 2 ] ≤ E[f (x s )] -E[f (x s+1 )] K + J 0 .

Summing the outer iteration from s = 0 to S -1, we have

u 0 E[ ∇f (x s k ) 2 ] = 1 S S-1 s=0 1 K K-1 k=0 u 0 E[ ∇f (x s k ) 2 ] + J 0 ≤ E[f (x 0 )] -E[f (x S )] KS + J 0 ≤ f (x 0 ) -f (x * ) KS + J 0 ,

where x s k indicates the s-th outer iteration at k-th inner iteration, and xs k is uniformly and randomly chosen from s = {0, ..., S -1} and k={0, .., K -1}.

C.2.2 CONVERGENCE ANALYSIS:

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 .

Proof of Theorem 2:

Proof. In order to have

E[ ∇f (x s k ) 2 ] ≤ , that is E[ ∇f (x s k ) 2 ] ≤ L f (f (x0)-f (x * )) u0SK + J 0 /u 0 ≤ 2 + 2 ≤ ,

we consider the corresponding parameters' setting:

1. For the first term, consider c k defined in (C.12) define c k = c k+1 Y + U , for k = K, we have

c K = 1 Y K c 0 + U Y -1 - U Y -1 ,

where

Y =1 + 2 h + 4hW η + 10 B 4 G L 2 F + W η 2 , U =2W η + 5(L 2 f + W )L f η 2 > 0. By setting c K → 0, we obtain c 0 = U Y K Y -1 - U Y -1 = U Y K -1 Y -1 .

Then, putting the Y and U into the above equation. We have → e,6 as t 1 , t 2 → +∞ and t 1 t 2 < 1, and the function is also the increasing function with an upper bound of e, we require

EQUATION

K < 1/ 2 h + 4hW η + 10 L 2 f + W η 2 , (C.17)

thus, we have C < e -1. (b) For u 0 defined in (C.13), in order to keep u k > 0, we need to keep c 0 h < 1/4. If c 0 h < 1/4, there exits a constant ũ such that u 0 = ũη. In order to satisfy c 0 h < 1/4, combine with (C.16) and C < e -1, that is

c 0 h ≤ 2W + 5(L 2 f + W )L f η 2 h + 4hW + 10 L 2 f + W η h (e -1) ≤ 1 4 , i. By setting h = 1 5 √ L 3 f η

, there exist w > 0, based on above inequality, we have

W ≤ 16L 3 f η + 50L 3.5 f √ ηη 9.6 + 34L 3 f η -50 L 3 f ηη < wL 3 f η

Thus, combine with the definition of W in (C.11), we require that

W = B 4 G L 2 F 4 I(A < n) A ≤ 8B 4 G L 2 F I(A < n) A ≤ wL 3 f η = O L 3 f η . If A < n, we require A ≥ O B 4 G L 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 L 3 f η + 4 5 √ L 3 f η wL 3 f η η + 10 L 2 f + wL 3 f η η 2 = 1 10 L 3 f η + 4 5 L 3 f η η + 10 L 2 f + η η 2 = O 1 (L f η) 3/2 .

2. For the second term about J 0 , as u 0 = w 1 η, we require

J 0 ũη = 1 ũ 1 2 + hc 0 W 2 + (L f + 2c 0 ) W 1 η ≤ 1 ũ W 1 3 5 + L f η + 1 2 η √ η ≤ 1 ũ 20B 2 G L 2 F H 1 + 5H 2 3 5 + L f η + η √ η I(D < n) D ≤ 1 2 , Then, if D < n, we require that D ≥ 2 ũ 20B 2 G L 2 F H 1 + 5H 2 3 5 + 1 2 L f η + c 0 η √ η = O 1 .

Thus, we set D = min {n, O(1/ )}.

3.. Based on the first term:

L f (f (x0)-f (x * )) ηSK ≤ 1 2 , the total number of iteration is T = SK = 2L f (f (x0)-f (x * )) η .

Thus, based on the above parameters' setting, we can ensure that E

[ ∇f (x s k ) 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 , n 4/5 ,

where the optimal η = min 1/n 2/5 , 2/5 .

D PROOF FOR THE MINI-BATCH OF THE SCCG TO THE COMPOSITION:



PROBLEM:

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 Ĝk defined in (3.3) and Λ defined in Algorithm 2 with

D = [D 1 , D 2 ] and D = |D 1 | = |D 2 |, we have E i k ,j k ,A,D Λ -∇f (x k ) 2 ≤5B 4 G L 2 F L 2 f bB 4 G L 2 F + 4 I (A < n) A + 4 I (D < n) D E x k -xs 2 + 20B 2 G L 2 F I(D < n) D H 1 + 5 I(D 2 < n 2 ) D 2 H 2 ,

Proof. Through adding and subtracting the term of

1 b (i,j)∈I b (∂G j (x k )) T ∇F i (G(x k )), 1 b (i,j)∈I b (∂G i (x s )) T ∇F i (G(x s )), and (∂G(x s )) T ∇F (G(x s )), (∂G D1 (x s )) T ∇F D1 (G(x s )),

we have

E Λ -∇f (x k ) 2

Algorithm 2 Mini-batch version of SCCG Require: K, S, η (learning rate), x0 and D 

= [D 1 , D 2 ] for s = 0, 1, 2, • • • , S -1 do Sample from [n] for D times to form mini-batch D 1 Sample from [n] for D times to form mini-batch D 2 ∇ fD (x s ) = (∂G D1 (x s )) T ∇F D2 (G D1 (x s )) x 0 = xs for k = 0, 1, 2, • • • , K -1 do Sample from [n] to form mini-batch A Ĝk = G A (x k ) -G A (x s ) + G D1 (x s ) Λ 0 = 0 for t=1,...,

Λ t+1 = Λ t + ∇ fk end for Λ = Λ b /b x k+1 = x k -ηΛ end for Update xs+1 = x K , or xs+1 = x r , r is randomly selected from [K -1] end for Output: xs

k is uniformly and randomly chosen from s ∈ {0, ..., S -1} and k ∈ {0, .., K -1}.

1 ≤5E 1 b (i,j)∈I b (∂G j (x k )) T ∇F i (G(x k )) -(∂G j (x s )) T ∇F i (G(x s )) -∇f (x k ) -(∂G(x s )) T ∇F (G(x s )) 2 + 5E 1 b (i,j)∈I b (∂G j (x k )) T ∇F i ( Ĝk ) -(∂G j (x k )) T ∇F i (G(x k )) 2 + 5E 1 b (i,j)∈I b (∂G j (x s )) T ∇F i (G(x s )) -(∂G j (x s )) T ∇F i (G D1 (x s )) 2 + 5E ∇ fD (x s ) -(∂G D1 (x s )) T ∇F D2 (G(x s )) 2 + 5E (∂G D1 (x s )) T ∇F D2 (G(x s )) -(∂G(x s )) T ∇F (G(x s )) 2 2 ≤ 5 b L 2 f E x k -xs 2 + 5B 2 G L 2 F E Ĝk -G(x k ) 2 + 5B 2 G L 2 F E G(x s ) -G D1 (x s ) 2 + 5B 2 G L 2 F E G(x s ) -G D1 (x s ) 2 + 5 I(D 2 < n 2 ) D 2 H 2 3 ≤5B 4 G L 2 F L 2 f bB 4 G L 2 F + 4 I (A < n) A E x k -xs 2 + 40B 2 G L 2 F I(D < n) D H 1 + 5 I(D 2 < n 2 ) D 2 H 2 ,

where 1 follows from

||a 1 + a 2 + a 3 + a 4 + a 5 || 2 ≤ 5a 2 1 + 5a 2 2 + 5a 2 3 + 5a 2 4 + 5a 2 5 , and 2 is based on E[ X -E[X] 2 ] = E[X 2 -E[X] 2 ] ≤ E[X 2 ]

and Lemma 1, the smoothness of F i , 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. Note that, consider the function g (x) = 1 1+x 2 , its gradient is ∇g (x) = 2x (1+x 2 ) 2 . For different value of x, we can see that

Proof of Corollary 2:

|x| ≥ 1 ⇒ 1 + x 2 2 ≥ x; |x| < 1 ⇒ 1 + x 2 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 D 1 = D 2 in default and choose three different sizes of sample set D 1 , which are smaller than n. For example, for the case of mnist, we choose |D 1 | = 400, 600, 800, which are denoted as SCCG (400), SCCG (600) and SCCG (800). Furthermore, we also set |A|≈ n 2/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.

E.3 REINFORCEMENT LEARNING:

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 s 1 , V π (s 1 ) = E π {R s1,s2 + γV π (s 2 ) |s 2 } , s 1 , s 2 ∈ [S],

where R s1,s2 is the reward of moving from state s 1 to s 2 , and the expectation is taking over state s 2 conditioned on state s 1 . We assume V π (s) ≈Φ T s w * for some w * ∈ R d , 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 (R i,j + γ Φ j , w )   2 ,

where γ is a discount factor, r ij 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 g j (w) =S Φ 1 , w , ..., Φ 2 , w , P π 1,j (R 1,j + γ Φ j , w ) , ..., P π S,j (R S,j + γ Φ j , w ) T ; g (w) = S j=1 g i (w) = y = y 1 y 2 ;

f i (y) =S y 1,i -y 2,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 |D 1 | = 0.95 * n, 0.9 * n, 0.8n, respectively for different value of n. We set b = |A|≈ n 2/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.

:

b denotes the size of the mini-batch, can be obtained through the η ≤ 1 from Theorem 1 and Theorem

In 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.

The parameters' setting can be referred to Theorem 1 and Theorem 2 for the strongly convex and nonconvex function, respectively.

Our 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.

This formulation is just used to verify our proposed algorithm. In appendix, we show the bounded Jacobian.

Here the 'e' is the Euler number, approximate to 2.718.

This formulation is just used to verify our proposed algorithm.

Figures and Tables:

Figure 1: Strongly convex: Comparison of the gap between the function value and the optimal value among SCGD, ASC-PG and SCCG methods. Dataset (from left to right): condition numbers of the covariance matrix are set κ cov =10, 30 and 50, respectively.

C.16) where C = Y K -1. Because c 0 has the influence on the parameters such as K, C and u 0 , we analyze them separately, (a) For K and C, based on the character of function 1 + 1 t2 t1

Figure 3: Non-convex: Comparison of the objective function between SCGD, ASC-PG and SCCG; Dataset (from left to right): mnist, olivettifaces and coil20.

Figure 4: Reinforcement Learning application: Comparison of the objectively values between SCGD, ASC-PG and SCCG (including three different values of |D 1 |= 0.95 * n, 0.9 * n, 0.8n); Dataset (from left to right): n=500,1000, and 1500.

b do Uniformly and randomly pick i k and j k from [n] Compute the estimated gradient ∇ fk from (3.4)

Table content: <table/>

Peer review (iclr2020):
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.