Stochastically Controlled Compositional Gradient for the Composition problem
Authors: Liu Liu
Ji Liu
Cho-Jui Hsieh
Dacheng Tao
Venue:  (2020)
Keywords: Non-convex optimisation
Composition problem
Stochastically controlled compositional gradient

Abstract: We consider  composition problems of the form  $\frac{1}{n}\sum\nolimits_{i= 1}^n F_i(\frac{1}{n}\sum\nolimits_{j = 1}^n G_j(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 $\frac{1}{n}\sum\nolimits_{j = 1}^n{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.

Under review as a conference paper at ICLR 2020
STOCHASTICALLY CONTROLLED COMPOSITIONAL GRADIENT FOR COMPOSITION PROBLEMS
Anonymous authors Paper under double-blind review
ABSTRACT
We consider composition problems of the form F(E Composition optimization arises in many important machine learning applica- tions: reinforcement learning, variance- aware learning, nonlinear embedding, and many others. Both gradient descent and stochastic gradient descent are straight- forward solution, but both require to compute 1/ Σø= Gj(z) in each single it- eration, which is inefficient-cspeciallly when n is large. Therefore, with the aim of significantly reducing the query complexity of such problems, we designed 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 mini-batch version of the proposed method that improves query complexity with respect the size of the mini-batch. Comprehensive experiments demonstrate the superiority of the proposed method over existing methods.
INTRODUCTION
In this paper, we study the following composition minimization problem, def
miH
[(x] - F(G(=)
def Σ F.
n Σ c.)
(1.1)
ZERN
where f: RN + is differentiable and possibly non-convex, each F;: RM + R is a smooth function, each G RN - RM is mapping function, both the numbers of Ft's and Gj's are assumed to be for simplicity We call G(z):= E/= Gz(z) the inner function, and F(w): 1 - P:(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 x S system of Bellman equations Wang et al. (2017) can be written min ||E[B] æ B[b]12, where E[B] I >Pr Y (0,1) is discount factor, pa is the transition probability under policy म, and B(M] is the expected state transition reward. This is one of key problems in reinforcement learning for evaluating the value of policy π.
(risk-averse learning) The risk-averse learning Lian et (2017) aims to maximize the expected return while control the variance (or risk) in the meantime:
min, Eg [x(:; a)] + AVrr, a)],
where h(z; a) is the loss function including a random variable À > 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 low dimensional space by minimizing the KL divergence. It is non-convex composition optimization
ming (L |l q.xc)
Σ ΣV Paje log Pije
Paje
(1.2)
gilt
where Pijt and dijt the conditional probabilities w.r.p.
{ and fxa )

---

Under review as a conference paper at ICLR 2020
d(2).2)) Eezr d())))y)) Oile
d(at mx))
Pile
Σ Sygt d(a).)y))
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 straight- forward approaches are the gradient descent (GD) and the stochastic gradient descent (SGD). How- ever, 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, [x [O)))(()))))) aP. [()( A Vf(x), where Giz)is the estimation of ((z). The key to solving this composition objective is how to es- timate the value of (( and its Jacobian with high accuracy using only few samples in each iteration.
Recently, many stochastic optimization methods solving the composition problem have been devel- oped, such as the stochastic gradient based method and the variance-reduction based method. For example, stochastic compositional gradient descent (SCGD) (Wang al., 2017: Liu al., 2016) estimates the inner function G(x) by using an iterative weighted average of the past values of G(r), and then performs the stochastic quasi-gradient iteration. The advantage of this method is that con- vergence 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-SVy the gradient of function fa) by using the variance reduction technique; however, the derived linear convergence rate is related to n. Motivated by few recent works (Lei & Jordan, 2017; Lei et al., 2017; Allen -llu 2017) that focus on the stochastically controlled gradient, we were inspired to look for way to improve the query complexity and reduce the dependence on to solve the composition optimization in (1.1).
(Lian et al., 2017) estimates the inner function G(z) and
Hence, this paper presents novel and more efficient method named stochastically controlled com- positional gradient (SCCG) for solving composition problems involving a two-finitessum 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 F; 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(z). In- spired by stochastically controlled stochastic gradient (SCSG) (Lei & Jordan, 2017) that estimates the gradient, G(x:) can also be estimated by using a snapshot ã., in which G(ã.) is not computed directly, but is estimated through a random subset from [n]. This is the first time that 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 stochastically controlled compositional gradient estimate the ff(z). How- ever, 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 un- biased estimation; and, second, the gradient of fī.) at the snapshot is formed by two random subsets, which are used for the functions F; and Gj respectively. Moreover, the biased gradient bring more difficulty in proving the convergence, which are greatly differ- ent from those encountered in (Lei & Jordan, 2017: Lian al., 2017; Lei et al., 2017). To address these scenarios, we have identified 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 general problem. the composition algorithm is also to find a point x satisfying f() - [[(")= < e for a convex function, where x" is the optimal point in the strongly convex function, and || [2) < e for non-convex function, respectively. The elegance
2

---

Under review as a conference paper at ICLR 2020
Algorithm
Strongly Convex
Non-convex
SCGD (Wang et al., 2017)
((1/65/2)
O(1/e4)
Ace-SCGD (Wang et al., 2017)
((1/E274)
O(1/e722
ASC-PG (Liu et al., 2016)
O(1/c%/4)
0(1/2/4)
SC-SVRG (Liu et al., 2017b)
T2 + L3//4² 1
log (1/e)
O(n4/3/e)
mini-batch VRSC-PG (Huo et al., 2018)
m + 1.7/1²
log (1/c)
O(n2/3/c)
mini-batch C-SAGA (Yuan al., 2019)
n + 13/10²
log (1/c)
O(n2/3/c)
SCCG
min
n4
cx
+
4i
x
min
na
log (1/e)
(min( (5)5))
-2-)) })
mini-batch SCCG i. {n, ))
min
m2
12
min
nh p
log (1/e)
(min 2573:
n2/a
Table I: Comparison of the query complexity with different algorithms. Note: μ and Ly 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 given sampling oracle that are needed to compute the gradient. Here, 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 ((min(n, 1/(ex²)) + 1///mmmin(n) 1/p²") ( log(1/e)). 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 ( n n/4//////// result in (Liu et al., 2016) and comparable to the result in (Liu et al., 2017b).
///s/e)), which is better than the
Mini-batch For the mini- version, the query complexity can be improved to some extent, that is O( 1/(cx²)3 + (2//(bp)mmmn (n, 1/1²)) log(1/c)). and (
for strongly convex and non-convex functions, respectively, which are better than mini-batch vari- ance reduced stochastic compositional proximal gradient method (VRSC-PG) (Huo et al., 2018) and mini-batch Composite SAGA (C-SAGA) (Yuan al., 2019) when b=1/ju and min {n. 1/c)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 pop- ular technique 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 co- ordinate ascent (SDCA) (Shalev-Shwartz & Zhang, 2014; 2013) and the accelerated Nesterov's '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 gra- dient. However, knowing that the estimated gradient usually has large variance, the gradient of the function is estimated from a snapshot to appropriately reduce the variance in other words, the procedure includes variance reduction mechanism.
Composition optimization problems can also be solved with the above algorithms, but the two- finite-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 query complexity of ( 7/2) for general function and O(E 5/4) for strongly convex function. Liu et al. (2016) employed Nes-
h denotes the size of the mini-batch, can be obtained through the n 1 from Theorem I and Theorem 2.
3

---

Under review as a conference paper at ICLR 2020
terov's method to accelerate the composition problem, reaching (/- and 0(e-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, result- ing in a sample complexity of (11/e2) 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 estimate the inner function G(x)) and the gradi- ent of the function f()). which yields a linear convergence rate, Subsequently, Liu et al. (2017a) and Devraj & Chen (2019) applied dtual-based method to composition problem, which also yields lin- ear convergence rate. Devraj & Chen (2019) also applied the stochastic variance reduced primal-dual algorithms to composition problem. Yu & Huang (2017) turned to an ADMM- Maad-a 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 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 random subset rather than through direct computation. Lei & Jordan (2017), for example, proposed an SCSG method for 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 Natashal.5 algorithm, 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 E [n] to denote that i generated from [n] 21. n). We denote by (z) " VF(G(=)) the full gradient of the function f. (G) the Jacobian of G, and (VF) function f. where and j are randomly and independently selected from [n).. We use = [A] to denote the number of elements in the set A, and define Ga(x) = 1 Cisisa (z)) We use to denote the expectation, that is [v = 4 E MA[j]- Note that all the variables such as subsets A and B, elements 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,, E, EA and Eg except when explicitly stated otherwise. Recall definitions on Lipschitz function, smooth function and strongly convex.
as the stochastic gradient of the
Definition 1. For functiio p on X, Yx,y y E X, A function P is By-Lipschitz. that is [Ip(=) p(v)1 < Bpllæ ull: A function p is a smoshh,, that is ||Vp(z) Vp(y)] < Ip vll: A function p p--trrongly convex, that is p (y) 2 (p --)+)))))))-))))//00 +//2lzz vll
Through our discussions, we make the following assumptions, Assumption 1. Let Be, LE and Ly be positive scalars,"
Gj is Ba-Lipschitz, j E [n], that is [[Gz(z) Gr(ni) S BaIlæ 1/].
F2 is Ly-smooth, i [n), that is (v) ( & -r -
II 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 F, is upper bounded. Moreover, in the experimental section, we will show that the Jacohian of G(x) is bounded.
4

---

Under review as a conference paper at ICLR 2020
For function (z()())). there exists constant L, satisfying [([G)())) (BC,())) & ب yll, Vi,j E [n]]
We assume that i and j are independently and randomly selected [n], 2 E RM IRN, then [x)) ( = VF))).
Furthermore, we define H1 and H2 are the upper bounds on the variance of G(x) and (0G(=)) respectively, that is,
-
H1. n² ΣΣ -
(OG,
H2.
In the paper, we denote by z the k-th inner iteration at s-th epoch. But in each epoch analysis, we drop the superscript and denote by 2μ for zi. We let x be the optimal solution of the convex f(x). Throughout the convergence analysis, we use (-)) notation to avoid many constants, such as Ba, Lr, and L,, that are irrelevant with the convergence rate.
STOCHASTICALIX 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, 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 ã., and then compute the full gradient V fīz)). In the inner iteration of the current epoch, SVRG defines the estimated gradient by randomly selecting is from [n] the k-th iteration.
recall the original SVRG (Johnson & Zhang, 2013). The general process
(DG(xx)) VF, (G(xx)) - (aG(z.)) VF,, (G(E.)) + Vf())..
(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 = GA(zz) G(ū.,,
(3.2)
where AA is the mini- batch formed by randomly sampling from [n]. Whereas, as the number of the inner function Gj and the outer function F, increase, it is not reasonable compute the full gradient of (x) and the full function ((x) directly for each epoch.
Extending from the SCSG (Lei et al., 2017; Lei & Jordan, 2017) and Natashal.5 ..5 (Allen-Zhu, 2017), we present a new algorithm SCCG for the composition problem as shown in Algorithm 1. We introduce two subsets D, and D2, which
independent with each other and randomly selected from [n]. respectively. We define D = DDUD2 as new variable, which is important in analyzing the convergence. Firstly, D, 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
GR (x(x) Ga(ā.) + GD, (T.),
(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 Dj rather than [n). Throughout the paper, we assume that [A| [D |. 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). We define this estimated full gradient of f(ā.) for each epoch as fD(ā.) (aGp, (t.)) TV FD, (G', (i.)). Though (Vf. # V f(.), ), we could still estimate the gradient of the f(xx) by
V = (8G,, (I+)) TV. (G&) (5.)) (GD, (5.)) + fā
(3.4)
The parameters' setting can he referred to Theorem and Theorem 2 for the strongly convex and non- function, respectively.
5

---

Under review as a conference paper at ICLR 2020
Algorithm Stochastically Controlled Compositional Gradient (SCCG) for the strongly convex or non-convex composition problem
Require: K, S. 77 To and D = D1 UD2 where D and D2 are mini-batches. do
for 0. 2, ....
Sample from [n] for D times to form mini-batch D1 Sample from [n] for times to form mini-batch D2
VfD(ū.) = (dGD, (8.)) (F,,) (Gv, (ix))
Fo = 3,
for k = 1, ... K --1 - do
Sample from [n] form mini-batch A (ā Ga(x))
GD, (..)
Uniformly and randomly pick in and ja from [n]
Compute the estimated gradient V from (3.4)
Tk++1 2k V
end for
Update Ø341 KK, 8241 Fy, is randomly selected from [K- - -1]
end for
Output: dg. is uniformly and randomly chosen from E ( 13 and (0, K 1}.
where is and ju are randomly selected from [n] at the k-th iteration for functions F and respec- tively. Furthermore, J..AA. f&l * ff(x))))) 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 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 I, for the u-strongly convex problem, suppose Assumption holds, let the step size is 1 S /u/ () the subset size of A is = min(n, 128B 12p//1²)) the subset size of Dj and D2 are both D min {n, 5 (16Bg + 4H2) /4(e))") the number of the inner iter- ation is K 2 540L2 n², the number of outer iteration is $ 2 1/ //olog( //og(1/p)) (ogg))))((((()))))
x=" 1/11//c) Then, the query complexity is (D + KA) = 30(==00-i) ((min n, cpa + 1 min { n. 1 log (L/e)).
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 B&, Li. H1 and H2, and analyze the size with the order of 1/2²2 We consider three internals of n while the min value of the function in the above query complexity will take different results:
obtain the query complex- ity is (((11((()) 137/"²) f²) log(1/ log() 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-SVRRG (Lian al., 2017: Liu et al., 2017a).
1/12 < 11(((22 n. When is large enough such that
1/12 n 1/(ep2). When is smaller than 1/(su²), the query complexity becomes O((n + 127/1²) (og())))), which is the same as Compositional-SVie
(Lian et al., 2017).
However, we need to compute the full gradient of V (ā.) as in (3.1). The estimation of inner function G(x)) is the same as in (Lian al., 2017).
n < 1/1² < 1/(ep²). When is the smallest one, the query complexity becomes O((n + 12mn/²²) log (1))).. The result has a similar form to SVRG (Johnson & Zhang, 2013). This also gives us an intuition that the inner function should computed directly rather than estimated if is small.

---

Under review as a conference paper at ICLR 2020
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 perfor- mance of the non 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))))
Theorem 2. In Algorithm 1, for non-convex function, suppose Assumption holds, let the step size is = min(1/n²/ ,,2/5,, the size of the subset D1 and D2 are D = min {n, (1/Ee), the size of subset A is A = min {n, O (1/n)}, the number of inner iteration is K S O (1/11/12), the total number of iteration is T = O (1/ (er)), in order to obtain V (21) S c, the query complexity is O (min (1/e// haalssn////////// /c])
From the above result, we analyze the query complexity of the non-convex problem separately: 1) when n 2 1/c, our query complexity becomes (1//2/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/e, the query complexity becomes OnA///c) /c), which is consistent with the result of (Liu et al., 201 7b) 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 that of Theorem and Theorem 2, and the difference with Algorithm is the computation of the gradient of (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 for the j--ttrongly convex problem, suppose A Assumption I holds, let the step size S bp// (1351,3)) the number of the inner ileration is 2 54012, (bp²²), in order to obtain
Bl x= 11 I c, the query complexity O ((min n,, sqc2
123 by²
min {n, nي=
}} log (1/0)
Corollary 2. In Algorithm 2, for the non-convex problem, suppose Assumption holds, let the step size 1) = 1//5 min (1/n2/5 2//5,,
}, the number of the inner iteration is K S O (b>/2 (r//2), in order obtain B[I[ (+) S e, the query complexity is (1/61/510 (min (1/e2/5 n//5 /e)).
From the above-given query complexity results for the strongly convex and non-convex problems, we can see that both of their step size 7 and the number of inner iteration K are larger than the corresponding ones in the non-mini-batcl 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" To verify the effectiveness of the algorithm, we use the mean-variance optimization portfolio management":
min - E. + EEE - Σ (r
where r; E RRN, E [m] is the reward vector, and x R. the invested quantity. In the experi- mental setting, we set n=3000, |A| n2233 |D,| = 2400, 2600, 2800, which are denoted as SCCG (2400), SCCG (2600) and SCCG (2800). The reward vectors are generated on Gaussian distribution
*Our aim is to compare our general variance-reduce hased method with the stochastic composition gradient method, and also to verify the proposed algorithm, thus we do not include SVRG-based method. This formulation just used to verify our proposed algorithm. In appendix, we show the hounded Jacobian.
7

---

Under review as a conference paper at ICLR 2020
ASS-TS
ASCING SCOCE 200
AOCING GOOD DE
SOOOD 200
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 Reov =10, 30 and 50, respectively.
AG
AG0 Pg
SCOUSTRRT
Figure 2: Non-convex: Comparison of the norm of the gradient between SCGD, ASC-PG and SCCG; Dataset (from left to right): mnist, olivettifaces and coil20.
with the condition number of its covariance matrix denoted by Keov. Furthermore, consider three conditions numbers, =co 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 24 and xy as 1/(1 + ||=; - =1,1² i,j [m]. 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, 1000x 784, 400 x 4096 and 1440x 16384. Our experiment is to verify our proposed algorithm, thus we set D, D2 default and choose three different sizes of sample set D,, which are smaller than n. For example, for the case of mnist, we choose 'D,l 400, 600, 800, which are denoted as SCCG (400), SCCG (600) and SCCG (800). Furthermore, samples. Figure 2 shows the norm of the gradient, and Figure (in appendix) shows the objection value. We compare 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 reinforcement learning are given in appendix.
also set |A| 2/233, where is the total number of
algorithm with the stochastic gradient based method (SCGD and ASC-PG),
5 CONCLUSION
In this paper, we propose the variance reduction based method for the strongly convex and non- convex composition problems. We apply the stochastically controlled stochastic gradient to estimate inner function G(r) 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, 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 real-world problem.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Zeyuan Allen-Zhu. Natasha 2: Faster Non-Convex Optimization
Than SGD. ArXiv,
abs/1708. 070044 2017.
Zeyuan Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. In Sym- posium on Theory of Computing, 2017.
Stephen Boyd. Alternating direction method of multipliers. In Talk at NIPS Workshop on Optimiza- fion and Machine Learning, 2011.
Adithya M Devraj and Jianshu Chen. Stochastic variance reduced primal dual algorithms for empir- ical composition optimization. arXiv preprint arXiv: 0etp//9977.90,,, 2019.
Onur Dikmen, Zhirong Yang, and Erkki Oja. Learning the information divergence. JEEE transac- fions on patlern analysis and machine intelligence, 37(7):1442-145: 2015.
Saeed Ghadimi and Guanghui Lan. Accelerated gradient methods for nonconvex nonlinear and stochastic programming. Mathematical Programming, 156(1-2):59-99, 2016.
Saeed Ghadimi, Andrzej Ruszczyáski, and Mengdi Wang. A single time-scale stochastic approxi- mation method for nested stochastic optimization. arXiv preprint arXiv: 18/2.01944 2018.
Geoffrey E Hinton and Sam T Roweis. Stochastic neighbor embedding. In Neural Information Processing Systems, pp. 857-864, 2003.
Zhouyuan Huo, Bin Gu, Ji Liu, and Heng Huang. Accelerated method for stochastic composition optimization with nonsmooth regularization. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Neural Information Processing Systems, pp. 315-323, 2013.
Lihua Lei and Michael Jordan. Less than a single pass: Stochastically controlled stochastic gradient. In Artificial Intelligence and Statistics, pp. 148-156, 2017.
Lihua Lei, Cheng Ju, Jianbo Chen, and Michael Jordan. Non-convex finite-sum optimization via sesg methods. In Neural Information Processing Systems, pp. 2348-2358, 2017.
Xiangru Lian, Mengdi Wang, and Ji Liu. Finite-sum composition optimization via variance reduced gradient descent. In Artificial Intelligence and Statistics, 2017.
Qihang Lin, Zhaosong Lu, and Lin Xiao. An accelerated proximal coordinate gradient method. In Neural Information Processing Systems, pp. 3059-3067, 2014.
Qihang Lin, Zhaosong Lu, and Lin Xiao. An accelerated randomized proximal coordinate gra- dient method and its application to regularized empirical risk mininization. SIAM Journal on 2015.
Optimization, pp.
Tianyi Lin, Chenyou Fan, Mengdi Wang, and Michael I Jordan.
Improved oracle complexity for stochastic compositional variance reduced gradient. arXiv preprint (006:0v8000004550 2018.
Liu, Mengdi Wang, and Ethan Fang. Accelerating stochastic composition optimization. In Neural Information Processing Systems, pp. 1714-1722, 2016.
Liu Liu, Ji Liu, and Dacheng Tao. Duality-free methods for stochastic composition optimization. arXiv preprint arXiv: 170..09554 2017a.
Liu Liu, Ji Liu, and Dacheng Tao. Variance reduced methods for non-convex composition optimiza- tion. arXiv preprini 1711:47 2017b.
Liu Liu, Minhao Cheng, Cho-Jui Hsieh, and Dacheng Tao. Stochastic zeroth-order optimization via 2018.
variance reduction method. arXiv preprint
Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2013.

---

Under review as a conference paper at ICLR 2020
Sashank Reddi, Ahmed Hefny, Suvrit Sra, Barnabas Poczos, and Alex Smola. Stochastic variance reduction for nonconvex optimization. International Conference on Machine Learning, pp- 314-323, 2016.
Shai Shalev-Shwartz and Tong Zhang. Stochastic dual coordinate ascent methods for regularized loss minimization. Journal of Machine Learning Research, 14(Feb):567-599, 2013.
Shai Shalev-Shward and Tong Zhang. Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization. In International Conference on Machine Learning, pp. 64-72, 2014.
Richard S Sutton, Andrew G Barto, et al. Reinforcement learning: An introduction. MIT press, 1998.
Mengdi Wang, Ethan X Fang, and Han Liu. Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-value functions. Mathematical Progranming, 161(1-2): 419-449, 2017.
Lin Xiao and Tong Zhang. A proximal stochastic gradient method with progressive variance reduc- tion. SIAM Journal on Optimization, 24(4)22057-2075, 2014.
Yue Yu and Longbo Huang. Fast stochastic variance reduced admm for stochastic composition optimization. In International Joint Conferences Artificial Intelligence, 2017.
Huizhuo Yuan, Xiangru Lian, Chris Junchi Li, and Liu Ji. Efficient non-convex stochastic compo- sitional optimization algorithm via stochastic recursive gradient descent. In Neural Information Processing Systems, 2019.
Junyu Zhang and Lin Xiao. composite randomized incremental gradient method. In International Conference on Machine Learning, pp. 7454-7462, 2019.
10

---

Under review as a conference paper at ICLR 2020
A TECHNICAL TOOL
For the subset A [n]. we present the following lemma that the variance of random variable decreases by a factor AA if we choose |A| independent elements from [n] and average them. The proof process trivial However, it is important tool for analyzing the query complexity under the different sizes of the subsets.
.... Lemma 1. If "
E I satisfy Di= = and A is a non-empry, uniform random subset of (n) and A [A), that is elements are uniformly selected from [n] without replacement, then
EAll a EsEA "oll
KA<m)
A
from Furthermore, if elements in A are independently selected from [n] with replacement, then
EA 1 EAEAADA
11
1 An Σ |0:11
Proof. Based on the Σi= vs = 6, and permutation and combination, For the case that A is non-empty, uniformly random subset of [nz], we have
EA Σ
2
=FA
[|wb|1]]
+
1
Dis
CA-1
DEA
DEA
C iE(m)
n n-1
$$1
A
||//11
+
A A(A 1)
Σ iE(nl
(v Enis>>
U/
72
i=1
n (n 1)
A
||w
+
A(A 1)
Σ KE((x) (1is (14)
ii
n (n 1)
A (n
A)
||0/|1
1)
<AT(A<M) Σ
where C%Al refer to the number of the combination of things taken A time without repetition. Thus, we have
E
Σ
A2 EA
Σ
2 I|
T(A < n) 1
Σ 10
DEA
DEa
A
For the case that the element in A is randomly and independently selected from [n], we have
E
EA
Σ
11bb11
+ +2EA
[ IsOCA (b6, EbcreA 8k
BEA
PEA
||:/11 2 + +2EA Σ Isticd
[F(u], 1011,E Ebekea (x
=
=A
||:b11
+ (A - 1) |E [w]]]
(A.1)
||0z|12.
71
Based on Lemma 1, we can obtain the inequality with two-variables D, and D2, which are used for the gradient of (xx)
11

---

Under review as a conference paper at ICLR 2020
Lemma 2. If w1, ...,...., Wn E R MxX and U1....y Un E RM satisfy ( Eiein wa) ( E SEEn)
w T.. and D = [Dı, D2] is a non-empry, uniform random subset consist of D2 and D2, which are
independently and uniformly selected from [ni), D |Di [D2], then
ED
1
EureD, W'd )'
( d2ED2 vida)
100
D1
D22
=B,
Ep
1
[diidalED ((W6)) JTdd w 8)
D
1
DD²
n²
a
[[ww)) Gi - w
-
D
n2
fJ=1
B BOUND ANALYSIS OF SCCG FOR THE COMPOSITION PROBLEM
B.I BOUNDS ANALYSIS OF THE ESTIMATED FUNCTION AND THE GRADIENT
Here, we mainly give different kinds of bounds for the proposed algorithm, such as EA,D, ||G
( These bounds will be G( Ep| in IV fal (=xx)) and A. V
used to analyze the convergence rate and query complexity. These bounds are all based on Assump- tion 1. Parameters such as Ba, Br, LG. LF and L5 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., 20: 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 prob- lems based on the Lemma I and Lemma 2. For simplicity, we drop the superscript in. jks, A and D for the expectation with E in the proof.
Lemma 3. Suppose Assumption holds, for GR defined in (3.3) with D [D1] and A |AI, we have
I(A n) B&TEIE
+6 2+6 T(D n)
EAD, G(xx)) <4
H1.
A
Proof. By the definition of G2 in (3.3), we have
B G(xx)]1 =E|GG - Gp. (1R) + GD. (1x) G(*))l?
①
S2B| - GD, (xx) )| + (xx) G(+))]l
21 11 (A < n) B - I| [(D n) H1.
A
D
where ① follows from ||a + 0z|l² < 2a + 2nl; 2 is based on Lemma 1 and the following inequality: Through adding and subtracting the term G(Ix)) - G(öz), we have
ElJć2 GD, (12
= -
+ - - (
- CA (G(#k) G(i.)) + ((a)) Go, GD,
(G (xx))
(2E|GA(m)) - GA(T.) (G(Ix) - G(z.)) + (0.) GD, (mx) (G(z.) - G(xx))II
3 (A < n)
22
E. (.I..( - G.(xx))l + BBI| (ā.) - G(ā.)I 2 + 2E GG(z)]]²
A
3
[(A < n)
I(D < n)
22 A
B&E I - -2.12 +
H11
D
12

---

Under review as a conference paper at ICLR 2020
where follows from ||a + b112 < + 2b2; @ is based on Lemma 1; @ follows from the bounded
function G and the upper bound variance of G. Note that A and I&k are independent; and D and E3 are independent.
Lemma 4. Suppose Assumption holds, for Gy defined in (3.3) and fx defined in (3.4) with =
D= [D. and D = (Pil = D22,, we have
I(A [[AA<))
Ep EA
V f vf(xx))| LAB
E E| T2ll
A
L(D < n)
1(D2 < n2²))
32B Dp
H1 +
H2.
D
D
Proof. Through adding and subtracting the terms of
(OGo,
we have
Ep E Aiiii
A
- (FC()))) (fb(E) (((k)))((((())) v((l))
4E
(OG(Ix)) - (FGGG))))))
+ 4E
+ 4
4E
(8.)
(8G( (FF
I(D2 n²)
[(A < n) G. G((x))
GD. (+.))l + +4B Go, (i.)1l
H2
D
SABAL
E||Ta - 1.1l 21 32B 1
11 < n.
H1 I1D2 n²)
D2 H2.
A
D
where ① follows from ||a + a2 + 03 a2l12 < 4a 40 + 4a 4a 2 is based the
bounded Jacobian of G and the smoothness of F in Assumption 1, and the upper bound of variance in Lemma ④ based on Lemma 3 and the upper bound of variance of G(x). Note that and Ja are independent; and D and H, are independent.
Lemma 5. Suppose Assumption holds, for GR defined in (3.3) and V defined in (3.4) with D [2] and D= (Dil = (D2), we have
A / f (#+)) <.0B3L33 T(D < n)
T(D2 < n²)
H1 +
H2
D
D2
I
1(A n)
L3
+
Ellar F2
B
A
Proof. Through adding and subtracting the term of (ZG (V(((()) (0Go, TVF,, (G(ā.)) (Note that, D
VV.
and H. are independent), we have
E v f - (xx))
13

---

Under review as a conference paper at ICLR 2020
+ 5E
+ 5E
+ 5E
- (octt))-(
+ 5E
( (G( (FF
35 - 2 5B L3
Gx - G((x))
+ (5BBL3B
GD, (
+5 1(02 < <n²² H₂
+ +5B G(t.) GD. (i.)ll
13 BELF
T(A [(A<n)) <)
T(D < <n)
H1 + T(D2 < n²)
+4
Bl| - -zlll + 40BBLT
H2.
A
D
D
where ! follows from || + 02
+
43
+ 04 + as | 5 + 5a + 5a + 50 + 5a @ is based
on B||| X E. [[]] = F[X2 [[[[]]]]]]
< ]] the smoothness of F., the bounded Jacobian of
((r) and the smoothness of in Assumption 1, and the upper bound of the variance. R 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 T. Thus, we obtaín 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.I 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, n and h. Based on the setting, we can obtain the corresponding query complexity, which is better than or equal to the WVRG-based method in (Lian et al., 2017) and (Liu et al., 20)7a). This is in fact that the event function has an influence on the size of A and D.
C.I.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 ã, are indepen- dent.
Theorem 3. Suppose Assumption 1 holds, Algorithm 1, let > 0, > 0, A |A, D= [D2), K is the number of the inner iteration, x² is the optimal point, have
Ps 5
Bllăs - x-1 < p - 12 10
1-pp p
where p ( + p2)/ P2 and p3 defined (V, V1 are defined in (C.4) and (C.5).)
P1 = 2/ 4V h
(121, + 10V)
(C.1)
14

---

Under review as a conference paper at ICLR 2020
P2 -2 2V 1 553 + m)))
(C.2)
1 4
Ps h n3 Vi n 2n
(C.3)
Proof. By the update of mg in Algorithm 1, we have
E [k+1 ==1
=B I z²1 11? - 2n V fR 2h x²) + E F ||
=Blaa x= 1| - 21 (V ((xx) + -AA. [v
Ty - (I
72 fill' (f(x)), Ik - x²)
x² 1| (V f(xx), 26 - x²) -n [ia
=E
+ R f (.++)) vs(xx) ||
<E ax z11 11 2nd 1²1 + + E EAA. [ vf(Ex) || + hnBBlax x=11
+ 2n7²
[x )1 R V ((((x))
(in hu)) B||o 201 112 + + " FAiS
ViA \)(r))
=R
+ 2n7² (xx)) ff((")) 1| E V <f(ax)||
2
<E|T 2²112 (nn hn) B|| - 2²11 + T (4V - 1=112 + V/2
1
+ 2n² [13B] In - x 2²11² + (L3 + v) || - 1 + vi)
=EI Ir - z²11² - 2/u - 4V 1 ,/ (121 + 1ov) n) 1B3|I1 - 11
+2 2V + 5 (17 + +1) nBlii - 112 + 1n1hs + 22
where
V -BOLT [[(AAn))
(C.4)
A
I(D n)
I(D2 < n²)
Vi 40
H1 +
H2,
(C.5)
D2
1/2 33-22B 12 I[D < n)
I(D² < n²)
4
H1 + 4
H2
Vı,
(C.6)
D
D2
5
① is based on ||aj + 2 < 2a + 2a3 and (a1, 02) < hll [llayll + #1l22 strongly-convex of f in Assumption 1, and Lemma 4, 5.
12, h > 0; 2 is based on
Summing up from k = 0 to A: K - 1, we have
K Fllax - x²1 < Fi x012 P
ElIaa 1² K Kp2F210. - x²11 + K
k=0
where
2p - h - 4V h -(121 + 1003
P1
P2 =2 2V + 5 (T2 + V) v)n)
15

---

p Under review as a conference paper at ICLR 2020
Ps - + 21/² V1. V2.
For 20 = F. by arranging, we have
1
pi p: 8s41
x²1
Bl x²11 1=2'11
P3
E
FK
x²1
K
K
< K
+ p2
Ellis - x²1 P3.
assume that P1 > 0 in (C.1), then obtain
Bliig
x²1
E
1=1
P3
p
P1 ==
P3 1
Sp
$ E 30
x²11
+
(C.7)
P1
1
where p ( + p2)/PP, P2 and Ps defined in (C.2) and (C.3), the last inequality is based on the formula of geometric progression.
Thus, if ø converges to the optimal point x", we need to ensure that < 1 and the second term Pa(1 /²) (1 p)) is less than c/2. Actually, if D n, the second term is equal zero, which will be similar to the convergence results in (Lian et al., 2017) and (Liu et al., 2017a).
Proof of Theorem
Proof. In order to keep the proposed algorithm converge, we consider the parameters' setting, we first ensure that #I > in (C.1), and then define
1 + P2)//11
(C.8)
that require p < 1, where P2 defined in (C.2). Thus, the convergence sequence is
E Es - 201 & p 2 x²
+
P3
pe S E x²1 x²1 +
P3
P1
P1 p
a=0
We ensure A8 1 following analyze the parameters' setting such that satisfying the above requirement.
1-p 2, where As defined in (C.3), that we can derive the size of the D. In the
1. In order to ensure P1 in (C.1), we consider the parameter h, n and A,
(a) μu, consider Pi (C.1), we should require that h S μ. however, V in (C.4) relationship with A and D. In order to keep A small enough, we set the upper bound of h. Thus, we set = μ.
(b) A min 128BA } based on the setting of h, we require that V/h <
P 16
Thus, we have
= V=BOL3 (((AEn)) < 8B4 L2 I(Acn) < 1
For V defined in (C.4), Af < n, we have
A 2 128 1 n² A = satisfy the requirement.
otherwise,
Thus, we have A =
min n1 12881
12 P
(c) 17 5
back the target of P1 > we require that 7 S 6317
3p
3p 5317
121 1
4 24 2 note that μ Ly by the definition in
12
+20
223 213+10
preliminaries.
16

---

Under review as a conference paper at ICLR 2020
2. In order to ensure p in (C.8), we first consider Pi and p2 in (C.1) and (C.2). By the setting of h = μ and V < p2/16, we have,
1 + 10
1
11) 12
3
101
P1 2 1 21-
16
1²
4 1
8
13p 1)
(C.9)
1
1
( L
1
85
54-1 1² + 10
16
Lg +
16
n
S
4
+ 10
n)
n =
7
+ 8
n
(C.10)
We require that p Kpi + 22
< 1, and analyze the two terms separately,
P
(a) In order to 2 1, that is
2
tuu+ E (1311) 1
P2 <
1137) n < 2
P1
gg 8
101
We get 1) S 13517
(b) In order to Kp _
< 1 that is
1
Kp <
S
pK 2K
(2u+ 10
(Iz + to.12) )a(e)n))
1) n
1
S
2K
(zu+
2s L3n)
n
2K (2um)
Thus, have K 2 540 17
3. Consider the term ,² F1 - x: x=11 + Pa I-p' we analyze them separately,
I
(a) In order to ensure
1 S e,, that is
PI
I-p
P3
1
P3
P3
P3
2p3
Kpi
1
+
P1
P
K P2
S
PI
K
2P1
2P1
K
T
P1
2 e.
Based on the bound of #ı in (C.9), the definition of V1 in (C.5) and the step size mentioned above, we have
i. For V
11//22 + 2 p
LV2 + 2
4LV + 2
+ 21 V1
3
S E,
P1
1/
3
101
8
1311
7/1
101
18t 1331
1/
101
1,311
thus, we have
V1 < 5
4
5
1
8
135
2
135
Ejt
2
<
1
33
5y
+
101
8
2
135aa
135
1
S
1/11
5y
4 + 13553
101 1
8 f
13527
#
<
3 101 13,1
4 By
2n
i. If D < n. we can obtain D
>
5. Tegz
(20Bg + 5H2). other-
wise D = 0, the above inequality is correct. Thus, we obtain D
min {n, 1...A...HH + 4H2)) dep
(b) In order to ensure 1² Eliāo - x² 12 S Le, we need the number of the outer iterations
2E Do
x²1 ?
S> log (1/p)
log
17

---

Under review as a conference paper at ICLR 2020
All in all, consider the query complexity based above parameters' setting. For each outer iteration, there will be (D + AA) queries. Thus, the query complexity is
((min((
(m,
min { n. μ2 cp2 f x²
1 } +
Li
1 123)
}} log (1/c)
(D+
C.2 PROOF OF SCCG METHOD FOR NON-CONVEX COMPOSITION PROBLEM
C.2.1 RELATED BOUNDS
Lemma 6. Suppose Assumption hold, Algorithm we can obtain the following new sequence
with respect to fIxx and Th E.112. let h >> 0, > 0, A = |A| and D (Dil ( we have
u [=I\V Jk. + cx+1 B - = - (xx())) B - 2.1l
where
[[(A<n) ())
+4 -1(==))
W BBLL 4
+4
(C.11)
A
D
2 +4hW) n 10 (L} + W) n²
CK =c+1
1+
h
+WW 5(L3 + W)Lfrr²
(C.12)
(6 hea-1 11- (T.p 20x+1) 1p)
us
(C.13)
W1 -2013 L7 1(D <n²)
I1D22 + n²)
111 +
H2.
(C.14)
D
D2
Jk 2 + hcck1 Win + (I.g + 20x+1) Win
(C.15)
Proof. Consider the upper bound of f(*x+1) and || =zll² respectively,
Base the smoothness of f in Assumption I and take expectation with respective to ig. ja.
we have
Big [xx++11)
, <f[f(xx)] - TE(V)((E)) Via) + L 2 F
2
Li 2 v Vi Tnl |
=B[s(xx) - T) Vix V)(xx) + V\(()))))))))))))))
2
=E(f(m)) / vx()))) - V.))
vf(*x)
I,f 2
V Vf(*x) + vf(on))
2
1 (5 |1 + ! 1 BAnn [iaa
<B(((nx))
Li , 2f( + 2E V vf(x)) 11²)
[f((()))
1 n 11 |
BAii [vih]] [)((x))
+ Lgn?
B[|[)(+))1 + E vi Ws(H))
n -,ش [+,|
1 BAn V
vf(xz)
" Vi -vf(m))
V((oo)
where the last inequality is based on
||a
a2ll
<
2n
2a3
18

---

Under review as a conference paper at ICLR 2020
Base on the update of zy in Algorithm and take expectation with respective to ix. Jk. have,
B Ba.]| - #2l1
-BI Tz11 - h: 2k - ..)) + E F
=BIlay - l1ll² Bn V f Vf((())))))))))))))))))(( Vf(()))(())))))))) Ix x.)) 2 f
-B||aa - 11 - 2n -
2n
V
[f(x))) Iz
+ 1 V f (xxa))) + [(xx))
<B1 #11l" + V> mn|l [Ti
+ BBlla =0
+1²
2B f 21 21 V - Vf(ce))]
= 1 + h² -|
1 + (hm 21)) E[ hnn E f
vf(=x)]
+ +2 v - Vf(os)
where the inequality is based on 2(a1, b2) /1/h||a1|| + 2 wh > 0, and |012
2n + 203.
Combine above equalities and Lemma 4, 5, we form Lyapunov function,
[[f(1++))] + ck+ B
2R ==11
=[]f(x
5" L1m²
[[x]]]
+ bリ E Fi
v((ax)
+ L V
[ - Vir-((aws)
2 n1 + ck+1 (1
E [ vf(rw|| || + 2 V((wN)
B1|aa
22112 (hn 2n7²) [++f()))))
hm
2 n1")
((3
1 ck+1h)
[E]f(Ex)] + ck+1
1+
E E| - =212
(L [+)((
+ (Lyn² + 2n (x41) V V)(ca))|'
2" + hnck+1
1
|
|
Vs(Wn))
<B]s(xx)] + Blbx - --1l2 - uN| - VS(xx)]
Jk.
where
- ((} hek+1 17 (L, + 2c, 11 n"²
I(D < <n)
II
< n²
W1 L.,
H1 5
H2i
D
D
4
W₂ Wi:
5
1
JR 2
+ hcx+11
W2n + (Li + 200+1) Win?;
(4I(A<m)
W- = I.
A
( h
Ck -c+11
1+
n 10 (w)++ + +2W + W) 4hW)
Based on the above inequality with respect to the sequence (xf + cg o2 - 2,1l 2 and Algo- rithm obtain the convergence form in which the parameters not clear defined.
19

---

Under review as a conference paper at ICLR 2020
Theorem 4. In Algorithm 1, suppose Assumption I holds, obtain the following sequence with respect to f(xx) and iterations, we have
[xy - 2.11?. K is the number of inner iterations, is the number of inner
f(xo) f(x²) Jo:
E (
KS
where 24 is the output point, Jo and ug are defined in (C.15) and (C.13).
Proof. Based on the update for Ck in (C. we can see that Ck > CR41- As cp is a decreasing sequence, we have uo up and JR < Ju- Then, we get
B V [[)()=]] cx =.11 (I0f + 1441B110441 1=1 + Jo-
Sum from k to
1, we can get
K
[[f(x))] - (BI )1 cx Bx - -x,113) + Jo
uE
K
K
k=0
[[f(xo)] - E[f(KK)]
+ Jo.
K
Since To = G.. Øx41 иK. we obtain,
K no [
[[f(Ee) B[f(2o+1) Jo.
K
Summing the outer iteration from
1, we have
S-1
Mo B [
No
[(1)))
5 s=0
K
[[f(
[fss
Jo f(xo) - ff(x)) Jo.
KS
KS
where zi indicates the s-th outer iteration k--th inner iteration, and it is uniformly and randomly chosen from 8 = {0, .O..... S - 1} and k= K 1}.
C.2.2 CONVERGENCE ANALYSIS
Base on Algorithm the analysis of convergence is based on the smoothness f(x) and the update of æ under the Lyapunov function to form the convergence sequence. Theorem I 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 the whole sample. Moreover, considering the convergence results, size 7 has the relationship with many parameters, such as the subset A, inner iteration K and the total iteration T.
see that the step
Proof of Theorem
Proof. In order to have E [ < e, that is
E /
(x((()))-((e)) + Jo/un S MrSK
consider the corresponding parameters' setting:
20

---

Under review as a conference paper at ICLR 2020
1. For the first term, consider с₁ defined in (C.12) define c ck+1Y + U, for k K, have
11
K
U
U Y
CK
+ Y Y-1 1
Y
where
2 + 4hW 7 10 (B + W)
= =
U 2n n + 5 + W) > 0.
By setting ск + 0, we obtain
UYK
U
U (Y 1)
co
Y-1
Y-1
Y -
Then, putting the Y and U into the above equation. We have
2Wn + (L3) + Lyn
C 2W + 5(13 + W)L C, (C.16)
co (2: + 4hW) 17 10 [33 + W) n/2
(2 4hW) 10 (13+ w)n
where C' = Y 1. Because co has the influence on the parameters such as K, C and uo. we analyze them separately,
(a) For K and C, based on the character of function (1+ - e, as L1, 12 - +o0
and titz 1, and the function is also the increasing function with an upper bound of e, we require
K << ((2. + 4hW) ((++anw)
( 10
(C.17)
thus, we have C' <e- 6e-1. (b) For uh defined in (C.13), in order to keep uy 0, we need to keep colt 1/4. If coh < 1/4, there exits a constant ů such that u4 = üm. In order to satisfy cyh < 1/4, combine with (6.16) and C' < 1, that is
2W + 5 + W)L h) 1) 4'
cul <
(7h + 4hW) 10 [2 [
i. By setting h
1 /
there exist き. > 0, based on above inequality, we have
W < 1613 + 50L3 Tm
< <WLin
9.6 3413n /0. 17mm
Thus, combine with the definition of W in (C.11), we require that
T(A < [{<=))))
I(A < n)
W = B BBBLL
LB
&
A
A
If A n. we require Z o (Li)))
Thus, we have A
min (n, O (1/n)).
ii Based on the setting of h and W, combing with (C.17), we have
K <
10 10m
/ wL33 n + 10 [1} ++((()) n?
1
0
31
10 L3 1 Lin n 10
[3 +
72
'Here the 'e" is the Fuler numher, approximate 2.718.
21

---

Under review as a conference paper at ICLR 2020
2. For the second term about Ju. uo W17,, require
Jo
1
1
hea
W2 + (I.g + 200) Winl
107
1
3
1
Wi
I
2 _
5
1
3
1(D <n)
1
(20 + +H12
Lyn + +
D 2/2
5
Then, if D < n, require that
D z eú (20B 5H2)
(3 + + =
Thus, we min {n, ((L/e)}.
3. Based on the first term
S fe, the total number of iteration is T SK
nSK
Thus, based on the above parameters' setting, we can ensure that B(IV S Based on the parameters' setting. that is D min fn, O(1/O), (n K s O (1/18/2)), and T = (1/ (en)), we have,
T ( KA) K
1
D
)
o
-0
+
A
6T
K
1
min
1//22
1
1
1/2
min
n1
n
4/5
1)
20
9/5
where the optimal 17 min {1/n2/5 2/51
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 y is obtained through b times repeat.
Lemma 7, Suppose Assumption 1 holds, for GR defined in (3.3) and A defined in Algorithm 2 with D = Dz) and D = |Dil (Dz), we have
12
I(A < n)
I(D <n) +4
E. E. - S5BBL1
4
Bliaa 1.11
b
A
D
T(D
< n)
IID < n²)
H1
H2,
D
D
Proof. Through adding and subtracting the term of 1 Σ (0C
(i.j)h
Σ
and (F(((.)) (ž.), VVF, TV.r, (G(2.)),
(i.))E have
EIAA v (xx))l2
22

---

Under review as a conference paper at ICLR 2020
Algorithm 2 Mini-batch version of SCCG
Require: K, S. 7) (learning rate), To and 'D [D1, D2] for 2, ... . do
Sample from [n] for times to form mini-batch D Sample from [n] for D times to form mini-batch D2
ffp( = (0Gp, (5.)) (Gp, (Tx)
To = 2g
for k: = 0, 2,
... 2........ Sample from [n] to form mini-bater A
K 15-1d do
Gx G((xx)) ( GD, (i.)
Ag = for t do
Uniformly and randomly pick i and ju from [n]
Compute the estimated gradient V fx from (3.4)
A++1 = A + f
end for
A Ab/b
Tk+1 Fk A/
end for Update Øs+1 = KK. or Ts+1 = Zy, r is randomly selected from [K - 1]
end for
Output: ii is uniformly and randomly chosen from E {O, S 1} and E {0,.., K-.KKi - 1}.
<5E
Σ (f) (())))((()())))))))))))))))) (00t))))-CCC))))TFFCCEEE
b
(i,))EZ,
+ 5E
(1.))
+ 51E
Σ - (8x))
(1.))
+ 5E
ff((.) (0G (2.) (3.)) (VF.
+ 51E
(0GD. (i.)) V V.D. (OCC
25 1.3 bo 1.1 5 G. - G(*x)
+ - GD, (i.))?
+ ( GD, (ā.)]l² 2 + I(D2 <n²) H2
D
L3 LB
I(A [(A<n)
I(D < n)
I(D² < nz)
+4
E1 3.11 40
H1 +5
H2. D2
A
D
where ① follows from [a + t
as
5a + 5a3 + 5a3 + 5a + 5a and 2 is < E[ and Lemma 1, the smoothness of F,,
based on |||| X - E 2] E[X2 -[X2-1E[X|[]] the bounded Jacobian of G(x) and the smoothness of F in Assumption 1, and the upper bound of variance in Lemma 2. ① is based on Lemma 3.
|E[
Proof of Corollary 2
23

---

Under review as a conference paper at ICLR 2020
Proof. Based on the parameters' setting, that is D = min (n. O(1/e), A min {n. O (b/n)),
K O (b /m3/)) and T = (1/ (en)), we have.
0 T K (D + KA)) =0
1/
1
61/26
)
11 n1/2
63/2
cbl/2n
min
T1
1//2
=
cbl/2
min nt +
175/2
63/2
0
min
1 +
eb
n?
1/5
6 0/5 }).
O
min
b1/5
where the optimal = 83/5 min f1/12/5,,200
E EXPERIMENT
E. RISK-AVERSE LEARNING
To verify the effectiveness of the algorithm, the vaan-nari optimization in portfolio management':
min RER
Σ (re, x)
1 n Σ (rr,, x)
Σ (ra x))
where 9i RN, E [n] the reward vector. and x EN is the invested quantity. The objec- tive function can be transformed as the composition of two finite-sum functions in (1.1) with the following forms:
Gý(x) [Ix, (r,,, ()), y - Σ Gy(x) = [vn [oi.ve]
(y( (11,01) + ((r., vn) y2) ,J. [m].
where 31 RM and y/2 R.
Note that the function G5(z) [x, (r,, and the corresponding Jacobian is [[,e]T, where / E R is unit matrix, and E R is all-ones vector. straightforward to prove that the norm of the Jacobian is bounded, i.e. G²(x) is Be.Liisschizz 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 al., 2017: Lin al., 2018). The source code package will be released as soon as possible to ensure the reproducibility.
E.2 NON-LINEAR EMBEDDING
For the non-convex function, we apply the proposed SCCG method to the nonlinear embed- ding problem in (1.2). We consider the distance of low-dimension space between 2; and æj as 1/(1 || - 2, 13, i.j E (n]. Then, the problem can be formulated the problem in (1.1). In particular,
Ev = - 1=1 Pi (
G3 (0)) ()))))
72
where
1 R G,(+);
Gz(z) 1 + || xzyl
1,
n
1 + || xz
Fy(y)
Pays (1ly: Me 1 + log(un i.j [m].
TThis formulation is just used verify our proposed algorithm.
24

---

Under review as a conference paper at ICLR 2020
2000 P1
1000 P11
0.00
100
Figure 3: Non-convex: Comparison of the objective function between SCGD, ASC-PG and SCCG; Dataset (from left to right); mnist, olivettifaces and coil20.
Note that, consider the function g (x) 1422 of z, we can see that
its gradient Vg (x) (1+=2)² For different value
x (1 x 1 (1+2²)² 21>;.
Thus, we obtain VV (z)) < 2, which is upper bounded. Based on this results, we can obtain that the norm Jacobian is also bounded. Moreover, 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 di- mensions, 1000x 784, 400 4096 and 1440 16384. Our experiment is to verify our proposed algorithm, thus, we set D) "D2 in default and choose three different sizes of sample set DD. which are smaller than n. For example, for the case of mnist, we choose [Dil 400, 600, 800, which are denoted as SCCG (400), SCCG (600) and SCCG (800). Furthermore, we also set |AAls> 2//3, where n. is the total number of samples. Figure 2(in the main paper) shows the norm of the gradient, and Figure 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 reinforcement learning. Let the policy of interest be m total states be S, and the value function of state be V at state 81.
va (s1) E3 {Rai. + VV* (s2) [82] 81, E [S],
where R2,,, is the reward of moving from state $1 to 82, and the expectation taking over state $2 conditioned on state 81. We assume (s) 2 "t for some w" E Rd, where & is the linear map of the feature used to approximate the value of the state. Then, the problem can be formulated the Bellman residual minimization problem, that is
2
min
(Di,w)
Σ P (Rig + (Q),ww)
where y is discount factor, rij is the random reward of transition from to state j. Our proposed algorithm can be applied to the above problem, which can be formulated as the composition problem by taking
9 (w) =S [ w) ..... (12, w), PT, (R1.5 + (B w)) .... P5, (Rs.) + 7 (2), w))]
(w) Σ Di (w) = =
1/1
8/2
j=1
fs (v) =Slly1, v2.1
25

---

Under review as a conference paper at ICLR 2020
A50-10
ASG
Figure 4: Reinforcement Learning application: Comparison the objectively values between SCGD, ASC-PG and SCCG (including three different values of [Di|= 0.95 n, 0.9 0.8n); Dataset (from left to right): n=500, and 1500.
Homberd
115
Figure 5: Reinforcement Learning application: Comparison of the norm of gradient between SCGD, ASC-PG and SCCG (including three different values of [D1]= | 0.95 n, 0.9 n, 0.8n); Dataset (from left to right): n=500, 1000, and 1500.
In the experiments, parameters pz & and R randomly selected. We implement on three data with the size of 500, 1000, 1500. And we set |Di| 0.95 n. 0.9 n. 0.8n, respectively for different value of n. We set b = |A|z 2/33 based on our theory analysis. Figure 4 and show the experimental results, which demonstrate that our proposed method is better than the non- variance reduction based methods SCGD and ASC-PG on both the objective value and the norm of the gradient.
26


Reviews:
[{"review_id": "SygFY6kpKS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In the paper, the authors consider composition problems and use the stochastically controlled stochastic gradient method (SCSG) to approximate the gradient G(x) and \\nabla f(x). The authors also provide convergence analysis of the proposed method for strongly convex problems and non-convex problems. Authors then conduct experiments on the\nmean-variance optimization in portfolio management task and the nonlinear embedding problem, results show that the proposed method is faster. \n\nThe following are my concerns:\n1) There are several important related works missing in the paper, e.g., [1][2].  \n2) The convergence results of the proposed method in the paper are not state-of-the-art. For a strongly convex case, the result in the paper is O( n+ k^2 min(n, 1/u^2) log1/e), it is not necessarily better than O(n+k^3 log 1/e) in [1] or O(n+kn^{2/3} log 1/e). For a non-convex case, the result in the paper is O(\\min{1/e^{9/5}, n^{4/5} / e}), it  is not necessarily better than O(n^{2/3}/e) in [1] or [2]. \n3) More compared results should be conducted in the experiments, e.g. [1][2]. \n\n[1]Huo, Zhouyuan, et al. \"Accelerated method for stochastic composition optimization with nonsmooth regularization.\" Thirty-Second AAAI Conference on Artificial Intelligence. 2018.\n[2] Zhang, Junyu, and Lin Xiao. \"A Composite Randomized Incremental Gradient Method.\" International Conference on Machine Learning. 2019.\n\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "S1gA4PuTYB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nClarity:\nThe paper is clear and well written.\n\nQuality:\nThe work is of good quality and is technically sound.\n\nSignificance:\nThe 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)].\n\n[A.Devraj & J.Chen (2019)] Stochastic Variance Reduced Primal Dual Algorithms for Empirical Composition Optimization. NeurIPS, 2019.\n\nA 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.\nIf the authors can show an empirical advantage over their method, it will make the paper stronger.\n\n-----\nUpdate:\nI 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.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HklwLDlucr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a variance reduction based algorithm to solve compositional problems. The idea comes from the stochastically controlled stochastic gradient (SCSG) methods. The paper applies the idea from SCSG to estimating the inner function G(x) and the gradient \\nabla f_k to solve compositional problems. The paper provides a theoretical analysis of the query complexity of the algorithm in both convex and non-convex setting. The experiments show the performance of the proposed algorithm is better than other recent methods. The paper seems to be the first attempt to extending stochastically controlled functions to the compositional problems. However, I vote for rejecting this submission for the following concerns. (1) Since SCSG is a member of the SVRG family of algorithms, the difference between this paper and [Xiangru Lian, Mengdi Wang, and Ji Liu, 2017] is not significant enough, especially in the algorithm design and the proof of the theoretical theorem. (2) The formulation of the compositional problems comes from reinforcement learning, risk-averse learning, nonlinear embedding, etc. However, the experiments are only performed on nonlinear-embedding problems. I think performing the experiments on different kinds of problems will be helpful to justify the significance.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}]

Author rebuttal:

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