Title | ||
---|---|---|
Decentralized Randomized Block-Coordinate Frank–Wolfe Algorithms for Submodular Maximization Over Networks |
Abstract | ||
---|---|---|
We consider decentralized large-scale continuous submodular constrained optimization problems over networks, where the goal is to maximize a sum of nonconvex functions with diminishing returns property. However, the computations of the projection step and the whole gradient can become prohibitive in high-dimensional constrained optimization problems. For this reason, a decentralized randomized block-coordinate Frank-Wolfe algorithm is proposed for submoduar maximization over networks by local communication and computation, which adopts the randomized block-coordinate descent and the Frank-Wolfe technique. We also show that the proposed algorithm converges to an approximation fact
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(1-e^{-p_{\max }/p_{\min }})$ </tex-math></inline-formula>
of the global maximal points at a rate of
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathcal {O}(1/T)$ </tex-math></inline-formula>
by choosing a suitable stepsize, where
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$T$ </tex-math></inline-formula>
is the number of iterations. In addition, we confirm the theoretical results by experiments. |
Year | DOI | Venue |
---|---|---|
2022 | 10.1109/TSMC.2021.3112691 | IEEE Transactions on Systems, Man, and Cybernetics: Systems |
Keywords | DocType | Volume |
Conditional gradient methods,decentralized optimization,randomized block-coordinate descent,submodular maximization | Journal | 52 |
Issue | ISSN | Citations |
8 | 2168-2216 | 0 |
PageRank | References | Authors |
0.34 | 32 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Mingchuan Zhang | 1 | 29 | 10.19 |
Yangfan Zhou | 2 | 232 | 29.72 |
Quanbo Ge | 3 | 0 | 0.34 |
Ruijuan Zheng | 4 | 25 | 5.25 |
Qingtao Wu | 5 | 16 | 5.35 |