Search

Privacy leakage and Byzantine failures are two adverse factors to the intelligent decision-making process of multi-agent systems (MASs). Considering the presence of these two issues, this paper targets the resolution of a class of nonconvex optimization problems under the Polyak-{\L}ojasiewicz (P-{\L}) condition. To address this problem, we first identify and construct the adversary system model. To enhance the robustness of stochastic gradient descent methods, we mask the local gradients with Gaussian noises and adopt a resilient aggregation method self-centered clipping (SCC) to design a differentially private (DP) decentralized Byzantine-resilient algorithm, namely DP-SCC-PL, which simultaneously achieves differential privacy and Byzantine resilience. The convergence analysis of DP-SCC-PL is challenging since the convergence error can be contributed jointly by privacy-preserving and Byzantine-resilient mechanisms, as well as the nonconvex relaxation, which is addressed via seeking the contraction relationships among the disagreement measure of reliable agents before and after aggregation, together with the optimal gap. Theoretical results reveal that DP-SCC-PL achieves consensus among all reliable agents and sublinear (inexact) convergence with well-designed step-sizes. It has also been proved that if there are no privacy issues and Byzantine agents, then the asymptotic exact convergence can be recovered. Numerical experiments verify the utility, resilience, and differential privacy of DP-SCC-PL by tackling a nonconvex optimization problem satisfying the P-{\L} condition under various Byzantine attacks., Comment: 13 pages, 13 figures

This paper considers a class of noncooperative games in which the feasible decision sets of all players are coupled together by a coupled inequality constraint. Adopting the variational inequality formulation of the game, we first introduce a new local edge-based equilibrium condition and develop a distributed primal-dual proximal algorithm with full information. Considering challenges when communication delays occur, we devise an asynchronous distributed algorithm to seek a generalized Nash equilibrium. This asynchronous scheme arbitrarily activates one player to start new computations independently at different iteration instants, which means that the picked player can use the involved out-dated information from itself and its neighbors to perform new updates. A distinctive attribute is that the proposed algorithms enable the derivation of new distributed forward-backward-like extensions. In theoretical aspect, we provide explicit conditions on algorithm parameters, for instance, the step-sizes to establish a sublinear convergence rate for the proposed synchronous algorithm. Moreover, the asynchronous algorithm guarantees almost sure convergence in expectation under the same step-size conditions and some standard assumptions. An interesting observation is that our analysis approach improves the convergence rate of prior synchronous distributed forward-backward-based algorithms. Finally, the viability and performance of the proposed algorithms are demonstrated by numerical studies on the networked Cournot competition., Comment: 13 pages, 2 figures

Distributed optimization is manifesting great potential in multiple fields, e.g., machine learning, control, and resource allocation. Existing decentralized optimization algorithms require sharing explicit state information among the agents, which raises the risk of private information leakage. To ensure privacy security, combining information security mechanisms, such as differential privacy and homomorphic encryption, with traditional decentralized optimization algorithms is a commonly used means. However, this would either sacrifice optimization accuracy or incur heavy computational burden. To overcome these shortcomings, we develop a novel privacy-preserving decentralized optimization algorithm, called PPSD, that combines gradient tracking with a state decomposition mechanism. Specifically, each agent decomposes its state associated with the gradient into two substates. One substate is used for interaction with neighboring agents, and the other substate containing private information acts only on the first substate and thus is entirely agnostic to other agents. For the strongly convex and smooth objective functions, PPSD attains a $R$-linear convergence rate. Moreover, the algorithm can preserve the agents' private information from being leaked to honest-but-curious neighbors. Simulations further confirm the results.

This paper studies optimization problems over multi-agent systems, in which all agents cooperatively minimize a global objective function expressed as a sum of local cost functions. Each agent in the systems uses only local computation and communication in the overall process without leaking their private information. Based on the Barzilai-Borwein (BB) method and multi-consensus inner loops, a distributed algorithm with the availability of larger stepsizes and accelerated convergence, namely ADBB, is proposed. Moreover, owing to employing only row-stochastic weight matrices, ADBB can resolve the optimization problems over unbalanced directed networks without requiring the knowledge of neighbors' out-degree for each agent. Via establishing contraction relationships between the consensus error, the optimality gap, and the gradient tracking error, ADBB is theoretically proved to converge linearly to the globally optimal solution. A real-world data set is used in simulations to validate the correctness of the theoretical analysis., Comment: 33 pages, 8 figures

Distributed stochastic optimization, arising in the crossing and integration of traditional stochastic optimization, distributed computing and storage, and network science, has advantages of high efficiency and a low per-iteration computational complexity in resolving large-scale optimization problems. This paper concentrates on resolving a large-scale convex finite-sum optimization problem in a multi-agent system over unbalanced directed networks. To tackle this problem in an efficient way, a distributed consensus optimization algorithm, adopting the push-sum technique and a distributed loopless stochastic variance-reduced gradient (LSVRG) method with uncoordinated triggered probabilities, is developed and named Push-LSVRG-UP. Each agent under this algorithmic framework performs only local computation and communicates only with its neighbors without leaking their private information. The convergence analysis of Push-LSVRG-UP is relied on analyzing the contraction relationships between four error terms associated with the multi-agent system. Theoretical results provide an explicit feasible range of the constant step-size, a linear convergence rate, and an iteration complexity of Push-LSVRG-UP when achieving the globally optimal solution. It is shown that Push-LSVRG-UP achieves the superior characteristics of accelerated linear convergence, fewer storage costs, and a lower per-iteration computational complexity than most existing works. Meanwhile, the introduction of an uncoordinated probabilistic triggered mechanism allows Push-LSVRG-UP to facilitate the independence and flexibility of agents in computing local batch gradients. In simulations, the practicability and improved performance of Push-LSVRG-UP are manifested via resolving two distributed learning problems based on real-world datasets., Comment: 16 pages, 30 figures

Decentralized stochastic gradient algorithms resolve efficiently large-scale finite-sum optimization problems when all agents over networks are reliable. However, most of these algorithms are not resilient to adverse conditions, such as malfunctioning agents, software bugs, and cyber attacks. This paper aims to handle a class of general composite finite-sum optimization problems over multi-agent cyber-physical systems (CPSs) in the presence of an unknown number of Byzantine agents. Based on the proximal mapping method, variance-reduced (VR) techniques, and a norm-penalized approximation strategy, we propose a decentralized Byzantine-resilient and proximal-gradient algorithmic framework, dubbed Prox-DBRO-VR,which achieves an optimization and control goal using only local computations and communications. To reduce asymptotically the variance generated by evaluating the local noisy stochastic gradients, we incorporate two localized VR techniques (SAGA and LSVRG) into Prox-DBRO-VR to design Prox-DBRO-SAGA and Prox-DBRO-LSVRG. By analyzing the contraction relationships among the gradient-learning error, robust consensus condition, and optimality gap in a unified theoretical framework, it is demonstrated that both Prox-DBRO-SAGA and Prox-DBRO-LSVRG,with a well-designed constant (resp., decaying) step-size, converge linearly (resp., sublinearly) inside an error ball around the optimal solution to the original problem under standard assumptions. The trade-off between convergence accuracy and the number of Byzantine agents in both linear and sub-linear cases is also characterized. In simulation, the effectiveness and practicability of the proposed algorithms are manifested via resolving a decentralized sparse machine-learning problem over multi-agent CPSs under various Byzantine attacks., Comment: 17 pages, 13 figures

Average consensus is essential for multi-agent systems to achieve specific functions and is widely used in network control, information fusion, etc. In conventional average consensus algorithms, all agents reach an agreement by individual calculations and sharing information with their respective neighbors. Nevertheless, the information interactions that occur in the communication network may make sensitive information be revealed. In this paper, we develop a new privacy-preserving average consensus method for unbalanced digraphs. Specifically, we ensure privacy preservation by carefully embedding randomness in mixing weights to confuse communications and introducing an extra auxiliary parameter to mask the state-updated rule in the initial several iterations. In parallel, we exploit the intrinsic robustness of consensus dynamics to guarantee that the average consensus is precisely achieved. Theoretical results demonstrate that the designed algorithms can converge linearly to the exact average consensus value and can guarantee privacy preservation of agents against both honest-but-curious and eavesdropping attacks. The designed algorithms are fundamentally different compared to differential privacy based algorithms that enable privacy preservation via sacrificing consensus performance. Finally, numerical experiments validate the correctness of the theoretical findings.

We deal with a general distributed constrained online learning problem with privacy over time-varying networks, where a class of nondecomposable objectives are considered. Under this setting, each node only controls a part of the global decision, and the goal of all nodes is to collaboratively minimize the global cost over a time horizon $T$ while guarantees the security of the transmitted information. For such problems, we first design a novel generic algorithm framework, named as DPSDA, of differentially private distributed online learning using the Laplace mechanism and the stochastic variants of dual averaging method. Note that in the dual updates, all nodes of DPSDA employ the noise-corrupted gradients for more generality. Then, we propose two algorithms, named as DPSDA-C and DPSDA-PS, under this framework. In DPSDA-C, the nodes implement a circulation-based communication in the primal updates so as to alleviate the disagreements over time-varying undirected networks. In addition, for the extension to time-varying directed ones, the nodes implement the broadcast-based push-sum dynamics in DPSDA-PS, which can achieve average consensus over arbitrary directed networks. Theoretical results show that both algorithms attain an expected regret upper bound in $\mathcal{O}( \sqrt{T} )$ when the objective function is convex, which matches the best utility achievable by cutting-edge algorithms. Finally, numerical experiment results on both synthetic and real-world datasets verify the effectiveness of our algorithms., Comment: 16 pages, 6 figures

Human evaluation is becoming a necessity to test the performance of Chatbots. However, off-the-shelf settings suffer the severe reliability and replication issues partly because of the extremely high diversity of criteria. It is high time to come up with standard criteria and exact definitions. To this end, we conduct a through investigation of 105 papers involving human evaluation for Chatbots. Deriving from this, we propose five standard criteria along with precise definitions.

In this paper, we study convex optimization problems where agents of a network cooperatively minimize the global objective function which consists of multiple local objective functions. Different from most of the existing works, the local objective function of each agent is presented as the average of finite instantaneous functions. The intention of this work is to solve large-scale optimization problems where the local objective function is complicated and numerous. Integrating the gradient tracking algorithm with stochastic averaging gradient technology, we propose a novel distributed stochastic gradient tracking (termed as S-DIGing) algorithm. At each time instant, only one randomly selected gradient of a instantaneous function is computed and applied to approximate the gradient of local objection function. Based on a primal-dual interpretation of the S-DIGing algorithm, we show that the S-DIGing algorithm linearly converges to the global optimal solution when step-size lies in an explicit internal under the assumptions that the instantaneous functions are strongly convex and have Lipschitz-continuous gradient. Numerical experiments on the logistic regression problem are presented to demonstrate the practicability of the algorithm and correctness of the theoretical results., Comment: This work has been submitted to the IEEE for possible publication

This paper studies a class of distributed optimization algorithms by a set of agents, where each agent has only access to its own local convex objective function, and jointly minimizes the sum of the functions. The communications among agents are described by a sequence of time-varying directed graphs which are assumed to be uniformly strongly connected. A column stochastic mixing matrices is employed in the algorithm, which also exactly steers all the agents to asymptotically converge to a global and consensual optimal solution even under the assumption that the step-sizes are uncoordinated. Two fairly standard conditions for achieving the geometrical convergence rate are established under the assumption that the objective functions are strong convexity and have Lipschitz continuous gradient. The theoretical analysis shows that the distributed algorithm is capable of driving the whole network to geometrically converge to an optimal solution of the convex optimization problem as long as the uncoordinated step-sizes do not exceed some upper bounds. We also give an explicit analysis for the convergence rate of our algorithm through a different approach. Finally, simulation results illustrate the feasibility of the proposed algorithm and the theoretical analysis throughout this paper., Comment: 23 pages