We study distributed multi-agent large-scale optimization problems, wherein the cost function is composed of a smooth possibly nonconvex sum-utility plus a DC (Difference-of-Convex) regularizer. We consider the scenario where the dimension of the optimization variables is so large that optimizing and/or transmitting the entire set of variables could cause unaffordable computation and communication overhead. To address this issue, we propose the first distributed algorithm whereby agents optimize and communicate only a portion of their local variables. The scheme hinges on successive convex approximation (SCA) to handle the nonconvexity of the objective function, coupled with a novel block- signal tracking scheme, aiming at locally estimating the average of the agents’ gradients. Asymptotic convergence to stationary solutions of the nonconvex problem is established. Numerical results on a sparse regression problem show the effectiveness of the proposed algorithm and the impact of the block size on its practical convergence speed and communication cost.

Distributed big-data optimization via block communications

Notarnicola, Ivano
;
Notarstefano, Giuseppe
2017

Abstract

We study distributed multi-agent large-scale optimization problems, wherein the cost function is composed of a smooth possibly nonconvex sum-utility plus a DC (Difference-of-Convex) regularizer. We consider the scenario where the dimension of the optimization variables is so large that optimizing and/or transmitting the entire set of variables could cause unaffordable computation and communication overhead. To address this issue, we propose the first distributed algorithm whereby agents optimize and communicate only a portion of their local variables. The scheme hinges on successive convex approximation (SCA) to handle the nonconvexity of the objective function, coupled with a novel block- signal tracking scheme, aiming at locally estimating the average of the agents’ gradients. Asymptotic convergence to stationary solutions of the nonconvex problem is established. Numerical results on a sparse regression problem show the effectiveness of the proposed algorithm and the impact of the block size on its practical convergence speed and communication cost.
IEEE 7th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP)
1
5
Notarnicola, Ivano; Sun, Ying; Scutari, Gesualdo; Notarstefano, Giuseppe
File in questo prodotto:
File Dimensione Formato  
/Users/ivanonotarnicola/Desktop/IRIS/2017camsap_/big_data_CAMSAP_post_reviewed.pdf

accesso riservato

Descrizione: pdf editoriale
Tipo: Versione (PDF) editoriale
Licenza: Licenza per accesso riservato
Dimensione 160.83 kB
Formato Adobe PDF
160.83 kB Adobe PDF   Visualizza/Apri   Contatta l'autore
versione_CRIS_unibo.pdf

accesso aperto

Descrizione: pdf post print
Tipo: Postprint
Licenza: Licenza per accesso libero gratuito
Dimensione 706.37 kB
Formato Adobe PDF
706.37 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11585/677716
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 0
social impact