ABSTRACT High frequency and utility are two crucial objectives in data mining, as they provide valuable insights for decision‐making. Most frequent‐utility pattern mining methods rely on threshold‐based approaches, which can inadvertently overlook itemsets with low frequency but high utility, or those with low utility but high frequency. Skyline frequent‐utility pattern mining addresses this limitation by capturing patterns that are optimal across both dimensions. However, existing skyline algorithms are primarily designed for static databases. In real‐world scenarios, databases typically receive new transactions incrementally, necessitating an efficient algorithm to find skyline frequent‐utility patterns in dynamic environments. This paper introduces the ISFUM (Incremental Skyline Frequent‐Utility Mining) algorithm, which efficiently discovers skyline frequent‐utility itemsets in dynamic transaction databases. By utilising global and local utility‐lists, ISFUM avoids rescanning the original database during incremental updates. Additionally, we have developed novel pruning strategies to further reduce computational time by minimising unnecessary candidate validation. Experimental results demonstrate that our algorithm is both efficient and effective in handling dynamic data environments.

Rack-aware storage systems organize the storage nodes in racks such that the cross-rack communication cost is much more expensive than the intra-rack communication cost. In this paper, we primarily investigate the cross-rack update bandwidth defined as the average amount of symbols transferred across different racks during an update process of one single node. It is critical to design erasure codes that minimize the cross-rack update bandwidth. Our main contributions are as follows. First, we establish the model of cross-rack update bandwidth of irregular array codes over rack-aware storage systems. Second, we derive the tight lower bound on cross-rack update bandwidth, and define minimum cross-rack update bandwidth (MCUB) codes as the irregular array codes that can achieve our tight lower bound. Third, we derive the tight lower bound on redundancy defined as the total number of parity symbols for MCUB codes, and define minimum redundancy MCUB (MR-MCUB) codes as the MCUB codes that can achieve the redundancy lower bound. Fourth, we present explicit constructions of MR-MCUB codes that achieve both the minimum cross-rack update bandwidth and the minimum redundancy, which means that the two lower bounds are tight. Last, we define intra-rack update bandwidth as the average amount of symbols incurred within one rack in an update process, and derive the lower bound of intra-rack update bandwidth of MCUB codes. Moreover, we show that our MCUB codes constructions can also achieve the lower bound of intra-rack update bandwidth.

Polynomial remainder codes form a class of linear codes constructed based on the Chinese Remainder Theorem over polynomial rings, with Reed-Solomon codes as a special case. In particular, irreducible polynomial remainder codes are those where the moduli are pairwise coprime irreducible polynomials. This paper presents an efficient encoding and decoding method for irreducible polynomial remainder codes over F2m, leveraging the additive Fast Fourier Transform (additive FFT). The proposed approach achieves a computational complexity ofO(Nlog2(N−K)), whereNandKdenote the code length and dimension, with the additional requirement thatN−Km−1andN−Kis a power of 2. This substantially outperforms the best known algorithm for such codes, which has a complexity ofO(N2). Furthermore, we conduct a non-asymptotic complexity comparison under specific parameters, with numerical results demonstrating that the proposed algorithms effectively reduces computational complexity. For example, with code lengthN= 256 and dimensionK= 224, our method achieves an approximately 83% reduction in multiplicative complexity for encoding and a 50% reduction for decoding compared to the state-of-the-art approach for polynomial remainder codes.

This paper proposes an improved ordered statistics decoding (OSD) algorithm, termed OSD with pre-stored systematic matrices (PSM-OSD), which completely avoids online Gaussian elimination by pre-storing multiple systematic generator matrices (SGMs) and selecting one based on the received sequence for decoding. To further improve the search efficiency, the local-constraint mechanism is combined with the PSM-OSD, resulting in the LC-PSM-OSD. We then address three critical questions for design: how many SGMs should be pre-stored, how they should be constructed, and how to select one for decoding. For the first question, we introduce the notion of maximum reliable-information coverage, which characterizes how well the pre-stored SGMs match the reliable bit positions. For construction and selection, we introduce a Reed-Muller-based design to ensure high basis diversity, and the sum-reliability strategy provides superior decoding performance among the tested selection criteria. A saddlepoint-based analytical framework is developed to estimate both the frame error rate (FER) upper bound and the average number of searches, enabling pre-stored matrix design without exhaustive decoding simulations. We also prove that, with tailored early stopping and unlimited maximum number of searches, the proposed algorithm is a non-exhaustive-search ML decoding algorithm. Numerical results and analysis demonstrate that the proposed decoding algorithms are effective across various coding schemes, including random linear codes, BCH codes, and 5G polar codes. Moreover, the results show that the proposed LC-PSM-OSD can closely approach the finite-length capacity over almost all code rates for the considered codes, and outperforms conventional OSD, guessing codeword decoding (GCD), and LC-GCD. © 2026 IEEE.

Byzantine-robust federated learning aims to maintain resilient performance in the presence of malicious attacks that can impede the convergence of learning algorithms. Although numerous robust aggregators have been developed to merge the collected gradient information in the server, they either require data homogeneity and are suboptimal for heterogeneous data, or their breakdown points—the smallest proportion of outliers that can make the aggregators fail—are not theoretically analyzed or less than 0.5. In contrast to existing aggregators, this paper formulates the aggregation process as a low-rank plus sparse decomposition model, where the low-rank component, with a rank of one, facilitates accurate gradient computation, while the sparse component, penalized by the ℓ2,0-norm, mitigates the impact of outliers. We prove that the devised rule achieves the maximum breakdown point of 0.5. Besides, we apply our aggregation rule to Byzantine-robust federated learning and employ the Polyak’s momentum to reduce gradient variance among honest workers. It is analyzed that our aggregator achieves order-optimal Byzantine-resilient federated learning for heterogeneous data. Experimental results using MNIST, Fashion-MNIST and CIFAR-10 demonstrate that the developed approach yields higher classification accuracy than the competing aggregators under different attack types and heterogeneity levels.

Recent advances in reasoning with large language models (LLMs) have popularized Long Chain-of-Thought (LCoT), a strategy that encourages deliberate and step-by-step reasoning before producing a final answer.While LCoTs have enabled expert-level performance in complex tasks, how the internal structures of their reasoning chains drive, or even predict, the correctness of final answers remains a critical yet underexplored question.In this work, we present LCoT2Tree, an automated framework that converts sequential LCoTs into hierarchical tree structures and thus enables deeper structural analysis of LLM reasoning.Using graph neural networks (GNNs), we reveal that structural patterns extracted by LCoT2Tree, including exploration, backtracking, and verification, serve as stronger predictors of final performance across a wide range of tasks and models.Leveraging an explainability technique, we further identify critical thought patterns such as over-branching that account for failures.Beyond diagnostic insights, the structural patterns by LCoT2Tree support practical applications, including improving Best-of-N decoding effectiveness.Overall, our results underscore the critical role of internal structures of reasoning chains, positioning LCoT2Tree as a powerful tool for diagnosing, interpreting, and improving reasoning in LLMs.The code is available at our GitHub repository.

This paper proposes an enhanced guessing codeword decoding (GCD) algorithm, termed GCD with most reliable cyclic basis (MRCB-GCD), specifically tailored for BCH codes. Unlike original GCD, the proposed method selects the k consecutive bits with the highest aggregate reliability as the re-encoding basis, leveraging the cyclic structure of BCH codes. To further enhance search efficiency, a local constraint (LC) mechanism is introduced, where the extended reliable bits of length k+δ enable the algorithm to skip numerous unnecessary test error patterns (TEPs). To stop the search process, we introduce two termination criteria and prove that the proposed approach with the trivial termination criterion forms a non-exhaustive-search maximum likelihood (ML) decoding algorithm. A saddlepoint-based numerical method is developed to approximately calculate the upper bound on the performance gap to the ML decoding and estimate the average number of searches, showing the advantages of the proposed MRCB-GCD over the original GCD in terms of both decoding performance and search efficiency. Simulation results demonstrate that: 1) MRCB- GCD outperforms original GCD in both frame error rate (FER) and number of searches, 2) the LC mechanism and termination criteria further reduce the number of searches, and 3) the proposed approach achieves finite-length capacity across various code rates but without requiring Gaussian elimination.

The embedded topic model (ETM) is a widely used approach that assumes the sampled document-topic distribution conforms to the logistic normal distribution for easier optimization. However, this assumption oversimplifies the real document-topic distribution, limiting the model’s performance. In response, we propose a novel method that introduces the diffusion process into the sampling process of document-topic distribution to overcome this limitation and maintain an easy optimization process. We validate our method through extensive experiments on two mainstream datasets, proving its effectiveness in improving topic modeling performance.

Catastrophic forgetting (CF) poses a significant challenge in machine learning, where a model forgets previously learned information upon learning new tasks. Despite the advanced capabilities of Large Language Models (LLMs), they continue to face challenges with CF during continual learning. The majority of existing research focuses on analyzing forgetting patterns through a singular training sequence, thereby overlooking the intricate effects that diverse tasks have on model behavior. Our study explores CF across various settings, discovering that model forgetting is influenced by both the specific training tasks and the models themselves. To this end, we interpret forgetting by examining the function vector (FV), a compact representation of functions in LLMs, offering a model-dependent indicator for the occurrence of CF. Through theoretical and empirical analyses, we demonstrated that CF in LLMs primarily stems from biases in function activation rather than the overwriting of task processing functions. Leveraging these insights, we propose a novel function vector guided training methodology, incorporating a regularization technique to stabilize the FV and mitigate forgetting. Empirical tests on four benchmarks confirm the effectiveness of our proposed training method, substantiating our theoretical framework concerning CF and model function dynamics.

Large language models (LLMs) have exhibited their problem-solving abilities in mathematical reasoning. Solving realistic optimization (OPT) problems in application scenarios requires advanced and applied mathematics ability. However, current OPT benchmarks that merely solve linear programming are far from complex realistic situations. In this work, we propose **OptiBench**, a benchmark for End-to-end optimization problem-solving with human-readable inputs and outputs. **OptiBench** contains rich optimization problems, including linear and nonlinear programming with or without tabular data, which can comprehensively evaluate LLMs' solving ability. In our benchmark, LLMs are required to call a code solver to provide precise numerical answers. Furthermore, to alleviate the data scarcity for optimization problems, and to bridge the gap between open-source LLMs on a small scale (e.g., Llama-3-8b) and closed-source LLMs (e.g., GPT-4), we further propose a data synthesis method namely ***ReSocratic***. Unlike general data synthesis methods that proceed from questions to answers, \ReSocratic first incrementally synthesizes formatted optimization demonstration with mathematical formulations step by step and then back-translates the generated demonstrations into questions. Based on this, we synthesize the ***ReSocratic-29k*** dataset. We further conduct supervised fine-tuning with ***ReSocratic-29k*** on multiple open-source models. Experimental results show that ***ReSocratic-29k*** significantly improves the performance of open-source models.

Large language models (LLMs) exhibit varying strengths and weaknesses across different tasks, prompting recent studies to explore the benefits of ensembling models to leverage their complementary advantages. However, existing LLM ensembling methods often overlook model compatibility and struggle with inefficient alignment of probabilities across the entire vocabulary. In this study, we empirically investigate the factors influencing ensemble performance, identifying model performance, vocabulary size, and response style as key determinants, revealing that compatibility among models is essential for effective ensembling. This analysis leads to the development of a simple yet effective model selection strategy that identifies compatible models. Additionally, we introduce the \textsc{Uni}on \textsc{T}op-$k$ \textsc{E}nsembling (\textsc{UniTE}), a novel approach that efficiently combines models by focusing on the union of the top-k tokens from each model, thereby avoiding the need for full vocabulary alignment and reducing computational overhead. Extensive evaluations across multiple benchmarks demonstrate that \textsc{UniTE} significantly enhances performance compared to existing methods, offering a more efficient framework for LLM ensembling.

Recent research has increasingly focused on reconciling the reasoning capabilities of System 2 with the efficiency of System 1. While existing training-based and prompt-based approaches face significant challenges in terms of efficiency and stability, model merging emerges as a promising strategy to integrate the diverse capabilities of different Large Language Models (LLMs) into a unified model. However, conventional model merging methods often assume uniform importance across layers, overlooking the functional heterogeneity inherent in neural components. To address this limitation, we propose \textbf{A}ctivation-Guided \textbf{C}onsensus \textbf{M}erging (\textbf{ACM}), a plug-and-play merging framework that determines layer-specific merging coefficients based on mutual information between activations of pre-trained and fine-tuned models. ACM effectively preserves task-specific capabilities without requiring gradient computations or additional training. Extensive experiments on Long-to-Short (L2S) and general merging tasks demonstrate that ACM consistently outperforms all baseline methods. For instance, in the case of Qwen-7B models, TIES-Merging equipped with ACM achieves a \textbf{55.3\%} reduction in response length while simultaneously improving reasoning accuracy by \textbf{1.3} points. We submit the code with the paper for reproducibility, and it will be publicly available.

In distributed learning systems, ensuring efficient communication and privacy protection are two significant challenges. Although several existing works have attempted to address these challenges simultaneously, they often overlook essential learning-oriented features such as dynamic gradient and communication characteristics. In this paper, we propose a communication-efficient and privacy-preserving distributed SGD algorithm. Our proposed algorithm employs a layered randomized quantizer (LRQ) to reduce communication overhead, which also ensures that quantization errors follow an exact Gaussian distribution, thus achieving client-level differential privacy. We analyze the trade-off between convergence error, communication, and privacy under non-IID data distributions. Besides, we modify the algorithm to be training-adaptive by adjusting the perround privacy budget allocation in response to i) dynamic gradient features and ii) real-time changing communication rounds. Both closed-form solutions are derived by solving the minimization problem of convergence error subject to the privacy budget constraint. Finally, we evaluate the effectiveness of our approach through extensive experiments on various datasets, including MNIST, CIFAR-10, and CIFAR-100, demonstrating its superiority in terms of communication cost, privacy protection, and model performance compared to state-of-the-art methods.

We consider broadcasting a block of data packets to multiple users via instantly decodable network coding (IDNC) under the semi-online feedback transmission mode. In this paper, we first introduce a new class of IDNC schemes called lightweight IDNC, tailored for wireless broadcast with stringent computational load at the receiver end. Unlike traditional IDNC that may encode a larger number of original packets together, lightweight IDNC limits each coded packet to a combination of at most two original packets. Explicit lower bounds of the total completion delay as well as the decoding delay are respectively obtained for arbitrary lightweight IDNC schemes. We further investigate the number of transmission rounds as another performance metric, and explicitly characterize its distribution and expectation. The characterizations apply to arbitrary partition-based IDNC schemes, including the lightweight IDNC schemes considered in this paper. A new efficient algorithm is also proposed to construct lightweight IDNC schemes which grants the original packets with lower coding opportunity a higher priority to be encoded. Numerical analyses demonstrate that the lightweight IDNC schemes constructed by the new algorithm not only achieve lower completion and decoding delays in comparison with the ones constructed by the existing algorithm but also adhere closely to theoretical lower bounds, demonstrating their efficiency and practical utility.

In this paper, we propose a two-stage soft-decision decoding (SDD) algorithm for BCH codes. At the first stage, we search for test error patterns (TEPs) according to the reliabilities of the received bits by using the flipping pattern tree (FPT) algorithm or the ordered reliability bits (ORB) technique, with a bounded number of searches. At the second stage, traditional algebraic hard-decision decoding (HDD), say, Berlekamp-Massey (BM) algorithm, is performed for these TEPs to find codewords. The proposed algorithm, referred to as FPT-BM algorithm or ORB-BM algorithm, can achieve near-optimal performance with a significantly small number of searches (dozens to hundreds). This enables efficient parallel implementation, ensuring low decoding latency and high throughput. To justify the sufficiency of the small number of searches, we provide qualitative reasoning and quantitative evaluation (using saddlepoint approximation) to show that the transmitted codeword under the proposed FPT-BM decoding strategy is reached much earlier in the search list than that under the single stage decoding (FPT-only). To analyze the performance, we calculate the upper bound on the performance gap between the proposed algorithm and maximum likelihood (ML) decoding based on the saddlepoint approximation, showing that the proposed algorithm can effectively approach the ML lower bound for high rate BCH codes. To reduce computational complexity, we introduce a filtering criterion, where the algebraic hard-decision decoding (BM decoding) is performed only for those candidates satisfying a sufficient number of parity-check equations. To determine the key parameters, we provide an intuitive criterion for the threshold in the filtering step based on the statistical analysis and a quantitative criterion for the maximum list size based on the upper bound on the performance gap to ML decoding. Numerical results demonstrate that: 1) By introducing the filtering criterion, the proposed FPT-BM algorithm effectively reduces the number of BM calls by half, with negligible performance loss, and outperforms the Chase-BM algorithm under the same filtering criterion; 2) The proposed decoding algorithm outperforms single stage decoding (FPT only) under limited search sizes; 3) For high rate BCH codes, the proposed decoding algorithm can approach the finite-length capacity, while for medium rate regions, the proposed decoding algorithm also exhibits better performance over FPT-only and BM-only decoding algorithms.

In data centers, storage nodes are typically organized in racks and rack-aware regenerating codes (RRCs) can achieve the optimal trade-off between storage capacity and cross-rack repair bandwidth. In this paper, we present explicit constructions for multiple erasure tolerance of rack-aware regenerating codes (MET-RRCs), i.e., RRCs with optimal cross-rack repair bandwidth for multi-node failures. We refine the MET-RRC framework in [2] under more extensive parameters and extend the existing construction methods of RRCs. Specifically, we leverage the parity-check matrix structure to present a general framework for multiple erasure tolerance of minimum storage rack-aware regenerating (MET-MSRR) codes. The existing parity-check matrix construction of MSRR codes can be elucidated with this framework. Moreover, we present the construction for multiple erasure tolerance of minimum bandwidth rack-aware regenerating (MET-MBRR) codes using the product-matrix framework.

Despite the increasing interest in sequential transfer optimization (STO), a comprehensive benchmark suite for systematically comparing various STO algorithms remains underexplored. Existing test problems, which are often manually configured and lack scalability, can result in biased and nongeneralizable algorithm performance. In light of the above, we first introduce four concepts for characterizing STO problems (STOPs) in this study and present an important feature, namely similarity distribution, to quantitatively delineate the relationship between the optimal solutions of source and target tasks. Subsequently, we present general design guidelines for STOPs and introduce a problem generator that demonstrates strong scalability. Specifically, the similarity distribution of a problem can be easily customized through a novel inverse generation strategy, allowing for a continuous spectrum that captures the diverse similarity relationships present in real-world scenarios. Lastly, a benchmark suite comprising 12 STOPs, characterized by a range of customized similarity relationships, has been developed using the proposed generator and will serve as a platform for examining various STO algorithms. For instance, biased transferability representation, irregular mapping learning behaviors, and performance improvements unrelated to search experience are significant empirical findings that previous benchmarks failed to reveal, yet can be effectively identified through our test problems. The source code of the proposed problem generator is available at https://github.com/XmingHsueh/STOP-G.

Expensive optimization problems (EOPs) have attracted increasing research attention over the decades due to their ubiquity in a variety of practical applications. Despite many sophisticated surrogate-assisted evolutionary algorithms (SAEAs) that have been developed for solving such problems, most of them lack the ability to transfer knowledge from previously-solved tasks and always start their search from scratch, making them troubled by the notorious cold-start issue. A few preliminary studies that integrate transfer learning into SAEAs still face some issues, such as defective similarity quantification that is prone to underestimate promising knowledge, surrogate-dependency that makes the transfer methods not coherent with the state-of-the-art in SAEAs, etc. In light of the above, a plug and play competitive knowledge transfer (CKT) method is proposed to boost various SAEAs in this article. Specifically, both the optimized solutions from the source tasks and the promising solutions acquired by the target surrogate are treated as task-solving knowledge, enabling them to compete with each other to elect the winner for expensive evaluation, thus boosting the search speed on the target task. Moreover, the lower bound of the convergence gain brought by the knowledge competition is mathematically analyzed, which is expected to strengthen the theoretical foundation of sequential transfer optimization. Experimental studies conducted on a series of benchmark problems and a practical application from the petroleum industry verify the efficacy of the proposed method. The source code of the CKT is available athttps://github.com/XmingHsueh/SAS-CKT.

Person re-identification (Re-ID) is an important task and has significant applications for public security and information forensics, which has progressed rapidly with the development of deep learning. In this work, we investigate a novel and challenging setting of Re-ID, i.e., cross-domain video-based person Re-ID. Specifically, we utilize synthetic video datasets as the source domain for training and real-world videos for testing, notably reducing the reliance on expensive real data acquisition and annotation. To harness the potential of synthetic data, we first propose a self-supervised domain-invariant feature learning strategy for both static and dynamic (temporal) features. Additionally, to enhance person identification accuracy in the target domain, we propose a mean-teacher scheme incorporating a self-supervised ID consistency loss. Experimental results across five real datasets validate the rationale behind cross-synthetic-real domain adaptation and demonstrate the efficacy of our method. Notably, the discovery that synthetic data outperforms real data in the cross-domain scenario is a surprising outcome. The code and data are publicly available at https://github.com/XiangqunZhang/UDA_Video_ReID.

Reed-Solomon (RS) codes are widely used to correct errors in storage systems. Finding the error locator polynomial is one of the key steps in the error correction procedure of RS codes. Modular Approach (MA) is an effective algorithm for solving the Welch-Berlekamp (WB) key-equation problem to find the error locator polynomial that needs$2t$steps, wheretis the error correction capability. In this paper, we first present a new MA algorithm that only requires$2e$steps and then propose two fast decoding algorithms for RS codes based on our MA algorithm, whereeis the number of errors and$e\leq t$. We propose the Improved-Frequency Domain Modular Approach (I-FDMA) algorithm that needs$2e$steps to solve the error locator polynomial and present our first decoding algorithm based on the I-FDMA algorithm. We show that, compared with the existing methods based on MA algorithms, our I-FDMA algorithm can effectively reduce the decoding complexity of RS codes when$e\lt t$. Furthermore, we propose the$t_{0}$-Shortened I-FDMA ($t_{0}$-SI-FDMA) algorithm ($t_{0}$is a predetermined even number less than$2t-1$) based on the new termination mechanism to solve the error numberequickly. We propose our second decoding algorithm based on the SI-FDMA algorithm for RS codes and show that the multiplication complexity of our second decoding algorithm is lower than our first decoding algorithm (the I-FDMA decoding algorithm) when$2e\lt t_{0}+1$.

Large language models (LLMs) have demonstrated remarkable capabilities and have been extensively deployed across various domains, including recommender systems. Prior research has employed specialized prompts to leverage the in-context learning capabilities of LLMs for recommendation purposes. More recent studies have utilized instruction tuning techniques to align LLMs with human preferences, promising more effective recommendations. However, existing methods suffer from several limitations. The full potential of LLMs is not fully elicited due to low-quality tuning data and the overlooked integration of conventional recommender signals. Furthermore, LLMs may generate inconsistent responses for different ranking tasks in the recommendation, potentially leading to unreliable results. In this article, we introduce Ranker for top- k Recommendations (RecRanker), tailored for instruction tuning LLMs to serve as the Ranker for top- k Recommendations. Specifically, we introduce importance-aware sampling, clustering-based sampling, and penalty for repetitive sampling for sampling high-quality, representative, and diverse training data. To enhance the prompt, we introduce a position shifting strategy to mitigate position bias and augment the prompt with auxiliary information from conventional recommendation models, thereby enriching the contextual understanding of the LLM. Subsequently, we utilize the sampled data to assemble an instruction-tuning dataset with the augmented prompts comprising three distinct ranking tasks: pointwise, pairwise, and listwise rankings. We further propose a hybrid ranking method to enhance the model performance by ensembling these ranking tasks. Our empirical evaluations demonstrate the effectiveness of our proposed RecRanker in both direct and sequential recommendation scenarios. 1

3D shapes captured by scanning devices are often incomplete due to occlusion. 3D shape completion methods have been explored to tackle this limitation. However, most of these methods are only trained and tested on a subset of categories, resulting in poor generalization to unseen categories. In this article, we propose a novel weakly-supervised framework to reconstruct the complete shapes from unseen categories. We first propose an end-to-end prior-assisted shape learning network that leverages data from the seen categories to infer a coarse shape. Specifically, we construct a prior bank consisting of representative shapes from the seen categories. Then, we design a multi-scale pattern correlation module for learning the complete shape of the input by analyzing the correlation between local patterns within the input and the priors at various scales. In addition, we propose a self-supervised shape refinement model to further refine the coarse shape. Considering the shape variability of 3D objects across categories, we construct a category-specific prior bank to facilitate shape refinement. Then, we devise a voxel-based partial matching loss and leverage the partial scans to drive the refinement process. Extensive experimental results show that our approach is superior to state-of-the-art methods by a large margin.

Yinya Huang, Ruixin Hong, Hongming Zhang, Wei Shao, Zhicheng Yang, Dong Yu, Changshui Zhang, Xiaodan Liang, Linqi Song. Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2024.

Haochen Tan, Zhijiang Guo, Zhan Shi, Lu Xu, Zhili Liu, Yunlong Feng, Xiaoguang Li, Yasheng Wang, Lifeng Shang, Qun Liu, Linqi Song. Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2024.

Tianqi Zhong, Zhaoyi Li, Quan Wang, Linqi Song, Ying Wei, Defu Lian, Zhendong Mao. Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2024.

Multi-modal federated learning (MFL) offers the advantage of aggregating models from diverse data modalities to obtain a more powerful fused model while preserving data privacy. However, MFL faces three key challenges: 1) Communication overhead - only a limited number of clients can participate in training due to communication budget constraints; 2) Modality heterogeneity - different modalities contribute unequally to the fused model; 3) Client heterogeneity - clients exhibit variations in data quantity and quality across modalities. To address these challenges, we formulate a joint client-modality selection problem under communication budget constraints. The goal is to determine the participating clients and their uploaded modalities in each communication round, maximizing the performance of the fused model given a limited communication budget. We propose a dynamic many-to-many matching algorithm with two quota budgeting strategies: 1) Round-aware Modality Budgeting (RMB) determines the total number of uploaded modality models per round based on the current training process (i.e., how close the model is to convergence). 2) Modality-aware Client Allocation (MCB) adaptively allocates client quota for each modality by balancing the modality’s contribution to the fusion model against its model size. After quota budgeting, we construct preference lists for clients and modalities to find a stable many-to-many matching of (client, modality) pairs. Experiments demonstrate that our algorithm achieves better model performance than baselines under the same communication budget, validating the benefits of dynamic budget allocation and client scheduling.

Optimizing antenna placement in in-building distributed antenna systems is critical for achieving comprehensive 5G coverage. Due to the utilization of high-frequency signal bands, the propagation of 5G signals is significantly influenced by distance and obstacles in indoor environments. Consequently, devising effective placement schemes faces challenges in complex indoor scenarios. This paper presents a multiobjective genetic algorithm for antenna placement optimization. It tracks the signal propagation by introducing the ray-tracing propagation model. Although the ray-tracing propagation model provides high simulation accuracy, it also incurs substantial computation costs, rendering the antenna placement problem expensive. To tackle this challenge, the algorithm introduces the idea of Bayesian optimization, where a surrogate model replaces certain calculations in the ray tracing propagation model, thereby reducing the computational burden. Experimental results demonstrate the superior performance of the proposed algorithm compared to other algorithms in two real-world scenarios, as evidenced by evaluations based on hypervolume and inverted generational distance metrics.

In cases of frequent problem-solving of multiobjective optimization tasks from a domain due to changing conditions or problem features, a growing number of individual tasks will be solved and stored in a database, providing an opportunity for a target task at hand to achieve better optimization performance through knowledge transfer from the previously-solved tasks, which is also known as sequential transfer optimization. Despite a variety of transfer algorithms that have been developed over the years, the research on the design of benchmark problems for evaluating such algorithms received far less attention. Oftentimes, the source and target tasks in existing test problems are manually assembled or extended from specific practical problems, limiting their ability to represent the diverse yet complex source-target similarity relationships in real-world problems. In light of this, we propose design methods to generate multiobjective sequential transfer optimization problems (MSTOPs) systematically in this work, wherein the Pareto manifolds of individual tasks and the manifold-based similarity between the tasks can be customized with ease, enabling a broad spectrum of representation of the diverse similarity relationships between the source-target Pareto manifolds of MSTOPs. Lastly, a benchmark suite with 12 test problems is developed using the proposed methods, which would serve as an arena for electing superior multiobjective sequential transfer optimization algorithms. The source code is available at https://github.com/XmingHsueh/MSTOP.

Vision-language pretrained models have achieved impressive performance on various downstream tasks. However, their large model sizes hinder their utilization on platforms with limited computational resources. We find that directly using smaller pretrained models and applying magnitude-based pruning on CLIP models leads to in-flexibility and inferior performance. Recent efforts for VLP compression either adopt uni-modal compression metrics resulting in limited performance or involve costly mask-search processes with learnable masks. In this paper, we first propose the Module-wise Pruning Error (MoPE) met-ric, accurately assessing CLIP module importance by performance decline on cross-modal tasks. Using the MoPE metric, we introduce a unified pruning framework applica-ble to both pretraining and task-specific fine-tuning compression stages. For pretraining, MoPE-CLIP effectively leverages knowledge from the teacher model, significantly reducing pretraining costs while maintaining strong zero-shot capabilities. For fine-tuning, consecutive pruning from width to depth yields highly competitive task-specific models. Extensive experiments in two stages demonstrate the effectiveness of the MoPE metric, and MoPE-CLIP outperforms previous state-of-the-art VLP compression methods.

Large Language Models (LLMs) have recently revolutionized the NLP field, while they still fall short in some specific down-stream tasks.In the work, we focus on utilizing LLMs to perform machine translation, where we observe that two patterns of errors frequently occur and drastically affect the translation quality: language mismatch and repetition.The work sets out to explore the potential for mitigating these two issues by leveraging model editing methods, e.g., by locating Feed-Forward Network (FFN) neurons or something that are responsible for the errors and deactivating them in the inference time.We find that directly applying such methods either limited effect on the targeted errors or has significant negative side-effect on the general translation quality, indicating that the located components may also be crucial for ensuring machine translation with LLMs on the rails.To this end, we propose to refine the located components by fetching the intersection of the locating results under different language settings, filtering out the aforementioned information that is irrelevant to targeted errors.The experiment results empirically demonstrate that our methods can effectively reduce the language mismatch and repetition ratios and meanwhile enhance or keep the general translation quality in most cases.

Recently, large language models (LLMs) have demonstrated impressive capabilities and gained widespread applications. However, their direct application to recommendation tasks (e.g., rating prediction task) often falls short of optimal results due to a lack of understanding of collaborative information in recommendations. In this paper, we propose Large lAnguage Model Augmented Recommendation (LAMAR) framework to address this limitation. Instead of relying solely on LLMs, our framework combines their outputs with traditional recommendation models, leveraging both collaborative and semantic information. We further enhance the recommendation performance through an ensemble of diverse prompts and utilize LLMs to extract side information for augmenting traditional recommendation models. Empirical studies on real-world datasets demonstrate that LAMAR outperforms existing approaches, highlighting the benefits of leveraging LLMs in recommendation systems. Code is available at https: //github.com/sichunluo/LAMAR.

Recent large language models (LLMs) have witnessed significant advancement in various tasks, including mathematical reasoning and theorem proving. As these two tasks require strict and formal multi-step inference, they are appealing domains for exploring the reasoning ability of LLMs but still face important challenges. Previous studies such as Chain-of-Thought (CoT) have revealed the effectiveness of intermediate steps guidance. However, such step-wise annotation requires heavy labor, leading to insufficient training steps for current benchmarks. To fill this gap, this work introduces MUSTARD, a data generation framework that masters uniform synthesis of theorem and proof data of high quality and diversity. MUSTARD synthesizes data in three stages: (1) It samples a few mathematical concept seeds as the problem category. (2) Then, it prompts a generative language model with the sampled concepts to obtain both the problems and their step-wise formal solutions. (3) Lastly, the framework utilizes a proof assistant (e.g., Lean Prover) to filter the valid proofs. With the proposed MUSTARD, we present a theorem-and-proof benchmark MUSTARDSAUCE with 5,866 valid data points. Each data point contains an informal statement, an informal proof, and a translated formal proof that passes the prover validation. We perform extensive analysis and demonstrate that MUSTARD generates validated high-quality step-by-step data. We further apply the MUSTARDSAUCE for fine-tuning smaller language models. The fine-tuned Llama 2-7B achieves a 15.41% average relative performance gain in automated theorem proving, and 8.18% in math word problems. Codes and data are available at https://github.com/Eleanor-H/MUSTARD.

The recently released GPT-4 Code Interpreter has demonstrated remarkable proficiency in solving challenging math problems, primarily attributed to its ability to seamlessly reason with natural language, generate code, execute code, and continue reasoning based on the execution output. In this paper, we present a method to fine-tune open-source language models, enabling them to use code for modeling and deriving math equations and, consequently, enhancing their mathematical reasoning abilities. We propose a method of generating novel and high-quality datasets with math problems and their code-based solutions, referred to as MathCodeInstruct. Each solution interleaves $\textit{natural language}$, $\textit{code}$, and $\textit{execution results}$. We also introduce a customized supervised fine-tuning and inference approach. This approach yields the MathCoder models, a family of models capable of generating code-based solutions for solving challenging math problems. Impressively, the MathCoder models achieve state-of-the-art scores among open-source LLMs on the MATH (45.2%) and GSM8K (83.9%) datasets, substantially outperforming other open-source alternatives. Notably, the MathCoder model not only surpasses ChatGPT-3.5 and PaLM-2 on GSM8K and MATH but also outperforms GPT-4 on the competition-level MATH dataset. The proposed dataset and models will be released upon acceptance.

Recent progress in large language models (LLMs) like GPT-4 and PaLM-2 has brought significant advancements in addressing math reasoning problems. In particular, OpenAI's latest version of GPT-4, known as GPT-4 Code Interpreter, shows remarkable performance on challenging math datasets. In this paper, we explore the effect of code on enhancing LLMs' reasoning capability by introducing different constraints on the Code Usage Frequency of GPT-4 Code Interpreter. We found that its success can be largely attributed to its powerful skills in generating and executing code, evaluating the output of code execution, and rectifying its solution when receiving unreasonable outputs. Based on this insight, we propose a novel and effective prompting method, explicit $\underline{\text{c}}$ode-based $\underline{\text{s}}$elf-$\underline{\text{v}}$erification (CSV), to further boost the mathematical reasoning potential of GPT-4 Code Interpreter. This method employs a zero-shot prompt on GPT-4 Code Interpreter to encourage it to use code to self-verify its answers. In instances where the verification state registers as "False", the model shall automatically amend its solution, analogous to our approach of rectifying errors during a mathematics examination. Furthermore, we recognize that the states of the verification result indicate the confidence of a solution, which can improve the effectiveness of majority voting. With GPT-4 Code Interpreter and CSV, we achieve an impressive zero-shot accuracy on MATH dataset.

Federated Learning (FL) has emerged as a transformative approach in distributed machine learning, enabling the collaborative training of models using decentralized datasets from diverse sources such as mobile edge devices. This paradigm not only enhances data privacy but also significantly reduces the communication burden typically associated with centralized data aggregation. In wireless networks, Over-the-air Federated Learning (OTA-FL) has been developed as a communication-efficient solution, allowing for the simultaneous transmission and aggregation of model updates from numerous edge devices across the available bandwidth. Gradient compression techniques are necessary to further enhance the communication efficiency of FL, particularly in bandwidth-constrained wireless environments. Despite these advancements, OTA-FL with gradient compression encounters substantial challenges, including learning performance degradation due to compression errors, non-uniform channel fading, and noise interference. Existing power control strategies have yet to fully address these issues, leaving a significant gap in optimizing OTA-FL performance under gradient compression. This paper introduces a novel power control strategy that coordinately integrates gradient compression to optimize OTAFL performance by minimizing the impact of channel fading and noise. Our approach employs linear approximations to complex terms, ensuring the stability and effectiveness of each gradient descent iteration. Numerical results demonstrate that our strategy significantly enhances convergence rates compared to traditional methods like channel inversion and uniform power transmission. This research advances the OTA-FL field and opens new avenues for performance tuning in communication-efficient federated learning systems.

To relieve the growing burden of mental disorders, deep learning techniques have emerged as a promising tool to aid clinicians by detecting abnormal patterns in neuroimaging data. However, the efficacy of such models is contingent upon access to vast pools of patient data, which is impractical for individual healthcare institutions. Moreover, the privacy-preserving policy regulations governing medical images further complicate the pooling of information necessary for training robust models. Federated Learning (FL) offers a solution to this dilemma by aggregating the local model updates without compromising patient privacy. However, current studies fail to adequately account for the need to personalize models according to the diverse structures of local data. In this work, an effective heterogeneous structured FL framework using graph convolutional aggregation dubbed GAHFL is proposed to diagnose mental disorders on functional magnetic resonance imaging data. In addition, we propose to perform the global model self-evaluation to enable the training to emphasize the samples that are difficult to classify. To solve the catastrophic forgetting problem, we build a historical logit pool to awaken the global model’s recognition ability by performing a server knowledge self-distillation. Empirical evaluations demonstrate that the proposed framework achieves averaged diagnosis AUC values of 69.01% and 69.04% with different sizes of public datasets of ABIDE-I and ADHD-200 datasets, respectively. The ablation studies and robustness validation test further demonstrate the superior performance of our framework.

Erasure codes have been widely employed in distributed storage systems to provide high data reliability at a cost of small redundancy. Modern distributed storage systems usually organize the storage nodes in racks, in which the cross-rack communication cost is much more expensive than the intra-rack communication cost. When the original data symbols stored in a single node are updated, it is critical to design erasure codes that can update the corresponding coded symbols with the cross-rack update bandwidth defined as the average amount of symbols transferred across different racks as small as possible. In this paper, we first derive a tight lower bound on the cross-rack update bandwidth under the condition of$(n, k)$reconstruction property that is any$k$out of the$n$nodes can retrieve all the data symbols. Moreover, we derive the lower bound on redundancy subject to the minimum cross-rack update bandwidth. Furthermore, we propose explicit constructions that can achieve both the minimum cross-rack update bandwidth and the minimum redundancy.

Reed-Solomon (RS) codes are constructed over a finite field that have been widely employed in storage and communication systems. Many fast encoding/decoding algorithms such as fast Fourier transform (FFT) and modular approach are designed for RS codes to reduce the encoding/decoding complexity defined as the number of XORs involved in the encoding/decoding procedure. In this paper, we present the construction of RS codes over the cyclic polynomial ring$\mathbb{F}_{2}[x]/(1+x+\ldots+x^{p-1})$and show that our codes are maximum distance separable (MDS) codes. Moreover, we propose the FFT and modular approach over the ring that can be employed in our codes for encoding/decoding complexity reduction. We show that our codes have 17.9% encoding complexity reduction and 7.5% decoding complexity reduction compared with RS codes over finite field, for$(n,k)$= (2048, 1984).

EVENODD+ codes are binary maximum distance separable (MDS) array codes for correcting double disk failures in RAID-6 with asymptotically optimal encoding/decoding/update complexities. However, the number of bits stored in each disk of EVENODD+ codes should be an odd number minus one. In this paper, we present a new construction of EVENODD+ codes that have more flexible parameters. The number of bits stored in each disk of our codes is an odd minus one times any positive integer. Moreover, our codes not only have asymptotically optimal encoding/decoding/update complexities but also have lower encoding/decoding/update complexities than the existing EVENODD+ codes.

Cauchy maximum distance separable (MDS) array codes are widely used in storage systems that can support high fault tolerance with systematic form. However, Cauchy MDS array codes suffer from high encoding/decoding complexities and limited parameters. In this paper, we first construct new Cauchy MDS array codes with circulant structure over quotient rings that have flexible sub-packetization. We show that our codes can support more parameters than the existing Cauchy MDS array codes. The sub-packetization of our codes is a multiple of prime minus one, while the sub-packetization of the existing Rabin-Like codes and circulant Cauchy codes is prime minus one. Second, we propose a fast decoding method by designing new division algorithm and employing the LU decomposition of Cauchy matrix for the proposed Cauchy MDS array codes. We show that the decoding complexity of our codes is nearly the same as new Rabin-Like codes [16], and lower than all the other Cauchy MDS array codes.

The I/O cost, i.e., the total number of symbols to be read during the single node failure/repair process in a distributed storage system, is one of the most important metrics in repairing Reed-Solomon (RS) codes by the linear repair scheme. In this paper, we construct a linear repair scheme that is applicable to arbitrary$(n,\ k)$RS codes. We show that most existing repair schemes of RS codes can be viewed as a special case of our repair scheme.

In distributed matrix multiplication, stragglers present a significant challenge. Coding techniques are often employed to mitigate this issue; however, their effectiveness is typically limited to handling a fixed number of stragglers. To address the issue of a fluctuating number of stragglers, we propose a novel approach that leverages a variant of Luby transform (LT) codes for distributed matrix multiplication, augmented with a feedback mechanism. This enables the system to tolerate a variable number of stragglers, potentially reducing the redundant computation to complete the task compared with existing coding methods dealing with a fixed number of strangers. Furthermore, we comprehensively analyze the computational complexity associated with the proposed algorithm.

This paper introduces a privacy-preserving distributed learning framework via private-key homomorphic encryption. Using randomness in the quantization of gradients, our encryption replaces the Gaussian error term of Learning With Errors (LWE) with quantized gradients, thus reducing the error expansion speed in conventional LWE-based homomorphic en-cryption. The proposed system allows a large number of learning participants to engage in distributed learning collaboratively over an honest-but-curious server, while ensuring the cryptographic security of participants' uploaded gradients.

To address the communication bottleneck challenge in distributed learning, our work introduces a novel two-stage quantization strategy designed to enhance the communication efficiency of distributed Stochastic Gradient Descent (SGD). The proposed method initially employs truncation to mitigate the impact of long-tail noise, followed by a non-uniform quantization of the post-truncation gradients based on their statistical characteristics. We provide a comprehensive convergence analysis of the quantized distributed SGD, establishing theoretical guarantees for its performance. Furthermore, by minimizing the convergence error, we derive optimal closed-form solutions for the truncation threshold and non-uniform quantization levels under given communication constraints. Both theoretical insights and extensive experimental evaluations demonstrate that our proposed algorithm outperforms existing quantization schemes, striking a superior balance between communication efficiency and convergence performance.

One-shot object detection (OSOD) uses a query patch to identify the same category of object in a target image. As the OSOD setting, the target images are required to contain the object category of the query patch, and the image styles (domains) of the query patch and target images are always similar. However, in practical application, the above requirements are not commonly satisfied. Therefore, we propose a new problem namely Cross-Domain Object Search (CDOS), where the object categories of the query patch and target image are decoupled, and the image styles between them may also be significantly different. For this problem, we develop a new method, which incorporates both foreground-background contrastive learning heads and a domain-generalized feature augmentation technique. This makes our method effectively handle the object category gap and domain distribution gap, between the query patch and target image in the training and testing datasets. We further build a new benchmark for the proposed CDOS problem, on which our method shows significant performance improvements over the comparison methods.

Formal verification (FV) has witnessed growing significance with current emerging program synthesis by the evolving large language models (LLMs). However, current formal verification mainly resorts to symbolic verifiers or hand-craft rules, resulting in limitations for extensive and flexible verification. On the other hand, formal languages for automated theorem proving, such as Isabelle, as another line of rigorous verification, are maintained with comprehensive rules and theorems. In this paper, we propose FVEL, an interactive Formal Verification Environment with LLMs. Specifically, FVEL transforms a given code to be verified into Isabelle, and then conducts verification via neural automated theorem proving with an LLM. The joined paradigm leverages the rigorous yet abundant formulated and organized rules in Isabelle and is also convenient for introducing and adjusting cutting-edge LLMs. To achieve this goal, we extract a large-scale FVELER. The FVELER dataset includes code dependencies and verification processes that are formulated in Isabelle, containing 758 theories, 29,304 lemmas, and 201,498 proof steps in total with in-depth dependencies. We benchmark FVELER in the FVEL environment by first fine-tuning LLMs with FVELER and then evaluating them on Code2Inv and SV-COMP. The results show that FVEL with FVELER fine-tuned Llama3-8B solves 17.39% (69→81) more problems, and Mistral-7B 12% (75→84) more problems in SV-COMP. And the proportion of proof errors is reduced. Project page: https://fveler.github.io/.

Quantization of large language models (LLMs) faces significant challenges, particularly due to the presence of outlier activations that impede efficient low-bit representation. Traditional approaches predominantly address Normal Outliers, which are activations across all tokens with relatively large magnitudes. However, these methods struggle with smoothing Massive Outliers that display significantly larger values, which leads to significant performance degradation in low-bit quantization. In this paper, we introduce DuQuant, a novel approach that utilizes rotation and permutation transformations to more effectively mitigate both massive and normal outliers. First, DuQuant starts by constructing the rotation matrix, using specific outlier dimensions as prior knowledge, to redistribute outliers to adjacent channels by block-wise rotation. Second, We further employ a zigzag permutation to balance the distribution of outliers across blocks, thereby reducing block-wise variance. A subsequent rotation further smooths the activation landscape, enhancing model performance. DuQuant simplifies the quantization process and excels in managing outliers, outperforming the state-of-the-art baselines across various sizes and types of LLMs on multiple tasks, even with 4-bit weight-activation quantization. Our code is available at https://github.com/Hsu1023/DuQuant.

We consider broadcasting a block of data packets to multiple users via instantly decodable network coding (IDNC) under the semi-online feedback transmission mode. In this paper, we first introduce a new class of IDNC schemes called lightweight IDNC, tailored for wireless broadcast with stringent computational load at the receiver end. Unlike traditional IDNC that may encode a larger number of original packets together, lightweight IDNC limits each coded packet to a combination of at most two original packets. We obtain lower bounds on the total completion delay that apply to arbitrary lightweight IDNC schemes. We further investigate the number of transmission rounds as another performance metric, and explicitly characterize its distribution and expectation. The characterizations apply to arbitrary partition-based IDNC schemes, including the lightweight IDNC schemes considered in this paper. A new efficient algorithm is also proposed to construct lightweight IDNC schemes which grants the original packets with lower coding opportunity a higher priority to be encoded. Numerical analyses demonstrate that the lightweight IDNC schemes constructed by the new algorithm not only achieve lower completion and decoding delays in comparison with the ones constructed by the existing algorithm but also adhere closely to theoretical lower bounds, demonstrating their efficiency and practical utility.

Conversational semantic role labeling (CSRL) is believed to be a crucial step toward dialogue understanding. By incorporating the CSRL information into the conversational models, previous work (Xu et al., 2021) has confirmed the usefulness of CSRL to downstream conversation-based tasks, including multi-turn dialogue rewriting and multi-turn dialogue response generation. However, (Xu et al., 2021) found that the quality of the extracted CSRL structures would consequently affect the performance of downstream dialogue tasks while the performance of existing CSRL models is still unsatisfactory. There are two major problems in existing CSRL models to handle predicate-aware and conversational structural information. First, they ignore the fact that explicitly correlating the predicate and the context utterances could help the model better identify the arguments. Secondly, these models do not encode some vital conversational structural information, such as the speaker information which is necessary for modeling inter-speaker dependency. In this paper, we model the conversational structure-aware features based on three components: 1) the predicate-aware module which aims to capture rich correlations between the predicate and utterances; 2) a speaker-aware graph network which explicitly encodes the speaker-dependent information; 3) a novel structure-aware dialogue modeling method for the model warm-up. Experimental results on benchmark datasets show that our model significantly outperforms the baselines. We also examine the efficiency of our model and its effectiveness in low-resource scenarios. We find that our model can achieve better performance with less training time and training data than the existing models. In addition, further improvements are observed when applying the CSRL information extracted by our model into downstream dialogue tasks, which consistently indicates the superiority of our model.

Spatio-temporal resolution adaptive (STRA) coding has been repeatedly proven to be a promising way to improve coding efficiency and reduce coding complexity. The wide consensus is that the optimal subsampled resolution and frame rate should be governed by so- called generalized rate-distortion performance based on the ultimately perceived distortion. However, it is non-trivial to accurately predict the quality of reconstructed videos due to the fact that the distortion originates from both subsampling and compression. To address this issue, we propose a novel video quality assessment model that is fully aware of the information available in downsampled videos for compression, such as resolution and frame rate. More specifically, the proposed model relies on quality-aware spatial features that are extracted by an image quality fine-tuned backbone. Subsequently, the spatio-temporal quality is modeled based on the transformer encoder, which is adaptive to the downsampling spatial and temporal resolutions. This enables the transformer encoder to produce discriminative features that capture long-range temporal dependencies related to the current context. The quality score, which is the output of the transformer encoder, thus reflects both the influence of the subsampling and compression. We conduct extensive experiments that demonstrate the superiority of the proposed model over state-of-the-art methods on four subsampling and compression video quality datasets. Furthermore, we apply the proposed model to bitrate ladder optimization, leading to a perceptual-aware spatial and temporal downsampling strategy that yields promising bitrate savings. The source codes of the proposed model will be publicly available athttps://github.com/h4nwei/STRA-VQA.

Knowledge transfer from optimized problems has emerged as a promising technique for enhancing evolutionary search. However, most studies in this domain primarily concentrate on devising knowledge transfer mechanisms for specific problem domains, often lacking the examination of the fundamental aspects of knowledge transfer, i.e., what, when and how to transfer across diverse scenarios. This not only restricts the generality of these algorithms but also hinders their practical applicability. In light of this, this paper: 1) reviews a vast array of techniques associated with the crucial aspects of solution transfer and 2) conducts a series of experiments to explore the underlying transfer mechanisms that enhance the evolutionary search. In particular, we first define solution transferability in the context of evolutionary search, which provides a new perspective in understanding what, when and how to transfer in enhancing evolutionary search. Next, through comprehensive experiments, we find that the approximation and evaluation of solution transferability is of great importance in designing what, when and how to transfer towards enhanced evolutionary search. Furthermore, our empirical study also discusses the counterintuitive performance improvements unrelated to the search experience of source tasks. The source code for reproducing our experiments is available at https://github.com/XmingHsueh/STO-EC.

Federated recommendation systems employ federated learning techniques to safeguard user privacy by transmitting model parameters instead of raw user data between user devices and the central server. Nevertheless, the current federated recommender system faces three significant challenges: (1) data heterogeneity: the heterogeneity of users’ attributes and local data necessitates the acquisition of personalized models to improve the performance of federated recommendation; (2) model performance degradation: the privacy-preserving protocol design in the federated recommendation, such as pseudo item labeling and differential privacy, would deteriorate the model performance; (3) communication bottleneck: the standard federated recommendation algorithm can have a high communication overhead. Previous studies have attempted to address these issues, but none have been able to solve them simultaneously. In this article, we propose a novel framework, named PerFedRec++ , to enhance the personalized federated recommendation with self-supervised pre-training. Specifically, we utilize the privacy-preserving mechanism of federated recommender systems to generate two augmented graph views, which are used as contrastive tasks in self-supervised graph learning to pre-train the model. Pre-training enhances the performance of federated models by improving the uniformity of representation learning. Also, by providing a better initial state for federated training, pre-training makes the overall training converge faster, thus alleviating the heavy communication burden. We then construct a collaborative graph to learn the client representation through a federated graph neural network. Based on these learned representations, we cluster users into different user groups and learn personalized models for each cluster. Each user learns a personalized model by combining the global federated model, the cluster-level federated model, and its own fine-tuned local model. Experiments on three real-world datasets show that our proposed method achieves superior performance over existing methods.

In recent years, the Internet of Vehicles (IoV) has experienced significant growth, but the lack of effective secret key establishment remains a security concern due to the dynamic and ad-hoc nature of IoV communications. Physical layer key generation has emerged as a promising solution for establishing a pair of cryptographic keys in a lightweight and information-theoretic secure manner. However, previous works have primarily focused on legacy communication technologies, such as Wi-Fi, ZigBee, and 5 G, which are limited to short-range IoV communications. With the emergence of Long-range (LoRa) communication technology, which features long-range, low power, and extremely low data rates, new challenges arise for key generation in long-range IoV scenarios. This paper presentsVehicle-Key, a secret key generation system designed to secure LoRa-enabled IoV communications.Vehicle-Keypresents an innovative scenario adaptive deep learning model that performs channel prediction and quantization concurrently while reducing the training cost through a data augmentation pipeline and enhancing the model's generalization using a domain-adaption method. Additionally, we propose a bloom filter-assisted autoencoder-based reconciliation method to significantly improve the key agreement rate. Comprehensive real-world experiments show thatVehicle-Keysurpasses the State-of-the-Art, achieving a 15.26%–50.35% improvement in key agreement rate and a 9–15× increase in key generation rate. Moreover, the proposed method attains a 4.37--9.33% improvement when adapted to new scenarios with limited data sizes. A security analysis demonstrates thatVehicle-Keyis resilient against several common attacks. Furthermore, we implementVehicle-Keyon a Raspberry Pi and demonstrate its ability to execute within 3.5 ms.

Smart cameras with on-device deep learning inference capabilities are enabling distributed video analytics at the data source without sending raw video data over the often unreliable and congested wireless network. However, how to unleash the full potential of the computing power of the camera network requires careful coordination among the distributed cameras, catering to the uneven workload distribution and the heterogeneous computing capabilities. This paper presents CrossVision, a distributed framework for real-time video analytics, that retains all video data on cameras while achieving low inference delay and high inference accuracy. The key idea behind CrossVision is that there is a significant information redundancy in the video content captured by cameras with overlapped Field-of-Views (FoVs), which can be exploited to reduce inference workload as well as improve inference accuracy between correlated cameras. CrossVision consists of three main components to realize its function: a Region-of-Interest (RoI) Matcher that discovers video content correlation based on a segmented FoV transformation scheme; a Workload Balancer that implements a randomized workload balancing strategy based on a bulk-queuing analysis, taking into account the cameras’ predicted future workload arrivals; an Accuracy Guard that ensures that the inference accuracy is not sacrificed as redundant information is discarded. We evaluate CrossVision in a hardware-augmented simulator and on real-world cross-camera datasets, and the results show that CrossVision is able to significantly reduce inference delay while improving the inference accuracy compared to a variety of baseline approaches.

There is a growing consensus in the research community that the optimization of low-light image enhancement approaches should be guided by the visual quality perceived by end users. Despite the substantial efforts invested in the design of low-light enhancement algorithms, there has been comparatively limited focus on assessing subjective and objective quality systematically. To mitigate this gap and provide a clear path towards optimizing low-light image enhancement for better visual quality, we propose a gap-closing framework. In particular, our gap-closing framework starts with the creation of a large-scale dataset for Subjective QUality Assessment of REconstructed LOw-Light Images (SQUARE-LOL). This database serves as the foundation for studying the quality of enhanced images and conducting a comprehensive subjective user study. Subsequently, we propose an objective quality assessment measure that plays a critical role in bridging the gap between visual quality and enhancement. Finally, we demonstrate that our proposed objective quality measure can be incorporated into the process of optimizing the learning of the enhancement model toward perceptual optimality. We validate the effectiveness of our proposed framework through both the accuracy of quality prediction and the perceptual quality of image enhancement.

The ubiquitous long-tail distribution of inherent user behaviors results in worse recommendation performance for the items with fewer user records (i.e., tail items) than those with richer ones (i.e., head items). Graph-based recommendation methods (e.g., using graph neural networks) have recently emerged as a powerful tool for recommender systems, often outperforming traditional methods. However, existing techniques for alleviating the long-tail problem mainly focus on traditional methods. There is a lack of graph-based methods that can efficiently deal with the long-tail problem.

Meetings typically involve multiple participants and lengthy conversations, resulting in redundant and trivial content.To overcome these challenges, we propose a two-step framework, Reconstruct before Summarize (RbS), for effective and efficient meeting summarization.RbS first leverages a self-supervised paradigm to annotate essential contents by reconstructing the meeting transcripts.Secondly, we propose a relative positional bucketing (RPB) algorithm to equip (conventional) summarization models to generate the summary.Despite the additional reconstruction process, our proposed RPB significantly compressed the input, leading to faster processing and reduced memory consumption compared to traditional summarization methods.We validate the effectiveness and efficiency of our method through extensive evaluations and analysis.On two meeting summarization datasets, AMI and ICSI, our approach outperforms previous state-of-the-art approaches without relying on large-scale pretraining or expert-grade annotating tools.

General-purpose text decoding approaches are usually adopted for dialogue response generation.Although the quality of the generated responses can be improved with dialogue-specific encoding methods, conversational decoding methods are still under-explored.Inspired by Wu et al. (2023) that a good dialogue feature space should follow the rules of locality and isotropy, we present a fine-grained conversational decoding method, termed isotropic and proximal search (IPS).Our method is designed to generate the semantic-concentrated response, while still maintaining informativeness and discrimination against the context.Experiments show that our approach outperforms existing decoding strategies in the dialogue field across both automatic and human evaluation metrics.More in-depth analyses further confirm the effectiveness of our approach.

Distributed stochastic gradient descent (SGD) with gradient compression has become a popular communication-efficient solution for accelerating distributed learning. One commonly used method for gradient compression is Top-K sparsification, which sparsifies the gradients by a fixed degree during model training. However, there has been a lack of an adaptive approach to adjust the sparsification degree to maximize the potential of the model's performance or training speed. This paper proposes a novel adaptive Top-K in SGD framework that enables an adaptive degree of sparsification for each gradient descent step to optimize the convergence performance by balancing the tradeoff between communication cost and convergence error. Firstly, an upper bound of convergence error is derived for the adaptive sparsification scheme and the loss function. Secondly, an algorithm is designed to minimize the convergence error under the communication cost constraints. Finally, numerical results on the MNIST and CIFAR-10 datasets demonstrate that the proposed adaptive Top-K algorithm in SGD achieves a significantly better convergence rate compared to state-of-the-art methods, even after considering error compensation.

The high prevalence of mental disorders gradually poses a huge pressure on the public healthcare services. Deep learning-based computer-aided diagnosis (CAD) has emerged to relieve the tension in healthcare institutions by detecting abnormal neuroimaging-derived phenotypes. However, training deep learning models relies on sufficient annotated datasets, which can be costly and laborious. Semi-supervised learning (SSL) and transfer learning (TL) can mitigate this challenge by leveraging unlabeled data within the same institution and advantageous information from source domain, respectively. This work is the first attempt to propose an effective semi-supervised transfer learning (SSTL) framework dubbed S3TL for CAD of mental disorders on fMRI data. Within S3TL, a secure cross-domain feature alignment method is developed to generate target-related source model in SSL. Subsequently, we propose an enhanced dual-stage pseudo-labeling approach to assign pseudo-labels for unlabeled samples in target domain. Finally, an advantageous knowledge transfer method is conducted to improve the generalization capability of the target model. Comprehensive experimental results demonstrate that S3TL achieves competitive accuracies of 69.14%, 69.65%, and 72.62% on ABIDE-I, ABIDE-II, and ADHD-200 datasets, respectively. Furthermore, the simulation experiments also demonstrate the application potential of S3TL through model interpretation analysis and federated learning extension.

Federated recommendation applies federated learning techniques in recommendation systems to help protect user privacy by exchanging models instead of raw user data between user devices and the central server. Due to the heterogeneity in user's attributes and local data, attaining personalized models is critical to help improve the federated recommendation performance. In this paper, we propose a Graph Neural Network based Personalized Federated Recommendation (PerFedRec) framework via joint representation learning, user clustering, and model adaptation. Specifically, we construct a collaborative graph and incorporate attribute information to jointly learn the representation through a federated GNN. Based on these learned representations, we cluster users into different user groups and learn personalized models for each cluster. Then each user learns a personalized model by combining the global federated model, the cluster-level federated model, and the user's fine-tuned local model. To alleviate the heavy communication burden, we intelligently select a few representative users (instead of randomly picked users) from each cluster to participate in training. Experiments on real-world datasets show that our proposed method achieves superior performance over existing methods.

The recent popularity of edge devices and Artificial Intelligent of Things (AIoT) has driven a new wave of contextual recommendations, such as location based Point of Interest (PoI) recommendations and computing resource-aware mobile app recommendations. In many such recommendation scenarios, contexts are drifting over time. For example, in a mobile game recommendation, contextual features like locations, battery, and storage levels of mobile devices are frequently drifting over time. However, most existing graph-based collaborative filtering methods are designed under the assumption of static features. Therefore, they would require frequent retraining and/or yield graphical models burgeoning in sizes, impeding their suitability for context-drifting recommendations.

In this paper, we propose a new federated multi-armed bandit framework with vector rewards that can abstract personalized recommendations. In our setup, each reward is a vector, and each user may be interested in a different dimension of this vector. For example, some users may specifically care about the food quality, service, environment, location, or price, in restaurant recommendations. We propose a Federated Personalized Arm Elimination (FPAE) algorithm and explore two communication constrained scenarios. One scenario allows only one communication round during learning, while the other allows multiple communication rounds. We design two algorithms (FPAE-1 and FPAE-R) for the scenarios and theoretically evaluate their regret. We show that communication can speed up the learning process and that there is a tradeoff between the communication cost and the learning performance as captured by the regret. Numerical analysis results demonstrate the performance of our proposed methods.

Gradient-based training in federated learning is known to be vulnerable to faulty/malicious clients, which are often modeled as Byzantine clients. To this end, previous work either makes use of auxiliary data at parameter server to verify the received gradients (e.g., by computing validation error rate) or leverages statistic-based methods (e.g. median and Krum) to identify and remove malicious gradients from Byzantine clients. In this paper, we remark that auxiliary data may not always be available in practice and focus on the statistic-based approach. However, recent work on model poisoning attacks has shown that well-crafted attacks can circumvent most of median- and distance-based statistical defense methods, making malicious gradients indistinguishable from honest ones. To tackle this challenge, we show that the element-wise sign of gradient vector can provide valuable insight in detecting model poisoning attacks. Based on our theoretical analysis of the Little is Enough attack, we propose a novel approach called SignGuard to enable Byzantine-robust federated learning through collaborative malicious gradient filtering. More precisely, the received gradients are first processed to generate relevant magnitude, sign, and similarity statistics, which are then collaboratively utilized by multiple filters to eliminate malicious gradients before final aggregation. Finally, extensive experiments of image and text classification tasks are conducted under recently proposed attacks and defense strategies. The numerical results demonstrate the effectiveness and superiority of our proposed approach.

Recent years have witnessed the remarkable growth of the Internet of Vehicles (IoV). Due to the high dynamics and ad-hoc nature of IoV communication, the lack of effective secret key establishment in IoV remains a security bottleneck. Physical layer key generation has emerged as a promising technology to establish a pair of cryptographic keys in a lightweight and information-theoretic secure way. However, prior works mainly focus on legacy communication technologies such as Wi-Fi, ZigBee, and 5G which can only achieve short range IoV communications. The emergence of Long-range (LoRa) communication technology that features long-range, low power, and extremely low data rate, brings new challenges for key generation in long range IoV scenarios. In this paper, we present Vehicle-Key, which is a secret key generation system to secure LoRa-enabled IoV communications. In Vehicle-Key, we design a novel deep learning model that can achieve channel prediction and quantization simultaneously. Additionally, we propose an autoencoder-based reconciliation method that improves the key agreement rate significantly. Extensive real-world experiments show that Vehicle-Key improves the key agreement rate by 15.10%–49.81% and key generation rate by 9–14× compared with the state-of-the-art. Security analysis demonstrates that Vehicle-Key is secure against several common attacks. Moreover, we implement Vehicle-Key on a Raspberry Pi and show that it can be executed in 3.4 ms.

The high prevalence of mental disorders gradually poses a huge pressure on the public healthcare services. Recently, deep learning-based computer-aided diagnosis has been introduced to relieve the tension in healthcare institutions by automatically detecting abnormal neuroimaging-derived pheno-types in patients. However, the training of deep learning models relies on sufficiently large annotated datasets, which can be costly, time-consuming, and laborious. Semi-supervised learning (SSL) can mitigate this challenge by leveraging both labeled and unlabeled samples. In this work, an effective dual-stage pseudo-labeling based classification framework dubbed DSPL is proposed to diagnose mental disorders on functional magnetic resonance imaging data. A bicriteria-based pseudo-labels selection method is developed to filter out inferior pseudo-labeled samples. Subsequently, we further propose a self-mutual learning enhanced pseudo-labeling generation approach to mitigate the adverse effects bought by the noisy pseudo-labeled samples. On real-world datasets, the proposed method achieves diagnosis accuracies of 68.09%, 67.94%, and 68.13% on ABIDE-I, ABIDE-II, and ADHD-200, respectively. Ablation study suggests that each component in DSPL makes a great contribution to performance improvement.

Embedding-based neural topic models could explicitly represent words and topics by embedding them to a homogeneous feature space, which shows higher interpretability. However, there are no explicit constraints for the training of embeddings, leading to a larger optimization space. Also, a clear description of the changes in embeddings and the impact on model performance is still lacking. In this paper, we propose an embedding regularized neural topic model, which applies the specially designed training constraints on word embedding and topic embedding to reduce the optimization space of parameters. To reveal the changes and roles of embeddings, we introduce uniformity into the embedding-based neural topic model as the evaluation metric of embedding space. On this basis, we describe how embeddings tend to change during training via the changes in the uniformity of embeddings. Furthermore, we demonstrate the impact of changes in embeddings in embedding-based neural topic models through ablation studies. The results of experiments on two mainstream datasets indicate that our model significantly outperforms baseline models in terms of the harmony between topic quality and document modeling. This work is the first attempt to exploit uniformity to explore changes in embeddings of embedding-based neural topic models and their impact on model performance to the best of our knowledge.

Data hiding with deep neural networks (DNNs) has experienced impressive successes in recent years. A prevailing scheme is to train an autoencoder, consisting of an encoding network to embed (or transform) secret messages in (or into) a carrier, and a decoding network to extract the hidden messages. This scheme may suffer from several limitations regarding practicability, security, and embedding capacity. In this work, we describe a different computational framework to hide images in deep probabilistic models. Specifically, we use a DNN to model the probability density of cover images, and hide a secret image in one particular location of the learned distribution. As an instantiation, we adopt a SinGAN, a pyramid of generative adversarial networks (GANs), to learn the patch distribution of one cover image. We hide the secret image by fitting a deterministic mapping from a fixed set of noise maps (generated by an embedding key) to the secret image during patch distribution learning. The stego SinGAN, behaving as the original SinGAN, is publicly communicated; only the receiver with the embedding key is able to extract the secret image. We demonstrate the feasibility of our SinGAN approach in terms of extraction accuracy and model security. Moreover, we show the flexibility of the proposed method in terms of hiding multiple images for different receivers and obfuscating the secret image.

Caching popular content at edge servers is a promising way to achieve high quality of experience for the wireless edge network. However, the design of an effective cache placement scheme still faces two key challenges: 1) content popularity profiles may be unknown in advance. Some online learning techniques can be incorporated to tackle this uncertainty. 2) content popularity profiles may be heterogeneous among different edge servers. Naively utilizing feedback collected by others may substantially hurt the local estimation if there are large disparities between the popularities. Therefore, an adptive information aggregation protocol is needed. In this paper, we first formulate the caching problem as a multi-agent multi-play bandits problem with heterogeneous reward distributions. We then propose a federated adaptive online learning algorithm. Specifically, each MES employs a model mixture technique to aggregate local user feedback and the knowledge captured by the central server. Our theoretical results show that the upper bound on the cache hit loss (e.g., regret) depends on the heterogeneity and information sharing across MESs. The simulation results demonstrate the effectiveness of our method against baseline schemes on both regrets and cache hit rate.

MOTIVATION: The rapid growth in literature accumulates diverse and yet comprehensive biomedical knowledge hidden to be mined such as drug interactions. However, it is difficult to extract the heterogeneous knowledge to retrieve or even discover the latest and novel knowledge in an efficient manner. To address such a problem, we propose EGFI for extracting and consolidating drug interactions from large-scale medical literature text data. Specifically, EGFI consists of two parts: classification and generation. In the classification part, EGFI encompasses the language model BioBERT which has been comprehensively pretrained on biomedical corpus. In particular, we propose the multihead self-attention mechanism and packed BiGRU to fuse multiple semantic information for rigorous context modeling. In the generation part, EGFI utilizes another pretrained language model BioGPT-2 where the generation sentences are selected based on filtering rules. RESULTS: We evaluated the classification part on 'DDIs 2013' dataset and 'DTIs' dataset, achieving the F1 scores of 0.842 and 0.720 respectively. Moreover, we applied the classification part to distinguish high-quality generated sentences and verified with the existing growth truth to confirm the filtered sentences. The generated sentences that are not recorded in DrugBank and DDIs 2013 dataset demonstrated the potential of EGFI to identify novel drug relationships. AVAILABILITY: Source code are publicly available at https://github.com/Layne-Huang/EGFI.

Communication bottleneck and data privacy are two critical concerns in federated multi-armed bandit (MAB) problems, such as situations in decision-making and recommendations of connected vehicles via wireless. In this paper, we design the privacy-preserving communication-efficient algorithm in such problems and study the interactions among privacy, communication and learning performance in terms of the regret. To be specific, we design privacy-preserving learning algorithms and communication protocols and derive the learning regret when networked private agents are performing online bandit learning in a master-worker, a decentralized and a hybrid structure. Our bandit learning algorithms are based on epoch-wise sub-optimal arm eliminations at each agent and agents exchange learning knowledge with the server/each other at the end of each epoch. Furthermore, we adopt the differential privacy (DP) approach to protect the data privacy at each agent when exchanging information; and we curtail communication costs by making less frequent communications with fewer agents participation. By analyzing the regret of our proposed algorithmic framework in the master-worker, decentralized and hybrid structures, we theoretically show trade-offs between regret and communication costs/privacy. Finally, we empirically show these trade-offs which are consistent with our theoretical analysis.

Gradient compression (e.g., gradient quantization and gradient sparsification) is a core technique in reducing communication costs in distributed learning systems. The recent trend of gradient compression is to use a varying number of bits across iterations, however, relying on empirical observations or engineering heuristics without a systematic treatment and analysis. To the best of our knowledge, a general dynamic gradient compression that leverages both quantization and sparsification techniques is still far from understanding. This paper proposes a novel Adaptively-Compressed Stochastic Gradient Descent (AC-SGD) strategy to adjust the number of quantization bits and the sparsification size with respect to the norm of gradients, the communication budget, and the remaining number of iterations. In particular, we derive an upper bound, tight in some cases, of the convergence error for arbitrary dynamic compression strategy. Then we consider communication budget constraints and propose an optimization formulation - denoted as theAdaptive Compression Problem (ACP)- for minimizing the deep model’s convergence error under such constraints. By solving the ACP, we obtain an enhanced compression algorithm that significantly improves model accuracy under given communication budget constraints. Finally, through extensive experiments on computer vision and natural language processing tasks on MNIST, CIFAR-10, CIFAR-100 and AG-News datasets, respectively, we demonstrate that our compression scheme significantly outperforms the state-of-the-art gradient compression methods in terms of mitigating communication costs.

Evolutionary sequential transfer optimization is a paradigm that leverages search experience from solved source optimization tasks to accelerate the evolutionary search of a target task. Even though many algorithms have been developed, they mainly focus on objective-homogeneous problems, where the source and target tasks possess a similar number of objectives. In this work, we explore objective-heterogeneous problems, in which knowledge transfers across single-objective optimization problems (SOPs), multiobjective optimization problems (MOPs), and many-objective optimization problems (MaOPs). Objective-heterogeneous problems challenge the existing methods due to the diverse search and objective spaces between the source and the target task. To address this issue, we present a decision variable analysis-based transfer method that can conduct knowledge transfer across problems with the different numbers of objectives. We first separate decision variables of MOPs and MaOPs into convergence-related variables (CVs) and diversity-related variables (DVs), according to their roles while treating variables of SOPs as CVs. Then, we propose a convergence transfer module to transfer knowledge of CVs to speed up the convergence. It aligns both solutions and fitness ranks for preserving fitness rank consistency between the source and target tasks, whereby accelerating search speed. Besides, a diversity transfer module is presented to refine the distribution of DVs to maintain the population diversity. The experimental results on objective-heterogeneous test problems and a real-world case study have demonstrated the effectiveness of the proposed algorithm.

Federated learning (FL) has attracted tremendous attentions in recent years due to its privacy-preserving measures and great potential in some distributed but privacy-sensitive applications, such as finance and health. However, high communication overloads for transmitting high-dimensional networks and extra security masks remain a bottleneck of FL. This article proposes a communication-efficient FL framework with an Adaptive Quantized Gradient (AQG), which adaptively adjusts the quantization level based on a local gradient’s update to fully utilize the heterogeneity of local data distribution for reducing unnecessary transmissions. In addition, client dropout issues are taken into account and an Augmented AQG is developed, which could limit the dropout noise with an appropriate amplification mechanism for transmitted gradients. Theoretical analysis and experiment results show that the proposed AQG leads to 18% to 50% of additional transmission reduction as compared with existing popular methods, including Quantized Gradient Descent (QGD) and Lazily Aggregated Quantized (LAQ) gradient-based methods without deteriorating convergence properties. Experiments with heterogenous data distributions corroborate a more significant transmission reduction compared with independent identical data distributions. The proposed AQG is robust to a client dropping rate up to 90% empirically, and the Augmented AQG manages to further improve the FL system’s communication efficiency with the presence of moderate-scale client dropouts commonly seen in practical FL scenarios.

Conversational semantic role labeling (CSRL) is believed to be a crucial step towards dialogue understanding.However, it remains a major challenge for existing CSRL parser to handle conversational structural information.In this paper, we present a simple and effective architecture for CSRL which aims to address this problem.Our model is based on a conversational structure-aware graph network which explicitly encodes the speaker dependent information.We also propose a multi-task learning method to further improve the model.Experimental results on benchmark datasets show that our model with our proposed training objectives significantly outperforms previous baselines.

This paper considers benefits of coding techniques in recommendation systems operating over wireless channels with erasures. We identify scenarios where coded broadcasting can increase the overall user satisfaction at a fixed channel utilization level. Such opportunities arise both when user preferences are unknown, and must be explored, and when they are known and must be exploited to recommend optimally. We determine the magnitude of the potential gains and show that coding is most beneficial if users have heterogeneous preferences. Finally, we provide inequalities that can be evaluated to determine whether coding would be beneficial for a certain reward structure.

Traditionally, decision making in the stock market greatly depends on human expertise in sophisticated information processing, such as analyzing various financial reports and related news. However, limitations of expertise, time, and resources make investors suffer from information overload and information imbalance and may pose a negative impact on the investment market. Recent improvements in computing power, the availability of large volumes of data, and the advanced Artificial Intelligence (AI) techniques empower us with the ability to assist decision making in the stock market. In this paper, we present an integrated system that comprehensively monitors the downside risks of individual stocks and the overall market. Specifically, the stock downside risk is predicted based on quantitative data of related stocks, where the relationship between stocks is measured by constructing an Enterprise Knowledge Graph (EKG) using public knowledge. On the other hand, the market downside risk is predicted based on information extracted from daily news. For each risk, a Temporal Convolutional Network (TCN) is trained to output a continuous risk level that reveals both the direction and amplitude of incoming changes. Finally, key information and the predicted risk levels are organized into a condensed and understandable dashboard to interact with investors. Experiments on three focal stocks in the U.S. market suggest convincing accuracy in both stock risk and market risk modeling. Further visualization analysis demonstrates that our model has the potential to inform reverse changes of a stock movement ten days in advance.

The training efficiency of distributed learning systems is vulnerable to stragglers, namely, those slow worker nodes. A naive strategy is performing the distributed learning by incor-porating the fastest K workers and ignoring these stragglers, which may induce high deviation for non-IID data. To tackle this, we develop a Live Gradient Compensation (LGC) strategy to incorporate the one-step delayed gradients from stragglers, aiming to accelerate learning process and utilize the stragglers simultaneously. In LGC framework, mini-batch data are divided into smaller blocks and processed separately, which makes the gradient computed based on partial work accessible. In addition, we provide theoretical convergence analysis of our algorithm for non-convex optimization problem under non-IID training data to show that LGC-SGD has almost the same convergence error as full synchronous SGD. The theoretical results also allow us to quantify a novel tradeoff in minimizing training time and error by selecting the optimal straggler threshold. Finally, extensive simulation experiments of image classification on CIFAR-10 dataset are conducted, and the numerical results demonstrate the effectiveness of our proposed strategy.

Matrix factorization is an important representation learning algorithm, e.g., recommender systems, where a large matrix can be factorized into the product of two low dimensional matrices termed as latent representations. This paper investigates the problem of matrix factorization in distributed computing systems with stragglers, those computing nodes that are slow to return computation results. A computation procedure, called coded Alternative Least Square (ALS), is proposed for mitigating the effect of stragglers in such systems. The coded ALS algorithm iteratively computes two low dimensional latent matrices by solving various linear equations, with the Entangled Polynomial Code (EPC) as a building block. We theoretically characterize the maximum number of stragglers that the algorithm can tolerate (or the recovery threshold) in relation to the redundancy of coding (or the code rate). In addition, we theoretically show the computation complexity for the coded ALS algorithm and conduct numerical experiments to validate our design.

Gradient quantization is an emerging technique in reducing communication costs in distributed learning. Existing gradient quantization algorithms often rely on engineering heuristics or empirical observations, lacking a systematic approach to dynamically quantize gradients. This paper addresses this issue by proposing a novel dynamically quantized SGD (DQ-SGD) framework, enabling us to dynamically adjust the quantization scheme for each gradient descent step by exploring the trade-off between communication cost and convergence error. We derive an upper bound, tight in some cases, of the convergence error for a restricted family of quantization schemes and loss functions. We design our DQSGD algorithm via minimizing the communication cost under the convergence error constraints. Finally, through extensive experiments on large-scale natural language processing and computer vision tasks on AG-News, CFAR-10, and CIFAR-100 datasets, we demonstrate that our quantization scheme achieves better tradeoffs between the communication cost and learning performance than other state-of-the-art gradient quantization methods.

Semantic role labeling (SRL) aims to extract the arguments for each predicate in an input sentence. Traditional SRL can fail to analyze dialogues because it only works on every single sentence, while ellipsis and anaphora frequently occur in dialogues. To address this problem, we propose the conversational SRL task, where an argument can be the dialogue participants, a phrase in the dialogue history or the current sentence. As the existing SRL datasets are in the sentence level, we manually annotate semantic roles for 3000 chit-chat dialogues (27198 sentences) to boost the research in this direction. Experiments show that while traditional SRL systems (even with the help of coreference resolution or rewriting) perform poorly for analyzing dialogues, modeling dialogue histories and participants greatly helps the performance, indicating that adapting SRL to conversations is very promising for universal dialogue understanding. Our initial study by applying CSRL to two mainstream conversational tasks, dialogue response generation and dialogue context rewriting, also confirms the usefulness of CSRL.

We study distributed optimization in the presence of Byzantine adversaries, where both data and computation are distributed among$m$worker machines,$t$of which may be corrupt. The compromised nodes may collaboratively and arbitrarily deviate from their pre-specified programs, and a designated (master) node iteratively computes the model/parameter vector forgeneralized linear models. In this work, we primarily focus on two iterative algorithms:Proximal Gradient Descent(PGD) andCoordinate Descent(CD). Gradient descent (GD) is a special case of these algorithms. PGD is typically used in the data-parallel setting, where data is partitioned across different samples, whereas, CD is used in the model-parallelism setting, where data is partitioned across the parameter space. At the core of our solutions to both these algorithms is a method for Byzantine-resilient matrix-vector (MV) multiplication; and for that, we propose a method based on data encoding and error correction over real numbers to combat adversarial attacks. We can tolerate up to$t\leq \lfloor \frac {m-1}{2}\rfloor $corrupt worker nodes, which is information-theoretically optimal. We give deterministic guarantees, and our method does not assume any probability distribution on the data. We develop asparseencoding scheme which enables computationally efficient data encoding and decoding. We demonstrate a trade-off between the corruption threshold and the resource requirements (storage, computational, and communication complexity). As an example, for$t\leq \frac {m}{3}$, our scheme incurs only aconstantoverhead on these resources, over that required by the plain distributed PGD/CD algorithms which provide no adversarial protection. To the best of our knowledge, ours is the first paper that connects MV multiplication with CD and designs a specific encoding matrix for MV multiplication whose structure we can leverage to make CD secure against adversarial attacks. Our encoding scheme extendsefficientlyto(i)the data streaming model, in which data samples come in an online fashion and are encoded as they arrive, and(ii)makingstochastic gradient descent(SGD) Byzantine-resilient. In the end, we give experimental results to show the efficacy of our proposed schemes.

For multi-turn dialogue rewriting, the capacity of effectively modeling the linguistic knowledge in dialog context and getting rid of the noises is essential to improve its performance.Existing attentive models attend to all words without prior focus, which results in inaccurate concentration on some dispensable words.In this paper, we propose to use semantic role labeling (SRL), which highlights the core semantic information of who did what to whom, to provide additional guidance for the rewriter model.Experiments show that this information significantly improves a RoBERTa-based model that already outperforms previous stateof-the-art systems.

With the explosive development of big data, it is necessary to sort the data according to their importance or priorities. The sources with different importance levels can be modeled by the multilevel diversity coding systems (MDCS). Another trend in future communication networks, say 5G wireless networks and Internet of Things, is that users may obtain their data from all available sources, even from devices belonging to other users. Then, the privacy of data becomes a crucial issue. In a recent work by Li et al., the secure asymmetric MDCS (S-AMDCS) with wiretap channels was investigated, where the wiretapped messages do not leak any information about the sources (i.e. perfect secrecy). It was shown that superposition (source-separate coding) is not optimal for the general S-AMDCS and the exact full secure rate region was proved for a class of S-AMDCS. In addition, a bound on the key size of the secure rate region was provided as well. As a further step on the SAMDCS problem, this paper mainly focuses on the key size characterization. Specifically, the constraints on the key size of superposition secure rate region are proved and a counterexample is found to show that the bound on the key size of the exact secure rate region provided by Li et al. is not tight. In contrast, tight necessary and sufficient constraints on the secrecy key size of the counterexample, which is the four-encoder S-AMDCS, are proved.

In this paper we are interested in what we term the federated private bandits framework, that combines differential privacy with multi-agent bandit learning. We explore how differential privacy based Upper Confidence Bound (UCB) methods can be applied to multi-agent environments, and in particular to federated learning environments both in ‘master-worker’ and ‘fully decentralized’ settings. We provide theoretical analysis on the privacy and regret performance of the proposed methods and explore the tradeoffs between these two.

This work is motivated by the need of collecting fresh data from power-constrained sensors in the industrial Internet of Things (IIoT) network. A recently proposed metric, the Age of Information (AoI) is adopted to measure data freshness from the perspective of the central controller in the IIoT network. We wonder what is the minimum average AoI the network can achieve and how to design scheduling algorithms to approach it. To answer these questions when the channel states of the network are time-varying and scheduling decisions are restricted to both bandwidth and power consumption constraint, we first decouple the multi-sensor scheduling problem into a single-sensor constrained Markov decision process (CMDP) by relaxing the hard bandwidth constraint. Next we exploit the threshold structure of the optimal policy for the decoupled single sensor CMDP and obtain the optimum solution through linear programming (LP). Finally, an asymptotically optimal truncated policy that can satisfy the hard bandwidth constraint is built upon the optimal solution to each of the decoupled single-sensor. Our investigation shows that to obtain a small average AoI over the network: (1) The scheduler exploits good channels to schedule sensors supported by limited power; (2) Sensors equipped with enough transmission power are updated in a timely manner such that the bandwidth constraint can be satisfied.

In the traditional index coding problem, a server employs coding to send messages to a set of clients within the same broadcast domain. Each client already has some messages as side information and requests a particular unknown message from the server. All clients learn the coding matrix so that they can decode and retrieve their requested data. Our starting observation comes from the work by Karmoose et al., which shows that learning the coding matrix can pose privacy concerns: it may enable a client to infer information about the requests and side information of other clients. In this paper, we mitigate this privacy concern by allowing each client to have limited access to the coding matrix. In particular, we design coding matrices so that each client needs only to learn some of (and not all) the rows to decode her requested message. We start by showing that this approach can indeed help mitigate that privacy concern. We do so by considering two different privacy metrics. The first one shows the attained privacy benefits based on a geometric interpretation of the problem. Differently, the second metric, referred to as maximal information leakage, provides upper bounds on: (i) the guessing power of the adversaries (i.e., curious clients) when our proposed approach is employed, and (ii) the effect of decreasing the number of accessible rows on the attained privacy. Then, we propose the use of k-limited-access schemes: given an index coding scheme that employs T transmissions, we create a k-limited-access scheme with Tk≥ T transmissions, and with the property that each client needs at most k transmissions to decode her message. We derive upper and lower bounds on Tkfor all values of k, and develop deterministic designs for these schemes, which are universal, i.e., independent of the coding matrix. We show that our schemes are order-optimal for some parameter regimes, and we propose heuristics that complement the universal schemes for the remaining regimes.

A promising research area that has recently emerged, is on how to use index coding to improve the communication efficiency in distributed computing systems, especially for data shuffling in iterative computations. In this paper, we posit that pliable index coding can offer a more efficient framework for data shuffling, as it can better leverage the many possible shuffling choices to reduce the number of transmissions. We theoretically analyze pliable index coding under data shuffling constraints, and design a hierarchical data-shuffling scheme that uses pliable coding as a component. We find benefits up to O(ns/m) over index coding, where ns/m is the average number of workers caching a message, and m, n, and s are the numbers of messages, workers, and cache size, respectively.

Content caching at the Internet edge using a network of wireless edge caching stations (ECSs) is recently considered as a key solution to alleviating the backhaul traffic burden and improving the quality of experience in 5G networks. This paper studies wireless edge caching systems with the following features: first, content files can be partitioned into many coded packets, which then can be cached in multiple ECSs for collaborative content delivery; second, the service provider (SP) deploys time-to-live cache at ECSs and each cached content file has an occupancy time that needs to be guaranteed; third, the content-to-be-cached arrives at the caching system following a stochastic process as users request new content over time. Unlike existing works that determine which content to cache, this paper focuses on how to distribute the coded packets of content-to-be-cached among the network of ECSs in order to reduce the content downloading time. A novel content placement strategy, called stochastic collaborative content placement is proposed based on Lyapunov techniques. The proposed algorithm makes content placement decisions using only currently available information without foreseeing future content arrivals, takes advantage of the spatial content popularity variation with coded caching, and achieves the provable close-to-optimal long-term caching performance. Simulations are carried out on a real-world YouTube video request trace and the results demonstrate a tremendous caching performance improvement against a variety of benchmark schemes.

Mobile Edge Computing (MEC) is delivering a rich portfolio of computation services to enable ultra-low latency and location-awareness for emerging mobile applications. However, the vulnerability of this new paradigm to potential security and privacy issues prevents mobile users from fully embracing its advantage. While various defensive strategies have been proposed to secure the connection between the end devices and edge servers, an equally important issue, the server-side risk is still under-investigated for most edge computing systems. To handle these server-side risks, a Risk-aware Computation Offloading (RCO) policy is proposed to distribute computation tasks safely among geographically distributed edge sites under server-side attacks. RCO takes into account the strategic behaviors of the potential attackers in the edge system and finds an appropriate balance between risk management and service delay reduction. The Bayesian Stackelberg game is employed to formulate the RCO problem, which describes an appropriate relation between the edge system (as a defender) and the attacker. In particular, the Bayesian Stackelberg game captures the uncertainty of attacker’s behavior and enables RCO to work even when the edge system does not know precisely the attacker that it is playing against. To facilitate the derivation of Stackelberg equilibria, two pruning rules, Heuristic Pruning (HP) and Branch-and-Bound (BaB), are proposed. HP prunes by analyzing the user demand distribution and attacker types, and BaB prunes by obtaining the tight upper/lower bound of edge system utility with the assist of disjunctive programming and Bender’s cut.

Recent years have witnessed deep neural networks (DNNs) become the de facto tool in many applications such as image classification and speech recognition. But significant unmet needs remain in performing DNN inference tasks on mobile devices. Although edge computing enables complex DNN inference tasks to be performed in close proximity to the mobile device, performance optimization requires a carefully designed synergy between the edge and the mobile device. Moreover, the confidentiality of uploaded data to the possibly untrusted edge server is of great concern. In this paper, we investigate the impact of DNN partitioning on the inference latency performance and the privacy risks in edge computing. Based on the obtained insights, we design an offloading strategy that adaptively partitions the DNN in varying network environments to make the optimal tradeoff between performance and privacy for battery-powered mobile devices. This strategy is designed under the learning-aided Lyapunov optimization framework and has a provable performance guarantee. Finally, we build a small- scale testbed to demonstrate the efficacy of the proposed offloading scheme.

Collaborative computing among peer mobile devices via device-to-device (D2D) links, a.k.a. D2D offloading, is a promising technology to enhance mobile computing performance and reduce core wireless network traffic. However, D2D offloading also creates new security risks as malware can relatively easily compromise mobile devices participating in D2D offloading and propagate across the entire network. In this paper, we build a new epidemic model to understand the malware propagation process in the D2D offloading-enabled network where mobile devices are strategically deciding their participation level. The system operator only indirectly controls their participation level via offering participation rewards. Based on this model, we further model the strategic interaction between the defender (i.e. the system operator) and the attacker (i.e. malware) as a zero-sum differential game. The existence of a saddle-point equilibrium is proved, and the optimal dynamic defender and attacker strategies are derived based on the Pontryagin's maximum principle. Numerical results validate the proposed model and show that the dynamic optimal strategies significantly improve the system utility compared with baseline strategies.

We consider distributed gradient computation, where both data and computation are distributed among m worker machines, t of which can be Byzantine adversaries, and a designated (master) node computes the model/parameter vector for generalized linear models, iteratively, using proximal gradient descent (PGD), of which gradient descent (GD) is a special case. The Byzantine adversaries can (collaboratively) deviate arbitrarily from their gradient computation. To solve this, we propose a method based on data encoding and (real) error correction to combat the adversarial behavior. We can tolerate up to t ≤ [m-1/2] corrupt worker nodes, which is information-theoretically optimal. Our method does not assume any probability distribution on the data. We develop a sparse encoding scheme which enables computationally efficient data encoding. We demonstrate a trade-off between the number of adversaries tolerated and the resource requirement (storage and computational complexity). As an example, our scheme incurs a constant overhead (storage and computational complexity) over that required by the distributed PGD algorithm, without adversaries, for t ≤ m/3 . Our encoding works as efficiently in the streaming data etting as it does in the

We consider recommendation systems that need to operate under wireless bandwidth constraints, which is measured as the number of broadcast transmissions. We demonstrate a (tight for some instances) tradeoff between regret and bandwidth for wireless recommendations formulated in a contextual multiarmed bandit framework.

It was recently observed in [1], that in index coding, learning the coding matrix used by the server can pose privacy concerns: curious clients can extract information about the requests and side information of other clients. One approach to mitigate such concerns is the use of k-limited-access schemes [1], that restrict each client to learn only part of the index coding matrix, and in particular, at most k rows. These schemes transform a linear index coding matrix of rank T to an alternate one, such that each client needs to learn at most k of the coding matrix rows to decode its requested message. This paper analyzes k-limited-access schemes. First, a worst-case scenario, where the total number of clients n is 2T-1 is studied. For this case, a novel construction of the coding matrix is provided and shown to be order-optimal in the number of transmissions. Then, the case of a general n is considered and two different schemes are designed and analytically and numerically assessed in their performance. It is shown that these schemes perform better than the one designed for the case n=2T-1.

Trade-offs between distributed computation and communication are recently attracting significant interest; however, these works assume that all nodes that share the distributed computation task are within the same broadcast domain, and each can losslessly broadcast to every other node that takes part in the computation task. In this work, we dispose of this assumption, and consider the case where each node can broadcast to a subset of the nodes that take part in the computation task. We model the network via an Erdos-Renyi random graph model where a pair of nodes can communicate with each other with a probability p. We propose both uncoded and coded transmission schemes and give an achievable communication-computation tradeoff for large computational loads.

Caching at the network edge devices such as wireless caching stations (WCS) is a key technology in the 5G network. The spatial-temporal diversity of content popularity requires different content to be cached in different WCSs and periodically updated to adapt to temporal changes. In this paper, we study how the popularity drifting speed affects the number of required broadcast transmissions by the MBS and then design coded transmission schemes by leveraging the broadcast advantage under the index coding framework. The key idea is that files already cached in WCSs, which although may be currently unpopular, can serve as side information to facilitate coded broadcast transmission for cache updating. Our algorithm extends existing index coding-based schemes from a single-request scenario to a multiple-request scenario via a “dynamic coloring” approach. Simulation results indicate that a significant bandwidth saving can be achieved by adopting our scheme.

We consider wireless recommender systems that need to learn the user preferences (explore) and use them to accordingly decide what are the most profitable recommendations to make (exploit), under bandwidth constraints. We propose a graph-based scheme that leverages user side information and coding to efficiently exploit and explore over wireless, and evaluate its performance.

In pliable index coding, we consider a server withm messages and n clients, where each client has as side information a subset of the messages. We seek to minimize the number of broadcast transmissions, so that each client can recover any one unknown message she does not already have. Previous work has shown that the pliable index coding problem is NP-hard and requires at most O(log2(n)) broadcast transmissions, which indicates exponential savings over the conventional index coding that requires in the worst case O(n) transmissions. In this paper, building on a decoding criterion that we propose, we first design a deterministic polynomial-time algorithm that can realize the exponential benefits, by achieving, in the worst case, a performance upper bounded by O(log2(n)) broadcast transmissions. We extend our algorithm to the t-requests case, where each client requires t unknown messages that she does not have, and show that our algorithm requires at most O(t log(n) + log2(n)) broadcast transmissions. We construct lower bound instances that require at least Ω(log(n)) transmissions for linear pliable index coding and at least Ω(t + log(n)) transmissions for the t-requests case, indicating that both our upper and lower bounds are polynomials of log(n) and differ within a factor of O(log(n)). We provide a probabilistic analysis over random instances and show that the required number of transmissions is almost surely Θ(log(n)), as compared with the Θ(n/ log(n)) for index coding. In addition, we show that these upper and lower bounds also hold for vector pliable index coding in the worst case instances and the random graph instances, implying that vector coding does not provide benefits in terms of these bounds. Our numerical experiments show that our algorithm outperforms existing algorithms for pliable index coding by up to 50% less transmissions.

Using a broadcast channel to transmit clients' data requests may impose privacy risks. In this paper, we tackle such privacy concerns in the index coding framework. We show how a curious client can infer some information about the requests and side information of other clients by learning the encoding matrix used by the server. We propose an information-theoretic metric to measure the level of privacy and show how encoding matrices can be designed to achieve specific privacy guarantees. We then consider a special scenario for which we design a transmission scheme and derive the achieved levels of privacy in closed-form. We also derive upper bounds and we compare them to the levels of privacy achieved by our scheme, highlighting that an inherent trade-off exists between protecting privacy of the request and of the side information of the clients.

This paper asks how much we can gain in terms of bandwidth and user satisfaction, if recommendation systems became bandwidth aware and took into account not only the user preferences, but also the fact that they may need to serve these users under bandwidth constraints, as is the case over wireless networks. We formulate this as a new problem in the context of index coding: we relax the index coding requirements to capture scenarios where each client has preferences associated with messages. The client is satisfied to receive any message she does not already have, with a satisfaction proportional to her preference for that message. We consistently find, over a number of scenarios we sample, that although the optimization problems are in general NP-hard, significant bandwidth savings are possible even when restricted to polynomial time algorithms.

A promising area that has recently emerged, is on how to use index coding to improve the communication efficiency in distributed computing systems, especially for data shuffling in iterative computations. In this paper, we posit that pliable index coding can offer a more efficient framework for data shuffling, as it can better leverage the many possible shuffling choices to reduce the number of transmissions. We theoretically analyze pliable index coding under data shuffling constraints, and design an hierarchical data-shuffling scheme that uses pliable index coding as a component. We find transmission benefits up to O(ns/m) over index coding, where ns/m is the average number of workers caching a message, and m, n, and s are the numbers of messages, workers, and cache size, respectively.

Index coding employs coding across clients within the same broadcast domain. This typically assumes that all clients learn the coding matrix so that they can decode and retrieve their requested data. However, learning the coding matrix can pose privacy concerns: it may enable clients to infer information about the requests and side information of other clients [1]. In this paper, we formalize the intuition that the achieved privacy can increase by decreasing the number of rows of the coding matrix that a client learns. Based on this, we propose the use of k-limited-access schemes: given an index coding scheme that employs T transmissions, we create a k-limited-access scheme with Tk≤ T transmissions, and with the property that each client learns at most k rows of the coding matrix to decode its message. We derive upper and lower bounds on Tkfor all values of k, and develop deterministic designs for these schemes for which Tkhas an order-optimal exponent for some regimes.

In wireless distributed computing, networked nodes perform intermediate computations over data placed in their memory and exchange these intermediate values to calculate function values. In this paper we consider an asymmetric setting where each node has access to a random subset of the data, i.e., we cannot control the data placement. The paper makes a simple point: we can realize significant benefits if we are allowed to be “flexible”, and decide which node computes which function, in our system. We make this argument in the case where each function depends on only two of the data messages, as is the case in similarity searches. We establish a percolation in the behaviour of the system, where, depending on the amount of observed data, by being flexible, we may need no communication at all.

Pliable index coding considers a server with m messages and n clients where each client has as side information a subset of the messages. We seek to minimize the number of transmissions the server should make, so that each client receives (any) one message she does not already have. Previous work has shown that the server can achieve this using at most O(log2(n)) transmissions and needs at least Ω(log(n)) transmissions in the worst case, but finding a code of optimal length is NP-hard. In this paper, we design a polynomial-time algorithm that uses less than O(log2(n)) transmissions, i.e., almost worst-case optimal. We also establish a connection between the pliable index coding problem and the minrank problem over a family of mixed matrices.

Clinicians need to routinely make management decisions about patients who are at risk for a disease such as breast cancer. This paper presents a novel clinical decision support tool that is capable of helping physicians make diagnostic decisions. We apply this support system to improve the specificity of breast cancer screening and diagnosis. The system utilizes clinical context (e.g., demographics, medical history) to minimize the false positive rates while avoiding false negatives. An online contextual learning algorithm is used to update the diagnostic strategy presented to the physicians over time. We analytically evaluate the diagnostic performance loss of the proposed algorithm, in which the true patient distribution is not known and needs to be learned, as compared with the optimal strategy where all information is assumed known, and prove that the false positive rate of the proposed learning algorithm asymptotically converges to the optimum. In addition, our algorithm also has the important merit that it can provide individualized confidence estimates about the accuracy of the diagnosis recommendation. Moreover, the relevancy of contextual features is assessed, enabling the approach to identify specific contextual features that provide the most value of information in reducing diagnostic errors. Experiments were conducted using patient data collected at a large academic medical center. Our proposed approach outperforms the current clinical practice by 36% in terms of false positive rate given a 2% false negative rate.

In this paper, we propose a novel large-scale, context-aware recommender system that provides accurate recommendations, scalability to a large number of diverse users and items, differential services, and does not suffer from “cold start” problems. Our proposed recommendation system relies on a novel algorithm which learns online the item preferences of users based on their click behavior, and constructs online item-cluster trees. The recommendations are then made by choosing an item-cluster level and then selecting an item within that cluster as a recommendation for the user. This approach is able to significantly improve the learning speed when the number of users and items is large, while still providing high recommendation accuracy. Each time a user arrives at the website, the system makes a recommendation based on the estimations of item payoffs by exploiting past context arrivals in a neighborhood of the current user's context. It exploits the similarity of contexts to learn how to make better recommendations even when the number and diversity of users and items is large. This also addresses the cold start problem by using the information gained from similar users and items to make recommendations for new users and items. We theoretically prove that the proposed algorithm for item recommendations converges to the optimal item recommendations in the long-run. We also bound the probability of making a suboptimal item recommendation for each user arriving to the system while the system is learning. Experimental results show that our approach outperforms the state-of-the-art algorithms by over 20 percent in terms of click through rates.

Enabling accurate and low-cost classification of a range of motion activities is of significant importance for wireless health through body worn inertial sensors and smartphones, due to the need by healthcare and fitness professonals to monitor exercises for quality and compliance. This paper proposes a novel contextual multi-armed bandits approach for large-scale activity classification. The proposed method is able to address the unique challenges arising from scaling, lack of training data and adaptation by melding context augmentation and continuous online learning into traditional activity classification. We rigorously characterize the performance of the proposed learning algorithm and prove that the learning regret (i.e. reward loss) is sublinear in time, thereby ensuring fast convergence to the optimal reward as well as providing short-term performance guarantees. Our experiments show that the proposed algorithm outperforms existing algorithms in terms of both providing higher classification accuracy as well as lower energy consumption.

A big challenge for the design and implementation of large-scale online services is determining what items to recommend to their users. For instance, Netflix makes movie recommendations; Amazon makes product recommendations; and Yahoo! makes webpage recommendations. In these systems, items are recommended based on the characteristics and circumstances of the users, which are provided to the recommender as contexts (e.g., search history, time, and location). The task of building an efficient recommender system is challenging due to the fact that both the item space and the context space are very large. Existing works either focus on a large item space without contexts, large context space with small number of items, or they jointly consider the space of items and contexts together to solve the online recommendation problem. In contrast, we develop an algorithm that does exploration and exploitation in the context space and the item space separately, and develop an algorithm that combines clustering of the items with information aggregation in the context space. Basically, given a user's context, our algorithm aggregates its past history over a ball centered on the user's context, whose radius decreases at a rate that allows sufficiently accurate estimates of the payoffs such that the recommended payoffs converge to the true (unknown) payoffs. Theoretical results show that our algorithm can achieve a sublinear learning regret in time, namely the payoff difference of the oracle optimal benchmark, where the preferences of users on certain items in certain context are known, and our algorithm, where the information is incomplete. Numerical results show that our algorithm significantly outperforms (over 48%) the existing algorithms in terms of regret.

Demand side management (DSM) is a key solution for reducing the peak-time power consumption in smart grids. The consumers choose their power consumption patterns according to different prices charged at different times of the day. Importantly, consumers incur discomfort costs from altering their power consumption patterns. Existing works propose stationary strategies for consumers that myopically minimize their short-term billing and discomfort costs. In contrast, we model the interaction emerging among self-interested consumers as a repeated energy scheduling game which foresightedly minimizes their long-term total costs. We then propose a novel methodology for determining optimal nonstationary DSM strategies in which consumers can choose different daily power consumption patterns depending on their preferences and routines, as well as on their past history of actions. We prove that the existing stationary strategies are suboptimal in terms of long-term total billing and discomfort costs and that the proposed strategies are optimal and incentive-compatible (strategy-proof). Simulations confirm that, given the same peak-to-average ratio, the proposed strategy can reduce the total cost (billing and discomfort costs) by up to 50% compared to existing DSM strategies.

Demand-side management (DSM) is a key solution for reducing the peak-time power consumption in smart grids. To provide incentives for consumers to shift their consumption to off-peak times, the utility company charges consumers the differential pricing for using power at different times of the day. Consumers take into account these differential prices when deciding when and how much power to consume daily. Importantly, while consumers enjoy lower billing costs when shifting their power usage to off-peak times, they also incur discomfort costs due to the altering of their power consumption patterns. Existing works propose stationary strategies for the myopic consumers to minimize their short-term billing and discomfort costs. In contrast, we model the interaction emerging among self-interested and foresighted consumers as a repeated energy scheduling game and prove that the stationary strategies are suboptimal in terms of long-term total billing and discomfort costs. Subsequently, we propose a novel framework for determining optimal nonstationary DSM strategies, in which consumers can choose different daily power consumption patterns depending on their preferences, routines, and needs. As a direct consequence of the nonstationary DSM policy, different subsets of consumers are allowed to use power in peak times at a low price. The subset of consumers that are selected daily to have their joint discomfort and billing costs minimized is determined based on the consumers power consumption preferences as well as on the past history of which consumers have shifted their usage previously. Importantly, we show that the proposed strategies are incentive compatible. Simulations confirm that, given the same peak-to-average ratio, the proposed strategy can reduce the total cost (billing and discomfort costs) by up to 50% compared to existing DSM strategies.