We propose a privacy-preserving uplink over-the-air computation (AirComp) method, termed FLORAS, for single-input single-output (SISO) wireless federated learning (FL) systems. From the perspective of communication designs, FLORAS eliminates the requirement of channel state information at the transmitters (CSIT) by leveraging the properties of orthogonal sequences. From the privacy perspective, we prove that FLORAS offers bothitem-levelandclient-leveldifferential privacy (DP) guarantees. Moreover, by properly adjusting the system parameters, FLORAS can flexibly achieve different DP levels at no additional cost. A new FL convergence bound is derived which, combined with the privacy guarantees, allows for a smooth tradeoff between the achieved convergence rate and differential privacy levels. Experimental results demonstrate the advantages of FLORAS compared with the baseline AirComp method, and validate that the analytical results can guide the design of privacy-preserving FL with different tradeoff requirements on the model convergence and privacy levels.

Federated Learning (FL) is widely used in mobile computing as a communication-efficient distributed machine learning (ML) paradigm; however, it faces challenges such as model convergence to local optima or slow convergence due to the heterogeneity of client data. To mitigate data heterogeneity, the Nesterov Accelerated Gradient (NAG) method demonstrates its effectiveness by predictively updating the gradient to improve system performance. However, the performance of NAG depends heavily on the choice of decay coefficients; larger coefficients have greater acceleration but may lead to an unstable convergence process due to their unreasonable prediction of the descent gradient. To solve the above problems, this paper proposes the first radical heavy ball (RHB) method that combines momentum and NAG. In Stochastic Gradient Descent (SGD), momentum stabilizes the gradient descent process by integrating the historical gradients to update the parameters, and the RHB strategy decouples a single decay coefficient into an NAG component and a momentum component. The RHB introduces a gradient recall after each gradient acceleration by the NAG to strengthen the NAG's perception of the historical gradients, thus stabilizing the gradient descent process. By weighing the historical gradients and the predicted gradient, RHB effectively mitigates the instability of NAG convergence and demonstrates better performance. As a result, the algorithm further mitigates the impact of customer data heterogeneity in FL and can effectively deliver global update information to participants without additional communication costs. We conduct comprehensive experiments in a binary function, single node, and federated model environment to analyze the convergence properties in non-convex loss functions. RHB exhibits better performance and less computational overhead than many existing algorithms.

Federated learning (FL) is one of the popular distributed machine learning (ML) solutions but incurs significant communication and computation costs at edge devices. Federated split learning (FSL) can train sub-models in parallel and reduce the computational burden of edge devices by splitting the model architecture. However, it still requires a high communication overhead due to transmitting the smashed data and gradients between clients and the server in every global round. Furthermore, the server must maintain separate partial models for every client, leading to a significant storage requirement. To address these challenges, this paper proposes a novel communication and storage efficient federated split learning method, termed CSE-FSL, which utilizes an auxiliary network to locally update the weights of the clients while keeping asinglemodel at the server, hence avoiding frequent transmissions of gradients from the server and greatly reducing the storage requirement of the server. Additionally, a new model update method of transmitting the smashed data in selected epochs can reduce the amount of smashed data sent from the clients. We provide a theoretical analysis of CSE-FSL, rigorously guaranteeing its convergence under non-convex loss functions. The extensive experimental results further indicate that CSE-FSL achieves a significant communication reduction over existing FSL solutions using real-world FL tasks.

Reinforcement Learning from Human Feedback (RLHF) has emerged as a pivotal technique for aligning artificial intelligence systems with human values, achieving remarkable success in fine-tuning large language models. However, existing RLHF frameworks often assume that human preferences are relatively homogeneous and can be captured by a single, unified reward model. This assumption overlooks the inherent diversity and heterogeneity across individuals, limiting the adaptability of RLHF to personalized scenarios and risking misalignments that can diminish user satisfaction and trust in AI systems. In this paper, we address these challenges by introducing Low-Rank Adaptation (LoRA) into the personalized RLHF framework. We apply LoRA in the parameter space of the aggregation of all personalized reward functions, thereby enabling efficient learning of personalized reward models from potentially limited local datasets. Our approach exploits potential shared structures among the local ground-truth reward models while allowing for individual adaptation, without relying on restrictive assumptions about shared representations as in prior works. We further establish sample complexity guarantees for our method. Theoretical analysis demonstrates the effectiveness of the proposed approach in capturing both shared and individual-specific structures within heterogeneous human preferences, addressing the dual challenge of personalization requirements and practical data constraints. Experimental results on real-world datasets corroborate the efficiency of our algorithm in the personalized RLHF setting.

Pure exploration is one of the fundamental problems in multi-armed bandits (MAB). However, existing works mostly focus on specific pure exploration tasks, without a holistic view of the general pure exploration problem. This work fills this gap by introducing a versatile framework to study pure exploration, with a focus on identifying the pairwise relationships between targeted arm pairs. Moreover, unlike existing works that only optimize the stopping time (i.e., sample complexity), this work considers that arms are associated with potentially different costs and targets at optimizing the cumulative cost that occurred during learning. Under the general framework of pairwise pure exploration with arm-specific costs, a performance lower bound is derived. Then, a novel algorithm, termed CAET (Cost-Aware Pairwise Exploration Task), is proposed. CAET builds on the track-and-stop principle with a novel design to handle the arm-specific costs, which can potentially be zero and thus represent a very challenging case. Theoretical analyses prove that the performance of CAET approaches the lower bound asymptotically. Special cases are further discussed, including an extension to regret minimization, which is another major focus of MAB. The effectiveness and efficiency of CAET are also verified through experimental results under various settings.

Retrieval-augmented generation (RAG) enhances large language models (LLMs) by integrating external knowledge sources to address their limitations in accessing up-to-date or specialized information.A natural strategy to increase the likelihood of retrieving relevant information is to expand the number of retrieved documents.However, involving more documents could introduce significant noise, as many documents may be irrelevant or misleading, thereby reducing the overall accuracy of the generated responses.To overcome the challenge associated with handling a larger number of documents, we propose WinnowRAG, a novel RAG framework designed to systematically filter out noisy documents while preserving valuable content -a process we refer to as winnowing.WinnowRAG operates in two stages: In Stage I, we perform queryaware clustering to group similar documents and form distinct topic clusters.Each cluster is assigned to an LLM agent for generating a unique answer.In Stage II, we perform winnowing, wherein a critic LLM evaluates the outputs of multiple agents and iteratively separates useful documents from noisy ones.To retain useful documents when discarding agents, we propose two strategic merging techniques to ensure that only relevant knowledge is used for generating the final response.Crucially, WinnowRAG is model-agnostic and does not require any model fine-tuning, making it easily adaptable to various tasks.Extensive experiments on various realistic datasets demonstrate the effectiveness of WinnowRAG over state-ofthe-art baselines.

Transformers have shown potential in solving wireless communication problems, particularly via in-context learning (ICL), where models adapt to new tasks through prompts without requiring model updates. However, prior ICL-based Transformer models rely on deep architectures with many layers to achieve satisfactory performance, resulting in substantial storage and computational costs. In this work, we propose CHain Of thOught Symbol dEtection (CHOOSE), a CoT-enhanced shallow Transformer framework for wireless symbol detection. By introducing autoregressive latent reasoning steps within the hidden space, CHOOSE significantly improves the reasoning capacity of shallow models (1-2 layers) without increasing model depth. This design enables lightweight Transformers to achieve detection performance comparable to much deeper models, making them well-suited for deployment on resource-constrained mobile devices. Experimental results demonstrate that our approach outperforms conventional shallow Transformers and achieves performance comparable to that of deep Transformers, while maintaining storage and computational efficiency. This represents a promising direction for implementing Transformer-based algorithms in wireless receivers with limited computational resources.

Pre-trained Transformers, through in-context learning (ICL), have demonstrated exceptional capabilities to adapt to new tasks using example prompts without model update. Transformer-based wireless receivers, where prompts consist of the pilot data in the form of transmitted and received signal pairs, have shown high estimation accuracy when pilot data are abundant. However, pilot information is often costly and limited in practice. In this work, we propose the DEcision Feedback INContExt Detection (DEFINED) solution as a new wireless receiver design, which bypasses channel estimation and directly performs symbol detection using the (sometimes extremely) limited pilot data. The key innovation in DEFINED is the proposed decision feedback mechanism in ICL, where we sequentially incorporate the detected symbols into the prompts to improve the detections for subsequent symbols. Extensive experiments across a broad range of wireless communication settings demonstrate that DEFINED achieves significant performance improvements, in some cases only needing a single pilot pair.

Large Language Models (LLMs) rely on the contextual information embedded in examples/demonstrations to perform in-context learning (ICL). To mitigate the risk of LLMs potentially leaking private information contained in examples in the prompt, we introduce a novel data-adaptive differentially private algorithm called **AdaDPSyn** to generate synthetic examples from the private dataset and then use these synthetic examples to perform ICL. The objective of AdaDPSyn is to adaptively adjust the noise level in the data synthesis mechanism according to the inherent statistical properties of the data, thereby preserving high ICL accuracy while maintaining formal differential privacy guarantees. A key innovation in AdaDPSyn is the *Precision-Focused Iterative Radius Reduction* technique, which dynamically refines the aggregation radius - the scope of data grouping for noise addition - based on patterns observed in data clustering, thereby minimizing the amount of additive noise. We conduct extensive experiments on standard benchmarks and compare AdaDPSyn with DP few-shot generation algorithm (Tang et al., 2023). The experiments demonstrate that AdaDPSyn not only outperforms DP few-shot generation, but also maintains high accuracy levels close to those of non-private baselines, providing an effective solution for ICL with privacy protection.

An intriguing property of the Transformer is its ability to perform in-context learning (ICL), where the Transformer can solve different inference tasks without parameter updating based on the contextual information provided by the corresponding input-output demonstration pairs. It has been theoretically proved that ICL is enabled by the capability of Transformers to perform gradient-descent algorithms (Von Oswald et al., 2023a; Bai et al., 2024). This work takes a step further and shows that Transformers can perform learning-to-optimize (L2O) algorithms. Specifically, for the ICL sparse recovery (formulated as LASSO) tasks, we show that a K-layer Transformer can perform an L2O algorithm with a provable convergence rate linear in K. This provides a new perspective explaining the superior ICL capability of Transformers, even with only a few layers, which cannot be achieved by the standard gradient-descent algorithms. Moreover, unlike the conventional L2O algorithms that require the measurement matrix involved in training to match that in testing, the trained Transformer is able to solve sparse recovery problems generated with different measurement matrices. Besides, Transformers as an L2O algorithm can leverage structural information embedded in the training tasks to accelerate its convergence during ICL, and generalize across different lengths of demonstration pairs, where conventional L2O algorithms typically struggle or fail. Such theoretical findings are supported by our experimental results.

In-Context Learning (ICL) empowers Large Language Models (LLMs) to tackle diverse tasks by incorporating multiple input-output examples, known as demonstrations, into the input of LLMs. More recently, advancements in the expanded context windows of LLMs have led to many-shot ICL, which uses hundreds of demonstrations and outperforms few-shot ICL, which relies on fewer examples. However, this approach is often hindered by the high cost of obtaining large amounts of labeled data. To address this challenge, we propose Many-Shot Adaptive Pseudo-LabEling, namely MAPLE, a novel influence-based many-shot ICL framework that utilizes pseudo-labeled samples to compensate for the lack of label information. We first identify a subset of impactful unlabeled samples and perform pseudo-labeling on them by querying LLMs. These pseudo-labeled samples are then adaptively selected and tailored to each test query as input to improve the performance of many-shot ICL, without significant labeling costs. Extensive experiments on real-world datasets demonstrate the effectiveness of our framework, showcasing its ability to enhance LLM adaptability and performance with limited labeled data. Our code is provided at https://github.com/Chen-1031/MAPLE_ICL.

Although transformers have demonstrated impressive capabilities for in-context learning (ICL) in practice, theoretical understanding of the underlying mechanism that allows transformers to perform ICL is still in its infancy. This work aims to theoretically study the training dynamics of transformers for in-context classification tasks. We demonstrate that, for in-context classification of Gaussian mixtures under certain assumptions, a single-layer transformer trained via gradient descent converges to a globally optimal model at a linear rate. We further quantify the impact of the training and testing prompt lengths on the ICL inference error of the trained transformer. We show that when the lengths of training and testing prompts are sufficiently large, the prediction of the trained transformer approaches the ground truth distribution of the labels. Experimental results corroborate the theoretical findings.

Graph learning models have demonstrated great prowess in learning expressive representations from large-scale graph data in a wide variety of real-world scenarios. As a prevalent strategy for training powerful graph learning models, the ''pre-training, adaptation'' scheme first pre-trains graph learning models on unlabeled graph data in a self-supervised manner and then adapts them to specific downstream tasks. During the adaptation phase, graph prompting emerges as a promising approach that learns trainable prompts while keeping the pre-trained graph learning models unchanged. In this paper, we present a systematic review of recent advancements in graph prompting. First, we introduce representative graph pre-training methods that serve as the foundation step of graph prompting. Next, we review mainstream techniques in graph prompting and elaborate on how they design learnable prompts for graph prompting. Furthermore, we summarize the real-world applications of graph prompting from different domains. Finally, we discuss several open challenges in existing studies with promising future directions in this field.

Time series data is now pervasive across domains such as healthcare, finance, entertainment, and transportation, driven by advances in sensing technologies that enable continuous data collection. The resulting increase in data volume and complexity poses significant challenges to traditional analysis methods, calling for the development of advanced, interdisciplinary approaches to temporal data mining. This workshop aims to: (1) identify key challenges in learning from time series data, including irregular sampling, spatiotemporal dependencies, and uncertainty quantification; (2) explore recent advances in algorithmic, statistical, theoretical, and systems-based solutions-ranging from classical methods to emerging techniques involving large language models (LLMs); and (3) foster collaboration by highlighting open problems and novel research directions in time series analysis. Bridging theory and practice, the workshop provides a platform for researchers and practitioners from academia, industry, and government to exchange ideas, discuss technical challenges, and showcase practical applications. Contributions from related areas such as AI, machine learning, data science, and statistics are strongly encouraged.

We study bilevel optimization problems where the lower-level problems are strongly convex and have coupled linear constraints. To overcome the potential non-smoothness of the hyper-objective and the computational challenges associated with the Hessian matrix, we utilize penalty and augmented Lagrangian methods to reformulate the original problem as a single-level one. Especially, we establish a strong theoretical connection between the reformulated function and the original hyper-objective by characterizing the closeness of their values and derivatives. Based on this reformulation, we propose a single-loop, first-order algorithm for linearly constrained bilevel optimization (SFLCB). We provide rigorous analyses of its non-asymptotic convergence rates, showing an improvement over prior double-loop algorithms -- form $O(\epsilon^{-3}\log(\epsilon^{-1}))$ to $O(\epsilon^{-3})$. The experiments corroborate our theoretical findings and demonstrate the practical efficiency of the proposed SFLCB algorithm. Simulation code is provided at https://github.com/ShenGroup/SFLCB.

Reinforcement Learning from Human Feedback (RLHF) has emerged as a key technique for post‑training large language models. Despite its empirical success, the theoretical understanding of RLHF is still limited, as learning the KL-regularized target with only preference feedback poses additional challenges compared with canonical RL. Existing works mostly study the reward-based Bradley-Terry (BT) preference model, and extend classical designs utilizing optimism or pessimism. This work, instead, considers the general preference model (whose practical relevance has been observed recently) and obtains performance guarantees with major, order-wise improvements over existing ones. Surprisingly, these results are derived from algorithms that directly use empirical estimates (i.e., greedy sampling), as opposed to constructing optimistic or pessimistic estimates in previous works. This insight has a deep root in the unique structural property of the optimal policy class under the KL-regularized target, and we further specialize it to the BT model, highlighting the surprising sufficiency of greedy sampling in RLHF.

This paper investigates a hybrid learning framework for reinforcement learning (RL) in which the agent can leverage both an offline dataset and online interactions to learn the optimal policy. We present a unified algorithm and analysis and show that augmenting confidence-based online RL algorithms with the offline dataset outperforms any pure online or offline algorithm alone and achieves state-of-the-art results under two learning metrics, i.e., sub-optimality gap and online learning regret. Specifically, we show that our algorithm achieves a sub-optimality gap $\tilde{O}( \sqrt{1/(N_0/ \mathtt{C}(\pi^\star| \rho)+N_1} ) )$, where $\mathtt{C}(\pi^\star|\rho)$ is a new concentrability coefficient, $N_0$ and $N_1$ are the numbers of offline and online samples, respectively. For regret minimization, we show that it achieves a constant $\tilde{O}( \sqrt{N_1/(N_0/\mathtt{C}(\pi^{-}|\rho)+N_1)} )$ speed-up compared to pure online learning, where $\mathtt{C}(\pi^-|\rho)$ is the concentrability coefficient over all sub-optimal policies. Our results also reveal an interesting separation on the desired coverage properties of the offline dataset for sub-optimality gap minimization and regret minimization. We further validate our theoretical findings in several experiments in special RL models such as linear contextual bandits and Markov decision processes (MDPs).

Federated Learning (FL) is a distributed machine learning framework that efficiently reduces communication and preserves privacy. Existing FL algorithms typically rely on the assumption of direct communication between the server and clients for model data exchange. However, this assumption does not apply in many real-world scenarios where appropriate communication infrastructure is lacking, such as in remote smart sensing. To overcome this challenge, we propose a new framework, FedEx (Federated Learning via Model Express Delivery). FedEx employs mobile transporters, such as Unmanned Aerial Vehicles (UAVs), to establish indirect communication channels between the server and clients. We have developed two algorithms under this framework: FedEx-Sync and FedEx-Async, which differ based on whether the transporters operate on a synchronized or asynchronized schedule. Although indirect communication introduces variable delays in global model dissemination and local model collection, we demonstrate the convergence of both FedEx versions. Additionally, we explore the energy consumption of transporters, integrating it with the convergence bounds and proposing a bi-level optimization algorithm for efficient client assignment and route planning. Our experiments, conducted on two public datasets in a simulated environment, further demonstrate the efficacy of FedEx.

In recent years, federated minimax optimization has attracted growing interest due to its extensive applications in various machine learning tasks. While Smoothed Alternative Gradient Descent Ascent (Smoothed-AGDA) has proved successful in centralized nonconvex minimax optimization, how and whether smoothing techniques could be helpful in a federated setting remains unexplored. In this paper, we propose a new algorithm termed Federated Stochastic Smoothed Gradient Descent Ascent (FESS-GDA), which utilizes the smoothing technique for federated minimax optimization. We prove that FESS-GDA can be uniformly applied to solve several classes of federated minimax problems and prove new or better analytical convergence results for these settings. We showcase the practical efficiency of FESS-GDA in practical federated learning tasks of training generative adversarial networks (GANs) and fair classification.

Personalized Federated Learning (PFL) relies on collective data knowledge to build customized models. However, non-IID data between clients poses significant challenges, as collaborating with clients who have diverse data distributions can harm local model performance, especially with limited training data. To address this issue, we propose FedACS, a new PFL algorithm with an Attention-based Client Selection mechanism. FedACS integrates an attention mechanism to enhance collaboration among clients with similar data distributions and mitigate the data scarcity issue. It prioritizes and allocates resources based on data similarity. We further establish the theoretical convergence behavior of FedACS. Experiments on CIFAR10 and FMNIST validate FedACS’s superiority, showcasing its potential to advance personalized federated learning. By tackling non-IID data challenges and data scarcity, FedACS offers promising advances in personalized federated learning.

Wireless federated learning (FL) relies on efficient uplink communications to aggregate model updates across distributed edge devices. Over-the-air computation (a.k.a. AirComp) has emerged as a promising approach for addressing the scala-bility challenge of FL over wireless links with limited communication resources. Unlike conventional methods, AirComp allows multiple edge devices to transmit uplink signals simultaneously, enabling the parameter server to directly decode the average global model. However, existing AirComp solutions are intrinsically analog, while modern wireless systems predominantly adopt digital modulations. Consequently, careful constellation designs are necessary to accurately decode the sum model updates without ambiguity. In this paper, we propose an end-to-end communication system supporting AirComp with digital modulation, aiming to overcome the challenges associated with accurate decoding of the sum signal with constellation designs. We leverage autoencoder network structures and explore the joint optimization of transmitter and receiver components. Our approach fills an important gap in the context of accurately decoding the sum signal in digital modulation-based AirComp, which can advance the deployment of FL in contemporary wireless systems.

Federated representation learning (FRL) is a popular personalized federated learning (FL) framework where clients work together to train a common representation while retaining their personalized heads. Existing studies, however, largely focus on the over-parameterized regime. In this paper, we make the initial efforts to investigate FRL in the under-parameterized regime, where the FL model is insufficient to express the variations in all ground-truth models. We propose a novel FRL algorithm FLUTE, and theoretically characterize its sample complexity and convergence rate for linear models in the under-parameterized regime. To the best of our knowledge, this is the first FRL algorithm with provable performance guarantees in this regime. FLUTE features a data-independent random initialization and a carefully designed objective function that aids the distillation of subspace spanned by the global optimal representation from the misaligned local representations. On the technical side, we bridge low-rank matrix approximation techniques with the FL analysis, which may be of broad interest. We also extend FLUTE beyond linear representations. Experimental results demonstrate that FLUTE outperforms state-of-the-art FRL solutions in both synthetic and real-world tasks.

As privacy concerns escalate in the realm of machine learning, data owners now have the option to utilize machine unlearning to remove their data from machine learning models, following recent legislation. To enhance transparency in machine unlearning and avoid potential dishonesty by model providers, various verification strategies have been proposed. These strategies enable data owners to ascertain whether their target data has been effectively unlearned from the model. However, our understanding of the safety issues of machine unlearning verification remains nascent. In this paper, we explore the novel research question of whether model providers can circumvent verification strategies while retaining the information of data supposedly unlearned. Our investigation leads to a pessimistic answer: the verification of machine unlearning is fragile. Specifically, we categorize the current verification strategies regarding potential dishonesty among model providers into two types. Subsequently, we introduce two novel adversarial unlearning processes capable of circumventing both types. We validate the efficacy of our methods through theoretical analysis and empirical experiments using real-world datasets. This study highlights the vulnerabilities and limitations in machine unlearning verification, paving the way for further research into the safety of machine unlearning.

Time series data has become ubiquitous across various fields such as healthcare, finance, entertainment, and transportation, driven by advancements in sensing technologies that enable continuous monitoring and recording. This growth in data size and complexity presents new challenges for traditional analysis techniques, necessitating the development of advanced, interdisciplinary temporal mining algorithms. The goals of this workshop are to: (1) highlight significant challenges in learning and mining from time series data, such as irregular sampling, spatiotemporal structures, and uncertainty quantification; (2) discuss recent developments in algorithmic, theoretical, statistical, and systems-based approaches for addressing these challenges, including both classical methods and large language models (LLMs); and (3) synergize research efforts by exploring both new and open problems in time series analysis and mining. This workshop will focus on both the theoretical and practical aspects of time series data analysis, providing a platform for researchers and practitioners from academia, government, and industry to discuss potential research directions, critical technical issues, and present solutions for practical applications. Contributions from related fields such as AI, machine learning, data science, and statistics are also included.

There is huge value in making software development more productive with AI. An important component of this vision is the capability to translate natural language to a programming language ("NL2Code") and thus to significantly accelerate the speed at which code is written.

The remarkable instruction-following capability of large language models (LLMs) has sparked a growing interest in automatically finding good prompts, i.e., prompt optimization. Most existing works follow the scheme of selecting from a pre-generated pool of candidate prompts. However, these designs mainly focus on the generation strategy, while limited attention has been paid to the selection method. Especially, the cost incurred during the selection (e.g., accessing LLM and evaluating the responses) is rarely explicitly considered. To overcome this limitation, this work provides a principled framework, TRIPLE, to efficiently perform prompt selection under an explicit budget constraint. TRIPLE is built on a novel connection established between prompt optimization and fixed-budget best arm identification (BAI-FB) in multi-armed bandits (MAB); thus, it is capable of leveraging the rich toolbox from BAI-FB systematically and also incorporating unique characteristics of prompt optimization. Extensive experiments on multiple well-adopted tasks using various LLMs demonstrate the remarkable performance improvement of TRIPLE over baselines while satisfying the limited budget constraints. As an extension, variants of TRIPLE are proposed to efficiently select examples for few-shot prompts, also achieving superior empirical performance.

The in-context learning (ICL) capability of pre-trained models based on the transformer architecture has received growing interest in recent years. While theoretical understanding has been obtained for ICL in reinforcement learning (RL), the previous results are largely confined to the single-agent setting. This work proposes to further explore the in-context learning capabilities of pre-trained transformer models in competitive multi-agent games, i.e., in-context game-playing (ICGP). Focusing on the classical two-player zero-sum games, theoretical guarantees are provided to demonstrate that pre-trained transformers can provably learn to approximate Nash equilibrium in an in-context manner for both decentralized and centralized learning settings. As a key part of the proof, constructional results are established to demonstrate that the transformer architecture is sufficiently rich to realize celebrated multi-agent game-playing algorithms, in particular, decentralized V-learning and centralized VI-ULCB.

In-Context Learning (ICL) empowers Large Language Models (LLMs) to tackle various tasks by providing input-output examples as additional inputs, referred to as demonstrations. Nevertheless, the performance of ICL could be easily impacted by the quality of selected demonstrations. Existing efforts generally learn a retriever model to score each demonstration for selecting suitable demonstrations, however, the effect is suboptimal due to the large search space and the noise from unhelpful demonstrations. In this study, we introduce MoD, which partitions the demonstration pool into groups, each governed by an expert to reduce search space. We further design an expert-wise training strategy to alleviate the impact of unhelpful demonstrations when optimizing the retriever model. During inference, experts collaboratively retrieve demonstrations for the input query to enhance the ICL performance. We validate MoD via experiments across a range of NLP datasets and tasks, demonstrating its state-of-the-art performance and shedding new light on the future design of retrieval methods for ICL.

Model quantization has drawn much attention for federated learning (FL) over the Internet of Things (IoT) since it is an effective way to address the critical bottleneck of communication efficiency. State-of-the-art studies have generally assumed homogeneous model quantization, where all clients’ updates are quantized using the same number of bits and aggregated with the same weight at the server. However, in practical IoT scenarios, various IoT devices may apply heterogeneous quantization bits due to their different hardware capabilities, which leads to heterogeneous model quantization accuracy. This article addresses the problem of heterogeneous quantization bit allocation and aggregation for FL. The clients may be allocated with a different number of quantization bits, subject to a total quantization bit constraint. The server may employ different aggregation weights to each IoT device. In particular, we propose FedHBAA—FL with Heterogeneous Bit Allocation and Aggregation, a novel joint quantization bit allocation and server aggregation algorithm. In FedHBAA, we first develop an optimal server aggregation scheme under any given bit allocation among clients. By minimizing the drift term in the convergence rate analysis, a closed-form aggregation weight solution as a function of the allocated bits is obtained for both the strongly convex and nonconvex loss functions. Then, by solving the derived optimal aggregation weights, the optimal bit allocation scheme is obtained. Numerical experiments demonstrate that FedHBAA outperforms the traditional FedAVG algorithm with equal quantization bits.

In this paper, the performance optimization of federated learning (FL), when deployed over a realistic wireless multiple-input multiple-output (MIMO) communication system with digital modulation and over-the-air computation (AirComp) is studied. In particular, a MIMO system is considered in which edge devices transmit their local FL models (trained using their locally collected data) to a parameter server (PS) using beamforming to maximize the number of devices scheduled for transmission. The PS, acting as a central controller, generates a global FL model using the received local FL models and broadcasts it back to all devices. Due to the limited bandwidth in a wireless network, AirComp is adopted to enable efficient wireless data aggregation. However, fading of wireless channels can produce aggregate distortions in an AirComp-based FL scheme. To tackle this challenge, we propose a modified federated averaging (FedAvg) algorithm that combines digital modulation with AirComp to mitigate wireless fading while ensuring the communication efficiency. This is achieved by a joint transmit and receive beamforming design, which is formulated as an optimization problem to dynamically adjust the beamforming matrices based on current FL model parameters so as to minimize the transmitting error and ensure the FL performance. To achieve this goal, we first analytically characterize how the beamforming matrices affect the performance of the FedAvg in different iterations. Based on this relationship, an artificial neural network (ANN) is used to estimate the local FL models of all devices and adjust the beamforming matrices at the PS for future model transmission. The algorithmic advantages and improved performance of the proposed methodologies are demonstrated through extensive numerical experiments.

We propose a novel communication design, termed random orthogonalization, for federated learning (FL) in a massive multiple-input and multiple-output (MIMO) wireless system. The key novelty of random orthogonalization comes from the tight coupling of FL and two unique characteristics of massive MIMO – channel hardening and favorable propagation. As a result, random orthogonalization can achieve natural over-the-air model aggregation without requiring transmitter side channel state information (CSI) for the uplink phase of FL, while significantly reducing the channel estimation overhead at the receiver. We extend this principle to the downlink communication phase and develop a simple but highly effective model broadcast method for FL. We also relax the massive MIMO assumption by proposing an enhanced random orthogonalization design for both uplink and downlink FL communications, that does not rely on channel hardening or favorable propagation. Theoretical analyses with respect to both communication and machine learning performance are carried out. In particular, an explicit relationship among the convergence rate, the number of clients, and the number of antennas is established. Experimental results validate the effectiveness and efficiency of random orthogonalization for FL in massive MIMO.

The recent development of reinforcement learning (RL) has boosted the adoption of online RL for wireless radio resource management (RRM). However, online RL algorithms require direct interactions with the environment, which may be undesirable given the potential performance loss due to the unavoidable exploration in RL. In this work, we first explore the use ofofflineRL algorithms in solving the RRM problem. We evaluate several state-of-the-art offline RL algorithms for a practical RRM problem that aims at maximizing a linear combination of total rates and 5-percentile rates via user scheduling. Our findings indicate that the performance of offline RL for the RRM problem is heavily contingent upon the behavior policy deployed for data collection. We propose an innovative offline RL approach utilizing heterogeneous datasets from various behavior policies. This method demonstrates that a strategic mixture of datasets enables near-optimal RL policy generation, even with suboptimal behavior policies. Additionally, we introduce two enhancements: an ensemble-based policy to augment dataset mixture training efficiency, and a novel offline-to-online strategy for seamless adaptation to new environments. Our data mixture approach achieves over 95% efficiency of an online RL agent in the absence of expert data. The ensemble algorithm notably reduces training duration by half compared to the data mixture method. Furthermore, our model, when applied with offline-to-online fine-tuning, surpasses existing benchmarks by approximately 5% in our user scheduling problem.

In this paper, we consider the optimization of federated learning (FL) over a realistic wireless multiple-input multiple-output (MIMO) communication system with digital modulation and over-the-air computation (AirComp). In such a system, MIMO devices transmit their locally trained FL models to a parameter server (PS) using beamforming to maximize the number of devices scheduled for transmission. AirComp enables efficient wireless model aggregation by the PS in bandwidth-limited settings. However, wireless channel fading can produce distortions in AirComp-based FL. To tackle this challenge, we develop a novel aggregation scheme that combines digital modulation with AirComp to mitigate wireless fading while ensuring communication efficiency. We formulate this as a joint transmit-receive beamforming design optimization problem which dynamically adjusts the beamforming matrices to minimize the FL training loss with transmission errors. To solve this problem based on limited information at the PS, we employ an artificial neural network (ANN) to estimate the local FL models of all devices. Then, we derive a closed-form optimal design of the transmit and receive beamforming matrices based on predicted FL models. Numerical evaluations validate the advantages of the proposed methodology in terms of model training performance compared with baselines.

Federated learning (FL) is a popular distributed machine learning (ML) paradigm, but is often limited by significant communication costs and edge device computation capabilities. Federated Split Learning (FSL) preserves the parallel model training principle of FL, with a reduced device computation requirement thanks to splitting the ML model between the server and clients. However, FSL still incurs very high communication overhead due to transmitting the smashed data and gradients between the clients and the server in each global round. Furthermore, the server has to maintain separate models for every client, resulting in a significant computation and storage requirement that grows linearly with the number of clients. This paper aims at solving these two issues by proposing a communication and storage efficient federated split learning (CSE-FSL) strategy, which utilizes an auxiliary network to locally update the client models while keeping only a single model at the server, hence avoiding the communication of gradients from the server and greatly reducing the server resource requirement. Communication cost is further reduced by only sending the smashed data in selected epochs from the clients. We provide a rigorous theoretical analysis of CSE-FSL that guarantees its convergence for non-convex loss functions. Extensive experimental results demonstrate that CSE-FSL has a significant communication reduction over existing FSL techniques, while achieving state-of-the-art convergence and model accuracy, using several real-world FL tasks.

We propose a novel private-preserving uplink over-the-air computation (AirComp) method, termed FLORAS, for wireless federated learning (FL) systems. From the communication design perspective, FLORAS eliminates the requirement of channel state information at the transmitters (CSIT) by leveraging the properties of orthogonal sequences. From the privacy perspective, we prove that FLORAS can offer pure differential privacy (DP) guarantee, and explicitly characterize the achievable$\epsilon$-DP level as a function of the FLORAS parameter configuration. A novel FL convergence bound is derived which, combined with the pure DP guarantee, allows for a smooth tradeoff between convergence rate and DP guarantee levels. Experiments based on real-world datasets not only corroborate the theoretical findings but also empirically demonstrate the communication and privacy advantages of FLORAS over state-of-the-art AirComp methods.

This paper investigates conservative exploration in reinforcement learning where the performance of the learning agent is guaranteed to be above a certain threshold throughout the learning process. It focuses on the tabular episodic Markov Decision Process (MDP) setting that has finite states and actions. With the knowledge of an existing safe baseline policy, an algorithms termed as StepMix is proposed to balance the exploitation and exploration while ensuring that the conservative constraint is never violated in each episode with high probability. StepMix features a unique design of a mixture policy that adaptively and smoothly interpolates between the baseline policy and the optimistic policy. Theoretical analysis shows that StepMix achieves near-optimal regret order as in the constraint-free setting, indicating that obeying the stringent episode-wise conservative constraint does not compromise the learning performance. Besides, a randomization based EpsMix algorithm is also proposed and shown the achieve the same performance as StepMix. The algorithm design and theoretical analysis are further extended to the setting where the baseline policy is not given a priori but must be learned from an offline dataset, and it is proved that similar conservative guarantee and regret can be achieved if the offline dataset is sufficiently large. Experiment results corroborate the theoretical analysis and demonstrate the effectiveness of the proposed conservative exploration strategies.

Existing theoretical studies on offline reinforcement learning (RL) mostly consider a dataset sampled directly from the target task. In practice, however, data often come from several heterogeneous but related sources. Motivated by this gap, this work aims at rigorously understanding offline RL with multiple datasets that are collected from randomly perturbed versions of the target task instead of from itself. An information-theoretic lower bound is derived, which reveals a necessary requirement on the number of involved sources in addition to that on the number of data samples. Then, a novel HetPEVI algorithm is proposed, which simultaneously considers the sample uncertainties from a finite number of data samples per data source and the source uncertainties due to a finite number of available data sources. Theoretical analyses demonstrate that HetPEVI can solve the target task as long as the data sources collectively provide a good data coverage. Moreover, HetPEVI is demonstrated to be optimal up to a polynomial factor of the horizon length. Finally, the study is extended to offline Markov games and offline robust RL, which demonstrates the generality of the proposed designs and theoretical analyses.

In this work, we investigate a general federated multitask learning (FMTL) problem where each task may be performed at multiple clients, and each client may perform multiple tasks. Although the tasks share some common representation (i.e., feature-map) that can help to learn, the distribution of the features in the feature space may vary across different tasks at different clients, which poses a significant challenge to FMTL. While non-independent and identically distributed (non-IID) local datasets at different clients are often considered detrimental to model convergence in federated learning (FL), such statistical heterogeneity in feature space may be beneficial to the generalization performance. In this work, we establish the impact of statistical feature heterogeneity on generalization, through the lens of a multi-task linear regression model. In order to leverage the feature distribution heterogeneity, we propose a novel augmented dataset based approach, and prove that under certain conditions, FMTL on heterogeneous datasets can outperform the homogeneous counterpart in terms of the generalization performance. The theoretical analysis further leads to a simple client weighting method based on optimizing the excess risk upper bound. Experimental results demonstrate that the generalization performance can be improved on a real-world dataset with the proposed method.

Most existing studies on linear bandits focus on a one-dimensional characterization of the overall system. While being representative, this formulation may fail to model applications with high-dimensional but favorable structures, such as the low-rank tensor representation for recommender systems. To address this limitation, this work studies a general tensor bandits model, where actions and system parameters are represented by tensors as opposed to vectors, and we particularly focus on the case that the unknown system tensor is low-rank. A novel bandit algorithm, coined TOFU (Tensor Optimism in the Face of Uncertainty), is developed. TOFU first leverages flexible tensor regression techniques to estimate low-dimensional subspaces associated with the system tensor. These estimates are then utilized to convert the original problem to a new one with norm constraints on its system parameters. Lastly, a norm-constrained bandit subroutine is adopted by TOFU, which utilizes these constraints to avoid exploring the entire high-dimensional parameter space. Theoretical analyses show that TOFU improves the best-known regret upper bound by a multiplicative factor that grows exponentially in the system order. A novel performance lower bound is also established, which further corroborates the efficiency of TOFU.

Most existing federated multi-armed bandits (FMAB) designs are based on the presumption that clients will implement the new design to collaborate with the server. In reality, however, it may not be possible to modify the client protocols. Motivated by this limitation, this work focuses on clients who always maximize their individual cumulative rewards, and introduces a novel idea of reward teaching, where the server guides the clients towards global optimality through implicit local reward adjustments. Under this framework, the server faces two tightly coupled tasks of bandit learning and target teaching, whose combination is non-trivial and challenging. A novel algorithm, called Teaching-After-Learning (TAL), is proposed, which encourages and discourages clients’ explorations separately. General performance analyses of TAL on regret and cost are first established when the clients’ strategies satisfy certain requirements. To particularize the results, clients with UCB or ε-greedy strategies are then considered, where novel technical approaches are developed to analyze their warm-start behaviors. The obtained guarantees concretely demonstrate that when facing these client strategies, TAL achieves logarithmic regrets while only incurring logarithmic adjustment costs, which is order-optimal w.r.t. a natural lower bound.

Time series data has become pervasive across domains such as finance, transportation, retail, entertainment, and healthcare. This shift towards continuous monitoring and recording, fueled by advancements in sensing technologies, necessitates the development of new tools and solutions. Despite extensive study, the importance of time series analysis continues to increase. However, modern time series data present challenges to existing techniques, including irregular sampling and spatiotemporal structures. Time series mining research is both challenging and rewarding as it connects diverse disciplines and requires interdisciplinary solutions. The goals of this workshop are to (1) highlight the significant challenges that underpin learning and mining from time series data (e.g., irregular sampling, spatiotemporal structure, uncertainty quantification), (2) discuss recent algorithmic, theoretical, statistical, or systems-based developments for tackling these problems, and (3) to synergize the research activities and discuss both new and open problems in time series analysis and mining. In summary, our workshop will focus on both the theoretical and practical aspects of time series data analysis and will provide a platform for researchers and practitioners from academia and industry to discuss potential research directions and critical technical issues and present solutions to tackle related issues in practical applications. We will invite researchers and practitioners from the related areas of AI, machine learning, data science, statistics, and many others to contribute to this workshop.

We study a federated linear bandits model, where $M$ clients communicate with a central server to solve a linear contextual bandits problem with finite adversarial action sets that may be different across clients. To address the unique challenges of **adversarial finite** action sets, we propose the FedSupLinUCB algorithm, which extends the principles of SupLinUCB and OFUL algorithms in linear contextual bandits. We prove that FedSupLinUCB achieves a total regret of $\tilde{O}(\sqrt{d T})$, where $T$ is the total number of arm pulls from all clients, and $d$ is the ambient dimension of the linear model. This matches the minimax lower bound and thus is order-optimal (up to polylog terms). We study both asynchronous and synchronous cases and show that the communication cost can be controlled as $O(d M^2 \log(d)\log(T))$ and $O(\sqrt{d^3 M^3} \log(d))$, respectively. The FedSupLinUCB design is further extended to two scenarios: (1) variance-adaptive, where a total regret of $\tilde{O} (\sqrt{d \sum \nolimits_{t=1}^{T} \sigma_t^2})$ can be achieved with $\sigma_t^2$ being the noise variance of round $t$; and (2) adversarial corruption, where a total regret of $\tilde{O}(\sqrt{dT} + d C_p)$ can be achieved with $C_p$ being the total corruption budget. Experiment results corroborate the theoretical analysis and demonstrate the effectiveness of \alg on both synthetic and real-world datasets.

Modern distributed machine learning (ML) paradigms, such as federated learning (FL), utilize data distributed at different clients to train a global model. In such paradigm, local datasets never leave the clients for better privacy protection, and the parameter server (PS) only performs simple aggregation. In practice, however, there is often some amount of data available at the PS, and its computation capability is strong enough to carry out more demanding tasks than simple model aggregation. The focus of this paper is to analyze the model convergence of a new hybrid learning architecture, which leverages the PS dataset and its computation power for collaborative model training with clients. Different from FL where stochastic gradient descent (SGD) is always computed in parallel across clients, the new architecture has both parallel SGD at clients and sequential SGD at PS. We analyze the convergence rate upper bounds of thisaggregate-then-advancedesign for both strongly convex and non-convex loss functions. We show that when the local SGD has an$\mathcal {O}(1/t)$stepsize, the server SGD needs to scale its stepsize to no slower than$\mathcal {O}(1/t^{2})$in order to strictly outperform local SGD with strongly convex loss functions. The theoretical findings are corroborated by numerical experiments, where advantages in terms of both accuracy and convergence speed over clients-only (local SGD and FED AVG) and server-only training are demonstrated.

Catering to the proliferation of Internet of Things devices and distributed machine learning at the edge, we propose an energy harvesting federated learning (EHFL) framework in this paper. The introduction of EH implies that a client’s availability to participate in any FL round cannot be guaranteed, which complicates the theoretical analysis. We derive novel convergence bounds that capture the impact of time-varying device availabilities due to the random EH characteristics of the participating clients, for both parallel and local stochastic gradient descent (SGD) with non-convex loss functions. The results suggest that having a uniform client scheduling that maximizes the minimum number of clients throughout the FL process is desirable, which is further corroborated by the numerical experiments using a real-world FL task and a state-of-the-art EH scheduler.

We propose a novel uplink communication method, coined random orthogonalization, for federated learning (FL) in a massive multiple-input and multiple-output (MIMO) wireless system. The key novelty of random orthogonalization comes from the tight coupling of FL model aggregation and two unique characteristics of massive MIMO – channel hardening and favorable propagation. As a result, random orthogonalization can achieve natural over-the-air model aggregation without requiring transmitter side channel state information, while significantly reducing the channel estimation overhead at the receiver. Theoretical analyses with respect to both communication and machine learning performances are carried out. In particular, an explicit relationship among the convergence rate, the number of clients and the number of antennas is established. Experimental results validate the effectiveness and efficiency of random orthogonalization for FL in massive MIMO.

Existing studies on provably efficient algorithms for Markov games (MGs) almost exclusively build on the “optimism in the face of uncertainty” (OFU) principle. This work focuses on a distinct approach of posterior sampling, which is celebrated in many bandits and reinforcement learning settings but remains under-explored for MGs. Specifically, for episodic two-player zero-sum MGs, a novel posterior sampling algorithm is developed with general function approximation. Theoretical analysis demonstrates that the posterior sampling algorithm admits a $\sqrt{T}$-regret bound for problems with a low multi-agent decoupling coefficient, which is a new complexity measure for MGs, where $T$ denotes the number of episodes. When specializing to linear MGs, the obtained regret bound matches the state-of-the-art results. To the best of our knowledge, this is the first provably efficient posterior sampling algorithm for MGs with frequentist regret guarantees, which extends the toolbox for MGs and promotes the broad applicability of posterior sampling.

Learning to optimize (L2O) has recently emerged as a promising approach to solving optimization problems by exploiting the strong prediction power of neural networks and offering lower runtime complexity than conventional solvers. While L2O has been applied to various problems, a crucial yet challenging class of problems — robust combinatorial optimization in the form of minimax optimization — have largely remained under-explored. In addition to the exponentially large decision space, a key challenge for robust combinatorial optimization lies in the inner optimization problem, which is typically non-convex and entangled with outer optimization. In this paper, we study robust combinatorial optimization and propose a novel learning-based optimizer, called LRCO (Learning for Robust Combinatorial Optimization), which quickly outputs a robust solution in the presence of uncertain context. LRCO leverages a pair of learning-based optimizers — one for the minimizer and the other for the maximizer — that use their respective objective functions as losses and can be trained without the need of labels for training problem instances. To evaluate the performance of LRCO, we perform simulations for the task offloading problem in vehicular edge computing. Our results highlight that LRCO can greatly reduce the worst-case cost and improve robustness, while having a very low runtime complexity.

Motivated by the engineering application of efficient mobility management in ultra-dense wireless networks, we propose a novel cost-aware cascading bandit model with two-level actions. Compared with the standard cascading bandit model with a single-level action, this new model captures the real-world action sequence in mobility management, where the base station not only decides on an ordered neighbor cell list before measurement, but also executes the final handover decision to the target base station. We first analyze the optimal offline policy when the arm statistics are known beforehand. An online learning algorithm coined two-level Cost-aware Cascading UCB (CC-UCB) is then proposed to exploit the structure of the optimal offline policy with estimated arm statistics. Theoretical analysis shows that the cumulative regret under two-level CC-UCB scales logarithmically in time, which coincides with the asymptotic lower bound, thus is order-optimal. Simulation results corroborate the theoretical results and validate the effectiveness of two-level CC-UCB for mobility management.

Deep fading represents the typical error event when communicating over wireless channels. We show that deep fading is particularly detrimental for federated learning (FL) over wireless communications. In particular, the celebrated FEDAVG and several of its variants break down for FL tasks when deep fading exists in the communication phase. The main contribution of this paper is an optimal global model aggregation method at the parameter server, which allocates different weights to different clients based on not only their learning characteristics but also the instantaneous channel state information at the receiver (CSIR). This is accomplished by first deriving an upper bound on the parallel stochastic gradient descent (SGD) convergence over fading channels, and then solving an optimization problem for the server aggregation weights that minimizes this upper bound. The derived optimal aggregation solution is closed-form, and achieves the well-known O(1/t) convergence rate for strongly-convex loss functions under arbitrary fading and decaying learning rates. We validate our approach using several real-world FL tasks.

Time series data are ubiquitous, and is one of the fastest growing and richest types of data. Recent advances in sensing technologies has resulted in a rapid growth in the size and complexity of time series archives. This demands development of new tools and solutions. The goals of this workshop are to: (1) highlight the significant challenges that underpin learning and mining from time series data (e.g. irregular sampling, spatiotemporal structure, uncertainty quantification), (2) discuss recent algorithmic, theoretical, statistical, or systems-based developments for tackling these problems, and (3) exploring new frontiers in time series analysis and their connections with important topics such as knowledge representation, reasoning, control, and business intelligence. In summary, our workshop will focus on both the theoretical and practical aspects of time series data analysis and will provide a platform for researchers and practitioners from both academia and industry to discuss potential research directions, key technical issues, and present solutions to tackle related issues in practical applications. We will invite researchers and practitioners from the related areas of AI, machine learning, data science, statistics, and many others to contribute to this workshop.

This article studies the problem of automated information processing from large volumes of unstructured, heterogeneous, and sometimes untrustworthy data sources. The main contribution is a novel framework called Machine Assisted Record Selection (MARS). Instead of today’s standard practice of relying on human experts to manually decide the order of records for processing, MARS learns the optimal record selection via an online learning algorithm. It further integrates algorithm-based record selection and processing with human-based error resolution to achieve a balanced task allocation between machine and human. Both fixed and adaptive MARS algorithms are proposed, leveraging different statistical knowledge about the existence, quality, and cost associated with the records. Experiments using semi-synthetic data that are generated from real-world patients record processing in the UK national cancer registry are carried out, which demonstrate significant (3 to 4 fold) performance gain over the fixed-order processing. MARS represents one of the few examples demonstrating that machine learning can assist humans with complex jobs by automating complex triaging tasks.

Vehicular ad hoc networks (VANETs) is one of the most promising approaches for the Intelligent Transportation Systems (ITS). With the rapid increase in the amount of traffic data, deep learning based algorithms have been used extensively in VANETs. The recently proposed federated learning is an attractive candidate for collaborative machine learning where instead of transferring a plethora of data to a centralized server, all clients train their respective local models and upload them to the server for model aggregation. Model quantization is an effective approach to address the communication efficiency issue in federated learning, and yet existing studies largely assume homogeneous quantization for all clients. However, in reality, clients are predominantly heterogeneous, where they support different quantization precision levels. In this work, we propose FedDO – Federated Learning with Double Optimization. Minimizing the drift term in the convergence analysis, which is a weighted sum of squared quantization errors (SQE) over all clients, leads to a double optimization at both clients and server sides. In particular, each client adopts a fully distributed, instantaneous (per learning round) and individualized (per client) quantization scheme that minimizes its own squared quantization error, and the server computes the aggregation weights that minimize the weighted sum of squared quantization errors over all clients. We show via numerical experiments that the minimal-SQE quantizer has a better performance than a widely adopted linear quantizer for federated learning. We also demonstrate the performance advantages of FedDO over the vanilla FedAvg with standard equal weights and linear quantization.

Federated multi-armed bandits (FMAB) is a new bandit paradigm that parallels the federated learning (FL) framework in supervised learning. It is inspired by practical applications in cognitive radio and recommender systems, and enjoys features that are analogous to FL. This paper proposes a general framework of FMAB and then studies two specific federated bandit models. We first study the approximate model where the heterogeneous local models are random realizations of the global model from an unknown distribution. This model introduces a new uncertainty of client sampling, as the global model may not be reliably learned even if the finite local models are perfectly known. Furthermore, this uncertainty cannot be quantified a priori without knowledge of the suboptimality gap. We solve the approximate model by proposing Federated Double UCB (Fed2-UCB), which constructs a novel “double UCB” principle accounting for uncertainties from both arm and client sampling. We show that gradually admitting new clients is critical in achieving an O(log(T)) regret while explicitly considering the communication loss. The exact model, where the global bandit model is the exact average of heterogeneous local models, is then studied as a special case. We show that, somewhat surprisingly, the order-optimal regret can be achieved independent of the number of clients with a careful choice of the update periodicity. Experiments using both synthetic and real-world datasets corroborate the theoretical analysis and demonstrate the effectiveness and efficiency of the proposed algorithms.

Phase I clinical trials are designed to test the safety (non-toxicity) of drugs and find the maximum tolerated dose (MTD). This task becomes significantly more challenging when multiple-drug dose-combinations (DC) are involved, due to the inherent conflict between the exponentially increasing DC candidates and the limited patient budget. This paper proposes a novel Bayesian design, SDF-Bayes, for finding the MTD for drug combinations in the presence of safety constraints. Rather than the conventional principle of escalating or de-escalating the current dose of one drug (perhaps alternating between drugs), SDF-Bayes proceeds by cautious optimism: it chooses the next DC that, on the basis of current information, is most likely to be the MTD (optimism), subject to the constraint that it only chooses DCs that have a high probability of being safe (caution). We also propose an extension, SDF-Bayes-AR, that accounts for patient heterogeneity and enables heterogeneous patient recruitment. Extensive experiments based on both synthetic and real-world datasets demonstrate the advantages of SDF-Bayes over state of the art DC trial designs in terms of accuracy and safety.

A general framework of personalized federated multi-armed bandits (PF-MAB) is proposed, which is a new bandit paradigm analogous to the federated learning (FL) framework in supervised learning and enjoys the features of FL with personalization. Under the PF-MAB framework, a mixed bandit learning problem that flexibly balances generalization and personalization is studied. A lower bound analysis for the mixed model is presented. We then propose the Personalized Federated Upper Confidence Bound (PF-UCB) algorithm, where the exploration length is chosen carefully to achieve the desired balance of learning the local model and supplying global information for the mixed learning objective. Theoretical analysis proves that PF-UCB achieves an O(log(T)) regret regardless of the degree of personalization, and has a similar instance dependency as the lower bound. Experiments using both synthetic and real-world datasets corroborate the theoretical analysis and demonstrate the effectiveness of the proposed algorithm.

Large-volume scientific data is one of the prominent driving forces behind next generation networking. In particular, Software Defined Network (SDN) makes leveraging path-based network multicast services practically feasible. In our prior work, we have developed a cross-layer architecture for supporting reliable file-streams multicasting over SDN-enabled Layer-2 network, and implemented the architecture for a meteorology data distribution application in atmospheric science. However, it is challenging to determine an optimal rate for this application with the varying type, volume, and quality of meteorological data. In this paper, we propose a Quality of Service (QoS)-driven rate management pipeline to determine the optimal rate based on the input traffic characteristics and performance constraints. Specifically, the pipeline employs a feedtype classifier using Multi-Layer Perception (MLP) to recognize the type of meteorological data and a delay prediction regressor using stacked Long Short-Term Memory (LSTM) to predict per-file delay for the file-streams. Finally, we determine the optimal rate for the given file-streams using the trained regressor. We implement this pipeline to test the real-world file-stream data collected from a trial deployment, and the results show that our regressor outperforms all baselines by selecting the optimal rate in the presence of varying file set sizes.

Implementation cost and power consumption are two important considerations in large-scale multi-antenna systems where the number of individual radio-frequency (RF) chains may be significantly larger than before. In this work, we propose to deploy a single low-noise amplifier (LNA) on the uplink multiple-input-multiple-output (MIMO) receiver to cover all antennas. This architecture, although favorable from the perspective of cost and power consumption, introduces challenges in the LNA gain control and user transmit power control. We formulate an energy efficiency maximization problem under practical system constraints, and prove that it is a constrained quasiconcave optimization problem. An efficient algorithm, Bisection – Gradient Assisted Interior Point (B-GAIP), is proposed to solve this optimization problem. The optimality and complexity of B-GAIP are analyzed, and further corroborated via numerical simulations. In particular, the performance loss due to using a shared LNA as opposed to separate LNAs in each RF chain, when using B-GAIP to determine the LNA gain and user transmit power, is very small in both centralized and distributed MIMO systems.

Does Federated Learning (FL) work when both uplink and downlink communications have errors? How much communication noise can FL handle and what is its impact to the learning performance? This work is devoted to answering these practically important questions by explicitly incorporating both uplink and downlink noisy channels in the FL pipeline. We present a rigorous convergence analysis of FL over simultaneous uplink and downlink noisy communication channels, and characterize the sufficient conditions for FL to maintain the same convergence rate scaling as the ideal case of no communication error. The analysis reveals that, in order to maintain the $\mathcal{O}\left( {1/T} \right)$ convergence rate of FedAvg with perfect communications, the uplink and downlink signal-to-noise-ratio (SNR) should be controlled such that they scale as $\mathcal{O}\left( {{t^2}} \right)$ where t is the index of communication rounds. This key result leads to a transmit power control policy for analog aggregation, whose performance is shown to be superior over the standard method via extensive numerical experiments using real-world FL tasks.

In this paper, we study the efficient communication design, including both uplink and downlink communications, for wireless federated learning (FL). We answer the question of what and how to communicate between clients and the parameter server and evaluate the impact of the various quantization and transmission options of the updated model on the learning performance. We provide new convergence analysis of the well-known FEDAVG under non-i.i.d. dataset distributions, partial clients participation, and finite-precision quantization in uplink and downlink communications. These analyses reveal that, in order to achieve an $\mathcal{O}(1/T)$ convergence rate with quantization, transmitting the weight requires increasing the quantization level at a logarithmic rate, while transmitting the weight differential can keep a constant quantization level. Comprehensive numerical evaluation on various real-world datasets reveals that the benefit of a FL-tailored uplink and downlink communication design is enormous – a carefully designed 1-bit quantization (3.1% of the floating-point baseline bandwidth) achieves 99.8% of the floating-point baseline accuracy at almost the same convergence rate on MNIST, representing the best known bandwidth-accuracy tradeoff to the best of the authors’ knowledge.

In this work, we study the no-sensing adversarial multi-player multi-armed bandits problem. A new dimension of hardness, called attackability, is introduced, which is orthogonal to the hardness of multiple players. All adversaries can be categorized based on the attackability and we introduce Adversary-Adaptive Collision-Communication (A2C2), a family of algorithms with forced-collision communications among players. Information-theoretic tools of the Z-channel model, error-correction/detection coding, and randomized communication are utilized to address the challenge of implicit communication without collision information in an adversarial environment. Theoretical analysis proves that asymptotic attackability-dependent sublinear regrets can be achieved, which do not have an exponential dependence on the number of players and as a result reveal a fundamental tradeoff between the two dimensions of hardness in this problem.

This paper presents a novel federated linear contextual bandits model, where individual clients face different $K$-armed stochastic bandits coupled through common global parameters. By leveraging the geometric structure of the linear rewards, a collaborative algorithm called Fed-PE is proposed to cope with the heterogeneity across clients without exchanging local feature vectors or raw data. Fed-PE relies on a novel multi-client G-optimal design, and achieves near-optimal regrets for both disjoint and shared parameter cases with logarithmic communication costs. In addition, a new concept called collinearly-dependent policies is introduced, based on which a tight minimax regret lower bound for the disjoint parameter case is derived. Experiments demonstrate the effectiveness of the proposed algorithms on both synthetic and real-world datasets.

Despite the significant interests and many progresses in decentralized multi-player multi-armed bandits (MP-MAB) problems in recent years, the regret gap to the natural centralized lower bound in the heterogeneous MP-MAB setting remains open. In this paper, we propose BEACON -- Batched Exploration with Adaptive COmmunicatioN -- that closes this gap. BEACON accomplishes this goal with novel contributions in implicit communication and efficient exploration. For the former, we propose a novel adaptive differential communication (ADC) design that significantly improves the implicit communication efficiency. For the latter, a carefully crafted batched exploration scheme is developed to enable incorporation of the combinatorial upper confidence bound (CUCB) principle. We then generalize the existing linear-reward MP-MAB problems, where the system reward is always the sum of individually collected rewards, to a new MP-MAB problem where the system reward is a general (nonlinear) function of individual rewards. We extend BEACON to solve this problem and prove a logarithmic regret. BEACON bridges the algorithm design and regret analysis of combinatorial MAB (CMAB) and MP-MAB, two largely disjointed areas in MAB, and the results in this paper suggest that this previously ignored connection is worth further investigation.

Incentivized exploration in multi-armed bandits (MAB) has witnessed increasing interests and many progresses in recent years, where a principal offers bonuses to agents to do explorations on her behalf. However, almost all existing studies are confined to temporary myopic agents. In this work, we break this barrier and study incentivized exploration with multiple and long-term strategic agents, who have more complicated behaviors that often appear in real-world applications. An important observation of this work is that strategic agents' intrinsic needs of learning benefit (instead of harming) the principal's explorations by providing "free pulls". Moreover, it turns out that increasing the population of agents significantly lowers the principal's burden of incentivizing. The key and somewhat surprising insight revealed from our results is that when there are sufficiently many learning agents involved, the exploration process of the principal can be (almost) free. Our main results are built upon three novel components which may be of independent interest: (1) a simple yet provably effective incentive-provision strategy; (2) a carefully crafted best arm identification algorithm for rewards aggregated under unequal confidences; (3) a high-probability finite-time lower bound of UCB algorithms. Experimental results are provided to complement the theoretical analysis.

Communication has been known to be one of the primary bottlenecks of federated learning (FL), and yet existing studies have not addressed the efficient communication design, particularly in wireless FL where both uplink and downlink communications have to be considered. In this paper, we focus on the design and analysis of physical layer quantization and transmission methods for wireless FL. We answer the question of what and how to communicate between clients and the parameter server and evaluate the impact of the various quantization and transmission options of the updated model on the learning performance. We provide new convergence analysis of the well-known FED AVG under non-i.i.d. dataset distributions, partial clients participation, and finite-precision quantization in uplink and downlink communications. These analyses reveal that, in order to achieve anO(1/T) convergence rate with quantization, transmitting the weight requires increasing the quantization level at a logarithmic rate, while transmitting the weight differential can keep a constant quantization level. Comprehensive numerical evaluation on various real-world datasets reveals that the benefit of a FL-tailored uplink and downlink communication design is enormous - a carefully designed quantization and transmission achieves more than 98% of the floating-point baseline accuracy with fewer than 10% of the baseline bandwidth, for majority of the experiments on both i.i.d. and non-i.i.d. datasets. In particular, 1-bit quantization (3.1% of the floating-point baseline bandwidth) achieves 99.8% of the floating-point baseline accuracy at almost the same convergence rate on MNIST, representing the best known bandwidth-accuracy tradeoff to the best of the authors' knowledge.

Mobile Edge Computing (MEC) pushes computing functionalities away from the centralized cloud to the proximity of data sources, thereby reducing service provision latency and saving backhaul network bandwidth. Although computation offloading for MEC systems has been extensively studied in the literature, service placement is an equally, if not more, important design topic of MEC, yet receives much less attention. Service placement refers to configuring the service platform and storing the related libraries/databases at the edge server, e.g., MEC-enabled Base Station (BS), which enables corresponding computation tasks to be executed. Due to the limited computing resource, the edge server can host only a small number of services and hence which services to host has to be judiciously decided to maximize the system performance. In this paper, we investigate collaborative service placement in MEC-enabled dense small cell networks. An efficient decentralized algorithm, called CSP (Collaborative Service Placement), is proposed where a network of small cell BSs optimize service placement decisions collaboratively to address a number of challenges in MEC systems, including service heterogeneity, spatial demand coupling, and decentralized coordination. CSP is developed based on parallel Gibbs sampling by exploiting the graph coloring on the small cell network. The algorithm significantly improves the time efficiency compared to conventional Gibbs sampling, yet guarantees provable convergence and optimality. CSP is further extended to work with selfish BSs, where BSs are allowed to choose “to cooperate” or “not to cooperate.” We employ coalitional game to investigate the strategic behaviors of selfish BSs and design a coalition formation scheme to form stable BS coalitions using merge-and-split rules. Simulations results show that CSP can effectively reduce edge system operational cost for both cooperative and selfish BSs.

Communication is widely known as the primary bottleneck of federated learning, and quantization of local model updates before uploading to the parameter server is an effective solution to reduce the communication overhead. However, prior literature always assumes homogeneous quantization for all clients, while in reality, devices are heterogeneous and support different levels of quantization precision. This heterogeneity of quantization poses a new challenge: fine-quantized model updates are more accurate than coarse-quantized ones, and how to optimally aggregate them at the server is an open problem. In this paper, we propose FedHQ – Federated Learning with Heterogeneous Quantization – that allocates different aggregation weights to different clients by minimizing the convergence rate upper bound as a function of the heterogeneous quantization errors of all clients, for both strongly convex and non-convex loss functions. To further accelerate the convergence, the instantaneous quantization error is computed and piggybacked when each client uploads the local model update, and the server dynamically calculates the weight accordingly for the current aggregation. Numerical experiment results demonstrate the performance advantages of FedHQ over both vanilla FedAvg with standard equal weights and a heuristic aggregation scheme, which assigns weights linearly proportional to the clients’ quantization precision.

Clinical trials in the medical domain are constrained by budgets. The number of patients that can be recruited is therefore limited. When a patient population is heterogeneous, this creates difficulties in learning subgroup specific responses to a particular drug and especially for a variety of dosages. In addition, patient recruitment can be difficult by the fact that clinical trials do not aim to provide a benefit to any given patient in the trial. In this paper, we propose C3T-Budget, a contextual constrained clinical trial algorithm for dose-finding under both budget and safety constraints. The algorithm aims to maximize drug efficacy within the clinical trial while also learning about the drug being tested. C3T-Budget recruits patients with consideration of the remaining budget, the remaining time, and the characteristics of each group, such as the population distribution, estimated expected efficacy, and estimation credibility. In addition, the algorithm aims to avoid unsafe dosages. These characteristics are further illustrated in a simulated clinical trial study, which corroborates the theoretical analysis and demonstrates an efficient budget usage as well as a balanced learning-treatment trade-off.

The decentralized stochastic multi-player multi-armed bandit (MP-MAB) problem, where the collision information is not available to the players, is studied in this paper. Building on the seminal work of Boursier and Perchet (2019), we propose error correction synchronization involving communication (EC-SIC), whose regret is shown to approach that of the centralized stochastic MP-MAB with collision information. By recognizing that the communication phase without collision information corresponds to the Z-channel model in information theory, the proposed EC-SIC algorithm applies optimal error correction coding for the communication of reward statistics. A fixed message length, as opposed to the logarithmically growing one in Boursier and Perchet (2019), also plays a crucial role in controlling the communication loss. Experiments with practical Z-channel codes, such as repetition code, flip code and modified Hamming code, demonstrate the superiority of EC-SIC in both synthetic and real-world datasets.

In this paper, we investigate the impact of context diversity on stochastic linear contextual bandits. As opposed to the previous view that contexts lead to more difficult bandit learning, we show that when the contexts are sufficiently diverse, the learner is able to utilize the information obtained during exploitation to shorten the exploration process, thus achieving reduced regret. We design the LinUCB-d algorithm, and propose a novel approach to analyze its regret performance. The main theoretical result is that under the diverse context assumption, the cumulative expected regret of LinUCB-d is bounded by a constant. As a by-product, our results improve the previous understanding of LinUCB and strengthen its performance guarantee.

Phase I dose-finding trials are increasingly challenging as the relationship between efficacy and toxicity of new compounds (or combination of them) becomes more complex. Despite this, most commonly used methods in practice focus on identifying a Maximum Tolerated Dose (MTD) by learning only from toxicity events. We present a novel adaptive clinical trial methodology, called Safe Efficacy Exploration Dose Allocation (SEEDA), that aims at maximizing the cumulative efficacies while satisfying the toxicity safety constraint with high probability. We evaluate performance objectives that have operational meanings in practical clinical trials, including cumulative efficacy, recommendation/allocation success probabilities, toxicity violation probability, and sample efficiency. An extended SEEDA-Plateau algorithm that is tailored for the increase-then-plateau efficacy behavior of molecularly targeted agents (MTA) is also presented. Through numerical experiments using both synthetic and real-world datasets, we show that SEEDA outperforms state-of-the-art clinical trial designs by finding the optimal dose with higher success rate and fewer patients.

Quantization of local model updates before uploading to the parameter server is a primary solution to reduce the communication overhead in federated learning. However, prior literature always assumes homogeneous quantization for all clients, while in reality devices are heterogeneous and they support different levels of quantization precision. This heterogeneity of quantization poses a new challenge: fine-quantized model updates are more accurate than coarse-quantized ones, and how to optimally aggregate them at the server is an unsolved problem. In this paper, we propose FEDHQ: Federated Learning with Heterogeneous Quantization. In particular, FEDHQ allocates different weights to clients by minimizing the convergence rate upper bound, which is a function of quantization errors of all clients. We derive the convergence rate of FEDHQ under strongly convex loss functions. To further accelerate the convergence, the instantaneous quantization error is computed and piggybacked when each client uploads the local model update, and the server dynamically calculates the weight accordingly for the current round. Numerical experiments demonstrate the performance advantages of FEDHQ+ over conventional FEDAVG with standard equal weights and a heuristic scheme which assigns weights linearly proportional to the clients’ quantization precision.

We analyze the performance of Borda counting algorithm on noisy m-wise ranking data to accurately select the top-k items from a total of n items. This generalizes a previous result of a similar nature reported by Shah et al. on the noisy pairwise comparison data. We show that the associated score separation Δkbetween the k-th item and the (k+1)-th item plays an important role: if Δkis greater than a threshold depending on (n, k) and the scoring system in Borda counting, then the top-k selection is accurate asymptotically almost surely; if Δkis below a threshold, then the top-k selection will not be accurate with at least a constant probability. This separation between the two thresholds depends on m and the scoring systems in the Borda counting procedure.

Subgroup analysis of treatment effects plays an important role in applications from medicine to public policy to recommender systems. It allows physicians (for example) to identify groups of patients for whom a given drug or treatment is likely to be effective and groups of patients for which it is not. Most of the current methods of subgroup analysis begin with a particular algorithm for estimating individualized treatment effects (ITE) and identify subgroups by maximizing the difference across subgroups of the average treatment effect in each subgroup. These approaches have several weaknesses: they rely on a particular algorithm for estimating ITE, they ignore (in)homogeneity within identified subgroups, and they do not produce good confidence estimates. This paper develops a new method for subgroup analysis, R2P, that addresses all these weaknesses. R2P uses an arbitrary, exogenously prescribed algorithm for estimating ITE and quantifies the uncertainty of the ITE estimation, using a construction that is more robust than other methods. Experiments using synthetic and semi-synthetic datasets (based on real data) demonstrate that R2P constructs partitions that are simultaneously more homogeneous within groups and more heterogeneous across groups than the partitions produced by other methods. Moreover, because R2P can employ any ITE estimator, it also produces much narrower confidence intervals with a prescribed coverage guarantee than other methods.

A deep neural network (DNN) based power control method that aims at solving the non-convex optimization problem of maximizing the sum rate of a fading multi-user interference channel is proposed. Towards this end, we first present PCNet, which is a multi-layer fully connected neural network that is specifically designed for the power control problem. A key challenge in training a DNN for the power control problem is the lack of ground truth, i.e., the optimal power allocation is unknown. To address this issue, PCNet leverages the unsupervised learning strategy and directly maximizes the sum rate in the training phase. We then present PCNet+, which enhances the generalization capacity of PCNet by incorporating noise power as an input to the network. Observing that a single PCNet(+) does not universally outperform the existing solutions, we further propose ePCNet(+), a network ensemble with multiple PCNets(+) trained independently. Simulation results show that for the standard symmetric K -user Gaussian interference channel, the proposed methods can outperform state-of-the-art power control solutions under a variety of system configurations. Furthermore, the performance improvement of ePCNet comes with a reduced computational complexity.

This paper investigates learning-based caching in small-cell networks (SCNs) when user preference is unknown. The goal is to optimize the cache placement in each small base station (SBS) for minimizing the system long-term transmission delay. We model this sequential multi-agent decision making problem in a multi-agent multi-armed bandit (MAMAB) perspective. Rather than estimating user preference first and then optimizing the cache strategy, we propose several MAMAB-based algorithms to directly learn the cache strategy online in both stationary and non-stationary environment. In the stationary environment, we first propose two high-complexity agent-based collaborative MAMAB algorithms with performance guarantee. Then we propose a low-complexity distributed MAMAB which ignores the SBS coordination. To achieve a better balance between SBS coordination gain and computational complexity, we develop an edge-based collaborative MAMAB with the coordination graph edge-based reward assignment method. In the non-stationary environment, we modify the MAMAB-based algorithms proposed in the stationary environment by proposing a practical initialization method and designing new perturbed terms to adapt to the dynamic environment. Simulation results are provided to validate the effectiveness of our proposed algorithms. The effects of different parameters on caching performance are also discussed.

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.

In this paper, we investigate the impact of diverse user preference on learning under the stochastic multi-armed bandit (MAB) framework. We aim to show that when the user preferences are sufficiently diverse and each arm is optimal for certain users, the O(log T ) regret incurred by exploring the sub-optimal arms under the standard stochastic MAB setting can be reduced to a constant. Our intuition is that to achieve sub-linear regret, the number of times an optimal arm being pulled should scale linearly in time; when all arms are optimal for certain users and pulled frequently, the estimated arm statistics can quickly converge to their true values, thus reducing the need of exploration dramatically. We cast the problem into a stochastic linear bandits model, where both user preferences and arm states are modeled as independent and identical distributed (i.i.d) d-dimensional random vectors. After receiving a user preference vector at the beginning of each time slot, the learner pulls an arm and receives a reward as the linear product of the preference vector and the arm state vector. We also assume that the state of the pulled arm is revealed to the learner once it is pulled. We propose a Weighted Upper Confidence Bound (W-UCB) algorithm and show that it can achieve a constant regret when the user preferences are sufficiently diverse. The performance of W-UCB under general setups is also completely characterized and validated with synthetic data.

A general information transmission model, under independent and identically distributed Gaussian codebook and nearest neighbor decoding rule with processed channel output, is investigated using the performance metric of generalized mutual information. When the encoder and the decoder know the statistical channel model, it is found that the optimal channel output processing function is the conditional expectation operator, thus hinting a potential role of regression, a classical topic in machine learning, for this model. Without utilizing the statistical channel model, a problem formulation inspired by machine learning principles is established, with suitable performance metrics introduced. A data-driven inference algorithm is proposed to solve the problem, and the effectiveness of the algorithm is validated via numerical experiments. Extensions to more general information transmission models are also discussed.

Efficient mobility management is an important problem in modern wireless networks with heterogeneous cell sizes and increased node densities. We show that optimization-based mobility protocols cannot achieve long-term optimal performance, particularly for ultra-dense networks in a time-varying environment. To address the complex system dynamics, especially the possible change of statistics due to user movement and environment changes, we propose piece-wise stationary online-learning algorithms to learn the varying throughput distribution and solve the frequent handover problem. The proposed MMBD/MMBSW algorithms are proved to achieve sublinear regret performance in finite time horizon and a linear, non-trivial rigorous regret bound for infinite time horizon. We also study the robustness of the MMBD/MMBSW algorithms under delayed or missing feedback. The simulations show that the proposed algorithms can outperform 3GPP protocols with optimal thresholds. More importantly, they are more robust to system dynamics which are commonly present in practical ultra-dense wireless networks.

We consider a variant of the classic multi-armed bandit problem where the expected reward of each arm is a function of an unknown parameter. The arms are divided into different groups, each of which has a common parameter. Therefore, when the player selects an arm at each time slot, information of other arms in the same group is also revealed. This regional bandit model naturally bridges the non-informative bandit setting where the player can only learn the chosen arm, and the global bandit model where sampling one arms reveals information of all arms. We propose an efficient algorithm, UCB-g, that solves the regional bandit problem by combining the Upper Confidence Bound (UCB) and greedy principles. Both parameter-dependent and parameter-free regret upper bounds are derived. We also establish a matching lower bound, which proves the order-optimality of UCB-g. Moreover, we propose SW-UCB-g, which is an extension of UCB-g for a non-stationary environment where the parameters slowly vary over time.

In-band relay nodes (RNs) can be utilized to enhance the coverage of heterogeneous networks (HetNets) in a cost effective way. However, the in-band RNs also consume the limited spectrum resources. Appropriate spectrum resource management/cooperation is necessary to ensure the balanced resource usages between the macro base stations (BSs) and the RNs. In this paper, we study the sparse spectrum reuse strategy in a HetNet with in-band RNs to maximize the overall proportional fairness metric. Although limiting the number of active reuse patterns will degrade the performance and render the resulting problem non-convex, we first show that there must exist one solution achieving the optimum when the upper bound on the number of active reuse patterns is not less than the total number of mobile stations (MSs) and RNs. We also put forth one active pattern identification scheme based on the re-weighted l1-norm algorithm to deal with the non-convex problem and refine the set of active reuse patterns in a soft manner. Furthermore, in order to offload the heavy computation burden from the central server, one distributed resource allocation algorithm based on the alternating direction method of multipliers (ADMM) algorithm is developed. Numerical simulations demonstrate the superiority and effectiveness of our proposed algorithm.

In time-division duplexing (TDD) systems, massive multiple-input multiple-output (MIMO) relies on the channel reciprocity to obtain the downlink (DL) channel state information (CSI) with the acquired uplink (UL) CSI at the base station (BS). However, the mismatches in the radio frequency (RF) analog circuits at different antennas at the BS break the end-to-end UL and DL channel reciprocity. To restore the channel reciprocity, it is necessary to calibrate all the antennas at the BS. This paper addresses the interconnection strategy for the internal self-calibration at the BS where different antennas are interconnected via hardware transmission lines. Specifically, the paper reveals the optimality of the star interconnection and the daisy chain interconnection respectively. From the results, we see the star interconnection is the optimal interconnection strategy when the B S are given the same number of measurements. On the other hand, the daisy chain interconnection outperforms the star interconnection when the same amount of time resources are consumed. Numerical results corroborate our theoretical analyses.

Inspired by the recent advances in deep learning, we propose a novel iterative belief propagation-convolutional neural network (BP-CNN) architecture to exploit noise correlation for channel decoding under correlated noise. The standard BP decoder is used to estimate the coded bits, followed by a CNN to remove the estimation errors of the BP decoder and obtain a more accurate estimation of the channel noise. Iterating between BP and CNN will gradually improve the decoding SNR and hence result in better decoding performance. To train a well-behaved CNN model, we define a new loss function which involves not only the accuracy of the noise estimation but also the normality test for the estimation errors, i.e., to measure how likely the estimation errors follow a Gaussian distribution. The introduction of the normality test to the CNN training shapes the residual noise distribution and further reduces the BER of the iterative decoding, compared to using the standard quadratic loss function. We carry out extensive experiments to analyze and verify the proposed framework.

Mobile Edge Computing (MEC) (a.k.a. fog computing) has recently emerged to enable low-latency and location-aware data processing at the edge of mobile networks. Providing grid power supply in support of MEC, however, is costly and even infeasible, thus mandating on-site renewable energy as a major or even sole power supply in many scenarios. Nonetheless, the high intermittency and unpredictability of energy harvesting creates many new challenges of performing effective MEC. In this paper, we develop an algorithm called GLOBE that performs joint geographical load balancing (GLB) (for computation workload) and admission control (for communication data traffic), for optimizing the system performance of a network of MEC-enabled base stations. By leveraging the Lyapunov optimization with perturbation technique, GLOBE operates online without requiring future system information and addresses significant challenges caused by battery state dynamics and energy causality constraints. We prove that GLOBE achieves a close-to-optimal system performance compared to the offline algorithm that knows full future information, and present a critical tradeoff between battery capacity and system performance. Simulation results validate our analysis and demonstrate the superior performance of GLOBE compared to benchmark algorithms.

Efficient mobility management is an important problem in modern wireless networks with heterogeneous cell sizes and increased nodes densities. We show that optimization- based mobility protocols cannot achieve long-term optimal performance, particularly in a time-varying environment for ultra-dense networks. To address the complex system dynamics, especially the possible change of statistics due to user movement and environment changes, we propose piece-wise stationary online-learning algorithms to track the activities of small base stations and solve frequent handover (FHO) problems. The BASD/BASSW algorithms are proved to achieve sublinear regret performance in finite time horizon and a linear, non-trivial rigorous bound for infinite time horizon. We study the robustness of the BASD/BASSW algorithms under missing feedback. Simulations show that proposed algorithms can outperform 3GPP protocols with the best threshold, and tend to be more robust than 3GPP to various dynamics which are common in practical ultra- dense wireless networks.

In this paper, we propose a cost-aware cascading bandits model, a new variant of multi-armed bandits with cascading feedback, by considering the random cost of pulling arms. In each step, the learning agent chooses an {\it ordered} list of items and \congr{examines} them sequentially, until certain stopping condition is satisfied. Our objective is then to maximize the expected {\it net reward} in each step, i.e., the reward obtained in each step minus the total cost incurred in examining the items, by deciding the ordered list of items, as well as when to stop examination. We study both the offline and online settings, depending on whether the state and cost statistics of the items are known beforehand. For the offline setting, we show that the Unit Cost Ranking with Threshold 1 (UCR-T1) policy is optimal. For the online setting, we propose a Cost-aware Cascading Upper Confidence Bound (CC-UCB) algorithm, and show that the cumulative regret scales in $O(\log T)$. We also provide a lower bound for all $\alpha$-consistent policies, which scales in $\Omega(\log T)$ and matches our upper bound. The performance of the CC-UCB algorithm is evaluated with both synthetic and real-world data.

The problem of multilevel diversity coding with secure regeneration is revisited. Under the assumption that the eavesdropper can access the repair data for all compromised storage nodes, Shao el al. provided a precise characterization of the minimum-bandwidth-regeneration (MBR) point of the achievable normalized storage-capacity repair-bandwidth tradeoff region. In this paper, it is shown that the MBR point of the achievable normalized storage-capacity repair-bandwidth tradeoff region remains the same even if we assume that the eavesdropper can access the repair data for some compromised storage nodes (type II compromised nodes) but only the data contents of the remaining compromised nodes (type I compromised nodes), as long as the number of type I compromised nodes is no greater than that of type II compromised nodes.

Computation offloading via device-to-device (D2D) communication, or D2D offloading, can enhance mobile computing performance by exploiting spare computing resources of nearby user devices. The success of D2D offloading relies on user participation in collaborative service provisioning, which incurs extra costs to users providing the service, thus mandating an incentive mechanism that can compensate for these costs. Although incentive mechanism design has been intensively studied in the literature, this paper considers a much more challenging yet less investigated problem in which selfish users are also facing interdependent security risks, such as infectious proximity-based attacks. Security cost is significantly different in nature from conventional service provisioning costs such as energy consumption because security risks often depend on the collective behavior of all users. To this end, we build a novel mathematical framework by leveraging the combined power of game theory and epidemic theory to investigate the interplay between user incentives and interdependent security risks in D2D offloading, thereby enabling the design of security-aware incentive mechanisms. Our analysis discovers an interesting “less is more” phenomenon: although giving users more incentives promotes more participation, it may harm the network operator’s utility. This is because too much participation may foster persistent security risks, and as a result, the effective participation level does not improve.

Effective capacity analysis is a powerful tool to investigate the impact of physical layer designs on the link layer delay-sensitive QoS performance, which is important for real-time multimedia applications. In this paper, we rigorously analyze the effective capacities of downlink large-scale antenna systems. The main focus is to establish the fundamental effective capacity in a very-large MIMO system, and to characterize the performance difference between co-located and distributed antenna layouts. To that end, we first analytically derive the closed-form effective capacities for two widely used linear precoding schemes, conjugate beamforming and zero-forcing beamforming. We then analyze the asymptotic average effective capacities when the number of BS antennas and the number of users grow unboundedly with a fixed ratio. The effective capacity gain of the distributed antenna layout over the co-located layout is established via theoretical analysis.

Judiciously setting the base station transmit power that matches its deployment environment is a key problem in ultra dense networks and heterogeneous in-building cellular deployments. A unique characteristic of this problem is the tradeoff between sufficient indoor coverage and limited outdoor leakage, which has to be met without explicit knowledge of the environment. In this paper, we address the small base station (SBS) transmit power assignment problem based on stochastic bandit theory. We explicitly consider power switching penalties to discourage frequent changes of the transmit power, which causes varying coverage and uneven user experience. Unlike existing solutions that rely on RF surveys in the target area, we take advantage of the user behavior with simple coverage feedback in the network. In addition, the proposed power assignment algorithms follow the Bayesian principle to utilize the available prior knowledge and correlation structure from the self configuration phase. Simulations mimicking practical deployments are performed for both single and multiple SBS scenarios, and the resulting power settings are compared to the state-of-the-art solutions. Significant performance gains of the proposed algorithms are observed.

We consider the {n, k, d, l) secure exact-repair regenerating code problem, which generalizes the {n, k, d) exact-repair regenerating code problem with the additional constraint that the stored file needs to be kept information-theoretically secure against an eavesdropper, who can access the data transmitted to regenerate a total of l different failed nodes. For all known results on this problem, the achievable tradeoff regions between the normalized storage capacity and repair bandwidth have a single corner point, achieved by a scheme proposed by Shah, Rashmi and Kumar (the SRK point). Since the achievable tradeoff regions of the exact-repair regenerating code problem without any secrecy constraints are known to have multiple corner points in general, these existing results suggest a phase-change-like behavior, i.e., enforcing a secrecy constraint (l ≥ 1) immediately reduces the tradeoff region to one with a single corner point. In this work, we first show that when the secrecy parameter l is sufficiently large, the SRK point is indeed the only corner point of the tradeoff region. However, when £ is small, we show that the tradeoff region can in fact have multiple corner points. In particular, we establish a precise characterization of the tradeoff region for the (7, 6, 6,1) problem, which has exactly two corner points. Thus, a smooth transition, instead of a phase-change-type of transition, should be expected as the secrecy constraint is gradually strengthened.

In frequency-division duplexing (FDD) massive multiple-input multiple-output (MIMO) systems, the downlink (DL) and uplink (UL) channels are not reciprocal anymore. However, some long-term parameters, e.g. the time delays and angles of arrival (AoAs) of the channel paths, still enjoy reciprocity. In this paper, through efficiently exploiting the aforementioned limited reciprocity, we address the DL channel state information (CSI) feedback in a practical wideband massive MIMO system operating in the FDD mode. In particular, the base station (BS) can transmit the FFT-based pilots with carefully-selected phase shifts to align the DL paths. Then the user can rely on the so-called time-domain aggregate channel (TAC) to derive the feedback of reduced dimensionality per the instructions from the serving BS. We further demonstrate that the BS can recover the DL CSIs with the scalable feedback from the users. Numerical simulation results corroborate our designs.

Indoor temperature monitoring using wireless sensor networks is critical in many applications. For example, in data centers, it is important to monitor if the indoor temperature is within certain range so that the computers can function with near-optimal performance. In contrast to existing research that often separates the sensor network design and the measured temperature, this paper proposes a cyber-physical design approach to monitor the indoor temperature using wireless sensor networks. The source sensor wakes up and senses the temperature periodically using sleep#x002F;wake duty cycles and sends the data to the destination via multi-hop relaying nodes in an anycast way. Moreover, the period of sleep#x002F;wake duty cycle is dynamically adjusted based on the sensed temperature: when the measured temperature is normal, the sensor nodes wake up infrequently for better energy efficiency; as the sensed temperature approaches a pre-determined threshold, the sensor nodes wake up more frequently to avoid any delayed alarm trigger. The proposed design is implemented using TelosB with TinyOS, and experiments confirm that the cyber-physical system reports the alarm with a very small delay while achieving high long-term energy efficiency.

The industry standard 3GPP mobility solutions are analyzed through the lens of bandit learning theory. In particular, it is shown that the original 3GPP handover protocol, developed primarily from a radio frequency and load balancing perspective, can be viewed as a special case of the ε-greedy bandit algorithm, and thus its sub-optimality can be characterized via the regret analysis. Inspired by the equivalence between 3GPP handover protocols and bandit algorithms, we rigorously analyze the performance of cell range expansion in 3GPP handover enhancement, and further propose a learning-based approach to address the frequent handover (FHO) challenges in ultra-dense networks. The key component is to explicitly consider the handover cost to discourage FHOs. Rather surprisingly, we prove that the bandit-inspired scheme with handover cost can be viewed as an enhancement to the simple sticky biasing solution in 3GPP that has been developed to partially address the FHO problem, and hence lay a theoretic foundation to this industrial intuition.

Judiciously setting the base station transmit power that matches its deployment environment is a key problem in ultra-dense networks and heterogeneous in-building cellular deployments. A unique characteristic of this problem is the tradeoff between sufficient indoor coverage and limited outdoor leakage, which has to be met without explicit knowledge of the environment. In this paper, we address the small base station (SBS) transmit power assignment problem based on stochastic bandit theory. Unlike existing solutions that rely on heavy involvement of RF engineers surveying the target area, we take advantage of the human user behavior with simple coverage feedback in the network, and thus significantly reduce the planned human measurement. In addition, the proposed power assignment algorithms follow the Bayesian principle to utilize the available prior knowledge from system self-configuration. To guarantee good performance when the prior knowledge is insufficient, we incorporate the performance correlation among similar power values, and establish an algorithm that exploits the correlation structure to recover majority of the degraded performance. Furthermore, we explicitly consider power switching penalties in order to discourage frequent changes of the transmit power, which cause varying coverage and uneven user experience. Comprehensive system-level simulations are performed for both single and multiple SBS deployment scenarios, and the resulting power settings are compared with the state-of-the-art solutions. Significant performance gains of the proposed algorithms are observed. Particularly, the correlation structure enables the algorithm to converge much faster to the optimal long-term power than other methods.

We consider the (n, k, d, ℓ) secure exact-repair regenerating code problem, which generalizes the (n, k, d) exact-repair regenerating code problem with the additional constraint that the stored file needs to be kept information-theoretically secure against an eavesdropper, who can access the data transmitted to regenerate a total of ℓ different failed nodes. For all known results on this problem, the achievable tradeoff regions between the normalized storage capacity and repair bandwidth have a single corner point, achieved by a scheme proposed by Shah, Rashmi, and Kumar (the SRK point). Since the achievable tradeoff regions of the exact-repair regenerating code problem without any secrecy constraints are known to have multiple corner points in general, these existing results suggest a phasechange-like behavior, i.e., enforcing a secrecy constraint (ℓ ≥ 1) immediately reduces the tradeoff region to one with a single corner point. In this paper, we first show that when the secrecy parameter ℓ is sufficiently large, the SRK point is indeed the only corner point of the tradeoff region. However, when ℓ is small, we show that the tradeoff region can in fact have multiple corner points. In particular, we establish a precise characterization of the tradeoff region for the (7, 6, 6, 1) problem, which has exactly two corner points. Thus, a smooth transition, instead of a phase-change-type of transition, should be expected as the secrecy constraint is gradually strengthened.

Many emerging Big Data applications involve real- time classification in which data instances arriving sequentially over time need to be classified based on their feature vectors. A common and implicit assumption in existing works is that the features become available instantly with the instance and simultaneously with each other, which, however, rarely holds in practice. Instead, features of an instance may experience various random delays to be available. In such scenarios, an important trade-off emerges between accurate classification and timely classification. In this paper, we provide a first formulation of this important problem and propose efficient online algorithms, namely DAlay-aware Real-time Classification (DARC) algorithms, that maximize the classification accuracy given an average classification delay constraint. The algorithms are developed based on the Lyapunov stochastic optimization technique which provides strong performance guarantee. Numerical results on an intrusion detection dataset are provided to show the effectiveness of the proposed algorithm.

This paper studies a layered erasure model for two-user interference channels, which can be viewed as a simplified version of Gaussian fading interference channel. It is assumed that channel state information (CSI) is only available at receivers but not at transmitters. Under such assumption, an outer bound is derived for the capacity region of such interference channel. The new outer bound is tight in many circumstances. For the remaining open cases, the outer bound extends previous results in [1].

Energy efficient mobility management is an important problem in modern wireless networks with heterogeneous cell sizes and increased nodes densities. We show that optimization-based mobility protocols cannot achieve long-term optimal energy consumption, particularly for ultra-dense networks (UDNs). To address the complex dynamics of UDN, we propose a non-stochastic online-learning approach, which does not make any assumption on the statistical behavior of the small base station (SBS) activities. In addition, we introduce handover cost to the overall energy consumption, which forces the resulting solution to explicitly minimize frequent handovers. The proposed batched randomization with exponential weighting (BREW) algorithm relies on batching to explore in bulk, and hence reduces unnecessary handovers. We prove that the regret of BREW is sublinear in time, thus guaranteeing its convergence to the optimal SBS selection. We further study the robustness of the BREW algorithm to delayed or missing feedback. Moreover, we study the setting where SBSs can be dynamically turned ON and OFF. We prove that sublinear regret is impossible with respect to arbitrary SBS ON/OFF, and then develop a novel learning strategy, called ranking expert (RE), that simultaneously takes into account the handover cost and the availability of SBS. To address the high complexity of RE, we propose a contextual ranking expert (CRE) algorithm that only assigns experts in a given context. Rigorous regret bounds are proved for both RE and CRE with respect to the best expert. Simulations show that not only do the proposed mobility algorithms greatly reduce the system energy consumption, but they are also robust to various dynamics which are common in practical ultra-dense wireless networks.

This paper considers an uplink cellular system, in which each base station (BS) is equipped with a large number of antennas to serve multiple single-antenna user equipments (UEs) simultaneously. Uplink training with pilot reusing is adopted to acquire the channel state information (CSI) and maximum ratio combining (MRC) or zero forcing (ZF) reception is used for handling multiuser interference. Leveraging stochastic geometry to model the spatial distribution of UEs, we analyze the statistical distributions of the interferences experienced by a typical uplink: intra-cell interference, inter-cell interference and interference due to pilot contamination. For a practical but still large number of BS antennas, a key observation for MRC reception is that it is the intra-cell interference that accounts for the dominant portion of the total interference. In addition, the interference due to pilot contamination tends to have a much wider distribution range than the inter-cell interference when shadowing is strong, although their mean powers are roughly equal. For ZF reception, on the other hand, we observe a significant reduction of the intra-cell interference compared to MRC reception, while the inter-cell interference and the interference due to pilot contamination remains almost the same, thus demonstrating a substantial superiority over MRC reception.

Electronic tokens have been successfully used as incentive mechanisms to stimulate self-interested network nodes to relay other nodes' traffic. In other words, tokens are paid tobuy transmission(relaying) services. In this work, we propose a novel distributed token exchange framework, which can be usedin heterogeneous small cell networks to successfully mitigate interference among the self-interested users. Contrary to the traditional role of buying transmission, tokens are exchanged between users tobuy silence. Heterogeneity poses unique challenges for interference mitigation, which are difficult to handle with previous solutions but can be effectively tackled with the proposed token design. This paper focuses on the rigorous design of the optimal token scheme that minimizes the system outage probability. We first analyze the optimal strategies of individual users, which only consider their own utility maximization and do not care about the system-wise performance. We prove that under some mild conditions the optimal strategy has a simple threshold structure. We then analytically derive the optimal token supply that minimizes the network outage probability. Analysis shows that even if each user adopts the optimal strategy that only maximizes its own utility, a careful token system design can lead to a significant overall network performance improvement. Simulation results show that not only does the proposed token system design greatly improve the network outage probability, it also improves the overall network QoS, particularly when the deployment density is high.

Electronic tokens have been proved as an effective incentive scheme in stimulating self-interested network nodes to transmit other nodes' traffic. In other words, tokens are paid to buy transmission. In this work, we propose a novel token framework in a distributed small cell network and design the token system for improved interference mitigation. Contrary to the traditional role of tokens for buying transmission, they are exchanged between users to buy "silence". We focus on designing the optimal token system that minimizes the system outage probability. We first analyze the optimal strategies of individual users, which only consider their own utility maximization and do not care about the system-wise performance. We show that under some mild conditions the optimal strategy has a simple threshold structure. We then analytically derive the optimal token supply that minimizes the network outage probability. Simulation results show that not only does the proposed token system design greatly improve the network outage probability (by up to 75%), it also improves the overall small cell network QoS, particularly when the deployment density is high.

This paper focuses on studying the fundamental performance limits and linear dispersion code design for the MIMO-ARQ slow fading channel. The optimal average rate of well-known HARQ protocols is analyzed. The optimal design of space-time coding for the MIMO-ARQ channel is discussed. Information-theoretic measures are used to optimize the rate assignment and derive the optimum design criterion, which is then used to evaluate the optimality of existing space-time codes. A different design criterion, which is obtained from the error probability analysis of space-time coded MIMO-HARQ, is presented. Examples are studied to reveal the gain of ARQ feedback in space-time coded MIMO systems.

The problem of efficient communication over a scalar quasi-static fading channel is considered. The single-layer transmission (SLT) and multi-layer transmission (MLT) schemes do not require any knowledge of the channel state information (CSI) at the transmitter, but their performance is also limited. It is shown that using Hybrid-ARQ (HARQ) can significantly improve the average rate performance, provided that the rate assignment between different ARQ rounds is carefully chosen. The average rate performance of several HARQ schemes is optimized and compared. In addition, optimal power allocation among retransmissions is derived and shown to further increase the average rate. This power allocation gain is remarkable at low signal-to-noise ratio (SNR), but becomes negligible at high SNR. Comparison of two different types of limited feedback, sequential feedback (ARQ) and one-shot feedback (quantized CSI), is made from several perspectives. Although the optimization problem is formed with respect to the average rate, simulation results give a comprehensive comparison under different metrics, including average rate, outage probability, and the combination of both. Substantial performance improvement is observed with even one ARQ retransmission in all simulations. More importantly, this gain appears to be robust with respect to the fading distributions.

Different error protection capabilities associated with different bit positions in a constellation are utilized to provide unequal error protection (UEP) with multilevel coding (MLC) on AWGN and fast/slow fading channels. Unlike previous work on this problem, the design tool in this paper is the symmetric information rate (SIR), which is well suited to the use of modern component codes. The constellation design problem is addressed from two perspectives: bits-to-symbol mapping, and positions of constellation points. Design guidelines of MLC for UEP are presented, and examples are shown to demonstrate the validity of the proposed method. It is further shown that the proposed design is especially desirable for communication over a slow-fading wireless channel, as it allows for a gradual performance degradation with the decreasing receive SNR. Throughput advantages are shown to support this claim.

The problem of efficient communication over a quasi-static wireless fading channel is considered in this paper. The disadvantages of two well-known schemes, single-layer transmission (SLT) and multi-layer transmission (MLT), are pointed out. A new scheme named aggressive transmission with ARQ (AT-ARQ) is developed and optimized to provide better performance, at the expense of requiring ARQ feedback. Optimal power allocation among (re)transmissions is derived. A comprehensive performance comparison of the three schemes, under different performance metrics such as throughput, outage probability, and the combination of two, is reported via numerical simulations. Substantial performance improvement is observed with even 1-bit ARQ feedback in Rayleigh fading.

The observation that different bit positions in a constellation typically have different error protection capabilities is utilized to design unequal error protection (UEP) with multilevel coding (MLC) in AWGN and fading channels. Both parallel independent decoding (PID) and multi-stage decoding (MSD) are considered. The design tool in this work is the symmetric information rate (SIR), which is well suited to the use of capacity-approaching component codes. This paper first formulates the UEP design as a utility maximization problem, and then considers some optimal UEP designs, including mapping, non-uniform constellation, bits grouping, and decoding order in MSD. Several exemplary utility functions are studied, corresponding to different application scenarios. The UEP design is especially beneficial in a slow fading channel, as it allows for a gradual performance degradation with the decreasing receive SNR. Average rate advantage is shown to quantify this gain.

The MIMO-OFDM beamforming design problem is addressed from a system level standpoint. A beamforming method is proposed which helps improve the receiver channel estimation performance without degrading any benefit of a conventional beamformer. To that end, the smoothed singular value decomposition (SSVD) algorithm is first developed to get "close" effective channels after beamforming for two adjacent subcarriers. Based on the SSVD algorithm, the frequency smoothed beamformer (FSB) design is then derived, in which smooth effective channels across all subcarriers are generated and thus the receiver can apply interpolation and smoothing to improve the channel estimation performance. The close singular value problem is discussed. Statistical characteristics of the effective channel are analyzed, which is used to design channel estimation for the beamformed channel. Simulation results show that the FSB design is efficient in the IEEE 802.11n setting.

We study the problem of optimal resource allocation for multi-user multiaccess wireless video communication from an information-theoretic point of view. We derive the optimal resource allocation policies by directly maximizing at the application layer the weighted sum of video qualities of all users, subject to information-theoretic multiaccess capacity region constraints in theMAC-PHY layers.We solve this problem for three multiaccess capacity regions: 1) non-fading channel, 2) fading channel with a given power control policy, and 3) fading channel with dynamic power control policies. The optimal resource allocation policy is referred as Largest Quality Improvement Highest Possible Rate (LQIHPR). We propose simple greedy algorithms to implement this policy. Since the capacity region is the fundamental characterization of achievable rates, the solutions developed in this paper provide the operational upper bound of achievable video quality in a multiaccess fading channel.

We study the problem of optimal resource allocation for multi-user wireless video transmissions from an information- theoretic point of view. We show that the previously known optimal rate allocation solution in wireless multiaccess which maximizes the weighted sum rate is suboptimal in wireless video communications. We further derive the optimal video resource allocation by jointly considering the Application-MAC-PHY layers. This optimal scheme maximizes the weighted sum video quality of all video users for any feasible power control policy. We refer to this policy as Largest Quality Improvement Highest Possible Rate (LQIHPR). We propose a simple greedy algorithm for implementation. With the help of the inherent prioritization mechanism of video coders, we show that LQIHPR is universally optimal for all video coding schemes. Simulation results demonstrate the significant improvement LQIHPR leads to as opposed to the conventional one.

The authors develop a generalized layered orthogonal lattice detector (G-LORD) for the golden code. G-LORD includes the previously developed LORD algorithm and exhaustive search ML detection as special cases, and is proved to achieve the perfect balance between error performance and complexity. Meanwhile, G-LORD is suitable for parallel implementations, and has a deterministic complexity as opposed to the sphere decoder approach. Thanks to the special structure of the golden code, G-LORD can implement the optimal ordering with very low complexity. Most importantly, G-LORD can efficiently generate bit soft-output metric when golden code is concatenated with outer channel code. The development of G-LORD boosts the practical application of the golden code.

This paper takes a system view of the MIMO-OFDM beamformer design problem. We present a design method that helps improve the receiver channel estimation performance without damaging the optimality of beamforming. We design a so-called smoothed singular value decomposition (SSVD) algorithm to get smooth equivalent channels after beamforming, and thus the receiver can apply interpolation and smoothing to improve channel estimation. We then present some analysis of the statistical characteristics of the equivalent channel, which will be useful in designing the channel estimation. Simulation results are shown to support our algorithm.