Search

Distributed optimization methods with probabilistic local updates have recently gained attention for their provable ability to communication acceleration. Nevertheless, this capability is effective only when the loss function is smooth and the network is sufficiently well-connected. In this paper, we propose the first linear convergent method MG-Skip with probabilistic local updates for nonsmooth distributed optimization. Without any extra condition for the network connectivity, MG-Skip allows for the multiple-round gossip communication to be skipped in most iterations, while its iteration complexity is $\mathcal{O}\left(\kappa \log \frac{1}{\epsilon}\right)$ and communication complexity is only $\mathcal{O}\left(\sqrt{\frac{\kappa}{(1-\rho)}} \log \frac{1}{\epsilon}\right)$, where $\kappa$ is the condition number of the loss function and $\rho$ reflects the connectivity of the network topology. To the best of our knowledge, MG-Skip achieves the best communication complexity when the loss function has the smooth (strongly convex)+nonsmooth (convex) composite form.

The ProxSkip algorithm for decentralized and federated learning is gaining increasing attention due to its proven benefits in accelerating communication complexity while maintaining robustness against data heterogeneity. However, existing analyses of ProxSkip are limited to the strongly convex setting and do not achieve linear speedup, where convergence performance increases linearly with respect to the number of nodes. So far, questions remain open about how ProxSkip behaves in the non-convex setting and whether linear speedup is achievable. In this paper, we revisit decentralized ProxSkip and address both questions. We demonstrate that the leading communication complexity of ProxSkip is $\mathcal{O}\left(\frac{p\sigma^2}{n\epsilon^2}\right)$ for non-convex and convex settings, and $\mathcal{O}\left(\frac{p\sigma^2}{n\epsilon}\right)$ for the strongly convex setting, where $n$ represents the number of nodes, $p$ denotes the probability of communication, $\sigma^2$ signifies the level of stochastic noise, and $\epsilon$ denotes the desired accuracy level. This result illustrates that ProxSkip achieves linear speedup and can asymptotically reduce communication overhead proportional to the probability of communication. Additionally, for the strongly convex setting, we further prove that ProxSkip can achieve linear speedup with network-independent stepsizes.

This paper proposes a novel CTA (Combine-Then-Adapt)-based decentralized algorithm for solving convex composite optimization problems over undirected and connected networks. The local loss function in these problems contains both smooth and nonsmooth terms. The proposed algorithm uses uncoordinated network-independent constant stepsizes and only needs to approximately solve a sequence of proximal mappings, which is advantageous for solving decentralized composite optimization problems where the proximal mappings of the nonsmooth loss functions may not have analytical solutions. For the general convex case, we prove an O(1/k) convergence rate of the proposed algorithm, which can be improved to o(1/k) if the proximal mappings are solved exactly. Furthermore, with metric subregularity, we establish a linear convergence rate for the proposed algorithm. Numerical experiments demonstrate the efficiency of the algorithm.

To address the privacy leakage problem in decentralized composite convex optimization, we proposes a novel differentially private decentralized primal--dual algorithm named DP-RECAL with operator splitting method and relay communication mechanism. We study the relationship between communication and privacy leakage, thus defining a new measure: local communication involvement (LCI). To the best of our knowledge, compared with existing differentially private algorithms, DP-RECAL is the first to take advantage of the relay communication mechanism to experience less LCI so as to reduce the overall privacy budget. In addition, we prove that DP-RECAL is convergent with uncoordinated network-independent stepsizes and establish the linear convergence rate of DP-RECAL under metric subregularity. Furthermore, taking the least squares problem as an example, DP-RECAL presents better privacy performance and communication complexity than listed differentially private decentralized algorithms. Numerical experiments on real-world datasets verify our analysis results and demonstrate that DP-RECAL can defend deep leakage from gradients (DLG) attacks.

In this paper, we propose a novel primal-dual proximal splitting algorithm (PD-PSA), named BALPA, for the composite optimization problem with equality constraints, where the loss function consists of a smooth term and a nonsmooth term composed with a linear mapping. In BALPA, the dual update is designed as a proximal point for a time-varying quadratic function, which balances the implementation of primal and dual update and retains the proximity-induced feature of classic PD-PSAs. In addition, by this balance, BALPA eliminates the inefficiency of classic PD-PSAs for composite optimization problems in which the Euclidean norm of the linear mapping or the equality constraint mapping is large. Therefore, BALPA not only inherits the advantages of simple structure and easy implementation of classic PD-PSAs but also ensures a fast convergence when these norms are large. Moreover, we propose a stochastic version of BALPA (S-BALPA) and apply the developed BALPA to distributed optimization to devise a new distributed optimization algorithm. Furthermore, a comprehensive convergence analysis for BALPA and S-BALPA is conducted, respectively. Finally, numerical experiments demonstrate the efficiency of the proposed algorithms.

In this paper, we propose a novel Dual Inexact Splitting Algorithm (DISA) for distributed convex composite optimization problems, where the local loss function consists of a smooth term and a possibly nonsmooth term composed with a linear mapping. DISA, for the first time, eliminates the dependence of the convergent step-size range on the Euclidean norm of the linear mapping, while inheriting the advantages of the classic Primal-Dual Proximal Splitting Algorithm (PD-PSA): simple structure and easy implementation. This indicates that DISA can be executed without prior knowledge of the norm, and tiny step-sizes can be avoided when the norm is large. Additionally, we prove sublinear and linear convergence rates of DISA under general convexity and metric subregularity, respectively. Moreover, we provide a variant of DISA with approximate proximal mapping and prove its global convergence and sublinear convergence rate. Numerical experiments corroborate our theoretical analyses and demonstrate a significant acceleration of DISA compared to existing PD-PSAs.