Distributed Nonconvex Optimization with Double Privacy Protection and Exact Convergence

Zichong Ou, Dandan Wang, Zixuan Liu, Jie Lu · 2025

Read Distributed Nonconvex Optimization with Double Privacy Protection and Exact Convergence by Zichong Ou, Dandan Wang, Zixuan Liu, Jie Lu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-02283.txt.

Introduction

Zichong Ou, Dandan Wang, Zixuan Liu, and Jie Lu design a distributed optimisation algorithm that keeps every agent's data private twice over. In multi-agent networks, agents cooperate to minimise a shared objective built from their private local functions, but the messages they exchange can leak exactly what they are protecting. Current distributed methods for nonconvex objectives mostly ignore this leakage.

Their algorithm first merges the primal and dual variables through a transformation, hiding the critical local information inside the combined quantities. It then adds a random jitter to obscure what is transmitted. The authors prove the scheme delivers differential privacy for the local objectives. It still converges exactly, at a sublinear rate in general and a linear one under an extra geometric condition on the objective. A numerical example shows it outrunning several leading algorithms at the same privacy level.

Catalog record

CREATORZichong Ou, Dandan Wang, Zixuan Liu, Jie Lu
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE93 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-02283

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Distributed Nonconvex Optimization with Double Privacy Protection and Exact Convergence Zichong Ou, Dandan Wang, Zixuan Liu, Jie Lu Abstract Motivated by the pervasive lack of privacy protection in existing distributed nonconvex optimization methods, this paper proposes a decentralized proximal primal-dual algorithm enabling double protection of privacy ( DPP 2 \text{DPP}^{2} ) for minimizing nonconvex sum-utility functions over multi-agent networks, which ensures zero leakage of critical local information during inter-agent communications. We develop a two-tier privacy protection mechanism that first merges the primal and dual variables by means of a variable transformation, followed by embedding an additional random perturbation to further obfuscate the transmitted information. We theoretically establish that DPP 2 \text{DPP}^{2} ensures differential privacy for local objectives while achieving exact convergence under nonconvex settings. Specifically, DPP 2 \text{DPP}^{2} converges sublinearly to a stationary point and attains a linear convergence rate under the additional Polyak-Łojasiewicz (P-Ł) condition. Finally, a numerical example demonstrates the superiority of DPP 2 \text{DPP}^{2} over a number of state-of-the-art algorithms, showcasing the faster, exact convergence achieved by DPP 2 \text{DPP}^{2} under the same level of differential privacy. I Introduction Decentralized optimization has garnered considerable attention recently. In real-world scenarios, a vast majority of optimization problems exhibit nonconvex characteristics. These problems include but are not limited to distributed reinforcement learning [ 1 ] , dictionary learning [ 2 ] and wireless resource management [ 3 ] . Moreover, with the increasing scale of such problems, distributed nonconvex optimization techniques are becoming progressively urgent to develop, which employ a multi-agent network to enable cooperative optimization, and only allow interactions among neighboring agents. This paper studies the distributed optimization problem \min_{x\in\mathbb{R}^{d}}f(x)=\sum_{i=1}^{N}f_{i}(x) (1) over an N -node multi-agent network, where the global objective function f(x) is the sum of the nonconvex and smooth local objectives f_{1},\dots,f_{N} , each associated with a node. To address this problem, a collection of distributed nonconvex optimization algorithms have emerged, including primal gradient-based methods [ 4 , 5 , 6 ] and primal-dual methods [ 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 ] . Specifically, [ 4 ] shows that the well-known Decentralized Gradient Descent (DGD) and Proximal DGD (Prox-DGD) [ 15 ] asymptotically converge to the set of stationary solutions for nonconvex objectives, and [ 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 ] improve the convergence rate to a sublinear rate of \mathcal{O}(1/K) (where K denotes the number of iterations). Moreover, under the additional Polyak-Łojasiewicz (P-Ł) condition, [ 9 , 14 ] are shown to converge to the global optimum at a linear rate of \mathcal{O}(\theta^{K}) (where \theta\in(0,1) ). Despite their satisfactory convergence performance, the aforementioned algorithms heavily rely on the communication of local information to achieve consensus, which inadvertently lead to privacy leakage of sensitive data (including local decisions, local objective functions and their gradients). Existing approaches [ 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 ] typically require nodes to share their local decisions with neighboring agents, potentially exposing private information. Furthermore, gradient-tracking-based methods [ 5 , 6 ] inherently expose gradient information over iterations, creating additional vulnerabilities. Of particular concern is that local decisions often contain highly sensitive data, such as personal medical records [ 16 ] and precise locations of sensor nodes in surveillance networks [ 17 ] . Moreover, in multi-robot coordination systems [ 18 ] , even gradient information can expose movement directions and operational patterns, posing significant security risks. In addition, the frequent exchanges of model parameters (i.e., decision variables) may lead to the disclosure of the raw dataset [ 19 ] . TABLE I: Comparison to state-of-the-art algorithms with differential privacy. Here, for x_{a},x_{b}\in\mathbb{R}^{d} and i_{0}=1,\dots,N , we define the differentiable functions f_{i_{0}}^{(h)}:\mathbb{R}^{d}\rightarrow\mathbb{R},h=1,2 with gradients \nabla f_{i_{0}}^{(h)} and \Delta g_{i_{0}}^{(h)}=\nabla f_{i_{0}}^{(h)}(x_{a})-\nabla f_{i_{0}}^{(h)}(x_{b}) . We denote K as the number of iterations, and \theta\in(0,1) . Algorithm Problem DP Extra Diminishing Exact Convergence type guarantee conditions stepsize/noise convergence rate PrivSGP-VR [ 20 ] nonconvex (\epsilon,\delta) -DP bounded \|\nabla f_{i}-\nabla f\| stepsize ✗ \mathcal{O}(1/\sqrt{K}) DIFF2 [ 21 ] nonconvex (\epsilon,\delta) -DP bounded \|\nabla f_{i}\| stepsize ✗ \mathcal{O}(1/\sqrt{K}) [ 22 ] nonconvex ( \epsilon,\delta )-DP bounded \|\nabla f_{i}\| stepsize ✓ asymptotic [ 23 ] convex \epsilon -DP bounded \|\nabla f_{i}\| stepsize ✓ asymptotic DMSP [ 24 ] strongly convex \epsilon -DP bounded \|\nabla f_{i}\| stepsize,noise ✗ asymptotic DiaDSP [ 25 ] strongly convex \epsilon -DP bounded \|\nabla f^{(1)}_{i_{0}}-\nabla f^{(2)}_{i_{0}}\| noise ✗ \mathcal{O}(\theta^{K}) \Delta g_{i_{0}}^{(1)}=\Delta g_{i_{0}}^{(2)} eDP-TN [ 26 ] strongly convex \epsilon -DP bounded \|\nabla f^{(1)}_{i_{0}}-\nabla f^{(2)}_{i_{0}}\| noise ✓ \mathcal{O}(\theta^{K}) \Delta g_{i_{0}}^{(1)}=\Delta g_{i_{0}}^{(2)} PPDC [ 27 ] nonconvex \epsilon -DP bounded \|\nabla f_{i}\| noise ✗ \mathcal{O}(1/K) P-Ł condition ✗ \mathcal{O}(\theta^{K}) This paper nonconvex \epsilon -DP bounded \|\nabla f^{(1)}_{i_{0}}-\nabla f^{(2)}_{i_{0}}\| noise ✓ \mathcal{O}(1/K) P-Ł condition ✓ \mathcal{O}(\theta^{K}) To preserve local information, differential privacy (DP) has received significant attention in recent works. The core mechanism of DP involves injecting carefully designed noise into transmitted information, thereby preventing eavesdroppers from inferring private data based on their observations. In decentralized learning [ 20 , 21 ] , ( \epsilon,\delta )-DP is commonly adopted, where \epsilon quantifies the privacy guarantee against distinguishing outputs from adjacent datasets, allowing a \delta probability of failure. However, due to the accumulation of noise and the use of stochastic gradients, these methods can only guarantee sublinear convergence of \mathcal{O}(1/\sqrt{K}) to a neighborhood of the optimal solutions. While [ 22 ] achieves exact convergence via vanishing stepsizes, it sacrifices convergence rate, only ensuring asymptotic convergence. For stricter privacy requirements (such as protecting sensitive medical or financial data [ 28 ] ), \epsilon -DP ( \delta=0 ) is particularly suitable. Yet, static noises under \epsilon -DP lead to a accumulative explosion of parameters [ 29 ] , prompting existing \epsilon -DP methods [ 24 , 25 , 30 , 27 , 31 , 26 ] to employ decaying noises for convergence. Under strong convexity, the methods in [ 25 , 30 , 31 ] achieve linear convergence to a neighborhood of the optimum. Meanwhile, [ 27 ] achieves sublinear convergence to a neighborhood of stationarity for nonconvex objectives and linear convergence to the global optimum under the additional P-Ł condition. Notably, as is proven in [ 31 ] , gradient-tracking algorithms cannot achieve \epsilon -DP and exact convergence simultaneously, which limits the works in [ 24 , 25 , 30 , 27 , 31 ] to suboptimal convergence only. The recent studies [ 23 , 26 ] achieve exact convergence with \epsilon -DP. However, [ 23 ] relies on convexity and [ 26 ] requires more stringent strong convexity as well as additional assumptions, as is stated in Table I . In this paper, we design a D ecentralized P roximal P rimal-dual algorithm enabling D ouble P rivacy P rotection ( \text{DPP}^{2} ) for addressing a class of nonconvex optimization problems over multi-agent networks. In \text{DPP}^{2} , each node minimizes an augmented-Lagrangian-like function comprising a linearized objective function and a proximal term, which is followed by a dual ascent step. We then introduce an encryption strategy, called double privacy protection , which effectively protects local private information from being

Read the complete text