# Decentralized Nonconvex Optimization with Guaranteed Privacy and Accuracy arXiv: https://arxiv.org/abs/2212.07534 · HTML: https://mlsanity.com/paper/2212.07534/ ## Key facts - Cited by 10 papers in the map (data through 14 Oct 2026). - Builds on 31 of its 65 references that are in the map. - First posted on arXiv 14 Dec 2022. ## Builds on (most cited first, 30 of 31) - [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016) - [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021) - [Deep Leakage from Gradients](https://mlsanity.com/paper/1906.08935/) (2019) - [Differential Privacy Has Disparate Impact on Model Accuracy](https://mlsanity.com/paper/1905.12101/) (2019) - [Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator](https://mlsanity.com/paper/1801.05039/) (2018) - [Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition](https://mlsanity.com/paper/1503.02101/) (2015) - [Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication](https://mlsanity.com/paper/1902.00340/) (2019) - [No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis](https://mlsanity.com/paper/1704.00708/) (2017) - [NEXT: In-Network Nonconvex Optimization](https://mlsanity.com/paper/1602.00591/) (2016) - [Gradient Descent Can Take Exponential Time to Escape Saddle Points](https://mlsanity.com/paper/1705.10412/) (2017) - [Escaping Saddles with Stochastic Gradients](https://mlsanity.com/paper/1803.05999/) (2018) - [Collaborative Deep Learning in Fixed Topology Networks](https://mlsanity.com/paper/1706.07880/) (2017) - [On the Linear Convergence of the ADMM in Decentralized Consensus Optimization](https://mlsanity.com/paper/1307.5561/) (2013) - [Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture](https://mlsanity.com/paper/1511.03607/) (2015) - [The non-convex Burer-Monteiro approach works on smooth semidefinite programs](https://mlsanity.com/paper/1606.04970/) (2016) - [Policy Optimization for H2 Linear Control with H_∞ Robustness Guarantee: Implicit Regularization and Global Convergence](https://mlsanity.com/paper/1910.09496/) (2019) - [On Nonconvex Decentralized Gradient Descent](https://mlsanity.com/paper/1608.05766/) (2016) - [Communication-Efficient Distributed Deep Learning: A Comprehensive Survey](https://mlsanity.com/paper/2003.06307/) (2020) - [Differentially Private Distributed Optimization](https://mlsanity.com/paper/1401.2596/) (2014) - [Tailoring Gradient Methods for Differentially-Private Distributed Optimization](https://mlsanity.com/paper/2202.01113/) (2022) - [Decentralized Frank-Wolfe Algorithm for Convex and Non-convex Problems](https://mlsanity.com/paper/1612.01216/) (2016) - [Decentralized Stochastic Optimization with Inherent Privacy Protection](https://mlsanity.com/paper/2205.03884/) (2022) - [Non-Convex Distributed Optimization](https://mlsanity.com/paper/1512.00895/) (2015) - [Quantization enabled Privacy Protection in Decentralized Stochastic Optimization](https://mlsanity.com/paper/2208.04845/) (2022) - [Online ICA: Understanding Global Dynamics of Nonconvex Optimization via Diffusion Processes](https://mlsanity.com/paper/1808.09642/) (2018) - [Second-order Guarantees of Distributed Gradient Algorithms](https://mlsanity.com/paper/1809.08694/) (2018) - [Harnessing Smoothness to Accelerate Distributed Optimization](https://mlsanity.com/paper/1605.07112/) (2016) - [Gradient-tracking based Distributed Optimization with Guaranteed Optimality under Noisy Information Sharing](https://mlsanity.com/paper/2210.00551/) (2022) - [Annealing for Distributed Global Optimization](https://mlsanity.com/paper/1903.07258/) (2019) - [Distributed Gradient Methods for Nonconvex Optimization: Local and Global Convergence Guarantees](https://mlsanity.com/paper/2003.10309/) (2020) ## Built on by (most cited first, 10 of 10) - [Private (Stochastic) Non-Convex Optimization Revisited: Second-Order Stationary Points and Excess Risks](https://mlsanity.com/paper/2302.09699/) (2023) - [A survey on secure decentralized optimization and learning](https://mlsanity.com/paper/2408.08628/) (2024) - [Sparse Decentralized Federated Learning](https://mlsanity.com/paper/2308.16671/) (2023) - [Privacy-Preserving Distributed Optimization and Learning](https://mlsanity.com/paper/2403.00157/) (2024) - [Generalizing Differentially Private Decentralized Deep Learning with Multi-Agent Consensus](https://mlsanity.com/paper/2306.13892/) (2023) - [Locally Differentially Private Distributed Online Learning with Guaranteed Optimality](https://mlsanity.com/paper/2306.14094/) (2023) - [Distributed optimization: designed for federated learning](https://mlsanity.com/paper/2508.08606/) (2025) - [Decentralized Federated Learning by Partial Message Exchange](https://mlsanity.com/paper/2603.01730/) (2026) - [Immersion and Invariance-based Coding for Privacy-Preserving Federated Learning](https://mlsanity.com/paper/2409.17201/) (2024) - [Enhancing Privacy in Decentralized Min-Max Optimization: A Differentially Private Approach](https://mlsanity.com/paper/2508.07505/) (2025) ## Abstract (arXiv) Privacy protection and nonconvexity are two challenging problems in decentralized optimization and learning involving sensitive data. Despite some recent advances addressing each of the two problems separately, no results have been reported that have theoretical guarantees on both privacy protection and saddle/maximum avoidance in decentralized nonconvex optimization. We propose a new algorithm for decentralized nonconvex optimization that can enable both rigorous differential privacy and saddle/maximum avoiding performance. The new algorithm allows the incorporation of persistent additive noise to enable rigorous differential privacy for data samples, gradients, and intermediate optimization variables without losing provable convergence, and thus circumventing the dilemma of trading accuracy for privacy in differential privacy design. More interestingly, the algorithm is theoretically proven to be able to efficiently { guarantee accuracy by avoiding} convergence to local maxima and saddle points, which has not been reported before in the literature on decentralized nonconvex optimization. The algorithm is efficient in both communication (it only shares one variable in each iteration) and computation (it is encryption-free), and hence is promising for large-scale nonconvex optimization and learning involving high-dimensional optimization parameters. Numerical experiments for both a decentralized estimation problem and an Independent Component Analysis (ICA) problem confirm the effectiveness of the proposed approach.