Decentralized Inexact Proximal Gradient Method With Network-Independent Stepsizes for Convex Composite Optimization

• URL: http://arxiv.org/abs/2302.03238v1
• Date: Tue, 7 Feb 2023 03:50:38 GMT
• Title: Decentralized Inexact Proximal Gradient Method With Network-Independent Stepsizes for Convex Composite Optimization
• Authors: Luyao Guo, Xinli Shi, Jinde Cao, and Zihao Wang
• Abstract summary: This paper considers decentralized convex composite optimization over undirected and connected networks. A novel CTA (Combine-Then-Adapt)-based decentralized algorithm is proposed under uncoordinated network-independent constant stepsizes.
• Score: 39.352542703876104
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper considers decentralized convex composite optimization over undirected and connected networks, where the local loss function contains both smooth and nonsmooth terms. For this problem, a novel CTA (Combine-Then-Adapt)-based decentralized algorithm is proposed under uncoordinated network-independent constant stepsizes. Particularly, the proposed algorithm only needs to approximately solve a sequence of proximal mappings, which benefits the decentralized composite optimization where the proximal mappings of the nonsmooth loss functions may not have analytic solutions. For the general convex case, we prove the O(1/k) convergence rate of the proposed algorithm, which can be improved to o(1/k) if the proximal mappings are solved exactly. Moreover, with metric subregularity, we establish the linear convergence rate. Finally, the numerical experiments demonstrate the efficiency of the algorithm.

Related papers

• Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks [57.24087627267086]
  We consider the task of minimizing the sum of convex functions stored in a decentralized manner across the nodes of a communication network. Lower bounds on the number of decentralized communications and (sub)gradient computations required to solve the problem have been established. We develop the first optimal algorithm that matches these lower bounds and offers substantially improved theoretical performance compared to the existing state of the art.
  arXiv  Detail & Related papers  (2024-05-28T10:28:45Z)
• Decentralized Sum-of-Nonconvex Optimization [42.04181488477227]
  We consider the optimization problem of the sum-of-non function, i.e., a guarantee function that is the average non-consensus number. We propose an accelerated decentralized first-order algorithm by techniques of gradient, tracking into the rate, and multi-consensus.
  arXiv  Detail & Related papers  (2024-02-04T05:48:45Z)
• On Linear Convergence of PI Consensus Algorithm under the Restricted Secant Inequality [5.35599092568615]
  This paper considers solving distributed optimization problems in peer-to-peer multi-agent networks. By using the proportional-integral (PI) control strategy, various algorithms with fixed stepsize have been developed.
  arXiv  Detail & Related papers  (2023-09-30T15:54:52Z)
• Composite Optimization Algorithms for Sigmoid Networks [3.160070867400839]
  We propose the composite optimization algorithms based on the linearized proximal algorithms and the alternating direction of multipliers. Numerical experiments on Frank's function fitting show that the proposed algorithms perform satisfactorily robustly.
  arXiv  Detail & Related papers  (2023-03-01T15:30:29Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  This paper studies first-order algorithms for solving fully composite optimization problems convex compact sets. We leverage the structure of the objective by handling differentiable and non-differentiable separately, linearizing only the smooth parts.
  arXiv  Detail & Related papers  (2023-02-24T18:41:48Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  We consider the task of minimizing the sum of smooth and strongly convex functions stored in a decentralized manner across the nodes of a communication network. We design two optimal algorithms that attain these lower bounds. We corroborate the theoretical efficiency of these algorithms by performing an experimental comparison with existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-06-08T15:54:44Z)
• Distributed Stochastic Consensus Optimization with Momentum for Nonconvex Nonsmooth Problems [45.88640334610308]
  This paper presents a new distributed optimization algorithm for non-smooth problems. We show that the proposed algorithm can achieve an overcal communication. Experiments are presented to illustrate the effectiveness of the proposed algorithms.
  arXiv  Detail & Related papers  (2020-11-10T13:12:21Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope. Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
  arXiv  Detail & Related papers  (2020-06-11T17:43:19Z)
• Second-Order Guarantees in Centralized, Federated and Decentralized Nonconvex Optimization [64.26238893241322]
  Simple algorithms have been shown to lead to good empirical results in many contexts. Several works have pursued rigorous analytical justification for studying non optimization problems. A key insight in these analyses is that perturbations play a critical role in allowing local descent algorithms.
  arXiv  Detail & Related papers  (2020-03-31T16:54:22Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.