Distributed Composite Optimization With Distributed Composite Block Mirror Descent

doi:10.1109/TAC.2026.3652901

Distributed Composite Optimization With Distributed Composite Block Mirror Descent

2026-01-12

0

PRE

AI

DOI：10.1109/TAC.2026.3652901

Original

Original request for help

Save

Abstract

En 中文

This article investigates a class of large-scale distributed nonsmooth composite optimization problems over time-varying multiagent networks. Specifically, the decision space, which can be split into several blocks of convex set, is considered. Each node, endowed with a private nonsmooth cost function and a regularization function, aims to minimize the sum of all local functions across the network. We propose a novel distributed composite block mirror descent (DCBMD) method, where each node performs information communication with other agents and executes a block regularized mirror descent in each iteration. In contrast to existing work on distributed composite optimization, for the decision space with block structure, we do not require the projection to be operated on the whole decision space. Instead, in each step, a distributed projection procedure induced by a composite mirror descent scheme is performed on only one randomly selected block, significantly saving the iteration cost. The explicit formulation of the convergence bound depending on random projection probabilities and network parameters is achieved. An optimal convergence rate <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/\sqrt{T})$</tex-math></inline-formula> is rigorously derived. The DCBMD provides a generic framework for different projection-based distributed algorithms.

Keywords:

Block mirror descent

distributed composite optimization

random coordinate descent

rate of convergence

stochastic optimization

Distributed Composite Optimization With Distributed Composite Block Mirror Descent

Abstract

Journal

Organization