Projection-Free Gradient Tracking Neurodynamic for Distributed Nonnegative Sparse Optimization
Authors: Juntao Li, Qihang Guo, Deyuan Meng
Organizations: School of Mathematics and Statistics, Henan Normal University, Xinxiang 453007, P. R. China · Seventh Research Division, School of Automation Science and Electrical Engineering, Beihang University (BUAA), Beijing 100191, P. R. China
This paper proposes a continuous-time, projection-free neurodynamic system based on gradient tracking for distributed nonnegative sparse optimization. Unlike traditional methods, our approach avoids projecting states onto the feasible set. Instead, it employs gradient tracking to estimate average gradients under heterogeneous costs, coupling primal and dual dynamics such that feasibility and sparsity emerge naturally from the equilibrium conditions. The system ensures unique solutions through a locally Lipschitz vector field and guarantees that every equilibrium corresponds to an exact KKT point. We establish rigorous convergence guarantees for convex objectives through three distinct analytical layers. These include a centralized kernel rate, a computable distributed rate derived from Jacobian analysis without restrictive stability assumptions, and a global exponential stability proof based on Lur'e system theory. Our analysis quantitatively separates these layers, revealing that the convergence rate is primarily limited by graph sparsity and remains robust to variations in momentum time scales. Numerical experiments on strongly convex quadratic problems validate the theoretical rates, demonstrate effective active set recovery, and show that the system maintains stable tail convergence rates even under strong local heterogeneity.
Figures & tables
Fig. 1: Exponential convergence on convex quadratic ( n=10 , d=5 , L/μ=1.5 , per-agent IC): relative error (a) and consensus error (b) for projection-free GT-PNN, continuous-time DIGing, projected DGD, and PNN without gradient tracking. Both GT-PNN errors decrease from t=0 ; its state-norm rate matches the certified Jacobian abscissa to within 1% on the tail window, and the primal scalar decays at the faster kernel abscissa.
Fig. 2: Sparse regularization path on the nonnegative sparse regression instance ( n=8 , d=8 , mi=12 , four nonzeros). (a) Coordinates of the limit versus κ : solid curves are the coordinates in supp(xtrue) , dashed lines their true values, gray curves the remaining coordinates, and circles the limits obtained by integrating ( 3 )–( 7 ) at the fourteen anchor values κ=0.005,…,0.6 . (b) Relative distance to xtrue ; the shaded region is where the centralized path recovers the support of xtrue ( κ≳0.035 ).
Fig. 3: Scalability on the convex quadratic ( L/μ=1.5 , ring). (a) Relative error versus time for n∈{5,10,20,40} : the decay slows as ν2 shrinks. (b) Relative error versus time for d∈{2,5,10,30} : the rate is essentially independent of d .
Fig. 4: Coupling strength and gradient-tracking ablation ( n=10 , d=5 , convex quadratic, L/μ=1.5 , per-agent initial conditions xi(0)∼U[0,2]d , independent across agents). Median over three instance seeds and two initialization seeds; shaded bands: [min,max] . (a) Consensus error for different ρ : it starts at O(1) and decreases with ρ , while the transient to a 10−2 primal error is nearly unchanged. (b) Without gradient tracking the error stagnates.
β
0.1
0.2
0.3
0.4
γJ (cert.)
0.0995
0.1708
0.2325
0.2815
measured
0.1053
0.1809
0.2583
0.2832
ρ
1
3
10
30
γJ (cert.)
0.1584
0.2150
0.2815
0.3013
measured
0.166
0.223
0.283
0.303
ε
0.01
0.02
0.05
0.20
TABLE I: Rate versus problem data ( n=10 , d=5 , μ=0.5 unless stated). Cert. : Jacobian abscissa γJ of Condition 2 (offline LMI at the KKT point). Measured : exponential fit of ∥ζ(t)−ζ∗∥ on [0.75T,T] ( R2≥0.998 ), median over six runs (three instance seeds and two initializations). All rows are full-trajectory tail fits; the n row gives certificates only, and its measured rates are in the text.
flow
rel
viol
KKT
comp
tact
supp
GT-PNN
3.0×10−10
8.8×10−2
3.7×10−11
1.3×10−9
17.22
15/15
N1
6.4×10−4
0
4.8×10−3
8.7×10−10
16.52
15/15
N2
6.3×10−10
0
1.4×10−9
5.8×10−10
16.12
15/15
N3
1.2
0
2.1×10−3
2.9×10−1
—
0/15
N4
1.9
5.1×10−1
—
—
—
0/15
−σ
2.8×10−10
8.7×10−2
4.1×10−11
1.9×10−10
17.22
15/15
TABLE II: Solvers and block ablations on the convex quadratic, with the same instance, integrator, step and initialization as the main runs; median over the fifteen (instance, initialization) pairs. rel : relative primal error at t=60 ; viol : max(0,−mini,jxij) over the horizon; KKT and comp : stationarity and complementarity residuals at t=60 ; tact : last time from which the zero pattern of xˉ matches that of x∗ ; supp : runs whose active set equals the centralized one (the five instances have 3 , 3 , 1 , 1 and 4 nonzeros). Dashes: no dual state.
Fig. 5: The seven flows of Table II on the nominal instance. (a) Relative primal error: the flows without tracking ( N3 ) or without a dual ( N4 ) stagnate, and the clipped flow without compensation ( N1 ) stalls near 10−4 ; the compensated clipped flow ( N2 ) coincides with the proposed one. (b) Violation of the orthant: the clipped flows are feasible by construction, the projection-free flows return to the orthant after a transient, and the flow without a dual stays outside it.
∥μ(0)∥
∥δ∥
d(∞)/∥δ∥
conservation
0.012
3.2×10−2
1.903
7×10−15
0.059
1.6×10−1
1.903
3×10−14
0.236
6.4×10−1
1.903
1×10−13
0.943
2.5
1.465
3×10−13
TABLE III: Displacement of the limit under a mean tracker defect on the nominal instance ( n=10 , d=5 , state dimension 250 , dimkerC=245 , nominal parameters, T=120 , Δt=2×10−3 ). Columns: defect, ℓ2 norm of δ=C†μ(0) , displacement over ∥δ∥ , and the violation of (I−ΠC)z(t)=(I−ΠC)z(0) .
Distributed optimization coordinates computation across multiple agents or machines while balancing convergence, communication, privacy, and reliability.
This paper proposes a bilevel particle swarm optimization (PSO)-neurodynamic method for solving the distributed sparse least-squares problem regularized by the smoothly clipped absolute deviation (SCAD) penalty to global optimality. The SCAD penalty is nonsmooth and nonconvex, so existing distributed neurodynamic methods have not been extended to it directly. Through two-time-scale singular perturbation analysis, a rigorous full-trajectory convergence theory with explicit convergence rates is established for the inner collaborative multi-agent neurodynamic system without requiring the second-order sufficient condition. A theory-guided inner-outer collaborative optimization framework is further developed, in which a red-light green-light sensitivity mechanism is embedded in the outer PSO search to enhance global search while concentrating computational effort on the SCAD shape parameters, thereby improving recovery accuracy and computational efficiency. Simulation results on four sparse-recovery scenarios demonstrate that the proposed method accurately recovers the true sparsity pattern and achieves faster convergence and lower relative error than competing neurodynamic methods.
Juntao Li, Qihang Guo, Deyuan Meng
School of Mathematics and Statistics, Henan Normal University, Xinxiang 453007, P. R. China · Seventh Research Division, School of Automation Science and Electrical Engineering, Beihang University (BUAA), Beijing 100191, P. R. China
We analyze Bregman ADMM for nonconvex linearly constrained problems under two-sided relative smoothness, a condition that replaces the standard Lipschitz gradient assumption with a Hessian comparison relative to a Bregman kernel. This setting covers polynomial objectives arising in matrix and tensor models for which a global Lipschitz-gradient constant need not exist. We show that on an invariant open state-space domain, one iteration of Bregman ADMM defines a smooth primal--dual fixed-point map whose strict-saddle KKT points are unstable fixed points; consequently, from random initialization the iterates converge to a strict saddle with probability zero. Combined with existing first-order convergence results, this yields almost-sure second-order stationarity of limiting KKT points. We extend the analysis to a multi-block star consensus formulation for distributed optimization. The technical novelty lies in a determinant reduction with a Bregman-specific symmetrization and scaling step in the two block spectral argument, together with a null space cancellation exploiting the star graph structure in the consensus case. Numerical experiments on distributed matrix factorization illustrate the theory, and a symmetric tensor factorization example demonstrates the broader Bregman proximal splitting idea beyond the separable consensus setting.
Shuang Li, Zhihui Zhu, Qiuwei Li
Department of Electrical and Computer Engineering, Iowa State University, Ames, Iowa 50014, USA · Department of Computer Science and Engineering, Ohio State University, Columbus, Ohio 43210, USA · DAMO Academy, Alibaba Group US, Bellevue, Washington 98004, USA
In recent years, singular-spectrum-based optimizers have attracted increasing attention due to their ability to preserve the matrix structure of neural network gradients, thereby enabling geometry-aware optimization. However, most singular-spectrum-based (SSB) approaches remain centralized, limiting their use in distributed learning infrastructures that exploit massive parallelism. Distributed SSB optimization is still at an early stage, with open questions about convergence guarantees and communication efficiency. To fill this gap, we propose the Distributed Momentum-based Spectral Estimator (DisMUSE), an efficient distributed SSB optimization framework for both data-center and federated settings. Using Muon-style exact orthogonalized momentum as the spectral update, DisMUSE integrates a recursive variance-reduced momentum estimator and achieves an O((KT)−1/3) convergence rate, where K and T denote the number of nodes and local iterations per node, respectively. This rate matches the best-known rates for variance-reduced nonconvex distributed optimization. Building on this variance-reduced framework, we study two extensions. First, our DisMUSE method with finite Newton-Schulz (NS) iterations preserves the same convergence order under a uniform normalized support-spectrum condition, up to a multiplicative factor. Second, we develop a communication-efficient variant based on low-rank (LR) momentum transmission and quantify the error it introduces to the stationarity bound, characterizing the trade-off between accuracy and communication cost.
Zhen Qin, Zhiyao Zhang, Yingbin Liang +1
Department of Electrical and Computer Engineering, The Ohio State University, Columbus, Ohio, USA