Solving the Nash equilibrium in normal-form games with large-scale strategy spaces presents significant challenges. Open-ended learning frameworks, such as PSRO and its variants, have emerged as effective solutions. However, these methods often lack an efficient metric for evaluating strategy improvement, which limits their effectiveness in approximating equilibria. In this paper, we introduce a novel evaluative metric called Advantage, which possesses desirable properties inherently connected to the Nash equilibrium, ensuring that each strategy update approaches equilibrium. Building upon this, we propose the Advantage Policy Space Response Oracle (A-PSRO), an innovative unified open-ended learning framework applicable to both zero-sum and general-sum games. A-PSRO leverages the Advantage as a refined evaluation metric, leading to a consistent learning objective for agents in normal-form games. Experiments showcase that A-PSRO significantly reduces exploitability in zero-sum games and improves rewards in general-sum games, outperforming existing algorithms and validating its practical effectiveness.

Federated learning is a distributed machine learning system that uses participants’ data to train an improved global model. In federated learning, participants collaboratively train a global model, and after the training is completed, each participant receives that global model along with an incentive. Rational participants try to maximize their individual utility, and they will not input their high-quality data truthfully unless they are provided with satisfactory payments based on their contributions. Furthermore, federated learning benefits from the cooperation of participants. Accordingly, how to establish an incentive mechanism that both incentivizes inputting data truthfully and promotes cooperative contributions has become an important issue to consider. In this article, we introduce a data sharing game model for federated learning and employ game-theoretic approaches to design a core-selecting incentive mechanism by utilizing a popular concept in cooperative games, the core. In federated learning, the core can be empty, resulting in the core-selecting mechanism becoming infeasible. To address this issue, our core-selecting mechanism employs a relaxation method and simultaneously minimizes the benefits of inputting false data for all participants. Meanwhile, to reduce the computational complexity of the core-selecting mechanism, we propose an efficient core-selecting mechanism based on sampling approximation that only aggregates models on sampled coalitions to approximate the exact result. Extensive experiments demonstrate that the efficient core-selecting mechanism can incentivize truthful input of high-quality data and promote cooperation effectively, while it reduces computational overhead compared to the core-selecting mechanism.

Disentangled representation learning is typically achieved by a generative model, variational encoder (VAE). Existing VAE-based methods try to disentangle all the attributes simultaneously in a single hidden space, while the separation of the attribute from irrelevant information varies in complexity. Thus, it should be conducted in different hidden spaces. Therefore, we propose to disentangle the disentanglement itself by assigning the disentanglement of each attribute to different layers. To achieve this, we present a stair disentanglement net (STDNet), a stair-like structure network with each step corresponding to the disentanglement of an attribute. An information separation principle is employed to peel off the irrelevant information to form a compact representation of the targeted attribute within each step. Compact representations, thus, obtained together form the final disentangled representation. To ensure the final disentangled representation is compressed as well as complete with respect to the input data, we propose a variant of the information bottleneck (IB) principle, the stair IB (SIB) principle, to optimize a tradeoff between compression and expressiveness. In particular, for the assignment to the network steps, we define an attribute complexity metric to assign the attributes by the complexity ascending rule (CAR) that dictates a sequencing of the attribute disentanglement in ascending order of complexity. Experimentally, STDNet achieves state-of-the-art results in representation learning and image generation on multiple benchmarks, including Mixed National Institute of Standards and Technology database (MNIST), dSprites, and CelebA. Furthermore, we conduct thorough ablation experiments to show how the strategies employed here contribute to the performance, including neurons block, CAR, hierarchical structure, and variational form of SIB.

Transformers-based methods have achieved significant performance in image deraining as they can model the non-local information which is vital for high-quality image reconstruction. In this paper, we find that most existing Transformers usually use all similarities of the tokens from the query-key pairs for the feature aggregation. However, if the tokens from the query are different from those of the key, the self-attention values estimated from these tokens also involve in feature aggregation, which accordingly interferes with the clear image restoration. To overcome this problem, we propose an effective DeRaining network, Sparse Transformer (DRSformer) that can adaptively keep the most useful self-attention values for feature aggregation so that the aggregated features better facilitate high-quality image reconstruction. Specifically, we develop a learnable top-k selection operator to adaptively retain the most crucial attention scores from the keys for each query for better feature aggregation. Simultaneously, as the naive feed-forward network in Transformers does not model the multi-scale information that is important for latent clear image restoration, we develop an effective mixed-scale feed-forward network to generate better features for image deraining. To learn an enriched set of hybrid features, which combines local context from CNN operators, we equip our model with mixture of experts feature compensator to present a cooperation refinement deraining scheme. Extensive experimental results on the commonly used benchmarks demonstrate that the proposed method achieves favorable performance against state-of-the-art approaches. The source code and trained models are available at https://github.com/cschenxiang/DRSformer.

We present an effective and efficient method that explores the properties of Transformers in the frequency domain for high-quality image deblurring. Our method is motivated by the convolution theorem that the correlation or convolution of two signals in the spatial domain is equivalent to an element-wise product of them in the frequency domain. This inspires us to develop an efficient frequency domain-based self-attention solver (FSAS) to estimate the scaled dot-product attention by an element-wise product operation instead of the matrix multiplication in the spatial domain. In addition, we note that simply using the naive feed-forward network (FFN) in Transformers does not generate good deblurred results. To overcome this problem, we propose a simple yet effective discriminative frequency domain-based FFN (DFFN), where we introduce a gated mechanism in the FFN based on the Joint Photographic Experts Group (JPEG) compression algorithm to discriminatively determine which low- and high-frequency information of the features should be preserved for latent clear image restoration. We formulate the proposed FSAS and DFFN into an asymmetrical network based on an encoder and decoder architecture, where the FSAS is only used in the decoder module for better image deblurring. Experimental results show that the proposed method performs favorably against the state-of-the-art approaches.

With the rapid growth in fingerprint databases, it has become necessary to develop excellent fingerprint indexing to achieve efficiency and accuracy. Fingerprint indexing has been widely studied with real-valued features, but few studies focus on binary feature representation, which is more suitable to identify fingerprints efficiently in large-scale fingerprint databases. In this study, we propose a deep compact binary minutia cylinder code (DCBMCC) as an effective and discriminative feature representation for fingerprint indexing. Specifically, the minutia cylinder code (MCC), as the state-of-the-art fingerprint representation, is analyzed and its shortcomings are revealed. Accordingly, we propose a novel fingerprint indexing method based on deep neural networks to learn DCBMCC. Our novel network restricts the penultimate layer to directly output binary codes. Moreover, we incorporate independence, balance, quantization-loss-minimum, and similarity-preservation properties in this learning process. Eventually, a multi-index hashing (MIH) based fingerprint indexing scheme further speeds up the exact search in the Hamming space by building multiple hash tables on binary code substrings. Furthermore, numerous experiments on public databases show that the proposed approach is an outstanding fingerprint indexing method since it has an extremely small error rate with a very low penetration rate.

Although RAID is a well-known technique to protect data against disk errors, it is vulnerable to silent data corruptions that cannot be detected by disk drives. Existing integrity protection schemes designed for RAID arrays often introduce high I/O overhead. Our key insight is that by properly designing an integrity protection scheme that adapts to the read/write characteristics of storage workloads, the I/O overhead can be significantly mitigated. In view of this, this paper presents a systematic study on I/O-efficient integrity protection against silent data corruptions in RAID arrays. We formalize an integrity checking model, and justify that a large proportion of disk reads can be checked with simpler and more I/O-efficient integrity checking mechanisms. Based on this integrity checking model, we construct two integrity protection schemes that provide complementary performance advantages for storage workloads with different user write sizes. We further propose a quantitative method for choosing between the two schemes in real-world scenarios. Our trace-driven simulation results show that with the appropriate integrity protection scheme, we can reduce the I/O overhead to below 15%.

Practical storage systems often adopt erasure codes to tolerate device failures and sector failures, both of which are prevalent in the field. However, traditional erasure codes employ device-level redundancy to protect against sector failures, and hence incur significant space overhead. Recent sector-disk (SD) codes are available only for limited configurations. By making a relaxed but practical assumption, we construct a general family of erasure codes called STAIR codes , which efficiently and provably tolerate both device and sector failures without any restriction on the size of a storage array and the numbers of tolerable device failures and sector failures. We propose the upstairs encoding and downstairs encoding methods, which provide complementary performance advantages for different configurations. We conduct extensive experiments on STAIR codes in terms of space saving, encoding/decoding speed, and update cost. We demonstrate that STAIR codes not only improve space efficiency over traditional erasure codes, but also provide better computational efficiency than SD codes based on our special code construction. Finally, we present analytical models that characterize the reliability of STAIR codes, and show that the support of a wider range of configurations by STAIR codes is critical for tolerating sector failure bursts discovered in the field.

Data deduplication is a technique for eliminating duplicate copies of data, and has been widely used in cloud storage to reduce storage space and upload bandwidth. Promising as it is, an arising challenge is to perform secure deduplication in cloud storage. Although convergent encryption has been extensively adopted for secure deduplication, a critical issue of making convergent encryption practical is to efficiently and reliably manage a huge number of convergent keys. This paper makes the first attempt to formally address the problem of achieving efficient and reliable key management in secure deduplication. We first introduce a baseline approach in which each user holds an independent master key for encrypting the convergent keys and outsourcing them to the cloud. However, such a baseline key management scheme generates an enormous number of keys with the increasing number of users and requires users to dedicatedly protect the master keys. To this end, we propose Dekey , a new construction in which users do not need to manage any keys on their own but instead securely distribute the convergent key shares across multiple servers. Security analysis demonstrates that Dekey is secure in terms of the definitions specified in the proposed security model. As a proof of concept, we implement Dekey using the Ramp secret sharing scheme and demonstrate that Dekey incurs limited overhead in realistic environments.

The B-Code is a class of MDS array code with optimal properties for RAID 6. Xu et al. proposed an open problem in 1999: Are the B-Code constructions strongly equivalent to perfect one-factorizations of a graph? In this paper, we show that the constructions of the B-Code of length l are equivalent to perfect one-factorizations of a l-regular graph on l + r vertices, where l is an integer not smaller than 4, and r is equal to 1 for an odd l or 2 for an even l.

In this paper, we present a systematic study on cyclic lowest density MDS array codes constructed using starters. We first show that all cyclic lowest density MDS array codes of distance 3 and length 2n can be constructed using normalized cyclic bipyramidal starters in the additive group of congruence classes modulo 2n. We then discuss when and how to transform non-cyclic lowest density MDS array codes constructed using other starters (including even starters and patterned starters) to cyclic codes. Finally, we also discuss how to construct quasi-cyclic lowest density MDS array codes using multi-starters for an even length when no cyclic lowest density MDS array code exists for this even length.

Large-scale erasure-coded storage systems have a serious performance problem due to I/O congestion and disk media access congestion caused by read-modify-write operations involved in small-write operations. All the existing technologies based on the conventional disk can provide very limited performance improvement. This paper presents a new Disk Architecture with Composite Operation (DACO), whose disk media access interface consists of three kinds of operations: READ, WRITE, and Composite Operation (CO). The CO adopts a sector-based pipeline technology to implement block-level data modify operations, and thus, can replace the read-modify-write operations involved in small-write operations. When the DACO is adopted in a large-scale erasure-coded storage system with t fault tolerance, t I/Os and t disk media access operations can be reduced in each small-write operation, respectively. This alleviates both I/O congestion and disk media access congestion in nature, and thus, can remarkably improve the performance of large-scale erasure-coded storage systems. A simulation study shows that the DACO can provide significant performance improvement: reducing the average I/O response time by up to 31.16 percent even in the worst case where t=1. This paper also discusses the important implementation issues of the DACO and investigates the additional cost involved in the DACO.

One recent technical challenge facing the designers of erasure-coded storage systems is how to prevent silent data corruptions from propagating during data reconstruction. This paper proposes a new technique of exploiting erasure-coded storage systems to cope with silent data corruptions during data reconstruction. To develop a data reconstruction method that can prevent silent data corruptions from propagating, we first define the consistency of a strip group and then study the impact of silent data corruptions on the consistency of strip groups. Based on the conclusions obtained from the study, an efficient adaptive data reconstruction method is developed for data reconstruction in the presence of silent data corruptions. A performance analysis of our new data reconstruction method is then made using a probabilistic method. Our results show that the overall performance impact of our data reconstruction method is negligible in practical systems. A comparison of techniques for coping with silent data corruptions in erasure-coded storage systems is also made. The comparison shows that the technique based on our data reconstruction method is a better choice to cope with silent data corruptions when periodic validation is used in an erasure-coded storage system.

As storage systems grow in size and complexity, they are increasingly confronted with concurrent disk failures together with multiple unrecoverable sector errors. To ensure high data reliability and availability, erasure codes with high fault tolerance are required. In this article, we present a new family of erasure codes with high fault tolerance, named GRID codes. They are called such because they are a family of strip-based codes whose strips are arranged into multi-dimensional grids. In the construction of GRID codes, we first introduce a concept of matched codes and then discuss how to use matched codes to construct GRID codes. In addition, we propose an iterative reconstruction algorithm for GRID codes. We also discuss some important features of GRID codes. Finally, we compare GRID codes with several categories of existing codes. Our comparisons show that for large-scale storage systems, our GRID codes have attractive advantages over many existing erasure codes: (a) They are completely XOR-based and have very regular structures, ensuring easy implementation; (b) they can provide up to 15 and even higher fault tolerance; and (c) their storage efficiency can reach up to 80% and even higher. All the advantages make GRID codes more suitable for large-scale storage systems.