XYXinlei Yi

Xinlei Yi

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Xinlei Yi has a total of 61 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Communication-Efficient Distributed Online Nonconvex Optimization With Time-Varying Constraints

    by Kunpeng Zhang, Lei Xu, Xinlei Yi, Guanghui Wen, Ming Cao, Karl H. Johansson, Tianyou Chai, Tao Yang

    This paper considers distributed online nonconvex optimization with time-varying inequality constraints, where the nonconvex local loss and convex local constraint functions can vary arbitrarily across iterations. For a time-varying directed graph, we propose two distributed bandit online primal–dual algorithms with compressed communication to efficiently utilize communication resources in the one-point and two-point bandit feedback settings, respectively. To measure the performance of the proposed algorithms, we use a network regret metric grounded in the first-order optimality condition associated with the variational inequality. We show that the compressed algorithm with one-point bandit feedback establishes an $\mathcal {O} ({{T^{\theta _{1}}}})$ network regret bound and an $\mathcal {O} ({T^{7/4 - {\theta _{1}}}})$ network cumulative constraint violation bound, where $T$ is the number of iterations and ${\theta _{1}} \in ({3/4,5/6}]$ is a user-defined trade-off parameter. When Slater's condition holds, the network cumulative constraint violation bound is reduced to $\mathcal {O} ({T^{5/2 - 2{\theta _{1}}}})$. In addition, we show that the compressed algorithm with two-point bandit feedback establishes an $\mathcal {O} ({{T^{\max \lbrace {1 - {\theta _{1}},{\theta _{1}}} \rbrace }}})$ network regret and an $\mathcal {O} ({T^{1 - {\theta _{1}}/2}})$ network cumulative constraint violation bounds, where ${\theta _{1}} \in ({0,1})$. Moreover, the network cumulative constraint violation bound is reduced to $\mathcal {O} ({T^{1 - {\theta _{1}}}})$ under Slater's condition. Finally, a simulation example is presented to validate the theoretical results.


  • Distributed Optimization by Network Flows With Spatio-Temporal Compression

    by Zihao Ren, Lei Wang, Xinlei Yi, Xi Wang, Deming Yuan, Tao Yang, Zhengguang Wu, Guodong Shi

    Several data compressors have been proposed in distributed optimization frameworks of network systems to reduce communication overhead in large-scale applications. In this paper, we demonstrate that effective information compression may occur over time or space during sequences of node communications in distributed algorithms, leading to the concept of spatio-temporal compressors. This abstraction classifies existing compressors and inspires new compressors as spatio-temporal compressors, with their effectiveness described by constructive stability criteria from nonlinear system theory. Subsequently, we incorporate these spatio-temporal compressors directly into standard continuous-time consensus flows and distributed primal-dual flows, establishing conditions ensuring exponential convergence. Additionally, we introduce a novel observer-based distributed primal-dual continuous flow integrated with spatio-temporal compressors, which provides broader convergence conditions. These continuous flows achieve exponential convergence to the global optimum when the objective function is strongly convex and can be discretized using Euler approximations. Finally, numerical simulations illustrate the versatility of the proposed spatio-temporal compressors and verify the convergence of algorithms.


  • Game-Theoretic Safe Multiagent Motion Planning With Reachability Analysis for Dynamic and Uncertain Environments

    by Wenbin Mai, Minghui Liwang, Xinlei Yi, Xiaoyu Xia, Seyyedali Hosseinalipour, Xianbin Wang

    Ensuring safe, robust, and scalable motion planning for multiagent systems in dynamic and uncertain environments is a persistent challenge, driven by complex interagent interactions, stochastic disturbances, and model uncertainties. To overcome these challenges, particularly the computational complexity of coupled decision-making and the need for proactive safety guarantees, we propose a reachability-enhanced dynamic potential game (RE-DPG) framework, which integrates game-theoretic coordination into reachability analysis. This approach formulates multiagent coordination as a dynamic potential game, where the Nash equilibrium (NE) defines optimal control strategies across agents. To enable scalability and decentralized execution, we develop a neighborhood-dominated iterative best response scheme, built upon an iterated $\varepsilon$-BR process that guarantees finite-step convergence to an $\varepsilon$-NE. This allows agents to compute strategies based on local interactions while ensuring theoretical convergence guarantees. Furthermore, to ensure safety under uncertainty, we integrate a multiagent forward reachable set mechanism into the cost function, explicitly modeling uncertainty propagation and enforcing collision avoidance constraints. Through both simulations and real-world experiments in 2-D and 3-D environments, we validate the effectiveness of RE-DPG across diverse operational scenarios.

  • Asymmetric Learning in Convex Games

    by Zifan Wang, Xinlei Yi, Yi Shen, Michael M. Zavlanos, Karl H. Johansson

    This paper considers convex games involving multiple agents that aim to minimize their own cost functions using locally available information. A common assumption in the study of such games is that the agents are symmetric, meaning that they have access to the same type of information. Here we lift this assumption, which is often violated in practice, and instead consider asymmetric agents; specifically, we assume some agents have access to first-order gradient information and others have access to the zeroth-order oracles (cost function evaluations). We propose an asymmetric learning algorithm that combines the agent information mechanisms. We analyze the regret and Nash equilibrium convergence of this algorithm for convex and strongly monotone games, respectively. Specifically, we show that our algorithm always performs between pure first- and zeroth-order methods, and can match the performance of these two extremes by adjusting the number of agents with access to zeroth-order oracles. Therefore, our algorithm incorporates the pure first- and zeroth-order methods as special cases. We provide numerical experiments on a market problem for both deterministic and risk-averse games to demonstrate the performance of the proposed algorithm.


  • One-Point Sampling for Distributed Bandit Convex Optimization With Time-Varying Constraints

    by Kunpeng Zhang, Lei Xu, Xinlei Yi, Guanghui Wen, Lihua Xie, Tianyou Chai, Tao Yang

    This paper considers the distributed bandit convex optimization problem with time-varying constraints. In this problem, the global loss function is the average of all the local convex loss functions, which are unknown beforehand. Each agent iteratively makes its own decision subject to time-varying inequality constraints which can be violated but are fulfilled in the long run. For a uniformly jointly strongly connected time-varying directed graph, a distributed bandit online primal–dual projection algorithm with one-point sampling is proposed. We show that sublinear dynamic network regret and network cumulative constraint violation (CCV) are achieved if the path–length of the benchmark also increases in a sublinear manner. In addition, an $\mathcal {O}({T^{3/4 + g}})$ static network regret bound and an $\mathcal {O}( {{T^{1 - {g}/2}}})$ network CCV bound are established, where $T$ is the total number of iterations and $g \in ( {0,1/4})$ is a trade-off parameter. Moreover, a reduced static network regret bound $\mathcal {O}( {{T^{2/3 + 4g /3}}})$ is established for strongly convex local loss functions. Finally, a numerical example is presented to validate the theoretical results.


  • Quantized Distributed Nonconvex Optimization Algorithms With Linear Convergence Under the Polyak–Łojasiewicz Condition

    by Lei Xu, Xinlei Yi, Jiayue Sun, Yang Shi, Karl H. Johansson, Tao Yang

    This article considers distributed optimization for minimizing the average of local nonconvex cost functions, by using local information exchange over undirected communication networks. To reduce the required communication capacity, we introduce an encoder–decoder scheme. By integrating it with distributed gradient tracking and proportional integral algorithms, respectively, we then propose two quantized distributed nonconvex optimization algorithms. Assuming the global cost function satisfies the Polyak–Łojasiewicz condition, which does not require the global cost function to be convex and the global minimizer is not necessarily unique, we show that our proposed algorithms linearly converge to a global optimal point. Moreover, we show that a low data rate is sufficient to guarantee linear convergence when the algorithm parameters are properly chosen. The theoretical results are illustrated by numerical examples.


  • Distributed Event-Triggered Bandit Convex Optimization With Time-Varying Constraints

    by Kunpeng Zhang, Xinlei Yi, Guanghui Wen, Ming Cao, Karl H. Johansson, Tianyou Chai, Tao Yang

    This paper considers the distributed bandit convex optimization problem with time-varying inequality constraints over a network of agents, where the goal is to minimize network regret and cumulative constraint violation. Existing distributed online algorithms solving this problem require that each agent broadcasts its decision to its neighbors at each iteration. However, communication resources are often limited. To better utilize communication resources, we propose a distributed event-triggered online primal–dual algorithm with two-point bandit feedback. Under several classes of appropriately chosen decreasing parameter sequences and non-increasing event-triggered threshold sequences, we establish dynamic network regret and network cumulative constraint violation bounds. These bounds are comparable to the results achieved by distributed event-triggered online algorithms with full-information feedback. Finally, a numerical example is provided to verify the theoretical results.


  • Distributed Online Convex Optimization With Time-Varying Constraints: Tighter Cumulative Constraint Violation Bounds Under Slater's Condition

    by Xinlei Yi, Xiuxian Li, Tao Yang, Lihua Xie, Yiguang Hong, Tianyou Chai, Karl H. Johansson

    This article considers distributed online convex optimization with time-varying constraints. In this setting, a network of agents makes decisions at each round, and then, only a portion of the loss function and a coordinate block of the constraint function are privately revealed to each agent. The loss and constraint functions are convex and can vary arbitrarily across rounds. The agents collaborate to minimize static network regret and network cumulative constraint violation. A novel distributed online algorithm with a vanishing stepsize is proposed and it achieves an $\mathcal {O}(T^{\max \lbrace c,1-c\rbrace })$ static network regret bound and an $\mathcal {O}(T^{1-c/2})$ network cumulative constraint violation bound, where $T$ is the number of rounds and $c\in (0,1)$ is a user-defined tradeoff parameter. When Slater's condition holds (i.e., there is a point that strictly satisfies the inequality constraints), the network cumulative constraint violation bound is reduced to $\mathcal {O}(T^{1-c})$. Moreover, if the loss functions are strongly convex, then static network regret bound is reduced to $\mathcal {O}(\log (T))$, and the network cumulative constraint violation bound is reduced to $\mathcal {O}(\sqrt{\log (T)T})$ and $\mathcal {O}(\log (T))$ without and with Slater's condition, respectively. To the best of the authors' knowledge, this article is the first to achieve tighter (network) cumulative constraint violation bounds for (distributed) online convex optimization with time-varying constraints under Slater's condition. Finally, the theoretical results are verified through numerical simulations.


  • Decentralized Federated Learning Algorithm Under Adversary Eavesdropping

    by Lei Xu, Danya Xu, Xinlei Yi, Chao Deng, Tianyou Chai, Tao Yang

    In this paper, we study the decentralized federated learning problem, which involves the collaborative training of a global model among multiple devices while ensuring data privacy. In classical federated learning, the communication channel between the devices poses a potential risk of compromising private information. To reduce the risk of adversary eavesdropping in the communication channel, we propose TRADE (transmit difference weight) concept. This concept replaces the decentralized federated learning algorithm's transmitted weight parameters with differential weight parameters, enhancing the privacy data against eavesdropping. Subsequently, by integrating the TRADE concept with the primal-dual stochastic gradient descent (SGD) algorithm, we propose a decentralized TRADE primal-dual SGD algorithm. We demonstrate that our proposed algorithm's convergence properties are the same as those of the primal-dual SGD algorithm while providing enhanced privacy protection. We validate the algorithm's performance on fault diagnosis task using the Case Western Reserve University dataset, and image classification tasks using the CIFAR-10 and CIFAR-100 datasets, revealing model accuracy comparable to centralized federated learning. Additionally, the experiments confirm the algorithm's privacy protection capability.


  • Linear Convergent Distributed Nash Equilibrium Seeking With Compression

    by Xiaomeng Chen, Yuchi Wu, Xinlei Yi, Minyi Huang, Ling Shi

    Information compression techniques are majorly employed to reduce communication cost over peer-to-peer links. In this article, we investigate distributed Nash equilibrium (NE) seeking problems in a class of noncooperative games over directed graphs with information compression. To improve communication efficiency, a compressed distributed NE seeking (C-DNES) algorithm is proposed to obtain an NE for games, where the differences between decision vectors and their estimates are compressed. The proposed algorithm is compatible with a general class of compressors, including both unbiased and biased compressors. Moreover, our approach only requires the adjacency matrix of the directed graph to be row-stochastic, in contrast to past works that relied on balancedness or specific global network parameters. It is shown that C-DNES not only inherits the advantages of conventional distributed NE algorithms, achieving linear convergence rate for games with restricted strongly monotone mappings, but also saves communication costs in terms of transmitted bits. Finally, numerical simulations illustrate the advantages of C-DNES in saving communication cost by an order of magnitude under different compressors.