AIMech AI
Home / Curated / Algorithms / NIDS (Network-Independent Step-Size Decentralized Proximal-Gradient Method)

NIDS (Network-Independent Step-Size Decentralized Proximal-Gradient Method)

Algorithms AIMech:NidsNetworkIndependentStepSizeDecentralizedProximalGradientMethod DRAFT
Aliases: NIDS, Network-Independent Step-Size Decentralized Proximal-Gradient Method, NIDS Decentralized Proximal-Gradient Algorithm
A decentralized composite optimization algorithm (Li, Shi, & Yan 2019, Section II, Equation 4) for minimizing (1/n) sum_{i=1}^n (s_i(x) + r_i(x)) over an undirected connected network with symmetric doubly stochastic mixing matrix W that updates X^{k+1} = prox_{alpha R}(W_tilde X^k + X^k - W_tilde X^{k-1} - alpha nabla S(X^k) + alpha W_tilde nabla S(X^{k-1})) using the affine-shifted consensus matrix W_tilde = ((1 + c) I + (1 - c) W) / 2 with c in [1 / (1 - lambda_n(W)), 1), admitting any network-independent step size alpha_i in (0, 2 / L_i) identical to centralized proximal gradient descent.
Identity Notes & Concept Scope Distinct from EXTRA (AIMech:ExtraExactFirstOrderAlgorithmForDecentralizedConsensusOptimization, Shi et al. 2015) and PG-EXTRA, which apply the raw mixing matrix W in the gradient difference term X^{k+1} = W X^k + X^k - W_tilde X^{k-1} - alpha(nabla S(X^k) - nabla S(X^{k-1})) and therefore restrict step sizes by the spectral gap of W (alpha < 2 lambda_min(W_tilde) / L), whereas NIDS multiplies the previous gradient by W_tilde inside the proximal argument so the maximal stable step size alpha < 2 / L is completely independent of the network topology.

Claims & Grounded Evidence

4 Claims
Mechanism #r440-primal-dual-metric-recursion-and-network-independent-step-size
Introducing the dual sequence d^{k+1} = d^k - alpha^{-1}(I - W_tilde)(X^k - alpha nabla S(X^k)) and metric M = alpha^{-1} I - (I - W_tilde)^{-1} + I (Section II-B, Equation 6), NIDS is equivalent to the symmetric primal-dual proximal iteration (X^k - X^{k+1}) + alpha(d^k - d^{k+1}) = alpha(nabla S(X^k) - nabla S(X^{k-1})) with X^{k+1} = prox_{alpha R}(X^k - alpha d^{k+1} - alpha nabla S(X^k)), which remains positive-definite and convergent for any 0 < alpha_i < 2 / L_i regardless of how close lambda_2(W) is to 1 (Theorem 1).
Mechanism #r440-separated-function-and-consensus-linear-convergence-rate
When the smooth local objectives s_i are mu_i-strongly convex and r_i = 0, Theorem 2 proves global linear convergence at rate O((1 - max(1 - alpha mu / 2, (1 - c)(1 - lambda_2(W)) / 2))^{-k}), cleanly separating the optimization condition number L / mu from the network spectral gap 1 - lambda_2(W) so that O(L/mu + 1/(1 - lambda_2(W))) log(1/epsilon) iterations suffice instead of their product.
Limitation #r440-smallest-eigenvalue-bound-and-two-step-history-limitation
Choosing the mixing shift parameter c >= 1 / (1 - lambda_n(W)) requires a lower bound on the smallest eigenvalue lambda_n(W) of the symmetric mixing matrix W (e.g., c = 1/2 when lambda_n(W) >= -1), and each node must store two consecutive primal iterates X^k, X^{k-1} and gradients nabla S(X^k), nabla S(X^{k-1}).
Application #r440-decentralized-sparse-lasso-and-quadratic-sensing-application
Applied to decentralized sparse signal recovery (L_1-regularized LASSO) and ill-conditioned distributed quadratic estimation over poorly connected networks.

⚠️ Curated Limitations & Negative Results

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes
AIO Target Class Mapping Relation Mapping Rationale
AIO:LassoRegression
Lasso Regression
 related_match NIDS solves decentralized composite non-smooth problems including L_1-regularized LASSO with network-independent proximal-gradient step sizes.
AIO:FederatedLearning
Federated Learning
 related_match Provides decentralized peer-to-peer composite consensus optimization with separated computation and communication complexity.

Evidence Sources & Primary Literature

3 Sources
Source ID Publication / Document Type / Access Reference & Checksum
r440-primary-pdf
Zhi Li, Wei Shi, Ming Yan
primary paper
full_text
ID: https://doi.org/10.1109/TSP.2019.2926022
sha256:b567c2cd1afb…
r440-arxiv-abs
Zhi Li, Wei Shi, Ming Yan
primary paper
abstract_only
ID: https://arxiv.org/abs/1704.07807
sha256:0739ef418ed0…
r440-metadata-cr
Zhi Li, Wei Shi, Ming Yan
primary paper
abstract_only
ID: https://doi.org/10.1109/TSP.2019.2926022
sha256:2559daf2a20c…

Ontology & Grounding Topology

Open in interactive network graph →
CONCEPT KIND Algorithms AIMech:NidsNetworkIndependentStepSizeDecentralizedProximalGradientMethod NIDS... 4 claims · 3 sources AIO GROUNDING AIO:LassoRegression (2)

Curation Provenance

Curator: Antigravity
Method: ai_assisted
Model: Gemini
Created: 2026-10-19T08:43:00Z
Updated: 2026-10-19T08:43:00Z
Source File: data/curated/NidsNetworkIndependentStepSizeDecentralizedProximalGradientMethod.yaml · Schema: curated_concept.yaml

Explore across X-Mech

Related computational & biological Mechs: Embedding Map Network Graph ProteinTraitsMech (ESM-2 pLM) DUFMech (Domain pLM) TraitMech CultureMech All 14 X-Mech Repositories