On the Convergence of a Noisy Gradient Method for Non-convex Distributed Resource Allocation: Saddle Point Escape

2025/08/09 by Qin, Lei, Ye Pu, Pu, Ye
Computer Science · #Distributed Control Multi-Agent Systems #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Variational Analysis #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2508.06922

openalex publication_date 2025/08/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper considers a class of distributed resource allocation problems where each agent privately holds a smooth, potentially non-convex local objective, subject to a globally coupled equality constraint. Built upon the existing method, Laplacian-weighted Gradient Descent, we propose to add random perturbations to the gradient iteration to enable efficient escape from saddle points and achieve second-order convergence guarantees. We show that, with a sufficiently small fixed step size, the iterates of all agents converge to an approximate second-order optimal solution with high probability. Numerical experiments confirm the effectiveness of the proposed approach, demonstrating improved performance over standard weighted gradient descent in non-convex scenarios.

Citations

• Convergence Analysis of EXTRA in Non-convex Distributed Optimization
• Accelerated Distributed Allocation
• Second-order Properties of Noisy Distributed Gradient Descent
• Decentralized Nonconvex Optimization with Guaranteed Privacy and Accuracy
• 1st-Order Dynamics on Nonlinear Agents for Resource Allocation over Uniformly-Connected Networks
• Distributed Learning in Non-Convex Environments -- Part II: Polynomial\n Escape from Saddle-Points
• Improved Convergence Rates for Distributed Resource Allocation
• Gradient Descent Can Take Exponential Time to Escape Saddle Points
• How to Escape Saddle Points Efficiently
• Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition

Related

• Convergence Analysis of Noisy Distributed Gradient Descent for Non-convex Optimization -- Saddle Point Escape
• Second-order Properties of Noisy Distributed Gradient Descent
• Improved Convergence Rates for Distributed Resource Allocation
• Novel Distributed Algorithms Design for Nonsmooth Resource Allocation on Weight-Balanced Digraphs
• Distributed Dual Gradient Tracking for Resource Allocation in Unbalanced Networks