On the Convergence of a Noisy Gradient Method for Non-convex Distributed Resource Allocation: Saddle Point Escape
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915437368836096 |
|---|---|
| author | Qin, Lei Pu, Ye |
| author_facet | Qin, Lei Pu, Ye |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_06922 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Convergence of a Noisy Gradient Method for Non-convex Distributed Resource Allocation: Saddle Point Escape Qin, Lei Pu, Ye Optimization and Control 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. |
| title | On the Convergence of a Noisy Gradient Method for Non-convex Distributed Resource Allocation: Saddle Point Escape |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2508.06922 |