Multi-armed Bandit motivates methods with provable upper bounds on regret and also the counterpart lower bounds have been extensively studied in this context. Recently, Multi-agent Multi-armed Bandit has gained significant traction in various domains, where individual clients face bandit problems in a distributed manner and the objective is the overall system performance, typically measured by regret. While efficient algorithms with regret upper bounds have emerged, limited attention has been given to the corresponding regret lower bounds, except for a recent lower bound for adversarial settings, which, however, has a gap with let known upper bounds. To this end, we herein provide the first comprehensive study on regret lower bounds across different settings and establish their tightness. Specifically, when the graphs exhibit good connectivity properties and the rewards are stochastically distributed, we demonstrate a lower bound of order $O(\log T)$ for instance-dependent bounds and $\sqrt{T}$ for mean-gap independent bounds which are tight. Assuming adversarial rewards, we establish a lower bound $O(T^{\frac{2}{3}})$ for connected graphs, thereby bridging the gap between the lower and upper bound in the prior work. We also show a linear regret lower bound when the graph is disconnected. These lower bounds are made possible through our newly constructed instances. In the numerical study, we assess the performance of various algorithms on these hard instances. While previous works have explored these settings with upper bounds, we provide a thorough study on tight lower bounds.

We study the distributed multi-agent multi-armed bandit problem with heterogeneous rewards over random communication graphs. Uniquely, at each time step $t$ agents communicate over a time-varying random graph $\mathcal{G}\_t$ generated by applying the Erdős–Rényi model to a fixed connected base graph $\mathcal{G}$ (for classical Erdos-Rényi graphs, $\mathcal{G}$ is a complete graph), where each potential edge in $\mathcal{G}$ is randomly and independently present with the link probability $p$. Notably, the resulting random graph is not necessarily connected at each time step. Each agent's arm rewards follow time-invariant distributions, and the reward distribution for the same arm may differ across agents. The goal is to minimize the cumulative expected regret relative to the global mean reward of each arm, defined as the average of that arm’s mean rewards across all agents. To this end, we propose a fully distributed algorithm that integrates the arm elimination strategy with the random gossip algorithm. We theoretically show that the regret upper bound is of order $\log T$ and is highly interpretable, where $T$ is the time horizon. It includes the optimal centralized regret $\mathcal O\left(\sum_{k: \Delta_k>0} \frac{\log T}{\Delta_k}\right)$ and an additional term $\mathcal O\left(\frac{N^2 \log T}{p \lambda_{N-1}(\operatorname{Lap}(\mathcal{G}))} + \frac{KN^2 \log T}{p}\right)$ where $N$ and $K$ denote the total number of agents and arms, respectively. This term reflects the impact of $\mathcal G$'s algebraic connectivity $\lambda_{N-1}(\operatorname{Lap}(\mathcal{G}))$ and the link probability $p$, and thus highlights a fundamental trade-off between communication efficiency and regret. As a by-product, we show a nearly optimal regret lower bound. Finally, our numerical experiments not only show the superiority of our algorithm over existing benchmarks, but also validate the theoretical regret scaling with problem complexity.

The federated learning (FL) client selection scheme can effectively mitigate global model performance degradation caused by the random aggregation of clients with heterogeneous data. Simultaneously, research has exposed FL’s susceptibility to backdoor attacks. However herein lies the dilemma, traditional client selection methods and backdoor defenses stand at odds, so their integration is an elusive goal. To resolve this, we introduce Grace, a resilient client selection framework blending combinational class sampling with data augmentation. On the client side, Grace first proposes a local model purification method, fortifying the model’s defenses by bolstering its innate robustness. After, local class representations are extracted for server-side client selection. This approach not only shields benign models from backdoor tampering but also allows the server to glean insights into local class representations without infringing upon the client’s privacy. On the server side, Grace introduces a novel representation combination sampling method. Clients are selected based on the interplay of their class representations, a strategy that simultaneously weeds out malicious actors and draws in clients whose data holds unique value. Our extensive experiments highlight Grace’s capabilities. The results are compelling: Grace enhances defense performance by over 50% compared to state-of-the-art (SOTA) backdoor defenses, and, in the best case, improves accuracy by 3.19% compared to SOTA client selection schemes. Consequently, Grace achieves substantial advancements in both security and accuracy.

Multidimensional range queries are typical database operations used to retrieve data. With the development of cloud computing, outsourcing data storage and queries to a cloud server is an attractive choice for data owners; however, this choice involves well-known privacy issues. To preserve data privacy, data should be encrypted before they are outsourced to the cloud. Therefore, exploring multidimensional range queries on encrypted data has important theoretical and practical significance. Certain privacy-preserving schemes have been proposed to support multidimensional range queries on encrypted data. However, these schemes exhibit either poor privacy performance or poor computational or communication performance. This makes such schemes impractical for resource-constrained scenarios such as Internet of Things (IoT) environments. To improve security and efficiency in making them applicable to IoT environments, we propose lightweight secure vector comparison and secure double-blind protocols as building blocks to construct an efficient scheme, named the fully privacy-preserving multidimensional range queries scheme (FPMRQ), and prove that FPMRQ can resist database reconstruction and query-recovery attacks. To improve communication efficiency, we adopt methods to pack multidimensional data into single-dimensional data and aggregate multiple data records into a single record of data. Finally, we conducted numerous experiments on real-world data sets to examine the efficiency of FPMRQ, and the experimental results show that FPMRQ significantly improves the computational efficiency (almost three orders of magnitude faster) and communication efficiency (at least$7.15\times $faster) in comparison with existing schemes with the same security level. These results demonstrate the practicality of the FPMRQ for resource-restrained environments, such as IoT.

There is substantial attention to federated learning with its ability to train a powerful global model collaboratively while protecting data privacy. Despite its many advantages, federated learning is vulnerable to backdoor attacks, where an adversary injects malicious weights into the global model, making the global model's targeted predictions incorrect. Existing defenses based on identifying and eliminating malicious weights ignore the similarity variation of the local weights during iterations in the malicious model detection and the presence of benign weights in the malicious model during the malicious local weight elimination, resulting in a poor defense and a degradation of global model accuracy. In this paper, we defend against backdoor attacks from the perspective of local models. First, a malicious model detection method based on interpretability techniques is proposed. The method appends a sampling check after clustering to identify malicious models accurately. We further design a malicious local weight elimination method based on local weight contributions. This method preserves the benign weights in the malicious model to maintain their contributions to the global model. Finally, we analyze the security of the proposed method in terms of model closeness and then verify the effectiveness of the proposed method through experiments. In comparison with existing defenses, the results show that BADFL improves the global model accuracy by 23.14% while reducing the attack success rate to 0.04% in the best case.

We study Pareto optimality in multi-objective multi-armed bandit by providing a formulation of adversarial multi-objective multi-armed bandit and defining its Pareto regrets that can be applied to both stochastic and adversarial settings. The regrets do not rely on any scalarization functions and reflect Pareto optimality compared to scalarized regrets. We also present new algorithms assuming both with and without prior information of the multi-objective multi-armed bandit setting. The algorithms are shown optimal in adversarial settings and nearly optimal up to a logarithmic factor in stochastic settings simultaneously by our established upper bounds and lower bounds on Pareto regrets. Moreover, the lower bound analyses show that the new regrets are consistent with the existing Pareto regret for stochastic settings and extend an adversarial attack mechanism from bandit to the multi-objective one.

We study a decentralized multi-agent multi-armed bandit problem in which multiple clients are connected by time dependent random graphs provided by an environment. The reward distributions of each arm vary across clients and rewards are generated independently over time by an environment based on distributions that include both sub-exponential and sub-gaussian distributions. Each client pulls an arm and communicates with neighbors based on the graph provided by the environment. The goal is to minimize the overall regret of the entire system through collaborations. To this end, we introduce a novel algorithmic framework, which first provides robust simulation methods for generating random graphs using rapidly mixing markov chains or the random graph model, and then combines an averaging-based consensus approach with a newly proposed weighting technique and the upper confidence bound to deliver a UCB-type solution. Our algorithms account for the randomness in the graphs, removing the conventional doubly stochasticity assumption, and only require the knowledge of the number of clients at initialization. We derive optimal instance-dependent regret upper bounds of order $\log{T}$ in both sub-gaussian and sub-exponential environments, and a nearly optimal instance-free regret upper bound of order $\sqrt{T}\log T$ up to a $\log T$ factor. Importantly, our regret bounds hold with high probability and capture graph randomness, whereas prior works consider expected regret under assumptions and require more stringent reward distributions.

Federated learning (FL) can push the limitation of "Data Island" while protecting data privacy has been a broad concern.However, the centralised FL is vulnerable to a single-point failure.While decentralised and tamper-proof blockchains can cope with the above issues, it is difficult to find a benign benchmark gradient and eliminate the poisoning attack in the later stage of global model aggregation.To address the above problems, we present a global to local based privacy-preserving federated consensus scheme against poisoning attacks (FedG2L).This scheme can effectively reduce the influence of poisoning attacks on model accuracy.In the global aggregation stage, a gradient-similarity-based secure consensus algorithm (SecPBFT) is designed to eliminate malicious gradients.During this procedure, the gradient of the data owner will not be leaked.Then, we propose an improved ACGAN algorithm to generate local data to further update the model without poisoning attacks.Finally, we theoretically prove the security and correctness of our scheme.Experimental results demonstrated that the model accuracy is improved by at least 55% than no defense scheme, and the attack success rate is reduced by more than 60%.

Federated learning is good for building better cooperative intelligent transportation system (C-ITS). Intellectual property protection in C-ITS brings many benefits to all vehicles. Although the protection of model intellectual property by watermark has received much research attention, the existing works only deploy watermark in centralized models. Due to the difference of watermark distribution among vehicles, the global model accuracy of watermark in federated learning is significantly reduced or the local watermark is invalid. To solve these problems, we propose a multi-party entangled watermark algorithm in federated learning. Specifically, in the local training, we propose a watermark enhancement algorithm, which solves the problem of local watermark failure. Then, in the global aggregation, we propose an entanglement aggregation algorithm, which solves the problem of a great loss of global model accuracy. We conduct extensive experiments on public datasets to show the superiority of our proposal. The results show that our scheme can obtain more than 16% and 31% advantages in model accuracy and watermark success rate, respectively, compared with existing watermark schemes in federated learning.

A constrained shortest distance (CSD) query calculates the shortest distance between two vertices of a graph and places constraints on certain factors so as not to exceed corresponding thresholds. With the development of cloud computing, outsourcing graph data storage and the computation of CSD queries to a cloud platform (CP) are an attractive choice for graph owners; however, this choice is accompanied by well-known privacy issues. Certain privacy-preserving schemes have been proposed to support CSD queries on encrypted graphs, but all such schemes consider only single-CSD queries, even though, in practical applications, users may need to set two or more constraints when executing the shortest distance query. Additionally, existing schemes disclose too much private information to the CP. To address these considerable problems, we propose a strong privacy-preserving CSD query scheme called SPCS, which realizes accurate double-CSD queries without disclosing any critical private information. We prove that SPCS does not reveal any private information to the CP except for the number of vertices and conduct numerous experiments on real-world data sets to test this scheme’s efficiency. The experimental results show that SPCS is practical, especially in its computational efficiency in the graph-encryption phase, which is higher than that of available, state-of-the-art schemes.

In recent decades, multi-objective multifactorial evolutionary algorithm (MOMFEA) has become a very promising research direction. How to achieve effective knowledge transfer between similar tasks is the key issue to affect the performance of the algorithm. In this paper, an adaptive MOMFEA (AMOMFEA) is proposed by exploiting the mixture Gaussian distribution of the population distributions of related tasks to help solve the target task. Wasserstein distance is used to measure the inter-task relevance in that the weight coefficient in the mixture distribution is proportional to the inter-task relevance. Experimental results on benchmark problems validate the effectiveness and efficiency of the proposed method in comparison with MOMFEA and NSGA-II.

Nowadays, in machine learning based intrusion detection systems, ensemble learning is a commonly adopted method to improve the detection accuracy. Unfortunately, the existing works have not considered the accumulation and reuse of historical knowledge, as well as the sensitivity of the detection model to different types of attacks, which leads to a low detection accuracy. To address the issue, this article proposes a model based on sustainable ensemble learning. In the model training stage, by taking the individual classifiers probability output and classification confidence as the training data, we build multi-class regression models such that ensemble learning adapts to different attacks. Besides, in the updating stage, an iterative updating method is presented, where the parameters and decision results of the historical model are added to the training process of the new ensemble model to realize the incremental learning. Experiment results show that the proposed model significantly outperforms the existing solutions in terms of detection accuracy, false alarm, stability and robustness.

Multi-stage attack is a new trend of cyber attack. It is difficult for existing schemes to identify multiple stages in an attack period and associate independent stages. To address these issues, we design a long and short-term memory network (LSTM) based on multi-feature layer. First, we introduce stage features layer, the historical data is stored and calculated to identify the different stages of variable durations in multi-stage attacks. Then, the time-series features layer is used to associate the independent attack stages to analyze whether the current data falls in an attack period. Extensive experiments indicate that our proposed scheme has a lower false positive rate than existing schemes by at least 65.83%, and the false negative rate is reduced by at least 65.26%.