Estimation Network Design framework for efficient distributed optimization
Mattia Bianchi Sergio Grammatico


=4

























 
 


    GNEPGNEPgeneralized Nash equilibrium problemNENENash equilibriumNEPNEPNash equilibrium problemGNEGNEgeneralized Nash equilibriumv-GNEv-GNEvariational GNEISSISSInput-to-state-stablePPAPPAproximal-point algorithmPPPAPPPApreconditioned PPAVIVIvariational inequalityGAEGAEgeneralized aggregative equilibriumv-GAEv-GAEvariational GAEKKTKKTKarush–Kuhn–TuckerFQNEFQNEfirmly quasinonexpansiveFNEFNEfirmly nonexpansiveADMMADMMalternating direction method of multipliersMPMMMPMMmodified proximal method of multipliersOPFOPFoptimal power flowOPFPOPFPoptimal power flow problemNUMNUMnetwork utility maximizationENDENDEstimation Network DesignDGDDGDdistributed gradient descentSTSTSteiner TreeFBFBforward-backward
     1
     argmin argmax det diag dimexp exp In  bnd int null rank range range sign sgn trace#1∇_ #1#1∂_#1∇^21 21 31 41 61 N1 n1 mlim_k→∞lim_N→∞#1#1#1#1#1 to 0pt#1#1^_#1
    fixgrazerdomranJNℋ
    αøωϵłλ
    ℝℕ𝒴𝒳ℱ𝒩ℐ𝒜ℬℱ2n̅x̂ŷł̂ẑv̂ø̂x̃ỹz̃ṽø̃x̅y̅ł̅z̅ø̅ x yøł z v ux̂ŷø̂ł̂ẑb̂ŝ ̂v̂x̃ỹø̃ł̃z̃b̃s̃ ̃ṽx̅y̅ø̅ł̅z̅b̅s̅ ̅v̅mylettersOMLztmcmmitmyletters"15@partk̨ ̨∈̨thmTheoremTheoremslemLemmaLemmascorCorollaryCorollariesclaimClaimClaimsaxiomAxiomAxiomsconjConjectureConjecturesfactFactFactshypoHypothesisHypothesesassumAssumptionAssumptionspropPropositionPropositionscritCriterionCriteriastandingStanding AssumptionStanding AssumptionsdefnDefinitionDefinitionsexmpExampleExamplesremRemarkRemarksprobProblemProblemsprinPrinciplePrinciplesalgAlgorithmAlgorithmsfigureFigureFiguresassumptionAssumptionAssumptionsthmlistiTheoremTheoremslemlistiLemmaLemmaasmlistiAssumptionAssumptiontheoremTheoremcorollaryCorollarylemmaLemmaclaimClaimaxiomAxiomconjectureConjecturefactFacthypothesisHypothesisassumptionAssumptionpropositionPropositioncriterionCriterionstandingStanding AssumptiondefinitionDefinitionexampleExampleremarkRemarkproblemProblemprinciplePrinciplealgAlgorithmthmlistenumerate1[thmlist]label=(thmlisti), ref=(thmlisti),noitemsep,topsep=0em,leftmargin=*thmlist2enumerate1[thmlist2]label=(thmlist2i), ref=(thmlist2i),topsep=0emasmlistenumerate1[asmlist]label=(asmlisti), ref=(asmlisti),noitemsep,topsep=0em,leftmargin=*[
    name=Problem,
    
    Refname=Problem,Problem,
    ]pbpbProblemProblems[pb]thmlistipb[
    name=Assumption,
    
    Refname=Assumption,Assumption,
    ]asmasmAssumptionAssumptions[assumption]thmlistiassumption[add refs]
    Iıi∈NMm∈MPp∈Pq∈QQ
    yyỹyŷy̅y_y_∥y_⊥y_∥ŷ_⊥y_∥λσσ̃szz̃zz̅ww̃gg̃y^⋆z^⋆Vvω
    _min_max
     FF̃RFf
    #1n_#1
    #1C_#1#1C_⊥^#1#1#2C_⊥,#1^ #2#1C̃_#1^⊥#1C̃_#1P#1Π_∥^#1#1Π_⊥^#1#1#2Π_∥,#2^#1#1#2Π_⊥,#2^#1#1#2Π_∥^#1,#2
    design𝕀I#1N_#1#1N_#1
    #1E^#1#1G^#1#1V^#1#1 W^#1Ł#1 L^#1#1 D^#1#1w^#1#̣1d^#1#1#2N ^#1(#2)#1#2N ^#1(#2)#1#2#3deg^#1_#2(#3)#1#2#3deg^#1_#2(#3)
    #1G^D_#1#1V^D_#1#1 W^D_#1#1 L^D_#1#1E^D_#1#1#2N ^D_#1(#2)#1#2N^D_#1(#2)#1#2deg^D_#1(#2)#1#2deg^D_#1(#2)#1q^D_#1
    #1#2G^#1,#2#1#2E^#1,#2#1#2G^#1#2#1#2E^#1#2#1#2G^D,#1_#2#1#2 W^D,#1_#2#1#2E^D,#1_#2
     W^DW̃^D L^DL̃^DV^DṼ^D
    
    #1#2E^#1,#2#1#2G^#1,#2#1#2V^#1,#2#1#2 W^#1,#2#1#2 L^#1,#2#1#2 D^#1,#2#1#2w^#1,#2#1#2d^#1,#2#1#2#3N ^#1,#3(#2)#1#2#3N ^#1,#3(#2)#1#2#3#4deg^#1_#2(#3)#1#2#3#4deg^#1_#2(#3)
    #1#2G^D,#2_#1#1#2V^D,#2_#1#1#2 W^D,#2_#1#1#2 L^D,#2_#1#1#2E^D,#2_#1#1#2#3N ^D,#3_#1(#2)#1#2#3N^D_#1(#2)#1#2#3deg^D,#3_#1(#2)#1#2#3deg^D,#3_#1(#2)#1#2q^D_#1,#2#1 L^D,#1#1G^D,λ_#1
    	Estimation Network Design framework for efficient distributed optimization
    
        Mattia Bianchi and  Sergio Grammatico
         
    	M. Bianchi is with the Automatic Control Laboratory (IfA), ETH Zürich, Switzerland (). S. Grammatico is with the Delft Center for Systems and Control (DCSC), TU Delft, The Netherlands (). This work is supported by NWO under research project OMEGA (613.001.702), by the ERC under research project COSMOS (802348) and by ETH Zürich funds.
    
        Received 28 February 2024 / Accepted 23 April 2024
    ==================================================================================================================================================================================================================================================================================================================================================================================================
    
    emptyempty
    
        Distributed decision problems features a group of agents that can only communicate over a peer-to-peer network, without a central memory. In applications such as network control and data ranking, each agent is only affected by a small portion of the decision vector: this sparsity is typically ignored in distributed algorithms, while it could be leveraged to improve efficiency and scalability. To address this issue, our recent paper <cit.> introduces END, a graph theoretical language for the analysis and design of distributed iterations.
        END algorithms can be tuned  to exploit the sparsity of specific problem instances, reducing communication overhead and minimizing redundancy, yet without requiring case-by-case convergence analysis. In this paper, we showcase the flexility of END in the context of distributed optimization. In particular, we study the sparsity-aware version of many established methods, including ADMM, AugDGM and Push-Sum DGD. Simulations on an estimation problem in sensor networks demonstrate that END algorithms can boost convergence speed and greatly reduce  the communication and memory  cost.
    
    
    
    
    
    
    § INTRODUCTION
    
     Modern big data optimization problems in network control and  machine learning 
     are typically partially separable<cit.>– i.e., the cost function is the sum of N individual costs, each depending only on a small portion of the overall optimization variable. This structure is widely exploited in parallel algorithms <cit.>– where multiple distinct processors share the computation cost, but having access to a common memory. Yet, this is not the case for distributed scenarios – where the processors (or agents) are constrained to communicate uniquely with some neighbors over a communication network. In fact, most distributed optimization methods entails the agents reaching consensus on the entire optimization vector <cit.>, even when each agent eventually only uses a few components of the solution, as in resource allocation and network control <cit.>. 
     This may result in prohibitive memory and communication requirements, and in poor scalability  if the decision vector grows with the network size. 
    
    Efficient solutions are known for partitioned problems, where the local cost functions (or constraints) only directly couple each agent to its  neighbors <cit.>.
    
    
    
    
    Notably, however, this requires that
    the communication graph matches the interference graph (describing the coupling among the agents in the cost or constraints),
    
    which is usually not the case for wireless and ad-hoc networks. 
    
    Remarkably, general partially-separable problems were addressed via distributed dual methods, by Mota et al. <cit.> and
    later by Alghunaim et al.  <cit.>: 
    in this approach, each component of the optimization variable  is estimated by a suitably chosen cluster of agents only. 
    
    Unfortunately, the dual formulation is only effective over undirected communication networks.
    Other works <cit.> rely on the concept of locality, which result in improved efficiency, but at the cost of accuracy; further, any structure beyond distance on the communication graph is ignored. 
    
    To deal with these challenges, in our recent work <cit.>, we  introduced END, a
    graph-theoretic language to describe   how the estimates of any variable of interest (e.g., optimization vector, dual multipliers, cost gradient)  are allocated and combined among the agents in a generic distributed algorithm. END allows assigning the estimate of each component of the variable of interest to a subset of the agents, 
    according to the sparsity structure of a given problem –  without resorting to a case-by-case convergence analysis. Leveraging the problem sparsity is especially convenient in repeated or time-varying problems (e.g., distributed estimation and model predictive control (MPC) <cit.>), where the one time-cost of efficiently assigning the estimates yields improved (iterative) online performance. 
    Although <cit.>   focuses on distributed Nash equilibrium problems, the END framework is flexible and applicable to virtually any distributed decision problem.
    
    Contributions: In this paper, we apply and tailor the END framework <cit.> to distributed optimization problems, thus  unifying and generalizing several recent approaches.  
    For the case of dual algorithms, our setup retrieves the formulation in <cit.> (see Proposition <ref>). Here we present a novel sparsity-aware ADMM, but one can obtain the END version of virtually any dual algorithm (Section <ref>).  Further, compared to <cit.>, our framework has broader applicability:
    
      (i)it can be used for primal methods. To illustrate, we present the END version of the ABC method <cit.>,  encompassing many established algorithms.  As an example, we derive a gradient-tracking iteration where each agent only needs to estimate a fraction of the cost gradient – the END counterpart of AugDGM <cit.> (Section <ref>);
        
      (ii)it works on directed graphs. Specifically, we present the sparsity-aware version of the Push-Sum DGD algorithm <cit.>, that is guaranteed to converge over time-varying and column stochastic graphs (Section <ref>).
    
    It will be clear from our arguments that,  thanks to our powerful stacked notation, the analysis of END algorithms presents  little complication compared to their sparsity-unaware counterparts.  Nonetheless, the impact in terms of flexibility and performance is remarkable. We illustrate numerically this point on an estimation problem for wireless sensor network, where we observe that END can decrease the communication cost by more than 90% (Section <ref>).
    
    
    
    
     
     
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
     §.§ Background and notation
    
    
      §.§.§ Basic notation
    ℕ is the set of natural numbers, including 0.
     (_≥ 0) is the set of (nonnegative) real numbers.
    
    _q∈^q (_q∈^q) is a vector with all elements equal to 0 (1); I_q∈^q× q is an identity matrix; the subscripts may be omitted when there is no ambiguity. e_i denotes a vector of appropriate dimension with i-th element equal to 1 and all other elements equal to 0.
    For  a matrix A  ∈^p × q, [ A]_i,j is the element on  row i and column j; ( A){x∈^q | Ax=_n} and ( A){v∈^p | v= Ax, x∈^q }.
    If A=  A^⊤∈^q× q, _min( A)=:_1( A)≤…≤_q( A)=:_max( A) denote its eigenvalues.
    
    ( A_1,…, A_N) is the block diagonal matrix with A_1,…, A_N on its diagonal. Given N vectors x_1, …, x_N,  (x_1,…,x_N )   [ x_1^⊤…  x_N^⊤ ]^⊤. ⊗ denotes the Kronecker product.  Given a positive definite matrix ^q× q∋ Q ≻ 0,  ⟨ x | y ⟩ _Q=x^⊤ Q y os the  Q-weighted inner product,  ·_ Q is the associated norm; we omit the subscripts if Q = 𝕀.
    Given a function ψ: ^q →∪{∞}, its set-valued subdifferential operator is denoted by
    ∂ψ: ^q ⇉^q:x↦{ v ∈^q |ψ(z) ≥ψ(x) + ⟨ v | z-x ⟩ , ∀  z ∈^q }.
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
      §.§.§ Graph theory
    
    A (directed) graph =(,)
    consists of a nonempty set of vertices (or nodes) ={1,2,…, V } and a set of edges ⊆×. We denote by v{ u| (u,v) ∈} and v{ u | (v,u) ∈} the set of in-neighbors (or simply neighbors)  and out-neighbors of vertex v ∈, respectively.
    A path  from v_1∈ to  v_N∈ of length T is a sequence of vertices (v_1,v_2,…,v_T) such that (v_t,v_t+1 )∈ for all t=1,…, T-1.  is strongly connected if there exist a path from u to v, for all u,v ∈; in case  is undirected, namely if (u,v) ∈ whenever (v,u) ∈, we simply say that  is connected. The restriction of the  graph  to a set of vertices A⊆ is defined as |_A ( A, ∩ (A×A)).   We also write =(A, B,) to highlight that G is bipartite, namely = A∪B and ⊆A×B.
    We may associate to   a weight matrix ∈^V× V compliant with , namely _u,v[]_u,v>0 if (v,u)∈, _u,v=0 otherwise.
    
     is unweighted if _u,v=1 if (v,u) ∈. 
    Given two graphs A=(A,A) and B=(B,B), we write  A⊆B if A is a subgraph of B,  if A⊆B and A⊆B; we define A⋃B  (A∪B, A∪B).
    A
    time-varying graph (k)_, k=(,k) is Q-strongly connected if 
    
    ⋃_t=kQ^(k+1)Q-1t  is strongly connected for all $̨. 
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    § END FOR DISTRIBUTED OPTIMIZATION 
    
    
    
    We first recall the general
    END
    framework <cit.>, 
    
    
    
    
    that describes the information structure in any distributed algorithm. It is characterized by:
    
      *   a set of agents{ 1,2,…,N };
    	
    	
      *  a given (directed) communication graphC=(,C), over which the agents can exchange information:  agent i can receive data from agent j if and only if
    
    	j∈Ci;
    	
    	
      *  a variable of interesty ∈^ y, partitioned as y=((y_p)_p∈),   {1,…,P}, y_p∈^y_p;
    	
    	
      *  a given  interference graphI=(,,I),  I⊆×, specifying  which components of y  are indispensable for each agent:  p∈Ii means that agent i needs (an estimate of) y_p to perform some essential local computation;[For ease of notation, assume Ip≠∅ for all .]
      *   a bipartite estimate graphE=(,,E), E⊆×. Since agents might be unable to access y, each agent estimates some of the components y_p's, as specified by the estimate graph: agent i keeps an estimate y_i,p∈^y_p of y_p if and only if p∈Ei;
        
      * P directed design  graphs{p}_,  p=(Ep,p). p  describes how the agents that estimate  y_p  exchange their estimates: agent i can receive y_j,p from agent j if and only if i∈pj;
    
    
    
    
     Specifically, in this paper, we apply the END framework to the distributed optimization problems
    
        min_y∈^y ∑_ı f_i(y),
    
     wheref_i:^y→is a private cost function of agenti. 
    We choose the variable of interest in the END framework to coincide with the optimization variable[Except for Section <ref>, where we instead select the dual variable as variable of interest; see also <cit.> for different possible choices (e.g., aggregative values) in variational problems.]. Hence, we partition the optimization variable asy= ((y_p)_).
    
    The common approach <cit.> to  solve (<ref>) over a communication networkCis to  assign to each agentıa copy_i ((y_i,p)_) ∈^yof the whole decision variable 
    
    	and to let the agents exchange their estimates with every neighbor overC; in END notation, we write this as[In the following, we refer to (<ref>) as the  “standard” choice, as it is the most widely studied scenario. With c = p we also imply C = p.]
        E =×,     p =C  (∀).
    
    Yet, in  several applications, like network control and data ranking <cit.>,
    each cost functionf_idepends only on some of the components ofy, as specified by an interference graphI:f_idepends ony_pif and only ifp∈Ii⊆. With some abuse of notation, we highlight this fact by writing 
    
        f_i(y)=f_i ((y_p)_p∈Ii) .
    
    Clearly, the standard choice (<ref>) for the graphsEand{p}_does not take advantage of the  structure in (<ref>). In fact, agentionly needs(y_p)_p∈Iito evaluate (the gradient of) its local costf_i; storing a copy of the whole vectorycould be unnecessary and  inefficient – especially ifIis sparse andyis large.
     
    
     §.§ Problem-dependent design,  unified analysis
    
    
    From an algorithm design perspective, the graphsCandIshall be considered  fixed as part of the problem formulation. In contrast, the graphsEand{p}_are design choices, although with some constraints.
    
    E and p are chosen such that I⊆E and  p⊆C  for all .  □
    
    In particular,E⊆Imeans that each agent estimates at least the components ofywhich are indispensable for local computation. Moreover, since the estimates are exchanged overpand communication can only happen overC, it must hold thatp⊆C. 
    In addition, we will always need some level of connectedness for each graphp, to ensure that the agents can reach consensus on the estimates ofy_p, as for instance in the following condition. 
    
    
        For each , p is undirected and connected. □
    
    DesigningEand{p}_to satisfy <ref> and <ref> is not difficult ifCis itself undirected and connected: one trivial choice is (<ref>). Yet, one wishes to also consider efficiency specifications (e.g., in terms of memory allocation, communication or bandwidth) by imposing extra (soft) constraints onEand{p}_. We present a simple instance  in <ref> and refer to <cit.> for  more examples. Such an optimal design is in general computationally expensive. Nonetheless, the performance advantages in terms of algorithm execution can be well worth the (one-time) cost of an efficient algorithm design, especially in 
    repeated problems  <cit.> (where the same distributed problem is solved multiple times for different values of some parameters/measurements). 
    
    Further, while this design procedure is very problem and goal dependent,  it does not affect the analysis of END algorithms. By simply postulating some connectedness property, as in <ref>, we can unify the convergence analysis of standard algorithms (that use (<ref>)) with that of methods specifically devised for problems with unique sparsity. 
    
    
    
     §.§ END Notation
    
    
    We next introduce the stacked END notation, crucial in our analysis.
    For all, letp| Ep|be the number of copies ofy_p. Recalling that that_i,pis the estimate of_pkept by agenti, we define:
    
        _p     ( ( y_i,p )_i∈Ep )∈^p n_y_p,   ∀;
        	
           ( ( y_p )_ ) ∈^,
    
    where∑_py_p.  Note that_pcollects all the copies ofy_pkept by different agents. We denote
    
        ( ( p⊗I_y_p)_ ),
    
    wherepis the weight matrix ofp.  Let
    
        p   {_p ∈^N_p y_p|_p = _N_p⊗ v, v∈^y_p},
    
    be the consensus space for_p (where all the estimates of_pare equal);∏_pbe the overall consensus space;
    
        ()(( _N_p⊗_p )_ ).
    
    For each, for eachi∈Ep, we denote by 
        i_p∑_j∈Ep,   j≤ i 1
     
    the  position ofiin the ordered set of nodesEp. For alli ∈Ep, we denote by_i,p∈^y_p×N_p y_pthe matrix that selects_i,pfrom_p,_i,p= _i,p_p.
    
    Sometimes it is useful to define agent-wise quantities, indicated with a tilde. Let 
    
        _i  ( ( _i,p )_p∈Ei ), ( ( _i )_ı ) ∈^,
    
    where_icollects all the estimates kept by agenti.
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    § DISTRIBUTED OPTIMIZATION ALGORITHMS
    
    
    In this section,  we leverage the END framework to extend several distributed optimization algorithms by exploiting partial coupling. We recall the cost-coupled problem in (<ref>):
    
        min_ y∈^y f(y) ∑_ı f_i( (y_p)_p∈Ii ),
    
    wheref_iis a private cost function of agenti, and  we choose the optimization variabley = ( (y_p)_)as the variable of interest in the END; with some usual overloading, we write
    
        f_i(y) = f_i(  (y_p)_p∈Ei  ) = f_i ( (y_p)_p∈Ii  ).
    
    Let Y^⋆be the solution set of (<ref>), assumed to be nonempty. 
    
    
    
    
     §.§ END dual methods
    
    Under <ref>, we  can recast (<ref>) by introducing local estimates and consensus constraints.The   following redormulation is not novel, and in fact it was employed for the dual methods in <cit.>. 
    
    	Let <ref> hold. Then, problem (<ref>) is equivalent to:
    
    		
        {min_∈^    ∑_ı f_i( _i ) = f_i((_i,p)_p∈Ei)
        			
        s.t.    _i,p=_j,p  ∀,∀ (i,j)∈p. 
        			.
    
    	□
    
    Ifp=Cfor all, then (<ref>) reverts to the formulation used in standard dual methods <cit.>: these algorithms require each agent to store a copy of the whole optimization vector.  Instead, choosing a sparseEcan conveniently reduces the number  constraints in  (<ref>).
    Regardless, due to its structure ( separable costs and coupling constraints compliant withp, hence with the communication graph), the problem in  (<ref>) can be immediately  solved via several  established Lagrangian-based algorithms (provided that the functionsf_i's are sufficiently well-behaved). In practice, this allows one to extend most (virtually all) the existing dual methods to the END framework. 
    
    [END ADMM]
    	Let  <ref> hold, and assume that f_i is proper closed convex, for all ı. Applying the ADMM  in <cit.> to  (<ref>)[After decoupling the constraints in  (<ref>) by introducing auxiliary bridge variables as {_i,p=h_(i,j),p, h_(i,j),p=h_(j,i),p, h_(j,i),p=_j,p};  the approach is standard and we refer to <cit.> for a complete derivation.] results in the iteration
    	
        _i ^k+1    =_i [t]
        			{
        			f_i (_i)   +  ∑_p∈Ei∑_j∈pi(
        			_i,p^2 
        			
        
        			-  ⟨ z_i,j,p,   _i,p⟩) }
        
        			z_i,j,p^k+1   =  (1-α )z_i,j,p^k -α z_j,i,p^k +2α_j,p^k+1,
    
    	where z_i,j,p  is an auxiliary variable kept by agent i,  for each ı, p∈Ei, j∈pi. Then, for any α∈ (0,1),  _i,p converges to y_p^⋆, where y^⋆=((y_p^⋆)_) is a solution of (<ref>), for all ı and p∈Ei.
    	Note that performing the update (<ref>) requires agent i to receive data from its neighbor j ∈pi (while (<ref>) requires no communication). 
    	If p=C for all , then the method retrieves the standard ADMM for consensus optimization <cit.>. Yet, in general (<ref>)  requires the agents to store and exchange  less (auxiliary) variables.
    	□
    While 
    <ref> would hold even if the graphsp's are only strongly connected, distributed algorithms to efficiently solve (<ref>) typically require undirected communication. 
    
    
    
    
     §.§ END ABC  algorithm
    
    In this subsection, we propose an END version of the ABC algorithm, recently developed in <cit.>. For  differentiable costsf_i's, let us consider the iteration:(∀ı)(∀ p ∈Ei)_i,p^k+1   = - _i,p^k+
        		 ∑_j ∈Ep [ A_p]_i_p,j_p_j,p^k - γ  [  B_p]_i_p,j_py_p  f_j(_j^k)
        		
        _i,p^k+1    = _i,p^k +    ∑_j ∈Ep [ C_p]_i_p,j_p_j,p^k+1,
    
    where_i,p∈^y_pis a local variable kept by agenti; for all, A_p,   B_p,  C_pare matrices in^N_p × N_p;γ>0is a step size; and we recall the notation in (<ref>). Note that if the matrices A_p,  B_p,  C_p's are compliant with the corresponding graphsp's ( A_p =  B_p =  C_p = p), then the iteration (<ref>) is distributed. We can rewrite (<ref>)  in stacked form as
    
        ^k+1   =    A	^k - γ B   (^k) - ^k
        ^k+1    = ^k +   C  ^k+1,
    
    where A ((  A_p⊗𝕀_y_p  )_ ), B ((  B_p⊗𝕀_y_p  )_  ), C ((  C_p⊗𝕀 _y_p  )_ )belong to^×, ( ( _p )_ )with_p  ((_i,p )_i∈Ep), and()∑_ı f_i (_i). Ifp = Cfor allp, and A_p, B_p, C_pare independent ofp, then (<ref>) retrieves the ABC algorithm <cit.>.
    
    
    We next charachterize the asymptotic behavior of (<ref>) for appropriately chosen A, B, C(all the proofs are in appendix). We recall the notation in (<ref>)-(<ref>).
    
        Let D( ( D_p⊗𝕀_y_p
    	 )_ ), for some  { D_p ∈^N_p × N_p}_. Assume that   f_i is L-smooth and convex for each ı, and that:
    	
    		
    		
      * A= B  D and B≽ 0, D≻ 0;
    		
      * (∀∈)D  =, B  =;
    		
      * C≽ 0,  ( C)=;
    		
      * B and C commute: B  C = C  B;
    		
      * 𝕀 -1/2 C -√( B) D √( B)≽ 0.
    		
    	
    	Let y^⋆∈ Y ^ ⋆, ^⋆ (y^⋆),
    	and consider the  merit function
    	
        𝔐 ()max{( ^⋆ ) , | ( ) - (^⋆) |  }.
    
    	Then, for any ^0∈^, ^0 = _, γ∈  ( (D) /L), the sequence (^k)_$̨ generated by (<ref>) satisfies
    	
        𝔐( ^k ) ≤O (1/k),
    
    	for all$̨, where ^k 1/k∑_t=1 ^k ^t.
    	□
    
    It is shown in <cit.> that many celebrated schemes for consensus optimization can be retrieved as particular instances of the ABC algorithm, by suitably choosing  the matrices A, B, C<cit.>: 
    EXTRA <cit.>,
      NEXT <cit.>,
     DIGing <cit.>,
     NIDS <cit.>,
    and others. 
     <ref> allows the extension of each of these methods to the  END framework. We only discuss an example below; for the other schemes, the analysis can be carried out analogously, see also <cit.>.
    
    [END AugDGM]
    	The following gradient-tracking algorithm is the END version of <cit.>: (∀ı)(p∈Ei)
        _i,p^k+1   = ∑_j ∈p i
        				[p]_i_p,j_p  ( _j,p^k-γ_j,p^k)
        				
        
        	    	_i,p^k+1    = ∑_j ∈p i
        				[p]_i_p,j_p  (_j,p^k +   y_p f_j (^k+1) -  y_p f_j (^k)),
    
    	or, in stacked form,
    		
        ^k+1   =   (^k - γ^k)
        		
        
        		^k+1    =   (^k +    (^k+1) -   (^k) );
    
    	we impose (0) =, (0) =  (^0). Here, _i,p represents an estimate of y_p∑_j ∈I f_j (y)/N_p kept by agent i. Note that  agent i only estimates and exchanges the components of the cost gradient (and of the optimization variable) specified by Ei, instead of the whole vector as in <cit.>– the two algorithms coincide only if  p=C for all .
    	By eliminating the  variable in (<ref>), we obtain 
    	
        ^k+2   =  2^k+1 -  ( )^2  ^k
            
        			- γ( )^2  
        
        			( (^k+1) -   (^k)) .
    
    	Instead, eliminating  from (<ref>) we get
    	
        ^k+2   =  (𝕀- C+ A ) ^k+1 -  A  ^k
            - γ B  ( (^k+1) -   (^k)) .
    
    	which retrieves  (<ref>)  for A= B=()
    	^2, C=(𝕀- )^2.[In fact, the sequence (^k) generated by (<ref>) coincide with that generated by (<ref>)
        for the given initialization.] This choice satisfies the conditions in <ref>, with D=𝕀, under  <ref> and doubly stochasticity.[Note that the properties of p's easily translate to  due to the block structure in (<ref>). For instance, under the stated conditions, clearly (I -p)^2 = (_N_p) and (I -)^2 =. ]
    		Let <ref> hold; assume that p_N_p=_N_p, p=p^⊤, for all , and that f_i is L-smooth and convex, for all ı. Then, for any γ∈ (0,1/L) the rate (<ref>) holds for (<ref>).  □<ref> requires a recovery procedure (i.e., (<ref>) holds for the running average only), as e.g. in <cit.>, but pointwise convergence could be shown for several special cases of (<ref>), see e.g. <cit.>. 
    We  note  that  <ref> enhances customizability with respect to  <cit.>,   even in the standard scenario (<ref>) (the sparsity-oblivious case), by allowing for non-identical blocks A_p's, B_p's, C_p's – corresponding to integrating different methods for the components ofy.
    
    
    
    
    
     §.§ END Push-sum DGD
    
    Techniques to solve optimization problems over switching or directed graphs also find their counterpart in the END framework. As an example, here we generalize the push-sum subgradient algorithm in <cit.>.
    
    Let the agents  communicate over a time-varying network(Ck)_,Ck =(,Ck). Given a fixed estimate graphE⊇I, for eachwe consider a time-dependent design graph(kp)_,kp = (Ep,kp) ⊆Ck(note that the set of nodes is fixed inkp). 
    For allıand p ∈Ei, agentiperforms the following updates:
    
        q_i,p^k+1    = ∑ _j ∈Ep  [ kp ]_i_p,j_p q_j,p ^k
        		
        _i,p^k+1   ∑ _j ∈Ep  [ kp ]_i_p,j_p_j,p ^k
        		
        _i,p ^k+1   ∈y_pf_i ( _i^k+1) ,    _i,p^k+1_i,p^k+1/q_i,p^k+1
        _i,p^k+1    = _i,p^k+1 - γ^k_i,p ^k+1,
    
    initialized at_i,p^0∈^n_y_p,q_i,p^0=1. 
    With respect to <cit.>,  agentikeeps  one scalarq_i,pfor eachp∈Ei(instead of one overall), but does not store and exchange  the variables_i,p∈^y_pforp ∉Ei.
    
     
       For all $̨ and, it holds that:
    
      (i) Self-loops:  for all i∈Ep, (i,i) ∈kp;
    	
      (ii) Column-stochasticity:  _N_p^⊤kp = _N_p^⊤;
    	
      (iii) Finite weights:  [kp]_i_p,j_p≥ν >0,  ∀  (i,j) ∈kp.
    	 □
        There exists an integer Q>0 such that, for all , (kp)_ is Q-strongly connected.  □[Choosing time-varying design graphs]  Assume 
    	C⊆⋃_t=kQ^(k+1)Q-1Ck, for all $̨ and some strongly connected graphC.
    	Choose some graphs(p)_that satisfy <ref> and such that eachpis strongly connected. Then, <ref>  holds by settihgkp=p⋂Ck, for alland all$̨. □
     Let <ref> hold. Assume that, for all ı, f_i is  convex and there is L>0 such that g_i ≤ L, for all y ∈^y and  g_i ∈y f_i (y). Let (γ^k)_ be a positive non-increasing sequence such that ∑_k=0^∞γ^k =∞, ∑_k=0^∞ (γ^k)^2<∞. Then, the sequence (^k)_$̨ generated by (<ref>) converges to(y^⋆), for somey^⋆∈Y^⋆.□§.§ Constraint-coupled distributed optimization
    
    
    Finally, we study  a different,  constraint-coupled problem:
    [left=]alignmin_ x_i ∈^ x_i, ı    ∑_ı f_i(  x_i ) 
    s.t.       ∑_i ∈Ip A_p ,  i  x_i  - a_p, i = ,   ∀
    		
    	
    for a given interference graphI = ( P,  I,I), wheref_iand{ A_p ,  i∈^y_p×x_i,  a_p,i∈^y_p}_  p ∈Iiare private data kept by agenti; and the constraints (<ref>) are  not compliant with the communication graphC, namelyIp⊈Cifor anyi. Differently from what we did with the cost-coupled problem in (<ref>), here we choose as the variable of interest the dual variable associated with the constraints in (<ref>),y = ((y_p)_)∈^y.
    Typical distributed methods to solve (<ref>) require each agent to store a copy of the entire dual variable  (and possibly of  other variables in^y, e.g., an estimate of the constraint violation) <cit.>. 
    
    END primal-dual or dual methods can improve efficiency by exploiting the sparsity ofI.
     For instance, (a simplified version of) the algorithm in <cit.> can be directly used to solve (<ref>). 
     
     Alternatively, let us consider the dual of  (<ref>):
    
        max_ y ∈^ y    ∑_ıφ_i (  (y_p)_p∈Ii ),φ_i (y) min_x_i ∈^x_i  f_i(x_i) + ∑_ p ∈Ii⟨ y_p  ,   A_p,i x_i -a_p,i⟩; note that (<ref>) is  in the form (<ref>). In fact, (<ref>) was solved in  <cit.> via the reformulation (<ref>); this approach has the disadvantage of requiring undirected communication. Nonetheless, (<ref>) can also be solved over directed (time-varying) networks,  via the iteration in (<ref>).[If each f_i is convex with compact domain, where the subgradients of the local dual function φ_i can be computed as _i,p^k =  A_p,ix_i^⋆(^k_i) -a_p,i, with x_i^⋆ (_i) ∈_x_i ∈^x_i  f_i(x_i) + ∑_ p ∈Ii⟨_i,p  ,   A_p,i x_i -a_p,i⟩.]
    
    
    § ILLUSTRATIVE APPLICATION
    
    In this section we study numerically a  regression problem with sparse measurements <cit.>, arising from distributed estimation in wireless and ad-hoc sensor networks. 
    Let us consider some sensors{1,2,…,N} Iand some sources{1,2,…, P} P, spatially distributed on a plane in the square[0,1] × [0,1], as illustrated in <ref>. Each sourcepemits a signaly̅_p ∈, sensed by all the sensors in a radiusr_s >0; in turn, each sensorimeasures
    
        h_i  H_i   ((y̅_p)_p ∈Ii) + w_i,
    
     whereh_i ∈^h_i, H_iis a known output matrix,w_iis the measurement noise.  Sensorican send information to all the peers in a radiusr_c^i(e.g., proportional to the sensor specific power); this induces a directed communication networkC = ( I, C)among the sensors, which we assume to be strongly connected.
    
    
    
      §.§.§ Linear regression
    
    In our first simulation, the sensors' goal is to collaboratively solve the least square problem
    
        min_y ∈^P ∑_ı h_i -  H_i  ((y_p)_p∈Ii) ^2,
     
    whereIiis the set of sources positioned less thanr_saway from sensori.
    Problem (<ref>) is  in the form  (<ref>). We seek a solution via algorithm (<ref>) (with fixed communication graph), comparing the performance for two choices of the design graphs:
    
      * Standard: p's are chosen as in (<ref>): with this choice, (<ref>) boils down to the standard Push-sum DGD<cit.>.
        
      * Customized: each p is designed to exploit the sparsity in (<ref>). In particular, we  aim at optimizing the memory allocation for the estimates, by minimizing the number of nodes in p, provided that p must be strongly connected (and <ref> must be satisfied). Designing such a p  corresponds to (approximately) solving a Strongly Connected Steiner Subgraph Problem <cit.> (where p is a subgraph of  C)[We use all the available edges, i.e., p = C|_Ep.].  
        
    
    
    We setN = 100,P=20,  and randomly  generate sensor/sources positions as in <ref>.
    We chooser_s = 0.2, and draw eachr^i_cuniformly in[ r_c^min,r_c^min+0.1] .
    For allı,  we fixh_i = 10, we generate H_iby first uniformly drawing entries in[0,1]and then normalizing the rows to unitary norm, we  draw each element ofw_ifrom an unbiased normal distribution with variance0.1; each signaly̅_pis uniformly randomly chosen in[0,1]; the step size is set asγ^k = k^-0.51in (<ref>).[Although the bounded subgradient assumption in <ref> fails, boundedness of the sequences generated by (<ref>), and hence convergence, can be established based on coercivity of the cost function.]  The advancement is evaluated via the merit function𝔙  ()max{( (1/N_p I)_)( ^⋆ ) , | ( ) -(^⋆) |  }, where^⋆ = (y^⋆)andy^⋆solves (<ref>).
    <ref> shows the results for different values ofr_c^min. Forr_c^min = 0.1, the customized method is  15 times faster then the standard one. 
    Increasingr_c^minonly marginally reduces the  per-iteration communication cost of the customized method. In fact, already forr_c^min = 0.25, the graphC|_Ipis strongly connected for all, soE = Ican be chosen (in other terms, each agent only estimates and exchanges the components ofythat directly affect its local cost, while it also has to estimate other components for smallerr_c^min). 
    
    
    In this situation, the customized method achieves a reduction of the communication cost (where sending a variable to all the neighbors onChas a cost of1, in a broadcast fashion) of over99.9 %.
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
      §.§.§ LASSO
     
    
    Next, we assume that only30 %of the sources emits a signal at a given instant (the vectory̅is sparse). The sensors collaboratively solve the following problem, regularized to promote sparsity,
    
        min_y ∈^P y_1+ ∑_ı h_i -  H_i  (y_p)_p∈Ii^2,
    
    where·_1is theℓ_1norm. 
    By definingf_i((y_p)_p ∈Ii) =  h_i -  H_i  ((y_p)_p ∈Ii) ^2+  ∑_p ∈Ii1/|Ip||y_p|, we retrieve the form (<ref>).
    We setN = 10,P=20,r_c^min = 0.1,h_i =1for alli, generate random positions for the sensors and sources,  and choose the other parameters as above, for both the standard and customized methods. <ref> compares the results for different values ofr_s. 
    For largerr_s, the interference graphIis denser, and the gap between customized and standard method decreases: in fact, forr_s =0.8the two algorithms coincide, asIis complete. Nonetheless, whenIis sparse, the customized algorithm saves up to99%of the communication cost. 
    
    In conclusion, while requiring some initial computational  effort to choose the design graphsp,
    the sparsity-aware method results in substantial efficiency
    improvement –  especially if the estimation problem is solved
    repeatedly, e.g., each time new signals are received from the sources. 
    
    
    
    
    § CONCLUSION
    
    
    We have shown that the END framework <cit.> can be applied to a variety of distributed optimization problems, to enhance efficiency by accounting for the intrinsic sparsity in the agents coupling. Besides revisiting dual methods, we derived the END (i.e., sparsity aware) version of the very general ABC method and of  Push-sum DGD; and we showed how to efficiently tackle constraint-coupled problems with sparse constraints, even over directed graphs. Our simulations show that END algorithms can substantially reduce the computational and communication cost, while introducing little complication in the convergence proof with respect to their sparsity-unaware counterparts. 
    
    As sparsity-aware END algorithms require some initial design effort for the allocation of the estimates, their use is particularly recommended for problems with special structure <cit.>, or repeated/time-varying problems like distributed estimation and MPC. 
    Future work should focus on computationally efficient and
    distributed methods to perform the allocation of the estimates online, thus avoiding the need for any a priori
    design.
    
    
    
    
     §.§ Proof of <ref>
    
    We adapt the proof of <cit.>. We note that ^0=_∈( B); by the conditions <ref> and <ref>, the update in (<ref>), and an induction argument, we have  ^k,^k∈( B), for all k≥ 1. Hence, we  rewrite (<ref>) as
    
        ^k     =  B^k,   ^k=γ B^k
        ^k+1    =  D ^k -γ ((^k) +^k )
        	
        ^k+1    = ^k+1/γ  C^k+1
    
    for all k≥ 1. Let Φ(,) ()+⟨,⟩; the form in (<ref>) can be exploited to prove the following lemma.
    
    	Let (^k,^k,^k) be a sequence generated by (<ref>).
    	Then, for all  ∈, ∈, it holds that:
    	
        Φ(^k+1,)  - Φ(,) ≤1/2k h (,),
    
    	where
    	h (,)1/γ^0 -^2_ D+ γ B-/^2
    	and
    	min{  (_2 (  C_p))_}.
    	□
    	The proof is analogous to that of <cit.>, and omitted here. Note  that <cit.> uses a matrix notation (i.e., ∈^I × n), while we need a stacked notation (as the vectors (_i)_ı are not homogeneous in size). Nonetheless, (<ref>) matches <cit.>, which allows us to repeat all the steps in  <cit.> (with the only precaution of replacing
    	J, span (_m), _2 ( C) in <cit.> 	with , , ).
    
    For all ∈ (so that ⟨, ^⋆⟩ = 0), setting =^⋆ in <ref>, together with the definition of Φ, yields
    (^k) - () + ⟨^k, ⟩≤1/2k  h ( ,  ).
    Further choosing = 2 ^k /^k, with -(), leads to
    
        (^k) - () + 2 ^k≤1/2k  h ( , 2  ).
    
    By convexity and since ^⋆∈ (by  optimality conditions), it holds that f(^k)-f() ≥ -⟨^k-,⟩ = -⟨^k,⟩≥ - ^k; the latter inequality and  (<ref>) imply 𝔐 (^k) ≤1/2k h ( , 2  ). ▪
    
    
     §.§ Proof of <ref>
    
    Note that, for each , (<ref>) is the standard perturbed push-sum protocol <cit.>, with perturbation term -γ^k ^k+1_i,p. Therefore, since ^k+1_i,p is uniformly bounded by assumption and by the choice of  (γ^k)_, we can apply  <cit.> to infer that, for all ı, p∈Ei
    
        lim_k→∞_i,p^k- ^k_p   =0,  
        ∑_k=0^∞γ^k _i,p^k-  ^k_p  = 0,
    
    where _p^k 1/N_p∑_i ∈Ep_i,p^k ∈^y_p, for all $̨.
    Let us also define^k( ( ^k_p )_ ) ∈^y. By (<ref>) and  <ref>(ii), it follows that
    
        ^k+1_p = ^k_p - γ^k 1/N_p∑_i ∈Ep_i,p ^k+1.
    
    We next show thatlim_k→∞^k = y^⋆∈Y^⋆; then, the theorem follows by (<ref>).
    The main complication with respect to the proof of <cit.> is that we need a modification of  <cit.> to cope with the non-homogeneity of the estimates.
    
    	For all y^⋆∈Y^⋆, for all $̨, it holds that
    	
        [b]
        			^k+1 -^⋆^2_D   ≤^k -^⋆^2_ D -2γ^k(f( ^k) -f(y^⋆) )
        			
            +  4L γ^k ∑_ı∑_ p∈Ei^k_p - _i,p^k+1
            + (γ^k)^2 N L^2,
    
    	where D (( N_p 𝕀_n_p)_ ).□By (<ref>), we have
    	
        [b]
        			^k+1 -^⋆^2_ D    =  ^k -^⋆^2_ D
           
        			- 2 γ^k∑_⟨^k_p -_p^⋆ , ∑_i ∈Ep_i,p ^k+1⟩
           
        			+ (γ^k)^2  ∑_1/N_p∑_i ∈Ep_i,p ^k+1^2.
    
    	The third addend on the right-hand side of (<ref>) is bounded above by (γ^k)^2 NL^2. For the second addend, we have
    	
        ∑_⟨^k_p -_p^⋆ , ∑_i ∈Ep_i,p ^k+1⟩
            = ∑_ı∑_p ∈Ei⟨ (^k_p- _i,p^k+1)+(_i,p^k+1- ^⋆_p),    _i,p^k+1⟩
           (a)≥∑_ı   -L ( (^k_p)_p∈Ei)- _i^k+1   + f_i(_i^k+1)- f_i(y^⋆)
        			
           (b)≥∑_ı   -2L ( (^k_p)_p∈Ei)- _i^k+1   + f_i(^k+1)- f_i(y^⋆),
    
    	where in (a) we used that _i^k+1∈ _i f_i(_i^k+1) and convexity of f_i, and (b) follows by adding and subtracting (inside the sum) f_i ( (^k+1_p )_p∈Ei) = f_i(^k+1) and by L-Lipschitz continuity of f_i. The result follows by substituting the bound back into (<ref>).
    
    We finally note that, due to (<ref>) and  the choice of(γ_k)_$̨,   the inequality in <ref> satisfies all the conditions of <cit.>, in the norm ·_ D;  hence we can conclude that
    ^k → y^⋆, for some ^⋆∈Y^⋆.  ▪
    IEEEtran
