Fast Training  Method for  Stochastic Compositional Optimization Problems
Authors: Hongchang Gao
Heng Huang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Decentralized optimization
stochastic compositional optimization problem
model-agnostic meta-learning

Abstract: The stochastic compositional optimization problem covers a wide range of machine learning models, such as sparse additive models and model-agnostic meta-learning.  Thus, it is necessary to develop efficient methods for its optimization. Existing methods for the stochastic compositional optimization problem only focus on the single machine scenario, which is far from satisfactory when data are distributed on different devices. To address this problem, we propose novel decentralized stochastic compositional gradient descent methods to efficiently train the large-scale stochastic compositional optimization problem. To the best of our knowledge, our work is the first one facilitating decentralized training for this kind of problem. Furthermore, we provide the convergence analysis for our methods, which shows that the convergence rate of our methods can achieve linear speedup with respect to the number of devices. At last, we apply our decentralized training methods to the model-agnostic meta-learning problem, and the experimental results confirm the superior performance of our methods. 

Fast Training Methods for Stochastic Compositional Optimization Problems
Hongchang Gao', Heng Huang"
Department Computer and Information Sciences, Temple University, PA, USA
Department of Electrical and Computer Engineering. University Pittsburgh, PA, USA hongchang.gann gaw.nngpl..ttmm....oom edu, heng. www.ghuitt..
Abstract
The stochastic compositional optimization problem covers a wide range of machine learning models, such sparse additive models and model-agnostic meta-learning Thus, it is necessary to develop efficient methods for its optimization. Existing methods for the stochastic compositional optimization problem only focus the single machine scenario, which is far from satisfactory when data are distributed different devices. To address this problem, propose novel decentralized stochastic compositional gradient descent methods to efficiently train the large- scale stochastic compositional optimization problem. To the best of our knowledge, our work the first one facilitating decentralized training for this kind of problem. Furthermore, we provide the convergence analysis for our methods, which shows that the convergence rate of our methods can achieve linear speedup with respect the number of devices. At last, we apply our decentralized training methods the model-agnostic meta-learning problem, and the experimental results confirm the superior performance of our methods.
Introduction
The stochastic compositional optimization problem 20 plays important role in the machine learning field, since it covers numerous applications, such as policy evaluation [19), sparse additive models (2), and model-agnostic meta-learning [6. Specifically, the stochastic compositional
optimization problem is defined as follows:
min E. [ (E)l
#ERd
where the outer-level function f(v) = [ ( Rdd + IR. is smooth and nonconvex function, the inner-level function g(x) [g Rd Rd is smooth function. It is obvious that the loss function consists of two stochastic functions f and g, making it different from the non-
compositional problem.
The compositional structure in Eq. leads to more challenges in optimization compared with the non-compositional problem. since the stochastic gradient of the loss function in Eq. (I) is not
unbiased estimation of the full gradient. Thus, efficient training of the stochastic compositional optimization problem has attracted increasing attention in recent years. For example, (20 proposed the stochastic compositional gradient descent (SCGD) method to deal with the two-level stochasticity convergence rate than the standard stochastic gradient descent method.
in Eq. TTp. But it has
To improve it, series of variance-reduced methods have been proposed. For example, [25] developed the composite randomized incremental gradient method based the SAGA 4 technique. [27 further improved the convergence rate based on the SPIDER [ method.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Although aforementioned methods have achieved much progress in optimizing Eq. Q. all of them only focus on the single-machine scenario. In fact, data are usually distributed on different devices in many real-world applications. It is necessary to study the distributed training method for the stochastic compositional optimization problem. In the past few years, numerous distributed training methods have been proposed, such as asynchronous stochastic gradient descent (SGD) [16], decentralized SGID [3], local SGD [14]. But they are not applicable to the stochastic compositional problem. Especially, their convergence results do not hold for Eq. ① because those distributed training methods require the stochastic gradient is an unbiased estimation of the full gradient. As far as we know, there are no existing works studying distributed training methods for Eq. ① with theoretical guarantees.
To fill the aforementioned gap, we developed two novel decentralized training methods for the stochastic compositional optimization problem. In particular, we proposed a gossip- based decentral- ized stochastic compositional gradient descent (GP-SCGI) method and tradkent-trucking-- -haseed decentralized stochastic compositional gradient descent (GT-SCGI) method. With our methods, different devices can collaboratively optimize Eq. ( However, establishing the convergence rate of our proposed methods is challenging. Existing convergence analysis techniques for decentralized SGD are not applicable to our methods because the stochastic compositional gradient is different from the stochastic gradient. To address this challenge, we proposed new convergence analysis techniques for the decentralized SCGD method, where we show how to bound the gradient variance and the consensus error under the decentralized setting. In particular, both GP-SCGI and GT-SCGD 1 to achieve e-accuracy solution, where K is the number can achieve the convergence rate O K2² of devices. It indicates that methods achieve the linear speedup with respect to the number of devices, which is consistent with decentralized SGD. To the best of our knowledge, our work is the first one to establish the convergence rate of decentralized SCGD and achieving the linear speedup. Moreover, the sample complexity of our methods is O( k==) )- It indicates that our methods can achieve better sample complexity O than (233) of traditional SCGD [20] when K = 1, which further confirms the superiority of our methods. Finally, we applied our proposed methods to optimize the model-agnostic meta-learning problem. The empirical results confirm the effectiveness of our methods. In the following, we summarize the contributions of our work.
We proposed two novel decentralized stochastic compositional gradient descent methods: GP-SCGD and GT-SCGD, This the first work studying the decentralized training method for stochastic compositional optimization problems.
We established the convergence rate of our decentralized stochastic compositional gradient descent methods with novel theoretical analysis. This is the first work establishing the convergence rate for decentralized SCGD and showing the linear speedup with respect to the number of devices. In addition, our methods can achieve better sample complexities than traditional SCGD.
The extensive empirical evaluation on the model-agnostic meta-learning task confirms the
effectiveness of our proposed methods.
2
Related Works
2.1
Stochastic Compositional Optimization Problem
The stochastic compositional optimization problem is common in the machine learning field. However, it is more difficult to optimize than the standard non-compositional problem. The reason is that its stochastic gradient is not unbiased estimation of the full gradient, which is shown as follows:
_ Vf (): # Vg(x) " fg(((()))
To train the stochastic compositional problem efficiently, numerous methods have been proposed in the past few years. Specifically, [20) developed the stochastic compositional gradient descent (SCGD) method, which is defined as follows:
u4 = (1 - 9 11-1) + 11-19 Be,1)
(3)
11+1 = 2, Vg V (u,;
where Be, and Açt denote the random samples, < B, < is a hyperparameter, and ve is the learning rate. Here, us serves as the estimator of the inner function g(æz), and then the gradient

---

vgf(g(zz)) is estimated by V (uf(u;;A,.) As result, this stochastic compositional gradient Vg(a;; B ( Aça; has a smaller variance to improve the accelerate the convergence speed. However, it still has worse theoretical convergence rate than SGD. Furthermore, improve the convergence speed of SCGD for nonconvex problems, advanced variance reduction techniques have been incorporated into SCGD. For example, 25 incorporated the variance reduction technique SAGA [I5] to SCGD and obtained better convergence rate. Later, [27] employed another variance reduction technique SPIDER [S] for SCGD, while (23 accelerated SCGD with the STORM 3 variance reduction technique. More recently, some works [2] 10) disclosed the connection between stochastic bilevel optimization problems and stochastic compositional problems and developed the alternating SGD method to solve Eq. (T). However, all of these methods only studied the convergence rate for the single machine case, ignoring the distributed setting.
2.2 Decentralized Training Methods
Recently, with the emergence of large-scale data, numerous distributed training methods [16 13 14
18 II 7 8 have been proposed. Among them, the decentralized training method, where different devices conduct the peer-to-peer communication, has attracted lot of attention. In particular, there are two kinds of communication strategies in a decentralized training system. They are the gossip strategy and the gradient tracking strategy. Based on the gossip strategy, [13] studied the convergence rate of decentralized SGD and disclosed how the topology of the communication graph affects the convergence rate. Additionally, numerous works aim to reduce the communication cost of the gossip-based decentralized SGD by compressing gradients or skipping the communication step. Meanwhile, based on the gradient-tracking strategy, [17 developed the distributed stochastic gradient tracking method and established its convergence rate. Recently, some works [18] 22) combined the variance reduction strategy and the pradient-trackinn strategy further accelerate decentralized SGD, However, all of these methods are not applicable to SCGD, Thus, in this paper, we will develop efficient decentralized SCGD methods for optimizing the stochastic compositional optimization problem.
3 Decentralized Stochastic Compositional Optimization Methods
3.1 Problem Definition
Formally, we consider the distributed stochastic compositional optimization problem, which is defined as follows:
K E
min
((()
(x: (c:E)):s)]
(4)
FER
K
where x E Rdd denotes the model parameter, K is the total number of devices, (A) = (x (v: O) Rdd R and gik) (*) (x:; E)] TRd TRd' are smooth functions on the k-th device, and accordingly Es [[ (Eg (z: (x: is the loss function on the k-th device. In other words, each device has its own data and all devices collaboratively learn the model parameter by utilizing their local data.
To efficiently train this distributed stochastic compositional optimization problem, we consider the decentralized training method. In particular, each device connects with its neighbors, composing a communication network. All devices conduct the peer-to-peer communication based on this communication network. Formally, we represent the communication network with G (V, W) where V = (01, "2,... Ux denotes all devices and W = [w:y] E TR K is the adjacency matrix the adjacency matrix
which indicates whether two devices are connected or not. Following [ B3
Wi is assumed to satisfy the following assumption.
Assumption 1. The adjacency matrix W has the following properties:
Nonnegative: Wij 2 0, Vi
Symmetric: Wij Wji Vi, j.
Doubly Stochastic: Σn= Wij 1, Σ Wij = 1.
3

---

The eigenvalues of W can be sorted as |aa S S 12l < A1l =
In our convergence analysis, we denote À X2l for simplicity. In terms of the aforementioned decentralized training setting, we proposed two descentralized stochastic compositional gradient descent methods. The details are described in the following subsection.
3.2 Gossip-based Decentralized Stochastic Compositional Gradient Descent Method
In Algorithm [ we developed the gossip-based decentralized stochastic compositional gradient descent (GP-DSCGD) method. Following the standard SCGD method [20], each device estimates
the inner-level function g (8)) (kk) with ui (k) follows:
(5) where Y > and 3, > 0 are two hyperparameters, 73, < 1. is the index of devices and t is the index of iterations. Different from the standard SCGD method in Eq. (3). there is additional hyperparameter y when computing "t which can help controlling the estimation variance. We will show it in theoretical analysis in Appendix. Based on this estimation, each device computes the stochastic compositional gradient 2{*) as shown Line 9. Then, each worker uses the gossip communication strategy update the local model parameter as follows:
U1
(k: = (1 - (1--)(-1)u (2) + (h (k), 1
(k)
Σ JEN
Wkjzt (7( (k)
(6)
1+1
where 7) > 0 denotes the learning rate, No. = (ilwky > 0} is the neighboring devices of the k-th device. Here, the first term the right-hand side incurs the communication average the model parameter of neighboring devices, and the second term indicates to update the model parameter with the local gradient 2(4), Then, instead of using (k) as the new model parameter, compute the model parameter of the (t + 1)-th iteration as follows:
+ = _ + (r - x (
In fact, this strategy couples the update of u, (k) and x; (k) by the sharing hyperparameter Br, which can benefit controlling the estimation variance of ut (k) All devices repeat the aforementioned steps until the iterates converge.
Algorithm 1 GGsssip Decentralized Stochastic Compositional Gradient Descent (GP-DSCGD)
(k) vo. 3r 0, > 0, 1) > Input: 20
1: for t = 0, ... T - 1, each device & do
2: Sample subset of samples Bx(²) to compute:
3: if 0 then
" (k) (k) (1r (b)))
4:
5:
else
ut (R)
(1 (.8-1104 (k) 7/:-19 (b) (z) (k), )
6:
7:
end if
((())
(x) (k); ; kb
8:
Sample subset of samples A (k)
9:
to compute:
(k) (0 ( (()) (m (k).
,,, (k)
21
10:
Z L+1 EjEN., wayzt 17t
x 24+1 zi + ((a( zi (k)
(k) (k)
12: end for
3.3 Gradient-Tracking-baas Decentralized Stochastic Compositional Gradient Descent Method
Besides the gossip communication strategy, the gradient tracking strategy is also widely used in the decentralized training method. Therefore, completeness, we further proposed the gradient- tracking-based descentralized stochastic compositional gradient descent (GT-DSCGD) method in

---

(k) and 2t as shown in Lines 2-9. Different Algorithm| 2 Same with Algorithm we compute "y
(k)
from Algorithm GT-DSCGD introduces an auxiliary variable st for each device, which used
to track the global stochastic compositional gradient R > (k) updated as follows:
18 17 Specifically, & is
(k)
(M) Wkist (-1 + 2t
(8)
JEN
is easy to verify that & update the model parameter follows:
E
(k)
(k) Ex=1 21
Then, each device uses s; (k)
(k) instead of 21 to
k
(k)
wkjat
1788 (8)
JENu
To sum up, the difference between our two methods is that GT-DSCGD has an additional step to track the gradient with 8 and accordingly updates the model parameter with
Algorithm Gradient- Traettt-rraaiinn-bbae based Decentralized Stochastic Compositional Gradient Descent (GT-DSCGD)
Input: (k) Tu, 2 0, [ 0, 3, 0, 7 0, 0.
1: for = 0, ... T - 1, each device do
2: Sample subset of samples (x(*) to compute:
3: it' then
4: ui (k) (/hk (x, ;
5:
else
(k), (B())) 6: u, (k) (1 9/1-1)44 )u, (*) (k)
7: end if
o/t) (x) (z) (R),
(z, BBaa)
8:
Sample a subset of samples A (8)
9:
to compute:
2, (k) (o) (T (b)
(w
(k).
A (k)
10:
s EjEN., 0kjst-1 +
2
(k)
// gradient tracking
F41 EjeNs Wkjatt (1)
F (K)
(k)
11:
ns;
s F41 It + ((((((() It (k)
(R) (k)
12:
13: end for
4 Convergence Analysis
4.1
Assumptions
To establish the convergence rate of our proposed two methods, first introduce some standard assumptions, which are also used in existing stochastic compositional gradient descent methods
20 21 26 24).
Assumption 2. (Smoothness) For Vy,, U/2 Rdd and VI1, Rdd there exist constant values L, > and L > such that
(4) (211 - (xz)) & Lgll=1 - x2ll (10) | f (y)) - v (K) (y2)l S L - 22l1, V
Assumption 3. (Bounded gradient) For Va E Rdd and Vy E TRod there exist two constant values C2 and Cj O such that
g (I: (1(E) Cg. E (
(11)
Assumption (Bounded variance) For x Rdd and y E C.d. there exist three constant values of > 0, 0g > 0, 0g' > O, such that
(k) (v: (w)PP B 1b) (x:E) ( oz ( (x) o
(12)
Bilg (x:E) (x:E)
5

---

To study the convergence rate of our two methods, we denote F(z) = 1 F =
k (()
K E f(h) (g(+) Then, F(x) is Lp-smooth with LF - oyL, + CyLgg In addition, we denote ū; = E oy (k) and x, as the optimal solution.
4.2 Convergence Rate
In terms of aforementioned definitions and assumptions, we establish convergence rates our proposed A and Algorithm 2 respectively.
Theorem 1. Assume Assumptions
hold, for Algorithm by setting |A, |B B, 7 >
3t = B S min 85 2n 13. 7) S mil (1, 12, 113 where
7
1-
27 + 2
124C 199
1/1
3 3V602
1/2
2
72
20
Vb2 + 4ac
b
1240 + 33)
12C
27C L
1/3 =
2a
8(1 - C2
1 X2
+
272
b
X2 x
4C,
1.
(13)
we can get
T-1 Σ 1=
2F(F(x0) F(x.)] nST
2(3C + C213333 + 24yoz)
T
B
(14)
48C700 + 160220 + 130
480
16,
BBB
3B
Corollary 1. Assume Assumptions 1 hold, for Algorithm and y to be two positive constant values, we can get
by setting
0 K
B B=
T
2B(F(x0) - F(x.))
233C + 3C703. + +G1 2470y)
E
(F)
BVKT
VKT
(15)
48C703. + +6G0203 + 130
LC
48a
1630
KT
3VTT
For sufficiently large T, Corollary 7 indicates that GP-DSCGD can achieve linear speedup with respect to the number of devices, which is consistent with decentralized SGD.
Remark 1.
Remark 2. To achieve the c-accuracy solution such that + EET V S c, the communi-
cation complexity is O Ke and the sample complexity is T x B = O Kc
When K = 1, the
sample complexity of our method is better than ((2) ) of traditional SCGD 2201
Note that when T is sufficiently large, 2nLE could be greater than 1 so that f and y do not affect the order the convergence rate in Corollary [ Additionally, our method does not use the acceleration that the sample complexity of our method is
or variance reduction techniques as 21 25 24 inferior to those methods.
Theorem 2. Assune Assumptions
4 hold, for Algorithm 2 by setting LAt 3 = B & min By. 2nLF 1), and n min(n, 12, (t)) where
|B
B, 0.
4~ - x2)
7
1n = L +1022899447 + 1667 1/2 =
2 1/19/113 CGLL
(16)
V 4ac
L7
3 12
3C
b
X2 (1 2)2,
2a
4-2
8
128-2

---

we can get
1 T 1=0
T
F - F(x.))
60%03 + +67 + +30
BIIVF(E)
nST
B
(C70 + (193) + 031.))
1C70 + (1,3) + C312))
B2B
2 B
187 + Cz0f))
96m(C707 + C200)) 101-22937
+ 8C 966(1
L332
X2)B
7BB
(17)
Corollary 2. Assume Assumptions 1 1ohod for Algorithm
by setting = 0 X VI
B = -
3 and y to be two positive constant values, we can get
(((o()))) - F(a.))
48(C70g + Cg07)
96(C70g + C200))
B
T t=0
BVK
7(1 (1-X2)) X2YT
21-
24
48(C707 + (103) C3T2))
KK/22///2
72 22)K1/223/2
o0 + 6070'. + 30 10 8021702 + 96(1 - 2)02
VKT
BBVTT
(18)
Remark 3. For sufficiently large T, Corollary 2 also indicates that GT-DSCGD can achieve linear speedup with respect to the number of devices, which is consistent with the decentralized SGD method.
Similar to GP-DSCGD, to achieve the e-accuracy solution such that + Ei= B V F (f+) S
the communication complexity of GT-DSCGD is O Kc and the sample complexity is O Kc3
4.3 Proof Sketch
In this subsection, we present the main idea of establishing the convergence rate of Algorithm I More details are deferred to Appendix.
and
Algorithm 2
Proof sketch of Theorem I To establish the convergence rate of Algorithm 1 proposed novel potential function as follows:
K
4n K 111 (x.
P B(
g(k)
Elll (k)
K
K
1=1
(19)
MB 1
21
Eell
Zz 113
1C313
K
K 1=1
1=1
Then, the task boils down to bound each term in this potential function. In particular, we obtain these bounds in Lemmas 3 5 hyperparameter as shown in Theorem 1 we can get
respectively in Appendix. With these lemmas, by setting the
Po+1 P. n
EIIVF(.))11 33(30 + 3C303 + C21300 + 2470y)
24C30² 80 13 TmB
(20)
B
4C3
By summing 1, complete the proof.
Proof sketch of Theorem 2 Similar to the convergence analysis of Algorithm we also proposed novel potential function to facilitate the theoretical analysis. Here, different from the proof of
Theorem we didn't directly use E[[] (({)) - sell in the potential function. Instead, we introduce an (k) which is defined as follows:
additional variable 1
(k) = 0 h (1) = Σ
wkght + qt -
(R)
(21)
JENoN
7

---

where (1) (x) ( (k) and - 0. Here, the difference between hgg and s(()) is that h uses the full gradient of each function while st uses the stochastic gradient. Note that hgth is just used for theoretical analysis. It does NOT need to be computed in practice. Based this new variable, we define the following potential function:
L
K
711 - A)
K
P: = [[F(t)
+
E Elll
(K) - (x)
Elll
(K) - -..11))
K
7 K
k=1
B B
(k)
Fz 1x
K
(22)
Similar to the proof of Theorem the task boils down bound each term in the potential function, respectively. The detailed bounds can be found Lemmas] 9
13 Then, we can also get the bound for P Pt and complete the proof by summing over iterations like the proof of Theorem
5 Experiment
5.1 Model-Agnostic Meta-Learning
Model-Agnostic Meta-Learning (MAML) 66] is to learn a meta-initialization model parameter for of new tasks. Specifically, it is to optimize the following model:
min E Dix. 4, (EDi... mis
(z VV, Dinain) Di
(23)
ZERe
where p is the task distribution, a is the learning rate, 1 is the loss function for the i-th task, Dimin the training set of the i-th task and Dist is the testing set of the i-th task. Note that we omit the superscript & for simplication. MAML can be reformulated as stochastic compositional optimization problem as follows:
f(y: 1, (y. Dies). where < (i, Diest) g(x;E) = a - al, (Ir, Dirai)) ), where Ç = Disin
(24)
Then, the stochastic compostional gradient to optimize MAML. In particular, Ue to track ((x) as follows:
We = (1-Mh-1)):- + Be,,) = (I-
Va (x+-1, 1, Pirin ))
(25)
our experiment, we will use GP-DSCGD and GT-DSCGD to solve the distributed MAML problem, where tasks are distributed on different devices.
5.2 Regression Task
Following Go, we verify the performance of our methods with the regression problem. particular, each task in MAML is regression task, which maps the input to a sine wave. Different sine waves have different amplitudes and phases. Specifically,
generate set of sine waves, the amplitude is uniformly drawn from [0.1, 5.0] and the phase is uniformly drawn from [0, m]. Additionally, the input randomly drawn from 55.0, 5.0]. Then, we use a parameterized neural network [(x;; a) to approximate the sine wave. In our experiment, f(x;; a) has two hidden layers and the dimensionality of different layers is [1, 40, 40, 1). In each hidden layer, we use the ReLU function as the activation function. There are numerous regression tasks, the goal of MAML is to learn good initialization for the model parameter x such that it can be quickly adapted to new regression tasks and have good performance.
In our experiment, we use four GPUs where each GPU viewed device. These devices compose ring graph. On each device, the number of tasks in each meta-best batch is set to 200. The number of samples each task for training set to 10. As for the testing set, the number of tasks set to 500 and the number of samples in each task is also set to 10. In addition, the number of iterations for adaptation the training phase set to while set to 10 in the testing phase. verify the performance of our methods, we compare them with the gossip- based decentralized SGD (DSGD)
8

---

method. Specifically, the decentralized SGD method directly uses = (xz). In other words, DSGD directly uses - VV, (zx-11, D Pinin] for adaptation rather than that in Eq. (25). In our experiment, 0.01. For adaptation, the learning rale 7 of DSGD better performance in MAML [6]. we actually use the decentralized Adam in our experiment as the baseline method. Accordingly, for fair comparison, we also use the adaptive learning rate for addition, we set (k) (k) Bma,.) Therefore, y 3.0, 7) 0.03, B 0.33. The reason for this setting is that 21+1 2t
17 0.001. Sine Adam has
our two methods based on the stochastic compositional gradient 2(k) and &
the effective learning rate 3r) of our methods is approximately equal to that of the baseline method, which is fair comparison.
In Figure [[a] we show the average and standard deviation of the training loss across different devices. It can be seen that our two methods converge much faster than DSGD. The reason is that our methods use un to track the gxzz) so that the estimation variance for g(xe) is smaller than DSGD, Meanwhile, it can be seen that our two methods achieve similar performance. Moreover, in Figure [(b) we plot the loss function value when using the learned model parameter as the initialization for new tasks and
then conducting 10 gradient descent steps. It can be seen that our two methods can achieve better performance in adaptation to the new task.
DSGD
DSGD
GP-DSCGD
GP-DSCGD GT-DSCGD
GT-DSCGD
25
Loss
Loss
1.5
1.0
1
0.5
200
400
600
800
1000
Iteration
Iteration
(a) Sine: meta--raining
(b) Sine: meta-test
2.00
DSGD
1.75
GP-DSCGD
GT-DSCGD
33-
3.25
Loss
Accuracy
1.00
0.75
3.3
0.50
W.A
0.00
Epoch
DSGD
GP-DSCGD
GT-DSCGD
(c) Omniglo: meta-training
(d) Omniglot: meta-test
Figure 1: Meta-training and meta-test for the regression and classification task.
5.3 Classification Task
Besides the regression task, we also verify the performance of our distributed training methods with the classification task. Here, we use the Omniglot image dataset [12]. It has 1623 characters and each character has images. Under the MAML setting, recognizing each character corresponds to a task so that there are 1623 tasks totally. In our experiment, we use 1200 tasks as the training set and the rest tasks as the testing set. To recognize the character, we use the same convolutional neural network [6). To get the meta-initie mntaa-nitialization for the model parameter, use the 5-way 1-shot setting. As

---

for the distributed training, we still use four devices. The meta batch-size on each device is 8. The number of iterations for adaptation in the training phase set to I while is set to 3 in the testing phase. Additionally, we set the inner learning rate = 0.4, the learning rate of DSGD = 0.001. As for our methods, we keep the same learning rates as the regression task.
From Figure [[c] we also plot the loss function value for the classification task. We can still find that our two methods converge much faster than DSGD, which further confirms the effectiveness of our proposed methods. Additionally, we show the classification accuracy after adaptation for new tasks Figure I(d) It is obvious that our two methods can achieve higher accuracy and smaller variance compared with DSGD, which further confirms the effectiveness of our methods.
5.4 Additional Experiment
In this experiment, we verify the performance of our methods with different number of devices. In particular, we compare the performance using four GPUs and that using eight GPUs for the regression task. For these two settings, we use the same overall meta-batch size that in Section 5.2, and then uniformly distribute the tasks on all devices. As for other hyperparameters, they are the same for these two settings. In Figure 2 plot the training loss function value with respect to the consumed time. It can be observed that our two methods converge much faster when using more devices, which confirms the speedup of the decentralized training.
GP-DSCGD-8
GT-DSCGD-8 GT-DSCGD-4
GP-DSCGD-4
Loss
Loss
200
400
600
200
600
Time(seconds)
Time(seconds)
(a) GP-DSCGD
(b) GT-DSCGD
Figure 2: Meta-training for the regression task by using GP-DSCGD and GT-DSCGD.
6 Conclusion
In this paper, studied the distributed training methods for the stochastic compositional optimization problem. In particular, we proposed two novel decentralized stochastic compositional gradient descent method based on the gossip communication mechanism and the gradient tracking communication mechanism. As far as we know, our work is the first one facilitating distributed training for large-scale stochastic compositional optimization problem. Meanwhile, we established the convergence rate of our proposed methods with novel theoretical analysis. The theoretical results indicate that our two methods achieve linear speedup with respect to the number of devices. This is the first work disclosing this favorable result. At last, extensive experimental results on the MAMI. task demonstrate the superior performance of our methods.
Acknowledgments and Disclosure of Funding
This work was partially supported by NSF IIS 1845666, 1852606, 1838627. 1837956, 1956002, OIA 2040588. In addition, this research includes calculations carried out on HPC resources supported in part by the National Science Foundation through major research instrumentation grant number 1625061 and by the US Army Research Laboratory under contract number INF-NF-16-2
10

---

References
[1] T. Chen, Y. Sun, and W. Yin. Solving stochastic compositional optimization is nearly easy solving stochastic optimization. arXiv preprint arXiv:2008. 10847, 2020.
[2] T. Chen, Y. Sun, and W. Yin. Tighter analysis of alternating stochastic gradient method for stochastic nested problems, arXiv preprint arXiv:2106. 13781, 2021.
[3] A. Cutkosky and Orabona. Momentum- based variance reduction in non-convex sgd. In Advances in Neural Information Processing Systems, pages 15236-15245, 2019.
[4] A. Defazio, Bach, and S. Lacoste-Julien, Saga: fast incremental gradient method with support for non-strongly convex composite objectives. arXiv preprint arXiv:1407.0200 2014.
[5] C. Fang, C. Li, Z. Lin, and T. Zhang. Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator. In Advances in Neural Information Processing Systems, pages 689-699, 2018.
[6] C. Finn, P. Abheel, and S. Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In International Conference on Machine Learning, pages 126-1135. PMI.R, 2017.
[7] H. Gao and H. Huang. Periodic stochastic gradient descent with momentum for decentralized training. arXiv preprint arXiv:2008. 10435, 2020.
[8] H. Gao, A. Xu, and H. Huang. On the convergence of communication-effiiien local sgd for federated learning. In Proceedings the AAAI Conference Artificial Intelligence, volume 35, pages 7510-7518, 2021.
[9] H. Gao, H. Xu, and S. Vucetic. Sample efficient decentralized stochastic frank-wolfe methods for continuous dr-submodular maximization. Thirtieth International Joint Conference on Artificial Intelligence, 2021.
[10] R. Grazzi, M. Pontil, and S. Salzo. Convergence properties of stochastic hypergradients. In International Conference on Artificial Intelligence and Statistics, pages 3826-3834. PMLR, 2021.
[11] A. Koloskova, T. Lin, S. U. Stich, and M. Jaggi. Decentralized deep learning with arbitrary communication compression. arXiv preprint arXiv: 1exxv:/907.000 99070093566 2019.
[12] B. M. Lake, R. Salakhutdinov, and J. B. Tenenbaum. Human-level concept learning through probabilistic program induction. Science, 350(6266): 13322 - 2015.
[13] X. Lian, C. Zhang, H. Zhang, C.-J. Hsich, W. Zhang, and J. Liu. Can decentralized algorithms outperform centralized algorithms? case study for decentralized parallel stochastic gradient descent. arXiv preprint arXiv:1703 777700050666. 2017.
[14] B. McMahan. E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas. Communication-efficeee learning of deep networks from decentralized data. In Artificial Intelligence and Statistics, pages 1273-1282. PMI.R, 2017.
[15] A. Mokhtari, H. Hassani, and A. Karbasi. Stochastic conditional gradient methods: From convex mini- mization to submodular maximization. Journal of Machine Learning Research, 21(105):1-44 49, 2020.
[16] F. Niu, B. Recht, Ré, and S. J. Wright. Hogwild!: A lock-free approach to parallelizing stochastic gradient descent. arXiv preprint arXiv:1106.5733 2011.
[17] S. Pu and A. Nedié. Distributed stochastic gradicnt tracking methods. Mathematical Programming, pages 1-49, 2020.
[18] Н. Sun, S. Lu, and M. Hong. Improving the sample and communication complexity for decentralized non-convex optimization: Joint gradient estimation and tracking. In International Conference on Machine Learning, pages 9217-9228. PMLR, 2020.
[19] R. S. Sutton and A. G. Barto. Reinforcement learning: An introduction. MIT press, 2018.
compositions of expected-value functions. Mathematical Programming, 161(1-2):11944) 2017. [20] M. Wang, E. X. Fang, and H. Liu, Stochastic compositional gradient descent: algorithms for minimizing
[21] M. Wang, J. Liu, and E. X. Fang. Accelerating stochastic composition optimization. The Journal of Machine Learning Research, (8(1)3321137453 2017.

---

[22] R. Xin, U. A. Khan, and S. Kar. A near-optinal stochastic gradient method for decentralized non-convex finite-sum optimization. arXiv preprini arXiv:2008.07428, 2020.
[23] J. Yang and W. Hu. Stochastic recursive momentum method for non-convex compositional optimization. arXiv preprint arXiv:2006.0166 01688, 2020.
[24] H. Yuan, X. Lian, and J. Liu. Stochastic recursive variance reduction for efficient smooth non-convex compositional optimization. arXiv preprint 131555191,. 2019.
[25] J. Zhang and I.. Xiao. A composite randomized incremental gradient method. In International Conference Machine Learning, pages 7454-7462, 2019.
[26] J. Zhang and L. Xiao, Multi-level composite stochastic optimization via nested variance reduction. arXiv preprint arXiv: /908. / 1468, 2019.
[27] J. Zhang and L. Xiao. A stochastic composite gradient method with incremental variance reduction. In Advances in Neural Information Processing Systems, pages 9078-9088, 2019.
12


Reviews:
[{"review_id": "XSNANbqzauH", "reviewer": "Reviewer_HU5v", "summary": "This paper studies the stochastic compositional optimization problem under the distributed learning setting. Two decentralized optimization methods are proposed for solving this problem, both of which are based on SCGD method. Theoretical analysis is conducted to provide convergence bound for both methods. Experiments are also carried out accordingly.", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "After rebuttal:\nThe authors' clarification about the overall complexity of the algorithm seems reasonable to me. I decided to raise the score. Hope these discussions about the algorithm complexity can be combined into the final version.\n\n=====================================================\n\nMy main concern about this paper is that the theoretical bounds are not well discussed and compared with existing methods.\n\nIt is only mentioned in the paper that the number of iterations required by the proposed methods is $T=O(1/(K\\epsilon^2))$, the same as decentralized SGD. But according to Corollaries 1 and 3, the proposed methods use the batch size $B=O(\\sqrt{KT})$, which depends on the number of nodes $K$ and the number of iterations $T$, while decentralized SGD only needs batch size 1. So, it is unfair to directly compare the number of iterations. The overall computation complexity, which takes both factors into account, should be discussed and compared with decentralized SGD and the single-machine SCGD to see if the proposed methods really have linear speedup and optimal convergence rate.\n\nThe values of the hyperparameters used in the experiments are not mentioned. Especially for the batch size, is the theoretically optimal batch size $B=O(\\sqrt{KT})$ used here, or just set $B=1$? Also, the batch size of the baseline should also be clarified.\n\nBesides, I guess there are some typos or errors in the convergence analysis part. What is $\\beta$? Is it $\\beta_t$ is the algorithm? I also failed to locate the term $1/(2\\eta L_F)$ mentioned in Remark 2.\n\nOne more suggestion: since this paper focus on distributed optimization, it is better to reflect this in the title (though I am not sure if the title can be modified in this stage).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "WGKegqjKi2O", "reviewer": "Reviewer_eCMs", "summary": "This paper proposed two decentralized training methods for stochastic compositional optimization problem and establish the convergence results for them.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "This paper introduces the decentralized training methods to solve the stochastic compositional optimization. Although I don’t get into the whole proof, the techniques used in this paper are fairly standard and the analysis is technically sound. My main concern is the significance of this paper. \n\nMinor Comments:\n\n1. I suggest the authors replace the ‘fast training methods’ in the title with e.g.’decentralized training’ as this is a paper on the decentralized training, rather than accelerating the convergence (on single machine).\n\n2. Please formalize the definition of $g$ and $f$. Note that the $f$ and $g$ in (1) depends on some random variable, but are deterministic functions in (2) and some parts hereafter.\n\n3. Should it be better to denote the difference of $f^{(k)}$ and $g^{(k)}$ in (4) by the difference of the corresponding random variables? This means the difference are induced by different batch of data that are sampled according to the random variables, which avoid some potential ambiguity. Note that in (3) the authors use some similar notation. I feel the current notations mean that each device have different $f$ and $g$.\n\n4. I would like to ask what’s the relation of the analysis in this paper and analysis of smooth SCGD and smooth distributed SGD. It would be better to illustrate the technical significance beyond the direct combination of the previous work. Specifically, given that the gradient variance are bounded, it’s not so hard to derive Lemma 14 that replace $s_t$ with $h_t$ as emphasized in Line 201-209. It would be more interesting if there’s other technical insight in this paper.\n\n5. For experiments, I think the convergence rate with different $K$ is necessary, as the authors argue it as a main contribution.\n\nI tend to accept this paper, but due to the concern on the technical significance, I would rather assign a conservative score for it.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have properly addressed them.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "O3WHOOMMIp", "reviewer": "Reviewer_P4ej", "summary": "This paper studies decentralized stochastic compositional optimization problem, and proposes two algorithms: GP-DSCGD and GT-DSCGD. They also have convergence guarantee for both algorithms. This problem has significant application in model agnostic meta learning. \n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "The problem studied in this paper has significant application in large scale distributed meta learning, so I think this work has nice results except issues discussed below. As far as I know, this paper is the first to study decentralized stochastic compositional optimization, and provide analysis. From my point of view, it is novel. The theoretical analysis looks sound as far as I checked. The theoretical results are supported through experiments. The paper is well-organized and both experimental and theoretical results are clearly presented.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "If my understanding is correct, the gradient tracking based algorithm has the same convergence rate with GP-DSCGD, then I was left wondering what would be its significance.\n\nAlso, I notice that we need a fairly large batch size $\\sqrt{KT}$ to guarantee the convergence and appreciate clarification from authors.  In particular, is it due to the decentralized setting, or the single machine version of the algorithm also needs a large batch size?\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "0bB8kD8HgQ", "reviewer": "Reviewer_AZDJ", "summary": "The paper presents two algorithms for distributed optimization of stochastic composite objectives where one is interested in optimizing one outer objective that is computed on points that depend on another function (called the inner objective in the paper).\nThe authors adapt two strategies for distributed optimization to the stochastic composite optimization problem and derive convergence rates for the general non-convex outer objective problems, that show linear rates w.r.t. the number of devices used (this is probably the main contribution of this paper).\nFinally, they present a set of experiments in meta-learning using MAML as meta-learning algorithm.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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": "Clarity: \nThe paper is well written and generally clear. Few exceptions are: \n- missing definition of the non-stochastic versions of g and f, used, for instance, in Eq. (2). I interpret these to be $\\mathbb{E} f$ and g, but this should be clarified.\n- perhaps, more importantly, I find a discussion on the limit case where K=1 (i.e. only one device) missing. How do the algorithms read in this case? and, what are the similarities/differences with [14]? \n- one case where composite functions emerge in machine learning is bilvel optimization (not limited to the MAML setting). In bilevel optimization typically the term ''inner objective''/inner function is reserved to the (scalar-valued) objective of the inner problem. In this work, $g$ essentially maps to the argmin operator, which is in general not necessarily a function (could be multiple minimizes). I think it would be appropriate to include a brief comment on this after the authors introduce the main assumptions, perhaps also linking to some recent works on stochastic bilevel optimization, e.g. [1].\n\nOriginality and significance:\nThe work seems original and significant to me, as the methods proposed may be applied to many problems of interest in ML, especially in meta-learning. However, I am not particularly an expert in the field of distributed optimization, so cannot evaluate properly this point.\n\nQuality: \nThe derivations seem correct to me, although I have not checked carefully the supplementary material.\n- One main concern that I have about this work is that I think there is a disconnect between the theoretical results and the experimental section. Specifically, as the authors claim that one main contribution of the paper is about showing linear rates w.r.t. the number of devices, I would have expected some empirical results in this regard. Instead, all the experiments are conducted with only 4 devices, which makes it impossible to appreciate this aspect of the paper. This point should be address in the rebuttal, ideally with some empirical result.\n\nTypos:\n- L80 (the) \n- L88 (of) \n\n[1] Grazzi, Riccardo, Massimiliano Pontil, and Saverio Salzo. \"Convergence properties of stochastic hypergradients.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2021.\n\n____\nPost-rebuttal:\n\nThanks for your reply! I am raising my score and suggest acceptance. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not applicable", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper considers the Stochastic Compositional Optimization on the decentralized training setting, which is an interesting and novel problem, as recognized by reviewers. A decentralized stochastic compositional gradient method is proposed. The proved convergence rate is provided as well. Most reviewers' comments have been addressed. Although we decide to accept this paper, authors should realize that this rate is not tight, comparing to the special case (single machine), which should be explicitly pointed out in the revision.
Decision: Accept (Poster)