Search

The push-sum algorithm is probably the most important distributed averaging approach over directed graphs, which has been applied to various problems including distributed optimization. This paper establishes the explicit absolute probability sequence for the push-sum algorithm, and based on which, constructs quadratic Lyapunov functions for push-sum based distributed optimization algorithms. As illustrative examples, the proposed novel analysis tool can improve the convergence rates of the subgradient-push and stochastic gradient-push, two important algorithms for distributed convex optimization over unbalanced directed graphs. Specifically, the paper proves that the subgradient-push algorithm converges at a rate of $O(1/\sqrt{t})$ for general convex functions and stochastic gradient-push algorithm converges at a rate of $O(1/t)$ for strongly convex functions, over time-varying unbalanced directed graphs. Both rates are respectively the same as the state-of-the-art rates of their single-agent counterparts and thus optimal, which closes the theoretical gap between the centralized and push-sum based (sub)gradient methods. The paper further proposes a heterogeneous push-sum based subgradient algorithm in which each agent can arbitrarily switch between subgradient-push and push-subgradient. The heterogeneous algorithm thus subsumes both subgradient-push and push-subgradient as special cases, and still converges to an optimal point at an optimal rate. The proposed tool can also be extended to analyze distributed weighted averaging., arXiv admin note: substantial text overlap with arXiv:2203.16623, arXiv:2303.17060

The paper proposes a heterogeneous push-sum based subgradient algorithm for multi-agent distributed convex optimization in which each agent can arbitrarily switch between subgradient-push and push-subgradient at each time. It is shown that the heterogeneous algorithm converges to an optimal point at an optimal rate over time-varying directed graphs., Comment: arXiv admin note: text overlap with arXiv:2203.16623

This paper considers a distributed optimization problem in the presence of Byzantine agents capable of introducing untrustworthy information into the communication network. A resilient distributed subgradient algorithm is proposed based on graph redundancy and objective redundancy. It is shown that the algorithm causes all non-Byzantine agents' states to asymptotically converge to the same optimal point under appropriate assumptions. A partial convergence rate result is also provided., This version fixes the incorrect statements of Proposition 3 and Theorem 2 in the last version

In decentralized cooperative multi-agent reinforcement learning, agents can aggregate information from one another to learn policies that maximize a team-average objective function. Despite the willingness to cooperate with others, the individual agents may find direct sharing of information about their local state, reward, and value function undesirable due to privacy issues. In this work, we introduce a decentralized actor-critic algorithm with TD error aggregation that does not violate privacy issues and assumes that communication channels are subject to time delays and packet dropouts. The cost we pay for making such weak assumptions is an increased communication burden for every agent as measured by the dimension of the transmitted data. Interestingly, the communication burden is only quadratic in the graph size, which renders the algorithm applicable in large networks. We provide a convergence analysis under diminishing step size to verify that the agents maximize the team-average objective function.

This paper considers a resilient high-dimensional constrained consensus problem and studies a resilient distributed algorithm for complete graphs. For convex constrained sets with a singleton intersection, a sufficient condition on feasibility redundancy and set regularity for reaching a desired consensus exponentially fast in the presence of Byzantine agents is derived, which can be directly applied to polyhedral sets. A necessary condition on feasibility redundancy for the resilient constrained consensus problem to be solvable is also provided., Comment: to appear in ACC 2022

The push-sum based subgradient is an important method for distributed convex optimization over unbalanced directed graphs, which is known to converge at a rate of $O(\ln t/\sqrt{t})$. This paper shows that the push-subgradient algorithm actually converges at a rate of $O(1/\sqrt{t})$, which is the same as that of the single-agent subgradient and thus optimal. The proposed tool for analyzing push-sum based algorithms is of independent interest.

This paper considers a novel multi-agent linear stochastic approximation algorithm driven by Markovian noise and general consensus-type interaction, in which each agent evolves according to its local stochastic approximation process which depends on the information from its neighbors. The interconnection structure among the agents is described by a time-varying directed graph. While the convergence of consensus-based stochastic approximation algorithms when the interconnection among the agents is described by doubly stochastic matrices (at least in expectation) has been studied, less is known about the case when the interconnection matrix is simply stochastic. For any uniformly strongly connected graph sequences whose associated interaction matrices are stochastic, the paper derives finite-time bounds on the mean-square error, defined as the deviation of the output of the algorithm from the unique equilibrium point of the associated ordinary differential equation. For the case of interconnection matrices being stochastic, the equilibrium point can be any unspecified convex combination of the local equilibria of all the agents in the absence of communication. Both the cases with constant and time-varying step-sizes are considered. In the case when the convex combination is required to be a straight average and interaction between any pair of neighboring agents may be uni-directional, so that doubly stochastic matrices cannot be implemented in a distributed manner, the paper proposes a push-sum-type distributed stochastic approximation algorithm and provides its finite-time bound for the time-varying step-size case by leveraging the analysis for the consensus-type algorithm with stochastic matrices and developing novel properties of the push-sum algorithm.

Adversarial attacks during training can strongly influence the performance of multi-agent reinforcement learning algorithms. It is, thus, highly desirable to augment existing algorithms such that the impact of adversarial attacks on cooperative networks is eliminated, or at least bounded. In this work, we consider a fully decentralized network, where each agent receives a local reward and observes the global state and action. We propose a resilient consensus-based actor-critic algorithm, whereby each agent estimates the team-average reward and value function, and communicates the associated parameter vectors to its immediate neighbors. We show that in the presence of Byzantine agents, whose estimation and communication strategies are completely arbitrary, the estimates of the cooperative agents converge to a bounded consensus value with probability one, provided that there are at most $H$ Byzantine agents in the neighborhood of each cooperative agent and the network is $(2H+1)$-robust. Furthermore, we prove that the policy of the cooperative agents converges with probability one to a bounded neighborhood around a local maximizer of their team-average objective function under the assumption that the policies of the adversarial agents asymptotically become stationary.

YiXuan Lin,1 Jinju Li,1 Di Wu,1 FanJing Wang,1 ZhaoHui Fang,2,3 GuoMing Shen1 1Graduate School of Anhui University of Chinese Medicine, Hefei, Anhui, People’s Republic of China; 2Department of Endocrinology, The First Affiliated Hospital of Anhui University of Traditional Chinese Medicine, Hefei, Anhui, People’s Republic of China; 3Anhui Academic of Traditional Chinese Medicine Diabetes Research Institute, Hefei, Anhui, People’s Republic of ChinaCorrespondence: ZhaoHui Fang; GuoMing Shen Tel +86-13085513100Email fangzhaohui9097@163.com; shengm_66@163.comBackground: Type 2 diabetes mellitus (T2DM) is one of the most common chronic diseases in the world with complicated pathogenesis. This study aimed to identify differentially expressed genes (DEGs) and molecular pathways in T2DM using bioinformatics analysis.Materials and Methods: To explore potential therapeutic targets for T2DM, we analyzed three microarray datasets (GSE50397, GSE38642, and GSE44035) acquired from the Gene Expression Omnibus (GEO) database. DEGs between T2DM islet and normal islet were picked out by the GEO2R tool and Venn diagram software. Gene Ontology (GO) function and Kyoto Encyclopedia of Genes and Genomes (KEGG) pathway enrichment analysis were performed using the Database for Annotation, Visualization, and Integrated Discovery (DAVID) to identify the pathways and functional annotation of DEGs. Then, protein–protein interaction (PPI) of these DEGs was visualized by Cytoscape with Search Tool for the Retrieval of Interacting Genes/Proteins (STRING).Results: In total, we identified 36 DEGs in the three datasets, including 32 up-regulated genes and four down-regulated genes. The improved functions and pathways of the DEGs enriched in cytokine–cytokine receptor interaction, pathways in cancer, PI3K-Akt signaling pathway, and Rheumatoid arthritis. Among them, ten hub genes with a high degree of connectivity were selected. Furthermore, via the re-analysis of DAVID, four genes (IL6, MMP3, MMP1, and IL11) were significantly enriched in the Rheumatoid arthritis pathway.Conclusion: Our study, based on the GEO database, identified four significant up-regulated DEGs and provided novel targets for diagnosis and treatment of T2DM.Keywords: bioinformatics analysis, microarray, differentially expressed genes, type 2 diabetes mellitus