1
S3LDBO: A Snapshot Single-Loop Algorithm for Decentralized Bilevel Optimization
arXiv:2605.31311v1 [math.OC] 29 May 2026
Chao Yin, Youran Dong, Shiqian Ma, Bofan Wang, and Junfeng Yang
N
Abstract—Networked AI systems increasingly rely on multiple agents that collaboratively learn and adapt models over communication networks. In such systems, bilevel formulations naturally arise in hyperparameter optimization, data cleaning, and meta-learning, but the repeated evaluation of gradients, Jacobians, and Hessians can impose a substantial computational burden on individual agents. To address this challenge, we propose Snapshot-SLDBO (S3 LDBO), an efficient single-loop decentralized bilevel optimization algorithm that enables agents to intermittently skip expensive derivative evaluations through a snapshot mechanism. This mechanism can be interpreted as an autonomous computation-adaptation strategy for networked AI, where agents selectively perform costly local updates while maintaining global collaborative learning. We establish the ergodic iteration complexity and the high probability nonergodic iteration complexity of the proposed algorithm within a deterministic setting. Experimental results on hyperparameter optimization with synthetic and MNIST datasets, data hyper-cleaning on FashionMNIST, and decentralized meta-learning on miniImageNet demonstrate that the proposed algorithm improves computational efficiency while maintaining competitive learning performance. Index Terms—Decentralized bilevel optimization, snapshot gradient tracking, single-loop, networked AI systems.
I. I NTRODUCTION
This paper focuses on the following decentralized bilevel optimization (DBO) problem: n
min Φ(x) := F (x, y ∗ (x)) :=
x∈Rd
1X Fi (x, y ∗ (x)) n i=1 n
s.t. y ∗ (x) ∈ argmin f (x, y) := y∈Rq
1X fi (x, y), n i=1
(1)
where n collaborative nodes, connected via a communication graph G = (V, E), jointly solve this problem. Here, V represents the set of agents, and E represents the set of feasible communication links between the agents. Each node i privately holds an upper-level cost function Fi : Rd × Rq → R and a lower-level cost function fi : Rd × Rq → R. The decentralized framework eliminates the need for a central server and enables more efficient and scalable computation across distributed networks [12]. In this paper, we propose an efficient single-loop algorithm for solving (1). A. Related work a) Bilevel optimization: When utilizing gradient methods for solving (1), a central challenge is how to estimate the hypergradient ∇Φ(x), which is given by
ETWORKED AI systems, such as distributed sensing networks, n 1 X edge intelligence, federated learning systems, and multi-agent ∇Φ(x) = ∇1 Fi (x, y ∗ (x)) − ∇212 fi (x, y ∗ (x)) z(x) , (2a) n autonomous platforms, require multiple agents to collaborai=1 " #−1 n n tively learn and adapt models over communication networks [1]– X 1X 1 2 ∗ z(x) = ∇ f (x, y (x)) ∇2 Fi (x, y ∗ (x)) . (2b) 22 i [3]. A central challenge in these systems is how to enable each n i=1 n i=1 agent to update its local model efficiently while maintaining global coordination with other agents. This challenge becomes To address this challenge, various algorithms have been more pronounced when the learning objective has a hierar- proposed in the literature, leveraging approaches such as chical structure, where model parameters, hyperparameters, approximate implicit differentiation (AID) [9], [13]–[18], data weights, or task-specific adaptation variables must be iterative differentiation (ITD) [4], [6], [14]–[16], [19], [20] optimized jointly. Such hierarchical learning problems can and Neumann series-based approach [13], [17]. Furthermore, often be formulated as bilevel optimization problems. Bilevel both AID and ITD approaches involve heavy Hessian- and optimization (BO) has attracted increasing attention in recent Jacobian-vector multiplications, which also consist of a complex years. It has found important applications in meta-learning [4]– double-loop structure. Recently, [18] introduced a single-loop [6], hyperparameter optimization [4], [7], [8], reinforcement framework, named SOBA, to solve BO with single agent, learning [9], and adversarial learning [10], [11]. To achieve i.e., n = 1 in (1). This framework approximates z(x) without state-of-the-art results in these domains, vast training datasets requiring heavy matrix-vector multiplications, thus saving effort and distributed algorithms operating across multiple computing in solving the linear system. Specifically, the SOBA algorithm maintains three sequences, which are updated as follows: agents are often required. Chao Yin is with the School of Mathematics, Hohai University, Nanjing, P. R. China (e-mail: [email protected]). Youran Dong, Bofan Wang, and Junfeng Yang are with the School of Mathematics, Nanjing University, Nanjing, P. R. China (e-mail: [email protected]; [email protected]; [email protected]). Shiqian Ma is with the Department of Computational Applied Mathematics and Operations Research, Rice University, Houston, USA (e-mail: [email protected]).
y k+1 = y k − βk Dyk , v k+1 = v k + ηk Dvk , xk+1 = xk − αk Dxk , where αk , βk and ηk are positive stepsizes, Dyk , Dvk and Dxk are respectively unbiased stochastic estimators of ∇2 f (xk , y k ), ∇2 F (xk , y k ) − ∇222 f (xk , y k )v k and ∇1 F (xk , y k ) − ∇212 f (xk , y k )v k . The SOBA framework was later extended by [21] to address the case where the lower-level
2
problem is merely convex. [22] addressed the non-convexity of K is the iteration counter. Moreover, we establish a high the lower-level function and proposed two techniques to tackle probability non-ergodic convergence result for S3 LDBO. the resulting challenges. • We validate the proposed method on hyperparameter optimization, data hyper-cleaning, and decentralized metab) Decentralized bilevel optimization: In the past few learning tasks. The results demonstrate improved time effiyears, a series of decentralized optimization algorithms have ciency and competitive learning performance in networked been proposed to solve (1). The first algorithm for solving (1) AI scenarios. Additionally, we also study the numerical was proposed in [23]. They introduced the DSBO algorithm, impact of network topology and data heterogeneity on the which integrates a decentralized approach to solve the linear performance of S3 LDBO. system in (2). Subsequently, the same authors improved the DSBO algorithm by incorporating the moving average While S3 LDBO builds upon the foundational ideas of technique [24]. Other works on DBO include [25], in which SLDBO and SSGT, their integration into a coherent and a gossip-based DBO algorithm was proposed and its sample provably convergent algorithm presents non-trivial challenges. complexity was established, and [26], in which momentum The primary difficulty lies in adapting the snapshot mechaand variance-reduced techniques were employed to solve nism—originally conceived for single-level optimization—to distributed stochastic BO problems. All of these algorithms the more intricate, three-sequence dynamic (x, y, v) inherent rely on inner-loop updates to assess the lower-level solution in bilevel algorithms like SLDBO. Our core contribution is as well as the Hessian inverse, which demands extensive therefore not merely the algorithmic proposal, but the rigorous computational resources and leads to significant communication convergence analysis that validates this complex integration. overhead, thus greatly reducing their practical applicability. [27] We demonstrate that despite intermittent computations across proposed a stochastic linearized augmented Lagrangian method coupled sequences, the algorithm maintains a solid theoretical for solving (1), which, however, also requires heavy matrix- convergence guarantee, a key step toward making DBO more vector multiplications when approximating the hypergradient. practical for large-scale problems. We also note that our current Recently, [28] extended the SOBA algorithm [18] to the decen- analysis is focused on the deterministic setting, where full tralized setting and proposed the first single-loop decentralized gradients are accessible; extending this framework to the algorithm, named SLDBO, for solving (1). Similar to SOBA, stochastic realm remains an important direction for future SLDBO does not require heavy matrix-vector multiplications investigation. when approximating the hypergradient. Additionally, SLDBO imposes no assumptions regarding gradient heterogeneity or C. Organization the boundedness of {vk }. [29] introduced a decentralized The remainder of this paper is organized as follows. In SOBA with the moving average technique and established its transient iteration complexity. Similarly, [30] employed Section II, we introduce the notation, assumptions, and essential variance reduction and gradient tracking techniques to address preliminaries which will be utilized in subsequent analysis. In 3 the stochastic DBO problem. However, the consensus error was Section III, we propose the S LDBO algorithm and analyze its not taken into account in the convergence analysis. We point convergence. Numerical results on hyperparameter optimizaout that these single-loop algorithms still need to calculate tion, data hyper-cleaning, and decentralized meta-learning are gradients, Jacobian and Hessian matrices in each iteration, presented in Section IV to demonstrate the effectiveness of S3 LDBO. Finally, concluding remarks are drawn in Section V. which can be time consuming for large-scale problems. In this paper, we incorporate the snapshot gradient tracking II. P RELIMINARIES (SSGT) technique [31] – a recent technique for decentralized optimization – to SLDBO and demonstrate that the new We denote the optimal value of (1) as F ∗ . The gradients of algorithm S3 LDBO is much more efficient than SLDBO. f with respect to x and y are represented by ∇1 f (x, y) and Unlike traditional methods that track the average gradient of ∇2 f (x, y) respectively, and the Jacobian matrix of ∇1 f and decision variables, the SSGT tracks the average gradient of Hessian matrix of f with respect to y are denoted as ∇212 f (x, y) a snapshot point incorporating historical information. This and ∇222 f (x, y) respectively. Unless otherwise specified, ∥ · ∥ technique employs intermittent gradient, Jacobian, and Hessian refers to the ℓ2 norm for vectors and the Frobenius norm for computations, offering a more effective approach to utilizing matrices. The operator norm of a matrix Z is denoted by ∥Z∥op . computational resources. We also define the projection operator Pr , which projects a given point onto a Euclidean ball with radius r ≥ 0, i.e., B. Main results
Pr [z] := arg min∥z′ ∥≤r ∥z ′ − z∥ = min {1, r/∥z∥} z.
Contributions of this paper are summarized as follows. Throughout this paper, we adhere to the following standard • We propose a novel single-loop algorithm named Snapshotassumptions in the literature of bilevel optimization and SLDBO (S3 LDBO), which integrates the snapshot idea decentralized optimization problems. from SSGT [31] into SLDBO [28] and intermittently skips the computations of gradients, Jacobians and Hessians, Assumption II.1. The following assumptions hold for functions thus significantly reducing the overall computational cost. F , f , all Fi and fi in (1). 3 • We analyze the iteration complexity of S LDBO, demon1) For any fixed x, f (x, ·) is σ-strongly convex, with σ > 0 strating that it achieves O(1/K) convergence rate, where being a constant.
3
2) The function Fi is differentiable and ∇Fi is Lipschitz continuous with Lipschitz constant LF,1 . 3) For all x, there exists a constant LF,0 such that ∥∇2 F (x, y ∗ (x))∥ ≤ LF,0 . 4) The function fi is twice differentiable, and its gradient ∇fi is Lipschitz continuous with Lipschitz constant Lf,1 . Moreover, ∇212 fi (x, y) and ∇222 fi (x, y) are also Lipschitz continuous with Lipschitz constant Lf,2 .
With the initial values (yi0 , zi0 , u0i , s0i ) and gi0 = ∇hi (s0i ), i = 1, . . . , n, SSGT iterates for k = 0, 1, 2, . . . as xki = (1 − α − τ )yik + αzik + τ uki , 1 Xn zik+1 = wij zjk + βxkj j=1 1+β h i − η gjk + ζ k ∇hj (xkj ) − ∇hj (skj ) , yik+1 = xki + γ zik+1 − zik ,
Assumption II.2 (Network topology). Suppose the communication network is represented by a nonnegative weight matrix sk+1 = ξ k xki + (1 − ξ k )ski , i n×n Xn W = (wij ) ∈ R , where wij = 0 if i ̸= j and nodes uk+1 = wij ξ k xkj + (1 − ξ k )ukj , i i and j are not connected. Moreover, we assume that W j=1 Xn is symmetric and doubly stochastic, i.e. W = W T and gik+1 = wij gjk + ξ k ∇hi (xki ) − ∇hi (ski ) , n j=1 W 1n = 1n , where 1n is the all-one vector in R . Furthermore, the eigenvalues of W satisfy 1 = λ1 > λ2 ≥ · · · ≥ λn and where α, β, γ, η and τ are positive constants. In other gradientρ := max{|λ2 |, |λn |} < 1. tracking based algorithms, when ∇hi (xk+1 ) − ∇hi (xki ) is i large, a small stepsize is taken to control the consensus The following results are instrumental in our convergence error, ultimately resulting in suboptimal convergence rates. analysis. Lemma II.3 is a well-known result in decentralized The introduction of the snapshot point sk is designed to i optimization, as noted in [32]. Lemma II.4, adopted from overcome this limitation and mitigate its impact on converLemma 3.2 in [33], elucidates the relationship between the gence rates. Meanwhile, the update of xk is expressed as a i consensus error before and after the projection. linear combination of three other variables yik , zik , and uki , k k Lemma II.3. Consider the mixing matrix W = (wij ) ∈ Rn×n ensuring that the distance between xi and si is not too large, k k d and ∇hi (x ) − ∇hi (si ) is not too large. Most importantly, defined Pn in Assumption II.2, for any x1 , . . . , xn ∈ R , let x̄ = the SSGT ialgorithm skips 1 the gradient computation when i=1 xi , we have n k k ξ = ζ = 0, which greatly reduces the computational burden. n n n P P P 2 2 The SLDBO algorithm [28] for solving (1) updates in the 1) wij xj ≤ ∥xj ∥ , and i=1 j=1 j=1 kth iteration as follows: n n n P P P 2 2 Xn 2 ∥xi − x̄∥ . 2) wij (xj − x̄) ≤ ρ k+1 k t = wij tky,j + dk+1 (3a) y,i y,i − dy,i , i=1 i=1 j=1 j=1 Xn yik+1 = wij (yjk − βtky,j ), (3b) Lemma II.4. For any x1 , . . . , xn ∈ Rd and r ≥ 0, we have j=1 Xn k 2 2 tk+1 wij tkv,j + dk+1 (3c) v,i = v,i − dv,i , n n n n j=1 X X X X 1 1 hXn i xi − Pr [xj ] ≤ xj . Pr [xi ] − vik+1 = Prv wij (vjk + ηtkv,j ) , (3d) n j=1 n j=1 j=1 i=1 i=1 Xn k tk+1 wij tkx,j + dk+1 (3e) x,i = x,i − dx,i , j=1 Xn xk+1 = wij (xkj − αtkx,j ), (3f) III. O UR S3 LDBO A LGORITHM i j=1
where rv := LF,0 /σ, and dky,i , dkv,i and dkx,i are defined in (4)-(6), respectively. In each iteration, the SLDBO algorithm needs to evaluate one gradient, one Jacobian, and one Hessian of the lower-level function, and two gradients of the upper-level function. This brings heavy computational burden for large-scale problems. To alleviate the burden caused by computing gradients, Jacobians and Hessians in each A. Algorithm development iteration, we propose the S3 LDBO algorithm, which skips intermittently using the SSGT idea. The The SSGT algorithm [31] is designed for solving the these computations 3 details of our S LDBO algorithm are described in Algorithm following single-level decentralized problem: 1. Inspired by SSGT, we also introduce a stochastic variable ξ k in the kth iteration. It should be noted that whenever the 1 Xn minx h(x) = hi (x), random variable ξ k = 0, the algorithm does not compute any i=1 n gradients, Jacobians, and Hessians. This leads to substantial where x is the global decision variable and each hi is a smooth savings in computational time when dealing with large-scale and strongly convex function. Let {(ξ k , ζ k ) : k = 0, 1, 2, . . .} problems. In particular, as shown in [28], the SLDBO algorithm be a sequence of two-point random variables with ξ k ∼ computes three gradients, one Jacobian, and one Hessian in Bernoulli(p) and ζ k ∼ Bernoulli(l)/l, where p, l ∈ (0, 1). each iteration. Assuming that the amount of CPU time required In this section, we propose the Snapshot-SLDBO algorithm (S3 LDBO), which improves the SLDBO algorithm [28] with the idea of SSGT [31]. We start with discussing related algorithms and explaining the derivation of S3 LDBO.
4
for these computations is T in each iteration, this totals T K for K iterations. In contrast, S3 LDBO only needs an expected computational cost of pT K for the same number of iterations, where p ∈ (0, 1). This significantly reduces computational time.
B. Convergence results Next, we present convergence results of S3 LDBO. First, we recall the definition of a stationary point as presented in [34].
Definition III.1. For any ε > 0, a random vector (x, y), with x = [x1 ; x2 ; . . . ; xn ]⊤ and y = [y1 ; y2 ; . . . ; yn ]⊤ , is called a stochastic ε-stationary point in expectation of (1) if Algorithm 1 A Snapshot Single-Loop Algorithm for DBO n n 3 h i (S LDBO) 1X 1X E ∥∇Φ(x̄)∥2 + ∥xi − x̄∥2 + ∥yi − ȳ∥2 ≤ ε, Input: Let K be the maximum iteration number and p ∈ (0, 1). n i=1 n i=1 0 Initialize t0x,i = t0y,i = t0v,i = d0x̃,i = dỹ,i = d0ṽ,i = 0 for P P n n 1 1 all i. Given {(x0i , yi0 , vi0 ) : i = 1, 2, . . . , n}, satisfying where x̄ := n i=1 xi and ȳ := n i=1 yi . ∥vi0 ∥ ≤ rv := LF,0 /σ for all i. Let α, β, η > 0, which Our primary convergence rate results for Algorithm 1 are satisfy the upper bound conditions in (55). summarized in Theorem III.2 and Theorem III.3, and their 1: for k = 0, 1, . . . , K − 1 do proofs are postponed to the Appendix A. 2: Sample ξ k ∼ Bernoulli(p) Theorem III.2 (Convergence expectation). 3: for i = 1, . . . , n do Pn in Pn Fork any 1 1 k k k k k ≥ 0, define x̄ = , ȳ = x 4: if ξ = 1 then i=1 i i=1 yi and n n Pn 1 k k v v̄ = . For any integer K ≥ 1, the following 5: # Computation. i=1 i n convergence rate results hold for Algorithm 1. dky,i = ∇2 fi (xki , yik ), (4) 1) Consensus Error. We have k k k 2 k k k dv,i = ∇2 Fi (xi , yi ) − ∇22 fi (xi , yi )vi , (5) i h 1 XK−1 Xn 1 k k 2 k k k 2 k k k ∥x − x̄ ∥ = O E , i dx,i = ∇1 Fi (xi , yi ) − ∇12 fi (xi , yi )vi , (6) k=0 i=1 nK K h 1 XK−1 Xn i 1 E , ∥yik − ȳ k ∥2 = O 6: # Communication. k=0 i=1 nK K Xn h 1 XK−1 Xn i 1 k 1 ) , yik+1 = wij yjk − β tky,j + (dky,j − dỹ,j E ∥vik − v̄ k ∥2 = O . j=1 p k=0 i=1 nK K h i 1 k (dv,j − dkṽ,j ) p Xn 1 k ) , xk+1 = wij xkj − α tkx,j + (dkx,j − dx̃,j i j=1 p Xn k+1 k k k ty,i = wij (ty,j + dy,j − dỹ,j ), j=1 Xn k+1 tv,i = wij (tkv,j + dkv,j − dkṽ,j ), j=1 Xn k tk+1 wij (tkx,j + dkx,j − dx̃,j ), x,i = vik+1 = Prv
Xn
j=1
wij vjk + η tkv,j +
,
j=1
7: 8: 9:
k+1 k k dỹ,i = dky,i , dk+1 dk+1 ṽ,i = dv,i , x̃,i = dx,i . else # No computation of gradient, Jacobian and Hessian matrices. Xn yik+1 = wij (yjk − βtky,j ), j=1 hXn i vik+1 = Prv wij (vjk + ηtkv,j ) , j=1 Xn k k xk+1 = w ij (xj − αtx,j ), i j=1 Xn Xn tk+1 wij tky,j , tk+1 = wij tkv,j , y,i = v,i j=1 j=1 Xn tk+1 wij tkx,j , x,i = j=1
k+1 k k k dỹ,i = dỹ,i , dk+1 dk+1 ṽ,i = dṽ,i , x̃,i = dx̃,i . end if end for 13: end for K K Output: {(xK i , yi , vi ) : i = 1, 2, . . . , n}.
10: 11: 12:
2) Stationarity. There holds h 1 XK−1 i 1 E . ∥∇Φ(x̄k )∥2 = O k=0 K K
Theorem III.3 (Convergence in probability). Let {(xki , yik ) : i = 1, . . . , n}k≥0 by Algorithm 1. Pnbe the sequence generated Pn Define x̄k = n1 i=1 xki and ȳ k = n1 i=1 yik for k ≥ 0, and set n n 1X k 1X k Rk := ∥∇Φ(x̄k )∥2 + ∥xi − x̄k ∥2 + ∥y − ȳ k ∥2 . n i=1 n i=1 i Then, for any ε > 0, there holds lim Prob{Rk ≥ ε} = 0.
k→+∞
IV. N UMERICAL EXPERIMENTS In this section, we evaluate the proposed S3 LDBO algorithm on three representative decentralized bilevel learning tasks, including hyperparameter optimization, data hyper-cleaning, and decentralized meta-learning. The first two tasks are conducted on synthetic data, MNIST, and corrupted FashionMNIST, while the meta-learning experiment is conducted on miniImageNet. These tasks cover both classical bilevel learning problems and neural-network-based multi-agent learning scenarios, and are used to assess the computational efficiency and learning performance of the proposed snapshot mechanism. For hyperparameter optimization, we compare S3 LDBO with SLDBO [28], MA-DSBO [24], and SLAM [27]. SLDBO is the most directly related single-loop DBO baseline, MADSBO is a representative double-loop method, and SLAM
5
is a stochastic linearized augmented Lagrangian method for DBO. For data hyper-cleaning, we mainly compare S3 LDBO with SLDBO in order to isolate the effect of the snapshot mechanism against its closest single-loop counterpart. For decentralized meta-learning, we further include MAML [35] and ANIL [36] as representative meta-learning baselines. Other DBO algorithms are not included because they are designed for different stochastic settings, relying on different assumptions, or focusing on communication complexity rather than the local derivative-evaluation cost considered here. A major goal of the experiments is to isolate the computational savings achieved by the snapshot mechanism relative to the most direct single3 loop counterpart, while also examining whether such savings Fig. 1. Comparison of S LDBO, SLDBO, SLAM and MA-DSBO on synthetic data with respect to CPU time (d = 60). translate into improved time efficiency in neural-network-based meta-learning. Throughout all experiments, we set the number of nodes to n = 8 and adopt a ring topology to model the decentralized we set3 β to 1.2 and the maximum number of iterations is set communication network. The corresponding weight matrix to 10 , which are the same as in [28]. MA-DSBO utilizes W = (wij ) ∈ Rn×n is defined as follows: for i, j = 1, . . . , n, two key parameters, namely T and N . Here, T stands for wij = w if i = j; wij = (1 − w)/2 if i = j ± 1 or (i, j) ∈ the number of iterations carried out in the inner loop, while {(1, n), (n, 1)}; and wij = 0 otherwise. We set w = 0.4, under N represents the number of Hessian-inverse-gradient product which each node is connected to two neighboring nodes and iterations. MA-DSBO requires sufficient inner-loop iterations the associated spectral constant is ρ ≈ 0.724. Unless otherwise to estimate the LL solution and the hypergradient accurately. specified, all results are reported with respect to CPU time SLAM has one key parameter b, which is associated with or the number of expensive local derivative evaluations, so as matrix-vector products used for estimating the inverse of the to directly reflect the computational savings brought by the Hessian. In our experiments, we set T = 5, N = 5 and b = 5. To visualize the performance of the three algorithms being snapshot mechanism. All the experiments were performed within Python 3.8 running on a laptop with AMD Ryzen 5 compared, we present the curves of train loss, test loss, 3550H CPU at 2.1GHz with 16GB memory. We employed classification accuracy, and hypergradient norm against CPU time (in seconds) in Fig. 1 and Fig. 2, corresponding to mpi4py [37] for parallel computing. d = 60 and d = 300 respectively. As the dimension of the data increases, the computational demands for calculating the A. Hyperparameter optimization gradients, Jacobian, and Hessian matrices rise significantly. 1) Synthetic data: We first carry out numerical experiments The S3 LDBO algorithm attains higher numerical efficiency due on the logistic regression problem with ℓ2 regularization. Let to its ability to skip certain computationally intensive steps, ψ(t) = log(1 + e−t ) for t ∈ R and d be the dimension of the thereby enhancing the overall performance. In this experiment, data. Following [24] and [28], for each node i, we have we tested two values of p, namely p = 0.3 and p = 0.75. These X values were chosen to represent a low-frequency (p = 0.3) Fi (λ, ω) = ψ ye x⊤ ω , e versus a high-frequency (p = 0.75) update regime. This allows (xe ,ye )∈Di′ X us to empirically study the trade-off between per-iteration cost 1 Xd fi (λ, ω) = ψ ye x⊤ eλj ωj2 , e ω + and convergence speed discussed. It can be seen that p = 0.3 j=1 2 (xe ,ye )∈Di yields a better performance compared to p = 0.75. Furthermore, where Di and Di′ denote the training and testing datasets by comparing Fig. 1 and Fig. 2, it can be seen that the advantage on node i, respectively. We aim to determine the optimal of setting p = 0.3 becomes clearer for problems with larger hyperparameter λ such that ω ∗ (λ) minimizes the logistic loss dimensions compared to when p = 0.75. Fig. 3 and Fig. 4 display the comparison results between evaluated on the testing dataset. We utilize synthetic heterogeneous data generated in the same two single-loop algorithms, S3 LDBO and SLDBO, with respect manner as in [24] and [28]. Specifically, the data distribution to train loss, test loss, accuracy, and hypergradient magnitude of xe on node i follows a normal distribution with mean 0 versus the number of lower-level function’s gradient evaluations, and variance i2 · r2 , where r is the heterogeneity rate. In our where Fig. 3 corresponds to d = 60 and Fig. 4 corresponds experiments, we set r to 1. For the corresponding response to d = 300. It is noteworthy that within each iteration of the variable, we let ye = x⊤ SLDBO algorithm, the iteration requires one computation of e w +0.1z, where z is sampled from the standard normal distribution. The training and testing datasets the lower-level function’s gradient, two computations of the used in all algorithms each consist of 20,000 samples. In our upper-level function’s gradient, one computation of the lowerexperiments, we compare S3 LDBO with SLDBO [28], MA- level function’s Jacobian matrix, and one computation of the DSBO [24] and SLAM [27]. In SLDBO and S3 LDBO, the lower-level function’s Hessian matrix. In Fig. 3 and Fig. 4, the parameter rv is set to 20, which can be chosen via grid search, horizontal axis represents the number of lower-level function and the values of both α and η are assigned as 0.5. Furthermore, gradient computations in one node, based on which we present
6
Fig. 5. Performance of S3 LDBO with different networks. Fig. 2. Comparison of S3 LDBO, SLDBO, SLAM and MA-DSBO on synthetic data with respect to CPU time (d = 300).
Fig. 3. Comparison between S3 LDBO and SLDBO on synthetic data with respect to the number of gradient computations (d = 60). Fig. 6. Four distinct network structures.
Fig. 4. Comparison between S3 LDBO and SLDBO on synthetic data with respect to the number of gradient computations (d = 300).
Fig. 7. Comparison of train loss, test loss, and classification accuracy for S3 LDBO, SLDBO, SLAM and MA-DSBO on the MNIST dataset with respect to CPU time.
comparative curve results. It can be seen from both figures that S3 LDBO with p = 0.3 performs the best, followed by MNIST dataset [38]. In particular, the objective and constraint S3 LDBO with p = 0.75 and SLDBO. functions in (1) are given by 3 Fig. 5 showcases the performance of S LDBO across four X graphs, which is showed in Fig. 6. It can be observed that F (λ, ω) = 1 L(x⊤ i e ω, ye ), ′ 3 |Di | the performance of S LDBO improves as the connectivity of ′ (x ,y )∈D e e i the graph increases. Specifically, S3 LDBO performs best when c d X 1 1 X X λj 2 using the complete graph, followed by the random, the grid e ωmj , fi (λ, ω) = L(x⊤ ω, y ) + e e and the line graphs. This indicates that a network with better |Di | cd m=1 j=1 (xe ,ye )∈Di connectivity can generally accelerate the convergence process. 2) Real-world data: Similar to the case of synthetic data, we where ω ∈ Rc×d is the model parameter, L represents the cross define Di and Di′ as the training and testing datasets for node entropy loss, and |S| denotes the cardinality of a set S. In this i, respectively. Next, we apply S3 LDBO, SLDBO and MA- experiment, c represents the number of classes and d represents DSBO to solve hyperparameter optimization problem using the the number of features. The values of c and d are set to 10 and
7
784 respectively. The training and testing datasets each consist of 60,000 samples, with balanced representation across all classes. For both S3 LDBO and SLDBO, the hyperparameters were set as follows: rv = 100, α = η = 6, and β = 12. For MA-DSBO, we set T = 10 and N = 20. For SLAM, we set b = 5. In the experiment, we only tested p = 0.3 for S3 LDBO. The comparison results of test loss, train loss, and classification accuracy for the three algorithms with respect to CPU time are presented in Fig. 7. These results clearly demonstrate that all the compared algorithms can efficiently solve this problem. Moreover, our proposed algorithm S3 LDBO performs the best in terms of improved convergence rate and classification accuracy, followed by SLDBO, SLAM and MADSBO.
Fig. 8. Data class distributions on each client. The left figure is the i.i.d. case and the right figure is the Dirichlet case with α̃ = 0.1 and pcls = (1, . . . , 1).
B. Data hyper-cleaning In this subsection, we compare the proposed S3 LDBO with SLDBO on a data hyper-cleaning problem [19] for the FashionMNIST dataset [39]. The dataset consists of 60,000 images for training and 10,000 images for testing. Within the training phase, the 60,000 training images are partitioned into two distinct subsets: a training set of 50,000 images (denoted as ST ) and a validation set of 10,000 images (denoted as SV ). In the data hyper-cleaning problem, we aim to train a classifier in a corrupted setting. Here, each training data’s label is replaced by a random class number with probability prob (i.e. the corruption rate). We again use a decentralized ring network with n = 8 clients. This problem can be modeled as the bilevel optimization problem (1) with X 1 Fi (λ, w) = i L(w⊤ xe , ye ), |SV | i (xe ,ye )∈SV
1 fi (λ, w) = i |ST |
X
Fig. 9. Comparison of upper-level train loss, test accuracy, and F1-score for S3 LDBO and SLDBO on the Fashion-MNIST dataset with i.i.d. and Dirichlet data distributions.
Fig. 10. Comparison of S3 LDBO and SLDBO on the Fashion-MNIST dataset regarding CPU time. Two corruption rates are tested: prob = 0.4 and prob = 0.7.
σ(λe )L(w⊤ xe , ye ) + C̃∥w∥2 .
the two compared algorithms depends on the assumption of data heterogeneity. Here, L represents the cross-entropy loss, C̃ is a regularization To clearly illustrate the performance of the two compared parameter, σ(·) is the sigmoid function, STi and SVi respectively algorithms, Fig. 10 shows the results of the upper-level train denote the training and validation sets of the ith client. loss, classification accuracy and F1-score with corruption Following the description in [40], we assume that on each rates prob = 0.4 and prob = 0.7 as the CPU time client, training examples are independently drawn with class progresses. Here, classification accuracy refers to the accuracy labels following a categorical distribution over M classes of classifying data whose labels have not been corrupted, and parameterized by a vector q = (q1 , . . . , qM ) where qi ≥ 0 F1-score measures the quality of the data cleaner [41]. The for all i and ∥q∥1 = 1. To synthesize a population of non- detailed experimental results of the final test accuracy, F1-score, identical clients, we draw q from a Dirichlet distribution and the consumed CPU time (in seconds) are summarized q ∼ Dir(α̃pcls ). Here, pcls represents a prior class distribution in Table I, with an additional corruption rate prob = 0.1. over M classes, and α̃ > 0 is a concentration parameter that Compared to SLDBO, our algorithm S3 LDBO achieves a 35% controls the identicalness among clients. In the experiment, we reduction in CPU time, enhances accuracy by approximately set C̃ = 0.005. 4%, and increases the F1-score by 2 to 4 points. From these In Fig. 8, we display the data class distributions for both results, it is evident that S3 LDBO outperforms SLDBO in the i.i.d. case and the Dirichlet case with α̃ = 0.1, pcls = terms of both speed and accuracy. (1, . . . , 1) and M = 10. For both cases, our rule for corrupting the 10 labels is to contaminate them using any one of the other 9 types. Fig. 9 shows the results of upper-level train loss, test C. Decentralized Meta-Learning accuracy and F1-score of the two algorithms for the two types To further evaluate the applicability of the proposed alof data distributions with corruption rate prob = 0.4, from gorithm to networked AI systems, we conduct experiments which it is clear that data heterogeneity does not influence the on a decentralized meta-learning task [35], [36] using the performance of the two algorithms. This is because neither of miniImageNet dataset [42]. Meta-learning aims to learn a i (xe ,ye )∈ST
8
TABLE I C OMPARISON OF SOLUTION QUALITY AND CPU TIME BETWEEN S3 LDBO AND SLDBO UNDER DIFFERENT CORRUPTION RATES . Corruption Rate prob = 0.1
Algorithm SLDBO S3 LDBO
Test Acc. 0.7721 0.8125
F1-score 92.88 94.39
CPU Time (s) 143.29 93.98
prob = 0.4
SLDBO S3 LDBO
0.7671 0.8027
89.97 92.04
146.19 92.29
prob = 0.7
SLDBO S3 LDBO
0.6752 0.7127
75.38 78.93
144.40 89.60
shared representation or initialization that can rapidly adapt to new tasks using only a small number of task-specific samples. This setting naturally leads to a bilevel structure, where the lower-level problem performs task-specific adaptation on the support set and the upper-level problem evaluates the adapted model on the query set. We consider a collection of tasks {Tr : r = 1, . . . , R}. For each task Tr , let x denote the shared model parameter and yr denote the task-specific parameter. The task loss is defined as
Fig. 11. The accuracy on training set (left) and testing set (right) of different algorithms for the meta-learning problem with respect to the number of iterations.
ℓr (x, yr ) = Eξ∈Dr L(x, yr ; ξ), Fig. 12. The accuracy on training set (left) and testing set (right) of different
where L denotes the supervised learning loss. In the decentral- algorithms for the meta-learning problem with respect to CPU time. ized setting, the data associated with each task are distributed over n agents. For node i and task Tr , we denote the local tr dataset by Dr,i , which is further split into a support set Dr,i The same task splits, batch size, and evaluation protocol are val and a query set Dr,i . used for all compared methods. The decentralized meta-learning problem [43] can be formuWe compare S3 LDBO with SLDBO, MAML [35] and lated as the DBO problem (1). For each node i, the upper-level ANIL [36]. MAML [35] is a representative gradient-based and lower-level objectives are given by meta-learning baseline, while ANIL [36] restricts task-specific adaptation mainly to the final layers. For a fair comparison, R X 1 X 1 the stepsizes of all compared methods are tuned from the same Fi (x, y) = L(x, yr ; ξ) , val | R r=1 |Dr,i candidate set on the validation tasks. For S3 LDBO, we set the val ξ∈Dr,i upper-level stepsize to α = 0.002, the lower-level stepsize to β = 0.004, and the auxiliary-variable stepsize to η = 0.001. and For SLDBO, we use the same stepsizes. For MAML and ANIL, R X 1 X 1 the meta stepsize and the inner-loop adaptation stepsize are set fi (x, y) = L(x, yr ; ξ) + R(yr ) , tr | R r=1 |Dr,i to αmeta = 0.002 and αin = 0.002, respectively. These values tr ξ∈Dr,i are selected to provide stable training behavior for all methods where y = (y1 , . . . , yR ) collects the task-specific parameters under the same miniImageNet task split. For the snapshot and R(yr ) is a regularization term. The lower-level objective probability in S3 LDBO, we use p = 0.6 in this experiment. This adapts the task-specific parameter using the support set, while value is chosen as a moderate snapshot frequency that balances the upper-level objective measures the query-set performance af- computational saving and update accuracy: a smaller p further ter adaptation. Compared with the previous logistic-regression- reduces derivative-evaluation cost but may introduce larger based experiments, this experiment is more representative of snapshot errors, whereas a larger p makes the method closer to networked AI applications because it involves neural-network SLDBO and weakens the computational advantage. Since the influence of p has already been investigated in the synthetic models, task-level adaptation, and distributed task data. In our implementation, we use a 5-way 10-shot few-shot and data hyper-cleaning experiments, the decentralized metaclassification setting. The dataset is miniImageNet [42], which learning experiment focuses on validating whether the proposed is generated from ImageNet [44] and consists of 100 classes snapshot mechanism remains effective in a more computationwith each class containing 600 images of size 84 × 84. Each ally demanding neural-network-based setting. Therefore, we task contains 5 classes, with 10 support samples and 10 query report the representative result with p = 0.6. samples per class. The decentralized network consists of n = 8 Fig. 11 and Fig. 12 compare different algorithms on the nodes. We use 1000 training tasks, 200 validation tasks, and meta-learning problem in terms of training and testing accuracy, 600 testing tasks. The batch size is set to 32, and all algorithms where Fig. 11 reports the results with respect to the number are trained for 1500 iterations. The models are evaluated every of iterations and Fig. 12 reports the results with respect to 25 iterations, and each evaluation is averaged over 200 episodes. CPU time. Under the iteration-based comparison, S3 LDBO
9
achieves the highest training accuracy and obtains testing accuracy comparable to MAML, while outperforming SLDBO and ANIL. This indicates that the proposed method maintains strong task adaptation performance during the iterative optimization process. Under the CPU-time-based comparison, S3 LDBO achieves the best performance on both training and testing tasks within the same time budget. These results show that the snapshot mechanism not only preserves competitive learning performance in terms of iterations, but also improves practical time efficiency by reducing expensive derivative evaluations. Overall, the meta-learning experiment demonstrates that S3 LDBO is effective for decentralized task adaptation and is suitable for networked AI applications with limited computational resources. V. C ONCLUDING REMARKS In this paper, we propose a novel single-loop algorithm, S3 LDBO, which integrates the SLDBO framework with the snapshot gradient tracking technique to efficiently solve decentralized bilevel optimization problems. Unlike other singleloop algorithms that require the computation of full gradients, Jacobian, and Hessian matrices in every iteration – a timeconsuming task in practical settings, S3 LDBO allows agents to skip these calculations in some iterations, which significantly reduces computational costs in large-scale distributed optimization. We establish the ergodic iteration complexity and the high probability nonergodic iteration complexity of S3 LDBO. Numerical experiments on hyperparameter optimization, data hyper-cleaning, and decentralized meta-learning confirm the efficacy of the proposed algorithm. These results suggest that snapshot-based DBO algorithm is a promising tool for scalable and adaptive learning in networked AI systems. A key avenue for future research is the extension of S3 LDBO to the stochastic setting. Developing an algorithm that can effectively handle variance from both stochastic data sampling and the snapshot mechanism would require new analytical tools and could significantly broaden the practical applicability of this work to large-scale machine learning problems. R EFERENCES [1] W. Xu, Z. Yang, D. W. K. Ng, M. Levorato, Y. C. Eldar, and M. Debbah, “Edge learning for b5g networks with distributed signal processing: Semantic communication, edge computing, and wireless sensing,” IEEE Journal of Selected Topics in Signal Processing, vol. 17, no. 1, pp. 9–39, 2023. [2] H. Ye, L. Liang, and G. Y. Li, “Decentralized federated learning with unreliable communications,” IEEE Journal of Selected Topics in Signal Processing, vol. 16, no. 3, pp. 487–500, 2022. [3] J. Chen, C. Richard, and A. H. Sayed, “Multitask diffusion adaptation over networks with common latent representations,” IEEE Journal of Selected Topics in Signal Processing, vol. 11, no. 3, pp. 563–579, 2017. [4] L. Franceschi, P. Frasconi, S. Salzo, R. Grazzi, and M. Pontil, “Bilevel programming for hyperparameter optimization and meta-learning,” in Proceedings of the 35th International Conference on Machine Learning, vol. 80. PMLR, 2018, pp. 1568–1577. [5] A. Rajeswaran, C. Finn, S. M. Kakade, and S. Levine, “Meta-learning with implicit gradients,” in Advances in Neural Information Processing Systems, vol. 32. Curran Associates, Inc., 2019. [6] K. Ji, J. D. Lee, Y. Liang, and H. V. Poor, “Convergence of meta-learning with task-specific adaptation over partial parameters,” in Advances in Neural Information Processing Systems, vol. 33. Curran Associates, Inc., 2020, pp. 11 490–11 500.
[7] F. Pedregosa, “Hyperparameter optimization with approximate gradient,” in Proceedings of The 33rd International Conference on Machine Learning, vol. 48. PMLR, 2016, pp. 737–746. [8] J. J. Ye, X. Yuan, S. Zeng, and J. Zhang, “Difference of convex algorithms for bilevel programs with applications in hyperparameter selection,” Mathematical Programming, vol. 198, no. 1-2, pp. 1583–1616, 2023. [9] M. Hong, H.-T. Wai, Z. Wang, and Z. Yang, “A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor-critic,” SIAM Journal on Optimization, vol. 33, no. 1, pp. 147–180, 2023. [10] N. Bishop, L. Tran-Thanh, and E. Gerding, “Optimal learning from verified training data,” in Advances in Neural Information Processing Systems, vol. 33. Curran Associates, Inc., 2020, pp. 9520–9529. [11] Y. Zhang, G. Zhang, P. Khanduri, M. Hong, S. Chang, and S. Liu, “Revisiting and advancing fast adversarial training through the lens of bilevel optimization,” in Proceedings of the 39th International Conference on Machine Learning, vol. 162. PMLR, 2022, pp. 26 693–26 712. [12] X. Lian, C. Zhang, H. Zhang, C.-J. Hsieh, W. Zhang, and J. Liu, “Can decentralized algorithms outperform centralized algorithms? A case study for decentralized parallel stochastic gradient descent,” in Advances in Neural Information Processing Systems, vol. 30. Curran Associates, Inc., 2017. [13] S. Ghadimi and M. Wang, “Approximation methods for bilevel programming,” arXiv preprint arXiv:1802.02246, 2018. [14] R. Grazzi, L. Franceschi, M. Pontil, and S. Salzo, “On the iteration complexity of hypergradient computation,” in Proceedings of the 37th International Conference on Machine Learning, vol. 119. PMLR, 2020, pp. 3748–3758. [15] K. Ji, J. Yang, and Y. Liang, “Bilevel optimization: Convergence analysis and enhanced design,” in Proceedings of the 38th International Conference on Machine Learning, vol. 139. PMLR, 2021, pp. 4882– 4892. [16] K. Ji, M. Liu, Y. Liang, and L. Ying, “Will bilevel optimizers benefit from loops,” in Advances in Neural Information Processing Systems, vol. 35. Curran Associates, Inc., 2022, pp. 3011–3023. [17] T. Chen, Y. Sun, and W. Yin, “Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems,” in Advances in Neural Information Processing Systems, vol. 34. Curran Associates, Inc., 2021, pp. 25 294–25 307. [18] M. Dagréou, P. Ablin, S. Vaiter, and T. Moreau, “A framework for bilevel optimization that enables stochastic and global variance reduction algorithms,” in Advances in Neural Information Processing Systems, vol. 35. Curran Associates, Inc., 2022, pp. 26 698–26 710. [19] A. Shaban, C.-A. Cheng, N. Hatch, and B. Boots, “Truncated backpropagation for bilevel optimization,” in Proceedings of the TwentySecond International Conference on Artificial Intelligence and Statistics, ser. Proceedings of Machine Learning Research, vol. 89. PMLR, 2019, pp. 1723–1732. [20] R. Liu, P. Mu, X. Yuan, S. Zeng, and J. Zhang, “A general descent aggregation framework for gradient-based bi-level optimization,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 45, no. 1, pp. 38–57, 2023. [21] R. Liu, Y. Liu, W. Yao, S. Zeng, and J. Zhang, “Averaged method of multipliers for bi-level optimization without lower-level strong convexity,” in Proceedings of the 40th International Conference on Machine Learning, vol. 202. PMLR, 2023, pp. 21 839–21 866. [22] R. Liu, Y. Liu, S. Zeng, and J. Zhang, “Towards gradient-based bilevel optimization with non-convex followers and beyond,” in Advances in Neural Information Processing Systems, vol. 34. Curran Associates, Inc., 2021, pp. 8662–8675. [23] X. Chen, M. Huang, and S. Ma, “Decentralized bilevel optimization,” Optimization Letters, 2024. [24] X. Chen, M. Huang, S. Ma, and K. Balasubramanian, “Decentralized stochastic bilevel optimization with improved per-iteration complexity,” in Proceedings of the 40th International Conference on Machine Learning, vol. 202. PMLR, 2023, pp. 4641–4671. [25] S. Yang, X. Zhang, and M. Wang, “Decentralized gossip-based stochastic bilevel optimization over communication networks,” in Advances in Neural Information Processing Systems, vol. 35. Curran Associates, Inc., 2022, pp. 238–252. [26] H. Gao, B. Gu, and M. T. Thai, “On the convergence of distributed stochastic bilevel optimization algorithms over a network,” in Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, ser. Proceedings of Machine Learning Research, vol. 206. PMLR, 2023, pp. 9238–9281. [27] S. Lu, S. Zeng, X. Cui, M. Squillante, L. Horesh, B. Kingsbury, J. Liu, and M. Hong, “A stochastic linearized augmented Lagrangian method for
10
decentralized bilevel optimization,” in Advances in Neural Information Processing Systems, vol. 35. Curran Associates, Inc., 2022, pp. 30 638– 30 650. [28] Y. Dong, S. Ma, J. Yang, and C. Yin, “A single-loop algorithm for decentralized bilevel optimization,” Mathematics of Operations Research, vol. 0, no. 0, 2025. [29] B. Kong, S. Zhu, S. Lu, X. Huang, and K. Yuan, “Decentralized bilevel optimization: A perspective from transient iteration complexity,” Journal of Machine Learning Research, vol. 26, no. 240, pp. 1–64, 2025. [30] Y. Zhang, M. T. Thai, J. Wu, and H. Gao, “On the communication complexity of decentralized bilevel optimization.” arXiv preprint arXiv:2311.11342, 2023. [31] Z. Song, L. Shi, S. Pu, and M. Yan, “Optimal gradient tracking for decentralized optimization,” Mathematical Programming, vol. 207, no. 1–2, p. 1–53, 2024. [32] S. Pu and A. Nedić, “Distributed stochastic gradient tracking methods,” Mathematical Programming, vol. 187, no. 1-2, pp. 409–457, 2021. [33] W. Choi and J. Kim, “On the convergence analysis of the decentralized projected gradient descent,” arXiv preprint arXiv:2303.08412, 2023. [34] Y. Xu, “Decentralized gradient descent maximization method for composite nonconvex strongly-concave minimax problems,” SIAM Journal on Optimization, vol. 34, no. 1, pp. 1006–1044, 2024. [35] C. Finn, P. Abbeel, and S. Levine, “Model-agnostic meta-learning for fast adaptation of deep networks,” in Proceedings of the 34th International Conference on Machine Learning, ser. Proceedings of Machine Learning Research, D. Precup and Y. W. Teh, Eds., vol. 70. PMLR, 06–11 Aug 2017, pp. 1126–1135. [36] A. Raghu, M. Raghu, S. Bengio, and O. Vinyals, “Rapid learning or feature reuse? towards understanding the effectiveness of MAML,” in 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. [37] L. Dalcin and Y.-L. L. Fang, “mpi4py: Status update after 12 years of development,” Computing in Science & Engineering, vol. 23, no. 4, pp. 47–54, 2021. [38] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner, “Gradient-based learning applied to document recognition,” Proceedings of the IEEE, vol. 86, no. 11, pp. 2278–2324, 1998. [39] H. Xiao, K. Rasul, and R. Vollgraf, “Fashion-MNIST: A novel image dataset for benchmarking machine learning algorithms.” arXiv preprint arXiv:1708.07747, 2017. [40] T. H. Hsu, H. Qi, and M. Brown, “Measuring the effects of nonidentical data distribution for federated visual classification,” arXiv preprint arXiv:1909.06335, 2019. [41] H. Shen and T. Chen, “On penalty-based bilevel gradient descent method,” in Proceedings of the 40th International Conference on Machine Learning, ser. Proceedings of Machine Learning Research, vol. 202. PMLR, 2023, pp. 30 992–31 015. [42] O. Vinyals, C. Blundell, T. Lillicrap, K. Kavukcuoglu, and D. Wierstra, “Matching networks for one shot learning,” in Advances in Neural Information Processing Systems, D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, Eds., vol. 29. Curran Associates, Inc., 2016. [43] M. Kayaalp, S. Vlaski, and A. H. Sayed, “Dif-maml: Decentralized multi-agent meta-learning,” IEEE Open Journal of Signal Processing, vol. 3, pp. 71–93, 2022. [44] O. Russakovsky, J. Deng, H. Su, J. Krause, S. Satheesh, S. Ma, Z. Huang, A. Karpathy, A. Khosla, M. Bernstein, A. C. Berg, and L. Fei-Fei, “ImageNet Large Scale Visual Recognition Challenge,” International Journal of Computer Vision (IJCV), vol. 115, no. 3, pp. 211–252, 2015. [45] A. Beck, First-order Methods in Optimization. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2017, vol. 25. [46] Y. Nesterov, Lectures on Convex Optimization, 2nd ed. Springer, Cham, 2018, vol. 137.
11
A PPENDIX A C OMPLETE PROOF OF THE CONVERGENCE RESULTS In this appendix, we provide the proof of our convergence results, i.e., Theorem III.2 and Theorem III.3. Assumptions II.1 and II.2 are used throughout the proof. Recall that rv := LF,0 /σ and ρ is defined in Assumption II.2. Moreover, we define the following constants for the analysis: Lv := (LF,1 + Lf,2 rv ) (1 + Lf,1 /σ) , L1 := LF,1 + Lf,2 rv , (7) L := L + 2LF,1 Lf,1 +Lf,2 L2F,0 + 2Lf,1 LF,0 Lf,2 +L2f,1 LF,1 + Lf,2 L2f,1 LF,0 , Φ F,1 σ σ2 σ3 where constants such as σ, LF,0 , LF,1 , Lf,1 , Lf,2 are defined in Assumptions II.1 and II.2. 1) Notation, constants, and roadmap: For convenience in the subsequent convergence proof, we rewrite the kth iteration of Algorithm 1 in a more concise form as follows, together with (4), (5) and (6): Xn k k k zy,i = tky,i + ξ k (dky,i − dỹ,i )/p, yik+1 = wij (yjk − βzy,j ), (8a) j=1 Xn k ỹik+1 = ξ k yik + (1 − ξ k )ỹik , tk+1 wij tky,j + ξ k (dky,j − dỹ,j ) , (8b) y,i = j=1 hXn i k k zv,i = tkv,i + ξ k (dkv,i − dkṽ,i )/p, vik+1 = Prv wij (vjk + ηzv,j ) , (8c) j=1 Xn ṽik+1 = ξ k vik + (1 − ξ k )ṽik , tk+1 wij tkv,j + ξ k (dkv,j − dkṽ,j ) , (8d) v,i = j=1 Xn k k zx,i = tkx,i + ξ k (dkx,i − dkx̃,i )/p, xk+1 = wij (xkj − αzx,j ), (8e) i j=1 Xn x̃k+1 = ξ k xki + (1 − ξ k )x̃ki , tk+1 wij tkx,j + ξ k (dkx,j − dkx̃,j ) , (8f) i x,i = j=1 k+1 k k dṽ,i = ξ dv,i + (1 − ξ k )dkṽ,i ,
k+1 k dỹ,i = ξ k dky,i + (1 − ξ k )dỹ,i , k+1 k k k k dx̃,i = ξ dx,i + (1 − ξ )dx̃,i .
(8g) (8h)
k+1 k+1 From (8), we know that dỹ,i , dṽ,i and dk+1 x̃,i have the following representations, which will be useful in the subsequent analysis: k+1 = ∇2 fi (x̃k+1 , ỹik+1 ), dỹ,i i
(9)
k+1 k+1 dk+1 , ỹi ) − ∇222 fi (x̃k+1 , ỹik+1 )ṽik+1 , i ṽ,i = ∇2 Fi (x̃i k+1 k+1 dk+1 , ỹi ) − ∇212 fi (x̃k+1 , ỹik+1 )ṽik+1 . i x̃,i = ∇1 Fi (x̃i
For the analysis, we further define Pn k x̄ := n1 i=1 xki , ¯k Pn 1 k dx := n Pi=1 dx,i , n 1 k d¯x̃ := n i=1 dkx̃,i , Pn t̄kx := n1 i=1 tkx,i , Pn k k z̄x := n1 i=1 zx,i ,
Pn Pn ȳ k := n1 i=1 yik , v̄ k := n1 i=1 vik , Pn Pn d¯ky := n1 i=1 dky,i , d¯kv := n1 i=1 dkv,i , P Pn n k d¯ỹk := n1 i=1 dỹ,i , d¯kṽ := n1 i=1 dkṽ,i , Pn Pn t̄ky := n1 i=1 tky,i , t̄kv := n1 i=1 tkv,i , Pn Pn k k z̄yk := n1 i=1 zy,i , z̄vk := n1 i=1 zv,i ,
(10) (11)
(12)
and two additional constants C1 := 3 max{(LF,1 + rv Lf,2 )2 , L2f,1 } and C2 := L2f,1 .
(13)
a) Roadmap of the proof.: Here we briefly describe the roadmap of the proof of Theorem III.2. First, we define the Lyapunov function n
Vk = F (x̄k , y ∗ (x̄k )) − F ∗ + a1 ∥ȳ k − y ∗ (x̄k )∥2 + a2 ∥v̄ k − v ∗ (x̄k )∥2 +
a3 X k ∥x − x̄k ∥2 n i=1 i
+
n n n n a4 X k a5 X k a6 α2 X k a7 β 2 X k ∥yi − ȳ k ∥2 + ∥vi − v̄ k ∥2 + ∥zx,i − z̄xk ∥2 + ∥z − z̄yk ∥2 n i=1 n i=1 n i=1 n i=1 y,i
+
n n n n a8 η 2 X k a9 X k a10 X k a11 X k ∥zv,i − z̄vk ∥2 + ∥xi − x̃ki ∥2 + ∥yi − ỹik ∥2 + ∥v − ṽik ∥2 , n i=1 n i=1 n i=1 n i=1 i
(14)
12
−1 where v ∗ (x) := ∇222 f (x, y ∗ (x)) ∇2 F (x, y ∗ (x)) and a1 , a2 , . . . , a11 are constants. We will show that, for another set of positive constants A1 , A2 , . . . , A12 , the following inequality holds i i h i h i h h i α h E Vk+1 − Vk ≤ − E ∥∇Φ(x̄k )∥2 − A1 E ∥d¯kx ∥2 − A2 E ∥ȳ k − y ∗ (x̄k )∥2 − A3 E ∥v̄ k − v ∗ (x̄k )∥2 2 n n n i A hX i A hX i A4 h X k 5 6 − E E E ∥xi − x̄k ∥2 − ∥yik − ȳ k ∥2 − ∥vik − v̄ k ∥2 n n n i=1 i=1 i=1 n n n i A hX i A hX i A7 h X k 8 9 k k − E E E ∥zx,i − z̄xk ∥2 − ∥zy,i − z̄yk ∥2 − ∥zv,i − z̄vk ∥2 n n n i=1 i=1 i=1 n n n i A hX i A hX i A10 h X k 11 12 − E E E ∥xi − x̃ki ∥2 − ∥yik − ỹik ∥2 − ∥vik − ṽik ∥2 . n n n i=1 i=1 i=1 Then, the proof can be obtained by telescoping the above inequality. 2) Some lemmas for consensus error of Algorithm 1: Recall that x̄k , ȳ k , v̄ k , d¯kx , d¯ky , d¯kv , d¯x̃k , d¯ỹk , d¯kṽ , t̄kx , t̄ky , t̄kv , z̄xk , z̄yk and k z̄v are defined in (12). Let Fk be the sigma field generated by {ξ j }0≤j≤k−1 and Ek [·] be the conditional expectation taken k over Fk . Then, for any k ≥ 0, the variables {xki , yik , vik , dkx,i , dky,i , dkv,i , x̃ki , ỹik , ṽik , dkx̃,i , dỹ,i , dkṽ,i , tkx,i , tky,i , tkv,i } are measurable with respect to Fk . We first prove some useful lemmas. Lemma A.1. For any 0 ≤ k ≤ K, there hold t̄kx = d¯kx̃ , h
Ek z̄xk
i
= d¯kx ,
t̄ky = d¯ỹk , i Ek z̄yk = d¯ky , h
t̄kv = d¯kṽ ; h i Ek z̄vk = d¯kv .
(15) (16)
Proof. First, by initialization, we have the relation (15) for k = 0. Suppose we have shown the relation (15) for 0, . . . , k − 1. Next, we prove the relation for k. = d¯k−1 = d¯kx̃ . If ξ k−1 = 1, then If ξ k−1 = 0, then x̃ki = x̃k−1 , ỹik = ỹik−1 and ṽik = ṽik−1 . By induction, we have t̄kx = t̄k−1 x i x̃ k−1 k k−1 k−1 k k x̃i = xi , ỹi = yi and ṽi = vi . Again, by induction, we have n
t̄kx = t̄k−1 + x
1 X k−1 k−1 (d − dx̃,i ) = d¯k−1 + d¯k−1 − d¯x̃k−1 = d¯k−1 = d¯kx̃ . x x x̃ n i=1 x,i
k k k k ¯k k k ¯k ¯k ¯k Following similar steps, h we ican show t̄y = dỹ and h t̄vi = dṽ . From the update of zx,i in (8e), h iwe have z̄x =ht̄x + i ξ (dx − dx̃ )/p. With t̄k = d¯k and Ek ξ k /p = 1, we obtain Ek z̄ k = d¯k . Similarly, we also have Ek z̄ k = d¯k and Ek z̄ k = d¯k . x
x
x̃
x
y
y
v
v
k Lemma A.2. The sequences {zx,i }, {dkx,i } and {dkx̃,i } generated by (8) satisfy
Ek
n hX
n i i hX k+1 k ∥zx,i − z̄xk+1 ∥2 ≤ ρEk ∥zx,i − z̄xk ∥2 +
i=1
i=1
n h i X 1 k+1 k+1 2 k k 2 ∥d − d ∥ + E ∥d − d ∥ . k x,i x̃,i x,i x̃,i (1 − ρ)2 ρp i=1
(17)
k+1 k+1 k+1 Proof. By using the update of zx,i in (8e) and defining △k+1 (dx,i − dk+1 x,i = ξ x̃,i ), we have n n 1 1 k+1 X 1 k+1 X 1 k+1 k k k zx,i = tk+1 + △ = w (t + △ ) + △ = wij zx,j + (1 − )△kx,j + △k+1 . ij x,j x,j x,i x,i x,i p p p p x,i j=1 j=1
Therefore, we have Ek = Ek
n hX
n n i hX i X 1 1−p k k+1 k k k k+1 2 △x,j ) + △k+1 − z̄ + z̄ − z̄ ∥ ∥zx,i − z̄xk+1 ∥2 = Ek ∥ wij (zx,j − x x x p p x,i i=1 i=1 j=1
n n n n hX i h X i X 1 1−pX k+1 k k 2 k k+1 2 ∥ wij zx,j − z̄xk + △k+1 − zx,i − z̄xk , z̄xk − z̄xk+1 . w △ ∥ + n∥z̄ − z̄ ∥ + E 2 ij x,j k x x x,i p p j=1 i=1 j=1 i=1
For the cross term, since the second factor is independent of i, we have * n + n X X k+1 k+1 k k k+1 k k k+1 2 zx,i − z̄x , z̄x − z̄x = 2 (zx,i − z̄x ), z̄x − z̄x i=1
i=1
= 2n z̄xk+1 − z̄xk , z̄xk − z̄xk+1 = −2n∥z̄xk+1 − z̄xk ∥2 .
13
Therefore, Ek
n hX
k+1 ∥zx,i − z̄xk+1 ∥2
i
i=1 n n n hX i X 1 1−pX k = Ek ∥ wij zx,j − z̄xk + △k+1 − wij △kx,j ∥2 − n∥z̄xk+1 − z̄xk ∥2 x,i p p j=1 i=1 j=1
≤ Ek
n n n hX i X 1−pX 1 k 2 k ∥ − w △ ∥ wij zx,j − z̄xk + △k+1 ij x,j p x,i p j=1 i=1 j=1
≤ ρEk
n hX
i k ∥zx,i − z̄xk ∥2 +
i=1
≤ ρEk
n hX i=1
k ∥zx,i − z̄xk ∥2
i
n n hX i 1 1−pX 1 k 2 Ek − w △ ∥ △k+1 ∥ ij x,j 1−ρ p x,i p j=1 i=1
n i h X 1 k+1 k+1 2 k k 2 + ∥d . − d ∥ + E ∥d − d ∥ k x,i x̃,i x,i x̃,i (1 − ρ)2 ρp i=1
where the first inequality follows from dropping the nonpositive term “−n∥z̄xk+1 − z̄xk ∥2 ”. The second inequality follows from ρ 2 ∥a∥2 + 1−ρ expanding the square, applying 2⟨a, b⟩ ≤ 1−ρ ρ ∥b∥ , and then using Lemma II.3. This introduces a prefactor 1/ρ, which combines with the ρ2 contraction in Lemma II.3 and yields the factor ρ. And the last inequality follows from n n hX i 1 1−pX Ek ∥ △k+1 − wij △kx,j ∥2 x,i p p j=1 i=1 ≤
n n n h i hX iX i (1 − p)2 h X 1 k+1 k+1 2 k+1 2 k 2 E E (ξ ) E ∥d − d ∥ (ξ ) ∥ wij (dkx,j − dkx̃,j )∥2 + k k k x,i x̃,i 2 (1 − ρ)p2 ρp i=1 i=1 j=1
=
n n n hX i (1 − p)2 X X 1 k+1 2 Ek ∥dk+1 − d ∥ ∥ wij (dkx,j − dkx̃,j )∥2 + x,i x̃,i (1 − ρ)p ρp i=1 i=1 j=1
n h i X 1 k+1 2 Ek ∥dk+1 ≤ + ∥dkx,i − dkx̃,i ∥2 , x,i − dx̃,i ∥ ρ(1 − ρ)p i=1
where the last inequality follows from multiplying the first term by 1/ρ, the second term by 1/ (1 − ρ)(1 − p)2 , and then applying Lemma II.3 (a). Remark A.3. The following inequalities can be derived by following similar steps as in Lemma A.2. Details are omitted to avoid redundancy. n n n hX i hX i h i X 1 k+1 k+1 k+1 2 k+1 2 k k 2 k k 2 Ek ∥zy,i − z̄y ∥ ≤ ρEk ∥zy,i − z̄y ∥ + ∥d − d ∥ + E ∥d − d ∥ , k y,i ỹ,i y,i ỹ,i (1 − ρ)2 ρp i=1 i=1 i=1 n n n h i hX i hX i X 1 k+1 k+1 2 k+1 k k 2 k+1 2 k k 2 ∥d − d ∥ + E ∥d − d ∥ . Ek ∥zv,i − z̄v ∥ ≤ ρEk ∥zv,i − z̄v ∥ + k v,i ṽ,i v,i ṽ,i (1 − ρ)2 ρp i=1 i=1 i=1 Then, we will bound the terms related to the consensus error in (14). Lemma A.4. The sequence {vik } generated by (8) satisfies n n n i hX i X ρ2 η 2 h X k Ek ∥zv,i − z̄vk ∥2 . Ek ∥vik+1 − v̄ k+1 ∥2 ≤ ρ ∥vik − v̄ k ∥2 + 1−ρ i=1 i=1 i=1 Proof. In fact, we have n n hX i hX hXn Ek ∥vik+1 − v̄ k+1 ∥2 = Ek ∥Prv i=1
n i 1X h Xn i i k k wij (vjk + ηzv,j ) − Prv wsj (vjk + ηzv,j ) ∥2 j=1 j=1 n s=1 i=1 n n n n hX X i 1 XX k k ≤ Ek ∥ wij (vjk + ηzv,j )− wsj (vjk + ηzv,j )∥2 n s=1 j=1 i=1 j=1 n n i hX Xn 2i 1 h X Xn η2 k Ek ∥ wij vjk − v̄ k ∥2 + Ek wij zv,j − z̄vk j=1 j=1 ρ 1−ρ i=1 i=1 n n i X ρ2 η 2 h X k ≤ρ ∥vik − v̄ k ∥2 + Ek ∥zv,i − z̄vk ∥2 , 1−ρ i=1 i=1
≤
14
where the first inequality follows from Lemma II.4, the second follows from Cauchy-Schwarz inequality and the notation defined in (12), the third follows from Lemma II.3 (b). Remark A.5. By following similar deductions as in Lemma A.4, we can derive n n i i X ρ2 α 2 h X k k+1 2 k k 2 ≤ ρ ∥xk+1 − x̄ ∥ ∥x − x̄ ∥ + E ∥zx,i − z̄xk ∥2 , k i i 1−ρ i=1 i=1 i=1 n n n hX i h i 2 2 X X ρ β k Ek Ek ∥yik+1 − ȳ k+1 ∥2 ≤ ρ ∥yik − ȳ k ∥2 + ∥zy,i − z̄yk ∥2 . 1−ρ i=1 i=1 i=1
Ek
n hX
The details are omitted. Next, we bound the term Ek
hP
n k k 2 i=1 ∥dx,i −dx̃,i ∥
i
in (17), as well as Ek
hP
n k k 2 i=1 ∥dy,i −dỹ,i ∥
i
and Ek
hP
n k k 2 i=1 ∥dv,i −dṽ,i ∥
i
.
Lemma A.6. The sequences {dkx,i }, {dkv,i } and {dky,i } generated by (8) satisfy Ek Ek Ek
n hX i=1 n hX i=1 n hX
n i X ∥dkx,i − dkx̃,i ∥2 ≤ C1 ∥xki − x̃ki ∥2 + ∥yik − ỹik ∥2 + ∥vik − ṽik ∥2 ,
i ∥dkv,i − dkṽ,i ∥2 ≤ C1 i k ∥dky,i − dỹ,i ∥2 ≤ C2
i=1
i=1 n X i=1 n X
(18)
∥xki − x̃ki ∥2 + ∥yik − ỹik ∥2 + ∥vik − ṽik ∥2 ,
(19)
∥xki − x̃ki ∥2 + ∥yik − ỹik ∥2 ,
(20)
i=1
where C1 and C2 are defined in (13). Proof. By the definition of dkx,i in (6) and the representation of dkx̃,i in (11), it follows that Ek
n hX
n i hX i ∥dkx,i − dkx̃,i ∥2 ≤ 3Ek ∥∇1 Fi (xki , yik ) − ∇1 Fi (x̃ki , ỹik )∥2
i=1
i=1
+ 3Ek
n hX
n i hX i ∥(∇212 fi (xki , yik ) − ∇212 fi (x̃ki , ỹik ))vik ∥2 + 3Ek ∥∇212 fi (x̃ki , ỹik )(vik − ṽik )∥2
i=1
i=1
≤ 3(LF,1 + rv Lf,2 )2 Ek
n hX
i
∥xki − x̃ki ∥2 + 3(LF,1 + rv Lf,2 )2 Ek
i=1
+ 3L2f,1 Ek
n hX
n hX
∥yik − ỹik ∥2
i
i=1
i
∥vik − ṽik ∥2 ≤ C1
i=1
n X
∥xki − x̃ki ∥2 + ∥yik − ỹik ∥2 + ∥vik − ṽik ∥2 ,
i=1
where the second inequality is due to Assumption II.1 (b) and (c) and ∥vik ∥ ≤ rv for all i. Similarly, by (5) and (10), we can derive Ek
n hX
n i X ∥dkv,i − dkṽ,i ∥2 ≤ C1 ∥xki − x̃ki ∥2 + ∥yik − ỹik ∥2 + ∥vik − ṽik ∥2 ,
i=1
i=1
and by (4) and (9), we can also derive Ek
n hX
n i hX i k ∥dky,i − dỹ,i ∥2 ≤ Ek ∥∇2 fi (xki , yik ) − ∇2 fi (x̃ki , ỹik )∥2
i=1
i=1
≤ L2f,1 Ek
n hX i=1
i
∥xki − x̃ki ∥2 + L2f,1 Ek
n hX
n i X ∥yik − ỹik ∥2 = C2 ∥xki − x̃ki ∥2 + ∥yik − ỹik ∥2 .
i=1
i=1
This completes the proof. Lemma A.7. The sequences {xki } and {x̃ki } generated by (8) satisfy Ek
n hX
n n i 1 − pX hX i 1 ∥xk+1 − x̃k+1 ∥2 ≤ ∥xki − x̃ki ∥2 + Ek ∥xk+1 − xki ∥2 . i i i ρ i=1 1−ρ i=1 i=1
(21)
15
Proof. From the update of x̃k+1 in (8f), we get i n n hX i hX i k+1 2 k+1 k+1 2 k k Ek = E ∥xk+1 − x̃ ∥ ∥x − x + x − x̃ ∥ k i i i i i i i=1
i=1 n n hX i 1 hX i 1 k 2 k k k 2 ≤ Ek + E ∥xk+1 − x ∥ ∥(1 − ξ )(x − x̃ )∥ k i i i i 1−ρ ρ i=1 i=1 n n hX i 1 − pX 1 k 2 = Ek + ∥xki − x̃ki ∥2 , ∥xk+1 − x ∥ i i 1−ρ ρ i=1 i=1
where the inequality is due to the Cauchy-Schwarz inequality. Remark A.8. The following inequalities can be derived by following similar steps as in Lemma A.7 (details are omitted to avoid redundancy): n n n hX i 1 − pX hX i 1 ∥vik − ṽik ∥2 + Ek Ek ∥vik+1 − ṽik+1 ∥2 ≤ ∥vik+1 − vik ∥2 , (22) ρ i=1 1−ρ i=1 i=1 n n n hX i hX i 1 − pX 1 ∥yik − ỹik ∥2 + Ek (23) Ek ∥yik+1 − yik ∥2 . ∥yik+1 − ỹik+1 ∥2 ≤ ρ i=1 1−ρ i=1 i=1 hP i n k+1 k 2 Next, we bound the term Ek ∥v − v ∥ in (22). i i i=1 Lemma A.9. The sequence {vik } generated by (8) satisfies n n n n hX i hX i X 1 − pX k k ∥dv,i − dkṽ,i ∥2 . Ek ∥vik+1 − vik ∥2 ≤8 ∥vik − v̄ k ∥2 + 4η 2 Ek ∥zv,i − z̄vk ∥2 + 4nη 2 ∥d¯kv ∥2 + 4η 2 p i=1 i=1 i=1 i=1 k Proof. It follows from the update of zv,i in (8c) that (15)
z̄vk = t̄kv + ξ k (d¯kv − d¯kṽ )/p = d¯kṽ + ξ k (d¯kv − d¯kṽ )/p. h i h i Then, we have z̄vk − d¯kv = (1 − ξ k /p)(d¯kṽ − d¯kv ). Since Ek ξ k = p, we have Ek 1 − ξ k /p = 0. Thus, we have h i h i h i Ek ⟨z̄vk − d¯kv , d¯kv ⟩ = Ek ⟨(1 − ξ k /p)(d¯kṽ − d¯kv ), d¯kv ⟩ = Ek 1 − ξ k /p ⟨d¯kṽ − d¯kv , d¯kv ⟩ = 0.
(24)
By following the update of vik+1 in (8c) , we derive n n n n n hX i hX i hX i X X k k Ek ∥vik+1 − vik ∥2 = Ek ∥Prv [ wij (vjk + ηzv,j )] − vik ∥2 ] ≤ Ek ∥ wij (vjk + ηzv,j ) − vik ∥2 i=1
i=1
j=1
i=1
j=1
n n n n n n hX i hX i hX i hX i X X k ≤ 4Ek ∥ wij vjk − v̄ k ∥2 + 4Ek ∥v̄ k − vik ∥2 + 4η 2 Ek ∥ wij zv,j − z̄vk ∥2 + 4η 2 Ek ∥z̄vk ∥2 i=1
≤ 8Ek
n hX
j=1
i=1
i
∥vik − v̄ k ∥2 + 4η 2 Ek
n hX
i=1
i=1
i
h
j=1
i=1
k ∥zv,i − z̄vk ∥2 + 4nη 2 Ek ∥d¯kv ∥2 + ∥z̄vk − d¯kv ∥2
i
i=1
n n n hX i X X k k 2 2 k k 2 2 ¯k 2 21 − p ≤8 ∥vi − v̄ ∥ + 4η Ek ∥zv,i − z̄v ∥ + 4nη ∥dv ∥ + 4η ∥dk − dkṽ,i ∥2 , p i=1 v,i i=1 i=1
Ps 2 where Ps the2 first inequality holds because the projection operator is non-expansive, the second follows from ( l=1 al ) ≤ s l=1 al , the third is due to Lemma II.3 and (24), and the last one follows from n n h i h 1X i i 1 h X nEk ∥d¯kv − z̄vk ∥2 = nEk ∥ (1 − ξ k /p)(dkṽ,i − dkv,i )∥2 = Ek ∥ (1 − ξ k /p)(dkṽ,i − dkv,i )∥2 n i=1 n i=1 n n hX i h iX ≤ Ek ∥(1 − ξ k /p)(dkṽ,i − dkv,i )∥2 = Ek (1 − ξ k /p)2 ∥dkṽ,i − dkv,i ∥2 i=1
i=1
n n X 1 − pX k ∥dṽ,i − dkv,i ∥2 . = p(1 − 1/p)2 + (1 − p) ∥dkṽ,i − dkv,i ∥2 = p i=1 i=1
This completes the proof.
(25)
16
Remark A.10. Similarly, we can deduce the following inequalities. The details are omitted. n n n i hX i X X k 2 k k 2 2 2 ¯k 2 21 − p k k 2 ≤8 ∥dkx,i − dkx̃,i ∥2 , ∥xk+1 − x ∥ ∥x − x̄ ∥ + 4α E + 4nα ∥ d ∥ + 4α ∥z − z̄ ∥ k i i x x,i x i p i=1 i=1 i=1 i=1 n n n n hX i hX i X X 1−p k k Ek ∥yik+1 − yik ∥2 ≤8 ∥yik − ȳ k ∥2 + 4β 2 Ek ∥dky,i − dỹ,i ∥2 . ∥zy,i − z̄yk ∥2 + 4nβ 2 ∥d¯ky ∥2 + 4β 2 p i=1 i=1 i=1 i=1 hP i n k+1 k+1 2 k k 2 Next, we bound Ek ˜,i ∥ + ∥d⋆,i − d⋆ ˜,i ∥ ) for ⋆ = x, y, v respectively. By combining (18)-(23), we i=1 (∥d⋆,i − d⋆ derive n hX i k+1 2 Ek ∥dkx,i − dkx̃,i ∥2 + ∥dk+1 − d ∥ x,i x̃,i
Ek
n hX
i=1
≤C1 Ek
n hX
∥xk+1 − x̃k+1 ∥2 + ∥yik+1 − ỹik+1 ∥2 + ∥vik+1 − ṽik+1 ∥2 + ∥xki − x̃ki ∥2 + ∥yik − ỹik ∥2 + ∥vik − ṽik ∥2 i i
i
i=1
≤C1
n X 1−p+ρ
ρ n hX
i=1
+
1 Ek 1−ρ
∥xki − x̃ki ∥2 + ∥yik − ỹik ∥2 + ∥vik − ṽik ∥2 ∥xk+1 − xki ∥2 + i
i=1
n X
∥yik+1 − yik ∥2 +
i=1
n X
∥vik+1 − vik ∥2
i
.
(26)
i=1
Similarly, we can deduce Ek
n hX
k+1 2 k ∥dky,i − dỹ,i ∥2 + ∥dk+1 y,i − dỹ,i ∥
i
i=1
≤ C2
n X 1−p+ρ
ρ
i=1
∥xki − x̃ki ∥2 + ∥yik − ỹik ∥2
n n i hX X 1 k+1 k 2 + Ek ∥xi − xi ∥ + ∥yik+1 − yik ∥2 , 1−ρ i=1 i=1
(27)
and Ek
n hX
k+1 2 ∥dkv,i − dkṽ,i ∥2 + ∥dk+1 v,i − dṽ,i ∥
i
i=1
≤ C1
n X 1−p+ρ i=1
+
ρ n hX
1 Ek 1−ρ
∥xki − x̃ki ∥2 + ∥yik − ỹik ∥2 + ∥vik − ṽik ∥2 ∥xk+1 − xki ∥2 + i
n X i=1
i=1
∥yik+1 − yik ∥2 +
n X
∥vik+1 − vik ∥2
i
.
(28)
i=1
Next, we recall a Lemma from [28], which is useful for bounding ∥d¯ky ∥2 and ∥d¯kv ∥2 . Lemma A.11. [28, Lemma A.7] The sequences {dky,i } and {dkv,i } generated by (8) satisfy ∥d¯ky ∥2 ≤
n 2L2f,1 X ∥xki − x̄k ∥2 + ∥yik − ȳ k ∥2 + 2L2f,1 ∥ȳ k − y ∗ (x̄k )∥2 , n i=1
∥d¯kv ∥2 ≤
n n 5L2f,1 X 5(Lf,2 rv + LF,1 )2 X ∥xki − x̄k ∥2 + ∥yik − ȳ k ∥2 + ∥vik − v̄ k ∥2 n n i=1 i=1
+ 5(LF,1 + rv Lf,2 )2 ∥ȳ k − y ∗ (x̄k )∥2 + 5L2f,1 ∥v̄ k − v ∗ (x̄k )∥2 .
(29)
(30)
Now, by combining (17), A.3, Lemma A.9, Remark A.10 and (26)-(30), we can establish the i h Pthe inequalities in Remark n k+1 1 k+1 2 following results for Ek n i=1 ∥z⋆,i − z̄⋆ ∥ for ⋆ = x, y, v respectively. Again, details are omitted for simplicity. Ek
n h1 X
k+1 ∥zx,i − z̄xk+1 ∥2
i
n i=1 n n n i h1 X i h1 X i 4α2 C h 1 X k 4β 2 C 4η 2 C k k ≤ ρ+ Ek ∥zx,i − z̄xk ∥2 + Ek ∥zy,i − z̄yk ∥2 + Ek ∥zv,i − z̄vk ∥2 3 3 3 (1 − ρ) ρp n i=1 (1 − ρ) ρp n i=1 (1 − ρ) ρp n i=1 n (1 − p + ρ)C 2 2 2 2 X 4(α + β + η )C 1 4α2 C + + ∥xki − x̃ki ∥2 + ∥yik − ỹik ∥2 + ∥vik − ṽik ∥2 + ∥d¯kx ∥2 2 2 3 2 (1 − ρ) ρ p (1 − ρ )p n i=1 (1 − ρ)3 ρp
17
+
n n n (8 + 8L2f,1 β 2 + 20η 2 L21 )C 1 X k 1X k 1X k 8C ∥xi − x̄k ∥2 + ∥yi − ȳ k ∥2 + ∥vi − v̄ k ∥2 3 3 (1 − ρ) ρp n i=1 n i=1 (1 − ρ) ρp n i=1
+
(8L2f,1 β 2 + 20η 2 L21 )C k 20η 2 L21 C ∥ȳ − y ∗ (x̄k )∥2 + ∥v̄ k − v ∗ (x̄k )∥2 , 3 (1 − ρ) ρp (1 − ρ)3 ρp
Ek
n h1 X
k+1 − z̄yk+1 ∥2 ∥zy,i
i
n i=1 n n i h1 X i 4β 2 C h 1 X k 4α2 C k ≤ ρ+ Ek ∥zy,i − z̄yk ∥2 + Ek ∥zx,i − z̄xk ∥2 3 3 (1 − ρ) ρp n i=1 (1 − ρ) ρp n i=1 n (1 − p + ρ)C 2 2 2 2 8L2f,1 β 2 C k 4(α + β + η )C 1 X k k 2 k k 2 + + ∥ȳ − y ∗ (x̄k )∥2 ∥x − x̃ ∥ + ∥y − ỹ ∥ + i i i i (1 − ρ)2 ρ2 p (1 − ρ3 )p2 n i=1 (1 − ρ)3 ρp n n (8 + 8L2f,1 β 2 )C 1 X k 1X k 4α2 C k 2 + ∥d¯kx ∥2 , ∥x − x̄ ∥ + ∥yi − ȳ k ∥2 + i 3 (1 − ρ) ρp n i=1 n i=1 (1 − ρ)3 ρp n h1 X i k+1 Ek − z̄vk+1 ∥2 ∥zv,i n i=1 n n n i h1 X i h1 X i 4α2 C 4β 2 C 4η 2 C h 1 X k k 2 k k 2 k k 2 ∥z − z̄ ∥ + E ∥z − z̄ ∥ + E ∥z − z̄ ∥ ≤ ρ+ E k k k v,i v x,i x y,i y (1 − ρ)3 ρp n i=1 (1 − ρ)3 ρp n i=1 (1 − ρ)3 ρp n i=1 n (1 − p + ρ)C 4(α2 + β 2 + η 2 )C 2 1 X 4α2 C + + ∥xki − x̃ki ∥2 + ∥yik − ỹik ∥2 + ∥vik − ṽik ∥2 + ∥d¯kx ∥2 2 2 3 2 (1 − ρ) ρ p (1 − ρ )p n i=1 (1 − ρ)3 ρp n n n (8 + 8L2f,1 β 2 + 20η 2 L21 )C 1 X k 1X k 8C 1X k + ∥xi − x̄k ∥2 + ∥yi − ȳ k ∥2 + ∥vi − v̄ k ∥2 3 3 (1 − ρ) ρp n i=1 n i=1 (1 − ρ) ρp n i=1 +
(31)
(8L2f,1 β 2 + 20η 2 L21 )C k 20η 2 L21 C ∥ȳ − y ∗ (x̄k )∥2 + ∥v̄ k − v ∗ (x̄k )∥2 , 3 (1 − ρ) ρp (1 − ρ)3 ρp
(32)
(33)
where C = max{C1 , C2 } and L1 is defined in (7).
3) Some lemmas for convergence rate of Algorithm 1: Recall that Φ(x) = F (x, y ∗ (x)) denotes the overall objective function. For
any k > 0, Φ(x̄k ) and ∇Φ(x̄k ) are also measurable with respect to Fk . Lemma A.12. The sequence {(xki , yik , vik )} generated by (8) satisfies h i i 5αL2 (1/α − LΦ ) h k+1 α f,1 Ek Φ(x̄k+1 ) − Φ(x̄k ) ≤ − ∥∇Φ(x̄k )∥2 − Ek ∥x̄ − x̄k ∥2 + ∥v̄ k − v ∗ (x̄k )∥2 2 2 2 n 5αL2f,1 X k 5α (LF,1 + Lf,2 rv )2 k ∥ȳ − y ∗ (x̄k )∥2 + ∥vi − v̄ k ∥2 + 2 2n i=1 n n α(1 − p) X 5α (LF,1 + rv Lf,2 )2 X k k + ∥xi − x̄k ∥2 + ∥yik − ȳ k ∥2 + ∥dkx,i − dx̃,i ∥2 , 2n 2np i=1 i=1 where LΦ is defined in (7). k Proof. From the updates of xk+1 and zx,i in (8e), we have i
x̄k+1 = x̄k − αz̄xk .
(34)
It follows from Lemma 2.2 in [13] that ∇Φ(x) is LΦ -Lipschitz continuous. On the other hand, from Lemma 5.7 in [45] we derive h i h i LΦ k+1 Ek Φ(x̄k+1 ) − Φ(x̄k ) ≤ Ek ∇Φ(x̄k ), x̄k+1 − x̄k + ∥x̄ − x̄k ∥2 2 h i i (34) LΦ h k+1 k k − x̄k ∥2 = − α ∇Φ(x̄ ), Ek z̄x + Ek ∥x̄ 2 i i α h i L h α α h Φ = − ∥∇Φ(x̄k )∥2 − Ek ∥z̄xk ∥2 + Ek ∥∇Φ(x̄k ) − z̄xk ∥2 + Ek ∥x̄k+1 − x̄k ∥2 2 2 2 2 h i α (34) α 1 k 2 k+1 k 2 k k 2 ¯ = − ∥∇Φ(x̄ )∥ − Ek ∥x̄ − x̄ ∥ + ∥∇Φ(x̄ ) − dx ∥ 2 2α 2 i L h i α h ¯k Φ k 2 k+1 k 2 + Ek ∥dx − z̄x ∥ + Ek ∥x̄ − x̄ ∥ , (35) 2 2 h i h i where the last equality is due to Ek ⟨∇Φ(x̄k ) − d¯kx , d¯kx − z̄xk ⟩ = Ek 1 − ξ k /p ⟨∇Φ(x̄k ) − d¯kx , d¯kx − d¯kx̃ ⟩ = 0. By definition, we have P k k 2 k k k ∇Φ(x̄k ) = ∇1 F (x̄k , y ∗ (x̄k )) − ∇212 f (x̄k , y ∗ (x̄k ))v ∗ (x̄k ) and d¯kx = n1 n i=1 ∇1 Fi (xi , yi ) − ∇12 fi (xi , yi )vi . For convenience, we define ∆1 := ∇1 F (x̄k , y ∗ (x̄k )) − ∇212 f (x̄k , y ∗ (x̄k ))v ∗ (x̄k ) − ∇1 F (x̄k , ȳ k ) + ∇212 f (x̄k , ȳ k )v̄ k , P k k 2 k k k ∆2 := ∇1 F (x̄k , ȳ k ) − ∇212 f (x̄k , ȳ k )v̄ k − n1 n . i=1 ∇1 Fi (xi , yi ) − ∇12 fi (xi , yi )vi
18
From the triangle inequality and ∥vi ∥ ≤ rv for all i, we derive ∆1 ≤ ∇1 F (x̄k , y ∗ (x̄k )) − ∇1 F (x̄k , ȳ k ) + + ∇212 f (x̄k , y ∗ (x̄k )) v̄ k − v ∗ (x̄k )
∇212 f (x̄k , ȳ k ) − ∇212 f (x̄k , y ∗ (x̄k )) v̄ k
≤ (LF,1 + Lf,2 rv ) ∥ȳ k − y ∗ (x̄k )∥ + Lf,1 ∥v̄ k − v ∗ (x̄k )∥. P Pn 1 By using the triangle inequality again and considering F = n1 n i=1 Fi and f = n i=1 fi , we derive
(36)
n
1X ∇1 Fi (x̄k , ȳ k ) − ∇212 fi (x̄k , ȳ k )v̄ k − ∇1 Fi (xki , yik ) + ∇212 fi (xki , yik )vik ) n i=1 n n 1X 1X 2 ≤ ∇1 Fi (x̄k , ȳ k ) − ∇1 Fi (xki , yik ) + ∇12 fi (x̄k , ȳ k ) − ∇212 fi (xki , yik ) vik n i=1 n i=1
∆2 ≤
n
+ ≤
1X ∇212 fi (x̄k , ȳ k )(v̄ k − vik ) n i=1
n n Lf,1 X LF,1 + rv Lf,2 X ∥xki − x̄k ∥ + ∥yik − ȳ k ∥ + ∥vik − v̄ k ∥. n n i=1 i=1
(37)
2 Ps It P is easy to observe from the triangle inequality that ∥∇Φ(x̄k ) − d¯kx ∥ ≤ ∆1 + ∆2 . Then, by using (36), (37) and the inequality ≤ l=1 al s s l=1 a2l , it is easy to derive ∇Φ(x̄k ) − d¯kx
2
≤ 5 (LF,1 + Lf,2 rv )2 ∥ȳ k − y ∗ (x̄k )∥2 + 5L2f,1 ∥v̄ k − v ∗ (x̄k )∥2
n n 5L2 X 5 (LF,1 + rv Lf,2 )2 X k f,1 ∥xi − x̄k ∥2 + ∥yik − ȳ k ∥2 + ∥vik − v̄ k ∥2 , n n i=1 i=1 i h Pn 2 k k which, together with (35) and Ek ∥d¯kx − z̄xk ∥2 ≤ 1−p i=1 ∥dx,i − dx̃,i ∥ (similar to (25)), yields the desired result. np i i h h The next two lemmas bound Ek ∥ȳ k+1 − y ∗ (x̄k )∥2 and Ek ∥v̄ k+1 − v ∗ (x̄k )∥2 , respectively.
+
Lemma A.13. The sequence {(xki , yik , vik )} generated by (8) satisfies n h i 3βL2f,1 X k βσ k Ek ∥ȳ k+1 − y ∗ (x̄k )∥2 ≤ 1 − ∥ȳ − y ∗ (x̄k )∥2 + ∥x̄ − xki ∥2 + ∥ȳ k − yik ∥2 2 nσ i=1 n 2 (1 − p)β C2 X + ∥xki − x̃ki ∥2 + ∥yik − ỹik ∥2 . np i=1
(38)
Proof. First, by Cauchy-Schwarz inequality, for any Λ > 0, we have ∥ȳ k − β d¯ky − y ∗ (x̄k )∥2 = ∥ ȳ k − β∇2 f (x̄k , ȳ k ) − y ∗ (x̄k ) + β ∇2 f (x̄k , ȳ k ) − d¯ky ∥2 ≤ (1 + Λ)∥ȳ k − β∇2 f (x̄k , ȳ k ) − y ∗ (x̄k )∥2 + (1 + 1/Λ)β 2 ∥∇2 f (x̄k , ȳ k ) − d¯ky ∥2 . k
∗
k
(39)
k
Note that ∇2 f (x̄ , y (x̄ )) = 0. It follows from the σ-strong convexity of f (x̄ , ·), Lf,1 -smoothness of f and [46, Theorem 2.1.12] that ⟨ȳ k − y ∗ (x̄k ), ∇2 f (x̄k , ȳ k )⟩ = ⟨ȳ k − y ∗ (x̄k ), ∇2 f (x̄k , ȳ k ) − ∇2 f (x̄k , y ∗ (x̄k ))⟩ σLf,1 1 ≥ ∥ȳ k − y ∗ (x̄k )∥2 + ∥∇2 f (x̄k , ȳ k )∥2 . σ + Lf,1 σ + Lf,1
(40)
1 2 By expanding ∥ȳ k − β∇2 f (x̄k , ȳ k ) − y ∗ (x̄k )∥2 , plugging in (40), and noting that σ ≤ Lf,1 and β ≤ Lf,1 ≤ σ+L in Algorithm 1, we f,1 obtain 2βσLf,1 k ∥ȳ − y ∗ (x̄k )∥2 ≤ (1 − βσ)∥ȳ k − y ∗ (x̄k )∥2 . (41) ∥ȳ k − β∇2 f (x̄k , ȳ k ) − y ∗ (x̄k )∥2 ≤ 1 − σ + Lf,1 P ¯k It is elementary to show from f = n1 n i=1 fi , the definition of dy in (12), the triangle inequality and Assumption II.1 (c) that n L2f,1 X ∥∇2 f (x̄k , ȳ k ) − d¯ky ∥2 ≤ ∥x̄k − xki ∥2 + ∥ȳ k − yik ∥2 . n i=1 i h From (16), we know that Ek ⟨d¯ky − z̄yk , ȳ k − β d¯ky − y ∗ (x̄k )⟩ = 0, and thus we have h i h i Ek ∥ȳ k+1 − y ∗ (x̄k )∥2 = Ek ∥ȳ k − β d¯ky − y ∗ (x̄k ) + β(d¯ky − z̄yk )∥2 h i = ∥ȳ k − β d¯ky − y ∗ (x̄k )∥2 + Ek β 2 ∥d¯ky − z̄yk ∥2 .
(42)
(43)
19
By combining (25), (39), (41)-(43), we derive n h i 1 − p β2 X k k Ek ∥ȳ k+1 − y ∗ (x̄k )∥2 ≤ (1 + Λ)(1 − βσ)∥ȳ k − y ∗ (x̄k )∥2 + ∥dy,i − dỹ,i ∥2 p n i=1 n
+ (1 + 1/Λ)
β 2 L2f,1 X ∥x̄k − xki ∥2 + ∥ȳ k − yik ∥2 . n i=1
The desired result (38) can be obtained by setting Λ = βσ/2 and using βσ ≤ 1 and (20). Lemma A.14. The sequence {(xki , yik , vik )} generated by (8) satisfies h i 2 2 3η (LF,1 + Lf,2 rv )2 k ȳ − y ∗ (x̄k ) Ek ∥v̄ k+1 − v ∗ (x̄k )∥2 ≤ (1 − ησ/2) v̄ k − v ∗ (x̄k ) + σ n n 2η 2 ρ2 h X i 9η (LF,1 + Lf,2 rv )2 X k k 2 k k 2 k Ek + ∥xi − x̄ ∥ + ∥yi − ȳ ∥ + ∥zv,i − z̄vk ∥2 nσ n i=1 i=1 n n 2 2X 2 X 9ηLf,1 /σ + 2ρ (1 − p)η C 1 + ∥xki − x̃ki ∥2 + ∥yik − ỹik ∥2 + ∥vik − ṽik ∥2 . ∥vik − v̄ k ∥2 + n np i=1 i=1
(44)
Proof. For convenience, we define (
∆3 := v̄ k + η ∇2 F (x̄k , ȳ k ) − ∇222 f (x̄k , ȳ k )v̄ k − v ∗ (x̄k ), ∆4 := ∇222 f (x̄k , ȳ k )v̄ k − ∇2 F (x̄k , ȳ k ) + d¯kv .
Similar to (39), for any δ > 0, we have ∥v̄ k + η d¯kv − v ∗ (x̄k )∥2 ≤ (1 + δ) ∥∆3 ∥2 + (1 + 1/δ)η 2 ∥∆4 ∥2 .
(45)
First, we treat the term ∥∆3 ∥2 in (45). Since ∇222 f (x̄k , y ∗ (x̄k ))v ∗ (x̄k ) = ∇2 F (x̄k , y ∗ (x̄k )), we have the following reformulation: ∆3 = ∆3,1 − η ∆3,2 + ∆3,3 , where k 2 k k ∗ k ∆ := I − η∇ f (x̄ , ȳ ) v̄ − v (x̄ ) , 3,1 22 2 ∗ k k k 2 k ∗ k ∆3,2 := ∇22 f (x̄ , ȳ ) − ∇22 f (x̄ , y (x̄ )) v (x̄ ), ∆3,3 := ∇2 F (x̄k , y ∗ (x̄k )) − ∇2 F (x̄k , ȳ k ). By Cauchy-Schwarz inequality, for any δ1 > 0, we have ∥∆3 ∥2 ≤ (1 + δ1 ) ∥∆3,1 ∥2 + (1 + 1/δ1 ) η 2 ∥∆3,2 + ∆3,3 ∥2 . Since η ≤ 1/Lf,1 and f (x, ·) is σ-strongly convex, there holds ∥∆3,1 ∥ ≤ I − η∇222 f (x̄k , ȳ k )
v̄ k − v ∗ (x̄k ) ≤ (1 − ησ) v̄ k − v ∗ (x̄k ) . op
Furthermore, it is apparent from Assumption II.1 that ∥∆3,2 + ∆3,3 ∥ ≤ (Lf,2 rv + LF,1 ) ∥ȳ k − y ∗ (x̄k )∥. By taking δ1 = ησ and noting ησ ≤ ηLf,1 ≤ 1, we obtain ∥∆3 ∥2 ≤ (1 + ησ) (1 − ησ)2 v̄ k − v ∗ (x̄k ) ≤ (1 − ησ) v̄ k − v ∗ (x̄k )
2
+
2
+ (1 + 1/ησ) η 2 (Lf,2 rv + LF,1 )2 ȳ k − y ∗ (x̄k )
2 2η (Lf,2 rv + LF,1 )2 k ȳ − y ∗ (x̄k ) . σ
2
(46)
Next, we treat the term ∥∆4 ∥2 in (45). The definition of d¯kv implies that ∥∆4 ∥2 ≤
n n 3X 3X 2 2 ∇222 fi (x̄k , ȳ k )(v̄ k − vik ) + [∇222 fi (x̄k , ȳ k ) − ∇222 fi (xki , yik )]vik n i=1 n i=1 n
3X 2 ∇2 Fi (x̄k , ȳ k ) − ∇2 Fi (xki , yik ) n i=1 n n 3L2 X 3(Lf,2 rv + LF,1 )2 X k f,1 ≤ ∥xi − x̄k ∥2 + ∥yik − ȳ k ∥2 + ∥vik − v̄ k ∥2 . n n i=1 i=1 +
(47)
20
Similar to Lemma A.13, we next evaluate n X
∥vik+1 − v ∗ (x̄k )∥2 =
Pn
k+1 − v ∗ (x̄k )∥2 to bound ∥v̄ k+1 − v ∗ (x̄k )∥2 . By the update of vik+1 in (8c), we have i=1 ∥vi
n X
Prv
hXn j=1
i=1
i=1
≤
n X Xn j=1
i=1
=
n X Xn j=1
i=1
≤ ≤
n X
i
− v ∗ (x̄k )
2
2 k − v ∗ (x̄k ) wij vjk + ηzv,j
wij vjk − v̄ k + η
∗
k
k wij vjk + ηzv,j
∥v̄ − v (x̄
k
Xn
) + ηz̄vk ∥2 + 2
j=1
i=1
i=1 n X 2
∥v̄ k − v ∗ (x̄k ) + ηz̄vk ∥2 + 2ρ
2
+
n X
j=1
wij vjk − v̄ k
2
+ 2η 2
n X Xn i=1
j=1
k wij zv,j − z̄vk
2
n X k ∥vik − v̄ k ∥2 + 2η 2 ρ2 ∥zv,i − z̄vk ∥2 ,
i=1
hP n
Pn
∥v̄ k − v ∗ (x̄k ) + ηz̄vk ∥2
i=1
n X Xn
n X i=1
k wij zv,j − z̄vk
i=1
k k where the second equality holds because i=1 j=1 wij vj − v̄ + η( Lemma II.3. Then, by combining (19), (45)-(47), we derive
Pn
k k j=1 wij zv,j − z̄v )
i
= 0, and the last inequality follows from
n i h i 1 h X k+1 − v ∗ (x̄k )∥2 Ek ∥v̄ k+1 − v ∗ (x̄k )∥2 ≤ Ek ∥vi n i=1 n n i 2ρ2 h X h i 2η 2 ρ2 h X i k ≤ Ek ∥v̄ k − v ∗ (x̄k ) + η d¯kv + η(z̄vk − d¯kv )∥2 + ∥vik − v̄ k ∥2 + ∥zv,i − z̄vk ∥2 Ek Ek n n i=1 i=1 n n h i h i 2ρ2 h X i 2η 2 ρ2 h X i k ∗ k k 2 2 k k 2 k k 2 k = Ek ∥v̄ − v (x̄ ) + η d¯v ∥ + η Ek ∥z̄v − d¯v ∥ + Ek ∥vi − v̄ ∥ + Ek ∥zv,i − z̄vk ∥2 n n i=1 i=1 2 2(1 + δ)η (LF,1 + Lf,2 rv )2 k ȳ − y ∗ (x̄k ) σ n n i X X 3(1 + 1/δ)η 2 h ∥vik − v̄ k ∥2 ∥xki − x̄k ∥2 + ∥yik − ȳ k ∥2 + L2f,1 (LF,1 + Lf,2 rv )2 + n i=1 i=1 n n n hX i (1 − p)η 2 X 2 X 2 2 2ρ 2ρ η k + ∥vik − v̄ k ∥2 + Ek ∥zv,i − z̄vk ∥2 + ∥dkv,i − dkṽ,i ∥2 , n i=1 n np i=1 i=1
≤ (1 + δ) (1 − ησ) v̄ k − v ∗ (x̄k )
2
+
2 Ps P where the first inequality is because ≤ s sl=1 a2l , and the equality is due to l=1 al h i h i Ek ⟨v̄ k − v ∗ (x̄k ) + η d¯kv , z̄vk − d¯kv ⟩ = Ek 1 − ξ k /p ⟨v̄ k − v ∗ (x̄k ) + η d¯kv , d¯kṽ − d¯kv ⟩) = 0. Finally, the desired result (44) follows from setting δ = ησ/2 and using ησ ≤ 1 and (19). Lemma A.15. Let Lv be defined in (7). Then, there hold ∥y ∗ (x̄k+1 ) − y ∗ (x̄k )∥ ≤
Lf,1 k+1 Lv k+1 ∥x̄ − x̄k ∥ and ∥v ∗ (x̄k+1 ) − v ∗ (x̄k )∥ ≤ ∥x̄ − x̄k ∥. σ σ
(48)
Proof. Due to the optimality of y ∗ (x), we have ∇2 f (x, y ∗ (x)) = 0 for any x. Now, let x and x′ be arbitrarily fixed. It follows from the σ-strong convexity of f (x, ·) and Lf,1 -Lipschitz continuity of ∇f that σ∥y ∗ (x) − y ∗ (x′ )∥ ≤ ∥∇2 f (x, y ∗ (x)) − ∇2 f (x, y ∗ (x′ ))∥ = ∥∇2 f (x, y ∗ (x′ )) − ∇2 f (x′ , y ∗ (x′ ))∥ ≤ Lf,1 ∥x − x′ ∥. Hence, we have ∥y ∗ (x) − y ∗ (x′ )∥ ≤
Lf,1 ∥x − x′ ∥. σ
(49)
The first inequality in (48) follows immediately from (49) by taking x = x̄k+1 and x′ = x̄k . Next, to obtain the second inequality in (48), we define ( ∆5 := ∇2 F (x̄k , y ∗ (x̄k )) − ∇2 F (x̄k+1 , y ∗ (x̄k+1 )), ∆6 := ∇222 f (x̄k+1 , y ∗ (x̄k+1 )) − ∇222 f (x̄k , y ∗ (x̄k )) v ∗ (x̄k+1 ). By using Assumption II.1, we have (
∥∆5 ∥ ≤ LF,1 ∥x̄k+1 − x̄k ∥ + ∥y ∗ (x̄k+1 ) − y ∗ (x̄k )∥ , ∥∆6 ∥ ≤ Lf,2 rv ∥x̄k+1 − x̄k ∥ + ∥y ∗ (x̄k+1 ) − y ∗ (x̄k )∥ .
(50)
It follows from ∇222 f (x̄k+1 , y ∗ (x̄k+1 ))v ∗ (x̄k+1 ) = ∇2 F (x̄k+1 , y ∗ (x̄k+1 )) that ∇222 f (x̄k , y ∗ (x̄k ))(v ∗ (x̄k ) − v ∗ (x̄k+1 )) = ∆5 + ∆6 .
(51)
21
The σ-strong convexity of f (x̄k , ·) implies that σ∥v ∗ (x̄k ) − v ∗ (x̄k+1 )∥ ≤ ∥∇222 f (x̄k , y ∗ (x̄k ))(v ∗ (x̄k ) − v ∗ (x̄k+1 ))∥ (51)
= ∥∆5 + ∆6 ∥ ≤ ∥∆5 ∥ + ∥∆6 ∥
(49,50)
≤
(LF,1 + Lf,2 rv ) (1 + Lf,1 /σ) ∥x̄k+1 − x̄k ∥,
which implies the second inequality in (48) by noting the definition of Lv in (7).
4) Proof of Theorem III.2.:
Proof. By using Cauchy-Schwarz inequality again, we derive h h i i i h βσ 4 Ek ∥ȳ k+1 − y ∗ (x̄k+1 )∥2 ≤ 1 + Ek ∥ȳ k+1 − y ∗ (x̄k )∥2 + 1 + Ek ∥y ∗ (x̄k+1 ) − y ∗ (x̄k )∥2 . 4 βσ By taking into account (38), the first inequality in (48), and βσ ≤ 1, we obtain n h i i 15βL2 hX i βσ h k f,1 Ek ∥ȳ k+1 −y ∗ (x̄k+1 )∥2 ≤ 1 − Ek ∥ȳ − y ∗ (x̄k )∥2 + Ek ∥x̄k − xki ∥2 + ∥ȳ k − yik ∥2 4 4nσ i=1 n 2 i h i h 2 X 5Lf,1 5(1 − p)β C 2 k k 2 k k 2 k+1 k 2 ∥x − x̃ ∥ + ∥y − ỹ ∥ . + E ∥x̄ − x̄ ∥ + E k k i i i i βσ 3 4np i=1
(52)
Similarly, we can derive h i h i i ησ h k+1 4 Ek ∥v̄ k+1 − v ∗ (x̄k+1 )∥2 ≤ 1 + Ek ∥v̄ − v ∗ (x̄k )∥2 + 1 + Ek ∥v ∗ (x̄k+1 ) − v ∗ (x̄k )∥2 . 4 ησ By taking into account (44), the second inequality in (48), and ησ ≤ 1, we obtain h i 2i 2i 15η (LF,1 + Lf,2 rv )2 h k ησ h k + Ek ∥v̄ k+1 − v ∗ (x̄k+1 )∥2 ≤ 1 − Ek v̄ − v ∗ (x̄k ) Ek ȳ − y ∗ (x̄k ) 4 4σ n i 45η (L + L r )2 h X i 5L2v h k+1 F,1 f,2 v k 2 + Ek ∥x̄ − x̄ ∥ + Ek ∥xki − x̄k ∥2 + ∥yik − ȳ k ∥2 3 ησ 4nσ i=1 n n 45ηL2 h i 5ρ2 η 2 h X i 2 X 5ρ 1 f,1 k + + Ek ∥vik − v̄ k ∥2 + Ek ∥zv,i − z̄vk ∥2 4σ 2 n 2n i=1 i=1 n h i 2 X 5(1 − p)η C1 + Ek ∥xki − x̃ki ∥2 + ∥yik − ỹik ∥2 + ∥vik − ṽik ∥2 . 4np i=1
(53)
Define the Lyapunov function as in (14). By taking expectation of the inequalities in Lemma A.4, Remark A.5 and Lemma A.12, as well as (31)-(33), (52) and (53), and combining them all together, it is straightforward to derive h i i h i h i h i α h E Vk+1 − Vk ≤ − E ∥∇Φ(x̄k )∥2 − A1 E ∥d¯kx ∥2 − A2 E ∥ȳ k − y ∗ (x̄k )∥2 − A3 E ∥v̄ k − v ∗ (x̄k )∥2 2 n n n i A hX i A hX i A4 h X k 5 6 − E ∥xi − x̄k ∥2 − E ∥yik − ȳ k ∥2 − E ∥vik − v̄ k ∥2 n n n i=1 i=1 i=1 n n n h i h i hX i X k X A7 A A 8 9 k k − E ∥zx,i − z̄xk ∥2 − E ∥zy,i − z̄yk ∥2 − E ∥zv,i − z̄vk ∥2 n n n i=1 i=1 i=1 n n n h i h i h i X X X A10 A11 A12 − E ∥xki − x̃ki ∥2 − E ∥yik − ỹik ∥2 − E ∥vik − ṽik ∥2 , n n n i=1 i=1 i=1
(54)
22
where the coefficients are given by 4α2 (α2 a6 C1 + a7 β 2 C1 + a8 η 2 C2 ) α LΦ α2 4α2 a9 − − − , 3 2 2 (1 − ρ) ρp 1−ρ 2 2 2 2 2 (8β Lf,1 + 20η L1 )C1 (a6 α + a7 β 2 ) + 8β 2 L2f,1 C2 a8 η 2 a1 βσ 5αL21 3ηL21 a2 A2 = − − − 2 2 σ (1 − ρ)3 ρp 2 2 2 2 (8β Lf,1 a10 + 20η L1 a11 ) − , 1−ρ 5αL2f,1 20η 2 L2f,1 C1 (a6 α2 + a7 β 2 ) 20η 2 L2f,1 a11 a2 ησ A3 = − − − , 2 2 (1 − ρ)3 ρp 1−ρ 2 2 2 3βLf,1 a1 C1 (a6 α + a7 β )(8 + 8β 2 L2f,1 + 20η 2 L21 ) 9ηL21 a2 5αL21 − − − A4 = a3 (1 − ρ) − 2 σ σ (1 − ρ)3 ρp 2 2 2 2 2 2 2 C2 a8 η (8 + 8β Lf,1 ) 8β Lf,1 a10 8a9 20η L1 a11 − − − − , (1 − ρ)3 ρp 1−ρ 1−ρ 1−ρ 3βL2f,1 a1 C1 (a6 α2 + a7 β 2 )(8 + 8β 2 L2f,1 + 20η 2 L21 ) 5αL21 9ηL21 a2 A5 = a4 (1 − ρ) − − − − 2 σ σ (1 − ρ)3 ρp 2 2 2 2 2 2 2 (8 + 8β Lf,1 )a10 C2 a8 η (8 + 8β Lf,1 ) 20η L1 a11 − − , − (1 − ρ)3 ρp 1−ρ 1−ρ 5αL2f,1 9ηL2f,1 8C1 (a6 α2 + a7 β 2 ) 8a11 A6 = a5 (1 − ρ) − − + 2ρ2 a2 − − , 2 σ (1 − ρ)3 ρp 1−ρ 2 2 2 2 2 2 2 2 2 2 16α η C1 a6 α 16α η C1 a7 β 16α β C2 a8 η 2 4a9 α2 ρ α a3 − − − − , A7 = a6 α2 (1 − ρ) − 1−ρ (1 − ρ)3 ρp (1 − ρ)3 ρp (1 − ρ)3 ρp 1−ρ ρ2 β 2 a4 16α2 η 2 C1 a6 α2 16α2 η 2 C1 a7 β 2 16α2 β 2 C2 a8 η 2 4a10 β 2 A8 = a7 β 2 (1 − ρ) − − − − − , 3 3 3 1−ρ (1 − ρ) ρp (1 − ρ) ρp (1 − ρ) ρp 1−ρ ρ2 α2 a5 16α2 η 2 C1 a6 α2 16α2 η 2 C1 a7 β 2 4a11 η 2 A9 = a8 η 2 (1 − ρ) − 2η 2 ρ2 a2 − − − − , 3 3 1−ρ (1 − ρ) ρp (1 − ρ) ρp 1−ρ (1 − p + ρ) (a6 α2 + a7 β 2 )C1 + a8 η 2 C2 a9 (p + ρ − 1) ρβ 2 C2 a1 ρη 2 C1 a2 A10 = − − − ρ p p (1 − ρ)2 ρ2 p 2 2 2 2 2 2 2 4(α + β + η )C (a6 α + a7 β + a8 η ) − , (1 − ρ)3 p2 (1 − p + ρ) (a6 α2 + a7 β 2 )C1 + a8 η 2 C2 a10 (p + ρ − 1) ρβ 2 C2 a1 ρη 2 C1 a2 − − − A11 = ρ p p (1 − ρ)2 ρ2 p 2 2 2 2 2 2 2 4(α + β + η )C (a6 α + a7 β + a8 η ) − , (1 − ρ)3 p2 (1 − p + ρ)(a6 α2 + a7 β 2 )C1 4(α2 + β 2 + η 2 )C 2 (a6 α2 + a7 β 2 ) a11 (p + ρ − 1) ρη 2 C1 a2 − − − . A12 = 2 2 ρ p (1 − ρ) ρ p (1 − ρ)3 p2 A1 =
Here, constants such as LΦ , Lv and L1 are defined in (7). Set a1 = a2 = a6 = a7 = 1, a3 = a4 =
(1 − ρ)2 (1 − ρ)4 (1 − ρ)ρ2 10ρ2 , a5 = a8 = , a9 = a10 = , a11 = , 2 5ρ 1−ρ 320 4
and choose the stepsizes satisfying s r (1 − ρ)σ (1 − ρ)3 ρpσ a3 (1 − ρ)σ 1 a3 (1 − ρ)4 ρp a3 (1 − ρ)2 a3 (1 − ρ)σ β ≤ min , , , , , , , , 2 2 2 3C 128a10 Lf,1 128Lf,1 24Lf,1 Lf,1 576C 64a10 L2f,1 48L2f,1 s s r r a5 (1 − ρ)4 ρp 3(1 − ρ)4 ρp a9 (p + ρ − 1)p a9 (p + ρ − 1)(1 − ρ)2 ρp , , , , 2 80C 80 3ρ C 12(1 − p + ρ)C s s s a11 (p + ρ − 1)(1 − ρ)2 ρp a9 (p + ρ − 1)(1 − ρ)3 p2 a11 a8 (p + ρ − 1)(1 − ρ)3 p2 o , , , 6(1 − p + ρ)C 16ρ 8ρ s r n 1 3βρ(1 − ρ)3 ρp (1 − ρ)3 ρpσ (1 − ρ)σ a3 (1 − ρ)σ 1 a3 (1 − ρ)4 ρp η ≤ min , , , , , , , 3a8 C 80L2f,1 120a11 L2f,1 72L1 L1 128a8 C 640L1 2 s s r a3 (1 − ρ)2 a3 (1 − ρ)σ a5 σ(1 − ρ) 3(1 − ρ)4 ρp a9 (p + ρ − 1)p , , , , , 2 2 2 160a11 L1 72L1 45Lf,1 80 3ρ2 C s s s a9 (p + ρ − 1)(1 − ρ)2 ρp a11 (p + ρ − 1) a9 (p + ρ − 1)(1 − ρ)3 p2 o , , , 12(1 − p + ρ)a8 C 2ρ2 C 16ρ n 1
23
α ≤ min
r n 1 a3 (1 − ρ) a3 (1 − ρ)4 ρp 2a5 (1 − ρ) ησ 1 (1 − ρ)3 ρp 1 − ρ βσ , , , , , , , , , 2 2 2 3Lϕ 3C 24 24a9 20L1 15Lf,1 20L1 576C 25L2f,1 s r r a5 (1 − ρ)4 ρp (1 − ρ)η 3a8 (1 − ρ)4 ρp a9 (p + ρ − 1)(1 − ρ)2 ρp , √ , , , 80C 80 12(1 − p + ρ)C 5ρ s s s a11 (p + ρ − 1)(1 − ρ)2 ρp a9 (p + ρ − 1)(1 − ρ)3 p2 a11 a8 (p + ρ − 1)(1 − ρ)3 p2 o , , . 6(1 − p + ρ)C 16ρ 8ρ
(55)
Assume p + ρ > 1. Then, it is elementary to show from (55) that A1 , A2 , . . . , A12 are all nonnegative. Thus, (54) implies i h i α h E Vk+1 − Vk ≤ − E ∥∇Φ(x̄k )∥2 . 2 By telescoping the above inequality, we obtain h 1 XK−1 i 1 2V0 E ∥∇Φ(x̄k )∥2 ≤ =O . k=0 K αK K i h i hP n k k 2 The consensus error can also be established by E Vk+1 − Vk ≤ −A4 E n, which yields i=1 ∥xi − x̄ ∥ h 1 XK−1 Xn i 1 V0 E ∥xki − x̄k ∥2 ≤ =O . k=0 i=1 nK A4 K K Similarly, we can derive i h 1 XK−1 Xn 1 ∥yik − ȳ k ∥2 = O E k=0 i=1 nK K
and
h 1 XK−1 Xn i 1 E , ∥vik − v̄ k ∥2 = O k=0 i=1 nK K
which completes the proof of Theorem III.2. Remark A.16. The method of selecting the stepsizes is as follows: the subsequent m terms subtracted from the first term should each be no greater than 1/m times the value of the first term to ensure that all Ai are nonnegative. Then, the appropriate range for the stepsizes can be determined. Remark A.17. In our analysis, the condition p > 1 − ρ is required to ensure that A10 , A11 , A12 are nonnegative. In fact, this requirement is a flaw of the proof and not essential, which we now explain. In the proof of Lemma A.7, we used the Cauchy-Schwarz inequality 2⟨a, b⟩ ≤ t∥a∥2 + ∥b∥2 /t iwith t = ρ/(1 − ρ). This choice of t makes the condition (1 − p)/ρ < 1 necessary to bound the term hP n k+1 Ek − x̃k+1 ∥2 . If a different t > 0 is chosen, the condition p > 1 − ρ can then be replaced by p > 1/(1 + t). As t can be i i=1 ∥xi arbitrarily large, p > 0 can be arbitrarily small.
5) Proof of Theorem III.3.: Proof. From (54) and (55), we can establish the following inequality: n n i A hX i h i i A hX α h 5 4 ∥xki − x̄k ∥2 − ∥yik − ȳ k ∥2 , E Vk+1 − Vk ≤ − E ∥∇Φ(x̄k )∥2 − E E 2 n n i=1 i=1 h i P∞ P P n n k 2 1 which yields ∥xki − x̄k ∥2 + n1 i=1 ∥yik − ȳ k ∥2 ≤ V0 /C3 < ∞, where C3 = min{α/2, A4 , A5 }. k=0 E ∥∇Φ(x̄ )∥ + n Pn i=1k P k 2 k k 2 1 Therefore, the term ∥∇Φ(x̄ )∥ + n i=1 ∥xi − x̄k ∥2 + n1 n i=1 ∥yi − ȳ ∥ approaches 0 in expectation as k → ∞. The desired result follows from the Markov inequality.