decent_bench.algorithms.p2p

class decent_bench.algorithms.p2p.P2PAlgorithm

Bases: Algorithm[P2PNetwork]

Distributed algorithm - agents collaborate using peer-to-peer communication.

cleanup_agents(network: P2PNetwork) → Iterable[Agent]

Return the agents whose auxiliary variables should be cleared.

Parameters:

network – provides the agents and topology for this algorithm.

cleanup(network: NetworkT) → None

Clean up the algorithm state by clearing auxiliary variables from agents.

This method is used to free up memory used by auxiliary variables that are not needed after training. Can be overridden to control what gets cleaned up.

Note

Override cleanup_agents() to control which agents are cleaned up.

Parameters:

network – provides the agents and topology for this algorithm.

abstractmethod initialize(network: NetworkT) → None

Initialize the algorithm.

Parameters:

network – provides the agents and topology for this algorithm.

abstract property name: str

Name of the algorithm.

run(network: NetworkT, start_iteration: int = 0, progress_callback: Callable[[int], None] | None = None) → None

Run the algorithm.

This method first calls initialize(), then step() for the specified number of iterations. Optionally call cleanup() after run() to clear auxiliary variables and free up memory.

Parameters:

• network – provides the agents and topology for this algorithm.

• start_iteration – iteration number to start from, used when resuming from a checkpoint. If greater than 0, initialize() will be skipped.

• progress_callback – optional callback to report progress after each iteration.

Raises:

ValueError – if start_iteration is not in [0, iterations]

Warning

Do not override this method. Instead, override initialize() and step() as needed.

Note

The algorithm saves the agents’ states every state_snapshot_period.

abstractmethod step(network: NetworkT, iteration: int) → None

Perform one iteration of the algorithm.

Parameters:

• network – provides the agents and topology for this algorithm.

• iteration – current iteration number.

iterations: int

Number of iterations to run the algorithm for.

class decent_bench.algorithms.p2p.ADMM(iterations: int = 100, penalty: float = 1, relaxation: float = 0.5, x0: InitialStates = None, z0: InitialStates = None, name: str = 'ADMM')

Bases: P2PAlgorithm

Distributed Alternating Direction Method of Multipliers characterized by the update step below.

\[\mathbf{x}_{i, k+1} = \operatorname{prox}_{\frac{1}{\rho N_i} f_i} \left(\sum_j \mathbf{z}_{ij, k} \frac{1}{\rho N_i} \right)\]

\[\mathbf{z}_{ij, k+1} = (1-\alpha) \mathbf{z}_{ij, k} - \alpha (\mathbf{z}_{ji, k} - 2 \rho \mathbf{x}_{j, k+1})\]

where \(\mathbf{x}_{i, k}\) is agent i’s local optimization variable at iteration k, \(\operatorname{prox}\) is the proximal operator described in Cost.proximal(), \(\rho > 0\) is the Lagrangian penalty parameter (the corresponding argument is penalty), \(N_i\) is the number of neighbors of i, \(f_i\) is i’s local cost function, j is a neighbor of i, and \(\alpha \in (0, 1)\) is the relaxation parameter (the corresponding argument is relaxation).

Note

x0 and z0 follow the InitialStates convention and are resolved per agent during initialize via initial_states(). If x0 is None and z0 is provided, each agent initializes x0 from z0 with one proximal update:

\[x_{i,0} = \operatorname{prox}_{\frac{1}{\rho N_i} f_i}\left(\frac{z_{i,0}}{\rho}\right)\]

The \(\mathbf{z}_{ij}\) variables of an agent are all initialized to the same value specified in z0 (if any).

iterations: int = 100

Number of iterations to run the algorithm for.

penalty: float = 1

relaxation: float = 0.5

x0: InitialStates = None

z0: InitialStates = None

name: str = 'ADMM'

class decent_bench.algorithms.p2p.ATC(iterations: int = 100, step_size: float = 0.001, x0: InitialStates = None, name: str = 'ATC')

Bases: P2PAlgorithm

Adapt-Then-Combine (ATC) distributed gradient descent characterized by the update below [1].

\[\mathbf{x}_{i, k+1} = (\sum_{j} \mathbf{W}_{ij} \mathbf{x}_{j,k} - \rho \nabla f_j(\mathbf{x}_{j,k}))\]

where \(\mathbf{x}_{i, k}\) is agent i’s local optimization variable at iteration k, j is a neighbor of i or i itself, \(\mathbf{W}_{ij}\) is the metropolis weight between agent i and j, \(\rho\) is the step size (the corresponding argument is step_size), and \(f_i\) is agent i’s local cost function.

Alias: AdaptThenCombine

[1]

Jianshu Chen and Ali H. Sayed. Diffusion adaptation strategies for distributed optimization and learning over networks. IEEE Transactions on Signal Processing, 60(8):4289–4305, 2012. doi:10.1109/TSP.2012.2198470.

iterations: int = 100

Number of iterations to run the algorithm for.

step_size: float = 0.001

x0: InitialStates = None

name: str = 'ATC'

decent_bench.algorithms.p2p.ATCT

alias of ATC_Tracking

class decent_bench.algorithms.p2p.ATG(iterations: int = 100, penalty: float = 1, relaxation: float = 0.5, gamma: float = 0.1, delta: float = 0.001, x0: InitialStates = None, z0: InitialStates = None, name: str = 'ATG')

Bases: P2PAlgorithm

ADMM-Tracking Gradient (ATG) [2] characterized by the update steps below.

\[\begin{split}\begin{bmatrix} \mathbf{y}_{i,k} \\ \mathbf{s}_{i,k} \end{bmatrix} = \frac{1}{1 + \rho N_i} \left( \begin{bmatrix} \mathbf{x}_{i,k} \\ \nabla f_i(\mathbf{x}_{i,k}) \end{bmatrix} + \sum_j \mathbf{z}_{ij, k} \right)\end{split}\]

\[\mathbf{x}_{i,k+1} = (1 - \gamma) \mathbf{x}_{i,k} + \gamma \left( \mathbf{y}_{i,k} - \delta \mathbf{s}_{i,k} \right)\]

\[\begin{split}\mathbf{z}_{ij, k+1} = (1-\alpha) \mathbf{z}_{ij, k} - \alpha \left( \mathbf{z}_{ji, k} - 2 \rho \begin{bmatrix} \mathbf{y}_{i,k} \\ \mathbf{s}_{i,k} \end{bmatrix} \right)\end{split}\]

where \(\mathbf{x}_{i, k} \in \mathbb{R}^n\) is agent i’s local optimization variable at iteration k, \(\mathbf{y}_{i,k}, \ \mathbf{s}_{i,k} \in \mathbb{R}^n\) and \(\mathbf{z}_{ij,k} \in \mathbb{R}^{2n}\) are auxiliary variables, \(N_i\) is the number of neighbors of i, \(f_i\) is i’s local cost function, j is a neighbor of i. The parameters are: the penalty \(\rho > 0\) (the corresponding argument is penalty), the relaxation \(\alpha \in (0, 1)\) (the corresponding argument is relaxation), the step-size \(\delta > 0\) (the corresponding argument is delta), and the mixing parameter \(\gamma > 0\) (the corresponding argument is gamma). Notice that the convergence of the algorithm is guaranteed provided that \(\delta, \ \gamma\) are below certain thresholds.

The idea of the algorithm is to apply distributed ADMM to perform gradient tracking, instead of the usual average consensus.

Aliases: ADMM_Tracking, ADMM_TrackingGradient

[2]

Guido Carnevale, Nicola Bastianello, Giuseppe Notarstefano, and Ruggero Carli. Admm-tracking gradient for distributed optimization over asynchronous and unreliable networks. IEEE Transactions on Automatic Control, 70(8):5160–5175, 2025. doi:10.1109/TAC.2025.3539454.

iterations: int = 100

Number of iterations to run the algorithm for.

penalty: float = 1

relaxation: float = 0.5

gamma: float = 0.1

delta: float = 0.001

x0: InitialStates = None

z0: InitialStates = None

name: str = 'ATG'

class decent_bench.algorithms.p2p.DGD(iterations: int = 100, step_size: float = 0.001, x0: InitialStates = None, name: str = 'DGD')

Bases: P2PAlgorithm

Distributed gradient descent characterized by the update step below.

\[\mathbf{x}_{i, k+1} = \sum_{j} \mathbf{W}_{ij} \mathbf{x}_{j,k}) - \rho \nabla f_i(\mathbf{x}_{i,k})\]

where \(\mathbf{x}_{i, k}\) is agent i’s local optimization variable at iteration k, j is a neighbor of i or i itself, \(\mathbf{W}_{ij}\) is the metropolis weight between agent i and j, \(\rho\) is the step size (the corresponding argument is step_size), and \(f_i\) is agent i’s local cost function.

iterations: int = 100

Number of iterations to run the algorithm for.

step_size: float = 0.001

x0: InitialStates = None

name: str = 'DGD'

class decent_bench.algorithms.p2p.DLM(iterations: int = 100, step_size: float = 0.001, penalty: float = 1, x0: InitialStates = None, name: str = 'DLM')

Bases: P2PAlgorithm

Decentralized Linearized ADMM (DLM) [3][4] characterized by the update steps below.

\[\mathbf{x}_{i,k+1} = \mathbf{x}_{i,k} - \mu \left( \nabla f_i(\mathbf{x}_{i,k}) + \rho \sum_j (\mathbf{x}_{i,k} - \mathbf{x}_{j,k}) + \mathbf{z}_{i,k} \right)\]

\[\mathbf{z}_{i, k+1} = \mathbf{z}_{i, k} + \rho \sum_j (\mathbf{x}_{i,k+1} - \mathbf{x}_{j,k+1})\]

where \(\mathbf{x}_{i, k}\) is agent i’s local optimization variable at iteration k, \(\mathbf{z}_{i,k}\) is the local dual variable, \(f_i\) is i’s local cost function, j is a neighbor of i. The parameters are: the penalty \(\rho > 0\) and the step-size \(\mu > 0\).

Alias: DecentralizedLinearizedADMM

[3]

Qing Ling, Wei Shi, Gang Wu, and Alejandro Ribeiro. Dlm: decentralized linearized alternating direction method of multipliers. IEEE Transactions on Signal Processing, 63(15):4051–4064, 2015. doi:10.1109/TSP.2015.2436358.

[4]

Sulaiman A. Alghunaim, Ernest K. Ryu, Kun Yuan, and Ali H. Sayed. Decentralized proximal gradient algorithms with linear convergence rates. IEEE Transactions on Automatic Control, 66(6):2787–2794, 2021. doi:10.1109/TAC.2020.3009363.

iterations: int = 100

Number of iterations to run the algorithm for.

step_size: float = 0.001

penalty: float = 1

x0: InitialStates = None

name: str = 'DLM'

class decent_bench.algorithms.p2p.ED(iterations: int = 100, step_size: float = 0.001, x0: InitialStates = None, name: str = 'ED')

Bases: P2PAlgorithm

Gradient tracking algorithm characterized by the update step below.

\[\mathbf{y}_{i, k+1} = \mathbf{x}_{i, k} - \rho \nabla f_i(\mathbf{x}_{i,k})\]

\[\mathbf{x}_{i, k+1} = \sum_j \frac{1}{2} (\mathbf{I} + \mathbf{W})_{ij} (\mathbf{x}_{j,k} + \mathbf{y}_{j, k+1} - \mathbf{y}_{j, k})\]

where \(\mathbf{x}_{i, k}\) is agent i’s local optimization variable at iteration k, \(\rho\) is the step size (the corresponding argument is step_size), \(f_i\) is agent i’s local cost function, j is a neighbor of i or i itself, and \(\mathbf{W}_{ij}\) is the metropolis weight between agent i and j.

Alias: ExactDiffusion

iterations: int = 100

Number of iterations to run the algorithm for.

step_size: float = 0.001

x0: InitialStates = None

name: str = 'ED'

class decent_bench.algorithms.p2p.EXTRA(iterations: int = 100, step_size: float = 0.001, x0: InitialStates = None, name: str = 'EXTRA')

Bases: P2PAlgorithm

EXTRA [5] gradient tracking algorithm characterized by the update steps below.

\[\mathbf{x}_{i, k+1} = \mathbf{x}_{i, k} + \sum_j \mathbf{W}_{ij} \mathbf{x}_{j,k} - \sum_j \tilde{\mathbf{W}}_{ij} \mathbf{x}_{j,k-1} - \rho (\nabla f_i(\mathbf{x}_{i,k}) - \nabla f_i(\mathbf{x}_{i,k-1}))\]

where \(\mathbf{x}_{i, k}\) is agent i’s local optimization variable at iteration k, \(\rho\) is the step size (the corresponding argument is step_size), \(f_i\) is agent i’s local cost function, j is a neighbor of i or i itself, \(\mathbf{W}_{ij}\) is the metropolis weight between agent i and j, and \(\tilde{\mathbf{W}} = (\mathbf{I} + \mathbf{W}) / 2\).

[5]

Wei Shi, Qing Ling, Gang Wu, and Wotao Yin. Extra: an exact first-order algorithm for decentralized consensus optimization. 2014. URL: https://arxiv.org/abs/1404.6264, arXiv:1404.6264.

iterations: int = 100

Number of iterations to run the algorithm for.

step_size: float = 0.001

x0: InitialStates = None

name: str = 'EXTRA'

class decent_bench.algorithms.p2p.GT_SAGA(iterations: int = 100, step_size: float = 0.01, x0: InitialStates = None, name: str = 'GT-SAGA')

Bases: P2PAlgorithm

Gradient Tracking with SAGA variance reduction [6] [7].

Parameters:

• iterations – Total number of iterations

• step_size – Step size for local updates

• x0 – Initial parameters (optional)

• name – Algorithm name (default “GT-SAGA”)

Raises:

TypeError – If any agent’s cost function is not an instance of EmpiricalRiskCost.

[6]

Ran Xin, Usman A. Khan, and Soummya Kar. Variance-reduced decentralized stochastic optimization with accelerated convergence. IEEE Transactions on Signal Processing, 68():6255–6271, 2020. doi:10.1109/TSP.2020.3031071.

[7]

Ran Xin, Usman A. Khan, and Soummya Kar. A fast randomized incremental gradient method for decentralized nonconvex optimization. IEEE Transactions on Automatic Control, 67(10):5150–5165, 2022. doi:10.1109/TAC.2021.3122586.

iterations: int = 100

Number of iterations to run the algorithm for.

step_size: float = 0.01

x0: InitialStates = None

name: str = 'GT-SAGA'

class decent_bench.algorithms.p2p.GT_SARAH(iterations: int = 100, num_local_steps: int = 5, step_size: float = 0.01, x0: InitialStates = None, name: str = 'GT-SARAH')

Bases: P2PAlgorithm

GT-SARAH: Gradient Tracking with SARAH variance reduction [8].

Parameters:

• iterations – Total number of outer loops (S)

• num_local_steps – Number of inner loop iterations (q)

• step_size – Step size (alpha) for updates

• x0 – Initial parameters (optional)

• name – Algorithm name (default “GT-SARAH”)

Raises:

TypeError – If any agent’s cost function is not an instance of EmpiricalRiskCost.

[8]

Ran Xin, Usman A. Khan, and Soummya Kar. Fast decentralized non-convex finite-sum optimization with recursive variance reduction. 2021. URL: https://arxiv.org/abs/2008.07428, arXiv:2008.07428.

iterations: int = 100

Number of iterations to run the algorithm for.

num_local_steps: int = 5

step_size: float = 0.01

x0: InitialStates = None

name: str = 'GT-SARAH'

class decent_bench.algorithms.p2p.GT_VR(iterations: int = 100, step_size: float = 0.01, snapshot_prob: float = 0.3, x0: InitialStates = None, name: str = 'GT-VR')

Bases: P2PAlgorithm

GT-VR: Gradient Tracking with Variance Reduction algorithm [9].

Parameters:

• iterations – Total number of iterations

• step_size – Step size for primal updates

• snapshot_prob – Probability of performing a snapshot update (P in the paper)

• x0 – Initial parameters (optional)

• name – Algorithm name (default “GT-VR”)

Raises:

TypeError – If any agent’s cost function is not an instance of EmpiricalRiskCost.

[9]

Xia Jiang, Xianlin Zeng, Jian Sun, and Jie Chen. Distributed stochastic gradient tracking algorithm with variance reduction for non-convex optimization. IEEE Transactions on Neural Networks and Learning Systems, 34(9):5310–5321, 2023. doi:10.1109/TNNLS.2022.3170944.

iterations: int = 100

Number of iterations to run the algorithm for.

step_size: float = 0.01

snapshot_prob: float = 0.3

x0: InitialStates = None

name: str = 'GT-VR'

class decent_bench.algorithms.p2p.KGT(iterations: int = 100, num_local_steps: int = 5, step_size: float = 0.01, aux_step_size: float = 0.01, x0: InitialStates = None, name: str = 'K-GT')

Bases: P2PAlgorithm

K-GT: Gradient Sum Tracking algorithm [10].

Parameters:

• iterations – Total number of communication rounds (T)

• num_local_steps – Number of local gradient steps (K)

• step_size – Local step size (eta_c)

• aux_step_size – Communication step size (eta_s)

• x0 – Initial parameters (optional)

• name – Algorithm name (default “K-GT”)

[10]

Yue Liu, Tao Lin, Anastasia Koloskova, and Sebastian U. Stich. Decentralized gradient tracking with local steps. 2023. URL: https://arxiv.org/abs/2301.01313, arXiv:2301.01313.

iterations: int = 100

Number of iterations to run the algorithm for.

num_local_steps: int = 5

step_size: float = 0.01

aux_step_size: float = 0.01

x0: InitialStates = None

name: str = 'K-GT'

class decent_bench.algorithms.p2p.LED(iterations: int = 100, num_local_steps: int = 5, step_size: float = 0.01, aux_step_size: float = 0.01, x0: InitialStates = None, name: str = 'LED')

Bases: P2PAlgorithm

Local Exact-Diffusion (LED) algorithm [11].

Parameters:

• iterations – Total number of communication rounds (r)

• num_local_steps – Number of local updates (tau)

• step_size – Step size alpha for gradient steps

• aux_step_size – Step size beta for dual variable

• x0 – Initial parameters (optional)

• name – Algorithm name (default “LED”)

[11]

Sulaiman A. Alghunaim. Local exact-diffusion for decentralized optimization and learning. IEEE Transactions on Automatic Control, 69(11):7371–7386, 2024. doi:10.1109/TAC.2024.3383271.

iterations: int = 100

Number of iterations to run the algorithm for.

num_local_steps: int = 5

step_size: float = 0.01

aux_step_size: float = 0.01

x0: InitialStates = None

name: str = 'LED'

class decent_bench.algorithms.p2p.LT_ADMM(iterations: int = 100, num_local_steps: int = 5, step_size: float = 0.01, aux_step_size: float = 0.01, penalty: float = 1.0, alpha: float = 0.5, x0: InitialStates = None, name: str = 'LT-ADMM')

Bases: P2PAlgorithm

Local Training ADMM (LT-ADMM) [12].

Parameters:

• iterations – Total number of communication rounds (K)

• num_local_steps – Number of local training steps (tau)

• step_size – Local step size (gamma)

• aux_step_size – Local step size (beta)

• penalty – Penalty parameter (rho)

• alpha – Relaxation parameter (alpha)

• x0 – Initial parameters (optional)

• name – Algorithm name (default “LT-ADMM”)

[12] (1,2)

Xiaoxing Ren, Nicola Bastianello, Karl H. Johansson, and Thomas Parisini. Communication-efficient stochastic distributed learning. 2026. doi:10.1109/TAC.2026.3675513.

iterations: int = 100

Number of iterations to run the algorithm for.

num_local_steps: int = 5

step_size: float = 0.01

aux_step_size: float = 0.01

penalty: float = 1.0

alpha: float = 0.5

x0: InitialStates = None

name: str = 'LT-ADMM'

class decent_bench.algorithms.p2p.LT_ADMM_VR(iterations: int = 100, num_local_steps: int = 5, step_size: float = 0.01, aux_step_size: float = 0.01, penalty: float = 1.0, alpha: float = 0.5, x0: InitialStates = None, name: str = 'LT-ADMM-VR', v2: bool = True)

Bases: LT_ADMM

Local Training ADMM with Variance Reduction (LT-ADMM-VR) [12].

Extends LT-ADMM with variance reduction techniques for improved convergence. This variant implements additional gradient variance reduction mechanisms during the local training phase.

Parameters:

• iterations – Total number of communication rounds (K)

• num_local_steps – Number of local training steps (tau)

• step_size – Local step size (gamma)

• aux_step_size – Local step size (beta)

• penalty – Penalty parameter (rho)

• alpha – Relaxation parameter (alpha)

• x0 – Initial parameters (optional)

• v2 – Whether to use the LT-ADMM-VR-2 variant with improved variance reduction techniques which is less computational heavy (default True).

• name – Algorithm name (default “LT-ADMM-VR”)

Raises:

TypeError – If any agent’s cost function is not an instance of EmpiricalRiskCost.

v2: bool = True

name: str = 'LT-ADMM-VR'

decent_bench.algorithms.p2p.NEXT

alias of ATC_Tracking

class decent_bench.algorithms.p2p.NIDS(iterations: int = 100, step_size: float = 0.001, x0: InitialStates = None, name: str = 'NIDS')

Bases: P2PAlgorithm

NIDS [13] gradient tracking algorithm characterized by the update steps below.

\[\mathbf{x}_{i, k+1} = \sum_j \tilde{\mathbf{W}}_{ij} (2 x_{j,k} - x_{j, k-1} - \rho \nabla f_j(\mathbf{x}_{j,k}) + \rho \nabla f_j(\mathbf{x}_{j,k-1}))\]

where \(\mathbf{x}_{i, k}\) is agent i’s local optimization variable at iteration k, \(\rho\) is the step size, \(f_i\) is agent i’s local cost function, j is a neighbor of i or i itself, and \(\tilde{\mathbf{W}} = (\mathbf{I} + \mathbf{W}) / 2\) with \(\mathbf{W}\) are the Metropolis weights.

This is a simplified version of the algorithm proposed in [13] (see eq. (9) therein).

[13] (1,2)

Zhi Li, Wei Shi, and Ming Yan. A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates. IEEE Transactions on Signal Processing, 67(17):4494–4506, 2019. doi:10.1109/TSP.2019.2926022.

iterations: int = 100

Number of iterations to run the algorithm for.

step_size: float = 0.001

x0: InitialStates = None

name: str = 'NIDS'

decent_bench.algorithms.p2p.SONATA

alias of ATC_Tracking

decent_bench.algorithms.p2p.ADMM_Tracking

alias of ATG

decent_bench.algorithms.p2p.ADMM_TrackingGradient

alias of ATG

decent_bench.algorithms.p2p.ATC_DIGing

alias of AugDGM

class decent_bench.algorithms.p2p.ATC_Tracking(iterations: int = 100, step_size: float = 0.001, x0: InitialStates = None, name: str = 'ATC-Tracking')

Bases: P2PAlgorithm

ATC-Tracking [14][15][16] gradient tracking algorithm.

The algorithm is characterized by the updates below.

\[\mathbf{x}_{i, k+1} = \sum_j \mathbf{W}_{ij} (\mathbf{x}_{j, k} - \rho \mathbf{y}_{j, k})\]

\[\mathbf{y}_{i, k+1} = \sum_j \mathbf{W}_{ij} \mathbf{y}_{j, k} + \nabla f_i(\mathbf{x}_{i,k+1}) - \nabla f_i(\mathbf{x}_{i,k})\]

where \(\mathbf{x}_{i, k}\) is agent i’s local optimization variable at iteration k, \(\rho\) is the step size, \(f_i\) is agent i’s local cost function, j is a neighbor of i or i itself, and \(\mathbf{W}_{ij}\) is the metropolis weight between agent i and j.

Aliases: SONATA, NEXT, ATCT

[14]

Paolo Di Lorenzo and Gesualdo Scutari. Next: in-network nonconvex optimization. IEEE Transactions on Signal and Information Processing over Networks, 2(2):120–136, 2016. doi:10.1109/TSIPN.2016.2524588.

[15]

Gesualdo Scutari and Ying Sun. Distributed nonconvex constrained optimization over time-varying digraphs. 2018. URL: https://arxiv.org/abs/1809.01106, arXiv:1809.01106.

[16]

Sulaiman A. Alghunaim, Ernest K. Ryu, Kun Yuan, and Ali H. Sayed. Decentralized proximal gradient algorithms with linear convergence rates. IEEE Transactions on Automatic Control, 66(6):2787–2794, 2021. doi:10.1109/TAC.2020.3009363.

iterations: int = 100

Number of iterations to run the algorithm for.

step_size: float = 0.001

x0: InitialStates = None

name: str = 'ATC-Tracking'

decent_bench.algorithms.p2p.AdaptThenCombine

alias of ATC

class decent_bench.algorithms.p2p.AugDGM(iterations: int = 100, step_size: float = 0.001, x0: InitialStates = None, name: str = 'Aug-DGM')

Bases: P2PAlgorithm

Aug-DGM [17] or ATC-DIGing [18] gradient tracking algorithm.

The algorithm is characterized by the updates below.

\[\mathbf{x}_{i, k+1} = \sum_j \mathbf{W}_{ij} (\mathbf{x}_{j, k} - \rho \mathbf{y}_{j, k})\]

\[\mathbf{y}_{i, k+1} = \sum_j \mathbf{W}_{ij} (\mathbf{y}_{j, k} + \nabla f_j(\mathbf{x}_{j,k+1}) - \nabla f_j(\mathbf{x}_{j,k}))\]

where \(\mathbf{x}_{i, k}\) is agent i’s local optimization variable at iteration k, \(\rho\) is the step size, \(f_i\) is agent i’s local cost function, j is a neighbor of i or i itself, and \(\mathbf{W}_{ij}\) is the metropolis weight between agent i and j.

Alias: ATC_DIGing

[17]

Jinming Xu, Shanying Zhu, Yeng Chai Soh, and Lihua Xie. Augmented distributed gradient methods for multi-agent optimization under uncoordinated constant stepsizes. In 2015 54th IEEE Conference on Decision and Control (CDC), volume, 2055–2060. 2015. doi:10.1109/CDC.2015.7402509.

[18]

Angelia Nedić, Alex Olshevsky, Wei Shi, and César A. Uribe. Geometrically convergent distributed optimization with uncoordinated step-sizes. In 2017 American Control Conference (ACC), volume, 3950–3955. 2017. doi:10.23919/ACC.2017.7963560.

iterations: int = 100

Number of iterations to run the algorithm for.

step_size: float = 0.001

x0: InitialStates = None

name: str = 'Aug-DGM'

decent_bench.algorithms.p2p.DecentralizedLinearizedADMM

alias of DLM

class decent_bench.algorithms.p2p.DiNNO(iterations: int = 100, step_size: float = 0.01, num_local_steps: int = 5, penalty: float = 0.5, x0: InitialStates = None, name: str = 'DiNNO')

Bases: P2PAlgorithm

Distributed Neural Network Optimization (DiNNO) algorithm [19].

Each iteration, each agent approximately optimizes an augmented Lagrangian function which is then communicated to its neighbors in order to update the dual variables. This is then repeated for a number of iterations.

Parameters:

• iterations – Total number of outer iterations (K)

• step_size – Step size for primal updates

• num_local_steps – Number of inner iterations (B) for approximate primal update

• penalty – Penalty parameter (rho) for augmented Lagrangian

• x0 – Initial parameters (optional)

• name – Algorithm name (default “DiNNO”)

[19]

Javier Yu, Joseph A. Vincent, and Mac Schwager. Dinno: distributed neural network optimization for multi-robot collaborative learning. IEEE Robotics and Automation Letters, 7(2):1896–1903, April 2022. URL: http://dx.doi.org/10.1109/LRA.2022.3142402, doi:10.1109/lra.2022.3142402.

iterations: int = 100

Number of iterations to run the algorithm for.

step_size: float = 0.01

num_local_steps: int = 5

penalty: float = 0.5

x0: InitialStates = None

name: str = 'DiNNO'

decent_bench.algorithms.p2p.ExactDiffusion

alias of ED

class decent_bench.algorithms.p2p.ProxSkip(iterations: int = 100, step_size: float = 0.01, aux_step_size: float = 0.01, comm_probability: float = 0.7, chi: float = 1.0, x0: InitialStates = None, name: str = 'ProxSkip')

Bases: P2PAlgorithm

Proximal Skip with local gradient steps [20].

Parameters:

• iterations – Total number of iterations (T)

• step_size – Step size alpha > 0 for primal updates

• aux_step_size – Step size beta > 0 for dual updates

• comm_probability – Communication probability 0 < p <= 1 for skipping communication

• chi – chi >= 1, averaging weight parameter for weighted averaging during communication

• x0 – Initial parameters (optional)

• name – Algorithm name (default “ProxSkip”)

[20]

Konstantin Mishchenko, Grigory Malinovsky, Sebastian Stich, and Peter Richtárik. Proxskip: yes! local gradient steps provably lead to communication acceleration! finally! 2023. URL: https://arxiv.org/abs/2202.09357, arXiv:2202.09357.

iterations: int = 100

Number of iterations to run the algorithm for.

step_size: float = 0.01

aux_step_size: float = 0.01

comm_probability: float = 0.7

chi: float = 1.0

x0: InitialStates = None

name: str = 'ProxSkip'

class decent_bench.algorithms.p2p.SimpleGT(iterations: int = 100, step_size: float = 0.001, x0: InitialStates = None, name: str = 'SimpleGT')

Bases: P2PAlgorithm

Gradient tracking algorithm characterized by the update step below.

\[\mathbf{y}_{i, k+1} = \mathbf{x}_{i, k} - \rho \nabla f_i(\mathbf{x}_{i,k})\]

\[\mathbf{x}_{i, k+1} = \mathbf{y}_{i, k+1} - \mathbf{y}_{i, k} + \sum_j \mathbf{W}_{ij} \mathbf{x}_{j,k}\]

where \(\mathbf{x}_{i, k}\) is agent i’s local optimization variable at iteration k, \(\rho\) is the step size, \(f_i\) is agent i’s local cost function, j is a neighbor of i or i itself, and \(\mathbf{W}_{ij}\) is the metropolis weight between agent i and j.

Alias: SimpleGradientTracking

iterations: int = 100

Number of iterations to run the algorithm for.

step_size: float = 0.001

x0: InitialStates = None

name: str = 'SimpleGT'

decent_bench.algorithms.p2p.SimpleGradientTracking

alias of SimpleGT

class decent_bench.algorithms.p2p.WangElia(iterations: int = 100, step_size: float = 0.001, x0: InitialStates = None, name: str = 'Wang-Elia')

Bases: P2PAlgorithm

Wang-Elia gradient tracking algorithm characterized by the updates below, see [21][22].

\[\mathbf{x}_{i, k+1} = \mathbf{x}_{i, k} - \sum_j \mathbf{K}_{ij} (\mathbf{x}_{j, k} + \mathbf{z}_{j, k}) - \rho \nabla f_i(\mathbf{x}_{i,k})\]

\[\mathbf{z}_{i, k+1} = \mathbf{z}_{i, k} + \sum_j \mathbf{K}_{ij} \mathbf{x}_{j, k}\]

where \(\mathbf{x}_{i, k}\) is agent i’s local optimization variable at iteration k, \(\rho\) is the step size, \(f_i\) is agent i’s local cost function, j is a neighbor of i or i itself, and \(\mathbf{K}_{ij}\) is the weight between agent i and j. The matrix \(\mathbf{K}\) is chosen as \(0.5 (\mathbf{I} - \mathbf{W})\), where \(\mathbf{W}\) is the Metropolis weight matrix.

[21]

Jing Wang and Nicola Elia. Control approach to distributed optimization. In 2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton), volume, 557–561. 2010. doi:10.1109/ALLERTON.2010.5706956.

[22]

Michelangelo Bin, Ivano Notarnicola, and Thomas Parisini. Stability, linear convergence, and robustness of the wang-elia algorithm for distributed consensus optimization. In 2022 IEEE 61st Conference on Decision and Control (CDC), volume, 1610–1615. 2022. doi:10.1109/CDC51059.2022.9993284.

iterations: int = 100

Number of iterations to run the algorithm for.

step_size: float = 0.001

x0: InitialStates = None

name: str = 'Wang-Elia'